]>
Commit | Line | Data |
---|---|---|
6de9cd9a DN |
1 | /* SSA-PRE for trees. |
2 | Copyright (C) 2001, 2002, 2003, 2004 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 | |
20 | the Free Software Foundation, 59 Temple Place - Suite 330, | |
21 | Boston, MA 02111-1307, USA. */ | |
33c94679 | 22 | |
6de9cd9a DN |
23 | #include "config.h" |
24 | #include "system.h" | |
25 | #include "coretypes.h" | |
26 | #include "tm.h" | |
27 | #include "errors.h" | |
28 | #include "ggc.h" | |
29 | #include "tree.h" | |
6de9cd9a DN |
30 | #include "basic-block.h" |
31 | #include "diagnostic.h" | |
32 | #include "tree-inline.h" | |
33 | #include "tree-flow.h" | |
eadf906f | 34 | #include "tree-gimple.h" |
6de9cd9a DN |
35 | #include "tree-dump.h" |
36 | #include "timevar.h" | |
37 | #include "fibheap.h" | |
38 | #include "hashtab.h" | |
39 | #include "tree-iterator.h" | |
40 | #include "real.h" | |
41 | #include "alloc-pool.h" | |
42 | #include "tree-pass.h" | |
43 | #include "flags.h" | |
7e6eb623 DB |
44 | #include "splay-tree.h" |
45 | #include "bitmap.h" | |
46 | #include "langhooks.h" | |
33c94679 | 47 | |
7e6eb623 | 48 | /* TODO: |
6de9cd9a | 49 | |
bdee7684 | 50 | 1. Avail sets can be shared by making an avail_find_leader that |
7e6eb623 DB |
51 | walks up the dominator tree and looks in those avail sets. |
52 | This might affect code optimality, it's unclear right now. | |
bdee7684 | 53 | 2. Load motion can be performed by value numbering the loads the |
7e6eb623 DB |
54 | same as we do other expressions. This requires iterative |
55 | hashing the vuses into the values. Right now we simply assign | |
56 | a new value every time we see a statement with a vuse. | |
bdee7684 | 57 | 3. Strength reduction can be performed by anticipating expressions |
7e6eb623 | 58 | we can repair later on. |
bdee7684 | 59 | 4. Our canonicalization of expressions during lookups don't take |
56db793a DB |
60 | constants into account very well. In particular, we don't fold |
61 | anywhere, so we can get situations where we stupidly think | |
62 | something is a new value (a + 1 + 1 vs a + 2). This is somewhat | |
63 | expensive to fix, but it does expose a lot more eliminations. | |
64 | It may or not be worth it, depending on how critical you | |
65 | consider PRE vs just plain GRE. | |
7e6eb623 DB |
66 | */ |
67 | ||
68 | /* For ease of terminology, "expression node" in the below refers to | |
69 | every expression node but MODIFY_EXPR, because MODIFY_EXPR's represent | |
70 | the actual statement containing the expressions we care about, and | |
71 | we cache the value number by putting it in the expression. */ | |
72 | ||
73 | /* Basic algorithm | |
6de9cd9a | 74 | |
56db793a DB |
75 | First we walk the statements to generate the AVAIL sets, the |
76 | EXP_GEN sets, and the tmp_gen sets. EXP_GEN sets represent the | |
77 | generation of values/expressions by a given block. We use them | |
78 | when computing the ANTIC sets. The AVAIL sets consist of | |
79 | SSA_NAME's that represent values, so we know what values are | |
80 | available in what blocks. AVAIL is a forward dataflow problem. In | |
81 | SSA, values are never killed, so we don't need a kill set, or a | |
82 | fixpoint iteration, in order to calculate the AVAIL sets. In | |
83 | traditional parlance, AVAIL sets tell us the downsafety of the | |
7e6eb623 | 84 | expressions/values. |
6de9cd9a | 85 | |
56db793a DB |
86 | Next, we generate the ANTIC sets. These sets represent the |
87 | anticipatable expressions. ANTIC is a backwards dataflow | |
88 | problem.An expression is anticipatable in a given block if it could | |
89 | be generated in that block. This means that if we had to perform | |
90 | an insertion in that block, of the value of that expression, we | |
91 | could. Calculating the ANTIC sets requires phi translation of | |
92 | expressions, because the flow goes backwards through phis. We must | |
93 | iterate to a fixpoint of the ANTIC sets, because we have a kill | |
94 | set. Even in SSA form, values are not live over the entire | |
95 | function, only from their definition point onwards. So we have to | |
96 | remove values from the ANTIC set once we go past the definition | |
97 | point of the leaders that make them up. | |
98 | compute_antic/compute_antic_aux performs this computation. | |
7e6eb623 DB |
99 | |
100 | Third, we perform insertions to make partially redundant | |
101 | expressions fully redundant. | |
102 | ||
103 | An expression is partially redundant (excluding partial | |
104 | anticipation) if: | |
105 | ||
106 | 1. It is AVAIL in some, but not all, of the predecessors of a | |
107 | given block. | |
108 | 2. It is ANTIC in all the predecessors. | |
109 | ||
110 | In order to make it fully redundant, we insert the expression into | |
111 | the predecessors where it is not available, but is ANTIC. | |
112 | insert/insert_aux performs this insertion. | |
113 | ||
114 | Fourth, we eliminate fully redundant expressions. | |
115 | This is a simple statement walk that replaces redundant | |
116 | calculations with the now available values. */ | |
117 | ||
118 | /* Representations of value numbers: | |
119 | ||
120 | Value numbers are represented using the "value handle" approach. | |
121 | This means that each SSA_NAME (and for other reasons to be | |
56db793a DB |
122 | disclosed in a moment, expression nodes) has a value handle that |
123 | can be retrieved through get_value_handle. This value handle, *is* | |
124 | the value number of the SSA_NAME. You can pointer compare the | |
125 | value handles for equivalence purposes. | |
7e6eb623 DB |
126 | |
127 | For debugging reasons, the value handle is internally more than | |
128 | just a number, it is a VAR_DECL named "value.x", where x is a | |
129 | unique number for each value number in use. This allows | |
130 | expressions with SSA_NAMES replaced by value handles to still be | |
131 | pretty printed in a sane way. They simply print as "value.3 * | |
132 | value.5", etc. | |
133 | ||
134 | Expression nodes have value handles associated with them as a | |
135 | cache. Otherwise, we'd have to look them up again in the hash | |
136 | table This makes significant difference (factor of two or more) on | |
56db793a DB |
137 | some test cases. They can be thrown away after the pass is |
138 | finished. */ | |
7e6eb623 DB |
139 | |
140 | /* Representation of expressions on value numbers: | |
141 | ||
142 | In some portions of this code, you will notice we allocate "fake" | |
143 | analogues to the expression we are value numbering, and replace the | |
144 | operands with the values of the expression. Since we work on | |
145 | values, and not just names, we canonicalize expressions to value | |
146 | expressions for use in the ANTIC sets, the EXP_GEN set, etc. | |
147 | ||
148 | This is theoretically unnecessary, it just saves a bunch of | |
149 | repeated get_value_handle and find_leader calls in the remainder of | |
150 | the code, trading off temporary memory usage for speed. The tree | |
151 | nodes aren't actually creating more garbage, since they are | |
152 | allocated in a special pools which are thrown away at the end of | |
153 | this pass. | |
154 | ||
155 | All of this also means that if you print the EXP_GEN or ANTIC sets, | |
156 | you will see "value.5 + value.7" in the set, instead of "a_55 + | |
157 | b_66" or something. The only thing that actually cares about | |
158 | seeing the value leaders is phi translation, and it needs to be | |
159 | able to find the leader for a value in an arbitrary block, so this | |
160 | "value expression" form is perfect for it (otherwise you'd do | |
161 | get_value_handle->find_leader->translate->get_value_handle->find_leader).*/ | |
162 | ||
163 | ||
164 | /* Representation of sets: | |
165 | ||
bdee7684 DB |
166 | There are currently two types of sets used, hopefully to be unified soon. |
167 | The AVAIL sets do not need to be sorted in any particular order, | |
168 | and thus, are simply represented as two bitmaps, one that keeps | |
169 | track of values present in the set, and one that keeps track of | |
170 | expressions present in the set. | |
171 | ||
172 | The other sets are represented as doubly linked lists kept in topological | |
7e6eb623 | 173 | order, with an optional supporting bitmap of values present in the |
56db793a DB |
174 | set. The sets represent values, and the elements can be values or |
175 | expressions. The elements can appear in different sets, but each | |
176 | element can only appear once in each set. | |
7e6eb623 DB |
177 | |
178 | Since each node in the set represents a value, we also want to be | |
179 | able to map expression, set pairs to something that tells us | |
180 | whether the value is present is a set. We use a per-set bitmap for | |
181 | that. The value handles also point to a linked list of the | |
182 | expressions they represent via a tree annotation. This is mainly | |
183 | useful only for debugging, since we don't do identity lookups. */ | |
184 | ||
185 | ||
186 | /* A value set element. Basically a single linked list of | |
56db793a | 187 | expressions/values. */ |
7e6eb623 | 188 | typedef struct value_set_node |
6de9cd9a | 189 | { |
ca072a31 | 190 | /* An expression. */ |
7e6eb623 | 191 | tree expr; |
ca072a31 DB |
192 | |
193 | /* A pointer to the next element of the value set. */ | |
7e6eb623 DB |
194 | struct value_set_node *next; |
195 | } *value_set_node_t; | |
6de9cd9a | 196 | |
6de9cd9a | 197 | |
ca072a31 DB |
198 | /* A value set. This is a singly linked list of value_set_node |
199 | elements with a possible bitmap that tells us what values exist in | |
200 | the set. This set must be kept in topologically sorted order. */ | |
7e6eb623 DB |
201 | typedef struct value_set |
202 | { | |
ca072a31 DB |
203 | /* The head of the list. Used for iterating over the list in |
204 | order. */ | |
7e6eb623 | 205 | value_set_node_t head; |
ca072a31 DB |
206 | |
207 | /* The tail of the list. Used for tail insertions, which are | |
208 | necessary to keep the set in topologically sorted order because | |
209 | of how the set is built. */ | |
7e6eb623 | 210 | value_set_node_t tail; |
ca072a31 DB |
211 | |
212 | /* The length of the list. */ | |
7e6eb623 | 213 | size_t length; |
ca072a31 DB |
214 | |
215 | /* True if the set is indexed, which means it contains a backing | |
216 | bitmap for quick determination of whether certain values exist in the | |
217 | set. */ | |
7e6eb623 | 218 | bool indexed; |
ca072a31 DB |
219 | |
220 | /* The bitmap of values that exist in the set. May be NULL in an | |
221 | empty or non-indexed set. */ | |
7e6eb623 | 222 | bitmap values; |
6de9cd9a | 223 | |
7e6eb623 | 224 | } *value_set_t; |
6de9cd9a | 225 | |
bdee7684 DB |
226 | |
227 | /* An unordered bitmap set. One bitmap tracks values, the other, | |
8c27b7d4 | 228 | expressions. */ |
bdee7684 DB |
229 | typedef struct bitmap_set |
230 | { | |
231 | bitmap expressions; | |
232 | bitmap values; | |
233 | } *bitmap_set_t; | |
234 | ||
6b416da1 | 235 | /* Sets that we need to keep track of. */ |
7e6eb623 | 236 | typedef struct bb_value_sets |
6de9cd9a | 237 | { |
ca072a31 DB |
238 | /* The EXP_GEN set, which represents expressions/values generated in |
239 | a basic block. */ | |
7e6eb623 | 240 | value_set_t exp_gen; |
ca072a31 DB |
241 | |
242 | /* The PHI_GEN set, which represents PHI results generated in a | |
243 | basic block. */ | |
6b416da1 | 244 | bitmap_set_t phi_gen; |
ca072a31 | 245 | |
f6fe65dc | 246 | /* The TMP_GEN set, which represents results/temporaries generated |
ca072a31 | 247 | in a basic block. IE the LHS of an expression. */ |
6b416da1 | 248 | bitmap_set_t tmp_gen; |
ca072a31 DB |
249 | |
250 | /* The AVAIL_OUT set, which represents which values are available in | |
251 | a given basic block. */ | |
bdee7684 | 252 | bitmap_set_t avail_out; |
ca072a31 DB |
253 | |
254 | /* The ANTIC_IN set, which represents which values are anticiptable | |
255 | in a given basic block. */ | |
7e6eb623 | 256 | value_set_t antic_in; |
ca072a31 DB |
257 | |
258 | /* The NEW_SETS set, which is used during insertion to augment the | |
259 | AVAIL_OUT set of blocks with the new insertions performed during | |
260 | the current iteration. */ | |
6b416da1 | 261 | bitmap_set_t new_sets; |
7e6eb623 DB |
262 | } *bb_value_sets_t; |
263 | ||
264 | #define EXP_GEN(BB) ((bb_value_sets_t) ((BB)->aux))->exp_gen | |
265 | #define PHI_GEN(BB) ((bb_value_sets_t) ((BB)->aux))->phi_gen | |
266 | #define TMP_GEN(BB) ((bb_value_sets_t) ((BB)->aux))->tmp_gen | |
267 | #define AVAIL_OUT(BB) ((bb_value_sets_t) ((BB)->aux))->avail_out | |
268 | #define ANTIC_IN(BB) ((bb_value_sets_t) ((BB)->aux))->antic_in | |
269 | #define NEW_SETS(BB) ((bb_value_sets_t) ((BB)->aux))->new_sets | |
6de9cd9a | 270 | |
ca072a31 DB |
271 | /* This structure is used to keep track of statistics on what |
272 | optimization PRE was able to perform. */ | |
7e6eb623 | 273 | static struct |
6de9cd9a | 274 | { |
ca072a31 | 275 | /* The number of RHS computations eliminated by PRE. */ |
7e6eb623 | 276 | int eliminations; |
ca072a31 DB |
277 | |
278 | /* The number of new expressions/temporaries generated by PRE. */ | |
7e6eb623 | 279 | int insertions; |
ca072a31 DB |
280 | |
281 | /* The number of new PHI nodes added by PRE. */ | |
7e6eb623 DB |
282 | int phis; |
283 | } pre_stats; | |
6de9cd9a | 284 | |
bdee7684 DB |
285 | |
286 | static tree bitmap_find_leader (bitmap_set_t, tree); | |
7e6eb623 DB |
287 | static tree find_leader (value_set_t, tree); |
288 | static void value_insert_into_set (value_set_t, tree); | |
bdee7684 DB |
289 | static void bitmap_value_insert_into_set (bitmap_set_t, tree); |
290 | static void bitmap_value_replace_in_set (bitmap_set_t, tree); | |
7e6eb623 | 291 | static void insert_into_set (value_set_t, tree); |
bdee7684 DB |
292 | static void bitmap_set_copy (bitmap_set_t, bitmap_set_t); |
293 | static bool bitmap_set_contains_value (bitmap_set_t, tree); | |
294 | static bitmap_set_t bitmap_set_new (void); | |
7e6eb623 DB |
295 | static value_set_t set_new (bool); |
296 | static bool is_undefined_value (tree); | |
56db793a | 297 | static tree create_expression_by_pieces (basic_block, tree, tree); |
6de9cd9a | 298 | |
bdee7684 | 299 | |
7e6eb623 DB |
300 | /* We can add and remove elements and entries to and from sets |
301 | and hash tables, so we use alloc pools for them. */ | |
6de9cd9a | 302 | |
7e6eb623 | 303 | static alloc_pool value_set_pool; |
bdee7684 | 304 | static alloc_pool bitmap_set_pool; |
7e6eb623 DB |
305 | static alloc_pool value_set_node_pool; |
306 | static alloc_pool binary_node_pool; | |
307 | static alloc_pool unary_node_pool; | |
3d3fa3a1 | 308 | static alloc_pool reference_node_pool; |
c4817ba6 | 309 | static struct obstack grand_bitmap_obstack; |
6de9cd9a | 310 | |
53b4bf74 DN |
311 | /* Set of blocks with statements that have had its EH information |
312 | cleaned up. */ | |
313 | static bitmap need_eh_cleanup; | |
314 | ||
7e6eb623 DB |
315 | /* The phi_translate_table caches phi translations for a given |
316 | expression and predecessor. */ | |
ca072a31 | 317 | |
7e6eb623 | 318 | static htab_t phi_translate_table; |
6de9cd9a | 319 | |
7e6eb623 DB |
320 | /* A three tuple {e, pred, v} used to cache phi translations in the |
321 | phi_translate_table. */ | |
6de9cd9a | 322 | |
7e6eb623 | 323 | typedef struct expr_pred_trans_d |
6de9cd9a | 324 | { |
8c27b7d4 | 325 | /* The expression. */ |
7e6eb623 | 326 | tree e; |
ca072a31 DB |
327 | |
328 | /* The predecessor block along which we translated the expression. */ | |
7e6eb623 | 329 | basic_block pred; |
ca072a31 DB |
330 | |
331 | /* The value that resulted from the translation. */ | |
7e6eb623 | 332 | tree v; |
ca072a31 DB |
333 | |
334 | /* The hashcode for the expression, pred pair. This is cached for | |
335 | speed reasons. */ | |
7e6eb623 DB |
336 | hashval_t hashcode; |
337 | } *expr_pred_trans_t; | |
6de9cd9a | 338 | |
7e6eb623 | 339 | /* Return the hash value for a phi translation table entry. */ |
6de9cd9a | 340 | |
7e6eb623 DB |
341 | static hashval_t |
342 | expr_pred_trans_hash (const void *p) | |
343 | { | |
344 | const expr_pred_trans_t ve = (expr_pred_trans_t) p; | |
345 | return ve->hashcode; | |
346 | } | |
6de9cd9a | 347 | |
ca072a31 DB |
348 | /* Return true if two phi translation table entries are the same. |
349 | P1 and P2 should point to the expr_pred_trans_t's to be compared.*/ | |
7e6eb623 DB |
350 | |
351 | static int | |
352 | expr_pred_trans_eq (const void *p1, const void *p2) | |
353 | { | |
354 | const expr_pred_trans_t ve1 = (expr_pred_trans_t) p1; | |
355 | const expr_pred_trans_t ve2 = (expr_pred_trans_t) p2; | |
7e6eb623 DB |
356 | basic_block b1 = ve1->pred; |
357 | basic_block b2 = ve2->pred; | |
7e6eb623 | 358 | |
ca072a31 DB |
359 | |
360 | /* If they are not translations for the same basic block, they can't | |
361 | be equal. */ | |
7e6eb623 | 362 | if (b1 != b2) |
6de9cd9a | 363 | return false; |
6de9cd9a | 364 | |
ca072a31 | 365 | /* If they are for the same basic block, determine if the |
471854f8 | 366 | expressions are equal. */ |
ca072a31 | 367 | if (expressions_equal_p (ve1->e, ve2->e)) |
7e6eb623 DB |
368 | return true; |
369 | ||
370 | return false; | |
6de9cd9a DN |
371 | } |
372 | ||
ca072a31 DB |
373 | /* Search in the phi translation table for the translation of |
374 | expression E in basic block PRED. Return the translated value, if | |
8c27b7d4 | 375 | found, NULL otherwise. */ |
6de9cd9a DN |
376 | |
377 | static inline tree | |
7e6eb623 | 378 | phi_trans_lookup (tree e, basic_block pred) |
6de9cd9a | 379 | { |
7e6eb623 | 380 | void **slot; |
ca072a31 DB |
381 | struct expr_pred_trans_d ept; |
382 | ept.e = e; | |
383 | ept.pred = pred; | |
ff2ad0f7 | 384 | ept.hashcode = vn_compute (e, (unsigned long) pred, NULL); |
ca072a31 | 385 | slot = htab_find_slot_with_hash (phi_translate_table, &ept, ept.hashcode, |
7e6eb623 DB |
386 | NO_INSERT); |
387 | if (!slot) | |
388 | return NULL; | |
389 | else | |
390 | return ((expr_pred_trans_t) *slot)->v; | |
391 | } | |
6de9cd9a | 392 | |
6de9cd9a | 393 | |
ca072a31 DB |
394 | /* Add the tuple mapping from {expression E, basic block PRED} to |
395 | value V, to the phi translation table. */ | |
7e6eb623 DB |
396 | |
397 | static inline void | |
398 | phi_trans_add (tree e, tree v, basic_block pred) | |
399 | { | |
400 | void **slot; | |
401 | expr_pred_trans_t new_pair = xmalloc (sizeof (*new_pair)); | |
402 | new_pair->e = e; | |
403 | new_pair->pred = pred; | |
404 | new_pair->v = v; | |
ff2ad0f7 | 405 | new_pair->hashcode = vn_compute (e, (unsigned long) pred, NULL); |
7e6eb623 DB |
406 | slot = htab_find_slot_with_hash (phi_translate_table, new_pair, |
407 | new_pair->hashcode, INSERT); | |
408 | if (*slot) | |
409 | free (*slot); | |
410 | *slot = (void *) new_pair; | |
6de9cd9a DN |
411 | } |
412 | ||
ff2ad0f7 | 413 | |
ca072a31 | 414 | /* Add expression E to the expression set of value V. */ |
6de9cd9a | 415 | |
33c94679 | 416 | void |
7e6eb623 | 417 | add_to_value (tree v, tree e) |
6de9cd9a | 418 | { |
bddeccfe DN |
419 | /* Constants have no expression sets. */ |
420 | if (is_gimple_min_invariant (v)) | |
56db793a | 421 | return; |
6de9cd9a | 422 | |
33c94679 DN |
423 | if (VALUE_HANDLE_EXPR_SET (v) == NULL) |
424 | VALUE_HANDLE_EXPR_SET (v) = set_new (false); | |
7e6eb623 | 425 | |
33c94679 | 426 | insert_into_set (VALUE_HANDLE_EXPR_SET (v), e); |
7e6eb623 | 427 | } |
6de9cd9a | 428 | |
6de9cd9a | 429 | |
ca072a31 | 430 | /* Return true if value V exists in the bitmap for SET. */ |
6de9cd9a DN |
431 | |
432 | static inline bool | |
ca072a31 | 433 | value_exists_in_set_bitmap (value_set_t set, tree v) |
6de9cd9a | 434 | { |
7e6eb623 DB |
435 | if (!set->values) |
436 | return false; | |
33c94679 DN |
437 | |
438 | return bitmap_bit_p (set->values, VALUE_HANDLE_ID (v)); | |
6de9cd9a DN |
439 | } |
440 | ||
33c94679 | 441 | |
ca072a31 | 442 | /* Remove value V from the bitmap for SET. */ |
6de9cd9a | 443 | |
7e6eb623 | 444 | static void |
ca072a31 | 445 | value_remove_from_set_bitmap (value_set_t set, tree v) |
7e6eb623 | 446 | { |
1e128c5f | 447 | gcc_assert (set->indexed); |
33c94679 | 448 | |
7e6eb623 DB |
449 | if (!set->values) |
450 | return; | |
33c94679 DN |
451 | |
452 | bitmap_clear_bit (set->values, VALUE_HANDLE_ID (v)); | |
7e6eb623 | 453 | } |
6de9cd9a | 454 | |
6de9cd9a | 455 | |
ca072a31 | 456 | /* Insert the value number V into the bitmap of values existing in |
7e6eb623 | 457 | SET. */ |
6de9cd9a | 458 | |
7e6eb623 | 459 | static inline void |
ca072a31 | 460 | value_insert_into_set_bitmap (value_set_t set, tree v) |
6de9cd9a | 461 | { |
1e128c5f | 462 | gcc_assert (set->indexed); |
33c94679 | 463 | |
7e6eb623 | 464 | if (set->values == NULL) |
6de9cd9a | 465 | { |
c4817ba6 | 466 | set->values = BITMAP_OBSTACK_ALLOC (&grand_bitmap_obstack); |
7e6eb623 | 467 | bitmap_clear (set->values); |
6de9cd9a | 468 | } |
33c94679 DN |
469 | |
470 | bitmap_set_bit (set->values, VALUE_HANDLE_ID (v)); | |
7e6eb623 | 471 | } |
6de9cd9a | 472 | |
33c94679 | 473 | |
bdee7684 DB |
474 | /* Create a new bitmap set and return it. */ |
475 | ||
476 | static bitmap_set_t | |
477 | bitmap_set_new (void) | |
478 | { | |
479 | bitmap_set_t ret = pool_alloc (bitmap_set_pool); | |
c4817ba6 JH |
480 | ret->expressions = BITMAP_OBSTACK_ALLOC (&grand_bitmap_obstack); |
481 | ret->values = BITMAP_OBSTACK_ALLOC (&grand_bitmap_obstack); | |
bdee7684 DB |
482 | bitmap_clear (ret->expressions); |
483 | bitmap_clear (ret->values); | |
484 | return ret; | |
485 | } | |
486 | ||
7e6eb623 DB |
487 | /* Create a new set. */ |
488 | ||
489 | static value_set_t | |
490 | set_new (bool indexed) | |
491 | { | |
492 | value_set_t ret; | |
493 | ret = pool_alloc (value_set_pool); | |
494 | ret->head = ret->tail = NULL; | |
495 | ret->length = 0; | |
496 | ret->indexed = indexed; | |
497 | ret->values = NULL; | |
6de9cd9a DN |
498 | return ret; |
499 | } | |
500 | ||
6b416da1 | 501 | /* Insert an expression EXPR into a bitmapped set. */ |
bdee7684 DB |
502 | |
503 | static void | |
504 | bitmap_insert_into_set (bitmap_set_t set, tree expr) | |
505 | { | |
506 | tree val; | |
507 | /* XXX: For now, we only let SSA_NAMES into the bitmap sets. */ | |
1e128c5f | 508 | gcc_assert (TREE_CODE (expr) == SSA_NAME); |
bdee7684 DB |
509 | val = get_value_handle (expr); |
510 | ||
1e128c5f | 511 | gcc_assert (val); |
6b416da1 | 512 | if (!is_gimple_min_invariant (val)) |
d6fd4b8d | 513 | { |
6b416da1 | 514 | bitmap_set_bit (set->values, VALUE_HANDLE_ID (val)); |
d6fd4b8d DB |
515 | bitmap_set_bit (set->expressions, SSA_NAME_VERSION (expr)); |
516 | } | |
bdee7684 | 517 | } |
6de9cd9a | 518 | |
7e6eb623 DB |
519 | /* Insert EXPR into SET. */ |
520 | ||
521 | static void | |
522 | insert_into_set (value_set_t set, tree expr) | |
523 | { | |
524 | value_set_node_t newnode = pool_alloc (value_set_node_pool); | |
525 | tree val = get_value_handle (expr); | |
1e128c5f | 526 | gcc_assert (val); |
97141338 DB |
527 | |
528 | if (is_gimple_min_invariant (val)) | |
529 | return; | |
6de9cd9a | 530 | |
7e6eb623 DB |
531 | /* For indexed sets, insert the value into the set value bitmap. |
532 | For all sets, add it to the linked list and increment the list | |
533 | length. */ | |
534 | if (set->indexed) | |
535 | value_insert_into_set_bitmap (set, val); | |
6de9cd9a | 536 | |
7e6eb623 DB |
537 | newnode->next = NULL; |
538 | newnode->expr = expr; | |
539 | set->length ++; | |
540 | if (set->head == NULL) | |
541 | { | |
542 | set->head = set->tail = newnode; | |
543 | } | |
544 | else | |
545 | { | |
546 | set->tail->next = newnode; | |
547 | set->tail = newnode; | |
548 | } | |
549 | } | |
6de9cd9a | 550 | |
bdee7684 DB |
551 | /* Copy a bitmapped set ORIG, into bitmapped set DEST. */ |
552 | ||
553 | static void | |
554 | bitmap_set_copy (bitmap_set_t dest, bitmap_set_t orig) | |
555 | { | |
556 | bitmap_copy (dest->expressions, orig->expressions); | |
557 | bitmap_copy (dest->values, orig->values); | |
558 | } | |
559 | ||
7e6eb623 | 560 | /* Copy the set ORIG to the set DEST. */ |
6de9cd9a | 561 | |
7e6eb623 DB |
562 | static void |
563 | set_copy (value_set_t dest, value_set_t orig) | |
564 | { | |
565 | value_set_node_t node; | |
566 | ||
567 | if (!orig || !orig->head) | |
568 | return; | |
6de9cd9a | 569 | |
7e6eb623 DB |
570 | for (node = orig->head; |
571 | node; | |
572 | node = node->next) | |
573 | { | |
574 | insert_into_set (dest, node->expr); | |
575 | } | |
576 | } | |
6de9cd9a | 577 | |
7e6eb623 | 578 | /* Remove EXPR from SET. */ |
6de9cd9a DN |
579 | |
580 | static void | |
7e6eb623 | 581 | set_remove (value_set_t set, tree expr) |
6de9cd9a | 582 | { |
7e6eb623 | 583 | value_set_node_t node, prev; |
6de9cd9a | 584 | |
7e6eb623 DB |
585 | /* Remove the value of EXPR from the bitmap, decrement the set |
586 | length, and remove it from the actual double linked list. */ | |
587 | value_remove_from_set_bitmap (set, get_value_handle (expr)); | |
588 | set->length--; | |
589 | prev = NULL; | |
590 | for (node = set->head; | |
591 | node != NULL; | |
592 | prev = node, node = node->next) | |
593 | { | |
594 | if (node->expr == expr) | |
595 | { | |
596 | if (prev == NULL) | |
597 | set->head = node->next; | |
598 | else | |
599 | prev->next= node->next; | |
600 | ||
601 | if (node == set->tail) | |
602 | set->tail = prev; | |
603 | pool_free (value_set_node_pool, node); | |
604 | return; | |
605 | } | |
6de9cd9a DN |
606 | } |
607 | } | |
608 | ||
7e6eb623 DB |
609 | /* Return true if SET contains the value VAL. */ |
610 | ||
611 | static bool | |
612 | set_contains_value (value_set_t set, tree val) | |
613 | { | |
bddeccfe DN |
614 | /* All constants are in every set. */ |
615 | if (is_gimple_min_invariant (val)) | |
7e6eb623 DB |
616 | return true; |
617 | ||
618 | if (set->length == 0) | |
619 | return false; | |
620 | ||
621 | return value_exists_in_set_bitmap (set, val); | |
622 | } | |
6de9cd9a | 623 | |
6b416da1 DB |
624 | /* Return true if bitmapped set SET contains the expression EXPR. */ |
625 | static bool | |
626 | bitmap_set_contains (bitmap_set_t set, tree expr) | |
627 | { | |
af75a7ea DB |
628 | /* All constants are in every set. */ |
629 | if (is_gimple_min_invariant (get_value_handle (expr))) | |
630 | return true; | |
631 | ||
6b416da1 DB |
632 | /* XXX: Bitmapped sets only contain SSA_NAME's for now. */ |
633 | if (TREE_CODE (expr) != SSA_NAME) | |
634 | return false; | |
635 | return bitmap_bit_p (set->expressions, SSA_NAME_VERSION (expr)); | |
636 | } | |
637 | ||
638 | ||
bdee7684 | 639 | /* Return true if bitmapped set SET contains the value VAL. */ |
6de9cd9a | 640 | |
bdee7684 DB |
641 | static bool |
642 | bitmap_set_contains_value (bitmap_set_t set, tree val) | |
6de9cd9a | 643 | { |
bdee7684 DB |
644 | if (is_gimple_min_invariant (val)) |
645 | return true; | |
646 | return bitmap_bit_p (set->values, VALUE_HANDLE_ID (val)); | |
647 | } | |
7e6eb623 | 648 | |
bdee7684 | 649 | /* Replace an instance of value LOOKFOR with expression EXPR in SET. */ |
7e6eb623 | 650 | |
bdee7684 DB |
651 | static void |
652 | bitmap_set_replace_value (bitmap_set_t set, tree lookfor, tree expr) | |
653 | { | |
654 | value_set_t exprset; | |
655 | value_set_node_t node; | |
656 | if (is_gimple_min_invariant (lookfor)) | |
657 | return; | |
658 | if (!bitmap_set_contains_value (set, lookfor)) | |
659 | return; | |
6b416da1 DB |
660 | /* The number of expressions having a given value is usually |
661 | significantly less than the total number of expressions in SET. | |
662 | Thus, rather than check, for each expression in SET, whether it | |
663 | has the value LOOKFOR, we walk the reverse mapping that tells us | |
664 | what expressions have a given value, and see if any of those | |
665 | expressions are in our set. For large testcases, this is about | |
666 | 5-10x faster than walking the bitmap. If this is somehow a | |
667 | significant lose for some cases, we can choose which set to walk | |
668 | based on the set size. */ | |
bdee7684 DB |
669 | exprset = VALUE_HANDLE_EXPR_SET (lookfor); |
670 | for (node = exprset->head; node; node = node->next) | |
6de9cd9a | 671 | { |
bdee7684 | 672 | if (TREE_CODE (node->expr) == SSA_NAME) |
6de9cd9a | 673 | { |
bdee7684 DB |
674 | if (bitmap_bit_p (set->expressions, SSA_NAME_VERSION (node->expr))) |
675 | { | |
676 | bitmap_clear_bit (set->expressions, SSA_NAME_VERSION (node->expr)); | |
677 | bitmap_set_bit (set->expressions, SSA_NAME_VERSION (expr)); | |
678 | return; | |
679 | } | |
6de9cd9a | 680 | } |
6de9cd9a DN |
681 | } |
682 | } | |
683 | ||
6b416da1 | 684 | /* Subtract bitmapped set B from value set A, and return the new set. */ |
6de9cd9a | 685 | |
7e6eb623 | 686 | static value_set_t |
6b416da1 DB |
687 | bitmap_set_subtract_from_value_set (value_set_t a, bitmap_set_t b, |
688 | bool indexed) | |
7e6eb623 DB |
689 | { |
690 | value_set_t ret = set_new (indexed); | |
691 | value_set_node_t node; | |
692 | for (node = a->head; | |
693 | node; | |
694 | node = node->next) | |
695 | { | |
6b416da1 | 696 | if (!bitmap_set_contains (b, node->expr)) |
7e6eb623 DB |
697 | insert_into_set (ret, node->expr); |
698 | } | |
699 | return ret; | |
6de9cd9a DN |
700 | } |
701 | ||
8c27b7d4 | 702 | /* Return true if two sets are equal. */ |
6de9cd9a | 703 | |
7e6eb623 DB |
704 | static bool |
705 | set_equal (value_set_t a, value_set_t b) | |
6de9cd9a | 706 | { |
7e6eb623 DB |
707 | value_set_node_t node; |
708 | ||
709 | if (a->length != b->length) | |
710 | return false; | |
711 | for (node = a->head; | |
712 | node; | |
713 | node = node->next) | |
714 | { | |
715 | if (!set_contains_value (b, get_value_handle (node->expr))) | |
716 | return false; | |
717 | } | |
718 | return true; | |
6de9cd9a DN |
719 | } |
720 | ||
bdee7684 DB |
721 | /* Replace an instance of EXPR's VALUE with EXPR in SET. */ |
722 | ||
7e6eb623 | 723 | static void |
bdee7684 | 724 | bitmap_value_replace_in_set (bitmap_set_t set, tree expr) |
7e6eb623 DB |
725 | { |
726 | tree val = get_value_handle (expr); | |
bdee7684 DB |
727 | bitmap_set_replace_value (set, val, expr); |
728 | } | |
7e6eb623 | 729 | |
bdee7684 DB |
730 | /* Insert EXPR into SET if EXPR's value is not already present in |
731 | SET. */ | |
732 | ||
733 | static void | |
734 | bitmap_value_insert_into_set (bitmap_set_t set, tree expr) | |
735 | { | |
736 | tree val = get_value_handle (expr); | |
af75a7ea | 737 | |
bdee7684 | 738 | if (is_gimple_min_invariant (val)) |
7e6eb623 DB |
739 | return; |
740 | ||
bdee7684 DB |
741 | if (!bitmap_set_contains_value (set, val)) |
742 | bitmap_insert_into_set (set, expr); | |
7e6eb623 | 743 | } |
6de9cd9a | 744 | |
7e6eb623 | 745 | /* Insert the value for EXPR into SET, if it doesn't exist already. */ |
6de9cd9a | 746 | |
7e6eb623 DB |
747 | static void |
748 | value_insert_into_set (value_set_t set, tree expr) | |
6de9cd9a | 749 | { |
7e6eb623 | 750 | tree val = get_value_handle (expr); |
6de9cd9a | 751 | |
56db793a DB |
752 | /* Constant and invariant values exist everywhere, and thus, |
753 | actually keeping them in the sets is pointless. */ | |
bddeccfe | 754 | if (is_gimple_min_invariant (val)) |
7e6eb623 | 755 | return; |
6de9cd9a | 756 | |
7e6eb623 DB |
757 | if (!set_contains_value (set, val)) |
758 | insert_into_set (set, expr); | |
6de9cd9a DN |
759 | } |
760 | ||
761 | ||
bdee7684 DB |
762 | /* Print out SET to OUTFILE. */ |
763 | ||
764 | static void | |
765 | bitmap_print_value_set (FILE *outfile, bitmap_set_t set, | |
766 | const char *setname, int blockindex) | |
767 | { | |
768 | fprintf (outfile, "%s[%d] := { ", setname, blockindex); | |
769 | if (set) | |
770 | { | |
65a6f342 | 771 | bool first; |
3cd8c58a | 772 | unsigned i; |
87c476a2 ZD |
773 | bitmap_iterator bi; |
774 | ||
775 | EXECUTE_IF_SET_IN_BITMAP (set->expressions, 0, i, bi) | |
776 | { | |
65a6f342 NS |
777 | if (!first) |
778 | fprintf (outfile, ", "); | |
779 | first = false; | |
87c476a2 | 780 | print_generic_expr (outfile, ssa_name (i), 0); |
bdee7684 | 781 | |
87c476a2 ZD |
782 | fprintf (outfile, " ("); |
783 | print_generic_expr (outfile, get_value_handle (ssa_name (i)), 0); | |
784 | fprintf (outfile, ") "); | |
87c476a2 | 785 | } |
bdee7684 DB |
786 | } |
787 | fprintf (outfile, " }\n"); | |
788 | } | |
7e6eb623 | 789 | /* Print out the value_set SET to OUTFILE. */ |
6de9cd9a | 790 | |
7e6eb623 DB |
791 | static void |
792 | print_value_set (FILE *outfile, value_set_t set, | |
793 | const char *setname, int blockindex) | |
6de9cd9a | 794 | { |
7e6eb623 DB |
795 | value_set_node_t node; |
796 | fprintf (outfile, "%s[%d] := { ", setname, blockindex); | |
797 | if (set) | |
6de9cd9a | 798 | { |
7e6eb623 DB |
799 | for (node = set->head; |
800 | node; | |
801 | node = node->next) | |
6de9cd9a | 802 | { |
7e6eb623 | 803 | print_generic_expr (outfile, node->expr, 0); |
ca072a31 DB |
804 | |
805 | fprintf (outfile, " ("); | |
806 | print_generic_expr (outfile, get_value_handle (node->expr), 0); | |
807 | fprintf (outfile, ") "); | |
808 | ||
7e6eb623 DB |
809 | if (node->next) |
810 | fprintf (outfile, ", "); | |
6de9cd9a | 811 | } |
6de9cd9a DN |
812 | } |
813 | ||
7e6eb623 DB |
814 | fprintf (outfile, " }\n"); |
815 | } | |
816 | ||
817 | /* Print out the expressions that have VAL to OUTFILE. */ | |
33c94679 | 818 | |
7e6eb623 DB |
819 | void |
820 | print_value_expressions (FILE *outfile, tree val) | |
821 | { | |
33c94679 DN |
822 | if (VALUE_HANDLE_EXPR_SET (val)) |
823 | { | |
824 | char s[10]; | |
825 | sprintf (s, "VH.%04d", VALUE_HANDLE_ID (val)); | |
826 | print_value_set (outfile, VALUE_HANDLE_EXPR_SET (val), s, 0); | |
827 | } | |
6de9cd9a DN |
828 | } |
829 | ||
6de9cd9a | 830 | |
7e6eb623 DB |
831 | void |
832 | debug_value_expressions (tree val) | |
6de9cd9a | 833 | { |
7e6eb623 DB |
834 | print_value_expressions (stderr, val); |
835 | } | |
836 | ||
6de9cd9a | 837 | |
7e6eb623 | 838 | void debug_value_set (value_set_t, const char *, int); |
6de9cd9a | 839 | |
7e6eb623 DB |
840 | void |
841 | debug_value_set (value_set_t set, const char *setname, int blockindex) | |
6de9cd9a | 842 | { |
7e6eb623 | 843 | print_value_set (stderr, set, setname, blockindex); |
6de9cd9a DN |
844 | } |
845 | ||
7e6eb623 DB |
846 | /* Translate EXPR using phis in PHIBLOCK, so that it has the values of |
847 | the phis in PRED. Return NULL if we can't find a leader for each | |
848 | part of the translated expression. */ | |
6de9cd9a DN |
849 | |
850 | static tree | |
ff2ad0f7 | 851 | phi_translate (tree expr, value_set_t set, basic_block pred, |
7e6eb623 | 852 | basic_block phiblock) |
6de9cd9a | 853 | { |
7e6eb623 DB |
854 | tree phitrans = NULL; |
855 | tree oldexpr = expr; | |
6de9cd9a | 856 | |
7e6eb623 DB |
857 | if (expr == NULL) |
858 | return NULL; | |
6de9cd9a | 859 | |
6615c446 JO |
860 | if (is_gimple_min_invariant (expr)) |
861 | return expr; | |
862 | ||
ea4b7848 | 863 | /* Phi translations of a given expression don't change. */ |
7e6eb623 DB |
864 | phitrans = phi_trans_lookup (expr, pred); |
865 | if (phitrans) | |
866 | return phitrans; | |
867 | ||
7e6eb623 | 868 | switch (TREE_CODE_CLASS (TREE_CODE (expr))) |
6de9cd9a | 869 | { |
6615c446 | 870 | case tcc_reference: |
471854f8 | 871 | /* XXX: Until we have PRE of loads working, none will be ANTIC. */ |
6615c446 JO |
872 | return NULL; |
873 | ||
874 | case tcc_binary: | |
7e6eb623 DB |
875 | { |
876 | tree oldop1 = TREE_OPERAND (expr, 0); | |
877 | tree oldop2 = TREE_OPERAND (expr, 1); | |
878 | tree newop1; | |
879 | tree newop2; | |
880 | tree newexpr; | |
881 | ||
882 | newop1 = phi_translate (find_leader (set, oldop1), | |
883 | set, pred, phiblock); | |
884 | if (newop1 == NULL) | |
885 | return NULL; | |
886 | newop2 = phi_translate (find_leader (set, oldop2), | |
887 | set, pred, phiblock); | |
888 | if (newop2 == NULL) | |
889 | return NULL; | |
890 | if (newop1 != oldop1 || newop2 != oldop2) | |
891 | { | |
892 | newexpr = pool_alloc (binary_node_pool); | |
893 | memcpy (newexpr, expr, tree_size (expr)); | |
06d72ee6 | 894 | create_tree_ann (newexpr); |
7e6eb623 DB |
895 | TREE_OPERAND (newexpr, 0) = newop1 == oldop1 ? oldop1 : get_value_handle (newop1); |
896 | TREE_OPERAND (newexpr, 1) = newop2 == oldop2 ? oldop2 : get_value_handle (newop2); | |
ff2ad0f7 | 897 | vn_lookup_or_add (newexpr, NULL); |
7e6eb623 DB |
898 | expr = newexpr; |
899 | phi_trans_add (oldexpr, newexpr, pred); | |
900 | } | |
901 | } | |
6615c446 JO |
902 | return expr; |
903 | ||
904 | case tcc_unary: | |
7e6eb623 DB |
905 | { |
906 | tree oldop1 = TREE_OPERAND (expr, 0); | |
907 | tree newop1; | |
908 | tree newexpr; | |
909 | ||
910 | newop1 = phi_translate (find_leader (set, oldop1), | |
911 | set, pred, phiblock); | |
912 | if (newop1 == NULL) | |
913 | return NULL; | |
914 | if (newop1 != oldop1) | |
915 | { | |
ca072a31 | 916 | newexpr = pool_alloc (unary_node_pool); |
7e6eb623 | 917 | memcpy (newexpr, expr, tree_size (expr)); |
06d72ee6 | 918 | create_tree_ann (newexpr); |
7e6eb623 | 919 | TREE_OPERAND (newexpr, 0) = get_value_handle (newop1); |
ff2ad0f7 | 920 | vn_lookup_or_add (newexpr, NULL); |
7e6eb623 DB |
921 | expr = newexpr; |
922 | phi_trans_add (oldexpr, newexpr, pred); | |
923 | } | |
924 | } | |
6615c446 JO |
925 | return expr; |
926 | ||
927 | case tcc_exceptional: | |
7e6eb623 DB |
928 | { |
929 | tree phi = NULL; | |
930 | int i; | |
1e128c5f | 931 | gcc_assert (TREE_CODE (expr) == SSA_NAME); |
7e6eb623 DB |
932 | if (TREE_CODE (SSA_NAME_DEF_STMT (expr)) == PHI_NODE) |
933 | phi = SSA_NAME_DEF_STMT (expr); | |
934 | else | |
935 | return expr; | |
936 | ||
937 | for (i = 0; i < PHI_NUM_ARGS (phi); i++) | |
938 | if (PHI_ARG_EDGE (phi, i)->src == pred) | |
6de9cd9a | 939 | { |
7e6eb623 DB |
940 | tree val; |
941 | if (is_undefined_value (PHI_ARG_DEF (phi, i))) | |
942 | return NULL; | |
ff2ad0f7 | 943 | val = vn_lookup_or_add (PHI_ARG_DEF (phi, i), NULL); |
7e6eb623 | 944 | return PHI_ARG_DEF (phi, i); |
6de9cd9a | 945 | } |
7e6eb623 | 946 | } |
6615c446 JO |
947 | return expr; |
948 | ||
949 | default: | |
950 | gcc_unreachable (); | |
6de9cd9a DN |
951 | } |
952 | } | |
953 | ||
6de9cd9a | 954 | static void |
7e6eb623 DB |
955 | phi_translate_set (value_set_t dest, value_set_t set, basic_block pred, |
956 | basic_block phiblock) | |
6de9cd9a | 957 | { |
7e6eb623 DB |
958 | value_set_node_t node; |
959 | for (node = set->head; | |
960 | node; | |
961 | node = node->next) | |
6de9cd9a | 962 | { |
7e6eb623 DB |
963 | tree translated; |
964 | translated = phi_translate (node->expr, set, pred, phiblock); | |
965 | phi_trans_add (node->expr, translated, pred); | |
6de9cd9a | 966 | |
7e6eb623 DB |
967 | if (translated != NULL) |
968 | value_insert_into_set (dest, translated); | |
969 | } | |
6de9cd9a DN |
970 | } |
971 | ||
bdee7684 DB |
972 | /* Find the leader for a value (i.e., the name representing that |
973 | value) in a given set, and return it. Return NULL if no leader is | |
974 | found. */ | |
975 | ||
976 | static tree | |
977 | bitmap_find_leader (bitmap_set_t set, tree val) | |
978 | { | |
979 | if (val == NULL) | |
980 | return NULL; | |
981 | ||
982 | if (is_gimple_min_invariant (val)) | |
983 | return val; | |
984 | if (bitmap_set_contains_value (set, val)) | |
985 | { | |
6b416da1 DB |
986 | /* Rather than walk the entire bitmap of expressions, and see |
987 | whether any of them has the value we are looking for, we look | |
988 | at the reverse mapping, which tells us the set of expressions | |
989 | that have a given value (IE value->expressions with that | |
990 | value) and see if any of those expressions are in our set. | |
991 | The number of expressions per value is usually significantly | |
992 | less than the number of expressions in the set. In fact, for | |
993 | large testcases, doing it this way is roughly 5-10x faster | |
994 | than walking the bitmap. | |
995 | If this is somehow a significant lose for some cases, we can | |
996 | choose which set to walk based on which set is smaller. */ | |
997 | value_set_t exprset; | |
998 | value_set_node_t node; | |
999 | exprset = VALUE_HANDLE_EXPR_SET (val); | |
1000 | for (node = exprset->head; node; node = node->next) | |
1001 | { | |
1002 | if (TREE_CODE (node->expr) == SSA_NAME) | |
1003 | { | |
1004 | if (bitmap_bit_p (set->expressions, | |
1005 | SSA_NAME_VERSION (node->expr))) | |
1006 | return node->expr; | |
1007 | } | |
1008 | } | |
bdee7684 DB |
1009 | } |
1010 | return NULL; | |
1011 | } | |
1012 | ||
1013 | ||
ff2ad0f7 | 1014 | /* Find the leader for a value (i.e., the name representing that |
7e6eb623 DB |
1015 | value) in a given set, and return it. Return NULL if no leader is |
1016 | found. */ | |
6de9cd9a | 1017 | |
7e6eb623 DB |
1018 | static tree |
1019 | find_leader (value_set_t set, tree val) | |
6de9cd9a | 1020 | { |
7e6eb623 | 1021 | value_set_node_t node; |
6de9cd9a | 1022 | |
7e6eb623 DB |
1023 | if (val == NULL) |
1024 | return NULL; | |
ff2ad0f7 | 1025 | |
bddeccfe DN |
1026 | /* Constants represent themselves. */ |
1027 | if (is_gimple_min_invariant (val)) | |
56db793a | 1028 | return val; |
ff2ad0f7 | 1029 | |
7e6eb623 DB |
1030 | if (set->length == 0) |
1031 | return NULL; | |
6de9cd9a | 1032 | |
7e6eb623 | 1033 | if (value_exists_in_set_bitmap (set, val)) |
6de9cd9a | 1034 | { |
7e6eb623 DB |
1035 | for (node = set->head; |
1036 | node; | |
1037 | node = node->next) | |
6de9cd9a | 1038 | { |
7e6eb623 DB |
1039 | if (get_value_handle (node->expr) == val) |
1040 | return node->expr; | |
6de9cd9a DN |
1041 | } |
1042 | } | |
ff2ad0f7 | 1043 | |
7e6eb623 | 1044 | return NULL; |
6de9cd9a DN |
1045 | } |
1046 | ||
7e6eb623 DB |
1047 | /* Determine if the expression EXPR is valid in SET. This means that |
1048 | we have a leader for each part of the expression (if it consists of | |
1049 | values), or the expression is an SSA_NAME. | |
6de9cd9a | 1050 | |
7e6eb623 DB |
1051 | NB: We never should run into a case where we have SSA_NAME + |
1052 | SSA_NAME or SSA_NAME + value. The sets valid_in_set is called on, | |
1053 | the ANTIC sets, will only ever have SSA_NAME's or binary value | |
1054 | expression (IE VALUE1 + VALUE2) */ | |
6de9cd9a DN |
1055 | |
1056 | static bool | |
7e6eb623 | 1057 | valid_in_set (value_set_t set, tree expr) |
6de9cd9a | 1058 | { |
7e6eb623 DB |
1059 | switch (TREE_CODE_CLASS (TREE_CODE (expr))) |
1060 | { | |
6615c446 | 1061 | case tcc_binary: |
6de9cd9a | 1062 | { |
7e6eb623 DB |
1063 | tree op1 = TREE_OPERAND (expr, 0); |
1064 | tree op2 = TREE_OPERAND (expr, 1); | |
1065 | return set_contains_value (set, op1) && set_contains_value (set, op2); | |
6de9cd9a | 1066 | } |
6615c446 JO |
1067 | |
1068 | case tcc_unary: | |
7e6eb623 DB |
1069 | { |
1070 | tree op1 = TREE_OPERAND (expr, 0); | |
1071 | return set_contains_value (set, op1); | |
1072 | } | |
6615c446 JO |
1073 | |
1074 | case tcc_reference: | |
1075 | /* XXX: Until PRE of loads works, no reference nodes are ANTIC. */ | |
1076 | return false; | |
1077 | ||
1078 | case tcc_exceptional: | |
1079 | gcc_assert (TREE_CODE (expr) == SSA_NAME); | |
1080 | return true; | |
1081 | ||
1082 | default: | |
1083 | /* No other cases should be encountered. */ | |
1084 | gcc_unreachable (); | |
1085 | } | |
6de9cd9a DN |
1086 | } |
1087 | ||
ca072a31 DB |
1088 | /* Clean the set of expressions that are no longer valid in SET. This |
1089 | means expressions that are made up of values we have no leaders for | |
1090 | in SET. */ | |
6de9cd9a DN |
1091 | |
1092 | static void | |
7e6eb623 | 1093 | clean (value_set_t set) |
6de9cd9a | 1094 | { |
7e6eb623 DB |
1095 | value_set_node_t node; |
1096 | value_set_node_t next; | |
1097 | node = set->head; | |
1098 | while (node) | |
6de9cd9a | 1099 | { |
7e6eb623 DB |
1100 | next = node->next; |
1101 | if (!valid_in_set (set, node->expr)) | |
1102 | set_remove (set, node->expr); | |
1103 | node = next; | |
6de9cd9a DN |
1104 | } |
1105 | } | |
1106 | ||
d6fd4b8d DB |
1107 | DEF_VEC_MALLOC_P (basic_block); |
1108 | ||
7e6eb623 | 1109 | /* Compute the ANTIC set for BLOCK. |
6de9cd9a | 1110 | |
7e6eb623 DB |
1111 | ANTIC_OUT[BLOCK] = intersection of ANTIC_IN[b] for all succ(BLOCK), if |
1112 | succs(BLOCK) > 1 | |
1113 | ANTIC_OUT[BLOCK] = phi_translate (ANTIC_IN[succ(BLOCK)]) if | |
1114 | succs(BLOCK) == 1 | |
6de9cd9a | 1115 | |
7e6eb623 DB |
1116 | ANTIC_IN[BLOCK] = clean(ANTIC_OUT[BLOCK] U EXP_GEN[BLOCK] - |
1117 | TMP_GEN[BLOCK]) | |
6de9cd9a | 1118 | |
7e6eb623 | 1119 | Iterate until fixpointed. |
6de9cd9a | 1120 | |
7e6eb623 DB |
1121 | XXX: It would be nice to either write a set_clear, and use it for |
1122 | antic_out, or to mark the antic_out set as deleted at the end | |
1123 | of this routine, so that the pool can hand the same memory back out | |
1124 | again for the next antic_out. */ | |
6de9cd9a | 1125 | |
7e6eb623 DB |
1126 | |
1127 | static bool | |
1128 | compute_antic_aux (basic_block block) | |
6de9cd9a | 1129 | { |
7e6eb623 DB |
1130 | basic_block son; |
1131 | edge e; | |
1132 | bool changed = false; | |
1133 | value_set_t S, old, ANTIC_OUT; | |
1134 | value_set_node_t node; | |
1135 | ||
1136 | ANTIC_OUT = S = NULL; | |
1137 | /* If any edges from predecessors are abnormal, antic_in is empty, so | |
1138 | punt. Remember that the block has an incoming abnormal edge by | |
1139 | setting the BB_VISITED flag. */ | |
1140 | if (! (block->flags & BB_VISITED)) | |
6de9cd9a | 1141 | { |
628f6a4e BE |
1142 | edge_iterator ei; |
1143 | FOR_EACH_EDGE (e, ei, block->preds) | |
1144 | if (e->flags & EDGE_ABNORMAL) | |
1145 | { | |
1146 | block->flags |= BB_VISITED; | |
1147 | break; | |
1148 | } | |
6de9cd9a | 1149 | } |
7e6eb623 | 1150 | if (block->flags & BB_VISITED) |
6de9cd9a | 1151 | { |
7e6eb623 DB |
1152 | S = NULL; |
1153 | goto visit_sons; | |
6de9cd9a | 1154 | } |
7e6eb623 | 1155 | |
6de9cd9a | 1156 | |
7e6eb623 DB |
1157 | old = set_new (false); |
1158 | set_copy (old, ANTIC_IN (block)); | |
1159 | ANTIC_OUT = set_new (true); | |
6de9cd9a | 1160 | |
7e6eb623 DB |
1161 | /* If the block has no successors, ANTIC_OUT is empty, because it is |
1162 | the exit block. */ | |
628f6a4e | 1163 | if (EDGE_COUNT (block->succs) == 0); |
6de9cd9a | 1164 | |
7e6eb623 DB |
1165 | /* If we have one successor, we could have some phi nodes to |
1166 | translate through. */ | |
628f6a4e | 1167 | else if (EDGE_COUNT (block->succs) == 1) |
6de9cd9a | 1168 | { |
628f6a4e BE |
1169 | phi_translate_set (ANTIC_OUT, ANTIC_IN(EDGE_SUCC (block, 0)->dest), |
1170 | block, EDGE_SUCC (block, 0)->dest); | |
6de9cd9a | 1171 | } |
7e6eb623 DB |
1172 | /* If we have multiple successors, we take the intersection of all of |
1173 | them. */ | |
1174 | else | |
6de9cd9a | 1175 | { |
d6fd4b8d | 1176 | VEC (basic_block) * worklist; |
7e6eb623 DB |
1177 | edge e; |
1178 | size_t i; | |
1179 | basic_block bprime, first; | |
628f6a4e | 1180 | edge_iterator ei; |
7e6eb623 | 1181 | |
d6fd4b8d | 1182 | worklist = VEC_alloc (basic_block, 2); |
628f6a4e BE |
1183 | FOR_EACH_EDGE (e, ei, block->succs) |
1184 | VEC_safe_push (basic_block, worklist, e->dest); | |
d6fd4b8d | 1185 | first = VEC_index (basic_block, worklist, 0); |
7e6eb623 | 1186 | set_copy (ANTIC_OUT, ANTIC_IN (first)); |
6de9cd9a | 1187 | |
d6fd4b8d | 1188 | for (i = 1; VEC_iterate (basic_block, worklist, i, bprime); i++) |
6de9cd9a | 1189 | { |
7e6eb623 DB |
1190 | node = ANTIC_OUT->head; |
1191 | while (node) | |
6de9cd9a | 1192 | { |
7e6eb623 DB |
1193 | tree val; |
1194 | value_set_node_t next = node->next; | |
1195 | val = get_value_handle (node->expr); | |
1196 | if (!set_contains_value (ANTIC_IN (bprime), val)) | |
1197 | set_remove (ANTIC_OUT, node->expr); | |
1198 | node = next; | |
6de9cd9a | 1199 | } |
6de9cd9a | 1200 | } |
d6fd4b8d | 1201 | VEC_free (basic_block, worklist); |
6de9cd9a | 1202 | } |
6de9cd9a | 1203 | |
ea4b7848 | 1204 | /* Generate ANTIC_OUT - TMP_GEN. */ |
6b416da1 | 1205 | S = bitmap_set_subtract_from_value_set (ANTIC_OUT, TMP_GEN (block), false); |
6de9cd9a | 1206 | |
7e6eb623 | 1207 | /* Start ANTIC_IN with EXP_GEN - TMP_GEN */ |
6b416da1 DB |
1208 | ANTIC_IN (block) = bitmap_set_subtract_from_value_set (EXP_GEN (block), |
1209 | TMP_GEN (block), | |
1210 | true); | |
6de9cd9a | 1211 | |
7e6eb623 DB |
1212 | /* Then union in the ANTIC_OUT - TMP_GEN values, to get ANTIC_OUT U |
1213 | EXP_GEN - TMP_GEN */ | |
1214 | for (node = S->head; | |
1215 | node; | |
1216 | node = node->next) | |
6de9cd9a | 1217 | { |
7e6eb623 | 1218 | value_insert_into_set (ANTIC_IN (block), node->expr); |
6de9cd9a | 1219 | } |
7e6eb623 | 1220 | clean (ANTIC_IN (block)); |
ca072a31 | 1221 | |
6de9cd9a | 1222 | |
7e6eb623 DB |
1223 | if (!set_equal (old, ANTIC_IN (block))) |
1224 | changed = true; | |
6de9cd9a | 1225 | |
7e6eb623 DB |
1226 | visit_sons: |
1227 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
1228 | { | |
1229 | if (ANTIC_OUT) | |
1230 | print_value_set (dump_file, ANTIC_OUT, "ANTIC_OUT", block->index); | |
1231 | print_value_set (dump_file, ANTIC_IN (block), "ANTIC_IN", block->index); | |
1232 | if (S) | |
1233 | print_value_set (dump_file, S, "S", block->index); | |
6de9cd9a | 1234 | |
7e6eb623 | 1235 | } |
6de9cd9a | 1236 | |
7e6eb623 DB |
1237 | for (son = first_dom_son (CDI_POST_DOMINATORS, block); |
1238 | son; | |
1239 | son = next_dom_son (CDI_POST_DOMINATORS, son)) | |
6de9cd9a | 1240 | { |
7e6eb623 | 1241 | changed |= compute_antic_aux (son); |
6de9cd9a | 1242 | } |
7e6eb623 | 1243 | return changed; |
6de9cd9a DN |
1244 | } |
1245 | ||
7e6eb623 | 1246 | /* Compute ANTIC sets. */ |
6de9cd9a DN |
1247 | |
1248 | static void | |
7e6eb623 | 1249 | compute_antic (void) |
6de9cd9a | 1250 | { |
7e6eb623 DB |
1251 | bool changed = true; |
1252 | basic_block bb; | |
1253 | int num_iterations = 0; | |
1254 | FOR_ALL_BB (bb) | |
1255 | { | |
1256 | ANTIC_IN (bb) = set_new (true); | |
1e128c5f | 1257 | gcc_assert (!(bb->flags & BB_VISITED)); |
7e6eb623 DB |
1258 | } |
1259 | ||
1260 | while (changed) | |
1261 | { | |
1262 | num_iterations++; | |
1263 | changed = false; | |
1264 | changed = compute_antic_aux (EXIT_BLOCK_PTR); | |
1265 | } | |
2e24fa83 ZD |
1266 | FOR_ALL_BB (bb) |
1267 | { | |
1268 | bb->flags &= ~BB_VISITED; | |
1269 | } | |
7e6eb623 DB |
1270 | if (num_iterations > 2 && dump_file && (dump_flags & TDF_STATS)) |
1271 | fprintf (dump_file, "compute_antic required %d iterations\n", num_iterations); | |
6de9cd9a DN |
1272 | } |
1273 | ||
56db793a DB |
1274 | |
1275 | /* Find a leader for an expression, or generate one using | |
1276 | create_expression_by_pieces if it's ANTIC but | |
1277 | complex. | |
1278 | BLOCK is the basic_block we are looking for leaders in. | |
1279 | EXPR is the expression to find a leader or generate for. | |
1280 | STMTS is the statement list to put the inserted expressions on. | |
1281 | Returns the SSA_NAME of the LHS of the generated expression or the | |
1282 | leader. */ | |
1283 | ||
1284 | static tree | |
1285 | find_or_generate_expression (basic_block block, tree expr, tree stmts) | |
1286 | { | |
1287 | tree genop; | |
bdee7684 | 1288 | genop = bitmap_find_leader (AVAIL_OUT (block), expr); |
56db793a DB |
1289 | /* Depending on the order we process DOM branches in, the value |
1290 | may not have propagated to all the dom children yet during | |
1291 | this iteration. In this case, the value will always be in | |
61ada8ae | 1292 | the NEW_SETS for us already, having been propagated from our |
56db793a DB |
1293 | dominator. */ |
1294 | if (genop == NULL) | |
6b416da1 | 1295 | genop = bitmap_find_leader (NEW_SETS (block), expr); |
56db793a DB |
1296 | /* If it's still NULL, see if it is a complex expression, and if |
1297 | so, generate it recursively, otherwise, abort, because it's | |
1298 | not really . */ | |
1299 | if (genop == NULL) | |
1300 | { | |
33c94679 | 1301 | genop = VALUE_HANDLE_EXPR_SET (expr)->head->expr; |
6615c446 JO |
1302 | gcc_assert (UNARY_CLASS_P (genop) |
1303 | || BINARY_CLASS_P (genop) | |
1304 | || REFERENCE_CLASS_P (genop)); | |
56db793a DB |
1305 | genop = create_expression_by_pieces (block, genop, stmts); |
1306 | } | |
1307 | return genop; | |
1308 | } | |
1309 | ||
1310 | ||
1311 | /* Create an expression in pieces, so that we can handle very complex | |
1312 | expressions that may be ANTIC, but not necessary GIMPLE. | |
1313 | BLOCK is the basic block the expression will be inserted into, | |
1314 | EXPR is the expression to insert (in value form) | |
1315 | STMTS is a statement list to append the necessary insertions into. | |
1316 | ||
1317 | This function will abort if we hit some value that shouldn't be | |
1318 | ANTIC but is (IE there is no leader for it, or its components). | |
1319 | This function may also generate expressions that are themselves | |
1320 | partially or fully redundant. Those that are will be either made | |
1321 | fully redundant during the next iteration of insert (for partially | |
1322 | redundant ones), or eliminated by eliminate (for fully redundant | |
1323 | ones). */ | |
1324 | ||
1325 | static tree | |
1326 | create_expression_by_pieces (basic_block block, tree expr, tree stmts) | |
1327 | { | |
1328 | tree name = NULL_TREE; | |
1329 | tree newexpr = NULL_TREE; | |
1330 | tree v; | |
1331 | ||
1332 | switch (TREE_CODE_CLASS (TREE_CODE (expr))) | |
1333 | { | |
6615c446 | 1334 | case tcc_binary: |
56db793a DB |
1335 | { |
1336 | tree_stmt_iterator tsi; | |
1337 | tree genop1, genop2; | |
1338 | tree temp; | |
1339 | tree op1 = TREE_OPERAND (expr, 0); | |
1340 | tree op2 = TREE_OPERAND (expr, 1); | |
1341 | genop1 = find_or_generate_expression (block, op1, stmts); | |
1342 | genop2 = find_or_generate_expression (block, op2, stmts); | |
1343 | temp = create_tmp_var (TREE_TYPE (expr), "pretmp"); | |
1344 | add_referenced_tmp_var (temp); | |
1345 | newexpr = build (TREE_CODE (expr), TREE_TYPE (expr), | |
1346 | genop1, genop2); | |
1347 | newexpr = build (MODIFY_EXPR, TREE_TYPE (expr), | |
1348 | temp, newexpr); | |
1349 | name = make_ssa_name (temp, newexpr); | |
1350 | TREE_OPERAND (newexpr, 0) = name; | |
1351 | tsi = tsi_last (stmts); | |
1352 | tsi_link_after (&tsi, newexpr, TSI_CONTINUE_LINKING); | |
1353 | pre_stats.insertions++; | |
1354 | break; | |
1355 | } | |
6615c446 | 1356 | case tcc_unary: |
56db793a DB |
1357 | { |
1358 | tree_stmt_iterator tsi; | |
1359 | tree genop1; | |
1360 | tree temp; | |
1361 | tree op1 = TREE_OPERAND (expr, 0); | |
1362 | genop1 = find_or_generate_expression (block, op1, stmts); | |
1363 | temp = create_tmp_var (TREE_TYPE (expr), "pretmp"); | |
1364 | add_referenced_tmp_var (temp); | |
1365 | newexpr = build (TREE_CODE (expr), TREE_TYPE (expr), | |
1366 | genop1); | |
1367 | newexpr = build (MODIFY_EXPR, TREE_TYPE (expr), | |
1368 | temp, newexpr); | |
1369 | name = make_ssa_name (temp, newexpr); | |
1370 | TREE_OPERAND (newexpr, 0) = name; | |
1371 | tsi = tsi_last (stmts); | |
1372 | tsi_link_after (&tsi, newexpr, TSI_CONTINUE_LINKING); | |
1373 | pre_stats.insertions++; | |
1374 | ||
1375 | break; | |
1376 | } | |
1377 | default: | |
1e128c5f | 1378 | gcc_unreachable (); |
56db793a DB |
1379 | |
1380 | } | |
1381 | v = get_value_handle (expr); | |
ff2ad0f7 | 1382 | vn_add (name, v, NULL); |
6b416da1 | 1383 | bitmap_insert_into_set (NEW_SETS (block), name); |
bdee7684 | 1384 | bitmap_value_insert_into_set (AVAIL_OUT (block), name); |
56db793a DB |
1385 | if (dump_file && (dump_flags & TDF_DETAILS)) |
1386 | { | |
1387 | fprintf (dump_file, "Inserted "); | |
1388 | print_generic_expr (dump_file, newexpr, 0); | |
1389 | fprintf (dump_file, " in predecessor %d\n", block->index); | |
1390 | } | |
1391 | return name; | |
1392 | } | |
1393 | ||
7e6eb623 DB |
1394 | /* Perform insertion of partially redundant values. |
1395 | For BLOCK, do the following: | |
1396 | 1. Propagate the NEW_SETS of the dominator into the current block. | |
1397 | If the block has multiple predecessors, | |
1398 | 2a. Iterate over the ANTIC expressions for the block to see if | |
1399 | any of them are partially redundant. | |
1400 | 2b. If so, insert them into the necessary predecessors to make | |
1401 | the expression fully redundant. | |
1402 | 2c. Insert a new PHI merging the values of the predecessors. | |
1403 | 2d. Insert the new PHI, and the new expressions, into the | |
1404 | NEW_SETS set. | |
1405 | 3. Recursively call ourselves on the dominator children of BLOCK. | |
6de9cd9a | 1406 | |
7e6eb623 DB |
1407 | */ |
1408 | static bool | |
1409 | insert_aux (basic_block block) | |
6de9cd9a | 1410 | { |
7e6eb623 DB |
1411 | basic_block son; |
1412 | bool new_stuff = false; | |
6de9cd9a | 1413 | |
7e6eb623 | 1414 | if (block) |
6de9cd9a | 1415 | { |
7e6eb623 DB |
1416 | basic_block dom; |
1417 | dom = get_immediate_dominator (CDI_DOMINATORS, block); | |
1418 | if (dom) | |
a32b97a2 | 1419 | { |
3cd8c58a | 1420 | unsigned i; |
87c476a2 ZD |
1421 | bitmap_iterator bi; |
1422 | ||
6b416da1 | 1423 | bitmap_set_t newset = NEW_SETS (dom); |
87c476a2 ZD |
1424 | EXECUTE_IF_SET_IN_BITMAP (newset->expressions, 0, i, bi) |
1425 | { | |
1426 | bitmap_insert_into_set (NEW_SETS (block), ssa_name (i)); | |
1427 | bitmap_value_replace_in_set (AVAIL_OUT (block), ssa_name (i)); | |
1428 | } | |
628f6a4e | 1429 | if (EDGE_COUNT (block->preds) > 1) |
6de9cd9a | 1430 | { |
7e6eb623 DB |
1431 | value_set_node_t node; |
1432 | for (node = ANTIC_IN (block)->head; | |
1433 | node; | |
1434 | node = node->next) | |
6de9cd9a | 1435 | { |
6615c446 JO |
1436 | if (BINARY_CLASS_P (node->expr) |
1437 | || UNARY_CLASS_P (node->expr)) | |
6de9cd9a | 1438 | { |
7e6eb623 DB |
1439 | tree *avail; |
1440 | tree val; | |
1441 | bool by_some = false; | |
ca072a31 | 1442 | bool cant_insert = false; |
7e6eb623 DB |
1443 | bool all_same = true; |
1444 | tree first_s = NULL; | |
1445 | edge pred; | |
1446 | basic_block bprime; | |
1447 | tree eprime; | |
628f6a4e | 1448 | edge_iterator ei; |
ce25943a | 1449 | |
7e6eb623 | 1450 | val = get_value_handle (node->expr); |
6b416da1 | 1451 | if (bitmap_set_contains_value (PHI_GEN (block), val)) |
7e6eb623 | 1452 | continue; |
bdee7684 | 1453 | if (bitmap_set_contains_value (AVAIL_OUT (dom), val)) |
7e6eb623 DB |
1454 | { |
1455 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
1456 | fprintf (dump_file, "Found fully redundant value\n"); | |
1457 | continue; | |
1458 | } | |
628f6a4e | 1459 | |
ce25943a | 1460 | avail = xcalloc (last_basic_block, sizeof (tree)); |
628f6a4e | 1461 | FOR_EACH_EDGE (pred, ei, block->preds) |
7e6eb623 DB |
1462 | { |
1463 | tree vprime; | |
1464 | tree edoubleprime; | |
3f7d210d DB |
1465 | |
1466 | /* This can happen in the very weird case | |
1467 | that our fake infinite loop edges have caused a | |
1468 | critical edge to appear. */ | |
1469 | if (EDGE_CRITICAL_P (pred)) | |
1470 | { | |
1471 | cant_insert = true; | |
1472 | break; | |
1473 | } | |
7e6eb623 DB |
1474 | bprime = pred->src; |
1475 | eprime = phi_translate (node->expr, | |
1476 | ANTIC_IN (block), | |
1477 | bprime, block); | |
ce25943a DB |
1478 | |
1479 | /* eprime will generally only be NULL if the | |
1480 | value of the expression, translated | |
1481 | through the PHI for this predecessor, is | |
1482 | undefined. If that is the case, we can't | |
1483 | make the expression fully redundant, | |
1484 | because its value is undefined along a | |
1485 | predecessor path. We can thus break out | |
1486 | early because it doesn't matter what the | |
1487 | rest of the results are. */ | |
7e6eb623 | 1488 | if (eprime == NULL) |
ce25943a DB |
1489 | { |
1490 | cant_insert = true; | |
1491 | break; | |
1492 | } | |
7e6eb623 DB |
1493 | |
1494 | vprime = get_value_handle (eprime); | |
1e128c5f | 1495 | gcc_assert (vprime); |
bdee7684 DB |
1496 | edoubleprime = bitmap_find_leader (AVAIL_OUT (bprime), |
1497 | vprime); | |
7e6eb623 DB |
1498 | if (edoubleprime == NULL) |
1499 | { | |
1500 | avail[bprime->index] = eprime; | |
1501 | all_same = false; | |
1502 | } | |
1503 | else | |
1504 | { | |
1505 | avail[bprime->index] = edoubleprime; | |
ca072a31 | 1506 | by_some = true; |
7e6eb623 DB |
1507 | if (first_s == NULL) |
1508 | first_s = edoubleprime; | |
1509 | else if (first_s != edoubleprime) | |
1510 | all_same = false; | |
1e128c5f GB |
1511 | gcc_assert (first_s == edoubleprime |
1512 | || !operand_equal_p | |
1513 | (first_s, edoubleprime, 0)); | |
7e6eb623 DB |
1514 | } |
1515 | } | |
ca072a31 DB |
1516 | /* If we can insert it, it's not the same value |
1517 | already existing along every predecessor, and | |
1518 | it's defined by some predecessor, it is | |
1519 | partially redundant. */ | |
ce25943a | 1520 | if (!cant_insert && !all_same && by_some) |
7e6eb623 | 1521 | { |
628f6a4e | 1522 | tree type = TREE_TYPE (avail[EDGE_PRED (block, 0)->src->index]); |
ca072a31 | 1523 | tree temp; |
7e6eb623 DB |
1524 | if (dump_file && (dump_flags & TDF_DETAILS)) |
1525 | { | |
1526 | fprintf (dump_file, "Found partial redundancy for expression "); | |
1527 | print_generic_expr (dump_file, node->expr, 0); | |
1528 | fprintf (dump_file, "\n"); | |
1529 | } | |
1530 | ||
8c27b7d4 | 1531 | /* Make the necessary insertions. */ |
628f6a4e | 1532 | FOR_EACH_EDGE (pred, ei, block->preds) |
7e6eb623 | 1533 | { |
56db793a DB |
1534 | tree stmts = alloc_stmt_list (); |
1535 | tree builtexpr; | |
7e6eb623 DB |
1536 | bprime = pred->src; |
1537 | eprime = avail[bprime->index]; | |
6615c446 JO |
1538 | if (BINARY_CLASS_P (eprime) |
1539 | || UNARY_CLASS_P (eprime)) | |
7e6eb623 | 1540 | { |
56db793a DB |
1541 | builtexpr = create_expression_by_pieces (bprime, |
1542 | eprime, | |
1543 | stmts); | |
1544 | bsi_insert_on_edge (pred, stmts); | |
56db793a DB |
1545 | avail[bprime->index] = builtexpr; |
1546 | } | |
628f6a4e | 1547 | } |
7e6eb623 DB |
1548 | /* Now build a phi for the new variable. */ |
1549 | temp = create_tmp_var (type, "prephitmp"); | |
1550 | add_referenced_tmp_var (temp); | |
1551 | temp = create_phi_node (temp, block); | |
ff2ad0f7 | 1552 | vn_add (PHI_RESULT (temp), val, NULL); |
7e6eb623 DB |
1553 | |
1554 | #if 0 | |
1555 | if (!set_contains_value (AVAIL_OUT (block), val)) | |
1556 | insert_into_set (AVAIL_OUT (block), | |
1557 | PHI_RESULT (temp)); | |
1558 | else | |
1559 | #endif | |
bdee7684 DB |
1560 | bitmap_value_replace_in_set (AVAIL_OUT (block), |
1561 | PHI_RESULT (temp)); | |
628f6a4e | 1562 | FOR_EACH_EDGE (pred, ei, block->preds) |
7e6eb623 DB |
1563 | { |
1564 | add_phi_arg (&temp, avail[pred->src->index], | |
1565 | pred); | |
1566 | } | |
1567 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
1568 | { | |
1569 | fprintf (dump_file, "Created phi "); | |
1570 | print_generic_expr (dump_file, temp, 0); | |
1571 | fprintf (dump_file, " in block %d\n", block->index); | |
1572 | } | |
1573 | pre_stats.phis++; | |
1574 | new_stuff = true; | |
6b416da1 DB |
1575 | bitmap_insert_into_set (NEW_SETS (block), |
1576 | PHI_RESULT (temp)); | |
1577 | bitmap_insert_into_set (PHI_GEN (block), | |
1578 | PHI_RESULT (temp)); | |
7e6eb623 DB |
1579 | } |
1580 | ||
1581 | free (avail); | |
6de9cd9a DN |
1582 | } |
1583 | } | |
1584 | } | |
1585 | } | |
1586 | } | |
7e6eb623 DB |
1587 | for (son = first_dom_son (CDI_DOMINATORS, block); |
1588 | son; | |
1589 | son = next_dom_son (CDI_DOMINATORS, son)) | |
1590 | { | |
1591 | new_stuff |= insert_aux (son); | |
1592 | } | |
1593 | ||
1594 | return new_stuff; | |
6de9cd9a DN |
1595 | } |
1596 | ||
7e6eb623 | 1597 | /* Perform insertion of partially redundant values. */ |
6de9cd9a | 1598 | |
7e6eb623 DB |
1599 | static void |
1600 | insert (void) | |
6de9cd9a | 1601 | { |
7e6eb623 | 1602 | bool new_stuff = true; |
6de9cd9a | 1603 | basic_block bb; |
7e6eb623 | 1604 | int num_iterations = 0; |
bdee7684 | 1605 | |
7e6eb623 | 1606 | FOR_ALL_BB (bb) |
6b416da1 | 1607 | NEW_SETS (bb) = bitmap_set_new (); |
6de9cd9a | 1608 | |
7e6eb623 | 1609 | while (new_stuff) |
6de9cd9a | 1610 | { |
7e6eb623 DB |
1611 | num_iterations++; |
1612 | new_stuff = false; | |
1613 | new_stuff = insert_aux (ENTRY_BLOCK_PTR); | |
6de9cd9a | 1614 | } |
7e6eb623 DB |
1615 | if (num_iterations > 2 && dump_file && (dump_flags & TDF_STATS)) |
1616 | fprintf (dump_file, "insert required %d iterations\n", num_iterations); | |
1617 | } | |
6de9cd9a | 1618 | |
33c94679 | 1619 | |
ff2ad0f7 DN |
1620 | /* Return true if VAR is an SSA variable with no defining statement in |
1621 | this procedure, *AND* isn't a live-on-entry parameter. */ | |
33c94679 | 1622 | |
7e6eb623 DB |
1623 | static bool |
1624 | is_undefined_value (tree expr) | |
ff2ad0f7 DN |
1625 | { |
1626 | return (TREE_CODE (expr) == SSA_NAME | |
1627 | && IS_EMPTY_STMT (SSA_NAME_DEF_STMT (expr)) | |
1628 | /* PARM_DECLs and hard registers are always defined. */ | |
e670d9e4 | 1629 | && TREE_CODE (SSA_NAME_VAR (expr)) != PARM_DECL); |
ff2ad0f7 DN |
1630 | } |
1631 | ||
1632 | ||
1633 | /* Given an SSA variable VAR and an expression EXPR, compute the value | |
1634 | number for EXPR and create a value handle (VAL) for it. If VAR and | |
1635 | EXPR are not the same, associate VAL with VAR. Finally, add VAR to | |
1636 | S1 and its value handle to S2. | |
1637 | ||
1638 | VUSES represent the virtual use operands associated with EXPR (if | |
1639 | any). They are used when computing the hash value for EXPR. */ | |
1640 | ||
1641 | static inline void | |
6b416da1 | 1642 | add_to_sets (tree var, tree expr, vuse_optype vuses, bitmap_set_t s1, |
bdee7684 | 1643 | bitmap_set_t s2) |
ff2ad0f7 DN |
1644 | { |
1645 | tree val = vn_lookup_or_add (expr, vuses); | |
1646 | ||
1647 | /* VAR and EXPR may be the same when processing statements for which | |
1648 | we are not computing value numbers (e.g., non-assignments, or | |
1649 | statements that make aliased stores). In those cases, we are | |
1650 | only interested in making VAR available as its own value. */ | |
1651 | if (var != expr) | |
3d3fa3a1 | 1652 | vn_add (var, val, NULL); |
ff2ad0f7 | 1653 | |
6b416da1 | 1654 | bitmap_insert_into_set (s1, var); |
bdee7684 | 1655 | bitmap_value_insert_into_set (s2, var); |
ff2ad0f7 DN |
1656 | } |
1657 | ||
1658 | ||
1659 | /* Given a unary or binary expression EXPR, create and return a new | |
f6fe65dc | 1660 | expression with the same structure as EXPR but with its operands |
ff2ad0f7 DN |
1661 | replaced with the value handles of each of the operands of EXPR. |
1662 | Insert EXPR's operands into the EXP_GEN set for BLOCK. | |
1663 | ||
1664 | VUSES represent the virtual use operands associated with EXPR (if | |
1665 | any). They are used when computing the hash value for EXPR. */ | |
1666 | ||
1667 | static inline tree | |
1668 | create_value_expr_from (tree expr, basic_block block, vuse_optype vuses) | |
1669 | { | |
1670 | int i; | |
1671 | enum tree_code code = TREE_CODE (expr); | |
1672 | tree vexpr; | |
1673 | ||
6615c446 JO |
1674 | gcc_assert (TREE_CODE_CLASS (code) == tcc_unary |
1675 | || TREE_CODE_CLASS (code) == tcc_binary | |
1676 | || TREE_CODE_CLASS (code) == tcc_reference); | |
33c94679 | 1677 | |
6615c446 | 1678 | if (TREE_CODE_CLASS (code) == tcc_unary) |
ff2ad0f7 | 1679 | vexpr = pool_alloc (unary_node_pool); |
6615c446 | 1680 | else if (TREE_CODE_CLASS (code) == tcc_reference) |
3d3fa3a1 | 1681 | vexpr = pool_alloc (reference_node_pool); |
ff2ad0f7 DN |
1682 | else |
1683 | vexpr = pool_alloc (binary_node_pool); | |
1684 | ||
1685 | memcpy (vexpr, expr, tree_size (expr)); | |
1686 | ||
1687 | for (i = 0; i < TREE_CODE_LENGTH (code); i++) | |
6de9cd9a | 1688 | { |
ff2ad0f7 | 1689 | tree op = TREE_OPERAND (expr, i); |
bdee7684 DB |
1690 | if (op != NULL) |
1691 | { | |
1692 | tree val = vn_lookup_or_add (op, vuses); | |
1693 | if (!is_undefined_value (op)) | |
1694 | value_insert_into_set (EXP_GEN (block), op); | |
af75a7ea DB |
1695 | if (TREE_CODE (val) == VALUE_HANDLE) |
1696 | TREE_TYPE (val) = TREE_TYPE (TREE_OPERAND (vexpr, i)); | |
bdee7684 DB |
1697 | TREE_OPERAND (vexpr, i) = val; |
1698 | } | |
6de9cd9a | 1699 | } |
33c94679 | 1700 | |
ff2ad0f7 | 1701 | return vexpr; |
6de9cd9a DN |
1702 | } |
1703 | ||
ff2ad0f7 | 1704 | |
7e6eb623 DB |
1705 | /* Compute the AVAIL set for BLOCK. |
1706 | This function performs value numbering of the statements in BLOCK. | |
1707 | The AVAIL sets are built from information we glean while doing this | |
ff2ad0f7 | 1708 | value numbering, since the AVAIL sets contain only one entry per |
7e6eb623 | 1709 | value. |
7e6eb623 DB |
1710 | |
1711 | AVAIL_IN[BLOCK] = AVAIL_OUT[dom(BLOCK)]. | |
ff2ad0f7 | 1712 | AVAIL_OUT[BLOCK] = AVAIL_IN[BLOCK] U PHI_GEN[BLOCK] U TMP_GEN[BLOCK]. */ |
6de9cd9a | 1713 | |
7e6eb623 DB |
1714 | static void |
1715 | compute_avail (basic_block block) | |
6de9cd9a | 1716 | { |
6de9cd9a | 1717 | basic_block son; |
6de9cd9a | 1718 | |
7e6eb623 DB |
1719 | /* For arguments with default definitions, we pretend they are |
1720 | defined in the entry block. */ | |
1721 | if (block == ENTRY_BLOCK_PTR) | |
1722 | { | |
1723 | tree param; | |
1724 | for (param = DECL_ARGUMENTS (current_function_decl); | |
1725 | param; | |
1726 | param = TREE_CHAIN (param)) | |
1727 | { | |
1728 | if (default_def (param) != NULL) | |
1729 | { | |
1730 | tree val; | |
1731 | tree def = default_def (param); | |
ff2ad0f7 | 1732 | val = vn_lookup_or_add (def, NULL); |
6b416da1 | 1733 | bitmap_insert_into_set (TMP_GEN (block), def); |
bdee7684 | 1734 | bitmap_value_insert_into_set (AVAIL_OUT (block), def); |
7e6eb623 DB |
1735 | } |
1736 | } | |
1737 | } | |
1738 | else if (block) | |
6de9cd9a | 1739 | { |
7e6eb623 DB |
1740 | block_stmt_iterator bsi; |
1741 | tree stmt, phi; | |
1742 | basic_block dom; | |
1743 | ||
ff2ad0f7 DN |
1744 | /* Initially, the set of available values in BLOCK is that of |
1745 | its immediate dominator. */ | |
7e6eb623 DB |
1746 | dom = get_immediate_dominator (CDI_DOMINATORS, block); |
1747 | if (dom) | |
bdee7684 | 1748 | bitmap_set_copy (AVAIL_OUT (block), AVAIL_OUT (dom)); |
33c94679 | 1749 | |
ff2ad0f7 | 1750 | /* Generate values for PHI nodes. */ |
17192884 | 1751 | for (phi = phi_nodes (block); phi; phi = PHI_CHAIN (phi)) |
6b416da1 DB |
1752 | /* We have no need for virtual phis, as they don't represent |
1753 | actual computations. */ | |
1754 | if (is_gimple_reg (PHI_RESULT (phi))) | |
1755 | add_to_sets (PHI_RESULT (phi), PHI_RESULT (phi), NULL, | |
1756 | PHI_GEN (block), AVAIL_OUT (block)); | |
7e6eb623 | 1757 | |
ff2ad0f7 DN |
1758 | /* Now compute value numbers and populate value sets with all |
1759 | the expressions computed in BLOCK. */ | |
7e6eb623 | 1760 | for (bsi = bsi_start (block); !bsi_end_p (bsi); bsi_next (&bsi)) |
6de9cd9a | 1761 | { |
ff2ad0f7 DN |
1762 | stmt_ann_t ann; |
1763 | size_t j; | |
1764 | ||
7e6eb623 | 1765 | stmt = bsi_stmt (bsi); |
ff2ad0f7 | 1766 | ann = stmt_ann (stmt); |
7e6eb623 | 1767 | get_stmt_operands (stmt); |
ff2ad0f7 DN |
1768 | |
1769 | /* We are only interested in assignments of the form | |
1770 | X_i = EXPR, where EXPR represents an "interesting" | |
1771 | computation, it has no volatile operands and X_i | |
1772 | doesn't flow through an abnormal edge. */ | |
1773 | if (TREE_CODE (stmt) == MODIFY_EXPR | |
1774 | && !ann->has_volatile_ops | |
1775 | && TREE_CODE (TREE_OPERAND (stmt, 0)) == SSA_NAME | |
1776 | && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (TREE_OPERAND (stmt, 0))) | |
7e6eb623 | 1777 | { |
ff2ad0f7 DN |
1778 | tree lhs = TREE_OPERAND (stmt, 0); |
1779 | tree rhs = TREE_OPERAND (stmt, 1); | |
1780 | vuse_optype vuses = STMT_VUSE_OPS (stmt); | |
1781 | ||
1782 | STRIP_USELESS_TYPE_CONVERSION (rhs); | |
3d3fa3a1 DB |
1783 | if (TREE_CODE (rhs) == SSA_NAME |
1784 | || is_gimple_min_invariant (rhs)) | |
1785 | { | |
1786 | /* Compute a value number for the RHS of the statement | |
1787 | and add its value to the AVAIL_OUT set for the block. | |
1788 | Add the LHS to TMP_GEN. */ | |
1789 | add_to_sets (lhs, rhs, vuses, TMP_GEN (block), | |
1790 | AVAIL_OUT (block)); | |
1791 | ||
1792 | if (TREE_CODE (rhs) == SSA_NAME | |
1793 | && !is_undefined_value (rhs)) | |
1794 | value_insert_into_set (EXP_GEN (block), rhs); | |
1795 | continue; | |
1796 | } | |
6615c446 | 1797 | else if (UNARY_CLASS_P (rhs) || BINARY_CLASS_P (rhs) |
3d3fa3a1 | 1798 | || TREE_CODE (rhs) == INDIRECT_REF) |
7e6eb623 | 1799 | { |
bdee7684 DB |
1800 | /* For binary, unary, and reference expressions, |
1801 | create a duplicate expression with the operands | |
1802 | replaced with the value handles of the original | |
1803 | RHS. */ | |
ff2ad0f7 DN |
1804 | tree newt = create_value_expr_from (rhs, block, vuses); |
1805 | add_to_sets (lhs, newt, vuses, TMP_GEN (block), | |
1806 | AVAIL_OUT (block)); | |
1807 | value_insert_into_set (EXP_GEN (block), newt); | |
1808 | continue; | |
7e6eb623 | 1809 | } |
7e6eb623 | 1810 | } |
56db793a | 1811 | |
ff2ad0f7 DN |
1812 | /* For any other statement that we don't recognize, simply |
1813 | make the names generated by the statement available in | |
1814 | AVAIL_OUT and TMP_GEN. */ | |
1815 | for (j = 0; j < NUM_DEFS (STMT_DEF_OPS (stmt)); j++) | |
6de9cd9a | 1816 | { |
ff2ad0f7 DN |
1817 | tree def = DEF_OP (STMT_DEF_OPS (stmt), j); |
1818 | add_to_sets (def, def, NULL, TMP_GEN (block), | |
1819 | AVAIL_OUT (block)); | |
7e6eb623 | 1820 | } |
ff2ad0f7 DN |
1821 | |
1822 | for (j = 0; j < NUM_USES (STMT_USE_OPS (stmt)); j++) | |
7e6eb623 | 1823 | { |
ff2ad0f7 DN |
1824 | tree use = USE_OP (STMT_USE_OPS (stmt), j); |
1825 | add_to_sets (use, use, NULL, TMP_GEN (block), | |
1826 | AVAIL_OUT (block)); | |
6de9cd9a DN |
1827 | } |
1828 | } | |
6de9cd9a | 1829 | } |
33c94679 | 1830 | |
ff2ad0f7 | 1831 | /* Compute available sets for the dominator children of BLOCK. */ |
6de9cd9a DN |
1832 | for (son = first_dom_son (CDI_DOMINATORS, block); |
1833 | son; | |
1834 | son = next_dom_son (CDI_DOMINATORS, son)) | |
7e6eb623 | 1835 | compute_avail (son); |
7e6eb623 DB |
1836 | } |
1837 | ||
33c94679 | 1838 | |
7e6eb623 DB |
1839 | /* Eliminate fully redundant computations. */ |
1840 | ||
1841 | static void | |
1842 | eliminate (void) | |
1843 | { | |
1844 | basic_block b; | |
1845 | ||
1846 | FOR_EACH_BB (b) | |
1847 | { | |
1848 | block_stmt_iterator i; | |
1849 | ||
1850 | for (i = bsi_start (b); !bsi_end_p (i); bsi_next (&i)) | |
1851 | { | |
1852 | tree stmt = bsi_stmt (i); | |
1853 | ||
ff2ad0f7 DN |
1854 | /* Lookup the RHS of the expression, see if we have an |
1855 | available computation for it. If so, replace the RHS with | |
7e6eb623 | 1856 | the available computation. */ |
ff2ad0f7 DN |
1857 | if (TREE_CODE (stmt) == MODIFY_EXPR |
1858 | && TREE_CODE (TREE_OPERAND (stmt, 0)) == SSA_NAME | |
1859 | && TREE_CODE (TREE_OPERAND (stmt ,1)) != SSA_NAME | |
1860 | && !is_gimple_min_invariant (TREE_OPERAND (stmt, 1)) | |
1861 | && !stmt_ann (stmt)->has_volatile_ops) | |
1862 | { | |
1863 | tree lhs = TREE_OPERAND (stmt, 0); | |
1864 | tree *rhs_p = &TREE_OPERAND (stmt, 1); | |
1865 | tree sprime; | |
ff2ad0f7 | 1866 | |
3d3fa3a1 DB |
1867 | sprime = bitmap_find_leader (AVAIL_OUT (b), |
1868 | vn_lookup (lhs, NULL)); | |
ff2ad0f7 DN |
1869 | if (sprime |
1870 | && sprime != lhs | |
1871 | && (TREE_CODE (*rhs_p) != SSA_NAME | |
1872 | || may_propagate_copy (*rhs_p, sprime))) | |
1873 | { | |
1e128c5f | 1874 | gcc_assert (sprime != *rhs_p); |
ff2ad0f7 | 1875 | |
7e6eb623 DB |
1876 | if (dump_file && (dump_flags & TDF_DETAILS)) |
1877 | { | |
1878 | fprintf (dump_file, "Replaced "); | |
ff2ad0f7 | 1879 | print_generic_expr (dump_file, *rhs_p, 0); |
7e6eb623 DB |
1880 | fprintf (dump_file, " with "); |
1881 | print_generic_expr (dump_file, sprime, 0); | |
1882 | fprintf (dump_file, " in "); | |
1883 | print_generic_stmt (dump_file, stmt, 0); | |
1884 | } | |
1885 | pre_stats.eliminations++; | |
ff2ad0f7 DN |
1886 | propagate_tree_value (rhs_p, sprime); |
1887 | modify_stmt (stmt); | |
53b4bf74 DN |
1888 | |
1889 | /* If we removed EH side effects from the statement, clean | |
1890 | its EH information. */ | |
1891 | if (maybe_clean_eh_stmt (stmt)) | |
1892 | { | |
1893 | bitmap_set_bit (need_eh_cleanup, | |
1894 | bb_for_stmt (stmt)->index); | |
1895 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
1896 | fprintf (dump_file, " Removed EH side effects.\n"); | |
1897 | } | |
ff2ad0f7 DN |
1898 | } |
1899 | } | |
7e6eb623 DB |
1900 | } |
1901 | } | |
6de9cd9a DN |
1902 | } |
1903 | ||
33c94679 | 1904 | |
ff2ad0f7 | 1905 | /* Initialize data structures used by PRE. */ |
6de9cd9a DN |
1906 | |
1907 | static void | |
ff2ad0f7 | 1908 | init_pre (void) |
6de9cd9a | 1909 | { |
7e6eb623 | 1910 | basic_block bb; |
ff2ad0f7 | 1911 | |
50265400 | 1912 | connect_infinite_loops_to_exit (); |
ff2ad0f7 | 1913 | vn_init (); |
7e6eb623 | 1914 | memset (&pre_stats, 0, sizeof (pre_stats)); |
53b4bf74 DN |
1915 | |
1916 | /* If block 0 has more than one predecessor, it means that its PHI | |
1917 | nodes will have arguments coming from block -1. This creates | |
1918 | problems for several places in PRE that keep local arrays indexed | |
1919 | by block number. To prevent this, we split the edge coming from | |
1920 | ENTRY_BLOCK_PTR (FIXME, if ENTRY_BLOCK_PTR had an index number | |
1921 | different than -1 we wouldn't have to hack this. tree-ssa-dce.c | |
1922 | needs a similar change). */ | |
628f6a4e BE |
1923 | if (EDGE_COUNT (EDGE_SUCC (ENTRY_BLOCK_PTR, 0)->dest->preds) > 1) |
1924 | if (!(EDGE_SUCC (ENTRY_BLOCK_PTR, 0)->flags & EDGE_ABNORMAL)) | |
1925 | split_edge (EDGE_SUCC (ENTRY_BLOCK_PTR, 0)); | |
53b4bf74 | 1926 | |
7e6eb623 | 1927 | FOR_ALL_BB (bb) |
ff2ad0f7 DN |
1928 | bb->aux = xcalloc (1, sizeof (struct bb_value_sets)); |
1929 | ||
c4817ba6 | 1930 | gcc_obstack_init (&grand_bitmap_obstack); |
7e6eb623 | 1931 | phi_translate_table = htab_create (511, expr_pred_trans_hash, |
ff2ad0f7 | 1932 | expr_pred_trans_eq, free); |
7e6eb623 DB |
1933 | value_set_pool = create_alloc_pool ("Value sets", |
1934 | sizeof (struct value_set), 30); | |
bdee7684 DB |
1935 | bitmap_set_pool = create_alloc_pool ("Bitmap sets", |
1936 | sizeof (struct bitmap_set), 30); | |
7e6eb623 | 1937 | value_set_node_pool = create_alloc_pool ("Value set nodes", |
ff2ad0f7 | 1938 | sizeof (struct value_set_node), 30); |
7e6eb623 | 1939 | calculate_dominance_info (CDI_POST_DOMINATORS); |
6de9cd9a | 1940 | calculate_dominance_info (CDI_DOMINATORS); |
a38b644b ZW |
1941 | binary_node_pool = create_alloc_pool ("Binary tree nodes", |
1942 | tree_code_size (PLUS_EXPR), 30); | |
1943 | unary_node_pool = create_alloc_pool ("Unary tree nodes", | |
1944 | tree_code_size (NEGATE_EXPR), 30); | |
1945 | reference_node_pool = create_alloc_pool ("Reference tree nodes", | |
6048b706 | 1946 | tree_code_size (ARRAY_REF), 30); |
7e6eb623 DB |
1947 | FOR_ALL_BB (bb) |
1948 | { | |
1949 | EXP_GEN (bb) = set_new (true); | |
6b416da1 DB |
1950 | PHI_GEN (bb) = bitmap_set_new (); |
1951 | TMP_GEN (bb) = bitmap_set_new (); | |
bdee7684 | 1952 | AVAIL_OUT (bb) = bitmap_set_new (); |
7e6eb623 | 1953 | } |
53b4bf74 DN |
1954 | |
1955 | need_eh_cleanup = BITMAP_XMALLOC (); | |
ff2ad0f7 DN |
1956 | } |
1957 | ||
1958 | ||
1959 | /* Deallocate data structures used by PRE. */ | |
6de9cd9a | 1960 | |
ff2ad0f7 DN |
1961 | static void |
1962 | fini_pre (void) | |
1963 | { | |
1964 | basic_block bb; | |
3aecd08b JL |
1965 | unsigned int i; |
1966 | ||
8eee3528 | 1967 | bsi_commit_edge_inserts (NULL); |
ff2ad0f7 | 1968 | |
c4817ba6 | 1969 | obstack_free (&grand_bitmap_obstack, NULL); |
ff2ad0f7 | 1970 | free_alloc_pool (value_set_pool); |
bdee7684 | 1971 | free_alloc_pool (bitmap_set_pool); |
ff2ad0f7 DN |
1972 | free_alloc_pool (value_set_node_pool); |
1973 | free_alloc_pool (binary_node_pool); | |
3d3fa3a1 | 1974 | free_alloc_pool (reference_node_pool); |
ff2ad0f7 DN |
1975 | free_alloc_pool (unary_node_pool); |
1976 | htab_delete (phi_translate_table); | |
6809cbf9 | 1977 | remove_fake_exit_edges (); |
50265400 | 1978 | |
ff2ad0f7 DN |
1979 | FOR_ALL_BB (bb) |
1980 | { | |
1981 | free (bb->aux); | |
1982 | bb->aux = NULL; | |
1983 | } | |
6809cbf9 | 1984 | |
ff2ad0f7 DN |
1985 | free_dominance_info (CDI_POST_DOMINATORS); |
1986 | vn_delete (); | |
53b4bf74 | 1987 | |
eb59b8de | 1988 | if (!bitmap_empty_p (need_eh_cleanup)) |
53b4bf74 DN |
1989 | { |
1990 | tree_purge_all_dead_eh_edges (need_eh_cleanup); | |
1991 | cleanup_tree_cfg (); | |
1992 | } | |
1993 | ||
1994 | BITMAP_XFREE (need_eh_cleanup); | |
3aecd08b JL |
1995 | |
1996 | /* Wipe out pointers to VALUE_HANDLEs. In the not terribly distant | |
1997 | future we will want them to be persistent though. */ | |
1998 | for (i = 0; i < num_ssa_names; i++) | |
1999 | { | |
2000 | tree name = ssa_name (i); | |
2001 | ||
2002 | if (!name) | |
2003 | continue; | |
2004 | ||
2005 | if (SSA_NAME_VALUE (name) | |
2006 | && TREE_CODE (SSA_NAME_VALUE (name)) == VALUE_HANDLE) | |
2007 | SSA_NAME_VALUE (name) = NULL; | |
2008 | } | |
ff2ad0f7 DN |
2009 | } |
2010 | ||
2011 | ||
2012 | /* Main entry point to the SSA-PRE pass. DO_FRE is true if the caller | |
2013 | only wants to do full redundancy elimination. */ | |
2014 | ||
2015 | static void | |
2016 | execute_pre (bool do_fre) | |
2017 | { | |
2018 | init_pre (); | |
2019 | ||
2020 | /* Collect and value number expressions computed in each basic | |
2021 | block. */ | |
7e6eb623 | 2022 | compute_avail (ENTRY_BLOCK_PTR); |
6de9cd9a | 2023 | |
7e6eb623 DB |
2024 | if (dump_file && (dump_flags & TDF_DETAILS)) |
2025 | { | |
ff2ad0f7 DN |
2026 | basic_block bb; |
2027 | ||
7e6eb623 DB |
2028 | FOR_ALL_BB (bb) |
2029 | { | |
2030 | print_value_set (dump_file, EXP_GEN (bb), "exp_gen", bb->index); | |
6b416da1 DB |
2031 | bitmap_print_value_set (dump_file, TMP_GEN (bb), "tmp_gen", |
2032 | bb->index); | |
bdee7684 DB |
2033 | bitmap_print_value_set (dump_file, AVAIL_OUT (bb), "avail_out", |
2034 | bb->index); | |
7e6eb623 DB |
2035 | } |
2036 | } | |
6de9cd9a | 2037 | |
7e6eb623 DB |
2038 | /* Insert can get quite slow on an incredibly large number of basic |
2039 | blocks due to some quadratic behavior. Until this behavior is | |
2040 | fixed, don't run it when he have an incredibly large number of | |
2041 | bb's. If we aren't going to run insert, there is no point in | |
2042 | computing ANTIC, either, even though it's plenty fast. */ | |
ff2ad0f7 | 2043 | if (!do_fre && n_basic_blocks < 4000) |
6de9cd9a | 2044 | { |
7e6eb623 | 2045 | compute_antic (); |
7e6eb623 DB |
2046 | insert (); |
2047 | } | |
ff2ad0f7 DN |
2048 | |
2049 | /* Remove all the redundant expressions. */ | |
7e6eb623 DB |
2050 | eliminate (); |
2051 | ||
2052 | if (dump_file && (dump_flags & TDF_STATS)) | |
2053 | { | |
2054 | fprintf (dump_file, "Insertions:%d\n", pre_stats.insertions); | |
2055 | fprintf (dump_file, "New PHIs:%d\n", pre_stats.phis); | |
2056 | fprintf (dump_file, "Eliminated:%d\n", pre_stats.eliminations); | |
6de9cd9a DN |
2057 | } |
2058 | ||
ff2ad0f7 DN |
2059 | fini_pre (); |
2060 | } | |
2061 | ||
2062 | ||
2063 | /* Gate and execute functions for PRE. */ | |
2064 | ||
2065 | static void | |
2066 | do_pre (void) | |
2067 | { | |
2068 | execute_pre (false); | |
6de9cd9a DN |
2069 | } |
2070 | ||
2071 | static bool | |
2072 | gate_pre (void) | |
2073 | { | |
2074 | return flag_tree_pre != 0; | |
2075 | } | |
2076 | ||
7e6eb623 | 2077 | struct tree_opt_pass pass_pre = |
6de9cd9a DN |
2078 | { |
2079 | "pre", /* name */ | |
2080 | gate_pre, /* gate */ | |
ff2ad0f7 | 2081 | do_pre, /* execute */ |
6de9cd9a DN |
2082 | NULL, /* sub */ |
2083 | NULL, /* next */ | |
2084 | 0, /* static_pass_number */ | |
2085 | TV_TREE_PRE, /* tv_id */ | |
c1b763fa DN |
2086 | PROP_no_crit_edges | PROP_cfg |
2087 | | PROP_ssa | PROP_alias, /* properties_required */ | |
6de9cd9a DN |
2088 | 0, /* properties_provided */ |
2089 | 0, /* properties_destroyed */ | |
2090 | 0, /* todo_flags_start */ | |
9f8628ba PB |
2091 | TODO_dump_func | TODO_ggc_collect | TODO_verify_ssa, /* todo_flags_finish */ |
2092 | 0 /* letter */ | |
6de9cd9a | 2093 | }; |
ff2ad0f7 DN |
2094 | |
2095 | ||
2096 | /* Gate and execute functions for FRE. */ | |
2097 | ||
2098 | static void | |
2099 | do_fre (void) | |
2100 | { | |
2101 | execute_pre (true); | |
2102 | } | |
2103 | ||
2104 | static bool | |
2105 | gate_fre (void) | |
2106 | { | |
2107 | return flag_tree_fre != 0; | |
2108 | } | |
2109 | ||
2110 | struct tree_opt_pass pass_fre = | |
2111 | { | |
2112 | "fre", /* name */ | |
2113 | gate_fre, /* gate */ | |
2114 | do_fre, /* execute */ | |
2115 | NULL, /* sub */ | |
2116 | NULL, /* next */ | |
2117 | 0, /* static_pass_number */ | |
2118 | TV_TREE_FRE, /* tv_id */ | |
c1b763fa | 2119 | PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */ |
ff2ad0f7 DN |
2120 | 0, /* properties_provided */ |
2121 | 0, /* properties_destroyed */ | |
2122 | 0, /* todo_flags_start */ | |
9f8628ba PB |
2123 | TODO_dump_func | TODO_ggc_collect | TODO_verify_ssa, /* todo_flags_finish */ |
2124 | 0 /* letter */ | |
ff2ad0f7 | 2125 | }; |