]>
Commit | Line | Data |
---|---|---|
33c94679 | 1 | /* Value Numbering routines for tree expressions. |
9dcd6f09 | 2 | Copyright (C) 2001, 2002, 2003, 2004, 2005, 2007 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 | |
9dcd6f09 | 10 | the Free Software Foundation; either version 3, or (at your option) |
33c94679 DN |
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 | |
9dcd6f09 NC |
19 | along with GCC; see the file COPYING3. If not see |
20 | <http://www.gnu.org/licenses/>. */ | |
33c94679 DN |
21 | |
22 | #include "config.h" | |
23 | #include "system.h" | |
24 | #include "coretypes.h" | |
25 | #include "tm.h" | |
26 | #include "ggc.h" | |
27 | #include "tree.h" | |
28 | #include "tree-flow.h" | |
29 | #include "hashtab.h" | |
30 | #include "langhooks.h" | |
31 | #include "tree-pass.h" | |
32 | #include "tree-dump.h" | |
33 | #include "diagnostic.h" | |
89fb70a3 | 34 | #include "tree-ssa-sccvn.h" |
33c94679 | 35 | |
89fb70a3 DB |
36 | /* Most of this is PRE specific. The real grunt work is done in |
37 | tree-ssa-sccvn.c. This is where the lookup and insertion | |
38 | functions, etc, can be found */ | |
33c94679 DN |
39 | |
40 | /* Create and return a new value handle node of type TYPE. */ | |
41 | ||
89fb70a3 | 42 | tree |
33c94679 DN |
43 | make_value_handle (tree type) |
44 | { | |
45 | static unsigned int id = 0; | |
46 | tree vh; | |
47 | ||
48 | vh = build0 (VALUE_HANDLE, type); | |
49 | VALUE_HANDLE_ID (vh) = id++; | |
50 | return vh; | |
51 | } | |
52 | ||
53 | ||
33c94679 | 54 | |
33c94679 DN |
55 | /* Compare two expressions E1 and E2 and return true if they are |
56 | equal. */ | |
57 | ||
58 | bool | |
59 | expressions_equal_p (tree e1, tree e2) | |
60 | { | |
61 | tree te1, te2; | |
070b797d | 62 | |
33c94679 DN |
63 | if (e1 == e2) |
64 | return true; | |
65 | ||
66 | te1 = TREE_TYPE (e1); | |
67 | te2 = TREE_TYPE (e2); | |
68 | ||
43da81be DB |
69 | if (TREE_CODE (e1) == TREE_LIST && TREE_CODE (e2) == TREE_LIST) |
70 | { | |
71 | tree lop1 = e1; | |
72 | tree lop2 = e2; | |
73 | for (lop1 = e1, lop2 = e2; | |
74 | lop1 || lop2; | |
75 | lop1 = TREE_CHAIN (lop1), lop2 = TREE_CHAIN (lop2)) | |
76 | { | |
77 | if (!lop1 || !lop2) | |
78 | return false; | |
79 | if (!expressions_equal_p (TREE_VALUE (lop1), TREE_VALUE (lop2))) | |
80 | return false; | |
81 | } | |
82 | return true; | |
83 | ||
84 | } | |
070b797d | 85 | else if (TREE_CODE (e1) == TREE_CODE (e2) |
f4088621 RG |
86 | && (te1 == te2 |
87 | || types_compatible_p (te1, te2)) | |
43da81be | 88 | && operand_equal_p (e1, e2, OEP_PURE_SAME)) |
33c94679 DN |
89 | return true; |
90 | ||
91 | return false; | |
92 | } | |
93 | ||
ea4b7848 | 94 | /* Set the value handle for expression E to value V. */ |
070b797d | 95 | |
89fb70a3 | 96 | void |
33c94679 DN |
97 | set_value_handle (tree e, tree v) |
98 | { | |
99 | if (TREE_CODE (e) == SSA_NAME) | |
100 | SSA_NAME_VALUE (e) = v; | |
b71b4522 | 101 | else if (EXPR_P (e) || DECL_P (e) || TREE_CODE (e) == TREE_LIST |
07beea0d | 102 | || GIMPLE_STMT_P (e) |
4038c495 | 103 | || TREE_CODE (e) == CONSTRUCTOR) |
93c094b5 | 104 | get_tree_common_ann (e)->value_handle = v; |
33c94679 | 105 | else |
1e128c5f GB |
106 | /* Do nothing. Constants are their own value handles. */ |
107 | gcc_assert (is_gimple_min_invariant (e)); | |
33c94679 DN |
108 | } |
109 | ||
89fb70a3 DB |
110 | /* A comparison function for use in qsort to compare vuses. Simply |
111 | subtracts version numbers. */ | |
c90186eb | 112 | |
89fb70a3 DB |
113 | static int |
114 | vuses_compare (const void *pa, const void *pb) | |
115 | { | |
116 | const tree vusea = *((const tree *)pa); | |
117 | const tree vuseb = *((const tree *)pb); | |
118 | int sn = SSA_NAME_VERSION (vusea) - SSA_NAME_VERSION (vuseb); | |
c90186eb | 119 | |
89fb70a3 DB |
120 | return sn; |
121 | } | |
c90186eb | 122 | |
89fb70a3 DB |
123 | /* Print out the "Created value <x> for <Y>" statement to the |
124 | dump_file. | |
125 | This is factored because both versions of lookup use it, and it | |
126 | obscures the real work going on in those functions. */ | |
c90186eb | 127 | |
89fb70a3 DB |
128 | static void |
129 | print_creation_to_file (tree v, tree expr, VEC (tree, gc) *vuses) | |
c90186eb | 130 | { |
89fb70a3 DB |
131 | fprintf (dump_file, "Created value "); |
132 | print_generic_expr (dump_file, v, dump_flags); | |
133 | fprintf (dump_file, " for "); | |
134 | print_generic_expr (dump_file, expr, dump_flags); | |
070b797d | 135 | |
89fb70a3 DB |
136 | if (vuses && VEC_length (tree, vuses) != 0) |
137 | { | |
138 | size_t i; | |
139 | tree vuse; | |
070b797d | 140 | |
89fb70a3 DB |
141 | fprintf (dump_file, " vuses: ("); |
142 | for (i = 0; VEC_iterate (tree, vuses, i, vuse); i++) | |
143 | { | |
144 | print_generic_expr (dump_file, vuse, dump_flags); | |
145 | if (VEC_length (tree, vuses) - 1 != i) | |
146 | fprintf (dump_file, ","); | |
147 | } | |
148 | fprintf (dump_file, ")"); | |
070b797d | 149 | } |
89fb70a3 DB |
150 | fprintf (dump_file, "\n"); |
151 | } | |
c90186eb | 152 | |
c90186eb | 153 | |
89fb70a3 DB |
154 | /* Sort the VUSE array so that we can do equality comparisons |
155 | quicker on two vuse vecs. */ | |
c90186eb | 156 | |
070b797d | 157 | void |
89fb70a3 DB |
158 | sort_vuses (VEC (tree,gc) *vuses) |
159 | { | |
160 | if (VEC_length (tree, vuses) > 1) | |
161 | qsort (VEC_address (tree, vuses), | |
162 | VEC_length (tree, vuses), | |
163 | sizeof (tree), | |
164 | vuses_compare); | |
165 | } | |
c90186eb | 166 | |
89fb70a3 DB |
167 | /* Sort the VUSE array so that we can do equality comparisons |
168 | quicker on two vuse vecs. */ | |
c90186eb | 169 | |
070b797d | 170 | void |
89fb70a3 DB |
171 | sort_vuses_heap (VEC (tree,heap) *vuses) |
172 | { | |
173 | if (VEC_length (tree, vuses) > 1) | |
174 | qsort (VEC_address (tree, vuses), | |
175 | VEC_length (tree, vuses), | |
176 | sizeof (tree), | |
177 | vuses_compare); | |
c90186eb | 178 | } |
c90186eb DB |
179 | /* Insert EXPR into VALUE_TABLE with value VAL, and add expression |
180 | EXPR to the value set for value VAL. */ | |
181 | ||
182 | void | |
183 | vn_add (tree expr, tree val) | |
184 | { | |
89fb70a3 DB |
185 | switch (TREE_CODE_CLASS (TREE_CODE (expr))) |
186 | { | |
187 | case tcc_comparison: | |
188 | case tcc_binary: | |
189 | vn_binary_op_insert (expr, val); | |
190 | break; | |
191 | case tcc_unary: | |
192 | vn_unary_op_insert (expr, val); | |
193 | break; | |
194 | /* In the case of array-refs of constants, for example, we can | |
195 | end up with no vuses. */ | |
196 | case tcc_reference: | |
197 | vn_reference_insert (expr, val, NULL); | |
198 | break; | |
199 | /* The *only* time CALL_EXPR should appear here is | |
200 | when it has no vuses. */ | |
201 | case tcc_vl_exp: | |
202 | case tcc_exceptional: | |
203 | case tcc_expression: | |
204 | case tcc_declaration: | |
205 | if (TREE_CODE (expr) == CALL_EXPR || DECL_P (expr)) | |
206 | { | |
207 | vn_reference_insert (expr, val, NULL); | |
208 | break; | |
209 | } | |
210 | else if (TREE_CODE (expr) == SSA_NAME) | |
211 | { | |
212 | SSA_NAME_VALUE (expr) = val; | |
213 | break; | |
214 | } | |
215 | else if (TREE_CODE (expr) == ADDR_EXPR) | |
216 | { | |
217 | vn_unary_op_insert (expr, val); | |
218 | break; | |
219 | } | |
220 | /* FALLTHROUGH */ | |
221 | default: | |
222 | gcc_unreachable (); | |
223 | } | |
224 | set_value_handle (expr, val); | |
225 | if (TREE_CODE (val) == VALUE_HANDLE) | |
226 | add_to_value (val, expr); | |
c90186eb | 227 | } |
33c94679 | 228 | |
89fb70a3 DB |
229 | /* Insert EXPR into the value numbering tables. with value VAL, and |
230 | add expression EXPR to the value set for value VAL. VUSES | |
231 | represents the virtual use operands associated with EXPR. It is | |
232 | used when computing a hash value for EXPR. */ | |
33c94679 DN |
233 | |
234 | void | |
c90186eb | 235 | vn_add_with_vuses (tree expr, tree val, VEC (tree, gc) *vuses) |
33c94679 | 236 | { |
89fb70a3 DB |
237 | if (!vuses) |
238 | { | |
239 | vn_add (expr, val); | |
240 | return; | |
241 | } | |
242 | vn_reference_insert (expr, val, vuses); | |
33c94679 | 243 | |
ff2ad0f7 | 244 | set_value_handle (expr, val); |
c90186eb DB |
245 | if (TREE_CODE (val) == VALUE_HANDLE) |
246 | add_to_value (val, expr); | |
33c94679 DN |
247 | } |
248 | ||
249 | ||
89fb70a3 DB |
250 | /* Lookup EXPR in the value numbering tables and return the result, if |
251 | we have one. */ | |
252 | ||
253 | tree | |
254 | vn_lookup (tree expr) | |
255 | { | |
256 | /* Constants are their own value. */ | |
257 | if (is_gimple_min_invariant (expr) || TREE_CODE (expr) == FIELD_DECL) | |
258 | return expr; | |
259 | ||
260 | switch (TREE_CODE_CLASS (TREE_CODE (expr))) | |
261 | { | |
262 | case tcc_comparison: | |
263 | case tcc_binary: | |
264 | return vn_binary_op_lookup (expr); | |
265 | case tcc_unary: | |
266 | return vn_unary_op_lookup (expr); | |
267 | break; | |
268 | /* In the case of array-refs of constants, for example, we can | |
269 | end up with no vuses. */ | |
270 | case tcc_reference: | |
271 | return vn_reference_lookup (expr, NULL); | |
272 | break; | |
273 | /* It is possible to have CALL_EXPR with no vuses for things | |
274 | like "cos", and these will fall into vn_lookup. */ | |
275 | case tcc_vl_exp: | |
276 | case tcc_exceptional: | |
277 | case tcc_expression: | |
278 | case tcc_declaration: | |
279 | if (TREE_CODE (expr) == CALL_EXPR || DECL_P (expr)) | |
280 | return vn_reference_lookup (expr, NULL); | |
281 | else if (TREE_CODE (expr) == SSA_NAME) | |
070b797d | 282 | return SSA_NAME_VALUE (expr); |
89fb70a3 DB |
283 | else if (TREE_CODE (expr) == ADDR_EXPR) |
284 | return vn_unary_op_lookup (expr); | |
285 | /* FALLTHROUGH */ | |
286 | default: | |
287 | gcc_unreachable (); | |
288 | } | |
289 | return NULL; | |
290 | } | |
291 | ||
292 | /* Search in the value numbering tables for an existing instance of | |
293 | expression EXPR, and return its value, or NULL if none has been set. STMT | |
070b797d | 294 | represents the stmt associated with EXPR. It is used when computing the |
89fb70a3 | 295 | hash value for EXPR for reference operations. */ |
33c94679 DN |
296 | |
297 | tree | |
89fb70a3 | 298 | vn_lookup_with_stmt (tree expr, tree stmt) |
c90186eb | 299 | { |
89fb70a3 DB |
300 | if (stmt == NULL) |
301 | return vn_lookup (expr); | |
302 | ||
303 | /* Constants are their own value. */ | |
304 | if (is_gimple_min_invariant (expr) || TREE_CODE (expr) == FIELD_DECL) | |
305 | return expr; | |
306 | ||
c90186eb DB |
307 | return vn_lookup_with_vuses (expr, shared_vuses_from_stmt (stmt)); |
308 | } | |
309 | ||
310 | /* Search in VALUE_TABLE for an existing instance of expression EXPR, | |
311 | and return its value, or NULL if none has been set. VUSES is the | |
312 | list of virtual use operands associated with EXPR. It is used when | |
313 | computing the hash value for EXPR. */ | |
314 | ||
315 | tree | |
316 | vn_lookup_with_vuses (tree expr, VEC (tree, gc) *vuses) | |
33c94679 | 317 | { |
89fb70a3 DB |
318 | if (!vuses || !VEC_length (tree, vuses)) |
319 | return vn_lookup (expr); | |
33c94679 | 320 | |
89fb70a3 | 321 | if (is_gimple_min_invariant (expr) || TREE_CODE (expr) == FIELD_DECL) |
ff2ad0f7 | 322 | return expr; |
bddeccfe | 323 | |
89fb70a3 | 324 | return vn_reference_lookup (expr, vuses); |
33c94679 DN |
325 | } |
326 | ||
89fb70a3 | 327 | static tree |
c5830edf | 328 | create_value_handle_for_expr (tree expr, VEC(tree, gc) *vuses) |
c90186eb | 329 | { |
89fb70a3 | 330 | tree v; |
070b797d | 331 | |
89fb70a3 | 332 | v = make_value_handle (TREE_TYPE (expr)); |
070b797d | 333 | |
89fb70a3 DB |
334 | if (dump_file && (dump_flags & TDF_DETAILS)) |
335 | print_creation_to_file (v, expr, vuses); | |
89fb70a3 | 336 | return v; |
c90186eb DB |
337 | } |
338 | ||
89fb70a3 DB |
339 | /* Like vn_lookup, but creates a new value for the operation if one |
340 | does not exist. */ | |
c90186eb | 341 | |
89fb70a3 DB |
342 | tree |
343 | vn_lookup_or_add (tree expr) | |
c90186eb | 344 | { |
89fb70a3 | 345 | tree v = vn_lookup (expr); |
070b797d | 346 | |
89fb70a3 | 347 | if (v == NULL_TREE) |
c90186eb | 348 | { |
89fb70a3 DB |
349 | v = create_value_handle_for_expr (expr, NULL); |
350 | vn_add (expr, v); | |
351 | } | |
352 | else | |
353 | set_value_handle (expr, v); | |
354 | ||
355 | return v; | |
c90186eb DB |
356 | } |
357 | ||
89fb70a3 DB |
358 | /* Like vn_lookup, but handles reference operations as well by using |
359 | STMT to get the set of vuses. */ | |
33c94679 DN |
360 | |
361 | tree | |
89fb70a3 | 362 | vn_lookup_or_add_with_stmt (tree expr, tree stmt) |
33c94679 | 363 | { |
89fb70a3 DB |
364 | tree v; |
365 | if (!stmt) | |
366 | return vn_lookup_or_add (expr); | |
367 | ||
368 | v = vn_lookup_with_stmt (expr, stmt); | |
ff2ad0f7 | 369 | if (v == NULL_TREE) |
33c94679 | 370 | { |
89fb70a3 DB |
371 | VEC (tree, gc) *vuses = copy_vuses_from_stmt (stmt); |
372 | v = create_value_handle_for_expr (expr, vuses); | |
c90186eb | 373 | vn_add_with_vuses (expr, v, vuses); |
33c94679 | 374 | } |
89fb70a3 DB |
375 | else |
376 | set_value_handle (expr, v); | |
33c94679 | 377 | |
ff2ad0f7 | 378 | return v; |
33c94679 DN |
379 | } |
380 | ||
c90186eb DB |
381 | /* Like vn_lookup, but creates a new value for expression EXPR, if |
382 | EXPR doesn't already have a value. Return the existing/created | |
383 | value for EXPR. STMT represents the stmt associated with EXPR. It is used | |
384 | when computing the hash value for EXPR. */ | |
385 | ||
386 | tree | |
387 | vn_lookup_or_add_with_vuses (tree expr, VEC (tree, gc) *vuses) | |
388 | { | |
89fb70a3 | 389 | tree v; |
070b797d | 390 | |
89fb70a3 DB |
391 | if (!vuses || VEC_length (tree, vuses) == 0) |
392 | return vn_lookup_or_add (expr); | |
070b797d | 393 | |
89fb70a3 | 394 | v = vn_lookup_with_vuses (expr, vuses); |
c90186eb DB |
395 | if (v == NULL_TREE) |
396 | { | |
89fb70a3 | 397 | v = create_value_handle_for_expr (expr, vuses); |
c90186eb DB |
398 | vn_add_with_vuses (expr, v, vuses); |
399 | } | |
89fb70a3 DB |
400 | else |
401 | set_value_handle (expr, v); | |
c90186eb DB |
402 | |
403 | return v; | |
404 | } | |
405 |