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