* sv.po, zh_CN.po: Update.
[official-gcc.git] / gcc / tree-vn.c
blob38ba39b69bbbf8535dc0b957d911a84334873a19
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>
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify
9 it under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 2, or (at your option)
11 any later version.
13 GCC is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 GNU General Public License for more details.
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING. If not, write to
20 the Free Software Foundation, 51 Franklin Street, Fifth Floor,
21 Boston, MA 02110-1301, USA. */
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"
36 /* The value table that maps expressions to values. */
37 static htab_t value_table;
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. */
43 typedef struct val_expr_pair_d
45 /* Value handle. */
46 tree v;
48 /* Associated expression. */
49 tree e;
51 /* for comparing Virtual uses in E. */
52 tree stmt;
54 /* E's hash value. */
55 hashval_t hashcode;
56 } *val_expr_pair_t;
58 static void set_value_handle (tree e, tree v);
61 /* Create and return a new value handle node of type TYPE. */
63 static tree
64 make_value_handle (tree type)
66 static unsigned int id = 0;
67 tree vh;
69 vh = build0 (VALUE_HANDLE, type);
70 VALUE_HANDLE_ID (vh) = id++;
71 return vh;
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).
79 VAL can be used to iterate by passing previous value numbers (it is
80 used by iterative_hash_expr).
82 STMT is the stmt associated with EXPR for comparing virtual operands. */
84 hashval_t
85 vn_compute (tree expr, hashval_t val, tree stmt)
87 ssa_op_iter iter;
88 tree vuse;
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);
96 val = iterative_hash_expr (expr, val);
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);
104 return val;
108 /* Compare two expressions E1 and E2 and return true if they are
109 equal. */
111 bool
112 expressions_equal_p (tree e1, tree e2)
114 tree te1, te2;
116 if (e1 == e2)
117 return true;
119 te1 = TREE_TYPE (e1);
120 te2 = TREE_TYPE (e2);
122 if (TREE_CODE (e1) == TREE_LIST && TREE_CODE (e2) == TREE_LIST)
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))
130 if (!lop1 || !lop2)
131 return false;
132 if (!expressions_equal_p (TREE_VALUE (lop1), TREE_VALUE (lop2)))
133 return false;
135 return true;
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;
143 return false;
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. */
151 static hashval_t
152 val_expr_pair_hash (const void *p)
154 const val_expr_pair_t ve = (val_expr_pair_t) p;
155 return ve->hashcode;
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. */
163 static int
164 val_expr_pair_expr_eq (const void *p1, const void *p2)
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;
170 if (! expressions_equal_p (ve1->e, ve2->e))
171 return false;
173 ret = compare_ssa_operands_equal (ve1->stmt, ve2->stmt, SSA_OP_VUSE);
174 return ret;
178 /* Set the value handle for expression E to value V. */
180 static void
181 set_value_handle (tree e, tree v)
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 get_tree_ann (e)->common.value_handle = v;
187 else
188 /* Do nothing. Constants are their own value handles. */
189 gcc_assert (is_gimple_min_invariant (e));
193 /* Insert EXPR into VALUE_TABLE with value VAL, and add expression
194 EXPR to the value set for value VAL. STMT represents the stmt
195 associated with EXPR. It is used when computing a hash value for EXPR. */
197 void
198 vn_add (tree expr, tree val, tree stmt)
200 void **slot;
201 val_expr_pair_t new_pair;
203 new_pair = xmalloc (sizeof (struct val_expr_pair_d));
204 new_pair->e = expr;
205 new_pair->v = val;
206 new_pair->stmt = stmt;
207 new_pair->hashcode = vn_compute (expr, 0, stmt);
208 slot = htab_find_slot_with_hash (value_table, new_pair, new_pair->hashcode,
209 INSERT);
210 if (*slot)
211 free (*slot);
212 *slot = (void *) new_pair;
214 set_value_handle (expr, val);
215 add_to_value (val, expr);
219 /* Search in VALUE_TABLE for an existing instance of expression EXPR,
220 and return its value, or NULL if none has been set. STMT
221 represents the stmt associated with EXPR. It is used when computing the
222 hash value for EXPR. */
224 tree
225 vn_lookup (tree expr, tree stmt)
227 void **slot;
228 struct val_expr_pair_d vep = {NULL, NULL, NULL, 0};
230 /* Constants are their own value. */
231 if (is_gimple_min_invariant (expr))
232 return expr;
234 vep.e = expr;
235 vep.stmt = stmt;
236 vep.hashcode = vn_compute (expr, 0, stmt);
237 slot = htab_find_slot_with_hash (value_table, &vep, vep.hashcode, NO_INSERT);
238 if (!slot)
239 return NULL_TREE;
240 else
241 return ((val_expr_pair_t) *slot)->v;
245 /* Like vn_lookup, but creates a new value for expression EXPR, if
246 EXPR doesn't already have a value. Return the existing/created
247 value for EXPR. STMT represents the stmt associated with EXPR. It is used
248 when computing the hash value for EXPR. */
250 tree
251 vn_lookup_or_add (tree expr, tree stmt)
253 tree v = vn_lookup (expr, stmt);
254 if (v == NULL_TREE)
256 v = make_value_handle (TREE_TYPE (expr));
258 if (dump_file && (dump_flags & TDF_DETAILS))
260 fprintf (dump_file, "Created value ");
261 print_generic_expr (dump_file, v, dump_flags);
262 fprintf (dump_file, " for ");
263 print_generic_expr (dump_file, expr, dump_flags);
264 fprintf (dump_file, "\n");
267 vn_add (expr, v, stmt);
270 set_value_handle (expr, v);
272 return v;
276 /* Get the value handle of EXPR. This is the only correct way to get
277 the value handle for a "thing". If EXPR does not have a value
278 handle associated, it returns NULL_TREE.
279 NB: If EXPR is min_invariant, this function is *required* to return EXPR. */
281 tree
282 get_value_handle (tree expr)
285 if (is_gimple_min_invariant (expr))
286 return expr;
288 if (TREE_CODE (expr) == SSA_NAME)
289 return SSA_NAME_VALUE (expr);
290 else if (EXPR_P (expr) || DECL_P (expr) || TREE_CODE (expr) == TREE_LIST)
292 tree_ann_t ann = tree_ann (expr);
293 return ((ann) ? ann->common.value_handle : NULL_TREE);
295 else
296 gcc_unreachable ();
300 /* Initialize data structures used in value numbering. */
302 void
303 vn_init (void)
305 value_table = htab_create (511, val_expr_pair_hash,
306 val_expr_pair_expr_eq, free);
310 /* Delete data used for value numbering. */
312 void
313 vn_delete (void)
315 htab_delete (value_table);
316 value_table = NULL;