1 /* Full and partial redundancy elimination and code hoisting on SSA GIMPLE.
2 Copyright (C) 2001-2021 Free Software Foundation, Inc.
3 Contributed by Daniel Berlin <dan@dberlin.org> and Steven Bosscher
6 This file is part of GCC.
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)
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.
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/>. */
24 #include "coretypes.h"
30 #include "alloc-pool.h"
31 #include "tree-pass.h"
34 #include "gimple-pretty-print.h"
35 #include "fold-const.h"
37 #include "gimple-fold.h"
40 #include "gimple-iterator.h"
42 #include "tree-into-ssa.h"
46 #include "tree-ssa-sccvn.h"
47 #include "tree-scalar-evolution.h"
50 #include "tree-ssa-propagate.h"
51 #include "tree-ssa-dce.h"
52 #include "tree-cfgcleanup.h"
54 #include "gimple-range.h"
56 /* Even though this file is called tree-ssa-pre.c, 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.c.
60 1. Full Redundancy Elimination (FRE)
61 This is the elimination phase of GVN.
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.
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).
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
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.
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. */
93 /* Basic algorithm for Partial Redundancy Elimination:
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
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.
120 Third, we perform insertions to make partially redundant
121 expressions fully redundant.
123 An expression is partially redundant (excluding partial
126 1. It is AVAIL in some, but not all, of the predecessors of a
128 2. It is ANTIC in all the predecessors.
130 In order to make it fully redundant, we insert the expression into
131 the predecessors where it is not available, but is ANTIC.
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.
137 For the partial anticipation case, we only perform insertion if it
138 is partially anticipated in some block, and fully available in all
141 do_pre_regular_insertion/do_pre_partial_partial_insertion
142 performs these steps, driven by insert/insert_aux.
144 Fourth, we eliminate fully redundant expressions.
145 This is a simple statement walk that replaces redundant
146 calculations with the now available values. */
148 /* Basic algorithm for Code Hoisting:
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.
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
160 For the purpose of this implementation, a value is hoistable to a basic
161 block B if the following properties are met:
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);
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;
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;
173 4. At least one successor has the value in AVAIL_OUT -- to avoid
174 hoisting values up too far;
176 5. There are at least two successors of B -- hoisting in straight
177 line code is pointless.
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).
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.
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.
199 The code hoisting algorithm is implemented in do_hoist_insert, driven
200 by insert/insert_aux. */
202 /* Representations of value numbers:
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).
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
219 /* Representation of expressions on value numbers:
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. */
226 /* Representation of sets:
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.
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
237 /* Type of expression, used to know which member of the PRE_EXPR union
253 vn_reference_t reference
;
256 typedef struct pre_expr_d
: nofree_ptr_hash
<pre_expr_d
>
258 enum pre_expr_kind kind
;
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
*);
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
274 /* Compare E1 and E1 for equality. */
277 pre_expr_d::equal (const pre_expr_d
*e1
, const pre_expr_d
*e2
)
279 if (e1
->kind
!= e2
->kind
)
285 return vn_constant_eq_with_type (PRE_EXPR_CONSTANT (e1
),
286 PRE_EXPR_CONSTANT (e2
));
288 return PRE_EXPR_NAME (e1
) == PRE_EXPR_NAME (e2
);
290 return vn_nary_op_eq (PRE_EXPR_NARY (e1
), PRE_EXPR_NARY (e2
));
292 return vn_reference_eq (PRE_EXPR_REFERENCE (e1
),
293 PRE_EXPR_REFERENCE (e2
));
302 pre_expr_d::hash (const pre_expr_d
*e
)
307 return vn_hash_constant_with_type (PRE_EXPR_CONSTANT (e
));
309 return SSA_NAME_VERSION (PRE_EXPR_NAME (e
));
311 return PRE_EXPR_NARY (e
)->hashcode
;
313 return PRE_EXPR_REFERENCE (e
)->hashcode
;
319 /* Next global expression id number. */
320 static unsigned int next_expression_id
;
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
;
327 /* Allocate an expression id for EXPR. */
329 static inline unsigned int
330 alloc_expression_id (pre_expr expr
)
332 struct pre_expr_d
**slot
;
333 /* Make sure we won't overflow. */
334 gcc_assert (next_expression_id
+ 1 > next_expression_id
);
335 expr
->id
= next_expression_id
++;
336 expressions
.safe_push (expr
);
337 if (expr
->kind
== NAME
)
339 unsigned version
= SSA_NAME_VERSION (PRE_EXPR_NAME (expr
));
340 /* vec::safe_grow_cleared allocates no headroom. Avoid frequent
341 re-allocations by using vec::reserve upfront. */
342 unsigned old_len
= name_to_id
.length ();
343 name_to_id
.reserve (num_ssa_names
- old_len
);
344 name_to_id
.quick_grow_cleared (num_ssa_names
);
345 gcc_assert (name_to_id
[version
] == 0);
346 name_to_id
[version
] = expr
->id
;
350 slot
= expression_to_id
->find_slot (expr
, INSERT
);
354 return next_expression_id
- 1;
357 /* Return the expression id for tree EXPR. */
359 static inline unsigned int
360 get_expression_id (const pre_expr expr
)
365 static inline unsigned int
366 lookup_expression_id (const pre_expr expr
)
368 struct pre_expr_d
**slot
;
370 if (expr
->kind
== NAME
)
372 unsigned version
= SSA_NAME_VERSION (PRE_EXPR_NAME (expr
));
373 if (name_to_id
.length () <= version
)
375 return name_to_id
[version
];
379 slot
= expression_to_id
->find_slot (expr
, NO_INSERT
);
382 return ((pre_expr
)*slot
)->id
;
386 /* Return the existing expression id for EXPR, or create one if one
387 does not exist yet. */
389 static inline unsigned int
390 get_or_alloc_expression_id (pre_expr expr
)
392 unsigned int id
= lookup_expression_id (expr
);
394 return alloc_expression_id (expr
);
395 return expr
->id
= id
;
398 /* Return the expression that has expression id ID */
400 static inline pre_expr
401 expression_for_id (unsigned int id
)
403 return expressions
[id
];
406 static object_allocator
<pre_expr_d
> pre_expr_pool ("pre_expr nodes");
408 /* Given an SSA_NAME NAME, get or create a pre_expr to represent it. */
411 get_or_alloc_expr_for_name (tree name
)
413 struct pre_expr_d expr
;
415 unsigned int result_id
;
419 PRE_EXPR_NAME (&expr
) = name
;
420 result_id
= lookup_expression_id (&expr
);
422 return expression_for_id (result_id
);
424 result
= pre_expr_pool
.allocate ();
426 result
->loc
= UNKNOWN_LOCATION
;
427 result
->value_id
= VN_INFO (name
)->value_id
;
428 PRE_EXPR_NAME (result
) = name
;
429 alloc_expression_id (result
);
433 /* Given an NARY, get or create a pre_expr to represent it. */
436 get_or_alloc_expr_for_nary (vn_nary_op_t nary
,
437 location_t loc
= UNKNOWN_LOCATION
)
439 struct pre_expr_d expr
;
441 unsigned int result_id
;
445 PRE_EXPR_NARY (&expr
) = nary
;
446 result_id
= lookup_expression_id (&expr
);
448 return expression_for_id (result_id
);
450 result
= pre_expr_pool
.allocate ();
453 result
->value_id
= nary
->value_id
;
454 PRE_EXPR_NARY (result
) = nary
;
455 alloc_expression_id (result
);
459 /* Given an REFERENCE, get or create a pre_expr to represent it. */
462 get_or_alloc_expr_for_reference (vn_reference_t reference
,
463 location_t loc
= UNKNOWN_LOCATION
)
465 struct pre_expr_d expr
;
467 unsigned int result_id
;
469 expr
.kind
= REFERENCE
;
471 PRE_EXPR_REFERENCE (&expr
) = reference
;
472 result_id
= lookup_expression_id (&expr
);
474 return expression_for_id (result_id
);
476 result
= pre_expr_pool
.allocate ();
477 result
->kind
= REFERENCE
;
479 result
->value_id
= reference
->value_id
;
480 PRE_EXPR_REFERENCE (result
) = reference
;
481 alloc_expression_id (result
);
486 /* An unordered bitmap set. One bitmap tracks values, the other,
488 typedef class bitmap_set
491 bitmap_head expressions
;
495 #define FOR_EACH_EXPR_ID_IN_SET(set, id, bi) \
496 EXECUTE_IF_SET_IN_BITMAP (&(set)->expressions, 0, (id), (bi))
498 #define FOR_EACH_VALUE_ID_IN_SET(set, id, bi) \
499 EXECUTE_IF_SET_IN_BITMAP (&(set)->values, 0, (id), (bi))
501 /* Mapping from value id to expressions with that value_id. */
502 static vec
<bitmap
> value_expressions
;
503 /* We just record a single expression for each constant value,
504 one of kind CONSTANT. */
505 static vec
<pre_expr
> constant_value_expressions
;
508 /* This structure is used to keep track of statistics on what
509 optimization PRE was able to perform. */
512 /* The number of new expressions/temporaries generated by PRE. */
515 /* The number of inserts found due to partial anticipation */
518 /* The number of inserts made for code hoisting. */
521 /* The number of new PHI nodes added by PRE. */
525 static bool do_partial_partial
;
526 static pre_expr
bitmap_find_leader (bitmap_set_t
, unsigned int);
527 static void bitmap_value_insert_into_set (bitmap_set_t
, pre_expr
);
528 static bool bitmap_value_replace_in_set (bitmap_set_t
, pre_expr
);
529 static void bitmap_set_copy (bitmap_set_t
, bitmap_set_t
);
530 static bool bitmap_set_contains_value (bitmap_set_t
, unsigned int);
531 static void bitmap_insert_into_set (bitmap_set_t
, pre_expr
);
532 static bitmap_set_t
bitmap_set_new (void);
533 static tree
create_expression_by_pieces (basic_block
, pre_expr
, gimple_seq
*,
535 static tree
find_or_generate_expression (basic_block
, tree
, gimple_seq
*);
536 static unsigned int get_expr_value_id (pre_expr
);
538 /* We can add and remove elements and entries to and from sets
539 and hash tables, so we use alloc pools for them. */
541 static object_allocator
<bitmap_set
> bitmap_set_pool ("Bitmap sets");
542 static bitmap_obstack grand_bitmap_obstack
;
544 /* A three tuple {e, pred, v} used to cache phi translations in the
545 phi_translate_table. */
547 typedef struct expr_pred_trans_d
: public typed_noop_remove
<expr_pred_trans_d
>
549 typedef expr_pred_trans_d value_type
;
550 typedef expr_pred_trans_d compare_type
;
552 /* The expression ID. */
555 /* The value expression ID that resulted from the translation. */
558 /* hash_table support. */
559 static inline void mark_empty (expr_pred_trans_d
&);
560 static inline bool is_empty (const expr_pred_trans_d
&);
561 static inline void mark_deleted (expr_pred_trans_d
&);
562 static inline bool is_deleted (const expr_pred_trans_d
&);
563 static const bool empty_zero_p
= true;
564 static inline hashval_t
hash (const expr_pred_trans_d
&);
565 static inline int equal (const expr_pred_trans_d
&, const expr_pred_trans_d
&);
566 } *expr_pred_trans_t
;
567 typedef const struct expr_pred_trans_d
*const_expr_pred_trans_t
;
570 expr_pred_trans_d::is_empty (const expr_pred_trans_d
&e
)
576 expr_pred_trans_d::is_deleted (const expr_pred_trans_d
&e
)
582 expr_pred_trans_d::mark_empty (expr_pred_trans_d
&e
)
588 expr_pred_trans_d::mark_deleted (expr_pred_trans_d
&e
)
594 expr_pred_trans_d::hash (const expr_pred_trans_d
&e
)
600 expr_pred_trans_d::equal (const expr_pred_trans_d
&ve1
,
601 const expr_pred_trans_d
&ve2
)
603 return ve1
.e
== ve2
.e
;
606 /* Sets that we need to keep track of. */
607 typedef struct bb_bitmap_sets
609 /* The EXP_GEN set, which represents expressions/values generated in
611 bitmap_set_t exp_gen
;
613 /* The PHI_GEN set, which represents PHI results generated in a
615 bitmap_set_t phi_gen
;
617 /* The TMP_GEN set, which represents results/temporaries generated
618 in a basic block. IE the LHS of an expression. */
619 bitmap_set_t tmp_gen
;
621 /* The AVAIL_OUT set, which represents which values are available in
622 a given basic block. */
623 bitmap_set_t avail_out
;
625 /* The ANTIC_IN set, which represents which values are anticipatable
626 in a given basic block. */
627 bitmap_set_t antic_in
;
629 /* The PA_IN set, which represents which values are
630 partially anticipatable in a given basic block. */
633 /* The NEW_SETS set, which is used during insertion to augment the
634 AVAIL_OUT set of blocks with the new insertions performed during
635 the current iteration. */
636 bitmap_set_t new_sets
;
638 /* A cache for value_dies_in_block_x. */
641 /* The live virtual operand on successor edges. */
644 /* PHI translate cache for the single successor edge. */
645 hash_table
<expr_pred_trans_d
> *phi_translate_table
;
647 /* True if we have visited this block during ANTIC calculation. */
648 unsigned int visited
: 1;
650 /* True when the block contains a call that might not return. */
651 unsigned int contains_may_not_return_call
: 1;
654 #define EXP_GEN(BB) ((bb_value_sets_t) ((BB)->aux))->exp_gen
655 #define PHI_GEN(BB) ((bb_value_sets_t) ((BB)->aux))->phi_gen
656 #define TMP_GEN(BB) ((bb_value_sets_t) ((BB)->aux))->tmp_gen
657 #define AVAIL_OUT(BB) ((bb_value_sets_t) ((BB)->aux))->avail_out
658 #define ANTIC_IN(BB) ((bb_value_sets_t) ((BB)->aux))->antic_in
659 #define PA_IN(BB) ((bb_value_sets_t) ((BB)->aux))->pa_in
660 #define NEW_SETS(BB) ((bb_value_sets_t) ((BB)->aux))->new_sets
661 #define EXPR_DIES(BB) ((bb_value_sets_t) ((BB)->aux))->expr_dies
662 #define PHI_TRANS_TABLE(BB) ((bb_value_sets_t) ((BB)->aux))->phi_translate_table
663 #define BB_VISITED(BB) ((bb_value_sets_t) ((BB)->aux))->visited
664 #define BB_MAY_NOTRETURN(BB) ((bb_value_sets_t) ((BB)->aux))->contains_may_not_return_call
665 #define BB_LIVE_VOP_ON_EXIT(BB) ((bb_value_sets_t) ((BB)->aux))->vop_on_exit
668 /* Add the tuple mapping from {expression E, basic block PRED} to
669 the phi translation table and return whether it pre-existed. */
672 phi_trans_add (expr_pred_trans_t
*entry
, pre_expr e
, basic_block pred
)
674 if (!PHI_TRANS_TABLE (pred
))
675 PHI_TRANS_TABLE (pred
) = new hash_table
<expr_pred_trans_d
> (11);
677 expr_pred_trans_t slot
;
678 expr_pred_trans_d tem
;
679 unsigned id
= get_expression_id (e
);
681 slot
= PHI_TRANS_TABLE (pred
)->find_slot_with_hash (tem
, id
, INSERT
);
694 /* Add expression E to the expression set of value id V. */
697 add_to_value (unsigned int v
, pre_expr e
)
699 gcc_checking_assert (get_expr_value_id (e
) == v
);
701 if (value_id_constant_p (v
))
703 if (e
->kind
!= CONSTANT
)
706 if (-v
>= constant_value_expressions
.length ())
707 constant_value_expressions
.safe_grow_cleared (-v
+ 1);
709 pre_expr leader
= constant_value_expressions
[-v
];
711 constant_value_expressions
[-v
] = e
;
715 if (v
>= value_expressions
.length ())
716 value_expressions
.safe_grow_cleared (v
+ 1);
718 bitmap set
= value_expressions
[v
];
721 set
= BITMAP_ALLOC (&grand_bitmap_obstack
);
722 value_expressions
[v
] = set
;
724 bitmap_set_bit (set
, get_or_alloc_expression_id (e
));
728 /* Create a new bitmap set and return it. */
731 bitmap_set_new (void)
733 bitmap_set_t ret
= bitmap_set_pool
.allocate ();
734 bitmap_initialize (&ret
->expressions
, &grand_bitmap_obstack
);
735 bitmap_initialize (&ret
->values
, &grand_bitmap_obstack
);
739 /* Return the value id for a PRE expression EXPR. */
742 get_expr_value_id (pre_expr expr
)
744 /* ??? We cannot assert that expr has a value-id (it can be 0), because
745 we assign value-ids only to expressions that have a result
746 in set_hashtable_value_ids. */
747 return expr
->value_id
;
750 /* Return a VN valnum (SSA name or constant) for the PRE value-id VAL. */
753 vn_valnum_from_value_id (unsigned int val
)
755 if (value_id_constant_p (val
))
757 pre_expr vexpr
= constant_value_expressions
[-val
];
759 return PRE_EXPR_CONSTANT (vexpr
);
763 bitmap exprset
= value_expressions
[val
];
766 EXECUTE_IF_SET_IN_BITMAP (exprset
, 0, i
, bi
)
768 pre_expr vexpr
= expression_for_id (i
);
769 if (vexpr
->kind
== NAME
)
770 return VN_INFO (PRE_EXPR_NAME (vexpr
))->valnum
;
775 /* Insert an expression EXPR into a bitmapped set. */
778 bitmap_insert_into_set (bitmap_set_t set
, pre_expr expr
)
780 unsigned int val
= get_expr_value_id (expr
);
781 if (! value_id_constant_p (val
))
783 /* Note this is the only function causing multiple expressions
784 for the same value to appear in a set. This is needed for
785 TMP_GEN, PHI_GEN and NEW_SETs. */
786 bitmap_set_bit (&set
->values
, val
);
787 bitmap_set_bit (&set
->expressions
, get_or_alloc_expression_id (expr
));
791 /* Copy a bitmapped set ORIG, into bitmapped set DEST. */
794 bitmap_set_copy (bitmap_set_t dest
, bitmap_set_t orig
)
796 bitmap_copy (&dest
->expressions
, &orig
->expressions
);
797 bitmap_copy (&dest
->values
, &orig
->values
);
801 /* Free memory used up by SET. */
803 bitmap_set_free (bitmap_set_t set
)
805 bitmap_clear (&set
->expressions
);
806 bitmap_clear (&set
->values
);
810 pre_expr_DFS (pre_expr expr
, bitmap_set_t set
, bitmap val_visited
,
811 vec
<pre_expr
> &post
);
813 /* DFS walk leaders of VAL to their operands with leaders in SET, collecting
814 expressions in SET in postorder into POST. */
817 pre_expr_DFS (unsigned val
, bitmap_set_t set
, bitmap val_visited
,
823 /* Iterate over all leaders and DFS recurse. Borrowed from
824 bitmap_find_leader. */
825 bitmap exprset
= value_expressions
[val
];
826 if (!exprset
->first
->next
)
828 EXECUTE_IF_SET_IN_BITMAP (exprset
, 0, i
, bi
)
829 if (bitmap_bit_p (&set
->expressions
, i
))
830 pre_expr_DFS (expression_for_id (i
), set
, val_visited
, post
);
834 EXECUTE_IF_AND_IN_BITMAP (exprset
, &set
->expressions
, 0, i
, bi
)
835 pre_expr_DFS (expression_for_id (i
), set
, val_visited
, post
);
838 /* DFS walk EXPR to its operands with leaders in SET, collecting
839 expressions in SET in postorder into POST. */
842 pre_expr_DFS (pre_expr expr
, bitmap_set_t set
, bitmap val_visited
,
849 vn_nary_op_t nary
= PRE_EXPR_NARY (expr
);
850 for (unsigned i
= 0; i
< nary
->length
; i
++)
852 if (TREE_CODE (nary
->op
[i
]) != SSA_NAME
)
854 unsigned int op_val_id
= VN_INFO (nary
->op
[i
])->value_id
;
855 /* If we already found a leader for the value we've
856 recursed already. Avoid the costly bitmap_find_leader. */
857 if (bitmap_bit_p (&set
->values
, op_val_id
)
858 && bitmap_set_bit (val_visited
, op_val_id
))
859 pre_expr_DFS (op_val_id
, set
, val_visited
, post
);
865 vn_reference_t ref
= PRE_EXPR_REFERENCE (expr
);
866 vec
<vn_reference_op_s
> operands
= ref
->operands
;
867 vn_reference_op_t operand
;
868 for (unsigned i
= 0; operands
.iterate (i
, &operand
); i
++)
871 op
[0] = operand
->op0
;
872 op
[1] = operand
->op1
;
873 op
[2] = operand
->op2
;
874 for (unsigned n
= 0; n
< 3; ++n
)
876 if (!op
[n
] || TREE_CODE (op
[n
]) != SSA_NAME
)
878 unsigned op_val_id
= VN_INFO (op
[n
])->value_id
;
879 if (bitmap_bit_p (&set
->values
, op_val_id
)
880 && bitmap_set_bit (val_visited
, op_val_id
))
881 pre_expr_DFS (op_val_id
, set
, val_visited
, post
);
888 post
.quick_push (expr
);
891 /* Generate an topological-ordered array of bitmap set SET. */
894 sorted_array_from_bitmap_set (bitmap_set_t set
)
898 vec
<pre_expr
> result
;
900 /* Pre-allocate enough space for the array. */
901 result
.create (bitmap_count_bits (&set
->expressions
));
903 auto_bitmap
val_visited (&grand_bitmap_obstack
);
904 bitmap_tree_view (val_visited
);
905 FOR_EACH_VALUE_ID_IN_SET (set
, i
, bi
)
906 if (bitmap_set_bit (val_visited
, i
))
907 pre_expr_DFS (i
, set
, val_visited
, result
);
912 /* Subtract all expressions contained in ORIG from DEST. */
915 bitmap_set_subtract_expressions (bitmap_set_t dest
, bitmap_set_t orig
)
917 bitmap_set_t result
= bitmap_set_new ();
921 bitmap_and_compl (&result
->expressions
, &dest
->expressions
,
924 FOR_EACH_EXPR_ID_IN_SET (result
, i
, bi
)
926 pre_expr expr
= expression_for_id (i
);
927 unsigned int value_id
= get_expr_value_id (expr
);
928 bitmap_set_bit (&result
->values
, value_id
);
934 /* Subtract all values in bitmap set B from bitmap set A. */
937 bitmap_set_subtract_values (bitmap_set_t a
, bitmap_set_t b
)
941 unsigned to_remove
= -1U;
942 bitmap_and_compl_into (&a
->values
, &b
->values
);
943 FOR_EACH_EXPR_ID_IN_SET (a
, i
, bi
)
945 if (to_remove
!= -1U)
947 bitmap_clear_bit (&a
->expressions
, to_remove
);
950 pre_expr expr
= expression_for_id (i
);
951 if (! bitmap_bit_p (&a
->values
, get_expr_value_id (expr
)))
954 if (to_remove
!= -1U)
955 bitmap_clear_bit (&a
->expressions
, to_remove
);
959 /* Return true if bitmapped set SET contains the value VALUE_ID. */
962 bitmap_set_contains_value (bitmap_set_t set
, unsigned int value_id
)
964 if (value_id_constant_p (value_id
))
967 return bitmap_bit_p (&set
->values
, value_id
);
970 /* Return true if two bitmap sets are equal. */
973 bitmap_set_equal (bitmap_set_t a
, bitmap_set_t b
)
975 return bitmap_equal_p (&a
->values
, &b
->values
);
978 /* Replace an instance of EXPR's VALUE with EXPR in SET if it exists,
979 and add it otherwise. Return true if any changes were made. */
982 bitmap_value_replace_in_set (bitmap_set_t set
, pre_expr expr
)
984 unsigned int val
= get_expr_value_id (expr
);
985 if (value_id_constant_p (val
))
988 if (bitmap_set_contains_value (set
, val
))
990 /* The number of expressions having a given value is usually
991 significantly less than the total number of expressions in SET.
992 Thus, rather than check, for each expression in SET, whether it
993 has the value LOOKFOR, we walk the reverse mapping that tells us
994 what expressions have a given value, and see if any of those
995 expressions are in our set. For large testcases, this is about
996 5-10x faster than walking the bitmap. If this is somehow a
997 significant lose for some cases, we can choose which set to walk
998 based on the set size. */
1001 bitmap exprset
= value_expressions
[val
];
1002 EXECUTE_IF_SET_IN_BITMAP (exprset
, 0, i
, bi
)
1004 if (bitmap_clear_bit (&set
->expressions
, i
))
1006 bitmap_set_bit (&set
->expressions
, get_expression_id (expr
));
1007 return i
!= get_expression_id (expr
);
1013 bitmap_insert_into_set (set
, expr
);
1017 /* Insert EXPR into SET if EXPR's value is not already present in
1021 bitmap_value_insert_into_set (bitmap_set_t set
, pre_expr expr
)
1023 unsigned int val
= get_expr_value_id (expr
);
1025 gcc_checking_assert (expr
->id
== get_or_alloc_expression_id (expr
));
1027 /* Constant values are always considered to be part of the set. */
1028 if (value_id_constant_p (val
))
1031 /* If the value membership changed, add the expression. */
1032 if (bitmap_set_bit (&set
->values
, val
))
1033 bitmap_set_bit (&set
->expressions
, expr
->id
);
1036 /* Print out EXPR to outfile. */
1039 print_pre_expr (FILE *outfile
, const pre_expr expr
)
1043 fprintf (outfile
, "NULL");
1049 print_generic_expr (outfile
, PRE_EXPR_CONSTANT (expr
));
1052 print_generic_expr (outfile
, PRE_EXPR_NAME (expr
));
1057 vn_nary_op_t nary
= PRE_EXPR_NARY (expr
);
1058 fprintf (outfile
, "{%s,", get_tree_code_name (nary
->opcode
));
1059 for (i
= 0; i
< nary
->length
; i
++)
1061 print_generic_expr (outfile
, nary
->op
[i
]);
1062 if (i
!= (unsigned) nary
->length
- 1)
1063 fprintf (outfile
, ",");
1065 fprintf (outfile
, "}");
1071 vn_reference_t ref
= PRE_EXPR_REFERENCE (expr
);
1072 print_vn_reference_ops (outfile
, ref
->operands
);
1075 fprintf (outfile
, "@");
1076 print_generic_expr (outfile
, ref
->vuse
);
1082 void debug_pre_expr (pre_expr
);
1084 /* Like print_pre_expr but always prints to stderr. */
1086 debug_pre_expr (pre_expr e
)
1088 print_pre_expr (stderr
, e
);
1089 fprintf (stderr
, "\n");
1092 /* Print out SET to OUTFILE. */
1095 print_bitmap_set (FILE *outfile
, bitmap_set_t set
,
1096 const char *setname
, int blockindex
)
1098 fprintf (outfile
, "%s[%d] := { ", setname
, blockindex
);
1105 FOR_EACH_EXPR_ID_IN_SET (set
, i
, bi
)
1107 const pre_expr expr
= expression_for_id (i
);
1110 fprintf (outfile
, ", ");
1112 print_pre_expr (outfile
, expr
);
1114 fprintf (outfile
, " (%04d)", get_expr_value_id (expr
));
1117 fprintf (outfile
, " }\n");
1120 void debug_bitmap_set (bitmap_set_t
);
1123 debug_bitmap_set (bitmap_set_t set
)
1125 print_bitmap_set (stderr
, set
, "debug", 0);
1128 void debug_bitmap_sets_for (basic_block
);
1131 debug_bitmap_sets_for (basic_block bb
)
1133 print_bitmap_set (stderr
, AVAIL_OUT (bb
), "avail_out", bb
->index
);
1134 print_bitmap_set (stderr
, EXP_GEN (bb
), "exp_gen", bb
->index
);
1135 print_bitmap_set (stderr
, PHI_GEN (bb
), "phi_gen", bb
->index
);
1136 print_bitmap_set (stderr
, TMP_GEN (bb
), "tmp_gen", bb
->index
);
1137 print_bitmap_set (stderr
, ANTIC_IN (bb
), "antic_in", bb
->index
);
1138 if (do_partial_partial
)
1139 print_bitmap_set (stderr
, PA_IN (bb
), "pa_in", bb
->index
);
1140 print_bitmap_set (stderr
, NEW_SETS (bb
), "new_sets", bb
->index
);
1143 /* Print out the expressions that have VAL to OUTFILE. */
1146 print_value_expressions (FILE *outfile
, unsigned int val
)
1148 bitmap set
= value_expressions
[val
];
1153 sprintf (s
, "%04d", val
);
1154 x
.expressions
= *set
;
1155 print_bitmap_set (outfile
, &x
, s
, 0);
1161 debug_value_expressions (unsigned int val
)
1163 print_value_expressions (stderr
, val
);
1166 /* Given a CONSTANT, allocate a new CONSTANT type PRE_EXPR to
1170 get_or_alloc_expr_for_constant (tree constant
)
1172 unsigned int result_id
;
1173 struct pre_expr_d expr
;
1176 expr
.kind
= CONSTANT
;
1177 PRE_EXPR_CONSTANT (&expr
) = constant
;
1178 result_id
= lookup_expression_id (&expr
);
1180 return expression_for_id (result_id
);
1182 newexpr
= pre_expr_pool
.allocate ();
1183 newexpr
->kind
= CONSTANT
;
1184 newexpr
->loc
= UNKNOWN_LOCATION
;
1185 PRE_EXPR_CONSTANT (newexpr
) = constant
;
1186 alloc_expression_id (newexpr
);
1187 newexpr
->value_id
= get_or_alloc_constant_value_id (constant
);
1188 add_to_value (newexpr
->value_id
, newexpr
);
1192 /* Get or allocate a pre_expr for a piece of GIMPLE, and return it.
1193 Currently only supports constants and SSA_NAMES. */
1195 get_or_alloc_expr_for (tree t
)
1197 if (TREE_CODE (t
) == SSA_NAME
)
1198 return get_or_alloc_expr_for_name (t
);
1199 else if (is_gimple_min_invariant (t
))
1200 return get_or_alloc_expr_for_constant (t
);
1204 /* Return the folded version of T if T, when folded, is a gimple
1205 min_invariant or an SSA name. Otherwise, return T. */
1208 fully_constant_expression (pre_expr e
)
1216 vn_nary_op_t nary
= PRE_EXPR_NARY (e
);
1217 tree res
= vn_nary_simplify (nary
);
1220 if (is_gimple_min_invariant (res
))
1221 return get_or_alloc_expr_for_constant (res
);
1222 if (TREE_CODE (res
) == SSA_NAME
)
1223 return get_or_alloc_expr_for_name (res
);
1228 vn_reference_t ref
= PRE_EXPR_REFERENCE (e
);
1230 if ((folded
= fully_constant_vn_reference_p (ref
)))
1231 return get_or_alloc_expr_for_constant (folded
);
1240 /* Translate the VUSE backwards through phi nodes in E->dest, so that
1241 it has the value it would have in E->src. Set *SAME_VALID to true
1242 in case the new vuse doesn't change the value id of the OPERANDS. */
1245 translate_vuse_through_block (vec
<vn_reference_op_s
> operands
,
1246 alias_set_type set
, alias_set_type base_set
,
1247 tree type
, tree vuse
, edge e
, bool *same_valid
)
1249 basic_block phiblock
= e
->dest
;
1250 gimple
*phi
= SSA_NAME_DEF_STMT (vuse
);
1256 if (gimple_bb (phi
) != phiblock
)
1259 /* We have pruned expressions that are killed in PHIBLOCK via
1260 prune_clobbered_mems but we have not rewritten the VUSE to the one
1261 live at the start of the block. If there is no virtual PHI to translate
1262 through return the VUSE live at entry. Otherwise the VUSE to translate
1263 is the def of the virtual PHI node. */
1264 phi
= get_virtual_phi (phiblock
);
1266 return BB_LIVE_VOP_ON_EXIT
1267 (get_immediate_dominator (CDI_DOMINATORS
, phiblock
));
1270 && ao_ref_init_from_vn_reference (&ref
, set
, base_set
, type
, operands
))
1272 bitmap visited
= NULL
;
1273 /* Try to find a vuse that dominates this phi node by skipping
1274 non-clobbering statements. */
1275 unsigned int cnt
= param_sccvn_max_alias_queries_per_access
;
1276 vuse
= get_continuation_for_phi (phi
, &ref
, true,
1277 cnt
, &visited
, false, NULL
, NULL
);
1279 BITMAP_FREE (visited
);
1283 /* If we didn't find any, the value ID can't stay the same. */
1284 if (!vuse
&& same_valid
)
1285 *same_valid
= false;
1287 /* ??? We would like to return vuse here as this is the canonical
1288 upmost vdef that this reference is associated with. But during
1289 insertion of the references into the hash tables we only ever
1290 directly insert with their direct gimple_vuse, hence returning
1291 something else would make us not find the other expression. */
1292 return PHI_ARG_DEF (phi
, e
->dest_idx
);
1295 /* Like bitmap_find_leader, but checks for the value existing in SET1 *or*
1296 SET2 *or* SET3. This is used to avoid making a set consisting of the union
1297 of PA_IN and ANTIC_IN during insert and phi-translation. */
1299 static inline pre_expr
1300 find_leader_in_sets (unsigned int val
, bitmap_set_t set1
, bitmap_set_t set2
,
1301 bitmap_set_t set3
= NULL
)
1303 pre_expr result
= NULL
;
1306 result
= bitmap_find_leader (set1
, val
);
1307 if (!result
&& set2
)
1308 result
= bitmap_find_leader (set2
, val
);
1309 if (!result
&& set3
)
1310 result
= bitmap_find_leader (set3
, val
);
1314 /* Get the tree type for our PRE expression e. */
1317 get_expr_type (const pre_expr e
)
1322 return TREE_TYPE (PRE_EXPR_NAME (e
));
1324 return TREE_TYPE (PRE_EXPR_CONSTANT (e
));
1326 return PRE_EXPR_REFERENCE (e
)->type
;
1328 return PRE_EXPR_NARY (e
)->type
;
1333 /* Get a representative SSA_NAME for a given expression that is available in B.
1334 Since all of our sub-expressions are treated as values, we require
1335 them to be SSA_NAME's for simplicity.
1336 Prior versions of GVNPRE used to use "value handles" here, so that
1337 an expression would be VH.11 + VH.10 instead of d_3 + e_6. In
1338 either case, the operands are really values (IE we do not expect
1339 them to be usable without finding leaders). */
1342 get_representative_for (const pre_expr e
, basic_block b
= NULL
)
1344 tree name
, valnum
= NULL_TREE
;
1345 unsigned int value_id
= get_expr_value_id (e
);
1350 return PRE_EXPR_NAME (e
);
1352 return PRE_EXPR_CONSTANT (e
);
1356 /* Go through all of the expressions representing this value
1357 and pick out an SSA_NAME. */
1360 bitmap exprs
= value_expressions
[value_id
];
1361 EXECUTE_IF_SET_IN_BITMAP (exprs
, 0, i
, bi
)
1363 pre_expr rep
= expression_for_id (i
);
1364 if (rep
->kind
== NAME
)
1366 tree name
= PRE_EXPR_NAME (rep
);
1367 valnum
= VN_INFO (name
)->valnum
;
1368 gimple
*def
= SSA_NAME_DEF_STMT (name
);
1369 /* We have to return either a new representative or one
1370 that can be used for expression simplification and thus
1371 is available in B. */
1373 || gimple_nop_p (def
)
1374 || dominated_by_p (CDI_DOMINATORS
, b
, gimple_bb (def
)))
1377 else if (rep
->kind
== CONSTANT
)
1378 return PRE_EXPR_CONSTANT (rep
);
1384 /* If we reached here we couldn't find an SSA_NAME. This can
1385 happen when we've discovered a value that has never appeared in
1386 the program as set to an SSA_NAME, as the result of phi translation.
1388 ??? We should be able to re-use this when we insert the statement
1390 name
= make_temp_ssa_name (get_expr_type (e
), gimple_build_nop (), "pretmp");
1391 vn_ssa_aux_t vn_info
= VN_INFO (name
);
1392 vn_info
->value_id
= value_id
;
1393 vn_info
->valnum
= valnum
? valnum
: name
;
1394 /* ??? For now mark this SSA name for release by VN. */
1395 vn_info
->needs_insertion
= true;
1396 add_to_value (value_id
, get_or_alloc_expr_for_name (name
));
1397 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1399 fprintf (dump_file
, "Created SSA_NAME representative ");
1400 print_generic_expr (dump_file
, name
);
1401 fprintf (dump_file
, " for expression:");
1402 print_pre_expr (dump_file
, e
);
1403 fprintf (dump_file
, " (%04d)\n", value_id
);
1411 phi_translate (bitmap_set_t
, pre_expr
, bitmap_set_t
, bitmap_set_t
, edge
);
1413 /* Translate EXPR using phis in PHIBLOCK, so that it has the values of
1414 the phis in PRED. Return NULL if we can't find a leader for each part
1415 of the translated expression. */
1418 phi_translate_1 (bitmap_set_t dest
,
1419 pre_expr expr
, bitmap_set_t set1
, bitmap_set_t set2
, edge e
)
1421 basic_block pred
= e
->src
;
1422 basic_block phiblock
= e
->dest
;
1423 location_t expr_loc
= expr
->loc
;
1429 bool changed
= false;
1430 vn_nary_op_t nary
= PRE_EXPR_NARY (expr
);
1431 vn_nary_op_t newnary
= XALLOCAVAR (struct vn_nary_op_s
,
1432 sizeof_vn_nary_op (nary
->length
));
1433 memcpy (newnary
, nary
, sizeof_vn_nary_op (nary
->length
));
1435 for (i
= 0; i
< newnary
->length
; i
++)
1437 if (TREE_CODE (newnary
->op
[i
]) != SSA_NAME
)
1441 pre_expr leader
, result
;
1442 unsigned int op_val_id
= VN_INFO (newnary
->op
[i
])->value_id
;
1443 leader
= find_leader_in_sets (op_val_id
, set1
, set2
);
1444 result
= phi_translate (dest
, leader
, set1
, set2
, e
);
1445 if (result
&& result
!= leader
)
1446 /* If op has a leader in the sets we translate make
1447 sure to use the value of the translated expression.
1448 We might need a new representative for that. */
1449 newnary
->op
[i
] = get_representative_for (result
, pred
);
1453 changed
|= newnary
->op
[i
] != nary
->op
[i
];
1459 unsigned int new_val_id
;
1461 PRE_EXPR_NARY (expr
) = newnary
;
1462 constant
= fully_constant_expression (expr
);
1463 PRE_EXPR_NARY (expr
) = nary
;
1464 if (constant
!= expr
)
1466 /* For non-CONSTANTs we have to make sure we can eventually
1467 insert the expression. Which means we need to have a
1469 if (constant
->kind
!= CONSTANT
)
1471 /* Do not allow simplifications to non-constants over
1472 backedges as this will likely result in a loop PHI node
1473 to be inserted and increased register pressure.
1474 See PR77498 - this avoids doing predcoms work in
1475 a less efficient way. */
1476 if (e
->flags
& EDGE_DFS_BACK
)
1480 unsigned value_id
= get_expr_value_id (constant
);
1481 /* We want a leader in ANTIC_OUT or AVAIL_OUT here.
1482 dest has what we computed into ANTIC_OUT sofar
1483 so pick from that - since topological sorting
1484 by sorted_array_from_bitmap_set isn't perfect
1485 we may lose some cases here. */
1486 constant
= find_leader_in_sets (value_id
, dest
,
1490 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1492 fprintf (dump_file
, "simplifying ");
1493 print_pre_expr (dump_file
, expr
);
1494 fprintf (dump_file
, " translated %d -> %d to ",
1495 phiblock
->index
, pred
->index
);
1496 PRE_EXPR_NARY (expr
) = newnary
;
1497 print_pre_expr (dump_file
, expr
);
1498 PRE_EXPR_NARY (expr
) = nary
;
1499 fprintf (dump_file
, " to ");
1500 print_pre_expr (dump_file
, constant
);
1501 fprintf (dump_file
, "\n");
1511 /* vn_nary_* do not valueize operands. */
1512 for (i
= 0; i
< newnary
->length
; ++i
)
1513 if (TREE_CODE (newnary
->op
[i
]) == SSA_NAME
)
1514 newnary
->op
[i
] = VN_INFO (newnary
->op
[i
])->valnum
;
1515 tree result
= vn_nary_op_lookup_pieces (newnary
->length
,
1520 if (result
&& is_gimple_min_invariant (result
))
1521 return get_or_alloc_expr_for_constant (result
);
1523 if (!nary
|| nary
->predicated_values
)
1525 new_val_id
= get_next_value_id ();
1526 nary
= vn_nary_op_insert_pieces (newnary
->length
,
1530 result
, new_val_id
);
1532 expr
= get_or_alloc_expr_for_nary (nary
, expr_loc
);
1533 add_to_value (get_expr_value_id (expr
), expr
);
1541 vn_reference_t ref
= PRE_EXPR_REFERENCE (expr
);
1542 vec
<vn_reference_op_s
> operands
= ref
->operands
;
1543 tree vuse
= ref
->vuse
;
1544 tree newvuse
= vuse
;
1545 vec
<vn_reference_op_s
> newoperands
= vNULL
;
1546 bool changed
= false, same_valid
= true;
1548 vn_reference_op_t operand
;
1549 vn_reference_t newref
;
1551 for (i
= 0; operands
.iterate (i
, &operand
); i
++)
1556 tree type
= operand
->type
;
1557 vn_reference_op_s newop
= *operand
;
1558 op
[0] = operand
->op0
;
1559 op
[1] = operand
->op1
;
1560 op
[2] = operand
->op2
;
1561 for (n
= 0; n
< 3; ++n
)
1563 unsigned int op_val_id
;
1566 if (TREE_CODE (op
[n
]) != SSA_NAME
)
1568 /* We can't possibly insert these. */
1570 && !is_gimple_min_invariant (op
[n
]))
1574 op_val_id
= VN_INFO (op
[n
])->value_id
;
1575 leader
= find_leader_in_sets (op_val_id
, set1
, set2
);
1576 opresult
= phi_translate (dest
, leader
, set1
, set2
, e
);
1577 if (opresult
&& opresult
!= leader
)
1579 tree name
= get_representative_for (opresult
);
1580 changed
|= name
!= op
[n
];
1588 newoperands
.release ();
1593 if (!newoperands
.exists ())
1594 newoperands
= operands
.copy ();
1595 /* We may have changed from an SSA_NAME to a constant */
1596 if (newop
.opcode
== SSA_NAME
&& TREE_CODE (op
[0]) != SSA_NAME
)
1597 newop
.opcode
= TREE_CODE (op
[0]);
1602 newoperands
[i
] = newop
;
1604 gcc_checking_assert (i
== operands
.length ());
1608 newvuse
= translate_vuse_through_block (newoperands
.exists ()
1609 ? newoperands
: operands
,
1610 ref
->set
, ref
->base_set
,
1613 ? NULL
: &same_valid
);
1614 if (newvuse
== NULL_TREE
)
1616 newoperands
.release ();
1621 if (changed
|| newvuse
!= vuse
)
1623 unsigned int new_val_id
;
1625 tree result
= vn_reference_lookup_pieces (newvuse
, ref
->set
,
1628 newoperands
.exists ()
1629 ? newoperands
: operands
,
1632 newoperands
.release ();
1634 /* We can always insert constants, so if we have a partial
1635 redundant constant load of another type try to translate it
1636 to a constant of appropriate type. */
1637 if (result
&& is_gimple_min_invariant (result
))
1640 if (!useless_type_conversion_p (ref
->type
, TREE_TYPE (result
)))
1642 tem
= fold_unary (VIEW_CONVERT_EXPR
, ref
->type
, result
);
1643 if (tem
&& !is_gimple_min_invariant (tem
))
1647 return get_or_alloc_expr_for_constant (tem
);
1650 /* If we'd have to convert things we would need to validate
1651 if we can insert the translated expression. So fail
1652 here for now - we cannot insert an alias with a different
1653 type in the VN tables either, as that would assert. */
1655 && !useless_type_conversion_p (ref
->type
, TREE_TYPE (result
)))
1657 else if (!result
&& newref
1658 && !useless_type_conversion_p (ref
->type
, newref
->type
))
1660 newoperands
.release ();
1665 new_val_id
= newref
->value_id
;
1668 if (changed
|| !same_valid
)
1669 new_val_id
= get_next_value_id ();
1671 new_val_id
= ref
->value_id
;
1672 if (!newoperands
.exists ())
1673 newoperands
= operands
.copy ();
1674 newref
= vn_reference_insert_pieces (newvuse
, ref
->set
,
1675 ref
->base_set
, ref
->type
,
1677 result
, new_val_id
);
1678 newoperands
= vNULL
;
1680 expr
= get_or_alloc_expr_for_reference (newref
, expr_loc
);
1681 add_to_value (new_val_id
, expr
);
1683 newoperands
.release ();
1690 tree name
= PRE_EXPR_NAME (expr
);
1691 gimple
*def_stmt
= SSA_NAME_DEF_STMT (name
);
1692 /* If the SSA name is defined by a PHI node in this block,
1694 if (gimple_code (def_stmt
) == GIMPLE_PHI
1695 && gimple_bb (def_stmt
) == phiblock
)
1697 tree def
= PHI_ARG_DEF (def_stmt
, e
->dest_idx
);
1699 /* Handle constant. */
1700 if (is_gimple_min_invariant (def
))
1701 return get_or_alloc_expr_for_constant (def
);
1703 return get_or_alloc_expr_for_name (def
);
1705 /* Otherwise return it unchanged - it will get removed if its
1706 value is not available in PREDs AVAIL_OUT set of expressions
1707 by the subtraction of TMP_GEN. */
1716 /* Wrapper around phi_translate_1 providing caching functionality. */
1719 phi_translate (bitmap_set_t dest
, pre_expr expr
,
1720 bitmap_set_t set1
, bitmap_set_t set2
, edge e
)
1722 expr_pred_trans_t slot
= NULL
;
1728 /* Constants contain no values that need translation. */
1729 if (expr
->kind
== CONSTANT
)
1732 if (value_id_constant_p (get_expr_value_id (expr
)))
1735 /* Don't add translations of NAMEs as those are cheap to translate. */
1736 if (expr
->kind
!= NAME
)
1738 if (phi_trans_add (&slot
, expr
, e
->src
))
1739 return slot
->v
== 0 ? NULL
: expression_for_id (slot
->v
);
1740 /* Store NULL for the value we want to return in the case of
1746 basic_block saved_valueize_bb
= vn_context_bb
;
1747 vn_context_bb
= e
->src
;
1748 phitrans
= phi_translate_1 (dest
, expr
, set1
, set2
, e
);
1749 vn_context_bb
= saved_valueize_bb
;
1753 /* We may have reallocated. */
1754 phi_trans_add (&slot
, expr
, e
->src
);
1756 slot
->v
= get_expression_id (phitrans
);
1758 /* Remove failed translations again, they cause insert
1759 iteration to not pick up new opportunities reliably. */
1760 PHI_TRANS_TABLE (e
->src
)->clear_slot (slot
);
1767 /* For each expression in SET, translate the values through phi nodes
1768 in PHIBLOCK using edge PHIBLOCK->PRED, and store the resulting
1769 expressions in DEST. */
1772 phi_translate_set (bitmap_set_t dest
, bitmap_set_t set
, edge e
)
1777 if (gimple_seq_empty_p (phi_nodes (e
->dest
)))
1779 bitmap_set_copy (dest
, set
);
1783 /* Allocate the phi-translation cache where we have an idea about
1784 its size. hash-table implementation internals tell us that
1785 allocating the table to fit twice the number of elements will
1786 make sure we do not usually re-allocate. */
1787 if (!PHI_TRANS_TABLE (e
->src
))
1788 PHI_TRANS_TABLE (e
->src
) = new hash_table
<expr_pred_trans_d
>
1789 (2 * bitmap_count_bits (&set
->expressions
));
1790 FOR_EACH_EXPR_ID_IN_SET (set
, i
, bi
)
1792 pre_expr expr
= expression_for_id (i
);
1793 pre_expr translated
= phi_translate (dest
, expr
, set
, NULL
, e
);
1797 bitmap_insert_into_set (dest
, translated
);
1801 /* Find the leader for a value (i.e., the name representing that
1802 value) in a given set, and return it. Return NULL if no leader
1806 bitmap_find_leader (bitmap_set_t set
, unsigned int val
)
1808 if (value_id_constant_p (val
))
1809 return constant_value_expressions
[-val
];
1811 if (bitmap_set_contains_value (set
, val
))
1813 /* Rather than walk the entire bitmap of expressions, and see
1814 whether any of them has the value we are looking for, we look
1815 at the reverse mapping, which tells us the set of expressions
1816 that have a given value (IE value->expressions with that
1817 value) and see if any of those expressions are in our set.
1818 The number of expressions per value is usually significantly
1819 less than the number of expressions in the set. In fact, for
1820 large testcases, doing it this way is roughly 5-10x faster
1821 than walking the bitmap.
1822 If this is somehow a significant lose for some cases, we can
1823 choose which set to walk based on which set is smaller. */
1826 bitmap exprset
= value_expressions
[val
];
1828 if (!exprset
->first
->next
)
1829 EXECUTE_IF_SET_IN_BITMAP (exprset
, 0, i
, bi
)
1830 if (bitmap_bit_p (&set
->expressions
, i
))
1831 return expression_for_id (i
);
1833 EXECUTE_IF_AND_IN_BITMAP (exprset
, &set
->expressions
, 0, i
, bi
)
1834 return expression_for_id (i
);
1839 /* Determine if EXPR, a memory expression, is ANTIC_IN at the top of
1840 BLOCK by seeing if it is not killed in the block. Note that we are
1841 only determining whether there is a store that kills it. Because
1842 of the order in which clean iterates over values, we are guaranteed
1843 that altered operands will have caused us to be eliminated from the
1844 ANTIC_IN set already. */
1847 value_dies_in_block_x (pre_expr expr
, basic_block block
)
1849 tree vuse
= PRE_EXPR_REFERENCE (expr
)->vuse
;
1850 vn_reference_t refx
= PRE_EXPR_REFERENCE (expr
);
1852 gimple_stmt_iterator gsi
;
1853 unsigned id
= get_expression_id (expr
);
1860 /* Lookup a previously calculated result. */
1861 if (EXPR_DIES (block
)
1862 && bitmap_bit_p (EXPR_DIES (block
), id
* 2))
1863 return bitmap_bit_p (EXPR_DIES (block
), id
* 2 + 1);
1865 /* A memory expression {e, VUSE} dies in the block if there is a
1866 statement that may clobber e. If, starting statement walk from the
1867 top of the basic block, a statement uses VUSE there can be no kill
1868 inbetween that use and the original statement that loaded {e, VUSE},
1869 so we can stop walking. */
1870 ref
.base
= NULL_TREE
;
1871 for (gsi
= gsi_start_bb (block
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1873 tree def_vuse
, def_vdef
;
1874 def
= gsi_stmt (gsi
);
1875 def_vuse
= gimple_vuse (def
);
1876 def_vdef
= gimple_vdef (def
);
1878 /* Not a memory statement. */
1882 /* Not a may-def. */
1885 /* A load with the same VUSE, we're done. */
1886 if (def_vuse
== vuse
)
1892 /* Init ref only if we really need it. */
1893 if (ref
.base
== NULL_TREE
1894 && !ao_ref_init_from_vn_reference (&ref
, refx
->set
, refx
->base_set
,
1895 refx
->type
, refx
->operands
))
1900 /* If the statement may clobber expr, it dies. */
1901 if (stmt_may_clobber_ref_p_1 (def
, &ref
))
1908 /* Remember the result. */
1909 if (!EXPR_DIES (block
))
1910 EXPR_DIES (block
) = BITMAP_ALLOC (&grand_bitmap_obstack
);
1911 bitmap_set_bit (EXPR_DIES (block
), id
* 2);
1913 bitmap_set_bit (EXPR_DIES (block
), id
* 2 + 1);
1919 /* Determine if OP is valid in SET1 U SET2, which it is when the union
1920 contains its value-id. */
1923 op_valid_in_sets (bitmap_set_t set1
, bitmap_set_t set2
, tree op
)
1925 if (op
&& TREE_CODE (op
) == SSA_NAME
)
1927 unsigned int value_id
= VN_INFO (op
)->value_id
;
1928 if (!(bitmap_set_contains_value (set1
, value_id
)
1929 || (set2
&& bitmap_set_contains_value (set2
, value_id
))))
1935 /* Determine if the expression EXPR is valid in SET1 U SET2.
1936 ONLY SET2 CAN BE NULL.
1937 This means that we have a leader for each part of the expression
1938 (if it consists of values), or the expression is an SSA_NAME.
1939 For loads/calls, we also see if the vuse is killed in this block. */
1942 valid_in_sets (bitmap_set_t set1
, bitmap_set_t set2
, pre_expr expr
)
1947 /* By construction all NAMEs are available. Non-available
1948 NAMEs are removed by subtracting TMP_GEN from the sets. */
1953 vn_nary_op_t nary
= PRE_EXPR_NARY (expr
);
1954 for (i
= 0; i
< nary
->length
; i
++)
1955 if (!op_valid_in_sets (set1
, set2
, nary
->op
[i
]))
1962 vn_reference_t ref
= PRE_EXPR_REFERENCE (expr
);
1963 vn_reference_op_t vro
;
1966 FOR_EACH_VEC_ELT (ref
->operands
, i
, vro
)
1968 if (!op_valid_in_sets (set1
, set2
, vro
->op0
)
1969 || !op_valid_in_sets (set1
, set2
, vro
->op1
)
1970 || !op_valid_in_sets (set1
, set2
, vro
->op2
))
1980 /* Clean the set of expressions SET1 that are no longer valid in SET1 or SET2.
1981 This means expressions that are made up of values we have no leaders for
1985 clean (bitmap_set_t set1
, bitmap_set_t set2
= NULL
)
1987 vec
<pre_expr
> exprs
= sorted_array_from_bitmap_set (set1
);
1991 FOR_EACH_VEC_ELT (exprs
, i
, expr
)
1993 if (!valid_in_sets (set1
, set2
, expr
))
1995 unsigned int val
= get_expr_value_id (expr
);
1996 bitmap_clear_bit (&set1
->expressions
, get_expression_id (expr
));
1997 /* We are entered with possibly multiple expressions for a value
1998 so before removing a value from the set see if there's an
1999 expression for it left. */
2000 if (! bitmap_find_leader (set1
, val
))
2001 bitmap_clear_bit (&set1
->values
, val
);
2010 FOR_EACH_EXPR_ID_IN_SET (set1
, j
, bi
)
2011 gcc_assert (valid_in_sets (set1
, set2
, expression_for_id (j
)));
2015 /* Clean the set of expressions that are no longer valid in SET because
2016 they are clobbered in BLOCK or because they trap and may not be executed. */
2019 prune_clobbered_mems (bitmap_set_t set
, basic_block block
)
2023 unsigned to_remove
= -1U;
2024 bool any_removed
= false;
2026 FOR_EACH_EXPR_ID_IN_SET (set
, i
, bi
)
2028 /* Remove queued expr. */
2029 if (to_remove
!= -1U)
2031 bitmap_clear_bit (&set
->expressions
, to_remove
);
2036 pre_expr expr
= expression_for_id (i
);
2037 if (expr
->kind
== REFERENCE
)
2039 vn_reference_t ref
= PRE_EXPR_REFERENCE (expr
);
2042 gimple
*def_stmt
= SSA_NAME_DEF_STMT (ref
->vuse
);
2043 if (!gimple_nop_p (def_stmt
)
2044 && ((gimple_bb (def_stmt
) != block
2045 && !dominated_by_p (CDI_DOMINATORS
,
2046 block
, gimple_bb (def_stmt
)))
2047 || (gimple_bb (def_stmt
) == block
2048 && value_dies_in_block_x (expr
, block
))))
2051 /* If the REFERENCE may trap make sure the block does not contain
2052 a possible exit point.
2053 ??? This is overly conservative if we translate AVAIL_OUT
2054 as the available expression might be after the exit point. */
2055 if (BB_MAY_NOTRETURN (block
)
2056 && vn_reference_may_trap (ref
))
2059 else if (expr
->kind
== NARY
)
2061 vn_nary_op_t nary
= PRE_EXPR_NARY (expr
);
2062 /* If the NARY may trap make sure the block does not contain
2063 a possible exit point.
2064 ??? This is overly conservative if we translate AVAIL_OUT
2065 as the available expression might be after the exit point. */
2066 if (BB_MAY_NOTRETURN (block
)
2067 && vn_nary_may_trap (nary
))
2072 /* Remove queued expr. */
2073 if (to_remove
!= -1U)
2075 bitmap_clear_bit (&set
->expressions
, to_remove
);
2079 /* Above we only removed expressions, now clean the set of values
2080 which no longer have any corresponding expression. We cannot
2081 clear the value at the time we remove an expression since there
2082 may be multiple expressions per value.
2083 If we'd queue possibly to be removed values we could use
2084 the bitmap_find_leader way to see if there's still an expression
2085 for it. For some ratio of to be removed values and number of
2086 values/expressions in the set this might be faster than rebuilding
2090 bitmap_clear (&set
->values
);
2091 FOR_EACH_EXPR_ID_IN_SET (set
, i
, bi
)
2093 pre_expr expr
= expression_for_id (i
);
2094 unsigned int value_id
= get_expr_value_id (expr
);
2095 bitmap_set_bit (&set
->values
, value_id
);
2100 /* Compute the ANTIC set for BLOCK.
2102 If succs(BLOCK) > 1 then
2103 ANTIC_OUT[BLOCK] = intersection of ANTIC_IN[b] for all succ(BLOCK)
2104 else if succs(BLOCK) == 1 then
2105 ANTIC_OUT[BLOCK] = phi_translate (ANTIC_IN[succ(BLOCK)])
2107 ANTIC_IN[BLOCK] = clean(ANTIC_OUT[BLOCK] U EXP_GEN[BLOCK] - TMP_GEN[BLOCK])
2109 Note that clean() is deferred until after the iteration. */
2112 compute_antic_aux (basic_block block
, bool block_has_abnormal_pred_edge
)
2114 bitmap_set_t S
, old
, ANTIC_OUT
;
2118 bool was_visited
= BB_VISITED (block
);
2119 bool changed
= ! BB_VISITED (block
);
2120 BB_VISITED (block
) = 1;
2121 old
= ANTIC_OUT
= S
= NULL
;
2123 /* If any edges from predecessors are abnormal, antic_in is empty,
2125 if (block_has_abnormal_pred_edge
)
2126 goto maybe_dump_sets
;
2128 old
= ANTIC_IN (block
);
2129 ANTIC_OUT
= bitmap_set_new ();
2131 /* If the block has no successors, ANTIC_OUT is empty. */
2132 if (EDGE_COUNT (block
->succs
) == 0)
2134 /* If we have one successor, we could have some phi nodes to
2135 translate through. */
2136 else if (single_succ_p (block
))
2138 e
= single_succ_edge (block
);
2139 gcc_assert (BB_VISITED (e
->dest
));
2140 phi_translate_set (ANTIC_OUT
, ANTIC_IN (e
->dest
), e
);
2142 /* If we have multiple successors, we take the intersection of all of
2143 them. Note that in the case of loop exit phi nodes, we may have
2144 phis to translate through. */
2150 auto_vec
<edge
> worklist (EDGE_COUNT (block
->succs
));
2151 FOR_EACH_EDGE (e
, ei
, block
->succs
)
2154 && BB_VISITED (e
->dest
))
2156 else if (BB_VISITED (e
->dest
))
2157 worklist
.quick_push (e
);
2160 /* Unvisited successors get their ANTIC_IN replaced by the
2161 maximal set to arrive at a maximum ANTIC_IN solution.
2162 We can ignore them in the intersection operation and thus
2163 need not explicitely represent that maximum solution. */
2164 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2165 fprintf (dump_file
, "ANTIC_IN is MAX on %d->%d\n",
2166 e
->src
->index
, e
->dest
->index
);
2170 /* Of multiple successors we have to have visited one already
2171 which is guaranteed by iteration order. */
2172 gcc_assert (first
!= NULL
);
2174 phi_translate_set (ANTIC_OUT
, ANTIC_IN (first
->dest
), first
);
2176 /* If we have multiple successors we need to intersect the ANTIC_OUT
2177 sets. For values that's a simple intersection but for
2178 expressions it is a union. Given we want to have a single
2179 expression per value in our sets we have to canonicalize.
2180 Avoid randomness and running into cycles like for PR82129 and
2181 canonicalize the expression we choose to the one with the
2182 lowest id. This requires we actually compute the union first. */
2183 FOR_EACH_VEC_ELT (worklist
, i
, e
)
2185 if (!gimple_seq_empty_p (phi_nodes (e
->dest
)))
2187 bitmap_set_t tmp
= bitmap_set_new ();
2188 phi_translate_set (tmp
, ANTIC_IN (e
->dest
), e
);
2189 bitmap_and_into (&ANTIC_OUT
->values
, &tmp
->values
);
2190 bitmap_ior_into (&ANTIC_OUT
->expressions
, &tmp
->expressions
);
2191 bitmap_set_free (tmp
);
2195 bitmap_and_into (&ANTIC_OUT
->values
, &ANTIC_IN (e
->dest
)->values
);
2196 bitmap_ior_into (&ANTIC_OUT
->expressions
,
2197 &ANTIC_IN (e
->dest
)->expressions
);
2200 if (! worklist
.is_empty ())
2202 /* Prune expressions not in the value set. */
2205 unsigned int to_clear
= -1U;
2206 FOR_EACH_EXPR_ID_IN_SET (ANTIC_OUT
, i
, bi
)
2208 if (to_clear
!= -1U)
2210 bitmap_clear_bit (&ANTIC_OUT
->expressions
, to_clear
);
2213 pre_expr expr
= expression_for_id (i
);
2214 unsigned int value_id
= get_expr_value_id (expr
);
2215 if (!bitmap_bit_p (&ANTIC_OUT
->values
, value_id
))
2218 if (to_clear
!= -1U)
2219 bitmap_clear_bit (&ANTIC_OUT
->expressions
, to_clear
);
2223 /* Prune expressions that are clobbered in block and thus become
2224 invalid if translated from ANTIC_OUT to ANTIC_IN. */
2225 prune_clobbered_mems (ANTIC_OUT
, block
);
2227 /* Generate ANTIC_OUT - TMP_GEN. */
2228 S
= bitmap_set_subtract_expressions (ANTIC_OUT
, TMP_GEN (block
));
2230 /* Start ANTIC_IN with EXP_GEN - TMP_GEN. */
2231 ANTIC_IN (block
) = bitmap_set_subtract_expressions (EXP_GEN (block
),
2234 /* Then union in the ANTIC_OUT - TMP_GEN values,
2235 to get ANTIC_OUT U EXP_GEN - TMP_GEN */
2236 bitmap_ior_into (&ANTIC_IN (block
)->values
, &S
->values
);
2237 bitmap_ior_into (&ANTIC_IN (block
)->expressions
, &S
->expressions
);
2239 /* clean (ANTIC_IN (block)) is defered to after the iteration converged
2240 because it can cause non-convergence, see for example PR81181. */
2242 /* Intersect ANTIC_IN with the old ANTIC_IN. This is required until
2243 we properly represent the maximum expression set, thus not prune
2244 values without expressions during the iteration. */
2246 && bitmap_and_into (&ANTIC_IN (block
)->values
, &old
->values
))
2248 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2249 fprintf (dump_file
, "warning: intersecting with old ANTIC_IN "
2250 "shrinks the set\n");
2251 /* Prune expressions not in the value set. */
2254 unsigned int to_clear
= -1U;
2255 FOR_EACH_EXPR_ID_IN_SET (ANTIC_IN (block
), i
, bi
)
2257 if (to_clear
!= -1U)
2259 bitmap_clear_bit (&ANTIC_IN (block
)->expressions
, to_clear
);
2262 pre_expr expr
= expression_for_id (i
);
2263 unsigned int value_id
= get_expr_value_id (expr
);
2264 if (!bitmap_bit_p (&ANTIC_IN (block
)->values
, value_id
))
2267 if (to_clear
!= -1U)
2268 bitmap_clear_bit (&ANTIC_IN (block
)->expressions
, to_clear
);
2271 if (!bitmap_set_equal (old
, ANTIC_IN (block
)))
2275 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2278 print_bitmap_set (dump_file
, ANTIC_OUT
, "ANTIC_OUT", block
->index
);
2281 fprintf (dump_file
, "[changed] ");
2282 print_bitmap_set (dump_file
, ANTIC_IN (block
), "ANTIC_IN",
2286 print_bitmap_set (dump_file
, S
, "S", block
->index
);
2289 bitmap_set_free (old
);
2291 bitmap_set_free (S
);
2293 bitmap_set_free (ANTIC_OUT
);
2297 /* Compute PARTIAL_ANTIC for BLOCK.
2299 If succs(BLOCK) > 1 then
2300 PA_OUT[BLOCK] = value wise union of PA_IN[b] + all ANTIC_IN not
2301 in ANTIC_OUT for all succ(BLOCK)
2302 else if succs(BLOCK) == 1 then
2303 PA_OUT[BLOCK] = phi_translate (PA_IN[succ(BLOCK)])
2305 PA_IN[BLOCK] = clean(PA_OUT[BLOCK] - TMP_GEN[BLOCK] - ANTIC_IN[BLOCK])
2309 compute_partial_antic_aux (basic_block block
,
2310 bool block_has_abnormal_pred_edge
)
2312 bitmap_set_t old_PA_IN
;
2313 bitmap_set_t PA_OUT
;
2316 unsigned long max_pa
= param_max_partial_antic_length
;
2318 old_PA_IN
= PA_OUT
= NULL
;
2320 /* If any edges from predecessors are abnormal, antic_in is empty,
2322 if (block_has_abnormal_pred_edge
)
2323 goto maybe_dump_sets
;
2325 /* If there are too many partially anticipatable values in the
2326 block, phi_translate_set can take an exponential time: stop
2327 before the translation starts. */
2329 && single_succ_p (block
)
2330 && bitmap_count_bits (&PA_IN (single_succ (block
))->values
) > max_pa
)
2331 goto maybe_dump_sets
;
2333 old_PA_IN
= PA_IN (block
);
2334 PA_OUT
= bitmap_set_new ();
2336 /* If the block has no successors, ANTIC_OUT is empty. */
2337 if (EDGE_COUNT (block
->succs
) == 0)
2339 /* If we have one successor, we could have some phi nodes to
2340 translate through. Note that we can't phi translate across DFS
2341 back edges in partial antic, because it uses a union operation on
2342 the successors. For recurrences like IV's, we will end up
2343 generating a new value in the set on each go around (i + 3 (VH.1)
2344 VH.1 + 1 (VH.2), VH.2 + 1 (VH.3), etc), forever. */
2345 else if (single_succ_p (block
))
2347 e
= single_succ_edge (block
);
2348 if (!(e
->flags
& EDGE_DFS_BACK
))
2349 phi_translate_set (PA_OUT
, PA_IN (e
->dest
), e
);
2351 /* If we have multiple successors, we take the union of all of
2357 auto_vec
<edge
> worklist (EDGE_COUNT (block
->succs
));
2358 FOR_EACH_EDGE (e
, ei
, block
->succs
)
2360 if (e
->flags
& EDGE_DFS_BACK
)
2362 worklist
.quick_push (e
);
2364 if (worklist
.length () > 0)
2366 FOR_EACH_VEC_ELT (worklist
, i
, e
)
2371 FOR_EACH_EXPR_ID_IN_SET (ANTIC_IN (e
->dest
), i
, bi
)
2372 bitmap_value_insert_into_set (PA_OUT
,
2373 expression_for_id (i
));
2374 if (!gimple_seq_empty_p (phi_nodes (e
->dest
)))
2376 bitmap_set_t pa_in
= bitmap_set_new ();
2377 phi_translate_set (pa_in
, PA_IN (e
->dest
), e
);
2378 FOR_EACH_EXPR_ID_IN_SET (pa_in
, i
, bi
)
2379 bitmap_value_insert_into_set (PA_OUT
,
2380 expression_for_id (i
));
2381 bitmap_set_free (pa_in
);
2384 FOR_EACH_EXPR_ID_IN_SET (PA_IN (e
->dest
), i
, bi
)
2385 bitmap_value_insert_into_set (PA_OUT
,
2386 expression_for_id (i
));
2391 /* Prune expressions that are clobbered in block and thus become
2392 invalid if translated from PA_OUT to PA_IN. */
2393 prune_clobbered_mems (PA_OUT
, block
);
2395 /* PA_IN starts with PA_OUT - TMP_GEN.
2396 Then we subtract things from ANTIC_IN. */
2397 PA_IN (block
) = bitmap_set_subtract_expressions (PA_OUT
, TMP_GEN (block
));
2399 /* For partial antic, we want to put back in the phi results, since
2400 we will properly avoid making them partially antic over backedges. */
2401 bitmap_ior_into (&PA_IN (block
)->values
, &PHI_GEN (block
)->values
);
2402 bitmap_ior_into (&PA_IN (block
)->expressions
, &PHI_GEN (block
)->expressions
);
2404 /* PA_IN[block] = PA_IN[block] - ANTIC_IN[block] */
2405 bitmap_set_subtract_values (PA_IN (block
), ANTIC_IN (block
));
2407 clean (PA_IN (block
), ANTIC_IN (block
));
2410 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2413 print_bitmap_set (dump_file
, PA_OUT
, "PA_OUT", block
->index
);
2415 print_bitmap_set (dump_file
, PA_IN (block
), "PA_IN", block
->index
);
2418 bitmap_set_free (old_PA_IN
);
2420 bitmap_set_free (PA_OUT
);
2423 /* Compute ANTIC and partial ANTIC sets. */
2426 compute_antic (void)
2428 bool changed
= true;
2429 int num_iterations
= 0;
2435 /* If any predecessor edges are abnormal, we punt, so antic_in is empty.
2436 We pre-build the map of blocks with incoming abnormal edges here. */
2437 auto_sbitmap
has_abnormal_preds (last_basic_block_for_fn (cfun
));
2438 bitmap_clear (has_abnormal_preds
);
2440 FOR_ALL_BB_FN (block
, cfun
)
2442 BB_VISITED (block
) = 0;
2444 FOR_EACH_EDGE (e
, ei
, block
->preds
)
2445 if (e
->flags
& EDGE_ABNORMAL
)
2447 bitmap_set_bit (has_abnormal_preds
, block
->index
);
2451 /* While we are here, give empty ANTIC_IN sets to each block. */
2452 ANTIC_IN (block
) = bitmap_set_new ();
2453 if (do_partial_partial
)
2454 PA_IN (block
) = bitmap_set_new ();
2457 /* At the exit block we anticipate nothing. */
2458 BB_VISITED (EXIT_BLOCK_PTR_FOR_FN (cfun
)) = 1;
2460 /* For ANTIC computation we need a postorder that also guarantees that
2461 a block with a single successor is visited after its successor.
2462 RPO on the inverted CFG has this property. */
2463 auto_vec
<int, 20> postorder
;
2464 inverted_post_order_compute (&postorder
);
2466 auto_sbitmap
worklist (last_basic_block_for_fn (cfun
) + 1);
2467 bitmap_clear (worklist
);
2468 FOR_EACH_EDGE (e
, ei
, EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
)
2469 bitmap_set_bit (worklist
, e
->src
->index
);
2472 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2473 fprintf (dump_file
, "Starting iteration %d\n", num_iterations
);
2474 /* ??? We need to clear our PHI translation cache here as the
2475 ANTIC sets shrink and we restrict valid translations to
2476 those having operands with leaders in ANTIC. Same below
2477 for PA ANTIC computation. */
2480 for (i
= postorder
.length () - 1; i
>= 0; i
--)
2482 if (bitmap_bit_p (worklist
, postorder
[i
]))
2484 basic_block block
= BASIC_BLOCK_FOR_FN (cfun
, postorder
[i
]);
2485 bitmap_clear_bit (worklist
, block
->index
);
2486 if (compute_antic_aux (block
,
2487 bitmap_bit_p (has_abnormal_preds
,
2490 FOR_EACH_EDGE (e
, ei
, block
->preds
)
2491 bitmap_set_bit (worklist
, e
->src
->index
);
2496 /* Theoretically possible, but *highly* unlikely. */
2497 gcc_checking_assert (num_iterations
< 500);
2500 /* We have to clean after the dataflow problem converged as cleaning
2501 can cause non-convergence because it is based on expressions
2502 rather than values. */
2503 FOR_EACH_BB_FN (block
, cfun
)
2504 clean (ANTIC_IN (block
));
2506 statistics_histogram_event (cfun
, "compute_antic iterations",
2509 if (do_partial_partial
)
2511 /* For partial antic we ignore backedges and thus we do not need
2512 to perform any iteration when we process blocks in postorder. */
2513 for (i
= postorder
.length () - 1; i
>= 0; i
--)
2515 basic_block block
= BASIC_BLOCK_FOR_FN (cfun
, postorder
[i
]);
2516 compute_partial_antic_aux (block
,
2517 bitmap_bit_p (has_abnormal_preds
,
2524 /* Inserted expressions are placed onto this worklist, which is used
2525 for performing quick dead code elimination of insertions we made
2526 that didn't turn out to be necessary. */
2527 static bitmap inserted_exprs
;
2529 /* The actual worker for create_component_ref_by_pieces. */
2532 create_component_ref_by_pieces_1 (basic_block block
, vn_reference_t ref
,
2533 unsigned int *operand
, gimple_seq
*stmts
)
2535 vn_reference_op_t currop
= &ref
->operands
[*operand
];
2538 switch (currop
->opcode
)
2545 tree baseop
= create_component_ref_by_pieces_1 (block
, ref
, operand
,
2549 tree offset
= currop
->op0
;
2550 if (TREE_CODE (baseop
) == ADDR_EXPR
2551 && handled_component_p (TREE_OPERAND (baseop
, 0)))
2555 base
= get_addr_base_and_unit_offset (TREE_OPERAND (baseop
, 0),
2558 offset
= int_const_binop (PLUS_EXPR
, offset
,
2559 build_int_cst (TREE_TYPE (offset
),
2561 baseop
= build_fold_addr_expr (base
);
2563 genop
= build2 (MEM_REF
, currop
->type
, baseop
, offset
);
2564 MR_DEPENDENCE_CLIQUE (genop
) = currop
->clique
;
2565 MR_DEPENDENCE_BASE (genop
) = currop
->base
;
2566 REF_REVERSE_STORAGE_ORDER (genop
) = currop
->reverse
;
2570 case TARGET_MEM_REF
:
2572 tree genop0
= NULL_TREE
, genop1
= NULL_TREE
;
2573 vn_reference_op_t nextop
= &ref
->operands
[(*operand
)++];
2574 tree baseop
= create_component_ref_by_pieces_1 (block
, ref
, operand
,
2580 genop0
= find_or_generate_expression (block
, currop
->op0
, stmts
);
2586 genop1
= find_or_generate_expression (block
, nextop
->op0
, stmts
);
2590 genop
= build5 (TARGET_MEM_REF
, currop
->type
,
2591 baseop
, currop
->op2
, genop0
, currop
->op1
, genop1
);
2593 MR_DEPENDENCE_CLIQUE (genop
) = currop
->clique
;
2594 MR_DEPENDENCE_BASE (genop
) = currop
->base
;
2601 gcc_assert (is_gimple_min_invariant (currop
->op0
));
2607 case VIEW_CONVERT_EXPR
:
2609 tree genop0
= create_component_ref_by_pieces_1 (block
, ref
, operand
,
2613 return fold_build1 (currop
->opcode
, currop
->type
, genop0
);
2616 case WITH_SIZE_EXPR
:
2618 tree genop0
= create_component_ref_by_pieces_1 (block
, ref
, operand
,
2622 tree genop1
= find_or_generate_expression (block
, currop
->op0
, stmts
);
2625 return fold_build2 (currop
->opcode
, currop
->type
, genop0
, genop1
);
2630 tree genop0
= create_component_ref_by_pieces_1 (block
, ref
, operand
,
2634 tree op1
= currop
->op0
;
2635 tree op2
= currop
->op1
;
2636 tree t
= build3 (BIT_FIELD_REF
, currop
->type
, genop0
, op1
, op2
);
2637 REF_REVERSE_STORAGE_ORDER (t
) = currop
->reverse
;
2641 /* For array ref vn_reference_op's, operand 1 of the array ref
2642 is op0 of the reference op and operand 3 of the array ref is
2644 case ARRAY_RANGE_REF
:
2648 tree genop1
= currop
->op0
;
2649 tree genop2
= currop
->op1
;
2650 tree genop3
= currop
->op2
;
2651 genop0
= create_component_ref_by_pieces_1 (block
, ref
, operand
,
2655 genop1
= find_or_generate_expression (block
, genop1
, stmts
);
2660 tree domain_type
= TYPE_DOMAIN (TREE_TYPE (genop0
));
2661 /* Drop zero minimum index if redundant. */
2662 if (integer_zerop (genop2
)
2664 || integer_zerop (TYPE_MIN_VALUE (domain_type
))))
2668 genop2
= find_or_generate_expression (block
, genop2
, stmts
);
2675 tree elmt_type
= TREE_TYPE (TREE_TYPE (genop0
));
2676 /* We can't always put a size in units of the element alignment
2677 here as the element alignment may be not visible. See
2678 PR43783. Simply drop the element size for constant
2680 if (TREE_CODE (genop3
) == INTEGER_CST
2681 && TREE_CODE (TYPE_SIZE_UNIT (elmt_type
)) == INTEGER_CST
2682 && wi::eq_p (wi::to_offset (TYPE_SIZE_UNIT (elmt_type
)),
2683 (wi::to_offset (genop3
)
2684 * vn_ref_op_align_unit (currop
))))
2688 genop3
= find_or_generate_expression (block
, genop3
, stmts
);
2693 return build4 (currop
->opcode
, currop
->type
, genop0
, genop1
,
2700 tree genop2
= currop
->op1
;
2701 op0
= create_component_ref_by_pieces_1 (block
, ref
, operand
, stmts
);
2704 /* op1 should be a FIELD_DECL, which are represented by themselves. */
2708 genop2
= find_or_generate_expression (block
, genop2
, stmts
);
2712 return fold_build3 (COMPONENT_REF
, TREE_TYPE (op1
), op0
, op1
, genop2
);
2717 genop
= find_or_generate_expression (block
, currop
->op0
, stmts
);
2739 /* For COMPONENT_REF's and ARRAY_REF's, we can't have any intermediates for the
2740 COMPONENT_REF or MEM_REF or ARRAY_REF portion, because we'd end up with
2741 trying to rename aggregates into ssa form directly, which is a no no.
2743 Thus, this routine doesn't create temporaries, it just builds a
2744 single access expression for the array, calling
2745 find_or_generate_expression to build the innermost pieces.
2747 This function is a subroutine of create_expression_by_pieces, and
2748 should not be called on it's own unless you really know what you
2752 create_component_ref_by_pieces (basic_block block
, vn_reference_t ref
,
2755 unsigned int op
= 0;
2756 return create_component_ref_by_pieces_1 (block
, ref
, &op
, stmts
);
2759 /* Find a simple leader for an expression, or generate one using
2760 create_expression_by_pieces from a NARY expression for the value.
2761 BLOCK is the basic_block we are looking for leaders in.
2762 OP is the tree expression to find a leader for or generate.
2763 Returns the leader or NULL_TREE on failure. */
2766 find_or_generate_expression (basic_block block
, tree op
, gimple_seq
*stmts
)
2768 pre_expr expr
= get_or_alloc_expr_for (op
);
2769 unsigned int lookfor
= get_expr_value_id (expr
);
2770 pre_expr leader
= bitmap_find_leader (AVAIL_OUT (block
), lookfor
);
2773 if (leader
->kind
== NAME
)
2774 return PRE_EXPR_NAME (leader
);
2775 else if (leader
->kind
== CONSTANT
)
2776 return PRE_EXPR_CONSTANT (leader
);
2782 /* It must be a complex expression, so generate it recursively. Note
2783 that this is only necessary to handle gcc.dg/tree-ssa/ssa-pre28.c
2784 where the insert algorithm fails to insert a required expression. */
2785 bitmap exprset
= value_expressions
[lookfor
];
2788 EXECUTE_IF_SET_IN_BITMAP (exprset
, 0, i
, bi
)
2790 pre_expr temp
= expression_for_id (i
);
2791 /* We cannot insert random REFERENCE expressions at arbitrary
2792 places. We can insert NARYs which eventually re-materializes
2793 its operand values. */
2794 if (temp
->kind
== NARY
)
2795 return create_expression_by_pieces (block
, temp
, stmts
,
2796 get_expr_type (expr
));
2803 /* Create an expression in pieces, so that we can handle very complex
2804 expressions that may be ANTIC, but not necessary GIMPLE.
2805 BLOCK is the basic block the expression will be inserted into,
2806 EXPR is the expression to insert (in value form)
2807 STMTS is a statement list to append the necessary insertions into.
2809 This function will die if we hit some value that shouldn't be
2810 ANTIC but is (IE there is no leader for it, or its components).
2811 The function returns NULL_TREE in case a different antic expression
2812 has to be inserted first.
2813 This function may also generate expressions that are themselves
2814 partially or fully redundant. Those that are will be either made
2815 fully redundant during the next iteration of insert (for partially
2816 redundant ones), or eliminated by eliminate (for fully redundant
2820 create_expression_by_pieces (basic_block block
, pre_expr expr
,
2821 gimple_seq
*stmts
, tree type
)
2825 gimple_seq forced_stmts
= NULL
;
2826 unsigned int value_id
;
2827 gimple_stmt_iterator gsi
;
2828 tree exprtype
= type
? type
: get_expr_type (expr
);
2834 /* We may hit the NAME/CONSTANT case if we have to convert types
2835 that value numbering saw through. */
2837 folded
= PRE_EXPR_NAME (expr
);
2838 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (folded
))
2840 if (useless_type_conversion_p (exprtype
, TREE_TYPE (folded
)))
2845 folded
= PRE_EXPR_CONSTANT (expr
);
2846 tree tem
= fold_convert (exprtype
, folded
);
2847 if (is_gimple_min_invariant (tem
))
2852 if (PRE_EXPR_REFERENCE (expr
)->operands
[0].opcode
== CALL_EXPR
)
2854 vn_reference_t ref
= PRE_EXPR_REFERENCE (expr
);
2855 unsigned int operand
= 1;
2856 vn_reference_op_t currop
= &ref
->operands
[0];
2857 tree sc
= NULL_TREE
;
2858 tree fn
= NULL_TREE
;
2861 fn
= find_or_generate_expression (block
, currop
->op0
, stmts
);
2867 sc
= find_or_generate_expression (block
, currop
->op1
, stmts
);
2871 auto_vec
<tree
> args (ref
->operands
.length () - 1);
2872 while (operand
< ref
->operands
.length ())
2874 tree arg
= create_component_ref_by_pieces_1 (block
, ref
,
2878 args
.quick_push (arg
);
2883 call
= gimple_build_call_vec (fn
, args
);
2884 gimple_call_set_fntype (call
, currop
->type
);
2887 call
= gimple_build_call_internal_vec ((internal_fn
)currop
->clique
,
2889 gimple_set_location (call
, expr
->loc
);
2891 gimple_call_set_chain (call
, sc
);
2892 tree forcedname
= make_ssa_name (ref
->type
);
2893 gimple_call_set_lhs (call
, forcedname
);
2894 /* There's no CCP pass after PRE which would re-compute alignment
2895 information so make sure we re-materialize this here. */
2896 if (gimple_call_builtin_p (call
, BUILT_IN_ASSUME_ALIGNED
)
2897 && args
.length () - 2 <= 1
2898 && tree_fits_uhwi_p (args
[1])
2899 && (args
.length () != 3 || tree_fits_uhwi_p (args
[2])))
2901 unsigned HOST_WIDE_INT halign
= tree_to_uhwi (args
[1]);
2902 unsigned HOST_WIDE_INT hmisalign
2903 = args
.length () == 3 ? tree_to_uhwi (args
[2]) : 0;
2904 if ((halign
& (halign
- 1)) == 0
2905 && (hmisalign
& ~(halign
- 1)) == 0
2906 && (unsigned int)halign
!= 0)
2907 set_ptr_info_alignment (get_ptr_info (forcedname
),
2910 gimple_set_vuse (call
, BB_LIVE_VOP_ON_EXIT (block
));
2911 gimple_seq_add_stmt_without_update (&forced_stmts
, call
);
2912 folded
= forcedname
;
2916 folded
= create_component_ref_by_pieces (block
,
2917 PRE_EXPR_REFERENCE (expr
),
2921 name
= make_temp_ssa_name (exprtype
, NULL
, "pretmp");
2922 newstmt
= gimple_build_assign (name
, folded
);
2923 gimple_set_location (newstmt
, expr
->loc
);
2924 gimple_seq_add_stmt_without_update (&forced_stmts
, newstmt
);
2925 gimple_set_vuse (newstmt
, BB_LIVE_VOP_ON_EXIT (block
));
2931 vn_nary_op_t nary
= PRE_EXPR_NARY (expr
);
2932 tree
*genop
= XALLOCAVEC (tree
, nary
->length
);
2934 for (i
= 0; i
< nary
->length
; ++i
)
2936 genop
[i
] = find_or_generate_expression (block
, nary
->op
[i
], stmts
);
2939 /* Ensure genop[] is properly typed for POINTER_PLUS_EXPR. It
2940 may have conversions stripped. */
2941 if (nary
->opcode
== POINTER_PLUS_EXPR
)
2944 genop
[i
] = gimple_convert (&forced_stmts
,
2945 nary
->type
, genop
[i
]);
2947 genop
[i
] = gimple_convert (&forced_stmts
,
2948 sizetype
, genop
[i
]);
2951 genop
[i
] = gimple_convert (&forced_stmts
,
2952 TREE_TYPE (nary
->op
[i
]), genop
[i
]);
2954 if (nary
->opcode
== CONSTRUCTOR
)
2956 vec
<constructor_elt
, va_gc
> *elts
= NULL
;
2957 for (i
= 0; i
< nary
->length
; ++i
)
2958 CONSTRUCTOR_APPEND_ELT (elts
, NULL_TREE
, genop
[i
]);
2959 folded
= build_constructor (nary
->type
, elts
);
2960 name
= make_temp_ssa_name (exprtype
, NULL
, "pretmp");
2961 newstmt
= gimple_build_assign (name
, folded
);
2962 gimple_set_location (newstmt
, expr
->loc
);
2963 gimple_seq_add_stmt_without_update (&forced_stmts
, newstmt
);
2968 switch (nary
->length
)
2971 folded
= gimple_build (&forced_stmts
, expr
->loc
,
2972 nary
->opcode
, nary
->type
, genop
[0]);
2975 folded
= gimple_build (&forced_stmts
, expr
->loc
, nary
->opcode
,
2976 nary
->type
, genop
[0], genop
[1]);
2979 folded
= gimple_build (&forced_stmts
, expr
->loc
, nary
->opcode
,
2980 nary
->type
, genop
[0], genop
[1],
2993 folded
= gimple_convert (&forced_stmts
, exprtype
, folded
);
2995 /* If there is nothing to insert, return the simplified result. */
2996 if (gimple_seq_empty_p (forced_stmts
))
2998 /* If we simplified to a constant return it and discard eventually
3000 if (is_gimple_min_invariant (folded
))
3002 gimple_seq_discard (forced_stmts
);
3005 /* Likewise if we simplified to sth not queued for insertion. */
3007 gsi
= gsi_last (forced_stmts
);
3008 for (; !gsi_end_p (gsi
); gsi_prev (&gsi
))
3010 gimple
*stmt
= gsi_stmt (gsi
);
3011 tree forcedname
= gimple_get_lhs (stmt
);
3012 if (forcedname
== folded
)
3020 gimple_seq_discard (forced_stmts
);
3023 gcc_assert (TREE_CODE (folded
) == SSA_NAME
);
3025 /* If we have any intermediate expressions to the value sets, add them
3026 to the value sets and chain them in the instruction stream. */
3029 gsi
= gsi_start (forced_stmts
);
3030 for (; !gsi_end_p (gsi
); gsi_next (&gsi
))
3032 gimple
*stmt
= gsi_stmt (gsi
);
3033 tree forcedname
= gimple_get_lhs (stmt
);
3036 if (forcedname
!= folded
)
3038 vn_ssa_aux_t vn_info
= VN_INFO (forcedname
);
3039 vn_info
->valnum
= forcedname
;
3040 vn_info
->value_id
= get_next_value_id ();
3041 nameexpr
= get_or_alloc_expr_for_name (forcedname
);
3042 add_to_value (vn_info
->value_id
, nameexpr
);
3043 if (NEW_SETS (block
))
3044 bitmap_value_replace_in_set (NEW_SETS (block
), nameexpr
);
3045 bitmap_value_replace_in_set (AVAIL_OUT (block
), nameexpr
);
3048 bitmap_set_bit (inserted_exprs
, SSA_NAME_VERSION (forcedname
));
3050 gimple_seq_add_seq (stmts
, forced_stmts
);
3055 /* Fold the last statement. */
3056 gsi
= gsi_last (*stmts
);
3057 if (fold_stmt_inplace (&gsi
))
3058 update_stmt (gsi_stmt (gsi
));
3060 /* Add a value number to the temporary.
3061 The value may already exist in either NEW_SETS, or AVAIL_OUT, because
3062 we are creating the expression by pieces, and this particular piece of
3063 the expression may have been represented. There is no harm in replacing
3065 value_id
= get_expr_value_id (expr
);
3066 vn_ssa_aux_t vn_info
= VN_INFO (name
);
3067 vn_info
->value_id
= value_id
;
3068 vn_info
->valnum
= vn_valnum_from_value_id (value_id
);
3069 if (vn_info
->valnum
== NULL_TREE
)
3070 vn_info
->valnum
= name
;
3071 gcc_assert (vn_info
->valnum
!= NULL_TREE
);
3072 nameexpr
= get_or_alloc_expr_for_name (name
);
3073 add_to_value (value_id
, nameexpr
);
3074 if (NEW_SETS (block
))
3075 bitmap_value_replace_in_set (NEW_SETS (block
), nameexpr
);
3076 bitmap_value_replace_in_set (AVAIL_OUT (block
), nameexpr
);
3078 pre_stats
.insertions
++;
3079 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3081 fprintf (dump_file
, "Inserted ");
3082 print_gimple_stmt (dump_file
, gsi_stmt (gsi_last (*stmts
)), 0);
3083 fprintf (dump_file
, " in predecessor %d (%04d)\n",
3084 block
->index
, value_id
);
3091 /* Insert the to-be-made-available values of expression EXPRNUM for each
3092 predecessor, stored in AVAIL, into the predecessors of BLOCK, and
3093 merge the result with a phi node, given the same value number as
3094 NODE. Return true if we have inserted new stuff. */
3097 insert_into_preds_of_block (basic_block block
, unsigned int exprnum
,
3098 vec
<pre_expr
> &avail
)
3100 pre_expr expr
= expression_for_id (exprnum
);
3102 unsigned int val
= get_expr_value_id (expr
);
3104 bool insertions
= false;
3109 tree type
= get_expr_type (expr
);
3113 /* Make sure we aren't creating an induction variable. */
3114 if (bb_loop_depth (block
) > 0 && EDGE_COUNT (block
->preds
) == 2)
3116 bool firstinsideloop
= false;
3117 bool secondinsideloop
= false;
3118 firstinsideloop
= flow_bb_inside_loop_p (block
->loop_father
,
3119 EDGE_PRED (block
, 0)->src
);
3120 secondinsideloop
= flow_bb_inside_loop_p (block
->loop_father
,
3121 EDGE_PRED (block
, 1)->src
);
3122 /* Induction variables only have one edge inside the loop. */
3123 if ((firstinsideloop
^ secondinsideloop
)
3124 && expr
->kind
!= REFERENCE
)
3126 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3127 fprintf (dump_file
, "Skipping insertion of phi for partial "
3128 "redundancy: Looks like an induction variable\n");
3133 /* Make the necessary insertions. */
3134 FOR_EACH_EDGE (pred
, ei
, block
->preds
)
3136 /* When we are not inserting a PHI node do not bother inserting
3137 into places that do not dominate the anticipated computations. */
3138 if (nophi
&& !dominated_by_p (CDI_DOMINATORS
, block
, pred
->src
))
3140 gimple_seq stmts
= NULL
;
3143 eprime
= avail
[pred
->dest_idx
];
3144 builtexpr
= create_expression_by_pieces (bprime
, eprime
,
3146 gcc_assert (!(pred
->flags
& EDGE_ABNORMAL
));
3147 if (!gimple_seq_empty_p (stmts
))
3149 basic_block new_bb
= gsi_insert_seq_on_edge_immediate (pred
, stmts
);
3150 gcc_assert (! new_bb
);
3155 /* We cannot insert a PHI node if we failed to insert
3160 if (is_gimple_min_invariant (builtexpr
))
3161 avail
[pred
->dest_idx
] = get_or_alloc_expr_for_constant (builtexpr
);
3163 avail
[pred
->dest_idx
] = get_or_alloc_expr_for_name (builtexpr
);
3165 /* If we didn't want a phi node, and we made insertions, we still have
3166 inserted new stuff, and thus return true. If we didn't want a phi node,
3167 and didn't make insertions, we haven't added anything new, so return
3169 if (nophi
&& insertions
)
3171 else if (nophi
&& !insertions
)
3174 /* Now build a phi for the new variable. */
3175 temp
= make_temp_ssa_name (type
, NULL
, "prephitmp");
3176 phi
= create_phi_node (temp
, block
);
3178 vn_ssa_aux_t vn_info
= VN_INFO (temp
);
3179 vn_info
->value_id
= val
;
3180 vn_info
->valnum
= vn_valnum_from_value_id (val
);
3181 if (vn_info
->valnum
== NULL_TREE
)
3182 vn_info
->valnum
= temp
;
3183 bitmap_set_bit (inserted_exprs
, SSA_NAME_VERSION (temp
));
3184 FOR_EACH_EDGE (pred
, ei
, block
->preds
)
3186 pre_expr ae
= avail
[pred
->dest_idx
];
3187 gcc_assert (get_expr_type (ae
) == type
3188 || useless_type_conversion_p (type
, get_expr_type (ae
)));
3189 if (ae
->kind
== CONSTANT
)
3190 add_phi_arg (phi
, unshare_expr (PRE_EXPR_CONSTANT (ae
)),
3191 pred
, UNKNOWN_LOCATION
);
3193 add_phi_arg (phi
, PRE_EXPR_NAME (ae
), pred
, UNKNOWN_LOCATION
);
3196 newphi
= get_or_alloc_expr_for_name (temp
);
3197 add_to_value (val
, newphi
);
3199 /* The value should *not* exist in PHI_GEN, or else we wouldn't be doing
3200 this insertion, since we test for the existence of this value in PHI_GEN
3201 before proceeding with the partial redundancy checks in insert_aux.
3203 The value may exist in AVAIL_OUT, in particular, it could be represented
3204 by the expression we are trying to eliminate, in which case we want the
3205 replacement to occur. If it's not existing in AVAIL_OUT, we want it
3208 Similarly, to the PHI_GEN case, the value should not exist in NEW_SETS of
3209 this block, because if it did, it would have existed in our dominator's
3210 AVAIL_OUT, and would have been skipped due to the full redundancy check.
3213 bitmap_insert_into_set (PHI_GEN (block
), newphi
);
3214 bitmap_value_replace_in_set (AVAIL_OUT (block
),
3216 if (NEW_SETS (block
))
3217 bitmap_insert_into_set (NEW_SETS (block
), newphi
);
3219 /* If we insert a PHI node for a conversion of another PHI node
3220 in the same basic-block try to preserve range information.
3221 This is important so that followup loop passes receive optimal
3222 number of iteration analysis results. See PR61743. */
3223 if (expr
->kind
== NARY
3224 && CONVERT_EXPR_CODE_P (expr
->u
.nary
->opcode
)
3225 && TREE_CODE (expr
->u
.nary
->op
[0]) == SSA_NAME
3226 && gimple_bb (SSA_NAME_DEF_STMT (expr
->u
.nary
->op
[0])) == block
3227 && INTEGRAL_TYPE_P (type
)
3228 && INTEGRAL_TYPE_P (TREE_TYPE (expr
->u
.nary
->op
[0]))
3229 && (TYPE_PRECISION (type
)
3230 >= TYPE_PRECISION (TREE_TYPE (expr
->u
.nary
->op
[0])))
3231 && SSA_NAME_RANGE_INFO (expr
->u
.nary
->op
[0]))
3234 if (get_range_query (cfun
)->range_of_expr (r
, expr
->u
.nary
->op
[0])
3235 && r
.kind () == VR_RANGE
3236 && !wi::neg_p (r
.lower_bound (), SIGNED
)
3237 && !wi::neg_p (r
.upper_bound (), SIGNED
))
3238 /* Just handle extension and sign-changes of all-positive ranges. */
3239 set_range_info (temp
, VR_RANGE
,
3240 wide_int_storage::from (r
.lower_bound (),
3241 TYPE_PRECISION (type
),
3243 wide_int_storage::from (r
.upper_bound (),
3244 TYPE_PRECISION (type
),
3248 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3250 fprintf (dump_file
, "Created phi ");
3251 print_gimple_stmt (dump_file
, phi
, 0);
3252 fprintf (dump_file
, " in block %d (%04d)\n", block
->index
, val
);
3260 /* Perform insertion of partially redundant or hoistable values.
3261 For BLOCK, do the following:
3262 1. Propagate the NEW_SETS of the dominator into the current block.
3263 If the block has multiple predecessors,
3264 2a. Iterate over the ANTIC expressions for the block to see if
3265 any of them are partially redundant.
3266 2b. If so, insert them into the necessary predecessors to make
3267 the expression fully redundant.
3268 2c. Insert a new PHI merging the values of the predecessors.
3269 2d. Insert the new PHI, and the new expressions, into the
3271 If the block has multiple successors,
3272 3a. Iterate over the ANTIC values for the block to see if
3273 any of them are good candidates for hoisting.
3274 3b. If so, insert expressions computing the values in BLOCK,
3275 and add the new expressions into the NEW_SETS set.
3276 4. Recursively call ourselves on the dominator children of BLOCK.
3278 Steps 1, 2a, and 4 are done by insert_aux. 2b, 2c and 2d are done by
3279 do_pre_regular_insertion and do_partial_insertion. 3a and 3b are
3280 done in do_hoist_insertion.
3284 do_pre_regular_insertion (basic_block block
, basic_block dom
,
3285 vec
<pre_expr
> exprs
)
3287 bool new_stuff
= false;
3289 auto_vec
<pre_expr
, 2> avail
;
3292 avail
.safe_grow (EDGE_COUNT (block
->preds
), true);
3294 FOR_EACH_VEC_ELT (exprs
, i
, expr
)
3296 if (expr
->kind
== NARY
3297 || expr
->kind
== REFERENCE
)
3300 bool by_some
= false;
3301 bool cant_insert
= false;
3302 bool all_same
= true;
3303 pre_expr first_s
= NULL
;
3306 pre_expr eprime
= NULL
;
3308 pre_expr edoubleprime
= NULL
;
3309 bool do_insertion
= false;
3311 val
= get_expr_value_id (expr
);
3312 if (bitmap_set_contains_value (PHI_GEN (block
), val
))
3314 if (bitmap_set_contains_value (AVAIL_OUT (dom
), val
))
3316 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3318 fprintf (dump_file
, "Found fully redundant value: ");
3319 print_pre_expr (dump_file
, expr
);
3320 fprintf (dump_file
, "\n");
3325 FOR_EACH_EDGE (pred
, ei
, block
->preds
)
3327 unsigned int vprime
;
3329 /* We should never run insertion for the exit block
3330 and so not come across fake pred edges. */
3331 gcc_assert (!(pred
->flags
& EDGE_FAKE
));
3333 /* We are looking at ANTIC_OUT of bprime. */
3334 eprime
= phi_translate (NULL
, expr
, ANTIC_IN (block
), NULL
, pred
);
3336 /* eprime will generally only be NULL if the
3337 value of the expression, translated
3338 through the PHI for this predecessor, is
3339 undefined. If that is the case, we can't
3340 make the expression fully redundant,
3341 because its value is undefined along a
3342 predecessor path. We can thus break out
3343 early because it doesn't matter what the
3344 rest of the results are. */
3347 avail
[pred
->dest_idx
] = NULL
;
3352 vprime
= get_expr_value_id (eprime
);
3353 edoubleprime
= bitmap_find_leader (AVAIL_OUT (bprime
),
3355 if (edoubleprime
== NULL
)
3357 avail
[pred
->dest_idx
] = eprime
;
3362 avail
[pred
->dest_idx
] = edoubleprime
;
3364 /* We want to perform insertions to remove a redundancy on
3365 a path in the CFG we want to optimize for speed. */
3366 if (optimize_edge_for_speed_p (pred
))
3367 do_insertion
= true;
3368 if (first_s
== NULL
)
3369 first_s
= edoubleprime
;
3370 else if (!pre_expr_d::equal (first_s
, edoubleprime
))
3374 /* If we can insert it, it's not the same value
3375 already existing along every predecessor, and
3376 it's defined by some predecessor, it is
3377 partially redundant. */
3378 if (!cant_insert
&& !all_same
&& by_some
)
3382 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3384 fprintf (dump_file
, "Skipping partial redundancy for "
3386 print_pre_expr (dump_file
, expr
);
3387 fprintf (dump_file
, " (%04d), no redundancy on to be "
3388 "optimized for speed edge\n", val
);
3391 else if (dbg_cnt (treepre_insert
))
3393 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3395 fprintf (dump_file
, "Found partial redundancy for "
3397 print_pre_expr (dump_file
, expr
);
3398 fprintf (dump_file
, " (%04d)\n",
3399 get_expr_value_id (expr
));
3401 if (insert_into_preds_of_block (block
,
3402 get_expression_id (expr
),
3407 /* If all edges produce the same value and that value is
3408 an invariant, then the PHI has the same value on all
3409 edges. Note this. */
3410 else if (!cant_insert
3412 && (edoubleprime
->kind
!= NAME
3413 || !SSA_NAME_OCCURS_IN_ABNORMAL_PHI
3414 (PRE_EXPR_NAME (edoubleprime
))))
3416 gcc_assert (edoubleprime
->kind
== CONSTANT
3417 || edoubleprime
->kind
== NAME
);
3419 tree temp
= make_temp_ssa_name (get_expr_type (expr
),
3422 = gimple_build_assign (temp
,
3423 edoubleprime
->kind
== CONSTANT
?
3424 PRE_EXPR_CONSTANT (edoubleprime
) :
3425 PRE_EXPR_NAME (edoubleprime
));
3426 gimple_stmt_iterator gsi
= gsi_after_labels (block
);
3427 gsi_insert_before (&gsi
, assign
, GSI_NEW_STMT
);
3429 vn_ssa_aux_t vn_info
= VN_INFO (temp
);
3430 vn_info
->value_id
= val
;
3431 vn_info
->valnum
= vn_valnum_from_value_id (val
);
3432 if (vn_info
->valnum
== NULL_TREE
)
3433 vn_info
->valnum
= temp
;
3434 bitmap_set_bit (inserted_exprs
, SSA_NAME_VERSION (temp
));
3435 pre_expr newe
= get_or_alloc_expr_for_name (temp
);
3436 add_to_value (val
, newe
);
3437 bitmap_value_replace_in_set (AVAIL_OUT (block
), newe
);
3438 bitmap_insert_into_set (NEW_SETS (block
), newe
);
3439 bitmap_insert_into_set (PHI_GEN (block
), newe
);
3448 /* Perform insertion for partially anticipatable expressions. There
3449 is only one case we will perform insertion for these. This case is
3450 if the expression is partially anticipatable, and fully available.
3451 In this case, we know that putting it earlier will enable us to
3452 remove the later computation. */
3455 do_pre_partial_partial_insertion (basic_block block
, basic_block dom
,
3456 vec
<pre_expr
> exprs
)
3458 bool new_stuff
= false;
3460 auto_vec
<pre_expr
, 2> avail
;
3463 avail
.safe_grow (EDGE_COUNT (block
->preds
), true);
3465 FOR_EACH_VEC_ELT (exprs
, i
, expr
)
3467 if (expr
->kind
== NARY
3468 || expr
->kind
== REFERENCE
)
3472 bool cant_insert
= false;
3475 pre_expr eprime
= NULL
;
3478 val
= get_expr_value_id (expr
);
3479 if (bitmap_set_contains_value (PHI_GEN (block
), val
))
3481 if (bitmap_set_contains_value (AVAIL_OUT (dom
), val
))
3484 FOR_EACH_EDGE (pred
, ei
, block
->preds
)
3486 unsigned int vprime
;
3487 pre_expr edoubleprime
;
3489 /* We should never run insertion for the exit block
3490 and so not come across fake pred edges. */
3491 gcc_assert (!(pred
->flags
& EDGE_FAKE
));
3493 eprime
= phi_translate (NULL
, expr
, ANTIC_IN (block
),
3494 PA_IN (block
), pred
);
3496 /* eprime will generally only be NULL if the
3497 value of the expression, translated
3498 through the PHI for this predecessor, is
3499 undefined. If that is the case, we can't
3500 make the expression fully redundant,
3501 because its value is undefined along a
3502 predecessor path. We can thus break out
3503 early because it doesn't matter what the
3504 rest of the results are. */
3507 avail
[pred
->dest_idx
] = NULL
;
3512 vprime
= get_expr_value_id (eprime
);
3513 edoubleprime
= bitmap_find_leader (AVAIL_OUT (bprime
), vprime
);
3514 avail
[pred
->dest_idx
] = edoubleprime
;
3515 if (edoubleprime
== NULL
)
3522 /* If we can insert it, it's not the same value
3523 already existing along every predecessor, and
3524 it's defined by some predecessor, it is
3525 partially redundant. */
3526 if (!cant_insert
&& by_all
)
3529 bool do_insertion
= false;
3531 /* Insert only if we can remove a later expression on a path
3532 that we want to optimize for speed.
3533 The phi node that we will be inserting in BLOCK is not free,
3534 and inserting it for the sake of !optimize_for_speed successor
3535 may cause regressions on the speed path. */
3536 FOR_EACH_EDGE (succ
, ei
, block
->succs
)
3538 if (bitmap_set_contains_value (PA_IN (succ
->dest
), val
)
3539 || bitmap_set_contains_value (ANTIC_IN (succ
->dest
), val
))
3541 if (optimize_edge_for_speed_p (succ
))
3542 do_insertion
= true;
3548 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3550 fprintf (dump_file
, "Skipping partial partial redundancy "
3552 print_pre_expr (dump_file
, expr
);
3553 fprintf (dump_file
, " (%04d), not (partially) anticipated "
3554 "on any to be optimized for speed edges\n", val
);
3557 else if (dbg_cnt (treepre_insert
))
3559 pre_stats
.pa_insert
++;
3560 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3562 fprintf (dump_file
, "Found partial partial redundancy "
3564 print_pre_expr (dump_file
, expr
);
3565 fprintf (dump_file
, " (%04d)\n",
3566 get_expr_value_id (expr
));
3568 if (insert_into_preds_of_block (block
,
3569 get_expression_id (expr
),
3580 /* Insert expressions in BLOCK to compute hoistable values up.
3581 Return TRUE if something was inserted, otherwise return FALSE.
3582 The caller has to make sure that BLOCK has at least two successors. */
3585 do_hoist_insertion (basic_block block
)
3589 bool new_stuff
= false;
3591 gimple_stmt_iterator last
;
3593 /* At least two successors, or else... */
3594 gcc_assert (EDGE_COUNT (block
->succs
) >= 2);
3596 /* Check that all successors of BLOCK are dominated by block.
3597 We could use dominated_by_p() for this, but actually there is a much
3598 quicker check: any successor that is dominated by BLOCK can't have
3599 more than one predecessor edge. */
3600 FOR_EACH_EDGE (e
, ei
, block
->succs
)
3601 if (! single_pred_p (e
->dest
))
3604 /* Determine the insertion point. If we cannot safely insert before
3605 the last stmt if we'd have to, bail out. */
3606 last
= gsi_last_bb (block
);
3607 if (!gsi_end_p (last
)
3608 && !is_ctrl_stmt (gsi_stmt (last
))
3609 && stmt_ends_bb_p (gsi_stmt (last
)))
3612 /* Compute the set of hoistable expressions from ANTIC_IN. First compute
3613 hoistable values. */
3614 bitmap_set hoistable_set
;
3616 /* A hoistable value must be in ANTIC_IN(block)
3617 but not in AVAIL_OUT(BLOCK). */
3618 bitmap_initialize (&hoistable_set
.values
, &grand_bitmap_obstack
);
3619 bitmap_and_compl (&hoistable_set
.values
,
3620 &ANTIC_IN (block
)->values
, &AVAIL_OUT (block
)->values
);
3622 /* Short-cut for a common case: hoistable_set is empty. */
3623 if (bitmap_empty_p (&hoistable_set
.values
))
3626 /* Compute which of the hoistable values is in AVAIL_OUT of
3627 at least one of the successors of BLOCK. */
3628 bitmap_head availout_in_some
;
3629 bitmap_initialize (&availout_in_some
, &grand_bitmap_obstack
);
3630 FOR_EACH_EDGE (e
, ei
, block
->succs
)
3631 /* Do not consider expressions solely because their availability
3632 on loop exits. They'd be ANTIC-IN throughout the whole loop
3633 and thus effectively hoisted across loops by combination of
3634 PRE and hoisting. */
3635 if (! loop_exit_edge_p (block
->loop_father
, e
))
3636 bitmap_ior_and_into (&availout_in_some
, &hoistable_set
.values
,
3637 &AVAIL_OUT (e
->dest
)->values
);
3638 bitmap_clear (&hoistable_set
.values
);
3640 /* Short-cut for a common case: availout_in_some is empty. */
3641 if (bitmap_empty_p (&availout_in_some
))
3644 /* Hack hoitable_set in-place so we can use sorted_array_from_bitmap_set. */
3645 bitmap_move (&hoistable_set
.values
, &availout_in_some
);
3646 hoistable_set
.expressions
= ANTIC_IN (block
)->expressions
;
3648 /* Now finally construct the topological-ordered expression set. */
3649 vec
<pre_expr
> exprs
= sorted_array_from_bitmap_set (&hoistable_set
);
3651 bitmap_clear (&hoistable_set
.values
);
3653 /* If there are candidate values for hoisting, insert expressions
3654 strategically to make the hoistable expressions fully redundant. */
3656 FOR_EACH_VEC_ELT (exprs
, i
, expr
)
3658 /* While we try to sort expressions topologically above the
3659 sorting doesn't work out perfectly. Catch expressions we
3660 already inserted. */
3661 unsigned int value_id
= get_expr_value_id (expr
);
3662 if (bitmap_set_contains_value (AVAIL_OUT (block
), value_id
))
3664 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3667 "Already inserted expression for ");
3668 print_pre_expr (dump_file
, expr
);
3669 fprintf (dump_file
, " (%04d)\n", value_id
);
3674 /* If we end up with a punned expression representation and this
3675 happens to be a float typed one give up - we can't know for
3676 sure whether all paths perform the floating-point load we are
3677 about to insert and on some targets this can cause correctness
3678 issues. See PR88240. */
3679 if (expr
->kind
== REFERENCE
3680 && PRE_EXPR_REFERENCE (expr
)->punned
3681 && FLOAT_TYPE_P (get_expr_type (expr
)))
3684 /* OK, we should hoist this value. Perform the transformation. */
3685 pre_stats
.hoist_insert
++;
3686 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3689 "Inserting expression in block %d for code hoisting: ",
3691 print_pre_expr (dump_file
, expr
);
3692 fprintf (dump_file
, " (%04d)\n", value_id
);
3695 gimple_seq stmts
= NULL
;
3696 tree res
= create_expression_by_pieces (block
, expr
, &stmts
,
3697 get_expr_type (expr
));
3699 /* Do not return true if expression creation ultimately
3700 did not insert any statements. */
3701 if (gimple_seq_empty_p (stmts
))
3705 if (gsi_end_p (last
) || is_ctrl_stmt (gsi_stmt (last
)))
3706 gsi_insert_seq_before (&last
, stmts
, GSI_SAME_STMT
);
3708 gsi_insert_seq_after (&last
, stmts
, GSI_NEW_STMT
);
3711 /* Make sure to not return true if expression creation ultimately
3712 failed but also make sure to insert any stmts produced as they
3713 are tracked in inserted_exprs. */
3725 /* Perform insertion of partially redundant and hoistable values. */
3732 FOR_ALL_BB_FN (bb
, cfun
)
3733 NEW_SETS (bb
) = bitmap_set_new ();
3735 int *rpo
= XNEWVEC (int, n_basic_blocks_for_fn (cfun
));
3736 int *bb_rpo
= XNEWVEC (int, last_basic_block_for_fn (cfun
) + 1);
3737 int rpo_num
= pre_and_rev_post_order_compute (NULL
, rpo
, false);
3738 for (int i
= 0; i
< rpo_num
; ++i
)
3741 int num_iterations
= 0;
3746 if (dump_file
&& dump_flags
& TDF_DETAILS
)
3747 fprintf (dump_file
, "Starting insert iteration %d\n", num_iterations
);
3750 for (int idx
= 0; idx
< rpo_num
; ++idx
)
3752 basic_block block
= BASIC_BLOCK_FOR_FN (cfun
, rpo
[idx
]);
3753 basic_block dom
= get_immediate_dominator (CDI_DOMINATORS
, block
);
3758 bitmap_set_t newset
;
3760 /* First, update the AVAIL_OUT set with anything we may have
3761 inserted higher up in the dominator tree. */
3762 newset
= NEW_SETS (dom
);
3764 /* Note that we need to value_replace both NEW_SETS, and
3765 AVAIL_OUT. For both the case of NEW_SETS, the value may be
3766 represented by some non-simple expression here that we want
3767 to replace it with. */
3768 bool avail_out_changed
= false;
3769 FOR_EACH_EXPR_ID_IN_SET (newset
, i
, bi
)
3771 pre_expr expr
= expression_for_id (i
);
3772 bitmap_value_replace_in_set (NEW_SETS (block
), expr
);
3774 |= bitmap_value_replace_in_set (AVAIL_OUT (block
), expr
);
3776 /* We need to iterate if AVAIL_OUT of an already processed
3777 block source changed. */
3778 if (avail_out_changed
&& !changed
)
3782 FOR_EACH_EDGE (e
, ei
, block
->succs
)
3783 if (e
->dest
->index
!= EXIT_BLOCK
3784 && bb_rpo
[e
->dest
->index
] < idx
)
3788 /* Insert expressions for partial redundancies. */
3789 if (flag_tree_pre
&& !single_pred_p (block
))
3792 = sorted_array_from_bitmap_set (ANTIC_IN (block
));
3793 /* Sorting is not perfect, iterate locally. */
3794 while (do_pre_regular_insertion (block
, dom
, exprs
))
3797 if (do_partial_partial
)
3799 exprs
= sorted_array_from_bitmap_set (PA_IN (block
));
3800 while (do_pre_partial_partial_insertion (block
, dom
,
3809 /* Clear the NEW sets before the next iteration. We have already
3810 fully propagated its contents. */
3812 FOR_ALL_BB_FN (bb
, cfun
)
3813 bitmap_set_free (NEW_SETS (bb
));
3817 statistics_histogram_event (cfun
, "insert iterations", num_iterations
);
3819 /* AVAIL_OUT is not needed after insertion so we don't have to
3820 propagate NEW_SETS from hoist insertion. */
3821 FOR_ALL_BB_FN (bb
, cfun
)
3823 bitmap_set_free (NEW_SETS (bb
));
3824 bitmap_set_pool
.remove (NEW_SETS (bb
));
3825 NEW_SETS (bb
) = NULL
;
3828 /* Insert expressions for hoisting. Do a backward walk here since
3829 inserting into BLOCK exposes new opportunities in its predecessors.
3830 Since PRE and hoist insertions can cause back-to-back iteration
3831 and we are interested in PRE insertion exposed hoisting opportunities
3832 but not in hoisting exposed PRE ones do hoist insertion only after
3833 PRE insertion iteration finished and do not iterate it. */
3834 if (flag_code_hoisting
)
3835 for (int idx
= rpo_num
- 1; idx
>= 0; --idx
)
3837 basic_block block
= BASIC_BLOCK_FOR_FN (cfun
, rpo
[idx
]);
3838 if (EDGE_COUNT (block
->succs
) >= 2)
3839 changed
|= do_hoist_insertion (block
);
3847 /* Compute the AVAIL set for all basic blocks.
3849 This function performs value numbering of the statements in each basic
3850 block. The AVAIL sets are built from information we glean while doing
3851 this value numbering, since the AVAIL sets contain only one entry per
3854 AVAIL_IN[BLOCK] = AVAIL_OUT[dom(BLOCK)].
3855 AVAIL_OUT[BLOCK] = AVAIL_IN[BLOCK] U PHI_GEN[BLOCK] U TMP_GEN[BLOCK]. */
3858 compute_avail (function
*fun
)
3861 basic_block block
, son
;
3862 basic_block
*worklist
;
3867 /* We pretend that default definitions are defined in the entry block.
3868 This includes function arguments and the static chain decl. */
3869 FOR_EACH_SSA_NAME (i
, name
, fun
)
3872 if (!SSA_NAME_IS_DEFAULT_DEF (name
)
3873 || has_zero_uses (name
)
3874 || virtual_operand_p (name
))
3877 e
= get_or_alloc_expr_for_name (name
);
3878 add_to_value (get_expr_value_id (e
), e
);
3879 bitmap_insert_into_set (TMP_GEN (ENTRY_BLOCK_PTR_FOR_FN (fun
)), e
);
3880 bitmap_value_insert_into_set (AVAIL_OUT (ENTRY_BLOCK_PTR_FOR_FN (fun
)),
3884 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3886 print_bitmap_set (dump_file
, TMP_GEN (ENTRY_BLOCK_PTR_FOR_FN (fun
)),
3887 "tmp_gen", ENTRY_BLOCK
);
3888 print_bitmap_set (dump_file
, AVAIL_OUT (ENTRY_BLOCK_PTR_FOR_FN (fun
)),
3889 "avail_out", ENTRY_BLOCK
);
3892 /* Allocate the worklist. */
3893 worklist
= XNEWVEC (basic_block
, n_basic_blocks_for_fn (fun
));
3895 /* Seed the algorithm by putting the dominator children of the entry
3896 block on the worklist. */
3897 for (son
= first_dom_son (CDI_DOMINATORS
, ENTRY_BLOCK_PTR_FOR_FN (fun
));
3899 son
= next_dom_son (CDI_DOMINATORS
, son
))
3900 worklist
[sp
++] = son
;
3902 BB_LIVE_VOP_ON_EXIT (ENTRY_BLOCK_PTR_FOR_FN (fun
))
3903 = ssa_default_def (fun
, gimple_vop (fun
));
3905 /* Loop until the worklist is empty. */
3911 /* Pick a block from the worklist. */
3912 block
= worklist
[--sp
];
3913 vn_context_bb
= block
;
3915 /* Initially, the set of available values in BLOCK is that of
3916 its immediate dominator. */
3917 dom
= get_immediate_dominator (CDI_DOMINATORS
, block
);
3920 bitmap_set_copy (AVAIL_OUT (block
), AVAIL_OUT (dom
));
3921 BB_LIVE_VOP_ON_EXIT (block
) = BB_LIVE_VOP_ON_EXIT (dom
);
3924 /* Generate values for PHI nodes. */
3925 for (gphi_iterator gsi
= gsi_start_phis (block
); !gsi_end_p (gsi
);
3928 tree result
= gimple_phi_result (gsi
.phi ());
3930 /* We have no need for virtual phis, as they don't represent
3931 actual computations. */
3932 if (virtual_operand_p (result
))
3934 BB_LIVE_VOP_ON_EXIT (block
) = result
;
3938 pre_expr e
= get_or_alloc_expr_for_name (result
);
3939 add_to_value (get_expr_value_id (e
), e
);
3940 bitmap_value_insert_into_set (AVAIL_OUT (block
), e
);
3941 bitmap_insert_into_set (PHI_GEN (block
), e
);
3944 BB_MAY_NOTRETURN (block
) = 0;
3946 /* Now compute value numbers and populate value sets with all
3947 the expressions computed in BLOCK. */
3948 bool set_bb_may_notreturn
= false;
3949 for (gimple_stmt_iterator gsi
= gsi_start_bb (block
); !gsi_end_p (gsi
);
3955 stmt
= gsi_stmt (gsi
);
3957 if (set_bb_may_notreturn
)
3959 BB_MAY_NOTRETURN (block
) = 1;
3960 set_bb_may_notreturn
= false;
3963 /* Cache whether the basic-block has any non-visible side-effect
3965 If this isn't a call or it is the last stmt in the
3966 basic-block then the CFG represents things correctly. */
3967 if (is_gimple_call (stmt
) && !stmt_ends_bb_p (stmt
))
3969 /* Non-looping const functions always return normally.
3970 Otherwise the call might not return or have side-effects
3971 that forbids hoisting possibly trapping expressions
3973 int flags
= gimple_call_flags (stmt
);
3974 if (!(flags
& (ECF_CONST
|ECF_PURE
))
3975 || (flags
& ECF_LOOPING_CONST_OR_PURE
)
3976 || stmt_can_throw_external (fun
, stmt
))
3977 /* Defer setting of BB_MAY_NOTRETURN to avoid it
3978 influencing the processing of the call itself. */
3979 set_bb_may_notreturn
= true;
3982 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, iter
, SSA_OP_DEF
)
3984 pre_expr e
= get_or_alloc_expr_for_name (op
);
3986 add_to_value (get_expr_value_id (e
), e
);
3987 bitmap_insert_into_set (TMP_GEN (block
), e
);
3988 bitmap_value_insert_into_set (AVAIL_OUT (block
), e
);
3991 if (gimple_vdef (stmt
))
3992 BB_LIVE_VOP_ON_EXIT (block
) = gimple_vdef (stmt
);
3994 if (gimple_has_side_effects (stmt
)
3995 || stmt_could_throw_p (fun
, stmt
)
3996 || is_gimple_debug (stmt
))
3999 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, iter
, SSA_OP_USE
)
4001 if (ssa_undefined_value_p (op
))
4003 pre_expr e
= get_or_alloc_expr_for_name (op
);
4004 bitmap_value_insert_into_set (EXP_GEN (block
), e
);
4007 switch (gimple_code (stmt
))
4015 vn_reference_s ref1
;
4016 pre_expr result
= NULL
;
4018 vn_reference_lookup_call (as_a
<gcall
*> (stmt
), &ref
, &ref1
);
4019 /* There is no point to PRE a call without a value. */
4020 if (!ref
|| !ref
->result
)
4023 /* If the value of the call is not invalidated in
4024 this block until it is computed, add the expression
4026 if ((!gimple_vuse (stmt
)
4028 (SSA_NAME_DEF_STMT (gimple_vuse (stmt
))) == GIMPLE_PHI
4029 || gimple_bb (SSA_NAME_DEF_STMT
4030 (gimple_vuse (stmt
))) != block
)
4031 /* If the REFERENCE traps and there was a preceding
4032 point in the block that might not return avoid
4033 adding the reference to EXP_GEN. */
4034 && (!BB_MAY_NOTRETURN (block
)
4035 || !vn_reference_may_trap (ref
)))
4037 result
= get_or_alloc_expr_for_reference
4038 (ref
, gimple_location (stmt
));
4039 add_to_value (get_expr_value_id (result
), result
);
4040 bitmap_value_insert_into_set (EXP_GEN (block
), result
);
4047 pre_expr result
= NULL
;
4048 switch (vn_get_stmt_kind (stmt
))
4052 enum tree_code code
= gimple_assign_rhs_code (stmt
);
4055 /* COND_EXPR is awkward in that it contains an
4056 embedded complex expression.
4057 Don't even try to shove it through PRE. */
4058 if (code
== COND_EXPR
)
4061 vn_nary_op_lookup_stmt (stmt
, &nary
);
4062 if (!nary
|| nary
->predicated_values
)
4065 /* If the NARY traps and there was a preceding
4066 point in the block that might not return avoid
4067 adding the nary to EXP_GEN. */
4068 if (BB_MAY_NOTRETURN (block
)
4069 && vn_nary_may_trap (nary
))
4072 result
= get_or_alloc_expr_for_nary
4073 (nary
, gimple_location (stmt
));
4079 tree rhs1
= gimple_assign_rhs1 (stmt
);
4081 ao_ref_init (&rhs1_ref
, rhs1
);
4082 alias_set_type set
= ao_ref_alias_set (&rhs1_ref
);
4083 alias_set_type base_set
4084 = ao_ref_base_alias_set (&rhs1_ref
);
4085 vec
<vn_reference_op_s
> operands
4086 = vn_reference_operands_for_lookup (rhs1
);
4088 vn_reference_lookup_pieces (gimple_vuse (stmt
), set
,
4089 base_set
, TREE_TYPE (rhs1
),
4090 operands
, &ref
, VN_WALK
);
4093 operands
.release ();
4097 /* If the REFERENCE traps and there was a preceding
4098 point in the block that might not return avoid
4099 adding the reference to EXP_GEN. */
4100 if (BB_MAY_NOTRETURN (block
)
4101 && vn_reference_may_trap (ref
))
4103 operands
.release ();
4107 /* If the value of the reference is not invalidated in
4108 this block until it is computed, add the expression
4110 if (gimple_vuse (stmt
))
4114 def_stmt
= SSA_NAME_DEF_STMT (gimple_vuse (stmt
));
4115 while (!gimple_nop_p (def_stmt
)
4116 && gimple_code (def_stmt
) != GIMPLE_PHI
4117 && gimple_bb (def_stmt
) == block
)
4119 if (stmt_may_clobber_ref_p
4120 (def_stmt
, gimple_assign_rhs1 (stmt
)))
4126 = SSA_NAME_DEF_STMT (gimple_vuse (def_stmt
));
4130 operands
.release ();
4135 /* If the load was value-numbered to another
4136 load make sure we do not use its expression
4137 for insertion if it wouldn't be a valid
4139 /* At the momemt we have a testcase
4140 for hoist insertion of aligned vs. misaligned
4141 variants in gcc.dg/torture/pr65270-1.c thus
4142 with just alignment to be considered we can
4143 simply replace the expression in the hashtable
4144 with the most conservative one. */
4145 vn_reference_op_t ref1
= &ref
->operands
.last ();
4146 while (ref1
->opcode
!= TARGET_MEM_REF
4147 && ref1
->opcode
!= MEM_REF
4148 && ref1
!= &ref
->operands
[0])
4150 vn_reference_op_t ref2
= &operands
.last ();
4151 while (ref2
->opcode
!= TARGET_MEM_REF
4152 && ref2
->opcode
!= MEM_REF
4153 && ref2
!= &operands
[0])
4155 if ((ref1
->opcode
== TARGET_MEM_REF
4156 || ref1
->opcode
== MEM_REF
)
4157 && (TYPE_ALIGN (ref1
->type
)
4158 > TYPE_ALIGN (ref2
->type
)))
4160 = build_aligned_type (ref1
->type
,
4161 TYPE_ALIGN (ref2
->type
));
4162 /* TBAA behavior is an obvious part so make sure
4163 that the hashtable one covers this as well
4164 by adjusting the ref alias set and its base. */
4166 || alias_set_subset_of (set
, ref
->set
))
4168 else if (ref1
->opcode
!= ref2
->opcode
4169 || (ref1
->opcode
!= MEM_REF
4170 && ref1
->opcode
!= TARGET_MEM_REF
))
4172 /* With mismatching base opcodes or bases
4173 other than MEM_REF or TARGET_MEM_REF we
4174 can't do any easy TBAA adjustment. */
4175 operands
.release ();
4178 else if (alias_set_subset_of (ref
->set
, set
))
4181 if (ref1
->opcode
== MEM_REF
)
4183 = wide_int_to_tree (TREE_TYPE (ref2
->op0
),
4184 wi::to_wide (ref1
->op0
));
4187 = wide_int_to_tree (TREE_TYPE (ref2
->op2
),
4188 wi::to_wide (ref1
->op2
));
4193 if (ref1
->opcode
== MEM_REF
)
4195 = wide_int_to_tree (ptr_type_node
,
4196 wi::to_wide (ref1
->op0
));
4199 = wide_int_to_tree (ptr_type_node
,
4200 wi::to_wide (ref1
->op2
));
4202 operands
.release ();
4204 result
= get_or_alloc_expr_for_reference
4205 (ref
, gimple_location (stmt
));
4213 add_to_value (get_expr_value_id (result
), result
);
4214 bitmap_value_insert_into_set (EXP_GEN (block
), result
);
4221 if (set_bb_may_notreturn
)
4223 BB_MAY_NOTRETURN (block
) = 1;
4224 set_bb_may_notreturn
= false;
4227 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4229 print_bitmap_set (dump_file
, EXP_GEN (block
),
4230 "exp_gen", block
->index
);
4231 print_bitmap_set (dump_file
, PHI_GEN (block
),
4232 "phi_gen", block
->index
);
4233 print_bitmap_set (dump_file
, TMP_GEN (block
),
4234 "tmp_gen", block
->index
);
4235 print_bitmap_set (dump_file
, AVAIL_OUT (block
),
4236 "avail_out", block
->index
);
4239 /* Put the dominator children of BLOCK on the worklist of blocks
4240 to compute available sets for. */
4241 for (son
= first_dom_son (CDI_DOMINATORS
, block
);
4243 son
= next_dom_son (CDI_DOMINATORS
, son
))
4244 worklist
[sp
++] = son
;
4246 vn_context_bb
= NULL
;
4252 /* Initialize data structures used by PRE. */
4259 next_expression_id
= 1;
4260 expressions
.create (0);
4261 expressions
.safe_push (NULL
);
4262 value_expressions
.create (get_max_value_id () + 1);
4263 value_expressions
.quick_grow_cleared (get_max_value_id () + 1);
4264 constant_value_expressions
.create (get_max_constant_value_id () + 1);
4265 constant_value_expressions
.quick_grow_cleared (get_max_constant_value_id () + 1);
4266 name_to_id
.create (0);
4268 inserted_exprs
= BITMAP_ALLOC (NULL
);
4270 connect_infinite_loops_to_exit ();
4271 memset (&pre_stats
, 0, sizeof (pre_stats
));
4273 alloc_aux_for_blocks (sizeof (struct bb_bitmap_sets
));
4275 calculate_dominance_info (CDI_DOMINATORS
);
4277 bitmap_obstack_initialize (&grand_bitmap_obstack
);
4278 expression_to_id
= new hash_table
<pre_expr_d
> (num_ssa_names
* 3);
4279 FOR_ALL_BB_FN (bb
, cfun
)
4281 EXP_GEN (bb
) = bitmap_set_new ();
4282 PHI_GEN (bb
) = bitmap_set_new ();
4283 TMP_GEN (bb
) = bitmap_set_new ();
4284 AVAIL_OUT (bb
) = bitmap_set_new ();
4285 PHI_TRANS_TABLE (bb
) = NULL
;
4290 /* Deallocate data structures used by PRE. */
4295 value_expressions
.release ();
4296 constant_value_expressions
.release ();
4297 expressions
.release ();
4298 BITMAP_FREE (inserted_exprs
);
4299 bitmap_obstack_release (&grand_bitmap_obstack
);
4300 bitmap_set_pool
.release ();
4301 pre_expr_pool
.release ();
4302 delete expression_to_id
;
4303 expression_to_id
= NULL
;
4304 name_to_id
.release ();
4307 FOR_ALL_BB_FN (bb
, cfun
)
4308 if (bb
->aux
&& PHI_TRANS_TABLE (bb
))
4309 delete PHI_TRANS_TABLE (bb
);
4310 free_aux_for_blocks ();
4315 const pass_data pass_data_pre
=
4317 GIMPLE_PASS
, /* type */
4319 OPTGROUP_NONE
, /* optinfo_flags */
4320 TV_TREE_PRE
, /* tv_id */
4321 ( PROP_cfg
| PROP_ssa
), /* properties_required */
4322 0, /* properties_provided */
4323 0, /* properties_destroyed */
4324 TODO_rebuild_alias
, /* todo_flags_start */
4325 0, /* todo_flags_finish */
4328 class pass_pre
: public gimple_opt_pass
4331 pass_pre (gcc::context
*ctxt
)
4332 : gimple_opt_pass (pass_data_pre
, ctxt
)
4335 /* opt_pass methods: */
4336 virtual bool gate (function
*)
4337 { return flag_tree_pre
!= 0 || flag_code_hoisting
!= 0; }
4338 virtual unsigned int execute (function
*);
4340 }; // class pass_pre
4342 /* Valueization hook for RPO VN when we are calling back to it
4343 at ANTIC compute time. */
4346 pre_valueize (tree name
)
4348 if (TREE_CODE (name
) == SSA_NAME
)
4350 tree tem
= VN_INFO (name
)->valnum
;
4351 if (tem
!= VN_TOP
&& tem
!= name
)
4353 if (TREE_CODE (tem
) != SSA_NAME
4354 || SSA_NAME_IS_DEFAULT_DEF (tem
))
4356 /* We create temporary SSA names for representatives that
4357 do not have a definition (yet) but are not default defs either
4358 assume they are fine to use. */
4359 basic_block def_bb
= gimple_bb (SSA_NAME_DEF_STMT (tem
));
4361 || dominated_by_p (CDI_DOMINATORS
, vn_context_bb
, def_bb
))
4363 /* ??? Now we could look for a leader. Ideally we'd somehow
4364 expose RPO VN leaders and get rid of AVAIL_OUT as well... */
4371 pass_pre::execute (function
*fun
)
4373 unsigned int todo
= 0;
4375 do_partial_partial
=
4376 flag_tree_partial_pre
&& optimize_function_for_speed_p (fun
);
4378 /* This has to happen before VN runs because
4379 loop_optimizer_init may create new phis, etc. */
4380 loop_optimizer_init (LOOPS_NORMAL
);
4381 split_edges_for_insertion ();
4383 calculate_dominance_info (CDI_DOMINATORS
);
4385 run_rpo_vn (VN_WALK
);
4389 vn_valueize
= pre_valueize
;
4391 /* Insert can get quite slow on an incredibly large number of basic
4392 blocks due to some quadratic behavior. Until this behavior is
4393 fixed, don't run it when he have an incredibly large number of
4394 bb's. If we aren't going to run insert, there is no point in
4395 computing ANTIC, either, even though it's plenty fast nor do
4396 we require AVAIL. */
4397 if (n_basic_blocks_for_fn (fun
) < 4000)
4399 compute_avail (fun
);
4404 /* Make sure to remove fake edges before committing our inserts.
4405 This makes sure we don't end up with extra critical edges that
4406 we would need to split. */
4407 remove_fake_exit_edges ();
4408 gsi_commit_edge_inserts ();
4410 /* Eliminate folds statements which might (should not...) end up
4411 not keeping virtual operands up-to-date. */
4412 gcc_assert (!need_ssa_update_p (fun
));
4414 statistics_counter_event (fun
, "Insertions", pre_stats
.insertions
);
4415 statistics_counter_event (fun
, "PA inserted", pre_stats
.pa_insert
);
4416 statistics_counter_event (fun
, "HOIST inserted", pre_stats
.hoist_insert
);
4417 statistics_counter_event (fun
, "New PHIs", pre_stats
.phis
);
4419 todo
|= eliminate_with_rpo_vn (inserted_exprs
);
4423 /* Because we don't follow exactly the standard PRE algorithm, and decide not
4424 to insert PHI nodes sometimes, and because value numbering of casts isn't
4425 perfect, we sometimes end up inserting dead code. This simple DCE-like
4426 pass removes any insertions we made that weren't actually used. */
4427 simple_dce_from_worklist (inserted_exprs
);
4432 loop_optimizer_finalize ();
4434 /* TODO: tail_merge_optimize may merge all predecessors of a block, in which
4435 case we can merge the block with the remaining predecessor of the block.
4437 - call merge_blocks after each tail merge iteration
4438 - call merge_blocks after all tail merge iterations
4439 - mark TODO_cleanup_cfg when necessary
4440 - share the cfg cleanup with fini_pre. */
4441 todo
|= tail_merge_optimize (todo
);
4445 /* Tail merging invalidates the virtual SSA web, together with
4446 cfg-cleanup opportunities exposed by PRE this will wreck the
4447 SSA updating machinery. So make sure to run update-ssa
4448 manually, before eventually scheduling cfg-cleanup as part of
4450 update_ssa (TODO_update_ssa_only_virtuals
);
4458 make_pass_pre (gcc::context
*ctxt
)
4460 return new pass_pre (ctxt
);