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 if (dump_file
&& (dump_flags
& TDF_STATS
))
2035 fprintf (dump_file
, "compute_antic required %d iterations\n",
2038 if (do_partial_partial
)
2040 sbitmap_ones (changed_blocks
);
2041 mark_dfs_back_edges ();
2046 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2047 fprintf (dump_file
, "Starting iteration %d\n", num_iterations
);
2050 for (i
= 0; i
< last_basic_block
- NUM_FIXED_BLOCKS
; i
++)
2052 if (TEST_BIT (changed_blocks
, postorder
[i
]))
2054 basic_block block
= BASIC_BLOCK (postorder
[i
]);
2056 |= compute_partial_antic_aux (block
,
2057 TEST_BIT (has_abnormal_preds
,
2061 /* Theoretically possible, but *highly* unlikely. */
2062 gcc_assert (num_iterations
< 50);
2064 if (dump_file
&& (dump_flags
& TDF_STATS
))
2065 fprintf (dump_file
, "compute_partial_antic required %d iterations\n",
2068 sbitmap_free (has_abnormal_preds
);
2069 sbitmap_free (changed_blocks
);
2072 /* Return true if we can value number the call in STMT. This is true
2073 if we have a pure or constant call. */
2076 can_value_number_call (tree stmt
)
2078 tree call
= get_call_expr_in (stmt
);
2080 if (call_expr_flags (call
) & (ECF_PURE
| ECF_CONST
))
2085 /* Return true if OP is an exception handler related operation, such as
2086 FILTER_EXPR or EXC_PTR_EXPR. */
2089 is_exception_related (tree op
)
2091 return TREE_CODE (op
) == FILTER_EXPR
|| TREE_CODE (op
) == EXC_PTR_EXPR
;
2094 /* Return true if OP is a tree which we can perform value numbering
2098 can_value_number_operation (tree op
)
2100 return (UNARY_CLASS_P (op
)
2101 && !is_exception_related (TREE_OPERAND (op
, 0)))
2102 || BINARY_CLASS_P (op
)
2103 || COMPARISON_CLASS_P (op
)
2104 || REFERENCE_CLASS_P (op
)
2105 || (TREE_CODE (op
) == CALL_EXPR
2106 && can_value_number_call (op
));
2110 /* Return true if OP is a tree which we can perform PRE on
2111 on. This may not match the operations we can value number, but in
2112 a perfect world would. */
2115 can_PRE_operation (tree op
)
2117 return UNARY_CLASS_P (op
)
2118 || BINARY_CLASS_P (op
)
2119 || COMPARISON_CLASS_P (op
)
2120 || TREE_CODE (op
) == INDIRECT_REF
2121 || TREE_CODE (op
) == COMPONENT_REF
2122 || TREE_CODE (op
) == VIEW_CONVERT_EXPR
2123 || TREE_CODE (op
) == CALL_EXPR
2124 || TREE_CODE (op
) == ARRAY_REF
;
2128 /* Inserted expressions are placed onto this worklist, which is used
2129 for performing quick dead code elimination of insertions we made
2130 that didn't turn out to be necessary. */
2131 static VEC(tree
,heap
) *inserted_exprs
;
2133 /* Pool allocated fake store expressions are placed onto this
2134 worklist, which, after performing dead code elimination, is walked
2135 to see which expressions need to be put into GC'able memory */
2136 static VEC(tree
, heap
) *need_creation
;
2138 /* For COMPONENT_REF's and ARRAY_REF's, we can't have any intermediates for the
2139 COMPONENT_REF or INDIRECT_REF or ARRAY_REF portion, because we'd end up with
2140 trying to rename aggregates into ssa form directly, which is a no
2143 Thus, this routine doesn't create temporaries, it just builds a
2144 single access expression for the array, calling
2145 find_or_generate_expression to build the innermost pieces.
2147 This function is a subroutine of create_expression_by_pieces, and
2148 should not be called on it's own unless you really know what you
2152 create_component_ref_by_pieces (basic_block block
, tree expr
, tree stmts
,
2158 if (TREE_CODE (genop
) == VALUE_HANDLE
)
2160 tree found
= bitmap_find_leader (AVAIL_OUT (block
), expr
, domstmt
);
2165 if (TREE_CODE (genop
) == VALUE_HANDLE
)
2167 bitmap_set_t exprset
= VALUE_HANDLE_EXPR_SET (expr
);
2168 unsigned int firstbit
= bitmap_first_set_bit (exprset
->expressions
);
2169 genop
= expression_for_id (firstbit
);
2172 switch TREE_CODE (genop
)
2178 op0
= create_component_ref_by_pieces (block
,
2179 TREE_OPERAND (genop
, 0),
2181 op1
= TREE_OPERAND (genop
, 1);
2182 if (TREE_CODE (op1
) == VALUE_HANDLE
)
2183 op1
= find_or_generate_expression (block
, op1
, stmts
, domstmt
);
2184 op2
= TREE_OPERAND (genop
, 2);
2185 if (op2
&& TREE_CODE (op2
) == VALUE_HANDLE
)
2186 op2
= find_or_generate_expression (block
, op2
, stmts
, domstmt
);
2187 op3
= TREE_OPERAND (genop
, 3);
2188 if (op3
&& TREE_CODE (op3
) == VALUE_HANDLE
)
2189 op3
= find_or_generate_expression (block
, op3
, stmts
, domstmt
);
2192 folded
= build4 (ARRAY_REF
, TREE_TYPE (genop
), op0
, op1
,
2200 op0
= create_component_ref_by_pieces (block
,
2201 TREE_OPERAND (genop
, 0),
2205 /* op1 should be a FIELD_DECL, which are represented by
2207 op1
= TREE_OPERAND (genop
, 1);
2208 folded
= fold_build3 (COMPONENT_REF
, TREE_TYPE (genop
), op0
, op1
,
2215 tree op1
= TREE_OPERAND (genop
, 0);
2216 tree genop1
= find_or_generate_expression (block
, op1
, stmts
, domstmt
);
2220 folded
= fold_build1 (TREE_CODE (genop
), TREE_TYPE (genop
),
2238 /* Find a leader for an expression, or generate one using
2239 create_expression_by_pieces if it's ANTIC but
2241 BLOCK is the basic_block we are looking for leaders in.
2242 EXPR is the expression to find a leader or generate for.
2243 STMTS is the statement list to put the inserted expressions on.
2244 Returns the SSA_NAME of the LHS of the generated expression or the
2246 DOMSTMT if non-NULL is a statement that should be dominated by
2247 all uses in the generated expression. If DOMSTMT is non-NULL this
2248 routine can fail and return NULL_TREE. Otherwise it will assert
2252 find_or_generate_expression (basic_block block
, tree expr
, tree stmts
,
2255 tree genop
= bitmap_find_leader (AVAIL_OUT (block
), expr
, domstmt
);
2257 /* If it's still NULL, it must be a complex expression, so generate
2261 bitmap_set_t exprset
= VALUE_HANDLE_EXPR_SET (expr
);
2262 bool handled
= false;
2266 /* We will hit cases where we have SSA_NAME's in exprset before
2267 other operations, because we may have come up with the SCCVN
2268 value before getting to the RHS of the expression. */
2269 FOR_EACH_EXPR_ID_IN_SET (exprset
, i
, bi
)
2271 genop
= expression_for_id (i
);
2272 if (can_PRE_operation (genop
))
2275 genop
= create_expression_by_pieces (block
, genop
, stmts
,
2280 if (!handled
&& domstmt
)
2283 gcc_assert (handled
);
2288 #define NECESSARY(stmt) stmt->base.asm_written_flag
2289 /* Create an expression in pieces, so that we can handle very complex
2290 expressions that may be ANTIC, but not necessary GIMPLE.
2291 BLOCK is the basic block the expression will be inserted into,
2292 EXPR is the expression to insert (in value form)
2293 STMTS is a statement list to append the necessary insertions into.
2295 This function will die if we hit some value that shouldn't be
2296 ANTIC but is (IE there is no leader for it, or its components).
2297 This function may also generate expressions that are themselves
2298 partially or fully redundant. Those that are will be either made
2299 fully redundant during the next iteration of insert (for partially
2300 redundant ones), or eliminated by eliminate (for fully redundant
2303 If DOMSTMT is non-NULL then we make sure that all uses in the
2304 expressions dominate that statement. In this case the function
2305 can return NULL_TREE to signal failure. */
2308 create_expression_by_pieces (basic_block block
, tree expr
, tree stmts
,
2312 tree folded
, forced_stmts
, newexpr
;
2314 tree_stmt_iterator tsi
;
2316 switch (TREE_CODE_CLASS (TREE_CODE (expr
)))
2325 gcc_assert (TREE_CODE (expr
) == CALL_EXPR
);
2327 fn
= CALL_EXPR_FN (expr
);
2328 sc
= CALL_EXPR_STATIC_CHAIN (expr
);
2330 genfn
= find_or_generate_expression (block
, fn
, stmts
, domstmt
);
2334 nargs
= call_expr_nargs (expr
);
2335 buffer
= (tree
*) alloca (nargs
* sizeof (tree
));
2337 for (i
= 0; i
< nargs
; i
++)
2339 tree arg
= CALL_EXPR_ARG (expr
, i
);
2340 buffer
[i
] = find_or_generate_expression (block
, arg
, stmts
,
2346 folded
= build_call_array (TREE_TYPE (expr
), genfn
, nargs
, buffer
);
2349 CALL_EXPR_STATIC_CHAIN (folded
) =
2350 find_or_generate_expression (block
, sc
, stmts
, domstmt
);
2351 if (!CALL_EXPR_STATIC_CHAIN (folded
))
2354 folded
= fold (folded
);
2360 if (TREE_CODE (expr
) == COMPONENT_REF
2361 || TREE_CODE (expr
) == ARRAY_REF
)
2363 folded
= create_component_ref_by_pieces (block
, expr
, stmts
,
2370 tree op1
= TREE_OPERAND (expr
, 0);
2371 tree genop1
= find_or_generate_expression (block
, op1
, stmts
,
2376 folded
= fold_build1 (TREE_CODE (expr
), TREE_TYPE (expr
),
2383 case tcc_comparison
:
2385 tree op1
= TREE_OPERAND (expr
, 0);
2386 tree op2
= TREE_OPERAND (expr
, 1);
2387 tree genop1
= find_or_generate_expression (block
, op1
, stmts
, domstmt
);
2388 tree genop2
= find_or_generate_expression (block
, op2
, stmts
, domstmt
);
2389 if (!genop1
|| !genop2
)
2391 folded
= fold_build2 (TREE_CODE (expr
), TREE_TYPE (expr
),
2398 tree op1
= TREE_OPERAND (expr
, 0);
2399 tree genop1
= find_or_generate_expression (block
, op1
, stmts
, domstmt
);
2402 folded
= fold_build1 (TREE_CODE (expr
), TREE_TYPE (expr
),
2411 /* Force the generated expression to be a sequence of GIMPLE
2413 We have to call unshare_expr because force_gimple_operand may
2414 modify the tree we pass to it. */
2415 newexpr
= force_gimple_operand (unshare_expr (folded
), &forced_stmts
,
2418 /* If we have any intermediate expressions to the value sets, add them
2419 to the value sets and chain them on in the instruction stream. */
2422 tsi
= tsi_start (forced_stmts
);
2423 for (; !tsi_end_p (tsi
); tsi_next (&tsi
))
2425 tree stmt
= tsi_stmt (tsi
);
2426 tree forcedname
= GIMPLE_STMT_OPERAND (stmt
, 0);
2427 tree forcedexpr
= GIMPLE_STMT_OPERAND (stmt
, 1);
2428 tree val
= vn_lookup_or_add (forcedexpr
);
2430 VEC_safe_push (tree
, heap
, inserted_exprs
, stmt
);
2431 VN_INFO_GET (forcedname
)->valnum
= forcedname
;
2432 vn_add (forcedname
, val
);
2433 bitmap_value_replace_in_set (NEW_SETS (block
), forcedname
);
2434 bitmap_value_replace_in_set (AVAIL_OUT (block
), forcedname
);
2435 mark_symbols_for_renaming (stmt
);
2437 tsi
= tsi_last (stmts
);
2438 tsi_link_after (&tsi
, forced_stmts
, TSI_CONTINUE_LINKING
);
2441 /* Build and insert the assignment of the end result to the temporary
2442 that we will return. */
2443 if (!pretemp
|| TREE_TYPE (expr
) != TREE_TYPE (pretemp
))
2445 pretemp
= create_tmp_var (TREE_TYPE (expr
), "pretmp");
2446 get_var_ann (pretemp
);
2450 add_referenced_var (temp
);
2452 if (TREE_CODE (TREE_TYPE (expr
)) == COMPLEX_TYPE
2453 || TREE_CODE (TREE_TYPE (expr
)) == VECTOR_TYPE
)
2454 DECL_GIMPLE_REG_P (temp
) = 1;
2456 newexpr
= build_gimple_modify_stmt (temp
, newexpr
);
2457 name
= make_ssa_name (temp
, newexpr
);
2458 GIMPLE_STMT_OPERAND (newexpr
, 0) = name
;
2459 NECESSARY (newexpr
) = 0;
2461 tsi
= tsi_last (stmts
);
2462 tsi_link_after (&tsi
, newexpr
, TSI_CONTINUE_LINKING
);
2463 VEC_safe_push (tree
, heap
, inserted_exprs
, newexpr
);
2465 /* All the symbols in NEWEXPR should be put into SSA form. */
2466 mark_symbols_for_renaming (newexpr
);
2468 /* Add a value handle to the temporary.
2469 The value may already exist in either NEW_SETS, or AVAIL_OUT, because
2470 we are creating the expression by pieces, and this particular piece of
2471 the expression may have been represented. There is no harm in replacing
2473 v
= get_value_handle (expr
);
2475 VN_INFO_GET (name
)->valnum
= name
;
2476 get_or_alloc_expression_id (name
);
2478 bitmap_value_replace_in_set (NEW_SETS (block
), name
);
2479 bitmap_value_replace_in_set (AVAIL_OUT (block
), name
);
2481 pre_stats
.insertions
++;
2482 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2484 fprintf (dump_file
, "Inserted ");
2485 print_generic_expr (dump_file
, newexpr
, 0);
2486 fprintf (dump_file
, " in predecessor %d\n", block
->index
);
2492 /* Insert the to-be-made-available values of expression EXPRNUM for each
2493 predecessor, stored in AVAIL, into the predecessors of BLOCK, and
2494 merge the result with a phi node, given the same value handle as
2495 NODE. Return true if we have inserted new stuff. */
2498 insert_into_preds_of_block (basic_block block
, unsigned int exprnum
,
2501 tree expr
= expression_for_id (exprnum
);
2502 tree val
= get_value_handle (expr
);
2504 bool insertions
= false;
2509 tree type
= TREE_TYPE (avail
[EDGE_PRED (block
, 0)->src
->index
]);
2512 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2514 fprintf (dump_file
, "Found partial redundancy for expression ");
2515 print_generic_expr (dump_file
, expr
, 0);
2516 fprintf (dump_file
, " (");
2517 print_generic_expr (dump_file
, val
, 0);
2518 fprintf (dump_file
, ")");
2519 fprintf (dump_file
, "\n");
2522 /* Make sure we aren't creating an induction variable. */
2523 if (block
->loop_depth
> 0 && EDGE_COUNT (block
->preds
) == 2
2524 && TREE_CODE_CLASS (TREE_CODE (expr
)) != tcc_reference
)
2526 bool firstinsideloop
= false;
2527 bool secondinsideloop
= false;
2528 firstinsideloop
= flow_bb_inside_loop_p (block
->loop_father
,
2529 EDGE_PRED (block
, 0)->src
);
2530 secondinsideloop
= flow_bb_inside_loop_p (block
->loop_father
,
2531 EDGE_PRED (block
, 1)->src
);
2532 /* Induction variables only have one edge inside the loop. */
2533 if (firstinsideloop
^ secondinsideloop
)
2535 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2536 fprintf (dump_file
, "Skipping insertion of phi for partial redundancy: Looks like an induction variable\n");
2542 /* Make the necessary insertions. */
2543 FOR_EACH_EDGE (pred
, ei
, block
->preds
)
2545 tree stmts
= alloc_stmt_list ();
2548 eprime
= avail
[bprime
->index
];
2550 if (can_PRE_operation (eprime
))
2552 builtexpr
= create_expression_by_pieces (bprime
,
2555 gcc_assert (!(pred
->flags
& EDGE_ABNORMAL
));
2556 bsi_insert_on_edge (pred
, stmts
);
2557 avail
[bprime
->index
] = builtexpr
;
2561 /* If we didn't want a phi node, and we made insertions, we still have
2562 inserted new stuff, and thus return true. If we didn't want a phi node,
2563 and didn't make insertions, we haven't added anything new, so return
2565 if (nophi
&& insertions
)
2567 else if (nophi
&& !insertions
)
2570 /* Now build a phi for the new variable. */
2571 if (!prephitemp
|| TREE_TYPE (prephitemp
) != type
)
2573 prephitemp
= create_tmp_var (type
, "prephitmp");
2574 get_var_ann (prephitemp
);
2578 add_referenced_var (temp
);
2581 if (TREE_CODE (type
) == COMPLEX_TYPE
2582 || TREE_CODE (type
) == VECTOR_TYPE
)
2583 DECL_GIMPLE_REG_P (temp
) = 1;
2584 temp
= create_phi_node (temp
, block
);
2586 NECESSARY (temp
) = 0;
2587 VN_INFO_GET (PHI_RESULT (temp
))->valnum
= PHI_RESULT (temp
);
2589 VEC_safe_push (tree
, heap
, inserted_exprs
, temp
);
2590 FOR_EACH_EDGE (pred
, ei
, block
->preds
)
2591 add_phi_arg (temp
, avail
[pred
->src
->index
], pred
);
2593 vn_add (PHI_RESULT (temp
), val
);
2595 /* The value should *not* exist in PHI_GEN, or else we wouldn't be doing
2596 this insertion, since we test for the existence of this value in PHI_GEN
2597 before proceeding with the partial redundancy checks in insert_aux.
2599 The value may exist in AVAIL_OUT, in particular, it could be represented
2600 by the expression we are trying to eliminate, in which case we want the
2601 replacement to occur. If it's not existing in AVAIL_OUT, we want it
2604 Similarly, to the PHI_GEN case, the value should not exist in NEW_SETS of
2605 this block, because if it did, it would have existed in our dominator's
2606 AVAIL_OUT, and would have been skipped due to the full redundancy check.
2609 bitmap_insert_into_set (PHI_GEN (block
),
2611 bitmap_value_replace_in_set (AVAIL_OUT (block
),
2613 bitmap_insert_into_set (NEW_SETS (block
),
2616 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2618 fprintf (dump_file
, "Created phi ");
2619 print_generic_expr (dump_file
, temp
, 0);
2620 fprintf (dump_file
, " in block %d\n", block
->index
);
2628 /* Perform insertion of partially redundant values.
2629 For BLOCK, do the following:
2630 1. Propagate the NEW_SETS of the dominator into the current block.
2631 If the block has multiple predecessors,
2632 2a. Iterate over the ANTIC expressions for the block to see if
2633 any of them are partially redundant.
2634 2b. If so, insert them into the necessary predecessors to make
2635 the expression fully redundant.
2636 2c. Insert a new PHI merging the values of the predecessors.
2637 2d. Insert the new PHI, and the new expressions, into the
2639 3. Recursively call ourselves on the dominator children of BLOCK.
2641 Steps 1, 2a, and 3 are done by insert_aux. 2b, 2c and 2d are done by
2642 do_regular_insertion and do_partial_insertion.
2647 do_regular_insertion (basic_block block
, basic_block dom
)
2649 bool new_stuff
= false;
2650 VEC (tree
, heap
) *exprs
= sorted_array_from_bitmap_set (ANTIC_IN (block
));
2654 for (i
= 0; VEC_iterate (tree
, exprs
, i
, expr
); i
++)
2656 if (can_PRE_operation (expr
) && !AGGREGATE_TYPE_P (TREE_TYPE (expr
)))
2660 bool by_some
= false;
2661 bool cant_insert
= false;
2662 bool all_same
= true;
2663 tree first_s
= NULL
;
2666 tree eprime
= NULL_TREE
;
2669 val
= get_value_handle (expr
);
2670 if (bitmap_set_contains_value (PHI_GEN (block
), val
))
2672 if (bitmap_set_contains_value (AVAIL_OUT (dom
), val
))
2674 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2675 fprintf (dump_file
, "Found fully redundant value\n");
2679 avail
= XCNEWVEC (tree
, last_basic_block
);
2680 FOR_EACH_EDGE (pred
, ei
, block
->preds
)
2685 /* This can happen in the very weird case
2686 that our fake infinite loop edges have caused a
2687 critical edge to appear. */
2688 if (EDGE_CRITICAL_P (pred
))
2694 eprime
= phi_translate (expr
, ANTIC_IN (block
), NULL
,
2697 /* eprime will generally only be NULL if the
2698 value of the expression, translated
2699 through the PHI for this predecessor, is
2700 undefined. If that is the case, we can't
2701 make the expression fully redundant,
2702 because its value is undefined along a
2703 predecessor path. We can thus break out
2704 early because it doesn't matter what the
2705 rest of the results are. */
2712 eprime
= fully_constant_expression (eprime
);
2713 vprime
= get_value_handle (eprime
);
2714 gcc_assert (vprime
);
2715 edoubleprime
= bitmap_find_leader (AVAIL_OUT (bprime
),
2717 if (edoubleprime
== NULL
)
2719 avail
[bprime
->index
] = eprime
;
2724 avail
[bprime
->index
] = edoubleprime
;
2726 if (first_s
== NULL
)
2727 first_s
= edoubleprime
;
2728 else if (!operand_equal_p (first_s
, edoubleprime
,
2733 /* If we can insert it, it's not the same value
2734 already existing along every predecessor, and
2735 it's defined by some predecessor, it is
2736 partially redundant. */
2737 if (!cant_insert
&& !all_same
&& by_some
)
2739 if (insert_into_preds_of_block (block
, get_expression_id (expr
),
2743 /* If all edges produce the same value and that value is
2744 an invariant, then the PHI has the same value on all
2745 edges. Note this. */
2746 else if (!cant_insert
&& all_same
&& eprime
2747 && is_gimple_min_invariant (eprime
)
2748 && !is_gimple_min_invariant (val
))
2753 bitmap_set_t exprset
= VALUE_HANDLE_EXPR_SET (val
);
2754 FOR_EACH_EXPR_ID_IN_SET (exprset
, j
, bi
)
2756 tree expr
= expression_for_id (j
);
2757 if (TREE_CODE (expr
) == SSA_NAME
)
2759 vn_add (expr
, eprime
);
2760 pre_stats
.constified
++;
2768 VEC_free (tree
, heap
, exprs
);
2773 /* Perform insertion for partially anticipatable expressions. There
2774 is only one case we will perform insertion for these. This case is
2775 if the expression is partially anticipatable, and fully available.
2776 In this case, we know that putting it earlier will enable us to
2777 remove the later computation. */
2781 do_partial_partial_insertion (basic_block block
, basic_block dom
)
2783 bool new_stuff
= false;
2784 VEC (tree
, heap
) *exprs
= sorted_array_from_bitmap_set (PA_IN (block
));
2788 for (i
= 0; VEC_iterate (tree
, exprs
, i
, expr
); i
++)
2790 if (can_PRE_operation (expr
) && !AGGREGATE_TYPE_P (TREE_TYPE (expr
)))
2795 bool cant_insert
= false;
2798 tree eprime
= NULL_TREE
;
2801 val
= get_value_handle (expr
);
2802 if (bitmap_set_contains_value (PHI_GEN (block
), val
))
2804 if (bitmap_set_contains_value (AVAIL_OUT (dom
), val
))
2807 avail
= XCNEWVEC (tree
, last_basic_block
);
2808 FOR_EACH_EDGE (pred
, ei
, block
->preds
)
2813 /* This can happen in the very weird case
2814 that our fake infinite loop edges have caused a
2815 critical edge to appear. */
2816 if (EDGE_CRITICAL_P (pred
))
2822 eprime
= phi_translate (expr
, ANTIC_IN (block
),
2826 /* eprime will generally only be NULL if the
2827 value of the expression, translated
2828 through the PHI for this predecessor, is
2829 undefined. If that is the case, we can't
2830 make the expression fully redundant,
2831 because its value is undefined along a
2832 predecessor path. We can thus break out
2833 early because it doesn't matter what the
2834 rest of the results are. */
2841 eprime
= fully_constant_expression (eprime
);
2842 vprime
= get_value_handle (eprime
);
2843 gcc_assert (vprime
);
2844 edoubleprime
= bitmap_find_leader (AVAIL_OUT (bprime
),
2846 if (edoubleprime
== NULL
)
2852 avail
[bprime
->index
] = edoubleprime
;
2856 /* If we can insert it, it's not the same value
2857 already existing along every predecessor, and
2858 it's defined by some predecessor, it is
2859 partially redundant. */
2860 if (!cant_insert
&& by_all
)
2862 pre_stats
.pa_insert
++;
2863 if (insert_into_preds_of_block (block
, get_expression_id (expr
),
2871 VEC_free (tree
, heap
, exprs
);
2876 insert_aux (basic_block block
)
2879 bool new_stuff
= false;
2884 dom
= get_immediate_dominator (CDI_DOMINATORS
, block
);
2889 bitmap_set_t newset
= NEW_SETS (dom
);
2892 /* Note that we need to value_replace both NEW_SETS, and
2893 AVAIL_OUT. For both the case of NEW_SETS, the value may be
2894 represented by some non-simple expression here that we want
2895 to replace it with. */
2896 FOR_EACH_EXPR_ID_IN_SET (newset
, i
, bi
)
2898 tree expr
= expression_for_id (i
);
2899 bitmap_value_replace_in_set (NEW_SETS (block
), expr
);
2900 bitmap_value_replace_in_set (AVAIL_OUT (block
), expr
);
2903 if (!single_pred_p (block
))
2905 new_stuff
|= do_regular_insertion (block
, dom
);
2906 if (do_partial_partial
)
2907 new_stuff
|= do_partial_partial_insertion (block
, dom
);
2911 for (son
= first_dom_son (CDI_DOMINATORS
, block
);
2913 son
= next_dom_son (CDI_DOMINATORS
, son
))
2915 new_stuff
|= insert_aux (son
);
2921 /* Perform insertion of partially redundant values. */
2926 bool new_stuff
= true;
2928 int num_iterations
= 0;
2931 NEW_SETS (bb
) = bitmap_set_new ();
2937 new_stuff
= insert_aux (ENTRY_BLOCK_PTR
);
2939 if (num_iterations
> 2 && dump_file
&& (dump_flags
& TDF_STATS
))
2940 fprintf (dump_file
, "insert required %d iterations\n", num_iterations
);
2944 /* Add OP to EXP_GEN (block), and possibly to the maximal set if it is
2945 not defined by a phi node.
2946 PHI nodes can't go in the maximal sets because they are not in
2947 TMP_GEN, so it is possible to get into non-monotonic situations
2948 during ANTIC calculation, because it will *add* bits. */
2951 add_to_exp_gen (basic_block block
, tree op
)
2955 if (TREE_CODE (op
) == SSA_NAME
&& ssa_undefined_value_p (op
))
2957 bitmap_value_insert_into_set (EXP_GEN (block
), op
);
2958 if (TREE_CODE (op
) != SSA_NAME
2959 || TREE_CODE (SSA_NAME_DEF_STMT (op
)) != PHI_NODE
)
2960 bitmap_value_insert_into_set (maximal_set
, op
);
2965 /* Given an SSA variable VAR and an expression EXPR, compute the value
2966 number for EXPR and create a value handle (VAL) for it. If VAR and
2967 EXPR are not the same, associate VAL with VAR. Finally, add VAR to
2968 S1 and its value handle to S2, and to the maximal set if
2969 ADD_TO_MAXIMAL is true.
2971 VUSES represent the virtual use operands associated with EXPR (if
2975 add_to_sets (tree var
, tree expr
, VEC(tree
, gc
) *vuses
, bitmap_set_t s1
,
2979 val
= vn_lookup_or_add_with_vuses (expr
, vuses
);
2981 /* VAR and EXPR may be the same when processing statements for which
2982 we are not computing value numbers (e.g., non-assignments, or
2983 statements that make aliased stores). In those cases, we are
2984 only interested in making VAR available as its own value. */
2989 bitmap_insert_into_set (s1
, var
);
2991 bitmap_value_insert_into_set (s2
, var
);
2994 /* Find existing value expression that is the same as T,
2995 and return it if it exists. */
2998 find_existing_value_expr (tree t
, VEC (tree
, gc
) *vuses
)
3003 bitmap_set_t exprset
;
3005 if (REFERENCE_CLASS_P (t
) || TREE_CODE (t
) == CALL_EXPR
|| DECL_P (t
))
3006 vh
= vn_lookup_with_vuses (t
, vuses
);
3012 exprset
= VALUE_HANDLE_EXPR_SET (vh
);
3013 FOR_EACH_EXPR_ID_IN_SET (exprset
, bii
, bi
)
3015 tree efi
= expression_for_id (bii
);
3016 if (expressions_equal_p (t
, efi
))
3022 /* Given a unary or binary expression EXPR, create and return a new
3023 expression with the same structure as EXPR but with its operands
3024 replaced with the value handles of each of the operands of EXPR.
3026 VUSES represent the virtual use operands associated with EXPR (if
3027 any). Insert EXPR's operands into the EXP_GEN set for BLOCK.
3029 If CHECK_AVAIL is true, checks availability of each operand in
3030 BLOCKs AVAIL_OUT set. */
3033 create_value_expr_from (tree expr
, basic_block block
, VEC (tree
, gc
) *vuses
,
3037 enum tree_code code
= TREE_CODE (expr
);
3039 alloc_pool pool
= NULL
;
3042 gcc_assert (TREE_CODE_CLASS (code
) == tcc_unary
3043 || TREE_CODE_CLASS (code
) == tcc_binary
3044 || TREE_CODE_CLASS (code
) == tcc_comparison
3045 || TREE_CODE_CLASS (code
) == tcc_reference
3046 || TREE_CODE_CLASS (code
) == tcc_expression
3047 || TREE_CODE_CLASS (code
) == tcc_vl_exp
3048 || TREE_CODE_CLASS (code
) == tcc_exceptional
3049 || TREE_CODE_CLASS (code
) == tcc_declaration
);
3051 if (TREE_CODE_CLASS (code
) == tcc_unary
)
3052 pool
= unary_node_pool
;
3053 else if (TREE_CODE_CLASS (code
) == tcc_reference
)
3054 pool
= reference_node_pool
;
3055 else if (TREE_CODE_CLASS (code
) == tcc_binary
)
3056 pool
= binary_node_pool
;
3057 else if (TREE_CODE_CLASS (code
) == tcc_comparison
)
3058 pool
= comparison_node_pool
;
3060 gcc_assert (code
== CALL_EXPR
);
3062 if (code
== CALL_EXPR
)
3063 vexpr
= temp_copy_call_expr (expr
);
3066 vexpr
= (tree
) pool_alloc (pool
);
3067 memcpy (vexpr
, expr
, tree_size (expr
));
3070 for (i
= 0; i
< TREE_OPERAND_LENGTH (expr
); i
++)
3072 tree val
= NULL_TREE
;
3075 op
= TREE_OPERAND (expr
, i
);
3076 if (op
== NULL_TREE
)
3079 /* Recursively value-numberize reference ops and tree lists. */
3080 if (REFERENCE_CLASS_P (op
))
3082 tree tempop
= create_value_expr_from (op
, block
, vuses
, check_avail
);
3083 op
= tempop
? tempop
: op
;
3084 val
= vn_lookup_or_add_with_vuses (op
, vuses
);
3085 set_expression_vuses (op
, vuses
);
3089 val
= vn_lookup_or_add (op
);
3091 if (TREE_CODE (op
) != TREE_LIST
)
3092 add_to_exp_gen (block
, op
);
3094 if (TREE_CODE (val
) == VALUE_HANDLE
)
3095 TREE_TYPE (val
) = TREE_TYPE (TREE_OPERAND (vexpr
, i
));
3097 TREE_OPERAND (vexpr
, i
) = val
;
3100 && TREE_CODE (val
) == VALUE_HANDLE
3101 && !bitmap_set_contains_value (AVAIL_OUT (block
), val
))
3104 efi
= find_existing_value_expr (vexpr
, vuses
);
3107 get_or_alloc_expression_id (vexpr
);
3112 /* For each real store operation of the form
3113 *a = <value> that we see, create a corresponding fake store of the
3114 form storetmp_<version> = *a.
3116 This enables AVAIL computation to mark the results of stores as
3117 available. Without this, you'd need to do some computation to
3118 mark the result of stores as ANTIC and AVAIL at all the right
3120 To save memory, we keep the store
3121 statements pool allocated until we decide whether they are
3122 necessary or not. */
3125 insert_fake_stores (void)
3131 block_stmt_iterator bsi
;
3132 for (bsi
= bsi_start (block
); !bsi_end_p (bsi
); bsi_next (&bsi
))
3134 tree stmt
= bsi_stmt (bsi
);
3136 /* We can't generate SSA names for stores that are complex
3137 or aggregate. We also want to ignore things whose
3138 virtual uses occur in abnormal phis. */
3140 if (TREE_CODE (stmt
) == GIMPLE_MODIFY_STMT
3141 && (TREE_CODE (GIMPLE_STMT_OPERAND (stmt
, 0)) == INDIRECT_REF
3142 || handled_component_p (GIMPLE_STMT_OPERAND (stmt
, 0)))
3143 && !AGGREGATE_TYPE_P (TREE_TYPE (GIMPLE_STMT_OPERAND (stmt
, 0))))
3147 tree lhs
= GIMPLE_STMT_OPERAND (stmt
, 0);
3148 tree rhs
= GIMPLE_STMT_OPERAND (stmt
, 1);
3149 tree new_tree
, new_lhs
;
3150 bool notokay
= false;
3152 FOR_EACH_SSA_DEF_OPERAND (defp
, stmt
, iter
, SSA_OP_VIRTUAL_DEFS
)
3154 tree defvar
= DEF_FROM_PTR (defp
);
3155 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (defvar
))
3165 if (!storetemp
|| TREE_TYPE (rhs
) != TREE_TYPE (storetemp
))
3167 storetemp
= create_tmp_var (TREE_TYPE (rhs
), "storetmp");
3168 if (TREE_CODE (TREE_TYPE (storetemp
)) == VECTOR_TYPE
3169 || TREE_CODE (TREE_TYPE (storetemp
)) == COMPLEX_TYPE
)
3170 DECL_GIMPLE_REG_P (storetemp
) = 1;
3171 get_var_ann (storetemp
);
3174 new_tree
= build_gimple_modify_stmt (NULL_TREE
, lhs
);
3175 new_lhs
= make_ssa_name (storetemp
, new_tree
);
3176 GIMPLE_STMT_OPERAND (new_tree
, 0) = new_lhs
;
3178 create_ssa_artificial_load_stmt (new_tree
, stmt
, false);
3180 NECESSARY (new_tree
) = 0;
3181 VEC_safe_push (tree
, heap
, inserted_exprs
, new_tree
);
3182 VEC_safe_push (tree
, heap
, need_creation
, new_tree
);
3183 bsi_insert_after (&bsi
, new_tree
, BSI_NEW_STMT
);
3189 /* Turn the pool allocated fake stores that we created back into real
3190 GC allocated ones if they turned out to be necessary to PRE some
3194 realify_fake_stores (void)
3199 for (i
= 0; VEC_iterate (tree
, need_creation
, i
, stmt
); i
++)
3201 if (NECESSARY (stmt
))
3203 block_stmt_iterator bsi
, bsi2
;
3206 /* Mark the temp variable as referenced */
3207 add_referenced_var (SSA_NAME_VAR (GIMPLE_STMT_OPERAND (stmt
, 0)));
3209 /* Put the statement before the store in the IR stream
3210 as a plain ssa name copy. */
3211 bsi
= bsi_for_stmt (stmt
);
3213 rhs
= GIMPLE_STMT_OPERAND (bsi_stmt (bsi
), 1);
3214 GIMPLE_STMT_OPERAND (stmt
, 1) = rhs
;
3215 bsi2
= bsi_for_stmt (stmt
);
3216 bsi_remove (&bsi2
, true);
3217 bsi_insert_before (&bsi
, stmt
, BSI_SAME_STMT
);
3220 release_defs (stmt
);
3224 /* Given an SSA_NAME, see if SCCVN has a value number for it, and if
3225 so, return the value handle for this value number, creating it if
3227 Return NULL if SCCVN has no info for us. */
3230 get_sccvn_value (tree name
)
3232 if (TREE_CODE (name
) == SSA_NAME
3233 && VN_INFO (name
)->valnum
!= name
3234 && VN_INFO (name
)->valnum
!= VN_TOP
)
3236 tree val
= VN_INFO (name
)->valnum
;
3237 bool is_invariant
= is_gimple_min_invariant (val
);
3238 tree valvh
= !is_invariant
? get_value_handle (val
) : NULL_TREE
;
3240 /* We may end up with situations where SCCVN has chosen a
3241 representative for the equivalence set that we have not
3242 visited yet. In this case, just create the value handle for
3244 if (!valvh
&& !is_invariant
)
3246 /* We lookup with the LHS, so do not use vn_lookup_or_add_with_stmt
3247 here, as that will result in useless reference lookups. */
3248 valvh
= vn_lookup_or_add (val
);
3251 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3253 fprintf (dump_file
, "SCCVN says ");
3254 print_generic_expr (dump_file
, name
, 0);
3255 fprintf (dump_file
, " value numbers to ");
3256 if (valvh
&& !is_invariant
)
3258 print_generic_expr (dump_file
, val
, 0);
3259 fprintf (dump_file
, " (");
3260 print_generic_expr (dump_file
, valvh
, 0);
3261 fprintf (dump_file
, ")\n");
3264 print_generic_stmt (dump_file
, val
, 0);
3274 /* Create value handles for PHI in BLOCK. */
3277 make_values_for_phi (tree phi
, basic_block block
)
3279 tree result
= PHI_RESULT (phi
);
3280 /* We have no need for virtual phis, as they don't represent
3281 actual computations. */
3282 if (is_gimple_reg (result
))
3284 tree sccvnval
= get_sccvn_value (result
);
3287 vn_add (result
, sccvnval
);
3288 bitmap_insert_into_set (PHI_GEN (block
), result
);
3289 bitmap_value_insert_into_set (AVAIL_OUT (block
), result
);
3292 add_to_sets (result
, result
, NULL
,
3293 PHI_GEN (block
), AVAIL_OUT (block
));
3297 /* Create value handles for STMT in BLOCK. Return true if we handled
3301 make_values_for_stmt (tree stmt
, basic_block block
)
3304 tree lhs
= GIMPLE_STMT_OPERAND (stmt
, 0);
3305 tree rhs
= GIMPLE_STMT_OPERAND (stmt
, 1);
3306 tree valvh
= NULL_TREE
;
3308 VEC (tree
, gc
) *vuses
= NULL
;
3310 valvh
= get_sccvn_value (lhs
);
3314 vn_add (lhs
, valvh
);
3315 bitmap_value_insert_into_set (AVAIL_OUT (block
), lhs
);
3316 /* Shortcut for FRE. We have no need to create value expressions,
3317 just want to know what values are available where. */
3324 /* For FRE, if SCCVN didn't find anything, we aren't going to
3325 either, so just make up a new value number if necessary and
3327 if (get_value_handle (lhs
) == NULL
)
3328 vn_lookup_or_add (lhs
);
3329 bitmap_value_insert_into_set (AVAIL_OUT (block
), lhs
);
3333 lhsval
= valvh
? valvh
: get_value_handle (lhs
);
3334 vuses
= copy_vuses_from_stmt (stmt
);
3335 STRIP_USELESS_TYPE_CONVERSION (rhs
);
3336 if (can_value_number_operation (rhs
)
3337 && (!lhsval
|| !is_gimple_min_invariant (lhsval
))
3338 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
3340 /* For value numberable operation, create a
3341 duplicate expression with the operands replaced
3342 with the value handles of the original RHS. */
3343 tree newt
= create_value_expr_from (rhs
, block
, vuses
, false);
3346 set_expression_vuses (newt
, vuses
);
3347 /* If we already have a value number for the LHS, reuse
3348 it rather than creating a new one. */
3351 set_value_handle (newt
, lhsval
);
3352 if (!is_gimple_min_invariant (lhsval
))
3353 add_to_value (lhsval
, newt
);
3357 tree val
= vn_lookup_or_add_with_vuses (newt
, vuses
);
3361 add_to_exp_gen (block
, newt
);
3364 bitmap_insert_into_set (TMP_GEN (block
), lhs
);
3365 bitmap_value_insert_into_set (AVAIL_OUT (block
), lhs
);
3368 else if ((TREE_CODE (rhs
) == SSA_NAME
3369 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs
))
3370 || is_gimple_min_invariant (rhs
)
3371 || TREE_CODE (rhs
) == ADDR_EXPR
3377 set_expression_vuses (rhs
, vuses
);
3378 set_value_handle (rhs
, lhsval
);
3379 if (!is_gimple_min_invariant (lhsval
))
3380 add_to_value (lhsval
, rhs
);
3381 bitmap_insert_into_set (TMP_GEN (block
), lhs
);
3382 bitmap_value_insert_into_set (AVAIL_OUT (block
), lhs
);
3386 /* Compute a value number for the RHS of the statement
3387 and add its value to the AVAIL_OUT set for the block.
3388 Add the LHS to TMP_GEN. */
3389 set_expression_vuses (rhs
, vuses
);
3390 add_to_sets (lhs
, rhs
, vuses
, TMP_GEN (block
),
3393 /* None of the rest of these can be PRE'd. */
3394 if (TREE_CODE (rhs
) == SSA_NAME
&& !ssa_undefined_value_p (rhs
))
3395 add_to_exp_gen (block
, rhs
);
3402 /* Compute the AVAIL set for all basic blocks.
3404 This function performs value numbering of the statements in each basic
3405 block. The AVAIL sets are built from information we glean while doing
3406 this value numbering, since the AVAIL sets contain only one entry per
3409 AVAIL_IN[BLOCK] = AVAIL_OUT[dom(BLOCK)].
3410 AVAIL_OUT[BLOCK] = AVAIL_IN[BLOCK] U PHI_GEN[BLOCK] U TMP_GEN[BLOCK]. */
3413 compute_avail (void)
3415 basic_block block
, son
;
3416 basic_block
*worklist
;
3420 /* For arguments with default definitions, we pretend they are
3421 defined in the entry block. */
3422 for (param
= DECL_ARGUMENTS (current_function_decl
);
3424 param
= TREE_CHAIN (param
))
3426 if (gimple_default_def (cfun
, param
) != NULL
)
3428 tree def
= gimple_default_def (cfun
, param
);
3430 vn_lookup_or_add (def
);
3433 bitmap_insert_into_set (TMP_GEN (ENTRY_BLOCK_PTR
), def
);
3434 bitmap_value_insert_into_set (maximal_set
, def
);
3436 bitmap_value_insert_into_set (AVAIL_OUT (ENTRY_BLOCK_PTR
), def
);
3440 /* Likewise for the static chain decl. */
3441 if (cfun
->static_chain_decl
)
3443 param
= cfun
->static_chain_decl
;
3444 if (gimple_default_def (cfun
, param
) != NULL
)
3446 tree def
= gimple_default_def (cfun
, param
);
3448 vn_lookup_or_add (def
);
3451 bitmap_insert_into_set (TMP_GEN (ENTRY_BLOCK_PTR
), def
);
3452 bitmap_value_insert_into_set (maximal_set
, def
);
3454 bitmap_value_insert_into_set (AVAIL_OUT (ENTRY_BLOCK_PTR
), def
);
3458 /* Allocate the worklist. */
3459 worklist
= XNEWVEC (basic_block
, n_basic_blocks
);
3461 /* Seed the algorithm by putting the dominator children of the entry
3462 block on the worklist. */
3463 for (son
= first_dom_son (CDI_DOMINATORS
, ENTRY_BLOCK_PTR
);
3465 son
= next_dom_son (CDI_DOMINATORS
, son
))
3466 worklist
[sp
++] = son
;
3468 /* Loop until the worklist is empty. */
3471 block_stmt_iterator bsi
;
3474 unsigned int stmt_uid
= 1;
3476 /* Pick a block from the worklist. */
3477 block
= worklist
[--sp
];
3479 /* Initially, the set of available values in BLOCK is that of
3480 its immediate dominator. */
3481 dom
= get_immediate_dominator (CDI_DOMINATORS
, block
);
3483 bitmap_set_copy (AVAIL_OUT (block
), AVAIL_OUT (dom
));
3485 /* Generate values for PHI nodes. */
3486 for (phi
= phi_nodes (block
); phi
; phi
= PHI_CHAIN (phi
))
3487 make_values_for_phi (phi
, block
);
3489 /* Now compute value numbers and populate value sets with all
3490 the expressions computed in BLOCK. */
3491 for (bsi
= bsi_start (block
); !bsi_end_p (bsi
); bsi_next (&bsi
))
3497 stmt
= bsi_stmt (bsi
);
3498 ann
= stmt_ann (stmt
);
3500 ann
->uid
= stmt_uid
++;
3502 /* For regular value numbering, we are only interested in
3503 assignments of the form X_i = EXPR, where EXPR represents
3504 an "interesting" computation, it has no volatile operands
3505 and X_i doesn't flow through an abnormal edge. */
3506 if (TREE_CODE (stmt
) == RETURN_EXPR
3507 && !ann
->has_volatile_ops
)
3509 tree realstmt
= stmt
;
3513 stmt
= TREE_OPERAND (stmt
, 0);
3514 if (stmt
&& TREE_CODE (stmt
) == GIMPLE_MODIFY_STMT
)
3516 lhs
= GIMPLE_STMT_OPERAND (stmt
, 0);
3517 rhs
= GIMPLE_STMT_OPERAND (stmt
, 1);
3518 if (TREE_CODE (lhs
) == SSA_NAME
3519 && is_gimple_min_invariant (VN_INFO (lhs
)->valnum
))
3521 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3523 fprintf (dump_file
, "SCCVN says ");
3524 print_generic_expr (dump_file
, lhs
, 0);
3525 fprintf (dump_file
, " value numbers to ");
3526 print_generic_stmt (dump_file
, VN_INFO (lhs
)->valnum
,
3529 vn_add (lhs
, VN_INFO (lhs
)->valnum
);
3533 if (TREE_CODE (rhs
) == SSA_NAME
)
3534 add_to_exp_gen (block
, rhs
);
3536 FOR_EACH_SSA_TREE_OPERAND (op
, realstmt
, iter
, SSA_OP_DEF
)
3537 add_to_sets (op
, op
, NULL
, TMP_GEN (block
),
3543 else if (TREE_CODE (stmt
) == GIMPLE_MODIFY_STMT
3544 && !ann
->has_volatile_ops
3545 && TREE_CODE (GIMPLE_STMT_OPERAND (stmt
, 0)) == SSA_NAME
3546 && !tree_could_throw_p (stmt
))
3548 if (make_values_for_stmt (stmt
, block
))
3552 /* For any other statement that we don't recognize, simply
3553 make the names generated by the statement available in
3554 AVAIL_OUT and TMP_GEN. */
3555 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, iter
, SSA_OP_DEF
)
3556 add_to_sets (op
, op
, NULL
, TMP_GEN (block
), AVAIL_OUT (block
));
3558 /* Also add all referenced SSA_NAMEs to EXP_GEN. */
3559 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, iter
, SSA_OP_USE
)
3560 add_to_exp_gen (block
, op
);
3563 /* Put the dominator children of BLOCK on the worklist of blocks
3564 to compute available sets for. */
3565 for (son
= first_dom_son (CDI_DOMINATORS
, block
);
3567 son
= next_dom_son (CDI_DOMINATORS
, son
))
3568 worklist
[sp
++] = son
;
3574 /* Insert the expression for SSA_VN that SCCVN thought would be simpler
3575 than the available expressions for it. The insertion point is
3576 right before the first use in STMT. Returns the SSA_NAME that should
3577 be used for replacement. */
3580 do_SCCVN_insertion (tree stmt
, tree ssa_vn
)
3582 basic_block bb
= bb_for_stmt (stmt
);
3583 block_stmt_iterator bsi
;
3586 /* First create a value expression from the expression we want
3587 to insert and associate it with the value handle for SSA_VN. */
3588 expr
= create_value_expr_from (VN_INFO (ssa_vn
)->expr
, bb
, NULL
, true);
3589 if (expr
== NULL_TREE
)
3591 set_value_handle (expr
, get_value_handle (ssa_vn
));
3593 /* Then use create_expression_by_pieces to generate a valid
3594 expression to insert at this point of the IL stream. */
3595 stmts
= alloc_stmt_list ();
3596 expr
= create_expression_by_pieces (bb
, expr
, stmts
, stmt
);
3597 if (expr
== NULL_TREE
)
3599 bsi
= bsi_for_stmt (stmt
);
3600 bsi_insert_before (&bsi
, stmts
, BSI_SAME_STMT
);
3605 /* Eliminate fully redundant computations. */
3611 unsigned int todo
= 0;
3615 block_stmt_iterator i
;
3617 for (i
= bsi_start (b
); !bsi_end_p (i
); bsi_next (&i
))
3619 tree stmt
= bsi_stmt (i
);
3621 /* Lookup the RHS of the expression, see if we have an
3622 available computation for it. If so, replace the RHS with
3623 the available computation. */
3624 if (TREE_CODE (stmt
) == GIMPLE_MODIFY_STMT
3625 && TREE_CODE (GIMPLE_STMT_OPERAND (stmt
, 0)) == SSA_NAME
3626 && TREE_CODE (GIMPLE_STMT_OPERAND (stmt
, 1)) != SSA_NAME
3627 && !is_gimple_min_invariant (GIMPLE_STMT_OPERAND (stmt
, 1))
3628 && !stmt_ann (stmt
)->has_volatile_ops
)
3630 tree lhs
= GIMPLE_STMT_OPERAND (stmt
, 0);
3631 tree
*rhs_p
= &GIMPLE_STMT_OPERAND (stmt
, 1);
3634 sprime
= bitmap_find_leader (AVAIL_OUT (b
),
3635 get_value_handle (lhs
), NULL_TREE
);
3637 /* If there is no existing usable leader but SCCVN thinks
3638 it has an expression it wants to use as replacement,
3643 tree val
= VN_INFO (lhs
)->valnum
;
3645 && VN_INFO (val
)->needs_insertion
3646 && can_PRE_operation (VN_INFO (val
)->expr
))
3647 sprime
= do_SCCVN_insertion (stmt
, val
);
3652 && (TREE_CODE (*rhs_p
) != SSA_NAME
3653 || may_propagate_copy (*rhs_p
, sprime
)))
3655 gcc_assert (sprime
!= *rhs_p
);
3657 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3659 fprintf (dump_file
, "Replaced ");
3660 print_generic_expr (dump_file
, *rhs_p
, 0);
3661 fprintf (dump_file
, " with ");
3662 print_generic_expr (dump_file
, sprime
, 0);
3663 fprintf (dump_file
, " in ");
3664 print_generic_stmt (dump_file
, stmt
, 0);
3667 if (TREE_CODE (sprime
) == SSA_NAME
)
3668 NECESSARY (SSA_NAME_DEF_STMT (sprime
)) = 1;
3669 /* We need to make sure the new and old types actually match,
3670 which may require adding a simple cast, which fold_convert
3672 if (TREE_CODE (*rhs_p
) != SSA_NAME
3673 && !useless_type_conversion_p (TREE_TYPE (*rhs_p
),
3674 TREE_TYPE (sprime
)))
3675 sprime
= fold_convert (TREE_TYPE (*rhs_p
), sprime
);
3677 pre_stats
.eliminations
++;
3678 propagate_tree_value (rhs_p
, sprime
);
3681 /* If we removed EH side effects from the statement, clean
3682 its EH information. */
3683 if (maybe_clean_or_replace_eh_stmt (stmt
, stmt
))
3685 bitmap_set_bit (need_eh_cleanup
,
3686 bb_for_stmt (stmt
)->index
);
3687 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3688 fprintf (dump_file
, " Removed EH side effects.\n");
3692 /* Visit COND_EXPRs and fold the comparison with the
3693 available value-numbers. */
3694 else if (TREE_CODE (stmt
) == COND_EXPR
3695 && COMPARISON_CLASS_P (COND_EXPR_COND (stmt
)))
3697 tree cond
= COND_EXPR_COND (stmt
);
3698 tree op0
= TREE_OPERAND (cond
, 0);
3699 tree op1
= TREE_OPERAND (cond
, 1);
3702 if (TREE_CODE (op0
) == SSA_NAME
)
3703 op0
= VN_INFO (op0
)->valnum
;
3704 if (TREE_CODE (op1
) == SSA_NAME
)
3705 op1
= VN_INFO (op1
)->valnum
;
3706 result
= fold_binary (TREE_CODE (cond
), TREE_TYPE (cond
),
3708 if (result
&& TREE_CODE (result
) == INTEGER_CST
)
3710 COND_EXPR_COND (stmt
) = result
;
3712 todo
= TODO_cleanup_cfg
;
3715 else if (TREE_CODE (stmt
) == COND_EXPR
3716 && TREE_CODE (COND_EXPR_COND (stmt
)) == SSA_NAME
)
3718 tree op
= COND_EXPR_COND (stmt
);
3719 op
= VN_INFO (op
)->valnum
;
3720 if (TREE_CODE (op
) == INTEGER_CST
)
3722 COND_EXPR_COND (stmt
) = integer_zerop (op
)
3723 ? boolean_false_node
: boolean_true_node
;
3725 todo
= TODO_cleanup_cfg
;
3734 /* Borrow a bit of tree-ssa-dce.c for the moment.
3735 XXX: In 4.1, we should be able to just run a DCE pass after PRE, though
3736 this may be a bit faster, and we may want critical edges kept split. */
3738 /* If OP's defining statement has not already been determined to be necessary,
3739 mark that statement necessary. Return the stmt, if it is newly
3743 mark_operand_necessary (tree op
)
3749 if (TREE_CODE (op
) != SSA_NAME
)
3752 stmt
= SSA_NAME_DEF_STMT (op
);
3755 if (NECESSARY (stmt
)
3756 || IS_EMPTY_STMT (stmt
))
3759 NECESSARY (stmt
) = 1;
3763 /* Because we don't follow exactly the standard PRE algorithm, and decide not
3764 to insert PHI nodes sometimes, and because value numbering of casts isn't
3765 perfect, we sometimes end up inserting dead code. This simple DCE-like
3766 pass removes any insertions we made that weren't actually used. */
3769 remove_dead_inserted_code (void)
3771 VEC(tree
,heap
) *worklist
= NULL
;
3775 worklist
= VEC_alloc (tree
, heap
, VEC_length (tree
, inserted_exprs
));
3776 for (i
= 0; VEC_iterate (tree
, inserted_exprs
, i
, t
); i
++)
3779 VEC_quick_push (tree
, worklist
, t
);
3781 while (VEC_length (tree
, worklist
) > 0)
3783 t
= VEC_pop (tree
, worklist
);
3785 /* PHI nodes are somewhat special in that each PHI alternative has
3786 data and control dependencies. All the statements feeding the
3787 PHI node's arguments are always necessary. */
3788 if (TREE_CODE (t
) == PHI_NODE
)
3792 VEC_reserve (tree
, heap
, worklist
, PHI_NUM_ARGS (t
));
3793 for (k
= 0; k
< PHI_NUM_ARGS (t
); k
++)
3795 tree arg
= PHI_ARG_DEF (t
, k
);
3796 if (TREE_CODE (arg
) == SSA_NAME
)
3798 arg
= mark_operand_necessary (arg
);
3800 VEC_quick_push (tree
, worklist
, arg
);
3806 /* Propagate through the operands. Examine all the USE, VUSE and
3807 VDEF operands in this statement. Mark all the statements
3808 which feed this statement's uses as necessary. */
3812 /* The operands of VDEF expressions are also needed as they
3813 represent potential definitions that may reach this
3814 statement (VDEF operands allow us to follow def-def
3817 FOR_EACH_SSA_TREE_OPERAND (use
, t
, iter
, SSA_OP_ALL_USES
)
3819 tree n
= mark_operand_necessary (use
);
3821 VEC_safe_push (tree
, heap
, worklist
, n
);
3826 for (i
= 0; VEC_iterate (tree
, inserted_exprs
, i
, t
); i
++)
3830 block_stmt_iterator bsi
;
3832 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3834 fprintf (dump_file
, "Removing unnecessary insertion:");
3835 print_generic_stmt (dump_file
, t
, 0);
3838 if (TREE_CODE (t
) == PHI_NODE
)
3840 remove_phi_node (t
, NULL
, true);
3844 bsi
= bsi_for_stmt (t
);
3845 bsi_remove (&bsi
, true);
3850 VEC_free (tree
, heap
, worklist
);
3853 /* Initialize data structures used by PRE. */
3856 init_pre (bool do_fre
)
3860 next_expression_id
= 0;
3862 expression_vuses
= NULL
;
3865 inserted_exprs
= NULL
;
3866 need_creation
= NULL
;
3867 pretemp
= NULL_TREE
;
3868 storetemp
= NULL_TREE
;
3869 prephitemp
= NULL_TREE
;
3872 loop_optimizer_init (LOOPS_NORMAL
);
3874 connect_infinite_loops_to_exit ();
3875 memset (&pre_stats
, 0, sizeof (pre_stats
));
3878 postorder
= XNEWVEC (int, n_basic_blocks
- NUM_FIXED_BLOCKS
);
3879 post_order_compute (postorder
, false, false);
3882 bb
->aux
= xcalloc (1, sizeof (struct bb_bitmap_sets
));
3884 calculate_dominance_info (CDI_POST_DOMINATORS
);
3885 calculate_dominance_info (CDI_DOMINATORS
);
3887 bitmap_obstack_initialize (&grand_bitmap_obstack
);
3888 phi_translate_table
= htab_create (5110, expr_pred_trans_hash
,
3889 expr_pred_trans_eq
, free
);
3890 seen_during_translate
= BITMAP_ALLOC (&grand_bitmap_obstack
);
3891 bitmap_set_pool
= create_alloc_pool ("Bitmap sets",
3892 sizeof (struct bitmap_set
), 30);
3893 binary_node_pool
= create_alloc_pool ("Binary tree nodes",
3894 tree_code_size (PLUS_EXPR
), 30);
3895 unary_node_pool
= create_alloc_pool ("Unary tree nodes",
3896 tree_code_size (NEGATE_EXPR
), 30);
3897 reference_node_pool
= create_alloc_pool ("Reference tree nodes",
3898 tree_code_size (ARRAY_REF
), 30);
3899 comparison_node_pool
= create_alloc_pool ("Comparison tree nodes",
3900 tree_code_size (EQ_EXPR
), 30);
3901 obstack_init (&temp_call_expr_obstack
);
3905 EXP_GEN (bb
) = bitmap_set_new ();
3906 PHI_GEN (bb
) = bitmap_set_new ();
3907 TMP_GEN (bb
) = bitmap_set_new ();
3908 AVAIL_OUT (bb
) = bitmap_set_new ();
3910 maximal_set
= in_fre
? NULL
: bitmap_set_new ();
3912 need_eh_cleanup
= BITMAP_ALLOC (NULL
);
3916 /* Deallocate data structures used by PRE. */
3925 VEC_free (tree
, heap
, inserted_exprs
);
3926 VEC_free (tree
, heap
, need_creation
);
3927 bitmap_obstack_release (&grand_bitmap_obstack
);
3928 free_alloc_pool (bitmap_set_pool
);
3929 free_alloc_pool (binary_node_pool
);
3930 free_alloc_pool (reference_node_pool
);
3931 free_alloc_pool (unary_node_pool
);
3932 free_alloc_pool (comparison_node_pool
);
3933 htab_delete (phi_translate_table
);
3934 remove_fake_exit_edges ();
3942 free_dominance_info (CDI_POST_DOMINATORS
);
3944 if (!bitmap_empty_p (need_eh_cleanup
))
3946 tree_purge_all_dead_eh_edges (need_eh_cleanup
);
3947 cleanup_tree_cfg ();
3950 BITMAP_FREE (need_eh_cleanup
);
3952 /* Wipe out pointers to VALUE_HANDLEs. In the not terribly distant
3953 future we will want them to be persistent though. */
3954 for (i
= 0; i
< num_ssa_names
; i
++)
3956 tree name
= ssa_name (i
);
3961 if (SSA_NAME_VALUE (name
)
3962 && TREE_CODE (SSA_NAME_VALUE (name
)) == VALUE_HANDLE
)
3963 SSA_NAME_VALUE (name
) = NULL
;
3965 if (current_loops
!= NULL
)
3966 loop_optimizer_finalize ();
3969 /* Main entry point to the SSA-PRE pass. DO_FRE is true if the caller
3970 only wants to do full redundancy elimination. */
3973 execute_pre (bool do_fre
)
3975 unsigned int todo
= 0;
3977 do_partial_partial
= optimize
> 2;
3981 insert_fake_stores ();
3983 /* Collect and value number expressions computed in each basic block. */
3984 if (!run_scc_vn (do_fre
))
3987 remove_dead_inserted_code ();
3991 switch_to_PRE_table ();
3994 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4000 print_bitmap_set (dump_file
, EXP_GEN (bb
), "exp_gen", bb
->index
);
4001 print_bitmap_set (dump_file
, TMP_GEN (bb
), "tmp_gen",
4003 print_bitmap_set (dump_file
, AVAIL_OUT (bb
), "avail_out",
4008 /* Insert can get quite slow on an incredibly large number of basic
4009 blocks due to some quadratic behavior. Until this behavior is
4010 fixed, don't run it when he have an incredibly large number of
4011 bb's. If we aren't going to run insert, there is no point in
4012 computing ANTIC, either, even though it's plenty fast. */
4013 if (!do_fre
&& n_basic_blocks
< 4000)
4019 /* Remove all the redundant expressions. */
4020 todo
|= eliminate ();
4022 if (dump_file
&& (dump_flags
& TDF_STATS
))
4024 fprintf (dump_file
, "Insertions: %d\n", pre_stats
.insertions
);
4025 fprintf (dump_file
, "PA inserted: %d\n", pre_stats
.pa_insert
);
4026 fprintf (dump_file
, "New PHIs: %d\n", pre_stats
.phis
);
4027 fprintf (dump_file
, "Eliminated: %d\n", pre_stats
.eliminations
);
4028 fprintf (dump_file
, "Constified: %d\n", pre_stats
.constified
);
4030 bsi_commit_edge_inserts ();
4032 clear_expression_ids ();
4036 remove_dead_inserted_code ();
4037 realify_fake_stores ();
4045 /* Gate and execute functions for PRE. */
4050 return TODO_rebuild_alias
| execute_pre (false);
4056 return flag_tree_pre
!= 0;
4059 struct gimple_opt_pass pass_pre
=
4064 gate_pre
, /* gate */
4065 do_pre
, /* execute */
4068 0, /* static_pass_number */
4069 TV_TREE_PRE
, /* tv_id */
4070 PROP_no_crit_edges
| PROP_cfg
4071 | PROP_ssa
| PROP_alias
, /* properties_required */
4072 0, /* properties_provided */
4073 0, /* properties_destroyed */
4074 0, /* todo_flags_start */
4075 TODO_update_ssa_only_virtuals
| TODO_dump_func
| TODO_ggc_collect
4076 | TODO_verify_ssa
/* todo_flags_finish */
4081 /* Gate and execute functions for FRE. */
4086 return execute_pre (true);
4092 return flag_tree_fre
!= 0;
4095 struct gimple_opt_pass pass_fre
=
4100 gate_fre
, /* gate */
4101 execute_fre
, /* execute */
4104 0, /* static_pass_number */
4105 TV_TREE_FRE
, /* tv_id */
4106 PROP_cfg
| PROP_ssa
| PROP_alias
, /* properties_required */
4107 0, /* properties_provided */
4108 0, /* properties_destroyed */
4109 0, /* todo_flags_start */
4110 TODO_dump_func
| TODO_ggc_collect
| TODO_verify_ssa
/* todo_flags_finish */