2 Copyright (C) 2001, 2002, 2003, 2004 Free Software Foundation, Inc.
3 Contributed by Daniel Berlin <dan@dberlin.org> and Steven Bosscher
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify
9 it under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 2, or (at your option)
13 GCC is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 GNU General Public License for more details.
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING. If not, write to
20 the Free Software Foundation, 59 Temple Place - Suite 330,
21 Boston, MA 02111-1307, USA. */
24 #include "coretypes.h"
30 /* These RTL headers are needed for basic-block.h. */
33 #include "hard-reg-set.h"
34 #include "basic-block.h"
35 #include "diagnostic.h"
36 #include "tree-inline.h"
37 #include "tree-flow.h"
38 #include "tree-gimple.h"
39 #include "tree-dump.h"
43 #include "tree-iterator.h"
45 #include "alloc-pool.h"
46 #include "tree-pass.h"
48 #include "splay-tree.h"
50 #include "langhooks.h"
53 1. Implement load value numbering.
54 2. Speed up insert_aux so that we can use it all the time. It
55 spends most of it's time in quadratic value replacement.
56 3. Avail sets can be shared by making an avail_find_leader that
57 walks up the dominator tree and looks in those avail sets.
58 This might affect code optimality, it's unclear right now.
59 4. Load motion can be performed by value numbering the loads the
60 same as we do other expressions. This requires iterative
61 hashing the vuses into the values. Right now we simply assign
62 a new value every time we see a statement with a vuse.
63 5. Strength reduction can be performed by anticipating expressions
64 we can repair later on.
67 /* For ease of terminology, "expression node" in the below refers to
68 every expression node but MODIFY_EXPR, because MODIFY_EXPR's represent
69 the actual statement containing the expressions we care about, and
70 we cache the value number by putting it in the expression. */
74 First we walk the statements to generate the AVAIL sets, the EXP_GEN
75 sets, and the tmp_gen sets. AVAIL is a forward dataflow
76 problem. EXP_GEN sets represent the generation of
77 values/expressions by a given block. We use them when computing
78 the ANTIC sets. The AVAIL sets consist of SSA_NAME's that
79 represent values, so we know what values are available in what
80 blocks. In SSA, values are never killed, so we don't need a kill
81 set, or a fixpoint iteration, in order to calculate the AVAIL sets.
82 In traditional parlance, AVAIL sets tell us the downsafety of the
85 Next, we generate the ANTIC sets. ANTIC is a backwards dataflow
86 problem. These sets represent the anticipatable expressions. An
87 expression is anticipatable in a given block if it could be
88 generated in that block. This means that if we had to perform an
89 insertion in that block, of the value of that expression, we could.
90 Calculating the ANTIC sets requires phi translation of expressions,
91 because the flow goes backwards through phis. We must iterate to a
92 fixpoint of the ANTIC sets, because we have a kill set.
93 Even in SSA form, values are not live over the entire function,
94 only from their definition point onwards. So we have to remove
95 values from the ANTIC set once we go past the definition point of
96 the leaders that make them up. compute_antic/compute_antic_aux
97 performs this computation.
99 Third, we perform insertions to make partially redundant
100 expressions fully redundant.
102 An expression is partially redundant (excluding partial
105 1. It is AVAIL in some, but not all, of the predecessors of a
107 2. It is ANTIC in all the predecessors.
109 In order to make it fully redundant, we insert the expression into
110 the predecessors where it is not available, but is ANTIC.
111 insert/insert_aux performs this insertion.
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 and constant nodes) has a
122 value handle that can be retrieved through get_value_handle. This
123 value handle, *is* the value number of the SSA_NAME. You can
124 pointer compare the value handles for equivalence purposes.
126 For debugging reasons, the value handle is internally more than
127 just a number, it is a VAR_DECL named "value.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 "value.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 Constants have
137 value handles associated with them so that they aren't special
138 cased everywhere, and for consistency sake. This may be changed
139 depending on memory usage vs code maintenance tradeoff. */
141 /* Representation of expressions on value numbers:
143 In some portions of this code, you will notice we allocate "fake"
144 analogues to the expression we are value numbering, and replace the
145 operands with the values of the expression. Since we work on
146 values, and not just names, we canonicalize expressions to value
147 expressions for use in the ANTIC sets, the EXP_GEN set, etc.
149 This is theoretically unnecessary, it just saves a bunch of
150 repeated get_value_handle and find_leader calls in the remainder of
151 the code, trading off temporary memory usage for speed. The tree
152 nodes aren't actually creating more garbage, since they are
153 allocated in a special pools which are thrown away at the end of
156 All of this also means that if you print the EXP_GEN or ANTIC sets,
157 you will see "value.5 + value.7" in the set, instead of "a_55 +
158 b_66" or something. The only thing that actually cares about
159 seeing the value leaders is phi translation, and it needs to be
160 able to find the leader for a value in an arbitrary block, so this
161 "value expression" form is perfect for it (otherwise you'd do
162 get_value_handle->find_leader->translate->get_value_handle->find_leader).*/
165 /* Representation of sets:
167 Sets are represented as doubly linked lists kept in topological
168 order, with an optional supporting bitmap of values present in the
169 set. The sets represent values, and the elements can be constants,
170 values, or expressions. The elements can appear in different sets,
171 but each element can only appear once in each set.
173 Since each node in the set represents a value, we also want to be
174 able to map expression, set pairs to something that tells us
175 whether the value is present is a set. We use a per-set bitmap for
176 that. The value handles also point to a linked list of the
177 expressions they represent via a tree annotation. This is mainly
178 useful only for debugging, since we don't do identity lookups. */
181 /* A value set element. Basically a single linked list of
182 expressions/constants/values. */
183 typedef struct value_set_node
188 /* A pointer to the next element of the value set. */
189 struct value_set_node *next;
193 /* A value set. This is a singly linked list of value_set_node
194 elements with a possible bitmap that tells us what values exist in
195 the set. This set must be kept in topologically sorted order. */
196 typedef struct value_set
198 /* The head of the list. Used for iterating over the list in
200 value_set_node_t head;
202 /* The tail of the list. Used for tail insertions, which are
203 necessary to keep the set in topologically sorted order because
204 of how the set is built. */
205 value_set_node_t tail;
207 /* The length of the list. */
210 /* True if the set is indexed, which means it contains a backing
211 bitmap for quick determination of whether certain values exist in the
215 /* The bitmap of values that exist in the set. May be NULL in an
216 empty or non-indexed set. */
221 /* All of the following sets, except for TMP_GEN, are indexed.
222 TMP_GEN is only ever iterated over, we never check what values
225 typedef struct bb_value_sets
227 /* The EXP_GEN set, which represents expressions/values generated in
231 /* The PHI_GEN set, which represents PHI results generated in a
235 /* The TMP_GEN set, which represents results/temporaries genererated
236 in a basic block. IE the LHS of an expression. */
239 /* The AVAIL_OUT set, which represents which values are available in
240 a given basic block. */
241 value_set_t avail_out;
243 /* The ANTIC_IN set, which represents which values are anticiptable
244 in a given basic block. */
245 value_set_t antic_in;
247 /* The NEW_SETS set, which is used during insertion to augment the
248 AVAIL_OUT set of blocks with the new insertions performed during
249 the current iteration. */
250 value_set_t new_sets;
253 #define EXP_GEN(BB) ((bb_value_sets_t) ((BB)->aux))->exp_gen
254 #define PHI_GEN(BB) ((bb_value_sets_t) ((BB)->aux))->phi_gen
255 #define TMP_GEN(BB) ((bb_value_sets_t) ((BB)->aux))->tmp_gen
256 #define AVAIL_OUT(BB) ((bb_value_sets_t) ((BB)->aux))->avail_out
257 #define ANTIC_IN(BB) ((bb_value_sets_t) ((BB)->aux))->antic_in
258 #define NEW_SETS(BB) ((bb_value_sets_t) ((BB)->aux))->new_sets
260 /* This structure is used to keep track of statistics on what
261 optimization PRE was able to perform. */
264 /* The number of RHS computations eliminated by PRE. */
267 /* The number of new expressions/temporaries generated by PRE. */
270 /* The number of new PHI nodes added by PRE. */
274 static tree find_leader (value_set_t, tree);
275 static void value_insert_into_set (value_set_t, tree);
276 static void insert_into_set (value_set_t, tree);
277 static void add_to_value (tree, tree);
278 static value_set_t set_new (bool);
279 static bool is_undefined_value (tree);
280 static bool expressions_equal_p (tree, tree);
282 /* We can add and remove elements and entries to and from sets
283 and hash tables, so we use alloc pools for them. */
285 static alloc_pool value_set_pool;
286 static alloc_pool value_set_node_pool;
287 static alloc_pool binary_node_pool;
288 static alloc_pool unary_node_pool;
290 /* The value table that maps expressions to values. */
292 static htab_t value_table;
294 /* The phi_translate_table caches phi translations for a given
295 expression and predecessor. */
297 static htab_t phi_translate_table;
299 /* Compare two expressions E1 and E2 and return true if they are
303 expressions_equal_p (tree e1, tree e2)
310 te1 = TREE_TYPE (e1);
311 te2 = TREE_TYPE (e2);
313 if (TREE_CODE (e1) == TREE_CODE (e2)
314 && (te1 == te2 || lang_hooks.types_compatible_p (te1, te2))
315 && operand_equal_p (e1, e2, 0))
320 /* Map expressions to values. These are simple pairs of expressions
321 and the values they represent. To find the value represented by
322 an expression, we use a hash table where the elements are {e,v}
323 pairs, and the expression is the key. */
325 typedef struct val_expr_pair_d
332 /* Hash a {v,e} pair that is pointed to by P.
333 The hashcode is cached in the val_expr_pair, so we just return
337 val_expr_pair_hash (const void *p)
339 const val_expr_pair_t ve = (val_expr_pair_t) p;
344 /* Given two val_expr_pair_t's, return true if they represent the same
345 expression, false otherwise.
346 P1 and P2 should point to the val_expr_pair_t's to be compared. */
349 val_expr_pair_expr_eq (const void *p1, const void *p2)
351 const val_expr_pair_t ve1 = (val_expr_pair_t) p1;
352 const val_expr_pair_t ve2 = (val_expr_pair_t) p2;
354 if (expressions_equal_p (ve1->e, ve2->e))
361 /* Get the value handle of EXPR. This is the only correct way to get
362 the value handle for a "thing".
363 Returns NULL if the value handle does not exist. */
366 get_value_handle (tree expr)
368 /* We should never see these. */
371 else if (TREE_CODE (expr) == SSA_NAME)
373 return SSA_NAME_VALUE (expr);
375 else if (TREE_CODE_CLASS (TREE_CODE (expr)) == 'c')
377 cst_ann_t ann = cst_ann (expr);
379 return ann->common.value_handle;
382 else if (EXPR_P (expr))
384 expr_ann_t ann = expr_ann (expr);
386 return ann->common.value_handle;
393 /* Set the value handle for expression E to value V */
396 set_value_handle (tree e, tree v)
400 else if (TREE_CODE (e) == SSA_NAME)
401 SSA_NAME_VALUE (e) = v;
402 else if (TREE_CODE_CLASS (TREE_CODE (e)) == 'c')
403 get_cst_ann (e)->common.value_handle = v;
405 get_expr_ann (e)->common.value_handle = v;
408 /* A three tuple {e, pred, v} used to cache phi translations in the
409 phi_translate_table. */
411 typedef struct expr_pred_trans_d
413 /* The expression. */
416 /* The predecessor block along which we translated the expression. */
419 /* The value that resulted from the translation. */
422 /* The hashcode for the expression, pred pair. This is cached for
425 } *expr_pred_trans_t;
427 /* Return the hash value for a phi translation table entry. */
430 expr_pred_trans_hash (const void *p)
432 const expr_pred_trans_t ve = (expr_pred_trans_t) p;
436 /* Return true if two phi translation table entries are the same.
437 P1 and P2 should point to the expr_pred_trans_t's to be compared.*/
440 expr_pred_trans_eq (const void *p1, const void *p2)
442 const expr_pred_trans_t ve1 = (expr_pred_trans_t) p1;
443 const expr_pred_trans_t ve2 = (expr_pred_trans_t) p2;
444 basic_block b1 = ve1->pred;
445 basic_block b2 = ve2->pred;
448 /* If they are not translations for the same basic block, they can't
453 /* If they are for the same basic block, determine if the
454 expressions are equal. */
455 if (expressions_equal_p (ve1->e, ve2->e))
461 /* Search in the phi translation table for the translation of
462 expression E in basic block PRED. Return the translated value, if
463 found, NULL otherwise. */
466 phi_trans_lookup (tree e, basic_block pred)
469 struct expr_pred_trans_d ept;
472 ept.hashcode = iterative_hash_expr (e, (unsigned long) pred);
473 slot = htab_find_slot_with_hash (phi_translate_table, &ept, ept.hashcode,
478 return ((expr_pred_trans_t) *slot)->v;
482 /* Add the tuple mapping from {expression E, basic block PRED} to
483 value V, to the phi translation table. */
486 phi_trans_add (tree e, tree v, basic_block pred)
489 expr_pred_trans_t new_pair = xmalloc (sizeof (*new_pair));
491 new_pair->pred = pred;
493 new_pair->hashcode = iterative_hash_expr (e, (unsigned long) pred);
494 slot = htab_find_slot_with_hash (phi_translate_table, new_pair,
495 new_pair->hashcode, INSERT);
498 *slot = (void *) new_pair;
501 /* Search in TABLE for an existing instance of expression E,
502 and return its value, or NULL if none has been set. */
505 lookup (htab_t table, tree e)
508 struct val_expr_pair_d vep = {NULL, NULL, 0};
510 vep.hashcode = iterative_hash_expr (e,0);
511 slot = htab_find_slot_with_hash (table, &vep, vep.hashcode, NO_INSERT);
515 return ((val_expr_pair_t) *slot)->v;
518 /* Add expression E to the expression set of value V. */
521 add_to_value (tree v, tree e)
523 #if DEBUG_VALUE_EXPRESSIONS
524 var_ann_t va = var_ann (v);
526 /* For values representing numerical constants, we mark
527 TREE_CONSTANT as true and set the tree chain to the actual
528 constant. This is because unlike values involving expressions,
529 which are only available to use where the expressions are live, a
530 constant can be remade anywhere, and thus, is available
532 if (TREE_CODE_CLASS (TREE_CODE (e)) == 'c')
534 TREE_CONSTANT (v) = true;
537 else if (is_gimple_min_invariant (e))
539 TREE_CONSTANT (v) = true;
542 #if DEBUG_VALUE_EXPRESSIONS
543 if (va->expr_set == NULL)
544 va->expr_set = set_new (false);
545 insert_into_set (va->expr_set, e);
549 /* Insert E into TABLE with value V, and add expression E to the value
553 add (htab_t table, tree e, tree v)
557 val_expr_pair_t new_pair = xmalloc (sizeof (struct val_expr_pair_d));
560 new_pair->hashcode = iterative_hash_expr (e, 0);
561 slot = htab_find_slot_with_hash (table, new_pair, new_pair->hashcode,
565 *slot = (void *) new_pair;
566 set_value_handle (e, v);
572 /* A unique counter that is incremented every time we create a new
576 /* Create a new value handle for expression EXPR. */
579 create_new_value (tree expr)
581 tree a = create_tmp_var_raw (TREE_TYPE (expr), "value");
583 var_ann (a)->uid = pre_uid++;
585 if (dump_file && (dump_flags & TDF_DETAILS))
587 fprintf (dump_file, "Created value ");
588 print_generic_expr (dump_file, a, dump_flags);
589 fprintf (dump_file, " for ");
590 print_generic_expr (dump_file, expr, dump_flags);
591 fprintf (dump_file, "\n");
596 /* Like lookup, but creates a new value for expression E if E doesn't
597 already have a value.
598 Return the existing/created value for E. */
601 lookup_or_add (htab_t table, tree e)
603 tree x = lookup (table, e);
607 v = create_new_value (e);
611 set_value_handle (e, x);
616 /* Return true if value V exists in the bitmap for SET. */
619 value_exists_in_set_bitmap (value_set_t set, tree v)
621 if (TREE_CODE (v) != VAR_DECL)
626 return bitmap_bit_p (set->values, get_var_ann (v)->uid);
629 /* Remove value V from the bitmap for SET. */
632 value_remove_from_set_bitmap (value_set_t set, tree v)
634 if (TREE_CODE (v) != VAR_DECL)
636 #ifdef ENABLE_CHECKING
642 bitmap_clear_bit (set->values, get_var_ann (v)->uid);
646 /* Insert the value number V into the bitmap of values existing in
650 value_insert_into_set_bitmap (value_set_t set, tree v)
652 if (TREE_CODE (v) != VAR_DECL)
654 #ifdef ENABLE_CHECKING
658 if (set->values == NULL)
660 set->values = BITMAP_GGC_ALLOC ();
661 bitmap_clear (set->values);
663 bitmap_set_bit (set->values, get_var_ann (v)->uid);
666 /* Create a new set. */
669 set_new (bool indexed)
672 ret = pool_alloc (value_set_pool);
673 ret->head = ret->tail = NULL;
675 ret->indexed = indexed;
681 /* Insert EXPR into SET. */
684 insert_into_set (value_set_t set, tree expr)
686 value_set_node_t newnode = pool_alloc (value_set_node_pool);
687 tree val = get_value_handle (expr);
694 /* For indexed sets, insert the value into the set value bitmap.
695 For all sets, add it to the linked list and increment the list
698 value_insert_into_set_bitmap (set, val);
700 newnode->next = NULL;
701 newnode->expr = expr;
703 if (set->head == NULL)
705 set->head = set->tail = newnode;
709 set->tail->next = newnode;
714 /* Copy the set ORIG to the set DEST. */
717 set_copy (value_set_t dest, value_set_t orig)
719 value_set_node_t node;
721 if (!orig || !orig->head)
724 for (node = orig->head;
728 insert_into_set (dest, node->expr);
732 /* Remove EXPR from SET. */
735 set_remove (value_set_t set, tree expr)
737 value_set_node_t node, prev;
739 /* Remove the value of EXPR from the bitmap, decrement the set
740 length, and remove it from the actual double linked list. */
741 value_remove_from_set_bitmap (set, get_value_handle (expr));
744 for (node = set->head;
746 prev = node, node = node->next)
748 if (node->expr == expr)
751 set->head = node->next;
753 prev->next= node->next;
755 if (node == set->tail)
757 pool_free (value_set_node_pool, node);
763 /* Return true if SET contains the value VAL. */
766 set_contains_value (value_set_t set, tree val)
768 /* This is only referring to the flag above that we set on
769 values referring to numerical constants, because we know that we
770 are dealing with one of the value handles we created. */
771 if (TREE_CONSTANT (val))
774 if (set->length == 0)
777 return value_exists_in_set_bitmap (set, val);
780 /* Replace the leader for the value LOOKFOR in SET with EXPR. */
783 set_replace_value (value_set_t set, tree lookfor, tree expr)
785 value_set_node_t node = set->head;
787 /* The lookup is probably more expensive than walking the linked
788 list when we have only a small number of nodes. */
789 if (!set_contains_value (set, lookfor))
792 for (node = set->head;
796 if (get_value_handle (node->expr) == lookfor)
804 /* Return true if the set contains expression (not value) EXPR. */
807 set_contains (value_set_t set, tree expr)
809 value_set_node_t node;
811 for (node = set->head;
815 if (operand_equal_p (node->expr, expr, 0))
821 /* Subtract set B from set A, and return the new set. */
824 set_subtract (value_set_t a, value_set_t b, bool indexed)
826 value_set_t ret = set_new (indexed);
827 value_set_node_t node;
832 if (!set_contains (b, node->expr))
833 insert_into_set (ret, node->expr);
838 /* Return true if two sets are equal. */
841 set_equal (value_set_t a, value_set_t b)
843 value_set_node_t node;
845 if (a->length != b->length)
851 if (!set_contains_value (b, get_value_handle (node->expr)))
857 /* Replace the value for EXPR in SET with EXPR. */
859 value_replace_in_set (value_set_t set, tree expr)
861 tree val = get_value_handle (expr);
863 if (set->length == 0)
866 set_replace_value (set, val, expr);
869 /* Insert the value for EXPR into SET, if it doesn't exist already. */
872 value_insert_into_set (value_set_t set, tree expr)
874 tree val = get_value_handle (expr);
876 /* Constant values exist everywhere. */
877 if (TREE_CONSTANT (val))
880 if (!set_contains_value (set, val))
881 insert_into_set (set, expr);
885 /* Print out the value_set SET to OUTFILE. */
888 print_value_set (FILE *outfile, value_set_t set,
889 const char *setname, int blockindex)
891 value_set_node_t node;
892 fprintf (outfile, "%s[%d] := { ", setname, blockindex);
895 for (node = set->head;
899 print_generic_expr (outfile, node->expr, 0);
901 fprintf (outfile, " (");
902 print_generic_expr (outfile, get_value_handle (node->expr), 0);
903 fprintf (outfile, ") ");
906 fprintf (outfile, ", ");
910 fprintf (outfile, " }\n");
913 /* Print out the expressions that have VAL to OUTFILE. */
915 print_value_expressions (FILE *outfile, tree val)
917 var_ann_t va = var_ann (val);
918 if (va && va->expr_set)
919 print_value_set (outfile, va->expr_set,
920 IDENTIFIER_POINTER (DECL_NAME (val)), 0);
925 debug_value_expressions (tree val)
927 print_value_expressions (stderr, val);
931 void debug_value_set (value_set_t, const char *, int);
934 debug_value_set (value_set_t set, const char *setname, int blockindex)
936 print_value_set (stderr, set, setname, blockindex);
939 /* Translate EXPR using phis in PHIBLOCK, so that it has the values of
940 the phis in PRED. Return NULL if we can't find a leader for each
941 part of the translated expression. */
944 phi_translate (tree expr, value_set_t set, basic_block pred,
945 basic_block phiblock)
947 tree phitrans = NULL;
953 /* Phi translations of a given expression don't change, */
954 phitrans = phi_trans_lookup (expr, pred);
959 switch (TREE_CODE_CLASS (TREE_CODE (expr)))
963 tree oldop1 = TREE_OPERAND (expr, 0);
964 tree oldop2 = TREE_OPERAND (expr, 1);
969 newop1 = phi_translate (find_leader (set, oldop1),
970 set, pred, phiblock);
973 newop2 = phi_translate (find_leader (set, oldop2),
974 set, pred, phiblock);
977 if (newop1 != oldop1 || newop2 != oldop2)
979 newexpr = pool_alloc (binary_node_pool);
980 memcpy (newexpr, expr, tree_size (expr));
981 create_expr_ann (newexpr);
982 TREE_OPERAND (newexpr, 0) = newop1 == oldop1 ? oldop1 : get_value_handle (newop1);
983 TREE_OPERAND (newexpr, 1) = newop2 == oldop2 ? oldop2 : get_value_handle (newop2);
984 lookup_or_add (value_table, newexpr);
986 phi_trans_add (oldexpr, newexpr, pred);
992 tree oldop1 = TREE_OPERAND (expr, 0);
996 newop1 = phi_translate (find_leader (set, oldop1),
997 set, pred, phiblock);
1000 if (newop1 != oldop1)
1002 newexpr = pool_alloc (unary_node_pool);
1003 memcpy (newexpr, expr, tree_size (expr));
1004 create_expr_ann (newexpr);
1005 TREE_OPERAND (newexpr, 0) = get_value_handle (newop1);
1006 lookup_or_add (value_table, newexpr);
1008 phi_trans_add (oldexpr, newexpr, pred);
1018 if (TREE_CODE (expr) != SSA_NAME)
1020 if (TREE_CODE (SSA_NAME_DEF_STMT (expr)) == PHI_NODE)
1021 phi = SSA_NAME_DEF_STMT (expr);
1025 for (i = 0; i < PHI_NUM_ARGS (phi); i++)
1026 if (PHI_ARG_EDGE (phi, i)->src == pred)
1029 if (is_undefined_value (PHI_ARG_DEF (phi, i)))
1031 val = lookup_or_add (value_table, PHI_ARG_DEF (phi, i));
1032 return PHI_ARG_DEF (phi, i);
1041 phi_translate_set (value_set_t dest, value_set_t set, basic_block pred,
1042 basic_block phiblock)
1044 value_set_node_t node;
1045 for (node = set->head;
1050 translated = phi_translate (node->expr, set, pred, phiblock);
1051 phi_trans_add (node->expr, translated, pred);
1053 if (translated != NULL)
1054 value_insert_into_set (dest, translated);
1058 /* Find the leader for a value (IE the name representing that
1059 value) in a given set, and return it. Return NULL if no leader is
1063 find_leader (value_set_t set, tree val)
1065 value_set_node_t node;
1070 if (TREE_CONSTANT (val))
1071 return TREE_CHAIN (val);
1073 if (set->length == 0)
1076 if (value_exists_in_set_bitmap (set, val))
1078 for (node = set->head;
1082 if (get_value_handle (node->expr) == val)
1089 /* Determine if the expression EXPR is valid in SET. This means that
1090 we have a leader for each part of the expression (if it consists of
1091 values), or the expression is an SSA_NAME.
1093 NB: We never should run into a case where we have SSA_NAME +
1094 SSA_NAME or SSA_NAME + value. The sets valid_in_set is called on,
1095 the ANTIC sets, will only ever have SSA_NAME's or binary value
1096 expression (IE VALUE1 + VALUE2) */
1099 valid_in_set (value_set_t set, tree expr)
1101 switch (TREE_CODE_CLASS (TREE_CODE (expr)))
1105 tree op1 = TREE_OPERAND (expr, 0);
1106 tree op2 = TREE_OPERAND (expr, 1);
1107 return set_contains_value (set, op1) && set_contains_value (set, op2);
1112 tree op1 = TREE_OPERAND (expr, 0);
1113 return set_contains_value (set, op1);
1118 if (TREE_CODE (expr) == SSA_NAME)
1128 /* Clean the set of expressions that are no longer valid in SET. This
1129 means expressions that are made up of values we have no leaders for
1133 clean (value_set_t set)
1135 value_set_node_t node;
1136 value_set_node_t next;
1141 if (!valid_in_set (set, node->expr))
1142 set_remove (set, node->expr);
1147 /* Compute the ANTIC set for BLOCK.
1149 ANTIC_OUT[BLOCK] = intersection of ANTIC_IN[b] for all succ(BLOCK), if
1151 ANTIC_OUT[BLOCK] = phi_translate (ANTIC_IN[succ(BLOCK)]) if
1154 ANTIC_IN[BLOCK] = clean(ANTIC_OUT[BLOCK] U EXP_GEN[BLOCK] -
1157 Iterate until fixpointed.
1159 XXX: It would be nice to either write a set_clear, and use it for
1160 antic_out, or to mark the antic_out set as deleted at the end
1161 of this routine, so that the pool can hand the same memory back out
1162 again for the next antic_out. */
1166 compute_antic_aux (basic_block block)
1170 bool changed = false;
1171 value_set_t S, old, ANTIC_OUT;
1172 value_set_node_t node;
1174 ANTIC_OUT = S = NULL;
1175 /* If any edges from predecessors are abnormal, antic_in is empty, so
1176 punt. Remember that the block has an incoming abnormal edge by
1177 setting the BB_VISITED flag. */
1178 if (! (block->flags & BB_VISITED))
1180 for (e = block->pred; e; e = e->pred_next)
1181 if (e->flags & EDGE_ABNORMAL)
1183 block->flags |= BB_VISITED;
1187 if (block->flags & BB_VISITED)
1194 old = set_new (false);
1195 set_copy (old, ANTIC_IN (block));
1196 ANTIC_OUT = set_new (true);
1198 /* If the block has no successors, ANTIC_OUT is empty, because it is
1200 if (block->succ == NULL);
1202 /* If we have one successor, we could have some phi nodes to
1203 translate through. */
1204 else if (block->succ->succ_next == NULL)
1206 phi_translate_set (ANTIC_OUT, ANTIC_IN(block->succ->dest),
1207 block, block->succ->dest);
1209 /* If we have multiple successors, we take the intersection of all of
1213 varray_type worklist;
1216 basic_block bprime, first;
1218 VARRAY_BB_INIT (worklist, 1, "succ");
1222 VARRAY_PUSH_BB (worklist, e->dest);
1225 first = VARRAY_BB (worklist, 0);
1226 set_copy (ANTIC_OUT, ANTIC_IN (first));
1228 for (i = 1; i < VARRAY_ACTIVE_SIZE (worklist); i++)
1230 bprime = VARRAY_BB (worklist, i);
1231 node = ANTIC_OUT->head;
1235 value_set_node_t next = node->next;
1236 val = get_value_handle (node->expr);
1237 if (!set_contains_value (ANTIC_IN (bprime), val))
1238 set_remove (ANTIC_OUT, node->expr);
1242 VARRAY_CLEAR (worklist);
1245 /* Generate ANTIC_OUT - TMP_GEN */
1246 S = set_subtract (ANTIC_OUT, TMP_GEN (block), false);
1248 /* Start ANTIC_IN with EXP_GEN - TMP_GEN */
1249 ANTIC_IN (block) = set_subtract (EXP_GEN (block),TMP_GEN (block), true);
1251 /* Then union in the ANTIC_OUT - TMP_GEN values, to get ANTIC_OUT U
1252 EXP_GEN - TMP_GEN */
1253 for (node = S->head;
1257 value_insert_into_set (ANTIC_IN (block), node->expr);
1259 clean (ANTIC_IN (block));
1262 if (!set_equal (old, ANTIC_IN (block)))
1266 if (dump_file && (dump_flags & TDF_DETAILS))
1269 print_value_set (dump_file, ANTIC_OUT, "ANTIC_OUT", block->index);
1270 print_value_set (dump_file, ANTIC_IN (block), "ANTIC_IN", block->index);
1272 print_value_set (dump_file, S, "S", block->index);
1276 for (son = first_dom_son (CDI_POST_DOMINATORS, block);
1278 son = next_dom_son (CDI_POST_DOMINATORS, son))
1280 changed |= compute_antic_aux (son);
1285 /* Compute ANTIC sets. */
1288 compute_antic (void)
1290 bool changed = true;
1292 int num_iterations = 0;
1295 ANTIC_IN (bb) = set_new (true);
1296 bb->flags &= ~BB_VISITED;
1303 changed = compute_antic_aux (EXIT_BLOCK_PTR);
1305 if (num_iterations > 2 && dump_file && (dump_flags & TDF_STATS))
1306 fprintf (dump_file, "compute_antic required %d iterations\n", num_iterations);
1309 /* Perform insertion of partially redundant values.
1310 For BLOCK, do the following:
1311 1. Propagate the NEW_SETS of the dominator into the current block.
1312 If the block has multiple predecessors,
1313 2a. Iterate over the ANTIC expressions for the block to see if
1314 any of them are partially redundant.
1315 2b. If so, insert them into the necessary predecessors to make
1316 the expression fully redundant.
1317 2c. Insert a new PHI merging the values of the predecessors.
1318 2d. Insert the new PHI, and the new expressions, into the
1320 3. Recursively call ourselves on the dominator children of BLOCK.
1324 insert_aux (basic_block block)
1327 bool new_stuff = false;
1333 dom = get_immediate_dominator (CDI_DOMINATORS, block);
1336 e = NEW_SETS (dom)->head;
1339 insert_into_set (NEW_SETS (block), e->expr);
1340 value_replace_in_set (AVAIL_OUT (block), e->expr);
1343 if (block->pred->pred_next)
1345 value_set_node_t node;
1346 for (node = ANTIC_IN (block)->head;
1350 if (TREE_CODE_CLASS (TREE_CODE (node->expr)) == '2'
1351 || TREE_CODE_CLASS (TREE_CODE (node->expr)) == '1')
1355 bool by_some = false;
1356 bool cant_insert = false;
1357 bool all_same = true;
1358 tree first_s = NULL;
1363 val = get_value_handle (node->expr);
1364 if (set_contains_value (PHI_GEN (block), val))
1366 if (set_contains_value (AVAIL_OUT (dom), val))
1368 if (dump_file && (dump_flags & TDF_DETAILS))
1369 fprintf (dump_file, "Found fully redundant value\n");
1373 avail = xcalloc (last_basic_block, sizeof (tree));
1374 for (pred = block->pred;
1376 pred = pred->pred_next)
1381 eprime = phi_translate (node->expr,
1385 /* eprime will generally only be NULL if the
1386 value of the expression, translated
1387 through the PHI for this predecessor, is
1388 undefined. If that is the case, we can't
1389 make the expression fully redundant,
1390 because its value is undefined along a
1391 predecessor path. We can thus break out
1392 early because it doesn't matter what the
1393 rest of the results are. */
1400 vprime = get_value_handle (eprime);
1403 edoubleprime = find_leader (AVAIL_OUT (bprime),
1405 if (edoubleprime == NULL)
1407 avail[bprime->index] = eprime;
1412 avail[bprime->index] = edoubleprime;
1414 if (first_s == NULL)
1415 first_s = edoubleprime;
1416 else if (first_s != edoubleprime)
1418 if (first_s != edoubleprime
1419 && operand_equal_p (first_s, edoubleprime, 0))
1423 /* If we can insert it, it's not the same value
1424 already existing along every predecessor, and
1425 it's defined by some predecessor, it is
1426 partially redundant. */
1427 if (!cant_insert && !all_same && by_some)
1429 tree type = TREE_TYPE (avail[block->pred->src->index]);
1433 if (dump_file && (dump_flags & TDF_DETAILS))
1435 fprintf (dump_file, "Found partial redundancy for expression ");
1436 print_generic_expr (dump_file, node->expr, 0);
1437 fprintf (dump_file, "\n");
1440 /* Make the necessary insertions. */
1441 for (pred = block->pred;
1443 pred = pred->pred_next)
1446 eprime = avail[bprime->index];
1447 if (TREE_CODE_CLASS (TREE_CODE (eprime)) == '2')
1451 s1 = find_leader (AVAIL_OUT (bprime),
1452 TREE_OPERAND (eprime, 0));
1453 /* Depending on the order we process
1454 DOM branches in, the value may
1455 not have propagated to all the
1456 dom children yet during this
1457 iteration. In this case, the
1458 value will always be in the
1459 NEW_SETS for *our* dominator */
1461 s1 = find_leader (NEW_SETS (dom),
1462 TREE_OPERAND (eprime, 0));
1466 s2 = find_leader (AVAIL_OUT (bprime),
1467 TREE_OPERAND (eprime, 1));
1469 s2 = find_leader (NEW_SETS (dom),
1470 TREE_OPERAND (eprime, 1));
1474 temp = create_tmp_var (TREE_TYPE (eprime),
1476 add_referenced_tmp_var (temp);
1477 newexpr = build (TREE_CODE (eprime),
1480 newexpr = build (MODIFY_EXPR,
1483 temp = make_ssa_name (temp, newexpr);
1484 TREE_OPERAND (newexpr, 0) = temp;
1485 bsi_insert_on_edge (pred, newexpr);
1486 bsi_commit_edge_inserts (NULL);
1488 if (dump_file && (dump_flags & TDF_DETAILS))
1490 fprintf (dump_file, "Inserted ");
1491 print_generic_expr (dump_file, newexpr, 0);
1492 fprintf (dump_file, " in predecessor %d\n", pred->src->index);
1494 pre_stats.insertions++;
1495 v = lookup_or_add (value_table, eprime);
1496 add (value_table, temp, v);
1497 insert_into_set (NEW_SETS (bprime), temp);
1498 value_insert_into_set (AVAIL_OUT (bprime),
1500 avail[bprime->index] = temp;
1502 else if (TREE_CODE_CLASS (TREE_CODE (eprime)) == '1')
1506 s1 = find_leader (AVAIL_OUT (bprime),
1507 TREE_OPERAND (eprime, 0));
1508 /* Depending on the order we process
1509 DOM branches in, the value may not have
1510 propagated to all the dom
1511 children yet in the current
1512 iteration, but it will be in
1513 NEW_SETS if it is not yet
1517 s1 = find_leader (NEW_SETS (dom),
1518 TREE_OPERAND (eprime, 0));
1522 temp = create_tmp_var (TREE_TYPE (eprime),
1524 add_referenced_tmp_var (temp);
1525 newexpr = build (TREE_CODE (eprime),
1528 newexpr = build (MODIFY_EXPR,
1531 temp = make_ssa_name (temp, newexpr);
1532 TREE_OPERAND (newexpr, 0) = temp;
1533 bsi_insert_on_edge (pred, newexpr);
1534 bsi_commit_edge_inserts (NULL);
1536 if (dump_file && (dump_flags & TDF_DETAILS))
1538 fprintf (dump_file, "Inserted ");
1539 print_generic_expr (dump_file, newexpr, 0);
1540 fprintf (dump_file, " in predecessor %d\n", pred->src->index);
1542 pre_stats.insertions++;
1543 v = lookup_or_add (value_table, eprime);
1544 add (value_table, temp, v);
1545 insert_into_set (NEW_SETS (bprime), temp);
1546 value_insert_into_set (AVAIL_OUT (bprime),
1548 avail[bprime->index] = temp;
1551 /* Now build a phi for the new variable. */
1552 temp = create_tmp_var (type, "prephitmp");
1553 add_referenced_tmp_var (temp);
1554 temp = create_phi_node (temp, block);
1555 add (value_table, PHI_RESULT (temp), val);
1558 if (!set_contains_value (AVAIL_OUT (block), val))
1559 insert_into_set (AVAIL_OUT (block),
1563 value_replace_in_set (AVAIL_OUT (block),
1565 for (pred = block->pred;
1567 pred = pred->pred_next)
1569 add_phi_arg (&temp, avail[pred->src->index],
1572 if (dump_file && (dump_flags & TDF_DETAILS))
1574 fprintf (dump_file, "Created phi ");
1575 print_generic_expr (dump_file, temp, 0);
1576 fprintf (dump_file, " in block %d\n", block->index);
1580 insert_into_set (NEW_SETS (block),
1582 insert_into_set (PHI_GEN (block),
1592 for (son = first_dom_son (CDI_DOMINATORS, block);
1594 son = next_dom_son (CDI_DOMINATORS, son))
1596 new_stuff |= insert_aux (son);
1602 /* Perform insertion of partially redundant values. */
1607 bool new_stuff = true;
1609 int num_iterations = 0;
1612 NEW_SETS (bb) = set_new (true);
1618 new_stuff = insert_aux (ENTRY_BLOCK_PTR);
1620 if (num_iterations > 2 && dump_file && (dump_flags & TDF_STATS))
1621 fprintf (dump_file, "insert required %d iterations\n", num_iterations);
1624 /* Return true if EXPR has no defining statement in this procedure,
1625 *AND* isn't a live-on-entry parameter. */
1627 is_undefined_value (tree expr)
1630 #ifdef ENABLE_CHECKING
1631 /* We should never be handed DECL's */
1635 if (TREE_CODE (expr) == SSA_NAME)
1637 /* XXX: Is this the correct test? */
1638 if (TREE_CODE (SSA_NAME_VAR (expr)) == PARM_DECL)
1640 if (IS_EMPTY_STMT (SSA_NAME_DEF_STMT (expr)))
1646 /* Compute the AVAIL set for BLOCK.
1647 This function performs value numbering of the statements in BLOCK.
1648 The AVAIL sets are built from information we glean while doing this
1649 value numbering, since the AVAIL sets contain only entry per
1653 AVAIL_IN[BLOCK] = AVAIL_OUT[dom(BLOCK)].
1654 AVAIL_OUT[BLOCK] = AVAIL_IN[BLOCK] U PHI_GEN[BLOCK] U
1659 compute_avail (basic_block block)
1663 /* For arguments with default definitions, we pretend they are
1664 defined in the entry block. */
1665 if (block == ENTRY_BLOCK_PTR)
1668 for (param = DECL_ARGUMENTS (current_function_decl);
1670 param = TREE_CHAIN (param))
1672 if (default_def (param) != NULL)
1675 tree def = default_def (param);
1676 val = lookup_or_add (value_table, def);
1677 insert_into_set (TMP_GEN (block), def);
1678 value_insert_into_set (AVAIL_OUT (block), def);
1684 block_stmt_iterator bsi;
1688 dom = get_immediate_dominator (CDI_DOMINATORS, block);
1690 set_copy (AVAIL_OUT (block), AVAIL_OUT (dom));
1691 for (phi = phi_nodes (block); phi; phi = PHI_CHAIN (phi))
1693 /* Ignore virtual PHIs until we can do PRE on expressions
1694 with virtual operands. */
1695 if (!is_gimple_reg (SSA_NAME_VAR (PHI_RESULT (phi))))
1698 lookup_or_add (value_table, PHI_RESULT (phi));
1699 value_insert_into_set (AVAIL_OUT (block), PHI_RESULT (phi));
1700 insert_into_set (PHI_GEN (block), PHI_RESULT (phi));
1703 for (bsi = bsi_start (block); !bsi_end_p (bsi); bsi_next (&bsi))
1706 stmt = bsi_stmt (bsi);
1707 get_stmt_operands (stmt);
1709 if (NUM_VUSES (STMT_VUSE_OPS (stmt))
1710 || NUM_V_MUST_DEFS (STMT_V_MUST_DEF_OPS (stmt))
1711 || NUM_V_MAY_DEFS (STMT_V_MAY_DEF_OPS (stmt))
1712 || stmt_ann (stmt)->has_volatile_ops)
1715 for (j = 0; j < NUM_DEFS (STMT_DEF_OPS (stmt)); j++)
1717 tree def = DEF_OP (STMT_DEF_OPS (stmt), j);
1718 lookup_or_add (value_table, def);
1719 insert_into_set (TMP_GEN (block), def);
1720 value_insert_into_set (AVAIL_OUT (block), def);
1722 for (j = 0; j < NUM_USES (STMT_USE_OPS (stmt)); j++)
1724 tree use = USE_OP (STMT_USE_OPS (stmt), j);
1725 if (TREE_CODE (use) == SSA_NAME)
1727 lookup_or_add (value_table, use);
1728 insert_into_set (TMP_GEN (block), use);
1729 value_insert_into_set (AVAIL_OUT (block), use);
1734 else if (TREE_CODE (stmt) == RETURN_EXPR
1735 && TREE_OPERAND (stmt, 0)
1736 && TREE_CODE (TREE_OPERAND (stmt, 0)) == MODIFY_EXPR)
1737 stmt = TREE_OPERAND (stmt, 0);
1739 if (TREE_CODE (stmt) == MODIFY_EXPR)
1741 op0 = TREE_OPERAND (stmt, 0);
1742 if (TREE_CODE (op0) != SSA_NAME)
1744 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op0))
1746 op1 = TREE_OPERAND (stmt, 1);
1747 STRIP_USELESS_TYPE_CONVERSION (op1);
1748 if (TREE_CODE_CLASS (TREE_CODE (op1)) == 'c')
1750 add (value_table, op0, lookup_or_add (value_table, op1));
1751 insert_into_set (TMP_GEN (block), op0);
1752 value_insert_into_set (AVAIL_OUT (block), op0);
1754 else if (TREE_CODE_CLASS (TREE_CODE (op1)) == '2')
1757 tree val, val1, val2;
1759 bop1 = TREE_OPERAND (op1, 0);
1760 bop2 = TREE_OPERAND (op1, 1);
1761 val1 = lookup_or_add (value_table, bop1);
1762 val2 = lookup_or_add (value_table, bop2);
1764 newt = pool_alloc (binary_node_pool);
1765 memcpy (newt, op1, tree_size (op1));
1766 TREE_OPERAND (newt, 0) = val1;
1767 TREE_OPERAND (newt, 1) = val2;
1768 val = lookup_or_add (value_table, newt);
1769 add (value_table, op0, val);
1770 if (!is_undefined_value (bop1))
1771 value_insert_into_set (EXP_GEN (block), bop1);
1772 if (!is_undefined_value (bop2))
1773 value_insert_into_set (EXP_GEN (block), bop2);
1774 value_insert_into_set (EXP_GEN (block), newt);
1775 insert_into_set (TMP_GEN (block), op0);
1776 value_insert_into_set (AVAIL_OUT (block), op0);
1778 else if (TREE_CODE_CLASS (TREE_CODE (op1)) == '1'
1779 && !is_gimple_cast (op1))
1784 uop = TREE_OPERAND (op1, 0);
1785 val1 = lookup_or_add (value_table, uop);
1786 newt = pool_alloc (unary_node_pool);
1787 memcpy (newt, op1, tree_size (op1));
1788 TREE_OPERAND (newt, 0) = val1;
1789 val = lookup_or_add (value_table, newt);
1790 add (value_table, op0, val);
1791 if (!is_undefined_value (uop))
1792 value_insert_into_set (EXP_GEN (block), uop);
1793 value_insert_into_set (EXP_GEN (block), newt);
1794 insert_into_set (TMP_GEN (block), op0);
1795 value_insert_into_set (AVAIL_OUT (block), op0);
1797 else if (TREE_CODE (op1) == SSA_NAME)
1799 tree val = lookup_or_add (value_table, op1);
1800 add (value_table, op0, val);
1801 if (!is_undefined_value (op1))
1802 value_insert_into_set (EXP_GEN (block), op1);
1803 insert_into_set (TMP_GEN (block), op0);
1804 value_insert_into_set (AVAIL_OUT (block), op0);
1809 for (j = 0; j < NUM_DEFS (STMT_DEF_OPS (stmt)); j++)
1811 tree def = DEF_OP (STMT_DEF_OPS (stmt), j);
1812 lookup_or_add (value_table, def);
1813 insert_into_set (TMP_GEN (block), def);
1814 value_insert_into_set (AVAIL_OUT (block), def);
1818 for (j = 0; j < NUM_USES (STMT_USE_OPS (stmt)); j++)
1820 tree use = USE_OP (STMT_USE_OPS (stmt), j);
1821 if (TREE_CODE (use) == SSA_NAME)
1823 lookup_or_add (value_table, use);
1824 insert_into_set (TMP_GEN (block), use);
1825 value_insert_into_set (AVAIL_OUT (block), use);
1833 for (j = 0; j < NUM_DEFS (STMT_DEF_OPS (stmt)); j++)
1835 tree def = DEF_OP (STMT_DEF_OPS (stmt), j);
1836 lookup_or_add (value_table, def);
1837 insert_into_set (TMP_GEN (block), def);
1838 value_insert_into_set (AVAIL_OUT (block), def);
1840 for (j = 0; j < NUM_USES (STMT_USE_OPS (stmt)); j++)
1842 tree use = USE_OP (STMT_USE_OPS (stmt), j);
1843 if (TREE_CODE (use) == SSA_NAME)
1845 lookup_or_add (value_table, use);
1846 insert_into_set (TMP_GEN (block), use);
1847 value_insert_into_set (AVAIL_OUT (block), use);
1853 for (son = first_dom_son (CDI_DOMINATORS, block);
1855 son = next_dom_son (CDI_DOMINATORS, son))
1856 compute_avail (son);
1860 /* Eliminate fully redundant computations. */
1869 block_stmt_iterator i;
1871 for (i = bsi_start (b); !bsi_end_p (i); bsi_next (&i))
1873 tree stmt = bsi_stmt (i);
1875 if (NUM_VUSES (STMT_VUSE_OPS (stmt))
1876 || NUM_V_MUST_DEFS (STMT_V_MUST_DEF_OPS (stmt))
1877 || NUM_V_MAY_DEFS (STMT_V_MAY_DEF_OPS (stmt))
1878 || stmt_ann (stmt)->has_volatile_ops)
1880 /* Lookup the RHS of the expression, see if we have an
1881 available computation for it. If so, replace the RHS with
1882 the available computation. */
1883 if (TREE_CODE (stmt) == MODIFY_EXPR)
1885 tree t = TREE_OPERAND (stmt, 0);
1886 tree expr = TREE_OPERAND (stmt, 1);
1888 /* There is no point in eliminating NOP_EXPR, it isn't
1889 supposed to generate any code. */
1890 if (TREE_CODE (expr) == NOP_EXPR
1891 || (TREE_CODE_CLASS (TREE_CODE (expr)) != '2'
1892 && TREE_CODE_CLASS (TREE_CODE (expr)) != '1'))
1894 sprime = find_leader (AVAIL_OUT (b),
1895 lookup (value_table, t));
1898 && may_propagate_copy (sprime, TREE_OPERAND (stmt, 1)))
1900 if (dump_file && (dump_flags & TDF_DETAILS))
1902 fprintf (dump_file, "Replaced ");
1903 print_generic_expr (dump_file, expr, 0);
1904 fprintf (dump_file, " with ");
1905 print_generic_expr (dump_file, sprime, 0);
1906 fprintf (dump_file, " in ");
1907 print_generic_stmt (dump_file, stmt, 0);
1909 pre_stats.eliminations++;
1910 propagate_value (&TREE_OPERAND (stmt, 1), sprime);
1919 /* Main entry point to the SSA-PRE pass.
1921 PHASE indicates which dump file from the DUMP_FILES array to use when
1922 dumping debugging information. */
1929 pre_uid = num_referenced_vars;
1930 memset (&pre_stats, 0, sizeof (pre_stats));
1933 bb->aux = xcalloc (1, sizeof (struct bb_value_sets));
1935 phi_translate_table = htab_create (511, expr_pred_trans_hash,
1938 value_table = htab_create (511, val_expr_pair_hash,
1939 val_expr_pair_expr_eq, free);
1940 value_set_pool = create_alloc_pool ("Value sets",
1941 sizeof (struct value_set), 30);
1942 value_set_node_pool = create_alloc_pool ("Value set nodes",
1943 sizeof (struct value_set_node), 30);
1944 calculate_dominance_info (CDI_POST_DOMINATORS);
1945 calculate_dominance_info (CDI_DOMINATORS);
1946 tsize = tree_size (build (PLUS_EXPR, void_type_node, NULL_TREE,
1948 binary_node_pool = create_alloc_pool ("Binary tree nodes", tsize, 30);
1949 tsize = tree_size (build1 (NEGATE_EXPR, void_type_node, NULL_TREE));
1950 unary_node_pool = create_alloc_pool ("Unary tree nodes", tsize, 30);
1954 EXP_GEN (bb) = set_new (true);
1955 PHI_GEN (bb) = set_new (true);
1956 TMP_GEN (bb) = set_new (false);
1957 AVAIL_OUT (bb) = set_new (true);
1960 compute_avail (ENTRY_BLOCK_PTR);
1962 if (dump_file && (dump_flags & TDF_DETAILS))
1966 print_value_set (dump_file, EXP_GEN (bb), "exp_gen", bb->index);
1967 print_value_set (dump_file, TMP_GEN (bb), "tmp_gen", bb->index);
1968 print_value_set (dump_file, AVAIL_OUT (bb), "avail_out", bb->index);
1972 /* Insert can get quite slow on an incredibly large number of basic
1973 blocks due to some quadratic behavior. Until this behavior is
1974 fixed, don't run it when he have an incredibly large number of
1975 bb's. If we aren't going to run insert, there is no point in
1976 computing ANTIC, either, even though it's plenty fast. */
1978 if (n_basic_blocks < 4000)
1986 if (dump_file && (dump_flags & TDF_STATS))
1988 fprintf (dump_file, "Insertions:%d\n", pre_stats.insertions);
1989 fprintf (dump_file, "New PHIs:%d\n", pre_stats.phis);
1990 fprintf (dump_file, "Eliminated:%d\n", pre_stats.eliminations);
1993 free_alloc_pool (value_set_pool);
1994 free_alloc_pool (value_set_node_pool);
1995 free_alloc_pool (binary_node_pool);
1996 free_alloc_pool (unary_node_pool);
1997 htab_delete (value_table);
1998 htab_delete (phi_translate_table);
2005 free_dominance_info (CDI_POST_DOMINATORS);
2011 return flag_tree_pre != 0;
2014 struct tree_opt_pass pass_pre =
2017 gate_pre, /* gate */
2018 execute_pre, /* execute */
2021 0, /* static_pass_number */
2022 TV_TREE_PRE, /* tv_id */
2023 PROP_no_crit_edges | PROP_cfg | PROP_ssa,/* properties_required */
2024 0, /* properties_provided */
2025 0, /* properties_destroyed */
2026 0, /* todo_flags_start */
2027 TODO_dump_func | TODO_ggc_collect | TODO_verify_ssa /* todo_flags_finish */