2 Copyright (C) 2001, 2002, 2003, 2004, 2005 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"
45 #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. We can do back-substitution or smarter value numbering to catch
60 commutative expressions split up over multiple statements.
63 /* For ease of terminology, "expression node" in the below refers to
64 every expression node but MODIFY_EXPR, because MODIFY_EXPR's represent
65 the actual statement containing the expressions we care about, and
66 we cache the value number by putting it in the expression. */
70 First we walk the statements to generate the AVAIL sets, the
71 EXP_GEN sets, and the tmp_gen sets. EXP_GEN sets represent the
72 generation of values/expressions by a given block. We use them
73 when computing the ANTIC sets. The AVAIL sets consist of
74 SSA_NAME's that represent values, so we know what values are
75 available in what blocks. AVAIL is a forward dataflow problem. In
76 SSA, values are never killed, so we don't need a kill set, or a
77 fixpoint iteration, in order to calculate the AVAIL sets. In
78 traditional parlance, AVAIL sets tell us the downsafety of the
81 Next, we generate the ANTIC sets. These sets represent the
82 anticipatable expressions. ANTIC is a backwards dataflow
83 problem.An expression is anticipatable in a given block if it could
84 be generated in that block. This means that if we had to perform
85 an insertion in that block, of the value of that expression, we
86 could. Calculating the ANTIC sets requires phi translation of
87 expressions, because the flow goes backwards through phis. We must
88 iterate to a fixpoint of the ANTIC sets, because we have a kill
89 set. Even in SSA form, values are not live over the entire
90 function, only from their definition point onwards. So we have to
91 remove values from the ANTIC set once we go past the definition
92 point of the leaders that make them up.
93 compute_antic/compute_antic_aux performs this computation.
95 Third, we perform insertions to make partially redundant
96 expressions fully redundant.
98 An expression is partially redundant (excluding partial
101 1. It is AVAIL in some, but not all, of the predecessors of a
103 2. It is ANTIC in all the predecessors.
105 In order to make it fully redundant, we insert the expression into
106 the predecessors where it is not available, but is ANTIC.
107 insert/insert_aux performs this insertion.
109 Fourth, we eliminate fully redundant expressions.
110 This is a simple statement walk that replaces redundant
111 calculations with the now available values. */
113 /* Representations of value numbers:
115 Value numbers are represented using the "value handle" approach.
116 This means that each SSA_NAME (and for other reasons to be
117 disclosed in a moment, expression nodes) has a value handle that
118 can be retrieved through get_value_handle. This value handle, *is*
119 the value number of the SSA_NAME. You can pointer compare the
120 value handles for equivalence purposes.
122 For debugging reasons, the value handle is internally more than
123 just a number, it is a VAR_DECL named "value.x", where x is a
124 unique number for each value number in use. This allows
125 expressions with SSA_NAMES replaced by value handles to still be
126 pretty printed in a sane way. They simply print as "value.3 *
129 Expression nodes have value handles associated with them as a
130 cache. Otherwise, we'd have to look them up again in the hash
131 table This makes significant difference (factor of two or more) on
132 some test cases. They can be thrown away after the pass is
135 /* Representation of expressions on value numbers:
137 In some portions of this code, you will notice we allocate "fake"
138 analogues to the expression we are value numbering, and replace the
139 operands with the values of the expression. Since we work on
140 values, and not just names, we canonicalize expressions to value
141 expressions for use in the ANTIC sets, the EXP_GEN set, etc.
143 This is theoretically unnecessary, it just saves a bunch of
144 repeated get_value_handle and find_leader calls in the remainder of
145 the code, trading off temporary memory usage for speed. The tree
146 nodes aren't actually creating more garbage, since they are
147 allocated in a special pools which are thrown away at the end of
150 All of this also means that if you print the EXP_GEN or ANTIC sets,
151 you will see "value.5 + value.7" in the set, instead of "a_55 +
152 b_66" or something. The only thing that actually cares about
153 seeing the value leaders is phi translation, and it needs to be
154 able to find the leader for a value in an arbitrary block, so this
155 "value expression" form is perfect for it (otherwise you'd do
156 get_value_handle->find_leader->translate->get_value_handle->find_leader).*/
159 /* Representation of sets:
161 There are currently two types of sets used, hopefully to be unified soon.
162 The AVAIL sets do not need to be sorted in any particular order,
163 and thus, are simply represented as two bitmaps, one that keeps
164 track of values present in the set, and one that keeps track of
165 expressions present in the set.
167 The other 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 values or
170 expressions. The elements can appear in different sets, but each
171 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/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. */
222 /* An unordered bitmap set. One bitmap tracks values, the other,
224 typedef struct bitmap_set
230 /* Sets that we need to keep track of. */
231 typedef struct bb_value_sets
233 /* The EXP_GEN set, which represents expressions/values generated in
237 /* The PHI_GEN set, which represents PHI results generated in a
239 bitmap_set_t phi_gen;
241 /* The TMP_GEN set, which represents results/temporaries generated
242 in a basic block. IE the LHS of an expression. */
243 bitmap_set_t tmp_gen;
245 /* The AVAIL_OUT set, which represents which values are available in
246 a given basic block. */
247 bitmap_set_t avail_out;
249 /* The ANTIC_IN set, which represents which values are anticiptable
250 in a given basic block. */
251 value_set_t antic_in;
253 /* The NEW_SETS set, which is used during insertion to augment the
254 AVAIL_OUT set of blocks with the new insertions performed during
255 the current iteration. */
256 bitmap_set_t new_sets;
259 #define EXP_GEN(BB) ((bb_value_sets_t) ((BB)->aux))->exp_gen
260 #define PHI_GEN(BB) ((bb_value_sets_t) ((BB)->aux))->phi_gen
261 #define TMP_GEN(BB) ((bb_value_sets_t) ((BB)->aux))->tmp_gen
262 #define AVAIL_OUT(BB) ((bb_value_sets_t) ((BB)->aux))->avail_out
263 #define ANTIC_IN(BB) ((bb_value_sets_t) ((BB)->aux))->antic_in
264 #define NEW_SETS(BB) ((bb_value_sets_t) ((BB)->aux))->new_sets
266 /* This structure is used to keep track of statistics on what
267 optimization PRE was able to perform. */
270 /* The number of RHS computations eliminated by PRE. */
273 /* The number of new expressions/temporaries generated by PRE. */
276 /* The number of new PHI nodes added by PRE. */
279 /* The number of values found constant. */
285 static tree bitmap_find_leader (bitmap_set_t, tree);
286 static tree find_leader (value_set_t, tree);
287 static void value_insert_into_set (value_set_t, tree);
288 static void bitmap_value_insert_into_set (bitmap_set_t, tree);
289 static void bitmap_value_replace_in_set (bitmap_set_t, tree);
290 static void insert_into_set (value_set_t, tree);
291 static void bitmap_set_copy (bitmap_set_t, bitmap_set_t);
292 static bool bitmap_set_contains_value (bitmap_set_t, tree);
293 static bitmap_set_t bitmap_set_new (void);
294 static value_set_t set_new (bool);
295 static bool is_undefined_value (tree);
296 static tree create_expression_by_pieces (basic_block, tree, tree);
299 /* We can add and remove elements and entries to and from sets
300 and hash tables, so we use alloc pools for them. */
302 static alloc_pool value_set_pool;
303 static alloc_pool bitmap_set_pool;
304 static alloc_pool value_set_node_pool;
305 static alloc_pool binary_node_pool;
306 static alloc_pool unary_node_pool;
307 static alloc_pool reference_node_pool;
308 static alloc_pool comparison_node_pool;
309 static alloc_pool expression_node_pool;
310 static alloc_pool list_node_pool;
311 static bitmap_obstack grand_bitmap_obstack;
313 /* Set of blocks with statements that have had its EH information
315 static bitmap need_eh_cleanup;
317 /* The phi_translate_table caches phi translations for a given
318 expression and predecessor. */
320 static htab_t phi_translate_table;
322 /* A three tuple {e, pred, v} used to cache phi translations in the
323 phi_translate_table. */
325 typedef struct expr_pred_trans_d
327 /* The expression. */
330 /* The predecessor block along which we translated the expression. */
333 /* The value that resulted from the translation. */
336 /* The hashcode for the expression, pred pair. This is cached for
339 } *expr_pred_trans_t;
341 /* Return the hash value for a phi translation table entry. */
344 expr_pred_trans_hash (const void *p)
346 const expr_pred_trans_t ve = (expr_pred_trans_t) p;
350 /* Return true if two phi translation table entries are the same.
351 P1 and P2 should point to the expr_pred_trans_t's to be compared.*/
354 expr_pred_trans_eq (const void *p1, const void *p2)
356 const expr_pred_trans_t ve1 = (expr_pred_trans_t) p1;
357 const expr_pred_trans_t ve2 = (expr_pred_trans_t) p2;
358 basic_block b1 = ve1->pred;
359 basic_block b2 = ve2->pred;
362 /* If they are not translations for the same basic block, they can't
367 /* If they are for the same basic block, determine if the
368 expressions are equal. */
369 if (expressions_equal_p (ve1->e, ve2->e))
375 /* Search in the phi translation table for the translation of
376 expression E in basic block PRED. Return the translated value, if
377 found, NULL otherwise. */
380 phi_trans_lookup (tree e, basic_block pred)
383 struct expr_pred_trans_d ept;
386 ept.hashcode = vn_compute (e, (unsigned long) pred, NULL);
387 slot = htab_find_slot_with_hash (phi_translate_table, &ept, ept.hashcode,
392 return ((expr_pred_trans_t) *slot)->v;
396 /* Add the tuple mapping from {expression E, basic block PRED} to
397 value V, to the phi translation table. */
400 phi_trans_add (tree e, tree v, basic_block pred)
403 expr_pred_trans_t new_pair = xmalloc (sizeof (*new_pair));
405 new_pair->pred = pred;
407 new_pair->hashcode = vn_compute (e, (unsigned long) pred, NULL);
408 slot = htab_find_slot_with_hash (phi_translate_table, new_pair,
409 new_pair->hashcode, INSERT);
412 *slot = (void *) new_pair;
416 /* Add expression E to the expression set of value V. */
419 add_to_value (tree v, tree e)
421 /* Constants have no expression sets. */
422 if (is_gimple_min_invariant (v))
425 if (VALUE_HANDLE_EXPR_SET (v) == NULL)
426 VALUE_HANDLE_EXPR_SET (v) = set_new (false);
428 insert_into_set (VALUE_HANDLE_EXPR_SET (v), e);
432 /* Return true if value V exists in the bitmap for SET. */
435 value_exists_in_set_bitmap (value_set_t set, tree v)
440 return bitmap_bit_p (set->values, VALUE_HANDLE_ID (v));
444 /* Remove value V from the bitmap for SET. */
447 value_remove_from_set_bitmap (value_set_t set, tree v)
449 gcc_assert (set->indexed);
454 bitmap_clear_bit (set->values, VALUE_HANDLE_ID (v));
458 /* Insert the value number V into the bitmap of values existing in
462 value_insert_into_set_bitmap (value_set_t set, tree v)
464 gcc_assert (set->indexed);
466 if (set->values == NULL)
467 set->values = BITMAP_ALLOC (&grand_bitmap_obstack);
469 bitmap_set_bit (set->values, VALUE_HANDLE_ID (v));
473 /* Create a new bitmap set and return it. */
476 bitmap_set_new (void)
478 bitmap_set_t ret = pool_alloc (bitmap_set_pool);
479 ret->expressions = BITMAP_ALLOC (&grand_bitmap_obstack);
480 ret->values = BITMAP_ALLOC (&grand_bitmap_obstack);
484 /* Create a new set. */
487 set_new (bool indexed)
490 ret = pool_alloc (value_set_pool);
491 ret->head = ret->tail = NULL;
493 ret->indexed = indexed;
498 /* Insert an expression EXPR into a bitmapped set. */
501 bitmap_insert_into_set (bitmap_set_t set, tree expr)
504 /* XXX: For now, we only let SSA_NAMES into the bitmap sets. */
505 gcc_assert (TREE_CODE (expr) == SSA_NAME);
506 val = get_value_handle (expr);
509 if (!is_gimple_min_invariant (val))
511 bitmap_set_bit (set->values, VALUE_HANDLE_ID (val));
512 bitmap_set_bit (set->expressions, SSA_NAME_VERSION (expr));
516 /* Insert EXPR into SET. */
519 insert_into_set (value_set_t set, tree expr)
521 value_set_node_t newnode = pool_alloc (value_set_node_pool);
522 tree val = get_value_handle (expr);
525 if (is_gimple_min_invariant (val))
528 /* For indexed sets, insert the value into the set value bitmap.
529 For all sets, add it to the linked list and increment the list
532 value_insert_into_set_bitmap (set, val);
534 newnode->next = NULL;
535 newnode->expr = expr;
537 if (set->head == NULL)
539 set->head = set->tail = newnode;
543 set->tail->next = newnode;
548 /* Copy a bitmapped set ORIG, into bitmapped set DEST. */
551 bitmap_set_copy (bitmap_set_t dest, bitmap_set_t orig)
553 bitmap_copy (dest->expressions, orig->expressions);
554 bitmap_copy (dest->values, orig->values);
557 /* Copy the set ORIG to the set DEST. */
560 set_copy (value_set_t dest, value_set_t orig)
562 value_set_node_t node;
564 if (!orig || !orig->head)
567 for (node = orig->head;
571 insert_into_set (dest, node->expr);
575 /* Remove EXPR from SET. */
578 set_remove (value_set_t set, tree expr)
580 value_set_node_t node, prev;
582 /* Remove the value of EXPR from the bitmap, decrement the set
583 length, and remove it from the actual double linked list. */
584 value_remove_from_set_bitmap (set, get_value_handle (expr));
587 for (node = set->head;
589 prev = node, node = node->next)
591 if (node->expr == expr)
594 set->head = node->next;
596 prev->next= node->next;
598 if (node == set->tail)
600 pool_free (value_set_node_pool, node);
606 /* Return true if SET contains the value VAL. */
609 set_contains_value (value_set_t set, tree val)
611 /* All constants are in every set. */
612 if (is_gimple_min_invariant (val))
615 if (set->length == 0)
618 return value_exists_in_set_bitmap (set, val);
621 /* Return true if bitmapped set SET contains the expression EXPR. */
623 bitmap_set_contains (bitmap_set_t set, tree expr)
625 /* All constants are in every set. */
626 if (is_gimple_min_invariant (get_value_handle (expr)))
629 /* XXX: Bitmapped sets only contain SSA_NAME's for now. */
630 if (TREE_CODE (expr) != SSA_NAME)
632 return bitmap_bit_p (set->expressions, SSA_NAME_VERSION (expr));
636 /* Return true if bitmapped set SET contains the value VAL. */
639 bitmap_set_contains_value (bitmap_set_t set, tree val)
641 if (is_gimple_min_invariant (val))
643 return bitmap_bit_p (set->values, VALUE_HANDLE_ID (val));
646 /* Replace an instance of value LOOKFOR with expression EXPR in SET. */
649 bitmap_set_replace_value (bitmap_set_t set, tree lookfor, tree expr)
652 value_set_node_t node;
653 if (is_gimple_min_invariant (lookfor))
655 if (!bitmap_set_contains_value (set, lookfor))
658 /* The number of expressions having a given value is usually
659 significantly less than the total number of expressions in SET.
660 Thus, rather than check, for each expression in SET, whether it
661 has the value LOOKFOR, we walk the reverse mapping that tells us
662 what expressions have a given value, and see if any of those
663 expressions are in our set. For large testcases, this is about
664 5-10x faster than walking the bitmap. If this is somehow a
665 significant lose for some cases, we can choose which set to walk
666 based on the set size. */
667 exprset = VALUE_HANDLE_EXPR_SET (lookfor);
668 for (node = exprset->head; node; node = node->next)
670 if (TREE_CODE (node->expr) == SSA_NAME)
672 if (bitmap_bit_p (set->expressions, SSA_NAME_VERSION (node->expr)))
674 bitmap_clear_bit (set->expressions, SSA_NAME_VERSION (node->expr));
675 bitmap_set_bit (set->expressions, SSA_NAME_VERSION (expr));
682 /* Subtract bitmapped set B from value set A, and return the new set. */
685 bitmap_set_subtract_from_value_set (value_set_t a, bitmap_set_t b,
688 value_set_t ret = set_new (indexed);
689 value_set_node_t node;
694 if (!bitmap_set_contains (b, node->expr))
695 insert_into_set (ret, node->expr);
700 /* Return true if two sets are equal. */
703 set_equal (value_set_t a, value_set_t b)
705 value_set_node_t node;
707 if (a->length != b->length)
713 if (!set_contains_value (b, get_value_handle (node->expr)))
719 /* Replace an instance of EXPR's VALUE with EXPR in SET if it exists,
720 and add it otherwise. */
723 bitmap_value_replace_in_set (bitmap_set_t set, tree expr)
725 tree val = get_value_handle (expr);
726 if (bitmap_set_contains_value (set, val))
727 bitmap_set_replace_value (set, val, expr);
729 bitmap_insert_into_set (set, expr);
732 /* Insert EXPR into SET if EXPR's value is not already present in
736 bitmap_value_insert_into_set (bitmap_set_t set, tree expr)
738 tree val = get_value_handle (expr);
740 if (is_gimple_min_invariant (val))
743 if (!bitmap_set_contains_value (set, val))
744 bitmap_insert_into_set (set, expr);
747 /* Insert the value for EXPR into SET, if it doesn't exist already. */
750 value_insert_into_set (value_set_t set, tree expr)
752 tree val = get_value_handle (expr);
754 /* Constant and invariant values exist everywhere, and thus,
755 actually keeping them in the sets is pointless. */
756 if (is_gimple_min_invariant (val))
759 if (!set_contains_value (set, val))
760 insert_into_set (set, expr);
764 /* Print out SET to OUTFILE. */
767 bitmap_print_value_set (FILE *outfile, bitmap_set_t set,
768 const char *setname, int blockindex)
770 fprintf (outfile, "%s[%d] := { ", setname, blockindex);
777 EXECUTE_IF_SET_IN_BITMAP (set->expressions, 0, i, bi)
780 fprintf (outfile, ", ");
782 print_generic_expr (outfile, ssa_name (i), 0);
784 fprintf (outfile, " (");
785 print_generic_expr (outfile, get_value_handle (ssa_name (i)), 0);
786 fprintf (outfile, ") ");
789 fprintf (outfile, " }\n");
791 /* Print out the value_set SET to OUTFILE. */
794 print_value_set (FILE *outfile, value_set_t set,
795 const char *setname, int blockindex)
797 value_set_node_t node;
798 fprintf (outfile, "%s[%d] := { ", setname, blockindex);
801 for (node = set->head;
805 print_generic_expr (outfile, node->expr, 0);
807 fprintf (outfile, " (");
808 print_generic_expr (outfile, get_value_handle (node->expr), 0);
809 fprintf (outfile, ") ");
812 fprintf (outfile, ", ");
816 fprintf (outfile, " }\n");
819 /* Print out the expressions that have VAL to OUTFILE. */
822 print_value_expressions (FILE *outfile, tree val)
824 if (VALUE_HANDLE_EXPR_SET (val))
827 sprintf (s, "VH.%04d", VALUE_HANDLE_ID (val));
828 print_value_set (outfile, VALUE_HANDLE_EXPR_SET (val), s, 0);
834 debug_value_expressions (tree val)
836 print_value_expressions (stderr, val);
840 void debug_value_set (value_set_t, const char *, int);
843 debug_value_set (value_set_t set, const char *setname, int blockindex)
845 print_value_set (stderr, set, setname, blockindex);
848 /* Return the folded version of T if T, when folded, is a gimple
849 min_invariant. Otherwise, return T. */
852 fully_constant_expression (tree t)
856 if (folded && is_gimple_min_invariant (folded))
861 /* Return a copy of a chain of nodes, chained through the TREE_CHAIN field.
862 For example, this can copy a list made of TREE_LIST nodes.
863 Allocates the nodes in list_node_pool*/
866 pool_copy_list (tree list)
873 head = pool_alloc (list_node_pool);
875 memcpy (head, list, tree_size (list));
878 next = TREE_CHAIN (list);
881 TREE_CHAIN (prev) = pool_alloc (list_node_pool);
882 memcpy (TREE_CHAIN (prev), next, tree_size (next));
883 prev = TREE_CHAIN (prev);
884 next = TREE_CHAIN (next);
890 /* Translate EXPR using phis in PHIBLOCK, so that it has the values of
891 the phis in PRED. Return NULL if we can't find a leader for each
892 part of the translated expression. */
895 phi_translate (tree expr, value_set_t set, basic_block pred,
896 basic_block phiblock)
898 tree phitrans = NULL;
904 if (is_gimple_min_invariant (expr))
907 /* Phi translations of a given expression don't change. */
908 phitrans = phi_trans_lookup (expr, pred);
912 switch (TREE_CODE_CLASS (TREE_CODE (expr)))
916 if (TREE_CODE (expr) != CALL_EXPR)
920 tree oldop0 = TREE_OPERAND (expr, 0);
921 tree oldarglist = TREE_OPERAND (expr, 1);
922 tree oldop2 = TREE_OPERAND (expr, 2);
929 bool listchanged = false;
931 /* Call expressions are kind of weird because they have an
932 argument list. We don't want to value number the list
933 as one value number, because that doesn't make much
934 sense, and just breaks the support functions we call,
935 which expect TREE_OPERAND (call_expr, 2) to be a
938 newop0 = phi_translate (find_leader (set, oldop0),
939 set, pred, phiblock);
944 newop2 = phi_translate (find_leader (set, oldop2),
945 set, pred, phiblock);
950 /* phi translate the argument list piece by piece.
952 We could actually build the list piece by piece here,
953 but it's likely to not be worth the memory we will save,
954 unless you have millions of call arguments. */
956 newarglist = pool_copy_list (oldarglist);
957 for (oldwalker = oldarglist, newwalker = newarglist;
958 oldwalker && newwalker;
959 oldwalker = TREE_CHAIN (oldwalker),
960 newwalker = TREE_CHAIN (newwalker))
963 tree oldval = TREE_VALUE (oldwalker);
967 newval = phi_translate (find_leader (set, oldval),
968 set, pred, phiblock);
971 if (newval != oldval)
974 TREE_VALUE (newwalker) = get_value_handle (newval);
979 vn_lookup_or_add (newarglist, NULL);
981 if (listchanged || (newop0 != oldop0) || (oldop2 != newop2))
983 newexpr = pool_alloc (expression_node_pool);
984 memcpy (newexpr, expr, tree_size (expr));
985 TREE_OPERAND (newexpr, 0) = newop0 == oldop0 ? oldop0 : get_value_handle (newop0);
986 TREE_OPERAND (newexpr, 1) = listchanged ? newarglist : oldarglist;
987 TREE_OPERAND (newexpr, 2) = newop2 == oldop2 ? oldop2 : get_value_handle (newop2);
988 create_tree_ann (newexpr);
989 vn_lookup_or_add (newexpr, NULL);
991 phi_trans_add (oldexpr, newexpr, pred);
998 /* XXX: Until we have PRE of loads working, none will be ANTIC. */
1002 case tcc_comparison:
1004 tree oldop1 = TREE_OPERAND (expr, 0);
1005 tree oldop2 = TREE_OPERAND (expr, 1);
1010 newop1 = phi_translate (find_leader (set, oldop1),
1011 set, pred, phiblock);
1014 newop2 = phi_translate (find_leader (set, oldop2),
1015 set, pred, phiblock);
1018 if (newop1 != oldop1 || newop2 != oldop2)
1021 newexpr = pool_alloc (binary_node_pool);
1022 memcpy (newexpr, expr, tree_size (expr));
1023 TREE_OPERAND (newexpr, 0) = newop1 == oldop1 ? oldop1 : get_value_handle (newop1);
1024 TREE_OPERAND (newexpr, 1) = newop2 == oldop2 ? oldop2 : get_value_handle (newop2);
1025 t = fully_constant_expression (newexpr);
1028 pool_free (binary_node_pool, newexpr);
1033 create_tree_ann (newexpr);
1034 vn_lookup_or_add (newexpr, NULL);
1037 phi_trans_add (oldexpr, newexpr, pred);
1044 tree oldop1 = TREE_OPERAND (expr, 0);
1048 newop1 = phi_translate (find_leader (set, oldop1),
1049 set, pred, phiblock);
1052 if (newop1 != oldop1)
1055 newexpr = pool_alloc (unary_node_pool);
1056 memcpy (newexpr, expr, tree_size (expr));
1057 TREE_OPERAND (newexpr, 0) = get_value_handle (newop1);
1058 t = fully_constant_expression (newexpr);
1061 pool_free (unary_node_pool, newexpr);
1066 create_tree_ann (newexpr);
1067 vn_lookup_or_add (newexpr, NULL);
1070 phi_trans_add (oldexpr, newexpr, pred);
1075 case tcc_exceptional:
1079 gcc_assert (TREE_CODE (expr) == SSA_NAME);
1080 if (TREE_CODE (SSA_NAME_DEF_STMT (expr)) == PHI_NODE)
1081 phi = SSA_NAME_DEF_STMT (expr);
1085 e = find_edge (pred, bb_for_stmt (phi));
1088 if (is_undefined_value (PHI_ARG_DEF (phi, e->dest_idx)))
1090 vn_lookup_or_add (PHI_ARG_DEF (phi, e->dest_idx), NULL);
1091 return PHI_ARG_DEF (phi, e->dest_idx);
1101 /* For each expression in SET, translate the value handles through phi nodes
1102 in PHIBLOCK using edge PHIBLOCK->PRED, and store the resulting
1103 expressions in DEST. */
1106 phi_translate_set (value_set_t dest, value_set_t set, basic_block pred,
1107 basic_block phiblock)
1109 value_set_node_t node;
1110 for (node = set->head;
1115 translated = phi_translate (node->expr, set, pred, phiblock);
1116 phi_trans_add (node->expr, translated, pred);
1118 if (translated != NULL)
1119 value_insert_into_set (dest, translated);
1123 /* Find the leader for a value (i.e., the name representing that
1124 value) in a given set, and return it. Return NULL if no leader is
1128 bitmap_find_leader (bitmap_set_t set, tree val)
1133 if (is_gimple_min_invariant (val))
1135 if (bitmap_set_contains_value (set, val))
1137 /* Rather than walk the entire bitmap of expressions, and see
1138 whether any of them has the value we are looking for, we look
1139 at the reverse mapping, which tells us the set of expressions
1140 that have a given value (IE value->expressions with that
1141 value) and see if any of those expressions are in our set.
1142 The number of expressions per value is usually significantly
1143 less than the number of expressions in the set. In fact, for
1144 large testcases, doing it this way is roughly 5-10x faster
1145 than walking the bitmap.
1146 If this is somehow a significant lose for some cases, we can
1147 choose which set to walk based on which set is smaller. */
1148 value_set_t exprset;
1149 value_set_node_t node;
1150 exprset = VALUE_HANDLE_EXPR_SET (val);
1151 for (node = exprset->head; node; node = node->next)
1153 if (TREE_CODE (node->expr) == SSA_NAME)
1155 if (bitmap_bit_p (set->expressions,
1156 SSA_NAME_VERSION (node->expr)))
1165 /* Find the leader for a value (i.e., the name representing that
1166 value) in a given set, and return it. Return NULL if no leader is
1170 find_leader (value_set_t set, tree val)
1172 value_set_node_t node;
1177 /* Constants represent themselves. */
1178 if (is_gimple_min_invariant (val))
1181 if (set->length == 0)
1184 if (value_exists_in_set_bitmap (set, val))
1186 for (node = set->head;
1190 if (get_value_handle (node->expr) == val)
1198 /* Determine if the expression EXPR is valid in SET. This means that
1199 we have a leader for each part of the expression (if it consists of
1200 values), or the expression is an SSA_NAME.
1202 NB: We never should run into a case where we have SSA_NAME +
1203 SSA_NAME or SSA_NAME + value. The sets valid_in_set is called on,
1204 the ANTIC sets, will only ever have SSA_NAME's or value expressions
1205 (IE VALUE1 + VALUE2, *VALUE1, VALUE1 < VALUE2) */
1208 valid_in_set (value_set_t set, tree expr)
1210 switch (TREE_CODE_CLASS (TREE_CODE (expr)))
1213 case tcc_comparison:
1215 tree op1 = TREE_OPERAND (expr, 0);
1216 tree op2 = TREE_OPERAND (expr, 1);
1217 return set_contains_value (set, op1) && set_contains_value (set, op2);
1222 tree op1 = TREE_OPERAND (expr, 0);
1223 return set_contains_value (set, op1);
1226 case tcc_expression:
1228 if (TREE_CODE (expr) == CALL_EXPR)
1230 tree op0 = TREE_OPERAND (expr, 0);
1231 tree arglist = TREE_OPERAND (expr, 1);
1232 tree op2 = TREE_OPERAND (expr, 2);
1234 /* Check the non-list operands first. */
1235 if (!set_contains_value (set, op0)
1236 || (op2 && !set_contains_value (set, op2)))
1239 /* Now check the operands. */
1240 for (; arglist; arglist = TREE_CHAIN (arglist))
1242 if (!set_contains_value (set, TREE_VALUE (arglist)))
1251 /* XXX: Until PRE of loads works, no reference nodes are ANTIC. */
1254 case tcc_exceptional:
1255 gcc_assert (TREE_CODE (expr) == SSA_NAME);
1258 case tcc_declaration:
1259 /* VAR_DECL and PARM_DECL are never anticipatable. */
1263 /* No other cases should be encountered. */
1268 /* Clean the set of expressions that are no longer valid in SET. This
1269 means expressions that are made up of values we have no leaders for
1273 clean (value_set_t set)
1275 value_set_node_t node;
1276 value_set_node_t next;
1281 if (!valid_in_set (set, node->expr))
1282 set_remove (set, node->expr);
1287 DEF_VEC_P (basic_block);
1288 DEF_VEC_ALLOC_P (basic_block, heap);
1289 static sbitmap has_abnormal_preds;
1291 /* Compute the ANTIC set for BLOCK.
1293 If succs(BLOCK) > 1 then
1294 ANTIC_OUT[BLOCK] = intersection of ANTIC_IN[b] for all succ(BLOCK)
1295 else if succs(BLOCK) == 1 then
1296 ANTIC_OUT[BLOCK] = phi_translate (ANTIC_IN[succ(BLOCK)])
1298 ANTIC_IN[BLOCK] = clean(ANTIC_OUT[BLOCK] U EXP_GEN[BLOCK] - TMP_GEN[BLOCK])
1300 XXX: It would be nice to either write a set_clear, and use it for
1301 ANTIC_OUT, or to mark the antic_out set as deleted at the end
1302 of this routine, so that the pool can hand the same memory back out
1303 again for the next ANTIC_OUT. */
1306 compute_antic_aux (basic_block block, bool block_has_abnormal_pred_edge)
1309 bool changed = false;
1310 value_set_t S, old, ANTIC_OUT;
1311 value_set_node_t node;
1313 ANTIC_OUT = S = NULL;
1315 /* If any edges from predecessors are abnormal, antic_in is empty,
1317 if (block_has_abnormal_pred_edge)
1318 goto maybe_dump_sets;
1320 old = set_new (false);
1321 set_copy (old, ANTIC_IN (block));
1322 ANTIC_OUT = set_new (true);
1324 /* If the block has no successors, ANTIC_OUT is empty. */
1325 if (EDGE_COUNT (block->succs) == 0)
1327 /* If we have one successor, we could have some phi nodes to
1328 translate through. */
1329 else if (single_succ_p (block))
1331 phi_translate_set (ANTIC_OUT, ANTIC_IN (single_succ (block)),
1332 block, single_succ (block));
1334 /* If we have multiple successors, we take the intersection of all of
1338 VEC(basic_block, heap) * worklist;
1341 basic_block bprime, first;
1344 worklist = VEC_alloc (basic_block, heap, EDGE_COUNT (block->succs));
1345 FOR_EACH_EDGE (e, ei, block->succs)
1346 VEC_quick_push (basic_block, worklist, e->dest);
1347 first = VEC_index (basic_block, worklist, 0);
1348 set_copy (ANTIC_OUT, ANTIC_IN (first));
1350 for (i = 1; VEC_iterate (basic_block, worklist, i, bprime); i++)
1352 node = ANTIC_OUT->head;
1356 value_set_node_t next = node->next;
1357 val = get_value_handle (node->expr);
1358 if (!set_contains_value (ANTIC_IN (bprime), val))
1359 set_remove (ANTIC_OUT, node->expr);
1363 VEC_free (basic_block, heap, worklist);
1366 /* Generate ANTIC_OUT - TMP_GEN. */
1367 S = bitmap_set_subtract_from_value_set (ANTIC_OUT, TMP_GEN (block), false);
1369 /* Start ANTIC_IN with EXP_GEN - TMP_GEN */
1370 ANTIC_IN (block) = bitmap_set_subtract_from_value_set (EXP_GEN (block),
1374 /* Then union in the ANTIC_OUT - TMP_GEN values,
1375 to get ANTIC_OUT U EXP_GEN - TMP_GEN */
1376 for (node = S->head; node; node = node->next)
1377 value_insert_into_set (ANTIC_IN (block), node->expr);
1379 clean (ANTIC_IN (block));
1380 if (!set_equal (old, ANTIC_IN (block)))
1384 if (dump_file && (dump_flags & TDF_DETAILS))
1387 print_value_set (dump_file, ANTIC_OUT, "ANTIC_OUT", block->index);
1388 print_value_set (dump_file, ANTIC_IN (block), "ANTIC_IN", block->index);
1390 print_value_set (dump_file, S, "S", block->index);
1393 for (son = first_dom_son (CDI_POST_DOMINATORS, block);
1395 son = next_dom_son (CDI_POST_DOMINATORS, son))
1397 changed |= compute_antic_aux (son,
1398 TEST_BIT (has_abnormal_preds, son->index));
1403 /* Compute ANTIC sets. */
1406 compute_antic (void)
1408 bool changed = true;
1409 int num_iterations = 0;
1412 /* If any predecessor edges are abnormal, we punt, so antic_in is empty.
1413 We pre-build the map of blocks with incoming abnormal edges here. */
1414 has_abnormal_preds = sbitmap_alloc (last_basic_block);
1415 sbitmap_zero (has_abnormal_preds);
1421 FOR_EACH_EDGE (e, ei, block->preds)
1422 if (e->flags & EDGE_ABNORMAL)
1424 SET_BIT (has_abnormal_preds, block->index);
1428 /* While we are here, give empty ANTIC_IN sets to each block. */
1429 ANTIC_IN (block) = set_new (true);
1431 /* At the exit block we anticipate nothing. */
1432 ANTIC_IN (EXIT_BLOCK_PTR) = set_new (true);
1438 changed = compute_antic_aux (EXIT_BLOCK_PTR, false);
1441 sbitmap_free (has_abnormal_preds);
1443 if (dump_file && (dump_flags & TDF_STATS))
1444 fprintf (dump_file, "compute_antic required %d iterations\n", num_iterations);
1447 static VEC(tree,heap) *inserted_exprs;
1448 /* Find a leader for an expression, or generate one using
1449 create_expression_by_pieces if it's ANTIC but
1451 BLOCK is the basic_block we are looking for leaders in.
1452 EXPR is the expression to find a leader or generate for.
1453 STMTS is the statement list to put the inserted expressions on.
1454 Returns the SSA_NAME of the LHS of the generated expression or the
1458 find_or_generate_expression (basic_block block, tree expr, tree stmts)
1460 tree genop = bitmap_find_leader (AVAIL_OUT (block), expr);
1462 /* If it's still NULL, it must be a complex expression, so generate
1466 genop = VALUE_HANDLE_EXPR_SET (expr)->head->expr;
1467 gcc_assert (UNARY_CLASS_P (genop)
1468 || BINARY_CLASS_P (genop)
1469 || COMPARISON_CLASS_P (genop)
1470 || REFERENCE_CLASS_P (genop));
1471 genop = create_expression_by_pieces (block, genop, stmts);
1476 #define NECESSARY(stmt) stmt->common.asm_written_flag
1477 /* Create an expression in pieces, so that we can handle very complex
1478 expressions that may be ANTIC, but not necessary GIMPLE.
1479 BLOCK is the basic block the expression will be inserted into,
1480 EXPR is the expression to insert (in value form)
1481 STMTS is a statement list to append the necessary insertions into.
1483 This function will die if we hit some value that shouldn't be
1484 ANTIC but is (IE there is no leader for it, or its components).
1485 This function may also generate expressions that are themselves
1486 partially or fully redundant. Those that are will be either made
1487 fully redundant during the next iteration of insert (for partially
1488 redundant ones), or eliminated by eliminate (for fully redundant
1492 create_expression_by_pieces (basic_block block, tree expr, tree stmts)
1495 tree folded, forced_stmts, newexpr;
1497 tree_stmt_iterator tsi;
1499 switch (TREE_CODE_CLASS (TREE_CODE (expr)))
1501 case tcc_expression:
1505 tree genop0, genop2;
1507 tree walker, genwalker;
1509 gcc_assert (TREE_CODE (expr) == CALL_EXPR);
1512 op0 = TREE_OPERAND (expr, 0);
1513 arglist = TREE_OPERAND (expr, 1);
1514 op2 = TREE_OPERAND (expr, 2);
1516 genop0 = find_or_generate_expression (block, op0, stmts);
1517 genarglist = copy_list (arglist);
1518 for (walker = arglist, genwalker = genarglist;
1519 genwalker && walker;
1520 genwalker = TREE_CHAIN (genwalker), walker = TREE_CHAIN (walker))
1522 TREE_VALUE (genwalker) = find_or_generate_expression (block,
1523 TREE_VALUE (walker),
1528 genop2 = find_or_generate_expression (block, op2, stmts);
1529 folded = fold (build (TREE_CODE (expr), TREE_TYPE (expr),
1530 genop0, genarglist, genop2));
1538 case tcc_comparison:
1540 tree op1 = TREE_OPERAND (expr, 0);
1541 tree op2 = TREE_OPERAND (expr, 1);
1542 tree genop1 = find_or_generate_expression (block, op1, stmts);
1543 tree genop2 = find_or_generate_expression (block, op2, stmts);
1544 folded = fold (build (TREE_CODE (expr), TREE_TYPE (expr),
1551 tree op1 = TREE_OPERAND (expr, 0);
1552 tree genop1 = find_or_generate_expression (block, op1, stmts);
1553 folded = fold (build (TREE_CODE (expr), TREE_TYPE (expr),
1562 /* Force the generated expression to be a sequence of GIMPLE
1564 We have to call unshare_expr because force_gimple_operand may
1565 modify the tree we pass to it. */
1566 newexpr = force_gimple_operand (unshare_expr (folded), &forced_stmts,
1569 /* If we have any intermediate expressions to the value sets, add them
1570 to the value sets and chain them on in the instruction stream. */
1573 tsi = tsi_start (forced_stmts);
1574 for (; !tsi_end_p (tsi); tsi_next (&tsi))
1576 tree stmt = tsi_stmt (tsi);
1577 tree forcedname = TREE_OPERAND (stmt, 0);
1578 tree forcedexpr = TREE_OPERAND (stmt, 1);
1579 tree val = vn_lookup_or_add (forcedexpr, NULL);
1581 VEC_safe_push (tree, heap, inserted_exprs, stmt);
1582 vn_add (forcedname, val, NULL);
1583 bitmap_value_replace_in_set (NEW_SETS (block), forcedname);
1584 bitmap_value_replace_in_set (AVAIL_OUT (block), forcedname);
1586 tsi = tsi_last (stmts);
1587 tsi_link_after (&tsi, forced_stmts, TSI_CONTINUE_LINKING);
1590 /* Build and insert the assignment of the end result to the temporary
1591 that we will return. */
1592 temp = create_tmp_var (TREE_TYPE (expr), "pretmp");
1593 add_referenced_tmp_var (temp);
1594 newexpr = build (MODIFY_EXPR, TREE_TYPE (expr), temp, newexpr);
1595 name = make_ssa_name (temp, newexpr);
1596 TREE_OPERAND (newexpr, 0) = name;
1597 NECESSARY (newexpr) = 0;
1598 tsi = tsi_last (stmts);
1599 tsi_link_after (&tsi, newexpr, TSI_CONTINUE_LINKING);
1600 VEC_safe_push (tree, heap, inserted_exprs, newexpr);
1602 /* Add a value handle to the temporary.
1603 The value may already exist in either NEW_SETS, or AVAIL_OUT, because
1604 we are creating the expression by pieces, and this particular piece of
1605 the expression may have been represented. There is no harm in replacing
1607 v = get_value_handle (expr);
1608 vn_add (name, v, NULL);
1609 bitmap_value_replace_in_set (NEW_SETS (block), name);
1610 bitmap_value_replace_in_set (AVAIL_OUT (block), name);
1612 pre_stats.insertions++;
1613 if (dump_file && (dump_flags & TDF_DETAILS))
1615 fprintf (dump_file, "Inserted ");
1616 print_generic_expr (dump_file, newexpr, 0);
1617 fprintf (dump_file, " in predecessor %d\n", block->index);
1623 /* Insert the to-be-made-available values of NODE for each predecessor, stored
1624 in AVAIL, into the predecessors of BLOCK, and merge the result with a phi
1625 node, given the same value handle as NODE. The prefix of the phi node is
1626 given with TMPNAME. Return true if we have inserted new stuff. */
1629 insert_into_preds_of_block (basic_block block, value_set_node_t node,
1630 tree *avail, const char *tmpname)
1632 tree val = get_value_handle (node->expr);
1634 bool insertions = false;
1639 tree type = TREE_TYPE (avail[EDGE_PRED (block, 0)->src->index]);
1642 if (dump_file && (dump_flags & TDF_DETAILS))
1644 fprintf (dump_file, "Found partial redundancy for expression ");
1645 print_generic_expr (dump_file, node->expr, 0);
1646 fprintf (dump_file, "\n");
1649 /* Make sure we aren't creating an induction variable. */
1650 if (block->loop_depth > 0 && EDGE_COUNT (block->preds) == 2)
1652 bool firstinsideloop = false;
1653 bool secondinsideloop = false;
1654 firstinsideloop = flow_bb_inside_loop_p (block->loop_father,
1655 EDGE_PRED (block, 0)->src);
1656 secondinsideloop = flow_bb_inside_loop_p (block->loop_father,
1657 EDGE_PRED (block, 1)->src);
1658 /* Induction variables only have one edge inside the loop. */
1659 if (firstinsideloop ^ secondinsideloop)
1661 if (dump_file && (dump_flags & TDF_DETAILS))
1662 fprintf (dump_file, "Skipping insertion of phi for partial redundancy: Looks like an induction variable\n");
1668 /* Make the necessary insertions. */
1669 FOR_EACH_EDGE (pred, ei, block->preds)
1671 tree stmts = alloc_stmt_list ();
1674 eprime = avail[bprime->index];
1675 if (BINARY_CLASS_P (eprime)
1676 || COMPARISON_CLASS_P (eprime)
1677 || UNARY_CLASS_P (eprime)
1678 || TREE_CODE (eprime) == CALL_EXPR)
1680 builtexpr = create_expression_by_pieces (bprime,
1683 bsi_insert_on_edge (pred, stmts);
1684 avail[bprime->index] = builtexpr;
1688 /* If we didn't want a phi node, and we made insertions, we still have
1689 inserted new stuff, and thus return true. If we didn't want a phi node,
1690 and didn't make insertions, we haven't added anything new, so return
1692 if (nophi && insertions)
1694 else if (nophi && !insertions)
1697 /* Now build a phi for the new variable. */
1698 temp = create_tmp_var (type, tmpname);
1699 add_referenced_tmp_var (temp);
1700 temp = create_phi_node (temp, block);
1701 NECESSARY (temp) = 0;
1702 VEC_safe_push (tree, heap, inserted_exprs, temp);
1703 FOR_EACH_EDGE (pred, ei, block->preds)
1704 add_phi_arg (temp, avail[pred->src->index], pred);
1706 vn_add (PHI_RESULT (temp), val, NULL);
1708 /* The value should *not* exist in PHI_GEN, or else we wouldn't be doing
1709 this insertion, since we test for the existence of this value in PHI_GEN
1710 before proceeding with the partial redundancy checks in insert_aux.
1712 The value may exist in AVAIL_OUT, in particular, it could be represented
1713 by the expression we are trying to eliminate, in which case we want the
1714 replacement to occur. If it's not existing in AVAIL_OUT, we want it
1717 Similarly, to the PHI_GEN case, the value should not exist in NEW_SETS of
1718 this block, because if it did, it would have existed in our dominator's
1719 AVAIL_OUT, and would have been skipped due to the full redundancy check.
1722 bitmap_insert_into_set (PHI_GEN (block),
1724 bitmap_value_replace_in_set (AVAIL_OUT (block),
1726 bitmap_insert_into_set (NEW_SETS (block),
1729 if (dump_file && (dump_flags & TDF_DETAILS))
1731 fprintf (dump_file, "Created phi ");
1732 print_generic_expr (dump_file, temp, 0);
1733 fprintf (dump_file, " in block %d\n", block->index);
1741 /* Perform insertion of partially redundant values.
1742 For BLOCK, do the following:
1743 1. Propagate the NEW_SETS of the dominator into the current block.
1744 If the block has multiple predecessors,
1745 2a. Iterate over the ANTIC expressions for the block to see if
1746 any of them are partially redundant.
1747 2b. If so, insert them into the necessary predecessors to make
1748 the expression fully redundant.
1749 2c. Insert a new PHI merging the values of the predecessors.
1750 2d. Insert the new PHI, and the new expressions, into the
1752 3. Recursively call ourselves on the dominator children of BLOCK.
1757 insert_aux (basic_block block)
1760 bool new_stuff = false;
1765 dom = get_immediate_dominator (CDI_DOMINATORS, block);
1770 bitmap_set_t newset = NEW_SETS (dom);
1773 /* Note that we need to value_replace both NEW_SETS, and
1774 AVAIL_OUT. For both the case of NEW_SETS, the value may be
1775 represented by some non-simple expression here that we want
1776 to replace it with. */
1777 EXECUTE_IF_SET_IN_BITMAP (newset->expressions, 0, i, bi)
1779 bitmap_value_replace_in_set (NEW_SETS (block), ssa_name (i));
1780 bitmap_value_replace_in_set (AVAIL_OUT (block), ssa_name (i));
1783 if (!single_pred_p (block))
1785 value_set_node_t node;
1786 for (node = ANTIC_IN (block)->head;
1790 if (BINARY_CLASS_P (node->expr)
1791 || COMPARISON_CLASS_P (node->expr)
1792 || UNARY_CLASS_P (node->expr)
1793 || TREE_CODE (node->expr) == CALL_EXPR)
1797 bool by_some = false;
1798 bool cant_insert = false;
1799 bool all_same = true;
1800 tree first_s = NULL;
1803 tree eprime = NULL_TREE;
1806 val = get_value_handle (node->expr);
1807 if (bitmap_set_contains_value (PHI_GEN (block), val))
1809 if (bitmap_set_contains_value (AVAIL_OUT (dom), val))
1811 if (dump_file && (dump_flags & TDF_DETAILS))
1812 fprintf (dump_file, "Found fully redundant value\n");
1816 avail = xcalloc (last_basic_block, sizeof (tree));
1817 FOR_EACH_EDGE (pred, ei, block->preds)
1822 /* This can happen in the very weird case
1823 that our fake infinite loop edges have caused a
1824 critical edge to appear. */
1825 if (EDGE_CRITICAL_P (pred))
1831 eprime = phi_translate (node->expr,
1835 /* eprime will generally only be NULL if the
1836 value of the expression, translated
1837 through the PHI for this predecessor, is
1838 undefined. If that is the case, we can't
1839 make the expression fully redundant,
1840 because its value is undefined along a
1841 predecessor path. We can thus break out
1842 early because it doesn't matter what the
1843 rest of the results are. */
1850 eprime = fully_constant_expression (eprime);
1851 vprime = get_value_handle (eprime);
1852 gcc_assert (vprime);
1853 edoubleprime = bitmap_find_leader (AVAIL_OUT (bprime),
1855 if (edoubleprime == NULL)
1857 avail[bprime->index] = eprime;
1862 avail[bprime->index] = edoubleprime;
1864 if (first_s == NULL)
1865 first_s = edoubleprime;
1866 else if (!operand_equal_p (first_s, edoubleprime,
1871 /* If we can insert it, it's not the same value
1872 already existing along every predecessor, and
1873 it's defined by some predecessor, it is
1874 partially redundant. */
1875 if (!cant_insert && !all_same && by_some)
1877 if (insert_into_preds_of_block (block, node, avail,
1881 /* If all edges produce the same value and that value is
1882 an invariant, then the PHI has the same value on all
1883 edges. Note this. */
1884 else if (!cant_insert && all_same && eprime
1885 && is_gimple_min_invariant (eprime)
1886 && !is_gimple_min_invariant (val))
1888 value_set_t exprset = VALUE_HANDLE_EXPR_SET (val);
1889 value_set_node_t node;
1890 for (node = exprset->head; node; node = node->next)
1892 if (TREE_CODE (node->expr) == SSA_NAME)
1894 vn_add (node->expr, eprime, NULL);
1895 pre_stats.constified++;
1905 for (son = first_dom_son (CDI_DOMINATORS, block);
1907 son = next_dom_son (CDI_DOMINATORS, son))
1909 new_stuff |= insert_aux (son);
1915 /* Perform insertion of partially redundant values. */
1920 bool new_stuff = true;
1922 int num_iterations = 0;
1925 NEW_SETS (bb) = bitmap_set_new ();
1931 new_stuff = insert_aux (ENTRY_BLOCK_PTR);
1933 if (num_iterations > 2 && dump_file && (dump_flags & TDF_STATS))
1934 fprintf (dump_file, "insert required %d iterations\n", num_iterations);
1938 /* Return true if VAR is an SSA variable with no defining statement in
1939 this procedure, *AND* isn't a live-on-entry parameter. */
1942 is_undefined_value (tree expr)
1944 return (TREE_CODE (expr) == SSA_NAME
1945 && IS_EMPTY_STMT (SSA_NAME_DEF_STMT (expr))
1946 /* PARM_DECLs and hard registers are always defined. */
1947 && TREE_CODE (SSA_NAME_VAR (expr)) != PARM_DECL);
1951 /* Given an SSA variable VAR and an expression EXPR, compute the value
1952 number for EXPR and create a value handle (VAL) for it. If VAR and
1953 EXPR are not the same, associate VAL with VAR. Finally, add VAR to
1954 S1 and its value handle to S2.
1956 VUSES represent the virtual use operands associated with EXPR (if
1957 any). They are used when computing the hash value for EXPR. */
1960 add_to_sets (tree var, tree expr, tree stmt, bitmap_set_t s1,
1963 tree val = vn_lookup_or_add (expr, stmt);
1965 /* VAR and EXPR may be the same when processing statements for which
1966 we are not computing value numbers (e.g., non-assignments, or
1967 statements that make aliased stores). In those cases, we are
1968 only interested in making VAR available as its own value. */
1970 vn_add (var, val, NULL_TREE);
1973 bitmap_insert_into_set (s1, var);
1974 bitmap_value_insert_into_set (s2, var);
1978 /* Given a unary or binary expression EXPR, create and return a new
1979 expression with the same structure as EXPR but with its operands
1980 replaced with the value handles of each of the operands of EXPR.
1982 VUSES represent the virtual use operands associated with EXPR (if
1983 any). They are used when computing the hash value for EXPR.
1984 Insert EXPR's operands into the EXP_GEN set for BLOCK. */
1987 create_value_expr_from (tree expr, basic_block block, tree stmt)
1990 enum tree_code code = TREE_CODE (expr);
1994 gcc_assert (TREE_CODE_CLASS (code) == tcc_unary
1995 || TREE_CODE_CLASS (code) == tcc_binary
1996 || TREE_CODE_CLASS (code) == tcc_comparison
1997 || TREE_CODE_CLASS (code) == tcc_reference
1998 || TREE_CODE_CLASS (code) == tcc_expression
1999 || TREE_CODE_CLASS (code) == tcc_exceptional);
2001 if (TREE_CODE_CLASS (code) == tcc_unary)
2002 pool = unary_node_pool;
2003 else if (TREE_CODE_CLASS (code) == tcc_reference)
2004 pool = reference_node_pool;
2005 else if (TREE_CODE_CLASS (code) == tcc_binary)
2006 pool = binary_node_pool;
2007 else if (TREE_CODE_CLASS (code) == tcc_comparison)
2008 pool = comparison_node_pool;
2009 else if (TREE_CODE_CLASS (code) == tcc_exceptional)
2011 gcc_assert (code == TREE_LIST);
2012 pool = list_node_pool;
2016 gcc_assert (code == CALL_EXPR);
2017 pool = expression_node_pool;
2020 vexpr = pool_alloc (pool);
2021 memcpy (vexpr, expr, tree_size (expr));
2023 /* This case is only for TREE_LIST's that appear as part of
2024 CALL_EXPR's. Anything else is a bug, but we can't easily verify
2025 this, hence this comment. TREE_LIST is not handled by the
2026 general case below is because they don't have a fixed length, or
2027 operands, so you can't access purpose/value/chain through
2028 TREE_OPERAND macros. */
2030 if (code == TREE_LIST)
2032 tree temp = NULL_TREE;
2033 if (TREE_CHAIN (vexpr))
2034 temp = create_value_expr_from (TREE_CHAIN (vexpr), block, stmt);
2035 TREE_CHAIN (vexpr) = temp ? temp : TREE_CHAIN (vexpr);
2037 /* This is the equivalent of inserting op into EXP_GEN like we
2039 if (!is_undefined_value (TREE_VALUE (vexpr)))
2040 value_insert_into_set (EXP_GEN (block), TREE_VALUE (vexpr));
2042 TREE_VALUE (vexpr) = vn_lookup_or_add (TREE_VALUE (vexpr), NULL);
2047 for (i = 0; i < TREE_CODE_LENGTH (code); i++)
2051 op = TREE_OPERAND (expr, i);
2052 if (op == NULL_TREE)
2055 /* If OP is a constant that has overflowed, do not value number
2057 if (CONSTANT_CLASS_P (op)
2058 && TREE_OVERFLOW (op))
2060 pool_free (pool, vexpr);
2064 /* Recursively value-numberize reference ops and tree lists. */
2065 if (REFERENCE_CLASS_P (op))
2067 tree tempop = create_value_expr_from (op, block, stmt);
2068 op = tempop ? tempop : op;
2069 val = vn_lookup_or_add (op, stmt);
2071 else if (TREE_CODE (op) == TREE_LIST)
2075 gcc_assert (TREE_CODE (expr) == CALL_EXPR);
2076 tempop = create_value_expr_from (op, block, stmt);
2078 op = tempop ? tempop : op;
2079 vn_lookup_or_add (op, NULL);
2080 /* Unlike everywhere else, we do *not* want to replace the
2081 TREE_LIST itself with a value number, because support
2082 functions we call will blow up. */
2086 /* Create a value handle for OP and add it to VEXPR. */
2087 val = vn_lookup_or_add (op, NULL);
2089 if (!is_undefined_value (op) && TREE_CODE (op) != TREE_LIST)
2090 value_insert_into_set (EXP_GEN (block), op);
2092 if (TREE_CODE (val) == VALUE_HANDLE)
2093 TREE_TYPE (val) = TREE_TYPE (TREE_OPERAND (vexpr, i));
2095 TREE_OPERAND (vexpr, i) = val;
2102 /* Return true if we can value number a call. This is true if we have
2103 a pure or constant call. */
2105 can_value_number_call (tree stmt)
2107 tree call = get_call_expr_in (stmt);
2109 /* This is a temporary restriction until we translate vuses through
2111 if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS))
2113 if (call_expr_flags (call) & (ECF_PURE | ECF_CONST))
2118 /* Compute the AVAIL set for all basic blocks.
2120 This function performs value numbering of the statements in each basic
2121 block. The AVAIL sets are built from information we glean while doing
2122 this value numbering, since the AVAIL sets contain only one entry per
2125 AVAIL_IN[BLOCK] = AVAIL_OUT[dom(BLOCK)].
2126 AVAIL_OUT[BLOCK] = AVAIL_IN[BLOCK] U PHI_GEN[BLOCK] U TMP_GEN[BLOCK]. */
2129 compute_avail (void)
2131 basic_block block, son;
2132 basic_block *worklist;
2136 /* For arguments with default definitions, we pretend they are
2137 defined in the entry block. */
2138 for (param = DECL_ARGUMENTS (current_function_decl);
2140 param = TREE_CHAIN (param))
2142 if (default_def (param) != NULL)
2144 tree def = default_def (param);
2145 vn_lookup_or_add (def, NULL);
2146 bitmap_insert_into_set (TMP_GEN (ENTRY_BLOCK_PTR), def);
2147 bitmap_value_insert_into_set (AVAIL_OUT (ENTRY_BLOCK_PTR), def);
2151 /* Allocate the worklist. */
2152 worklist = xmalloc (sizeof (basic_block) * n_basic_blocks);
2154 /* Seed the algorithm by putting the dominator children of the entry
2155 block on the worklist. */
2156 for (son = first_dom_son (CDI_DOMINATORS, ENTRY_BLOCK_PTR);
2158 son = next_dom_son (CDI_DOMINATORS, son))
2159 worklist[sp++] = son;
2161 /* Loop until the worklist is empty. */
2164 block_stmt_iterator bsi;
2168 /* Pick a block from the worklist. */
2169 block = worklist[--sp];
2171 /* Initially, the set of available values in BLOCK is that of
2172 its immediate dominator. */
2173 dom = get_immediate_dominator (CDI_DOMINATORS, block);
2175 bitmap_set_copy (AVAIL_OUT (block), AVAIL_OUT (dom));
2177 /* Generate values for PHI nodes. */
2178 for (phi = phi_nodes (block); phi; phi = PHI_CHAIN (phi))
2179 /* We have no need for virtual phis, as they don't represent
2180 actual computations. */
2181 if (is_gimple_reg (PHI_RESULT (phi)))
2182 add_to_sets (PHI_RESULT (phi), PHI_RESULT (phi), NULL,
2183 PHI_GEN (block), AVAIL_OUT (block));
2185 /* Now compute value numbers and populate value sets with all
2186 the expressions computed in BLOCK. */
2187 for (bsi = bsi_start (block); !bsi_end_p (bsi); bsi_next (&bsi))
2193 stmt = bsi_stmt (bsi);
2194 ann = stmt_ann (stmt);
2196 /* We are only interested in assignments of the form
2197 X_i = EXPR, where EXPR represents an "interesting"
2198 computation, it has no volatile operands and X_i
2199 doesn't flow through an abnormal edge. */
2200 if (TREE_CODE (stmt) == MODIFY_EXPR
2201 && !ann->has_volatile_ops
2202 && TREE_CODE (TREE_OPERAND (stmt, 0)) == SSA_NAME
2203 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (TREE_OPERAND (stmt, 0)))
2205 tree lhs = TREE_OPERAND (stmt, 0);
2206 tree rhs = TREE_OPERAND (stmt, 1);
2208 STRIP_USELESS_TYPE_CONVERSION (rhs);
2209 if (UNARY_CLASS_P (rhs)
2210 || BINARY_CLASS_P (rhs)
2211 || COMPARISON_CLASS_P (rhs)
2212 || REFERENCE_CLASS_P (rhs)
2213 || (TREE_CODE (rhs) == CALL_EXPR
2214 && can_value_number_call (stmt)))
2216 /* For binary, unary, and reference expressions,
2217 create a duplicate expression with the operands
2218 replaced with the value handles of the original
2220 tree newt = create_value_expr_from (rhs, block, stmt);
2223 add_to_sets (lhs, newt, stmt, TMP_GEN (block),
2225 value_insert_into_set (EXP_GEN (block), newt);
2229 else if (TREE_CODE (rhs) == SSA_NAME
2230 || is_gimple_min_invariant (rhs)
2231 || TREE_CODE (rhs) == ADDR_EXPR
2232 || TREE_INVARIANT (rhs)
2235 /* Compute a value number for the RHS of the statement
2236 and add its value to the AVAIL_OUT set for the block.
2237 Add the LHS to TMP_GEN. */
2238 add_to_sets (lhs, rhs, stmt, TMP_GEN (block),
2241 if (TREE_CODE (rhs) == SSA_NAME
2242 && !is_undefined_value (rhs))
2243 value_insert_into_set (EXP_GEN (block), rhs);
2248 /* For any other statement that we don't recognize, simply
2249 make the names generated by the statement available in
2250 AVAIL_OUT and TMP_GEN. */
2251 FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_DEF)
2252 add_to_sets (op, op, NULL, TMP_GEN (block), AVAIL_OUT (block));
2254 FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_USE)
2255 add_to_sets (op, op, NULL, NULL , AVAIL_OUT (block));
2258 /* Put the dominator children of BLOCK on the worklist of blocks
2259 to compute available sets for. */
2260 for (son = first_dom_son (CDI_DOMINATORS, block);
2262 son = next_dom_son (CDI_DOMINATORS, son))
2263 worklist[sp++] = son;
2270 /* Eliminate fully redundant computations. */
2279 block_stmt_iterator i;
2281 for (i = bsi_start (b); !bsi_end_p (i); bsi_next (&i))
2283 tree stmt = bsi_stmt (i);
2285 /* Lookup the RHS of the expression, see if we have an
2286 available computation for it. If so, replace the RHS with
2287 the available computation. */
2288 if (TREE_CODE (stmt) == MODIFY_EXPR
2289 && TREE_CODE (TREE_OPERAND (stmt, 0)) == SSA_NAME
2290 && TREE_CODE (TREE_OPERAND (stmt ,1)) != SSA_NAME
2291 && !is_gimple_min_invariant (TREE_OPERAND (stmt, 1))
2292 && !stmt_ann (stmt)->has_volatile_ops)
2294 tree lhs = TREE_OPERAND (stmt, 0);
2295 tree *rhs_p = &TREE_OPERAND (stmt, 1);
2298 sprime = bitmap_find_leader (AVAIL_OUT (b),
2299 vn_lookup (lhs, NULL));
2302 && (TREE_CODE (*rhs_p) != SSA_NAME
2303 || may_propagate_copy (*rhs_p, sprime)))
2305 gcc_assert (sprime != *rhs_p);
2307 if (dump_file && (dump_flags & TDF_DETAILS))
2309 fprintf (dump_file, "Replaced ");
2310 print_generic_expr (dump_file, *rhs_p, 0);
2311 fprintf (dump_file, " with ");
2312 print_generic_expr (dump_file, sprime, 0);
2313 fprintf (dump_file, " in ");
2314 print_generic_stmt (dump_file, stmt, 0);
2316 if (TREE_CODE (sprime) == SSA_NAME)
2317 NECESSARY (SSA_NAME_DEF_STMT (sprime)) = 1;
2318 pre_stats.eliminations++;
2319 propagate_tree_value (rhs_p, sprime);
2322 /* If we removed EH side effects from the statement, clean
2323 its EH information. */
2324 if (maybe_clean_eh_stmt (stmt))
2326 bitmap_set_bit (need_eh_cleanup,
2327 bb_for_stmt (stmt)->index);
2328 if (dump_file && (dump_flags & TDF_DETAILS))
2329 fprintf (dump_file, " Removed EH side effects.\n");
2337 /* Borrow a bit of tree-ssa-dce.c for the moment.
2338 XXX: In 4.1, we should be able to just run a DCE pass after PRE, though
2339 this may be a bit faster, and we may want critical edges kept split. */
2341 /* If OP's defining statement has not already been determined to be necessary,
2342 mark that statement necessary. Return the stmt, if it is newly
2346 mark_operand_necessary (tree op)
2352 stmt = SSA_NAME_DEF_STMT (op);
2355 if (NECESSARY (stmt)
2356 || IS_EMPTY_STMT (stmt))
2359 NECESSARY (stmt) = 1;
2363 /* Because we don't follow exactly the standard PRE algorithm, and decide not
2364 to insert PHI nodes sometimes, and because value numbering of casts isn't
2365 perfect, we sometimes end up inserting dead code. This simple DCE-like
2366 pass removes any insertions we made that weren't actually used. */
2369 remove_dead_inserted_code (void)
2371 VEC(tree,heap) *worklist = NULL;
2375 worklist = VEC_alloc (tree, heap, VEC_length (tree, inserted_exprs));
2376 for (i = 0; VEC_iterate (tree, inserted_exprs, i, t); i++)
2379 VEC_quick_push (tree, worklist, t);
2381 while (VEC_length (tree, worklist) > 0)
2383 t = VEC_pop (tree, worklist);
2384 if (TREE_CODE (t) == PHI_NODE)
2386 /* PHI nodes are somewhat special in that each PHI alternative has
2387 data and control dependencies. All the statements feeding the
2388 PHI node's arguments are always necessary. In aggressive mode,
2389 we also consider the control dependent edges leading to the
2390 predecessor block associated with each PHI alternative as
2394 VEC_reserve (tree, heap, worklist, PHI_NUM_ARGS (t));
2395 for (k = 0; k < PHI_NUM_ARGS (t); k++)
2397 tree arg = PHI_ARG_DEF (t, k);
2398 if (TREE_CODE (arg) == SSA_NAME)
2400 arg = mark_operand_necessary (arg);
2402 VEC_quick_push (tree, worklist, arg);
2408 /* Propagate through the operands. Examine all the USE, VUSE and
2409 V_MAY_DEF operands in this statement. Mark all the statements
2410 which feed this statement's uses as necessary. */
2414 /* The operands of V_MAY_DEF expressions are also needed as they
2415 represent potential definitions that may reach this
2416 statement (V_MAY_DEF operands allow us to follow def-def
2419 FOR_EACH_SSA_TREE_OPERAND (use, t, iter, SSA_OP_ALL_USES)
2421 tree n = mark_operand_necessary (use);
2423 VEC_safe_push (tree, heap, worklist, n);
2427 for (i = 0; VEC_iterate (tree, inserted_exprs, i, t); i++)
2431 block_stmt_iterator bsi;
2432 if (dump_file && (dump_flags & TDF_DETAILS))
2434 fprintf (dump_file, "Removing unnecessary insertion:");
2435 print_generic_stmt (dump_file, t, 0);
2437 if (TREE_CODE (t) == PHI_NODE)
2439 remove_phi_node (t, NULL);
2443 bsi = bsi_for_stmt (t);
2448 VEC_free (tree, heap, worklist);
2450 /* Initialize data structures used by PRE. */
2453 init_pre (bool do_fre)
2457 inserted_exprs = NULL;
2460 current_loops = loop_optimizer_init (dump_file);
2461 connect_infinite_loops_to_exit ();
2462 memset (&pre_stats, 0, sizeof (pre_stats));
2464 /* If block 0 has more than one predecessor, it means that its PHI
2465 nodes will have arguments coming from block -1. This creates
2466 problems for several places in PRE that keep local arrays indexed
2467 by block number. To prevent this, we split the edge coming from
2468 ENTRY_BLOCK_PTR (FIXME, if ENTRY_BLOCK_PTR had an index number
2469 different than -1 we wouldn't have to hack this. tree-ssa-dce.c
2470 needs a similar change). */
2471 if (!single_pred_p (single_succ (ENTRY_BLOCK_PTR)))
2472 if (!(single_succ_edge (ENTRY_BLOCK_PTR)->flags & EDGE_ABNORMAL))
2473 split_edge (single_succ_edge (ENTRY_BLOCK_PTR));
2476 bb->aux = xcalloc (1, sizeof (struct bb_value_sets));
2478 bitmap_obstack_initialize (&grand_bitmap_obstack);
2479 phi_translate_table = htab_create (511, expr_pred_trans_hash,
2480 expr_pred_trans_eq, free);
2481 value_set_pool = create_alloc_pool ("Value sets",
2482 sizeof (struct value_set), 30);
2483 bitmap_set_pool = create_alloc_pool ("Bitmap sets",
2484 sizeof (struct bitmap_set), 30);
2485 value_set_node_pool = create_alloc_pool ("Value set nodes",
2486 sizeof (struct value_set_node), 30);
2487 calculate_dominance_info (CDI_POST_DOMINATORS);
2488 calculate_dominance_info (CDI_DOMINATORS);
2489 binary_node_pool = create_alloc_pool ("Binary tree nodes",
2490 tree_code_size (PLUS_EXPR), 30);
2491 unary_node_pool = create_alloc_pool ("Unary tree nodes",
2492 tree_code_size (NEGATE_EXPR), 30);
2493 reference_node_pool = create_alloc_pool ("Reference tree nodes",
2494 tree_code_size (ARRAY_REF), 30);
2495 expression_node_pool = create_alloc_pool ("Expression tree nodes",
2496 tree_code_size (CALL_EXPR), 30);
2497 list_node_pool = create_alloc_pool ("List tree nodes",
2498 tree_code_size (TREE_LIST), 30);
2499 comparison_node_pool = create_alloc_pool ("Comparison tree nodes",
2500 tree_code_size (EQ_EXPR), 30);
2503 EXP_GEN (bb) = set_new (true);
2504 PHI_GEN (bb) = bitmap_set_new ();
2505 TMP_GEN (bb) = bitmap_set_new ();
2506 AVAIL_OUT (bb) = bitmap_set_new ();
2509 need_eh_cleanup = BITMAP_ALLOC (NULL);
2513 /* Deallocate data structures used by PRE. */
2516 fini_pre (bool do_fre)
2521 VEC_free (tree, heap, inserted_exprs);
2522 bitmap_obstack_release (&grand_bitmap_obstack);
2523 free_alloc_pool (value_set_pool);
2524 free_alloc_pool (bitmap_set_pool);
2525 free_alloc_pool (value_set_node_pool);
2526 free_alloc_pool (binary_node_pool);
2527 free_alloc_pool (reference_node_pool);
2528 free_alloc_pool (unary_node_pool);
2529 free_alloc_pool (list_node_pool);
2530 free_alloc_pool (expression_node_pool);
2531 free_alloc_pool (comparison_node_pool);
2532 htab_delete (phi_translate_table);
2533 remove_fake_exit_edges ();
2541 free_dominance_info (CDI_POST_DOMINATORS);
2544 if (!bitmap_empty_p (need_eh_cleanup))
2546 tree_purge_all_dead_eh_edges (need_eh_cleanup);
2547 cleanup_tree_cfg ();
2550 BITMAP_FREE (need_eh_cleanup);
2552 /* Wipe out pointers to VALUE_HANDLEs. In the not terribly distant
2553 future we will want them to be persistent though. */
2554 for (i = 0; i < num_ssa_names; i++)
2556 tree name = ssa_name (i);
2561 if (SSA_NAME_VALUE (name)
2562 && TREE_CODE (SSA_NAME_VALUE (name)) == VALUE_HANDLE)
2563 SSA_NAME_VALUE (name) = NULL;
2565 if (!do_fre && current_loops)
2567 loop_optimizer_finalize (current_loops, dump_file);
2568 current_loops = NULL;
2573 /* Main entry point to the SSA-PRE pass. DO_FRE is true if the caller
2574 only wants to do full redundancy elimination. */
2577 execute_pre (bool do_fre)
2581 /* Collect and value number expressions computed in each basic block. */
2584 if (dump_file && (dump_flags & TDF_DETAILS))
2590 print_value_set (dump_file, EXP_GEN (bb), "exp_gen", bb->index);
2591 bitmap_print_value_set (dump_file, TMP_GEN (bb), "tmp_gen",
2593 bitmap_print_value_set (dump_file, AVAIL_OUT (bb), "avail_out",
2598 /* Insert can get quite slow on an incredibly large number of basic
2599 blocks due to some quadratic behavior. Until this behavior is
2600 fixed, don't run it when he have an incredibly large number of
2601 bb's. If we aren't going to run insert, there is no point in
2602 computing ANTIC, either, even though it's plenty fast. */
2603 if (!do_fre && n_basic_blocks < 4000)
2609 /* Remove all the redundant expressions. */
2613 if (dump_file && (dump_flags & TDF_STATS))
2615 fprintf (dump_file, "Insertions: %d\n", pre_stats.insertions);
2616 fprintf (dump_file, "New PHIs: %d\n", pre_stats.phis);
2617 fprintf (dump_file, "Eliminated: %d\n", pre_stats.eliminations);
2618 fprintf (dump_file, "Constified: %d\n", pre_stats.constified);
2621 bsi_commit_edge_inserts ();
2623 remove_dead_inserted_code ();
2629 /* Gate and execute functions for PRE. */
2634 execute_pre (false);
2640 return flag_tree_pre != 0;
2643 struct tree_opt_pass pass_pre =
2646 gate_pre, /* gate */
2647 do_pre, /* execute */
2650 0, /* static_pass_number */
2651 TV_TREE_PRE, /* tv_id */
2652 PROP_no_crit_edges | PROP_cfg
2653 | PROP_ssa | PROP_alias, /* properties_required */
2654 0, /* properties_provided */
2655 0, /* properties_destroyed */
2656 0, /* todo_flags_start */
2657 TODO_update_ssa | TODO_dump_func | TODO_ggc_collect
2658 | TODO_verify_ssa, /* todo_flags_finish */
2663 /* Gate and execute functions for FRE. */
2674 return flag_tree_fre != 0;
2677 struct tree_opt_pass pass_fre =
2680 gate_fre, /* gate */
2681 execute_fre, /* execute */
2684 0, /* static_pass_number */
2685 TV_TREE_FRE, /* tv_id */
2686 PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */
2687 0, /* properties_provided */
2688 0, /* properties_destroyed */
2689 0, /* todo_flags_start */
2690 TODO_dump_func | TODO_ggc_collect | TODO_verify_ssa, /* todo_flags_finish */