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. */
25 #include "coretypes.h"
30 #include "basic-block.h"
31 #include "diagnostic.h"
32 #include "tree-inline.h"
33 #include "tree-flow.h"
34 #include "tree-gimple.h"
35 #include "tree-dump.h"
39 #include "tree-iterator.h"
41 #include "alloc-pool.h"
42 #include "tree-pass.h"
44 #include "splay-tree.h"
46 #include "langhooks.h"
50 1. Avail sets can be shared by making an avail_find_leader that
51 walks up the dominator tree and looks in those avail sets.
52 This might affect code optimality, it's unclear right now.
53 2. Load motion can be performed by value numbering the loads the
54 same as we do other expressions. This requires iterative
55 hashing the vuses into the values. Right now we simply assign
56 a new value every time we see a statement with a vuse.
57 3. Strength reduction can be performed by anticipating expressions
58 we can repair later on.
59 4. Our canonicalization of expressions during lookups don't take
60 constants into account very well. In particular, we don't fold
61 anywhere, so we can get situations where we stupidly think
62 something is a new value (a + 1 + 1 vs a + 2). This is somewhat
63 expensive to fix, but it does expose a lot more eliminations.
64 It may or not be worth it, depending on how critical you
65 consider PRE vs just plain GRE.
68 /* For ease of terminology, "expression node" in the below refers to
69 every expression node but MODIFY_EXPR, because MODIFY_EXPR's represent
70 the actual statement containing the expressions we care about, and
71 we cache the value number by putting it in the expression. */
75 First we walk the statements to generate the AVAIL sets, the
76 EXP_GEN sets, and the tmp_gen sets. EXP_GEN sets represent the
77 generation of values/expressions by a given block. We use them
78 when computing the ANTIC sets. The AVAIL sets consist of
79 SSA_NAME's that represent values, so we know what values are
80 available in what blocks. AVAIL is a forward dataflow problem. In
81 SSA, values are never killed, so we don't need a kill set, or a
82 fixpoint iteration, in order to calculate the AVAIL sets. In
83 traditional parlance, AVAIL sets tell us the downsafety of the
86 Next, we generate the ANTIC sets. These sets represent the
87 anticipatable expressions. ANTIC is a backwards dataflow
88 problem.An expression is anticipatable in a given block if it could
89 be generated in that block. This means that if we had to perform
90 an insertion in that block, of the value of that expression, we
91 could. Calculating the ANTIC sets requires phi translation of
92 expressions, because the flow goes backwards through phis. We must
93 iterate to a fixpoint of the ANTIC sets, because we have a kill
94 set. Even in SSA form, values are not live over the entire
95 function, only from their definition point onwards. So we have to
96 remove values from the ANTIC set once we go past the definition
97 point of the leaders that make them up.
98 compute_antic/compute_antic_aux performs this computation.
100 Third, we perform insertions to make partially redundant
101 expressions fully redundant.
103 An expression is partially redundant (excluding partial
106 1. It is AVAIL in some, but not all, of the predecessors of a
108 2. It is ANTIC in all the predecessors.
110 In order to make it fully redundant, we insert the expression into
111 the predecessors where it is not available, but is ANTIC.
112 insert/insert_aux performs this insertion.
114 Fourth, we eliminate fully redundant expressions.
115 This is a simple statement walk that replaces redundant
116 calculations with the now available values. */
118 /* Representations of value numbers:
120 Value numbers are represented using the "value handle" approach.
121 This means that each SSA_NAME (and for other reasons to be
122 disclosed in a moment, expression nodes) has a value handle that
123 can be retrieved through get_value_handle. This value handle, *is*
124 the value number of the SSA_NAME. You can pointer compare the
125 value handles for equivalence purposes.
127 For debugging reasons, the value handle is internally more than
128 just a number, it is a VAR_DECL named "value.x", where x is a
129 unique number for each value number in use. This allows
130 expressions with SSA_NAMES replaced by value handles to still be
131 pretty printed in a sane way. They simply print as "value.3 *
134 Expression nodes have value handles associated with them as a
135 cache. Otherwise, we'd have to look them up again in the hash
136 table This makes significant difference (factor of two or more) on
137 some test cases. They can be thrown away after the pass is
140 /* Representation of expressions on value numbers:
142 In some portions of this code, you will notice we allocate "fake"
143 analogues to the expression we are value numbering, and replace the
144 operands with the values of the expression. Since we work on
145 values, and not just names, we canonicalize expressions to value
146 expressions for use in the ANTIC sets, the EXP_GEN set, etc.
148 This is theoretically unnecessary, it just saves a bunch of
149 repeated get_value_handle and find_leader calls in the remainder of
150 the code, trading off temporary memory usage for speed. The tree
151 nodes aren't actually creating more garbage, since they are
152 allocated in a special pools which are thrown away at the end of
155 All of this also means that if you print the EXP_GEN or ANTIC sets,
156 you will see "value.5 + value.7" in the set, instead of "a_55 +
157 b_66" or something. The only thing that actually cares about
158 seeing the value leaders is phi translation, and it needs to be
159 able to find the leader for a value in an arbitrary block, so this
160 "value expression" form is perfect for it (otherwise you'd do
161 get_value_handle->find_leader->translate->get_value_handle->find_leader).*/
164 /* Representation of sets:
166 There are currently two types of sets used, hopefully to be unified soon.
167 The AVAIL sets do not need to be sorted in any particular order,
168 and thus, are simply represented as two bitmaps, one that keeps
169 track of values present in the set, and one that keeps track of
170 expressions present in the set.
172 The other sets are represented as doubly linked lists kept in topological
173 order, with an optional supporting bitmap of values present in the
174 set. The sets represent values, and the elements can be values or
175 expressions. The elements can appear in different sets, but each
176 element can only appear once in each set.
178 Since each node in the set represents a value, we also want to be
179 able to map expression, set pairs to something that tells us
180 whether the value is present is a set. We use a per-set bitmap for
181 that. The value handles also point to a linked list of the
182 expressions they represent via a tree annotation. This is mainly
183 useful only for debugging, since we don't do identity lookups. */
186 /* A value set element. Basically a single linked list of
187 expressions/values. */
188 typedef struct value_set_node
193 /* A pointer to the next element of the value set. */
194 struct value_set_node *next;
198 /* A value set. This is a singly linked list of value_set_node
199 elements with a possible bitmap that tells us what values exist in
200 the set. This set must be kept in topologically sorted order. */
201 typedef struct value_set
203 /* The head of the list. Used for iterating over the list in
205 value_set_node_t head;
207 /* The tail of the list. Used for tail insertions, which are
208 necessary to keep the set in topologically sorted order because
209 of how the set is built. */
210 value_set_node_t tail;
212 /* The length of the list. */
215 /* True if the set is indexed, which means it contains a backing
216 bitmap for quick determination of whether certain values exist in the
220 /* The bitmap of values that exist in the set. May be NULL in an
221 empty or non-indexed set. */
227 /* An unordered bitmap set. One bitmap tracks values, the other,
229 typedef struct bitmap_set
235 /* Sets that we need to keep track of. */
236 typedef struct bb_value_sets
238 /* The EXP_GEN set, which represents expressions/values generated in
242 /* The PHI_GEN set, which represents PHI results generated in a
244 bitmap_set_t phi_gen;
246 /* The TMP_GEN set, which represents results/temporaries generated
247 in a basic block. IE the LHS of an expression. */
248 bitmap_set_t tmp_gen;
250 /* The AVAIL_OUT set, which represents which values are available in
251 a given basic block. */
252 bitmap_set_t avail_out;
254 /* The ANTIC_IN set, which represents which values are anticiptable
255 in a given basic block. */
256 value_set_t antic_in;
258 /* The NEW_SETS set, which is used during insertion to augment the
259 AVAIL_OUT set of blocks with the new insertions performed during
260 the current iteration. */
261 bitmap_set_t new_sets;
264 #define EXP_GEN(BB) ((bb_value_sets_t) ((BB)->aux))->exp_gen
265 #define PHI_GEN(BB) ((bb_value_sets_t) ((BB)->aux))->phi_gen
266 #define TMP_GEN(BB) ((bb_value_sets_t) ((BB)->aux))->tmp_gen
267 #define AVAIL_OUT(BB) ((bb_value_sets_t) ((BB)->aux))->avail_out
268 #define ANTIC_IN(BB) ((bb_value_sets_t) ((BB)->aux))->antic_in
269 #define NEW_SETS(BB) ((bb_value_sets_t) ((BB)->aux))->new_sets
271 /* This structure is used to keep track of statistics on what
272 optimization PRE was able to perform. */
275 /* The number of RHS computations eliminated by PRE. */
278 /* The number of new expressions/temporaries generated by PRE. */
281 /* The number of new PHI nodes added by PRE. */
286 static tree bitmap_find_leader (bitmap_set_t, tree);
287 static tree find_leader (value_set_t, tree);
288 static void value_insert_into_set (value_set_t, tree);
289 static void bitmap_value_insert_into_set (bitmap_set_t, tree);
290 static void bitmap_value_replace_in_set (bitmap_set_t, tree);
291 static void insert_into_set (value_set_t, tree);
292 static void bitmap_set_copy (bitmap_set_t, bitmap_set_t);
293 static bool bitmap_set_contains_value (bitmap_set_t, tree);
294 static bitmap_set_t bitmap_set_new (void);
295 static value_set_t set_new (bool);
296 static bool is_undefined_value (tree);
297 static tree create_expression_by_pieces (basic_block, tree, tree);
300 /* We can add and remove elements and entries to and from sets
301 and hash tables, so we use alloc pools for them. */
303 static alloc_pool value_set_pool;
304 static alloc_pool bitmap_set_pool;
305 static alloc_pool value_set_node_pool;
306 static alloc_pool binary_node_pool;
307 static alloc_pool unary_node_pool;
309 /* The phi_translate_table caches phi translations for a given
310 expression and predecessor. */
312 static htab_t phi_translate_table;
314 /* A three tuple {e, pred, v} used to cache phi translations in the
315 phi_translate_table. */
317 typedef struct expr_pred_trans_d
319 /* The expression. */
322 /* The predecessor block along which we translated the expression. */
325 /* The value that resulted from the translation. */
328 /* The hashcode for the expression, pred pair. This is cached for
331 } *expr_pred_trans_t;
333 /* Return the hash value for a phi translation table entry. */
336 expr_pred_trans_hash (const void *p)
338 const expr_pred_trans_t ve = (expr_pred_trans_t) p;
342 /* Return true if two phi translation table entries are the same.
343 P1 and P2 should point to the expr_pred_trans_t's to be compared.*/
346 expr_pred_trans_eq (const void *p1, const void *p2)
348 const expr_pred_trans_t ve1 = (expr_pred_trans_t) p1;
349 const expr_pred_trans_t ve2 = (expr_pred_trans_t) p2;
350 basic_block b1 = ve1->pred;
351 basic_block b2 = ve2->pred;
354 /* If they are not translations for the same basic block, they can't
359 /* If they are for the same basic block, determine if the
360 expressions are equal. */
361 if (expressions_equal_p (ve1->e, ve2->e))
367 /* Search in the phi translation table for the translation of
368 expression E in basic block PRED. Return the translated value, if
369 found, NULL otherwise. */
372 phi_trans_lookup (tree e, basic_block pred)
375 struct expr_pred_trans_d ept;
378 ept.hashcode = vn_compute (e, (unsigned long) pred, NULL);
379 slot = htab_find_slot_with_hash (phi_translate_table, &ept, ept.hashcode,
384 return ((expr_pred_trans_t) *slot)->v;
388 /* Add the tuple mapping from {expression E, basic block PRED} to
389 value V, to the phi translation table. */
392 phi_trans_add (tree e, tree v, basic_block pred)
395 expr_pred_trans_t new_pair = xmalloc (sizeof (*new_pair));
397 new_pair->pred = pred;
399 new_pair->hashcode = vn_compute (e, (unsigned long) pred, NULL);
400 slot = htab_find_slot_with_hash (phi_translate_table, new_pair,
401 new_pair->hashcode, INSERT);
404 *slot = (void *) new_pair;
408 /* Add expression E to the expression set of value V. */
411 add_to_value (tree v, tree e)
413 /* Constants have no expression sets. */
414 if (is_gimple_min_invariant (v))
417 if (VALUE_HANDLE_EXPR_SET (v) == NULL)
418 VALUE_HANDLE_EXPR_SET (v) = set_new (false);
420 insert_into_set (VALUE_HANDLE_EXPR_SET (v), e);
424 /* Return true if value V exists in the bitmap for SET. */
427 value_exists_in_set_bitmap (value_set_t set, tree v)
432 return bitmap_bit_p (set->values, VALUE_HANDLE_ID (v));
436 /* Remove value V from the bitmap for SET. */
439 value_remove_from_set_bitmap (value_set_t set, tree v)
441 #ifdef ENABLE_CHECKING
449 bitmap_clear_bit (set->values, VALUE_HANDLE_ID (v));
453 /* Insert the value number V into the bitmap of values existing in
457 value_insert_into_set_bitmap (value_set_t set, tree v)
459 #ifdef ENABLE_CHECKING
464 if (set->values == NULL)
466 set->values = BITMAP_GGC_ALLOC ();
467 bitmap_clear (set->values);
470 bitmap_set_bit (set->values, VALUE_HANDLE_ID (v));
474 /* Create a new bitmap set and return it. */
477 bitmap_set_new (void)
479 bitmap_set_t ret = pool_alloc (bitmap_set_pool);
480 ret->expressions = BITMAP_GGC_ALLOC ();
481 ret->values = BITMAP_GGC_ALLOC ();
482 bitmap_clear (ret->expressions);
483 bitmap_clear (ret->values);
487 /* Create a new set. */
490 set_new (bool indexed)
493 ret = pool_alloc (value_set_pool);
494 ret->head = ret->tail = NULL;
496 ret->indexed = indexed;
501 /* Insert an expression EXPR into a bitmapped set. */
504 bitmap_insert_into_set (bitmap_set_t set, tree expr)
507 /* XXX: For now, we only let SSA_NAMES into the bitmap sets. */
508 if (TREE_CODE (expr) != SSA_NAME)
510 val = get_value_handle (expr);
514 if (!is_gimple_min_invariant (val))
515 bitmap_set_bit (set->values, VALUE_HANDLE_ID (val));
516 bitmap_set_bit (set->expressions, SSA_NAME_VERSION (expr));
519 /* Insert EXPR into SET. */
522 insert_into_set (value_set_t set, tree expr)
524 value_set_node_t newnode = pool_alloc (value_set_node_pool);
525 tree val = get_value_handle (expr);
530 /* For indexed sets, insert the value into the set value bitmap.
531 For all sets, add it to the linked list and increment the list
534 value_insert_into_set_bitmap (set, val);
536 newnode->next = NULL;
537 newnode->expr = expr;
539 if (set->head == NULL)
541 set->head = set->tail = newnode;
545 set->tail->next = newnode;
550 /* Copy a bitmapped set ORIG, into bitmapped set DEST. */
553 bitmap_set_copy (bitmap_set_t dest, bitmap_set_t orig)
555 bitmap_copy (dest->expressions, orig->expressions);
556 bitmap_copy (dest->values, orig->values);
559 /* Copy the set ORIG to the set DEST. */
562 set_copy (value_set_t dest, value_set_t orig)
564 value_set_node_t node;
566 if (!orig || !orig->head)
569 for (node = orig->head;
573 insert_into_set (dest, node->expr);
577 /* Remove EXPR from SET. */
580 set_remove (value_set_t set, tree expr)
582 value_set_node_t node, prev;
584 /* Remove the value of EXPR from the bitmap, decrement the set
585 length, and remove it from the actual double linked list. */
586 value_remove_from_set_bitmap (set, get_value_handle (expr));
589 for (node = set->head;
591 prev = node, node = node->next)
593 if (node->expr == expr)
596 set->head = node->next;
598 prev->next= node->next;
600 if (node == set->tail)
602 pool_free (value_set_node_pool, node);
608 /* Return true if SET contains the value VAL. */
611 set_contains_value (value_set_t set, tree val)
613 /* All constants are in every set. */
614 if (is_gimple_min_invariant (val))
617 if (set->length == 0)
620 return value_exists_in_set_bitmap (set, val);
623 /* Return true if bitmapped set SET contains the expression EXPR. */
625 bitmap_set_contains (bitmap_set_t set, tree expr)
627 /* XXX: Bitmapped sets only contain SSA_NAME's for now. */
628 if (TREE_CODE (expr) != SSA_NAME)
630 return bitmap_bit_p (set->expressions, SSA_NAME_VERSION (expr));
634 /* Return true if bitmapped set SET contains the value VAL. */
637 bitmap_set_contains_value (bitmap_set_t set, tree val)
639 if (is_gimple_min_invariant (val))
641 return bitmap_bit_p (set->values, VALUE_HANDLE_ID (val));
644 /* Replace an instance of value LOOKFOR with expression EXPR in SET. */
647 bitmap_set_replace_value (bitmap_set_t set, tree lookfor, tree expr)
650 value_set_node_t node;
651 if (is_gimple_min_invariant (lookfor))
653 if (!bitmap_set_contains_value (set, lookfor))
655 /* The number of expressions having a given value is usually
656 significantly less than the total number of expressions in SET.
657 Thus, rather than check, for each expression in SET, whether it
658 has the value LOOKFOR, we walk the reverse mapping that tells us
659 what expressions have a given value, and see if any of those
660 expressions are in our set. For large testcases, this is about
661 5-10x faster than walking the bitmap. If this is somehow a
662 significant lose for some cases, we can choose which set to walk
663 based on the set size. */
664 exprset = VALUE_HANDLE_EXPR_SET (lookfor);
665 for (node = exprset->head; node; node = node->next)
667 if (TREE_CODE (node->expr) == SSA_NAME)
669 if (bitmap_bit_p (set->expressions, SSA_NAME_VERSION (node->expr)))
671 bitmap_clear_bit (set->expressions, SSA_NAME_VERSION (node->expr));
672 bitmap_set_bit (set->expressions, SSA_NAME_VERSION (expr));
679 /* Subtract bitmapped set B from value set A, and return the new set. */
682 bitmap_set_subtract_from_value_set (value_set_t a, bitmap_set_t b,
685 value_set_t ret = set_new (indexed);
686 value_set_node_t node;
691 if (!bitmap_set_contains (b, node->expr))
692 insert_into_set (ret, node->expr);
697 /* Return true if two sets are equal. */
700 set_equal (value_set_t a, value_set_t b)
702 value_set_node_t node;
704 if (a->length != b->length)
710 if (!set_contains_value (b, get_value_handle (node->expr)))
716 /* Replace an instance of EXPR's VALUE with EXPR in SET. */
719 bitmap_value_replace_in_set (bitmap_set_t set, tree expr)
721 tree val = get_value_handle (expr);
722 bitmap_set_replace_value (set, val, expr);
725 /* Insert EXPR into SET if EXPR's value is not already present in
729 bitmap_value_insert_into_set (bitmap_set_t set, tree expr)
731 tree val = get_value_handle (expr);
732 if (is_gimple_min_invariant (val))
735 if (!bitmap_set_contains_value (set, val))
736 bitmap_insert_into_set (set, expr);
739 /* Insert the value for EXPR into SET, if it doesn't exist already. */
742 value_insert_into_set (value_set_t set, tree expr)
744 tree val = get_value_handle (expr);
746 /* Constant and invariant values exist everywhere, and thus,
747 actually keeping them in the sets is pointless. */
748 if (is_gimple_min_invariant (val))
751 if (!set_contains_value (set, val))
752 insert_into_set (set, expr);
756 /* Print out SET to OUTFILE. */
759 bitmap_print_value_set (FILE *outfile, bitmap_set_t set,
760 const char *setname, int blockindex)
762 fprintf (outfile, "%s[%d] := { ", setname, blockindex);
766 EXECUTE_IF_SET_IN_BITMAP (set->expressions, 0, i,
768 print_generic_expr (outfile, ssa_name (i), 0);
770 fprintf (outfile, " (");
771 print_generic_expr (outfile, get_value_handle (ssa_name (i)), 0);
772 fprintf (outfile, ") ");
773 if (bitmap_last_set_bit (set->expressions) != i)
774 fprintf (outfile, ", ");
777 fprintf (outfile, " }\n");
779 /* Print out the value_set SET to OUTFILE. */
782 print_value_set (FILE *outfile, value_set_t set,
783 const char *setname, int blockindex)
785 value_set_node_t node;
786 fprintf (outfile, "%s[%d] := { ", setname, blockindex);
789 for (node = set->head;
793 print_generic_expr (outfile, node->expr, 0);
795 fprintf (outfile, " (");
796 print_generic_expr (outfile, get_value_handle (node->expr), 0);
797 fprintf (outfile, ") ");
800 fprintf (outfile, ", ");
804 fprintf (outfile, " }\n");
807 /* Print out the expressions that have VAL to OUTFILE. */
810 print_value_expressions (FILE *outfile, tree val)
812 if (VALUE_HANDLE_EXPR_SET (val))
815 sprintf (s, "VH.%04d", VALUE_HANDLE_ID (val));
816 print_value_set (outfile, VALUE_HANDLE_EXPR_SET (val), s, 0);
822 debug_value_expressions (tree val)
824 print_value_expressions (stderr, val);
828 void debug_value_set (value_set_t, const char *, int);
831 debug_value_set (value_set_t set, const char *setname, int blockindex)
833 print_value_set (stderr, set, setname, blockindex);
836 /* Translate EXPR using phis in PHIBLOCK, so that it has the values of
837 the phis in PRED. Return NULL if we can't find a leader for each
838 part of the translated expression. */
841 phi_translate (tree expr, value_set_t set, basic_block pred,
842 basic_block phiblock)
844 tree phitrans = NULL;
850 /* Phi translations of a given expression don't change, */
851 phitrans = phi_trans_lookup (expr, pred);
856 switch (TREE_CODE_CLASS (TREE_CODE (expr)))
860 tree oldop1 = TREE_OPERAND (expr, 0);
861 tree oldop2 = TREE_OPERAND (expr, 1);
866 newop1 = phi_translate (find_leader (set, oldop1),
867 set, pred, phiblock);
870 newop2 = phi_translate (find_leader (set, oldop2),
871 set, pred, phiblock);
874 if (newop1 != oldop1 || newop2 != oldop2)
876 newexpr = pool_alloc (binary_node_pool);
877 memcpy (newexpr, expr, tree_size (expr));
878 create_tree_ann (newexpr);
879 TREE_OPERAND (newexpr, 0) = newop1 == oldop1 ? oldop1 : get_value_handle (newop1);
880 TREE_OPERAND (newexpr, 1) = newop2 == oldop2 ? oldop2 : get_value_handle (newop2);
881 vn_lookup_or_add (newexpr, NULL);
883 phi_trans_add (oldexpr, newexpr, pred);
887 /* XXX: Until we have PRE of loads working, none will be ANTIC.
894 tree oldop1 = TREE_OPERAND (expr, 0);
898 newop1 = phi_translate (find_leader (set, oldop1),
899 set, pred, phiblock);
902 if (newop1 != oldop1)
904 newexpr = pool_alloc (unary_node_pool);
905 memcpy (newexpr, expr, tree_size (expr));
906 create_tree_ann (newexpr);
907 TREE_OPERAND (newexpr, 0) = get_value_handle (newop1);
908 vn_lookup_or_add (newexpr, NULL);
910 phi_trans_add (oldexpr, newexpr, pred);
920 if (TREE_CODE (expr) != SSA_NAME)
922 if (TREE_CODE (SSA_NAME_DEF_STMT (expr)) == PHI_NODE)
923 phi = SSA_NAME_DEF_STMT (expr);
927 for (i = 0; i < PHI_NUM_ARGS (phi); i++)
928 if (PHI_ARG_EDGE (phi, i)->src == pred)
931 if (is_undefined_value (PHI_ARG_DEF (phi, i)))
933 val = vn_lookup_or_add (PHI_ARG_DEF (phi, i), NULL);
934 return PHI_ARG_DEF (phi, i);
943 phi_translate_set (value_set_t dest, value_set_t set, basic_block pred,
944 basic_block phiblock)
946 value_set_node_t node;
947 for (node = set->head;
952 translated = phi_translate (node->expr, set, pred, phiblock);
953 phi_trans_add (node->expr, translated, pred);
955 if (translated != NULL)
956 value_insert_into_set (dest, translated);
960 /* Find the leader for a value (i.e., the name representing that
961 value) in a given set, and return it. Return NULL if no leader is
965 bitmap_find_leader (bitmap_set_t set, tree val)
970 if (is_gimple_min_invariant (val))
972 if (bitmap_set_contains_value (set, val))
974 /* Rather than walk the entire bitmap of expressions, and see
975 whether any of them has the value we are looking for, we look
976 at the reverse mapping, which tells us the set of expressions
977 that have a given value (IE value->expressions with that
978 value) and see if any of those expressions are in our set.
979 The number of expressions per value is usually significantly
980 less than the number of expressions in the set. In fact, for
981 large testcases, doing it this way is roughly 5-10x faster
982 than walking the bitmap.
983 If this is somehow a significant lose for some cases, we can
984 choose which set to walk based on which set is smaller. */
986 value_set_node_t node;
987 exprset = VALUE_HANDLE_EXPR_SET (val);
988 for (node = exprset->head; node; node = node->next)
990 if (TREE_CODE (node->expr) == SSA_NAME)
992 if (bitmap_bit_p (set->expressions,
993 SSA_NAME_VERSION (node->expr)))
1002 /* Find the leader for a value (i.e., the name representing that
1003 value) in a given set, and return it. Return NULL if no leader is
1007 find_leader (value_set_t set, tree val)
1009 value_set_node_t node;
1014 /* Constants represent themselves. */
1015 if (is_gimple_min_invariant (val))
1018 if (set->length == 0)
1021 if (value_exists_in_set_bitmap (set, val))
1023 for (node = set->head;
1027 if (get_value_handle (node->expr) == val)
1035 /* Determine if the expression EXPR is valid in SET. This means that
1036 we have a leader for each part of the expression (if it consists of
1037 values), or the expression is an SSA_NAME.
1039 NB: We never should run into a case where we have SSA_NAME +
1040 SSA_NAME or SSA_NAME + value. The sets valid_in_set is called on,
1041 the ANTIC sets, will only ever have SSA_NAME's or binary value
1042 expression (IE VALUE1 + VALUE2) */
1045 valid_in_set (value_set_t set, tree expr)
1047 switch (TREE_CODE_CLASS (TREE_CODE (expr)))
1051 tree op1 = TREE_OPERAND (expr, 0);
1052 tree op2 = TREE_OPERAND (expr, 1);
1053 return set_contains_value (set, op1) && set_contains_value (set, op2);
1058 tree op1 = TREE_OPERAND (expr, 0);
1059 return set_contains_value (set, op1);
1062 /* XXX: Until PRE of loads works, no reference nodes are ANTIC.
1070 if (TREE_CODE (expr) == SSA_NAME)
1080 /* Clean the set of expressions that are no longer valid in SET. This
1081 means expressions that are made up of values we have no leaders for
1085 clean (value_set_t set)
1087 value_set_node_t node;
1088 value_set_node_t next;
1093 if (!valid_in_set (set, node->expr))
1094 set_remove (set, node->expr);
1099 /* Compute the ANTIC set for BLOCK.
1101 ANTIC_OUT[BLOCK] = intersection of ANTIC_IN[b] for all succ(BLOCK), if
1103 ANTIC_OUT[BLOCK] = phi_translate (ANTIC_IN[succ(BLOCK)]) if
1106 ANTIC_IN[BLOCK] = clean(ANTIC_OUT[BLOCK] U EXP_GEN[BLOCK] -
1109 Iterate until fixpointed.
1111 XXX: It would be nice to either write a set_clear, and use it for
1112 antic_out, or to mark the antic_out set as deleted at the end
1113 of this routine, so that the pool can hand the same memory back out
1114 again for the next antic_out. */
1118 compute_antic_aux (basic_block block)
1122 bool changed = false;
1123 value_set_t S, old, ANTIC_OUT;
1124 value_set_node_t node;
1126 ANTIC_OUT = S = NULL;
1127 /* If any edges from predecessors are abnormal, antic_in is empty, so
1128 punt. Remember that the block has an incoming abnormal edge by
1129 setting the BB_VISITED flag. */
1130 if (! (block->flags & BB_VISITED))
1132 for (e = block->pred; e; e = e->pred_next)
1133 if (e->flags & EDGE_ABNORMAL)
1135 block->flags |= BB_VISITED;
1139 if (block->flags & BB_VISITED)
1146 old = set_new (false);
1147 set_copy (old, ANTIC_IN (block));
1148 ANTIC_OUT = set_new (true);
1150 /* If the block has no successors, ANTIC_OUT is empty, because it is
1152 if (block->succ == NULL);
1154 /* If we have one successor, we could have some phi nodes to
1155 translate through. */
1156 else if (block->succ->succ_next == NULL)
1158 phi_translate_set (ANTIC_OUT, ANTIC_IN(block->succ->dest),
1159 block, block->succ->dest);
1161 /* If we have multiple successors, we take the intersection of all of
1165 varray_type worklist;
1168 basic_block bprime, first;
1170 VARRAY_BB_INIT (worklist, 1, "succ");
1174 VARRAY_PUSH_BB (worklist, e->dest);
1177 first = VARRAY_BB (worklist, 0);
1178 set_copy (ANTIC_OUT, ANTIC_IN (first));
1180 for (i = 1; i < VARRAY_ACTIVE_SIZE (worklist); i++)
1182 bprime = VARRAY_BB (worklist, i);
1183 node = ANTIC_OUT->head;
1187 value_set_node_t next = node->next;
1188 val = get_value_handle (node->expr);
1189 if (!set_contains_value (ANTIC_IN (bprime), val))
1190 set_remove (ANTIC_OUT, node->expr);
1194 VARRAY_CLEAR (worklist);
1197 /* Generate ANTIC_OUT - TMP_GEN */
1198 S = bitmap_set_subtract_from_value_set (ANTIC_OUT, TMP_GEN (block), false);
1200 /* Start ANTIC_IN with EXP_GEN - TMP_GEN */
1201 ANTIC_IN (block) = bitmap_set_subtract_from_value_set (EXP_GEN (block),
1205 /* Then union in the ANTIC_OUT - TMP_GEN values, to get ANTIC_OUT U
1206 EXP_GEN - TMP_GEN */
1207 for (node = S->head;
1211 value_insert_into_set (ANTIC_IN (block), node->expr);
1213 clean (ANTIC_IN (block));
1216 if (!set_equal (old, ANTIC_IN (block)))
1220 if (dump_file && (dump_flags & TDF_DETAILS))
1223 print_value_set (dump_file, ANTIC_OUT, "ANTIC_OUT", block->index);
1224 print_value_set (dump_file, ANTIC_IN (block), "ANTIC_IN", block->index);
1226 print_value_set (dump_file, S, "S", block->index);
1230 for (son = first_dom_son (CDI_POST_DOMINATORS, block);
1232 son = next_dom_son (CDI_POST_DOMINATORS, son))
1234 changed |= compute_antic_aux (son);
1239 /* Compute ANTIC sets. */
1242 compute_antic (void)
1244 bool changed = true;
1246 int num_iterations = 0;
1249 ANTIC_IN (bb) = set_new (true);
1250 if (bb->flags & BB_VISITED)
1258 changed = compute_antic_aux (EXIT_BLOCK_PTR);
1262 bb->flags &= ~BB_VISITED;
1264 if (num_iterations > 2 && dump_file && (dump_flags & TDF_STATS))
1265 fprintf (dump_file, "compute_antic required %d iterations\n", num_iterations);
1269 /* Find a leader for an expression, or generate one using
1270 create_expression_by_pieces if it's ANTIC but
1272 BLOCK is the basic_block we are looking for leaders in.
1273 EXPR is the expression to find a leader or generate for.
1274 STMTS is the statement list to put the inserted expressions on.
1275 Returns the SSA_NAME of the LHS of the generated expression or the
1279 find_or_generate_expression (basic_block block, tree expr, tree stmts)
1282 genop = bitmap_find_leader (AVAIL_OUT (block), expr);
1283 /* Depending on the order we process DOM branches in, the value
1284 may not have propagated to all the dom children yet during
1285 this iteration. In this case, the value will always be in
1286 the NEW_SETS for us already, having been propagated from our
1289 genop = bitmap_find_leader (NEW_SETS (block), expr);
1290 /* If it's still NULL, see if it is a complex expression, and if
1291 so, generate it recursively, otherwise, abort, because it's
1295 genop = VALUE_HANDLE_EXPR_SET (expr)->head->expr;
1296 if (TREE_CODE_CLASS (TREE_CODE (genop)) != '1'
1297 && TREE_CODE_CLASS (TREE_CODE (genop)) != '2')
1299 genop = create_expression_by_pieces (block, genop, stmts);
1305 /* Create an expression in pieces, so that we can handle very complex
1306 expressions that may be ANTIC, but not necessary GIMPLE.
1307 BLOCK is the basic block the expression will be inserted into,
1308 EXPR is the expression to insert (in value form)
1309 STMTS is a statement list to append the necessary insertions into.
1311 This function will abort if we hit some value that shouldn't be
1312 ANTIC but is (IE there is no leader for it, or its components).
1313 This function may also generate expressions that are themselves
1314 partially or fully redundant. Those that are will be either made
1315 fully redundant during the next iteration of insert (for partially
1316 redundant ones), or eliminated by eliminate (for fully redundant
1320 create_expression_by_pieces (basic_block block, tree expr, tree stmts)
1322 tree name = NULL_TREE;
1323 tree newexpr = NULL_TREE;
1326 switch (TREE_CODE_CLASS (TREE_CODE (expr)))
1330 tree_stmt_iterator tsi;
1331 tree genop1, genop2;
1333 tree op1 = TREE_OPERAND (expr, 0);
1334 tree op2 = TREE_OPERAND (expr, 1);
1335 genop1 = find_or_generate_expression (block, op1, stmts);
1336 genop2 = find_or_generate_expression (block, op2, stmts);
1337 temp = create_tmp_var (TREE_TYPE (expr), "pretmp");
1338 add_referenced_tmp_var (temp);
1339 newexpr = build (TREE_CODE (expr), TREE_TYPE (expr),
1341 newexpr = build (MODIFY_EXPR, TREE_TYPE (expr),
1343 name = make_ssa_name (temp, newexpr);
1344 TREE_OPERAND (newexpr, 0) = name;
1345 tsi = tsi_last (stmts);
1346 tsi_link_after (&tsi, newexpr, TSI_CONTINUE_LINKING);
1347 pre_stats.insertions++;
1352 tree_stmt_iterator tsi;
1355 tree op1 = TREE_OPERAND (expr, 0);
1356 genop1 = find_or_generate_expression (block, op1, stmts);
1357 temp = create_tmp_var (TREE_TYPE (expr), "pretmp");
1358 add_referenced_tmp_var (temp);
1359 newexpr = build (TREE_CODE (expr), TREE_TYPE (expr),
1361 newexpr = build (MODIFY_EXPR, TREE_TYPE (expr),
1363 name = make_ssa_name (temp, newexpr);
1364 TREE_OPERAND (newexpr, 0) = name;
1365 tsi = tsi_last (stmts);
1366 tsi_link_after (&tsi, newexpr, TSI_CONTINUE_LINKING);
1367 pre_stats.insertions++;
1375 v = get_value_handle (expr);
1376 vn_add (name, v, NULL);
1377 bitmap_insert_into_set (NEW_SETS (block), name);
1378 bitmap_value_insert_into_set (AVAIL_OUT (block), name);
1379 if (dump_file && (dump_flags & TDF_DETAILS))
1381 fprintf (dump_file, "Inserted ");
1382 print_generic_expr (dump_file, newexpr, 0);
1383 fprintf (dump_file, " in predecessor %d\n", block->index);
1388 /* Perform insertion of partially redundant values.
1389 For BLOCK, do the following:
1390 1. Propagate the NEW_SETS of the dominator into the current block.
1391 If the block has multiple predecessors,
1392 2a. Iterate over the ANTIC expressions for the block to see if
1393 any of them are partially redundant.
1394 2b. If so, insert them into the necessary predecessors to make
1395 the expression fully redundant.
1396 2c. Insert a new PHI merging the values of the predecessors.
1397 2d. Insert the new PHI, and the new expressions, into the
1399 3. Recursively call ourselves on the dominator children of BLOCK.
1403 insert_aux (basic_block block)
1406 bool new_stuff = false;
1411 dom = get_immediate_dominator (CDI_DOMINATORS, block);
1415 bitmap_set_t newset = NEW_SETS (dom);
1416 EXECUTE_IF_SET_IN_BITMAP (newset->expressions, 0, i,
1418 bitmap_insert_into_set (NEW_SETS (block), ssa_name (i));
1419 bitmap_value_replace_in_set (AVAIL_OUT (block), ssa_name (i));
1421 if (block->pred->pred_next)
1423 value_set_node_t node;
1424 for (node = ANTIC_IN (block)->head;
1428 if (TREE_CODE_CLASS (TREE_CODE (node->expr)) == '2'
1429 || TREE_CODE_CLASS (TREE_CODE (node->expr)) == '1')
1433 bool by_some = false;
1434 bool cant_insert = false;
1435 bool all_same = true;
1436 tree first_s = NULL;
1441 val = get_value_handle (node->expr);
1442 if (bitmap_set_contains_value (PHI_GEN (block), val))
1444 if (bitmap_set_contains_value (AVAIL_OUT (dom), val))
1446 if (dump_file && (dump_flags & TDF_DETAILS))
1447 fprintf (dump_file, "Found fully redundant value\n");
1451 avail = xcalloc (last_basic_block, sizeof (tree));
1452 for (pred = block->pred;
1454 pred = pred->pred_next)
1459 eprime = phi_translate (node->expr,
1463 /* eprime will generally only be NULL if the
1464 value of the expression, translated
1465 through the PHI for this predecessor, is
1466 undefined. If that is the case, we can't
1467 make the expression fully redundant,
1468 because its value is undefined along a
1469 predecessor path. We can thus break out
1470 early because it doesn't matter what the
1471 rest of the results are. */
1478 vprime = get_value_handle (eprime);
1481 edoubleprime = bitmap_find_leader (AVAIL_OUT (bprime),
1483 if (edoubleprime == NULL)
1485 avail[bprime->index] = eprime;
1490 avail[bprime->index] = edoubleprime;
1492 if (first_s == NULL)
1493 first_s = edoubleprime;
1494 else if (first_s != edoubleprime)
1496 if (first_s != edoubleprime
1497 && operand_equal_p (first_s, edoubleprime, 0))
1501 /* If we can insert it, it's not the same value
1502 already existing along every predecessor, and
1503 it's defined by some predecessor, it is
1504 partially redundant. */
1505 if (!cant_insert && !all_same && by_some)
1507 tree type = TREE_TYPE (avail[block->pred->src->index]);
1509 if (dump_file && (dump_flags & TDF_DETAILS))
1511 fprintf (dump_file, "Found partial redundancy for expression ");
1512 print_generic_expr (dump_file, node->expr, 0);
1513 fprintf (dump_file, "\n");
1516 /* Make the necessary insertions. */
1517 for (pred = block->pred;
1519 pred = pred->pred_next)
1521 tree stmts = alloc_stmt_list ();
1524 eprime = avail[bprime->index];
1525 if (TREE_CODE_CLASS (TREE_CODE (eprime)) == '2'
1526 || TREE_CODE_CLASS (TREE_CODE (eprime)) == '1')
1528 builtexpr = create_expression_by_pieces (bprime,
1531 bsi_insert_on_edge (pred, stmts);
1532 bsi_commit_edge_inserts (NULL);
1533 avail[bprime->index] = builtexpr;
1536 /* Now build a phi for the new variable. */
1537 temp = create_tmp_var (type, "prephitmp");
1538 add_referenced_tmp_var (temp);
1539 temp = create_phi_node (temp, block);
1540 vn_add (PHI_RESULT (temp), val, NULL);
1543 if (!set_contains_value (AVAIL_OUT (block), val))
1544 insert_into_set (AVAIL_OUT (block),
1548 bitmap_value_replace_in_set (AVAIL_OUT (block),
1550 for (pred = block->pred;
1552 pred = pred->pred_next)
1554 add_phi_arg (&temp, avail[pred->src->index],
1557 if (dump_file && (dump_flags & TDF_DETAILS))
1559 fprintf (dump_file, "Created phi ");
1560 print_generic_expr (dump_file, temp, 0);
1561 fprintf (dump_file, " in block %d\n", block->index);
1565 bitmap_insert_into_set (NEW_SETS (block),
1567 bitmap_insert_into_set (PHI_GEN (block),
1577 for (son = first_dom_son (CDI_DOMINATORS, block);
1579 son = next_dom_son (CDI_DOMINATORS, son))
1581 new_stuff |= insert_aux (son);
1587 /* Perform insertion of partially redundant values. */
1592 bool new_stuff = true;
1594 int num_iterations = 0;
1597 NEW_SETS (bb) = bitmap_set_new ();
1603 new_stuff = insert_aux (ENTRY_BLOCK_PTR);
1605 if (num_iterations > 2 && dump_file && (dump_flags & TDF_STATS))
1606 fprintf (dump_file, "insert required %d iterations\n", num_iterations);
1610 /* Return true if VAR is an SSA variable with no defining statement in
1611 this procedure, *AND* isn't a live-on-entry parameter. */
1614 is_undefined_value (tree expr)
1616 return (TREE_CODE (expr) == SSA_NAME
1617 && IS_EMPTY_STMT (SSA_NAME_DEF_STMT (expr))
1618 /* PARM_DECLs and hard registers are always defined. */
1619 && TREE_CODE (SSA_NAME_VAR (expr)) != PARM_DECL
1620 && !DECL_HARD_REGISTER (SSA_NAME_VAR (expr)));
1624 /* Given an SSA variable VAR and an expression EXPR, compute the value
1625 number for EXPR and create a value handle (VAL) for it. If VAR and
1626 EXPR are not the same, associate VAL with VAR. Finally, add VAR to
1627 S1 and its value handle to S2.
1629 VUSES represent the virtual use operands associated with EXPR (if
1630 any). They are used when computing the hash value for EXPR. */
1633 add_to_sets (tree var, tree expr, vuse_optype vuses, bitmap_set_t s1,
1636 tree val = vn_lookup_or_add (expr, vuses);
1638 /* VAR and EXPR may be the same when processing statements for which
1639 we are not computing value numbers (e.g., non-assignments, or
1640 statements that make aliased stores). In those cases, we are
1641 only interested in making VAR available as its own value. */
1643 vn_add (var, val, vuses);
1645 bitmap_insert_into_set (s1, var);
1646 bitmap_value_insert_into_set (s2, var);
1650 /* Given a unary or binary expression EXPR, create and return a new
1651 expression with the same structure as EXPR but with its operands
1652 replaced with the value handles of each of the operands of EXPR.
1653 Insert EXPR's operands into the EXP_GEN set for BLOCK.
1655 VUSES represent the virtual use operands associated with EXPR (if
1656 any). They are used when computing the hash value for EXPR. */
1659 create_value_expr_from (tree expr, basic_block block, vuse_optype vuses)
1662 enum tree_code code = TREE_CODE (expr);
1665 #if defined ENABLE_CHECKING
1666 if (TREE_CODE_CLASS (code) != '1'
1667 && TREE_CODE_CLASS (code) != '2')
1671 if (TREE_CODE_CLASS (code) == '1')
1672 vexpr = pool_alloc (unary_node_pool);
1674 vexpr = pool_alloc (binary_node_pool);
1676 memcpy (vexpr, expr, tree_size (expr));
1678 for (i = 0; i < TREE_CODE_LENGTH (code); i++)
1680 tree op = TREE_OPERAND (expr, i);
1683 tree val = vn_lookup_or_add (op, vuses);
1684 if (!is_undefined_value (op))
1685 value_insert_into_set (EXP_GEN (block), op);
1686 TREE_TYPE (val) = TREE_TYPE (TREE_OPERAND (vexpr, i));
1687 TREE_OPERAND (vexpr, i) = val;
1695 /* Compute the AVAIL set for BLOCK.
1696 This function performs value numbering of the statements in BLOCK.
1697 The AVAIL sets are built from information we glean while doing this
1698 value numbering, since the AVAIL sets contain only one entry per
1701 AVAIL_IN[BLOCK] = AVAIL_OUT[dom(BLOCK)].
1702 AVAIL_OUT[BLOCK] = AVAIL_IN[BLOCK] U PHI_GEN[BLOCK] U TMP_GEN[BLOCK]. */
1705 compute_avail (basic_block block)
1709 /* For arguments with default definitions, we pretend they are
1710 defined in the entry block. */
1711 if (block == ENTRY_BLOCK_PTR)
1714 for (param = DECL_ARGUMENTS (current_function_decl);
1716 param = TREE_CHAIN (param))
1718 if (default_def (param) != NULL)
1721 tree def = default_def (param);
1722 val = vn_lookup_or_add (def, NULL);
1723 bitmap_insert_into_set (TMP_GEN (block), def);
1724 bitmap_value_insert_into_set (AVAIL_OUT (block), def);
1730 block_stmt_iterator bsi;
1734 /* Initially, the set of available values in BLOCK is that of
1735 its immediate dominator. */
1736 dom = get_immediate_dominator (CDI_DOMINATORS, block);
1738 bitmap_set_copy (AVAIL_OUT (block), AVAIL_OUT (dom));
1740 /* Generate values for PHI nodes. */
1741 for (phi = phi_nodes (block); phi; phi = PHI_CHAIN (phi))
1742 /* We have no need for virtual phis, as they don't represent
1743 actual computations. */
1744 if (is_gimple_reg (PHI_RESULT (phi)))
1745 add_to_sets (PHI_RESULT (phi), PHI_RESULT (phi), NULL,
1746 PHI_GEN (block), AVAIL_OUT (block));
1748 /* Now compute value numbers and populate value sets with all
1749 the expressions computed in BLOCK. */
1750 for (bsi = bsi_start (block); !bsi_end_p (bsi); bsi_next (&bsi))
1755 stmt = bsi_stmt (bsi);
1756 ann = stmt_ann (stmt);
1757 get_stmt_operands (stmt);
1759 /* We are only interested in assignments of the form
1760 X_i = EXPR, where EXPR represents an "interesting"
1761 computation, it has no volatile operands and X_i
1762 doesn't flow through an abnormal edge. */
1763 if (TREE_CODE (stmt) == MODIFY_EXPR
1764 && !ann->has_volatile_ops
1765 && TREE_CODE (TREE_OPERAND (stmt, 0)) == SSA_NAME
1766 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (TREE_OPERAND (stmt, 0)))
1768 tree lhs = TREE_OPERAND (stmt, 0);
1769 tree rhs = TREE_OPERAND (stmt, 1);
1770 vuse_optype vuses = STMT_VUSE_OPS (stmt);
1772 STRIP_USELESS_TYPE_CONVERSION (rhs);
1774 if (TREE_CODE_CLASS (TREE_CODE (rhs)) == '1'
1775 || TREE_CODE_CLASS (TREE_CODE (rhs)) == '2')
1777 /* For binary, unary, and reference expressions,
1778 create a duplicate expression with the operands
1779 replaced with the value handles of the original
1781 tree newt = create_value_expr_from (rhs, block, vuses);
1782 add_to_sets (lhs, newt, vuses, TMP_GEN (block),
1784 value_insert_into_set (EXP_GEN (block), newt);
1787 else if (TREE_CODE (rhs) == SSA_NAME
1788 || is_gimple_min_invariant (rhs))
1790 /* Compute a value number for the RHS of the statement
1791 and add its value to the AVAIL_OUT set for the block.
1792 Add the LHS to TMP_GEN. */
1793 add_to_sets (lhs, rhs, vuses, TMP_GEN (block),
1796 if (TREE_CODE (rhs) == SSA_NAME
1797 && !is_undefined_value (rhs))
1798 value_insert_into_set (EXP_GEN (block), rhs);
1803 /* For any other statement that we don't recognize, simply
1804 make the names generated by the statement available in
1805 AVAIL_OUT and TMP_GEN. */
1806 for (j = 0; j < NUM_DEFS (STMT_DEF_OPS (stmt)); j++)
1808 tree def = DEF_OP (STMT_DEF_OPS (stmt), j);
1809 add_to_sets (def, def, NULL, TMP_GEN (block),
1813 for (j = 0; j < NUM_USES (STMT_USE_OPS (stmt)); j++)
1815 tree use = USE_OP (STMT_USE_OPS (stmt), j);
1816 add_to_sets (use, use, NULL, TMP_GEN (block),
1822 /* Compute available sets for the dominator children of BLOCK. */
1823 for (son = first_dom_son (CDI_DOMINATORS, block);
1825 son = next_dom_son (CDI_DOMINATORS, son))
1826 compute_avail (son);
1830 /* Eliminate fully redundant computations. */
1839 block_stmt_iterator i;
1841 for (i = bsi_start (b); !bsi_end_p (i); bsi_next (&i))
1843 tree stmt = bsi_stmt (i);
1845 /* Lookup the RHS of the expression, see if we have an
1846 available computation for it. If so, replace the RHS with
1847 the available computation. */
1848 if (TREE_CODE (stmt) == MODIFY_EXPR
1849 && TREE_CODE (TREE_OPERAND (stmt, 0)) == SSA_NAME
1850 && TREE_CODE (TREE_OPERAND (stmt ,1)) != SSA_NAME
1851 && !is_gimple_min_invariant (TREE_OPERAND (stmt, 1))
1852 && !stmt_ann (stmt)->has_volatile_ops)
1854 tree lhs = TREE_OPERAND (stmt, 0);
1855 tree *rhs_p = &TREE_OPERAND (stmt, 1);
1857 vuse_optype vuses = STMT_VUSE_OPS (stmt);
1859 sprime = bitmap_find_leader (AVAIL_OUT (b), vn_lookup (lhs, vuses));
1862 && (TREE_CODE (*rhs_p) != SSA_NAME
1863 || may_propagate_copy (*rhs_p, sprime)))
1865 if (sprime == *rhs_p)
1868 if (dump_file && (dump_flags & TDF_DETAILS))
1870 fprintf (dump_file, "Replaced ");
1871 print_generic_expr (dump_file, *rhs_p, 0);
1872 fprintf (dump_file, " with ");
1873 print_generic_expr (dump_file, sprime, 0);
1874 fprintf (dump_file, " in ");
1875 print_generic_stmt (dump_file, stmt, 0);
1877 pre_stats.eliminations++;
1878 propagate_tree_value (rhs_p, sprime);
1887 /* Initialize data structures used by PRE. */
1896 memset (&pre_stats, 0, sizeof (pre_stats));
1898 bb->aux = xcalloc (1, sizeof (struct bb_value_sets));
1900 phi_translate_table = htab_create (511, expr_pred_trans_hash,
1901 expr_pred_trans_eq, free);
1902 value_set_pool = create_alloc_pool ("Value sets",
1903 sizeof (struct value_set), 30);
1904 bitmap_set_pool = create_alloc_pool ("Bitmap sets",
1905 sizeof (struct bitmap_set), 30);
1906 value_set_node_pool = create_alloc_pool ("Value set nodes",
1907 sizeof (struct value_set_node), 30);
1908 calculate_dominance_info (CDI_POST_DOMINATORS);
1909 calculate_dominance_info (CDI_DOMINATORS);
1910 tsize = tree_size (build (PLUS_EXPR, void_type_node, NULL_TREE, NULL_TREE));
1911 binary_node_pool = create_alloc_pool ("Binary tree nodes", tsize, 30);
1912 tsize = tree_size (build1 (NEGATE_EXPR, void_type_node, NULL_TREE));
1913 unary_node_pool = create_alloc_pool ("Unary tree nodes", tsize, 30);
1917 EXP_GEN (bb) = set_new (true);
1918 PHI_GEN (bb) = bitmap_set_new ();
1919 TMP_GEN (bb) = bitmap_set_new ();
1920 AVAIL_OUT (bb) = bitmap_set_new ();
1925 /* Deallocate data structures used by PRE. */
1932 free_alloc_pool (value_set_pool);
1933 free_alloc_pool (bitmap_set_pool);
1934 free_alloc_pool (value_set_node_pool);
1935 free_alloc_pool (binary_node_pool);
1936 free_alloc_pool (unary_node_pool);
1937 htab_delete (phi_translate_table);
1944 free_dominance_info (CDI_POST_DOMINATORS);
1949 /* Main entry point to the SSA-PRE pass. DO_FRE is true if the caller
1950 only wants to do full redundancy elimination. */
1953 execute_pre (bool do_fre)
1957 /* Collect and value number expressions computed in each basic
1959 compute_avail (ENTRY_BLOCK_PTR);
1961 if (dump_file && (dump_flags & TDF_DETAILS))
1967 print_value_set (dump_file, EXP_GEN (bb), "exp_gen", bb->index);
1968 bitmap_print_value_set (dump_file, TMP_GEN (bb), "tmp_gen",
1970 bitmap_print_value_set (dump_file, AVAIL_OUT (bb), "avail_out",
1975 /* Insert can get quite slow on an incredibly large number of basic
1976 blocks due to some quadratic behavior. Until this behavior is
1977 fixed, don't run it when he have an incredibly large number of
1978 bb's. If we aren't going to run insert, there is no point in
1979 computing ANTIC, either, even though it's plenty fast. */
1980 if (!do_fre && n_basic_blocks < 4000)
1986 /* Remove all the redundant expressions. */
1989 if (dump_file && (dump_flags & TDF_STATS))
1991 fprintf (dump_file, "Insertions:%d\n", pre_stats.insertions);
1992 fprintf (dump_file, "New PHIs:%d\n", pre_stats.phis);
1993 fprintf (dump_file, "Eliminated:%d\n", pre_stats.eliminations);
2000 /* Gate and execute functions for PRE. */
2005 execute_pre (false);
2011 return flag_tree_pre != 0;
2014 struct tree_opt_pass pass_pre =
2017 gate_pre, /* gate */
2018 do_pre, /* execute */
2021 0, /* static_pass_number */
2022 TV_TREE_PRE, /* tv_id */
2023 PROP_no_crit_edges | PROP_cfg | PROP_ssa,/* properties_required */
2024 0, /* properties_provided */
2025 0, /* properties_destroyed */
2026 0, /* todo_flags_start */
2027 TODO_dump_func | TODO_ggc_collect | TODO_verify_ssa /* todo_flags_finish */
2031 /* Gate and execute functions for FRE. */
2042 return flag_tree_fre != 0;
2045 struct tree_opt_pass pass_fre =
2048 gate_fre, /* gate */
2049 do_fre, /* execute */
2052 0, /* static_pass_number */
2053 TV_TREE_FRE, /* tv_id */
2054 PROP_no_crit_edges | PROP_cfg | PROP_ssa,/* properties_required */
2055 0, /* properties_provided */
2056 0, /* properties_destroyed */
2057 0, /* todo_flags_start */
2058 TODO_dump_func | TODO_ggc_collect | TODO_verify_ssa /* todo_flags_finish */