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