]>
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 | { | |
3cd8c58a | 771 | unsigned i; |
87c476a2 ZD |
772 | bitmap_iterator bi; |
773 | ||
774 | EXECUTE_IF_SET_IN_BITMAP (set->expressions, 0, i, bi) | |
775 | { | |
776 | print_generic_expr (outfile, ssa_name (i), 0); | |
bdee7684 | 777 | |
87c476a2 ZD |
778 | fprintf (outfile, " ("); |
779 | print_generic_expr (outfile, get_value_handle (ssa_name (i)), 0); | |
780 | fprintf (outfile, ") "); | |
3cd8c58a | 781 | if (bitmap_last_set_bit (set->expressions) != (int)i) |
87c476a2 ZD |
782 | fprintf (outfile, ", "); |
783 | } | |
bdee7684 DB |
784 | } |
785 | fprintf (outfile, " }\n"); | |
786 | } | |
7e6eb623 | 787 | /* Print out the value_set SET to OUTFILE. */ |
6de9cd9a | 788 | |
7e6eb623 DB |
789 | static void |
790 | print_value_set (FILE *outfile, value_set_t set, | |
791 | const char *setname, int blockindex) | |
6de9cd9a | 792 | { |
7e6eb623 DB |
793 | value_set_node_t node; |
794 | fprintf (outfile, "%s[%d] := { ", setname, blockindex); | |
795 | if (set) | |
6de9cd9a | 796 | { |
7e6eb623 DB |
797 | for (node = set->head; |
798 | node; | |
799 | node = node->next) | |
6de9cd9a | 800 | { |
7e6eb623 | 801 | print_generic_expr (outfile, node->expr, 0); |
ca072a31 DB |
802 | |
803 | fprintf (outfile, " ("); | |
804 | print_generic_expr (outfile, get_value_handle (node->expr), 0); | |
805 | fprintf (outfile, ") "); | |
806 | ||
7e6eb623 DB |
807 | if (node->next) |
808 | fprintf (outfile, ", "); | |
6de9cd9a | 809 | } |
6de9cd9a DN |
810 | } |
811 | ||
7e6eb623 DB |
812 | fprintf (outfile, " }\n"); |
813 | } | |
814 | ||
815 | /* Print out the expressions that have VAL to OUTFILE. */ | |
33c94679 | 816 | |
7e6eb623 DB |
817 | void |
818 | print_value_expressions (FILE *outfile, tree val) | |
819 | { | |
33c94679 DN |
820 | if (VALUE_HANDLE_EXPR_SET (val)) |
821 | { | |
822 | char s[10]; | |
823 | sprintf (s, "VH.%04d", VALUE_HANDLE_ID (val)); | |
824 | print_value_set (outfile, VALUE_HANDLE_EXPR_SET (val), s, 0); | |
825 | } | |
6de9cd9a DN |
826 | } |
827 | ||
6de9cd9a | 828 | |
7e6eb623 DB |
829 | void |
830 | debug_value_expressions (tree val) | |
6de9cd9a | 831 | { |
7e6eb623 DB |
832 | print_value_expressions (stderr, val); |
833 | } | |
834 | ||
6de9cd9a | 835 | |
7e6eb623 | 836 | void debug_value_set (value_set_t, const char *, int); |
6de9cd9a | 837 | |
7e6eb623 DB |
838 | void |
839 | debug_value_set (value_set_t set, const char *setname, int blockindex) | |
6de9cd9a | 840 | { |
7e6eb623 | 841 | print_value_set (stderr, set, setname, blockindex); |
6de9cd9a DN |
842 | } |
843 | ||
7e6eb623 DB |
844 | /* Translate EXPR using phis in PHIBLOCK, so that it has the values of |
845 | the phis in PRED. Return NULL if we can't find a leader for each | |
846 | part of the translated expression. */ | |
6de9cd9a DN |
847 | |
848 | static tree | |
ff2ad0f7 | 849 | phi_translate (tree expr, value_set_t set, basic_block pred, |
7e6eb623 | 850 | basic_block phiblock) |
6de9cd9a | 851 | { |
7e6eb623 DB |
852 | tree phitrans = NULL; |
853 | tree oldexpr = expr; | |
6de9cd9a | 854 | |
7e6eb623 DB |
855 | if (expr == NULL) |
856 | return NULL; | |
6de9cd9a | 857 | |
6615c446 JO |
858 | if (is_gimple_min_invariant (expr)) |
859 | return expr; | |
860 | ||
ea4b7848 | 861 | /* Phi translations of a given expression don't change. */ |
7e6eb623 DB |
862 | phitrans = phi_trans_lookup (expr, pred); |
863 | if (phitrans) | |
864 | return phitrans; | |
865 | ||
7e6eb623 | 866 | switch (TREE_CODE_CLASS (TREE_CODE (expr))) |
6de9cd9a | 867 | { |
6615c446 | 868 | case tcc_reference: |
471854f8 | 869 | /* XXX: Until we have PRE of loads working, none will be ANTIC. */ |
6615c446 JO |
870 | return NULL; |
871 | ||
872 | case tcc_binary: | |
7e6eb623 DB |
873 | { |
874 | tree oldop1 = TREE_OPERAND (expr, 0); | |
875 | tree oldop2 = TREE_OPERAND (expr, 1); | |
876 | tree newop1; | |
877 | tree newop2; | |
878 | tree newexpr; | |
879 | ||
880 | newop1 = phi_translate (find_leader (set, oldop1), | |
881 | set, pred, phiblock); | |
882 | if (newop1 == NULL) | |
883 | return NULL; | |
884 | newop2 = phi_translate (find_leader (set, oldop2), | |
885 | set, pred, phiblock); | |
886 | if (newop2 == NULL) | |
887 | return NULL; | |
888 | if (newop1 != oldop1 || newop2 != oldop2) | |
889 | { | |
890 | newexpr = pool_alloc (binary_node_pool); | |
891 | memcpy (newexpr, expr, tree_size (expr)); | |
06d72ee6 | 892 | create_tree_ann (newexpr); |
7e6eb623 DB |
893 | TREE_OPERAND (newexpr, 0) = newop1 == oldop1 ? oldop1 : get_value_handle (newop1); |
894 | TREE_OPERAND (newexpr, 1) = newop2 == oldop2 ? oldop2 : get_value_handle (newop2); | |
ff2ad0f7 | 895 | vn_lookup_or_add (newexpr, NULL); |
7e6eb623 DB |
896 | expr = newexpr; |
897 | phi_trans_add (oldexpr, newexpr, pred); | |
898 | } | |
899 | } | |
6615c446 JO |
900 | return expr; |
901 | ||
902 | case tcc_unary: | |
7e6eb623 DB |
903 | { |
904 | tree oldop1 = TREE_OPERAND (expr, 0); | |
905 | tree newop1; | |
906 | tree newexpr; | |
907 | ||
908 | newop1 = phi_translate (find_leader (set, oldop1), | |
909 | set, pred, phiblock); | |
910 | if (newop1 == NULL) | |
911 | return NULL; | |
912 | if (newop1 != oldop1) | |
913 | { | |
ca072a31 | 914 | newexpr = pool_alloc (unary_node_pool); |
7e6eb623 | 915 | memcpy (newexpr, expr, tree_size (expr)); |
06d72ee6 | 916 | create_tree_ann (newexpr); |
7e6eb623 | 917 | TREE_OPERAND (newexpr, 0) = get_value_handle (newop1); |
ff2ad0f7 | 918 | vn_lookup_or_add (newexpr, NULL); |
7e6eb623 DB |
919 | expr = newexpr; |
920 | phi_trans_add (oldexpr, newexpr, pred); | |
921 | } | |
922 | } | |
6615c446 JO |
923 | return expr; |
924 | ||
925 | case tcc_exceptional: | |
7e6eb623 DB |
926 | { |
927 | tree phi = NULL; | |
928 | int i; | |
1e128c5f | 929 | gcc_assert (TREE_CODE (expr) == SSA_NAME); |
7e6eb623 DB |
930 | if (TREE_CODE (SSA_NAME_DEF_STMT (expr)) == PHI_NODE) |
931 | phi = SSA_NAME_DEF_STMT (expr); | |
932 | else | |
933 | return expr; | |
934 | ||
935 | for (i = 0; i < PHI_NUM_ARGS (phi); i++) | |
936 | if (PHI_ARG_EDGE (phi, i)->src == pred) | |
6de9cd9a | 937 | { |
7e6eb623 DB |
938 | tree val; |
939 | if (is_undefined_value (PHI_ARG_DEF (phi, i))) | |
940 | return NULL; | |
ff2ad0f7 | 941 | val = vn_lookup_or_add (PHI_ARG_DEF (phi, i), NULL); |
7e6eb623 | 942 | return PHI_ARG_DEF (phi, i); |
6de9cd9a | 943 | } |
7e6eb623 | 944 | } |
6615c446 JO |
945 | return expr; |
946 | ||
947 | default: | |
948 | gcc_unreachable (); | |
6de9cd9a DN |
949 | } |
950 | } | |
951 | ||
6de9cd9a | 952 | static void |
7e6eb623 DB |
953 | phi_translate_set (value_set_t dest, value_set_t set, basic_block pred, |
954 | basic_block phiblock) | |
6de9cd9a | 955 | { |
7e6eb623 DB |
956 | value_set_node_t node; |
957 | for (node = set->head; | |
958 | node; | |
959 | node = node->next) | |
6de9cd9a | 960 | { |
7e6eb623 DB |
961 | tree translated; |
962 | translated = phi_translate (node->expr, set, pred, phiblock); | |
963 | phi_trans_add (node->expr, translated, pred); | |
6de9cd9a | 964 | |
7e6eb623 DB |
965 | if (translated != NULL) |
966 | value_insert_into_set (dest, translated); | |
967 | } | |
6de9cd9a DN |
968 | } |
969 | ||
bdee7684 DB |
970 | /* Find the leader for a value (i.e., the name representing that |
971 | value) in a given set, and return it. Return NULL if no leader is | |
972 | found. */ | |
973 | ||
974 | static tree | |
975 | bitmap_find_leader (bitmap_set_t set, tree val) | |
976 | { | |
977 | if (val == NULL) | |
978 | return NULL; | |
979 | ||
980 | if (is_gimple_min_invariant (val)) | |
981 | return val; | |
982 | if (bitmap_set_contains_value (set, val)) | |
983 | { | |
6b416da1 DB |
984 | /* Rather than walk the entire bitmap of expressions, and see |
985 | whether any of them has the value we are looking for, we look | |
986 | at the reverse mapping, which tells us the set of expressions | |
987 | that have a given value (IE value->expressions with that | |
988 | value) and see if any of those expressions are in our set. | |
989 | The number of expressions per value is usually significantly | |
990 | less than the number of expressions in the set. In fact, for | |
991 | large testcases, doing it this way is roughly 5-10x faster | |
992 | than walking the bitmap. | |
993 | If this is somehow a significant lose for some cases, we can | |
994 | choose which set to walk based on which set is smaller. */ | |
995 | value_set_t exprset; | |
996 | value_set_node_t node; | |
997 | exprset = VALUE_HANDLE_EXPR_SET (val); | |
998 | for (node = exprset->head; node; node = node->next) | |
999 | { | |
1000 | if (TREE_CODE (node->expr) == SSA_NAME) | |
1001 | { | |
1002 | if (bitmap_bit_p (set->expressions, | |
1003 | SSA_NAME_VERSION (node->expr))) | |
1004 | return node->expr; | |
1005 | } | |
1006 | } | |
bdee7684 DB |
1007 | } |
1008 | return NULL; | |
1009 | } | |
1010 | ||
1011 | ||
ff2ad0f7 | 1012 | /* Find the leader for a value (i.e., the name representing that |
7e6eb623 DB |
1013 | value) in a given set, and return it. Return NULL if no leader is |
1014 | found. */ | |
6de9cd9a | 1015 | |
7e6eb623 DB |
1016 | static tree |
1017 | find_leader (value_set_t set, tree val) | |
6de9cd9a | 1018 | { |
7e6eb623 | 1019 | value_set_node_t node; |
6de9cd9a | 1020 | |
7e6eb623 DB |
1021 | if (val == NULL) |
1022 | return NULL; | |
ff2ad0f7 | 1023 | |
bddeccfe DN |
1024 | /* Constants represent themselves. */ |
1025 | if (is_gimple_min_invariant (val)) | |
56db793a | 1026 | return val; |
ff2ad0f7 | 1027 | |
7e6eb623 DB |
1028 | if (set->length == 0) |
1029 | return NULL; | |
6de9cd9a | 1030 | |
7e6eb623 | 1031 | if (value_exists_in_set_bitmap (set, val)) |
6de9cd9a | 1032 | { |
7e6eb623 DB |
1033 | for (node = set->head; |
1034 | node; | |
1035 | node = node->next) | |
6de9cd9a | 1036 | { |
7e6eb623 DB |
1037 | if (get_value_handle (node->expr) == val) |
1038 | return node->expr; | |
6de9cd9a DN |
1039 | } |
1040 | } | |
ff2ad0f7 | 1041 | |
7e6eb623 | 1042 | return NULL; |
6de9cd9a DN |
1043 | } |
1044 | ||
7e6eb623 DB |
1045 | /* Determine if the expression EXPR is valid in SET. This means that |
1046 | we have a leader for each part of the expression (if it consists of | |
1047 | values), or the expression is an SSA_NAME. | |
6de9cd9a | 1048 | |
7e6eb623 DB |
1049 | NB: We never should run into a case where we have SSA_NAME + |
1050 | SSA_NAME or SSA_NAME + value. The sets valid_in_set is called on, | |
1051 | the ANTIC sets, will only ever have SSA_NAME's or binary value | |
1052 | expression (IE VALUE1 + VALUE2) */ | |
6de9cd9a DN |
1053 | |
1054 | static bool | |
7e6eb623 | 1055 | valid_in_set (value_set_t set, tree expr) |
6de9cd9a | 1056 | { |
7e6eb623 DB |
1057 | switch (TREE_CODE_CLASS (TREE_CODE (expr))) |
1058 | { | |
6615c446 | 1059 | case tcc_binary: |
6de9cd9a | 1060 | { |
7e6eb623 DB |
1061 | tree op1 = TREE_OPERAND (expr, 0); |
1062 | tree op2 = TREE_OPERAND (expr, 1); | |
1063 | return set_contains_value (set, op1) && set_contains_value (set, op2); | |
6de9cd9a | 1064 | } |
6615c446 JO |
1065 | |
1066 | case tcc_unary: | |
7e6eb623 DB |
1067 | { |
1068 | tree op1 = TREE_OPERAND (expr, 0); | |
1069 | return set_contains_value (set, op1); | |
1070 | } | |
6615c446 JO |
1071 | |
1072 | case tcc_reference: | |
1073 | /* XXX: Until PRE of loads works, no reference nodes are ANTIC. */ | |
1074 | return false; | |
1075 | ||
1076 | case tcc_exceptional: | |
1077 | gcc_assert (TREE_CODE (expr) == SSA_NAME); | |
1078 | return true; | |
1079 | ||
1080 | default: | |
1081 | /* No other cases should be encountered. */ | |
1082 | gcc_unreachable (); | |
1083 | } | |
6de9cd9a DN |
1084 | } |
1085 | ||
ca072a31 DB |
1086 | /* Clean the set of expressions that are no longer valid in SET. This |
1087 | means expressions that are made up of values we have no leaders for | |
1088 | in SET. */ | |
6de9cd9a DN |
1089 | |
1090 | static void | |
7e6eb623 | 1091 | clean (value_set_t set) |
6de9cd9a | 1092 | { |
7e6eb623 DB |
1093 | value_set_node_t node; |
1094 | value_set_node_t next; | |
1095 | node = set->head; | |
1096 | while (node) | |
6de9cd9a | 1097 | { |
7e6eb623 DB |
1098 | next = node->next; |
1099 | if (!valid_in_set (set, node->expr)) | |
1100 | set_remove (set, node->expr); | |
1101 | node = next; | |
6de9cd9a DN |
1102 | } |
1103 | } | |
1104 | ||
d6fd4b8d DB |
1105 | DEF_VEC_MALLOC_P (basic_block); |
1106 | ||
7e6eb623 | 1107 | /* Compute the ANTIC set for BLOCK. |
6de9cd9a | 1108 | |
7e6eb623 DB |
1109 | ANTIC_OUT[BLOCK] = intersection of ANTIC_IN[b] for all succ(BLOCK), if |
1110 | succs(BLOCK) > 1 | |
1111 | ANTIC_OUT[BLOCK] = phi_translate (ANTIC_IN[succ(BLOCK)]) if | |
1112 | succs(BLOCK) == 1 | |
6de9cd9a | 1113 | |
7e6eb623 DB |
1114 | ANTIC_IN[BLOCK] = clean(ANTIC_OUT[BLOCK] U EXP_GEN[BLOCK] - |
1115 | TMP_GEN[BLOCK]) | |
6de9cd9a | 1116 | |
7e6eb623 | 1117 | Iterate until fixpointed. |
6de9cd9a | 1118 | |
7e6eb623 DB |
1119 | XXX: It would be nice to either write a set_clear, and use it for |
1120 | antic_out, or to mark the antic_out set as deleted at the end | |
1121 | of this routine, so that the pool can hand the same memory back out | |
1122 | again for the next antic_out. */ | |
6de9cd9a | 1123 | |
7e6eb623 DB |
1124 | |
1125 | static bool | |
1126 | compute_antic_aux (basic_block block) | |
6de9cd9a | 1127 | { |
7e6eb623 DB |
1128 | basic_block son; |
1129 | edge e; | |
1130 | bool changed = false; | |
1131 | value_set_t S, old, ANTIC_OUT; | |
1132 | value_set_node_t node; | |
1133 | ||
1134 | ANTIC_OUT = S = NULL; | |
1135 | /* If any edges from predecessors are abnormal, antic_in is empty, so | |
1136 | punt. Remember that the block has an incoming abnormal edge by | |
1137 | setting the BB_VISITED flag. */ | |
1138 | if (! (block->flags & BB_VISITED)) | |
6de9cd9a | 1139 | { |
628f6a4e BE |
1140 | edge_iterator ei; |
1141 | FOR_EACH_EDGE (e, ei, block->preds) | |
1142 | if (e->flags & EDGE_ABNORMAL) | |
1143 | { | |
1144 | block->flags |= BB_VISITED; | |
1145 | break; | |
1146 | } | |
6de9cd9a | 1147 | } |
7e6eb623 | 1148 | if (block->flags & BB_VISITED) |
6de9cd9a | 1149 | { |
7e6eb623 DB |
1150 | S = NULL; |
1151 | goto visit_sons; | |
6de9cd9a | 1152 | } |
7e6eb623 | 1153 | |
6de9cd9a | 1154 | |
7e6eb623 DB |
1155 | old = set_new (false); |
1156 | set_copy (old, ANTIC_IN (block)); | |
1157 | ANTIC_OUT = set_new (true); | |
6de9cd9a | 1158 | |
7e6eb623 DB |
1159 | /* If the block has no successors, ANTIC_OUT is empty, because it is |
1160 | the exit block. */ | |
628f6a4e | 1161 | if (EDGE_COUNT (block->succs) == 0); |
6de9cd9a | 1162 | |
7e6eb623 DB |
1163 | /* If we have one successor, we could have some phi nodes to |
1164 | translate through. */ | |
628f6a4e | 1165 | else if (EDGE_COUNT (block->succs) == 1) |
6de9cd9a | 1166 | { |
628f6a4e BE |
1167 | phi_translate_set (ANTIC_OUT, ANTIC_IN(EDGE_SUCC (block, 0)->dest), |
1168 | block, EDGE_SUCC (block, 0)->dest); | |
6de9cd9a | 1169 | } |
7e6eb623 DB |
1170 | /* If we have multiple successors, we take the intersection of all of |
1171 | them. */ | |
1172 | else | |
6de9cd9a | 1173 | { |
d6fd4b8d | 1174 | VEC (basic_block) * worklist; |
7e6eb623 DB |
1175 | edge e; |
1176 | size_t i; | |
1177 | basic_block bprime, first; | |
628f6a4e | 1178 | edge_iterator ei; |
7e6eb623 | 1179 | |
d6fd4b8d | 1180 | worklist = VEC_alloc (basic_block, 2); |
628f6a4e BE |
1181 | FOR_EACH_EDGE (e, ei, block->succs) |
1182 | VEC_safe_push (basic_block, worklist, e->dest); | |
d6fd4b8d | 1183 | first = VEC_index (basic_block, worklist, 0); |
7e6eb623 | 1184 | set_copy (ANTIC_OUT, ANTIC_IN (first)); |
6de9cd9a | 1185 | |
d6fd4b8d | 1186 | for (i = 1; VEC_iterate (basic_block, worklist, i, bprime); i++) |
6de9cd9a | 1187 | { |
7e6eb623 DB |
1188 | node = ANTIC_OUT->head; |
1189 | while (node) | |
6de9cd9a | 1190 | { |
7e6eb623 DB |
1191 | tree val; |
1192 | value_set_node_t next = node->next; | |
1193 | val = get_value_handle (node->expr); | |
1194 | if (!set_contains_value (ANTIC_IN (bprime), val)) | |
1195 | set_remove (ANTIC_OUT, node->expr); | |
1196 | node = next; | |
6de9cd9a | 1197 | } |
6de9cd9a | 1198 | } |
d6fd4b8d | 1199 | VEC_free (basic_block, worklist); |
6de9cd9a | 1200 | } |
6de9cd9a | 1201 | |
ea4b7848 | 1202 | /* Generate ANTIC_OUT - TMP_GEN. */ |
6b416da1 | 1203 | S = bitmap_set_subtract_from_value_set (ANTIC_OUT, TMP_GEN (block), false); |
6de9cd9a | 1204 | |
7e6eb623 | 1205 | /* Start ANTIC_IN with EXP_GEN - TMP_GEN */ |
6b416da1 DB |
1206 | ANTIC_IN (block) = bitmap_set_subtract_from_value_set (EXP_GEN (block), |
1207 | TMP_GEN (block), | |
1208 | true); | |
6de9cd9a | 1209 | |
7e6eb623 DB |
1210 | /* Then union in the ANTIC_OUT - TMP_GEN values, to get ANTIC_OUT U |
1211 | EXP_GEN - TMP_GEN */ | |
1212 | for (node = S->head; | |
1213 | node; | |
1214 | node = node->next) | |
6de9cd9a | 1215 | { |
7e6eb623 | 1216 | value_insert_into_set (ANTIC_IN (block), node->expr); |
6de9cd9a | 1217 | } |
7e6eb623 | 1218 | clean (ANTIC_IN (block)); |
ca072a31 | 1219 | |
6de9cd9a | 1220 | |
7e6eb623 DB |
1221 | if (!set_equal (old, ANTIC_IN (block))) |
1222 | changed = true; | |
6de9cd9a | 1223 | |
7e6eb623 DB |
1224 | visit_sons: |
1225 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
1226 | { | |
1227 | if (ANTIC_OUT) | |
1228 | print_value_set (dump_file, ANTIC_OUT, "ANTIC_OUT", block->index); | |
1229 | print_value_set (dump_file, ANTIC_IN (block), "ANTIC_IN", block->index); | |
1230 | if (S) | |
1231 | print_value_set (dump_file, S, "S", block->index); | |
6de9cd9a | 1232 | |
7e6eb623 | 1233 | } |
6de9cd9a | 1234 | |
7e6eb623 DB |
1235 | for (son = first_dom_son (CDI_POST_DOMINATORS, block); |
1236 | son; | |
1237 | son = next_dom_son (CDI_POST_DOMINATORS, son)) | |
6de9cd9a | 1238 | { |
7e6eb623 | 1239 | changed |= compute_antic_aux (son); |
6de9cd9a | 1240 | } |
7e6eb623 | 1241 | return changed; |
6de9cd9a DN |
1242 | } |
1243 | ||
7e6eb623 | 1244 | /* Compute ANTIC sets. */ |
6de9cd9a DN |
1245 | |
1246 | static void | |
7e6eb623 | 1247 | compute_antic (void) |
6de9cd9a | 1248 | { |
7e6eb623 DB |
1249 | bool changed = true; |
1250 | basic_block bb; | |
1251 | int num_iterations = 0; | |
1252 | FOR_ALL_BB (bb) | |
1253 | { | |
1254 | ANTIC_IN (bb) = set_new (true); | |
1e128c5f | 1255 | gcc_assert (!(bb->flags & BB_VISITED)); |
7e6eb623 DB |
1256 | } |
1257 | ||
1258 | while (changed) | |
1259 | { | |
1260 | num_iterations++; | |
1261 | changed = false; | |
1262 | changed = compute_antic_aux (EXIT_BLOCK_PTR); | |
1263 | } | |
2e24fa83 ZD |
1264 | FOR_ALL_BB (bb) |
1265 | { | |
1266 | bb->flags &= ~BB_VISITED; | |
1267 | } | |
7e6eb623 DB |
1268 | if (num_iterations > 2 && dump_file && (dump_flags & TDF_STATS)) |
1269 | fprintf (dump_file, "compute_antic required %d iterations\n", num_iterations); | |
6de9cd9a DN |
1270 | } |
1271 | ||
56db793a DB |
1272 | |
1273 | /* Find a leader for an expression, or generate one using | |
1274 | create_expression_by_pieces if it's ANTIC but | |
1275 | complex. | |
1276 | BLOCK is the basic_block we are looking for leaders in. | |
1277 | EXPR is the expression to find a leader or generate for. | |
1278 | STMTS is the statement list to put the inserted expressions on. | |
1279 | Returns the SSA_NAME of the LHS of the generated expression or the | |
1280 | leader. */ | |
1281 | ||
1282 | static tree | |
1283 | find_or_generate_expression (basic_block block, tree expr, tree stmts) | |
1284 | { | |
1285 | tree genop; | |
bdee7684 | 1286 | genop = bitmap_find_leader (AVAIL_OUT (block), expr); |
56db793a DB |
1287 | /* Depending on the order we process DOM branches in, the value |
1288 | may not have propagated to all the dom children yet during | |
1289 | this iteration. In this case, the value will always be in | |
61ada8ae | 1290 | the NEW_SETS for us already, having been propagated from our |
56db793a DB |
1291 | dominator. */ |
1292 | if (genop == NULL) | |
6b416da1 | 1293 | genop = bitmap_find_leader (NEW_SETS (block), expr); |
56db793a DB |
1294 | /* If it's still NULL, see if it is a complex expression, and if |
1295 | so, generate it recursively, otherwise, abort, because it's | |
1296 | not really . */ | |
1297 | if (genop == NULL) | |
1298 | { | |
33c94679 | 1299 | genop = VALUE_HANDLE_EXPR_SET (expr)->head->expr; |
6615c446 JO |
1300 | gcc_assert (UNARY_CLASS_P (genop) |
1301 | || BINARY_CLASS_P (genop) | |
1302 | || REFERENCE_CLASS_P (genop)); | |
56db793a DB |
1303 | genop = create_expression_by_pieces (block, genop, stmts); |
1304 | } | |
1305 | return genop; | |
1306 | } | |
1307 | ||
1308 | ||
1309 | /* Create an expression in pieces, so that we can handle very complex | |
1310 | expressions that may be ANTIC, but not necessary GIMPLE. | |
1311 | BLOCK is the basic block the expression will be inserted into, | |
1312 | EXPR is the expression to insert (in value form) | |
1313 | STMTS is a statement list to append the necessary insertions into. | |
1314 | ||
1315 | This function will abort if we hit some value that shouldn't be | |
1316 | ANTIC but is (IE there is no leader for it, or its components). | |
1317 | This function may also generate expressions that are themselves | |
1318 | partially or fully redundant. Those that are will be either made | |
1319 | fully redundant during the next iteration of insert (for partially | |
1320 | redundant ones), or eliminated by eliminate (for fully redundant | |
1321 | ones). */ | |
1322 | ||
1323 | static tree | |
1324 | create_expression_by_pieces (basic_block block, tree expr, tree stmts) | |
1325 | { | |
1326 | tree name = NULL_TREE; | |
1327 | tree newexpr = NULL_TREE; | |
1328 | tree v; | |
1329 | ||
1330 | switch (TREE_CODE_CLASS (TREE_CODE (expr))) | |
1331 | { | |
6615c446 | 1332 | case tcc_binary: |
56db793a DB |
1333 | { |
1334 | tree_stmt_iterator tsi; | |
1335 | tree genop1, genop2; | |
1336 | tree temp; | |
1337 | tree op1 = TREE_OPERAND (expr, 0); | |
1338 | tree op2 = TREE_OPERAND (expr, 1); | |
1339 | genop1 = find_or_generate_expression (block, op1, stmts); | |
1340 | genop2 = find_or_generate_expression (block, op2, stmts); | |
1341 | temp = create_tmp_var (TREE_TYPE (expr), "pretmp"); | |
1342 | add_referenced_tmp_var (temp); | |
1343 | newexpr = build (TREE_CODE (expr), TREE_TYPE (expr), | |
1344 | genop1, genop2); | |
1345 | newexpr = build (MODIFY_EXPR, TREE_TYPE (expr), | |
1346 | temp, newexpr); | |
1347 | name = make_ssa_name (temp, newexpr); | |
1348 | TREE_OPERAND (newexpr, 0) = name; | |
1349 | tsi = tsi_last (stmts); | |
1350 | tsi_link_after (&tsi, newexpr, TSI_CONTINUE_LINKING); | |
1351 | pre_stats.insertions++; | |
1352 | break; | |
1353 | } | |
6615c446 | 1354 | case tcc_unary: |
56db793a DB |
1355 | { |
1356 | tree_stmt_iterator tsi; | |
1357 | tree genop1; | |
1358 | tree temp; | |
1359 | tree op1 = TREE_OPERAND (expr, 0); | |
1360 | genop1 = find_or_generate_expression (block, op1, stmts); | |
1361 | temp = create_tmp_var (TREE_TYPE (expr), "pretmp"); | |
1362 | add_referenced_tmp_var (temp); | |
1363 | newexpr = build (TREE_CODE (expr), TREE_TYPE (expr), | |
1364 | genop1); | |
1365 | newexpr = build (MODIFY_EXPR, TREE_TYPE (expr), | |
1366 | temp, newexpr); | |
1367 | name = make_ssa_name (temp, newexpr); | |
1368 | TREE_OPERAND (newexpr, 0) = name; | |
1369 | tsi = tsi_last (stmts); | |
1370 | tsi_link_after (&tsi, newexpr, TSI_CONTINUE_LINKING); | |
1371 | pre_stats.insertions++; | |
1372 | ||
1373 | break; | |
1374 | } | |
1375 | default: | |
1e128c5f | 1376 | gcc_unreachable (); |
56db793a DB |
1377 | |
1378 | } | |
1379 | v = get_value_handle (expr); | |
ff2ad0f7 | 1380 | vn_add (name, v, NULL); |
6b416da1 | 1381 | bitmap_insert_into_set (NEW_SETS (block), name); |
bdee7684 | 1382 | bitmap_value_insert_into_set (AVAIL_OUT (block), name); |
56db793a DB |
1383 | if (dump_file && (dump_flags & TDF_DETAILS)) |
1384 | { | |
1385 | fprintf (dump_file, "Inserted "); | |
1386 | print_generic_expr (dump_file, newexpr, 0); | |
1387 | fprintf (dump_file, " in predecessor %d\n", block->index); | |
1388 | } | |
1389 | return name; | |
1390 | } | |
1391 | ||
7e6eb623 DB |
1392 | /* Perform insertion of partially redundant values. |
1393 | For BLOCK, do the following: | |
1394 | 1. Propagate the NEW_SETS of the dominator into the current block. | |
1395 | If the block has multiple predecessors, | |
1396 | 2a. Iterate over the ANTIC expressions for the block to see if | |
1397 | any of them are partially redundant. | |
1398 | 2b. If so, insert them into the necessary predecessors to make | |
1399 | the expression fully redundant. | |
1400 | 2c. Insert a new PHI merging the values of the predecessors. | |
1401 | 2d. Insert the new PHI, and the new expressions, into the | |
1402 | NEW_SETS set. | |
1403 | 3. Recursively call ourselves on the dominator children of BLOCK. | |
6de9cd9a | 1404 | |
7e6eb623 DB |
1405 | */ |
1406 | static bool | |
1407 | insert_aux (basic_block block) | |
6de9cd9a | 1408 | { |
7e6eb623 DB |
1409 | basic_block son; |
1410 | bool new_stuff = false; | |
6de9cd9a | 1411 | |
7e6eb623 | 1412 | if (block) |
6de9cd9a | 1413 | { |
7e6eb623 DB |
1414 | basic_block dom; |
1415 | dom = get_immediate_dominator (CDI_DOMINATORS, block); | |
1416 | if (dom) | |
a32b97a2 | 1417 | { |
3cd8c58a | 1418 | unsigned i; |
87c476a2 ZD |
1419 | bitmap_iterator bi; |
1420 | ||
6b416da1 | 1421 | bitmap_set_t newset = NEW_SETS (dom); |
87c476a2 ZD |
1422 | EXECUTE_IF_SET_IN_BITMAP (newset->expressions, 0, i, bi) |
1423 | { | |
1424 | bitmap_insert_into_set (NEW_SETS (block), ssa_name (i)); | |
1425 | bitmap_value_replace_in_set (AVAIL_OUT (block), ssa_name (i)); | |
1426 | } | |
628f6a4e | 1427 | if (EDGE_COUNT (block->preds) > 1) |
6de9cd9a | 1428 | { |
7e6eb623 DB |
1429 | value_set_node_t node; |
1430 | for (node = ANTIC_IN (block)->head; | |
1431 | node; | |
1432 | node = node->next) | |
6de9cd9a | 1433 | { |
6615c446 JO |
1434 | if (BINARY_CLASS_P (node->expr) |
1435 | || UNARY_CLASS_P (node->expr)) | |
6de9cd9a | 1436 | { |
7e6eb623 DB |
1437 | tree *avail; |
1438 | tree val; | |
1439 | bool by_some = false; | |
ca072a31 | 1440 | bool cant_insert = false; |
7e6eb623 DB |
1441 | bool all_same = true; |
1442 | tree first_s = NULL; | |
1443 | edge pred; | |
1444 | basic_block bprime; | |
1445 | tree eprime; | |
628f6a4e | 1446 | edge_iterator ei; |
ce25943a | 1447 | |
7e6eb623 | 1448 | val = get_value_handle (node->expr); |
6b416da1 | 1449 | if (bitmap_set_contains_value (PHI_GEN (block), val)) |
7e6eb623 | 1450 | continue; |
bdee7684 | 1451 | if (bitmap_set_contains_value (AVAIL_OUT (dom), val)) |
7e6eb623 DB |
1452 | { |
1453 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
1454 | fprintf (dump_file, "Found fully redundant value\n"); | |
1455 | continue; | |
1456 | } | |
628f6a4e | 1457 | |
ce25943a | 1458 | avail = xcalloc (last_basic_block, sizeof (tree)); |
628f6a4e | 1459 | FOR_EACH_EDGE (pred, ei, block->preds) |
7e6eb623 DB |
1460 | { |
1461 | tree vprime; | |
1462 | tree edoubleprime; | |
3f7d210d DB |
1463 | |
1464 | /* This can happen in the very weird case | |
1465 | that our fake infinite loop edges have caused a | |
1466 | critical edge to appear. */ | |
1467 | if (EDGE_CRITICAL_P (pred)) | |
1468 | { | |
1469 | cant_insert = true; | |
1470 | break; | |
1471 | } | |
7e6eb623 DB |
1472 | bprime = pred->src; |
1473 | eprime = phi_translate (node->expr, | |
1474 | ANTIC_IN (block), | |
1475 | bprime, block); | |
ce25943a DB |
1476 | |
1477 | /* eprime will generally only be NULL if the | |
1478 | value of the expression, translated | |
1479 | through the PHI for this predecessor, is | |
1480 | undefined. If that is the case, we can't | |
1481 | make the expression fully redundant, | |
1482 | because its value is undefined along a | |
1483 | predecessor path. We can thus break out | |
1484 | early because it doesn't matter what the | |
1485 | rest of the results are. */ | |
7e6eb623 | 1486 | if (eprime == NULL) |
ce25943a DB |
1487 | { |
1488 | cant_insert = true; | |
1489 | break; | |
1490 | } | |
7e6eb623 DB |
1491 | |
1492 | vprime = get_value_handle (eprime); | |
1e128c5f | 1493 | gcc_assert (vprime); |
bdee7684 DB |
1494 | edoubleprime = bitmap_find_leader (AVAIL_OUT (bprime), |
1495 | vprime); | |
7e6eb623 DB |
1496 | if (edoubleprime == NULL) |
1497 | { | |
1498 | avail[bprime->index] = eprime; | |
1499 | all_same = false; | |
1500 | } | |
1501 | else | |
1502 | { | |
1503 | avail[bprime->index] = edoubleprime; | |
ca072a31 | 1504 | by_some = true; |
7e6eb623 DB |
1505 | if (first_s == NULL) |
1506 | first_s = edoubleprime; | |
1507 | else if (first_s != edoubleprime) | |
1508 | all_same = false; | |
1e128c5f GB |
1509 | gcc_assert (first_s == edoubleprime |
1510 | || !operand_equal_p | |
1511 | (first_s, edoubleprime, 0)); | |
7e6eb623 DB |
1512 | } |
1513 | } | |
ca072a31 DB |
1514 | /* If we can insert it, it's not the same value |
1515 | already existing along every predecessor, and | |
1516 | it's defined by some predecessor, it is | |
1517 | partially redundant. */ | |
ce25943a | 1518 | if (!cant_insert && !all_same && by_some) |
7e6eb623 | 1519 | { |
628f6a4e | 1520 | tree type = TREE_TYPE (avail[EDGE_PRED (block, 0)->src->index]); |
ca072a31 | 1521 | tree temp; |
7e6eb623 DB |
1522 | if (dump_file && (dump_flags & TDF_DETAILS)) |
1523 | { | |
1524 | fprintf (dump_file, "Found partial redundancy for expression "); | |
1525 | print_generic_expr (dump_file, node->expr, 0); | |
1526 | fprintf (dump_file, "\n"); | |
1527 | } | |
1528 | ||
8c27b7d4 | 1529 | /* Make the necessary insertions. */ |
628f6a4e | 1530 | FOR_EACH_EDGE (pred, ei, block->preds) |
7e6eb623 | 1531 | { |
56db793a DB |
1532 | tree stmts = alloc_stmt_list (); |
1533 | tree builtexpr; | |
7e6eb623 DB |
1534 | bprime = pred->src; |
1535 | eprime = avail[bprime->index]; | |
6615c446 JO |
1536 | if (BINARY_CLASS_P (eprime) |
1537 | || UNARY_CLASS_P (eprime)) | |
7e6eb623 | 1538 | { |
56db793a DB |
1539 | builtexpr = create_expression_by_pieces (bprime, |
1540 | eprime, | |
1541 | stmts); | |
1542 | bsi_insert_on_edge (pred, stmts); | |
56db793a DB |
1543 | avail[bprime->index] = builtexpr; |
1544 | } | |
628f6a4e | 1545 | } |
7e6eb623 DB |
1546 | /* Now build a phi for the new variable. */ |
1547 | temp = create_tmp_var (type, "prephitmp"); | |
1548 | add_referenced_tmp_var (temp); | |
1549 | temp = create_phi_node (temp, block); | |
ff2ad0f7 | 1550 | vn_add (PHI_RESULT (temp), val, NULL); |
7e6eb623 DB |
1551 | |
1552 | #if 0 | |
1553 | if (!set_contains_value (AVAIL_OUT (block), val)) | |
1554 | insert_into_set (AVAIL_OUT (block), | |
1555 | PHI_RESULT (temp)); | |
1556 | else | |
1557 | #endif | |
bdee7684 DB |
1558 | bitmap_value_replace_in_set (AVAIL_OUT (block), |
1559 | PHI_RESULT (temp)); | |
628f6a4e | 1560 | FOR_EACH_EDGE (pred, ei, block->preds) |
7e6eb623 DB |
1561 | { |
1562 | add_phi_arg (&temp, avail[pred->src->index], | |
1563 | pred); | |
1564 | } | |
1565 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
1566 | { | |
1567 | fprintf (dump_file, "Created phi "); | |
1568 | print_generic_expr (dump_file, temp, 0); | |
1569 | fprintf (dump_file, " in block %d\n", block->index); | |
1570 | } | |
1571 | pre_stats.phis++; | |
1572 | new_stuff = true; | |
6b416da1 DB |
1573 | bitmap_insert_into_set (NEW_SETS (block), |
1574 | PHI_RESULT (temp)); | |
1575 | bitmap_insert_into_set (PHI_GEN (block), | |
1576 | PHI_RESULT (temp)); | |
7e6eb623 DB |
1577 | } |
1578 | ||
1579 | free (avail); | |
6de9cd9a DN |
1580 | } |
1581 | } | |
1582 | } | |
1583 | } | |
1584 | } | |
7e6eb623 DB |
1585 | for (son = first_dom_son (CDI_DOMINATORS, block); |
1586 | son; | |
1587 | son = next_dom_son (CDI_DOMINATORS, son)) | |
1588 | { | |
1589 | new_stuff |= insert_aux (son); | |
1590 | } | |
1591 | ||
1592 | return new_stuff; | |
6de9cd9a DN |
1593 | } |
1594 | ||
7e6eb623 | 1595 | /* Perform insertion of partially redundant values. */ |
6de9cd9a | 1596 | |
7e6eb623 DB |
1597 | static void |
1598 | insert (void) | |
6de9cd9a | 1599 | { |
7e6eb623 | 1600 | bool new_stuff = true; |
6de9cd9a | 1601 | basic_block bb; |
7e6eb623 | 1602 | int num_iterations = 0; |
bdee7684 | 1603 | |
7e6eb623 | 1604 | FOR_ALL_BB (bb) |
6b416da1 | 1605 | NEW_SETS (bb) = bitmap_set_new (); |
6de9cd9a | 1606 | |
7e6eb623 | 1607 | while (new_stuff) |
6de9cd9a | 1608 | { |
7e6eb623 DB |
1609 | num_iterations++; |
1610 | new_stuff = false; | |
1611 | new_stuff = insert_aux (ENTRY_BLOCK_PTR); | |
6de9cd9a | 1612 | } |
7e6eb623 DB |
1613 | if (num_iterations > 2 && dump_file && (dump_flags & TDF_STATS)) |
1614 | fprintf (dump_file, "insert required %d iterations\n", num_iterations); | |
1615 | } | |
6de9cd9a | 1616 | |
33c94679 | 1617 | |
ff2ad0f7 DN |
1618 | /* Return true if VAR is an SSA variable with no defining statement in |
1619 | this procedure, *AND* isn't a live-on-entry parameter. */ | |
33c94679 | 1620 | |
7e6eb623 DB |
1621 | static bool |
1622 | is_undefined_value (tree expr) | |
ff2ad0f7 DN |
1623 | { |
1624 | return (TREE_CODE (expr) == SSA_NAME | |
1625 | && IS_EMPTY_STMT (SSA_NAME_DEF_STMT (expr)) | |
1626 | /* PARM_DECLs and hard registers are always defined. */ | |
e670d9e4 | 1627 | && TREE_CODE (SSA_NAME_VAR (expr)) != PARM_DECL); |
ff2ad0f7 DN |
1628 | } |
1629 | ||
1630 | ||
1631 | /* Given an SSA variable VAR and an expression EXPR, compute the value | |
1632 | number for EXPR and create a value handle (VAL) for it. If VAR and | |
1633 | EXPR are not the same, associate VAL with VAR. Finally, add VAR to | |
1634 | S1 and its value handle to S2. | |
1635 | ||
1636 | VUSES represent the virtual use operands associated with EXPR (if | |
1637 | any). They are used when computing the hash value for EXPR. */ | |
1638 | ||
1639 | static inline void | |
6b416da1 | 1640 | add_to_sets (tree var, tree expr, vuse_optype vuses, bitmap_set_t s1, |
bdee7684 | 1641 | bitmap_set_t s2) |
ff2ad0f7 DN |
1642 | { |
1643 | tree val = vn_lookup_or_add (expr, vuses); | |
1644 | ||
1645 | /* VAR and EXPR may be the same when processing statements for which | |
1646 | we are not computing value numbers (e.g., non-assignments, or | |
1647 | statements that make aliased stores). In those cases, we are | |
1648 | only interested in making VAR available as its own value. */ | |
1649 | if (var != expr) | |
3d3fa3a1 | 1650 | vn_add (var, val, NULL); |
ff2ad0f7 | 1651 | |
6b416da1 | 1652 | bitmap_insert_into_set (s1, var); |
bdee7684 | 1653 | bitmap_value_insert_into_set (s2, var); |
ff2ad0f7 DN |
1654 | } |
1655 | ||
1656 | ||
1657 | /* Given a unary or binary expression EXPR, create and return a new | |
f6fe65dc | 1658 | expression with the same structure as EXPR but with its operands |
ff2ad0f7 DN |
1659 | replaced with the value handles of each of the operands of EXPR. |
1660 | Insert EXPR's operands into the EXP_GEN set for BLOCK. | |
1661 | ||
1662 | VUSES represent the virtual use operands associated with EXPR (if | |
1663 | any). They are used when computing the hash value for EXPR. */ | |
1664 | ||
1665 | static inline tree | |
1666 | create_value_expr_from (tree expr, basic_block block, vuse_optype vuses) | |
1667 | { | |
1668 | int i; | |
1669 | enum tree_code code = TREE_CODE (expr); | |
1670 | tree vexpr; | |
1671 | ||
6615c446 JO |
1672 | gcc_assert (TREE_CODE_CLASS (code) == tcc_unary |
1673 | || TREE_CODE_CLASS (code) == tcc_binary | |
1674 | || TREE_CODE_CLASS (code) == tcc_reference); | |
33c94679 | 1675 | |
6615c446 | 1676 | if (TREE_CODE_CLASS (code) == tcc_unary) |
ff2ad0f7 | 1677 | vexpr = pool_alloc (unary_node_pool); |
6615c446 | 1678 | else if (TREE_CODE_CLASS (code) == tcc_reference) |
3d3fa3a1 | 1679 | vexpr = pool_alloc (reference_node_pool); |
ff2ad0f7 DN |
1680 | else |
1681 | vexpr = pool_alloc (binary_node_pool); | |
1682 | ||
1683 | memcpy (vexpr, expr, tree_size (expr)); | |
1684 | ||
1685 | for (i = 0; i < TREE_CODE_LENGTH (code); i++) | |
6de9cd9a | 1686 | { |
ff2ad0f7 | 1687 | tree op = TREE_OPERAND (expr, i); |
bdee7684 DB |
1688 | if (op != NULL) |
1689 | { | |
1690 | tree val = vn_lookup_or_add (op, vuses); | |
1691 | if (!is_undefined_value (op)) | |
1692 | value_insert_into_set (EXP_GEN (block), op); | |
af75a7ea DB |
1693 | if (TREE_CODE (val) == VALUE_HANDLE) |
1694 | TREE_TYPE (val) = TREE_TYPE (TREE_OPERAND (vexpr, i)); | |
bdee7684 DB |
1695 | TREE_OPERAND (vexpr, i) = val; |
1696 | } | |
6de9cd9a | 1697 | } |
33c94679 | 1698 | |
ff2ad0f7 | 1699 | return vexpr; |
6de9cd9a DN |
1700 | } |
1701 | ||
ff2ad0f7 | 1702 | |
7e6eb623 DB |
1703 | /* Compute the AVAIL set for BLOCK. |
1704 | This function performs value numbering of the statements in BLOCK. | |
1705 | The AVAIL sets are built from information we glean while doing this | |
ff2ad0f7 | 1706 | value numbering, since the AVAIL sets contain only one entry per |
7e6eb623 | 1707 | value. |
7e6eb623 DB |
1708 | |
1709 | AVAIL_IN[BLOCK] = AVAIL_OUT[dom(BLOCK)]. | |
ff2ad0f7 | 1710 | AVAIL_OUT[BLOCK] = AVAIL_IN[BLOCK] U PHI_GEN[BLOCK] U TMP_GEN[BLOCK]. */ |
6de9cd9a | 1711 | |
7e6eb623 DB |
1712 | static void |
1713 | compute_avail (basic_block block) | |
6de9cd9a | 1714 | { |
6de9cd9a | 1715 | basic_block son; |
6de9cd9a | 1716 | |
7e6eb623 DB |
1717 | /* For arguments with default definitions, we pretend they are |
1718 | defined in the entry block. */ | |
1719 | if (block == ENTRY_BLOCK_PTR) | |
1720 | { | |
1721 | tree param; | |
1722 | for (param = DECL_ARGUMENTS (current_function_decl); | |
1723 | param; | |
1724 | param = TREE_CHAIN (param)) | |
1725 | { | |
1726 | if (default_def (param) != NULL) | |
1727 | { | |
1728 | tree val; | |
1729 | tree def = default_def (param); | |
ff2ad0f7 | 1730 | val = vn_lookup_or_add (def, NULL); |
6b416da1 | 1731 | bitmap_insert_into_set (TMP_GEN (block), def); |
bdee7684 | 1732 | bitmap_value_insert_into_set (AVAIL_OUT (block), def); |
7e6eb623 DB |
1733 | } |
1734 | } | |
1735 | } | |
1736 | else if (block) | |
6de9cd9a | 1737 | { |
7e6eb623 DB |
1738 | block_stmt_iterator bsi; |
1739 | tree stmt, phi; | |
1740 | basic_block dom; | |
1741 | ||
ff2ad0f7 DN |
1742 | /* Initially, the set of available values in BLOCK is that of |
1743 | its immediate dominator. */ | |
7e6eb623 DB |
1744 | dom = get_immediate_dominator (CDI_DOMINATORS, block); |
1745 | if (dom) | |
bdee7684 | 1746 | bitmap_set_copy (AVAIL_OUT (block), AVAIL_OUT (dom)); |
33c94679 | 1747 | |
ff2ad0f7 | 1748 | /* Generate values for PHI nodes. */ |
17192884 | 1749 | for (phi = phi_nodes (block); phi; phi = PHI_CHAIN (phi)) |
6b416da1 DB |
1750 | /* We have no need for virtual phis, as they don't represent |
1751 | actual computations. */ | |
1752 | if (is_gimple_reg (PHI_RESULT (phi))) | |
1753 | add_to_sets (PHI_RESULT (phi), PHI_RESULT (phi), NULL, | |
1754 | PHI_GEN (block), AVAIL_OUT (block)); | |
7e6eb623 | 1755 | |
ff2ad0f7 DN |
1756 | /* Now compute value numbers and populate value sets with all |
1757 | the expressions computed in BLOCK. */ | |
7e6eb623 | 1758 | for (bsi = bsi_start (block); !bsi_end_p (bsi); bsi_next (&bsi)) |
6de9cd9a | 1759 | { |
ff2ad0f7 DN |
1760 | stmt_ann_t ann; |
1761 | size_t j; | |
1762 | ||
7e6eb623 | 1763 | stmt = bsi_stmt (bsi); |
ff2ad0f7 | 1764 | ann = stmt_ann (stmt); |
7e6eb623 | 1765 | get_stmt_operands (stmt); |
ff2ad0f7 DN |
1766 | |
1767 | /* We are only interested in assignments of the form | |
1768 | X_i = EXPR, where EXPR represents an "interesting" | |
1769 | computation, it has no volatile operands and X_i | |
1770 | doesn't flow through an abnormal edge. */ | |
1771 | if (TREE_CODE (stmt) == MODIFY_EXPR | |
1772 | && !ann->has_volatile_ops | |
1773 | && TREE_CODE (TREE_OPERAND (stmt, 0)) == SSA_NAME | |
1774 | && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (TREE_OPERAND (stmt, 0))) | |
7e6eb623 | 1775 | { |
ff2ad0f7 DN |
1776 | tree lhs = TREE_OPERAND (stmt, 0); |
1777 | tree rhs = TREE_OPERAND (stmt, 1); | |
1778 | vuse_optype vuses = STMT_VUSE_OPS (stmt); | |
1779 | ||
1780 | STRIP_USELESS_TYPE_CONVERSION (rhs); | |
3d3fa3a1 DB |
1781 | if (TREE_CODE (rhs) == SSA_NAME |
1782 | || is_gimple_min_invariant (rhs)) | |
1783 | { | |
1784 | /* Compute a value number for the RHS of the statement | |
1785 | and add its value to the AVAIL_OUT set for the block. | |
1786 | Add the LHS to TMP_GEN. */ | |
1787 | add_to_sets (lhs, rhs, vuses, TMP_GEN (block), | |
1788 | AVAIL_OUT (block)); | |
1789 | ||
1790 | if (TREE_CODE (rhs) == SSA_NAME | |
1791 | && !is_undefined_value (rhs)) | |
1792 | value_insert_into_set (EXP_GEN (block), rhs); | |
1793 | continue; | |
1794 | } | |
6615c446 | 1795 | else if (UNARY_CLASS_P (rhs) || BINARY_CLASS_P (rhs) |
3d3fa3a1 | 1796 | || TREE_CODE (rhs) == INDIRECT_REF) |
7e6eb623 | 1797 | { |
bdee7684 DB |
1798 | /* For binary, unary, and reference expressions, |
1799 | create a duplicate expression with the operands | |
1800 | replaced with the value handles of the original | |
1801 | RHS. */ | |
ff2ad0f7 DN |
1802 | tree newt = create_value_expr_from (rhs, block, vuses); |
1803 | add_to_sets (lhs, newt, vuses, TMP_GEN (block), | |
1804 | AVAIL_OUT (block)); | |
1805 | value_insert_into_set (EXP_GEN (block), newt); | |
1806 | continue; | |
7e6eb623 | 1807 | } |
7e6eb623 | 1808 | } |
56db793a | 1809 | |
ff2ad0f7 DN |
1810 | /* For any other statement that we don't recognize, simply |
1811 | make the names generated by the statement available in | |
1812 | AVAIL_OUT and TMP_GEN. */ | |
1813 | for (j = 0; j < NUM_DEFS (STMT_DEF_OPS (stmt)); j++) | |
6de9cd9a | 1814 | { |
ff2ad0f7 DN |
1815 | tree def = DEF_OP (STMT_DEF_OPS (stmt), j); |
1816 | add_to_sets (def, def, NULL, TMP_GEN (block), | |
1817 | AVAIL_OUT (block)); | |
7e6eb623 | 1818 | } |
ff2ad0f7 DN |
1819 | |
1820 | for (j = 0; j < NUM_USES (STMT_USE_OPS (stmt)); j++) | |
7e6eb623 | 1821 | { |
ff2ad0f7 DN |
1822 | tree use = USE_OP (STMT_USE_OPS (stmt), j); |
1823 | add_to_sets (use, use, NULL, TMP_GEN (block), | |
1824 | AVAIL_OUT (block)); | |
6de9cd9a DN |
1825 | } |
1826 | } | |
6de9cd9a | 1827 | } |
33c94679 | 1828 | |
ff2ad0f7 | 1829 | /* Compute available sets for the dominator children of BLOCK. */ |
6de9cd9a DN |
1830 | for (son = first_dom_son (CDI_DOMINATORS, block); |
1831 | son; | |
1832 | son = next_dom_son (CDI_DOMINATORS, son)) | |
7e6eb623 | 1833 | compute_avail (son); |
7e6eb623 DB |
1834 | } |
1835 | ||
33c94679 | 1836 | |
7e6eb623 DB |
1837 | /* Eliminate fully redundant computations. */ |
1838 | ||
1839 | static void | |
1840 | eliminate (void) | |
1841 | { | |
1842 | basic_block b; | |
1843 | ||
1844 | FOR_EACH_BB (b) | |
1845 | { | |
1846 | block_stmt_iterator i; | |
1847 | ||
1848 | for (i = bsi_start (b); !bsi_end_p (i); bsi_next (&i)) | |
1849 | { | |
1850 | tree stmt = bsi_stmt (i); | |
1851 | ||
ff2ad0f7 DN |
1852 | /* Lookup the RHS of the expression, see if we have an |
1853 | available computation for it. If so, replace the RHS with | |
7e6eb623 | 1854 | the available computation. */ |
ff2ad0f7 DN |
1855 | if (TREE_CODE (stmt) == MODIFY_EXPR |
1856 | && TREE_CODE (TREE_OPERAND (stmt, 0)) == SSA_NAME | |
1857 | && TREE_CODE (TREE_OPERAND (stmt ,1)) != SSA_NAME | |
1858 | && !is_gimple_min_invariant (TREE_OPERAND (stmt, 1)) | |
1859 | && !stmt_ann (stmt)->has_volatile_ops) | |
1860 | { | |
1861 | tree lhs = TREE_OPERAND (stmt, 0); | |
1862 | tree *rhs_p = &TREE_OPERAND (stmt, 1); | |
1863 | tree sprime; | |
ff2ad0f7 | 1864 | |
3d3fa3a1 DB |
1865 | sprime = bitmap_find_leader (AVAIL_OUT (b), |
1866 | vn_lookup (lhs, NULL)); | |
ff2ad0f7 DN |
1867 | if (sprime |
1868 | && sprime != lhs | |
1869 | && (TREE_CODE (*rhs_p) != SSA_NAME | |
1870 | || may_propagate_copy (*rhs_p, sprime))) | |
1871 | { | |
1e128c5f | 1872 | gcc_assert (sprime != *rhs_p); |
ff2ad0f7 | 1873 | |
7e6eb623 DB |
1874 | if (dump_file && (dump_flags & TDF_DETAILS)) |
1875 | { | |
1876 | fprintf (dump_file, "Replaced "); | |
ff2ad0f7 | 1877 | print_generic_expr (dump_file, *rhs_p, 0); |
7e6eb623 DB |
1878 | fprintf (dump_file, " with "); |
1879 | print_generic_expr (dump_file, sprime, 0); | |
1880 | fprintf (dump_file, " in "); | |
1881 | print_generic_stmt (dump_file, stmt, 0); | |
1882 | } | |
1883 | pre_stats.eliminations++; | |
ff2ad0f7 DN |
1884 | propagate_tree_value (rhs_p, sprime); |
1885 | modify_stmt (stmt); | |
53b4bf74 DN |
1886 | |
1887 | /* If we removed EH side effects from the statement, clean | |
1888 | its EH information. */ | |
1889 | if (maybe_clean_eh_stmt (stmt)) | |
1890 | { | |
1891 | bitmap_set_bit (need_eh_cleanup, | |
1892 | bb_for_stmt (stmt)->index); | |
1893 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
1894 | fprintf (dump_file, " Removed EH side effects.\n"); | |
1895 | } | |
ff2ad0f7 DN |
1896 | } |
1897 | } | |
7e6eb623 DB |
1898 | } |
1899 | } | |
6de9cd9a DN |
1900 | } |
1901 | ||
33c94679 | 1902 | |
ff2ad0f7 | 1903 | /* Initialize data structures used by PRE. */ |
6de9cd9a DN |
1904 | |
1905 | static void | |
ff2ad0f7 | 1906 | init_pre (void) |
6de9cd9a | 1907 | { |
7e6eb623 | 1908 | basic_block bb; |
ff2ad0f7 | 1909 | |
50265400 | 1910 | connect_infinite_loops_to_exit (); |
ff2ad0f7 | 1911 | vn_init (); |
7e6eb623 | 1912 | memset (&pre_stats, 0, sizeof (pre_stats)); |
53b4bf74 DN |
1913 | |
1914 | /* If block 0 has more than one predecessor, it means that its PHI | |
1915 | nodes will have arguments coming from block -1. This creates | |
1916 | problems for several places in PRE that keep local arrays indexed | |
1917 | by block number. To prevent this, we split the edge coming from | |
1918 | ENTRY_BLOCK_PTR (FIXME, if ENTRY_BLOCK_PTR had an index number | |
1919 | different than -1 we wouldn't have to hack this. tree-ssa-dce.c | |
1920 | needs a similar change). */ | |
628f6a4e BE |
1921 | if (EDGE_COUNT (EDGE_SUCC (ENTRY_BLOCK_PTR, 0)->dest->preds) > 1) |
1922 | if (!(EDGE_SUCC (ENTRY_BLOCK_PTR, 0)->flags & EDGE_ABNORMAL)) | |
1923 | split_edge (EDGE_SUCC (ENTRY_BLOCK_PTR, 0)); | |
53b4bf74 | 1924 | |
7e6eb623 | 1925 | FOR_ALL_BB (bb) |
ff2ad0f7 DN |
1926 | bb->aux = xcalloc (1, sizeof (struct bb_value_sets)); |
1927 | ||
c4817ba6 | 1928 | gcc_obstack_init (&grand_bitmap_obstack); |
7e6eb623 | 1929 | phi_translate_table = htab_create (511, expr_pred_trans_hash, |
ff2ad0f7 | 1930 | expr_pred_trans_eq, free); |
7e6eb623 DB |
1931 | value_set_pool = create_alloc_pool ("Value sets", |
1932 | sizeof (struct value_set), 30); | |
bdee7684 DB |
1933 | bitmap_set_pool = create_alloc_pool ("Bitmap sets", |
1934 | sizeof (struct bitmap_set), 30); | |
7e6eb623 | 1935 | value_set_node_pool = create_alloc_pool ("Value set nodes", |
ff2ad0f7 | 1936 | sizeof (struct value_set_node), 30); |
7e6eb623 | 1937 | calculate_dominance_info (CDI_POST_DOMINATORS); |
6de9cd9a | 1938 | calculate_dominance_info (CDI_DOMINATORS); |
a38b644b ZW |
1939 | binary_node_pool = create_alloc_pool ("Binary tree nodes", |
1940 | tree_code_size (PLUS_EXPR), 30); | |
1941 | unary_node_pool = create_alloc_pool ("Unary tree nodes", | |
1942 | tree_code_size (NEGATE_EXPR), 30); | |
1943 | reference_node_pool = create_alloc_pool ("Reference tree nodes", | |
6048b706 | 1944 | tree_code_size (ARRAY_REF), 30); |
7e6eb623 DB |
1945 | FOR_ALL_BB (bb) |
1946 | { | |
1947 | EXP_GEN (bb) = set_new (true); | |
6b416da1 DB |
1948 | PHI_GEN (bb) = bitmap_set_new (); |
1949 | TMP_GEN (bb) = bitmap_set_new (); | |
bdee7684 | 1950 | AVAIL_OUT (bb) = bitmap_set_new (); |
7e6eb623 | 1951 | } |
53b4bf74 DN |
1952 | |
1953 | need_eh_cleanup = BITMAP_XMALLOC (); | |
ff2ad0f7 DN |
1954 | } |
1955 | ||
1956 | ||
1957 | /* Deallocate data structures used by PRE. */ | |
6de9cd9a | 1958 | |
ff2ad0f7 DN |
1959 | static void |
1960 | fini_pre (void) | |
1961 | { | |
1962 | basic_block bb; | |
3aecd08b JL |
1963 | unsigned int i; |
1964 | ||
8eee3528 | 1965 | bsi_commit_edge_inserts (NULL); |
ff2ad0f7 | 1966 | |
c4817ba6 | 1967 | obstack_free (&grand_bitmap_obstack, NULL); |
ff2ad0f7 | 1968 | free_alloc_pool (value_set_pool); |
bdee7684 | 1969 | free_alloc_pool (bitmap_set_pool); |
ff2ad0f7 DN |
1970 | free_alloc_pool (value_set_node_pool); |
1971 | free_alloc_pool (binary_node_pool); | |
3d3fa3a1 | 1972 | free_alloc_pool (reference_node_pool); |
ff2ad0f7 DN |
1973 | free_alloc_pool (unary_node_pool); |
1974 | htab_delete (phi_translate_table); | |
6809cbf9 | 1975 | remove_fake_exit_edges (); |
50265400 | 1976 | |
ff2ad0f7 DN |
1977 | FOR_ALL_BB (bb) |
1978 | { | |
1979 | free (bb->aux); | |
1980 | bb->aux = NULL; | |
1981 | } | |
6809cbf9 | 1982 | |
ff2ad0f7 DN |
1983 | free_dominance_info (CDI_POST_DOMINATORS); |
1984 | vn_delete (); | |
53b4bf74 | 1985 | |
eb59b8de | 1986 | if (!bitmap_empty_p (need_eh_cleanup)) |
53b4bf74 DN |
1987 | { |
1988 | tree_purge_all_dead_eh_edges (need_eh_cleanup); | |
1989 | cleanup_tree_cfg (); | |
1990 | } | |
1991 | ||
1992 | BITMAP_XFREE (need_eh_cleanup); | |
3aecd08b JL |
1993 | |
1994 | /* Wipe out pointers to VALUE_HANDLEs. In the not terribly distant | |
1995 | future we will want them to be persistent though. */ | |
1996 | for (i = 0; i < num_ssa_names; i++) | |
1997 | { | |
1998 | tree name = ssa_name (i); | |
1999 | ||
2000 | if (!name) | |
2001 | continue; | |
2002 | ||
2003 | if (SSA_NAME_VALUE (name) | |
2004 | && TREE_CODE (SSA_NAME_VALUE (name)) == VALUE_HANDLE) | |
2005 | SSA_NAME_VALUE (name) = NULL; | |
2006 | } | |
ff2ad0f7 DN |
2007 | } |
2008 | ||
2009 | ||
2010 | /* Main entry point to the SSA-PRE pass. DO_FRE is true if the caller | |
2011 | only wants to do full redundancy elimination. */ | |
2012 | ||
2013 | static void | |
2014 | execute_pre (bool do_fre) | |
2015 | { | |
2016 | init_pre (); | |
2017 | ||
2018 | /* Collect and value number expressions computed in each basic | |
2019 | block. */ | |
7e6eb623 | 2020 | compute_avail (ENTRY_BLOCK_PTR); |
6de9cd9a | 2021 | |
7e6eb623 DB |
2022 | if (dump_file && (dump_flags & TDF_DETAILS)) |
2023 | { | |
ff2ad0f7 DN |
2024 | basic_block bb; |
2025 | ||
7e6eb623 DB |
2026 | FOR_ALL_BB (bb) |
2027 | { | |
2028 | print_value_set (dump_file, EXP_GEN (bb), "exp_gen", bb->index); | |
6b416da1 DB |
2029 | bitmap_print_value_set (dump_file, TMP_GEN (bb), "tmp_gen", |
2030 | bb->index); | |
bdee7684 DB |
2031 | bitmap_print_value_set (dump_file, AVAIL_OUT (bb), "avail_out", |
2032 | bb->index); | |
7e6eb623 DB |
2033 | } |
2034 | } | |
6de9cd9a | 2035 | |
7e6eb623 DB |
2036 | /* Insert can get quite slow on an incredibly large number of basic |
2037 | blocks due to some quadratic behavior. Until this behavior is | |
2038 | fixed, don't run it when he have an incredibly large number of | |
2039 | bb's. If we aren't going to run insert, there is no point in | |
2040 | computing ANTIC, either, even though it's plenty fast. */ | |
ff2ad0f7 | 2041 | if (!do_fre && n_basic_blocks < 4000) |
6de9cd9a | 2042 | { |
7e6eb623 | 2043 | compute_antic (); |
7e6eb623 DB |
2044 | insert (); |
2045 | } | |
ff2ad0f7 DN |
2046 | |
2047 | /* Remove all the redundant expressions. */ | |
7e6eb623 DB |
2048 | eliminate (); |
2049 | ||
2050 | if (dump_file && (dump_flags & TDF_STATS)) | |
2051 | { | |
2052 | fprintf (dump_file, "Insertions:%d\n", pre_stats.insertions); | |
2053 | fprintf (dump_file, "New PHIs:%d\n", pre_stats.phis); | |
2054 | fprintf (dump_file, "Eliminated:%d\n", pre_stats.eliminations); | |
6de9cd9a DN |
2055 | } |
2056 | ||
ff2ad0f7 DN |
2057 | fini_pre (); |
2058 | } | |
2059 | ||
2060 | ||
2061 | /* Gate and execute functions for PRE. */ | |
2062 | ||
2063 | static void | |
2064 | do_pre (void) | |
2065 | { | |
2066 | execute_pre (false); | |
6de9cd9a DN |
2067 | } |
2068 | ||
2069 | static bool | |
2070 | gate_pre (void) | |
2071 | { | |
2072 | return flag_tree_pre != 0; | |
2073 | } | |
2074 | ||
7e6eb623 | 2075 | struct tree_opt_pass pass_pre = |
6de9cd9a DN |
2076 | { |
2077 | "pre", /* name */ | |
2078 | gate_pre, /* gate */ | |
ff2ad0f7 | 2079 | do_pre, /* execute */ |
6de9cd9a DN |
2080 | NULL, /* sub */ |
2081 | NULL, /* next */ | |
2082 | 0, /* static_pass_number */ | |
2083 | TV_TREE_PRE, /* tv_id */ | |
c1b763fa DN |
2084 | PROP_no_crit_edges | PROP_cfg |
2085 | | PROP_ssa | PROP_alias, /* properties_required */ | |
6de9cd9a DN |
2086 | 0, /* properties_provided */ |
2087 | 0, /* properties_destroyed */ | |
2088 | 0, /* todo_flags_start */ | |
9f8628ba PB |
2089 | TODO_dump_func | TODO_ggc_collect | TODO_verify_ssa, /* todo_flags_finish */ |
2090 | 0 /* letter */ | |
6de9cd9a | 2091 | }; |
ff2ad0f7 DN |
2092 | |
2093 | ||
2094 | /* Gate and execute functions for FRE. */ | |
2095 | ||
2096 | static void | |
2097 | do_fre (void) | |
2098 | { | |
2099 | execute_pre (true); | |
2100 | } | |
2101 | ||
2102 | static bool | |
2103 | gate_fre (void) | |
2104 | { | |
2105 | return flag_tree_fre != 0; | |
2106 | } | |
2107 | ||
2108 | struct tree_opt_pass pass_fre = | |
2109 | { | |
2110 | "fre", /* name */ | |
2111 | gate_fre, /* gate */ | |
2112 | do_fre, /* execute */ | |
2113 | NULL, /* sub */ | |
2114 | NULL, /* next */ | |
2115 | 0, /* static_pass_number */ | |
2116 | TV_TREE_FRE, /* tv_id */ | |
c1b763fa | 2117 | PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */ |
ff2ad0f7 DN |
2118 | 0, /* properties_provided */ |
2119 | 0, /* properties_destroyed */ | |
2120 | 0, /* todo_flags_start */ | |
9f8628ba PB |
2121 | TODO_dump_func | TODO_ggc_collect | TODO_verify_ssa, /* todo_flags_finish */ |
2122 | 0 /* letter */ | |
ff2ad0f7 | 2123 | }; |