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