]>
Commit | Line | Data |
---|---|---|
6de9cd9a | 1 | /* SSA-PRE for trees. |
ad616de1 | 2 | Copyright (C) 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc. |
7e6eb623 DB |
3 | Contributed by Daniel Berlin <dan@dberlin.org> and Steven Bosscher |
4 | <stevenb@suse.de> | |
6de9cd9a DN |
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 | |
366ccddb KC |
20 | the Free Software Foundation, 51 Franklin Street, Fifth Floor, |
21 | Boston, MA 02110-1301, USA. */ | |
33c94679 | 22 | |
6de9cd9a DN |
23 | #include "config.h" |
24 | #include "system.h" | |
25 | #include "coretypes.h" | |
26 | #include "tm.h" | |
6de9cd9a DN |
27 | #include "ggc.h" |
28 | #include "tree.h" | |
6de9cd9a DN |
29 | #include "basic-block.h" |
30 | #include "diagnostic.h" | |
31 | #include "tree-inline.h" | |
32 | #include "tree-flow.h" | |
eadf906f | 33 | #include "tree-gimple.h" |
6de9cd9a DN |
34 | #include "tree-dump.h" |
35 | #include "timevar.h" | |
36 | #include "fibheap.h" | |
37 | #include "hashtab.h" | |
38 | #include "tree-iterator.h" | |
39 | #include "real.h" | |
40 | #include "alloc-pool.h" | |
41 | #include "tree-pass.h" | |
42 | #include "flags.h" | |
7e6eb623 DB |
43 | #include "bitmap.h" |
44 | #include "langhooks.h" | |
0fc6c492 | 45 | #include "cfgloop.h" |
33c94679 | 46 | |
7e6eb623 | 47 | /* TODO: |
6de9cd9a | 48 | |
bdee7684 | 49 | 1. Avail sets can be shared by making an avail_find_leader that |
7e6eb623 DB |
50 | walks up the dominator tree and looks in those avail sets. |
51 | This might affect code optimality, it's unclear right now. | |
c90186eb | 52 | 2. Strength reduction can be performed by anticipating expressions |
7e6eb623 | 53 | we can repair later on. |
c90186eb | 54 | 3. We can do back-substitution or smarter value numbering to catch |
0fc6c492 | 55 | commutative expressions split up over multiple statements. |
7e6eb623 DB |
56 | */ |
57 | ||
58 | /* For ease of terminology, "expression node" in the below refers to | |
59 | every expression node but MODIFY_EXPR, because MODIFY_EXPR's represent | |
60 | the actual statement containing the expressions we care about, and | |
61 | we cache the value number by putting it in the expression. */ | |
62 | ||
63 | /* Basic algorithm | |
6de9cd9a | 64 | |
56db793a DB |
65 | First we walk the statements to generate the AVAIL sets, the |
66 | EXP_GEN sets, and the tmp_gen sets. EXP_GEN sets represent the | |
67 | generation of values/expressions by a given block. We use them | |
68 | when computing the ANTIC sets. The AVAIL sets consist of | |
69 | SSA_NAME's that represent values, so we know what values are | |
70 | available in what blocks. AVAIL is a forward dataflow problem. In | |
71 | SSA, values are never killed, so we don't need a kill set, or a | |
72 | fixpoint iteration, in order to calculate the AVAIL sets. In | |
73 | traditional parlance, AVAIL sets tell us the downsafety of the | |
7e6eb623 | 74 | expressions/values. |
6de9cd9a | 75 | |
56db793a DB |
76 | Next, we generate the ANTIC sets. These sets represent the |
77 | anticipatable expressions. ANTIC is a backwards dataflow | |
78 | problem.An expression is anticipatable in a given block if it could | |
79 | be generated in that block. This means that if we had to perform | |
80 | an insertion in that block, of the value of that expression, we | |
81 | could. Calculating the ANTIC sets requires phi translation of | |
82 | expressions, because the flow goes backwards through phis. We must | |
83 | iterate to a fixpoint of the ANTIC sets, because we have a kill | |
84 | set. Even in SSA form, values are not live over the entire | |
85 | function, only from their definition point onwards. So we have to | |
86 | remove values from the ANTIC set once we go past the definition | |
87 | point of the leaders that make them up. | |
88 | compute_antic/compute_antic_aux performs this computation. | |
7e6eb623 DB |
89 | |
90 | Third, we perform insertions to make partially redundant | |
91 | expressions fully redundant. | |
92 | ||
93 | An expression is partially redundant (excluding partial | |
94 | anticipation) if: | |
95 | ||
96 | 1. It is AVAIL in some, but not all, of the predecessors of a | |
97 | given block. | |
98 | 2. It is ANTIC in all the predecessors. | |
99 | ||
100 | In order to make it fully redundant, we insert the expression into | |
101 | the predecessors where it is not available, but is ANTIC. | |
102 | insert/insert_aux performs this insertion. | |
103 | ||
104 | Fourth, we eliminate fully redundant expressions. | |
105 | This is a simple statement walk that replaces redundant | |
106 | calculations with the now available values. */ | |
107 | ||
108 | /* Representations of value numbers: | |
109 | ||
110 | Value numbers are represented using the "value handle" approach. | |
111 | This means that each SSA_NAME (and for other reasons to be | |
56db793a DB |
112 | disclosed in a moment, expression nodes) has a value handle that |
113 | can be retrieved through get_value_handle. This value handle, *is* | |
114 | the value number of the SSA_NAME. You can pointer compare the | |
115 | value handles for equivalence purposes. | |
7e6eb623 DB |
116 | |
117 | For debugging reasons, the value handle is internally more than | |
118 | just a number, it is a VAR_DECL named "value.x", where x is a | |
119 | unique number for each value number in use. This allows | |
120 | expressions with SSA_NAMES replaced by value handles to still be | |
121 | pretty printed in a sane way. They simply print as "value.3 * | |
122 | value.5", etc. | |
123 | ||
124 | Expression nodes have value handles associated with them as a | |
125 | cache. Otherwise, we'd have to look them up again in the hash | |
126 | table This makes significant difference (factor of two or more) on | |
56db793a DB |
127 | some test cases. They can be thrown away after the pass is |
128 | finished. */ | |
7e6eb623 DB |
129 | |
130 | /* Representation of expressions on value numbers: | |
131 | ||
132 | In some portions of this code, you will notice we allocate "fake" | |
133 | analogues to the expression we are value numbering, and replace the | |
134 | operands with the values of the expression. Since we work on | |
135 | values, and not just names, we canonicalize expressions to value | |
136 | expressions for use in the ANTIC sets, the EXP_GEN set, etc. | |
137 | ||
138 | This is theoretically unnecessary, it just saves a bunch of | |
139 | repeated get_value_handle and find_leader calls in the remainder of | |
140 | the code, trading off temporary memory usage for speed. The tree | |
141 | nodes aren't actually creating more garbage, since they are | |
142 | allocated in a special pools which are thrown away at the end of | |
143 | this pass. | |
144 | ||
145 | All of this also means that if you print the EXP_GEN or ANTIC sets, | |
146 | you will see "value.5 + value.7" in the set, instead of "a_55 + | |
147 | b_66" or something. The only thing that actually cares about | |
148 | seeing the value leaders is phi translation, and it needs to be | |
149 | able to find the leader for a value in an arbitrary block, so this | |
150 | "value expression" form is perfect for it (otherwise you'd do | |
151 | get_value_handle->find_leader->translate->get_value_handle->find_leader).*/ | |
152 | ||
153 | ||
154 | /* Representation of sets: | |
155 | ||
bdee7684 DB |
156 | There are currently two types of sets used, hopefully to be unified soon. |
157 | The AVAIL sets do not need to be sorted in any particular order, | |
158 | and thus, are simply represented as two bitmaps, one that keeps | |
159 | track of values present in the set, and one that keeps track of | |
160 | expressions present in the set. | |
161 | ||
162 | The other sets are represented as doubly linked lists kept in topological | |
7e6eb623 | 163 | order, with an optional supporting bitmap of values present in the |
56db793a DB |
164 | set. The sets represent values, and the elements can be values or |
165 | expressions. The elements can appear in different sets, but each | |
166 | element can only appear once in each set. | |
7e6eb623 DB |
167 | |
168 | Since each node in the set represents a value, we also want to be | |
169 | able to map expression, set pairs to something that tells us | |
170 | whether the value is present is a set. We use a per-set bitmap for | |
171 | that. The value handles also point to a linked list of the | |
172 | expressions they represent via a tree annotation. This is mainly | |
173 | useful only for debugging, since we don't do identity lookups. */ | |
174 | ||
175 | ||
81def1b7 DB |
176 | static bool in_fre = false; |
177 | ||
7e6eb623 | 178 | /* A value set element. Basically a single linked list of |
56db793a | 179 | expressions/values. */ |
7e6eb623 | 180 | typedef struct value_set_node |
6de9cd9a | 181 | { |
ca072a31 | 182 | /* An expression. */ |
7e6eb623 | 183 | tree expr; |
ca072a31 DB |
184 | |
185 | /* A pointer to the next element of the value set. */ | |
7e6eb623 DB |
186 | struct value_set_node *next; |
187 | } *value_set_node_t; | |
6de9cd9a | 188 | |
6de9cd9a | 189 | |
ca072a31 DB |
190 | /* A value set. This is a singly linked list of value_set_node |
191 | elements with a possible bitmap that tells us what values exist in | |
192 | the set. This set must be kept in topologically sorted order. */ | |
7e6eb623 DB |
193 | typedef struct value_set |
194 | { | |
ca072a31 DB |
195 | /* The head of the list. Used for iterating over the list in |
196 | order. */ | |
7e6eb623 | 197 | value_set_node_t head; |
ca072a31 DB |
198 | |
199 | /* The tail of the list. Used for tail insertions, which are | |
200 | necessary to keep the set in topologically sorted order because | |
201 | of how the set is built. */ | |
7e6eb623 | 202 | value_set_node_t tail; |
ca072a31 DB |
203 | |
204 | /* The length of the list. */ | |
7e6eb623 | 205 | size_t length; |
ca072a31 DB |
206 | |
207 | /* True if the set is indexed, which means it contains a backing | |
208 | bitmap for quick determination of whether certain values exist in the | |
209 | set. */ | |
7e6eb623 | 210 | bool indexed; |
ca072a31 DB |
211 | |
212 | /* The bitmap of values that exist in the set. May be NULL in an | |
213 | empty or non-indexed set. */ | |
7e6eb623 | 214 | bitmap values; |
6de9cd9a | 215 | |
7e6eb623 | 216 | } *value_set_t; |
6de9cd9a | 217 | |
bdee7684 DB |
218 | |
219 | /* An unordered bitmap set. One bitmap tracks values, the other, | |
8c27b7d4 | 220 | expressions. */ |
bdee7684 DB |
221 | typedef struct bitmap_set |
222 | { | |
223 | bitmap expressions; | |
224 | bitmap values; | |
225 | } *bitmap_set_t; | |
226 | ||
6b416da1 | 227 | /* Sets that we need to keep track of. */ |
7e6eb623 | 228 | typedef struct bb_value_sets |
6de9cd9a | 229 | { |
ca072a31 DB |
230 | /* The EXP_GEN set, which represents expressions/values generated in |
231 | a basic block. */ | |
7e6eb623 | 232 | value_set_t exp_gen; |
ca072a31 DB |
233 | |
234 | /* The PHI_GEN set, which represents PHI results generated in a | |
235 | basic block. */ | |
6b416da1 | 236 | bitmap_set_t phi_gen; |
ca072a31 | 237 | |
f6fe65dc | 238 | /* The TMP_GEN set, which represents results/temporaries generated |
ca072a31 | 239 | in a basic block. IE the LHS of an expression. */ |
6b416da1 | 240 | bitmap_set_t tmp_gen; |
ca072a31 DB |
241 | |
242 | /* The AVAIL_OUT set, which represents which values are available in | |
243 | a given basic block. */ | |
bdee7684 | 244 | bitmap_set_t avail_out; |
ca072a31 | 245 | |
c90186eb | 246 | /* The ANTIC_IN set, which represents which values are anticipatable |
ca072a31 | 247 | in a given basic block. */ |
7e6eb623 | 248 | value_set_t antic_in; |
ca072a31 DB |
249 | |
250 | /* The NEW_SETS set, which is used during insertion to augment the | |
251 | AVAIL_OUT set of blocks with the new insertions performed during | |
252 | the current iteration. */ | |
6b416da1 | 253 | bitmap_set_t new_sets; |
c90186eb DB |
254 | |
255 | /* The RVUSE sets, which are used during ANTIC computation to ensure | |
256 | that we don't mark loads ANTIC once they have died. */ | |
257 | bitmap rvuse_in; | |
258 | bitmap rvuse_out; | |
259 | bitmap rvuse_gen; | |
260 | bitmap rvuse_kill; | |
7e6eb623 DB |
261 | } *bb_value_sets_t; |
262 | ||
263 | #define EXP_GEN(BB) ((bb_value_sets_t) ((BB)->aux))->exp_gen | |
264 | #define PHI_GEN(BB) ((bb_value_sets_t) ((BB)->aux))->phi_gen | |
265 | #define TMP_GEN(BB) ((bb_value_sets_t) ((BB)->aux))->tmp_gen | |
266 | #define AVAIL_OUT(BB) ((bb_value_sets_t) ((BB)->aux))->avail_out | |
267 | #define ANTIC_IN(BB) ((bb_value_sets_t) ((BB)->aux))->antic_in | |
c90186eb DB |
268 | #define RVUSE_IN(BB) ((bb_value_sets_t) ((BB)->aux))->rvuse_in |
269 | #define RVUSE_GEN(BB) ((bb_value_sets_t) ((BB)->aux))->rvuse_gen | |
270 | #define RVUSE_KILL(BB) ((bb_value_sets_t) ((BB)->aux))->rvuse_kill | |
271 | #define RVUSE_OUT(BB) ((bb_value_sets_t) ((BB)->aux))->rvuse_out | |
7e6eb623 | 272 | #define NEW_SETS(BB) ((bb_value_sets_t) ((BB)->aux))->new_sets |
6de9cd9a | 273 | |
ca072a31 DB |
274 | /* This structure is used to keep track of statistics on what |
275 | optimization PRE was able to perform. */ | |
7e6eb623 | 276 | static struct |
6de9cd9a | 277 | { |
ca072a31 | 278 | /* The number of RHS computations eliminated by PRE. */ |
7e6eb623 | 279 | int eliminations; |
ca072a31 DB |
280 | |
281 | /* The number of new expressions/temporaries generated by PRE. */ | |
7e6eb623 | 282 | int insertions; |
ca072a31 DB |
283 | |
284 | /* The number of new PHI nodes added by PRE. */ | |
7e6eb623 | 285 | int phis; |
0fc6c492 DB |
286 | |
287 | /* The number of values found constant. */ | |
288 | int constified; | |
289 | ||
7e6eb623 | 290 | } pre_stats; |
6de9cd9a | 291 | |
bdee7684 DB |
292 | |
293 | static tree bitmap_find_leader (bitmap_set_t, tree); | |
7e6eb623 DB |
294 | static tree find_leader (value_set_t, tree); |
295 | static void value_insert_into_set (value_set_t, tree); | |
bdee7684 DB |
296 | static void bitmap_value_insert_into_set (bitmap_set_t, tree); |
297 | static void bitmap_value_replace_in_set (bitmap_set_t, tree); | |
7e6eb623 | 298 | static void insert_into_set (value_set_t, tree); |
bdee7684 DB |
299 | static void bitmap_set_copy (bitmap_set_t, bitmap_set_t); |
300 | static bool bitmap_set_contains_value (bitmap_set_t, tree); | |
301 | static bitmap_set_t bitmap_set_new (void); | |
7e6eb623 DB |
302 | static value_set_t set_new (bool); |
303 | static bool is_undefined_value (tree); | |
56db793a | 304 | static tree create_expression_by_pieces (basic_block, tree, tree); |
6de9cd9a | 305 | |
bdee7684 | 306 | |
7e6eb623 DB |
307 | /* We can add and remove elements and entries to and from sets |
308 | and hash tables, so we use alloc pools for them. */ | |
6de9cd9a | 309 | |
7e6eb623 | 310 | static alloc_pool value_set_pool; |
bdee7684 | 311 | static alloc_pool bitmap_set_pool; |
7e6eb623 DB |
312 | static alloc_pool value_set_node_pool; |
313 | static alloc_pool binary_node_pool; | |
314 | static alloc_pool unary_node_pool; | |
3d3fa3a1 | 315 | static alloc_pool reference_node_pool; |
43da81be DB |
316 | static alloc_pool comparison_node_pool; |
317 | static alloc_pool expression_node_pool; | |
318 | static alloc_pool list_node_pool; | |
c90186eb | 319 | static alloc_pool modify_expr_node_pool; |
7932a3db | 320 | static bitmap_obstack grand_bitmap_obstack; |
6de9cd9a | 321 | |
c90186eb DB |
322 | /* To avoid adding 300 temporary variables when we only need one, we |
323 | only create one temporary variable, on demand, and build ssa names | |
324 | off that. We do have to change the variable if the types don't | |
325 | match the current variable's type. */ | |
326 | static tree pretemp; | |
327 | static tree storetemp; | |
328 | static tree mergephitemp; | |
329 | static tree prephitemp; | |
330 | ||
53b4bf74 DN |
331 | /* Set of blocks with statements that have had its EH information |
332 | cleaned up. */ | |
333 | static bitmap need_eh_cleanup; | |
334 | ||
7e6eb623 DB |
335 | /* The phi_translate_table caches phi translations for a given |
336 | expression and predecessor. */ | |
ca072a31 | 337 | |
7e6eb623 | 338 | static htab_t phi_translate_table; |
6de9cd9a | 339 | |
7e6eb623 DB |
340 | /* A three tuple {e, pred, v} used to cache phi translations in the |
341 | phi_translate_table. */ | |
6de9cd9a | 342 | |
7e6eb623 | 343 | typedef struct expr_pred_trans_d |
6de9cd9a | 344 | { |
8c27b7d4 | 345 | /* The expression. */ |
7e6eb623 | 346 | tree e; |
ca072a31 DB |
347 | |
348 | /* The predecessor block along which we translated the expression. */ | |
7e6eb623 | 349 | basic_block pred; |
ca072a31 | 350 | |
c90186eb DB |
351 | /* vuses associated with the expression. */ |
352 | VEC (tree, gc) *vuses; | |
353 | ||
ca072a31 | 354 | /* The value that resulted from the translation. */ |
7e6eb623 | 355 | tree v; |
ca072a31 | 356 | |
c90186eb | 357 | |
ca072a31 DB |
358 | /* The hashcode for the expression, pred pair. This is cached for |
359 | speed reasons. */ | |
7e6eb623 DB |
360 | hashval_t hashcode; |
361 | } *expr_pred_trans_t; | |
6de9cd9a | 362 | |
7e6eb623 | 363 | /* Return the hash value for a phi translation table entry. */ |
6de9cd9a | 364 | |
7e6eb623 DB |
365 | static hashval_t |
366 | expr_pred_trans_hash (const void *p) | |
367 | { | |
368 | const expr_pred_trans_t ve = (expr_pred_trans_t) p; | |
369 | return ve->hashcode; | |
370 | } | |
6de9cd9a | 371 | |
ca072a31 DB |
372 | /* Return true if two phi translation table entries are the same. |
373 | P1 and P2 should point to the expr_pred_trans_t's to be compared.*/ | |
7e6eb623 DB |
374 | |
375 | static int | |
376 | expr_pred_trans_eq (const void *p1, const void *p2) | |
377 | { | |
378 | const expr_pred_trans_t ve1 = (expr_pred_trans_t) p1; | |
379 | const expr_pred_trans_t ve2 = (expr_pred_trans_t) p2; | |
7e6eb623 DB |
380 | basic_block b1 = ve1->pred; |
381 | basic_block b2 = ve2->pred; | |
c90186eb DB |
382 | int i; |
383 | tree vuse1; | |
ca072a31 DB |
384 | |
385 | /* If they are not translations for the same basic block, they can't | |
386 | be equal. */ | |
7e6eb623 | 387 | if (b1 != b2) |
6de9cd9a | 388 | return false; |
6de9cd9a | 389 | |
c90186eb | 390 | |
ca072a31 | 391 | /* If they are for the same basic block, determine if the |
471854f8 | 392 | expressions are equal. */ |
c90186eb DB |
393 | if (!expressions_equal_p (ve1->e, ve2->e)) |
394 | return false; | |
395 | ||
396 | /* Make sure the vuses are equivalent. */ | |
397 | if (ve1->vuses == ve2->vuses) | |
7e6eb623 DB |
398 | return true; |
399 | ||
c90186eb DB |
400 | if (VEC_length (tree, ve1->vuses) != VEC_length (tree, ve2->vuses)) |
401 | return false; | |
402 | ||
403 | for (i = 0; VEC_iterate (tree, ve1->vuses, i, vuse1); i++) | |
404 | { | |
405 | if (VEC_index (tree, ve2->vuses, i) != vuse1) | |
406 | return false; | |
407 | } | |
408 | ||
409 | return true; | |
6de9cd9a DN |
410 | } |
411 | ||
ca072a31 | 412 | /* Search in the phi translation table for the translation of |
c90186eb DB |
413 | expression E in basic block PRED with vuses VUSES. |
414 | Return the translated value, if found, NULL otherwise. */ | |
6de9cd9a DN |
415 | |
416 | static inline tree | |
c90186eb | 417 | phi_trans_lookup (tree e, basic_block pred, VEC (tree, gc) *vuses) |
6de9cd9a | 418 | { |
7e6eb623 | 419 | void **slot; |
ca072a31 | 420 | struct expr_pred_trans_d ept; |
c90186eb | 421 | |
ca072a31 DB |
422 | ept.e = e; |
423 | ept.pred = pred; | |
c90186eb DB |
424 | ept.vuses = vuses; |
425 | ept.hashcode = vn_compute (e, (unsigned long) pred); | |
ca072a31 | 426 | slot = htab_find_slot_with_hash (phi_translate_table, &ept, ept.hashcode, |
7e6eb623 DB |
427 | NO_INSERT); |
428 | if (!slot) | |
429 | return NULL; | |
430 | else | |
431 | return ((expr_pred_trans_t) *slot)->v; | |
432 | } | |
6de9cd9a | 433 | |
6de9cd9a | 434 | |
c90186eb | 435 | /* Add the tuple mapping from {expression E, basic block PRED, vuses VUSES} to |
ca072a31 | 436 | value V, to the phi translation table. */ |
7e6eb623 DB |
437 | |
438 | static inline void | |
c90186eb | 439 | phi_trans_add (tree e, tree v, basic_block pred, VEC (tree, gc) *vuses) |
7e6eb623 DB |
440 | { |
441 | void **slot; | |
e1111e8e | 442 | expr_pred_trans_t new_pair = XNEW (struct expr_pred_trans_d); |
7e6eb623 DB |
443 | new_pair->e = e; |
444 | new_pair->pred = pred; | |
c90186eb | 445 | new_pair->vuses = vuses; |
7e6eb623 | 446 | new_pair->v = v; |
c90186eb | 447 | new_pair->hashcode = vn_compute (e, (unsigned long) pred); |
7e6eb623 DB |
448 | slot = htab_find_slot_with_hash (phi_translate_table, new_pair, |
449 | new_pair->hashcode, INSERT); | |
450 | if (*slot) | |
451 | free (*slot); | |
452 | *slot = (void *) new_pair; | |
6de9cd9a DN |
453 | } |
454 | ||
ff2ad0f7 | 455 | |
ca072a31 | 456 | /* Add expression E to the expression set of value V. */ |
6de9cd9a | 457 | |
33c94679 | 458 | void |
7e6eb623 | 459 | add_to_value (tree v, tree e) |
6de9cd9a | 460 | { |
bddeccfe DN |
461 | /* Constants have no expression sets. */ |
462 | if (is_gimple_min_invariant (v)) | |
56db793a | 463 | return; |
6de9cd9a | 464 | |
33c94679 DN |
465 | if (VALUE_HANDLE_EXPR_SET (v) == NULL) |
466 | VALUE_HANDLE_EXPR_SET (v) = set_new (false); | |
7e6eb623 | 467 | |
33c94679 | 468 | insert_into_set (VALUE_HANDLE_EXPR_SET (v), e); |
7e6eb623 | 469 | } |
6de9cd9a | 470 | |
6de9cd9a | 471 | |
ca072a31 | 472 | /* Return true if value V exists in the bitmap for SET. */ |
6de9cd9a DN |
473 | |
474 | static inline bool | |
ca072a31 | 475 | value_exists_in_set_bitmap (value_set_t set, tree v) |
6de9cd9a | 476 | { |
7e6eb623 DB |
477 | if (!set->values) |
478 | return false; | |
33c94679 DN |
479 | |
480 | return bitmap_bit_p (set->values, VALUE_HANDLE_ID (v)); | |
6de9cd9a DN |
481 | } |
482 | ||
33c94679 | 483 | |
ca072a31 | 484 | /* Remove value V from the bitmap for SET. */ |
6de9cd9a | 485 | |
7e6eb623 | 486 | static void |
ca072a31 | 487 | value_remove_from_set_bitmap (value_set_t set, tree v) |
7e6eb623 | 488 | { |
1e128c5f | 489 | gcc_assert (set->indexed); |
33c94679 | 490 | |
7e6eb623 DB |
491 | if (!set->values) |
492 | return; | |
33c94679 DN |
493 | |
494 | bitmap_clear_bit (set->values, VALUE_HANDLE_ID (v)); | |
7e6eb623 | 495 | } |
6de9cd9a | 496 | |
6de9cd9a | 497 | |
ca072a31 | 498 | /* Insert the value number V into the bitmap of values existing in |
7e6eb623 | 499 | SET. */ |
6de9cd9a | 500 | |
7e6eb623 | 501 | static inline void |
ca072a31 | 502 | value_insert_into_set_bitmap (value_set_t set, tree v) |
6de9cd9a | 503 | { |
1e128c5f | 504 | gcc_assert (set->indexed); |
33c94679 | 505 | |
7e6eb623 | 506 | if (set->values == NULL) |
cc175e7c | 507 | set->values = BITMAP_ALLOC (&grand_bitmap_obstack); |
33c94679 DN |
508 | |
509 | bitmap_set_bit (set->values, VALUE_HANDLE_ID (v)); | |
7e6eb623 | 510 | } |
6de9cd9a | 511 | |
33c94679 | 512 | |
bdee7684 DB |
513 | /* Create a new bitmap set and return it. */ |
514 | ||
515 | static bitmap_set_t | |
516 | bitmap_set_new (void) | |
517 | { | |
e1111e8e | 518 | bitmap_set_t ret = (bitmap_set_t) pool_alloc (bitmap_set_pool); |
cc175e7c NS |
519 | ret->expressions = BITMAP_ALLOC (&grand_bitmap_obstack); |
520 | ret->values = BITMAP_ALLOC (&grand_bitmap_obstack); | |
bdee7684 DB |
521 | return ret; |
522 | } | |
523 | ||
7e6eb623 DB |
524 | /* Create a new set. */ |
525 | ||
526 | static value_set_t | |
527 | set_new (bool indexed) | |
528 | { | |
529 | value_set_t ret; | |
e1111e8e | 530 | ret = (value_set_t) pool_alloc (value_set_pool); |
7e6eb623 DB |
531 | ret->head = ret->tail = NULL; |
532 | ret->length = 0; | |
533 | ret->indexed = indexed; | |
534 | ret->values = NULL; | |
6de9cd9a DN |
535 | return ret; |
536 | } | |
537 | ||
6b416da1 | 538 | /* Insert an expression EXPR into a bitmapped set. */ |
bdee7684 DB |
539 | |
540 | static void | |
541 | bitmap_insert_into_set (bitmap_set_t set, tree expr) | |
542 | { | |
543 | tree val; | |
544 | /* XXX: For now, we only let SSA_NAMES into the bitmap sets. */ | |
1e128c5f | 545 | gcc_assert (TREE_CODE (expr) == SSA_NAME); |
bdee7684 DB |
546 | val = get_value_handle (expr); |
547 | ||
1e128c5f | 548 | gcc_assert (val); |
6b416da1 | 549 | if (!is_gimple_min_invariant (val)) |
d6fd4b8d | 550 | { |
6b416da1 | 551 | bitmap_set_bit (set->values, VALUE_HANDLE_ID (val)); |
d6fd4b8d DB |
552 | bitmap_set_bit (set->expressions, SSA_NAME_VERSION (expr)); |
553 | } | |
bdee7684 | 554 | } |
6de9cd9a | 555 | |
7e6eb623 DB |
556 | /* Insert EXPR into SET. */ |
557 | ||
558 | static void | |
559 | insert_into_set (value_set_t set, tree expr) | |
560 | { | |
e1111e8e | 561 | value_set_node_t newnode = (value_set_node_t) pool_alloc (value_set_node_pool); |
7e6eb623 | 562 | tree val = get_value_handle (expr); |
1e128c5f | 563 | gcc_assert (val); |
97141338 DB |
564 | |
565 | if (is_gimple_min_invariant (val)) | |
566 | return; | |
6de9cd9a | 567 | |
7e6eb623 DB |
568 | /* For indexed sets, insert the value into the set value bitmap. |
569 | For all sets, add it to the linked list and increment the list | |
570 | length. */ | |
571 | if (set->indexed) | |
572 | value_insert_into_set_bitmap (set, val); | |
6de9cd9a | 573 | |
7e6eb623 DB |
574 | newnode->next = NULL; |
575 | newnode->expr = expr; | |
576 | set->length ++; | |
577 | if (set->head == NULL) | |
578 | { | |
579 | set->head = set->tail = newnode; | |
580 | } | |
581 | else | |
582 | { | |
583 | set->tail->next = newnode; | |
584 | set->tail = newnode; | |
585 | } | |
586 | } | |
6de9cd9a | 587 | |
bdee7684 DB |
588 | /* Copy a bitmapped set ORIG, into bitmapped set DEST. */ |
589 | ||
590 | static void | |
591 | bitmap_set_copy (bitmap_set_t dest, bitmap_set_t orig) | |
592 | { | |
593 | bitmap_copy (dest->expressions, orig->expressions); | |
594 | bitmap_copy (dest->values, orig->values); | |
595 | } | |
596 | ||
6416ae7f | 597 | /* Perform bitmapped set operation DEST &= ORIG. */ |
ff3fdad2 DB |
598 | |
599 | static void | |
600 | bitmap_set_and (bitmap_set_t dest, bitmap_set_t orig) | |
601 | { | |
602 | bitmap_iterator bi; | |
603 | unsigned int i; | |
604 | bitmap temp = BITMAP_ALLOC (&grand_bitmap_obstack); | |
605 | ||
606 | bitmap_and_into (dest->values, orig->values); | |
607 | bitmap_copy (temp, dest->expressions); | |
608 | EXECUTE_IF_SET_IN_BITMAP (temp, 0, i, bi) | |
609 | { | |
610 | tree name = ssa_name (i); | |
611 | tree val = get_value_handle (name); | |
612 | if (!bitmap_bit_p (dest->values, VALUE_HANDLE_ID (val))) | |
613 | bitmap_clear_bit (dest->expressions, i); | |
614 | } | |
615 | ||
616 | } | |
617 | ||
618 | /* Perform bitmapped value set operation DEST = DEST & ~ORIG. */ | |
619 | ||
620 | static void | |
621 | bitmap_set_and_compl (bitmap_set_t dest, bitmap_set_t orig) | |
622 | { | |
623 | bitmap_iterator bi; | |
624 | unsigned int i; | |
625 | bitmap temp = BITMAP_ALLOC (&grand_bitmap_obstack); | |
626 | ||
627 | bitmap_and_compl_into (dest->values, orig->values); | |
628 | bitmap_copy (temp, dest->expressions); | |
629 | EXECUTE_IF_SET_IN_BITMAP (temp, 0, i, bi) | |
630 | { | |
631 | tree name = ssa_name (i); | |
632 | tree val = get_value_handle (name); | |
633 | if (!bitmap_bit_p (dest->values, VALUE_HANDLE_ID (val))) | |
634 | bitmap_clear_bit (dest->expressions, i); | |
635 | } | |
636 | } | |
637 | ||
638 | /* Return true if the bitmap set SET is empty. */ | |
639 | ||
640 | static bool | |
641 | bitmap_set_empty_p (bitmap_set_t set) | |
642 | { | |
643 | return bitmap_empty_p (set->values); | |
644 | } | |
645 | ||
7e6eb623 | 646 | /* Copy the set ORIG to the set DEST. */ |
6de9cd9a | 647 | |
7e6eb623 DB |
648 | static void |
649 | set_copy (value_set_t dest, value_set_t orig) | |
650 | { | |
651 | value_set_node_t node; | |
652 | ||
653 | if (!orig || !orig->head) | |
654 | return; | |
6de9cd9a | 655 | |
7e6eb623 DB |
656 | for (node = orig->head; |
657 | node; | |
658 | node = node->next) | |
659 | { | |
660 | insert_into_set (dest, node->expr); | |
661 | } | |
662 | } | |
6de9cd9a | 663 | |
7e6eb623 | 664 | /* Remove EXPR from SET. */ |
6de9cd9a DN |
665 | |
666 | static void | |
7e6eb623 | 667 | set_remove (value_set_t set, tree expr) |
6de9cd9a | 668 | { |
7e6eb623 | 669 | value_set_node_t node, prev; |
6de9cd9a | 670 | |
7e6eb623 DB |
671 | /* Remove the value of EXPR from the bitmap, decrement the set |
672 | length, and remove it from the actual double linked list. */ | |
673 | value_remove_from_set_bitmap (set, get_value_handle (expr)); | |
674 | set->length--; | |
675 | prev = NULL; | |
676 | for (node = set->head; | |
677 | node != NULL; | |
678 | prev = node, node = node->next) | |
679 | { | |
680 | if (node->expr == expr) | |
681 | { | |
682 | if (prev == NULL) | |
683 | set->head = node->next; | |
684 | else | |
685 | prev->next= node->next; | |
686 | ||
687 | if (node == set->tail) | |
688 | set->tail = prev; | |
689 | pool_free (value_set_node_pool, node); | |
690 | return; | |
691 | } | |
6de9cd9a DN |
692 | } |
693 | } | |
694 | ||
7e6eb623 DB |
695 | /* Return true if SET contains the value VAL. */ |
696 | ||
697 | static bool | |
698 | set_contains_value (value_set_t set, tree val) | |
699 | { | |
bddeccfe DN |
700 | /* All constants are in every set. */ |
701 | if (is_gimple_min_invariant (val)) | |
7e6eb623 DB |
702 | return true; |
703 | ||
704 | if (set->length == 0) | |
705 | return false; | |
706 | ||
707 | return value_exists_in_set_bitmap (set, val); | |
708 | } | |
6de9cd9a | 709 | |
6b416da1 DB |
710 | /* Return true if bitmapped set SET contains the expression EXPR. */ |
711 | static bool | |
712 | bitmap_set_contains (bitmap_set_t set, tree expr) | |
713 | { | |
af75a7ea DB |
714 | /* All constants are in every set. */ |
715 | if (is_gimple_min_invariant (get_value_handle (expr))) | |
716 | return true; | |
717 | ||
6b416da1 DB |
718 | /* XXX: Bitmapped sets only contain SSA_NAME's for now. */ |
719 | if (TREE_CODE (expr) != SSA_NAME) | |
720 | return false; | |
721 | return bitmap_bit_p (set->expressions, SSA_NAME_VERSION (expr)); | |
722 | } | |
723 | ||
724 | ||
bdee7684 | 725 | /* Return true if bitmapped set SET contains the value VAL. */ |
6de9cd9a | 726 | |
bdee7684 DB |
727 | static bool |
728 | bitmap_set_contains_value (bitmap_set_t set, tree val) | |
6de9cd9a | 729 | { |
bdee7684 DB |
730 | if (is_gimple_min_invariant (val)) |
731 | return true; | |
732 | return bitmap_bit_p (set->values, VALUE_HANDLE_ID (val)); | |
733 | } | |
7e6eb623 | 734 | |
bdee7684 | 735 | /* Replace an instance of value LOOKFOR with expression EXPR in SET. */ |
7e6eb623 | 736 | |
bdee7684 DB |
737 | static void |
738 | bitmap_set_replace_value (bitmap_set_t set, tree lookfor, tree expr) | |
739 | { | |
740 | value_set_t exprset; | |
741 | value_set_node_t node; | |
742 | if (is_gimple_min_invariant (lookfor)) | |
743 | return; | |
744 | if (!bitmap_set_contains_value (set, lookfor)) | |
745 | return; | |
e9284566 | 746 | |
6b416da1 DB |
747 | /* The number of expressions having a given value is usually |
748 | significantly less than the total number of expressions in SET. | |
749 | Thus, rather than check, for each expression in SET, whether it | |
750 | has the value LOOKFOR, we walk the reverse mapping that tells us | |
751 | what expressions have a given value, and see if any of those | |
752 | expressions are in our set. For large testcases, this is about | |
753 | 5-10x faster than walking the bitmap. If this is somehow a | |
754 | significant lose for some cases, we can choose which set to walk | |
755 | based on the set size. */ | |
bdee7684 DB |
756 | exprset = VALUE_HANDLE_EXPR_SET (lookfor); |
757 | for (node = exprset->head; node; node = node->next) | |
6de9cd9a | 758 | { |
bdee7684 | 759 | if (TREE_CODE (node->expr) == SSA_NAME) |
6de9cd9a | 760 | { |
bdee7684 DB |
761 | if (bitmap_bit_p (set->expressions, SSA_NAME_VERSION (node->expr))) |
762 | { | |
763 | bitmap_clear_bit (set->expressions, SSA_NAME_VERSION (node->expr)); | |
764 | bitmap_set_bit (set->expressions, SSA_NAME_VERSION (expr)); | |
765 | return; | |
766 | } | |
6de9cd9a | 767 | } |
6de9cd9a DN |
768 | } |
769 | } | |
770 | ||
6b416da1 | 771 | /* Subtract bitmapped set B from value set A, and return the new set. */ |
6de9cd9a | 772 | |
7e6eb623 | 773 | static value_set_t |
6b416da1 DB |
774 | bitmap_set_subtract_from_value_set (value_set_t a, bitmap_set_t b, |
775 | bool indexed) | |
7e6eb623 DB |
776 | { |
777 | value_set_t ret = set_new (indexed); | |
778 | value_set_node_t node; | |
779 | for (node = a->head; | |
780 | node; | |
781 | node = node->next) | |
782 | { | |
6b416da1 | 783 | if (!bitmap_set_contains (b, node->expr)) |
7e6eb623 DB |
784 | insert_into_set (ret, node->expr); |
785 | } | |
786 | return ret; | |
6de9cd9a DN |
787 | } |
788 | ||
8c27b7d4 | 789 | /* Return true if two sets are equal. */ |
6de9cd9a | 790 | |
7e6eb623 DB |
791 | static bool |
792 | set_equal (value_set_t a, value_set_t b) | |
6de9cd9a | 793 | { |
7e6eb623 DB |
794 | value_set_node_t node; |
795 | ||
796 | if (a->length != b->length) | |
797 | return false; | |
798 | for (node = a->head; | |
799 | node; | |
800 | node = node->next) | |
801 | { | |
802 | if (!set_contains_value (b, get_value_handle (node->expr))) | |
803 | return false; | |
804 | } | |
805 | return true; | |
6de9cd9a DN |
806 | } |
807 | ||
e9284566 | 808 | /* Replace an instance of EXPR's VALUE with EXPR in SET if it exists, |
6c6cfbfd | 809 | and add it otherwise. */ |
bdee7684 | 810 | |
7e6eb623 | 811 | static void |
bdee7684 | 812 | bitmap_value_replace_in_set (bitmap_set_t set, tree expr) |
7e6eb623 DB |
813 | { |
814 | tree val = get_value_handle (expr); | |
e9284566 DB |
815 | if (bitmap_set_contains_value (set, val)) |
816 | bitmap_set_replace_value (set, val, expr); | |
817 | else | |
818 | bitmap_insert_into_set (set, expr); | |
bdee7684 | 819 | } |
7e6eb623 | 820 | |
bdee7684 DB |
821 | /* Insert EXPR into SET if EXPR's value is not already present in |
822 | SET. */ | |
823 | ||
824 | static void | |
825 | bitmap_value_insert_into_set (bitmap_set_t set, tree expr) | |
826 | { | |
827 | tree val = get_value_handle (expr); | |
af75a7ea | 828 | |
bdee7684 | 829 | if (is_gimple_min_invariant (val)) |
7e6eb623 DB |
830 | return; |
831 | ||
bdee7684 DB |
832 | if (!bitmap_set_contains_value (set, val)) |
833 | bitmap_insert_into_set (set, expr); | |
7e6eb623 | 834 | } |
6de9cd9a | 835 | |
7e6eb623 | 836 | /* Insert the value for EXPR into SET, if it doesn't exist already. */ |
6de9cd9a | 837 | |
7e6eb623 DB |
838 | static void |
839 | value_insert_into_set (value_set_t set, tree expr) | |
6de9cd9a | 840 | { |
7e6eb623 | 841 | tree val = get_value_handle (expr); |
6de9cd9a | 842 | |
56db793a DB |
843 | /* Constant and invariant values exist everywhere, and thus, |
844 | actually keeping them in the sets is pointless. */ | |
bddeccfe | 845 | if (is_gimple_min_invariant (val)) |
7e6eb623 | 846 | return; |
6de9cd9a | 847 | |
7e6eb623 DB |
848 | if (!set_contains_value (set, val)) |
849 | insert_into_set (set, expr); | |
6de9cd9a DN |
850 | } |
851 | ||
852 | ||
bdee7684 DB |
853 | /* Print out SET to OUTFILE. */ |
854 | ||
855 | static void | |
856 | bitmap_print_value_set (FILE *outfile, bitmap_set_t set, | |
857 | const char *setname, int blockindex) | |
858 | { | |
859 | fprintf (outfile, "%s[%d] := { ", setname, blockindex); | |
860 | if (set) | |
861 | { | |
cf6b9ef1 | 862 | bool first = true; |
3cd8c58a | 863 | unsigned i; |
87c476a2 ZD |
864 | bitmap_iterator bi; |
865 | ||
866 | EXECUTE_IF_SET_IN_BITMAP (set->expressions, 0, i, bi) | |
867 | { | |
65a6f342 NS |
868 | if (!first) |
869 | fprintf (outfile, ", "); | |
870 | first = false; | |
87c476a2 | 871 | print_generic_expr (outfile, ssa_name (i), 0); |
bdee7684 | 872 | |
87c476a2 ZD |
873 | fprintf (outfile, " ("); |
874 | print_generic_expr (outfile, get_value_handle (ssa_name (i)), 0); | |
875 | fprintf (outfile, ") "); | |
87c476a2 | 876 | } |
bdee7684 DB |
877 | } |
878 | fprintf (outfile, " }\n"); | |
879 | } | |
7e6eb623 | 880 | /* Print out the value_set SET to OUTFILE. */ |
6de9cd9a | 881 | |
7e6eb623 DB |
882 | static void |
883 | print_value_set (FILE *outfile, value_set_t set, | |
884 | const char *setname, int blockindex) | |
6de9cd9a | 885 | { |
7e6eb623 DB |
886 | value_set_node_t node; |
887 | fprintf (outfile, "%s[%d] := { ", setname, blockindex); | |
888 | if (set) | |
6de9cd9a | 889 | { |
7e6eb623 DB |
890 | for (node = set->head; |
891 | node; | |
892 | node = node->next) | |
6de9cd9a | 893 | { |
7e6eb623 | 894 | print_generic_expr (outfile, node->expr, 0); |
ca072a31 DB |
895 | |
896 | fprintf (outfile, " ("); | |
897 | print_generic_expr (outfile, get_value_handle (node->expr), 0); | |
898 | fprintf (outfile, ") "); | |
899 | ||
7e6eb623 DB |
900 | if (node->next) |
901 | fprintf (outfile, ", "); | |
6de9cd9a | 902 | } |
6de9cd9a DN |
903 | } |
904 | ||
7e6eb623 DB |
905 | fprintf (outfile, " }\n"); |
906 | } | |
907 | ||
908 | /* Print out the expressions that have VAL to OUTFILE. */ | |
33c94679 | 909 | |
7e6eb623 DB |
910 | void |
911 | print_value_expressions (FILE *outfile, tree val) | |
912 | { | |
33c94679 DN |
913 | if (VALUE_HANDLE_EXPR_SET (val)) |
914 | { | |
915 | char s[10]; | |
916 | sprintf (s, "VH.%04d", VALUE_HANDLE_ID (val)); | |
917 | print_value_set (outfile, VALUE_HANDLE_EXPR_SET (val), s, 0); | |
918 | } | |
6de9cd9a DN |
919 | } |
920 | ||
6de9cd9a | 921 | |
7e6eb623 DB |
922 | void |
923 | debug_value_expressions (tree val) | |
6de9cd9a | 924 | { |
7e6eb623 DB |
925 | print_value_expressions (stderr, val); |
926 | } | |
927 | ||
6de9cd9a | 928 | |
7e6eb623 | 929 | void debug_value_set (value_set_t, const char *, int); |
6de9cd9a | 930 | |
7e6eb623 DB |
931 | void |
932 | debug_value_set (value_set_t set, const char *setname, int blockindex) | |
6de9cd9a | 933 | { |
7e6eb623 | 934 | print_value_set (stderr, set, setname, blockindex); |
6de9cd9a DN |
935 | } |
936 | ||
0995a441 SB |
937 | /* Return the folded version of T if T, when folded, is a gimple |
938 | min_invariant. Otherwise, return T. */ | |
939 | ||
940 | static tree | |
941 | fully_constant_expression (tree t) | |
942 | { | |
943 | tree folded; | |
944 | folded = fold (t); | |
945 | if (folded && is_gimple_min_invariant (folded)) | |
946 | return folded; | |
947 | return t; | |
948 | } | |
949 | ||
43da81be DB |
950 | /* Return a copy of a chain of nodes, chained through the TREE_CHAIN field. |
951 | For example, this can copy a list made of TREE_LIST nodes. | |
952 | Allocates the nodes in list_node_pool*/ | |
953 | ||
954 | static tree | |
955 | pool_copy_list (tree list) | |
956 | { | |
957 | tree head; | |
958 | tree prev, next; | |
959 | ||
960 | if (list == 0) | |
961 | return 0; | |
e1111e8e | 962 | head = (tree) pool_alloc (list_node_pool); |
43da81be DB |
963 | |
964 | memcpy (head, list, tree_size (list)); | |
965 | prev = head; | |
966 | ||
967 | next = TREE_CHAIN (list); | |
968 | while (next) | |
969 | { | |
e1111e8e | 970 | TREE_CHAIN (prev) = (tree) pool_alloc (list_node_pool); |
43da81be DB |
971 | memcpy (TREE_CHAIN (prev), next, tree_size (next)); |
972 | prev = TREE_CHAIN (prev); | |
973 | next = TREE_CHAIN (next); | |
974 | } | |
975 | return head; | |
976 | } | |
977 | ||
c90186eb DB |
978 | /* Translate the vuses in the VUSES vector backwards through phi |
979 | nodes, so that they have the value they would have in BLOCK. */ | |
980 | ||
981 | static VEC(tree, gc) * | |
982 | translate_vuses_through_block (VEC (tree, gc) *vuses, basic_block block) | |
983 | { | |
984 | tree oldvuse; | |
985 | VEC(tree, gc) *result = NULL; | |
986 | int i; | |
43da81be | 987 | |
c90186eb DB |
988 | for (i = 0; VEC_iterate (tree, vuses, i, oldvuse); i++) |
989 | { | |
990 | tree phi = SSA_NAME_DEF_STMT (oldvuse); | |
991 | if (TREE_CODE (phi) == PHI_NODE) | |
992 | { | |
993 | edge e = find_edge (block, bb_for_stmt (phi)); | |
994 | if (e) | |
995 | { | |
996 | tree def = PHI_ARG_DEF (phi, e->dest_idx); | |
997 | if (def != oldvuse) | |
998 | { | |
999 | if (!result) | |
1000 | result = VEC_copy (tree, gc, vuses); | |
1001 | VEC_replace (tree, result, i, def); | |
1002 | } | |
1003 | } | |
1004 | } | |
1005 | } | |
1006 | if (result) | |
1007 | { | |
1008 | sort_vuses (result); | |
1009 | return result; | |
1010 | } | |
1011 | return vuses; | |
1012 | ||
1013 | } | |
7e6eb623 DB |
1014 | /* Translate EXPR using phis in PHIBLOCK, so that it has the values of |
1015 | the phis in PRED. Return NULL if we can't find a leader for each | |
1016 | part of the translated expression. */ | |
6de9cd9a DN |
1017 | |
1018 | static tree | |
ff2ad0f7 | 1019 | phi_translate (tree expr, value_set_t set, basic_block pred, |
7e6eb623 | 1020 | basic_block phiblock) |
6de9cd9a | 1021 | { |
7e6eb623 DB |
1022 | tree phitrans = NULL; |
1023 | tree oldexpr = expr; | |
7e6eb623 DB |
1024 | if (expr == NULL) |
1025 | return NULL; | |
6de9cd9a | 1026 | |
6615c446 JO |
1027 | if (is_gimple_min_invariant (expr)) |
1028 | return expr; | |
1029 | ||
ea4b7848 | 1030 | /* Phi translations of a given expression don't change. */ |
c90186eb DB |
1031 | if (EXPR_P (expr)) |
1032 | { | |
1033 | tree vh; | |
1034 | ||
1035 | vh = get_value_handle (expr); | |
1036 | if (vh && TREE_CODE (vh) == VALUE_HANDLE) | |
1037 | phitrans = phi_trans_lookup (expr, pred, VALUE_HANDLE_VUSES (vh)); | |
1038 | else | |
1039 | phitrans = phi_trans_lookup (expr, pred, NULL); | |
1040 | } | |
1041 | else | |
1042 | phitrans = phi_trans_lookup (expr, pred, NULL); | |
1043 | ||
7e6eb623 DB |
1044 | if (phitrans) |
1045 | return phitrans; | |
1046 | ||
7e6eb623 | 1047 | switch (TREE_CODE_CLASS (TREE_CODE (expr))) |
6de9cd9a | 1048 | { |
43da81be DB |
1049 | case tcc_expression: |
1050 | { | |
1051 | if (TREE_CODE (expr) != CALL_EXPR) | |
1052 | return NULL; | |
1053 | else | |
1054 | { | |
1055 | tree oldop0 = TREE_OPERAND (expr, 0); | |
1056 | tree oldarglist = TREE_OPERAND (expr, 1); | |
1057 | tree oldop2 = TREE_OPERAND (expr, 2); | |
1058 | tree newop0; | |
1059 | tree newarglist; | |
1060 | tree newop2 = NULL; | |
1061 | tree oldwalker; | |
1062 | tree newwalker; | |
1063 | tree newexpr; | |
c90186eb | 1064 | tree vh = get_value_handle (expr); |
43da81be | 1065 | bool listchanged = false; |
c90186eb DB |
1066 | VEC (tree, gc) *vuses = VALUE_HANDLE_VUSES (vh); |
1067 | VEC (tree, gc) *tvuses; | |
43da81be DB |
1068 | |
1069 | /* Call expressions are kind of weird because they have an | |
1070 | argument list. We don't want to value number the list | |
1071 | as one value number, because that doesn't make much | |
1072 | sense, and just breaks the support functions we call, | |
1073 | which expect TREE_OPERAND (call_expr, 2) to be a | |
1074 | TREE_LIST. */ | |
1075 | ||
1076 | newop0 = phi_translate (find_leader (set, oldop0), | |
1077 | set, pred, phiblock); | |
1078 | if (newop0 == NULL) | |
1079 | return NULL; | |
1080 | if (oldop2) | |
1081 | { | |
1082 | newop2 = phi_translate (find_leader (set, oldop2), | |
1083 | set, pred, phiblock); | |
1084 | if (newop2 == NULL) | |
1085 | return NULL; | |
1086 | } | |
1087 | ||
1088 | /* phi translate the argument list piece by piece. | |
1089 | ||
1090 | We could actually build the list piece by piece here, | |
1091 | but it's likely to not be worth the memory we will save, | |
1092 | unless you have millions of call arguments. */ | |
1093 | ||
1094 | newarglist = pool_copy_list (oldarglist); | |
1095 | for (oldwalker = oldarglist, newwalker = newarglist; | |
1096 | oldwalker && newwalker; | |
1097 | oldwalker = TREE_CHAIN (oldwalker), | |
1098 | newwalker = TREE_CHAIN (newwalker)) | |
1099 | { | |
1100 | ||
1101 | tree oldval = TREE_VALUE (oldwalker); | |
1102 | tree newval; | |
1103 | if (oldval) | |
1104 | { | |
1105 | newval = phi_translate (find_leader (set, oldval), | |
1106 | set, pred, phiblock); | |
1107 | if (newval == NULL) | |
1108 | return NULL; | |
1109 | if (newval != oldval) | |
1110 | { | |
1111 | listchanged = true; | |
1112 | TREE_VALUE (newwalker) = get_value_handle (newval); | |
1113 | } | |
1114 | } | |
1115 | } | |
1116 | if (listchanged) | |
1117 | vn_lookup_or_add (newarglist, NULL); | |
1118 | ||
c90186eb DB |
1119 | tvuses = translate_vuses_through_block (vuses, pred); |
1120 | ||
1121 | if (listchanged || (newop0 != oldop0) || (oldop2 != newop2) | |
1122 | || vuses != tvuses) | |
43da81be | 1123 | { |
e1111e8e | 1124 | newexpr = (tree) pool_alloc (expression_node_pool); |
43da81be DB |
1125 | memcpy (newexpr, expr, tree_size (expr)); |
1126 | TREE_OPERAND (newexpr, 0) = newop0 == oldop0 ? oldop0 : get_value_handle (newop0); | |
1127 | TREE_OPERAND (newexpr, 1) = listchanged ? newarglist : oldarglist; | |
1128 | TREE_OPERAND (newexpr, 2) = newop2 == oldop2 ? oldop2 : get_value_handle (newop2); | |
1129 | create_tree_ann (newexpr); | |
c90186eb | 1130 | vn_lookup_or_add_with_vuses (newexpr, tvuses); |
43da81be | 1131 | expr = newexpr; |
c90186eb | 1132 | phi_trans_add (oldexpr, newexpr, pred, tvuses); |
43da81be DB |
1133 | } |
1134 | } | |
1135 | } | |
1136 | return expr; | |
1137 | ||
c90186eb DB |
1138 | case tcc_declaration: |
1139 | { | |
1140 | VEC (tree, gc) * oldvuses = NULL; | |
1141 | VEC (tree, gc) * newvuses = NULL; | |
1142 | ||
1143 | oldvuses = VALUE_HANDLE_VUSES (get_value_handle (expr)); | |
1144 | if (oldvuses) | |
1145 | newvuses = translate_vuses_through_block (oldvuses, pred); | |
1146 | ||
1147 | if (oldvuses != newvuses) | |
1148 | vn_lookup_or_add_with_vuses (expr, newvuses); | |
1149 | ||
1150 | phi_trans_add (oldexpr, expr, pred, newvuses); | |
1151 | } | |
1152 | return expr; | |
1153 | ||
6615c446 | 1154 | case tcc_reference: |
c90186eb DB |
1155 | { |
1156 | tree oldop1 = TREE_OPERAND (expr, 0); | |
1157 | tree newop1; | |
1158 | tree newexpr; | |
1159 | VEC (tree, gc) * oldvuses = NULL; | |
1160 | VEC (tree, gc) * newvuses = NULL; | |
1161 | ||
1162 | if (TREE_CODE (expr) != INDIRECT_REF) | |
1163 | return NULL; | |
1164 | ||
1165 | newop1 = phi_translate (find_leader (set, oldop1), | |
1166 | set, pred, phiblock); | |
1167 | if (newop1 == NULL) | |
1168 | return NULL; | |
1169 | ||
1170 | oldvuses = VALUE_HANDLE_VUSES (get_value_handle (expr)); | |
1171 | if (oldvuses) | |
1172 | newvuses = translate_vuses_through_block (oldvuses, pred); | |
1173 | ||
1174 | if (newop1 != oldop1 || newvuses != oldvuses) | |
1175 | { | |
1176 | tree t; | |
1177 | ||
1178 | newexpr = pool_alloc (reference_node_pool); | |
1179 | memcpy (newexpr, expr, tree_size (expr)); | |
1180 | TREE_OPERAND (newexpr, 0) = get_value_handle (newop1); | |
1181 | ||
1182 | t = fully_constant_expression (newexpr); | |
1183 | ||
1184 | if (t != newexpr) | |
1185 | { | |
1186 | pool_free (reference_node_pool, newexpr); | |
1187 | newexpr = t; | |
1188 | } | |
1189 | else | |
1190 | { | |
1191 | create_tree_ann (newexpr); | |
1192 | vn_lookup_or_add_with_vuses (newexpr, newvuses); | |
1193 | } | |
1194 | expr = newexpr; | |
1195 | phi_trans_add (oldexpr, newexpr, pred, newvuses); | |
1196 | } | |
1197 | } | |
1198 | return expr; | |
1199 | break; | |
6615c446 JO |
1200 | |
1201 | case tcc_binary: | |
b89361c6 | 1202 | case tcc_comparison: |
7e6eb623 DB |
1203 | { |
1204 | tree oldop1 = TREE_OPERAND (expr, 0); | |
1205 | tree oldop2 = TREE_OPERAND (expr, 1); | |
1206 | tree newop1; | |
1207 | tree newop2; | |
1208 | tree newexpr; | |
1209 | ||
1210 | newop1 = phi_translate (find_leader (set, oldop1), | |
1211 | set, pred, phiblock); | |
1212 | if (newop1 == NULL) | |
1213 | return NULL; | |
1214 | newop2 = phi_translate (find_leader (set, oldop2), | |
1215 | set, pred, phiblock); | |
1216 | if (newop2 == NULL) | |
1217 | return NULL; | |
1218 | if (newop1 != oldop1 || newop2 != oldop2) | |
1219 | { | |
0995a441 | 1220 | tree t; |
e1111e8e | 1221 | newexpr = (tree) pool_alloc (binary_node_pool); |
7e6eb623 | 1222 | memcpy (newexpr, expr, tree_size (expr)); |
7e6eb623 DB |
1223 | TREE_OPERAND (newexpr, 0) = newop1 == oldop1 ? oldop1 : get_value_handle (newop1); |
1224 | TREE_OPERAND (newexpr, 1) = newop2 == oldop2 ? oldop2 : get_value_handle (newop2); | |
0995a441 SB |
1225 | t = fully_constant_expression (newexpr); |
1226 | if (t != newexpr) | |
1227 | { | |
1228 | pool_free (binary_node_pool, newexpr); | |
1229 | newexpr = t; | |
1230 | } | |
1231 | else | |
1232 | { | |
1233 | create_tree_ann (newexpr); | |
1234 | vn_lookup_or_add (newexpr, NULL); | |
1235 | } | |
7e6eb623 | 1236 | expr = newexpr; |
c90186eb | 1237 | phi_trans_add (oldexpr, newexpr, pred, NULL); |
7e6eb623 DB |
1238 | } |
1239 | } | |
6615c446 JO |
1240 | return expr; |
1241 | ||
1242 | case tcc_unary: | |
7e6eb623 DB |
1243 | { |
1244 | tree oldop1 = TREE_OPERAND (expr, 0); | |
1245 | tree newop1; | |
1246 | tree newexpr; | |
1247 | ||
1248 | newop1 = phi_translate (find_leader (set, oldop1), | |
1249 | set, pred, phiblock); | |
1250 | if (newop1 == NULL) | |
1251 | return NULL; | |
1252 | if (newop1 != oldop1) | |
1253 | { | |
0995a441 | 1254 | tree t; |
e1111e8e | 1255 | newexpr = (tree) pool_alloc (unary_node_pool); |
7e6eb623 | 1256 | memcpy (newexpr, expr, tree_size (expr)); |
7e6eb623 | 1257 | TREE_OPERAND (newexpr, 0) = get_value_handle (newop1); |
0995a441 SB |
1258 | t = fully_constant_expression (newexpr); |
1259 | if (t != newexpr) | |
1260 | { | |
1261 | pool_free (unary_node_pool, newexpr); | |
1262 | newexpr = t; | |
1263 | } | |
1264 | else | |
1265 | { | |
1266 | create_tree_ann (newexpr); | |
1267 | vn_lookup_or_add (newexpr, NULL); | |
1268 | } | |
7e6eb623 | 1269 | expr = newexpr; |
c90186eb | 1270 | phi_trans_add (oldexpr, newexpr, pred, NULL); |
7e6eb623 DB |
1271 | } |
1272 | } | |
6615c446 JO |
1273 | return expr; |
1274 | ||
1275 | case tcc_exceptional: | |
7e6eb623 DB |
1276 | { |
1277 | tree phi = NULL; | |
9323afae | 1278 | edge e; |
1e128c5f | 1279 | gcc_assert (TREE_CODE (expr) == SSA_NAME); |
7e6eb623 DB |
1280 | if (TREE_CODE (SSA_NAME_DEF_STMT (expr)) == PHI_NODE) |
1281 | phi = SSA_NAME_DEF_STMT (expr); | |
1282 | else | |
1283 | return expr; | |
1284 | ||
9323afae KH |
1285 | e = find_edge (pred, bb_for_stmt (phi)); |
1286 | if (e) | |
1287 | { | |
1288 | if (is_undefined_value (PHI_ARG_DEF (phi, e->dest_idx))) | |
1289 | return NULL; | |
1290 | vn_lookup_or_add (PHI_ARG_DEF (phi, e->dest_idx), NULL); | |
1291 | return PHI_ARG_DEF (phi, e->dest_idx); | |
1292 | } | |
7e6eb623 | 1293 | } |
6615c446 JO |
1294 | return expr; |
1295 | ||
1296 | default: | |
1297 | gcc_unreachable (); | |
6de9cd9a DN |
1298 | } |
1299 | } | |
1300 | ||
f5594471 DB |
1301 | /* For each expression in SET, translate the value handles through phi nodes |
1302 | in PHIBLOCK using edge PHIBLOCK->PRED, and store the resulting | |
1303 | expressions in DEST. */ | |
1304 | ||
6de9cd9a | 1305 | static void |
7e6eb623 DB |
1306 | phi_translate_set (value_set_t dest, value_set_t set, basic_block pred, |
1307 | basic_block phiblock) | |
6de9cd9a | 1308 | { |
7e6eb623 DB |
1309 | value_set_node_t node; |
1310 | for (node = set->head; | |
1311 | node; | |
1312 | node = node->next) | |
6de9cd9a | 1313 | { |
7e6eb623 | 1314 | tree translated; |
6de9cd9a | 1315 | |
c90186eb DB |
1316 | translated = phi_translate (node->expr, set, pred, phiblock); |
1317 | ||
1318 | /* Don't add constants or empty translations to the cache, since | |
1319 | we won't look them up that way, or use the result, anyway. */ | |
1320 | if (translated && !is_gimple_min_invariant (translated)) | |
1321 | { | |
1322 | tree vh = get_value_handle (translated); | |
1323 | VEC (tree, gc) *vuses; | |
1324 | ||
1325 | /* The value handle itself may also be an invariant, in | |
1326 | which case, it has no vuses. */ | |
1327 | vuses = !is_gimple_min_invariant (vh) | |
1328 | ? VALUE_HANDLE_VUSES (vh) : NULL; | |
1329 | phi_trans_add (node->expr, translated, pred, vuses); | |
1330 | } | |
1331 | ||
7e6eb623 DB |
1332 | if (translated != NULL) |
1333 | value_insert_into_set (dest, translated); | |
1334 | } | |
6de9cd9a DN |
1335 | } |
1336 | ||
bdee7684 DB |
1337 | /* Find the leader for a value (i.e., the name representing that |
1338 | value) in a given set, and return it. Return NULL if no leader is | |
1339 | found. */ | |
1340 | ||
1341 | static tree | |
1342 | bitmap_find_leader (bitmap_set_t set, tree val) | |
1343 | { | |
1344 | if (val == NULL) | |
1345 | return NULL; | |
1346 | ||
1347 | if (is_gimple_min_invariant (val)) | |
1348 | return val; | |
1349 | if (bitmap_set_contains_value (set, val)) | |
1350 | { | |
6b416da1 DB |
1351 | /* Rather than walk the entire bitmap of expressions, and see |
1352 | whether any of them has the value we are looking for, we look | |
1353 | at the reverse mapping, which tells us the set of expressions | |
1354 | that have a given value (IE value->expressions with that | |
1355 | value) and see if any of those expressions are in our set. | |
1356 | The number of expressions per value is usually significantly | |
1357 | less than the number of expressions in the set. In fact, for | |
1358 | large testcases, doing it this way is roughly 5-10x faster | |
1359 | than walking the bitmap. | |
1360 | If this is somehow a significant lose for some cases, we can | |
1361 | choose which set to walk based on which set is smaller. */ | |
1362 | value_set_t exprset; | |
1363 | value_set_node_t node; | |
1364 | exprset = VALUE_HANDLE_EXPR_SET (val); | |
1365 | for (node = exprset->head; node; node = node->next) | |
1366 | { | |
1367 | if (TREE_CODE (node->expr) == SSA_NAME) | |
1368 | { | |
1369 | if (bitmap_bit_p (set->expressions, | |
1370 | SSA_NAME_VERSION (node->expr))) | |
1371 | return node->expr; | |
1372 | } | |
1373 | } | |
bdee7684 DB |
1374 | } |
1375 | return NULL; | |
1376 | } | |
1377 | ||
1378 | ||
ff2ad0f7 | 1379 | /* Find the leader for a value (i.e., the name representing that |
7e6eb623 DB |
1380 | value) in a given set, and return it. Return NULL if no leader is |
1381 | found. */ | |
6de9cd9a | 1382 | |
7e6eb623 DB |
1383 | static tree |
1384 | find_leader (value_set_t set, tree val) | |
6de9cd9a | 1385 | { |
7e6eb623 | 1386 | value_set_node_t node; |
6de9cd9a | 1387 | |
7e6eb623 DB |
1388 | if (val == NULL) |
1389 | return NULL; | |
ff2ad0f7 | 1390 | |
bddeccfe DN |
1391 | /* Constants represent themselves. */ |
1392 | if (is_gimple_min_invariant (val)) | |
56db793a | 1393 | return val; |
ff2ad0f7 | 1394 | |
7e6eb623 DB |
1395 | if (set->length == 0) |
1396 | return NULL; | |
6de9cd9a | 1397 | |
7e6eb623 | 1398 | if (value_exists_in_set_bitmap (set, val)) |
6de9cd9a | 1399 | { |
7e6eb623 DB |
1400 | for (node = set->head; |
1401 | node; | |
1402 | node = node->next) | |
6de9cd9a | 1403 | { |
7e6eb623 DB |
1404 | if (get_value_handle (node->expr) == val) |
1405 | return node->expr; | |
6de9cd9a DN |
1406 | } |
1407 | } | |
ff2ad0f7 | 1408 | |
7e6eb623 | 1409 | return NULL; |
6de9cd9a DN |
1410 | } |
1411 | ||
c90186eb DB |
1412 | /* Given the vuse representative map, MAP, and an SSA version number, |
1413 | ID, return the bitmap of names ID represents, or NULL, if none | |
1414 | exists. */ | |
1415 | ||
1416 | static bitmap | |
1417 | get_representative (bitmap *map, int id) | |
1418 | { | |
1419 | if (map[id] != NULL) | |
1420 | return map[id]; | |
1421 | return NULL; | |
1422 | } | |
1423 | ||
1424 | /* A vuse is anticipable at the top of block x, from the bottom of the | |
1425 | block, if it reaches the top of the block, and is not killed in the | |
1426 | block. In effect, we are trying to see if the vuse is transparent | |
1427 | backwards in the block. */ | |
1428 | ||
1429 | static bool | |
1430 | vuses_dies_in_block_x (VEC (tree, gc) *vuses, basic_block block) | |
1431 | { | |
1432 | int i; | |
1433 | tree vuse; | |
1434 | ||
1435 | for (i = 0; VEC_iterate (tree, vuses, i, vuse); i++) | |
1436 | { | |
1437 | /* Any places where this is too conservative, are places | |
1438 | where we created a new version and shouldn't have. */ | |
1439 | ||
1440 | if (!bitmap_bit_p (RVUSE_IN (block), SSA_NAME_VERSION (vuse)) | |
1441 | || bitmap_bit_p (RVUSE_KILL (block), SSA_NAME_VERSION | |
1442 | (vuse))) | |
1443 | return true; | |
1444 | } | |
1445 | return false; | |
1446 | } | |
1447 | ||
7e6eb623 DB |
1448 | /* Determine if the expression EXPR is valid in SET. This means that |
1449 | we have a leader for each part of the expression (if it consists of | |
1450 | values), or the expression is an SSA_NAME. | |
6de9cd9a | 1451 | |
43da81be | 1452 | NB: We never should run into a case where we have SSA_NAME + |
7e6eb623 | 1453 | SSA_NAME or SSA_NAME + value. The sets valid_in_set is called on, |
43da81be DB |
1454 | the ANTIC sets, will only ever have SSA_NAME's or value expressions |
1455 | (IE VALUE1 + VALUE2, *VALUE1, VALUE1 < VALUE2) */ | |
6de9cd9a DN |
1456 | |
1457 | static bool | |
c90186eb | 1458 | valid_in_set (value_set_t set, tree expr, basic_block block) |
6de9cd9a | 1459 | { |
c90186eb DB |
1460 | tree vh = get_value_handle (expr); |
1461 | switch (TREE_CODE_CLASS (TREE_CODE (expr))) | |
7e6eb623 | 1462 | { |
6615c446 | 1463 | case tcc_binary: |
b89361c6 | 1464 | case tcc_comparison: |
6de9cd9a | 1465 | { |
7e6eb623 DB |
1466 | tree op1 = TREE_OPERAND (expr, 0); |
1467 | tree op2 = TREE_OPERAND (expr, 1); | |
1468 | return set_contains_value (set, op1) && set_contains_value (set, op2); | |
6de9cd9a | 1469 | } |
6615c446 JO |
1470 | |
1471 | case tcc_unary: | |
7e6eb623 DB |
1472 | { |
1473 | tree op1 = TREE_OPERAND (expr, 0); | |
1474 | return set_contains_value (set, op1); | |
1475 | } | |
43da81be DB |
1476 | |
1477 | case tcc_expression: | |
1478 | { | |
1479 | if (TREE_CODE (expr) == CALL_EXPR) | |
1480 | { | |
1481 | tree op0 = TREE_OPERAND (expr, 0); | |
1482 | tree arglist = TREE_OPERAND (expr, 1); | |
1483 | tree op2 = TREE_OPERAND (expr, 2); | |
6615c446 | 1484 | |
43da81be DB |
1485 | /* Check the non-list operands first. */ |
1486 | if (!set_contains_value (set, op0) | |
1487 | || (op2 && !set_contains_value (set, op2))) | |
1488 | return false; | |
1489 | ||
1490 | /* Now check the operands. */ | |
1491 | for (; arglist; arglist = TREE_CHAIN (arglist)) | |
1492 | { | |
1493 | if (!set_contains_value (set, TREE_VALUE (arglist))) | |
1494 | return false; | |
1495 | } | |
c90186eb | 1496 | return !vuses_dies_in_block_x (VALUE_HANDLE_VUSES (vh), block); |
43da81be DB |
1497 | } |
1498 | return false; | |
1499 | } | |
1500 | ||
6615c446 | 1501 | case tcc_reference: |
c90186eb DB |
1502 | { |
1503 | if (TREE_CODE (expr) == INDIRECT_REF) | |
1504 | { | |
1505 | tree op0 = TREE_OPERAND (expr, 0); | |
1506 | if (is_gimple_min_invariant (op0) | |
1507 | || TREE_CODE (op0) == VALUE_HANDLE) | |
1508 | { | |
1509 | bool retval = set_contains_value (set, op0); | |
1510 | if (retval) | |
1511 | return !vuses_dies_in_block_x (VALUE_HANDLE_VUSES (vh), | |
1512 | block); | |
1513 | return false; | |
1514 | } | |
1515 | } | |
1516 | } | |
6615c446 JO |
1517 | return false; |
1518 | ||
1519 | case tcc_exceptional: | |
1520 | gcc_assert (TREE_CODE (expr) == SSA_NAME); | |
1521 | return true; | |
1522 | ||
b89361c6 | 1523 | case tcc_declaration: |
c90186eb | 1524 | return !vuses_dies_in_block_x (VALUE_HANDLE_VUSES (vh), block); |
b89361c6 | 1525 | |
6615c446 JO |
1526 | default: |
1527 | /* No other cases should be encountered. */ | |
1528 | gcc_unreachable (); | |
1529 | } | |
6de9cd9a DN |
1530 | } |
1531 | ||
ca072a31 DB |
1532 | /* Clean the set of expressions that are no longer valid in SET. This |
1533 | means expressions that are made up of values we have no leaders for | |
1534 | in SET. */ | |
6de9cd9a DN |
1535 | |
1536 | static void | |
c90186eb | 1537 | clean (value_set_t set, basic_block block) |
6de9cd9a | 1538 | { |
7e6eb623 DB |
1539 | value_set_node_t node; |
1540 | value_set_node_t next; | |
1541 | node = set->head; | |
1542 | while (node) | |
6de9cd9a | 1543 | { |
7e6eb623 | 1544 | next = node->next; |
c90186eb | 1545 | if (!valid_in_set (set, node->expr, block)) |
7e6eb623 DB |
1546 | set_remove (set, node->expr); |
1547 | node = next; | |
6de9cd9a DN |
1548 | } |
1549 | } | |
1550 | ||
d4222d43 | 1551 | static sbitmap has_abnormal_preds; |
d6fd4b8d | 1552 | |
7e6eb623 | 1553 | /* Compute the ANTIC set for BLOCK. |
6de9cd9a | 1554 | |
665fcad8 SB |
1555 | If succs(BLOCK) > 1 then |
1556 | ANTIC_OUT[BLOCK] = intersection of ANTIC_IN[b] for all succ(BLOCK) | |
1557 | else if succs(BLOCK) == 1 then | |
1558 | ANTIC_OUT[BLOCK] = phi_translate (ANTIC_IN[succ(BLOCK)]) | |
6de9cd9a | 1559 | |
665fcad8 | 1560 | ANTIC_IN[BLOCK] = clean(ANTIC_OUT[BLOCK] U EXP_GEN[BLOCK] - TMP_GEN[BLOCK]) |
6de9cd9a | 1561 | |
665fcad8 SB |
1562 | XXX: It would be nice to either write a set_clear, and use it for |
1563 | ANTIC_OUT, or to mark the antic_out set as deleted at the end | |
1564 | of this routine, so that the pool can hand the same memory back out | |
1565 | again for the next ANTIC_OUT. */ | |
6de9cd9a | 1566 | |
7e6eb623 | 1567 | static bool |
a28fee03 | 1568 | compute_antic_aux (basic_block block, bool block_has_abnormal_pred_edge) |
6de9cd9a | 1569 | { |
c33bae88 | 1570 | basic_block son; |
7e6eb623 DB |
1571 | bool changed = false; |
1572 | value_set_t S, old, ANTIC_OUT; | |
1573 | value_set_node_t node; | |
a28fee03 | 1574 | |
7e6eb623 | 1575 | ANTIC_OUT = S = NULL; |
a28fee03 SB |
1576 | |
1577 | /* If any edges from predecessors are abnormal, antic_in is empty, | |
1578 | so do nothing. */ | |
1579 | if (block_has_abnormal_pred_edge) | |
1580 | goto maybe_dump_sets; | |
6de9cd9a | 1581 | |
7e6eb623 DB |
1582 | old = set_new (false); |
1583 | set_copy (old, ANTIC_IN (block)); | |
1584 | ANTIC_OUT = set_new (true); | |
6de9cd9a | 1585 | |
a28fee03 SB |
1586 | /* If the block has no successors, ANTIC_OUT is empty. */ |
1587 | if (EDGE_COUNT (block->succs) == 0) | |
1588 | ; | |
7e6eb623 DB |
1589 | /* If we have one successor, we could have some phi nodes to |
1590 | translate through. */ | |
c5cbcccf | 1591 | else if (single_succ_p (block)) |
6de9cd9a | 1592 | { |
43da81be | 1593 | phi_translate_set (ANTIC_OUT, ANTIC_IN (single_succ (block)), |
c5cbcccf | 1594 | block, single_succ (block)); |
6de9cd9a | 1595 | } |
7e6eb623 DB |
1596 | /* If we have multiple successors, we take the intersection of all of |
1597 | them. */ | |
1598 | else | |
6de9cd9a | 1599 | { |
d4e6fecb | 1600 | VEC(basic_block, heap) * worklist; |
7e6eb623 DB |
1601 | edge e; |
1602 | size_t i; | |
1603 | basic_block bprime, first; | |
628f6a4e | 1604 | edge_iterator ei; |
7e6eb623 | 1605 | |
d4e6fecb | 1606 | worklist = VEC_alloc (basic_block, heap, EDGE_COUNT (block->succs)); |
628f6a4e | 1607 | FOR_EACH_EDGE (e, ei, block->succs) |
d4e6fecb | 1608 | VEC_quick_push (basic_block, worklist, e->dest); |
d6fd4b8d | 1609 | first = VEC_index (basic_block, worklist, 0); |
7e6eb623 | 1610 | set_copy (ANTIC_OUT, ANTIC_IN (first)); |
6de9cd9a | 1611 | |
d6fd4b8d | 1612 | for (i = 1; VEC_iterate (basic_block, worklist, i, bprime); i++) |
6de9cd9a | 1613 | { |
7e6eb623 DB |
1614 | node = ANTIC_OUT->head; |
1615 | while (node) | |
6de9cd9a | 1616 | { |
7e6eb623 DB |
1617 | tree val; |
1618 | value_set_node_t next = node->next; | |
c90186eb | 1619 | |
7e6eb623 DB |
1620 | val = get_value_handle (node->expr); |
1621 | if (!set_contains_value (ANTIC_IN (bprime), val)) | |
1622 | set_remove (ANTIC_OUT, node->expr); | |
1623 | node = next; | |
6de9cd9a | 1624 | } |
6de9cd9a | 1625 | } |
d4e6fecb | 1626 | VEC_free (basic_block, heap, worklist); |
6de9cd9a | 1627 | } |
6de9cd9a | 1628 | |
ea4b7848 | 1629 | /* Generate ANTIC_OUT - TMP_GEN. */ |
6b416da1 | 1630 | S = bitmap_set_subtract_from_value_set (ANTIC_OUT, TMP_GEN (block), false); |
6de9cd9a | 1631 | |
7e6eb623 | 1632 | /* Start ANTIC_IN with EXP_GEN - TMP_GEN */ |
6b416da1 DB |
1633 | ANTIC_IN (block) = bitmap_set_subtract_from_value_set (EXP_GEN (block), |
1634 | TMP_GEN (block), | |
1635 | true); | |
c33bae88 | 1636 | |
a28fee03 SB |
1637 | /* Then union in the ANTIC_OUT - TMP_GEN values, |
1638 | to get ANTIC_OUT U EXP_GEN - TMP_GEN */ | |
1639 | for (node = S->head; node; node = node->next) | |
1640 | value_insert_into_set (ANTIC_IN (block), node->expr); | |
6de9cd9a | 1641 | |
c90186eb | 1642 | clean (ANTIC_IN (block), block); |
7e6eb623 DB |
1643 | if (!set_equal (old, ANTIC_IN (block))) |
1644 | changed = true; | |
6de9cd9a | 1645 | |
a28fee03 | 1646 | maybe_dump_sets: |
7e6eb623 DB |
1647 | if (dump_file && (dump_flags & TDF_DETAILS)) |
1648 | { | |
1649 | if (ANTIC_OUT) | |
1650 | print_value_set (dump_file, ANTIC_OUT, "ANTIC_OUT", block->index); | |
1651 | print_value_set (dump_file, ANTIC_IN (block), "ANTIC_IN", block->index); | |
1652 | if (S) | |
1653 | print_value_set (dump_file, S, "S", block->index); | |
7e6eb623 | 1654 | } |
6de9cd9a | 1655 | |
c33bae88 SB |
1656 | for (son = first_dom_son (CDI_POST_DOMINATORS, block); |
1657 | son; | |
1658 | son = next_dom_son (CDI_POST_DOMINATORS, son)) | |
1659 | { | |
1660 | changed |= compute_antic_aux (son, | |
1661 | TEST_BIT (has_abnormal_preds, son->index)); | |
1662 | } | |
7e6eb623 | 1663 | return changed; |
6de9cd9a DN |
1664 | } |
1665 | ||
c33bae88 | 1666 | /* Compute ANTIC sets. */ |
6de9cd9a DN |
1667 | |
1668 | static void | |
7e6eb623 | 1669 | compute_antic (void) |
6de9cd9a | 1670 | { |
c33bae88 | 1671 | bool changed = true; |
7e6eb623 | 1672 | int num_iterations = 0; |
c33bae88 | 1673 | basic_block block; |
a28fee03 SB |
1674 | |
1675 | /* If any predecessor edges are abnormal, we punt, so antic_in is empty. | |
1676 | We pre-build the map of blocks with incoming abnormal edges here. */ | |
1677 | has_abnormal_preds = sbitmap_alloc (last_basic_block); | |
1678 | sbitmap_zero (has_abnormal_preds); | |
1679 | FOR_EACH_BB (block) | |
7e6eb623 | 1680 | { |
a28fee03 SB |
1681 | edge_iterator ei; |
1682 | edge e; | |
1683 | ||
1684 | FOR_EACH_EDGE (e, ei, block->preds) | |
c33bae88 SB |
1685 | if (e->flags & EDGE_ABNORMAL) |
1686 | { | |
1687 | SET_BIT (has_abnormal_preds, block->index); | |
1688 | break; | |
1689 | } | |
a28fee03 SB |
1690 | |
1691 | /* While we are here, give empty ANTIC_IN sets to each block. */ | |
1692 | ANTIC_IN (block) = set_new (true); | |
7e6eb623 | 1693 | } |
a28fee03 SB |
1694 | /* At the exit block we anticipate nothing. */ |
1695 | ANTIC_IN (EXIT_BLOCK_PTR) = set_new (true); | |
1696 | ||
7e6eb623 DB |
1697 | while (changed) |
1698 | { | |
a28fee03 | 1699 | num_iterations++; |
c33bae88 SB |
1700 | changed = false; |
1701 | changed = compute_antic_aux (EXIT_BLOCK_PTR, false); | |
2e24fa83 | 1702 | } |
a28fee03 | 1703 | |
a28fee03 SB |
1704 | sbitmap_free (has_abnormal_preds); |
1705 | ||
1706 | if (dump_file && (dump_flags & TDF_STATS)) | |
7e6eb623 | 1707 | fprintf (dump_file, "compute_antic required %d iterations\n", num_iterations); |
6de9cd9a DN |
1708 | } |
1709 | ||
c90186eb DB |
1710 | /* Print the names represented by the bitmap NAMES, to the file OUT. */ |
1711 | static void | |
1712 | dump_bitmap_of_names (FILE *out, bitmap names) | |
1713 | { | |
1714 | bitmap_iterator bi; | |
1715 | unsigned int i; | |
1716 | ||
1717 | fprintf (out, " { "); | |
1718 | EXECUTE_IF_SET_IN_BITMAP (names, 0, i, bi) | |
1719 | { | |
1720 | print_generic_expr (out, ssa_name (i), 0); | |
1721 | fprintf (out, " "); | |
1722 | } | |
1723 | fprintf (out, "}\n"); | |
1724 | } | |
1725 | ||
1726 | /* Compute a set of representative vuse versions for each phi. This | |
1727 | is so we can compute conservative kill sets in terms of all vuses | |
1728 | that are killed, instead of continually walking chains. | |
1729 | ||
1730 | We also have to be able kill all names associated with a phi when | |
1731 | the phi dies in order to ensure we don't generate overlapping | |
1732 | live ranges, which are not allowed in virtual SSA. */ | |
1733 | ||
1734 | static bitmap *vuse_names; | |
1735 | static void | |
1736 | compute_vuse_representatives (void) | |
1737 | { | |
1738 | tree phi; | |
1739 | basic_block bb; | |
1740 | VEC (tree, heap) *phis = NULL; | |
1741 | bool changed = true; | |
1742 | size_t i; | |
1743 | ||
1744 | FOR_EACH_BB (bb) | |
1745 | { | |
1746 | for (phi = phi_nodes (bb); | |
1747 | phi; | |
1748 | phi = PHI_CHAIN (phi)) | |
1749 | if (!is_gimple_reg (PHI_RESULT (phi))) | |
1750 | VEC_safe_push (tree, heap, phis, phi); | |
1751 | } | |
1752 | ||
1753 | while (changed) | |
1754 | { | |
1755 | changed = false; | |
1756 | ||
1757 | for (i = 0; VEC_iterate (tree, phis, i, phi); i++) | |
1758 | { | |
1759 | size_t ver = SSA_NAME_VERSION (PHI_RESULT (phi)); | |
1760 | use_operand_p usep; | |
1761 | ssa_op_iter iter; | |
1762 | ||
1763 | if (vuse_names[ver] == NULL) | |
1764 | { | |
1765 | vuse_names[ver] = BITMAP_ALLOC (&grand_bitmap_obstack); | |
1766 | bitmap_set_bit (vuse_names[ver], ver); | |
1767 | } | |
1768 | FOR_EACH_PHI_ARG (usep, phi, iter, SSA_OP_ALL_USES) | |
1769 | { | |
1770 | tree use = USE_FROM_PTR (usep); | |
1771 | bitmap usebitmap = get_representative (vuse_names, | |
1772 | SSA_NAME_VERSION (use)); | |
1773 | if (usebitmap != NULL) | |
1774 | { | |
1775 | changed |= bitmap_ior_into (vuse_names[ver], | |
1776 | usebitmap); | |
1777 | } | |
1778 | else | |
1779 | { | |
1780 | changed |= !bitmap_bit_p (vuse_names[ver], | |
1781 | SSA_NAME_VERSION (use)); | |
1782 | if (changed) | |
1783 | bitmap_set_bit (vuse_names[ver], | |
1784 | SSA_NAME_VERSION (use)); | |
1785 | } | |
1786 | } | |
1787 | } | |
1788 | } | |
1789 | ||
1790 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
1791 | for (i = 0; VEC_iterate (tree, phis, i, phi); i++) | |
1792 | { | |
1793 | bitmap reps = get_representative (vuse_names, | |
1794 | SSA_NAME_VERSION (PHI_RESULT (phi))); | |
1795 | if (reps) | |
1796 | { | |
1797 | print_generic_expr (dump_file, PHI_RESULT (phi), 0); | |
1798 | fprintf (dump_file, " represents "); | |
1799 | dump_bitmap_of_names (dump_file, reps); | |
1800 | } | |
1801 | } | |
1802 | VEC_free (tree, heap, phis); | |
1803 | } | |
1804 | ||
1805 | /* Compute reaching vuses. This is a small bit of iterative dataflow | |
1806 | to determine what virtual uses reach what blocks. Because we can't | |
1807 | generate overlapping virtual uses, and virtual uses *do* actually | |
1808 | die, this ends up being faster in most cases than continually | |
1809 | walking the virtual use/def chains to determine whether we are | |
1810 | inside a block where a given virtual is still available to be | |
1811 | used. */ | |
1812 | ||
1813 | static void | |
1814 | compute_rvuse (void) | |
1815 | { | |
1816 | ||
1817 | size_t i; | |
1818 | tree phi; | |
1819 | basic_block bb; | |
1820 | int *postorder; | |
1821 | bool changed = true; | |
1822 | ||
1823 | compute_vuse_representatives (); | |
1824 | ||
1825 | FOR_ALL_BB (bb) | |
1826 | { | |
1827 | RVUSE_IN (bb) = BITMAP_ALLOC (&grand_bitmap_obstack); | |
1828 | RVUSE_GEN (bb) = BITMAP_ALLOC (&grand_bitmap_obstack); | |
1829 | RVUSE_KILL (bb) = BITMAP_ALLOC (&grand_bitmap_obstack); | |
1830 | RVUSE_OUT (bb) = BITMAP_ALLOC (&grand_bitmap_obstack); | |
1831 | } | |
1832 | ||
1833 | ||
1834 | /* Mark live on entry */ | |
1835 | for (i = 0; i < num_ssa_names; i++) | |
1836 | { | |
1837 | tree name = ssa_name (i); | |
1838 | if (name && !is_gimple_reg (name) | |
1839 | && IS_EMPTY_STMT (SSA_NAME_DEF_STMT (name))) | |
1840 | bitmap_set_bit (RVUSE_OUT (ENTRY_BLOCK_PTR), | |
1841 | SSA_NAME_VERSION (name)); | |
1842 | } | |
1843 | ||
1844 | /* Compute local sets for reaching vuses. | |
1845 | GEN(block) = generated in block and not locally killed. | |
1846 | KILL(block) = set of vuses killed in block. | |
1847 | */ | |
1848 | ||
1849 | FOR_EACH_BB (bb) | |
1850 | { | |
1851 | block_stmt_iterator bsi; | |
1852 | ssa_op_iter iter; | |
1853 | def_operand_p defp; | |
1854 | use_operand_p usep; | |
1855 | ||
1856 | ||
1857 | for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) | |
1858 | { | |
1859 | tree stmt = bsi_stmt (bsi); | |
1860 | FOR_EACH_SSA_USE_OPERAND (usep, stmt, iter, SSA_OP_VIRTUAL_KILLS | |
1861 | | SSA_OP_VMAYUSE) | |
1862 | { | |
1863 | tree use = USE_FROM_PTR (usep); | |
1864 | bitmap repbit = get_representative (vuse_names, | |
1865 | SSA_NAME_VERSION (use)); | |
1866 | if (repbit != NULL) | |
1867 | { | |
1868 | bitmap_and_compl_into (RVUSE_GEN (bb), repbit); | |
1869 | bitmap_ior_into (RVUSE_KILL (bb), repbit); | |
1870 | } | |
1871 | else | |
1872 | { | |
1873 | bitmap_set_bit (RVUSE_KILL (bb), SSA_NAME_VERSION (use)); | |
1874 | bitmap_clear_bit (RVUSE_GEN (bb), SSA_NAME_VERSION (use)); | |
1875 | } | |
1876 | } | |
1877 | FOR_EACH_SSA_DEF_OPERAND (defp, stmt, iter, SSA_OP_VIRTUAL_DEFS) | |
1878 | { | |
1879 | tree def = DEF_FROM_PTR (defp); | |
1880 | bitmap_set_bit (RVUSE_GEN (bb), SSA_NAME_VERSION (def)); | |
1881 | } | |
1882 | } | |
1883 | } | |
1884 | ||
1885 | FOR_EACH_BB (bb) | |
1886 | { | |
1887 | for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) | |
1888 | { | |
1889 | if (!is_gimple_reg (PHI_RESULT (phi))) | |
1890 | { | |
1891 | edge e; | |
1892 | edge_iterator ei; | |
1893 | ||
1894 | tree def = PHI_RESULT (phi); | |
1895 | /* In reality, the PHI result is generated at the end of | |
1896 | each predecessor block. This will make the value | |
1897 | LVUSE_IN for the bb containing the PHI, which is | |
1898 | correct. */ | |
1899 | FOR_EACH_EDGE (e, ei, bb->preds) | |
1900 | bitmap_set_bit (RVUSE_GEN (e->src), SSA_NAME_VERSION (def)); | |
1901 | } | |
1902 | } | |
1903 | } | |
1904 | ||
1905 | /* Solve reaching vuses. | |
1906 | ||
1907 | RVUSE_IN[BB] = Union of RVUSE_OUT of predecessors. | |
1908 | RVUSE_OUT[BB] = RVUSE_GEN[BB] U (RVUSE_IN[BB] - RVUSE_KILL[BB]) | |
1909 | */ | |
1910 | postorder = xmalloc (sizeof (int) * (n_basic_blocks - NUM_FIXED_BLOCKS)); | |
1911 | pre_and_rev_post_order_compute (NULL, postorder, false); | |
1912 | ||
1913 | changed = true; | |
1914 | while (changed) | |
1915 | { | |
1916 | int j; | |
1917 | changed = false; | |
1918 | for (j = 0; j < n_basic_blocks - NUM_FIXED_BLOCKS; j++) | |
1919 | { | |
1920 | edge e; | |
1921 | edge_iterator ei; | |
1922 | bb = BASIC_BLOCK (postorder[j]); | |
1923 | ||
1924 | FOR_EACH_EDGE (e, ei, bb->preds) | |
1925 | bitmap_ior_into (RVUSE_IN (bb), RVUSE_OUT (e->src)); | |
1926 | ||
1927 | changed |= bitmap_ior_and_compl (RVUSE_OUT (bb), | |
1928 | RVUSE_GEN (bb), | |
1929 | RVUSE_IN (bb), | |
1930 | RVUSE_KILL (bb)); | |
1931 | } | |
1932 | } | |
1933 | free (postorder); | |
1934 | ||
1935 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
1936 | { | |
1937 | FOR_ALL_BB (bb) | |
1938 | { | |
1939 | fprintf (dump_file, "RVUSE_IN (%d) =", bb->index); | |
1940 | dump_bitmap_of_names (dump_file, RVUSE_IN (bb)); | |
1941 | ||
1942 | fprintf (dump_file, "RVUSE_KILL (%d) =", bb->index); | |
1943 | dump_bitmap_of_names (dump_file, RVUSE_KILL (bb)); | |
1944 | ||
1945 | fprintf (dump_file, "RVUSE_GEN (%d) =", bb->index); | |
1946 | dump_bitmap_of_names (dump_file, RVUSE_GEN (bb)); | |
1947 | ||
1948 | fprintf (dump_file, "RVUSE_OUT (%d) =", bb->index); | |
1949 | dump_bitmap_of_names (dump_file, RVUSE_OUT (bb)); | |
1950 | } | |
1951 | } | |
1952 | } | |
1953 | ||
1954 | /* Return true if we can value number the call in STMT. This is true | |
1955 | if we have a pure or constant call. */ | |
1956 | ||
1957 | static bool | |
1958 | can_value_number_call (tree stmt) | |
1959 | { | |
1960 | tree call = get_call_expr_in (stmt); | |
1961 | ||
1962 | if (call_expr_flags (call) & (ECF_PURE | ECF_CONST)) | |
1963 | return true; | |
1964 | return false; | |
1965 | } | |
1966 | ||
1967 | /* Return true if OP is a tree which we can perform value numbering | |
1968 | on. */ | |
1969 | ||
1970 | static bool | |
1971 | can_value_number_operation (tree op) | |
1972 | { | |
1973 | return UNARY_CLASS_P (op) | |
1974 | || BINARY_CLASS_P (op) | |
1975 | || COMPARISON_CLASS_P (op) | |
1976 | || REFERENCE_CLASS_P (op) | |
1977 | || (TREE_CODE (op) == CALL_EXPR | |
1978 | && can_value_number_call (op)); | |
1979 | } | |
1980 | ||
1981 | ||
1982 | /* Return true if OP is a tree which we can perform PRE on | |
1983 | on. This may not match the operations we can value number, but in | |
1984 | a perfect world would. */ | |
1985 | ||
1986 | static bool | |
1987 | can_PRE_operation (tree op) | |
1988 | { | |
1989 | return UNARY_CLASS_P (op) | |
1990 | || BINARY_CLASS_P (op) | |
1991 | || COMPARISON_CLASS_P (op) | |
1992 | || TREE_CODE (op) == INDIRECT_REF | |
1993 | || TREE_CODE (op) == CALL_EXPR; | |
1994 | } | |
1995 | ||
1996 | ||
1997 | /* Inserted expressions are placed onto this worklist, which is used | |
1998 | for performing quick dead code elimination of insertions we made | |
1999 | that didn't turn out to be necessary. */ | |
d4e6fecb | 2000 | static VEC(tree,heap) *inserted_exprs; |
c90186eb DB |
2001 | |
2002 | /* Pool allocated fake store expressions are placed onto this | |
2003 | worklist, which, after performing dead code elimination, is walked | |
2004 | to see which expressions need to be put into GC'able memory */ | |
2005 | static VEC(tree, heap) *need_creation; | |
2006 | ||
2007 | ||
56db793a DB |
2008 | /* Find a leader for an expression, or generate one using |
2009 | create_expression_by_pieces if it's ANTIC but | |
2010 | complex. | |
2011 | BLOCK is the basic_block we are looking for leaders in. | |
2012 | EXPR is the expression to find a leader or generate for. | |
2013 | STMTS is the statement list to put the inserted expressions on. | |
2014 | Returns the SSA_NAME of the LHS of the generated expression or the | |
2015 | leader. */ | |
2016 | ||
2017 | static tree | |
2018 | find_or_generate_expression (basic_block block, tree expr, tree stmts) | |
2019 | { | |
e9284566 DB |
2020 | tree genop = bitmap_find_leader (AVAIL_OUT (block), expr); |
2021 | ||
0e61db61 NS |
2022 | /* If it's still NULL, it must be a complex expression, so generate |
2023 | it recursively. */ | |
56db793a DB |
2024 | if (genop == NULL) |
2025 | { | |
33c94679 | 2026 | genop = VALUE_HANDLE_EXPR_SET (expr)->head->expr; |
c90186eb DB |
2027 | |
2028 | gcc_assert (can_PRE_operation (genop)); | |
56db793a DB |
2029 | genop = create_expression_by_pieces (block, genop, stmts); |
2030 | } | |
2031 | return genop; | |
2032 | } | |
2033 | ||
0fc6c492 | 2034 | #define NECESSARY(stmt) stmt->common.asm_written_flag |
56db793a DB |
2035 | /* Create an expression in pieces, so that we can handle very complex |
2036 | expressions that may be ANTIC, but not necessary GIMPLE. | |
2037 | BLOCK is the basic block the expression will be inserted into, | |
2038 | EXPR is the expression to insert (in value form) | |
2039 | STMTS is a statement list to append the necessary insertions into. | |
2040 | ||
0e61db61 | 2041 | This function will die if we hit some value that shouldn't be |
56db793a DB |
2042 | ANTIC but is (IE there is no leader for it, or its components). |
2043 | This function may also generate expressions that are themselves | |
2044 | partially or fully redundant. Those that are will be either made | |
2045 | fully redundant during the next iteration of insert (for partially | |
2046 | redundant ones), or eliminated by eliminate (for fully redundant | |
2047 | ones). */ | |
2048 | ||
2049 | static tree | |
2050 | create_expression_by_pieces (basic_block block, tree expr, tree stmts) | |
2051 | { | |
81c4f554 SB |
2052 | tree temp, name; |
2053 | tree folded, forced_stmts, newexpr; | |
56db793a | 2054 | tree v; |
81c4f554 SB |
2055 | tree_stmt_iterator tsi; |
2056 | ||
56db793a DB |
2057 | switch (TREE_CODE_CLASS (TREE_CODE (expr))) |
2058 | { | |
43da81be DB |
2059 | case tcc_expression: |
2060 | { | |
2061 | tree op0, op2; | |
2062 | tree arglist; | |
2063 | tree genop0, genop2; | |
2064 | tree genarglist; | |
2065 | tree walker, genwalker; | |
2066 | ||
2067 | gcc_assert (TREE_CODE (expr) == CALL_EXPR); | |
2068 | genop2 = NULL; | |
2069 | ||
2070 | op0 = TREE_OPERAND (expr, 0); | |
2071 | arglist = TREE_OPERAND (expr, 1); | |
2072 | op2 = TREE_OPERAND (expr, 2); | |
2073 | ||
2074 | genop0 = find_or_generate_expression (block, op0, stmts); | |
2075 | genarglist = copy_list (arglist); | |
2076 | for (walker = arglist, genwalker = genarglist; | |
2077 | genwalker && walker; | |
2078 | genwalker = TREE_CHAIN (genwalker), walker = TREE_CHAIN (walker)) | |
2079 | { | |
c90186eb DB |
2080 | TREE_VALUE (genwalker) |
2081 | = find_or_generate_expression (block, TREE_VALUE (walker), | |
2082 | stmts); | |
43da81be DB |
2083 | } |
2084 | ||
2085 | if (op2) | |
2086 | genop2 = find_or_generate_expression (block, op2, stmts); | |
987b67bc KH |
2087 | folded = fold_build3 (TREE_CODE (expr), TREE_TYPE (expr), |
2088 | genop0, genarglist, genop2); | |
43da81be DB |
2089 | break; |
2090 | ||
2091 | ||
2092 | } | |
2093 | break; | |
c90186eb DB |
2094 | case tcc_reference: |
2095 | gcc_assert (TREE_CODE (expr) == INDIRECT_REF); | |
2096 | { | |
2097 | tree op1 = TREE_OPERAND (expr, 0); | |
2098 | tree genop1 = find_or_generate_expression (block, op1, stmts); | |
2099 | ||
2100 | folded = fold_build1 (TREE_CODE (expr), TREE_TYPE (expr), | |
2101 | genop1); | |
2102 | break; | |
2103 | } | |
43da81be | 2104 | |
6615c446 | 2105 | case tcc_binary: |
b89361c6 | 2106 | case tcc_comparison: |
56db793a | 2107 | { |
56db793a DB |
2108 | tree op1 = TREE_OPERAND (expr, 0); |
2109 | tree op2 = TREE_OPERAND (expr, 1); | |
81c4f554 SB |
2110 | tree genop1 = find_or_generate_expression (block, op1, stmts); |
2111 | tree genop2 = find_or_generate_expression (block, op2, stmts); | |
987b67bc KH |
2112 | folded = fold_build2 (TREE_CODE (expr), TREE_TYPE (expr), |
2113 | genop1, genop2); | |
56db793a DB |
2114 | break; |
2115 | } | |
81c4f554 | 2116 | |
6615c446 | 2117 | case tcc_unary: |
56db793a | 2118 | { |
56db793a | 2119 | tree op1 = TREE_OPERAND (expr, 0); |
81c4f554 | 2120 | tree genop1 = find_or_generate_expression (block, op1, stmts); |
987b67bc KH |
2121 | folded = fold_build1 (TREE_CODE (expr), TREE_TYPE (expr), |
2122 | genop1); | |
56db793a DB |
2123 | break; |
2124 | } | |
81c4f554 | 2125 | |
56db793a | 2126 | default: |
1e128c5f | 2127 | gcc_unreachable (); |
56db793a | 2128 | } |
e9284566 | 2129 | |
81c4f554 SB |
2130 | /* Force the generated expression to be a sequence of GIMPLE |
2131 | statements. | |
2132 | We have to call unshare_expr because force_gimple_operand may | |
2133 | modify the tree we pass to it. */ | |
2134 | newexpr = force_gimple_operand (unshare_expr (folded), &forced_stmts, | |
2135 | false, NULL); | |
2136 | ||
2137 | /* If we have any intermediate expressions to the value sets, add them | |
2138 | to the value sets and chain them on in the instruction stream. */ | |
2139 | if (forced_stmts) | |
2140 | { | |
2141 | tsi = tsi_start (forced_stmts); | |
2142 | for (; !tsi_end_p (tsi); tsi_next (&tsi)) | |
2143 | { | |
2144 | tree stmt = tsi_stmt (tsi); | |
2145 | tree forcedname = TREE_OPERAND (stmt, 0); | |
2146 | tree forcedexpr = TREE_OPERAND (stmt, 1); | |
2147 | tree val = vn_lookup_or_add (forcedexpr, NULL); | |
7cc70b5e DB |
2148 | |
2149 | VEC_safe_push (tree, heap, inserted_exprs, stmt); | |
c90186eb | 2150 | vn_add (forcedname, val); |
81c4f554 SB |
2151 | bitmap_value_replace_in_set (NEW_SETS (block), forcedname); |
2152 | bitmap_value_replace_in_set (AVAIL_OUT (block), forcedname); | |
c90186eb DB |
2153 | update_stmt (stmt); |
2154 | mark_new_vars_to_rename (tsi_stmt (tsi)); | |
81c4f554 SB |
2155 | } |
2156 | tsi = tsi_last (stmts); | |
2157 | tsi_link_after (&tsi, forced_stmts, TSI_CONTINUE_LINKING); | |
2158 | } | |
2159 | ||
2160 | /* Build and insert the assignment of the end result to the temporary | |
2161 | that we will return. */ | |
c90186eb DB |
2162 | if (!pretemp || TREE_TYPE (expr) != TREE_TYPE (pretemp)) |
2163 | { | |
2164 | pretemp = create_tmp_var (TREE_TYPE (expr), "pretmp"); | |
2165 | get_var_ann (pretemp); | |
2166 | } | |
2167 | ||
2168 | temp = pretemp; | |
81c4f554 | 2169 | add_referenced_tmp_var (temp); |
c90186eb | 2170 | |
aad97b9b RH |
2171 | if (TREE_CODE (TREE_TYPE (expr)) == COMPLEX_TYPE) |
2172 | DECL_COMPLEX_GIMPLE_REG_P (temp) = 1; | |
c90186eb | 2173 | |
b4257cfc | 2174 | newexpr = build2 (MODIFY_EXPR, TREE_TYPE (expr), temp, newexpr); |
81c4f554 SB |
2175 | name = make_ssa_name (temp, newexpr); |
2176 | TREE_OPERAND (newexpr, 0) = name; | |
2177 | NECESSARY (newexpr) = 0; | |
c90186eb | 2178 | |
81c4f554 SB |
2179 | tsi = tsi_last (stmts); |
2180 | tsi_link_after (&tsi, newexpr, TSI_CONTINUE_LINKING); | |
2181 | VEC_safe_push (tree, heap, inserted_exprs, newexpr); | |
c90186eb DB |
2182 | update_stmt (newexpr); |
2183 | mark_new_vars_to_rename (newexpr); | |
81c4f554 | 2184 | |
a1c8251a | 2185 | /* Add a value handle to the temporary. |
81c4f554 | 2186 | The value may already exist in either NEW_SETS, or AVAIL_OUT, because |
e9284566 DB |
2187 | we are creating the expression by pieces, and this particular piece of |
2188 | the expression may have been represented. There is no harm in replacing | |
2189 | here. */ | |
81c4f554 | 2190 | v = get_value_handle (expr); |
c90186eb | 2191 | vn_add (name, v); |
e9284566 DB |
2192 | bitmap_value_replace_in_set (NEW_SETS (block), name); |
2193 | bitmap_value_replace_in_set (AVAIL_OUT (block), name); | |
81c4f554 SB |
2194 | |
2195 | pre_stats.insertions++; | |
56db793a DB |
2196 | if (dump_file && (dump_flags & TDF_DETAILS)) |
2197 | { | |
2198 | fprintf (dump_file, "Inserted "); | |
2199 | print_generic_expr (dump_file, newexpr, 0); | |
2200 | fprintf (dump_file, " in predecessor %d\n", block->index); | |
2201 | } | |
81c4f554 | 2202 | |
56db793a DB |
2203 | return name; |
2204 | } | |
e9284566 | 2205 | |
c90186eb DB |
2206 | /* Insert the to-be-made-available values of NODE for each |
2207 | predecessor, stored in AVAIL, into the predecessors of BLOCK, and | |
2208 | merge the result with a phi node, given the same value handle as | |
2209 | NODE. Return true if we have inserted new stuff. */ | |
e9284566 DB |
2210 | |
2211 | static bool | |
2212 | insert_into_preds_of_block (basic_block block, value_set_node_t node, | |
c90186eb | 2213 | tree *avail) |
e9284566 DB |
2214 | { |
2215 | tree val = get_value_handle (node->expr); | |
2216 | edge pred; | |
0fc6c492 DB |
2217 | bool insertions = false; |
2218 | bool nophi = false; | |
e9284566 DB |
2219 | basic_block bprime; |
2220 | tree eprime; | |
2221 | edge_iterator ei; | |
2222 | tree type = TREE_TYPE (avail[EDGE_PRED (block, 0)->src->index]); | |
2223 | tree temp; | |
2224 | ||
2225 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
2226 | { | |
2227 | fprintf (dump_file, "Found partial redundancy for expression "); | |
2228 | print_generic_expr (dump_file, node->expr, 0); | |
c90186eb DB |
2229 | fprintf (dump_file, " ("); |
2230 | print_generic_expr (dump_file, val, 0); | |
2231 | fprintf (dump_file, ")"); | |
e9284566 DB |
2232 | fprintf (dump_file, "\n"); |
2233 | } | |
2234 | ||
0fc6c492 | 2235 | /* Make sure we aren't creating an induction variable. */ |
c90186eb DB |
2236 | if (block->loop_depth > 0 && EDGE_COUNT (block->preds) == 2 |
2237 | && TREE_CODE_CLASS (TREE_CODE (node->expr)) != tcc_reference ) | |
0fc6c492 DB |
2238 | { |
2239 | bool firstinsideloop = false; | |
2240 | bool secondinsideloop = false; | |
2241 | firstinsideloop = flow_bb_inside_loop_p (block->loop_father, | |
2242 | EDGE_PRED (block, 0)->src); | |
2243 | secondinsideloop = flow_bb_inside_loop_p (block->loop_father, | |
2244 | EDGE_PRED (block, 1)->src); | |
2245 | /* Induction variables only have one edge inside the loop. */ | |
2246 | if (firstinsideloop ^ secondinsideloop) | |
2247 | { | |
2248 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
2249 | fprintf (dump_file, "Skipping insertion of phi for partial redundancy: Looks like an induction variable\n"); | |
2250 | nophi = true; | |
2251 | } | |
2252 | } | |
2253 | ||
2254 | ||
e9284566 DB |
2255 | /* Make the necessary insertions. */ |
2256 | FOR_EACH_EDGE (pred, ei, block->preds) | |
2257 | { | |
2258 | tree stmts = alloc_stmt_list (); | |
2259 | tree builtexpr; | |
2260 | bprime = pred->src; | |
2261 | eprime = avail[bprime->index]; | |
c90186eb DB |
2262 | |
2263 | if (can_PRE_operation (eprime)) | |
e9284566 | 2264 | { |
c90186eb DB |
2265 | #ifdef ENABLE_CHECKING |
2266 | tree vh; | |
2267 | ||
2268 | /* eprime may be an invariant. */ | |
2269 | vh = TREE_CODE (eprime) == VALUE_HANDLE | |
2270 | ? eprime | |
2271 | : get_value_handle (eprime); | |
2272 | ||
2273 | /* ensure that the virtual uses we need reach our block. */ | |
2274 | if (TREE_CODE (vh) == VALUE_HANDLE) | |
2275 | { | |
2276 | int i; | |
2277 | tree vuse; | |
2278 | for (i = 0; | |
2279 | VEC_iterate (tree, VALUE_HANDLE_VUSES (vh), i, vuse); | |
2280 | i++) | |
2281 | { | |
2282 | size_t id = SSA_NAME_VERSION (vuse); | |
2283 | gcc_assert (bitmap_bit_p (RVUSE_OUT (bprime), id) | |
2284 | || IS_EMPTY_STMT (SSA_NAME_DEF_STMT (vuse))); | |
2285 | } | |
2286 | } | |
2287 | #endif | |
e9284566 DB |
2288 | builtexpr = create_expression_by_pieces (bprime, |
2289 | eprime, | |
2290 | stmts); | |
2291 | bsi_insert_on_edge (pred, stmts); | |
2292 | avail[bprime->index] = builtexpr; | |
0fc6c492 | 2293 | insertions = true; |
e9284566 DB |
2294 | } |
2295 | } | |
0fc6c492 DB |
2296 | /* If we didn't want a phi node, and we made insertions, we still have |
2297 | inserted new stuff, and thus return true. If we didn't want a phi node, | |
2298 | and didn't make insertions, we haven't added anything new, so return | |
2299 | false. */ | |
2300 | if (nophi && insertions) | |
2301 | return true; | |
2302 | else if (nophi && !insertions) | |
2303 | return false; | |
2304 | ||
e9284566 | 2305 | /* Now build a phi for the new variable. */ |
c90186eb DB |
2306 | if (!prephitemp || TREE_TYPE (prephitemp) != type) |
2307 | { | |
2308 | prephitemp = create_tmp_var (type, "prephitmp"); | |
2309 | get_var_ann (prephitemp); | |
2310 | } | |
2311 | ||
2312 | temp = prephitemp; | |
e9284566 | 2313 | add_referenced_tmp_var (temp); |
c90186eb | 2314 | |
aad97b9b RH |
2315 | if (TREE_CODE (type) == COMPLEX_TYPE) |
2316 | DECL_COMPLEX_GIMPLE_REG_P (temp) = 1; | |
e9284566 | 2317 | temp = create_phi_node (temp, block); |
c90186eb | 2318 | |
0fc6c492 | 2319 | NECESSARY (temp) = 0; |
d4e6fecb | 2320 | VEC_safe_push (tree, heap, inserted_exprs, temp); |
e9284566 DB |
2321 | FOR_EACH_EDGE (pred, ei, block->preds) |
2322 | add_phi_arg (temp, avail[pred->src->index], pred); | |
2323 | ||
c90186eb | 2324 | vn_add (PHI_RESULT (temp), val); |
e9284566 DB |
2325 | |
2326 | /* The value should *not* exist in PHI_GEN, or else we wouldn't be doing | |
2327 | this insertion, since we test for the existence of this value in PHI_GEN | |
2328 | before proceeding with the partial redundancy checks in insert_aux. | |
2329 | ||
2330 | The value may exist in AVAIL_OUT, in particular, it could be represented | |
2331 | by the expression we are trying to eliminate, in which case we want the | |
2332 | replacement to occur. If it's not existing in AVAIL_OUT, we want it | |
2333 | inserted there. | |
2334 | ||
2335 | Similarly, to the PHI_GEN case, the value should not exist in NEW_SETS of | |
2336 | this block, because if it did, it would have existed in our dominator's | |
2337 | AVAIL_OUT, and would have been skipped due to the full redundancy check. | |
2338 | */ | |
2339 | ||
2340 | bitmap_insert_into_set (PHI_GEN (block), | |
2341 | PHI_RESULT (temp)); | |
2342 | bitmap_value_replace_in_set (AVAIL_OUT (block), | |
2343 | PHI_RESULT (temp)); | |
2344 | bitmap_insert_into_set (NEW_SETS (block), | |
2345 | PHI_RESULT (temp)); | |
2346 | ||
2347 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
2348 | { | |
2349 | fprintf (dump_file, "Created phi "); | |
2350 | print_generic_expr (dump_file, temp, 0); | |
2351 | fprintf (dump_file, " in block %d\n", block->index); | |
2352 | } | |
2353 | pre_stats.phis++; | |
2354 | return true; | |
2355 | } | |
2356 | ||
2357 | ||
56db793a | 2358 | |
7e6eb623 DB |
2359 | /* Perform insertion of partially redundant values. |
2360 | For BLOCK, do the following: | |
2361 | 1. Propagate the NEW_SETS of the dominator into the current block. | |
2362 | If the block has multiple predecessors, | |
2363 | 2a. Iterate over the ANTIC expressions for the block to see if | |
2364 | any of them are partially redundant. | |
2365 | 2b. If so, insert them into the necessary predecessors to make | |
2366 | the expression fully redundant. | |
2367 | 2c. Insert a new PHI merging the values of the predecessors. | |
2368 | 2d. Insert the new PHI, and the new expressions, into the | |
2369 | NEW_SETS set. | |
2370 | 3. Recursively call ourselves on the dominator children of BLOCK. | |
6de9cd9a | 2371 | |
7e6eb623 | 2372 | */ |
e9284566 | 2373 | |
7e6eb623 DB |
2374 | static bool |
2375 | insert_aux (basic_block block) | |
6de9cd9a | 2376 | { |
7e6eb623 DB |
2377 | basic_block son; |
2378 | bool new_stuff = false; | |
6de9cd9a | 2379 | |
7e6eb623 | 2380 | if (block) |
6de9cd9a | 2381 | { |
7e6eb623 DB |
2382 | basic_block dom; |
2383 | dom = get_immediate_dominator (CDI_DOMINATORS, block); | |
2384 | if (dom) | |
a32b97a2 | 2385 | { |
3cd8c58a | 2386 | unsigned i; |
87c476a2 | 2387 | bitmap_iterator bi; |
6b416da1 | 2388 | bitmap_set_t newset = NEW_SETS (dom); |
e9284566 | 2389 | if (newset) |
87c476a2 | 2390 | { |
e9284566 DB |
2391 | /* Note that we need to value_replace both NEW_SETS, and |
2392 | AVAIL_OUT. For both the case of NEW_SETS, the value may be | |
2393 | represented by some non-simple expression here that we want | |
2394 | to replace it with. */ | |
2395 | EXECUTE_IF_SET_IN_BITMAP (newset->expressions, 0, i, bi) | |
2396 | { | |
2397 | bitmap_value_replace_in_set (NEW_SETS (block), ssa_name (i)); | |
2398 | bitmap_value_replace_in_set (AVAIL_OUT (block), ssa_name (i)); | |
2399 | } | |
87c476a2 | 2400 | } |
c5cbcccf | 2401 | if (!single_pred_p (block)) |
6de9cd9a | 2402 | { |
7e6eb623 DB |
2403 | value_set_node_t node; |
2404 | for (node = ANTIC_IN (block)->head; | |
2405 | node; | |
2406 | node = node->next) | |
6de9cd9a | 2407 | { |
c90186eb | 2408 | if (can_PRE_operation (node->expr)) |
6de9cd9a | 2409 | { |
7e6eb623 DB |
2410 | tree *avail; |
2411 | tree val; | |
2412 | bool by_some = false; | |
ca072a31 | 2413 | bool cant_insert = false; |
7e6eb623 DB |
2414 | bool all_same = true; |
2415 | tree first_s = NULL; | |
2416 | edge pred; | |
2417 | basic_block bprime; | |
e9284566 | 2418 | tree eprime = NULL_TREE; |
628f6a4e | 2419 | edge_iterator ei; |
ce25943a | 2420 | |
7e6eb623 | 2421 | val = get_value_handle (node->expr); |
6b416da1 | 2422 | if (bitmap_set_contains_value (PHI_GEN (block), val)) |
7e6eb623 | 2423 | continue; |
bdee7684 | 2424 | if (bitmap_set_contains_value (AVAIL_OUT (dom), val)) |
7e6eb623 DB |
2425 | { |
2426 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
2427 | fprintf (dump_file, "Found fully redundant value\n"); | |
2428 | continue; | |
2429 | } | |
628f6a4e | 2430 | |
e1111e8e | 2431 | avail = XCNEWVEC (tree, last_basic_block); |
628f6a4e | 2432 | FOR_EACH_EDGE (pred, ei, block->preds) |
7e6eb623 DB |
2433 | { |
2434 | tree vprime; | |
2435 | tree edoubleprime; | |
3f7d210d DB |
2436 | |
2437 | /* This can happen in the very weird case | |
2438 | that our fake infinite loop edges have caused a | |
2439 | critical edge to appear. */ | |
2440 | if (EDGE_CRITICAL_P (pred)) | |
2441 | { | |
2442 | cant_insert = true; | |
2443 | break; | |
2444 | } | |
7e6eb623 DB |
2445 | bprime = pred->src; |
2446 | eprime = phi_translate (node->expr, | |
2447 | ANTIC_IN (block), | |
2448 | bprime, block); | |
ce25943a DB |
2449 | |
2450 | /* eprime will generally only be NULL if the | |
2451 | value of the expression, translated | |
2452 | through the PHI for this predecessor, is | |
2453 | undefined. If that is the case, we can't | |
2454 | make the expression fully redundant, | |
2455 | because its value is undefined along a | |
2456 | predecessor path. We can thus break out | |
2457 | early because it doesn't matter what the | |
2458 | rest of the results are. */ | |
7e6eb623 | 2459 | if (eprime == NULL) |
ce25943a DB |
2460 | { |
2461 | cant_insert = true; | |
2462 | break; | |
2463 | } | |
7e6eb623 | 2464 | |
0fc6c492 | 2465 | eprime = fully_constant_expression (eprime); |
7e6eb623 | 2466 | vprime = get_value_handle (eprime); |
1e128c5f | 2467 | gcc_assert (vprime); |
bdee7684 DB |
2468 | edoubleprime = bitmap_find_leader (AVAIL_OUT (bprime), |
2469 | vprime); | |
7e6eb623 DB |
2470 | if (edoubleprime == NULL) |
2471 | { | |
2472 | avail[bprime->index] = eprime; | |
2473 | all_same = false; | |
2474 | } | |
2475 | else | |
2476 | { | |
2477 | avail[bprime->index] = edoubleprime; | |
ca072a31 | 2478 | by_some = true; |
7e6eb623 DB |
2479 | if (first_s == NULL) |
2480 | first_s = edoubleprime; | |
e9284566 DB |
2481 | else if (!operand_equal_p (first_s, edoubleprime, |
2482 | 0)) | |
7e6eb623 | 2483 | all_same = false; |
7e6eb623 DB |
2484 | } |
2485 | } | |
ca072a31 DB |
2486 | /* If we can insert it, it's not the same value |
2487 | already existing along every predecessor, and | |
2488 | it's defined by some predecessor, it is | |
2489 | partially redundant. */ | |
ce25943a | 2490 | if (!cant_insert && !all_same && by_some) |
7e6eb623 | 2491 | { |
c90186eb | 2492 | if (insert_into_preds_of_block (block, node, avail)) |
e9284566 | 2493 | new_stuff = true; |
7e6eb623 | 2494 | } |
0fc6c492 DB |
2495 | /* If all edges produce the same value and that value is |
2496 | an invariant, then the PHI has the same value on all | |
2497 | edges. Note this. */ | |
9be09bbc | 2498 | else if (!cant_insert && all_same && eprime |
0fc6c492 DB |
2499 | && is_gimple_min_invariant (eprime) |
2500 | && !is_gimple_min_invariant (val)) | |
2501 | { | |
2502 | value_set_t exprset = VALUE_HANDLE_EXPR_SET (val); | |
2503 | value_set_node_t node; | |
c90186eb | 2504 | |
0fc6c492 DB |
2505 | for (node = exprset->head; node; node = node->next) |
2506 | { | |
2507 | if (TREE_CODE (node->expr) == SSA_NAME) | |
2508 | { | |
c90186eb | 2509 | vn_add (node->expr, eprime); |
0fc6c492 DB |
2510 | pre_stats.constified++; |
2511 | } | |
2512 | } | |
2513 | } | |
7e6eb623 | 2514 | free (avail); |
6de9cd9a DN |
2515 | } |
2516 | } | |
2517 | } | |
2518 | } | |
2519 | } | |
7e6eb623 DB |
2520 | for (son = first_dom_son (CDI_DOMINATORS, block); |
2521 | son; | |
2522 | son = next_dom_son (CDI_DOMINATORS, son)) | |
2523 | { | |
2524 | new_stuff |= insert_aux (son); | |
2525 | } | |
2526 | ||
2527 | return new_stuff; | |
6de9cd9a DN |
2528 | } |
2529 | ||
7e6eb623 | 2530 | /* Perform insertion of partially redundant values. */ |
6de9cd9a | 2531 | |
7e6eb623 DB |
2532 | static void |
2533 | insert (void) | |
6de9cd9a | 2534 | { |
7e6eb623 | 2535 | bool new_stuff = true; |
6de9cd9a | 2536 | basic_block bb; |
7e6eb623 | 2537 | int num_iterations = 0; |
bdee7684 | 2538 | |
7e6eb623 | 2539 | FOR_ALL_BB (bb) |
6b416da1 | 2540 | NEW_SETS (bb) = bitmap_set_new (); |
6de9cd9a | 2541 | |
7e6eb623 | 2542 | while (new_stuff) |
6de9cd9a | 2543 | { |
7e6eb623 DB |
2544 | num_iterations++; |
2545 | new_stuff = false; | |
2546 | new_stuff = insert_aux (ENTRY_BLOCK_PTR); | |
6de9cd9a | 2547 | } |
7e6eb623 DB |
2548 | if (num_iterations > 2 && dump_file && (dump_flags & TDF_STATS)) |
2549 | fprintf (dump_file, "insert required %d iterations\n", num_iterations); | |
2550 | } | |
6de9cd9a | 2551 | |
33c94679 | 2552 | |
ff2ad0f7 DN |
2553 | /* Return true if VAR is an SSA variable with no defining statement in |
2554 | this procedure, *AND* isn't a live-on-entry parameter. */ | |
33c94679 | 2555 | |
7e6eb623 DB |
2556 | static bool |
2557 | is_undefined_value (tree expr) | |
ff2ad0f7 DN |
2558 | { |
2559 | return (TREE_CODE (expr) == SSA_NAME | |
2560 | && IS_EMPTY_STMT (SSA_NAME_DEF_STMT (expr)) | |
2561 | /* PARM_DECLs and hard registers are always defined. */ | |
e670d9e4 | 2562 | && TREE_CODE (SSA_NAME_VAR (expr)) != PARM_DECL); |
ff2ad0f7 DN |
2563 | } |
2564 | ||
2565 | ||
2566 | /* Given an SSA variable VAR and an expression EXPR, compute the value | |
2567 | number for EXPR and create a value handle (VAL) for it. If VAR and | |
2568 | EXPR are not the same, associate VAL with VAR. Finally, add VAR to | |
2569 | S1 and its value handle to S2. | |
2570 | ||
2571 | VUSES represent the virtual use operands associated with EXPR (if | |
c90186eb | 2572 | any). */ |
ff2ad0f7 DN |
2573 | |
2574 | static inline void | |
f47c96aa | 2575 | add_to_sets (tree var, tree expr, tree stmt, bitmap_set_t s1, |
bdee7684 | 2576 | bitmap_set_t s2) |
ff2ad0f7 | 2577 | { |
f47c96aa | 2578 | tree val = vn_lookup_or_add (expr, stmt); |
ff2ad0f7 DN |
2579 | |
2580 | /* VAR and EXPR may be the same when processing statements for which | |
2581 | we are not computing value numbers (e.g., non-assignments, or | |
2582 | statements that make aliased stores). In those cases, we are | |
2583 | only interested in making VAR available as its own value. */ | |
2584 | if (var != expr) | |
c90186eb | 2585 | vn_add (var, val); |
ff2ad0f7 | 2586 | |
7f233d9f DB |
2587 | if (s1) |
2588 | bitmap_insert_into_set (s1, var); | |
bdee7684 | 2589 | bitmap_value_insert_into_set (s2, var); |
ff2ad0f7 DN |
2590 | } |
2591 | ||
2592 | ||
2593 | /* Given a unary or binary expression EXPR, create and return a new | |
f6fe65dc | 2594 | expression with the same structure as EXPR but with its operands |
ff2ad0f7 | 2595 | replaced with the value handles of each of the operands of EXPR. |
ff2ad0f7 DN |
2596 | |
2597 | VUSES represent the virtual use operands associated with EXPR (if | |
c90186eb | 2598 | any). Insert EXPR's operands into the EXP_GEN set for BLOCK. */ |
ff2ad0f7 DN |
2599 | |
2600 | static inline tree | |
f47c96aa | 2601 | create_value_expr_from (tree expr, basic_block block, tree stmt) |
ff2ad0f7 DN |
2602 | { |
2603 | int i; | |
2604 | enum tree_code code = TREE_CODE (expr); | |
2605 | tree vexpr; | |
b89361c6 | 2606 | alloc_pool pool; |
ff2ad0f7 | 2607 | |
6615c446 JO |
2608 | gcc_assert (TREE_CODE_CLASS (code) == tcc_unary |
2609 | || TREE_CODE_CLASS (code) == tcc_binary | |
b89361c6 | 2610 | || TREE_CODE_CLASS (code) == tcc_comparison |
43da81be DB |
2611 | || TREE_CODE_CLASS (code) == tcc_reference |
2612 | || TREE_CODE_CLASS (code) == tcc_expression | |
c90186eb DB |
2613 | || TREE_CODE_CLASS (code) == tcc_exceptional |
2614 | || TREE_CODE_CLASS (code) == tcc_declaration); | |
33c94679 | 2615 | |
6615c446 | 2616 | if (TREE_CODE_CLASS (code) == tcc_unary) |
b89361c6 | 2617 | pool = unary_node_pool; |
6615c446 | 2618 | else if (TREE_CODE_CLASS (code) == tcc_reference) |
b89361c6 | 2619 | pool = reference_node_pool; |
43da81be | 2620 | else if (TREE_CODE_CLASS (code) == tcc_binary) |
b89361c6 | 2621 | pool = binary_node_pool; |
43da81be DB |
2622 | else if (TREE_CODE_CLASS (code) == tcc_comparison) |
2623 | pool = comparison_node_pool; | |
2624 | else if (TREE_CODE_CLASS (code) == tcc_exceptional) | |
2625 | { | |
2626 | gcc_assert (code == TREE_LIST); | |
2627 | pool = list_node_pool; | |
2628 | } | |
2629 | else | |
2630 | { | |
2631 | gcc_assert (code == CALL_EXPR); | |
2632 | pool = expression_node_pool; | |
2633 | } | |
ff2ad0f7 | 2634 | |
e1111e8e | 2635 | vexpr = (tree) pool_alloc (pool); |
ff2ad0f7 | 2636 | memcpy (vexpr, expr, tree_size (expr)); |
43da81be DB |
2637 | |
2638 | /* This case is only for TREE_LIST's that appear as part of | |
2639 | CALL_EXPR's. Anything else is a bug, but we can't easily verify | |
bbf6f1cf | 2640 | this, hence this comment. TREE_LIST is not handled by the |
43da81be DB |
2641 | general case below is because they don't have a fixed length, or |
2642 | operands, so you can't access purpose/value/chain through | |
2643 | TREE_OPERAND macros. */ | |
2644 | ||
2645 | if (code == TREE_LIST) | |
2646 | { | |
81def1b7 | 2647 | tree op = NULL_TREE; |
43da81be DB |
2648 | tree temp = NULL_TREE; |
2649 | if (TREE_CHAIN (vexpr)) | |
2650 | temp = create_value_expr_from (TREE_CHAIN (vexpr), block, stmt); | |
2651 | TREE_CHAIN (vexpr) = temp ? temp : TREE_CHAIN (vexpr); | |
2652 | ||
81def1b7 DB |
2653 | |
2654 | /* Recursively value-numberize reference ops. */ | |
2655 | if (REFERENCE_CLASS_P (TREE_VALUE (vexpr))) | |
2656 | { | |
2657 | tree tempop; | |
2658 | op = TREE_VALUE (vexpr); | |
2659 | tempop = create_value_expr_from (op, block, stmt); | |
2660 | op = tempop ? tempop : op; | |
2661 | ||
2662 | TREE_VALUE (vexpr) = vn_lookup_or_add (op, stmt); | |
2663 | } | |
2664 | else | |
2665 | { | |
2666 | op = TREE_VALUE (vexpr); | |
2667 | TREE_VALUE (vexpr) = vn_lookup_or_add (TREE_VALUE (vexpr), NULL); | |
2668 | } | |
43da81be DB |
2669 | /* This is the equivalent of inserting op into EXP_GEN like we |
2670 | do below */ | |
81def1b7 DB |
2671 | if (!is_undefined_value (op)) |
2672 | value_insert_into_set (EXP_GEN (block), op); | |
43da81be DB |
2673 | |
2674 | return vexpr; | |
2675 | } | |
ff2ad0f7 DN |
2676 | |
2677 | for (i = 0; i < TREE_CODE_LENGTH (code); i++) | |
6de9cd9a | 2678 | { |
b89361c6 DB |
2679 | tree val, op; |
2680 | ||
2681 | op = TREE_OPERAND (expr, i); | |
2682 | if (op == NULL_TREE) | |
2683 | continue; | |
2684 | ||
2685 | /* If OP is a constant that has overflowed, do not value number | |
2686 | this expression. */ | |
7da4bf7d | 2687 | if (CONSTANT_CLASS_P (op) |
b89361c6 DB |
2688 | && TREE_OVERFLOW (op)) |
2689 | { | |
2690 | pool_free (pool, vexpr); | |
2691 | return NULL; | |
2692 | } | |
2693 | ||
43da81be | 2694 | /* Recursively value-numberize reference ops and tree lists. */ |
7da4bf7d | 2695 | if (REFERENCE_CLASS_P (op)) |
bdee7684 | 2696 | { |
f47c96aa | 2697 | tree tempop = create_value_expr_from (op, block, stmt); |
b89361c6 | 2698 | op = tempop ? tempop : op; |
f47c96aa | 2699 | val = vn_lookup_or_add (op, stmt); |
bdee7684 | 2700 | } |
43da81be DB |
2701 | else if (TREE_CODE (op) == TREE_LIST) |
2702 | { | |
2703 | tree tempop; | |
2704 | ||
2705 | gcc_assert (TREE_CODE (expr) == CALL_EXPR); | |
2706 | tempop = create_value_expr_from (op, block, stmt); | |
2707 | ||
2708 | op = tempop ? tempop : op; | |
2709 | vn_lookup_or_add (op, NULL); | |
2710 | /* Unlike everywhere else, we do *not* want to replace the | |
2711 | TREE_LIST itself with a value number, because support | |
2712 | functions we call will blow up. */ | |
2713 | val = op; | |
2714 | } | |
b89361c6 DB |
2715 | else |
2716 | /* Create a value handle for OP and add it to VEXPR. */ | |
2717 | val = vn_lookup_or_add (op, NULL); | |
2718 | ||
43da81be | 2719 | if (!is_undefined_value (op) && TREE_CODE (op) != TREE_LIST) |
b89361c6 DB |
2720 | value_insert_into_set (EXP_GEN (block), op); |
2721 | ||
2722 | if (TREE_CODE (val) == VALUE_HANDLE) | |
2723 | TREE_TYPE (val) = TREE_TYPE (TREE_OPERAND (vexpr, i)); | |
2724 | ||
2725 | TREE_OPERAND (vexpr, i) = val; | |
6de9cd9a | 2726 | } |
33c94679 | 2727 | |
ff2ad0f7 | 2728 | return vexpr; |
6de9cd9a DN |
2729 | } |
2730 | ||
ff2ad0f7 | 2731 | |
43da81be | 2732 | |
ff3fdad2 DB |
2733 | /* Insert extra phis to merge values that are fully available from |
2734 | preds of BLOCK, but have no dominating representative coming from | |
2735 | block DOM. */ | |
2736 | ||
2737 | static void | |
2738 | insert_extra_phis (basic_block block, basic_block dom) | |
2739 | { | |
2740 | ||
2741 | if (!single_pred_p (block)) | |
2742 | { | |
2743 | edge e; | |
2744 | edge_iterator ei; | |
2745 | bool first = true; | |
2746 | bitmap_set_t tempset = bitmap_set_new (); | |
2747 | ||
2748 | FOR_EACH_EDGE (e, ei, block->preds) | |
2749 | { | |
2750 | if (first) | |
2751 | { | |
2752 | bitmap_set_copy (tempset, AVAIL_OUT (e->src)); | |
2753 | first = false; | |
2754 | } | |
2755 | else | |
2756 | bitmap_set_and (tempset, AVAIL_OUT (e->src)); | |
2757 | } | |
2758 | ||
2759 | if (dom) | |
2760 | bitmap_set_and_compl (tempset, AVAIL_OUT (dom)); | |
2761 | ||
2762 | if (!bitmap_set_empty_p (tempset)) | |
2763 | { | |
2764 | unsigned int i; | |
2765 | bitmap_iterator bi; | |
2766 | ||
2767 | EXECUTE_IF_SET_IN_BITMAP (tempset->expressions, 0, i, bi) | |
2768 | { | |
2769 | tree name = ssa_name (i); | |
2770 | tree val = get_value_handle (name); | |
c90186eb DB |
2771 | tree temp; |
2772 | ||
2773 | if (!mergephitemp | |
2774 | || TREE_TYPE (name) != TREE_TYPE (mergephitemp)) | |
2775 | { | |
2776 | mergephitemp = create_tmp_var (TREE_TYPE (name), | |
2777 | "mergephitmp"); | |
2778 | get_var_ann (mergephitemp); | |
2779 | } | |
2780 | temp = mergephitemp; | |
ff3fdad2 DB |
2781 | |
2782 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
2783 | { | |
2784 | fprintf (dump_file, "Creating phi "); | |
2785 | print_generic_expr (dump_file, temp, 0); | |
2786 | fprintf (dump_file, " to merge available but not dominating values "); | |
2787 | } | |
2788 | ||
2789 | add_referenced_tmp_var (temp); | |
2790 | temp = create_phi_node (temp, block); | |
2791 | NECESSARY (temp) = 0; | |
2792 | VEC_safe_push (tree, heap, inserted_exprs, temp); | |
2793 | ||
2794 | FOR_EACH_EDGE (e, ei, block->preds) | |
2795 | { | |
2796 | tree leader = bitmap_find_leader (AVAIL_OUT (e->src), val); | |
2797 | ||
2798 | gcc_assert (leader); | |
2799 | add_phi_arg (temp, leader, e); | |
2800 | ||
2801 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
2802 | { | |
2803 | print_generic_expr (dump_file, leader, 0); | |
2804 | fprintf (dump_file, " in block %d,", e->src->index); | |
2805 | } | |
2806 | } | |
2807 | ||
c90186eb | 2808 | vn_add (PHI_RESULT (temp), val); |
ff3fdad2 DB |
2809 | |
2810 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
2811 | fprintf (dump_file, "\n"); | |
2812 | } | |
2813 | } | |
2814 | } | |
2815 | } | |
2816 | ||
dda243de SB |
2817 | /* Given a statement STMT and its right hand side which is a load, try |
2818 | to look for the expression stored in the location for the load, and | |
2819 | return true if a useful equivalence was recorded for LHS. */ | |
2820 | ||
2821 | static bool | |
2822 | try_look_through_load (tree lhs, tree mem_ref, tree stmt, basic_block block) | |
2823 | { | |
2824 | tree store_stmt = NULL; | |
2825 | tree rhs; | |
2826 | ssa_op_iter i; | |
2827 | tree vuse; | |
2828 | ||
2829 | FOR_EACH_SSA_TREE_OPERAND (vuse, stmt, i, SSA_OP_VIRTUAL_USES) | |
2830 | { | |
2831 | tree def_stmt; | |
2832 | ||
2833 | gcc_assert (TREE_CODE (vuse) == SSA_NAME); | |
2834 | def_stmt = SSA_NAME_DEF_STMT (vuse); | |
2835 | ||
2836 | /* If there is no useful statement for this VUSE, we'll not find a | |
2837 | useful expression to return either. Likewise, if there is a | |
2838 | statement but it is not a simple assignment or it has virtual | |
2839 | uses, we can stop right here. Note that this means we do | |
2840 | not look through PHI nodes, which is intentional. */ | |
2841 | if (!def_stmt | |
2842 | || TREE_CODE (def_stmt) != MODIFY_EXPR | |
2843 | || !ZERO_SSA_OPERANDS (def_stmt, SSA_OP_VIRTUAL_USES)) | |
2844 | return false; | |
2845 | ||
2846 | /* If this is not the same statement as one we have looked at for | |
2847 | another VUSE of STMT already, we have two statements producing | |
2848 | something that reaches our STMT. */ | |
2849 | if (store_stmt && store_stmt != def_stmt) | |
2850 | return false; | |
2851 | else | |
2852 | { | |
2853 | /* Is this a store to the exact same location as the one we are | |
2854 | loading from in STMT? */ | |
2855 | if (!operand_equal_p (TREE_OPERAND (def_stmt, 0), mem_ref, 0)) | |
2856 | return false; | |
2857 | ||
2858 | /* Otherwise remember this statement and see if all other VUSEs | |
2859 | come from the same statement. */ | |
2860 | store_stmt = def_stmt; | |
2861 | } | |
2862 | } | |
2863 | ||
2864 | /* Alright then, we have visited all VUSEs of STMT and we've determined | |
2865 | that all of them come from the same statement STORE_STMT. See if there | |
2866 | is a useful expression we can deduce from STORE_STMT. */ | |
2867 | rhs = TREE_OPERAND (store_stmt, 1); | |
b3e2e29c DB |
2868 | if ((TREE_CODE (rhs) == SSA_NAME |
2869 | && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs)) | |
dda243de SB |
2870 | || is_gimple_min_invariant (rhs) |
2871 | || TREE_CODE (rhs) == ADDR_EXPR | |
2872 | || TREE_INVARIANT (rhs)) | |
2873 | { | |
b3e2e29c | 2874 | |
dda243de SB |
2875 | /* Yay! Compute a value number for the RHS of the statement and |
2876 | add its value to the AVAIL_OUT set for the block. Add the LHS | |
2877 | to TMP_GEN. */ | |
2878 | add_to_sets (lhs, rhs, store_stmt, TMP_GEN (block), AVAIL_OUT (block)); | |
2879 | if (TREE_CODE (rhs) == SSA_NAME | |
2880 | && !is_undefined_value (rhs)) | |
2881 | value_insert_into_set (EXP_GEN (block), rhs); | |
2882 | return true; | |
2883 | } | |
2884 | ||
2885 | return false; | |
2886 | } | |
2887 | ||
c90186eb DB |
2888 | /* Return a copy of NODE that is stored in the temporary alloc_pool's. |
2889 | This is made recursively true, so that the operands are stored in | |
2890 | the pool as well. */ | |
2891 | ||
2892 | static tree | |
2893 | poolify_tree (tree node) | |
2894 | { | |
2895 | switch (TREE_CODE (node)) | |
2896 | { | |
2897 | case INDIRECT_REF: | |
2898 | { | |
2899 | tree temp = pool_alloc (reference_node_pool); | |
2900 | memcpy (temp, node, tree_size (node)); | |
2901 | TREE_OPERAND (temp, 0) = poolify_tree (TREE_OPERAND (temp, 0)); | |
2902 | return temp; | |
2903 | } | |
2904 | break; | |
2905 | case MODIFY_EXPR: | |
2906 | { | |
2907 | tree temp = pool_alloc (modify_expr_node_pool); | |
2908 | memcpy (temp, node, tree_size (node)); | |
2909 | TREE_OPERAND (temp, 0) = poolify_tree (TREE_OPERAND (temp, 0)); | |
2910 | TREE_OPERAND (temp, 1) = poolify_tree (TREE_OPERAND (temp, 1)); | |
2911 | return temp; | |
2912 | } | |
2913 | break; | |
2914 | case SSA_NAME: | |
2915 | case INTEGER_CST: | |
2916 | case STRING_CST: | |
2917 | case REAL_CST: | |
2918 | case PARM_DECL: | |
2919 | case VAR_DECL: | |
2920 | case RESULT_DECL: | |
2921 | return node; | |
2922 | default: | |
2923 | gcc_unreachable (); | |
2924 | } | |
2925 | } | |
2926 | ||
2927 | static tree modify_expr_template; | |
2928 | ||
2929 | /* Allocate a MODIFY_EXPR with TYPE, and operands OP1, OP2 in the | |
2930 | alloc pools and return it. */ | |
2931 | static tree | |
2932 | poolify_modify_expr (tree type, tree op1, tree op2) | |
2933 | { | |
2934 | if (modify_expr_template == NULL) | |
2935 | modify_expr_template = build2 (MODIFY_EXPR, type, op1, op2); | |
2936 | ||
2937 | TREE_OPERAND (modify_expr_template, 0) = op1; | |
2938 | TREE_OPERAND (modify_expr_template, 1) = op2; | |
2939 | TREE_TYPE (modify_expr_template) = type; | |
2940 | ||
2941 | return poolify_tree (modify_expr_template); | |
2942 | } | |
2943 | ||
2944 | ||
2945 | /* For each real store operation of the form | |
2946 | *a = <value> that we see, create a corresponding fake store of the | |
2947 | form storetmp_<version> = *a. | |
2948 | ||
2949 | This enables AVAIL computation to mark the results of stores as | |
2950 | available. Without this, you'd need to do some computation to | |
2951 | mark the result of stores as ANTIC and AVAIL at all the right | |
2952 | points. | |
2953 | To save memory, we keep the store | |
2954 | statements pool allocated until we decide whether they are | |
2955 | necessary or not. */ | |
2956 | ||
2957 | static void | |
2958 | insert_fake_stores (void) | |
2959 | { | |
2960 | basic_block block; | |
2961 | ||
2962 | FOR_ALL_BB (block) | |
2963 | { | |
2964 | block_stmt_iterator bsi; | |
2965 | for (bsi = bsi_start (block); !bsi_end_p (bsi); bsi_next (&bsi)) | |
2966 | { | |
2967 | tree stmt = bsi_stmt (bsi); | |
2968 | ||
2969 | /* We can't generate SSA names for stores that are complex | |
2970 | or aggregate. We also want to ignore things whose | |
2971 | virtual uses occur in abnormal phis. */ | |
2972 | ||
2973 | if (TREE_CODE (stmt) == MODIFY_EXPR | |
2974 | && TREE_CODE (TREE_OPERAND (stmt, 0)) == INDIRECT_REF | |
2975 | && !AGGREGATE_TYPE_P (TREE_TYPE (TREE_OPERAND (stmt, 0))) | |
2976 | && TREE_CODE (TREE_TYPE (TREE_OPERAND (stmt, 0))) != COMPLEX_TYPE) | |
2977 | { | |
2978 | ssa_op_iter iter; | |
2979 | def_operand_p defp; | |
2980 | tree lhs = TREE_OPERAND (stmt, 0); | |
2981 | tree rhs = TREE_OPERAND (stmt, 1); | |
2982 | tree new; | |
2983 | bool notokay = false; | |
2984 | ||
2985 | FOR_EACH_SSA_DEF_OPERAND (defp, stmt, iter, SSA_OP_VIRTUAL_DEFS) | |
2986 | { | |
2987 | tree defvar = DEF_FROM_PTR (defp); | |
2988 | if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (defvar)) | |
2989 | { | |
2990 | notokay = true; | |
2991 | break; | |
2992 | } | |
2993 | } | |
2994 | ||
2995 | if (notokay) | |
2996 | continue; | |
2997 | ||
2998 | if (!storetemp || TREE_TYPE (rhs) != TREE_TYPE (storetemp)) | |
2999 | { | |
3000 | storetemp = create_tmp_var (TREE_TYPE (rhs), "storetmp"); | |
3001 | get_var_ann (storetemp); | |
3002 | } | |
3003 | ||
3004 | new = poolify_modify_expr (TREE_TYPE (stmt), storetemp, lhs); | |
3005 | ||
3006 | lhs = make_ssa_name (storetemp, new); | |
3007 | TREE_OPERAND (new, 0) = lhs; | |
3008 | create_ssa_artficial_load_stmt (new, stmt); | |
3009 | ||
3010 | NECESSARY (new) = 0; | |
3011 | VEC_safe_push (tree, heap, inserted_exprs, new); | |
3012 | VEC_safe_push (tree, heap, need_creation, new); | |
3013 | bsi_insert_after (&bsi, new, BSI_NEW_STMT); | |
3014 | } | |
3015 | } | |
3016 | } | |
3017 | } | |
3018 | ||
3019 | /* Turn the pool allocated fake stores that we created back into real | |
3020 | GC allocated ones if they turned out to be necessary to PRE some | |
3021 | expressions. */ | |
3022 | ||
3023 | static void | |
3024 | realify_fake_stores (void) | |
3025 | { | |
3026 | unsigned int i; | |
3027 | tree stmt; | |
3028 | ||
3029 | for (i = 0; VEC_iterate (tree, need_creation, i, stmt); i++) | |
3030 | { | |
3031 | if (NECESSARY (stmt)) | |
3032 | { | |
3033 | block_stmt_iterator bsi; | |
3034 | tree newstmt; | |
3035 | ||
3036 | /* Mark the temp variable as referenced */ | |
3037 | add_referenced_tmp_var (SSA_NAME_VAR (TREE_OPERAND (stmt, 0))); | |
3038 | ||
3039 | /* Put the new statement in GC memory, fix up the annotation | |
3040 | and SSA_NAME_DEF_STMT on it, and then put it in place of | |
3041 | the old statement in the IR stream. */ | |
3042 | newstmt = unshare_expr (stmt); | |
3043 | SSA_NAME_DEF_STMT (TREE_OPERAND (newstmt, 0)) = newstmt; | |
3044 | ||
3045 | newstmt->common.ann = stmt->common.ann; | |
3046 | ||
3047 | bsi = bsi_for_stmt (stmt); | |
3048 | bsi_replace (&bsi, newstmt, true); | |
3049 | } | |
3050 | else | |
3051 | release_defs (stmt); | |
3052 | } | |
3053 | } | |
3054 | ||
3055 | ||
665fcad8 SB |
3056 | /* Compute the AVAIL set for all basic blocks. |
3057 | ||
3058 | This function performs value numbering of the statements in each basic | |
3059 | block. The AVAIL sets are built from information we glean while doing | |
3060 | this value numbering, since the AVAIL sets contain only one entry per | |
7e6eb623 | 3061 | value. |
7e6eb623 DB |
3062 | |
3063 | AVAIL_IN[BLOCK] = AVAIL_OUT[dom(BLOCK)]. | |
ff2ad0f7 | 3064 | AVAIL_OUT[BLOCK] = AVAIL_IN[BLOCK] U PHI_GEN[BLOCK] U TMP_GEN[BLOCK]. */ |
6de9cd9a | 3065 | |
7e6eb623 | 3066 | static void |
665fcad8 | 3067 | compute_avail (void) |
6de9cd9a | 3068 | { |
665fcad8 SB |
3069 | basic_block block, son; |
3070 | basic_block *worklist; | |
3071 | size_t sp = 0; | |
3072 | tree param; | |
3073 | ||
7e6eb623 DB |
3074 | /* For arguments with default definitions, we pretend they are |
3075 | defined in the entry block. */ | |
665fcad8 SB |
3076 | for (param = DECL_ARGUMENTS (current_function_decl); |
3077 | param; | |
3078 | param = TREE_CHAIN (param)) | |
7e6eb623 | 3079 | { |
665fcad8 | 3080 | if (default_def (param) != NULL) |
7e6eb623 | 3081 | { |
665fcad8 | 3082 | tree def = default_def (param); |
84ceaf06 | 3083 | vn_lookup_or_add (def, NULL); |
665fcad8 SB |
3084 | bitmap_insert_into_set (TMP_GEN (ENTRY_BLOCK_PTR), def); |
3085 | bitmap_value_insert_into_set (AVAIL_OUT (ENTRY_BLOCK_PTR), def); | |
7e6eb623 DB |
3086 | } |
3087 | } | |
665fcad8 SB |
3088 | |
3089 | /* Allocate the worklist. */ | |
e1111e8e | 3090 | worklist = XNEWVEC (basic_block, n_basic_blocks); |
665fcad8 SB |
3091 | |
3092 | /* Seed the algorithm by putting the dominator children of the entry | |
3093 | block on the worklist. */ | |
3094 | for (son = first_dom_son (CDI_DOMINATORS, ENTRY_BLOCK_PTR); | |
3095 | son; | |
3096 | son = next_dom_son (CDI_DOMINATORS, son)) | |
3097 | worklist[sp++] = son; | |
3098 | ||
3099 | /* Loop until the worklist is empty. */ | |
3100 | while (sp) | |
6de9cd9a | 3101 | { |
7e6eb623 DB |
3102 | block_stmt_iterator bsi; |
3103 | tree stmt, phi; | |
3104 | basic_block dom; | |
3105 | ||
665fcad8 SB |
3106 | /* Pick a block from the worklist. */ |
3107 | block = worklist[--sp]; | |
3108 | ||
ff2ad0f7 DN |
3109 | /* Initially, the set of available values in BLOCK is that of |
3110 | its immediate dominator. */ | |
7e6eb623 DB |
3111 | dom = get_immediate_dominator (CDI_DOMINATORS, block); |
3112 | if (dom) | |
bdee7684 | 3113 | bitmap_set_copy (AVAIL_OUT (block), AVAIL_OUT (dom)); |
33c94679 | 3114 | |
ff3fdad2 DB |
3115 | if (!in_fre) |
3116 | insert_extra_phis (block, dom); | |
3117 | ||
ff2ad0f7 | 3118 | /* Generate values for PHI nodes. */ |
17192884 | 3119 | for (phi = phi_nodes (block); phi; phi = PHI_CHAIN (phi)) |
6b416da1 DB |
3120 | /* We have no need for virtual phis, as they don't represent |
3121 | actual computations. */ | |
3122 | if (is_gimple_reg (PHI_RESULT (phi))) | |
3123 | add_to_sets (PHI_RESULT (phi), PHI_RESULT (phi), NULL, | |
3124 | PHI_GEN (block), AVAIL_OUT (block)); | |
7e6eb623 | 3125 | |
ff2ad0f7 DN |
3126 | /* Now compute value numbers and populate value sets with all |
3127 | the expressions computed in BLOCK. */ | |
7e6eb623 | 3128 | for (bsi = bsi_start (block); !bsi_end_p (bsi); bsi_next (&bsi)) |
6de9cd9a | 3129 | { |
ff2ad0f7 | 3130 | stmt_ann_t ann; |
f47c96aa AM |
3131 | ssa_op_iter iter; |
3132 | tree op; | |
ff2ad0f7 | 3133 | |
7e6eb623 | 3134 | stmt = bsi_stmt (bsi); |
ff2ad0f7 | 3135 | ann = stmt_ann (stmt); |
ff2ad0f7 | 3136 | |
c90186eb DB |
3137 | /* For regular value numbering, we are only interested in |
3138 | assignments of the form X_i = EXPR, where EXPR represents | |
3139 | an "interesting" computation, it has no volatile operands | |
3140 | and X_i doesn't flow through an abnormal edge. */ | |
ff2ad0f7 DN |
3141 | if (TREE_CODE (stmt) == MODIFY_EXPR |
3142 | && !ann->has_volatile_ops | |
3143 | && TREE_CODE (TREE_OPERAND (stmt, 0)) == SSA_NAME | |
3144 | && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (TREE_OPERAND (stmt, 0))) | |
7e6eb623 | 3145 | { |
ff2ad0f7 DN |
3146 | tree lhs = TREE_OPERAND (stmt, 0); |
3147 | tree rhs = TREE_OPERAND (stmt, 1); | |
ff2ad0f7 | 3148 | |
dda243de SB |
3149 | /* Try to look through loads. */ |
3150 | if (TREE_CODE (lhs) == SSA_NAME | |
3151 | && !ZERO_SSA_OPERANDS (stmt, SSA_OP_VIRTUAL_USES) | |
3152 | && try_look_through_load (lhs, rhs, stmt, block)) | |
3153 | continue; | |
3154 | ||
ff2ad0f7 | 3155 | STRIP_USELESS_TYPE_CONVERSION (rhs); |
c90186eb | 3156 | if (can_value_number_operation (rhs)) |
b89361c6 | 3157 | { |
c90186eb DB |
3158 | /* For value numberable operation, create a |
3159 | duplicate expression with the operands replaced | |
3160 | with the value handles of the original RHS. */ | |
f47c96aa | 3161 | tree newt = create_value_expr_from (rhs, block, stmt); |
b89361c6 DB |
3162 | if (newt) |
3163 | { | |
f47c96aa | 3164 | add_to_sets (lhs, newt, stmt, TMP_GEN (block), |
b89361c6 DB |
3165 | AVAIL_OUT (block)); |
3166 | value_insert_into_set (EXP_GEN (block), newt); | |
3167 | continue; | |
3168 | } | |
3169 | } | |
b3e2e29c DB |
3170 | else if ((TREE_CODE (rhs) == SSA_NAME |
3171 | && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs)) | |
b89361c6 | 3172 | || is_gimple_min_invariant (rhs) |
b89361c6 | 3173 | || TREE_CODE (rhs) == ADDR_EXPR |
f5594471 | 3174 | || TREE_INVARIANT (rhs) |
b89361c6 | 3175 | || DECL_P (rhs)) |
3d3fa3a1 DB |
3176 | { |
3177 | /* Compute a value number for the RHS of the statement | |
3178 | and add its value to the AVAIL_OUT set for the block. | |
3179 | Add the LHS to TMP_GEN. */ | |
f47c96aa | 3180 | add_to_sets (lhs, rhs, stmt, TMP_GEN (block), |
3d3fa3a1 DB |
3181 | AVAIL_OUT (block)); |
3182 | ||
3183 | if (TREE_CODE (rhs) == SSA_NAME | |
3184 | && !is_undefined_value (rhs)) | |
3185 | value_insert_into_set (EXP_GEN (block), rhs); | |
3186 | continue; | |
3187 | } | |
7e6eb623 | 3188 | } |
56db793a | 3189 | |
ff2ad0f7 DN |
3190 | /* For any other statement that we don't recognize, simply |
3191 | make the names generated by the statement available in | |
3192 | AVAIL_OUT and TMP_GEN. */ | |
f47c96aa AM |
3193 | FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_DEF) |
3194 | add_to_sets (op, op, NULL, TMP_GEN (block), AVAIL_OUT (block)); | |
ff2ad0f7 | 3195 | |
f47c96aa AM |
3196 | FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_USE) |
3197 | add_to_sets (op, op, NULL, NULL , AVAIL_OUT (block)); | |
6de9cd9a | 3198 | } |
665fcad8 SB |
3199 | |
3200 | /* Put the dominator children of BLOCK on the worklist of blocks | |
3201 | to compute available sets for. */ | |
3202 | for (son = first_dom_son (CDI_DOMINATORS, block); | |
3203 | son; | |
3204 | son = next_dom_son (CDI_DOMINATORS, son)) | |
3205 | worklist[sp++] = son; | |
6de9cd9a | 3206 | } |
33c94679 | 3207 | |
665fcad8 | 3208 | free (worklist); |
7e6eb623 DB |
3209 | } |
3210 | ||
33c94679 | 3211 | |
7e6eb623 DB |
3212 | /* Eliminate fully redundant computations. */ |
3213 | ||
3214 | static void | |
3215 | eliminate (void) | |
3216 | { | |
3217 | basic_block b; | |
3218 | ||
3219 | FOR_EACH_BB (b) | |
3220 | { | |
3221 | block_stmt_iterator i; | |
3222 | ||
3223 | for (i = bsi_start (b); !bsi_end_p (i); bsi_next (&i)) | |
3224 | { | |
3225 | tree stmt = bsi_stmt (i); | |
3226 | ||
ff2ad0f7 DN |
3227 | /* Lookup the RHS of the expression, see if we have an |
3228 | available computation for it. If so, replace the RHS with | |
7e6eb623 | 3229 | the available computation. */ |
ff2ad0f7 DN |
3230 | if (TREE_CODE (stmt) == MODIFY_EXPR |
3231 | && TREE_CODE (TREE_OPERAND (stmt, 0)) == SSA_NAME | |
3232 | && TREE_CODE (TREE_OPERAND (stmt ,1)) != SSA_NAME | |
3233 | && !is_gimple_min_invariant (TREE_OPERAND (stmt, 1)) | |
3234 | && !stmt_ann (stmt)->has_volatile_ops) | |
3235 | { | |
3236 | tree lhs = TREE_OPERAND (stmt, 0); | |
3237 | tree *rhs_p = &TREE_OPERAND (stmt, 1); | |
3238 | tree sprime; | |
ff2ad0f7 | 3239 | |
3d3fa3a1 DB |
3240 | sprime = bitmap_find_leader (AVAIL_OUT (b), |
3241 | vn_lookup (lhs, NULL)); | |
ff2ad0f7 DN |
3242 | if (sprime |
3243 | && sprime != lhs | |
3244 | && (TREE_CODE (*rhs_p) != SSA_NAME | |
3245 | || may_propagate_copy (*rhs_p, sprime))) | |
3246 | { | |
1e128c5f | 3247 | gcc_assert (sprime != *rhs_p); |
ff2ad0f7 | 3248 | |
7e6eb623 DB |
3249 | if (dump_file && (dump_flags & TDF_DETAILS)) |
3250 | { | |
3251 | fprintf (dump_file, "Replaced "); | |
ff2ad0f7 | 3252 | print_generic_expr (dump_file, *rhs_p, 0); |
7e6eb623 DB |
3253 | fprintf (dump_file, " with "); |
3254 | print_generic_expr (dump_file, sprime, 0); | |
3255 | fprintf (dump_file, " in "); | |
3256 | print_generic_stmt (dump_file, stmt, 0); | |
3257 | } | |
fe83f543 | 3258 | |
0fc6c492 DB |
3259 | if (TREE_CODE (sprime) == SSA_NAME) |
3260 | NECESSARY (SSA_NAME_DEF_STMT (sprime)) = 1; | |
fe83f543 AP |
3261 | /* We need to make sure the new and old types actually match, |
3262 | which may require adding a simple cast, which fold_convert | |
3263 | will do for us. */ | |
3264 | if (TREE_CODE (*rhs_p) != SSA_NAME | |
3265 | && !tree_ssa_useless_type_conversion_1 (TREE_TYPE (*rhs_p), | |
3266 | TREE_TYPE (sprime))) | |
3267 | sprime = fold_convert (TREE_TYPE (*rhs_p), sprime); | |
3268 | ||
7e6eb623 | 3269 | pre_stats.eliminations++; |
ff2ad0f7 | 3270 | propagate_tree_value (rhs_p, sprime); |
f430bae8 | 3271 | update_stmt (stmt); |
53b4bf74 DN |
3272 | |
3273 | /* If we removed EH side effects from the statement, clean | |
3274 | its EH information. */ | |
af47810a | 3275 | if (maybe_clean_or_replace_eh_stmt (stmt, stmt)) |
53b4bf74 DN |
3276 | { |
3277 | bitmap_set_bit (need_eh_cleanup, | |
3278 | bb_for_stmt (stmt)->index); | |
3279 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
3280 | fprintf (dump_file, " Removed EH side effects.\n"); | |
3281 | } | |
ff2ad0f7 DN |
3282 | } |
3283 | } | |
7e6eb623 DB |
3284 | } |
3285 | } | |
6de9cd9a DN |
3286 | } |
3287 | ||
0fc6c492 DB |
3288 | /* Borrow a bit of tree-ssa-dce.c for the moment. |
3289 | XXX: In 4.1, we should be able to just run a DCE pass after PRE, though | |
3290 | this may be a bit faster, and we may want critical edges kept split. */ | |
3291 | ||
3292 | /* If OP's defining statement has not already been determined to be necessary, | |
d4e6fecb NS |
3293 | mark that statement necessary. Return the stmt, if it is newly |
3294 | necessary. */ | |
0fc6c492 | 3295 | |
d4e6fecb NS |
3296 | static inline tree |
3297 | mark_operand_necessary (tree op) | |
0fc6c492 DB |
3298 | { |
3299 | tree stmt; | |
0fc6c492 DB |
3300 | |
3301 | gcc_assert (op); | |
3302 | ||
c90186eb DB |
3303 | if (TREE_CODE (op) != SSA_NAME) |
3304 | return NULL; | |
3305 | ||
0fc6c492 DB |
3306 | stmt = SSA_NAME_DEF_STMT (op); |
3307 | gcc_assert (stmt); | |
3308 | ||
3309 | if (NECESSARY (stmt) | |
3310 | || IS_EMPTY_STMT (stmt)) | |
d4e6fecb | 3311 | return NULL; |
0fc6c492 DB |
3312 | |
3313 | NECESSARY (stmt) = 1; | |
d4e6fecb | 3314 | return stmt; |
0fc6c492 DB |
3315 | } |
3316 | ||
3317 | /* Because we don't follow exactly the standard PRE algorithm, and decide not | |
3318 | to insert PHI nodes sometimes, and because value numbering of casts isn't | |
3319 | perfect, we sometimes end up inserting dead code. This simple DCE-like | |
3320 | pass removes any insertions we made that weren't actually used. */ | |
3321 | ||
3322 | static void | |
3323 | remove_dead_inserted_code (void) | |
3324 | { | |
d4e6fecb | 3325 | VEC(tree,heap) *worklist = NULL; |
0fc6c492 DB |
3326 | int i; |
3327 | tree t; | |
3328 | ||
d4e6fecb NS |
3329 | worklist = VEC_alloc (tree, heap, VEC_length (tree, inserted_exprs)); |
3330 | for (i = 0; VEC_iterate (tree, inserted_exprs, i, t); i++) | |
0fc6c492 DB |
3331 | { |
3332 | if (NECESSARY (t)) | |
d4e6fecb | 3333 | VEC_quick_push (tree, worklist, t); |
0fc6c492 | 3334 | } |
d4e6fecb | 3335 | while (VEC_length (tree, worklist) > 0) |
0fc6c492 | 3336 | { |
d4e6fecb | 3337 | t = VEC_pop (tree, worklist); |
c90186eb DB |
3338 | |
3339 | /* PHI nodes are somewhat special in that each PHI alternative has | |
3340 | data and control dependencies. All the statements feeding the | |
3341 | PHI node's arguments are always necessary. */ | |
0fc6c492 DB |
3342 | if (TREE_CODE (t) == PHI_NODE) |
3343 | { | |
0fc6c492 | 3344 | int k; |
d4e6fecb NS |
3345 | |
3346 | VEC_reserve (tree, heap, worklist, PHI_NUM_ARGS (t)); | |
0fc6c492 DB |
3347 | for (k = 0; k < PHI_NUM_ARGS (t); k++) |
3348 | { | |
3349 | tree arg = PHI_ARG_DEF (t, k); | |
3350 | if (TREE_CODE (arg) == SSA_NAME) | |
d4e6fecb NS |
3351 | { |
3352 | arg = mark_operand_necessary (arg); | |
3353 | if (arg) | |
3354 | VEC_quick_push (tree, worklist, arg); | |
3355 | } | |
0fc6c492 DB |
3356 | } |
3357 | } | |
3358 | else | |
3359 | { | |
3360 | /* Propagate through the operands. Examine all the USE, VUSE and | |
3361 | V_MAY_DEF operands in this statement. Mark all the statements | |
3362 | which feed this statement's uses as necessary. */ | |
3363 | ssa_op_iter iter; | |
3364 | tree use; | |
3365 | ||
0fc6c492 DB |
3366 | /* The operands of V_MAY_DEF expressions are also needed as they |
3367 | represent potential definitions that may reach this | |
3368 | statement (V_MAY_DEF operands allow us to follow def-def | |
3369 | links). */ | |
33c94679 | 3370 | |
0fc6c492 | 3371 | FOR_EACH_SSA_TREE_OPERAND (use, t, iter, SSA_OP_ALL_USES) |
d4e6fecb NS |
3372 | { |
3373 | tree n = mark_operand_necessary (use); | |
3374 | if (n) | |
3375 | VEC_safe_push (tree, heap, worklist, n); | |
3376 | } | |
0fc6c492 DB |
3377 | } |
3378 | } | |
c90186eb | 3379 | |
d4e6fecb | 3380 | for (i = 0; VEC_iterate (tree, inserted_exprs, i, t); i++) |
0fc6c492 DB |
3381 | { |
3382 | if (!NECESSARY (t)) | |
3383 | { | |
3384 | block_stmt_iterator bsi; | |
c90186eb | 3385 | |
0fc6c492 DB |
3386 | if (dump_file && (dump_flags & TDF_DETAILS)) |
3387 | { | |
3388 | fprintf (dump_file, "Removing unnecessary insertion:"); | |
3389 | print_generic_stmt (dump_file, t, 0); | |
3390 | } | |
c90186eb | 3391 | |
0fc6c492 DB |
3392 | if (TREE_CODE (t) == PHI_NODE) |
3393 | { | |
d19e3ef6 | 3394 | remove_phi_node (t, NULL); |
0fc6c492 DB |
3395 | } |
3396 | else | |
3397 | { | |
3398 | bsi = bsi_for_stmt (t); | |
3399 | bsi_remove (&bsi); | |
c90186eb | 3400 | release_defs (t); |
0fc6c492 DB |
3401 | } |
3402 | } | |
3403 | } | |
d4e6fecb | 3404 | VEC_free (tree, heap, worklist); |
0fc6c492 | 3405 | } |
c90186eb | 3406 | |
ff2ad0f7 | 3407 | /* Initialize data structures used by PRE. */ |
6de9cd9a DN |
3408 | |
3409 | static void | |
0fc6c492 | 3410 | init_pre (bool do_fre) |
6de9cd9a | 3411 | { |
7e6eb623 | 3412 | basic_block bb; |
81def1b7 DB |
3413 | |
3414 | in_fre = do_fre; | |
ff2ad0f7 | 3415 | |
0fc6c492 | 3416 | inserted_exprs = NULL; |
c90186eb DB |
3417 | need_creation = NULL; |
3418 | pretemp = NULL_TREE; | |
3419 | storetemp = NULL_TREE; | |
3420 | mergephitemp = NULL_TREE; | |
3421 | prephitemp = NULL_TREE; | |
3422 | ||
ff2ad0f7 | 3423 | vn_init (); |
0fc6c492 DB |
3424 | if (!do_fre) |
3425 | current_loops = loop_optimizer_init (dump_file); | |
c90186eb | 3426 | |
0fc6c492 | 3427 | connect_infinite_loops_to_exit (); |
7e6eb623 | 3428 | memset (&pre_stats, 0, sizeof (pre_stats)); |
53b4bf74 DN |
3429 | |
3430 | /* If block 0 has more than one predecessor, it means that its PHI | |
3431 | nodes will have arguments coming from block -1. This creates | |
3432 | problems for several places in PRE that keep local arrays indexed | |
3433 | by block number. To prevent this, we split the edge coming from | |
3434 | ENTRY_BLOCK_PTR (FIXME, if ENTRY_BLOCK_PTR had an index number | |
3435 | different than -1 we wouldn't have to hack this. tree-ssa-dce.c | |
3436 | needs a similar change). */ | |
c5cbcccf ZD |
3437 | if (!single_pred_p (single_succ (ENTRY_BLOCK_PTR))) |
3438 | if (!(single_succ_edge (ENTRY_BLOCK_PTR)->flags & EDGE_ABNORMAL)) | |
3439 | split_edge (single_succ_edge (ENTRY_BLOCK_PTR)); | |
53b4bf74 | 3440 | |
7e6eb623 | 3441 | FOR_ALL_BB (bb) |
ff2ad0f7 DN |
3442 | bb->aux = xcalloc (1, sizeof (struct bb_value_sets)); |
3443 | ||
7932a3db | 3444 | bitmap_obstack_initialize (&grand_bitmap_obstack); |
7e6eb623 | 3445 | phi_translate_table = htab_create (511, expr_pred_trans_hash, |
ff2ad0f7 | 3446 | expr_pred_trans_eq, free); |
7e6eb623 DB |
3447 | value_set_pool = create_alloc_pool ("Value sets", |
3448 | sizeof (struct value_set), 30); | |
bdee7684 DB |
3449 | bitmap_set_pool = create_alloc_pool ("Bitmap sets", |
3450 | sizeof (struct bitmap_set), 30); | |
7e6eb623 | 3451 | value_set_node_pool = create_alloc_pool ("Value set nodes", |
ff2ad0f7 | 3452 | sizeof (struct value_set_node), 30); |
7e6eb623 | 3453 | calculate_dominance_info (CDI_POST_DOMINATORS); |
6de9cd9a | 3454 | calculate_dominance_info (CDI_DOMINATORS); |
a38b644b ZW |
3455 | binary_node_pool = create_alloc_pool ("Binary tree nodes", |
3456 | tree_code_size (PLUS_EXPR), 30); | |
3457 | unary_node_pool = create_alloc_pool ("Unary tree nodes", | |
3458 | tree_code_size (NEGATE_EXPR), 30); | |
3459 | reference_node_pool = create_alloc_pool ("Reference tree nodes", | |
6048b706 | 3460 | tree_code_size (ARRAY_REF), 30); |
43da81be DB |
3461 | expression_node_pool = create_alloc_pool ("Expression tree nodes", |
3462 | tree_code_size (CALL_EXPR), 30); | |
3463 | list_node_pool = create_alloc_pool ("List tree nodes", | |
3464 | tree_code_size (TREE_LIST), 30); | |
3465 | comparison_node_pool = create_alloc_pool ("Comparison tree nodes", | |
3466 | tree_code_size (EQ_EXPR), 30); | |
c90186eb DB |
3467 | modify_expr_node_pool = create_alloc_pool ("MODIFY_EXPR nodes", |
3468 | tree_code_size (MODIFY_EXPR), | |
3469 | 30); | |
3470 | modify_expr_template = NULL; | |
3471 | ||
7e6eb623 DB |
3472 | FOR_ALL_BB (bb) |
3473 | { | |
3474 | EXP_GEN (bb) = set_new (true); | |
6b416da1 DB |
3475 | PHI_GEN (bb) = bitmap_set_new (); |
3476 | TMP_GEN (bb) = bitmap_set_new (); | |
bdee7684 | 3477 | AVAIL_OUT (bb) = bitmap_set_new (); |
7e6eb623 | 3478 | } |
53b4bf74 | 3479 | |
8bdbfff5 | 3480 | need_eh_cleanup = BITMAP_ALLOC (NULL); |
ff2ad0f7 DN |
3481 | } |
3482 | ||
3483 | ||
3484 | /* Deallocate data structures used by PRE. */ | |
6de9cd9a | 3485 | |
ff2ad0f7 | 3486 | static void |
0fc6c492 | 3487 | fini_pre (bool do_fre) |
ff2ad0f7 DN |
3488 | { |
3489 | basic_block bb; | |
3aecd08b JL |
3490 | unsigned int i; |
3491 | ||
d4e6fecb | 3492 | VEC_free (tree, heap, inserted_exprs); |
c90186eb | 3493 | VEC_free (tree, heap, need_creation); |
7932a3db | 3494 | bitmap_obstack_release (&grand_bitmap_obstack); |
ff2ad0f7 | 3495 | free_alloc_pool (value_set_pool); |
bdee7684 | 3496 | free_alloc_pool (bitmap_set_pool); |
ff2ad0f7 DN |
3497 | free_alloc_pool (value_set_node_pool); |
3498 | free_alloc_pool (binary_node_pool); | |
3d3fa3a1 | 3499 | free_alloc_pool (reference_node_pool); |
ff2ad0f7 | 3500 | free_alloc_pool (unary_node_pool); |
43da81be DB |
3501 | free_alloc_pool (list_node_pool); |
3502 | free_alloc_pool (expression_node_pool); | |
3503 | free_alloc_pool (comparison_node_pool); | |
c90186eb | 3504 | free_alloc_pool (modify_expr_node_pool); |
ff2ad0f7 | 3505 | htab_delete (phi_translate_table); |
6809cbf9 | 3506 | remove_fake_exit_edges (); |
50265400 | 3507 | |
ff2ad0f7 DN |
3508 | FOR_ALL_BB (bb) |
3509 | { | |
3510 | free (bb->aux); | |
3511 | bb->aux = NULL; | |
3512 | } | |
6809cbf9 | 3513 | |
ff2ad0f7 DN |
3514 | free_dominance_info (CDI_POST_DOMINATORS); |
3515 | vn_delete (); | |
53b4bf74 | 3516 | |
eb59b8de | 3517 | if (!bitmap_empty_p (need_eh_cleanup)) |
53b4bf74 DN |
3518 | { |
3519 | tree_purge_all_dead_eh_edges (need_eh_cleanup); | |
3520 | cleanup_tree_cfg (); | |
3521 | } | |
3522 | ||
8bdbfff5 | 3523 | BITMAP_FREE (need_eh_cleanup); |
3aecd08b JL |
3524 | |
3525 | /* Wipe out pointers to VALUE_HANDLEs. In the not terribly distant | |
3526 | future we will want them to be persistent though. */ | |
3527 | for (i = 0; i < num_ssa_names; i++) | |
3528 | { | |
3529 | tree name = ssa_name (i); | |
3530 | ||
3531 | if (!name) | |
3532 | continue; | |
3533 | ||
3534 | if (SSA_NAME_VALUE (name) | |
3535 | && TREE_CODE (SSA_NAME_VALUE (name)) == VALUE_HANDLE) | |
3536 | SSA_NAME_VALUE (name) = NULL; | |
3537 | } | |
0fc6c492 DB |
3538 | if (!do_fre && current_loops) |
3539 | { | |
3540 | loop_optimizer_finalize (current_loops, dump_file); | |
3541 | current_loops = NULL; | |
3542 | } | |
ff2ad0f7 DN |
3543 | } |
3544 | ||
ff2ad0f7 DN |
3545 | /* Main entry point to the SSA-PRE pass. DO_FRE is true if the caller |
3546 | only wants to do full redundancy elimination. */ | |
3547 | ||
3548 | static void | |
3549 | execute_pre (bool do_fre) | |
3550 | { | |
0fc6c492 | 3551 | init_pre (do_fre); |
ff2ad0f7 | 3552 | |
c90186eb DB |
3553 | if (!do_fre) |
3554 | insert_fake_stores (); | |
3555 | ||
665fcad8 SB |
3556 | /* Collect and value number expressions computed in each basic block. */ |
3557 | compute_avail (); | |
6de9cd9a | 3558 | |
7e6eb623 DB |
3559 | if (dump_file && (dump_flags & TDF_DETAILS)) |
3560 | { | |
ff2ad0f7 DN |
3561 | basic_block bb; |
3562 | ||
7e6eb623 DB |
3563 | FOR_ALL_BB (bb) |
3564 | { | |
3565 | print_value_set (dump_file, EXP_GEN (bb), "exp_gen", bb->index); | |
6b416da1 DB |
3566 | bitmap_print_value_set (dump_file, TMP_GEN (bb), "tmp_gen", |
3567 | bb->index); | |
bdee7684 DB |
3568 | bitmap_print_value_set (dump_file, AVAIL_OUT (bb), "avail_out", |
3569 | bb->index); | |
7e6eb623 DB |
3570 | } |
3571 | } | |
6de9cd9a | 3572 | |
7e6eb623 DB |
3573 | /* Insert can get quite slow on an incredibly large number of basic |
3574 | blocks due to some quadratic behavior. Until this behavior is | |
3575 | fixed, don't run it when he have an incredibly large number of | |
3576 | bb's. If we aren't going to run insert, there is no point in | |
3577 | computing ANTIC, either, even though it's plenty fast. */ | |
ff2ad0f7 | 3578 | if (!do_fre && n_basic_blocks < 4000) |
6de9cd9a | 3579 | { |
c90186eb DB |
3580 | vuse_names = xcalloc (num_ssa_names, sizeof (bitmap)); |
3581 | compute_rvuse (); | |
7e6eb623 | 3582 | compute_antic (); |
7e6eb623 | 3583 | insert (); |
c90186eb | 3584 | free (vuse_names); |
7e6eb623 | 3585 | } |
ff2ad0f7 DN |
3586 | |
3587 | /* Remove all the redundant expressions. */ | |
7e6eb623 | 3588 | eliminate (); |
0fc6c492 DB |
3589 | |
3590 | ||
7e6eb623 DB |
3591 | if (dump_file && (dump_flags & TDF_STATS)) |
3592 | { | |
b89361c6 DB |
3593 | fprintf (dump_file, "Insertions: %d\n", pre_stats.insertions); |
3594 | fprintf (dump_file, "New PHIs: %d\n", pre_stats.phis); | |
3595 | fprintf (dump_file, "Eliminated: %d\n", pre_stats.eliminations); | |
3596 | fprintf (dump_file, "Constified: %d\n", pre_stats.constified); | |
6de9cd9a | 3597 | } |
0fc6c492 DB |
3598 | |
3599 | bsi_commit_edge_inserts (); | |
c90186eb | 3600 | |
0fc6c492 | 3601 | if (!do_fre) |
c90186eb DB |
3602 | { |
3603 | remove_dead_inserted_code (); | |
3604 | realify_fake_stores (); | |
3605 | } | |
3606 | ||
0fc6c492 | 3607 | fini_pre (do_fre); |
6de9cd9a | 3608 | |
ff2ad0f7 DN |
3609 | } |
3610 | ||
ff2ad0f7 DN |
3611 | /* Gate and execute functions for PRE. */ |
3612 | ||
3613 | static void | |
3614 | do_pre (void) | |
3615 | { | |
3616 | execute_pre (false); | |
6de9cd9a DN |
3617 | } |
3618 | ||
3619 | static bool | |
3620 | gate_pre (void) | |
3621 | { | |
3622 | return flag_tree_pre != 0; | |
3623 | } | |
3624 | ||
7e6eb623 | 3625 | struct tree_opt_pass pass_pre = |
6de9cd9a DN |
3626 | { |
3627 | "pre", /* name */ | |
3628 | gate_pre, /* gate */ | |
ff2ad0f7 | 3629 | do_pre, /* execute */ |
6de9cd9a DN |
3630 | NULL, /* sub */ |
3631 | NULL, /* next */ | |
3632 | 0, /* static_pass_number */ | |
3633 | TV_TREE_PRE, /* tv_id */ | |
c1b763fa DN |
3634 | PROP_no_crit_edges | PROP_cfg |
3635 | | PROP_ssa | PROP_alias, /* properties_required */ | |
6de9cd9a DN |
3636 | 0, /* properties_provided */ |
3637 | 0, /* properties_destroyed */ | |
3638 | 0, /* todo_flags_start */ | |
43da81be DB |
3639 | TODO_update_ssa | TODO_dump_func | TODO_ggc_collect |
3640 | | TODO_verify_ssa, /* todo_flags_finish */ | |
9f8628ba | 3641 | 0 /* letter */ |
6de9cd9a | 3642 | }; |
ff2ad0f7 DN |
3643 | |
3644 | ||
3645 | /* Gate and execute functions for FRE. */ | |
3646 | ||
3647 | static void | |
b89361c6 | 3648 | execute_fre (void) |
ff2ad0f7 DN |
3649 | { |
3650 | execute_pre (true); | |
3651 | } | |
3652 | ||
3653 | static bool | |
3654 | gate_fre (void) | |
3655 | { | |
3656 | return flag_tree_fre != 0; | |
3657 | } | |
3658 | ||
3659 | struct tree_opt_pass pass_fre = | |
3660 | { | |
3661 | "fre", /* name */ | |
3662 | gate_fre, /* gate */ | |
b89361c6 | 3663 | execute_fre, /* execute */ |
ff2ad0f7 DN |
3664 | NULL, /* sub */ |
3665 | NULL, /* next */ | |
3666 | 0, /* static_pass_number */ | |
3667 | TV_TREE_FRE, /* tv_id */ | |
c1b763fa | 3668 | PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */ |
ff2ad0f7 DN |
3669 | 0, /* properties_provided */ |
3670 | 0, /* properties_destroyed */ | |
3671 | 0, /* todo_flags_start */ | |
9f8628ba PB |
3672 | TODO_dump_func | TODO_ggc_collect | TODO_verify_ssa, /* todo_flags_finish */ |
3673 | 0 /* letter */ | |
ff2ad0f7 | 3674 | }; |
45159bf6 | 3675 |