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 void bitmap_set_and (bitmap_set_t
, bitmap_set_t
);
541 static bool bitmap_set_contains_value (bitmap_set_t
, unsigned int);
542 static void bitmap_insert_into_set (bitmap_set_t
, pre_expr
);
543 static void bitmap_insert_into_set_1 (bitmap_set_t
, pre_expr
,
545 static bitmap_set_t
bitmap_set_new (void);
546 static tree
create_expression_by_pieces (basic_block
, pre_expr
, gimple_seq
*,
548 static tree
find_or_generate_expression (basic_block
, tree
, gimple_seq
*);
549 static unsigned int get_expr_value_id (pre_expr
);
551 /* We can add and remove elements and entries to and from sets
552 and hash tables, so we use alloc pools for them. */
554 static object_allocator
<bitmap_set
> bitmap_set_pool ("Bitmap sets");
555 static bitmap_obstack grand_bitmap_obstack
;
557 /* Set of blocks with statements that have had their EH properties changed. */
558 static bitmap need_eh_cleanup
;
560 /* Set of blocks with statements that have had their AB properties changed. */
561 static bitmap need_ab_cleanup
;
563 /* A three tuple {e, pred, v} used to cache phi translations in the
564 phi_translate_table. */
566 typedef struct expr_pred_trans_d
: free_ptr_hash
<expr_pred_trans_d
>
568 /* The expression. */
571 /* The predecessor block along which we translated the expression. */
574 /* The value that resulted from the translation. */
577 /* The hashcode for the expression, pred pair. This is cached for
581 /* hash_table support. */
582 static inline hashval_t
hash (const expr_pred_trans_d
*);
583 static inline int equal (const expr_pred_trans_d
*, const expr_pred_trans_d
*);
584 } *expr_pred_trans_t
;
585 typedef const struct expr_pred_trans_d
*const_expr_pred_trans_t
;
588 expr_pred_trans_d::hash (const expr_pred_trans_d
*e
)
594 expr_pred_trans_d::equal (const expr_pred_trans_d
*ve1
,
595 const expr_pred_trans_d
*ve2
)
597 basic_block b1
= ve1
->pred
;
598 basic_block b2
= ve2
->pred
;
600 /* If they are not translations for the same basic block, they can't
604 return pre_expr_d::equal (ve1
->e
, ve2
->e
);
607 /* The phi_translate_table caches phi translations for a given
608 expression and predecessor. */
609 static hash_table
<expr_pred_trans_d
> *phi_translate_table
;
611 /* Add the tuple mapping from {expression E, basic block PRED} to
612 the phi translation table and return whether it pre-existed. */
615 phi_trans_add (expr_pred_trans_t
*entry
, pre_expr e
, basic_block pred
)
617 expr_pred_trans_t
*slot
;
618 expr_pred_trans_d tem
;
619 hashval_t hash
= iterative_hash_hashval_t (pre_expr_d::hash (e
),
624 slot
= phi_translate_table
->find_slot_with_hash (&tem
, hash
, INSERT
);
631 *entry
= *slot
= XNEW (struct expr_pred_trans_d
);
633 (*entry
)->pred
= pred
;
634 (*entry
)->hashcode
= hash
;
639 /* Add expression E to the expression set of value id V. */
642 add_to_value (unsigned int v
, pre_expr e
)
646 gcc_checking_assert (get_expr_value_id (e
) == v
);
648 if (v
>= value_expressions
.length ())
650 value_expressions
.safe_grow_cleared (v
+ 1);
653 set
= value_expressions
[v
];
656 set
= BITMAP_ALLOC (&grand_bitmap_obstack
);
657 value_expressions
[v
] = set
;
660 bitmap_set_bit (set
, get_or_alloc_expression_id (e
));
663 /* Create a new bitmap set and return it. */
666 bitmap_set_new (void)
668 bitmap_set_t ret
= bitmap_set_pool
.allocate ();
669 bitmap_initialize (&ret
->expressions
, &grand_bitmap_obstack
);
670 bitmap_initialize (&ret
->values
, &grand_bitmap_obstack
);
674 /* Return the value id for a PRE expression EXPR. */
677 get_expr_value_id (pre_expr expr
)
683 id
= get_constant_value_id (PRE_EXPR_CONSTANT (expr
));
686 id
= VN_INFO (PRE_EXPR_NAME (expr
))->value_id
;
689 id
= PRE_EXPR_NARY (expr
)->value_id
;
692 id
= PRE_EXPR_REFERENCE (expr
)->value_id
;
697 /* ??? We cannot assert that expr has a value-id (it can be 0), because
698 we assign value-ids only to expressions that have a result
699 in set_hashtable_value_ids. */
703 /* Return a SCCVN valnum (SSA name or constant) for the PRE value-id VAL. */
706 sccvn_valnum_from_value_id (unsigned int val
)
710 bitmap exprset
= value_expressions
[val
];
711 EXECUTE_IF_SET_IN_BITMAP (exprset
, 0, i
, bi
)
713 pre_expr vexpr
= expression_for_id (i
);
714 if (vexpr
->kind
== NAME
)
715 return VN_INFO (PRE_EXPR_NAME (vexpr
))->valnum
;
716 else if (vexpr
->kind
== CONSTANT
)
717 return PRE_EXPR_CONSTANT (vexpr
);
722 /* Remove an expression EXPR from a bitmapped set. */
725 bitmap_remove_from_set (bitmap_set_t set
, pre_expr expr
)
727 unsigned int val
= get_expr_value_id (expr
);
728 if (!value_id_constant_p (val
))
730 bitmap_clear_bit (&set
->values
, val
);
731 bitmap_clear_bit (&set
->expressions
, get_expression_id (expr
));
736 bitmap_insert_into_set_1 (bitmap_set_t set
, pre_expr expr
,
737 unsigned int val
, bool allow_constants
)
739 if (allow_constants
|| !value_id_constant_p (val
))
741 /* We specifically expect this and only this function to be able to
742 insert constants into a set. */
743 bitmap_set_bit (&set
->values
, val
);
744 bitmap_set_bit (&set
->expressions
, get_or_alloc_expression_id (expr
));
748 /* Insert an expression EXPR into a bitmapped set. */
751 bitmap_insert_into_set (bitmap_set_t set
, pre_expr expr
)
753 bitmap_insert_into_set_1 (set
, expr
, get_expr_value_id (expr
), false);
756 /* Copy a bitmapped set ORIG, into bitmapped set DEST. */
759 bitmap_set_copy (bitmap_set_t dest
, bitmap_set_t orig
)
761 bitmap_copy (&dest
->expressions
, &orig
->expressions
);
762 bitmap_copy (&dest
->values
, &orig
->values
);
766 /* Free memory used up by SET. */
768 bitmap_set_free (bitmap_set_t set
)
770 bitmap_clear (&set
->expressions
);
771 bitmap_clear (&set
->values
);
775 /* Generate an topological-ordered array of bitmap set SET. */
778 sorted_array_from_bitmap_set (bitmap_set_t set
)
781 bitmap_iterator bi
, bj
;
782 vec
<pre_expr
> result
;
784 /* Pre-allocate enough space for the array. */
785 result
.create (bitmap_count_bits (&set
->expressions
));
787 FOR_EACH_VALUE_ID_IN_SET (set
, i
, bi
)
789 /* The number of expressions having a given value is usually
790 relatively small. Thus, rather than making a vector of all
791 the expressions and sorting it by value-id, we walk the values
792 and check in the reverse mapping that tells us what expressions
793 have a given value, to filter those in our set. As a result,
794 the expressions are inserted in value-id order, which means
797 If this is somehow a significant lose for some cases, we can
798 choose which set to walk based on the set size. */
799 bitmap exprset
= value_expressions
[i
];
800 EXECUTE_IF_SET_IN_BITMAP (exprset
, 0, j
, bj
)
802 if (bitmap_bit_p (&set
->expressions
, j
))
803 result
.quick_push (expression_for_id (j
));
810 /* Perform bitmapped set operation DEST &= ORIG. */
813 bitmap_set_and (bitmap_set_t dest
, bitmap_set_t orig
)
820 bitmap_and_into (&dest
->values
, &orig
->values
);
822 unsigned int to_clear
= -1U;
823 FOR_EACH_EXPR_ID_IN_SET (dest
, i
, bi
)
827 bitmap_clear_bit (&dest
->expressions
, to_clear
);
830 pre_expr expr
= expression_for_id (i
);
831 unsigned int value_id
= get_expr_value_id (expr
);
832 if (!bitmap_bit_p (&dest
->values
, value_id
))
836 bitmap_clear_bit (&dest
->expressions
, to_clear
);
840 /* Subtract all values and expressions contained in ORIG from DEST. */
843 bitmap_set_subtract (bitmap_set_t dest
, bitmap_set_t orig
)
845 bitmap_set_t result
= bitmap_set_new ();
849 bitmap_and_compl (&result
->expressions
, &dest
->expressions
,
852 FOR_EACH_EXPR_ID_IN_SET (result
, i
, bi
)
854 pre_expr expr
= expression_for_id (i
);
855 unsigned int value_id
= get_expr_value_id (expr
);
856 bitmap_set_bit (&result
->values
, value_id
);
862 /* Subtract all the values in bitmap set B from bitmap set A. */
865 bitmap_set_subtract_values (bitmap_set_t a
, bitmap_set_t b
)
869 pre_expr to_remove
= NULL
;
870 FOR_EACH_EXPR_ID_IN_SET (a
, i
, bi
)
874 bitmap_remove_from_set (a
, to_remove
);
877 pre_expr expr
= expression_for_id (i
);
878 if (bitmap_set_contains_value (b
, get_expr_value_id (expr
)))
882 bitmap_remove_from_set (a
, to_remove
);
886 /* Return true if bitmapped set SET contains the value VALUE_ID. */
889 bitmap_set_contains_value (bitmap_set_t set
, unsigned int value_id
)
891 if (value_id_constant_p (value_id
))
894 if (!set
|| bitmap_empty_p (&set
->expressions
))
897 return bitmap_bit_p (&set
->values
, value_id
);
901 bitmap_set_contains_expr (bitmap_set_t set
, const pre_expr expr
)
903 return bitmap_bit_p (&set
->expressions
, get_expression_id (expr
));
906 /* Replace an instance of value LOOKFOR with expression EXPR in SET. */
909 bitmap_set_replace_value (bitmap_set_t set
, unsigned int lookfor
,
916 if (value_id_constant_p (lookfor
))
919 if (!bitmap_set_contains_value (set
, lookfor
))
922 /* The number of expressions having a given value is usually
923 significantly less than the total number of expressions in SET.
924 Thus, rather than check, for each expression in SET, whether it
925 has the value LOOKFOR, we walk the reverse mapping that tells us
926 what expressions have a given value, and see if any of those
927 expressions are in our set. For large testcases, this is about
928 5-10x faster than walking the bitmap. If this is somehow a
929 significant lose for some cases, we can choose which set to walk
930 based on the set size. */
931 exprset
= value_expressions
[lookfor
];
932 EXECUTE_IF_SET_IN_BITMAP (exprset
, 0, i
, bi
)
934 if (bitmap_clear_bit (&set
->expressions
, i
))
936 bitmap_set_bit (&set
->expressions
, get_expression_id (expr
));
944 /* Return true if two bitmap sets are equal. */
947 bitmap_set_equal (bitmap_set_t a
, bitmap_set_t b
)
949 return bitmap_equal_p (&a
->values
, &b
->values
);
952 /* Replace an instance of EXPR's VALUE with EXPR in SET if it exists,
953 and add it otherwise. */
956 bitmap_value_replace_in_set (bitmap_set_t set
, pre_expr expr
)
958 unsigned int val
= get_expr_value_id (expr
);
960 if (bitmap_set_contains_value (set
, val
))
961 bitmap_set_replace_value (set
, val
, expr
);
963 bitmap_insert_into_set (set
, expr
);
966 /* Insert EXPR into SET if EXPR's value is not already present in
970 bitmap_value_insert_into_set (bitmap_set_t set
, pre_expr expr
)
972 unsigned int val
= get_expr_value_id (expr
);
974 gcc_checking_assert (expr
->id
== get_or_alloc_expression_id (expr
));
976 /* Constant values are always considered to be part of the set. */
977 if (value_id_constant_p (val
))
980 /* If the value membership changed, add the expression. */
981 if (bitmap_set_bit (&set
->values
, val
))
982 bitmap_set_bit (&set
->expressions
, expr
->id
);
985 /* Print out EXPR to outfile. */
988 print_pre_expr (FILE *outfile
, const pre_expr expr
)
993 print_generic_expr (outfile
, PRE_EXPR_CONSTANT (expr
), 0);
996 print_generic_expr (outfile
, PRE_EXPR_NAME (expr
), 0);
1001 vn_nary_op_t nary
= PRE_EXPR_NARY (expr
);
1002 fprintf (outfile
, "{%s,", get_tree_code_name (nary
->opcode
));
1003 for (i
= 0; i
< nary
->length
; i
++)
1005 print_generic_expr (outfile
, nary
->op
[i
], 0);
1006 if (i
!= (unsigned) nary
->length
- 1)
1007 fprintf (outfile
, ",");
1009 fprintf (outfile
, "}");
1015 vn_reference_op_t vro
;
1017 vn_reference_t ref
= PRE_EXPR_REFERENCE (expr
);
1018 fprintf (outfile
, "{");
1020 ref
->operands
.iterate (i
, &vro
);
1023 bool closebrace
= false;
1024 if (vro
->opcode
!= SSA_NAME
1025 && TREE_CODE_CLASS (vro
->opcode
) != tcc_declaration
)
1027 fprintf (outfile
, "%s", get_tree_code_name (vro
->opcode
));
1030 fprintf (outfile
, "<");
1036 print_generic_expr (outfile
, vro
->op0
, 0);
1039 fprintf (outfile
, ",");
1040 print_generic_expr (outfile
, vro
->op1
, 0);
1044 fprintf (outfile
, ",");
1045 print_generic_expr (outfile
, vro
->op2
, 0);
1049 fprintf (outfile
, ">");
1050 if (i
!= ref
->operands
.length () - 1)
1051 fprintf (outfile
, ",");
1053 fprintf (outfile
, "}");
1056 fprintf (outfile
, "@");
1057 print_generic_expr (outfile
, ref
->vuse
, 0);
1063 void debug_pre_expr (pre_expr
);
1065 /* Like print_pre_expr but always prints to stderr. */
1067 debug_pre_expr (pre_expr e
)
1069 print_pre_expr (stderr
, e
);
1070 fprintf (stderr
, "\n");
1073 /* Print out SET to OUTFILE. */
1076 print_bitmap_set (FILE *outfile
, bitmap_set_t set
,
1077 const char *setname
, int blockindex
)
1079 fprintf (outfile
, "%s[%d] := { ", setname
, blockindex
);
1086 FOR_EACH_EXPR_ID_IN_SET (set
, i
, bi
)
1088 const pre_expr expr
= expression_for_id (i
);
1091 fprintf (outfile
, ", ");
1093 print_pre_expr (outfile
, expr
);
1095 fprintf (outfile
, " (%04d)", get_expr_value_id (expr
));
1098 fprintf (outfile
, " }\n");
1101 void debug_bitmap_set (bitmap_set_t
);
1104 debug_bitmap_set (bitmap_set_t set
)
1106 print_bitmap_set (stderr
, set
, "debug", 0);
1109 void debug_bitmap_sets_for (basic_block
);
1112 debug_bitmap_sets_for (basic_block bb
)
1114 print_bitmap_set (stderr
, AVAIL_OUT (bb
), "avail_out", bb
->index
);
1115 print_bitmap_set (stderr
, EXP_GEN (bb
), "exp_gen", bb
->index
);
1116 print_bitmap_set (stderr
, PHI_GEN (bb
), "phi_gen", bb
->index
);
1117 print_bitmap_set (stderr
, TMP_GEN (bb
), "tmp_gen", bb
->index
);
1118 print_bitmap_set (stderr
, ANTIC_IN (bb
), "antic_in", bb
->index
);
1119 if (do_partial_partial
)
1120 print_bitmap_set (stderr
, PA_IN (bb
), "pa_in", bb
->index
);
1121 print_bitmap_set (stderr
, NEW_SETS (bb
), "new_sets", bb
->index
);
1124 /* Print out the expressions that have VAL to OUTFILE. */
1127 print_value_expressions (FILE *outfile
, unsigned int val
)
1129 bitmap set
= value_expressions
[val
];
1134 sprintf (s
, "%04d", val
);
1135 x
.expressions
= *set
;
1136 print_bitmap_set (outfile
, &x
, s
, 0);
1142 debug_value_expressions (unsigned int val
)
1144 print_value_expressions (stderr
, val
);
1147 /* Given a CONSTANT, allocate a new CONSTANT type PRE_EXPR to
1151 get_or_alloc_expr_for_constant (tree constant
)
1153 unsigned int result_id
;
1154 unsigned int value_id
;
1155 struct pre_expr_d expr
;
1158 expr
.kind
= CONSTANT
;
1159 PRE_EXPR_CONSTANT (&expr
) = constant
;
1160 result_id
= lookup_expression_id (&expr
);
1162 return expression_for_id (result_id
);
1164 newexpr
= pre_expr_pool
.allocate ();
1165 newexpr
->kind
= CONSTANT
;
1166 PRE_EXPR_CONSTANT (newexpr
) = constant
;
1167 alloc_expression_id (newexpr
);
1168 value_id
= get_or_alloc_constant_value_id (constant
);
1169 add_to_value (value_id
, newexpr
);
1173 /* Get or allocate a pre_expr for a piece of GIMPLE, and return it.
1174 Currently only supports constants and SSA_NAMES. */
1176 get_or_alloc_expr_for (tree t
)
1178 if (TREE_CODE (t
) == SSA_NAME
)
1179 return get_or_alloc_expr_for_name (t
);
1180 else if (is_gimple_min_invariant (t
))
1181 return get_or_alloc_expr_for_constant (t
);
1185 /* Return the folded version of T if T, when folded, is a gimple
1186 min_invariant or an SSA name. Otherwise, return T. */
1189 fully_constant_expression (pre_expr e
)
1197 vn_nary_op_t nary
= PRE_EXPR_NARY (e
);
1198 tree res
= vn_nary_simplify (nary
);
1201 if (is_gimple_min_invariant (res
))
1202 return get_or_alloc_expr_for_constant (res
);
1203 if (TREE_CODE (res
) == SSA_NAME
)
1204 return get_or_alloc_expr_for_name (res
);
1209 vn_reference_t ref
= PRE_EXPR_REFERENCE (e
);
1211 if ((folded
= fully_constant_vn_reference_p (ref
)))
1212 return get_or_alloc_expr_for_constant (folded
);
1221 /* Translate the VUSE backwards through phi nodes in PHIBLOCK, so that
1222 it has the value it would have in BLOCK. Set *SAME_VALID to true
1223 in case the new vuse doesn't change the value id of the OPERANDS. */
1226 translate_vuse_through_block (vec
<vn_reference_op_s
> operands
,
1227 alias_set_type set
, tree type
, tree vuse
,
1228 basic_block phiblock
,
1229 basic_block block
, bool *same_valid
)
1231 gimple
*phi
= SSA_NAME_DEF_STMT (vuse
);
1238 if (gimple_bb (phi
) != phiblock
)
1241 use_oracle
= ao_ref_init_from_vn_reference (&ref
, set
, type
, operands
);
1243 /* Use the alias-oracle to find either the PHI node in this block,
1244 the first VUSE used in this block that is equivalent to vuse or
1245 the first VUSE which definition in this block kills the value. */
1246 if (gimple_code (phi
) == GIMPLE_PHI
)
1247 e
= find_edge (block
, phiblock
);
1248 else if (use_oracle
)
1249 while (!stmt_may_clobber_ref_p_1 (phi
, &ref
))
1251 vuse
= gimple_vuse (phi
);
1252 phi
= SSA_NAME_DEF_STMT (vuse
);
1253 if (gimple_bb (phi
) != phiblock
)
1255 if (gimple_code (phi
) == GIMPLE_PHI
)
1257 e
= find_edge (block
, phiblock
);
1268 bitmap visited
= NULL
;
1270 /* Try to find a vuse that dominates this phi node by skipping
1271 non-clobbering statements. */
1272 vuse
= get_continuation_for_phi (phi
, &ref
, &cnt
, &visited
, false,
1275 BITMAP_FREE (visited
);
1281 /* If we didn't find any, the value ID can't stay the same,
1282 but return the translated vuse. */
1283 *same_valid
= false;
1284 vuse
= PHI_ARG_DEF (phi
, e
->dest_idx
);
1286 /* ??? We would like to return vuse here as this is the canonical
1287 upmost vdef that this reference is associated with. But during
1288 insertion of the references into the hash tables we only ever
1289 directly insert with their direct gimple_vuse, hence returning
1290 something else would make us not find the other expression. */
1291 return PHI_ARG_DEF (phi
, e
->dest_idx
);
1297 /* Like bitmap_find_leader, but checks for the value existing in SET1 *or*
1298 SET2 *or* SET3. This is used to avoid making a set consisting of the union
1299 of PA_IN and ANTIC_IN during insert and phi-translation. */
1301 static inline pre_expr
1302 find_leader_in_sets (unsigned int val
, bitmap_set_t set1
, bitmap_set_t set2
,
1303 bitmap_set_t set3
= NULL
)
1307 result
= bitmap_find_leader (set1
, val
);
1308 if (!result
&& set2
)
1309 result
= bitmap_find_leader (set2
, val
);
1310 if (!result
&& set3
)
1311 result
= bitmap_find_leader (set3
, val
);
1315 /* Get the tree type for our PRE expression e. */
1318 get_expr_type (const pre_expr e
)
1323 return TREE_TYPE (PRE_EXPR_NAME (e
));
1325 return TREE_TYPE (PRE_EXPR_CONSTANT (e
));
1327 return PRE_EXPR_REFERENCE (e
)->type
;
1329 return PRE_EXPR_NARY (e
)->type
;
1334 /* Get a representative SSA_NAME for a given expression.
1335 Since all of our sub-expressions are treated as values, we require
1336 them to be SSA_NAME's for simplicity.
1337 Prior versions of GVNPRE used to use "value handles" here, so that
1338 an expression would be VH.11 + VH.10 instead of d_3 + e_6. In
1339 either case, the operands are really values (IE we do not expect
1340 them to be usable without finding leaders). */
1343 get_representative_for (const pre_expr e
)
1346 unsigned int value_id
= get_expr_value_id (e
);
1351 return VN_INFO (PRE_EXPR_NAME (e
))->valnum
;
1353 return PRE_EXPR_CONSTANT (e
);
1357 /* Go through all of the expressions representing this value
1358 and pick out an SSA_NAME. */
1361 bitmap exprs
= value_expressions
[value_id
];
1362 EXECUTE_IF_SET_IN_BITMAP (exprs
, 0, i
, bi
)
1364 pre_expr rep
= expression_for_id (i
);
1365 if (rep
->kind
== NAME
)
1366 return VN_INFO (PRE_EXPR_NAME (rep
))->valnum
;
1367 else if (rep
->kind
== CONSTANT
)
1368 return PRE_EXPR_CONSTANT (rep
);
1374 /* If we reached here we couldn't find an SSA_NAME. This can
1375 happen when we've discovered a value that has never appeared in
1376 the program as set to an SSA_NAME, as the result of phi translation.
1378 ??? We should be able to re-use this when we insert the statement
1380 name
= make_temp_ssa_name (get_expr_type (e
), gimple_build_nop (), "pretmp");
1381 VN_INFO_GET (name
)->value_id
= value_id
;
1382 VN_INFO (name
)->valnum
= name
;
1383 /* ??? For now mark this SSA name for release by SCCVN. */
1384 VN_INFO (name
)->needs_insertion
= true;
1385 add_to_value (value_id
, get_or_alloc_expr_for_name (name
));
1386 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1388 fprintf (dump_file
, "Created SSA_NAME representative ");
1389 print_generic_expr (dump_file
, name
, 0);
1390 fprintf (dump_file
, " for expression:");
1391 print_pre_expr (dump_file
, e
);
1392 fprintf (dump_file
, " (%04d)\n", value_id
);
1401 phi_translate (pre_expr expr
, bitmap_set_t set1
, bitmap_set_t set2
,
1402 basic_block pred
, basic_block phiblock
);
1404 /* Translate EXPR using phis in PHIBLOCK, so that it has the values of
1405 the phis in PRED. Return NULL if we can't find a leader for each part
1406 of the translated expression. */
1409 phi_translate_1 (pre_expr expr
, bitmap_set_t set1
, bitmap_set_t set2
,
1410 basic_block pred
, basic_block phiblock
)
1417 bool changed
= false;
1418 vn_nary_op_t nary
= PRE_EXPR_NARY (expr
);
1419 vn_nary_op_t newnary
= XALLOCAVAR (struct vn_nary_op_s
,
1420 sizeof_vn_nary_op (nary
->length
));
1421 memcpy (newnary
, nary
, sizeof_vn_nary_op (nary
->length
));
1423 for (i
= 0; i
< newnary
->length
; i
++)
1425 if (TREE_CODE (newnary
->op
[i
]) != SSA_NAME
)
1429 pre_expr leader
, result
;
1430 unsigned int op_val_id
= VN_INFO (newnary
->op
[i
])->value_id
;
1431 leader
= find_leader_in_sets (op_val_id
, set1
, set2
);
1432 result
= phi_translate (leader
, set1
, set2
, pred
, phiblock
);
1433 if (result
&& result
!= leader
)
1434 newnary
->op
[i
] = get_representative_for (result
);
1438 changed
|= newnary
->op
[i
] != nary
->op
[i
];
1444 unsigned int new_val_id
;
1446 PRE_EXPR_NARY (expr
) = newnary
;
1447 constant
= fully_constant_expression (expr
);
1448 PRE_EXPR_NARY (expr
) = nary
;
1449 if (constant
!= expr
)
1451 /* For non-CONSTANTs we have to make sure we can eventually
1452 insert the expression. Which means we need to have a
1454 if (constant
->kind
!= CONSTANT
)
1456 /* Do not allow simplifications to non-constants over
1457 backedges as this will likely result in a loop PHI node
1458 to be inserted and increased register pressure.
1459 See PR77498 - this avoids doing predcoms work in
1460 a less efficient way. */
1461 if (find_edge (pred
, phiblock
)->flags
& EDGE_DFS_BACK
)
1465 unsigned value_id
= get_expr_value_id (constant
);
1466 constant
= find_leader_in_sets (value_id
, set1
, set2
,
1476 tree result
= vn_nary_op_lookup_pieces (newnary
->length
,
1481 if (result
&& is_gimple_min_invariant (result
))
1482 return get_or_alloc_expr_for_constant (result
);
1484 expr
= pre_expr_pool
.allocate ();
1489 PRE_EXPR_NARY (expr
) = nary
;
1490 new_val_id
= nary
->value_id
;
1491 get_or_alloc_expression_id (expr
);
1495 new_val_id
= get_next_value_id ();
1496 value_expressions
.safe_grow_cleared (get_max_value_id () + 1);
1497 nary
= vn_nary_op_insert_pieces (newnary
->length
,
1501 result
, new_val_id
);
1502 PRE_EXPR_NARY (expr
) = nary
;
1503 get_or_alloc_expression_id (expr
);
1505 add_to_value (new_val_id
, expr
);
1513 vn_reference_t ref
= PRE_EXPR_REFERENCE (expr
);
1514 vec
<vn_reference_op_s
> operands
= ref
->operands
;
1515 tree vuse
= ref
->vuse
;
1516 tree newvuse
= vuse
;
1517 vec
<vn_reference_op_s
> newoperands
= vNULL
;
1518 bool changed
= false, same_valid
= true;
1520 vn_reference_op_t operand
;
1521 vn_reference_t newref
;
1523 for (i
= 0; operands
.iterate (i
, &operand
); i
++)
1528 tree type
= operand
->type
;
1529 vn_reference_op_s newop
= *operand
;
1530 op
[0] = operand
->op0
;
1531 op
[1] = operand
->op1
;
1532 op
[2] = operand
->op2
;
1533 for (n
= 0; n
< 3; ++n
)
1535 unsigned int op_val_id
;
1538 if (TREE_CODE (op
[n
]) != SSA_NAME
)
1540 /* We can't possibly insert these. */
1542 && !is_gimple_min_invariant (op
[n
]))
1546 op_val_id
= VN_INFO (op
[n
])->value_id
;
1547 leader
= find_leader_in_sets (op_val_id
, set1
, set2
);
1548 opresult
= phi_translate (leader
, set1
, set2
, pred
, phiblock
);
1549 if (opresult
&& opresult
!= leader
)
1551 tree name
= get_representative_for (opresult
);
1552 changed
|= name
!= op
[n
];
1560 newoperands
.release ();
1565 if (!newoperands
.exists ())
1566 newoperands
= operands
.copy ();
1567 /* We may have changed from an SSA_NAME to a constant */
1568 if (newop
.opcode
== SSA_NAME
&& TREE_CODE (op
[0]) != SSA_NAME
)
1569 newop
.opcode
= TREE_CODE (op
[0]);
1574 newoperands
[i
] = newop
;
1576 gcc_checking_assert (i
== operands
.length ());
1580 newvuse
= translate_vuse_through_block (newoperands
.exists ()
1581 ? newoperands
: operands
,
1582 ref
->set
, ref
->type
,
1583 vuse
, phiblock
, pred
,
1585 if (newvuse
== NULL_TREE
)
1587 newoperands
.release ();
1592 if (changed
|| newvuse
!= vuse
)
1594 unsigned int new_val_id
;
1597 tree result
= vn_reference_lookup_pieces (newvuse
, ref
->set
,
1599 newoperands
.exists ()
1600 ? newoperands
: operands
,
1603 newoperands
.release ();
1605 /* We can always insert constants, so if we have a partial
1606 redundant constant load of another type try to translate it
1607 to a constant of appropriate type. */
1608 if (result
&& is_gimple_min_invariant (result
))
1611 if (!useless_type_conversion_p (ref
->type
, TREE_TYPE (result
)))
1613 tem
= fold_unary (VIEW_CONVERT_EXPR
, ref
->type
, result
);
1614 if (tem
&& !is_gimple_min_invariant (tem
))
1618 return get_or_alloc_expr_for_constant (tem
);
1621 /* If we'd have to convert things we would need to validate
1622 if we can insert the translated expression. So fail
1623 here for now - we cannot insert an alias with a different
1624 type in the VN tables either, as that would assert. */
1626 && !useless_type_conversion_p (ref
->type
, TREE_TYPE (result
)))
1628 else if (!result
&& newref
1629 && !useless_type_conversion_p (ref
->type
, newref
->type
))
1631 newoperands
.release ();
1635 expr
= pre_expr_pool
.allocate ();
1636 expr
->kind
= REFERENCE
;
1641 PRE_EXPR_REFERENCE (expr
) = newref
;
1642 constant
= fully_constant_expression (expr
);
1643 if (constant
!= expr
)
1646 new_val_id
= newref
->value_id
;
1647 get_or_alloc_expression_id (expr
);
1651 if (changed
|| !same_valid
)
1653 new_val_id
= get_next_value_id ();
1654 value_expressions
.safe_grow_cleared
1655 (get_max_value_id () + 1);
1658 new_val_id
= ref
->value_id
;
1659 if (!newoperands
.exists ())
1660 newoperands
= operands
.copy ();
1661 newref
= vn_reference_insert_pieces (newvuse
, ref
->set
,
1664 result
, new_val_id
);
1665 newoperands
= vNULL
;
1666 PRE_EXPR_REFERENCE (expr
) = newref
;
1667 constant
= fully_constant_expression (expr
);
1668 if (constant
!= expr
)
1670 get_or_alloc_expression_id (expr
);
1672 add_to_value (new_val_id
, expr
);
1674 newoperands
.release ();
1681 tree name
= PRE_EXPR_NAME (expr
);
1682 gimple
*def_stmt
= SSA_NAME_DEF_STMT (name
);
1683 /* If the SSA name is defined by a PHI node in this block,
1685 if (gimple_code (def_stmt
) == GIMPLE_PHI
1686 && gimple_bb (def_stmt
) == phiblock
)
1688 edge e
= find_edge (pred
, gimple_bb (def_stmt
));
1689 tree def
= PHI_ARG_DEF (def_stmt
, e
->dest_idx
);
1691 /* Handle constant. */
1692 if (is_gimple_min_invariant (def
))
1693 return get_or_alloc_expr_for_constant (def
);
1695 return get_or_alloc_expr_for_name (def
);
1697 /* Otherwise return it unchanged - it will get removed if its
1698 value is not available in PREDs AVAIL_OUT set of expressions
1699 by the subtraction of TMP_GEN. */
1708 /* Wrapper around phi_translate_1 providing caching functionality. */
1711 phi_translate (pre_expr expr
, bitmap_set_t set1
, bitmap_set_t set2
,
1712 basic_block pred
, basic_block phiblock
)
1714 expr_pred_trans_t slot
= NULL
;
1720 /* Constants contain no values that need translation. */
1721 if (expr
->kind
== CONSTANT
)
1724 if (value_id_constant_p (get_expr_value_id (expr
)))
1727 /* Don't add translations of NAMEs as those are cheap to translate. */
1728 if (expr
->kind
!= NAME
)
1730 if (phi_trans_add (&slot
, expr
, pred
))
1732 /* Store NULL for the value we want to return in the case of
1738 phitrans
= phi_translate_1 (expr
, set1
, set2
, pred
, phiblock
);
1745 /* Remove failed translations again, they cause insert
1746 iteration to not pick up new opportunities reliably. */
1747 phi_translate_table
->remove_elt_with_hash (slot
, slot
->hashcode
);
1754 /* For each expression in SET, translate the values through phi nodes
1755 in PHIBLOCK using edge PHIBLOCK->PRED, and store the resulting
1756 expressions in DEST. */
1759 phi_translate_set (bitmap_set_t dest
, bitmap_set_t set
, basic_block pred
,
1760 basic_block phiblock
)
1762 vec
<pre_expr
> exprs
;
1766 if (gimple_seq_empty_p (phi_nodes (phiblock
)))
1768 bitmap_set_copy (dest
, set
);
1772 exprs
= sorted_array_from_bitmap_set (set
);
1773 FOR_EACH_VEC_ELT (exprs
, i
, expr
)
1775 pre_expr translated
;
1776 translated
= phi_translate (expr
, set
, NULL
, pred
, phiblock
);
1780 /* We might end up with multiple expressions from SET being
1781 translated to the same value. In this case we do not want
1782 to retain the NARY or REFERENCE expression but prefer a NAME
1783 which would be the leader. */
1784 if (translated
->kind
== NAME
)
1785 bitmap_value_replace_in_set (dest
, translated
);
1787 bitmap_value_insert_into_set (dest
, translated
);
1792 /* Find the leader for a value (i.e., the name representing that
1793 value) in a given set, and return it. Return NULL if no leader
1797 bitmap_find_leader (bitmap_set_t set
, unsigned int val
)
1799 if (value_id_constant_p (val
))
1803 bitmap exprset
= value_expressions
[val
];
1805 EXECUTE_IF_SET_IN_BITMAP (exprset
, 0, i
, bi
)
1807 pre_expr expr
= expression_for_id (i
);
1808 if (expr
->kind
== CONSTANT
)
1812 if (bitmap_set_contains_value (set
, val
))
1814 /* Rather than walk the entire bitmap of expressions, and see
1815 whether any of them has the value we are looking for, we look
1816 at the reverse mapping, which tells us the set of expressions
1817 that have a given value (IE value->expressions with that
1818 value) and see if any of those expressions are in our set.
1819 The number of expressions per value is usually significantly
1820 less than the number of expressions in the set. In fact, for
1821 large testcases, doing it this way is roughly 5-10x faster
1822 than walking the bitmap.
1823 If this is somehow a significant lose for some cases, we can
1824 choose which set to walk based on which set is smaller. */
1827 bitmap exprset
= value_expressions
[val
];
1829 EXECUTE_IF_AND_IN_BITMAP (exprset
, &set
->expressions
, 0, i
, bi
)
1830 return expression_for_id (i
);
1835 /* Determine if EXPR, a memory expression, is ANTIC_IN at the top of
1836 BLOCK by seeing if it is not killed in the block. Note that we are
1837 only determining whether there is a store that kills it. Because
1838 of the order in which clean iterates over values, we are guaranteed
1839 that altered operands will have caused us to be eliminated from the
1840 ANTIC_IN set already. */
1843 value_dies_in_block_x (pre_expr expr
, basic_block block
)
1845 tree vuse
= PRE_EXPR_REFERENCE (expr
)->vuse
;
1846 vn_reference_t refx
= PRE_EXPR_REFERENCE (expr
);
1848 gimple_stmt_iterator gsi
;
1849 unsigned id
= get_expression_id (expr
);
1856 /* Lookup a previously calculated result. */
1857 if (EXPR_DIES (block
)
1858 && bitmap_bit_p (EXPR_DIES (block
), id
* 2))
1859 return bitmap_bit_p (EXPR_DIES (block
), id
* 2 + 1);
1861 /* A memory expression {e, VUSE} dies in the block if there is a
1862 statement that may clobber e. If, starting statement walk from the
1863 top of the basic block, a statement uses VUSE there can be no kill
1864 inbetween that use and the original statement that loaded {e, VUSE},
1865 so we can stop walking. */
1866 ref
.base
= NULL_TREE
;
1867 for (gsi
= gsi_start_bb (block
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1869 tree def_vuse
, def_vdef
;
1870 def
= gsi_stmt (gsi
);
1871 def_vuse
= gimple_vuse (def
);
1872 def_vdef
= gimple_vdef (def
);
1874 /* Not a memory statement. */
1878 /* Not a may-def. */
1881 /* A load with the same VUSE, we're done. */
1882 if (def_vuse
== vuse
)
1888 /* Init ref only if we really need it. */
1889 if (ref
.base
== NULL_TREE
1890 && !ao_ref_init_from_vn_reference (&ref
, refx
->set
, refx
->type
,
1896 /* If the statement may clobber expr, it dies. */
1897 if (stmt_may_clobber_ref_p_1 (def
, &ref
))
1904 /* Remember the result. */
1905 if (!EXPR_DIES (block
))
1906 EXPR_DIES (block
) = BITMAP_ALLOC (&grand_bitmap_obstack
);
1907 bitmap_set_bit (EXPR_DIES (block
), id
* 2);
1909 bitmap_set_bit (EXPR_DIES (block
), id
* 2 + 1);
1915 /* Determine if OP is valid in SET1 U SET2, which it is when the union
1916 contains its value-id. */
1919 op_valid_in_sets (bitmap_set_t set1
, bitmap_set_t set2
, tree op
)
1921 if (op
&& TREE_CODE (op
) == SSA_NAME
)
1923 unsigned int value_id
= VN_INFO (op
)->value_id
;
1924 if (!(bitmap_set_contains_value (set1
, value_id
)
1925 || (set2
&& bitmap_set_contains_value (set2
, value_id
))))
1931 /* Determine if the expression EXPR is valid in SET1 U SET2.
1932 ONLY SET2 CAN BE NULL.
1933 This means that we have a leader for each part of the expression
1934 (if it consists of values), or the expression is an SSA_NAME.
1935 For loads/calls, we also see if the vuse is killed in this block. */
1938 valid_in_sets (bitmap_set_t set1
, bitmap_set_t set2
, pre_expr expr
)
1943 /* By construction all NAMEs are available. Non-available
1944 NAMEs are removed by subtracting TMP_GEN from the sets. */
1949 vn_nary_op_t nary
= PRE_EXPR_NARY (expr
);
1950 for (i
= 0; i
< nary
->length
; i
++)
1951 if (!op_valid_in_sets (set1
, set2
, nary
->op
[i
]))
1958 vn_reference_t ref
= PRE_EXPR_REFERENCE (expr
);
1959 vn_reference_op_t vro
;
1962 FOR_EACH_VEC_ELT (ref
->operands
, i
, vro
)
1964 if (!op_valid_in_sets (set1
, set2
, vro
->op0
)
1965 || !op_valid_in_sets (set1
, set2
, vro
->op1
)
1966 || !op_valid_in_sets (set1
, set2
, vro
->op2
))
1976 /* Clean the set of expressions that are no longer valid in SET1 or
1977 SET2. This means expressions that are made up of values we have no
1978 leaders for in SET1 or SET2. This version is used for partial
1979 anticipation, which means it is not valid in either ANTIC_IN or
1983 dependent_clean (bitmap_set_t set1
, bitmap_set_t set2
)
1985 vec
<pre_expr
> exprs
= sorted_array_from_bitmap_set (set1
);
1989 FOR_EACH_VEC_ELT (exprs
, i
, expr
)
1991 if (!valid_in_sets (set1
, set2
, expr
))
1992 bitmap_remove_from_set (set1
, expr
);
1997 /* Clean the set of expressions that are no longer valid in SET. This
1998 means expressions that are made up of values we have no leaders for
2002 clean (bitmap_set_t set
)
2004 vec
<pre_expr
> exprs
= sorted_array_from_bitmap_set (set
);
2008 FOR_EACH_VEC_ELT (exprs
, i
, expr
)
2010 if (!valid_in_sets (set
, NULL
, expr
))
2011 bitmap_remove_from_set (set
, expr
);
2016 /* Clean the set of expressions that are no longer valid in SET because
2017 they are clobbered in BLOCK or because they trap and may not be executed. */
2020 prune_clobbered_mems (bitmap_set_t set
, basic_block block
)
2024 pre_expr to_remove
= NULL
;
2026 FOR_EACH_EXPR_ID_IN_SET (set
, i
, bi
)
2028 /* Remove queued expr. */
2031 bitmap_remove_from_set (set
, to_remove
);
2035 pre_expr expr
= expression_for_id (i
);
2036 if (expr
->kind
== REFERENCE
)
2038 vn_reference_t ref
= PRE_EXPR_REFERENCE (expr
);
2041 gimple
*def_stmt
= SSA_NAME_DEF_STMT (ref
->vuse
);
2042 if (!gimple_nop_p (def_stmt
)
2043 && ((gimple_bb (def_stmt
) != block
2044 && !dominated_by_p (CDI_DOMINATORS
,
2045 block
, gimple_bb (def_stmt
)))
2046 || (gimple_bb (def_stmt
) == block
2047 && value_dies_in_block_x (expr
, block
))))
2051 else if (expr
->kind
== NARY
)
2053 vn_nary_op_t nary
= PRE_EXPR_NARY (expr
);
2054 /* If the NARY may trap make sure the block does not contain
2055 a possible exit point.
2056 ??? This is overly conservative if we translate AVAIL_OUT
2057 as the available expression might be after the exit point. */
2058 if (BB_MAY_NOTRETURN (block
)
2059 && vn_nary_may_trap (nary
))
2064 /* Remove queued expr. */
2066 bitmap_remove_from_set (set
, to_remove
);
2069 static sbitmap has_abnormal_preds
;
2071 /* Compute the ANTIC set for BLOCK.
2073 If succs(BLOCK) > 1 then
2074 ANTIC_OUT[BLOCK] = intersection of ANTIC_IN[b] for all succ(BLOCK)
2075 else if succs(BLOCK) == 1 then
2076 ANTIC_OUT[BLOCK] = phi_translate (ANTIC_IN[succ(BLOCK)])
2078 ANTIC_IN[BLOCK] = clean(ANTIC_OUT[BLOCK] U EXP_GEN[BLOCK] - TMP_GEN[BLOCK])
2082 compute_antic_aux (basic_block block
, bool block_has_abnormal_pred_edge
)
2084 bool changed
= false;
2085 bitmap_set_t S
, old
, ANTIC_OUT
;
2090 bool was_visited
= BB_VISITED (block
);
2092 old
= ANTIC_OUT
= S
= NULL
;
2093 BB_VISITED (block
) = 1;
2095 /* If any edges from predecessors are abnormal, antic_in is empty,
2097 if (block_has_abnormal_pred_edge
)
2098 goto maybe_dump_sets
;
2100 old
= ANTIC_IN (block
);
2101 ANTIC_OUT
= bitmap_set_new ();
2103 /* If the block has no successors, ANTIC_OUT is empty. */
2104 if (EDGE_COUNT (block
->succs
) == 0)
2106 /* If we have one successor, we could have some phi nodes to
2107 translate through. */
2108 else if (single_succ_p (block
))
2110 basic_block succ_bb
= single_succ (block
);
2111 gcc_assert (BB_VISITED (succ_bb
));
2112 phi_translate_set (ANTIC_OUT
, ANTIC_IN (succ_bb
), block
, succ_bb
);
2114 /* If we have multiple successors, we take the intersection of all of
2115 them. Note that in the case of loop exit phi nodes, we may have
2116 phis to translate through. */
2120 basic_block bprime
, first
= NULL
;
2122 auto_vec
<basic_block
> worklist (EDGE_COUNT (block
->succs
));
2123 FOR_EACH_EDGE (e
, ei
, block
->succs
)
2126 && BB_VISITED (e
->dest
))
2128 else if (BB_VISITED (e
->dest
))
2129 worklist
.quick_push (e
->dest
);
2132 /* Unvisited successors get their ANTIC_IN replaced by the
2133 maximal set to arrive at a maximum ANTIC_IN solution.
2134 We can ignore them in the intersection operation and thus
2135 need not explicitely represent that maximum solution. */
2136 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2137 fprintf (dump_file
, "ANTIC_IN is MAX on %d->%d\n",
2138 e
->src
->index
, e
->dest
->index
);
2142 /* Of multiple successors we have to have visited one already
2143 which is guaranteed by iteration order. */
2144 gcc_assert (first
!= NULL
);
2146 phi_translate_set (ANTIC_OUT
, ANTIC_IN (first
), block
, first
);
2148 FOR_EACH_VEC_ELT (worklist
, i
, bprime
)
2150 if (!gimple_seq_empty_p (phi_nodes (bprime
)))
2152 bitmap_set_t tmp
= bitmap_set_new ();
2153 phi_translate_set (tmp
, ANTIC_IN (bprime
), block
, bprime
);
2154 bitmap_set_and (ANTIC_OUT
, tmp
);
2155 bitmap_set_free (tmp
);
2158 bitmap_set_and (ANTIC_OUT
, ANTIC_IN (bprime
));
2162 /* Prune expressions that are clobbered in block and thus become
2163 invalid if translated from ANTIC_OUT to ANTIC_IN. */
2164 prune_clobbered_mems (ANTIC_OUT
, block
);
2166 /* Generate ANTIC_OUT - TMP_GEN. */
2167 S
= bitmap_set_subtract (ANTIC_OUT
, TMP_GEN (block
));
2169 /* Start ANTIC_IN with EXP_GEN - TMP_GEN. */
2170 ANTIC_IN (block
) = bitmap_set_subtract (EXP_GEN (block
),
2173 /* Then union in the ANTIC_OUT - TMP_GEN values,
2174 to get ANTIC_OUT U EXP_GEN - TMP_GEN */
2175 FOR_EACH_EXPR_ID_IN_SET (S
, bii
, bi
)
2176 bitmap_value_insert_into_set (ANTIC_IN (block
),
2177 expression_for_id (bii
));
2179 clean (ANTIC_IN (block
));
2181 if (!was_visited
|| !bitmap_set_equal (old
, ANTIC_IN (block
)))
2185 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2188 print_bitmap_set (dump_file
, ANTIC_OUT
, "ANTIC_OUT", block
->index
);
2191 fprintf (dump_file
, "[changed] ");
2192 print_bitmap_set (dump_file
, ANTIC_IN (block
), "ANTIC_IN",
2196 print_bitmap_set (dump_file
, S
, "S", block
->index
);
2199 bitmap_set_free (old
);
2201 bitmap_set_free (S
);
2203 bitmap_set_free (ANTIC_OUT
);
2207 /* Compute PARTIAL_ANTIC for BLOCK.
2209 If succs(BLOCK) > 1 then
2210 PA_OUT[BLOCK] = value wise union of PA_IN[b] + all ANTIC_IN not
2211 in ANTIC_OUT for all succ(BLOCK)
2212 else if succs(BLOCK) == 1 then
2213 PA_OUT[BLOCK] = phi_translate (PA_IN[succ(BLOCK)])
2215 PA_IN[BLOCK] = dependent_clean(PA_OUT[BLOCK] - TMP_GEN[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 (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 dependent_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
);
2361 /* We also anticipate nothing. */
2362 BB_VISITED (block
) = 1;
2366 /* While we are here, give empty ANTIC_IN sets to each block. */
2367 ANTIC_IN (block
) = bitmap_set_new ();
2368 if (do_partial_partial
)
2369 PA_IN (block
) = bitmap_set_new ();
2372 /* At the exit block we anticipate nothing. */
2373 BB_VISITED (EXIT_BLOCK_PTR_FOR_FN (cfun
)) = 1;
2375 /* For ANTIC computation we need a postorder that also guarantees that
2376 a block with a single successor is visited after its successor.
2377 RPO on the inverted CFG has this property. */
2378 int *postorder
= XNEWVEC (int, n_basic_blocks_for_fn (cfun
));
2379 int postorder_num
= inverted_post_order_compute (postorder
);
2381 auto_sbitmap
worklist (last_basic_block_for_fn (cfun
) + 1);
2382 bitmap_ones (worklist
);
2385 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2386 fprintf (dump_file
, "Starting iteration %d\n", num_iterations
);
2387 /* ??? We need to clear our PHI translation cache here as the
2388 ANTIC sets shrink and we restrict valid translations to
2389 those having operands with leaders in ANTIC. Same below
2390 for PA ANTIC computation. */
2393 for (i
= postorder_num
- 1; i
>= 0; i
--)
2395 if (bitmap_bit_p (worklist
, postorder
[i
]))
2397 basic_block block
= BASIC_BLOCK_FOR_FN (cfun
, postorder
[i
]);
2398 bitmap_clear_bit (worklist
, block
->index
);
2399 if (compute_antic_aux (block
,
2400 bitmap_bit_p (has_abnormal_preds
,
2403 FOR_EACH_EDGE (e
, ei
, block
->preds
)
2404 bitmap_set_bit (worklist
, e
->src
->index
);
2409 /* Theoretically possible, but *highly* unlikely. */
2410 gcc_checking_assert (num_iterations
< 500);
2413 statistics_histogram_event (cfun
, "compute_antic iterations",
2416 if (do_partial_partial
)
2418 /* For partial antic we ignore backedges and thus we do not need
2419 to perform any iteration when we process blocks in postorder. */
2420 postorder_num
= pre_and_rev_post_order_compute (NULL
, postorder
, 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
);
2435 /* Inserted expressions are placed onto this worklist, which is used
2436 for performing quick dead code elimination of insertions we made
2437 that didn't turn out to be necessary. */
2438 static bitmap inserted_exprs
;
2440 /* The actual worker for create_component_ref_by_pieces. */
2443 create_component_ref_by_pieces_1 (basic_block block
, vn_reference_t ref
,
2444 unsigned int *operand
, gimple_seq
*stmts
)
2446 vn_reference_op_t currop
= &ref
->operands
[*operand
];
2449 switch (currop
->opcode
)
2456 tree baseop
= create_component_ref_by_pieces_1 (block
, ref
, operand
,
2460 tree offset
= currop
->op0
;
2461 if (TREE_CODE (baseop
) == ADDR_EXPR
2462 && handled_component_p (TREE_OPERAND (baseop
, 0)))
2466 base
= get_addr_base_and_unit_offset (TREE_OPERAND (baseop
, 0),
2469 offset
= int_const_binop (PLUS_EXPR
, offset
,
2470 build_int_cst (TREE_TYPE (offset
),
2472 baseop
= build_fold_addr_expr (base
);
2474 genop
= build2 (MEM_REF
, currop
->type
, baseop
, offset
);
2475 MR_DEPENDENCE_CLIQUE (genop
) = currop
->clique
;
2476 MR_DEPENDENCE_BASE (genop
) = currop
->base
;
2477 REF_REVERSE_STORAGE_ORDER (genop
) = currop
->reverse
;
2481 case TARGET_MEM_REF
:
2483 tree genop0
= NULL_TREE
, genop1
= NULL_TREE
;
2484 vn_reference_op_t nextop
= &ref
->operands
[++*operand
];
2485 tree baseop
= create_component_ref_by_pieces_1 (block
, ref
, operand
,
2491 genop0
= find_or_generate_expression (block
, currop
->op0
, stmts
);
2497 genop1
= find_or_generate_expression (block
, nextop
->op0
, stmts
);
2501 genop
= build5 (TARGET_MEM_REF
, currop
->type
,
2502 baseop
, currop
->op2
, genop0
, currop
->op1
, genop1
);
2504 MR_DEPENDENCE_CLIQUE (genop
) = currop
->clique
;
2505 MR_DEPENDENCE_BASE (genop
) = currop
->base
;
2512 gcc_assert (is_gimple_min_invariant (currop
->op0
));
2518 case VIEW_CONVERT_EXPR
:
2520 tree genop0
= create_component_ref_by_pieces_1 (block
, ref
, operand
,
2524 return fold_build1 (currop
->opcode
, currop
->type
, genop0
);
2527 case WITH_SIZE_EXPR
:
2529 tree genop0
= create_component_ref_by_pieces_1 (block
, ref
, operand
,
2533 tree genop1
= find_or_generate_expression (block
, currop
->op0
, stmts
);
2536 return fold_build2 (currop
->opcode
, currop
->type
, genop0
, genop1
);
2541 tree genop0
= create_component_ref_by_pieces_1 (block
, ref
, operand
,
2545 tree op1
= currop
->op0
;
2546 tree op2
= currop
->op1
;
2547 tree t
= build3 (BIT_FIELD_REF
, currop
->type
, genop0
, op1
, op2
);
2548 REF_REVERSE_STORAGE_ORDER (t
) = currop
->reverse
;
2552 /* For array ref vn_reference_op's, operand 1 of the array ref
2553 is op0 of the reference op and operand 3 of the array ref is
2555 case ARRAY_RANGE_REF
:
2559 tree genop1
= currop
->op0
;
2560 tree genop2
= currop
->op1
;
2561 tree genop3
= currop
->op2
;
2562 genop0
= create_component_ref_by_pieces_1 (block
, ref
, operand
,
2566 genop1
= find_or_generate_expression (block
, genop1
, stmts
);
2571 tree domain_type
= TYPE_DOMAIN (TREE_TYPE (genop0
));
2572 /* Drop zero minimum index if redundant. */
2573 if (integer_zerop (genop2
)
2575 || integer_zerop (TYPE_MIN_VALUE (domain_type
))))
2579 genop2
= find_or_generate_expression (block
, genop2
, stmts
);
2586 tree elmt_type
= TREE_TYPE (TREE_TYPE (genop0
));
2587 /* We can't always put a size in units of the element alignment
2588 here as the element alignment may be not visible. See
2589 PR43783. Simply drop the element size for constant
2591 if (TREE_CODE (genop3
) == INTEGER_CST
2592 && TREE_CODE (TYPE_SIZE_UNIT (elmt_type
)) == INTEGER_CST
2593 && wi::eq_p (wi::to_offset (TYPE_SIZE_UNIT (elmt_type
)),
2594 (wi::to_offset (genop3
)
2595 * vn_ref_op_align_unit (currop
))))
2599 genop3
= find_or_generate_expression (block
, genop3
, stmts
);
2604 return build4 (currop
->opcode
, currop
->type
, genop0
, genop1
,
2611 tree genop2
= currop
->op1
;
2612 op0
= create_component_ref_by_pieces_1 (block
, ref
, operand
, stmts
);
2615 /* op1 should be a FIELD_DECL, which are represented by themselves. */
2619 genop2
= find_or_generate_expression (block
, genop2
, stmts
);
2623 return fold_build3 (COMPONENT_REF
, TREE_TYPE (op1
), op0
, op1
, genop2
);
2628 genop
= find_or_generate_expression (block
, currop
->op0
, stmts
);
2649 /* For COMPONENT_REF's and ARRAY_REF's, we can't have any intermediates for the
2650 COMPONENT_REF or MEM_REF or ARRAY_REF portion, because we'd end up with
2651 trying to rename aggregates into ssa form directly, which is a no no.
2653 Thus, this routine doesn't create temporaries, it just builds a
2654 single access expression for the array, calling
2655 find_or_generate_expression to build the innermost pieces.
2657 This function is a subroutine of create_expression_by_pieces, and
2658 should not be called on it's own unless you really know what you
2662 create_component_ref_by_pieces (basic_block block
, vn_reference_t ref
,
2665 unsigned int op
= 0;
2666 return create_component_ref_by_pieces_1 (block
, ref
, &op
, stmts
);
2669 /* Find a simple leader for an expression, or generate one using
2670 create_expression_by_pieces from a NARY expression for the value.
2671 BLOCK is the basic_block we are looking for leaders in.
2672 OP is the tree expression to find a leader for or generate.
2673 Returns the leader or NULL_TREE on failure. */
2676 find_or_generate_expression (basic_block block
, tree op
, gimple_seq
*stmts
)
2678 pre_expr expr
= get_or_alloc_expr_for (op
);
2679 unsigned int lookfor
= get_expr_value_id (expr
);
2680 pre_expr leader
= bitmap_find_leader (AVAIL_OUT (block
), lookfor
);
2683 if (leader
->kind
== NAME
)
2684 return PRE_EXPR_NAME (leader
);
2685 else if (leader
->kind
== CONSTANT
)
2686 return PRE_EXPR_CONSTANT (leader
);
2692 /* It must be a complex expression, so generate it recursively. Note
2693 that this is only necessary to handle gcc.dg/tree-ssa/ssa-pre28.c
2694 where the insert algorithm fails to insert a required expression. */
2695 bitmap exprset
= value_expressions
[lookfor
];
2698 EXECUTE_IF_SET_IN_BITMAP (exprset
, 0, i
, bi
)
2700 pre_expr temp
= expression_for_id (i
);
2701 /* We cannot insert random REFERENCE expressions at arbitrary
2702 places. We can insert NARYs which eventually re-materializes
2703 its operand values. */
2704 if (temp
->kind
== NARY
)
2705 return create_expression_by_pieces (block
, temp
, stmts
,
2706 get_expr_type (expr
));
2713 #define NECESSARY GF_PLF_1
2715 /* Create an expression in pieces, so that we can handle very complex
2716 expressions that may be ANTIC, but not necessary GIMPLE.
2717 BLOCK is the basic block the expression will be inserted into,
2718 EXPR is the expression to insert (in value form)
2719 STMTS is a statement list to append the necessary insertions into.
2721 This function will die if we hit some value that shouldn't be
2722 ANTIC but is (IE there is no leader for it, or its components).
2723 The function returns NULL_TREE in case a different antic expression
2724 has to be inserted first.
2725 This function may also generate expressions that are themselves
2726 partially or fully redundant. Those that are will be either made
2727 fully redundant during the next iteration of insert (for partially
2728 redundant ones), or eliminated by eliminate (for fully redundant
2732 create_expression_by_pieces (basic_block block
, pre_expr expr
,
2733 gimple_seq
*stmts
, tree type
)
2737 gimple_seq forced_stmts
= NULL
;
2738 unsigned int value_id
;
2739 gimple_stmt_iterator gsi
;
2740 tree exprtype
= type
? type
: get_expr_type (expr
);
2746 /* We may hit the NAME/CONSTANT case if we have to convert types
2747 that value numbering saw through. */
2749 folded
= PRE_EXPR_NAME (expr
);
2750 if (useless_type_conversion_p (exprtype
, TREE_TYPE (folded
)))
2755 folded
= PRE_EXPR_CONSTANT (expr
);
2756 tree tem
= fold_convert (exprtype
, folded
);
2757 if (is_gimple_min_invariant (tem
))
2762 if (PRE_EXPR_REFERENCE (expr
)->operands
[0].opcode
== CALL_EXPR
)
2764 vn_reference_t ref
= PRE_EXPR_REFERENCE (expr
);
2765 unsigned int operand
= 1;
2766 vn_reference_op_t currop
= &ref
->operands
[0];
2767 tree sc
= NULL_TREE
;
2769 if (TREE_CODE (currop
->op0
) == FUNCTION_DECL
)
2772 fn
= find_or_generate_expression (block
, currop
->op0
, stmts
);
2777 sc
= find_or_generate_expression (block
, currop
->op1
, stmts
);
2781 auto_vec
<tree
> args (ref
->operands
.length () - 1);
2782 while (operand
< ref
->operands
.length ())
2784 tree arg
= create_component_ref_by_pieces_1 (block
, ref
,
2788 args
.quick_push (arg
);
2791 = gimple_build_call_vec ((TREE_CODE (fn
) == FUNCTION_DECL
2792 ? build_fold_addr_expr (fn
) : fn
), args
);
2793 gimple_call_set_with_bounds (call
, currop
->with_bounds
);
2795 gimple_call_set_chain (call
, sc
);
2796 tree forcedname
= make_ssa_name (currop
->type
);
2797 gimple_call_set_lhs (call
, forcedname
);
2798 gimple_set_vuse (call
, BB_LIVE_VOP_ON_EXIT (block
));
2799 gimple_seq_add_stmt_without_update (&forced_stmts
, call
);
2800 folded
= forcedname
;
2804 folded
= create_component_ref_by_pieces (block
,
2805 PRE_EXPR_REFERENCE (expr
),
2809 name
= make_temp_ssa_name (exprtype
, NULL
, "pretmp");
2810 newstmt
= gimple_build_assign (name
, folded
);
2811 gimple_seq_add_stmt_without_update (&forced_stmts
, newstmt
);
2812 gimple_set_vuse (newstmt
, BB_LIVE_VOP_ON_EXIT (block
));
2818 vn_nary_op_t nary
= PRE_EXPR_NARY (expr
);
2819 tree
*genop
= XALLOCAVEC (tree
, nary
->length
);
2821 for (i
= 0; i
< nary
->length
; ++i
)
2823 genop
[i
] = find_or_generate_expression (block
, nary
->op
[i
], stmts
);
2826 /* Ensure genop[] is properly typed for POINTER_PLUS_EXPR. It
2827 may have conversions stripped. */
2828 if (nary
->opcode
== POINTER_PLUS_EXPR
)
2831 genop
[i
] = gimple_convert (&forced_stmts
,
2832 nary
->type
, genop
[i
]);
2834 genop
[i
] = gimple_convert (&forced_stmts
,
2835 sizetype
, genop
[i
]);
2838 genop
[i
] = gimple_convert (&forced_stmts
,
2839 TREE_TYPE (nary
->op
[i
]), genop
[i
]);
2841 if (nary
->opcode
== CONSTRUCTOR
)
2843 vec
<constructor_elt
, va_gc
> *elts
= NULL
;
2844 for (i
= 0; i
< nary
->length
; ++i
)
2845 CONSTRUCTOR_APPEND_ELT (elts
, NULL_TREE
, genop
[i
]);
2846 folded
= build_constructor (nary
->type
, elts
);
2847 name
= make_temp_ssa_name (exprtype
, NULL
, "pretmp");
2848 newstmt
= gimple_build_assign (name
, folded
);
2849 gimple_seq_add_stmt_without_update (&forced_stmts
, newstmt
);
2854 switch (nary
->length
)
2857 folded
= gimple_build (&forced_stmts
, nary
->opcode
, nary
->type
,
2861 folded
= gimple_build (&forced_stmts
, nary
->opcode
, nary
->type
,
2862 genop
[0], genop
[1]);
2865 folded
= gimple_build (&forced_stmts
, nary
->opcode
, nary
->type
,
2866 genop
[0], genop
[1], genop
[2]);
2878 folded
= gimple_convert (&forced_stmts
, exprtype
, folded
);
2880 /* If there is nothing to insert, return the simplified result. */
2881 if (gimple_seq_empty_p (forced_stmts
))
2883 /* If we simplified to a constant return it and discard eventually
2885 if (is_gimple_min_invariant (folded
))
2887 gimple_seq_discard (forced_stmts
);
2890 /* Likewise if we simplified to sth not queued for insertion. */
2892 gsi
= gsi_last (forced_stmts
);
2893 for (; !gsi_end_p (gsi
); gsi_prev (&gsi
))
2895 gimple
*stmt
= gsi_stmt (gsi
);
2896 tree forcedname
= gimple_get_lhs (stmt
);
2897 if (forcedname
== folded
)
2905 gimple_seq_discard (forced_stmts
);
2908 gcc_assert (TREE_CODE (folded
) == SSA_NAME
);
2910 /* If we have any intermediate expressions to the value sets, add them
2911 to the value sets and chain them in the instruction stream. */
2914 gsi
= gsi_start (forced_stmts
);
2915 for (; !gsi_end_p (gsi
); gsi_next (&gsi
))
2917 gimple
*stmt
= gsi_stmt (gsi
);
2918 tree forcedname
= gimple_get_lhs (stmt
);
2921 if (forcedname
!= folded
)
2923 VN_INFO_GET (forcedname
)->valnum
= forcedname
;
2924 VN_INFO (forcedname
)->value_id
= get_next_value_id ();
2925 nameexpr
= get_or_alloc_expr_for_name (forcedname
);
2926 add_to_value (VN_INFO (forcedname
)->value_id
, nameexpr
);
2927 bitmap_value_replace_in_set (NEW_SETS (block
), nameexpr
);
2928 bitmap_value_replace_in_set (AVAIL_OUT (block
), nameexpr
);
2931 bitmap_set_bit (inserted_exprs
, SSA_NAME_VERSION (forcedname
));
2932 gimple_set_plf (stmt
, NECESSARY
, false);
2934 gimple_seq_add_seq (stmts
, forced_stmts
);
2939 /* Fold the last statement. */
2940 gsi
= gsi_last (*stmts
);
2941 if (fold_stmt_inplace (&gsi
))
2942 update_stmt (gsi_stmt (gsi
));
2944 /* Add a value number to the temporary.
2945 The value may already exist in either NEW_SETS, or AVAIL_OUT, because
2946 we are creating the expression by pieces, and this particular piece of
2947 the expression may have been represented. There is no harm in replacing
2949 value_id
= get_expr_value_id (expr
);
2950 VN_INFO_GET (name
)->value_id
= value_id
;
2951 VN_INFO (name
)->valnum
= sccvn_valnum_from_value_id (value_id
);
2952 if (VN_INFO (name
)->valnum
== NULL_TREE
)
2953 VN_INFO (name
)->valnum
= name
;
2954 gcc_assert (VN_INFO (name
)->valnum
!= NULL_TREE
);
2955 nameexpr
= get_or_alloc_expr_for_name (name
);
2956 add_to_value (value_id
, nameexpr
);
2957 if (NEW_SETS (block
))
2958 bitmap_value_replace_in_set (NEW_SETS (block
), nameexpr
);
2959 bitmap_value_replace_in_set (AVAIL_OUT (block
), nameexpr
);
2961 pre_stats
.insertions
++;
2962 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2964 fprintf (dump_file
, "Inserted ");
2965 print_gimple_stmt (dump_file
, gsi_stmt (gsi_last (*stmts
)), 0, 0);
2966 fprintf (dump_file
, " in predecessor %d (%04d)\n",
2967 block
->index
, value_id
);
2974 /* Insert the to-be-made-available values of expression EXPRNUM for each
2975 predecessor, stored in AVAIL, into the predecessors of BLOCK, and
2976 merge the result with a phi node, given the same value number as
2977 NODE. Return true if we have inserted new stuff. */
2980 insert_into_preds_of_block (basic_block block
, unsigned int exprnum
,
2981 vec
<pre_expr
> avail
)
2983 pre_expr expr
= expression_for_id (exprnum
);
2985 unsigned int val
= get_expr_value_id (expr
);
2987 bool insertions
= false;
2992 tree type
= get_expr_type (expr
);
2996 /* Make sure we aren't creating an induction variable. */
2997 if (bb_loop_depth (block
) > 0 && EDGE_COUNT (block
->preds
) == 2)
2999 bool firstinsideloop
= false;
3000 bool secondinsideloop
= false;
3001 firstinsideloop
= flow_bb_inside_loop_p (block
->loop_father
,
3002 EDGE_PRED (block
, 0)->src
);
3003 secondinsideloop
= flow_bb_inside_loop_p (block
->loop_father
,
3004 EDGE_PRED (block
, 1)->src
);
3005 /* Induction variables only have one edge inside the loop. */
3006 if ((firstinsideloop
^ secondinsideloop
)
3007 && expr
->kind
!= REFERENCE
)
3009 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3010 fprintf (dump_file
, "Skipping insertion of phi for partial redundancy: Looks like an induction variable\n");
3015 /* Make the necessary insertions. */
3016 FOR_EACH_EDGE (pred
, ei
, block
->preds
)
3018 gimple_seq stmts
= NULL
;
3021 eprime
= avail
[pred
->dest_idx
];
3022 builtexpr
= create_expression_by_pieces (bprime
, eprime
,
3024 gcc_assert (!(pred
->flags
& EDGE_ABNORMAL
));
3025 if (!gimple_seq_empty_p (stmts
))
3027 gsi_insert_seq_on_edge (pred
, stmts
);
3032 /* We cannot insert a PHI node if we failed to insert
3037 if (is_gimple_min_invariant (builtexpr
))
3038 avail
[pred
->dest_idx
] = get_or_alloc_expr_for_constant (builtexpr
);
3040 avail
[pred
->dest_idx
] = get_or_alloc_expr_for_name (builtexpr
);
3042 /* If we didn't want a phi node, and we made insertions, we still have
3043 inserted new stuff, and thus return true. If we didn't want a phi node,
3044 and didn't make insertions, we haven't added anything new, so return
3046 if (nophi
&& insertions
)
3048 else if (nophi
&& !insertions
)
3051 /* Now build a phi for the new variable. */
3052 temp
= make_temp_ssa_name (type
, NULL
, "prephitmp");
3053 phi
= create_phi_node (temp
, block
);
3055 gimple_set_plf (phi
, NECESSARY
, false);
3056 VN_INFO_GET (temp
)->value_id
= val
;
3057 VN_INFO (temp
)->valnum
= sccvn_valnum_from_value_id (val
);
3058 if (VN_INFO (temp
)->valnum
== NULL_TREE
)
3059 VN_INFO (temp
)->valnum
= temp
;
3060 bitmap_set_bit (inserted_exprs
, SSA_NAME_VERSION (temp
));
3061 FOR_EACH_EDGE (pred
, ei
, block
->preds
)
3063 pre_expr ae
= avail
[pred
->dest_idx
];
3064 gcc_assert (get_expr_type (ae
) == type
3065 || useless_type_conversion_p (type
, get_expr_type (ae
)));
3066 if (ae
->kind
== CONSTANT
)
3067 add_phi_arg (phi
, unshare_expr (PRE_EXPR_CONSTANT (ae
)),
3068 pred
, UNKNOWN_LOCATION
);
3070 add_phi_arg (phi
, PRE_EXPR_NAME (ae
), pred
, UNKNOWN_LOCATION
);
3073 newphi
= get_or_alloc_expr_for_name (temp
);
3074 add_to_value (val
, newphi
);
3076 /* The value should *not* exist in PHI_GEN, or else we wouldn't be doing
3077 this insertion, since we test for the existence of this value in PHI_GEN
3078 before proceeding with the partial redundancy checks in insert_aux.
3080 The value may exist in AVAIL_OUT, in particular, it could be represented
3081 by the expression we are trying to eliminate, in which case we want the
3082 replacement to occur. If it's not existing in AVAIL_OUT, we want it
3085 Similarly, to the PHI_GEN case, the value should not exist in NEW_SETS of
3086 this block, because if it did, it would have existed in our dominator's
3087 AVAIL_OUT, and would have been skipped due to the full redundancy check.
3090 bitmap_insert_into_set (PHI_GEN (block
), newphi
);
3091 bitmap_value_replace_in_set (AVAIL_OUT (block
),
3093 bitmap_insert_into_set (NEW_SETS (block
),
3096 /* If we insert a PHI node for a conversion of another PHI node
3097 in the same basic-block try to preserve range information.
3098 This is important so that followup loop passes receive optimal
3099 number of iteration analysis results. See PR61743. */
3100 if (expr
->kind
== NARY
3101 && CONVERT_EXPR_CODE_P (expr
->u
.nary
->opcode
)
3102 && TREE_CODE (expr
->u
.nary
->op
[0]) == SSA_NAME
3103 && gimple_bb (SSA_NAME_DEF_STMT (expr
->u
.nary
->op
[0])) == block
3104 && INTEGRAL_TYPE_P (type
)
3105 && INTEGRAL_TYPE_P (TREE_TYPE (expr
->u
.nary
->op
[0]))
3106 && (TYPE_PRECISION (type
)
3107 >= TYPE_PRECISION (TREE_TYPE (expr
->u
.nary
->op
[0])))
3108 && SSA_NAME_RANGE_INFO (expr
->u
.nary
->op
[0]))
3111 if (get_range_info (expr
->u
.nary
->op
[0], &min
, &max
) == VR_RANGE
3112 && !wi::neg_p (min
, SIGNED
)
3113 && !wi::neg_p (max
, SIGNED
))
3114 /* Just handle extension and sign-changes of all-positive ranges. */
3115 set_range_info (temp
,
3116 SSA_NAME_RANGE_TYPE (expr
->u
.nary
->op
[0]),
3117 wide_int_storage::from (min
, TYPE_PRECISION (type
),
3119 wide_int_storage::from (max
, TYPE_PRECISION (type
),
3123 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3125 fprintf (dump_file
, "Created phi ");
3126 print_gimple_stmt (dump_file
, phi
, 0, 0);
3127 fprintf (dump_file
, " in block %d (%04d)\n", block
->index
, val
);
3135 /* Perform insertion of partially redundant or hoistable values.
3136 For BLOCK, do the following:
3137 1. Propagate the NEW_SETS of the dominator into the current block.
3138 If the block has multiple predecessors,
3139 2a. Iterate over the ANTIC expressions for the block to see if
3140 any of them are partially redundant.
3141 2b. If so, insert them into the necessary predecessors to make
3142 the expression fully redundant.
3143 2c. Insert a new PHI merging the values of the predecessors.
3144 2d. Insert the new PHI, and the new expressions, into the
3146 If the block has multiple successors,
3147 3a. Iterate over the ANTIC values for the block to see if
3148 any of them are good candidates for hoisting.
3149 3b. If so, insert expressions computing the values in BLOCK,
3150 and add the new expressions into the NEW_SETS set.
3151 4. Recursively call ourselves on the dominator children of BLOCK.
3153 Steps 1, 2a, and 4 are done by insert_aux. 2b, 2c and 2d are done by
3154 do_pre_regular_insertion and do_partial_insertion. 3a and 3b are
3155 done in do_hoist_insertion.
3159 do_pre_regular_insertion (basic_block block
, basic_block dom
)
3161 bool new_stuff
= false;
3162 vec
<pre_expr
> exprs
;
3164 auto_vec
<pre_expr
> avail
;
3167 exprs
= sorted_array_from_bitmap_set (ANTIC_IN (block
));
3168 avail
.safe_grow (EDGE_COUNT (block
->preds
));
3170 FOR_EACH_VEC_ELT (exprs
, i
, expr
)
3172 if (expr
->kind
== NARY
3173 || expr
->kind
== REFERENCE
)
3176 bool by_some
= false;
3177 bool cant_insert
= false;
3178 bool all_same
= true;
3179 pre_expr first_s
= NULL
;
3182 pre_expr eprime
= NULL
;
3184 pre_expr edoubleprime
= NULL
;
3185 bool do_insertion
= false;
3187 val
= get_expr_value_id (expr
);
3188 if (bitmap_set_contains_value (PHI_GEN (block
), val
))
3190 if (bitmap_set_contains_value (AVAIL_OUT (dom
), val
))
3192 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3194 fprintf (dump_file
, "Found fully redundant value: ");
3195 print_pre_expr (dump_file
, expr
);
3196 fprintf (dump_file
, "\n");
3201 FOR_EACH_EDGE (pred
, ei
, block
->preds
)
3203 unsigned int vprime
;
3205 /* We should never run insertion for the exit block
3206 and so not come across fake pred edges. */
3207 gcc_assert (!(pred
->flags
& EDGE_FAKE
));
3209 /* We are looking at ANTIC_OUT of bprime. */
3210 eprime
= phi_translate (expr
, ANTIC_IN (block
), NULL
,
3213 /* eprime will generally only be NULL if the
3214 value of the expression, translated
3215 through the PHI for this predecessor, is
3216 undefined. If that is the case, we can't
3217 make the expression fully redundant,
3218 because its value is undefined along a
3219 predecessor path. We can thus break out
3220 early because it doesn't matter what the
3221 rest of the results are. */
3224 avail
[pred
->dest_idx
] = NULL
;
3229 vprime
= get_expr_value_id (eprime
);
3230 edoubleprime
= bitmap_find_leader (AVAIL_OUT (bprime
),
3232 if (edoubleprime
== NULL
)
3234 avail
[pred
->dest_idx
] = eprime
;
3239 avail
[pred
->dest_idx
] = edoubleprime
;
3241 /* We want to perform insertions to remove a redundancy on
3242 a path in the CFG we want to optimize for speed. */
3243 if (optimize_edge_for_speed_p (pred
))
3244 do_insertion
= true;
3245 if (first_s
== NULL
)
3246 first_s
= edoubleprime
;
3247 else if (!pre_expr_d::equal (first_s
, edoubleprime
))
3251 /* If we can insert it, it's not the same value
3252 already existing along every predecessor, and
3253 it's defined by some predecessor, it is
3254 partially redundant. */
3255 if (!cant_insert
&& !all_same
&& by_some
)
3259 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3261 fprintf (dump_file
, "Skipping partial redundancy for "
3263 print_pre_expr (dump_file
, expr
);
3264 fprintf (dump_file
, " (%04d), no redundancy on to be "
3265 "optimized for speed edge\n", val
);
3268 else if (dbg_cnt (treepre_insert
))
3270 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3272 fprintf (dump_file
, "Found partial redundancy for "
3274 print_pre_expr (dump_file
, expr
);
3275 fprintf (dump_file
, " (%04d)\n",
3276 get_expr_value_id (expr
));
3278 if (insert_into_preds_of_block (block
,
3279 get_expression_id (expr
),
3284 /* If all edges produce the same value and that value is
3285 an invariant, then the PHI has the same value on all
3286 edges. Note this. */
3287 else if (!cant_insert
&& all_same
)
3289 gcc_assert (edoubleprime
->kind
== CONSTANT
3290 || edoubleprime
->kind
== NAME
);
3292 tree temp
= make_temp_ssa_name (get_expr_type (expr
),
3295 = gimple_build_assign (temp
,
3296 edoubleprime
->kind
== CONSTANT
?
3297 PRE_EXPR_CONSTANT (edoubleprime
) :
3298 PRE_EXPR_NAME (edoubleprime
));
3299 gimple_stmt_iterator gsi
= gsi_after_labels (block
);
3300 gsi_insert_before (&gsi
, assign
, GSI_NEW_STMT
);
3302 gimple_set_plf (assign
, NECESSARY
, false);
3303 VN_INFO_GET (temp
)->value_id
= val
;
3304 VN_INFO (temp
)->valnum
= sccvn_valnum_from_value_id (val
);
3305 if (VN_INFO (temp
)->valnum
== NULL_TREE
)
3306 VN_INFO (temp
)->valnum
= temp
;
3307 bitmap_set_bit (inserted_exprs
, SSA_NAME_VERSION (temp
));
3308 pre_expr newe
= get_or_alloc_expr_for_name (temp
);
3309 add_to_value (val
, newe
);
3310 bitmap_value_replace_in_set (AVAIL_OUT (block
), newe
);
3311 bitmap_insert_into_set (NEW_SETS (block
), newe
);
3321 /* Perform insertion for partially anticipatable expressions. There
3322 is only one case we will perform insertion for these. This case is
3323 if the expression is partially anticipatable, and fully available.
3324 In this case, we know that putting it earlier will enable us to
3325 remove the later computation. */
3328 do_pre_partial_partial_insertion (basic_block block
, basic_block dom
)
3330 bool new_stuff
= false;
3331 vec
<pre_expr
> exprs
;
3333 auto_vec
<pre_expr
> avail
;
3336 exprs
= sorted_array_from_bitmap_set (PA_IN (block
));
3337 avail
.safe_grow (EDGE_COUNT (block
->preds
));
3339 FOR_EACH_VEC_ELT (exprs
, i
, expr
)
3341 if (expr
->kind
== NARY
3342 || expr
->kind
== REFERENCE
)
3346 bool cant_insert
= false;
3349 pre_expr eprime
= NULL
;
3352 val
= get_expr_value_id (expr
);
3353 if (bitmap_set_contains_value (PHI_GEN (block
), val
))
3355 if (bitmap_set_contains_value (AVAIL_OUT (dom
), val
))
3358 FOR_EACH_EDGE (pred
, ei
, block
->preds
)
3360 unsigned int vprime
;
3361 pre_expr edoubleprime
;
3363 /* We should never run insertion for the exit block
3364 and so not come across fake pred edges. */
3365 gcc_assert (!(pred
->flags
& EDGE_FAKE
));
3367 eprime
= phi_translate (expr
, ANTIC_IN (block
),
3371 /* eprime will generally only be NULL if the
3372 value of the expression, translated
3373 through the PHI for this predecessor, is
3374 undefined. If that is the case, we can't
3375 make the expression fully redundant,
3376 because its value is undefined along a
3377 predecessor path. We can thus break out
3378 early because it doesn't matter what the
3379 rest of the results are. */
3382 avail
[pred
->dest_idx
] = NULL
;
3387 vprime
= get_expr_value_id (eprime
);
3388 edoubleprime
= bitmap_find_leader (AVAIL_OUT (bprime
), vprime
);
3389 avail
[pred
->dest_idx
] = edoubleprime
;
3390 if (edoubleprime
== NULL
)
3397 /* If we can insert it, it's not the same value
3398 already existing along every predecessor, and
3399 it's defined by some predecessor, it is
3400 partially redundant. */
3401 if (!cant_insert
&& by_all
)
3404 bool do_insertion
= false;
3406 /* Insert only if we can remove a later expression on a path
3407 that we want to optimize for speed.
3408 The phi node that we will be inserting in BLOCK is not free,
3409 and inserting it for the sake of !optimize_for_speed successor
3410 may cause regressions on the speed path. */
3411 FOR_EACH_EDGE (succ
, ei
, block
->succs
)
3413 if (bitmap_set_contains_value (PA_IN (succ
->dest
), val
)
3414 || bitmap_set_contains_value (ANTIC_IN (succ
->dest
), val
))
3416 if (optimize_edge_for_speed_p (succ
))
3417 do_insertion
= true;
3423 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3425 fprintf (dump_file
, "Skipping partial partial redundancy "
3427 print_pre_expr (dump_file
, expr
);
3428 fprintf (dump_file
, " (%04d), not (partially) anticipated "
3429 "on any to be optimized for speed edges\n", val
);
3432 else if (dbg_cnt (treepre_insert
))
3434 pre_stats
.pa_insert
++;
3435 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3437 fprintf (dump_file
, "Found partial partial redundancy "
3439 print_pre_expr (dump_file
, expr
);
3440 fprintf (dump_file
, " (%04d)\n",
3441 get_expr_value_id (expr
));
3443 if (insert_into_preds_of_block (block
,
3444 get_expression_id (expr
),
3456 /* Insert expressions in BLOCK to compute hoistable values up.
3457 Return TRUE if something was inserted, otherwise return FALSE.
3458 The caller has to make sure that BLOCK has at least two successors. */
3461 do_hoist_insertion (basic_block block
)
3465 bool new_stuff
= false;
3467 gimple_stmt_iterator last
;
3469 /* At least two successors, or else... */
3470 gcc_assert (EDGE_COUNT (block
->succs
) >= 2);
3472 /* Check that all successors of BLOCK are dominated by block.
3473 We could use dominated_by_p() for this, but actually there is a much
3474 quicker check: any successor that is dominated by BLOCK can't have
3475 more than one predecessor edge. */
3476 FOR_EACH_EDGE (e
, ei
, block
->succs
)
3477 if (! single_pred_p (e
->dest
))
3480 /* Determine the insertion point. If we cannot safely insert before
3481 the last stmt if we'd have to, bail out. */
3482 last
= gsi_last_bb (block
);
3483 if (!gsi_end_p (last
)
3484 && !is_ctrl_stmt (gsi_stmt (last
))
3485 && stmt_ends_bb_p (gsi_stmt (last
)))
3488 /* Compute the set of hoistable expressions from ANTIC_IN. First compute
3489 hoistable values. */
3490 bitmap_set hoistable_set
;
3492 /* A hoistable value must be in ANTIC_IN(block)
3493 but not in AVAIL_OUT(BLOCK). */
3494 bitmap_initialize (&hoistable_set
.values
, &grand_bitmap_obstack
);
3495 bitmap_and_compl (&hoistable_set
.values
,
3496 &ANTIC_IN (block
)->values
, &AVAIL_OUT (block
)->values
);
3498 /* Short-cut for a common case: hoistable_set is empty. */
3499 if (bitmap_empty_p (&hoistable_set
.values
))
3502 /* Compute which of the hoistable values is in AVAIL_OUT of
3503 at least one of the successors of BLOCK. */
3504 bitmap_head availout_in_some
;
3505 bitmap_initialize (&availout_in_some
, &grand_bitmap_obstack
);
3506 FOR_EACH_EDGE (e
, ei
, block
->succs
)
3507 /* Do not consider expressions solely because their availability
3508 on loop exits. They'd be ANTIC-IN throughout the whole loop
3509 and thus effectively hoisted across loops by combination of
3510 PRE and hoisting. */
3511 if (! loop_exit_edge_p (block
->loop_father
, e
))
3512 bitmap_ior_and_into (&availout_in_some
, &hoistable_set
.values
,
3513 &AVAIL_OUT (e
->dest
)->values
);
3514 bitmap_clear (&hoistable_set
.values
);
3516 /* Short-cut for a common case: availout_in_some is empty. */
3517 if (bitmap_empty_p (&availout_in_some
))
3520 /* Hack hoitable_set in-place so we can use sorted_array_from_bitmap_set. */
3521 hoistable_set
.values
= availout_in_some
;
3522 hoistable_set
.expressions
= ANTIC_IN (block
)->expressions
;
3524 /* Now finally construct the topological-ordered expression set. */
3525 vec
<pre_expr
> exprs
= sorted_array_from_bitmap_set (&hoistable_set
);
3527 bitmap_clear (&hoistable_set
.values
);
3529 /* If there are candidate values for hoisting, insert expressions
3530 strategically to make the hoistable expressions fully redundant. */
3532 FOR_EACH_VEC_ELT (exprs
, i
, expr
)
3534 /* While we try to sort expressions topologically above the
3535 sorting doesn't work out perfectly. Catch expressions we
3536 already inserted. */
3537 unsigned int value_id
= get_expr_value_id (expr
);
3538 if (bitmap_set_contains_value (AVAIL_OUT (block
), value_id
))
3540 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3543 "Already inserted expression for ");
3544 print_pre_expr (dump_file
, expr
);
3545 fprintf (dump_file
, " (%04d)\n", value_id
);
3550 /* OK, we should hoist this value. Perform the transformation. */
3551 pre_stats
.hoist_insert
++;
3552 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3555 "Inserting expression in block %d for code hoisting: ",
3557 print_pre_expr (dump_file
, expr
);
3558 fprintf (dump_file
, " (%04d)\n", value_id
);
3561 gimple_seq stmts
= NULL
;
3562 tree res
= create_expression_by_pieces (block
, expr
, &stmts
,
3563 get_expr_type (expr
));
3565 /* Do not return true if expression creation ultimately
3566 did not insert any statements. */
3567 if (gimple_seq_empty_p (stmts
))
3571 if (gsi_end_p (last
) || is_ctrl_stmt (gsi_stmt (last
)))
3572 gsi_insert_seq_before (&last
, stmts
, GSI_SAME_STMT
);
3574 gsi_insert_seq_after (&last
, stmts
, GSI_NEW_STMT
);
3577 /* Make sure to not return true if expression creation ultimately
3578 failed but also make sure to insert any stmts produced as they
3579 are tracked in inserted_exprs. */
3591 /* Do a dominator walk on the control flow graph, and insert computations
3592 of values as necessary for PRE and hoisting. */
3595 insert_aux (basic_block block
, bool do_pre
, bool do_hoist
)
3598 bool new_stuff
= false;
3603 dom
= get_immediate_dominator (CDI_DOMINATORS
, block
);
3608 bitmap_set_t newset
;
3610 /* First, update the AVAIL_OUT set with anything we may have
3611 inserted higher up in the dominator tree. */
3612 newset
= NEW_SETS (dom
);
3615 /* Note that we need to value_replace both NEW_SETS, and
3616 AVAIL_OUT. For both the case of NEW_SETS, the value may be
3617 represented by some non-simple expression here that we want
3618 to replace it with. */
3619 FOR_EACH_EXPR_ID_IN_SET (newset
, i
, bi
)
3621 pre_expr expr
= expression_for_id (i
);
3622 bitmap_value_replace_in_set (NEW_SETS (block
), expr
);
3623 bitmap_value_replace_in_set (AVAIL_OUT (block
), expr
);
3627 /* Insert expressions for partial redundancies. */
3628 if (do_pre
&& !single_pred_p (block
))
3630 new_stuff
|= do_pre_regular_insertion (block
, dom
);
3631 if (do_partial_partial
)
3632 new_stuff
|= do_pre_partial_partial_insertion (block
, dom
);
3635 /* Insert expressions for hoisting. */
3636 if (do_hoist
&& EDGE_COUNT (block
->succs
) >= 2)
3637 new_stuff
|= do_hoist_insertion (block
);
3640 for (son
= first_dom_son (CDI_DOMINATORS
, block
);
3642 son
= next_dom_son (CDI_DOMINATORS
, son
))
3644 new_stuff
|= insert_aux (son
, do_pre
, do_hoist
);
3650 /* Perform insertion of partially redundant and hoistable values. */
3655 bool new_stuff
= true;
3657 int num_iterations
= 0;
3659 FOR_ALL_BB_FN (bb
, cfun
)
3660 NEW_SETS (bb
) = bitmap_set_new ();
3665 if (dump_file
&& dump_flags
& TDF_DETAILS
)
3666 fprintf (dump_file
, "Starting insert iteration %d\n", num_iterations
);
3667 new_stuff
= insert_aux (ENTRY_BLOCK_PTR_FOR_FN (cfun
), flag_tree_pre
,
3668 flag_code_hoisting
);
3670 /* Clear the NEW sets before the next iteration. We have already
3671 fully propagated its contents. */
3673 FOR_ALL_BB_FN (bb
, cfun
)
3674 bitmap_set_free (NEW_SETS (bb
));
3676 statistics_histogram_event (cfun
, "insert iterations", num_iterations
);
3680 /* Compute the AVAIL set for all basic blocks.
3682 This function performs value numbering of the statements in each basic
3683 block. The AVAIL sets are built from information we glean while doing
3684 this value numbering, since the AVAIL sets contain only one entry per
3687 AVAIL_IN[BLOCK] = AVAIL_OUT[dom(BLOCK)].
3688 AVAIL_OUT[BLOCK] = AVAIL_IN[BLOCK] U PHI_GEN[BLOCK] U TMP_GEN[BLOCK]. */
3691 compute_avail (void)
3694 basic_block block
, son
;
3695 basic_block
*worklist
;
3700 /* We pretend that default definitions are defined in the entry block.
3701 This includes function arguments and the static chain decl. */
3702 FOR_EACH_SSA_NAME (i
, name
, cfun
)
3705 if (!SSA_NAME_IS_DEFAULT_DEF (name
)
3706 || has_zero_uses (name
)
3707 || virtual_operand_p (name
))
3710 e
= get_or_alloc_expr_for_name (name
);
3711 add_to_value (get_expr_value_id (e
), e
);
3712 bitmap_insert_into_set (TMP_GEN (ENTRY_BLOCK_PTR_FOR_FN (cfun
)), e
);
3713 bitmap_value_insert_into_set (AVAIL_OUT (ENTRY_BLOCK_PTR_FOR_FN (cfun
)),
3717 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3719 print_bitmap_set (dump_file
, TMP_GEN (ENTRY_BLOCK_PTR_FOR_FN (cfun
)),
3720 "tmp_gen", ENTRY_BLOCK
);
3721 print_bitmap_set (dump_file
, AVAIL_OUT (ENTRY_BLOCK_PTR_FOR_FN (cfun
)),
3722 "avail_out", ENTRY_BLOCK
);
3725 /* Allocate the worklist. */
3726 worklist
= XNEWVEC (basic_block
, n_basic_blocks_for_fn (cfun
));
3728 /* Seed the algorithm by putting the dominator children of the entry
3729 block on the worklist. */
3730 for (son
= first_dom_son (CDI_DOMINATORS
, ENTRY_BLOCK_PTR_FOR_FN (cfun
));
3732 son
= next_dom_son (CDI_DOMINATORS
, son
))
3733 worklist
[sp
++] = son
;
3735 BB_LIVE_VOP_ON_EXIT (ENTRY_BLOCK_PTR_FOR_FN (cfun
))
3736 = ssa_default_def (cfun
, gimple_vop (cfun
));
3738 /* Loop until the worklist is empty. */
3744 /* Pick a block from the worklist. */
3745 block
= worklist
[--sp
];
3747 /* Initially, the set of available values in BLOCK is that of
3748 its immediate dominator. */
3749 dom
= get_immediate_dominator (CDI_DOMINATORS
, block
);
3752 bitmap_set_copy (AVAIL_OUT (block
), AVAIL_OUT (dom
));
3753 BB_LIVE_VOP_ON_EXIT (block
) = BB_LIVE_VOP_ON_EXIT (dom
);
3756 /* Generate values for PHI nodes. */
3757 for (gphi_iterator gsi
= gsi_start_phis (block
); !gsi_end_p (gsi
);
3760 tree result
= gimple_phi_result (gsi
.phi ());
3762 /* We have no need for virtual phis, as they don't represent
3763 actual computations. */
3764 if (virtual_operand_p (result
))
3766 BB_LIVE_VOP_ON_EXIT (block
) = result
;
3770 pre_expr e
= get_or_alloc_expr_for_name (result
);
3771 add_to_value (get_expr_value_id (e
), e
);
3772 bitmap_value_insert_into_set (AVAIL_OUT (block
), e
);
3773 bitmap_insert_into_set (PHI_GEN (block
), e
);
3776 BB_MAY_NOTRETURN (block
) = 0;
3778 /* Now compute value numbers and populate value sets with all
3779 the expressions computed in BLOCK. */
3780 for (gimple_stmt_iterator gsi
= gsi_start_bb (block
); !gsi_end_p (gsi
);
3786 stmt
= gsi_stmt (gsi
);
3788 /* Cache whether the basic-block has any non-visible side-effect
3790 If this isn't a call or it is the last stmt in the
3791 basic-block then the CFG represents things correctly. */
3792 if (is_gimple_call (stmt
) && !stmt_ends_bb_p (stmt
))
3794 /* Non-looping const functions always return normally.
3795 Otherwise the call might not return or have side-effects
3796 that forbids hoisting possibly trapping expressions
3798 int flags
= gimple_call_flags (stmt
);
3799 if (!(flags
& ECF_CONST
)
3800 || (flags
& ECF_LOOPING_CONST_OR_PURE
))
3801 BB_MAY_NOTRETURN (block
) = 1;
3804 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, iter
, SSA_OP_DEF
)
3806 pre_expr e
= get_or_alloc_expr_for_name (op
);
3808 add_to_value (get_expr_value_id (e
), e
);
3809 bitmap_insert_into_set (TMP_GEN (block
), e
);
3810 bitmap_value_insert_into_set (AVAIL_OUT (block
), e
);
3813 if (gimple_vdef (stmt
))
3814 BB_LIVE_VOP_ON_EXIT (block
) = gimple_vdef (stmt
);
3816 if (gimple_has_side_effects (stmt
)
3817 || stmt_could_throw_p (stmt
)
3818 || is_gimple_debug (stmt
))
3821 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, iter
, SSA_OP_USE
)
3823 if (ssa_undefined_value_p (op
))
3825 pre_expr e
= get_or_alloc_expr_for_name (op
);
3826 bitmap_value_insert_into_set (EXP_GEN (block
), e
);
3829 switch (gimple_code (stmt
))
3837 vn_reference_s ref1
;
3838 pre_expr result
= NULL
;
3840 /* We can value number only calls to real functions. */
3841 if (gimple_call_internal_p (stmt
))
3844 vn_reference_lookup_call (as_a
<gcall
*> (stmt
), &ref
, &ref1
);
3848 /* If the value of the call is not invalidated in
3849 this block until it is computed, add the expression
3851 if (!gimple_vuse (stmt
)
3853 (SSA_NAME_DEF_STMT (gimple_vuse (stmt
))) == GIMPLE_PHI
3854 || gimple_bb (SSA_NAME_DEF_STMT
3855 (gimple_vuse (stmt
))) != block
)
3857 result
= pre_expr_pool
.allocate ();
3858 result
->kind
= REFERENCE
;
3860 PRE_EXPR_REFERENCE (result
) = ref
;
3862 get_or_alloc_expression_id (result
);
3863 add_to_value (get_expr_value_id (result
), result
);
3864 bitmap_value_insert_into_set (EXP_GEN (block
), result
);
3871 pre_expr result
= NULL
;
3872 switch (vn_get_stmt_kind (stmt
))
3876 enum tree_code code
= gimple_assign_rhs_code (stmt
);
3879 /* COND_EXPR and VEC_COND_EXPR are awkward in
3880 that they contain an embedded complex expression.
3881 Don't even try to shove those through PRE. */
3882 if (code
== COND_EXPR
3883 || code
== VEC_COND_EXPR
)
3886 vn_nary_op_lookup_stmt (stmt
, &nary
);
3890 /* If the NARY traps and there was a preceding
3891 point in the block that might not return avoid
3892 adding the nary to EXP_GEN. */
3893 if (BB_MAY_NOTRETURN (block
)
3894 && vn_nary_may_trap (nary
))
3897 result
= pre_expr_pool
.allocate ();
3898 result
->kind
= NARY
;
3900 PRE_EXPR_NARY (result
) = nary
;
3906 tree rhs1
= gimple_assign_rhs1 (stmt
);
3907 alias_set_type set
= get_alias_set (rhs1
);
3908 vec
<vn_reference_op_s
> operands
3909 = vn_reference_operands_for_lookup (rhs1
);
3911 vn_reference_lookup_pieces (gimple_vuse (stmt
), set
,
3913 operands
, &ref
, VN_WALK
);
3916 operands
.release ();
3920 /* If the value of the reference is not invalidated in
3921 this block until it is computed, add the expression
3923 if (gimple_vuse (stmt
))
3927 def_stmt
= SSA_NAME_DEF_STMT (gimple_vuse (stmt
));
3928 while (!gimple_nop_p (def_stmt
)
3929 && gimple_code (def_stmt
) != GIMPLE_PHI
3930 && gimple_bb (def_stmt
) == block
)
3932 if (stmt_may_clobber_ref_p
3933 (def_stmt
, gimple_assign_rhs1 (stmt
)))
3939 = SSA_NAME_DEF_STMT (gimple_vuse (def_stmt
));
3943 operands
.release ();
3948 /* If the load was value-numbered to another
3949 load make sure we do not use its expression
3950 for insertion if it wouldn't be a valid
3952 /* At the momemt we have a testcase
3953 for hoist insertion of aligned vs. misaligned
3954 variants in gcc.dg/torture/pr65270-1.c thus
3955 with just alignment to be considered we can
3956 simply replace the expression in the hashtable
3957 with the most conservative one. */
3958 vn_reference_op_t ref1
= &ref
->operands
.last ();
3959 while (ref1
->opcode
!= TARGET_MEM_REF
3960 && ref1
->opcode
!= MEM_REF
3961 && ref1
!= &ref
->operands
[0])
3963 vn_reference_op_t ref2
= &operands
.last ();
3964 while (ref2
->opcode
!= TARGET_MEM_REF
3965 && ref2
->opcode
!= MEM_REF
3966 && ref2
!= &operands
[0])
3968 if ((ref1
->opcode
== TARGET_MEM_REF
3969 || ref1
->opcode
== MEM_REF
)
3970 && (TYPE_ALIGN (ref1
->type
)
3971 > TYPE_ALIGN (ref2
->type
)))
3973 = build_aligned_type (ref1
->type
,
3974 TYPE_ALIGN (ref2
->type
));
3975 /* TBAA behavior is an obvious part so make sure
3976 that the hashtable one covers this as well
3977 by adjusting the ref alias set and its base. */
3979 || alias_set_subset_of (set
, ref
->set
))
3981 else if (alias_set_subset_of (ref
->set
, set
))
3984 if (ref1
->opcode
== MEM_REF
)
3985 ref1
->op0
= wide_int_to_tree (TREE_TYPE (ref2
->op0
),
3988 ref1
->op2
= wide_int_to_tree (TREE_TYPE (ref2
->op2
),
3994 if (ref1
->opcode
== MEM_REF
)
3995 ref1
->op0
= wide_int_to_tree (ptr_type_node
,
3998 ref1
->op2
= wide_int_to_tree (ptr_type_node
,
4001 operands
.release ();
4003 result
= pre_expr_pool
.allocate ();
4004 result
->kind
= REFERENCE
;
4006 PRE_EXPR_REFERENCE (result
) = ref
;
4014 get_or_alloc_expression_id (result
);
4015 add_to_value (get_expr_value_id (result
), result
);
4016 bitmap_value_insert_into_set (EXP_GEN (block
), result
);
4024 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4026 print_bitmap_set (dump_file
, EXP_GEN (block
),
4027 "exp_gen", block
->index
);
4028 print_bitmap_set (dump_file
, PHI_GEN (block
),
4029 "phi_gen", block
->index
);
4030 print_bitmap_set (dump_file
, TMP_GEN (block
),
4031 "tmp_gen", block
->index
);
4032 print_bitmap_set (dump_file
, AVAIL_OUT (block
),
4033 "avail_out", block
->index
);
4036 /* Put the dominator children of BLOCK on the worklist of blocks
4037 to compute available sets for. */
4038 for (son
= first_dom_son (CDI_DOMINATORS
, block
);
4040 son
= next_dom_son (CDI_DOMINATORS
, son
))
4041 worklist
[sp
++] = son
;
4048 /* Local state for the eliminate domwalk. */
4049 static vec
<gimple
*> el_to_remove
;
4050 static vec
<gimple
*> el_to_fixup
;
4051 static unsigned int el_todo
;
4052 static vec
<tree
> el_avail
;
4053 static vec
<tree
> el_avail_stack
;
4055 /* Return a leader for OP that is available at the current point of the
4056 eliminate domwalk. */
4059 eliminate_avail (tree op
)
4061 tree valnum
= VN_INFO (op
)->valnum
;
4062 if (TREE_CODE (valnum
) == SSA_NAME
)
4064 if (SSA_NAME_IS_DEFAULT_DEF (valnum
))
4066 if (el_avail
.length () > SSA_NAME_VERSION (valnum
))
4067 return el_avail
[SSA_NAME_VERSION (valnum
)];
4069 else if (is_gimple_min_invariant (valnum
))
4074 /* At the current point of the eliminate domwalk make OP available. */
4077 eliminate_push_avail (tree op
)
4079 tree valnum
= VN_INFO (op
)->valnum
;
4080 if (TREE_CODE (valnum
) == SSA_NAME
)
4082 if (el_avail
.length () <= SSA_NAME_VERSION (valnum
))
4083 el_avail
.safe_grow_cleared (SSA_NAME_VERSION (valnum
) + 1);
4085 if (el_avail
[SSA_NAME_VERSION (valnum
)])
4086 pushop
= el_avail
[SSA_NAME_VERSION (valnum
)];
4087 el_avail_stack
.safe_push (pushop
);
4088 el_avail
[SSA_NAME_VERSION (valnum
)] = op
;
4092 /* Insert the expression recorded by SCCVN for VAL at *GSI. Returns
4093 the leader for the expression if insertion was successful. */
4096 eliminate_insert (gimple_stmt_iterator
*gsi
, tree val
)
4098 /* We can insert a sequence with a single assignment only. */
4099 gimple_seq stmts
= VN_INFO (val
)->expr
;
4100 if (!gimple_seq_singleton_p (stmts
))
4102 gassign
*stmt
= dyn_cast
<gassign
*> (gimple_seq_first_stmt (stmts
));
4104 || (!CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (stmt
))
4105 && gimple_assign_rhs_code (stmt
) != VIEW_CONVERT_EXPR
4106 && gimple_assign_rhs_code (stmt
) != BIT_FIELD_REF
4107 && (gimple_assign_rhs_code (stmt
) != BIT_AND_EXPR
4108 || TREE_CODE (gimple_assign_rhs2 (stmt
)) != INTEGER_CST
)))
4111 tree op
= gimple_assign_rhs1 (stmt
);
4112 if (gimple_assign_rhs_code (stmt
) == VIEW_CONVERT_EXPR
4113 || gimple_assign_rhs_code (stmt
) == BIT_FIELD_REF
)
4114 op
= TREE_OPERAND (op
, 0);
4115 tree leader
= TREE_CODE (op
) == SSA_NAME
? eliminate_avail (op
) : op
;
4121 if (gimple_assign_rhs_code (stmt
) == BIT_FIELD_REF
)
4122 res
= gimple_build (&stmts
, BIT_FIELD_REF
,
4123 TREE_TYPE (val
), leader
,
4124 TREE_OPERAND (gimple_assign_rhs1 (stmt
), 1),
4125 TREE_OPERAND (gimple_assign_rhs1 (stmt
), 2));
4126 else if (gimple_assign_rhs_code (stmt
) == BIT_AND_EXPR
)
4127 res
= gimple_build (&stmts
, BIT_AND_EXPR
,
4128 TREE_TYPE (val
), leader
, gimple_assign_rhs2 (stmt
));
4130 res
= gimple_build (&stmts
, gimple_assign_rhs_code (stmt
),
4131 TREE_TYPE (val
), leader
);
4132 if (TREE_CODE (res
) != SSA_NAME
4133 || SSA_NAME_IS_DEFAULT_DEF (res
)
4134 || gimple_bb (SSA_NAME_DEF_STMT (res
)))
4136 gimple_seq_discard (stmts
);
4138 /* During propagation we have to treat SSA info conservatively
4139 and thus we can end up simplifying the inserted expression
4140 at elimination time to sth not defined in stmts. */
4141 /* But then this is a redundancy we failed to detect. Which means
4142 res now has two values. That doesn't play well with how
4143 we track availability here, so give up. */
4144 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4146 if (TREE_CODE (res
) == SSA_NAME
)
4147 res
= eliminate_avail (res
);
4150 fprintf (dump_file
, "Failed to insert expression for value ");
4151 print_generic_expr (dump_file
, val
, 0);
4152 fprintf (dump_file
, " which is really fully redundant to ");
4153 print_generic_expr (dump_file
, res
, 0);
4154 fprintf (dump_file
, "\n");
4162 gsi_insert_seq_before (gsi
, stmts
, GSI_SAME_STMT
);
4163 VN_INFO_GET (res
)->valnum
= val
;
4165 if (TREE_CODE (leader
) == SSA_NAME
)
4166 gimple_set_plf (SSA_NAME_DEF_STMT (leader
), NECESSARY
, true);
4169 pre_stats
.insertions
++;
4170 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4172 fprintf (dump_file
, "Inserted ");
4173 print_gimple_stmt (dump_file
, SSA_NAME_DEF_STMT (res
), 0, 0);
4179 class eliminate_dom_walker
: public dom_walker
4182 eliminate_dom_walker (cdi_direction direction
, bool do_pre_
)
4183 : dom_walker (direction
), do_pre (do_pre_
) {}
4185 virtual edge
before_dom_children (basic_block
);
4186 virtual void after_dom_children (basic_block
);
4191 /* Perform elimination for the basic-block B during the domwalk. */
4194 eliminate_dom_walker::before_dom_children (basic_block b
)
4197 el_avail_stack
.safe_push (NULL_TREE
);
4199 /* Skip unreachable blocks marked unreachable during the SCCVN domwalk. */
4202 FOR_EACH_EDGE (e
, ei
, b
->preds
)
4203 if (e
->flags
& EDGE_EXECUTABLE
)
4208 for (gphi_iterator gsi
= gsi_start_phis (b
); !gsi_end_p (gsi
);)
4210 gphi
*phi
= gsi
.phi ();
4211 tree res
= PHI_RESULT (phi
);
4213 if (virtual_operand_p (res
))
4219 tree sprime
= eliminate_avail (res
);
4223 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4225 fprintf (dump_file
, "Replaced redundant PHI node defining ");
4226 print_generic_expr (dump_file
, res
, 0);
4227 fprintf (dump_file
, " with ");
4228 print_generic_expr (dump_file
, sprime
, 0);
4229 fprintf (dump_file
, "\n");
4232 /* If we inserted this PHI node ourself, it's not an elimination. */
4234 && bitmap_bit_p (inserted_exprs
, SSA_NAME_VERSION (res
)))
4237 pre_stats
.eliminations
++;
4239 /* If we will propagate into all uses don't bother to do
4241 if (may_propagate_copy (res
, sprime
))
4243 /* Mark the PHI for removal. */
4244 el_to_remove
.safe_push (phi
);
4249 remove_phi_node (&gsi
, false);
4252 && !bitmap_bit_p (inserted_exprs
, SSA_NAME_VERSION (res
))
4253 && TREE_CODE (sprime
) == SSA_NAME
)
4254 gimple_set_plf (SSA_NAME_DEF_STMT (sprime
), NECESSARY
, true);
4256 if (!useless_type_conversion_p (TREE_TYPE (res
), TREE_TYPE (sprime
)))
4257 sprime
= fold_convert (TREE_TYPE (res
), sprime
);
4258 gimple
*stmt
= gimple_build_assign (res
, sprime
);
4259 /* ??? It cannot yet be necessary (DOM walk). */
4260 gimple_set_plf (stmt
, NECESSARY
, gimple_plf (phi
, NECESSARY
));
4262 gimple_stmt_iterator gsi2
= gsi_after_labels (b
);
4263 gsi_insert_before (&gsi2
, stmt
, GSI_NEW_STMT
);
4267 eliminate_push_avail (res
);
4271 for (gimple_stmt_iterator gsi
= gsi_start_bb (b
);
4275 tree sprime
= NULL_TREE
;
4276 gimple
*stmt
= gsi_stmt (gsi
);
4277 tree lhs
= gimple_get_lhs (stmt
);
4278 if (lhs
&& TREE_CODE (lhs
) == SSA_NAME
4279 && !gimple_has_volatile_ops (stmt
)
4280 /* See PR43491. Do not replace a global register variable when
4281 it is a the RHS of an assignment. Do replace local register
4282 variables since gcc does not guarantee a local variable will
4283 be allocated in register.
4284 ??? The fix isn't effective here. This should instead
4285 be ensured by not value-numbering them the same but treating
4286 them like volatiles? */
4287 && !(gimple_assign_single_p (stmt
)
4288 && (TREE_CODE (gimple_assign_rhs1 (stmt
)) == VAR_DECL
4289 && DECL_HARD_REGISTER (gimple_assign_rhs1 (stmt
))
4290 && is_global_var (gimple_assign_rhs1 (stmt
)))))
4292 sprime
= eliminate_avail (lhs
);
4295 /* If there is no existing usable leader but SCCVN thinks
4296 it has an expression it wants to use as replacement,
4298 tree val
= VN_INFO (lhs
)->valnum
;
4300 && TREE_CODE (val
) == SSA_NAME
4301 && VN_INFO (val
)->needs_insertion
4302 && VN_INFO (val
)->expr
!= NULL
4303 && (sprime
= eliminate_insert (&gsi
, val
)) != NULL_TREE
)
4304 eliminate_push_avail (sprime
);
4307 /* If this now constitutes a copy duplicate points-to
4308 and range info appropriately. This is especially
4309 important for inserted code. See tree-ssa-copy.c
4310 for similar code. */
4312 && TREE_CODE (sprime
) == SSA_NAME
)
4314 basic_block sprime_b
= gimple_bb (SSA_NAME_DEF_STMT (sprime
));
4315 if (POINTER_TYPE_P (TREE_TYPE (lhs
))
4316 && VN_INFO_PTR_INFO (lhs
)
4317 && ! VN_INFO_PTR_INFO (sprime
))
4319 duplicate_ssa_name_ptr_info (sprime
,
4320 VN_INFO_PTR_INFO (lhs
));
4322 mark_ptr_info_alignment_unknown
4323 (SSA_NAME_PTR_INFO (sprime
));
4325 else if (INTEGRAL_TYPE_P (TREE_TYPE (lhs
))
4326 && VN_INFO_RANGE_INFO (lhs
)
4327 && ! VN_INFO_RANGE_INFO (sprime
)
4329 duplicate_ssa_name_range_info (sprime
,
4330 VN_INFO_RANGE_TYPE (lhs
),
4331 VN_INFO_RANGE_INFO (lhs
));
4334 /* Inhibit the use of an inserted PHI on a loop header when
4335 the address of the memory reference is a simple induction
4336 variable. In other cases the vectorizer won't do anything
4337 anyway (either it's loop invariant or a complicated
4340 && TREE_CODE (sprime
) == SSA_NAME
4342 && (flag_tree_loop_vectorize
|| flag_tree_parallelize_loops
> 1)
4343 && loop_outer (b
->loop_father
)
4344 && has_zero_uses (sprime
)
4345 && bitmap_bit_p (inserted_exprs
, SSA_NAME_VERSION (sprime
))
4346 && gimple_assign_load_p (stmt
))
4348 gimple
*def_stmt
= SSA_NAME_DEF_STMT (sprime
);
4349 basic_block def_bb
= gimple_bb (def_stmt
);
4350 if (gimple_code (def_stmt
) == GIMPLE_PHI
4351 && def_bb
->loop_father
->header
== def_bb
)
4353 loop_p loop
= def_bb
->loop_father
;
4357 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, iter
, SSA_OP_USE
)
4360 def_bb
= gimple_bb (SSA_NAME_DEF_STMT (op
));
4362 && flow_bb_inside_loop_p (loop
, def_bb
)
4363 && simple_iv (loop
, loop
, op
, &iv
, true))
4371 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4373 fprintf (dump_file
, "Not replacing ");
4374 print_gimple_expr (dump_file
, stmt
, 0, 0);
4375 fprintf (dump_file
, " with ");
4376 print_generic_expr (dump_file
, sprime
, 0);
4377 fprintf (dump_file
, " which would add a loop"
4378 " carried dependence to loop %d\n",
4381 /* Don't keep sprime available. */
4389 /* If we can propagate the value computed for LHS into
4390 all uses don't bother doing anything with this stmt. */
4391 if (may_propagate_copy (lhs
, sprime
))
4393 /* Mark it for removal. */
4394 el_to_remove
.safe_push (stmt
);
4396 /* ??? Don't count copy/constant propagations. */
4397 if (gimple_assign_single_p (stmt
)
4398 && (TREE_CODE (gimple_assign_rhs1 (stmt
)) == SSA_NAME
4399 || gimple_assign_rhs1 (stmt
) == sprime
))
4402 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4404 fprintf (dump_file
, "Replaced ");
4405 print_gimple_expr (dump_file
, stmt
, 0, 0);
4406 fprintf (dump_file
, " with ");
4407 print_generic_expr (dump_file
, sprime
, 0);
4408 fprintf (dump_file
, " in all uses of ");
4409 print_gimple_stmt (dump_file
, stmt
, 0, 0);
4412 pre_stats
.eliminations
++;
4416 /* If this is an assignment from our leader (which
4417 happens in the case the value-number is a constant)
4418 then there is nothing to do. */
4419 if (gimple_assign_single_p (stmt
)
4420 && sprime
== gimple_assign_rhs1 (stmt
))
4423 /* Else replace its RHS. */
4424 bool can_make_abnormal_goto
4425 = is_gimple_call (stmt
)
4426 && stmt_can_make_abnormal_goto (stmt
);
4428 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4430 fprintf (dump_file
, "Replaced ");
4431 print_gimple_expr (dump_file
, stmt
, 0, 0);
4432 fprintf (dump_file
, " with ");
4433 print_generic_expr (dump_file
, sprime
, 0);
4434 fprintf (dump_file
, " in ");
4435 print_gimple_stmt (dump_file
, stmt
, 0, 0);
4438 if (TREE_CODE (sprime
) == SSA_NAME
)
4439 gimple_set_plf (SSA_NAME_DEF_STMT (sprime
),
4442 pre_stats
.eliminations
++;
4443 gimple
*orig_stmt
= stmt
;
4444 if (!useless_type_conversion_p (TREE_TYPE (lhs
),
4445 TREE_TYPE (sprime
)))
4446 sprime
= fold_convert (TREE_TYPE (lhs
), sprime
);
4447 tree vdef
= gimple_vdef (stmt
);
4448 tree vuse
= gimple_vuse (stmt
);
4449 propagate_tree_value_into_stmt (&gsi
, sprime
);
4450 stmt
= gsi_stmt (gsi
);
4452 if (vdef
!= gimple_vdef (stmt
))
4453 VN_INFO (vdef
)->valnum
= vuse
;
4455 /* If we removed EH side-effects from the statement, clean
4456 its EH information. */
4457 if (maybe_clean_or_replace_eh_stmt (orig_stmt
, stmt
))
4459 bitmap_set_bit (need_eh_cleanup
,
4460 gimple_bb (stmt
)->index
);
4461 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4462 fprintf (dump_file
, " Removed EH side-effects.\n");
4465 /* Likewise for AB side-effects. */
4466 if (can_make_abnormal_goto
4467 && !stmt_can_make_abnormal_goto (stmt
))
4469 bitmap_set_bit (need_ab_cleanup
,
4470 gimple_bb (stmt
)->index
);
4471 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4472 fprintf (dump_file
, " Removed AB side-effects.\n");
4479 /* If the statement is a scalar store, see if the expression
4480 has the same value number as its rhs. If so, the store is
4482 if (gimple_assign_single_p (stmt
)
4483 && !gimple_has_volatile_ops (stmt
)
4484 && !is_gimple_reg (gimple_assign_lhs (stmt
))
4485 && (TREE_CODE (gimple_assign_rhs1 (stmt
)) == SSA_NAME
4486 || is_gimple_min_invariant (gimple_assign_rhs1 (stmt
))))
4489 tree rhs
= gimple_assign_rhs1 (stmt
);
4490 vn_reference_t vnresult
;
4491 val
= vn_reference_lookup (lhs
, gimple_vuse (stmt
), VN_WALKREWRITE
,
4493 if (TREE_CODE (rhs
) == SSA_NAME
)
4494 rhs
= VN_INFO (rhs
)->valnum
;
4496 && operand_equal_p (val
, rhs
, 0))
4498 /* We can only remove the later store if the former aliases
4499 at least all accesses the later one does or if the store
4500 was to readonly memory storing the same value. */
4501 alias_set_type set
= get_alias_set (lhs
);
4503 || vnresult
->set
== set
4504 || alias_set_subset_of (set
, vnresult
->set
))
4506 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4508 fprintf (dump_file
, "Deleted redundant store ");
4509 print_gimple_stmt (dump_file
, stmt
, 0, 0);
4512 /* Queue stmt for removal. */
4513 el_to_remove
.safe_push (stmt
);
4519 /* If this is a control statement value numbering left edges
4520 unexecuted on force the condition in a way consistent with
4522 if (gcond
*cond
= dyn_cast
<gcond
*> (stmt
))
4524 if ((EDGE_SUCC (b
, 0)->flags
& EDGE_EXECUTABLE
)
4525 ^ (EDGE_SUCC (b
, 1)->flags
& EDGE_EXECUTABLE
))
4527 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4529 fprintf (dump_file
, "Removing unexecutable edge from ");
4530 print_gimple_stmt (dump_file
, stmt
, 0, 0);
4532 if (((EDGE_SUCC (b
, 0)->flags
& EDGE_TRUE_VALUE
) != 0)
4533 == ((EDGE_SUCC (b
, 0)->flags
& EDGE_EXECUTABLE
) != 0))
4534 gimple_cond_make_true (cond
);
4536 gimple_cond_make_false (cond
);
4538 el_todo
|= TODO_cleanup_cfg
;
4543 bool can_make_abnormal_goto
= stmt_can_make_abnormal_goto (stmt
);
4544 bool was_noreturn
= (is_gimple_call (stmt
)
4545 && gimple_call_noreturn_p (stmt
));
4546 tree vdef
= gimple_vdef (stmt
);
4547 tree vuse
= gimple_vuse (stmt
);
4549 /* If we didn't replace the whole stmt (or propagate the result
4550 into all uses), replace all uses on this stmt with their
4552 use_operand_p use_p
;
4554 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, iter
, SSA_OP_USE
)
4556 tree use
= USE_FROM_PTR (use_p
);
4557 /* ??? The call code above leaves stmt operands un-updated. */
4558 if (TREE_CODE (use
) != SSA_NAME
)
4560 tree sprime
= eliminate_avail (use
);
4561 if (sprime
&& sprime
!= use
4562 && may_propagate_copy (use
, sprime
)
4563 /* We substitute into debug stmts to avoid excessive
4564 debug temporaries created by removed stmts, but we need
4565 to avoid doing so for inserted sprimes as we never want
4566 to create debug temporaries for them. */
4568 || TREE_CODE (sprime
) != SSA_NAME
4569 || !is_gimple_debug (stmt
)
4570 || !bitmap_bit_p (inserted_exprs
, SSA_NAME_VERSION (sprime
))))
4572 propagate_value (use_p
, sprime
);
4573 gimple_set_modified (stmt
, true);
4574 if (TREE_CODE (sprime
) == SSA_NAME
4575 && !is_gimple_debug (stmt
))
4576 gimple_set_plf (SSA_NAME_DEF_STMT (sprime
),
4581 /* Visit indirect calls and turn them into direct calls if
4582 possible using the devirtualization machinery. */
4583 if (gcall
*call_stmt
= dyn_cast
<gcall
*> (stmt
))
4585 tree fn
= gimple_call_fn (call_stmt
);
4587 && flag_devirtualize
4588 && virtual_method_call_p (fn
))
4590 tree otr_type
= obj_type_ref_class (fn
);
4592 ipa_polymorphic_call_context
context (current_function_decl
, fn
, stmt
, &instance
);
4595 context
.get_dynamic_type (instance
, OBJ_TYPE_REF_OBJECT (fn
), otr_type
, stmt
);
4597 vec
<cgraph_node
*>targets
4598 = possible_polymorphic_call_targets (obj_type_ref_class (fn
),
4600 (OBJ_TYPE_REF_TOKEN (fn
)),
4604 dump_possible_polymorphic_call_targets (dump_file
,
4605 obj_type_ref_class (fn
),
4607 (OBJ_TYPE_REF_TOKEN (fn
)),
4609 if (final
&& targets
.length () <= 1 && dbg_cnt (devirt
))
4612 if (targets
.length () == 1)
4613 fn
= targets
[0]->decl
;
4615 fn
= builtin_decl_implicit (BUILT_IN_UNREACHABLE
);
4616 if (dump_enabled_p ())
4618 location_t loc
= gimple_location_safe (stmt
);
4619 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS
, loc
,
4620 "converting indirect call to "
4622 lang_hooks
.decl_printable_name (fn
, 2));
4624 gimple_call_set_fndecl (call_stmt
, fn
);
4625 /* If changing the call to __builtin_unreachable
4626 or similar noreturn function, adjust gimple_call_fntype
4628 if (gimple_call_noreturn_p (call_stmt
)
4629 && VOID_TYPE_P (TREE_TYPE (TREE_TYPE (fn
)))
4630 && TYPE_ARG_TYPES (TREE_TYPE (fn
))
4631 && (TREE_VALUE (TYPE_ARG_TYPES (TREE_TYPE (fn
)))
4633 gimple_call_set_fntype (call_stmt
, TREE_TYPE (fn
));
4634 maybe_remove_unused_call_args (cfun
, call_stmt
);
4635 gimple_set_modified (stmt
, true);
4640 if (gimple_modified_p (stmt
))
4642 /* If a formerly non-invariant ADDR_EXPR is turned into an
4643 invariant one it was on a separate stmt. */
4644 if (gimple_assign_single_p (stmt
)
4645 && TREE_CODE (gimple_assign_rhs1 (stmt
)) == ADDR_EXPR
)
4646 recompute_tree_invariant_for_addr_expr (gimple_assign_rhs1 (stmt
));
4647 gimple
*old_stmt
= stmt
;
4648 if (is_gimple_call (stmt
))
4650 /* ??? Only fold calls inplace for now, this may create new
4651 SSA names which in turn will confuse free_scc_vn SSA name
4653 fold_stmt_inplace (&gsi
);
4654 /* When changing a call into a noreturn call, cfg cleanup
4655 is needed to fix up the noreturn call. */
4656 if (!was_noreturn
&& gimple_call_noreturn_p (stmt
))
4657 el_to_fixup
.safe_push (stmt
);
4662 stmt
= gsi_stmt (gsi
);
4663 if ((gimple_code (stmt
) == GIMPLE_COND
4664 && (gimple_cond_true_p (as_a
<gcond
*> (stmt
))
4665 || gimple_cond_false_p (as_a
<gcond
*> (stmt
))))
4666 || (gimple_code (stmt
) == GIMPLE_SWITCH
4667 && TREE_CODE (gimple_switch_index (
4668 as_a
<gswitch
*> (stmt
)))
4670 el_todo
|= TODO_cleanup_cfg
;
4672 /* If we removed EH side-effects from the statement, clean
4673 its EH information. */
4674 if (maybe_clean_or_replace_eh_stmt (old_stmt
, stmt
))
4676 bitmap_set_bit (need_eh_cleanup
,
4677 gimple_bb (stmt
)->index
);
4678 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4679 fprintf (dump_file
, " Removed EH side-effects.\n");
4681 /* Likewise for AB side-effects. */
4682 if (can_make_abnormal_goto
4683 && !stmt_can_make_abnormal_goto (stmt
))
4685 bitmap_set_bit (need_ab_cleanup
,
4686 gimple_bb (stmt
)->index
);
4687 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4688 fprintf (dump_file
, " Removed AB side-effects.\n");
4691 if (vdef
!= gimple_vdef (stmt
))
4692 VN_INFO (vdef
)->valnum
= vuse
;
4695 /* Make new values available - for fully redundant LHS we
4696 continue with the next stmt above and skip this. */
4698 FOR_EACH_SSA_DEF_OPERAND (defp
, stmt
, iter
, SSA_OP_DEF
)
4699 eliminate_push_avail (DEF_FROM_PTR (defp
));
4702 /* Replace destination PHI arguments. */
4703 FOR_EACH_EDGE (e
, ei
, b
->succs
)
4704 if (e
->flags
& EDGE_EXECUTABLE
)
4705 for (gphi_iterator gsi
= gsi_start_phis (e
->dest
);
4709 gphi
*phi
= gsi
.phi ();
4710 use_operand_p use_p
= PHI_ARG_DEF_PTR_FROM_EDGE (phi
, e
);
4711 tree arg
= USE_FROM_PTR (use_p
);
4712 if (TREE_CODE (arg
) != SSA_NAME
4713 || virtual_operand_p (arg
))
4715 tree sprime
= eliminate_avail (arg
);
4716 if (sprime
&& may_propagate_copy (arg
, sprime
))
4718 propagate_value (use_p
, sprime
);
4719 if (TREE_CODE (sprime
) == SSA_NAME
)
4720 gimple_set_plf (SSA_NAME_DEF_STMT (sprime
), NECESSARY
, true);
4726 /* Make no longer available leaders no longer available. */
4729 eliminate_dom_walker::after_dom_children (basic_block
)
4732 while ((entry
= el_avail_stack
.pop ()) != NULL_TREE
)
4734 tree valnum
= VN_INFO (entry
)->valnum
;
4735 tree old
= el_avail
[SSA_NAME_VERSION (valnum
)];
4737 el_avail
[SSA_NAME_VERSION (valnum
)] = NULL_TREE
;
4739 el_avail
[SSA_NAME_VERSION (valnum
)] = entry
;
4743 /* Eliminate fully redundant computations. */
4746 eliminate (bool do_pre
)
4748 need_eh_cleanup
= BITMAP_ALLOC (NULL
);
4749 need_ab_cleanup
= BITMAP_ALLOC (NULL
);
4751 el_to_remove
.create (0);
4752 el_to_fixup
.create (0);
4754 el_avail
.create (num_ssa_names
);
4755 el_avail_stack
.create (0);
4757 eliminate_dom_walker (CDI_DOMINATORS
,
4758 do_pre
).walk (cfun
->cfg
->x_entry_block_ptr
);
4760 el_avail
.release ();
4761 el_avail_stack
.release ();
4766 /* Perform CFG cleanups made necessary by elimination. */
4769 fini_eliminate (void)
4771 gimple_stmt_iterator gsi
;
4775 /* We cannot remove stmts during BB walk, especially not release SSA
4776 names there as this confuses the VN machinery. The stmts ending
4777 up in el_to_remove are either stores or simple copies.
4778 Remove stmts in reverse order to make debug stmt creation possible. */
4779 while (!el_to_remove
.is_empty ())
4781 stmt
= el_to_remove
.pop ();
4784 if (gimple_code (stmt
) == GIMPLE_PHI
)
4785 lhs
= gimple_phi_result (stmt
);
4787 lhs
= gimple_get_lhs (stmt
);
4790 && TREE_CODE (lhs
) == SSA_NAME
4791 && bitmap_bit_p (inserted_exprs
, SSA_NAME_VERSION (lhs
)))
4794 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4796 fprintf (dump_file
, "Removing dead stmt ");
4797 print_gimple_stmt (dump_file
, stmt
, 0, 0);
4800 gsi
= gsi_for_stmt (stmt
);
4801 if (gimple_code (stmt
) == GIMPLE_PHI
)
4802 remove_phi_node (&gsi
, true);
4805 basic_block bb
= gimple_bb (stmt
);
4806 unlink_stmt_vdef (stmt
);
4807 if (gsi_remove (&gsi
, true))
4808 bitmap_set_bit (need_eh_cleanup
, bb
->index
);
4809 if (is_gimple_call (stmt
) && stmt_can_make_abnormal_goto (stmt
))
4810 bitmap_set_bit (need_ab_cleanup
, bb
->index
);
4811 release_defs (stmt
);
4814 /* Removing a stmt may expose a forwarder block. */
4815 todo
|= TODO_cleanup_cfg
;
4817 el_to_remove
.release ();
4819 /* Fixup stmts that became noreturn calls. This may require splitting
4820 blocks and thus isn't possible during the dominator walk. Do this
4821 in reverse order so we don't inadvertedly remove a stmt we want to
4822 fixup by visiting a dominating now noreturn call first. */
4823 while (!el_to_fixup
.is_empty ())
4825 stmt
= el_to_fixup
.pop ();
4827 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4829 fprintf (dump_file
, "Fixing up noreturn call ");
4830 print_gimple_stmt (dump_file
, stmt
, 0, 0);
4833 if (fixup_noreturn_call (stmt
))
4834 todo
|= TODO_cleanup_cfg
;
4836 el_to_fixup
.release ();
4838 bool do_eh_cleanup
= !bitmap_empty_p (need_eh_cleanup
);
4839 bool do_ab_cleanup
= !bitmap_empty_p (need_ab_cleanup
);
4842 gimple_purge_all_dead_eh_edges (need_eh_cleanup
);
4845 gimple_purge_all_dead_abnormal_call_edges (need_ab_cleanup
);
4847 BITMAP_FREE (need_eh_cleanup
);
4848 BITMAP_FREE (need_ab_cleanup
);
4850 if (do_eh_cleanup
|| do_ab_cleanup
)
4851 todo
|= TODO_cleanup_cfg
;
4855 /* Borrow a bit of tree-ssa-dce.c for the moment.
4856 XXX: In 4.1, we should be able to just run a DCE pass after PRE, though
4857 this may be a bit faster, and we may want critical edges kept split. */
4859 /* If OP's defining statement has not already been determined to be necessary,
4860 mark that statement necessary. Return the stmt, if it is newly
4863 static inline gimple
*
4864 mark_operand_necessary (tree op
)
4870 if (TREE_CODE (op
) != SSA_NAME
)
4873 stmt
= SSA_NAME_DEF_STMT (op
);
4876 if (gimple_plf (stmt
, NECESSARY
)
4877 || gimple_nop_p (stmt
))
4880 gimple_set_plf (stmt
, NECESSARY
, true);
4884 /* Because we don't follow exactly the standard PRE algorithm, and decide not
4885 to insert PHI nodes sometimes, and because value numbering of casts isn't
4886 perfect, we sometimes end up inserting dead code. This simple DCE-like
4887 pass removes any insertions we made that weren't actually used. */
4890 remove_dead_inserted_code (void)
4897 worklist
= BITMAP_ALLOC (NULL
);
4898 EXECUTE_IF_SET_IN_BITMAP (inserted_exprs
, 0, i
, bi
)
4900 t
= SSA_NAME_DEF_STMT (ssa_name (i
));
4901 if (gimple_plf (t
, NECESSARY
))
4902 bitmap_set_bit (worklist
, i
);
4904 while (!bitmap_empty_p (worklist
))
4906 i
= bitmap_first_set_bit (worklist
);
4907 bitmap_clear_bit (worklist
, i
);
4908 t
= SSA_NAME_DEF_STMT (ssa_name (i
));
4910 /* PHI nodes are somewhat special in that each PHI alternative has
4911 data and control dependencies. All the statements feeding the
4912 PHI node's arguments are always necessary. */
4913 if (gimple_code (t
) == GIMPLE_PHI
)
4917 for (k
= 0; k
< gimple_phi_num_args (t
); k
++)
4919 tree arg
= PHI_ARG_DEF (t
, k
);
4920 if (TREE_CODE (arg
) == SSA_NAME
)
4922 gimple
*n
= mark_operand_necessary (arg
);
4924 bitmap_set_bit (worklist
, SSA_NAME_VERSION (arg
));
4930 /* Propagate through the operands. Examine all the USE, VUSE and
4931 VDEF operands in this statement. Mark all the statements
4932 which feed this statement's uses as necessary. */
4936 /* The operands of VDEF expressions are also needed as they
4937 represent potential definitions that may reach this
4938 statement (VDEF operands allow us to follow def-def
4941 FOR_EACH_SSA_TREE_OPERAND (use
, t
, iter
, SSA_OP_ALL_USES
)
4943 gimple
*n
= mark_operand_necessary (use
);
4945 bitmap_set_bit (worklist
, SSA_NAME_VERSION (use
));
4950 unsigned int to_clear
= -1U;
4951 EXECUTE_IF_SET_IN_BITMAP (inserted_exprs
, 0, i
, bi
)
4953 if (to_clear
!= -1U)
4955 bitmap_clear_bit (inserted_exprs
, to_clear
);
4958 t
= SSA_NAME_DEF_STMT (ssa_name (i
));
4959 if (!gimple_plf (t
, NECESSARY
))
4961 gimple_stmt_iterator gsi
;
4963 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4965 fprintf (dump_file
, "Removing unnecessary insertion:");
4966 print_gimple_stmt (dump_file
, t
, 0, 0);
4969 gsi
= gsi_for_stmt (t
);
4970 if (gimple_code (t
) == GIMPLE_PHI
)
4971 remove_phi_node (&gsi
, true);
4974 gsi_remove (&gsi
, true);
4979 /* eliminate_fini will skip stmts marked for removal if we
4980 already removed it and uses inserted_exprs for this, so
4981 clear those we didn't end up removing. */
4984 if (to_clear
!= -1U)
4985 bitmap_clear_bit (inserted_exprs
, to_clear
);
4986 BITMAP_FREE (worklist
);
4990 /* Initialize data structures used by PRE. */
4997 next_expression_id
= 1;
4998 expressions
.create (0);
4999 expressions
.safe_push (NULL
);
5000 value_expressions
.create (get_max_value_id () + 1);
5001 value_expressions
.safe_grow_cleared (get_max_value_id () + 1);
5002 name_to_id
.create (0);
5004 inserted_exprs
= BITMAP_ALLOC (NULL
);
5006 connect_infinite_loops_to_exit ();
5007 memset (&pre_stats
, 0, sizeof (pre_stats
));
5009 alloc_aux_for_blocks (sizeof (struct bb_bitmap_sets
));
5011 calculate_dominance_info (CDI_DOMINATORS
);
5013 bitmap_obstack_initialize (&grand_bitmap_obstack
);
5014 phi_translate_table
= new hash_table
<expr_pred_trans_d
> (5110);
5015 expression_to_id
= new hash_table
<pre_expr_d
> (num_ssa_names
* 3);
5016 FOR_ALL_BB_FN (bb
, cfun
)
5018 EXP_GEN (bb
) = bitmap_set_new ();
5019 PHI_GEN (bb
) = bitmap_set_new ();
5020 TMP_GEN (bb
) = bitmap_set_new ();
5021 AVAIL_OUT (bb
) = bitmap_set_new ();
5026 /* Deallocate data structures used by PRE. */
5031 value_expressions
.release ();
5032 BITMAP_FREE (inserted_exprs
);
5033 bitmap_obstack_release (&grand_bitmap_obstack
);
5034 bitmap_set_pool
.release ();
5035 pre_expr_pool
.release ();
5036 delete phi_translate_table
;
5037 phi_translate_table
= NULL
;
5038 delete expression_to_id
;
5039 expression_to_id
= NULL
;
5040 name_to_id
.release ();
5042 free_aux_for_blocks ();
5047 const pass_data pass_data_pre
=
5049 GIMPLE_PASS
, /* type */
5051 OPTGROUP_NONE
, /* optinfo_flags */
5052 TV_TREE_PRE
, /* tv_id */
5053 /* PROP_no_crit_edges is ensured by placing pass_split_crit_edges before
5055 ( PROP_no_crit_edges
| PROP_cfg
| PROP_ssa
), /* properties_required */
5056 0, /* properties_provided */
5057 PROP_no_crit_edges
, /* properties_destroyed */
5058 TODO_rebuild_alias
, /* todo_flags_start */
5059 0, /* todo_flags_finish */
5062 class pass_pre
: public gimple_opt_pass
5065 pass_pre (gcc::context
*ctxt
)
5066 : gimple_opt_pass (pass_data_pre
, ctxt
)
5069 /* opt_pass methods: */
5070 virtual bool gate (function
*)
5071 { return flag_tree_pre
!= 0 || flag_code_hoisting
!= 0; }
5072 virtual unsigned int execute (function
*);
5074 }; // class pass_pre
5077 pass_pre::execute (function
*fun
)
5079 unsigned int todo
= 0;
5081 do_partial_partial
=
5082 flag_tree_partial_pre
&& optimize_function_for_speed_p (fun
);
5084 /* This has to happen before SCCVN runs because
5085 loop_optimizer_init may create new phis, etc. */
5086 loop_optimizer_init (LOOPS_NORMAL
);
5088 run_scc_vn (VN_WALK
);
5093 /* Collect and value number expressions computed in each basic block. */
5096 /* Insert can get quite slow on an incredibly large number of basic
5097 blocks due to some quadratic behavior. Until this behavior is
5098 fixed, don't run it when he have an incredibly large number of
5099 bb's. If we aren't going to run insert, there is no point in
5100 computing ANTIC, either, even though it's plenty fast. */
5101 if (n_basic_blocks_for_fn (fun
) < 4000)
5107 /* Make sure to remove fake edges before committing our inserts.
5108 This makes sure we don't end up with extra critical edges that
5109 we would need to split. */
5110 remove_fake_exit_edges ();
5111 gsi_commit_edge_inserts ();
5113 /* Eliminate folds statements which might (should not...) end up
5114 not keeping virtual operands up-to-date. */
5115 gcc_assert (!need_ssa_update_p (fun
));
5117 /* Remove all the redundant expressions. */
5118 todo
|= eliminate (true);
5120 statistics_counter_event (fun
, "Insertions", pre_stats
.insertions
);
5121 statistics_counter_event (fun
, "PA inserted", pre_stats
.pa_insert
);
5122 statistics_counter_event (fun
, "HOIST inserted", pre_stats
.hoist_insert
);
5123 statistics_counter_event (fun
, "New PHIs", pre_stats
.phis
);
5124 statistics_counter_event (fun
, "Eliminated", pre_stats
.eliminations
);
5126 clear_expression_ids ();
5127 remove_dead_inserted_code ();
5130 todo
|= fini_eliminate ();
5132 loop_optimizer_finalize ();
5134 /* Restore SSA info before tail-merging as that resets it as well. */
5135 scc_vn_restore_ssa_info ();
5137 /* TODO: tail_merge_optimize may merge all predecessors of a block, in which
5138 case we can merge the block with the remaining predecessor of the block.
5140 - call merge_blocks after each tail merge iteration
5141 - call merge_blocks after all tail merge iterations
5142 - mark TODO_cleanup_cfg when necessary
5143 - share the cfg cleanup with fini_pre. */
5144 todo
|= tail_merge_optimize (todo
);
5148 /* Tail merging invalidates the virtual SSA web, together with
5149 cfg-cleanup opportunities exposed by PRE this will wreck the
5150 SSA updating machinery. So make sure to run update-ssa
5151 manually, before eventually scheduling cfg-cleanup as part of
5153 update_ssa (TODO_update_ssa_only_virtuals
);
5161 make_pass_pre (gcc::context
*ctxt
)
5163 return new pass_pre (ctxt
);
5168 const pass_data pass_data_fre
=
5170 GIMPLE_PASS
, /* type */
5172 OPTGROUP_NONE
, /* optinfo_flags */
5173 TV_TREE_FRE
, /* tv_id */
5174 ( PROP_cfg
| PROP_ssa
), /* properties_required */
5175 0, /* properties_provided */
5176 0, /* properties_destroyed */
5177 0, /* todo_flags_start */
5178 0, /* todo_flags_finish */
5181 class pass_fre
: public gimple_opt_pass
5184 pass_fre (gcc::context
*ctxt
)
5185 : gimple_opt_pass (pass_data_fre
, ctxt
)
5188 /* opt_pass methods: */
5189 opt_pass
* clone () { return new pass_fre (m_ctxt
); }
5190 virtual bool gate (function
*) { return flag_tree_fre
!= 0; }
5191 virtual unsigned int execute (function
*);
5193 }; // class pass_fre
5196 pass_fre::execute (function
*fun
)
5198 unsigned int todo
= 0;
5200 run_scc_vn (VN_WALKREWRITE
);
5202 memset (&pre_stats
, 0, sizeof (pre_stats
));
5204 /* Remove all the redundant expressions. */
5205 todo
|= eliminate (false);
5207 todo
|= fini_eliminate ();
5209 scc_vn_restore_ssa_info ();
5212 statistics_counter_event (fun
, "Insertions", pre_stats
.insertions
);
5213 statistics_counter_event (fun
, "Eliminated", pre_stats
.eliminations
);
5221 make_pass_fre (gcc::context
*ctxt
)
5223 return new pass_fre (ctxt
);