]>
Commit | Line | Data |
---|---|---|
33c94679 | 1 | /* Value Numbering routines for tree expressions. |
c8d3e15a | 2 | Copyright (C) 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc. |
33c94679 DN |
3 | Contributed by Daniel Berlin <dan@dberlin.org>, Steven Bosscher |
4 | <stevenb@suse.de> and Diego Novillo <dnovillo@redhat.com> | |
5 | ||
6 | This file is part of GCC. | |
7 | ||
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. | |
12 | ||
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. | |
17 | ||
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, 59 Temple Place - Suite 330, | |
21 | Boston, MA 02111-1307, 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. */ | |
37 | static 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. */ | |
43 | typedef struct val_expr_pair_d | |
44 | { | |
ff2ad0f7 DN |
45 | /* Value handle. */ |
46 | tree v; | |
47 | ||
48 | /* Associated expression. */ | |
49 | tree e; | |
50 | ||
f47c96aa AM |
51 | /* for comparing Virtual uses in E. */ |
52 | tree stmt; | |
ff2ad0f7 DN |
53 | |
54 | /* E's hash value. */ | |
33c94679 DN |
55 | hashval_t hashcode; |
56 | } *val_expr_pair_t; | |
57 | ||
58 | static void set_value_handle (tree e, tree v); | |
59 | ||
60 | ||
61 | /* Create and return a new value handle node of type TYPE. */ | |
62 | ||
63 | static tree | |
64 | make_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 | ||
ff2ad0f7 DN |
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 | ||
f47c96aa | 82 | STMT is the stmt associated with EXPR for comparing virtual operands. */ |
33c94679 DN |
83 | |
84 | hashval_t | |
f47c96aa | 85 | vn_compute (tree expr, hashval_t val, tree stmt) |
33c94679 | 86 | { |
f47c96aa AM |
87 | ssa_op_iter iter; |
88 | tree vuse; | |
ff2ad0f7 | 89 | |
ff2ad0f7 DN |
90 | /* EXPR must not be a statement. We are only interested in value |
91 | numbering expressions on the RHS of assignments. */ | |
1e128c5f GB |
92 | gcc_assert (expr); |
93 | gcc_assert (!expr->common.ann | |
94 | || expr->common.ann->common.type != STMT_ANN); | |
ff2ad0f7 | 95 | |
33c94679 | 96 | val = iterative_hash_expr (expr, val); |
ff2ad0f7 DN |
97 | |
98 | /* If the expression has virtual uses, incorporate them into the | |
99 | hash value computed for EXPR. */ | |
f47c96aa AM |
100 | if (stmt) |
101 | FOR_EACH_SSA_TREE_OPERAND (vuse, stmt, iter, SSA_OP_VUSE) | |
102 | val = iterative_hash_expr (vuse, val); | |
ff2ad0f7 | 103 | |
33c94679 DN |
104 | return val; |
105 | } | |
106 | ||
107 | ||
108 | /* Compare two expressions E1 and E2 and return true if they are | |
109 | equal. */ | |
110 | ||
111 | bool | |
112 | expressions_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 | ||
43da81be DB |
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)) | |
33c94679 DN |
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 | ||
151 | static hashval_t | |
152 | val_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 | ||
163 | static int | |
164 | val_expr_pair_expr_eq (const void *p1, const void *p2) | |
165 | { | |
f47c96aa | 166 | bool ret; |
33c94679 DN |
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 | ||
b2ddaebb GK |
170 | if (! expressions_equal_p (ve1->e, ve2->e)) |
171 | return false; | |
172 | ||
f47c96aa AM |
173 | ret = compare_ssa_operands_equal (ve1->stmt, ve2->stmt, SSA_OP_VUSE); |
174 | return ret; | |
33c94679 DN |
175 | } |
176 | ||
177 | ||
ea4b7848 | 178 | /* Set the value handle for expression E to value V. */ |
33c94679 DN |
179 | |
180 | static void | |
181 | set_value_handle (tree e, tree v) | |
182 | { | |
183 | if (TREE_CODE (e) == SSA_NAME) | |
184 | SSA_NAME_VALUE (e) = v; | |
43da81be | 185 | else if (EXPR_P (e) || DECL_P (e) || TREE_CODE (e) == TREE_LIST) |
33c94679 | 186 | get_tree_ann (e)->common.value_handle = v; |
33c94679 | 187 | else |
1e128c5f GB |
188 | /* Do nothing. Constants are their own value handles. */ |
189 | gcc_assert (is_gimple_min_invariant (e)); | |
33c94679 DN |
190 | } |
191 | ||
192 | ||
ff2ad0f7 | 193 | /* Insert EXPR into VALUE_TABLE with value VAL, and add expression |
395bda42 | 194 | EXPR to the value set for value VAL. STMT represents the stmt |
f47c96aa | 195 | associated with EXPR. It is used when computing a hash value for EXPR. */ |
33c94679 DN |
196 | |
197 | void | |
f47c96aa | 198 | vn_add (tree expr, tree val, tree stmt) |
33c94679 DN |
199 | { |
200 | void **slot; | |
ff2ad0f7 DN |
201 | val_expr_pair_t new_pair; |
202 | ||
203 | new_pair = xmalloc (sizeof (struct val_expr_pair_d)); | |
204 | new_pair->e = expr; | |
205 | new_pair->v = val; | |
f47c96aa AM |
206 | new_pair->stmt = stmt; |
207 | new_pair->hashcode = vn_compute (expr, 0, stmt); | |
33c94679 DN |
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; | |
33c94679 | 213 | |
ff2ad0f7 DN |
214 | set_value_handle (expr, val); |
215 | add_to_value (val, expr); | |
33c94679 DN |
216 | } |
217 | ||
218 | ||
ff2ad0f7 | 219 | /* Search in VALUE_TABLE for an existing instance of expression EXPR, |
f47c96aa | 220 | and return its value, or NULL if none has been set. STMT |
395bda42 | 221 | represents the stmt associated with EXPR. It is used when computing the |
f47c96aa | 222 | hash value for EXPR. */ |
33c94679 DN |
223 | |
224 | tree | |
f47c96aa | 225 | vn_lookup (tree expr, tree stmt) |
33c94679 DN |
226 | { |
227 | void **slot; | |
ff2ad0f7 | 228 | struct val_expr_pair_d vep = {NULL, NULL, NULL, 0}; |
33c94679 | 229 | |
bddeccfe DN |
230 | /* Constants are their own value. */ |
231 | if (is_gimple_min_invariant (expr)) | |
ff2ad0f7 | 232 | return expr; |
bddeccfe | 233 | |
ff2ad0f7 | 234 | vep.e = expr; |
f47c96aa AM |
235 | vep.stmt = stmt; |
236 | vep.hashcode = vn_compute (expr, 0, stmt); | |
33c94679 DN |
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; | |
242 | } | |
243 | ||
244 | ||
ff2ad0f7 DN |
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 | |
395bda42 | 247 | value for EXPR. STMT represents the stmt associated with EXPR. It is used |
f47c96aa | 248 | when computing the hash value for EXPR. */ |
33c94679 DN |
249 | |
250 | tree | |
f47c96aa | 251 | vn_lookup_or_add (tree expr, tree stmt) |
33c94679 | 252 | { |
f47c96aa | 253 | tree v = vn_lookup (expr, stmt); |
ff2ad0f7 | 254 | if (v == NULL_TREE) |
33c94679 | 255 | { |
ff2ad0f7 | 256 | v = make_value_handle (TREE_TYPE (expr)); |
33c94679 DN |
257 | |
258 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
259 | { | |
260 | fprintf (dump_file, "Created value "); | |
261 | print_generic_expr (dump_file, v, dump_flags); | |
262 | fprintf (dump_file, " for "); | |
ff2ad0f7 | 263 | print_generic_expr (dump_file, expr, dump_flags); |
33c94679 DN |
264 | fprintf (dump_file, "\n"); |
265 | } | |
266 | ||
f47c96aa | 267 | vn_add (expr, v, stmt); |
33c94679 DN |
268 | } |
269 | ||
ff2ad0f7 | 270 | set_value_handle (expr, v); |
33c94679 | 271 | |
ff2ad0f7 | 272 | return v; |
33c94679 DN |
273 | } |
274 | ||
275 | ||
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 | |
eace8c18 DB |
278 | handle associated, it returns NULL_TREE. |
279 | NB: If EXPR is min_invariant, this function is *required* to return EXPR. */ | |
33c94679 DN |
280 | |
281 | tree | |
282 | get_value_handle (tree expr) | |
283 | { | |
eace8c18 DB |
284 | |
285 | if (is_gimple_min_invariant (expr)) | |
286 | return expr; | |
287 | ||
33c94679 DN |
288 | if (TREE_CODE (expr) == SSA_NAME) |
289 | return SSA_NAME_VALUE (expr); | |
43da81be | 290 | else if (EXPR_P (expr) || DECL_P (expr) || TREE_CODE (expr) == TREE_LIST) |
33c94679 DN |
291 | { |
292 | tree_ann_t ann = tree_ann (expr); | |
293 | return ((ann) ? ann->common.value_handle : NULL_TREE); | |
294 | } | |
1e128c5f | 295 | else |
eace8c18 | 296 | gcc_unreachable (); |
33c94679 DN |
297 | } |
298 | ||
299 | ||
300 | /* Initialize data structures used in value numbering. */ | |
301 | ||
302 | void | |
303 | vn_init (void) | |
304 | { | |
305 | value_table = htab_create (511, val_expr_pair_hash, | |
306 | val_expr_pair_expr_eq, free); | |
307 | } | |
308 | ||
309 | ||
310 | /* Delete data used for value numbering. */ | |
311 | ||
312 | void | |
313 | vn_delete (void) | |
314 | { | |
315 | htab_delete (value_table); | |
316 | value_table = NULL; | |
317 | } |