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