2 Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007
3 Free Software Foundation, Inc.
4 Contributed by Daniel Berlin <dan@dberlin.org> and Steven Bosscher
7 This file is part of GCC.
9 GCC is free software; you can redistribute it and/or modify
10 it under the terms of the GNU General Public License as published by
11 the Free Software Foundation; either version 2, or (at your option)
14 GCC is distributed in the hope that it will be useful,
15 but WITHOUT ANY WARRANTY; without even the implied warranty of
16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 GNU General Public License for more details.
19 You should have received a copy of the GNU General Public License
20 along with GCC; see the file COPYING. If not, write to
21 the Free Software Foundation, 51 Franklin Street, Fifth Floor,
22 Boston, MA 02110-1301, USA. */
26 #include "coretypes.h"
30 #include "basic-block.h"
31 #include "diagnostic.h"
32 #include "tree-inline.h"
33 #include "tree-flow.h"
34 #include "tree-gimple.h"
35 #include "tree-dump.h"
39 #include "tree-iterator.h"
41 #include "alloc-pool.h"
43 #include "tree-pass.h"
46 #include "langhooks.h"
48 #include "tree-ssa-sccvn.h"
52 1. Avail sets can be shared by making an avail_find_leader that
53 walks up the dominator tree and looks in those avail sets.
54 This might affect code optimality, it's unclear right now.
55 2. Strength reduction can be performed by anticipating expressions
56 we can repair later on.
57 3. We can do back-substitution or smarter value numbering to catch
58 commutative expressions split up over multiple statements.
61 /* For ease of terminology, "expression node" in the below refers to
62 every expression node but GIMPLE_MODIFY_STMT, because GIMPLE_MODIFY_STMT's
63 represent the actual statement containing the expressions we care about,
64 and we cache the value number by putting it in the expression. */
68 First we walk the statements to generate the AVAIL sets, the
69 EXP_GEN sets, and the tmp_gen sets. EXP_GEN sets represent the
70 generation of values/expressions by a given block. We use them
71 when computing the ANTIC sets. The AVAIL sets consist of
72 SSA_NAME's that represent values, so we know what values are
73 available in what blocks. AVAIL is a forward dataflow problem. In
74 SSA, values are never killed, so we don't need a kill set, or a
75 fixpoint iteration, in order to calculate the AVAIL sets. In
76 traditional parlance, AVAIL sets tell us the downsafety of the
79 Next, we generate the ANTIC sets. These sets represent the
80 anticipatable expressions. ANTIC is a backwards dataflow
81 problem. An expression is anticipatable in a given block if it could
82 be generated in that block. This means that if we had to perform
83 an insertion in that block, of the value of that expression, we
84 could. Calculating the ANTIC sets requires phi translation of
85 expressions, because the flow goes backwards through phis. We must
86 iterate to a fixpoint of the ANTIC sets, because we have a kill
87 set. Even in SSA form, values are not live over the entire
88 function, only from their definition point onwards. So we have to
89 remove values from the ANTIC set once we go past the definition
90 point of the leaders that make them up.
91 compute_antic/compute_antic_aux performs this computation.
93 Third, we perform insertions to make partially redundant
94 expressions fully redundant.
96 An expression is partially redundant (excluding partial
99 1. It is AVAIL in some, but not all, of the predecessors of a
101 2. It is ANTIC in all the predecessors.
103 In order to make it fully redundant, we insert the expression into
104 the predecessors where it is not available, but is ANTIC.
106 For the partial anticipation case, we only perform insertion if it
107 is partially anticipated in some block, and fully available in all
110 insert/insert_aux/do_regular_insertion/do_partial_partial_insertion
111 performs these steps.
113 Fourth, we eliminate fully redundant expressions.
114 This is a simple statement walk that replaces redundant
115 calculations with the now available values. */
117 /* Representations of value numbers:
119 Value numbers are represented using the "value handle" approach.
120 This means that each SSA_NAME (and for other reasons to be
121 disclosed in a moment, expression nodes) has a value handle that
122 can be retrieved through get_value_handle. This value handle *is*
123 the value number of the SSA_NAME. You can pointer compare the
124 value handles for equivalence purposes.
126 For debugging reasons, the value handle is internally more than
127 just a number, it is a VALUE_HANDLE named "VH.x", where x is a
128 unique number for each value number in use. This allows
129 expressions with SSA_NAMES replaced by value handles to still be
130 pretty printed in a sane way. They simply print as "VH.3 *
133 Expression nodes have value handles associated with them as a
134 cache. Otherwise, we'd have to look them up again in the hash
135 table This makes significant difference (factor of two or more) on
136 some test cases. They can be thrown away after the pass is
139 /* Representation of expressions on value numbers:
141 In some portions of this code, you will notice we allocate "fake"
142 analogues to the expression we are value numbering, and replace the
143 operands with the values of the expression. Since we work on
144 values, and not just names, we canonicalize expressions to value
145 expressions for use in the ANTIC sets, the EXP_GEN set, etc.
147 This is theoretically unnecessary, it just saves a bunch of
148 repeated get_value_handle and find_leader calls in the remainder of
149 the code, trading off temporary memory usage for speed. The tree
150 nodes aren't actually creating more garbage, since they are
151 allocated in a special pools which are thrown away at the end of
154 All of this also means that if you print the EXP_GEN or ANTIC sets,
155 you will see "VH.5 + VH.7" in the set, instead of "a_55 +
156 b_66" or something. The only thing that actually cares about
157 seeing the value leaders is phi translation, and it needs to be
158 able to find the leader for a value in an arbitrary block, so this
159 "value expression" form is perfect for it (otherwise you'd do
160 get_value_handle->find_leader->translate->get_value_handle->find_leader).*/
163 /* Representation of sets:
165 There are currently two types of sets used, hopefully to be unified soon.
166 The AVAIL sets do not need to be sorted in any particular order,
167 and thus, are simply represented as two bitmaps, one that keeps
168 track of values present in the set, and one that keeps track of
169 expressions present in the set.
171 The other sets are represented as doubly linked lists kept in topological
172 order, with an optional supporting bitmap of values present in the
173 set. The sets represent values, and the elements can be values or
174 expressions. The elements can appear in different sets, but each
175 element can only appear once in each set.
177 Since each node in the set represents a value, we also want to be
178 able to map expression, set pairs to something that tells us
179 whether the value is present is a set. We use a per-set bitmap for
180 that. The value handles also point to a linked list of the
181 expressions they represent via a tree annotation. This is mainly
182 useful only for debugging, since we don't do identity lookups. */
185 /* Next global expression id number. */
186 static unsigned int next_expression_id;
188 /* Mapping from expression to id number we can use in bitmap sets. */
189 static VEC(tree, heap) *expressions;
191 /* Allocate an expression id for EXPR. */
193 static inline unsigned int
194 alloc_expression_id (tree expr)
196 tree_ann_common_t ann;
198 ann = get_tree_common_ann (expr);
200 /* Make sure we won't overflow. */
201 gcc_assert (next_expression_id + 1 > next_expression_id);
203 ann->aux = XNEW (unsigned int);
204 * ((unsigned int *)ann->aux) = next_expression_id++;
205 VEC_safe_push (tree, heap, expressions, expr);
206 return next_expression_id - 1;
209 /* Return the expression id for tree EXPR. */
211 static inline unsigned int
212 get_expression_id (tree expr)
214 tree_ann_common_t ann = tree_common_ann (expr);
216 gcc_assert (ann->aux);
218 return *((unsigned int *)ann->aux);
221 /* Return the existing expression id for EXPR, or create one if one
222 does not exist yet. */
224 static inline unsigned int
225 get_or_alloc_expression_id (tree expr)
227 tree_ann_common_t ann = tree_common_ann (expr);
229 if (ann == NULL || !ann->aux)
230 return alloc_expression_id (expr);
232 return get_expression_id (expr);
235 /* Return the expression that has expression id ID */
238 expression_for_id (unsigned int id)
240 return VEC_index (tree, expressions, id);
243 /* Free the expression id field in all of our expressions,
244 and then destroy the expressions array. */
247 clear_expression_ids (void)
252 for (i = 0; VEC_iterate (tree, expressions, i, expr); i++)
254 free (tree_common_ann (expr)->aux);
255 tree_common_ann (expr)->aux = NULL;
257 VEC_free (tree, heap, expressions);
260 static bool in_fre = false;
262 /* An unordered bitmap set. One bitmap tracks values, the other,
264 typedef struct bitmap_set
270 #define FOR_EACH_EXPR_ID_IN_SET(set, id, bi) \
271 EXECUTE_IF_SET_IN_BITMAP(set->expressions, 0, id, bi)
273 /* Sets that we need to keep track of. */
274 typedef struct bb_bitmap_sets
276 /* The EXP_GEN set, which represents expressions/values generated in
278 bitmap_set_t exp_gen;
280 /* The PHI_GEN set, which represents PHI results generated in a
282 bitmap_set_t phi_gen;
284 /* The TMP_GEN set, which represents results/temporaries generated
285 in a basic block. IE the LHS of an expression. */
286 bitmap_set_t tmp_gen;
288 /* The AVAIL_OUT set, which represents which values are available in
289 a given basic block. */
290 bitmap_set_t avail_out;
292 /* The ANTIC_IN set, which represents which values are anticipatable
293 in a given basic block. */
294 bitmap_set_t antic_in;
296 /* The PA_IN set, which represents which values are
297 partially anticipatable in a given basic block. */
300 /* The NEW_SETS set, which is used during insertion to augment the
301 AVAIL_OUT set of blocks with the new insertions performed during
302 the current iteration. */
303 bitmap_set_t new_sets;
305 /* True if we have visited this block during ANTIC calculation. */
306 unsigned int visited:1;
308 /* True we have deferred processing this block during ANTIC
309 calculation until its successor is processed. */
310 unsigned int deferred : 1;
313 #define EXP_GEN(BB) ((bb_value_sets_t) ((BB)->aux))->exp_gen
314 #define PHI_GEN(BB) ((bb_value_sets_t) ((BB)->aux))->phi_gen
315 #define TMP_GEN(BB) ((bb_value_sets_t) ((BB)->aux))->tmp_gen
316 #define AVAIL_OUT(BB) ((bb_value_sets_t) ((BB)->aux))->avail_out
317 #define ANTIC_IN(BB) ((bb_value_sets_t) ((BB)->aux))->antic_in
318 #define PA_IN(BB) ((bb_value_sets_t) ((BB)->aux))->pa_in
319 #define NEW_SETS(BB) ((bb_value_sets_t) ((BB)->aux))->new_sets
320 #define BB_VISITED(BB) ((bb_value_sets_t) ((BB)->aux))->visited
321 #define BB_DEFERRED(BB) ((bb_value_sets_t) ((BB)->aux))->deferred
323 /* Maximal set of values, used to initialize the ANTIC problem, which
324 is an intersection problem. */
325 static bitmap_set_t maximal_set;
327 /* Basic block list in postorder. */
328 static int *postorder;
330 /* This structure is used to keep track of statistics on what
331 optimization PRE was able to perform. */
334 /* The number of RHS computations eliminated by PRE. */
337 /* The number of new expressions/temporaries generated by PRE. */
340 /* The number of inserts found due to partial anticipation */
343 /* The number of new PHI nodes added by PRE. */
346 /* The number of values found constant. */
351 static bool do_partial_partial;
352 static tree bitmap_find_leader (bitmap_set_t, tree);
353 static void bitmap_value_insert_into_set (bitmap_set_t, tree);
354 static void bitmap_value_replace_in_set (bitmap_set_t, tree);
355 static void bitmap_set_copy (bitmap_set_t, bitmap_set_t);
356 static bool bitmap_set_contains_value (bitmap_set_t, tree);
357 static void bitmap_insert_into_set (bitmap_set_t, tree);
358 static bitmap_set_t bitmap_set_new (void);
359 static bool is_undefined_value (tree);
360 static tree create_expression_by_pieces (basic_block, tree, tree);
361 static tree find_or_generate_expression (basic_block, tree, tree);
363 /* We can add and remove elements and entries to and from sets
364 and hash tables, so we use alloc pools for them. */
366 static alloc_pool bitmap_set_pool;
367 static alloc_pool binary_node_pool;
368 static alloc_pool unary_node_pool;
369 static alloc_pool reference_node_pool;
370 static alloc_pool comparison_node_pool;
371 static alloc_pool modify_expr_node_pool;
372 static bitmap_obstack grand_bitmap_obstack;
374 /* We can't use allocation pools to hold temporary CALL_EXPR objects, since
375 they are not of fixed size. Instead, use an obstack. */
377 static struct obstack temp_call_expr_obstack;
380 /* To avoid adding 300 temporary variables when we only need one, we
381 only create one temporary variable, on demand, and build ssa names
382 off that. We do have to change the variable if the types don't
383 match the current variable's type. */
385 static tree storetemp;
386 static tree prephitemp;
388 /* Set of blocks with statements that have had its EH information
390 static bitmap need_eh_cleanup;
392 /* Which expressions have been seen during a given phi translation. */
393 static bitmap seen_during_translate;
395 /* The phi_translate_table caches phi translations for a given
396 expression and predecessor. */
398 static htab_t phi_translate_table;
400 /* A three tuple {e, pred, v} used to cache phi translations in the
401 phi_translate_table. */
403 typedef struct expr_pred_trans_d
405 /* The expression. */
408 /* The predecessor block along which we translated the expression. */
411 /* vuses associated with the expression. */
412 VEC (tree, gc) *vuses;
414 /* The value that resulted from the translation. */
417 /* The hashcode for the expression, pred pair. This is cached for
420 } *expr_pred_trans_t;
422 /* Return the hash value for a phi translation table entry. */
425 expr_pred_trans_hash (const void *p)
427 const expr_pred_trans_t ve = (expr_pred_trans_t) p;
431 /* Return true if two phi translation table entries are the same.
432 P1 and P2 should point to the expr_pred_trans_t's to be compared.*/
435 expr_pred_trans_eq (const void *p1, const void *p2)
437 const expr_pred_trans_t ve1 = (expr_pred_trans_t) p1;
438 const expr_pred_trans_t ve2 = (expr_pred_trans_t) p2;
439 basic_block b1 = ve1->pred;
440 basic_block b2 = ve2->pred;
444 /* If they are not translations for the same basic block, they can't
450 /* If they are for the same basic block, determine if the
451 expressions are equal. */
452 if (!expressions_equal_p (ve1->e, ve2->e))
455 /* Make sure the vuses are equivalent. */
456 if (ve1->vuses == ve2->vuses)
459 if (VEC_length (tree, ve1->vuses) != VEC_length (tree, ve2->vuses))
462 for (i = 0; VEC_iterate (tree, ve1->vuses, i, vuse1); i++)
464 if (VEC_index (tree, ve2->vuses, i) != vuse1)
471 /* Search in the phi translation table for the translation of
472 expression E in basic block PRED with vuses VUSES.
473 Return the translated value, if found, NULL otherwise. */
476 phi_trans_lookup (tree e, basic_block pred, VEC (tree, gc) *vuses)
479 struct expr_pred_trans_d ept;
484 ept.hashcode = iterative_hash_expr (e, (unsigned long) pred);
485 slot = htab_find_slot_with_hash (phi_translate_table, &ept, ept.hashcode,
490 return ((expr_pred_trans_t) *slot)->v;
494 /* Add the tuple mapping from {expression E, basic block PRED, vuses VUSES} to
495 value V, to the phi translation table. */
498 phi_trans_add (tree e, tree v, basic_block pred, VEC (tree, gc) *vuses)
501 expr_pred_trans_t new_pair = XNEW (struct expr_pred_trans_d);
503 new_pair->pred = pred;
504 new_pair->vuses = vuses;
506 new_pair->hashcode = iterative_hash_expr (e, (unsigned long) pred);
507 slot = htab_find_slot_with_hash (phi_translate_table, new_pair,
508 new_pair->hashcode, INSERT);
511 *slot = (void *) new_pair;
515 /* Return true if V is a value expression that represents itself.
516 In our world, this is *only* non-value handles. */
519 constant_expr_p (tree v)
521 return TREE_CODE (v) != VALUE_HANDLE &&
522 (TREE_CODE (v) == FIELD_DECL || is_gimple_min_invariant (v));
525 /* Add expression E to the expression set of value V. */
528 add_to_value (tree v, tree e)
530 /* Constants have no expression sets. */
531 if (constant_expr_p (v))
534 if (VALUE_HANDLE_EXPR_SET (v) == NULL)
535 VALUE_HANDLE_EXPR_SET (v) = bitmap_set_new ();
537 bitmap_insert_into_set (VALUE_HANDLE_EXPR_SET (v), e);
540 /* Create a new bitmap set and return it. */
543 bitmap_set_new (void)
545 bitmap_set_t ret = (bitmap_set_t) pool_alloc (bitmap_set_pool);
546 ret->expressions = BITMAP_ALLOC (&grand_bitmap_obstack);
547 ret->values = BITMAP_ALLOC (&grand_bitmap_obstack);
551 /* Remove an expression EXPR from a bitmapped set. */
554 bitmap_remove_from_set (bitmap_set_t set, tree expr)
556 tree val = get_value_handle (expr);
559 if (!constant_expr_p (val))
561 bitmap_clear_bit (set->values, VALUE_HANDLE_ID (val));
562 bitmap_clear_bit (set->expressions, get_expression_id (expr));
566 /* Insert an expression EXPR into a bitmapped set. */
569 bitmap_insert_into_set (bitmap_set_t set, tree expr)
571 tree val = get_value_handle (expr);
574 if (!constant_expr_p (val))
576 bitmap_set_bit (set->values, VALUE_HANDLE_ID (val));
577 bitmap_set_bit (set->expressions, get_or_alloc_expression_id (expr));
581 /* Copy a bitmapped set ORIG, into bitmapped set DEST. */
584 bitmap_set_copy (bitmap_set_t dest, bitmap_set_t orig)
586 bitmap_copy (dest->expressions, orig->expressions);
587 bitmap_copy (dest->values, orig->values);
591 /* Free memory used up by SET. */
593 bitmap_set_free (bitmap_set_t set)
595 BITMAP_FREE (set->expressions);
596 BITMAP_FREE (set->values);
600 /* A comparison function for use in qsort to top sort a bitmap set. Simply
601 subtracts value handle ids, since they are created in topo-order. */
604 vh_compare (const void *pa, const void *pb)
606 const tree vha = get_value_handle (*((const tree *)pa));
607 const tree vhb = get_value_handle (*((const tree *)pb));
609 /* This can happen when we constify things. */
610 if (constant_expr_p (vha))
612 if (constant_expr_p (vhb))
616 else if (constant_expr_p (vhb))
618 return VALUE_HANDLE_ID (vha) - VALUE_HANDLE_ID (vhb);
621 /* Generate an topological-ordered array of bitmap set SET. */
623 static VEC(tree, heap) *
624 sorted_array_from_bitmap_set (bitmap_set_t set)
628 VEC(tree, heap) *result = NULL;
630 FOR_EACH_EXPR_ID_IN_SET (set, i, bi)
631 VEC_safe_push (tree, heap, result, expression_for_id (i));
633 qsort (VEC_address (tree, result), VEC_length (tree, result),
634 sizeof (tree), vh_compare);
639 /* Perform bitmapped set operation DEST &= ORIG. */
642 bitmap_set_and (bitmap_set_t dest, bitmap_set_t orig)
649 bitmap temp = BITMAP_ALLOC (&grand_bitmap_obstack);
651 bitmap_and_into (dest->values, orig->values);
652 bitmap_copy (temp, dest->expressions);
653 EXECUTE_IF_SET_IN_BITMAP (temp, 0, i, bi)
655 tree expr = expression_for_id (i);
656 tree val = get_value_handle (expr);
657 if (!bitmap_bit_p (dest->values, VALUE_HANDLE_ID (val)))
658 bitmap_clear_bit (dest->expressions, i);
664 /* Subtract all values and expressions contained in ORIG from DEST. */
667 bitmap_set_subtract (bitmap_set_t dest, bitmap_set_t orig)
669 bitmap_set_t result = bitmap_set_new ();
673 bitmap_and_compl (result->expressions, dest->expressions,
676 FOR_EACH_EXPR_ID_IN_SET (result, i, bi)
678 tree expr = expression_for_id (i);
679 tree val = get_value_handle (expr);
680 bitmap_set_bit (result->values, VALUE_HANDLE_ID (val));
686 /* Subtract all the values in bitmap set B from bitmap set A. */
689 bitmap_set_subtract_values (bitmap_set_t a, bitmap_set_t b)
693 bitmap temp = BITMAP_ALLOC (&grand_bitmap_obstack);
695 bitmap_copy (temp, a->expressions);
696 EXECUTE_IF_SET_IN_BITMAP (temp, 0, i, bi)
698 tree expr = expression_for_id (i);
699 if (bitmap_set_contains_value (b, get_value_handle (expr)))
700 bitmap_remove_from_set (a, expr);
706 /* Return true if bitmapped set SET contains the value VAL. */
709 bitmap_set_contains_value (bitmap_set_t set, tree val)
711 if (constant_expr_p (val))
714 if (!set || bitmap_empty_p (set->expressions))
717 return bitmap_bit_p (set->values, VALUE_HANDLE_ID (val));
721 bitmap_set_contains_expr (bitmap_set_t set, tree expr)
723 return bitmap_bit_p (set->expressions, get_expression_id (expr));
726 /* Replace an instance of value LOOKFOR with expression EXPR in SET. */
729 bitmap_set_replace_value (bitmap_set_t set, tree lookfor, tree expr)
731 bitmap_set_t exprset;
735 if (constant_expr_p (lookfor))
738 if (!bitmap_set_contains_value (set, lookfor))
741 /* The number of expressions having a given value is usually
742 significantly less than the total number of expressions in SET.
743 Thus, rather than check, for each expression in SET, whether it
744 has the value LOOKFOR, we walk the reverse mapping that tells us
745 what expressions have a given value, and see if any of those
746 expressions are in our set. For large testcases, this is about
747 5-10x faster than walking the bitmap. If this is somehow a
748 significant lose for some cases, we can choose which set to walk
749 based on the set size. */
750 exprset = VALUE_HANDLE_EXPR_SET (lookfor);
751 FOR_EACH_EXPR_ID_IN_SET (exprset, i, bi)
753 if (bitmap_bit_p (set->expressions, i))
755 bitmap_clear_bit (set->expressions, i);
756 bitmap_set_bit (set->expressions, get_expression_id (expr));
762 /* Return true if two bitmap sets are equal. */
765 bitmap_set_equal (bitmap_set_t a, bitmap_set_t b)
767 return bitmap_equal_p (a->values, b->values);
770 /* Replace an instance of EXPR's VALUE with EXPR in SET if it exists,
771 and add it otherwise. */
774 bitmap_value_replace_in_set (bitmap_set_t set, tree expr)
776 tree val = get_value_handle (expr);
778 if (bitmap_set_contains_value (set, val))
779 bitmap_set_replace_value (set, val, expr);
781 bitmap_insert_into_set (set, expr);
784 /* Insert EXPR into SET if EXPR's value is not already present in
788 bitmap_value_insert_into_set (bitmap_set_t set, tree expr)
790 tree val = get_value_handle (expr);
792 if (constant_expr_p (val))
795 if (!bitmap_set_contains_value (set, val))
796 bitmap_insert_into_set (set, expr);
799 /* Print out SET to OUTFILE. */
802 print_bitmap_set (FILE *outfile, bitmap_set_t set,
803 const char *setname, int blockindex)
805 fprintf (outfile, "%s[%d] := { ", setname, blockindex);
812 FOR_EACH_EXPR_ID_IN_SET (set, i, bi)
814 tree expr = expression_for_id (i);
817 fprintf (outfile, ", ");
819 print_generic_expr (outfile, expr, 0);
821 fprintf (outfile, " (");
822 print_generic_expr (outfile, get_value_handle (expr), 0);
823 fprintf (outfile, ") ");
826 fprintf (outfile, " }\n");
829 void debug_bitmap_set (bitmap_set_t);
832 debug_bitmap_set (bitmap_set_t set)
834 print_bitmap_set (stderr, set, "debug", 0);
837 /* Print out the expressions that have VAL to OUTFILE. */
840 print_value_expressions (FILE *outfile, tree val)
842 if (VALUE_HANDLE_EXPR_SET (val))
845 sprintf (s, "VH.%04d", VALUE_HANDLE_ID (val));
846 print_bitmap_set (outfile, VALUE_HANDLE_EXPR_SET (val), s, 0);
852 debug_value_expressions (tree val)
854 print_value_expressions (stderr, val);
857 /* Return the folded version of T if T, when folded, is a gimple
858 min_invariant. Otherwise, return T. */
861 fully_constant_expression (tree t)
865 if (folded && is_gimple_min_invariant (folded))
870 /* Make a temporary copy of a CALL_EXPR object NODE. */
873 temp_copy_call_expr (tree node)
875 return (tree) obstack_copy (&temp_call_expr_obstack, node, tree_size (node));
878 /* Translate the vuses in the VUSES vector backwards through phi nodes
879 in PHIBLOCK, so that they have the value they would have in
882 static VEC(tree, gc) *
883 translate_vuses_through_block (VEC (tree, gc) *vuses,
884 basic_block phiblock,
888 VEC(tree, gc) *result = NULL;
891 for (i = 0; VEC_iterate (tree, vuses, i, oldvuse); i++)
893 tree phi = SSA_NAME_DEF_STMT (oldvuse);
894 if (TREE_CODE (phi) == PHI_NODE
895 && bb_for_stmt (phi) == phiblock)
897 edge e = find_edge (block, bb_for_stmt (phi));
900 tree def = PHI_ARG_DEF (phi, e->dest_idx);
904 result = VEC_copy (tree, gc, vuses);
905 VEC_replace (tree, result, i, def);
911 /* We avoid creating a new copy of the vuses unless something
912 actually changed, so result can be NULL. */
922 /* Like find_leader, but checks for the value existing in SET1 *or*
923 SET2. This is used to avoid making a set consisting of the union
924 of PA_IN and ANTIC_IN during insert. */
927 find_leader_in_sets (tree expr, bitmap_set_t set1, bitmap_set_t set2)
931 result = bitmap_find_leader (set1, expr);
933 result = bitmap_find_leader (set2, expr);
937 /* Translate EXPR using phis in PHIBLOCK, so that it has the values of
938 the phis in PRED. SEEN is a bitmap saying which expression we have
939 translated since we started translation of the toplevel expression.
940 Return NULL if we can't find a leader for each part of the
941 translated expression. */
944 phi_translate_1 (tree expr, bitmap_set_t set1, bitmap_set_t set2,
945 basic_block pred, basic_block phiblock, bitmap seen)
947 tree phitrans = NULL;
953 if (constant_expr_p (expr))
956 /* Phi translations of a given expression don't change. */
957 if (EXPR_P (expr) || GIMPLE_STMT_P (expr))
961 vh = get_value_handle (expr);
962 if (vh && TREE_CODE (vh) == VALUE_HANDLE)
963 phitrans = phi_trans_lookup (expr, pred, VALUE_HANDLE_VUSES (vh));
965 phitrans = phi_trans_lookup (expr, pred, NULL);
968 phitrans = phi_trans_lookup (expr, pred, NULL);
973 /* Prevent cycles when we have recursively dependent leaders. This
974 can only happen when phi translating the maximal set. */
977 unsigned int expr_id = get_expression_id (expr);
978 if (bitmap_bit_p (seen, expr_id))
980 bitmap_set_bit (seen, expr_id);
983 switch (TREE_CODE_CLASS (TREE_CODE (expr)))
990 if (TREE_CODE (expr) != CALL_EXPR)
994 tree oldfn = CALL_EXPR_FN (expr);
995 tree oldsc = CALL_EXPR_STATIC_CHAIN (expr);
996 tree newfn, newsc = NULL;
997 tree newexpr = NULL_TREE;
998 tree vh = get_value_handle (expr);
999 bool invariantarg = false;
1001 VEC (tree, gc) *vuses = VALUE_HANDLE_VUSES (vh);
1002 VEC (tree, gc) *tvuses;
1004 newfn = phi_translate_1 (find_leader_in_sets (oldfn, set1, set2),
1005 set1, set2, pred, phiblock, seen);
1010 newexpr = temp_copy_call_expr (expr);
1011 CALL_EXPR_FN (newexpr) = get_value_handle (newfn);
1015 newsc = phi_translate_1 (find_leader_in_sets (oldsc, set1, set2),
1016 set1, set2, pred, phiblock, seen);
1022 newexpr = temp_copy_call_expr (expr);
1023 CALL_EXPR_STATIC_CHAIN (newexpr) = get_value_handle (newsc);
1027 /* phi translate the argument list piece by piece. */
1028 nargs = call_expr_nargs (expr);
1029 for (i = 0; i < nargs; i++)
1031 tree oldval = CALL_EXPR_ARG (expr, i);
1035 /* This may seem like a weird place for this
1036 check, but it's actually the easiest place to
1037 do it. We can't do it lower on in the
1038 recursion because it's valid for pieces of a
1039 component ref to be of AGGREGATE_TYPE, as long
1040 as the outermost one is not.
1041 To avoid *that* case, we have a check for
1042 AGGREGATE_TYPE_P in insert_aux. However, that
1043 check will *not* catch this case because here
1044 it occurs in the argument list. */
1045 if (AGGREGATE_TYPE_P (TREE_TYPE (oldval)))
1047 oldval = find_leader_in_sets (oldval, set1, set2);
1048 newval = phi_translate_1 (oldval, set1, set2, pred,
1052 if (newval != oldval)
1054 invariantarg |= is_gimple_min_invariant (newval);
1056 newexpr = temp_copy_call_expr (expr);
1057 CALL_EXPR_ARG (newexpr, i) = get_value_handle (newval);
1062 /* In case of new invariant args we might try to fold the call
1064 if (invariantarg && !newsc)
1066 tree tmp1 = build_call_array (TREE_TYPE (expr),
1067 newfn, call_expr_nargs (newexpr),
1068 CALL_EXPR_ARGP (newexpr));
1069 tree tmp2 = fold (tmp1);
1072 STRIP_TYPE_NOPS (tmp2);
1073 if (is_gimple_min_invariant (tmp2))
1078 tvuses = translate_vuses_through_block (vuses, phiblock, pred);
1079 if (vuses != tvuses && ! newexpr)
1080 newexpr = temp_copy_call_expr (expr);
1084 newexpr->base.ann = NULL;
1085 vn_lookup_or_add_with_vuses (newexpr, tvuses);
1088 phi_trans_add (oldexpr, expr, pred, tvuses);
1093 case tcc_declaration:
1095 VEC (tree, gc) * oldvuses = NULL;
1096 VEC (tree, gc) * newvuses = NULL;
1098 oldvuses = VALUE_HANDLE_VUSES (get_value_handle (expr));
1100 newvuses = translate_vuses_through_block (oldvuses, phiblock,
1103 if (oldvuses != newvuses)
1104 vn_lookup_or_add_with_vuses (expr, newvuses);
1106 phi_trans_add (oldexpr, expr, pred, newvuses);
1112 tree oldop0 = TREE_OPERAND (expr, 0);
1121 VEC (tree, gc) * oldvuses = NULL;
1122 VEC (tree, gc) * newvuses = NULL;
1124 if (TREE_CODE (expr) != INDIRECT_REF
1125 && TREE_CODE (expr) != COMPONENT_REF
1126 && TREE_CODE (expr) != ARRAY_REF)
1129 oldop0 = find_leader_in_sets (oldop0, set1, set2);
1130 newop0 = phi_translate_1 (oldop0, set1, set2, pred, phiblock, seen);
1134 if (TREE_CODE (expr) == ARRAY_REF)
1136 oldop1 = TREE_OPERAND (expr, 1);
1137 oldop1 = find_leader_in_sets (oldop1, set1, set2);
1138 newop1 = phi_translate_1 (oldop1, set1, set2, pred, phiblock, seen);
1143 oldop2 = TREE_OPERAND (expr, 2);
1146 oldop2 = find_leader_in_sets (oldop2, set1, set2);
1147 newop2 = phi_translate_1 (oldop2, set1, set2, pred, phiblock, seen);
1152 oldop3 = TREE_OPERAND (expr, 3);
1155 oldop3 = find_leader_in_sets (oldop3, set1, set2);
1156 newop3 = phi_translate_1 (oldop3, set1, set2, pred, phiblock, seen);
1163 oldvuses = VALUE_HANDLE_VUSES (get_value_handle (expr));
1165 newvuses = translate_vuses_through_block (oldvuses, phiblock,
1168 if (newop0 != oldop0 || newvuses != oldvuses
1171 || newop3 != oldop3)
1175 newexpr = (tree) pool_alloc (reference_node_pool);
1176 memcpy (newexpr, expr, tree_size (expr));
1177 TREE_OPERAND (newexpr, 0) = get_value_handle (newop0);
1178 if (TREE_CODE (expr) == ARRAY_REF)
1180 TREE_OPERAND (newexpr, 1) = get_value_handle (newop1);
1182 TREE_OPERAND (newexpr, 2) = get_value_handle (newop2);
1184 TREE_OPERAND (newexpr, 3) = get_value_handle (newop3);
1187 t = fully_constant_expression (newexpr);
1191 pool_free (reference_node_pool, newexpr);
1196 newexpr->base.ann = NULL;
1197 vn_lookup_or_add_with_vuses (newexpr, newvuses);
1201 phi_trans_add (oldexpr, expr, pred, newvuses);
1207 case tcc_comparison:
1209 tree oldop1 = TREE_OPERAND (expr, 0);
1210 tree oldval1 = oldop1;
1211 tree oldop2 = TREE_OPERAND (expr, 1);
1212 tree oldval2 = oldop2;
1217 oldop1 = find_leader_in_sets (oldop1, set1, set2);
1218 newop1 = phi_translate_1 (oldop1, set1, set2, pred, phiblock, seen);
1222 oldop2 = find_leader_in_sets (oldop2, set1, set2);
1223 newop2 = phi_translate_1 (oldop2, set1, set2, pred, phiblock, seen);
1226 if (newop1 != oldop1 || newop2 != oldop2)
1229 newexpr = (tree) pool_alloc (binary_node_pool);
1230 memcpy (newexpr, expr, tree_size (expr));
1231 TREE_OPERAND (newexpr, 0) = newop1 == oldop1 ? oldval1 : get_value_handle (newop1);
1232 TREE_OPERAND (newexpr, 1) = newop2 == oldop2 ? oldval2 : get_value_handle (newop2);
1233 t = fully_constant_expression (newexpr);
1236 pool_free (binary_node_pool, newexpr);
1241 newexpr->base.ann = NULL;
1242 vn_lookup_or_add (newexpr);
1246 phi_trans_add (oldexpr, expr, pred, NULL);
1252 tree oldop1 = TREE_OPERAND (expr, 0);
1256 oldop1 = find_leader_in_sets (oldop1, set1, set2);
1257 newop1 = phi_translate_1 (oldop1, set1, set2, pred, phiblock, seen);
1260 if (newop1 != oldop1)
1263 newexpr = (tree) pool_alloc (unary_node_pool);
1264 memcpy (newexpr, expr, tree_size (expr));
1265 TREE_OPERAND (newexpr, 0) = get_value_handle (newop1);
1266 t = fully_constant_expression (newexpr);
1269 pool_free (unary_node_pool, newexpr);
1274 newexpr->base.ann = NULL;
1275 vn_lookup_or_add (newexpr);
1279 phi_trans_add (oldexpr, expr, pred, NULL);
1283 case tcc_exceptional:
1288 gcc_assert (TREE_CODE (expr) == SSA_NAME);
1290 def_stmt = SSA_NAME_DEF_STMT (expr);
1291 if (TREE_CODE (def_stmt) == PHI_NODE
1292 && bb_for_stmt (def_stmt) == phiblock)
1297 e = find_edge (pred, bb_for_stmt (phi));
1301 tree def = PHI_ARG_DEF (phi, e->dest_idx);
1303 if (is_gimple_min_invariant (def))
1306 if (is_undefined_value (def))
1309 val = get_value_handle (def);
1321 /* Translate EXPR using phis in PHIBLOCK, so that it has the values of
1323 Return NULL if we can't find a leader for each part of the
1324 translated expression. */
1327 phi_translate (tree expr, bitmap_set_t set1, bitmap_set_t set2,
1328 basic_block pred, basic_block phiblock)
1330 bitmap_clear (seen_during_translate);
1331 return phi_translate_1 (expr, set1, set2, pred, phiblock,
1332 seen_during_translate);
1335 /* For each expression in SET, translate the value handles through phi nodes
1336 in PHIBLOCK using edge PHIBLOCK->PRED, and store the resulting
1337 expressions in DEST. */
1340 phi_translate_set (bitmap_set_t dest, bitmap_set_t set, basic_block pred,
1341 basic_block phiblock)
1343 VEC (tree, heap) *exprs;
1347 if (!phi_nodes (phiblock))
1349 bitmap_set_copy (dest, set);
1353 exprs = sorted_array_from_bitmap_set (set);
1354 for (i = 0; VEC_iterate (tree, exprs, i, expr); i++)
1357 translated = phi_translate (expr, set, NULL, pred, phiblock);
1359 /* Don't add constants or empty translations to the cache, since
1360 we won't look them up that way, or use the result, anyway. */
1361 if (translated && !is_gimple_min_invariant (translated))
1363 tree vh = get_value_handle (translated);
1364 VEC (tree, gc) *vuses;
1366 /* The value handle itself may also be an invariant, in
1367 which case, it has no vuses. */
1368 vuses = !is_gimple_min_invariant (vh)
1369 ? VALUE_HANDLE_VUSES (vh) : NULL;
1370 phi_trans_add (expr, translated, pred, vuses);
1373 if (translated != NULL)
1374 bitmap_value_insert_into_set (dest, translated);
1376 VEC_free (tree, heap, exprs);
1379 /* Find the leader for a value (i.e., the name representing that
1380 value) in a given set, and return it. Return NULL if no leader is
1384 bitmap_find_leader (bitmap_set_t set, tree val)
1389 if (constant_expr_p (val))
1392 if (bitmap_set_contains_value (set, val))
1394 /* Rather than walk the entire bitmap of expressions, and see
1395 whether any of them has the value we are looking for, we look
1396 at the reverse mapping, which tells us the set of expressions
1397 that have a given value (IE value->expressions with that
1398 value) and see if any of those expressions are in our set.
1399 The number of expressions per value is usually significantly
1400 less than the number of expressions in the set. In fact, for
1401 large testcases, doing it this way is roughly 5-10x faster
1402 than walking the bitmap.
1403 If this is somehow a significant lose for some cases, we can
1404 choose which set to walk based on which set is smaller. */
1407 bitmap_set_t exprset = VALUE_HANDLE_EXPR_SET (val);
1409 EXECUTE_IF_AND_IN_BITMAP (exprset->expressions,
1410 set->expressions, 0, i, bi)
1411 return expression_for_id (i);
1416 /* Determine if VALUE, a memory operation, is ANTIC_IN at the top of
1417 BLOCK by seeing if it is not killed in the block. Note that we are
1418 only determining whether there is a store that kills it. Because
1419 of the order in which clean iterates over values, we are guaranteed
1420 that altered operands will have caused us to be eliminated from the
1421 ANTIC_IN set already. */
1424 value_dies_in_block_x (tree vh, basic_block block)
1428 VEC (tree, gc) *vuses = VALUE_HANDLE_VUSES (vh);
1430 /* Conservatively, a value dies if it's vuses are defined in this
1431 block, unless they come from phi nodes (which are merge operations,
1432 rather than stores. */
1433 for (i = 0; VEC_iterate (tree, vuses, i, vuse); i++)
1435 tree def = SSA_NAME_DEF_STMT (vuse);
1437 if (bb_for_stmt (def) != block)
1439 if (TREE_CODE (def) == PHI_NODE)
1446 /* Determine if the expression EXPR is valid in SET1 U SET2.
1447 ONLY SET2 CAN BE NULL.
1448 This means that we have a leader for each part of the expression
1449 (if it consists of values), or the expression is an SSA_NAME.
1450 For loads/calls, we also see if the vuses are killed in this block.
1452 NB: We never should run into a case where we have SSA_NAME +
1453 SSA_NAME or SSA_NAME + value. The sets valid_in_sets is called on,
1454 the ANTIC sets, will only ever have SSA_NAME's or value expressions
1455 (IE VALUE1 + VALUE2, *VALUE1, VALUE1 < VALUE2) */
1457 #define union_contains_value(SET1, SET2, VAL) \
1458 (bitmap_set_contains_value ((SET1), (VAL)) \
1459 || ((SET2) && bitmap_set_contains_value ((SET2), (VAL))))
1462 valid_in_sets (bitmap_set_t set1, bitmap_set_t set2, tree expr,
1465 tree vh = get_value_handle (expr);
1466 switch (TREE_CODE_CLASS (TREE_CODE (expr)))
1469 case tcc_comparison:
1471 tree op1 = TREE_OPERAND (expr, 0);
1472 tree op2 = TREE_OPERAND (expr, 1);
1474 return union_contains_value (set1, set2, op1)
1475 && union_contains_value (set1, set2, op2);
1480 tree op1 = TREE_OPERAND (expr, 0);
1481 return union_contains_value (set1, set2, op1);
1484 case tcc_expression:
1489 if (TREE_CODE (expr) == CALL_EXPR)
1491 tree fn = CALL_EXPR_FN (expr);
1492 tree sc = CALL_EXPR_STATIC_CHAIN (expr);
1494 call_expr_arg_iterator iter;
1496 /* Check the non-argument operands first. */
1497 if (!union_contains_value (set1, set2, fn)
1498 || (sc && !union_contains_value (set1, set2, sc)))
1501 /* Now check the operands. */
1502 FOR_EACH_CALL_EXPR_ARG (arg, iter, expr)
1504 if (!union_contains_value (set1, set2, arg))
1507 return !value_dies_in_block_x (vh, block);
1514 if (TREE_CODE (expr) == INDIRECT_REF
1515 || TREE_CODE (expr) == COMPONENT_REF
1516 || TREE_CODE (expr) == ARRAY_REF)
1518 tree op0 = TREE_OPERAND (expr, 0);
1519 gcc_assert (is_gimple_min_invariant (op0)
1520 || TREE_CODE (op0) == VALUE_HANDLE);
1521 if (!union_contains_value (set1, set2, op0))
1523 if (TREE_CODE (expr) == ARRAY_REF)
1525 tree op1 = TREE_OPERAND (expr, 1);
1526 tree op2 = TREE_OPERAND (expr, 2);
1527 tree op3 = TREE_OPERAND (expr, 3);
1528 gcc_assert (is_gimple_min_invariant (op1)
1529 || TREE_CODE (op1) == VALUE_HANDLE);
1530 if (!union_contains_value (set1, set2, op1))
1532 gcc_assert (!op2 || is_gimple_min_invariant (op2)
1533 || TREE_CODE (op2) == VALUE_HANDLE);
1535 && !union_contains_value (set1, set2, op2))
1537 gcc_assert (!op3 || is_gimple_min_invariant (op3)
1538 || TREE_CODE (op3) == VALUE_HANDLE);
1540 && !union_contains_value (set1, set2, op3))
1543 return !value_dies_in_block_x (vh, block);
1548 case tcc_exceptional:
1550 gcc_assert (TREE_CODE (expr) == SSA_NAME);
1551 return bitmap_set_contains_expr (AVAIL_OUT (block), expr);
1554 case tcc_declaration:
1555 return !value_dies_in_block_x (vh, block);
1558 /* No other cases should be encountered. */
1563 /* Clean the set of expressions that are no longer valid in SET1 or
1564 SET2. This means expressions that are made up of values we have no
1565 leaders for in SET1 or SET2. This version is used for partial
1566 anticipation, which means it is not valid in either ANTIC_IN or
1570 dependent_clean (bitmap_set_t set1, bitmap_set_t set2, basic_block block)
1572 VEC (tree, heap) *exprs = sorted_array_from_bitmap_set (set1);
1576 for (i = 0; VEC_iterate (tree, exprs, i, expr); i++)
1578 if (!valid_in_sets (set1, set2, expr, block))
1579 bitmap_remove_from_set (set1, expr);
1581 VEC_free (tree, heap, exprs);
1584 /* Clean the set of expressions that are no longer valid in SET. This
1585 means expressions that are made up of values we have no leaders for
1589 clean (bitmap_set_t set, basic_block block)
1591 VEC (tree, heap) *exprs = sorted_array_from_bitmap_set (set);
1595 for (i = 0; VEC_iterate (tree, exprs, i, expr); i++)
1597 if (!valid_in_sets (set, NULL, expr, block))
1598 bitmap_remove_from_set (set, expr);
1600 VEC_free (tree, heap, exprs);
1603 static sbitmap has_abnormal_preds;
1605 /* List of blocks that may have changed during ANTIC computation and
1606 thus need to be iterated over. */
1608 static sbitmap changed_blocks;
1610 /* Decide whether to defer a block for a later iteration, or PHI
1611 translate SOURCE to DEST using phis in PHIBLOCK. Return false if we
1612 should defer the block, and true if we processed it. */
1615 defer_or_phi_translate_block (bitmap_set_t dest, bitmap_set_t source,
1616 basic_block block, basic_block phiblock)
1618 if (!BB_VISITED (phiblock))
1620 SET_BIT (changed_blocks, block->index);
1621 BB_VISITED (block) = 0;
1622 BB_DEFERRED (block) = 1;
1626 phi_translate_set (dest, source, block, phiblock);
1630 /* Compute the ANTIC set for BLOCK.
1632 If succs(BLOCK) > 1 then
1633 ANTIC_OUT[BLOCK] = intersection of ANTIC_IN[b] for all succ(BLOCK)
1634 else if succs(BLOCK) == 1 then
1635 ANTIC_OUT[BLOCK] = phi_translate (ANTIC_IN[succ(BLOCK)])
1637 ANTIC_IN[BLOCK] = clean(ANTIC_OUT[BLOCK] U EXP_GEN[BLOCK] - TMP_GEN[BLOCK])
1641 compute_antic_aux (basic_block block, bool block_has_abnormal_pred_edge)
1643 bool changed = false;
1644 bitmap_set_t S, old, ANTIC_OUT;
1650 old = ANTIC_OUT = S = NULL;
1651 BB_VISITED (block) = 1;
1653 /* If any edges from predecessors are abnormal, antic_in is empty,
1655 if (block_has_abnormal_pred_edge)
1656 goto maybe_dump_sets;
1658 old = ANTIC_IN (block);
1659 ANTIC_OUT = bitmap_set_new ();
1661 /* If the block has no successors, ANTIC_OUT is empty. */
1662 if (EDGE_COUNT (block->succs) == 0)
1664 /* If we have one successor, we could have some phi nodes to
1665 translate through. */
1666 else if (single_succ_p (block))
1668 basic_block succ_bb = single_succ (block);
1670 /* We trade iterations of the dataflow equations for having to
1671 phi translate the maximal set, which is incredibly slow
1672 (since the maximal set often has 300+ members, even when you
1673 have a small number of blocks).
1674 Basically, we defer the computation of ANTIC for this block
1675 until we have processed it's successor, which will inevitably
1676 have a *much* smaller set of values to phi translate once
1677 clean has been run on it.
1678 The cost of doing this is that we technically perform more
1679 iterations, however, they are lower cost iterations.
1681 Timings for PRE on tramp3d-v4:
1682 without maximal set fix: 11 seconds
1683 with maximal set fix/without deferring: 26 seconds
1684 with maximal set fix/with deferring: 11 seconds
1687 if (!defer_or_phi_translate_block (ANTIC_OUT, ANTIC_IN (succ_bb),
1691 goto maybe_dump_sets;
1694 /* If we have multiple successors, we take the intersection of all of
1695 them. Note that in the case of loop exit phi nodes, we may have
1696 phis to translate through. */
1699 VEC(basic_block, heap) * worklist;
1701 basic_block bprime, first;
1703 worklist = VEC_alloc (basic_block, heap, EDGE_COUNT (block->succs));
1704 FOR_EACH_EDGE (e, ei, block->succs)
1705 VEC_quick_push (basic_block, worklist, e->dest);
1706 first = VEC_index (basic_block, worklist, 0);
1708 if (phi_nodes (first))
1710 bitmap_set_t from = ANTIC_IN (first);
1712 if (!BB_VISITED (first))
1714 phi_translate_set (ANTIC_OUT, from, block, first);
1718 if (!BB_VISITED (first))
1719 bitmap_set_copy (ANTIC_OUT, maximal_set);
1721 bitmap_set_copy (ANTIC_OUT, ANTIC_IN (first));
1724 for (i = 1; VEC_iterate (basic_block, worklist, i, bprime); i++)
1726 if (phi_nodes (bprime))
1728 bitmap_set_t tmp = bitmap_set_new ();
1729 bitmap_set_t from = ANTIC_IN (bprime);
1731 if (!BB_VISITED (bprime))
1733 phi_translate_set (tmp, from, block, bprime);
1734 bitmap_set_and (ANTIC_OUT, tmp);
1735 bitmap_set_free (tmp);
1739 if (!BB_VISITED (bprime))
1740 bitmap_set_and (ANTIC_OUT, maximal_set);
1742 bitmap_set_and (ANTIC_OUT, ANTIC_IN (bprime));
1745 VEC_free (basic_block, heap, worklist);
1748 /* Generate ANTIC_OUT - TMP_GEN. */
1749 S = bitmap_set_subtract (ANTIC_OUT, TMP_GEN (block));
1751 /* Start ANTIC_IN with EXP_GEN - TMP_GEN. */
1752 ANTIC_IN (block) = bitmap_set_subtract (EXP_GEN (block),
1755 /* Then union in the ANTIC_OUT - TMP_GEN values,
1756 to get ANTIC_OUT U EXP_GEN - TMP_GEN */
1757 FOR_EACH_EXPR_ID_IN_SET (S, bii, bi)
1758 bitmap_value_insert_into_set (ANTIC_IN (block),
1759 expression_for_id (bii));
1761 clean (ANTIC_IN (block), block);
1763 /* !old->expressions can happen when we deferred a block. */
1764 if (!old->expressions || !bitmap_set_equal (old, ANTIC_IN (block)))
1767 SET_BIT (changed_blocks, block->index);
1768 FOR_EACH_EDGE (e, ei, block->preds)
1769 SET_BIT (changed_blocks, e->src->index);
1772 RESET_BIT (changed_blocks, block->index);
1775 if (dump_file && (dump_flags & TDF_DETAILS))
1777 if (!BB_DEFERRED (block) || BB_VISITED (block))
1780 print_bitmap_set (dump_file, ANTIC_OUT, "ANTIC_OUT", block->index);
1782 print_bitmap_set (dump_file, ANTIC_IN (block), "ANTIC_IN",
1786 print_bitmap_set (dump_file, S, "S", block->index);
1791 "Block %d was deferred for a future iteration.\n",
1796 bitmap_set_free (old);
1798 bitmap_set_free (S);
1800 bitmap_set_free (ANTIC_OUT);
1804 /* Compute PARTIAL_ANTIC for BLOCK.
1806 If succs(BLOCK) > 1 then
1807 PA_OUT[BLOCK] = value wise union of PA_IN[b] + all ANTIC_IN not
1808 in ANTIC_OUT for all succ(BLOCK)
1809 else if succs(BLOCK) == 1 then
1810 PA_OUT[BLOCK] = phi_translate (PA_IN[succ(BLOCK)])
1812 PA_IN[BLOCK] = dependent_clean(PA_OUT[BLOCK] - TMP_GEN[BLOCK]
1817 compute_partial_antic_aux (basic_block block,
1818 bool block_has_abnormal_pred_edge)
1820 bool changed = false;
1821 bitmap_set_t old_PA_IN;
1822 bitmap_set_t PA_OUT;
1826 old_PA_IN = PA_OUT = NULL;
1828 /* If any edges from predecessors are abnormal, antic_in is empty,
1830 if (block_has_abnormal_pred_edge)
1831 goto maybe_dump_sets;
1833 old_PA_IN = PA_IN (block);
1834 PA_OUT = bitmap_set_new ();
1836 /* If the block has no successors, ANTIC_OUT is empty. */
1837 if (EDGE_COUNT (block->succs) == 0)
1839 /* If we have one successor, we could have some phi nodes to
1840 translate through. Note that we can't phi translate across DFS
1841 back edges in partial antic, because it uses a union operation on
1842 the successors. For recurrences like IV's, we will end up
1843 generating a new value in the set on each go around (i + 3 (VH.1)
1844 VH.1 + 1 (VH.2), VH.2 + 1 (VH.3), etc), forever. */
1845 else if (single_succ_p (block))
1847 basic_block succ = single_succ (block);
1848 if (!(single_succ_edge (block)->flags & EDGE_DFS_BACK))
1849 phi_translate_set (PA_OUT, PA_IN (succ), block, succ);
1851 /* If we have multiple successors, we take the union of all of
1855 VEC(basic_block, heap) * worklist;
1859 worklist = VEC_alloc (basic_block, heap, EDGE_COUNT (block->succs));
1860 FOR_EACH_EDGE (e, ei, block->succs)
1862 if (e->flags & EDGE_DFS_BACK)
1864 VEC_quick_push (basic_block, worklist, e->dest);
1866 if (VEC_length (basic_block, worklist) > 0)
1868 for (i = 0; VEC_iterate (basic_block, worklist, i, bprime); i++)
1873 FOR_EACH_EXPR_ID_IN_SET (ANTIC_IN (bprime), i, bi)
1874 bitmap_value_insert_into_set (PA_OUT,
1875 expression_for_id (i));
1876 if (phi_nodes (bprime))
1878 bitmap_set_t pa_in = bitmap_set_new ();
1879 phi_translate_set (pa_in, PA_IN (bprime), block, bprime);
1880 FOR_EACH_EXPR_ID_IN_SET (pa_in, i, bi)
1881 bitmap_value_insert_into_set (PA_OUT,
1882 expression_for_id (i));
1883 bitmap_set_free (pa_in);
1886 FOR_EACH_EXPR_ID_IN_SET (PA_IN (bprime), i, bi)
1887 bitmap_value_insert_into_set (PA_OUT,
1888 expression_for_id (i));
1891 VEC_free (basic_block, heap, worklist);
1894 /* PA_IN starts with PA_OUT - TMP_GEN.
1895 Then we subtract things from ANTIC_IN. */
1896 PA_IN (block) = bitmap_set_subtract (PA_OUT, TMP_GEN (block));
1898 /* For partial antic, we want to put back in the phi results, since
1899 we will properly avoid making them partially antic over backedges. */
1900 bitmap_ior_into (PA_IN (block)->values, PHI_GEN (block)->values);
1901 bitmap_ior_into (PA_IN (block)->expressions, PHI_GEN (block)->expressions);
1903 /* PA_IN[block] = PA_IN[block] - ANTIC_IN[block] */
1904 bitmap_set_subtract_values (PA_IN (block), ANTIC_IN (block));
1906 dependent_clean (PA_IN (block), ANTIC_IN (block), block);
1908 if (!bitmap_set_equal (old_PA_IN, PA_IN (block)))
1911 SET_BIT (changed_blocks, block->index);
1912 FOR_EACH_EDGE (e, ei, block->preds)
1913 SET_BIT (changed_blocks, e->src->index);
1916 RESET_BIT (changed_blocks, block->index);
1919 if (dump_file && (dump_flags & TDF_DETAILS))
1922 print_bitmap_set (dump_file, PA_OUT, "PA_OUT", block->index);
1924 print_bitmap_set (dump_file, PA_IN (block), "PA_IN", block->index);
1927 bitmap_set_free (old_PA_IN);
1929 bitmap_set_free (PA_OUT);
1933 /* Compute ANTIC and partial ANTIC sets. */
1936 compute_antic (void)
1938 bool changed = true;
1939 int num_iterations = 0;
1943 /* If any predecessor edges are abnormal, we punt, so antic_in is empty.
1944 We pre-build the map of blocks with incoming abnormal edges here. */
1945 has_abnormal_preds = sbitmap_alloc (last_basic_block);
1946 sbitmap_zero (has_abnormal_preds);
1953 FOR_EACH_EDGE (e, ei, block->preds)
1955 e->flags &= ~EDGE_DFS_BACK;
1956 if (e->flags & EDGE_ABNORMAL)
1958 SET_BIT (has_abnormal_preds, block->index);
1963 BB_VISITED (block) = 0;
1964 BB_DEFERRED (block) = 0;
1965 /* While we are here, give empty ANTIC_IN sets to each block. */
1966 ANTIC_IN (block) = bitmap_set_new ();
1967 PA_IN (block) = bitmap_set_new ();
1970 /* At the exit block we anticipate nothing. */
1971 ANTIC_IN (EXIT_BLOCK_PTR) = bitmap_set_new ();
1972 BB_VISITED (EXIT_BLOCK_PTR) = 1;
1973 PA_IN (EXIT_BLOCK_PTR) = bitmap_set_new ();
1975 changed_blocks = sbitmap_alloc (last_basic_block + 1);
1976 sbitmap_ones (changed_blocks);
1979 if (dump_file && (dump_flags & TDF_DETAILS))
1980 fprintf (dump_file, "Starting iteration %d\n", num_iterations);
1983 for (i = 0; i < last_basic_block - NUM_FIXED_BLOCKS; i++)
1985 if (TEST_BIT (changed_blocks, postorder[i]))
1987 basic_block block = BASIC_BLOCK (postorder[i]);
1988 changed |= compute_antic_aux (block,
1989 TEST_BIT (has_abnormal_preds,
1993 /* Theoretically possible, but *highly* unlikely. */
1994 gcc_assert (num_iterations < 50);
1997 if (dump_file && (dump_flags & TDF_STATS))
1998 fprintf (dump_file, "compute_antic required %d iterations\n",
2001 if (do_partial_partial)
2003 sbitmap_ones (changed_blocks);
2004 mark_dfs_back_edges ();
2009 if (dump_file && (dump_flags & TDF_DETAILS))
2010 fprintf (dump_file, "Starting iteration %d\n", num_iterations);
2013 for (i = 0; i < last_basic_block - NUM_FIXED_BLOCKS; i++)
2015 if (TEST_BIT (changed_blocks, postorder[i]))
2017 basic_block block = BASIC_BLOCK (postorder[i]);
2019 |= compute_partial_antic_aux (block,
2020 TEST_BIT (has_abnormal_preds,
2024 /* Theoretically possible, but *highly* unlikely. */
2025 gcc_assert (num_iterations < 50);
2027 if (dump_file && (dump_flags & TDF_STATS))
2028 fprintf (dump_file, "compute_partial_antic required %d iterations\n",
2031 sbitmap_free (has_abnormal_preds);
2032 sbitmap_free (changed_blocks);
2035 /* Return true if we can value number the call in STMT. This is true
2036 if we have a pure or constant call. */
2039 can_value_number_call (tree stmt)
2041 tree call = get_call_expr_in (stmt);
2043 if (call_expr_flags (call) & (ECF_PURE | ECF_CONST))
2048 /* Return true if OP is an exception handler related operation, such as
2049 FILTER_EXPRor EXC_PTR_EXPR. */
2052 is_exception_related (tree op)
2054 return TREE_CODE (op) == FILTER_EXPR || TREE_CODE (op) == EXC_PTR_EXPR;
2057 /* Return true if OP is a tree which we can perform value numbering
2061 can_value_number_operation (tree op)
2063 return (UNARY_CLASS_P (op)
2064 && !is_exception_related (TREE_OPERAND (op, 0)))
2065 || BINARY_CLASS_P (op)
2066 || COMPARISON_CLASS_P (op)
2067 || 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)
2083 || TREE_CODE (op) == INDIRECT_REF
2084 || TREE_CODE (op) == COMPONENT_REF
2085 || TREE_CODE (op) == CALL_EXPR
2086 || TREE_CODE (op) == ARRAY_REF;
2090 /* Inserted expressions are placed onto this worklist, which is used
2091 for performing quick dead code elimination of insertions we made
2092 that didn't turn out to be necessary. */
2093 static VEC(tree,heap) *inserted_exprs;
2095 /* Pool allocated fake store expressions are placed onto this
2096 worklist, which, after performing dead code elimination, is walked
2097 to see which expressions need to be put into GC'able memory */
2098 static VEC(tree, heap) *need_creation;
2100 /* For COMPONENT_REF's and ARRAY_REF's, we can't have any intermediates for the
2101 COMPONENT_REF or INDIRECT_REF or ARRAY_REF portion, because we'd end up with
2102 trying to rename aggregates into ssa form directly, which is a no
2105 Thus, this routine doesn't create temporaries, it just builds a
2106 single access expression for the array, calling
2107 find_or_generate_expression to build the innermost pieces.
2109 This function is a subroutine of create_expression_by_pieces, and
2110 should not be called on it's own unless you really know what you
2114 create_component_ref_by_pieces (basic_block block, tree expr, tree stmts)
2119 if (TREE_CODE (genop) == VALUE_HANDLE)
2121 tree found = bitmap_find_leader (AVAIL_OUT (block), expr);
2126 if (TREE_CODE (genop) == VALUE_HANDLE)
2128 bitmap_set_t exprset = VALUE_HANDLE_EXPR_SET (expr);
2129 unsigned int firstbit = bitmap_first_set_bit (exprset->expressions);
2130 genop = expression_for_id (firstbit);
2133 switch TREE_CODE (genop)
2139 op0 = create_component_ref_by_pieces (block,
2140 TREE_OPERAND (genop, 0),
2142 op1 = TREE_OPERAND (genop, 1);
2143 if (TREE_CODE (op1) == VALUE_HANDLE)
2144 op1 = find_or_generate_expression (block, op1, stmts);
2145 op2 = TREE_OPERAND (genop, 2);
2146 if (op2 && TREE_CODE (op2) == VALUE_HANDLE)
2147 op2 = find_or_generate_expression (block, op2, stmts);
2148 op3 = TREE_OPERAND (genop, 3);
2149 if (op3 && TREE_CODE (op3) == VALUE_HANDLE)
2150 op3 = find_or_generate_expression (block, op3, stmts);
2151 folded = build4 (ARRAY_REF, TREE_TYPE (genop), op0, op1,
2159 op0 = create_component_ref_by_pieces (block,
2160 TREE_OPERAND (genop, 0),
2162 /* op1 should be a FIELD_DECL, which are represented by
2164 op1 = TREE_OPERAND (genop, 1);
2165 folded = fold_build3 (COMPONENT_REF, TREE_TYPE (genop), op0, op1,
2172 tree op1 = TREE_OPERAND (genop, 0);
2173 tree genop1 = find_or_generate_expression (block, op1, stmts);
2175 folded = fold_build1 (TREE_CODE (genop), TREE_TYPE (genop),
2193 /* Find a leader for an expression, or generate one using
2194 create_expression_by_pieces if it's ANTIC but
2196 BLOCK is the basic_block we are looking for leaders in.
2197 EXPR is the expression to find a leader or generate for.
2198 STMTS is the statement list to put the inserted expressions on.
2199 Returns the SSA_NAME of the LHS of the generated expression or the
2203 find_or_generate_expression (basic_block block, tree expr, tree stmts)
2205 tree genop = bitmap_find_leader (AVAIL_OUT (block), expr);
2207 /* If it's still NULL, it must be a complex expression, so generate
2211 bitmap_set_t exprset = VALUE_HANDLE_EXPR_SET (expr);
2212 bool handled = false;
2216 /* We will hit cases where we have SSA_NAME's in exprset before
2217 other operations, because we may have come up with the SCCVN
2218 value before getting to the RHS of the expression. */
2219 FOR_EACH_EXPR_ID_IN_SET (exprset, i, bi)
2221 genop = expression_for_id (i);
2222 if (can_PRE_operation (genop))
2225 genop = create_expression_by_pieces (block, genop, stmts);
2229 gcc_assert (handled);
2234 #define NECESSARY(stmt) stmt->base.asm_written_flag
2235 /* Create an expression in pieces, so that we can handle very complex
2236 expressions that may be ANTIC, but not necessary GIMPLE.
2237 BLOCK is the basic block the expression will be inserted into,
2238 EXPR is the expression to insert (in value form)
2239 STMTS is a statement list to append the necessary insertions into.
2241 This function will die if we hit some value that shouldn't be
2242 ANTIC but is (IE there is no leader for it, or its components).
2243 This function may also generate expressions that are themselves
2244 partially or fully redundant. Those that are will be either made
2245 fully redundant during the next iteration of insert (for partially
2246 redundant ones), or eliminated by eliminate (for fully redundant
2250 create_expression_by_pieces (basic_block block, tree expr, tree stmts)
2253 tree folded, forced_stmts, newexpr;
2255 tree_stmt_iterator tsi;
2257 switch (TREE_CODE_CLASS (TREE_CODE (expr)))
2266 gcc_assert (TREE_CODE (expr) == CALL_EXPR);
2268 fn = CALL_EXPR_FN (expr);
2269 sc = CALL_EXPR_STATIC_CHAIN (expr);
2271 genfn = find_or_generate_expression (block, fn, stmts);
2273 nargs = call_expr_nargs (expr);
2274 buffer = (tree*) alloca (nargs * sizeof (tree));
2276 for (i = 0; i < nargs; i++)
2278 tree arg = CALL_EXPR_ARG (expr, i);
2279 buffer[i] = find_or_generate_expression (block, arg, stmts);
2282 folded = build_call_array (TREE_TYPE (expr), genfn, nargs, buffer);
2284 CALL_EXPR_STATIC_CHAIN (folded) =
2285 find_or_generate_expression (block, sc, stmts);
2286 folded = fold (folded);
2292 if (TREE_CODE (expr) == COMPONENT_REF
2293 || TREE_CODE (expr) == ARRAY_REF)
2295 folded = create_component_ref_by_pieces (block, expr, stmts);
2299 tree op1 = TREE_OPERAND (expr, 0);
2300 tree genop1 = find_or_generate_expression (block, op1, stmts);
2302 folded = fold_build1 (TREE_CODE (expr), TREE_TYPE (expr),
2309 case tcc_comparison:
2311 tree op1 = TREE_OPERAND (expr, 0);
2312 tree op2 = TREE_OPERAND (expr, 1);
2313 tree genop1 = find_or_generate_expression (block, op1, stmts);
2314 tree genop2 = find_or_generate_expression (block, op2, stmts);
2315 folded = fold_build2 (TREE_CODE (expr), TREE_TYPE (expr),
2322 tree op1 = TREE_OPERAND (expr, 0);
2323 tree genop1 = find_or_generate_expression (block, op1, stmts);
2324 folded = fold_build1 (TREE_CODE (expr), TREE_TYPE (expr),
2333 /* Force the generated expression to be a sequence of GIMPLE
2335 We have to call unshare_expr because force_gimple_operand may
2336 modify the tree we pass to it. */
2337 newexpr = force_gimple_operand (unshare_expr (folded), &forced_stmts,
2340 /* If we have any intermediate expressions to the value sets, add them
2341 to the value sets and chain them on in the instruction stream. */
2344 tsi = tsi_start (forced_stmts);
2345 for (; !tsi_end_p (tsi); tsi_next (&tsi))
2347 tree stmt = tsi_stmt (tsi);
2348 tree forcedname = GIMPLE_STMT_OPERAND (stmt, 0);
2349 tree forcedexpr = GIMPLE_STMT_OPERAND (stmt, 1);
2350 tree val = vn_lookup_or_add (forcedexpr);
2352 VEC_safe_push (tree, heap, inserted_exprs, stmt);
2353 VN_INFO_GET (forcedname)->valnum = forcedname;
2354 vn_add (forcedname, val);
2355 bitmap_value_replace_in_set (NEW_SETS (block), forcedname);
2356 bitmap_value_replace_in_set (AVAIL_OUT (block), forcedname);
2357 mark_symbols_for_renaming (stmt);
2359 tsi = tsi_last (stmts);
2360 tsi_link_after (&tsi, forced_stmts, TSI_CONTINUE_LINKING);
2363 /* Build and insert the assignment of the end result to the temporary
2364 that we will return. */
2365 if (!pretemp || TREE_TYPE (expr) != TREE_TYPE (pretemp))
2367 pretemp = create_tmp_var (TREE_TYPE (expr), "pretmp");
2368 get_var_ann (pretemp);
2372 add_referenced_var (temp);
2374 if (TREE_CODE (TREE_TYPE (expr)) == COMPLEX_TYPE
2375 || TREE_CODE (TREE_TYPE (expr)) == VECTOR_TYPE)
2376 DECL_GIMPLE_REG_P (temp) = 1;
2378 newexpr = build_gimple_modify_stmt (temp, newexpr);
2379 name = make_ssa_name (temp, newexpr);
2380 GIMPLE_STMT_OPERAND (newexpr, 0) = name;
2381 NECESSARY (newexpr) = 0;
2383 tsi = tsi_last (stmts);
2384 tsi_link_after (&tsi, newexpr, TSI_CONTINUE_LINKING);
2385 VEC_safe_push (tree, heap, inserted_exprs, newexpr);
2387 /* All the symbols in NEWEXPR should be put into SSA form. */
2388 mark_symbols_for_renaming (newexpr);
2390 /* Add a value handle to the temporary.
2391 The value may already exist in either NEW_SETS, or AVAIL_OUT, because
2392 we are creating the expression by pieces, and this particular piece of
2393 the expression may have been represented. There is no harm in replacing
2395 v = get_value_handle (expr);
2397 VN_INFO_GET (name)->valnum = name;
2398 get_or_alloc_expression_id (name);
2399 bitmap_value_replace_in_set (NEW_SETS (block), name);
2400 bitmap_value_replace_in_set (AVAIL_OUT (block), name);
2402 pre_stats.insertions++;
2403 if (dump_file && (dump_flags & TDF_DETAILS))
2405 fprintf (dump_file, "Inserted ");
2406 print_generic_expr (dump_file, newexpr, 0);
2407 fprintf (dump_file, " in predecessor %d\n", block->index);
2413 /* Insert the to-be-made-available values of expression EXPRNUM for each
2414 predecessor, stored in AVAIL, into the predecessors of BLOCK, and
2415 merge the result with a phi node, given the same value handle as
2416 NODE. Return true if we have inserted new stuff. */
2419 insert_into_preds_of_block (basic_block block, unsigned int exprnum,
2422 tree expr = expression_for_id (exprnum);
2423 tree val = get_value_handle (expr);
2425 bool insertions = false;
2430 tree type = TREE_TYPE (avail[EDGE_PRED (block, 0)->src->index]);
2433 if (dump_file && (dump_flags & TDF_DETAILS))
2435 fprintf (dump_file, "Found partial redundancy for expression ");
2436 print_generic_expr (dump_file, expr, 0);
2437 fprintf (dump_file, " (");
2438 print_generic_expr (dump_file, val, 0);
2439 fprintf (dump_file, ")");
2440 fprintf (dump_file, "\n");
2443 /* Make sure we aren't creating an induction variable. */
2444 if (block->loop_depth > 0 && EDGE_COUNT (block->preds) == 2
2445 && TREE_CODE_CLASS (TREE_CODE (expr)) != tcc_reference )
2447 bool firstinsideloop = false;
2448 bool secondinsideloop = false;
2449 firstinsideloop = flow_bb_inside_loop_p (block->loop_father,
2450 EDGE_PRED (block, 0)->src);
2451 secondinsideloop = flow_bb_inside_loop_p (block->loop_father,
2452 EDGE_PRED (block, 1)->src);
2453 /* Induction variables only have one edge inside the loop. */
2454 if (firstinsideloop ^ secondinsideloop)
2456 if (dump_file && (dump_flags & TDF_DETAILS))
2457 fprintf (dump_file, "Skipping insertion of phi for partial redundancy: Looks like an induction variable\n");
2463 /* Make the necessary insertions. */
2464 FOR_EACH_EDGE (pred, ei, block->preds)
2466 tree stmts = alloc_stmt_list ();
2469 eprime = avail[bprime->index];
2471 if (can_PRE_operation (eprime))
2473 builtexpr = create_expression_by_pieces (bprime,
2476 gcc_assert (!(pred->flags & EDGE_ABNORMAL));
2477 bsi_insert_on_edge (pred, stmts);
2478 avail[bprime->index] = builtexpr;
2482 /* If we didn't want a phi node, and we made insertions, we still have
2483 inserted new stuff, and thus return true. If we didn't want a phi node,
2484 and didn't make insertions, we haven't added anything new, so return
2486 if (nophi && insertions)
2488 else if (nophi && !insertions)
2491 /* Now build a phi for the new variable. */
2492 if (!prephitemp || TREE_TYPE (prephitemp) != type)
2494 prephitemp = create_tmp_var (type, "prephitmp");
2495 get_var_ann (prephitemp);
2499 add_referenced_var (temp);
2502 if (TREE_CODE (type) == COMPLEX_TYPE
2503 || TREE_CODE (type) == VECTOR_TYPE)
2504 DECL_GIMPLE_REG_P (temp) = 1;
2505 temp = create_phi_node (temp, block);
2507 NECESSARY (temp) = 0;
2508 VN_INFO_GET (PHI_RESULT (temp))->valnum = PHI_RESULT (temp);
2510 VEC_safe_push (tree, heap, inserted_exprs, temp);
2511 FOR_EACH_EDGE (pred, ei, block->preds)
2512 add_phi_arg (temp, avail[pred->src->index], pred);
2514 vn_add (PHI_RESULT (temp), val);
2516 /* The value should *not* exist in PHI_GEN, or else we wouldn't be doing
2517 this insertion, since we test for the existence of this value in PHI_GEN
2518 before proceeding with the partial redundancy checks in insert_aux.
2520 The value may exist in AVAIL_OUT, in particular, it could be represented
2521 by the expression we are trying to eliminate, in which case we want the
2522 replacement to occur. If it's not existing in AVAIL_OUT, we want it
2525 Similarly, to the PHI_GEN case, the value should not exist in NEW_SETS of
2526 this block, because if it did, it would have existed in our dominator's
2527 AVAIL_OUT, and would have been skipped due to the full redundancy check.
2530 bitmap_insert_into_set (PHI_GEN (block),
2532 bitmap_value_replace_in_set (AVAIL_OUT (block),
2534 bitmap_insert_into_set (NEW_SETS (block),
2537 if (dump_file && (dump_flags & TDF_DETAILS))
2539 fprintf (dump_file, "Created phi ");
2540 print_generic_expr (dump_file, temp, 0);
2541 fprintf (dump_file, " in block %d\n", block->index);
2549 /* Perform insertion of partially redundant values.
2550 For BLOCK, do the following:
2551 1. Propagate the NEW_SETS of the dominator into the current block.
2552 If the block has multiple predecessors,
2553 2a. Iterate over the ANTIC expressions for the block to see if
2554 any of them are partially redundant.
2555 2b. If so, insert them into the necessary predecessors to make
2556 the expression fully redundant.
2557 2c. Insert a new PHI merging the values of the predecessors.
2558 2d. Insert the new PHI, and the new expressions, into the
2560 3. Recursively call ourselves on the dominator children of BLOCK.
2562 Steps 1, 2a, and 3 are done by insert_aux. 2b, 2c and 2d are done by
2563 do_regular_insertion and do_partial_insertion.
2568 do_regular_insertion (basic_block block, basic_block dom)
2570 bool new_stuff = false;
2571 VEC (tree, heap) *exprs = sorted_array_from_bitmap_set (ANTIC_IN (block));
2575 for (i = 0; VEC_iterate (tree, exprs, i, expr); i++)
2577 if (can_PRE_operation (expr) && !AGGREGATE_TYPE_P (TREE_TYPE (expr)))
2581 bool by_some = false;
2582 bool cant_insert = false;
2583 bool all_same = true;
2584 tree first_s = NULL;
2587 tree eprime = NULL_TREE;
2590 val = get_value_handle (expr);
2591 if (bitmap_set_contains_value (PHI_GEN (block), val))
2593 if (bitmap_set_contains_value (AVAIL_OUT (dom), val))
2595 if (dump_file && (dump_flags & TDF_DETAILS))
2596 fprintf (dump_file, "Found fully redundant value\n");
2600 avail = XCNEWVEC (tree, last_basic_block);
2601 FOR_EACH_EDGE (pred, ei, block->preds)
2606 /* This can happen in the very weird case
2607 that our fake infinite loop edges have caused a
2608 critical edge to appear. */
2609 if (EDGE_CRITICAL_P (pred))
2615 eprime = phi_translate (expr, ANTIC_IN (block), NULL,
2618 /* eprime will generally only be NULL if the
2619 value of the expression, translated
2620 through the PHI for this predecessor, is
2621 undefined. If that is the case, we can't
2622 make the expression fully redundant,
2623 because its value is undefined along a
2624 predecessor path. We can thus break out
2625 early because it doesn't matter what the
2626 rest of the results are. */
2633 eprime = fully_constant_expression (eprime);
2634 vprime = get_value_handle (eprime);
2635 gcc_assert (vprime);
2636 edoubleprime = bitmap_find_leader (AVAIL_OUT (bprime),
2638 if (edoubleprime == NULL)
2640 avail[bprime->index] = eprime;
2645 avail[bprime->index] = edoubleprime;
2647 if (first_s == NULL)
2648 first_s = edoubleprime;
2649 else if (!operand_equal_p (first_s, edoubleprime,
2654 /* If we can insert it, it's not the same value
2655 already existing along every predecessor, and
2656 it's defined by some predecessor, it is
2657 partially redundant. */
2658 if (!cant_insert && !all_same && by_some)
2660 if (insert_into_preds_of_block (block, get_expression_id (expr),
2664 /* If all edges produce the same value and that value is
2665 an invariant, then the PHI has the same value on all
2666 edges. Note this. */
2667 else if (!cant_insert && all_same && eprime
2668 && is_gimple_min_invariant (eprime)
2669 && !is_gimple_min_invariant (val))
2674 bitmap_set_t exprset = VALUE_HANDLE_EXPR_SET (val);
2675 FOR_EACH_EXPR_ID_IN_SET (exprset, j, bi)
2677 tree expr = expression_for_id (j);
2678 if (TREE_CODE (expr) == SSA_NAME)
2680 vn_add (expr, eprime);
2681 pre_stats.constified++;
2689 VEC_free (tree, heap, exprs);
2694 /* Perform insertion for partially anticipatable expressions. There
2695 is only one case we will perform insertion for these. This case is
2696 if the expression is partially anticipatable, and fully available.
2697 In this case, we know that putting it earlier will enable us to
2698 remove the later computation. */
2702 do_partial_partial_insertion (basic_block block, basic_block dom)
2704 bool new_stuff = false;
2705 VEC (tree, heap) *exprs = sorted_array_from_bitmap_set (PA_IN (block));
2709 for (i = 0; VEC_iterate (tree, exprs, i, expr); i++)
2711 if (can_PRE_operation (expr) && !AGGREGATE_TYPE_P (TREE_TYPE (expr)))
2716 bool cant_insert = false;
2719 tree eprime = NULL_TREE;
2722 val = get_value_handle (expr);
2723 if (bitmap_set_contains_value (PHI_GEN (block), val))
2725 if (bitmap_set_contains_value (AVAIL_OUT (dom), val))
2728 avail = XCNEWVEC (tree, last_basic_block);
2729 FOR_EACH_EDGE (pred, ei, block->preds)
2734 /* This can happen in the very weird case
2735 that our fake infinite loop edges have caused a
2736 critical edge to appear. */
2737 if (EDGE_CRITICAL_P (pred))
2743 eprime = phi_translate (expr, ANTIC_IN (block),
2747 /* eprime will generally only be NULL if the
2748 value of the expression, translated
2749 through the PHI for this predecessor, is
2750 undefined. If that is the case, we can't
2751 make the expression fully redundant,
2752 because its value is undefined along a
2753 predecessor path. We can thus break out
2754 early because it doesn't matter what the
2755 rest of the results are. */
2762 eprime = fully_constant_expression (eprime);
2763 vprime = get_value_handle (eprime);
2764 gcc_assert (vprime);
2765 edoubleprime = bitmap_find_leader (AVAIL_OUT (bprime),
2767 if (edoubleprime == NULL)
2773 avail[bprime->index] = edoubleprime;
2777 /* If we can insert it, it's not the same value
2778 already existing along every predecessor, and
2779 it's defined by some predecessor, it is
2780 partially redundant. */
2781 if (!cant_insert && by_all)
2783 pre_stats.pa_insert++;
2784 if (insert_into_preds_of_block (block, get_expression_id (expr),
2792 VEC_free (tree, heap, exprs);
2797 insert_aux (basic_block block)
2800 bool new_stuff = false;
2805 dom = get_immediate_dominator (CDI_DOMINATORS, block);
2810 bitmap_set_t newset = NEW_SETS (dom);
2813 /* Note that we need to value_replace both NEW_SETS, and
2814 AVAIL_OUT. For both the case of NEW_SETS, the value may be
2815 represented by some non-simple expression here that we want
2816 to replace it with. */
2817 FOR_EACH_EXPR_ID_IN_SET (newset, i, bi)
2819 tree expr = expression_for_id (i);
2820 bitmap_value_replace_in_set (NEW_SETS (block), expr);
2821 bitmap_value_replace_in_set (AVAIL_OUT (block), expr);
2824 if (!single_pred_p (block))
2826 new_stuff |= do_regular_insertion (block, dom);
2827 if (do_partial_partial)
2828 new_stuff |= do_partial_partial_insertion (block, dom);
2832 for (son = first_dom_son (CDI_DOMINATORS, block);
2834 son = next_dom_son (CDI_DOMINATORS, son))
2836 new_stuff |= insert_aux (son);
2842 /* Perform insertion of partially redundant values. */
2847 bool new_stuff = true;
2849 int num_iterations = 0;
2852 NEW_SETS (bb) = bitmap_set_new ();
2858 new_stuff = insert_aux (ENTRY_BLOCK_PTR);
2860 if (num_iterations > 2 && dump_file && (dump_flags & TDF_STATS))
2861 fprintf (dump_file, "insert required %d iterations\n", num_iterations);
2865 /* Return true if VAR is an SSA variable with no defining statement in
2866 this procedure, *AND* isn't a live-on-entry parameter. */
2869 is_undefined_value (tree expr)
2871 return (TREE_CODE (expr) == SSA_NAME
2872 && IS_EMPTY_STMT (SSA_NAME_DEF_STMT (expr))
2873 /* PARM_DECLs and hard registers are always defined. */
2874 && TREE_CODE (SSA_NAME_VAR (expr)) != PARM_DECL);
2877 /* Add OP to EXP_GEN (block), and possibly to the maximal set if it is
2878 not defined by a phi node.
2879 PHI nodes can't go in the maximal sets because they are not in
2880 TMP_GEN, so it is possible to get into non-monotonic situations
2881 during ANTIC calculation, because it will *add* bits. */
2884 add_to_exp_gen (basic_block block, tree op)
2888 if (TREE_CODE (op) == SSA_NAME && is_undefined_value (op))
2890 bitmap_value_insert_into_set (EXP_GEN (block), op);
2891 if (TREE_CODE (op) != SSA_NAME
2892 || TREE_CODE (SSA_NAME_DEF_STMT (op)) != PHI_NODE)
2893 bitmap_value_insert_into_set (maximal_set, op);
2898 /* Given an SSA variable VAR and an expression EXPR, compute the value
2899 number for EXPR and create a value handle (VAL) for it. If VAR and
2900 EXPR are not the same, associate VAL with VAR. Finally, add VAR to
2901 S1 and its value handle to S2, and to the maximal set if
2902 ADD_TO_MAXIMAL is true.
2904 VUSES represent the virtual use operands associated with EXPR (if
2908 add_to_sets (tree var, tree expr, tree stmt, bitmap_set_t s1,
2912 val = vn_lookup_or_add_with_stmt (expr, stmt);
2914 /* VAR and EXPR may be the same when processing statements for which
2915 we are not computing value numbers (e.g., non-assignments, or
2916 statements that make aliased stores). In those cases, we are
2917 only interested in making VAR available as its own value. */
2922 bitmap_insert_into_set (s1, var);
2924 bitmap_value_insert_into_set (s2, var);
2927 /* Find existing value expression that is the same as T,
2928 and return it if it exists. */
2931 find_existing_value_expr (tree t, tree stmt)
2936 bitmap_set_t exprset;
2938 if (REFERENCE_CLASS_P (t) || TREE_CODE (t) == CALL_EXPR || DECL_P (t))
2939 vh = vn_lookup_with_stmt (t, stmt);
2945 exprset = VALUE_HANDLE_EXPR_SET (vh);
2946 FOR_EACH_EXPR_ID_IN_SET (exprset, bii, bi)
2948 tree efi = expression_for_id (bii);
2949 if (expressions_equal_p (t, efi))
2955 /* Given a unary or binary expression EXPR, create and return a new
2956 expression with the same structure as EXPR but with its operands
2957 replaced with the value handles of each of the operands of EXPR.
2959 VUSES represent the virtual use operands associated with EXPR (if
2960 any). Insert EXPR's operands into the EXP_GEN set for BLOCK. */
2963 create_value_expr_from (tree expr, basic_block block, tree stmt)
2966 enum tree_code code = TREE_CODE (expr);
2968 alloc_pool pool = NULL;
2971 gcc_assert (TREE_CODE_CLASS (code) == tcc_unary
2972 || TREE_CODE_CLASS (code) == tcc_binary
2973 || TREE_CODE_CLASS (code) == tcc_comparison
2974 || TREE_CODE_CLASS (code) == tcc_reference
2975 || TREE_CODE_CLASS (code) == tcc_expression
2976 || TREE_CODE_CLASS (code) == tcc_vl_exp
2977 || TREE_CODE_CLASS (code) == tcc_exceptional
2978 || TREE_CODE_CLASS (code) == tcc_declaration);
2980 if (TREE_CODE_CLASS (code) == tcc_unary)
2981 pool = unary_node_pool;
2982 else if (TREE_CODE_CLASS (code) == tcc_reference)
2983 pool = reference_node_pool;
2984 else if (TREE_CODE_CLASS (code) == tcc_binary)
2985 pool = binary_node_pool;
2986 else if (TREE_CODE_CLASS (code) == tcc_comparison)
2987 pool = comparison_node_pool;
2989 gcc_assert (code == CALL_EXPR);
2991 if (code == CALL_EXPR)
2992 vexpr = temp_copy_call_expr (expr);
2995 vexpr = (tree) pool_alloc (pool);
2996 memcpy (vexpr, expr, tree_size (expr));
2999 for (i = 0; i < TREE_OPERAND_LENGTH (expr); i++)
3001 tree val = NULL_TREE;
3004 op = TREE_OPERAND (expr, i);
3005 if (op == NULL_TREE)
3008 /* Recursively value-numberize reference ops and tree lists. */
3009 if (REFERENCE_CLASS_P (op))
3011 tree tempop = create_value_expr_from (op, block, stmt);
3012 op = tempop ? tempop : op;
3013 val = vn_lookup_or_add_with_stmt (op, stmt);
3017 val = vn_lookup_or_add (op);
3019 if (TREE_CODE (op) != TREE_LIST)
3020 add_to_exp_gen (block, op);
3022 if (TREE_CODE (val) == VALUE_HANDLE)
3023 TREE_TYPE (val) = TREE_TYPE (TREE_OPERAND (vexpr, i));
3025 TREE_OPERAND (vexpr, i) = val;
3027 efi = find_existing_value_expr (vexpr, stmt);
3030 get_or_alloc_expression_id (vexpr);
3034 /* Return a copy of NODE that is stored in the temporary alloc_pool's.
3035 This is made recursively true, so that the operands are stored in
3036 the pool as well. */
3039 poolify_tree (tree node)
3041 switch (TREE_CODE (node))
3045 tree temp = (tree) pool_alloc (reference_node_pool);
3046 memcpy (temp, node, tree_size (node));
3047 TREE_OPERAND (temp, 0) = poolify_tree (TREE_OPERAND (temp, 0));
3051 case GIMPLE_MODIFY_STMT:
3053 tree temp = (tree) pool_alloc (modify_expr_node_pool);
3054 memcpy (temp, node, tree_size (node));
3055 GIMPLE_STMT_OPERAND (temp, 0) =
3056 poolify_tree (GIMPLE_STMT_OPERAND (temp, 0));
3057 GIMPLE_STMT_OPERAND (temp, 1) =
3058 poolify_tree (GIMPLE_STMT_OPERAND (temp, 1));
3075 static tree modify_expr_template;
3077 /* Allocate a GIMPLE_MODIFY_STMT with TYPE, and operands OP1, OP2 in the
3078 alloc pools and return it. */
3080 poolify_modify_stmt (tree op1, tree op2)
3082 if (modify_expr_template == NULL)
3083 modify_expr_template = build_gimple_modify_stmt (op1, op2);
3085 GIMPLE_STMT_OPERAND (modify_expr_template, 0) = op1;
3086 GIMPLE_STMT_OPERAND (modify_expr_template, 1) = op2;
3088 return poolify_tree (modify_expr_template);
3092 /* For each real store operation of the form
3093 *a = <value> that we see, create a corresponding fake store of the
3094 form storetmp_<version> = *a.
3096 This enables AVAIL computation to mark the results of stores as
3097 available. Without this, you'd need to do some computation to
3098 mark the result of stores as ANTIC and AVAIL at all the right
3100 To save memory, we keep the store
3101 statements pool allocated until we decide whether they are
3102 necessary or not. */
3105 insert_fake_stores (void)
3111 block_stmt_iterator bsi;
3112 for (bsi = bsi_start (block); !bsi_end_p (bsi); bsi_next (&bsi))
3114 tree stmt = bsi_stmt (bsi);
3116 /* We can't generate SSA names for stores that are complex
3117 or aggregate. We also want to ignore things whose
3118 virtual uses occur in abnormal phis. */
3120 if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT
3121 && TREE_CODE (GIMPLE_STMT_OPERAND (stmt, 0)) == INDIRECT_REF
3122 && !AGGREGATE_TYPE_P (TREE_TYPE (GIMPLE_STMT_OPERAND (stmt, 0)))
3123 && TREE_CODE (TREE_TYPE (GIMPLE_STMT_OPERAND
3124 (stmt, 0))) != COMPLEX_TYPE)
3128 tree lhs = GIMPLE_STMT_OPERAND (stmt, 0);
3129 tree rhs = GIMPLE_STMT_OPERAND (stmt, 1);
3131 bool notokay = false;
3133 FOR_EACH_SSA_DEF_OPERAND (defp, stmt, iter, SSA_OP_VIRTUAL_DEFS)
3135 tree defvar = DEF_FROM_PTR (defp);
3136 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (defvar))
3146 if (!storetemp || TREE_TYPE (rhs) != TREE_TYPE (storetemp))
3148 storetemp = create_tmp_var (TREE_TYPE (rhs), "storetmp");
3149 if (TREE_CODE (TREE_TYPE (storetemp)) == VECTOR_TYPE)
3150 DECL_GIMPLE_REG_P (storetemp) = 1;
3151 get_var_ann (storetemp);
3154 new_tree = poolify_modify_stmt (storetemp, lhs);
3156 lhs = make_ssa_name (storetemp, new_tree);
3157 GIMPLE_STMT_OPERAND (new_tree, 0) = lhs;
3158 create_ssa_artificial_load_stmt (new_tree, stmt);
3160 NECESSARY (new_tree) = 0;
3161 VEC_safe_push (tree, heap, inserted_exprs, new_tree);
3162 VEC_safe_push (tree, heap, need_creation, new_tree);
3163 bsi_insert_after (&bsi, new_tree, BSI_NEW_STMT);
3169 /* Turn the pool allocated fake stores that we created back into real
3170 GC allocated ones if they turned out to be necessary to PRE some
3174 realify_fake_stores (void)
3179 for (i = 0; VEC_iterate (tree, need_creation, i, stmt); i++)
3181 if (NECESSARY (stmt))
3183 block_stmt_iterator bsi;
3186 /* Mark the temp variable as referenced */
3187 add_referenced_var (SSA_NAME_VAR (GIMPLE_STMT_OPERAND (stmt, 0)));
3189 /* Put the new statement in GC memory, fix up the
3190 SSA_NAME_DEF_STMT on it, and then put it in place of
3191 the old statement before the store in the IR stream
3192 as a plain ssa name copy. */
3193 bsi = bsi_for_stmt (stmt);
3195 tmp = GIMPLE_STMT_OPERAND (bsi_stmt (bsi), 1);
3196 newstmt = build_gimple_modify_stmt (GIMPLE_STMT_OPERAND (stmt, 0),
3198 SSA_NAME_DEF_STMT (GIMPLE_STMT_OPERAND (newstmt, 0)) = newstmt;
3199 bsi_insert_before (&bsi, newstmt, BSI_SAME_STMT);
3200 bsi = bsi_for_stmt (stmt);
3201 bsi_remove (&bsi, true);
3204 release_defs (stmt);
3208 /* Given an SSA_NAME, see if SCCVN has a value number for it, and if
3209 so, return the value handle for this value number, creating it if
3211 Return NULL if SCCVN has no info for us. */
3214 get_sccvn_value (tree name)
3216 if (TREE_CODE (name) == SSA_NAME
3217 && VN_INFO (name)->valnum != name
3218 && VN_INFO (name)->valnum != VN_TOP)
3220 tree val = VN_INFO (name)->valnum;
3221 bool is_invariant = is_gimple_min_invariant (val);
3222 tree valvh = !is_invariant ? get_value_handle (val) : NULL_TREE;
3224 /* We may end up with situations where SCCVN has chosen a
3225 representative for the equivalence set that we have not
3226 visited yet. In this case, just create the value handle for
3228 if (!valvh && !is_invariant)
3230 tree defstmt = SSA_NAME_DEF_STMT (val);
3232 gcc_assert (VN_INFO (val)->valnum == val);
3233 /* PHI nodes can't have vuses and attempts to iterate over
3234 their VUSE operands will crash. */
3235 if (TREE_CODE (defstmt) == PHI_NODE || IS_EMPTY_STMT (defstmt))
3238 tree defstmt2 = SSA_NAME_DEF_STMT (name);
3239 if (TREE_CODE (defstmt2) != PHI_NODE &&
3240 !ZERO_SSA_OPERANDS (defstmt2, SSA_OP_ALL_VIRTUALS))
3241 gcc_assert (defstmt);
3243 valvh = vn_lookup_or_add_with_stmt (val, defstmt);
3246 if (dump_file && (dump_flags & TDF_DETAILS))
3248 fprintf (dump_file, "SCCVN says ");
3249 print_generic_expr (dump_file, name, 0);
3250 fprintf (dump_file, " value numbers to ");
3251 if (valvh && !is_invariant)
3253 print_generic_expr (dump_file, val, 0);
3254 fprintf (dump_file, " (");
3255 print_generic_expr (dump_file, valvh, 0);
3256 fprintf (dump_file, ")\n");
3259 print_generic_stmt (dump_file, val, 0);
3269 /* Create value handles for PHI in BLOCK. */
3272 make_values_for_phi (tree phi, basic_block block)
3274 tree result = PHI_RESULT (phi);
3275 /* We have no need for virtual phis, as they don't represent
3276 actual computations. */
3277 if (is_gimple_reg (result))
3279 tree sccvnval = get_sccvn_value (result);
3282 vn_add (result, sccvnval);
3283 bitmap_insert_into_set (PHI_GEN (block), result);
3284 bitmap_value_insert_into_set (AVAIL_OUT (block), result);
3287 add_to_sets (result, result, NULL,
3288 PHI_GEN (block), AVAIL_OUT (block));
3292 /* Return true if both the statement and the value handles have no
3293 vuses, or both the statement and the value handle do have vuses.
3295 Unlike SCCVN, PRE needs not only to know equivalence, but what the
3296 actual vuses are so it can translate them through blocks. Thus,
3297 we have to make a new value handle if the existing one has no
3298 vuses but needs them. */
3301 vuse_equiv (tree vh1, tree stmt)
3303 bool stmt_has_vuses = !ZERO_SSA_OPERANDS (stmt, SSA_OP_VIRTUAL_USES);
3304 return (VALUE_HANDLE_VUSES (vh1) && stmt_has_vuses)
3305 || (!VALUE_HANDLE_VUSES (vh1) && !stmt_has_vuses);
3308 /* Create value handles for STMT in BLOCK. Return true if we handled
3312 make_values_for_stmt (tree stmt, basic_block block)
3315 tree lhs = GIMPLE_STMT_OPERAND (stmt, 0);
3316 tree rhs = GIMPLE_STMT_OPERAND (stmt, 1);
3317 tree valvh = NULL_TREE;
3320 valvh = get_sccvn_value (lhs);
3323 vn_add (lhs, valvh);
3324 bitmap_value_insert_into_set (AVAIL_OUT (block), lhs);
3325 /* Shortcut for FRE. We have no need to create value expressions,
3326 just want to know what values are available where. */
3333 /* For FRE, if SCCVN didn't find anything, we aren't going to
3334 either, so just make up a new value number if necessary and
3336 if (get_value_handle (lhs) == NULL)
3337 vn_lookup_or_add (lhs);
3338 bitmap_value_insert_into_set (AVAIL_OUT (block), lhs);
3342 lhsval = valvh ? valvh : get_value_handle (lhs);
3344 STRIP_USELESS_TYPE_CONVERSION (rhs);
3345 if (can_value_number_operation (rhs)
3346 && (!lhsval || !is_gimple_min_invariant (lhsval)))
3348 /* For value numberable operation, create a
3349 duplicate expression with the operands replaced
3350 with the value handles of the original RHS. */
3351 tree newt = create_value_expr_from (rhs, block, stmt);
3354 /* If we already have a value number for the LHS, reuse
3355 it rather than creating a new one. */
3356 if (lhsval && vuse_equiv (lhsval, stmt))
3358 set_value_handle (newt, lhsval);
3359 if (!is_gimple_min_invariant (lhsval))
3360 add_to_value (lhsval, newt);
3364 tree val = vn_lookup_or_add_with_stmt (newt, stmt);
3368 add_to_exp_gen (block, newt);
3371 bitmap_insert_into_set (TMP_GEN (block), lhs);
3372 bitmap_value_insert_into_set (AVAIL_OUT (block), lhs);
3375 else if ((TREE_CODE (rhs) == SSA_NAME
3376 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs))
3377 || is_gimple_min_invariant (rhs)
3378 || TREE_CODE (rhs) == ADDR_EXPR
3379 || TREE_INVARIANT (rhs)
3385 set_value_handle (rhs, lhsval);
3386 if (!is_gimple_min_invariant (lhsval))
3387 add_to_value (lhsval, rhs);
3388 bitmap_insert_into_set (TMP_GEN (block), lhs);
3389 bitmap_value_insert_into_set (AVAIL_OUT (block), lhs);
3393 /* Compute a value number for the RHS of the statement
3394 and add its value to the AVAIL_OUT set for the block.
3395 Add the LHS to TMP_GEN. */
3396 add_to_sets (lhs, rhs, stmt, TMP_GEN (block),
3399 /* None of the rest of these can be PRE'd. */
3400 if (TREE_CODE (rhs) == SSA_NAME && !is_undefined_value (rhs))
3401 add_to_exp_gen (block, rhs);
3408 /* Compute the AVAIL set for all basic blocks.
3410 This function performs value numbering of the statements in each basic
3411 block. The AVAIL sets are built from information we glean while doing
3412 this value numbering, since the AVAIL sets contain only one entry per
3415 AVAIL_IN[BLOCK] = AVAIL_OUT[dom(BLOCK)].
3416 AVAIL_OUT[BLOCK] = AVAIL_IN[BLOCK] U PHI_GEN[BLOCK] U TMP_GEN[BLOCK]. */
3419 compute_avail (void)
3421 basic_block block, son;
3422 basic_block *worklist;
3426 /* For arguments with default definitions, we pretend they are
3427 defined in the entry block. */
3428 for (param = DECL_ARGUMENTS (current_function_decl);
3430 param = TREE_CHAIN (param))
3432 if (gimple_default_def (cfun, param) != NULL)
3434 tree def = gimple_default_def (cfun, param);
3436 vn_lookup_or_add (def);
3439 bitmap_insert_into_set (TMP_GEN (ENTRY_BLOCK_PTR), def);
3440 bitmap_value_insert_into_set (maximal_set, def);
3442 bitmap_value_insert_into_set (AVAIL_OUT (ENTRY_BLOCK_PTR), def);
3446 /* Likewise for the static chain decl. */
3447 if (cfun->static_chain_decl)
3449 param = cfun->static_chain_decl;
3450 if (gimple_default_def (cfun, param) != NULL)
3452 tree def = gimple_default_def (cfun, param);
3454 vn_lookup_or_add (def);
3457 bitmap_insert_into_set (TMP_GEN (ENTRY_BLOCK_PTR), def);
3458 bitmap_value_insert_into_set (maximal_set, def);
3460 bitmap_value_insert_into_set (AVAIL_OUT (ENTRY_BLOCK_PTR), def);
3464 /* Allocate the worklist. */
3465 worklist = XNEWVEC (basic_block, n_basic_blocks);
3467 /* Seed the algorithm by putting the dominator children of the entry
3468 block on the worklist. */
3469 for (son = first_dom_son (CDI_DOMINATORS, ENTRY_BLOCK_PTR);
3471 son = next_dom_son (CDI_DOMINATORS, son))
3472 worklist[sp++] = son;
3474 /* Loop until the worklist is empty. */
3477 block_stmt_iterator bsi;
3480 unsigned int stmt_uid = 1;
3482 /* Pick a block from the worklist. */
3483 block = worklist[--sp];
3485 /* Initially, the set of available values in BLOCK is that of
3486 its immediate dominator. */
3487 dom = get_immediate_dominator (CDI_DOMINATORS, block);
3489 bitmap_set_copy (AVAIL_OUT (block), AVAIL_OUT (dom));
3491 /* Generate values for PHI nodes. */
3492 for (phi = phi_nodes (block); phi; phi = PHI_CHAIN (phi))
3493 make_values_for_phi (phi, block);
3495 /* Now compute value numbers and populate value sets with all
3496 the expressions computed in BLOCK. */
3497 for (bsi = bsi_start (block); !bsi_end_p (bsi); bsi_next (&bsi))
3503 stmt = bsi_stmt (bsi);
3504 ann = stmt_ann (stmt);
3506 ann->uid = stmt_uid++;
3508 /* For regular value numbering, we are only interested in
3509 assignments of the form X_i = EXPR, where EXPR represents
3510 an "interesting" computation, it has no volatile operands
3511 and X_i doesn't flow through an abnormal edge. */
3512 if (TREE_CODE (stmt) == RETURN_EXPR
3513 && !ann->has_volatile_ops)
3515 tree realstmt = stmt;
3519 stmt = TREE_OPERAND (stmt, 0);
3520 if (stmt && TREE_CODE (stmt) == GIMPLE_MODIFY_STMT)
3522 lhs = GIMPLE_STMT_OPERAND (stmt, 0);
3523 rhs = GIMPLE_STMT_OPERAND (stmt, 1);
3524 if (TREE_CODE (lhs) == SSA_NAME
3525 && is_gimple_min_invariant (VN_INFO (lhs)->valnum))
3527 if (dump_file && (dump_flags & TDF_DETAILS))
3529 fprintf (dump_file, "SCCVN says ");
3530 print_generic_expr (dump_file, lhs, 0);
3531 fprintf (dump_file, " value numbers to ");
3532 print_generic_stmt (dump_file, VN_INFO (lhs)->valnum,
3535 vn_add (lhs, VN_INFO (lhs)->valnum);
3539 if (TREE_CODE (rhs) == SSA_NAME)
3540 add_to_exp_gen (block, rhs);
3542 FOR_EACH_SSA_TREE_OPERAND (op, realstmt, iter, SSA_OP_DEF)
3543 add_to_sets (op, op, NULL, TMP_GEN (block),
3549 else if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT
3550 && !ann->has_volatile_ops
3551 && TREE_CODE (GIMPLE_STMT_OPERAND (stmt, 0)) == SSA_NAME
3552 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI
3553 (GIMPLE_STMT_OPERAND (stmt, 0)))
3555 if (make_values_for_stmt (stmt, block))
3560 /* For any other statement that we don't recognize, simply
3561 make the names generated by the statement available in
3562 AVAIL_OUT and TMP_GEN. */
3563 FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_DEF)
3564 add_to_sets (op, op, NULL, TMP_GEN (block), AVAIL_OUT (block));
3566 FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_USE)
3568 add_to_sets (op, op, NULL, NULL , AVAIL_OUT (block));
3569 if (TREE_CODE (op) == SSA_NAME || can_PRE_operation (op))
3570 add_to_exp_gen (block, op);
3574 /* Put the dominator children of BLOCK on the worklist of blocks
3575 to compute available sets for. */
3576 for (son = first_dom_son (CDI_DOMINATORS, block);
3578 son = next_dom_son (CDI_DOMINATORS, son))
3579 worklist[sp++] = son;
3586 /* Eliminate fully redundant computations. */
3595 block_stmt_iterator i;
3597 for (i = bsi_start (b); !bsi_end_p (i); bsi_next (&i))
3599 tree stmt = bsi_stmt (i);
3601 /* Lookup the RHS of the expression, see if we have an
3602 available computation for it. If so, replace the RHS with
3603 the available computation. */
3604 if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT
3605 && TREE_CODE (GIMPLE_STMT_OPERAND (stmt, 0)) == SSA_NAME
3606 && TREE_CODE (GIMPLE_STMT_OPERAND (stmt, 1)) != SSA_NAME
3607 && !is_gimple_min_invariant (GIMPLE_STMT_OPERAND (stmt, 1))
3608 && !stmt_ann (stmt)->has_volatile_ops)
3610 tree lhs = GIMPLE_STMT_OPERAND (stmt, 0);
3611 tree *rhs_p = &GIMPLE_STMT_OPERAND (stmt, 1);
3614 sprime = bitmap_find_leader (AVAIL_OUT (b),
3615 get_value_handle (lhs));
3619 && (TREE_CODE (*rhs_p) != SSA_NAME
3620 || may_propagate_copy (*rhs_p, sprime)))
3622 gcc_assert (sprime != *rhs_p);
3624 if (dump_file && (dump_flags & TDF_DETAILS))
3626 fprintf (dump_file, "Replaced ");
3627 print_generic_expr (dump_file, *rhs_p, 0);
3628 fprintf (dump_file, " with ");
3629 print_generic_expr (dump_file, sprime, 0);
3630 fprintf (dump_file, " in ");
3631 print_generic_stmt (dump_file, stmt, 0);
3634 if (TREE_CODE (sprime) == SSA_NAME)
3635 NECESSARY (SSA_NAME_DEF_STMT (sprime)) = 1;
3636 /* We need to make sure the new and old types actually match,
3637 which may require adding a simple cast, which fold_convert
3639 if (TREE_CODE (*rhs_p) != SSA_NAME
3640 && !useless_type_conversion_p (TREE_TYPE (*rhs_p),
3641 TREE_TYPE (sprime)))
3642 sprime = fold_convert (TREE_TYPE (*rhs_p), sprime);
3644 pre_stats.eliminations++;
3645 propagate_tree_value (rhs_p, sprime);
3648 /* If we removed EH side effects from the statement, clean
3649 its EH information. */
3650 if (maybe_clean_or_replace_eh_stmt (stmt, stmt))
3652 bitmap_set_bit (need_eh_cleanup,
3653 bb_for_stmt (stmt)->index);
3654 if (dump_file && (dump_flags & TDF_DETAILS))
3655 fprintf (dump_file, " Removed EH side effects.\n");
3663 /* Borrow a bit of tree-ssa-dce.c for the moment.
3664 XXX: In 4.1, we should be able to just run a DCE pass after PRE, though
3665 this may be a bit faster, and we may want critical edges kept split. */
3667 /* If OP's defining statement has not already been determined to be necessary,
3668 mark that statement necessary. Return the stmt, if it is newly
3672 mark_operand_necessary (tree op)
3678 if (TREE_CODE (op) != SSA_NAME)
3681 stmt = SSA_NAME_DEF_STMT (op);
3684 if (NECESSARY (stmt)
3685 || IS_EMPTY_STMT (stmt))
3688 NECESSARY (stmt) = 1;
3692 /* Because we don't follow exactly the standard PRE algorithm, and decide not
3693 to insert PHI nodes sometimes, and because value numbering of casts isn't
3694 perfect, we sometimes end up inserting dead code. This simple DCE-like
3695 pass removes any insertions we made that weren't actually used. */
3698 remove_dead_inserted_code (void)
3700 VEC(tree,heap) *worklist = NULL;
3704 worklist = VEC_alloc (tree, heap, VEC_length (tree, inserted_exprs));
3705 for (i = 0; VEC_iterate (tree, inserted_exprs, i, t); i++)
3708 VEC_quick_push (tree, worklist, t);
3710 while (VEC_length (tree, worklist) > 0)
3712 t = VEC_pop (tree, worklist);
3714 /* PHI nodes are somewhat special in that each PHI alternative has
3715 data and control dependencies. All the statements feeding the
3716 PHI node's arguments are always necessary. */
3717 if (TREE_CODE (t) == PHI_NODE)
3721 VEC_reserve (tree, heap, worklist, PHI_NUM_ARGS (t));
3722 for (k = 0; k < PHI_NUM_ARGS (t); k++)
3724 tree arg = PHI_ARG_DEF (t, k);
3725 if (TREE_CODE (arg) == SSA_NAME)
3727 arg = mark_operand_necessary (arg);
3729 VEC_quick_push (tree, worklist, arg);
3735 /* Propagate through the operands. Examine all the USE, VUSE and
3736 VDEF operands in this statement. Mark all the statements
3737 which feed this statement's uses as necessary. */
3741 /* The operands of VDEF expressions are also needed as they
3742 represent potential definitions that may reach this
3743 statement (VDEF operands allow us to follow def-def
3746 FOR_EACH_SSA_TREE_OPERAND (use, t, iter, SSA_OP_ALL_USES)
3748 tree n = mark_operand_necessary (use);
3750 VEC_safe_push (tree, heap, worklist, n);
3755 for (i = 0; VEC_iterate (tree, inserted_exprs, i, t); i++)
3759 block_stmt_iterator bsi;
3761 if (dump_file && (dump_flags & TDF_DETAILS))
3763 fprintf (dump_file, "Removing unnecessary insertion:");
3764 print_generic_stmt (dump_file, t, 0);
3767 if (TREE_CODE (t) == PHI_NODE)
3769 remove_phi_node (t, NULL, true);
3773 bsi = bsi_for_stmt (t);
3774 bsi_remove (&bsi, true);
3779 VEC_free (tree, heap, worklist);
3782 /* Initialize data structures used by PRE. */
3785 init_pre (bool do_fre)
3789 next_expression_id = 0;
3793 inserted_exprs = NULL;
3794 need_creation = NULL;
3795 pretemp = NULL_TREE;
3796 storetemp = NULL_TREE;
3797 prephitemp = NULL_TREE;
3800 loop_optimizer_init (LOOPS_NORMAL);
3802 connect_infinite_loops_to_exit ();
3803 memset (&pre_stats, 0, sizeof (pre_stats));
3806 postorder = XNEWVEC (int, n_basic_blocks - NUM_FIXED_BLOCKS);
3807 post_order_compute (postorder, false, false);
3810 bb->aux = xcalloc (1, sizeof (struct bb_bitmap_sets));
3812 calculate_dominance_info (CDI_POST_DOMINATORS);
3813 calculate_dominance_info (CDI_DOMINATORS);
3815 bitmap_obstack_initialize (&grand_bitmap_obstack);
3816 phi_translate_table = htab_create (5110, expr_pred_trans_hash,
3817 expr_pred_trans_eq, free);
3818 seen_during_translate = BITMAP_ALLOC (&grand_bitmap_obstack);
3819 bitmap_set_pool = create_alloc_pool ("Bitmap sets",
3820 sizeof (struct bitmap_set), 30);
3821 binary_node_pool = create_alloc_pool ("Binary tree nodes",
3822 tree_code_size (PLUS_EXPR), 30);
3823 unary_node_pool = create_alloc_pool ("Unary tree nodes",
3824 tree_code_size (NEGATE_EXPR), 30);
3825 reference_node_pool = create_alloc_pool ("Reference tree nodes",
3826 tree_code_size (ARRAY_REF), 30);
3827 comparison_node_pool = create_alloc_pool ("Comparison tree nodes",
3828 tree_code_size (EQ_EXPR), 30);
3829 modify_expr_node_pool = create_alloc_pool ("GIMPLE_MODIFY_STMT nodes",
3830 tree_code_size (GIMPLE_MODIFY_STMT),
3832 obstack_init (&temp_call_expr_obstack);
3833 modify_expr_template = NULL;
3837 EXP_GEN (bb) = bitmap_set_new ();
3838 PHI_GEN (bb) = bitmap_set_new ();
3839 TMP_GEN (bb) = bitmap_set_new ();
3840 AVAIL_OUT (bb) = bitmap_set_new ();
3842 maximal_set = in_fre ? NULL : bitmap_set_new ();
3844 need_eh_cleanup = BITMAP_ALLOC (NULL);
3848 /* Deallocate data structures used by PRE. */
3857 VEC_free (tree, heap, inserted_exprs);
3858 VEC_free (tree, heap, need_creation);
3859 bitmap_obstack_release (&grand_bitmap_obstack);
3860 free_alloc_pool (bitmap_set_pool);
3861 free_alloc_pool (binary_node_pool);
3862 free_alloc_pool (reference_node_pool);
3863 free_alloc_pool (unary_node_pool);
3864 free_alloc_pool (comparison_node_pool);
3865 free_alloc_pool (modify_expr_node_pool);
3866 htab_delete (phi_translate_table);
3867 remove_fake_exit_edges ();
3875 free_dominance_info (CDI_POST_DOMINATORS);
3877 if (!bitmap_empty_p (need_eh_cleanup))
3879 tree_purge_all_dead_eh_edges (need_eh_cleanup);
3880 cleanup_tree_cfg ();
3883 BITMAP_FREE (need_eh_cleanup);
3885 /* Wipe out pointers to VALUE_HANDLEs. In the not terribly distant
3886 future we will want them to be persistent though. */
3887 for (i = 0; i < num_ssa_names; i++)
3889 tree name = ssa_name (i);
3894 if (SSA_NAME_VALUE (name)
3895 && TREE_CODE (SSA_NAME_VALUE (name)) == VALUE_HANDLE)
3896 SSA_NAME_VALUE (name) = NULL;
3898 if (current_loops != NULL)
3899 loop_optimizer_finalize ();
3902 /* Main entry point to the SSA-PRE pass. DO_FRE is true if the caller
3903 only wants to do full redundancy elimination. */
3906 execute_pre (bool do_fre)
3909 do_partial_partial = optimize > 2;
3913 insert_fake_stores ();
3915 /* Collect and value number expressions computed in each basic block. */
3917 switch_to_PRE_table ();
3920 if (dump_file && (dump_flags & TDF_DETAILS))
3926 print_bitmap_set (dump_file, EXP_GEN (bb), "exp_gen", bb->index);
3927 print_bitmap_set (dump_file, TMP_GEN (bb), "tmp_gen",
3929 print_bitmap_set (dump_file, AVAIL_OUT (bb), "avail_out",
3934 /* Insert can get quite slow on an incredibly large number of basic
3935 blocks due to some quadratic behavior. Until this behavior is
3936 fixed, don't run it when he have an incredibly large number of
3937 bb's. If we aren't going to run insert, there is no point in
3938 computing ANTIC, either, even though it's plenty fast. */
3939 if (!do_fre && n_basic_blocks < 4000)
3945 /* Remove all the redundant expressions. */
3948 if (dump_file && (dump_flags & TDF_STATS))
3950 fprintf (dump_file, "Insertions: %d\n", pre_stats.insertions);
3951 fprintf (dump_file, "PA inserted: %d\n", pre_stats.pa_insert);
3952 fprintf (dump_file, "New PHIs: %d\n", pre_stats.phis);
3953 fprintf (dump_file, "Eliminated: %d\n", pre_stats.eliminations);
3954 fprintf (dump_file, "Constified: %d\n", pre_stats.constified);
3956 bsi_commit_edge_inserts ();
3959 clear_expression_ids ();
3962 remove_dead_inserted_code ();
3963 realify_fake_stores ();
3969 /* Gate and execute functions for PRE. */
3974 execute_pre (false);
3981 return flag_tree_pre != 0;
3984 struct tree_opt_pass pass_pre =
3987 gate_pre, /* gate */
3988 do_pre, /* execute */
3991 0, /* static_pass_number */
3992 TV_TREE_PRE, /* tv_id */
3993 PROP_no_crit_edges | PROP_cfg
3994 | PROP_ssa | PROP_alias, /* properties_required */
3995 0, /* properties_provided */
3996 0, /* properties_destroyed */
3997 0, /* todo_flags_start */
3998 TODO_update_ssa_only_virtuals | TODO_dump_func | TODO_ggc_collect
3999 | TODO_verify_ssa, /* todo_flags_finish */
4004 /* Gate and execute functions for FRE. */
4016 return flag_tree_fre != 0;
4019 struct tree_opt_pass pass_fre =
4022 gate_fre, /* gate */
4023 execute_fre, /* execute */
4026 0, /* static_pass_number */
4027 TV_TREE_FRE, /* tv_id */
4028 PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */
4029 0, /* properties_provided */
4030 0, /* properties_destroyed */
4031 0, /* todo_flags_start */
4032 TODO_dump_func | TODO_ggc_collect | TODO_verify_ssa, /* todo_flags_finish */