2 Copyright (C) 2001-2015 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"
33 #include "fold-const.h"
35 #include "hard-reg-set.h"
37 #include "dominance.h"
40 #include "basic-block.h"
41 #include "gimple-pretty-print.h"
42 #include "tree-inline.h"
43 #include "hash-table.h"
44 #include "tree-ssa-alias.h"
45 #include "internal-fn.h"
46 #include "gimple-fold.h"
48 #include "gimple-expr.h"
52 #include "gimple-iterator.h"
53 #include "gimplify-me.h"
54 #include "gimple-ssa.h"
56 #include "tree-phinodes.h"
57 #include "ssa-iterators.h"
58 #include "stringpool.h"
59 #include "tree-ssanames.h"
60 #include "tree-ssa-loop.h"
61 #include "tree-into-ssa.h"
65 #include "statistics.h"
66 #include "insn-config.h"
77 #include "tree-iterator.h"
78 #include "alloc-pool.h"
80 #include "tree-pass.h"
81 #include "langhooks.h"
83 #include "tree-ssa-sccvn.h"
84 #include "tree-scalar-evolution.h"
89 #include "plugin-api.h"
92 #include "symbol-summary.h"
94 #include "tree-ssa-propagate.h"
95 #include "ipa-utils.h"
96 #include "tree-cfgcleanup.h"
100 1. Avail sets can be shared by making an avail_find_leader that
101 walks up the dominator tree and looks in those avail sets.
102 This might affect code optimality, it's unclear right now.
103 2. Strength reduction can be performed by anticipating expressions
104 we can repair later on.
105 3. We can do back-substitution or smarter value numbering to catch
106 commutative expressions split up over multiple statements.
109 /* For ease of terminology, "expression node" in the below refers to
110 every expression node but GIMPLE_ASSIGN, because GIMPLE_ASSIGNs
111 represent the actual statement containing the expressions we care about,
112 and we cache the value number by putting it in the expression. */
116 First we walk the statements to generate the AVAIL sets, the
117 EXP_GEN sets, and the tmp_gen sets. EXP_GEN sets represent the
118 generation of values/expressions by a given block. We use them
119 when computing the ANTIC sets. The AVAIL sets consist of
120 SSA_NAME's that represent values, so we know what values are
121 available in what blocks. AVAIL is a forward dataflow problem. In
122 SSA, values are never killed, so we don't need a kill set, or a
123 fixpoint iteration, in order to calculate the AVAIL sets. In
124 traditional parlance, AVAIL sets tell us the downsafety of the
127 Next, we generate the ANTIC sets. These sets represent the
128 anticipatable expressions. ANTIC is a backwards dataflow
129 problem. An expression is anticipatable in a given block if it could
130 be generated in that block. This means that if we had to perform
131 an insertion in that block, of the value of that expression, we
132 could. Calculating the ANTIC sets requires phi translation of
133 expressions, because the flow goes backwards through phis. We must
134 iterate to a fixpoint of the ANTIC sets, because we have a kill
135 set. Even in SSA form, values are not live over the entire
136 function, only from their definition point onwards. So we have to
137 remove values from the ANTIC set once we go past the definition
138 point of the leaders that make them up.
139 compute_antic/compute_antic_aux performs this computation.
141 Third, we perform insertions to make partially redundant
142 expressions fully redundant.
144 An expression is partially redundant (excluding partial
147 1. It is AVAIL in some, but not all, of the predecessors of a
149 2. It is ANTIC in all the predecessors.
151 In order to make it fully redundant, we insert the expression into
152 the predecessors where it is not available, but is ANTIC.
154 For the partial anticipation case, we only perform insertion if it
155 is partially anticipated in some block, and fully available in all
158 insert/insert_aux/do_regular_insertion/do_partial_partial_insertion
159 performs these steps.
161 Fourth, we eliminate fully redundant expressions.
162 This is a simple statement walk that replaces redundant
163 calculations with the now available values. */
165 /* Representations of value numbers:
167 Value numbers are represented by a representative SSA_NAME. We
168 will create fake SSA_NAME's in situations where we need a
169 representative but do not have one (because it is a complex
170 expression). In order to facilitate storing the value numbers in
171 bitmaps, and keep the number of wasted SSA_NAME's down, we also
172 associate a value_id with each value number, and create full blown
173 ssa_name's only where we actually need them (IE in operands of
174 existing expressions).
176 Theoretically you could replace all the value_id's with
177 SSA_NAME_VERSION, but this would allocate a large number of
178 SSA_NAME's (which are each > 30 bytes) just to get a 4 byte number.
179 It would also require an additional indirection at each point we
182 /* Representation of expressions on value numbers:
184 Expressions consisting of value numbers are represented the same
185 way as our VN internally represents them, with an additional
186 "pre_expr" wrapping around them in order to facilitate storing all
187 of the expressions in the same sets. */
189 /* Representation of sets:
191 The dataflow sets do not need to be sorted in any particular order
192 for the majority of their lifetime, are simply represented as two
193 bitmaps, one that keeps track of values present in the set, and one
194 that keeps track of expressions present in the set.
196 When we need them in topological order, we produce it on demand by
197 transforming the bitmap into an array and sorting it into topo
200 /* Type of expression, used to know which member of the PRE_EXPR union
211 typedef union pre_expr_union_d
216 vn_reference_t reference
;
219 typedef struct pre_expr_d
: typed_noop_remove
<pre_expr_d
>
221 enum pre_expr_kind kind
;
225 /* hash_table support. */
226 typedef pre_expr_d
*value_type
;
227 typedef pre_expr_d
*compare_type
;
228 static inline hashval_t
hash (const pre_expr_d
*);
229 static inline int equal (const pre_expr_d
*, const pre_expr_d
*);
232 #define PRE_EXPR_NAME(e) (e)->u.name
233 #define PRE_EXPR_NARY(e) (e)->u.nary
234 #define PRE_EXPR_REFERENCE(e) (e)->u.reference
235 #define PRE_EXPR_CONSTANT(e) (e)->u.constant
237 /* Compare E1 and E1 for equality. */
240 pre_expr_d::equal (const pre_expr_d
*e1
, const pre_expr_d
*e2
)
242 if (e1
->kind
!= e2
->kind
)
248 return vn_constant_eq_with_type (PRE_EXPR_CONSTANT (e1
),
249 PRE_EXPR_CONSTANT (e2
));
251 return PRE_EXPR_NAME (e1
) == PRE_EXPR_NAME (e2
);
253 return vn_nary_op_eq (PRE_EXPR_NARY (e1
), PRE_EXPR_NARY (e2
));
255 return vn_reference_eq (PRE_EXPR_REFERENCE (e1
),
256 PRE_EXPR_REFERENCE (e2
));
265 pre_expr_d::hash (const pre_expr_d
*e
)
270 return vn_hash_constant_with_type (PRE_EXPR_CONSTANT (e
));
272 return SSA_NAME_VERSION (PRE_EXPR_NAME (e
));
274 return PRE_EXPR_NARY (e
)->hashcode
;
276 return PRE_EXPR_REFERENCE (e
)->hashcode
;
282 /* Next global expression id number. */
283 static unsigned int next_expression_id
;
285 /* Mapping from expression to id number we can use in bitmap sets. */
286 static vec
<pre_expr
> expressions
;
287 static hash_table
<pre_expr_d
> *expression_to_id
;
288 static vec
<unsigned> name_to_id
;
290 /* Allocate an expression id for EXPR. */
292 static inline unsigned int
293 alloc_expression_id (pre_expr expr
)
295 struct pre_expr_d
**slot
;
296 /* Make sure we won't overflow. */
297 gcc_assert (next_expression_id
+ 1 > next_expression_id
);
298 expr
->id
= next_expression_id
++;
299 expressions
.safe_push (expr
);
300 if (expr
->kind
== NAME
)
302 unsigned version
= SSA_NAME_VERSION (PRE_EXPR_NAME (expr
));
303 /* vec::safe_grow_cleared allocates no headroom. Avoid frequent
304 re-allocations by using vec::reserve upfront. */
305 unsigned old_len
= name_to_id
.length ();
306 name_to_id
.reserve (num_ssa_names
- old_len
);
307 name_to_id
.quick_grow_cleared (num_ssa_names
);
308 gcc_assert (name_to_id
[version
] == 0);
309 name_to_id
[version
] = expr
->id
;
313 slot
= expression_to_id
->find_slot (expr
, INSERT
);
317 return next_expression_id
- 1;
320 /* Return the expression id for tree EXPR. */
322 static inline unsigned int
323 get_expression_id (const pre_expr expr
)
328 static inline unsigned int
329 lookup_expression_id (const pre_expr expr
)
331 struct pre_expr_d
**slot
;
333 if (expr
->kind
== NAME
)
335 unsigned version
= SSA_NAME_VERSION (PRE_EXPR_NAME (expr
));
336 if (name_to_id
.length () <= version
)
338 return name_to_id
[version
];
342 slot
= expression_to_id
->find_slot (expr
, NO_INSERT
);
345 return ((pre_expr
)*slot
)->id
;
349 /* Return the existing expression id for EXPR, or create one if one
350 does not exist yet. */
352 static inline unsigned int
353 get_or_alloc_expression_id (pre_expr expr
)
355 unsigned int id
= lookup_expression_id (expr
);
357 return alloc_expression_id (expr
);
358 return expr
->id
= id
;
361 /* Return the expression that has expression id ID */
363 static inline pre_expr
364 expression_for_id (unsigned int id
)
366 return expressions
[id
];
369 /* Free the expression id field in all of our expressions,
370 and then destroy the expressions array. */
373 clear_expression_ids (void)
375 expressions
.release ();
378 static pool_allocator
<pre_expr_d
> pre_expr_pool ("pre_expr nodes", 30);
380 /* Given an SSA_NAME NAME, get or create a pre_expr to represent it. */
383 get_or_alloc_expr_for_name (tree name
)
385 struct pre_expr_d expr
;
387 unsigned int result_id
;
391 PRE_EXPR_NAME (&expr
) = name
;
392 result_id
= lookup_expression_id (&expr
);
394 return expression_for_id (result_id
);
396 result
= pre_expr_pool
.allocate ();
398 PRE_EXPR_NAME (result
) = name
;
399 alloc_expression_id (result
);
403 /* An unordered bitmap set. One bitmap tracks values, the other,
405 typedef struct bitmap_set
407 bitmap_head expressions
;
411 #define FOR_EACH_EXPR_ID_IN_SET(set, id, bi) \
412 EXECUTE_IF_SET_IN_BITMAP (&(set)->expressions, 0, (id), (bi))
414 #define FOR_EACH_VALUE_ID_IN_SET(set, id, bi) \
415 EXECUTE_IF_SET_IN_BITMAP (&(set)->values, 0, (id), (bi))
417 /* Mapping from value id to expressions with that value_id. */
418 static vec
<bitmap
> value_expressions
;
420 /* Sets that we need to keep track of. */
421 typedef struct bb_bitmap_sets
423 /* The EXP_GEN set, which represents expressions/values generated in
425 bitmap_set_t exp_gen
;
427 /* The PHI_GEN set, which represents PHI results generated in a
429 bitmap_set_t phi_gen
;
431 /* The TMP_GEN set, which represents results/temporaries generated
432 in a basic block. IE the LHS of an expression. */
433 bitmap_set_t tmp_gen
;
435 /* The AVAIL_OUT set, which represents which values are available in
436 a given basic block. */
437 bitmap_set_t avail_out
;
439 /* The ANTIC_IN set, which represents which values are anticipatable
440 in a given basic block. */
441 bitmap_set_t antic_in
;
443 /* The PA_IN set, which represents which values are
444 partially anticipatable in a given basic block. */
447 /* The NEW_SETS set, which is used during insertion to augment the
448 AVAIL_OUT set of blocks with the new insertions performed during
449 the current iteration. */
450 bitmap_set_t new_sets
;
452 /* A cache for value_dies_in_block_x. */
455 /* The live virtual operand on successor edges. */
458 /* True if we have visited this block during ANTIC calculation. */
459 unsigned int visited
: 1;
461 /* True when the block contains a call that might not return. */
462 unsigned int contains_may_not_return_call
: 1;
465 #define EXP_GEN(BB) ((bb_value_sets_t) ((BB)->aux))->exp_gen
466 #define PHI_GEN(BB) ((bb_value_sets_t) ((BB)->aux))->phi_gen
467 #define TMP_GEN(BB) ((bb_value_sets_t) ((BB)->aux))->tmp_gen
468 #define AVAIL_OUT(BB) ((bb_value_sets_t) ((BB)->aux))->avail_out
469 #define ANTIC_IN(BB) ((bb_value_sets_t) ((BB)->aux))->antic_in
470 #define PA_IN(BB) ((bb_value_sets_t) ((BB)->aux))->pa_in
471 #define NEW_SETS(BB) ((bb_value_sets_t) ((BB)->aux))->new_sets
472 #define EXPR_DIES(BB) ((bb_value_sets_t) ((BB)->aux))->expr_dies
473 #define BB_VISITED(BB) ((bb_value_sets_t) ((BB)->aux))->visited
474 #define BB_MAY_NOTRETURN(BB) ((bb_value_sets_t) ((BB)->aux))->contains_may_not_return_call
475 #define BB_LIVE_VOP_ON_EXIT(BB) ((bb_value_sets_t) ((BB)->aux))->vop_on_exit
478 /* Basic block list in postorder. */
479 static int *postorder
;
480 static int postorder_num
;
482 /* This structure is used to keep track of statistics on what
483 optimization PRE was able to perform. */
486 /* The number of RHS computations eliminated by PRE. */
489 /* The number of new expressions/temporaries generated by PRE. */
492 /* The number of inserts found due to partial anticipation */
495 /* The number of new PHI nodes added by PRE. */
499 static bool do_partial_partial
;
500 static pre_expr
bitmap_find_leader (bitmap_set_t
, unsigned int);
501 static void bitmap_value_insert_into_set (bitmap_set_t
, pre_expr
);
502 static void bitmap_value_replace_in_set (bitmap_set_t
, pre_expr
);
503 static void bitmap_set_copy (bitmap_set_t
, bitmap_set_t
);
504 static bool bitmap_set_contains_value (bitmap_set_t
, unsigned int);
505 static void bitmap_insert_into_set (bitmap_set_t
, pre_expr
);
506 static void bitmap_insert_into_set_1 (bitmap_set_t
, pre_expr
,
508 static bitmap_set_t
bitmap_set_new (void);
509 static tree
create_expression_by_pieces (basic_block
, pre_expr
, gimple_seq
*,
511 static tree
find_or_generate_expression (basic_block
, tree
, gimple_seq
*);
512 static unsigned int get_expr_value_id (pre_expr
);
514 /* We can add and remove elements and entries to and from sets
515 and hash tables, so we use alloc pools for them. */
517 static pool_allocator
<bitmap_set
> bitmap_set_pool ("Bitmap sets", 30);
518 static bitmap_obstack grand_bitmap_obstack
;
520 /* Set of blocks with statements that have had their EH properties changed. */
521 static bitmap need_eh_cleanup
;
523 /* Set of blocks with statements that have had their AB properties changed. */
524 static bitmap need_ab_cleanup
;
526 /* A three tuple {e, pred, v} used to cache phi translations in the
527 phi_translate_table. */
529 typedef struct expr_pred_trans_d
: typed_free_remove
<expr_pred_trans_d
>
531 /* The expression. */
534 /* The predecessor block along which we translated the expression. */
537 /* The value that resulted from the translation. */
540 /* The hashcode for the expression, pred pair. This is cached for
544 /* hash_table support. */
545 typedef expr_pred_trans_d
*value_type
;
546 typedef expr_pred_trans_d
*compare_type
;
547 static inline hashval_t
hash (const expr_pred_trans_d
*);
548 static inline int equal (const expr_pred_trans_d
*, const expr_pred_trans_d
*);
549 } *expr_pred_trans_t
;
550 typedef const struct expr_pred_trans_d
*const_expr_pred_trans_t
;
553 expr_pred_trans_d::hash (const expr_pred_trans_d
*e
)
559 expr_pred_trans_d::equal (const expr_pred_trans_d
*ve1
,
560 const expr_pred_trans_d
*ve2
)
562 basic_block b1
= ve1
->pred
;
563 basic_block b2
= ve2
->pred
;
565 /* If they are not translations for the same basic block, they can't
569 return pre_expr_d::equal (ve1
->e
, ve2
->e
);
572 /* The phi_translate_table caches phi translations for a given
573 expression and predecessor. */
574 static hash_table
<expr_pred_trans_d
> *phi_translate_table
;
576 /* Add the tuple mapping from {expression E, basic block PRED} to
577 the phi translation table and return whether it pre-existed. */
580 phi_trans_add (expr_pred_trans_t
*entry
, pre_expr e
, basic_block pred
)
582 expr_pred_trans_t
*slot
;
583 expr_pred_trans_d tem
;
584 hashval_t hash
= iterative_hash_hashval_t (pre_expr_d::hash (e
),
589 slot
= phi_translate_table
->find_slot_with_hash (&tem
, hash
, INSERT
);
596 *entry
= *slot
= XNEW (struct expr_pred_trans_d
);
598 (*entry
)->pred
= pred
;
599 (*entry
)->hashcode
= hash
;
604 /* Add expression E to the expression set of value id V. */
607 add_to_value (unsigned int v
, pre_expr e
)
611 gcc_checking_assert (get_expr_value_id (e
) == v
);
613 if (v
>= value_expressions
.length ())
615 value_expressions
.safe_grow_cleared (v
+ 1);
618 set
= value_expressions
[v
];
621 set
= BITMAP_ALLOC (&grand_bitmap_obstack
);
622 value_expressions
[v
] = set
;
625 bitmap_set_bit (set
, get_or_alloc_expression_id (e
));
628 /* Create a new bitmap set and return it. */
631 bitmap_set_new (void)
633 bitmap_set_t ret
= bitmap_set_pool
.allocate ();
634 bitmap_initialize (&ret
->expressions
, &grand_bitmap_obstack
);
635 bitmap_initialize (&ret
->values
, &grand_bitmap_obstack
);
639 /* Return the value id for a PRE expression EXPR. */
642 get_expr_value_id (pre_expr expr
)
648 id
= get_constant_value_id (PRE_EXPR_CONSTANT (expr
));
651 id
= VN_INFO (PRE_EXPR_NAME (expr
))->value_id
;
654 id
= PRE_EXPR_NARY (expr
)->value_id
;
657 id
= PRE_EXPR_REFERENCE (expr
)->value_id
;
662 /* ??? We cannot assert that expr has a value-id (it can be 0), because
663 we assign value-ids only to expressions that have a result
664 in set_hashtable_value_ids. */
668 /* Return a SCCVN valnum (SSA name or constant) for the PRE value-id VAL. */
671 sccvn_valnum_from_value_id (unsigned int val
)
675 bitmap exprset
= value_expressions
[val
];
676 EXECUTE_IF_SET_IN_BITMAP (exprset
, 0, i
, bi
)
678 pre_expr vexpr
= expression_for_id (i
);
679 if (vexpr
->kind
== NAME
)
680 return VN_INFO (PRE_EXPR_NAME (vexpr
))->valnum
;
681 else if (vexpr
->kind
== CONSTANT
)
682 return PRE_EXPR_CONSTANT (vexpr
);
687 /* Remove an expression EXPR from a bitmapped set. */
690 bitmap_remove_from_set (bitmap_set_t set
, pre_expr expr
)
692 unsigned int val
= get_expr_value_id (expr
);
693 if (!value_id_constant_p (val
))
695 bitmap_clear_bit (&set
->values
, val
);
696 bitmap_clear_bit (&set
->expressions
, get_expression_id (expr
));
701 bitmap_insert_into_set_1 (bitmap_set_t set
, pre_expr expr
,
702 unsigned int val
, bool allow_constants
)
704 if (allow_constants
|| !value_id_constant_p (val
))
706 /* We specifically expect this and only this function to be able to
707 insert constants into a set. */
708 bitmap_set_bit (&set
->values
, val
);
709 bitmap_set_bit (&set
->expressions
, get_or_alloc_expression_id (expr
));
713 /* Insert an expression EXPR into a bitmapped set. */
716 bitmap_insert_into_set (bitmap_set_t set
, pre_expr expr
)
718 bitmap_insert_into_set_1 (set
, expr
, get_expr_value_id (expr
), false);
721 /* Copy a bitmapped set ORIG, into bitmapped set DEST. */
724 bitmap_set_copy (bitmap_set_t dest
, bitmap_set_t orig
)
726 bitmap_copy (&dest
->expressions
, &orig
->expressions
);
727 bitmap_copy (&dest
->values
, &orig
->values
);
731 /* Free memory used up by SET. */
733 bitmap_set_free (bitmap_set_t set
)
735 bitmap_clear (&set
->expressions
);
736 bitmap_clear (&set
->values
);
740 /* Generate an topological-ordered array of bitmap set SET. */
743 sorted_array_from_bitmap_set (bitmap_set_t set
)
746 bitmap_iterator bi
, bj
;
747 vec
<pre_expr
> result
;
749 /* Pre-allocate enough space for the array. */
750 result
.create (bitmap_count_bits (&set
->expressions
));
752 FOR_EACH_VALUE_ID_IN_SET (set
, i
, bi
)
754 /* The number of expressions having a given value is usually
755 relatively small. Thus, rather than making a vector of all
756 the expressions and sorting it by value-id, we walk the values
757 and check in the reverse mapping that tells us what expressions
758 have a given value, to filter those in our set. As a result,
759 the expressions are inserted in value-id order, which means
762 If this is somehow a significant lose for some cases, we can
763 choose which set to walk based on the set size. */
764 bitmap exprset
= value_expressions
[i
];
765 EXECUTE_IF_SET_IN_BITMAP (exprset
, 0, j
, bj
)
767 if (bitmap_bit_p (&set
->expressions
, j
))
768 result
.quick_push (expression_for_id (j
));
775 /* Perform bitmapped set operation DEST &= ORIG. */
778 bitmap_set_and (bitmap_set_t dest
, bitmap_set_t orig
)
786 bitmap_initialize (&temp
, &grand_bitmap_obstack
);
788 bitmap_and_into (&dest
->values
, &orig
->values
);
789 bitmap_copy (&temp
, &dest
->expressions
);
790 EXECUTE_IF_SET_IN_BITMAP (&temp
, 0, i
, bi
)
792 pre_expr expr
= expression_for_id (i
);
793 unsigned int value_id
= get_expr_value_id (expr
);
794 if (!bitmap_bit_p (&dest
->values
, value_id
))
795 bitmap_clear_bit (&dest
->expressions
, i
);
797 bitmap_clear (&temp
);
801 /* Subtract all values and expressions contained in ORIG from DEST. */
804 bitmap_set_subtract (bitmap_set_t dest
, bitmap_set_t orig
)
806 bitmap_set_t result
= bitmap_set_new ();
810 bitmap_and_compl (&result
->expressions
, &dest
->expressions
,
813 FOR_EACH_EXPR_ID_IN_SET (result
, i
, bi
)
815 pre_expr expr
= expression_for_id (i
);
816 unsigned int value_id
= get_expr_value_id (expr
);
817 bitmap_set_bit (&result
->values
, value_id
);
823 /* Subtract all the values in bitmap set B from bitmap set A. */
826 bitmap_set_subtract_values (bitmap_set_t a
, bitmap_set_t b
)
832 bitmap_initialize (&temp
, &grand_bitmap_obstack
);
834 bitmap_copy (&temp
, &a
->expressions
);
835 EXECUTE_IF_SET_IN_BITMAP (&temp
, 0, i
, bi
)
837 pre_expr expr
= expression_for_id (i
);
838 if (bitmap_set_contains_value (b
, get_expr_value_id (expr
)))
839 bitmap_remove_from_set (a
, expr
);
841 bitmap_clear (&temp
);
845 /* Return true if bitmapped set SET contains the value VALUE_ID. */
848 bitmap_set_contains_value (bitmap_set_t set
, unsigned int value_id
)
850 if (value_id_constant_p (value_id
))
853 if (!set
|| bitmap_empty_p (&set
->expressions
))
856 return bitmap_bit_p (&set
->values
, value_id
);
860 bitmap_set_contains_expr (bitmap_set_t set
, const pre_expr expr
)
862 return bitmap_bit_p (&set
->expressions
, get_expression_id (expr
));
865 /* Replace an instance of value LOOKFOR with expression EXPR in SET. */
868 bitmap_set_replace_value (bitmap_set_t set
, unsigned int lookfor
,
875 if (value_id_constant_p (lookfor
))
878 if (!bitmap_set_contains_value (set
, lookfor
))
881 /* The number of expressions having a given value is usually
882 significantly less than the total number of expressions in SET.
883 Thus, rather than check, for each expression in SET, whether it
884 has the value LOOKFOR, we walk the reverse mapping that tells us
885 what expressions have a given value, and see if any of those
886 expressions are in our set. For large testcases, this is about
887 5-10x faster than walking the bitmap. If this is somehow a
888 significant lose for some cases, we can choose which set to walk
889 based on the set size. */
890 exprset
= value_expressions
[lookfor
];
891 EXECUTE_IF_SET_IN_BITMAP (exprset
, 0, i
, bi
)
893 if (bitmap_clear_bit (&set
->expressions
, i
))
895 bitmap_set_bit (&set
->expressions
, get_expression_id (expr
));
903 /* Return true if two bitmap sets are equal. */
906 bitmap_set_equal (bitmap_set_t a
, bitmap_set_t b
)
908 return bitmap_equal_p (&a
->values
, &b
->values
);
911 /* Replace an instance of EXPR's VALUE with EXPR in SET if it exists,
912 and add it otherwise. */
915 bitmap_value_replace_in_set (bitmap_set_t set
, pre_expr expr
)
917 unsigned int val
= get_expr_value_id (expr
);
919 if (bitmap_set_contains_value (set
, val
))
920 bitmap_set_replace_value (set
, val
, expr
);
922 bitmap_insert_into_set (set
, expr
);
925 /* Insert EXPR into SET if EXPR's value is not already present in
929 bitmap_value_insert_into_set (bitmap_set_t set
, pre_expr expr
)
931 unsigned int val
= get_expr_value_id (expr
);
933 gcc_checking_assert (expr
->id
== get_or_alloc_expression_id (expr
));
935 /* Constant values are always considered to be part of the set. */
936 if (value_id_constant_p (val
))
939 /* If the value membership changed, add the expression. */
940 if (bitmap_set_bit (&set
->values
, val
))
941 bitmap_set_bit (&set
->expressions
, expr
->id
);
944 /* Print out EXPR to outfile. */
947 print_pre_expr (FILE *outfile
, const pre_expr expr
)
952 print_generic_expr (outfile
, PRE_EXPR_CONSTANT (expr
), 0);
955 print_generic_expr (outfile
, PRE_EXPR_NAME (expr
), 0);
960 vn_nary_op_t nary
= PRE_EXPR_NARY (expr
);
961 fprintf (outfile
, "{%s,", get_tree_code_name (nary
->opcode
));
962 for (i
= 0; i
< nary
->length
; i
++)
964 print_generic_expr (outfile
, nary
->op
[i
], 0);
965 if (i
!= (unsigned) nary
->length
- 1)
966 fprintf (outfile
, ",");
968 fprintf (outfile
, "}");
974 vn_reference_op_t vro
;
976 vn_reference_t ref
= PRE_EXPR_REFERENCE (expr
);
977 fprintf (outfile
, "{");
979 ref
->operands
.iterate (i
, &vro
);
982 bool closebrace
= false;
983 if (vro
->opcode
!= SSA_NAME
984 && TREE_CODE_CLASS (vro
->opcode
) != tcc_declaration
)
986 fprintf (outfile
, "%s", get_tree_code_name (vro
->opcode
));
989 fprintf (outfile
, "<");
995 print_generic_expr (outfile
, vro
->op0
, 0);
998 fprintf (outfile
, ",");
999 print_generic_expr (outfile
, vro
->op1
, 0);
1003 fprintf (outfile
, ",");
1004 print_generic_expr (outfile
, vro
->op2
, 0);
1008 fprintf (outfile
, ">");
1009 if (i
!= ref
->operands
.length () - 1)
1010 fprintf (outfile
, ",");
1012 fprintf (outfile
, "}");
1015 fprintf (outfile
, "@");
1016 print_generic_expr (outfile
, ref
->vuse
, 0);
1022 void debug_pre_expr (pre_expr
);
1024 /* Like print_pre_expr but always prints to stderr. */
1026 debug_pre_expr (pre_expr e
)
1028 print_pre_expr (stderr
, e
);
1029 fprintf (stderr
, "\n");
1032 /* Print out SET to OUTFILE. */
1035 print_bitmap_set (FILE *outfile
, bitmap_set_t set
,
1036 const char *setname
, int blockindex
)
1038 fprintf (outfile
, "%s[%d] := { ", setname
, blockindex
);
1045 FOR_EACH_EXPR_ID_IN_SET (set
, i
, bi
)
1047 const pre_expr expr
= expression_for_id (i
);
1050 fprintf (outfile
, ", ");
1052 print_pre_expr (outfile
, expr
);
1054 fprintf (outfile
, " (%04d)", get_expr_value_id (expr
));
1057 fprintf (outfile
, " }\n");
1060 void debug_bitmap_set (bitmap_set_t
);
1063 debug_bitmap_set (bitmap_set_t set
)
1065 print_bitmap_set (stderr
, set
, "debug", 0);
1068 void debug_bitmap_sets_for (basic_block
);
1071 debug_bitmap_sets_for (basic_block bb
)
1073 print_bitmap_set (stderr
, AVAIL_OUT (bb
), "avail_out", bb
->index
);
1074 print_bitmap_set (stderr
, EXP_GEN (bb
), "exp_gen", bb
->index
);
1075 print_bitmap_set (stderr
, PHI_GEN (bb
), "phi_gen", bb
->index
);
1076 print_bitmap_set (stderr
, TMP_GEN (bb
), "tmp_gen", bb
->index
);
1077 print_bitmap_set (stderr
, ANTIC_IN (bb
), "antic_in", bb
->index
);
1078 if (do_partial_partial
)
1079 print_bitmap_set (stderr
, PA_IN (bb
), "pa_in", bb
->index
);
1080 print_bitmap_set (stderr
, NEW_SETS (bb
), "new_sets", bb
->index
);
1083 /* Print out the expressions that have VAL to OUTFILE. */
1086 print_value_expressions (FILE *outfile
, unsigned int val
)
1088 bitmap set
= value_expressions
[val
];
1093 sprintf (s
, "%04d", val
);
1094 x
.expressions
= *set
;
1095 print_bitmap_set (outfile
, &x
, s
, 0);
1101 debug_value_expressions (unsigned int val
)
1103 print_value_expressions (stderr
, val
);
1106 /* Given a CONSTANT, allocate a new CONSTANT type PRE_EXPR to
1110 get_or_alloc_expr_for_constant (tree constant
)
1112 unsigned int result_id
;
1113 unsigned int value_id
;
1114 struct pre_expr_d expr
;
1117 expr
.kind
= CONSTANT
;
1118 PRE_EXPR_CONSTANT (&expr
) = constant
;
1119 result_id
= lookup_expression_id (&expr
);
1121 return expression_for_id (result_id
);
1123 newexpr
= pre_expr_pool
.allocate ();
1124 newexpr
->kind
= CONSTANT
;
1125 PRE_EXPR_CONSTANT (newexpr
) = constant
;
1126 alloc_expression_id (newexpr
);
1127 value_id
= get_or_alloc_constant_value_id (constant
);
1128 add_to_value (value_id
, newexpr
);
1132 /* Given a value id V, find the actual tree representing the constant
1133 value if there is one, and return it. Return NULL if we can't find
1137 get_constant_for_value_id (unsigned int v
)
1139 if (value_id_constant_p (v
))
1143 bitmap exprset
= value_expressions
[v
];
1145 EXECUTE_IF_SET_IN_BITMAP (exprset
, 0, i
, bi
)
1147 pre_expr expr
= expression_for_id (i
);
1148 if (expr
->kind
== CONSTANT
)
1149 return PRE_EXPR_CONSTANT (expr
);
1155 /* Get or allocate a pre_expr for a piece of GIMPLE, and return it.
1156 Currently only supports constants and SSA_NAMES. */
1158 get_or_alloc_expr_for (tree t
)
1160 if (TREE_CODE (t
) == SSA_NAME
)
1161 return get_or_alloc_expr_for_name (t
);
1162 else if (is_gimple_min_invariant (t
))
1163 return get_or_alloc_expr_for_constant (t
);
1166 /* More complex expressions can result from SCCVN expression
1167 simplification that inserts values for them. As they all
1168 do not have VOPs the get handled by the nary ops struct. */
1169 vn_nary_op_t result
;
1170 unsigned int result_id
;
1171 vn_nary_op_lookup (t
, &result
);
1174 pre_expr e
= pre_expr_pool
.allocate ();
1176 PRE_EXPR_NARY (e
) = result
;
1177 result_id
= lookup_expression_id (e
);
1180 pre_expr_pool
.remove (e
);
1181 e
= expression_for_id (result_id
);
1184 alloc_expression_id (e
);
1191 /* Return the folded version of T if T, when folded, is a gimple
1192 min_invariant. Otherwise, return T. */
1195 fully_constant_expression (pre_expr e
)
1203 vn_nary_op_t nary
= PRE_EXPR_NARY (e
);
1204 switch (TREE_CODE_CLASS (nary
->opcode
))
1207 case tcc_comparison
:
1209 /* We have to go from trees to pre exprs to value ids to
1211 tree naryop0
= nary
->op
[0];
1212 tree naryop1
= nary
->op
[1];
1214 if (!is_gimple_min_invariant (naryop0
))
1216 pre_expr rep0
= get_or_alloc_expr_for (naryop0
);
1217 unsigned int vrep0
= get_expr_value_id (rep0
);
1218 tree const0
= get_constant_for_value_id (vrep0
);
1220 naryop0
= fold_convert (TREE_TYPE (naryop0
), const0
);
1222 if (!is_gimple_min_invariant (naryop1
))
1224 pre_expr rep1
= get_or_alloc_expr_for (naryop1
);
1225 unsigned int vrep1
= get_expr_value_id (rep1
);
1226 tree const1
= get_constant_for_value_id (vrep1
);
1228 naryop1
= fold_convert (TREE_TYPE (naryop1
), const1
);
1230 result
= fold_binary (nary
->opcode
, nary
->type
,
1232 if (result
&& is_gimple_min_invariant (result
))
1233 return get_or_alloc_expr_for_constant (result
);
1234 /* We might have simplified the expression to a
1235 SSA_NAME for example from x_1 * 1. But we cannot
1236 insert a PHI for x_1 unconditionally as x_1 might
1237 not be available readily. */
1241 if (nary
->opcode
!= REALPART_EXPR
1242 && nary
->opcode
!= IMAGPART_EXPR
1243 && nary
->opcode
!= VIEW_CONVERT_EXPR
)
1248 /* We have to go from trees to pre exprs to value ids to
1250 tree naryop0
= nary
->op
[0];
1251 tree const0
, result
;
1252 if (is_gimple_min_invariant (naryop0
))
1256 pre_expr rep0
= get_or_alloc_expr_for (naryop0
);
1257 unsigned int vrep0
= get_expr_value_id (rep0
);
1258 const0
= get_constant_for_value_id (vrep0
);
1263 tree type1
= TREE_TYPE (nary
->op
[0]);
1264 const0
= fold_convert (type1
, const0
);
1265 result
= fold_unary (nary
->opcode
, nary
->type
, const0
);
1267 if (result
&& is_gimple_min_invariant (result
))
1268 return get_or_alloc_expr_for_constant (result
);
1277 vn_reference_t ref
= PRE_EXPR_REFERENCE (e
);
1279 if ((folded
= fully_constant_vn_reference_p (ref
)))
1280 return get_or_alloc_expr_for_constant (folded
);
1289 /* Translate the VUSE backwards through phi nodes in PHIBLOCK, so that
1290 it has the value it would have in BLOCK. Set *SAME_VALID to true
1291 in case the new vuse doesn't change the value id of the OPERANDS. */
1294 translate_vuse_through_block (vec
<vn_reference_op_s
> operands
,
1295 alias_set_type set
, tree type
, tree vuse
,
1296 basic_block phiblock
,
1297 basic_block block
, bool *same_valid
)
1299 gimple phi
= SSA_NAME_DEF_STMT (vuse
);
1306 if (gimple_bb (phi
) != phiblock
)
1309 use_oracle
= ao_ref_init_from_vn_reference (&ref
, set
, type
, operands
);
1311 /* Use the alias-oracle to find either the PHI node in this block,
1312 the first VUSE used in this block that is equivalent to vuse or
1313 the first VUSE which definition in this block kills the value. */
1314 if (gimple_code (phi
) == GIMPLE_PHI
)
1315 e
= find_edge (block
, phiblock
);
1316 else if (use_oracle
)
1317 while (!stmt_may_clobber_ref_p_1 (phi
, &ref
))
1319 vuse
= gimple_vuse (phi
);
1320 phi
= SSA_NAME_DEF_STMT (vuse
);
1321 if (gimple_bb (phi
) != phiblock
)
1323 if (gimple_code (phi
) == GIMPLE_PHI
)
1325 e
= find_edge (block
, phiblock
);
1336 bitmap visited
= NULL
;
1338 /* Try to find a vuse that dominates this phi node by skipping
1339 non-clobbering statements. */
1340 vuse
= get_continuation_for_phi (phi
, &ref
, &cnt
, &visited
, false,
1343 BITMAP_FREE (visited
);
1349 /* If we didn't find any, the value ID can't stay the same,
1350 but return the translated vuse. */
1351 *same_valid
= false;
1352 vuse
= PHI_ARG_DEF (phi
, e
->dest_idx
);
1354 /* ??? We would like to return vuse here as this is the canonical
1355 upmost vdef that this reference is associated with. But during
1356 insertion of the references into the hash tables we only ever
1357 directly insert with their direct gimple_vuse, hence returning
1358 something else would make us not find the other expression. */
1359 return PHI_ARG_DEF (phi
, e
->dest_idx
);
1365 /* Like bitmap_find_leader, but checks for the value existing in SET1 *or*
1366 SET2. This is used to avoid making a set consisting of the union
1367 of PA_IN and ANTIC_IN during insert. */
1369 static inline pre_expr
1370 find_leader_in_sets (unsigned int val
, bitmap_set_t set1
, bitmap_set_t set2
)
1374 result
= bitmap_find_leader (set1
, val
);
1375 if (!result
&& set2
)
1376 result
= bitmap_find_leader (set2
, val
);
1380 /* Get the tree type for our PRE expression e. */
1383 get_expr_type (const pre_expr e
)
1388 return TREE_TYPE (PRE_EXPR_NAME (e
));
1390 return TREE_TYPE (PRE_EXPR_CONSTANT (e
));
1392 return PRE_EXPR_REFERENCE (e
)->type
;
1394 return PRE_EXPR_NARY (e
)->type
;
1399 /* Get a representative SSA_NAME for a given expression.
1400 Since all of our sub-expressions are treated as values, we require
1401 them to be SSA_NAME's for simplicity.
1402 Prior versions of GVNPRE used to use "value handles" here, so that
1403 an expression would be VH.11 + VH.10 instead of d_3 + e_6. In
1404 either case, the operands are really values (IE we do not expect
1405 them to be usable without finding leaders). */
1408 get_representative_for (const pre_expr e
)
1411 unsigned int value_id
= get_expr_value_id (e
);
1416 return PRE_EXPR_NAME (e
);
1418 return PRE_EXPR_CONSTANT (e
);
1422 /* Go through all of the expressions representing this value
1423 and pick out an SSA_NAME. */
1426 bitmap exprs
= value_expressions
[value_id
];
1427 EXECUTE_IF_SET_IN_BITMAP (exprs
, 0, i
, bi
)
1429 pre_expr rep
= expression_for_id (i
);
1430 if (rep
->kind
== NAME
)
1431 return PRE_EXPR_NAME (rep
);
1432 else if (rep
->kind
== CONSTANT
)
1433 return PRE_EXPR_CONSTANT (rep
);
1439 /* If we reached here we couldn't find an SSA_NAME. This can
1440 happen when we've discovered a value that has never appeared in
1441 the program as set to an SSA_NAME, as the result of phi translation.
1443 ??? We should be able to re-use this when we insert the statement
1445 name
= make_temp_ssa_name (get_expr_type (e
), gimple_build_nop (), "pretmp");
1446 VN_INFO_GET (name
)->value_id
= value_id
;
1447 VN_INFO (name
)->valnum
= name
;
1448 /* ??? For now mark this SSA name for release by SCCVN. */
1449 VN_INFO (name
)->needs_insertion
= true;
1450 add_to_value (value_id
, get_or_alloc_expr_for_name (name
));
1451 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1453 fprintf (dump_file
, "Created SSA_NAME representative ");
1454 print_generic_expr (dump_file
, name
, 0);
1455 fprintf (dump_file
, " for expression:");
1456 print_pre_expr (dump_file
, e
);
1457 fprintf (dump_file
, " (%04d)\n", value_id
);
1466 phi_translate (pre_expr expr
, bitmap_set_t set1
, bitmap_set_t set2
,
1467 basic_block pred
, basic_block phiblock
);
1469 /* Translate EXPR using phis in PHIBLOCK, so that it has the values of
1470 the phis in PRED. Return NULL if we can't find a leader for each part
1471 of the translated expression. */
1474 phi_translate_1 (pre_expr expr
, bitmap_set_t set1
, bitmap_set_t set2
,
1475 basic_block pred
, basic_block phiblock
)
1482 bool changed
= false;
1483 vn_nary_op_t nary
= PRE_EXPR_NARY (expr
);
1484 vn_nary_op_t newnary
= XALLOCAVAR (struct vn_nary_op_s
,
1485 sizeof_vn_nary_op (nary
->length
));
1486 memcpy (newnary
, nary
, sizeof_vn_nary_op (nary
->length
));
1488 for (i
= 0; i
< newnary
->length
; i
++)
1490 if (TREE_CODE (newnary
->op
[i
]) != SSA_NAME
)
1494 pre_expr leader
, result
;
1495 unsigned int op_val_id
= VN_INFO (newnary
->op
[i
])->value_id
;
1496 leader
= find_leader_in_sets (op_val_id
, set1
, set2
);
1497 result
= phi_translate (leader
, set1
, set2
, pred
, phiblock
);
1498 if (result
&& result
!= leader
)
1500 tree name
= get_representative_for (result
);
1503 newnary
->op
[i
] = name
;
1508 changed
|= newnary
->op
[i
] != nary
->op
[i
];
1514 unsigned int new_val_id
;
1516 tree result
= vn_nary_op_lookup_pieces (newnary
->length
,
1521 if (result
&& is_gimple_min_invariant (result
))
1522 return get_or_alloc_expr_for_constant (result
);
1524 expr
= pre_expr_pool
.allocate ();
1529 PRE_EXPR_NARY (expr
) = nary
;
1530 constant
= fully_constant_expression (expr
);
1531 if (constant
!= expr
)
1534 new_val_id
= nary
->value_id
;
1535 get_or_alloc_expression_id (expr
);
1539 new_val_id
= get_next_value_id ();
1540 value_expressions
.safe_grow_cleared (get_max_value_id () + 1);
1541 nary
= vn_nary_op_insert_pieces (newnary
->length
,
1545 result
, new_val_id
);
1546 PRE_EXPR_NARY (expr
) = nary
;
1547 constant
= fully_constant_expression (expr
);
1548 if (constant
!= expr
)
1550 get_or_alloc_expression_id (expr
);
1552 add_to_value (new_val_id
, expr
);
1560 vn_reference_t ref
= PRE_EXPR_REFERENCE (expr
);
1561 vec
<vn_reference_op_s
> operands
= ref
->operands
;
1562 tree vuse
= ref
->vuse
;
1563 tree newvuse
= vuse
;
1564 vec
<vn_reference_op_s
> newoperands
= vNULL
;
1565 bool changed
= false, same_valid
= true;
1567 vn_reference_op_t operand
;
1568 vn_reference_t newref
;
1570 for (i
= 0; operands
.iterate (i
, &operand
); i
++)
1575 tree type
= operand
->type
;
1576 vn_reference_op_s newop
= *operand
;
1577 op
[0] = operand
->op0
;
1578 op
[1] = operand
->op1
;
1579 op
[2] = operand
->op2
;
1580 for (n
= 0; n
< 3; ++n
)
1582 unsigned int op_val_id
;
1585 if (TREE_CODE (op
[n
]) != SSA_NAME
)
1587 /* We can't possibly insert these. */
1589 && !is_gimple_min_invariant (op
[n
]))
1593 op_val_id
= VN_INFO (op
[n
])->value_id
;
1594 leader
= find_leader_in_sets (op_val_id
, set1
, set2
);
1597 opresult
= phi_translate (leader
, set1
, set2
, pred
, phiblock
);
1600 if (opresult
!= leader
)
1602 tree name
= get_representative_for (opresult
);
1605 changed
|= name
!= op
[n
];
1611 newoperands
.release ();
1616 if (!newoperands
.exists ())
1617 newoperands
= operands
.copy ();
1618 /* We may have changed from an SSA_NAME to a constant */
1619 if (newop
.opcode
== SSA_NAME
&& TREE_CODE (op
[0]) != SSA_NAME
)
1620 newop
.opcode
= TREE_CODE (op
[0]);
1625 newoperands
[i
] = newop
;
1627 gcc_checking_assert (i
== operands
.length ());
1631 newvuse
= translate_vuse_through_block (newoperands
.exists ()
1632 ? newoperands
: operands
,
1633 ref
->set
, ref
->type
,
1634 vuse
, phiblock
, pred
,
1636 if (newvuse
== NULL_TREE
)
1638 newoperands
.release ();
1643 if (changed
|| newvuse
!= vuse
)
1645 unsigned int new_val_id
;
1648 tree result
= vn_reference_lookup_pieces (newvuse
, ref
->set
,
1650 newoperands
.exists ()
1651 ? newoperands
: operands
,
1654 newoperands
.release ();
1656 /* We can always insert constants, so if we have a partial
1657 redundant constant load of another type try to translate it
1658 to a constant of appropriate type. */
1659 if (result
&& is_gimple_min_invariant (result
))
1662 if (!useless_type_conversion_p (ref
->type
, TREE_TYPE (result
)))
1664 tem
= fold_unary (VIEW_CONVERT_EXPR
, ref
->type
, result
);
1665 if (tem
&& !is_gimple_min_invariant (tem
))
1669 return get_or_alloc_expr_for_constant (tem
);
1672 /* If we'd have to convert things we would need to validate
1673 if we can insert the translated expression. So fail
1674 here for now - we cannot insert an alias with a different
1675 type in the VN tables either, as that would assert. */
1677 && !useless_type_conversion_p (ref
->type
, TREE_TYPE (result
)))
1679 else if (!result
&& newref
1680 && !useless_type_conversion_p (ref
->type
, newref
->type
))
1682 newoperands
.release ();
1686 expr
= pre_expr_pool
.allocate ();
1687 expr
->kind
= REFERENCE
;
1692 PRE_EXPR_REFERENCE (expr
) = newref
;
1693 constant
= fully_constant_expression (expr
);
1694 if (constant
!= expr
)
1697 new_val_id
= newref
->value_id
;
1698 get_or_alloc_expression_id (expr
);
1702 if (changed
|| !same_valid
)
1704 new_val_id
= get_next_value_id ();
1705 value_expressions
.safe_grow_cleared
1706 (get_max_value_id () + 1);
1709 new_val_id
= ref
->value_id
;
1710 if (!newoperands
.exists ())
1711 newoperands
= operands
.copy ();
1712 newref
= vn_reference_insert_pieces (newvuse
, ref
->set
,
1715 result
, new_val_id
);
1716 newoperands
= vNULL
;
1717 PRE_EXPR_REFERENCE (expr
) = newref
;
1718 constant
= fully_constant_expression (expr
);
1719 if (constant
!= expr
)
1721 get_or_alloc_expression_id (expr
);
1723 add_to_value (new_val_id
, expr
);
1725 newoperands
.release ();
1732 tree name
= PRE_EXPR_NAME (expr
);
1733 gimple def_stmt
= SSA_NAME_DEF_STMT (name
);
1734 /* If the SSA name is defined by a PHI node in this block,
1736 if (gimple_code (def_stmt
) == GIMPLE_PHI
1737 && gimple_bb (def_stmt
) == phiblock
)
1739 edge e
= find_edge (pred
, gimple_bb (def_stmt
));
1740 tree def
= PHI_ARG_DEF (def_stmt
, e
->dest_idx
);
1742 /* Handle constant. */
1743 if (is_gimple_min_invariant (def
))
1744 return get_or_alloc_expr_for_constant (def
);
1746 return get_or_alloc_expr_for_name (def
);
1748 /* Otherwise return it unchanged - it will get removed if its
1749 value is not available in PREDs AVAIL_OUT set of expressions
1750 by the subtraction of TMP_GEN. */
1759 /* Wrapper around phi_translate_1 providing caching functionality. */
1762 phi_translate (pre_expr expr
, bitmap_set_t set1
, bitmap_set_t set2
,
1763 basic_block pred
, basic_block phiblock
)
1765 expr_pred_trans_t slot
= NULL
;
1771 /* Constants contain no values that need translation. */
1772 if (expr
->kind
== CONSTANT
)
1775 if (value_id_constant_p (get_expr_value_id (expr
)))
1778 /* Don't add translations of NAMEs as those are cheap to translate. */
1779 if (expr
->kind
!= NAME
)
1781 if (phi_trans_add (&slot
, expr
, pred
))
1783 /* Store NULL for the value we want to return in the case of
1789 phitrans
= phi_translate_1 (expr
, set1
, set2
, pred
, phiblock
);
1796 /* Remove failed translations again, they cause insert
1797 iteration to not pick up new opportunities reliably. */
1798 phi_translate_table
->remove_elt_with_hash (slot
, slot
->hashcode
);
1805 /* For each expression in SET, translate the values through phi nodes
1806 in PHIBLOCK using edge PHIBLOCK->PRED, and store the resulting
1807 expressions in DEST. */
1810 phi_translate_set (bitmap_set_t dest
, bitmap_set_t set
, basic_block pred
,
1811 basic_block phiblock
)
1813 vec
<pre_expr
> exprs
;
1817 if (gimple_seq_empty_p (phi_nodes (phiblock
)))
1819 bitmap_set_copy (dest
, set
);
1823 exprs
= sorted_array_from_bitmap_set (set
);
1824 FOR_EACH_VEC_ELT (exprs
, i
, expr
)
1826 pre_expr translated
;
1827 translated
= phi_translate (expr
, set
, NULL
, pred
, phiblock
);
1831 /* We might end up with multiple expressions from SET being
1832 translated to the same value. In this case we do not want
1833 to retain the NARY or REFERENCE expression but prefer a NAME
1834 which would be the leader. */
1835 if (translated
->kind
== NAME
)
1836 bitmap_value_replace_in_set (dest
, translated
);
1838 bitmap_value_insert_into_set (dest
, translated
);
1843 /* Find the leader for a value (i.e., the name representing that
1844 value) in a given set, and return it. Return NULL if no leader
1848 bitmap_find_leader (bitmap_set_t set
, unsigned int val
)
1850 if (value_id_constant_p (val
))
1854 bitmap exprset
= value_expressions
[val
];
1856 EXECUTE_IF_SET_IN_BITMAP (exprset
, 0, i
, bi
)
1858 pre_expr expr
= expression_for_id (i
);
1859 if (expr
->kind
== CONSTANT
)
1863 if (bitmap_set_contains_value (set
, val
))
1865 /* Rather than walk the entire bitmap of expressions, and see
1866 whether any of them has the value we are looking for, we look
1867 at the reverse mapping, which tells us the set of expressions
1868 that have a given value (IE value->expressions with that
1869 value) and see if any of those expressions are in our set.
1870 The number of expressions per value is usually significantly
1871 less than the number of expressions in the set. In fact, for
1872 large testcases, doing it this way is roughly 5-10x faster
1873 than walking the bitmap.
1874 If this is somehow a significant lose for some cases, we can
1875 choose which set to walk based on which set is smaller. */
1878 bitmap exprset
= value_expressions
[val
];
1880 EXECUTE_IF_AND_IN_BITMAP (exprset
, &set
->expressions
, 0, i
, bi
)
1881 return expression_for_id (i
);
1886 /* Determine if EXPR, a memory expression, is ANTIC_IN at the top of
1887 BLOCK by seeing if it is not killed in the block. Note that we are
1888 only determining whether there is a store that kills it. Because
1889 of the order in which clean iterates over values, we are guaranteed
1890 that altered operands will have caused us to be eliminated from the
1891 ANTIC_IN set already. */
1894 value_dies_in_block_x (pre_expr expr
, basic_block block
)
1896 tree vuse
= PRE_EXPR_REFERENCE (expr
)->vuse
;
1897 vn_reference_t refx
= PRE_EXPR_REFERENCE (expr
);
1899 gimple_stmt_iterator gsi
;
1900 unsigned id
= get_expression_id (expr
);
1907 /* Lookup a previously calculated result. */
1908 if (EXPR_DIES (block
)
1909 && bitmap_bit_p (EXPR_DIES (block
), id
* 2))
1910 return bitmap_bit_p (EXPR_DIES (block
), id
* 2 + 1);
1912 /* A memory expression {e, VUSE} dies in the block if there is a
1913 statement that may clobber e. If, starting statement walk from the
1914 top of the basic block, a statement uses VUSE there can be no kill
1915 inbetween that use and the original statement that loaded {e, VUSE},
1916 so we can stop walking. */
1917 ref
.base
= NULL_TREE
;
1918 for (gsi
= gsi_start_bb (block
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1920 tree def_vuse
, def_vdef
;
1921 def
= gsi_stmt (gsi
);
1922 def_vuse
= gimple_vuse (def
);
1923 def_vdef
= gimple_vdef (def
);
1925 /* Not a memory statement. */
1929 /* Not a may-def. */
1932 /* A load with the same VUSE, we're done. */
1933 if (def_vuse
== vuse
)
1939 /* Init ref only if we really need it. */
1940 if (ref
.base
== NULL_TREE
1941 && !ao_ref_init_from_vn_reference (&ref
, refx
->set
, refx
->type
,
1947 /* If the statement may clobber expr, it dies. */
1948 if (stmt_may_clobber_ref_p_1 (def
, &ref
))
1955 /* Remember the result. */
1956 if (!EXPR_DIES (block
))
1957 EXPR_DIES (block
) = BITMAP_ALLOC (&grand_bitmap_obstack
);
1958 bitmap_set_bit (EXPR_DIES (block
), id
* 2);
1960 bitmap_set_bit (EXPR_DIES (block
), id
* 2 + 1);
1966 /* Determine if OP is valid in SET1 U SET2, which it is when the union
1967 contains its value-id. */
1970 op_valid_in_sets (bitmap_set_t set1
, bitmap_set_t set2
, tree op
)
1972 if (op
&& TREE_CODE (op
) == SSA_NAME
)
1974 unsigned int value_id
= VN_INFO (op
)->value_id
;
1975 if (!(bitmap_set_contains_value (set1
, value_id
)
1976 || (set2
&& bitmap_set_contains_value (set2
, value_id
))))
1982 /* Determine if the expression EXPR is valid in SET1 U SET2.
1983 ONLY SET2 CAN BE NULL.
1984 This means that we have a leader for each part of the expression
1985 (if it consists of values), or the expression is an SSA_NAME.
1986 For loads/calls, we also see if the vuse is killed in this block. */
1989 valid_in_sets (bitmap_set_t set1
, bitmap_set_t set2
, pre_expr expr
)
1994 /* By construction all NAMEs are available. Non-available
1995 NAMEs are removed by subtracting TMP_GEN from the sets. */
2000 vn_nary_op_t nary
= PRE_EXPR_NARY (expr
);
2001 for (i
= 0; i
< nary
->length
; i
++)
2002 if (!op_valid_in_sets (set1
, set2
, nary
->op
[i
]))
2009 vn_reference_t ref
= PRE_EXPR_REFERENCE (expr
);
2010 vn_reference_op_t vro
;
2013 FOR_EACH_VEC_ELT (ref
->operands
, i
, vro
)
2015 if (!op_valid_in_sets (set1
, set2
, vro
->op0
)
2016 || !op_valid_in_sets (set1
, set2
, vro
->op1
)
2017 || !op_valid_in_sets (set1
, set2
, vro
->op2
))
2027 /* Clean the set of expressions that are no longer valid in SET1 or
2028 SET2. This means expressions that are made up of values we have no
2029 leaders for in SET1 or SET2. This version is used for partial
2030 anticipation, which means it is not valid in either ANTIC_IN or
2034 dependent_clean (bitmap_set_t set1
, bitmap_set_t set2
)
2036 vec
<pre_expr
> exprs
= sorted_array_from_bitmap_set (set1
);
2040 FOR_EACH_VEC_ELT (exprs
, i
, expr
)
2042 if (!valid_in_sets (set1
, set2
, expr
))
2043 bitmap_remove_from_set (set1
, expr
);
2048 /* Clean the set of expressions that are no longer valid in SET. This
2049 means expressions that are made up of values we have no leaders for
2053 clean (bitmap_set_t set
)
2055 vec
<pre_expr
> exprs
= sorted_array_from_bitmap_set (set
);
2059 FOR_EACH_VEC_ELT (exprs
, i
, expr
)
2061 if (!valid_in_sets (set
, NULL
, expr
))
2062 bitmap_remove_from_set (set
, expr
);
2067 /* Clean the set of expressions that are no longer valid in SET because
2068 they are clobbered in BLOCK or because they trap and may not be executed. */
2071 prune_clobbered_mems (bitmap_set_t set
, basic_block block
)
2076 FOR_EACH_EXPR_ID_IN_SET (set
, i
, bi
)
2078 pre_expr expr
= expression_for_id (i
);
2079 if (expr
->kind
== REFERENCE
)
2081 vn_reference_t ref
= PRE_EXPR_REFERENCE (expr
);
2084 gimple def_stmt
= SSA_NAME_DEF_STMT (ref
->vuse
);
2085 if (!gimple_nop_p (def_stmt
)
2086 && ((gimple_bb (def_stmt
) != block
2087 && !dominated_by_p (CDI_DOMINATORS
,
2088 block
, gimple_bb (def_stmt
)))
2089 || (gimple_bb (def_stmt
) == block
2090 && value_dies_in_block_x (expr
, block
))))
2091 bitmap_remove_from_set (set
, expr
);
2094 else if (expr
->kind
== NARY
)
2096 vn_nary_op_t nary
= PRE_EXPR_NARY (expr
);
2097 /* If the NARY may trap make sure the block does not contain
2098 a possible exit point.
2099 ??? This is overly conservative if we translate AVAIL_OUT
2100 as the available expression might be after the exit point. */
2101 if (BB_MAY_NOTRETURN (block
)
2102 && vn_nary_may_trap (nary
))
2103 bitmap_remove_from_set (set
, expr
);
2108 static sbitmap has_abnormal_preds
;
2110 /* List of blocks that may have changed during ANTIC computation and
2111 thus need to be iterated over. */
2113 static sbitmap changed_blocks
;
2115 /* Compute the ANTIC set for BLOCK.
2117 If succs(BLOCK) > 1 then
2118 ANTIC_OUT[BLOCK] = intersection of ANTIC_IN[b] for all succ(BLOCK)
2119 else if succs(BLOCK) == 1 then
2120 ANTIC_OUT[BLOCK] = phi_translate (ANTIC_IN[succ(BLOCK)])
2122 ANTIC_IN[BLOCK] = clean(ANTIC_OUT[BLOCK] U EXP_GEN[BLOCK] - TMP_GEN[BLOCK])
2126 compute_antic_aux (basic_block block
, bool block_has_abnormal_pred_edge
)
2128 bool changed
= false;
2129 bitmap_set_t S
, old
, ANTIC_OUT
;
2135 old
= ANTIC_OUT
= S
= NULL
;
2136 BB_VISITED (block
) = 1;
2138 /* If any edges from predecessors are abnormal, antic_in is empty,
2140 if (block_has_abnormal_pred_edge
)
2141 goto maybe_dump_sets
;
2143 old
= ANTIC_IN (block
);
2144 ANTIC_OUT
= bitmap_set_new ();
2146 /* If the block has no successors, ANTIC_OUT is empty. */
2147 if (EDGE_COUNT (block
->succs
) == 0)
2149 /* If we have one successor, we could have some phi nodes to
2150 translate through. */
2151 else if (single_succ_p (block
))
2153 basic_block succ_bb
= single_succ (block
);
2154 gcc_assert (BB_VISITED (succ_bb
));
2155 phi_translate_set (ANTIC_OUT
, ANTIC_IN (succ_bb
), block
, succ_bb
);
2157 /* If we have multiple successors, we take the intersection of all of
2158 them. Note that in the case of loop exit phi nodes, we may have
2159 phis to translate through. */
2163 basic_block bprime
, first
= NULL
;
2165 auto_vec
<basic_block
> worklist (EDGE_COUNT (block
->succs
));
2166 FOR_EACH_EDGE (e
, ei
, block
->succs
)
2169 && BB_VISITED (e
->dest
))
2171 else if (BB_VISITED (e
->dest
))
2172 worklist
.quick_push (e
->dest
);
2175 /* Of multiple successors we have to have visited one already
2176 which is guaranteed by iteration order. */
2177 gcc_assert (first
!= NULL
);
2179 phi_translate_set (ANTIC_OUT
, ANTIC_IN (first
), block
, first
);
2181 FOR_EACH_VEC_ELT (worklist
, i
, bprime
)
2183 if (!gimple_seq_empty_p (phi_nodes (bprime
)))
2185 bitmap_set_t tmp
= bitmap_set_new ();
2186 phi_translate_set (tmp
, ANTIC_IN (bprime
), block
, bprime
);
2187 bitmap_set_and (ANTIC_OUT
, tmp
);
2188 bitmap_set_free (tmp
);
2191 bitmap_set_and (ANTIC_OUT
, ANTIC_IN (bprime
));
2195 /* Prune expressions that are clobbered in block and thus become
2196 invalid if translated from ANTIC_OUT to ANTIC_IN. */
2197 prune_clobbered_mems (ANTIC_OUT
, block
);
2199 /* Generate ANTIC_OUT - TMP_GEN. */
2200 S
= bitmap_set_subtract (ANTIC_OUT
, TMP_GEN (block
));
2202 /* Start ANTIC_IN with EXP_GEN - TMP_GEN. */
2203 ANTIC_IN (block
) = bitmap_set_subtract (EXP_GEN (block
),
2206 /* Then union in the ANTIC_OUT - TMP_GEN values,
2207 to get ANTIC_OUT U EXP_GEN - TMP_GEN */
2208 FOR_EACH_EXPR_ID_IN_SET (S
, bii
, bi
)
2209 bitmap_value_insert_into_set (ANTIC_IN (block
),
2210 expression_for_id (bii
));
2212 clean (ANTIC_IN (block
));
2214 if (!bitmap_set_equal (old
, ANTIC_IN (block
)))
2217 bitmap_set_bit (changed_blocks
, block
->index
);
2218 FOR_EACH_EDGE (e
, ei
, block
->preds
)
2219 bitmap_set_bit (changed_blocks
, e
->src
->index
);
2222 bitmap_clear_bit (changed_blocks
, block
->index
);
2225 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2228 print_bitmap_set (dump_file
, ANTIC_OUT
, "ANTIC_OUT", block
->index
);
2230 print_bitmap_set (dump_file
, ANTIC_IN (block
), "ANTIC_IN",
2234 print_bitmap_set (dump_file
, S
, "S", block
->index
);
2237 bitmap_set_free (old
);
2239 bitmap_set_free (S
);
2241 bitmap_set_free (ANTIC_OUT
);
2245 /* Compute PARTIAL_ANTIC for BLOCK.
2247 If succs(BLOCK) > 1 then
2248 PA_OUT[BLOCK] = value wise union of PA_IN[b] + all ANTIC_IN not
2249 in ANTIC_OUT for all succ(BLOCK)
2250 else if succs(BLOCK) == 1 then
2251 PA_OUT[BLOCK] = phi_translate (PA_IN[succ(BLOCK)])
2253 PA_IN[BLOCK] = dependent_clean(PA_OUT[BLOCK] - TMP_GEN[BLOCK]
2258 compute_partial_antic_aux (basic_block block
,
2259 bool block_has_abnormal_pred_edge
)
2261 bool changed
= false;
2262 bitmap_set_t old_PA_IN
;
2263 bitmap_set_t PA_OUT
;
2266 unsigned long max_pa
= PARAM_VALUE (PARAM_MAX_PARTIAL_ANTIC_LENGTH
);
2268 old_PA_IN
= PA_OUT
= NULL
;
2270 /* If any edges from predecessors are abnormal, antic_in is empty,
2272 if (block_has_abnormal_pred_edge
)
2273 goto maybe_dump_sets
;
2275 /* If there are too many partially anticipatable values in the
2276 block, phi_translate_set can take an exponential time: stop
2277 before the translation starts. */
2279 && single_succ_p (block
)
2280 && bitmap_count_bits (&PA_IN (single_succ (block
))->values
) > max_pa
)
2281 goto maybe_dump_sets
;
2283 old_PA_IN
= PA_IN (block
);
2284 PA_OUT
= bitmap_set_new ();
2286 /* If the block has no successors, ANTIC_OUT is empty. */
2287 if (EDGE_COUNT (block
->succs
) == 0)
2289 /* If we have one successor, we could have some phi nodes to
2290 translate through. Note that we can't phi translate across DFS
2291 back edges in partial antic, because it uses a union operation on
2292 the successors. For recurrences like IV's, we will end up
2293 generating a new value in the set on each go around (i + 3 (VH.1)
2294 VH.1 + 1 (VH.2), VH.2 + 1 (VH.3), etc), forever. */
2295 else if (single_succ_p (block
))
2297 basic_block succ
= single_succ (block
);
2298 if (!(single_succ_edge (block
)->flags
& EDGE_DFS_BACK
))
2299 phi_translate_set (PA_OUT
, PA_IN (succ
), block
, succ
);
2301 /* If we have multiple successors, we take the union of all of
2308 auto_vec
<basic_block
> worklist (EDGE_COUNT (block
->succs
));
2309 FOR_EACH_EDGE (e
, ei
, block
->succs
)
2311 if (e
->flags
& EDGE_DFS_BACK
)
2313 worklist
.quick_push (e
->dest
);
2315 if (worklist
.length () > 0)
2317 FOR_EACH_VEC_ELT (worklist
, i
, bprime
)
2322 FOR_EACH_EXPR_ID_IN_SET (ANTIC_IN (bprime
), i
, bi
)
2323 bitmap_value_insert_into_set (PA_OUT
,
2324 expression_for_id (i
));
2325 if (!gimple_seq_empty_p (phi_nodes (bprime
)))
2327 bitmap_set_t pa_in
= bitmap_set_new ();
2328 phi_translate_set (pa_in
, PA_IN (bprime
), block
, bprime
);
2329 FOR_EACH_EXPR_ID_IN_SET (pa_in
, i
, bi
)
2330 bitmap_value_insert_into_set (PA_OUT
,
2331 expression_for_id (i
));
2332 bitmap_set_free (pa_in
);
2335 FOR_EACH_EXPR_ID_IN_SET (PA_IN (bprime
), i
, bi
)
2336 bitmap_value_insert_into_set (PA_OUT
,
2337 expression_for_id (i
));
2342 /* Prune expressions that are clobbered in block and thus become
2343 invalid if translated from PA_OUT to PA_IN. */
2344 prune_clobbered_mems (PA_OUT
, block
);
2346 /* PA_IN starts with PA_OUT - TMP_GEN.
2347 Then we subtract things from ANTIC_IN. */
2348 PA_IN (block
) = bitmap_set_subtract (PA_OUT
, TMP_GEN (block
));
2350 /* For partial antic, we want to put back in the phi results, since
2351 we will properly avoid making them partially antic over backedges. */
2352 bitmap_ior_into (&PA_IN (block
)->values
, &PHI_GEN (block
)->values
);
2353 bitmap_ior_into (&PA_IN (block
)->expressions
, &PHI_GEN (block
)->expressions
);
2355 /* PA_IN[block] = PA_IN[block] - ANTIC_IN[block] */
2356 bitmap_set_subtract_values (PA_IN (block
), ANTIC_IN (block
));
2358 dependent_clean (PA_IN (block
), ANTIC_IN (block
));
2360 if (!bitmap_set_equal (old_PA_IN
, PA_IN (block
)))
2363 bitmap_set_bit (changed_blocks
, block
->index
);
2364 FOR_EACH_EDGE (e
, ei
, block
->preds
)
2365 bitmap_set_bit (changed_blocks
, e
->src
->index
);
2368 bitmap_clear_bit (changed_blocks
, block
->index
);
2371 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2374 print_bitmap_set (dump_file
, PA_OUT
, "PA_OUT", block
->index
);
2376 print_bitmap_set (dump_file
, PA_IN (block
), "PA_IN", block
->index
);
2379 bitmap_set_free (old_PA_IN
);
2381 bitmap_set_free (PA_OUT
);
2385 /* Compute ANTIC and partial ANTIC sets. */
2388 compute_antic (void)
2390 bool changed
= true;
2391 int num_iterations
= 0;
2395 /* If any predecessor edges are abnormal, we punt, so antic_in is empty.
2396 We pre-build the map of blocks with incoming abnormal edges here. */
2397 has_abnormal_preds
= sbitmap_alloc (last_basic_block_for_fn (cfun
));
2398 bitmap_clear (has_abnormal_preds
);
2400 FOR_ALL_BB_FN (block
, cfun
)
2405 FOR_EACH_EDGE (e
, ei
, block
->preds
)
2407 e
->flags
&= ~EDGE_DFS_BACK
;
2408 if (e
->flags
& EDGE_ABNORMAL
)
2410 bitmap_set_bit (has_abnormal_preds
, block
->index
);
2415 BB_VISITED (block
) = 0;
2417 /* While we are here, give empty ANTIC_IN sets to each block. */
2418 ANTIC_IN (block
) = bitmap_set_new ();
2419 PA_IN (block
) = bitmap_set_new ();
2422 /* At the exit block we anticipate nothing. */
2423 BB_VISITED (EXIT_BLOCK_PTR_FOR_FN (cfun
)) = 1;
2425 changed_blocks
= sbitmap_alloc (last_basic_block_for_fn (cfun
) + 1);
2426 bitmap_ones (changed_blocks
);
2429 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2430 fprintf (dump_file
, "Starting iteration %d\n", num_iterations
);
2431 /* ??? We need to clear our PHI translation cache here as the
2432 ANTIC sets shrink and we restrict valid translations to
2433 those having operands with leaders in ANTIC. Same below
2434 for PA ANTIC computation. */
2437 for (i
= postorder_num
- 1; i
>= 0; i
--)
2439 if (bitmap_bit_p (changed_blocks
, postorder
[i
]))
2441 basic_block block
= BASIC_BLOCK_FOR_FN (cfun
, postorder
[i
]);
2442 changed
|= compute_antic_aux (block
,
2443 bitmap_bit_p (has_abnormal_preds
,
2447 /* Theoretically possible, but *highly* unlikely. */
2448 gcc_checking_assert (num_iterations
< 500);
2451 statistics_histogram_event (cfun
, "compute_antic iterations",
2454 if (do_partial_partial
)
2456 bitmap_ones (changed_blocks
);
2457 mark_dfs_back_edges ();
2462 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2463 fprintf (dump_file
, "Starting iteration %d\n", num_iterations
);
2466 for (i
= postorder_num
- 1 ; i
>= 0; i
--)
2468 if (bitmap_bit_p (changed_blocks
, postorder
[i
]))
2470 basic_block block
= BASIC_BLOCK_FOR_FN (cfun
, postorder
[i
]);
2472 |= compute_partial_antic_aux (block
,
2473 bitmap_bit_p (has_abnormal_preds
,
2477 /* Theoretically possible, but *highly* unlikely. */
2478 gcc_checking_assert (num_iterations
< 500);
2480 statistics_histogram_event (cfun
, "compute_partial_antic iterations",
2483 sbitmap_free (has_abnormal_preds
);
2484 sbitmap_free (changed_blocks
);
2488 /* Inserted expressions are placed onto this worklist, which is used
2489 for performing quick dead code elimination of insertions we made
2490 that didn't turn out to be necessary. */
2491 static bitmap inserted_exprs
;
2493 /* The actual worker for create_component_ref_by_pieces. */
2496 create_component_ref_by_pieces_1 (basic_block block
, vn_reference_t ref
,
2497 unsigned int *operand
, gimple_seq
*stmts
)
2499 vn_reference_op_t currop
= &ref
->operands
[*operand
];
2502 switch (currop
->opcode
)
2506 tree folded
, sc
= NULL_TREE
;
2507 unsigned int nargs
= 0;
2509 if (TREE_CODE (currop
->op0
) == FUNCTION_DECL
)
2512 fn
= find_or_generate_expression (block
, currop
->op0
, stmts
);
2517 sc
= find_or_generate_expression (block
, currop
->op1
, stmts
);
2521 args
= XNEWVEC (tree
, ref
->operands
.length () - 1);
2522 while (*operand
< ref
->operands
.length ())
2524 args
[nargs
] = create_component_ref_by_pieces_1 (block
, ref
,
2530 folded
= build_call_array (currop
->type
,
2531 (TREE_CODE (fn
) == FUNCTION_DECL
2532 ? build_fold_addr_expr (fn
) : fn
),
2534 if (currop
->with_bounds
)
2535 CALL_WITH_BOUNDS_P (folded
) = true;
2538 CALL_EXPR_STATIC_CHAIN (folded
) = sc
;
2544 tree baseop
= create_component_ref_by_pieces_1 (block
, ref
, operand
,
2548 tree offset
= currop
->op0
;
2549 if (TREE_CODE (baseop
) == ADDR_EXPR
2550 && handled_component_p (TREE_OPERAND (baseop
, 0)))
2554 base
= get_addr_base_and_unit_offset (TREE_OPERAND (baseop
, 0),
2557 offset
= int_const_binop (PLUS_EXPR
, offset
,
2558 build_int_cst (TREE_TYPE (offset
),
2560 baseop
= build_fold_addr_expr (base
);
2562 return fold_build2 (MEM_REF
, currop
->type
, baseop
, offset
);
2565 case TARGET_MEM_REF
:
2567 tree genop0
= NULL_TREE
, genop1
= NULL_TREE
;
2568 vn_reference_op_t nextop
= &ref
->operands
[++*operand
];
2569 tree baseop
= create_component_ref_by_pieces_1 (block
, ref
, operand
,
2575 genop0
= find_or_generate_expression (block
, currop
->op0
, stmts
);
2581 genop1
= find_or_generate_expression (block
, nextop
->op0
, stmts
);
2585 return build5 (TARGET_MEM_REF
, currop
->type
,
2586 baseop
, currop
->op2
, genop0
, currop
->op1
, genop1
);
2592 gcc_assert (is_gimple_min_invariant (currop
->op0
));
2598 case VIEW_CONVERT_EXPR
:
2600 tree genop0
= create_component_ref_by_pieces_1 (block
, ref
, operand
,
2604 return fold_build1 (currop
->opcode
, currop
->type
, genop0
);
2607 case WITH_SIZE_EXPR
:
2609 tree genop0
= create_component_ref_by_pieces_1 (block
, ref
, operand
,
2613 tree genop1
= find_or_generate_expression (block
, currop
->op0
, stmts
);
2616 return fold_build2 (currop
->opcode
, currop
->type
, genop0
, genop1
);
2621 tree genop0
= create_component_ref_by_pieces_1 (block
, ref
, operand
,
2625 tree op1
= currop
->op0
;
2626 tree op2
= currop
->op1
;
2627 return fold_build3 (BIT_FIELD_REF
, currop
->type
, genop0
, op1
, op2
);
2630 /* For array ref vn_reference_op's, operand 1 of the array ref
2631 is op0 of the reference op and operand 3 of the array ref is
2633 case ARRAY_RANGE_REF
:
2637 tree genop1
= currop
->op0
;
2638 tree genop2
= currop
->op1
;
2639 tree genop3
= currop
->op2
;
2640 genop0
= create_component_ref_by_pieces_1 (block
, ref
, operand
,
2644 genop1
= find_or_generate_expression (block
, genop1
, stmts
);
2649 tree domain_type
= TYPE_DOMAIN (TREE_TYPE (genop0
));
2650 /* Drop zero minimum index if redundant. */
2651 if (integer_zerop (genop2
)
2653 || integer_zerop (TYPE_MIN_VALUE (domain_type
))))
2657 genop2
= find_or_generate_expression (block
, genop2
, stmts
);
2664 tree elmt_type
= TREE_TYPE (TREE_TYPE (genop0
));
2665 /* We can't always put a size in units of the element alignment
2666 here as the element alignment may be not visible. See
2667 PR43783. Simply drop the element size for constant
2669 if (tree_int_cst_equal (genop3
, TYPE_SIZE_UNIT (elmt_type
)))
2673 genop3
= size_binop (EXACT_DIV_EXPR
, genop3
,
2674 size_int (TYPE_ALIGN_UNIT (elmt_type
)));
2675 genop3
= find_or_generate_expression (block
, genop3
, stmts
);
2680 return build4 (currop
->opcode
, currop
->type
, genop0
, genop1
,
2687 tree genop2
= currop
->op1
;
2688 op0
= create_component_ref_by_pieces_1 (block
, ref
, operand
, stmts
);
2691 /* op1 should be a FIELD_DECL, which are represented by themselves. */
2695 genop2
= find_or_generate_expression (block
, genop2
, stmts
);
2699 return fold_build3 (COMPONENT_REF
, TREE_TYPE (op1
), op0
, op1
, genop2
);
2704 genop
= find_or_generate_expression (block
, currop
->op0
, stmts
);
2725 /* For COMPONENT_REF's and ARRAY_REF's, we can't have any intermediates for the
2726 COMPONENT_REF or MEM_REF or ARRAY_REF portion, because we'd end up with
2727 trying to rename aggregates into ssa form directly, which is a no no.
2729 Thus, this routine doesn't create temporaries, it just builds a
2730 single access expression for the array, calling
2731 find_or_generate_expression to build the innermost pieces.
2733 This function is a subroutine of create_expression_by_pieces, and
2734 should not be called on it's own unless you really know what you
2738 create_component_ref_by_pieces (basic_block block
, vn_reference_t ref
,
2741 unsigned int op
= 0;
2742 return create_component_ref_by_pieces_1 (block
, ref
, &op
, stmts
);
2745 /* Find a simple leader for an expression, or generate one using
2746 create_expression_by_pieces from a NARY expression for the value.
2747 BLOCK is the basic_block we are looking for leaders in.
2748 OP is the tree expression to find a leader for or generate.
2749 Returns the leader or NULL_TREE on failure. */
2752 find_or_generate_expression (basic_block block
, tree op
, gimple_seq
*stmts
)
2754 pre_expr expr
= get_or_alloc_expr_for (op
);
2755 unsigned int lookfor
= get_expr_value_id (expr
);
2756 pre_expr leader
= bitmap_find_leader (AVAIL_OUT (block
), lookfor
);
2759 if (leader
->kind
== NAME
)
2760 return PRE_EXPR_NAME (leader
);
2761 else if (leader
->kind
== CONSTANT
)
2762 return PRE_EXPR_CONSTANT (leader
);
2768 /* It must be a complex expression, so generate it recursively. Note
2769 that this is only necessary to handle gcc.dg/tree-ssa/ssa-pre28.c
2770 where the insert algorithm fails to insert a required expression. */
2771 bitmap exprset
= value_expressions
[lookfor
];
2774 EXECUTE_IF_SET_IN_BITMAP (exprset
, 0, i
, bi
)
2776 pre_expr temp
= expression_for_id (i
);
2777 /* We cannot insert random REFERENCE expressions at arbitrary
2778 places. We can insert NARYs which eventually re-materializes
2779 its operand values. */
2780 if (temp
->kind
== NARY
)
2781 return create_expression_by_pieces (block
, temp
, stmts
,
2782 get_expr_type (expr
));
2789 #define NECESSARY GF_PLF_1
2791 /* Create an expression in pieces, so that we can handle very complex
2792 expressions that may be ANTIC, but not necessary GIMPLE.
2793 BLOCK is the basic block the expression will be inserted into,
2794 EXPR is the expression to insert (in value form)
2795 STMTS is a statement list to append the necessary insertions into.
2797 This function will die if we hit some value that shouldn't be
2798 ANTIC but is (IE there is no leader for it, or its components).
2799 The function returns NULL_TREE in case a different antic expression
2800 has to be inserted first.
2801 This function may also generate expressions that are themselves
2802 partially or fully redundant. Those that are will be either made
2803 fully redundant during the next iteration of insert (for partially
2804 redundant ones), or eliminated by eliminate (for fully redundant
2808 create_expression_by_pieces (basic_block block
, pre_expr expr
,
2809 gimple_seq
*stmts
, tree type
)
2813 gimple_seq forced_stmts
= NULL
;
2814 unsigned int value_id
;
2815 gimple_stmt_iterator gsi
;
2816 tree exprtype
= type
? type
: get_expr_type (expr
);
2822 /* We may hit the NAME/CONSTANT case if we have to convert types
2823 that value numbering saw through. */
2825 folded
= PRE_EXPR_NAME (expr
);
2828 folded
= PRE_EXPR_CONSTANT (expr
);
2832 vn_reference_t ref
= PRE_EXPR_REFERENCE (expr
);
2833 folded
= create_component_ref_by_pieces (block
, ref
, stmts
);
2840 vn_nary_op_t nary
= PRE_EXPR_NARY (expr
);
2841 tree
*genop
= XALLOCAVEC (tree
, nary
->length
);
2843 for (i
= 0; i
< nary
->length
; ++i
)
2845 genop
[i
] = find_or_generate_expression (block
, nary
->op
[i
], stmts
);
2848 /* Ensure genop[] is properly typed for POINTER_PLUS_EXPR. It
2849 may have conversions stripped. */
2850 if (nary
->opcode
== POINTER_PLUS_EXPR
)
2853 genop
[i
] = gimple_convert (&forced_stmts
,
2854 nary
->type
, genop
[i
]);
2856 genop
[i
] = gimple_convert (&forced_stmts
,
2857 sizetype
, genop
[i
]);
2860 genop
[i
] = gimple_convert (&forced_stmts
,
2861 TREE_TYPE (nary
->op
[i
]), genop
[i
]);
2863 if (nary
->opcode
== CONSTRUCTOR
)
2865 vec
<constructor_elt
, va_gc
> *elts
= NULL
;
2866 for (i
= 0; i
< nary
->length
; ++i
)
2867 CONSTRUCTOR_APPEND_ELT (elts
, NULL_TREE
, genop
[i
]);
2868 folded
= build_constructor (nary
->type
, elts
);
2872 switch (nary
->length
)
2875 folded
= fold_build1 (nary
->opcode
, nary
->type
,
2879 folded
= fold_build2 (nary
->opcode
, nary
->type
,
2880 genop
[0], genop
[1]);
2883 folded
= fold_build3 (nary
->opcode
, nary
->type
,
2884 genop
[0], genop
[1], genop
[2]);
2896 if (!useless_type_conversion_p (exprtype
, TREE_TYPE (folded
)))
2897 folded
= fold_convert (exprtype
, folded
);
2899 /* Force the generated expression to be a sequence of GIMPLE
2901 We have to call unshare_expr because force_gimple_operand may
2902 modify the tree we pass to it. */
2903 gimple_seq tem
= NULL
;
2904 folded
= force_gimple_operand (unshare_expr (folded
), &tem
,
2906 gimple_seq_add_seq_without_update (&forced_stmts
, tem
);
2908 /* If we have any intermediate expressions to the value sets, add them
2909 to the value sets and chain them in the instruction stream. */
2912 gsi
= gsi_start (forced_stmts
);
2913 for (; !gsi_end_p (gsi
); gsi_next (&gsi
))
2915 gimple stmt
= gsi_stmt (gsi
);
2916 tree forcedname
= gimple_get_lhs (stmt
);
2919 if (TREE_CODE (forcedname
) == SSA_NAME
)
2921 bitmap_set_bit (inserted_exprs
, SSA_NAME_VERSION (forcedname
));
2922 VN_INFO_GET (forcedname
)->valnum
= forcedname
;
2923 VN_INFO (forcedname
)->value_id
= get_next_value_id ();
2924 nameexpr
= get_or_alloc_expr_for_name (forcedname
);
2925 add_to_value (VN_INFO (forcedname
)->value_id
, nameexpr
);
2926 bitmap_value_replace_in_set (NEW_SETS (block
), nameexpr
);
2927 bitmap_value_replace_in_set (AVAIL_OUT (block
), nameexpr
);
2930 gimple_set_vuse (stmt
, BB_LIVE_VOP_ON_EXIT (block
));
2931 gimple_set_modified (stmt
, true);
2933 gimple_seq_add_seq (stmts
, forced_stmts
);
2936 name
= make_temp_ssa_name (exprtype
, NULL
, "pretmp");
2937 newstmt
= gimple_build_assign (name
, folded
);
2938 gimple_set_vuse (newstmt
, BB_LIVE_VOP_ON_EXIT (block
));
2939 gimple_set_modified (newstmt
, true);
2940 gimple_set_plf (newstmt
, NECESSARY
, false);
2942 gimple_seq_add_stmt (stmts
, newstmt
);
2943 bitmap_set_bit (inserted_exprs
, SSA_NAME_VERSION (name
));
2945 /* Fold the last statement. */
2946 gsi
= gsi_last (*stmts
);
2947 if (fold_stmt_inplace (&gsi
))
2948 update_stmt (gsi_stmt (gsi
));
2950 /* Add a value number to the temporary.
2951 The value may already exist in either NEW_SETS, or AVAIL_OUT, because
2952 we are creating the expression by pieces, and this particular piece of
2953 the expression may have been represented. There is no harm in replacing
2955 value_id
= get_expr_value_id (expr
);
2956 VN_INFO_GET (name
)->value_id
= value_id
;
2957 VN_INFO (name
)->valnum
= sccvn_valnum_from_value_id (value_id
);
2958 if (VN_INFO (name
)->valnum
== NULL_TREE
)
2959 VN_INFO (name
)->valnum
= name
;
2960 gcc_assert (VN_INFO (name
)->valnum
!= NULL_TREE
);
2961 nameexpr
= get_or_alloc_expr_for_name (name
);
2962 add_to_value (value_id
, nameexpr
);
2963 if (NEW_SETS (block
))
2964 bitmap_value_replace_in_set (NEW_SETS (block
), nameexpr
);
2965 bitmap_value_replace_in_set (AVAIL_OUT (block
), nameexpr
);
2967 pre_stats
.insertions
++;
2968 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2970 fprintf (dump_file
, "Inserted ");
2971 print_gimple_stmt (dump_file
, newstmt
, 0, 0);
2972 fprintf (dump_file
, " in predecessor %d (%04d)\n",
2973 block
->index
, value_id
);
2980 /* Insert the to-be-made-available values of expression EXPRNUM for each
2981 predecessor, stored in AVAIL, into the predecessors of BLOCK, and
2982 merge the result with a phi node, given the same value number as
2983 NODE. Return true if we have inserted new stuff. */
2986 insert_into_preds_of_block (basic_block block
, unsigned int exprnum
,
2987 vec
<pre_expr
> avail
)
2989 pre_expr expr
= expression_for_id (exprnum
);
2991 unsigned int val
= get_expr_value_id (expr
);
2993 bool insertions
= false;
2998 tree type
= get_expr_type (expr
);
3002 /* Make sure we aren't creating an induction variable. */
3003 if (bb_loop_depth (block
) > 0 && EDGE_COUNT (block
->preds
) == 2)
3005 bool firstinsideloop
= false;
3006 bool secondinsideloop
= false;
3007 firstinsideloop
= flow_bb_inside_loop_p (block
->loop_father
,
3008 EDGE_PRED (block
, 0)->src
);
3009 secondinsideloop
= flow_bb_inside_loop_p (block
->loop_father
,
3010 EDGE_PRED (block
, 1)->src
);
3011 /* Induction variables only have one edge inside the loop. */
3012 if ((firstinsideloop
^ secondinsideloop
)
3013 && expr
->kind
!= REFERENCE
)
3015 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3016 fprintf (dump_file
, "Skipping insertion of phi for partial redundancy: Looks like an induction variable\n");
3021 /* Make the necessary insertions. */
3022 FOR_EACH_EDGE (pred
, ei
, block
->preds
)
3024 gimple_seq stmts
= NULL
;
3027 eprime
= avail
[pred
->dest_idx
];
3029 if (eprime
->kind
!= NAME
&& eprime
->kind
!= CONSTANT
)
3031 builtexpr
= create_expression_by_pieces (bprime
, eprime
,
3033 gcc_assert (!(pred
->flags
& EDGE_ABNORMAL
));
3034 gsi_insert_seq_on_edge (pred
, stmts
);
3037 /* We cannot insert a PHI node if we failed to insert
3042 avail
[pred
->dest_idx
] = get_or_alloc_expr_for_name (builtexpr
);
3045 else if (eprime
->kind
== CONSTANT
)
3047 /* Constants may not have the right type, fold_convert
3048 should give us back a constant with the right type. */
3049 tree constant
= PRE_EXPR_CONSTANT (eprime
);
3050 if (!useless_type_conversion_p (type
, TREE_TYPE (constant
)))
3052 tree builtexpr
= fold_convert (type
, constant
);
3053 if (!is_gimple_min_invariant (builtexpr
))
3055 tree forcedexpr
= force_gimple_operand (builtexpr
,
3058 if (!is_gimple_min_invariant (forcedexpr
))
3060 if (forcedexpr
!= builtexpr
)
3062 VN_INFO_GET (forcedexpr
)->valnum
= PRE_EXPR_CONSTANT (eprime
);
3063 VN_INFO (forcedexpr
)->value_id
= get_expr_value_id (eprime
);
3067 gimple_stmt_iterator gsi
;
3068 gsi
= gsi_start (stmts
);
3069 for (; !gsi_end_p (gsi
); gsi_next (&gsi
))
3071 gimple stmt
= gsi_stmt (gsi
);
3072 tree lhs
= gimple_get_lhs (stmt
);
3073 if (TREE_CODE (lhs
) == SSA_NAME
)
3074 bitmap_set_bit (inserted_exprs
,
3075 SSA_NAME_VERSION (lhs
));
3076 gimple_set_plf (stmt
, NECESSARY
, false);
3078 gsi_insert_seq_on_edge (pred
, stmts
);
3080 avail
[pred
->dest_idx
]
3081 = get_or_alloc_expr_for_name (forcedexpr
);
3085 avail
[pred
->dest_idx
]
3086 = get_or_alloc_expr_for_constant (builtexpr
);
3089 else if (eprime
->kind
== NAME
)
3091 /* We may have to do a conversion because our value
3092 numbering can look through types in certain cases, but
3093 our IL requires all operands of a phi node have the same
3095 tree name
= PRE_EXPR_NAME (eprime
);
3096 if (!useless_type_conversion_p (type
, TREE_TYPE (name
)))
3100 builtexpr
= fold_convert (type
, name
);
3101 forcedexpr
= force_gimple_operand (builtexpr
,
3105 if (forcedexpr
!= name
)
3107 VN_INFO_GET (forcedexpr
)->valnum
= VN_INFO (name
)->valnum
;
3108 VN_INFO (forcedexpr
)->value_id
= VN_INFO (name
)->value_id
;
3113 gimple_stmt_iterator gsi
;
3114 gsi
= gsi_start (stmts
);
3115 for (; !gsi_end_p (gsi
); gsi_next (&gsi
))
3117 gimple stmt
= gsi_stmt (gsi
);
3118 tree lhs
= gimple_get_lhs (stmt
);
3119 if (TREE_CODE (lhs
) == SSA_NAME
)
3120 bitmap_set_bit (inserted_exprs
, SSA_NAME_VERSION (lhs
));
3121 gimple_set_plf (stmt
, NECESSARY
, false);
3123 gsi_insert_seq_on_edge (pred
, stmts
);
3125 avail
[pred
->dest_idx
] = get_or_alloc_expr_for_name (forcedexpr
);
3129 /* If we didn't want a phi node, and we made insertions, we still have
3130 inserted new stuff, and thus return true. If we didn't want a phi node,
3131 and didn't make insertions, we haven't added anything new, so return
3133 if (nophi
&& insertions
)
3135 else if (nophi
&& !insertions
)
3138 /* Now build a phi for the new variable. */
3139 temp
= make_temp_ssa_name (type
, NULL
, "prephitmp");
3140 phi
= create_phi_node (temp
, block
);
3142 gimple_set_plf (phi
, NECESSARY
, false);
3143 VN_INFO_GET (temp
)->value_id
= val
;
3144 VN_INFO (temp
)->valnum
= sccvn_valnum_from_value_id (val
);
3145 if (VN_INFO (temp
)->valnum
== NULL_TREE
)
3146 VN_INFO (temp
)->valnum
= temp
;
3147 bitmap_set_bit (inserted_exprs
, SSA_NAME_VERSION (temp
));
3148 FOR_EACH_EDGE (pred
, ei
, block
->preds
)
3150 pre_expr ae
= avail
[pred
->dest_idx
];
3151 gcc_assert (get_expr_type (ae
) == type
3152 || useless_type_conversion_p (type
, get_expr_type (ae
)));
3153 if (ae
->kind
== CONSTANT
)
3154 add_phi_arg (phi
, unshare_expr (PRE_EXPR_CONSTANT (ae
)),
3155 pred
, UNKNOWN_LOCATION
);
3157 add_phi_arg (phi
, PRE_EXPR_NAME (ae
), pred
, UNKNOWN_LOCATION
);
3160 newphi
= get_or_alloc_expr_for_name (temp
);
3161 add_to_value (val
, newphi
);
3163 /* The value should *not* exist in PHI_GEN, or else we wouldn't be doing
3164 this insertion, since we test for the existence of this value in PHI_GEN
3165 before proceeding with the partial redundancy checks in insert_aux.
3167 The value may exist in AVAIL_OUT, in particular, it could be represented
3168 by the expression we are trying to eliminate, in which case we want the
3169 replacement to occur. If it's not existing in AVAIL_OUT, we want it
3172 Similarly, to the PHI_GEN case, the value should not exist in NEW_SETS of
3173 this block, because if it did, it would have existed in our dominator's
3174 AVAIL_OUT, and would have been skipped due to the full redundancy check.
3177 bitmap_insert_into_set (PHI_GEN (block
), newphi
);
3178 bitmap_value_replace_in_set (AVAIL_OUT (block
),
3180 bitmap_insert_into_set (NEW_SETS (block
),
3183 /* If we insert a PHI node for a conversion of another PHI node
3184 in the same basic-block try to preserve range information.
3185 This is important so that followup loop passes receive optimal
3186 number of iteration analysis results. See PR61743. */
3187 if (expr
->kind
== NARY
3188 && CONVERT_EXPR_CODE_P (expr
->u
.nary
->opcode
)
3189 && TREE_CODE (expr
->u
.nary
->op
[0]) == SSA_NAME
3190 && gimple_bb (SSA_NAME_DEF_STMT (expr
->u
.nary
->op
[0])) == block
3191 && INTEGRAL_TYPE_P (type
)
3192 && INTEGRAL_TYPE_P (TREE_TYPE (expr
->u
.nary
->op
[0]))
3193 && (TYPE_PRECISION (type
)
3194 >= TYPE_PRECISION (TREE_TYPE (expr
->u
.nary
->op
[0])))
3195 && SSA_NAME_RANGE_INFO (expr
->u
.nary
->op
[0]))
3198 if (get_range_info (expr
->u
.nary
->op
[0], &min
, &max
) == VR_RANGE
3199 && !wi::neg_p (min
, SIGNED
)
3200 && !wi::neg_p (max
, SIGNED
))
3201 /* Just handle extension and sign-changes of all-positive ranges. */
3202 set_range_info (temp
,
3203 SSA_NAME_RANGE_TYPE (expr
->u
.nary
->op
[0]),
3204 wide_int_storage::from (min
, TYPE_PRECISION (type
),
3206 wide_int_storage::from (max
, TYPE_PRECISION (type
),
3210 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3212 fprintf (dump_file
, "Created phi ");
3213 print_gimple_stmt (dump_file
, phi
, 0, 0);
3214 fprintf (dump_file
, " in block %d (%04d)\n", block
->index
, val
);
3222 /* Perform insertion of partially redundant values.
3223 For BLOCK, do the following:
3224 1. Propagate the NEW_SETS of the dominator into the current block.
3225 If the block has multiple predecessors,
3226 2a. Iterate over the ANTIC expressions for the block to see if
3227 any of them are partially redundant.
3228 2b. If so, insert them into the necessary predecessors to make
3229 the expression fully redundant.
3230 2c. Insert a new PHI merging the values of the predecessors.
3231 2d. Insert the new PHI, and the new expressions, into the
3233 3. Recursively call ourselves on the dominator children of BLOCK.
3235 Steps 1, 2a, and 3 are done by insert_aux. 2b, 2c and 2d are done by
3236 do_regular_insertion and do_partial_insertion.
3241 do_regular_insertion (basic_block block
, basic_block dom
)
3243 bool new_stuff
= false;
3244 vec
<pre_expr
> exprs
;
3246 auto_vec
<pre_expr
> avail
;
3249 exprs
= sorted_array_from_bitmap_set (ANTIC_IN (block
));
3250 avail
.safe_grow (EDGE_COUNT (block
->preds
));
3252 FOR_EACH_VEC_ELT (exprs
, i
, expr
)
3254 if (expr
->kind
== NARY
3255 || expr
->kind
== REFERENCE
)
3258 bool by_some
= false;
3259 bool cant_insert
= false;
3260 bool all_same
= true;
3261 pre_expr first_s
= NULL
;
3264 pre_expr eprime
= NULL
;
3266 pre_expr edoubleprime
= NULL
;
3267 bool do_insertion
= false;
3269 val
= get_expr_value_id (expr
);
3270 if (bitmap_set_contains_value (PHI_GEN (block
), val
))
3272 if (bitmap_set_contains_value (AVAIL_OUT (dom
), val
))
3274 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3276 fprintf (dump_file
, "Found fully redundant value: ");
3277 print_pre_expr (dump_file
, expr
);
3278 fprintf (dump_file
, "\n");
3283 FOR_EACH_EDGE (pred
, ei
, block
->preds
)
3285 unsigned int vprime
;
3287 /* We should never run insertion for the exit block
3288 and so not come across fake pred edges. */
3289 gcc_assert (!(pred
->flags
& EDGE_FAKE
));
3291 eprime
= phi_translate (expr
, ANTIC_IN (block
), NULL
,
3294 /* eprime will generally only be NULL if the
3295 value of the expression, translated
3296 through the PHI for this predecessor, is
3297 undefined. If that is the case, we can't
3298 make the expression fully redundant,
3299 because its value is undefined along a
3300 predecessor path. We can thus break out
3301 early because it doesn't matter what the
3302 rest of the results are. */
3305 avail
[pred
->dest_idx
] = NULL
;
3310 eprime
= fully_constant_expression (eprime
);
3311 vprime
= get_expr_value_id (eprime
);
3312 edoubleprime
= bitmap_find_leader (AVAIL_OUT (bprime
),
3314 if (edoubleprime
== NULL
)
3316 avail
[pred
->dest_idx
] = eprime
;
3321 avail
[pred
->dest_idx
] = edoubleprime
;
3323 /* We want to perform insertions to remove a redundancy on
3324 a path in the CFG we want to optimize for speed. */
3325 if (optimize_edge_for_speed_p (pred
))
3326 do_insertion
= true;
3327 if (first_s
== NULL
)
3328 first_s
= edoubleprime
;
3329 else if (!pre_expr_d::equal (first_s
, edoubleprime
))
3333 /* If we can insert it, it's not the same value
3334 already existing along every predecessor, and
3335 it's defined by some predecessor, it is
3336 partially redundant. */
3337 if (!cant_insert
&& !all_same
&& by_some
)
3341 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3343 fprintf (dump_file
, "Skipping partial redundancy for "
3345 print_pre_expr (dump_file
, expr
);
3346 fprintf (dump_file
, " (%04d), no redundancy on to be "
3347 "optimized for speed edge\n", val
);
3350 else if (dbg_cnt (treepre_insert
))
3352 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3354 fprintf (dump_file
, "Found partial redundancy for "
3356 print_pre_expr (dump_file
, expr
);
3357 fprintf (dump_file
, " (%04d)\n",
3358 get_expr_value_id (expr
));
3360 if (insert_into_preds_of_block (block
,
3361 get_expression_id (expr
),
3366 /* If all edges produce the same value and that value is
3367 an invariant, then the PHI has the same value on all
3368 edges. Note this. */
3369 else if (!cant_insert
&& all_same
)
3371 gcc_assert (edoubleprime
->kind
== CONSTANT
3372 || edoubleprime
->kind
== NAME
);
3374 tree temp
= make_temp_ssa_name (get_expr_type (expr
),
3377 = gimple_build_assign (temp
,
3378 edoubleprime
->kind
== CONSTANT
?
3379 PRE_EXPR_CONSTANT (edoubleprime
) :
3380 PRE_EXPR_NAME (edoubleprime
));
3381 gimple_stmt_iterator gsi
= gsi_after_labels (block
);
3382 gsi_insert_before (&gsi
, assign
, GSI_NEW_STMT
);
3384 gimple_set_plf (assign
, NECESSARY
, false);
3385 VN_INFO_GET (temp
)->value_id
= val
;
3386 VN_INFO (temp
)->valnum
= sccvn_valnum_from_value_id (val
);
3387 if (VN_INFO (temp
)->valnum
== NULL_TREE
)
3388 VN_INFO (temp
)->valnum
= temp
;
3389 bitmap_set_bit (inserted_exprs
, SSA_NAME_VERSION (temp
));
3390 pre_expr newe
= get_or_alloc_expr_for_name (temp
);
3391 add_to_value (val
, newe
);
3392 bitmap_value_replace_in_set (AVAIL_OUT (block
), newe
);
3393 bitmap_insert_into_set (NEW_SETS (block
), newe
);
3403 /* Perform insertion for partially anticipatable expressions. There
3404 is only one case we will perform insertion for these. This case is
3405 if the expression is partially anticipatable, and fully available.
3406 In this case, we know that putting it earlier will enable us to
3407 remove the later computation. */
3411 do_partial_partial_insertion (basic_block block
, basic_block dom
)
3413 bool new_stuff
= false;
3414 vec
<pre_expr
> exprs
;
3416 auto_vec
<pre_expr
> avail
;
3419 exprs
= sorted_array_from_bitmap_set (PA_IN (block
));
3420 avail
.safe_grow (EDGE_COUNT (block
->preds
));
3422 FOR_EACH_VEC_ELT (exprs
, i
, expr
)
3424 if (expr
->kind
== NARY
3425 || expr
->kind
== REFERENCE
)
3429 bool cant_insert
= false;
3432 pre_expr eprime
= NULL
;
3435 val
= get_expr_value_id (expr
);
3436 if (bitmap_set_contains_value (PHI_GEN (block
), val
))
3438 if (bitmap_set_contains_value (AVAIL_OUT (dom
), val
))
3441 FOR_EACH_EDGE (pred
, ei
, block
->preds
)
3443 unsigned int vprime
;
3444 pre_expr edoubleprime
;
3446 /* We should never run insertion for the exit block
3447 and so not come across fake pred edges. */
3448 gcc_assert (!(pred
->flags
& EDGE_FAKE
));
3450 eprime
= phi_translate (expr
, ANTIC_IN (block
),
3454 /* eprime will generally only be NULL if the
3455 value of the expression, translated
3456 through the PHI for this predecessor, is
3457 undefined. If that is the case, we can't
3458 make the expression fully redundant,
3459 because its value is undefined along a
3460 predecessor path. We can thus break out
3461 early because it doesn't matter what the
3462 rest of the results are. */
3465 avail
[pred
->dest_idx
] = NULL
;
3470 eprime
= fully_constant_expression (eprime
);
3471 vprime
= get_expr_value_id (eprime
);
3472 edoubleprime
= bitmap_find_leader (AVAIL_OUT (bprime
), vprime
);
3473 avail
[pred
->dest_idx
] = edoubleprime
;
3474 if (edoubleprime
== NULL
)
3481 /* If we can insert it, it's not the same value
3482 already existing along every predecessor, and
3483 it's defined by some predecessor, it is
3484 partially redundant. */
3485 if (!cant_insert
&& by_all
)
3488 bool do_insertion
= false;
3490 /* Insert only if we can remove a later expression on a path
3491 that we want to optimize for speed.
3492 The phi node that we will be inserting in BLOCK is not free,
3493 and inserting it for the sake of !optimize_for_speed successor
3494 may cause regressions on the speed path. */
3495 FOR_EACH_EDGE (succ
, ei
, block
->succs
)
3497 if (bitmap_set_contains_value (PA_IN (succ
->dest
), val
)
3498 || bitmap_set_contains_value (ANTIC_IN (succ
->dest
), val
))
3500 if (optimize_edge_for_speed_p (succ
))
3501 do_insertion
= true;
3507 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3509 fprintf (dump_file
, "Skipping partial partial redundancy "
3511 print_pre_expr (dump_file
, expr
);
3512 fprintf (dump_file
, " (%04d), not (partially) anticipated "
3513 "on any to be optimized for speed edges\n", val
);
3516 else if (dbg_cnt (treepre_insert
))
3518 pre_stats
.pa_insert
++;
3519 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3521 fprintf (dump_file
, "Found partial partial redundancy "
3523 print_pre_expr (dump_file
, expr
);
3524 fprintf (dump_file
, " (%04d)\n",
3525 get_expr_value_id (expr
));
3527 if (insert_into_preds_of_block (block
,
3528 get_expression_id (expr
),
3541 insert_aux (basic_block block
)
3544 bool new_stuff
= false;
3549 dom
= get_immediate_dominator (CDI_DOMINATORS
, block
);
3554 bitmap_set_t newset
= NEW_SETS (dom
);
3557 /* Note that we need to value_replace both NEW_SETS, and
3558 AVAIL_OUT. For both the case of NEW_SETS, the value may be
3559 represented by some non-simple expression here that we want
3560 to replace it with. */
3561 FOR_EACH_EXPR_ID_IN_SET (newset
, i
, bi
)
3563 pre_expr expr
= expression_for_id (i
);
3564 bitmap_value_replace_in_set (NEW_SETS (block
), expr
);
3565 bitmap_value_replace_in_set (AVAIL_OUT (block
), expr
);
3568 if (!single_pred_p (block
))
3570 new_stuff
|= do_regular_insertion (block
, dom
);
3571 if (do_partial_partial
)
3572 new_stuff
|= do_partial_partial_insertion (block
, dom
);
3576 for (son
= first_dom_son (CDI_DOMINATORS
, block
);
3578 son
= next_dom_son (CDI_DOMINATORS
, son
))
3580 new_stuff
|= insert_aux (son
);
3586 /* Perform insertion of partially redundant values. */
3591 bool new_stuff
= true;
3593 int num_iterations
= 0;
3595 FOR_ALL_BB_FN (bb
, cfun
)
3596 NEW_SETS (bb
) = bitmap_set_new ();
3601 if (dump_file
&& dump_flags
& TDF_DETAILS
)
3602 fprintf (dump_file
, "Starting insert iteration %d\n", num_iterations
);
3603 new_stuff
= insert_aux (ENTRY_BLOCK_PTR_FOR_FN (cfun
));
3605 /* Clear the NEW sets before the next iteration. We have already
3606 fully propagated its contents. */
3608 FOR_ALL_BB_FN (bb
, cfun
)
3609 bitmap_set_free (NEW_SETS (bb
));
3611 statistics_histogram_event (cfun
, "insert iterations", num_iterations
);
3615 /* Compute the AVAIL set for all basic blocks.
3617 This function performs value numbering of the statements in each basic
3618 block. The AVAIL sets are built from information we glean while doing
3619 this value numbering, since the AVAIL sets contain only one entry per
3622 AVAIL_IN[BLOCK] = AVAIL_OUT[dom(BLOCK)].
3623 AVAIL_OUT[BLOCK] = AVAIL_IN[BLOCK] U PHI_GEN[BLOCK] U TMP_GEN[BLOCK]. */
3626 compute_avail (void)
3629 basic_block block
, son
;
3630 basic_block
*worklist
;
3634 /* We pretend that default definitions are defined in the entry block.
3635 This includes function arguments and the static chain decl. */
3636 for (i
= 1; i
< num_ssa_names
; ++i
)
3638 tree name
= ssa_name (i
);
3641 || !SSA_NAME_IS_DEFAULT_DEF (name
)
3642 || has_zero_uses (name
)
3643 || virtual_operand_p (name
))
3646 e
= get_or_alloc_expr_for_name (name
);
3647 add_to_value (get_expr_value_id (e
), e
);
3648 bitmap_insert_into_set (TMP_GEN (ENTRY_BLOCK_PTR_FOR_FN (cfun
)), e
);
3649 bitmap_value_insert_into_set (AVAIL_OUT (ENTRY_BLOCK_PTR_FOR_FN (cfun
)),
3653 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3655 print_bitmap_set (dump_file
, TMP_GEN (ENTRY_BLOCK_PTR_FOR_FN (cfun
)),
3656 "tmp_gen", ENTRY_BLOCK
);
3657 print_bitmap_set (dump_file
, AVAIL_OUT (ENTRY_BLOCK_PTR_FOR_FN (cfun
)),
3658 "avail_out", ENTRY_BLOCK
);
3661 /* Allocate the worklist. */
3662 worklist
= XNEWVEC (basic_block
, n_basic_blocks_for_fn (cfun
));
3664 /* Seed the algorithm by putting the dominator children of the entry
3665 block on the worklist. */
3666 for (son
= first_dom_son (CDI_DOMINATORS
, ENTRY_BLOCK_PTR_FOR_FN (cfun
));
3668 son
= next_dom_son (CDI_DOMINATORS
, son
))
3669 worklist
[sp
++] = son
;
3671 BB_LIVE_VOP_ON_EXIT (ENTRY_BLOCK_PTR_FOR_FN (cfun
))
3672 = ssa_default_def (cfun
, gimple_vop (cfun
));
3674 /* Loop until the worklist is empty. */
3680 /* Pick a block from the worklist. */
3681 block
= worklist
[--sp
];
3683 /* Initially, the set of available values in BLOCK is that of
3684 its immediate dominator. */
3685 dom
= get_immediate_dominator (CDI_DOMINATORS
, block
);
3688 bitmap_set_copy (AVAIL_OUT (block
), AVAIL_OUT (dom
));
3689 BB_LIVE_VOP_ON_EXIT (block
) = BB_LIVE_VOP_ON_EXIT (dom
);
3692 /* Generate values for PHI nodes. */
3693 for (gphi_iterator gsi
= gsi_start_phis (block
); !gsi_end_p (gsi
);
3696 tree result
= gimple_phi_result (gsi
.phi ());
3698 /* We have no need for virtual phis, as they don't represent
3699 actual computations. */
3700 if (virtual_operand_p (result
))
3702 BB_LIVE_VOP_ON_EXIT (block
) = result
;
3706 pre_expr e
= get_or_alloc_expr_for_name (result
);
3707 add_to_value (get_expr_value_id (e
), e
);
3708 bitmap_value_insert_into_set (AVAIL_OUT (block
), e
);
3709 bitmap_insert_into_set (PHI_GEN (block
), e
);
3712 BB_MAY_NOTRETURN (block
) = 0;
3714 /* Now compute value numbers and populate value sets with all
3715 the expressions computed in BLOCK. */
3716 for (gimple_stmt_iterator gsi
= gsi_start_bb (block
); !gsi_end_p (gsi
);
3722 stmt
= gsi_stmt (gsi
);
3724 /* Cache whether the basic-block has any non-visible side-effect
3726 If this isn't a call or it is the last stmt in the
3727 basic-block then the CFG represents things correctly. */
3728 if (is_gimple_call (stmt
) && !stmt_ends_bb_p (stmt
))
3730 /* Non-looping const functions always return normally.
3731 Otherwise the call might not return or have side-effects
3732 that forbids hoisting possibly trapping expressions
3734 int flags
= gimple_call_flags (stmt
);
3735 if (!(flags
& ECF_CONST
)
3736 || (flags
& ECF_LOOPING_CONST_OR_PURE
))
3737 BB_MAY_NOTRETURN (block
) = 1;
3740 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, iter
, SSA_OP_DEF
)
3742 pre_expr e
= get_or_alloc_expr_for_name (op
);
3744 add_to_value (get_expr_value_id (e
), e
);
3745 bitmap_insert_into_set (TMP_GEN (block
), e
);
3746 bitmap_value_insert_into_set (AVAIL_OUT (block
), e
);
3749 if (gimple_vdef (stmt
))
3750 BB_LIVE_VOP_ON_EXIT (block
) = gimple_vdef (stmt
);
3752 if (gimple_has_side_effects (stmt
)
3753 || stmt_could_throw_p (stmt
)
3754 || is_gimple_debug (stmt
))
3757 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, iter
, SSA_OP_USE
)
3759 if (ssa_undefined_value_p (op
))
3761 pre_expr e
= get_or_alloc_expr_for_name (op
);
3762 bitmap_value_insert_into_set (EXP_GEN (block
), e
);
3765 switch (gimple_code (stmt
))
3773 vn_reference_s ref1
;
3774 pre_expr result
= NULL
;
3776 /* We can value number only calls to real functions. */
3777 if (gimple_call_internal_p (stmt
))
3780 vn_reference_lookup_call (as_a
<gcall
*> (stmt
), &ref
, &ref1
);
3784 /* If the value of the call is not invalidated in
3785 this block until it is computed, add the expression
3787 if (!gimple_vuse (stmt
)
3789 (SSA_NAME_DEF_STMT (gimple_vuse (stmt
))) == GIMPLE_PHI
3790 || gimple_bb (SSA_NAME_DEF_STMT
3791 (gimple_vuse (stmt
))) != block
)
3793 result
= pre_expr_pool
.allocate ();
3794 result
->kind
= REFERENCE
;
3796 PRE_EXPR_REFERENCE (result
) = ref
;
3798 get_or_alloc_expression_id (result
);
3799 add_to_value (get_expr_value_id (result
), result
);
3800 bitmap_value_insert_into_set (EXP_GEN (block
), result
);
3807 pre_expr result
= NULL
;
3808 switch (vn_get_stmt_kind (stmt
))
3812 enum tree_code code
= gimple_assign_rhs_code (stmt
);
3815 /* COND_EXPR and VEC_COND_EXPR are awkward in
3816 that they contain an embedded complex expression.
3817 Don't even try to shove those through PRE. */
3818 if (code
== COND_EXPR
3819 || code
== VEC_COND_EXPR
)
3822 vn_nary_op_lookup_stmt (stmt
, &nary
);
3826 /* If the NARY traps and there was a preceding
3827 point in the block that might not return avoid
3828 adding the nary to EXP_GEN. */
3829 if (BB_MAY_NOTRETURN (block
)
3830 && vn_nary_may_trap (nary
))
3833 result
= pre_expr_pool
.allocate ();
3834 result
->kind
= NARY
;
3836 PRE_EXPR_NARY (result
) = nary
;
3843 vn_reference_lookup (gimple_assign_rhs1 (stmt
),
3849 /* If the value of the reference is not invalidated in
3850 this block until it is computed, add the expression
3852 if (gimple_vuse (stmt
))
3856 def_stmt
= SSA_NAME_DEF_STMT (gimple_vuse (stmt
));
3857 while (!gimple_nop_p (def_stmt
)
3858 && gimple_code (def_stmt
) != GIMPLE_PHI
3859 && gimple_bb (def_stmt
) == block
)
3861 if (stmt_may_clobber_ref_p
3862 (def_stmt
, gimple_assign_rhs1 (stmt
)))
3868 = SSA_NAME_DEF_STMT (gimple_vuse (def_stmt
));
3874 result
= pre_expr_pool
.allocate ();
3875 result
->kind
= REFERENCE
;
3877 PRE_EXPR_REFERENCE (result
) = ref
;
3885 get_or_alloc_expression_id (result
);
3886 add_to_value (get_expr_value_id (result
), result
);
3887 bitmap_value_insert_into_set (EXP_GEN (block
), result
);
3895 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3897 print_bitmap_set (dump_file
, EXP_GEN (block
),
3898 "exp_gen", block
->index
);
3899 print_bitmap_set (dump_file
, PHI_GEN (block
),
3900 "phi_gen", block
->index
);
3901 print_bitmap_set (dump_file
, TMP_GEN (block
),
3902 "tmp_gen", block
->index
);
3903 print_bitmap_set (dump_file
, AVAIL_OUT (block
),
3904 "avail_out", block
->index
);
3907 /* Put the dominator children of BLOCK on the worklist of blocks
3908 to compute available sets for. */
3909 for (son
= first_dom_son (CDI_DOMINATORS
, block
);
3911 son
= next_dom_son (CDI_DOMINATORS
, son
))
3912 worklist
[sp
++] = son
;
3919 /* Local state for the eliminate domwalk. */
3920 static vec
<gimple
> el_to_remove
;
3921 static vec
<gimple
> el_to_fixup
;
3922 static unsigned int el_todo
;
3923 static vec
<tree
> el_avail
;
3924 static vec
<tree
> el_avail_stack
;
3926 /* Return a leader for OP that is available at the current point of the
3927 eliminate domwalk. */
3930 eliminate_avail (tree op
)
3932 tree valnum
= VN_INFO (op
)->valnum
;
3933 if (TREE_CODE (valnum
) == SSA_NAME
)
3935 if (SSA_NAME_IS_DEFAULT_DEF (valnum
))
3937 if (el_avail
.length () > SSA_NAME_VERSION (valnum
))
3938 return el_avail
[SSA_NAME_VERSION (valnum
)];
3940 else if (is_gimple_min_invariant (valnum
))
3945 /* At the current point of the eliminate domwalk make OP available. */
3948 eliminate_push_avail (tree op
)
3950 tree valnum
= VN_INFO (op
)->valnum
;
3951 if (TREE_CODE (valnum
) == SSA_NAME
)
3953 if (el_avail
.length () <= SSA_NAME_VERSION (valnum
))
3954 el_avail
.safe_grow_cleared (SSA_NAME_VERSION (valnum
) + 1);
3956 if (el_avail
[SSA_NAME_VERSION (valnum
)])
3957 pushop
= el_avail
[SSA_NAME_VERSION (valnum
)];
3958 el_avail_stack
.safe_push (pushop
);
3959 el_avail
[SSA_NAME_VERSION (valnum
)] = op
;
3963 /* Insert the expression recorded by SCCVN for VAL at *GSI. Returns
3964 the leader for the expression if insertion was successful. */
3967 eliminate_insert (gimple_stmt_iterator
*gsi
, tree val
)
3969 tree expr
= vn_get_expr_for (val
);
3970 if (!CONVERT_EXPR_P (expr
)
3971 && TREE_CODE (expr
) != VIEW_CONVERT_EXPR
)
3974 tree op
= TREE_OPERAND (expr
, 0);
3975 tree leader
= TREE_CODE (op
) == SSA_NAME
? eliminate_avail (op
) : op
;
3979 tree res
= make_temp_ssa_name (TREE_TYPE (val
), NULL
, "pretmp");
3980 gassign
*tem
= gimple_build_assign (res
,
3981 fold_build1 (TREE_CODE (expr
),
3982 TREE_TYPE (expr
), leader
));
3983 gsi_insert_before (gsi
, tem
, GSI_SAME_STMT
);
3984 VN_INFO_GET (res
)->valnum
= val
;
3986 if (TREE_CODE (leader
) == SSA_NAME
)
3987 gimple_set_plf (SSA_NAME_DEF_STMT (leader
), NECESSARY
, true);
3989 pre_stats
.insertions
++;
3990 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3992 fprintf (dump_file
, "Inserted ");
3993 print_gimple_stmt (dump_file
, tem
, 0, 0);
3999 class eliminate_dom_walker
: public dom_walker
4002 eliminate_dom_walker (cdi_direction direction
, bool do_pre_
)
4003 : dom_walker (direction
), do_pre (do_pre_
) {}
4005 virtual void before_dom_children (basic_block
);
4006 virtual void after_dom_children (basic_block
);
4011 /* Perform elimination for the basic-block B during the domwalk. */
4014 eliminate_dom_walker::before_dom_children (basic_block b
)
4017 el_avail_stack
.safe_push (NULL_TREE
);
4019 /* ??? If we do nothing for unreachable blocks then this will confuse
4020 tailmerging. Eventually we can reduce its reliance on SCCVN now
4021 that we fully copy/constant-propagate (most) things. */
4023 for (gphi_iterator gsi
= gsi_start_phis (b
); !gsi_end_p (gsi
);)
4025 gphi
*phi
= gsi
.phi ();
4026 tree res
= PHI_RESULT (phi
);
4028 if (virtual_operand_p (res
))
4034 tree sprime
= eliminate_avail (res
);
4038 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4040 fprintf (dump_file
, "Replaced redundant PHI node defining ");
4041 print_generic_expr (dump_file
, res
, 0);
4042 fprintf (dump_file
, " with ");
4043 print_generic_expr (dump_file
, sprime
, 0);
4044 fprintf (dump_file
, "\n");
4047 /* If we inserted this PHI node ourself, it's not an elimination. */
4049 && bitmap_bit_p (inserted_exprs
, SSA_NAME_VERSION (res
)))
4052 pre_stats
.eliminations
++;
4054 /* If we will propagate into all uses don't bother to do
4056 if (may_propagate_copy (res
, sprime
))
4058 /* Mark the PHI for removal. */
4059 el_to_remove
.safe_push (phi
);
4064 remove_phi_node (&gsi
, false);
4067 && !bitmap_bit_p (inserted_exprs
, SSA_NAME_VERSION (res
))
4068 && TREE_CODE (sprime
) == SSA_NAME
)
4069 gimple_set_plf (SSA_NAME_DEF_STMT (sprime
), NECESSARY
, true);
4071 if (!useless_type_conversion_p (TREE_TYPE (res
), TREE_TYPE (sprime
)))
4072 sprime
= fold_convert (TREE_TYPE (res
), sprime
);
4073 gimple stmt
= gimple_build_assign (res
, sprime
);
4074 /* ??? It cannot yet be necessary (DOM walk). */
4075 gimple_set_plf (stmt
, NECESSARY
, gimple_plf (phi
, NECESSARY
));
4077 gimple_stmt_iterator gsi2
= gsi_after_labels (b
);
4078 gsi_insert_before (&gsi2
, stmt
, GSI_NEW_STMT
);
4082 eliminate_push_avail (res
);
4086 for (gimple_stmt_iterator gsi
= gsi_start_bb (b
);
4090 tree sprime
= NULL_TREE
;
4091 gimple stmt
= gsi_stmt (gsi
);
4092 tree lhs
= gimple_get_lhs (stmt
);
4093 if (lhs
&& TREE_CODE (lhs
) == SSA_NAME
4094 && !gimple_has_volatile_ops (stmt
)
4095 /* See PR43491. Do not replace a global register variable when
4096 it is a the RHS of an assignment. Do replace local register
4097 variables since gcc does not guarantee a local variable will
4098 be allocated in register.
4099 ??? The fix isn't effective here. This should instead
4100 be ensured by not value-numbering them the same but treating
4101 them like volatiles? */
4102 && !(gimple_assign_single_p (stmt
)
4103 && (TREE_CODE (gimple_assign_rhs1 (stmt
)) == VAR_DECL
4104 && DECL_HARD_REGISTER (gimple_assign_rhs1 (stmt
))
4105 && is_global_var (gimple_assign_rhs1 (stmt
)))))
4107 sprime
= eliminate_avail (lhs
);
4110 /* If there is no existing usable leader but SCCVN thinks
4111 it has an expression it wants to use as replacement,
4113 tree val
= VN_INFO (lhs
)->valnum
;
4115 && TREE_CODE (val
) == SSA_NAME
4116 && VN_INFO (val
)->needs_insertion
4117 && VN_INFO (val
)->expr
!= NULL_TREE
4118 && (sprime
= eliminate_insert (&gsi
, val
)) != NULL_TREE
)
4119 eliminate_push_avail (sprime
);
4122 /* If this now constitutes a copy duplicate points-to
4123 and range info appropriately. This is especially
4124 important for inserted code. See tree-ssa-copy.c
4125 for similar code. */
4127 && TREE_CODE (sprime
) == SSA_NAME
)
4129 basic_block sprime_b
= gimple_bb (SSA_NAME_DEF_STMT (sprime
));
4130 if (POINTER_TYPE_P (TREE_TYPE (lhs
))
4131 && SSA_NAME_PTR_INFO (lhs
)
4132 && !SSA_NAME_PTR_INFO (sprime
))
4134 duplicate_ssa_name_ptr_info (sprime
,
4135 SSA_NAME_PTR_INFO (lhs
));
4137 mark_ptr_info_alignment_unknown
4138 (SSA_NAME_PTR_INFO (sprime
));
4140 else if (!POINTER_TYPE_P (TREE_TYPE (lhs
))
4141 && SSA_NAME_RANGE_INFO (lhs
)
4142 && !SSA_NAME_RANGE_INFO (sprime
)
4144 duplicate_ssa_name_range_info (sprime
,
4145 SSA_NAME_RANGE_TYPE (lhs
),
4146 SSA_NAME_RANGE_INFO (lhs
));
4149 /* Inhibit the use of an inserted PHI on a loop header when
4150 the address of the memory reference is a simple induction
4151 variable. In other cases the vectorizer won't do anything
4152 anyway (either it's loop invariant or a complicated
4155 && TREE_CODE (sprime
) == SSA_NAME
4157 && flag_tree_loop_vectorize
4158 && loop_outer (b
->loop_father
)
4159 && has_zero_uses (sprime
)
4160 && bitmap_bit_p (inserted_exprs
, SSA_NAME_VERSION (sprime
))
4161 && gimple_assign_load_p (stmt
))
4163 gimple def_stmt
= SSA_NAME_DEF_STMT (sprime
);
4164 basic_block def_bb
= gimple_bb (def_stmt
);
4165 if (gimple_code (def_stmt
) == GIMPLE_PHI
4166 && b
->loop_father
->header
== def_bb
)
4171 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, iter
, SSA_OP_USE
)
4174 def_bb
= gimple_bb (SSA_NAME_DEF_STMT (op
));
4176 && flow_bb_inside_loop_p (b
->loop_father
, def_bb
)
4177 && simple_iv (b
->loop_father
,
4178 b
->loop_father
, op
, &iv
, true))
4186 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4188 fprintf (dump_file
, "Not replacing ");
4189 print_gimple_expr (dump_file
, stmt
, 0, 0);
4190 fprintf (dump_file
, " with ");
4191 print_generic_expr (dump_file
, sprime
, 0);
4192 fprintf (dump_file
, " which would add a loop"
4193 " carried dependence to loop %d\n",
4194 b
->loop_father
->num
);
4196 /* Don't keep sprime available. */
4204 /* If we can propagate the value computed for LHS into
4205 all uses don't bother doing anything with this stmt. */
4206 if (may_propagate_copy (lhs
, sprime
))
4208 /* Mark it for removal. */
4209 el_to_remove
.safe_push (stmt
);
4211 /* ??? Don't count copy/constant propagations. */
4212 if (gimple_assign_single_p (stmt
)
4213 && (TREE_CODE (gimple_assign_rhs1 (stmt
)) == SSA_NAME
4214 || gimple_assign_rhs1 (stmt
) == sprime
))
4217 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4219 fprintf (dump_file
, "Replaced ");
4220 print_gimple_expr (dump_file
, stmt
, 0, 0);
4221 fprintf (dump_file
, " with ");
4222 print_generic_expr (dump_file
, sprime
, 0);
4223 fprintf (dump_file
, " in all uses of ");
4224 print_gimple_stmt (dump_file
, stmt
, 0, 0);
4227 pre_stats
.eliminations
++;
4231 /* If this is an assignment from our leader (which
4232 happens in the case the value-number is a constant)
4233 then there is nothing to do. */
4234 if (gimple_assign_single_p (stmt
)
4235 && sprime
== gimple_assign_rhs1 (stmt
))
4238 /* Else replace its RHS. */
4239 bool can_make_abnormal_goto
4240 = is_gimple_call (stmt
)
4241 && stmt_can_make_abnormal_goto (stmt
);
4243 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4245 fprintf (dump_file
, "Replaced ");
4246 print_gimple_expr (dump_file
, stmt
, 0, 0);
4247 fprintf (dump_file
, " with ");
4248 print_generic_expr (dump_file
, sprime
, 0);
4249 fprintf (dump_file
, " in ");
4250 print_gimple_stmt (dump_file
, stmt
, 0, 0);
4253 if (TREE_CODE (sprime
) == SSA_NAME
)
4254 gimple_set_plf (SSA_NAME_DEF_STMT (sprime
),
4257 pre_stats
.eliminations
++;
4258 gimple orig_stmt
= stmt
;
4259 if (!useless_type_conversion_p (TREE_TYPE (lhs
),
4260 TREE_TYPE (sprime
)))
4261 sprime
= fold_convert (TREE_TYPE (lhs
), sprime
);
4262 tree vdef
= gimple_vdef (stmt
);
4263 tree vuse
= gimple_vuse (stmt
);
4264 propagate_tree_value_into_stmt (&gsi
, sprime
);
4265 stmt
= gsi_stmt (gsi
);
4267 if (vdef
!= gimple_vdef (stmt
))
4268 VN_INFO (vdef
)->valnum
= vuse
;
4270 /* If we removed EH side-effects from the statement, clean
4271 its EH information. */
4272 if (maybe_clean_or_replace_eh_stmt (orig_stmt
, stmt
))
4274 bitmap_set_bit (need_eh_cleanup
,
4275 gimple_bb (stmt
)->index
);
4276 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4277 fprintf (dump_file
, " Removed EH side-effects.\n");
4280 /* Likewise for AB side-effects. */
4281 if (can_make_abnormal_goto
4282 && !stmt_can_make_abnormal_goto (stmt
))
4284 bitmap_set_bit (need_ab_cleanup
,
4285 gimple_bb (stmt
)->index
);
4286 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4287 fprintf (dump_file
, " Removed AB side-effects.\n");
4294 /* If the statement is a scalar store, see if the expression
4295 has the same value number as its rhs. If so, the store is
4297 if (gimple_assign_single_p (stmt
)
4298 && !gimple_has_volatile_ops (stmt
)
4299 && !is_gimple_reg (gimple_assign_lhs (stmt
))
4300 && (TREE_CODE (gimple_assign_rhs1 (stmt
)) == SSA_NAME
4301 || is_gimple_min_invariant (gimple_assign_rhs1 (stmt
))))
4304 tree rhs
= gimple_assign_rhs1 (stmt
);
4305 val
= vn_reference_lookup (gimple_assign_lhs (stmt
),
4306 gimple_vuse (stmt
), VN_WALK
, NULL
);
4307 if (TREE_CODE (rhs
) == SSA_NAME
)
4308 rhs
= VN_INFO (rhs
)->valnum
;
4310 && operand_equal_p (val
, rhs
, 0))
4312 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4314 fprintf (dump_file
, "Deleted redundant store ");
4315 print_gimple_stmt (dump_file
, stmt
, 0, 0);
4318 /* Queue stmt for removal. */
4319 el_to_remove
.safe_push (stmt
);
4324 bool can_make_abnormal_goto
= stmt_can_make_abnormal_goto (stmt
);
4325 bool was_noreturn
= (is_gimple_call (stmt
)
4326 && gimple_call_noreturn_p (stmt
));
4327 tree vdef
= gimple_vdef (stmt
);
4328 tree vuse
= gimple_vuse (stmt
);
4330 /* If we didn't replace the whole stmt (or propagate the result
4331 into all uses), replace all uses on this stmt with their
4333 use_operand_p use_p
;
4335 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, iter
, SSA_OP_USE
)
4337 tree use
= USE_FROM_PTR (use_p
);
4338 /* ??? The call code above leaves stmt operands un-updated. */
4339 if (TREE_CODE (use
) != SSA_NAME
)
4341 tree sprime
= eliminate_avail (use
);
4342 if (sprime
&& sprime
!= use
4343 && may_propagate_copy (use
, sprime
)
4344 /* We substitute into debug stmts to avoid excessive
4345 debug temporaries created by removed stmts, but we need
4346 to avoid doing so for inserted sprimes as we never want
4347 to create debug temporaries for them. */
4349 || TREE_CODE (sprime
) != SSA_NAME
4350 || !is_gimple_debug (stmt
)
4351 || !bitmap_bit_p (inserted_exprs
, SSA_NAME_VERSION (sprime
))))
4353 propagate_value (use_p
, sprime
);
4354 gimple_set_modified (stmt
, true);
4355 if (TREE_CODE (sprime
) == SSA_NAME
4356 && !is_gimple_debug (stmt
))
4357 gimple_set_plf (SSA_NAME_DEF_STMT (sprime
),
4362 /* Visit indirect calls and turn them into direct calls if
4363 possible using the devirtualization machinery. */
4364 if (gcall
*call_stmt
= dyn_cast
<gcall
*> (stmt
))
4366 tree fn
= gimple_call_fn (call_stmt
);
4368 && flag_devirtualize
4369 && virtual_method_call_p (fn
))
4371 tree otr_type
= obj_type_ref_class (fn
);
4373 ipa_polymorphic_call_context
context (current_function_decl
, fn
, stmt
, &instance
);
4376 context
.get_dynamic_type (instance
, OBJ_TYPE_REF_OBJECT (fn
), otr_type
, stmt
);
4378 vec
<cgraph_node
*>targets
4379 = possible_polymorphic_call_targets (obj_type_ref_class (fn
),
4381 (OBJ_TYPE_REF_TOKEN (fn
)),
4384 if (dump_enabled_p ())
4385 dump_possible_polymorphic_call_targets (dump_file
,
4386 obj_type_ref_class (fn
),
4388 (OBJ_TYPE_REF_TOKEN (fn
)),
4390 if (final
&& targets
.length () <= 1 && dbg_cnt (devirt
))
4393 if (targets
.length () == 1)
4394 fn
= targets
[0]->decl
;
4396 fn
= builtin_decl_implicit (BUILT_IN_UNREACHABLE
);
4397 if (dump_enabled_p ())
4399 location_t loc
= gimple_location_safe (stmt
);
4400 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS
, loc
,
4401 "converting indirect call to "
4403 cgraph_node::get (fn
)->name ());
4405 gimple_call_set_fndecl (call_stmt
, fn
);
4406 maybe_remove_unused_call_args (cfun
, call_stmt
);
4407 gimple_set_modified (stmt
, true);
4412 if (gimple_modified_p (stmt
))
4414 /* If a formerly non-invariant ADDR_EXPR is turned into an
4415 invariant one it was on a separate stmt. */
4416 if (gimple_assign_single_p (stmt
)
4417 && TREE_CODE (gimple_assign_rhs1 (stmt
)) == ADDR_EXPR
)
4418 recompute_tree_invariant_for_addr_expr (gimple_assign_rhs1 (stmt
));
4419 gimple old_stmt
= stmt
;
4420 if (is_gimple_call (stmt
))
4422 /* ??? Only fold calls inplace for now, this may create new
4423 SSA names which in turn will confuse free_scc_vn SSA name
4425 fold_stmt_inplace (&gsi
);
4426 /* When changing a call into a noreturn call, cfg cleanup
4427 is needed to fix up the noreturn call. */
4428 if (!was_noreturn
&& gimple_call_noreturn_p (stmt
))
4429 el_to_fixup
.safe_push (stmt
);
4434 stmt
= gsi_stmt (gsi
);
4435 if ((gimple_code (stmt
) == GIMPLE_COND
4436 && (gimple_cond_true_p (as_a
<gcond
*> (stmt
))
4437 || gimple_cond_false_p (as_a
<gcond
*> (stmt
))))
4438 || (gimple_code (stmt
) == GIMPLE_SWITCH
4439 && TREE_CODE (gimple_switch_index (
4440 as_a
<gswitch
*> (stmt
)))
4442 el_todo
|= TODO_cleanup_cfg
;
4444 /* If we removed EH side-effects from the statement, clean
4445 its EH information. */
4446 if (maybe_clean_or_replace_eh_stmt (old_stmt
, stmt
))
4448 bitmap_set_bit (need_eh_cleanup
,
4449 gimple_bb (stmt
)->index
);
4450 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4451 fprintf (dump_file
, " Removed EH side-effects.\n");
4453 /* Likewise for AB side-effects. */
4454 if (can_make_abnormal_goto
4455 && !stmt_can_make_abnormal_goto (stmt
))
4457 bitmap_set_bit (need_ab_cleanup
,
4458 gimple_bb (stmt
)->index
);
4459 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4460 fprintf (dump_file
, " Removed AB side-effects.\n");
4463 if (vdef
!= gimple_vdef (stmt
))
4464 VN_INFO (vdef
)->valnum
= vuse
;
4467 /* Make new values available - for fully redundant LHS we
4468 continue with the next stmt above and skip this. */
4470 FOR_EACH_SSA_DEF_OPERAND (defp
, stmt
, iter
, SSA_OP_DEF
)
4471 eliminate_push_avail (DEF_FROM_PTR (defp
));
4474 /* Replace destination PHI arguments. */
4477 FOR_EACH_EDGE (e
, ei
, b
->succs
)
4479 for (gphi_iterator gsi
= gsi_start_phis (e
->dest
);
4483 gphi
*phi
= gsi
.phi ();
4484 use_operand_p use_p
= PHI_ARG_DEF_PTR_FROM_EDGE (phi
, e
);
4485 tree arg
= USE_FROM_PTR (use_p
);
4486 if (TREE_CODE (arg
) != SSA_NAME
4487 || virtual_operand_p (arg
))
4489 tree sprime
= eliminate_avail (arg
);
4490 if (sprime
&& may_propagate_copy (arg
, sprime
))
4492 propagate_value (use_p
, sprime
);
4493 if (TREE_CODE (sprime
) == SSA_NAME
)
4494 gimple_set_plf (SSA_NAME_DEF_STMT (sprime
), NECESSARY
, true);
4500 /* Make no longer available leaders no longer available. */
4503 eliminate_dom_walker::after_dom_children (basic_block
)
4506 while ((entry
= el_avail_stack
.pop ()) != NULL_TREE
)
4508 tree valnum
= VN_INFO (entry
)->valnum
;
4509 tree old
= el_avail
[SSA_NAME_VERSION (valnum
)];
4511 el_avail
[SSA_NAME_VERSION (valnum
)] = NULL_TREE
;
4513 el_avail
[SSA_NAME_VERSION (valnum
)] = entry
;
4517 /* Eliminate fully redundant computations. */
4520 eliminate (bool do_pre
)
4522 gimple_stmt_iterator gsi
;
4525 need_eh_cleanup
= BITMAP_ALLOC (NULL
);
4526 need_ab_cleanup
= BITMAP_ALLOC (NULL
);
4528 el_to_remove
.create (0);
4529 el_to_fixup
.create (0);
4531 el_avail
.create (num_ssa_names
);
4532 el_avail_stack
.create (0);
4534 eliminate_dom_walker (CDI_DOMINATORS
,
4535 do_pre
).walk (cfun
->cfg
->x_entry_block_ptr
);
4537 el_avail
.release ();
4538 el_avail_stack
.release ();
4540 /* We cannot remove stmts during BB walk, especially not release SSA
4541 names there as this confuses the VN machinery. The stmts ending
4542 up in el_to_remove are either stores or simple copies.
4543 Remove stmts in reverse order to make debug stmt creation possible. */
4544 while (!el_to_remove
.is_empty ())
4546 stmt
= el_to_remove
.pop ();
4548 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4550 fprintf (dump_file
, "Removing dead stmt ");
4551 print_gimple_stmt (dump_file
, stmt
, 0, 0);
4555 if (gimple_code (stmt
) == GIMPLE_PHI
)
4556 lhs
= gimple_phi_result (stmt
);
4558 lhs
= gimple_get_lhs (stmt
);
4561 && TREE_CODE (lhs
) == SSA_NAME
)
4562 bitmap_clear_bit (inserted_exprs
, SSA_NAME_VERSION (lhs
));
4564 gsi
= gsi_for_stmt (stmt
);
4565 if (gimple_code (stmt
) == GIMPLE_PHI
)
4566 remove_phi_node (&gsi
, true);
4569 basic_block bb
= gimple_bb (stmt
);
4570 unlink_stmt_vdef (stmt
);
4571 if (gsi_remove (&gsi
, true))
4572 bitmap_set_bit (need_eh_cleanup
, bb
->index
);
4573 release_defs (stmt
);
4576 /* Removing a stmt may expose a forwarder block. */
4577 el_todo
|= TODO_cleanup_cfg
;
4579 el_to_remove
.release ();
4581 /* Fixup stmts that became noreturn calls. This may require splitting
4582 blocks and thus isn't possible during the dominator walk. Do this
4583 in reverse order so we don't inadvertedly remove a stmt we want to
4584 fixup by visiting a dominating now noreturn call first. */
4585 while (!el_to_fixup
.is_empty ())
4587 stmt
= el_to_fixup
.pop ();
4589 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4591 fprintf (dump_file
, "Fixing up noreturn call ");
4592 print_gimple_stmt (dump_file
, stmt
, 0, 0);
4595 if (fixup_noreturn_call (stmt
))
4596 el_todo
|= TODO_cleanup_cfg
;
4598 el_to_fixup
.release ();
4603 /* Perform CFG cleanups made necessary by elimination. */
4606 fini_eliminate (void)
4608 bool do_eh_cleanup
= !bitmap_empty_p (need_eh_cleanup
);
4609 bool do_ab_cleanup
= !bitmap_empty_p (need_ab_cleanup
);
4612 gimple_purge_all_dead_eh_edges (need_eh_cleanup
);
4615 gimple_purge_all_dead_abnormal_call_edges (need_ab_cleanup
);
4617 BITMAP_FREE (need_eh_cleanup
);
4618 BITMAP_FREE (need_ab_cleanup
);
4620 if (do_eh_cleanup
|| do_ab_cleanup
)
4621 return TODO_cleanup_cfg
;
4625 /* Borrow a bit of tree-ssa-dce.c for the moment.
4626 XXX: In 4.1, we should be able to just run a DCE pass after PRE, though
4627 this may be a bit faster, and we may want critical edges kept split. */
4629 /* If OP's defining statement has not already been determined to be necessary,
4630 mark that statement necessary. Return the stmt, if it is newly
4633 static inline gimple
4634 mark_operand_necessary (tree op
)
4640 if (TREE_CODE (op
) != SSA_NAME
)
4643 stmt
= SSA_NAME_DEF_STMT (op
);
4646 if (gimple_plf (stmt
, NECESSARY
)
4647 || gimple_nop_p (stmt
))
4650 gimple_set_plf (stmt
, NECESSARY
, true);
4654 /* Because we don't follow exactly the standard PRE algorithm, and decide not
4655 to insert PHI nodes sometimes, and because value numbering of casts isn't
4656 perfect, we sometimes end up inserting dead code. This simple DCE-like
4657 pass removes any insertions we made that weren't actually used. */
4660 remove_dead_inserted_code (void)
4667 worklist
= BITMAP_ALLOC (NULL
);
4668 EXECUTE_IF_SET_IN_BITMAP (inserted_exprs
, 0, i
, bi
)
4670 t
= SSA_NAME_DEF_STMT (ssa_name (i
));
4671 if (gimple_plf (t
, NECESSARY
))
4672 bitmap_set_bit (worklist
, i
);
4674 while (!bitmap_empty_p (worklist
))
4676 i
= bitmap_first_set_bit (worklist
);
4677 bitmap_clear_bit (worklist
, i
);
4678 t
= SSA_NAME_DEF_STMT (ssa_name (i
));
4680 /* PHI nodes are somewhat special in that each PHI alternative has
4681 data and control dependencies. All the statements feeding the
4682 PHI node's arguments are always necessary. */
4683 if (gimple_code (t
) == GIMPLE_PHI
)
4687 for (k
= 0; k
< gimple_phi_num_args (t
); k
++)
4689 tree arg
= PHI_ARG_DEF (t
, k
);
4690 if (TREE_CODE (arg
) == SSA_NAME
)
4692 gimple n
= mark_operand_necessary (arg
);
4694 bitmap_set_bit (worklist
, SSA_NAME_VERSION (arg
));
4700 /* Propagate through the operands. Examine all the USE, VUSE and
4701 VDEF operands in this statement. Mark all the statements
4702 which feed this statement's uses as necessary. */
4706 /* The operands of VDEF expressions are also needed as they
4707 represent potential definitions that may reach this
4708 statement (VDEF operands allow us to follow def-def
4711 FOR_EACH_SSA_TREE_OPERAND (use
, t
, iter
, SSA_OP_ALL_USES
)
4713 gimple n
= mark_operand_necessary (use
);
4715 bitmap_set_bit (worklist
, SSA_NAME_VERSION (use
));
4720 EXECUTE_IF_SET_IN_BITMAP (inserted_exprs
, 0, i
, bi
)
4722 t
= SSA_NAME_DEF_STMT (ssa_name (i
));
4723 if (!gimple_plf (t
, NECESSARY
))
4725 gimple_stmt_iterator gsi
;
4727 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4729 fprintf (dump_file
, "Removing unnecessary insertion:");
4730 print_gimple_stmt (dump_file
, t
, 0, 0);
4733 gsi
= gsi_for_stmt (t
);
4734 if (gimple_code (t
) == GIMPLE_PHI
)
4735 remove_phi_node (&gsi
, true);
4738 gsi_remove (&gsi
, true);
4743 BITMAP_FREE (worklist
);
4747 /* Initialize data structures used by PRE. */
4754 next_expression_id
= 1;
4755 expressions
.create (0);
4756 expressions
.safe_push (NULL
);
4757 value_expressions
.create (get_max_value_id () + 1);
4758 value_expressions
.safe_grow_cleared (get_max_value_id () + 1);
4759 name_to_id
.create (0);
4761 inserted_exprs
= BITMAP_ALLOC (NULL
);
4763 connect_infinite_loops_to_exit ();
4764 memset (&pre_stats
, 0, sizeof (pre_stats
));
4766 postorder
= XNEWVEC (int, n_basic_blocks_for_fn (cfun
));
4767 postorder_num
= inverted_post_order_compute (postorder
);
4769 alloc_aux_for_blocks (sizeof (struct bb_bitmap_sets
));
4771 calculate_dominance_info (CDI_POST_DOMINATORS
);
4772 calculate_dominance_info (CDI_DOMINATORS
);
4774 bitmap_obstack_initialize (&grand_bitmap_obstack
);
4775 phi_translate_table
= new hash_table
<expr_pred_trans_d
> (5110);
4776 expression_to_id
= new hash_table
<pre_expr_d
> (num_ssa_names
* 3);
4777 FOR_ALL_BB_FN (bb
, cfun
)
4779 EXP_GEN (bb
) = bitmap_set_new ();
4780 PHI_GEN (bb
) = bitmap_set_new ();
4781 TMP_GEN (bb
) = bitmap_set_new ();
4782 AVAIL_OUT (bb
) = bitmap_set_new ();
4787 /* Deallocate data structures used by PRE. */
4793 value_expressions
.release ();
4794 BITMAP_FREE (inserted_exprs
);
4795 bitmap_obstack_release (&grand_bitmap_obstack
);
4796 bitmap_set_pool
.release ();
4797 pre_expr_pool
.release ();
4798 delete phi_translate_table
;
4799 phi_translate_table
= NULL
;
4800 delete expression_to_id
;
4801 expression_to_id
= NULL
;
4802 name_to_id
.release ();
4804 free_aux_for_blocks ();
4806 free_dominance_info (CDI_POST_DOMINATORS
);
4811 const pass_data pass_data_pre
=
4813 GIMPLE_PASS
, /* type */
4815 OPTGROUP_NONE
, /* optinfo_flags */
4816 TV_TREE_PRE
, /* tv_id */
4817 /* PROP_no_crit_edges is ensured by placing pass_split_crit_edges before
4819 ( PROP_no_crit_edges
| PROP_cfg
| PROP_ssa
), /* properties_required */
4820 0, /* properties_provided */
4821 PROP_no_crit_edges
, /* properties_destroyed */
4822 TODO_rebuild_alias
, /* todo_flags_start */
4823 0, /* todo_flags_finish */
4826 class pass_pre
: public gimple_opt_pass
4829 pass_pre (gcc::context
*ctxt
)
4830 : gimple_opt_pass (pass_data_pre
, ctxt
)
4833 /* opt_pass methods: */
4834 virtual bool gate (function
*) { return flag_tree_pre
!= 0; }
4835 virtual unsigned int execute (function
*);
4837 }; // class pass_pre
4840 pass_pre::execute (function
*fun
)
4842 unsigned int todo
= 0;
4844 do_partial_partial
=
4845 flag_tree_partial_pre
&& optimize_function_for_speed_p (fun
);
4847 /* This has to happen before SCCVN runs because
4848 loop_optimizer_init may create new phis, etc. */
4849 loop_optimizer_init (LOOPS_NORMAL
);
4851 if (!run_scc_vn (VN_WALK
))
4853 loop_optimizer_finalize ();
4860 /* Collect and value number expressions computed in each basic block. */
4863 /* Insert can get quite slow on an incredibly large number of basic
4864 blocks due to some quadratic behavior. Until this behavior is
4865 fixed, don't run it when he have an incredibly large number of
4866 bb's. If we aren't going to run insert, there is no point in
4867 computing ANTIC, either, even though it's plenty fast. */
4868 if (n_basic_blocks_for_fn (fun
) < 4000)
4874 /* Make sure to remove fake edges before committing our inserts.
4875 This makes sure we don't end up with extra critical edges that
4876 we would need to split. */
4877 remove_fake_exit_edges ();
4878 gsi_commit_edge_inserts ();
4880 /* Eliminate folds statements which might (should not...) end up
4881 not keeping virtual operands up-to-date. */
4882 gcc_assert (!need_ssa_update_p (fun
));
4884 /* Remove all the redundant expressions. */
4885 todo
|= eliminate (true);
4887 statistics_counter_event (fun
, "Insertions", pre_stats
.insertions
);
4888 statistics_counter_event (fun
, "PA inserted", pre_stats
.pa_insert
);
4889 statistics_counter_event (fun
, "New PHIs", pre_stats
.phis
);
4890 statistics_counter_event (fun
, "Eliminated", pre_stats
.eliminations
);
4892 clear_expression_ids ();
4893 remove_dead_inserted_code ();
4897 todo
|= fini_eliminate ();
4898 loop_optimizer_finalize ();
4900 /* TODO: tail_merge_optimize may merge all predecessors of a block, in which
4901 case we can merge the block with the remaining predecessor of the block.
4903 - call merge_blocks after each tail merge iteration
4904 - call merge_blocks after all tail merge iterations
4905 - mark TODO_cleanup_cfg when necessary
4906 - share the cfg cleanup with fini_pre. */
4907 todo
|= tail_merge_optimize (todo
);
4911 /* Tail merging invalidates the virtual SSA web, together with
4912 cfg-cleanup opportunities exposed by PRE this will wreck the
4913 SSA updating machinery. So make sure to run update-ssa
4914 manually, before eventually scheduling cfg-cleanup as part of
4916 update_ssa (TODO_update_ssa_only_virtuals
);
4924 make_pass_pre (gcc::context
*ctxt
)
4926 return new pass_pre (ctxt
);
4931 const pass_data pass_data_fre
=
4933 GIMPLE_PASS
, /* type */
4935 OPTGROUP_NONE
, /* optinfo_flags */
4936 TV_TREE_FRE
, /* tv_id */
4937 ( PROP_cfg
| PROP_ssa
), /* properties_required */
4938 0, /* properties_provided */
4939 0, /* properties_destroyed */
4940 0, /* todo_flags_start */
4941 0, /* todo_flags_finish */
4944 class pass_fre
: public gimple_opt_pass
4947 pass_fre (gcc::context
*ctxt
)
4948 : gimple_opt_pass (pass_data_fre
, ctxt
)
4951 /* opt_pass methods: */
4952 opt_pass
* clone () { return new pass_fre (m_ctxt
); }
4953 virtual bool gate (function
*) { return flag_tree_fre
!= 0; }
4954 virtual unsigned int execute (function
*);
4956 }; // class pass_fre
4959 pass_fre::execute (function
*fun
)
4961 unsigned int todo
= 0;
4963 if (!run_scc_vn (VN_WALKREWRITE
))
4966 memset (&pre_stats
, 0, sizeof (pre_stats
));
4968 /* Remove all the redundant expressions. */
4969 todo
|= eliminate (false);
4971 todo
|= fini_eliminate ();
4975 statistics_counter_event (fun
, "Insertions", pre_stats
.insertions
);
4976 statistics_counter_event (fun
, "Eliminated", pre_stats
.eliminations
);
4984 make_pass_fre (gcc::context
*ctxt
)
4986 return new pass_fre (ctxt
);