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 if (bb->flags & BB_VISITED)
1297 changed = compute_antic_aux (EXIT_BLOCK_PTR);
1301 bb->flags &= ~BB_VISITED;
1303 if (num_iterations > 2 && dump_file && (dump_flags & TDF_STATS))
1304 fprintf (dump_file, "compute_antic required %d iterations\n", num_iterations);
1307 /* Perform insertion of partially redundant values.
1308 For BLOCK, do the following:
1309 1. Propagate the NEW_SETS of the dominator into the current block.
1310 If the block has multiple predecessors,
1311 2a. Iterate over the ANTIC expressions for the block to see if
1312 any of them are partially redundant.
1313 2b. If so, insert them into the necessary predecessors to make
1314 the expression fully redundant.
1315 2c. Insert a new PHI merging the values of the predecessors.
1316 2d. Insert the new PHI, and the new expressions, into the
1318 3. Recursively call ourselves on the dominator children of BLOCK.
1322 insert_aux (basic_block block)
1325 bool new_stuff = false;
1331 dom = get_immediate_dominator (CDI_DOMINATORS, block);
1334 e = NEW_SETS (dom)->head;
1337 insert_into_set (NEW_SETS (block), e->expr);
1338 value_replace_in_set (AVAIL_OUT (block), e->expr);
1341 if (block->pred->pred_next)
1343 value_set_node_t node;
1344 for (node = ANTIC_IN (block)->head;
1348 if (TREE_CODE_CLASS (TREE_CODE (node->expr)) == '2'
1349 || TREE_CODE_CLASS (TREE_CODE (node->expr)) == '1')
1353 bool by_some = false;
1354 bool cant_insert = false;
1355 bool all_same = true;
1356 tree first_s = NULL;
1361 val = get_value_handle (node->expr);
1362 if (set_contains_value (PHI_GEN (block), val))
1364 if (set_contains_value (AVAIL_OUT (dom), val))
1366 if (dump_file && (dump_flags & TDF_DETAILS))
1367 fprintf (dump_file, "Found fully redundant value\n");
1371 avail = xcalloc (last_basic_block, sizeof (tree));
1372 for (pred = block->pred;
1374 pred = pred->pred_next)
1379 eprime = phi_translate (node->expr,
1383 /* eprime will generally only be NULL if the
1384 value of the expression, translated
1385 through the PHI for this predecessor, is
1386 undefined. If that is the case, we can't
1387 make the expression fully redundant,
1388 because its value is undefined along a
1389 predecessor path. We can thus break out
1390 early because it doesn't matter what the
1391 rest of the results are. */
1398 vprime = get_value_handle (eprime);
1401 edoubleprime = find_leader (AVAIL_OUT (bprime),
1403 if (edoubleprime == NULL)
1405 avail[bprime->index] = eprime;
1410 avail[bprime->index] = edoubleprime;
1412 if (first_s == NULL)
1413 first_s = edoubleprime;
1414 else if (first_s != edoubleprime)
1416 if (first_s != edoubleprime
1417 && operand_equal_p (first_s, edoubleprime, 0))
1421 /* If we can insert it, it's not the same value
1422 already existing along every predecessor, and
1423 it's defined by some predecessor, it is
1424 partially redundant. */
1425 if (!cant_insert && !all_same && by_some)
1427 tree type = TREE_TYPE (avail[block->pred->src->index]);
1431 if (dump_file && (dump_flags & TDF_DETAILS))
1433 fprintf (dump_file, "Found partial redundancy for expression ");
1434 print_generic_expr (dump_file, node->expr, 0);
1435 fprintf (dump_file, "\n");
1438 /* Make the necessary insertions. */
1439 for (pred = block->pred;
1441 pred = pred->pred_next)
1444 eprime = avail[bprime->index];
1445 if (TREE_CODE_CLASS (TREE_CODE (eprime)) == '2')
1449 s1 = find_leader (AVAIL_OUT (bprime),
1450 TREE_OPERAND (eprime, 0));
1451 /* Depending on the order we process
1452 DOM branches in, the value may
1453 not have propagated to all the
1454 dom children yet during this
1455 iteration. In this case, the
1456 value will always be in the
1457 NEW_SETS for *our* dominator */
1459 s1 = find_leader (NEW_SETS (dom),
1460 TREE_OPERAND (eprime, 0));
1464 s2 = find_leader (AVAIL_OUT (bprime),
1465 TREE_OPERAND (eprime, 1));
1467 s2 = find_leader (NEW_SETS (dom),
1468 TREE_OPERAND (eprime, 1));
1472 temp = create_tmp_var (TREE_TYPE (eprime),
1474 add_referenced_tmp_var (temp);
1475 newexpr = build (TREE_CODE (eprime),
1478 newexpr = build (MODIFY_EXPR,
1481 temp = make_ssa_name (temp, newexpr);
1482 TREE_OPERAND (newexpr, 0) = temp;
1483 bsi_insert_on_edge (pred, newexpr);
1484 bsi_commit_edge_inserts (NULL);
1486 if (dump_file && (dump_flags & TDF_DETAILS))
1488 fprintf (dump_file, "Inserted ");
1489 print_generic_expr (dump_file, newexpr, 0);
1490 fprintf (dump_file, " in predecessor %d\n", pred->src->index);
1492 pre_stats.insertions++;
1493 v = lookup_or_add (value_table, eprime);
1494 add (value_table, temp, v);
1495 insert_into_set (NEW_SETS (bprime), temp);
1496 value_insert_into_set (AVAIL_OUT (bprime),
1498 avail[bprime->index] = temp;
1500 else if (TREE_CODE_CLASS (TREE_CODE (eprime)) == '1')
1504 s1 = find_leader (AVAIL_OUT (bprime),
1505 TREE_OPERAND (eprime, 0));
1506 /* Depending on the order we process
1507 DOM branches in, the value may not have
1508 propagated to all the dom
1509 children yet in the current
1510 iteration, but it will be in
1511 NEW_SETS if it is not yet
1515 s1 = find_leader (NEW_SETS (dom),
1516 TREE_OPERAND (eprime, 0));
1520 temp = create_tmp_var (TREE_TYPE (eprime),
1522 add_referenced_tmp_var (temp);
1523 newexpr = build (TREE_CODE (eprime),
1526 newexpr = build (MODIFY_EXPR,
1529 temp = make_ssa_name (temp, newexpr);
1530 TREE_OPERAND (newexpr, 0) = temp;
1531 bsi_insert_on_edge (pred, newexpr);
1532 bsi_commit_edge_inserts (NULL);
1534 if (dump_file && (dump_flags & TDF_DETAILS))
1536 fprintf (dump_file, "Inserted ");
1537 print_generic_expr (dump_file, newexpr, 0);
1538 fprintf (dump_file, " in predecessor %d\n", pred->src->index);
1540 pre_stats.insertions++;
1541 v = lookup_or_add (value_table, eprime);
1542 add (value_table, temp, v);
1543 insert_into_set (NEW_SETS (bprime), temp);
1544 value_insert_into_set (AVAIL_OUT (bprime),
1546 avail[bprime->index] = temp;
1549 /* Now build a phi for the new variable. */
1550 temp = create_tmp_var (type, "prephitmp");
1551 add_referenced_tmp_var (temp);
1552 temp = create_phi_node (temp, block);
1553 add (value_table, PHI_RESULT (temp), val);
1556 if (!set_contains_value (AVAIL_OUT (block), val))
1557 insert_into_set (AVAIL_OUT (block),
1561 value_replace_in_set (AVAIL_OUT (block),
1563 for (pred = block->pred;
1565 pred = pred->pred_next)
1567 add_phi_arg (&temp, avail[pred->src->index],
1570 if (dump_file && (dump_flags & TDF_DETAILS))
1572 fprintf (dump_file, "Created phi ");
1573 print_generic_expr (dump_file, temp, 0);
1574 fprintf (dump_file, " in block %d\n", block->index);
1578 insert_into_set (NEW_SETS (block),
1580 insert_into_set (PHI_GEN (block),
1590 for (son = first_dom_son (CDI_DOMINATORS, block);
1592 son = next_dom_son (CDI_DOMINATORS, son))
1594 new_stuff |= insert_aux (son);
1600 /* Perform insertion of partially redundant values. */
1605 bool new_stuff = true;
1607 int num_iterations = 0;
1610 NEW_SETS (bb) = set_new (true);
1616 new_stuff = insert_aux (ENTRY_BLOCK_PTR);
1618 if (num_iterations > 2 && dump_file && (dump_flags & TDF_STATS))
1619 fprintf (dump_file, "insert required %d iterations\n", num_iterations);
1622 /* Return true if EXPR has no defining statement in this procedure,
1623 *AND* isn't a live-on-entry parameter. */
1625 is_undefined_value (tree expr)
1628 #ifdef ENABLE_CHECKING
1629 /* We should never be handed DECL's */
1633 if (TREE_CODE (expr) == SSA_NAME)
1635 /* XXX: Is this the correct test? */
1636 if (TREE_CODE (SSA_NAME_VAR (expr)) == PARM_DECL)
1638 if (IS_EMPTY_STMT (SSA_NAME_DEF_STMT (expr)))
1644 /* Compute the AVAIL set for BLOCK.
1645 This function performs value numbering of the statements in BLOCK.
1646 The AVAIL sets are built from information we glean while doing this
1647 value numbering, since the AVAIL sets contain only entry per
1651 AVAIL_IN[BLOCK] = AVAIL_OUT[dom(BLOCK)].
1652 AVAIL_OUT[BLOCK] = AVAIL_IN[BLOCK] U PHI_GEN[BLOCK] U
1657 compute_avail (basic_block block)
1661 /* For arguments with default definitions, we pretend they are
1662 defined in the entry block. */
1663 if (block == ENTRY_BLOCK_PTR)
1666 for (param = DECL_ARGUMENTS (current_function_decl);
1668 param = TREE_CHAIN (param))
1670 if (default_def (param) != NULL)
1673 tree def = default_def (param);
1674 val = lookup_or_add (value_table, def);
1675 insert_into_set (TMP_GEN (block), def);
1676 value_insert_into_set (AVAIL_OUT (block), def);
1682 block_stmt_iterator bsi;
1686 dom = get_immediate_dominator (CDI_DOMINATORS, block);
1688 set_copy (AVAIL_OUT (block), AVAIL_OUT (dom));
1689 for (phi = phi_nodes (block); phi; phi = PHI_CHAIN (phi))
1691 /* Ignore virtual PHIs until we can do PRE on expressions
1692 with virtual operands. */
1693 if (!is_gimple_reg (SSA_NAME_VAR (PHI_RESULT (phi))))
1696 lookup_or_add (value_table, PHI_RESULT (phi));
1697 value_insert_into_set (AVAIL_OUT (block), PHI_RESULT (phi));
1698 insert_into_set (PHI_GEN (block), PHI_RESULT (phi));
1701 for (bsi = bsi_start (block); !bsi_end_p (bsi); bsi_next (&bsi))
1704 stmt = bsi_stmt (bsi);
1705 get_stmt_operands (stmt);
1707 if (NUM_VUSES (STMT_VUSE_OPS (stmt))
1708 || NUM_V_MUST_DEFS (STMT_V_MUST_DEF_OPS (stmt))
1709 || NUM_V_MAY_DEFS (STMT_V_MAY_DEF_OPS (stmt))
1710 || stmt_ann (stmt)->has_volatile_ops)
1713 for (j = 0; j < NUM_DEFS (STMT_DEF_OPS (stmt)); j++)
1715 tree def = DEF_OP (STMT_DEF_OPS (stmt), j);
1716 lookup_or_add (value_table, def);
1717 insert_into_set (TMP_GEN (block), def);
1718 value_insert_into_set (AVAIL_OUT (block), def);
1720 for (j = 0; j < NUM_USES (STMT_USE_OPS (stmt)); j++)
1722 tree use = USE_OP (STMT_USE_OPS (stmt), j);
1723 if (TREE_CODE (use) == SSA_NAME)
1725 lookup_or_add (value_table, use);
1726 insert_into_set (TMP_GEN (block), use);
1727 value_insert_into_set (AVAIL_OUT (block), use);
1732 else if (TREE_CODE (stmt) == RETURN_EXPR
1733 && TREE_OPERAND (stmt, 0)
1734 && TREE_CODE (TREE_OPERAND (stmt, 0)) == MODIFY_EXPR)
1735 stmt = TREE_OPERAND (stmt, 0);
1737 if (TREE_CODE (stmt) == MODIFY_EXPR)
1739 op0 = TREE_OPERAND (stmt, 0);
1740 if (TREE_CODE (op0) != SSA_NAME)
1742 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op0))
1744 op1 = TREE_OPERAND (stmt, 1);
1745 STRIP_USELESS_TYPE_CONVERSION (op1);
1746 if (TREE_CODE_CLASS (TREE_CODE (op1)) == 'c')
1748 add (value_table, op0, lookup_or_add (value_table, op1));
1749 insert_into_set (TMP_GEN (block), op0);
1750 value_insert_into_set (AVAIL_OUT (block), op0);
1752 else if (TREE_CODE_CLASS (TREE_CODE (op1)) == '2')
1755 tree val, val1, val2;
1757 bop1 = TREE_OPERAND (op1, 0);
1758 bop2 = TREE_OPERAND (op1, 1);
1759 val1 = lookup_or_add (value_table, bop1);
1760 val2 = lookup_or_add (value_table, bop2);
1762 newt = pool_alloc (binary_node_pool);
1763 memcpy (newt, op1, tree_size (op1));
1764 TREE_OPERAND (newt, 0) = val1;
1765 TREE_OPERAND (newt, 1) = val2;
1766 val = lookup_or_add (value_table, newt);
1767 add (value_table, op0, val);
1768 if (!is_undefined_value (bop1))
1769 value_insert_into_set (EXP_GEN (block), bop1);
1770 if (!is_undefined_value (bop2))
1771 value_insert_into_set (EXP_GEN (block), bop2);
1772 value_insert_into_set (EXP_GEN (block), newt);
1773 insert_into_set (TMP_GEN (block), op0);
1774 value_insert_into_set (AVAIL_OUT (block), op0);
1776 else if (TREE_CODE_CLASS (TREE_CODE (op1)) == '1'
1777 && !is_gimple_cast (op1))
1782 uop = TREE_OPERAND (op1, 0);
1783 val1 = lookup_or_add (value_table, uop);
1784 newt = pool_alloc (unary_node_pool);
1785 memcpy (newt, op1, tree_size (op1));
1786 TREE_OPERAND (newt, 0) = val1;
1787 val = lookup_or_add (value_table, newt);
1788 add (value_table, op0, val);
1789 if (!is_undefined_value (uop))
1790 value_insert_into_set (EXP_GEN (block), uop);
1791 value_insert_into_set (EXP_GEN (block), newt);
1792 insert_into_set (TMP_GEN (block), op0);
1793 value_insert_into_set (AVAIL_OUT (block), op0);
1795 else if (TREE_CODE (op1) == SSA_NAME)
1797 tree val = lookup_or_add (value_table, op1);
1798 add (value_table, op0, val);
1799 if (!is_undefined_value (op1))
1800 value_insert_into_set (EXP_GEN (block), op1);
1801 insert_into_set (TMP_GEN (block), op0);
1802 value_insert_into_set (AVAIL_OUT (block), op0);
1807 for (j = 0; j < NUM_DEFS (STMT_DEF_OPS (stmt)); j++)
1809 tree def = DEF_OP (STMT_DEF_OPS (stmt), j);
1810 lookup_or_add (value_table, def);
1811 insert_into_set (TMP_GEN (block), def);
1812 value_insert_into_set (AVAIL_OUT (block), def);
1816 for (j = 0; j < NUM_USES (STMT_USE_OPS (stmt)); j++)
1818 tree use = USE_OP (STMT_USE_OPS (stmt), j);
1819 if (TREE_CODE (use) == SSA_NAME)
1821 lookup_or_add (value_table, use);
1822 insert_into_set (TMP_GEN (block), use);
1823 value_insert_into_set (AVAIL_OUT (block), use);
1831 for (j = 0; j < NUM_DEFS (STMT_DEF_OPS (stmt)); j++)
1833 tree def = DEF_OP (STMT_DEF_OPS (stmt), j);
1834 lookup_or_add (value_table, def);
1835 insert_into_set (TMP_GEN (block), def);
1836 value_insert_into_set (AVAIL_OUT (block), def);
1838 for (j = 0; j < NUM_USES (STMT_USE_OPS (stmt)); j++)
1840 tree use = USE_OP (STMT_USE_OPS (stmt), j);
1841 if (TREE_CODE (use) == SSA_NAME)
1843 lookup_or_add (value_table, use);
1844 insert_into_set (TMP_GEN (block), use);
1845 value_insert_into_set (AVAIL_OUT (block), use);
1851 for (son = first_dom_son (CDI_DOMINATORS, block);
1853 son = next_dom_son (CDI_DOMINATORS, son))
1854 compute_avail (son);
1858 /* Eliminate fully redundant computations. */
1867 block_stmt_iterator i;
1869 for (i = bsi_start (b); !bsi_end_p (i); bsi_next (&i))
1871 tree stmt = bsi_stmt (i);
1873 if (NUM_VUSES (STMT_VUSE_OPS (stmt))
1874 || NUM_V_MUST_DEFS (STMT_V_MUST_DEF_OPS (stmt))
1875 || NUM_V_MAY_DEFS (STMT_V_MAY_DEF_OPS (stmt))
1876 || stmt_ann (stmt)->has_volatile_ops)
1878 /* Lookup the RHS of the expression, see if we have an
1879 available computation for it. If so, replace the RHS with
1880 the available computation. */
1881 if (TREE_CODE (stmt) == MODIFY_EXPR)
1883 tree t = TREE_OPERAND (stmt, 0);
1884 tree expr = TREE_OPERAND (stmt, 1);
1886 /* There is no point in eliminating NOP_EXPR, it isn't
1887 supposed to generate any code. */
1888 if (TREE_CODE (expr) == NOP_EXPR
1889 || (TREE_CODE_CLASS (TREE_CODE (expr)) != '2'
1890 && TREE_CODE_CLASS (TREE_CODE (expr)) != '1'))
1892 sprime = find_leader (AVAIL_OUT (b),
1893 lookup (value_table, t));
1896 && may_propagate_copy (sprime, TREE_OPERAND (stmt, 1)))
1898 if (dump_file && (dump_flags & TDF_DETAILS))
1900 fprintf (dump_file, "Replaced ");
1901 print_generic_expr (dump_file, expr, 0);
1902 fprintf (dump_file, " with ");
1903 print_generic_expr (dump_file, sprime, 0);
1904 fprintf (dump_file, " in ");
1905 print_generic_stmt (dump_file, stmt, 0);
1907 pre_stats.eliminations++;
1908 propagate_tree_value (&TREE_OPERAND (stmt, 1), sprime);
1917 /* Main entry point to the SSA-PRE pass.
1919 PHASE indicates which dump file from the DUMP_FILES array to use when
1920 dumping debugging information. */
1927 pre_uid = num_referenced_vars;
1928 memset (&pre_stats, 0, sizeof (pre_stats));
1931 bb->aux = xcalloc (1, sizeof (struct bb_value_sets));
1933 phi_translate_table = htab_create (511, expr_pred_trans_hash,
1936 value_table = htab_create (511, val_expr_pair_hash,
1937 val_expr_pair_expr_eq, free);
1938 value_set_pool = create_alloc_pool ("Value sets",
1939 sizeof (struct value_set), 30);
1940 value_set_node_pool = create_alloc_pool ("Value set nodes",
1941 sizeof (struct value_set_node), 30);
1942 calculate_dominance_info (CDI_POST_DOMINATORS);
1943 calculate_dominance_info (CDI_DOMINATORS);
1944 tsize = tree_size (build (PLUS_EXPR, void_type_node, NULL_TREE,
1946 binary_node_pool = create_alloc_pool ("Binary tree nodes", tsize, 30);
1947 tsize = tree_size (build1 (NEGATE_EXPR, void_type_node, NULL_TREE));
1948 unary_node_pool = create_alloc_pool ("Unary tree nodes", tsize, 30);
1952 EXP_GEN (bb) = set_new (true);
1953 PHI_GEN (bb) = set_new (true);
1954 TMP_GEN (bb) = set_new (false);
1955 AVAIL_OUT (bb) = set_new (true);
1958 compute_avail (ENTRY_BLOCK_PTR);
1960 if (dump_file && (dump_flags & TDF_DETAILS))
1964 print_value_set (dump_file, EXP_GEN (bb), "exp_gen", bb->index);
1965 print_value_set (dump_file, TMP_GEN (bb), "tmp_gen", bb->index);
1966 print_value_set (dump_file, AVAIL_OUT (bb), "avail_out", bb->index);
1970 /* Insert can get quite slow on an incredibly large number of basic
1971 blocks due to some quadratic behavior. Until this behavior is
1972 fixed, don't run it when he have an incredibly large number of
1973 bb's. If we aren't going to run insert, there is no point in
1974 computing ANTIC, either, even though it's plenty fast. */
1976 if (n_basic_blocks < 4000)
1984 if (dump_file && (dump_flags & TDF_STATS))
1986 fprintf (dump_file, "Insertions:%d\n", pre_stats.insertions);
1987 fprintf (dump_file, "New PHIs:%d\n", pre_stats.phis);
1988 fprintf (dump_file, "Eliminated:%d\n", pre_stats.eliminations);
1991 free_alloc_pool (value_set_pool);
1992 free_alloc_pool (value_set_node_pool);
1993 free_alloc_pool (binary_node_pool);
1994 free_alloc_pool (unary_node_pool);
1995 htab_delete (value_table);
1996 htab_delete (phi_translate_table);
2003 free_dominance_info (CDI_POST_DOMINATORS);
2009 return flag_tree_pre != 0;
2012 struct tree_opt_pass pass_pre =
2015 gate_pre, /* gate */
2016 execute_pre, /* execute */
2019 0, /* static_pass_number */
2020 TV_TREE_PRE, /* tv_id */
2021 PROP_no_crit_edges | PROP_cfg | PROP_ssa,/* properties_required */
2022 0, /* properties_provided */
2023 0, /* properties_destroyed */
2024 0, /* todo_flags_start */
2025 TODO_dump_func | TODO_ggc_collect | TODO_verify_ssa /* todo_flags_finish */