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  tree stmt;
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
82   STMT is the stmt associated with EXPR for comparing virtual operands.  */
83
84hashval_t
85vn_compute (tree expr, hashval_t val, tree stmt)
86{
87  ssa_op_iter iter;
88  tree vuse;
89
90  /* EXPR must not be a statement.  We are only interested in value
91     numbering expressions on the RHS of assignments.  */
92  gcc_assert (expr);
93  gcc_assert (!expr->common.ann
94	      || expr->common.ann->common.type != STMT_ANN);
95
96  val = iterative_hash_expr (expr, val);
97
98  /* If the expression has virtual uses, incorporate them into the
99     hash value computed for EXPR.  */
100  if (stmt)
101    FOR_EACH_SSA_TREE_OPERAND (vuse, stmt, iter, SSA_OP_VUSE)
102      val = iterative_hash_expr (vuse,  val);
103
104  return val;
105}
106
107
108/* Compare two expressions E1 and E2 and return true if they are
109   equal.  */
110
111bool
112expressions_equal_p (tree e1, tree e2)
113{
114  tree te1, te2;
115
116  if (e1 == e2)
117    return true;
118
119  te1 = TREE_TYPE (e1);
120  te2 = TREE_TYPE (e2);
121
122  if (TREE_CODE (e1) == TREE_LIST && TREE_CODE (e2) == TREE_LIST)
123    {
124      tree lop1 = e1;
125      tree lop2 = e2;
126      for (lop1 = e1, lop2 = e2;
127	   lop1 || lop2;
128	   lop1 = TREE_CHAIN (lop1), lop2 = TREE_CHAIN (lop2))
129	{
130	  if (!lop1 || !lop2)
131	    return false;
132	  if (!expressions_equal_p (TREE_VALUE (lop1), TREE_VALUE (lop2)))
133	    return false;
134	}
135      return true;
136
137    }
138  else if (TREE_CODE (e1) == TREE_CODE (e2)
139	   && (te1 == te2 || lang_hooks.types_compatible_p (te1, te2))
140	   && operand_equal_p (e1, e2, OEP_PURE_SAME))
141    return true;
142
143  return false;
144}
145
146
147/* Hash a {v,e} pair that is pointed to by P.
148   The hashcode is cached in the val_expr_pair, so we just return
149   that.  */
150
151static hashval_t
152val_expr_pair_hash (const void *p)
153{
154  const val_expr_pair_t ve = (val_expr_pair_t) p;
155  return ve->hashcode;
156}
157
158
159/* Given two val_expr_pair_t's, return true if they represent the same
160   expression, false otherwise.
161   P1 and P2 should point to the val_expr_pair_t's to be compared.  */
162
163static int
164val_expr_pair_expr_eq (const void *p1, const void *p2)
165{
166  bool ret;
167  const val_expr_pair_t ve1 = (val_expr_pair_t) p1;
168  const val_expr_pair_t ve2 = (val_expr_pair_t) p2;
169
170  if (! expressions_equal_p (ve1->e, ve2->e))
171    return false;
172
173  ret = compare_ssa_operands_equal (ve1->stmt, ve2->stmt, SSA_OP_VUSE);
174  return ret;
175}
176
177
178/* Set the value handle for expression E to value V.  */
179
180static void
181set_value_handle (tree e, tree v)
182{
183  if (TREE_CODE (e) == SSA_NAME)
184    SSA_NAME_VALUE (e) = v;
185  else if (EXPR_P (e) || DECL_P (e) || TREE_CODE (e) == TREE_LIST
186	   || TREE_CODE (e) == CONSTRUCTOR)
187    get_tree_ann (e)->common.value_handle = v;
188  else
189    /* Do nothing.  Constants are their own value handles.  */
190    gcc_assert (is_gimple_min_invariant (e));
191}
192
193
194/* Insert EXPR into VALUE_TABLE with value VAL, and add expression
195   EXPR to the value set for value VAL.  STMT represents the stmt
196   associated with EXPR.  It is used when computing a hash value for EXPR.  */
197
198void
199vn_add (tree expr, tree val, tree stmt)
200{
201  void **slot;
202  val_expr_pair_t new_pair;
203
204  new_pair = xmalloc (sizeof (struct val_expr_pair_d));
205  new_pair->e = expr;
206  new_pair->v = val;
207  new_pair->stmt = stmt;
208  new_pair->hashcode = vn_compute (expr, 0, stmt);
209  slot = htab_find_slot_with_hash (value_table, new_pair, new_pair->hashcode,
210				   INSERT);
211  if (*slot)
212    free (*slot);
213  *slot = (void *) new_pair;
214
215  set_value_handle (expr, val);
216  add_to_value (val, expr);
217}
218
219
220/* Search in VALUE_TABLE for an existing instance of expression EXPR,
221   and return its value, or NULL if none has been set.  STMT
222   represents the stmt associated with EXPR.  It is used when computing the
223   hash value for EXPR.  */
224
225tree
226vn_lookup (tree expr, tree stmt)
227{
228  void **slot;
229  struct val_expr_pair_d vep = {NULL, NULL, NULL, 0};
230
231  /* Constants are their own value.  */
232  if (is_gimple_min_invariant (expr))
233    return expr;
234
235  vep.e = expr;
236  vep.stmt = stmt;
237  vep.hashcode = vn_compute (expr, 0, stmt);
238  slot = htab_find_slot_with_hash (value_table, &vep, vep.hashcode, NO_INSERT);
239  if (!slot)
240    return NULL_TREE;
241  else
242    return ((val_expr_pair_t) *slot)->v;
243}
244
245
246/* Like vn_lookup, but creates a new value for expression EXPR, if
247   EXPR doesn't already have a value.  Return the existing/created
248   value for EXPR.  STMT represents the stmt associated with EXPR.  It is used
249   when computing the hash value for EXPR.  */
250
251tree
252vn_lookup_or_add (tree expr, tree stmt)
253{
254  tree v = vn_lookup (expr, stmt);
255  if (v == NULL_TREE)
256    {
257      v = make_value_handle (TREE_TYPE (expr));
258
259      if (dump_file && (dump_flags & TDF_DETAILS))
260	{
261	  fprintf (dump_file, "Created value ");
262	  print_generic_expr (dump_file, v, dump_flags);
263	  fprintf (dump_file, " for ");
264	  print_generic_expr (dump_file, expr, dump_flags);
265	  fprintf (dump_file, "\n");
266	}
267
268      vn_add (expr, v, stmt);
269    }
270
271  set_value_handle (expr, v);
272
273  return v;
274}
275
276
277/* Get the value handle of EXPR.  This is the only correct way to get
278   the value handle for a "thing".  If EXPR does not have a value
279   handle associated, it returns NULL_TREE.
280   NB: If EXPR is min_invariant, this function is *required* to return EXPR.  */
281
282tree
283get_value_handle (tree expr)
284{
285
286  if (is_gimple_min_invariant (expr))
287    return expr;
288
289  if (TREE_CODE (expr) == SSA_NAME)
290    return SSA_NAME_VALUE (expr);
291  else if (EXPR_P (expr) || DECL_P (expr) || TREE_CODE (expr) == TREE_LIST
292	   || TREE_CODE (expr) == CONSTRUCTOR)
293    {
294      tree_ann_t ann = tree_ann (expr);
295      return ((ann) ? ann->common.value_handle : NULL_TREE);
296    }
297  else
298    gcc_unreachable ();
299}
300
301
302/* Initialize data structures used in value numbering.  */
303
304void
305vn_init (void)
306{
307  value_table = htab_create (511, val_expr_pair_hash,
308			     val_expr_pair_expr_eq, free);
309}
310
311
312/* Delete data used for value numbering.  */
313
314void
315vn_delete (void)
316{
317  htab_delete (value_table);
318  value_table = NULL;
319}
320