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"
29 #include "double-int.h"
36 #include "fold-const.h"
38 #include "hard-reg-set.h"
40 #include "dominance.h"
43 #include "basic-block.h"
44 #include "gimple-pretty-print.h"
45 #include "tree-inline.h"
46 #include "hash-table.h"
47 #include "tree-ssa-alias.h"
48 #include "internal-fn.h"
49 #include "gimple-fold.h"
51 #include "gimple-expr.h"
55 #include "gimple-iterator.h"
56 #include "gimplify-me.h"
57 #include "gimple-ssa.h"
59 #include "tree-phinodes.h"
60 #include "ssa-iterators.h"
61 #include "stringpool.h"
62 #include "tree-ssanames.h"
63 #include "tree-ssa-loop.h"
64 #include "tree-into-ssa.h"
68 #include "statistics.h"
70 #include "fixed-value.h"
71 #include "insn-config.h"
82 #include "tree-iterator.h"
83 #include "alloc-pool.h"
85 #include "tree-pass.h"
86 #include "langhooks.h"
88 #include "tree-ssa-sccvn.h"
89 #include "tree-scalar-evolution.h"
94 #include "plugin-api.h"
97 #include "symbol-summary.h"
99 #include "tree-ssa-propagate.h"
100 #include "ipa-utils.h"
104 1. Avail sets can be shared by making an avail_find_leader that
105 walks up the dominator tree and looks in those avail sets.
106 This might affect code optimality, it's unclear right now.
107 2. Strength reduction can be performed by anticipating expressions
108 we can repair later on.
109 3. We can do back-substitution or smarter value numbering to catch
110 commutative expressions split up over multiple statements.
113 /* For ease of terminology, "expression node" in the below refers to
114 every expression node but GIMPLE_ASSIGN, because GIMPLE_ASSIGNs
115 represent the actual statement containing the expressions we care about,
116 and we cache the value number by putting it in the expression. */
120 First we walk the statements to generate the AVAIL sets, the
121 EXP_GEN sets, and the tmp_gen sets. EXP_GEN sets represent the
122 generation of values/expressions by a given block. We use them
123 when computing the ANTIC sets. The AVAIL sets consist of
124 SSA_NAME's that represent values, so we know what values are
125 available in what blocks. AVAIL is a forward dataflow problem. In
126 SSA, values are never killed, so we don't need a kill set, or a
127 fixpoint iteration, in order to calculate the AVAIL sets. In
128 traditional parlance, AVAIL sets tell us the downsafety of the
131 Next, we generate the ANTIC sets. These sets represent the
132 anticipatable expressions. ANTIC is a backwards dataflow
133 problem. An expression is anticipatable in a given block if it could
134 be generated in that block. This means that if we had to perform
135 an insertion in that block, of the value of that expression, we
136 could. Calculating the ANTIC sets requires phi translation of
137 expressions, because the flow goes backwards through phis. We must
138 iterate to a fixpoint of the ANTIC sets, because we have a kill
139 set. Even in SSA form, values are not live over the entire
140 function, only from their definition point onwards. So we have to
141 remove values from the ANTIC set once we go past the definition
142 point of the leaders that make them up.
143 compute_antic/compute_antic_aux performs this computation.
145 Third, we perform insertions to make partially redundant
146 expressions fully redundant.
148 An expression is partially redundant (excluding partial
151 1. It is AVAIL in some, but not all, of the predecessors of a
153 2. It is ANTIC in all the predecessors.
155 In order to make it fully redundant, we insert the expression into
156 the predecessors where it is not available, but is ANTIC.
158 For the partial anticipation case, we only perform insertion if it
159 is partially anticipated in some block, and fully available in all
162 insert/insert_aux/do_regular_insertion/do_partial_partial_insertion
163 performs these steps.
165 Fourth, we eliminate fully redundant expressions.
166 This is a simple statement walk that replaces redundant
167 calculations with the now available values. */
169 /* Representations of value numbers:
171 Value numbers are represented by a representative SSA_NAME. We
172 will create fake SSA_NAME's in situations where we need a
173 representative but do not have one (because it is a complex
174 expression). In order to facilitate storing the value numbers in
175 bitmaps, and keep the number of wasted SSA_NAME's down, we also
176 associate a value_id with each value number, and create full blown
177 ssa_name's only where we actually need them (IE in operands of
178 existing expressions).
180 Theoretically you could replace all the value_id's with
181 SSA_NAME_VERSION, but this would allocate a large number of
182 SSA_NAME's (which are each > 30 bytes) just to get a 4 byte number.
183 It would also require an additional indirection at each point we
186 /* Representation of expressions on value numbers:
188 Expressions consisting of value numbers are represented the same
189 way as our VN internally represents them, with an additional
190 "pre_expr" wrapping around them in order to facilitate storing all
191 of the expressions in the same sets. */
193 /* Representation of sets:
195 The dataflow sets do not need to be sorted in any particular order
196 for the majority of their lifetime, are simply represented as two
197 bitmaps, one that keeps track of values present in the set, and one
198 that keeps track of expressions present in the set.
200 When we need them in topological order, we produce it on demand by
201 transforming the bitmap into an array and sorting it into topo
204 /* Type of expression, used to know which member of the PRE_EXPR union
215 typedef union pre_expr_union_d
220 vn_reference_t reference
;
223 typedef struct pre_expr_d
: typed_noop_remove
<pre_expr_d
>
225 enum pre_expr_kind kind
;
229 /* hash_table support. */
230 typedef pre_expr_d value_type
;
231 typedef pre_expr_d compare_type
;
232 static inline hashval_t
hash (const pre_expr_d
*);
233 static inline int equal (const pre_expr_d
*, const pre_expr_d
*);
236 #define PRE_EXPR_NAME(e) (e)->u.name
237 #define PRE_EXPR_NARY(e) (e)->u.nary
238 #define PRE_EXPR_REFERENCE(e) (e)->u.reference
239 #define PRE_EXPR_CONSTANT(e) (e)->u.constant
241 /* Compare E1 and E1 for equality. */
244 pre_expr_d::equal (const value_type
*e1
, const compare_type
*e2
)
246 if (e1
->kind
!= e2
->kind
)
252 return vn_constant_eq_with_type (PRE_EXPR_CONSTANT (e1
),
253 PRE_EXPR_CONSTANT (e2
));
255 return PRE_EXPR_NAME (e1
) == PRE_EXPR_NAME (e2
);
257 return vn_nary_op_eq (PRE_EXPR_NARY (e1
), PRE_EXPR_NARY (e2
));
259 return vn_reference_eq (PRE_EXPR_REFERENCE (e1
),
260 PRE_EXPR_REFERENCE (e2
));
269 pre_expr_d::hash (const value_type
*e
)
274 return vn_hash_constant_with_type (PRE_EXPR_CONSTANT (e
));
276 return SSA_NAME_VERSION (PRE_EXPR_NAME (e
));
278 return PRE_EXPR_NARY (e
)->hashcode
;
280 return PRE_EXPR_REFERENCE (e
)->hashcode
;
286 /* Next global expression id number. */
287 static unsigned int next_expression_id
;
289 /* Mapping from expression to id number we can use in bitmap sets. */
290 static vec
<pre_expr
> expressions
;
291 static hash_table
<pre_expr_d
> *expression_to_id
;
292 static vec
<unsigned> name_to_id
;
294 /* Allocate an expression id for EXPR. */
296 static inline unsigned int
297 alloc_expression_id (pre_expr expr
)
299 struct pre_expr_d
**slot
;
300 /* Make sure we won't overflow. */
301 gcc_assert (next_expression_id
+ 1 > next_expression_id
);
302 expr
->id
= next_expression_id
++;
303 expressions
.safe_push (expr
);
304 if (expr
->kind
== NAME
)
306 unsigned version
= SSA_NAME_VERSION (PRE_EXPR_NAME (expr
));
307 /* vec::safe_grow_cleared allocates no headroom. Avoid frequent
308 re-allocations by using vec::reserve upfront. */
309 unsigned old_len
= name_to_id
.length ();
310 name_to_id
.reserve (num_ssa_names
- old_len
);
311 name_to_id
.quick_grow_cleared (num_ssa_names
);
312 gcc_assert (name_to_id
[version
] == 0);
313 name_to_id
[version
] = expr
->id
;
317 slot
= expression_to_id
->find_slot (expr
, INSERT
);
321 return next_expression_id
- 1;
324 /* Return the expression id for tree EXPR. */
326 static inline unsigned int
327 get_expression_id (const pre_expr expr
)
332 static inline unsigned int
333 lookup_expression_id (const pre_expr expr
)
335 struct pre_expr_d
**slot
;
337 if (expr
->kind
== NAME
)
339 unsigned version
= SSA_NAME_VERSION (PRE_EXPR_NAME (expr
));
340 if (name_to_id
.length () <= version
)
342 return name_to_id
[version
];
346 slot
= expression_to_id
->find_slot (expr
, NO_INSERT
);
349 return ((pre_expr
)*slot
)->id
;
353 /* Return the existing expression id for EXPR, or create one if one
354 does not exist yet. */
356 static inline unsigned int
357 get_or_alloc_expression_id (pre_expr expr
)
359 unsigned int id
= lookup_expression_id (expr
);
361 return alloc_expression_id (expr
);
362 return expr
->id
= id
;
365 /* Return the expression that has expression id ID */
367 static inline pre_expr
368 expression_for_id (unsigned int id
)
370 return expressions
[id
];
373 /* Free the expression id field in all of our expressions,
374 and then destroy the expressions array. */
377 clear_expression_ids (void)
379 expressions
.release ();
382 static alloc_pool pre_expr_pool
;
384 /* Given an SSA_NAME NAME, get or create a pre_expr to represent it. */
387 get_or_alloc_expr_for_name (tree name
)
389 struct pre_expr_d expr
;
391 unsigned int result_id
;
395 PRE_EXPR_NAME (&expr
) = name
;
396 result_id
= lookup_expression_id (&expr
);
398 return expression_for_id (result_id
);
400 result
= (pre_expr
) pool_alloc (pre_expr_pool
);
402 PRE_EXPR_NAME (result
) = name
;
403 alloc_expression_id (result
);
407 /* An unordered bitmap set. One bitmap tracks values, the other,
409 typedef struct bitmap_set
411 bitmap_head expressions
;
415 #define FOR_EACH_EXPR_ID_IN_SET(set, id, bi) \
416 EXECUTE_IF_SET_IN_BITMAP (&(set)->expressions, 0, (id), (bi))
418 #define FOR_EACH_VALUE_ID_IN_SET(set, id, bi) \
419 EXECUTE_IF_SET_IN_BITMAP (&(set)->values, 0, (id), (bi))
421 /* Mapping from value id to expressions with that value_id. */
422 static vec
<bitmap
> value_expressions
;
424 /* Sets that we need to keep track of. */
425 typedef struct bb_bitmap_sets
427 /* The EXP_GEN set, which represents expressions/values generated in
429 bitmap_set_t exp_gen
;
431 /* The PHI_GEN set, which represents PHI results generated in a
433 bitmap_set_t phi_gen
;
435 /* The TMP_GEN set, which represents results/temporaries generated
436 in a basic block. IE the LHS of an expression. */
437 bitmap_set_t tmp_gen
;
439 /* The AVAIL_OUT set, which represents which values are available in
440 a given basic block. */
441 bitmap_set_t avail_out
;
443 /* The ANTIC_IN set, which represents which values are anticipatable
444 in a given basic block. */
445 bitmap_set_t antic_in
;
447 /* The PA_IN set, which represents which values are
448 partially anticipatable in a given basic block. */
451 /* The NEW_SETS set, which is used during insertion to augment the
452 AVAIL_OUT set of blocks with the new insertions performed during
453 the current iteration. */
454 bitmap_set_t new_sets
;
456 /* A cache for value_dies_in_block_x. */
459 /* The live virtual operand on successor edges. */
462 /* True if we have visited this block during ANTIC calculation. */
463 unsigned int visited
: 1;
465 /* True when the block contains a call that might not return. */
466 unsigned int contains_may_not_return_call
: 1;
469 #define EXP_GEN(BB) ((bb_value_sets_t) ((BB)->aux))->exp_gen
470 #define PHI_GEN(BB) ((bb_value_sets_t) ((BB)->aux))->phi_gen
471 #define TMP_GEN(BB) ((bb_value_sets_t) ((BB)->aux))->tmp_gen
472 #define AVAIL_OUT(BB) ((bb_value_sets_t) ((BB)->aux))->avail_out
473 #define ANTIC_IN(BB) ((bb_value_sets_t) ((BB)->aux))->antic_in
474 #define PA_IN(BB) ((bb_value_sets_t) ((BB)->aux))->pa_in
475 #define NEW_SETS(BB) ((bb_value_sets_t) ((BB)->aux))->new_sets
476 #define EXPR_DIES(BB) ((bb_value_sets_t) ((BB)->aux))->expr_dies
477 #define BB_VISITED(BB) ((bb_value_sets_t) ((BB)->aux))->visited
478 #define BB_MAY_NOTRETURN(BB) ((bb_value_sets_t) ((BB)->aux))->contains_may_not_return_call
479 #define BB_LIVE_VOP_ON_EXIT(BB) ((bb_value_sets_t) ((BB)->aux))->vop_on_exit
482 /* Basic block list in postorder. */
483 static int *postorder
;
484 static int postorder_num
;
486 /* This structure is used to keep track of statistics on what
487 optimization PRE was able to perform. */
490 /* The number of RHS computations eliminated by PRE. */
493 /* The number of new expressions/temporaries generated by PRE. */
496 /* The number of inserts found due to partial anticipation */
499 /* The number of new PHI nodes added by PRE. */
503 static bool do_partial_partial
;
504 static pre_expr
bitmap_find_leader (bitmap_set_t
, unsigned int);
505 static void bitmap_value_insert_into_set (bitmap_set_t
, pre_expr
);
506 static void bitmap_value_replace_in_set (bitmap_set_t
, pre_expr
);
507 static void bitmap_set_copy (bitmap_set_t
, bitmap_set_t
);
508 static bool bitmap_set_contains_value (bitmap_set_t
, unsigned int);
509 static void bitmap_insert_into_set (bitmap_set_t
, pre_expr
);
510 static void bitmap_insert_into_set_1 (bitmap_set_t
, pre_expr
,
512 static bitmap_set_t
bitmap_set_new (void);
513 static tree
create_expression_by_pieces (basic_block
, pre_expr
, gimple_seq
*,
515 static tree
find_or_generate_expression (basic_block
, tree
, gimple_seq
*);
516 static unsigned int get_expr_value_id (pre_expr
);
518 /* We can add and remove elements and entries to and from sets
519 and hash tables, so we use alloc pools for them. */
521 static alloc_pool bitmap_set_pool
;
522 static bitmap_obstack grand_bitmap_obstack
;
524 /* Set of blocks with statements that have had their EH properties changed. */
525 static bitmap need_eh_cleanup
;
527 /* Set of blocks with statements that have had their AB properties changed. */
528 static bitmap need_ab_cleanup
;
530 /* A three tuple {e, pred, v} used to cache phi translations in the
531 phi_translate_table. */
533 typedef struct expr_pred_trans_d
: typed_free_remove
<expr_pred_trans_d
>
535 /* The expression. */
538 /* The predecessor block along which we translated the expression. */
541 /* The value that resulted from the translation. */
544 /* The hashcode for the expression, pred pair. This is cached for
548 /* hash_table support. */
549 typedef expr_pred_trans_d value_type
;
550 typedef expr_pred_trans_d compare_type
;
551 static inline hashval_t
hash (const value_type
*);
552 static inline int equal (const value_type
*, const compare_type
*);
553 } *expr_pred_trans_t
;
554 typedef const struct expr_pred_trans_d
*const_expr_pred_trans_t
;
557 expr_pred_trans_d::hash (const expr_pred_trans_d
*e
)
563 expr_pred_trans_d::equal (const value_type
*ve1
,
564 const compare_type
*ve2
)
566 basic_block b1
= ve1
->pred
;
567 basic_block b2
= ve2
->pred
;
569 /* If they are not translations for the same basic block, they can't
573 return pre_expr_d::equal (ve1
->e
, ve2
->e
);
576 /* The phi_translate_table caches phi translations for a given
577 expression and predecessor. */
578 static hash_table
<expr_pred_trans_d
> *phi_translate_table
;
580 /* Add the tuple mapping from {expression E, basic block PRED} to
581 the phi translation table and return whether it pre-existed. */
584 phi_trans_add (expr_pred_trans_t
*entry
, pre_expr e
, basic_block pred
)
586 expr_pred_trans_t
*slot
;
587 expr_pred_trans_d tem
;
588 hashval_t hash
= iterative_hash_hashval_t (pre_expr_d::hash (e
),
593 slot
= phi_translate_table
->find_slot_with_hash (&tem
, hash
, INSERT
);
600 *entry
= *slot
= XNEW (struct expr_pred_trans_d
);
602 (*entry
)->pred
= pred
;
603 (*entry
)->hashcode
= hash
;
608 /* Add expression E to the expression set of value id V. */
611 add_to_value (unsigned int v
, pre_expr e
)
615 gcc_checking_assert (get_expr_value_id (e
) == v
);
617 if (v
>= value_expressions
.length ())
619 value_expressions
.safe_grow_cleared (v
+ 1);
622 set
= value_expressions
[v
];
625 set
= BITMAP_ALLOC (&grand_bitmap_obstack
);
626 value_expressions
[v
] = set
;
629 bitmap_set_bit (set
, get_or_alloc_expression_id (e
));
632 /* Create a new bitmap set and return it. */
635 bitmap_set_new (void)
637 bitmap_set_t ret
= (bitmap_set_t
) pool_alloc (bitmap_set_pool
);
638 bitmap_initialize (&ret
->expressions
, &grand_bitmap_obstack
);
639 bitmap_initialize (&ret
->values
, &grand_bitmap_obstack
);
643 /* Return the value id for a PRE expression EXPR. */
646 get_expr_value_id (pre_expr expr
)
652 id
= get_constant_value_id (PRE_EXPR_CONSTANT (expr
));
655 id
= VN_INFO (PRE_EXPR_NAME (expr
))->value_id
;
658 id
= PRE_EXPR_NARY (expr
)->value_id
;
661 id
= PRE_EXPR_REFERENCE (expr
)->value_id
;
666 /* ??? We cannot assert that expr has a value-id (it can be 0), because
667 we assign value-ids only to expressions that have a result
668 in set_hashtable_value_ids. */
672 /* Return a SCCVN valnum (SSA name or constant) for the PRE value-id VAL. */
675 sccvn_valnum_from_value_id (unsigned int val
)
679 bitmap exprset
= value_expressions
[val
];
680 EXECUTE_IF_SET_IN_BITMAP (exprset
, 0, i
, bi
)
682 pre_expr vexpr
= expression_for_id (i
);
683 if (vexpr
->kind
== NAME
)
684 return VN_INFO (PRE_EXPR_NAME (vexpr
))->valnum
;
685 else if (vexpr
->kind
== CONSTANT
)
686 return PRE_EXPR_CONSTANT (vexpr
);
691 /* Remove an expression EXPR from a bitmapped set. */
694 bitmap_remove_from_set (bitmap_set_t set
, pre_expr expr
)
696 unsigned int val
= get_expr_value_id (expr
);
697 if (!value_id_constant_p (val
))
699 bitmap_clear_bit (&set
->values
, val
);
700 bitmap_clear_bit (&set
->expressions
, get_expression_id (expr
));
705 bitmap_insert_into_set_1 (bitmap_set_t set
, pre_expr expr
,
706 unsigned int val
, bool allow_constants
)
708 if (allow_constants
|| !value_id_constant_p (val
))
710 /* We specifically expect this and only this function to be able to
711 insert constants into a set. */
712 bitmap_set_bit (&set
->values
, val
);
713 bitmap_set_bit (&set
->expressions
, get_or_alloc_expression_id (expr
));
717 /* Insert an expression EXPR into a bitmapped set. */
720 bitmap_insert_into_set (bitmap_set_t set
, pre_expr expr
)
722 bitmap_insert_into_set_1 (set
, expr
, get_expr_value_id (expr
), false);
725 /* Copy a bitmapped set ORIG, into bitmapped set DEST. */
728 bitmap_set_copy (bitmap_set_t dest
, bitmap_set_t orig
)
730 bitmap_copy (&dest
->expressions
, &orig
->expressions
);
731 bitmap_copy (&dest
->values
, &orig
->values
);
735 /* Free memory used up by SET. */
737 bitmap_set_free (bitmap_set_t set
)
739 bitmap_clear (&set
->expressions
);
740 bitmap_clear (&set
->values
);
744 /* Generate an topological-ordered array of bitmap set SET. */
747 sorted_array_from_bitmap_set (bitmap_set_t set
)
750 bitmap_iterator bi
, bj
;
751 vec
<pre_expr
> result
;
753 /* Pre-allocate enough space for the array. */
754 result
.create (bitmap_count_bits (&set
->expressions
));
756 FOR_EACH_VALUE_ID_IN_SET (set
, i
, bi
)
758 /* The number of expressions having a given value is usually
759 relatively small. Thus, rather than making a vector of all
760 the expressions and sorting it by value-id, we walk the values
761 and check in the reverse mapping that tells us what expressions
762 have a given value, to filter those in our set. As a result,
763 the expressions are inserted in value-id order, which means
766 If this is somehow a significant lose for some cases, we can
767 choose which set to walk based on the set size. */
768 bitmap exprset
= value_expressions
[i
];
769 EXECUTE_IF_SET_IN_BITMAP (exprset
, 0, j
, bj
)
771 if (bitmap_bit_p (&set
->expressions
, j
))
772 result
.quick_push (expression_for_id (j
));
779 /* Perform bitmapped set operation DEST &= ORIG. */
782 bitmap_set_and (bitmap_set_t dest
, bitmap_set_t orig
)
790 bitmap_initialize (&temp
, &grand_bitmap_obstack
);
792 bitmap_and_into (&dest
->values
, &orig
->values
);
793 bitmap_copy (&temp
, &dest
->expressions
);
794 EXECUTE_IF_SET_IN_BITMAP (&temp
, 0, i
, bi
)
796 pre_expr expr
= expression_for_id (i
);
797 unsigned int value_id
= get_expr_value_id (expr
);
798 if (!bitmap_bit_p (&dest
->values
, value_id
))
799 bitmap_clear_bit (&dest
->expressions
, i
);
801 bitmap_clear (&temp
);
805 /* Subtract all values and expressions contained in ORIG from DEST. */
808 bitmap_set_subtract (bitmap_set_t dest
, bitmap_set_t orig
)
810 bitmap_set_t result
= bitmap_set_new ();
814 bitmap_and_compl (&result
->expressions
, &dest
->expressions
,
817 FOR_EACH_EXPR_ID_IN_SET (result
, i
, bi
)
819 pre_expr expr
= expression_for_id (i
);
820 unsigned int value_id
= get_expr_value_id (expr
);
821 bitmap_set_bit (&result
->values
, value_id
);
827 /* Subtract all the values in bitmap set B from bitmap set A. */
830 bitmap_set_subtract_values (bitmap_set_t a
, bitmap_set_t b
)
836 bitmap_initialize (&temp
, &grand_bitmap_obstack
);
838 bitmap_copy (&temp
, &a
->expressions
);
839 EXECUTE_IF_SET_IN_BITMAP (&temp
, 0, i
, bi
)
841 pre_expr expr
= expression_for_id (i
);
842 if (bitmap_set_contains_value (b
, get_expr_value_id (expr
)))
843 bitmap_remove_from_set (a
, expr
);
845 bitmap_clear (&temp
);
849 /* Return true if bitmapped set SET contains the value VALUE_ID. */
852 bitmap_set_contains_value (bitmap_set_t set
, unsigned int value_id
)
854 if (value_id_constant_p (value_id
))
857 if (!set
|| bitmap_empty_p (&set
->expressions
))
860 return bitmap_bit_p (&set
->values
, value_id
);
864 bitmap_set_contains_expr (bitmap_set_t set
, const pre_expr expr
)
866 return bitmap_bit_p (&set
->expressions
, get_expression_id (expr
));
869 /* Replace an instance of value LOOKFOR with expression EXPR in SET. */
872 bitmap_set_replace_value (bitmap_set_t set
, unsigned int lookfor
,
879 if (value_id_constant_p (lookfor
))
882 if (!bitmap_set_contains_value (set
, lookfor
))
885 /* The number of expressions having a given value is usually
886 significantly less than the total number of expressions in SET.
887 Thus, rather than check, for each expression in SET, whether it
888 has the value LOOKFOR, we walk the reverse mapping that tells us
889 what expressions have a given value, and see if any of those
890 expressions are in our set. For large testcases, this is about
891 5-10x faster than walking the bitmap. If this is somehow a
892 significant lose for some cases, we can choose which set to walk
893 based on the set size. */
894 exprset
= value_expressions
[lookfor
];
895 EXECUTE_IF_SET_IN_BITMAP (exprset
, 0, i
, bi
)
897 if (bitmap_clear_bit (&set
->expressions
, i
))
899 bitmap_set_bit (&set
->expressions
, get_expression_id (expr
));
907 /* Return true if two bitmap sets are equal. */
910 bitmap_set_equal (bitmap_set_t a
, bitmap_set_t b
)
912 return bitmap_equal_p (&a
->values
, &b
->values
);
915 /* Replace an instance of EXPR's VALUE with EXPR in SET if it exists,
916 and add it otherwise. */
919 bitmap_value_replace_in_set (bitmap_set_t set
, pre_expr expr
)
921 unsigned int val
= get_expr_value_id (expr
);
923 if (bitmap_set_contains_value (set
, val
))
924 bitmap_set_replace_value (set
, val
, expr
);
926 bitmap_insert_into_set (set
, expr
);
929 /* Insert EXPR into SET if EXPR's value is not already present in
933 bitmap_value_insert_into_set (bitmap_set_t set
, pre_expr expr
)
935 unsigned int val
= get_expr_value_id (expr
);
937 gcc_checking_assert (expr
->id
== get_or_alloc_expression_id (expr
));
939 /* Constant values are always considered to be part of the set. */
940 if (value_id_constant_p (val
))
943 /* If the value membership changed, add the expression. */
944 if (bitmap_set_bit (&set
->values
, val
))
945 bitmap_set_bit (&set
->expressions
, expr
->id
);
948 /* Print out EXPR to outfile. */
951 print_pre_expr (FILE *outfile
, const pre_expr expr
)
956 print_generic_expr (outfile
, PRE_EXPR_CONSTANT (expr
), 0);
959 print_generic_expr (outfile
, PRE_EXPR_NAME (expr
), 0);
964 vn_nary_op_t nary
= PRE_EXPR_NARY (expr
);
965 fprintf (outfile
, "{%s,", get_tree_code_name (nary
->opcode
));
966 for (i
= 0; i
< nary
->length
; i
++)
968 print_generic_expr (outfile
, nary
->op
[i
], 0);
969 if (i
!= (unsigned) nary
->length
- 1)
970 fprintf (outfile
, ",");
972 fprintf (outfile
, "}");
978 vn_reference_op_t vro
;
980 vn_reference_t ref
= PRE_EXPR_REFERENCE (expr
);
981 fprintf (outfile
, "{");
983 ref
->operands
.iterate (i
, &vro
);
986 bool closebrace
= false;
987 if (vro
->opcode
!= SSA_NAME
988 && TREE_CODE_CLASS (vro
->opcode
) != tcc_declaration
)
990 fprintf (outfile
, "%s", get_tree_code_name (vro
->opcode
));
993 fprintf (outfile
, "<");
999 print_generic_expr (outfile
, vro
->op0
, 0);
1002 fprintf (outfile
, ",");
1003 print_generic_expr (outfile
, vro
->op1
, 0);
1007 fprintf (outfile
, ",");
1008 print_generic_expr (outfile
, vro
->op2
, 0);
1012 fprintf (outfile
, ">");
1013 if (i
!= ref
->operands
.length () - 1)
1014 fprintf (outfile
, ",");
1016 fprintf (outfile
, "}");
1019 fprintf (outfile
, "@");
1020 print_generic_expr (outfile
, ref
->vuse
, 0);
1026 void debug_pre_expr (pre_expr
);
1028 /* Like print_pre_expr but always prints to stderr. */
1030 debug_pre_expr (pre_expr e
)
1032 print_pre_expr (stderr
, e
);
1033 fprintf (stderr
, "\n");
1036 /* Print out SET to OUTFILE. */
1039 print_bitmap_set (FILE *outfile
, bitmap_set_t set
,
1040 const char *setname
, int blockindex
)
1042 fprintf (outfile
, "%s[%d] := { ", setname
, blockindex
);
1049 FOR_EACH_EXPR_ID_IN_SET (set
, i
, bi
)
1051 const pre_expr expr
= expression_for_id (i
);
1054 fprintf (outfile
, ", ");
1056 print_pre_expr (outfile
, expr
);
1058 fprintf (outfile
, " (%04d)", get_expr_value_id (expr
));
1061 fprintf (outfile
, " }\n");
1064 void debug_bitmap_set (bitmap_set_t
);
1067 debug_bitmap_set (bitmap_set_t set
)
1069 print_bitmap_set (stderr
, set
, "debug", 0);
1072 void debug_bitmap_sets_for (basic_block
);
1075 debug_bitmap_sets_for (basic_block bb
)
1077 print_bitmap_set (stderr
, AVAIL_OUT (bb
), "avail_out", bb
->index
);
1078 print_bitmap_set (stderr
, EXP_GEN (bb
), "exp_gen", bb
->index
);
1079 print_bitmap_set (stderr
, PHI_GEN (bb
), "phi_gen", bb
->index
);
1080 print_bitmap_set (stderr
, TMP_GEN (bb
), "tmp_gen", bb
->index
);
1081 print_bitmap_set (stderr
, ANTIC_IN (bb
), "antic_in", bb
->index
);
1082 if (do_partial_partial
)
1083 print_bitmap_set (stderr
, PA_IN (bb
), "pa_in", bb
->index
);
1084 print_bitmap_set (stderr
, NEW_SETS (bb
), "new_sets", bb
->index
);
1087 /* Print out the expressions that have VAL to OUTFILE. */
1090 print_value_expressions (FILE *outfile
, unsigned int val
)
1092 bitmap set
= value_expressions
[val
];
1097 sprintf (s
, "%04d", val
);
1098 x
.expressions
= *set
;
1099 print_bitmap_set (outfile
, &x
, s
, 0);
1105 debug_value_expressions (unsigned int val
)
1107 print_value_expressions (stderr
, val
);
1110 /* Given a CONSTANT, allocate a new CONSTANT type PRE_EXPR to
1114 get_or_alloc_expr_for_constant (tree constant
)
1116 unsigned int result_id
;
1117 unsigned int value_id
;
1118 struct pre_expr_d expr
;
1121 expr
.kind
= CONSTANT
;
1122 PRE_EXPR_CONSTANT (&expr
) = constant
;
1123 result_id
= lookup_expression_id (&expr
);
1125 return expression_for_id (result_id
);
1127 newexpr
= (pre_expr
) pool_alloc (pre_expr_pool
);
1128 newexpr
->kind
= CONSTANT
;
1129 PRE_EXPR_CONSTANT (newexpr
) = constant
;
1130 alloc_expression_id (newexpr
);
1131 value_id
= get_or_alloc_constant_value_id (constant
);
1132 add_to_value (value_id
, newexpr
);
1136 /* Given a value id V, find the actual tree representing the constant
1137 value if there is one, and return it. Return NULL if we can't find
1141 get_constant_for_value_id (unsigned int v
)
1143 if (value_id_constant_p (v
))
1147 bitmap exprset
= value_expressions
[v
];
1149 EXECUTE_IF_SET_IN_BITMAP (exprset
, 0, i
, bi
)
1151 pre_expr expr
= expression_for_id (i
);
1152 if (expr
->kind
== CONSTANT
)
1153 return PRE_EXPR_CONSTANT (expr
);
1159 /* Get or allocate a pre_expr for a piece of GIMPLE, and return it.
1160 Currently only supports constants and SSA_NAMES. */
1162 get_or_alloc_expr_for (tree t
)
1164 if (TREE_CODE (t
) == SSA_NAME
)
1165 return get_or_alloc_expr_for_name (t
);
1166 else if (is_gimple_min_invariant (t
))
1167 return get_or_alloc_expr_for_constant (t
);
1170 /* More complex expressions can result from SCCVN expression
1171 simplification that inserts values for them. As they all
1172 do not have VOPs the get handled by the nary ops struct. */
1173 vn_nary_op_t result
;
1174 unsigned int result_id
;
1175 vn_nary_op_lookup (t
, &result
);
1178 pre_expr e
= (pre_expr
) pool_alloc (pre_expr_pool
);
1180 PRE_EXPR_NARY (e
) = result
;
1181 result_id
= lookup_expression_id (e
);
1184 pool_free (pre_expr_pool
, e
);
1185 e
= expression_for_id (result_id
);
1188 alloc_expression_id (e
);
1195 /* Return the folded version of T if T, when folded, is a gimple
1196 min_invariant. Otherwise, return T. */
1199 fully_constant_expression (pre_expr e
)
1207 vn_nary_op_t nary
= PRE_EXPR_NARY (e
);
1208 switch (TREE_CODE_CLASS (nary
->opcode
))
1211 case tcc_comparison
:
1213 /* We have to go from trees to pre exprs to value ids to
1215 tree naryop0
= nary
->op
[0];
1216 tree naryop1
= nary
->op
[1];
1218 if (!is_gimple_min_invariant (naryop0
))
1220 pre_expr rep0
= get_or_alloc_expr_for (naryop0
);
1221 unsigned int vrep0
= get_expr_value_id (rep0
);
1222 tree const0
= get_constant_for_value_id (vrep0
);
1224 naryop0
= fold_convert (TREE_TYPE (naryop0
), const0
);
1226 if (!is_gimple_min_invariant (naryop1
))
1228 pre_expr rep1
= get_or_alloc_expr_for (naryop1
);
1229 unsigned int vrep1
= get_expr_value_id (rep1
);
1230 tree const1
= get_constant_for_value_id (vrep1
);
1232 naryop1
= fold_convert (TREE_TYPE (naryop1
), const1
);
1234 result
= fold_binary (nary
->opcode
, nary
->type
,
1236 if (result
&& is_gimple_min_invariant (result
))
1237 return get_or_alloc_expr_for_constant (result
);
1238 /* We might have simplified the expression to a
1239 SSA_NAME for example from x_1 * 1. But we cannot
1240 insert a PHI for x_1 unconditionally as x_1 might
1241 not be available readily. */
1245 if (nary
->opcode
!= REALPART_EXPR
1246 && nary
->opcode
!= IMAGPART_EXPR
1247 && nary
->opcode
!= VIEW_CONVERT_EXPR
)
1252 /* We have to go from trees to pre exprs to value ids to
1254 tree naryop0
= nary
->op
[0];
1255 tree const0
, result
;
1256 if (is_gimple_min_invariant (naryop0
))
1260 pre_expr rep0
= get_or_alloc_expr_for (naryop0
);
1261 unsigned int vrep0
= get_expr_value_id (rep0
);
1262 const0
= get_constant_for_value_id (vrep0
);
1267 tree type1
= TREE_TYPE (nary
->op
[0]);
1268 const0
= fold_convert (type1
, const0
);
1269 result
= fold_unary (nary
->opcode
, nary
->type
, const0
);
1271 if (result
&& is_gimple_min_invariant (result
))
1272 return get_or_alloc_expr_for_constant (result
);
1281 vn_reference_t ref
= PRE_EXPR_REFERENCE (e
);
1283 if ((folded
= fully_constant_vn_reference_p (ref
)))
1284 return get_or_alloc_expr_for_constant (folded
);
1293 /* Translate the VUSE backwards through phi nodes in PHIBLOCK, so that
1294 it has the value it would have in BLOCK. Set *SAME_VALID to true
1295 in case the new vuse doesn't change the value id of the OPERANDS. */
1298 translate_vuse_through_block (vec
<vn_reference_op_s
> operands
,
1299 alias_set_type set
, tree type
, tree vuse
,
1300 basic_block phiblock
,
1301 basic_block block
, bool *same_valid
)
1303 gimple phi
= SSA_NAME_DEF_STMT (vuse
);
1310 if (gimple_bb (phi
) != phiblock
)
1313 use_oracle
= ao_ref_init_from_vn_reference (&ref
, set
, type
, operands
);
1315 /* Use the alias-oracle to find either the PHI node in this block,
1316 the first VUSE used in this block that is equivalent to vuse or
1317 the first VUSE which definition in this block kills the value. */
1318 if (gimple_code (phi
) == GIMPLE_PHI
)
1319 e
= find_edge (block
, phiblock
);
1320 else if (use_oracle
)
1321 while (!stmt_may_clobber_ref_p_1 (phi
, &ref
))
1323 vuse
= gimple_vuse (phi
);
1324 phi
= SSA_NAME_DEF_STMT (vuse
);
1325 if (gimple_bb (phi
) != phiblock
)
1327 if (gimple_code (phi
) == GIMPLE_PHI
)
1329 e
= find_edge (block
, phiblock
);
1340 bitmap visited
= NULL
;
1342 /* Try to find a vuse that dominates this phi node by skipping
1343 non-clobbering statements. */
1344 vuse
= get_continuation_for_phi (phi
, &ref
, &cnt
, &visited
, false,
1347 BITMAP_FREE (visited
);
1353 /* If we didn't find any, the value ID can't stay the same,
1354 but return the translated vuse. */
1355 *same_valid
= false;
1356 vuse
= PHI_ARG_DEF (phi
, e
->dest_idx
);
1358 /* ??? We would like to return vuse here as this is the canonical
1359 upmost vdef that this reference is associated with. But during
1360 insertion of the references into the hash tables we only ever
1361 directly insert with their direct gimple_vuse, hence returning
1362 something else would make us not find the other expression. */
1363 return PHI_ARG_DEF (phi
, e
->dest_idx
);
1369 /* Like bitmap_find_leader, but checks for the value existing in SET1 *or*
1370 SET2. This is used to avoid making a set consisting of the union
1371 of PA_IN and ANTIC_IN during insert. */
1373 static inline pre_expr
1374 find_leader_in_sets (unsigned int val
, bitmap_set_t set1
, bitmap_set_t set2
)
1378 result
= bitmap_find_leader (set1
, val
);
1379 if (!result
&& set2
)
1380 result
= bitmap_find_leader (set2
, val
);
1384 /* Get the tree type for our PRE expression e. */
1387 get_expr_type (const pre_expr e
)
1392 return TREE_TYPE (PRE_EXPR_NAME (e
));
1394 return TREE_TYPE (PRE_EXPR_CONSTANT (e
));
1396 return PRE_EXPR_REFERENCE (e
)->type
;
1398 return PRE_EXPR_NARY (e
)->type
;
1403 /* Get a representative SSA_NAME for a given expression.
1404 Since all of our sub-expressions are treated as values, we require
1405 them to be SSA_NAME's for simplicity.
1406 Prior versions of GVNPRE used to use "value handles" here, so that
1407 an expression would be VH.11 + VH.10 instead of d_3 + e_6. In
1408 either case, the operands are really values (IE we do not expect
1409 them to be usable without finding leaders). */
1412 get_representative_for (const pre_expr e
)
1415 unsigned int value_id
= get_expr_value_id (e
);
1420 return PRE_EXPR_NAME (e
);
1422 return PRE_EXPR_CONSTANT (e
);
1426 /* Go through all of the expressions representing this value
1427 and pick out an SSA_NAME. */
1430 bitmap exprs
= value_expressions
[value_id
];
1431 EXECUTE_IF_SET_IN_BITMAP (exprs
, 0, i
, bi
)
1433 pre_expr rep
= expression_for_id (i
);
1434 if (rep
->kind
== NAME
)
1435 return PRE_EXPR_NAME (rep
);
1436 else if (rep
->kind
== CONSTANT
)
1437 return PRE_EXPR_CONSTANT (rep
);
1443 /* If we reached here we couldn't find an SSA_NAME. This can
1444 happen when we've discovered a value that has never appeared in
1445 the program as set to an SSA_NAME, as the result of phi translation.
1447 ??? We should be able to re-use this when we insert the statement
1449 name
= make_temp_ssa_name (get_expr_type (e
), gimple_build_nop (), "pretmp");
1450 VN_INFO_GET (name
)->value_id
= value_id
;
1451 VN_INFO (name
)->valnum
= name
;
1452 /* ??? For now mark this SSA name for release by SCCVN. */
1453 VN_INFO (name
)->needs_insertion
= true;
1454 add_to_value (value_id
, get_or_alloc_expr_for_name (name
));
1455 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1457 fprintf (dump_file
, "Created SSA_NAME representative ");
1458 print_generic_expr (dump_file
, name
, 0);
1459 fprintf (dump_file
, " for expression:");
1460 print_pre_expr (dump_file
, e
);
1461 fprintf (dump_file
, " (%04d)\n", value_id
);
1470 phi_translate (pre_expr expr
, bitmap_set_t set1
, bitmap_set_t set2
,
1471 basic_block pred
, basic_block phiblock
);
1473 /* Translate EXPR using phis in PHIBLOCK, so that it has the values of
1474 the phis in PRED. Return NULL if we can't find a leader for each part
1475 of the translated expression. */
1478 phi_translate_1 (pre_expr expr
, bitmap_set_t set1
, bitmap_set_t set2
,
1479 basic_block pred
, basic_block phiblock
)
1486 bool changed
= false;
1487 vn_nary_op_t nary
= PRE_EXPR_NARY (expr
);
1488 vn_nary_op_t newnary
= XALLOCAVAR (struct vn_nary_op_s
,
1489 sizeof_vn_nary_op (nary
->length
));
1490 memcpy (newnary
, nary
, sizeof_vn_nary_op (nary
->length
));
1492 for (i
= 0; i
< newnary
->length
; i
++)
1494 if (TREE_CODE (newnary
->op
[i
]) != SSA_NAME
)
1498 pre_expr leader
, result
;
1499 unsigned int op_val_id
= VN_INFO (newnary
->op
[i
])->value_id
;
1500 leader
= find_leader_in_sets (op_val_id
, set1
, set2
);
1501 result
= phi_translate (leader
, set1
, set2
, pred
, phiblock
);
1502 if (result
&& result
!= leader
)
1504 tree name
= get_representative_for (result
);
1507 newnary
->op
[i
] = name
;
1512 changed
|= newnary
->op
[i
] != nary
->op
[i
];
1518 unsigned int new_val_id
;
1520 tree result
= vn_nary_op_lookup_pieces (newnary
->length
,
1525 if (result
&& is_gimple_min_invariant (result
))
1526 return get_or_alloc_expr_for_constant (result
);
1528 expr
= (pre_expr
) pool_alloc (pre_expr_pool
);
1533 PRE_EXPR_NARY (expr
) = nary
;
1534 constant
= fully_constant_expression (expr
);
1535 if (constant
!= expr
)
1538 new_val_id
= nary
->value_id
;
1539 get_or_alloc_expression_id (expr
);
1543 new_val_id
= get_next_value_id ();
1544 value_expressions
.safe_grow_cleared (get_max_value_id () + 1);
1545 nary
= vn_nary_op_insert_pieces (newnary
->length
,
1549 result
, new_val_id
);
1550 PRE_EXPR_NARY (expr
) = nary
;
1551 constant
= fully_constant_expression (expr
);
1552 if (constant
!= expr
)
1554 get_or_alloc_expression_id (expr
);
1556 add_to_value (new_val_id
, expr
);
1564 vn_reference_t ref
= PRE_EXPR_REFERENCE (expr
);
1565 vec
<vn_reference_op_s
> operands
= ref
->operands
;
1566 tree vuse
= ref
->vuse
;
1567 tree newvuse
= vuse
;
1568 vec
<vn_reference_op_s
> newoperands
= vNULL
;
1569 bool changed
= false, same_valid
= true;
1571 vn_reference_op_t operand
;
1572 vn_reference_t newref
;
1574 for (i
= 0; operands
.iterate (i
, &operand
); i
++)
1579 tree type
= operand
->type
;
1580 vn_reference_op_s newop
= *operand
;
1581 op
[0] = operand
->op0
;
1582 op
[1] = operand
->op1
;
1583 op
[2] = operand
->op2
;
1584 for (n
= 0; n
< 3; ++n
)
1586 unsigned int op_val_id
;
1589 if (TREE_CODE (op
[n
]) != SSA_NAME
)
1591 /* We can't possibly insert these. */
1593 && !is_gimple_min_invariant (op
[n
]))
1597 op_val_id
= VN_INFO (op
[n
])->value_id
;
1598 leader
= find_leader_in_sets (op_val_id
, set1
, set2
);
1601 opresult
= phi_translate (leader
, set1
, set2
, pred
, phiblock
);
1604 if (opresult
!= leader
)
1606 tree name
= get_representative_for (opresult
);
1609 changed
|= name
!= op
[n
];
1615 newoperands
.release ();
1620 if (!newoperands
.exists ())
1621 newoperands
= operands
.copy ();
1622 /* We may have changed from an SSA_NAME to a constant */
1623 if (newop
.opcode
== SSA_NAME
&& TREE_CODE (op
[0]) != SSA_NAME
)
1624 newop
.opcode
= TREE_CODE (op
[0]);
1629 newoperands
[i
] = newop
;
1631 gcc_checking_assert (i
== operands
.length ());
1635 newvuse
= translate_vuse_through_block (newoperands
.exists ()
1636 ? newoperands
: operands
,
1637 ref
->set
, ref
->type
,
1638 vuse
, phiblock
, pred
,
1640 if (newvuse
== NULL_TREE
)
1642 newoperands
.release ();
1647 if (changed
|| newvuse
!= vuse
)
1649 unsigned int new_val_id
;
1652 tree result
= vn_reference_lookup_pieces (newvuse
, ref
->set
,
1654 newoperands
.exists ()
1655 ? newoperands
: operands
,
1658 newoperands
.release ();
1660 /* We can always insert constants, so if we have a partial
1661 redundant constant load of another type try to translate it
1662 to a constant of appropriate type. */
1663 if (result
&& is_gimple_min_invariant (result
))
1666 if (!useless_type_conversion_p (ref
->type
, TREE_TYPE (result
)))
1668 tem
= fold_unary (VIEW_CONVERT_EXPR
, ref
->type
, result
);
1669 if (tem
&& !is_gimple_min_invariant (tem
))
1673 return get_or_alloc_expr_for_constant (tem
);
1676 /* If we'd have to convert things we would need to validate
1677 if we can insert the translated expression. So fail
1678 here for now - we cannot insert an alias with a different
1679 type in the VN tables either, as that would assert. */
1681 && !useless_type_conversion_p (ref
->type
, TREE_TYPE (result
)))
1683 else if (!result
&& newref
1684 && !useless_type_conversion_p (ref
->type
, newref
->type
))
1686 newoperands
.release ();
1690 expr
= (pre_expr
) pool_alloc (pre_expr_pool
);
1691 expr
->kind
= REFERENCE
;
1696 PRE_EXPR_REFERENCE (expr
) = newref
;
1697 constant
= fully_constant_expression (expr
);
1698 if (constant
!= expr
)
1701 new_val_id
= newref
->value_id
;
1702 get_or_alloc_expression_id (expr
);
1706 if (changed
|| !same_valid
)
1708 new_val_id
= get_next_value_id ();
1709 value_expressions
.safe_grow_cleared
1710 (get_max_value_id () + 1);
1713 new_val_id
= ref
->value_id
;
1714 if (!newoperands
.exists ())
1715 newoperands
= operands
.copy ();
1716 newref
= vn_reference_insert_pieces (newvuse
, ref
->set
,
1719 result
, new_val_id
);
1720 newoperands
= vNULL
;
1721 PRE_EXPR_REFERENCE (expr
) = newref
;
1722 constant
= fully_constant_expression (expr
);
1723 if (constant
!= expr
)
1725 get_or_alloc_expression_id (expr
);
1727 add_to_value (new_val_id
, expr
);
1729 newoperands
.release ();
1736 tree name
= PRE_EXPR_NAME (expr
);
1737 gimple def_stmt
= SSA_NAME_DEF_STMT (name
);
1738 /* If the SSA name is defined by a PHI node in this block,
1740 if (gimple_code (def_stmt
) == GIMPLE_PHI
1741 && gimple_bb (def_stmt
) == phiblock
)
1743 edge e
= find_edge (pred
, gimple_bb (def_stmt
));
1744 tree def
= PHI_ARG_DEF (def_stmt
, e
->dest_idx
);
1746 /* Handle constant. */
1747 if (is_gimple_min_invariant (def
))
1748 return get_or_alloc_expr_for_constant (def
);
1750 return get_or_alloc_expr_for_name (def
);
1752 /* Otherwise return it unchanged - it will get removed if its
1753 value is not available in PREDs AVAIL_OUT set of expressions
1754 by the subtraction of TMP_GEN. */
1763 /* Wrapper around phi_translate_1 providing caching functionality. */
1766 phi_translate (pre_expr expr
, bitmap_set_t set1
, bitmap_set_t set2
,
1767 basic_block pred
, basic_block phiblock
)
1769 expr_pred_trans_t slot
= NULL
;
1775 /* Constants contain no values that need translation. */
1776 if (expr
->kind
== CONSTANT
)
1779 if (value_id_constant_p (get_expr_value_id (expr
)))
1782 /* Don't add translations of NAMEs as those are cheap to translate. */
1783 if (expr
->kind
!= NAME
)
1785 if (phi_trans_add (&slot
, expr
, pred
))
1787 /* Store NULL for the value we want to return in the case of
1793 phitrans
= phi_translate_1 (expr
, set1
, set2
, pred
, phiblock
);
1800 /* Remove failed translations again, they cause insert
1801 iteration to not pick up new opportunities reliably. */
1802 phi_translate_table
->remove_elt_with_hash (slot
, slot
->hashcode
);
1809 /* For each expression in SET, translate the values through phi nodes
1810 in PHIBLOCK using edge PHIBLOCK->PRED, and store the resulting
1811 expressions in DEST. */
1814 phi_translate_set (bitmap_set_t dest
, bitmap_set_t set
, basic_block pred
,
1815 basic_block phiblock
)
1817 vec
<pre_expr
> exprs
;
1821 if (gimple_seq_empty_p (phi_nodes (phiblock
)))
1823 bitmap_set_copy (dest
, set
);
1827 exprs
= sorted_array_from_bitmap_set (set
);
1828 FOR_EACH_VEC_ELT (exprs
, i
, expr
)
1830 pre_expr translated
;
1831 translated
= phi_translate (expr
, set
, NULL
, pred
, phiblock
);
1835 /* We might end up with multiple expressions from SET being
1836 translated to the same value. In this case we do not want
1837 to retain the NARY or REFERENCE expression but prefer a NAME
1838 which would be the leader. */
1839 if (translated
->kind
== NAME
)
1840 bitmap_value_replace_in_set (dest
, translated
);
1842 bitmap_value_insert_into_set (dest
, translated
);
1847 /* Find the leader for a value (i.e., the name representing that
1848 value) in a given set, and return it. Return NULL if no leader
1852 bitmap_find_leader (bitmap_set_t set
, unsigned int val
)
1854 if (value_id_constant_p (val
))
1858 bitmap exprset
= value_expressions
[val
];
1860 EXECUTE_IF_SET_IN_BITMAP (exprset
, 0, i
, bi
)
1862 pre_expr expr
= expression_for_id (i
);
1863 if (expr
->kind
== CONSTANT
)
1867 if (bitmap_set_contains_value (set
, val
))
1869 /* Rather than walk the entire bitmap of expressions, and see
1870 whether any of them has the value we are looking for, we look
1871 at the reverse mapping, which tells us the set of expressions
1872 that have a given value (IE value->expressions with that
1873 value) and see if any of those expressions are in our set.
1874 The number of expressions per value is usually significantly
1875 less than the number of expressions in the set. In fact, for
1876 large testcases, doing it this way is roughly 5-10x faster
1877 than walking the bitmap.
1878 If this is somehow a significant lose for some cases, we can
1879 choose which set to walk based on which set is smaller. */
1882 bitmap exprset
= value_expressions
[val
];
1884 EXECUTE_IF_AND_IN_BITMAP (exprset
, &set
->expressions
, 0, i
, bi
)
1885 return expression_for_id (i
);
1890 /* Determine if EXPR, a memory expression, is ANTIC_IN at the top of
1891 BLOCK by seeing if it is not killed in the block. Note that we are
1892 only determining whether there is a store that kills it. Because
1893 of the order in which clean iterates over values, we are guaranteed
1894 that altered operands will have caused us to be eliminated from the
1895 ANTIC_IN set already. */
1898 value_dies_in_block_x (pre_expr expr
, basic_block block
)
1900 tree vuse
= PRE_EXPR_REFERENCE (expr
)->vuse
;
1901 vn_reference_t refx
= PRE_EXPR_REFERENCE (expr
);
1903 gimple_stmt_iterator gsi
;
1904 unsigned id
= get_expression_id (expr
);
1911 /* Lookup a previously calculated result. */
1912 if (EXPR_DIES (block
)
1913 && bitmap_bit_p (EXPR_DIES (block
), id
* 2))
1914 return bitmap_bit_p (EXPR_DIES (block
), id
* 2 + 1);
1916 /* A memory expression {e, VUSE} dies in the block if there is a
1917 statement that may clobber e. If, starting statement walk from the
1918 top of the basic block, a statement uses VUSE there can be no kill
1919 inbetween that use and the original statement that loaded {e, VUSE},
1920 so we can stop walking. */
1921 ref
.base
= NULL_TREE
;
1922 for (gsi
= gsi_start_bb (block
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1924 tree def_vuse
, def_vdef
;
1925 def
= gsi_stmt (gsi
);
1926 def_vuse
= gimple_vuse (def
);
1927 def_vdef
= gimple_vdef (def
);
1929 /* Not a memory statement. */
1933 /* Not a may-def. */
1936 /* A load with the same VUSE, we're done. */
1937 if (def_vuse
== vuse
)
1943 /* Init ref only if we really need it. */
1944 if (ref
.base
== NULL_TREE
1945 && !ao_ref_init_from_vn_reference (&ref
, refx
->set
, refx
->type
,
1951 /* If the statement may clobber expr, it dies. */
1952 if (stmt_may_clobber_ref_p_1 (def
, &ref
))
1959 /* Remember the result. */
1960 if (!EXPR_DIES (block
))
1961 EXPR_DIES (block
) = BITMAP_ALLOC (&grand_bitmap_obstack
);
1962 bitmap_set_bit (EXPR_DIES (block
), id
* 2);
1964 bitmap_set_bit (EXPR_DIES (block
), id
* 2 + 1);
1970 /* Determine if OP is valid in SET1 U SET2, which it is when the union
1971 contains its value-id. */
1974 op_valid_in_sets (bitmap_set_t set1
, bitmap_set_t set2
, tree op
)
1976 if (op
&& TREE_CODE (op
) == SSA_NAME
)
1978 unsigned int value_id
= VN_INFO (op
)->value_id
;
1979 if (!(bitmap_set_contains_value (set1
, value_id
)
1980 || (set2
&& bitmap_set_contains_value (set2
, value_id
))))
1986 /* Determine if the expression EXPR is valid in SET1 U SET2.
1987 ONLY SET2 CAN BE NULL.
1988 This means that we have a leader for each part of the expression
1989 (if it consists of values), or the expression is an SSA_NAME.
1990 For loads/calls, we also see if the vuse is killed in this block. */
1993 valid_in_sets (bitmap_set_t set1
, bitmap_set_t set2
, pre_expr expr
)
1998 /* By construction all NAMEs are available. Non-available
1999 NAMEs are removed by subtracting TMP_GEN from the sets. */
2004 vn_nary_op_t nary
= PRE_EXPR_NARY (expr
);
2005 for (i
= 0; i
< nary
->length
; i
++)
2006 if (!op_valid_in_sets (set1
, set2
, nary
->op
[i
]))
2013 vn_reference_t ref
= PRE_EXPR_REFERENCE (expr
);
2014 vn_reference_op_t vro
;
2017 FOR_EACH_VEC_ELT (ref
->operands
, i
, vro
)
2019 if (!op_valid_in_sets (set1
, set2
, vro
->op0
)
2020 || !op_valid_in_sets (set1
, set2
, vro
->op1
)
2021 || !op_valid_in_sets (set1
, set2
, vro
->op2
))
2031 /* Clean the set of expressions that are no longer valid in SET1 or
2032 SET2. This means expressions that are made up of values we have no
2033 leaders for in SET1 or SET2. This version is used for partial
2034 anticipation, which means it is not valid in either ANTIC_IN or
2038 dependent_clean (bitmap_set_t set1
, bitmap_set_t set2
)
2040 vec
<pre_expr
> exprs
= sorted_array_from_bitmap_set (set1
);
2044 FOR_EACH_VEC_ELT (exprs
, i
, expr
)
2046 if (!valid_in_sets (set1
, set2
, expr
))
2047 bitmap_remove_from_set (set1
, expr
);
2052 /* Clean the set of expressions that are no longer valid in SET. This
2053 means expressions that are made up of values we have no leaders for
2057 clean (bitmap_set_t set
)
2059 vec
<pre_expr
> exprs
= sorted_array_from_bitmap_set (set
);
2063 FOR_EACH_VEC_ELT (exprs
, i
, expr
)
2065 if (!valid_in_sets (set
, NULL
, expr
))
2066 bitmap_remove_from_set (set
, expr
);
2071 /* Clean the set of expressions that are no longer valid in SET because
2072 they are clobbered in BLOCK or because they trap and may not be executed. */
2075 prune_clobbered_mems (bitmap_set_t set
, basic_block block
)
2080 FOR_EACH_EXPR_ID_IN_SET (set
, i
, bi
)
2082 pre_expr expr
= expression_for_id (i
);
2083 if (expr
->kind
== REFERENCE
)
2085 vn_reference_t ref
= PRE_EXPR_REFERENCE (expr
);
2088 gimple def_stmt
= SSA_NAME_DEF_STMT (ref
->vuse
);
2089 if (!gimple_nop_p (def_stmt
)
2090 && ((gimple_bb (def_stmt
) != block
2091 && !dominated_by_p (CDI_DOMINATORS
,
2092 block
, gimple_bb (def_stmt
)))
2093 || (gimple_bb (def_stmt
) == block
2094 && value_dies_in_block_x (expr
, block
))))
2095 bitmap_remove_from_set (set
, expr
);
2098 else if (expr
->kind
== NARY
)
2100 vn_nary_op_t nary
= PRE_EXPR_NARY (expr
);
2101 /* If the NARY may trap make sure the block does not contain
2102 a possible exit point.
2103 ??? This is overly conservative if we translate AVAIL_OUT
2104 as the available expression might be after the exit point. */
2105 if (BB_MAY_NOTRETURN (block
)
2106 && vn_nary_may_trap (nary
))
2107 bitmap_remove_from_set (set
, expr
);
2112 static sbitmap has_abnormal_preds
;
2114 /* List of blocks that may have changed during ANTIC computation and
2115 thus need to be iterated over. */
2117 static sbitmap changed_blocks
;
2119 /* Compute the ANTIC set for BLOCK.
2121 If succs(BLOCK) > 1 then
2122 ANTIC_OUT[BLOCK] = intersection of ANTIC_IN[b] for all succ(BLOCK)
2123 else if succs(BLOCK) == 1 then
2124 ANTIC_OUT[BLOCK] = phi_translate (ANTIC_IN[succ(BLOCK)])
2126 ANTIC_IN[BLOCK] = clean(ANTIC_OUT[BLOCK] U EXP_GEN[BLOCK] - TMP_GEN[BLOCK])
2130 compute_antic_aux (basic_block block
, bool block_has_abnormal_pred_edge
)
2132 bool changed
= false;
2133 bitmap_set_t S
, old
, ANTIC_OUT
;
2139 old
= ANTIC_OUT
= S
= NULL
;
2140 BB_VISITED (block
) = 1;
2142 /* If any edges from predecessors are abnormal, antic_in is empty,
2144 if (block_has_abnormal_pred_edge
)
2145 goto maybe_dump_sets
;
2147 old
= ANTIC_IN (block
);
2148 ANTIC_OUT
= bitmap_set_new ();
2150 /* If the block has no successors, ANTIC_OUT is empty. */
2151 if (EDGE_COUNT (block
->succs
) == 0)
2153 /* If we have one successor, we could have some phi nodes to
2154 translate through. */
2155 else if (single_succ_p (block
))
2157 basic_block succ_bb
= single_succ (block
);
2158 gcc_assert (BB_VISITED (succ_bb
));
2159 phi_translate_set (ANTIC_OUT
, ANTIC_IN (succ_bb
), block
, succ_bb
);
2161 /* If we have multiple successors, we take the intersection of all of
2162 them. Note that in the case of loop exit phi nodes, we may have
2163 phis to translate through. */
2167 basic_block bprime
, first
= NULL
;
2169 auto_vec
<basic_block
> worklist (EDGE_COUNT (block
->succs
));
2170 FOR_EACH_EDGE (e
, ei
, block
->succs
)
2173 && BB_VISITED (e
->dest
))
2175 else if (BB_VISITED (e
->dest
))
2176 worklist
.quick_push (e
->dest
);
2179 /* Of multiple successors we have to have visited one already
2180 which is guaranteed by iteration order. */
2181 gcc_assert (first
!= NULL
);
2183 phi_translate_set (ANTIC_OUT
, ANTIC_IN (first
), block
, first
);
2185 FOR_EACH_VEC_ELT (worklist
, i
, bprime
)
2187 if (!gimple_seq_empty_p (phi_nodes (bprime
)))
2189 bitmap_set_t tmp
= bitmap_set_new ();
2190 phi_translate_set (tmp
, ANTIC_IN (bprime
), block
, bprime
);
2191 bitmap_set_and (ANTIC_OUT
, tmp
);
2192 bitmap_set_free (tmp
);
2195 bitmap_set_and (ANTIC_OUT
, ANTIC_IN (bprime
));
2199 /* Prune expressions that are clobbered in block and thus become
2200 invalid if translated from ANTIC_OUT to ANTIC_IN. */
2201 prune_clobbered_mems (ANTIC_OUT
, block
);
2203 /* Generate ANTIC_OUT - TMP_GEN. */
2204 S
= bitmap_set_subtract (ANTIC_OUT
, TMP_GEN (block
));
2206 /* Start ANTIC_IN with EXP_GEN - TMP_GEN. */
2207 ANTIC_IN (block
) = bitmap_set_subtract (EXP_GEN (block
),
2210 /* Then union in the ANTIC_OUT - TMP_GEN values,
2211 to get ANTIC_OUT U EXP_GEN - TMP_GEN */
2212 FOR_EACH_EXPR_ID_IN_SET (S
, bii
, bi
)
2213 bitmap_value_insert_into_set (ANTIC_IN (block
),
2214 expression_for_id (bii
));
2216 clean (ANTIC_IN (block
));
2218 if (!bitmap_set_equal (old
, ANTIC_IN (block
)))
2221 bitmap_set_bit (changed_blocks
, block
->index
);
2222 FOR_EACH_EDGE (e
, ei
, block
->preds
)
2223 bitmap_set_bit (changed_blocks
, e
->src
->index
);
2226 bitmap_clear_bit (changed_blocks
, block
->index
);
2229 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2232 print_bitmap_set (dump_file
, ANTIC_OUT
, "ANTIC_OUT", block
->index
);
2234 print_bitmap_set (dump_file
, ANTIC_IN (block
), "ANTIC_IN",
2238 print_bitmap_set (dump_file
, S
, "S", block
->index
);
2241 bitmap_set_free (old
);
2243 bitmap_set_free (S
);
2245 bitmap_set_free (ANTIC_OUT
);
2249 /* Compute PARTIAL_ANTIC for BLOCK.
2251 If succs(BLOCK) > 1 then
2252 PA_OUT[BLOCK] = value wise union of PA_IN[b] + all ANTIC_IN not
2253 in ANTIC_OUT for all succ(BLOCK)
2254 else if succs(BLOCK) == 1 then
2255 PA_OUT[BLOCK] = phi_translate (PA_IN[succ(BLOCK)])
2257 PA_IN[BLOCK] = dependent_clean(PA_OUT[BLOCK] - TMP_GEN[BLOCK]
2262 compute_partial_antic_aux (basic_block block
,
2263 bool block_has_abnormal_pred_edge
)
2265 bool changed
= false;
2266 bitmap_set_t old_PA_IN
;
2267 bitmap_set_t PA_OUT
;
2270 unsigned long max_pa
= PARAM_VALUE (PARAM_MAX_PARTIAL_ANTIC_LENGTH
);
2272 old_PA_IN
= PA_OUT
= NULL
;
2274 /* If any edges from predecessors are abnormal, antic_in is empty,
2276 if (block_has_abnormal_pred_edge
)
2277 goto maybe_dump_sets
;
2279 /* If there are too many partially anticipatable values in the
2280 block, phi_translate_set can take an exponential time: stop
2281 before the translation starts. */
2283 && single_succ_p (block
)
2284 && bitmap_count_bits (&PA_IN (single_succ (block
))->values
) > max_pa
)
2285 goto maybe_dump_sets
;
2287 old_PA_IN
= PA_IN (block
);
2288 PA_OUT
= bitmap_set_new ();
2290 /* If the block has no successors, ANTIC_OUT is empty. */
2291 if (EDGE_COUNT (block
->succs
) == 0)
2293 /* If we have one successor, we could have some phi nodes to
2294 translate through. Note that we can't phi translate across DFS
2295 back edges in partial antic, because it uses a union operation on
2296 the successors. For recurrences like IV's, we will end up
2297 generating a new value in the set on each go around (i + 3 (VH.1)
2298 VH.1 + 1 (VH.2), VH.2 + 1 (VH.3), etc), forever. */
2299 else if (single_succ_p (block
))
2301 basic_block succ
= single_succ (block
);
2302 if (!(single_succ_edge (block
)->flags
& EDGE_DFS_BACK
))
2303 phi_translate_set (PA_OUT
, PA_IN (succ
), block
, succ
);
2305 /* If we have multiple successors, we take the union of all of
2312 auto_vec
<basic_block
> worklist (EDGE_COUNT (block
->succs
));
2313 FOR_EACH_EDGE (e
, ei
, block
->succs
)
2315 if (e
->flags
& EDGE_DFS_BACK
)
2317 worklist
.quick_push (e
->dest
);
2319 if (worklist
.length () > 0)
2321 FOR_EACH_VEC_ELT (worklist
, i
, bprime
)
2326 FOR_EACH_EXPR_ID_IN_SET (ANTIC_IN (bprime
), i
, bi
)
2327 bitmap_value_insert_into_set (PA_OUT
,
2328 expression_for_id (i
));
2329 if (!gimple_seq_empty_p (phi_nodes (bprime
)))
2331 bitmap_set_t pa_in
= bitmap_set_new ();
2332 phi_translate_set (pa_in
, PA_IN (bprime
), block
, bprime
);
2333 FOR_EACH_EXPR_ID_IN_SET (pa_in
, i
, bi
)
2334 bitmap_value_insert_into_set (PA_OUT
,
2335 expression_for_id (i
));
2336 bitmap_set_free (pa_in
);
2339 FOR_EACH_EXPR_ID_IN_SET (PA_IN (bprime
), i
, bi
)
2340 bitmap_value_insert_into_set (PA_OUT
,
2341 expression_for_id (i
));
2346 /* Prune expressions that are clobbered in block and thus become
2347 invalid if translated from PA_OUT to PA_IN. */
2348 prune_clobbered_mems (PA_OUT
, block
);
2350 /* PA_IN starts with PA_OUT - TMP_GEN.
2351 Then we subtract things from ANTIC_IN. */
2352 PA_IN (block
) = bitmap_set_subtract (PA_OUT
, TMP_GEN (block
));
2354 /* For partial antic, we want to put back in the phi results, since
2355 we will properly avoid making them partially antic over backedges. */
2356 bitmap_ior_into (&PA_IN (block
)->values
, &PHI_GEN (block
)->values
);
2357 bitmap_ior_into (&PA_IN (block
)->expressions
, &PHI_GEN (block
)->expressions
);
2359 /* PA_IN[block] = PA_IN[block] - ANTIC_IN[block] */
2360 bitmap_set_subtract_values (PA_IN (block
), ANTIC_IN (block
));
2362 dependent_clean (PA_IN (block
), ANTIC_IN (block
));
2364 if (!bitmap_set_equal (old_PA_IN
, PA_IN (block
)))
2367 bitmap_set_bit (changed_blocks
, block
->index
);
2368 FOR_EACH_EDGE (e
, ei
, block
->preds
)
2369 bitmap_set_bit (changed_blocks
, e
->src
->index
);
2372 bitmap_clear_bit (changed_blocks
, block
->index
);
2375 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2378 print_bitmap_set (dump_file
, PA_OUT
, "PA_OUT", block
->index
);
2380 print_bitmap_set (dump_file
, PA_IN (block
), "PA_IN", block
->index
);
2383 bitmap_set_free (old_PA_IN
);
2385 bitmap_set_free (PA_OUT
);
2389 /* Compute ANTIC and partial ANTIC sets. */
2392 compute_antic (void)
2394 bool changed
= true;
2395 int num_iterations
= 0;
2399 /* If any predecessor edges are abnormal, we punt, so antic_in is empty.
2400 We pre-build the map of blocks with incoming abnormal edges here. */
2401 has_abnormal_preds
= sbitmap_alloc (last_basic_block_for_fn (cfun
));
2402 bitmap_clear (has_abnormal_preds
);
2404 FOR_ALL_BB_FN (block
, cfun
)
2409 FOR_EACH_EDGE (e
, ei
, block
->preds
)
2411 e
->flags
&= ~EDGE_DFS_BACK
;
2412 if (e
->flags
& EDGE_ABNORMAL
)
2414 bitmap_set_bit (has_abnormal_preds
, block
->index
);
2419 BB_VISITED (block
) = 0;
2421 /* While we are here, give empty ANTIC_IN sets to each block. */
2422 ANTIC_IN (block
) = bitmap_set_new ();
2423 PA_IN (block
) = bitmap_set_new ();
2426 /* At the exit block we anticipate nothing. */
2427 BB_VISITED (EXIT_BLOCK_PTR_FOR_FN (cfun
)) = 1;
2429 changed_blocks
= sbitmap_alloc (last_basic_block_for_fn (cfun
) + 1);
2430 bitmap_ones (changed_blocks
);
2433 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2434 fprintf (dump_file
, "Starting iteration %d\n", num_iterations
);
2435 /* ??? We need to clear our PHI translation cache here as the
2436 ANTIC sets shrink and we restrict valid translations to
2437 those having operands with leaders in ANTIC. Same below
2438 for PA ANTIC computation. */
2441 for (i
= postorder_num
- 1; i
>= 0; i
--)
2443 if (bitmap_bit_p (changed_blocks
, postorder
[i
]))
2445 basic_block block
= BASIC_BLOCK_FOR_FN (cfun
, postorder
[i
]);
2446 changed
|= compute_antic_aux (block
,
2447 bitmap_bit_p (has_abnormal_preds
,
2451 /* Theoretically possible, but *highly* unlikely. */
2452 gcc_checking_assert (num_iterations
< 500);
2455 statistics_histogram_event (cfun
, "compute_antic iterations",
2458 if (do_partial_partial
)
2460 bitmap_ones (changed_blocks
);
2461 mark_dfs_back_edges ();
2466 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2467 fprintf (dump_file
, "Starting iteration %d\n", num_iterations
);
2470 for (i
= postorder_num
- 1 ; i
>= 0; i
--)
2472 if (bitmap_bit_p (changed_blocks
, postorder
[i
]))
2474 basic_block block
= BASIC_BLOCK_FOR_FN (cfun
, postorder
[i
]);
2476 |= compute_partial_antic_aux (block
,
2477 bitmap_bit_p (has_abnormal_preds
,
2481 /* Theoretically possible, but *highly* unlikely. */
2482 gcc_checking_assert (num_iterations
< 500);
2484 statistics_histogram_event (cfun
, "compute_partial_antic iterations",
2487 sbitmap_free (has_abnormal_preds
);
2488 sbitmap_free (changed_blocks
);
2492 /* Inserted expressions are placed onto this worklist, which is used
2493 for performing quick dead code elimination of insertions we made
2494 that didn't turn out to be necessary. */
2495 static bitmap inserted_exprs
;
2497 /* The actual worker for create_component_ref_by_pieces. */
2500 create_component_ref_by_pieces_1 (basic_block block
, vn_reference_t ref
,
2501 unsigned int *operand
, gimple_seq
*stmts
)
2503 vn_reference_op_t currop
= &ref
->operands
[*operand
];
2506 switch (currop
->opcode
)
2510 tree folded
, sc
= NULL_TREE
;
2511 unsigned int nargs
= 0;
2513 if (TREE_CODE (currop
->op0
) == FUNCTION_DECL
)
2516 fn
= find_or_generate_expression (block
, currop
->op0
, stmts
);
2521 sc
= find_or_generate_expression (block
, currop
->op1
, stmts
);
2525 args
= XNEWVEC (tree
, ref
->operands
.length () - 1);
2526 while (*operand
< ref
->operands
.length ())
2528 args
[nargs
] = create_component_ref_by_pieces_1 (block
, ref
,
2534 folded
= build_call_array (currop
->type
,
2535 (TREE_CODE (fn
) == FUNCTION_DECL
2536 ? build_fold_addr_expr (fn
) : fn
),
2538 if (currop
->with_bounds
)
2539 CALL_WITH_BOUNDS_P (folded
) = true;
2542 CALL_EXPR_STATIC_CHAIN (folded
) = sc
;
2548 tree baseop
= create_component_ref_by_pieces_1 (block
, ref
, operand
,
2552 tree offset
= currop
->op0
;
2553 if (TREE_CODE (baseop
) == ADDR_EXPR
2554 && handled_component_p (TREE_OPERAND (baseop
, 0)))
2558 base
= get_addr_base_and_unit_offset (TREE_OPERAND (baseop
, 0),
2561 offset
= int_const_binop (PLUS_EXPR
, offset
,
2562 build_int_cst (TREE_TYPE (offset
),
2564 baseop
= build_fold_addr_expr (base
);
2566 return fold_build2 (MEM_REF
, currop
->type
, baseop
, offset
);
2569 case TARGET_MEM_REF
:
2571 tree genop0
= NULL_TREE
, genop1
= NULL_TREE
;
2572 vn_reference_op_t nextop
= &ref
->operands
[++*operand
];
2573 tree baseop
= create_component_ref_by_pieces_1 (block
, ref
, operand
,
2579 genop0
= find_or_generate_expression (block
, currop
->op0
, stmts
);
2585 genop1
= find_or_generate_expression (block
, nextop
->op0
, stmts
);
2589 return build5 (TARGET_MEM_REF
, currop
->type
,
2590 baseop
, currop
->op2
, genop0
, currop
->op1
, genop1
);
2596 gcc_assert (is_gimple_min_invariant (currop
->op0
));
2602 case VIEW_CONVERT_EXPR
:
2604 tree genop0
= create_component_ref_by_pieces_1 (block
, ref
, operand
,
2608 return fold_build1 (currop
->opcode
, currop
->type
, genop0
);
2611 case WITH_SIZE_EXPR
:
2613 tree genop0
= create_component_ref_by_pieces_1 (block
, ref
, operand
,
2617 tree genop1
= find_or_generate_expression (block
, currop
->op0
, stmts
);
2620 return fold_build2 (currop
->opcode
, currop
->type
, genop0
, genop1
);
2625 tree genop0
= create_component_ref_by_pieces_1 (block
, ref
, operand
,
2629 tree op1
= currop
->op0
;
2630 tree op2
= currop
->op1
;
2631 return fold_build3 (BIT_FIELD_REF
, currop
->type
, genop0
, op1
, op2
);
2634 /* For array ref vn_reference_op's, operand 1 of the array ref
2635 is op0 of the reference op and operand 3 of the array ref is
2637 case ARRAY_RANGE_REF
:
2641 tree genop1
= currop
->op0
;
2642 tree genop2
= currop
->op1
;
2643 tree genop3
= currop
->op2
;
2644 genop0
= create_component_ref_by_pieces_1 (block
, ref
, operand
,
2648 genop1
= find_or_generate_expression (block
, genop1
, stmts
);
2653 tree domain_type
= TYPE_DOMAIN (TREE_TYPE (genop0
));
2654 /* Drop zero minimum index if redundant. */
2655 if (integer_zerop (genop2
)
2657 || integer_zerop (TYPE_MIN_VALUE (domain_type
))))
2661 genop2
= find_or_generate_expression (block
, genop2
, stmts
);
2668 tree elmt_type
= TREE_TYPE (TREE_TYPE (genop0
));
2669 /* We can't always put a size in units of the element alignment
2670 here as the element alignment may be not visible. See
2671 PR43783. Simply drop the element size for constant
2673 if (tree_int_cst_equal (genop3
, TYPE_SIZE_UNIT (elmt_type
)))
2677 genop3
= size_binop (EXACT_DIV_EXPR
, genop3
,
2678 size_int (TYPE_ALIGN_UNIT (elmt_type
)));
2679 genop3
= find_or_generate_expression (block
, genop3
, stmts
);
2684 return build4 (currop
->opcode
, currop
->type
, genop0
, genop1
,
2691 tree genop2
= currop
->op1
;
2692 op0
= create_component_ref_by_pieces_1 (block
, ref
, operand
, stmts
);
2695 /* op1 should be a FIELD_DECL, which are represented by themselves. */
2699 genop2
= find_or_generate_expression (block
, genop2
, stmts
);
2703 return fold_build3 (COMPONENT_REF
, TREE_TYPE (op1
), op0
, op1
, genop2
);
2708 genop
= find_or_generate_expression (block
, currop
->op0
, stmts
);
2729 /* For COMPONENT_REF's and ARRAY_REF's, we can't have any intermediates for the
2730 COMPONENT_REF or MEM_REF or ARRAY_REF portion, because we'd end up with
2731 trying to rename aggregates into ssa form directly, which is a no no.
2733 Thus, this routine doesn't create temporaries, it just builds a
2734 single access expression for the array, calling
2735 find_or_generate_expression to build the innermost pieces.
2737 This function is a subroutine of create_expression_by_pieces, and
2738 should not be called on it's own unless you really know what you
2742 create_component_ref_by_pieces (basic_block block
, vn_reference_t ref
,
2745 unsigned int op
= 0;
2746 return create_component_ref_by_pieces_1 (block
, ref
, &op
, stmts
);
2749 /* Find a simple leader for an expression, or generate one using
2750 create_expression_by_pieces from a NARY expression for the value.
2751 BLOCK is the basic_block we are looking for leaders in.
2752 OP is the tree expression to find a leader for or generate.
2753 Returns the leader or NULL_TREE on failure. */
2756 find_or_generate_expression (basic_block block
, tree op
, gimple_seq
*stmts
)
2758 pre_expr expr
= get_or_alloc_expr_for (op
);
2759 unsigned int lookfor
= get_expr_value_id (expr
);
2760 pre_expr leader
= bitmap_find_leader (AVAIL_OUT (block
), lookfor
);
2763 if (leader
->kind
== NAME
)
2764 return PRE_EXPR_NAME (leader
);
2765 else if (leader
->kind
== CONSTANT
)
2766 return PRE_EXPR_CONSTANT (leader
);
2772 /* It must be a complex expression, so generate it recursively. Note
2773 that this is only necessary to handle gcc.dg/tree-ssa/ssa-pre28.c
2774 where the insert algorithm fails to insert a required expression. */
2775 bitmap exprset
= value_expressions
[lookfor
];
2778 EXECUTE_IF_SET_IN_BITMAP (exprset
, 0, i
, bi
)
2780 pre_expr temp
= expression_for_id (i
);
2781 /* We cannot insert random REFERENCE expressions at arbitrary
2782 places. We can insert NARYs which eventually re-materializes
2783 its operand values. */
2784 if (temp
->kind
== NARY
)
2785 return create_expression_by_pieces (block
, temp
, stmts
,
2786 get_expr_type (expr
));
2793 #define NECESSARY GF_PLF_1
2795 /* Create an expression in pieces, so that we can handle very complex
2796 expressions that may be ANTIC, but not necessary GIMPLE.
2797 BLOCK is the basic block the expression will be inserted into,
2798 EXPR is the expression to insert (in value form)
2799 STMTS is a statement list to append the necessary insertions into.
2801 This function will die if we hit some value that shouldn't be
2802 ANTIC but is (IE there is no leader for it, or its components).
2803 The function returns NULL_TREE in case a different antic expression
2804 has to be inserted first.
2805 This function may also generate expressions that are themselves
2806 partially or fully redundant. Those that are will be either made
2807 fully redundant during the next iteration of insert (for partially
2808 redundant ones), or eliminated by eliminate (for fully redundant
2812 create_expression_by_pieces (basic_block block
, pre_expr expr
,
2813 gimple_seq
*stmts
, tree type
)
2817 gimple_seq forced_stmts
= NULL
;
2818 unsigned int value_id
;
2819 gimple_stmt_iterator gsi
;
2820 tree exprtype
= type
? type
: get_expr_type (expr
);
2826 /* We may hit the NAME/CONSTANT case if we have to convert types
2827 that value numbering saw through. */
2829 folded
= PRE_EXPR_NAME (expr
);
2832 folded
= PRE_EXPR_CONSTANT (expr
);
2836 vn_reference_t ref
= PRE_EXPR_REFERENCE (expr
);
2837 folded
= create_component_ref_by_pieces (block
, ref
, stmts
);
2844 vn_nary_op_t nary
= PRE_EXPR_NARY (expr
);
2845 tree
*genop
= XALLOCAVEC (tree
, nary
->length
);
2847 for (i
= 0; i
< nary
->length
; ++i
)
2849 genop
[i
] = find_or_generate_expression (block
, nary
->op
[i
], stmts
);
2852 /* Ensure genop[] is properly typed for POINTER_PLUS_EXPR. It
2853 may have conversions stripped. */
2854 if (nary
->opcode
== POINTER_PLUS_EXPR
)
2857 genop
[i
] = gimple_convert (&forced_stmts
,
2858 nary
->type
, genop
[i
]);
2860 genop
[i
] = gimple_convert (&forced_stmts
,
2861 sizetype
, genop
[i
]);
2864 genop
[i
] = gimple_convert (&forced_stmts
,
2865 TREE_TYPE (nary
->op
[i
]), genop
[i
]);
2867 if (nary
->opcode
== CONSTRUCTOR
)
2869 vec
<constructor_elt
, va_gc
> *elts
= NULL
;
2870 for (i
= 0; i
< nary
->length
; ++i
)
2871 CONSTRUCTOR_APPEND_ELT (elts
, NULL_TREE
, genop
[i
]);
2872 folded
= build_constructor (nary
->type
, elts
);
2876 switch (nary
->length
)
2879 folded
= fold_build1 (nary
->opcode
, nary
->type
,
2883 folded
= fold_build2 (nary
->opcode
, nary
->type
,
2884 genop
[0], genop
[1]);
2887 folded
= fold_build3 (nary
->opcode
, nary
->type
,
2888 genop
[0], genop
[1], genop
[2]);
2900 if (!useless_type_conversion_p (exprtype
, TREE_TYPE (folded
)))
2901 folded
= fold_convert (exprtype
, folded
);
2903 /* Force the generated expression to be a sequence of GIMPLE
2905 We have to call unshare_expr because force_gimple_operand may
2906 modify the tree we pass to it. */
2907 gimple_seq tem
= NULL
;
2908 folded
= force_gimple_operand (unshare_expr (folded
), &tem
,
2910 gimple_seq_add_seq_without_update (&forced_stmts
, tem
);
2912 /* If we have any intermediate expressions to the value sets, add them
2913 to the value sets and chain them in the instruction stream. */
2916 gsi
= gsi_start (forced_stmts
);
2917 for (; !gsi_end_p (gsi
); gsi_next (&gsi
))
2919 gimple stmt
= gsi_stmt (gsi
);
2920 tree forcedname
= gimple_get_lhs (stmt
);
2923 if (TREE_CODE (forcedname
) == SSA_NAME
)
2925 bitmap_set_bit (inserted_exprs
, SSA_NAME_VERSION (forcedname
));
2926 VN_INFO_GET (forcedname
)->valnum
= forcedname
;
2927 VN_INFO (forcedname
)->value_id
= get_next_value_id ();
2928 nameexpr
= get_or_alloc_expr_for_name (forcedname
);
2929 add_to_value (VN_INFO (forcedname
)->value_id
, nameexpr
);
2930 bitmap_value_replace_in_set (NEW_SETS (block
), nameexpr
);
2931 bitmap_value_replace_in_set (AVAIL_OUT (block
), nameexpr
);
2934 gimple_set_vuse (stmt
, BB_LIVE_VOP_ON_EXIT (block
));
2935 gimple_set_modified (stmt
, true);
2937 gimple_seq_add_seq (stmts
, forced_stmts
);
2940 name
= make_temp_ssa_name (exprtype
, NULL
, "pretmp");
2941 newstmt
= gimple_build_assign (name
, folded
);
2942 gimple_set_vuse (newstmt
, BB_LIVE_VOP_ON_EXIT (block
));
2943 gimple_set_modified (newstmt
, true);
2944 gimple_set_plf (newstmt
, NECESSARY
, false);
2946 gimple_seq_add_stmt (stmts
, newstmt
);
2947 bitmap_set_bit (inserted_exprs
, SSA_NAME_VERSION (name
));
2949 /* Fold the last statement. */
2950 gsi
= gsi_last (*stmts
);
2951 if (fold_stmt_inplace (&gsi
))
2952 update_stmt (gsi_stmt (gsi
));
2954 /* Add a value number to the temporary.
2955 The value may already exist in either NEW_SETS, or AVAIL_OUT, because
2956 we are creating the expression by pieces, and this particular piece of
2957 the expression may have been represented. There is no harm in replacing
2959 value_id
= get_expr_value_id (expr
);
2960 VN_INFO_GET (name
)->value_id
= value_id
;
2961 VN_INFO (name
)->valnum
= sccvn_valnum_from_value_id (value_id
);
2962 if (VN_INFO (name
)->valnum
== NULL_TREE
)
2963 VN_INFO (name
)->valnum
= name
;
2964 gcc_assert (VN_INFO (name
)->valnum
!= NULL_TREE
);
2965 nameexpr
= get_or_alloc_expr_for_name (name
);
2966 add_to_value (value_id
, nameexpr
);
2967 if (NEW_SETS (block
))
2968 bitmap_value_replace_in_set (NEW_SETS (block
), nameexpr
);
2969 bitmap_value_replace_in_set (AVAIL_OUT (block
), nameexpr
);
2971 pre_stats
.insertions
++;
2972 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2974 fprintf (dump_file
, "Inserted ");
2975 print_gimple_stmt (dump_file
, newstmt
, 0, 0);
2976 fprintf (dump_file
, " in predecessor %d (%04d)\n",
2977 block
->index
, value_id
);
2984 /* Insert the to-be-made-available values of expression EXPRNUM for each
2985 predecessor, stored in AVAIL, into the predecessors of BLOCK, and
2986 merge the result with a phi node, given the same value number as
2987 NODE. Return true if we have inserted new stuff. */
2990 insert_into_preds_of_block (basic_block block
, unsigned int exprnum
,
2991 vec
<pre_expr
> avail
)
2993 pre_expr expr
= expression_for_id (exprnum
);
2995 unsigned int val
= get_expr_value_id (expr
);
2997 bool insertions
= false;
3002 tree type
= get_expr_type (expr
);
3006 /* Make sure we aren't creating an induction variable. */
3007 if (bb_loop_depth (block
) > 0 && EDGE_COUNT (block
->preds
) == 2)
3009 bool firstinsideloop
= false;
3010 bool secondinsideloop
= false;
3011 firstinsideloop
= flow_bb_inside_loop_p (block
->loop_father
,
3012 EDGE_PRED (block
, 0)->src
);
3013 secondinsideloop
= flow_bb_inside_loop_p (block
->loop_father
,
3014 EDGE_PRED (block
, 1)->src
);
3015 /* Induction variables only have one edge inside the loop. */
3016 if ((firstinsideloop
^ secondinsideloop
)
3017 && expr
->kind
!= REFERENCE
)
3019 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3020 fprintf (dump_file
, "Skipping insertion of phi for partial redundancy: Looks like an induction variable\n");
3025 /* Make the necessary insertions. */
3026 FOR_EACH_EDGE (pred
, ei
, block
->preds
)
3028 gimple_seq stmts
= NULL
;
3031 eprime
= avail
[pred
->dest_idx
];
3033 if (eprime
->kind
!= NAME
&& eprime
->kind
!= CONSTANT
)
3035 builtexpr
= create_expression_by_pieces (bprime
, eprime
,
3037 gcc_assert (!(pred
->flags
& EDGE_ABNORMAL
));
3038 gsi_insert_seq_on_edge (pred
, stmts
);
3041 /* We cannot insert a PHI node if we failed to insert
3046 avail
[pred
->dest_idx
] = get_or_alloc_expr_for_name (builtexpr
);
3049 else if (eprime
->kind
== CONSTANT
)
3051 /* Constants may not have the right type, fold_convert
3052 should give us back a constant with the right type. */
3053 tree constant
= PRE_EXPR_CONSTANT (eprime
);
3054 if (!useless_type_conversion_p (type
, TREE_TYPE (constant
)))
3056 tree builtexpr
= fold_convert (type
, constant
);
3057 if (!is_gimple_min_invariant (builtexpr
))
3059 tree forcedexpr
= force_gimple_operand (builtexpr
,
3062 if (!is_gimple_min_invariant (forcedexpr
))
3064 if (forcedexpr
!= builtexpr
)
3066 VN_INFO_GET (forcedexpr
)->valnum
= PRE_EXPR_CONSTANT (eprime
);
3067 VN_INFO (forcedexpr
)->value_id
= get_expr_value_id (eprime
);
3071 gimple_stmt_iterator gsi
;
3072 gsi
= gsi_start (stmts
);
3073 for (; !gsi_end_p (gsi
); gsi_next (&gsi
))
3075 gimple stmt
= gsi_stmt (gsi
);
3076 tree lhs
= gimple_get_lhs (stmt
);
3077 if (TREE_CODE (lhs
) == SSA_NAME
)
3078 bitmap_set_bit (inserted_exprs
,
3079 SSA_NAME_VERSION (lhs
));
3080 gimple_set_plf (stmt
, NECESSARY
, false);
3082 gsi_insert_seq_on_edge (pred
, stmts
);
3084 avail
[pred
->dest_idx
]
3085 = get_or_alloc_expr_for_name (forcedexpr
);
3089 avail
[pred
->dest_idx
]
3090 = get_or_alloc_expr_for_constant (builtexpr
);
3093 else if (eprime
->kind
== NAME
)
3095 /* We may have to do a conversion because our value
3096 numbering can look through types in certain cases, but
3097 our IL requires all operands of a phi node have the same
3099 tree name
= PRE_EXPR_NAME (eprime
);
3100 if (!useless_type_conversion_p (type
, TREE_TYPE (name
)))
3104 builtexpr
= fold_convert (type
, name
);
3105 forcedexpr
= force_gimple_operand (builtexpr
,
3109 if (forcedexpr
!= name
)
3111 VN_INFO_GET (forcedexpr
)->valnum
= VN_INFO (name
)->valnum
;
3112 VN_INFO (forcedexpr
)->value_id
= VN_INFO (name
)->value_id
;
3117 gimple_stmt_iterator gsi
;
3118 gsi
= gsi_start (stmts
);
3119 for (; !gsi_end_p (gsi
); gsi_next (&gsi
))
3121 gimple stmt
= gsi_stmt (gsi
);
3122 tree lhs
= gimple_get_lhs (stmt
);
3123 if (TREE_CODE (lhs
) == SSA_NAME
)
3124 bitmap_set_bit (inserted_exprs
, SSA_NAME_VERSION (lhs
));
3125 gimple_set_plf (stmt
, NECESSARY
, false);
3127 gsi_insert_seq_on_edge (pred
, stmts
);
3129 avail
[pred
->dest_idx
] = get_or_alloc_expr_for_name (forcedexpr
);
3133 /* If we didn't want a phi node, and we made insertions, we still have
3134 inserted new stuff, and thus return true. If we didn't want a phi node,
3135 and didn't make insertions, we haven't added anything new, so return
3137 if (nophi
&& insertions
)
3139 else if (nophi
&& !insertions
)
3142 /* Now build a phi for the new variable. */
3143 temp
= make_temp_ssa_name (type
, NULL
, "prephitmp");
3144 phi
= create_phi_node (temp
, block
);
3146 gimple_set_plf (phi
, NECESSARY
, false);
3147 VN_INFO_GET (temp
)->value_id
= val
;
3148 VN_INFO (temp
)->valnum
= sccvn_valnum_from_value_id (val
);
3149 if (VN_INFO (temp
)->valnum
== NULL_TREE
)
3150 VN_INFO (temp
)->valnum
= temp
;
3151 bitmap_set_bit (inserted_exprs
, SSA_NAME_VERSION (temp
));
3152 FOR_EACH_EDGE (pred
, ei
, block
->preds
)
3154 pre_expr ae
= avail
[pred
->dest_idx
];
3155 gcc_assert (get_expr_type (ae
) == type
3156 || useless_type_conversion_p (type
, get_expr_type (ae
)));
3157 if (ae
->kind
== CONSTANT
)
3158 add_phi_arg (phi
, unshare_expr (PRE_EXPR_CONSTANT (ae
)),
3159 pred
, UNKNOWN_LOCATION
);
3161 add_phi_arg (phi
, PRE_EXPR_NAME (ae
), pred
, UNKNOWN_LOCATION
);
3164 newphi
= get_or_alloc_expr_for_name (temp
);
3165 add_to_value (val
, newphi
);
3167 /* The value should *not* exist in PHI_GEN, or else we wouldn't be doing
3168 this insertion, since we test for the existence of this value in PHI_GEN
3169 before proceeding with the partial redundancy checks in insert_aux.
3171 The value may exist in AVAIL_OUT, in particular, it could be represented
3172 by the expression we are trying to eliminate, in which case we want the
3173 replacement to occur. If it's not existing in AVAIL_OUT, we want it
3176 Similarly, to the PHI_GEN case, the value should not exist in NEW_SETS of
3177 this block, because if it did, it would have existed in our dominator's
3178 AVAIL_OUT, and would have been skipped due to the full redundancy check.
3181 bitmap_insert_into_set (PHI_GEN (block
), newphi
);
3182 bitmap_value_replace_in_set (AVAIL_OUT (block
),
3184 bitmap_insert_into_set (NEW_SETS (block
),
3187 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3189 fprintf (dump_file
, "Created phi ");
3190 print_gimple_stmt (dump_file
, phi
, 0, 0);
3191 fprintf (dump_file
, " in block %d (%04d)\n", block
->index
, val
);
3199 /* Perform insertion of partially redundant values.
3200 For BLOCK, do the following:
3201 1. Propagate the NEW_SETS of the dominator into the current block.
3202 If the block has multiple predecessors,
3203 2a. Iterate over the ANTIC expressions for the block to see if
3204 any of them are partially redundant.
3205 2b. If so, insert them into the necessary predecessors to make
3206 the expression fully redundant.
3207 2c. Insert a new PHI merging the values of the predecessors.
3208 2d. Insert the new PHI, and the new expressions, into the
3210 3. Recursively call ourselves on the dominator children of BLOCK.
3212 Steps 1, 2a, and 3 are done by insert_aux. 2b, 2c and 2d are done by
3213 do_regular_insertion and do_partial_insertion.
3218 do_regular_insertion (basic_block block
, basic_block dom
)
3220 bool new_stuff
= false;
3221 vec
<pre_expr
> exprs
;
3223 auto_vec
<pre_expr
> avail
;
3226 exprs
= sorted_array_from_bitmap_set (ANTIC_IN (block
));
3227 avail
.safe_grow (EDGE_COUNT (block
->preds
));
3229 FOR_EACH_VEC_ELT (exprs
, i
, expr
)
3231 if (expr
->kind
== NARY
3232 || expr
->kind
== REFERENCE
)
3235 bool by_some
= false;
3236 bool cant_insert
= false;
3237 bool all_same
= true;
3238 pre_expr first_s
= NULL
;
3241 pre_expr eprime
= NULL
;
3243 pre_expr edoubleprime
= NULL
;
3244 bool do_insertion
= false;
3246 val
= get_expr_value_id (expr
);
3247 if (bitmap_set_contains_value (PHI_GEN (block
), val
))
3249 if (bitmap_set_contains_value (AVAIL_OUT (dom
), val
))
3251 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3253 fprintf (dump_file
, "Found fully redundant value: ");
3254 print_pre_expr (dump_file
, expr
);
3255 fprintf (dump_file
, "\n");
3260 FOR_EACH_EDGE (pred
, ei
, block
->preds
)
3262 unsigned int vprime
;
3264 /* We should never run insertion for the exit block
3265 and so not come across fake pred edges. */
3266 gcc_assert (!(pred
->flags
& EDGE_FAKE
));
3268 eprime
= phi_translate (expr
, ANTIC_IN (block
), NULL
,
3271 /* eprime will generally only be NULL if the
3272 value of the expression, translated
3273 through the PHI for this predecessor, is
3274 undefined. If that is the case, we can't
3275 make the expression fully redundant,
3276 because its value is undefined along a
3277 predecessor path. We can thus break out
3278 early because it doesn't matter what the
3279 rest of the results are. */
3282 avail
[pred
->dest_idx
] = NULL
;
3287 eprime
= fully_constant_expression (eprime
);
3288 vprime
= get_expr_value_id (eprime
);
3289 edoubleprime
= bitmap_find_leader (AVAIL_OUT (bprime
),
3291 if (edoubleprime
== NULL
)
3293 avail
[pred
->dest_idx
] = eprime
;
3298 avail
[pred
->dest_idx
] = edoubleprime
;
3300 /* We want to perform insertions to remove a redundancy on
3301 a path in the CFG we want to optimize for speed. */
3302 if (optimize_edge_for_speed_p (pred
))
3303 do_insertion
= true;
3304 if (first_s
== NULL
)
3305 first_s
= edoubleprime
;
3306 else if (!pre_expr_d::equal (first_s
, edoubleprime
))
3310 /* If we can insert it, it's not the same value
3311 already existing along every predecessor, and
3312 it's defined by some predecessor, it is
3313 partially redundant. */
3314 if (!cant_insert
&& !all_same
&& by_some
)
3318 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3320 fprintf (dump_file
, "Skipping partial redundancy for "
3322 print_pre_expr (dump_file
, expr
);
3323 fprintf (dump_file
, " (%04d), no redundancy on to be "
3324 "optimized for speed edge\n", val
);
3327 else if (dbg_cnt (treepre_insert
))
3329 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3331 fprintf (dump_file
, "Found partial redundancy for "
3333 print_pre_expr (dump_file
, expr
);
3334 fprintf (dump_file
, " (%04d)\n",
3335 get_expr_value_id (expr
));
3337 if (insert_into_preds_of_block (block
,
3338 get_expression_id (expr
),
3343 /* If all edges produce the same value and that value is
3344 an invariant, then the PHI has the same value on all
3345 edges. Note this. */
3346 else if (!cant_insert
&& all_same
)
3348 gcc_assert (edoubleprime
->kind
== CONSTANT
3349 || edoubleprime
->kind
== NAME
);
3351 tree temp
= make_temp_ssa_name (get_expr_type (expr
),
3354 = gimple_build_assign (temp
,
3355 edoubleprime
->kind
== CONSTANT
?
3356 PRE_EXPR_CONSTANT (edoubleprime
) :
3357 PRE_EXPR_NAME (edoubleprime
));
3358 gimple_stmt_iterator gsi
= gsi_after_labels (block
);
3359 gsi_insert_before (&gsi
, assign
, GSI_NEW_STMT
);
3361 gimple_set_plf (assign
, NECESSARY
, false);
3362 VN_INFO_GET (temp
)->value_id
= val
;
3363 VN_INFO (temp
)->valnum
= sccvn_valnum_from_value_id (val
);
3364 if (VN_INFO (temp
)->valnum
== NULL_TREE
)
3365 VN_INFO (temp
)->valnum
= temp
;
3366 bitmap_set_bit (inserted_exprs
, SSA_NAME_VERSION (temp
));
3367 pre_expr newe
= get_or_alloc_expr_for_name (temp
);
3368 add_to_value (val
, newe
);
3369 bitmap_value_replace_in_set (AVAIL_OUT (block
), newe
);
3370 bitmap_insert_into_set (NEW_SETS (block
), newe
);
3380 /* Perform insertion for partially anticipatable expressions. There
3381 is only one case we will perform insertion for these. This case is
3382 if the expression is partially anticipatable, and fully available.
3383 In this case, we know that putting it earlier will enable us to
3384 remove the later computation. */
3388 do_partial_partial_insertion (basic_block block
, basic_block dom
)
3390 bool new_stuff
= false;
3391 vec
<pre_expr
> exprs
;
3393 auto_vec
<pre_expr
> avail
;
3396 exprs
= sorted_array_from_bitmap_set (PA_IN (block
));
3397 avail
.safe_grow (EDGE_COUNT (block
->preds
));
3399 FOR_EACH_VEC_ELT (exprs
, i
, expr
)
3401 if (expr
->kind
== NARY
3402 || expr
->kind
== REFERENCE
)
3406 bool cant_insert
= false;
3409 pre_expr eprime
= NULL
;
3412 val
= get_expr_value_id (expr
);
3413 if (bitmap_set_contains_value (PHI_GEN (block
), val
))
3415 if (bitmap_set_contains_value (AVAIL_OUT (dom
), val
))
3418 FOR_EACH_EDGE (pred
, ei
, block
->preds
)
3420 unsigned int vprime
;
3421 pre_expr edoubleprime
;
3423 /* We should never run insertion for the exit block
3424 and so not come across fake pred edges. */
3425 gcc_assert (!(pred
->flags
& EDGE_FAKE
));
3427 eprime
= phi_translate (expr
, ANTIC_IN (block
),
3431 /* eprime will generally only be NULL if the
3432 value of the expression, translated
3433 through the PHI for this predecessor, is
3434 undefined. If that is the case, we can't
3435 make the expression fully redundant,
3436 because its value is undefined along a
3437 predecessor path. We can thus break out
3438 early because it doesn't matter what the
3439 rest of the results are. */
3442 avail
[pred
->dest_idx
] = NULL
;
3447 eprime
= fully_constant_expression (eprime
);
3448 vprime
= get_expr_value_id (eprime
);
3449 edoubleprime
= bitmap_find_leader (AVAIL_OUT (bprime
), vprime
);
3450 avail
[pred
->dest_idx
] = edoubleprime
;
3451 if (edoubleprime
== NULL
)
3458 /* If we can insert it, it's not the same value
3459 already existing along every predecessor, and
3460 it's defined by some predecessor, it is
3461 partially redundant. */
3462 if (!cant_insert
&& by_all
)
3465 bool do_insertion
= false;
3467 /* Insert only if we can remove a later expression on a path
3468 that we want to optimize for speed.
3469 The phi node that we will be inserting in BLOCK is not free,
3470 and inserting it for the sake of !optimize_for_speed successor
3471 may cause regressions on the speed path. */
3472 FOR_EACH_EDGE (succ
, ei
, block
->succs
)
3474 if (bitmap_set_contains_value (PA_IN (succ
->dest
), val
)
3475 || bitmap_set_contains_value (ANTIC_IN (succ
->dest
), val
))
3477 if (optimize_edge_for_speed_p (succ
))
3478 do_insertion
= true;
3484 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3486 fprintf (dump_file
, "Skipping partial partial redundancy "
3488 print_pre_expr (dump_file
, expr
);
3489 fprintf (dump_file
, " (%04d), not (partially) anticipated "
3490 "on any to be optimized for speed edges\n", val
);
3493 else if (dbg_cnt (treepre_insert
))
3495 pre_stats
.pa_insert
++;
3496 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3498 fprintf (dump_file
, "Found partial partial redundancy "
3500 print_pre_expr (dump_file
, expr
);
3501 fprintf (dump_file
, " (%04d)\n",
3502 get_expr_value_id (expr
));
3504 if (insert_into_preds_of_block (block
,
3505 get_expression_id (expr
),
3518 insert_aux (basic_block block
)
3521 bool new_stuff
= false;
3526 dom
= get_immediate_dominator (CDI_DOMINATORS
, block
);
3531 bitmap_set_t newset
= NEW_SETS (dom
);
3534 /* Note that we need to value_replace both NEW_SETS, and
3535 AVAIL_OUT. For both the case of NEW_SETS, the value may be
3536 represented by some non-simple expression here that we want
3537 to replace it with. */
3538 FOR_EACH_EXPR_ID_IN_SET (newset
, i
, bi
)
3540 pre_expr expr
= expression_for_id (i
);
3541 bitmap_value_replace_in_set (NEW_SETS (block
), expr
);
3542 bitmap_value_replace_in_set (AVAIL_OUT (block
), expr
);
3545 if (!single_pred_p (block
))
3547 new_stuff
|= do_regular_insertion (block
, dom
);
3548 if (do_partial_partial
)
3549 new_stuff
|= do_partial_partial_insertion (block
, dom
);
3553 for (son
= first_dom_son (CDI_DOMINATORS
, block
);
3555 son
= next_dom_son (CDI_DOMINATORS
, son
))
3557 new_stuff
|= insert_aux (son
);
3563 /* Perform insertion of partially redundant values. */
3568 bool new_stuff
= true;
3570 int num_iterations
= 0;
3572 FOR_ALL_BB_FN (bb
, cfun
)
3573 NEW_SETS (bb
) = bitmap_set_new ();
3578 if (dump_file
&& dump_flags
& TDF_DETAILS
)
3579 fprintf (dump_file
, "Starting insert iteration %d\n", num_iterations
);
3580 new_stuff
= insert_aux (ENTRY_BLOCK_PTR_FOR_FN (cfun
));
3582 /* Clear the NEW sets before the next iteration. We have already
3583 fully propagated its contents. */
3585 FOR_ALL_BB_FN (bb
, cfun
)
3586 bitmap_set_free (NEW_SETS (bb
));
3588 statistics_histogram_event (cfun
, "insert iterations", num_iterations
);
3592 /* Compute the AVAIL set for all basic blocks.
3594 This function performs value numbering of the statements in each basic
3595 block. The AVAIL sets are built from information we glean while doing
3596 this value numbering, since the AVAIL sets contain only one entry per
3599 AVAIL_IN[BLOCK] = AVAIL_OUT[dom(BLOCK)].
3600 AVAIL_OUT[BLOCK] = AVAIL_IN[BLOCK] U PHI_GEN[BLOCK] U TMP_GEN[BLOCK]. */
3603 compute_avail (void)
3606 basic_block block
, son
;
3607 basic_block
*worklist
;
3611 /* We pretend that default definitions are defined in the entry block.
3612 This includes function arguments and the static chain decl. */
3613 for (i
= 1; i
< num_ssa_names
; ++i
)
3615 tree name
= ssa_name (i
);
3618 || !SSA_NAME_IS_DEFAULT_DEF (name
)
3619 || has_zero_uses (name
)
3620 || virtual_operand_p (name
))
3623 e
= get_or_alloc_expr_for_name (name
);
3624 add_to_value (get_expr_value_id (e
), e
);
3625 bitmap_insert_into_set (TMP_GEN (ENTRY_BLOCK_PTR_FOR_FN (cfun
)), e
);
3626 bitmap_value_insert_into_set (AVAIL_OUT (ENTRY_BLOCK_PTR_FOR_FN (cfun
)),
3630 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3632 print_bitmap_set (dump_file
, TMP_GEN (ENTRY_BLOCK_PTR_FOR_FN (cfun
)),
3633 "tmp_gen", ENTRY_BLOCK
);
3634 print_bitmap_set (dump_file
, AVAIL_OUT (ENTRY_BLOCK_PTR_FOR_FN (cfun
)),
3635 "avail_out", ENTRY_BLOCK
);
3638 /* Allocate the worklist. */
3639 worklist
= XNEWVEC (basic_block
, n_basic_blocks_for_fn (cfun
));
3641 /* Seed the algorithm by putting the dominator children of the entry
3642 block on the worklist. */
3643 for (son
= first_dom_son (CDI_DOMINATORS
, ENTRY_BLOCK_PTR_FOR_FN (cfun
));
3645 son
= next_dom_son (CDI_DOMINATORS
, son
))
3646 worklist
[sp
++] = son
;
3648 BB_LIVE_VOP_ON_EXIT (ENTRY_BLOCK_PTR_FOR_FN (cfun
))
3649 = ssa_default_def (cfun
, gimple_vop (cfun
));
3651 /* Loop until the worklist is empty. */
3657 /* Pick a block from the worklist. */
3658 block
= worklist
[--sp
];
3660 /* Initially, the set of available values in BLOCK is that of
3661 its immediate dominator. */
3662 dom
= get_immediate_dominator (CDI_DOMINATORS
, block
);
3665 bitmap_set_copy (AVAIL_OUT (block
), AVAIL_OUT (dom
));
3666 BB_LIVE_VOP_ON_EXIT (block
) = BB_LIVE_VOP_ON_EXIT (dom
);
3669 /* Generate values for PHI nodes. */
3670 for (gphi_iterator gsi
= gsi_start_phis (block
); !gsi_end_p (gsi
);
3673 tree result
= gimple_phi_result (gsi
.phi ());
3675 /* We have no need for virtual phis, as they don't represent
3676 actual computations. */
3677 if (virtual_operand_p (result
))
3679 BB_LIVE_VOP_ON_EXIT (block
) = result
;
3683 pre_expr e
= get_or_alloc_expr_for_name (result
);
3684 add_to_value (get_expr_value_id (e
), e
);
3685 bitmap_value_insert_into_set (AVAIL_OUT (block
), e
);
3686 bitmap_insert_into_set (PHI_GEN (block
), e
);
3689 BB_MAY_NOTRETURN (block
) = 0;
3691 /* Now compute value numbers and populate value sets with all
3692 the expressions computed in BLOCK. */
3693 for (gimple_stmt_iterator gsi
= gsi_start_bb (block
); !gsi_end_p (gsi
);
3699 stmt
= gsi_stmt (gsi
);
3701 /* Cache whether the basic-block has any non-visible side-effect
3703 If this isn't a call or it is the last stmt in the
3704 basic-block then the CFG represents things correctly. */
3705 if (is_gimple_call (stmt
) && !stmt_ends_bb_p (stmt
))
3707 /* Non-looping const functions always return normally.
3708 Otherwise the call might not return or have side-effects
3709 that forbids hoisting possibly trapping expressions
3711 int flags
= gimple_call_flags (stmt
);
3712 if (!(flags
& ECF_CONST
)
3713 || (flags
& ECF_LOOPING_CONST_OR_PURE
))
3714 BB_MAY_NOTRETURN (block
) = 1;
3717 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, iter
, SSA_OP_DEF
)
3719 pre_expr e
= get_or_alloc_expr_for_name (op
);
3721 add_to_value (get_expr_value_id (e
), e
);
3722 bitmap_insert_into_set (TMP_GEN (block
), e
);
3723 bitmap_value_insert_into_set (AVAIL_OUT (block
), e
);
3726 if (gimple_vdef (stmt
))
3727 BB_LIVE_VOP_ON_EXIT (block
) = gimple_vdef (stmt
);
3729 if (gimple_has_side_effects (stmt
)
3730 || stmt_could_throw_p (stmt
)
3731 || is_gimple_debug (stmt
))
3734 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, iter
, SSA_OP_USE
)
3736 if (ssa_undefined_value_p (op
))
3738 pre_expr e
= get_or_alloc_expr_for_name (op
);
3739 bitmap_value_insert_into_set (EXP_GEN (block
), e
);
3742 switch (gimple_code (stmt
))
3750 vn_reference_s ref1
;
3751 pre_expr result
= NULL
;
3753 /* We can value number only calls to real functions. */
3754 if (gimple_call_internal_p (stmt
))
3757 vn_reference_lookup_call (as_a
<gcall
*> (stmt
), &ref
, &ref1
);
3761 /* If the value of the call is not invalidated in
3762 this block until it is computed, add the expression
3764 if (!gimple_vuse (stmt
)
3766 (SSA_NAME_DEF_STMT (gimple_vuse (stmt
))) == GIMPLE_PHI
3767 || gimple_bb (SSA_NAME_DEF_STMT
3768 (gimple_vuse (stmt
))) != block
)
3770 result
= (pre_expr
) pool_alloc (pre_expr_pool
);
3771 result
->kind
= REFERENCE
;
3773 PRE_EXPR_REFERENCE (result
) = ref
;
3775 get_or_alloc_expression_id (result
);
3776 add_to_value (get_expr_value_id (result
), result
);
3777 bitmap_value_insert_into_set (EXP_GEN (block
), result
);
3784 pre_expr result
= NULL
;
3785 switch (vn_get_stmt_kind (stmt
))
3789 enum tree_code code
= gimple_assign_rhs_code (stmt
);
3792 /* COND_EXPR and VEC_COND_EXPR are awkward in
3793 that they contain an embedded complex expression.
3794 Don't even try to shove those through PRE. */
3795 if (code
== COND_EXPR
3796 || code
== VEC_COND_EXPR
)
3799 vn_nary_op_lookup_stmt (stmt
, &nary
);
3803 /* If the NARY traps and there was a preceding
3804 point in the block that might not return avoid
3805 adding the nary to EXP_GEN. */
3806 if (BB_MAY_NOTRETURN (block
)
3807 && vn_nary_may_trap (nary
))
3810 result
= (pre_expr
) pool_alloc (pre_expr_pool
);
3811 result
->kind
= NARY
;
3813 PRE_EXPR_NARY (result
) = nary
;
3820 vn_reference_lookup (gimple_assign_rhs1 (stmt
),
3826 /* If the value of the reference is not invalidated in
3827 this block until it is computed, add the expression
3829 if (gimple_vuse (stmt
))
3833 def_stmt
= SSA_NAME_DEF_STMT (gimple_vuse (stmt
));
3834 while (!gimple_nop_p (def_stmt
)
3835 && gimple_code (def_stmt
) != GIMPLE_PHI
3836 && gimple_bb (def_stmt
) == block
)
3838 if (stmt_may_clobber_ref_p
3839 (def_stmt
, gimple_assign_rhs1 (stmt
)))
3845 = SSA_NAME_DEF_STMT (gimple_vuse (def_stmt
));
3851 result
= (pre_expr
) pool_alloc (pre_expr_pool
);
3852 result
->kind
= REFERENCE
;
3854 PRE_EXPR_REFERENCE (result
) = ref
;
3862 get_or_alloc_expression_id (result
);
3863 add_to_value (get_expr_value_id (result
), result
);
3864 bitmap_value_insert_into_set (EXP_GEN (block
), result
);
3872 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3874 print_bitmap_set (dump_file
, EXP_GEN (block
),
3875 "exp_gen", block
->index
);
3876 print_bitmap_set (dump_file
, PHI_GEN (block
),
3877 "phi_gen", block
->index
);
3878 print_bitmap_set (dump_file
, TMP_GEN (block
),
3879 "tmp_gen", block
->index
);
3880 print_bitmap_set (dump_file
, AVAIL_OUT (block
),
3881 "avail_out", block
->index
);
3884 /* Put the dominator children of BLOCK on the worklist of blocks
3885 to compute available sets for. */
3886 for (son
= first_dom_son (CDI_DOMINATORS
, block
);
3888 son
= next_dom_son (CDI_DOMINATORS
, son
))
3889 worklist
[sp
++] = son
;
3896 /* Local state for the eliminate domwalk. */
3897 static vec
<gimple
> el_to_remove
;
3898 static unsigned int el_todo
;
3899 static vec
<tree
> el_avail
;
3900 static vec
<tree
> el_avail_stack
;
3902 /* Return a leader for OP that is available at the current point of the
3903 eliminate domwalk. */
3906 eliminate_avail (tree op
)
3908 tree valnum
= VN_INFO (op
)->valnum
;
3909 if (TREE_CODE (valnum
) == SSA_NAME
)
3911 if (SSA_NAME_IS_DEFAULT_DEF (valnum
))
3913 if (el_avail
.length () > SSA_NAME_VERSION (valnum
))
3914 return el_avail
[SSA_NAME_VERSION (valnum
)];
3916 else if (is_gimple_min_invariant (valnum
))
3921 /* At the current point of the eliminate domwalk make OP available. */
3924 eliminate_push_avail (tree op
)
3926 tree valnum
= VN_INFO (op
)->valnum
;
3927 if (TREE_CODE (valnum
) == SSA_NAME
)
3929 if (el_avail
.length () <= SSA_NAME_VERSION (valnum
))
3930 el_avail
.safe_grow_cleared (SSA_NAME_VERSION (valnum
) + 1);
3932 if (el_avail
[SSA_NAME_VERSION (valnum
)])
3933 pushop
= el_avail
[SSA_NAME_VERSION (valnum
)];
3934 el_avail_stack
.safe_push (pushop
);
3935 el_avail
[SSA_NAME_VERSION (valnum
)] = op
;
3939 /* Insert the expression recorded by SCCVN for VAL at *GSI. Returns
3940 the leader for the expression if insertion was successful. */
3943 eliminate_insert (gimple_stmt_iterator
*gsi
, tree val
)
3945 tree expr
= vn_get_expr_for (val
);
3946 if (!CONVERT_EXPR_P (expr
)
3947 && TREE_CODE (expr
) != VIEW_CONVERT_EXPR
)
3950 tree op
= TREE_OPERAND (expr
, 0);
3951 tree leader
= TREE_CODE (op
) == SSA_NAME
? eliminate_avail (op
) : op
;
3955 tree res
= make_temp_ssa_name (TREE_TYPE (val
), NULL
, "pretmp");
3956 gassign
*tem
= gimple_build_assign (res
,
3957 fold_build1 (TREE_CODE (expr
),
3958 TREE_TYPE (expr
), leader
));
3959 gsi_insert_before (gsi
, tem
, GSI_SAME_STMT
);
3960 VN_INFO_GET (res
)->valnum
= val
;
3962 if (TREE_CODE (leader
) == SSA_NAME
)
3963 gimple_set_plf (SSA_NAME_DEF_STMT (leader
), NECESSARY
, true);
3965 pre_stats
.insertions
++;
3966 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3968 fprintf (dump_file
, "Inserted ");
3969 print_gimple_stmt (dump_file
, tem
, 0, 0);
3975 class eliminate_dom_walker
: public dom_walker
3978 eliminate_dom_walker (cdi_direction direction
, bool do_pre_
)
3979 : dom_walker (direction
), do_pre (do_pre_
) {}
3981 virtual void before_dom_children (basic_block
);
3982 virtual void after_dom_children (basic_block
);
3987 /* Perform elimination for the basic-block B during the domwalk. */
3990 eliminate_dom_walker::before_dom_children (basic_block b
)
3993 el_avail_stack
.safe_push (NULL_TREE
);
3995 /* ??? If we do nothing for unreachable blocks then this will confuse
3996 tailmerging. Eventually we can reduce its reliance on SCCVN now
3997 that we fully copy/constant-propagate (most) things. */
3999 for (gphi_iterator gsi
= gsi_start_phis (b
); !gsi_end_p (gsi
);)
4001 gphi
*phi
= gsi
.phi ();
4002 tree res
= PHI_RESULT (phi
);
4004 if (virtual_operand_p (res
))
4010 tree sprime
= eliminate_avail (res
);
4014 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4016 fprintf (dump_file
, "Replaced redundant PHI node defining ");
4017 print_generic_expr (dump_file
, res
, 0);
4018 fprintf (dump_file
, " with ");
4019 print_generic_expr (dump_file
, sprime
, 0);
4020 fprintf (dump_file
, "\n");
4023 /* If we inserted this PHI node ourself, it's not an elimination. */
4025 && bitmap_bit_p (inserted_exprs
, SSA_NAME_VERSION (res
)))
4028 pre_stats
.eliminations
++;
4030 /* If we will propagate into all uses don't bother to do
4032 if (may_propagate_copy (res
, sprime
))
4034 /* Mark the PHI for removal. */
4035 el_to_remove
.safe_push (phi
);
4040 remove_phi_node (&gsi
, false);
4043 && !bitmap_bit_p (inserted_exprs
, SSA_NAME_VERSION (res
))
4044 && TREE_CODE (sprime
) == SSA_NAME
)
4045 gimple_set_plf (SSA_NAME_DEF_STMT (sprime
), NECESSARY
, true);
4047 if (!useless_type_conversion_p (TREE_TYPE (res
), TREE_TYPE (sprime
)))
4048 sprime
= fold_convert (TREE_TYPE (res
), sprime
);
4049 gimple stmt
= gimple_build_assign (res
, sprime
);
4050 /* ??? It cannot yet be necessary (DOM walk). */
4051 gimple_set_plf (stmt
, NECESSARY
, gimple_plf (phi
, NECESSARY
));
4053 gimple_stmt_iterator gsi2
= gsi_after_labels (b
);
4054 gsi_insert_before (&gsi2
, stmt
, GSI_NEW_STMT
);
4058 eliminate_push_avail (res
);
4062 for (gimple_stmt_iterator gsi
= gsi_start_bb (b
);
4066 tree sprime
= NULL_TREE
;
4067 gimple stmt
= gsi_stmt (gsi
);
4068 tree lhs
= gimple_get_lhs (stmt
);
4069 if (lhs
&& TREE_CODE (lhs
) == SSA_NAME
4070 && !gimple_has_volatile_ops (stmt
)
4071 /* See PR43491. Do not replace a global register variable when
4072 it is a the RHS of an assignment. Do replace local register
4073 variables since gcc does not guarantee a local variable will
4074 be allocated in register.
4075 ??? The fix isn't effective here. This should instead
4076 be ensured by not value-numbering them the same but treating
4077 them like volatiles? */
4078 && !(gimple_assign_single_p (stmt
)
4079 && (TREE_CODE (gimple_assign_rhs1 (stmt
)) == VAR_DECL
4080 && DECL_HARD_REGISTER (gimple_assign_rhs1 (stmt
))
4081 && is_global_var (gimple_assign_rhs1 (stmt
)))))
4083 sprime
= eliminate_avail (lhs
);
4086 /* If there is no existing usable leader but SCCVN thinks
4087 it has an expression it wants to use as replacement,
4089 tree val
= VN_INFO (lhs
)->valnum
;
4091 && TREE_CODE (val
) == SSA_NAME
4092 && VN_INFO (val
)->needs_insertion
4093 && VN_INFO (val
)->expr
!= NULL_TREE
4094 && (sprime
= eliminate_insert (&gsi
, val
)) != NULL_TREE
)
4095 eliminate_push_avail (sprime
);
4098 /* If this now constitutes a copy duplicate points-to
4099 and range info appropriately. This is especially
4100 important for inserted code. See tree-ssa-copy.c
4101 for similar code. */
4103 && TREE_CODE (sprime
) == SSA_NAME
)
4105 basic_block sprime_b
= gimple_bb (SSA_NAME_DEF_STMT (sprime
));
4106 if (POINTER_TYPE_P (TREE_TYPE (lhs
))
4107 && SSA_NAME_PTR_INFO (lhs
)
4108 && !SSA_NAME_PTR_INFO (sprime
))
4110 duplicate_ssa_name_ptr_info (sprime
,
4111 SSA_NAME_PTR_INFO (lhs
));
4113 mark_ptr_info_alignment_unknown
4114 (SSA_NAME_PTR_INFO (sprime
));
4116 else if (!POINTER_TYPE_P (TREE_TYPE (lhs
))
4117 && SSA_NAME_RANGE_INFO (lhs
)
4118 && !SSA_NAME_RANGE_INFO (sprime
)
4120 duplicate_ssa_name_range_info (sprime
,
4121 SSA_NAME_RANGE_TYPE (lhs
),
4122 SSA_NAME_RANGE_INFO (lhs
));
4125 /* Inhibit the use of an inserted PHI on a loop header when
4126 the address of the memory reference is a simple induction
4127 variable. In other cases the vectorizer won't do anything
4128 anyway (either it's loop invariant or a complicated
4131 && TREE_CODE (sprime
) == SSA_NAME
4133 && flag_tree_loop_vectorize
4134 && loop_outer (b
->loop_father
)
4135 && has_zero_uses (sprime
)
4136 && bitmap_bit_p (inserted_exprs
, SSA_NAME_VERSION (sprime
))
4137 && gimple_assign_load_p (stmt
))
4139 gimple def_stmt
= SSA_NAME_DEF_STMT (sprime
);
4140 basic_block def_bb
= gimple_bb (def_stmt
);
4141 if (gimple_code (def_stmt
) == GIMPLE_PHI
4142 && b
->loop_father
->header
== def_bb
)
4147 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, iter
, SSA_OP_USE
)
4150 def_bb
= gimple_bb (SSA_NAME_DEF_STMT (op
));
4152 && flow_bb_inside_loop_p (b
->loop_father
, def_bb
)
4153 && simple_iv (b
->loop_father
,
4154 b
->loop_father
, op
, &iv
, true))
4162 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4164 fprintf (dump_file
, "Not replacing ");
4165 print_gimple_expr (dump_file
, stmt
, 0, 0);
4166 fprintf (dump_file
, " with ");
4167 print_generic_expr (dump_file
, sprime
, 0);
4168 fprintf (dump_file
, " which would add a loop"
4169 " carried dependence to loop %d\n",
4170 b
->loop_father
->num
);
4172 /* Don't keep sprime available. */
4180 /* If we can propagate the value computed for LHS into
4181 all uses don't bother doing anything with this stmt. */
4182 if (may_propagate_copy (lhs
, sprime
))
4184 /* Mark it for removal. */
4185 el_to_remove
.safe_push (stmt
);
4187 /* ??? Don't count copy/constant propagations. */
4188 if (gimple_assign_single_p (stmt
)
4189 && (TREE_CODE (gimple_assign_rhs1 (stmt
)) == SSA_NAME
4190 || gimple_assign_rhs1 (stmt
) == sprime
))
4193 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4195 fprintf (dump_file
, "Replaced ");
4196 print_gimple_expr (dump_file
, stmt
, 0, 0);
4197 fprintf (dump_file
, " with ");
4198 print_generic_expr (dump_file
, sprime
, 0);
4199 fprintf (dump_file
, " in all uses of ");
4200 print_gimple_stmt (dump_file
, stmt
, 0, 0);
4203 pre_stats
.eliminations
++;
4207 /* If this is an assignment from our leader (which
4208 happens in the case the value-number is a constant)
4209 then there is nothing to do. */
4210 if (gimple_assign_single_p (stmt
)
4211 && sprime
== gimple_assign_rhs1 (stmt
))
4214 /* Else replace its RHS. */
4215 bool can_make_abnormal_goto
4216 = is_gimple_call (stmt
)
4217 && stmt_can_make_abnormal_goto (stmt
);
4219 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4221 fprintf (dump_file
, "Replaced ");
4222 print_gimple_expr (dump_file
, stmt
, 0, 0);
4223 fprintf (dump_file
, " with ");
4224 print_generic_expr (dump_file
, sprime
, 0);
4225 fprintf (dump_file
, " in ");
4226 print_gimple_stmt (dump_file
, stmt
, 0, 0);
4229 if (TREE_CODE (sprime
) == SSA_NAME
)
4230 gimple_set_plf (SSA_NAME_DEF_STMT (sprime
),
4233 pre_stats
.eliminations
++;
4234 gimple orig_stmt
= stmt
;
4235 if (!useless_type_conversion_p (TREE_TYPE (lhs
),
4236 TREE_TYPE (sprime
)))
4237 sprime
= fold_convert (TREE_TYPE (lhs
), sprime
);
4238 tree vdef
= gimple_vdef (stmt
);
4239 tree vuse
= gimple_vuse (stmt
);
4240 propagate_tree_value_into_stmt (&gsi
, sprime
);
4241 stmt
= gsi_stmt (gsi
);
4243 if (vdef
!= gimple_vdef (stmt
))
4244 VN_INFO (vdef
)->valnum
= vuse
;
4246 /* If we removed EH side-effects from the statement, clean
4247 its EH information. */
4248 if (maybe_clean_or_replace_eh_stmt (orig_stmt
, stmt
))
4250 bitmap_set_bit (need_eh_cleanup
,
4251 gimple_bb (stmt
)->index
);
4252 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4253 fprintf (dump_file
, " Removed EH side-effects.\n");
4256 /* Likewise for AB side-effects. */
4257 if (can_make_abnormal_goto
4258 && !stmt_can_make_abnormal_goto (stmt
))
4260 bitmap_set_bit (need_ab_cleanup
,
4261 gimple_bb (stmt
)->index
);
4262 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4263 fprintf (dump_file
, " Removed AB side-effects.\n");
4270 /* If the statement is a scalar store, see if the expression
4271 has the same value number as its rhs. If so, the store is
4273 if (gimple_assign_single_p (stmt
)
4274 && !gimple_has_volatile_ops (stmt
)
4275 && !is_gimple_reg (gimple_assign_lhs (stmt
))
4276 && (TREE_CODE (gimple_assign_rhs1 (stmt
)) == SSA_NAME
4277 || is_gimple_min_invariant (gimple_assign_rhs1 (stmt
))))
4280 tree rhs
= gimple_assign_rhs1 (stmt
);
4281 val
= vn_reference_lookup (gimple_assign_lhs (stmt
),
4282 gimple_vuse (stmt
), VN_WALK
, NULL
);
4283 if (TREE_CODE (rhs
) == SSA_NAME
)
4284 rhs
= VN_INFO (rhs
)->valnum
;
4286 && operand_equal_p (val
, rhs
, 0))
4288 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4290 fprintf (dump_file
, "Deleted redundant store ");
4291 print_gimple_stmt (dump_file
, stmt
, 0, 0);
4294 /* Queue stmt for removal. */
4295 el_to_remove
.safe_push (stmt
);
4300 bool can_make_abnormal_goto
= stmt_can_make_abnormal_goto (stmt
);
4301 bool was_noreturn
= (is_gimple_call (stmt
)
4302 && gimple_call_noreturn_p (stmt
));
4303 tree vdef
= gimple_vdef (stmt
);
4304 tree vuse
= gimple_vuse (stmt
);
4306 /* If we didn't replace the whole stmt (or propagate the result
4307 into all uses), replace all uses on this stmt with their
4309 use_operand_p use_p
;
4311 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, iter
, SSA_OP_USE
)
4313 tree use
= USE_FROM_PTR (use_p
);
4314 /* ??? The call code above leaves stmt operands un-updated. */
4315 if (TREE_CODE (use
) != SSA_NAME
)
4317 tree sprime
= eliminate_avail (use
);
4318 if (sprime
&& sprime
!= use
4319 && may_propagate_copy (use
, sprime
)
4320 /* We substitute into debug stmts to avoid excessive
4321 debug temporaries created by removed stmts, but we need
4322 to avoid doing so for inserted sprimes as we never want
4323 to create debug temporaries for them. */
4325 || TREE_CODE (sprime
) != SSA_NAME
4326 || !is_gimple_debug (stmt
)
4327 || !bitmap_bit_p (inserted_exprs
, SSA_NAME_VERSION (sprime
))))
4329 propagate_value (use_p
, sprime
);
4330 gimple_set_modified (stmt
, true);
4331 if (TREE_CODE (sprime
) == SSA_NAME
4332 && !is_gimple_debug (stmt
))
4333 gimple_set_plf (SSA_NAME_DEF_STMT (sprime
),
4338 /* Visit indirect calls and turn them into direct calls if
4339 possible using the devirtualization machinery. */
4340 if (gcall
*call_stmt
= dyn_cast
<gcall
*> (stmt
))
4342 tree fn
= gimple_call_fn (call_stmt
);
4344 && flag_devirtualize
4345 && virtual_method_call_p (fn
))
4347 tree otr_type
= obj_type_ref_class (fn
);
4349 ipa_polymorphic_call_context
context (current_function_decl
, fn
, stmt
, &instance
);
4352 context
.get_dynamic_type (instance
, OBJ_TYPE_REF_OBJECT (fn
), otr_type
, stmt
);
4354 vec
<cgraph_node
*>targets
4355 = possible_polymorphic_call_targets (obj_type_ref_class (fn
),
4357 (OBJ_TYPE_REF_TOKEN (fn
)),
4360 if (dump_enabled_p ())
4361 dump_possible_polymorphic_call_targets (dump_file
,
4362 obj_type_ref_class (fn
),
4364 (OBJ_TYPE_REF_TOKEN (fn
)),
4366 if (final
&& targets
.length () <= 1 && dbg_cnt (devirt
))
4369 if (targets
.length () == 1)
4370 fn
= targets
[0]->decl
;
4372 fn
= builtin_decl_implicit (BUILT_IN_UNREACHABLE
);
4373 if (dump_enabled_p ())
4375 location_t loc
= gimple_location_safe (stmt
);
4376 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS
, loc
,
4377 "converting indirect call to "
4379 cgraph_node::get (fn
)->name ());
4381 gimple_call_set_fndecl (call_stmt
, fn
);
4382 gimple_set_modified (stmt
, true);
4387 if (gimple_modified_p (stmt
))
4389 /* If a formerly non-invariant ADDR_EXPR is turned into an
4390 invariant one it was on a separate stmt. */
4391 if (gimple_assign_single_p (stmt
)
4392 && TREE_CODE (gimple_assign_rhs1 (stmt
)) == ADDR_EXPR
)
4393 recompute_tree_invariant_for_addr_expr (gimple_assign_rhs1 (stmt
));
4394 gimple old_stmt
= stmt
;
4395 if (is_gimple_call (stmt
))
4397 /* ??? Only fold calls inplace for now, this may create new
4398 SSA names which in turn will confuse free_scc_vn SSA name
4400 fold_stmt_inplace (&gsi
);
4401 /* When changing a call into a noreturn call, cfg cleanup
4402 is needed to fix up the noreturn call. */
4403 if (!was_noreturn
&& gimple_call_noreturn_p (stmt
))
4404 el_todo
|= TODO_cleanup_cfg
;
4409 stmt
= gsi_stmt (gsi
);
4410 if ((gimple_code (stmt
) == GIMPLE_COND
4411 && (gimple_cond_true_p (as_a
<gcond
*> (stmt
))
4412 || gimple_cond_false_p (as_a
<gcond
*> (stmt
))))
4413 || (gimple_code (stmt
) == GIMPLE_SWITCH
4414 && TREE_CODE (gimple_switch_index (
4415 as_a
<gswitch
*> (stmt
)))
4417 el_todo
|= TODO_cleanup_cfg
;
4419 /* If we removed EH side-effects from the statement, clean
4420 its EH information. */
4421 if (maybe_clean_or_replace_eh_stmt (old_stmt
, stmt
))
4423 bitmap_set_bit (need_eh_cleanup
,
4424 gimple_bb (stmt
)->index
);
4425 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4426 fprintf (dump_file
, " Removed EH side-effects.\n");
4428 /* Likewise for AB side-effects. */
4429 if (can_make_abnormal_goto
4430 && !stmt_can_make_abnormal_goto (stmt
))
4432 bitmap_set_bit (need_ab_cleanup
,
4433 gimple_bb (stmt
)->index
);
4434 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4435 fprintf (dump_file
, " Removed AB side-effects.\n");
4438 if (vdef
!= gimple_vdef (stmt
))
4439 VN_INFO (vdef
)->valnum
= vuse
;
4442 /* Make new values available - for fully redundant LHS we
4443 continue with the next stmt above and skip this. */
4445 FOR_EACH_SSA_DEF_OPERAND (defp
, stmt
, iter
, SSA_OP_DEF
)
4446 eliminate_push_avail (DEF_FROM_PTR (defp
));
4449 /* Replace destination PHI arguments. */
4452 FOR_EACH_EDGE (e
, ei
, b
->succs
)
4454 for (gphi_iterator gsi
= gsi_start_phis (e
->dest
);
4458 gphi
*phi
= gsi
.phi ();
4459 use_operand_p use_p
= PHI_ARG_DEF_PTR_FROM_EDGE (phi
, e
);
4460 tree arg
= USE_FROM_PTR (use_p
);
4461 if (TREE_CODE (arg
) != SSA_NAME
4462 || virtual_operand_p (arg
))
4464 tree sprime
= eliminate_avail (arg
);
4465 if (sprime
&& may_propagate_copy (arg
, sprime
))
4467 propagate_value (use_p
, sprime
);
4468 if (TREE_CODE (sprime
) == SSA_NAME
)
4469 gimple_set_plf (SSA_NAME_DEF_STMT (sprime
), NECESSARY
, true);
4475 /* Make no longer available leaders no longer available. */
4478 eliminate_dom_walker::after_dom_children (basic_block
)
4481 while ((entry
= el_avail_stack
.pop ()) != NULL_TREE
)
4483 tree valnum
= VN_INFO (entry
)->valnum
;
4484 tree old
= el_avail
[SSA_NAME_VERSION (valnum
)];
4486 el_avail
[SSA_NAME_VERSION (valnum
)] = NULL_TREE
;
4488 el_avail
[SSA_NAME_VERSION (valnum
)] = entry
;
4492 /* Eliminate fully redundant computations. */
4495 eliminate (bool do_pre
)
4497 gimple_stmt_iterator gsi
;
4500 need_eh_cleanup
= BITMAP_ALLOC (NULL
);
4501 need_ab_cleanup
= BITMAP_ALLOC (NULL
);
4503 el_to_remove
.create (0);
4505 el_avail
.create (num_ssa_names
);
4506 el_avail_stack
.create (0);
4508 eliminate_dom_walker (CDI_DOMINATORS
,
4509 do_pre
).walk (cfun
->cfg
->x_entry_block_ptr
);
4511 el_avail
.release ();
4512 el_avail_stack
.release ();
4514 /* We cannot remove stmts during BB walk, especially not release SSA
4515 names there as this confuses the VN machinery. The stmts ending
4516 up in el_to_remove are either stores or simple copies.
4517 Remove stmts in reverse order to make debug stmt creation possible. */
4518 while (!el_to_remove
.is_empty ())
4520 stmt
= el_to_remove
.pop ();
4522 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4524 fprintf (dump_file
, "Removing dead stmt ");
4525 print_gimple_stmt (dump_file
, stmt
, 0, 0);
4529 if (gimple_code (stmt
) == GIMPLE_PHI
)
4530 lhs
= gimple_phi_result (stmt
);
4532 lhs
= gimple_get_lhs (stmt
);
4535 && TREE_CODE (lhs
) == SSA_NAME
)
4536 bitmap_clear_bit (inserted_exprs
, SSA_NAME_VERSION (lhs
));
4538 gsi
= gsi_for_stmt (stmt
);
4539 if (gimple_code (stmt
) == GIMPLE_PHI
)
4540 remove_phi_node (&gsi
, true);
4543 basic_block bb
= gimple_bb (stmt
);
4544 unlink_stmt_vdef (stmt
);
4545 if (gsi_remove (&gsi
, true))
4546 bitmap_set_bit (need_eh_cleanup
, bb
->index
);
4547 release_defs (stmt
);
4550 /* Removing a stmt may expose a forwarder block. */
4551 el_todo
|= TODO_cleanup_cfg
;
4553 el_to_remove
.release ();
4558 /* Perform CFG cleanups made necessary by elimination. */
4561 fini_eliminate (void)
4563 bool do_eh_cleanup
= !bitmap_empty_p (need_eh_cleanup
);
4564 bool do_ab_cleanup
= !bitmap_empty_p (need_ab_cleanup
);
4567 gimple_purge_all_dead_eh_edges (need_eh_cleanup
);
4570 gimple_purge_all_dead_abnormal_call_edges (need_ab_cleanup
);
4572 BITMAP_FREE (need_eh_cleanup
);
4573 BITMAP_FREE (need_ab_cleanup
);
4575 if (do_eh_cleanup
|| do_ab_cleanup
)
4576 return TODO_cleanup_cfg
;
4580 /* Borrow a bit of tree-ssa-dce.c for the moment.
4581 XXX: In 4.1, we should be able to just run a DCE pass after PRE, though
4582 this may be a bit faster, and we may want critical edges kept split. */
4584 /* If OP's defining statement has not already been determined to be necessary,
4585 mark that statement necessary. Return the stmt, if it is newly
4588 static inline gimple
4589 mark_operand_necessary (tree op
)
4595 if (TREE_CODE (op
) != SSA_NAME
)
4598 stmt
= SSA_NAME_DEF_STMT (op
);
4601 if (gimple_plf (stmt
, NECESSARY
)
4602 || gimple_nop_p (stmt
))
4605 gimple_set_plf (stmt
, NECESSARY
, true);
4609 /* Because we don't follow exactly the standard PRE algorithm, and decide not
4610 to insert PHI nodes sometimes, and because value numbering of casts isn't
4611 perfect, we sometimes end up inserting dead code. This simple DCE-like
4612 pass removes any insertions we made that weren't actually used. */
4615 remove_dead_inserted_code (void)
4622 worklist
= BITMAP_ALLOC (NULL
);
4623 EXECUTE_IF_SET_IN_BITMAP (inserted_exprs
, 0, i
, bi
)
4625 t
= SSA_NAME_DEF_STMT (ssa_name (i
));
4626 if (gimple_plf (t
, NECESSARY
))
4627 bitmap_set_bit (worklist
, i
);
4629 while (!bitmap_empty_p (worklist
))
4631 i
= bitmap_first_set_bit (worklist
);
4632 bitmap_clear_bit (worklist
, i
);
4633 t
= SSA_NAME_DEF_STMT (ssa_name (i
));
4635 /* PHI nodes are somewhat special in that each PHI alternative has
4636 data and control dependencies. All the statements feeding the
4637 PHI node's arguments are always necessary. */
4638 if (gimple_code (t
) == GIMPLE_PHI
)
4642 for (k
= 0; k
< gimple_phi_num_args (t
); k
++)
4644 tree arg
= PHI_ARG_DEF (t
, k
);
4645 if (TREE_CODE (arg
) == SSA_NAME
)
4647 gimple n
= mark_operand_necessary (arg
);
4649 bitmap_set_bit (worklist
, SSA_NAME_VERSION (arg
));
4655 /* Propagate through the operands. Examine all the USE, VUSE and
4656 VDEF operands in this statement. Mark all the statements
4657 which feed this statement's uses as necessary. */
4661 /* The operands of VDEF expressions are also needed as they
4662 represent potential definitions that may reach this
4663 statement (VDEF operands allow us to follow def-def
4666 FOR_EACH_SSA_TREE_OPERAND (use
, t
, iter
, SSA_OP_ALL_USES
)
4668 gimple n
= mark_operand_necessary (use
);
4670 bitmap_set_bit (worklist
, SSA_NAME_VERSION (use
));
4675 EXECUTE_IF_SET_IN_BITMAP (inserted_exprs
, 0, i
, bi
)
4677 t
= SSA_NAME_DEF_STMT (ssa_name (i
));
4678 if (!gimple_plf (t
, NECESSARY
))
4680 gimple_stmt_iterator gsi
;
4682 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4684 fprintf (dump_file
, "Removing unnecessary insertion:");
4685 print_gimple_stmt (dump_file
, t
, 0, 0);
4688 gsi
= gsi_for_stmt (t
);
4689 if (gimple_code (t
) == GIMPLE_PHI
)
4690 remove_phi_node (&gsi
, true);
4693 gsi_remove (&gsi
, true);
4698 BITMAP_FREE (worklist
);
4702 /* Initialize data structures used by PRE. */
4709 next_expression_id
= 1;
4710 expressions
.create (0);
4711 expressions
.safe_push (NULL
);
4712 value_expressions
.create (get_max_value_id () + 1);
4713 value_expressions
.safe_grow_cleared (get_max_value_id () + 1);
4714 name_to_id
.create (0);
4716 inserted_exprs
= BITMAP_ALLOC (NULL
);
4718 connect_infinite_loops_to_exit ();
4719 memset (&pre_stats
, 0, sizeof (pre_stats
));
4721 postorder
= XNEWVEC (int, n_basic_blocks_for_fn (cfun
));
4722 postorder_num
= inverted_post_order_compute (postorder
);
4724 alloc_aux_for_blocks (sizeof (struct bb_bitmap_sets
));
4726 calculate_dominance_info (CDI_POST_DOMINATORS
);
4727 calculate_dominance_info (CDI_DOMINATORS
);
4729 bitmap_obstack_initialize (&grand_bitmap_obstack
);
4730 phi_translate_table
= new hash_table
<expr_pred_trans_d
> (5110);
4731 expression_to_id
= new hash_table
<pre_expr_d
> (num_ssa_names
* 3);
4732 bitmap_set_pool
= create_alloc_pool ("Bitmap sets",
4733 sizeof (struct bitmap_set
), 30);
4734 pre_expr_pool
= create_alloc_pool ("pre_expr nodes",
4735 sizeof (struct pre_expr_d
), 30);
4736 FOR_ALL_BB_FN (bb
, cfun
)
4738 EXP_GEN (bb
) = bitmap_set_new ();
4739 PHI_GEN (bb
) = bitmap_set_new ();
4740 TMP_GEN (bb
) = bitmap_set_new ();
4741 AVAIL_OUT (bb
) = bitmap_set_new ();
4746 /* Deallocate data structures used by PRE. */
4752 value_expressions
.release ();
4753 BITMAP_FREE (inserted_exprs
);
4754 bitmap_obstack_release (&grand_bitmap_obstack
);
4755 free_alloc_pool (bitmap_set_pool
);
4756 free_alloc_pool (pre_expr_pool
);
4757 delete phi_translate_table
;
4758 phi_translate_table
= NULL
;
4759 delete expression_to_id
;
4760 expression_to_id
= NULL
;
4761 name_to_id
.release ();
4763 free_aux_for_blocks ();
4765 free_dominance_info (CDI_POST_DOMINATORS
);
4770 const pass_data pass_data_pre
=
4772 GIMPLE_PASS
, /* type */
4774 OPTGROUP_NONE
, /* optinfo_flags */
4775 TV_TREE_PRE
, /* tv_id */
4776 /* PROP_no_crit_edges is ensured by placing pass_split_crit_edges before
4778 ( PROP_no_crit_edges
| PROP_cfg
| PROP_ssa
), /* properties_required */
4779 0, /* properties_provided */
4780 PROP_no_crit_edges
, /* properties_destroyed */
4781 TODO_rebuild_alias
, /* todo_flags_start */
4782 0, /* todo_flags_finish */
4785 class pass_pre
: public gimple_opt_pass
4788 pass_pre (gcc::context
*ctxt
)
4789 : gimple_opt_pass (pass_data_pre
, ctxt
)
4792 /* opt_pass methods: */
4793 virtual bool gate (function
*) { return flag_tree_pre
!= 0; }
4794 virtual unsigned int execute (function
*);
4796 }; // class pass_pre
4799 pass_pre::execute (function
*fun
)
4801 unsigned int todo
= 0;
4803 do_partial_partial
=
4804 flag_tree_partial_pre
&& optimize_function_for_speed_p (fun
);
4806 /* This has to happen before SCCVN runs because
4807 loop_optimizer_init may create new phis, etc. */
4808 loop_optimizer_init (LOOPS_NORMAL
);
4810 if (!run_scc_vn (VN_WALK
))
4812 loop_optimizer_finalize ();
4819 /* Collect and value number expressions computed in each basic block. */
4822 /* Insert can get quite slow on an incredibly large number of basic
4823 blocks due to some quadratic behavior. Until this behavior is
4824 fixed, don't run it when he have an incredibly large number of
4825 bb's. If we aren't going to run insert, there is no point in
4826 computing ANTIC, either, even though it's plenty fast. */
4827 if (n_basic_blocks_for_fn (fun
) < 4000)
4833 /* Make sure to remove fake edges before committing our inserts.
4834 This makes sure we don't end up with extra critical edges that
4835 we would need to split. */
4836 remove_fake_exit_edges ();
4837 gsi_commit_edge_inserts ();
4839 /* Eliminate folds statements which might (should not...) end up
4840 not keeping virtual operands up-to-date. */
4841 gcc_assert (!need_ssa_update_p (fun
));
4843 /* Remove all the redundant expressions. */
4844 todo
|= eliminate (true);
4846 statistics_counter_event (fun
, "Insertions", pre_stats
.insertions
);
4847 statistics_counter_event (fun
, "PA inserted", pre_stats
.pa_insert
);
4848 statistics_counter_event (fun
, "New PHIs", pre_stats
.phis
);
4849 statistics_counter_event (fun
, "Eliminated", pre_stats
.eliminations
);
4851 clear_expression_ids ();
4852 remove_dead_inserted_code ();
4856 todo
|= fini_eliminate ();
4857 loop_optimizer_finalize ();
4859 /* TODO: tail_merge_optimize may merge all predecessors of a block, in which
4860 case we can merge the block with the remaining predecessor of the block.
4862 - call merge_blocks after each tail merge iteration
4863 - call merge_blocks after all tail merge iterations
4864 - mark TODO_cleanup_cfg when necessary
4865 - share the cfg cleanup with fini_pre. */
4866 todo
|= tail_merge_optimize (todo
);
4870 /* Tail merging invalidates the virtual SSA web, together with
4871 cfg-cleanup opportunities exposed by PRE this will wreck the
4872 SSA updating machinery. So make sure to run update-ssa
4873 manually, before eventually scheduling cfg-cleanup as part of
4875 update_ssa (TODO_update_ssa_only_virtuals
);
4883 make_pass_pre (gcc::context
*ctxt
)
4885 return new pass_pre (ctxt
);
4890 const pass_data pass_data_fre
=
4892 GIMPLE_PASS
, /* type */
4894 OPTGROUP_NONE
, /* optinfo_flags */
4895 TV_TREE_FRE
, /* tv_id */
4896 ( PROP_cfg
| PROP_ssa
), /* properties_required */
4897 0, /* properties_provided */
4898 0, /* properties_destroyed */
4899 0, /* todo_flags_start */
4900 0, /* todo_flags_finish */
4903 class pass_fre
: public gimple_opt_pass
4906 pass_fre (gcc::context
*ctxt
)
4907 : gimple_opt_pass (pass_data_fre
, ctxt
)
4910 /* opt_pass methods: */
4911 opt_pass
* clone () { return new pass_fre (m_ctxt
); }
4912 virtual bool gate (function
*) { return flag_tree_fre
!= 0; }
4913 virtual unsigned int execute (function
*);
4915 }; // class pass_fre
4918 pass_fre::execute (function
*fun
)
4920 unsigned int todo
= 0;
4922 if (!run_scc_vn (VN_WALKREWRITE
))
4925 memset (&pre_stats
, 0, sizeof (pre_stats
));
4927 /* Remove all the redundant expressions. */
4928 todo
|= eliminate (false);
4930 todo
|= fini_eliminate ();
4934 statistics_counter_event (fun
, "Insertions", pre_stats
.insertions
);
4935 statistics_counter_event (fun
, "Eliminated", pre_stats
.eliminations
);
4943 make_pass_fre (gcc::context
*ctxt
)
4945 return new pass_fre (ctxt
);