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