1/* Value Numbering routines for tree expressions.
2   Copyright (C) 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc.
3   Contributed by Daniel Berlin <dan@dberlin.org>, Steven Bosscher
4   <stevenb@suse.de> and Diego Novillo <dnovillo@redhat.com>
5
6This file is part of GCC.
7
8GCC is free software; you can redistribute it and/or modify
9it under the terms of the GNU General Public License as published by
10the Free Software Foundation; either version 2, or (at your option)
11any later version.
12
13GCC is distributed in the hope that it will be useful,
14but WITHOUT ANY WARRANTY; without even the implied warranty of
15MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
16GNU General Public License for more details.
17
18You should have received a copy of the GNU General Public License
19along with GCC; see the file COPYING.  If not, write to
20the Free Software Foundation, 51 Franklin Street, Fifth Floor,
21Boston, MA 02110-1301, USA.  */
22
23#include "config.h"
24#include "system.h"
25#include "coretypes.h"
26#include "tm.h"
27#include "ggc.h"
28#include "tree.h"
29#include "tree-flow.h"
30#include "hashtab.h"
31#include "langhooks.h"
32#include "tree-pass.h"
33#include "tree-dump.h"
34#include "diagnostic.h"
35
36/* The value table that maps expressions to values.  */
37static htab_t value_table;
38
39/* Map expressions to values.  These are simple pairs of expressions
40   and the values they represent.  To find the value represented by
41   an expression, we use a hash table where the elements are {e,v}
42   pairs, and the expression is the key.  */
43typedef struct val_expr_pair_d
44{
45  /* Value handle.  */
46  tree v;
47
48  /* Associated expression.  */
49  tree e;
50
51  /* For comparing virtual uses in E.  */
52  VEC (tree, gc) *vuses;
53
54  /* E's hash value.  */
55  hashval_t hashcode;
56} *val_expr_pair_t;
57
58static void set_value_handle (tree e, tree v);
59
60
61/* Create and return a new value handle node of type TYPE.  */
62
63static tree
64make_value_handle (tree type)
65{
66  static unsigned int id = 0;
67  tree vh;
68
69  vh = build0 (VALUE_HANDLE, type);
70  VALUE_HANDLE_ID (vh) = id++;
71  return vh;
72}
73
74
75/* Given an expression EXPR, compute a hash value number using the
76   code of the expression, its real operands and virtual operands (if
77   any).
78
79   VAL can be used to iterate by passing previous value numbers (it is
80   used by iterative_hash_expr).  */
81
82hashval_t
83vn_compute (tree expr, hashval_t val)
84{
85  /* EXPR must not be a statement.  We are only interested in value
86     numbering expressions on the RHS of assignments.  */
87  gcc_assert (expr);
88  gcc_assert (!expr->common.ann
89	      || expr->common.ann->common.type != STMT_ANN);
90
91  val = iterative_hash_expr (expr, val);
92  return val;
93}
94
95/* Compare two expressions E1 and E2 and return true if they are
96   equal.  */
97
98bool
99expressions_equal_p (tree e1, tree e2)
100{
101  tree te1, te2;
102
103  if (e1 == e2)
104    return true;
105
106  te1 = TREE_TYPE (e1);
107  te2 = TREE_TYPE (e2);
108
109  if (TREE_CODE (e1) == TREE_LIST && TREE_CODE (e2) == TREE_LIST)
110    {
111      tree lop1 = e1;
112      tree lop2 = e2;
113      for (lop1 = e1, lop2 = e2;
114	   lop1 || lop2;
115	   lop1 = TREE_CHAIN (lop1), lop2 = TREE_CHAIN (lop2))
116	{
117	  if (!lop1 || !lop2)
118	    return false;
119	  if (!expressions_equal_p (TREE_VALUE (lop1), TREE_VALUE (lop2)))
120	    return false;
121	}
122      return true;
123
124    }
125  else if (TREE_CODE (e1) == TREE_CODE (e2)
126	   && (te1 == te2 || lang_hooks.types_compatible_p (te1, te2))
127	   && operand_equal_p (e1, e2, OEP_PURE_SAME))
128    return true;
129
130  return false;
131}
132
133
134/* Hash a {v,e} pair that is pointed to by P.
135   The hashcode is cached in the val_expr_pair, so we just return
136   that.  */
137
138static hashval_t
139val_expr_pair_hash (const void *p)
140{
141  const val_expr_pair_t ve = (val_expr_pair_t) p;
142  return ve->hashcode;
143}
144
145
146/* Given two val_expr_pair_t's, return true if they represent the same
147   expression, false otherwise.
148   P1 and P2 should point to the val_expr_pair_t's to be compared.  */
149
150static int
151val_expr_pair_expr_eq (const void *p1, const void *p2)
152{
153  int i;
154  tree vuse1;
155  const val_expr_pair_t ve1 = (val_expr_pair_t) p1;
156  const val_expr_pair_t ve2 = (val_expr_pair_t) p2;
157
158  if (! expressions_equal_p (ve1->e, ve2->e))
159    return false;
160
161  if (ve1->vuses == ve2->vuses)
162    return true;
163
164  if (VEC_length (tree, ve1->vuses) != VEC_length (tree, ve2->vuses))
165    return false;
166
167  for (i = 0; VEC_iterate (tree, ve1->vuses, i, vuse1); i++)
168    {
169      if (VEC_index (tree, ve2->vuses, i) != vuse1)
170	return false;
171    }
172  return true;
173}
174
175
176/* Set the value handle for expression E to value V.  */
177
178static void
179set_value_handle (tree e, tree v)
180{
181  if (TREE_CODE (e) == SSA_NAME)
182    SSA_NAME_VALUE (e) = v;
183  else if (EXPR_P (e) || DECL_P (e) || TREE_CODE (e) == TREE_LIST
184	   || TREE_CODE (e) == CONSTRUCTOR)
185    get_tree_common_ann (e)->value_handle = v;
186  else
187    /* Do nothing.  Constants are their own value handles.  */
188    gcc_assert (is_gimple_min_invariant (e));
189}
190
191/* Copy the virtual uses from STMT into a newly allocated VEC(tree),
192   and return the VEC(tree).  */
193
194static VEC (tree, gc) *
195copy_vuses_from_stmt (tree stmt)
196{
197  ssa_op_iter iter;
198  tree vuse;
199  VEC (tree, gc) *vuses = NULL;
200
201  if (!stmt)
202    return NULL;
203
204  FOR_EACH_SSA_TREE_OPERAND (vuse, stmt, iter, SSA_OP_VUSE)
205    VEC_safe_push (tree, gc, vuses, vuse);
206
207  return vuses;
208}
209
210/* Place for shared_vuses_from_stmt to shove vuses.  */
211static VEC (tree, gc) *shared_lookup_vuses;
212
213/* Copy the virtual uses from STMT into SHARED_LOOKUP_VUSES.
214   This function will overwrite the current SHARED_LOOKUP_VUSES
215   variable.  */
216
217static VEC (tree, gc) *
218shared_vuses_from_stmt (tree stmt)
219{
220  ssa_op_iter iter;
221  tree vuse;
222
223  if (!stmt)
224    return NULL;
225
226  VEC_truncate (tree, shared_lookup_vuses, 0);
227
228  FOR_EACH_SSA_TREE_OPERAND (vuse, stmt, iter, SSA_OP_VUSE)
229    VEC_safe_push (tree, gc, shared_lookup_vuses, vuse);
230
231  if (VEC_length (tree, shared_lookup_vuses) > 1)
232    sort_vuses (shared_lookup_vuses);
233
234  return shared_lookup_vuses;
235}
236
237/* Insert EXPR into VALUE_TABLE with value VAL, and add expression
238   EXPR to the value set for value VAL.  */
239
240void
241vn_add (tree expr, tree val)
242{
243  vn_add_with_vuses (expr, val, NULL);
244}
245
246/* Insert EXPR into VALUE_TABLE with value VAL, and add expression
247   EXPR to the value set for value VAL.  VUSES represents the virtual
248   use operands associated with EXPR.  It is used when computing a
249   hash value for EXPR.  */
250
251void
252vn_add_with_vuses (tree expr, tree val, VEC (tree, gc) *vuses)
253{
254  void **slot;
255  val_expr_pair_t new_pair;
256
257  new_pair = XNEW (struct val_expr_pair_d);
258  new_pair->e = expr;
259  new_pair->v = val;
260  new_pair->vuses = vuses;
261  new_pair->hashcode = vn_compute (expr, 0);
262  slot = htab_find_slot_with_hash (value_table, new_pair, new_pair->hashcode,
263				   INSERT);
264  if (*slot)
265    free (*slot);
266  *slot = (void *) new_pair;
267
268  set_value_handle (expr, val);
269  if (TREE_CODE (val) == VALUE_HANDLE)
270    add_to_value (val, expr);
271}
272
273
274/* Search in VALUE_TABLE for an existing instance of expression EXPR,
275   and return its value, or NULL if none has been set.  STMT
276   represents the stmt associated with EXPR.  It is used when computing the
277   hash value for EXPR.  */
278
279tree
280vn_lookup (tree expr, tree stmt)
281{
282  return vn_lookup_with_vuses (expr, shared_vuses_from_stmt (stmt));
283}
284
285/* Search in VALUE_TABLE for an existing instance of expression EXPR,
286   and return its value, or NULL if none has been set.  VUSES is the
287   list of virtual use operands associated with EXPR.  It is used when
288   computing the hash value for EXPR.  */
289
290tree
291vn_lookup_with_vuses (tree expr, VEC (tree, gc) *vuses)
292{
293  void **slot;
294  struct val_expr_pair_d vep = {NULL, NULL, NULL, 0};
295
296  /* Constants are their own value.  */
297  if (is_gimple_min_invariant (expr))
298    return expr;
299
300  vep.e = expr;
301  vep.vuses = vuses;
302  vep.hashcode = vn_compute (expr, 0);
303  slot = htab_find_slot_with_hash (value_table, &vep, vep.hashcode, NO_INSERT);
304  if (!slot)
305    return NULL_TREE;
306  else
307    return ((val_expr_pair_t) *slot)->v;
308}
309
310
311/* A comparison function for use in qsort to compare vuses.  Simply
312   subtracts version numbers.  */
313
314static int
315vuses_compare (const void *pa, const void *pb)
316{
317  const tree vusea = *((const tree *)pa);
318  const tree vuseb = *((const tree *)pb);
319  int sn = SSA_NAME_VERSION (vusea) - SSA_NAME_VERSION (vuseb);
320
321  return sn;
322}
323
324/* Print out the "Created value <x> for <Y>" statement to the
325   dump_file.
326   This is factored because both versions of lookup use it, and it
327   obscures the real work going on in those functions.  */
328
329static void
330print_creation_to_file (tree v, tree expr, VEC (tree, gc) *vuses)
331{
332  fprintf (dump_file, "Created value ");
333  print_generic_expr (dump_file, v, dump_flags);
334  fprintf (dump_file, " for ");
335  print_generic_expr (dump_file, expr, dump_flags);
336
337  if (vuses && VEC_length (tree, vuses) != 0)
338    {
339      size_t i;
340      tree vuse;
341
342      fprintf (dump_file, " vuses: (");
343      for (i = 0; VEC_iterate (tree, vuses, i, vuse); i++)
344	{
345	  print_generic_expr (dump_file, vuse, dump_flags);
346	  if (VEC_length (tree, vuses) - 1 != i)
347	    fprintf (dump_file, ",");
348	}
349      fprintf (dump_file, ")");
350    }
351  fprintf (dump_file, "\n");
352}
353
354/* Like vn_lookup, but creates a new value for expression EXPR, if
355   EXPR doesn't already have a value.  Return the existing/created
356   value for EXPR.  STMT represents the stmt associated with EXPR.  It
357   is used when computing the VUSES for EXPR.  */
358
359tree
360vn_lookup_or_add (tree expr, tree stmt)
361{
362  tree v = vn_lookup (expr, stmt);
363  if (v == NULL_TREE)
364    {
365      VEC(tree,gc) *vuses;
366
367      v = make_value_handle (TREE_TYPE (expr));
368      vuses = copy_vuses_from_stmt (stmt);
369      sort_vuses (vuses);
370
371      if (dump_file && (dump_flags & TDF_DETAILS))
372	print_creation_to_file (v, expr, vuses);
373
374      VALUE_HANDLE_VUSES (v) = vuses;
375      vn_add_with_vuses (expr, v, vuses);
376    }
377
378  set_value_handle (expr, v);
379
380  return v;
381}
382
383/* Sort the VUSE array so that we can do equality comparisons
384   quicker on two vuse vecs.  */
385
386void
387sort_vuses (VEC (tree,gc) *vuses)
388{
389  if (VEC_length (tree, vuses) > 1)
390    qsort (VEC_address (tree, vuses),
391	   VEC_length (tree, vuses),
392	   sizeof (tree),
393	   vuses_compare);
394}
395
396/* Like vn_lookup, but creates a new value for expression EXPR, if
397   EXPR doesn't already have a value.  Return the existing/created
398   value for EXPR.  STMT represents the stmt associated with EXPR.  It is used
399   when computing the hash value for EXPR.  */
400
401tree
402vn_lookup_or_add_with_vuses (tree expr, VEC (tree, gc) *vuses)
403{
404  tree v = vn_lookup_with_vuses (expr, vuses);
405  if (v == NULL_TREE)
406    {
407      v = make_value_handle (TREE_TYPE (expr));
408      sort_vuses (vuses);
409
410      if (dump_file && (dump_flags & TDF_DETAILS))
411	print_creation_to_file (v, expr, vuses);
412
413      VALUE_HANDLE_VUSES (v) = vuses;
414      vn_add_with_vuses (expr, v, vuses);
415    }
416
417  set_value_handle (expr, v);
418
419  return v;
420}
421
422
423
424/* Get the value handle of EXPR.  This is the only correct way to get
425   the value handle for a "thing".  If EXPR does not have a value
426   handle associated, it returns NULL_TREE.
427   NB: If EXPR is min_invariant, this function is *required* to return EXPR.  */
428
429tree
430get_value_handle (tree expr)
431{
432
433  if (is_gimple_min_invariant (expr))
434    return expr;
435
436  if (TREE_CODE (expr) == SSA_NAME)
437    return SSA_NAME_VALUE (expr);
438  else if (EXPR_P (expr) || DECL_P (expr) || TREE_CODE (expr) == TREE_LIST
439	   || TREE_CODE (expr) == CONSTRUCTOR)
440    {
441      tree_ann_common_t ann = tree_common_ann (expr);
442      return ((ann) ? ann->value_handle : NULL_TREE);
443    }
444  else
445    gcc_unreachable ();
446}
447
448
449/* Initialize data structures used in value numbering.  */
450
451void
452vn_init (void)
453{
454  value_table = htab_create (511, val_expr_pair_hash,
455			     val_expr_pair_expr_eq, free);
456  shared_lookup_vuses = NULL;
457}
458
459
460/* Delete data used for value numbering.  */
461
462void
463vn_delete (void)
464{
465  htab_delete (value_table);
466  VEC_free (tree, gc, shared_lookup_vuses);
467  value_table = NULL;
468}
469