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'
378 tree_ann_t ann = tree_ann (expr);
380 return ann->common.value_handle;
387 /* Set the value handle for expression E to value V */
390 set_value_handle (tree e, tree v)
394 else if (TREE_CODE (e) == SSA_NAME)
395 SSA_NAME_VALUE (e) = v;
396 else if (TREE_CODE_CLASS (TREE_CODE (e)) == 'c'
398 get_tree_ann (e)->common.value_handle = v;
401 /* A three tuple {e, pred, v} used to cache phi translations in the
402 phi_translate_table. */
404 typedef struct expr_pred_trans_d
406 /* The expression. */
409 /* The predecessor block along which we translated the expression. */
412 /* The value that resulted from the translation. */
415 /* The hashcode for the expression, pred pair. This is cached for
418 } *expr_pred_trans_t;
420 /* Return the hash value for a phi translation table entry. */
423 expr_pred_trans_hash (const void *p)
425 const expr_pred_trans_t ve = (expr_pred_trans_t) p;
429 /* Return true if two phi translation table entries are the same.
430 P1 and P2 should point to the expr_pred_trans_t's to be compared.*/
433 expr_pred_trans_eq (const void *p1, const void *p2)
435 const expr_pred_trans_t ve1 = (expr_pred_trans_t) p1;
436 const expr_pred_trans_t ve2 = (expr_pred_trans_t) p2;
437 basic_block b1 = ve1->pred;
438 basic_block b2 = ve2->pred;
441 /* If they are not translations for the same basic block, they can't
446 /* If they are for the same basic block, determine if the
447 expressions are equal. */
448 if (expressions_equal_p (ve1->e, ve2->e))
454 /* Search in the phi translation table for the translation of
455 expression E in basic block PRED. Return the translated value, if
456 found, NULL otherwise. */
459 phi_trans_lookup (tree e, basic_block pred)
462 struct expr_pred_trans_d ept;
465 ept.hashcode = iterative_hash_expr (e, (unsigned long) pred);
466 slot = htab_find_slot_with_hash (phi_translate_table, &ept, ept.hashcode,
471 return ((expr_pred_trans_t) *slot)->v;
475 /* Add the tuple mapping from {expression E, basic block PRED} to
476 value V, to the phi translation table. */
479 phi_trans_add (tree e, tree v, basic_block pred)
482 expr_pred_trans_t new_pair = xmalloc (sizeof (*new_pair));
484 new_pair->pred = pred;
486 new_pair->hashcode = iterative_hash_expr (e, (unsigned long) pred);
487 slot = htab_find_slot_with_hash (phi_translate_table, new_pair,
488 new_pair->hashcode, INSERT);
491 *slot = (void *) new_pair;
494 /* Search in TABLE for an existing instance of expression E,
495 and return its value, or NULL if none has been set. */
498 lookup (htab_t table, tree e)
501 struct val_expr_pair_d vep = {NULL, NULL, 0};
503 vep.hashcode = iterative_hash_expr (e,0);
504 slot = htab_find_slot_with_hash (table, &vep, vep.hashcode, NO_INSERT);
508 return ((val_expr_pair_t) *slot)->v;
511 /* Add expression E to the expression set of value V. */
514 add_to_value (tree v, tree e)
516 #if DEBUG_VALUE_EXPRESSIONS
517 var_ann_t va = var_ann (v);
519 /* For values representing numerical constants, we mark
520 TREE_CONSTANT as true and set the tree chain to the actual
521 constant. This is because unlike values involving expressions,
522 which are only available to use where the expressions are live, a
523 constant can be remade anywhere, and thus, is available
525 if (TREE_CODE_CLASS (TREE_CODE (e)) == 'c')
527 TREE_CONSTANT (v) = true;
530 else if (is_gimple_min_invariant (e))
532 TREE_CONSTANT (v) = true;
535 #if DEBUG_VALUE_EXPRESSIONS
536 if (va->expr_set == NULL)
537 va->expr_set = set_new (false);
538 insert_into_set (va->expr_set, e);
542 /* Insert E into TABLE with value V, and add expression E to the value
546 add (htab_t table, tree e, tree v)
550 val_expr_pair_t new_pair = xmalloc (sizeof (struct val_expr_pair_d));
553 new_pair->hashcode = iterative_hash_expr (e, 0);
554 slot = htab_find_slot_with_hash (table, new_pair, new_pair->hashcode,
558 *slot = (void *) new_pair;
559 set_value_handle (e, v);
565 /* A unique counter that is incremented every time we create a new
569 /* Create a new value handle for expression EXPR. */
572 create_new_value (tree expr)
574 tree a = create_tmp_var_raw (TREE_TYPE (expr), "value");
576 var_ann (a)->uid = pre_uid++;
578 if (dump_file && (dump_flags & TDF_DETAILS))
580 fprintf (dump_file, "Created value ");
581 print_generic_expr (dump_file, a, dump_flags);
582 fprintf (dump_file, " for ");
583 print_generic_expr (dump_file, expr, dump_flags);
584 fprintf (dump_file, "\n");
589 /* Like lookup, but creates a new value for expression E if E doesn't
590 already have a value.
591 Return the existing/created value for E. */
594 lookup_or_add (htab_t table, tree e)
596 tree x = lookup (table, e);
600 v = create_new_value (e);
604 set_value_handle (e, x);
609 /* Return true if value V exists in the bitmap for SET. */
612 value_exists_in_set_bitmap (value_set_t set, tree v)
614 if (TREE_CODE (v) != VAR_DECL)
619 return bitmap_bit_p (set->values, get_var_ann (v)->uid);
622 /* Remove value V from the bitmap for SET. */
625 value_remove_from_set_bitmap (value_set_t set, tree v)
627 if (TREE_CODE (v) != VAR_DECL)
629 #ifdef ENABLE_CHECKING
635 bitmap_clear_bit (set->values, get_var_ann (v)->uid);
639 /* Insert the value number V into the bitmap of values existing in
643 value_insert_into_set_bitmap (value_set_t set, tree v)
645 if (TREE_CODE (v) != VAR_DECL)
647 #ifdef ENABLE_CHECKING
651 if (set->values == NULL)
653 set->values = BITMAP_GGC_ALLOC ();
654 bitmap_clear (set->values);
656 bitmap_set_bit (set->values, get_var_ann (v)->uid);
659 /* Create a new set. */
662 set_new (bool indexed)
665 ret = pool_alloc (value_set_pool);
666 ret->head = ret->tail = NULL;
668 ret->indexed = indexed;
674 /* Insert EXPR into SET. */
677 insert_into_set (value_set_t set, tree expr)
679 value_set_node_t newnode = pool_alloc (value_set_node_pool);
680 tree val = get_value_handle (expr);
687 /* For indexed sets, insert the value into the set value bitmap.
688 For all sets, add it to the linked list and increment the list
691 value_insert_into_set_bitmap (set, val);
693 newnode->next = NULL;
694 newnode->expr = expr;
696 if (set->head == NULL)
698 set->head = set->tail = newnode;
702 set->tail->next = newnode;
707 /* Copy the set ORIG to the set DEST. */
710 set_copy (value_set_t dest, value_set_t orig)
712 value_set_node_t node;
714 if (!orig || !orig->head)
717 for (node = orig->head;
721 insert_into_set (dest, node->expr);
725 /* Remove EXPR from SET. */
728 set_remove (value_set_t set, tree expr)
730 value_set_node_t node, prev;
732 /* Remove the value of EXPR from the bitmap, decrement the set
733 length, and remove it from the actual double linked list. */
734 value_remove_from_set_bitmap (set, get_value_handle (expr));
737 for (node = set->head;
739 prev = node, node = node->next)
741 if (node->expr == expr)
744 set->head = node->next;
746 prev->next= node->next;
748 if (node == set->tail)
750 pool_free (value_set_node_pool, node);
756 /* Return true if SET contains the value VAL. */
759 set_contains_value (value_set_t set, tree val)
761 /* This is only referring to the flag above that we set on
762 values referring to numerical constants, because we know that we
763 are dealing with one of the value handles we created. */
764 if (TREE_CONSTANT (val))
767 if (set->length == 0)
770 return value_exists_in_set_bitmap (set, val);
773 /* Replace the leader for the value LOOKFOR in SET with EXPR. */
776 set_replace_value (value_set_t set, tree lookfor, tree expr)
778 value_set_node_t node = set->head;
780 /* The lookup is probably more expensive than walking the linked
781 list when we have only a small number of nodes. */
782 if (!set_contains_value (set, lookfor))
785 for (node = set->head;
789 if (get_value_handle (node->expr) == lookfor)
797 /* Return true if the set contains expression (not value) EXPR. */
800 set_contains (value_set_t set, tree expr)
802 value_set_node_t node;
804 for (node = set->head;
808 if (operand_equal_p (node->expr, expr, 0))
814 /* Subtract set B from set A, and return the new set. */
817 set_subtract (value_set_t a, value_set_t b, bool indexed)
819 value_set_t ret = set_new (indexed);
820 value_set_node_t node;
825 if (!set_contains (b, node->expr))
826 insert_into_set (ret, node->expr);
831 /* Return true if two sets are equal. */
834 set_equal (value_set_t a, value_set_t b)
836 value_set_node_t node;
838 if (a->length != b->length)
844 if (!set_contains_value (b, get_value_handle (node->expr)))
850 /* Replace the value for EXPR in SET with EXPR. */
852 value_replace_in_set (value_set_t set, tree expr)
854 tree val = get_value_handle (expr);
856 if (set->length == 0)
859 set_replace_value (set, val, expr);
862 /* Insert the value for EXPR into SET, if it doesn't exist already. */
865 value_insert_into_set (value_set_t set, tree expr)
867 tree val = get_value_handle (expr);
869 /* Constant values exist everywhere. */
870 if (TREE_CONSTANT (val))
873 if (!set_contains_value (set, val))
874 insert_into_set (set, expr);
878 /* Print out the value_set SET to OUTFILE. */
881 print_value_set (FILE *outfile, value_set_t set,
882 const char *setname, int blockindex)
884 value_set_node_t node;
885 fprintf (outfile, "%s[%d] := { ", setname, blockindex);
888 for (node = set->head;
892 print_generic_expr (outfile, node->expr, 0);
894 fprintf (outfile, " (");
895 print_generic_expr (outfile, get_value_handle (node->expr), 0);
896 fprintf (outfile, ") ");
899 fprintf (outfile, ", ");
903 fprintf (outfile, " }\n");
906 /* Print out the expressions that have VAL to OUTFILE. */
908 print_value_expressions (FILE *outfile, tree val)
910 var_ann_t va = var_ann (val);
911 if (va && va->expr_set)
912 print_value_set (outfile, va->expr_set,
913 IDENTIFIER_POINTER (DECL_NAME (val)), 0);
918 debug_value_expressions (tree val)
920 print_value_expressions (stderr, val);
924 void debug_value_set (value_set_t, const char *, int);
927 debug_value_set (value_set_t set, const char *setname, int blockindex)
929 print_value_set (stderr, set, setname, blockindex);
932 /* Translate EXPR using phis in PHIBLOCK, so that it has the values of
933 the phis in PRED. Return NULL if we can't find a leader for each
934 part of the translated expression. */
937 phi_translate (tree expr, value_set_t set, basic_block pred,
938 basic_block phiblock)
940 tree phitrans = NULL;
946 /* Phi translations of a given expression don't change, */
947 phitrans = phi_trans_lookup (expr, pred);
952 switch (TREE_CODE_CLASS (TREE_CODE (expr)))
956 tree oldop1 = TREE_OPERAND (expr, 0);
957 tree oldop2 = TREE_OPERAND (expr, 1);
962 newop1 = phi_translate (find_leader (set, oldop1),
963 set, pred, phiblock);
966 newop2 = phi_translate (find_leader (set, oldop2),
967 set, pred, phiblock);
970 if (newop1 != oldop1 || newop2 != oldop2)
972 newexpr = pool_alloc (binary_node_pool);
973 memcpy (newexpr, expr, tree_size (expr));
974 create_tree_ann (newexpr);
975 TREE_OPERAND (newexpr, 0) = newop1 == oldop1 ? oldop1 : get_value_handle (newop1);
976 TREE_OPERAND (newexpr, 1) = newop2 == oldop2 ? oldop2 : get_value_handle (newop2);
977 lookup_or_add (value_table, newexpr);
979 phi_trans_add (oldexpr, newexpr, pred);
985 tree oldop1 = TREE_OPERAND (expr, 0);
989 newop1 = phi_translate (find_leader (set, oldop1),
990 set, pred, phiblock);
993 if (newop1 != oldop1)
995 newexpr = pool_alloc (unary_node_pool);
996 memcpy (newexpr, expr, tree_size (expr));
997 create_tree_ann (newexpr);
998 TREE_OPERAND (newexpr, 0) = get_value_handle (newop1);
999 lookup_or_add (value_table, newexpr);
1001 phi_trans_add (oldexpr, newexpr, pred);
1011 if (TREE_CODE (expr) != SSA_NAME)
1013 if (TREE_CODE (SSA_NAME_DEF_STMT (expr)) == PHI_NODE)
1014 phi = SSA_NAME_DEF_STMT (expr);
1018 for (i = 0; i < PHI_NUM_ARGS (phi); i++)
1019 if (PHI_ARG_EDGE (phi, i)->src == pred)
1022 if (is_undefined_value (PHI_ARG_DEF (phi, i)))
1024 val = lookup_or_add (value_table, PHI_ARG_DEF (phi, i));
1025 return PHI_ARG_DEF (phi, i);
1034 phi_translate_set (value_set_t dest, value_set_t set, basic_block pred,
1035 basic_block phiblock)
1037 value_set_node_t node;
1038 for (node = set->head;
1043 translated = phi_translate (node->expr, set, pred, phiblock);
1044 phi_trans_add (node->expr, translated, pred);
1046 if (translated != NULL)
1047 value_insert_into_set (dest, translated);
1051 /* Find the leader for a value (IE the name representing that
1052 value) in a given set, and return it. Return NULL if no leader is
1056 find_leader (value_set_t set, tree val)
1058 value_set_node_t node;
1063 if (TREE_CONSTANT (val))
1064 return TREE_CHAIN (val);
1066 if (set->length == 0)
1069 if (value_exists_in_set_bitmap (set, val))
1071 for (node = set->head;
1075 if (get_value_handle (node->expr) == val)
1082 /* Determine if the expression EXPR is valid in SET. This means that
1083 we have a leader for each part of the expression (if it consists of
1084 values), or the expression is an SSA_NAME.
1086 NB: We never should run into a case where we have SSA_NAME +
1087 SSA_NAME or SSA_NAME + value. The sets valid_in_set is called on,
1088 the ANTIC sets, will only ever have SSA_NAME's or binary value
1089 expression (IE VALUE1 + VALUE2) */
1092 valid_in_set (value_set_t set, tree expr)
1094 switch (TREE_CODE_CLASS (TREE_CODE (expr)))
1098 tree op1 = TREE_OPERAND (expr, 0);
1099 tree op2 = TREE_OPERAND (expr, 1);
1100 return set_contains_value (set, op1) && set_contains_value (set, op2);
1105 tree op1 = TREE_OPERAND (expr, 0);
1106 return set_contains_value (set, op1);
1111 if (TREE_CODE (expr) == SSA_NAME)
1121 /* Clean the set of expressions that are no longer valid in SET. This
1122 means expressions that are made up of values we have no leaders for
1126 clean (value_set_t set)
1128 value_set_node_t node;
1129 value_set_node_t next;
1134 if (!valid_in_set (set, node->expr))
1135 set_remove (set, node->expr);
1140 /* Compute the ANTIC set for BLOCK.
1142 ANTIC_OUT[BLOCK] = intersection of ANTIC_IN[b] for all succ(BLOCK), if
1144 ANTIC_OUT[BLOCK] = phi_translate (ANTIC_IN[succ(BLOCK)]) if
1147 ANTIC_IN[BLOCK] = clean(ANTIC_OUT[BLOCK] U EXP_GEN[BLOCK] -
1150 Iterate until fixpointed.
1152 XXX: It would be nice to either write a set_clear, and use it for
1153 antic_out, or to mark the antic_out set as deleted at the end
1154 of this routine, so that the pool can hand the same memory back out
1155 again for the next antic_out. */
1159 compute_antic_aux (basic_block block)
1163 bool changed = false;
1164 value_set_t S, old, ANTIC_OUT;
1165 value_set_node_t node;
1167 ANTIC_OUT = S = NULL;
1168 /* If any edges from predecessors are abnormal, antic_in is empty, so
1169 punt. Remember that the block has an incoming abnormal edge by
1170 setting the BB_VISITED flag. */
1171 if (! (block->flags & BB_VISITED))
1173 for (e = block->pred; e; e = e->pred_next)
1174 if (e->flags & EDGE_ABNORMAL)
1176 block->flags |= BB_VISITED;
1180 if (block->flags & BB_VISITED)
1187 old = set_new (false);
1188 set_copy (old, ANTIC_IN (block));
1189 ANTIC_OUT = set_new (true);
1191 /* If the block has no successors, ANTIC_OUT is empty, because it is
1193 if (block->succ == NULL);
1195 /* If we have one successor, we could have some phi nodes to
1196 translate through. */
1197 else if (block->succ->succ_next == NULL)
1199 phi_translate_set (ANTIC_OUT, ANTIC_IN(block->succ->dest),
1200 block, block->succ->dest);
1202 /* If we have multiple successors, we take the intersection of all of
1206 varray_type worklist;
1209 basic_block bprime, first;
1211 VARRAY_BB_INIT (worklist, 1, "succ");
1215 VARRAY_PUSH_BB (worklist, e->dest);
1218 first = VARRAY_BB (worklist, 0);
1219 set_copy (ANTIC_OUT, ANTIC_IN (first));
1221 for (i = 1; i < VARRAY_ACTIVE_SIZE (worklist); i++)
1223 bprime = VARRAY_BB (worklist, i);
1224 node = ANTIC_OUT->head;
1228 value_set_node_t next = node->next;
1229 val = get_value_handle (node->expr);
1230 if (!set_contains_value (ANTIC_IN (bprime), val))
1231 set_remove (ANTIC_OUT, node->expr);
1235 VARRAY_CLEAR (worklist);
1238 /* Generate ANTIC_OUT - TMP_GEN */
1239 S = set_subtract (ANTIC_OUT, TMP_GEN (block), false);
1241 /* Start ANTIC_IN with EXP_GEN - TMP_GEN */
1242 ANTIC_IN (block) = set_subtract (EXP_GEN (block),TMP_GEN (block), true);
1244 /* Then union in the ANTIC_OUT - TMP_GEN values, to get ANTIC_OUT U
1245 EXP_GEN - TMP_GEN */
1246 for (node = S->head;
1250 value_insert_into_set (ANTIC_IN (block), node->expr);
1252 clean (ANTIC_IN (block));
1255 if (!set_equal (old, ANTIC_IN (block)))
1259 if (dump_file && (dump_flags & TDF_DETAILS))
1262 print_value_set (dump_file, ANTIC_OUT, "ANTIC_OUT", block->index);
1263 print_value_set (dump_file, ANTIC_IN (block), "ANTIC_IN", block->index);
1265 print_value_set (dump_file, S, "S", block->index);
1269 for (son = first_dom_son (CDI_POST_DOMINATORS, block);
1271 son = next_dom_son (CDI_POST_DOMINATORS, son))
1273 changed |= compute_antic_aux (son);
1278 /* Compute ANTIC sets. */
1281 compute_antic (void)
1283 bool changed = true;
1285 int num_iterations = 0;
1288 ANTIC_IN (bb) = set_new (true);
1289 bb->flags &= ~BB_VISITED;
1296 changed = compute_antic_aux (EXIT_BLOCK_PTR);
1298 if (num_iterations > 2 && dump_file && (dump_flags & TDF_STATS))
1299 fprintf (dump_file, "compute_antic required %d iterations\n", num_iterations);
1302 /* Perform insertion of partially redundant values.
1303 For BLOCK, do the following:
1304 1. Propagate the NEW_SETS of the dominator into the current block.
1305 If the block has multiple predecessors,
1306 2a. Iterate over the ANTIC expressions for the block to see if
1307 any of them are partially redundant.
1308 2b. If so, insert them into the necessary predecessors to make
1309 the expression fully redundant.
1310 2c. Insert a new PHI merging the values of the predecessors.
1311 2d. Insert the new PHI, and the new expressions, into the
1313 3. Recursively call ourselves on the dominator children of BLOCK.
1317 insert_aux (basic_block block)
1320 bool new_stuff = false;
1326 dom = get_immediate_dominator (CDI_DOMINATORS, block);
1329 e = NEW_SETS (dom)->head;
1332 insert_into_set (NEW_SETS (block), e->expr);
1333 value_replace_in_set (AVAIL_OUT (block), e->expr);
1336 if (block->pred->pred_next)
1338 value_set_node_t node;
1339 for (node = ANTIC_IN (block)->head;
1343 if (TREE_CODE_CLASS (TREE_CODE (node->expr)) == '2'
1344 || TREE_CODE_CLASS (TREE_CODE (node->expr)) == '1')
1348 bool by_some = false;
1349 bool cant_insert = false;
1350 bool all_same = true;
1351 tree first_s = NULL;
1356 val = get_value_handle (node->expr);
1357 if (set_contains_value (PHI_GEN (block), val))
1359 if (set_contains_value (AVAIL_OUT (dom), val))
1361 if (dump_file && (dump_flags & TDF_DETAILS))
1362 fprintf (dump_file, "Found fully redundant value\n");
1366 avail = xcalloc (last_basic_block, sizeof (tree));
1367 for (pred = block->pred;
1369 pred = pred->pred_next)
1374 eprime = phi_translate (node->expr,
1378 /* eprime will generally only be NULL if the
1379 value of the expression, translated
1380 through the PHI for this predecessor, is
1381 undefined. If that is the case, we can't
1382 make the expression fully redundant,
1383 because its value is undefined along a
1384 predecessor path. We can thus break out
1385 early because it doesn't matter what the
1386 rest of the results are. */
1393 vprime = get_value_handle (eprime);
1396 edoubleprime = find_leader (AVAIL_OUT (bprime),
1398 if (edoubleprime == NULL)
1400 avail[bprime->index] = eprime;
1405 avail[bprime->index] = edoubleprime;
1407 if (first_s == NULL)
1408 first_s = edoubleprime;
1409 else if (first_s != edoubleprime)
1411 if (first_s != edoubleprime
1412 && operand_equal_p (first_s, edoubleprime, 0))
1416 /* If we can insert it, it's not the same value
1417 already existing along every predecessor, and
1418 it's defined by some predecessor, it is
1419 partially redundant. */
1420 if (!cant_insert && !all_same && by_some)
1422 tree type = TREE_TYPE (avail[block->pred->src->index]);
1426 if (dump_file && (dump_flags & TDF_DETAILS))
1428 fprintf (dump_file, "Found partial redundancy for expression ");
1429 print_generic_expr (dump_file, node->expr, 0);
1430 fprintf (dump_file, "\n");
1433 /* Make the necessary insertions. */
1434 for (pred = block->pred;
1436 pred = pred->pred_next)
1439 eprime = avail[bprime->index];
1440 if (TREE_CODE_CLASS (TREE_CODE (eprime)) == '2')
1444 s1 = find_leader (AVAIL_OUT (bprime),
1445 TREE_OPERAND (eprime, 0));
1446 /* Depending on the order we process
1447 DOM branches in, the value may
1448 not have propagated to all the
1449 dom children yet during this
1450 iteration. In this case, the
1451 value will always be in the
1452 NEW_SETS for *our* dominator */
1454 s1 = find_leader (NEW_SETS (dom),
1455 TREE_OPERAND (eprime, 0));
1459 s2 = find_leader (AVAIL_OUT (bprime),
1460 TREE_OPERAND (eprime, 1));
1462 s2 = find_leader (NEW_SETS (dom),
1463 TREE_OPERAND (eprime, 1));
1467 temp = create_tmp_var (TREE_TYPE (eprime),
1469 add_referenced_tmp_var (temp);
1470 newexpr = build (TREE_CODE (eprime),
1473 newexpr = build (MODIFY_EXPR,
1476 temp = make_ssa_name (temp, newexpr);
1477 TREE_OPERAND (newexpr, 0) = temp;
1478 bsi_insert_on_edge (pred, newexpr);
1479 bsi_commit_edge_inserts (NULL);
1481 if (dump_file && (dump_flags & TDF_DETAILS))
1483 fprintf (dump_file, "Inserted ");
1484 print_generic_expr (dump_file, newexpr, 0);
1485 fprintf (dump_file, " in predecessor %d\n", pred->src->index);
1487 pre_stats.insertions++;
1488 v = lookup_or_add (value_table, eprime);
1489 add (value_table, temp, v);
1490 insert_into_set (NEW_SETS (bprime), temp);
1491 value_insert_into_set (AVAIL_OUT (bprime),
1493 avail[bprime->index] = temp;
1495 else if (TREE_CODE_CLASS (TREE_CODE (eprime)) == '1')
1499 s1 = find_leader (AVAIL_OUT (bprime),
1500 TREE_OPERAND (eprime, 0));
1501 /* Depending on the order we process
1502 DOM branches in, the value may not have
1503 propagated to all the dom
1504 children yet in the current
1505 iteration, but it will be in
1506 NEW_SETS if it is not yet
1510 s1 = find_leader (NEW_SETS (dom),
1511 TREE_OPERAND (eprime, 0));
1515 temp = create_tmp_var (TREE_TYPE (eprime),
1517 add_referenced_tmp_var (temp);
1518 newexpr = build (TREE_CODE (eprime),
1521 newexpr = build (MODIFY_EXPR,
1524 temp = make_ssa_name (temp, newexpr);
1525 TREE_OPERAND (newexpr, 0) = temp;
1526 bsi_insert_on_edge (pred, newexpr);
1527 bsi_commit_edge_inserts (NULL);
1529 if (dump_file && (dump_flags & TDF_DETAILS))
1531 fprintf (dump_file, "Inserted ");
1532 print_generic_expr (dump_file, newexpr, 0);
1533 fprintf (dump_file, " in predecessor %d\n", pred->src->index);
1535 pre_stats.insertions++;
1536 v = lookup_or_add (value_table, eprime);
1537 add (value_table, temp, v);
1538 insert_into_set (NEW_SETS (bprime), temp);
1539 value_insert_into_set (AVAIL_OUT (bprime),
1541 avail[bprime->index] = temp;
1544 /* Now build a phi for the new variable. */
1545 temp = create_tmp_var (type, "prephitmp");
1546 add_referenced_tmp_var (temp);
1547 temp = create_phi_node (temp, block);
1548 add (value_table, PHI_RESULT (temp), val);
1551 if (!set_contains_value (AVAIL_OUT (block), val))
1552 insert_into_set (AVAIL_OUT (block),
1556 value_replace_in_set (AVAIL_OUT (block),
1558 for (pred = block->pred;
1560 pred = pred->pred_next)
1562 add_phi_arg (&temp, avail[pred->src->index],
1565 if (dump_file && (dump_flags & TDF_DETAILS))
1567 fprintf (dump_file, "Created phi ");
1568 print_generic_expr (dump_file, temp, 0);
1569 fprintf (dump_file, " in block %d\n", block->index);
1573 insert_into_set (NEW_SETS (block),
1575 insert_into_set (PHI_GEN (block),
1585 for (son = first_dom_son (CDI_DOMINATORS, block);
1587 son = next_dom_son (CDI_DOMINATORS, son))
1589 new_stuff |= insert_aux (son);
1595 /* Perform insertion of partially redundant values. */
1600 bool new_stuff = true;
1602 int num_iterations = 0;
1605 NEW_SETS (bb) = set_new (true);
1611 new_stuff = insert_aux (ENTRY_BLOCK_PTR);
1613 if (num_iterations > 2 && dump_file && (dump_flags & TDF_STATS))
1614 fprintf (dump_file, "insert required %d iterations\n", num_iterations);
1617 /* Return true if EXPR has no defining statement in this procedure,
1618 *AND* isn't a live-on-entry parameter. */
1620 is_undefined_value (tree expr)
1623 #ifdef ENABLE_CHECKING
1624 /* We should never be handed DECL's */
1628 if (TREE_CODE (expr) == SSA_NAME)
1630 /* XXX: Is this the correct test? */
1631 if (TREE_CODE (SSA_NAME_VAR (expr)) == PARM_DECL)
1633 if (IS_EMPTY_STMT (SSA_NAME_DEF_STMT (expr)))
1639 /* Compute the AVAIL set for BLOCK.
1640 This function performs value numbering of the statements in BLOCK.
1641 The AVAIL sets are built from information we glean while doing this
1642 value numbering, since the AVAIL sets contain only entry per
1646 AVAIL_IN[BLOCK] = AVAIL_OUT[dom(BLOCK)].
1647 AVAIL_OUT[BLOCK] = AVAIL_IN[BLOCK] U PHI_GEN[BLOCK] U
1652 compute_avail (basic_block block)
1656 /* For arguments with default definitions, we pretend they are
1657 defined in the entry block. */
1658 if (block == ENTRY_BLOCK_PTR)
1661 for (param = DECL_ARGUMENTS (current_function_decl);
1663 param = TREE_CHAIN (param))
1665 if (default_def (param) != NULL)
1668 tree def = default_def (param);
1669 val = lookup_or_add (value_table, def);
1670 insert_into_set (TMP_GEN (block), def);
1671 value_insert_into_set (AVAIL_OUT (block), def);
1677 block_stmt_iterator bsi;
1681 dom = get_immediate_dominator (CDI_DOMINATORS, block);
1683 set_copy (AVAIL_OUT (block), AVAIL_OUT (dom));
1684 for (phi = phi_nodes (block); phi; phi = PHI_CHAIN (phi))
1686 /* Ignore virtual PHIs until we can do PRE on expressions
1687 with virtual operands. */
1688 if (!is_gimple_reg (SSA_NAME_VAR (PHI_RESULT (phi))))
1691 lookup_or_add (value_table, PHI_RESULT (phi));
1692 value_insert_into_set (AVAIL_OUT (block), PHI_RESULT (phi));
1693 insert_into_set (PHI_GEN (block), PHI_RESULT (phi));
1696 for (bsi = bsi_start (block); !bsi_end_p (bsi); bsi_next (&bsi))
1699 stmt = bsi_stmt (bsi);
1700 get_stmt_operands (stmt);
1702 if (NUM_VUSES (STMT_VUSE_OPS (stmt))
1703 || NUM_V_MUST_DEFS (STMT_V_MUST_DEF_OPS (stmt))
1704 || NUM_V_MAY_DEFS (STMT_V_MAY_DEF_OPS (stmt))
1705 || stmt_ann (stmt)->has_volatile_ops)
1708 for (j = 0; j < NUM_DEFS (STMT_DEF_OPS (stmt)); j++)
1710 tree def = DEF_OP (STMT_DEF_OPS (stmt), j);
1711 lookup_or_add (value_table, def);
1712 insert_into_set (TMP_GEN (block), def);
1713 value_insert_into_set (AVAIL_OUT (block), def);
1715 for (j = 0; j < NUM_USES (STMT_USE_OPS (stmt)); j++)
1717 tree use = USE_OP (STMT_USE_OPS (stmt), j);
1718 if (TREE_CODE (use) == SSA_NAME)
1720 lookup_or_add (value_table, use);
1721 insert_into_set (TMP_GEN (block), use);
1722 value_insert_into_set (AVAIL_OUT (block), use);
1727 else if (TREE_CODE (stmt) == RETURN_EXPR
1728 && TREE_OPERAND (stmt, 0)
1729 && TREE_CODE (TREE_OPERAND (stmt, 0)) == MODIFY_EXPR)
1730 stmt = TREE_OPERAND (stmt, 0);
1732 if (TREE_CODE (stmt) == MODIFY_EXPR)
1734 op0 = TREE_OPERAND (stmt, 0);
1735 if (TREE_CODE (op0) != SSA_NAME)
1737 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op0))
1739 op1 = TREE_OPERAND (stmt, 1);
1740 STRIP_USELESS_TYPE_CONVERSION (op1);
1741 if (TREE_CODE_CLASS (TREE_CODE (op1)) == 'c')
1743 add (value_table, op0, lookup_or_add (value_table, op1));
1744 insert_into_set (TMP_GEN (block), op0);
1745 value_insert_into_set (AVAIL_OUT (block), op0);
1747 else if (TREE_CODE_CLASS (TREE_CODE (op1)) == '2')
1750 tree val, val1, val2;
1752 bop1 = TREE_OPERAND (op1, 0);
1753 bop2 = TREE_OPERAND (op1, 1);
1754 val1 = lookup_or_add (value_table, bop1);
1755 val2 = lookup_or_add (value_table, bop2);
1757 newt = pool_alloc (binary_node_pool);
1758 memcpy (newt, op1, tree_size (op1));
1759 TREE_OPERAND (newt, 0) = val1;
1760 TREE_OPERAND (newt, 1) = val2;
1761 val = lookup_or_add (value_table, newt);
1762 add (value_table, op0, val);
1763 if (!is_undefined_value (bop1))
1764 value_insert_into_set (EXP_GEN (block), bop1);
1765 if (!is_undefined_value (bop2))
1766 value_insert_into_set (EXP_GEN (block), bop2);
1767 value_insert_into_set (EXP_GEN (block), newt);
1768 insert_into_set (TMP_GEN (block), op0);
1769 value_insert_into_set (AVAIL_OUT (block), op0);
1771 else if (TREE_CODE_CLASS (TREE_CODE (op1)) == '1'
1772 && !is_gimple_cast (op1))
1777 uop = TREE_OPERAND (op1, 0);
1778 val1 = lookup_or_add (value_table, uop);
1779 newt = pool_alloc (unary_node_pool);
1780 memcpy (newt, op1, tree_size (op1));
1781 TREE_OPERAND (newt, 0) = val1;
1782 val = lookup_or_add (value_table, newt);
1783 add (value_table, op0, val);
1784 if (!is_undefined_value (uop))
1785 value_insert_into_set (EXP_GEN (block), uop);
1786 value_insert_into_set (EXP_GEN (block), newt);
1787 insert_into_set (TMP_GEN (block), op0);
1788 value_insert_into_set (AVAIL_OUT (block), op0);
1790 else if (TREE_CODE (op1) == SSA_NAME)
1792 tree val = lookup_or_add (value_table, op1);
1793 add (value_table, op0, val);
1794 if (!is_undefined_value (op1))
1795 value_insert_into_set (EXP_GEN (block), op1);
1796 insert_into_set (TMP_GEN (block), op0);
1797 value_insert_into_set (AVAIL_OUT (block), op0);
1802 for (j = 0; j < NUM_DEFS (STMT_DEF_OPS (stmt)); j++)
1804 tree def = DEF_OP (STMT_DEF_OPS (stmt), j);
1805 lookup_or_add (value_table, def);
1806 insert_into_set (TMP_GEN (block), def);
1807 value_insert_into_set (AVAIL_OUT (block), def);
1811 for (j = 0; j < NUM_USES (STMT_USE_OPS (stmt)); j++)
1813 tree use = USE_OP (STMT_USE_OPS (stmt), j);
1814 if (TREE_CODE (use) == SSA_NAME)
1816 lookup_or_add (value_table, use);
1817 insert_into_set (TMP_GEN (block), use);
1818 value_insert_into_set (AVAIL_OUT (block), use);
1826 for (j = 0; j < NUM_DEFS (STMT_DEF_OPS (stmt)); j++)
1828 tree def = DEF_OP (STMT_DEF_OPS (stmt), j);
1829 lookup_or_add (value_table, def);
1830 insert_into_set (TMP_GEN (block), def);
1831 value_insert_into_set (AVAIL_OUT (block), def);
1833 for (j = 0; j < NUM_USES (STMT_USE_OPS (stmt)); j++)
1835 tree use = USE_OP (STMT_USE_OPS (stmt), j);
1836 if (TREE_CODE (use) == SSA_NAME)
1838 lookup_or_add (value_table, use);
1839 insert_into_set (TMP_GEN (block), use);
1840 value_insert_into_set (AVAIL_OUT (block), use);
1846 for (son = first_dom_son (CDI_DOMINATORS, block);
1848 son = next_dom_son (CDI_DOMINATORS, son))
1849 compute_avail (son);
1853 /* Eliminate fully redundant computations. */
1862 block_stmt_iterator i;
1864 for (i = bsi_start (b); !bsi_end_p (i); bsi_next (&i))
1866 tree stmt = bsi_stmt (i);
1868 if (NUM_VUSES (STMT_VUSE_OPS (stmt))
1869 || NUM_V_MUST_DEFS (STMT_V_MUST_DEF_OPS (stmt))
1870 || NUM_V_MAY_DEFS (STMT_V_MAY_DEF_OPS (stmt))
1871 || stmt_ann (stmt)->has_volatile_ops)
1873 /* Lookup the RHS of the expression, see if we have an
1874 available computation for it. If so, replace the RHS with
1875 the available computation. */
1876 if (TREE_CODE (stmt) == MODIFY_EXPR)
1878 tree t = TREE_OPERAND (stmt, 0);
1879 tree expr = TREE_OPERAND (stmt, 1);
1881 /* There is no point in eliminating NOP_EXPR, it isn't
1882 supposed to generate any code. */
1883 if (TREE_CODE (expr) == NOP_EXPR
1884 || (TREE_CODE_CLASS (TREE_CODE (expr)) != '2'
1885 && TREE_CODE_CLASS (TREE_CODE (expr)) != '1'))
1887 sprime = find_leader (AVAIL_OUT (b),
1888 lookup (value_table, t));
1891 && may_propagate_copy (sprime, TREE_OPERAND (stmt, 1)))
1893 if (dump_file && (dump_flags & TDF_DETAILS))
1895 fprintf (dump_file, "Replaced ");
1896 print_generic_expr (dump_file, expr, 0);
1897 fprintf (dump_file, " with ");
1898 print_generic_expr (dump_file, sprime, 0);
1899 fprintf (dump_file, " in ");
1900 print_generic_stmt (dump_file, stmt, 0);
1902 pre_stats.eliminations++;
1903 propagate_tree_value (&TREE_OPERAND (stmt, 1), sprime);
1912 /* Main entry point to the SSA-PRE pass.
1914 PHASE indicates which dump file from the DUMP_FILES array to use when
1915 dumping debugging information. */
1922 pre_uid = num_referenced_vars;
1923 memset (&pre_stats, 0, sizeof (pre_stats));
1926 bb->aux = xcalloc (1, sizeof (struct bb_value_sets));
1928 phi_translate_table = htab_create (511, expr_pred_trans_hash,
1931 value_table = htab_create (511, val_expr_pair_hash,
1932 val_expr_pair_expr_eq, free);
1933 value_set_pool = create_alloc_pool ("Value sets",
1934 sizeof (struct value_set), 30);
1935 value_set_node_pool = create_alloc_pool ("Value set nodes",
1936 sizeof (struct value_set_node), 30);
1937 calculate_dominance_info (CDI_POST_DOMINATORS);
1938 calculate_dominance_info (CDI_DOMINATORS);
1939 tsize = tree_size (build (PLUS_EXPR, void_type_node, NULL_TREE,
1941 binary_node_pool = create_alloc_pool ("Binary tree nodes", tsize, 30);
1942 tsize = tree_size (build1 (NEGATE_EXPR, void_type_node, NULL_TREE));
1943 unary_node_pool = create_alloc_pool ("Unary tree nodes", tsize, 30);
1947 EXP_GEN (bb) = set_new (true);
1948 PHI_GEN (bb) = set_new (true);
1949 TMP_GEN (bb) = set_new (false);
1950 AVAIL_OUT (bb) = set_new (true);
1953 compute_avail (ENTRY_BLOCK_PTR);
1955 if (dump_file && (dump_flags & TDF_DETAILS))
1959 print_value_set (dump_file, EXP_GEN (bb), "exp_gen", bb->index);
1960 print_value_set (dump_file, TMP_GEN (bb), "tmp_gen", bb->index);
1961 print_value_set (dump_file, AVAIL_OUT (bb), "avail_out", bb->index);
1965 /* Insert can get quite slow on an incredibly large number of basic
1966 blocks due to some quadratic behavior. Until this behavior is
1967 fixed, don't run it when he have an incredibly large number of
1968 bb's. If we aren't going to run insert, there is no point in
1969 computing ANTIC, either, even though it's plenty fast. */
1971 if (n_basic_blocks < 4000)
1979 if (dump_file && (dump_flags & TDF_STATS))
1981 fprintf (dump_file, "Insertions:%d\n", pre_stats.insertions);
1982 fprintf (dump_file, "New PHIs:%d\n", pre_stats.phis);
1983 fprintf (dump_file, "Eliminated:%d\n", pre_stats.eliminations);
1986 free_alloc_pool (value_set_pool);
1987 free_alloc_pool (value_set_node_pool);
1988 free_alloc_pool (binary_node_pool);
1989 free_alloc_pool (unary_node_pool);
1990 htab_delete (value_table);
1991 htab_delete (phi_translate_table);
1998 free_dominance_info (CDI_POST_DOMINATORS);
2004 return flag_tree_pre != 0;
2007 struct tree_opt_pass pass_pre =
2010 gate_pre, /* gate */
2011 execute_pre, /* execute */
2014 0, /* static_pass_number */
2015 TV_TREE_PRE, /* tv_id */
2016 PROP_no_crit_edges | PROP_cfg | PROP_ssa,/* properties_required */
2017 0, /* properties_provided */
2018 0, /* properties_destroyed */
2019 0, /* todo_flags_start */
2020 TODO_dump_func | TODO_ggc_collect | TODO_verify_ssa /* todo_flags_finish */