2 Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007
3 Free Software Foundation, Inc.
4 Contributed by Daniel Berlin <dan@dberlin.org> and Steven Bosscher
7 This file is part of GCC.
9 GCC is free software; you can redistribute it and/or modify
10 it under the terms of the GNU General Public License as published by
11 the Free Software Foundation; either version 3, or (at your option)
14 GCC is distributed in the hope that it will be useful,
15 but WITHOUT ANY WARRANTY; without even the implied warranty of
16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 GNU General Public License for more details.
19 You should have received a copy of the GNU General Public License
20 along with GCC; see the file COPYING3. If not see
21 <http://www.gnu.org/licenses/>. */
25 #include "coretypes.h"
29 #include "basic-block.h"
30 #include "diagnostic.h"
31 #include "tree-inline.h"
32 #include "tree-flow.h"
33 #include "tree-gimple.h"
34 #include "tree-dump.h"
38 #include "tree-iterator.h"
40 #include "alloc-pool.h"
42 #include "tree-pass.h"
45 #include "langhooks.h"
47 #include "tree-ssa-sccvn.h"
52 1. Avail sets can be shared by making an avail_find_leader that
53 walks up the dominator tree and looks in those avail sets.
54 This might affect code optimality, it's unclear right now.
55 2. Strength reduction can be performed by anticipating expressions
56 we can repair later on.
57 3. We can do back-substitution or smarter value numbering to catch
58 commutative expressions split up over multiple statements.
61 /* For ease of terminology, "expression node" in the below refers to
62 every expression node but GIMPLE_MODIFY_STMT, because GIMPLE_MODIFY_STMT's
63 represent the actual statement containing the expressions we care about,
64 and we cache the value number by putting it in the expression. */
68 First we walk the statements to generate the AVAIL sets, the
69 EXP_GEN sets, and the tmp_gen sets. EXP_GEN sets represent the
70 generation of values/expressions by a given block. We use them
71 when computing the ANTIC sets. The AVAIL sets consist of
72 SSA_NAME's that represent values, so we know what values are
73 available in what blocks. AVAIL is a forward dataflow problem. In
74 SSA, values are never killed, so we don't need a kill set, or a
75 fixpoint iteration, in order to calculate the AVAIL sets. In
76 traditional parlance, AVAIL sets tell us the downsafety of the
79 Next, we generate the ANTIC sets. These sets represent the
80 anticipatable expressions. ANTIC is a backwards dataflow
81 problem. An expression is anticipatable in a given block if it could
82 be generated in that block. This means that if we had to perform
83 an insertion in that block, of the value of that expression, we
84 could. Calculating the ANTIC sets requires phi translation of
85 expressions, because the flow goes backwards through phis. We must
86 iterate to a fixpoint of the ANTIC sets, because we have a kill
87 set. Even in SSA form, values are not live over the entire
88 function, only from their definition point onwards. So we have to
89 remove values from the ANTIC set once we go past the definition
90 point of the leaders that make them up.
91 compute_antic/compute_antic_aux performs this computation.
93 Third, we perform insertions to make partially redundant
94 expressions fully redundant.
96 An expression is partially redundant (excluding partial
99 1. It is AVAIL in some, but not all, of the predecessors of a
101 2. It is ANTIC in all the predecessors.
103 In order to make it fully redundant, we insert the expression into
104 the predecessors where it is not available, but is ANTIC.
106 For the partial anticipation case, we only perform insertion if it
107 is partially anticipated in some block, and fully available in all
110 insert/insert_aux/do_regular_insertion/do_partial_partial_insertion
111 performs these steps.
113 Fourth, we eliminate fully redundant expressions.
114 This is a simple statement walk that replaces redundant
115 calculations with the now available values. */
117 /* Representations of value numbers:
119 Value numbers are represented using the "value handle" approach.
120 This means that each SSA_NAME (and for other reasons to be
121 disclosed in a moment, expression nodes) has a value handle that
122 can be retrieved through get_value_handle. This value handle *is*
123 the value number of the SSA_NAME. You can pointer compare the
124 value handles for equivalence purposes.
126 For debugging reasons, the value handle is internally more than
127 just a number, it is a VALUE_HANDLE named "VH.x", where x is a
128 unique number for each value number in use. This allows
129 expressions with SSA_NAMES replaced by value handles to still be
130 pretty printed in a sane way. They simply print as "VH.3 *
133 Expression nodes have value handles associated with them as a
134 cache. Otherwise, we'd have to look them up again in the hash
135 table This makes significant difference (factor of two or more) on
136 some test cases. They can be thrown away after the pass is
139 /* Representation of expressions on value numbers:
141 In some portions of this code, you will notice we allocate "fake"
142 analogues to the expression we are value numbering, and replace the
143 operands with the values of the expression. Since we work on
144 values, and not just names, we canonicalize expressions to value
145 expressions for use in the ANTIC sets, the EXP_GEN set, etc.
147 This is theoretically unnecessary, it just saves a bunch of
148 repeated get_value_handle and find_leader calls in the remainder of
149 the code, trading off temporary memory usage for speed. The tree
150 nodes aren't actually creating more garbage, since they are
151 allocated in a special pools which are thrown away at the end of
154 All of this also means that if you print the EXP_GEN or ANTIC sets,
155 you will see "VH.5 + VH.7" in the set, instead of "a_55 +
156 b_66" or something. The only thing that actually cares about
157 seeing the value leaders is phi translation, and it needs to be
158 able to find the leader for a value in an arbitrary block, so this
159 "value expression" form is perfect for it (otherwise you'd do
160 get_value_handle->find_leader->translate->get_value_handle->find_leader).*/
163 /* Representation of sets:
165 There are currently two types of sets used, hopefully to be unified soon.
166 The AVAIL sets do not need to be sorted in any particular order,
167 and thus, are simply represented as two bitmaps, one that keeps
168 track of values present in the set, and one that keeps track of
169 expressions present in the set.
171 The other sets are represented as doubly linked lists kept in topological
172 order, with an optional supporting bitmap of values present in the
173 set. The sets represent values, and the elements can be values or
174 expressions. The elements can appear in different sets, but each
175 element can only appear once in each set.
177 Since each node in the set represents a value, we also want to be
178 able to map expression, set pairs to something that tells us
179 whether the value is present is a set. We use a per-set bitmap for
180 that. The value handles also point to a linked list of the
181 expressions they represent via a tree annotation. This is mainly
182 useful only for debugging, since we don't do identity lookups. */
185 /* Next global expression id number. */
186 static unsigned int next_expression_id
;
188 typedef VEC(tree
, gc
) *vuse_vec
;
189 DEF_VEC_P (vuse_vec
);
190 DEF_VEC_ALLOC_P (vuse_vec
, heap
);
192 static VEC(vuse_vec
, heap
) *expression_vuses
;
194 /* Mapping from expression to id number we can use in bitmap sets. */
195 static VEC(tree
, heap
) *expressions
;
197 /* Allocate an expression id for EXPR. */
199 static inline unsigned int
200 alloc_expression_id (tree expr
)
202 tree_ann_common_t ann
;
204 ann
= get_tree_common_ann (expr
);
206 /* Make sure we won't overflow. */
207 gcc_assert (next_expression_id
+ 1 > next_expression_id
);
209 ann
->aux
= XNEW (unsigned int);
210 * ((unsigned int *)ann
->aux
) = next_expression_id
++;
211 VEC_safe_push (tree
, heap
, expressions
, expr
);
212 VEC_safe_push (vuse_vec
, heap
, expression_vuses
, NULL
);
213 return next_expression_id
- 1;
216 /* Return the expression id for tree EXPR. */
218 static inline unsigned int
219 get_expression_id (tree expr
)
221 tree_ann_common_t ann
= tree_common_ann (expr
);
223 gcc_assert (ann
->aux
);
225 return *((unsigned int *)ann
->aux
);
228 /* Return the existing expression id for EXPR, or create one if one
229 does not exist yet. */
231 static inline unsigned int
232 get_or_alloc_expression_id (tree expr
)
234 tree_ann_common_t ann
= tree_common_ann (expr
);
236 if (ann
== NULL
|| !ann
->aux
)
237 return alloc_expression_id (expr
);
239 return get_expression_id (expr
);
242 /* Return the expression that has expression id ID */
245 expression_for_id (unsigned int id
)
247 return VEC_index (tree
, expressions
, id
);
250 /* Return the expression vuses for EXPR, if there are any. */
252 static inline vuse_vec
253 get_expression_vuses (tree expr
)
255 unsigned int expr_id
= get_or_alloc_expression_id (expr
);
256 return VEC_index (vuse_vec
, expression_vuses
, expr_id
);
259 /* Set the expression vuses for EXPR to VUSES. */
262 set_expression_vuses (tree expr
, vuse_vec vuses
)
264 unsigned int expr_id
= get_or_alloc_expression_id (expr
);
265 VEC_replace (vuse_vec
, expression_vuses
, expr_id
, vuses
);
269 /* Free the expression id field in all of our expressions,
270 and then destroy the expressions array. */
273 clear_expression_ids (void)
278 for (i
= 0; VEC_iterate (tree
, expressions
, i
, expr
); i
++)
280 free (tree_common_ann (expr
)->aux
);
281 tree_common_ann (expr
)->aux
= NULL
;
283 VEC_free (tree
, heap
, expressions
);
284 VEC_free (vuse_vec
, heap
, expression_vuses
);
287 static bool in_fre
= false;
289 /* An unordered bitmap set. One bitmap tracks values, the other,
291 typedef struct bitmap_set
297 #define FOR_EACH_EXPR_ID_IN_SET(set, id, bi) \
298 EXECUTE_IF_SET_IN_BITMAP(set->expressions, 0, id, bi)
300 /* Sets that we need to keep track of. */
301 typedef struct bb_bitmap_sets
303 /* The EXP_GEN set, which represents expressions/values generated in
305 bitmap_set_t exp_gen
;
307 /* The PHI_GEN set, which represents PHI results generated in a
309 bitmap_set_t phi_gen
;
311 /* The TMP_GEN set, which represents results/temporaries generated
312 in a basic block. IE the LHS of an expression. */
313 bitmap_set_t tmp_gen
;
315 /* The AVAIL_OUT set, which represents which values are available in
316 a given basic block. */
317 bitmap_set_t avail_out
;
319 /* The ANTIC_IN set, which represents which values are anticipatable
320 in a given basic block. */
321 bitmap_set_t antic_in
;
323 /* The PA_IN set, which represents which values are
324 partially anticipatable in a given basic block. */
327 /* The NEW_SETS set, which is used during insertion to augment the
328 AVAIL_OUT set of blocks with the new insertions performed during
329 the current iteration. */
330 bitmap_set_t new_sets
;
332 /* True if we have visited this block during ANTIC calculation. */
333 unsigned int visited
:1;
335 /* True we have deferred processing this block during ANTIC
336 calculation until its successor is processed. */
337 unsigned int deferred
: 1;
340 #define EXP_GEN(BB) ((bb_value_sets_t) ((BB)->aux))->exp_gen
341 #define PHI_GEN(BB) ((bb_value_sets_t) ((BB)->aux))->phi_gen
342 #define TMP_GEN(BB) ((bb_value_sets_t) ((BB)->aux))->tmp_gen
343 #define AVAIL_OUT(BB) ((bb_value_sets_t) ((BB)->aux))->avail_out
344 #define ANTIC_IN(BB) ((bb_value_sets_t) ((BB)->aux))->antic_in
345 #define PA_IN(BB) ((bb_value_sets_t) ((BB)->aux))->pa_in
346 #define NEW_SETS(BB) ((bb_value_sets_t) ((BB)->aux))->new_sets
347 #define BB_VISITED(BB) ((bb_value_sets_t) ((BB)->aux))->visited
348 #define BB_DEFERRED(BB) ((bb_value_sets_t) ((BB)->aux))->deferred
350 /* Maximal set of values, used to initialize the ANTIC problem, which
351 is an intersection problem. */
352 static bitmap_set_t maximal_set
;
354 /* Basic block list in postorder. */
355 static int *postorder
;
357 /* This structure is used to keep track of statistics on what
358 optimization PRE was able to perform. */
361 /* The number of RHS computations eliminated by PRE. */
364 /* The number of new expressions/temporaries generated by PRE. */
367 /* The number of inserts found due to partial anticipation */
370 /* The number of new PHI nodes added by PRE. */
373 /* The number of values found constant. */
378 static bool do_partial_partial
;
379 static tree
bitmap_find_leader (bitmap_set_t
, tree
, tree
);
380 static void bitmap_value_insert_into_set (bitmap_set_t
, tree
);
381 static void bitmap_value_replace_in_set (bitmap_set_t
, tree
);
382 static void bitmap_set_copy (bitmap_set_t
, bitmap_set_t
);
383 static bool bitmap_set_contains_value (bitmap_set_t
, tree
);
384 static void bitmap_insert_into_set (bitmap_set_t
, tree
);
385 static bitmap_set_t
bitmap_set_new (void);
386 static tree
create_expression_by_pieces (basic_block
, tree
, tree
, tree
);
387 static tree
find_or_generate_expression (basic_block
, tree
, tree
, tree
);
389 /* We can add and remove elements and entries to and from sets
390 and hash tables, so we use alloc pools for them. */
392 static alloc_pool bitmap_set_pool
;
393 static alloc_pool binary_node_pool
;
394 static alloc_pool unary_node_pool
;
395 static alloc_pool reference_node_pool
;
396 static alloc_pool comparison_node_pool
;
397 static bitmap_obstack grand_bitmap_obstack
;
399 /* We can't use allocation pools to hold temporary CALL_EXPR objects, since
400 they are not of fixed size. Instead, use an obstack. */
402 static struct obstack temp_call_expr_obstack
;
405 /* To avoid adding 300 temporary variables when we only need one, we
406 only create one temporary variable, on demand, and build ssa names
407 off that. We do have to change the variable if the types don't
408 match the current variable's type. */
410 static tree storetemp
;
411 static tree prephitemp
;
413 /* Set of blocks with statements that have had its EH information
415 static bitmap need_eh_cleanup
;
417 /* Which expressions have been seen during a given phi translation. */
418 static bitmap seen_during_translate
;
420 /* The phi_translate_table caches phi translations for a given
421 expression and predecessor. */
423 static htab_t phi_translate_table
;
425 /* A three tuple {e, pred, v} used to cache phi translations in the
426 phi_translate_table. */
428 typedef struct expr_pred_trans_d
430 /* The expression. */
433 /* The predecessor block along which we translated the expression. */
436 /* vuses associated with the expression. */
437 VEC (tree
, gc
) *vuses
;
439 /* The value that resulted from the translation. */
442 /* The hashcode for the expression, pred pair. This is cached for
445 } *expr_pred_trans_t
;
446 typedef const struct expr_pred_trans_d
*const_expr_pred_trans_t
;
448 /* Return the hash value for a phi translation table entry. */
451 expr_pred_trans_hash (const void *p
)
453 const_expr_pred_trans_t
const ve
= (const_expr_pred_trans_t
) p
;
457 /* Return true if two phi translation table entries are the same.
458 P1 and P2 should point to the expr_pred_trans_t's to be compared.*/
461 expr_pred_trans_eq (const void *p1
, const void *p2
)
463 const_expr_pred_trans_t
const ve1
= (const_expr_pred_trans_t
) p1
;
464 const_expr_pred_trans_t
const ve2
= (const_expr_pred_trans_t
) p2
;
465 basic_block b1
= ve1
->pred
;
466 basic_block b2
= ve2
->pred
;
470 /* If they are not translations for the same basic block, they can't
476 /* If they are for the same basic block, determine if the
477 expressions are equal. */
478 if (!expressions_equal_p (ve1
->e
, ve2
->e
))
481 /* Make sure the vuses are equivalent. */
482 if (ve1
->vuses
== ve2
->vuses
)
485 if (VEC_length (tree
, ve1
->vuses
) != VEC_length (tree
, ve2
->vuses
))
488 for (i
= 0; VEC_iterate (tree
, ve1
->vuses
, i
, vuse1
); i
++)
490 if (VEC_index (tree
, ve2
->vuses
, i
) != vuse1
)
497 /* Search in the phi translation table for the translation of
498 expression E in basic block PRED with vuses VUSES.
499 Return the translated value, if found, NULL otherwise. */
502 phi_trans_lookup (tree e
, basic_block pred
, VEC (tree
, gc
) *vuses
)
505 struct expr_pred_trans_d ept
;
510 ept
.hashcode
= iterative_hash_expr (e
, (unsigned long) pred
);
511 slot
= htab_find_slot_with_hash (phi_translate_table
, &ept
, ept
.hashcode
,
516 return ((expr_pred_trans_t
) *slot
)->v
;
520 /* Add the tuple mapping from {expression E, basic block PRED, vuses VUSES} to
521 value V, to the phi translation table. */
524 phi_trans_add (tree e
, tree v
, basic_block pred
, VEC (tree
, gc
) *vuses
)
527 expr_pred_trans_t new_pair
= XNEW (struct expr_pred_trans_d
);
529 new_pair
->pred
= pred
;
530 new_pair
->vuses
= vuses
;
532 new_pair
->hashcode
= iterative_hash_expr (e
, (unsigned long) pred
);
533 slot
= htab_find_slot_with_hash (phi_translate_table
, new_pair
,
534 new_pair
->hashcode
, INSERT
);
537 *slot
= (void *) new_pair
;
541 /* Return true if V is a value expression that represents itself.
542 In our world, this is *only* non-value handles. */
545 constant_expr_p (tree v
)
547 return TREE_CODE (v
) != VALUE_HANDLE
&&
548 (TREE_CODE (v
) == FIELD_DECL
|| is_gimple_min_invariant (v
));
551 /* Add expression E to the expression set of value V. */
554 add_to_value (tree v
, tree e
)
556 /* Constants have no expression sets. */
557 if (constant_expr_p (v
))
560 if (VALUE_HANDLE_EXPR_SET (v
) == NULL
)
561 VALUE_HANDLE_EXPR_SET (v
) = bitmap_set_new ();
563 bitmap_insert_into_set (VALUE_HANDLE_EXPR_SET (v
), e
);
566 /* Create a new bitmap set and return it. */
569 bitmap_set_new (void)
571 bitmap_set_t ret
= (bitmap_set_t
) pool_alloc (bitmap_set_pool
);
572 ret
->expressions
= BITMAP_ALLOC (&grand_bitmap_obstack
);
573 ret
->values
= BITMAP_ALLOC (&grand_bitmap_obstack
);
577 /* Remove an expression EXPR from a bitmapped set. */
580 bitmap_remove_from_set (bitmap_set_t set
, tree expr
)
582 tree val
= get_value_handle (expr
);
585 if (!constant_expr_p (val
))
587 bitmap_clear_bit (set
->values
, VALUE_HANDLE_ID (val
));
588 bitmap_clear_bit (set
->expressions
, get_expression_id (expr
));
592 /* Insert an expression EXPR into a bitmapped set. */
595 bitmap_insert_into_set (bitmap_set_t set
, tree expr
)
597 tree val
= get_value_handle (expr
);
600 if (!constant_expr_p (val
))
602 bitmap_set_bit (set
->values
, VALUE_HANDLE_ID (val
));
603 bitmap_set_bit (set
->expressions
, get_or_alloc_expression_id (expr
));
607 /* Copy a bitmapped set ORIG, into bitmapped set DEST. */
610 bitmap_set_copy (bitmap_set_t dest
, bitmap_set_t orig
)
612 bitmap_copy (dest
->expressions
, orig
->expressions
);
613 bitmap_copy (dest
->values
, orig
->values
);
617 /* Free memory used up by SET. */
619 bitmap_set_free (bitmap_set_t set
)
621 BITMAP_FREE (set
->expressions
);
622 BITMAP_FREE (set
->values
);
626 /* A comparison function for use in qsort to top sort a bitmap set. Simply
627 subtracts value handle ids, since they are created in topo-order. */
630 vh_compare (const void *pa
, const void *pb
)
632 const tree vha
= get_value_handle (*((const tree
*)pa
));
633 const tree vhb
= get_value_handle (*((const tree
*)pb
));
635 /* This can happen when we constify things. */
636 if (constant_expr_p (vha
))
638 if (constant_expr_p (vhb
))
642 else if (constant_expr_p (vhb
))
644 return VALUE_HANDLE_ID (vha
) - VALUE_HANDLE_ID (vhb
);
647 /* Generate an topological-ordered array of bitmap set SET. */
649 static VEC(tree
, heap
) *
650 sorted_array_from_bitmap_set (bitmap_set_t set
)
654 VEC(tree
, heap
) *result
= NULL
;
656 FOR_EACH_EXPR_ID_IN_SET (set
, i
, bi
)
657 VEC_safe_push (tree
, heap
, result
, expression_for_id (i
));
659 qsort (VEC_address (tree
, result
), VEC_length (tree
, result
),
660 sizeof (tree
), vh_compare
);
665 /* Perform bitmapped set operation DEST &= ORIG. */
668 bitmap_set_and (bitmap_set_t dest
, bitmap_set_t orig
)
675 bitmap temp
= BITMAP_ALLOC (&grand_bitmap_obstack
);
677 bitmap_and_into (dest
->values
, orig
->values
);
678 bitmap_copy (temp
, dest
->expressions
);
679 EXECUTE_IF_SET_IN_BITMAP (temp
, 0, i
, bi
)
681 tree expr
= expression_for_id (i
);
682 tree val
= get_value_handle (expr
);
683 if (!bitmap_bit_p (dest
->values
, VALUE_HANDLE_ID (val
)))
684 bitmap_clear_bit (dest
->expressions
, i
);
690 /* Subtract all values and expressions contained in ORIG from DEST. */
693 bitmap_set_subtract (bitmap_set_t dest
, bitmap_set_t orig
)
695 bitmap_set_t result
= bitmap_set_new ();
699 bitmap_and_compl (result
->expressions
, dest
->expressions
,
702 FOR_EACH_EXPR_ID_IN_SET (result
, i
, bi
)
704 tree expr
= expression_for_id (i
);
705 tree val
= get_value_handle (expr
);
706 bitmap_set_bit (result
->values
, VALUE_HANDLE_ID (val
));
712 /* Subtract all the values in bitmap set B from bitmap set A. */
715 bitmap_set_subtract_values (bitmap_set_t a
, bitmap_set_t b
)
719 bitmap temp
= BITMAP_ALLOC (&grand_bitmap_obstack
);
721 bitmap_copy (temp
, a
->expressions
);
722 EXECUTE_IF_SET_IN_BITMAP (temp
, 0, i
, bi
)
724 tree expr
= expression_for_id (i
);
725 if (bitmap_set_contains_value (b
, get_value_handle (expr
)))
726 bitmap_remove_from_set (a
, expr
);
732 /* Return true if bitmapped set SET contains the value VAL. */
735 bitmap_set_contains_value (bitmap_set_t set
, tree val
)
737 if (constant_expr_p (val
))
740 if (!set
|| bitmap_empty_p (set
->expressions
))
743 return bitmap_bit_p (set
->values
, VALUE_HANDLE_ID (val
));
747 bitmap_set_contains_expr (bitmap_set_t set
, tree expr
)
749 return bitmap_bit_p (set
->expressions
, get_expression_id (expr
));
752 /* Replace an instance of value LOOKFOR with expression EXPR in SET. */
755 bitmap_set_replace_value (bitmap_set_t set
, tree lookfor
, tree expr
)
757 bitmap_set_t exprset
;
761 if (constant_expr_p (lookfor
))
764 if (!bitmap_set_contains_value (set
, lookfor
))
767 /* The number of expressions having a given value is usually
768 significantly less than the total number of expressions in SET.
769 Thus, rather than check, for each expression in SET, whether it
770 has the value LOOKFOR, we walk the reverse mapping that tells us
771 what expressions have a given value, and see if any of those
772 expressions are in our set. For large testcases, this is about
773 5-10x faster than walking the bitmap. If this is somehow a
774 significant lose for some cases, we can choose which set to walk
775 based on the set size. */
776 exprset
= VALUE_HANDLE_EXPR_SET (lookfor
);
777 FOR_EACH_EXPR_ID_IN_SET (exprset
, i
, bi
)
779 if (bitmap_bit_p (set
->expressions
, i
))
781 bitmap_clear_bit (set
->expressions
, i
);
782 bitmap_set_bit (set
->expressions
, get_expression_id (expr
));
788 /* Return true if two bitmap sets are equal. */
791 bitmap_set_equal (bitmap_set_t a
, bitmap_set_t b
)
793 return bitmap_equal_p (a
->values
, b
->values
);
796 /* Replace an instance of EXPR's VALUE with EXPR in SET if it exists,
797 and add it otherwise. */
800 bitmap_value_replace_in_set (bitmap_set_t set
, tree expr
)
802 tree val
= get_value_handle (expr
);
804 if (bitmap_set_contains_value (set
, val
))
805 bitmap_set_replace_value (set
, val
, expr
);
807 bitmap_insert_into_set (set
, expr
);
810 /* Insert EXPR into SET if EXPR's value is not already present in
814 bitmap_value_insert_into_set (bitmap_set_t set
, tree expr
)
816 tree val
= get_value_handle (expr
);
818 if (constant_expr_p (val
))
821 if (!bitmap_set_contains_value (set
, val
))
822 bitmap_insert_into_set (set
, expr
);
825 /* Print out SET to OUTFILE. */
828 print_bitmap_set (FILE *outfile
, bitmap_set_t set
,
829 const char *setname
, int blockindex
)
831 fprintf (outfile
, "%s[%d] := { ", setname
, blockindex
);
838 FOR_EACH_EXPR_ID_IN_SET (set
, i
, bi
)
840 tree expr
= expression_for_id (i
);
843 fprintf (outfile
, ", ");
845 print_generic_expr (outfile
, expr
, 0);
847 fprintf (outfile
, " (");
848 print_generic_expr (outfile
, get_value_handle (expr
), 0);
849 fprintf (outfile
, ") ");
852 fprintf (outfile
, " }\n");
855 void debug_bitmap_set (bitmap_set_t
);
858 debug_bitmap_set (bitmap_set_t set
)
860 print_bitmap_set (stderr
, set
, "debug", 0);
863 /* Print out the expressions that have VAL to OUTFILE. */
866 print_value_expressions (FILE *outfile
, tree val
)
868 if (VALUE_HANDLE_EXPR_SET (val
))
871 sprintf (s
, "VH.%04d", VALUE_HANDLE_ID (val
));
872 print_bitmap_set (outfile
, VALUE_HANDLE_EXPR_SET (val
), s
, 0);
878 debug_value_expressions (tree val
)
880 print_value_expressions (stderr
, val
);
883 /* Return the folded version of T if T, when folded, is a gimple
884 min_invariant. Otherwise, return T. */
887 fully_constant_expression (tree t
)
891 if (folded
&& is_gimple_min_invariant (folded
))
896 /* Make a temporary copy of a CALL_EXPR object NODE. */
899 temp_copy_call_expr (tree node
)
901 return (tree
) obstack_copy (&temp_call_expr_obstack
, node
, tree_size (node
));
904 /* Translate the vuses in the VUSES vector backwards through phi nodes
905 in PHIBLOCK, so that they have the value they would have in
908 static VEC(tree
, gc
) *
909 translate_vuses_through_block (VEC (tree
, gc
) *vuses
,
910 basic_block phiblock
,
914 VEC(tree
, gc
) *result
= NULL
;
917 for (i
= 0; VEC_iterate (tree
, vuses
, i
, oldvuse
); i
++)
919 tree phi
= SSA_NAME_DEF_STMT (oldvuse
);
920 if (TREE_CODE (phi
) == PHI_NODE
921 && bb_for_stmt (phi
) == phiblock
)
923 edge e
= find_edge (block
, bb_for_stmt (phi
));
926 tree def
= PHI_ARG_DEF (phi
, e
->dest_idx
);
930 result
= VEC_copy (tree
, gc
, vuses
);
931 VEC_replace (tree
, result
, i
, def
);
937 /* We avoid creating a new copy of the vuses unless something
938 actually changed, so result can be NULL. */
948 /* Like find_leader, but checks for the value existing in SET1 *or*
949 SET2. This is used to avoid making a set consisting of the union
950 of PA_IN and ANTIC_IN during insert. */
953 find_leader_in_sets (tree expr
, bitmap_set_t set1
, bitmap_set_t set2
)
957 result
= bitmap_find_leader (set1
, expr
, NULL_TREE
);
959 result
= bitmap_find_leader (set2
, expr
, NULL_TREE
);
963 /* Translate EXPR using phis in PHIBLOCK, so that it has the values of
964 the phis in PRED. SEEN is a bitmap saying which expression we have
965 translated since we started translation of the toplevel expression.
966 Return NULL if we can't find a leader for each part of the
967 translated expression. */
970 phi_translate_1 (tree expr
, bitmap_set_t set1
, bitmap_set_t set2
,
971 basic_block pred
, basic_block phiblock
, bitmap seen
)
973 tree phitrans
= NULL
;
979 if (constant_expr_p (expr
))
982 /* Phi translations of a given expression don't change. */
983 if (EXPR_P (expr
) || GIMPLE_STMT_P (expr
))
985 phitrans
= phi_trans_lookup (expr
, pred
, get_expression_vuses (expr
));
988 phitrans
= phi_trans_lookup (expr
, pred
, NULL
);
993 /* Prevent cycles when we have recursively dependent leaders. This
994 can only happen when phi translating the maximal set. */
997 unsigned int expr_id
= get_expression_id (expr
);
998 if (bitmap_bit_p (seen
, expr_id
))
1000 bitmap_set_bit (seen
, expr_id
);
1003 switch (TREE_CODE_CLASS (TREE_CODE (expr
)))
1005 case tcc_expression
:
1010 if (TREE_CODE (expr
) != CALL_EXPR
)
1014 tree oldfn
= CALL_EXPR_FN (expr
);
1015 tree oldsc
= CALL_EXPR_STATIC_CHAIN (expr
);
1016 tree newfn
, newsc
= NULL
;
1017 tree newexpr
= NULL_TREE
;
1018 bool invariantarg
= false;
1020 VEC (tree
, gc
) *vuses
= get_expression_vuses (expr
);
1021 VEC (tree
, gc
) *tvuses
;
1023 newfn
= phi_translate_1 (find_leader_in_sets (oldfn
, set1
, set2
),
1024 set1
, set2
, pred
, phiblock
, seen
);
1029 newexpr
= temp_copy_call_expr (expr
);
1030 CALL_EXPR_FN (newexpr
) = get_value_handle (newfn
);
1034 newsc
= phi_translate_1 (find_leader_in_sets (oldsc
, set1
, set2
),
1035 set1
, set2
, pred
, phiblock
, seen
);
1041 newexpr
= temp_copy_call_expr (expr
);
1042 CALL_EXPR_STATIC_CHAIN (newexpr
) = get_value_handle (newsc
);
1046 /* phi translate the argument list piece by piece. */
1047 nargs
= call_expr_nargs (expr
);
1048 for (i
= 0; i
< nargs
; i
++)
1050 tree oldval
= CALL_EXPR_ARG (expr
, i
);
1054 /* This may seem like a weird place for this
1055 check, but it's actually the easiest place to
1056 do it. We can't do it lower on in the
1057 recursion because it's valid for pieces of a
1058 component ref to be of AGGREGATE_TYPE, as long
1059 as the outermost one is not.
1060 To avoid *that* case, we have a check for
1061 AGGREGATE_TYPE_P in insert_aux. However, that
1062 check will *not* catch this case because here
1063 it occurs in the argument list. */
1064 if (AGGREGATE_TYPE_P (TREE_TYPE (oldval
)))
1066 oldval
= find_leader_in_sets (oldval
, set1
, set2
);
1067 newval
= phi_translate_1 (oldval
, set1
, set2
, pred
,
1071 if (newval
!= oldval
)
1073 invariantarg
|= is_gimple_min_invariant (newval
);
1075 newexpr
= temp_copy_call_expr (expr
);
1076 CALL_EXPR_ARG (newexpr
, i
) = get_value_handle (newval
);
1081 /* In case of new invariant args we might try to fold the call
1083 if (invariantarg
&& !newsc
)
1085 tree tmp1
= build_call_array (TREE_TYPE (expr
),
1086 newfn
, call_expr_nargs (newexpr
),
1087 CALL_EXPR_ARGP (newexpr
));
1088 tree tmp2
= fold (tmp1
);
1091 STRIP_TYPE_NOPS (tmp2
);
1092 if (is_gimple_min_invariant (tmp2
))
1097 tvuses
= translate_vuses_through_block (vuses
, phiblock
, pred
);
1098 if (vuses
!= tvuses
&& ! newexpr
)
1099 newexpr
= temp_copy_call_expr (expr
);
1103 newexpr
->base
.ann
= NULL
;
1104 vn_lookup_or_add_with_vuses (newexpr
, tvuses
);
1106 set_expression_vuses (newexpr
, tvuses
);
1108 phi_trans_add (oldexpr
, expr
, pred
, tvuses
);
1113 case tcc_declaration
:
1115 VEC (tree
, gc
) * oldvuses
= NULL
;
1116 VEC (tree
, gc
) * newvuses
= NULL
;
1118 oldvuses
= get_expression_vuses (expr
);
1120 newvuses
= translate_vuses_through_block (oldvuses
, phiblock
,
1123 if (oldvuses
!= newvuses
)
1125 vn_lookup_or_add_with_vuses (expr
, newvuses
);
1126 set_expression_vuses (expr
, newvuses
);
1128 phi_trans_add (oldexpr
, expr
, pred
, newvuses
);
1134 tree oldop0
= TREE_OPERAND (expr
, 0);
1143 VEC (tree
, gc
) * oldvuses
= NULL
;
1144 VEC (tree
, gc
) * newvuses
= NULL
;
1146 if (TREE_CODE (expr
) != INDIRECT_REF
1147 && TREE_CODE (expr
) != COMPONENT_REF
1148 && TREE_CODE (expr
) != ARRAY_REF
)
1151 oldop0
= find_leader_in_sets (oldop0
, set1
, set2
);
1152 newop0
= phi_translate_1 (oldop0
, set1
, set2
, pred
, phiblock
, seen
);
1156 if (TREE_CODE (expr
) == ARRAY_REF
)
1158 oldop1
= TREE_OPERAND (expr
, 1);
1159 oldop1
= find_leader_in_sets (oldop1
, set1
, set2
);
1160 newop1
= phi_translate_1 (oldop1
, set1
, set2
, pred
, phiblock
, seen
);
1165 oldop2
= TREE_OPERAND (expr
, 2);
1168 oldop2
= find_leader_in_sets (oldop2
, set1
, set2
);
1169 newop2
= phi_translate_1 (oldop2
, set1
, set2
, pred
, phiblock
, seen
);
1174 oldop3
= TREE_OPERAND (expr
, 3);
1177 oldop3
= find_leader_in_sets (oldop3
, set1
, set2
);
1178 newop3
= phi_translate_1 (oldop3
, set1
, set2
, pred
, phiblock
, seen
);
1185 oldvuses
= get_expression_vuses (expr
);
1187 newvuses
= translate_vuses_through_block (oldvuses
, phiblock
,
1190 if (newop0
!= oldop0
|| newvuses
!= oldvuses
1193 || newop3
!= oldop3
)
1197 newexpr
= (tree
) pool_alloc (reference_node_pool
);
1198 memcpy (newexpr
, expr
, tree_size (expr
));
1199 TREE_OPERAND (newexpr
, 0) = get_value_handle (newop0
);
1200 if (TREE_CODE (expr
) == ARRAY_REF
)
1202 TREE_OPERAND (newexpr
, 1) = get_value_handle (newop1
);
1204 TREE_OPERAND (newexpr
, 2) = get_value_handle (newop2
);
1206 TREE_OPERAND (newexpr
, 3) = get_value_handle (newop3
);
1209 t
= fully_constant_expression (newexpr
);
1213 pool_free (reference_node_pool
, newexpr
);
1218 newexpr
->base
.ann
= NULL
;
1219 vn_lookup_or_add_with_vuses (newexpr
, newvuses
);
1220 set_expression_vuses (newexpr
, newvuses
);
1224 phi_trans_add (oldexpr
, expr
, pred
, newvuses
);
1230 case tcc_comparison
:
1232 tree oldop1
= TREE_OPERAND (expr
, 0);
1233 tree oldval1
= oldop1
;
1234 tree oldop2
= TREE_OPERAND (expr
, 1);
1235 tree oldval2
= oldop2
;
1240 oldop1
= find_leader_in_sets (oldop1
, set1
, set2
);
1241 newop1
= phi_translate_1 (oldop1
, set1
, set2
, pred
, phiblock
, seen
);
1245 oldop2
= find_leader_in_sets (oldop2
, set1
, set2
);
1246 newop2
= phi_translate_1 (oldop2
, set1
, set2
, pred
, phiblock
, seen
);
1249 if (newop1
!= oldop1
|| newop2
!= oldop2
)
1252 newexpr
= (tree
) pool_alloc (binary_node_pool
);
1253 memcpy (newexpr
, expr
, tree_size (expr
));
1254 TREE_OPERAND (newexpr
, 0) = newop1
== oldop1
? oldval1
: get_value_handle (newop1
);
1255 TREE_OPERAND (newexpr
, 1) = newop2
== oldop2
? oldval2
: get_value_handle (newop2
);
1256 t
= fully_constant_expression (newexpr
);
1259 pool_free (binary_node_pool
, newexpr
);
1264 newexpr
->base
.ann
= NULL
;
1265 vn_lookup_or_add (newexpr
);
1269 phi_trans_add (oldexpr
, expr
, pred
, NULL
);
1275 tree oldop1
= TREE_OPERAND (expr
, 0);
1279 oldop1
= find_leader_in_sets (oldop1
, set1
, set2
);
1280 newop1
= phi_translate_1 (oldop1
, set1
, set2
, pred
, phiblock
, seen
);
1283 if (newop1
!= oldop1
)
1286 newexpr
= (tree
) pool_alloc (unary_node_pool
);
1287 memcpy (newexpr
, expr
, tree_size (expr
));
1288 TREE_OPERAND (newexpr
, 0) = get_value_handle (newop1
);
1289 t
= fully_constant_expression (newexpr
);
1292 pool_free (unary_node_pool
, newexpr
);
1297 newexpr
->base
.ann
= NULL
;
1298 vn_lookup_or_add (newexpr
);
1302 phi_trans_add (oldexpr
, expr
, pred
, NULL
);
1306 case tcc_exceptional
:
1311 gcc_assert (TREE_CODE (expr
) == SSA_NAME
);
1313 def_stmt
= SSA_NAME_DEF_STMT (expr
);
1314 if (TREE_CODE (def_stmt
) == PHI_NODE
1315 && bb_for_stmt (def_stmt
) == phiblock
)
1320 e
= find_edge (pred
, bb_for_stmt (phi
));
1324 tree def
= PHI_ARG_DEF (phi
, e
->dest_idx
);
1326 if (is_gimple_min_invariant (def
))
1329 if (TREE_CODE (def
) == SSA_NAME
&& ssa_undefined_value_p (def
))
1332 val
= get_value_handle (def
);
1344 /* Translate EXPR using phis in PHIBLOCK, so that it has the values of
1346 Return NULL if we can't find a leader for each part of the
1347 translated expression. */
1350 phi_translate (tree expr
, bitmap_set_t set1
, bitmap_set_t set2
,
1351 basic_block pred
, basic_block phiblock
)
1353 bitmap_clear (seen_during_translate
);
1354 return phi_translate_1 (expr
, set1
, set2
, pred
, phiblock
,
1355 seen_during_translate
);
1358 /* For each expression in SET, translate the value handles through phi nodes
1359 in PHIBLOCK using edge PHIBLOCK->PRED, and store the resulting
1360 expressions in DEST. */
1363 phi_translate_set (bitmap_set_t dest
, bitmap_set_t set
, basic_block pred
,
1364 basic_block phiblock
)
1366 VEC (tree
, heap
) *exprs
;
1370 if (!phi_nodes (phiblock
))
1372 bitmap_set_copy (dest
, set
);
1376 exprs
= sorted_array_from_bitmap_set (set
);
1377 for (i
= 0; VEC_iterate (tree
, exprs
, i
, expr
); i
++)
1380 translated
= phi_translate (expr
, set
, NULL
, pred
, phiblock
);
1382 /* Don't add constants or empty translations to the cache, since
1383 we won't look them up that way, or use the result, anyway. */
1384 if (translated
&& !is_gimple_min_invariant (translated
))
1386 phi_trans_add (expr
, translated
, pred
,
1387 get_expression_vuses (translated
));
1390 if (translated
!= NULL
)
1391 bitmap_value_insert_into_set (dest
, translated
);
1393 VEC_free (tree
, heap
, exprs
);
1396 /* Find the leader for a value (i.e., the name representing that
1397 value) in a given set, and return it. If STMT is non-NULL it
1398 makes sure the defining statement for the leader dominates it.
1399 Return NULL if no leader is found. */
1402 bitmap_find_leader (bitmap_set_t set
, tree val
, tree stmt
)
1407 if (constant_expr_p (val
))
1410 if (bitmap_set_contains_value (set
, val
))
1412 /* Rather than walk the entire bitmap of expressions, and see
1413 whether any of them has the value we are looking for, we look
1414 at the reverse mapping, which tells us the set of expressions
1415 that have a given value (IE value->expressions with that
1416 value) and see if any of those expressions are in our set.
1417 The number of expressions per value is usually significantly
1418 less than the number of expressions in the set. In fact, for
1419 large testcases, doing it this way is roughly 5-10x faster
1420 than walking the bitmap.
1421 If this is somehow a significant lose for some cases, we can
1422 choose which set to walk based on which set is smaller. */
1425 bitmap_set_t exprset
= VALUE_HANDLE_EXPR_SET (val
);
1427 EXECUTE_IF_AND_IN_BITMAP (exprset
->expressions
,
1428 set
->expressions
, 0, i
, bi
)
1430 tree val
= expression_for_id (i
);
1433 tree def_stmt
= SSA_NAME_DEF_STMT (val
);
1434 if (TREE_CODE (def_stmt
) != PHI_NODE
1435 && bb_for_stmt (def_stmt
) == bb_for_stmt (stmt
)
1436 && stmt_ann (def_stmt
)->uid
>= stmt_ann (stmt
)->uid
)
1445 /* Determine if EXPR, a memory expression, is ANTIC_IN at the top of
1446 BLOCK by seeing if it is not killed in the block. Note that we are
1447 only determining whether there is a store that kills it. Because
1448 of the order in which clean iterates over values, we are guaranteed
1449 that altered operands will have caused us to be eliminated from the
1450 ANTIC_IN set already. */
1453 value_dies_in_block_x (tree expr
, basic_block block
)
1457 VEC (tree
, gc
) *vuses
= get_expression_vuses (expr
);
1459 /* Conservatively, a value dies if it's vuses are defined in this
1460 block, unless they come from phi nodes (which are merge operations,
1461 rather than stores. */
1462 for (i
= 0; VEC_iterate (tree
, vuses
, i
, vuse
); i
++)
1464 tree def
= SSA_NAME_DEF_STMT (vuse
);
1466 if (bb_for_stmt (def
) != block
)
1468 if (TREE_CODE (def
) == PHI_NODE
)
1475 /* Determine if the expression EXPR is valid in SET1 U SET2.
1476 ONLY SET2 CAN BE NULL.
1477 This means that we have a leader for each part of the expression
1478 (if it consists of values), or the expression is an SSA_NAME.
1479 For loads/calls, we also see if the vuses are killed in this block.
1481 NB: We never should run into a case where we have SSA_NAME +
1482 SSA_NAME or SSA_NAME + value. The sets valid_in_sets is called on,
1483 the ANTIC sets, will only ever have SSA_NAME's or value expressions
1484 (IE VALUE1 + VALUE2, *VALUE1, VALUE1 < VALUE2) */
1486 #define union_contains_value(SET1, SET2, VAL) \
1487 (bitmap_set_contains_value ((SET1), (VAL)) \
1488 || ((SET2) && bitmap_set_contains_value ((SET2), (VAL))))
1491 valid_in_sets (bitmap_set_t set1
, bitmap_set_t set2
, tree expr
,
1494 switch (TREE_CODE_CLASS (TREE_CODE (expr
)))
1497 case tcc_comparison
:
1499 tree op1
= TREE_OPERAND (expr
, 0);
1500 tree op2
= TREE_OPERAND (expr
, 1);
1502 return union_contains_value (set1
, set2
, op1
)
1503 && union_contains_value (set1
, set2
, op2
);
1508 tree op1
= TREE_OPERAND (expr
, 0);
1509 return union_contains_value (set1
, set2
, op1
);
1512 case tcc_expression
:
1517 if (TREE_CODE (expr
) == CALL_EXPR
)
1519 tree fn
= CALL_EXPR_FN (expr
);
1520 tree sc
= CALL_EXPR_STATIC_CHAIN (expr
);
1522 call_expr_arg_iterator iter
;
1524 /* Check the non-argument operands first. */
1525 if (!union_contains_value (set1
, set2
, fn
)
1526 || (sc
&& !union_contains_value (set1
, set2
, sc
)))
1529 /* Now check the operands. */
1530 FOR_EACH_CALL_EXPR_ARG (arg
, iter
, expr
)
1532 if (!union_contains_value (set1
, set2
, arg
))
1535 return !value_dies_in_block_x (expr
, block
);
1542 if (TREE_CODE (expr
) == INDIRECT_REF
1543 || TREE_CODE (expr
) == COMPONENT_REF
1544 || TREE_CODE (expr
) == ARRAY_REF
)
1546 tree op0
= TREE_OPERAND (expr
, 0);
1547 gcc_assert (is_gimple_min_invariant (op0
)
1548 || TREE_CODE (op0
) == VALUE_HANDLE
);
1549 if (!union_contains_value (set1
, set2
, op0
))
1551 if (TREE_CODE (expr
) == ARRAY_REF
)
1553 tree op1
= TREE_OPERAND (expr
, 1);
1554 tree op2
= TREE_OPERAND (expr
, 2);
1555 tree op3
= TREE_OPERAND (expr
, 3);
1556 gcc_assert (is_gimple_min_invariant (op1
)
1557 || TREE_CODE (op1
) == VALUE_HANDLE
);
1558 if (!union_contains_value (set1
, set2
, op1
))
1560 gcc_assert (!op2
|| is_gimple_min_invariant (op2
)
1561 || TREE_CODE (op2
) == VALUE_HANDLE
);
1563 && !union_contains_value (set1
, set2
, op2
))
1565 gcc_assert (!op3
|| is_gimple_min_invariant (op3
)
1566 || TREE_CODE (op3
) == VALUE_HANDLE
);
1568 && !union_contains_value (set1
, set2
, op3
))
1571 return !value_dies_in_block_x (expr
, block
);
1576 case tcc_exceptional
:
1578 gcc_assert (TREE_CODE (expr
) == SSA_NAME
);
1579 return bitmap_set_contains_expr (AVAIL_OUT (block
), expr
);
1582 case tcc_declaration
:
1583 return !value_dies_in_block_x (expr
, block
);
1586 /* No other cases should be encountered. */
1591 /* Clean the set of expressions that are no longer valid in SET1 or
1592 SET2. This means expressions that are made up of values we have no
1593 leaders for in SET1 or SET2. This version is used for partial
1594 anticipation, which means it is not valid in either ANTIC_IN or
1598 dependent_clean (bitmap_set_t set1
, bitmap_set_t set2
, basic_block block
)
1600 VEC (tree
, heap
) *exprs
= sorted_array_from_bitmap_set (set1
);
1604 for (i
= 0; VEC_iterate (tree
, exprs
, i
, expr
); i
++)
1606 if (!valid_in_sets (set1
, set2
, expr
, block
))
1607 bitmap_remove_from_set (set1
, expr
);
1609 VEC_free (tree
, heap
, exprs
);
1612 /* Clean the set of expressions that are no longer valid in SET. This
1613 means expressions that are made up of values we have no leaders for
1617 clean (bitmap_set_t set
, basic_block block
)
1619 VEC (tree
, heap
) *exprs
= sorted_array_from_bitmap_set (set
);
1623 for (i
= 0; VEC_iterate (tree
, exprs
, i
, expr
); i
++)
1625 if (!valid_in_sets (set
, NULL
, expr
, block
))
1626 bitmap_remove_from_set (set
, expr
);
1628 VEC_free (tree
, heap
, exprs
);
1631 static sbitmap has_abnormal_preds
;
1633 /* List of blocks that may have changed during ANTIC computation and
1634 thus need to be iterated over. */
1636 static sbitmap changed_blocks
;
1638 /* Decide whether to defer a block for a later iteration, or PHI
1639 translate SOURCE to DEST using phis in PHIBLOCK. Return false if we
1640 should defer the block, and true if we processed it. */
1643 defer_or_phi_translate_block (bitmap_set_t dest
, bitmap_set_t source
,
1644 basic_block block
, basic_block phiblock
)
1646 if (!BB_VISITED (phiblock
))
1648 SET_BIT (changed_blocks
, block
->index
);
1649 BB_VISITED (block
) = 0;
1650 BB_DEFERRED (block
) = 1;
1654 phi_translate_set (dest
, source
, block
, phiblock
);
1658 /* Compute the ANTIC set for BLOCK.
1660 If succs(BLOCK) > 1 then
1661 ANTIC_OUT[BLOCK] = intersection of ANTIC_IN[b] for all succ(BLOCK)
1662 else if succs(BLOCK) == 1 then
1663 ANTIC_OUT[BLOCK] = phi_translate (ANTIC_IN[succ(BLOCK)])
1665 ANTIC_IN[BLOCK] = clean(ANTIC_OUT[BLOCK] U EXP_GEN[BLOCK] - TMP_GEN[BLOCK])
1669 compute_antic_aux (basic_block block
, bool block_has_abnormal_pred_edge
)
1671 bool changed
= false;
1672 bitmap_set_t S
, old
, ANTIC_OUT
;
1678 old
= ANTIC_OUT
= S
= NULL
;
1679 BB_VISITED (block
) = 1;
1681 /* If any edges from predecessors are abnormal, antic_in is empty,
1683 if (block_has_abnormal_pred_edge
)
1684 goto maybe_dump_sets
;
1686 old
= ANTIC_IN (block
);
1687 ANTIC_OUT
= bitmap_set_new ();
1689 /* If the block has no successors, ANTIC_OUT is empty. */
1690 if (EDGE_COUNT (block
->succs
) == 0)
1692 /* If we have one successor, we could have some phi nodes to
1693 translate through. */
1694 else if (single_succ_p (block
))
1696 basic_block succ_bb
= single_succ (block
);
1698 /* We trade iterations of the dataflow equations for having to
1699 phi translate the maximal set, which is incredibly slow
1700 (since the maximal set often has 300+ members, even when you
1701 have a small number of blocks).
1702 Basically, we defer the computation of ANTIC for this block
1703 until we have processed it's successor, which will inevitably
1704 have a *much* smaller set of values to phi translate once
1705 clean has been run on it.
1706 The cost of doing this is that we technically perform more
1707 iterations, however, they are lower cost iterations.
1709 Timings for PRE on tramp3d-v4:
1710 without maximal set fix: 11 seconds
1711 with maximal set fix/without deferring: 26 seconds
1712 with maximal set fix/with deferring: 11 seconds
1715 if (!defer_or_phi_translate_block (ANTIC_OUT
, ANTIC_IN (succ_bb
),
1719 goto maybe_dump_sets
;
1722 /* If we have multiple successors, we take the intersection of all of
1723 them. Note that in the case of loop exit phi nodes, we may have
1724 phis to translate through. */
1727 VEC(basic_block
, heap
) * worklist
;
1729 basic_block bprime
, first
;
1731 worklist
= VEC_alloc (basic_block
, heap
, EDGE_COUNT (block
->succs
));
1732 FOR_EACH_EDGE (e
, ei
, block
->succs
)
1733 VEC_quick_push (basic_block
, worklist
, e
->dest
);
1734 first
= VEC_index (basic_block
, worklist
, 0);
1736 if (phi_nodes (first
))
1738 bitmap_set_t from
= ANTIC_IN (first
);
1740 if (!BB_VISITED (first
))
1742 phi_translate_set (ANTIC_OUT
, from
, block
, first
);
1746 if (!BB_VISITED (first
))
1747 bitmap_set_copy (ANTIC_OUT
, maximal_set
);
1749 bitmap_set_copy (ANTIC_OUT
, ANTIC_IN (first
));
1752 for (i
= 1; VEC_iterate (basic_block
, worklist
, i
, bprime
); i
++)
1754 if (phi_nodes (bprime
))
1756 bitmap_set_t tmp
= bitmap_set_new ();
1757 bitmap_set_t from
= ANTIC_IN (bprime
);
1759 if (!BB_VISITED (bprime
))
1761 phi_translate_set (tmp
, from
, block
, bprime
);
1762 bitmap_set_and (ANTIC_OUT
, tmp
);
1763 bitmap_set_free (tmp
);
1767 if (!BB_VISITED (bprime
))
1768 bitmap_set_and (ANTIC_OUT
, maximal_set
);
1770 bitmap_set_and (ANTIC_OUT
, ANTIC_IN (bprime
));
1773 VEC_free (basic_block
, heap
, worklist
);
1776 /* Generate ANTIC_OUT - TMP_GEN. */
1777 S
= bitmap_set_subtract (ANTIC_OUT
, TMP_GEN (block
));
1779 /* Start ANTIC_IN with EXP_GEN - TMP_GEN. */
1780 ANTIC_IN (block
) = bitmap_set_subtract (EXP_GEN (block
),
1783 /* Then union in the ANTIC_OUT - TMP_GEN values,
1784 to get ANTIC_OUT U EXP_GEN - TMP_GEN */
1785 FOR_EACH_EXPR_ID_IN_SET (S
, bii
, bi
)
1786 bitmap_value_insert_into_set (ANTIC_IN (block
),
1787 expression_for_id (bii
));
1789 clean (ANTIC_IN (block
), block
);
1791 /* !old->expressions can happen when we deferred a block. */
1792 if (!old
->expressions
|| !bitmap_set_equal (old
, ANTIC_IN (block
)))
1795 SET_BIT (changed_blocks
, block
->index
);
1796 FOR_EACH_EDGE (e
, ei
, block
->preds
)
1797 SET_BIT (changed_blocks
, e
->src
->index
);
1800 RESET_BIT (changed_blocks
, block
->index
);
1803 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1805 if (!BB_DEFERRED (block
) || BB_VISITED (block
))
1808 print_bitmap_set (dump_file
, ANTIC_OUT
, "ANTIC_OUT", block
->index
);
1810 print_bitmap_set (dump_file
, ANTIC_IN (block
), "ANTIC_IN",
1814 print_bitmap_set (dump_file
, S
, "S", block
->index
);
1819 "Block %d was deferred for a future iteration.\n",
1824 bitmap_set_free (old
);
1826 bitmap_set_free (S
);
1828 bitmap_set_free (ANTIC_OUT
);
1832 /* Compute PARTIAL_ANTIC for BLOCK.
1834 If succs(BLOCK) > 1 then
1835 PA_OUT[BLOCK] = value wise union of PA_IN[b] + all ANTIC_IN not
1836 in ANTIC_OUT for all succ(BLOCK)
1837 else if succs(BLOCK) == 1 then
1838 PA_OUT[BLOCK] = phi_translate (PA_IN[succ(BLOCK)])
1840 PA_IN[BLOCK] = dependent_clean(PA_OUT[BLOCK] - TMP_GEN[BLOCK]
1845 compute_partial_antic_aux (basic_block block
,
1846 bool block_has_abnormal_pred_edge
)
1848 bool changed
= false;
1849 bitmap_set_t old_PA_IN
;
1850 bitmap_set_t PA_OUT
;
1853 unsigned long max_pa
= PARAM_VALUE (PARAM_MAX_PARTIAL_ANTIC_LENGTH
);
1855 old_PA_IN
= PA_OUT
= NULL
;
1857 /* If any edges from predecessors are abnormal, antic_in is empty,
1859 if (block_has_abnormal_pred_edge
)
1860 goto maybe_dump_sets
;
1862 /* If there are too many partially anticipatable values in the
1863 block, phi_translate_set can take an exponential time: stop
1864 before the translation starts. */
1866 && single_succ_p (block
)
1867 && bitmap_count_bits (PA_IN (single_succ (block
))->values
) > max_pa
)
1868 goto maybe_dump_sets
;
1870 old_PA_IN
= PA_IN (block
);
1871 PA_OUT
= bitmap_set_new ();
1873 /* If the block has no successors, ANTIC_OUT is empty. */
1874 if (EDGE_COUNT (block
->succs
) == 0)
1876 /* If we have one successor, we could have some phi nodes to
1877 translate through. Note that we can't phi translate across DFS
1878 back edges in partial antic, because it uses a union operation on
1879 the successors. For recurrences like IV's, we will end up
1880 generating a new value in the set on each go around (i + 3 (VH.1)
1881 VH.1 + 1 (VH.2), VH.2 + 1 (VH.3), etc), forever. */
1882 else if (single_succ_p (block
))
1884 basic_block succ
= single_succ (block
);
1885 if (!(single_succ_edge (block
)->flags
& EDGE_DFS_BACK
))
1886 phi_translate_set (PA_OUT
, PA_IN (succ
), block
, succ
);
1888 /* If we have multiple successors, we take the union of all of
1892 VEC(basic_block
, heap
) * worklist
;
1896 worklist
= VEC_alloc (basic_block
, heap
, EDGE_COUNT (block
->succs
));
1897 FOR_EACH_EDGE (e
, ei
, block
->succs
)
1899 if (e
->flags
& EDGE_DFS_BACK
)
1901 VEC_quick_push (basic_block
, worklist
, e
->dest
);
1903 if (VEC_length (basic_block
, worklist
) > 0)
1905 for (i
= 0; VEC_iterate (basic_block
, worklist
, i
, bprime
); i
++)
1910 FOR_EACH_EXPR_ID_IN_SET (ANTIC_IN (bprime
), i
, bi
)
1911 bitmap_value_insert_into_set (PA_OUT
,
1912 expression_for_id (i
));
1913 if (phi_nodes (bprime
))
1915 bitmap_set_t pa_in
= bitmap_set_new ();
1916 phi_translate_set (pa_in
, PA_IN (bprime
), block
, bprime
);
1917 FOR_EACH_EXPR_ID_IN_SET (pa_in
, i
, bi
)
1918 bitmap_value_insert_into_set (PA_OUT
,
1919 expression_for_id (i
));
1920 bitmap_set_free (pa_in
);
1923 FOR_EACH_EXPR_ID_IN_SET (PA_IN (bprime
), i
, bi
)
1924 bitmap_value_insert_into_set (PA_OUT
,
1925 expression_for_id (i
));
1928 VEC_free (basic_block
, heap
, worklist
);
1931 /* PA_IN starts with PA_OUT - TMP_GEN.
1932 Then we subtract things from ANTIC_IN. */
1933 PA_IN (block
) = bitmap_set_subtract (PA_OUT
, TMP_GEN (block
));
1935 /* For partial antic, we want to put back in the phi results, since
1936 we will properly avoid making them partially antic over backedges. */
1937 bitmap_ior_into (PA_IN (block
)->values
, PHI_GEN (block
)->values
);
1938 bitmap_ior_into (PA_IN (block
)->expressions
, PHI_GEN (block
)->expressions
);
1940 /* PA_IN[block] = PA_IN[block] - ANTIC_IN[block] */
1941 bitmap_set_subtract_values (PA_IN (block
), ANTIC_IN (block
));
1943 dependent_clean (PA_IN (block
), ANTIC_IN (block
), block
);
1945 if (!bitmap_set_equal (old_PA_IN
, PA_IN (block
)))
1948 SET_BIT (changed_blocks
, block
->index
);
1949 FOR_EACH_EDGE (e
, ei
, block
->preds
)
1950 SET_BIT (changed_blocks
, e
->src
->index
);
1953 RESET_BIT (changed_blocks
, block
->index
);
1956 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1959 print_bitmap_set (dump_file
, PA_OUT
, "PA_OUT", block
->index
);
1961 print_bitmap_set (dump_file
, PA_IN (block
), "PA_IN", block
->index
);
1964 bitmap_set_free (old_PA_IN
);
1966 bitmap_set_free (PA_OUT
);
1970 /* Compute ANTIC and partial ANTIC sets. */
1973 compute_antic (void)
1975 bool changed
= true;
1976 int num_iterations
= 0;
1980 /* If any predecessor edges are abnormal, we punt, so antic_in is empty.
1981 We pre-build the map of blocks with incoming abnormal edges here. */
1982 has_abnormal_preds
= sbitmap_alloc (last_basic_block
);
1983 sbitmap_zero (has_abnormal_preds
);
1990 FOR_EACH_EDGE (e
, ei
, block
->preds
)
1992 e
->flags
&= ~EDGE_DFS_BACK
;
1993 if (e
->flags
& EDGE_ABNORMAL
)
1995 SET_BIT (has_abnormal_preds
, block
->index
);
2000 BB_VISITED (block
) = 0;
2001 BB_DEFERRED (block
) = 0;
2002 /* While we are here, give empty ANTIC_IN sets to each block. */
2003 ANTIC_IN (block
) = bitmap_set_new ();
2004 PA_IN (block
) = bitmap_set_new ();
2007 /* At the exit block we anticipate nothing. */
2008 ANTIC_IN (EXIT_BLOCK_PTR
) = bitmap_set_new ();
2009 BB_VISITED (EXIT_BLOCK_PTR
) = 1;
2010 PA_IN (EXIT_BLOCK_PTR
) = bitmap_set_new ();
2012 changed_blocks
= sbitmap_alloc (last_basic_block
+ 1);
2013 sbitmap_ones (changed_blocks
);
2016 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2017 fprintf (dump_file
, "Starting iteration %d\n", num_iterations
);
2020 for (i
= 0; i
< last_basic_block
- NUM_FIXED_BLOCKS
; i
++)
2022 if (TEST_BIT (changed_blocks
, postorder
[i
]))
2024 basic_block block
= BASIC_BLOCK (postorder
[i
]);
2025 changed
|= compute_antic_aux (block
,
2026 TEST_BIT (has_abnormal_preds
,
2030 /* Theoretically possible, but *highly* unlikely. */
2031 gcc_assert (num_iterations
< 50);
2034 statistics_histogram_event (cfun
, "compute_antic iterations",
2037 if (do_partial_partial
)
2039 sbitmap_ones (changed_blocks
);
2040 mark_dfs_back_edges ();
2045 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2046 fprintf (dump_file
, "Starting iteration %d\n", num_iterations
);
2049 for (i
= 0; i
< last_basic_block
- NUM_FIXED_BLOCKS
; i
++)
2051 if (TEST_BIT (changed_blocks
, postorder
[i
]))
2053 basic_block block
= BASIC_BLOCK (postorder
[i
]);
2055 |= compute_partial_antic_aux (block
,
2056 TEST_BIT (has_abnormal_preds
,
2060 /* Theoretically possible, but *highly* unlikely. */
2061 gcc_assert (num_iterations
< 50);
2063 statistics_histogram_event (cfun
, "compute_partial_antic iterations",
2066 sbitmap_free (has_abnormal_preds
);
2067 sbitmap_free (changed_blocks
);
2070 /* Return true if we can value number the call in STMT. This is true
2071 if we have a pure or constant call. */
2074 can_value_number_call (tree stmt
)
2076 tree call
= get_call_expr_in (stmt
);
2078 if (call_expr_flags (call
) & (ECF_PURE
| ECF_CONST
))
2083 /* Return true if OP is an exception handler related operation, such as
2084 FILTER_EXPR or EXC_PTR_EXPR. */
2087 is_exception_related (tree op
)
2089 return TREE_CODE (op
) == FILTER_EXPR
|| TREE_CODE (op
) == EXC_PTR_EXPR
;
2092 /* Return true if OP is a tree which we can perform value numbering
2096 can_value_number_operation (tree op
)
2098 return (UNARY_CLASS_P (op
)
2099 && !is_exception_related (TREE_OPERAND (op
, 0)))
2100 || BINARY_CLASS_P (op
)
2101 || COMPARISON_CLASS_P (op
)
2102 || REFERENCE_CLASS_P (op
)
2103 || (TREE_CODE (op
) == CALL_EXPR
2104 && can_value_number_call (op
));
2108 /* Return true if OP is a tree which we can perform PRE on
2109 on. This may not match the operations we can value number, but in
2110 a perfect world would. */
2113 can_PRE_operation (tree op
)
2115 return UNARY_CLASS_P (op
)
2116 || BINARY_CLASS_P (op
)
2117 || COMPARISON_CLASS_P (op
)
2118 || TREE_CODE (op
) == INDIRECT_REF
2119 || TREE_CODE (op
) == COMPONENT_REF
2120 || TREE_CODE (op
) == VIEW_CONVERT_EXPR
2121 || TREE_CODE (op
) == CALL_EXPR
2122 || TREE_CODE (op
) == ARRAY_REF
;
2126 /* Inserted expressions are placed onto this worklist, which is used
2127 for performing quick dead code elimination of insertions we made
2128 that didn't turn out to be necessary. */
2129 static VEC(tree
,heap
) *inserted_exprs
;
2131 /* Pool allocated fake store expressions are placed onto this
2132 worklist, which, after performing dead code elimination, is walked
2133 to see which expressions need to be put into GC'able memory */
2134 static VEC(tree
, heap
) *need_creation
;
2136 /* For COMPONENT_REF's and ARRAY_REF's, we can't have any intermediates for the
2137 COMPONENT_REF or INDIRECT_REF or ARRAY_REF portion, because we'd end up with
2138 trying to rename aggregates into ssa form directly, which is a no
2141 Thus, this routine doesn't create temporaries, it just builds a
2142 single access expression for the array, calling
2143 find_or_generate_expression to build the innermost pieces.
2145 This function is a subroutine of create_expression_by_pieces, and
2146 should not be called on it's own unless you really know what you
2150 create_component_ref_by_pieces (basic_block block
, tree expr
, tree stmts
,
2156 if (TREE_CODE (genop
) == VALUE_HANDLE
)
2158 tree found
= bitmap_find_leader (AVAIL_OUT (block
), expr
, domstmt
);
2163 if (TREE_CODE (genop
) == VALUE_HANDLE
)
2165 bitmap_set_t exprset
= VALUE_HANDLE_EXPR_SET (expr
);
2166 unsigned int firstbit
= bitmap_first_set_bit (exprset
->expressions
);
2167 genop
= expression_for_id (firstbit
);
2170 switch TREE_CODE (genop
)
2176 op0
= create_component_ref_by_pieces (block
,
2177 TREE_OPERAND (genop
, 0),
2179 op1
= TREE_OPERAND (genop
, 1);
2180 if (TREE_CODE (op1
) == VALUE_HANDLE
)
2181 op1
= find_or_generate_expression (block
, op1
, stmts
, domstmt
);
2182 op2
= TREE_OPERAND (genop
, 2);
2183 if (op2
&& TREE_CODE (op2
) == VALUE_HANDLE
)
2184 op2
= find_or_generate_expression (block
, op2
, stmts
, domstmt
);
2185 op3
= TREE_OPERAND (genop
, 3);
2186 if (op3
&& TREE_CODE (op3
) == VALUE_HANDLE
)
2187 op3
= find_or_generate_expression (block
, op3
, stmts
, domstmt
);
2190 folded
= build4 (ARRAY_REF
, TREE_TYPE (genop
), op0
, op1
,
2198 op0
= create_component_ref_by_pieces (block
,
2199 TREE_OPERAND (genop
, 0),
2203 /* op1 should be a FIELD_DECL, which are represented by
2205 op1
= TREE_OPERAND (genop
, 1);
2206 folded
= fold_build3 (COMPONENT_REF
, TREE_TYPE (genop
), op0
, op1
,
2213 tree op1
= TREE_OPERAND (genop
, 0);
2214 tree genop1
= find_or_generate_expression (block
, op1
, stmts
, domstmt
);
2218 folded
= fold_build1 (TREE_CODE (genop
), TREE_TYPE (genop
),
2236 /* Find a leader for an expression, or generate one using
2237 create_expression_by_pieces if it's ANTIC but
2239 BLOCK is the basic_block we are looking for leaders in.
2240 EXPR is the expression to find a leader or generate for.
2241 STMTS is the statement list to put the inserted expressions on.
2242 Returns the SSA_NAME of the LHS of the generated expression or the
2244 DOMSTMT if non-NULL is a statement that should be dominated by
2245 all uses in the generated expression. If DOMSTMT is non-NULL this
2246 routine can fail and return NULL_TREE. Otherwise it will assert
2250 find_or_generate_expression (basic_block block
, tree expr
, tree stmts
,
2253 tree genop
= bitmap_find_leader (AVAIL_OUT (block
), expr
, domstmt
);
2255 /* If it's still NULL, it must be a complex expression, so generate
2259 bitmap_set_t exprset
= VALUE_HANDLE_EXPR_SET (expr
);
2260 bool handled
= false;
2264 /* We will hit cases where we have SSA_NAME's in exprset before
2265 other operations, because we may have come up with the SCCVN
2266 value before getting to the RHS of the expression. */
2267 FOR_EACH_EXPR_ID_IN_SET (exprset
, i
, bi
)
2269 genop
= expression_for_id (i
);
2270 if (can_PRE_operation (genop
))
2273 genop
= create_expression_by_pieces (block
, genop
, stmts
,
2278 if (!handled
&& domstmt
)
2281 gcc_assert (handled
);
2286 #define NECESSARY(stmt) stmt->base.asm_written_flag
2287 /* Create an expression in pieces, so that we can handle very complex
2288 expressions that may be ANTIC, but not necessary GIMPLE.
2289 BLOCK is the basic block the expression will be inserted into,
2290 EXPR is the expression to insert (in value form)
2291 STMTS is a statement list to append the necessary insertions into.
2293 This function will die if we hit some value that shouldn't be
2294 ANTIC but is (IE there is no leader for it, or its components).
2295 This function may also generate expressions that are themselves
2296 partially or fully redundant. Those that are will be either made
2297 fully redundant during the next iteration of insert (for partially
2298 redundant ones), or eliminated by eliminate (for fully redundant
2301 If DOMSTMT is non-NULL then we make sure that all uses in the
2302 expressions dominate that statement. In this case the function
2303 can return NULL_TREE to signal failure. */
2306 create_expression_by_pieces (basic_block block
, tree expr
, tree stmts
,
2310 tree folded
, forced_stmts
, newexpr
;
2312 tree_stmt_iterator tsi
;
2314 switch (TREE_CODE_CLASS (TREE_CODE (expr
)))
2323 gcc_assert (TREE_CODE (expr
) == CALL_EXPR
);
2325 fn
= CALL_EXPR_FN (expr
);
2326 sc
= CALL_EXPR_STATIC_CHAIN (expr
);
2328 genfn
= find_or_generate_expression (block
, fn
, stmts
, domstmt
);
2332 nargs
= call_expr_nargs (expr
);
2333 buffer
= (tree
*) alloca (nargs
* sizeof (tree
));
2335 for (i
= 0; i
< nargs
; i
++)
2337 tree arg
= CALL_EXPR_ARG (expr
, i
);
2338 buffer
[i
] = find_or_generate_expression (block
, arg
, stmts
,
2344 folded
= build_call_array (TREE_TYPE (expr
), genfn
, nargs
, buffer
);
2347 CALL_EXPR_STATIC_CHAIN (folded
) =
2348 find_or_generate_expression (block
, sc
, stmts
, domstmt
);
2349 if (!CALL_EXPR_STATIC_CHAIN (folded
))
2352 folded
= fold (folded
);
2358 if (TREE_CODE (expr
) == COMPONENT_REF
2359 || TREE_CODE (expr
) == ARRAY_REF
)
2361 folded
= create_component_ref_by_pieces (block
, expr
, stmts
,
2368 tree op1
= TREE_OPERAND (expr
, 0);
2369 tree genop1
= find_or_generate_expression (block
, op1
, stmts
,
2374 folded
= fold_build1 (TREE_CODE (expr
), TREE_TYPE (expr
),
2381 case tcc_comparison
:
2383 tree op1
= TREE_OPERAND (expr
, 0);
2384 tree op2
= TREE_OPERAND (expr
, 1);
2385 tree genop1
= find_or_generate_expression (block
, op1
, stmts
, domstmt
);
2386 tree genop2
= find_or_generate_expression (block
, op2
, stmts
, domstmt
);
2387 if (!genop1
|| !genop2
)
2389 folded
= fold_build2 (TREE_CODE (expr
), TREE_TYPE (expr
),
2396 tree op1
= TREE_OPERAND (expr
, 0);
2397 tree genop1
= find_or_generate_expression (block
, op1
, stmts
, domstmt
);
2400 folded
= fold_build1 (TREE_CODE (expr
), TREE_TYPE (expr
),
2409 /* Force the generated expression to be a sequence of GIMPLE
2411 We have to call unshare_expr because force_gimple_operand may
2412 modify the tree we pass to it. */
2413 newexpr
= force_gimple_operand (unshare_expr (folded
), &forced_stmts
,
2416 /* If we have any intermediate expressions to the value sets, add them
2417 to the value sets and chain them on in the instruction stream. */
2420 tsi
= tsi_start (forced_stmts
);
2421 for (; !tsi_end_p (tsi
); tsi_next (&tsi
))
2423 tree stmt
= tsi_stmt (tsi
);
2424 tree forcedname
= GIMPLE_STMT_OPERAND (stmt
, 0);
2425 tree forcedexpr
= GIMPLE_STMT_OPERAND (stmt
, 1);
2426 tree val
= vn_lookup_or_add (forcedexpr
);
2428 VEC_safe_push (tree
, heap
, inserted_exprs
, stmt
);
2429 VN_INFO_GET (forcedname
)->valnum
= forcedname
;
2430 vn_add (forcedname
, val
);
2431 bitmap_value_replace_in_set (NEW_SETS (block
), forcedname
);
2432 bitmap_value_replace_in_set (AVAIL_OUT (block
), forcedname
);
2433 mark_symbols_for_renaming (stmt
);
2435 tsi
= tsi_last (stmts
);
2436 tsi_link_after (&tsi
, forced_stmts
, TSI_CONTINUE_LINKING
);
2439 /* Build and insert the assignment of the end result to the temporary
2440 that we will return. */
2441 if (!pretemp
|| TREE_TYPE (expr
) != TREE_TYPE (pretemp
))
2443 pretemp
= create_tmp_var (TREE_TYPE (expr
), "pretmp");
2444 get_var_ann (pretemp
);
2448 add_referenced_var (temp
);
2450 if (TREE_CODE (TREE_TYPE (expr
)) == COMPLEX_TYPE
2451 || TREE_CODE (TREE_TYPE (expr
)) == VECTOR_TYPE
)
2452 DECL_GIMPLE_REG_P (temp
) = 1;
2454 newexpr
= build_gimple_modify_stmt (temp
, newexpr
);
2455 name
= make_ssa_name (temp
, newexpr
);
2456 GIMPLE_STMT_OPERAND (newexpr
, 0) = name
;
2457 NECESSARY (newexpr
) = 0;
2459 tsi
= tsi_last (stmts
);
2460 tsi_link_after (&tsi
, newexpr
, TSI_CONTINUE_LINKING
);
2461 VEC_safe_push (tree
, heap
, inserted_exprs
, newexpr
);
2463 /* All the symbols in NEWEXPR should be put into SSA form. */
2464 mark_symbols_for_renaming (newexpr
);
2466 /* Add a value handle to the temporary.
2467 The value may already exist in either NEW_SETS, or AVAIL_OUT, because
2468 we are creating the expression by pieces, and this particular piece of
2469 the expression may have been represented. There is no harm in replacing
2471 v
= get_value_handle (expr
);
2473 VN_INFO_GET (name
)->valnum
= name
;
2474 get_or_alloc_expression_id (name
);
2476 bitmap_value_replace_in_set (NEW_SETS (block
), name
);
2477 bitmap_value_replace_in_set (AVAIL_OUT (block
), name
);
2479 pre_stats
.insertions
++;
2480 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2482 fprintf (dump_file
, "Inserted ");
2483 print_generic_expr (dump_file
, newexpr
, 0);
2484 fprintf (dump_file
, " in predecessor %d\n", block
->index
);
2490 /* Insert the to-be-made-available values of expression EXPRNUM for each
2491 predecessor, stored in AVAIL, into the predecessors of BLOCK, and
2492 merge the result with a phi node, given the same value handle as
2493 NODE. Return true if we have inserted new stuff. */
2496 insert_into_preds_of_block (basic_block block
, unsigned int exprnum
,
2499 tree expr
= expression_for_id (exprnum
);
2500 tree val
= get_value_handle (expr
);
2502 bool insertions
= false;
2507 tree type
= TREE_TYPE (avail
[EDGE_PRED (block
, 0)->src
->index
]);
2510 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2512 fprintf (dump_file
, "Found partial redundancy for expression ");
2513 print_generic_expr (dump_file
, expr
, 0);
2514 fprintf (dump_file
, " (");
2515 print_generic_expr (dump_file
, val
, 0);
2516 fprintf (dump_file
, ")");
2517 fprintf (dump_file
, "\n");
2520 /* Make sure we aren't creating an induction variable. */
2521 if (block
->loop_depth
> 0 && EDGE_COUNT (block
->preds
) == 2
2522 && TREE_CODE_CLASS (TREE_CODE (expr
)) != tcc_reference
)
2524 bool firstinsideloop
= false;
2525 bool secondinsideloop
= false;
2526 firstinsideloop
= flow_bb_inside_loop_p (block
->loop_father
,
2527 EDGE_PRED (block
, 0)->src
);
2528 secondinsideloop
= flow_bb_inside_loop_p (block
->loop_father
,
2529 EDGE_PRED (block
, 1)->src
);
2530 /* Induction variables only have one edge inside the loop. */
2531 if (firstinsideloop
^ secondinsideloop
)
2533 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2534 fprintf (dump_file
, "Skipping insertion of phi for partial redundancy: Looks like an induction variable\n");
2540 /* Make the necessary insertions. */
2541 FOR_EACH_EDGE (pred
, ei
, block
->preds
)
2543 tree stmts
= alloc_stmt_list ();
2546 eprime
= avail
[bprime
->index
];
2548 if (can_PRE_operation (eprime
))
2550 builtexpr
= create_expression_by_pieces (bprime
,
2553 gcc_assert (!(pred
->flags
& EDGE_ABNORMAL
));
2554 bsi_insert_on_edge (pred
, stmts
);
2555 avail
[bprime
->index
] = builtexpr
;
2559 /* If we didn't want a phi node, and we made insertions, we still have
2560 inserted new stuff, and thus return true. If we didn't want a phi node,
2561 and didn't make insertions, we haven't added anything new, so return
2563 if (nophi
&& insertions
)
2565 else if (nophi
&& !insertions
)
2568 /* Now build a phi for the new variable. */
2569 if (!prephitemp
|| TREE_TYPE (prephitemp
) != type
)
2571 prephitemp
= create_tmp_var (type
, "prephitmp");
2572 get_var_ann (prephitemp
);
2576 add_referenced_var (temp
);
2579 if (TREE_CODE (type
) == COMPLEX_TYPE
2580 || TREE_CODE (type
) == VECTOR_TYPE
)
2581 DECL_GIMPLE_REG_P (temp
) = 1;
2582 temp
= create_phi_node (temp
, block
);
2584 NECESSARY (temp
) = 0;
2585 VN_INFO_GET (PHI_RESULT (temp
))->valnum
= PHI_RESULT (temp
);
2587 VEC_safe_push (tree
, heap
, inserted_exprs
, temp
);
2588 FOR_EACH_EDGE (pred
, ei
, block
->preds
)
2589 add_phi_arg (temp
, avail
[pred
->src
->index
], pred
);
2591 vn_add (PHI_RESULT (temp
), val
);
2593 /* The value should *not* exist in PHI_GEN, or else we wouldn't be doing
2594 this insertion, since we test for the existence of this value in PHI_GEN
2595 before proceeding with the partial redundancy checks in insert_aux.
2597 The value may exist in AVAIL_OUT, in particular, it could be represented
2598 by the expression we are trying to eliminate, in which case we want the
2599 replacement to occur. If it's not existing in AVAIL_OUT, we want it
2602 Similarly, to the PHI_GEN case, the value should not exist in NEW_SETS of
2603 this block, because if it did, it would have existed in our dominator's
2604 AVAIL_OUT, and would have been skipped due to the full redundancy check.
2607 bitmap_insert_into_set (PHI_GEN (block
),
2609 bitmap_value_replace_in_set (AVAIL_OUT (block
),
2611 bitmap_insert_into_set (NEW_SETS (block
),
2614 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2616 fprintf (dump_file
, "Created phi ");
2617 print_generic_expr (dump_file
, temp
, 0);
2618 fprintf (dump_file
, " in block %d\n", block
->index
);
2626 /* Perform insertion of partially redundant values.
2627 For BLOCK, do the following:
2628 1. Propagate the NEW_SETS of the dominator into the current block.
2629 If the block has multiple predecessors,
2630 2a. Iterate over the ANTIC expressions for the block to see if
2631 any of them are partially redundant.
2632 2b. If so, insert them into the necessary predecessors to make
2633 the expression fully redundant.
2634 2c. Insert a new PHI merging the values of the predecessors.
2635 2d. Insert the new PHI, and the new expressions, into the
2637 3. Recursively call ourselves on the dominator children of BLOCK.
2639 Steps 1, 2a, and 3 are done by insert_aux. 2b, 2c and 2d are done by
2640 do_regular_insertion and do_partial_insertion.
2645 do_regular_insertion (basic_block block
, basic_block dom
)
2647 bool new_stuff
= false;
2648 VEC (tree
, heap
) *exprs
= sorted_array_from_bitmap_set (ANTIC_IN (block
));
2652 for (i
= 0; VEC_iterate (tree
, exprs
, i
, expr
); i
++)
2654 if (can_PRE_operation (expr
) && !AGGREGATE_TYPE_P (TREE_TYPE (expr
)))
2658 bool by_some
= false;
2659 bool cant_insert
= false;
2660 bool all_same
= true;
2661 tree first_s
= NULL
;
2664 tree eprime
= NULL_TREE
;
2667 val
= get_value_handle (expr
);
2668 if (bitmap_set_contains_value (PHI_GEN (block
), val
))
2670 if (bitmap_set_contains_value (AVAIL_OUT (dom
), val
))
2672 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2673 fprintf (dump_file
, "Found fully redundant value\n");
2677 avail
= XCNEWVEC (tree
, last_basic_block
);
2678 FOR_EACH_EDGE (pred
, ei
, block
->preds
)
2683 /* This can happen in the very weird case
2684 that our fake infinite loop edges have caused a
2685 critical edge to appear. */
2686 if (EDGE_CRITICAL_P (pred
))
2692 eprime
= phi_translate (expr
, ANTIC_IN (block
), NULL
,
2695 /* eprime will generally only be NULL if the
2696 value of the expression, translated
2697 through the PHI for this predecessor, is
2698 undefined. If that is the case, we can't
2699 make the expression fully redundant,
2700 because its value is undefined along a
2701 predecessor path. We can thus break out
2702 early because it doesn't matter what the
2703 rest of the results are. */
2710 eprime
= fully_constant_expression (eprime
);
2711 vprime
= get_value_handle (eprime
);
2712 gcc_assert (vprime
);
2713 edoubleprime
= bitmap_find_leader (AVAIL_OUT (bprime
),
2715 if (edoubleprime
== NULL
)
2717 avail
[bprime
->index
] = eprime
;
2722 avail
[bprime
->index
] = edoubleprime
;
2724 if (first_s
== NULL
)
2725 first_s
= edoubleprime
;
2726 else if (!operand_equal_p (first_s
, edoubleprime
,
2731 /* If we can insert it, it's not the same value
2732 already existing along every predecessor, and
2733 it's defined by some predecessor, it is
2734 partially redundant. */
2735 if (!cant_insert
&& !all_same
&& by_some
)
2737 if (insert_into_preds_of_block (block
, get_expression_id (expr
),
2741 /* If all edges produce the same value and that value is
2742 an invariant, then the PHI has the same value on all
2743 edges. Note this. */
2744 else if (!cant_insert
&& all_same
&& eprime
2745 && is_gimple_min_invariant (eprime
)
2746 && !is_gimple_min_invariant (val
))
2751 bitmap_set_t exprset
= VALUE_HANDLE_EXPR_SET (val
);
2752 FOR_EACH_EXPR_ID_IN_SET (exprset
, j
, bi
)
2754 tree expr
= expression_for_id (j
);
2755 if (TREE_CODE (expr
) == SSA_NAME
)
2757 vn_add (expr
, eprime
);
2758 pre_stats
.constified
++;
2766 VEC_free (tree
, heap
, exprs
);
2771 /* Perform insertion for partially anticipatable expressions. There
2772 is only one case we will perform insertion for these. This case is
2773 if the expression is partially anticipatable, and fully available.
2774 In this case, we know that putting it earlier will enable us to
2775 remove the later computation. */
2779 do_partial_partial_insertion (basic_block block
, basic_block dom
)
2781 bool new_stuff
= false;
2782 VEC (tree
, heap
) *exprs
= sorted_array_from_bitmap_set (PA_IN (block
));
2786 for (i
= 0; VEC_iterate (tree
, exprs
, i
, expr
); i
++)
2788 if (can_PRE_operation (expr
) && !AGGREGATE_TYPE_P (TREE_TYPE (expr
)))
2793 bool cant_insert
= false;
2796 tree eprime
= NULL_TREE
;
2799 val
= get_value_handle (expr
);
2800 if (bitmap_set_contains_value (PHI_GEN (block
), val
))
2802 if (bitmap_set_contains_value (AVAIL_OUT (dom
), val
))
2805 avail
= XCNEWVEC (tree
, last_basic_block
);
2806 FOR_EACH_EDGE (pred
, ei
, block
->preds
)
2811 /* This can happen in the very weird case
2812 that our fake infinite loop edges have caused a
2813 critical edge to appear. */
2814 if (EDGE_CRITICAL_P (pred
))
2820 eprime
= phi_translate (expr
, ANTIC_IN (block
),
2824 /* eprime will generally only be NULL if the
2825 value of the expression, translated
2826 through the PHI for this predecessor, is
2827 undefined. If that is the case, we can't
2828 make the expression fully redundant,
2829 because its value is undefined along a
2830 predecessor path. We can thus break out
2831 early because it doesn't matter what the
2832 rest of the results are. */
2839 eprime
= fully_constant_expression (eprime
);
2840 vprime
= get_value_handle (eprime
);
2841 gcc_assert (vprime
);
2842 edoubleprime
= bitmap_find_leader (AVAIL_OUT (bprime
),
2844 if (edoubleprime
== NULL
)
2850 avail
[bprime
->index
] = edoubleprime
;
2854 /* If we can insert it, it's not the same value
2855 already existing along every predecessor, and
2856 it's defined by some predecessor, it is
2857 partially redundant. */
2858 if (!cant_insert
&& by_all
)
2860 pre_stats
.pa_insert
++;
2861 if (insert_into_preds_of_block (block
, get_expression_id (expr
),
2869 VEC_free (tree
, heap
, exprs
);
2874 insert_aux (basic_block block
)
2877 bool new_stuff
= false;
2882 dom
= get_immediate_dominator (CDI_DOMINATORS
, block
);
2887 bitmap_set_t newset
= NEW_SETS (dom
);
2890 /* Note that we need to value_replace both NEW_SETS, and
2891 AVAIL_OUT. For both the case of NEW_SETS, the value may be
2892 represented by some non-simple expression here that we want
2893 to replace it with. */
2894 FOR_EACH_EXPR_ID_IN_SET (newset
, i
, bi
)
2896 tree expr
= expression_for_id (i
);
2897 bitmap_value_replace_in_set (NEW_SETS (block
), expr
);
2898 bitmap_value_replace_in_set (AVAIL_OUT (block
), expr
);
2901 if (!single_pred_p (block
))
2903 new_stuff
|= do_regular_insertion (block
, dom
);
2904 if (do_partial_partial
)
2905 new_stuff
|= do_partial_partial_insertion (block
, dom
);
2909 for (son
= first_dom_son (CDI_DOMINATORS
, block
);
2911 son
= next_dom_son (CDI_DOMINATORS
, son
))
2913 new_stuff
|= insert_aux (son
);
2919 /* Perform insertion of partially redundant values. */
2924 bool new_stuff
= true;
2926 int num_iterations
= 0;
2929 NEW_SETS (bb
) = bitmap_set_new ();
2935 new_stuff
= insert_aux (ENTRY_BLOCK_PTR
);
2937 statistics_histogram_event (cfun
, "insert iterations", num_iterations
);
2941 /* Add OP to EXP_GEN (block), and possibly to the maximal set if it is
2942 not defined by a phi node.
2943 PHI nodes can't go in the maximal sets because they are not in
2944 TMP_GEN, so it is possible to get into non-monotonic situations
2945 during ANTIC calculation, because it will *add* bits. */
2948 add_to_exp_gen (basic_block block
, tree op
)
2952 if (TREE_CODE (op
) == SSA_NAME
&& ssa_undefined_value_p (op
))
2954 bitmap_value_insert_into_set (EXP_GEN (block
), op
);
2955 if (TREE_CODE (op
) != SSA_NAME
2956 || TREE_CODE (SSA_NAME_DEF_STMT (op
)) != PHI_NODE
)
2957 bitmap_value_insert_into_set (maximal_set
, op
);
2962 /* Given an SSA variable VAR and an expression EXPR, compute the value
2963 number for EXPR and create a value handle (VAL) for it. If VAR and
2964 EXPR are not the same, associate VAL with VAR. Finally, add VAR to
2965 S1 and its value handle to S2, and to the maximal set if
2966 ADD_TO_MAXIMAL is true.
2968 VUSES represent the virtual use operands associated with EXPR (if
2972 add_to_sets (tree var
, tree expr
, VEC(tree
, gc
) *vuses
, bitmap_set_t s1
,
2976 val
= vn_lookup_or_add_with_vuses (expr
, vuses
);
2978 /* VAR and EXPR may be the same when processing statements for which
2979 we are not computing value numbers (e.g., non-assignments, or
2980 statements that make aliased stores). In those cases, we are
2981 only interested in making VAR available as its own value. */
2986 bitmap_insert_into_set (s1
, var
);
2988 bitmap_value_insert_into_set (s2
, var
);
2991 /* Find existing value expression that is the same as T,
2992 and return it if it exists. */
2995 find_existing_value_expr (tree t
, VEC (tree
, gc
) *vuses
)
3000 bitmap_set_t exprset
;
3002 if (REFERENCE_CLASS_P (t
) || TREE_CODE (t
) == CALL_EXPR
|| DECL_P (t
))
3003 vh
= vn_lookup_with_vuses (t
, vuses
);
3009 exprset
= VALUE_HANDLE_EXPR_SET (vh
);
3010 FOR_EACH_EXPR_ID_IN_SET (exprset
, bii
, bi
)
3012 tree efi
= expression_for_id (bii
);
3013 if (expressions_equal_p (t
, efi
))
3019 /* Given a unary or binary expression EXPR, create and return a new
3020 expression with the same structure as EXPR but with its operands
3021 replaced with the value handles of each of the operands of EXPR.
3023 VUSES represent the virtual use operands associated with EXPR (if
3024 any). Insert EXPR's operands into the EXP_GEN set for BLOCK.
3026 If CHECK_AVAIL is true, checks availability of each operand in
3027 BLOCKs AVAIL_OUT set. */
3030 create_value_expr_from (tree expr
, basic_block block
, VEC (tree
, gc
) *vuses
,
3034 enum tree_code code
= TREE_CODE (expr
);
3036 alloc_pool pool
= NULL
;
3039 gcc_assert (TREE_CODE_CLASS (code
) == tcc_unary
3040 || TREE_CODE_CLASS (code
) == tcc_binary
3041 || TREE_CODE_CLASS (code
) == tcc_comparison
3042 || TREE_CODE_CLASS (code
) == tcc_reference
3043 || TREE_CODE_CLASS (code
) == tcc_expression
3044 || TREE_CODE_CLASS (code
) == tcc_vl_exp
3045 || TREE_CODE_CLASS (code
) == tcc_exceptional
3046 || TREE_CODE_CLASS (code
) == tcc_declaration
);
3048 if (TREE_CODE_CLASS (code
) == tcc_unary
)
3049 pool
= unary_node_pool
;
3050 else if (TREE_CODE_CLASS (code
) == tcc_reference
)
3051 pool
= reference_node_pool
;
3052 else if (TREE_CODE_CLASS (code
) == tcc_binary
)
3053 pool
= binary_node_pool
;
3054 else if (TREE_CODE_CLASS (code
) == tcc_comparison
)
3055 pool
= comparison_node_pool
;
3057 gcc_assert (code
== CALL_EXPR
);
3059 if (code
== CALL_EXPR
)
3060 vexpr
= temp_copy_call_expr (expr
);
3063 vexpr
= (tree
) pool_alloc (pool
);
3064 memcpy (vexpr
, expr
, tree_size (expr
));
3067 for (i
= 0; i
< TREE_OPERAND_LENGTH (expr
); i
++)
3069 tree val
= NULL_TREE
;
3072 op
= TREE_OPERAND (expr
, i
);
3073 if (op
== NULL_TREE
)
3076 /* Recursively value-numberize reference ops and tree lists. */
3077 if (REFERENCE_CLASS_P (op
))
3079 tree tempop
= create_value_expr_from (op
, block
, vuses
, check_avail
);
3080 op
= tempop
? tempop
: op
;
3081 val
= vn_lookup_or_add_with_vuses (op
, vuses
);
3082 set_expression_vuses (op
, vuses
);
3086 val
= vn_lookup_or_add (op
);
3088 if (TREE_CODE (op
) != TREE_LIST
)
3089 add_to_exp_gen (block
, op
);
3091 if (TREE_CODE (val
) == VALUE_HANDLE
)
3092 TREE_TYPE (val
) = TREE_TYPE (TREE_OPERAND (vexpr
, i
));
3094 TREE_OPERAND (vexpr
, i
) = val
;
3097 && TREE_CODE (val
) == VALUE_HANDLE
3098 && !bitmap_set_contains_value (AVAIL_OUT (block
), val
))
3101 efi
= find_existing_value_expr (vexpr
, vuses
);
3104 get_or_alloc_expression_id (vexpr
);
3109 /* For each real store operation of the form
3110 *a = <value> that we see, create a corresponding fake store of the
3111 form storetmp_<version> = *a.
3113 This enables AVAIL computation to mark the results of stores as
3114 available. Without this, you'd need to do some computation to
3115 mark the result of stores as ANTIC and AVAIL at all the right
3117 To save memory, we keep the store
3118 statements pool allocated until we decide whether they are
3119 necessary or not. */
3122 insert_fake_stores (void)
3128 block_stmt_iterator bsi
;
3129 for (bsi
= bsi_start (block
); !bsi_end_p (bsi
); bsi_next (&bsi
))
3131 tree stmt
= bsi_stmt (bsi
);
3133 /* We can't generate SSA names for stores that are complex
3134 or aggregate. We also want to ignore things whose
3135 virtual uses occur in abnormal phis. */
3137 if (TREE_CODE (stmt
) == GIMPLE_MODIFY_STMT
3138 && (TREE_CODE (GIMPLE_STMT_OPERAND (stmt
, 0)) == INDIRECT_REF
3139 || handled_component_p (GIMPLE_STMT_OPERAND (stmt
, 0)))
3140 && !AGGREGATE_TYPE_P (TREE_TYPE (GIMPLE_STMT_OPERAND (stmt
, 0))))
3144 tree lhs
= GIMPLE_STMT_OPERAND (stmt
, 0);
3145 tree rhs
= GIMPLE_STMT_OPERAND (stmt
, 1);
3146 tree new_tree
, new_lhs
;
3147 bool notokay
= false;
3149 FOR_EACH_SSA_DEF_OPERAND (defp
, stmt
, iter
, SSA_OP_VIRTUAL_DEFS
)
3151 tree defvar
= DEF_FROM_PTR (defp
);
3152 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (defvar
))
3162 if (!storetemp
|| TREE_TYPE (rhs
) != TREE_TYPE (storetemp
))
3164 storetemp
= create_tmp_var (TREE_TYPE (rhs
), "storetmp");
3165 if (TREE_CODE (TREE_TYPE (storetemp
)) == VECTOR_TYPE
3166 || TREE_CODE (TREE_TYPE (storetemp
)) == COMPLEX_TYPE
)
3167 DECL_GIMPLE_REG_P (storetemp
) = 1;
3168 get_var_ann (storetemp
);
3171 new_tree
= build_gimple_modify_stmt (NULL_TREE
, lhs
);
3172 new_lhs
= make_ssa_name (storetemp
, new_tree
);
3173 GIMPLE_STMT_OPERAND (new_tree
, 0) = new_lhs
;
3175 create_ssa_artificial_load_stmt (new_tree
, stmt
, false);
3177 NECESSARY (new_tree
) = 0;
3178 VEC_safe_push (tree
, heap
, inserted_exprs
, new_tree
);
3179 VEC_safe_push (tree
, heap
, need_creation
, new_tree
);
3180 bsi_insert_after (&bsi
, new_tree
, BSI_NEW_STMT
);
3186 /* Turn the pool allocated fake stores that we created back into real
3187 GC allocated ones if they turned out to be necessary to PRE some
3191 realify_fake_stores (void)
3196 for (i
= 0; VEC_iterate (tree
, need_creation
, i
, stmt
); i
++)
3198 if (NECESSARY (stmt
))
3200 block_stmt_iterator bsi
, bsi2
;
3203 /* Mark the temp variable as referenced */
3204 add_referenced_var (SSA_NAME_VAR (GIMPLE_STMT_OPERAND (stmt
, 0)));
3206 /* Put the statement before the store in the IR stream
3207 as a plain ssa name copy. */
3208 bsi
= bsi_for_stmt (stmt
);
3210 rhs
= GIMPLE_STMT_OPERAND (bsi_stmt (bsi
), 1);
3211 GIMPLE_STMT_OPERAND (stmt
, 1) = rhs
;
3212 bsi2
= bsi_for_stmt (stmt
);
3213 bsi_remove (&bsi2
, true);
3214 bsi_insert_before (&bsi
, stmt
, BSI_SAME_STMT
);
3217 release_defs (stmt
);
3221 /* Given an SSA_NAME, see if SCCVN has a value number for it, and if
3222 so, return the value handle for this value number, creating it if
3224 Return NULL if SCCVN has no info for us. */
3227 get_sccvn_value (tree name
)
3229 if (TREE_CODE (name
) == SSA_NAME
3230 && VN_INFO (name
)->valnum
!= name
3231 && VN_INFO (name
)->valnum
!= VN_TOP
)
3233 tree val
= VN_INFO (name
)->valnum
;
3234 bool is_invariant
= is_gimple_min_invariant (val
);
3235 tree valvh
= !is_invariant
? get_value_handle (val
) : NULL_TREE
;
3237 /* We may end up with situations where SCCVN has chosen a
3238 representative for the equivalence set that we have not
3239 visited yet. In this case, just create the value handle for
3241 if (!valvh
&& !is_invariant
)
3243 /* We lookup with the LHS, so do not use vn_lookup_or_add_with_stmt
3244 here, as that will result in useless reference lookups. */
3245 valvh
= vn_lookup_or_add (val
);
3248 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3250 fprintf (dump_file
, "SCCVN says ");
3251 print_generic_expr (dump_file
, name
, 0);
3252 fprintf (dump_file
, " value numbers to ");
3253 if (valvh
&& !is_invariant
)
3255 print_generic_expr (dump_file
, val
, 0);
3256 fprintf (dump_file
, " (");
3257 print_generic_expr (dump_file
, valvh
, 0);
3258 fprintf (dump_file
, ")\n");
3261 print_generic_stmt (dump_file
, val
, 0);
3271 /* Create value handles for PHI in BLOCK. */
3274 make_values_for_phi (tree phi
, basic_block block
)
3276 tree result
= PHI_RESULT (phi
);
3277 /* We have no need for virtual phis, as they don't represent
3278 actual computations. */
3279 if (is_gimple_reg (result
))
3281 tree sccvnval
= get_sccvn_value (result
);
3284 vn_add (result
, sccvnval
);
3285 bitmap_insert_into_set (PHI_GEN (block
), result
);
3286 bitmap_value_insert_into_set (AVAIL_OUT (block
), result
);
3289 add_to_sets (result
, result
, NULL
,
3290 PHI_GEN (block
), AVAIL_OUT (block
));
3294 /* Create value handles for STMT in BLOCK. Return true if we handled
3298 make_values_for_stmt (tree stmt
, basic_block block
)
3301 tree lhs
= GIMPLE_STMT_OPERAND (stmt
, 0);
3302 tree rhs
= GIMPLE_STMT_OPERAND (stmt
, 1);
3303 tree valvh
= NULL_TREE
;
3305 VEC (tree
, gc
) *vuses
= NULL
;
3307 valvh
= get_sccvn_value (lhs
);
3311 vn_add (lhs
, valvh
);
3312 bitmap_value_insert_into_set (AVAIL_OUT (block
), lhs
);
3313 /* Shortcut for FRE. We have no need to create value expressions,
3314 just want to know what values are available where. */
3321 /* For FRE, if SCCVN didn't find anything, we aren't going to
3322 either, so just make up a new value number if necessary and
3324 if (get_value_handle (lhs
) == NULL
)
3325 vn_lookup_or_add (lhs
);
3326 bitmap_value_insert_into_set (AVAIL_OUT (block
), lhs
);
3330 lhsval
= valvh
? valvh
: get_value_handle (lhs
);
3331 vuses
= copy_vuses_from_stmt (stmt
);
3332 STRIP_USELESS_TYPE_CONVERSION (rhs
);
3333 if (can_value_number_operation (rhs
)
3334 && (!lhsval
|| !is_gimple_min_invariant (lhsval
))
3335 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
3337 /* For value numberable operation, create a
3338 duplicate expression with the operands replaced
3339 with the value handles of the original RHS. */
3340 tree newt
= create_value_expr_from (rhs
, block
, vuses
, false);
3343 set_expression_vuses (newt
, vuses
);
3344 /* If we already have a value number for the LHS, reuse
3345 it rather than creating a new one. */
3348 set_value_handle (newt
, lhsval
);
3349 if (!is_gimple_min_invariant (lhsval
))
3350 add_to_value (lhsval
, newt
);
3354 tree val
= vn_lookup_or_add_with_vuses (newt
, vuses
);
3358 add_to_exp_gen (block
, newt
);
3361 bitmap_insert_into_set (TMP_GEN (block
), lhs
);
3362 bitmap_value_insert_into_set (AVAIL_OUT (block
), lhs
);
3365 else if ((TREE_CODE (rhs
) == SSA_NAME
3366 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs
))
3367 || is_gimple_min_invariant (rhs
)
3368 || TREE_CODE (rhs
) == ADDR_EXPR
3374 set_expression_vuses (rhs
, vuses
);
3375 set_value_handle (rhs
, lhsval
);
3376 if (!is_gimple_min_invariant (lhsval
))
3377 add_to_value (lhsval
, rhs
);
3378 bitmap_insert_into_set (TMP_GEN (block
), lhs
);
3379 bitmap_value_insert_into_set (AVAIL_OUT (block
), lhs
);
3383 /* Compute a value number for the RHS of the statement
3384 and add its value to the AVAIL_OUT set for the block.
3385 Add the LHS to TMP_GEN. */
3386 set_expression_vuses (rhs
, vuses
);
3387 add_to_sets (lhs
, rhs
, vuses
, TMP_GEN (block
),
3390 /* None of the rest of these can be PRE'd. */
3391 if (TREE_CODE (rhs
) == SSA_NAME
&& !ssa_undefined_value_p (rhs
))
3392 add_to_exp_gen (block
, rhs
);
3399 /* Compute the AVAIL set for all basic blocks.
3401 This function performs value numbering of the statements in each basic
3402 block. The AVAIL sets are built from information we glean while doing
3403 this value numbering, since the AVAIL sets contain only one entry per
3406 AVAIL_IN[BLOCK] = AVAIL_OUT[dom(BLOCK)].
3407 AVAIL_OUT[BLOCK] = AVAIL_IN[BLOCK] U PHI_GEN[BLOCK] U TMP_GEN[BLOCK]. */
3410 compute_avail (void)
3412 basic_block block
, son
;
3413 basic_block
*worklist
;
3417 /* For arguments with default definitions, we pretend they are
3418 defined in the entry block. */
3419 for (param
= DECL_ARGUMENTS (current_function_decl
);
3421 param
= TREE_CHAIN (param
))
3423 if (gimple_default_def (cfun
, param
) != NULL
)
3425 tree def
= gimple_default_def (cfun
, param
);
3427 vn_lookup_or_add (def
);
3430 bitmap_insert_into_set (TMP_GEN (ENTRY_BLOCK_PTR
), def
);
3431 bitmap_value_insert_into_set (maximal_set
, def
);
3433 bitmap_value_insert_into_set (AVAIL_OUT (ENTRY_BLOCK_PTR
), def
);
3437 /* Likewise for the static chain decl. */
3438 if (cfun
->static_chain_decl
)
3440 param
= cfun
->static_chain_decl
;
3441 if (gimple_default_def (cfun
, param
) != NULL
)
3443 tree def
= gimple_default_def (cfun
, param
);
3445 vn_lookup_or_add (def
);
3448 bitmap_insert_into_set (TMP_GEN (ENTRY_BLOCK_PTR
), def
);
3449 bitmap_value_insert_into_set (maximal_set
, def
);
3451 bitmap_value_insert_into_set (AVAIL_OUT (ENTRY_BLOCK_PTR
), def
);
3455 /* Allocate the worklist. */
3456 worklist
= XNEWVEC (basic_block
, n_basic_blocks
);
3458 /* Seed the algorithm by putting the dominator children of the entry
3459 block on the worklist. */
3460 for (son
= first_dom_son (CDI_DOMINATORS
, ENTRY_BLOCK_PTR
);
3462 son
= next_dom_son (CDI_DOMINATORS
, son
))
3463 worklist
[sp
++] = son
;
3465 /* Loop until the worklist is empty. */
3468 block_stmt_iterator bsi
;
3471 unsigned int stmt_uid
= 1;
3473 /* Pick a block from the worklist. */
3474 block
= worklist
[--sp
];
3476 /* Initially, the set of available values in BLOCK is that of
3477 its immediate dominator. */
3478 dom
= get_immediate_dominator (CDI_DOMINATORS
, block
);
3480 bitmap_set_copy (AVAIL_OUT (block
), AVAIL_OUT (dom
));
3482 /* Generate values for PHI nodes. */
3483 for (phi
= phi_nodes (block
); phi
; phi
= PHI_CHAIN (phi
))
3484 make_values_for_phi (phi
, block
);
3486 /* Now compute value numbers and populate value sets with all
3487 the expressions computed in BLOCK. */
3488 for (bsi
= bsi_start (block
); !bsi_end_p (bsi
); bsi_next (&bsi
))
3494 stmt
= bsi_stmt (bsi
);
3495 ann
= stmt_ann (stmt
);
3497 ann
->uid
= stmt_uid
++;
3499 /* For regular value numbering, we are only interested in
3500 assignments of the form X_i = EXPR, where EXPR represents
3501 an "interesting" computation, it has no volatile operands
3502 and X_i doesn't flow through an abnormal edge. */
3503 if (TREE_CODE (stmt
) == RETURN_EXPR
3504 && !ann
->has_volatile_ops
)
3506 tree realstmt
= stmt
;
3510 stmt
= TREE_OPERAND (stmt
, 0);
3511 if (stmt
&& TREE_CODE (stmt
) == GIMPLE_MODIFY_STMT
)
3513 lhs
= GIMPLE_STMT_OPERAND (stmt
, 0);
3514 rhs
= GIMPLE_STMT_OPERAND (stmt
, 1);
3515 if (TREE_CODE (lhs
) == SSA_NAME
3516 && is_gimple_min_invariant (VN_INFO (lhs
)->valnum
))
3518 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3520 fprintf (dump_file
, "SCCVN says ");
3521 print_generic_expr (dump_file
, lhs
, 0);
3522 fprintf (dump_file
, " value numbers to ");
3523 print_generic_stmt (dump_file
, VN_INFO (lhs
)->valnum
,
3526 vn_add (lhs
, VN_INFO (lhs
)->valnum
);
3530 if (TREE_CODE (rhs
) == SSA_NAME
)
3531 add_to_exp_gen (block
, rhs
);
3533 FOR_EACH_SSA_TREE_OPERAND (op
, realstmt
, iter
, SSA_OP_DEF
)
3534 add_to_sets (op
, op
, NULL
, TMP_GEN (block
),
3540 else if (TREE_CODE (stmt
) == GIMPLE_MODIFY_STMT
3541 && !ann
->has_volatile_ops
3542 && TREE_CODE (GIMPLE_STMT_OPERAND (stmt
, 0)) == SSA_NAME
3543 && !tree_could_throw_p (stmt
))
3545 if (make_values_for_stmt (stmt
, block
))
3549 /* For any other statement that we don't recognize, simply
3550 make the names generated by the statement available in
3551 AVAIL_OUT and TMP_GEN. */
3552 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, iter
, SSA_OP_DEF
)
3553 add_to_sets (op
, op
, NULL
, TMP_GEN (block
), AVAIL_OUT (block
));
3555 /* Also add all referenced SSA_NAMEs to EXP_GEN. */
3556 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, iter
, SSA_OP_USE
)
3557 add_to_exp_gen (block
, op
);
3560 /* Put the dominator children of BLOCK on the worklist of blocks
3561 to compute available sets for. */
3562 for (son
= first_dom_son (CDI_DOMINATORS
, block
);
3564 son
= next_dom_son (CDI_DOMINATORS
, son
))
3565 worklist
[sp
++] = son
;
3571 /* Insert the expression for SSA_VN that SCCVN thought would be simpler
3572 than the available expressions for it. The insertion point is
3573 right before the first use in STMT. Returns the SSA_NAME that should
3574 be used for replacement. */
3577 do_SCCVN_insertion (tree stmt
, tree ssa_vn
)
3579 basic_block bb
= bb_for_stmt (stmt
);
3580 block_stmt_iterator bsi
;
3583 /* First create a value expression from the expression we want
3584 to insert and associate it with the value handle for SSA_VN. */
3585 expr
= create_value_expr_from (VN_INFO (ssa_vn
)->expr
, bb
, NULL
, true);
3586 if (expr
== NULL_TREE
)
3588 set_value_handle (expr
, get_value_handle (ssa_vn
));
3590 /* Then use create_expression_by_pieces to generate a valid
3591 expression to insert at this point of the IL stream. */
3592 stmts
= alloc_stmt_list ();
3593 expr
= create_expression_by_pieces (bb
, expr
, stmts
, stmt
);
3594 if (expr
== NULL_TREE
)
3596 bsi
= bsi_for_stmt (stmt
);
3597 bsi_insert_before (&bsi
, stmts
, BSI_SAME_STMT
);
3602 /* Eliminate fully redundant computations. */
3608 unsigned int todo
= 0;
3612 block_stmt_iterator i
;
3614 for (i
= bsi_start (b
); !bsi_end_p (i
); bsi_next (&i
))
3616 tree stmt
= bsi_stmt (i
);
3618 /* Lookup the RHS of the expression, see if we have an
3619 available computation for it. If so, replace the RHS with
3620 the available computation. */
3621 if (TREE_CODE (stmt
) == GIMPLE_MODIFY_STMT
3622 && TREE_CODE (GIMPLE_STMT_OPERAND (stmt
, 0)) == SSA_NAME
3623 && TREE_CODE (GIMPLE_STMT_OPERAND (stmt
, 1)) != SSA_NAME
3624 && !is_gimple_min_invariant (GIMPLE_STMT_OPERAND (stmt
, 1))
3625 && !stmt_ann (stmt
)->has_volatile_ops
)
3627 tree lhs
= GIMPLE_STMT_OPERAND (stmt
, 0);
3628 tree
*rhs_p
= &GIMPLE_STMT_OPERAND (stmt
, 1);
3631 sprime
= bitmap_find_leader (AVAIL_OUT (b
),
3632 get_value_handle (lhs
), NULL_TREE
);
3634 /* If there is no existing usable leader but SCCVN thinks
3635 it has an expression it wants to use as replacement,
3640 tree val
= VN_INFO (lhs
)->valnum
;
3642 && VN_INFO (val
)->needs_insertion
3643 && can_PRE_operation (VN_INFO (val
)->expr
))
3644 sprime
= do_SCCVN_insertion (stmt
, val
);
3649 && (TREE_CODE (*rhs_p
) != SSA_NAME
3650 || may_propagate_copy (*rhs_p
, sprime
)))
3652 gcc_assert (sprime
!= *rhs_p
);
3654 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3656 fprintf (dump_file
, "Replaced ");
3657 print_generic_expr (dump_file
, *rhs_p
, 0);
3658 fprintf (dump_file
, " with ");
3659 print_generic_expr (dump_file
, sprime
, 0);
3660 fprintf (dump_file
, " in ");
3661 print_generic_stmt (dump_file
, stmt
, 0);
3664 if (TREE_CODE (sprime
) == SSA_NAME
)
3665 NECESSARY (SSA_NAME_DEF_STMT (sprime
)) = 1;
3666 /* We need to make sure the new and old types actually match,
3667 which may require adding a simple cast, which fold_convert
3669 if (TREE_CODE (*rhs_p
) != SSA_NAME
3670 && !useless_type_conversion_p (TREE_TYPE (*rhs_p
),
3671 TREE_TYPE (sprime
)))
3672 sprime
= fold_convert (TREE_TYPE (*rhs_p
), sprime
);
3674 pre_stats
.eliminations
++;
3675 propagate_tree_value (rhs_p
, sprime
);
3678 /* If we removed EH side effects from the statement, clean
3679 its EH information. */
3680 if (maybe_clean_or_replace_eh_stmt (stmt
, stmt
))
3682 bitmap_set_bit (need_eh_cleanup
,
3683 bb_for_stmt (stmt
)->index
);
3684 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3685 fprintf (dump_file
, " Removed EH side effects.\n");
3689 /* Visit COND_EXPRs and fold the comparison with the
3690 available value-numbers. */
3691 else if (TREE_CODE (stmt
) == COND_EXPR
3692 && COMPARISON_CLASS_P (COND_EXPR_COND (stmt
)))
3694 tree cond
= COND_EXPR_COND (stmt
);
3695 tree op0
= TREE_OPERAND (cond
, 0);
3696 tree op1
= TREE_OPERAND (cond
, 1);
3699 if (TREE_CODE (op0
) == SSA_NAME
)
3700 op0
= VN_INFO (op0
)->valnum
;
3701 if (TREE_CODE (op1
) == SSA_NAME
)
3702 op1
= VN_INFO (op1
)->valnum
;
3703 result
= fold_binary (TREE_CODE (cond
), TREE_TYPE (cond
),
3705 if (result
&& TREE_CODE (result
) == INTEGER_CST
)
3707 COND_EXPR_COND (stmt
) = result
;
3709 todo
= TODO_cleanup_cfg
;
3712 else if (TREE_CODE (stmt
) == COND_EXPR
3713 && TREE_CODE (COND_EXPR_COND (stmt
)) == SSA_NAME
)
3715 tree op
= COND_EXPR_COND (stmt
);
3716 op
= VN_INFO (op
)->valnum
;
3717 if (TREE_CODE (op
) == INTEGER_CST
)
3719 COND_EXPR_COND (stmt
) = integer_zerop (op
)
3720 ? boolean_false_node
: boolean_true_node
;
3722 todo
= TODO_cleanup_cfg
;
3731 /* Borrow a bit of tree-ssa-dce.c for the moment.
3732 XXX: In 4.1, we should be able to just run a DCE pass after PRE, though
3733 this may be a bit faster, and we may want critical edges kept split. */
3735 /* If OP's defining statement has not already been determined to be necessary,
3736 mark that statement necessary. Return the stmt, if it is newly
3740 mark_operand_necessary (tree op
)
3746 if (TREE_CODE (op
) != SSA_NAME
)
3749 stmt
= SSA_NAME_DEF_STMT (op
);
3752 if (NECESSARY (stmt
)
3753 || IS_EMPTY_STMT (stmt
))
3756 NECESSARY (stmt
) = 1;
3760 /* Because we don't follow exactly the standard PRE algorithm, and decide not
3761 to insert PHI nodes sometimes, and because value numbering of casts isn't
3762 perfect, we sometimes end up inserting dead code. This simple DCE-like
3763 pass removes any insertions we made that weren't actually used. */
3766 remove_dead_inserted_code (void)
3768 VEC(tree
,heap
) *worklist
= NULL
;
3772 worklist
= VEC_alloc (tree
, heap
, VEC_length (tree
, inserted_exprs
));
3773 for (i
= 0; VEC_iterate (tree
, inserted_exprs
, i
, t
); i
++)
3776 VEC_quick_push (tree
, worklist
, t
);
3778 while (VEC_length (tree
, worklist
) > 0)
3780 t
= VEC_pop (tree
, worklist
);
3782 /* PHI nodes are somewhat special in that each PHI alternative has
3783 data and control dependencies. All the statements feeding the
3784 PHI node's arguments are always necessary. */
3785 if (TREE_CODE (t
) == PHI_NODE
)
3789 VEC_reserve (tree
, heap
, worklist
, PHI_NUM_ARGS (t
));
3790 for (k
= 0; k
< PHI_NUM_ARGS (t
); k
++)
3792 tree arg
= PHI_ARG_DEF (t
, k
);
3793 if (TREE_CODE (arg
) == SSA_NAME
)
3795 arg
= mark_operand_necessary (arg
);
3797 VEC_quick_push (tree
, worklist
, arg
);
3803 /* Propagate through the operands. Examine all the USE, VUSE and
3804 VDEF operands in this statement. Mark all the statements
3805 which feed this statement's uses as necessary. */
3809 /* The operands of VDEF expressions are also needed as they
3810 represent potential definitions that may reach this
3811 statement (VDEF operands allow us to follow def-def
3814 FOR_EACH_SSA_TREE_OPERAND (use
, t
, iter
, SSA_OP_ALL_USES
)
3816 tree n
= mark_operand_necessary (use
);
3818 VEC_safe_push (tree
, heap
, worklist
, n
);
3823 for (i
= 0; VEC_iterate (tree
, inserted_exprs
, i
, t
); i
++)
3827 block_stmt_iterator bsi
;
3829 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3831 fprintf (dump_file
, "Removing unnecessary insertion:");
3832 print_generic_stmt (dump_file
, t
, 0);
3835 if (TREE_CODE (t
) == PHI_NODE
)
3837 remove_phi_node (t
, NULL
, true);
3841 bsi
= bsi_for_stmt (t
);
3842 bsi_remove (&bsi
, true);
3847 VEC_free (tree
, heap
, worklist
);
3850 /* Initialize data structures used by PRE. */
3853 init_pre (bool do_fre
)
3857 next_expression_id
= 0;
3859 expression_vuses
= NULL
;
3862 inserted_exprs
= NULL
;
3863 need_creation
= NULL
;
3864 pretemp
= NULL_TREE
;
3865 storetemp
= NULL_TREE
;
3866 prephitemp
= NULL_TREE
;
3869 loop_optimizer_init (LOOPS_NORMAL
);
3871 connect_infinite_loops_to_exit ();
3872 memset (&pre_stats
, 0, sizeof (pre_stats
));
3875 postorder
= XNEWVEC (int, n_basic_blocks
- NUM_FIXED_BLOCKS
);
3876 post_order_compute (postorder
, false, false);
3879 bb
->aux
= xcalloc (1, sizeof (struct bb_bitmap_sets
));
3881 calculate_dominance_info (CDI_POST_DOMINATORS
);
3882 calculate_dominance_info (CDI_DOMINATORS
);
3884 bitmap_obstack_initialize (&grand_bitmap_obstack
);
3885 phi_translate_table
= htab_create (5110, expr_pred_trans_hash
,
3886 expr_pred_trans_eq
, free
);
3887 seen_during_translate
= BITMAP_ALLOC (&grand_bitmap_obstack
);
3888 bitmap_set_pool
= create_alloc_pool ("Bitmap sets",
3889 sizeof (struct bitmap_set
), 30);
3890 binary_node_pool
= create_alloc_pool ("Binary tree nodes",
3891 tree_code_size (PLUS_EXPR
), 30);
3892 unary_node_pool
= create_alloc_pool ("Unary tree nodes",
3893 tree_code_size (NEGATE_EXPR
), 30);
3894 reference_node_pool
= create_alloc_pool ("Reference tree nodes",
3895 tree_code_size (ARRAY_REF
), 30);
3896 comparison_node_pool
= create_alloc_pool ("Comparison tree nodes",
3897 tree_code_size (EQ_EXPR
), 30);
3898 obstack_init (&temp_call_expr_obstack
);
3902 EXP_GEN (bb
) = bitmap_set_new ();
3903 PHI_GEN (bb
) = bitmap_set_new ();
3904 TMP_GEN (bb
) = bitmap_set_new ();
3905 AVAIL_OUT (bb
) = bitmap_set_new ();
3907 maximal_set
= in_fre
? NULL
: bitmap_set_new ();
3909 need_eh_cleanup
= BITMAP_ALLOC (NULL
);
3913 /* Deallocate data structures used by PRE. */
3922 VEC_free (tree
, heap
, inserted_exprs
);
3923 VEC_free (tree
, heap
, need_creation
);
3924 bitmap_obstack_release (&grand_bitmap_obstack
);
3925 free_alloc_pool (bitmap_set_pool
);
3926 free_alloc_pool (binary_node_pool
);
3927 free_alloc_pool (reference_node_pool
);
3928 free_alloc_pool (unary_node_pool
);
3929 free_alloc_pool (comparison_node_pool
);
3930 htab_delete (phi_translate_table
);
3931 remove_fake_exit_edges ();
3939 free_dominance_info (CDI_POST_DOMINATORS
);
3941 if (!bitmap_empty_p (need_eh_cleanup
))
3943 tree_purge_all_dead_eh_edges (need_eh_cleanup
);
3944 cleanup_tree_cfg ();
3947 BITMAP_FREE (need_eh_cleanup
);
3949 /* Wipe out pointers to VALUE_HANDLEs. In the not terribly distant
3950 future we will want them to be persistent though. */
3951 for (i
= 0; i
< num_ssa_names
; i
++)
3953 tree name
= ssa_name (i
);
3958 if (SSA_NAME_VALUE (name
)
3959 && TREE_CODE (SSA_NAME_VALUE (name
)) == VALUE_HANDLE
)
3960 SSA_NAME_VALUE (name
) = NULL
;
3962 if (current_loops
!= NULL
)
3963 loop_optimizer_finalize ();
3966 /* Main entry point to the SSA-PRE pass. DO_FRE is true if the caller
3967 only wants to do full redundancy elimination. */
3970 execute_pre (bool do_fre
)
3972 unsigned int todo
= 0;
3974 do_partial_partial
= optimize
> 2;
3978 insert_fake_stores ();
3980 /* Collect and value number expressions computed in each basic block. */
3981 if (!run_scc_vn (do_fre
))
3984 remove_dead_inserted_code ();
3988 switch_to_PRE_table ();
3991 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3997 print_bitmap_set (dump_file
, EXP_GEN (bb
), "exp_gen", bb
->index
);
3998 print_bitmap_set (dump_file
, TMP_GEN (bb
), "tmp_gen",
4000 print_bitmap_set (dump_file
, AVAIL_OUT (bb
), "avail_out",
4005 /* Insert can get quite slow on an incredibly large number of basic
4006 blocks due to some quadratic behavior. Until this behavior is
4007 fixed, don't run it when he have an incredibly large number of
4008 bb's. If we aren't going to run insert, there is no point in
4009 computing ANTIC, either, even though it's plenty fast. */
4010 if (!do_fre
&& n_basic_blocks
< 4000)
4016 /* Remove all the redundant expressions. */
4017 todo
|= eliminate ();
4019 statistics_counter_event (cfun
, "Insertions", pre_stats
.insertions
);
4020 statistics_counter_event (cfun
, "PA inserted", pre_stats
.pa_insert
);
4021 statistics_counter_event (cfun
, "New PHIs", pre_stats
.phis
);
4022 statistics_counter_event (cfun
, "Eliminated", pre_stats
.eliminations
);
4023 statistics_counter_event (cfun
, "Constified", pre_stats
.constified
);
4024 bsi_commit_edge_inserts ();
4026 clear_expression_ids ();
4030 remove_dead_inserted_code ();
4031 realify_fake_stores ();
4039 /* Gate and execute functions for PRE. */
4044 return TODO_rebuild_alias
| execute_pre (false);
4050 return flag_tree_pre
!= 0;
4053 struct gimple_opt_pass pass_pre
=
4058 gate_pre
, /* gate */
4059 do_pre
, /* execute */
4062 0, /* static_pass_number */
4063 TV_TREE_PRE
, /* tv_id */
4064 PROP_no_crit_edges
| PROP_cfg
4065 | PROP_ssa
| PROP_alias
, /* properties_required */
4066 0, /* properties_provided */
4067 0, /* properties_destroyed */
4068 0, /* todo_flags_start */
4069 TODO_update_ssa_only_virtuals
| TODO_dump_func
| TODO_ggc_collect
4070 | TODO_verify_ssa
/* todo_flags_finish */
4075 /* Gate and execute functions for FRE. */
4080 return execute_pre (true);
4086 return flag_tree_fre
!= 0;
4089 struct gimple_opt_pass pass_fre
=
4094 gate_fre
, /* gate */
4095 execute_fre
, /* execute */
4098 0, /* static_pass_number */
4099 TV_TREE_FRE
, /* tv_id */
4100 PROP_cfg
| PROP_ssa
| PROP_alias
, /* properties_required */
4101 0, /* properties_provided */
4102 0, /* properties_destroyed */
4103 0, /* todo_flags_start */
4104 TODO_dump_func
| TODO_ggc_collect
| TODO_verify_ssa
/* todo_flags_finish */