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 /* Initialize data structures used for ANTIC and AVAIL. */
1977 next_expression_id
= 0;
1979 expression_vuses
= NULL
;
1981 postorder
= XNEWVEC (int, n_basic_blocks
- NUM_FIXED_BLOCKS
);
1982 post_order_compute (postorder
, false, false);
1984 bitmap_obstack_initialize (&grand_bitmap_obstack
);
1985 obstack_init (&temp_call_expr_obstack
);
1986 seen_during_translate
= BITMAP_ALLOC (&grand_bitmap_obstack
);
1988 bitmap_set_pool
= create_alloc_pool ("Bitmap sets",
1989 sizeof (struct bitmap_set
), 30);
1990 binary_node_pool
= create_alloc_pool ("Binary tree nodes",
1991 tree_code_size (PLUS_EXPR
), 30);
1992 unary_node_pool
= create_alloc_pool ("Unary tree nodes",
1993 tree_code_size (NEGATE_EXPR
), 30);
1994 reference_node_pool
= create_alloc_pool ("Reference tree nodes",
1995 tree_code_size (ARRAY_REF
), 30);
1996 comparison_node_pool
= create_alloc_pool ("Comparison tree nodes",
1997 tree_code_size (EQ_EXPR
), 30);
1999 phi_translate_table
= htab_create (5110, expr_pred_trans_hash
,
2000 expr_pred_trans_eq
, free
);
2001 maximal_set
= in_fre
? NULL
: bitmap_set_new ();
2005 bb
->aux
= xcalloc (1, sizeof (struct bb_bitmap_sets
));
2006 EXP_GEN (bb
) = bitmap_set_new ();
2007 PHI_GEN (bb
) = bitmap_set_new ();
2008 TMP_GEN (bb
) = bitmap_set_new ();
2009 AVAIL_OUT (bb
) = bitmap_set_new ();
2013 /* Deinitialize data structures used for ANTIC and AVAIL. */
2021 bitmap_set_free (maximal_set
);
2023 bitmap_obstack_release (&grand_bitmap_obstack
);
2024 free_alloc_pool (bitmap_set_pool
);
2025 free_alloc_pool (binary_node_pool
);
2026 free_alloc_pool (reference_node_pool
);
2027 free_alloc_pool (unary_node_pool
);
2028 free_alloc_pool (comparison_node_pool
);
2037 /* Compute ANTIC and partial ANTIC sets. */
2040 compute_antic (void)
2042 bool changed
= true;
2043 int num_iterations
= 0;
2047 /* If any predecessor edges are abnormal, we punt, so antic_in is empty.
2048 We pre-build the map of blocks with incoming abnormal edges here. */
2049 has_abnormal_preds
= sbitmap_alloc (last_basic_block
);
2050 sbitmap_zero (has_abnormal_preds
);
2057 FOR_EACH_EDGE (e
, ei
, block
->preds
)
2059 e
->flags
&= ~EDGE_DFS_BACK
;
2060 if (e
->flags
& EDGE_ABNORMAL
)
2062 SET_BIT (has_abnormal_preds
, block
->index
);
2067 BB_VISITED (block
) = 0;
2068 BB_DEFERRED (block
) = 0;
2069 /* While we are here, give empty ANTIC_IN sets to each block. */
2070 ANTIC_IN (block
) = bitmap_set_new ();
2071 PA_IN (block
) = bitmap_set_new ();
2074 /* At the exit block we anticipate nothing. */
2075 ANTIC_IN (EXIT_BLOCK_PTR
) = bitmap_set_new ();
2076 BB_VISITED (EXIT_BLOCK_PTR
) = 1;
2077 PA_IN (EXIT_BLOCK_PTR
) = bitmap_set_new ();
2079 changed_blocks
= sbitmap_alloc (last_basic_block
+ 1);
2080 sbitmap_ones (changed_blocks
);
2083 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2084 fprintf (dump_file
, "Starting iteration %d\n", num_iterations
);
2087 for (i
= 0; i
< last_basic_block
- NUM_FIXED_BLOCKS
; i
++)
2089 if (TEST_BIT (changed_blocks
, postorder
[i
]))
2091 basic_block block
= BASIC_BLOCK (postorder
[i
]);
2092 changed
|= compute_antic_aux (block
,
2093 TEST_BIT (has_abnormal_preds
,
2097 #ifdef ENABLE_CHECKING
2098 /* Theoretically possible, but *highly* unlikely. */
2099 gcc_assert (num_iterations
< 500);
2103 statistics_histogram_event (cfun
, "compute_antic iterations",
2106 if (do_partial_partial
)
2108 sbitmap_ones (changed_blocks
);
2109 mark_dfs_back_edges ();
2114 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2115 fprintf (dump_file
, "Starting iteration %d\n", num_iterations
);
2118 for (i
= 0; i
< last_basic_block
- NUM_FIXED_BLOCKS
; i
++)
2120 if (TEST_BIT (changed_blocks
, postorder
[i
]))
2122 basic_block block
= BASIC_BLOCK (postorder
[i
]);
2124 |= compute_partial_antic_aux (block
,
2125 TEST_BIT (has_abnormal_preds
,
2129 #ifdef ENABLE_CHECKING
2130 /* Theoretically possible, but *highly* unlikely. */
2131 gcc_assert (num_iterations
< 500);
2134 statistics_histogram_event (cfun
, "compute_partial_antic iterations",
2137 sbitmap_free (has_abnormal_preds
);
2138 sbitmap_free (changed_blocks
);
2141 /* Return true if we can value number the call in STMT. This is true
2142 if we have a pure or constant call. */
2145 can_value_number_call (tree stmt
)
2147 tree call
= get_call_expr_in (stmt
);
2149 if (call_expr_flags (call
) & (ECF_PURE
| ECF_CONST
))
2154 /* Return true if OP is an exception handler related operation, such as
2155 FILTER_EXPR or EXC_PTR_EXPR. */
2158 is_exception_related (tree op
)
2160 return TREE_CODE (op
) == FILTER_EXPR
|| TREE_CODE (op
) == EXC_PTR_EXPR
;
2163 /* Return true if OP is a tree which we can perform value numbering
2167 can_value_number_operation (tree op
)
2169 return (UNARY_CLASS_P (op
)
2170 && !is_exception_related (TREE_OPERAND (op
, 0)))
2171 || BINARY_CLASS_P (op
)
2172 || COMPARISON_CLASS_P (op
)
2173 || REFERENCE_CLASS_P (op
)
2174 || (TREE_CODE (op
) == CALL_EXPR
2175 && can_value_number_call (op
));
2179 /* Return true if OP is a tree which we can perform PRE on
2180 on. This may not match the operations we can value number, but in
2181 a perfect world would. */
2184 can_PRE_operation (tree op
)
2186 return UNARY_CLASS_P (op
)
2187 || BINARY_CLASS_P (op
)
2188 || COMPARISON_CLASS_P (op
)
2189 || TREE_CODE (op
) == INDIRECT_REF
2190 || TREE_CODE (op
) == COMPONENT_REF
2191 || TREE_CODE (op
) == VIEW_CONVERT_EXPR
2192 || TREE_CODE (op
) == CALL_EXPR
2193 || TREE_CODE (op
) == ARRAY_REF
;
2197 /* Inserted expressions are placed onto this worklist, which is used
2198 for performing quick dead code elimination of insertions we made
2199 that didn't turn out to be necessary. */
2200 static VEC(tree
,heap
) *inserted_exprs
;
2202 /* Pool allocated fake store expressions are placed onto this
2203 worklist, which, after performing dead code elimination, is walked
2204 to see which expressions need to be put into GC'able memory */
2205 static VEC(tree
, heap
) *need_creation
;
2207 /* For COMPONENT_REF's and ARRAY_REF's, we can't have any intermediates for the
2208 COMPONENT_REF or INDIRECT_REF or ARRAY_REF portion, because we'd end up with
2209 trying to rename aggregates into ssa form directly, which is a no
2212 Thus, this routine doesn't create temporaries, it just builds a
2213 single access expression for the array, calling
2214 find_or_generate_expression to build the innermost pieces.
2216 This function is a subroutine of create_expression_by_pieces, and
2217 should not be called on it's own unless you really know what you
2221 create_component_ref_by_pieces (basic_block block
, tree expr
, tree stmts
,
2227 if (TREE_CODE (genop
) == VALUE_HANDLE
)
2229 tree found
= bitmap_find_leader (AVAIL_OUT (block
), expr
, domstmt
);
2234 if (TREE_CODE (genop
) == VALUE_HANDLE
)
2236 bitmap_set_t exprset
= VALUE_HANDLE_EXPR_SET (expr
);
2237 unsigned int firstbit
= bitmap_first_set_bit (exprset
->expressions
);
2238 genop
= expression_for_id (firstbit
);
2241 switch TREE_CODE (genop
)
2247 op0
= create_component_ref_by_pieces (block
,
2248 TREE_OPERAND (genop
, 0),
2250 op1
= TREE_OPERAND (genop
, 1);
2251 if (TREE_CODE (op1
) == VALUE_HANDLE
)
2252 op1
= find_or_generate_expression (block
, op1
, stmts
, domstmt
);
2253 op2
= TREE_OPERAND (genop
, 2);
2254 if (op2
&& TREE_CODE (op2
) == VALUE_HANDLE
)
2255 op2
= find_or_generate_expression (block
, op2
, stmts
, domstmt
);
2256 op3
= TREE_OPERAND (genop
, 3);
2257 if (op3
&& TREE_CODE (op3
) == VALUE_HANDLE
)
2258 op3
= find_or_generate_expression (block
, op3
, stmts
, domstmt
);
2261 folded
= build4 (ARRAY_REF
, TREE_TYPE (genop
), op0
, op1
,
2269 op0
= create_component_ref_by_pieces (block
,
2270 TREE_OPERAND (genop
, 0),
2274 /* op1 should be a FIELD_DECL, which are represented by
2276 op1
= TREE_OPERAND (genop
, 1);
2277 folded
= fold_build3 (COMPONENT_REF
, TREE_TYPE (genop
), op0
, op1
,
2284 tree op1
= TREE_OPERAND (genop
, 0);
2285 tree genop1
= find_or_generate_expression (block
, op1
, stmts
, domstmt
);
2289 folded
= fold_build1 (TREE_CODE (genop
), TREE_TYPE (genop
),
2307 /* Find a leader for an expression, or generate one using
2308 create_expression_by_pieces if it's ANTIC but
2310 BLOCK is the basic_block we are looking for leaders in.
2311 EXPR is the expression to find a leader or generate for.
2312 STMTS is the statement list to put the inserted expressions on.
2313 Returns the SSA_NAME of the LHS of the generated expression or the
2315 DOMSTMT if non-NULL is a statement that should be dominated by
2316 all uses in the generated expression. If DOMSTMT is non-NULL this
2317 routine can fail and return NULL_TREE. Otherwise it will assert
2321 find_or_generate_expression (basic_block block
, tree expr
, tree stmts
,
2324 tree genop
= bitmap_find_leader (AVAIL_OUT (block
), expr
, domstmt
);
2326 /* If it's still NULL, it must be a complex expression, so generate
2330 bitmap_set_t exprset
= VALUE_HANDLE_EXPR_SET (expr
);
2331 bool handled
= false;
2335 /* We will hit cases where we have SSA_NAME's in exprset before
2336 other operations, because we may have come up with the SCCVN
2337 value before getting to the RHS of the expression. */
2338 FOR_EACH_EXPR_ID_IN_SET (exprset
, i
, bi
)
2340 genop
= expression_for_id (i
);
2341 if (can_PRE_operation (genop
))
2344 genop
= create_expression_by_pieces (block
, genop
, stmts
,
2349 if (!handled
&& domstmt
)
2352 gcc_assert (handled
);
2357 #define NECESSARY(stmt) stmt->base.asm_written_flag
2358 /* Create an expression in pieces, so that we can handle very complex
2359 expressions that may be ANTIC, but not necessary GIMPLE.
2360 BLOCK is the basic block the expression will be inserted into,
2361 EXPR is the expression to insert (in value form)
2362 STMTS is a statement list to append the necessary insertions into.
2364 This function will die if we hit some value that shouldn't be
2365 ANTIC but is (IE there is no leader for it, or its components).
2366 This function may also generate expressions that are themselves
2367 partially or fully redundant. Those that are will be either made
2368 fully redundant during the next iteration of insert (for partially
2369 redundant ones), or eliminated by eliminate (for fully redundant
2372 If DOMSTMT is non-NULL then we make sure that all uses in the
2373 expressions dominate that statement. In this case the function
2374 can return NULL_TREE to signal failure. */
2377 create_expression_by_pieces (basic_block block
, tree expr
, tree stmts
,
2381 tree folded
, forced_stmts
, newexpr
;
2383 tree_stmt_iterator tsi
;
2385 switch (TREE_CODE_CLASS (TREE_CODE (expr
)))
2394 gcc_assert (TREE_CODE (expr
) == CALL_EXPR
);
2396 fn
= CALL_EXPR_FN (expr
);
2397 sc
= CALL_EXPR_STATIC_CHAIN (expr
);
2399 genfn
= find_or_generate_expression (block
, fn
, stmts
, domstmt
);
2403 nargs
= call_expr_nargs (expr
);
2404 buffer
= (tree
*) alloca (nargs
* sizeof (tree
));
2406 for (i
= 0; i
< nargs
; i
++)
2408 tree arg
= CALL_EXPR_ARG (expr
, i
);
2409 buffer
[i
] = find_or_generate_expression (block
, arg
, stmts
,
2415 folded
= build_call_array (TREE_TYPE (expr
), genfn
, nargs
, buffer
);
2418 CALL_EXPR_STATIC_CHAIN (folded
) =
2419 find_or_generate_expression (block
, sc
, stmts
, domstmt
);
2420 if (!CALL_EXPR_STATIC_CHAIN (folded
))
2423 folded
= fold (folded
);
2429 if (TREE_CODE (expr
) == COMPONENT_REF
2430 || TREE_CODE (expr
) == ARRAY_REF
)
2432 folded
= create_component_ref_by_pieces (block
, expr
, stmts
,
2439 tree op1
= TREE_OPERAND (expr
, 0);
2440 tree genop1
= find_or_generate_expression (block
, op1
, stmts
,
2445 folded
= fold_build1 (TREE_CODE (expr
), TREE_TYPE (expr
),
2452 case tcc_comparison
:
2454 tree op1
= TREE_OPERAND (expr
, 0);
2455 tree op2
= TREE_OPERAND (expr
, 1);
2456 tree genop1
= find_or_generate_expression (block
, op1
, stmts
, domstmt
);
2457 tree genop2
= find_or_generate_expression (block
, op2
, stmts
, domstmt
);
2458 if (!genop1
|| !genop2
)
2460 folded
= fold_build2 (TREE_CODE (expr
), TREE_TYPE (expr
),
2467 tree op1
= TREE_OPERAND (expr
, 0);
2468 tree genop1
= find_or_generate_expression (block
, op1
, stmts
, domstmt
);
2471 folded
= fold_build1 (TREE_CODE (expr
), TREE_TYPE (expr
),
2480 /* Force the generated expression to be a sequence of GIMPLE
2482 We have to call unshare_expr because force_gimple_operand may
2483 modify the tree we pass to it. */
2484 newexpr
= force_gimple_operand (unshare_expr (folded
), &forced_stmts
,
2487 /* If we have any intermediate expressions to the value sets, add them
2488 to the value sets and chain them in the instruction stream. */
2491 tsi
= tsi_start (forced_stmts
);
2492 for (; !tsi_end_p (tsi
); tsi_next (&tsi
))
2494 tree stmt
= tsi_stmt (tsi
);
2495 tree forcedname
= GIMPLE_STMT_OPERAND (stmt
, 0);
2496 tree forcedexpr
= GIMPLE_STMT_OPERAND (stmt
, 1);
2497 tree val
= vn_lookup_or_add (forcedexpr
);
2499 VEC_safe_push (tree
, heap
, inserted_exprs
, stmt
);
2500 VN_INFO_GET (forcedname
)->valnum
= forcedname
;
2501 vn_add (forcedname
, val
);
2502 bitmap_value_replace_in_set (NEW_SETS (block
), forcedname
);
2503 bitmap_value_replace_in_set (AVAIL_OUT (block
), forcedname
);
2504 mark_symbols_for_renaming (stmt
);
2506 tsi
= tsi_last (stmts
);
2507 tsi_link_after (&tsi
, forced_stmts
, TSI_CONTINUE_LINKING
);
2510 /* Build and insert the assignment of the end result to the temporary
2511 that we will return. */
2512 if (!pretemp
|| TREE_TYPE (expr
) != TREE_TYPE (pretemp
))
2514 pretemp
= create_tmp_var (TREE_TYPE (expr
), "pretmp");
2515 get_var_ann (pretemp
);
2519 add_referenced_var (temp
);
2521 if (TREE_CODE (TREE_TYPE (expr
)) == COMPLEX_TYPE
2522 || TREE_CODE (TREE_TYPE (expr
)) == VECTOR_TYPE
)
2523 DECL_GIMPLE_REG_P (temp
) = 1;
2525 newexpr
= build_gimple_modify_stmt (temp
, newexpr
);
2526 name
= make_ssa_name (temp
, newexpr
);
2527 GIMPLE_STMT_OPERAND (newexpr
, 0) = name
;
2528 NECESSARY (newexpr
) = 0;
2530 tsi
= tsi_last (stmts
);
2531 tsi_link_after (&tsi
, newexpr
, TSI_CONTINUE_LINKING
);
2532 VEC_safe_push (tree
, heap
, inserted_exprs
, newexpr
);
2534 /* All the symbols in NEWEXPR should be put into SSA form. */
2535 mark_symbols_for_renaming (newexpr
);
2537 /* Add a value handle to the temporary.
2538 The value may already exist in either NEW_SETS, or AVAIL_OUT, because
2539 we are creating the expression by pieces, and this particular piece of
2540 the expression may have been represented. There is no harm in replacing
2542 v
= get_value_handle (expr
);
2544 VN_INFO_GET (name
)->valnum
= name
;
2545 get_or_alloc_expression_id (name
);
2547 bitmap_value_replace_in_set (NEW_SETS (block
), name
);
2548 bitmap_value_replace_in_set (AVAIL_OUT (block
), name
);
2550 pre_stats
.insertions
++;
2551 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2553 fprintf (dump_file
, "Inserted ");
2554 print_generic_expr (dump_file
, newexpr
, 0);
2555 fprintf (dump_file
, " in predecessor %d\n", block
->index
);
2561 /* Insert the to-be-made-available values of expression EXPRNUM for each
2562 predecessor, stored in AVAIL, into the predecessors of BLOCK, and
2563 merge the result with a phi node, given the same value handle as
2564 NODE. Return true if we have inserted new stuff. */
2567 insert_into_preds_of_block (basic_block block
, unsigned int exprnum
,
2570 tree expr
= expression_for_id (exprnum
);
2571 tree val
= get_value_handle (expr
);
2573 bool insertions
= false;
2578 tree type
= TREE_TYPE (avail
[EDGE_PRED (block
, 0)->src
->index
]);
2581 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2583 fprintf (dump_file
, "Found partial redundancy for expression ");
2584 print_generic_expr (dump_file
, expr
, 0);
2585 fprintf (dump_file
, " (");
2586 print_generic_expr (dump_file
, val
, 0);
2587 fprintf (dump_file
, ")");
2588 fprintf (dump_file
, "\n");
2591 /* Make sure we aren't creating an induction variable. */
2592 if (block
->loop_depth
> 0 && EDGE_COUNT (block
->preds
) == 2
2593 && TREE_CODE_CLASS (TREE_CODE (expr
)) != tcc_reference
)
2595 bool firstinsideloop
= false;
2596 bool secondinsideloop
= false;
2597 firstinsideloop
= flow_bb_inside_loop_p (block
->loop_father
,
2598 EDGE_PRED (block
, 0)->src
);
2599 secondinsideloop
= flow_bb_inside_loop_p (block
->loop_father
,
2600 EDGE_PRED (block
, 1)->src
);
2601 /* Induction variables only have one edge inside the loop. */
2602 if (firstinsideloop
^ secondinsideloop
)
2604 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2605 fprintf (dump_file
, "Skipping insertion of phi for partial redundancy: Looks like an induction variable\n");
2611 /* Make the necessary insertions. */
2612 FOR_EACH_EDGE (pred
, ei
, block
->preds
)
2614 tree stmts
= alloc_stmt_list ();
2617 eprime
= avail
[bprime
->index
];
2619 if (can_PRE_operation (eprime
))
2621 builtexpr
= create_expression_by_pieces (bprime
,
2624 gcc_assert (!(pred
->flags
& EDGE_ABNORMAL
));
2625 bsi_insert_on_edge (pred
, stmts
);
2626 avail
[bprime
->index
] = builtexpr
;
2630 /* If we didn't want a phi node, and we made insertions, we still have
2631 inserted new stuff, and thus return true. If we didn't want a phi node,
2632 and didn't make insertions, we haven't added anything new, so return
2634 if (nophi
&& insertions
)
2636 else if (nophi
&& !insertions
)
2639 /* Now build a phi for the new variable. */
2640 if (!prephitemp
|| TREE_TYPE (prephitemp
) != type
)
2642 prephitemp
= create_tmp_var (type
, "prephitmp");
2643 get_var_ann (prephitemp
);
2647 add_referenced_var (temp
);
2650 if (TREE_CODE (type
) == COMPLEX_TYPE
2651 || TREE_CODE (type
) == VECTOR_TYPE
)
2652 DECL_GIMPLE_REG_P (temp
) = 1;
2653 temp
= create_phi_node (temp
, block
);
2655 NECESSARY (temp
) = 0;
2656 VN_INFO_GET (PHI_RESULT (temp
))->valnum
= PHI_RESULT (temp
);
2658 VEC_safe_push (tree
, heap
, inserted_exprs
, temp
);
2659 FOR_EACH_EDGE (pred
, ei
, block
->preds
)
2660 add_phi_arg (temp
, avail
[pred
->src
->index
], pred
);
2662 vn_add (PHI_RESULT (temp
), val
);
2664 /* The value should *not* exist in PHI_GEN, or else we wouldn't be doing
2665 this insertion, since we test for the existence of this value in PHI_GEN
2666 before proceeding with the partial redundancy checks in insert_aux.
2668 The value may exist in AVAIL_OUT, in particular, it could be represented
2669 by the expression we are trying to eliminate, in which case we want the
2670 replacement to occur. If it's not existing in AVAIL_OUT, we want it
2673 Similarly, to the PHI_GEN case, the value should not exist in NEW_SETS of
2674 this block, because if it did, it would have existed in our dominator's
2675 AVAIL_OUT, and would have been skipped due to the full redundancy check.
2678 bitmap_insert_into_set (PHI_GEN (block
),
2680 bitmap_value_replace_in_set (AVAIL_OUT (block
),
2682 bitmap_insert_into_set (NEW_SETS (block
),
2685 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2687 fprintf (dump_file
, "Created phi ");
2688 print_generic_expr (dump_file
, temp
, 0);
2689 fprintf (dump_file
, " in block %d\n", block
->index
);
2697 /* Perform insertion of partially redundant values.
2698 For BLOCK, do the following:
2699 1. Propagate the NEW_SETS of the dominator into the current block.
2700 If the block has multiple predecessors,
2701 2a. Iterate over the ANTIC expressions for the block to see if
2702 any of them are partially redundant.
2703 2b. If so, insert them into the necessary predecessors to make
2704 the expression fully redundant.
2705 2c. Insert a new PHI merging the values of the predecessors.
2706 2d. Insert the new PHI, and the new expressions, into the
2708 3. Recursively call ourselves on the dominator children of BLOCK.
2710 Steps 1, 2a, and 3 are done by insert_aux. 2b, 2c and 2d are done by
2711 do_regular_insertion and do_partial_insertion.
2716 do_regular_insertion (basic_block block
, basic_block dom
)
2718 bool new_stuff
= false;
2719 VEC (tree
, heap
) *exprs
= sorted_array_from_bitmap_set (ANTIC_IN (block
));
2723 for (i
= 0; VEC_iterate (tree
, exprs
, i
, expr
); i
++)
2725 if (can_PRE_operation (expr
) && !AGGREGATE_TYPE_P (TREE_TYPE (expr
)))
2729 bool by_some
= false;
2730 bool cant_insert
= false;
2731 bool all_same
= true;
2732 tree first_s
= NULL
;
2735 tree eprime
= NULL_TREE
;
2738 val
= get_value_handle (expr
);
2739 if (bitmap_set_contains_value (PHI_GEN (block
), val
))
2741 if (bitmap_set_contains_value (AVAIL_OUT (dom
), val
))
2743 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2744 fprintf (dump_file
, "Found fully redundant value\n");
2748 avail
= XCNEWVEC (tree
, last_basic_block
);
2749 FOR_EACH_EDGE (pred
, ei
, block
->preds
)
2754 /* This can happen in the very weird case
2755 that our fake infinite loop edges have caused a
2756 critical edge to appear. */
2757 if (EDGE_CRITICAL_P (pred
))
2763 eprime
= phi_translate (expr
, ANTIC_IN (block
), NULL
,
2766 /* eprime will generally only be NULL if the
2767 value of the expression, translated
2768 through the PHI for this predecessor, is
2769 undefined. If that is the case, we can't
2770 make the expression fully redundant,
2771 because its value is undefined along a
2772 predecessor path. We can thus break out
2773 early because it doesn't matter what the
2774 rest of the results are. */
2781 eprime
= fully_constant_expression (eprime
);
2782 vprime
= get_value_handle (eprime
);
2783 gcc_assert (vprime
);
2784 edoubleprime
= bitmap_find_leader (AVAIL_OUT (bprime
),
2786 if (edoubleprime
== NULL
)
2788 avail
[bprime
->index
] = eprime
;
2793 avail
[bprime
->index
] = edoubleprime
;
2795 if (first_s
== NULL
)
2796 first_s
= edoubleprime
;
2797 else if (!operand_equal_p (first_s
, edoubleprime
,
2802 /* If we can insert it, it's not the same value
2803 already existing along every predecessor, and
2804 it's defined by some predecessor, it is
2805 partially redundant. */
2806 if (!cant_insert
&& !all_same
&& by_some
)
2808 if (insert_into_preds_of_block (block
, get_expression_id (expr
),
2812 /* If all edges produce the same value and that value is
2813 an invariant, then the PHI has the same value on all
2814 edges. Note this. */
2815 else if (!cant_insert
&& all_same
&& eprime
2816 && is_gimple_min_invariant (eprime
)
2817 && !is_gimple_min_invariant (val
))
2822 bitmap_set_t exprset
= VALUE_HANDLE_EXPR_SET (val
);
2823 FOR_EACH_EXPR_ID_IN_SET (exprset
, j
, bi
)
2825 tree expr
= expression_for_id (j
);
2826 if (TREE_CODE (expr
) == SSA_NAME
)
2828 vn_add (expr
, eprime
);
2829 pre_stats
.constified
++;
2837 VEC_free (tree
, heap
, exprs
);
2842 /* Perform insertion for partially anticipatable expressions. There
2843 is only one case we will perform insertion for these. This case is
2844 if the expression is partially anticipatable, and fully available.
2845 In this case, we know that putting it earlier will enable us to
2846 remove the later computation. */
2850 do_partial_partial_insertion (basic_block block
, basic_block dom
)
2852 bool new_stuff
= false;
2853 VEC (tree
, heap
) *exprs
= sorted_array_from_bitmap_set (PA_IN (block
));
2857 for (i
= 0; VEC_iterate (tree
, exprs
, i
, expr
); i
++)
2859 if (can_PRE_operation (expr
) && !AGGREGATE_TYPE_P (TREE_TYPE (expr
)))
2864 bool cant_insert
= false;
2867 tree eprime
= NULL_TREE
;
2870 val
= get_value_handle (expr
);
2871 if (bitmap_set_contains_value (PHI_GEN (block
), val
))
2873 if (bitmap_set_contains_value (AVAIL_OUT (dom
), val
))
2876 avail
= XCNEWVEC (tree
, last_basic_block
);
2877 FOR_EACH_EDGE (pred
, ei
, block
->preds
)
2882 /* This can happen in the very weird case
2883 that our fake infinite loop edges have caused a
2884 critical edge to appear. */
2885 if (EDGE_CRITICAL_P (pred
))
2891 eprime
= phi_translate (expr
, ANTIC_IN (block
),
2895 /* eprime will generally only be NULL if the
2896 value of the expression, translated
2897 through the PHI for this predecessor, is
2898 undefined. If that is the case, we can't
2899 make the expression fully redundant,
2900 because its value is undefined along a
2901 predecessor path. We can thus break out
2902 early because it doesn't matter what the
2903 rest of the results are. */
2910 eprime
= fully_constant_expression (eprime
);
2911 vprime
= get_value_handle (eprime
);
2912 gcc_assert (vprime
);
2913 edoubleprime
= bitmap_find_leader (AVAIL_OUT (bprime
),
2915 if (edoubleprime
== NULL
)
2921 avail
[bprime
->index
] = edoubleprime
;
2925 /* If we can insert it, it's not the same value
2926 already existing along every predecessor, and
2927 it's defined by some predecessor, it is
2928 partially redundant. */
2929 if (!cant_insert
&& by_all
)
2931 pre_stats
.pa_insert
++;
2932 if (insert_into_preds_of_block (block
, get_expression_id (expr
),
2940 VEC_free (tree
, heap
, exprs
);
2945 insert_aux (basic_block block
)
2948 bool new_stuff
= false;
2953 dom
= get_immediate_dominator (CDI_DOMINATORS
, block
);
2958 bitmap_set_t newset
= NEW_SETS (dom
);
2961 /* Note that we need to value_replace both NEW_SETS, and
2962 AVAIL_OUT. For both the case of NEW_SETS, the value may be
2963 represented by some non-simple expression here that we want
2964 to replace it with. */
2965 FOR_EACH_EXPR_ID_IN_SET (newset
, i
, bi
)
2967 tree expr
= expression_for_id (i
);
2968 bitmap_value_replace_in_set (NEW_SETS (block
), expr
);
2969 bitmap_value_replace_in_set (AVAIL_OUT (block
), expr
);
2972 if (!single_pred_p (block
))
2974 new_stuff
|= do_regular_insertion (block
, dom
);
2975 if (do_partial_partial
)
2976 new_stuff
|= do_partial_partial_insertion (block
, dom
);
2980 for (son
= first_dom_son (CDI_DOMINATORS
, block
);
2982 son
= next_dom_son (CDI_DOMINATORS
, son
))
2984 new_stuff
|= insert_aux (son
);
2990 /* Perform insertion of partially redundant values. */
2995 bool new_stuff
= true;
2997 int num_iterations
= 0;
3000 NEW_SETS (bb
) = bitmap_set_new ();
3005 new_stuff
= insert_aux (ENTRY_BLOCK_PTR
);
3007 statistics_histogram_event (cfun
, "insert iterations", num_iterations
);
3011 /* Add OP to EXP_GEN (block), and possibly to the maximal set if it is
3012 not defined by a phi node.
3013 PHI nodes can't go in the maximal sets because they are not in
3014 TMP_GEN, so it is possible to get into non-monotonic situations
3015 during ANTIC calculation, because it will *add* bits. */
3018 add_to_exp_gen (basic_block block
, tree op
)
3022 if (TREE_CODE (op
) == SSA_NAME
&& ssa_undefined_value_p (op
))
3024 bitmap_value_insert_into_set (EXP_GEN (block
), op
);
3025 if (TREE_CODE (op
) != SSA_NAME
3026 || TREE_CODE (SSA_NAME_DEF_STMT (op
)) != PHI_NODE
)
3027 bitmap_value_insert_into_set (maximal_set
, op
);
3032 /* Given an SSA variable VAR and an expression EXPR, compute the value
3033 number for EXPR and create a value handle (VAL) for it. If VAR and
3034 EXPR are not the same, associate VAL with VAR. Finally, add VAR to
3035 S1 and its value handle to S2, and to the maximal set if
3036 ADD_TO_MAXIMAL is true.
3038 VUSES represent the virtual use operands associated with EXPR (if
3042 add_to_sets (tree var
, tree expr
, VEC(tree
, gc
) *vuses
, bitmap_set_t s1
,
3046 val
= vn_lookup_or_add_with_vuses (expr
, vuses
);
3048 /* VAR and EXPR may be the same when processing statements for which
3049 we are not computing value numbers (e.g., non-assignments, or
3050 statements that make aliased stores). In those cases, we are
3051 only interested in making VAR available as its own value. */
3056 bitmap_insert_into_set (s1
, var
);
3058 bitmap_value_insert_into_set (s2
, var
);
3061 /* Find existing value expression that is the same as T,
3062 and return it if it exists. */
3065 find_existing_value_expr (tree t
, VEC (tree
, gc
) *vuses
)
3070 bitmap_set_t exprset
;
3072 if (REFERENCE_CLASS_P (t
) || TREE_CODE (t
) == CALL_EXPR
|| DECL_P (t
))
3073 vh
= vn_lookup_with_vuses (t
, vuses
);
3079 exprset
= VALUE_HANDLE_EXPR_SET (vh
);
3080 FOR_EACH_EXPR_ID_IN_SET (exprset
, bii
, bi
)
3082 tree efi
= expression_for_id (bii
);
3083 if (expressions_equal_p (t
, efi
))
3089 /* Given a unary or binary expression EXPR, create and return a new
3090 expression with the same structure as EXPR but with its operands
3091 replaced with the value handles of each of the operands of EXPR.
3093 VUSES represent the virtual use operands associated with EXPR (if
3094 any). Insert EXPR's operands into the EXP_GEN set for BLOCK.
3096 If CHECK_AVAIL is true, checks availability of each operand in
3097 BLOCKs AVAIL_OUT set. */
3100 create_value_expr_from (tree expr
, basic_block block
, VEC (tree
, gc
) *vuses
,
3104 enum tree_code code
= TREE_CODE (expr
);
3106 alloc_pool pool
= NULL
;
3109 gcc_assert (TREE_CODE_CLASS (code
) == tcc_unary
3110 || TREE_CODE_CLASS (code
) == tcc_binary
3111 || TREE_CODE_CLASS (code
) == tcc_comparison
3112 || TREE_CODE_CLASS (code
) == tcc_reference
3113 || TREE_CODE_CLASS (code
) == tcc_expression
3114 || TREE_CODE_CLASS (code
) == tcc_vl_exp
3115 || TREE_CODE_CLASS (code
) == tcc_exceptional
3116 || TREE_CODE_CLASS (code
) == tcc_declaration
);
3118 if (TREE_CODE_CLASS (code
) == tcc_unary
)
3119 pool
= unary_node_pool
;
3120 else if (TREE_CODE_CLASS (code
) == tcc_reference
)
3121 pool
= reference_node_pool
;
3122 else if (TREE_CODE_CLASS (code
) == tcc_binary
)
3123 pool
= binary_node_pool
;
3124 else if (TREE_CODE_CLASS (code
) == tcc_comparison
)
3125 pool
= comparison_node_pool
;
3127 gcc_assert (code
== CALL_EXPR
);
3129 if (code
== CALL_EXPR
)
3130 vexpr
= temp_copy_call_expr (expr
);
3133 vexpr
= (tree
) pool_alloc (pool
);
3134 memcpy (vexpr
, expr
, tree_size (expr
));
3137 for (i
= 0; i
< TREE_OPERAND_LENGTH (expr
); i
++)
3139 tree val
= NULL_TREE
;
3142 op
= TREE_OPERAND (expr
, i
);
3143 if (op
== NULL_TREE
)
3146 /* Recursively value-numberize reference ops and tree lists. */
3147 if (REFERENCE_CLASS_P (op
))
3149 tree tempop
= create_value_expr_from (op
, block
, vuses
, check_avail
);
3150 op
= tempop
? tempop
: op
;
3151 val
= vn_lookup_or_add_with_vuses (op
, vuses
);
3152 set_expression_vuses (op
, vuses
);
3156 val
= vn_lookup_or_add (op
);
3158 if (TREE_CODE (op
) != TREE_LIST
)
3159 add_to_exp_gen (block
, op
);
3161 if (TREE_CODE (val
) == VALUE_HANDLE
)
3162 TREE_TYPE (val
) = TREE_TYPE (TREE_OPERAND (vexpr
, i
));
3164 TREE_OPERAND (vexpr
, i
) = val
;
3167 && TREE_CODE (val
) == VALUE_HANDLE
3168 && !bitmap_set_contains_value (AVAIL_OUT (block
), val
))
3171 efi
= find_existing_value_expr (vexpr
, vuses
);
3174 get_or_alloc_expression_id (vexpr
);
3179 /* For each real store operation of the form
3180 *a = <value> that we see, create a corresponding fake store of the
3181 form storetmp_<version> = *a.
3183 This enables AVAIL computation to mark the results of stores as
3184 available. Without this, you'd need to do some computation to
3185 mark the result of stores as ANTIC and AVAIL at all the right
3187 To save memory, we keep the store
3188 statements pool allocated until we decide whether they are
3189 necessary or not. */
3192 insert_fake_stores (void)
3198 block_stmt_iterator bsi
;
3199 for (bsi
= bsi_start (block
); !bsi_end_p (bsi
); bsi_next (&bsi
))
3201 tree stmt
= bsi_stmt (bsi
);
3203 /* We can't generate SSA names for stores that are complex
3204 or aggregate. We also want to ignore things whose
3205 virtual uses occur in abnormal phis. */
3207 if (TREE_CODE (stmt
) == GIMPLE_MODIFY_STMT
3208 && (TREE_CODE (GIMPLE_STMT_OPERAND (stmt
, 0)) == INDIRECT_REF
3209 || handled_component_p (GIMPLE_STMT_OPERAND (stmt
, 0)))
3210 && !AGGREGATE_TYPE_P (TREE_TYPE (GIMPLE_STMT_OPERAND (stmt
, 0))))
3214 tree lhs
= GIMPLE_STMT_OPERAND (stmt
, 0);
3215 tree rhs
= GIMPLE_STMT_OPERAND (stmt
, 1);
3216 tree new_tree
, new_lhs
;
3217 bool notokay
= false;
3219 FOR_EACH_SSA_DEF_OPERAND (defp
, stmt
, iter
, SSA_OP_VIRTUAL_DEFS
)
3221 tree defvar
= DEF_FROM_PTR (defp
);
3222 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (defvar
))
3232 if (!storetemp
|| TREE_TYPE (rhs
) != TREE_TYPE (storetemp
))
3234 storetemp
= create_tmp_var (TREE_TYPE (rhs
), "storetmp");
3235 if (TREE_CODE (TREE_TYPE (storetemp
)) == VECTOR_TYPE
3236 || TREE_CODE (TREE_TYPE (storetemp
)) == COMPLEX_TYPE
)
3237 DECL_GIMPLE_REG_P (storetemp
) = 1;
3238 get_var_ann (storetemp
);
3241 new_tree
= build_gimple_modify_stmt (NULL_TREE
, lhs
);
3242 new_lhs
= make_ssa_name (storetemp
, new_tree
);
3243 GIMPLE_STMT_OPERAND (new_tree
, 0) = new_lhs
;
3244 create_ssa_artificial_load_stmt (new_tree
, stmt
, false);
3246 NECESSARY (new_tree
) = 0;
3247 VEC_safe_push (tree
, heap
, inserted_exprs
, new_tree
);
3248 VEC_safe_push (tree
, heap
, need_creation
, new_tree
);
3249 bsi_insert_after (&bsi
, new_tree
, BSI_NEW_STMT
);
3255 /* Turn the pool allocated fake stores that we created back into real
3256 GC allocated ones if they turned out to be necessary to PRE some
3260 realify_fake_stores (void)
3265 for (i
= 0; VEC_iterate (tree
, need_creation
, i
, stmt
); i
++)
3267 if (NECESSARY (stmt
))
3269 block_stmt_iterator bsi
, bsi2
;
3272 /* Mark the temp variable as referenced */
3273 add_referenced_var (SSA_NAME_VAR (GIMPLE_STMT_OPERAND (stmt
, 0)));
3275 /* Put the statement before the store in the IR stream
3276 as a plain ssa name copy. */
3277 bsi
= bsi_for_stmt (stmt
);
3279 rhs
= GIMPLE_STMT_OPERAND (bsi_stmt (bsi
), 1);
3280 GIMPLE_STMT_OPERAND (stmt
, 1) = rhs
;
3281 bsi2
= bsi_for_stmt (stmt
);
3282 bsi_remove (&bsi2
, true);
3283 bsi_insert_before (&bsi
, stmt
, BSI_SAME_STMT
);
3286 release_defs (stmt
);
3290 /* Given an SSA_NAME, see if SCCVN has a value number for it, and if
3291 so, return the value handle for this value number, creating it if
3293 Return NULL if SCCVN has no info for us. */
3296 get_sccvn_value (tree name
)
3298 if (TREE_CODE (name
) == SSA_NAME
3299 && VN_INFO (name
)->valnum
!= name
3300 && VN_INFO (name
)->valnum
!= VN_TOP
)
3302 tree val
= VN_INFO (name
)->valnum
;
3303 bool is_invariant
= is_gimple_min_invariant (val
);
3304 tree valvh
= !is_invariant
? get_value_handle (val
) : NULL_TREE
;
3306 /* We may end up with situations where SCCVN has chosen a
3307 representative for the equivalence set that we have not
3308 visited yet. In this case, just create the value handle for
3310 if (!valvh
&& !is_invariant
)
3312 /* We lookup with the LHS, so do not use vn_lookup_or_add_with_stmt
3313 here, as that will result in useless reference lookups. */
3314 valvh
= vn_lookup_or_add (val
);
3317 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3319 fprintf (dump_file
, "SCCVN says ");
3320 print_generic_expr (dump_file
, name
, 0);
3321 fprintf (dump_file
, " value numbers to ");
3322 if (valvh
&& !is_invariant
)
3324 print_generic_expr (dump_file
, val
, 0);
3325 fprintf (dump_file
, " (");
3326 print_generic_expr (dump_file
, valvh
, 0);
3327 fprintf (dump_file
, ")\n");
3330 print_generic_stmt (dump_file
, val
, 0);
3340 /* Create value handles for PHI in BLOCK. */
3343 make_values_for_phi (tree phi
, basic_block block
)
3345 tree result
= PHI_RESULT (phi
);
3346 /* We have no need for virtual phis, as they don't represent
3347 actual computations. */
3348 if (is_gimple_reg (result
))
3350 tree sccvnval
= get_sccvn_value (result
);
3353 vn_add (result
, sccvnval
);
3354 bitmap_insert_into_set (PHI_GEN (block
), result
);
3355 bitmap_value_insert_into_set (AVAIL_OUT (block
), result
);
3358 add_to_sets (result
, result
, NULL
,
3359 PHI_GEN (block
), AVAIL_OUT (block
));
3363 /* Create value handles for STMT in BLOCK. Return true if we handled
3367 make_values_for_stmt (tree stmt
, basic_block block
)
3370 tree lhs
= GIMPLE_STMT_OPERAND (stmt
, 0);
3371 tree rhs
= GIMPLE_STMT_OPERAND (stmt
, 1);
3372 tree valvh
= NULL_TREE
;
3374 VEC (tree
, gc
) *vuses
= NULL
;
3376 valvh
= get_sccvn_value (lhs
);
3380 vn_add (lhs
, valvh
);
3381 bitmap_value_insert_into_set (AVAIL_OUT (block
), lhs
);
3382 /* Shortcut for FRE. We have no need to create value expressions,
3383 just want to know what values are available where. */
3390 /* For FRE, if SCCVN didn't find anything, we aren't going to
3391 either, so just make up a new value number if necessary and
3393 if (get_value_handle (lhs
) == NULL
)
3394 vn_lookup_or_add (lhs
);
3395 bitmap_value_insert_into_set (AVAIL_OUT (block
), lhs
);
3399 lhsval
= valvh
? valvh
: get_value_handle (lhs
);
3400 vuses
= copy_vuses_from_stmt (stmt
);
3401 STRIP_USELESS_TYPE_CONVERSION (rhs
);
3402 if (can_value_number_operation (rhs
)
3403 && (!lhsval
|| !is_gimple_min_invariant (lhsval
))
3404 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
3406 /* For value numberable operation, create a
3407 duplicate expression with the operands replaced
3408 with the value handles of the original RHS. */
3409 tree newt
= create_value_expr_from (rhs
, block
, vuses
, false);
3412 set_expression_vuses (newt
, vuses
);
3413 /* If we already have a value number for the LHS, reuse
3414 it rather than creating a new one. */
3417 set_value_handle (newt
, lhsval
);
3418 if (!is_gimple_min_invariant (lhsval
))
3419 add_to_value (lhsval
, newt
);
3423 tree val
= vn_lookup_or_add_with_vuses (newt
, vuses
);
3427 add_to_exp_gen (block
, newt
);
3430 bitmap_insert_into_set (TMP_GEN (block
), lhs
);
3431 bitmap_value_insert_into_set (AVAIL_OUT (block
), lhs
);
3434 else if ((TREE_CODE (rhs
) == SSA_NAME
3435 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs
))
3436 || is_gimple_min_invariant (rhs
)
3437 || TREE_CODE (rhs
) == ADDR_EXPR
3443 set_expression_vuses (rhs
, vuses
);
3444 set_value_handle (rhs
, lhsval
);
3445 if (!is_gimple_min_invariant (lhsval
))
3446 add_to_value (lhsval
, rhs
);
3447 bitmap_insert_into_set (TMP_GEN (block
), lhs
);
3448 bitmap_value_insert_into_set (AVAIL_OUT (block
), lhs
);
3452 /* Compute a value number for the RHS of the statement
3453 and add its value to the AVAIL_OUT set for the block.
3454 Add the LHS to TMP_GEN. */
3455 set_expression_vuses (rhs
, vuses
);
3456 add_to_sets (lhs
, rhs
, vuses
, TMP_GEN (block
),
3459 /* None of the rest of these can be PRE'd. */
3460 if (TREE_CODE (rhs
) == SSA_NAME
&& !ssa_undefined_value_p (rhs
))
3461 add_to_exp_gen (block
, rhs
);
3468 /* Compute the AVAIL set for all basic blocks.
3470 This function performs value numbering of the statements in each basic
3471 block. The AVAIL sets are built from information we glean while doing
3472 this value numbering, since the AVAIL sets contain only one entry per
3475 AVAIL_IN[BLOCK] = AVAIL_OUT[dom(BLOCK)].
3476 AVAIL_OUT[BLOCK] = AVAIL_IN[BLOCK] U PHI_GEN[BLOCK] U TMP_GEN[BLOCK]. */
3479 compute_avail (void)
3481 basic_block block
, son
;
3482 basic_block
*worklist
;
3486 /* For arguments with default definitions, we pretend they are
3487 defined in the entry block. */
3488 for (param
= DECL_ARGUMENTS (current_function_decl
);
3490 param
= TREE_CHAIN (param
))
3492 if (gimple_default_def (cfun
, param
) != NULL
)
3494 tree def
= gimple_default_def (cfun
, param
);
3496 vn_lookup_or_add (def
);
3499 bitmap_insert_into_set (TMP_GEN (ENTRY_BLOCK_PTR
), def
);
3500 bitmap_value_insert_into_set (maximal_set
, def
);
3502 bitmap_value_insert_into_set (AVAIL_OUT (ENTRY_BLOCK_PTR
), def
);
3506 /* Likewise for the static chain decl. */
3507 if (cfun
->static_chain_decl
)
3509 param
= cfun
->static_chain_decl
;
3510 if (gimple_default_def (cfun
, param
) != NULL
)
3512 tree def
= gimple_default_def (cfun
, param
);
3514 vn_lookup_or_add (def
);
3517 bitmap_insert_into_set (TMP_GEN (ENTRY_BLOCK_PTR
), def
);
3518 bitmap_value_insert_into_set (maximal_set
, def
);
3520 bitmap_value_insert_into_set (AVAIL_OUT (ENTRY_BLOCK_PTR
), def
);
3524 /* Allocate the worklist. */
3525 worklist
= XNEWVEC (basic_block
, n_basic_blocks
);
3527 /* Seed the algorithm by putting the dominator children of the entry
3528 block on the worklist. */
3529 for (son
= first_dom_son (CDI_DOMINATORS
, ENTRY_BLOCK_PTR
);
3531 son
= next_dom_son (CDI_DOMINATORS
, son
))
3532 worklist
[sp
++] = son
;
3534 /* Loop until the worklist is empty. */
3537 block_stmt_iterator bsi
;
3540 unsigned int stmt_uid
= 1;
3542 /* Pick a block from the worklist. */
3543 block
= worklist
[--sp
];
3545 /* Initially, the set of available values in BLOCK is that of
3546 its immediate dominator. */
3547 dom
= get_immediate_dominator (CDI_DOMINATORS
, block
);
3549 bitmap_set_copy (AVAIL_OUT (block
), AVAIL_OUT (dom
));
3551 /* Generate values for PHI nodes. */
3552 for (phi
= phi_nodes (block
); phi
; phi
= PHI_CHAIN (phi
))
3553 make_values_for_phi (phi
, block
);
3555 /* Now compute value numbers and populate value sets with all
3556 the expressions computed in BLOCK. */
3557 for (bsi
= bsi_start (block
); !bsi_end_p (bsi
); bsi_next (&bsi
))
3563 stmt
= bsi_stmt (bsi
);
3564 ann
= stmt_ann (stmt
);
3566 set_gimple_stmt_uid (stmt
, stmt_uid
++);
3568 /* For regular value numbering, we are only interested in
3569 assignments of the form X_i = EXPR, where EXPR represents
3570 an "interesting" computation, it has no volatile operands
3571 and X_i doesn't flow through an abnormal edge. */
3572 if (TREE_CODE (stmt
) == RETURN_EXPR
3573 && !ann
->has_volatile_ops
)
3575 tree realstmt
= stmt
;
3579 stmt
= TREE_OPERAND (stmt
, 0);
3580 if (stmt
&& TREE_CODE (stmt
) == GIMPLE_MODIFY_STMT
)
3582 lhs
= GIMPLE_STMT_OPERAND (stmt
, 0);
3583 rhs
= GIMPLE_STMT_OPERAND (stmt
, 1);
3584 if (TREE_CODE (lhs
) == SSA_NAME
3585 && is_gimple_min_invariant (VN_INFO (lhs
)->valnum
))
3587 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3589 fprintf (dump_file
, "SCCVN says ");
3590 print_generic_expr (dump_file
, lhs
, 0);
3591 fprintf (dump_file
, " value numbers to ");
3592 print_generic_stmt (dump_file
, VN_INFO (lhs
)->valnum
,
3595 vn_add (lhs
, VN_INFO (lhs
)->valnum
);
3599 if (TREE_CODE (rhs
) == SSA_NAME
)
3600 add_to_exp_gen (block
, rhs
);
3602 FOR_EACH_SSA_TREE_OPERAND (op
, realstmt
, iter
, SSA_OP_DEF
)
3603 add_to_sets (op
, op
, NULL
, TMP_GEN (block
),
3609 else if (TREE_CODE (stmt
) == GIMPLE_MODIFY_STMT
3610 && !ann
->has_volatile_ops
3611 && TREE_CODE (GIMPLE_STMT_OPERAND (stmt
, 0)) == SSA_NAME
3612 && !tree_could_throw_p (stmt
))
3614 if (make_values_for_stmt (stmt
, block
))
3618 /* For any other statement that we don't recognize, simply
3619 make the names generated by the statement available in
3620 AVAIL_OUT and TMP_GEN. */
3621 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, iter
, SSA_OP_DEF
)
3622 add_to_sets (op
, op
, NULL
, TMP_GEN (block
), AVAIL_OUT (block
));
3624 /* Also add all referenced SSA_NAMEs to EXP_GEN. */
3625 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, iter
, SSA_OP_USE
)
3626 add_to_exp_gen (block
, op
);
3629 /* Put the dominator children of BLOCK on the worklist of blocks
3630 to compute available sets for. */
3631 for (son
= first_dom_son (CDI_DOMINATORS
, block
);
3633 son
= next_dom_son (CDI_DOMINATORS
, son
))
3634 worklist
[sp
++] = son
;
3640 /* Insert the expression for SSA_VN that SCCVN thought would be simpler
3641 than the available expressions for it. The insertion point is
3642 right before the first use in STMT. Returns the SSA_NAME that should
3643 be used for replacement. */
3646 do_SCCVN_insertion (tree stmt
, tree ssa_vn
)
3648 basic_block bb
= bb_for_stmt (stmt
);
3649 block_stmt_iterator bsi
;
3652 /* First create a value expression from the expression we want
3653 to insert and associate it with the value handle for SSA_VN. */
3654 expr
= create_value_expr_from (VN_INFO (ssa_vn
)->expr
, bb
, NULL
, true);
3655 if (expr
== NULL_TREE
)
3657 set_value_handle (expr
, get_value_handle (ssa_vn
));
3659 /* Then use create_expression_by_pieces to generate a valid
3660 expression to insert at this point of the IL stream. */
3661 stmts
= alloc_stmt_list ();
3662 expr
= create_expression_by_pieces (bb
, expr
, stmts
, stmt
);
3663 if (expr
== NULL_TREE
)
3665 bsi
= bsi_for_stmt (stmt
);
3666 bsi_insert_before (&bsi
, stmts
, BSI_SAME_STMT
);
3671 /* Eliminate fully redundant computations. */
3677 unsigned int todo
= 0;
3681 block_stmt_iterator i
;
3683 for (i
= bsi_start (b
); !bsi_end_p (i
); bsi_next (&i
))
3685 tree stmt
= bsi_stmt (i
);
3687 /* Lookup the RHS of the expression, see if we have an
3688 available computation for it. If so, replace the RHS with
3689 the available computation. */
3690 if (TREE_CODE (stmt
) == GIMPLE_MODIFY_STMT
3691 && TREE_CODE (GIMPLE_STMT_OPERAND (stmt
, 0)) == SSA_NAME
3692 && TREE_CODE (GIMPLE_STMT_OPERAND (stmt
, 1)) != SSA_NAME
3693 && !is_gimple_min_invariant (GIMPLE_STMT_OPERAND (stmt
, 1))
3694 && !stmt_ann (stmt
)->has_volatile_ops
)
3696 tree lhs
= GIMPLE_STMT_OPERAND (stmt
, 0);
3697 tree
*rhs_p
= &GIMPLE_STMT_OPERAND (stmt
, 1);
3700 sprime
= bitmap_find_leader (AVAIL_OUT (b
),
3701 get_value_handle (lhs
), NULL_TREE
);
3703 /* If there is no existing usable leader but SCCVN thinks
3704 it has an expression it wants to use as replacement,
3709 tree val
= VN_INFO (lhs
)->valnum
;
3711 && VN_INFO (val
)->needs_insertion
3712 && can_PRE_operation (VN_INFO (val
)->expr
))
3713 sprime
= do_SCCVN_insertion (stmt
, val
);
3718 && (TREE_CODE (*rhs_p
) != SSA_NAME
3719 || may_propagate_copy (*rhs_p
, sprime
)))
3721 gcc_assert (sprime
!= *rhs_p
);
3723 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3725 fprintf (dump_file
, "Replaced ");
3726 print_generic_expr (dump_file
, *rhs_p
, 0);
3727 fprintf (dump_file
, " with ");
3728 print_generic_expr (dump_file
, sprime
, 0);
3729 fprintf (dump_file
, " in ");
3730 print_generic_stmt (dump_file
, stmt
, 0);
3733 if (TREE_CODE (sprime
) == SSA_NAME
)
3734 NECESSARY (SSA_NAME_DEF_STMT (sprime
)) = 1;
3735 /* We need to make sure the new and old types actually match,
3736 which may require adding a simple cast, which fold_convert
3738 if (TREE_CODE (*rhs_p
) != SSA_NAME
3739 && !useless_type_conversion_p (TREE_TYPE (*rhs_p
),
3740 TREE_TYPE (sprime
)))
3741 sprime
= fold_convert (TREE_TYPE (*rhs_p
), sprime
);
3743 pre_stats
.eliminations
++;
3744 propagate_tree_value (rhs_p
, sprime
);
3747 /* If we removed EH side effects from the statement, clean
3748 its EH information. */
3749 if (maybe_clean_or_replace_eh_stmt (stmt
, stmt
))
3751 bitmap_set_bit (need_eh_cleanup
,
3752 bb_for_stmt (stmt
)->index
);
3753 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3754 fprintf (dump_file
, " Removed EH side effects.\n");
3758 /* Visit COND_EXPRs and fold the comparison with the
3759 available value-numbers. */
3760 else if (TREE_CODE (stmt
) == COND_EXPR
3761 && COMPARISON_CLASS_P (COND_EXPR_COND (stmt
)))
3763 tree cond
= COND_EXPR_COND (stmt
);
3764 tree op0
= TREE_OPERAND (cond
, 0);
3765 tree op1
= TREE_OPERAND (cond
, 1);
3768 if (TREE_CODE (op0
) == SSA_NAME
)
3769 op0
= VN_INFO (op0
)->valnum
;
3770 if (TREE_CODE (op1
) == SSA_NAME
)
3771 op1
= VN_INFO (op1
)->valnum
;
3772 result
= fold_binary (TREE_CODE (cond
), TREE_TYPE (cond
),
3774 if (result
&& TREE_CODE (result
) == INTEGER_CST
)
3776 COND_EXPR_COND (stmt
) = result
;
3778 todo
= TODO_cleanup_cfg
;
3781 else if (TREE_CODE (stmt
) == COND_EXPR
3782 && TREE_CODE (COND_EXPR_COND (stmt
)) == SSA_NAME
)
3784 tree op
= COND_EXPR_COND (stmt
);
3785 op
= VN_INFO (op
)->valnum
;
3786 if (TREE_CODE (op
) == INTEGER_CST
)
3788 COND_EXPR_COND (stmt
) = integer_zerop (op
)
3789 ? boolean_false_node
: boolean_true_node
;
3791 todo
= TODO_cleanup_cfg
;
3800 /* Borrow a bit of tree-ssa-dce.c for the moment.
3801 XXX: In 4.1, we should be able to just run a DCE pass after PRE, though
3802 this may be a bit faster, and we may want critical edges kept split. */
3804 /* If OP's defining statement has not already been determined to be necessary,
3805 mark that statement necessary. Return the stmt, if it is newly
3809 mark_operand_necessary (tree op
)
3815 if (TREE_CODE (op
) != SSA_NAME
)
3818 stmt
= SSA_NAME_DEF_STMT (op
);
3821 if (NECESSARY (stmt
)
3822 || IS_EMPTY_STMT (stmt
))
3825 NECESSARY (stmt
) = 1;
3829 /* Because we don't follow exactly the standard PRE algorithm, and decide not
3830 to insert PHI nodes sometimes, and because value numbering of casts isn't
3831 perfect, we sometimes end up inserting dead code. This simple DCE-like
3832 pass removes any insertions we made that weren't actually used. */
3835 remove_dead_inserted_code (void)
3837 VEC(tree
,heap
) *worklist
= NULL
;
3841 worklist
= VEC_alloc (tree
, heap
, VEC_length (tree
, inserted_exprs
));
3842 for (i
= 0; VEC_iterate (tree
, inserted_exprs
, i
, t
); i
++)
3845 VEC_quick_push (tree
, worklist
, t
);
3847 while (VEC_length (tree
, worklist
) > 0)
3849 t
= VEC_pop (tree
, worklist
);
3851 /* PHI nodes are somewhat special in that each PHI alternative has
3852 data and control dependencies. All the statements feeding the
3853 PHI node's arguments are always necessary. */
3854 if (TREE_CODE (t
) == PHI_NODE
)
3858 VEC_reserve (tree
, heap
, worklist
, PHI_NUM_ARGS (t
));
3859 for (k
= 0; k
< PHI_NUM_ARGS (t
); k
++)
3861 tree arg
= PHI_ARG_DEF (t
, k
);
3862 if (TREE_CODE (arg
) == SSA_NAME
)
3864 arg
= mark_operand_necessary (arg
);
3866 VEC_quick_push (tree
, worklist
, arg
);
3872 /* Propagate through the operands. Examine all the USE, VUSE and
3873 VDEF operands in this statement. Mark all the statements
3874 which feed this statement's uses as necessary. */
3878 /* The operands of VDEF expressions are also needed as they
3879 represent potential definitions that may reach this
3880 statement (VDEF operands allow us to follow def-def
3883 FOR_EACH_SSA_TREE_OPERAND (use
, t
, iter
, SSA_OP_ALL_USES
)
3885 tree n
= mark_operand_necessary (use
);
3887 VEC_safe_push (tree
, heap
, worklist
, n
);
3892 for (i
= 0; VEC_iterate (tree
, inserted_exprs
, i
, t
); i
++)
3896 block_stmt_iterator bsi
;
3898 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3900 fprintf (dump_file
, "Removing unnecessary insertion:");
3901 print_generic_stmt (dump_file
, t
, 0);
3904 if (TREE_CODE (t
) == PHI_NODE
)
3906 remove_phi_node (t
, NULL_TREE
, true);
3910 bsi
= bsi_for_stmt (t
);
3911 bsi_remove (&bsi
, true);
3916 VEC_free (tree
, heap
, worklist
);
3919 /* Initialize data structures used by PRE. */
3922 init_pre (bool do_fre
)
3926 inserted_exprs
= NULL
;
3927 need_creation
= NULL
;
3928 pretemp
= NULL_TREE
;
3929 storetemp
= NULL_TREE
;
3930 prephitemp
= NULL_TREE
;
3933 loop_optimizer_init (LOOPS_NORMAL
);
3935 connect_infinite_loops_to_exit ();
3936 memset (&pre_stats
, 0, sizeof (pre_stats
));
3938 calculate_dominance_info (CDI_POST_DOMINATORS
);
3939 calculate_dominance_info (CDI_DOMINATORS
);
3943 need_eh_cleanup
= BITMAP_ALLOC (NULL
);
3947 /* Deallocate data structures used by PRE. */
3954 VEC_free (tree
, heap
, inserted_exprs
);
3955 VEC_free (tree
, heap
, need_creation
);
3956 htab_delete (phi_translate_table
);
3957 remove_fake_exit_edges ();
3961 free_dominance_info (CDI_POST_DOMINATORS
);
3963 if (!bitmap_empty_p (need_eh_cleanup
))
3965 tree_purge_all_dead_eh_edges (need_eh_cleanup
);
3966 cleanup_tree_cfg ();
3969 BITMAP_FREE (need_eh_cleanup
);
3971 /* Wipe out pointers to VALUE_HANDLEs. In the not terribly distant
3972 future we will want them to be persistent though. */
3973 for (i
= 0; i
< num_ssa_names
; i
++)
3975 tree name
= ssa_name (i
);
3980 if (SSA_NAME_VALUE (name
)
3981 && TREE_CODE (SSA_NAME_VALUE (name
)) == VALUE_HANDLE
)
3982 SSA_NAME_VALUE (name
) = NULL
;
3984 if (current_loops
!= NULL
)
3985 loop_optimizer_finalize ();
3988 /* Main entry point to the SSA-PRE pass. DO_FRE is true if the caller
3989 only wants to do full redundancy elimination. */
3992 execute_pre (bool do_fre
)
3994 unsigned int todo
= 0;
3996 do_partial_partial
= optimize
> 2;
4000 insert_fake_stores ();
4002 /* Collect and value number expressions computed in each basic block. */
4003 if (!run_scc_vn (do_fre
))
4006 remove_dead_inserted_code ();
4010 switch_to_PRE_table ();
4013 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4019 print_bitmap_set (dump_file
, EXP_GEN (bb
), "exp_gen", bb
->index
);
4020 print_bitmap_set (dump_file
, TMP_GEN (bb
), "tmp_gen",
4022 print_bitmap_set (dump_file
, AVAIL_OUT (bb
), "avail_out",
4027 /* Insert can get quite slow on an incredibly large number of basic
4028 blocks due to some quadratic behavior. Until this behavior is
4029 fixed, don't run it when he have an incredibly large number of
4030 bb's. If we aren't going to run insert, there is no point in
4031 computing ANTIC, either, even though it's plenty fast. */
4032 if (!do_fre
&& n_basic_blocks
< 4000)
4035 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4041 print_bitmap_set (dump_file
, ANTIC_IN (bb
), "antic_in", bb
->index
);
4048 /* Remove all the redundant expressions. */
4049 todo
|= eliminate ();
4051 statistics_counter_event (cfun
, "Insertions", pre_stats
.insertions
);
4052 statistics_counter_event (cfun
, "PA inserted", pre_stats
.pa_insert
);
4053 statistics_counter_event (cfun
, "New PHIs", pre_stats
.phis
);
4054 statistics_counter_event (cfun
, "Eliminated", pre_stats
.eliminations
);
4055 statistics_counter_event (cfun
, "Constified", pre_stats
.constified
);
4056 bsi_commit_edge_inserts ();
4058 clear_expression_ids ();
4062 remove_dead_inserted_code ();
4063 realify_fake_stores ();
4071 /* Gate and execute functions for PRE. */
4076 return TODO_rebuild_alias
| execute_pre (false);
4082 return flag_tree_pre
!= 0;
4085 struct gimple_opt_pass pass_pre
=
4090 gate_pre
, /* gate */
4091 do_pre
, /* execute */
4094 0, /* static_pass_number */
4095 TV_TREE_PRE
, /* tv_id */
4096 PROP_no_crit_edges
| PROP_cfg
4097 | PROP_ssa
| PROP_alias
, /* properties_required */
4098 0, /* properties_provided */
4099 0, /* properties_destroyed */
4100 0, /* todo_flags_start */
4101 TODO_update_ssa_only_virtuals
| TODO_dump_func
| TODO_ggc_collect
4102 | TODO_verify_ssa
/* todo_flags_finish */
4107 /* Gate and execute functions for FRE. */
4112 return execute_pre (true);
4118 return flag_tree_fre
!= 0;
4121 struct gimple_opt_pass pass_fre
=
4126 gate_fre
, /* gate */
4127 execute_fre
, /* execute */
4130 0, /* static_pass_number */
4131 TV_TREE_FRE
, /* tv_id */
4132 PROP_cfg
| PROP_ssa
| PROP_alias
, /* properties_required */
4133 0, /* properties_provided */
4134 0, /* properties_destroyed */
4135 0, /* todo_flags_start */
4136 TODO_dump_func
| TODO_ggc_collect
| TODO_verify_ssa
/* todo_flags_finish */