1 /* Full and partial redundancy elimination and code hoisting on SSA GIMPLE.
2 Copyright (C) 2001-2017 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-ssa-loop.h"
43 #include "tree-into-ssa.h"
47 #include "tree-ssa-sccvn.h"
48 #include "tree-scalar-evolution.h"
52 #include "tree-ssa-propagate.h"
53 #include "ipa-utils.h"
54 #include "tree-cfgcleanup.h"
55 #include "langhooks.h"
58 /* Even though this file is called tree-ssa-pre.c, we actually
59 implement a bit more than just PRE here. All of them piggy-back
60 on GVN which is implemented in tree-ssa-sccvn.c.
62 1. Full Redundancy Elimination (FRE)
63 This is the elimination phase of GVN.
65 2. Partial Redundancy Elimination (PRE)
66 This is adds computation of AVAIL_OUT and ANTIC_IN and
67 doing expression insertion to form GVN-PRE.
70 This optimization uses the ANTIC_IN sets computed for PRE
71 to move expressions further up than PRE would do, to make
72 multiple computations of the same value fully redundant.
73 This pass is explained below (after the explanation of the
74 basic algorithm for PRE).
79 1. Avail sets can be shared by making an avail_find_leader that
80 walks up the dominator tree and looks in those avail sets.
81 This might affect code optimality, it's unclear right now.
82 Currently the AVAIL_OUT sets are the remaining quadraticness in
84 2. Strength reduction can be performed by anticipating expressions
85 we can repair later on.
86 3. We can do back-substitution or smarter value numbering to catch
87 commutative expressions split up over multiple statements.
90 /* For ease of terminology, "expression node" in the below refers to
91 every expression node but GIMPLE_ASSIGN, because GIMPLE_ASSIGNs
92 represent the actual statement containing the expressions we care about,
93 and we cache the value number by putting it in the expression. */
95 /* Basic algorithm for Partial Redundancy Elimination:
97 First we walk the statements to generate the AVAIL sets, the
98 EXP_GEN sets, and the tmp_gen sets. EXP_GEN sets represent the
99 generation of values/expressions by a given block. We use them
100 when computing the ANTIC sets. The AVAIL sets consist of
101 SSA_NAME's that represent values, so we know what values are
102 available in what blocks. AVAIL is a forward dataflow problem. In
103 SSA, values are never killed, so we don't need a kill set, or a
104 fixpoint iteration, in order to calculate the AVAIL sets. In
105 traditional parlance, AVAIL sets tell us the downsafety of the
108 Next, we generate the ANTIC sets. These sets represent the
109 anticipatable expressions. ANTIC is a backwards dataflow
110 problem. An expression is anticipatable in a given block if it could
111 be generated in that block. This means that if we had to perform
112 an insertion in that block, of the value of that expression, we
113 could. Calculating the ANTIC sets requires phi translation of
114 expressions, because the flow goes backwards through phis. We must
115 iterate to a fixpoint of the ANTIC sets, because we have a kill
116 set. Even in SSA form, values are not live over the entire
117 function, only from their definition point onwards. So we have to
118 remove values from the ANTIC set once we go past the definition
119 point of the leaders that make them up.
120 compute_antic/compute_antic_aux performs this computation.
122 Third, we perform insertions to make partially redundant
123 expressions fully redundant.
125 An expression is partially redundant (excluding partial
128 1. It is AVAIL in some, but not all, of the predecessors of a
130 2. It is ANTIC in all the predecessors.
132 In order to make it fully redundant, we insert the expression into
133 the predecessors where it is not available, but is ANTIC.
135 When optimizing for size, we only eliminate the partial redundancy
136 if we need to insert in only one predecessor. This avoids almost
137 completely the code size increase that PRE usually causes.
139 For the partial anticipation case, we only perform insertion if it
140 is partially anticipated in some block, and fully available in all
143 do_pre_regular_insertion/do_pre_partial_partial_insertion
144 performs these steps, driven by insert/insert_aux.
146 Fourth, we eliminate fully redundant expressions.
147 This is a simple statement walk that replaces redundant
148 calculations with the now available values. */
150 /* Basic algorithm for Code Hoisting:
152 Code hoisting is: Moving value computations up in the control flow
153 graph to make multiple copies redundant. Typically this is a size
154 optimization, but there are cases where it also is helpful for speed.
156 A simple code hoisting algorithm is implemented that piggy-backs on
157 the PRE infrastructure. For code hoisting, we have to know ANTIC_OUT
158 which is effectively ANTIC_IN - AVAIL_OUT. The latter two have to be
159 computed for PRE, and we can use them to perform a limited version of
162 For the purpose of this implementation, a value is hoistable to a basic
163 block B if the following properties are met:
165 1. The value is in ANTIC_IN(B) -- the value will be computed on all
166 paths from B to function exit and it can be computed in B);
168 2. The value is not in AVAIL_OUT(B) -- there would be no need to
169 compute the value again and make it available twice;
171 3. All successors of B are dominated by B -- makes sure that inserting
172 a computation of the value in B will make the remaining
173 computations fully redundant;
175 4. At least one successor has the value in AVAIL_OUT -- to avoid
176 hoisting values up too far;
178 5. There are at least two successors of B -- hoisting in straight
179 line code is pointless.
181 The third condition is not strictly necessary, but it would complicate
182 the hoisting pass a lot. In fact, I don't know of any code hoisting
183 algorithm that does not have this requirement. Fortunately, experiments
184 have show that most candidate hoistable values are in regions that meet
185 this condition (e.g. diamond-shape regions).
187 The forth condition is necessary to avoid hoisting things up too far
188 away from the uses of the value. Nothing else limits the algorithm
189 from hoisting everything up as far as ANTIC_IN allows. Experiments
190 with SPEC and CSiBE have shown that hoisting up too far results in more
191 spilling, less benefits for code size, and worse benchmark scores.
192 Fortunately, in practice most of the interesting hoisting opportunities
193 are caught despite this limitation.
195 For hoistable values that meet all conditions, expressions are inserted
196 to make the calculation of the hoistable value fully redundant. We
197 perform code hoisting insertions after each round of PRE insertions,
198 because code hoisting never exposes new PRE opportunities, but PRE can
199 create new code hoisting opportunities.
201 The code hoisting algorithm is implemented in do_hoist_insert, driven
202 by insert/insert_aux. */
204 /* Representations of value numbers:
206 Value numbers are represented by a representative SSA_NAME. We
207 will create fake SSA_NAME's in situations where we need a
208 representative but do not have one (because it is a complex
209 expression). In order to facilitate storing the value numbers in
210 bitmaps, and keep the number of wasted SSA_NAME's down, we also
211 associate a value_id with each value number, and create full blown
212 ssa_name's only where we actually need them (IE in operands of
213 existing expressions).
215 Theoretically you could replace all the value_id's with
216 SSA_NAME_VERSION, but this would allocate a large number of
217 SSA_NAME's (which are each > 30 bytes) just to get a 4 byte number.
218 It would also require an additional indirection at each point we
221 /* Representation of expressions on value numbers:
223 Expressions consisting of value numbers are represented the same
224 way as our VN internally represents them, with an additional
225 "pre_expr" wrapping around them in order to facilitate storing all
226 of the expressions in the same sets. */
228 /* Representation of sets:
230 The dataflow sets do not need to be sorted in any particular order
231 for the majority of their lifetime, are simply represented as two
232 bitmaps, one that keeps track of values present in the set, and one
233 that keeps track of expressions present in the set.
235 When we need them in topological order, we produce it on demand by
236 transforming the bitmap into an array and sorting it into topo
239 /* Type of expression, used to know which member of the PRE_EXPR union
255 vn_reference_t reference
;
258 typedef struct pre_expr_d
: nofree_ptr_hash
<pre_expr_d
>
260 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 /* Free the expression id field in all of our expressions,
407 and then destroy the expressions array. */
410 clear_expression_ids (void)
412 expressions
.release ();
415 static object_allocator
<pre_expr_d
> pre_expr_pool ("pre_expr nodes");
417 /* Given an SSA_NAME NAME, get or create a pre_expr to represent it. */
420 get_or_alloc_expr_for_name (tree name
)
422 struct pre_expr_d expr
;
424 unsigned int result_id
;
428 PRE_EXPR_NAME (&expr
) = name
;
429 result_id
= lookup_expression_id (&expr
);
431 return expression_for_id (result_id
);
433 result
= pre_expr_pool
.allocate ();
435 PRE_EXPR_NAME (result
) = name
;
436 alloc_expression_id (result
);
440 /* An unordered bitmap set. One bitmap tracks values, the other,
442 typedef struct bitmap_set
444 bitmap_head expressions
;
448 #define FOR_EACH_EXPR_ID_IN_SET(set, id, bi) \
449 EXECUTE_IF_SET_IN_BITMAP (&(set)->expressions, 0, (id), (bi))
451 #define FOR_EACH_VALUE_ID_IN_SET(set, id, bi) \
452 EXECUTE_IF_SET_IN_BITMAP (&(set)->values, 0, (id), (bi))
454 /* Mapping from value id to expressions with that value_id. */
455 static vec
<bitmap
> value_expressions
;
457 /* Sets that we need to keep track of. */
458 typedef struct bb_bitmap_sets
460 /* The EXP_GEN set, which represents expressions/values generated in
462 bitmap_set_t exp_gen
;
464 /* The PHI_GEN set, which represents PHI results generated in a
466 bitmap_set_t phi_gen
;
468 /* The TMP_GEN set, which represents results/temporaries generated
469 in a basic block. IE the LHS of an expression. */
470 bitmap_set_t tmp_gen
;
472 /* The AVAIL_OUT set, which represents which values are available in
473 a given basic block. */
474 bitmap_set_t avail_out
;
476 /* The ANTIC_IN set, which represents which values are anticipatable
477 in a given basic block. */
478 bitmap_set_t antic_in
;
480 /* The PA_IN set, which represents which values are
481 partially anticipatable in a given basic block. */
484 /* The NEW_SETS set, which is used during insertion to augment the
485 AVAIL_OUT set of blocks with the new insertions performed during
486 the current iteration. */
487 bitmap_set_t new_sets
;
489 /* A cache for value_dies_in_block_x. */
492 /* The live virtual operand on successor edges. */
495 /* True if we have visited this block during ANTIC calculation. */
496 unsigned int visited
: 1;
498 /* True when the block contains a call that might not return. */
499 unsigned int contains_may_not_return_call
: 1;
502 #define EXP_GEN(BB) ((bb_value_sets_t) ((BB)->aux))->exp_gen
503 #define PHI_GEN(BB) ((bb_value_sets_t) ((BB)->aux))->phi_gen
504 #define TMP_GEN(BB) ((bb_value_sets_t) ((BB)->aux))->tmp_gen
505 #define AVAIL_OUT(BB) ((bb_value_sets_t) ((BB)->aux))->avail_out
506 #define ANTIC_IN(BB) ((bb_value_sets_t) ((BB)->aux))->antic_in
507 #define PA_IN(BB) ((bb_value_sets_t) ((BB)->aux))->pa_in
508 #define NEW_SETS(BB) ((bb_value_sets_t) ((BB)->aux))->new_sets
509 #define EXPR_DIES(BB) ((bb_value_sets_t) ((BB)->aux))->expr_dies
510 #define BB_VISITED(BB) ((bb_value_sets_t) ((BB)->aux))->visited
511 #define BB_MAY_NOTRETURN(BB) ((bb_value_sets_t) ((BB)->aux))->contains_may_not_return_call
512 #define BB_LIVE_VOP_ON_EXIT(BB) ((bb_value_sets_t) ((BB)->aux))->vop_on_exit
515 /* This structure is used to keep track of statistics on what
516 optimization PRE was able to perform. */
519 /* The number of RHS computations eliminated by PRE. */
522 /* The number of new expressions/temporaries generated by PRE. */
525 /* The number of inserts found due to partial anticipation */
528 /* The number of inserts made for code hoisting. */
531 /* The number of new PHI nodes added by PRE. */
535 static bool do_partial_partial
;
536 static pre_expr
bitmap_find_leader (bitmap_set_t
, unsigned int);
537 static void bitmap_value_insert_into_set (bitmap_set_t
, pre_expr
);
538 static void bitmap_value_replace_in_set (bitmap_set_t
, pre_expr
);
539 static void bitmap_set_copy (bitmap_set_t
, bitmap_set_t
);
540 static bool bitmap_set_contains_value (bitmap_set_t
, unsigned int);
541 static void bitmap_insert_into_set (bitmap_set_t
, pre_expr
);
542 static bitmap_set_t
bitmap_set_new (void);
543 static tree
create_expression_by_pieces (basic_block
, pre_expr
, gimple_seq
*,
545 static tree
find_or_generate_expression (basic_block
, tree
, gimple_seq
*);
546 static unsigned int get_expr_value_id (pre_expr
);
548 /* We can add and remove elements and entries to and from sets
549 and hash tables, so we use alloc pools for them. */
551 static object_allocator
<bitmap_set
> bitmap_set_pool ("Bitmap sets");
552 static bitmap_obstack grand_bitmap_obstack
;
554 /* Set of blocks with statements that have had their EH properties changed. */
555 static bitmap need_eh_cleanup
;
557 /* Set of blocks with statements that have had their AB properties changed. */
558 static bitmap need_ab_cleanup
;
560 /* A three tuple {e, pred, v} used to cache phi translations in the
561 phi_translate_table. */
563 typedef struct expr_pred_trans_d
: free_ptr_hash
<expr_pred_trans_d
>
565 /* The expression. */
568 /* The predecessor block along which we translated the expression. */
571 /* The value that resulted from the translation. */
574 /* The hashcode for the expression, pred pair. This is cached for
578 /* hash_table support. */
579 static inline hashval_t
hash (const expr_pred_trans_d
*);
580 static inline int equal (const expr_pred_trans_d
*, const expr_pred_trans_d
*);
581 } *expr_pred_trans_t
;
582 typedef const struct expr_pred_trans_d
*const_expr_pred_trans_t
;
585 expr_pred_trans_d::hash (const expr_pred_trans_d
*e
)
591 expr_pred_trans_d::equal (const expr_pred_trans_d
*ve1
,
592 const expr_pred_trans_d
*ve2
)
594 basic_block b1
= ve1
->pred
;
595 basic_block b2
= ve2
->pred
;
597 /* If they are not translations for the same basic block, they can't
601 return pre_expr_d::equal (ve1
->e
, ve2
->e
);
604 /* The phi_translate_table caches phi translations for a given
605 expression and predecessor. */
606 static hash_table
<expr_pred_trans_d
> *phi_translate_table
;
608 /* Add the tuple mapping from {expression E, basic block PRED} to
609 the phi translation table and return whether it pre-existed. */
612 phi_trans_add (expr_pred_trans_t
*entry
, pre_expr e
, basic_block pred
)
614 expr_pred_trans_t
*slot
;
615 expr_pred_trans_d tem
;
616 hashval_t hash
= iterative_hash_hashval_t (pre_expr_d::hash (e
),
621 slot
= phi_translate_table
->find_slot_with_hash (&tem
, hash
, INSERT
);
628 *entry
= *slot
= XNEW (struct expr_pred_trans_d
);
630 (*entry
)->pred
= pred
;
631 (*entry
)->hashcode
= hash
;
636 /* Add expression E to the expression set of value id V. */
639 add_to_value (unsigned int v
, pre_expr e
)
643 gcc_checking_assert (get_expr_value_id (e
) == v
);
645 if (v
>= value_expressions
.length ())
647 value_expressions
.safe_grow_cleared (v
+ 1);
650 set
= value_expressions
[v
];
653 set
= BITMAP_ALLOC (&grand_bitmap_obstack
);
654 value_expressions
[v
] = set
;
657 bitmap_set_bit (set
, get_or_alloc_expression_id (e
));
660 /* Create a new bitmap set and return it. */
663 bitmap_set_new (void)
665 bitmap_set_t ret
= bitmap_set_pool
.allocate ();
666 bitmap_initialize (&ret
->expressions
, &grand_bitmap_obstack
);
667 bitmap_initialize (&ret
->values
, &grand_bitmap_obstack
);
671 /* Return the value id for a PRE expression EXPR. */
674 get_expr_value_id (pre_expr expr
)
680 id
= get_constant_value_id (PRE_EXPR_CONSTANT (expr
));
683 id
= VN_INFO (PRE_EXPR_NAME (expr
))->value_id
;
686 id
= PRE_EXPR_NARY (expr
)->value_id
;
689 id
= PRE_EXPR_REFERENCE (expr
)->value_id
;
694 /* ??? We cannot assert that expr has a value-id (it can be 0), because
695 we assign value-ids only to expressions that have a result
696 in set_hashtable_value_ids. */
700 /* Return a SCCVN valnum (SSA name or constant) for the PRE value-id VAL. */
703 sccvn_valnum_from_value_id (unsigned int val
)
707 bitmap exprset
= value_expressions
[val
];
708 EXECUTE_IF_SET_IN_BITMAP (exprset
, 0, i
, bi
)
710 pre_expr vexpr
= expression_for_id (i
);
711 if (vexpr
->kind
== NAME
)
712 return VN_INFO (PRE_EXPR_NAME (vexpr
))->valnum
;
713 else if (vexpr
->kind
== CONSTANT
)
714 return PRE_EXPR_CONSTANT (vexpr
);
719 /* Remove an expression EXPR from a bitmapped set. */
722 bitmap_remove_expr_from_set (bitmap_set_t set
, pre_expr expr
)
724 unsigned int val
= get_expr_value_id (expr
);
725 bitmap_clear_bit (&set
->values
, val
);
726 bitmap_clear_bit (&set
->expressions
, get_expression_id (expr
));
729 /* Insert an expression EXPR into a bitmapped set. */
732 bitmap_insert_into_set (bitmap_set_t set
, pre_expr expr
)
734 unsigned int val
= get_expr_value_id (expr
);
735 if (! value_id_constant_p (val
))
737 /* Note this is the only function causing multiple expressions
738 for the same value to appear in a set. This is needed for
739 TMP_GEN, PHI_GEN and NEW_SETs. */
740 bitmap_set_bit (&set
->values
, val
);
741 bitmap_set_bit (&set
->expressions
, get_or_alloc_expression_id (expr
));
745 /* Copy a bitmapped set ORIG, into bitmapped set DEST. */
748 bitmap_set_copy (bitmap_set_t dest
, bitmap_set_t orig
)
750 bitmap_copy (&dest
->expressions
, &orig
->expressions
);
751 bitmap_copy (&dest
->values
, &orig
->values
);
755 /* Free memory used up by SET. */
757 bitmap_set_free (bitmap_set_t set
)
759 bitmap_clear (&set
->expressions
);
760 bitmap_clear (&set
->values
);
764 /* Generate an topological-ordered array of bitmap set SET. */
767 sorted_array_from_bitmap_set (bitmap_set_t set
)
770 bitmap_iterator bi
, bj
;
771 vec
<pre_expr
> result
;
773 /* Pre-allocate enough space for the array. */
774 result
.create (bitmap_count_bits (&set
->expressions
));
776 FOR_EACH_VALUE_ID_IN_SET (set
, i
, bi
)
778 /* The number of expressions having a given value is usually
779 relatively small. Thus, rather than making a vector of all
780 the expressions and sorting it by value-id, we walk the values
781 and check in the reverse mapping that tells us what expressions
782 have a given value, to filter those in our set. As a result,
783 the expressions are inserted in value-id order, which means
786 If this is somehow a significant lose for some cases, we can
787 choose which set to walk based on the set size. */
788 bitmap exprset
= value_expressions
[i
];
789 EXECUTE_IF_SET_IN_BITMAP (exprset
, 0, j
, bj
)
791 if (bitmap_bit_p (&set
->expressions
, j
))
792 result
.quick_push (expression_for_id (j
));
799 /* Subtract all expressions contained in ORIG from DEST. */
802 bitmap_set_subtract_expressions (bitmap_set_t dest
, bitmap_set_t orig
)
804 bitmap_set_t result
= bitmap_set_new ();
808 bitmap_and_compl (&result
->expressions
, &dest
->expressions
,
811 FOR_EACH_EXPR_ID_IN_SET (result
, i
, bi
)
813 pre_expr expr
= expression_for_id (i
);
814 unsigned int value_id
= get_expr_value_id (expr
);
815 bitmap_set_bit (&result
->values
, value_id
);
821 /* Subtract all values in bitmap set B from bitmap set A. */
824 bitmap_set_subtract_values (bitmap_set_t a
, bitmap_set_t b
)
828 pre_expr to_remove
= NULL
;
829 FOR_EACH_EXPR_ID_IN_SET (a
, i
, bi
)
833 bitmap_remove_expr_from_set (a
, to_remove
);
836 pre_expr expr
= expression_for_id (i
);
837 if (bitmap_bit_p (&b
->values
, get_expr_value_id (expr
)))
841 bitmap_remove_expr_from_set (a
, to_remove
);
845 /* Return true if bitmapped set SET contains the value VALUE_ID. */
848 bitmap_set_contains_value (bitmap_set_t set
, unsigned int value_id
)
850 if (value_id_constant_p (value_id
))
853 return bitmap_bit_p (&set
->values
, value_id
);
857 bitmap_set_contains_expr (bitmap_set_t set
, const pre_expr expr
)
859 return bitmap_bit_p (&set
->expressions
, get_expression_id (expr
));
862 /* Return true if two bitmap sets are equal. */
865 bitmap_set_equal (bitmap_set_t a
, bitmap_set_t b
)
867 return bitmap_equal_p (&a
->values
, &b
->values
);
870 /* Replace an instance of EXPR's VALUE with EXPR in SET if it exists,
871 and add it otherwise. */
874 bitmap_value_replace_in_set (bitmap_set_t set
, pre_expr expr
)
876 unsigned int val
= get_expr_value_id (expr
);
877 if (value_id_constant_p (val
))
880 if (bitmap_set_contains_value (set
, val
))
882 /* The number of expressions having a given value is usually
883 significantly less than the total number of expressions in SET.
884 Thus, rather than check, for each expression in SET, whether it
885 has the value LOOKFOR, we walk the reverse mapping that tells us
886 what expressions have a given value, and see if any of those
887 expressions are in our set. For large testcases, this is about
888 5-10x faster than walking the bitmap. If this is somehow a
889 significant lose for some cases, we can choose which set to walk
890 based on the set size. */
893 bitmap exprset
= value_expressions
[val
];
894 EXECUTE_IF_SET_IN_BITMAP (exprset
, 0, i
, bi
)
896 if (bitmap_clear_bit (&set
->expressions
, i
))
898 bitmap_set_bit (&set
->expressions
, get_expression_id (expr
));
905 bitmap_insert_into_set (set
, expr
);
908 /* Insert EXPR into SET if EXPR's value is not already present in
912 bitmap_value_insert_into_set (bitmap_set_t set
, pre_expr expr
)
914 unsigned int val
= get_expr_value_id (expr
);
916 gcc_checking_assert (expr
->id
== get_or_alloc_expression_id (expr
));
918 /* Constant values are always considered to be part of the set. */
919 if (value_id_constant_p (val
))
922 /* If the value membership changed, add the expression. */
923 if (bitmap_set_bit (&set
->values
, val
))
924 bitmap_set_bit (&set
->expressions
, expr
->id
);
927 /* Print out EXPR to outfile. */
930 print_pre_expr (FILE *outfile
, const pre_expr expr
)
934 fprintf (outfile
, "NULL");
940 print_generic_expr (outfile
, PRE_EXPR_CONSTANT (expr
));
943 print_generic_expr (outfile
, PRE_EXPR_NAME (expr
));
948 vn_nary_op_t nary
= PRE_EXPR_NARY (expr
);
949 fprintf (outfile
, "{%s,", get_tree_code_name (nary
->opcode
));
950 for (i
= 0; i
< nary
->length
; i
++)
952 print_generic_expr (outfile
, nary
->op
[i
]);
953 if (i
!= (unsigned) nary
->length
- 1)
954 fprintf (outfile
, ",");
956 fprintf (outfile
, "}");
962 vn_reference_op_t vro
;
964 vn_reference_t ref
= PRE_EXPR_REFERENCE (expr
);
965 fprintf (outfile
, "{");
967 ref
->operands
.iterate (i
, &vro
);
970 bool closebrace
= false;
971 if (vro
->opcode
!= SSA_NAME
972 && TREE_CODE_CLASS (vro
->opcode
) != tcc_declaration
)
974 fprintf (outfile
, "%s", get_tree_code_name (vro
->opcode
));
977 fprintf (outfile
, "<");
983 print_generic_expr (outfile
, vro
->op0
);
986 fprintf (outfile
, ",");
987 print_generic_expr (outfile
, vro
->op1
);
991 fprintf (outfile
, ",");
992 print_generic_expr (outfile
, vro
->op2
);
996 fprintf (outfile
, ">");
997 if (i
!= ref
->operands
.length () - 1)
998 fprintf (outfile
, ",");
1000 fprintf (outfile
, "}");
1003 fprintf (outfile
, "@");
1004 print_generic_expr (outfile
, ref
->vuse
);
1010 void debug_pre_expr (pre_expr
);
1012 /* Like print_pre_expr but always prints to stderr. */
1014 debug_pre_expr (pre_expr e
)
1016 print_pre_expr (stderr
, e
);
1017 fprintf (stderr
, "\n");
1020 /* Print out SET to OUTFILE. */
1023 print_bitmap_set (FILE *outfile
, bitmap_set_t set
,
1024 const char *setname
, int blockindex
)
1026 fprintf (outfile
, "%s[%d] := { ", setname
, blockindex
);
1033 FOR_EACH_EXPR_ID_IN_SET (set
, i
, bi
)
1035 const pre_expr expr
= expression_for_id (i
);
1038 fprintf (outfile
, ", ");
1040 print_pre_expr (outfile
, expr
);
1042 fprintf (outfile
, " (%04d)", get_expr_value_id (expr
));
1045 fprintf (outfile
, " }\n");
1048 void debug_bitmap_set (bitmap_set_t
);
1051 debug_bitmap_set (bitmap_set_t set
)
1053 print_bitmap_set (stderr
, set
, "debug", 0);
1056 void debug_bitmap_sets_for (basic_block
);
1059 debug_bitmap_sets_for (basic_block bb
)
1061 print_bitmap_set (stderr
, AVAIL_OUT (bb
), "avail_out", bb
->index
);
1062 print_bitmap_set (stderr
, EXP_GEN (bb
), "exp_gen", bb
->index
);
1063 print_bitmap_set (stderr
, PHI_GEN (bb
), "phi_gen", bb
->index
);
1064 print_bitmap_set (stderr
, TMP_GEN (bb
), "tmp_gen", bb
->index
);
1065 print_bitmap_set (stderr
, ANTIC_IN (bb
), "antic_in", bb
->index
);
1066 if (do_partial_partial
)
1067 print_bitmap_set (stderr
, PA_IN (bb
), "pa_in", bb
->index
);
1068 print_bitmap_set (stderr
, NEW_SETS (bb
), "new_sets", bb
->index
);
1071 /* Print out the expressions that have VAL to OUTFILE. */
1074 print_value_expressions (FILE *outfile
, unsigned int val
)
1076 bitmap set
= value_expressions
[val
];
1081 sprintf (s
, "%04d", val
);
1082 x
.expressions
= *set
;
1083 print_bitmap_set (outfile
, &x
, s
, 0);
1089 debug_value_expressions (unsigned int val
)
1091 print_value_expressions (stderr
, val
);
1094 /* Given a CONSTANT, allocate a new CONSTANT type PRE_EXPR to
1098 get_or_alloc_expr_for_constant (tree constant
)
1100 unsigned int result_id
;
1101 unsigned int value_id
;
1102 struct pre_expr_d expr
;
1105 expr
.kind
= CONSTANT
;
1106 PRE_EXPR_CONSTANT (&expr
) = constant
;
1107 result_id
= lookup_expression_id (&expr
);
1109 return expression_for_id (result_id
);
1111 newexpr
= pre_expr_pool
.allocate ();
1112 newexpr
->kind
= CONSTANT
;
1113 PRE_EXPR_CONSTANT (newexpr
) = constant
;
1114 alloc_expression_id (newexpr
);
1115 value_id
= get_or_alloc_constant_value_id (constant
);
1116 add_to_value (value_id
, newexpr
);
1120 /* Get or allocate a pre_expr for a piece of GIMPLE, and return it.
1121 Currently only supports constants and SSA_NAMES. */
1123 get_or_alloc_expr_for (tree t
)
1125 if (TREE_CODE (t
) == SSA_NAME
)
1126 return get_or_alloc_expr_for_name (t
);
1127 else if (is_gimple_min_invariant (t
))
1128 return get_or_alloc_expr_for_constant (t
);
1132 /* Return the folded version of T if T, when folded, is a gimple
1133 min_invariant or an SSA name. Otherwise, return T. */
1136 fully_constant_expression (pre_expr e
)
1144 vn_nary_op_t nary
= PRE_EXPR_NARY (e
);
1145 tree res
= vn_nary_simplify (nary
);
1148 if (is_gimple_min_invariant (res
))
1149 return get_or_alloc_expr_for_constant (res
);
1150 if (TREE_CODE (res
) == SSA_NAME
)
1151 return get_or_alloc_expr_for_name (res
);
1156 vn_reference_t ref
= PRE_EXPR_REFERENCE (e
);
1158 if ((folded
= fully_constant_vn_reference_p (ref
)))
1159 return get_or_alloc_expr_for_constant (folded
);
1168 /* Translate the VUSE backwards through phi nodes in PHIBLOCK, so that
1169 it has the value it would have in BLOCK. Set *SAME_VALID to true
1170 in case the new vuse doesn't change the value id of the OPERANDS. */
1173 translate_vuse_through_block (vec
<vn_reference_op_s
> operands
,
1174 alias_set_type set
, tree type
, tree vuse
,
1175 basic_block phiblock
,
1176 basic_block block
, bool *same_valid
)
1178 gimple
*phi
= SSA_NAME_DEF_STMT (vuse
);
1185 if (gimple_bb (phi
) != phiblock
)
1188 use_oracle
= ao_ref_init_from_vn_reference (&ref
, set
, type
, operands
);
1190 /* Use the alias-oracle to find either the PHI node in this block,
1191 the first VUSE used in this block that is equivalent to vuse or
1192 the first VUSE which definition in this block kills the value. */
1193 if (gimple_code (phi
) == GIMPLE_PHI
)
1194 e
= find_edge (block
, phiblock
);
1195 else if (use_oracle
)
1196 while (!stmt_may_clobber_ref_p_1 (phi
, &ref
))
1198 vuse
= gimple_vuse (phi
);
1199 phi
= SSA_NAME_DEF_STMT (vuse
);
1200 if (gimple_bb (phi
) != phiblock
)
1202 if (gimple_code (phi
) == GIMPLE_PHI
)
1204 e
= find_edge (block
, phiblock
);
1215 bitmap visited
= NULL
;
1217 /* Try to find a vuse that dominates this phi node by skipping
1218 non-clobbering statements. */
1219 vuse
= get_continuation_for_phi (phi
, &ref
, &cnt
, &visited
, false,
1222 BITMAP_FREE (visited
);
1228 /* If we didn't find any, the value ID can't stay the same,
1229 but return the translated vuse. */
1230 *same_valid
= false;
1231 vuse
= PHI_ARG_DEF (phi
, e
->dest_idx
);
1233 /* ??? We would like to return vuse here as this is the canonical
1234 upmost vdef that this reference is associated with. But during
1235 insertion of the references into the hash tables we only ever
1236 directly insert with their direct gimple_vuse, hence returning
1237 something else would make us not find the other expression. */
1238 return PHI_ARG_DEF (phi
, e
->dest_idx
);
1244 /* Like bitmap_find_leader, but checks for the value existing in SET1 *or*
1245 SET2 *or* SET3. This is used to avoid making a set consisting of the union
1246 of PA_IN and ANTIC_IN during insert and phi-translation. */
1248 static inline pre_expr
1249 find_leader_in_sets (unsigned int val
, bitmap_set_t set1
, bitmap_set_t set2
,
1250 bitmap_set_t set3
= NULL
)
1254 result
= bitmap_find_leader (set1
, val
);
1255 if (!result
&& set2
)
1256 result
= bitmap_find_leader (set2
, val
);
1257 if (!result
&& set3
)
1258 result
= bitmap_find_leader (set3
, val
);
1262 /* Get the tree type for our PRE expression e. */
1265 get_expr_type (const pre_expr e
)
1270 return TREE_TYPE (PRE_EXPR_NAME (e
));
1272 return TREE_TYPE (PRE_EXPR_CONSTANT (e
));
1274 return PRE_EXPR_REFERENCE (e
)->type
;
1276 return PRE_EXPR_NARY (e
)->type
;
1281 /* Get a representative SSA_NAME for a given expression.
1282 Since all of our sub-expressions are treated as values, we require
1283 them to be SSA_NAME's for simplicity.
1284 Prior versions of GVNPRE used to use "value handles" here, so that
1285 an expression would be VH.11 + VH.10 instead of d_3 + e_6. In
1286 either case, the operands are really values (IE we do not expect
1287 them to be usable without finding leaders). */
1290 get_representative_for (const pre_expr e
)
1293 unsigned int value_id
= get_expr_value_id (e
);
1298 return VN_INFO (PRE_EXPR_NAME (e
))->valnum
;
1300 return PRE_EXPR_CONSTANT (e
);
1304 /* Go through all of the expressions representing this value
1305 and pick out an SSA_NAME. */
1308 bitmap exprs
= value_expressions
[value_id
];
1309 EXECUTE_IF_SET_IN_BITMAP (exprs
, 0, i
, bi
)
1311 pre_expr rep
= expression_for_id (i
);
1312 if (rep
->kind
== NAME
)
1313 return VN_INFO (PRE_EXPR_NAME (rep
))->valnum
;
1314 else if (rep
->kind
== CONSTANT
)
1315 return PRE_EXPR_CONSTANT (rep
);
1321 /* If we reached here we couldn't find an SSA_NAME. This can
1322 happen when we've discovered a value that has never appeared in
1323 the program as set to an SSA_NAME, as the result of phi translation.
1325 ??? We should be able to re-use this when we insert the statement
1327 name
= make_temp_ssa_name (get_expr_type (e
), gimple_build_nop (), "pretmp");
1328 VN_INFO_GET (name
)->value_id
= value_id
;
1329 VN_INFO (name
)->valnum
= name
;
1330 /* ??? For now mark this SSA name for release by SCCVN. */
1331 VN_INFO (name
)->needs_insertion
= true;
1332 add_to_value (value_id
, get_or_alloc_expr_for_name (name
));
1333 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1335 fprintf (dump_file
, "Created SSA_NAME representative ");
1336 print_generic_expr (dump_file
, name
);
1337 fprintf (dump_file
, " for expression:");
1338 print_pre_expr (dump_file
, e
);
1339 fprintf (dump_file
, " (%04d)\n", value_id
);
1348 phi_translate (pre_expr expr
, bitmap_set_t set1
, bitmap_set_t set2
,
1349 basic_block pred
, basic_block phiblock
);
1351 /* Translate EXPR using phis in PHIBLOCK, so that it has the values of
1352 the phis in PRED. Return NULL if we can't find a leader for each part
1353 of the translated expression. */
1356 phi_translate_1 (pre_expr expr
, bitmap_set_t set1
, bitmap_set_t set2
,
1357 basic_block pred
, basic_block phiblock
)
1364 bool changed
= false;
1365 vn_nary_op_t nary
= PRE_EXPR_NARY (expr
);
1366 vn_nary_op_t newnary
= XALLOCAVAR (struct vn_nary_op_s
,
1367 sizeof_vn_nary_op (nary
->length
));
1368 memcpy (newnary
, nary
, sizeof_vn_nary_op (nary
->length
));
1370 for (i
= 0; i
< newnary
->length
; i
++)
1372 if (TREE_CODE (newnary
->op
[i
]) != SSA_NAME
)
1376 pre_expr leader
, result
;
1377 unsigned int op_val_id
= VN_INFO (newnary
->op
[i
])->value_id
;
1378 leader
= find_leader_in_sets (op_val_id
, set1
, set2
);
1379 result
= phi_translate (leader
, set1
, set2
, pred
, phiblock
);
1380 if (result
&& result
!= leader
)
1381 newnary
->op
[i
] = get_representative_for (result
);
1385 changed
|= newnary
->op
[i
] != nary
->op
[i
];
1391 unsigned int new_val_id
;
1393 PRE_EXPR_NARY (expr
) = newnary
;
1394 constant
= fully_constant_expression (expr
);
1395 PRE_EXPR_NARY (expr
) = nary
;
1396 if (constant
!= expr
)
1398 /* For non-CONSTANTs we have to make sure we can eventually
1399 insert the expression. Which means we need to have a
1401 if (constant
->kind
!= CONSTANT
)
1403 /* Do not allow simplifications to non-constants over
1404 backedges as this will likely result in a loop PHI node
1405 to be inserted and increased register pressure.
1406 See PR77498 - this avoids doing predcoms work in
1407 a less efficient way. */
1408 if (find_edge (pred
, phiblock
)->flags
& EDGE_DFS_BACK
)
1412 unsigned value_id
= get_expr_value_id (constant
);
1413 constant
= find_leader_in_sets (value_id
, set1
, set2
,
1423 tree result
= vn_nary_op_lookup_pieces (newnary
->length
,
1428 if (result
&& is_gimple_min_invariant (result
))
1429 return get_or_alloc_expr_for_constant (result
);
1431 expr
= pre_expr_pool
.allocate ();
1436 PRE_EXPR_NARY (expr
) = nary
;
1437 new_val_id
= nary
->value_id
;
1438 get_or_alloc_expression_id (expr
);
1439 /* When we end up re-using a value number make sure that
1440 doesn't have unrelated (which we can't check here)
1441 range or points-to info on it. */
1443 && INTEGRAL_TYPE_P (TREE_TYPE (result
))
1444 && SSA_NAME_RANGE_INFO (result
)
1445 && ! SSA_NAME_IS_DEFAULT_DEF (result
))
1447 if (! VN_INFO (result
)->info
.range_info
)
1449 VN_INFO (result
)->info
.range_info
1450 = SSA_NAME_RANGE_INFO (result
);
1451 VN_INFO (result
)->range_info_anti_range_p
1452 = SSA_NAME_ANTI_RANGE_P (result
);
1454 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1456 fprintf (dump_file
, "clearing range info of ");
1457 print_generic_expr (dump_file
, result
);
1458 fprintf (dump_file
, "\n");
1460 SSA_NAME_RANGE_INFO (result
) = NULL
;
1463 && POINTER_TYPE_P (TREE_TYPE (result
))
1464 && SSA_NAME_PTR_INFO (result
)
1465 && ! SSA_NAME_IS_DEFAULT_DEF (result
))
1467 if (! VN_INFO (result
)->info
.ptr_info
)
1468 VN_INFO (result
)->info
.ptr_info
1469 = SSA_NAME_PTR_INFO (result
);
1470 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1472 fprintf (dump_file
, "clearing points-to info of ");
1473 print_generic_expr (dump_file
, result
);
1474 fprintf (dump_file
, "\n");
1476 SSA_NAME_PTR_INFO (result
) = NULL
;
1481 new_val_id
= get_next_value_id ();
1482 value_expressions
.safe_grow_cleared (get_max_value_id () + 1);
1483 nary
= vn_nary_op_insert_pieces (newnary
->length
,
1487 result
, new_val_id
);
1488 PRE_EXPR_NARY (expr
) = nary
;
1489 get_or_alloc_expression_id (expr
);
1491 add_to_value (new_val_id
, expr
);
1499 vn_reference_t ref
= PRE_EXPR_REFERENCE (expr
);
1500 vec
<vn_reference_op_s
> operands
= ref
->operands
;
1501 tree vuse
= ref
->vuse
;
1502 tree newvuse
= vuse
;
1503 vec
<vn_reference_op_s
> newoperands
= vNULL
;
1504 bool changed
= false, same_valid
= true;
1506 vn_reference_op_t operand
;
1507 vn_reference_t newref
;
1509 for (i
= 0; operands
.iterate (i
, &operand
); i
++)
1514 tree type
= operand
->type
;
1515 vn_reference_op_s newop
= *operand
;
1516 op
[0] = operand
->op0
;
1517 op
[1] = operand
->op1
;
1518 op
[2] = operand
->op2
;
1519 for (n
= 0; n
< 3; ++n
)
1521 unsigned int op_val_id
;
1524 if (TREE_CODE (op
[n
]) != SSA_NAME
)
1526 /* We can't possibly insert these. */
1528 && !is_gimple_min_invariant (op
[n
]))
1532 op_val_id
= VN_INFO (op
[n
])->value_id
;
1533 leader
= find_leader_in_sets (op_val_id
, set1
, set2
);
1534 opresult
= phi_translate (leader
, set1
, set2
, pred
, phiblock
);
1535 if (opresult
&& opresult
!= leader
)
1537 tree name
= get_representative_for (opresult
);
1538 changed
|= name
!= op
[n
];
1546 newoperands
.release ();
1551 if (!newoperands
.exists ())
1552 newoperands
= operands
.copy ();
1553 /* We may have changed from an SSA_NAME to a constant */
1554 if (newop
.opcode
== SSA_NAME
&& TREE_CODE (op
[0]) != SSA_NAME
)
1555 newop
.opcode
= TREE_CODE (op
[0]);
1560 newoperands
[i
] = newop
;
1562 gcc_checking_assert (i
== operands
.length ());
1566 newvuse
= translate_vuse_through_block (newoperands
.exists ()
1567 ? newoperands
: operands
,
1568 ref
->set
, ref
->type
,
1569 vuse
, phiblock
, pred
,
1571 if (newvuse
== NULL_TREE
)
1573 newoperands
.release ();
1578 if (changed
|| newvuse
!= vuse
)
1580 unsigned int new_val_id
;
1583 tree result
= vn_reference_lookup_pieces (newvuse
, ref
->set
,
1585 newoperands
.exists ()
1586 ? newoperands
: operands
,
1589 newoperands
.release ();
1591 /* We can always insert constants, so if we have a partial
1592 redundant constant load of another type try to translate it
1593 to a constant of appropriate type. */
1594 if (result
&& is_gimple_min_invariant (result
))
1597 if (!useless_type_conversion_p (ref
->type
, TREE_TYPE (result
)))
1599 tem
= fold_unary (VIEW_CONVERT_EXPR
, ref
->type
, result
);
1600 if (tem
&& !is_gimple_min_invariant (tem
))
1604 return get_or_alloc_expr_for_constant (tem
);
1607 /* If we'd have to convert things we would need to validate
1608 if we can insert the translated expression. So fail
1609 here for now - we cannot insert an alias with a different
1610 type in the VN tables either, as that would assert. */
1612 && !useless_type_conversion_p (ref
->type
, TREE_TYPE (result
)))
1614 else if (!result
&& newref
1615 && !useless_type_conversion_p (ref
->type
, newref
->type
))
1617 newoperands
.release ();
1621 expr
= pre_expr_pool
.allocate ();
1622 expr
->kind
= REFERENCE
;
1627 PRE_EXPR_REFERENCE (expr
) = newref
;
1628 constant
= fully_constant_expression (expr
);
1629 if (constant
!= expr
)
1632 new_val_id
= newref
->value_id
;
1633 get_or_alloc_expression_id (expr
);
1637 if (changed
|| !same_valid
)
1639 new_val_id
= get_next_value_id ();
1640 value_expressions
.safe_grow_cleared
1641 (get_max_value_id () + 1);
1644 new_val_id
= ref
->value_id
;
1645 if (!newoperands
.exists ())
1646 newoperands
= operands
.copy ();
1647 newref
= vn_reference_insert_pieces (newvuse
, ref
->set
,
1650 result
, new_val_id
);
1651 newoperands
= vNULL
;
1652 PRE_EXPR_REFERENCE (expr
) = newref
;
1653 constant
= fully_constant_expression (expr
);
1654 if (constant
!= expr
)
1656 get_or_alloc_expression_id (expr
);
1658 add_to_value (new_val_id
, expr
);
1660 newoperands
.release ();
1667 tree name
= PRE_EXPR_NAME (expr
);
1668 gimple
*def_stmt
= SSA_NAME_DEF_STMT (name
);
1669 /* If the SSA name is defined by a PHI node in this block,
1671 if (gimple_code (def_stmt
) == GIMPLE_PHI
1672 && gimple_bb (def_stmt
) == phiblock
)
1674 edge e
= find_edge (pred
, gimple_bb (def_stmt
));
1675 tree def
= PHI_ARG_DEF (def_stmt
, e
->dest_idx
);
1677 /* Handle constant. */
1678 if (is_gimple_min_invariant (def
))
1679 return get_or_alloc_expr_for_constant (def
);
1681 return get_or_alloc_expr_for_name (def
);
1683 /* Otherwise return it unchanged - it will get removed if its
1684 value is not available in PREDs AVAIL_OUT set of expressions
1685 by the subtraction of TMP_GEN. */
1694 /* Wrapper around phi_translate_1 providing caching functionality. */
1697 phi_translate (pre_expr expr
, bitmap_set_t set1
, bitmap_set_t set2
,
1698 basic_block pred
, basic_block phiblock
)
1700 expr_pred_trans_t slot
= NULL
;
1706 /* Constants contain no values that need translation. */
1707 if (expr
->kind
== CONSTANT
)
1710 if (value_id_constant_p (get_expr_value_id (expr
)))
1713 /* Don't add translations of NAMEs as those are cheap to translate. */
1714 if (expr
->kind
!= NAME
)
1716 if (phi_trans_add (&slot
, expr
, pred
))
1718 /* Store NULL for the value we want to return in the case of
1724 phitrans
= phi_translate_1 (expr
, set1
, set2
, pred
, phiblock
);
1731 /* Remove failed translations again, they cause insert
1732 iteration to not pick up new opportunities reliably. */
1733 phi_translate_table
->remove_elt_with_hash (slot
, slot
->hashcode
);
1740 /* For each expression in SET, translate the values through phi nodes
1741 in PHIBLOCK using edge PHIBLOCK->PRED, and store the resulting
1742 expressions in DEST. */
1745 phi_translate_set (bitmap_set_t dest
, bitmap_set_t set
, basic_block pred
,
1746 basic_block phiblock
)
1748 vec
<pre_expr
> exprs
;
1752 if (gimple_seq_empty_p (phi_nodes (phiblock
)))
1754 bitmap_set_copy (dest
, set
);
1758 exprs
= sorted_array_from_bitmap_set (set
);
1759 FOR_EACH_VEC_ELT (exprs
, i
, expr
)
1761 pre_expr translated
;
1762 translated
= phi_translate (expr
, set
, NULL
, pred
, phiblock
);
1766 /* We might end up with multiple expressions from SET being
1767 translated to the same value. In this case we do not want
1768 to retain the NARY or REFERENCE expression but prefer a NAME
1769 which would be the leader. */
1770 if (translated
->kind
== NAME
)
1771 bitmap_value_replace_in_set (dest
, translated
);
1773 bitmap_value_insert_into_set (dest
, translated
);
1778 /* Find the leader for a value (i.e., the name representing that
1779 value) in a given set, and return it. Return NULL if no leader
1783 bitmap_find_leader (bitmap_set_t set
, unsigned int val
)
1785 if (value_id_constant_p (val
))
1789 bitmap exprset
= value_expressions
[val
];
1791 EXECUTE_IF_SET_IN_BITMAP (exprset
, 0, i
, bi
)
1793 pre_expr expr
= expression_for_id (i
);
1794 if (expr
->kind
== CONSTANT
)
1798 if (bitmap_set_contains_value (set
, val
))
1800 /* Rather than walk the entire bitmap of expressions, and see
1801 whether any of them has the value we are looking for, we look
1802 at the reverse mapping, which tells us the set of expressions
1803 that have a given value (IE value->expressions with that
1804 value) and see if any of those expressions are in our set.
1805 The number of expressions per value is usually significantly
1806 less than the number of expressions in the set. In fact, for
1807 large testcases, doing it this way is roughly 5-10x faster
1808 than walking the bitmap.
1809 If this is somehow a significant lose for some cases, we can
1810 choose which set to walk based on which set is smaller. */
1813 bitmap exprset
= value_expressions
[val
];
1815 EXECUTE_IF_AND_IN_BITMAP (exprset
, &set
->expressions
, 0, i
, bi
)
1816 return expression_for_id (i
);
1821 /* Determine if EXPR, a memory expression, is ANTIC_IN at the top of
1822 BLOCK by seeing if it is not killed in the block. Note that we are
1823 only determining whether there is a store that kills it. Because
1824 of the order in which clean iterates over values, we are guaranteed
1825 that altered operands will have caused us to be eliminated from the
1826 ANTIC_IN set already. */
1829 value_dies_in_block_x (pre_expr expr
, basic_block block
)
1831 tree vuse
= PRE_EXPR_REFERENCE (expr
)->vuse
;
1832 vn_reference_t refx
= PRE_EXPR_REFERENCE (expr
);
1834 gimple_stmt_iterator gsi
;
1835 unsigned id
= get_expression_id (expr
);
1842 /* Lookup a previously calculated result. */
1843 if (EXPR_DIES (block
)
1844 && bitmap_bit_p (EXPR_DIES (block
), id
* 2))
1845 return bitmap_bit_p (EXPR_DIES (block
), id
* 2 + 1);
1847 /* A memory expression {e, VUSE} dies in the block if there is a
1848 statement that may clobber e. If, starting statement walk from the
1849 top of the basic block, a statement uses VUSE there can be no kill
1850 inbetween that use and the original statement that loaded {e, VUSE},
1851 so we can stop walking. */
1852 ref
.base
= NULL_TREE
;
1853 for (gsi
= gsi_start_bb (block
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1855 tree def_vuse
, def_vdef
;
1856 def
= gsi_stmt (gsi
);
1857 def_vuse
= gimple_vuse (def
);
1858 def_vdef
= gimple_vdef (def
);
1860 /* Not a memory statement. */
1864 /* Not a may-def. */
1867 /* A load with the same VUSE, we're done. */
1868 if (def_vuse
== vuse
)
1874 /* Init ref only if we really need it. */
1875 if (ref
.base
== NULL_TREE
1876 && !ao_ref_init_from_vn_reference (&ref
, refx
->set
, refx
->type
,
1882 /* If the statement may clobber expr, it dies. */
1883 if (stmt_may_clobber_ref_p_1 (def
, &ref
))
1890 /* Remember the result. */
1891 if (!EXPR_DIES (block
))
1892 EXPR_DIES (block
) = BITMAP_ALLOC (&grand_bitmap_obstack
);
1893 bitmap_set_bit (EXPR_DIES (block
), id
* 2);
1895 bitmap_set_bit (EXPR_DIES (block
), id
* 2 + 1);
1901 /* Determine if OP is valid in SET1 U SET2, which it is when the union
1902 contains its value-id. */
1905 op_valid_in_sets (bitmap_set_t set1
, bitmap_set_t set2
, tree op
)
1907 if (op
&& TREE_CODE (op
) == SSA_NAME
)
1909 unsigned int value_id
= VN_INFO (op
)->value_id
;
1910 if (!(bitmap_set_contains_value (set1
, value_id
)
1911 || (set2
&& bitmap_set_contains_value (set2
, value_id
))))
1917 /* Determine if the expression EXPR is valid in SET1 U SET2.
1918 ONLY SET2 CAN BE NULL.
1919 This means that we have a leader for each part of the expression
1920 (if it consists of values), or the expression is an SSA_NAME.
1921 For loads/calls, we also see if the vuse is killed in this block. */
1924 valid_in_sets (bitmap_set_t set1
, bitmap_set_t set2
, pre_expr expr
)
1929 /* By construction all NAMEs are available. Non-available
1930 NAMEs are removed by subtracting TMP_GEN from the sets. */
1935 vn_nary_op_t nary
= PRE_EXPR_NARY (expr
);
1936 for (i
= 0; i
< nary
->length
; i
++)
1937 if (!op_valid_in_sets (set1
, set2
, nary
->op
[i
]))
1944 vn_reference_t ref
= PRE_EXPR_REFERENCE (expr
);
1945 vn_reference_op_t vro
;
1948 FOR_EACH_VEC_ELT (ref
->operands
, i
, vro
)
1950 if (!op_valid_in_sets (set1
, set2
, vro
->op0
)
1951 || !op_valid_in_sets (set1
, set2
, vro
->op1
)
1952 || !op_valid_in_sets (set1
, set2
, vro
->op2
))
1962 /* Clean the set of expressions SET1 that are no longer valid in SET1 or SET2.
1963 This means expressions that are made up of values we have no leaders for
1967 clean (bitmap_set_t set1
, bitmap_set_t set2
= NULL
)
1969 vec
<pre_expr
> exprs
= sorted_array_from_bitmap_set (set1
);
1973 FOR_EACH_VEC_ELT (exprs
, i
, expr
)
1975 if (!valid_in_sets (set1
, set2
, expr
))
1976 bitmap_remove_expr_from_set (set1
, expr
);
1981 /* Clean the set of expressions that are no longer valid in SET because
1982 they are clobbered in BLOCK or because they trap and may not be executed. */
1985 prune_clobbered_mems (bitmap_set_t set
, basic_block block
)
1989 pre_expr to_remove
= NULL
;
1991 FOR_EACH_EXPR_ID_IN_SET (set
, i
, bi
)
1993 /* Remove queued expr. */
1996 bitmap_remove_expr_from_set (set
, to_remove
);
2000 pre_expr expr
= expression_for_id (i
);
2001 if (expr
->kind
== REFERENCE
)
2003 vn_reference_t ref
= PRE_EXPR_REFERENCE (expr
);
2006 gimple
*def_stmt
= SSA_NAME_DEF_STMT (ref
->vuse
);
2007 if (!gimple_nop_p (def_stmt
)
2008 && ((gimple_bb (def_stmt
) != block
2009 && !dominated_by_p (CDI_DOMINATORS
,
2010 block
, gimple_bb (def_stmt
)))
2011 || (gimple_bb (def_stmt
) == block
2012 && value_dies_in_block_x (expr
, block
))))
2016 else if (expr
->kind
== NARY
)
2018 vn_nary_op_t nary
= PRE_EXPR_NARY (expr
);
2019 /* If the NARY may trap make sure the block does not contain
2020 a possible exit point.
2021 ??? This is overly conservative if we translate AVAIL_OUT
2022 as the available expression might be after the exit point. */
2023 if (BB_MAY_NOTRETURN (block
)
2024 && vn_nary_may_trap (nary
))
2029 /* Remove queued expr. */
2031 bitmap_remove_expr_from_set (set
, to_remove
);
2034 static sbitmap has_abnormal_preds
;
2036 /* Compute the ANTIC set for BLOCK.
2038 If succs(BLOCK) > 1 then
2039 ANTIC_OUT[BLOCK] = intersection of ANTIC_IN[b] for all succ(BLOCK)
2040 else if succs(BLOCK) == 1 then
2041 ANTIC_OUT[BLOCK] = phi_translate (ANTIC_IN[succ(BLOCK)])
2043 ANTIC_IN[BLOCK] = clean(ANTIC_OUT[BLOCK] U EXP_GEN[BLOCK] - TMP_GEN[BLOCK])
2047 compute_antic_aux (basic_block block
, bool block_has_abnormal_pred_edge
)
2049 bitmap_set_t S
, old
, ANTIC_OUT
;
2055 bool changed
= ! BB_VISITED (block
);
2056 BB_VISITED (block
) = 1;
2057 old
= ANTIC_OUT
= S
= NULL
;
2059 /* If any edges from predecessors are abnormal, antic_in is empty,
2061 if (block_has_abnormal_pred_edge
)
2062 goto maybe_dump_sets
;
2064 old
= ANTIC_IN (block
);
2065 ANTIC_OUT
= bitmap_set_new ();
2067 /* If the block has no successors, ANTIC_OUT is empty. */
2068 if (EDGE_COUNT (block
->succs
) == 0)
2070 /* If we have one successor, we could have some phi nodes to
2071 translate through. */
2072 else if (single_succ_p (block
))
2074 basic_block succ_bb
= single_succ (block
);
2075 gcc_assert (BB_VISITED (succ_bb
));
2076 phi_translate_set (ANTIC_OUT
, ANTIC_IN (succ_bb
), block
, succ_bb
);
2078 /* If we have multiple successors, we take the intersection of all of
2079 them. Note that in the case of loop exit phi nodes, we may have
2080 phis to translate through. */
2084 basic_block bprime
, first
= NULL
;
2086 auto_vec
<basic_block
> worklist (EDGE_COUNT (block
->succs
));
2087 FOR_EACH_EDGE (e
, ei
, block
->succs
)
2090 && BB_VISITED (e
->dest
))
2092 else if (BB_VISITED (e
->dest
))
2093 worklist
.quick_push (e
->dest
);
2096 /* Unvisited successors get their ANTIC_IN replaced by the
2097 maximal set to arrive at a maximum ANTIC_IN solution.
2098 We can ignore them in the intersection operation and thus
2099 need not explicitely represent that maximum solution. */
2100 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2101 fprintf (dump_file
, "ANTIC_IN is MAX on %d->%d\n",
2102 e
->src
->index
, e
->dest
->index
);
2106 /* Of multiple successors we have to have visited one already
2107 which is guaranteed by iteration order. */
2108 gcc_assert (first
!= NULL
);
2110 phi_translate_set (ANTIC_OUT
, ANTIC_IN (first
), block
, first
);
2112 /* If we have multiple successors we need to intersect the ANTIC_OUT
2113 sets. For values that's a simple intersection but for
2114 expressions it is a union. Given we want to have a single
2115 expression per value in our sets we have to canonicalize.
2116 Avoid randomness and running into cycles like for PR82129 and
2117 canonicalize the expression we choose to the one with the
2118 lowest id. This requires we actually compute the union first. */
2119 FOR_EACH_VEC_ELT (worklist
, i
, bprime
)
2121 if (!gimple_seq_empty_p (phi_nodes (bprime
)))
2123 bitmap_set_t tmp
= bitmap_set_new ();
2124 phi_translate_set (tmp
, ANTIC_IN (bprime
), block
, bprime
);
2125 bitmap_and_into (&ANTIC_OUT
->values
, &tmp
->values
);
2126 bitmap_ior_into (&ANTIC_OUT
->expressions
, &tmp
->expressions
);
2127 bitmap_set_free (tmp
);
2131 bitmap_and_into (&ANTIC_OUT
->values
, &ANTIC_IN (bprime
)->values
);
2132 bitmap_ior_into (&ANTIC_OUT
->expressions
,
2133 &ANTIC_IN (bprime
)->expressions
);
2136 if (! worklist
.is_empty ())
2138 /* Prune expressions not in the value set, canonicalizing to
2139 expression with lowest ID. */
2142 unsigned int to_clear
= -1U;
2143 bitmap seen_value
= BITMAP_ALLOC (NULL
);
2144 FOR_EACH_EXPR_ID_IN_SET (ANTIC_OUT
, i
, bi
)
2146 if (to_clear
!= -1U)
2148 bitmap_clear_bit (&ANTIC_OUT
->expressions
, to_clear
);
2151 pre_expr expr
= expression_for_id (i
);
2152 unsigned int value_id
= get_expr_value_id (expr
);
2153 if (!bitmap_bit_p (&ANTIC_OUT
->values
, value_id
)
2154 || !bitmap_set_bit (seen_value
, value_id
))
2157 if (to_clear
!= -1U)
2158 bitmap_clear_bit (&ANTIC_OUT
->expressions
, to_clear
);
2159 BITMAP_FREE (seen_value
);
2163 /* Prune expressions that are clobbered in block and thus become
2164 invalid if translated from ANTIC_OUT to ANTIC_IN. */
2165 prune_clobbered_mems (ANTIC_OUT
, block
);
2167 /* Generate ANTIC_OUT - TMP_GEN. */
2168 S
= bitmap_set_subtract_expressions (ANTIC_OUT
, TMP_GEN (block
));
2170 /* Start ANTIC_IN with EXP_GEN - TMP_GEN. */
2171 ANTIC_IN (block
) = bitmap_set_subtract_expressions (EXP_GEN (block
),
2174 /* Then union in the ANTIC_OUT - TMP_GEN values,
2175 to get ANTIC_OUT U EXP_GEN - TMP_GEN */
2176 FOR_EACH_EXPR_ID_IN_SET (S
, bii
, bi
)
2177 bitmap_value_insert_into_set (ANTIC_IN (block
),
2178 expression_for_id (bii
));
2180 clean (ANTIC_IN (block
));
2182 if (!bitmap_set_equal (old
, ANTIC_IN (block
)))
2186 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2189 print_bitmap_set (dump_file
, ANTIC_OUT
, "ANTIC_OUT", block
->index
);
2192 fprintf (dump_file
, "[changed] ");
2193 print_bitmap_set (dump_file
, ANTIC_IN (block
), "ANTIC_IN",
2197 print_bitmap_set (dump_file
, S
, "S", block
->index
);
2200 bitmap_set_free (old
);
2202 bitmap_set_free (S
);
2204 bitmap_set_free (ANTIC_OUT
);
2208 /* Compute PARTIAL_ANTIC for BLOCK.
2210 If succs(BLOCK) > 1 then
2211 PA_OUT[BLOCK] = value wise union of PA_IN[b] + all ANTIC_IN not
2212 in ANTIC_OUT for all succ(BLOCK)
2213 else if succs(BLOCK) == 1 then
2214 PA_OUT[BLOCK] = phi_translate (PA_IN[succ(BLOCK)])
2216 PA_IN[BLOCK] = clean(PA_OUT[BLOCK] - TMP_GEN[BLOCK] - ANTIC_IN[BLOCK])
2220 compute_partial_antic_aux (basic_block block
,
2221 bool block_has_abnormal_pred_edge
)
2223 bitmap_set_t old_PA_IN
;
2224 bitmap_set_t PA_OUT
;
2227 unsigned long max_pa
= PARAM_VALUE (PARAM_MAX_PARTIAL_ANTIC_LENGTH
);
2229 old_PA_IN
= PA_OUT
= NULL
;
2231 /* If any edges from predecessors are abnormal, antic_in is empty,
2233 if (block_has_abnormal_pred_edge
)
2234 goto maybe_dump_sets
;
2236 /* If there are too many partially anticipatable values in the
2237 block, phi_translate_set can take an exponential time: stop
2238 before the translation starts. */
2240 && single_succ_p (block
)
2241 && bitmap_count_bits (&PA_IN (single_succ (block
))->values
) > max_pa
)
2242 goto maybe_dump_sets
;
2244 old_PA_IN
= PA_IN (block
);
2245 PA_OUT
= bitmap_set_new ();
2247 /* If the block has no successors, ANTIC_OUT is empty. */
2248 if (EDGE_COUNT (block
->succs
) == 0)
2250 /* If we have one successor, we could have some phi nodes to
2251 translate through. Note that we can't phi translate across DFS
2252 back edges in partial antic, because it uses a union operation on
2253 the successors. For recurrences like IV's, we will end up
2254 generating a new value in the set on each go around (i + 3 (VH.1)
2255 VH.1 + 1 (VH.2), VH.2 + 1 (VH.3), etc), forever. */
2256 else if (single_succ_p (block
))
2258 basic_block succ
= single_succ (block
);
2259 if (!(single_succ_edge (block
)->flags
& EDGE_DFS_BACK
))
2260 phi_translate_set (PA_OUT
, PA_IN (succ
), block
, succ
);
2262 /* If we have multiple successors, we take the union of all of
2269 auto_vec
<basic_block
> worklist (EDGE_COUNT (block
->succs
));
2270 FOR_EACH_EDGE (e
, ei
, block
->succs
)
2272 if (e
->flags
& EDGE_DFS_BACK
)
2274 worklist
.quick_push (e
->dest
);
2276 if (worklist
.length () > 0)
2278 FOR_EACH_VEC_ELT (worklist
, i
, bprime
)
2283 FOR_EACH_EXPR_ID_IN_SET (ANTIC_IN (bprime
), i
, bi
)
2284 bitmap_value_insert_into_set (PA_OUT
,
2285 expression_for_id (i
));
2286 if (!gimple_seq_empty_p (phi_nodes (bprime
)))
2288 bitmap_set_t pa_in
= bitmap_set_new ();
2289 phi_translate_set (pa_in
, PA_IN (bprime
), block
, bprime
);
2290 FOR_EACH_EXPR_ID_IN_SET (pa_in
, i
, bi
)
2291 bitmap_value_insert_into_set (PA_OUT
,
2292 expression_for_id (i
));
2293 bitmap_set_free (pa_in
);
2296 FOR_EACH_EXPR_ID_IN_SET (PA_IN (bprime
), i
, bi
)
2297 bitmap_value_insert_into_set (PA_OUT
,
2298 expression_for_id (i
));
2303 /* Prune expressions that are clobbered in block and thus become
2304 invalid if translated from PA_OUT to PA_IN. */
2305 prune_clobbered_mems (PA_OUT
, block
);
2307 /* PA_IN starts with PA_OUT - TMP_GEN.
2308 Then we subtract things from ANTIC_IN. */
2309 PA_IN (block
) = bitmap_set_subtract_expressions (PA_OUT
, TMP_GEN (block
));
2311 /* For partial antic, we want to put back in the phi results, since
2312 we will properly avoid making them partially antic over backedges. */
2313 bitmap_ior_into (&PA_IN (block
)->values
, &PHI_GEN (block
)->values
);
2314 bitmap_ior_into (&PA_IN (block
)->expressions
, &PHI_GEN (block
)->expressions
);
2316 /* PA_IN[block] = PA_IN[block] - ANTIC_IN[block] */
2317 bitmap_set_subtract_values (PA_IN (block
), ANTIC_IN (block
));
2319 clean (PA_IN (block
), ANTIC_IN (block
));
2322 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2325 print_bitmap_set (dump_file
, PA_OUT
, "PA_OUT", block
->index
);
2327 print_bitmap_set (dump_file
, PA_IN (block
), "PA_IN", block
->index
);
2330 bitmap_set_free (old_PA_IN
);
2332 bitmap_set_free (PA_OUT
);
2335 /* Compute ANTIC and partial ANTIC sets. */
2338 compute_antic (void)
2340 bool changed
= true;
2341 int num_iterations
= 0;
2347 /* If any predecessor edges are abnormal, we punt, so antic_in is empty.
2348 We pre-build the map of blocks with incoming abnormal edges here. */
2349 has_abnormal_preds
= sbitmap_alloc (last_basic_block_for_fn (cfun
));
2350 bitmap_clear (has_abnormal_preds
);
2352 FOR_ALL_BB_FN (block
, cfun
)
2354 BB_VISITED (block
) = 0;
2356 FOR_EACH_EDGE (e
, ei
, block
->preds
)
2357 if (e
->flags
& EDGE_ABNORMAL
)
2359 bitmap_set_bit (has_abnormal_preds
, block
->index
);
2363 /* While we are here, give empty ANTIC_IN sets to each block. */
2364 ANTIC_IN (block
) = bitmap_set_new ();
2365 if (do_partial_partial
)
2366 PA_IN (block
) = bitmap_set_new ();
2369 /* At the exit block we anticipate nothing. */
2370 BB_VISITED (EXIT_BLOCK_PTR_FOR_FN (cfun
)) = 1;
2372 /* For ANTIC computation we need a postorder that also guarantees that
2373 a block with a single successor is visited after its successor.
2374 RPO on the inverted CFG has this property. */
2375 auto_vec
<int, 20> postorder
;
2376 inverted_post_order_compute (&postorder
);
2378 auto_sbitmap
worklist (last_basic_block_for_fn (cfun
) + 1);
2379 bitmap_clear (worklist
);
2380 FOR_EACH_EDGE (e
, ei
, EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
)
2381 bitmap_set_bit (worklist
, e
->src
->index
);
2384 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2385 fprintf (dump_file
, "Starting iteration %d\n", num_iterations
);
2386 /* ??? We need to clear our PHI translation cache here as the
2387 ANTIC sets shrink and we restrict valid translations to
2388 those having operands with leaders in ANTIC. Same below
2389 for PA ANTIC computation. */
2392 for (i
= postorder
.length () - 1; i
>= 0; i
--)
2394 if (bitmap_bit_p (worklist
, postorder
[i
]))
2396 basic_block block
= BASIC_BLOCK_FOR_FN (cfun
, postorder
[i
]);
2397 bitmap_clear_bit (worklist
, block
->index
);
2398 if (compute_antic_aux (block
,
2399 bitmap_bit_p (has_abnormal_preds
,
2402 FOR_EACH_EDGE (e
, ei
, block
->preds
)
2403 bitmap_set_bit (worklist
, e
->src
->index
);
2408 /* Theoretically possible, but *highly* unlikely. */
2409 gcc_checking_assert (num_iterations
< 500);
2412 statistics_histogram_event (cfun
, "compute_antic iterations",
2415 if (do_partial_partial
)
2417 /* For partial antic we ignore backedges and thus we do not need
2418 to perform any iteration when we process blocks in postorder. */
2420 = pre_and_rev_post_order_compute (NULL
, postorder
.address (), false);
2421 for (i
= postorder_num
- 1 ; i
>= 0; i
--)
2423 basic_block block
= BASIC_BLOCK_FOR_FN (cfun
, postorder
[i
]);
2424 compute_partial_antic_aux (block
,
2425 bitmap_bit_p (has_abnormal_preds
,
2430 sbitmap_free (has_abnormal_preds
);
2434 /* Inserted expressions are placed onto this worklist, which is used
2435 for performing quick dead code elimination of insertions we made
2436 that didn't turn out to be necessary. */
2437 static bitmap inserted_exprs
;
2439 /* The actual worker for create_component_ref_by_pieces. */
2442 create_component_ref_by_pieces_1 (basic_block block
, vn_reference_t ref
,
2443 unsigned int *operand
, gimple_seq
*stmts
)
2445 vn_reference_op_t currop
= &ref
->operands
[*operand
];
2448 switch (currop
->opcode
)
2455 tree baseop
= create_component_ref_by_pieces_1 (block
, ref
, operand
,
2459 tree offset
= currop
->op0
;
2460 if (TREE_CODE (baseop
) == ADDR_EXPR
2461 && handled_component_p (TREE_OPERAND (baseop
, 0)))
2465 base
= get_addr_base_and_unit_offset (TREE_OPERAND (baseop
, 0),
2468 offset
= int_const_binop (PLUS_EXPR
, offset
,
2469 build_int_cst (TREE_TYPE (offset
),
2471 baseop
= build_fold_addr_expr (base
);
2473 genop
= build2 (MEM_REF
, currop
->type
, baseop
, offset
);
2474 MR_DEPENDENCE_CLIQUE (genop
) = currop
->clique
;
2475 MR_DEPENDENCE_BASE (genop
) = currop
->base
;
2476 REF_REVERSE_STORAGE_ORDER (genop
) = currop
->reverse
;
2480 case TARGET_MEM_REF
:
2482 tree genop0
= NULL_TREE
, genop1
= NULL_TREE
;
2483 vn_reference_op_t nextop
= &ref
->operands
[++*operand
];
2484 tree baseop
= create_component_ref_by_pieces_1 (block
, ref
, operand
,
2490 genop0
= find_or_generate_expression (block
, currop
->op0
, stmts
);
2496 genop1
= find_or_generate_expression (block
, nextop
->op0
, stmts
);
2500 genop
= build5 (TARGET_MEM_REF
, currop
->type
,
2501 baseop
, currop
->op2
, genop0
, currop
->op1
, genop1
);
2503 MR_DEPENDENCE_CLIQUE (genop
) = currop
->clique
;
2504 MR_DEPENDENCE_BASE (genop
) = currop
->base
;
2511 gcc_assert (is_gimple_min_invariant (currop
->op0
));
2517 case VIEW_CONVERT_EXPR
:
2519 tree genop0
= create_component_ref_by_pieces_1 (block
, ref
, operand
,
2523 return fold_build1 (currop
->opcode
, currop
->type
, genop0
);
2526 case WITH_SIZE_EXPR
:
2528 tree genop0
= create_component_ref_by_pieces_1 (block
, ref
, operand
,
2532 tree genop1
= find_or_generate_expression (block
, currop
->op0
, stmts
);
2535 return fold_build2 (currop
->opcode
, currop
->type
, genop0
, genop1
);
2540 tree genop0
= create_component_ref_by_pieces_1 (block
, ref
, operand
,
2544 tree op1
= currop
->op0
;
2545 tree op2
= currop
->op1
;
2546 tree t
= build3 (BIT_FIELD_REF
, currop
->type
, genop0
, op1
, op2
);
2547 REF_REVERSE_STORAGE_ORDER (t
) = currop
->reverse
;
2551 /* For array ref vn_reference_op's, operand 1 of the array ref
2552 is op0 of the reference op and operand 3 of the array ref is
2554 case ARRAY_RANGE_REF
:
2558 tree genop1
= currop
->op0
;
2559 tree genop2
= currop
->op1
;
2560 tree genop3
= currop
->op2
;
2561 genop0
= create_component_ref_by_pieces_1 (block
, ref
, operand
,
2565 genop1
= find_or_generate_expression (block
, genop1
, stmts
);
2570 tree domain_type
= TYPE_DOMAIN (TREE_TYPE (genop0
));
2571 /* Drop zero minimum index if redundant. */
2572 if (integer_zerop (genop2
)
2574 || integer_zerop (TYPE_MIN_VALUE (domain_type
))))
2578 genop2
= find_or_generate_expression (block
, genop2
, stmts
);
2585 tree elmt_type
= TREE_TYPE (TREE_TYPE (genop0
));
2586 /* We can't always put a size in units of the element alignment
2587 here as the element alignment may be not visible. See
2588 PR43783. Simply drop the element size for constant
2590 if (TREE_CODE (genop3
) == INTEGER_CST
2591 && TREE_CODE (TYPE_SIZE_UNIT (elmt_type
)) == INTEGER_CST
2592 && wi::eq_p (wi::to_offset (TYPE_SIZE_UNIT (elmt_type
)),
2593 (wi::to_offset (genop3
)
2594 * vn_ref_op_align_unit (currop
))))
2598 genop3
= find_or_generate_expression (block
, genop3
, stmts
);
2603 return build4 (currop
->opcode
, currop
->type
, genop0
, genop1
,
2610 tree genop2
= currop
->op1
;
2611 op0
= create_component_ref_by_pieces_1 (block
, ref
, operand
, stmts
);
2614 /* op1 should be a FIELD_DECL, which are represented by themselves. */
2618 genop2
= find_or_generate_expression (block
, genop2
, stmts
);
2622 return fold_build3 (COMPONENT_REF
, TREE_TYPE (op1
), op0
, op1
, genop2
);
2627 genop
= find_or_generate_expression (block
, currop
->op0
, stmts
);
2648 /* For COMPONENT_REF's and ARRAY_REF's, we can't have any intermediates for the
2649 COMPONENT_REF or MEM_REF or ARRAY_REF portion, because we'd end up with
2650 trying to rename aggregates into ssa form directly, which is a no no.
2652 Thus, this routine doesn't create temporaries, it just builds a
2653 single access expression for the array, calling
2654 find_or_generate_expression to build the innermost pieces.
2656 This function is a subroutine of create_expression_by_pieces, and
2657 should not be called on it's own unless you really know what you
2661 create_component_ref_by_pieces (basic_block block
, vn_reference_t ref
,
2664 unsigned int op
= 0;
2665 return create_component_ref_by_pieces_1 (block
, ref
, &op
, stmts
);
2668 /* Find a simple leader for an expression, or generate one using
2669 create_expression_by_pieces from a NARY expression for the value.
2670 BLOCK is the basic_block we are looking for leaders in.
2671 OP is the tree expression to find a leader for or generate.
2672 Returns the leader or NULL_TREE on failure. */
2675 find_or_generate_expression (basic_block block
, tree op
, gimple_seq
*stmts
)
2677 pre_expr expr
= get_or_alloc_expr_for (op
);
2678 unsigned int lookfor
= get_expr_value_id (expr
);
2679 pre_expr leader
= bitmap_find_leader (AVAIL_OUT (block
), lookfor
);
2682 if (leader
->kind
== NAME
)
2683 return PRE_EXPR_NAME (leader
);
2684 else if (leader
->kind
== CONSTANT
)
2685 return PRE_EXPR_CONSTANT (leader
);
2691 /* It must be a complex expression, so generate it recursively. Note
2692 that this is only necessary to handle gcc.dg/tree-ssa/ssa-pre28.c
2693 where the insert algorithm fails to insert a required expression. */
2694 bitmap exprset
= value_expressions
[lookfor
];
2697 EXECUTE_IF_SET_IN_BITMAP (exprset
, 0, i
, bi
)
2699 pre_expr temp
= expression_for_id (i
);
2700 /* We cannot insert random REFERENCE expressions at arbitrary
2701 places. We can insert NARYs which eventually re-materializes
2702 its operand values. */
2703 if (temp
->kind
== NARY
)
2704 return create_expression_by_pieces (block
, temp
, stmts
,
2705 get_expr_type (expr
));
2712 /* Create an expression in pieces, so that we can handle very complex
2713 expressions that may be ANTIC, but not necessary GIMPLE.
2714 BLOCK is the basic block the expression will be inserted into,
2715 EXPR is the expression to insert (in value form)
2716 STMTS is a statement list to append the necessary insertions into.
2718 This function will die if we hit some value that shouldn't be
2719 ANTIC but is (IE there is no leader for it, or its components).
2720 The function returns NULL_TREE in case a different antic expression
2721 has to be inserted first.
2722 This function may also generate expressions that are themselves
2723 partially or fully redundant. Those that are will be either made
2724 fully redundant during the next iteration of insert (for partially
2725 redundant ones), or eliminated by eliminate (for fully redundant
2729 create_expression_by_pieces (basic_block block
, pre_expr expr
,
2730 gimple_seq
*stmts
, tree type
)
2734 gimple_seq forced_stmts
= NULL
;
2735 unsigned int value_id
;
2736 gimple_stmt_iterator gsi
;
2737 tree exprtype
= type
? type
: get_expr_type (expr
);
2743 /* We may hit the NAME/CONSTANT case if we have to convert types
2744 that value numbering saw through. */
2746 folded
= PRE_EXPR_NAME (expr
);
2747 if (useless_type_conversion_p (exprtype
, TREE_TYPE (folded
)))
2752 folded
= PRE_EXPR_CONSTANT (expr
);
2753 tree tem
= fold_convert (exprtype
, folded
);
2754 if (is_gimple_min_invariant (tem
))
2759 if (PRE_EXPR_REFERENCE (expr
)->operands
[0].opcode
== CALL_EXPR
)
2761 vn_reference_t ref
= PRE_EXPR_REFERENCE (expr
);
2762 unsigned int operand
= 1;
2763 vn_reference_op_t currop
= &ref
->operands
[0];
2764 tree sc
= NULL_TREE
;
2766 if (TREE_CODE (currop
->op0
) == FUNCTION_DECL
)
2769 fn
= find_or_generate_expression (block
, currop
->op0
, stmts
);
2774 sc
= find_or_generate_expression (block
, currop
->op1
, stmts
);
2778 auto_vec
<tree
> args (ref
->operands
.length () - 1);
2779 while (operand
< ref
->operands
.length ())
2781 tree arg
= create_component_ref_by_pieces_1 (block
, ref
,
2785 args
.quick_push (arg
);
2788 = gimple_build_call_vec ((TREE_CODE (fn
) == FUNCTION_DECL
2789 ? build_fold_addr_expr (fn
) : fn
), args
);
2790 gimple_call_set_with_bounds (call
, currop
->with_bounds
);
2792 gimple_call_set_chain (call
, sc
);
2793 tree forcedname
= make_ssa_name (currop
->type
);
2794 gimple_call_set_lhs (call
, forcedname
);
2795 gimple_set_vuse (call
, BB_LIVE_VOP_ON_EXIT (block
));
2796 gimple_seq_add_stmt_without_update (&forced_stmts
, call
);
2797 folded
= forcedname
;
2801 folded
= create_component_ref_by_pieces (block
,
2802 PRE_EXPR_REFERENCE (expr
),
2806 name
= make_temp_ssa_name (exprtype
, NULL
, "pretmp");
2807 newstmt
= gimple_build_assign (name
, folded
);
2808 gimple_seq_add_stmt_without_update (&forced_stmts
, newstmt
);
2809 gimple_set_vuse (newstmt
, BB_LIVE_VOP_ON_EXIT (block
));
2815 vn_nary_op_t nary
= PRE_EXPR_NARY (expr
);
2816 tree
*genop
= XALLOCAVEC (tree
, nary
->length
);
2818 for (i
= 0; i
< nary
->length
; ++i
)
2820 genop
[i
] = find_or_generate_expression (block
, nary
->op
[i
], stmts
);
2823 /* Ensure genop[] is properly typed for POINTER_PLUS_EXPR. It
2824 may have conversions stripped. */
2825 if (nary
->opcode
== POINTER_PLUS_EXPR
)
2828 genop
[i
] = gimple_convert (&forced_stmts
,
2829 nary
->type
, genop
[i
]);
2831 genop
[i
] = gimple_convert (&forced_stmts
,
2832 sizetype
, genop
[i
]);
2835 genop
[i
] = gimple_convert (&forced_stmts
,
2836 TREE_TYPE (nary
->op
[i
]), genop
[i
]);
2838 if (nary
->opcode
== CONSTRUCTOR
)
2840 vec
<constructor_elt
, va_gc
> *elts
= NULL
;
2841 for (i
= 0; i
< nary
->length
; ++i
)
2842 CONSTRUCTOR_APPEND_ELT (elts
, NULL_TREE
, genop
[i
]);
2843 folded
= build_constructor (nary
->type
, elts
);
2844 name
= make_temp_ssa_name (exprtype
, NULL
, "pretmp");
2845 newstmt
= gimple_build_assign (name
, folded
);
2846 gimple_seq_add_stmt_without_update (&forced_stmts
, newstmt
);
2851 switch (nary
->length
)
2854 folded
= gimple_build (&forced_stmts
, nary
->opcode
, nary
->type
,
2858 folded
= gimple_build (&forced_stmts
, nary
->opcode
, nary
->type
,
2859 genop
[0], genop
[1]);
2862 folded
= gimple_build (&forced_stmts
, nary
->opcode
, nary
->type
,
2863 genop
[0], genop
[1], genop
[2]);
2875 folded
= gimple_convert (&forced_stmts
, exprtype
, folded
);
2877 /* If there is nothing to insert, return the simplified result. */
2878 if (gimple_seq_empty_p (forced_stmts
))
2880 /* If we simplified to a constant return it and discard eventually
2882 if (is_gimple_min_invariant (folded
))
2884 gimple_seq_discard (forced_stmts
);
2887 /* Likewise if we simplified to sth not queued for insertion. */
2889 gsi
= gsi_last (forced_stmts
);
2890 for (; !gsi_end_p (gsi
); gsi_prev (&gsi
))
2892 gimple
*stmt
= gsi_stmt (gsi
);
2893 tree forcedname
= gimple_get_lhs (stmt
);
2894 if (forcedname
== folded
)
2902 gimple_seq_discard (forced_stmts
);
2905 gcc_assert (TREE_CODE (folded
) == SSA_NAME
);
2907 /* If we have any intermediate expressions to the value sets, add them
2908 to the value sets and chain them in the instruction stream. */
2911 gsi
= gsi_start (forced_stmts
);
2912 for (; !gsi_end_p (gsi
); gsi_next (&gsi
))
2914 gimple
*stmt
= gsi_stmt (gsi
);
2915 tree forcedname
= gimple_get_lhs (stmt
);
2918 if (forcedname
!= folded
)
2920 VN_INFO_GET (forcedname
)->valnum
= forcedname
;
2921 VN_INFO (forcedname
)->value_id
= get_next_value_id ();
2922 nameexpr
= get_or_alloc_expr_for_name (forcedname
);
2923 add_to_value (VN_INFO (forcedname
)->value_id
, nameexpr
);
2924 bitmap_value_replace_in_set (NEW_SETS (block
), nameexpr
);
2925 bitmap_value_replace_in_set (AVAIL_OUT (block
), nameexpr
);
2928 bitmap_set_bit (inserted_exprs
, SSA_NAME_VERSION (forcedname
));
2930 gimple_seq_add_seq (stmts
, forced_stmts
);
2935 /* Fold the last statement. */
2936 gsi
= gsi_last (*stmts
);
2937 if (fold_stmt_inplace (&gsi
))
2938 update_stmt (gsi_stmt (gsi
));
2940 /* Add a value number to the temporary.
2941 The value may already exist in either NEW_SETS, or AVAIL_OUT, because
2942 we are creating the expression by pieces, and this particular piece of
2943 the expression may have been represented. There is no harm in replacing
2945 value_id
= get_expr_value_id (expr
);
2946 VN_INFO_GET (name
)->value_id
= value_id
;
2947 VN_INFO (name
)->valnum
= sccvn_valnum_from_value_id (value_id
);
2948 if (VN_INFO (name
)->valnum
== NULL_TREE
)
2949 VN_INFO (name
)->valnum
= name
;
2950 gcc_assert (VN_INFO (name
)->valnum
!= NULL_TREE
);
2951 nameexpr
= get_or_alloc_expr_for_name (name
);
2952 add_to_value (value_id
, nameexpr
);
2953 if (NEW_SETS (block
))
2954 bitmap_value_replace_in_set (NEW_SETS (block
), nameexpr
);
2955 bitmap_value_replace_in_set (AVAIL_OUT (block
), nameexpr
);
2957 pre_stats
.insertions
++;
2958 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2960 fprintf (dump_file
, "Inserted ");
2961 print_gimple_stmt (dump_file
, gsi_stmt (gsi_last (*stmts
)), 0);
2962 fprintf (dump_file
, " in predecessor %d (%04d)\n",
2963 block
->index
, value_id
);
2970 /* Insert the to-be-made-available values of expression EXPRNUM for each
2971 predecessor, stored in AVAIL, into the predecessors of BLOCK, and
2972 merge the result with a phi node, given the same value number as
2973 NODE. Return true if we have inserted new stuff. */
2976 insert_into_preds_of_block (basic_block block
, unsigned int exprnum
,
2977 vec
<pre_expr
> avail
)
2979 pre_expr expr
= expression_for_id (exprnum
);
2981 unsigned int val
= get_expr_value_id (expr
);
2983 bool insertions
= false;
2988 tree type
= get_expr_type (expr
);
2992 /* Make sure we aren't creating an induction variable. */
2993 if (bb_loop_depth (block
) > 0 && EDGE_COUNT (block
->preds
) == 2)
2995 bool firstinsideloop
= false;
2996 bool secondinsideloop
= false;
2997 firstinsideloop
= flow_bb_inside_loop_p (block
->loop_father
,
2998 EDGE_PRED (block
, 0)->src
);
2999 secondinsideloop
= flow_bb_inside_loop_p (block
->loop_father
,
3000 EDGE_PRED (block
, 1)->src
);
3001 /* Induction variables only have one edge inside the loop. */
3002 if ((firstinsideloop
^ secondinsideloop
)
3003 && expr
->kind
!= REFERENCE
)
3005 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3006 fprintf (dump_file
, "Skipping insertion of phi for partial redundancy: Looks like an induction variable\n");
3011 /* Make the necessary insertions. */
3012 FOR_EACH_EDGE (pred
, ei
, block
->preds
)
3014 gimple_seq stmts
= NULL
;
3017 eprime
= avail
[pred
->dest_idx
];
3018 builtexpr
= create_expression_by_pieces (bprime
, eprime
,
3020 gcc_assert (!(pred
->flags
& EDGE_ABNORMAL
));
3021 if (!gimple_seq_empty_p (stmts
))
3023 gsi_insert_seq_on_edge (pred
, stmts
);
3028 /* We cannot insert a PHI node if we failed to insert
3033 if (is_gimple_min_invariant (builtexpr
))
3034 avail
[pred
->dest_idx
] = get_or_alloc_expr_for_constant (builtexpr
);
3036 avail
[pred
->dest_idx
] = get_or_alloc_expr_for_name (builtexpr
);
3038 /* If we didn't want a phi node, and we made insertions, we still have
3039 inserted new stuff, and thus return true. If we didn't want a phi node,
3040 and didn't make insertions, we haven't added anything new, so return
3042 if (nophi
&& insertions
)
3044 else if (nophi
&& !insertions
)
3047 /* Now build a phi for the new variable. */
3048 temp
= make_temp_ssa_name (type
, NULL
, "prephitmp");
3049 phi
= create_phi_node (temp
, block
);
3051 VN_INFO_GET (temp
)->value_id
= val
;
3052 VN_INFO (temp
)->valnum
= sccvn_valnum_from_value_id (val
);
3053 if (VN_INFO (temp
)->valnum
== NULL_TREE
)
3054 VN_INFO (temp
)->valnum
= temp
;
3055 bitmap_set_bit (inserted_exprs
, SSA_NAME_VERSION (temp
));
3056 FOR_EACH_EDGE (pred
, ei
, block
->preds
)
3058 pre_expr ae
= avail
[pred
->dest_idx
];
3059 gcc_assert (get_expr_type (ae
) == type
3060 || useless_type_conversion_p (type
, get_expr_type (ae
)));
3061 if (ae
->kind
== CONSTANT
)
3062 add_phi_arg (phi
, unshare_expr (PRE_EXPR_CONSTANT (ae
)),
3063 pred
, UNKNOWN_LOCATION
);
3065 add_phi_arg (phi
, PRE_EXPR_NAME (ae
), pred
, UNKNOWN_LOCATION
);
3068 newphi
= get_or_alloc_expr_for_name (temp
);
3069 add_to_value (val
, newphi
);
3071 /* The value should *not* exist in PHI_GEN, or else we wouldn't be doing
3072 this insertion, since we test for the existence of this value in PHI_GEN
3073 before proceeding with the partial redundancy checks in insert_aux.
3075 The value may exist in AVAIL_OUT, in particular, it could be represented
3076 by the expression we are trying to eliminate, in which case we want the
3077 replacement to occur. If it's not existing in AVAIL_OUT, we want it
3080 Similarly, to the PHI_GEN case, the value should not exist in NEW_SETS of
3081 this block, because if it did, it would have existed in our dominator's
3082 AVAIL_OUT, and would have been skipped due to the full redundancy check.
3085 bitmap_insert_into_set (PHI_GEN (block
), newphi
);
3086 bitmap_value_replace_in_set (AVAIL_OUT (block
),
3088 bitmap_insert_into_set (NEW_SETS (block
),
3091 /* If we insert a PHI node for a conversion of another PHI node
3092 in the same basic-block try to preserve range information.
3093 This is important so that followup loop passes receive optimal
3094 number of iteration analysis results. See PR61743. */
3095 if (expr
->kind
== NARY
3096 && CONVERT_EXPR_CODE_P (expr
->u
.nary
->opcode
)
3097 && TREE_CODE (expr
->u
.nary
->op
[0]) == SSA_NAME
3098 && gimple_bb (SSA_NAME_DEF_STMT (expr
->u
.nary
->op
[0])) == block
3099 && INTEGRAL_TYPE_P (type
)
3100 && INTEGRAL_TYPE_P (TREE_TYPE (expr
->u
.nary
->op
[0]))
3101 && (TYPE_PRECISION (type
)
3102 >= TYPE_PRECISION (TREE_TYPE (expr
->u
.nary
->op
[0])))
3103 && SSA_NAME_RANGE_INFO (expr
->u
.nary
->op
[0]))
3106 if (get_range_info (expr
->u
.nary
->op
[0], &min
, &max
) == VR_RANGE
3107 && !wi::neg_p (min
, SIGNED
)
3108 && !wi::neg_p (max
, SIGNED
))
3109 /* Just handle extension and sign-changes of all-positive ranges. */
3110 set_range_info (temp
,
3111 SSA_NAME_RANGE_TYPE (expr
->u
.nary
->op
[0]),
3112 wide_int_storage::from (min
, TYPE_PRECISION (type
),
3114 wide_int_storage::from (max
, TYPE_PRECISION (type
),
3118 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3120 fprintf (dump_file
, "Created phi ");
3121 print_gimple_stmt (dump_file
, phi
, 0);
3122 fprintf (dump_file
, " in block %d (%04d)\n", block
->index
, val
);
3130 /* Perform insertion of partially redundant or hoistable values.
3131 For BLOCK, do the following:
3132 1. Propagate the NEW_SETS of the dominator into the current block.
3133 If the block has multiple predecessors,
3134 2a. Iterate over the ANTIC expressions for the block to see if
3135 any of them are partially redundant.
3136 2b. If so, insert them into the necessary predecessors to make
3137 the expression fully redundant.
3138 2c. Insert a new PHI merging the values of the predecessors.
3139 2d. Insert the new PHI, and the new expressions, into the
3141 If the block has multiple successors,
3142 3a. Iterate over the ANTIC values for the block to see if
3143 any of them are good candidates for hoisting.
3144 3b. If so, insert expressions computing the values in BLOCK,
3145 and add the new expressions into the NEW_SETS set.
3146 4. Recursively call ourselves on the dominator children of BLOCK.
3148 Steps 1, 2a, and 4 are done by insert_aux. 2b, 2c and 2d are done by
3149 do_pre_regular_insertion and do_partial_insertion. 3a and 3b are
3150 done in do_hoist_insertion.
3154 do_pre_regular_insertion (basic_block block
, basic_block dom
)
3156 bool new_stuff
= false;
3157 vec
<pre_expr
> exprs
;
3159 auto_vec
<pre_expr
> avail
;
3162 exprs
= sorted_array_from_bitmap_set (ANTIC_IN (block
));
3163 avail
.safe_grow (EDGE_COUNT (block
->preds
));
3165 FOR_EACH_VEC_ELT (exprs
, i
, expr
)
3167 if (expr
->kind
== NARY
3168 || expr
->kind
== REFERENCE
)
3171 bool by_some
= false;
3172 bool cant_insert
= false;
3173 bool all_same
= true;
3174 pre_expr first_s
= NULL
;
3177 pre_expr eprime
= NULL
;
3179 pre_expr edoubleprime
= NULL
;
3180 bool do_insertion
= false;
3182 val
= get_expr_value_id (expr
);
3183 if (bitmap_set_contains_value (PHI_GEN (block
), val
))
3185 if (bitmap_set_contains_value (AVAIL_OUT (dom
), val
))
3187 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3189 fprintf (dump_file
, "Found fully redundant value: ");
3190 print_pre_expr (dump_file
, expr
);
3191 fprintf (dump_file
, "\n");
3196 FOR_EACH_EDGE (pred
, ei
, block
->preds
)
3198 unsigned int vprime
;
3200 /* We should never run insertion for the exit block
3201 and so not come across fake pred edges. */
3202 gcc_assert (!(pred
->flags
& EDGE_FAKE
));
3204 /* We are looking at ANTIC_OUT of bprime. */
3205 eprime
= phi_translate (expr
, ANTIC_IN (block
), NULL
,
3208 /* eprime will generally only be NULL if the
3209 value of the expression, translated
3210 through the PHI for this predecessor, is
3211 undefined. If that is the case, we can't
3212 make the expression fully redundant,
3213 because its value is undefined along a
3214 predecessor path. We can thus break out
3215 early because it doesn't matter what the
3216 rest of the results are. */
3219 avail
[pred
->dest_idx
] = NULL
;
3224 vprime
= get_expr_value_id (eprime
);
3225 edoubleprime
= bitmap_find_leader (AVAIL_OUT (bprime
),
3227 if (edoubleprime
== NULL
)
3229 avail
[pred
->dest_idx
] = eprime
;
3234 avail
[pred
->dest_idx
] = edoubleprime
;
3236 /* We want to perform insertions to remove a redundancy on
3237 a path in the CFG we want to optimize for speed. */
3238 if (optimize_edge_for_speed_p (pred
))
3239 do_insertion
= true;
3240 if (first_s
== NULL
)
3241 first_s
= edoubleprime
;
3242 else if (!pre_expr_d::equal (first_s
, edoubleprime
))
3246 /* If we can insert it, it's not the same value
3247 already existing along every predecessor, and
3248 it's defined by some predecessor, it is
3249 partially redundant. */
3250 if (!cant_insert
&& !all_same
&& by_some
)
3254 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3256 fprintf (dump_file
, "Skipping partial redundancy for "
3258 print_pre_expr (dump_file
, expr
);
3259 fprintf (dump_file
, " (%04d), no redundancy on to be "
3260 "optimized for speed edge\n", val
);
3263 else if (dbg_cnt (treepre_insert
))
3265 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3267 fprintf (dump_file
, "Found partial redundancy for "
3269 print_pre_expr (dump_file
, expr
);
3270 fprintf (dump_file
, " (%04d)\n",
3271 get_expr_value_id (expr
));
3273 if (insert_into_preds_of_block (block
,
3274 get_expression_id (expr
),
3279 /* If all edges produce the same value and that value is
3280 an invariant, then the PHI has the same value on all
3281 edges. Note this. */
3282 else if (!cant_insert
&& all_same
)
3284 gcc_assert (edoubleprime
->kind
== CONSTANT
3285 || edoubleprime
->kind
== NAME
);
3287 tree temp
= make_temp_ssa_name (get_expr_type (expr
),
3290 = gimple_build_assign (temp
,
3291 edoubleprime
->kind
== CONSTANT
?
3292 PRE_EXPR_CONSTANT (edoubleprime
) :
3293 PRE_EXPR_NAME (edoubleprime
));
3294 gimple_stmt_iterator gsi
= gsi_after_labels (block
);
3295 gsi_insert_before (&gsi
, assign
, GSI_NEW_STMT
);
3297 VN_INFO_GET (temp
)->value_id
= val
;
3298 VN_INFO (temp
)->valnum
= sccvn_valnum_from_value_id (val
);
3299 if (VN_INFO (temp
)->valnum
== NULL_TREE
)
3300 VN_INFO (temp
)->valnum
= temp
;
3301 bitmap_set_bit (inserted_exprs
, SSA_NAME_VERSION (temp
));
3302 pre_expr newe
= get_or_alloc_expr_for_name (temp
);
3303 add_to_value (val
, newe
);
3304 bitmap_value_replace_in_set (AVAIL_OUT (block
), newe
);
3305 bitmap_insert_into_set (NEW_SETS (block
), newe
);
3315 /* Perform insertion for partially anticipatable expressions. There
3316 is only one case we will perform insertion for these. This case is
3317 if the expression is partially anticipatable, and fully available.
3318 In this case, we know that putting it earlier will enable us to
3319 remove the later computation. */
3322 do_pre_partial_partial_insertion (basic_block block
, basic_block dom
)
3324 bool new_stuff
= false;
3325 vec
<pre_expr
> exprs
;
3327 auto_vec
<pre_expr
> avail
;
3330 exprs
= sorted_array_from_bitmap_set (PA_IN (block
));
3331 avail
.safe_grow (EDGE_COUNT (block
->preds
));
3333 FOR_EACH_VEC_ELT (exprs
, i
, expr
)
3335 if (expr
->kind
== NARY
3336 || expr
->kind
== REFERENCE
)
3340 bool cant_insert
= false;
3343 pre_expr eprime
= NULL
;
3346 val
= get_expr_value_id (expr
);
3347 if (bitmap_set_contains_value (PHI_GEN (block
), val
))
3349 if (bitmap_set_contains_value (AVAIL_OUT (dom
), val
))
3352 FOR_EACH_EDGE (pred
, ei
, block
->preds
)
3354 unsigned int vprime
;
3355 pre_expr edoubleprime
;
3357 /* We should never run insertion for the exit block
3358 and so not come across fake pred edges. */
3359 gcc_assert (!(pred
->flags
& EDGE_FAKE
));
3361 eprime
= phi_translate (expr
, ANTIC_IN (block
),
3365 /* eprime will generally only be NULL if the
3366 value of the expression, translated
3367 through the PHI for this predecessor, is
3368 undefined. If that is the case, we can't
3369 make the expression fully redundant,
3370 because its value is undefined along a
3371 predecessor path. We can thus break out
3372 early because it doesn't matter what the
3373 rest of the results are. */
3376 avail
[pred
->dest_idx
] = NULL
;
3381 vprime
= get_expr_value_id (eprime
);
3382 edoubleprime
= bitmap_find_leader (AVAIL_OUT (bprime
), vprime
);
3383 avail
[pred
->dest_idx
] = edoubleprime
;
3384 if (edoubleprime
== NULL
)
3391 /* If we can insert it, it's not the same value
3392 already existing along every predecessor, and
3393 it's defined by some predecessor, it is
3394 partially redundant. */
3395 if (!cant_insert
&& by_all
)
3398 bool do_insertion
= false;
3400 /* Insert only if we can remove a later expression on a path
3401 that we want to optimize for speed.
3402 The phi node that we will be inserting in BLOCK is not free,
3403 and inserting it for the sake of !optimize_for_speed successor
3404 may cause regressions on the speed path. */
3405 FOR_EACH_EDGE (succ
, ei
, block
->succs
)
3407 if (bitmap_set_contains_value (PA_IN (succ
->dest
), val
)
3408 || bitmap_set_contains_value (ANTIC_IN (succ
->dest
), val
))
3410 if (optimize_edge_for_speed_p (succ
))
3411 do_insertion
= true;
3417 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3419 fprintf (dump_file
, "Skipping partial partial redundancy "
3421 print_pre_expr (dump_file
, expr
);
3422 fprintf (dump_file
, " (%04d), not (partially) anticipated "
3423 "on any to be optimized for speed edges\n", val
);
3426 else if (dbg_cnt (treepre_insert
))
3428 pre_stats
.pa_insert
++;
3429 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3431 fprintf (dump_file
, "Found partial partial redundancy "
3433 print_pre_expr (dump_file
, expr
);
3434 fprintf (dump_file
, " (%04d)\n",
3435 get_expr_value_id (expr
));
3437 if (insert_into_preds_of_block (block
,
3438 get_expression_id (expr
),
3450 /* Insert expressions in BLOCK to compute hoistable values up.
3451 Return TRUE if something was inserted, otherwise return FALSE.
3452 The caller has to make sure that BLOCK has at least two successors. */
3455 do_hoist_insertion (basic_block block
)
3459 bool new_stuff
= false;
3461 gimple_stmt_iterator last
;
3463 /* At least two successors, or else... */
3464 gcc_assert (EDGE_COUNT (block
->succs
) >= 2);
3466 /* Check that all successors of BLOCK are dominated by block.
3467 We could use dominated_by_p() for this, but actually there is a much
3468 quicker check: any successor that is dominated by BLOCK can't have
3469 more than one predecessor edge. */
3470 FOR_EACH_EDGE (e
, ei
, block
->succs
)
3471 if (! single_pred_p (e
->dest
))
3474 /* Determine the insertion point. If we cannot safely insert before
3475 the last stmt if we'd have to, bail out. */
3476 last
= gsi_last_bb (block
);
3477 if (!gsi_end_p (last
)
3478 && !is_ctrl_stmt (gsi_stmt (last
))
3479 && stmt_ends_bb_p (gsi_stmt (last
)))
3482 /* Compute the set of hoistable expressions from ANTIC_IN. First compute
3483 hoistable values. */
3484 bitmap_set hoistable_set
;
3486 /* A hoistable value must be in ANTIC_IN(block)
3487 but not in AVAIL_OUT(BLOCK). */
3488 bitmap_initialize (&hoistable_set
.values
, &grand_bitmap_obstack
);
3489 bitmap_and_compl (&hoistable_set
.values
,
3490 &ANTIC_IN (block
)->values
, &AVAIL_OUT (block
)->values
);
3492 /* Short-cut for a common case: hoistable_set is empty. */
3493 if (bitmap_empty_p (&hoistable_set
.values
))
3496 /* Compute which of the hoistable values is in AVAIL_OUT of
3497 at least one of the successors of BLOCK. */
3498 bitmap_head availout_in_some
;
3499 bitmap_initialize (&availout_in_some
, &grand_bitmap_obstack
);
3500 FOR_EACH_EDGE (e
, ei
, block
->succs
)
3501 /* Do not consider expressions solely because their availability
3502 on loop exits. They'd be ANTIC-IN throughout the whole loop
3503 and thus effectively hoisted across loops by combination of
3504 PRE and hoisting. */
3505 if (! loop_exit_edge_p (block
->loop_father
, e
))
3506 bitmap_ior_and_into (&availout_in_some
, &hoistable_set
.values
,
3507 &AVAIL_OUT (e
->dest
)->values
);
3508 bitmap_clear (&hoistable_set
.values
);
3510 /* Short-cut for a common case: availout_in_some is empty. */
3511 if (bitmap_empty_p (&availout_in_some
))
3514 /* Hack hoitable_set in-place so we can use sorted_array_from_bitmap_set. */
3515 hoistable_set
.values
= availout_in_some
;
3516 hoistable_set
.expressions
= ANTIC_IN (block
)->expressions
;
3518 /* Now finally construct the topological-ordered expression set. */
3519 vec
<pre_expr
> exprs
= sorted_array_from_bitmap_set (&hoistable_set
);
3521 bitmap_clear (&hoistable_set
.values
);
3523 /* If there are candidate values for hoisting, insert expressions
3524 strategically to make the hoistable expressions fully redundant. */
3526 FOR_EACH_VEC_ELT (exprs
, i
, expr
)
3528 /* While we try to sort expressions topologically above the
3529 sorting doesn't work out perfectly. Catch expressions we
3530 already inserted. */
3531 unsigned int value_id
= get_expr_value_id (expr
);
3532 if (bitmap_set_contains_value (AVAIL_OUT (block
), value_id
))
3534 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3537 "Already inserted expression for ");
3538 print_pre_expr (dump_file
, expr
);
3539 fprintf (dump_file
, " (%04d)\n", value_id
);
3544 /* OK, we should hoist this value. Perform the transformation. */
3545 pre_stats
.hoist_insert
++;
3546 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3549 "Inserting expression in block %d for code hoisting: ",
3551 print_pre_expr (dump_file
, expr
);
3552 fprintf (dump_file
, " (%04d)\n", value_id
);
3555 gimple_seq stmts
= NULL
;
3556 tree res
= create_expression_by_pieces (block
, expr
, &stmts
,
3557 get_expr_type (expr
));
3559 /* Do not return true if expression creation ultimately
3560 did not insert any statements. */
3561 if (gimple_seq_empty_p (stmts
))
3565 if (gsi_end_p (last
) || is_ctrl_stmt (gsi_stmt (last
)))
3566 gsi_insert_seq_before (&last
, stmts
, GSI_SAME_STMT
);
3568 gsi_insert_seq_after (&last
, stmts
, GSI_NEW_STMT
);
3571 /* Make sure to not return true if expression creation ultimately
3572 failed but also make sure to insert any stmts produced as they
3573 are tracked in inserted_exprs. */
3585 /* Do a dominator walk on the control flow graph, and insert computations
3586 of values as necessary for PRE and hoisting. */
3589 insert_aux (basic_block block
, bool do_pre
, bool do_hoist
)
3592 bool new_stuff
= false;
3597 dom
= get_immediate_dominator (CDI_DOMINATORS
, block
);
3602 bitmap_set_t newset
;
3604 /* First, update the AVAIL_OUT set with anything we may have
3605 inserted higher up in the dominator tree. */
3606 newset
= NEW_SETS (dom
);
3609 /* Note that we need to value_replace both NEW_SETS, and
3610 AVAIL_OUT. For both the case of NEW_SETS, the value may be
3611 represented by some non-simple expression here that we want
3612 to replace it with. */
3613 FOR_EACH_EXPR_ID_IN_SET (newset
, i
, bi
)
3615 pre_expr expr
= expression_for_id (i
);
3616 bitmap_value_replace_in_set (NEW_SETS (block
), expr
);
3617 bitmap_value_replace_in_set (AVAIL_OUT (block
), expr
);
3621 /* Insert expressions for partial redundancies. */
3622 if (do_pre
&& !single_pred_p (block
))
3624 new_stuff
|= do_pre_regular_insertion (block
, dom
);
3625 if (do_partial_partial
)
3626 new_stuff
|= do_pre_partial_partial_insertion (block
, dom
);
3629 /* Insert expressions for hoisting. */
3630 if (do_hoist
&& EDGE_COUNT (block
->succs
) >= 2)
3631 new_stuff
|= do_hoist_insertion (block
);
3634 for (son
= first_dom_son (CDI_DOMINATORS
, block
);
3636 son
= next_dom_son (CDI_DOMINATORS
, son
))
3638 new_stuff
|= insert_aux (son
, do_pre
, do_hoist
);
3644 /* Perform insertion of partially redundant and hoistable values. */
3649 bool new_stuff
= true;
3651 int num_iterations
= 0;
3653 FOR_ALL_BB_FN (bb
, cfun
)
3654 NEW_SETS (bb
) = bitmap_set_new ();
3659 if (dump_file
&& dump_flags
& TDF_DETAILS
)
3660 fprintf (dump_file
, "Starting insert iteration %d\n", num_iterations
);
3661 new_stuff
= insert_aux (ENTRY_BLOCK_PTR_FOR_FN (cfun
), flag_tree_pre
,
3662 flag_code_hoisting
);
3664 /* Clear the NEW sets before the next iteration. We have already
3665 fully propagated its contents. */
3667 FOR_ALL_BB_FN (bb
, cfun
)
3668 bitmap_set_free (NEW_SETS (bb
));
3670 statistics_histogram_event (cfun
, "insert iterations", num_iterations
);
3674 /* Compute the AVAIL set for all basic blocks.
3676 This function performs value numbering of the statements in each basic
3677 block. The AVAIL sets are built from information we glean while doing
3678 this value numbering, since the AVAIL sets contain only one entry per
3681 AVAIL_IN[BLOCK] = AVAIL_OUT[dom(BLOCK)].
3682 AVAIL_OUT[BLOCK] = AVAIL_IN[BLOCK] U PHI_GEN[BLOCK] U TMP_GEN[BLOCK]. */
3685 compute_avail (void)
3688 basic_block block
, son
;
3689 basic_block
*worklist
;
3694 /* We pretend that default definitions are defined in the entry block.
3695 This includes function arguments and the static chain decl. */
3696 FOR_EACH_SSA_NAME (i
, name
, cfun
)
3699 if (!SSA_NAME_IS_DEFAULT_DEF (name
)
3700 || has_zero_uses (name
)
3701 || virtual_operand_p (name
))
3704 e
= get_or_alloc_expr_for_name (name
);
3705 add_to_value (get_expr_value_id (e
), e
);
3706 bitmap_insert_into_set (TMP_GEN (ENTRY_BLOCK_PTR_FOR_FN (cfun
)), e
);
3707 bitmap_value_insert_into_set (AVAIL_OUT (ENTRY_BLOCK_PTR_FOR_FN (cfun
)),
3711 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3713 print_bitmap_set (dump_file
, TMP_GEN (ENTRY_BLOCK_PTR_FOR_FN (cfun
)),
3714 "tmp_gen", ENTRY_BLOCK
);
3715 print_bitmap_set (dump_file
, AVAIL_OUT (ENTRY_BLOCK_PTR_FOR_FN (cfun
)),
3716 "avail_out", ENTRY_BLOCK
);
3719 /* Allocate the worklist. */
3720 worklist
= XNEWVEC (basic_block
, n_basic_blocks_for_fn (cfun
));
3722 /* Seed the algorithm by putting the dominator children of the entry
3723 block on the worklist. */
3724 for (son
= first_dom_son (CDI_DOMINATORS
, ENTRY_BLOCK_PTR_FOR_FN (cfun
));
3726 son
= next_dom_son (CDI_DOMINATORS
, son
))
3727 worklist
[sp
++] = son
;
3729 BB_LIVE_VOP_ON_EXIT (ENTRY_BLOCK_PTR_FOR_FN (cfun
))
3730 = ssa_default_def (cfun
, gimple_vop (cfun
));
3732 /* Loop until the worklist is empty. */
3738 /* Pick a block from the worklist. */
3739 block
= worklist
[--sp
];
3741 /* Initially, the set of available values in BLOCK is that of
3742 its immediate dominator. */
3743 dom
= get_immediate_dominator (CDI_DOMINATORS
, block
);
3746 bitmap_set_copy (AVAIL_OUT (block
), AVAIL_OUT (dom
));
3747 BB_LIVE_VOP_ON_EXIT (block
) = BB_LIVE_VOP_ON_EXIT (dom
);
3750 /* Generate values for PHI nodes. */
3751 for (gphi_iterator gsi
= gsi_start_phis (block
); !gsi_end_p (gsi
);
3754 tree result
= gimple_phi_result (gsi
.phi ());
3756 /* We have no need for virtual phis, as they don't represent
3757 actual computations. */
3758 if (virtual_operand_p (result
))
3760 BB_LIVE_VOP_ON_EXIT (block
) = result
;
3764 pre_expr e
= get_or_alloc_expr_for_name (result
);
3765 add_to_value (get_expr_value_id (e
), e
);
3766 bitmap_value_insert_into_set (AVAIL_OUT (block
), e
);
3767 bitmap_insert_into_set (PHI_GEN (block
), e
);
3770 BB_MAY_NOTRETURN (block
) = 0;
3772 /* Now compute value numbers and populate value sets with all
3773 the expressions computed in BLOCK. */
3774 for (gimple_stmt_iterator gsi
= gsi_start_bb (block
); !gsi_end_p (gsi
);
3780 stmt
= gsi_stmt (gsi
);
3782 /* Cache whether the basic-block has any non-visible side-effect
3784 If this isn't a call or it is the last stmt in the
3785 basic-block then the CFG represents things correctly. */
3786 if (is_gimple_call (stmt
) && !stmt_ends_bb_p (stmt
))
3788 /* Non-looping const functions always return normally.
3789 Otherwise the call might not return or have side-effects
3790 that forbids hoisting possibly trapping expressions
3792 int flags
= gimple_call_flags (stmt
);
3793 if (!(flags
& ECF_CONST
)
3794 || (flags
& ECF_LOOPING_CONST_OR_PURE
))
3795 BB_MAY_NOTRETURN (block
) = 1;
3798 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, iter
, SSA_OP_DEF
)
3800 pre_expr e
= get_or_alloc_expr_for_name (op
);
3802 add_to_value (get_expr_value_id (e
), e
);
3803 bitmap_insert_into_set (TMP_GEN (block
), e
);
3804 bitmap_value_insert_into_set (AVAIL_OUT (block
), e
);
3807 if (gimple_vdef (stmt
))
3808 BB_LIVE_VOP_ON_EXIT (block
) = gimple_vdef (stmt
);
3810 if (gimple_has_side_effects (stmt
)
3811 || stmt_could_throw_p (stmt
)
3812 || is_gimple_debug (stmt
))
3815 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, iter
, SSA_OP_USE
)
3817 if (ssa_undefined_value_p (op
))
3819 pre_expr e
= get_or_alloc_expr_for_name (op
);
3820 bitmap_value_insert_into_set (EXP_GEN (block
), e
);
3823 switch (gimple_code (stmt
))
3831 vn_reference_s ref1
;
3832 pre_expr result
= NULL
;
3834 /* We can value number only calls to real functions. */
3835 if (gimple_call_internal_p (stmt
))
3838 vn_reference_lookup_call (as_a
<gcall
*> (stmt
), &ref
, &ref1
);
3842 /* If the value of the call is not invalidated in
3843 this block until it is computed, add the expression
3845 if (!gimple_vuse (stmt
)
3847 (SSA_NAME_DEF_STMT (gimple_vuse (stmt
))) == GIMPLE_PHI
3848 || gimple_bb (SSA_NAME_DEF_STMT
3849 (gimple_vuse (stmt
))) != block
)
3851 result
= pre_expr_pool
.allocate ();
3852 result
->kind
= REFERENCE
;
3854 PRE_EXPR_REFERENCE (result
) = ref
;
3856 get_or_alloc_expression_id (result
);
3857 add_to_value (get_expr_value_id (result
), result
);
3858 bitmap_value_insert_into_set (EXP_GEN (block
), result
);
3865 pre_expr result
= NULL
;
3866 switch (vn_get_stmt_kind (stmt
))
3870 enum tree_code code
= gimple_assign_rhs_code (stmt
);
3873 /* COND_EXPR and VEC_COND_EXPR are awkward in
3874 that they contain an embedded complex expression.
3875 Don't even try to shove those through PRE. */
3876 if (code
== COND_EXPR
3877 || code
== VEC_COND_EXPR
)
3880 vn_nary_op_lookup_stmt (stmt
, &nary
);
3884 /* If the NARY traps and there was a preceding
3885 point in the block that might not return avoid
3886 adding the nary to EXP_GEN. */
3887 if (BB_MAY_NOTRETURN (block
)
3888 && vn_nary_may_trap (nary
))
3891 result
= pre_expr_pool
.allocate ();
3892 result
->kind
= NARY
;
3894 PRE_EXPR_NARY (result
) = nary
;
3900 tree rhs1
= gimple_assign_rhs1 (stmt
);
3901 alias_set_type set
= get_alias_set (rhs1
);
3902 vec
<vn_reference_op_s
> operands
3903 = vn_reference_operands_for_lookup (rhs1
);
3905 vn_reference_lookup_pieces (gimple_vuse (stmt
), set
,
3907 operands
, &ref
, VN_WALK
);
3910 operands
.release ();
3914 /* If the value of the reference is not invalidated in
3915 this block until it is computed, add the expression
3917 if (gimple_vuse (stmt
))
3921 def_stmt
= SSA_NAME_DEF_STMT (gimple_vuse (stmt
));
3922 while (!gimple_nop_p (def_stmt
)
3923 && gimple_code (def_stmt
) != GIMPLE_PHI
3924 && gimple_bb (def_stmt
) == block
)
3926 if (stmt_may_clobber_ref_p
3927 (def_stmt
, gimple_assign_rhs1 (stmt
)))
3933 = SSA_NAME_DEF_STMT (gimple_vuse (def_stmt
));
3937 operands
.release ();
3942 /* If the load was value-numbered to another
3943 load make sure we do not use its expression
3944 for insertion if it wouldn't be a valid
3946 /* At the momemt we have a testcase
3947 for hoist insertion of aligned vs. misaligned
3948 variants in gcc.dg/torture/pr65270-1.c thus
3949 with just alignment to be considered we can
3950 simply replace the expression in the hashtable
3951 with the most conservative one. */
3952 vn_reference_op_t ref1
= &ref
->operands
.last ();
3953 while (ref1
->opcode
!= TARGET_MEM_REF
3954 && ref1
->opcode
!= MEM_REF
3955 && ref1
!= &ref
->operands
[0])
3957 vn_reference_op_t ref2
= &operands
.last ();
3958 while (ref2
->opcode
!= TARGET_MEM_REF
3959 && ref2
->opcode
!= MEM_REF
3960 && ref2
!= &operands
[0])
3962 if ((ref1
->opcode
== TARGET_MEM_REF
3963 || ref1
->opcode
== MEM_REF
)
3964 && (TYPE_ALIGN (ref1
->type
)
3965 > TYPE_ALIGN (ref2
->type
)))
3967 = build_aligned_type (ref1
->type
,
3968 TYPE_ALIGN (ref2
->type
));
3969 /* TBAA behavior is an obvious part so make sure
3970 that the hashtable one covers this as well
3971 by adjusting the ref alias set and its base. */
3973 || alias_set_subset_of (set
, ref
->set
))
3975 else if (alias_set_subset_of (ref
->set
, set
))
3978 if (ref1
->opcode
== MEM_REF
)
3980 = wide_int_to_tree (TREE_TYPE (ref2
->op0
),
3981 wi::to_wide (ref1
->op0
));
3984 = wide_int_to_tree (TREE_TYPE (ref2
->op2
),
3985 wi::to_wide (ref1
->op2
));
3990 if (ref1
->opcode
== MEM_REF
)
3992 = wide_int_to_tree (ptr_type_node
,
3993 wi::to_wide (ref1
->op0
));
3996 = wide_int_to_tree (ptr_type_node
,
3997 wi::to_wide (ref1
->op2
));
3999 operands
.release ();
4001 result
= pre_expr_pool
.allocate ();
4002 result
->kind
= REFERENCE
;
4004 PRE_EXPR_REFERENCE (result
) = ref
;
4012 get_or_alloc_expression_id (result
);
4013 add_to_value (get_expr_value_id (result
), result
);
4014 bitmap_value_insert_into_set (EXP_GEN (block
), result
);
4022 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4024 print_bitmap_set (dump_file
, EXP_GEN (block
),
4025 "exp_gen", block
->index
);
4026 print_bitmap_set (dump_file
, PHI_GEN (block
),
4027 "phi_gen", block
->index
);
4028 print_bitmap_set (dump_file
, TMP_GEN (block
),
4029 "tmp_gen", block
->index
);
4030 print_bitmap_set (dump_file
, AVAIL_OUT (block
),
4031 "avail_out", block
->index
);
4034 /* Put the dominator children of BLOCK on the worklist of blocks
4035 to compute available sets for. */
4036 for (son
= first_dom_son (CDI_DOMINATORS
, block
);
4038 son
= next_dom_son (CDI_DOMINATORS
, son
))
4039 worklist
[sp
++] = son
;
4046 /* Local state for the eliminate domwalk. */
4047 static vec
<gimple
*> el_to_remove
;
4048 static vec
<gimple
*> el_to_fixup
;
4049 static unsigned int el_todo
;
4050 static vec
<tree
> el_avail
;
4051 static vec
<tree
> el_avail_stack
;
4053 /* Return a leader for OP that is available at the current point of the
4054 eliminate domwalk. */
4057 eliminate_avail (tree op
)
4059 tree valnum
= VN_INFO (op
)->valnum
;
4060 if (TREE_CODE (valnum
) == SSA_NAME
)
4062 if (SSA_NAME_IS_DEFAULT_DEF (valnum
))
4064 if (el_avail
.length () > SSA_NAME_VERSION (valnum
))
4065 return el_avail
[SSA_NAME_VERSION (valnum
)];
4067 else if (is_gimple_min_invariant (valnum
))
4072 /* At the current point of the eliminate domwalk make OP available. */
4075 eliminate_push_avail (tree op
)
4077 tree valnum
= VN_INFO (op
)->valnum
;
4078 if (TREE_CODE (valnum
) == SSA_NAME
)
4080 if (el_avail
.length () <= SSA_NAME_VERSION (valnum
))
4081 el_avail
.safe_grow_cleared (SSA_NAME_VERSION (valnum
) + 1);
4083 if (el_avail
[SSA_NAME_VERSION (valnum
)])
4084 pushop
= el_avail
[SSA_NAME_VERSION (valnum
)];
4085 el_avail_stack
.safe_push (pushop
);
4086 el_avail
[SSA_NAME_VERSION (valnum
)] = op
;
4090 /* Insert the expression recorded by SCCVN for VAL at *GSI. Returns
4091 the leader for the expression if insertion was successful. */
4094 eliminate_insert (gimple_stmt_iterator
*gsi
, tree val
)
4096 /* We can insert a sequence with a single assignment only. */
4097 gimple_seq stmts
= VN_INFO (val
)->expr
;
4098 if (!gimple_seq_singleton_p (stmts
))
4100 gassign
*stmt
= dyn_cast
<gassign
*> (gimple_seq_first_stmt (stmts
));
4102 || (!CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (stmt
))
4103 && gimple_assign_rhs_code (stmt
) != VIEW_CONVERT_EXPR
4104 && gimple_assign_rhs_code (stmt
) != BIT_FIELD_REF
4105 && (gimple_assign_rhs_code (stmt
) != BIT_AND_EXPR
4106 || TREE_CODE (gimple_assign_rhs2 (stmt
)) != INTEGER_CST
)))
4109 tree op
= gimple_assign_rhs1 (stmt
);
4110 if (gimple_assign_rhs_code (stmt
) == VIEW_CONVERT_EXPR
4111 || gimple_assign_rhs_code (stmt
) == BIT_FIELD_REF
)
4112 op
= TREE_OPERAND (op
, 0);
4113 tree leader
= TREE_CODE (op
) == SSA_NAME
? eliminate_avail (op
) : op
;
4119 if (gimple_assign_rhs_code (stmt
) == BIT_FIELD_REF
)
4120 res
= gimple_build (&stmts
, BIT_FIELD_REF
,
4121 TREE_TYPE (val
), leader
,
4122 TREE_OPERAND (gimple_assign_rhs1 (stmt
), 1),
4123 TREE_OPERAND (gimple_assign_rhs1 (stmt
), 2));
4124 else if (gimple_assign_rhs_code (stmt
) == BIT_AND_EXPR
)
4125 res
= gimple_build (&stmts
, BIT_AND_EXPR
,
4126 TREE_TYPE (val
), leader
, gimple_assign_rhs2 (stmt
));
4128 res
= gimple_build (&stmts
, gimple_assign_rhs_code (stmt
),
4129 TREE_TYPE (val
), leader
);
4130 if (TREE_CODE (res
) != SSA_NAME
4131 || SSA_NAME_IS_DEFAULT_DEF (res
)
4132 || gimple_bb (SSA_NAME_DEF_STMT (res
)))
4134 gimple_seq_discard (stmts
);
4136 /* During propagation we have to treat SSA info conservatively
4137 and thus we can end up simplifying the inserted expression
4138 at elimination time to sth not defined in stmts. */
4139 /* But then this is a redundancy we failed to detect. Which means
4140 res now has two values. That doesn't play well with how
4141 we track availability here, so give up. */
4142 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4144 if (TREE_CODE (res
) == SSA_NAME
)
4145 res
= eliminate_avail (res
);
4148 fprintf (dump_file
, "Failed to insert expression for value ");
4149 print_generic_expr (dump_file
, val
);
4150 fprintf (dump_file
, " which is really fully redundant to ");
4151 print_generic_expr (dump_file
, res
);
4152 fprintf (dump_file
, "\n");
4160 gsi_insert_seq_before (gsi
, stmts
, GSI_SAME_STMT
);
4161 VN_INFO_GET (res
)->valnum
= val
;
4164 pre_stats
.insertions
++;
4165 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4167 fprintf (dump_file
, "Inserted ");
4168 print_gimple_stmt (dump_file
, SSA_NAME_DEF_STMT (res
), 0);
4174 class eliminate_dom_walker
: public dom_walker
4177 eliminate_dom_walker (cdi_direction direction
, bool do_pre_
)
4178 : dom_walker (direction
), do_pre (do_pre_
) {}
4180 virtual edge
before_dom_children (basic_block
);
4181 virtual void after_dom_children (basic_block
);
4186 /* Perform elimination for the basic-block B during the domwalk. */
4189 eliminate_dom_walker::before_dom_children (basic_block b
)
4192 el_avail_stack
.safe_push (NULL_TREE
);
4194 /* Skip unreachable blocks marked unreachable during the SCCVN domwalk. */
4197 FOR_EACH_EDGE (e
, ei
, b
->preds
)
4198 if (e
->flags
& EDGE_EXECUTABLE
)
4203 for (gphi_iterator gsi
= gsi_start_phis (b
); !gsi_end_p (gsi
);)
4205 gphi
*phi
= gsi
.phi ();
4206 tree res
= PHI_RESULT (phi
);
4208 if (virtual_operand_p (res
))
4214 tree sprime
= eliminate_avail (res
);
4218 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4220 fprintf (dump_file
, "Replaced redundant PHI node defining ");
4221 print_generic_expr (dump_file
, res
);
4222 fprintf (dump_file
, " with ");
4223 print_generic_expr (dump_file
, sprime
);
4224 fprintf (dump_file
, "\n");
4227 /* If we inserted this PHI node ourself, it's not an elimination. */
4229 && bitmap_bit_p (inserted_exprs
, SSA_NAME_VERSION (res
)))
4232 pre_stats
.eliminations
++;
4234 /* If we will propagate into all uses don't bother to do
4236 if (may_propagate_copy (res
, sprime
))
4238 /* Mark the PHI for removal. */
4239 el_to_remove
.safe_push (phi
);
4244 remove_phi_node (&gsi
, false);
4246 if (!useless_type_conversion_p (TREE_TYPE (res
), TREE_TYPE (sprime
)))
4247 sprime
= fold_convert (TREE_TYPE (res
), sprime
);
4248 gimple
*stmt
= gimple_build_assign (res
, sprime
);
4249 gimple_stmt_iterator gsi2
= gsi_after_labels (b
);
4250 gsi_insert_before (&gsi2
, stmt
, GSI_NEW_STMT
);
4254 eliminate_push_avail (res
);
4258 for (gimple_stmt_iterator gsi
= gsi_start_bb (b
);
4262 tree sprime
= NULL_TREE
;
4263 gimple
*stmt
= gsi_stmt (gsi
);
4264 tree lhs
= gimple_get_lhs (stmt
);
4265 if (lhs
&& TREE_CODE (lhs
) == SSA_NAME
4266 && !gimple_has_volatile_ops (stmt
)
4267 /* See PR43491. Do not replace a global register variable when
4268 it is a the RHS of an assignment. Do replace local register
4269 variables since gcc does not guarantee a local variable will
4270 be allocated in register.
4271 ??? The fix isn't effective here. This should instead
4272 be ensured by not value-numbering them the same but treating
4273 them like volatiles? */
4274 && !(gimple_assign_single_p (stmt
)
4275 && (TREE_CODE (gimple_assign_rhs1 (stmt
)) == VAR_DECL
4276 && DECL_HARD_REGISTER (gimple_assign_rhs1 (stmt
))
4277 && is_global_var (gimple_assign_rhs1 (stmt
)))))
4279 sprime
= eliminate_avail (lhs
);
4282 /* If there is no existing usable leader but SCCVN thinks
4283 it has an expression it wants to use as replacement,
4285 tree val
= VN_INFO (lhs
)->valnum
;
4287 && TREE_CODE (val
) == SSA_NAME
4288 && VN_INFO (val
)->needs_insertion
4289 && VN_INFO (val
)->expr
!= NULL
4290 && (sprime
= eliminate_insert (&gsi
, val
)) != NULL_TREE
)
4291 eliminate_push_avail (sprime
);
4294 /* If this now constitutes a copy duplicate points-to
4295 and range info appropriately. This is especially
4296 important for inserted code. See tree-ssa-copy.c
4297 for similar code. */
4299 && TREE_CODE (sprime
) == SSA_NAME
)
4301 basic_block sprime_b
= gimple_bb (SSA_NAME_DEF_STMT (sprime
));
4302 if (POINTER_TYPE_P (TREE_TYPE (lhs
))
4303 && VN_INFO_PTR_INFO (lhs
)
4304 && ! VN_INFO_PTR_INFO (sprime
))
4306 duplicate_ssa_name_ptr_info (sprime
,
4307 VN_INFO_PTR_INFO (lhs
));
4309 mark_ptr_info_alignment_unknown
4310 (SSA_NAME_PTR_INFO (sprime
));
4312 else if (INTEGRAL_TYPE_P (TREE_TYPE (lhs
))
4313 && VN_INFO_RANGE_INFO (lhs
)
4314 && ! VN_INFO_RANGE_INFO (sprime
)
4316 duplicate_ssa_name_range_info (sprime
,
4317 VN_INFO_RANGE_TYPE (lhs
),
4318 VN_INFO_RANGE_INFO (lhs
));
4321 /* Inhibit the use of an inserted PHI on a loop header when
4322 the address of the memory reference is a simple induction
4323 variable. In other cases the vectorizer won't do anything
4324 anyway (either it's loop invariant or a complicated
4327 && TREE_CODE (sprime
) == SSA_NAME
4329 && (flag_tree_loop_vectorize
|| flag_tree_parallelize_loops
> 1)
4330 && loop_outer (b
->loop_father
)
4331 && has_zero_uses (sprime
)
4332 && bitmap_bit_p (inserted_exprs
, SSA_NAME_VERSION (sprime
))
4333 && gimple_assign_load_p (stmt
))
4335 gimple
*def_stmt
= SSA_NAME_DEF_STMT (sprime
);
4336 basic_block def_bb
= gimple_bb (def_stmt
);
4337 if (gimple_code (def_stmt
) == GIMPLE_PHI
4338 && def_bb
->loop_father
->header
== def_bb
)
4340 loop_p loop
= def_bb
->loop_father
;
4344 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, iter
, SSA_OP_USE
)
4347 def_bb
= gimple_bb (SSA_NAME_DEF_STMT (op
));
4349 && flow_bb_inside_loop_p (loop
, def_bb
)
4350 && simple_iv (loop
, loop
, op
, &iv
, true))
4358 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4360 fprintf (dump_file
, "Not replacing ");
4361 print_gimple_expr (dump_file
, stmt
, 0);
4362 fprintf (dump_file
, " with ");
4363 print_generic_expr (dump_file
, sprime
);
4364 fprintf (dump_file
, " which would add a loop"
4365 " carried dependence to loop %d\n",
4368 /* Don't keep sprime available. */
4376 /* If we can propagate the value computed for LHS into
4377 all uses don't bother doing anything with this stmt. */
4378 if (may_propagate_copy (lhs
, sprime
))
4380 /* Mark it for removal. */
4381 el_to_remove
.safe_push (stmt
);
4383 /* ??? Don't count copy/constant propagations. */
4384 if (gimple_assign_single_p (stmt
)
4385 && (TREE_CODE (gimple_assign_rhs1 (stmt
)) == SSA_NAME
4386 || gimple_assign_rhs1 (stmt
) == sprime
))
4389 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4391 fprintf (dump_file
, "Replaced ");
4392 print_gimple_expr (dump_file
, stmt
, 0);
4393 fprintf (dump_file
, " with ");
4394 print_generic_expr (dump_file
, sprime
);
4395 fprintf (dump_file
, " in all uses of ");
4396 print_gimple_stmt (dump_file
, stmt
, 0);
4399 pre_stats
.eliminations
++;
4403 /* If this is an assignment from our leader (which
4404 happens in the case the value-number is a constant)
4405 then there is nothing to do. */
4406 if (gimple_assign_single_p (stmt
)
4407 && sprime
== gimple_assign_rhs1 (stmt
))
4410 /* Else replace its RHS. */
4411 bool can_make_abnormal_goto
4412 = is_gimple_call (stmt
)
4413 && stmt_can_make_abnormal_goto (stmt
);
4415 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4417 fprintf (dump_file
, "Replaced ");
4418 print_gimple_expr (dump_file
, stmt
, 0);
4419 fprintf (dump_file
, " with ");
4420 print_generic_expr (dump_file
, sprime
);
4421 fprintf (dump_file
, " in ");
4422 print_gimple_stmt (dump_file
, stmt
, 0);
4425 pre_stats
.eliminations
++;
4426 gimple
*orig_stmt
= stmt
;
4427 if (!useless_type_conversion_p (TREE_TYPE (lhs
),
4428 TREE_TYPE (sprime
)))
4429 sprime
= fold_convert (TREE_TYPE (lhs
), sprime
);
4430 tree vdef
= gimple_vdef (stmt
);
4431 tree vuse
= gimple_vuse (stmt
);
4432 propagate_tree_value_into_stmt (&gsi
, sprime
);
4433 stmt
= gsi_stmt (gsi
);
4435 if (vdef
!= gimple_vdef (stmt
))
4436 VN_INFO (vdef
)->valnum
= vuse
;
4438 /* If we removed EH side-effects from the statement, clean
4439 its EH information. */
4440 if (maybe_clean_or_replace_eh_stmt (orig_stmt
, stmt
))
4442 bitmap_set_bit (need_eh_cleanup
,
4443 gimple_bb (stmt
)->index
);
4444 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4445 fprintf (dump_file
, " Removed EH side-effects.\n");
4448 /* Likewise for AB side-effects. */
4449 if (can_make_abnormal_goto
4450 && !stmt_can_make_abnormal_goto (stmt
))
4452 bitmap_set_bit (need_ab_cleanup
,
4453 gimple_bb (stmt
)->index
);
4454 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4455 fprintf (dump_file
, " Removed AB side-effects.\n");
4462 /* If the statement is a scalar store, see if the expression
4463 has the same value number as its rhs. If so, the store is
4465 if (gimple_assign_single_p (stmt
)
4466 && !gimple_has_volatile_ops (stmt
)
4467 && !is_gimple_reg (gimple_assign_lhs (stmt
))
4468 && (TREE_CODE (gimple_assign_rhs1 (stmt
)) == SSA_NAME
4469 || is_gimple_min_invariant (gimple_assign_rhs1 (stmt
))))
4472 tree rhs
= gimple_assign_rhs1 (stmt
);
4473 vn_reference_t vnresult
;
4474 val
= vn_reference_lookup (lhs
, gimple_vuse (stmt
), VN_WALKREWRITE
,
4476 if (TREE_CODE (rhs
) == SSA_NAME
)
4477 rhs
= VN_INFO (rhs
)->valnum
;
4479 && operand_equal_p (val
, rhs
, 0))
4481 /* We can only remove the later store if the former aliases
4482 at least all accesses the later one does or if the store
4483 was to readonly memory storing the same value. */
4484 alias_set_type set
= get_alias_set (lhs
);
4486 || vnresult
->set
== set
4487 || alias_set_subset_of (set
, vnresult
->set
))
4489 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4491 fprintf (dump_file
, "Deleted redundant store ");
4492 print_gimple_stmt (dump_file
, stmt
, 0);
4495 /* Queue stmt for removal. */
4496 el_to_remove
.safe_push (stmt
);
4502 /* If this is a control statement value numbering left edges
4503 unexecuted on force the condition in a way consistent with
4505 if (gcond
*cond
= dyn_cast
<gcond
*> (stmt
))
4507 if ((EDGE_SUCC (b
, 0)->flags
& EDGE_EXECUTABLE
)
4508 ^ (EDGE_SUCC (b
, 1)->flags
& EDGE_EXECUTABLE
))
4510 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4512 fprintf (dump_file
, "Removing unexecutable edge from ");
4513 print_gimple_stmt (dump_file
, stmt
, 0);
4515 if (((EDGE_SUCC (b
, 0)->flags
& EDGE_TRUE_VALUE
) != 0)
4516 == ((EDGE_SUCC (b
, 0)->flags
& EDGE_EXECUTABLE
) != 0))
4517 gimple_cond_make_true (cond
);
4519 gimple_cond_make_false (cond
);
4521 el_todo
|= TODO_cleanup_cfg
;
4526 bool can_make_abnormal_goto
= stmt_can_make_abnormal_goto (stmt
);
4527 bool was_noreturn
= (is_gimple_call (stmt
)
4528 && gimple_call_noreturn_p (stmt
));
4529 tree vdef
= gimple_vdef (stmt
);
4530 tree vuse
= gimple_vuse (stmt
);
4532 /* If we didn't replace the whole stmt (or propagate the result
4533 into all uses), replace all uses on this stmt with their
4535 bool modified
= false;
4536 use_operand_p use_p
;
4538 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, iter
, SSA_OP_USE
)
4540 tree use
= USE_FROM_PTR (use_p
);
4541 /* ??? The call code above leaves stmt operands un-updated. */
4542 if (TREE_CODE (use
) != SSA_NAME
)
4544 tree sprime
= eliminate_avail (use
);
4545 if (sprime
&& sprime
!= use
4546 && may_propagate_copy (use
, sprime
)
4547 /* We substitute into debug stmts to avoid excessive
4548 debug temporaries created by removed stmts, but we need
4549 to avoid doing so for inserted sprimes as we never want
4550 to create debug temporaries for them. */
4552 || TREE_CODE (sprime
) != SSA_NAME
4553 || !is_gimple_debug (stmt
)
4554 || !bitmap_bit_p (inserted_exprs
, SSA_NAME_VERSION (sprime
))))
4556 propagate_value (use_p
, sprime
);
4561 /* Fold the stmt if modified, this canonicalizes MEM_REFs we propagated
4562 into which is a requirement for the IPA devirt machinery. */
4563 gimple
*old_stmt
= stmt
;
4566 /* If a formerly non-invariant ADDR_EXPR is turned into an
4567 invariant one it was on a separate stmt. */
4568 if (gimple_assign_single_p (stmt
)
4569 && TREE_CODE (gimple_assign_rhs1 (stmt
)) == ADDR_EXPR
)
4570 recompute_tree_invariant_for_addr_expr (gimple_assign_rhs1 (stmt
));
4571 gimple_stmt_iterator prev
= gsi
;
4573 if (fold_stmt (&gsi
))
4575 /* fold_stmt may have created new stmts inbetween
4576 the previous stmt and the folded stmt. Mark
4577 all defs created there as varying to not confuse
4578 the SCCVN machinery as we're using that even during
4580 if (gsi_end_p (prev
))
4581 prev
= gsi_start_bb (b
);
4584 if (gsi_stmt (prev
) != gsi_stmt (gsi
))
4589 FOR_EACH_SSA_TREE_OPERAND (def
, gsi_stmt (prev
),
4590 dit
, SSA_OP_ALL_DEFS
)
4591 /* As existing DEFs may move between stmts
4592 we have to guard VN_INFO_GET. */
4593 if (! has_VN_INFO (def
))
4594 VN_INFO_GET (def
)->valnum
= def
;
4595 if (gsi_stmt (prev
) == gsi_stmt (gsi
))
4601 stmt
= gsi_stmt (gsi
);
4602 /* In case we folded the stmt away schedule the NOP for removal. */
4603 if (gimple_nop_p (stmt
))
4604 el_to_remove
.safe_push (stmt
);
4607 /* Visit indirect calls and turn them into direct calls if
4608 possible using the devirtualization machinery. Do this before
4609 checking for required EH/abnormal/noreturn cleanup as devird
4610 may expose more of those. */
4611 if (gcall
*call_stmt
= dyn_cast
<gcall
*> (stmt
))
4613 tree fn
= gimple_call_fn (call_stmt
);
4615 && flag_devirtualize
4616 && virtual_method_call_p (fn
))
4618 tree otr_type
= obj_type_ref_class (fn
);
4619 unsigned HOST_WIDE_INT otr_tok
4620 = tree_to_uhwi (OBJ_TYPE_REF_TOKEN (fn
));
4622 ipa_polymorphic_call_context
context (current_function_decl
,
4623 fn
, stmt
, &instance
);
4624 context
.get_dynamic_type (instance
, OBJ_TYPE_REF_OBJECT (fn
),
4627 vec
<cgraph_node
*> targets
4628 = possible_polymorphic_call_targets (obj_type_ref_class (fn
),
4629 otr_tok
, context
, &final
);
4631 dump_possible_polymorphic_call_targets (dump_file
,
4632 obj_type_ref_class (fn
),
4634 if (final
&& targets
.length () <= 1 && dbg_cnt (devirt
))
4637 if (targets
.length () == 1)
4638 fn
= targets
[0]->decl
;
4640 fn
= builtin_decl_implicit (BUILT_IN_UNREACHABLE
);
4641 if (dump_enabled_p ())
4643 location_t loc
= gimple_location (stmt
);
4644 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS
, loc
,
4645 "converting indirect call to "
4647 lang_hooks
.decl_printable_name (fn
, 2));
4649 gimple_call_set_fndecl (call_stmt
, fn
);
4650 /* If changing the call to __builtin_unreachable
4651 or similar noreturn function, adjust gimple_call_fntype
4653 if (gimple_call_noreturn_p (call_stmt
)
4654 && VOID_TYPE_P (TREE_TYPE (TREE_TYPE (fn
)))
4655 && TYPE_ARG_TYPES (TREE_TYPE (fn
))
4656 && (TREE_VALUE (TYPE_ARG_TYPES (TREE_TYPE (fn
)))
4658 gimple_call_set_fntype (call_stmt
, TREE_TYPE (fn
));
4659 maybe_remove_unused_call_args (cfun
, call_stmt
);
4667 /* When changing a call into a noreturn call, cfg cleanup
4668 is needed to fix up the noreturn call. */
4670 && is_gimple_call (stmt
) && gimple_call_noreturn_p (stmt
))
4671 el_to_fixup
.safe_push (stmt
);
4672 /* When changing a condition or switch into one we know what
4673 edge will be executed, schedule a cfg cleanup. */
4674 if ((gimple_code (stmt
) == GIMPLE_COND
4675 && (gimple_cond_true_p (as_a
<gcond
*> (stmt
))
4676 || gimple_cond_false_p (as_a
<gcond
*> (stmt
))))
4677 || (gimple_code (stmt
) == GIMPLE_SWITCH
4678 && TREE_CODE (gimple_switch_index
4679 (as_a
<gswitch
*> (stmt
))) == INTEGER_CST
))
4680 el_todo
|= TODO_cleanup_cfg
;
4681 /* If we removed EH side-effects from the statement, clean
4682 its EH information. */
4683 if (maybe_clean_or_replace_eh_stmt (old_stmt
, stmt
))
4685 bitmap_set_bit (need_eh_cleanup
,
4686 gimple_bb (stmt
)->index
);
4687 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4688 fprintf (dump_file
, " Removed EH side-effects.\n");
4690 /* Likewise for AB side-effects. */
4691 if (can_make_abnormal_goto
4692 && !stmt_can_make_abnormal_goto (stmt
))
4694 bitmap_set_bit (need_ab_cleanup
,
4695 gimple_bb (stmt
)->index
);
4696 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4697 fprintf (dump_file
, " Removed AB side-effects.\n");
4700 if (vdef
!= gimple_vdef (stmt
))
4701 VN_INFO (vdef
)->valnum
= vuse
;
4704 /* Make new values available - for fully redundant LHS we
4705 continue with the next stmt above and skip this. */
4707 FOR_EACH_SSA_DEF_OPERAND (defp
, stmt
, iter
, SSA_OP_DEF
)
4708 eliminate_push_avail (DEF_FROM_PTR (defp
));
4711 /* Replace destination PHI arguments. */
4712 FOR_EACH_EDGE (e
, ei
, b
->succs
)
4713 if (e
->flags
& EDGE_EXECUTABLE
)
4714 for (gphi_iterator gsi
= gsi_start_phis (e
->dest
);
4718 gphi
*phi
= gsi
.phi ();
4719 use_operand_p use_p
= PHI_ARG_DEF_PTR_FROM_EDGE (phi
, e
);
4720 tree arg
= USE_FROM_PTR (use_p
);
4721 if (TREE_CODE (arg
) != SSA_NAME
4722 || virtual_operand_p (arg
))
4724 tree sprime
= eliminate_avail (arg
);
4725 if (sprime
&& may_propagate_copy (arg
, sprime
))
4726 propagate_value (use_p
, sprime
);
4731 /* Make no longer available leaders no longer available. */
4734 eliminate_dom_walker::after_dom_children (basic_block
)
4737 while ((entry
= el_avail_stack
.pop ()) != NULL_TREE
)
4739 tree valnum
= VN_INFO (entry
)->valnum
;
4740 tree old
= el_avail
[SSA_NAME_VERSION (valnum
)];
4742 el_avail
[SSA_NAME_VERSION (valnum
)] = NULL_TREE
;
4744 el_avail
[SSA_NAME_VERSION (valnum
)] = entry
;
4748 /* Eliminate fully redundant computations. */
4751 eliminate (bool do_pre
)
4753 need_eh_cleanup
= BITMAP_ALLOC (NULL
);
4754 need_ab_cleanup
= BITMAP_ALLOC (NULL
);
4756 el_to_remove
.create (0);
4757 el_to_fixup
.create (0);
4759 el_avail
.create (num_ssa_names
);
4760 el_avail_stack
.create (0);
4762 eliminate_dom_walker (CDI_DOMINATORS
,
4763 do_pre
).walk (cfun
->cfg
->x_entry_block_ptr
);
4765 el_avail
.release ();
4766 el_avail_stack
.release ();
4771 /* Perform CFG cleanups made necessary by elimination. */
4774 fini_eliminate (void)
4776 gimple_stmt_iterator gsi
;
4780 /* We cannot remove stmts during BB walk, especially not release SSA
4781 names there as this confuses the VN machinery. The stmts ending
4782 up in el_to_remove are either stores or simple copies.
4783 Remove stmts in reverse order to make debug stmt creation possible. */
4784 while (!el_to_remove
.is_empty ())
4786 stmt
= el_to_remove
.pop ();
4788 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4790 fprintf (dump_file
, "Removing dead stmt ");
4791 print_gimple_stmt (dump_file
, stmt
, 0, 0);
4794 gsi
= gsi_for_stmt (stmt
);
4795 if (gimple_code (stmt
) == GIMPLE_PHI
)
4796 remove_phi_node (&gsi
, true);
4799 basic_block bb
= gimple_bb (stmt
);
4800 unlink_stmt_vdef (stmt
);
4801 if (gsi_remove (&gsi
, true))
4802 bitmap_set_bit (need_eh_cleanup
, bb
->index
);
4803 if (is_gimple_call (stmt
) && stmt_can_make_abnormal_goto (stmt
))
4804 bitmap_set_bit (need_ab_cleanup
, bb
->index
);
4805 release_defs (stmt
);
4808 /* Removing a stmt may expose a forwarder block. */
4809 todo
|= TODO_cleanup_cfg
;
4811 el_to_remove
.release ();
4813 /* Fixup stmts that became noreturn calls. This may require splitting
4814 blocks and thus isn't possible during the dominator walk. Do this
4815 in reverse order so we don't inadvertedly remove a stmt we want to
4816 fixup by visiting a dominating now noreturn call first. */
4817 while (!el_to_fixup
.is_empty ())
4819 stmt
= el_to_fixup
.pop ();
4821 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4823 fprintf (dump_file
, "Fixing up noreturn call ");
4824 print_gimple_stmt (dump_file
, stmt
, 0);
4827 if (fixup_noreturn_call (stmt
))
4828 todo
|= TODO_cleanup_cfg
;
4830 el_to_fixup
.release ();
4832 bool do_eh_cleanup
= !bitmap_empty_p (need_eh_cleanup
);
4833 bool do_ab_cleanup
= !bitmap_empty_p (need_ab_cleanup
);
4836 gimple_purge_all_dead_eh_edges (need_eh_cleanup
);
4839 gimple_purge_all_dead_abnormal_call_edges (need_ab_cleanup
);
4841 BITMAP_FREE (need_eh_cleanup
);
4842 BITMAP_FREE (need_ab_cleanup
);
4844 if (do_eh_cleanup
|| do_ab_cleanup
)
4845 todo
|= TODO_cleanup_cfg
;
4849 /* Cheap DCE of a known set of possibly dead stmts.
4851 Because we don't follow exactly the standard PRE algorithm, and decide not
4852 to insert PHI nodes sometimes, and because value numbering of casts isn't
4853 perfect, we sometimes end up inserting dead code. This simple DCE-like
4854 pass removes any insertions we made that weren't actually used. */
4857 remove_dead_inserted_code (void)
4859 /* ??? Re-use inserted_exprs as worklist not only as initial set.
4860 This may end up removing non-inserted code as well. If we
4861 keep inserted_exprs unchanged we could restrict new worklist
4862 elements to members of inserted_exprs. */
4863 bitmap worklist
= inserted_exprs
;
4864 while (! bitmap_empty_p (worklist
))
4867 unsigned i
= bitmap_first_set_bit (worklist
);
4868 bitmap_clear_bit (worklist
, i
);
4870 tree def
= ssa_name (i
);
4871 /* Removed by somebody else or still in use. */
4872 if (! def
|| ! has_zero_uses (def
))
4875 gimple
*t
= SSA_NAME_DEF_STMT (def
);
4876 if (gimple_has_side_effects (t
))
4879 /* Add uses to the worklist. */
4881 use_operand_p use_p
;
4882 FOR_EACH_PHI_OR_STMT_USE (use_p
, t
, iter
, SSA_OP_USE
)
4884 tree use
= USE_FROM_PTR (use_p
);
4885 if (TREE_CODE (use
) == SSA_NAME
4886 && ! SSA_NAME_IS_DEFAULT_DEF (use
))
4887 bitmap_set_bit (worklist
, SSA_NAME_VERSION (use
));
4891 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4893 fprintf (dump_file
, "Removing unnecessary insertion:");
4894 print_gimple_stmt (dump_file
, t
, 0);
4896 gimple_stmt_iterator gsi
= gsi_for_stmt (t
);
4897 if (gimple_code (t
) == GIMPLE_PHI
)
4898 remove_phi_node (&gsi
, true);
4901 gsi_remove (&gsi
, true);
4908 /* Initialize data structures used by PRE. */
4915 next_expression_id
= 1;
4916 expressions
.create (0);
4917 expressions
.safe_push (NULL
);
4918 value_expressions
.create (get_max_value_id () + 1);
4919 value_expressions
.safe_grow_cleared (get_max_value_id () + 1);
4920 name_to_id
.create (0);
4922 inserted_exprs
= BITMAP_ALLOC (NULL
);
4924 connect_infinite_loops_to_exit ();
4925 memset (&pre_stats
, 0, sizeof (pre_stats
));
4927 alloc_aux_for_blocks (sizeof (struct bb_bitmap_sets
));
4929 calculate_dominance_info (CDI_DOMINATORS
);
4931 bitmap_obstack_initialize (&grand_bitmap_obstack
);
4932 phi_translate_table
= new hash_table
<expr_pred_trans_d
> (5110);
4933 expression_to_id
= new hash_table
<pre_expr_d
> (num_ssa_names
* 3);
4934 FOR_ALL_BB_FN (bb
, cfun
)
4936 EXP_GEN (bb
) = bitmap_set_new ();
4937 PHI_GEN (bb
) = bitmap_set_new ();
4938 TMP_GEN (bb
) = bitmap_set_new ();
4939 AVAIL_OUT (bb
) = bitmap_set_new ();
4944 /* Deallocate data structures used by PRE. */
4949 value_expressions
.release ();
4950 BITMAP_FREE (inserted_exprs
);
4951 bitmap_obstack_release (&grand_bitmap_obstack
);
4952 bitmap_set_pool
.release ();
4953 pre_expr_pool
.release ();
4954 delete phi_translate_table
;
4955 phi_translate_table
= NULL
;
4956 delete expression_to_id
;
4957 expression_to_id
= NULL
;
4958 name_to_id
.release ();
4960 free_aux_for_blocks ();
4965 const pass_data pass_data_pre
=
4967 GIMPLE_PASS
, /* type */
4969 OPTGROUP_NONE
, /* optinfo_flags */
4970 TV_TREE_PRE
, /* tv_id */
4971 ( PROP_cfg
| PROP_ssa
), /* properties_required */
4972 0, /* properties_provided */
4973 0, /* properties_destroyed */
4974 TODO_rebuild_alias
, /* todo_flags_start */
4975 0, /* todo_flags_finish */
4978 class pass_pre
: public gimple_opt_pass
4981 pass_pre (gcc::context
*ctxt
)
4982 : gimple_opt_pass (pass_data_pre
, ctxt
)
4985 /* opt_pass methods: */
4986 virtual bool gate (function
*)
4987 { return flag_tree_pre
!= 0 || flag_code_hoisting
!= 0; }
4988 virtual unsigned int execute (function
*);
4990 }; // class pass_pre
4993 pass_pre::execute (function
*fun
)
4995 unsigned int todo
= 0;
4997 do_partial_partial
=
4998 flag_tree_partial_pre
&& optimize_function_for_speed_p (fun
);
5000 /* This has to happen before SCCVN runs because
5001 loop_optimizer_init may create new phis, etc. */
5002 loop_optimizer_init (LOOPS_NORMAL
);
5003 split_critical_edges ();
5005 run_scc_vn (VN_WALK
);
5010 /* Collect and value number expressions computed in each basic block. */
5013 /* Insert can get quite slow on an incredibly large number of basic
5014 blocks due to some quadratic behavior. Until this behavior is
5015 fixed, don't run it when he have an incredibly large number of
5016 bb's. If we aren't going to run insert, there is no point in
5017 computing ANTIC, either, even though it's plenty fast. */
5018 if (n_basic_blocks_for_fn (fun
) < 4000)
5024 /* Make sure to remove fake edges before committing our inserts.
5025 This makes sure we don't end up with extra critical edges that
5026 we would need to split. */
5027 remove_fake_exit_edges ();
5028 gsi_commit_edge_inserts ();
5030 /* Eliminate folds statements which might (should not...) end up
5031 not keeping virtual operands up-to-date. */
5032 gcc_assert (!need_ssa_update_p (fun
));
5034 /* Remove all the redundant expressions. */
5035 todo
|= eliminate (true);
5037 statistics_counter_event (fun
, "Insertions", pre_stats
.insertions
);
5038 statistics_counter_event (fun
, "PA inserted", pre_stats
.pa_insert
);
5039 statistics_counter_event (fun
, "HOIST inserted", pre_stats
.hoist_insert
);
5040 statistics_counter_event (fun
, "New PHIs", pre_stats
.phis
);
5041 statistics_counter_event (fun
, "Eliminated", pre_stats
.eliminations
);
5043 clear_expression_ids ();
5046 todo
|= fini_eliminate ();
5047 remove_dead_inserted_code ();
5049 loop_optimizer_finalize ();
5051 /* Restore SSA info before tail-merging as that resets it as well. */
5052 scc_vn_restore_ssa_info ();
5054 /* TODO: tail_merge_optimize may merge all predecessors of a block, in which
5055 case we can merge the block with the remaining predecessor of the block.
5057 - call merge_blocks after each tail merge iteration
5058 - call merge_blocks after all tail merge iterations
5059 - mark TODO_cleanup_cfg when necessary
5060 - share the cfg cleanup with fini_pre. */
5061 todo
|= tail_merge_optimize (todo
);
5065 /* Tail merging invalidates the virtual SSA web, together with
5066 cfg-cleanup opportunities exposed by PRE this will wreck the
5067 SSA updating machinery. So make sure to run update-ssa
5068 manually, before eventually scheduling cfg-cleanup as part of
5070 update_ssa (TODO_update_ssa_only_virtuals
);
5078 make_pass_pre (gcc::context
*ctxt
)
5080 return new pass_pre (ctxt
);
5085 const pass_data pass_data_fre
=
5087 GIMPLE_PASS
, /* type */
5089 OPTGROUP_NONE
, /* optinfo_flags */
5090 TV_TREE_FRE
, /* tv_id */
5091 ( PROP_cfg
| PROP_ssa
), /* properties_required */
5092 0, /* properties_provided */
5093 0, /* properties_destroyed */
5094 0, /* todo_flags_start */
5095 0, /* todo_flags_finish */
5098 class pass_fre
: public gimple_opt_pass
5101 pass_fre (gcc::context
*ctxt
)
5102 : gimple_opt_pass (pass_data_fre
, ctxt
)
5105 /* opt_pass methods: */
5106 opt_pass
* clone () { return new pass_fre (m_ctxt
); }
5107 virtual bool gate (function
*) { return flag_tree_fre
!= 0; }
5108 virtual unsigned int execute (function
*);
5110 }; // class pass_fre
5113 pass_fre::execute (function
*fun
)
5115 unsigned int todo
= 0;
5117 run_scc_vn (VN_WALKREWRITE
);
5119 memset (&pre_stats
, 0, sizeof (pre_stats
));
5121 /* Remove all the redundant expressions. */
5122 todo
|= eliminate (false);
5124 todo
|= fini_eliminate ();
5126 scc_vn_restore_ssa_info ();
5129 statistics_counter_event (fun
, "Insertions", pre_stats
.insertions
);
5130 statistics_counter_event (fun
, "Eliminated", pre_stats
.eliminations
);
5138 make_pass_fre (gcc::context
*ctxt
)
5140 return new pass_fre (ctxt
);