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"
51 1. Avail sets can be shared by making an avail_find_leader that
52 walks up the dominator tree and looks in those avail sets.
53 This might affect code optimality, it's unclear right now.
54 2. Strength reduction can be performed by anticipating expressions
55 we can repair later on.
56 3. We can do back-substitution or smarter value numbering to catch
57 commutative expressions split up over multiple statements.
60 /* For ease of terminology, "expression node" in the below refers to
61 every expression node but GIMPLE_MODIFY_STMT, because GIMPLE_MODIFY_STMT's
62 represent the actual statement containing the expressions we care about,
63 and we cache the value number by putting it in the expression. */
67 First we walk the statements to generate the AVAIL sets, the
68 EXP_GEN sets, and the tmp_gen sets. EXP_GEN sets represent the
69 generation of values/expressions by a given block. We use them
70 when computing the ANTIC sets. The AVAIL sets consist of
71 SSA_NAME's that represent values, so we know what values are
72 available in what blocks. AVAIL is a forward dataflow problem. In
73 SSA, values are never killed, so we don't need a kill set, or a
74 fixpoint iteration, in order to calculate the AVAIL sets. In
75 traditional parlance, AVAIL sets tell us the downsafety of the
78 Next, we generate the ANTIC sets. These sets represent the
79 anticipatable expressions. ANTIC is a backwards dataflow
80 problem. An expression is anticipatable in a given block if it could
81 be generated in that block. This means that if we had to perform
82 an insertion in that block, of the value of that expression, we
83 could. Calculating the ANTIC sets requires phi translation of
84 expressions, because the flow goes backwards through phis. We must
85 iterate to a fixpoint of the ANTIC sets, because we have a kill
86 set. Even in SSA form, values are not live over the entire
87 function, only from their definition point onwards. So we have to
88 remove values from the ANTIC set once we go past the definition
89 point of the leaders that make them up.
90 compute_antic/compute_antic_aux performs this computation.
92 Third, we perform insertions to make partially redundant
93 expressions fully redundant.
95 An expression is partially redundant (excluding partial
98 1. It is AVAIL in some, but not all, of the predecessors of a
100 2. It is ANTIC in all the predecessors.
102 In order to make it fully redundant, we insert the expression into
103 the predecessors where it is not available, but is ANTIC.
105 For the partial anticipation case, we only perform insertion if it
106 is partially anticipated in some block, and fully available in all
109 insert/insert_aux/do_regular_insertion/do_partial_partial_insertion
110 performs these steps.
112 Fourth, we eliminate fully redundant expressions.
113 This is a simple statement walk that replaces redundant
114 calculations with the now available values. */
116 /* Representations of value numbers:
118 Value numbers are represented using the "value handle" approach.
119 This means that each SSA_NAME (and for other reasons to be
120 disclosed in a moment, expression nodes) has a value handle that
121 can be retrieved through get_value_handle. This value handle *is*
122 the value number of the SSA_NAME. You can pointer compare the
123 value handles for equivalence purposes.
125 For debugging reasons, the value handle is internally more than
126 just a number, it is a VALUE_HANDLE named "VH.x", where x is a
127 unique number for each value number in use. This allows
128 expressions with SSA_NAMES replaced by value handles to still be
129 pretty printed in a sane way. They simply print as "VH.3 *
132 Expression nodes have value handles associated with them as a
133 cache. Otherwise, we'd have to look them up again in the hash
134 table This makes significant difference (factor of two or more) on
135 some test cases. They can be thrown away after the pass is
138 /* Representation of expressions on value numbers:
140 In some portions of this code, you will notice we allocate "fake"
141 analogues to the expression we are value numbering, and replace the
142 operands with the values of the expression. Since we work on
143 values, and not just names, we canonicalize expressions to value
144 expressions for use in the ANTIC sets, the EXP_GEN set, etc.
146 This is theoretically unnecessary, it just saves a bunch of
147 repeated get_value_handle and find_leader calls in the remainder of
148 the code, trading off temporary memory usage for speed. The tree
149 nodes aren't actually creating more garbage, since they are
150 allocated in a special pools which are thrown away at the end of
153 All of this also means that if you print the EXP_GEN or ANTIC sets,
154 you will see "VH.5 + VH.7" in the set, instead of "a_55 +
155 b_66" or something. The only thing that actually cares about
156 seeing the value leaders is phi translation, and it needs to be
157 able to find the leader for a value in an arbitrary block, so this
158 "value expression" form is perfect for it (otherwise you'd do
159 get_value_handle->find_leader->translate->get_value_handle->find_leader).*/
162 /* Representation of sets:
164 There are currently two types of sets used, hopefully to be unified soon.
165 The AVAIL sets do not need to be sorted in any particular order,
166 and thus, are simply represented as two bitmaps, one that keeps
167 track of values present in the set, and one that keeps track of
168 expressions present in the set.
170 The other sets are represented as doubly linked lists kept in topological
171 order, with an optional supporting bitmap of values present in the
172 set. The sets represent values, and the elements can be values or
173 expressions. The elements can appear in different sets, but each
174 element can only appear once in each set.
176 Since each node in the set represents a value, we also want to be
177 able to map expression, set pairs to something that tells us
178 whether the value is present is a set. We use a per-set bitmap for
179 that. The value handles also point to a linked list of the
180 expressions they represent via a tree annotation. This is mainly
181 useful only for debugging, since we don't do identity lookups. */
184 /* Next global expression id number. */
185 static unsigned int next_expression_id;
187 /* Mapping from expression to id number we can use in bitmap sets. */
188 static VEC(tree, heap) *expressions;
190 /* Allocate an expression id for EXPR. */
192 static inline unsigned int
193 alloc_expression_id (tree expr)
195 tree_ann_common_t ann;
197 ann = get_tree_common_ann (expr);
199 /* Make sure we won't overflow. */
200 gcc_assert (next_expression_id + 1 > next_expression_id);
202 ann->aux = XNEW (unsigned int);
203 * ((unsigned int *)ann->aux) = next_expression_id++;
204 VEC_safe_push (tree, heap, expressions, expr);
205 return next_expression_id - 1;
208 /* Return the expression id for tree EXPR. */
210 static inline unsigned int
211 get_expression_id (tree expr)
213 tree_ann_common_t ann = tree_common_ann (expr);
215 gcc_assert (ann->aux);
217 return *((unsigned int *)ann->aux);
220 /* Return the existing expression id for EXPR, or create one if one
221 does not exist yet. */
223 static inline unsigned int
224 get_or_alloc_expression_id (tree expr)
226 tree_ann_common_t ann = tree_common_ann (expr);
228 if (ann == NULL || !ann->aux)
229 return alloc_expression_id (expr);
231 return get_expression_id (expr);
234 /* Return the expression that has expression id ID */
237 expression_for_id (unsigned int id)
239 return VEC_index (tree, expressions, id);
242 /* Free the expression id field in all of our expressions,
243 and then destroy the expressions array. */
246 clear_expression_ids (void)
251 for (i = 0; VEC_iterate (tree, expressions, i, expr); i++)
253 free (tree_common_ann (expr)->aux);
254 tree_common_ann (expr)->aux = NULL;
256 VEC_free (tree, heap, expressions);
259 static bool in_fre = false;
261 /* An unordered bitmap set. One bitmap tracks values, the other,
263 typedef struct bitmap_set
269 #define FOR_EACH_EXPR_ID_IN_SET(set, id, bi) \
270 EXECUTE_IF_SET_IN_BITMAP(set->expressions, 0, id, bi)
272 /* Sets that we need to keep track of. */
273 typedef struct bb_bitmap_sets
275 /* The EXP_GEN set, which represents expressions/values generated in
277 bitmap_set_t exp_gen;
279 /* The PHI_GEN set, which represents PHI results generated in a
281 bitmap_set_t phi_gen;
283 /* The TMP_GEN set, which represents results/temporaries generated
284 in a basic block. IE the LHS of an expression. */
285 bitmap_set_t tmp_gen;
287 /* The AVAIL_OUT set, which represents which values are available in
288 a given basic block. */
289 bitmap_set_t avail_out;
291 /* The ANTIC_IN set, which represents which values are anticipatable
292 in a given basic block. */
293 bitmap_set_t antic_in;
295 /* The PA_IN set, which represents which values are
296 partially anticipatable in a given basic block. */
299 /* The NEW_SETS set, which is used during insertion to augment the
300 AVAIL_OUT set of blocks with the new insertions performed during
301 the current iteration. */
302 bitmap_set_t new_sets;
304 /* These are the loads that will be ANTIC_IN at the top of the
305 block, and are actually generated in the block. */
306 bitmap_set_t antic_safe_loads;
308 /* True if we have visited this block during ANTIC calculation. */
309 unsigned int visited:1;
311 /* True we have deferred processing this block during ANTIC
312 calculation until its successor is processed. */
313 unsigned int deferred : 1;
316 #define EXP_GEN(BB) ((bb_value_sets_t) ((BB)->aux))->exp_gen
317 #define PHI_GEN(BB) ((bb_value_sets_t) ((BB)->aux))->phi_gen
318 #define TMP_GEN(BB) ((bb_value_sets_t) ((BB)->aux))->tmp_gen
319 #define AVAIL_OUT(BB) ((bb_value_sets_t) ((BB)->aux))->avail_out
320 #define ANTIC_IN(BB) ((bb_value_sets_t) ((BB)->aux))->antic_in
321 #define PA_IN(BB) ((bb_value_sets_t) ((BB)->aux))->pa_in
322 #define NEW_SETS(BB) ((bb_value_sets_t) ((BB)->aux))->new_sets
323 #define ANTIC_SAFE_LOADS(BB) ((bb_value_sets_t) ((BB)->aux))->antic_safe_loads
324 #define BB_VISITED(BB) ((bb_value_sets_t) ((BB)->aux))->visited
325 #define BB_DEFERRED(BB) ((bb_value_sets_t) ((BB)->aux))->deferred
327 /* Maximal set of values, used to initialize the ANTIC problem, which
328 is an intersection problem. */
329 static bitmap_set_t maximal_set;
331 /* Basic block list in postorder. */
332 static int *postorder;
334 /* This structure is used to keep track of statistics on what
335 optimization PRE was able to perform. */
338 /* The number of RHS computations eliminated by PRE. */
341 /* The number of new expressions/temporaries generated by PRE. */
344 /* The number of inserts found due to partial anticipation */
347 /* The number of new PHI nodes added by PRE. */
350 /* The number of values found constant. */
355 static bool do_partial_partial;
356 static tree bitmap_find_leader (bitmap_set_t, tree);
357 static void bitmap_value_insert_into_set (bitmap_set_t, tree);
358 static void bitmap_value_replace_in_set (bitmap_set_t, tree);
359 static void bitmap_set_copy (bitmap_set_t, bitmap_set_t);
360 static bool bitmap_set_contains_value (bitmap_set_t, tree);
361 static void bitmap_insert_into_set (bitmap_set_t, tree);
362 static bitmap_set_t bitmap_set_new (void);
363 static bool is_undefined_value (tree);
364 static tree create_expression_by_pieces (basic_block, tree, tree);
365 static tree find_or_generate_expression (basic_block, tree, tree);
367 /* We can add and remove elements and entries to and from sets
368 and hash tables, so we use alloc pools for them. */
370 static alloc_pool bitmap_set_pool;
371 static alloc_pool binary_node_pool;
372 static alloc_pool unary_node_pool;
373 static alloc_pool reference_node_pool;
374 static alloc_pool comparison_node_pool;
375 static alloc_pool modify_expr_node_pool;
376 static bitmap_obstack grand_bitmap_obstack;
378 /* We can't use allocation pools to hold temporary CALL_EXPR objects, since
379 they are not of fixed size. Instead, use an obstack. */
381 static struct obstack temp_call_expr_obstack;
384 /* To avoid adding 300 temporary variables when we only need one, we
385 only create one temporary variable, on demand, and build ssa names
386 off that. We do have to change the variable if the types don't
387 match the current variable's type. */
389 static tree storetemp;
390 static tree prephitemp;
392 /* Set of blocks with statements that have had its EH information
394 static bitmap need_eh_cleanup;
396 /* The phi_translate_table caches phi translations for a given
397 expression and predecessor. */
399 static htab_t phi_translate_table;
401 /* A three tuple {e, pred, v} used to cache phi translations in the
402 phi_translate_table. */
404 typedef struct expr_pred_trans_d
406 /* The expression. */
409 /* The predecessor block along which we translated the expression. */
412 /* vuses associated with the expression. */
413 VEC (tree, gc) *vuses;
415 /* The value that resulted from the translation. */
418 /* The hashcode for the expression, pred pair. This is cached for
421 } *expr_pred_trans_t;
423 /* Return the hash value for a phi translation table entry. */
426 expr_pred_trans_hash (const void *p)
428 const expr_pred_trans_t ve = (expr_pred_trans_t) p;
432 /* Return true if two phi translation table entries are the same.
433 P1 and P2 should point to the expr_pred_trans_t's to be compared.*/
436 expr_pred_trans_eq (const void *p1, const void *p2)
438 const expr_pred_trans_t ve1 = (expr_pred_trans_t) p1;
439 const expr_pred_trans_t ve2 = (expr_pred_trans_t) p2;
440 basic_block b1 = ve1->pred;
441 basic_block b2 = ve2->pred;
445 /* If they are not translations for the same basic block, they can't
451 /* If they are for the same basic block, determine if the
452 expressions are equal. */
453 if (!expressions_equal_p (ve1->e, ve2->e))
456 /* Make sure the vuses are equivalent. */
457 if (ve1->vuses == ve2->vuses)
460 if (VEC_length (tree, ve1->vuses) != VEC_length (tree, ve2->vuses))
463 for (i = 0; VEC_iterate (tree, ve1->vuses, i, vuse1); i++)
465 if (VEC_index (tree, ve2->vuses, i) != vuse1)
472 /* Search in the phi translation table for the translation of
473 expression E in basic block PRED with vuses VUSES.
474 Return the translated value, if found, NULL otherwise. */
477 phi_trans_lookup (tree e, basic_block pred, VEC (tree, gc) *vuses)
480 struct expr_pred_trans_d ept;
485 ept.hashcode = vn_compute (e, (unsigned long) pred);
486 slot = htab_find_slot_with_hash (phi_translate_table, &ept, ept.hashcode,
491 return ((expr_pred_trans_t) *slot)->v;
495 /* Add the tuple mapping from {expression E, basic block PRED, vuses VUSES} to
496 value V, to the phi translation table. */
499 phi_trans_add (tree e, tree v, basic_block pred, VEC (tree, gc) *vuses)
502 expr_pred_trans_t new_pair = XNEW (struct expr_pred_trans_d);
504 new_pair->pred = pred;
505 new_pair->vuses = vuses;
507 new_pair->hashcode = vn_compute (e, (unsigned long) pred);
508 slot = htab_find_slot_with_hash (phi_translate_table, new_pair,
509 new_pair->hashcode, INSERT);
512 *slot = (void *) new_pair;
516 /* Return true if V is a value expression that represents itself.
517 In our world, this is *only* non-value handles. */
520 constant_expr_p (tree v)
522 return TREE_CODE (v) != VALUE_HANDLE && is_gimple_min_invariant (v);
523 /* return TREE_CODE (v) != VALUE_HANDLE; */
526 /* Add expression E to the expression set of value V. */
529 add_to_value (tree v, tree e)
531 /* Constants have no expression sets. */
532 if (constant_expr_p (v))
535 if (VALUE_HANDLE_EXPR_SET (v) == NULL)
536 VALUE_HANDLE_EXPR_SET (v) = bitmap_set_new ();
538 bitmap_insert_into_set (VALUE_HANDLE_EXPR_SET (v), e);
541 /* Create a new bitmap set and return it. */
544 bitmap_set_new (void)
546 bitmap_set_t ret = (bitmap_set_t) pool_alloc (bitmap_set_pool);
547 ret->expressions = BITMAP_ALLOC (&grand_bitmap_obstack);
548 ret->values = BITMAP_ALLOC (&grand_bitmap_obstack);
552 /* Remove an expression EXPR from a bitmapped set. */
555 bitmap_remove_from_set (bitmap_set_t set, tree expr)
557 tree val = get_value_handle (expr);
560 if (!constant_expr_p (val))
562 bitmap_clear_bit (set->values, VALUE_HANDLE_ID (val));
563 bitmap_clear_bit (set->expressions, get_expression_id (expr));
567 /* Insert an expression EXPR into a bitmapped set. */
570 bitmap_insert_into_set (bitmap_set_t set, tree expr)
572 tree val = get_value_handle (expr);
575 if (!constant_expr_p (val))
577 bitmap_set_bit (set->values, VALUE_HANDLE_ID (val));
578 bitmap_set_bit (set->expressions, get_or_alloc_expression_id (expr));
582 /* Copy a bitmapped set ORIG, into bitmapped set DEST. */
585 bitmap_set_copy (bitmap_set_t dest, bitmap_set_t orig)
587 bitmap_copy (dest->expressions, orig->expressions);
588 bitmap_copy (dest->values, orig->values);
592 /* Free memory used up by SET. */
594 bitmap_set_free (bitmap_set_t set)
596 BITMAP_FREE (set->expressions);
597 BITMAP_FREE (set->values);
601 /* A comparison function for use in qsort to top sort a bitmap set. Simply
602 subtracts value handle ids, since they are created in topo-order. */
605 vh_compare (const void *pa, const void *pb)
607 const tree vha = get_value_handle (*((const tree *)pa));
608 const tree vhb = get_value_handle (*((const tree *)pb));
610 /* This can happen when we constify things. */
611 if (constant_expr_p (vha))
613 if (constant_expr_p (vhb))
617 else if (constant_expr_p (vhb))
619 return VALUE_HANDLE_ID (vha) - VALUE_HANDLE_ID (vhb);
622 /* Generate an topological-ordered array of bitmap set SET. */
624 static VEC(tree, heap) *
625 sorted_array_from_bitmap_set (bitmap_set_t set)
629 VEC(tree, heap) *result = NULL;
631 FOR_EACH_EXPR_ID_IN_SET (set, i, bi)
632 VEC_safe_push (tree, heap, result, expression_for_id (i));
634 qsort (VEC_address (tree, result), VEC_length (tree, result),
635 sizeof (tree), vh_compare);
640 /* Perform bitmapped set operation DEST &= ORIG. */
643 bitmap_set_and (bitmap_set_t dest, bitmap_set_t orig)
650 bitmap temp = BITMAP_ALLOC (&grand_bitmap_obstack);
652 bitmap_and_into (dest->values, orig->values);
654 bitmap_copy (temp, dest->expressions);
655 EXECUTE_IF_SET_IN_BITMAP (temp, 0, i, bi)
657 tree expr = expression_for_id (i);
658 tree val = get_value_handle (expr);
659 if (!bitmap_bit_p (dest->values, VALUE_HANDLE_ID (val)))
660 bitmap_clear_bit (dest->expressions, i);
666 /* Subtract all values and expressions contained in ORIG from DEST. */
669 bitmap_set_subtract (bitmap_set_t dest, bitmap_set_t orig)
671 bitmap_set_t result = bitmap_set_new ();
675 bitmap_and_compl (result->expressions, dest->expressions,
678 FOR_EACH_EXPR_ID_IN_SET (result, i, bi)
680 tree expr = expression_for_id (i);
681 tree val = get_value_handle (expr);
682 bitmap_set_bit (result->values, VALUE_HANDLE_ID (val));
688 /* Subtract all the values in bitmap set B from bitmap set A. */
691 bitmap_set_subtract_values (bitmap_set_t a, bitmap_set_t b)
695 bitmap temp = BITMAP_ALLOC (&grand_bitmap_obstack);
697 bitmap_copy (temp, a->expressions);
698 EXECUTE_IF_SET_IN_BITMAP (temp, 0, i, bi)
700 tree expr = expression_for_id (i);
701 if (bitmap_set_contains_value (b, get_value_handle (expr)))
702 bitmap_remove_from_set (a, expr);
708 /* Return true if bitmapped set SET contains the value VAL. */
711 bitmap_set_contains_value (bitmap_set_t set, tree val)
713 if (constant_expr_p (val))
716 if (!set || bitmap_empty_p (set->expressions))
719 return bitmap_bit_p (set->values, VALUE_HANDLE_ID (val));
723 bitmap_set_contains_expr (bitmap_set_t set, tree expr)
725 return bitmap_bit_p (set->expressions, get_expression_id (expr));
728 /* Replace an instance of value LOOKFOR with expression EXPR in SET. */
731 bitmap_set_replace_value (bitmap_set_t set, tree lookfor, tree expr)
733 bitmap_set_t exprset;
737 if (constant_expr_p (lookfor))
740 if (!bitmap_set_contains_value (set, lookfor))
743 /* The number of expressions having a given value is usually
744 significantly less than the total number of expressions in SET.
745 Thus, rather than check, for each expression in SET, whether it
746 has the value LOOKFOR, we walk the reverse mapping that tells us
747 what expressions have a given value, and see if any of those
748 expressions are in our set. For large testcases, this is about
749 5-10x faster than walking the bitmap. If this is somehow a
750 significant lose for some cases, we can choose which set to walk
751 based on the set size. */
752 exprset = VALUE_HANDLE_EXPR_SET (lookfor);
753 FOR_EACH_EXPR_ID_IN_SET (exprset, i, bi)
755 if (bitmap_bit_p (set->expressions, i))
757 bitmap_clear_bit (set->expressions, i);
758 bitmap_set_bit (set->expressions, get_expression_id (expr));
764 /* Return true if two bitmap sets are equal. */
767 bitmap_set_equal (bitmap_set_t a, bitmap_set_t b)
769 return bitmap_equal_p (a->values, b->values);
772 /* Replace an instance of EXPR's VALUE with EXPR in SET if it exists,
773 and add it otherwise. */
776 bitmap_value_replace_in_set (bitmap_set_t set, tree expr)
778 tree val = get_value_handle (expr);
780 if (bitmap_set_contains_value (set, val))
781 bitmap_set_replace_value (set, val, expr);
783 bitmap_insert_into_set (set, expr);
786 /* Insert EXPR into SET if EXPR's value is not already present in
790 bitmap_value_insert_into_set (bitmap_set_t set, tree expr)
792 tree val = get_value_handle (expr);
794 if (constant_expr_p (val))
797 if (!bitmap_set_contains_value (set, val))
798 bitmap_insert_into_set (set, expr);
801 /* Print out SET to OUTFILE. */
804 print_bitmap_set (FILE *outfile, bitmap_set_t set,
805 const char *setname, int blockindex)
807 fprintf (outfile, "%s[%d] := { ", setname, blockindex);
814 FOR_EACH_EXPR_ID_IN_SET (set, i, bi)
816 tree expr = expression_for_id (i);
819 fprintf (outfile, ", ");
821 print_generic_expr (outfile, expr, 0);
823 fprintf (outfile, " (");
824 print_generic_expr (outfile, get_value_handle (expr), 0);
825 fprintf (outfile, ") ");
828 fprintf (outfile, " }\n");
831 void debug_bitmap_set (bitmap_set_t);
834 debug_bitmap_set (bitmap_set_t set)
836 print_bitmap_set (stderr, set, "debug", 0);
839 /* Print out the expressions that have VAL to OUTFILE. */
842 print_value_expressions (FILE *outfile, tree val)
844 if (VALUE_HANDLE_EXPR_SET (val))
847 sprintf (s, "VH.%04d", VALUE_HANDLE_ID (val));
848 print_bitmap_set (outfile, VALUE_HANDLE_EXPR_SET (val), s, 0);
854 debug_value_expressions (tree val)
856 print_value_expressions (stderr, val);
859 /* Return the folded version of T if T, when folded, is a gimple
860 min_invariant. Otherwise, return T. */
863 fully_constant_expression (tree t)
867 if (folded && is_gimple_min_invariant (folded))
872 /* Make a temporary copy of a CALL_EXPR object NODE. */
875 temp_copy_call_expr (tree node)
877 return (tree) obstack_copy (&temp_call_expr_obstack, node, tree_size (node));
880 /* Translate the vuses in the VUSES vector backwards through phi nodes
881 in PHIBLOCK, so that they have the value they would have in
884 static VEC(tree, gc) *
885 translate_vuses_through_block (VEC (tree, gc) *vuses,
886 basic_block phiblock,
890 VEC(tree, gc) *result = NULL;
893 for (i = 0; VEC_iterate (tree, vuses, i, oldvuse); i++)
895 tree phi = SSA_NAME_DEF_STMT (oldvuse);
896 if (TREE_CODE (phi) == PHI_NODE
897 && bb_for_stmt (phi) == phiblock)
899 edge e = find_edge (block, bb_for_stmt (phi));
902 tree def = PHI_ARG_DEF (phi, e->dest_idx);
906 result = VEC_copy (tree, gc, vuses);
907 VEC_replace (tree, result, i, def);
913 /* We avoid creating a new copy of the vuses unless something
914 actually changed, so result can be NULL. */
924 /* Like find_leader, but checks for the value existing in SET1 *or*
925 SET2. This is used to avoid making a set consisting of the union
926 of PA_IN and ANTIC_IN during insert. */
929 find_leader_in_sets (tree expr, bitmap_set_t set1, bitmap_set_t set2)
933 result = bitmap_find_leader (set1, expr);
935 result = bitmap_find_leader (set2, expr);
939 /* Translate EXPR using phis in PHIBLOCK, so that it has the values of
940 the phis in PRED. Return NULL if we can't find a leader for each
941 part of the translated expression. */
944 phi_translate (tree expr, bitmap_set_t set1, bitmap_set_t set2,
945 basic_block pred, basic_block phiblock)
947 tree phitrans = NULL;
953 if (is_gimple_min_invariant (expr))
956 /* Phi translations of a given expression don't change. */
957 if (EXPR_P (expr) || GIMPLE_STMT_P (expr))
961 vh = get_value_handle (expr);
962 if (vh && TREE_CODE (vh) == VALUE_HANDLE)
963 phitrans = phi_trans_lookup (expr, pred, VALUE_HANDLE_VUSES (vh));
965 phitrans = phi_trans_lookup (expr, pred, NULL);
968 phitrans = phi_trans_lookup (expr, pred, NULL);
973 switch (TREE_CODE_CLASS (TREE_CODE (expr)))
980 if (TREE_CODE (expr) != CALL_EXPR)
984 tree oldfn = CALL_EXPR_FN (expr);
985 tree oldsc = CALL_EXPR_STATIC_CHAIN (expr);
986 tree newfn, newsc = NULL;
987 tree newexpr = NULL_TREE;
988 tree vh = get_value_handle (expr);
989 bool invariantarg = false;
991 VEC (tree, gc) *vuses = VALUE_HANDLE_VUSES (vh);
992 VEC (tree, gc) *tvuses;
994 newfn = phi_translate (find_leader_in_sets (oldfn, set1, set2),
995 set1, set2, pred, phiblock);
1000 newexpr = temp_copy_call_expr (expr);
1001 CALL_EXPR_FN (newexpr) = get_value_handle (newfn);
1005 newsc = phi_translate (find_leader_in_sets (oldsc, set1, set2),
1006 set1, set2, pred, phiblock);
1012 newexpr = temp_copy_call_expr (expr);
1013 CALL_EXPR_STATIC_CHAIN (newexpr) = get_value_handle (newsc);
1017 /* phi translate the argument list piece by piece. */
1018 nargs = call_expr_nargs (expr);
1019 for (i = 0; i < nargs; i++)
1021 tree oldval = CALL_EXPR_ARG (expr, i);
1025 /* This may seem like a weird place for this
1026 check, but it's actually the easiest place to
1027 do it. We can't do it lower on in the
1028 recursion because it's valid for pieces of a
1029 component ref to be of AGGREGATE_TYPE, as long
1030 as the outermost one is not.
1031 To avoid *that* case, we have a check for
1032 AGGREGATE_TYPE_P in insert_aux. However, that
1033 check will *not* catch this case because here
1034 it occurs in the argument list. */
1035 if (AGGREGATE_TYPE_P (TREE_TYPE (oldval)))
1037 oldval = find_leader_in_sets (oldval, set1, set2);
1038 newval = phi_translate (oldval, set1, set2, pred,
1042 if (newval != oldval)
1044 invariantarg |= is_gimple_min_invariant (newval);
1046 newexpr = temp_copy_call_expr (expr);
1047 CALL_EXPR_ARG (newexpr, i) = get_value_handle (newval);
1052 /* In case of new invariant args we might try to fold the call
1054 if (invariantarg && !newsc)
1056 tree tmp1 = build_call_array (TREE_TYPE (expr),
1057 newfn, call_expr_nargs (newexpr),
1058 CALL_EXPR_ARGP (newexpr));
1059 tree tmp2 = fold (tmp1);
1062 STRIP_TYPE_NOPS (tmp2);
1063 if (is_gimple_min_invariant (tmp2))
1068 tvuses = translate_vuses_through_block (vuses, phiblock, pred);
1069 if (vuses != tvuses && ! newexpr)
1070 newexpr = temp_copy_call_expr (expr);
1074 newexpr->base.ann = NULL;
1075 vn_lookup_or_add_with_vuses (newexpr, tvuses);
1078 phi_trans_add (oldexpr, expr, pred, tvuses);
1083 case tcc_declaration:
1085 VEC (tree, gc) * oldvuses = NULL;
1086 VEC (tree, gc) * newvuses = NULL;
1088 oldvuses = VALUE_HANDLE_VUSES (get_value_handle (expr));
1090 newvuses = translate_vuses_through_block (oldvuses, phiblock,
1093 if (oldvuses != newvuses)
1094 vn_lookup_or_add_with_vuses (expr, newvuses);
1096 phi_trans_add (oldexpr, expr, pred, newvuses);
1102 tree oldop0 = TREE_OPERAND (expr, 0);
1111 VEC (tree, gc) * oldvuses = NULL;
1112 VEC (tree, gc) * newvuses = NULL;
1114 if (TREE_CODE (expr) != INDIRECT_REF
1115 && TREE_CODE (expr) != COMPONENT_REF
1116 && TREE_CODE (expr) != ARRAY_REF)
1119 oldop0 = find_leader_in_sets (oldop0, set1, set2);
1120 newop0 = phi_translate (oldop0, set1, set2, pred, phiblock);
1124 if (TREE_CODE (expr) == ARRAY_REF)
1126 oldop1 = TREE_OPERAND (expr, 1);
1127 oldop1 = find_leader_in_sets (oldop1, set1, set2);
1128 newop1 = phi_translate (oldop1, set1, set2, pred, phiblock);
1133 oldop2 = TREE_OPERAND (expr, 2);
1136 oldop2 = find_leader_in_sets (oldop2, set1, set2);
1137 newop2 = phi_translate (oldop2, set1, set2, pred, phiblock);
1142 oldop3 = TREE_OPERAND (expr, 3);
1145 oldop3 = find_leader_in_sets (oldop3, set1, set2);
1146 newop3 = phi_translate (oldop3, set1, set2, pred, phiblock);
1153 oldvuses = VALUE_HANDLE_VUSES (get_value_handle (expr));
1155 newvuses = translate_vuses_through_block (oldvuses, phiblock,
1158 if (newop0 != oldop0 || newvuses != oldvuses
1161 || newop3 != oldop3)
1165 newexpr = (tree) pool_alloc (reference_node_pool);
1166 memcpy (newexpr, expr, tree_size (expr));
1167 TREE_OPERAND (newexpr, 0) = get_value_handle (newop0);
1168 if (TREE_CODE (expr) == ARRAY_REF)
1170 TREE_OPERAND (newexpr, 1) = get_value_handle (newop1);
1172 TREE_OPERAND (newexpr, 2) = get_value_handle (newop2);
1174 TREE_OPERAND (newexpr, 3) = get_value_handle (newop3);
1177 t = fully_constant_expression (newexpr);
1181 pool_free (reference_node_pool, newexpr);
1186 newexpr->base.ann = NULL;
1187 vn_lookup_or_add_with_vuses (newexpr, newvuses);
1191 phi_trans_add (oldexpr, expr, pred, newvuses);
1197 case tcc_comparison:
1199 tree oldop1 = TREE_OPERAND (expr, 0);
1200 tree oldval1 = oldop1;
1201 tree oldop2 = TREE_OPERAND (expr, 1);
1202 tree oldval2 = oldop2;
1207 oldop1 = find_leader_in_sets (oldop1, set1, set2);
1208 newop1 = phi_translate (oldop1, set1, set2, pred, phiblock);
1212 oldop2 = find_leader_in_sets (oldop2, set1, set2);
1213 newop2 = phi_translate (oldop2, set1, set2, pred, phiblock);
1216 if (newop1 != oldop1 || newop2 != oldop2)
1219 newexpr = (tree) pool_alloc (binary_node_pool);
1220 memcpy (newexpr, expr, tree_size (expr));
1221 TREE_OPERAND (newexpr, 0) = newop1 == oldop1 ? oldval1 : get_value_handle (newop1);
1222 TREE_OPERAND (newexpr, 1) = newop2 == oldop2 ? oldval2 : get_value_handle (newop2);
1223 t = fully_constant_expression (newexpr);
1226 pool_free (binary_node_pool, newexpr);
1231 newexpr->base.ann = NULL;
1232 vn_lookup_or_add (newexpr, NULL);
1236 phi_trans_add (oldexpr, expr, pred, NULL);
1242 tree oldop1 = TREE_OPERAND (expr, 0);
1246 oldop1 = find_leader_in_sets (oldop1, set1, set2);
1247 newop1 = phi_translate (oldop1, set1, set2, pred, phiblock);
1250 if (newop1 != oldop1)
1253 newexpr = (tree) pool_alloc (unary_node_pool);
1254 memcpy (newexpr, expr, tree_size (expr));
1255 TREE_OPERAND (newexpr, 0) = get_value_handle (newop1);
1256 t = fully_constant_expression (newexpr);
1259 pool_free (unary_node_pool, newexpr);
1264 newexpr->base.ann = NULL;
1265 vn_lookup_or_add (newexpr, NULL);
1269 phi_trans_add (oldexpr, expr, pred, NULL);
1273 case tcc_exceptional:
1278 gcc_assert (TREE_CODE (expr) == SSA_NAME);
1280 def_stmt = SSA_NAME_DEF_STMT (expr);
1281 if (TREE_CODE (def_stmt) == PHI_NODE
1282 && bb_for_stmt (def_stmt) == phiblock)
1287 e = find_edge (pred, bb_for_stmt (phi));
1290 if (is_undefined_value (PHI_ARG_DEF (phi, e->dest_idx)))
1292 vn_lookup_or_add (PHI_ARG_DEF (phi, e->dest_idx), NULL);
1293 return PHI_ARG_DEF (phi, e->dest_idx);
1303 /* For each expression in SET, translate the value handles through phi nodes
1304 in PHIBLOCK using edge PHIBLOCK->PRED, and store the resulting
1305 expressions in DEST. */
1308 phi_translate_set (bitmap_set_t dest, bitmap_set_t set, basic_block pred,
1309 basic_block phiblock)
1311 VEC (tree, heap) *exprs;
1315 if (!phi_nodes (phiblock))
1317 bitmap_set_copy (dest, set);
1321 exprs = sorted_array_from_bitmap_set (set);
1322 for (i = 0; VEC_iterate (tree, exprs, i, expr); i++)
1325 translated = phi_translate (expr, set, NULL, pred, phiblock);
1327 /* Don't add constants or empty translations to the cache, since
1328 we won't look them up that way, or use the result, anyway. */
1329 if (translated && !is_gimple_min_invariant (translated))
1331 tree vh = get_value_handle (translated);
1332 VEC (tree, gc) *vuses;
1334 /* The value handle itself may also be an invariant, in
1335 which case, it has no vuses. */
1336 vuses = !is_gimple_min_invariant (vh)
1337 ? VALUE_HANDLE_VUSES (vh) : NULL;
1338 phi_trans_add (expr, translated, pred, vuses);
1341 if (translated != NULL)
1342 bitmap_value_insert_into_set (dest, translated);
1344 VEC_free (tree, heap, exprs);
1347 /* Find the leader for a value (i.e., the name representing that
1348 value) in a given set, and return it. Return NULL if no leader is
1352 bitmap_find_leader (bitmap_set_t set, tree val)
1357 if (constant_expr_p (val))
1360 if (bitmap_set_contains_value (set, val))
1362 /* Rather than walk the entire bitmap of expressions, and see
1363 whether any of them has the value we are looking for, we look
1364 at the reverse mapping, which tells us the set of expressions
1365 that have a given value (IE value->expressions with that
1366 value) and see if any of those expressions are in our set.
1367 The number of expressions per value is usually significantly
1368 less than the number of expressions in the set. In fact, for
1369 large testcases, doing it this way is roughly 5-10x faster
1370 than walking the bitmap.
1371 If this is somehow a significant lose for some cases, we can
1372 choose which set to walk based on which set is smaller. */
1375 bitmap_set_t exprset = VALUE_HANDLE_EXPR_SET (val);
1377 EXECUTE_IF_AND_IN_BITMAP (exprset->expressions,
1378 set->expressions, 0, i, bi)
1379 return expression_for_id (i);
1384 /* Determine if VALUE, a memory operation, is ANTIC_IN at the top of
1385 BLOCK by seeing if it is not killed in the block. Note that we are
1386 only determining whether there is a store that kills it. Because
1387 of the order in which clean iterates over values, we are guaranteed
1388 that altered operands will have caused us to be eliminated from the
1389 ANTIC_IN set already. */
1392 value_dies_in_block_x (tree vh, basic_block block)
1396 VEC (tree, gc) *vuses = VALUE_HANDLE_VUSES (vh);
1398 /* Conservatively, a value dies if it's vuses are defined in this
1399 block, unless they come from phi nodes (which are merge operations,
1400 rather than stores. */
1401 for (i = 0; VEC_iterate (tree, vuses, i, vuse); i++)
1403 tree def = SSA_NAME_DEF_STMT (vuse);
1405 if (bb_for_stmt (def) != block)
1407 if (TREE_CODE (def) == PHI_NODE)
1414 /* Determine if the expression EXPR is valid in SET1 U SET2.
1415 ONLY SET2 CAN BE NULL.
1416 This means that we have a leader for each part of the expression
1417 (if it consists of values), or the expression is an SSA_NAME.
1418 For loads/calls, we also see if the vuses are killed in this block.
1420 NB: We never should run into a case where we have SSA_NAME +
1421 SSA_NAME or SSA_NAME + value. The sets valid_in_sets is called on,
1422 the ANTIC sets, will only ever have SSA_NAME's or value expressions
1423 (IE VALUE1 + VALUE2, *VALUE1, VALUE1 < VALUE2) */
1425 #define union_contains_value(SET1, SET2, VAL) \
1426 (bitmap_set_contains_value ((SET1), (VAL)) \
1427 || ((SET2) && bitmap_set_contains_value ((SET2), (VAL))))
1430 valid_in_sets (bitmap_set_t set1, bitmap_set_t set2, tree expr,
1433 tree vh = get_value_handle (expr);
1434 switch (TREE_CODE_CLASS (TREE_CODE (expr)))
1437 case tcc_comparison:
1439 tree op1 = TREE_OPERAND (expr, 0);
1440 tree op2 = TREE_OPERAND (expr, 1);
1442 return union_contains_value (set1, set2, op1)
1443 && union_contains_value (set1, set2, op2);
1448 tree op1 = TREE_OPERAND (expr, 0);
1449 return union_contains_value (set1, set2, op1);
1452 case tcc_expression:
1457 if (TREE_CODE (expr) == CALL_EXPR)
1459 tree fn = CALL_EXPR_FN (expr);
1460 tree sc = CALL_EXPR_STATIC_CHAIN (expr);
1462 call_expr_arg_iterator iter;
1464 /* Check the non-argument operands first. */
1465 if (!union_contains_value (set1, set2, fn)
1466 || (sc && !union_contains_value (set1, set2, sc)))
1469 /* Now check the operands. */
1470 FOR_EACH_CALL_EXPR_ARG (arg, iter, expr)
1472 if (!union_contains_value (set1, set2, arg))
1475 return !value_dies_in_block_x (vh, block);
1482 if (TREE_CODE (expr) == INDIRECT_REF
1483 || TREE_CODE (expr) == COMPONENT_REF
1484 || TREE_CODE (expr) == ARRAY_REF)
1486 tree op0 = TREE_OPERAND (expr, 0);
1487 gcc_assert (is_gimple_min_invariant (op0)
1488 || TREE_CODE (op0) == VALUE_HANDLE);
1489 if (!union_contains_value (set1, set2, op0))
1491 if (TREE_CODE (expr) == ARRAY_REF)
1493 tree op1 = TREE_OPERAND (expr, 1);
1494 tree op2 = TREE_OPERAND (expr, 2);
1495 tree op3 = TREE_OPERAND (expr, 3);
1496 gcc_assert (is_gimple_min_invariant (op1)
1497 || TREE_CODE (op1) == VALUE_HANDLE);
1498 if (!union_contains_value (set1, set2, op1))
1500 gcc_assert (!op2 || is_gimple_min_invariant (op2)
1501 || TREE_CODE (op2) == VALUE_HANDLE);
1503 && !union_contains_value (set1, set2, op2))
1505 gcc_assert (!op3 || is_gimple_min_invariant (op3)
1506 || TREE_CODE (op3) == VALUE_HANDLE);
1508 && !union_contains_value (set1, set2, op3))
1511 return bitmap_set_contains_value (ANTIC_SAFE_LOADS (block),
1513 || !value_dies_in_block_x (vh, block);
1518 case tcc_exceptional:
1520 gcc_assert (TREE_CODE (expr) == SSA_NAME);
1521 return bitmap_set_contains_expr (AVAIL_OUT (block), expr);
1524 case tcc_declaration:
1525 return !value_dies_in_block_x (vh, block);
1528 /* No other cases should be encountered. */
1533 /* Clean the set of expressions that are no longer valid in SET1 or
1534 SET2. This means expressions that are made up of values we have no
1535 leaders for in SET1 or SET2. This version is used for partial
1536 anticipation, which means it is not valid in either ANTIC_IN or
1540 dependent_clean (bitmap_set_t set1, bitmap_set_t set2, basic_block block)
1542 VEC (tree, heap) *exprs = sorted_array_from_bitmap_set (set1);
1546 for (i = 0; VEC_iterate (tree, exprs, i, expr); i++)
1548 if (!valid_in_sets (set1, set2, expr, block))
1549 bitmap_remove_from_set (set1, expr);
1551 VEC_free (tree, heap, exprs);
1554 /* Clean the set of expressions that are no longer valid in SET. This
1555 means expressions that are made up of values we have no leaders for
1559 clean (bitmap_set_t set, basic_block block)
1561 VEC (tree, heap) *exprs = sorted_array_from_bitmap_set (set);
1565 for (i = 0; VEC_iterate (tree, exprs, i, expr); i++)
1567 if (!valid_in_sets (set, NULL, expr, block))
1568 bitmap_remove_from_set (set, expr);
1570 VEC_free (tree, heap, exprs);
1573 static sbitmap has_abnormal_preds;
1575 /* List of blocks that may have changed during ANTIC computation and
1576 thus need to be iterated over. */
1578 static sbitmap changed_blocks;
1580 /* Decide whether to defer a block for a later iteration, or PHI
1581 translate SOURCE to DEST using phis in PHIBLOCK. Return false if we
1582 should defer the block, and true if we processed it. */
1585 defer_or_phi_translate_block (bitmap_set_t dest, bitmap_set_t source,
1586 basic_block block, basic_block phiblock)
1588 if (!BB_VISITED (phiblock))
1590 SET_BIT (changed_blocks, block->index);
1591 BB_VISITED (block) = 0;
1592 BB_DEFERRED (block) = 1;
1596 phi_translate_set (dest, source, block, phiblock);
1600 /* Compute the ANTIC set for BLOCK.
1602 If succs(BLOCK) > 1 then
1603 ANTIC_OUT[BLOCK] = intersection of ANTIC_IN[b] for all succ(BLOCK)
1604 else if succs(BLOCK) == 1 then
1605 ANTIC_OUT[BLOCK] = phi_translate (ANTIC_IN[succ(BLOCK)])
1607 ANTIC_IN[BLOCK] = clean(ANTIC_OUT[BLOCK] U EXP_GEN[BLOCK] - TMP_GEN[BLOCK])
1611 compute_antic_aux (basic_block block, bool block_has_abnormal_pred_edge)
1613 bool changed = false;
1614 bitmap_set_t S, old, ANTIC_OUT;
1620 old = ANTIC_OUT = S = NULL;
1621 BB_VISITED (block) = 1;
1623 /* If any edges from predecessors are abnormal, antic_in is empty,
1625 if (block_has_abnormal_pred_edge)
1626 goto maybe_dump_sets;
1628 old = ANTIC_IN (block);
1629 ANTIC_OUT = bitmap_set_new ();
1631 /* If the block has no successors, ANTIC_OUT is empty. */
1632 if (EDGE_COUNT (block->succs) == 0)
1634 /* If we have one successor, we could have some phi nodes to
1635 translate through. */
1636 else if (single_succ_p (block))
1638 basic_block succ_bb = single_succ (block);
1640 /* We trade iterations of the dataflow equations for having to
1641 phi translate the maximal set, which is incredibly slow
1642 (since the maximal set often has 300+ members, even when you
1643 have a small number of blocks).
1644 Basically, we defer the computation of ANTIC for this block
1645 until we have processed it's successor, which will inevitably
1646 have a *much* smaller set of values to phi translate once
1647 clean has been run on it.
1648 The cost of doing this is that we technically perform more
1649 iterations, however, they are lower cost iterations.
1651 Timings for PRE on tramp3d-v4:
1652 without maximal set fix: 11 seconds
1653 with maximal set fix/without deferring: 26 seconds
1654 with maximal set fix/with deferring: 11 seconds
1657 if (!defer_or_phi_translate_block (ANTIC_OUT, ANTIC_IN (succ_bb),
1661 goto maybe_dump_sets;
1664 /* If we have multiple successors, we take the intersection of all of
1665 them. Note that in the case of loop exit phi nodes, we may have
1666 phis to translate through. */
1669 VEC(basic_block, heap) * worklist;
1671 basic_block bprime, first;
1673 worklist = VEC_alloc (basic_block, heap, EDGE_COUNT (block->succs));
1674 FOR_EACH_EDGE (e, ei, block->succs)
1675 VEC_quick_push (basic_block, worklist, e->dest);
1676 first = VEC_index (basic_block, worklist, 0);
1678 if (phi_nodes (first))
1680 bitmap_set_t from = ANTIC_IN (first);
1682 if (!BB_VISITED (first))
1684 phi_translate_set (ANTIC_OUT, from, block, first);
1688 if (!BB_VISITED (first))
1689 bitmap_set_copy (ANTIC_OUT, maximal_set);
1691 bitmap_set_copy (ANTIC_OUT, ANTIC_IN (first));
1694 for (i = 1; VEC_iterate (basic_block, worklist, i, bprime); i++)
1696 if (phi_nodes (bprime))
1698 bitmap_set_t tmp = bitmap_set_new ();
1699 bitmap_set_t from = ANTIC_IN (bprime);
1701 if (!BB_VISITED (bprime))
1703 phi_translate_set (tmp, from, block, bprime);
1704 bitmap_set_and (ANTIC_OUT, tmp);
1705 bitmap_set_free (tmp);
1709 if (!BB_VISITED (bprime))
1710 bitmap_set_and (ANTIC_OUT, maximal_set);
1712 bitmap_set_and (ANTIC_OUT, ANTIC_IN (bprime));
1715 VEC_free (basic_block, heap, worklist);
1718 /* Generate ANTIC_OUT - TMP_GEN. */
1719 S = bitmap_set_subtract (ANTIC_OUT, TMP_GEN (block));
1721 /* Start ANTIC_IN with EXP_GEN - TMP_GEN. */
1722 ANTIC_IN (block) = bitmap_set_subtract (EXP_GEN (block),
1725 /* Then union in the ANTIC_OUT - TMP_GEN values,
1726 to get ANTIC_OUT U EXP_GEN - TMP_GEN */
1727 FOR_EACH_EXPR_ID_IN_SET (S, bii, bi)
1728 bitmap_value_insert_into_set (ANTIC_IN (block),
1729 expression_for_id (bii));
1731 clean (ANTIC_IN (block), block);
1733 /* !old->expressions can happen when we deferred a block. */
1734 if (!old->expressions || !bitmap_set_equal (old, ANTIC_IN (block)))
1737 SET_BIT (changed_blocks, block->index);
1738 FOR_EACH_EDGE (e, ei, block->preds)
1739 SET_BIT (changed_blocks, e->src->index);
1742 RESET_BIT (changed_blocks, block->index);
1745 if (dump_file && (dump_flags & TDF_DETAILS))
1747 if (!BB_DEFERRED (block) || BB_VISITED (block))
1750 print_bitmap_set (dump_file, ANTIC_OUT, "ANTIC_OUT", block->index);
1752 if (ANTIC_SAFE_LOADS (block))
1753 print_bitmap_set (dump_file, ANTIC_SAFE_LOADS (block),
1754 "ANTIC_SAFE_LOADS", block->index);
1755 print_bitmap_set (dump_file, ANTIC_IN (block), "ANTIC_IN",
1759 print_bitmap_set (dump_file, S, "S", block->index);
1764 "Block %d was deferred for a future iteration.\n",
1769 bitmap_set_free (old);
1771 bitmap_set_free (S);
1773 bitmap_set_free (ANTIC_OUT);
1777 /* Compute PARTIAL_ANTIC for BLOCK.
1779 If succs(BLOCK) > 1 then
1780 PA_OUT[BLOCK] = value wise union of PA_IN[b] + all ANTIC_IN not
1781 in ANTIC_OUT for all succ(BLOCK)
1782 else if succs(BLOCK) == 1 then
1783 PA_OUT[BLOCK] = phi_translate (PA_IN[succ(BLOCK)])
1785 PA_IN[BLOCK] = dependent_clean(PA_OUT[BLOCK] - TMP_GEN[BLOCK]
1790 compute_partial_antic_aux (basic_block block,
1791 bool block_has_abnormal_pred_edge)
1793 bool changed = false;
1794 bitmap_set_t old_PA_IN;
1795 bitmap_set_t PA_OUT;
1799 old_PA_IN = PA_OUT = NULL;
1801 /* If any edges from predecessors are abnormal, antic_in is empty,
1803 if (block_has_abnormal_pred_edge)
1804 goto maybe_dump_sets;
1806 old_PA_IN = PA_IN (block);
1807 PA_OUT = bitmap_set_new ();
1809 /* If the block has no successors, ANTIC_OUT is empty. */
1810 if (EDGE_COUNT (block->succs) == 0)
1812 /* If we have one successor, we could have some phi nodes to
1813 translate through. Note that we can't phi translate across DFS
1814 back edges in partial antic, because it uses a union operation
1815 on the successors. For recurrences like IV's, we will end up generating a
1816 new value in the set on each go around (i + 3 (VH.1) VH.1 + 1
1817 (VH.2), VH.2 + 1 (VH.3), etc), forever. */
1818 else if (single_succ_p (block))
1820 basic_block succ = single_succ (block);
1821 if (!(single_succ_edge (block)->flags & EDGE_DFS_BACK))
1822 phi_translate_set (PA_OUT, PA_IN (succ), block, succ);
1824 /* If we have multiple successors, we take the union of all of
1828 VEC(basic_block, heap) * worklist;
1832 worklist = VEC_alloc (basic_block, heap, EDGE_COUNT (block->succs));
1833 FOR_EACH_EDGE (e, ei, block->succs)
1835 if (e->flags & EDGE_DFS_BACK)
1837 VEC_quick_push (basic_block, worklist, e->dest);
1839 if (VEC_length (basic_block, worklist) > 0)
1841 for (i = 0; VEC_iterate (basic_block, worklist, i, bprime); i++)
1846 FOR_EACH_EXPR_ID_IN_SET (ANTIC_IN (bprime), i, bi)
1847 bitmap_value_insert_into_set (PA_OUT,
1848 expression_for_id (i));
1849 if (phi_nodes (bprime))
1851 bitmap_set_t pa_in = bitmap_set_new ();
1852 phi_translate_set (pa_in, PA_IN (bprime), block, bprime);
1853 FOR_EACH_EXPR_ID_IN_SET (pa_in, i, bi)
1854 bitmap_value_insert_into_set (PA_OUT,
1855 expression_for_id (i));
1856 bitmap_set_free (pa_in);
1859 FOR_EACH_EXPR_ID_IN_SET (PA_IN (bprime), i, bi)
1860 bitmap_value_insert_into_set (PA_OUT,
1861 expression_for_id (i));
1864 VEC_free (basic_block, heap, worklist);
1867 /* PA_IN starts with PA_OUT - TMP_GEN.
1868 Then we subtract things from ANTIC_IN. */
1869 PA_IN (block) = bitmap_set_subtract (PA_OUT, TMP_GEN (block));
1871 /* For partial antic, we want to put back in the phi results, since
1872 we will properly avoid making them partially antic over backedges. */
1873 bitmap_ior_into (PA_IN (block)->values, PHI_GEN (block)->values);
1874 bitmap_ior_into (PA_IN (block)->expressions, PHI_GEN (block)->expressions);
1876 /* PA_IN[block] = PA_IN[block] - ANTIC_IN[block] */
1877 bitmap_set_subtract_values (PA_IN (block), ANTIC_IN (block));
1879 dependent_clean (PA_IN (block), ANTIC_IN (block), block);
1881 if (!bitmap_set_equal (old_PA_IN, PA_IN (block)))
1884 SET_BIT (changed_blocks, block->index);
1885 FOR_EACH_EDGE (e, ei, block->preds)
1886 SET_BIT (changed_blocks, e->src->index);
1889 RESET_BIT (changed_blocks, block->index);
1892 if (dump_file && (dump_flags & TDF_DETAILS))
1895 print_bitmap_set (dump_file, PA_OUT, "PA_OUT", block->index);
1897 print_bitmap_set (dump_file, PA_IN (block), "PA_IN", block->index);
1900 bitmap_set_free (old_PA_IN);
1902 bitmap_set_free (PA_OUT);
1906 /* Compute ANTIC and partial ANTIC sets. */
1909 compute_antic (void)
1911 bool changed = true;
1912 int num_iterations = 0;
1916 /* If any predecessor edges are abnormal, we punt, so antic_in is empty.
1917 We pre-build the map of blocks with incoming abnormal edges here. */
1918 has_abnormal_preds = sbitmap_alloc (last_basic_block);
1919 sbitmap_zero (has_abnormal_preds);
1926 FOR_EACH_EDGE (e, ei, block->preds)
1928 e->flags &= ~EDGE_DFS_BACK;
1929 if (e->flags & EDGE_ABNORMAL)
1931 SET_BIT (has_abnormal_preds, block->index);
1936 BB_VISITED (block) = 0;
1937 BB_DEFERRED (block) = 0;
1938 /* While we are here, give empty ANTIC_IN sets to each block. */
1939 ANTIC_IN (block) = bitmap_set_new ();
1940 PA_IN (block) = bitmap_set_new ();
1943 /* At the exit block we anticipate nothing. */
1944 ANTIC_IN (EXIT_BLOCK_PTR) = bitmap_set_new ();
1945 BB_VISITED (EXIT_BLOCK_PTR) = 1;
1946 PA_IN (EXIT_BLOCK_PTR) = bitmap_set_new ();
1948 changed_blocks = sbitmap_alloc (last_basic_block + 1);
1949 sbitmap_ones (changed_blocks);
1952 if (dump_file && (dump_flags & TDF_DETAILS))
1953 fprintf (dump_file, "Starting iteration %d\n", num_iterations);
1956 for (i = 0; i < last_basic_block - NUM_FIXED_BLOCKS; i++)
1958 if (TEST_BIT (changed_blocks, postorder[i]))
1960 basic_block block = BASIC_BLOCK (postorder[i]);
1961 changed |= compute_antic_aux (block,
1962 TEST_BIT (has_abnormal_preds,
1966 /* Theoretically possible, but *highly* unlikely. */
1967 gcc_assert (num_iterations < 50);
1970 if (dump_file && (dump_flags & TDF_STATS))
1971 fprintf (dump_file, "compute_antic required %d iterations\n",
1974 if (do_partial_partial)
1976 sbitmap_ones (changed_blocks);
1977 mark_dfs_back_edges ();
1982 if (dump_file && (dump_flags & TDF_DETAILS))
1983 fprintf (dump_file, "Starting iteration %d\n", num_iterations);
1986 for (i = 0; i < last_basic_block - NUM_FIXED_BLOCKS; i++)
1988 if (TEST_BIT (changed_blocks, postorder[i]))
1990 basic_block block = BASIC_BLOCK (postorder[i]);
1992 |= compute_partial_antic_aux (block,
1993 TEST_BIT (has_abnormal_preds,
1997 /* Theoretically possible, but *highly* unlikely. */
1998 gcc_assert (num_iterations < 50);
2000 if (dump_file && (dump_flags & TDF_STATS))
2001 fprintf (dump_file, "compute_partial_antic required %d iterations\n",
2004 sbitmap_free (has_abnormal_preds);
2005 sbitmap_free (changed_blocks);
2009 ANTIC_SAFE_LOADS are those loads generated in a block that actually
2010 occur before any kill to their vuses in the block, and thus, are
2011 safe at the top of the block. This function computes the set by
2012 walking the EXP_GEN set for the block, and checking the VUSES.
2014 This set could be computed as ANTIC calculation is proceeding, but
2015 but because it does not actually change during that computation, it is
2016 quicker to pre-calculate the results and use them than to do it on
2017 the fly (particularly in the presence of multiple iteration). */
2020 compute_antic_safe (void)
2028 FOR_EACH_EXPR_ID_IN_SET (EXP_GEN (bb), i, bi)
2030 tree expr = expression_for_id (i);
2031 if (REFERENCE_CLASS_P (expr))
2033 tree vh = get_value_handle (expr);
2034 tree maybe = bitmap_find_leader (AVAIL_OUT (bb), vh);
2042 stmt = SSA_NAME_DEF_STMT (maybe);
2044 FOR_EACH_SSA_TREE_OPERAND (vuse, stmt, i,
2045 SSA_OP_VIRTUAL_USES)
2047 tree def = SSA_NAME_DEF_STMT (vuse);
2049 if (bb_for_stmt (def) != bb)
2052 /* See if the vuse is defined by a statement that
2053 comes before us in the block. Phi nodes are not
2054 stores, so they do not count. */
2055 if (TREE_CODE (def) != PHI_NODE
2056 && stmt_ann (def)->uid < stmt_ann (stmt)->uid)
2064 if (ANTIC_SAFE_LOADS (bb) == NULL)
2065 ANTIC_SAFE_LOADS (bb) = bitmap_set_new ();
2066 bitmap_value_insert_into_set (ANTIC_SAFE_LOADS (bb),
2074 /* Return true if we can value number the call in STMT. This is true
2075 if we have a pure or constant call. */
2078 can_value_number_call (tree stmt)
2080 tree call = get_call_expr_in (stmt);
2082 if (call_expr_flags (call) & (ECF_PURE | ECF_CONST))
2087 /* Return true if OP is a tree which we can perform value numbering
2091 can_value_number_operation (tree op)
2093 return UNARY_CLASS_P (op)
2094 || BINARY_CLASS_P (op)
2095 || COMPARISON_CLASS_P (op)
2096 || REFERENCE_CLASS_P (op)
2097 || (TREE_CODE (op) == CALL_EXPR
2098 && can_value_number_call (op));
2102 /* Return true if OP is a tree which we can perform PRE on
2103 on. This may not match the operations we can value number, but in
2104 a perfect world would. */
2107 can_PRE_operation (tree op)
2109 return UNARY_CLASS_P (op)
2110 || BINARY_CLASS_P (op)
2111 || COMPARISON_CLASS_P (op)
2112 || TREE_CODE (op) == INDIRECT_REF
2113 || TREE_CODE (op) == COMPONENT_REF
2114 || TREE_CODE (op) == CALL_EXPR
2115 || TREE_CODE (op) == ARRAY_REF;
2119 /* Inserted expressions are placed onto this worklist, which is used
2120 for performing quick dead code elimination of insertions we made
2121 that didn't turn out to be necessary. */
2122 static VEC(tree,heap) *inserted_exprs;
2124 /* Pool allocated fake store expressions are placed onto this
2125 worklist, which, after performing dead code elimination, is walked
2126 to see which expressions need to be put into GC'able memory */
2127 static VEC(tree, heap) *need_creation;
2129 /* For COMPONENT_REF's and ARRAY_REF's, we can't have any intermediates for the
2130 COMPONENT_REF or INDIRECT_REF or ARRAY_REF portion, because we'd end up with
2131 trying to rename aggregates into ssa form directly, which is a no
2134 Thus, this routine doesn't create temporaries, it just builds a
2135 single access expression for the array, calling
2136 find_or_generate_expression to build the innermost pieces.
2138 This function is a subroutine of create_expression_by_pieces, and
2139 should not be called on it's own unless you really know what you
2143 create_component_ref_by_pieces (basic_block block, tree expr, tree stmts)
2148 if (TREE_CODE (genop) == VALUE_HANDLE)
2150 tree found = bitmap_find_leader (AVAIL_OUT (block), expr);
2155 if (TREE_CODE (genop) == VALUE_HANDLE)
2157 bitmap_set_t exprset = VALUE_HANDLE_EXPR_SET (expr);
2158 unsigned int firstbit = bitmap_first_set_bit (exprset->expressions);
2159 genop = expression_for_id (firstbit);
2162 switch TREE_CODE (genop)
2168 op0 = create_component_ref_by_pieces (block,
2169 TREE_OPERAND (genop, 0),
2171 op1 = TREE_OPERAND (genop, 1);
2172 if (TREE_CODE (op1) == VALUE_HANDLE)
2173 op1 = find_or_generate_expression (block, op1, stmts);
2174 op2 = TREE_OPERAND (genop, 2);
2175 if (op2 && TREE_CODE (op2) == VALUE_HANDLE)
2176 op2 = find_or_generate_expression (block, op2, stmts);
2177 op3 = TREE_OPERAND (genop, 3);
2178 if (op3 && TREE_CODE (op3) == VALUE_HANDLE)
2179 op3 = find_or_generate_expression (block, op3, stmts);
2180 folded = build4 (ARRAY_REF, TREE_TYPE (genop), op0, op1,
2186 bitmap_set_t exprset;
2187 unsigned int firstbit;
2190 op0 = create_component_ref_by_pieces (block,
2191 TREE_OPERAND (genop, 0),
2193 exprset = VALUE_HANDLE_EXPR_SET (TREE_OPERAND (genop, 1));
2194 firstbit = bitmap_first_set_bit (exprset->expressions);
2195 op1 = expression_for_id (firstbit);
2196 folded = fold_build3 (COMPONENT_REF, TREE_TYPE (genop), op0, op1,
2203 tree op1 = TREE_OPERAND (genop, 0);
2204 tree genop1 = find_or_generate_expression (block, op1, stmts);
2206 folded = fold_build1 (TREE_CODE (genop), TREE_TYPE (genop),
2224 /* Find a leader for an expression, or generate one using
2225 create_expression_by_pieces if it's ANTIC but
2227 BLOCK is the basic_block we are looking for leaders in.
2228 EXPR is the expression to find a leader or generate for.
2229 STMTS is the statement list to put the inserted expressions on.
2230 Returns the SSA_NAME of the LHS of the generated expression or the
2234 find_or_generate_expression (basic_block block, tree expr, tree stmts)
2236 tree genop = bitmap_find_leader (AVAIL_OUT (block), expr);
2238 /* If it's still NULL, it must be a complex expression, so generate
2242 bitmap_set_t exprset = VALUE_HANDLE_EXPR_SET (expr);
2243 unsigned int firstbit = bitmap_first_set_bit (exprset->expressions);
2245 genop = expression_for_id (firstbit);
2246 gcc_assert (can_PRE_operation (genop));
2247 genop = create_expression_by_pieces (block, genop, stmts);
2252 #define NECESSARY(stmt) stmt->base.asm_written_flag
2253 /* Create an expression in pieces, so that we can handle very complex
2254 expressions that may be ANTIC, but not necessary GIMPLE.
2255 BLOCK is the basic block the expression will be inserted into,
2256 EXPR is the expression to insert (in value form)
2257 STMTS is a statement list to append the necessary insertions into.
2259 This function will die if we hit some value that shouldn't be
2260 ANTIC but is (IE there is no leader for it, or its components).
2261 This function may also generate expressions that are themselves
2262 partially or fully redundant. Those that are will be either made
2263 fully redundant during the next iteration of insert (for partially
2264 redundant ones), or eliminated by eliminate (for fully redundant
2268 create_expression_by_pieces (basic_block block, tree expr, tree stmts)
2271 tree folded, forced_stmts, newexpr;
2273 tree_stmt_iterator tsi;
2275 switch (TREE_CODE_CLASS (TREE_CODE (expr)))
2284 gcc_assert (TREE_CODE (expr) == CALL_EXPR);
2286 fn = CALL_EXPR_FN (expr);
2287 sc = CALL_EXPR_STATIC_CHAIN (expr);
2289 genfn = find_or_generate_expression (block, fn, stmts);
2291 nargs = call_expr_nargs (expr);
2292 buffer = (tree*) alloca (nargs * sizeof (tree));
2294 for (i = 0; i < nargs; i++)
2296 tree arg = CALL_EXPR_ARG (expr, i);
2297 buffer[i] = find_or_generate_expression (block, arg, stmts);
2300 folded = build_call_array (TREE_TYPE (expr), genfn, nargs, buffer);
2302 CALL_EXPR_STATIC_CHAIN (folded) =
2303 find_or_generate_expression (block, sc, stmts);
2304 folded = fold (folded);
2310 if (TREE_CODE (expr) == COMPONENT_REF
2311 || TREE_CODE (expr) == ARRAY_REF)
2313 folded = create_component_ref_by_pieces (block, expr, stmts);
2317 tree op1 = TREE_OPERAND (expr, 0);
2318 tree genop1 = find_or_generate_expression (block, op1, stmts);
2320 folded = fold_build1 (TREE_CODE (expr), TREE_TYPE (expr),
2327 case tcc_comparison:
2329 tree op1 = TREE_OPERAND (expr, 0);
2330 tree op2 = TREE_OPERAND (expr, 1);
2331 tree genop1 = find_or_generate_expression (block, op1, stmts);
2332 tree genop2 = find_or_generate_expression (block, op2, stmts);
2333 folded = fold_build2 (TREE_CODE (expr), TREE_TYPE (expr),
2340 tree op1 = TREE_OPERAND (expr, 0);
2341 tree genop1 = find_or_generate_expression (block, op1, stmts);
2342 folded = fold_build1 (TREE_CODE (expr), TREE_TYPE (expr),
2351 /* Force the generated expression to be a sequence of GIMPLE
2353 We have to call unshare_expr because force_gimple_operand may
2354 modify the tree we pass to it. */
2355 newexpr = force_gimple_operand (unshare_expr (folded), &forced_stmts,
2358 /* If we have any intermediate expressions to the value sets, add them
2359 to the value sets and chain them on in the instruction stream. */
2362 tsi = tsi_start (forced_stmts);
2363 for (; !tsi_end_p (tsi); tsi_next (&tsi))
2365 tree stmt = tsi_stmt (tsi);
2366 tree forcedname = GIMPLE_STMT_OPERAND (stmt, 0);
2367 tree forcedexpr = GIMPLE_STMT_OPERAND (stmt, 1);
2368 tree val = vn_lookup_or_add (forcedexpr, NULL);
2370 VEC_safe_push (tree, heap, inserted_exprs, stmt);
2371 vn_add (forcedname, val);
2372 bitmap_value_replace_in_set (NEW_SETS (block), forcedname);
2373 bitmap_value_replace_in_set (AVAIL_OUT (block), forcedname);
2374 mark_symbols_for_renaming (stmt);
2376 tsi = tsi_last (stmts);
2377 tsi_link_after (&tsi, forced_stmts, TSI_CONTINUE_LINKING);
2380 /* Build and insert the assignment of the end result to the temporary
2381 that we will return. */
2382 if (!pretemp || TREE_TYPE (expr) != TREE_TYPE (pretemp))
2384 pretemp = create_tmp_var (TREE_TYPE (expr), "pretmp");
2385 get_var_ann (pretemp);
2389 add_referenced_var (temp);
2391 if (TREE_CODE (TREE_TYPE (expr)) == COMPLEX_TYPE
2392 || TREE_CODE (TREE_TYPE (expr)) == VECTOR_TYPE)
2393 DECL_GIMPLE_REG_P (temp) = 1;
2395 newexpr = build_gimple_modify_stmt (temp, newexpr);
2396 name = make_ssa_name (temp, newexpr);
2397 GIMPLE_STMT_OPERAND (newexpr, 0) = name;
2398 NECESSARY (newexpr) = 0;
2400 tsi = tsi_last (stmts);
2401 tsi_link_after (&tsi, newexpr, TSI_CONTINUE_LINKING);
2402 VEC_safe_push (tree, heap, inserted_exprs, newexpr);
2404 /* All the symbols in NEWEXPR should be put into SSA form. */
2405 mark_symbols_for_renaming (newexpr);
2407 /* Add a value handle to the temporary.
2408 The value may already exist in either NEW_SETS, or AVAIL_OUT, because
2409 we are creating the expression by pieces, and this particular piece of
2410 the expression may have been represented. There is no harm in replacing
2412 v = get_value_handle (expr);
2414 get_or_alloc_expression_id (name);
2415 bitmap_value_replace_in_set (NEW_SETS (block), name);
2416 bitmap_value_replace_in_set (AVAIL_OUT (block), name);
2418 pre_stats.insertions++;
2419 if (dump_file && (dump_flags & TDF_DETAILS))
2421 fprintf (dump_file, "Inserted ");
2422 print_generic_expr (dump_file, newexpr, 0);
2423 fprintf (dump_file, " in predecessor %d\n", block->index);
2429 /* Insert the to-be-made-available values of expression EXPRNUM for each
2430 predecessor, stored in AVAIL, into the predecessors of BLOCK, and
2431 merge the result with a phi node, given the same value handle as
2432 NODE. Return true if we have inserted new stuff. */
2435 insert_into_preds_of_block (basic_block block, unsigned int exprnum,
2438 tree expr = expression_for_id (exprnum);
2439 tree val = get_value_handle (expr);
2441 bool insertions = false;
2446 tree type = TREE_TYPE (avail[EDGE_PRED (block, 0)->src->index]);
2449 if (dump_file && (dump_flags & TDF_DETAILS))
2451 fprintf (dump_file, "Found partial redundancy for expression ");
2452 print_generic_expr (dump_file, expr, 0);
2453 fprintf (dump_file, " (");
2454 print_generic_expr (dump_file, val, 0);
2455 fprintf (dump_file, ")");
2456 fprintf (dump_file, "\n");
2459 /* Make sure we aren't creating an induction variable. */
2460 if (block->loop_depth > 0 && EDGE_COUNT (block->preds) == 2
2461 && TREE_CODE_CLASS (TREE_CODE (expr)) != tcc_reference )
2463 bool firstinsideloop = false;
2464 bool secondinsideloop = false;
2465 firstinsideloop = flow_bb_inside_loop_p (block->loop_father,
2466 EDGE_PRED (block, 0)->src);
2467 secondinsideloop = flow_bb_inside_loop_p (block->loop_father,
2468 EDGE_PRED (block, 1)->src);
2469 /* Induction variables only have one edge inside the loop. */
2470 if (firstinsideloop ^ secondinsideloop)
2472 if (dump_file && (dump_flags & TDF_DETAILS))
2473 fprintf (dump_file, "Skipping insertion of phi for partial redundancy: Looks like an induction variable\n");
2479 /* Make the necessary insertions. */
2480 FOR_EACH_EDGE (pred, ei, block->preds)
2482 tree stmts = alloc_stmt_list ();
2485 eprime = avail[bprime->index];
2487 if (can_PRE_operation (eprime))
2489 builtexpr = create_expression_by_pieces (bprime,
2492 gcc_assert (!(pred->flags & EDGE_ABNORMAL));
2493 bsi_insert_on_edge (pred, stmts);
2494 avail[bprime->index] = builtexpr;
2498 /* If we didn't want a phi node, and we made insertions, we still have
2499 inserted new stuff, and thus return true. If we didn't want a phi node,
2500 and didn't make insertions, we haven't added anything new, so return
2502 if (nophi && insertions)
2504 else if (nophi && !insertions)
2507 /* Now build a phi for the new variable. */
2508 if (!prephitemp || TREE_TYPE (prephitemp) != type)
2510 prephitemp = create_tmp_var (type, "prephitmp");
2511 get_var_ann (prephitemp);
2515 add_referenced_var (temp);
2518 if (TREE_CODE (type) == COMPLEX_TYPE
2519 || TREE_CODE (type) == VECTOR_TYPE)
2520 DECL_GIMPLE_REG_P (temp) = 1;
2521 temp = create_phi_node (temp, block);
2523 NECESSARY (temp) = 0;
2524 VEC_safe_push (tree, heap, inserted_exprs, temp);
2525 FOR_EACH_EDGE (pred, ei, block->preds)
2526 add_phi_arg (temp, avail[pred->src->index], pred);
2528 vn_add (PHI_RESULT (temp), val);
2530 /* The value should *not* exist in PHI_GEN, or else we wouldn't be doing
2531 this insertion, since we test for the existence of this value in PHI_GEN
2532 before proceeding with the partial redundancy checks in insert_aux.
2534 The value may exist in AVAIL_OUT, in particular, it could be represented
2535 by the expression we are trying to eliminate, in which case we want the
2536 replacement to occur. If it's not existing in AVAIL_OUT, we want it
2539 Similarly, to the PHI_GEN case, the value should not exist in NEW_SETS of
2540 this block, because if it did, it would have existed in our dominator's
2541 AVAIL_OUT, and would have been skipped due to the full redundancy check.
2544 bitmap_insert_into_set (PHI_GEN (block),
2546 bitmap_value_replace_in_set (AVAIL_OUT (block),
2548 bitmap_insert_into_set (NEW_SETS (block),
2551 if (dump_file && (dump_flags & TDF_DETAILS))
2553 fprintf (dump_file, "Created phi ");
2554 print_generic_expr (dump_file, temp, 0);
2555 fprintf (dump_file, " in block %d\n", block->index);
2563 /* Perform insertion of partially redundant values.
2564 For BLOCK, do the following:
2565 1. Propagate the NEW_SETS of the dominator into the current block.
2566 If the block has multiple predecessors,
2567 2a. Iterate over the ANTIC expressions for the block to see if
2568 any of them are partially redundant.
2569 2b. If so, insert them into the necessary predecessors to make
2570 the expression fully redundant.
2571 2c. Insert a new PHI merging the values of the predecessors.
2572 2d. Insert the new PHI, and the new expressions, into the
2574 3. Recursively call ourselves on the dominator children of BLOCK.
2576 Steps 1, 2a, and 3 are done by insert_aux. 2b, 2c and 2d are done by
2577 do_regular_insertion and do_partial_insertion.
2582 do_regular_insertion (basic_block block, basic_block dom)
2584 bool new_stuff = false;
2585 VEC (tree, heap) *exprs = sorted_array_from_bitmap_set (ANTIC_IN (block));
2589 for (i = 0; VEC_iterate (tree, exprs, i, expr); i++)
2591 if (can_PRE_operation (expr) && !AGGREGATE_TYPE_P (TREE_TYPE (expr)))
2595 bool by_some = false;
2596 bool cant_insert = false;
2597 bool all_same = true;
2598 tree first_s = NULL;
2601 tree eprime = NULL_TREE;
2604 val = get_value_handle (expr);
2605 if (bitmap_set_contains_value (PHI_GEN (block), val))
2607 if (bitmap_set_contains_value (AVAIL_OUT (dom), val))
2609 if (dump_file && (dump_flags & TDF_DETAILS))
2610 fprintf (dump_file, "Found fully redundant value\n");
2614 avail = XCNEWVEC (tree, last_basic_block);
2615 FOR_EACH_EDGE (pred, ei, block->preds)
2620 /* This can happen in the very weird case
2621 that our fake infinite loop edges have caused a
2622 critical edge to appear. */
2623 if (EDGE_CRITICAL_P (pred))
2629 eprime = phi_translate (expr, ANTIC_IN (block), NULL,
2632 /* eprime will generally only be NULL if the
2633 value of the expression, translated
2634 through the PHI for this predecessor, is
2635 undefined. If that is the case, we can't
2636 make the expression fully redundant,
2637 because its value is undefined along a
2638 predecessor path. We can thus break out
2639 early because it doesn't matter what the
2640 rest of the results are. */
2647 eprime = fully_constant_expression (eprime);
2648 vprime = get_value_handle (eprime);
2649 gcc_assert (vprime);
2650 edoubleprime = bitmap_find_leader (AVAIL_OUT (bprime),
2652 if (edoubleprime == NULL)
2654 avail[bprime->index] = eprime;
2659 avail[bprime->index] = edoubleprime;
2661 if (first_s == NULL)
2662 first_s = edoubleprime;
2663 else if (!operand_equal_p (first_s, edoubleprime,
2668 /* If we can insert it, it's not the same value
2669 already existing along every predecessor, and
2670 it's defined by some predecessor, it is
2671 partially redundant. */
2672 if (!cant_insert && !all_same && by_some)
2674 if (insert_into_preds_of_block (block, get_expression_id (expr),
2678 /* If all edges produce the same value and that value is
2679 an invariant, then the PHI has the same value on all
2680 edges. Note this. */
2681 else if (!cant_insert && all_same && eprime
2682 && is_gimple_min_invariant (eprime)
2683 && !is_gimple_min_invariant (val))
2688 bitmap_set_t exprset = VALUE_HANDLE_EXPR_SET (val);
2689 FOR_EACH_EXPR_ID_IN_SET (exprset, j, bi)
2691 tree expr = expression_for_id (j);
2692 if (TREE_CODE (expr) == SSA_NAME)
2694 vn_add (expr, eprime);
2695 pre_stats.constified++;
2703 VEC_free (tree, heap, exprs);
2708 /* Perform insertion for partially anticipatable expressions. There
2709 is only one case we will perform insertion for these. This case is
2710 if the expression is partially anticipatable, and fully available.
2711 In this case, we know that putting it earlier will enable us to
2712 remove the later computation. */
2716 do_partial_partial_insertion (basic_block block, basic_block dom)
2718 bool new_stuff = false;
2719 VEC (tree, heap) *exprs = sorted_array_from_bitmap_set (PA_IN (block));
2723 for (i = 0; VEC_iterate (tree, exprs, i, expr); i++)
2725 if (can_PRE_operation (expr) && !AGGREGATE_TYPE_P (TREE_TYPE (expr)))
2730 bool cant_insert = false;
2733 tree eprime = NULL_TREE;
2736 val = get_value_handle (expr);
2737 if (bitmap_set_contains_value (PHI_GEN (block), val))
2739 if (bitmap_set_contains_value (AVAIL_OUT (dom), val))
2742 avail = XCNEWVEC (tree, last_basic_block);
2743 FOR_EACH_EDGE (pred, ei, block->preds)
2748 /* This can happen in the very weird case
2749 that our fake infinite loop edges have caused a
2750 critical edge to appear. */
2751 if (EDGE_CRITICAL_P (pred))
2757 eprime = phi_translate (expr, ANTIC_IN (block),
2761 /* eprime will generally only be NULL if the
2762 value of the expression, translated
2763 through the PHI for this predecessor, is
2764 undefined. If that is the case, we can't
2765 make the expression fully redundant,
2766 because its value is undefined along a
2767 predecessor path. We can thus break out
2768 early because it doesn't matter what the
2769 rest of the results are. */
2776 eprime = fully_constant_expression (eprime);
2777 vprime = get_value_handle (eprime);
2778 gcc_assert (vprime);
2779 edoubleprime = bitmap_find_leader (AVAIL_OUT (bprime),
2781 if (edoubleprime == NULL)
2787 avail[bprime->index] = edoubleprime;
2791 /* If we can insert it, it's not the same value
2792 already existing along every predecessor, and
2793 it's defined by some predecessor, it is
2794 partially redundant. */
2795 if (!cant_insert && by_all)
2797 pre_stats.pa_insert++;
2798 if (insert_into_preds_of_block (block, get_expression_id (expr),
2806 VEC_free (tree, heap, exprs);
2811 insert_aux (basic_block block)
2814 bool new_stuff = false;
2819 dom = get_immediate_dominator (CDI_DOMINATORS, block);
2824 bitmap_set_t newset = NEW_SETS (dom);
2827 /* Note that we need to value_replace both NEW_SETS, and
2828 AVAIL_OUT. For both the case of NEW_SETS, the value may be
2829 represented by some non-simple expression here that we want
2830 to replace it with. */
2831 FOR_EACH_EXPR_ID_IN_SET (newset, i, bi)
2833 tree expr = expression_for_id (i);
2834 bitmap_value_replace_in_set (NEW_SETS (block), expr);
2835 bitmap_value_replace_in_set (AVAIL_OUT (block), expr);
2838 if (!single_pred_p (block))
2840 new_stuff |= do_regular_insertion (block, dom);
2841 if (do_partial_partial)
2842 new_stuff |= do_partial_partial_insertion (block, dom);
2846 for (son = first_dom_son (CDI_DOMINATORS, block);
2848 son = next_dom_son (CDI_DOMINATORS, son))
2850 new_stuff |= insert_aux (son);
2856 /* Perform insertion of partially redundant values. */
2861 bool new_stuff = true;
2863 int num_iterations = 0;
2866 NEW_SETS (bb) = bitmap_set_new ();
2872 new_stuff = insert_aux (ENTRY_BLOCK_PTR);
2874 if (num_iterations > 2 && dump_file && (dump_flags & TDF_STATS))
2875 fprintf (dump_file, "insert required %d iterations\n", num_iterations);
2879 /* Return true if VAR is an SSA variable with no defining statement in
2880 this procedure, *AND* isn't a live-on-entry parameter. */
2883 is_undefined_value (tree expr)
2885 return (TREE_CODE (expr) == SSA_NAME
2886 && IS_EMPTY_STMT (SSA_NAME_DEF_STMT (expr))
2887 /* PARM_DECLs and hard registers are always defined. */
2888 && TREE_CODE (SSA_NAME_VAR (expr)) != PARM_DECL);
2892 /* Given an SSA variable VAR and an expression EXPR, compute the value
2893 number for EXPR and create a value handle (VAL) for it. If VAR and
2894 EXPR are not the same, associate VAL with VAR. Finally, add VAR to
2895 S1 and its value handle to S2, and to the maximal set if
2896 ADD_TO_MAXIMAL is true.
2898 VUSES represent the virtual use operands associated with EXPR (if
2902 add_to_sets (tree var, tree expr, tree stmt, bitmap_set_t s1,
2905 tree val = vn_lookup_or_add (expr, stmt);
2907 /* VAR and EXPR may be the same when processing statements for which
2908 we are not computing value numbers (e.g., non-assignments, or
2909 statements that make aliased stores). In those cases, we are
2910 only interested in making VAR available as its own value. */
2915 bitmap_insert_into_set (s1, var);
2917 /* PHI nodes can't go in the maximal sets because they are not in
2918 TMP_GEN, so it is possible to get into non-monotonic situations
2919 during ANTIC calculation, because it will *add* bits. */
2920 if (!in_fre && TREE_CODE (SSA_NAME_DEF_STMT (var)) != PHI_NODE)
2921 bitmap_value_insert_into_set (maximal_set, var);
2922 bitmap_value_insert_into_set (s2, var);
2925 /* Find existing value expression that is the same as T,
2926 and return it if it exists. */
2929 find_existing_value_expr (tree t, tree stmt)
2934 bitmap_set_t exprset;
2936 if (REFERENCE_CLASS_P (t))
2937 vh = vn_lookup (t, stmt);
2939 vh = vn_lookup (t, NULL);
2943 exprset = VALUE_HANDLE_EXPR_SET (vh);
2944 FOR_EACH_EXPR_ID_IN_SET (exprset, bii, bi)
2946 tree efi = expression_for_id (bii);
2947 if (expressions_equal_p (t, efi))
2953 /* Given a unary or binary expression EXPR, create and return a new
2954 expression with the same structure as EXPR but with its operands
2955 replaced with the value handles of each of the operands of EXPR.
2957 VUSES represent the virtual use operands associated with EXPR (if
2958 any). Insert EXPR's operands into the EXP_GEN set for BLOCK. */
2961 create_value_expr_from (tree expr, basic_block block, tree stmt)
2964 enum tree_code code = TREE_CODE (expr);
2966 alloc_pool pool = NULL;
2969 gcc_assert (TREE_CODE_CLASS (code) == tcc_unary
2970 || TREE_CODE_CLASS (code) == tcc_binary
2971 || TREE_CODE_CLASS (code) == tcc_comparison
2972 || TREE_CODE_CLASS (code) == tcc_reference
2973 || TREE_CODE_CLASS (code) == tcc_expression
2974 || TREE_CODE_CLASS (code) == tcc_vl_exp
2975 || TREE_CODE_CLASS (code) == tcc_exceptional
2976 || TREE_CODE_CLASS (code) == tcc_declaration);
2978 if (TREE_CODE_CLASS (code) == tcc_unary)
2979 pool = unary_node_pool;
2980 else if (TREE_CODE_CLASS (code) == tcc_reference)
2981 pool = reference_node_pool;
2982 else if (TREE_CODE_CLASS (code) == tcc_binary)
2983 pool = binary_node_pool;
2984 else if (TREE_CODE_CLASS (code) == tcc_comparison)
2985 pool = comparison_node_pool;
2987 gcc_assert (code == CALL_EXPR);
2989 if (code == CALL_EXPR)
2990 vexpr = temp_copy_call_expr (expr);
2993 vexpr = (tree) pool_alloc (pool);
2994 memcpy (vexpr, expr, tree_size (expr));
2997 for (i = 0; i < TREE_OPERAND_LENGTH (expr); i++)
3001 op = TREE_OPERAND (expr, i);
3002 if (op == NULL_TREE)
3005 /* Recursively value-numberize reference ops and tree lists. */
3006 if (REFERENCE_CLASS_P (op))
3008 tree tempop = create_value_expr_from (op, block, stmt);
3009 op = tempop ? tempop : op;
3010 val = vn_lookup_or_add (op, stmt);
3013 /* Create a value handle for OP and add it to VEXPR. */
3014 val = vn_lookup_or_add (op, NULL);
3016 if (!is_undefined_value (op) && TREE_CODE (op) != TREE_LIST)
3017 bitmap_value_insert_into_set (EXP_GEN (block), op);
3019 if (TREE_CODE (val) == VALUE_HANDLE)
3020 TREE_TYPE (val) = TREE_TYPE (TREE_OPERAND (vexpr, i));
3022 TREE_OPERAND (vexpr, i) = val;
3024 efi = find_existing_value_expr (vexpr, stmt);
3027 get_or_alloc_expression_id (vexpr);
3031 /* Given a statement STMT and its right hand side which is a load, try
3032 to look for the expression stored in the location for the load, and
3033 return true if a useful equivalence was recorded for LHS. */
3036 try_look_through_load (tree lhs, tree mem_ref, tree stmt, basic_block block)
3038 tree store_stmt = NULL;
3043 FOR_EACH_SSA_TREE_OPERAND (vuse, stmt, i, SSA_OP_VIRTUAL_USES)
3047 gcc_assert (TREE_CODE (vuse) == SSA_NAME);
3048 def_stmt = SSA_NAME_DEF_STMT (vuse);
3050 /* If there is no useful statement for this VUSE, we'll not find a
3051 useful expression to return either. Likewise, if there is a
3052 statement but it is not a simple assignment or it has virtual
3053 uses, we can stop right here. Note that this means we do
3054 not look through PHI nodes, which is intentional. */
3056 || TREE_CODE (def_stmt) != GIMPLE_MODIFY_STMT
3057 || !ZERO_SSA_OPERANDS (def_stmt, SSA_OP_VIRTUAL_USES))
3060 /* If this is not the same statement as one we have looked at for
3061 another VUSE of STMT already, we have two statements producing
3062 something that reaches our STMT. */
3063 if (store_stmt && store_stmt != def_stmt)
3067 /* Is this a store to the exact same location as the one we are
3068 loading from in STMT? */
3069 if (!operand_equal_p (GIMPLE_STMT_OPERAND (def_stmt, 0), mem_ref, 0))
3072 /* Otherwise remember this statement and see if all other VUSEs
3073 come from the same statement. */
3074 store_stmt = def_stmt;
3078 /* Alright then, we have visited all VUSEs of STMT and we've determined
3079 that all of them come from the same statement STORE_STMT. See if there
3080 is a useful expression we can deduce from STORE_STMT. */
3081 rhs = GIMPLE_STMT_OPERAND (store_stmt, 1);
3082 if ((TREE_CODE (rhs) == SSA_NAME
3083 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs))
3084 || is_gimple_min_invariant (rhs)
3085 || TREE_CODE (rhs) == ADDR_EXPR
3086 || TREE_INVARIANT (rhs))
3089 /* Yay! Compute a value number for the RHS of the statement and
3090 add its value to the AVAIL_OUT set for the block. Add the LHS
3092 add_to_sets (lhs, rhs, store_stmt, TMP_GEN (block), AVAIL_OUT (block));
3093 if (TREE_CODE (rhs) == SSA_NAME
3094 && !is_undefined_value (rhs))
3095 bitmap_value_insert_into_set (EXP_GEN (block), rhs);
3102 /* Return a copy of NODE that is stored in the temporary alloc_pool's.
3103 This is made recursively true, so that the operands are stored in
3104 the pool as well. */
3107 poolify_tree (tree node)
3109 switch (TREE_CODE (node))
3113 tree temp = (tree) pool_alloc (reference_node_pool);
3114 memcpy (temp, node, tree_size (node));
3115 TREE_OPERAND (temp, 0) = poolify_tree (TREE_OPERAND (temp, 0));
3119 case GIMPLE_MODIFY_STMT:
3121 tree temp = (tree) pool_alloc (modify_expr_node_pool);
3122 memcpy (temp, node, tree_size (node));
3123 GIMPLE_STMT_OPERAND (temp, 0) =
3124 poolify_tree (GIMPLE_STMT_OPERAND (temp, 0));
3125 GIMPLE_STMT_OPERAND (temp, 1) =
3126 poolify_tree (GIMPLE_STMT_OPERAND (temp, 1));
3143 static tree modify_expr_template;
3145 /* Allocate a GIMPLE_MODIFY_STMT with TYPE, and operands OP1, OP2 in the
3146 alloc pools and return it. */
3148 poolify_modify_stmt (tree op1, tree op2)
3150 if (modify_expr_template == NULL)
3151 modify_expr_template = build_gimple_modify_stmt (op1, op2);
3153 GIMPLE_STMT_OPERAND (modify_expr_template, 0) = op1;
3154 GIMPLE_STMT_OPERAND (modify_expr_template, 1) = op2;
3156 return poolify_tree (modify_expr_template);
3160 /* For each real store operation of the form
3161 *a = <value> that we see, create a corresponding fake store of the
3162 form storetmp_<version> = *a.
3164 This enables AVAIL computation to mark the results of stores as
3165 available. Without this, you'd need to do some computation to
3166 mark the result of stores as ANTIC and AVAIL at all the right
3168 To save memory, we keep the store
3169 statements pool allocated until we decide whether they are
3170 necessary or not. */
3173 insert_fake_stores (void)
3179 block_stmt_iterator bsi;
3180 for (bsi = bsi_start (block); !bsi_end_p (bsi); bsi_next (&bsi))
3182 tree stmt = bsi_stmt (bsi);
3184 /* We can't generate SSA names for stores that are complex
3185 or aggregate. We also want to ignore things whose
3186 virtual uses occur in abnormal phis. */
3188 if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT
3189 && TREE_CODE (GIMPLE_STMT_OPERAND (stmt, 0)) == INDIRECT_REF
3190 && !AGGREGATE_TYPE_P (TREE_TYPE (GIMPLE_STMT_OPERAND (stmt, 0)))
3191 && TREE_CODE (TREE_TYPE (GIMPLE_STMT_OPERAND
3192 (stmt, 0))) != COMPLEX_TYPE)
3196 tree lhs = GIMPLE_STMT_OPERAND (stmt, 0);
3197 tree rhs = GIMPLE_STMT_OPERAND (stmt, 1);
3199 bool notokay = false;
3201 FOR_EACH_SSA_DEF_OPERAND (defp, stmt, iter, SSA_OP_VIRTUAL_DEFS)
3203 tree defvar = DEF_FROM_PTR (defp);
3204 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (defvar))
3214 if (!storetemp || TREE_TYPE (rhs) != TREE_TYPE (storetemp))
3216 storetemp = create_tmp_var (TREE_TYPE (rhs), "storetmp");
3217 if (TREE_CODE (TREE_TYPE (storetemp)) == VECTOR_TYPE)
3218 DECL_GIMPLE_REG_P (storetemp) = 1;
3219 get_var_ann (storetemp);
3222 new_tree = poolify_modify_stmt (storetemp, lhs);
3224 lhs = make_ssa_name (storetemp, new_tree);
3225 GIMPLE_STMT_OPERAND (new_tree, 0) = lhs;
3226 create_ssa_artificial_load_stmt (new_tree, stmt);
3228 NECESSARY (new_tree) = 0;
3229 VEC_safe_push (tree, heap, inserted_exprs, new_tree);
3230 VEC_safe_push (tree, heap, need_creation, new_tree);
3231 bsi_insert_after (&bsi, new_tree, BSI_NEW_STMT);
3237 /* Turn the pool allocated fake stores that we created back into real
3238 GC allocated ones if they turned out to be necessary to PRE some
3242 realify_fake_stores (void)
3247 for (i = 0; VEC_iterate (tree, need_creation, i, stmt); i++)
3249 if (NECESSARY (stmt))
3251 block_stmt_iterator bsi;
3254 /* Mark the temp variable as referenced */
3255 add_referenced_var (SSA_NAME_VAR (GIMPLE_STMT_OPERAND (stmt, 0)));
3257 /* Put the new statement in GC memory, fix up the
3258 SSA_NAME_DEF_STMT on it, and then put it in place of
3259 the old statement before the store in the IR stream
3260 as a plain ssa name copy. */
3261 bsi = bsi_for_stmt (stmt);
3263 tmp = GIMPLE_STMT_OPERAND (bsi_stmt (bsi), 1);
3264 newstmt = build_gimple_modify_stmt (GIMPLE_STMT_OPERAND (stmt, 0),
3266 SSA_NAME_DEF_STMT (GIMPLE_STMT_OPERAND (newstmt, 0)) = newstmt;
3267 bsi_insert_before (&bsi, newstmt, BSI_SAME_STMT);
3268 bsi = bsi_for_stmt (stmt);
3269 bsi_remove (&bsi, true);
3272 release_defs (stmt);
3276 /* Tree-combine a value number expression *EXPR_P that does a type
3277 conversion with the value number expression of its operand.
3278 Returns true, if *EXPR_P simplifies to a value number or
3279 gimple min-invariant expression different from EXPR_P and
3280 sets *EXPR_P to the simplified expression value number.
3281 Otherwise returns false and does not change *EXPR_P. */
3284 try_combine_conversion (tree *expr_p)
3286 tree expr = *expr_p;
3288 bitmap_set_t exprset;
3289 unsigned int firstbit;
3291 if (!((TREE_CODE (expr) == NOP_EXPR
3292 || TREE_CODE (expr) == CONVERT_EXPR
3293 || TREE_CODE (expr) == REALPART_EXPR
3294 || TREE_CODE (expr) == IMAGPART_EXPR)
3295 && TREE_CODE (TREE_OPERAND (expr, 0)) == VALUE_HANDLE
3296 && !VALUE_HANDLE_VUSES (TREE_OPERAND (expr, 0))))
3299 exprset = VALUE_HANDLE_EXPR_SET (TREE_OPERAND (expr, 0));
3300 firstbit = bitmap_first_set_bit (exprset->expressions);
3301 t = fold_unary (TREE_CODE (expr), TREE_TYPE (expr),
3302 expression_for_id (firstbit));
3306 /* Strip useless type conversions, which is safe in the optimizers but
3307 not generally in fold. */
3308 STRIP_USELESS_TYPE_CONVERSION (t);
3310 /* Disallow value expressions we have no value number for already, as
3311 we would miss a leader for it here. */
3312 if (!(TREE_CODE (t) == VALUE_HANDLE
3313 || is_gimple_min_invariant (t)))
3314 t = vn_lookup (t, NULL);
3324 /* Compute the AVAIL set for all basic blocks.
3326 This function performs value numbering of the statements in each basic
3327 block. The AVAIL sets are built from information we glean while doing
3328 this value numbering, since the AVAIL sets contain only one entry per
3331 AVAIL_IN[BLOCK] = AVAIL_OUT[dom(BLOCK)].
3332 AVAIL_OUT[BLOCK] = AVAIL_IN[BLOCK] U PHI_GEN[BLOCK] U TMP_GEN[BLOCK]. */
3335 compute_avail (void)
3337 basic_block block, son;
3338 basic_block *worklist;
3341 /* For arguments with default definitions, we pretend they are
3342 defined in the entry block. */
3343 for (param = DECL_ARGUMENTS (current_function_decl);
3345 param = TREE_CHAIN (param))
3347 if (gimple_default_def (cfun, param) != NULL)
3349 tree def = gimple_default_def (cfun, param);
3351 vn_lookup_or_add (def, NULL);
3352 bitmap_insert_into_set (TMP_GEN (ENTRY_BLOCK_PTR), def);
3354 bitmap_value_insert_into_set (maximal_set, def);
3355 bitmap_value_insert_into_set (AVAIL_OUT (ENTRY_BLOCK_PTR), def);
3359 /* Likewise for the static chain decl. */
3360 if (cfun->static_chain_decl)
3362 param = cfun->static_chain_decl;
3363 if (gimple_default_def (cfun, param) != NULL)
3365 tree def = gimple_default_def (cfun, param);
3367 vn_lookup_or_add (def, NULL);
3368 bitmap_insert_into_set (TMP_GEN (ENTRY_BLOCK_PTR), def);
3370 bitmap_value_insert_into_set (maximal_set, def);
3371 bitmap_value_insert_into_set (AVAIL_OUT (ENTRY_BLOCK_PTR), def);
3375 /* Allocate the worklist. */
3376 worklist = XNEWVEC (basic_block, n_basic_blocks);
3378 /* Seed the algorithm by putting the dominator children of the entry
3379 block on the worklist. */
3380 for (son = first_dom_son (CDI_DOMINATORS, ENTRY_BLOCK_PTR);
3382 son = next_dom_son (CDI_DOMINATORS, son))
3383 worklist[sp++] = son;
3385 /* Loop until the worklist is empty. */
3388 block_stmt_iterator bsi;
3391 unsigned int stmt_uid = 1;
3393 /* Pick a block from the worklist. */
3394 block = worklist[--sp];
3396 /* Initially, the set of available values in BLOCK is that of
3397 its immediate dominator. */
3398 dom = get_immediate_dominator (CDI_DOMINATORS, block);
3400 bitmap_set_copy (AVAIL_OUT (block), AVAIL_OUT (dom));
3402 /* Generate values for PHI nodes. */
3403 for (phi = phi_nodes (block); phi; phi = PHI_CHAIN (phi))
3405 /* We have no need for virtual phis, as they don't represent
3406 actual computations. */
3407 if (is_gimple_reg (PHI_RESULT (phi)))
3409 add_to_sets (PHI_RESULT (phi), PHI_RESULT (phi), NULL,
3410 PHI_GEN (block), AVAIL_OUT (block));
3414 /* Now compute value numbers and populate value sets with all
3415 the expressions computed in BLOCK. */
3416 for (bsi = bsi_start (block); !bsi_end_p (bsi); bsi_next (&bsi))
3422 stmt = bsi_stmt (bsi);
3423 ann = stmt_ann (stmt);
3425 ann->uid = stmt_uid++;
3427 /* For regular value numbering, we are only interested in
3428 assignments of the form X_i = EXPR, where EXPR represents
3429 an "interesting" computation, it has no volatile operands
3430 and X_i doesn't flow through an abnormal edge. */
3431 if (TREE_CODE (stmt) == RETURN_EXPR
3432 && !ann->has_volatile_ops)
3434 tree realstmt = stmt;
3438 stmt = TREE_OPERAND (stmt, 0);
3439 if (stmt && TREE_CODE (stmt) == GIMPLE_MODIFY_STMT)
3441 lhs = GIMPLE_STMT_OPERAND (stmt, 0);
3442 rhs = GIMPLE_STMT_OPERAND (stmt, 1);
3443 if (TREE_CODE (rhs) == SSA_NAME
3444 && !is_undefined_value (rhs))
3445 bitmap_value_insert_into_set (EXP_GEN (block), rhs);
3447 FOR_EACH_SSA_TREE_OPERAND (op, realstmt, iter, SSA_OP_DEF)
3448 add_to_sets (op, op, NULL, TMP_GEN (block),
3454 else if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT
3455 && !ann->has_volatile_ops
3456 && TREE_CODE (GIMPLE_STMT_OPERAND (stmt, 0)) == SSA_NAME
3457 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI
3458 (GIMPLE_STMT_OPERAND (stmt, 0)))
3460 tree lhs = GIMPLE_STMT_OPERAND (stmt, 0);
3461 tree rhs = GIMPLE_STMT_OPERAND (stmt, 1);
3463 /* Try to look through loads. */
3464 if (TREE_CODE (lhs) == SSA_NAME
3465 && !ZERO_SSA_OPERANDS (stmt, SSA_OP_VIRTUAL_USES)
3466 && try_look_through_load (lhs, rhs, stmt, block))
3469 STRIP_USELESS_TYPE_CONVERSION (rhs);
3470 if (can_value_number_operation (rhs))
3472 /* For value numberable operation, create a
3473 duplicate expression with the operands replaced
3474 with the value handles of the original RHS. */
3475 tree newt = create_value_expr_from (rhs, block, stmt);
3478 /* If we can combine a conversion expression
3479 with the expression for its operand just
3480 record the value number for it. */
3481 if (try_combine_conversion (&newt))
3485 tree val = vn_lookup_or_add (newt, stmt);
3488 bitmap_value_insert_into_set (maximal_set, newt);
3489 bitmap_value_insert_into_set (EXP_GEN (block), newt);
3491 bitmap_insert_into_set (TMP_GEN (block), lhs);
3492 bitmap_value_insert_into_set (AVAIL_OUT (block), lhs);
3496 else if ((TREE_CODE (rhs) == SSA_NAME
3497 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs))
3498 || is_gimple_min_invariant (rhs)
3499 || TREE_CODE (rhs) == ADDR_EXPR
3500 || TREE_INVARIANT (rhs)
3503 /* Compute a value number for the RHS of the statement
3504 and add its value to the AVAIL_OUT set for the block.
3505 Add the LHS to TMP_GEN. */
3506 add_to_sets (lhs, rhs, stmt, TMP_GEN (block),
3509 if (TREE_CODE (rhs) == SSA_NAME
3510 && !is_undefined_value (rhs))
3511 bitmap_value_insert_into_set (EXP_GEN (block), rhs);
3516 /* For any other statement that we don't recognize, simply
3517 make the names generated by the statement available in
3518 AVAIL_OUT and TMP_GEN. */
3519 FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_DEF)
3520 add_to_sets (op, op, NULL, TMP_GEN (block), AVAIL_OUT (block));
3522 FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_USE)
3523 add_to_sets (op, op, NULL, NULL , AVAIL_OUT (block));
3526 /* Put the dominator children of BLOCK on the worklist of blocks
3527 to compute available sets for. */
3528 for (son = first_dom_son (CDI_DOMINATORS, block);
3530 son = next_dom_son (CDI_DOMINATORS, son))
3531 worklist[sp++] = son;
3538 /* Eliminate fully redundant computations. */
3547 block_stmt_iterator i;
3549 for (i = bsi_start (b); !bsi_end_p (i); bsi_next (&i))
3551 tree stmt = bsi_stmt (i);
3553 /* Lookup the RHS of the expression, see if we have an
3554 available computation for it. If so, replace the RHS with
3555 the available computation. */
3556 if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT
3557 && TREE_CODE (GIMPLE_STMT_OPERAND (stmt, 0)) == SSA_NAME
3558 && TREE_CODE (GIMPLE_STMT_OPERAND (stmt, 1)) != SSA_NAME
3559 && !is_gimple_min_invariant (GIMPLE_STMT_OPERAND (stmt, 1))
3560 && !stmt_ann (stmt)->has_volatile_ops)
3562 tree lhs = GIMPLE_STMT_OPERAND (stmt, 0);
3563 tree *rhs_p = &GIMPLE_STMT_OPERAND (stmt, 1);
3566 sprime = bitmap_find_leader (AVAIL_OUT (b),
3567 vn_lookup (lhs, NULL));
3570 && (TREE_CODE (*rhs_p) != SSA_NAME
3571 || may_propagate_copy (*rhs_p, sprime)))
3573 gcc_assert (sprime != *rhs_p);
3575 if (dump_file && (dump_flags & TDF_DETAILS))
3577 fprintf (dump_file, "Replaced ");
3578 print_generic_expr (dump_file, *rhs_p, 0);
3579 fprintf (dump_file, " with ");
3580 print_generic_expr (dump_file, sprime, 0);
3581 fprintf (dump_file, " in ");
3582 print_generic_stmt (dump_file, stmt, 0);
3585 if (TREE_CODE (sprime) == SSA_NAME)
3586 NECESSARY (SSA_NAME_DEF_STMT (sprime)) = 1;
3587 /* We need to make sure the new and old types actually match,
3588 which may require adding a simple cast, which fold_convert
3590 if (TREE_CODE (*rhs_p) != SSA_NAME
3591 && !tree_ssa_useless_type_conversion_1 (TREE_TYPE (*rhs_p),
3592 TREE_TYPE (sprime)))
3593 sprime = fold_convert (TREE_TYPE (*rhs_p), sprime);
3595 pre_stats.eliminations++;
3596 propagate_tree_value (rhs_p, sprime);
3599 /* If we removed EH side effects from the statement, clean
3600 its EH information. */
3601 if (maybe_clean_or_replace_eh_stmt (stmt, stmt))
3603 bitmap_set_bit (need_eh_cleanup,
3604 bb_for_stmt (stmt)->index);
3605 if (dump_file && (dump_flags & TDF_DETAILS))
3606 fprintf (dump_file, " Removed EH side effects.\n");
3614 /* Borrow a bit of tree-ssa-dce.c for the moment.
3615 XXX: In 4.1, we should be able to just run a DCE pass after PRE, though
3616 this may be a bit faster, and we may want critical edges kept split. */
3618 /* If OP's defining statement has not already been determined to be necessary,
3619 mark that statement necessary. Return the stmt, if it is newly
3623 mark_operand_necessary (tree op)
3629 if (TREE_CODE (op) != SSA_NAME)
3632 stmt = SSA_NAME_DEF_STMT (op);
3635 if (NECESSARY (stmt)
3636 || IS_EMPTY_STMT (stmt))
3639 NECESSARY (stmt) = 1;
3643 /* Because we don't follow exactly the standard PRE algorithm, and decide not
3644 to insert PHI nodes sometimes, and because value numbering of casts isn't
3645 perfect, we sometimes end up inserting dead code. This simple DCE-like
3646 pass removes any insertions we made that weren't actually used. */
3649 remove_dead_inserted_code (void)
3651 VEC(tree,heap) *worklist = NULL;
3655 worklist = VEC_alloc (tree, heap, VEC_length (tree, inserted_exprs));
3656 for (i = 0; VEC_iterate (tree, inserted_exprs, i, t); i++)
3659 VEC_quick_push (tree, worklist, t);
3661 while (VEC_length (tree, worklist) > 0)
3663 t = VEC_pop (tree, worklist);
3665 /* PHI nodes are somewhat special in that each PHI alternative has
3666 data and control dependencies. All the statements feeding the
3667 PHI node's arguments are always necessary. */
3668 if (TREE_CODE (t) == PHI_NODE)
3672 VEC_reserve (tree, heap, worklist, PHI_NUM_ARGS (t));
3673 for (k = 0; k < PHI_NUM_ARGS (t); k++)
3675 tree arg = PHI_ARG_DEF (t, k);
3676 if (TREE_CODE (arg) == SSA_NAME)
3678 arg = mark_operand_necessary (arg);
3680 VEC_quick_push (tree, worklist, arg);
3686 /* Propagate through the operands. Examine all the USE, VUSE and
3687 VDEF operands in this statement. Mark all the statements
3688 which feed this statement's uses as necessary. */
3692 /* The operands of VDEF expressions are also needed as they
3693 represent potential definitions that may reach this
3694 statement (VDEF operands allow us to follow def-def
3697 FOR_EACH_SSA_TREE_OPERAND (use, t, iter, SSA_OP_ALL_USES)
3699 tree n = mark_operand_necessary (use);
3701 VEC_safe_push (tree, heap, worklist, n);
3706 for (i = 0; VEC_iterate (tree, inserted_exprs, i, t); i++)
3710 block_stmt_iterator bsi;
3712 if (dump_file && (dump_flags & TDF_DETAILS))
3714 fprintf (dump_file, "Removing unnecessary insertion:");
3715 print_generic_stmt (dump_file, t, 0);
3718 if (TREE_CODE (t) == PHI_NODE)
3720 remove_phi_node (t, NULL, true);
3724 bsi = bsi_for_stmt (t);
3725 bsi_remove (&bsi, true);
3730 VEC_free (tree, heap, worklist);
3733 /* Initialize data structures used by PRE. */
3736 init_pre (bool do_fre)
3740 next_expression_id = 0;
3744 inserted_exprs = NULL;
3745 need_creation = NULL;
3746 pretemp = NULL_TREE;
3747 storetemp = NULL_TREE;
3748 prephitemp = NULL_TREE;
3752 loop_optimizer_init (LOOPS_NORMAL);
3754 connect_infinite_loops_to_exit ();
3755 memset (&pre_stats, 0, sizeof (pre_stats));
3758 postorder = XNEWVEC (int, n_basic_blocks - NUM_FIXED_BLOCKS);
3759 post_order_compute (postorder, false, false);
3762 bb->aux = xcalloc (1, sizeof (struct bb_bitmap_sets));
3764 calculate_dominance_info (CDI_POST_DOMINATORS);
3765 calculate_dominance_info (CDI_DOMINATORS);
3767 bitmap_obstack_initialize (&grand_bitmap_obstack);
3768 phi_translate_table = htab_create (5110, expr_pred_trans_hash,
3769 expr_pred_trans_eq, free);
3770 bitmap_set_pool = create_alloc_pool ("Bitmap sets",
3771 sizeof (struct bitmap_set), 30);
3772 binary_node_pool = create_alloc_pool ("Binary tree nodes",
3773 tree_code_size (PLUS_EXPR), 30);
3774 unary_node_pool = create_alloc_pool ("Unary tree nodes",
3775 tree_code_size (NEGATE_EXPR), 30);
3776 reference_node_pool = create_alloc_pool ("Reference tree nodes",
3777 tree_code_size (ARRAY_REF), 30);
3778 comparison_node_pool = create_alloc_pool ("Comparison tree nodes",
3779 tree_code_size (EQ_EXPR), 30);
3780 modify_expr_node_pool = create_alloc_pool ("GIMPLE_MODIFY_STMT nodes",
3781 tree_code_size (GIMPLE_MODIFY_STMT),
3783 obstack_init (&temp_call_expr_obstack);
3784 modify_expr_template = NULL;
3788 EXP_GEN (bb) = bitmap_set_new ();
3789 PHI_GEN (bb) = bitmap_set_new ();
3790 TMP_GEN (bb) = bitmap_set_new ();
3791 AVAIL_OUT (bb) = bitmap_set_new ();
3793 maximal_set = in_fre ? NULL : bitmap_set_new ();
3795 need_eh_cleanup = BITMAP_ALLOC (NULL);
3799 /* Deallocate data structures used by PRE. */
3808 VEC_free (tree, heap, inserted_exprs);
3809 VEC_free (tree, heap, need_creation);
3810 bitmap_obstack_release (&grand_bitmap_obstack);
3811 free_alloc_pool (bitmap_set_pool);
3812 free_alloc_pool (binary_node_pool);
3813 free_alloc_pool (reference_node_pool);
3814 free_alloc_pool (unary_node_pool);
3815 free_alloc_pool (comparison_node_pool);
3816 free_alloc_pool (modify_expr_node_pool);
3817 htab_delete (phi_translate_table);
3818 remove_fake_exit_edges ();
3826 free_dominance_info (CDI_POST_DOMINATORS);
3829 if (!bitmap_empty_p (need_eh_cleanup))
3831 tree_purge_all_dead_eh_edges (need_eh_cleanup);
3832 cleanup_tree_cfg ();
3835 BITMAP_FREE (need_eh_cleanup);
3837 /* Wipe out pointers to VALUE_HANDLEs. In the not terribly distant
3838 future we will want them to be persistent though. */
3839 for (i = 0; i < num_ssa_names; i++)
3841 tree name = ssa_name (i);
3846 if (SSA_NAME_VALUE (name)
3847 && TREE_CODE (SSA_NAME_VALUE (name)) == VALUE_HANDLE)
3848 SSA_NAME_VALUE (name) = NULL;
3850 if (current_loops != NULL)
3851 loop_optimizer_finalize ();
3854 /* Main entry point to the SSA-PRE pass. DO_FRE is true if the caller
3855 only wants to do full redundancy elimination. */
3858 execute_pre (bool do_fre)
3861 do_partial_partial = optimize > 2;
3865 insert_fake_stores ();
3867 /* Collect and value number expressions computed in each basic block. */
3870 if (dump_file && (dump_flags & TDF_DETAILS))
3876 print_bitmap_set (dump_file, EXP_GEN (bb), "exp_gen", bb->index);
3877 print_bitmap_set (dump_file, TMP_GEN (bb), "tmp_gen",
3879 print_bitmap_set (dump_file, AVAIL_OUT (bb), "avail_out",
3884 /* Insert can get quite slow on an incredibly large number of basic
3885 blocks due to some quadratic behavior. Until this behavior is
3886 fixed, don't run it when he have an incredibly large number of
3887 bb's. If we aren't going to run insert, there is no point in
3888 computing ANTIC, either, even though it's plenty fast. */
3889 if (!do_fre && n_basic_blocks < 4000)
3891 compute_antic_safe ();
3896 /* Remove all the redundant expressions. */
3899 if (dump_file && (dump_flags & TDF_STATS))
3901 fprintf (dump_file, "Insertions: %d\n", pre_stats.insertions);
3902 fprintf (dump_file, "PA inserted: %d\n", pre_stats.pa_insert);
3903 fprintf (dump_file, "New PHIs: %d\n", pre_stats.phis);
3904 fprintf (dump_file, "Eliminated: %d\n", pre_stats.eliminations);
3905 fprintf (dump_file, "Constified: %d\n", pre_stats.constified);
3907 bsi_commit_edge_inserts ();
3909 clear_expression_ids ();
3912 remove_dead_inserted_code ();
3913 realify_fake_stores ();
3919 /* Gate and execute functions for PRE. */
3924 execute_pre (false);
3931 return flag_tree_pre != 0;
3934 struct tree_opt_pass pass_pre =
3937 gate_pre, /* gate */
3938 do_pre, /* execute */
3941 0, /* static_pass_number */
3942 TV_TREE_PRE, /* tv_id */
3943 PROP_no_crit_edges | PROP_cfg
3944 | PROP_ssa | PROP_alias, /* properties_required */
3945 0, /* properties_provided */
3946 0, /* properties_destroyed */
3947 0, /* todo_flags_start */
3948 TODO_update_ssa_only_virtuals | TODO_dump_func | TODO_ggc_collect
3949 | TODO_verify_ssa, /* todo_flags_finish */
3954 /* Gate and execute functions for FRE. */
3966 return flag_tree_fre != 0;
3969 struct tree_opt_pass pass_fre =
3972 gate_fre, /* gate */
3973 execute_fre, /* execute */
3976 0, /* static_pass_number */
3977 TV_TREE_FRE, /* tv_id */
3978 PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */
3979 0, /* properties_provided */
3980 0, /* properties_destroyed */
3981 0, /* todo_flags_start */
3982 TODO_dump_func | TODO_ggc_collect | TODO_verify_ssa, /* todo_flags_finish */