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 /* All of the following sets, except for TMP_GEN, are indexed.
236 TMP_GEN is only ever iterated over, we never check what values
239 typedef struct bb_value_sets
241 /* The EXP_GEN set, which represents expressions/values generated in
245 /* The PHI_GEN set, which represents PHI results generated in a
249 /* The TMP_GEN set, which represents results/temporaries generated
250 in a basic block. IE the LHS of an expression. */
253 /* The AVAIL_OUT set, which represents which values are available in
254 a given basic block. */
255 bitmap_set_t avail_out;
257 /* The ANTIC_IN set, which represents which values are anticiptable
258 in a given basic block. */
259 value_set_t antic_in;
261 /* The NEW_SETS set, which is used during insertion to augment the
262 AVAIL_OUT set of blocks with the new insertions performed during
263 the current iteration. */
264 value_set_t new_sets;
267 #define EXP_GEN(BB) ((bb_value_sets_t) ((BB)->aux))->exp_gen
268 #define PHI_GEN(BB) ((bb_value_sets_t) ((BB)->aux))->phi_gen
269 #define TMP_GEN(BB) ((bb_value_sets_t) ((BB)->aux))->tmp_gen
270 #define AVAIL_OUT(BB) ((bb_value_sets_t) ((BB)->aux))->avail_out
271 #define ANTIC_IN(BB) ((bb_value_sets_t) ((BB)->aux))->antic_in
272 #define NEW_SETS(BB) ((bb_value_sets_t) ((BB)->aux))->new_sets
274 /* This structure is used to keep track of statistics on what
275 optimization PRE was able to perform. */
278 /* The number of RHS computations eliminated by PRE. */
281 /* The number of new expressions/temporaries generated by PRE. */
284 /* The number of new PHI nodes added by PRE. */
289 static tree bitmap_find_leader (bitmap_set_t, tree);
290 static tree find_leader (value_set_t, tree);
291 static void value_insert_into_set (value_set_t, tree);
292 static void bitmap_value_insert_into_set (bitmap_set_t, tree);
293 static void bitmap_value_replace_in_set (bitmap_set_t, tree);
294 static void insert_into_set (value_set_t, tree);
295 static void bitmap_set_copy (bitmap_set_t, bitmap_set_t);
296 static bool bitmap_set_contains_value (bitmap_set_t, tree);
297 static bitmap_set_t bitmap_set_new (void);
298 static value_set_t set_new (bool);
299 static bool is_undefined_value (tree);
300 static tree create_expression_by_pieces (basic_block, tree, tree);
303 /* We can add and remove elements and entries to and from sets
304 and hash tables, so we use alloc pools for them. */
306 static alloc_pool value_set_pool;
307 static alloc_pool bitmap_set_pool;
308 static alloc_pool value_set_node_pool;
309 static alloc_pool binary_node_pool;
310 static alloc_pool unary_node_pool;
312 /* The phi_translate_table caches phi translations for a given
313 expression and predecessor. */
315 static htab_t phi_translate_table;
317 /* A three tuple {e, pred, v} used to cache phi translations in the
318 phi_translate_table. */
320 typedef struct expr_pred_trans_d
322 /* The expression. */
325 /* The predecessor block along which we translated the expression. */
328 /* The value that resulted from the translation. */
331 /* The hashcode for the expression, pred pair. This is cached for
334 } *expr_pred_trans_t;
336 /* Return the hash value for a phi translation table entry. */
339 expr_pred_trans_hash (const void *p)
341 const expr_pred_trans_t ve = (expr_pred_trans_t) p;
345 /* Return true if two phi translation table entries are the same.
346 P1 and P2 should point to the expr_pred_trans_t's to be compared.*/
349 expr_pred_trans_eq (const void *p1, const void *p2)
351 const expr_pred_trans_t ve1 = (expr_pred_trans_t) p1;
352 const expr_pred_trans_t ve2 = (expr_pred_trans_t) p2;
353 basic_block b1 = ve1->pred;
354 basic_block b2 = ve2->pred;
357 /* If they are not translations for the same basic block, they can't
362 /* If they are for the same basic block, determine if the
363 expressions are equal. */
364 if (expressions_equal_p (ve1->e, ve2->e))
370 /* Search in the phi translation table for the translation of
371 expression E in basic block PRED. Return the translated value, if
372 found, NULL otherwise. */
375 phi_trans_lookup (tree e, basic_block pred)
378 struct expr_pred_trans_d ept;
381 ept.hashcode = vn_compute (e, (unsigned long) pred, NULL);
382 slot = htab_find_slot_with_hash (phi_translate_table, &ept, ept.hashcode,
387 return ((expr_pred_trans_t) *slot)->v;
391 /* Add the tuple mapping from {expression E, basic block PRED} to
392 value V, to the phi translation table. */
395 phi_trans_add (tree e, tree v, basic_block pred)
398 expr_pred_trans_t new_pair = xmalloc (sizeof (*new_pair));
400 new_pair->pred = pred;
402 new_pair->hashcode = vn_compute (e, (unsigned long) pred, NULL);
403 slot = htab_find_slot_with_hash (phi_translate_table, new_pair,
404 new_pair->hashcode, INSERT);
407 *slot = (void *) new_pair;
411 /* Add expression E to the expression set of value V. */
414 add_to_value (tree v, tree e)
416 /* Constants have no expression sets. */
417 if (is_gimple_min_invariant (v))
420 if (VALUE_HANDLE_EXPR_SET (v) == NULL)
421 VALUE_HANDLE_EXPR_SET (v) = set_new (false);
423 insert_into_set (VALUE_HANDLE_EXPR_SET (v), e);
427 /* Return true if value V exists in the bitmap for SET. */
430 value_exists_in_set_bitmap (value_set_t set, tree v)
435 return bitmap_bit_p (set->values, VALUE_HANDLE_ID (v));
439 /* Remove value V from the bitmap for SET. */
442 value_remove_from_set_bitmap (value_set_t set, tree v)
444 #ifdef ENABLE_CHECKING
452 bitmap_clear_bit (set->values, VALUE_HANDLE_ID (v));
456 /* Insert the value number V into the bitmap of values existing in
460 value_insert_into_set_bitmap (value_set_t set, tree v)
462 #ifdef ENABLE_CHECKING
467 if (set->values == NULL)
469 set->values = BITMAP_GGC_ALLOC ();
470 bitmap_clear (set->values);
473 bitmap_set_bit (set->values, VALUE_HANDLE_ID (v));
477 /* Create a new bitmap set and return it. */
480 bitmap_set_new (void)
482 bitmap_set_t ret = pool_alloc (bitmap_set_pool);
483 ret->expressions = BITMAP_GGC_ALLOC ();
484 ret->values = BITMAP_GGC_ALLOC ();
485 bitmap_clear (ret->expressions);
486 bitmap_clear (ret->values);
490 /* Create a new set. */
493 set_new (bool indexed)
496 ret = pool_alloc (value_set_pool);
497 ret->head = ret->tail = NULL;
499 ret->indexed = indexed;
504 /* Insert an expression, EXPR, into a bitmapped set. */
507 bitmap_insert_into_set (bitmap_set_t set, tree expr)
510 /* XXX: For now, we only let SSA_NAMES into the bitmap sets. */
511 if (TREE_CODE (expr) != SSA_NAME)
513 val = get_value_handle (expr);
518 bitmap_set_bit (set->values, VALUE_HANDLE_ID (val));
519 bitmap_set_bit (set->expressions, SSA_NAME_VERSION (expr));
522 /* Insert EXPR into SET. */
525 insert_into_set (value_set_t set, tree expr)
527 value_set_node_t newnode = pool_alloc (value_set_node_pool);
528 tree val = get_value_handle (expr);
533 /* For indexed sets, insert the value into the set value bitmap.
534 For all sets, add it to the linked list and increment the list
537 value_insert_into_set_bitmap (set, val);
539 newnode->next = NULL;
540 newnode->expr = expr;
542 if (set->head == NULL)
544 set->head = set->tail = newnode;
548 set->tail->next = newnode;
553 /* Copy a bitmapped set ORIG, into bitmapped set DEST. */
556 bitmap_set_copy (bitmap_set_t dest, bitmap_set_t orig)
558 bitmap_copy (dest->expressions, orig->expressions);
559 bitmap_copy (dest->values, orig->values);
562 /* Copy the set ORIG to the set DEST. */
565 set_copy (value_set_t dest, value_set_t orig)
567 value_set_node_t node;
569 if (!orig || !orig->head)
572 for (node = orig->head;
576 insert_into_set (dest, node->expr);
580 /* Remove EXPR from SET. */
583 set_remove (value_set_t set, tree expr)
585 value_set_node_t node, prev;
587 /* Remove the value of EXPR from the bitmap, decrement the set
588 length, and remove it from the actual double linked list. */
589 value_remove_from_set_bitmap (set, get_value_handle (expr));
592 for (node = set->head;
594 prev = node, node = node->next)
596 if (node->expr == expr)
599 set->head = node->next;
601 prev->next= node->next;
603 if (node == set->tail)
605 pool_free (value_set_node_pool, node);
611 /* Return true if SET contains the value VAL. */
614 set_contains_value (value_set_t set, tree val)
616 /* All constants are in every set. */
617 if (is_gimple_min_invariant (val))
620 if (set->length == 0)
623 return value_exists_in_set_bitmap (set, val);
626 /* Return true if bitmapped set SET contains the value VAL. */
629 bitmap_set_contains_value (bitmap_set_t set, tree val)
631 if (is_gimple_min_invariant (val))
633 return bitmap_bit_p (set->values, VALUE_HANDLE_ID (val));
636 /* Replace an instance of value LOOKFOR with expression EXPR in SET. */
639 bitmap_set_replace_value (bitmap_set_t set, tree lookfor, tree expr)
642 value_set_node_t node;
643 if (is_gimple_min_invariant (lookfor))
645 if (!bitmap_set_contains_value (set, lookfor))
647 exprset = VALUE_HANDLE_EXPR_SET (lookfor);
648 for (node = exprset->head; node; node = node->next)
650 if (TREE_CODE (node->expr) == SSA_NAME)
652 if (bitmap_bit_p (set->expressions, SSA_NAME_VERSION (node->expr)))
654 bitmap_clear_bit (set->expressions, SSA_NAME_VERSION (node->expr));
655 bitmap_set_bit (set->expressions, SSA_NAME_VERSION (expr));
662 /* Return true if the set contains expression (not value) EXPR. */
665 set_contains (value_set_t set, tree expr)
667 value_set_node_t node;
669 for (node = set->head;
673 if (operand_equal_p (node->expr, expr, 0))
679 /* Subtract set B from set A, and return the new set. */
682 set_subtract (value_set_t a, value_set_t b, bool indexed)
684 value_set_t ret = set_new (indexed);
685 value_set_node_t node;
690 if (!set_contains (b, node->expr))
691 insert_into_set (ret, node->expr);
696 /* Return true if two sets are equal. */
699 set_equal (value_set_t a, value_set_t b)
701 value_set_node_t node;
703 if (a->length != b->length)
709 if (!set_contains_value (b, get_value_handle (node->expr)))
715 /* Replace an instance of EXPR's VALUE with EXPR in SET. */
718 bitmap_value_replace_in_set (bitmap_set_t set, tree expr)
720 tree val = get_value_handle (expr);
721 bitmap_set_replace_value (set, val, expr);
724 /* Insert EXPR into SET if EXPR's value is not already present in
728 bitmap_value_insert_into_set (bitmap_set_t set, tree expr)
730 tree val = get_value_handle (expr);
731 if (is_gimple_min_invariant (val))
734 if (!bitmap_set_contains_value (set, val))
735 bitmap_insert_into_set (set, expr);
738 /* Insert the value for EXPR into SET, if it doesn't exist already. */
741 value_insert_into_set (value_set_t set, tree expr)
743 tree val = get_value_handle (expr);
745 /* Constant and invariant values exist everywhere, and thus,
746 actually keeping them in the sets is pointless. */
747 if (is_gimple_min_invariant (val))
750 if (!set_contains_value (set, val))
751 insert_into_set (set, expr);
755 /* Print out SET to OUTFILE. */
758 bitmap_print_value_set (FILE *outfile, bitmap_set_t set,
759 const char *setname, int blockindex)
761 fprintf (outfile, "%s[%d] := { ", setname, blockindex);
765 EXECUTE_IF_SET_IN_BITMAP (set->expressions, 0, i,
767 print_generic_expr (outfile, ssa_name (i), 0);
769 fprintf (outfile, " (");
770 print_generic_expr (outfile, get_value_handle (ssa_name (i)), 0);
771 fprintf (outfile, ") ");
772 if (bitmap_last_set_bit (set->expressions) != i)
773 fprintf (outfile, ", ");
776 fprintf (outfile, " }\n");
778 /* Print out the value_set SET to OUTFILE. */
781 print_value_set (FILE *outfile, value_set_t set,
782 const char *setname, int blockindex)
784 value_set_node_t node;
785 fprintf (outfile, "%s[%d] := { ", setname, blockindex);
788 for (node = set->head;
792 print_generic_expr (outfile, node->expr, 0);
794 fprintf (outfile, " (");
795 print_generic_expr (outfile, get_value_handle (node->expr), 0);
796 fprintf (outfile, ") ");
799 fprintf (outfile, ", ");
803 fprintf (outfile, " }\n");
806 /* Print out the expressions that have VAL to OUTFILE. */
809 print_value_expressions (FILE *outfile, tree val)
811 if (VALUE_HANDLE_EXPR_SET (val))
814 sprintf (s, "VH.%04d", VALUE_HANDLE_ID (val));
815 print_value_set (outfile, VALUE_HANDLE_EXPR_SET (val), s, 0);
821 debug_value_expressions (tree val)
823 print_value_expressions (stderr, val);
827 void debug_value_set (value_set_t, const char *, int);
830 debug_value_set (value_set_t set, const char *setname, int blockindex)
832 print_value_set (stderr, set, setname, blockindex);
835 /* Translate EXPR using phis in PHIBLOCK, so that it has the values of
836 the phis in PRED. Return NULL if we can't find a leader for each
837 part of the translated expression. */
840 phi_translate (tree expr, value_set_t set, basic_block pred,
841 basic_block phiblock)
843 tree phitrans = NULL;
849 /* Phi translations of a given expression don't change, */
850 phitrans = phi_trans_lookup (expr, pred);
855 switch (TREE_CODE_CLASS (TREE_CODE (expr)))
859 tree oldop1 = TREE_OPERAND (expr, 0);
860 tree oldop2 = TREE_OPERAND (expr, 1);
865 newop1 = phi_translate (find_leader (set, oldop1),
866 set, pred, phiblock);
869 newop2 = phi_translate (find_leader (set, oldop2),
870 set, pred, phiblock);
873 if (newop1 != oldop1 || newop2 != oldop2)
875 newexpr = pool_alloc (binary_node_pool);
876 memcpy (newexpr, expr, tree_size (expr));
877 create_tree_ann (newexpr);
878 TREE_OPERAND (newexpr, 0) = newop1 == oldop1 ? oldop1 : get_value_handle (newop1);
879 TREE_OPERAND (newexpr, 1) = newop2 == oldop2 ? oldop2 : get_value_handle (newop2);
880 vn_lookup_or_add (newexpr, NULL);
882 phi_trans_add (oldexpr, newexpr, pred);
886 /* XXX: Until we have PRE of loads working, none will be ANTIC.
893 tree oldop1 = TREE_OPERAND (expr, 0);
897 newop1 = phi_translate (find_leader (set, oldop1),
898 set, pred, phiblock);
901 if (newop1 != oldop1)
903 newexpr = pool_alloc (unary_node_pool);
904 memcpy (newexpr, expr, tree_size (expr));
905 create_tree_ann (newexpr);
906 TREE_OPERAND (newexpr, 0) = get_value_handle (newop1);
907 vn_lookup_or_add (newexpr, NULL);
909 phi_trans_add (oldexpr, newexpr, pred);
919 if (TREE_CODE (expr) != SSA_NAME)
921 if (TREE_CODE (SSA_NAME_DEF_STMT (expr)) == PHI_NODE)
922 phi = SSA_NAME_DEF_STMT (expr);
926 for (i = 0; i < PHI_NUM_ARGS (phi); i++)
927 if (PHI_ARG_EDGE (phi, i)->src == pred)
930 if (is_undefined_value (PHI_ARG_DEF (phi, i)))
932 val = vn_lookup_or_add (PHI_ARG_DEF (phi, i), NULL);
933 return PHI_ARG_DEF (phi, i);
942 phi_translate_set (value_set_t dest, value_set_t set, basic_block pred,
943 basic_block phiblock)
945 value_set_node_t node;
946 for (node = set->head;
951 translated = phi_translate (node->expr, set, pred, phiblock);
952 phi_trans_add (node->expr, translated, pred);
954 if (translated != NULL)
955 value_insert_into_set (dest, translated);
959 /* Find the leader for a value (i.e., the name representing that
960 value) in a given set, and return it. Return NULL if no leader is
964 bitmap_find_leader (bitmap_set_t set, tree val)
969 if (is_gimple_min_invariant (val))
971 if (bitmap_set_contains_value (set, val))
974 EXECUTE_IF_SET_IN_BITMAP (set->expressions, 0, i,
976 if (get_value_handle (ssa_name (i)) == val)
985 /* Find the leader for a value (i.e., the name representing that
986 value) in a given set, and return it. Return NULL if no leader is
990 find_leader (value_set_t set, tree val)
992 value_set_node_t node;
997 /* Constants represent themselves. */
998 if (is_gimple_min_invariant (val))
1001 if (set->length == 0)
1004 if (value_exists_in_set_bitmap (set, val))
1006 for (node = set->head;
1010 if (get_value_handle (node->expr) == val)
1018 /* Determine if the expression EXPR is valid in SET. This means that
1019 we have a leader for each part of the expression (if it consists of
1020 values), or the expression is an SSA_NAME.
1022 NB: We never should run into a case where we have SSA_NAME +
1023 SSA_NAME or SSA_NAME + value. The sets valid_in_set is called on,
1024 the ANTIC sets, will only ever have SSA_NAME's or binary value
1025 expression (IE VALUE1 + VALUE2) */
1028 valid_in_set (value_set_t set, tree expr)
1030 switch (TREE_CODE_CLASS (TREE_CODE (expr)))
1034 tree op1 = TREE_OPERAND (expr, 0);
1035 tree op2 = TREE_OPERAND (expr, 1);
1036 return set_contains_value (set, op1) && set_contains_value (set, op2);
1041 tree op1 = TREE_OPERAND (expr, 0);
1042 return set_contains_value (set, op1);
1045 /* XXX: Until PRE of loads works, no reference nodes are ANTIC.
1053 if (TREE_CODE (expr) == SSA_NAME)
1063 /* Clean the set of expressions that are no longer valid in SET. This
1064 means expressions that are made up of values we have no leaders for
1068 clean (value_set_t set)
1070 value_set_node_t node;
1071 value_set_node_t next;
1076 if (!valid_in_set (set, node->expr))
1077 set_remove (set, node->expr);
1082 /* Compute the ANTIC set for BLOCK.
1084 ANTIC_OUT[BLOCK] = intersection of ANTIC_IN[b] for all succ(BLOCK), if
1086 ANTIC_OUT[BLOCK] = phi_translate (ANTIC_IN[succ(BLOCK)]) if
1089 ANTIC_IN[BLOCK] = clean(ANTIC_OUT[BLOCK] U EXP_GEN[BLOCK] -
1092 Iterate until fixpointed.
1094 XXX: It would be nice to either write a set_clear, and use it for
1095 antic_out, or to mark the antic_out set as deleted at the end
1096 of this routine, so that the pool can hand the same memory back out
1097 again for the next antic_out. */
1101 compute_antic_aux (basic_block block)
1105 bool changed = false;
1106 value_set_t S, old, ANTIC_OUT;
1107 value_set_node_t node;
1109 ANTIC_OUT = S = NULL;
1110 /* If any edges from predecessors are abnormal, antic_in is empty, so
1111 punt. Remember that the block has an incoming abnormal edge by
1112 setting the BB_VISITED flag. */
1113 if (! (block->flags & BB_VISITED))
1115 for (e = block->pred; e; e = e->pred_next)
1116 if (e->flags & EDGE_ABNORMAL)
1118 block->flags |= BB_VISITED;
1122 if (block->flags & BB_VISITED)
1129 old = set_new (false);
1130 set_copy (old, ANTIC_IN (block));
1131 ANTIC_OUT = set_new (true);
1133 /* If the block has no successors, ANTIC_OUT is empty, because it is
1135 if (block->succ == NULL);
1137 /* If we have one successor, we could have some phi nodes to
1138 translate through. */
1139 else if (block->succ->succ_next == NULL)
1141 phi_translate_set (ANTIC_OUT, ANTIC_IN(block->succ->dest),
1142 block, block->succ->dest);
1144 /* If we have multiple successors, we take the intersection of all of
1148 varray_type worklist;
1151 basic_block bprime, first;
1153 VARRAY_BB_INIT (worklist, 1, "succ");
1157 VARRAY_PUSH_BB (worklist, e->dest);
1160 first = VARRAY_BB (worklist, 0);
1161 set_copy (ANTIC_OUT, ANTIC_IN (first));
1163 for (i = 1; i < VARRAY_ACTIVE_SIZE (worklist); i++)
1165 bprime = VARRAY_BB (worklist, i);
1166 node = ANTIC_OUT->head;
1170 value_set_node_t next = node->next;
1171 val = get_value_handle (node->expr);
1172 if (!set_contains_value (ANTIC_IN (bprime), val))
1173 set_remove (ANTIC_OUT, node->expr);
1177 VARRAY_CLEAR (worklist);
1180 /* Generate ANTIC_OUT - TMP_GEN */
1181 S = set_subtract (ANTIC_OUT, TMP_GEN (block), false);
1183 /* Start ANTIC_IN with EXP_GEN - TMP_GEN */
1184 ANTIC_IN (block) = set_subtract (EXP_GEN (block),TMP_GEN (block), true);
1186 /* Then union in the ANTIC_OUT - TMP_GEN values, to get ANTIC_OUT U
1187 EXP_GEN - TMP_GEN */
1188 for (node = S->head;
1192 value_insert_into_set (ANTIC_IN (block), node->expr);
1194 clean (ANTIC_IN (block));
1197 if (!set_equal (old, ANTIC_IN (block)))
1201 if (dump_file && (dump_flags & TDF_DETAILS))
1204 print_value_set (dump_file, ANTIC_OUT, "ANTIC_OUT", block->index);
1205 print_value_set (dump_file, ANTIC_IN (block), "ANTIC_IN", block->index);
1207 print_value_set (dump_file, S, "S", block->index);
1211 for (son = first_dom_son (CDI_POST_DOMINATORS, block);
1213 son = next_dom_son (CDI_POST_DOMINATORS, son))
1215 changed |= compute_antic_aux (son);
1220 /* Compute ANTIC sets. */
1223 compute_antic (void)
1225 bool changed = true;
1227 int num_iterations = 0;
1230 ANTIC_IN (bb) = set_new (true);
1231 if (bb->flags & BB_VISITED)
1239 changed = compute_antic_aux (EXIT_BLOCK_PTR);
1243 bb->flags &= ~BB_VISITED;
1245 if (num_iterations > 2 && dump_file && (dump_flags & TDF_STATS))
1246 fprintf (dump_file, "compute_antic required %d iterations\n", num_iterations);
1250 /* Find a leader for an expression, or generate one using
1251 create_expression_by_pieces if it's ANTIC but
1253 BLOCK is the basic_block we are looking for leaders in.
1254 EXPR is the expression to find a leader or generate for.
1255 STMTS is the statement list to put the inserted expressions on.
1256 Returns the SSA_NAME of the LHS of the generated expression or the
1260 find_or_generate_expression (basic_block block, tree expr, tree stmts)
1263 genop = bitmap_find_leader (AVAIL_OUT (block), expr);
1264 /* Depending on the order we process DOM branches in, the value
1265 may not have propagated to all the dom children yet during
1266 this iteration. In this case, the value will always be in
1267 the NEW_SETS for us already, having been propagated from our
1270 genop = find_leader (NEW_SETS (block), expr);
1271 /* If it's still NULL, see if it is a complex expression, and if
1272 so, generate it recursively, otherwise, abort, because it's
1276 genop = VALUE_HANDLE_EXPR_SET (expr)->head->expr;
1277 if (TREE_CODE_CLASS (TREE_CODE (genop)) != '1'
1278 && TREE_CODE_CLASS (TREE_CODE (genop)) != '2')
1280 genop = create_expression_by_pieces (block, genop, stmts);
1286 /* Create an expression in pieces, so that we can handle very complex
1287 expressions that may be ANTIC, but not necessary GIMPLE.
1288 BLOCK is the basic block the expression will be inserted into,
1289 EXPR is the expression to insert (in value form)
1290 STMTS is a statement list to append the necessary insertions into.
1292 This function will abort if we hit some value that shouldn't be
1293 ANTIC but is (IE there is no leader for it, or its components).
1294 This function may also generate expressions that are themselves
1295 partially or fully redundant. Those that are will be either made
1296 fully redundant during the next iteration of insert (for partially
1297 redundant ones), or eliminated by eliminate (for fully redundant
1301 create_expression_by_pieces (basic_block block, tree expr, tree stmts)
1303 tree name = NULL_TREE;
1304 tree newexpr = NULL_TREE;
1307 switch (TREE_CODE_CLASS (TREE_CODE (expr)))
1311 tree_stmt_iterator tsi;
1312 tree genop1, genop2;
1314 tree op1 = TREE_OPERAND (expr, 0);
1315 tree op2 = TREE_OPERAND (expr, 1);
1316 genop1 = find_or_generate_expression (block, op1, stmts);
1317 genop2 = find_or_generate_expression (block, op2, stmts);
1318 temp = create_tmp_var (TREE_TYPE (expr), "pretmp");
1319 add_referenced_tmp_var (temp);
1320 newexpr = build (TREE_CODE (expr), TREE_TYPE (expr),
1322 newexpr = build (MODIFY_EXPR, TREE_TYPE (expr),
1324 name = make_ssa_name (temp, newexpr);
1325 TREE_OPERAND (newexpr, 0) = name;
1326 tsi = tsi_last (stmts);
1327 tsi_link_after (&tsi, newexpr, TSI_CONTINUE_LINKING);
1328 pre_stats.insertions++;
1333 tree_stmt_iterator tsi;
1336 tree op1 = TREE_OPERAND (expr, 0);
1337 genop1 = find_or_generate_expression (block, op1, stmts);
1338 temp = create_tmp_var (TREE_TYPE (expr), "pretmp");
1339 add_referenced_tmp_var (temp);
1340 newexpr = build (TREE_CODE (expr), TREE_TYPE (expr),
1342 newexpr = build (MODIFY_EXPR, TREE_TYPE (expr),
1344 name = make_ssa_name (temp, newexpr);
1345 TREE_OPERAND (newexpr, 0) = name;
1346 tsi = tsi_last (stmts);
1347 tsi_link_after (&tsi, newexpr, TSI_CONTINUE_LINKING);
1348 pre_stats.insertions++;
1356 v = get_value_handle (expr);
1357 vn_add (name, v, NULL);
1358 insert_into_set (NEW_SETS (block), name);
1359 bitmap_value_insert_into_set (AVAIL_OUT (block), name);
1360 if (dump_file && (dump_flags & TDF_DETAILS))
1362 fprintf (dump_file, "Inserted ");
1363 print_generic_expr (dump_file, newexpr, 0);
1364 fprintf (dump_file, " in predecessor %d\n", block->index);
1369 /* Perform insertion of partially redundant values.
1370 For BLOCK, do the following:
1371 1. Propagate the NEW_SETS of the dominator into the current block.
1372 If the block has multiple predecessors,
1373 2a. Iterate over the ANTIC expressions for the block to see if
1374 any of them are partially redundant.
1375 2b. If so, insert them into the necessary predecessors to make
1376 the expression fully redundant.
1377 2c. Insert a new PHI merging the values of the predecessors.
1378 2d. Insert the new PHI, and the new expressions, into the
1380 3. Recursively call ourselves on the dominator children of BLOCK.
1384 insert_aux (basic_block block)
1387 bool new_stuff = false;
1393 dom = get_immediate_dominator (CDI_DOMINATORS, block);
1396 e = NEW_SETS (dom)->head;
1399 insert_into_set (NEW_SETS (block), e->expr);
1400 bitmap_value_replace_in_set (AVAIL_OUT (block), e->expr);
1403 if (block->pred->pred_next)
1405 value_set_node_t node;
1406 for (node = ANTIC_IN (block)->head;
1410 if (TREE_CODE_CLASS (TREE_CODE (node->expr)) == '2'
1411 || TREE_CODE_CLASS (TREE_CODE (node->expr)) == '1')
1415 bool by_some = false;
1416 bool cant_insert = false;
1417 bool all_same = true;
1418 tree first_s = NULL;
1423 val = get_value_handle (node->expr);
1424 if (set_contains_value (PHI_GEN (block), val))
1426 if (bitmap_set_contains_value (AVAIL_OUT (dom), val))
1428 if (dump_file && (dump_flags & TDF_DETAILS))
1429 fprintf (dump_file, "Found fully redundant value\n");
1433 avail = xcalloc (last_basic_block, sizeof (tree));
1434 for (pred = block->pred;
1436 pred = pred->pred_next)
1441 eprime = phi_translate (node->expr,
1445 /* eprime will generally only be NULL if the
1446 value of the expression, translated
1447 through the PHI for this predecessor, is
1448 undefined. If that is the case, we can't
1449 make the expression fully redundant,
1450 because its value is undefined along a
1451 predecessor path. We can thus break out
1452 early because it doesn't matter what the
1453 rest of the results are. */
1460 vprime = get_value_handle (eprime);
1463 edoubleprime = bitmap_find_leader (AVAIL_OUT (bprime),
1465 if (edoubleprime == NULL)
1467 avail[bprime->index] = eprime;
1472 avail[bprime->index] = edoubleprime;
1474 if (first_s == NULL)
1475 first_s = edoubleprime;
1476 else if (first_s != edoubleprime)
1478 if (first_s != edoubleprime
1479 && operand_equal_p (first_s, edoubleprime, 0))
1483 /* If we can insert it, it's not the same value
1484 already existing along every predecessor, and
1485 it's defined by some predecessor, it is
1486 partially redundant. */
1487 if (!cant_insert && !all_same && by_some)
1489 tree type = TREE_TYPE (avail[block->pred->src->index]);
1491 if (dump_file && (dump_flags & TDF_DETAILS))
1493 fprintf (dump_file, "Found partial redundancy for expression ");
1494 print_generic_expr (dump_file, node->expr, 0);
1495 fprintf (dump_file, "\n");
1498 /* Make the necessary insertions. */
1499 for (pred = block->pred;
1501 pred = pred->pred_next)
1503 tree stmts = alloc_stmt_list ();
1506 eprime = avail[bprime->index];
1507 if (TREE_CODE_CLASS (TREE_CODE (eprime)) == '2'
1508 || TREE_CODE_CLASS (TREE_CODE (eprime)) == '1')
1510 builtexpr = create_expression_by_pieces (bprime,
1513 bsi_insert_on_edge (pred, stmts);
1514 bsi_commit_edge_inserts (NULL);
1515 avail[bprime->index] = builtexpr;
1518 /* Now build a phi for the new variable. */
1519 temp = create_tmp_var (type, "prephitmp");
1520 add_referenced_tmp_var (temp);
1521 temp = create_phi_node (temp, block);
1522 vn_add (PHI_RESULT (temp), val, NULL);
1525 if (!set_contains_value (AVAIL_OUT (block), val))
1526 insert_into_set (AVAIL_OUT (block),
1530 bitmap_value_replace_in_set (AVAIL_OUT (block),
1532 for (pred = block->pred;
1534 pred = pred->pred_next)
1536 add_phi_arg (&temp, avail[pred->src->index],
1539 if (dump_file && (dump_flags & TDF_DETAILS))
1541 fprintf (dump_file, "Created phi ");
1542 print_generic_expr (dump_file, temp, 0);
1543 fprintf (dump_file, " in block %d\n", block->index);
1547 insert_into_set (NEW_SETS (block),
1549 insert_into_set (PHI_GEN (block),
1559 for (son = first_dom_son (CDI_DOMINATORS, block);
1561 son = next_dom_son (CDI_DOMINATORS, son))
1563 new_stuff |= insert_aux (son);
1569 /* Perform insertion of partially redundant values. */
1574 bool new_stuff = true;
1576 int num_iterations = 0;
1579 NEW_SETS (bb) = set_new (true);
1585 new_stuff = insert_aux (ENTRY_BLOCK_PTR);
1587 if (num_iterations > 2 && dump_file && (dump_flags & TDF_STATS))
1588 fprintf (dump_file, "insert required %d iterations\n", num_iterations);
1592 /* Return true if VAR is an SSA variable with no defining statement in
1593 this procedure, *AND* isn't a live-on-entry parameter. */
1596 is_undefined_value (tree expr)
1598 return (TREE_CODE (expr) == SSA_NAME
1599 && IS_EMPTY_STMT (SSA_NAME_DEF_STMT (expr))
1600 /* PARM_DECLs and hard registers are always defined. */
1601 && TREE_CODE (SSA_NAME_VAR (expr)) != PARM_DECL
1602 && !DECL_HARD_REGISTER (SSA_NAME_VAR (expr)));
1606 /* Given an SSA variable VAR and an expression EXPR, compute the value
1607 number for EXPR and create a value handle (VAL) for it. If VAR and
1608 EXPR are not the same, associate VAL with VAR. Finally, add VAR to
1609 S1 and its value handle to S2.
1611 VUSES represent the virtual use operands associated with EXPR (if
1612 any). They are used when computing the hash value for EXPR. */
1615 add_to_sets (tree var, tree expr, vuse_optype vuses, value_set_t s1,
1618 tree val = vn_lookup_or_add (expr, vuses);
1620 /* VAR and EXPR may be the same when processing statements for which
1621 we are not computing value numbers (e.g., non-assignments, or
1622 statements that make aliased stores). In those cases, we are
1623 only interested in making VAR available as its own value. */
1625 vn_add (var, val, vuses);
1627 insert_into_set (s1, var);
1628 bitmap_value_insert_into_set (s2, var);
1632 /* Given a unary or binary expression EXPR, create and return a new
1633 expression with the same structure as EXPR but with its operands
1634 replaced with the value handles of each of the operands of EXPR.
1635 Insert EXPR's operands into the EXP_GEN set for BLOCK.
1637 VUSES represent the virtual use operands associated with EXPR (if
1638 any). They are used when computing the hash value for EXPR. */
1641 create_value_expr_from (tree expr, basic_block block, vuse_optype vuses)
1644 enum tree_code code = TREE_CODE (expr);
1647 #if defined ENABLE_CHECKING
1648 if (TREE_CODE_CLASS (code) != '1'
1649 && TREE_CODE_CLASS (code) != '2')
1653 if (TREE_CODE_CLASS (code) == '1')
1654 vexpr = pool_alloc (unary_node_pool);
1656 vexpr = pool_alloc (binary_node_pool);
1658 memcpy (vexpr, expr, tree_size (expr));
1660 for (i = 0; i < TREE_CODE_LENGTH (code); i++)
1662 tree op = TREE_OPERAND (expr, i);
1665 tree val = vn_lookup_or_add (op, vuses);
1666 if (!is_undefined_value (op))
1667 value_insert_into_set (EXP_GEN (block), op);
1668 TREE_TYPE (val) = TREE_TYPE (TREE_OPERAND (vexpr, i));
1669 TREE_OPERAND (vexpr, i) = val;
1677 /* Compute the AVAIL set for BLOCK.
1678 This function performs value numbering of the statements in BLOCK.
1679 The AVAIL sets are built from information we glean while doing this
1680 value numbering, since the AVAIL sets contain only one entry per
1683 AVAIL_IN[BLOCK] = AVAIL_OUT[dom(BLOCK)].
1684 AVAIL_OUT[BLOCK] = AVAIL_IN[BLOCK] U PHI_GEN[BLOCK] U TMP_GEN[BLOCK]. */
1687 compute_avail (basic_block block)
1691 /* For arguments with default definitions, we pretend they are
1692 defined in the entry block. */
1693 if (block == ENTRY_BLOCK_PTR)
1696 for (param = DECL_ARGUMENTS (current_function_decl);
1698 param = TREE_CHAIN (param))
1700 if (default_def (param) != NULL)
1703 tree def = default_def (param);
1704 val = vn_lookup_or_add (def, NULL);
1705 insert_into_set (TMP_GEN (block), def);
1706 bitmap_value_insert_into_set (AVAIL_OUT (block), def);
1712 block_stmt_iterator bsi;
1716 /* Initially, the set of available values in BLOCK is that of
1717 its immediate dominator. */
1718 dom = get_immediate_dominator (CDI_DOMINATORS, block);
1720 bitmap_set_copy (AVAIL_OUT (block), AVAIL_OUT (dom));
1722 /* Generate values for PHI nodes. */
1723 for (phi = phi_nodes (block); phi; phi = PHI_CHAIN (phi))
1724 add_to_sets (PHI_RESULT (phi), PHI_RESULT (phi), NULL,
1725 PHI_GEN (block), AVAIL_OUT (block));
1727 /* Now compute value numbers and populate value sets with all
1728 the expressions computed in BLOCK. */
1729 for (bsi = bsi_start (block); !bsi_end_p (bsi); bsi_next (&bsi))
1734 stmt = bsi_stmt (bsi);
1735 ann = stmt_ann (stmt);
1736 get_stmt_operands (stmt);
1738 /* We are only interested in assignments of the form
1739 X_i = EXPR, where EXPR represents an "interesting"
1740 computation, it has no volatile operands and X_i
1741 doesn't flow through an abnormal edge. */
1742 if (TREE_CODE (stmt) == MODIFY_EXPR
1743 && !ann->has_volatile_ops
1744 && TREE_CODE (TREE_OPERAND (stmt, 0)) == SSA_NAME
1745 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (TREE_OPERAND (stmt, 0)))
1747 tree lhs = TREE_OPERAND (stmt, 0);
1748 tree rhs = TREE_OPERAND (stmt, 1);
1749 vuse_optype vuses = STMT_VUSE_OPS (stmt);
1751 STRIP_USELESS_TYPE_CONVERSION (rhs);
1753 if (TREE_CODE_CLASS (TREE_CODE (rhs)) == '1'
1754 || TREE_CODE_CLASS (TREE_CODE (rhs)) == '2')
1756 /* For binary, unary, and reference expressions,
1757 create a duplicate expression with the operands
1758 replaced with the value handles of the original
1760 tree newt = create_value_expr_from (rhs, block, vuses);
1761 add_to_sets (lhs, newt, vuses, TMP_GEN (block),
1763 value_insert_into_set (EXP_GEN (block), newt);
1766 else if (TREE_CODE (rhs) == SSA_NAME
1767 || is_gimple_min_invariant (rhs))
1769 /* Compute a value number for the RHS of the statement
1770 and add its value to the AVAIL_OUT set for the block.
1771 Add the LHS to TMP_GEN. */
1772 add_to_sets (lhs, rhs, vuses, TMP_GEN (block),
1775 if (TREE_CODE (rhs) == SSA_NAME
1776 && !is_undefined_value (rhs))
1777 value_insert_into_set (EXP_GEN (block), rhs);
1782 /* For any other statement that we don't recognize, simply
1783 make the names generated by the statement available in
1784 AVAIL_OUT and TMP_GEN. */
1785 for (j = 0; j < NUM_DEFS (STMT_DEF_OPS (stmt)); j++)
1787 tree def = DEF_OP (STMT_DEF_OPS (stmt), j);
1788 add_to_sets (def, def, NULL, TMP_GEN (block),
1792 for (j = 0; j < NUM_USES (STMT_USE_OPS (stmt)); j++)
1794 tree use = USE_OP (STMT_USE_OPS (stmt), j);
1795 add_to_sets (use, use, NULL, TMP_GEN (block),
1801 /* Compute available sets for the dominator children of BLOCK. */
1802 for (son = first_dom_son (CDI_DOMINATORS, block);
1804 son = next_dom_son (CDI_DOMINATORS, son))
1805 compute_avail (son);
1809 /* Eliminate fully redundant computations. */
1818 block_stmt_iterator i;
1820 for (i = bsi_start (b); !bsi_end_p (i); bsi_next (&i))
1822 tree stmt = bsi_stmt (i);
1824 /* Lookup the RHS of the expression, see if we have an
1825 available computation for it. If so, replace the RHS with
1826 the available computation. */
1827 if (TREE_CODE (stmt) == MODIFY_EXPR
1828 && TREE_CODE (TREE_OPERAND (stmt, 0)) == SSA_NAME
1829 && TREE_CODE (TREE_OPERAND (stmt ,1)) != SSA_NAME
1830 && !is_gimple_min_invariant (TREE_OPERAND (stmt, 1))
1831 && !stmt_ann (stmt)->has_volatile_ops)
1833 tree lhs = TREE_OPERAND (stmt, 0);
1834 tree *rhs_p = &TREE_OPERAND (stmt, 1);
1836 vuse_optype vuses = STMT_VUSE_OPS (stmt);
1838 sprime = bitmap_find_leader (AVAIL_OUT (b), vn_lookup (lhs, vuses));
1841 && (TREE_CODE (*rhs_p) != SSA_NAME
1842 || may_propagate_copy (*rhs_p, sprime)))
1844 if (sprime == *rhs_p)
1847 if (dump_file && (dump_flags & TDF_DETAILS))
1849 fprintf (dump_file, "Replaced ");
1850 print_generic_expr (dump_file, *rhs_p, 0);
1851 fprintf (dump_file, " with ");
1852 print_generic_expr (dump_file, sprime, 0);
1853 fprintf (dump_file, " in ");
1854 print_generic_stmt (dump_file, stmt, 0);
1856 pre_stats.eliminations++;
1857 propagate_tree_value (rhs_p, sprime);
1866 /* Initialize data structures used by PRE. */
1875 memset (&pre_stats, 0, sizeof (pre_stats));
1877 bb->aux = xcalloc (1, sizeof (struct bb_value_sets));
1879 phi_translate_table = htab_create (511, expr_pred_trans_hash,
1880 expr_pred_trans_eq, free);
1881 value_set_pool = create_alloc_pool ("Value sets",
1882 sizeof (struct value_set), 30);
1883 bitmap_set_pool = create_alloc_pool ("Bitmap sets",
1884 sizeof (struct bitmap_set), 30);
1885 value_set_node_pool = create_alloc_pool ("Value set nodes",
1886 sizeof (struct value_set_node), 30);
1887 calculate_dominance_info (CDI_POST_DOMINATORS);
1888 calculate_dominance_info (CDI_DOMINATORS);
1889 tsize = tree_size (build (PLUS_EXPR, void_type_node, NULL_TREE, NULL_TREE));
1890 binary_node_pool = create_alloc_pool ("Binary tree nodes", tsize, 30);
1891 tsize = tree_size (build1 (NEGATE_EXPR, void_type_node, NULL_TREE));
1892 unary_node_pool = create_alloc_pool ("Unary tree nodes", tsize, 30);
1896 EXP_GEN (bb) = set_new (true);
1897 PHI_GEN (bb) = set_new (true);
1898 TMP_GEN (bb) = set_new (false);
1899 AVAIL_OUT (bb) = bitmap_set_new ();
1904 /* Deallocate data structures used by PRE. */
1911 free_alloc_pool (value_set_pool);
1912 free_alloc_pool (bitmap_set_pool);
1913 free_alloc_pool (value_set_node_pool);
1914 free_alloc_pool (binary_node_pool);
1915 free_alloc_pool (unary_node_pool);
1916 htab_delete (phi_translate_table);
1923 free_dominance_info (CDI_POST_DOMINATORS);
1928 /* Main entry point to the SSA-PRE pass. DO_FRE is true if the caller
1929 only wants to do full redundancy elimination. */
1932 execute_pre (bool do_fre)
1936 /* Collect and value number expressions computed in each basic
1938 compute_avail (ENTRY_BLOCK_PTR);
1940 if (dump_file && (dump_flags & TDF_DETAILS))
1946 print_value_set (dump_file, EXP_GEN (bb), "exp_gen", bb->index);
1947 print_value_set (dump_file, TMP_GEN (bb), "tmp_gen", bb->index);
1948 bitmap_print_value_set (dump_file, AVAIL_OUT (bb), "avail_out",
1953 /* Insert can get quite slow on an incredibly large number of basic
1954 blocks due to some quadratic behavior. Until this behavior is
1955 fixed, don't run it when he have an incredibly large number of
1956 bb's. If we aren't going to run insert, there is no point in
1957 computing ANTIC, either, even though it's plenty fast. */
1958 if (!do_fre && n_basic_blocks < 4000)
1964 /* Remove all the redundant expressions. */
1967 if (dump_file && (dump_flags & TDF_STATS))
1969 fprintf (dump_file, "Insertions:%d\n", pre_stats.insertions);
1970 fprintf (dump_file, "New PHIs:%d\n", pre_stats.phis);
1971 fprintf (dump_file, "Eliminated:%d\n", pre_stats.eliminations);
1978 /* Gate and execute functions for PRE. */
1983 execute_pre (false);
1989 return flag_tree_pre != 0;
1992 struct tree_opt_pass pass_pre =
1995 gate_pre, /* gate */
1996 do_pre, /* execute */
1999 0, /* static_pass_number */
2000 TV_TREE_PRE, /* tv_id */
2001 PROP_no_crit_edges | PROP_cfg | PROP_ssa,/* properties_required */
2002 0, /* properties_provided */
2003 0, /* properties_destroyed */
2004 0, /* todo_flags_start */
2005 TODO_dump_func | TODO_ggc_collect | TODO_verify_ssa /* todo_flags_finish */
2009 /* Gate and execute functions for FRE. */
2020 return flag_tree_fre != 0;
2023 struct tree_opt_pass pass_fre =
2026 gate_fre, /* gate */
2027 do_fre, /* execute */
2030 0, /* static_pass_number */
2031 TV_TREE_FRE, /* tv_id */
2032 PROP_no_crit_edges | PROP_cfg | PROP_ssa,/* properties_required */
2033 0, /* properties_provided */
2034 0, /* properties_destroyed */
2035 0, /* todo_flags_start */
2036 TODO_dump_func | TODO_ggc_collect | TODO_verify_ssa /* todo_flags_finish */