]>
Commit | Line | Data |
---|---|---|
6de9cd9a | 1 | /* SSA-PRE for trees. |
66647d44 | 2 | Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009 |
939409af | 3 | Free Software Foundation, Inc. |
7e6eb623 | 4 | Contributed by Daniel Berlin <dan@dberlin.org> and Steven Bosscher |
b9c5e484 | 5 | <stevenb@suse.de> |
6de9cd9a DN |
6 | |
7 | This file is part of GCC. | |
8 | ||
9 | GCC is free software; you can redistribute it and/or modify | |
10 | it under the terms of the GNU General Public License as published by | |
9dcd6f09 | 11 | the Free Software Foundation; either version 3, or (at your option) |
6de9cd9a DN |
12 | any later version. |
13 | ||
14 | GCC is distributed in the hope that it will be useful, | |
15 | but WITHOUT ANY WARRANTY; without even the implied warranty of | |
16 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
17 | GNU General Public License for more details. | |
18 | ||
19 | You should have received a copy of the GNU General Public License | |
9dcd6f09 NC |
20 | along with GCC; see the file COPYING3. If not see |
21 | <http://www.gnu.org/licenses/>. */ | |
33c94679 | 22 | |
6de9cd9a DN |
23 | #include "config.h" |
24 | #include "system.h" | |
25 | #include "coretypes.h" | |
26 | #include "tm.h" | |
6de9cd9a DN |
27 | #include "ggc.h" |
28 | #include "tree.h" | |
6de9cd9a DN |
29 | #include "basic-block.h" |
30 | #include "diagnostic.h" | |
31 | #include "tree-inline.h" | |
32 | #include "tree-flow.h" | |
726a989a | 33 | #include "gimple.h" |
6de9cd9a DN |
34 | #include "tree-dump.h" |
35 | #include "timevar.h" | |
36 | #include "fibheap.h" | |
37 | #include "hashtab.h" | |
38 | #include "tree-iterator.h" | |
39 | #include "real.h" | |
40 | #include "alloc-pool.h" | |
5039610b | 41 | #include "obstack.h" |
6de9cd9a DN |
42 | #include "tree-pass.h" |
43 | #include "flags.h" | |
7e6eb623 DB |
44 | #include "bitmap.h" |
45 | #include "langhooks.h" | |
0fc6c492 | 46 | #include "cfgloop.h" |
89fb70a3 | 47 | #include "tree-ssa-sccvn.h" |
a8338640 | 48 | #include "tree-scalar-evolution.h" |
f0ed4cfb | 49 | #include "params.h" |
c9145754 | 50 | #include "dbgcnt.h" |
33c94679 | 51 | |
7e6eb623 | 52 | /* TODO: |
b9c5e484 | 53 | |
bdee7684 | 54 | 1. Avail sets can be shared by making an avail_find_leader that |
7e6eb623 DB |
55 | walks up the dominator tree and looks in those avail sets. |
56 | This might affect code optimality, it's unclear right now. | |
c90186eb | 57 | 2. Strength reduction can be performed by anticipating expressions |
7e6eb623 | 58 | we can repair later on. |
c90186eb | 59 | 3. We can do back-substitution or smarter value numbering to catch |
0fc6c492 | 60 | commutative expressions split up over multiple statements. |
b9c5e484 | 61 | */ |
7e6eb623 DB |
62 | |
63 | /* For ease of terminology, "expression node" in the below refers to | |
726a989a | 64 | every expression node but GIMPLE_ASSIGN, because GIMPLE_ASSIGNs |
07beea0d AH |
65 | represent the actual statement containing the expressions we care about, |
66 | and we cache the value number by putting it in the expression. */ | |
7e6eb623 DB |
67 | |
68 | /* Basic algorithm | |
b9c5e484 | 69 | |
56db793a DB |
70 | First we walk the statements to generate the AVAIL sets, the |
71 | EXP_GEN sets, and the tmp_gen sets. EXP_GEN sets represent the | |
72 | generation of values/expressions by a given block. We use them | |
73 | when computing the ANTIC sets. The AVAIL sets consist of | |
74 | SSA_NAME's that represent values, so we know what values are | |
75 | available in what blocks. AVAIL is a forward dataflow problem. In | |
76 | SSA, values are never killed, so we don't need a kill set, or a | |
77 | fixpoint iteration, in order to calculate the AVAIL sets. In | |
78 | traditional parlance, AVAIL sets tell us the downsafety of the | |
7e6eb623 | 79 | expressions/values. |
b9c5e484 | 80 | |
56db793a DB |
81 | Next, we generate the ANTIC sets. These sets represent the |
82 | anticipatable expressions. ANTIC is a backwards dataflow | |
d75dbccd | 83 | problem. An expression is anticipatable in a given block if it could |
56db793a DB |
84 | be generated in that block. This means that if we had to perform |
85 | an insertion in that block, of the value of that expression, we | |
86 | could. Calculating the ANTIC sets requires phi translation of | |
87 | expressions, because the flow goes backwards through phis. We must | |
88 | iterate to a fixpoint of the ANTIC sets, because we have a kill | |
89 | set. Even in SSA form, values are not live over the entire | |
90 | function, only from their definition point onwards. So we have to | |
91 | remove values from the ANTIC set once we go past the definition | |
92 | point of the leaders that make them up. | |
93 | compute_antic/compute_antic_aux performs this computation. | |
7e6eb623 DB |
94 | |
95 | Third, we perform insertions to make partially redundant | |
96 | expressions fully redundant. | |
97 | ||
98 | An expression is partially redundant (excluding partial | |
99 | anticipation) if: | |
100 | ||
101 | 1. It is AVAIL in some, but not all, of the predecessors of a | |
102 | given block. | |
103 | 2. It is ANTIC in all the predecessors. | |
104 | ||
105 | In order to make it fully redundant, we insert the expression into | |
106 | the predecessors where it is not available, but is ANTIC. | |
d75dbccd DB |
107 | |
108 | For the partial anticipation case, we only perform insertion if it | |
109 | is partially anticipated in some block, and fully available in all | |
110 | of the predecessors. | |
111 | ||
112 | insert/insert_aux/do_regular_insertion/do_partial_partial_insertion | |
113 | performs these steps. | |
7e6eb623 DB |
114 | |
115 | Fourth, we eliminate fully redundant expressions. | |
116 | This is a simple statement walk that replaces redundant | |
070b797d | 117 | calculations with the now available values. */ |
7e6eb623 DB |
118 | |
119 | /* Representations of value numbers: | |
120 | ||
c9145754 DB |
121 | Value numbers are represented by a representative SSA_NAME. We |
122 | will create fake SSA_NAME's in situations where we need a | |
123 | representative but do not have one (because it is a complex | |
124 | expression). In order to facilitate storing the value numbers in | |
125 | bitmaps, and keep the number of wasted SSA_NAME's down, we also | |
126 | associate a value_id with each value number, and create full blown | |
127 | ssa_name's only where we actually need them (IE in operands of | |
128 | existing expressions). | |
129 | ||
130 | Theoretically you could replace all the value_id's with | |
131 | SSA_NAME_VERSION, but this would allocate a large number of | |
132 | SSA_NAME's (which are each > 30 bytes) just to get a 4 byte number. | |
133 | It would also require an additional indirection at each point we | |
134 | use the value id. */ | |
7e6eb623 | 135 | |
b9c5e484 | 136 | /* Representation of expressions on value numbers: |
7e6eb623 | 137 | |
249eb506 | 138 | Expressions consisting of value numbers are represented the same |
c9145754 DB |
139 | way as our VN internally represents them, with an additional |
140 | "pre_expr" wrapping around them in order to facilitate storing all | |
141 | of the expressions in the same sets. */ | |
7e6eb623 | 142 | |
c9145754 | 143 | /* Representation of sets: |
7e6eb623 | 144 | |
c9145754 DB |
145 | The dataflow sets do not need to be sorted in any particular order |
146 | for the majority of their lifetime, are simply represented as two | |
147 | bitmaps, one that keeps track of values present in the set, and one | |
148 | that keeps track of expressions present in the set. | |
7e6eb623 | 149 | |
c9145754 DB |
150 | When we need them in topological order, we produce it on demand by |
151 | transforming the bitmap into an array and sorting it into topo | |
152 | order. */ | |
7e6eb623 | 153 | |
c9145754 DB |
154 | /* Type of expression, used to know which member of the PRE_EXPR union |
155 | is valid. */ | |
7e6eb623 | 156 | |
c9145754 DB |
157 | enum pre_expr_kind |
158 | { | |
159 | NAME, | |
160 | NARY, | |
161 | REFERENCE, | |
162 | CONSTANT | |
163 | }; | |
164 | ||
165 | typedef union pre_expr_union_d | |
166 | { | |
167 | tree name; | |
168 | tree constant; | |
169 | vn_nary_op_t nary; | |
170 | vn_reference_t reference; | |
171 | } pre_expr_union; | |
b9c5e484 | 172 | |
c9145754 DB |
173 | typedef struct pre_expr_d |
174 | { | |
175 | enum pre_expr_kind kind; | |
176 | unsigned int id; | |
177 | pre_expr_union u; | |
178 | } *pre_expr; | |
7e6eb623 | 179 | |
c9145754 DB |
180 | #define PRE_EXPR_NAME(e) (e)->u.name |
181 | #define PRE_EXPR_NARY(e) (e)->u.nary | |
182 | #define PRE_EXPR_REFERENCE(e) (e)->u.reference | |
183 | #define PRE_EXPR_CONSTANT(e) (e)->u.constant | |
7e6eb623 | 184 | |
c9145754 DB |
185 | static int |
186 | pre_expr_eq (const void *p1, const void *p2) | |
187 | { | |
188 | const struct pre_expr_d *e1 = (const struct pre_expr_d *) p1; | |
189 | const struct pre_expr_d *e2 = (const struct pre_expr_d *) p2; | |
7e6eb623 | 190 | |
c9145754 DB |
191 | if (e1->kind != e2->kind) |
192 | return false; | |
193 | ||
194 | switch (e1->kind) | |
195 | { | |
196 | case CONSTANT: | |
726a989a RB |
197 | return vn_constant_eq_with_type (PRE_EXPR_CONSTANT (e1), |
198 | PRE_EXPR_CONSTANT (e2)); | |
c9145754 DB |
199 | case NAME: |
200 | return PRE_EXPR_NAME (e1) == PRE_EXPR_NAME (e2); | |
201 | case NARY: | |
202 | return vn_nary_op_eq (PRE_EXPR_NARY (e1), PRE_EXPR_NARY (e2)); | |
203 | case REFERENCE: | |
204 | return vn_reference_eq (PRE_EXPR_REFERENCE (e1), | |
205 | PRE_EXPR_REFERENCE (e2)); | |
206 | default: | |
9708c51d | 207 | gcc_unreachable (); |
c9145754 DB |
208 | } |
209 | } | |
210 | ||
211 | static hashval_t | |
212 | pre_expr_hash (const void *p1) | |
213 | { | |
214 | const struct pre_expr_d *e = (const struct pre_expr_d *) p1; | |
215 | switch (e->kind) | |
216 | { | |
217 | case CONSTANT: | |
726a989a | 218 | return vn_hash_constant_with_type (PRE_EXPR_CONSTANT (e)); |
c9145754 | 219 | case NAME: |
9708c51d | 220 | return SSA_NAME_VERSION (PRE_EXPR_NAME (e)); |
c9145754 | 221 | case NARY: |
85169114 | 222 | return PRE_EXPR_NARY (e)->hashcode; |
c9145754 | 223 | case REFERENCE: |
85169114 | 224 | return PRE_EXPR_REFERENCE (e)->hashcode; |
c9145754 | 225 | default: |
9708c51d | 226 | gcc_unreachable (); |
c9145754 DB |
227 | } |
228 | } | |
83737db2 | 229 | |
c5830edf | 230 | |
c9145754 DB |
231 | /* Next global expression id number. */ |
232 | static unsigned int next_expression_id; | |
070b797d | 233 | |
83737db2 | 234 | /* Mapping from expression to id number we can use in bitmap sets. */ |
c9145754 DB |
235 | DEF_VEC_P (pre_expr); |
236 | DEF_VEC_ALLOC_P (pre_expr, heap); | |
237 | static VEC(pre_expr, heap) *expressions; | |
238 | static htab_t expression_to_id; | |
13de9095 | 239 | static VEC(unsigned, heap) *name_to_id; |
81def1b7 | 240 | |
83737db2 DB |
241 | /* Allocate an expression id for EXPR. */ |
242 | ||
243 | static inline unsigned int | |
c9145754 | 244 | alloc_expression_id (pre_expr expr) |
6de9cd9a | 245 | { |
c9145754 | 246 | void **slot; |
83737db2 DB |
247 | /* Make sure we won't overflow. */ |
248 | gcc_assert (next_expression_id + 1 > next_expression_id); | |
c9145754 DB |
249 | expr->id = next_expression_id++; |
250 | VEC_safe_push (pre_expr, heap, expressions, expr); | |
13de9095 RG |
251 | if (expr->kind == NAME) |
252 | { | |
253 | unsigned version = SSA_NAME_VERSION (PRE_EXPR_NAME (expr)); | |
254 | /* VEC_safe_grow_cleared allocates no headroom. Avoid frequent | |
255 | re-allocations by using VEC_reserve upfront. There is no | |
256 | VEC_quick_grow_cleared unfortunately. */ | |
257 | VEC_reserve (unsigned, heap, name_to_id, num_ssa_names); | |
258 | VEC_safe_grow_cleared (unsigned, heap, name_to_id, num_ssa_names); | |
259 | gcc_assert (VEC_index (unsigned, name_to_id, version) == 0); | |
260 | VEC_replace (unsigned, name_to_id, version, expr->id); | |
261 | } | |
262 | else | |
263 | { | |
264 | slot = htab_find_slot (expression_to_id, expr, INSERT); | |
265 | gcc_assert (!*slot); | |
266 | *slot = expr; | |
267 | } | |
83737db2 DB |
268 | return next_expression_id - 1; |
269 | } | |
270 | ||
271 | /* Return the expression id for tree EXPR. */ | |
272 | ||
273 | static inline unsigned int | |
c9145754 DB |
274 | get_expression_id (const pre_expr expr) |
275 | { | |
276 | return expr->id; | |
277 | } | |
278 | ||
279 | static inline unsigned int | |
280 | lookup_expression_id (const pre_expr expr) | |
7e6eb623 | 281 | { |
c9145754 | 282 | void **slot; |
b71b4522 | 283 | |
13de9095 RG |
284 | if (expr->kind == NAME) |
285 | { | |
286 | unsigned version = SSA_NAME_VERSION (PRE_EXPR_NAME (expr)); | |
287 | if (VEC_length (unsigned, name_to_id) <= version) | |
288 | return 0; | |
289 | return VEC_index (unsigned, name_to_id, version); | |
290 | } | |
291 | else | |
292 | { | |
293 | slot = htab_find_slot (expression_to_id, expr, NO_INSERT); | |
294 | if (!slot) | |
295 | return 0; | |
296 | return ((pre_expr)*slot)->id; | |
297 | } | |
83737db2 | 298 | } |
b9c5e484 | 299 | |
83737db2 DB |
300 | /* Return the existing expression id for EXPR, or create one if one |
301 | does not exist yet. */ | |
b9c5e484 | 302 | |
83737db2 | 303 | static inline unsigned int |
c9145754 | 304 | get_or_alloc_expression_id (pre_expr expr) |
83737db2 | 305 | { |
c9145754 DB |
306 | unsigned int id = lookup_expression_id (expr); |
307 | if (id == 0) | |
83737db2 | 308 | return alloc_expression_id (expr); |
c9145754 | 309 | return expr->id = id; |
83737db2 DB |
310 | } |
311 | ||
312 | /* Return the expression that has expression id ID */ | |
313 | ||
c9145754 | 314 | static inline pre_expr |
83737db2 DB |
315 | expression_for_id (unsigned int id) |
316 | { | |
c9145754 | 317 | return VEC_index (pre_expr, expressions, id); |
c5830edf DB |
318 | } |
319 | ||
b71b4522 DB |
320 | /* Free the expression id field in all of our expressions, |
321 | and then destroy the expressions array. */ | |
322 | ||
323 | static void | |
324 | clear_expression_ids (void) | |
325 | { | |
c9145754 DB |
326 | VEC_free (pre_expr, heap, expressions); |
327 | } | |
b71b4522 | 328 | |
c9145754 DB |
329 | static alloc_pool pre_expr_pool; |
330 | ||
331 | /* Given an SSA_NAME NAME, get or create a pre_expr to represent it. */ | |
332 | ||
333 | static pre_expr | |
334 | get_or_alloc_expr_for_name (tree name) | |
335 | { | |
5f5126d6 RG |
336 | struct pre_expr_d expr; |
337 | pre_expr result; | |
c9145754 DB |
338 | unsigned int result_id; |
339 | ||
5f5126d6 RG |
340 | expr.kind = NAME; |
341 | expr.id = 0; | |
342 | PRE_EXPR_NAME (&expr) = name; | |
343 | result_id = lookup_expression_id (&expr); | |
344 | if (result_id != 0) | |
345 | return expression_for_id (result_id); | |
346 | ||
347 | result = (pre_expr) pool_alloc (pre_expr_pool); | |
c9145754 | 348 | result->kind = NAME; |
c9145754 | 349 | PRE_EXPR_NAME (result) = name; |
5f5126d6 | 350 | alloc_expression_id (result); |
c9145754 | 351 | return result; |
b71b4522 DB |
352 | } |
353 | ||
83737db2 | 354 | static bool in_fre = false; |
bdee7684 DB |
355 | |
356 | /* An unordered bitmap set. One bitmap tracks values, the other, | |
8c27b7d4 | 357 | expressions. */ |
bdee7684 DB |
358 | typedef struct bitmap_set |
359 | { | |
360 | bitmap expressions; | |
361 | bitmap values; | |
362 | } *bitmap_set_t; | |
363 | ||
83737db2 | 364 | #define FOR_EACH_EXPR_ID_IN_SET(set, id, bi) \ |
c9145754 DB |
365 | EXECUTE_IF_SET_IN_BITMAP((set)->expressions, 0, (id), (bi)) |
366 | ||
85169114 PB |
367 | #define FOR_EACH_VALUE_ID_IN_SET(set, id, bi) \ |
368 | EXECUTE_IF_SET_IN_BITMAP((set)->values, 0, (id), (bi)) | |
369 | ||
c9145754 DB |
370 | /* Mapping from value id to expressions with that value_id. */ |
371 | DEF_VEC_P (bitmap_set_t); | |
372 | DEF_VEC_ALLOC_P (bitmap_set_t, heap); | |
373 | static VEC(bitmap_set_t, heap) *value_expressions; | |
83737db2 | 374 | |
6b416da1 | 375 | /* Sets that we need to keep track of. */ |
83737db2 | 376 | typedef struct bb_bitmap_sets |
6de9cd9a | 377 | { |
ca072a31 DB |
378 | /* The EXP_GEN set, which represents expressions/values generated in |
379 | a basic block. */ | |
83737db2 | 380 | bitmap_set_t exp_gen; |
ca072a31 DB |
381 | |
382 | /* The PHI_GEN set, which represents PHI results generated in a | |
383 | basic block. */ | |
6b416da1 | 384 | bitmap_set_t phi_gen; |
ca072a31 | 385 | |
f6fe65dc | 386 | /* The TMP_GEN set, which represents results/temporaries generated |
ca072a31 | 387 | in a basic block. IE the LHS of an expression. */ |
6b416da1 | 388 | bitmap_set_t tmp_gen; |
ca072a31 DB |
389 | |
390 | /* The AVAIL_OUT set, which represents which values are available in | |
391 | a given basic block. */ | |
bdee7684 | 392 | bitmap_set_t avail_out; |
ca072a31 | 393 | |
c90186eb | 394 | /* The ANTIC_IN set, which represents which values are anticipatable |
ca072a31 | 395 | in a given basic block. */ |
83737db2 | 396 | bitmap_set_t antic_in; |
ca072a31 | 397 | |
d75dbccd DB |
398 | /* The PA_IN set, which represents which values are |
399 | partially anticipatable in a given basic block. */ | |
400 | bitmap_set_t pa_in; | |
401 | ||
ca072a31 DB |
402 | /* The NEW_SETS set, which is used during insertion to augment the |
403 | AVAIL_OUT set of blocks with the new insertions performed during | |
404 | the current iteration. */ | |
6b416da1 | 405 | bitmap_set_t new_sets; |
c90186eb | 406 | |
5006671f RG |
407 | /* A cache for value_dies_in_block_x. */ |
408 | bitmap expr_dies; | |
409 | ||
d75dbccd | 410 | /* True if we have visited this block during ANTIC calculation. */ |
a19eb9d2 | 411 | unsigned int visited : 1; |
d75dbccd DB |
412 | |
413 | /* True we have deferred processing this block during ANTIC | |
414 | calculation until its successor is processed. */ | |
415 | unsigned int deferred : 1; | |
a19eb9d2 RG |
416 | |
417 | /* True when the block contains a call that might not return. */ | |
418 | unsigned int contains_may_not_return_call : 1; | |
d75dbccd DB |
419 | } *bb_value_sets_t; |
420 | ||
421 | #define EXP_GEN(BB) ((bb_value_sets_t) ((BB)->aux))->exp_gen | |
422 | #define PHI_GEN(BB) ((bb_value_sets_t) ((BB)->aux))->phi_gen | |
423 | #define TMP_GEN(BB) ((bb_value_sets_t) ((BB)->aux))->tmp_gen | |
424 | #define AVAIL_OUT(BB) ((bb_value_sets_t) ((BB)->aux))->avail_out | |
425 | #define ANTIC_IN(BB) ((bb_value_sets_t) ((BB)->aux))->antic_in | |
426 | #define PA_IN(BB) ((bb_value_sets_t) ((BB)->aux))->pa_in | |
d75dbccd | 427 | #define NEW_SETS(BB) ((bb_value_sets_t) ((BB)->aux))->new_sets |
5006671f RG |
428 | #define EXPR_DIES(BB) ((bb_value_sets_t) ((BB)->aux))->expr_dies |
429 | #define BB_VISITED(BB) ((bb_value_sets_t) ((BB)->aux))->visited | |
d75dbccd | 430 | #define BB_DEFERRED(BB) ((bb_value_sets_t) ((BB)->aux))->deferred |
a19eb9d2 | 431 | #define BB_MAY_NOTRETURN(BB) ((bb_value_sets_t) ((BB)->aux))->contains_may_not_return_call |
d75dbccd | 432 | |
c9145754 | 433 | |
83737db2 DB |
434 | /* Basic block list in postorder. */ |
435 | static int *postorder; | |
6de9cd9a | 436 | |
ca072a31 DB |
437 | /* This structure is used to keep track of statistics on what |
438 | optimization PRE was able to perform. */ | |
7e6eb623 | 439 | static struct |
6de9cd9a | 440 | { |
ca072a31 | 441 | /* The number of RHS computations eliminated by PRE. */ |
7e6eb623 | 442 | int eliminations; |
ca072a31 DB |
443 | |
444 | /* The number of new expressions/temporaries generated by PRE. */ | |
7e6eb623 | 445 | int insertions; |
ca072a31 | 446 | |
d75dbccd DB |
447 | /* The number of inserts found due to partial anticipation */ |
448 | int pa_insert; | |
449 | ||
ca072a31 | 450 | /* The number of new PHI nodes added by PRE. */ |
7e6eb623 | 451 | int phis; |
b9c5e484 | 452 | |
0fc6c492 DB |
453 | /* The number of values found constant. */ |
454 | int constified; | |
b9c5e484 | 455 | |
7e6eb623 | 456 | } pre_stats; |
6de9cd9a | 457 | |
d75dbccd | 458 | static bool do_partial_partial; |
726a989a | 459 | static pre_expr bitmap_find_leader (bitmap_set_t, unsigned int, gimple); |
c9145754 DB |
460 | static void bitmap_value_insert_into_set (bitmap_set_t, pre_expr); |
461 | static void bitmap_value_replace_in_set (bitmap_set_t, pre_expr); | |
bdee7684 | 462 | static void bitmap_set_copy (bitmap_set_t, bitmap_set_t); |
c9145754 DB |
463 | static bool bitmap_set_contains_value (bitmap_set_t, unsigned int); |
464 | static void bitmap_insert_into_set (bitmap_set_t, pre_expr); | |
9708c51d RG |
465 | static void bitmap_insert_into_set_1 (bitmap_set_t, pre_expr, |
466 | unsigned int, bool); | |
bdee7684 | 467 | static bitmap_set_t bitmap_set_new (void); |
726a989a RB |
468 | static tree create_expression_by_pieces (basic_block, pre_expr, gimple_seq *, |
469 | gimple, tree); | |
470 | static tree find_or_generate_expression (basic_block, pre_expr, gimple_seq *, | |
471 | gimple); | |
de081cfd | 472 | static unsigned int get_expr_value_id (pre_expr); |
6de9cd9a | 473 | |
7e6eb623 DB |
474 | /* We can add and remove elements and entries to and from sets |
475 | and hash tables, so we use alloc pools for them. */ | |
6de9cd9a | 476 | |
bdee7684 | 477 | static alloc_pool bitmap_set_pool; |
7932a3db | 478 | static bitmap_obstack grand_bitmap_obstack; |
6de9cd9a | 479 | |
c90186eb DB |
480 | /* To avoid adding 300 temporary variables when we only need one, we |
481 | only create one temporary variable, on demand, and build ssa names | |
482 | off that. We do have to change the variable if the types don't | |
483 | match the current variable's type. */ | |
484 | static tree pretemp; | |
485 | static tree storetemp; | |
c90186eb DB |
486 | static tree prephitemp; |
487 | ||
53b4bf74 DN |
488 | /* Set of blocks with statements that have had its EH information |
489 | cleaned up. */ | |
490 | static bitmap need_eh_cleanup; | |
491 | ||
7e6eb623 DB |
492 | /* The phi_translate_table caches phi translations for a given |
493 | expression and predecessor. */ | |
ca072a31 | 494 | |
7e6eb623 | 495 | static htab_t phi_translate_table; |
6de9cd9a | 496 | |
7e6eb623 DB |
497 | /* A three tuple {e, pred, v} used to cache phi translations in the |
498 | phi_translate_table. */ | |
6de9cd9a | 499 | |
7e6eb623 | 500 | typedef struct expr_pred_trans_d |
6de9cd9a | 501 | { |
8c27b7d4 | 502 | /* The expression. */ |
c9145754 | 503 | pre_expr e; |
ca072a31 DB |
504 | |
505 | /* The predecessor block along which we translated the expression. */ | |
7e6eb623 | 506 | basic_block pred; |
ca072a31 DB |
507 | |
508 | /* The value that resulted from the translation. */ | |
c9145754 | 509 | pre_expr v; |
ca072a31 DB |
510 | |
511 | /* The hashcode for the expression, pred pair. This is cached for | |
512 | speed reasons. */ | |
7e6eb623 DB |
513 | hashval_t hashcode; |
514 | } *expr_pred_trans_t; | |
741ac903 | 515 | typedef const struct expr_pred_trans_d *const_expr_pred_trans_t; |
6de9cd9a | 516 | |
7e6eb623 | 517 | /* Return the hash value for a phi translation table entry. */ |
6de9cd9a | 518 | |
7e6eb623 DB |
519 | static hashval_t |
520 | expr_pred_trans_hash (const void *p) | |
521 | { | |
741ac903 | 522 | const_expr_pred_trans_t const ve = (const_expr_pred_trans_t) p; |
7e6eb623 DB |
523 | return ve->hashcode; |
524 | } | |
6de9cd9a | 525 | |
ca072a31 DB |
526 | /* Return true if two phi translation table entries are the same. |
527 | P1 and P2 should point to the expr_pred_trans_t's to be compared.*/ | |
7e6eb623 DB |
528 | |
529 | static int | |
530 | expr_pred_trans_eq (const void *p1, const void *p2) | |
531 | { | |
741ac903 KG |
532 | const_expr_pred_trans_t const ve1 = (const_expr_pred_trans_t) p1; |
533 | const_expr_pred_trans_t const ve2 = (const_expr_pred_trans_t) p2; | |
7e6eb623 DB |
534 | basic_block b1 = ve1->pred; |
535 | basic_block b2 = ve2->pred; | |
b9c5e484 | 536 | |
ca072a31 DB |
537 | /* If they are not translations for the same basic block, they can't |
538 | be equal. */ | |
7e6eb623 | 539 | if (b1 != b2) |
6de9cd9a | 540 | return false; |
c9145754 | 541 | return pre_expr_eq (ve1->e, ve2->e); |
6de9cd9a DN |
542 | } |
543 | ||
ca072a31 | 544 | /* Search in the phi translation table for the translation of |
c9145754 | 545 | expression E in basic block PRED. |
c90186eb | 546 | Return the translated value, if found, NULL otherwise. */ |
6de9cd9a | 547 | |
c9145754 DB |
548 | static inline pre_expr |
549 | phi_trans_lookup (pre_expr e, basic_block pred) | |
6de9cd9a | 550 | { |
7e6eb623 | 551 | void **slot; |
ca072a31 | 552 | struct expr_pred_trans_d ept; |
c90186eb | 553 | |
ca072a31 DB |
554 | ept.e = e; |
555 | ept.pred = pred; | |
c9145754 | 556 | ept.hashcode = iterative_hash_hashval_t (pre_expr_hash (e), pred->index); |
ca072a31 | 557 | slot = htab_find_slot_with_hash (phi_translate_table, &ept, ept.hashcode, |
7e6eb623 DB |
558 | NO_INSERT); |
559 | if (!slot) | |
560 | return NULL; | |
561 | else | |
562 | return ((expr_pred_trans_t) *slot)->v; | |
563 | } | |
6de9cd9a | 564 | |
6de9cd9a | 565 | |
c9145754 | 566 | /* Add the tuple mapping from {expression E, basic block PRED} to |
ca072a31 | 567 | value V, to the phi translation table. */ |
7e6eb623 DB |
568 | |
569 | static inline void | |
c9145754 | 570 | phi_trans_add (pre_expr e, pre_expr v, basic_block pred) |
7e6eb623 DB |
571 | { |
572 | void **slot; | |
e1111e8e | 573 | expr_pred_trans_t new_pair = XNEW (struct expr_pred_trans_d); |
7e6eb623 DB |
574 | new_pair->e = e; |
575 | new_pair->pred = pred; | |
576 | new_pair->v = v; | |
c9145754 DB |
577 | new_pair->hashcode = iterative_hash_hashval_t (pre_expr_hash (e), |
578 | pred->index); | |
579 | ||
7e6eb623 DB |
580 | slot = htab_find_slot_with_hash (phi_translate_table, new_pair, |
581 | new_pair->hashcode, INSERT); | |
582 | if (*slot) | |
583 | free (*slot); | |
584 | *slot = (void *) new_pair; | |
6de9cd9a DN |
585 | } |
586 | ||
ff2ad0f7 | 587 | |
c9145754 | 588 | /* Add expression E to the expression set of value id V. */ |
33c94679 | 589 | |
83737db2 | 590 | void |
c9145754 | 591 | add_to_value (unsigned int v, pre_expr e) |
7e6eb623 | 592 | { |
c9145754 DB |
593 | bitmap_set_t set; |
594 | ||
de081cfd RG |
595 | gcc_assert (get_expr_value_id (e) == v); |
596 | ||
c9145754 DB |
597 | if (v >= VEC_length (bitmap_set_t, value_expressions)) |
598 | { | |
599 | VEC_safe_grow_cleared (bitmap_set_t, heap, value_expressions, | |
600 | v + 1); | |
601 | } | |
33c94679 | 602 | |
c9145754 DB |
603 | set = VEC_index (bitmap_set_t, value_expressions, v); |
604 | if (!set) | |
605 | { | |
606 | set = bitmap_set_new (); | |
607 | VEC_replace (bitmap_set_t, value_expressions, v, set); | |
608 | } | |
33c94679 | 609 | |
9708c51d | 610 | bitmap_insert_into_set_1 (set, e, v, true); |
7e6eb623 | 611 | } |
6de9cd9a | 612 | |
bdee7684 DB |
613 | /* Create a new bitmap set and return it. */ |
614 | ||
b9c5e484 | 615 | static bitmap_set_t |
bdee7684 DB |
616 | bitmap_set_new (void) |
617 | { | |
e1111e8e | 618 | bitmap_set_t ret = (bitmap_set_t) pool_alloc (bitmap_set_pool); |
cc175e7c NS |
619 | ret->expressions = BITMAP_ALLOC (&grand_bitmap_obstack); |
620 | ret->values = BITMAP_ALLOC (&grand_bitmap_obstack); | |
bdee7684 DB |
621 | return ret; |
622 | } | |
623 | ||
c9145754 DB |
624 | /* Return the value id for a PRE expression EXPR. */ |
625 | ||
626 | static unsigned int | |
627 | get_expr_value_id (pre_expr expr) | |
628 | { | |
629 | switch (expr->kind) | |
630 | { | |
631 | case CONSTANT: | |
bb9e4199 RG |
632 | { |
633 | unsigned int id; | |
634 | id = get_constant_value_id (PRE_EXPR_CONSTANT (expr)); | |
635 | if (id == 0) | |
636 | { | |
637 | id = get_or_alloc_constant_value_id (PRE_EXPR_CONSTANT (expr)); | |
638 | add_to_value (id, expr); | |
639 | } | |
640 | return id; | |
641 | } | |
c9145754 DB |
642 | case NAME: |
643 | return VN_INFO (PRE_EXPR_NAME (expr))->value_id; | |
644 | case NARY: | |
645 | return PRE_EXPR_NARY (expr)->value_id; | |
646 | case REFERENCE: | |
647 | return PRE_EXPR_REFERENCE (expr)->value_id; | |
648 | default: | |
649 | gcc_unreachable (); | |
650 | } | |
651 | } | |
652 | ||
83737db2 | 653 | /* Remove an expression EXPR from a bitmapped set. */ |
bdee7684 DB |
654 | |
655 | static void | |
c9145754 | 656 | bitmap_remove_from_set (bitmap_set_t set, pre_expr expr) |
bdee7684 | 657 | { |
c9145754 DB |
658 | unsigned int val = get_expr_value_id (expr); |
659 | if (!value_id_constant_p (val)) | |
83737db2 | 660 | { |
c9145754 | 661 | bitmap_clear_bit (set->values, val); |
83737db2 DB |
662 | bitmap_clear_bit (set->expressions, get_expression_id (expr)); |
663 | } | |
bdee7684 | 664 | } |
6de9cd9a | 665 | |
7e6eb623 | 666 | static void |
c9145754 | 667 | bitmap_insert_into_set_1 (bitmap_set_t set, pre_expr expr, |
9708c51d | 668 | unsigned int val, bool allow_constants) |
7e6eb623 | 669 | { |
c9145754 | 670 | if (allow_constants || !value_id_constant_p (val)) |
7e6eb623 | 671 | { |
c9145754 DB |
672 | /* We specifically expect this and only this function to be able to |
673 | insert constants into a set. */ | |
674 | bitmap_set_bit (set->values, val); | |
83737db2 | 675 | bitmap_set_bit (set->expressions, get_or_alloc_expression_id (expr)); |
7e6eb623 DB |
676 | } |
677 | } | |
6de9cd9a | 678 | |
c9145754 DB |
679 | /* Insert an expression EXPR into a bitmapped set. */ |
680 | ||
681 | static void | |
682 | bitmap_insert_into_set (bitmap_set_t set, pre_expr expr) | |
683 | { | |
9708c51d | 684 | bitmap_insert_into_set_1 (set, expr, get_expr_value_id (expr), false); |
c9145754 DB |
685 | } |
686 | ||
bdee7684 DB |
687 | /* Copy a bitmapped set ORIG, into bitmapped set DEST. */ |
688 | ||
689 | static void | |
690 | bitmap_set_copy (bitmap_set_t dest, bitmap_set_t orig) | |
691 | { | |
692 | bitmap_copy (dest->expressions, orig->expressions); | |
693 | bitmap_copy (dest->values, orig->values); | |
694 | } | |
695 | ||
ff3fdad2 | 696 | |
83737db2 | 697 | /* Free memory used up by SET. */ |
ff3fdad2 | 698 | static void |
83737db2 | 699 | bitmap_set_free (bitmap_set_t set) |
ff3fdad2 | 700 | { |
83737db2 DB |
701 | BITMAP_FREE (set->expressions); |
702 | BITMAP_FREE (set->values); | |
ff3fdad2 DB |
703 | } |
704 | ||
ff3fdad2 | 705 | |
83737db2 | 706 | /* Generate an topological-ordered array of bitmap set SET. */ |
ff3fdad2 | 707 | |
c9145754 | 708 | static VEC(pre_expr, heap) * |
83737db2 | 709 | sorted_array_from_bitmap_set (bitmap_set_t set) |
ff3fdad2 | 710 | { |
85169114 PB |
711 | unsigned int i, j; |
712 | bitmap_iterator bi, bj; | |
a7d04a53 RG |
713 | VEC(pre_expr, heap) *result; |
714 | ||
715 | /* Pre-allocate roughly enough space for the array. */ | |
716 | result = VEC_alloc (pre_expr, heap, bitmap_count_bits (set->values)); | |
ff3fdad2 | 717 | |
85169114 PB |
718 | FOR_EACH_VALUE_ID_IN_SET (set, i, bi) |
719 | { | |
720 | /* The number of expressions having a given value is usually | |
721 | relatively small. Thus, rather than making a vector of all | |
722 | the expressions and sorting it by value-id, we walk the values | |
723 | and check in the reverse mapping that tells us what expressions | |
724 | have a given value, to filter those in our set. As a result, | |
725 | the expressions are inserted in value-id order, which means | |
726 | topological order. | |
727 | ||
728 | If this is somehow a significant lose for some cases, we can | |
729 | choose which set to walk based on the set size. */ | |
730 | bitmap_set_t exprset = VEC_index (bitmap_set_t, value_expressions, i); | |
731 | FOR_EACH_EXPR_ID_IN_SET (exprset, j, bj) | |
732 | { | |
733 | if (bitmap_bit_p (set->expressions, j)) | |
734 | VEC_safe_push (pre_expr, heap, result, expression_for_id (j)); | |
735 | } | |
736 | } | |
6de9cd9a | 737 | |
83737db2 | 738 | return result; |
7e6eb623 | 739 | } |
6de9cd9a | 740 | |
83737db2 | 741 | /* Perform bitmapped set operation DEST &= ORIG. */ |
6de9cd9a DN |
742 | |
743 | static void | |
83737db2 | 744 | bitmap_set_and (bitmap_set_t dest, bitmap_set_t orig) |
6de9cd9a | 745 | { |
83737db2 DB |
746 | bitmap_iterator bi; |
747 | unsigned int i; | |
6de9cd9a | 748 | |
d75dbccd | 749 | if (dest != orig) |
83737db2 | 750 | { |
d75dbccd | 751 | bitmap temp = BITMAP_ALLOC (&grand_bitmap_obstack); |
89fb70a3 | 752 | |
d75dbccd | 753 | bitmap_and_into (dest->values, orig->values); |
d75dbccd DB |
754 | bitmap_copy (temp, dest->expressions); |
755 | EXECUTE_IF_SET_IN_BITMAP (temp, 0, i, bi) | |
756 | { | |
c9145754 DB |
757 | pre_expr expr = expression_for_id (i); |
758 | unsigned int value_id = get_expr_value_id (expr); | |
759 | if (!bitmap_bit_p (dest->values, value_id)) | |
d75dbccd DB |
760 | bitmap_clear_bit (dest->expressions, i); |
761 | } | |
762 | BITMAP_FREE (temp); | |
6de9cd9a DN |
763 | } |
764 | } | |
765 | ||
83737db2 | 766 | /* Subtract all values and expressions contained in ORIG from DEST. */ |
7e6eb623 | 767 | |
83737db2 DB |
768 | static bitmap_set_t |
769 | bitmap_set_subtract (bitmap_set_t dest, bitmap_set_t orig) | |
7e6eb623 | 770 | { |
83737db2 DB |
771 | bitmap_set_t result = bitmap_set_new (); |
772 | bitmap_iterator bi; | |
773 | unsigned int i; | |
b9c5e484 | 774 | |
83737db2 DB |
775 | bitmap_and_compl (result->expressions, dest->expressions, |
776 | orig->expressions); | |
6de9cd9a | 777 | |
83737db2 DB |
778 | FOR_EACH_EXPR_ID_IN_SET (result, i, bi) |
779 | { | |
c9145754 DB |
780 | pre_expr expr = expression_for_id (i); |
781 | unsigned int value_id = get_expr_value_id (expr); | |
782 | bitmap_set_bit (result->values, value_id); | |
83737db2 | 783 | } |
af75a7ea | 784 | |
83737db2 | 785 | return result; |
6b416da1 DB |
786 | } |
787 | ||
d75dbccd DB |
788 | /* Subtract all the values in bitmap set B from bitmap set A. */ |
789 | ||
790 | static void | |
791 | bitmap_set_subtract_values (bitmap_set_t a, bitmap_set_t b) | |
792 | { | |
793 | unsigned int i; | |
794 | bitmap_iterator bi; | |
795 | bitmap temp = BITMAP_ALLOC (&grand_bitmap_obstack); | |
796 | ||
797 | bitmap_copy (temp, a->expressions); | |
798 | EXECUTE_IF_SET_IN_BITMAP (temp, 0, i, bi) | |
799 | { | |
c9145754 DB |
800 | pre_expr expr = expression_for_id (i); |
801 | if (bitmap_set_contains_value (b, get_expr_value_id (expr))) | |
d75dbccd DB |
802 | bitmap_remove_from_set (a, expr); |
803 | } | |
804 | BITMAP_FREE (temp); | |
805 | } | |
806 | ||
807 | ||
c9145754 | 808 | /* Return true if bitmapped set SET contains the value VALUE_ID. */ |
6de9cd9a | 809 | |
bdee7684 | 810 | static bool |
c9145754 | 811 | bitmap_set_contains_value (bitmap_set_t set, unsigned int value_id) |
6de9cd9a | 812 | { |
c9145754 | 813 | if (value_id_constant_p (value_id)) |
bdee7684 | 814 | return true; |
83737db2 DB |
815 | |
816 | if (!set || bitmap_empty_p (set->expressions)) | |
817 | return false; | |
818 | ||
c9145754 | 819 | return bitmap_bit_p (set->values, value_id); |
bdee7684 | 820 | } |
7e6eb623 | 821 | |
d75dbccd | 822 | static inline bool |
c9145754 | 823 | bitmap_set_contains_expr (bitmap_set_t set, const pre_expr expr) |
d75dbccd DB |
824 | { |
825 | return bitmap_bit_p (set->expressions, get_expression_id (expr)); | |
826 | } | |
827 | ||
bdee7684 | 828 | /* Replace an instance of value LOOKFOR with expression EXPR in SET. */ |
7e6eb623 | 829 | |
bdee7684 | 830 | static void |
c9145754 DB |
831 | bitmap_set_replace_value (bitmap_set_t set, unsigned int lookfor, |
832 | const pre_expr expr) | |
bdee7684 | 833 | { |
83737db2 DB |
834 | bitmap_set_t exprset; |
835 | unsigned int i; | |
836 | bitmap_iterator bi; | |
837 | ||
c9145754 | 838 | if (value_id_constant_p (lookfor)) |
bdee7684 | 839 | return; |
83737db2 | 840 | |
bdee7684 DB |
841 | if (!bitmap_set_contains_value (set, lookfor)) |
842 | return; | |
e9284566 | 843 | |
6b416da1 DB |
844 | /* The number of expressions having a given value is usually |
845 | significantly less than the total number of expressions in SET. | |
846 | Thus, rather than check, for each expression in SET, whether it | |
847 | has the value LOOKFOR, we walk the reverse mapping that tells us | |
848 | what expressions have a given value, and see if any of those | |
849 | expressions are in our set. For large testcases, this is about | |
850 | 5-10x faster than walking the bitmap. If this is somehow a | |
851 | significant lose for some cases, we can choose which set to walk | |
852 | based on the set size. */ | |
c9145754 | 853 | exprset = VEC_index (bitmap_set_t, value_expressions, lookfor); |
83737db2 | 854 | FOR_EACH_EXPR_ID_IN_SET (exprset, i, bi) |
6de9cd9a | 855 | { |
83737db2 | 856 | if (bitmap_bit_p (set->expressions, i)) |
6de9cd9a | 857 | { |
83737db2 DB |
858 | bitmap_clear_bit (set->expressions, i); |
859 | bitmap_set_bit (set->expressions, get_expression_id (expr)); | |
860 | return; | |
6de9cd9a | 861 | } |
6de9cd9a DN |
862 | } |
863 | } | |
864 | ||
83737db2 | 865 | /* Return true if two bitmap sets are equal. */ |
6de9cd9a | 866 | |
7e6eb623 | 867 | static bool |
83737db2 | 868 | bitmap_set_equal (bitmap_set_t a, bitmap_set_t b) |
6de9cd9a | 869 | { |
83737db2 | 870 | return bitmap_equal_p (a->values, b->values); |
6de9cd9a DN |
871 | } |
872 | ||
e9284566 | 873 | /* Replace an instance of EXPR's VALUE with EXPR in SET if it exists, |
6c6cfbfd | 874 | and add it otherwise. */ |
bdee7684 | 875 | |
7e6eb623 | 876 | static void |
c9145754 | 877 | bitmap_value_replace_in_set (bitmap_set_t set, pre_expr expr) |
7e6eb623 | 878 | { |
c9145754 | 879 | unsigned int val = get_expr_value_id (expr); |
83737db2 | 880 | |
e9284566 DB |
881 | if (bitmap_set_contains_value (set, val)) |
882 | bitmap_set_replace_value (set, val, expr); | |
883 | else | |
884 | bitmap_insert_into_set (set, expr); | |
bdee7684 | 885 | } |
7e6eb623 | 886 | |
bdee7684 DB |
887 | /* Insert EXPR into SET if EXPR's value is not already present in |
888 | SET. */ | |
889 | ||
890 | static void | |
c9145754 | 891 | bitmap_value_insert_into_set (bitmap_set_t set, pre_expr expr) |
bdee7684 | 892 | { |
c9145754 | 893 | unsigned int val = get_expr_value_id (expr); |
af75a7ea | 894 | |
1befacc8 RG |
895 | #ifdef ENABLE_CHECKING |
896 | gcc_assert (expr->id == get_or_alloc_expression_id (expr)); | |
897 | #endif | |
898 | ||
899 | /* Constant values are always considered to be part of the set. */ | |
900 | if (value_id_constant_p (val)) | |
901 | return; | |
902 | ||
903 | /* If the value membership changed, add the expression. */ | |
904 | if (bitmap_set_bit (set->values, val)) | |
905 | bitmap_set_bit (set->expressions, expr->id); | |
7e6eb623 | 906 | } |
6de9cd9a | 907 | |
c9145754 DB |
908 | /* Print out EXPR to outfile. */ |
909 | ||
910 | static void | |
911 | print_pre_expr (FILE *outfile, const pre_expr expr) | |
912 | { | |
913 | switch (expr->kind) | |
914 | { | |
915 | case CONSTANT: | |
916 | print_generic_expr (outfile, PRE_EXPR_CONSTANT (expr), 0); | |
917 | break; | |
918 | case NAME: | |
919 | print_generic_expr (outfile, PRE_EXPR_NAME (expr), 0); | |
920 | break; | |
921 | case NARY: | |
922 | { | |
923 | unsigned int i; | |
924 | vn_nary_op_t nary = PRE_EXPR_NARY (expr); | |
925 | fprintf (outfile, "{%s,", tree_code_name [nary->opcode]); | |
926 | for (i = 0; i < nary->length; i++) | |
927 | { | |
928 | print_generic_expr (outfile, nary->op[i], 0); | |
929 | if (i != (unsigned) nary->length - 1) | |
930 | fprintf (outfile, ","); | |
931 | } | |
932 | fprintf (outfile, "}"); | |
933 | } | |
934 | break; | |
935 | ||
936 | case REFERENCE: | |
937 | { | |
938 | vn_reference_op_t vro; | |
939 | unsigned int i; | |
940 | vn_reference_t ref = PRE_EXPR_REFERENCE (expr); | |
941 | fprintf (outfile, "{"); | |
942 | for (i = 0; | |
943 | VEC_iterate (vn_reference_op_s, ref->operands, i, vro); | |
944 | i++) | |
945 | { | |
5006671f | 946 | bool closebrace = false; |
c9145754 DB |
947 | if (vro->opcode != SSA_NAME |
948 | && TREE_CODE_CLASS (vro->opcode) != tcc_declaration) | |
5006671f RG |
949 | { |
950 | fprintf (outfile, "%s", tree_code_name [vro->opcode]); | |
951 | if (vro->op0) | |
952 | { | |
953 | fprintf (outfile, "<"); | |
954 | closebrace = true; | |
955 | } | |
956 | } | |
c9145754 DB |
957 | if (vro->op0) |
958 | { | |
c9145754 DB |
959 | print_generic_expr (outfile, vro->op0, 0); |
960 | if (vro->op1) | |
961 | { | |
962 | fprintf (outfile, ","); | |
963 | print_generic_expr (outfile, vro->op1, 0); | |
964 | } | |
5006671f RG |
965 | if (vro->op2) |
966 | { | |
967 | fprintf (outfile, ","); | |
968 | print_generic_expr (outfile, vro->op2, 0); | |
969 | } | |
c9145754 | 970 | } |
5006671f RG |
971 | if (closebrace) |
972 | fprintf (outfile, ">"); | |
c9145754 DB |
973 | if (i != VEC_length (vn_reference_op_s, ref->operands) - 1) |
974 | fprintf (outfile, ","); | |
975 | } | |
976 | fprintf (outfile, "}"); | |
5006671f RG |
977 | if (ref->vuse) |
978 | { | |
979 | fprintf (outfile, "@"); | |
980 | print_generic_expr (outfile, ref->vuse, 0); | |
981 | } | |
c9145754 DB |
982 | } |
983 | break; | |
984 | } | |
985 | } | |
986 | void debug_pre_expr (pre_expr); | |
987 | ||
988 | /* Like print_pre_expr but always prints to stderr. */ | |
989 | void | |
990 | debug_pre_expr (pre_expr e) | |
991 | { | |
992 | print_pre_expr (stderr, e); | |
993 | fprintf (stderr, "\n"); | |
994 | } | |
995 | ||
bdee7684 DB |
996 | /* Print out SET to OUTFILE. */ |
997 | ||
998 | static void | |
83737db2 DB |
999 | print_bitmap_set (FILE *outfile, bitmap_set_t set, |
1000 | const char *setname, int blockindex) | |
bdee7684 DB |
1001 | { |
1002 | fprintf (outfile, "%s[%d] := { ", setname, blockindex); | |
1003 | if (set) | |
1004 | { | |
cf6b9ef1 | 1005 | bool first = true; |
3cd8c58a | 1006 | unsigned i; |
87c476a2 ZD |
1007 | bitmap_iterator bi; |
1008 | ||
83737db2 | 1009 | FOR_EACH_EXPR_ID_IN_SET (set, i, bi) |
87c476a2 | 1010 | { |
c9145754 | 1011 | const pre_expr expr = expression_for_id (i); |
83737db2 | 1012 | |
65a6f342 NS |
1013 | if (!first) |
1014 | fprintf (outfile, ", "); | |
1015 | first = false; | |
c9145754 | 1016 | print_pre_expr (outfile, expr); |
b9c5e484 | 1017 | |
c9145754 | 1018 | fprintf (outfile, " (%04d)", get_expr_value_id (expr)); |
87c476a2 | 1019 | } |
bdee7684 DB |
1020 | } |
1021 | fprintf (outfile, " }\n"); | |
1022 | } | |
6de9cd9a | 1023 | |
83737db2 | 1024 | void debug_bitmap_set (bitmap_set_t); |
6de9cd9a | 1025 | |
83737db2 DB |
1026 | void |
1027 | debug_bitmap_set (bitmap_set_t set) | |
1028 | { | |
1029 | print_bitmap_set (stderr, set, "debug", 0); | |
7e6eb623 DB |
1030 | } |
1031 | ||
1032 | /* Print out the expressions that have VAL to OUTFILE. */ | |
33c94679 | 1033 | |
7e6eb623 | 1034 | void |
c9145754 | 1035 | print_value_expressions (FILE *outfile, unsigned int val) |
7e6eb623 | 1036 | { |
c9145754 DB |
1037 | bitmap_set_t set = VEC_index (bitmap_set_t, value_expressions, val); |
1038 | if (set) | |
33c94679 DN |
1039 | { |
1040 | char s[10]; | |
c9145754 DB |
1041 | sprintf (s, "%04d", val); |
1042 | print_bitmap_set (outfile, set, s, 0); | |
33c94679 | 1043 | } |
6de9cd9a DN |
1044 | } |
1045 | ||
6de9cd9a | 1046 | |
7e6eb623 | 1047 | void |
c9145754 | 1048 | debug_value_expressions (unsigned int val) |
6de9cd9a | 1049 | { |
7e6eb623 DB |
1050 | print_value_expressions (stderr, val); |
1051 | } | |
1052 | ||
c9145754 DB |
1053 | /* Given a CONSTANT, allocate a new CONSTANT type PRE_EXPR to |
1054 | represent it. */ | |
0995a441 | 1055 | |
c9145754 DB |
1056 | static pre_expr |
1057 | get_or_alloc_expr_for_constant (tree constant) | |
b9c5e484 | 1058 | { |
c9145754 DB |
1059 | unsigned int result_id; |
1060 | unsigned int value_id; | |
5f5126d6 RG |
1061 | struct pre_expr_d expr; |
1062 | pre_expr newexpr; | |
1063 | ||
1064 | expr.kind = CONSTANT; | |
1065 | PRE_EXPR_CONSTANT (&expr) = constant; | |
1066 | result_id = lookup_expression_id (&expr); | |
1067 | if (result_id != 0) | |
1068 | return expression_for_id (result_id); | |
1069 | ||
1070 | newexpr = (pre_expr) pool_alloc (pre_expr_pool); | |
c9145754 DB |
1071 | newexpr->kind = CONSTANT; |
1072 | PRE_EXPR_CONSTANT (newexpr) = constant; | |
5f5126d6 | 1073 | alloc_expression_id (newexpr); |
c9145754 | 1074 | value_id = get_or_alloc_constant_value_id (constant); |
c9145754 DB |
1075 | add_to_value (value_id, newexpr); |
1076 | return newexpr; | |
0995a441 SB |
1077 | } |
1078 | ||
c9145754 DB |
1079 | /* Given a value id V, find the actual tree representing the constant |
1080 | value if there is one, and return it. Return NULL if we can't find | |
1081 | a constant. */ | |
43da81be DB |
1082 | |
1083 | static tree | |
726a989a | 1084 | get_constant_for_value_id (unsigned int v) |
43da81be | 1085 | { |
c9145754 DB |
1086 | if (value_id_constant_p (v)) |
1087 | { | |
1088 | unsigned int i; | |
1089 | bitmap_iterator bi; | |
1090 | bitmap_set_t exprset = VEC_index (bitmap_set_t, value_expressions, v); | |
1091 | ||
1092 | FOR_EACH_EXPR_ID_IN_SET (exprset, i, bi) | |
1093 | { | |
1094 | pre_expr expr = expression_for_id (i); | |
726a989a | 1095 | if (expr->kind == CONSTANT) |
c9145754 DB |
1096 | return PRE_EXPR_CONSTANT (expr); |
1097 | } | |
1098 | } | |
1099 | return NULL; | |
1100 | } | |
1101 | ||
1102 | /* Get or allocate a pre_expr for a piece of GIMPLE, and return it. | |
1103 | Currently only supports constants and SSA_NAMES. */ | |
1104 | static pre_expr | |
1105 | get_or_alloc_expr_for (tree t) | |
1106 | { | |
1107 | if (TREE_CODE (t) == SSA_NAME) | |
1108 | return get_or_alloc_expr_for_name (t); | |
1d65f45c | 1109 | else if (is_gimple_min_invariant (t)) |
c9145754 | 1110 | return get_or_alloc_expr_for_constant (t); |
726a989a RB |
1111 | else |
1112 | { | |
1113 | /* More complex expressions can result from SCCVN expression | |
1114 | simplification that inserts values for them. As they all | |
1115 | do not have VOPs the get handled by the nary ops struct. */ | |
1116 | vn_nary_op_t result; | |
1117 | unsigned int result_id; | |
1118 | vn_nary_op_lookup (t, &result); | |
1119 | if (result != NULL) | |
1120 | { | |
1121 | pre_expr e = (pre_expr) pool_alloc (pre_expr_pool); | |
1122 | e->kind = NARY; | |
1123 | PRE_EXPR_NARY (e) = result; | |
1124 | result_id = lookup_expression_id (e); | |
1125 | if (result_id != 0) | |
1126 | { | |
1127 | pool_free (pre_expr_pool, e); | |
1128 | e = expression_for_id (result_id); | |
1129 | return e; | |
1130 | } | |
1131 | alloc_expression_id (e); | |
1132 | return e; | |
1133 | } | |
1134 | } | |
c9145754 DB |
1135 | return NULL; |
1136 | } | |
1137 | ||
1138 | /* Return the folded version of T if T, when folded, is a gimple | |
1139 | min_invariant. Otherwise, return T. */ | |
1140 | ||
1141 | static pre_expr | |
1142 | fully_constant_expression (pre_expr e) | |
1143 | { | |
1144 | switch (e->kind) | |
1145 | { | |
1146 | case CONSTANT: | |
1147 | return e; | |
1148 | case NARY: | |
1149 | { | |
1150 | vn_nary_op_t nary = PRE_EXPR_NARY (e); | |
1151 | switch (TREE_CODE_CLASS (nary->opcode)) | |
1152 | { | |
40f64141 RG |
1153 | case tcc_expression: |
1154 | if (nary->opcode == TRUTH_NOT_EXPR) | |
1155 | goto do_unary; | |
1156 | if (nary->opcode != TRUTH_AND_EXPR | |
1157 | && nary->opcode != TRUTH_OR_EXPR | |
1158 | && nary->opcode != TRUTH_XOR_EXPR) | |
1159 | return e; | |
1160 | /* Fallthrough. */ | |
c9145754 | 1161 | case tcc_binary: |
40f64141 | 1162 | case tcc_comparison: |
c9145754 DB |
1163 | { |
1164 | /* We have to go from trees to pre exprs to value ids to | |
1165 | constants. */ | |
1166 | tree naryop0 = nary->op[0]; | |
1167 | tree naryop1 = nary->op[1]; | |
40f64141 RG |
1168 | tree result; |
1169 | if (!is_gimple_min_invariant (naryop0)) | |
726a989a RB |
1170 | { |
1171 | pre_expr rep0 = get_or_alloc_expr_for (naryop0); | |
1172 | unsigned int vrep0 = get_expr_value_id (rep0); | |
40f64141 RG |
1173 | tree const0 = get_constant_for_value_id (vrep0); |
1174 | if (const0) | |
1175 | naryop0 = fold_convert (TREE_TYPE (naryop0), const0); | |
726a989a | 1176 | } |
40f64141 | 1177 | if (!is_gimple_min_invariant (naryop1)) |
726a989a RB |
1178 | { |
1179 | pre_expr rep1 = get_or_alloc_expr_for (naryop1); | |
1180 | unsigned int vrep1 = get_expr_value_id (rep1); | |
40f64141 RG |
1181 | tree const1 = get_constant_for_value_id (vrep1); |
1182 | if (const1) | |
1183 | naryop1 = fold_convert (TREE_TYPE (naryop1), const1); | |
b463e8de | 1184 | } |
40f64141 RG |
1185 | result = fold_binary (nary->opcode, nary->type, |
1186 | naryop0, naryop1); | |
c9145754 DB |
1187 | if (result && is_gimple_min_invariant (result)) |
1188 | return get_or_alloc_expr_for_constant (result); | |
40f64141 RG |
1189 | /* We might have simplified the expression to a |
1190 | SSA_NAME for example from x_1 * 1. But we cannot | |
1191 | insert a PHI for x_1 unconditionally as x_1 might | |
1192 | not be available readily. */ | |
c9145754 DB |
1193 | return e; |
1194 | } | |
40f64141 RG |
1195 | case tcc_reference: |
1196 | if (nary->opcode != REALPART_EXPR | |
b8698a0f | 1197 | && nary->opcode != IMAGPART_EXPR |
40f64141 RG |
1198 | && nary->opcode != VIEW_CONVERT_EXPR) |
1199 | return e; | |
1200 | /* Fallthrough. */ | |
c9145754 | 1201 | case tcc_unary: |
40f64141 | 1202 | do_unary: |
c9145754 | 1203 | { |
40f64141 RG |
1204 | /* We have to go from trees to pre exprs to value ids to |
1205 | constants. */ | |
c9145754 | 1206 | tree naryop0 = nary->op[0]; |
726a989a RB |
1207 | tree const0, result; |
1208 | if (is_gimple_min_invariant (naryop0)) | |
1209 | const0 = naryop0; | |
1210 | else | |
1211 | { | |
1212 | pre_expr rep0 = get_or_alloc_expr_for (naryop0); | |
1213 | unsigned int vrep0 = get_expr_value_id (rep0); | |
1214 | const0 = get_constant_for_value_id (vrep0); | |
1215 | } | |
1216 | result = NULL; | |
c9145754 | 1217 | if (const0) |
b463e8de DB |
1218 | { |
1219 | tree type1 = TREE_TYPE (nary->op[0]); | |
1220 | const0 = fold_convert (type1, const0); | |
1221 | result = fold_unary (nary->opcode, nary->type, const0); | |
1222 | } | |
c9145754 DB |
1223 | if (result && is_gimple_min_invariant (result)) |
1224 | return get_or_alloc_expr_for_constant (result); | |
1225 | return e; | |
1226 | } | |
1227 | default: | |
1228 | return e; | |
1229 | } | |
1230 | } | |
47af7a5c RG |
1231 | case REFERENCE: |
1232 | { | |
1233 | vn_reference_t ref = PRE_EXPR_REFERENCE (e); | |
1234 | VEC (vn_reference_op_s, heap) *operands = ref->operands; | |
1235 | vn_reference_op_t op; | |
1236 | ||
1237 | /* Try to simplify the translated expression if it is | |
1238 | a call to a builtin function with at most two arguments. */ | |
1239 | op = VEC_index (vn_reference_op_s, operands, 0); | |
1240 | if (op->opcode == CALL_EXPR | |
1241 | && TREE_CODE (op->op0) == ADDR_EXPR | |
1242 | && TREE_CODE (TREE_OPERAND (op->op0, 0)) == FUNCTION_DECL | |
1243 | && DECL_BUILT_IN (TREE_OPERAND (op->op0, 0)) | |
1244 | && VEC_length (vn_reference_op_s, operands) >= 2 | |
1245 | && VEC_length (vn_reference_op_s, operands) <= 3) | |
1246 | { | |
1247 | vn_reference_op_t arg0, arg1 = NULL; | |
1248 | bool anyconst = false; | |
1249 | arg0 = VEC_index (vn_reference_op_s, operands, 1); | |
1250 | if (VEC_length (vn_reference_op_s, operands) > 2) | |
1251 | arg1 = VEC_index (vn_reference_op_s, operands, 2); | |
1252 | if (TREE_CODE_CLASS (arg0->opcode) == tcc_constant | |
1253 | || (arg0->opcode == ADDR_EXPR | |
1254 | && is_gimple_min_invariant (arg0->op0))) | |
1255 | anyconst = true; | |
1256 | if (arg1 | |
1257 | && (TREE_CODE_CLASS (arg1->opcode) == tcc_constant | |
1258 | || (arg1->opcode == ADDR_EXPR | |
1259 | && is_gimple_min_invariant (arg1->op0)))) | |
1260 | anyconst = true; | |
1261 | if (anyconst) | |
1262 | { | |
1263 | tree folded = build_call_expr (TREE_OPERAND (op->op0, 0), | |
1264 | arg1 ? 2 : 1, | |
1265 | arg0->op0, | |
1266 | arg1 ? arg1->op0 : NULL); | |
1267 | if (folded | |
1268 | && TREE_CODE (folded) == NOP_EXPR) | |
1269 | folded = TREE_OPERAND (folded, 0); | |
1270 | if (folded | |
1271 | && is_gimple_min_invariant (folded)) | |
1272 | return get_or_alloc_expr_for_constant (folded); | |
1273 | } | |
1274 | } | |
1275 | return e; | |
1276 | } | |
c9145754 DB |
1277 | default: |
1278 | return e; | |
1279 | } | |
1280 | return e; | |
43da81be DB |
1281 | } |
1282 | ||
5006671f | 1283 | /* Translate the VUSE backwards through phi nodes in PHIBLOCK, so that |
84280917 MM |
1284 | it has the value it would have in BLOCK. Set *SAME_VALID to true |
1285 | in case the new vuse doesn't change the value id of the OPERANDS. */ | |
c90186eb | 1286 | |
5006671f RG |
1287 | static tree |
1288 | translate_vuse_through_block (VEC (vn_reference_op_s, heap) *operands, | |
b45d2719 | 1289 | alias_set_type set, tree type, tree vuse, |
5006671f | 1290 | basic_block phiblock, |
84280917 | 1291 | basic_block block, bool *same_valid) |
c90186eb | 1292 | { |
5006671f | 1293 | gimple phi = SSA_NAME_DEF_STMT (vuse); |
b45d2719 | 1294 | ao_ref ref; |
84280917 MM |
1295 | edge e = NULL; |
1296 | bool use_oracle; | |
1297 | ||
1298 | *same_valid = true; | |
43da81be | 1299 | |
5006671f RG |
1300 | if (gimple_bb (phi) != phiblock) |
1301 | return vuse; | |
1302 | ||
84280917 | 1303 | use_oracle = ao_ref_init_from_vn_reference (&ref, set, type, operands); |
5006671f RG |
1304 | |
1305 | /* Use the alias-oracle to find either the PHI node in this block, | |
1306 | the first VUSE used in this block that is equivalent to vuse or | |
1307 | the first VUSE which definition in this block kills the value. */ | |
84280917 MM |
1308 | if (gimple_code (phi) == GIMPLE_PHI) |
1309 | e = find_edge (block, phiblock); | |
1310 | else if (use_oracle) | |
1311 | while (!stmt_may_clobber_ref_p_1 (phi, &ref)) | |
1312 | { | |
1313 | vuse = gimple_vuse (phi); | |
1314 | phi = SSA_NAME_DEF_STMT (vuse); | |
1315 | if (gimple_bb (phi) != phiblock) | |
1316 | return vuse; | |
1317 | if (gimple_code (phi) == GIMPLE_PHI) | |
1318 | { | |
1319 | e = find_edge (block, phiblock); | |
1320 | break; | |
1321 | } | |
1322 | } | |
1323 | else | |
1324 | return NULL_TREE; | |
1325 | ||
1326 | if (e) | |
c90186eb | 1327 | { |
84280917 | 1328 | if (use_oracle) |
5006671f | 1329 | { |
84280917 MM |
1330 | bitmap visited = NULL; |
1331 | /* Try to find a vuse that dominates this phi node by skipping | |
1332 | non-clobbering statements. */ | |
1333 | vuse = get_continuation_for_phi (phi, &ref, &visited); | |
1334 | if (visited) | |
1335 | BITMAP_FREE (visited); | |
5006671f | 1336 | } |
84280917 MM |
1337 | else |
1338 | vuse = NULL_TREE; | |
1339 | if (!vuse) | |
1340 | { | |
1341 | /* If we didn't find any, the value ID can't stay the same, | |
1342 | but return the translated vuse. */ | |
1343 | *same_valid = false; | |
1344 | vuse = PHI_ARG_DEF (phi, e->dest_idx); | |
1345 | } | |
1346 | /* ??? We would like to return vuse here as this is the canonical | |
1347 | upmost vdef that this reference is associated with. But during | |
1348 | insertion of the references into the hash tables we only ever | |
1349 | directly insert with their direct gimple_vuse, hence returning | |
1350 | something else would make us not find the other expression. */ | |
1351 | return PHI_ARG_DEF (phi, e->dest_idx); | |
c90186eb | 1352 | } |
c90186eb | 1353 | |
5006671f | 1354 | return NULL_TREE; |
c90186eb | 1355 | } |
83737db2 | 1356 | |
249eb506 | 1357 | /* Like bitmap_find_leader, but checks for the value existing in SET1 *or* |
83737db2 DB |
1358 | SET2. This is used to avoid making a set consisting of the union |
1359 | of PA_IN and ANTIC_IN during insert. */ | |
1360 | ||
c9145754 DB |
1361 | static inline pre_expr |
1362 | find_leader_in_sets (unsigned int val, bitmap_set_t set1, bitmap_set_t set2) | |
83737db2 | 1363 | { |
c9145754 | 1364 | pre_expr result; |
83737db2 | 1365 | |
726a989a | 1366 | result = bitmap_find_leader (set1, val, NULL); |
83737db2 | 1367 | if (!result && set2) |
726a989a | 1368 | result = bitmap_find_leader (set2, val, NULL); |
83737db2 DB |
1369 | return result; |
1370 | } | |
1371 | ||
c9145754 DB |
1372 | /* Get the tree type for our PRE expression e. */ |
1373 | ||
1374 | static tree | |
1375 | get_expr_type (const pre_expr e) | |
1376 | { | |
1377 | switch (e->kind) | |
1378 | { | |
1379 | case NAME: | |
1380 | return TREE_TYPE (PRE_EXPR_NAME (e)); | |
1381 | case CONSTANT: | |
1382 | return TREE_TYPE (PRE_EXPR_CONSTANT (e)); | |
1383 | case REFERENCE: | |
b45d2719 | 1384 | return PRE_EXPR_REFERENCE (e)->type; |
c9145754 DB |
1385 | case NARY: |
1386 | return PRE_EXPR_NARY (e)->type; | |
1387 | } | |
1388 | gcc_unreachable(); | |
1389 | } | |
1390 | ||
1391 | /* Get a representative SSA_NAME for a given expression. | |
1392 | Since all of our sub-expressions are treated as values, we require | |
1393 | them to be SSA_NAME's for simplicity. | |
1394 | Prior versions of GVNPRE used to use "value handles" here, so that | |
1395 | an expression would be VH.11 + VH.10 instead of d_3 + e_6. In | |
1396 | either case, the operands are really values (IE we do not expect | |
1397 | them to be usable without finding leaders). */ | |
1398 | ||
1399 | static tree | |
1400 | get_representative_for (const pre_expr e) | |
1401 | { | |
1402 | tree exprtype; | |
1403 | tree name; | |
1404 | unsigned int value_id = get_expr_value_id (e); | |
1405 | ||
1406 | switch (e->kind) | |
1407 | { | |
1408 | case NAME: | |
1409 | return PRE_EXPR_NAME (e); | |
1410 | case CONSTANT: | |
726a989a | 1411 | return PRE_EXPR_CONSTANT (e); |
c9145754 DB |
1412 | case NARY: |
1413 | case REFERENCE: | |
1414 | { | |
1415 | /* Go through all of the expressions representing this value | |
1416 | and pick out an SSA_NAME. */ | |
1417 | unsigned int i; | |
1418 | bitmap_iterator bi; | |
1419 | bitmap_set_t exprs = VEC_index (bitmap_set_t, value_expressions, | |
1420 | value_id); | |
1421 | FOR_EACH_EXPR_ID_IN_SET (exprs, i, bi) | |
1422 | { | |
1423 | pre_expr rep = expression_for_id (i); | |
1424 | if (rep->kind == NAME) | |
1425 | return PRE_EXPR_NAME (rep); | |
1426 | } | |
1427 | } | |
1428 | break; | |
1429 | } | |
1430 | /* If we reached here we couldn't find an SSA_NAME. This can | |
1431 | happen when we've discovered a value that has never appeared in | |
1432 | the program as set to an SSA_NAME, most likely as the result of | |
1433 | phi translation. */ | |
1434 | if (dump_file) | |
1435 | { | |
1436 | fprintf (dump_file, | |
1437 | "Could not find SSA_NAME representative for expression:"); | |
1438 | print_pre_expr (dump_file, e); | |
1439 | fprintf (dump_file, "\n"); | |
1440 | } | |
1441 | ||
1442 | exprtype = get_expr_type (e); | |
1443 | ||
1444 | /* Build and insert the assignment of the end result to the temporary | |
1445 | that we will return. */ | |
1446 | if (!pretemp || exprtype != TREE_TYPE (pretemp)) | |
1447 | { | |
1448 | pretemp = create_tmp_var (exprtype, "pretmp"); | |
1449 | get_var_ann (pretemp); | |
1450 | } | |
1451 | ||
726a989a | 1452 | name = make_ssa_name (pretemp, gimple_build_nop ()); |
c9145754 DB |
1453 | VN_INFO_GET (name)->value_id = value_id; |
1454 | if (e->kind == CONSTANT) | |
1455 | VN_INFO (name)->valnum = PRE_EXPR_CONSTANT (e); | |
1456 | else | |
1457 | VN_INFO (name)->valnum = name; | |
1458 | ||
1459 | add_to_value (value_id, get_or_alloc_expr_for_name (name)); | |
1460 | if (dump_file) | |
1461 | { | |
1462 | fprintf (dump_file, "Created SSA_NAME representative "); | |
1463 | print_generic_expr (dump_file, name, 0); | |
1464 | fprintf (dump_file, " for expression:"); | |
1465 | print_pre_expr (dump_file, e); | |
1466 | fprintf (dump_file, "\n"); | |
1467 | } | |
1468 | ||
1469 | return name; | |
1470 | } | |
1471 | ||
1472 | ||
1473 | ||
3e999e7b RG |
1474 | static pre_expr |
1475 | phi_translate (pre_expr expr, bitmap_set_t set1, bitmap_set_t set2, | |
1476 | basic_block pred, basic_block phiblock); | |
c9145754 | 1477 | |
7e6eb623 | 1478 | /* Translate EXPR using phis in PHIBLOCK, so that it has the values of |
788d04b2 RG |
1479 | the phis in PRED. Return NULL if we can't find a leader for each part |
1480 | of the translated expression. */ | |
6de9cd9a | 1481 | |
c9145754 | 1482 | static pre_expr |
3e999e7b RG |
1483 | phi_translate_1 (pre_expr expr, bitmap_set_t set1, bitmap_set_t set2, |
1484 | basic_block pred, basic_block phiblock) | |
6de9cd9a | 1485 | { |
c9145754 | 1486 | switch (expr->kind) |
6de9cd9a | 1487 | { |
c9145754 | 1488 | case NARY: |
43da81be | 1489 | { |
c9145754 DB |
1490 | unsigned int i; |
1491 | bool changed = false; | |
1492 | vn_nary_op_t nary = PRE_EXPR_NARY (expr); | |
1493 | struct vn_nary_op_s newnary; | |
1494 | /* The NARY structure is only guaranteed to have been | |
1495 | allocated to the nary->length operands. */ | |
1496 | memcpy (&newnary, nary, (sizeof (struct vn_nary_op_s) | |
1497 | - sizeof (tree) * (4 - nary->length))); | |
1498 | ||
1499 | for (i = 0; i < newnary.length; i++) | |
43da81be | 1500 | { |
c9145754 DB |
1501 | if (TREE_CODE (newnary.op[i]) != SSA_NAME) |
1502 | continue; | |
1503 | else | |
43da81be | 1504 | { |
af078bb0 | 1505 | pre_expr leader, result; |
c9145754 | 1506 | unsigned int op_val_id = VN_INFO (newnary.op[i])->value_id; |
af078bb0 | 1507 | leader = find_leader_in_sets (op_val_id, set1, set2); |
788d04b2 | 1508 | result = phi_translate (leader, set1, set2, pred, phiblock); |
c9145754 | 1509 | if (result && result != leader) |
43da81be | 1510 | { |
c9145754 DB |
1511 | tree name = get_representative_for (result); |
1512 | if (!name) | |
85300b46 | 1513 | return NULL; |
c9145754 | 1514 | newnary.op[i] = name; |
43da81be | 1515 | } |
c9145754 DB |
1516 | else if (!result) |
1517 | return NULL; | |
0778d4e8 | 1518 | |
c9145754 | 1519 | changed |= newnary.op[i] != nary->op[i]; |
0778d4e8 | 1520 | } |
c9145754 DB |
1521 | } |
1522 | if (changed) | |
1523 | { | |
1524 | pre_expr constant; | |
5f5126d6 | 1525 | unsigned int new_val_id; |
c9145754 DB |
1526 | |
1527 | tree result = vn_nary_op_lookup_pieces (newnary.length, | |
1528 | newnary.opcode, | |
1529 | newnary.type, | |
1530 | newnary.op[0], | |
1531 | newnary.op[1], | |
1532 | newnary.op[2], | |
1533 | newnary.op[3], | |
1534 | &nary); | |
5f5126d6 RG |
1535 | if (result && is_gimple_min_invariant (result)) |
1536 | return get_or_alloc_expr_for_constant (result); | |
c9145754 DB |
1537 | |
1538 | expr = (pre_expr) pool_alloc (pre_expr_pool); | |
1539 | expr->kind = NARY; | |
1540 | expr->id = 0; | |
c9145754 DB |
1541 | if (nary) |
1542 | { | |
1543 | PRE_EXPR_NARY (expr) = nary; | |
1544 | constant = fully_constant_expression (expr); | |
1545 | if (constant != expr) | |
1546 | return constant; | |
0778d4e8 | 1547 | |
c9145754 DB |
1548 | new_val_id = nary->value_id; |
1549 | get_or_alloc_expression_id (expr); | |
1550 | } | |
1551 | else | |
43da81be | 1552 | { |
c9145754 DB |
1553 | new_val_id = get_next_value_id (); |
1554 | VEC_safe_grow_cleared (bitmap_set_t, heap, | |
1555 | value_expressions, | |
1556 | get_max_value_id() + 1); | |
1557 | nary = vn_nary_op_insert_pieces (newnary.length, | |
1558 | newnary.opcode, | |
1559 | newnary.type, | |
1560 | newnary.op[0], | |
1561 | newnary.op[1], | |
1562 | newnary.op[2], | |
1563 | newnary.op[3], | |
1564 | result, new_val_id); | |
1565 | PRE_EXPR_NARY (expr) = nary; | |
1566 | constant = fully_constant_expression (expr); | |
1567 | if (constant != expr) | |
1568 | return constant; | |
1569 | get_or_alloc_expression_id (expr); | |
43da81be | 1570 | } |
b0a0ab2d | 1571 | add_to_value (new_val_id, expr); |
c5830edf | 1572 | } |
c9145754 | 1573 | return expr; |
c90186eb | 1574 | } |
c9145754 | 1575 | break; |
47af7a5c | 1576 | |
c9145754 | 1577 | case REFERENCE: |
c90186eb | 1578 | { |
c9145754 DB |
1579 | vn_reference_t ref = PRE_EXPR_REFERENCE (expr); |
1580 | VEC (vn_reference_op_s, heap) *operands = ref->operands; | |
5006671f RG |
1581 | tree vuse = ref->vuse; |
1582 | tree newvuse = vuse; | |
c9145754 | 1583 | VEC (vn_reference_op_s, heap) *newoperands = NULL; |
84280917 | 1584 | bool changed = false, same_valid = true; |
aa7069aa | 1585 | unsigned int i, j; |
c9145754 DB |
1586 | vn_reference_op_t operand; |
1587 | vn_reference_t newref; | |
1588 | ||
aa7069aa RG |
1589 | for (i = 0, j = 0; |
1590 | VEC_iterate (vn_reference_op_s, operands, i, operand); i++, j++) | |
e13f1c14 | 1591 | { |
c9145754 DB |
1592 | pre_expr opresult; |
1593 | pre_expr leader; | |
1594 | tree oldop0 = operand->op0; | |
1595 | tree oldop1 = operand->op1; | |
1596 | tree oldop2 = operand->op2; | |
1597 | tree op0 = oldop0; | |
1598 | tree op1 = oldop1; | |
1599 | tree op2 = oldop2; | |
1600 | tree type = operand->type; | |
1601 | vn_reference_op_s newop = *operand; | |
1602 | ||
1603 | if (op0 && TREE_CODE (op0) == SSA_NAME) | |
e13f1c14 | 1604 | { |
c9145754 DB |
1605 | unsigned int op_val_id = VN_INFO (op0)->value_id; |
1606 | leader = find_leader_in_sets (op_val_id, set1, set2); | |
788d04b2 | 1607 | opresult = phi_translate (leader, set1, set2, pred, phiblock); |
c9145754 DB |
1608 | if (opresult && opresult != leader) |
1609 | { | |
1610 | tree name = get_representative_for (opresult); | |
1611 | if (!name) | |
b5d76df4 | 1612 | break; |
c9145754 DB |
1613 | op0 = name; |
1614 | } | |
1615 | else if (!opresult) | |
b5d76df4 | 1616 | break; |
c9145754 DB |
1617 | } |
1618 | changed |= op0 != oldop0; | |
b9c5e484 | 1619 | |
c9145754 DB |
1620 | if (op1 && TREE_CODE (op1) == SSA_NAME) |
1621 | { | |
1622 | unsigned int op_val_id = VN_INFO (op1)->value_id; | |
1623 | leader = find_leader_in_sets (op_val_id, set1, set2); | |
788d04b2 | 1624 | opresult = phi_translate (leader, set1, set2, pred, phiblock); |
c9145754 DB |
1625 | if (opresult && opresult != leader) |
1626 | { | |
1627 | tree name = get_representative_for (opresult); | |
1628 | if (!name) | |
b5d76df4 | 1629 | break; |
c9145754 DB |
1630 | op1 = name; |
1631 | } | |
1632 | else if (!opresult) | |
b5d76df4 | 1633 | break; |
e13f1c14 | 1634 | } |
e52201b6 RG |
1635 | /* We can't possibly insert these. */ |
1636 | else if (op1 && !is_gimple_min_invariant (op1)) | |
1637 | break; | |
c9145754 DB |
1638 | changed |= op1 != oldop1; |
1639 | if (op2 && TREE_CODE (op2) == SSA_NAME) | |
e13f1c14 | 1640 | { |
c9145754 DB |
1641 | unsigned int op_val_id = VN_INFO (op2)->value_id; |
1642 | leader = find_leader_in_sets (op_val_id, set1, set2); | |
788d04b2 | 1643 | opresult = phi_translate (leader, set1, set2, pred, phiblock); |
c9145754 DB |
1644 | if (opresult && opresult != leader) |
1645 | { | |
1646 | tree name = get_representative_for (opresult); | |
1647 | if (!name) | |
b5d76df4 | 1648 | break; |
c9145754 DB |
1649 | op2 = name; |
1650 | } | |
1651 | else if (!opresult) | |
b5d76df4 | 1652 | break; |
e13f1c14 | 1653 | } |
e52201b6 RG |
1654 | /* We can't possibly insert these. */ |
1655 | else if (op2 && !is_gimple_min_invariant (op2)) | |
1656 | break; | |
c9145754 DB |
1657 | changed |= op2 != oldop2; |
1658 | ||
1659 | if (!newoperands) | |
1660 | newoperands = VEC_copy (vn_reference_op_s, heap, operands); | |
1661 | /* We may have changed from an SSA_NAME to a constant */ | |
1662 | if (newop.opcode == SSA_NAME && TREE_CODE (op0) != SSA_NAME) | |
1663 | newop.opcode = TREE_CODE (op0); | |
1664 | newop.type = type; | |
1665 | newop.op0 = op0; | |
1666 | newop.op1 = op1; | |
1667 | newop.op2 = op2; | |
aa7069aa RG |
1668 | VEC_replace (vn_reference_op_s, newoperands, j, &newop); |
1669 | /* If it transforms from an SSA_NAME to an address, fold with | |
1670 | a preceding indirect reference. */ | |
1671 | if (j > 0 && op0 && TREE_CODE (op0) == ADDR_EXPR | |
1672 | && VEC_index (vn_reference_op_s, | |
1673 | newoperands, j - 1)->opcode == INDIRECT_REF) | |
1674 | vn_reference_fold_indirect (&newoperands, &j); | |
e13f1c14 | 1675 | } |
b5d76df4 RG |
1676 | if (i != VEC_length (vn_reference_op_s, operands)) |
1677 | { | |
1678 | if (newoperands) | |
1679 | VEC_free (vn_reference_op_s, heap, newoperands); | |
1680 | return NULL; | |
1681 | } | |
c90186eb | 1682 | |
5006671f RG |
1683 | if (vuse) |
1684 | { | |
1685 | newvuse = translate_vuse_through_block (newoperands, | |
b45d2719 | 1686 | ref->set, ref->type, |
84280917 MM |
1687 | vuse, phiblock, pred, |
1688 | &same_valid); | |
5006671f RG |
1689 | if (newvuse == NULL_TREE) |
1690 | { | |
1691 | VEC_free (vn_reference_op_s, heap, newoperands); | |
1692 | return NULL; | |
1693 | } | |
1694 | } | |
b9c5e484 | 1695 | |
84280917 | 1696 | if (changed || newvuse != vuse) |
c90186eb | 1697 | { |
47af7a5c RG |
1698 | unsigned int new_val_id; |
1699 | pre_expr constant; | |
1700 | ||
b45d2719 RG |
1701 | tree result = vn_reference_lookup_pieces (newvuse, ref->set, |
1702 | ref->type, | |
c9145754 | 1703 | newoperands, |
53f3815c | 1704 | &newref, true); |
c9145754 DB |
1705 | if (newref) |
1706 | VEC_free (vn_reference_op_s, heap, newoperands); | |
c90186eb | 1707 | |
c9145754 | 1708 | if (result && is_gimple_min_invariant (result)) |
9e504cda JH |
1709 | { |
1710 | gcc_assert (!newoperands); | |
1711 | return get_or_alloc_expr_for_constant (result); | |
1712 | } | |
c90186eb | 1713 | |
c9145754 DB |
1714 | expr = (pre_expr) pool_alloc (pre_expr_pool); |
1715 | expr->kind = REFERENCE; | |
1716 | expr->id = 0; | |
6615c446 | 1717 | |
c9145754 | 1718 | if (newref) |
0995a441 | 1719 | { |
c9145754 | 1720 | PRE_EXPR_REFERENCE (expr) = newref; |
47af7a5c RG |
1721 | constant = fully_constant_expression (expr); |
1722 | if (constant != expr) | |
1723 | return constant; | |
1724 | ||
c9145754 DB |
1725 | new_val_id = newref->value_id; |
1726 | get_or_alloc_expression_id (expr); | |
0995a441 SB |
1727 | } |
1728 | else | |
1729 | { | |
84280917 MM |
1730 | if (changed || !same_valid) |
1731 | { | |
1732 | new_val_id = get_next_value_id (); | |
1733 | VEC_safe_grow_cleared (bitmap_set_t, heap, | |
1734 | value_expressions, | |
1735 | get_max_value_id() + 1); | |
1736 | } | |
1737 | else | |
1738 | new_val_id = ref->value_id; | |
b45d2719 RG |
1739 | newref = vn_reference_insert_pieces (newvuse, ref->set, |
1740 | ref->type, | |
c9145754 DB |
1741 | newoperands, |
1742 | result, new_val_id); | |
9e504cda | 1743 | newoperands = NULL; |
c9145754 | 1744 | PRE_EXPR_REFERENCE (expr) = newref; |
47af7a5c RG |
1745 | constant = fully_constant_expression (expr); |
1746 | if (constant != expr) | |
1747 | return constant; | |
c9145754 | 1748 | get_or_alloc_expression_id (expr); |
0995a441 | 1749 | } |
b0a0ab2d | 1750 | add_to_value (new_val_id, expr); |
7e6eb623 | 1751 | } |
9e504cda | 1752 | VEC_free (vn_reference_op_s, heap, newoperands); |
c9145754 | 1753 | return expr; |
7e6eb623 | 1754 | } |
c9145754 | 1755 | break; |
47af7a5c | 1756 | |
c9145754 | 1757 | case NAME: |
7e6eb623 | 1758 | { |
726a989a | 1759 | gimple phi = NULL; |
9323afae | 1760 | edge e; |
726a989a | 1761 | gimple def_stmt; |
c9145754 | 1762 | tree name = PRE_EXPR_NAME (expr); |
d75dbccd | 1763 | |
c9145754 | 1764 | def_stmt = SSA_NAME_DEF_STMT (name); |
726a989a RB |
1765 | if (gimple_code (def_stmt) == GIMPLE_PHI |
1766 | && gimple_bb (def_stmt) == phiblock) | |
d75dbccd | 1767 | phi = def_stmt; |
7e6eb623 DB |
1768 | else |
1769 | return expr; | |
b9c5e484 | 1770 | |
726a989a | 1771 | e = find_edge (pred, gimple_bb (phi)); |
9323afae KH |
1772 | if (e) |
1773 | { | |
89fb70a3 | 1774 | tree def = PHI_ARG_DEF (phi, e->dest_idx); |
c9145754 | 1775 | pre_expr newexpr; |
070b797d | 1776 | |
73a63870 RG |
1777 | if (TREE_CODE (def) == SSA_NAME) |
1778 | def = VN_INFO (def)->valnum; | |
1779 | ||
c9145754 | 1780 | /* Handle constant. */ |
89fb70a3 | 1781 | if (is_gimple_min_invariant (def)) |
c9145754 | 1782 | return get_or_alloc_expr_for_constant (def); |
070b797d | 1783 | |
7b7e6ecd | 1784 | if (TREE_CODE (def) == SSA_NAME && ssa_undefined_value_p (def)) |
9323afae | 1785 | return NULL; |
070b797d | 1786 | |
c9145754 DB |
1787 | newexpr = get_or_alloc_expr_for_name (def); |
1788 | return newexpr; | |
9323afae | 1789 | } |
7e6eb623 | 1790 | } |
6615c446 JO |
1791 | return expr; |
1792 | ||
1793 | default: | |
1794 | gcc_unreachable (); | |
6de9cd9a DN |
1795 | } |
1796 | } | |
f8b04195 | 1797 | |
3e999e7b RG |
1798 | /* Wrapper around phi_translate_1 providing caching functionality. */ |
1799 | ||
1800 | static pre_expr | |
1801 | phi_translate (pre_expr expr, bitmap_set_t set1, bitmap_set_t set2, | |
1802 | basic_block pred, basic_block phiblock) | |
1803 | { | |
1804 | pre_expr phitrans; | |
1805 | ||
1806 | if (!expr) | |
1807 | return NULL; | |
1808 | ||
1809 | /* Constants contain no values that need translation. */ | |
1810 | if (expr->kind == CONSTANT) | |
1811 | return expr; | |
1812 | ||
1813 | if (value_id_constant_p (get_expr_value_id (expr))) | |
1814 | return expr; | |
1815 | ||
1816 | if (expr->kind != NAME) | |
1817 | { | |
1818 | phitrans = phi_trans_lookup (expr, pred); | |
1819 | if (phitrans) | |
1820 | return phitrans; | |
1821 | } | |
1822 | ||
1823 | /* Translate. */ | |
1824 | phitrans = phi_translate_1 (expr, set1, set2, pred, phiblock); | |
1825 | ||
1826 | /* Don't add empty translations to the cache. Neither add | |
1827 | translations of NAMEs as those are cheap to translate. */ | |
1828 | if (phitrans | |
1829 | && expr->kind != NAME) | |
1830 | phi_trans_add (expr, phitrans, pred); | |
1831 | ||
1832 | return phitrans; | |
1833 | } | |
1834 | ||
1835 | ||
c9145754 | 1836 | /* For each expression in SET, translate the values through phi nodes |
f5594471 DB |
1837 | in PHIBLOCK using edge PHIBLOCK->PRED, and store the resulting |
1838 | expressions in DEST. */ | |
1839 | ||
6de9cd9a | 1840 | static void |
83737db2 | 1841 | phi_translate_set (bitmap_set_t dest, bitmap_set_t set, basic_block pred, |
7e6eb623 | 1842 | basic_block phiblock) |
6de9cd9a | 1843 | { |
c9145754 DB |
1844 | VEC (pre_expr, heap) *exprs; |
1845 | pre_expr expr; | |
83737db2 DB |
1846 | int i; |
1847 | ||
9adf0570 | 1848 | if (gimple_seq_empty_p (phi_nodes (phiblock))) |
6de9cd9a | 1849 | { |
83737db2 DB |
1850 | bitmap_set_copy (dest, set); |
1851 | return; | |
1852 | } | |
b9c5e484 | 1853 | |
83737db2 | 1854 | exprs = sorted_array_from_bitmap_set (set); |
c9145754 | 1855 | for (i = 0; VEC_iterate (pre_expr, exprs, i, expr); i++) |
83737db2 | 1856 | { |
c9145754 | 1857 | pre_expr translated; |
f8b04195 | 1858 | translated = phi_translate (expr, set, NULL, pred, phiblock); |
3ed7d068 RG |
1859 | if (!translated) |
1860 | continue; | |
c90186eb | 1861 | |
3ed7d068 RG |
1862 | /* We might end up with multiple expressions from SET being |
1863 | translated to the same value. In this case we do not want | |
1864 | to retain the NARY or REFERENCE expression but prefer a NAME | |
1865 | which would be the leader. */ | |
1866 | if (translated->kind == NAME) | |
1867 | bitmap_value_replace_in_set (dest, translated); | |
1868 | else | |
83737db2 | 1869 | bitmap_value_insert_into_set (dest, translated); |
b9c5e484 | 1870 | } |
c9145754 | 1871 | VEC_free (pre_expr, heap, exprs); |
6de9cd9a DN |
1872 | } |
1873 | ||
bdee7684 | 1874 | /* Find the leader for a value (i.e., the name representing that |
3d45dd59 RG |
1875 | value) in a given set, and return it. If STMT is non-NULL it |
1876 | makes sure the defining statement for the leader dominates it. | |
1877 | Return NULL if no leader is found. */ | |
bdee7684 | 1878 | |
c9145754 | 1879 | static pre_expr |
726a989a | 1880 | bitmap_find_leader (bitmap_set_t set, unsigned int val, gimple stmt) |
bdee7684 | 1881 | { |
c9145754 DB |
1882 | if (value_id_constant_p (val)) |
1883 | { | |
1884 | unsigned int i; | |
1885 | bitmap_iterator bi; | |
1886 | bitmap_set_t exprset = VEC_index (bitmap_set_t, value_expressions, val); | |
83737db2 | 1887 | |
c9145754 DB |
1888 | FOR_EACH_EXPR_ID_IN_SET (exprset, i, bi) |
1889 | { | |
1890 | pre_expr expr = expression_for_id (i); | |
1891 | if (expr->kind == CONSTANT) | |
1892 | return expr; | |
1893 | } | |
1894 | } | |
bdee7684 DB |
1895 | if (bitmap_set_contains_value (set, val)) |
1896 | { | |
6b416da1 DB |
1897 | /* Rather than walk the entire bitmap of expressions, and see |
1898 | whether any of them has the value we are looking for, we look | |
1899 | at the reverse mapping, which tells us the set of expressions | |
1900 | that have a given value (IE value->expressions with that | |
1901 | value) and see if any of those expressions are in our set. | |
1902 | The number of expressions per value is usually significantly | |
1903 | less than the number of expressions in the set. In fact, for | |
1904 | large testcases, doing it this way is roughly 5-10x faster | |
1905 | than walking the bitmap. | |
1906 | If this is somehow a significant lose for some cases, we can | |
b9c5e484 | 1907 | choose which set to walk based on which set is smaller. */ |
83737db2 DB |
1908 | unsigned int i; |
1909 | bitmap_iterator bi; | |
c9145754 | 1910 | bitmap_set_t exprset = VEC_index (bitmap_set_t, value_expressions, val); |
b9c5e484 | 1911 | |
83737db2 DB |
1912 | EXECUTE_IF_AND_IN_BITMAP (exprset->expressions, |
1913 | set->expressions, 0, i, bi) | |
3d45dd59 | 1914 | { |
c9145754 DB |
1915 | pre_expr val = expression_for_id (i); |
1916 | /* At the point where stmt is not null, there should always | |
1917 | be an SSA_NAME first in the list of expressions. */ | |
3d45dd59 RG |
1918 | if (stmt) |
1919 | { | |
726a989a RB |
1920 | gimple def_stmt = SSA_NAME_DEF_STMT (PRE_EXPR_NAME (val)); |
1921 | if (gimple_code (def_stmt) != GIMPLE_PHI | |
1922 | && gimple_bb (def_stmt) == gimple_bb (stmt) | |
1923 | && gimple_uid (def_stmt) >= gimple_uid (stmt)) | |
3d45dd59 RG |
1924 | continue; |
1925 | } | |
1926 | return val; | |
1927 | } | |
6de9cd9a | 1928 | } |
7e6eb623 | 1929 | return NULL; |
6de9cd9a DN |
1930 | } |
1931 | ||
cea618ac | 1932 | /* Determine if EXPR, a memory expression, is ANTIC_IN at the top of |
1e4816bc DB |
1933 | BLOCK by seeing if it is not killed in the block. Note that we are |
1934 | only determining whether there is a store that kills it. Because | |
1935 | of the order in which clean iterates over values, we are guaranteed | |
1936 | that altered operands will have caused us to be eliminated from the | |
1937 | ANTIC_IN set already. */ | |
c90186eb DB |
1938 | |
1939 | static bool | |
c9145754 | 1940 | value_dies_in_block_x (pre_expr expr, basic_block block) |
c90186eb | 1941 | { |
5006671f RG |
1942 | tree vuse = PRE_EXPR_REFERENCE (expr)->vuse; |
1943 | vn_reference_t refx = PRE_EXPR_REFERENCE (expr); | |
1944 | gimple def; | |
5006671f RG |
1945 | gimple_stmt_iterator gsi; |
1946 | unsigned id = get_expression_id (expr); | |
1947 | bool res = false; | |
b45d2719 | 1948 | ao_ref ref; |
89fb70a3 | 1949 | |
5006671f RG |
1950 | if (!vuse) |
1951 | return false; | |
1952 | ||
1953 | /* Lookup a previously calculated result. */ | |
1954 | if (EXPR_DIES (block) | |
1955 | && bitmap_bit_p (EXPR_DIES (block), id * 2)) | |
1956 | return bitmap_bit_p (EXPR_DIES (block), id * 2 + 1); | |
1957 | ||
1958 | /* A memory expression {e, VUSE} dies in the block if there is a | |
1959 | statement that may clobber e. If, starting statement walk from the | |
1960 | top of the basic block, a statement uses VUSE there can be no kill | |
1961 | inbetween that use and the original statement that loaded {e, VUSE}, | |
1962 | so we can stop walking. */ | |
b45d2719 | 1963 | ref.base = NULL_TREE; |
5006671f | 1964 | for (gsi = gsi_start_bb (block); !gsi_end_p (gsi); gsi_next (&gsi)) |
c90186eb | 1965 | { |
5006671f RG |
1966 | tree def_vuse, def_vdef; |
1967 | def = gsi_stmt (gsi); | |
1968 | def_vuse = gimple_vuse (def); | |
1969 | def_vdef = gimple_vdef (def); | |
89fb70a3 | 1970 | |
5006671f RG |
1971 | /* Not a memory statement. */ |
1972 | if (!def_vuse) | |
1e4816bc | 1973 | continue; |
5006671f RG |
1974 | |
1975 | /* Not a may-def. */ | |
1976 | if (!def_vdef) | |
1977 | { | |
1978 | /* A load with the same VUSE, we're done. */ | |
1979 | if (def_vuse == vuse) | |
1980 | break; | |
1981 | ||
1982 | continue; | |
1983 | } | |
1984 | ||
1985 | /* Init ref only if we really need it. */ | |
b45d2719 RG |
1986 | if (ref.base == NULL_TREE |
1987 | && !ao_ref_init_from_vn_reference (&ref, refx->set, refx->type, | |
1988 | refx->operands)) | |
5006671f | 1989 | { |
b45d2719 RG |
1990 | res = true; |
1991 | break; | |
5006671f RG |
1992 | } |
1993 | /* If the statement may clobber expr, it dies. */ | |
b45d2719 | 1994 | if (stmt_may_clobber_ref_p_1 (def, &ref)) |
5006671f RG |
1995 | { |
1996 | res = true; | |
1997 | break; | |
1998 | } | |
c90186eb | 1999 | } |
5006671f RG |
2000 | |
2001 | /* Remember the result. */ | |
2002 | if (!EXPR_DIES (block)) | |
2003 | EXPR_DIES (block) = BITMAP_ALLOC (&grand_bitmap_obstack); | |
2004 | bitmap_set_bit (EXPR_DIES (block), id * 2); | |
2005 | if (res) | |
2006 | bitmap_set_bit (EXPR_DIES (block), id * 2 + 1); | |
2007 | ||
2008 | return res; | |
c90186eb DB |
2009 | } |
2010 | ||
6de9cd9a | 2011 | |
83737db2 DB |
2012 | #define union_contains_value(SET1, SET2, VAL) \ |
2013 | (bitmap_set_contains_value ((SET1), (VAL)) \ | |
2014 | || ((SET2) && bitmap_set_contains_value ((SET2), (VAL)))) | |
2015 | ||
c9145754 DB |
2016 | /* Determine if vn_reference_op_t VRO is legal in SET1 U SET2. |
2017 | */ | |
6de9cd9a | 2018 | static bool |
c9145754 DB |
2019 | vro_valid_in_sets (bitmap_set_t set1, bitmap_set_t set2, |
2020 | vn_reference_op_t vro) | |
6de9cd9a | 2021 | { |
c9145754 | 2022 | if (vro->op0 && TREE_CODE (vro->op0) == SSA_NAME) |
7e6eb623 | 2023 | { |
c9145754 DB |
2024 | struct pre_expr_d temp; |
2025 | temp.kind = NAME; | |
2026 | temp.id = 0; | |
2027 | PRE_EXPR_NAME (&temp) = vro->op0; | |
2028 | temp.id = lookup_expression_id (&temp); | |
2029 | if (temp.id == 0) | |
2030 | return false; | |
2031 | if (!union_contains_value (set1, set2, | |
2032 | get_expr_value_id (&temp))) | |
2033 | return false; | |
2034 | } | |
2035 | if (vro->op1 && TREE_CODE (vro->op1) == SSA_NAME) | |
2036 | { | |
2037 | struct pre_expr_d temp; | |
2038 | temp.kind = NAME; | |
2039 | temp.id = 0; | |
2040 | PRE_EXPR_NAME (&temp) = vro->op1; | |
2041 | temp.id = lookup_expression_id (&temp); | |
2042 | if (temp.id == 0) | |
2043 | return false; | |
2044 | if (!union_contains_value (set1, set2, | |
2045 | get_expr_value_id (&temp))) | |
2046 | return false; | |
2047 | } | |
83737db2 | 2048 | |
c9145754 DB |
2049 | if (vro->op2 && TREE_CODE (vro->op2) == SSA_NAME) |
2050 | { | |
2051 | struct pre_expr_d temp; | |
2052 | temp.kind = NAME; | |
2053 | temp.id = 0; | |
2054 | PRE_EXPR_NAME (&temp) = vro->op2; | |
2055 | temp.id = lookup_expression_id (&temp); | |
2056 | if (temp.id == 0) | |
2057 | return false; | |
2058 | if (!union_contains_value (set1, set2, | |
2059 | get_expr_value_id (&temp))) | |
2060 | return false; | |
2061 | } | |
6615c446 | 2062 | |
c9145754 DB |
2063 | return true; |
2064 | } | |
b9c5e484 | 2065 | |
c9145754 DB |
2066 | /* Determine if the expression EXPR is valid in SET1 U SET2. |
2067 | ONLY SET2 CAN BE NULL. | |
2068 | This means that we have a leader for each part of the expression | |
2069 | (if it consists of values), or the expression is an SSA_NAME. | |
7763473e | 2070 | For loads/calls, we also see if the vuse is killed in this block. */ |
5039610b | 2071 | |
c9145754 DB |
2072 | static bool |
2073 | valid_in_sets (bitmap_set_t set1, bitmap_set_t set2, pre_expr expr, | |
2074 | basic_block block) | |
2075 | { | |
2076 | switch (expr->kind) | |
2077 | { | |
2078 | case NAME: | |
2079 | return bitmap_set_contains_expr (AVAIL_OUT (block), expr); | |
2080 | case NARY: | |
43da81be | 2081 | { |
c9145754 DB |
2082 | unsigned int i; |
2083 | vn_nary_op_t nary = PRE_EXPR_NARY (expr); | |
2084 | for (i = 0; i < nary->length; i++) | |
43da81be | 2085 | { |
c9145754 | 2086 | if (TREE_CODE (nary->op[i]) == SSA_NAME) |
43da81be | 2087 | { |
c9145754 DB |
2088 | struct pre_expr_d temp; |
2089 | temp.kind = NAME; | |
2090 | temp.id = 0; | |
2091 | PRE_EXPR_NAME (&temp) = nary->op[i]; | |
2092 | temp.id = lookup_expression_id (&temp); | |
2093 | if (temp.id == 0) | |
2094 | return false; | |
2095 | if (!union_contains_value (set1, set2, | |
2096 | get_expr_value_id (&temp))) | |
43da81be DB |
2097 | return false; |
2098 | } | |
43da81be | 2099 | } |
a19eb9d2 RG |
2100 | /* If the NARY may trap make sure the block does not contain |
2101 | a possible exit point. | |
2102 | ??? This is overly conservative if we translate AVAIL_OUT | |
2103 | as the available expression might be after the exit point. */ | |
2104 | if (BB_MAY_NOTRETURN (block) | |
2105 | && vn_nary_may_trap (nary)) | |
2106 | return false; | |
c9145754 | 2107 | return true; |
43da81be | 2108 | } |
c9145754 DB |
2109 | break; |
2110 | case REFERENCE: | |
c90186eb | 2111 | { |
c9145754 DB |
2112 | vn_reference_t ref = PRE_EXPR_REFERENCE (expr); |
2113 | vn_reference_op_t vro; | |
2114 | unsigned int i; | |
2115 | ||
2116 | for (i = 0; VEC_iterate (vn_reference_op_s, ref->operands, i, vro); i++) | |
c90186eb | 2117 | { |
c9145754 | 2118 | if (!vro_valid_in_sets (set1, set2, vro)) |
e13f1c14 | 2119 | return false; |
c90186eb | 2120 | } |
5006671f RG |
2121 | if (ref->vuse) |
2122 | { | |
2123 | gimple def_stmt = SSA_NAME_DEF_STMT (ref->vuse); | |
2124 | if (!gimple_nop_p (def_stmt) | |
2125 | && gimple_bb (def_stmt) != block | |
2126 | && !dominated_by_p (CDI_DOMINATORS, | |
2127 | block, gimple_bb (def_stmt))) | |
2128 | return false; | |
2129 | } | |
c9145754 | 2130 | return !value_dies_in_block_x (expr, block); |
c90186eb | 2131 | } |
6615c446 | 2132 | default: |
b9c5e484 | 2133 | gcc_unreachable (); |
c9145754 | 2134 | } |
6de9cd9a DN |
2135 | } |
2136 | ||
d75dbccd DB |
2137 | /* Clean the set of expressions that are no longer valid in SET1 or |
2138 | SET2. This means expressions that are made up of values we have no | |
2139 | leaders for in SET1 or SET2. This version is used for partial | |
2140 | anticipation, which means it is not valid in either ANTIC_IN or | |
2141 | PA_IN. */ | |
2142 | ||
2143 | static void | |
2144 | dependent_clean (bitmap_set_t set1, bitmap_set_t set2, basic_block block) | |
2145 | { | |
c9145754 DB |
2146 | VEC (pre_expr, heap) *exprs = sorted_array_from_bitmap_set (set1); |
2147 | pre_expr expr; | |
d75dbccd DB |
2148 | int i; |
2149 | ||
c9145754 | 2150 | for (i = 0; VEC_iterate (pre_expr, exprs, i, expr); i++) |
d75dbccd DB |
2151 | { |
2152 | if (!valid_in_sets (set1, set2, expr, block)) | |
2153 | bitmap_remove_from_set (set1, expr); | |
2154 | } | |
c9145754 | 2155 | VEC_free (pre_expr, heap, exprs); |
d75dbccd DB |
2156 | } |
2157 | ||
ca072a31 DB |
2158 | /* Clean the set of expressions that are no longer valid in SET. This |
2159 | means expressions that are made up of values we have no leaders for | |
2160 | in SET. */ | |
6de9cd9a DN |
2161 | |
2162 | static void | |
83737db2 | 2163 | clean (bitmap_set_t set, basic_block block) |
6de9cd9a | 2164 | { |
c9145754 DB |
2165 | VEC (pre_expr, heap) *exprs = sorted_array_from_bitmap_set (set); |
2166 | pre_expr expr; | |
83737db2 DB |
2167 | int i; |
2168 | ||
c9145754 | 2169 | for (i = 0; VEC_iterate (pre_expr, exprs, i, expr); i++) |
6de9cd9a | 2170 | { |
83737db2 DB |
2171 | if (!valid_in_sets (set, NULL, expr, block)) |
2172 | bitmap_remove_from_set (set, expr); | |
6de9cd9a | 2173 | } |
c9145754 | 2174 | VEC_free (pre_expr, heap, exprs); |
6de9cd9a DN |
2175 | } |
2176 | ||
d4222d43 | 2177 | static sbitmap has_abnormal_preds; |
89fb70a3 | 2178 | |
83737db2 DB |
2179 | /* List of blocks that may have changed during ANTIC computation and |
2180 | thus need to be iterated over. */ | |
2181 | ||
2182 | static sbitmap changed_blocks; | |
1e4816bc DB |
2183 | |
2184 | /* Decide whether to defer a block for a later iteration, or PHI | |
2185 | translate SOURCE to DEST using phis in PHIBLOCK. Return false if we | |
2186 | should defer the block, and true if we processed it. */ | |
2187 | ||
2188 | static bool | |
2189 | defer_or_phi_translate_block (bitmap_set_t dest, bitmap_set_t source, | |
2190 | basic_block block, basic_block phiblock) | |
2191 | { | |
2192 | if (!BB_VISITED (phiblock)) | |
2193 | { | |
2194 | SET_BIT (changed_blocks, block->index); | |
2195 | BB_VISITED (block) = 0; | |
2196 | BB_DEFERRED (block) = 1; | |
2197 | return false; | |
2198 | } | |
2199 | else | |
2200 | phi_translate_set (dest, source, block, phiblock); | |
2201 | return true; | |
2202 | } | |
2203 | ||
7e6eb623 | 2204 | /* Compute the ANTIC set for BLOCK. |
6de9cd9a | 2205 | |
665fcad8 SB |
2206 | If succs(BLOCK) > 1 then |
2207 | ANTIC_OUT[BLOCK] = intersection of ANTIC_IN[b] for all succ(BLOCK) | |
2208 | else if succs(BLOCK) == 1 then | |
2209 | ANTIC_OUT[BLOCK] = phi_translate (ANTIC_IN[succ(BLOCK)]) | |
6de9cd9a | 2210 | |
665fcad8 | 2211 | ANTIC_IN[BLOCK] = clean(ANTIC_OUT[BLOCK] U EXP_GEN[BLOCK] - TMP_GEN[BLOCK]) |
83737db2 | 2212 | */ |
6de9cd9a | 2213 | |
7e6eb623 | 2214 | static bool |
a28fee03 | 2215 | compute_antic_aux (basic_block block, bool block_has_abnormal_pred_edge) |
6de9cd9a | 2216 | { |
7e6eb623 | 2217 | bool changed = false; |
83737db2 DB |
2218 | bitmap_set_t S, old, ANTIC_OUT; |
2219 | bitmap_iterator bi; | |
2220 | unsigned int bii; | |
2221 | edge e; | |
2222 | edge_iterator ei; | |
a28fee03 | 2223 | |
83737db2 | 2224 | old = ANTIC_OUT = S = NULL; |
d75dbccd | 2225 | BB_VISITED (block) = 1; |
a28fee03 SB |
2226 | |
2227 | /* If any edges from predecessors are abnormal, antic_in is empty, | |
2228 | so do nothing. */ | |
2229 | if (block_has_abnormal_pred_edge) | |
2230 | goto maybe_dump_sets; | |
6de9cd9a | 2231 | |
83737db2 DB |
2232 | old = ANTIC_IN (block); |
2233 | ANTIC_OUT = bitmap_set_new (); | |
6de9cd9a | 2234 | |
a28fee03 SB |
2235 | /* If the block has no successors, ANTIC_OUT is empty. */ |
2236 | if (EDGE_COUNT (block->succs) == 0) | |
2237 | ; | |
7e6eb623 DB |
2238 | /* If we have one successor, we could have some phi nodes to |
2239 | translate through. */ | |
c5cbcccf | 2240 | else if (single_succ_p (block)) |
6de9cd9a | 2241 | { |
83737db2 | 2242 | basic_block succ_bb = single_succ (block); |
d75dbccd DB |
2243 | |
2244 | /* We trade iterations of the dataflow equations for having to | |
2245 | phi translate the maximal set, which is incredibly slow | |
2246 | (since the maximal set often has 300+ members, even when you | |
2247 | have a small number of blocks). | |
2248 | Basically, we defer the computation of ANTIC for this block | |
2f8e468b | 2249 | until we have processed it's successor, which will inevitably |
d75dbccd DB |
2250 | have a *much* smaller set of values to phi translate once |
2251 | clean has been run on it. | |
2252 | The cost of doing this is that we technically perform more | |
2253 | iterations, however, they are lower cost iterations. | |
2254 | ||
2255 | Timings for PRE on tramp3d-v4: | |
2256 | without maximal set fix: 11 seconds | |
2257 | with maximal set fix/without deferring: 26 seconds | |
2258 | with maximal set fix/with deferring: 11 seconds | |
2259 | */ | |
2260 | ||
1e4816bc DB |
2261 | if (!defer_or_phi_translate_block (ANTIC_OUT, ANTIC_IN (succ_bb), |
2262 | block, succ_bb)) | |
d75dbccd DB |
2263 | { |
2264 | changed = true; | |
d75dbccd DB |
2265 | goto maybe_dump_sets; |
2266 | } | |
6de9cd9a | 2267 | } |
7e6eb623 | 2268 | /* If we have multiple successors, we take the intersection of all of |
1e4816bc DB |
2269 | them. Note that in the case of loop exit phi nodes, we may have |
2270 | phis to translate through. */ | |
7e6eb623 | 2271 | else |
6de9cd9a | 2272 | { |
d4e6fecb | 2273 | VEC(basic_block, heap) * worklist; |
7e6eb623 | 2274 | size_t i; |
70a6b17e | 2275 | basic_block bprime, first = NULL; |
7e6eb623 | 2276 | |
d4e6fecb | 2277 | worklist = VEC_alloc (basic_block, heap, EDGE_COUNT (block->succs)); |
628f6a4e | 2278 | FOR_EACH_EDGE (e, ei, block->succs) |
1e4816bc | 2279 | { |
70a6b17e RG |
2280 | if (!first |
2281 | && BB_VISITED (e->dest)) | |
2282 | first = e->dest; | |
2283 | else if (BB_VISITED (e->dest)) | |
2284 | VEC_quick_push (basic_block, worklist, e->dest); | |
1e4816bc | 2285 | } |
70a6b17e RG |
2286 | |
2287 | /* Of multiple successors we have to have visited one already. */ | |
2288 | if (!first) | |
1e4816bc | 2289 | { |
70a6b17e RG |
2290 | SET_BIT (changed_blocks, block->index); |
2291 | BB_VISITED (block) = 0; | |
2292 | BB_DEFERRED (block) = 1; | |
2293 | changed = true; | |
2294 | VEC_free (basic_block, heap, worklist); | |
2295 | goto maybe_dump_sets; | |
1e4816bc | 2296 | } |
c90186eb | 2297 | |
9adf0570 | 2298 | if (!gimple_seq_empty_p (phi_nodes (first))) |
70a6b17e RG |
2299 | phi_translate_set (ANTIC_OUT, ANTIC_IN (first), block, first); |
2300 | else | |
2301 | bitmap_set_copy (ANTIC_OUT, ANTIC_IN (first)); | |
2302 | ||
2303 | for (i = 0; VEC_iterate (basic_block, worklist, i, bprime); i++) | |
d75dbccd | 2304 | { |
9adf0570 | 2305 | if (!gimple_seq_empty_p (phi_nodes (bprime))) |
1e4816bc DB |
2306 | { |
2307 | bitmap_set_t tmp = bitmap_set_new (); | |
70a6b17e | 2308 | phi_translate_set (tmp, ANTIC_IN (bprime), block, bprime); |
1e4816bc DB |
2309 | bitmap_set_and (ANTIC_OUT, tmp); |
2310 | bitmap_set_free (tmp); | |
2311 | } | |
89fb70a3 | 2312 | else |
70a6b17e | 2313 | bitmap_set_and (ANTIC_OUT, ANTIC_IN (bprime)); |
6de9cd9a | 2314 | } |
d75dbccd | 2315 | VEC_free (basic_block, heap, worklist); |
6de9cd9a | 2316 | } |
6de9cd9a | 2317 | |
ea4b7848 | 2318 | /* Generate ANTIC_OUT - TMP_GEN. */ |
83737db2 | 2319 | S = bitmap_set_subtract (ANTIC_OUT, TMP_GEN (block)); |
6de9cd9a | 2320 | |
d75dbccd | 2321 | /* Start ANTIC_IN with EXP_GEN - TMP_GEN. */ |
83737db2 DB |
2322 | ANTIC_IN (block) = bitmap_set_subtract (EXP_GEN (block), |
2323 | TMP_GEN (block)); | |
c33bae88 | 2324 | |
a28fee03 SB |
2325 | /* Then union in the ANTIC_OUT - TMP_GEN values, |
2326 | to get ANTIC_OUT U EXP_GEN - TMP_GEN */ | |
83737db2 DB |
2327 | FOR_EACH_EXPR_ID_IN_SET (S, bii, bi) |
2328 | bitmap_value_insert_into_set (ANTIC_IN (block), | |
2329 | expression_for_id (bii)); | |
6de9cd9a | 2330 | |
c90186eb | 2331 | clean (ANTIC_IN (block), block); |
d75dbccd DB |
2332 | |
2333 | /* !old->expressions can happen when we deferred a block. */ | |
2334 | if (!old->expressions || !bitmap_set_equal (old, ANTIC_IN (block))) | |
83737db2 DB |
2335 | { |
2336 | changed = true; | |
2337 | SET_BIT (changed_blocks, block->index); | |
2338 | FOR_EACH_EDGE (e, ei, block->preds) | |
2339 | SET_BIT (changed_blocks, e->src->index); | |
2340 | } | |
2341 | else | |
2342 | RESET_BIT (changed_blocks, block->index); | |
6de9cd9a | 2343 | |
a28fee03 | 2344 | maybe_dump_sets: |
7e6eb623 DB |
2345 | if (dump_file && (dump_flags & TDF_DETAILS)) |
2346 | { | |
d75dbccd DB |
2347 | if (!BB_DEFERRED (block) || BB_VISITED (block)) |
2348 | { | |
2349 | if (ANTIC_OUT) | |
2350 | print_bitmap_set (dump_file, ANTIC_OUT, "ANTIC_OUT", block->index); | |
85300b46 | 2351 | |
d75dbccd DB |
2352 | print_bitmap_set (dump_file, ANTIC_IN (block), "ANTIC_IN", |
2353 | block->index); | |
85300b46 | 2354 | |
d75dbccd DB |
2355 | if (S) |
2356 | print_bitmap_set (dump_file, S, "S", block->index); | |
2357 | } | |
2358 | else | |
2359 | { | |
2360 | fprintf (dump_file, | |
2361 | "Block %d was deferred for a future iteration.\n", | |
2362 | block->index); | |
2363 | } | |
83737db2 DB |
2364 | } |
2365 | if (old) | |
2366 | bitmap_set_free (old); | |
2367 | if (S) | |
2368 | bitmap_set_free (S); | |
2369 | if (ANTIC_OUT) | |
2370 | bitmap_set_free (ANTIC_OUT); | |
7e6eb623 | 2371 | return changed; |
6de9cd9a DN |
2372 | } |
2373 | ||
d75dbccd DB |
2374 | /* Compute PARTIAL_ANTIC for BLOCK. |
2375 | ||
2376 | If succs(BLOCK) > 1 then | |
2377 | PA_OUT[BLOCK] = value wise union of PA_IN[b] + all ANTIC_IN not | |
2378 | in ANTIC_OUT for all succ(BLOCK) | |
2379 | else if succs(BLOCK) == 1 then | |
2380 | PA_OUT[BLOCK] = phi_translate (PA_IN[succ(BLOCK)]) | |
2381 | ||
2382 | PA_IN[BLOCK] = dependent_clean(PA_OUT[BLOCK] - TMP_GEN[BLOCK] | |
2383 | - ANTIC_IN[BLOCK]) | |
2384 | ||
2385 | */ | |
2386 | static bool | |
2387 | compute_partial_antic_aux (basic_block block, | |
2388 | bool block_has_abnormal_pred_edge) | |
2389 | { | |
2390 | bool changed = false; | |
2391 | bitmap_set_t old_PA_IN; | |
2392 | bitmap_set_t PA_OUT; | |
2393 | edge e; | |
2394 | edge_iterator ei; | |
f0ed4cfb | 2395 | unsigned long max_pa = PARAM_VALUE (PARAM_MAX_PARTIAL_ANTIC_LENGTH); |
d75dbccd DB |
2396 | |
2397 | old_PA_IN = PA_OUT = NULL; | |
2398 | ||
2399 | /* If any edges from predecessors are abnormal, antic_in is empty, | |
2400 | so do nothing. */ | |
2401 | if (block_has_abnormal_pred_edge) | |
2402 | goto maybe_dump_sets; | |
2403 | ||
f0ed4cfb NC |
2404 | /* If there are too many partially anticipatable values in the |
2405 | block, phi_translate_set can take an exponential time: stop | |
2406 | before the translation starts. */ | |
2407 | if (max_pa | |
2408 | && single_succ_p (block) | |
2409 | && bitmap_count_bits (PA_IN (single_succ (block))->values) > max_pa) | |
2410 | goto maybe_dump_sets; | |
2411 | ||
d75dbccd DB |
2412 | old_PA_IN = PA_IN (block); |
2413 | PA_OUT = bitmap_set_new (); | |
2414 | ||
2415 | /* If the block has no successors, ANTIC_OUT is empty. */ | |
2416 | if (EDGE_COUNT (block->succs) == 0) | |
2417 | ; | |
2418 | /* If we have one successor, we could have some phi nodes to | |
2419 | translate through. Note that we can't phi translate across DFS | |
89fb70a3 DB |
2420 | back edges in partial antic, because it uses a union operation on |
2421 | the successors. For recurrences like IV's, we will end up | |
2422 | generating a new value in the set on each go around (i + 3 (VH.1) | |
2423 | VH.1 + 1 (VH.2), VH.2 + 1 (VH.3), etc), forever. */ | |
d75dbccd DB |
2424 | else if (single_succ_p (block)) |
2425 | { | |
2426 | basic_block succ = single_succ (block); | |
2427 | if (!(single_succ_edge (block)->flags & EDGE_DFS_BACK)) | |
2428 | phi_translate_set (PA_OUT, PA_IN (succ), block, succ); | |
2429 | } | |
2430 | /* If we have multiple successors, we take the union of all of | |
2431 | them. */ | |
2432 | else | |
2433 | { | |
2434 | VEC(basic_block, heap) * worklist; | |
2435 | size_t i; | |
2436 | basic_block bprime; | |
2437 | ||
2438 | worklist = VEC_alloc (basic_block, heap, EDGE_COUNT (block->succs)); | |
2439 | FOR_EACH_EDGE (e, ei, block->succs) | |
2440 | { | |
2441 | if (e->flags & EDGE_DFS_BACK) | |
2442 | continue; | |
2443 | VEC_quick_push (basic_block, worklist, e->dest); | |
2444 | } | |
2445 | if (VEC_length (basic_block, worklist) > 0) | |
2446 | { | |
2447 | for (i = 0; VEC_iterate (basic_block, worklist, i, bprime); i++) | |
2448 | { | |
2449 | unsigned int i; | |
2450 | bitmap_iterator bi; | |
2451 | ||
2452 | FOR_EACH_EXPR_ID_IN_SET (ANTIC_IN (bprime), i, bi) | |
2453 | bitmap_value_insert_into_set (PA_OUT, | |
2454 | expression_for_id (i)); | |
9adf0570 | 2455 | if (!gimple_seq_empty_p (phi_nodes (bprime))) |
1e4816bc DB |
2456 | { |
2457 | bitmap_set_t pa_in = bitmap_set_new (); | |
2458 | phi_translate_set (pa_in, PA_IN (bprime), block, bprime); | |
2459 | FOR_EACH_EXPR_ID_IN_SET (pa_in, i, bi) | |
2460 | bitmap_value_insert_into_set (PA_OUT, | |
2461 | expression_for_id (i)); | |
2462 | bitmap_set_free (pa_in); | |
2463 | } | |
2464 | else | |
2465 | FOR_EACH_EXPR_ID_IN_SET (PA_IN (bprime), i, bi) | |
2466 | bitmap_value_insert_into_set (PA_OUT, | |
2467 | expression_for_id (i)); | |
d75dbccd DB |
2468 | } |
2469 | } | |
2470 | VEC_free (basic_block, heap, worklist); | |
2471 | } | |
2472 | ||
2473 | /* PA_IN starts with PA_OUT - TMP_GEN. | |
2474 | Then we subtract things from ANTIC_IN. */ | |
2475 | PA_IN (block) = bitmap_set_subtract (PA_OUT, TMP_GEN (block)); | |
2476 | ||
2477 | /* For partial antic, we want to put back in the phi results, since | |
2478 | we will properly avoid making them partially antic over backedges. */ | |
2479 | bitmap_ior_into (PA_IN (block)->values, PHI_GEN (block)->values); | |
2480 | bitmap_ior_into (PA_IN (block)->expressions, PHI_GEN (block)->expressions); | |
2481 | ||
2482 | /* PA_IN[block] = PA_IN[block] - ANTIC_IN[block] */ | |
2483 | bitmap_set_subtract_values (PA_IN (block), ANTIC_IN (block)); | |
2484 | ||
2485 | dependent_clean (PA_IN (block), ANTIC_IN (block), block); | |
2486 | ||
2487 | if (!bitmap_set_equal (old_PA_IN, PA_IN (block))) | |
2488 | { | |
2489 | changed = true; | |
2490 | SET_BIT (changed_blocks, block->index); | |
2491 | FOR_EACH_EDGE (e, ei, block->preds) | |
2492 | SET_BIT (changed_blocks, e->src->index); | |
2493 | } | |
2494 | else | |
2495 | RESET_BIT (changed_blocks, block->index); | |
2496 | ||
2497 | maybe_dump_sets: | |
2498 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
2499 | { | |
2500 | if (PA_OUT) | |
2501 | print_bitmap_set (dump_file, PA_OUT, "PA_OUT", block->index); | |
2502 | ||
2503 | print_bitmap_set (dump_file, PA_IN (block), "PA_IN", block->index); | |
2504 | } | |
2505 | if (old_PA_IN) | |
2506 | bitmap_set_free (old_PA_IN); | |
2507 | if (PA_OUT) | |
2508 | bitmap_set_free (PA_OUT); | |
2509 | return changed; | |
2510 | } | |
2511 | ||
83737db2 | 2512 | /* Compute ANTIC and partial ANTIC sets. */ |
6de9cd9a DN |
2513 | |
2514 | static void | |
7e6eb623 | 2515 | compute_antic (void) |
6de9cd9a | 2516 | { |
c33bae88 | 2517 | bool changed = true; |
7e6eb623 | 2518 | int num_iterations = 0; |
c33bae88 | 2519 | basic_block block; |
83737db2 | 2520 | int i; |
a28fee03 SB |
2521 | |
2522 | /* If any predecessor edges are abnormal, we punt, so antic_in is empty. | |
2523 | We pre-build the map of blocks with incoming abnormal edges here. */ | |
2524 | has_abnormal_preds = sbitmap_alloc (last_basic_block); | |
2525 | sbitmap_zero (has_abnormal_preds); | |
83737db2 | 2526 | |
a28fee03 | 2527 | FOR_EACH_BB (block) |
7e6eb623 | 2528 | { |
a28fee03 SB |
2529 | edge_iterator ei; |
2530 | edge e; | |
2531 | ||
2532 | FOR_EACH_EDGE (e, ei, block->preds) | |
83737db2 DB |
2533 | { |
2534 | e->flags &= ~EDGE_DFS_BACK; | |
2535 | if (e->flags & EDGE_ABNORMAL) | |
2536 | { | |
2537 | SET_BIT (has_abnormal_preds, block->index); | |
2538 | break; | |
2539 | } | |
2540 | } | |
a28fee03 | 2541 | |
83737db2 | 2542 | BB_VISITED (block) = 0; |
d75dbccd | 2543 | BB_DEFERRED (block) = 0; |
a19eb9d2 | 2544 | |
a28fee03 | 2545 | /* While we are here, give empty ANTIC_IN sets to each block. */ |
83737db2 | 2546 | ANTIC_IN (block) = bitmap_set_new (); |
d75dbccd | 2547 | PA_IN (block) = bitmap_set_new (); |
7e6eb623 | 2548 | } |
83737db2 | 2549 | |
a28fee03 | 2550 | /* At the exit block we anticipate nothing. */ |
83737db2 DB |
2551 | ANTIC_IN (EXIT_BLOCK_PTR) = bitmap_set_new (); |
2552 | BB_VISITED (EXIT_BLOCK_PTR) = 1; | |
d75dbccd | 2553 | PA_IN (EXIT_BLOCK_PTR) = bitmap_set_new (); |
a28fee03 | 2554 | |
83737db2 DB |
2555 | changed_blocks = sbitmap_alloc (last_basic_block + 1); |
2556 | sbitmap_ones (changed_blocks); | |
7e6eb623 DB |
2557 | while (changed) |
2558 | { | |
83737db2 DB |
2559 | if (dump_file && (dump_flags & TDF_DETAILS)) |
2560 | fprintf (dump_file, "Starting iteration %d\n", num_iterations); | |
a28fee03 | 2561 | num_iterations++; |
c33bae88 | 2562 | changed = false; |
9ca87236 | 2563 | for (i = n_basic_blocks - NUM_FIXED_BLOCKS - 1; i >= 0; i--) |
83737db2 DB |
2564 | { |
2565 | if (TEST_BIT (changed_blocks, postorder[i])) | |
2566 | { | |
2567 | basic_block block = BASIC_BLOCK (postorder[i]); | |
2568 | changed |= compute_antic_aux (block, | |
2569 | TEST_BIT (has_abnormal_preds, | |
2570 | block->index)); | |
2571 | } | |
2572 | } | |
53983ae9 | 2573 | #ifdef ENABLE_CHECKING |
d75dbccd | 2574 | /* Theoretically possible, but *highly* unlikely. */ |
53983ae9 JJ |
2575 | gcc_assert (num_iterations < 500); |
2576 | #endif | |
2e24fa83 | 2577 | } |
a28fee03 | 2578 | |
9fe0cb7d RG |
2579 | statistics_histogram_event (cfun, "compute_antic iterations", |
2580 | num_iterations); | |
83737db2 | 2581 | |
d75dbccd DB |
2582 | if (do_partial_partial) |
2583 | { | |
2584 | sbitmap_ones (changed_blocks); | |
2585 | mark_dfs_back_edges (); | |
2586 | num_iterations = 0; | |
2587 | changed = true; | |
2588 | while (changed) | |
2589 | { | |
2590 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
2591 | fprintf (dump_file, "Starting iteration %d\n", num_iterations); | |
2592 | num_iterations++; | |
2593 | changed = false; | |
9ca87236 | 2594 | for (i = n_basic_blocks - NUM_FIXED_BLOCKS - 1 ; i >= 0; i--) |
d75dbccd DB |
2595 | { |
2596 | if (TEST_BIT (changed_blocks, postorder[i])) | |
2597 | { | |
2598 | basic_block block = BASIC_BLOCK (postorder[i]); | |
2599 | changed | |
2600 | |= compute_partial_antic_aux (block, | |
2601 | TEST_BIT (has_abnormal_preds, | |
2602 | block->index)); | |
2603 | } | |
2604 | } | |
53983ae9 | 2605 | #ifdef ENABLE_CHECKING |
d75dbccd | 2606 | /* Theoretically possible, but *highly* unlikely. */ |
53983ae9 JJ |
2607 | gcc_assert (num_iterations < 500); |
2608 | #endif | |
d75dbccd | 2609 | } |
9fe0cb7d RG |
2610 | statistics_histogram_event (cfun, "compute_partial_antic iterations", |
2611 | num_iterations); | |
d75dbccd | 2612 | } |
83737db2 DB |
2613 | sbitmap_free (has_abnormal_preds); |
2614 | sbitmap_free (changed_blocks); | |
6de9cd9a DN |
2615 | } |
2616 | ||
c90186eb DB |
2617 | /* Return true if we can value number the call in STMT. This is true |
2618 | if we have a pure or constant call. */ | |
2619 | ||
2620 | static bool | |
726a989a | 2621 | can_value_number_call (gimple stmt) |
c90186eb | 2622 | { |
726a989a | 2623 | if (gimple_call_flags (stmt) & (ECF_PURE | ECF_CONST)) |
c90186eb DB |
2624 | return true; |
2625 | return false; | |
2626 | } | |
2627 | ||
249eb506 BRF |
2628 | /* Return true if OP is a tree which we can perform PRE on. |
2629 | This may not match the operations we can value number, but in | |
c90186eb DB |
2630 | a perfect world would. */ |
2631 | ||
2632 | static bool | |
2633 | can_PRE_operation (tree op) | |
2634 | { | |
2635 | return UNARY_CLASS_P (op) | |
2636 | || BINARY_CLASS_P (op) | |
2637 | || COMPARISON_CLASS_P (op) | |
2638 | || TREE_CODE (op) == INDIRECT_REF | |
85300b46 | 2639 | || TREE_CODE (op) == COMPONENT_REF |
3d45dd59 | 2640 | || TREE_CODE (op) == VIEW_CONVERT_EXPR |
e13f1c14 AP |
2641 | || TREE_CODE (op) == CALL_EXPR |
2642 | || TREE_CODE (op) == ARRAY_REF; | |
c90186eb DB |
2643 | } |
2644 | ||
2645 | ||
2646 | /* Inserted expressions are placed onto this worklist, which is used | |
2647 | for performing quick dead code elimination of insertions we made | |
2648 | that didn't turn out to be necessary. */ | |
726a989a | 2649 | static VEC(gimple,heap) *inserted_exprs; |
439ef907 | 2650 | static bitmap inserted_phi_names; |
c90186eb DB |
2651 | |
2652 | /* Pool allocated fake store expressions are placed onto this | |
2653 | worklist, which, after performing dead code elimination, is walked | |
2654 | to see which expressions need to be put into GC'able memory */ | |
726a989a | 2655 | static VEC(gimple, heap) *need_creation; |
c90186eb | 2656 | |
ce94d354 | 2657 | /* The actual worker for create_component_ref_by_pieces. */ |
b9c5e484 | 2658 | |
85300b46 | 2659 | static tree |
ce94d354 RG |
2660 | create_component_ref_by_pieces_1 (basic_block block, vn_reference_t ref, |
2661 | unsigned int *operand, gimple_seq *stmts, | |
2662 | gimple domstmt) | |
85300b46 | 2663 | { |
c9145754 | 2664 | vn_reference_op_t currop = VEC_index (vn_reference_op_s, ref->operands, |
ce94d354 | 2665 | *operand); |
c9145754 | 2666 | tree genop; |
ce94d354 | 2667 | ++*operand; |
c9145754 | 2668 | switch (currop->opcode) |
85300b46 | 2669 | { |
c9145754 DB |
2670 | case CALL_EXPR: |
2671 | { | |
7aec7a38 | 2672 | tree folded, sc = currop->op1; |
ce94d354 RG |
2673 | unsigned int nargs = 0; |
2674 | tree *args = XNEWVEC (tree, VEC_length (vn_reference_op_s, | |
2675 | ref->operands) - 1); | |
2676 | while (*operand < VEC_length (vn_reference_op_s, ref->operands)) | |
c9145754 | 2677 | { |
ce94d354 RG |
2678 | args[nargs] = create_component_ref_by_pieces_1 (block, ref, |
2679 | operand, stmts, | |
2680 | domstmt); | |
2681 | nargs++; | |
c9145754 | 2682 | } |
726a989a | 2683 | folded = build_call_array (currop->type, |
ce94d354 RG |
2684 | TREE_CODE (currop->op0) == FUNCTION_DECL |
2685 | ? build_fold_addr_expr (currop->op0) | |
2686 | : currop->op0, | |
726a989a | 2687 | nargs, args); |
c9145754 | 2688 | free (args); |
7aec7a38 EB |
2689 | if (sc) |
2690 | { | |
2691 | pre_expr scexpr = get_or_alloc_expr_for (sc); | |
2692 | sc = find_or_generate_expression (block, scexpr, stmts, domstmt); | |
2693 | if (!sc) | |
2694 | return NULL_TREE; | |
2695 | CALL_EXPR_STATIC_CHAIN (folded) = sc; | |
2696 | } | |
c9145754 DB |
2697 | return folded; |
2698 | } | |
2699 | break; | |
150e3929 RG |
2700 | case TARGET_MEM_REF: |
2701 | { | |
2702 | vn_reference_op_t nextop = VEC_index (vn_reference_op_s, ref->operands, | |
2703 | *operand); | |
2704 | pre_expr op0expr; | |
2705 | tree genop0 = NULL_TREE; | |
2706 | tree baseop = create_component_ref_by_pieces_1 (block, ref, operand, | |
2707 | stmts, domstmt); | |
2708 | if (!baseop) | |
2709 | return NULL_TREE; | |
2710 | if (currop->op0) | |
2711 | { | |
2712 | op0expr = get_or_alloc_expr_for (currop->op0); | |
2713 | genop0 = find_or_generate_expression (block, op0expr, | |
2714 | stmts, domstmt); | |
2715 | if (!genop0) | |
2716 | return NULL_TREE; | |
2717 | } | |
2718 | if (DECL_P (baseop)) | |
2719 | return build6 (TARGET_MEM_REF, currop->type, | |
2720 | baseop, NULL_TREE, | |
2721 | genop0, currop->op1, currop->op2, | |
2722 | unshare_expr (nextop->op1)); | |
2723 | else | |
2724 | return build6 (TARGET_MEM_REF, currop->type, | |
2725 | NULL_TREE, baseop, | |
2726 | genop0, currop->op1, currop->op2, | |
2727 | unshare_expr (nextop->op1)); | |
2728 | } | |
2729 | break; | |
ce94d354 RG |
2730 | case ADDR_EXPR: |
2731 | if (currop->op0) | |
2732 | { | |
2733 | gcc_assert (is_gimple_min_invariant (currop->op0)); | |
2734 | return currop->op0; | |
2735 | } | |
2736 | /* Fallthrough. */ | |
c9145754 DB |
2737 | case REALPART_EXPR: |
2738 | case IMAGPART_EXPR: | |
2739 | case VIEW_CONVERT_EXPR: | |
2740 | { | |
2741 | tree folded; | |
ce94d354 RG |
2742 | tree genop0 = create_component_ref_by_pieces_1 (block, ref, |
2743 | operand, | |
2744 | stmts, domstmt); | |
c9145754 DB |
2745 | if (!genop0) |
2746 | return NULL_TREE; | |
2747 | folded = fold_build1 (currop->opcode, currop->type, | |
2748 | genop0); | |
2749 | return folded; | |
2750 | } | |
2751 | break; | |
2752 | case ALIGN_INDIRECT_REF: | |
2753 | case MISALIGNED_INDIRECT_REF: | |
2754 | case INDIRECT_REF: | |
2755 | { | |
ce94d354 RG |
2756 | tree folded; |
2757 | tree genop1 = create_component_ref_by_pieces_1 (block, ref, | |
2758 | operand, | |
2759 | stmts, domstmt); | |
2760 | if (!genop1) | |
2761 | return NULL_TREE; | |
2762 | genop1 = fold_convert (build_pointer_type (currop->type), | |
2763 | genop1); | |
c9145754 | 2764 | |
53f3815c RG |
2765 | if (currop->opcode == MISALIGNED_INDIRECT_REF) |
2766 | folded = fold_build2 (currop->opcode, currop->type, | |
2767 | genop1, currop->op1); | |
2768 | else | |
2769 | folded = fold_build1 (currop->opcode, currop->type, | |
2770 | genop1); | |
ce94d354 | 2771 | return folded; |
c9145754 DB |
2772 | } |
2773 | break; | |
2774 | case BIT_FIELD_REF: | |
e13f1c14 | 2775 | { |
c9145754 | 2776 | tree folded; |
ce94d354 RG |
2777 | tree genop0 = create_component_ref_by_pieces_1 (block, ref, operand, |
2778 | stmts, domstmt); | |
c9145754 DB |
2779 | pre_expr op1expr = get_or_alloc_expr_for (currop->op0); |
2780 | pre_expr op2expr = get_or_alloc_expr_for (currop->op1); | |
2781 | tree genop1; | |
2782 | tree genop2; | |
2783 | ||
2784 | if (!genop0) | |
2785 | return NULL_TREE; | |
2786 | genop1 = find_or_generate_expression (block, op1expr, stmts, domstmt); | |
2787 | if (!genop1) | |
3d45dd59 | 2788 | return NULL_TREE; |
c9145754 DB |
2789 | genop2 = find_or_generate_expression (block, op2expr, stmts, domstmt); |
2790 | if (!genop2) | |
2791 | return NULL_TREE; | |
2792 | folded = fold_build3 (BIT_FIELD_REF, currop->type, genop0, genop1, | |
2793 | genop2); | |
e13f1c14 AP |
2794 | return folded; |
2795 | } | |
c9145754 DB |
2796 | |
2797 | /* For array ref vn_reference_op's, operand 1 of the array ref | |
2798 | is op0 of the reference op and operand 3 of the array ref is | |
2799 | op1. */ | |
2800 | case ARRAY_RANGE_REF: | |
2801 | case ARRAY_REF: | |
2802 | { | |
c9145754 DB |
2803 | tree genop0; |
2804 | tree genop1 = currop->op0; | |
2805 | pre_expr op1expr; | |
2806 | tree genop2 = currop->op1; | |
2807 | pre_expr op2expr; | |
e52201b6 RG |
2808 | tree genop3 = currop->op2; |
2809 | pre_expr op3expr; | |
ce94d354 RG |
2810 | genop0 = create_component_ref_by_pieces_1 (block, ref, operand, |
2811 | stmts, domstmt); | |
c9145754 DB |
2812 | if (!genop0) |
2813 | return NULL_TREE; | |
2814 | op1expr = get_or_alloc_expr_for (genop1); | |
2815 | genop1 = find_or_generate_expression (block, op1expr, stmts, domstmt); | |
2816 | if (!genop1) | |
2817 | return NULL_TREE; | |
2818 | if (genop2) | |
2819 | { | |
2820 | op2expr = get_or_alloc_expr_for (genop2); | |
2821 | genop2 = find_or_generate_expression (block, op2expr, stmts, | |
2822 | domstmt); | |
2823 | if (!genop2) | |
2824 | return NULL_TREE; | |
2825 | } | |
e52201b6 RG |
2826 | if (genop3) |
2827 | { | |
2828 | tree elmt_type = TREE_TYPE (TREE_TYPE (genop0)); | |
2829 | genop3 = size_binop (EXACT_DIV_EXPR, genop3, | |
2830 | size_int (TYPE_ALIGN_UNIT (elmt_type))); | |
2831 | op3expr = get_or_alloc_expr_for (genop3); | |
2832 | genop3 = find_or_generate_expression (block, op3expr, stmts, | |
2833 | domstmt); | |
2834 | if (!genop3) | |
2835 | return NULL_TREE; | |
2836 | } | |
c9145754 DB |
2837 | return build4 (currop->opcode, currop->type, genop0, genop1, |
2838 | genop2, genop3); | |
2839 | } | |
85300b46 DB |
2840 | case COMPONENT_REF: |
2841 | { | |
2842 | tree op0; | |
2843 | tree op1; | |
c9145754 DB |
2844 | tree genop2 = currop->op1; |
2845 | pre_expr op2expr; | |
ce94d354 RG |
2846 | op0 = create_component_ref_by_pieces_1 (block, ref, operand, |
2847 | stmts, domstmt); | |
3d45dd59 RG |
2848 | if (!op0) |
2849 | return NULL_TREE; | |
89fb70a3 DB |
2850 | /* op1 should be a FIELD_DECL, which are represented by |
2851 | themselves. */ | |
c9145754 DB |
2852 | op1 = currop->op0; |
2853 | if (genop2) | |
2854 | { | |
2855 | op2expr = get_or_alloc_expr_for (genop2); | |
2856 | genop2 = find_or_generate_expression (block, op2expr, stmts, | |
2857 | domstmt); | |
2858 | if (!genop2) | |
2859 | return NULL_TREE; | |
2860 | } | |
2861 | ||
2862 | return fold_build3 (COMPONENT_REF, TREE_TYPE (op1), op0, op1, | |
2863 | genop2); | |
85300b46 DB |
2864 | } |
2865 | break; | |
c9145754 | 2866 | case SSA_NAME: |
85300b46 | 2867 | { |
c9145754 DB |
2868 | pre_expr op0expr = get_or_alloc_expr_for (currop->op0); |
2869 | genop = find_or_generate_expression (block, op0expr, stmts, domstmt); | |
2870 | return genop; | |
85300b46 | 2871 | } |
c9145754 DB |
2872 | case STRING_CST: |
2873 | case INTEGER_CST: | |
2874 | case COMPLEX_CST: | |
2875 | case VECTOR_CST: | |
2876 | case REAL_CST: | |
2877 | case CONSTRUCTOR: | |
85300b46 DB |
2878 | case VAR_DECL: |
2879 | case PARM_DECL: | |
c9145754 | 2880 | case CONST_DECL: |
5230d884 | 2881 | case RESULT_DECL: |
c9145754 | 2882 | case FUNCTION_DECL: |
c9145754 DB |
2883 | return currop->op0; |
2884 | ||
85300b46 | 2885 | default: |
b9c5e484 | 2886 | gcc_unreachable (); |
85300b46 | 2887 | } |
85300b46 | 2888 | } |
c90186eb | 2889 | |
ce94d354 RG |
2890 | /* For COMPONENT_REF's and ARRAY_REF's, we can't have any intermediates for the |
2891 | COMPONENT_REF or INDIRECT_REF or ARRAY_REF portion, because we'd end up with | |
2892 | trying to rename aggregates into ssa form directly, which is a no no. | |
2893 | ||
2894 | Thus, this routine doesn't create temporaries, it just builds a | |
2895 | single access expression for the array, calling | |
2896 | find_or_generate_expression to build the innermost pieces. | |
2897 | ||
2898 | This function is a subroutine of create_expression_by_pieces, and | |
2899 | should not be called on it's own unless you really know what you | |
2900 | are doing. */ | |
2901 | ||
2902 | static tree | |
2903 | create_component_ref_by_pieces (basic_block block, vn_reference_t ref, | |
2904 | gimple_seq *stmts, gimple domstmt) | |
2905 | { | |
2906 | unsigned int op = 0; | |
2907 | return create_component_ref_by_pieces_1 (block, ref, &op, stmts, domstmt); | |
2908 | } | |
2909 | ||
56db793a DB |
2910 | /* Find a leader for an expression, or generate one using |
2911 | create_expression_by_pieces if it's ANTIC but | |
b9c5e484 | 2912 | complex. |
56db793a | 2913 | BLOCK is the basic_block we are looking for leaders in. |
b9c5e484 | 2914 | EXPR is the expression to find a leader or generate for. |
56db793a DB |
2915 | STMTS is the statement list to put the inserted expressions on. |
2916 | Returns the SSA_NAME of the LHS of the generated expression or the | |
3d45dd59 RG |
2917 | leader. |
2918 | DOMSTMT if non-NULL is a statement that should be dominated by | |
2919 | all uses in the generated expression. If DOMSTMT is non-NULL this | |
2920 | routine can fail and return NULL_TREE. Otherwise it will assert | |
2921 | on failure. */ | |
56db793a DB |
2922 | |
2923 | static tree | |
726a989a RB |
2924 | find_or_generate_expression (basic_block block, pre_expr expr, |
2925 | gimple_seq *stmts, gimple domstmt) | |
56db793a | 2926 | { |
726a989a RB |
2927 | pre_expr leader = bitmap_find_leader (AVAIL_OUT (block), |
2928 | get_expr_value_id (expr), domstmt); | |
c9145754 DB |
2929 | tree genop = NULL; |
2930 | if (leader) | |
2931 | { | |
2932 | if (leader->kind == NAME) | |
2933 | genop = PRE_EXPR_NAME (leader); | |
2934 | else if (leader->kind == CONSTANT) | |
2935 | genop = PRE_EXPR_CONSTANT (leader); | |
2936 | } | |
e9284566 | 2937 | |
0e61db61 | 2938 | /* If it's still NULL, it must be a complex expression, so generate |
ecb4e37b RG |
2939 | it recursively. Not so for FRE though. */ |
2940 | if (genop == NULL | |
2941 | && !in_fre) | |
56db793a | 2942 | { |
c9145754 DB |
2943 | bitmap_set_t exprset; |
2944 | unsigned int lookfor = get_expr_value_id (expr); | |
89fb70a3 DB |
2945 | bool handled = false; |
2946 | bitmap_iterator bi; | |
2947 | unsigned int i; | |
c90186eb | 2948 | |
c9145754 | 2949 | exprset = VEC_index (bitmap_set_t, value_expressions, lookfor); |
89fb70a3 DB |
2950 | FOR_EACH_EXPR_ID_IN_SET (exprset, i, bi) |
2951 | { | |
c9145754 DB |
2952 | pre_expr temp = expression_for_id (i); |
2953 | if (temp->kind != NAME) | |
89fb70a3 DB |
2954 | { |
2955 | handled = true; | |
c9145754 DB |
2956 | genop = create_expression_by_pieces (block, temp, stmts, |
2957 | domstmt, | |
2958 | get_expr_type (expr)); | |
89fb70a3 DB |
2959 | break; |
2960 | } | |
2961 | } | |
3d45dd59 RG |
2962 | if (!handled && domstmt) |
2963 | return NULL_TREE; | |
2964 | ||
89fb70a3 | 2965 | gcc_assert (handled); |
56db793a DB |
2966 | } |
2967 | return genop; | |
2968 | } | |
2969 | ||
726a989a | 2970 | #define NECESSARY GF_PLF_1 |
c9145754 | 2971 | |
56db793a | 2972 | /* Create an expression in pieces, so that we can handle very complex |
b9c5e484 | 2973 | expressions that may be ANTIC, but not necessary GIMPLE. |
56db793a DB |
2974 | BLOCK is the basic block the expression will be inserted into, |
2975 | EXPR is the expression to insert (in value form) | |
2976 | STMTS is a statement list to append the necessary insertions into. | |
2977 | ||
0e61db61 | 2978 | This function will die if we hit some value that shouldn't be |
56db793a DB |
2979 | ANTIC but is (IE there is no leader for it, or its components). |
2980 | This function may also generate expressions that are themselves | |
2981 | partially or fully redundant. Those that are will be either made | |
2982 | fully redundant during the next iteration of insert (for partially | |
2983 | redundant ones), or eliminated by eliminate (for fully redundant | |
3d45dd59 RG |
2984 | ones). |
2985 | ||
2986 | If DOMSTMT is non-NULL then we make sure that all uses in the | |
2987 | expressions dominate that statement. In this case the function | |
2988 | can return NULL_TREE to signal failure. */ | |
56db793a DB |
2989 | |
2990 | static tree | |
726a989a RB |
2991 | create_expression_by_pieces (basic_block block, pre_expr expr, |
2992 | gimple_seq *stmts, gimple domstmt, tree type) | |
56db793a | 2993 | { |
81c4f554 | 2994 | tree temp, name; |
150e3929 RG |
2995 | tree folded; |
2996 | gimple_seq forced_stmts = NULL; | |
c9145754 | 2997 | unsigned int value_id; |
726a989a | 2998 | gimple_stmt_iterator gsi; |
c9145754 DB |
2999 | tree exprtype = type ? type : get_expr_type (expr); |
3000 | pre_expr nameexpr; | |
726a989a | 3001 | gimple newstmt; |
81c4f554 | 3002 | |
c9145754 | 3003 | switch (expr->kind) |
56db793a | 3004 | { |
c9145754 DB |
3005 | /* We may hit the NAME/CONSTANT case if we have to convert types |
3006 | that value numbering saw through. */ | |
3007 | case NAME: | |
3008 | folded = PRE_EXPR_NAME (expr); | |
3009 | break; | |
3010 | case CONSTANT: | |
3011 | folded = PRE_EXPR_CONSTANT (expr); | |
3012 | break; | |
3013 | case REFERENCE: | |
43da81be | 3014 | { |
c9145754 | 3015 | vn_reference_t ref = PRE_EXPR_REFERENCE (expr); |
ce94d354 | 3016 | folded = create_component_ref_by_pieces (block, ref, stmts, domstmt); |
43da81be DB |
3017 | } |
3018 | break; | |
c9145754 | 3019 | case NARY: |
c90186eb | 3020 | { |
c9145754 DB |
3021 | vn_nary_op_t nary = PRE_EXPR_NARY (expr); |
3022 | switch (nary->length) | |
85300b46 | 3023 | { |
c9145754 DB |
3024 | case 2: |
3025 | { | |
3026 | pre_expr op1 = get_or_alloc_expr_for (nary->op[0]); | |
3027 | pre_expr op2 = get_or_alloc_expr_for (nary->op[1]); | |
3028 | tree genop1 = find_or_generate_expression (block, op1, | |
3029 | stmts, domstmt); | |
3030 | tree genop2 = find_or_generate_expression (block, op2, | |
3031 | stmts, domstmt); | |
3032 | if (!genop1 || !genop2) | |
3033 | return NULL_TREE; | |
726a989a RB |
3034 | /* Ensure op2 is a sizetype for POINTER_PLUS_EXPR. It |
3035 | may be a constant with the wrong type. */ | |
3036 | if (nary->opcode == POINTER_PLUS_EXPR) | |
6d892147 RG |
3037 | { |
3038 | genop1 = fold_convert (nary->type, genop1); | |
3039 | genop2 = fold_convert (sizetype, genop2); | |
3040 | } | |
726a989a | 3041 | else |
6d892147 RG |
3042 | { |
3043 | genop1 = fold_convert (TREE_TYPE (nary->op[0]), genop1); | |
3044 | genop2 = fold_convert (TREE_TYPE (nary->op[1]), genop2); | |
3045 | } | |
b8698a0f | 3046 | |
c9145754 DB |
3047 | folded = fold_build2 (nary->opcode, nary->type, |
3048 | genop1, genop2); | |
3049 | } | |
3050 | break; | |
3051 | case 1: | |
3052 | { | |
3053 | pre_expr op1 = get_or_alloc_expr_for (nary->op[0]); | |
3054 | tree genop1 = find_or_generate_expression (block, op1, | |
3055 | stmts, domstmt); | |
3056 | if (!genop1) | |
3057 | return NULL_TREE; | |
6999afe1 DB |
3058 | genop1 = fold_convert (TREE_TYPE (nary->op[0]), genop1); |
3059 | ||
c9145754 DB |
3060 | folded = fold_build1 (nary->opcode, nary->type, |
3061 | genop1); | |
3062 | } | |
3063 | break; | |
3064 | default: | |
3065 | return NULL_TREE; | |
85300b46 | 3066 | } |
56db793a | 3067 | } |
c9145754 | 3068 | break; |
56db793a | 3069 | default: |
c9145754 | 3070 | return NULL_TREE; |
56db793a | 3071 | } |
150e3929 RG |
3072 | |
3073 | if (!useless_type_conversion_p (exprtype, TREE_TYPE (folded))) | |
3074 | folded = fold_convert (exprtype, folded); | |
3075 | ||
81c4f554 SB |
3076 | /* Force the generated expression to be a sequence of GIMPLE |
3077 | statements. | |
3078 | We have to call unshare_expr because force_gimple_operand may | |
3079 | modify the tree we pass to it. */ | |
150e3929 RG |
3080 | folded = force_gimple_operand (unshare_expr (folded), &forced_stmts, |
3081 | false, NULL); | |
81c4f554 SB |
3082 | |
3083 | /* If we have any intermediate expressions to the value sets, add them | |
a7849637 | 3084 | to the value sets and chain them in the instruction stream. */ |
81c4f554 SB |
3085 | if (forced_stmts) |
3086 | { | |
726a989a RB |
3087 | gsi = gsi_start (forced_stmts); |
3088 | for (; !gsi_end_p (gsi); gsi_next (&gsi)) | |
81c4f554 | 3089 | { |
726a989a RB |
3090 | gimple stmt = gsi_stmt (gsi); |
3091 | tree forcedname = gimple_get_lhs (stmt); | |
c9145754 | 3092 | pre_expr nameexpr; |
b9c5e484 | 3093 | |
726a989a | 3094 | VEC_safe_push (gimple, heap, inserted_exprs, stmt); |
c9145754 DB |
3095 | if (TREE_CODE (forcedname) == SSA_NAME) |
3096 | { | |
3097 | VN_INFO_GET (forcedname)->valnum = forcedname; | |
3098 | VN_INFO (forcedname)->value_id = get_next_value_id (); | |
3099 | nameexpr = get_or_alloc_expr_for_name (forcedname); | |
3100 | add_to_value (VN_INFO (forcedname)->value_id, nameexpr); | |
c8ce33fa RG |
3101 | if (!in_fre) |
3102 | bitmap_value_replace_in_set (NEW_SETS (block), nameexpr); | |
c9145754 DB |
3103 | bitmap_value_replace_in_set (AVAIL_OUT (block), nameexpr); |
3104 | } | |
cfaab3a9 | 3105 | mark_symbols_for_renaming (stmt); |
81c4f554 | 3106 | } |
726a989a | 3107 | gimple_seq_add_seq (stmts, forced_stmts); |
81c4f554 SB |
3108 | } |
3109 | ||
3110 | /* Build and insert the assignment of the end result to the temporary | |
3111 | that we will return. */ | |
c9145754 | 3112 | if (!pretemp || exprtype != TREE_TYPE (pretemp)) |
c90186eb | 3113 | { |
c9145754 | 3114 | pretemp = create_tmp_var (exprtype, "pretmp"); |
c90186eb DB |
3115 | get_var_ann (pretemp); |
3116 | } | |
3117 | ||
3118 | temp = pretemp; | |
f004ab02 | 3119 | add_referenced_var (temp); |
c90186eb | 3120 | |
c9145754 DB |
3121 | if (TREE_CODE (exprtype) == COMPLEX_TYPE |
3122 | || TREE_CODE (exprtype) == VECTOR_TYPE) | |
0890b981 | 3123 | DECL_GIMPLE_REG_P (temp) = 1; |
c90186eb | 3124 | |
150e3929 | 3125 | newstmt = gimple_build_assign (temp, folded); |
726a989a RB |
3126 | name = make_ssa_name (temp, newstmt); |
3127 | gimple_assign_set_lhs (newstmt, name); | |
3128 | gimple_set_plf (newstmt, NECESSARY, false); | |
c90186eb | 3129 | |
726a989a RB |
3130 | gimple_seq_add_stmt (stmts, newstmt); |
3131 | VEC_safe_push (gimple, heap, inserted_exprs, newstmt); | |
cfaab3a9 DN |
3132 | |
3133 | /* All the symbols in NEWEXPR should be put into SSA form. */ | |
726a989a | 3134 | mark_symbols_for_renaming (newstmt); |
81c4f554 | 3135 | |
c9145754 | 3136 | /* Add a value number to the temporary. |
81c4f554 | 3137 | The value may already exist in either NEW_SETS, or AVAIL_OUT, because |
e9284566 DB |
3138 | we are creating the expression by pieces, and this particular piece of |
3139 | the expression may have been represented. There is no harm in replacing | |
3140 | here. */ | |
89fb70a3 | 3141 | VN_INFO_GET (name)->valnum = name; |
c9145754 DB |
3142 | value_id = get_expr_value_id (expr); |
3143 | VN_INFO (name)->value_id = value_id; | |
3144 | nameexpr = get_or_alloc_expr_for_name (name); | |
3145 | add_to_value (value_id, nameexpr); | |
3d45dd59 | 3146 | if (!in_fre) |
c9145754 DB |
3147 | bitmap_value_replace_in_set (NEW_SETS (block), nameexpr); |
3148 | bitmap_value_replace_in_set (AVAIL_OUT (block), nameexpr); | |
81c4f554 SB |
3149 | |
3150 | pre_stats.insertions++; | |
56db793a | 3151 | if (dump_file && (dump_flags & TDF_DETAILS)) |
b9c5e484 | 3152 | { |
56db793a | 3153 | fprintf (dump_file, "Inserted "); |
726a989a | 3154 | print_gimple_stmt (dump_file, newstmt, 0, 0); |
56db793a DB |
3155 | fprintf (dump_file, " in predecessor %d\n", block->index); |
3156 | } | |
81c4f554 | 3157 | |
56db793a DB |
3158 | return name; |
3159 | } | |
e9284566 | 3160 | |
c9145754 | 3161 | |
a8338640 MM |
3162 | /* Returns true if we want to inhibit the insertions of PHI nodes |
3163 | for the given EXPR for basic block BB (a member of a loop). | |
3164 | We want to do this, when we fear that the induction variable we | |
3165 | create might inhibit vectorization. */ | |
3166 | ||
3167 | static bool | |
3168 | inhibit_phi_insertion (basic_block bb, pre_expr expr) | |
3169 | { | |
3170 | vn_reference_t vr = PRE_EXPR_REFERENCE (expr); | |
3171 | VEC (vn_reference_op_s, heap) *ops = vr->operands; | |
3172 | vn_reference_op_t op; | |
3173 | unsigned i; | |
3174 | ||
3175 | /* If we aren't going to vectorize we don't inhibit anything. */ | |
3176 | if (!flag_tree_vectorize) | |
3177 | return false; | |
3178 | ||
3179 | /* Otherwise we inhibit the insertion when the address of the | |
3180 | memory reference is a simple induction variable. In other | |
3181 | cases the vectorizer won't do anything anyway (either it's | |
3182 | loop invariant or a complicated expression). */ | |
3183 | for (i = 0; VEC_iterate (vn_reference_op_s, ops, i, op); ++i) | |
3184 | { | |
3185 | switch (op->opcode) | |
3186 | { | |
3187 | case ARRAY_REF: | |
3188 | case ARRAY_RANGE_REF: | |
3189 | if (TREE_CODE (op->op0) != SSA_NAME) | |
3190 | break; | |
3191 | /* Fallthru. */ | |
3192 | case SSA_NAME: | |
3193 | { | |
3194 | basic_block defbb = gimple_bb (SSA_NAME_DEF_STMT (op->op0)); | |
3195 | affine_iv iv; | |
3196 | /* Default defs are loop invariant. */ | |
3197 | if (!defbb) | |
3198 | break; | |
3199 | /* Defined outside this loop, also loop invariant. */ | |
3200 | if (!flow_bb_inside_loop_p (bb->loop_father, defbb)) | |
3201 | break; | |
3202 | /* If it's a simple induction variable inhibit insertion, | |
3203 | the vectorizer might be interested in this one. */ | |
3204 | if (simple_iv (bb->loop_father, bb->loop_father, | |
3205 | op->op0, &iv, true)) | |
3206 | return true; | |
3207 | /* No simple IV, vectorizer can't do anything, hence no | |
3208 | reason to inhibit the transformation for this operand. */ | |
3209 | break; | |
3210 | } | |
3211 | default: | |
3212 | break; | |
3213 | } | |
3214 | } | |
3215 | return false; | |
3216 | } | |
3217 | ||
83737db2 | 3218 | /* Insert the to-be-made-available values of expression EXPRNUM for each |
c90186eb | 3219 | predecessor, stored in AVAIL, into the predecessors of BLOCK, and |
c9145754 | 3220 | merge the result with a phi node, given the same value number as |
c90186eb | 3221 | NODE. Return true if we have inserted new stuff. */ |
e9284566 DB |
3222 | |
3223 | static bool | |
83737db2 | 3224 | insert_into_preds_of_block (basic_block block, unsigned int exprnum, |
c9145754 | 3225 | pre_expr *avail) |
e9284566 | 3226 | { |
c9145754 DB |
3227 | pre_expr expr = expression_for_id (exprnum); |
3228 | pre_expr newphi; | |
3229 | unsigned int val = get_expr_value_id (expr); | |
e9284566 | 3230 | edge pred; |
0fc6c492 DB |
3231 | bool insertions = false; |
3232 | bool nophi = false; | |
e9284566 | 3233 | basic_block bprime; |
c9145754 | 3234 | pre_expr eprime; |
e9284566 | 3235 | edge_iterator ei; |
c9145754 | 3236 | tree type = get_expr_type (expr); |
de081cfd | 3237 | tree temp; |
726a989a | 3238 | gimple phi; |
b9c5e484 | 3239 | |
e9284566 DB |
3240 | if (dump_file && (dump_flags & TDF_DETAILS)) |
3241 | { | |
3242 | fprintf (dump_file, "Found partial redundancy for expression "); | |
c9145754 DB |
3243 | print_pre_expr (dump_file, expr); |
3244 | fprintf (dump_file, " (%04d)\n", val); | |
e9284566 DB |
3245 | } |
3246 | ||
0fc6c492 | 3247 | /* Make sure we aren't creating an induction variable. */ |
a8338640 | 3248 | if (block->loop_depth > 0 && EDGE_COUNT (block->preds) == 2) |
0fc6c492 DB |
3249 | { |
3250 | bool firstinsideloop = false; | |
3251 | bool secondinsideloop = false; | |
b9c5e484 | 3252 | firstinsideloop = flow_bb_inside_loop_p (block->loop_father, |
0fc6c492 DB |
3253 | EDGE_PRED (block, 0)->src); |
3254 | secondinsideloop = flow_bb_inside_loop_p (block->loop_father, | |
3255 | EDGE_PRED (block, 1)->src); | |
3256 | /* Induction variables only have one edge inside the loop. */ | |
a8338640 MM |
3257 | if ((firstinsideloop ^ secondinsideloop) |
3258 | && (expr->kind != REFERENCE | |
3259 | || inhibit_phi_insertion (block, expr))) | |
0fc6c492 DB |
3260 | { |
3261 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
3262 | fprintf (dump_file, "Skipping insertion of phi for partial redundancy: Looks like an induction variable\n"); | |
3263 | nophi = true; | |
3264 | } | |
3265 | } | |
b9c5e484 | 3266 | |
c9145754 DB |
3267 | /* Make the necessary insertions. */ |
3268 | FOR_EACH_EDGE (pred, ei, block->preds) | |
3269 | { | |
726a989a | 3270 | gimple_seq stmts = NULL; |
c9145754 DB |
3271 | tree builtexpr; |
3272 | bprime = pred->src; | |
3273 | eprime = avail[bprime->index]; | |
3274 | ||
3275 | if (eprime->kind != NAME && eprime->kind != CONSTANT) | |
3276 | { | |
3277 | builtexpr = create_expression_by_pieces (bprime, | |
3278 | eprime, | |
726a989a | 3279 | &stmts, NULL, |
c9145754 DB |
3280 | type); |
3281 | gcc_assert (!(pred->flags & EDGE_ABNORMAL)); | |
726a989a | 3282 | gsi_insert_seq_on_edge (pred, stmts); |
c9145754 DB |
3283 | avail[bprime->index] = get_or_alloc_expr_for_name (builtexpr); |
3284 | insertions = true; | |
3285 | } | |
3286 | else if (eprime->kind == CONSTANT) | |
3287 | { | |
3288 | /* Constants may not have the right type, fold_convert | |
3289 | should give us back a constant with the right type. | |
3290 | */ | |
3291 | tree constant = PRE_EXPR_CONSTANT (eprime); | |
15d5fe33 | 3292 | if (!useless_type_conversion_p (type, TREE_TYPE (constant))) |
c9145754 DB |
3293 | { |
3294 | tree builtexpr = fold_convert (type, constant); | |
b8698a0f | 3295 | if (!is_gimple_min_invariant (builtexpr)) |
c9145754 DB |
3296 | { |
3297 | tree forcedexpr = force_gimple_operand (builtexpr, | |
3298 | &stmts, true, | |
3299 | NULL); | |
15d5fe33 | 3300 | if (!is_gimple_min_invariant (forcedexpr)) |
c9145754 DB |
3301 | { |
3302 | if (forcedexpr != builtexpr) | |
3303 | { | |
3304 | VN_INFO_GET (forcedexpr)->valnum = PRE_EXPR_CONSTANT (eprime); | |
3305 | VN_INFO (forcedexpr)->value_id = get_expr_value_id (eprime); | |
3306 | } | |
3307 | if (stmts) | |
3308 | { | |
726a989a RB |
3309 | gimple_stmt_iterator gsi; |
3310 | gsi = gsi_start (stmts); | |
3311 | for (; !gsi_end_p (gsi); gsi_next (&gsi)) | |
c9145754 | 3312 | { |
726a989a RB |
3313 | gimple stmt = gsi_stmt (gsi); |
3314 | VEC_safe_push (gimple, heap, inserted_exprs, stmt); | |
3315 | gimple_set_plf (stmt, NECESSARY, false); | |
c9145754 | 3316 | } |
726a989a | 3317 | gsi_insert_seq_on_edge (pred, stmts); |
c9145754 | 3318 | } |
c9145754 DB |
3319 | avail[bprime->index] = get_or_alloc_expr_for_name (forcedexpr); |
3320 | } | |
3321 | } | |
3322 | } | |
3323 | } | |
3324 | else if (eprime->kind == NAME) | |
3325 | { | |
3326 | /* We may have to do a conversion because our value | |
3327 | numbering can look through types in certain cases, but | |
3328 | our IL requires all operands of a phi node have the same | |
3329 | type. */ | |
3330 | tree name = PRE_EXPR_NAME (eprime); | |
f709638a | 3331 | if (!useless_type_conversion_p (type, TREE_TYPE (name))) |
c9145754 DB |
3332 | { |
3333 | tree builtexpr; | |
3334 | tree forcedexpr; | |
f709638a | 3335 | builtexpr = fold_convert (type, name); |
c9145754 DB |
3336 | forcedexpr = force_gimple_operand (builtexpr, |
3337 | &stmts, true, | |
3338 | NULL); | |
3339 | ||
3340 | if (forcedexpr != name) | |
3341 | { | |
3342 | VN_INFO_GET (forcedexpr)->valnum = VN_INFO (name)->valnum; | |
3343 | VN_INFO (forcedexpr)->value_id = VN_INFO (name)->value_id; | |
3344 | } | |
c90186eb | 3345 | |
c9145754 DB |
3346 | if (stmts) |
3347 | { | |
726a989a RB |
3348 | gimple_stmt_iterator gsi; |
3349 | gsi = gsi_start (stmts); | |
3350 | for (; !gsi_end_p (gsi); gsi_next (&gsi)) | |
c9145754 | 3351 | { |
726a989a RB |
3352 | gimple stmt = gsi_stmt (gsi); |
3353 | VEC_safe_push (gimple, heap, inserted_exprs, stmt); | |
3354 | gimple_set_plf (stmt, NECESSARY, false); | |
c9145754 | 3355 | } |
726a989a | 3356 | gsi_insert_seq_on_edge (pred, stmts); |
c9145754 | 3357 | } |
c9145754 DB |
3358 | avail[bprime->index] = get_or_alloc_expr_for_name (forcedexpr); |
3359 | } | |
b9c5e484 | 3360 | } |
e9284566 | 3361 | } |
0fc6c492 DB |
3362 | /* If we didn't want a phi node, and we made insertions, we still have |
3363 | inserted new stuff, and thus return true. If we didn't want a phi node, | |
3364 | and didn't make insertions, we haven't added anything new, so return | |
3365 | false. */ | |
3366 | if (nophi && insertions) | |
3367 | return true; | |
3368 | else if (nophi && !insertions) | |
3369 | return false; | |
3370 | ||
e9284566 | 3371 | /* Now build a phi for the new variable. */ |
c90186eb DB |
3372 | if (!prephitemp || TREE_TYPE (prephitemp) != type) |
3373 | { | |
3374 | prephitemp = create_tmp_var (type, "prephitmp"); | |
3375 | get_var_ann (prephitemp); | |
3376 | } | |
3377 | ||
3378 | temp = prephitemp; | |
f004ab02 | 3379 | add_referenced_var (temp); |
c90186eb | 3380 | |
0890b981 AP |
3381 | if (TREE_CODE (type) == COMPLEX_TYPE |
3382 | || TREE_CODE (type) == VECTOR_TYPE) | |
3383 | DECL_GIMPLE_REG_P (temp) = 1; | |
1e52075c | 3384 | phi = create_phi_node (temp, block); |
de081cfd RG |
3385 | |
3386 | gimple_set_plf (phi, NECESSARY, false); | |
3387 | VN_INFO_GET (gimple_phi_result (phi))->valnum = gimple_phi_result (phi); | |
3388 | VN_INFO (gimple_phi_result (phi))->value_id = val; | |
3389 | VEC_safe_push (gimple, heap, inserted_exprs, phi); | |
439ef907 RG |
3390 | bitmap_set_bit (inserted_phi_names, |
3391 | SSA_NAME_VERSION (gimple_phi_result (phi))); | |
e9284566 | 3392 | FOR_EACH_EDGE (pred, ei, block->preds) |
c9145754 DB |
3393 | { |
3394 | pre_expr ae = avail[pred->src->index]; | |
3395 | gcc_assert (get_expr_type (ae) == type | |
3396 | || useless_type_conversion_p (type, get_expr_type (ae))); | |
3397 | if (ae->kind == CONSTANT) | |
f5045c96 | 3398 | add_phi_arg (phi, PRE_EXPR_CONSTANT (ae), pred, UNKNOWN_LOCATION); |
c9145754 | 3399 | else |
f5045c96 AM |
3400 | add_phi_arg (phi, PRE_EXPR_NAME (avail[pred->src->index]), pred, |
3401 | UNKNOWN_LOCATION); | |
c9145754 | 3402 | } |
b9c5e484 | 3403 | |
726a989a | 3404 | newphi = get_or_alloc_expr_for_name (gimple_phi_result (phi)); |
c9145754 | 3405 | add_to_value (val, newphi); |
b9c5e484 | 3406 | |
e9284566 DB |
3407 | /* The value should *not* exist in PHI_GEN, or else we wouldn't be doing |
3408 | this insertion, since we test for the existence of this value in PHI_GEN | |
3409 | before proceeding with the partial redundancy checks in insert_aux. | |
b9c5e484 | 3410 | |
e9284566 DB |
3411 | The value may exist in AVAIL_OUT, in particular, it could be represented |
3412 | by the expression we are trying to eliminate, in which case we want the | |
3413 | replacement to occur. If it's not existing in AVAIL_OUT, we want it | |
3414 | inserted there. | |
b9c5e484 | 3415 | |
e9284566 DB |
3416 | Similarly, to the PHI_GEN case, the value should not exist in NEW_SETS of |
3417 | this block, because if it did, it would have existed in our dominator's | |
3418 | AVAIL_OUT, and would have been skipped due to the full redundancy check. | |
3419 | */ | |
3420 | ||
c9145754 | 3421 | bitmap_insert_into_set (PHI_GEN (block), newphi); |
b9c5e484 | 3422 | bitmap_value_replace_in_set (AVAIL_OUT (block), |
c9145754 | 3423 | newphi); |
e9284566 | 3424 | bitmap_insert_into_set (NEW_SETS (block), |
c9145754 | 3425 | newphi); |
b9c5e484 | 3426 | |
e9284566 DB |
3427 | if (dump_file && (dump_flags & TDF_DETAILS)) |
3428 | { | |
3429 | fprintf (dump_file, "Created phi "); | |
726a989a | 3430 | print_gimple_stmt (dump_file, phi, 0, 0); |
e9284566 DB |
3431 | fprintf (dump_file, " in block %d\n", block->index); |
3432 | } | |
3433 | pre_stats.phis++; | |
3434 | return true; | |
3435 | } | |
3436 | ||
3437 | ||
b9c5e484 | 3438 | |
7e6eb623 DB |
3439 | /* Perform insertion of partially redundant values. |
3440 | For BLOCK, do the following: | |
3441 | 1. Propagate the NEW_SETS of the dominator into the current block. | |
b9c5e484 | 3442 | If the block has multiple predecessors, |
7e6eb623 | 3443 | 2a. Iterate over the ANTIC expressions for the block to see if |
83737db2 | 3444 | any of them are partially redundant. |
7e6eb623 | 3445 | 2b. If so, insert them into the necessary predecessors to make |
83737db2 | 3446 | the expression fully redundant. |
7e6eb623 DB |
3447 | 2c. Insert a new PHI merging the values of the predecessors. |
3448 | 2d. Insert the new PHI, and the new expressions, into the | |
83737db2 | 3449 | NEW_SETS set. |
7e6eb623 | 3450 | 3. Recursively call ourselves on the dominator children of BLOCK. |
6de9cd9a | 3451 | |
83737db2 | 3452 | Steps 1, 2a, and 3 are done by insert_aux. 2b, 2c and 2d are done by |
d75dbccd | 3453 | do_regular_insertion and do_partial_insertion. |
83737db2 | 3454 | |
7e6eb623 | 3455 | */ |
e9284566 | 3456 | |
83737db2 DB |
3457 | static bool |
3458 | do_regular_insertion (basic_block block, basic_block dom) | |
3459 | { | |
3460 | bool new_stuff = false; | |
c9145754 DB |
3461 | VEC (pre_expr, heap) *exprs = sorted_array_from_bitmap_set (ANTIC_IN (block)); |
3462 | pre_expr expr; | |
83737db2 DB |
3463 | int i; |
3464 | ||
c9145754 | 3465 | for (i = 0; VEC_iterate (pre_expr, exprs, i, expr); i++) |
83737db2 | 3466 | { |
c9145754 | 3467 | if (expr->kind != NAME) |
83737db2 | 3468 | { |
c9145754 DB |
3469 | pre_expr *avail; |
3470 | unsigned int val; | |
83737db2 DB |
3471 | bool by_some = false; |
3472 | bool cant_insert = false; | |
3473 | bool all_same = true; | |
c9145754 | 3474 | pre_expr first_s = NULL; |
83737db2 DB |
3475 | edge pred; |
3476 | basic_block bprime; | |
c9145754 | 3477 | pre_expr eprime = NULL; |
83737db2 | 3478 | edge_iterator ei; |
f11d2f1e | 3479 | pre_expr edoubleprime = NULL; |
5813994e | 3480 | bool do_insertion = false; |
83737db2 | 3481 | |
c9145754 | 3482 | val = get_expr_value_id (expr); |
83737db2 DB |
3483 | if (bitmap_set_contains_value (PHI_GEN (block), val)) |
3484 | continue; | |
3485 | if (bitmap_set_contains_value (AVAIL_OUT (dom), val)) | |
3486 | { | |
3487 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
3488 | fprintf (dump_file, "Found fully redundant value\n"); | |
3489 | continue; | |
3490 | } | |
3491 | ||
c9145754 | 3492 | avail = XCNEWVEC (pre_expr, last_basic_block); |
83737db2 DB |
3493 | FOR_EACH_EDGE (pred, ei, block->preds) |
3494 | { | |
c9145754 | 3495 | unsigned int vprime; |
83737db2 | 3496 | |
c4ab2baa RG |
3497 | /* We should never run insertion for the exit block |
3498 | and so not come across fake pred edges. */ | |
3499 | gcc_assert (!(pred->flags & EDGE_FAKE)); | |
83737db2 DB |
3500 | bprime = pred->src; |
3501 | eprime = phi_translate (expr, ANTIC_IN (block), NULL, | |
3502 | bprime, block); | |
3503 | ||
3504 | /* eprime will generally only be NULL if the | |
3505 | value of the expression, translated | |
3506 | through the PHI for this predecessor, is | |
3507 | undefined. If that is the case, we can't | |
3508 | make the expression fully redundant, | |
3509 | because its value is undefined along a | |
3510 | predecessor path. We can thus break out | |
3511 | early because it doesn't matter what the | |
3512 | rest of the results are. */ | |
3513 | if (eprime == NULL) | |
3514 | { | |
3515 | cant_insert = true; | |
3516 | break; | |
3517 | } | |
3518 | ||
3519 | eprime = fully_constant_expression (eprime); | |
726a989a RB |
3520 | vprime = get_expr_value_id (eprime); |
3521 | edoubleprime = bitmap_find_leader (AVAIL_OUT (bprime), | |
3522 | vprime, NULL); | |
83737db2 DB |
3523 | if (edoubleprime == NULL) |
3524 | { | |
3525 | avail[bprime->index] = eprime; | |
3526 | all_same = false; | |
3527 | } | |
3528 | else | |
3529 | { | |
3530 | avail[bprime->index] = edoubleprime; | |
3531 | by_some = true; | |
5813994e RG |
3532 | /* We want to perform insertions to remove a redundancy on |
3533 | a path in the CFG we want to optimize for speed. */ | |
3534 | if (optimize_edge_for_speed_p (pred)) | |
3535 | do_insertion = true; | |
83737db2 DB |
3536 | if (first_s == NULL) |
3537 | first_s = edoubleprime; | |
c9145754 | 3538 | else if (!pre_expr_eq (first_s, edoubleprime)) |
83737db2 DB |
3539 | all_same = false; |
3540 | } | |
3541 | } | |
3542 | /* If we can insert it, it's not the same value | |
3543 | already existing along every predecessor, and | |
3544 | it's defined by some predecessor, it is | |
3545 | partially redundant. */ | |
5813994e RG |
3546 | if (!cant_insert && !all_same && by_some && do_insertion |
3547 | && dbg_cnt (treepre_insert)) | |
83737db2 DB |
3548 | { |
3549 | if (insert_into_preds_of_block (block, get_expression_id (expr), | |
3550 | avail)) | |
3551 | new_stuff = true; | |
3552 | } | |
3553 | /* If all edges produce the same value and that value is | |
3554 | an invariant, then the PHI has the same value on all | |
3555 | edges. Note this. */ | |
3556 | else if (!cant_insert && all_same && eprime | |
53f3815c RG |
3557 | && (edoubleprime->kind == CONSTANT |
3558 | || edoubleprime->kind == NAME) | |
c9145754 | 3559 | && !value_id_constant_p (val)) |
83737db2 DB |
3560 | { |
3561 | unsigned int j; | |
3562 | bitmap_iterator bi; | |
c9145754 DB |
3563 | bitmap_set_t exprset = VEC_index (bitmap_set_t, |
3564 | value_expressions, val); | |
83737db2 | 3565 | |
53f3815c | 3566 | unsigned int new_val = get_expr_value_id (edoubleprime); |
83737db2 DB |
3567 | FOR_EACH_EXPR_ID_IN_SET (exprset, j, bi) |
3568 | { | |
c9145754 DB |
3569 | pre_expr expr = expression_for_id (j); |
3570 | ||
3571 | if (expr->kind == NAME) | |
83737db2 | 3572 | { |
c9145754 DB |
3573 | vn_ssa_aux_t info = VN_INFO (PRE_EXPR_NAME (expr)); |
3574 | /* Just reset the value id and valnum so it is | |
3575 | the same as the constant we have discovered. */ | |
53f3815c RG |
3576 | if (edoubleprime->kind == CONSTANT) |
3577 | { | |
3578 | info->valnum = PRE_EXPR_CONSTANT (edoubleprime); | |
3579 | pre_stats.constified++; | |
3580 | } | |
3581 | else | |
de081cfd | 3582 | info->valnum = VN_INFO (PRE_EXPR_NAME (edoubleprime))->valnum; |
c9145754 | 3583 | info->value_id = new_val; |
83737db2 DB |
3584 | } |
3585 | } | |
3586 | } | |
3587 | free (avail); | |
3588 | } | |
3589 | } | |
3590 | ||
c9145754 | 3591 | VEC_free (pre_expr, heap, exprs); |
83737db2 DB |
3592 | return new_stuff; |
3593 | } | |
3594 | ||
3595 | ||
d75dbccd DB |
3596 | /* Perform insertion for partially anticipatable expressions. There |
3597 | is only one case we will perform insertion for these. This case is | |
3598 | if the expression is partially anticipatable, and fully available. | |
3599 | In this case, we know that putting it earlier will enable us to | |
3600 | remove the later computation. */ | |
3601 | ||
3602 | ||
3603 | static bool | |
3604 | do_partial_partial_insertion (basic_block block, basic_block dom) | |
3605 | { | |
3606 | bool new_stuff = false; | |
c9145754 DB |
3607 | VEC (pre_expr, heap) *exprs = sorted_array_from_bitmap_set (PA_IN (block)); |
3608 | pre_expr expr; | |
d75dbccd DB |
3609 | int i; |
3610 | ||
c9145754 | 3611 | for (i = 0; VEC_iterate (pre_expr, exprs, i, expr); i++) |
d75dbccd | 3612 | { |
c9145754 | 3613 | if (expr->kind != NAME) |
d75dbccd | 3614 | { |
c9145754 DB |
3615 | pre_expr *avail; |
3616 | unsigned int val; | |
d75dbccd DB |
3617 | bool by_all = true; |
3618 | bool cant_insert = false; | |
3619 | edge pred; | |
3620 | basic_block bprime; | |
c9145754 | 3621 | pre_expr eprime = NULL; |
d75dbccd DB |
3622 | edge_iterator ei; |
3623 | ||
c9145754 | 3624 | val = get_expr_value_id (expr); |
d75dbccd DB |
3625 | if (bitmap_set_contains_value (PHI_GEN (block), val)) |
3626 | continue; | |
3627 | if (bitmap_set_contains_value (AVAIL_OUT (dom), val)) | |
3628 | continue; | |
3629 | ||
c9145754 | 3630 | avail = XCNEWVEC (pre_expr, last_basic_block); |
d75dbccd DB |
3631 | FOR_EACH_EDGE (pred, ei, block->preds) |
3632 | { | |
c9145754 DB |
3633 | unsigned int vprime; |
3634 | pre_expr edoubleprime; | |
d75dbccd | 3635 | |
c4ab2baa RG |
3636 | /* We should never run insertion for the exit block |
3637 | and so not come across fake pred edges. */ | |
3638 | gcc_assert (!(pred->flags & EDGE_FAKE)); | |
d75dbccd DB |
3639 | bprime = pred->src; |
3640 | eprime = phi_translate (expr, ANTIC_IN (block), | |
3641 | PA_IN (block), | |
3642 | bprime, block); | |
3643 | ||
3644 | /* eprime will generally only be NULL if the | |
3645 | value of the expression, translated | |
3646 | through the PHI for this predecessor, is | |
3647 | undefined. If that is the case, we can't | |
3648 | make the expression fully redundant, | |
3649 | because its value is undefined along a | |
3650 | predecessor path. We can thus break out | |
3651 | early because it doesn't matter what the | |
3652 | rest of the results are. */ | |
3653 | if (eprime == NULL) | |
3654 | { | |
3655 | cant_insert = true; | |
3656 | break; | |
3657 | } | |
3658 | ||
3659 | eprime = fully_constant_expression (eprime); | |
726a989a RB |
3660 | vprime = get_expr_value_id (eprime); |
3661 | edoubleprime = bitmap_find_leader (AVAIL_OUT (bprime), | |
3662 | vprime, NULL); | |
d75dbccd DB |
3663 | if (edoubleprime == NULL) |
3664 | { | |
3665 | by_all = false; | |
3666 | break; | |
3667 | } | |
3668 | else | |
3669 | avail[bprime->index] = edoubleprime; | |
3670 | ||
3671 | } | |
3672 | ||
3673 | /* If we can insert it, it's not the same value | |
3674 | already existing along every predecessor, and | |
3675 | it's defined by some predecessor, it is | |
3676 | partially redundant. */ | |
c9145754 | 3677 | if (!cant_insert && by_all && dbg_cnt (treepre_insert)) |
d75dbccd DB |
3678 | { |
3679 | pre_stats.pa_insert++; | |
3680 | if (insert_into_preds_of_block (block, get_expression_id (expr), | |
3681 | avail)) | |
3682 | new_stuff = true; | |
3683 | } | |
3684 | free (avail); | |
3685 | } | |
3686 | } | |
3687 | ||
c9145754 | 3688 | VEC_free (pre_expr, heap, exprs); |
d75dbccd DB |
3689 | return new_stuff; |
3690 | } | |
83737db2 | 3691 | |
7e6eb623 DB |
3692 | static bool |
3693 | insert_aux (basic_block block) | |
6de9cd9a | 3694 | { |
7e6eb623 DB |
3695 | basic_block son; |
3696 | bool new_stuff = false; | |
6de9cd9a | 3697 | |
7e6eb623 | 3698 | if (block) |
6de9cd9a | 3699 | { |
7e6eb623 DB |
3700 | basic_block dom; |
3701 | dom = get_immediate_dominator (CDI_DOMINATORS, block); | |
3702 | if (dom) | |
a32b97a2 | 3703 | { |
3cd8c58a | 3704 | unsigned i; |
87c476a2 | 3705 | bitmap_iterator bi; |
6b416da1 | 3706 | bitmap_set_t newset = NEW_SETS (dom); |
e9284566 | 3707 | if (newset) |
87c476a2 | 3708 | { |
e9284566 DB |
3709 | /* Note that we need to value_replace both NEW_SETS, and |
3710 | AVAIL_OUT. For both the case of NEW_SETS, the value may be | |
3711 | represented by some non-simple expression here that we want | |
3712 | to replace it with. */ | |
83737db2 | 3713 | FOR_EACH_EXPR_ID_IN_SET (newset, i, bi) |
e9284566 | 3714 | { |
c9145754 | 3715 | pre_expr expr = expression_for_id (i); |
83737db2 DB |
3716 | bitmap_value_replace_in_set (NEW_SETS (block), expr); |
3717 | bitmap_value_replace_in_set (AVAIL_OUT (block), expr); | |
e9284566 | 3718 | } |
87c476a2 | 3719 | } |
c5cbcccf | 3720 | if (!single_pred_p (block)) |
6de9cd9a | 3721 | { |
83737db2 | 3722 | new_stuff |= do_regular_insertion (block, dom); |
d75dbccd DB |
3723 | if (do_partial_partial) |
3724 | new_stuff |= do_partial_partial_insertion (block, dom); | |
6de9cd9a DN |
3725 | } |
3726 | } | |
3727 | } | |
7e6eb623 DB |
3728 | for (son = first_dom_son (CDI_DOMINATORS, block); |
3729 | son; | |
3730 | son = next_dom_son (CDI_DOMINATORS, son)) | |
3731 | { | |
3732 | new_stuff |= insert_aux (son); | |
3733 | } | |
3734 | ||
3735 | return new_stuff; | |
6de9cd9a DN |
3736 | } |
3737 | ||
7e6eb623 | 3738 | /* Perform insertion of partially redundant values. */ |
6de9cd9a | 3739 | |
7e6eb623 DB |
3740 | static void |
3741 | insert (void) | |
6de9cd9a | 3742 | { |
7e6eb623 | 3743 | bool new_stuff = true; |
6de9cd9a | 3744 | basic_block bb; |
7e6eb623 | 3745 | int num_iterations = 0; |
b9c5e484 | 3746 | |
7e6eb623 | 3747 | FOR_ALL_BB (bb) |
6b416da1 | 3748 | NEW_SETS (bb) = bitmap_set_new (); |
b9c5e484 | 3749 | |
7e6eb623 | 3750 | while (new_stuff) |
6de9cd9a | 3751 | { |
7e6eb623 | 3752 | num_iterations++; |
7e6eb623 | 3753 | new_stuff = insert_aux (ENTRY_BLOCK_PTR); |
6de9cd9a | 3754 | } |
9fe0cb7d | 3755 | statistics_histogram_event (cfun, "insert iterations", num_iterations); |
7e6eb623 | 3756 | } |
6de9cd9a | 3757 | |
33c94679 | 3758 | |
7763473e | 3759 | /* Add OP to EXP_GEN (block), and possibly to the maximal set. */ |
89fb70a3 DB |
3760 | |
3761 | static void | |
3762 | add_to_exp_gen (basic_block block, tree op) | |
3763 | { | |
3764 | if (!in_fre) | |
3765 | { | |
c9145754 | 3766 | pre_expr result; |
7b7e6ecd | 3767 | if (TREE_CODE (op) == SSA_NAME && ssa_undefined_value_p (op)) |
89fb70a3 | 3768 | return; |
c9145754 DB |
3769 | result = get_or_alloc_expr_for_name (op); |
3770 | bitmap_value_insert_into_set (EXP_GEN (block), result); | |
6de9cd9a | 3771 | } |
6de9cd9a DN |
3772 | } |
3773 | ||
c9145754 | 3774 | /* Create value ids for PHI in BLOCK. */ |
89fb70a3 DB |
3775 | |
3776 | static void | |
726a989a | 3777 | make_values_for_phi (gimple phi, basic_block block) |
89fb70a3 | 3778 | { |
726a989a RB |
3779 | tree result = gimple_phi_result (phi); |
3780 | ||
89fb70a3 DB |
3781 | /* We have no need for virtual phis, as they don't represent |
3782 | actual computations. */ | |
3783 | if (is_gimple_reg (result)) | |
3784 | { | |
c9145754 DB |
3785 | pre_expr e = get_or_alloc_expr_for_name (result); |
3786 | add_to_value (get_expr_value_id (e), e); | |
3787 | bitmap_insert_into_set (PHI_GEN (block), e); | |
3788 | bitmap_value_insert_into_set (AVAIL_OUT (block), e); | |
7763473e RG |
3789 | if (!in_fre) |
3790 | { | |
3791 | unsigned i; | |
3792 | for (i = 0; i < gimple_phi_num_args (phi); ++i) | |
3793 | { | |
3794 | tree arg = gimple_phi_arg_def (phi, i); | |
3795 | if (TREE_CODE (arg) == SSA_NAME) | |
3796 | { | |
3797 | e = get_or_alloc_expr_for_name (arg); | |
3798 | add_to_value (get_expr_value_id (e), e); | |
7763473e RG |
3799 | } |
3800 | } | |
3801 | } | |
d818832c | 3802 | } |
d818832c | 3803 | } |
c90186eb | 3804 | |
665fcad8 SB |
3805 | /* Compute the AVAIL set for all basic blocks. |
3806 | ||
3807 | This function performs value numbering of the statements in each basic | |
3808 | block. The AVAIL sets are built from information we glean while doing | |
3809 | this value numbering, since the AVAIL sets contain only one entry per | |
7e6eb623 | 3810 | value. |
b9c5e484 | 3811 | |
7e6eb623 | 3812 | AVAIL_IN[BLOCK] = AVAIL_OUT[dom(BLOCK)]. |
ff2ad0f7 | 3813 | AVAIL_OUT[BLOCK] = AVAIL_IN[BLOCK] U PHI_GEN[BLOCK] U TMP_GEN[BLOCK]. */ |
6de9cd9a | 3814 | |
7e6eb623 | 3815 | static void |
665fcad8 | 3816 | compute_avail (void) |
6de9cd9a | 3817 | { |
c9145754 | 3818 | |
665fcad8 SB |
3819 | basic_block block, son; |
3820 | basic_block *worklist; | |
3821 | size_t sp = 0; | |
b005da11 RG |
3822 | unsigned i; |
3823 | ||
3824 | /* We pretend that default definitions are defined in the entry block. | |
3825 | This includes function arguments and the static chain decl. */ | |
3826 | for (i = 1; i < num_ssa_names; ++i) | |
3827 | { | |
3828 | tree name = ssa_name (i); | |
3829 | pre_expr e; | |
3830 | if (!name | |
3831 | || !SSA_NAME_IS_DEFAULT_DEF (name) | |
3832 | || has_zero_uses (name) | |
3833 | || !is_gimple_reg (name)) | |
3834 | continue; | |
665fcad8 | 3835 | |
b005da11 RG |
3836 | e = get_or_alloc_expr_for_name (name); |
3837 | add_to_value (get_expr_value_id (e), e); | |
3838 | if (!in_fre) | |
70a6b17e | 3839 | bitmap_insert_into_set (TMP_GEN (ENTRY_BLOCK_PTR), e); |
b005da11 | 3840 | bitmap_value_insert_into_set (AVAIL_OUT (ENTRY_BLOCK_PTR), e); |
2984956b AP |
3841 | } |
3842 | ||
665fcad8 | 3843 | /* Allocate the worklist. */ |
e1111e8e | 3844 | worklist = XNEWVEC (basic_block, n_basic_blocks); |
665fcad8 SB |
3845 | |
3846 | /* Seed the algorithm by putting the dominator children of the entry | |
3847 | block on the worklist. */ | |
3848 | for (son = first_dom_son (CDI_DOMINATORS, ENTRY_BLOCK_PTR); | |
3849 | son; | |
3850 | son = next_dom_son (CDI_DOMINATORS, son)) | |
3851 | worklist[sp++] = son; | |
3852 | ||
3853 | /* Loop until the worklist is empty. */ | |
3854 | while (sp) | |
6de9cd9a | 3855 | { |
726a989a RB |
3856 | gimple_stmt_iterator gsi; |
3857 | gimple stmt; | |
7e6eb623 | 3858 | basic_block dom; |
85300b46 | 3859 | unsigned int stmt_uid = 1; |
7e6eb623 | 3860 | |
665fcad8 SB |
3861 | /* Pick a block from the worklist. */ |
3862 | block = worklist[--sp]; | |
3863 | ||
ff2ad0f7 DN |
3864 | /* Initially, the set of available values in BLOCK is that of |
3865 | its immediate dominator. */ | |
7e6eb623 DB |
3866 | dom = get_immediate_dominator (CDI_DOMINATORS, block); |
3867 | if (dom) | |
bdee7684 | 3868 | bitmap_set_copy (AVAIL_OUT (block), AVAIL_OUT (dom)); |
33c94679 | 3869 | |
ff2ad0f7 | 3870 | /* Generate values for PHI nodes. */ |
726a989a RB |
3871 | for (gsi = gsi_start_phis (block); !gsi_end_p (gsi); gsi_next (&gsi)) |
3872 | make_values_for_phi (gsi_stmt (gsi), block); | |
7e6eb623 | 3873 | |
a19eb9d2 RG |
3874 | BB_MAY_NOTRETURN (block) = 0; |
3875 | ||
ff2ad0f7 DN |
3876 | /* Now compute value numbers and populate value sets with all |
3877 | the expressions computed in BLOCK. */ | |
726a989a | 3878 | for (gsi = gsi_start_bb (block); !gsi_end_p (gsi); gsi_next (&gsi)) |
6de9cd9a | 3879 | { |
f47c96aa AM |
3880 | ssa_op_iter iter; |
3881 | tree op; | |
ff2ad0f7 | 3882 | |
726a989a RB |
3883 | stmt = gsi_stmt (gsi); |
3884 | gimple_set_uid (stmt, stmt_uid++); | |
ff2ad0f7 | 3885 | |
a19eb9d2 RG |
3886 | /* Cache whether the basic-block has any non-visible side-effect |
3887 | or control flow. | |
3888 | If this isn't a call or it is the last stmt in the | |
3889 | basic-block then the CFG represents things correctly. */ | |
3890 | if (is_gimple_call (stmt) | |
3891 | && !stmt_ends_bb_p (stmt)) | |
3892 | { | |
3893 | /* Non-looping const functions always return normally. | |
3894 | Otherwise the call might not return or have side-effects | |
3895 | that forbids hoisting possibly trapping expressions | |
3896 | before it. */ | |
3897 | int flags = gimple_call_flags (stmt); | |
3898 | if (!(flags & ECF_CONST) | |
3899 | || (flags & ECF_LOOPING_CONST_OR_PURE)) | |
3900 | BB_MAY_NOTRETURN (block) = 1; | |
3901 | } | |
3902 | ||
c9145754 | 3903 | FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_DEF) |
83737db2 | 3904 | { |
c9145754 | 3905 | pre_expr e = get_or_alloc_expr_for_name (op); |
83737db2 | 3906 | |
c9145754 DB |
3907 | add_to_value (get_expr_value_id (e), e); |
3908 | if (!in_fre) | |
615cb001 | 3909 | bitmap_insert_into_set (TMP_GEN (block), e); |
c9145754 | 3910 | bitmap_value_insert_into_set (AVAIL_OUT (block), e); |
83737db2 DB |
3911 | } |
3912 | ||
726a989a RB |
3913 | if (gimple_has_volatile_ops (stmt) |
3914 | || stmt_could_throw_p (stmt)) | |
3915 | continue; | |
3916 | ||
3917 | switch (gimple_code (stmt)) | |
7e6eb623 | 3918 | { |
726a989a RB |
3919 | case GIMPLE_RETURN: |
3920 | FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_USE) | |
3921 | add_to_exp_gen (block, op); | |
c9145754 | 3922 | continue; |
726a989a RB |
3923 | |
3924 | case GIMPLE_CALL: | |
c9145754 | 3925 | { |
726a989a RB |
3926 | vn_reference_t ref; |
3927 | unsigned int i; | |
3928 | vn_reference_op_t vro; | |
3929 | pre_expr result = NULL; | |
3930 | VEC(vn_reference_op_s, heap) *ops = NULL; | |
c9145754 | 3931 | |
726a989a RB |
3932 | if (!can_value_number_call (stmt)) |
3933 | continue; | |
c9145754 | 3934 | |
726a989a | 3935 | copy_reference_ops_from_call (stmt, &ops); |
b45d2719 RG |
3936 | vn_reference_lookup_pieces (gimple_vuse (stmt), 0, |
3937 | gimple_expr_type (stmt), | |
53f3815c | 3938 | ops, &ref, false); |
726a989a RB |
3939 | VEC_free (vn_reference_op_s, heap, ops); |
3940 | if (!ref) | |
3941 | continue; | |
c9145754 | 3942 | |
726a989a RB |
3943 | for (i = 0; VEC_iterate (vn_reference_op_s, |
3944 | ref->operands, i, | |
3945 | vro); i++) | |
3946 | { | |
3947 | if (vro->op0 && TREE_CODE (vro->op0) == SSA_NAME) | |
3948 | add_to_exp_gen (block, vro->op0); | |
3949 | if (vro->op1 && TREE_CODE (vro->op1) == SSA_NAME) | |
3950 | add_to_exp_gen (block, vro->op1); | |
ce94d354 RG |
3951 | if (vro->op2 && TREE_CODE (vro->op2) == SSA_NAME) |
3952 | add_to_exp_gen (block, vro->op2); | |
726a989a RB |
3953 | } |
3954 | result = (pre_expr) pool_alloc (pre_expr_pool); | |
3955 | result->kind = REFERENCE; | |
3956 | result->id = 0; | |
3957 | PRE_EXPR_REFERENCE (result) = ref; | |
3958 | ||
3959 | get_or_alloc_expression_id (result); | |
3960 | add_to_value (get_expr_value_id (result), result); | |
3961 | if (!in_fre) | |
70a6b17e | 3962 | bitmap_value_insert_into_set (EXP_GEN (block), result); |
726a989a RB |
3963 | continue; |
3964 | } | |
c9145754 | 3965 | |
726a989a RB |
3966 | case GIMPLE_ASSIGN: |
3967 | { | |
3968 | pre_expr result = NULL; | |
3969 | switch (TREE_CODE_CLASS (gimple_assign_rhs_code (stmt))) | |
3970 | { | |
3971 | case tcc_unary: | |
726a989a | 3972 | case tcc_binary: |
24a3fbbe | 3973 | case tcc_comparison: |
726a989a RB |
3974 | { |
3975 | vn_nary_op_t nary; | |
3976 | unsigned int i; | |
3977 | ||
3978 | vn_nary_op_lookup_pieces (gimple_num_ops (stmt) - 1, | |
3979 | gimple_assign_rhs_code (stmt), | |
3980 | gimple_expr_type (stmt), | |
3981 | gimple_assign_rhs1 (stmt), | |
3982 | gimple_assign_rhs2 (stmt), | |
3983 | NULL_TREE, NULL_TREE, &nary); | |
3984 | ||
3985 | if (!nary) | |
3986 | continue; | |
3987 | ||
3988 | for (i = 0; i < nary->length; i++) | |
3989 | if (TREE_CODE (nary->op[i]) == SSA_NAME) | |
3990 | add_to_exp_gen (block, nary->op[i]); | |
3991 | ||
3992 | result = (pre_expr) pool_alloc (pre_expr_pool); | |
3993 | result->kind = NARY; | |
3994 | result->id = 0; | |
3995 | PRE_EXPR_NARY (result) = nary; | |
3996 | break; | |
3997 | } | |
c9145754 | 3998 | |
726a989a RB |
3999 | case tcc_declaration: |
4000 | case tcc_reference: | |
4001 | { | |
4002 | vn_reference_t ref; | |
4003 | unsigned int i; | |
4004 | vn_reference_op_t vro; | |
4005 | ||
4006 | vn_reference_lookup (gimple_assign_rhs1 (stmt), | |
5006671f | 4007 | gimple_vuse (stmt), |
84280917 | 4008 | true, &ref); |
726a989a RB |
4009 | if (!ref) |
4010 | continue; | |
4011 | ||
4012 | for (i = 0; VEC_iterate (vn_reference_op_s, | |
4013 | ref->operands, i, | |
4014 | vro); i++) | |
c9145754 | 4015 | { |
726a989a RB |
4016 | if (vro->op0 && TREE_CODE (vro->op0) == SSA_NAME) |
4017 | add_to_exp_gen (block, vro->op0); | |
4018 | if (vro->op1 && TREE_CODE (vro->op1) == SSA_NAME) | |
4019 | add_to_exp_gen (block, vro->op1); | |
ce94d354 RG |
4020 | if (vro->op2 && TREE_CODE (vro->op2) == SSA_NAME) |
4021 | add_to_exp_gen (block, vro->op2); | |
c9145754 | 4022 | } |
726a989a RB |
4023 | result = (pre_expr) pool_alloc (pre_expr_pool); |
4024 | result->kind = REFERENCE; | |
4025 | result->id = 0; | |
4026 | PRE_EXPR_REFERENCE (result) = ref; | |
4027 | break; | |
4028 | } | |
c9145754 | 4029 | |
726a989a RB |
4030 | default: |
4031 | /* For any other statement that we don't | |
4032 | recognize, simply add all referenced | |
4033 | SSA_NAMEs to EXP_GEN. */ | |
4034 | FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_USE) | |
4035 | add_to_exp_gen (block, op); | |
4036 | continue; | |
c9145754 | 4037 | } |
726a989a RB |
4038 | |
4039 | get_or_alloc_expression_id (result); | |
4040 | add_to_value (get_expr_value_id (result), result); | |
4041 | if (!in_fre) | |
70a6b17e | 4042 | bitmap_value_insert_into_set (EXP_GEN (block), result); |
726a989a | 4043 | |
dda243de | 4044 | continue; |
c9145754 DB |
4045 | } |
4046 | default: | |
4047 | break; | |
7e6eb623 | 4048 | } |
6de9cd9a | 4049 | } |
726a989a | 4050 | |
665fcad8 SB |
4051 | /* Put the dominator children of BLOCK on the worklist of blocks |
4052 | to compute available sets for. */ | |
4053 | for (son = first_dom_son (CDI_DOMINATORS, block); | |
4054 | son; | |
4055 | son = next_dom_son (CDI_DOMINATORS, son)) | |
4056 | worklist[sp++] = son; | |
6de9cd9a | 4057 | } |
33c94679 | 4058 | |
665fcad8 | 4059 | free (worklist); |
7e6eb623 DB |
4060 | } |
4061 | ||
3d45dd59 RG |
4062 | /* Insert the expression for SSA_VN that SCCVN thought would be simpler |
4063 | than the available expressions for it. The insertion point is | |
4064 | right before the first use in STMT. Returns the SSA_NAME that should | |
4065 | be used for replacement. */ | |
4066 | ||
4067 | static tree | |
726a989a | 4068 | do_SCCVN_insertion (gimple stmt, tree ssa_vn) |
3d45dd59 | 4069 | { |
726a989a RB |
4070 | basic_block bb = gimple_bb (stmt); |
4071 | gimple_stmt_iterator gsi; | |
4072 | gimple_seq stmts = NULL; | |
4073 | tree expr; | |
c9145754 | 4074 | pre_expr e; |
3d45dd59 RG |
4075 | |
4076 | /* First create a value expression from the expression we want | |
4077 | to insert and associate it with the value handle for SSA_VN. */ | |
726a989a | 4078 | e = get_or_alloc_expr_for (vn_get_expr_for (ssa_vn)); |
c9145754 | 4079 | if (e == NULL) |
3d45dd59 | 4080 | return NULL_TREE; |
3d45dd59 | 4081 | |
726a989a | 4082 | /* Then use create_expression_by_pieces to generate a valid |
3d45dd59 | 4083 | expression to insert at this point of the IL stream. */ |
726a989a | 4084 | expr = create_expression_by_pieces (bb, e, &stmts, stmt, NULL); |
3d45dd59 RG |
4085 | if (expr == NULL_TREE) |
4086 | return NULL_TREE; | |
726a989a RB |
4087 | gsi = gsi_for_stmt (stmt); |
4088 | gsi_insert_seq_before (&gsi, stmts, GSI_SAME_STMT); | |
3d45dd59 RG |
4089 | |
4090 | return expr; | |
4091 | } | |
33c94679 | 4092 | |
7e6eb623 DB |
4093 | /* Eliminate fully redundant computations. */ |
4094 | ||
b80280f2 | 4095 | static unsigned int |
7e6eb623 DB |
4096 | eliminate (void) |
4097 | { | |
5006671f | 4098 | VEC (gimple, heap) *to_remove = NULL; |
7e6eb623 | 4099 | basic_block b; |
b80280f2 | 4100 | unsigned int todo = 0; |
5006671f RG |
4101 | gimple_stmt_iterator gsi; |
4102 | gimple stmt; | |
4103 | unsigned i; | |
7e6eb623 DB |
4104 | |
4105 | FOR_EACH_BB (b) | |
4106 | { | |
5006671f | 4107 | for (gsi = gsi_start_bb (b); !gsi_end_p (gsi); gsi_next (&gsi)) |
83737db2 | 4108 | { |
5006671f | 4109 | stmt = gsi_stmt (gsi); |
7e6eb623 | 4110 | |
ff2ad0f7 DN |
4111 | /* Lookup the RHS of the expression, see if we have an |
4112 | available computation for it. If so, replace the RHS with | |
7e6eb623 | 4113 | the available computation. */ |
726a989a RB |
4114 | if (gimple_has_lhs (stmt) |
4115 | && TREE_CODE (gimple_get_lhs (stmt)) == SSA_NAME | |
4116 | && !gimple_assign_ssa_name_copy_p (stmt) | |
4117 | && (!gimple_assign_single_p (stmt) | |
4118 | || !is_gimple_min_invariant (gimple_assign_rhs1 (stmt))) | |
4119 | && !gimple_has_volatile_ops (stmt) | |
4120 | && !has_zero_uses (gimple_get_lhs (stmt))) | |
ff2ad0f7 | 4121 | { |
726a989a RB |
4122 | tree lhs = gimple_get_lhs (stmt); |
4123 | tree rhs = NULL_TREE; | |
c9145754 DB |
4124 | tree sprime = NULL; |
4125 | pre_expr lhsexpr = get_or_alloc_expr_for_name (lhs); | |
4126 | pre_expr sprimeexpr; | |
4127 | ||
726a989a RB |
4128 | if (gimple_assign_single_p (stmt)) |
4129 | rhs = gimple_assign_rhs1 (stmt); | |
4130 | ||
c9145754 DB |
4131 | sprimeexpr = bitmap_find_leader (AVAIL_OUT (b), |
4132 | get_expr_value_id (lhsexpr), | |
726a989a | 4133 | NULL); |
c9145754 DB |
4134 | |
4135 | if (sprimeexpr) | |
4136 | { | |
4137 | if (sprimeexpr->kind == CONSTANT) | |
4138 | sprime = PRE_EXPR_CONSTANT (sprimeexpr); | |
4139 | else if (sprimeexpr->kind == NAME) | |
4140 | sprime = PRE_EXPR_NAME (sprimeexpr); | |
4141 | else | |
4142 | gcc_unreachable (); | |
4143 | } | |
6999afe1 | 4144 | |
c9145754 DB |
4145 | /* If there is no existing leader but SCCVN knows this |
4146 | value is constant, use that constant. */ | |
4147 | if (!sprime && is_gimple_min_invariant (VN_INFO (lhs)->valnum)) | |
4148 | { | |
7e673273 RG |
4149 | sprime = VN_INFO (lhs)->valnum; |
4150 | if (!useless_type_conversion_p (TREE_TYPE (lhs), | |
4151 | TREE_TYPE (sprime))) | |
4152 | sprime = fold_convert (TREE_TYPE (lhs), sprime); | |
ff2ad0f7 | 4153 | |
c9145754 DB |
4154 | if (dump_file && (dump_flags & TDF_DETAILS)) |
4155 | { | |
4156 | fprintf (dump_file, "Replaced "); | |
726a989a | 4157 | print_gimple_expr (dump_file, stmt, 0, 0); |
c9145754 DB |
4158 | fprintf (dump_file, " with "); |
4159 | print_generic_expr (dump_file, sprime, 0); | |
4160 | fprintf (dump_file, " in "); | |
726a989a | 4161 | print_gimple_stmt (dump_file, stmt, 0, 0); |
c9145754 DB |
4162 | } |
4163 | pre_stats.eliminations++; | |
5006671f RG |
4164 | propagate_tree_value_into_stmt (&gsi, sprime); |
4165 | stmt = gsi_stmt (gsi); | |
c9145754 DB |
4166 | update_stmt (stmt); |
4167 | continue; | |
4168 | } | |
3d45dd59 RG |
4169 | |
4170 | /* If there is no existing usable leader but SCCVN thinks | |
4171 | it has an expression it wants to use as replacement, | |
4172 | insert that. */ | |
c9145754 | 4173 | if (!sprime || sprime == lhs) |
3d45dd59 RG |
4174 | { |
4175 | tree val = VN_INFO (lhs)->valnum; | |
4176 | if (val != VN_TOP | |
c9145754 | 4177 | && TREE_CODE (val) == SSA_NAME |
3d45dd59 | 4178 | && VN_INFO (val)->needs_insertion |
726a989a | 4179 | && can_PRE_operation (vn_get_expr_for (val))) |
3d45dd59 RG |
4180 | sprime = do_SCCVN_insertion (stmt, val); |
4181 | } | |
b9c5e484 | 4182 | if (sprime |
ff2ad0f7 | 4183 | && sprime != lhs |
726a989a RB |
4184 | && (rhs == NULL_TREE |
4185 | || TREE_CODE (rhs) != SSA_NAME | |
4186 | || may_propagate_copy (rhs, sprime))) | |
ff2ad0f7 | 4187 | { |
726a989a | 4188 | gcc_assert (sprime != rhs); |
ff2ad0f7 | 4189 | |
7e6eb623 DB |
4190 | if (dump_file && (dump_flags & TDF_DETAILS)) |
4191 | { | |
4192 | fprintf (dump_file, "Replaced "); | |
726a989a | 4193 | print_gimple_expr (dump_file, stmt, 0, 0); |
7e6eb623 DB |
4194 | fprintf (dump_file, " with "); |
4195 | print_generic_expr (dump_file, sprime, 0); | |
4196 | fprintf (dump_file, " in "); | |
726a989a | 4197 | print_gimple_stmt (dump_file, stmt, 0, 0); |
7e6eb623 | 4198 | } |
b9c5e484 EC |
4199 | |
4200 | if (TREE_CODE (sprime) == SSA_NAME) | |
726a989a RB |
4201 | gimple_set_plf (SSA_NAME_DEF_STMT (sprime), |
4202 | NECESSARY, true); | |
fe83f543 AP |
4203 | /* We need to make sure the new and old types actually match, |
4204 | which may require adding a simple cast, which fold_convert | |
4205 | will do for us. */ | |
726a989a RB |
4206 | if ((!rhs || TREE_CODE (rhs) != SSA_NAME) |
4207 | && !useless_type_conversion_p (gimple_expr_type (stmt), | |
4208 | TREE_TYPE (sprime))) | |
4209 | sprime = fold_convert (gimple_expr_type (stmt), sprime); | |
b9c5e484 | 4210 | |
7e6eb623 | 4211 | pre_stats.eliminations++; |
5006671f RG |
4212 | propagate_tree_value_into_stmt (&gsi, sprime); |
4213 | stmt = gsi_stmt (gsi); | |
f430bae8 | 4214 | update_stmt (stmt); |
53b4bf74 DN |
4215 | |
4216 | /* If we removed EH side effects from the statement, clean | |
4217 | its EH information. */ | |
af47810a | 4218 | if (maybe_clean_or_replace_eh_stmt (stmt, stmt)) |
53b4bf74 DN |
4219 | { |
4220 | bitmap_set_bit (need_eh_cleanup, | |
726a989a | 4221 | gimple_bb (stmt)->index); |
53b4bf74 DN |
4222 | if (dump_file && (dump_flags & TDF_DETAILS)) |
4223 | fprintf (dump_file, " Removed EH side effects.\n"); | |
4224 | } | |
ff2ad0f7 DN |
4225 | } |
4226 | } | |
6cdb0ee3 RG |
4227 | /* If the statement is a scalar store, see if the expression |
4228 | has the same value number as its rhs. If so, the store is | |
4229 | dead. */ | |
4230 | else if (gimple_assign_single_p (stmt) | |
4231 | && !is_gimple_reg (gimple_assign_lhs (stmt)) | |
4232 | && (TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME | |
4233 | || is_gimple_min_invariant (gimple_assign_rhs1 (stmt)))) | |
4234 | { | |
4235 | tree rhs = gimple_assign_rhs1 (stmt); | |
4236 | tree val; | |
4237 | val = vn_reference_lookup (gimple_assign_lhs (stmt), | |
5006671f | 4238 | gimple_vuse (stmt), true, NULL); |
6cdb0ee3 RG |
4239 | if (TREE_CODE (rhs) == SSA_NAME) |
4240 | rhs = VN_INFO (rhs)->valnum; | |
4241 | if (val | |
4242 | && operand_equal_p (val, rhs, 0)) | |
4243 | { | |
6cdb0ee3 RG |
4244 | if (dump_file && (dump_flags & TDF_DETAILS)) |
4245 | { | |
5006671f | 4246 | fprintf (dump_file, "Deleted redundant store "); |
6cdb0ee3 RG |
4247 | print_gimple_stmt (dump_file, stmt, 0, 0); |
4248 | } | |
4249 | ||
5006671f RG |
4250 | /* Queue stmt for removal. */ |
4251 | VEC_safe_push (gimple, heap, to_remove, stmt); | |
6cdb0ee3 RG |
4252 | } |
4253 | } | |
b80280f2 RG |
4254 | /* Visit COND_EXPRs and fold the comparison with the |
4255 | available value-numbers. */ | |
726a989a | 4256 | else if (gimple_code (stmt) == GIMPLE_COND) |
b80280f2 | 4257 | { |
726a989a RB |
4258 | tree op0 = gimple_cond_lhs (stmt); |
4259 | tree op1 = gimple_cond_rhs (stmt); | |
b80280f2 RG |
4260 | tree result; |
4261 | ||
4262 | if (TREE_CODE (op0) == SSA_NAME) | |
4263 | op0 = VN_INFO (op0)->valnum; | |
4264 | if (TREE_CODE (op1) == SSA_NAME) | |
4265 | op1 = VN_INFO (op1)->valnum; | |
726a989a | 4266 | result = fold_binary (gimple_cond_code (stmt), boolean_type_node, |
b80280f2 RG |
4267 | op0, op1); |
4268 | if (result && TREE_CODE (result) == INTEGER_CST) | |
4269 | { | |
726a989a RB |
4270 | if (integer_zerop (result)) |
4271 | gimple_cond_make_false (stmt); | |
4272 | else | |
4273 | gimple_cond_make_true (stmt); | |
b80280f2 RG |
4274 | update_stmt (stmt); |
4275 | todo = TODO_cleanup_cfg; | |
4276 | } | |
4277 | } | |
aa7069aa RG |
4278 | /* Visit indirect calls and turn them into direct calls if |
4279 | possible. */ | |
4280 | if (gimple_code (stmt) == GIMPLE_CALL | |
4281 | && TREE_CODE (gimple_call_fn (stmt)) == SSA_NAME) | |
4282 | { | |
4283 | tree fn = VN_INFO (gimple_call_fn (stmt))->valnum; | |
4284 | if (TREE_CODE (fn) == ADDR_EXPR | |
4285 | && TREE_CODE (TREE_OPERAND (fn, 0)) == FUNCTION_DECL) | |
4286 | { | |
4287 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
4288 | { | |
4289 | fprintf (dump_file, "Replacing call target with "); | |
4290 | print_generic_expr (dump_file, fn, 0); | |
4291 | fprintf (dump_file, " in "); | |
4292 | print_gimple_stmt (dump_file, stmt, 0, 0); | |
4293 | } | |
4294 | ||
4295 | gimple_call_set_fn (stmt, fn); | |
4296 | update_stmt (stmt); | |
4297 | if (maybe_clean_or_replace_eh_stmt (stmt, stmt)) | |
55194b0b RG |
4298 | { |
4299 | bitmap_set_bit (need_eh_cleanup, | |
4300 | gimple_bb (stmt)->index); | |
4301 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
4302 | fprintf (dump_file, " Removed EH side effects.\n"); | |
4303 | } | |
de0b4ad5 RG |
4304 | |
4305 | /* Changing an indirect call to a direct call may | |
4306 | have exposed different semantics. This may | |
4307 | require an SSA update. */ | |
7ffa47ca | 4308 | todo |= TODO_update_ssa_only_virtuals; |
aa7069aa RG |
4309 | } |
4310 | } | |
83737db2 | 4311 | } |
439ef907 RG |
4312 | |
4313 | for (gsi = gsi_start_phis (b); !gsi_end_p (gsi);) | |
4314 | { | |
4315 | gimple stmt, phi = gsi_stmt (gsi); | |
4316 | tree sprime = NULL_TREE, res = PHI_RESULT (phi); | |
4317 | pre_expr sprimeexpr, resexpr; | |
4318 | gimple_stmt_iterator gsi2; | |
4319 | ||
4320 | /* We want to perform redundant PHI elimination. Do so by | |
4321 | replacing the PHI with a single copy if possible. | |
4322 | Do not touch inserted, single-argument or virtual PHIs. */ | |
4323 | if (gimple_phi_num_args (phi) == 1 | |
4324 | || !is_gimple_reg (res) | |
4325 | || bitmap_bit_p (inserted_phi_names, SSA_NAME_VERSION (res))) | |
4326 | { | |
4327 | gsi_next (&gsi); | |
4328 | continue; | |
4329 | } | |
4330 | ||
4331 | resexpr = get_or_alloc_expr_for_name (res); | |
4332 | sprimeexpr = bitmap_find_leader (AVAIL_OUT (b), | |
4333 | get_expr_value_id (resexpr), NULL); | |
4334 | if (sprimeexpr) | |
4335 | { | |
4336 | if (sprimeexpr->kind == CONSTANT) | |
4337 | sprime = PRE_EXPR_CONSTANT (sprimeexpr); | |
4338 | else if (sprimeexpr->kind == NAME) | |
4339 | sprime = PRE_EXPR_NAME (sprimeexpr); | |
4340 | else | |
4341 | gcc_unreachable (); | |
4342 | } | |
4343 | if (!sprimeexpr | |
4344 | || sprime == res) | |
4345 | { | |
4346 | gsi_next (&gsi); | |
4347 | continue; | |
4348 | } | |
4349 | ||
4350 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
4351 | { | |
4352 | fprintf (dump_file, "Replaced redundant PHI node defining "); | |
4353 | print_generic_expr (dump_file, res, 0); | |
4354 | fprintf (dump_file, " with "); | |
4355 | print_generic_expr (dump_file, sprime, 0); | |
4356 | fprintf (dump_file, "\n"); | |
4357 | } | |
4358 | ||
4359 | remove_phi_node (&gsi, false); | |
4360 | ||
f116fecf RG |
4361 | if (!useless_type_conversion_p (TREE_TYPE (res), TREE_TYPE (sprime))) |
4362 | sprime = fold_convert (TREE_TYPE (res), sprime); | |
439ef907 RG |
4363 | stmt = gimple_build_assign (res, sprime); |
4364 | SSA_NAME_DEF_STMT (res) = stmt; | |
4365 | if (TREE_CODE (sprime) == SSA_NAME) | |
4366 | gimple_set_plf (SSA_NAME_DEF_STMT (sprime), | |
4367 | NECESSARY, true); | |
4368 | gsi2 = gsi_after_labels (b); | |
4369 | gsi_insert_before (&gsi2, stmt, GSI_NEW_STMT); | |
4370 | /* Queue the copy for eventual removal. */ | |
4371 | VEC_safe_push (gimple, heap, to_remove, stmt); | |
4372 | pre_stats.eliminations++; | |
4373 | } | |
7e6eb623 | 4374 | } |
b80280f2 | 4375 | |
5006671f | 4376 | /* We cannot remove stmts during BB walk, especially not release SSA |
439ef907 RG |
4377 | names there as this confuses the VN machinery. The stmts ending |
4378 | up in to_remove are either stores or simple copies. */ | |
5006671f RG |
4379 | for (i = 0; VEC_iterate (gimple, to_remove, i, stmt); ++i) |
4380 | { | |
439ef907 RG |
4381 | tree lhs = gimple_assign_lhs (stmt); |
4382 | use_operand_p use_p; | |
4383 | gimple use_stmt; | |
4384 | ||
4385 | /* If there is a single use only, propagate the equivalency | |
4386 | instead of keeping the copy. */ | |
4387 | if (TREE_CODE (lhs) == SSA_NAME | |
85e59f3a RG |
4388 | && single_imm_use (lhs, &use_p, &use_stmt) |
4389 | && may_propagate_copy (USE_FROM_PTR (use_p), | |
4390 | gimple_assign_rhs1 (stmt))) | |
439ef907 RG |
4391 | { |
4392 | SET_USE (use_p, gimple_assign_rhs1 (stmt)); | |
b4104018 | 4393 | update_stmt (use_stmt); |
439ef907 RG |
4394 | } |
4395 | ||
4396 | /* If this is a store or a now unused copy, remove it. */ | |
4397 | if (TREE_CODE (lhs) != SSA_NAME | |
4398 | || has_zero_uses (lhs)) | |
4399 | { | |
4400 | gsi = gsi_for_stmt (stmt); | |
4401 | unlink_stmt_vdef (stmt); | |
4402 | gsi_remove (&gsi, true); | |
4403 | release_defs (stmt); | |
4404 | } | |
5006671f RG |
4405 | } |
4406 | VEC_free (gimple, heap, to_remove); | |
4407 | ||
b80280f2 | 4408 | return todo; |
6de9cd9a DN |
4409 | } |
4410 | ||
0fc6c492 DB |
4411 | /* Borrow a bit of tree-ssa-dce.c for the moment. |
4412 | XXX: In 4.1, we should be able to just run a DCE pass after PRE, though | |
4413 | this may be a bit faster, and we may want critical edges kept split. */ | |
4414 | ||
4415 | /* If OP's defining statement has not already been determined to be necessary, | |
d4e6fecb | 4416 | mark that statement necessary. Return the stmt, if it is newly |
b9c5e484 | 4417 | necessary. */ |
0fc6c492 | 4418 | |
726a989a | 4419 | static inline gimple |
d4e6fecb | 4420 | mark_operand_necessary (tree op) |
0fc6c492 | 4421 | { |
726a989a | 4422 | gimple stmt; |
0fc6c492 DB |
4423 | |
4424 | gcc_assert (op); | |
4425 | ||
c90186eb DB |
4426 | if (TREE_CODE (op) != SSA_NAME) |
4427 | return NULL; | |
4428 | ||
0fc6c492 DB |
4429 | stmt = SSA_NAME_DEF_STMT (op); |
4430 | gcc_assert (stmt); | |
4431 | ||
726a989a RB |
4432 | if (gimple_plf (stmt, NECESSARY) |
4433 | || gimple_nop_p (stmt)) | |
d4e6fecb | 4434 | return NULL; |
0fc6c492 | 4435 | |
726a989a | 4436 | gimple_set_plf (stmt, NECESSARY, true); |
d4e6fecb | 4437 | return stmt; |
0fc6c492 DB |
4438 | } |
4439 | ||
4440 | /* Because we don't follow exactly the standard PRE algorithm, and decide not | |
4441 | to insert PHI nodes sometimes, and because value numbering of casts isn't | |
4442 | perfect, we sometimes end up inserting dead code. This simple DCE-like | |
4443 | pass removes any insertions we made that weren't actually used. */ | |
4444 | ||
4445 | static void | |
4446 | remove_dead_inserted_code (void) | |
4447 | { | |
726a989a | 4448 | VEC(gimple,heap) *worklist = NULL; |
0fc6c492 | 4449 | int i; |
726a989a | 4450 | gimple t; |
0fc6c492 | 4451 | |
726a989a RB |
4452 | worklist = VEC_alloc (gimple, heap, VEC_length (gimple, inserted_exprs)); |
4453 | for (i = 0; VEC_iterate (gimple, inserted_exprs, i, t); i++) | |
0fc6c492 | 4454 | { |
726a989a RB |
4455 | if (gimple_plf (t, NECESSARY)) |
4456 | VEC_quick_push (gimple, worklist, t); | |
0fc6c492 | 4457 | } |
726a989a | 4458 | while (VEC_length (gimple, worklist) > 0) |
0fc6c492 | 4459 | { |
726a989a | 4460 | t = VEC_pop (gimple, worklist); |
c90186eb DB |
4461 | |
4462 | /* PHI nodes are somewhat special in that each PHI alternative has | |
4463 | data and control dependencies. All the statements feeding the | |
4464 | PHI node's arguments are always necessary. */ | |
726a989a | 4465 | if (gimple_code (t) == GIMPLE_PHI) |
0fc6c492 | 4466 | { |
726a989a | 4467 | unsigned k; |
d4e6fecb | 4468 | |
726a989a RB |
4469 | VEC_reserve (gimple, heap, worklist, gimple_phi_num_args (t)); |
4470 | for (k = 0; k < gimple_phi_num_args (t); k++) | |
83737db2 | 4471 | { |
0fc6c492 DB |
4472 | tree arg = PHI_ARG_DEF (t, k); |
4473 | if (TREE_CODE (arg) == SSA_NAME) | |
d4e6fecb | 4474 | { |
726a989a RB |
4475 | gimple n = mark_operand_necessary (arg); |
4476 | if (n) | |
4477 | VEC_quick_push (gimple, worklist, n); | |
d4e6fecb | 4478 | } |
0fc6c492 DB |
4479 | } |
4480 | } | |
4481 | else | |
4482 | { | |
4483 | /* Propagate through the operands. Examine all the USE, VUSE and | |
89fb70a3 | 4484 | VDEF operands in this statement. Mark all the statements |
0fc6c492 DB |
4485 | which feed this statement's uses as necessary. */ |
4486 | ssa_op_iter iter; | |
4487 | tree use; | |
4488 | ||
38635499 | 4489 | /* The operands of VDEF expressions are also needed as they |
0fc6c492 | 4490 | represent potential definitions that may reach this |
89fb70a3 | 4491 | statement (VDEF operands allow us to follow def-def |
0fc6c492 | 4492 | links). */ |
33c94679 | 4493 | |
0fc6c492 | 4494 | FOR_EACH_SSA_TREE_OPERAND (use, t, iter, SSA_OP_ALL_USES) |
d4e6fecb | 4495 | { |
726a989a | 4496 | gimple n = mark_operand_necessary (use); |
d4e6fecb | 4497 | if (n) |
726a989a | 4498 | VEC_safe_push (gimple, heap, worklist, n); |
d4e6fecb | 4499 | } |
0fc6c492 DB |
4500 | } |
4501 | } | |
c90186eb | 4502 | |
726a989a | 4503 | for (i = 0; VEC_iterate (gimple, inserted_exprs, i, t); i++) |
0fc6c492 | 4504 | { |
726a989a | 4505 | if (!gimple_plf (t, NECESSARY)) |
0fc6c492 | 4506 | { |
726a989a | 4507 | gimple_stmt_iterator gsi; |
c90186eb | 4508 | |
0fc6c492 DB |
4509 | if (dump_file && (dump_flags & TDF_DETAILS)) |
4510 | { | |
4511 | fprintf (dump_file, "Removing unnecessary insertion:"); | |
726a989a | 4512 | print_gimple_stmt (dump_file, t, 0, 0); |
0fc6c492 | 4513 | } |
c90186eb | 4514 | |
726a989a RB |
4515 | gsi = gsi_for_stmt (t); |
4516 | if (gimple_code (t) == GIMPLE_PHI) | |
4517 | remove_phi_node (&gsi, true); | |
0fc6c492 | 4518 | else |
b70fdfe4 AO |
4519 | { |
4520 | gsi_remove (&gsi, true); | |
4521 | release_defs (t); | |
4522 | } | |
0fc6c492 DB |
4523 | } |
4524 | } | |
726a989a | 4525 | VEC_free (gimple, heap, worklist); |
0fc6c492 | 4526 | } |
c90186eb | 4527 | |
9ca87236 RB |
4528 | /* Compute a reverse post-order in *POST_ORDER. If INCLUDE_ENTRY_EXIT is |
4529 | true, then then ENTRY_BLOCK and EXIT_BLOCK are included. Returns | |
4530 | the number of visited blocks. */ | |
4531 | ||
4532 | static int | |
4533 | my_rev_post_order_compute (int *post_order, bool include_entry_exit) | |
4534 | { | |
4535 | edge_iterator *stack; | |
4536 | int sp; | |
4537 | int post_order_num = 0; | |
4538 | sbitmap visited; | |
4539 | int count; | |
4540 | ||
4541 | if (include_entry_exit) | |
4542 | post_order[post_order_num++] = EXIT_BLOCK; | |
4543 | ||
4544 | /* Allocate stack for back-tracking up CFG. */ | |
4545 | stack = XNEWVEC (edge_iterator, n_basic_blocks + 1); | |
4546 | sp = 0; | |
4547 | ||
4548 | /* Allocate bitmap to track nodes that have been visited. */ | |
4549 | visited = sbitmap_alloc (last_basic_block); | |
4550 | ||
4551 | /* None of the nodes in the CFG have been visited yet. */ | |
4552 | sbitmap_zero (visited); | |
4553 | ||
4554 | /* Push the last edge on to the stack. */ | |
4555 | stack[sp++] = ei_start (EXIT_BLOCK_PTR->preds); | |
4556 | ||
4557 | while (sp) | |
4558 | { | |
4559 | edge_iterator ei; | |
4560 | basic_block src; | |
4561 | basic_block dest; | |
4562 | ||
4563 | /* Look at the edge on the top of the stack. */ | |
4564 | ei = stack[sp - 1]; | |
4565 | src = ei_edge (ei)->src; | |
4566 | dest = ei_edge (ei)->dest; | |
4567 | ||
4568 | /* Check if the edge destination has been visited yet. */ | |
4569 | if (src != ENTRY_BLOCK_PTR && ! TEST_BIT (visited, src->index)) | |
4570 | { | |
4571 | /* Mark that we have visited the destination. */ | |
4572 | SET_BIT (visited, src->index); | |
4573 | ||
4574 | if (EDGE_COUNT (src->preds) > 0) | |
4575 | /* Since the DEST node has been visited for the first | |
4576 | time, check its successors. */ | |
4577 | stack[sp++] = ei_start (src->preds); | |
4578 | else | |
4579 | post_order[post_order_num++] = src->index; | |
4580 | } | |
4581 | else | |
4582 | { | |
4583 | if (ei_one_before_end_p (ei) && dest != EXIT_BLOCK_PTR) | |
4584 | post_order[post_order_num++] = dest->index; | |
4585 | ||
4586 | if (!ei_one_before_end_p (ei)) | |
4587 | ei_next (&stack[sp - 1]); | |
4588 | else | |
4589 | sp--; | |
4590 | } | |
4591 | } | |
4592 | ||
4593 | if (include_entry_exit) | |
4594 | { | |
4595 | post_order[post_order_num++] = ENTRY_BLOCK; | |
4596 | count = post_order_num; | |
4597 | } | |
4598 | else | |
4599 | count = post_order_num + 2; | |
4600 | ||
4601 | free (stack); | |
4602 | sbitmap_free (visited); | |
4603 | return post_order_num; | |
4604 | } | |
4605 | ||
4606 | ||
ff2ad0f7 | 4607 | /* Initialize data structures used by PRE. */ |
6de9cd9a DN |
4608 | |
4609 | static void | |
0fc6c492 | 4610 | init_pre (bool do_fre) |
6de9cd9a | 4611 | { |
c9145754 DB |
4612 | basic_block bb; |
4613 | ||
4614 | next_expression_id = 1; | |
4615 | expressions = NULL; | |
4616 | VEC_safe_push (pre_expr, heap, expressions, NULL); | |
4617 | value_expressions = VEC_alloc (bitmap_set_t, heap, get_max_value_id () + 1); | |
4618 | VEC_safe_grow_cleared (bitmap_set_t, heap, value_expressions, | |
4619 | get_max_value_id() + 1); | |
13de9095 | 4620 | name_to_id = NULL; |
c9145754 | 4621 | |
81def1b7 | 4622 | in_fre = do_fre; |
ff2ad0f7 | 4623 | |
0fc6c492 | 4624 | inserted_exprs = NULL; |
c90186eb DB |
4625 | need_creation = NULL; |
4626 | pretemp = NULL_TREE; | |
4627 | storetemp = NULL_TREE; | |
c90186eb DB |
4628 | prephitemp = NULL_TREE; |
4629 | ||
b71b4522 DB |
4630 | connect_infinite_loops_to_exit (); |
4631 | memset (&pre_stats, 0, sizeof (pre_stats)); | |
4632 | ||
c9145754 DB |
4633 | |
4634 | postorder = XNEWVEC (int, n_basic_blocks - NUM_FIXED_BLOCKS); | |
9ca87236 | 4635 | my_rev_post_order_compute (postorder, false); |
c9145754 DB |
4636 | |
4637 | FOR_ALL_BB (bb) | |
4638 | bb->aux = XCNEWVEC (struct bb_bitmap_sets, 1); | |
4639 | ||
b71b4522 | 4640 | calculate_dominance_info (CDI_POST_DOMINATORS); |
d75dbccd DB |
4641 | calculate_dominance_info (CDI_DOMINATORS); |
4642 | ||
c9145754 | 4643 | bitmap_obstack_initialize (&grand_bitmap_obstack); |
439ef907 | 4644 | inserted_phi_names = BITMAP_ALLOC (&grand_bitmap_obstack); |
c9145754 DB |
4645 | phi_translate_table = htab_create (5110, expr_pred_trans_hash, |
4646 | expr_pred_trans_eq, free); | |
4647 | expression_to_id = htab_create (num_ssa_names * 3, | |
4648 | pre_expr_hash, | |
4649 | pre_expr_eq, NULL); | |
c9145754 DB |
4650 | bitmap_set_pool = create_alloc_pool ("Bitmap sets", |
4651 | sizeof (struct bitmap_set), 30); | |
4652 | pre_expr_pool = create_alloc_pool ("pre_expr nodes", | |
4653 | sizeof (struct pre_expr_d), 30); | |
4654 | FOR_ALL_BB (bb) | |
4655 | { | |
4656 | EXP_GEN (bb) = bitmap_set_new (); | |
4657 | PHI_GEN (bb) = bitmap_set_new (); | |
4658 | TMP_GEN (bb) = bitmap_set_new (); | |
4659 | AVAIL_OUT (bb) = bitmap_set_new (); | |
4660 | } | |
d75dbccd | 4661 | |
8bdbfff5 | 4662 | need_eh_cleanup = BITMAP_ALLOC (NULL); |
ff2ad0f7 DN |
4663 | } |
4664 | ||
4665 | ||
4666 | /* Deallocate data structures used by PRE. */ | |
6de9cd9a | 4667 | |
ff2ad0f7 | 4668 | static void |
678e7c65 | 4669 | fini_pre (bool do_fre) |
ff2ad0f7 | 4670 | { |
c9145754 | 4671 | basic_block bb; |
b71b4522 | 4672 | |
c9145754 DB |
4673 | free (postorder); |
4674 | VEC_free (bitmap_set_t, heap, value_expressions); | |
726a989a RB |
4675 | VEC_free (gimple, heap, inserted_exprs); |
4676 | VEC_free (gimple, heap, need_creation); | |
c9145754 DB |
4677 | bitmap_obstack_release (&grand_bitmap_obstack); |
4678 | free_alloc_pool (bitmap_set_pool); | |
4679 | free_alloc_pool (pre_expr_pool); | |
b71b4522 | 4680 | htab_delete (phi_translate_table); |
c9145754 | 4681 | htab_delete (expression_to_id); |
13de9095 | 4682 | VEC_free (unsigned, heap, name_to_id); |
50265400 | 4683 | |
c9145754 DB |
4684 | FOR_ALL_BB (bb) |
4685 | { | |
4686 | free (bb->aux); | |
4687 | bb->aux = NULL; | |
4688 | } | |
6809cbf9 | 4689 | |
b71b4522 DB |
4690 | free_dominance_info (CDI_POST_DOMINATORS); |
4691 | ||
eb59b8de | 4692 | if (!bitmap_empty_p (need_eh_cleanup)) |
53b4bf74 | 4693 | { |
726a989a | 4694 | gimple_purge_all_dead_eh_edges (need_eh_cleanup); |
53b4bf74 DN |
4695 | cleanup_tree_cfg (); |
4696 | } | |
4697 | ||
8bdbfff5 | 4698 | BITMAP_FREE (need_eh_cleanup); |
b71b4522 | 4699 | |
678e7c65 | 4700 | if (!do_fre) |
598ec7bd | 4701 | loop_optimizer_finalize (); |
ff2ad0f7 DN |
4702 | } |
4703 | ||
ff2ad0f7 DN |
4704 | /* Main entry point to the SSA-PRE pass. DO_FRE is true if the caller |
4705 | only wants to do full redundancy elimination. */ | |
4706 | ||
b80280f2 | 4707 | static unsigned int |
5813994e | 4708 | execute_pre (bool do_fre) |
ff2ad0f7 | 4709 | { |
b80280f2 | 4710 | unsigned int todo = 0; |
83737db2 | 4711 | |
5813994e | 4712 | do_partial_partial = optimize > 2 && optimize_function_for_speed_p (cfun); |
ff2ad0f7 | 4713 | |
c9145754 DB |
4714 | /* This has to happen before SCCVN runs because |
4715 | loop_optimizer_init may create new phis, etc. */ | |
c90186eb | 4716 | if (!do_fre) |
c9145754 | 4717 | loop_optimizer_init (LOOPS_NORMAL); |
c90186eb | 4718 | |
3d45dd59 | 4719 | if (!run_scc_vn (do_fre)) |
863d2a57 RG |
4720 | { |
4721 | if (!do_fre) | |
6999afe1 DB |
4722 | { |
4723 | remove_dead_inserted_code (); | |
4724 | loop_optimizer_finalize (); | |
4725 | } | |
b8698a0f | 4726 | |
b80280f2 | 4727 | return 0; |
863d2a57 | 4728 | } |
c9145754 | 4729 | init_pre (do_fre); |
a8338640 | 4730 | scev_initialize (); |
c9145754 DB |
4731 | |
4732 | ||
4733 | /* Collect and value number expressions computed in each basic block. */ | |
665fcad8 | 4734 | compute_avail (); |
6de9cd9a | 4735 | |
7e6eb623 DB |
4736 | if (dump_file && (dump_flags & TDF_DETAILS)) |
4737 | { | |
ff2ad0f7 DN |
4738 | basic_block bb; |
4739 | ||
7e6eb623 DB |
4740 | FOR_ALL_BB (bb) |
4741 | { | |
83737db2 | 4742 | print_bitmap_set (dump_file, EXP_GEN (bb), "exp_gen", bb->index); |
7763473e RG |
4743 | print_bitmap_set (dump_file, PHI_GEN (bb), "phi_gen", bb->index); |
4744 | print_bitmap_set (dump_file, TMP_GEN (bb), "tmp_gen", bb->index); | |
4745 | print_bitmap_set (dump_file, AVAIL_OUT (bb), "avail_out", bb->index); | |
7e6eb623 DB |
4746 | } |
4747 | } | |
6de9cd9a | 4748 | |
7e6eb623 DB |
4749 | /* Insert can get quite slow on an incredibly large number of basic |
4750 | blocks due to some quadratic behavior. Until this behavior is | |
4751 | fixed, don't run it when he have an incredibly large number of | |
4752 | bb's. If we aren't going to run insert, there is no point in | |
4753 | computing ANTIC, either, even though it's plenty fast. */ | |
ff2ad0f7 | 4754 | if (!do_fre && n_basic_blocks < 4000) |
6de9cd9a | 4755 | { |
7e6eb623 | 4756 | compute_antic (); |
7e6eb623 DB |
4757 | insert (); |
4758 | } | |
ff2ad0f7 DN |
4759 | |
4760 | /* Remove all the redundant expressions. */ | |
b80280f2 | 4761 | todo |= eliminate (); |
0fc6c492 | 4762 | |
9fe0cb7d RG |
4763 | statistics_counter_event (cfun, "Insertions", pre_stats.insertions); |
4764 | statistics_counter_event (cfun, "PA inserted", pre_stats.pa_insert); | |
4765 | statistics_counter_event (cfun, "New PHIs", pre_stats.phis); | |
4766 | statistics_counter_event (cfun, "Eliminated", pre_stats.eliminations); | |
4767 | statistics_counter_event (cfun, "Constified", pre_stats.constified); | |
c4ab2baa RG |
4768 | |
4769 | /* Make sure to remove fake edges before committing our inserts. | |
4770 | This makes sure we don't end up with extra critical edges that | |
4771 | we would need to split. */ | |
4772 | remove_fake_exit_edges (); | |
726a989a | 4773 | gsi_commit_edge_inserts (); |
c90186eb | 4774 | |
b71b4522 | 4775 | clear_expression_ids (); |
3d45dd59 | 4776 | free_scc_vn (); |
0fc6c492 | 4777 | if (!do_fre) |
1961418e | 4778 | remove_dead_inserted_code (); |
c90186eb | 4779 | |
a8338640 | 4780 | scev_finalize (); |
678e7c65 | 4781 | fini_pre (do_fre); |
b80280f2 RG |
4782 | |
4783 | return todo; | |
ff2ad0f7 DN |
4784 | } |
4785 | ||
ff2ad0f7 DN |
4786 | /* Gate and execute functions for PRE. */ |
4787 | ||
c2924966 | 4788 | static unsigned int |
ff2ad0f7 DN |
4789 | do_pre (void) |
4790 | { | |
5006671f | 4791 | return execute_pre (false); |
6de9cd9a DN |
4792 | } |
4793 | ||
4794 | static bool | |
4795 | gate_pre (void) | |
4796 | { | |
5813994e | 4797 | return flag_tree_pre != 0; |
6de9cd9a DN |
4798 | } |
4799 | ||
8ddbbcae | 4800 | struct gimple_opt_pass pass_pre = |
6de9cd9a | 4801 | { |
8ddbbcae JH |
4802 | { |
4803 | GIMPLE_PASS, | |
6de9cd9a DN |
4804 | "pre", /* name */ |
4805 | gate_pre, /* gate */ | |
ff2ad0f7 | 4806 | do_pre, /* execute */ |
6de9cd9a DN |
4807 | NULL, /* sub */ |
4808 | NULL, /* next */ | |
4809 | 0, /* static_pass_number */ | |
4810 | TV_TREE_PRE, /* tv_id */ | |
c1b763fa | 4811 | PROP_no_crit_edges | PROP_cfg |
4effdf02 | 4812 | | PROP_ssa, /* properties_required */ |
6de9cd9a DN |
4813 | 0, /* properties_provided */ |
4814 | 0, /* properties_destroyed */ | |
5006671f | 4815 | TODO_rebuild_alias, /* todo_flags_start */ |
b9c5e484 | 4816 | TODO_update_ssa_only_virtuals | TODO_dump_func | TODO_ggc_collect |
8ddbbcae JH |
4817 | | TODO_verify_ssa /* todo_flags_finish */ |
4818 | } | |
6de9cd9a | 4819 | }; |
ff2ad0f7 DN |
4820 | |
4821 | ||
4822 | /* Gate and execute functions for FRE. */ | |
4823 | ||
c2924966 | 4824 | static unsigned int |
b89361c6 | 4825 | execute_fre (void) |
ff2ad0f7 | 4826 | { |
b80280f2 | 4827 | return execute_pre (true); |
ff2ad0f7 DN |
4828 | } |
4829 | ||
4830 | static bool | |
4831 | gate_fre (void) | |
4832 | { | |
4833 | return flag_tree_fre != 0; | |
4834 | } | |
4835 | ||
8ddbbcae | 4836 | struct gimple_opt_pass pass_fre = |
ff2ad0f7 | 4837 | { |
8ddbbcae JH |
4838 | { |
4839 | GIMPLE_PASS, | |
ff2ad0f7 DN |
4840 | "fre", /* name */ |
4841 | gate_fre, /* gate */ | |
b89361c6 | 4842 | execute_fre, /* execute */ |
ff2ad0f7 DN |
4843 | NULL, /* sub */ |
4844 | NULL, /* next */ | |
4845 | 0, /* static_pass_number */ | |
4846 | TV_TREE_FRE, /* tv_id */ | |
4effdf02 | 4847 | PROP_cfg | PROP_ssa, /* properties_required */ |
ff2ad0f7 DN |
4848 | 0, /* properties_provided */ |
4849 | 0, /* properties_destroyed */ | |
4850 | 0, /* todo_flags_start */ | |
8ddbbcae JH |
4851 | TODO_dump_func | TODO_ggc_collect | TODO_verify_ssa /* todo_flags_finish */ |
4852 | } | |
ff2ad0f7 | 4853 | }; |