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 2, 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 COPYING. If not, write to
21 the Free Software Foundation, 51 Franklin Street, Fifth Floor,
22 Boston, MA 02110-1301, USA. */
26 #include "coretypes.h"
30 #include "basic-block.h"
31 #include "diagnostic.h"
32 #include "tree-inline.h"
33 #include "tree-flow.h"
34 #include "tree-gimple.h"
35 #include "tree-dump.h"
39 #include "tree-iterator.h"
41 #include "alloc-pool.h"
43 #include "tree-pass.h"
46 #include "langhooks.h"
48 #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 /* Mapping from expression to id number we can use in bitmap sets. */
189 static VEC(tree
, heap
) *expressions
;
191 /* Allocate an expression id for EXPR. */
193 static inline unsigned int
194 alloc_expression_id (tree expr
)
196 tree_ann_common_t ann
;
198 ann
= get_tree_common_ann (expr
);
200 /* Make sure we won't overflow. */
201 gcc_assert (next_expression_id
+ 1 > next_expression_id
);
203 ann
->aux
= XNEW (unsigned int);
204 * ((unsigned int *)ann
->aux
) = next_expression_id
++;
205 VEC_safe_push (tree
, heap
, expressions
, expr
);
206 return next_expression_id
- 1;
209 /* Return the expression id for tree EXPR. */
211 static inline unsigned int
212 get_expression_id (tree expr
)
214 tree_ann_common_t ann
= tree_common_ann (expr
);
216 gcc_assert (ann
->aux
);
218 return *((unsigned int *)ann
->aux
);
221 /* Return the existing expression id for EXPR, or create one if one
222 does not exist yet. */
224 static inline unsigned int
225 get_or_alloc_expression_id (tree expr
)
227 tree_ann_common_t ann
= tree_common_ann (expr
);
229 if (ann
== NULL
|| !ann
->aux
)
230 return alloc_expression_id (expr
);
232 return get_expression_id (expr
);
235 /* Return the expression that has expression id ID */
238 expression_for_id (unsigned int id
)
240 return VEC_index (tree
, expressions
, id
);
243 /* Free the expression id field in all of our expressions,
244 and then destroy the expressions array. */
247 clear_expression_ids (void)
252 for (i
= 0; VEC_iterate (tree
, expressions
, i
, expr
); i
++)
254 free (tree_common_ann (expr
)->aux
);
255 tree_common_ann (expr
)->aux
= NULL
;
257 VEC_free (tree
, heap
, expressions
);
260 static bool in_fre
= false;
262 /* An unordered bitmap set. One bitmap tracks values, the other,
264 typedef struct bitmap_set
270 #define FOR_EACH_EXPR_ID_IN_SET(set, id, bi) \
271 EXECUTE_IF_SET_IN_BITMAP(set->expressions, 0, id, bi)
273 /* Sets that we need to keep track of. */
274 typedef struct bb_bitmap_sets
276 /* The EXP_GEN set, which represents expressions/values generated in
278 bitmap_set_t exp_gen
;
280 /* The PHI_GEN set, which represents PHI results generated in a
282 bitmap_set_t phi_gen
;
284 /* The TMP_GEN set, which represents results/temporaries generated
285 in a basic block. IE the LHS of an expression. */
286 bitmap_set_t tmp_gen
;
288 /* The AVAIL_OUT set, which represents which values are available in
289 a given basic block. */
290 bitmap_set_t avail_out
;
292 /* The ANTIC_IN set, which represents which values are anticipatable
293 in a given basic block. */
294 bitmap_set_t antic_in
;
296 /* The PA_IN set, which represents which values are
297 partially anticipatable in a given basic block. */
300 /* The NEW_SETS set, which is used during insertion to augment the
301 AVAIL_OUT set of blocks with the new insertions performed during
302 the current iteration. */
303 bitmap_set_t new_sets
;
305 /* These are the loads that will be ANTIC_IN at the top of the
306 block, and are actually generated in the block. */
307 bitmap_set_t antic_safe_loads
;
309 /* True if we have visited this block during ANTIC calculation. */
310 unsigned int visited
:1;
312 /* True we have deferred processing this block during ANTIC
313 calculation until its successor is processed. */
314 unsigned int deferred
: 1;
317 #define EXP_GEN(BB) ((bb_value_sets_t) ((BB)->aux))->exp_gen
318 #define PHI_GEN(BB) ((bb_value_sets_t) ((BB)->aux))->phi_gen
319 #define TMP_GEN(BB) ((bb_value_sets_t) ((BB)->aux))->tmp_gen
320 #define AVAIL_OUT(BB) ((bb_value_sets_t) ((BB)->aux))->avail_out
321 #define ANTIC_IN(BB) ((bb_value_sets_t) ((BB)->aux))->antic_in
322 #define PA_IN(BB) ((bb_value_sets_t) ((BB)->aux))->pa_in
323 #define NEW_SETS(BB) ((bb_value_sets_t) ((BB)->aux))->new_sets
324 #define ANTIC_SAFE_LOADS(BB) ((bb_value_sets_t) ((BB)->aux))->antic_safe_loads
325 #define BB_VISITED(BB) ((bb_value_sets_t) ((BB)->aux))->visited
326 #define BB_DEFERRED(BB) ((bb_value_sets_t) ((BB)->aux))->deferred
328 /* Maximal set of values, used to initialize the ANTIC problem, which
329 is an intersection problem. */
330 static bitmap_set_t maximal_set
;
332 /* Basic block list in postorder. */
333 static int *postorder
;
335 /* This structure is used to keep track of statistics on what
336 optimization PRE was able to perform. */
339 /* The number of RHS computations eliminated by PRE. */
342 /* The number of new expressions/temporaries generated by PRE. */
345 /* The number of inserts found due to partial anticipation */
348 /* The number of new PHI nodes added by PRE. */
351 /* The number of values found constant. */
356 static bool do_partial_partial
;
357 static tree
bitmap_find_leader (bitmap_set_t
, tree
);
358 static void bitmap_value_insert_into_set (bitmap_set_t
, tree
);
359 static void bitmap_value_replace_in_set (bitmap_set_t
, tree
);
360 static void bitmap_set_copy (bitmap_set_t
, bitmap_set_t
);
361 static bool bitmap_set_contains_value (bitmap_set_t
, tree
);
362 static void bitmap_insert_into_set (bitmap_set_t
, tree
);
363 static bitmap_set_t
bitmap_set_new (void);
364 static bool is_undefined_value (tree
);
365 static tree
create_expression_by_pieces (basic_block
, tree
, tree
);
366 static tree
find_or_generate_expression (basic_block
, tree
, tree
);
368 /* We can add and remove elements and entries to and from sets
369 and hash tables, so we use alloc pools for them. */
371 static alloc_pool bitmap_set_pool
;
372 static alloc_pool binary_node_pool
;
373 static alloc_pool unary_node_pool
;
374 static alloc_pool reference_node_pool
;
375 static alloc_pool comparison_node_pool
;
376 static alloc_pool modify_expr_node_pool
;
377 static bitmap_obstack grand_bitmap_obstack
;
379 /* We can't use allocation pools to hold temporary CALL_EXPR objects, since
380 they are not of fixed size. Instead, use an obstack. */
382 static struct obstack temp_call_expr_obstack
;
385 /* To avoid adding 300 temporary variables when we only need one, we
386 only create one temporary variable, on demand, and build ssa names
387 off that. We do have to change the variable if the types don't
388 match the current variable's type. */
390 static tree storetemp
;
391 static tree prephitemp
;
393 /* Set of blocks with statements that have had its EH information
395 static bitmap need_eh_cleanup
;
397 /* Which expressions have been seen during a given phi translation. */
398 static bitmap seen_during_translate
;
400 /* The phi_translate_table caches phi translations for a given
401 expression and predecessor. */
403 static htab_t phi_translate_table
;
405 /* A three tuple {e, pred, v} used to cache phi translations in the
406 phi_translate_table. */
408 typedef struct expr_pred_trans_d
410 /* The expression. */
413 /* The predecessor block along which we translated the expression. */
416 /* vuses associated with the expression. */
417 VEC (tree
, gc
) *vuses
;
419 /* The value that resulted from the translation. */
422 /* The hashcode for the expression, pred pair. This is cached for
425 } *expr_pred_trans_t
;
427 /* Return the hash value for a phi translation table entry. */
430 expr_pred_trans_hash (const void *p
)
432 const expr_pred_trans_t ve
= (expr_pred_trans_t
) p
;
436 /* Return true if two phi translation table entries are the same.
437 P1 and P2 should point to the expr_pred_trans_t's to be compared.*/
440 expr_pred_trans_eq (const void *p1
, const void *p2
)
442 const expr_pred_trans_t ve1
= (expr_pred_trans_t
) p1
;
443 const expr_pred_trans_t ve2
= (expr_pred_trans_t
) p2
;
444 basic_block b1
= ve1
->pred
;
445 basic_block b2
= ve2
->pred
;
449 /* If they are not translations for the same basic block, they can't
455 /* If they are for the same basic block, determine if the
456 expressions are equal. */
457 if (!expressions_equal_p (ve1
->e
, ve2
->e
))
460 /* Make sure the vuses are equivalent. */
461 if (ve1
->vuses
== ve2
->vuses
)
464 if (VEC_length (tree
, ve1
->vuses
) != VEC_length (tree
, ve2
->vuses
))
467 for (i
= 0; VEC_iterate (tree
, ve1
->vuses
, i
, vuse1
); i
++)
469 if (VEC_index (tree
, ve2
->vuses
, i
) != vuse1
)
476 /* Search in the phi translation table for the translation of
477 expression E in basic block PRED with vuses VUSES.
478 Return the translated value, if found, NULL otherwise. */
481 phi_trans_lookup (tree e
, basic_block pred
, VEC (tree
, gc
) *vuses
)
484 struct expr_pred_trans_d ept
;
489 ept
.hashcode
= iterative_hash_expr (e
, (unsigned long) pred
);
490 slot
= htab_find_slot_with_hash (phi_translate_table
, &ept
, ept
.hashcode
,
495 return ((expr_pred_trans_t
) *slot
)->v
;
499 /* Add the tuple mapping from {expression E, basic block PRED, vuses VUSES} to
500 value V, to the phi translation table. */
503 phi_trans_add (tree e
, tree v
, basic_block pred
, VEC (tree
, gc
) *vuses
)
506 expr_pred_trans_t new_pair
= XNEW (struct expr_pred_trans_d
);
508 new_pair
->pred
= pred
;
509 new_pair
->vuses
= vuses
;
511 new_pair
->hashcode
= iterative_hash_expr (e
, (unsigned long) pred
);
512 slot
= htab_find_slot_with_hash (phi_translate_table
, new_pair
,
513 new_pair
->hashcode
, INSERT
);
516 *slot
= (void *) new_pair
;
520 /* Return true if V is a value expression that represents itself.
521 In our world, this is *only* non-value handles. */
524 constant_expr_p (tree v
)
526 return TREE_CODE (v
) != VALUE_HANDLE
&&
527 (TREE_CODE (v
) == FIELD_DECL
|| is_gimple_min_invariant (v
));
530 /* Add expression E to the expression set of value V. */
533 add_to_value (tree v
, tree e
)
535 /* Constants have no expression sets. */
536 if (constant_expr_p (v
))
539 if (VALUE_HANDLE_EXPR_SET (v
) == NULL
)
540 VALUE_HANDLE_EXPR_SET (v
) = bitmap_set_new ();
542 bitmap_insert_into_set (VALUE_HANDLE_EXPR_SET (v
), e
);
545 /* Create a new bitmap set and return it. */
548 bitmap_set_new (void)
550 bitmap_set_t ret
= (bitmap_set_t
) pool_alloc (bitmap_set_pool
);
551 ret
->expressions
= BITMAP_ALLOC (&grand_bitmap_obstack
);
552 ret
->values
= BITMAP_ALLOC (&grand_bitmap_obstack
);
556 /* Remove an expression EXPR from a bitmapped set. */
559 bitmap_remove_from_set (bitmap_set_t set
, tree expr
)
561 tree val
= get_value_handle (expr
);
564 if (!constant_expr_p (val
))
566 bitmap_clear_bit (set
->values
, VALUE_HANDLE_ID (val
));
567 bitmap_clear_bit (set
->expressions
, get_expression_id (expr
));
571 /* Insert an expression EXPR into a bitmapped set. */
574 bitmap_insert_into_set (bitmap_set_t set
, tree expr
)
576 tree val
= get_value_handle (expr
);
579 if (!constant_expr_p (val
))
581 bitmap_set_bit (set
->values
, VALUE_HANDLE_ID (val
));
582 bitmap_set_bit (set
->expressions
, get_or_alloc_expression_id (expr
));
586 /* Copy a bitmapped set ORIG, into bitmapped set DEST. */
589 bitmap_set_copy (bitmap_set_t dest
, bitmap_set_t orig
)
591 bitmap_copy (dest
->expressions
, orig
->expressions
);
592 bitmap_copy (dest
->values
, orig
->values
);
596 /* Free memory used up by SET. */
598 bitmap_set_free (bitmap_set_t set
)
600 BITMAP_FREE (set
->expressions
);
601 BITMAP_FREE (set
->values
);
605 /* A comparison function for use in qsort to top sort a bitmap set. Simply
606 subtracts value handle ids, since they are created in topo-order. */
609 vh_compare (const void *pa
, const void *pb
)
611 const tree vha
= get_value_handle (*((const tree
*)pa
));
612 const tree vhb
= get_value_handle (*((const tree
*)pb
));
614 /* This can happen when we constify things. */
615 if (constant_expr_p (vha
))
617 if (constant_expr_p (vhb
))
621 else if (constant_expr_p (vhb
))
623 return VALUE_HANDLE_ID (vha
) - VALUE_HANDLE_ID (vhb
);
626 /* Generate an topological-ordered array of bitmap set SET. */
628 static VEC(tree
, heap
) *
629 sorted_array_from_bitmap_set (bitmap_set_t set
)
633 VEC(tree
, heap
) *result
= NULL
;
635 FOR_EACH_EXPR_ID_IN_SET (set
, i
, bi
)
636 VEC_safe_push (tree
, heap
, result
, expression_for_id (i
));
638 qsort (VEC_address (tree
, result
), VEC_length (tree
, result
),
639 sizeof (tree
), vh_compare
);
644 /* Perform bitmapped set operation DEST &= ORIG. */
647 bitmap_set_and (bitmap_set_t dest
, bitmap_set_t orig
)
654 bitmap temp
= BITMAP_ALLOC (&grand_bitmap_obstack
);
656 bitmap_and_into (dest
->values
, orig
->values
);
657 bitmap_copy (temp
, dest
->expressions
);
658 EXECUTE_IF_SET_IN_BITMAP (temp
, 0, i
, bi
)
660 tree expr
= expression_for_id (i
);
661 tree val
= get_value_handle (expr
);
662 if (!bitmap_bit_p (dest
->values
, VALUE_HANDLE_ID (val
)))
663 bitmap_clear_bit (dest
->expressions
, i
);
669 /* Subtract all values and expressions contained in ORIG from DEST. */
672 bitmap_set_subtract (bitmap_set_t dest
, bitmap_set_t orig
)
674 bitmap_set_t result
= bitmap_set_new ();
678 bitmap_and_compl (result
->expressions
, dest
->expressions
,
681 FOR_EACH_EXPR_ID_IN_SET (result
, i
, bi
)
683 tree expr
= expression_for_id (i
);
684 tree val
= get_value_handle (expr
);
685 bitmap_set_bit (result
->values
, VALUE_HANDLE_ID (val
));
691 /* Subtract all the values in bitmap set B from bitmap set A. */
694 bitmap_set_subtract_values (bitmap_set_t a
, bitmap_set_t b
)
698 bitmap temp
= BITMAP_ALLOC (&grand_bitmap_obstack
);
700 bitmap_copy (temp
, a
->expressions
);
701 EXECUTE_IF_SET_IN_BITMAP (temp
, 0, i
, bi
)
703 tree expr
= expression_for_id (i
);
704 if (bitmap_set_contains_value (b
, get_value_handle (expr
)))
705 bitmap_remove_from_set (a
, expr
);
711 /* Return true if bitmapped set SET contains the value VAL. */
714 bitmap_set_contains_value (bitmap_set_t set
, tree val
)
716 if (constant_expr_p (val
))
719 if (!set
|| bitmap_empty_p (set
->expressions
))
722 return bitmap_bit_p (set
->values
, VALUE_HANDLE_ID (val
));
726 bitmap_set_contains_expr (bitmap_set_t set
, tree expr
)
728 return bitmap_bit_p (set
->expressions
, get_expression_id (expr
));
731 /* Replace an instance of value LOOKFOR with expression EXPR in SET. */
734 bitmap_set_replace_value (bitmap_set_t set
, tree lookfor
, tree expr
)
736 bitmap_set_t exprset
;
740 if (constant_expr_p (lookfor
))
743 if (!bitmap_set_contains_value (set
, lookfor
))
746 /* The number of expressions having a given value is usually
747 significantly less than the total number of expressions in SET.
748 Thus, rather than check, for each expression in SET, whether it
749 has the value LOOKFOR, we walk the reverse mapping that tells us
750 what expressions have a given value, and see if any of those
751 expressions are in our set. For large testcases, this is about
752 5-10x faster than walking the bitmap. If this is somehow a
753 significant lose for some cases, we can choose which set to walk
754 based on the set size. */
755 exprset
= VALUE_HANDLE_EXPR_SET (lookfor
);
756 FOR_EACH_EXPR_ID_IN_SET (exprset
, i
, bi
)
758 if (bitmap_bit_p (set
->expressions
, i
))
760 bitmap_clear_bit (set
->expressions
, i
);
761 bitmap_set_bit (set
->expressions
, get_expression_id (expr
));
767 /* Return true if two bitmap sets are equal. */
770 bitmap_set_equal (bitmap_set_t a
, bitmap_set_t b
)
772 return bitmap_equal_p (a
->values
, b
->values
);
775 /* Replace an instance of EXPR's VALUE with EXPR in SET if it exists,
776 and add it otherwise. */
779 bitmap_value_replace_in_set (bitmap_set_t set
, tree expr
)
781 tree val
= get_value_handle (expr
);
783 if (bitmap_set_contains_value (set
, val
))
784 bitmap_set_replace_value (set
, val
, expr
);
786 bitmap_insert_into_set (set
, expr
);
789 /* Insert EXPR into SET if EXPR's value is not already present in
793 bitmap_value_insert_into_set (bitmap_set_t set
, tree expr
)
795 tree val
= get_value_handle (expr
);
797 if (constant_expr_p (val
))
800 if (!bitmap_set_contains_value (set
, val
))
801 bitmap_insert_into_set (set
, expr
);
804 /* Print out SET to OUTFILE. */
807 print_bitmap_set (FILE *outfile
, bitmap_set_t set
,
808 const char *setname
, int blockindex
)
810 fprintf (outfile
, "%s[%d] := { ", setname
, blockindex
);
817 FOR_EACH_EXPR_ID_IN_SET (set
, i
, bi
)
819 tree expr
= expression_for_id (i
);
822 fprintf (outfile
, ", ");
824 print_generic_expr (outfile
, expr
, 0);
826 fprintf (outfile
, " (");
827 print_generic_expr (outfile
, get_value_handle (expr
), 0);
828 fprintf (outfile
, ") ");
831 fprintf (outfile
, " }\n");
834 void debug_bitmap_set (bitmap_set_t
);
837 debug_bitmap_set (bitmap_set_t set
)
839 print_bitmap_set (stderr
, set
, "debug", 0);
842 /* Print out the expressions that have VAL to OUTFILE. */
845 print_value_expressions (FILE *outfile
, tree val
)
847 if (VALUE_HANDLE_EXPR_SET (val
))
850 sprintf (s
, "VH.%04d", VALUE_HANDLE_ID (val
));
851 print_bitmap_set (outfile
, VALUE_HANDLE_EXPR_SET (val
), s
, 0);
857 debug_value_expressions (tree val
)
859 print_value_expressions (stderr
, val
);
862 /* Return the folded version of T if T, when folded, is a gimple
863 min_invariant. Otherwise, return T. */
866 fully_constant_expression (tree t
)
870 if (folded
&& is_gimple_min_invariant (folded
))
875 /* Make a temporary copy of a CALL_EXPR object NODE. */
878 temp_copy_call_expr (tree node
)
880 return (tree
) obstack_copy (&temp_call_expr_obstack
, node
, tree_size (node
));
883 /* Translate the vuses in the VUSES vector backwards through phi nodes
884 in PHIBLOCK, so that they have the value they would have in
887 static VEC(tree
, gc
) *
888 translate_vuses_through_block (VEC (tree
, gc
) *vuses
,
889 basic_block phiblock
,
893 VEC(tree
, gc
) *result
= NULL
;
896 for (i
= 0; VEC_iterate (tree
, vuses
, i
, oldvuse
); i
++)
898 tree phi
= SSA_NAME_DEF_STMT (oldvuse
);
899 if (TREE_CODE (phi
) == PHI_NODE
900 && bb_for_stmt (phi
) == phiblock
)
902 edge e
= find_edge (block
, bb_for_stmt (phi
));
905 tree def
= PHI_ARG_DEF (phi
, e
->dest_idx
);
909 result
= VEC_copy (tree
, gc
, vuses
);
910 VEC_replace (tree
, result
, i
, def
);
916 /* We avoid creating a new copy of the vuses unless something
917 actually changed, so result can be NULL. */
927 /* Like find_leader, but checks for the value existing in SET1 *or*
928 SET2. This is used to avoid making a set consisting of the union
929 of PA_IN and ANTIC_IN during insert. */
932 find_leader_in_sets (tree expr
, bitmap_set_t set1
, bitmap_set_t set2
)
936 result
= bitmap_find_leader (set1
, expr
);
938 result
= bitmap_find_leader (set2
, expr
);
942 /* Translate EXPR using phis in PHIBLOCK, so that it has the values of
943 the phis in PRED. SEEN is a bitmap saying which expression we have
944 translated since we started translation of the toplevel expression.
945 Return NULL if we can't find a leader for each part of the
946 translated expression. */
949 phi_translate_1 (tree expr
, bitmap_set_t set1
, bitmap_set_t set2
,
950 basic_block pred
, basic_block phiblock
, bitmap seen
)
952 tree phitrans
= NULL
;
958 if (constant_expr_p (expr
))
961 /* Phi translations of a given expression don't change. */
962 if (EXPR_P (expr
) || GIMPLE_STMT_P (expr
))
966 vh
= get_value_handle (expr
);
967 if (vh
&& TREE_CODE (vh
) == VALUE_HANDLE
)
968 phitrans
= phi_trans_lookup (expr
, pred
, VALUE_HANDLE_VUSES (vh
));
970 phitrans
= phi_trans_lookup (expr
, pred
, NULL
);
973 phitrans
= phi_trans_lookup (expr
, pred
, NULL
);
978 /* Prevent cycles when we have recursively dependent leaders. This
979 can only happen when phi translating the maximal set. */
982 unsigned int expr_id
= get_expression_id (expr
);
983 if (bitmap_bit_p (seen
, expr_id
))
985 bitmap_set_bit (seen
, expr_id
);
988 switch (TREE_CODE_CLASS (TREE_CODE (expr
)))
995 if (TREE_CODE (expr
) != CALL_EXPR
)
999 tree oldfn
= CALL_EXPR_FN (expr
);
1000 tree oldsc
= CALL_EXPR_STATIC_CHAIN (expr
);
1001 tree newfn
, newsc
= NULL
;
1002 tree newexpr
= NULL_TREE
;
1003 tree vh
= get_value_handle (expr
);
1004 bool invariantarg
= false;
1006 VEC (tree
, gc
) *vuses
= VALUE_HANDLE_VUSES (vh
);
1007 VEC (tree
, gc
) *tvuses
;
1009 newfn
= phi_translate_1 (find_leader_in_sets (oldfn
, set1
, set2
),
1010 set1
, set2
, pred
, phiblock
, seen
);
1015 newexpr
= temp_copy_call_expr (expr
);
1016 CALL_EXPR_FN (newexpr
) = get_value_handle (newfn
);
1020 newsc
= phi_translate_1 (find_leader_in_sets (oldsc
, set1
, set2
),
1021 set1
, set2
, pred
, phiblock
, seen
);
1027 newexpr
= temp_copy_call_expr (expr
);
1028 CALL_EXPR_STATIC_CHAIN (newexpr
) = get_value_handle (newsc
);
1032 /* phi translate the argument list piece by piece. */
1033 nargs
= call_expr_nargs (expr
);
1034 for (i
= 0; i
< nargs
; i
++)
1036 tree oldval
= CALL_EXPR_ARG (expr
, i
);
1040 /* This may seem like a weird place for this
1041 check, but it's actually the easiest place to
1042 do it. We can't do it lower on in the
1043 recursion because it's valid for pieces of a
1044 component ref to be of AGGREGATE_TYPE, as long
1045 as the outermost one is not.
1046 To avoid *that* case, we have a check for
1047 AGGREGATE_TYPE_P in insert_aux. However, that
1048 check will *not* catch this case because here
1049 it occurs in the argument list. */
1050 if (AGGREGATE_TYPE_P (TREE_TYPE (oldval
)))
1052 oldval
= find_leader_in_sets (oldval
, set1
, set2
);
1053 newval
= phi_translate_1 (oldval
, set1
, set2
, pred
,
1057 if (newval
!= oldval
)
1059 invariantarg
|= is_gimple_min_invariant (newval
);
1061 newexpr
= temp_copy_call_expr (expr
);
1062 CALL_EXPR_ARG (newexpr
, i
) = get_value_handle (newval
);
1067 /* In case of new invariant args we might try to fold the call
1069 if (invariantarg
&& !newsc
)
1071 tree tmp1
= build_call_array (TREE_TYPE (expr
),
1072 newfn
, call_expr_nargs (newexpr
),
1073 CALL_EXPR_ARGP (newexpr
));
1074 tree tmp2
= fold (tmp1
);
1077 STRIP_TYPE_NOPS (tmp2
);
1078 if (is_gimple_min_invariant (tmp2
))
1083 tvuses
= translate_vuses_through_block (vuses
, phiblock
, pred
);
1084 if (vuses
!= tvuses
&& ! newexpr
)
1085 newexpr
= temp_copy_call_expr (expr
);
1089 newexpr
->base
.ann
= NULL
;
1090 vn_lookup_or_add_with_vuses (newexpr
, tvuses
);
1093 phi_trans_add (oldexpr
, expr
, pred
, tvuses
);
1098 case tcc_declaration
:
1100 VEC (tree
, gc
) * oldvuses
= NULL
;
1101 VEC (tree
, gc
) * newvuses
= NULL
;
1103 oldvuses
= VALUE_HANDLE_VUSES (get_value_handle (expr
));
1105 newvuses
= translate_vuses_through_block (oldvuses
, phiblock
,
1108 if (oldvuses
!= newvuses
)
1109 vn_lookup_or_add_with_vuses (expr
, newvuses
);
1111 phi_trans_add (oldexpr
, expr
, pred
, newvuses
);
1117 tree oldop0
= TREE_OPERAND (expr
, 0);
1126 VEC (tree
, gc
) * oldvuses
= NULL
;
1127 VEC (tree
, gc
) * newvuses
= NULL
;
1129 if (TREE_CODE (expr
) != INDIRECT_REF
1130 && TREE_CODE (expr
) != COMPONENT_REF
1131 && TREE_CODE (expr
) != ARRAY_REF
)
1134 oldop0
= find_leader_in_sets (oldop0
, set1
, set2
);
1135 newop0
= phi_translate_1 (oldop0
, set1
, set2
, pred
, phiblock
, seen
);
1139 if (TREE_CODE (expr
) == ARRAY_REF
)
1141 oldop1
= TREE_OPERAND (expr
, 1);
1142 oldop1
= find_leader_in_sets (oldop1
, set1
, set2
);
1143 newop1
= phi_translate_1 (oldop1
, set1
, set2
, pred
, phiblock
, seen
);
1148 oldop2
= TREE_OPERAND (expr
, 2);
1151 oldop2
= find_leader_in_sets (oldop2
, set1
, set2
);
1152 newop2
= phi_translate_1 (oldop2
, set1
, set2
, pred
, phiblock
, seen
);
1157 oldop3
= TREE_OPERAND (expr
, 3);
1160 oldop3
= find_leader_in_sets (oldop3
, set1
, set2
);
1161 newop3
= phi_translate_1 (oldop3
, set1
, set2
, pred
, phiblock
, seen
);
1168 oldvuses
= VALUE_HANDLE_VUSES (get_value_handle (expr
));
1170 newvuses
= translate_vuses_through_block (oldvuses
, phiblock
,
1173 if (newop0
!= oldop0
|| newvuses
!= oldvuses
1176 || newop3
!= oldop3
)
1180 newexpr
= (tree
) pool_alloc (reference_node_pool
);
1181 memcpy (newexpr
, expr
, tree_size (expr
));
1182 TREE_OPERAND (newexpr
, 0) = get_value_handle (newop0
);
1183 if (TREE_CODE (expr
) == ARRAY_REF
)
1185 TREE_OPERAND (newexpr
, 1) = get_value_handle (newop1
);
1187 TREE_OPERAND (newexpr
, 2) = get_value_handle (newop2
);
1189 TREE_OPERAND (newexpr
, 3) = get_value_handle (newop3
);
1192 t
= fully_constant_expression (newexpr
);
1196 pool_free (reference_node_pool
, newexpr
);
1201 newexpr
->base
.ann
= NULL
;
1202 vn_lookup_or_add_with_vuses (newexpr
, newvuses
);
1206 phi_trans_add (oldexpr
, expr
, pred
, newvuses
);
1212 case tcc_comparison
:
1214 tree oldop1
= TREE_OPERAND (expr
, 0);
1215 tree oldval1
= oldop1
;
1216 tree oldop2
= TREE_OPERAND (expr
, 1);
1217 tree oldval2
= oldop2
;
1222 oldop1
= find_leader_in_sets (oldop1
, set1
, set2
);
1223 newop1
= phi_translate_1 (oldop1
, set1
, set2
, pred
, phiblock
, seen
);
1227 oldop2
= find_leader_in_sets (oldop2
, set1
, set2
);
1228 newop2
= phi_translate_1 (oldop2
, set1
, set2
, pred
, phiblock
, seen
);
1231 if (newop1
!= oldop1
|| newop2
!= oldop2
)
1234 newexpr
= (tree
) pool_alloc (binary_node_pool
);
1235 memcpy (newexpr
, expr
, tree_size (expr
));
1236 TREE_OPERAND (newexpr
, 0) = newop1
== oldop1
? oldval1
: get_value_handle (newop1
);
1237 TREE_OPERAND (newexpr
, 1) = newop2
== oldop2
? oldval2
: get_value_handle (newop2
);
1238 t
= fully_constant_expression (newexpr
);
1241 pool_free (binary_node_pool
, newexpr
);
1246 newexpr
->base
.ann
= NULL
;
1247 vn_lookup_or_add (newexpr
);
1251 phi_trans_add (oldexpr
, expr
, pred
, NULL
);
1257 tree oldop1
= TREE_OPERAND (expr
, 0);
1261 oldop1
= find_leader_in_sets (oldop1
, set1
, set2
);
1262 newop1
= phi_translate_1 (oldop1
, set1
, set2
, pred
, phiblock
, seen
);
1265 if (newop1
!= oldop1
)
1268 newexpr
= (tree
) pool_alloc (unary_node_pool
);
1269 memcpy (newexpr
, expr
, tree_size (expr
));
1270 TREE_OPERAND (newexpr
, 0) = get_value_handle (newop1
);
1271 t
= fully_constant_expression (newexpr
);
1274 pool_free (unary_node_pool
, newexpr
);
1279 newexpr
->base
.ann
= NULL
;
1280 vn_lookup_or_add (newexpr
);
1284 phi_trans_add (oldexpr
, expr
, pred
, NULL
);
1288 case tcc_exceptional
:
1293 gcc_assert (TREE_CODE (expr
) == SSA_NAME
);
1295 def_stmt
= SSA_NAME_DEF_STMT (expr
);
1296 if (TREE_CODE (def_stmt
) == PHI_NODE
1297 && bb_for_stmt (def_stmt
) == phiblock
)
1302 e
= find_edge (pred
, bb_for_stmt (phi
));
1306 tree def
= PHI_ARG_DEF (phi
, e
->dest_idx
);
1308 if (is_gimple_min_invariant (def
))
1311 if (is_undefined_value (def
))
1314 val
= get_value_handle (def
);
1325 /* Translate EXPR using phis in PHIBLOCK, so that it has the values of
1327 Return NULL if we can't find a leader for each part of the
1328 translated expression. */
1331 phi_translate (tree expr
, bitmap_set_t set1
, bitmap_set_t set2
,
1332 basic_block pred
, basic_block phiblock
)
1334 return phi_translate_1 (expr
, set1
, set2
, pred
, phiblock
, NULL
);
1337 /* For each expression in SET, translate the value handles through phi nodes
1338 in PHIBLOCK using edge PHIBLOCK->PRED, and store the resulting
1339 expressions in DEST. */
1342 phi_translate_set (bitmap_set_t dest
, bitmap_set_t set
, basic_block pred
,
1343 basic_block phiblock
)
1345 VEC (tree
, heap
) *exprs
;
1349 if (!phi_nodes (phiblock
))
1351 bitmap_set_copy (dest
, set
);
1355 exprs
= sorted_array_from_bitmap_set (set
);
1356 for (i
= 0; VEC_iterate (tree
, exprs
, i
, expr
); i
++)
1359 bitmap_clear (seen_during_translate
);
1360 translated
= phi_translate_1 (expr
, set
, NULL
, pred
, phiblock
,
1361 seen_during_translate
);
1363 /* Don't add constants or empty translations to the cache, since
1364 we won't look them up that way, or use the result, anyway. */
1365 if (translated
&& !is_gimple_min_invariant (translated
))
1367 tree vh
= get_value_handle (translated
);
1368 VEC (tree
, gc
) *vuses
;
1370 /* The value handle itself may also be an invariant, in
1371 which case, it has no vuses. */
1372 vuses
= !is_gimple_min_invariant (vh
)
1373 ? VALUE_HANDLE_VUSES (vh
) : NULL
;
1374 phi_trans_add (expr
, translated
, pred
, vuses
);
1377 if (translated
!= NULL
)
1378 bitmap_value_insert_into_set (dest
, translated
);
1380 VEC_free (tree
, heap
, exprs
);
1383 /* Find the leader for a value (i.e., the name representing that
1384 value) in a given set, and return it. Return NULL if no leader is
1388 bitmap_find_leader (bitmap_set_t set
, tree val
)
1393 if (constant_expr_p (val
))
1396 if (bitmap_set_contains_value (set
, val
))
1398 /* Rather than walk the entire bitmap of expressions, and see
1399 whether any of them has the value we are looking for, we look
1400 at the reverse mapping, which tells us the set of expressions
1401 that have a given value (IE value->expressions with that
1402 value) and see if any of those expressions are in our set.
1403 The number of expressions per value is usually significantly
1404 less than the number of expressions in the set. In fact, for
1405 large testcases, doing it this way is roughly 5-10x faster
1406 than walking the bitmap.
1407 If this is somehow a significant lose for some cases, we can
1408 choose which set to walk based on which set is smaller. */
1411 bitmap_set_t exprset
= VALUE_HANDLE_EXPR_SET (val
);
1413 EXECUTE_IF_AND_IN_BITMAP (exprset
->expressions
,
1414 set
->expressions
, 0, i
, bi
)
1415 return expression_for_id (i
);
1420 /* Determine if VALUE, a memory operation, is ANTIC_IN at the top of
1421 BLOCK by seeing if it is not killed in the block. Note that we are
1422 only determining whether there is a store that kills it. Because
1423 of the order in which clean iterates over values, we are guaranteed
1424 that altered operands will have caused us to be eliminated from the
1425 ANTIC_IN set already. */
1428 value_dies_in_block_x (tree vh
, basic_block block
)
1432 VEC (tree
, gc
) *vuses
= VALUE_HANDLE_VUSES (vh
);
1434 /* Conservatively, a value dies if it's vuses are defined in this
1435 block, unless they come from phi nodes (which are merge operations,
1436 rather than stores. */
1437 for (i
= 0; VEC_iterate (tree
, vuses
, i
, vuse
); i
++)
1439 tree def
= SSA_NAME_DEF_STMT (vuse
);
1441 if (bb_for_stmt (def
) != block
)
1443 if (TREE_CODE (def
) == PHI_NODE
)
1450 /* Determine if the expression EXPR is valid in SET1 U SET2.
1451 ONLY SET2 CAN BE NULL.
1452 This means that we have a leader for each part of the expression
1453 (if it consists of values), or the expression is an SSA_NAME.
1454 For loads/calls, we also see if the vuses are killed in this block.
1456 NB: We never should run into a case where we have SSA_NAME +
1457 SSA_NAME or SSA_NAME + value. The sets valid_in_sets is called on,
1458 the ANTIC sets, will only ever have SSA_NAME's or value expressions
1459 (IE VALUE1 + VALUE2, *VALUE1, VALUE1 < VALUE2) */
1461 #define union_contains_value(SET1, SET2, VAL) \
1462 (bitmap_set_contains_value ((SET1), (VAL)) \
1463 || ((SET2) && bitmap_set_contains_value ((SET2), (VAL))))
1466 valid_in_sets (bitmap_set_t set1
, bitmap_set_t set2
, tree expr
,
1469 tree vh
= get_value_handle (expr
);
1470 switch (TREE_CODE_CLASS (TREE_CODE (expr
)))
1473 case tcc_comparison
:
1475 tree op1
= TREE_OPERAND (expr
, 0);
1476 tree op2
= TREE_OPERAND (expr
, 1);
1478 return union_contains_value (set1
, set2
, op1
)
1479 && union_contains_value (set1
, set2
, op2
);
1484 tree op1
= TREE_OPERAND (expr
, 0);
1485 return union_contains_value (set1
, set2
, op1
);
1488 case tcc_expression
:
1493 if (TREE_CODE (expr
) == CALL_EXPR
)
1495 tree fn
= CALL_EXPR_FN (expr
);
1496 tree sc
= CALL_EXPR_STATIC_CHAIN (expr
);
1498 call_expr_arg_iterator iter
;
1500 /* Check the non-argument operands first. */
1501 if (!union_contains_value (set1
, set2
, fn
)
1502 || (sc
&& !union_contains_value (set1
, set2
, sc
)))
1505 /* Now check the operands. */
1506 FOR_EACH_CALL_EXPR_ARG (arg
, iter
, expr
)
1508 if (!union_contains_value (set1
, set2
, arg
))
1511 return !value_dies_in_block_x (vh
, block
);
1518 if (TREE_CODE (expr
) == INDIRECT_REF
1519 || TREE_CODE (expr
) == COMPONENT_REF
1520 || TREE_CODE (expr
) == ARRAY_REF
)
1522 tree op0
= TREE_OPERAND (expr
, 0);
1523 gcc_assert (is_gimple_min_invariant (op0
)
1524 || TREE_CODE (op0
) == VALUE_HANDLE
);
1525 if (!union_contains_value (set1
, set2
, op0
))
1527 if (TREE_CODE (expr
) == ARRAY_REF
)
1529 tree op1
= TREE_OPERAND (expr
, 1);
1530 tree op2
= TREE_OPERAND (expr
, 2);
1531 tree op3
= TREE_OPERAND (expr
, 3);
1532 gcc_assert (is_gimple_min_invariant (op1
)
1533 || TREE_CODE (op1
) == VALUE_HANDLE
);
1534 if (!union_contains_value (set1
, set2
, op1
))
1536 gcc_assert (!op2
|| is_gimple_min_invariant (op2
)
1537 || TREE_CODE (op2
) == VALUE_HANDLE
);
1539 && !union_contains_value (set1
, set2
, op2
))
1541 gcc_assert (!op3
|| is_gimple_min_invariant (op3
)
1542 || TREE_CODE (op3
) == VALUE_HANDLE
);
1544 && !union_contains_value (set1
, set2
, op3
))
1547 return bitmap_set_contains_value (ANTIC_SAFE_LOADS (block
),
1549 || !value_dies_in_block_x (vh
, block
);
1554 case tcc_exceptional
:
1556 gcc_assert (TREE_CODE (expr
) == SSA_NAME
);
1557 return bitmap_set_contains_expr (AVAIL_OUT (block
), expr
);
1560 case tcc_declaration
:
1561 return !value_dies_in_block_x (vh
, block
);
1564 /* No other cases should be encountered. */
1569 /* Clean the set of expressions that are no longer valid in SET1 or
1570 SET2. This means expressions that are made up of values we have no
1571 leaders for in SET1 or SET2. This version is used for partial
1572 anticipation, which means it is not valid in either ANTIC_IN or
1576 dependent_clean (bitmap_set_t set1
, bitmap_set_t set2
, basic_block block
)
1578 VEC (tree
, heap
) *exprs
= sorted_array_from_bitmap_set (set1
);
1582 for (i
= 0; VEC_iterate (tree
, exprs
, i
, expr
); i
++)
1584 if (!valid_in_sets (set1
, set2
, expr
, block
))
1585 bitmap_remove_from_set (set1
, expr
);
1587 VEC_free (tree
, heap
, exprs
);
1590 /* Clean the set of expressions that are no longer valid in SET. This
1591 means expressions that are made up of values we have no leaders for
1595 clean (bitmap_set_t set
, basic_block block
)
1597 VEC (tree
, heap
) *exprs
= sorted_array_from_bitmap_set (set
);
1601 for (i
= 0; VEC_iterate (tree
, exprs
, i
, expr
); i
++)
1603 if (!valid_in_sets (set
, NULL
, expr
, block
))
1604 bitmap_remove_from_set (set
, expr
);
1606 VEC_free (tree
, heap
, exprs
);
1609 static sbitmap has_abnormal_preds
;
1611 /* List of blocks that may have changed during ANTIC computation and
1612 thus need to be iterated over. */
1614 static sbitmap changed_blocks
;
1616 /* Decide whether to defer a block for a later iteration, or PHI
1617 translate SOURCE to DEST using phis in PHIBLOCK. Return false if we
1618 should defer the block, and true if we processed it. */
1621 defer_or_phi_translate_block (bitmap_set_t dest
, bitmap_set_t source
,
1622 basic_block block
, basic_block phiblock
)
1624 if (!BB_VISITED (phiblock
))
1626 SET_BIT (changed_blocks
, block
->index
);
1627 BB_VISITED (block
) = 0;
1628 BB_DEFERRED (block
) = 1;
1632 phi_translate_set (dest
, source
, block
, phiblock
);
1636 /* Compute the ANTIC set for BLOCK.
1638 If succs(BLOCK) > 1 then
1639 ANTIC_OUT[BLOCK] = intersection of ANTIC_IN[b] for all succ(BLOCK)
1640 else if succs(BLOCK) == 1 then
1641 ANTIC_OUT[BLOCK] = phi_translate (ANTIC_IN[succ(BLOCK)])
1643 ANTIC_IN[BLOCK] = clean(ANTIC_OUT[BLOCK] U EXP_GEN[BLOCK] - TMP_GEN[BLOCK])
1647 compute_antic_aux (basic_block block
, bool block_has_abnormal_pred_edge
)
1649 bool changed
= false;
1650 bitmap_set_t S
, old
, ANTIC_OUT
;
1656 old
= ANTIC_OUT
= S
= NULL
;
1657 BB_VISITED (block
) = 1;
1659 /* If any edges from predecessors are abnormal, antic_in is empty,
1661 if (block_has_abnormal_pred_edge
)
1662 goto maybe_dump_sets
;
1664 old
= ANTIC_IN (block
);
1665 ANTIC_OUT
= bitmap_set_new ();
1667 /* If the block has no successors, ANTIC_OUT is empty. */
1668 if (EDGE_COUNT (block
->succs
) == 0)
1670 /* If we have one successor, we could have some phi nodes to
1671 translate through. */
1672 else if (single_succ_p (block
))
1674 basic_block succ_bb
= single_succ (block
);
1676 /* We trade iterations of the dataflow equations for having to
1677 phi translate the maximal set, which is incredibly slow
1678 (since the maximal set often has 300+ members, even when you
1679 have a small number of blocks).
1680 Basically, we defer the computation of ANTIC for this block
1681 until we have processed it's successor, which will inevitably
1682 have a *much* smaller set of values to phi translate once
1683 clean has been run on it.
1684 The cost of doing this is that we technically perform more
1685 iterations, however, they are lower cost iterations.
1687 Timings for PRE on tramp3d-v4:
1688 without maximal set fix: 11 seconds
1689 with maximal set fix/without deferring: 26 seconds
1690 with maximal set fix/with deferring: 11 seconds
1693 if (!defer_or_phi_translate_block (ANTIC_OUT
, ANTIC_IN (succ_bb
),
1697 goto maybe_dump_sets
;
1700 /* If we have multiple successors, we take the intersection of all of
1701 them. Note that in the case of loop exit phi nodes, we may have
1702 phis to translate through. */
1705 VEC(basic_block
, heap
) * worklist
;
1707 basic_block bprime
, first
;
1709 worklist
= VEC_alloc (basic_block
, heap
, EDGE_COUNT (block
->succs
));
1710 FOR_EACH_EDGE (e
, ei
, block
->succs
)
1711 VEC_quick_push (basic_block
, worklist
, e
->dest
);
1712 first
= VEC_index (basic_block
, worklist
, 0);
1714 if (phi_nodes (first
))
1716 bitmap_set_t from
= ANTIC_IN (first
);
1718 if (!BB_VISITED (first
))
1720 phi_translate_set (ANTIC_OUT
, from
, block
, first
);
1724 if (!BB_VISITED (first
))
1725 bitmap_set_copy (ANTIC_OUT
, maximal_set
);
1727 bitmap_set_copy (ANTIC_OUT
, ANTIC_IN (first
));
1730 for (i
= 1; VEC_iterate (basic_block
, worklist
, i
, bprime
); i
++)
1732 if (phi_nodes (bprime
))
1734 bitmap_set_t tmp
= bitmap_set_new ();
1735 bitmap_set_t from
= ANTIC_IN (bprime
);
1737 if (!BB_VISITED (bprime
))
1739 phi_translate_set (tmp
, from
, block
, bprime
);
1740 bitmap_set_and (ANTIC_OUT
, tmp
);
1741 bitmap_set_free (tmp
);
1745 if (!BB_VISITED (bprime
))
1746 bitmap_set_and (ANTIC_OUT
, maximal_set
);
1748 bitmap_set_and (ANTIC_OUT
, ANTIC_IN (bprime
));
1751 VEC_free (basic_block
, heap
, worklist
);
1754 /* Generate ANTIC_OUT - TMP_GEN. */
1755 S
= bitmap_set_subtract (ANTIC_OUT
, TMP_GEN (block
));
1757 /* Start ANTIC_IN with EXP_GEN - TMP_GEN. */
1758 ANTIC_IN (block
) = bitmap_set_subtract (EXP_GEN (block
),
1761 /* Then union in the ANTIC_OUT - TMP_GEN values,
1762 to get ANTIC_OUT U EXP_GEN - TMP_GEN */
1763 FOR_EACH_EXPR_ID_IN_SET (S
, bii
, bi
)
1764 bitmap_value_insert_into_set (ANTIC_IN (block
),
1765 expression_for_id (bii
));
1767 clean (ANTIC_IN (block
), block
);
1769 /* !old->expressions can happen when we deferred a block. */
1770 if (!old
->expressions
|| !bitmap_set_equal (old
, ANTIC_IN (block
)))
1773 SET_BIT (changed_blocks
, block
->index
);
1774 FOR_EACH_EDGE (e
, ei
, block
->preds
)
1775 SET_BIT (changed_blocks
, e
->src
->index
);
1778 RESET_BIT (changed_blocks
, block
->index
);
1781 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1783 if (!BB_DEFERRED (block
) || BB_VISITED (block
))
1786 print_bitmap_set (dump_file
, ANTIC_OUT
, "ANTIC_OUT", block
->index
);
1788 if (ANTIC_SAFE_LOADS (block
))
1789 print_bitmap_set (dump_file
, ANTIC_SAFE_LOADS (block
),
1790 "ANTIC_SAFE_LOADS", block
->index
);
1791 print_bitmap_set (dump_file
, ANTIC_IN (block
), "ANTIC_IN",
1795 print_bitmap_set (dump_file
, S
, "S", block
->index
);
1800 "Block %d was deferred for a future iteration.\n",
1805 bitmap_set_free (old
);
1807 bitmap_set_free (S
);
1809 bitmap_set_free (ANTIC_OUT
);
1813 /* Compute PARTIAL_ANTIC for BLOCK.
1815 If succs(BLOCK) > 1 then
1816 PA_OUT[BLOCK] = value wise union of PA_IN[b] + all ANTIC_IN not
1817 in ANTIC_OUT for all succ(BLOCK)
1818 else if succs(BLOCK) == 1 then
1819 PA_OUT[BLOCK] = phi_translate (PA_IN[succ(BLOCK)])
1821 PA_IN[BLOCK] = dependent_clean(PA_OUT[BLOCK] - TMP_GEN[BLOCK]
1826 compute_partial_antic_aux (basic_block block
,
1827 bool block_has_abnormal_pred_edge
)
1829 bool changed
= false;
1830 bitmap_set_t old_PA_IN
;
1831 bitmap_set_t PA_OUT
;
1835 old_PA_IN
= PA_OUT
= NULL
;
1837 /* If any edges from predecessors are abnormal, antic_in is empty,
1839 if (block_has_abnormal_pred_edge
)
1840 goto maybe_dump_sets
;
1842 old_PA_IN
= PA_IN (block
);
1843 PA_OUT
= bitmap_set_new ();
1845 /* If the block has no successors, ANTIC_OUT is empty. */
1846 if (EDGE_COUNT (block
->succs
) == 0)
1848 /* If we have one successor, we could have some phi nodes to
1849 translate through. Note that we can't phi translate across DFS
1850 back edges in partial antic, because it uses a union operation on
1851 the successors. For recurrences like IV's, we will end up
1852 generating a new value in the set on each go around (i + 3 (VH.1)
1853 VH.1 + 1 (VH.2), VH.2 + 1 (VH.3), etc), forever. */
1854 else if (single_succ_p (block
))
1856 basic_block succ
= single_succ (block
);
1857 if (!(single_succ_edge (block
)->flags
& EDGE_DFS_BACK
))
1858 phi_translate_set (PA_OUT
, PA_IN (succ
), block
, succ
);
1860 /* If we have multiple successors, we take the union of all of
1864 VEC(basic_block
, heap
) * worklist
;
1868 worklist
= VEC_alloc (basic_block
, heap
, EDGE_COUNT (block
->succs
));
1869 FOR_EACH_EDGE (e
, ei
, block
->succs
)
1871 if (e
->flags
& EDGE_DFS_BACK
)
1873 VEC_quick_push (basic_block
, worklist
, e
->dest
);
1875 if (VEC_length (basic_block
, worklist
) > 0)
1877 for (i
= 0; VEC_iterate (basic_block
, worklist
, i
, bprime
); i
++)
1882 FOR_EACH_EXPR_ID_IN_SET (ANTIC_IN (bprime
), i
, bi
)
1883 bitmap_value_insert_into_set (PA_OUT
,
1884 expression_for_id (i
));
1885 if (phi_nodes (bprime
))
1887 bitmap_set_t pa_in
= bitmap_set_new ();
1888 phi_translate_set (pa_in
, PA_IN (bprime
), block
, bprime
);
1889 FOR_EACH_EXPR_ID_IN_SET (pa_in
, i
, bi
)
1890 bitmap_value_insert_into_set (PA_OUT
,
1891 expression_for_id (i
));
1892 bitmap_set_free (pa_in
);
1895 FOR_EACH_EXPR_ID_IN_SET (PA_IN (bprime
), i
, bi
)
1896 bitmap_value_insert_into_set (PA_OUT
,
1897 expression_for_id (i
));
1900 VEC_free (basic_block
, heap
, worklist
);
1903 /* PA_IN starts with PA_OUT - TMP_GEN.
1904 Then we subtract things from ANTIC_IN. */
1905 PA_IN (block
) = bitmap_set_subtract (PA_OUT
, TMP_GEN (block
));
1907 /* For partial antic, we want to put back in the phi results, since
1908 we will properly avoid making them partially antic over backedges. */
1909 bitmap_ior_into (PA_IN (block
)->values
, PHI_GEN (block
)->values
);
1910 bitmap_ior_into (PA_IN (block
)->expressions
, PHI_GEN (block
)->expressions
);
1912 /* PA_IN[block] = PA_IN[block] - ANTIC_IN[block] */
1913 bitmap_set_subtract_values (PA_IN (block
), ANTIC_IN (block
));
1915 dependent_clean (PA_IN (block
), ANTIC_IN (block
), block
);
1917 if (!bitmap_set_equal (old_PA_IN
, PA_IN (block
)))
1920 SET_BIT (changed_blocks
, block
->index
);
1921 FOR_EACH_EDGE (e
, ei
, block
->preds
)
1922 SET_BIT (changed_blocks
, e
->src
->index
);
1925 RESET_BIT (changed_blocks
, block
->index
);
1928 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1931 print_bitmap_set (dump_file
, PA_OUT
, "PA_OUT", block
->index
);
1933 print_bitmap_set (dump_file
, PA_IN (block
), "PA_IN", block
->index
);
1936 bitmap_set_free (old_PA_IN
);
1938 bitmap_set_free (PA_OUT
);
1942 /* Compute ANTIC and partial ANTIC sets. */
1945 compute_antic (void)
1947 bool changed
= true;
1948 int num_iterations
= 0;
1952 /* If any predecessor edges are abnormal, we punt, so antic_in is empty.
1953 We pre-build the map of blocks with incoming abnormal edges here. */
1954 has_abnormal_preds
= sbitmap_alloc (last_basic_block
);
1955 sbitmap_zero (has_abnormal_preds
);
1962 FOR_EACH_EDGE (e
, ei
, block
->preds
)
1964 e
->flags
&= ~EDGE_DFS_BACK
;
1965 if (e
->flags
& EDGE_ABNORMAL
)
1967 SET_BIT (has_abnormal_preds
, block
->index
);
1972 BB_VISITED (block
) = 0;
1973 BB_DEFERRED (block
) = 0;
1974 /* While we are here, give empty ANTIC_IN sets to each block. */
1975 ANTIC_IN (block
) = bitmap_set_new ();
1976 PA_IN (block
) = bitmap_set_new ();
1979 /* At the exit block we anticipate nothing. */
1980 ANTIC_IN (EXIT_BLOCK_PTR
) = bitmap_set_new ();
1981 BB_VISITED (EXIT_BLOCK_PTR
) = 1;
1982 PA_IN (EXIT_BLOCK_PTR
) = bitmap_set_new ();
1984 changed_blocks
= sbitmap_alloc (last_basic_block
+ 1);
1985 sbitmap_ones (changed_blocks
);
1988 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1989 fprintf (dump_file
, "Starting iteration %d\n", num_iterations
);
1992 for (i
= 0; i
< last_basic_block
- NUM_FIXED_BLOCKS
; i
++)
1994 if (TEST_BIT (changed_blocks
, postorder
[i
]))
1996 basic_block block
= BASIC_BLOCK (postorder
[i
]);
1997 changed
|= compute_antic_aux (block
,
1998 TEST_BIT (has_abnormal_preds
,
2002 /* Theoretically possible, but *highly* unlikely. */
2003 gcc_assert (num_iterations
< 50);
2006 if (dump_file
&& (dump_flags
& TDF_STATS
))
2007 fprintf (dump_file
, "compute_antic required %d iterations\n",
2010 if (do_partial_partial
)
2012 sbitmap_ones (changed_blocks
);
2013 mark_dfs_back_edges ();
2018 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2019 fprintf (dump_file
, "Starting iteration %d\n", num_iterations
);
2022 for (i
= 0; i
< last_basic_block
- NUM_FIXED_BLOCKS
; i
++)
2024 if (TEST_BIT (changed_blocks
, postorder
[i
]))
2026 basic_block block
= BASIC_BLOCK (postorder
[i
]);
2028 |= compute_partial_antic_aux (block
,
2029 TEST_BIT (has_abnormal_preds
,
2033 /* Theoretically possible, but *highly* unlikely. */
2034 gcc_assert (num_iterations
< 50);
2036 if (dump_file
&& (dump_flags
& TDF_STATS
))
2037 fprintf (dump_file
, "compute_partial_antic required %d iterations\n",
2040 sbitmap_free (has_abnormal_preds
);
2041 sbitmap_free (changed_blocks
);
2045 ANTIC_SAFE_LOADS are those loads generated in a block that actually
2046 occur before any kill to their vuses in the block, and thus, are
2047 safe at the top of the block. This function computes the set by
2048 walking the EXP_GEN set for the block, and checking the VUSES.
2050 This set could be computed as ANTIC calculation is proceeding, but
2051 but because it does not actually change during that computation, it is
2052 quicker to pre-calculate the results and use them than to do it on
2053 the fly (particularly in the presence of multiple iteration). */
2056 compute_antic_safe (void)
2064 FOR_EACH_EXPR_ID_IN_SET (EXP_GEN (bb
), i
, bi
)
2066 tree expr
= expression_for_id (i
);
2067 if (REFERENCE_CLASS_P (expr
))
2069 tree vh
= get_value_handle (expr
);
2070 tree maybe
= bitmap_find_leader (AVAIL_OUT (bb
), vh
);
2078 stmt
= SSA_NAME_DEF_STMT (maybe
);
2079 if (TREE_CODE (stmt
) == PHI_NODE
)
2082 FOR_EACH_SSA_TREE_OPERAND (vuse
, stmt
, i
,
2083 SSA_OP_VIRTUAL_USES
)
2085 tree def
= SSA_NAME_DEF_STMT (vuse
);
2087 if (bb_for_stmt (def
) != bb
)
2090 /* See if the vuse is defined by a statement that
2091 comes before us in the block. Phi nodes are not
2092 stores, so they do not count. */
2093 if (TREE_CODE (def
) != PHI_NODE
2094 && stmt_ann (def
)->uid
< stmt_ann (stmt
)->uid
)
2102 if (ANTIC_SAFE_LOADS (bb
) == NULL
)
2103 ANTIC_SAFE_LOADS (bb
) = bitmap_set_new ();
2104 bitmap_value_insert_into_set (ANTIC_SAFE_LOADS (bb
),
2112 /* Return true if we can value number the call in STMT. This is true
2113 if we have a pure or constant call. */
2116 can_value_number_call (tree stmt
)
2118 tree call
= get_call_expr_in (stmt
);
2120 if (call_expr_flags (call
) & (ECF_PURE
| ECF_CONST
))
2125 /* Return true if OP is an exception handler related operation, such as
2126 FILTER_EXPRor EXC_PTR_EXPR. */
2129 is_exception_related (tree op
)
2131 return TREE_CODE (op
) == FILTER_EXPR
|| TREE_CODE (op
) == EXC_PTR_EXPR
;
2134 /* Return true if OP is a tree which we can perform value numbering
2138 can_value_number_operation (tree op
)
2140 return (UNARY_CLASS_P (op
)
2141 && !is_exception_related (TREE_OPERAND (op
, 0)))
2142 || BINARY_CLASS_P (op
)
2143 || COMPARISON_CLASS_P (op
)
2144 || REFERENCE_CLASS_P (op
)
2145 || (TREE_CODE (op
) == CALL_EXPR
2146 && can_value_number_call (op
));
2150 /* Return true if OP is a tree which we can perform PRE on
2151 on. This may not match the operations we can value number, but in
2152 a perfect world would. */
2155 can_PRE_operation (tree op
)
2157 return UNARY_CLASS_P (op
)
2158 || BINARY_CLASS_P (op
)
2159 || COMPARISON_CLASS_P (op
)
2160 || TREE_CODE (op
) == INDIRECT_REF
2161 || TREE_CODE (op
) == COMPONENT_REF
2162 || TREE_CODE (op
) == CALL_EXPR
2163 || TREE_CODE (op
) == ARRAY_REF
;
2167 /* Inserted expressions are placed onto this worklist, which is used
2168 for performing quick dead code elimination of insertions we made
2169 that didn't turn out to be necessary. */
2170 static VEC(tree
,heap
) *inserted_exprs
;
2172 /* Pool allocated fake store expressions are placed onto this
2173 worklist, which, after performing dead code elimination, is walked
2174 to see which expressions need to be put into GC'able memory */
2175 static VEC(tree
, heap
) *need_creation
;
2177 /* For COMPONENT_REF's and ARRAY_REF's, we can't have any intermediates for the
2178 COMPONENT_REF or INDIRECT_REF or ARRAY_REF portion, because we'd end up with
2179 trying to rename aggregates into ssa form directly, which is a no
2182 Thus, this routine doesn't create temporaries, it just builds a
2183 single access expression for the array, calling
2184 find_or_generate_expression to build the innermost pieces.
2186 This function is a subroutine of create_expression_by_pieces, and
2187 should not be called on it's own unless you really know what you
2191 create_component_ref_by_pieces (basic_block block
, tree expr
, tree stmts
)
2196 if (TREE_CODE (genop
) == VALUE_HANDLE
)
2198 tree found
= bitmap_find_leader (AVAIL_OUT (block
), expr
);
2203 if (TREE_CODE (genop
) == VALUE_HANDLE
)
2205 bitmap_set_t exprset
= VALUE_HANDLE_EXPR_SET (expr
);
2206 unsigned int firstbit
= bitmap_first_set_bit (exprset
->expressions
);
2207 genop
= expression_for_id (firstbit
);
2210 switch TREE_CODE (genop
)
2216 op0
= create_component_ref_by_pieces (block
,
2217 TREE_OPERAND (genop
, 0),
2219 op1
= TREE_OPERAND (genop
, 1);
2220 if (TREE_CODE (op1
) == VALUE_HANDLE
)
2221 op1
= find_or_generate_expression (block
, op1
, stmts
);
2222 op2
= TREE_OPERAND (genop
, 2);
2223 if (op2
&& TREE_CODE (op2
) == VALUE_HANDLE
)
2224 op2
= find_or_generate_expression (block
, op2
, stmts
);
2225 op3
= TREE_OPERAND (genop
, 3);
2226 if (op3
&& TREE_CODE (op3
) == VALUE_HANDLE
)
2227 op3
= find_or_generate_expression (block
, op3
, stmts
);
2228 folded
= build4 (ARRAY_REF
, TREE_TYPE (genop
), op0
, op1
,
2236 op0
= create_component_ref_by_pieces (block
,
2237 TREE_OPERAND (genop
, 0),
2239 /* op1 should be a FIELD_DECL, which are represented by
2241 op1
= TREE_OPERAND (genop
, 1);
2242 folded
= fold_build3 (COMPONENT_REF
, TREE_TYPE (genop
), op0
, op1
,
2249 tree op1
= TREE_OPERAND (genop
, 0);
2250 tree genop1
= find_or_generate_expression (block
, op1
, stmts
);
2252 folded
= fold_build1 (TREE_CODE (genop
), TREE_TYPE (genop
),
2270 /* Find a leader for an expression, or generate one using
2271 create_expression_by_pieces if it's ANTIC but
2273 BLOCK is the basic_block we are looking for leaders in.
2274 EXPR is the expression to find a leader or generate for.
2275 STMTS is the statement list to put the inserted expressions on.
2276 Returns the SSA_NAME of the LHS of the generated expression or the
2280 find_or_generate_expression (basic_block block
, tree expr
, tree stmts
)
2282 tree genop
= bitmap_find_leader (AVAIL_OUT (block
), expr
);
2284 /* If it's still NULL, it must be a complex expression, so generate
2288 bitmap_set_t exprset
= VALUE_HANDLE_EXPR_SET (expr
);
2289 bool handled
= false;
2293 /* We will hit cases where we have SSA_NAME's in exprset before
2294 other operations, because we may have come up with the SCCVN
2295 value before getting to the RHS of the expression. */
2296 FOR_EACH_EXPR_ID_IN_SET (exprset
, i
, bi
)
2298 genop
= expression_for_id (i
);
2299 if (can_PRE_operation (genop
))
2302 genop
= create_expression_by_pieces (block
, genop
, stmts
);
2306 gcc_assert (handled
);
2311 #define NECESSARY(stmt) stmt->base.asm_written_flag
2312 /* Create an expression in pieces, so that we can handle very complex
2313 expressions that may be ANTIC, but not necessary GIMPLE.
2314 BLOCK is the basic block the expression will be inserted into,
2315 EXPR is the expression to insert (in value form)
2316 STMTS is a statement list to append the necessary insertions into.
2318 This function will die if we hit some value that shouldn't be
2319 ANTIC but is (IE there is no leader for it, or its components).
2320 This function may also generate expressions that are themselves
2321 partially or fully redundant. Those that are will be either made
2322 fully redundant during the next iteration of insert (for partially
2323 redundant ones), or eliminated by eliminate (for fully redundant
2327 create_expression_by_pieces (basic_block block
, tree expr
, tree stmts
)
2330 tree folded
, forced_stmts
, newexpr
;
2332 tree_stmt_iterator tsi
;
2334 switch (TREE_CODE_CLASS (TREE_CODE (expr
)))
2343 gcc_assert (TREE_CODE (expr
) == CALL_EXPR
);
2345 fn
= CALL_EXPR_FN (expr
);
2346 sc
= CALL_EXPR_STATIC_CHAIN (expr
);
2348 genfn
= find_or_generate_expression (block
, fn
, stmts
);
2350 nargs
= call_expr_nargs (expr
);
2351 buffer
= (tree
*) alloca (nargs
* sizeof (tree
));
2353 for (i
= 0; i
< nargs
; i
++)
2355 tree arg
= CALL_EXPR_ARG (expr
, i
);
2356 buffer
[i
] = find_or_generate_expression (block
, arg
, stmts
);
2359 folded
= build_call_array (TREE_TYPE (expr
), genfn
, nargs
, buffer
);
2361 CALL_EXPR_STATIC_CHAIN (folded
) =
2362 find_or_generate_expression (block
, sc
, stmts
);
2363 folded
= fold (folded
);
2369 if (TREE_CODE (expr
) == COMPONENT_REF
2370 || TREE_CODE (expr
) == ARRAY_REF
)
2372 folded
= create_component_ref_by_pieces (block
, expr
, stmts
);
2376 tree op1
= TREE_OPERAND (expr
, 0);
2377 tree genop1
= find_or_generate_expression (block
, op1
, stmts
);
2379 folded
= fold_build1 (TREE_CODE (expr
), TREE_TYPE (expr
),
2386 case tcc_comparison
:
2388 tree op1
= TREE_OPERAND (expr
, 0);
2389 tree op2
= TREE_OPERAND (expr
, 1);
2390 tree genop1
= find_or_generate_expression (block
, op1
, stmts
);
2391 tree genop2
= find_or_generate_expression (block
, op2
, stmts
);
2392 folded
= fold_build2 (TREE_CODE (expr
), TREE_TYPE (expr
),
2399 tree op1
= TREE_OPERAND (expr
, 0);
2400 tree genop1
= find_or_generate_expression (block
, op1
, stmts
);
2401 folded
= fold_build1 (TREE_CODE (expr
), TREE_TYPE (expr
),
2410 /* Force the generated expression to be a sequence of GIMPLE
2412 We have to call unshare_expr because force_gimple_operand may
2413 modify the tree we pass to it. */
2414 newexpr
= force_gimple_operand (unshare_expr (folded
), &forced_stmts
,
2417 /* If we have any intermediate expressions to the value sets, add them
2418 to the value sets and chain them on in the instruction stream. */
2421 tsi
= tsi_start (forced_stmts
);
2422 for (; !tsi_end_p (tsi
); tsi_next (&tsi
))
2424 tree stmt
= tsi_stmt (tsi
);
2425 tree forcedname
= GIMPLE_STMT_OPERAND (stmt
, 0);
2426 tree forcedexpr
= GIMPLE_STMT_OPERAND (stmt
, 1);
2427 tree val
= vn_lookup_or_add (forcedexpr
);
2429 VEC_safe_push (tree
, heap
, inserted_exprs
, stmt
);
2430 VN_INFO_GET (forcedname
)->valnum
= forcedname
;
2431 vn_add (forcedname
, val
);
2432 bitmap_value_replace_in_set (NEW_SETS (block
), forcedname
);
2433 bitmap_value_replace_in_set (AVAIL_OUT (block
), forcedname
);
2434 mark_symbols_for_renaming (stmt
);
2436 tsi
= tsi_last (stmts
);
2437 tsi_link_after (&tsi
, forced_stmts
, TSI_CONTINUE_LINKING
);
2440 /* Build and insert the assignment of the end result to the temporary
2441 that we will return. */
2442 if (!pretemp
|| TREE_TYPE (expr
) != TREE_TYPE (pretemp
))
2444 pretemp
= create_tmp_var (TREE_TYPE (expr
), "pretmp");
2445 get_var_ann (pretemp
);
2449 add_referenced_var (temp
);
2451 if (TREE_CODE (TREE_TYPE (expr
)) == COMPLEX_TYPE
2452 || TREE_CODE (TREE_TYPE (expr
)) == VECTOR_TYPE
)
2453 DECL_GIMPLE_REG_P (temp
) = 1;
2455 newexpr
= build_gimple_modify_stmt (temp
, newexpr
);
2456 name
= make_ssa_name (temp
, newexpr
);
2457 GIMPLE_STMT_OPERAND (newexpr
, 0) = name
;
2458 NECESSARY (newexpr
) = 0;
2460 tsi
= tsi_last (stmts
);
2461 tsi_link_after (&tsi
, newexpr
, TSI_CONTINUE_LINKING
);
2462 VEC_safe_push (tree
, heap
, inserted_exprs
, newexpr
);
2464 /* All the symbols in NEWEXPR should be put into SSA form. */
2465 mark_symbols_for_renaming (newexpr
);
2467 /* Add a value handle to the temporary.
2468 The value may already exist in either NEW_SETS, or AVAIL_OUT, because
2469 we are creating the expression by pieces, and this particular piece of
2470 the expression may have been represented. There is no harm in replacing
2472 v
= get_value_handle (expr
);
2474 VN_INFO_GET (name
)->valnum
= name
;
2475 get_or_alloc_expression_id (name
);
2476 bitmap_value_replace_in_set (NEW_SETS (block
), name
);
2477 bitmap_value_replace_in_set (AVAIL_OUT (block
), name
);
2479 pre_stats
.insertions
++;
2480 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2482 fprintf (dump_file
, "Inserted ");
2483 print_generic_expr (dump_file
, newexpr
, 0);
2484 fprintf (dump_file
, " in predecessor %d\n", block
->index
);
2490 /* Insert the to-be-made-available values of expression EXPRNUM for each
2491 predecessor, stored in AVAIL, into the predecessors of BLOCK, and
2492 merge the result with a phi node, given the same value handle as
2493 NODE. Return true if we have inserted new stuff. */
2496 insert_into_preds_of_block (basic_block block
, unsigned int exprnum
,
2499 tree expr
= expression_for_id (exprnum
);
2500 tree val
= get_value_handle (expr
);
2502 bool insertions
= false;
2507 tree type
= TREE_TYPE (avail
[EDGE_PRED (block
, 0)->src
->index
]);
2510 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2512 fprintf (dump_file
, "Found partial redundancy for expression ");
2513 print_generic_expr (dump_file
, expr
, 0);
2514 fprintf (dump_file
, " (");
2515 print_generic_expr (dump_file
, val
, 0);
2516 fprintf (dump_file
, ")");
2517 fprintf (dump_file
, "\n");
2520 /* Make sure we aren't creating an induction variable. */
2521 if (block
->loop_depth
> 0 && EDGE_COUNT (block
->preds
) == 2
2522 && TREE_CODE_CLASS (TREE_CODE (expr
)) != tcc_reference
)
2524 bool firstinsideloop
= false;
2525 bool secondinsideloop
= false;
2526 firstinsideloop
= flow_bb_inside_loop_p (block
->loop_father
,
2527 EDGE_PRED (block
, 0)->src
);
2528 secondinsideloop
= flow_bb_inside_loop_p (block
->loop_father
,
2529 EDGE_PRED (block
, 1)->src
);
2530 /* Induction variables only have one edge inside the loop. */
2531 if (firstinsideloop
^ secondinsideloop
)
2533 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2534 fprintf (dump_file
, "Skipping insertion of phi for partial redundancy: Looks like an induction variable\n");
2540 /* Make the necessary insertions. */
2541 FOR_EACH_EDGE (pred
, ei
, block
->preds
)
2543 tree stmts
= alloc_stmt_list ();
2546 eprime
= avail
[bprime
->index
];
2548 if (can_PRE_operation (eprime
))
2550 builtexpr
= create_expression_by_pieces (bprime
,
2553 gcc_assert (!(pred
->flags
& EDGE_ABNORMAL
));
2554 bsi_insert_on_edge (pred
, stmts
);
2555 avail
[bprime
->index
] = builtexpr
;
2559 /* If we didn't want a phi node, and we made insertions, we still have
2560 inserted new stuff, and thus return true. If we didn't want a phi node,
2561 and didn't make insertions, we haven't added anything new, so return
2563 if (nophi
&& insertions
)
2565 else if (nophi
&& !insertions
)
2568 /* Now build a phi for the new variable. */
2569 if (!prephitemp
|| TREE_TYPE (prephitemp
) != type
)
2571 prephitemp
= create_tmp_var (type
, "prephitmp");
2572 get_var_ann (prephitemp
);
2576 add_referenced_var (temp
);
2579 if (TREE_CODE (type
) == COMPLEX_TYPE
2580 || TREE_CODE (type
) == VECTOR_TYPE
)
2581 DECL_GIMPLE_REG_P (temp
) = 1;
2582 temp
= create_phi_node (temp
, block
);
2584 NECESSARY (temp
) = 0;
2585 VN_INFO_GET (PHI_RESULT (temp
))->valnum
= PHI_RESULT (temp
);
2587 VEC_safe_push (tree
, heap
, inserted_exprs
, temp
);
2588 FOR_EACH_EDGE (pred
, ei
, block
->preds
)
2589 add_phi_arg (temp
, avail
[pred
->src
->index
], pred
);
2591 vn_add (PHI_RESULT (temp
), val
);
2593 /* The value should *not* exist in PHI_GEN, or else we wouldn't be doing
2594 this insertion, since we test for the existence of this value in PHI_GEN
2595 before proceeding with the partial redundancy checks in insert_aux.
2597 The value may exist in AVAIL_OUT, in particular, it could be represented
2598 by the expression we are trying to eliminate, in which case we want the
2599 replacement to occur. If it's not existing in AVAIL_OUT, we want it
2602 Similarly, to the PHI_GEN case, the value should not exist in NEW_SETS of
2603 this block, because if it did, it would have existed in our dominator's
2604 AVAIL_OUT, and would have been skipped due to the full redundancy check.
2607 bitmap_insert_into_set (PHI_GEN (block
),
2609 bitmap_value_replace_in_set (AVAIL_OUT (block
),
2611 bitmap_insert_into_set (NEW_SETS (block
),
2614 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2616 fprintf (dump_file
, "Created phi ");
2617 print_generic_expr (dump_file
, temp
, 0);
2618 fprintf (dump_file
, " in block %d\n", block
->index
);
2626 /* Perform insertion of partially redundant values.
2627 For BLOCK, do the following:
2628 1. Propagate the NEW_SETS of the dominator into the current block.
2629 If the block has multiple predecessors,
2630 2a. Iterate over the ANTIC expressions for the block to see if
2631 any of them are partially redundant.
2632 2b. If so, insert them into the necessary predecessors to make
2633 the expression fully redundant.
2634 2c. Insert a new PHI merging the values of the predecessors.
2635 2d. Insert the new PHI, and the new expressions, into the
2637 3. Recursively call ourselves on the dominator children of BLOCK.
2639 Steps 1, 2a, and 3 are done by insert_aux. 2b, 2c and 2d are done by
2640 do_regular_insertion and do_partial_insertion.
2645 do_regular_insertion (basic_block block
, basic_block dom
)
2647 bool new_stuff
= false;
2648 VEC (tree
, heap
) *exprs
= sorted_array_from_bitmap_set (ANTIC_IN (block
));
2652 for (i
= 0; VEC_iterate (tree
, exprs
, i
, expr
); i
++)
2654 if (can_PRE_operation (expr
) && !AGGREGATE_TYPE_P (TREE_TYPE (expr
)))
2658 bool by_some
= false;
2659 bool cant_insert
= false;
2660 bool all_same
= true;
2661 tree first_s
= NULL
;
2664 tree eprime
= NULL_TREE
;
2667 val
= get_value_handle (expr
);
2668 if (bitmap_set_contains_value (PHI_GEN (block
), val
))
2670 if (bitmap_set_contains_value (AVAIL_OUT (dom
), val
))
2672 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2673 fprintf (dump_file
, "Found fully redundant value\n");
2677 avail
= XCNEWVEC (tree
, last_basic_block
);
2678 FOR_EACH_EDGE (pred
, ei
, block
->preds
)
2683 /* This can happen in the very weird case
2684 that our fake infinite loop edges have caused a
2685 critical edge to appear. */
2686 if (EDGE_CRITICAL_P (pred
))
2692 eprime
= phi_translate (expr
, ANTIC_IN (block
), NULL
,
2695 /* eprime will generally only be NULL if the
2696 value of the expression, translated
2697 through the PHI for this predecessor, is
2698 undefined. If that is the case, we can't
2699 make the expression fully redundant,
2700 because its value is undefined along a
2701 predecessor path. We can thus break out
2702 early because it doesn't matter what the
2703 rest of the results are. */
2710 eprime
= fully_constant_expression (eprime
);
2711 vprime
= get_value_handle (eprime
);
2712 gcc_assert (vprime
);
2713 edoubleprime
= bitmap_find_leader (AVAIL_OUT (bprime
),
2715 if (edoubleprime
== NULL
)
2717 avail
[bprime
->index
] = eprime
;
2722 avail
[bprime
->index
] = edoubleprime
;
2724 if (first_s
== NULL
)
2725 first_s
= edoubleprime
;
2726 else if (!operand_equal_p (first_s
, edoubleprime
,
2731 /* If we can insert it, it's not the same value
2732 already existing along every predecessor, and
2733 it's defined by some predecessor, it is
2734 partially redundant. */
2735 if (!cant_insert
&& !all_same
&& by_some
)
2737 if (insert_into_preds_of_block (block
, get_expression_id (expr
),
2741 /* If all edges produce the same value and that value is
2742 an invariant, then the PHI has the same value on all
2743 edges. Note this. */
2744 else if (!cant_insert
&& all_same
&& eprime
2745 && is_gimple_min_invariant (eprime
)
2746 && !is_gimple_min_invariant (val
))
2751 bitmap_set_t exprset
= VALUE_HANDLE_EXPR_SET (val
);
2752 FOR_EACH_EXPR_ID_IN_SET (exprset
, j
, bi
)
2754 tree expr
= expression_for_id (j
);
2755 if (TREE_CODE (expr
) == SSA_NAME
)
2757 vn_add (expr
, eprime
);
2758 pre_stats
.constified
++;
2766 VEC_free (tree
, heap
, exprs
);
2771 /* Perform insertion for partially anticipatable expressions. There
2772 is only one case we will perform insertion for these. This case is
2773 if the expression is partially anticipatable, and fully available.
2774 In this case, we know that putting it earlier will enable us to
2775 remove the later computation. */
2779 do_partial_partial_insertion (basic_block block
, basic_block dom
)
2781 bool new_stuff
= false;
2782 VEC (tree
, heap
) *exprs
= sorted_array_from_bitmap_set (PA_IN (block
));
2786 for (i
= 0; VEC_iterate (tree
, exprs
, i
, expr
); i
++)
2788 if (can_PRE_operation (expr
) && !AGGREGATE_TYPE_P (TREE_TYPE (expr
)))
2793 bool cant_insert
= false;
2796 tree eprime
= NULL_TREE
;
2799 val
= get_value_handle (expr
);
2800 if (bitmap_set_contains_value (PHI_GEN (block
), val
))
2802 if (bitmap_set_contains_value (AVAIL_OUT (dom
), val
))
2805 avail
= XCNEWVEC (tree
, last_basic_block
);
2806 FOR_EACH_EDGE (pred
, ei
, block
->preds
)
2811 /* This can happen in the very weird case
2812 that our fake infinite loop edges have caused a
2813 critical edge to appear. */
2814 if (EDGE_CRITICAL_P (pred
))
2820 eprime
= phi_translate (expr
, ANTIC_IN (block
),
2824 /* eprime will generally only be NULL if the
2825 value of the expression, translated
2826 through the PHI for this predecessor, is
2827 undefined. If that is the case, we can't
2828 make the expression fully redundant,
2829 because its value is undefined along a
2830 predecessor path. We can thus break out
2831 early because it doesn't matter what the
2832 rest of the results are. */
2839 eprime
= fully_constant_expression (eprime
);
2840 vprime
= get_value_handle (eprime
);
2841 gcc_assert (vprime
);
2842 edoubleprime
= bitmap_find_leader (AVAIL_OUT (bprime
),
2844 if (edoubleprime
== NULL
)
2850 avail
[bprime
->index
] = edoubleprime
;
2854 /* If we can insert it, it's not the same value
2855 already existing along every predecessor, and
2856 it's defined by some predecessor, it is
2857 partially redundant. */
2858 if (!cant_insert
&& by_all
)
2860 pre_stats
.pa_insert
++;
2861 if (insert_into_preds_of_block (block
, get_expression_id (expr
),
2869 VEC_free (tree
, heap
, exprs
);
2874 insert_aux (basic_block block
)
2877 bool new_stuff
= false;
2882 dom
= get_immediate_dominator (CDI_DOMINATORS
, block
);
2887 bitmap_set_t newset
= NEW_SETS (dom
);
2890 /* Note that we need to value_replace both NEW_SETS, and
2891 AVAIL_OUT. For both the case of NEW_SETS, the value may be
2892 represented by some non-simple expression here that we want
2893 to replace it with. */
2894 FOR_EACH_EXPR_ID_IN_SET (newset
, i
, bi
)
2896 tree expr
= expression_for_id (i
);
2897 bitmap_value_replace_in_set (NEW_SETS (block
), expr
);
2898 bitmap_value_replace_in_set (AVAIL_OUT (block
), expr
);
2901 if (!single_pred_p (block
))
2903 new_stuff
|= do_regular_insertion (block
, dom
);
2904 if (do_partial_partial
)
2905 new_stuff
|= do_partial_partial_insertion (block
, dom
);
2909 for (son
= first_dom_son (CDI_DOMINATORS
, block
);
2911 son
= next_dom_son (CDI_DOMINATORS
, son
))
2913 new_stuff
|= insert_aux (son
);
2919 /* Perform insertion of partially redundant values. */
2924 bool new_stuff
= true;
2926 int num_iterations
= 0;
2929 NEW_SETS (bb
) = bitmap_set_new ();
2935 new_stuff
= insert_aux (ENTRY_BLOCK_PTR
);
2937 if (num_iterations
> 2 && dump_file
&& (dump_flags
& TDF_STATS
))
2938 fprintf (dump_file
, "insert required %d iterations\n", num_iterations
);
2942 /* Return true if VAR is an SSA variable with no defining statement in
2943 this procedure, *AND* isn't a live-on-entry parameter. */
2946 is_undefined_value (tree expr
)
2948 return (TREE_CODE (expr
) == SSA_NAME
2949 && IS_EMPTY_STMT (SSA_NAME_DEF_STMT (expr
))
2950 /* PARM_DECLs and hard registers are always defined. */
2951 && TREE_CODE (SSA_NAME_VAR (expr
)) != PARM_DECL
);
2954 /* Add OP to EXP_GEN (block), and possibly to the maximal set if it is
2955 not defined by a phi node.
2956 PHI nodes can't go in the maximal sets because they are not in
2957 TMP_GEN, so it is possible to get into non-monotonic situations
2958 during ANTIC calculation, because it will *add* bits. */
2961 add_to_exp_gen (basic_block block
, tree op
)
2965 if (TREE_CODE (op
) == SSA_NAME
&& is_undefined_value (op
))
2967 bitmap_value_insert_into_set (EXP_GEN (block
), op
);
2968 if (TREE_CODE (op
) != SSA_NAME
2969 || TREE_CODE (SSA_NAME_DEF_STMT (op
)) != PHI_NODE
)
2970 bitmap_value_insert_into_set (maximal_set
, op
);
2975 /* Given an SSA variable VAR and an expression EXPR, compute the value
2976 number for EXPR and create a value handle (VAL) for it. If VAR and
2977 EXPR are not the same, associate VAL with VAR. Finally, add VAR to
2978 S1 and its value handle to S2, and to the maximal set if
2979 ADD_TO_MAXIMAL is true.
2981 VUSES represent the virtual use operands associated with EXPR (if
2985 add_to_sets (tree var
, tree expr
, tree stmt
, bitmap_set_t s1
,
2989 val
= vn_lookup_or_add_with_stmt (expr
, stmt
);
2991 /* VAR and EXPR may be the same when processing statements for which
2992 we are not computing value numbers (e.g., non-assignments, or
2993 statements that make aliased stores). In those cases, we are
2994 only interested in making VAR available as its own value. */
2999 bitmap_insert_into_set (s1
, var
);
3001 bitmap_value_insert_into_set (s2
, var
);
3004 /* Find existing value expression that is the same as T,
3005 and return it if it exists. */
3008 find_existing_value_expr (tree t
, tree stmt
)
3013 bitmap_set_t exprset
;
3015 if (REFERENCE_CLASS_P (t
) || TREE_CODE (t
) == CALL_EXPR
|| DECL_P (t
))
3016 vh
= vn_lookup_with_stmt (t
, stmt
);
3022 exprset
= VALUE_HANDLE_EXPR_SET (vh
);
3023 FOR_EACH_EXPR_ID_IN_SET (exprset
, bii
, bi
)
3025 tree efi
= expression_for_id (bii
);
3026 if (expressions_equal_p (t
, efi
))
3032 /* Given a unary or binary expression EXPR, create and return a new
3033 expression with the same structure as EXPR but with its operands
3034 replaced with the value handles of each of the operands of EXPR.
3036 VUSES represent the virtual use operands associated with EXPR (if
3037 any). Insert EXPR's operands into the EXP_GEN set for BLOCK. */
3040 create_value_expr_from (tree expr
, basic_block block
, tree stmt
)
3043 enum tree_code code
= TREE_CODE (expr
);
3045 alloc_pool pool
= NULL
;
3048 gcc_assert (TREE_CODE_CLASS (code
) == tcc_unary
3049 || TREE_CODE_CLASS (code
) == tcc_binary
3050 || TREE_CODE_CLASS (code
) == tcc_comparison
3051 || TREE_CODE_CLASS (code
) == tcc_reference
3052 || TREE_CODE_CLASS (code
) == tcc_expression
3053 || TREE_CODE_CLASS (code
) == tcc_vl_exp
3054 || TREE_CODE_CLASS (code
) == tcc_exceptional
3055 || TREE_CODE_CLASS (code
) == tcc_declaration
);
3057 if (TREE_CODE_CLASS (code
) == tcc_unary
)
3058 pool
= unary_node_pool
;
3059 else if (TREE_CODE_CLASS (code
) == tcc_reference
)
3060 pool
= reference_node_pool
;
3061 else if (TREE_CODE_CLASS (code
) == tcc_binary
)
3062 pool
= binary_node_pool
;
3063 else if (TREE_CODE_CLASS (code
) == tcc_comparison
)
3064 pool
= comparison_node_pool
;
3066 gcc_assert (code
== CALL_EXPR
);
3068 if (code
== CALL_EXPR
)
3069 vexpr
= temp_copy_call_expr (expr
);
3072 vexpr
= (tree
) pool_alloc (pool
);
3073 memcpy (vexpr
, expr
, tree_size (expr
));
3076 for (i
= 0; i
< TREE_OPERAND_LENGTH (expr
); i
++)
3078 tree val
= NULL_TREE
;
3081 op
= TREE_OPERAND (expr
, i
);
3082 if (op
== NULL_TREE
)
3085 /* Recursively value-numberize reference ops and tree lists. */
3086 if (REFERENCE_CLASS_P (op
))
3088 tree tempop
= create_value_expr_from (op
, block
, stmt
);
3089 op
= tempop
? tempop
: op
;
3090 val
= vn_lookup_or_add_with_stmt (op
, stmt
);
3094 val
= vn_lookup_or_add (op
);
3096 if (TREE_CODE (op
) != TREE_LIST
)
3097 add_to_exp_gen (block
, op
);
3099 if (TREE_CODE (val
) == VALUE_HANDLE
)
3100 TREE_TYPE (val
) = TREE_TYPE (TREE_OPERAND (vexpr
, i
));
3102 TREE_OPERAND (vexpr
, i
) = val
;
3104 efi
= find_existing_value_expr (vexpr
, stmt
);
3107 get_or_alloc_expression_id (vexpr
);
3111 /* Return a copy of NODE that is stored in the temporary alloc_pool's.
3112 This is made recursively true, so that the operands are stored in
3113 the pool as well. */
3116 poolify_tree (tree node
)
3118 switch (TREE_CODE (node
))
3122 tree temp
= (tree
) pool_alloc (reference_node_pool
);
3123 memcpy (temp
, node
, tree_size (node
));
3124 TREE_OPERAND (temp
, 0) = poolify_tree (TREE_OPERAND (temp
, 0));
3128 case GIMPLE_MODIFY_STMT
:
3130 tree temp
= (tree
) pool_alloc (modify_expr_node_pool
);
3131 memcpy (temp
, node
, tree_size (node
));
3132 GIMPLE_STMT_OPERAND (temp
, 0) =
3133 poolify_tree (GIMPLE_STMT_OPERAND (temp
, 0));
3134 GIMPLE_STMT_OPERAND (temp
, 1) =
3135 poolify_tree (GIMPLE_STMT_OPERAND (temp
, 1));
3152 static tree modify_expr_template
;
3154 /* Allocate a GIMPLE_MODIFY_STMT with TYPE, and operands OP1, OP2 in the
3155 alloc pools and return it. */
3157 poolify_modify_stmt (tree op1
, tree op2
)
3159 if (modify_expr_template
== NULL
)
3160 modify_expr_template
= build_gimple_modify_stmt (op1
, op2
);
3162 GIMPLE_STMT_OPERAND (modify_expr_template
, 0) = op1
;
3163 GIMPLE_STMT_OPERAND (modify_expr_template
, 1) = op2
;
3165 return poolify_tree (modify_expr_template
);
3169 /* For each real store operation of the form
3170 *a = <value> that we see, create a corresponding fake store of the
3171 form storetmp_<version> = *a.
3173 This enables AVAIL computation to mark the results of stores as
3174 available. Without this, you'd need to do some computation to
3175 mark the result of stores as ANTIC and AVAIL at all the right
3177 To save memory, we keep the store
3178 statements pool allocated until we decide whether they are
3179 necessary or not. */
3182 insert_fake_stores (void)
3188 block_stmt_iterator bsi
;
3189 for (bsi
= bsi_start (block
); !bsi_end_p (bsi
); bsi_next (&bsi
))
3191 tree stmt
= bsi_stmt (bsi
);
3193 /* We can't generate SSA names for stores that are complex
3194 or aggregate. We also want to ignore things whose
3195 virtual uses occur in abnormal phis. */
3197 if (TREE_CODE (stmt
) == GIMPLE_MODIFY_STMT
3198 && TREE_CODE (GIMPLE_STMT_OPERAND (stmt
, 0)) == INDIRECT_REF
3199 && !AGGREGATE_TYPE_P (TREE_TYPE (GIMPLE_STMT_OPERAND (stmt
, 0)))
3200 && TREE_CODE (TREE_TYPE (GIMPLE_STMT_OPERAND
3201 (stmt
, 0))) != COMPLEX_TYPE
)
3205 tree lhs
= GIMPLE_STMT_OPERAND (stmt
, 0);
3206 tree rhs
= GIMPLE_STMT_OPERAND (stmt
, 1);
3208 bool notokay
= false;
3210 FOR_EACH_SSA_DEF_OPERAND (defp
, stmt
, iter
, SSA_OP_VIRTUAL_DEFS
)
3212 tree defvar
= DEF_FROM_PTR (defp
);
3213 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (defvar
))
3223 if (!storetemp
|| TREE_TYPE (rhs
) != TREE_TYPE (storetemp
))
3225 storetemp
= create_tmp_var (TREE_TYPE (rhs
), "storetmp");
3226 if (TREE_CODE (TREE_TYPE (storetemp
)) == VECTOR_TYPE
)
3227 DECL_GIMPLE_REG_P (storetemp
) = 1;
3228 get_var_ann (storetemp
);
3231 new_tree
= poolify_modify_stmt (storetemp
, lhs
);
3233 lhs
= make_ssa_name (storetemp
, new_tree
);
3234 GIMPLE_STMT_OPERAND (new_tree
, 0) = lhs
;
3235 create_ssa_artificial_load_stmt (new_tree
, stmt
);
3237 NECESSARY (new_tree
) = 0;
3238 VEC_safe_push (tree
, heap
, inserted_exprs
, new_tree
);
3239 VEC_safe_push (tree
, heap
, need_creation
, new_tree
);
3240 bsi_insert_after (&bsi
, new_tree
, BSI_NEW_STMT
);
3246 /* Turn the pool allocated fake stores that we created back into real
3247 GC allocated ones if they turned out to be necessary to PRE some
3251 realify_fake_stores (void)
3256 for (i
= 0; VEC_iterate (tree
, need_creation
, i
, stmt
); i
++)
3258 if (NECESSARY (stmt
))
3260 block_stmt_iterator bsi
;
3263 /* Mark the temp variable as referenced */
3264 add_referenced_var (SSA_NAME_VAR (GIMPLE_STMT_OPERAND (stmt
, 0)));
3266 /* Put the new statement in GC memory, fix up the
3267 SSA_NAME_DEF_STMT on it, and then put it in place of
3268 the old statement before the store in the IR stream
3269 as a plain ssa name copy. */
3270 bsi
= bsi_for_stmt (stmt
);
3272 tmp
= GIMPLE_STMT_OPERAND (bsi_stmt (bsi
), 1);
3273 newstmt
= build_gimple_modify_stmt (GIMPLE_STMT_OPERAND (stmt
, 0),
3275 SSA_NAME_DEF_STMT (GIMPLE_STMT_OPERAND (newstmt
, 0)) = newstmt
;
3276 bsi_insert_before (&bsi
, newstmt
, BSI_SAME_STMT
);
3277 bsi
= bsi_for_stmt (stmt
);
3278 bsi_remove (&bsi
, true);
3281 release_defs (stmt
);
3285 /* Given an SSA_NAME, see if SCCVN has a value number for it, and if
3286 so, return the value handle for this value number, creating it if
3288 Return NULL if SCCVN has no info for us. */
3291 get_sccvn_value (tree name
)
3293 if (TREE_CODE (name
) == SSA_NAME
3294 && VN_INFO (name
)->valnum
!= name
3295 && VN_INFO (name
)->valnum
!= VN_TOP
)
3297 tree val
= VN_INFO (name
)->valnum
;
3298 bool is_invariant
= is_gimple_min_invariant (val
);
3299 tree valvh
= !is_invariant
? get_value_handle (val
) : NULL_TREE
;
3301 /* We may end up with situations where SCCVN has chosen a
3302 representative for the equivalence set that we have not
3303 visited yet. In this case, just create the value handle for
3305 if (!valvh
&& !is_invariant
)
3307 tree defstmt
= SSA_NAME_DEF_STMT (val
);
3309 gcc_assert (VN_INFO (val
)->valnum
== val
);
3310 /* PHI nodes can't have vuses and attempts to iterate over
3311 their VUSE operands will crash. */
3312 if (TREE_CODE (defstmt
) == PHI_NODE
|| IS_EMPTY_STMT (defstmt
))
3315 tree defstmt2
= SSA_NAME_DEF_STMT (name
);
3316 if (TREE_CODE (defstmt2
) != PHI_NODE
&&
3317 !ZERO_SSA_OPERANDS (defstmt2
, SSA_OP_ALL_VIRTUALS
))
3318 gcc_assert (defstmt
);
3320 valvh
= vn_lookup_or_add_with_stmt (val
, defstmt
);
3323 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3325 fprintf (dump_file
, "SCCVN says ");
3326 print_generic_expr (dump_file
, name
, 0);
3327 fprintf (dump_file
, " value numbers to ");
3328 if (valvh
&& !is_invariant
)
3330 print_generic_expr (dump_file
, val
, 0);
3331 fprintf (dump_file
, " (");
3332 print_generic_expr (dump_file
, valvh
, 0);
3333 fprintf (dump_file
, ")\n");
3336 print_generic_stmt (dump_file
, val
, 0);
3346 /* Create value handles for PHI in BLOCK. */
3349 make_values_for_phi (tree phi
, basic_block block
)
3351 tree result
= PHI_RESULT (phi
);
3352 /* We have no need for virtual phis, as they don't represent
3353 actual computations. */
3354 if (is_gimple_reg (result
))
3356 tree sccvnval
= get_sccvn_value (result
);
3359 vn_add (result
, sccvnval
);
3360 bitmap_insert_into_set (PHI_GEN (block
), result
);
3361 bitmap_value_insert_into_set (AVAIL_OUT (block
), result
);
3364 add_to_sets (result
, result
, NULL
,
3365 PHI_GEN (block
), AVAIL_OUT (block
));
3370 /* Create value handles for STMT in BLOCK. Return true if we handled
3374 make_values_for_stmt (tree stmt
, basic_block block
)
3377 tree lhs
= GIMPLE_STMT_OPERAND (stmt
, 0);
3378 tree rhs
= GIMPLE_STMT_OPERAND (stmt
, 1);
3379 tree valvh
= NULL_TREE
;
3382 valvh
= get_sccvn_value (lhs
);
3385 vn_add (lhs
, valvh
);
3386 bitmap_value_insert_into_set (AVAIL_OUT (block
), lhs
);
3387 /* Shortcut for FRE. We have no need to create value expressions,
3388 just want to know what values are available where. */
3395 /* For FRE, if SCCVN didn't find anything, we aren't going to
3396 either, so just make up a new value number if necessary and
3398 if (get_value_handle (lhs
) == NULL
)
3399 vn_lookup_or_add (lhs
);
3400 bitmap_value_insert_into_set (AVAIL_OUT (block
), lhs
);
3404 lhsval
= valvh
? valvh
: get_value_handle (lhs
);
3406 STRIP_USELESS_TYPE_CONVERSION (rhs
);
3407 if (can_value_number_operation (rhs
))
3409 /* For value numberable operation, create a
3410 duplicate expression with the operands replaced
3411 with the value handles of the original RHS. */
3412 tree newt
= create_value_expr_from (rhs
, block
, stmt
);
3415 /* If we already have a value number for the LHS, reuse
3416 it rather than creating a new one. */
3419 set_value_handle (newt
, lhsval
);
3420 if (!is_gimple_min_invariant (lhsval
))
3421 add_to_value (lhsval
, newt
);
3425 tree val
= vn_lookup_or_add_with_stmt (newt
, stmt
);
3429 add_to_exp_gen (block
, newt
);
3432 bitmap_insert_into_set (TMP_GEN (block
), lhs
);
3433 bitmap_value_insert_into_set (AVAIL_OUT (block
), lhs
);
3436 else if ((TREE_CODE (rhs
) == SSA_NAME
3437 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs
))
3438 || is_gimple_min_invariant (rhs
)
3439 || TREE_CODE (rhs
) == ADDR_EXPR
3440 || TREE_INVARIANT (rhs
)
3446 set_value_handle (rhs
, lhsval
);
3447 if (!is_gimple_min_invariant (lhsval
))
3448 add_to_value (lhsval
, rhs
);
3449 bitmap_insert_into_set (TMP_GEN (block
), lhs
);
3450 bitmap_value_insert_into_set (AVAIL_OUT (block
), lhs
);
3454 /* Compute a value number for the RHS of the statement
3455 and add its value to the AVAIL_OUT set for the block.
3456 Add the LHS to TMP_GEN. */
3457 add_to_sets (lhs
, rhs
, stmt
, TMP_GEN (block
),
3460 /* None of the rest of these can be PRE'd. */
3461 if (TREE_CODE (rhs
) == SSA_NAME
&& !is_undefined_value (rhs
))
3462 add_to_exp_gen (block
, rhs
);
3469 /* Compute the AVAIL set for all basic blocks.
3471 This function performs value numbering of the statements in each basic
3472 block. The AVAIL sets are built from information we glean while doing
3473 this value numbering, since the AVAIL sets contain only one entry per
3476 AVAIL_IN[BLOCK] = AVAIL_OUT[dom(BLOCK)].
3477 AVAIL_OUT[BLOCK] = AVAIL_IN[BLOCK] U PHI_GEN[BLOCK] U TMP_GEN[BLOCK]. */
3480 compute_avail (void)
3482 basic_block block
, son
;
3483 basic_block
*worklist
;
3487 /* For arguments with default definitions, we pretend they are
3488 defined in the entry block. */
3489 for (param
= DECL_ARGUMENTS (current_function_decl
);
3491 param
= TREE_CHAIN (param
))
3493 if (gimple_default_def (cfun
, param
) != NULL
)
3495 tree def
= gimple_default_def (cfun
, param
);
3497 vn_lookup_or_add (def
);
3500 bitmap_insert_into_set (TMP_GEN (ENTRY_BLOCK_PTR
), def
);
3501 bitmap_value_insert_into_set (maximal_set
, def
);
3503 bitmap_value_insert_into_set (AVAIL_OUT (ENTRY_BLOCK_PTR
), def
);
3507 /* Likewise for the static chain decl. */
3508 if (cfun
->static_chain_decl
)
3510 param
= cfun
->static_chain_decl
;
3511 if (gimple_default_def (cfun
, param
) != NULL
)
3513 tree def
= gimple_default_def (cfun
, param
);
3515 vn_lookup_or_add (def
);
3518 bitmap_insert_into_set (TMP_GEN (ENTRY_BLOCK_PTR
), def
);
3519 bitmap_value_insert_into_set (maximal_set
, def
);
3521 bitmap_value_insert_into_set (AVAIL_OUT (ENTRY_BLOCK_PTR
), def
);
3525 /* Allocate the worklist. */
3526 worklist
= XNEWVEC (basic_block
, n_basic_blocks
);
3528 /* Seed the algorithm by putting the dominator children of the entry
3529 block on the worklist. */
3530 for (son
= first_dom_son (CDI_DOMINATORS
, ENTRY_BLOCK_PTR
);
3532 son
= next_dom_son (CDI_DOMINATORS
, son
))
3533 worklist
[sp
++] = son
;
3535 /* Loop until the worklist is empty. */
3538 block_stmt_iterator bsi
;
3541 unsigned int stmt_uid
= 1;
3543 /* Pick a block from the worklist. */
3544 block
= worklist
[--sp
];
3546 /* Initially, the set of available values in BLOCK is that of
3547 its immediate dominator. */
3548 dom
= get_immediate_dominator (CDI_DOMINATORS
, block
);
3550 bitmap_set_copy (AVAIL_OUT (block
), AVAIL_OUT (dom
));
3552 /* Generate values for PHI nodes. */
3553 for (phi
= phi_nodes (block
); phi
; phi
= PHI_CHAIN (phi
))
3554 make_values_for_phi (phi
, block
);
3556 /* Now compute value numbers and populate value sets with all
3557 the expressions computed in BLOCK. */
3558 for (bsi
= bsi_start (block
); !bsi_end_p (bsi
); bsi_next (&bsi
))
3564 stmt
= bsi_stmt (bsi
);
3565 ann
= stmt_ann (stmt
);
3567 ann
->uid
= stmt_uid
++;
3569 /* For regular value numbering, we are only interested in
3570 assignments of the form X_i = EXPR, where EXPR represents
3571 an "interesting" computation, it has no volatile operands
3572 and X_i doesn't flow through an abnormal edge. */
3573 if (TREE_CODE (stmt
) == RETURN_EXPR
3574 && !ann
->has_volatile_ops
)
3576 tree realstmt
= stmt
;
3580 stmt
= TREE_OPERAND (stmt
, 0);
3581 if (stmt
&& TREE_CODE (stmt
) == GIMPLE_MODIFY_STMT
)
3583 lhs
= GIMPLE_STMT_OPERAND (stmt
, 0);
3584 rhs
= GIMPLE_STMT_OPERAND (stmt
, 1);
3585 if (TREE_CODE (lhs
) == SSA_NAME
3586 && is_gimple_min_invariant (VN_INFO (lhs
)->valnum
))
3588 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3590 fprintf (dump_file
, "SCCVN says ");
3591 print_generic_expr (dump_file
, lhs
, 0);
3592 fprintf (dump_file
, " value numbers to ");
3593 print_generic_stmt (dump_file
, VN_INFO (lhs
)->valnum
,
3596 vn_add (lhs
, VN_INFO (lhs
)->valnum
);
3600 if (TREE_CODE (rhs
) == SSA_NAME
)
3601 add_to_exp_gen (block
, rhs
);
3603 FOR_EACH_SSA_TREE_OPERAND (op
, realstmt
, iter
, SSA_OP_DEF
)
3604 add_to_sets (op
, op
, NULL
, TMP_GEN (block
),
3610 else if (TREE_CODE (stmt
) == GIMPLE_MODIFY_STMT
3611 && !ann
->has_volatile_ops
3612 && TREE_CODE (GIMPLE_STMT_OPERAND (stmt
, 0)) == SSA_NAME
3613 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI
3614 (GIMPLE_STMT_OPERAND (stmt
, 0)))
3616 if (make_values_for_stmt (stmt
, block
))
3621 /* For any other statement that we don't recognize, simply
3622 make the names generated by the statement available in
3623 AVAIL_OUT and TMP_GEN. */
3624 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, iter
, SSA_OP_DEF
)
3625 add_to_sets (op
, op
, NULL
, TMP_GEN (block
), AVAIL_OUT (block
));
3627 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, iter
, SSA_OP_USE
)
3629 add_to_sets (op
, op
, NULL
, NULL
, AVAIL_OUT (block
));
3630 if (TREE_CODE (op
) == SSA_NAME
|| can_PRE_operation (op
))
3631 add_to_exp_gen (block
, op
);
3635 /* Put the dominator children of BLOCK on the worklist of blocks
3636 to compute available sets for. */
3637 for (son
= first_dom_son (CDI_DOMINATORS
, block
);
3639 son
= next_dom_son (CDI_DOMINATORS
, son
))
3640 worklist
[sp
++] = son
;
3647 /* Eliminate fully redundant computations. */
3656 block_stmt_iterator i
;
3658 for (i
= bsi_start (b
); !bsi_end_p (i
); bsi_next (&i
))
3660 tree stmt
= bsi_stmt (i
);
3662 /* Lookup the RHS of the expression, see if we have an
3663 available computation for it. If so, replace the RHS with
3664 the available computation. */
3665 if (TREE_CODE (stmt
) == GIMPLE_MODIFY_STMT
3666 && TREE_CODE (GIMPLE_STMT_OPERAND (stmt
, 0)) == SSA_NAME
3667 && TREE_CODE (GIMPLE_STMT_OPERAND (stmt
, 1)) != SSA_NAME
3668 && !is_gimple_min_invariant (GIMPLE_STMT_OPERAND (stmt
, 1))
3669 && !stmt_ann (stmt
)->has_volatile_ops
)
3671 tree lhs
= GIMPLE_STMT_OPERAND (stmt
, 0);
3672 tree
*rhs_p
= &GIMPLE_STMT_OPERAND (stmt
, 1);
3675 sprime
= bitmap_find_leader (AVAIL_OUT (b
),
3676 get_value_handle (lhs
));
3680 && (TREE_CODE (*rhs_p
) != SSA_NAME
3681 || may_propagate_copy (*rhs_p
, sprime
)))
3683 gcc_assert (sprime
!= *rhs_p
);
3685 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3687 fprintf (dump_file
, "Replaced ");
3688 print_generic_expr (dump_file
, *rhs_p
, 0);
3689 fprintf (dump_file
, " with ");
3690 print_generic_expr (dump_file
, sprime
, 0);
3691 fprintf (dump_file
, " in ");
3692 print_generic_stmt (dump_file
, stmt
, 0);
3695 if (TREE_CODE (sprime
) == SSA_NAME
)
3696 NECESSARY (SSA_NAME_DEF_STMT (sprime
)) = 1;
3697 /* We need to make sure the new and old types actually match,
3698 which may require adding a simple cast, which fold_convert
3700 if (TREE_CODE (*rhs_p
) != SSA_NAME
3701 && !tree_ssa_useless_type_conversion_1 (TREE_TYPE (*rhs_p
),
3702 TREE_TYPE (sprime
)))
3703 sprime
= fold_convert (TREE_TYPE (*rhs_p
), sprime
);
3705 pre_stats
.eliminations
++;
3706 propagate_tree_value (rhs_p
, sprime
);
3709 /* If we removed EH side effects from the statement, clean
3710 its EH information. */
3711 if (maybe_clean_or_replace_eh_stmt (stmt
, stmt
))
3713 bitmap_set_bit (need_eh_cleanup
,
3714 bb_for_stmt (stmt
)->index
);
3715 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3716 fprintf (dump_file
, " Removed EH side effects.\n");
3724 /* Borrow a bit of tree-ssa-dce.c for the moment.
3725 XXX: In 4.1, we should be able to just run a DCE pass after PRE, though
3726 this may be a bit faster, and we may want critical edges kept split. */
3728 /* If OP's defining statement has not already been determined to be necessary,
3729 mark that statement necessary. Return the stmt, if it is newly
3733 mark_operand_necessary (tree op
)
3739 if (TREE_CODE (op
) != SSA_NAME
)
3742 stmt
= SSA_NAME_DEF_STMT (op
);
3745 if (NECESSARY (stmt
)
3746 || IS_EMPTY_STMT (stmt
))
3749 NECESSARY (stmt
) = 1;
3753 /* Because we don't follow exactly the standard PRE algorithm, and decide not
3754 to insert PHI nodes sometimes, and because value numbering of casts isn't
3755 perfect, we sometimes end up inserting dead code. This simple DCE-like
3756 pass removes any insertions we made that weren't actually used. */
3759 remove_dead_inserted_code (void)
3761 VEC(tree
,heap
) *worklist
= NULL
;
3765 worklist
= VEC_alloc (tree
, heap
, VEC_length (tree
, inserted_exprs
));
3766 for (i
= 0; VEC_iterate (tree
, inserted_exprs
, i
, t
); i
++)
3769 VEC_quick_push (tree
, worklist
, t
);
3771 while (VEC_length (tree
, worklist
) > 0)
3773 t
= VEC_pop (tree
, worklist
);
3775 /* PHI nodes are somewhat special in that each PHI alternative has
3776 data and control dependencies. All the statements feeding the
3777 PHI node's arguments are always necessary. */
3778 if (TREE_CODE (t
) == PHI_NODE
)
3782 VEC_reserve (tree
, heap
, worklist
, PHI_NUM_ARGS (t
));
3783 for (k
= 0; k
< PHI_NUM_ARGS (t
); k
++)
3785 tree arg
= PHI_ARG_DEF (t
, k
);
3786 if (TREE_CODE (arg
) == SSA_NAME
)
3788 arg
= mark_operand_necessary (arg
);
3790 VEC_quick_push (tree
, worklist
, arg
);
3796 /* Propagate through the operands. Examine all the USE, VUSE and
3797 VDEF operands in this statement. Mark all the statements
3798 which feed this statement's uses as necessary. */
3802 /* The operands of VDEF expressions are also needed as they
3803 represent potential definitions that may reach this
3804 statement (VDEF operands allow us to follow def-def
3807 FOR_EACH_SSA_TREE_OPERAND (use
, t
, iter
, SSA_OP_ALL_USES
)
3809 tree n
= mark_operand_necessary (use
);
3811 VEC_safe_push (tree
, heap
, worklist
, n
);
3816 for (i
= 0; VEC_iterate (tree
, inserted_exprs
, i
, t
); i
++)
3820 block_stmt_iterator bsi
;
3822 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3824 fprintf (dump_file
, "Removing unnecessary insertion:");
3825 print_generic_stmt (dump_file
, t
, 0);
3828 if (TREE_CODE (t
) == PHI_NODE
)
3830 remove_phi_node (t
, NULL
, true);
3834 bsi
= bsi_for_stmt (t
);
3835 bsi_remove (&bsi
, true);
3840 VEC_free (tree
, heap
, worklist
);
3843 /* Initialize data structures used by PRE. */
3846 init_pre (bool do_fre
)
3850 next_expression_id
= 0;
3854 inserted_exprs
= NULL
;
3855 need_creation
= NULL
;
3856 pretemp
= NULL_TREE
;
3857 storetemp
= NULL_TREE
;
3858 prephitemp
= NULL_TREE
;
3861 loop_optimizer_init (LOOPS_NORMAL
);
3863 connect_infinite_loops_to_exit ();
3864 memset (&pre_stats
, 0, sizeof (pre_stats
));
3867 postorder
= XNEWVEC (int, n_basic_blocks
- NUM_FIXED_BLOCKS
);
3868 post_order_compute (postorder
, false, false);
3871 bb
->aux
= xcalloc (1, sizeof (struct bb_bitmap_sets
));
3873 calculate_dominance_info (CDI_POST_DOMINATORS
);
3874 calculate_dominance_info (CDI_DOMINATORS
);
3876 bitmap_obstack_initialize (&grand_bitmap_obstack
);
3877 phi_translate_table
= htab_create (5110, expr_pred_trans_hash
,
3878 expr_pred_trans_eq
, free
);
3879 seen_during_translate
= BITMAP_ALLOC (&grand_bitmap_obstack
);
3880 bitmap_set_pool
= create_alloc_pool ("Bitmap sets",
3881 sizeof (struct bitmap_set
), 30);
3882 binary_node_pool
= create_alloc_pool ("Binary tree nodes",
3883 tree_code_size (PLUS_EXPR
), 30);
3884 unary_node_pool
= create_alloc_pool ("Unary tree nodes",
3885 tree_code_size (NEGATE_EXPR
), 30);
3886 reference_node_pool
= create_alloc_pool ("Reference tree nodes",
3887 tree_code_size (ARRAY_REF
), 30);
3888 comparison_node_pool
= create_alloc_pool ("Comparison tree nodes",
3889 tree_code_size (EQ_EXPR
), 30);
3890 modify_expr_node_pool
= create_alloc_pool ("GIMPLE_MODIFY_STMT nodes",
3891 tree_code_size (GIMPLE_MODIFY_STMT
),
3893 obstack_init (&temp_call_expr_obstack
);
3894 modify_expr_template
= NULL
;
3898 EXP_GEN (bb
) = bitmap_set_new ();
3899 PHI_GEN (bb
) = bitmap_set_new ();
3900 TMP_GEN (bb
) = bitmap_set_new ();
3901 AVAIL_OUT (bb
) = bitmap_set_new ();
3903 maximal_set
= in_fre
? NULL
: bitmap_set_new ();
3905 need_eh_cleanup
= BITMAP_ALLOC (NULL
);
3909 /* Deallocate data structures used by PRE. */
3918 VEC_free (tree
, heap
, inserted_exprs
);
3919 VEC_free (tree
, heap
, need_creation
);
3920 bitmap_obstack_release (&grand_bitmap_obstack
);
3921 free_alloc_pool (bitmap_set_pool
);
3922 free_alloc_pool (binary_node_pool
);
3923 free_alloc_pool (reference_node_pool
);
3924 free_alloc_pool (unary_node_pool
);
3925 free_alloc_pool (comparison_node_pool
);
3926 free_alloc_pool (modify_expr_node_pool
);
3927 htab_delete (phi_translate_table
);
3928 remove_fake_exit_edges ();
3936 free_dominance_info (CDI_POST_DOMINATORS
);
3938 if (!bitmap_empty_p (need_eh_cleanup
))
3940 tree_purge_all_dead_eh_edges (need_eh_cleanup
);
3941 cleanup_tree_cfg ();
3944 BITMAP_FREE (need_eh_cleanup
);
3946 /* Wipe out pointers to VALUE_HANDLEs. In the not terribly distant
3947 future we will want them to be persistent though. */
3948 for (i
= 0; i
< num_ssa_names
; i
++)
3950 tree name
= ssa_name (i
);
3955 if (SSA_NAME_VALUE (name
)
3956 && TREE_CODE (SSA_NAME_VALUE (name
)) == VALUE_HANDLE
)
3957 SSA_NAME_VALUE (name
) = NULL
;
3959 if (current_loops
!= NULL
)
3960 loop_optimizer_finalize ();
3963 /* Main entry point to the SSA-PRE pass. DO_FRE is true if the caller
3964 only wants to do full redundancy elimination. */
3967 execute_pre (bool do_fre
)
3970 do_partial_partial
= optimize
> 2;
3974 insert_fake_stores ();
3976 /* Collect and value number expressions computed in each basic block. */
3978 switch_to_PRE_table ();
3981 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3987 print_bitmap_set (dump_file
, EXP_GEN (bb
), "exp_gen", bb
->index
);
3988 print_bitmap_set (dump_file
, TMP_GEN (bb
), "tmp_gen",
3990 print_bitmap_set (dump_file
, AVAIL_OUT (bb
), "avail_out",
3995 /* Insert can get quite slow on an incredibly large number of basic
3996 blocks due to some quadratic behavior. Until this behavior is
3997 fixed, don't run it when he have an incredibly large number of
3998 bb's. If we aren't going to run insert, there is no point in
3999 computing ANTIC, either, even though it's plenty fast. */
4000 if (!do_fre
&& n_basic_blocks
< 4000)
4002 compute_antic_safe ();
4007 /* Remove all the redundant expressions. */
4010 if (dump_file
&& (dump_flags
& TDF_STATS
))
4012 fprintf (dump_file
, "Insertions: %d\n", pre_stats
.insertions
);
4013 fprintf (dump_file
, "PA inserted: %d\n", pre_stats
.pa_insert
);
4014 fprintf (dump_file
, "New PHIs: %d\n", pre_stats
.phis
);
4015 fprintf (dump_file
, "Eliminated: %d\n", pre_stats
.eliminations
);
4016 fprintf (dump_file
, "Constified: %d\n", pre_stats
.constified
);
4018 bsi_commit_edge_inserts ();
4021 clear_expression_ids ();
4024 remove_dead_inserted_code ();
4025 realify_fake_stores ();
4031 /* Gate and execute functions for PRE. */
4036 execute_pre (false);
4043 return flag_tree_pre
!= 0;
4046 struct tree_opt_pass pass_pre
=
4049 gate_pre
, /* gate */
4050 do_pre
, /* execute */
4053 0, /* static_pass_number */
4054 TV_TREE_PRE
, /* tv_id */
4055 PROP_no_crit_edges
| PROP_cfg
4056 | PROP_ssa
| PROP_alias
, /* properties_required */
4057 0, /* properties_provided */
4058 0, /* properties_destroyed */
4059 0, /* todo_flags_start */
4060 TODO_update_ssa_only_virtuals
| TODO_dump_func
| TODO_ggc_collect
4061 | TODO_verify_ssa
, /* todo_flags_finish */
4066 /* Gate and execute functions for FRE. */
4078 return flag_tree_fre
!= 0;
4081 struct tree_opt_pass pass_fre
=
4084 gate_fre
, /* gate */
4085 execute_fre
, /* execute */
4088 0, /* static_pass_number */
4089 TV_TREE_FRE
, /* tv_id */
4090 PROP_cfg
| PROP_ssa
| PROP_alias
, /* properties_required */
4091 0, /* properties_provided */
4092 0, /* properties_destroyed */
4093 0, /* todo_flags_start */
4094 TODO_dump_func
| TODO_ggc_collect
| TODO_verify_ssa
, /* todo_flags_finish */