2 Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007
3 Free Software Foundation, Inc.
4 Contributed by Daniel Berlin <dan@dberlin.org> and Steven Bosscher
7 This file is part of GCC.
9 GCC is free software; you can redistribute it and/or modify
10 it under the terms of the GNU General Public License as published by
11 the Free Software Foundation; either version 2, or (at your option)
14 GCC is distributed in the hope that it will be useful,
15 but WITHOUT ANY WARRANTY; without even the implied warranty of
16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 GNU General Public License for more details.
19 You should have received a copy of the GNU General Public License
20 along with GCC; see the file COPYING. If not, write to
21 the Free Software Foundation, 51 Franklin Street, Fifth Floor,
22 Boston, MA 02110-1301, USA. */
26 #include "coretypes.h"
30 #include "basic-block.h"
31 #include "diagnostic.h"
32 #include "tree-inline.h"
33 #include "tree-flow.h"
34 #include "tree-gimple.h"
35 #include "tree-dump.h"
39 #include "tree-iterator.h"
41 #include "alloc-pool.h"
43 #include "tree-pass.h"
46 #include "langhooks.h"
48 #include "tree-ssa-sccvn.h"
49 #include "pointer-set.h"
53 1. Avail sets can be shared by making an avail_find_leader that
54 walks up the dominator tree and looks in those avail sets.
55 This might affect code optimality, it's unclear right now.
56 2. Strength reduction can be performed by anticipating expressions
57 we can repair later on.
58 3. We can do back-substitution or smarter value numbering to catch
59 commutative expressions split up over multiple statements.
62 /* For ease of terminology, "expression node" in the below refers to
63 every expression node but GIMPLE_MODIFY_STMT, because GIMPLE_MODIFY_STMT's
64 represent the actual statement containing the expressions we care about,
65 and we cache the value number by putting it in the expression. */
69 First we walk the statements to generate the AVAIL sets, the
70 EXP_GEN sets, and the tmp_gen sets. EXP_GEN sets represent the
71 generation of values/expressions by a given block. We use them
72 when computing the ANTIC sets. The AVAIL sets consist of
73 SSA_NAME's that represent values, so we know what values are
74 available in what blocks. AVAIL is a forward dataflow problem. In
75 SSA, values are never killed, so we don't need a kill set, or a
76 fixpoint iteration, in order to calculate the AVAIL sets. In
77 traditional parlance, AVAIL sets tell us the downsafety of the
80 Next, we generate the ANTIC sets. These sets represent the
81 anticipatable expressions. ANTIC is a backwards dataflow
82 problem. An expression is anticipatable in a given block if it could
83 be generated in that block. This means that if we had to perform
84 an insertion in that block, of the value of that expression, we
85 could. Calculating the ANTIC sets requires phi translation of
86 expressions, because the flow goes backwards through phis. We must
87 iterate to a fixpoint of the ANTIC sets, because we have a kill
88 set. Even in SSA form, values are not live over the entire
89 function, only from their definition point onwards. So we have to
90 remove values from the ANTIC set once we go past the definition
91 point of the leaders that make them up.
92 compute_antic/compute_antic_aux performs this computation.
94 Third, we perform insertions to make partially redundant
95 expressions fully redundant.
97 An expression is partially redundant (excluding partial
100 1. It is AVAIL in some, but not all, of the predecessors of a
102 2. It is ANTIC in all the predecessors.
104 In order to make it fully redundant, we insert the expression into
105 the predecessors where it is not available, but is ANTIC.
107 For the partial anticipation case, we only perform insertion if it
108 is partially anticipated in some block, and fully available in all
111 insert/insert_aux/do_regular_insertion/do_partial_partial_insertion
112 performs these steps.
114 Fourth, we eliminate fully redundant expressions.
115 This is a simple statement walk that replaces redundant
116 calculations with the now available values. */
118 /* Representations of value numbers:
120 Value numbers are represented using the "value handle" approach.
121 This means that each SSA_NAME (and for other reasons to be
122 disclosed in a moment, expression nodes) has a value handle that
123 can be retrieved through get_value_handle. This value handle *is*
124 the value number of the SSA_NAME. You can pointer compare the
125 value handles for equivalence purposes.
127 For debugging reasons, the value handle is internally more than
128 just a number, it is a VALUE_HANDLE named "VH.x", where x is a
129 unique number for each value number in use. This allows
130 expressions with SSA_NAMES replaced by value handles to still be
131 pretty printed in a sane way. They simply print as "VH.3 *
134 Expression nodes have value handles associated with them as a
135 cache. Otherwise, we'd have to look them up again in the hash
136 table This makes significant difference (factor of two or more) on
137 some test cases. They can be thrown away after the pass is
140 /* Representation of expressions on value numbers:
142 In some portions of this code, you will notice we allocate "fake"
143 analogues to the expression we are value numbering, and replace the
144 operands with the values of the expression. Since we work on
145 values, and not just names, we canonicalize expressions to value
146 expressions for use in the ANTIC sets, the EXP_GEN set, etc.
148 This is theoretically unnecessary, it just saves a bunch of
149 repeated get_value_handle and find_leader calls in the remainder of
150 the code, trading off temporary memory usage for speed. The tree
151 nodes aren't actually creating more garbage, since they are
152 allocated in a special pools which are thrown away at the end of
155 All of this also means that if you print the EXP_GEN or ANTIC sets,
156 you will see "VH.5 + VH.7" in the set, instead of "a_55 +
157 b_66" or something. The only thing that actually cares about
158 seeing the value leaders is phi translation, and it needs to be
159 able to find the leader for a value in an arbitrary block, so this
160 "value expression" form is perfect for it (otherwise you'd do
161 get_value_handle->find_leader->translate->get_value_handle->find_leader).*/
164 /* Representation of sets:
166 There are currently two types of sets used, hopefully to be unified soon.
167 The AVAIL sets do not need to be sorted in any particular order,
168 and thus, are simply represented as two bitmaps, one that keeps
169 track of values present in the set, and one that keeps track of
170 expressions present in the set.
172 The other sets are represented as doubly linked lists kept in topological
173 order, with an optional supporting bitmap of values present in the
174 set. The sets represent values, and the elements can be values or
175 expressions. The elements can appear in different sets, but each
176 element can only appear once in each set.
178 Since each node in the set represents a value, we also want to be
179 able to map expression, set pairs to something that tells us
180 whether the value is present is a set. We use a per-set bitmap for
181 that. The value handles also point to a linked list of the
182 expressions they represent via a tree annotation. This is mainly
183 useful only for debugging, since we don't do identity lookups. */
186 /* Mapping from decl's to value handles, by pointer equality. We
187 "unshare" decls so we can give the same decl in different places
188 different value handles. */
189 struct pointer_map_t *decl_vh_map;
191 /* Mapping from expressions to ids. */
192 struct pointer_map_t *expression_id_map;
194 /* Next global expression id number. */
195 static unsigned int next_expression_id;
197 /* Mapping from expression to id number we can use in bitmap sets. */
198 static VEC(tree, heap) *expressions;
200 /* Allocate an expression id for EXPR. */
202 static inline unsigned int
203 alloc_expression_id (tree expr)
207 slot = (unsigned int *) pointer_map_insert (expression_id_map,
209 /* Make sure we won't overflow. */
210 gcc_assert (next_expression_id + 1 > next_expression_id);
212 *slot = next_expression_id++;
213 VEC_safe_push (tree, heap, expressions, expr);
214 return next_expression_id - 1;
217 /* Return the expression id for tree EXPR. */
219 static inline unsigned int
220 get_expression_id (tree expr)
223 slot = (unsigned int *) pointer_map_contains (expression_id_map,
228 /* Return the existing expression id for EXPR, or create one if one
229 does not exist yet. */
231 static inline unsigned int
232 get_or_alloc_expression_id (tree expr)
235 slot = (unsigned int *) pointer_map_contains (expression_id_map,
240 return alloc_expression_id (expr);
243 /* Return the expression that has expression id ID */
246 expression_for_id (unsigned int id)
248 return VEC_index (tree, expressions, id);
251 static bool in_fre = false;
253 /* An unordered bitmap set. One bitmap tracks values, the other,
255 typedef struct bitmap_set
261 #define FOR_EACH_EXPR_ID_IN_SET(set, id, bi) \
262 EXECUTE_IF_SET_IN_BITMAP(set->expressions, 0, id, bi)
264 /* Sets that we need to keep track of. */
265 typedef struct bb_bitmap_sets
267 /* The EXP_GEN set, which represents expressions/values generated in
269 bitmap_set_t exp_gen;
271 /* The PHI_GEN set, which represents PHI results generated in a
273 bitmap_set_t phi_gen;
275 /* The TMP_GEN set, which represents results/temporaries generated
276 in a basic block. IE the LHS of an expression. */
277 bitmap_set_t tmp_gen;
279 /* The AVAIL_OUT set, which represents which values are available in
280 a given basic block. */
281 bitmap_set_t avail_out;
283 /* The ANTIC_IN set, which represents which values are anticipatable
284 in a given basic block. */
285 bitmap_set_t antic_in;
287 /* The PA_IN set, which represents which values are
288 partially anticipatable in a given basic block. */
291 /* The NEW_SETS set, which is used during insertion to augment the
292 AVAIL_OUT set of blocks with the new insertions performed during
293 the current iteration. */
294 bitmap_set_t new_sets;
296 /* True if we have visited this block during ANTIC calculation. */
297 unsigned int visited:1;
299 /* True we have deferred processing this block during ANTIC
300 calculation until its successor is processed. */
301 unsigned int deferred : 1;
304 #define EXP_GEN(BB) ((bb_value_sets_t) ((BB)->aux))->exp_gen
305 #define PHI_GEN(BB) ((bb_value_sets_t) ((BB)->aux))->phi_gen
306 #define TMP_GEN(BB) ((bb_value_sets_t) ((BB)->aux))->tmp_gen
307 #define AVAIL_OUT(BB) ((bb_value_sets_t) ((BB)->aux))->avail_out
308 #define ANTIC_IN(BB) ((bb_value_sets_t) ((BB)->aux))->antic_in
309 #define PA_IN(BB) ((bb_value_sets_t) ((BB)->aux))->pa_in
310 #define NEW_SETS(BB) ((bb_value_sets_t) ((BB)->aux))->new_sets
311 #define BB_VISITED(BB) ((bb_value_sets_t) ((BB)->aux))->visited
312 #define BB_DEFERRED(BB) ((bb_value_sets_t) ((BB)->aux))->deferred
314 /* Maximal set of values, used to initialize the ANTIC problem, which
315 is an intersection problem. */
316 static bitmap_set_t maximal_set;
318 /* Basic block list in postorder. */
319 static int *postorder;
321 /* This structure is used to keep track of statistics on what
322 optimization PRE was able to perform. */
325 /* The number of RHS computations eliminated by PRE. */
328 /* The number of new expressions/temporaries generated by PRE. */
331 /* The number of inserts found due to partial anticipation */
334 /* The number of new PHI nodes added by PRE. */
337 /* The number of values found constant. */
342 static bool do_partial_partial;
343 static tree bitmap_find_leader (bitmap_set_t, tree);
344 static void bitmap_value_insert_into_set (bitmap_set_t, tree);
345 static void bitmap_value_replace_in_set (bitmap_set_t, tree);
346 static void bitmap_set_copy (bitmap_set_t, bitmap_set_t);
347 static bool bitmap_set_contains_value (bitmap_set_t, tree);
348 static void bitmap_insert_into_set (bitmap_set_t, tree);
349 static bitmap_set_t bitmap_set_new (void);
350 static bool is_undefined_value (tree);
351 static tree create_expression_by_pieces (basic_block, tree, tree);
352 static tree find_or_generate_expression (basic_block, tree, tree);
354 /* We can add and remove elements and entries to and from sets
355 and hash tables, so we use alloc pools for them. */
357 static alloc_pool bitmap_set_pool;
358 static alloc_pool binary_node_pool;
359 static alloc_pool unary_node_pool;
360 static alloc_pool reference_node_pool;
361 static alloc_pool comparison_node_pool;
362 static alloc_pool modify_expr_node_pool;
363 static alloc_pool decl_node_pool;
364 static bitmap_obstack grand_bitmap_obstack;
366 /* We can't use allocation pools to hold temporary CALL_EXPR objects, since
367 they are not of fixed size. Instead, use an obstack. */
369 static struct obstack temp_call_expr_obstack;
372 /* To avoid adding 300 temporary variables when we only need one, we
373 only create one temporary variable, on demand, and build ssa names
374 off that. We do have to change the variable if the types don't
375 match the current variable's type. */
377 static tree storetemp;
378 static tree prephitemp;
380 /* Set of blocks with statements that have had its EH information
382 static bitmap need_eh_cleanup;
384 /* Which expressions have been seen during a given phi translation. */
385 static bitmap seen_during_translate;
387 /* The phi_translate_table caches phi translations for a given
388 expression and predecessor. */
390 static htab_t phi_translate_table;
392 /* A three tuple {e, pred, v} used to cache phi translations in the
393 phi_translate_table. */
395 typedef struct expr_pred_trans_d
397 /* The expression. */
400 /* The predecessor block along which we translated the expression. */
403 /* vuses associated with the expression. */
404 VEC (tree, gc) *vuses;
406 /* The value that resulted from the translation. */
409 /* The hashcode for the expression, pred pair. This is cached for
412 } *expr_pred_trans_t;
414 /* Return the hash value for a phi translation table entry. */
417 expr_pred_trans_hash (const void *p)
419 const expr_pred_trans_t ve = (expr_pred_trans_t) p;
423 /* Return true if two phi translation table entries are the same.
424 P1 and P2 should point to the expr_pred_trans_t's to be compared.*/
427 expr_pred_trans_eq (const void *p1, const void *p2)
429 const expr_pred_trans_t ve1 = (expr_pred_trans_t) p1;
430 const expr_pred_trans_t ve2 = (expr_pred_trans_t) p2;
431 basic_block b1 = ve1->pred;
432 basic_block b2 = ve2->pred;
436 /* If they are not translations for the same basic block, they can't
442 /* If they are for the same basic block, determine if the
443 expressions are equal. */
444 if (!expressions_equal_p (ve1->e, ve2->e))
447 /* Make sure the vuses are equivalent. */
448 if (ve1->vuses == ve2->vuses)
451 if (VEC_length (tree, ve1->vuses) != VEC_length (tree, ve2->vuses))
454 for (i = 0; VEC_iterate (tree, ve1->vuses, i, vuse1); i++)
456 if (VEC_index (tree, ve2->vuses, i) != vuse1)
463 /* Search in the phi translation table for the translation of
464 expression E in basic block PRED with vuses VUSES.
465 Return the translated value, if found, NULL otherwise. */
468 phi_trans_lookup (tree e, basic_block pred, VEC (tree, gc) *vuses)
471 struct expr_pred_trans_d ept;
476 ept.hashcode = iterative_hash_expr (e, (unsigned long) pred);
477 slot = htab_find_slot_with_hash (phi_translate_table, &ept, ept.hashcode,
482 return ((expr_pred_trans_t) *slot)->v;
486 /* Add the tuple mapping from {expression E, basic block PRED, vuses VUSES} to
487 value V, to the phi translation table. */
490 phi_trans_add (tree e, tree v, basic_block pred, VEC (tree, gc) *vuses)
493 expr_pred_trans_t new_pair = XNEW (struct expr_pred_trans_d);
495 new_pair->pred = pred;
496 new_pair->vuses = vuses;
498 new_pair->hashcode = iterative_hash_expr (e, (unsigned long) pred);
499 slot = htab_find_slot_with_hash (phi_translate_table, new_pair,
500 new_pair->hashcode, INSERT);
503 *slot = (void *) new_pair;
507 /* Return true if V is a value expression that represents itself.
508 In our world, this is *only* non-value handles. */
511 constant_expr_p (tree v)
513 return TREE_CODE (v) != VALUE_HANDLE &&
514 (TREE_CODE (v) == FIELD_DECL || is_gimple_min_invariant (v));
517 /* Add expression E to the expression set of value V. */
520 add_to_value (tree v, tree e)
522 /* Constants have no expression sets. */
523 if (constant_expr_p (v))
526 if (VALUE_HANDLE_EXPR_SET (v) == NULL)
527 VALUE_HANDLE_EXPR_SET (v) = bitmap_set_new ();
529 bitmap_insert_into_set (VALUE_HANDLE_EXPR_SET (v), e);
532 /* Create a new bitmap set and return it. */
535 bitmap_set_new (void)
537 bitmap_set_t ret = (bitmap_set_t) pool_alloc (bitmap_set_pool);
538 ret->expressions = BITMAP_ALLOC (&grand_bitmap_obstack);
539 ret->values = BITMAP_ALLOC (&grand_bitmap_obstack);
543 /* Remove an expression EXPR from a bitmapped set. */
546 bitmap_remove_from_set (bitmap_set_t set, tree expr)
548 tree val = get_value_handle (expr);
551 if (!constant_expr_p (val))
553 bitmap_clear_bit (set->values, VALUE_HANDLE_ID (val));
554 bitmap_clear_bit (set->expressions, get_expression_id (expr));
558 /* Insert an expression EXPR into a bitmapped set. */
561 bitmap_insert_into_set (bitmap_set_t set, tree expr)
563 tree val = get_value_handle (expr);
566 if (!constant_expr_p (val))
568 bitmap_set_bit (set->values, VALUE_HANDLE_ID (val));
569 bitmap_set_bit (set->expressions, get_or_alloc_expression_id (expr));
573 /* Copy a bitmapped set ORIG, into bitmapped set DEST. */
576 bitmap_set_copy (bitmap_set_t dest, bitmap_set_t orig)
578 bitmap_copy (dest->expressions, orig->expressions);
579 bitmap_copy (dest->values, orig->values);
583 /* Free memory used up by SET. */
585 bitmap_set_free (bitmap_set_t set)
587 BITMAP_FREE (set->expressions);
588 BITMAP_FREE (set->values);
592 /* A comparison function for use in qsort to top sort a bitmap set. Simply
593 subtracts value handle ids, since they are created in topo-order. */
596 vh_compare (const void *pa, const void *pb)
598 const tree vha = get_value_handle (*((const tree *)pa));
599 const tree vhb = get_value_handle (*((const tree *)pb));
601 /* This can happen when we constify things. */
602 if (constant_expr_p (vha))
604 if (constant_expr_p (vhb))
608 else if (constant_expr_p (vhb))
610 return VALUE_HANDLE_ID (vha) - VALUE_HANDLE_ID (vhb);
613 /* Generate an topological-ordered array of bitmap set SET. */
615 static VEC(tree, heap) *
616 sorted_array_from_bitmap_set (bitmap_set_t set)
620 VEC(tree, heap) *result = NULL;
622 FOR_EACH_EXPR_ID_IN_SET (set, i, bi)
623 VEC_safe_push (tree, heap, result, expression_for_id (i));
625 qsort (VEC_address (tree, result), VEC_length (tree, result),
626 sizeof (tree), vh_compare);
631 /* Perform bitmapped set operation DEST &= ORIG. */
634 bitmap_set_and (bitmap_set_t dest, bitmap_set_t orig)
641 bitmap temp = BITMAP_ALLOC (&grand_bitmap_obstack);
643 bitmap_and_into (dest->values, orig->values);
644 bitmap_copy (temp, dest->expressions);
645 EXECUTE_IF_SET_IN_BITMAP (temp, 0, i, bi)
647 tree expr = expression_for_id (i);
648 tree val = get_value_handle (expr);
649 if (!bitmap_bit_p (dest->values, VALUE_HANDLE_ID (val)))
650 bitmap_clear_bit (dest->expressions, i);
656 /* Subtract all values and expressions contained in ORIG from DEST. */
659 bitmap_set_subtract (bitmap_set_t dest, bitmap_set_t orig)
661 bitmap_set_t result = bitmap_set_new ();
665 bitmap_and_compl (result->expressions, dest->expressions,
668 FOR_EACH_EXPR_ID_IN_SET (result, i, bi)
670 tree expr = expression_for_id (i);
671 tree val = get_value_handle (expr);
672 bitmap_set_bit (result->values, VALUE_HANDLE_ID (val));
678 /* Subtract all the values in bitmap set B from bitmap set A. */
681 bitmap_set_subtract_values (bitmap_set_t a, bitmap_set_t b)
685 bitmap temp = BITMAP_ALLOC (&grand_bitmap_obstack);
687 bitmap_copy (temp, a->expressions);
688 EXECUTE_IF_SET_IN_BITMAP (temp, 0, i, bi)
690 tree expr = expression_for_id (i);
691 if (bitmap_set_contains_value (b, get_value_handle (expr)))
692 bitmap_remove_from_set (a, expr);
698 /* Return true if bitmapped set SET contains the value VAL. */
701 bitmap_set_contains_value (bitmap_set_t set, tree val)
703 if (constant_expr_p (val))
706 if (!set || bitmap_empty_p (set->expressions))
709 return bitmap_bit_p (set->values, VALUE_HANDLE_ID (val));
713 bitmap_set_contains_expr (bitmap_set_t set, tree expr)
715 return bitmap_bit_p (set->expressions, get_expression_id (expr));
718 /* Replace an instance of value LOOKFOR with expression EXPR in SET. */
721 bitmap_set_replace_value (bitmap_set_t set, tree lookfor, tree expr)
723 bitmap_set_t exprset;
727 if (constant_expr_p (lookfor))
730 if (!bitmap_set_contains_value (set, lookfor))
733 /* The number of expressions having a given value is usually
734 significantly less than the total number of expressions in SET.
735 Thus, rather than check, for each expression in SET, whether it
736 has the value LOOKFOR, we walk the reverse mapping that tells us
737 what expressions have a given value, and see if any of those
738 expressions are in our set. For large testcases, this is about
739 5-10x faster than walking the bitmap. If this is somehow a
740 significant lose for some cases, we can choose which set to walk
741 based on the set size. */
742 exprset = VALUE_HANDLE_EXPR_SET (lookfor);
743 FOR_EACH_EXPR_ID_IN_SET (exprset, i, bi)
745 if (bitmap_bit_p (set->expressions, i))
747 bitmap_clear_bit (set->expressions, i);
748 bitmap_set_bit (set->expressions, get_expression_id (expr));
754 /* Return true if two bitmap sets are equal. */
757 bitmap_set_equal (bitmap_set_t a, bitmap_set_t b)
759 return bitmap_equal_p (a->values, b->values);
762 /* Replace an instance of EXPR's VALUE with EXPR in SET if it exists,
763 and add it otherwise. */
766 bitmap_value_replace_in_set (bitmap_set_t set, tree expr)
768 tree val = get_value_handle (expr);
770 if (bitmap_set_contains_value (set, val))
771 bitmap_set_replace_value (set, val, expr);
773 bitmap_insert_into_set (set, expr);
776 /* Insert EXPR into SET if EXPR's value is not already present in
780 bitmap_value_insert_into_set (bitmap_set_t set, tree expr)
782 tree val = get_value_handle (expr);
784 if (constant_expr_p (val))
787 if (!bitmap_set_contains_value (set, val))
788 bitmap_insert_into_set (set, expr);
791 /* Print out SET to OUTFILE. */
794 print_bitmap_set (FILE *outfile, bitmap_set_t set,
795 const char *setname, int blockindex)
797 fprintf (outfile, "%s[%d] := { ", setname, blockindex);
804 FOR_EACH_EXPR_ID_IN_SET (set, i, bi)
806 tree expr = expression_for_id (i);
809 fprintf (outfile, ", ");
811 print_generic_expr (outfile, expr, 0);
813 fprintf (outfile, " (");
814 print_generic_expr (outfile, get_value_handle (expr), 0);
815 fprintf (outfile, ") ");
818 fprintf (outfile, " }\n");
821 void debug_bitmap_set (bitmap_set_t);
824 debug_bitmap_set (bitmap_set_t set)
826 print_bitmap_set (stderr, set, "debug", 0);
829 /* Print out the expressions that have VAL to OUTFILE. */
832 print_value_expressions (FILE *outfile, tree val)
834 if (VALUE_HANDLE_EXPR_SET (val))
837 sprintf (s, "VH.%04d", VALUE_HANDLE_ID (val));
838 print_bitmap_set (outfile, VALUE_HANDLE_EXPR_SET (val), s, 0);
844 debug_value_expressions (tree val)
846 print_value_expressions (stderr, val);
849 /* Return the folded version of T if T, when folded, is a gimple
850 min_invariant. Otherwise, return T. */
853 fully_constant_expression (tree t)
857 if (folded && is_gimple_min_invariant (folded))
862 /* Make a temporary copy of a CALL_EXPR object NODE. */
865 temp_copy_call_expr (tree node)
867 return (tree) obstack_copy (&temp_call_expr_obstack, node, tree_size (node));
870 /* Translate the vuses in the VUSES vector backwards through phi nodes
871 in PHIBLOCK, so that they have the value they would have in
874 static VEC(tree, gc) *
875 translate_vuses_through_block (VEC (tree, gc) *vuses,
876 basic_block phiblock,
880 VEC(tree, gc) *result = NULL;
883 for (i = 0; VEC_iterate (tree, vuses, i, oldvuse); i++)
885 tree phi = SSA_NAME_DEF_STMT (oldvuse);
886 if (TREE_CODE (phi) == PHI_NODE
887 && bb_for_stmt (phi) == phiblock)
889 edge e = find_edge (block, bb_for_stmt (phi));
892 tree def = PHI_ARG_DEF (phi, e->dest_idx);
896 result = VEC_copy (tree, gc, vuses);
897 VEC_replace (tree, result, i, def);
903 /* We avoid creating a new copy of the vuses unless something
904 actually changed, so result can be NULL. */
914 /* Like find_leader, but checks for the value existing in SET1 *or*
915 SET2. This is used to avoid making a set consisting of the union
916 of PA_IN and ANTIC_IN during insert. */
919 find_leader_in_sets (tree expr, bitmap_set_t set1, bitmap_set_t set2)
923 result = bitmap_find_leader (set1, expr);
925 result = bitmap_find_leader (set2, expr);
929 /* Translate EXPR using phis in PHIBLOCK, so that it has the values of
930 the phis in PRED. SEEN is a bitmap saying which expression we have
931 translated since we started translation of the toplevel expression.
932 Return NULL if we can't find a leader for each part of the
933 translated expression. */
936 phi_translate_1 (tree expr, bitmap_set_t set1, bitmap_set_t set2,
937 basic_block pred, basic_block phiblock, bitmap seen)
939 tree phitrans = NULL;
945 if (constant_expr_p (expr))
948 /* Phi translations of a given expression don't change. */
949 if (EXPR_P (expr) || GIMPLE_STMT_P (expr) || REFERENCE_CLASS_P (expr)
954 vh = get_value_handle (expr);
955 if (vh && TREE_CODE (vh) == VALUE_HANDLE)
956 phitrans = phi_trans_lookup (expr, pred, VALUE_HANDLE_VUSES (vh));
958 phitrans = phi_trans_lookup (expr, pred, NULL);
961 phitrans = phi_trans_lookup (expr, pred, NULL);
966 /* Prevent cycles when we have recursively dependent leaders. This
967 can only happen when phi translating the maximal set. */
970 unsigned int expr_id = get_expression_id (expr);
971 if (bitmap_bit_p (seen, expr_id))
973 bitmap_set_bit (seen, expr_id);
976 switch (TREE_CODE_CLASS (TREE_CODE (expr)))
983 if (TREE_CODE (expr) != CALL_EXPR)
987 tree oldfn = CALL_EXPR_FN (expr);
988 tree oldsc = CALL_EXPR_STATIC_CHAIN (expr);
989 tree newfn, newsc = NULL;
990 tree newexpr = NULL_TREE;
991 tree vh = get_value_handle (expr);
992 bool invariantarg = false;
994 VEC (tree, gc) *vuses = VALUE_HANDLE_VUSES (vh);
995 VEC (tree, gc) *tvuses;
997 newfn = phi_translate_1 (find_leader_in_sets (oldfn, set1, set2),
998 set1, set2, pred, phiblock, seen);
1003 newexpr = temp_copy_call_expr (expr);
1004 CALL_EXPR_FN (newexpr) = get_value_handle (newfn);
1008 newsc = phi_translate_1 (find_leader_in_sets (oldsc, set1, set2),
1009 set1, set2, pred, phiblock, seen);
1015 newexpr = temp_copy_call_expr (expr);
1016 CALL_EXPR_STATIC_CHAIN (newexpr) = get_value_handle (newsc);
1020 /* phi translate the argument list piece by piece. */
1021 nargs = call_expr_nargs (expr);
1022 for (i = 0; i < nargs; i++)
1024 tree oldval = CALL_EXPR_ARG (expr, i);
1028 /* This may seem like a weird place for this
1029 check, but it's actually the easiest place to
1030 do it. We can't do it lower on in the
1031 recursion because it's valid for pieces of a
1032 component ref to be of AGGREGATE_TYPE, as long
1033 as the outermost one is not.
1034 To avoid *that* case, we have a check for
1035 AGGREGATE_TYPE_P in insert_aux. However, that
1036 check will *not* catch this case because here
1037 it occurs in the argument list. */
1038 if (AGGREGATE_TYPE_P (TREE_TYPE (oldval)))
1040 oldval = find_leader_in_sets (oldval, set1, set2);
1041 newval = phi_translate_1 (oldval, set1, set2, pred,
1045 if (newval != oldval)
1047 invariantarg |= is_gimple_min_invariant (newval);
1049 newexpr = temp_copy_call_expr (expr);
1050 CALL_EXPR_ARG (newexpr, i) = get_value_handle (newval);
1055 /* In case of new invariant args we might try to fold the call
1057 if (invariantarg && !newsc)
1059 tree tmp1 = build_call_array (TREE_TYPE (expr),
1060 newfn, call_expr_nargs (newexpr),
1061 CALL_EXPR_ARGP (newexpr));
1062 tree tmp2 = fold (tmp1);
1065 STRIP_TYPE_NOPS (tmp2);
1066 if (is_gimple_min_invariant (tmp2))
1071 tvuses = translate_vuses_through_block (vuses, phiblock, pred);
1072 if (vuses != tvuses && ! newexpr)
1073 newexpr = temp_copy_call_expr (expr);
1077 newexpr->base.ann = NULL;
1078 vn_lookup_or_add_with_vuses (newexpr, tvuses);
1081 phi_trans_add (oldexpr, expr, pred, tvuses);
1086 case tcc_declaration:
1088 VEC (tree, gc) * oldvuses = NULL;
1089 VEC (tree, gc) * newvuses = NULL;
1091 oldvuses = VALUE_HANDLE_VUSES (get_value_handle (expr));
1093 newvuses = translate_vuses_through_block (oldvuses, phiblock,
1096 if (oldvuses != newvuses)
1098 tree newexpr = (tree) pool_alloc (decl_node_pool);
1099 memcpy (newexpr, expr, tree_size (expr));
1100 vn_lookup_or_add_with_vuses (newexpr, newvuses);
1102 phi_trans_add (expr, expr, pred, newvuses);
1105 phi_trans_add (oldexpr, expr, pred, newvuses);
1111 tree oldop0 = TREE_OPERAND (expr, 0);
1120 VEC (tree, gc) * oldvuses = NULL;
1121 VEC (tree, gc) * newvuses = NULL;
1123 if (TREE_CODE (expr) != INDIRECT_REF
1124 && TREE_CODE (expr) != COMPONENT_REF
1125 && TREE_CODE (expr) != ARRAY_REF)
1128 oldop0 = find_leader_in_sets (oldop0, set1, set2);
1129 newop0 = phi_translate_1 (oldop0, set1, set2, pred, phiblock, seen);
1133 if (TREE_CODE (expr) == ARRAY_REF)
1135 oldop1 = TREE_OPERAND (expr, 1);
1136 oldop1 = find_leader_in_sets (oldop1, set1, set2);
1137 newop1 = phi_translate_1 (oldop1, set1, set2, pred, phiblock, seen);
1142 oldop2 = TREE_OPERAND (expr, 2);
1145 oldop2 = find_leader_in_sets (oldop2, set1, set2);
1146 newop2 = phi_translate_1 (oldop2, set1, set2, pred, phiblock, seen);
1151 oldop3 = TREE_OPERAND (expr, 3);
1154 oldop3 = find_leader_in_sets (oldop3, set1, set2);
1155 newop3 = phi_translate_1 (oldop3, set1, set2, pred, phiblock, seen);
1162 oldvuses = VALUE_HANDLE_VUSES (get_value_handle (expr));
1164 newvuses = translate_vuses_through_block (oldvuses, phiblock,
1167 if (newop0 != oldop0 || newvuses != oldvuses
1170 || newop3 != oldop3)
1174 newexpr = (tree) pool_alloc (reference_node_pool);
1175 memcpy (newexpr, expr, tree_size (expr));
1176 TREE_OPERAND (newexpr, 0) = get_value_handle (newop0);
1177 if (TREE_CODE (expr) == ARRAY_REF)
1179 TREE_OPERAND (newexpr, 1) = get_value_handle (newop1);
1181 TREE_OPERAND (newexpr, 2) = get_value_handle (newop2);
1183 TREE_OPERAND (newexpr, 3) = get_value_handle (newop3);
1186 t = fully_constant_expression (newexpr);
1190 pool_free (reference_node_pool, newexpr);
1195 newexpr->base.ann = NULL;
1196 vn_lookup_or_add_with_vuses (newexpr, newvuses);
1200 phi_trans_add (oldexpr, expr, pred, newvuses);
1206 case tcc_comparison:
1208 tree oldop1 = TREE_OPERAND (expr, 0);
1209 tree oldval1 = oldop1;
1210 tree oldop2 = TREE_OPERAND (expr, 1);
1211 tree oldval2 = oldop2;
1216 oldop1 = find_leader_in_sets (oldop1, set1, set2);
1217 newop1 = phi_translate_1 (oldop1, set1, set2, pred, phiblock, seen);
1221 oldop2 = find_leader_in_sets (oldop2, set1, set2);
1222 newop2 = phi_translate_1 (oldop2, set1, set2, pred, phiblock, seen);
1225 if (newop1 != oldop1 || newop2 != oldop2)
1228 newexpr = (tree) pool_alloc (binary_node_pool);
1229 memcpy (newexpr, expr, tree_size (expr));
1230 TREE_OPERAND (newexpr, 0) = newop1 == oldop1 ? oldval1 : get_value_handle (newop1);
1231 TREE_OPERAND (newexpr, 1) = newop2 == oldop2 ? oldval2 : get_value_handle (newop2);
1232 t = fully_constant_expression (newexpr);
1235 pool_free (binary_node_pool, newexpr);
1240 newexpr->base.ann = NULL;
1241 vn_lookup_or_add (newexpr);
1245 phi_trans_add (oldexpr, expr, pred, NULL);
1251 tree oldop1 = TREE_OPERAND (expr, 0);
1255 oldop1 = find_leader_in_sets (oldop1, set1, set2);
1256 newop1 = phi_translate_1 (oldop1, set1, set2, pred, phiblock, seen);
1259 if (newop1 != oldop1)
1262 newexpr = (tree) pool_alloc (unary_node_pool);
1263 memcpy (newexpr, expr, tree_size (expr));
1264 TREE_OPERAND (newexpr, 0) = get_value_handle (newop1);
1265 t = fully_constant_expression (newexpr);
1268 pool_free (unary_node_pool, newexpr);
1273 newexpr->base.ann = NULL;
1274 vn_lookup_or_add (newexpr);
1278 phi_trans_add (oldexpr, expr, pred, NULL);
1282 case tcc_exceptional:
1287 gcc_assert (TREE_CODE (expr) == SSA_NAME);
1289 def_stmt = SSA_NAME_DEF_STMT (expr);
1290 if (TREE_CODE (def_stmt) == PHI_NODE
1291 && bb_for_stmt (def_stmt) == phiblock)
1296 e = find_edge (pred, bb_for_stmt (phi));
1300 tree def = PHI_ARG_DEF (phi, e->dest_idx);
1302 if (is_gimple_min_invariant (def))
1305 if (is_undefined_value (def))
1308 val = get_value_handle (def);
1320 /* Translate EXPR using phis in PHIBLOCK, so that it has the values of
1322 Return NULL if we can't find a leader for each part of the
1323 translated expression. */
1326 phi_translate (tree expr, bitmap_set_t set1, bitmap_set_t set2,
1327 basic_block pred, basic_block phiblock)
1329 bitmap_clear (seen_during_translate);
1330 return phi_translate_1 (expr, set1, set2, pred, phiblock,
1331 seen_during_translate);
1334 /* For each expression in SET, translate the value handles through phi nodes
1335 in PHIBLOCK using edge PHIBLOCK->PRED, and store the resulting
1336 expressions in DEST. */
1339 phi_translate_set (bitmap_set_t dest, bitmap_set_t set, basic_block pred,
1340 basic_block phiblock)
1342 VEC (tree, heap) *exprs;
1346 if (!phi_nodes (phiblock))
1348 bitmap_set_copy (dest, set);
1352 exprs = sorted_array_from_bitmap_set (set);
1353 for (i = 0; VEC_iterate (tree, exprs, i, expr); i++)
1356 translated = phi_translate (expr, set, NULL, pred, phiblock);
1358 /* Don't add constants or empty translations to the cache, since
1359 we won't look them up that way, or use the result, anyway. */
1360 if (translated && !is_gimple_min_invariant (translated))
1362 tree vh = get_value_handle (translated);
1363 VEC (tree, gc) *vuses;
1365 /* The value handle itself may also be an invariant, in
1366 which case, it has no vuses. */
1367 vuses = !is_gimple_min_invariant (vh)
1368 ? VALUE_HANDLE_VUSES (vh) : NULL;
1369 phi_trans_add (expr, translated, pred, vuses);
1372 if (translated != NULL)
1373 bitmap_value_insert_into_set (dest, translated);
1375 VEC_free (tree, heap, exprs);
1378 /* Find the leader for a value (i.e., the name representing that
1379 value) in a given set, and return it. Return NULL if no leader is
1383 bitmap_find_leader (bitmap_set_t set, tree val)
1388 if (constant_expr_p (val))
1391 if (bitmap_set_contains_value (set, val))
1393 /* Rather than walk the entire bitmap of expressions, and see
1394 whether any of them has the value we are looking for, we look
1395 at the reverse mapping, which tells us the set of expressions
1396 that have a given value (IE value->expressions with that
1397 value) and see if any of those expressions are in our set.
1398 The number of expressions per value is usually significantly
1399 less than the number of expressions in the set. In fact, for
1400 large testcases, doing it this way is roughly 5-10x faster
1401 than walking the bitmap.
1402 If this is somehow a significant lose for some cases, we can
1403 choose which set to walk based on which set is smaller. */
1406 bitmap_set_t exprset = VALUE_HANDLE_EXPR_SET (val);
1408 EXECUTE_IF_AND_IN_BITMAP (exprset->expressions,
1409 set->expressions, 0, i, bi)
1410 return expression_for_id (i);
1415 /* Determine if VALUE, a memory operation, is ANTIC_IN at the top of
1416 BLOCK by seeing if it is not killed in the block. Note that we are
1417 only determining whether there is a store that kills it. Because
1418 of the order in which clean iterates over values, we are guaranteed
1419 that altered operands will have caused us to be eliminated from the
1420 ANTIC_IN set already. */
1423 value_dies_in_block_x (tree vh, basic_block block)
1427 VEC (tree, gc) *vuses = VALUE_HANDLE_VUSES (vh);
1429 /* Conservatively, a value dies if it's vuses are defined in this
1430 block, unless they come from phi nodes (which are merge operations,
1431 rather than stores. */
1432 for (i = 0; VEC_iterate (tree, vuses, i, vuse); i++)
1434 tree def = SSA_NAME_DEF_STMT (vuse);
1436 if (bb_for_stmt (def) != block)
1438 if (TREE_CODE (def) == PHI_NODE)
1445 /* Determine if the expression EXPR is valid in SET1 U SET2.
1446 ONLY SET2 CAN BE NULL.
1447 This means that we have a leader for each part of the expression
1448 (if it consists of values), or the expression is an SSA_NAME.
1449 For loads/calls, we also see if the vuses are killed in this block.
1451 NB: We never should run into a case where we have SSA_NAME +
1452 SSA_NAME or SSA_NAME + value. The sets valid_in_sets is called on,
1453 the ANTIC sets, will only ever have SSA_NAME's or value expressions
1454 (IE VALUE1 + VALUE2, *VALUE1, VALUE1 < VALUE2) */
1456 #define union_contains_value(SET1, SET2, VAL) \
1457 (bitmap_set_contains_value ((SET1), (VAL)) \
1458 || ((SET2) && bitmap_set_contains_value ((SET2), (VAL))))
1461 valid_in_sets (bitmap_set_t set1, bitmap_set_t set2, tree expr,
1464 tree vh = get_value_handle (expr);
1465 switch (TREE_CODE_CLASS (TREE_CODE (expr)))
1468 case tcc_comparison:
1470 tree op1 = TREE_OPERAND (expr, 0);
1471 tree op2 = TREE_OPERAND (expr, 1);
1473 return union_contains_value (set1, set2, op1)
1474 && union_contains_value (set1, set2, op2);
1479 tree op1 = TREE_OPERAND (expr, 0);
1480 return union_contains_value (set1, set2, op1);
1483 case tcc_expression:
1488 if (TREE_CODE (expr) == CALL_EXPR)
1490 tree fn = CALL_EXPR_FN (expr);
1491 tree sc = CALL_EXPR_STATIC_CHAIN (expr);
1493 call_expr_arg_iterator iter;
1495 /* Check the non-argument operands first. */
1496 if (!union_contains_value (set1, set2, fn)
1497 || (sc && !union_contains_value (set1, set2, sc)))
1500 /* Now check the operands. */
1501 FOR_EACH_CALL_EXPR_ARG (arg, iter, expr)
1503 if (!union_contains_value (set1, set2, arg))
1506 return !value_dies_in_block_x (vh, block);
1513 if (TREE_CODE (expr) == INDIRECT_REF
1514 || TREE_CODE (expr) == COMPONENT_REF
1515 || TREE_CODE (expr) == ARRAY_REF)
1517 tree op0 = TREE_OPERAND (expr, 0);
1518 gcc_assert (is_gimple_min_invariant (op0)
1519 || TREE_CODE (op0) == VALUE_HANDLE);
1520 if (!union_contains_value (set1, set2, op0))
1522 if (TREE_CODE (expr) == ARRAY_REF)
1524 tree op1 = TREE_OPERAND (expr, 1);
1525 tree op2 = TREE_OPERAND (expr, 2);
1526 tree op3 = TREE_OPERAND (expr, 3);
1527 gcc_assert (is_gimple_min_invariant (op1)
1528 || TREE_CODE (op1) == VALUE_HANDLE);
1529 if (!union_contains_value (set1, set2, op1))
1531 gcc_assert (!op2 || is_gimple_min_invariant (op2)
1532 || TREE_CODE (op2) == VALUE_HANDLE);
1534 && !union_contains_value (set1, set2, op2))
1536 gcc_assert (!op3 || is_gimple_min_invariant (op3)
1537 || TREE_CODE (op3) == VALUE_HANDLE);
1539 && !union_contains_value (set1, set2, op3))
1542 return !value_dies_in_block_x (vh, block);
1547 case tcc_exceptional:
1549 gcc_assert (TREE_CODE (expr) == SSA_NAME);
1550 return bitmap_set_contains_expr (AVAIL_OUT (block), expr);
1553 case tcc_declaration:
1554 return !value_dies_in_block_x (vh, block);
1557 /* No other cases should be encountered. */
1562 /* Clean the set of expressions that are no longer valid in SET1 or
1563 SET2. This means expressions that are made up of values we have no
1564 leaders for in SET1 or SET2. This version is used for partial
1565 anticipation, which means it is not valid in either ANTIC_IN or
1569 dependent_clean (bitmap_set_t set1, bitmap_set_t set2, basic_block block)
1571 VEC (tree, heap) *exprs = sorted_array_from_bitmap_set (set1);
1575 for (i = 0; VEC_iterate (tree, exprs, i, expr); i++)
1577 if (!valid_in_sets (set1, set2, expr, block))
1578 bitmap_remove_from_set (set1, expr);
1580 VEC_free (tree, heap, exprs);
1583 /* Clean the set of expressions that are no longer valid in SET. This
1584 means expressions that are made up of values we have no leaders for
1588 clean (bitmap_set_t set, basic_block block)
1590 VEC (tree, heap) *exprs = sorted_array_from_bitmap_set (set);
1594 for (i = 0; VEC_iterate (tree, exprs, i, expr); i++)
1596 if (!valid_in_sets (set, NULL, expr, block))
1597 bitmap_remove_from_set (set, expr);
1599 VEC_free (tree, heap, exprs);
1602 static sbitmap has_abnormal_preds;
1604 /* List of blocks that may have changed during ANTIC computation and
1605 thus need to be iterated over. */
1607 static sbitmap changed_blocks;
1609 /* Decide whether to defer a block for a later iteration, or PHI
1610 translate SOURCE to DEST using phis in PHIBLOCK. Return false if we
1611 should defer the block, and true if we processed it. */
1614 defer_or_phi_translate_block (bitmap_set_t dest, bitmap_set_t source,
1615 basic_block block, basic_block phiblock)
1617 if (!BB_VISITED (phiblock))
1619 SET_BIT (changed_blocks, block->index);
1620 BB_VISITED (block) = 0;
1621 BB_DEFERRED (block) = 1;
1625 phi_translate_set (dest, source, block, phiblock);
1629 /* Compute the ANTIC set for BLOCK.
1631 If succs(BLOCK) > 1 then
1632 ANTIC_OUT[BLOCK] = intersection of ANTIC_IN[b] for all succ(BLOCK)
1633 else if succs(BLOCK) == 1 then
1634 ANTIC_OUT[BLOCK] = phi_translate (ANTIC_IN[succ(BLOCK)])
1636 ANTIC_IN[BLOCK] = clean(ANTIC_OUT[BLOCK] U EXP_GEN[BLOCK] - TMP_GEN[BLOCK])
1640 compute_antic_aux (basic_block block, bool block_has_abnormal_pred_edge)
1642 bool changed = false;
1643 bitmap_set_t S, old, ANTIC_OUT;
1649 old = ANTIC_OUT = S = NULL;
1650 BB_VISITED (block) = 1;
1652 /* If any edges from predecessors are abnormal, antic_in is empty,
1654 if (block_has_abnormal_pred_edge)
1655 goto maybe_dump_sets;
1657 old = ANTIC_IN (block);
1658 ANTIC_OUT = bitmap_set_new ();
1660 /* If the block has no successors, ANTIC_OUT is empty. */
1661 if (EDGE_COUNT (block->succs) == 0)
1663 /* If we have one successor, we could have some phi nodes to
1664 translate through. */
1665 else if (single_succ_p (block))
1667 basic_block succ_bb = single_succ (block);
1669 /* We trade iterations of the dataflow equations for having to
1670 phi translate the maximal set, which is incredibly slow
1671 (since the maximal set often has 300+ members, even when you
1672 have a small number of blocks).
1673 Basically, we defer the computation of ANTIC for this block
1674 until we have processed it's successor, which will inevitably
1675 have a *much* smaller set of values to phi translate once
1676 clean has been run on it.
1677 The cost of doing this is that we technically perform more
1678 iterations, however, they are lower cost iterations.
1680 Timings for PRE on tramp3d-v4:
1681 without maximal set fix: 11 seconds
1682 with maximal set fix/without deferring: 26 seconds
1683 with maximal set fix/with deferring: 11 seconds
1686 if (!defer_or_phi_translate_block (ANTIC_OUT, ANTIC_IN (succ_bb),
1690 goto maybe_dump_sets;
1693 /* If we have multiple successors, we take the intersection of all of
1694 them. Note that in the case of loop exit phi nodes, we may have
1695 phis to translate through. */
1698 VEC(basic_block, heap) * worklist;
1700 basic_block bprime, first;
1702 worklist = VEC_alloc (basic_block, heap, EDGE_COUNT (block->succs));
1703 FOR_EACH_EDGE (e, ei, block->succs)
1704 VEC_quick_push (basic_block, worklist, e->dest);
1705 first = VEC_index (basic_block, worklist, 0);
1707 if (phi_nodes (first))
1709 bitmap_set_t from = ANTIC_IN (first);
1711 if (!BB_VISITED (first))
1713 phi_translate_set (ANTIC_OUT, from, block, first);
1717 if (!BB_VISITED (first))
1718 bitmap_set_copy (ANTIC_OUT, maximal_set);
1720 bitmap_set_copy (ANTIC_OUT, ANTIC_IN (first));
1723 for (i = 1; VEC_iterate (basic_block, worklist, i, bprime); i++)
1725 if (phi_nodes (bprime))
1727 bitmap_set_t tmp = bitmap_set_new ();
1728 bitmap_set_t from = ANTIC_IN (bprime);
1730 if (!BB_VISITED (bprime))
1732 phi_translate_set (tmp, from, block, bprime);
1733 bitmap_set_and (ANTIC_OUT, tmp);
1734 bitmap_set_free (tmp);
1738 if (!BB_VISITED (bprime))
1739 bitmap_set_and (ANTIC_OUT, maximal_set);
1741 bitmap_set_and (ANTIC_OUT, ANTIC_IN (bprime));
1744 VEC_free (basic_block, heap, worklist);
1747 /* Generate ANTIC_OUT - TMP_GEN. */
1748 S = bitmap_set_subtract (ANTIC_OUT, TMP_GEN (block));
1750 /* Start ANTIC_IN with EXP_GEN - TMP_GEN. */
1751 ANTIC_IN (block) = bitmap_set_subtract (EXP_GEN (block),
1754 /* Then union in the ANTIC_OUT - TMP_GEN values,
1755 to get ANTIC_OUT U EXP_GEN - TMP_GEN */
1756 FOR_EACH_EXPR_ID_IN_SET (S, bii, bi)
1757 bitmap_value_insert_into_set (ANTIC_IN (block),
1758 expression_for_id (bii));
1760 clean (ANTIC_IN (block), block);
1762 /* !old->expressions can happen when we deferred a block. */
1763 if (!old->expressions || !bitmap_set_equal (old, ANTIC_IN (block)))
1766 SET_BIT (changed_blocks, block->index);
1767 FOR_EACH_EDGE (e, ei, block->preds)
1768 SET_BIT (changed_blocks, e->src->index);
1771 RESET_BIT (changed_blocks, block->index);
1774 if (dump_file && (dump_flags & TDF_DETAILS))
1776 if (!BB_DEFERRED (block) || BB_VISITED (block))
1779 print_bitmap_set (dump_file, ANTIC_OUT, "ANTIC_OUT", block->index);
1781 print_bitmap_set (dump_file, ANTIC_IN (block), "ANTIC_IN",
1785 print_bitmap_set (dump_file, S, "S", block->index);
1790 "Block %d was deferred for a future iteration.\n",
1795 bitmap_set_free (old);
1797 bitmap_set_free (S);
1799 bitmap_set_free (ANTIC_OUT);
1803 /* Compute PARTIAL_ANTIC for BLOCK.
1805 If succs(BLOCK) > 1 then
1806 PA_OUT[BLOCK] = value wise union of PA_IN[b] + all ANTIC_IN not
1807 in ANTIC_OUT for all succ(BLOCK)
1808 else if succs(BLOCK) == 1 then
1809 PA_OUT[BLOCK] = phi_translate (PA_IN[succ(BLOCK)])
1811 PA_IN[BLOCK] = dependent_clean(PA_OUT[BLOCK] - TMP_GEN[BLOCK]
1816 compute_partial_antic_aux (basic_block block,
1817 bool block_has_abnormal_pred_edge)
1819 bool changed = false;
1820 bitmap_set_t old_PA_IN;
1821 bitmap_set_t PA_OUT;
1825 old_PA_IN = PA_OUT = NULL;
1827 /* If any edges from predecessors are abnormal, antic_in is empty,
1829 if (block_has_abnormal_pred_edge)
1830 goto maybe_dump_sets;
1832 old_PA_IN = PA_IN (block);
1833 PA_OUT = bitmap_set_new ();
1835 /* If the block has no successors, ANTIC_OUT is empty. */
1836 if (EDGE_COUNT (block->succs) == 0)
1838 /* If we have one successor, we could have some phi nodes to
1839 translate through. Note that we can't phi translate across DFS
1840 back edges in partial antic, because it uses a union operation on
1841 the successors. For recurrences like IV's, we will end up
1842 generating a new value in the set on each go around (i + 3 (VH.1)
1843 VH.1 + 1 (VH.2), VH.2 + 1 (VH.3), etc), forever. */
1844 else if (single_succ_p (block))
1846 basic_block succ = single_succ (block);
1847 if (!(single_succ_edge (block)->flags & EDGE_DFS_BACK))
1848 phi_translate_set (PA_OUT, PA_IN (succ), block, succ);
1850 /* If we have multiple successors, we take the union of all of
1854 VEC(basic_block, heap) * worklist;
1858 worklist = VEC_alloc (basic_block, heap, EDGE_COUNT (block->succs));
1859 FOR_EACH_EDGE (e, ei, block->succs)
1861 if (e->flags & EDGE_DFS_BACK)
1863 VEC_quick_push (basic_block, worklist, e->dest);
1865 if (VEC_length (basic_block, worklist) > 0)
1867 for (i = 0; VEC_iterate (basic_block, worklist, i, bprime); i++)
1872 FOR_EACH_EXPR_ID_IN_SET (ANTIC_IN (bprime), i, bi)
1873 bitmap_value_insert_into_set (PA_OUT,
1874 expression_for_id (i));
1875 if (phi_nodes (bprime))
1877 bitmap_set_t pa_in = bitmap_set_new ();
1878 phi_translate_set (pa_in, PA_IN (bprime), block, bprime);
1879 FOR_EACH_EXPR_ID_IN_SET (pa_in, i, bi)
1880 bitmap_value_insert_into_set (PA_OUT,
1881 expression_for_id (i));
1882 bitmap_set_free (pa_in);
1885 FOR_EACH_EXPR_ID_IN_SET (PA_IN (bprime), i, bi)
1886 bitmap_value_insert_into_set (PA_OUT,
1887 expression_for_id (i));
1890 VEC_free (basic_block, heap, worklist);
1893 /* PA_IN starts with PA_OUT - TMP_GEN.
1894 Then we subtract things from ANTIC_IN. */
1895 PA_IN (block) = bitmap_set_subtract (PA_OUT, TMP_GEN (block));
1897 /* For partial antic, we want to put back in the phi results, since
1898 we will properly avoid making them partially antic over backedges. */
1899 bitmap_ior_into (PA_IN (block)->values, PHI_GEN (block)->values);
1900 bitmap_ior_into (PA_IN (block)->expressions, PHI_GEN (block)->expressions);
1902 /* PA_IN[block] = PA_IN[block] - ANTIC_IN[block] */
1903 bitmap_set_subtract_values (PA_IN (block), ANTIC_IN (block));
1905 dependent_clean (PA_IN (block), ANTIC_IN (block), block);
1907 if (!bitmap_set_equal (old_PA_IN, PA_IN (block)))
1910 SET_BIT (changed_blocks, block->index);
1911 FOR_EACH_EDGE (e, ei, block->preds)
1912 SET_BIT (changed_blocks, e->src->index);
1915 RESET_BIT (changed_blocks, block->index);
1918 if (dump_file && (dump_flags & TDF_DETAILS))
1921 print_bitmap_set (dump_file, PA_OUT, "PA_OUT", block->index);
1923 print_bitmap_set (dump_file, PA_IN (block), "PA_IN", block->index);
1926 bitmap_set_free (old_PA_IN);
1928 bitmap_set_free (PA_OUT);
1932 /* Compute ANTIC and partial ANTIC sets. */
1935 compute_antic (void)
1937 bool changed = true;
1938 int num_iterations = 0;
1942 /* If any predecessor edges are abnormal, we punt, so antic_in is empty.
1943 We pre-build the map of blocks with incoming abnormal edges here. */
1944 has_abnormal_preds = sbitmap_alloc (last_basic_block);
1945 sbitmap_zero (has_abnormal_preds);
1952 FOR_EACH_EDGE (e, ei, block->preds)
1954 e->flags &= ~EDGE_DFS_BACK;
1955 if (e->flags & EDGE_ABNORMAL)
1957 SET_BIT (has_abnormal_preds, block->index);
1962 BB_VISITED (block) = 0;
1963 BB_DEFERRED (block) = 0;
1964 /* While we are here, give empty ANTIC_IN sets to each block. */
1965 ANTIC_IN (block) = bitmap_set_new ();
1966 PA_IN (block) = bitmap_set_new ();
1969 /* At the exit block we anticipate nothing. */
1970 ANTIC_IN (EXIT_BLOCK_PTR) = bitmap_set_new ();
1971 BB_VISITED (EXIT_BLOCK_PTR) = 1;
1972 PA_IN (EXIT_BLOCK_PTR) = bitmap_set_new ();
1974 changed_blocks = sbitmap_alloc (last_basic_block + 1);
1975 sbitmap_ones (changed_blocks);
1978 if (dump_file && (dump_flags & TDF_DETAILS))
1979 fprintf (dump_file, "Starting iteration %d\n", num_iterations);
1982 for (i = 0; i < last_basic_block - NUM_FIXED_BLOCKS; i++)
1984 if (TEST_BIT (changed_blocks, postorder[i]))
1986 basic_block block = BASIC_BLOCK (postorder[i]);
1987 changed |= compute_antic_aux (block,
1988 TEST_BIT (has_abnormal_preds,
1992 /* Theoretically possible, but *highly* unlikely. */
1993 gcc_assert (num_iterations < 50);
1996 if (dump_file && (dump_flags & TDF_STATS))
1997 fprintf (dump_file, "compute_antic required %d iterations\n",
2000 if (do_partial_partial)
2002 sbitmap_ones (changed_blocks);
2003 mark_dfs_back_edges ();
2008 if (dump_file && (dump_flags & TDF_DETAILS))
2009 fprintf (dump_file, "Starting iteration %d\n", num_iterations);
2012 for (i = 0; i < last_basic_block - NUM_FIXED_BLOCKS; i++)
2014 if (TEST_BIT (changed_blocks, postorder[i]))
2016 basic_block block = BASIC_BLOCK (postorder[i]);
2018 |= compute_partial_antic_aux (block,
2019 TEST_BIT (has_abnormal_preds,
2023 /* Theoretically possible, but *highly* unlikely. */
2024 gcc_assert (num_iterations < 50);
2026 if (dump_file && (dump_flags & TDF_STATS))
2027 fprintf (dump_file, "compute_partial_antic required %d iterations\n",
2030 sbitmap_free (has_abnormal_preds);
2031 sbitmap_free (changed_blocks);
2034 /* Return true if we can value number the call in STMT. This is true
2035 if we have a pure or constant call. */
2038 can_value_number_call (tree stmt)
2040 tree call = get_call_expr_in (stmt);
2042 if (call_expr_flags (call) & (ECF_PURE | ECF_CONST))
2047 /* Return true if OP is an exception handler related operation, such as
2048 FILTER_EXPRor EXC_PTR_EXPR. */
2051 is_exception_related (tree op)
2053 return TREE_CODE (op) == FILTER_EXPR || TREE_CODE (op) == EXC_PTR_EXPR;
2056 /* Return true if OP is a tree which we can perform value numbering
2060 can_value_number_operation (tree op)
2062 return (UNARY_CLASS_P (op)
2063 && !is_exception_related (TREE_OPERAND (op, 0)))
2064 || BINARY_CLASS_P (op)
2065 || COMPARISON_CLASS_P (op)
2066 || REFERENCE_CLASS_P (op)
2068 || (TREE_CODE (op) == CALL_EXPR
2069 && can_value_number_call (op));
2073 /* Return true if OP is a tree which we can perform PRE on
2074 on. This may not match the operations we can value number, but in
2075 a perfect world would. */
2078 can_PRE_operation (tree op)
2080 return UNARY_CLASS_P (op)
2081 || BINARY_CLASS_P (op)
2082 || COMPARISON_CLASS_P (op)
2084 || TREE_CODE (op) == INDIRECT_REF
2085 || TREE_CODE (op) == COMPONENT_REF
2086 || TREE_CODE (op) == CALL_EXPR
2087 || TREE_CODE (op) == ARRAY_REF;
2091 /* Inserted expressions are placed onto this worklist, which is used
2092 for performing quick dead code elimination of insertions we made
2093 that didn't turn out to be necessary. */
2094 static VEC(tree,heap) *inserted_exprs;
2096 /* Pool allocated fake store expressions are placed onto this
2097 worklist, which, after performing dead code elimination, is walked
2098 to see which expressions need to be put into GC'able memory */
2099 static VEC(tree, heap) *need_creation;
2101 /* For COMPONENT_REF's and ARRAY_REF's, we can't have any intermediates for the
2102 COMPONENT_REF or INDIRECT_REF or ARRAY_REF portion, because we'd end up with
2103 trying to rename aggregates into ssa form directly, which is a no
2106 Thus, this routine doesn't create temporaries, it just builds a
2107 single access expression for the array, calling
2108 find_or_generate_expression to build the innermost pieces.
2110 This function is a subroutine of create_expression_by_pieces, and
2111 should not be called on it's own unless you really know what you
2115 create_component_ref_by_pieces (basic_block block, tree expr, tree stmts)
2120 if (TREE_CODE (genop) == VALUE_HANDLE)
2122 tree found = bitmap_find_leader (AVAIL_OUT (block), expr);
2127 if (TREE_CODE (genop) == VALUE_HANDLE)
2129 bitmap_set_t exprset = VALUE_HANDLE_EXPR_SET (expr);
2130 unsigned int firstbit = bitmap_first_set_bit (exprset->expressions);
2131 genop = expression_for_id (firstbit);
2134 switch TREE_CODE (genop)
2140 op0 = create_component_ref_by_pieces (block,
2141 TREE_OPERAND (genop, 0),
2143 op1 = TREE_OPERAND (genop, 1);
2144 if (TREE_CODE (op1) == VALUE_HANDLE)
2145 op1 = find_or_generate_expression (block, op1, stmts);
2146 op2 = TREE_OPERAND (genop, 2);
2147 if (op2 && TREE_CODE (op2) == VALUE_HANDLE)
2148 op2 = find_or_generate_expression (block, op2, stmts);
2149 op3 = TREE_OPERAND (genop, 3);
2150 if (op3 && TREE_CODE (op3) == VALUE_HANDLE)
2151 op3 = find_or_generate_expression (block, op3, stmts);
2152 folded = build4 (ARRAY_REF, TREE_TYPE (genop), op0, op1,
2160 op0 = create_component_ref_by_pieces (block,
2161 TREE_OPERAND (genop, 0),
2163 /* op1 should be a FIELD_DECL, which are represented by
2165 op1 = TREE_OPERAND (genop, 1);
2166 folded = fold_build3 (COMPONENT_REF, TREE_TYPE (genop), op0, op1,
2173 tree op1 = TREE_OPERAND (genop, 0);
2174 tree genop1 = find_or_generate_expression (block, op1, stmts);
2176 folded = fold_build1 (TREE_CODE (genop), TREE_TYPE (genop),
2194 /* Find a leader for an expression, or generate one using
2195 create_expression_by_pieces if it's ANTIC but
2197 BLOCK is the basic_block we are looking for leaders in.
2198 EXPR is the expression to find a leader or generate for.
2199 STMTS is the statement list to put the inserted expressions on.
2200 Returns the SSA_NAME of the LHS of the generated expression or the
2204 find_or_generate_expression (basic_block block, tree expr, tree stmts)
2206 tree genop = bitmap_find_leader (AVAIL_OUT (block), expr);
2208 /* If it's still NULL, it must be a complex expression, so generate
2212 bitmap_set_t exprset = VALUE_HANDLE_EXPR_SET (expr);
2213 bool handled = false;
2217 /* We will hit cases where we have SSA_NAME's in exprset before
2218 other operations, because we may have come up with the SCCVN
2219 value before getting to the RHS of the expression. */
2220 FOR_EACH_EXPR_ID_IN_SET (exprset, i, bi)
2222 genop = expression_for_id (i);
2223 if (can_PRE_operation (genop))
2226 genop = create_expression_by_pieces (block, genop, stmts);
2230 gcc_assert (handled);
2235 #define NECESSARY(stmt) stmt->base.asm_written_flag
2236 /* Create an expression in pieces, so that we can handle very complex
2237 expressions that may be ANTIC, but not necessary GIMPLE.
2238 BLOCK is the basic block the expression will be inserted into,
2239 EXPR is the expression to insert (in value form)
2240 STMTS is a statement list to append the necessary insertions into.
2242 This function will die if we hit some value that shouldn't be
2243 ANTIC but is (IE there is no leader for it, or its components).
2244 This function may also generate expressions that are themselves
2245 partially or fully redundant. Those that are will be either made
2246 fully redundant during the next iteration of insert (for partially
2247 redundant ones), or eliminated by eliminate (for fully redundant
2251 create_expression_by_pieces (basic_block block, tree expr, tree stmts)
2254 tree folded, forced_stmts, newexpr;
2256 tree_stmt_iterator tsi;
2258 switch (TREE_CODE_CLASS (TREE_CODE (expr)))
2267 gcc_assert (TREE_CODE (expr) == CALL_EXPR);
2269 fn = CALL_EXPR_FN (expr);
2270 sc = CALL_EXPR_STATIC_CHAIN (expr);
2272 genfn = find_or_generate_expression (block, fn, stmts);
2274 nargs = call_expr_nargs (expr);
2275 buffer = (tree*) alloca (nargs * sizeof (tree));
2277 for (i = 0; i < nargs; i++)
2279 tree arg = CALL_EXPR_ARG (expr, i);
2280 buffer[i] = find_or_generate_expression (block, arg, stmts);
2283 folded = build_call_array (TREE_TYPE (expr), genfn, nargs, buffer);
2285 CALL_EXPR_STATIC_CHAIN (folded) =
2286 find_or_generate_expression (block, sc, stmts);
2287 folded = fold (folded);
2293 if (TREE_CODE (expr) == COMPONENT_REF
2294 || TREE_CODE (expr) == ARRAY_REF)
2296 folded = create_component_ref_by_pieces (block, expr, stmts);
2300 tree op1 = TREE_OPERAND (expr, 0);
2301 tree genop1 = find_or_generate_expression (block, op1, stmts);
2303 folded = fold_build1 (TREE_CODE (expr), TREE_TYPE (expr),
2310 case tcc_comparison:
2312 tree op1 = TREE_OPERAND (expr, 0);
2313 tree op2 = TREE_OPERAND (expr, 1);
2314 tree genop1 = find_or_generate_expression (block, op1, stmts);
2315 tree genop2 = find_or_generate_expression (block, op2, stmts);
2316 folded = fold_build2 (TREE_CODE (expr), TREE_TYPE (expr),
2320 case tcc_declaration:
2322 /* Get the "shared" version of the DECL, that we didn't create
2324 folded = referenced_var_lookup (DECL_UID (expr));
2330 tree op1 = TREE_OPERAND (expr, 0);
2331 tree genop1 = find_or_generate_expression (block, op1, stmts);
2332 folded = fold_build1 (TREE_CODE (expr), TREE_TYPE (expr),
2341 /* Force the generated expression to be a sequence of GIMPLE
2343 We have to call unshare_expr because force_gimple_operand may
2344 modify the tree we pass to it. */
2345 newexpr = force_gimple_operand (unshare_expr (folded), &forced_stmts,
2348 /* If we have any intermediate expressions to the value sets, add them
2349 to the value sets and chain them on in the instruction stream. */
2352 tsi = tsi_start (forced_stmts);
2353 for (; !tsi_end_p (tsi); tsi_next (&tsi))
2355 tree stmt = tsi_stmt (tsi);
2356 tree forcedname = GIMPLE_STMT_OPERAND (stmt, 0);
2357 tree forcedexpr = GIMPLE_STMT_OPERAND (stmt, 1);
2358 tree val = vn_lookup_or_add (forcedexpr);
2360 VEC_safe_push (tree, heap, inserted_exprs, stmt);
2361 VN_INFO_GET (forcedname)->valnum = forcedname;
2362 vn_add (forcedname, val);
2363 bitmap_value_replace_in_set (NEW_SETS (block), forcedname);
2364 bitmap_value_replace_in_set (AVAIL_OUT (block), forcedname);
2365 mark_symbols_for_renaming (stmt);
2367 tsi = tsi_last (stmts);
2368 tsi_link_after (&tsi, forced_stmts, TSI_CONTINUE_LINKING);
2371 /* Build and insert the assignment of the end result to the temporary
2372 that we will return. */
2373 if (!pretemp || TREE_TYPE (expr) != TREE_TYPE (pretemp))
2375 pretemp = create_tmp_var (TREE_TYPE (expr), "pretmp");
2376 get_var_ann (pretemp);
2380 add_referenced_var (temp);
2382 if (TREE_CODE (TREE_TYPE (expr)) == COMPLEX_TYPE
2383 || TREE_CODE (TREE_TYPE (expr)) == VECTOR_TYPE)
2384 DECL_GIMPLE_REG_P (temp) = 1;
2386 newexpr = build_gimple_modify_stmt (temp, newexpr);
2387 name = make_ssa_name (temp, newexpr);
2388 GIMPLE_STMT_OPERAND (newexpr, 0) = name;
2389 NECESSARY (newexpr) = 0;
2391 tsi = tsi_last (stmts);
2392 tsi_link_after (&tsi, newexpr, TSI_CONTINUE_LINKING);
2393 VEC_safe_push (tree, heap, inserted_exprs, newexpr);
2395 /* All the symbols in NEWEXPR should be put into SSA form. */
2396 mark_symbols_for_renaming (newexpr);
2398 /* Add a value handle to the temporary.
2399 The value may already exist in either NEW_SETS, or AVAIL_OUT, because
2400 we are creating the expression by pieces, and this particular piece of
2401 the expression may have been represented. There is no harm in replacing
2403 v = get_value_handle (expr);
2405 VN_INFO_GET (name)->valnum = name;
2406 get_or_alloc_expression_id (name);
2407 bitmap_value_replace_in_set (NEW_SETS (block), name);
2408 bitmap_value_replace_in_set (AVAIL_OUT (block), name);
2410 pre_stats.insertions++;
2411 if (dump_file && (dump_flags & TDF_DETAILS))
2413 fprintf (dump_file, "Inserted ");
2414 print_generic_expr (dump_file, newexpr, 0);
2415 fprintf (dump_file, " in predecessor %d\n", block->index);
2421 /* Insert the to-be-made-available values of expression EXPRNUM for each
2422 predecessor, stored in AVAIL, into the predecessors of BLOCK, and
2423 merge the result with a phi node, given the same value handle as
2424 NODE. Return true if we have inserted new stuff. */
2427 insert_into_preds_of_block (basic_block block, unsigned int exprnum,
2430 tree expr = expression_for_id (exprnum);
2431 tree val = get_value_handle (expr);
2433 bool insertions = false;
2438 tree type = TREE_TYPE (avail[EDGE_PRED (block, 0)->src->index]);
2441 if (dump_file && (dump_flags & TDF_DETAILS))
2443 fprintf (dump_file, "Found partial redundancy for expression ");
2444 print_generic_expr (dump_file, expr, 0);
2445 fprintf (dump_file, " (");
2446 print_generic_expr (dump_file, val, 0);
2447 fprintf (dump_file, ")");
2448 fprintf (dump_file, "\n");
2451 /* Make sure we aren't creating an induction variable. */
2452 if (block->loop_depth > 0 && EDGE_COUNT (block->preds) == 2
2453 && TREE_CODE_CLASS (TREE_CODE (expr)) != tcc_reference )
2455 bool firstinsideloop = false;
2456 bool secondinsideloop = false;
2457 firstinsideloop = flow_bb_inside_loop_p (block->loop_father,
2458 EDGE_PRED (block, 0)->src);
2459 secondinsideloop = flow_bb_inside_loop_p (block->loop_father,
2460 EDGE_PRED (block, 1)->src);
2461 /* Induction variables only have one edge inside the loop. */
2462 if (firstinsideloop ^ secondinsideloop)
2464 if (dump_file && (dump_flags & TDF_DETAILS))
2465 fprintf (dump_file, "Skipping insertion of phi for partial redundancy: Looks like an induction variable\n");
2471 /* Make the necessary insertions. */
2472 FOR_EACH_EDGE (pred, ei, block->preds)
2474 tree stmts = alloc_stmt_list ();
2477 eprime = avail[bprime->index];
2479 if (can_PRE_operation (eprime))
2481 builtexpr = create_expression_by_pieces (bprime,
2484 gcc_assert (!(pred->flags & EDGE_ABNORMAL));
2485 bsi_insert_on_edge (pred, stmts);
2486 avail[bprime->index] = builtexpr;
2490 /* If we didn't want a phi node, and we made insertions, we still have
2491 inserted new stuff, and thus return true. If we didn't want a phi node,
2492 and didn't make insertions, we haven't added anything new, so return
2494 if (nophi && insertions)
2496 else if (nophi && !insertions)
2499 /* Now build a phi for the new variable. */
2500 if (!prephitemp || TREE_TYPE (prephitemp) != type)
2502 prephitemp = create_tmp_var (type, "prephitmp");
2503 get_var_ann (prephitemp);
2507 add_referenced_var (temp);
2510 if (TREE_CODE (type) == COMPLEX_TYPE
2511 || TREE_CODE (type) == VECTOR_TYPE)
2512 DECL_GIMPLE_REG_P (temp) = 1;
2513 temp = create_phi_node (temp, block);
2515 NECESSARY (temp) = 0;
2516 VN_INFO_GET (PHI_RESULT (temp))->valnum = PHI_RESULT (temp);
2518 VEC_safe_push (tree, heap, inserted_exprs, temp);
2519 FOR_EACH_EDGE (pred, ei, block->preds)
2520 add_phi_arg (temp, avail[pred->src->index], pred);
2522 vn_add (PHI_RESULT (temp), val);
2524 /* The value should *not* exist in PHI_GEN, or else we wouldn't be doing
2525 this insertion, since we test for the existence of this value in PHI_GEN
2526 before proceeding with the partial redundancy checks in insert_aux.
2528 The value may exist in AVAIL_OUT, in particular, it could be represented
2529 by the expression we are trying to eliminate, in which case we want the
2530 replacement to occur. If it's not existing in AVAIL_OUT, we want it
2533 Similarly, to the PHI_GEN case, the value should not exist in NEW_SETS of
2534 this block, because if it did, it would have existed in our dominator's
2535 AVAIL_OUT, and would have been skipped due to the full redundancy check.
2538 bitmap_insert_into_set (PHI_GEN (block),
2540 bitmap_value_replace_in_set (AVAIL_OUT (block),
2542 bitmap_insert_into_set (NEW_SETS (block),
2545 if (dump_file && (dump_flags & TDF_DETAILS))
2547 fprintf (dump_file, "Created phi ");
2548 print_generic_expr (dump_file, temp, 0);
2549 fprintf (dump_file, " in block %d\n", block->index);
2557 /* Perform insertion of partially redundant values.
2558 For BLOCK, do the following:
2559 1. Propagate the NEW_SETS of the dominator into the current block.
2560 If the block has multiple predecessors,
2561 2a. Iterate over the ANTIC expressions for the block to see if
2562 any of them are partially redundant.
2563 2b. If so, insert them into the necessary predecessors to make
2564 the expression fully redundant.
2565 2c. Insert a new PHI merging the values of the predecessors.
2566 2d. Insert the new PHI, and the new expressions, into the
2568 3. Recursively call ourselves on the dominator children of BLOCK.
2570 Steps 1, 2a, and 3 are done by insert_aux. 2b, 2c and 2d are done by
2571 do_regular_insertion and do_partial_insertion.
2576 do_regular_insertion (basic_block block, basic_block dom)
2578 bool new_stuff = false;
2579 VEC (tree, heap) *exprs = sorted_array_from_bitmap_set (ANTIC_IN (block));
2583 for (i = 0; VEC_iterate (tree, exprs, i, expr); i++)
2585 if (can_PRE_operation (expr) && !AGGREGATE_TYPE_P (TREE_TYPE (expr)))
2589 bool by_some = false;
2590 bool cant_insert = false;
2591 bool all_same = true;
2592 tree first_s = NULL;
2595 tree eprime = NULL_TREE;
2598 val = get_value_handle (expr);
2599 if (bitmap_set_contains_value (PHI_GEN (block), val))
2601 if (bitmap_set_contains_value (AVAIL_OUT (dom), val))
2603 if (dump_file && (dump_flags & TDF_DETAILS))
2604 fprintf (dump_file, "Found fully redundant value\n");
2608 avail = XCNEWVEC (tree, last_basic_block);
2609 FOR_EACH_EDGE (pred, ei, block->preds)
2614 /* This can happen in the very weird case
2615 that our fake infinite loop edges have caused a
2616 critical edge to appear. */
2617 if (EDGE_CRITICAL_P (pred))
2623 eprime = phi_translate (expr, ANTIC_IN (block), NULL,
2626 /* eprime will generally only be NULL if the
2627 value of the expression, translated
2628 through the PHI for this predecessor, is
2629 undefined. If that is the case, we can't
2630 make the expression fully redundant,
2631 because its value is undefined along a
2632 predecessor path. We can thus break out
2633 early because it doesn't matter what the
2634 rest of the results are. */
2641 eprime = fully_constant_expression (eprime);
2642 vprime = get_value_handle (eprime);
2643 gcc_assert (vprime);
2644 edoubleprime = bitmap_find_leader (AVAIL_OUT (bprime),
2646 if (edoubleprime == NULL)
2648 avail[bprime->index] = eprime;
2653 avail[bprime->index] = edoubleprime;
2655 if (first_s == NULL)
2656 first_s = edoubleprime;
2657 else if (!operand_equal_p (first_s, edoubleprime,
2662 /* If we can insert it, it's not the same value
2663 already existing along every predecessor, and
2664 it's defined by some predecessor, it is
2665 partially redundant. */
2666 if (!cant_insert && !all_same && by_some)
2668 if (insert_into_preds_of_block (block, get_expression_id (expr),
2672 /* If all edges produce the same value and that value is
2673 an invariant, then the PHI has the same value on all
2674 edges. Note this. */
2675 else if (!cant_insert && all_same && eprime
2676 && is_gimple_min_invariant (eprime)
2677 && !is_gimple_min_invariant (val))
2682 bitmap_set_t exprset = VALUE_HANDLE_EXPR_SET (val);
2683 FOR_EACH_EXPR_ID_IN_SET (exprset, j, bi)
2685 tree expr = expression_for_id (j);
2686 if (TREE_CODE (expr) == SSA_NAME)
2688 vn_add (expr, eprime);
2689 pre_stats.constified++;
2697 VEC_free (tree, heap, exprs);
2702 /* Perform insertion for partially anticipatable expressions. There
2703 is only one case we will perform insertion for these. This case is
2704 if the expression is partially anticipatable, and fully available.
2705 In this case, we know that putting it earlier will enable us to
2706 remove the later computation. */
2710 do_partial_partial_insertion (basic_block block, basic_block dom)
2712 bool new_stuff = false;
2713 VEC (tree, heap) *exprs = sorted_array_from_bitmap_set (PA_IN (block));
2717 for (i = 0; VEC_iterate (tree, exprs, i, expr); i++)
2719 if (can_PRE_operation (expr) && !AGGREGATE_TYPE_P (TREE_TYPE (expr)))
2724 bool cant_insert = false;
2727 tree eprime = NULL_TREE;
2730 val = get_value_handle (expr);
2731 if (bitmap_set_contains_value (PHI_GEN (block), val))
2733 if (bitmap_set_contains_value (AVAIL_OUT (dom), val))
2736 avail = XCNEWVEC (tree, last_basic_block);
2737 FOR_EACH_EDGE (pred, ei, block->preds)
2742 /* This can happen in the very weird case
2743 that our fake infinite loop edges have caused a
2744 critical edge to appear. */
2745 if (EDGE_CRITICAL_P (pred))
2751 eprime = phi_translate (expr, ANTIC_IN (block),
2755 /* eprime will generally only be NULL if the
2756 value of the expression, translated
2757 through the PHI for this predecessor, is
2758 undefined. If that is the case, we can't
2759 make the expression fully redundant,
2760 because its value is undefined along a
2761 predecessor path. We can thus break out
2762 early because it doesn't matter what the
2763 rest of the results are. */
2770 eprime = fully_constant_expression (eprime);
2771 vprime = get_value_handle (eprime);
2772 gcc_assert (vprime);
2773 edoubleprime = bitmap_find_leader (AVAIL_OUT (bprime),
2775 if (edoubleprime == NULL)
2781 avail[bprime->index] = edoubleprime;
2785 /* If we can insert it, it's not the same value
2786 already existing along every predecessor, and
2787 it's defined by some predecessor, it is
2788 partially redundant. */
2789 if (!cant_insert && by_all)
2791 pre_stats.pa_insert++;
2792 if (insert_into_preds_of_block (block, get_expression_id (expr),
2800 VEC_free (tree, heap, exprs);
2805 insert_aux (basic_block block)
2808 bool new_stuff = false;
2813 dom = get_immediate_dominator (CDI_DOMINATORS, block);
2818 bitmap_set_t newset = NEW_SETS (dom);
2821 /* Note that we need to value_replace both NEW_SETS, and
2822 AVAIL_OUT. For both the case of NEW_SETS, the value may be
2823 represented by some non-simple expression here that we want
2824 to replace it with. */
2825 FOR_EACH_EXPR_ID_IN_SET (newset, i, bi)
2827 tree expr = expression_for_id (i);
2828 bitmap_value_replace_in_set (NEW_SETS (block), expr);
2829 bitmap_value_replace_in_set (AVAIL_OUT (block), expr);
2832 if (!single_pred_p (block))
2834 new_stuff |= do_regular_insertion (block, dom);
2835 if (do_partial_partial)
2836 new_stuff |= do_partial_partial_insertion (block, dom);
2840 for (son = first_dom_son (CDI_DOMINATORS, block);
2842 son = next_dom_son (CDI_DOMINATORS, son))
2844 new_stuff |= insert_aux (son);
2850 /* Perform insertion of partially redundant values. */
2855 bool new_stuff = true;
2857 int num_iterations = 0;
2860 NEW_SETS (bb) = bitmap_set_new ();
2866 new_stuff = insert_aux (ENTRY_BLOCK_PTR);
2868 if (num_iterations > 2 && dump_file && (dump_flags & TDF_STATS))
2869 fprintf (dump_file, "insert required %d iterations\n", num_iterations);
2873 /* Return true if VAR is an SSA variable with no defining statement in
2874 this procedure, *AND* isn't a live-on-entry parameter. */
2877 is_undefined_value (tree expr)
2879 return (TREE_CODE (expr) == SSA_NAME
2880 && IS_EMPTY_STMT (SSA_NAME_DEF_STMT (expr))
2881 /* PARM_DECLs and hard registers are always defined. */
2882 && TREE_CODE (SSA_NAME_VAR (expr)) != PARM_DECL);
2885 /* Add OP to EXP_GEN (block), and possibly to the maximal set if it is
2886 not defined by a phi node.
2887 PHI nodes can't go in the maximal sets because they are not in
2888 TMP_GEN, so it is possible to get into non-monotonic situations
2889 during ANTIC calculation, because it will *add* bits. */
2892 add_to_exp_gen (basic_block block, tree op)
2896 if (TREE_CODE (op) == SSA_NAME && is_undefined_value (op))
2898 bitmap_value_insert_into_set (EXP_GEN (block), op);
2899 if (TREE_CODE (op) != SSA_NAME
2900 || TREE_CODE (SSA_NAME_DEF_STMT (op)) != PHI_NODE)
2901 bitmap_value_insert_into_set (maximal_set, op);
2906 /* Given an SSA variable VAR and an expression EXPR, compute the value
2907 number for EXPR and create a value handle (VAL) for it. If VAR and
2908 EXPR are not the same, associate VAL with VAR. Finally, add VAR to
2909 S1 and its value handle to S2, and to the maximal set if
2910 ADD_TO_MAXIMAL is true.
2912 VUSES represent the virtual use operands associated with EXPR (if
2916 add_to_sets (tree var, tree expr, tree stmt, bitmap_set_t s1,
2920 val = vn_lookup_or_add_with_stmt (expr, stmt);
2922 /* VAR and EXPR may be the same when processing statements for which
2923 we are not computing value numbers (e.g., non-assignments, or
2924 statements that make aliased stores). In those cases, we are
2925 only interested in making VAR available as its own value. */
2930 bitmap_insert_into_set (s1, var);
2932 bitmap_value_insert_into_set (s2, var);
2935 /* Find existing value expression that is the same as T,
2936 and return it if it exists. */
2939 find_existing_value_expr (tree t, tree stmt)
2944 bitmap_set_t exprset;
2946 if (REFERENCE_CLASS_P (t) || TREE_CODE (t) == CALL_EXPR || DECL_P (t))
2947 vh = vn_lookup_with_stmt (t, stmt);
2953 exprset = VALUE_HANDLE_EXPR_SET (vh);
2954 FOR_EACH_EXPR_ID_IN_SET (exprset, bii, bi)
2956 tree efi = expression_for_id (bii);
2957 if (expressions_equal_p (t, efi))
2963 /* Given a unary or binary expression EXPR, create and return a new
2964 expression with the same structure as EXPR but with its operands
2965 replaced with the value handles of each of the operands of EXPR.
2967 VUSES represent the virtual use operands associated with EXPR (if
2968 any). Insert EXPR's operands into the EXP_GEN set for BLOCK.
2970 TOP_LEVEL is true if we are at the top of the original
2971 expression. This is used to differentiate between addressing and
2972 actual loads of globals. IE a = t vs a = t[0]. */
2975 create_value_expr_from (tree expr, basic_block block, tree stmt,
2979 enum tree_code code = TREE_CODE (expr);
2981 alloc_pool pool = NULL;
2984 gcc_assert (TREE_CODE_CLASS (code) == tcc_unary
2985 || TREE_CODE_CLASS (code) == tcc_binary
2986 || TREE_CODE_CLASS (code) == tcc_comparison
2987 || TREE_CODE_CLASS (code) == tcc_reference
2988 || TREE_CODE_CLASS (code) == tcc_expression
2989 || TREE_CODE_CLASS (code) == tcc_vl_exp
2990 || TREE_CODE_CLASS (code) == tcc_exceptional
2991 || TREE_CODE_CLASS (code) == tcc_declaration);
2993 if (TREE_CODE_CLASS (code) == tcc_unary)
2994 pool = unary_node_pool;
2995 else if (TREE_CODE_CLASS (code) == tcc_reference)
2996 pool = reference_node_pool;
2997 else if (TREE_CODE_CLASS (code) == tcc_binary)
2998 pool = binary_node_pool;
2999 else if (TREE_CODE_CLASS (code) == tcc_comparison)
3000 pool = comparison_node_pool;
3001 else if (TREE_CODE_CLASS (code) == tcc_declaration)
3002 pool = decl_node_pool;
3004 gcc_assert (code == CALL_EXPR);
3006 if (code == CALL_EXPR)
3007 vexpr = temp_copy_call_expr (expr);
3010 vexpr = (tree) pool_alloc (pool);
3011 memcpy (vexpr, expr, tree_size (expr));
3014 for (i = 0; i < TREE_OPERAND_LENGTH (expr); i++)
3016 tree val = NULL_TREE;
3022 op = TREE_OPERAND (expr, i);
3023 if (op == NULL_TREE)
3026 /* Recursively value-numberize reference ops and tree lists. */
3027 if (REFERENCE_CLASS_P (op))
3029 tree tempop = create_value_expr_from (op, block, stmt, false);
3030 op = tempop ? tempop : op;
3031 val = vn_lookup_or_add_with_stmt (op, stmt);
3035 val = vn_lookup_or_add (op);
3037 if (TREE_CODE (op) != TREE_LIST)
3038 add_to_exp_gen (block, op);
3040 if (TREE_CODE (val) == VALUE_HANDLE)
3041 TREE_TYPE (val) = TREE_TYPE (TREE_OPERAND (vexpr, i));
3043 TREE_OPERAND (vexpr, i) = val;
3045 efi = find_existing_value_expr (vexpr, stmt);
3048 get_or_alloc_expression_id (vexpr);
3052 /* Return a copy of NODE that is stored in the temporary alloc_pool's.
3053 This is made recursively true, so that the operands are stored in
3054 the pool as well. */
3057 poolify_tree (tree node)
3059 switch (TREE_CODE (node))
3063 tree temp = (tree) pool_alloc (reference_node_pool);
3064 memcpy (temp, node, tree_size (node));
3065 TREE_OPERAND (temp, 0) = poolify_tree (TREE_OPERAND (temp, 0));
3069 case GIMPLE_MODIFY_STMT:
3071 tree temp = (tree) pool_alloc (modify_expr_node_pool);
3072 memcpy (temp, node, tree_size (node));
3073 GIMPLE_STMT_OPERAND (temp, 0) =
3074 poolify_tree (GIMPLE_STMT_OPERAND (temp, 0));
3075 GIMPLE_STMT_OPERAND (temp, 1) =
3076 poolify_tree (GIMPLE_STMT_OPERAND (temp, 1));
3095 static tree modify_expr_template;
3097 /* Allocate a GIMPLE_MODIFY_STMT with TYPE, and operands OP1, OP2 in the
3098 alloc pools and return it. */
3100 poolify_modify_stmt (tree op1, tree op2)
3102 if (modify_expr_template == NULL)
3103 modify_expr_template = build_gimple_modify_stmt (op1, op2);
3105 GIMPLE_STMT_OPERAND (modify_expr_template, 0) = op1;
3106 GIMPLE_STMT_OPERAND (modify_expr_template, 1) = op2;
3108 return poolify_tree (modify_expr_template);
3112 /* For each real store operation of the form
3113 *a = <value> that we see, create a corresponding fake store of the
3114 form storetmp_<version> = *a.
3116 This enables AVAIL computation to mark the results of stores as
3117 available. Without this, you'd need to do some computation to
3118 mark the result of stores as ANTIC and AVAIL at all the right
3120 To save memory, we keep the store
3121 statements pool allocated until we decide whether they are
3122 necessary or not. */
3125 insert_fake_stores (void)
3131 block_stmt_iterator bsi;
3132 for (bsi = bsi_start (block); !bsi_end_p (bsi); bsi_next (&bsi))
3134 tree stmt = bsi_stmt (bsi);
3136 /* We can't generate SSA names for stores that are complex
3137 or aggregate. We also want to ignore things whose
3138 virtual uses occur in abnormal phis. */
3140 if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT
3141 && TREE_CODE (GIMPLE_STMT_OPERAND (stmt, 0)) == INDIRECT_REF
3142 && !AGGREGATE_TYPE_P (TREE_TYPE (GIMPLE_STMT_OPERAND (stmt, 0)))
3143 && TREE_CODE (TREE_TYPE (GIMPLE_STMT_OPERAND
3144 (stmt, 0))) != COMPLEX_TYPE)
3148 tree lhs = GIMPLE_STMT_OPERAND (stmt, 0);
3149 tree rhs = GIMPLE_STMT_OPERAND (stmt, 1);
3151 bool notokay = false;
3153 FOR_EACH_SSA_DEF_OPERAND (defp, stmt, iter, SSA_OP_VIRTUAL_DEFS)
3155 tree defvar = DEF_FROM_PTR (defp);
3156 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (defvar))
3166 if (!storetemp || TREE_TYPE (rhs) != TREE_TYPE (storetemp))
3168 storetemp = create_tmp_var (TREE_TYPE (rhs), "storetmp");
3169 if (TREE_CODE (TREE_TYPE (storetemp)) == VECTOR_TYPE)
3170 DECL_GIMPLE_REG_P (storetemp) = 1;
3171 get_var_ann (storetemp);
3174 new_tree = poolify_modify_stmt (storetemp, lhs);
3176 lhs = make_ssa_name (storetemp, new_tree);
3177 GIMPLE_STMT_OPERAND (new_tree, 0) = lhs;
3178 create_ssa_artificial_load_stmt (new_tree, stmt);
3180 NECESSARY (new_tree) = 0;
3181 VEC_safe_push (tree, heap, inserted_exprs, new_tree);
3182 VEC_safe_push (tree, heap, need_creation, new_tree);
3183 bsi_insert_after (&bsi, new_tree, BSI_NEW_STMT);
3189 /* Turn the pool allocated fake stores that we created back into real
3190 GC allocated ones if they turned out to be necessary to PRE some
3194 realify_fake_stores (void)
3199 for (i = 0; VEC_iterate (tree, need_creation, i, stmt); i++)
3201 if (NECESSARY (stmt))
3203 block_stmt_iterator bsi;
3206 /* Mark the temp variable as referenced */
3207 add_referenced_var (SSA_NAME_VAR (GIMPLE_STMT_OPERAND (stmt, 0)));
3209 /* Put the new statement in GC memory, fix up the
3210 SSA_NAME_DEF_STMT on it, and then put it in place of
3211 the old statement before the store in the IR stream
3212 as a plain ssa name copy. */
3213 bsi = bsi_for_stmt (stmt);
3215 tmp = GIMPLE_STMT_OPERAND (bsi_stmt (bsi), 1);
3216 newstmt = build_gimple_modify_stmt (GIMPLE_STMT_OPERAND (stmt, 0),
3218 SSA_NAME_DEF_STMT (GIMPLE_STMT_OPERAND (newstmt, 0)) = newstmt;
3219 bsi_insert_before (&bsi, newstmt, BSI_SAME_STMT);
3220 bsi = bsi_for_stmt (stmt);
3221 bsi_remove (&bsi, true);
3224 release_defs (stmt);
3228 /* Given an SSA_NAME, see if SCCVN has a value number for it, and if
3229 so, return the value handle for this value number, creating it if
3231 Return NULL if SCCVN has no info for us. */
3234 get_sccvn_value (tree name)
3236 if (TREE_CODE (name) == SSA_NAME
3237 && VN_INFO (name)->valnum != name
3238 && VN_INFO (name)->valnum != VN_TOP)
3240 tree val = VN_INFO (name)->valnum;
3241 bool is_invariant = is_gimple_min_invariant (val);
3242 tree valvh = !is_invariant ? get_value_handle (val) : NULL_TREE;
3244 /* We may end up with situations where SCCVN has chosen a
3245 representative for the equivalence set that we have not
3246 visited yet. In this case, just create the value handle for
3248 if (!valvh && !is_invariant)
3250 tree defstmt = SSA_NAME_DEF_STMT (val);
3252 gcc_assert (VN_INFO (val)->valnum == val);
3253 /* PHI nodes can't have vuses and attempts to iterate over
3254 their VUSE operands will crash. */
3255 if (TREE_CODE (defstmt) == PHI_NODE || IS_EMPTY_STMT (defstmt))
3258 tree defstmt2 = SSA_NAME_DEF_STMT (name);
3259 if (TREE_CODE (defstmt2) != PHI_NODE &&
3260 !ZERO_SSA_OPERANDS (defstmt2, SSA_OP_ALL_VIRTUALS))
3261 gcc_assert (defstmt);
3263 valvh = vn_lookup_or_add_with_stmt (val, defstmt);
3266 if (dump_file && (dump_flags & TDF_DETAILS))
3268 fprintf (dump_file, "SCCVN says ");
3269 print_generic_expr (dump_file, name, 0);
3270 fprintf (dump_file, " value numbers to ");
3271 if (valvh && !is_invariant)
3273 print_generic_expr (dump_file, val, 0);
3274 fprintf (dump_file, " (");
3275 print_generic_expr (dump_file, valvh, 0);
3276 fprintf (dump_file, ")\n");
3279 print_generic_stmt (dump_file, val, 0);
3289 /* Create value handles for PHI in BLOCK. */
3292 make_values_for_phi (tree phi, basic_block block)
3294 tree result = PHI_RESULT (phi);
3295 /* We have no need for virtual phis, as they don't represent
3296 actual computations. */
3297 if (is_gimple_reg (result))
3299 tree sccvnval = get_sccvn_value (result);
3302 vn_add (result, sccvnval);
3304 bitmap_insert_into_set (PHI_GEN (block), result);
3305 bitmap_value_insert_into_set (AVAIL_OUT (block), result);
3308 add_to_sets (result, result, NULL,
3309 PHI_GEN (block), AVAIL_OUT (block));
3313 /* Return true if both the statement and the value handles have no
3314 vuses, or both the statement and the value handle do have vuses.
3316 Unlike SCCVN, PRE needs not only to know equivalence, but what the
3317 actual vuses are so it can translate them through blocks. Thus,
3318 we have to make a new value handle if the existing one has no
3319 vuses but needs them. */
3322 vuse_equiv (tree vh1, tree stmt)
3324 bool stmt_has_vuses = !ZERO_SSA_OPERANDS (stmt, SSA_OP_VIRTUAL_USES);
3325 return (VALUE_HANDLE_VUSES (vh1) && stmt_has_vuses)
3326 || (!VALUE_HANDLE_VUSES (vh1) && !stmt_has_vuses);
3329 /* Create value handles for STMT in BLOCK. Return true if we handled
3333 make_values_for_stmt (tree stmt, basic_block block)
3336 tree lhs = GIMPLE_STMT_OPERAND (stmt, 0);
3337 tree rhs = GIMPLE_STMT_OPERAND (stmt, 1);
3338 tree valvh = NULL_TREE;
3341 valvh = get_sccvn_value (lhs);
3344 vn_add (lhs, valvh);
3345 bitmap_value_insert_into_set (AVAIL_OUT (block), lhs);
3346 /* Shortcut for FRE. We have no need to create value expressions,
3347 just want to know what values are available where. */
3354 /* For FRE, if SCCVN didn't find anything, we aren't going to
3355 either, so just make up a new value number if necessary and
3357 if (get_value_handle (lhs) == NULL)
3358 vn_lookup_or_add (lhs);
3359 bitmap_value_insert_into_set (AVAIL_OUT (block), lhs);
3363 lhsval = valvh ? valvh : get_value_handle (lhs);
3365 STRIP_USELESS_TYPE_CONVERSION (rhs);
3366 if (can_value_number_operation (rhs)
3367 && (!lhsval || !is_gimple_min_invariant (lhsval)))
3369 /* For value numberable operation, create a
3370 duplicate expression with the operands replaced
3371 with the value handles of the original RHS. */
3372 tree newt = create_value_expr_from (rhs, block, stmt, true);
3375 /* If we already have a value number for the LHS, reuse
3376 it rather than creating a new one. */
3377 if (lhsval && vuse_equiv (lhsval, stmt))
3379 set_value_handle (newt, lhsval);
3380 if (!is_gimple_min_invariant (lhsval))
3381 add_to_value (lhsval, newt);
3385 tree val = vn_lookup_or_add_with_stmt (newt, stmt);
3389 add_to_exp_gen (block, newt);
3392 bitmap_insert_into_set (TMP_GEN (block), lhs);
3393 bitmap_value_insert_into_set (AVAIL_OUT (block), lhs);
3396 else if ((TREE_CODE (rhs) == SSA_NAME
3397 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs))
3398 || is_gimple_min_invariant (rhs)
3399 || TREE_CODE (rhs) == ADDR_EXPR
3400 || TREE_INVARIANT (rhs))
3405 set_value_handle (rhs, lhsval);
3406 if (!is_gimple_min_invariant (lhsval))
3407 add_to_value (lhsval, rhs);
3408 bitmap_insert_into_set (TMP_GEN (block), lhs);
3409 bitmap_value_insert_into_set (AVAIL_OUT (block), lhs);
3413 /* Compute a value number for the RHS of the statement
3414 and add its value to the AVAIL_OUT set for the block.
3415 Add the LHS to TMP_GEN. */
3416 add_to_sets (lhs, rhs, stmt, TMP_GEN (block),
3419 /* None of the rest of these can be PRE'd. */
3420 if (TREE_CODE (rhs) == SSA_NAME && !is_undefined_value (rhs))
3421 add_to_exp_gen (block, rhs);
3428 /* Compute the AVAIL set for all basic blocks.
3430 This function performs value numbering of the statements in each basic
3431 block. The AVAIL sets are built from information we glean while doing
3432 this value numbering, since the AVAIL sets contain only one entry per
3435 AVAIL_IN[BLOCK] = AVAIL_OUT[dom(BLOCK)].
3436 AVAIL_OUT[BLOCK] = AVAIL_IN[BLOCK] U PHI_GEN[BLOCK] U TMP_GEN[BLOCK]. */
3439 compute_avail (void)
3441 basic_block block, son;
3442 basic_block *worklist;
3446 /* For arguments with default definitions, we pretend they are
3447 defined in the entry block. */
3448 for (param = DECL_ARGUMENTS (current_function_decl);
3450 param = TREE_CHAIN (param))
3452 if (gimple_default_def (cfun, param) != NULL)
3454 tree def = gimple_default_def (cfun, param);
3456 vn_lookup_or_add (def);
3459 bitmap_insert_into_set (TMP_GEN (ENTRY_BLOCK_PTR), def);
3460 bitmap_value_insert_into_set (maximal_set, def);
3462 bitmap_value_insert_into_set (AVAIL_OUT (ENTRY_BLOCK_PTR), def);
3466 /* Likewise for the static chain decl. */
3467 if (cfun->static_chain_decl)
3469 param = cfun->static_chain_decl;
3470 if (gimple_default_def (cfun, param) != NULL)
3472 tree def = gimple_default_def (cfun, param);
3474 vn_lookup_or_add (def);
3477 bitmap_insert_into_set (TMP_GEN (ENTRY_BLOCK_PTR), def);
3478 bitmap_value_insert_into_set (maximal_set, def);
3480 bitmap_value_insert_into_set (AVAIL_OUT (ENTRY_BLOCK_PTR), def);
3484 /* Allocate the worklist. */
3485 worklist = XNEWVEC (basic_block, n_basic_blocks);
3487 /* Seed the algorithm by putting the dominator children of the entry
3488 block on the worklist. */
3489 for (son = first_dom_son (CDI_DOMINATORS, ENTRY_BLOCK_PTR);
3491 son = next_dom_son (CDI_DOMINATORS, son))
3492 worklist[sp++] = son;
3494 /* Loop until the worklist is empty. */
3497 block_stmt_iterator bsi;
3500 unsigned int stmt_uid = 1;
3502 /* Pick a block from the worklist. */
3503 block = worklist[--sp];
3505 /* Initially, the set of available values in BLOCK is that of
3506 its immediate dominator. */
3507 dom = get_immediate_dominator (CDI_DOMINATORS, block);
3509 bitmap_set_copy (AVAIL_OUT (block), AVAIL_OUT (dom));
3511 /* Generate values for PHI nodes. */
3512 for (phi = phi_nodes (block); phi; phi = PHI_CHAIN (phi))
3513 make_values_for_phi (phi, block);
3515 /* Now compute value numbers and populate value sets with all
3516 the expressions computed in BLOCK. */
3517 for (bsi = bsi_start (block); !bsi_end_p (bsi); bsi_next (&bsi))
3523 stmt = bsi_stmt (bsi);
3524 ann = stmt_ann (stmt);
3526 ann->uid = stmt_uid++;
3528 /* For regular value numbering, we are only interested in
3529 assignments of the form X_i = EXPR, where EXPR represents
3530 an "interesting" computation, it has no volatile operands
3531 and X_i doesn't flow through an abnormal edge. */
3532 if (TREE_CODE (stmt) == RETURN_EXPR
3533 && !ann->has_volatile_ops)
3535 tree realstmt = stmt;
3539 stmt = TREE_OPERAND (stmt, 0);
3540 if (stmt && TREE_CODE (stmt) == GIMPLE_MODIFY_STMT)
3542 lhs = GIMPLE_STMT_OPERAND (stmt, 0);
3543 rhs = GIMPLE_STMT_OPERAND (stmt, 1);
3544 if (TREE_CODE (lhs) == SSA_NAME
3545 && is_gimple_min_invariant (VN_INFO (lhs)->valnum))
3547 if (dump_file && (dump_flags & TDF_DETAILS))
3549 fprintf (dump_file, "SCCVN says ");
3550 print_generic_expr (dump_file, lhs, 0);
3551 fprintf (dump_file, " value numbers to ");
3552 print_generic_stmt (dump_file, VN_INFO (lhs)->valnum,
3555 vn_add (lhs, VN_INFO (lhs)->valnum);
3559 if (TREE_CODE (rhs) == SSA_NAME)
3560 add_to_exp_gen (block, rhs);
3562 FOR_EACH_SSA_TREE_OPERAND (op, realstmt, iter, SSA_OP_DEF)
3563 add_to_sets (op, op, NULL, TMP_GEN (block),
3569 else if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT
3570 && !ann->has_volatile_ops
3571 && TREE_CODE (GIMPLE_STMT_OPERAND (stmt, 0)) == SSA_NAME
3572 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI
3573 (GIMPLE_STMT_OPERAND (stmt, 0)))
3575 if (make_values_for_stmt (stmt, block))
3580 /* For any other statement that we don't recognize, simply
3581 make the names generated by the statement available in
3582 AVAIL_OUT and TMP_GEN. */
3583 FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_DEF)
3584 add_to_sets (op, op, NULL, TMP_GEN (block), AVAIL_OUT (block));
3586 FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_USE)
3588 add_to_sets (op, op, NULL, NULL , AVAIL_OUT (block));
3589 if (TREE_CODE (op) == SSA_NAME || can_PRE_operation (op))
3590 add_to_exp_gen (block, op);
3594 /* Put the dominator children of BLOCK on the worklist of blocks
3595 to compute available sets for. */
3596 for (son = first_dom_son (CDI_DOMINATORS, block);
3598 son = next_dom_son (CDI_DOMINATORS, son))
3599 worklist[sp++] = son;
3606 /* Eliminate fully redundant computations. */
3615 block_stmt_iterator i;
3617 for (i = bsi_start (b); !bsi_end_p (i); bsi_next (&i))
3619 tree stmt = bsi_stmt (i);
3621 /* Lookup the RHS of the expression, see if we have an
3622 available computation for it. If so, replace the RHS with
3623 the available computation. */
3624 if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT
3625 && TREE_CODE (GIMPLE_STMT_OPERAND (stmt, 0)) == SSA_NAME
3626 && TREE_CODE (GIMPLE_STMT_OPERAND (stmt, 1)) != SSA_NAME
3627 && !is_gimple_min_invariant (GIMPLE_STMT_OPERAND (stmt, 1))
3628 && !stmt_ann (stmt)->has_volatile_ops)
3630 tree lhs = GIMPLE_STMT_OPERAND (stmt, 0);
3631 tree *rhs_p = &GIMPLE_STMT_OPERAND (stmt, 1);
3634 sprime = bitmap_find_leader (AVAIL_OUT (b),
3635 get_value_handle (lhs));
3639 && (TREE_CODE (*rhs_p) != SSA_NAME
3640 || may_propagate_copy (*rhs_p, sprime)))
3642 gcc_assert (sprime != *rhs_p);
3644 if (dump_file && (dump_flags & TDF_DETAILS))
3646 fprintf (dump_file, "Replaced ");
3647 print_generic_expr (dump_file, *rhs_p, 0);
3648 fprintf (dump_file, " with ");
3649 print_generic_expr (dump_file, sprime, 0);
3650 fprintf (dump_file, " in ");
3651 print_generic_stmt (dump_file, stmt, 0);
3654 if (TREE_CODE (sprime) == SSA_NAME)
3655 NECESSARY (SSA_NAME_DEF_STMT (sprime)) = 1;
3656 /* We need to make sure the new and old types actually match,
3657 which may require adding a simple cast, which fold_convert
3659 if (TREE_CODE (*rhs_p) != SSA_NAME
3660 && !useless_type_conversion_p (TREE_TYPE (*rhs_p),
3661 TREE_TYPE (sprime)))
3662 sprime = fold_convert (TREE_TYPE (*rhs_p), sprime);
3664 pre_stats.eliminations++;
3665 propagate_tree_value (rhs_p, sprime);
3668 /* If we removed EH side effects from the statement, clean
3669 its EH information. */
3670 if (maybe_clean_or_replace_eh_stmt (stmt, stmt))
3672 bitmap_set_bit (need_eh_cleanup,
3673 bb_for_stmt (stmt)->index);
3674 if (dump_file && (dump_flags & TDF_DETAILS))
3675 fprintf (dump_file, " Removed EH side effects.\n");
3683 /* Borrow a bit of tree-ssa-dce.c for the moment.
3684 XXX: In 4.1, we should be able to just run a DCE pass after PRE, though
3685 this may be a bit faster, and we may want critical edges kept split. */
3687 /* If OP's defining statement has not already been determined to be necessary,
3688 mark that statement necessary. Return the stmt, if it is newly
3692 mark_operand_necessary (tree op)
3698 if (TREE_CODE (op) != SSA_NAME)
3701 stmt = SSA_NAME_DEF_STMT (op);
3704 if (NECESSARY (stmt)
3705 || IS_EMPTY_STMT (stmt))
3708 NECESSARY (stmt) = 1;
3712 /* Because we don't follow exactly the standard PRE algorithm, and decide not
3713 to insert PHI nodes sometimes, and because value numbering of casts isn't
3714 perfect, we sometimes end up inserting dead code. This simple DCE-like
3715 pass removes any insertions we made that weren't actually used. */
3718 remove_dead_inserted_code (void)
3720 VEC(tree,heap) *worklist = NULL;
3724 worklist = VEC_alloc (tree, heap, VEC_length (tree, inserted_exprs));
3725 for (i = 0; VEC_iterate (tree, inserted_exprs, i, t); i++)
3728 VEC_quick_push (tree, worklist, t);
3730 while (VEC_length (tree, worklist) > 0)
3732 t = VEC_pop (tree, worklist);
3734 /* PHI nodes are somewhat special in that each PHI alternative has
3735 data and control dependencies. All the statements feeding the
3736 PHI node's arguments are always necessary. */
3737 if (TREE_CODE (t) == PHI_NODE)
3741 VEC_reserve (tree, heap, worklist, PHI_NUM_ARGS (t));
3742 for (k = 0; k < PHI_NUM_ARGS (t); k++)
3744 tree arg = PHI_ARG_DEF (t, k);
3745 if (TREE_CODE (arg) == SSA_NAME)
3747 arg = mark_operand_necessary (arg);
3749 VEC_quick_push (tree, worklist, arg);
3755 /* Propagate through the operands. Examine all the USE, VUSE and
3756 VDEF operands in this statement. Mark all the statements
3757 which feed this statement's uses as necessary. */
3761 /* The operands of VDEF expressions are also needed as they
3762 represent potential definitions that may reach this
3763 statement (VDEF operands allow us to follow def-def
3766 FOR_EACH_SSA_TREE_OPERAND (use, t, iter, SSA_OP_ALL_USES)
3768 tree n = mark_operand_necessary (use);
3770 VEC_safe_push (tree, heap, worklist, n);
3775 for (i = 0; VEC_iterate (tree, inserted_exprs, i, t); i++)
3779 block_stmt_iterator bsi;
3781 if (dump_file && (dump_flags & TDF_DETAILS))
3783 fprintf (dump_file, "Removing unnecessary insertion:");
3784 print_generic_stmt (dump_file, t, 0);
3787 if (TREE_CODE (t) == PHI_NODE)
3789 remove_phi_node (t, NULL, true);
3793 bsi = bsi_for_stmt (t);
3794 bsi_remove (&bsi, true);
3799 VEC_free (tree, heap, worklist);
3802 /* Initialize data structures used by PRE. */
3805 init_pre (bool do_fre)
3808 unsigned int max_decl_size;
3810 next_expression_id = 0;
3814 inserted_exprs = NULL;
3815 need_creation = NULL;
3816 pretemp = NULL_TREE;
3817 storetemp = NULL_TREE;
3818 prephitemp = NULL_TREE;
3820 memset (&pre_stats, 0, sizeof (pre_stats));
3821 bitmap_obstack_initialize (&grand_bitmap_obstack);
3825 loop_optimizer_init (LOOPS_NORMAL);
3826 connect_infinite_loops_to_exit ();
3827 postorder = XNEWVEC (int, n_basic_blocks - NUM_FIXED_BLOCKS);
3828 post_order_compute (postorder, false, false);
3829 calculate_dominance_info (CDI_POST_DOMINATORS);
3830 phi_translate_table = htab_create (5110, expr_pred_trans_hash,
3831 expr_pred_trans_eq, free);
3832 seen_during_translate = BITMAP_ALLOC (&grand_bitmap_obstack);
3833 binary_node_pool = create_alloc_pool ("Binary tree nodes",
3834 tree_code_size (PLUS_EXPR), 30);
3835 unary_node_pool = create_alloc_pool ("Unary tree nodes",
3836 tree_code_size (NEGATE_EXPR), 30);
3837 reference_node_pool = create_alloc_pool ("Reference tree nodes",
3838 tree_code_size (ARRAY_REF), 30);
3839 comparison_node_pool = create_alloc_pool ("Comparison tree nodes",
3840 tree_code_size (EQ_EXPR), 30);
3841 modify_expr_node_pool = create_alloc_pool ("GIMPLE_MODIFY_STMT nodes",
3842 tree_code_size (GIMPLE_MODIFY_STMT),
3844 max_decl_size = MAX (tree_code_size (VAR_DECL), tree_code_size (PARM_DECL));
3845 max_decl_size = MAX (max_decl_size, tree_code_size (RESULT_DECL));
3846 max_decl_size = MAX (max_decl_size, tree_code_size (CONST_DECL));
3847 max_decl_size = MAX (max_decl_size, tree_code_size (FUNCTION_DECL));
3848 decl_node_pool = create_alloc_pool ("_DECL nodes", max_decl_size, 30);
3850 obstack_init (&temp_call_expr_obstack);
3851 modify_expr_template = NULL;
3855 bb->aux = xcalloc (1, sizeof (struct bb_bitmap_sets));
3857 calculate_dominance_info (CDI_DOMINATORS);
3859 bitmap_set_pool = create_alloc_pool ("Bitmap sets",
3860 sizeof (struct bitmap_set), 30);
3866 EXP_GEN (bb) = bitmap_set_new ();
3867 PHI_GEN (bb) = bitmap_set_new ();
3868 TMP_GEN (bb) = bitmap_set_new ();
3870 AVAIL_OUT (bb) = bitmap_set_new ();
3872 maximal_set = do_fre ? NULL : bitmap_set_new ();
3874 need_eh_cleanup = BITMAP_ALLOC (NULL);
3875 decl_vh_map = pointer_map_create ();
3876 expression_id_map = pointer_map_create ();
3880 /* Deallocate data structures used by PRE. */
3891 VEC_free (tree, heap, inserted_exprs);
3892 VEC_free (tree, heap, need_creation);
3893 free_alloc_pool (binary_node_pool);
3894 free_alloc_pool (reference_node_pool);
3895 free_alloc_pool (unary_node_pool);
3896 free_alloc_pool (comparison_node_pool);
3897 free_alloc_pool (modify_expr_node_pool);
3898 free_alloc_pool (decl_node_pool);
3899 htab_delete (phi_translate_table);
3900 remove_fake_exit_edges ();
3901 free_dominance_info (CDI_POST_DOMINATORS);
3903 bitmap_obstack_release (&grand_bitmap_obstack);
3904 free_alloc_pool (bitmap_set_pool);
3912 if (!bitmap_empty_p (need_eh_cleanup))
3914 tree_purge_all_dead_eh_edges (need_eh_cleanup);
3915 cleanup_tree_cfg ();
3918 BITMAP_FREE (need_eh_cleanup);
3919 pointer_map_destroy (decl_vh_map);
3920 pointer_map_destroy (expression_id_map);
3922 /* Wipe out pointers to VALUE_HANDLEs. In the not terribly distant
3923 future we will want them to be persistent though. */
3924 for (i = 0; i < num_ssa_names; i++)
3926 tree name = ssa_name (i);
3931 if (SSA_NAME_VALUE (name)
3932 && TREE_CODE (SSA_NAME_VALUE (name)) == VALUE_HANDLE)
3933 SSA_NAME_VALUE (name) = NULL;
3935 if (current_loops != NULL && !in_fre)
3936 loop_optimizer_finalize ();
3939 /* Main entry point to the SSA-PRE pass. DO_FRE is true if the caller
3940 only wants to do full redundancy elimination. */
3943 execute_pre (bool do_fre)
3946 do_partial_partial = optimize > 2;
3950 insert_fake_stores ();
3952 /* Collect and value number expressions computed in each basic block. */
3954 switch_to_PRE_table ();
3957 if (dump_file && (dump_flags & TDF_DETAILS))
3963 print_bitmap_set (dump_file, EXP_GEN (bb), "exp_gen", bb->index);
3964 print_bitmap_set (dump_file, TMP_GEN (bb), "tmp_gen",
3966 print_bitmap_set (dump_file, AVAIL_OUT (bb), "avail_out",
3971 /* Insert can get quite slow on an incredibly large number of basic
3972 blocks due to some quadratic behavior. Until this behavior is
3973 fixed, don't run it when he have an incredibly large number of
3974 bb's. If we aren't going to run insert, there is no point in
3975 computing ANTIC, either, even though it's plenty fast. */
3976 if (!do_fre && n_basic_blocks < 4000)
3982 /* Remove all the redundant expressions. */
3985 if (dump_file && (dump_flags & TDF_STATS))
3987 fprintf (dump_file, "Insertions: %d\n", pre_stats.insertions);
3988 fprintf (dump_file, "PA inserted: %d\n", pre_stats.pa_insert);
3989 fprintf (dump_file, "New PHIs: %d\n", pre_stats.phis);
3990 fprintf (dump_file, "Eliminated: %d\n", pre_stats.eliminations);
3991 fprintf (dump_file, "Constified: %d\n", pre_stats.constified);
3993 bsi_commit_edge_inserts ();
3998 remove_dead_inserted_code ();
3999 realify_fake_stores ();
4005 /* Gate and execute functions for PRE. */
4010 execute_pre (false);
4017 return flag_tree_pre != 0;
4020 struct tree_opt_pass pass_pre =
4023 gate_pre, /* gate */
4024 do_pre, /* execute */
4027 0, /* static_pass_number */
4028 TV_TREE_PRE, /* tv_id */
4029 PROP_no_crit_edges | PROP_cfg
4030 | PROP_ssa | PROP_alias, /* properties_required */
4031 0, /* properties_provided */
4032 0, /* properties_destroyed */
4033 0, /* todo_flags_start */
4034 TODO_update_ssa_only_virtuals | TODO_dump_func | TODO_ggc_collect
4035 | TODO_verify_ssa, /* todo_flags_finish */
4040 /* Gate and execute functions for FRE. */
4052 return flag_tree_fre != 0;
4055 struct tree_opt_pass pass_fre =
4058 gate_fre, /* gate */
4059 execute_fre, /* execute */
4062 0, /* static_pass_number */
4063 TV_TREE_FRE, /* tv_id */
4064 PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */
4065 0, /* properties_provided */
4066 0, /* properties_destroyed */
4067 0, /* todo_flags_start */
4068 TODO_dump_func | TODO_ggc_collect | TODO_verify_ssa, /* todo_flags_finish */