2 Copyright (C) 2001, 2002, 2003, 2004 Free Software Foundation, Inc.
3 Contributed by Daniel Berlin <dan@dberlin.org> and Steven Bosscher
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify
9 it under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 2, or (at your option)
13 GCC is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 GNU General Public License for more details.
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING. If not, write to
20 the Free Software Foundation, 59 Temple Place - Suite 330,
21 Boston, MA 02111-1307, USA. */
24 #include "coretypes.h"
30 /* These RTL headers are needed for basic-block.h. */
33 #include "hard-reg-set.h"
34 #include "basic-block.h"
35 #include "diagnostic.h"
36 #include "tree-inline.h"
37 #include "tree-flow.h"
38 #include "tree-gimple.h"
39 #include "tree-dump.h"
43 #include "tree-iterator.h"
45 #include "alloc-pool.h"
46 #include "tree-pass.h"
48 #include "splay-tree.h"
50 #include "langhooks.h"
53 1. Implement load value numbering.
54 2. Speed up insert_aux so that we can use it all the time. It
55 spends most of it's time in quadratic value replacement.
56 3. Avail sets can be shared by making an avail_find_leader that
57 walks up the dominator tree and looks in those avail sets.
58 This might affect code optimality, it's unclear right now.
59 4. Load motion can be performed by value numbering the loads the
60 same as we do other expressions. This requires iterative
61 hashing the vuses into the values. Right now we simply assign
62 a new value every time we see a statement with a vuse.
63 5. Strength reduction can be performed by anticipating expressions
64 we can repair later on.
65 6. Our canonicalization of expressions during lookups don't take
66 constants into account very well. In particular, we don't fold
67 anywhere, so we can get situations where we stupidly think
68 something is a new value (a + 1 + 1 vs a + 2). This is somewhat
69 expensive to fix, but it does expose a lot more eliminations.
70 It may or not be worth it, depending on how critical you
71 consider PRE vs just plain GRE.
74 /* For ease of terminology, "expression node" in the below refers to
75 every expression node but MODIFY_EXPR, because MODIFY_EXPR's represent
76 the actual statement containing the expressions we care about, and
77 we cache the value number by putting it in the expression. */
81 First we walk the statements to generate the AVAIL sets, the
82 EXP_GEN sets, and the tmp_gen sets. EXP_GEN sets represent the
83 generation of values/expressions by a given block. We use them
84 when computing the ANTIC sets. The AVAIL sets consist of
85 SSA_NAME's that represent values, so we know what values are
86 available in what blocks. AVAIL is a forward dataflow problem. In
87 SSA, values are never killed, so we don't need a kill set, or a
88 fixpoint iteration, in order to calculate the AVAIL sets. In
89 traditional parlance, AVAIL sets tell us the downsafety of the
92 Next, we generate the ANTIC sets. These sets represent the
93 anticipatable expressions. ANTIC is a backwards dataflow
94 problem.An expression is anticipatable in a given block if it could
95 be generated in that block. This means that if we had to perform
96 an insertion in that block, of the value of that expression, we
97 could. Calculating the ANTIC sets requires phi translation of
98 expressions, because the flow goes backwards through phis. We must
99 iterate to a fixpoint of the ANTIC sets, because we have a kill
100 set. Even in SSA form, values are not live over the entire
101 function, only from their definition point onwards. So we have to
102 remove values from the ANTIC set once we go past the definition
103 point of the leaders that make them up.
104 compute_antic/compute_antic_aux performs this computation.
106 Third, we perform insertions to make partially redundant
107 expressions fully redundant.
109 An expression is partially redundant (excluding partial
112 1. It is AVAIL in some, but not all, of the predecessors of a
114 2. It is ANTIC in all the predecessors.
116 In order to make it fully redundant, we insert the expression into
117 the predecessors where it is not available, but is ANTIC.
118 insert/insert_aux performs this insertion.
120 Fourth, we eliminate fully redundant expressions.
121 This is a simple statement walk that replaces redundant
122 calculations with the now available values. */
124 /* Representations of value numbers:
126 Value numbers are represented using the "value handle" approach.
127 This means that each SSA_NAME (and for other reasons to be
128 disclosed in a moment, expression nodes) has a value handle that
129 can be retrieved through get_value_handle. This value handle, *is*
130 the value number of the SSA_NAME. You can pointer compare the
131 value handles for equivalence purposes.
133 For debugging reasons, the value handle is internally more than
134 just a number, it is a VAR_DECL named "value.x", where x is a
135 unique number for each value number in use. This allows
136 expressions with SSA_NAMES replaced by value handles to still be
137 pretty printed in a sane way. They simply print as "value.3 *
140 Expression nodes have value handles associated with them as a
141 cache. Otherwise, we'd have to look them up again in the hash
142 table This makes significant difference (factor of two or more) on
143 some test cases. They can be thrown away after the pass is
146 /* Representation of expressions on value numbers:
148 In some portions of this code, you will notice we allocate "fake"
149 analogues to the expression we are value numbering, and replace the
150 operands with the values of the expression. Since we work on
151 values, and not just names, we canonicalize expressions to value
152 expressions for use in the ANTIC sets, the EXP_GEN set, etc.
154 This is theoretically unnecessary, it just saves a bunch of
155 repeated get_value_handle and find_leader calls in the remainder of
156 the code, trading off temporary memory usage for speed. The tree
157 nodes aren't actually creating more garbage, since they are
158 allocated in a special pools which are thrown away at the end of
161 All of this also means that if you print the EXP_GEN or ANTIC sets,
162 you will see "value.5 + value.7" in the set, instead of "a_55 +
163 b_66" or something. The only thing that actually cares about
164 seeing the value leaders is phi translation, and it needs to be
165 able to find the leader for a value in an arbitrary block, so this
166 "value expression" form is perfect for it (otherwise you'd do
167 get_value_handle->find_leader->translate->get_value_handle->find_leader).*/
170 /* Representation of sets:
172 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. */
226 /* All of the following sets, except for TMP_GEN, are indexed.
227 TMP_GEN is only ever iterated over, we never check what values
230 typedef struct bb_value_sets
232 /* The EXP_GEN set, which represents expressions/values generated in
236 /* The PHI_GEN set, which represents PHI results generated in a
240 /* The TMP_GEN set, which represents results/temporaries genererated
241 in a basic block. IE the LHS of an expression. */
244 /* The AVAIL_OUT set, which represents which values are available in
245 a given basic block. */
246 value_set_t avail_out;
248 /* The ANTIC_IN set, which represents which values are anticiptable
249 in a given basic block. */
250 value_set_t antic_in;
252 /* The NEW_SETS set, which is used during insertion to augment the
253 AVAIL_OUT set of blocks with the new insertions performed during
254 the current iteration. */
255 value_set_t new_sets;
258 #define EXP_GEN(BB) ((bb_value_sets_t) ((BB)->aux))->exp_gen
259 #define PHI_GEN(BB) ((bb_value_sets_t) ((BB)->aux))->phi_gen
260 #define TMP_GEN(BB) ((bb_value_sets_t) ((BB)->aux))->tmp_gen
261 #define AVAIL_OUT(BB) ((bb_value_sets_t) ((BB)->aux))->avail_out
262 #define ANTIC_IN(BB) ((bb_value_sets_t) ((BB)->aux))->antic_in
263 #define NEW_SETS(BB) ((bb_value_sets_t) ((BB)->aux))->new_sets
265 /* This structure is used to keep track of statistics on what
266 optimization PRE was able to perform. */
269 /* The number of RHS computations eliminated by PRE. */
272 /* The number of new expressions/temporaries generated by PRE. */
275 /* The number of new PHI nodes added by PRE. */
279 static tree find_leader (value_set_t, tree);
280 static void value_insert_into_set (value_set_t, tree);
281 static void insert_into_set (value_set_t, tree);
282 static void add_to_value (tree, tree);
283 static value_set_t set_new (bool);
284 static bool is_undefined_value (tree);
285 static bool expressions_equal_p (tree, tree);
286 static tree create_expression_by_pieces (basic_block, tree, tree);
288 /* We can add and remove elements and entries to and from sets
289 and hash tables, so we use alloc pools for them. */
291 static alloc_pool value_set_pool;
292 static alloc_pool value_set_node_pool;
293 static alloc_pool binary_node_pool;
294 static alloc_pool unary_node_pool;
296 /* The value table that maps expressions to values. */
298 static htab_t value_table;
300 /* The phi_translate_table caches phi translations for a given
301 expression and predecessor. */
303 static htab_t phi_translate_table;
305 /* Compare two expressions E1 and E2 and return true if they are
309 expressions_equal_p (tree e1, tree e2)
316 te1 = TREE_TYPE (e1);
317 te2 = TREE_TYPE (e2);
319 if (TREE_CODE (e1) == TREE_CODE (e2)
320 && (te1 == te2 || lang_hooks.types_compatible_p (te1, te2))
321 && operand_equal_p (e1, e2, 0))
326 /* Map expressions to values. These are simple pairs of expressions
327 and the values they represent. To find the value represented by
328 an expression, we use a hash table where the elements are {e,v}
329 pairs, and the expression is the key. */
331 typedef struct val_expr_pair_d
338 /* Hash a {v,e} pair that is pointed to by P.
339 The hashcode is cached in the val_expr_pair, so we just return
343 val_expr_pair_hash (const void *p)
345 const val_expr_pair_t ve = (val_expr_pair_t) p;
350 /* Given two val_expr_pair_t's, return true if they represent the same
351 expression, false otherwise.
352 P1 and P2 should point to the val_expr_pair_t's to be compared. */
355 val_expr_pair_expr_eq (const void *p1, const void *p2)
357 const val_expr_pair_t ve1 = (val_expr_pair_t) p1;
358 const val_expr_pair_t ve2 = (val_expr_pair_t) p2;
360 if (expressions_equal_p (ve1->e, ve2->e))
367 /* Get the value handle of EXPR. This is the only correct way to get
368 the value handle for a "thing".
369 Returns NULL if the value handle does not exist. */
372 get_value_handle (tree expr)
374 /* We should never see these. */
377 else if (TREE_CODE (expr) == SSA_NAME)
379 return SSA_NAME_VALUE (expr);
381 else if (TREE_CODE_CLASS (TREE_CODE (expr)) == 'c')
383 else if (EXPR_P (expr))
385 tree_ann_t ann = tree_ann (expr);
387 return ann->common.value_handle;
394 /* Set the value handle for expression E to value V */
397 set_value_handle (tree e, tree v)
401 else if (TREE_CODE (e) == SSA_NAME)
402 SSA_NAME_VALUE (e) = v;
404 get_tree_ann (e)->common.value_handle = v;
407 /* A three tuple {e, pred, v} used to cache phi translations in the
408 phi_translate_table. */
410 typedef struct expr_pred_trans_d
412 /* The expression. */
415 /* The predecessor block along which we translated the expression. */
418 /* The value that resulted from the translation. */
421 /* The hashcode for the expression, pred pair. This is cached for
424 } *expr_pred_trans_t;
426 /* Return the hash value for a phi translation table entry. */
429 expr_pred_trans_hash (const void *p)
431 const expr_pred_trans_t ve = (expr_pred_trans_t) p;
435 /* Return true if two phi translation table entries are the same.
436 P1 and P2 should point to the expr_pred_trans_t's to be compared.*/
439 expr_pred_trans_eq (const void *p1, const void *p2)
441 const expr_pred_trans_t ve1 = (expr_pred_trans_t) p1;
442 const expr_pred_trans_t ve2 = (expr_pred_trans_t) p2;
443 basic_block b1 = ve1->pred;
444 basic_block b2 = ve2->pred;
447 /* If they are not translations for the same basic block, they can't
452 /* If they are for the same basic block, determine if the
453 expressions are equal. */
454 if (expressions_equal_p (ve1->e, ve2->e))
460 /* Search in the phi translation table for the translation of
461 expression E in basic block PRED. Return the translated value, if
462 found, NULL otherwise. */
465 phi_trans_lookup (tree e, basic_block pred)
468 struct expr_pred_trans_d ept;
471 ept.hashcode = iterative_hash_expr (e, (unsigned long) pred);
472 slot = htab_find_slot_with_hash (phi_translate_table, &ept, ept.hashcode,
477 return ((expr_pred_trans_t) *slot)->v;
481 /* Add the tuple mapping from {expression E, basic block PRED} to
482 value V, to the phi translation table. */
485 phi_trans_add (tree e, tree v, basic_block pred)
488 expr_pred_trans_t new_pair = xmalloc (sizeof (*new_pair));
490 new_pair->pred = pred;
492 new_pair->hashcode = iterative_hash_expr (e, (unsigned long) pred);
493 slot = htab_find_slot_with_hash (phi_translate_table, new_pair,
494 new_pair->hashcode, INSERT);
497 *slot = (void *) new_pair;
500 /* Search in TABLE for an existing instance of expression E,
501 and return its value, or NULL if none has been set. */
504 lookup (htab_t table, tree e)
507 struct val_expr_pair_d vep = {NULL, NULL, 0};
508 if (TREE_CODE_CLASS (TREE_CODE (e)) == 'c')
511 vep.hashcode = iterative_hash_expr (e,0);
512 slot = htab_find_slot_with_hash (table, &vep, vep.hashcode, NO_INSERT);
516 return ((val_expr_pair_t) *slot)->v;
519 /* Add expression E to the expression set of value V. */
522 add_to_value (tree v, tree e)
525 /* For values representing non-CST nodes, but still function
526 invariant things we mark TREE_CONSTANT as true and set the tree
527 chain to the actual constant. This is because unlike values
528 involving expressions, which are only available to use where the
529 expressions are live, a function invariant can be remade
530 anywhere, and thus, is available everywhere, just like a constant. */
531 if (TREE_CODE_CLASS (TREE_CODE (v)) == 'c')
533 else if (is_gimple_min_invariant (v))
535 TREE_CONSTANT (v) = true;
540 if (va->expr_set == NULL)
541 va->expr_set = set_new (false);
542 insert_into_set (va->expr_set, e);
545 /* Insert E into TABLE with value V, and add expression E to the value
549 add (htab_t table, tree e, tree v)
553 val_expr_pair_t new_pair = xmalloc (sizeof (struct val_expr_pair_d));
556 new_pair->hashcode = iterative_hash_expr (e, 0);
557 slot = htab_find_slot_with_hash (table, new_pair, new_pair->hashcode,
561 *slot = (void *) new_pair;
562 set_value_handle (e, v);
568 /* A unique counter that is incremented every time we create a new
572 /* Create a new value handle for expression EXPR. */
575 create_new_value (tree expr)
577 tree a = create_tmp_var_raw (TREE_TYPE (expr), "value");
579 var_ann (a)->uid = pre_uid++;
581 if (dump_file && (dump_flags & TDF_DETAILS))
583 fprintf (dump_file, "Created value ");
584 print_generic_expr (dump_file, a, dump_flags);
585 fprintf (dump_file, " for ");
586 print_generic_expr (dump_file, expr, dump_flags);
587 fprintf (dump_file, "\n");
592 /* Like lookup, but creates a new value for expression E if E doesn't
593 already have a value.
594 Return the existing/created value for E. */
597 lookup_or_add (htab_t table, tree e)
599 tree x = lookup (table, e);
603 v = create_new_value (e);
607 set_value_handle (e, x);
612 /* Return true if value V exists in the bitmap for SET. */
615 value_exists_in_set_bitmap (value_set_t set, tree v)
617 if (TREE_CODE (v) != VAR_DECL)
622 return bitmap_bit_p (set->values, get_var_ann (v)->uid);
625 /* Remove value V from the bitmap for SET. */
628 value_remove_from_set_bitmap (value_set_t set, tree v)
630 if (TREE_CODE (v) != VAR_DECL)
632 #ifdef ENABLE_CHECKING
638 bitmap_clear_bit (set->values, get_var_ann (v)->uid);
642 /* Insert the value number V into the bitmap of values existing in
646 value_insert_into_set_bitmap (value_set_t set, tree v)
648 if (TREE_CODE (v) != VAR_DECL)
650 #ifdef ENABLE_CHECKING
654 if (set->values == NULL)
656 set->values = BITMAP_GGC_ALLOC ();
657 bitmap_clear (set->values);
659 bitmap_set_bit (set->values, get_var_ann (v)->uid);
662 /* Create a new set. */
665 set_new (bool indexed)
668 ret = pool_alloc (value_set_pool);
669 ret->head = ret->tail = NULL;
671 ret->indexed = indexed;
677 /* Insert EXPR into SET. */
680 insert_into_set (value_set_t set, tree expr)
682 value_set_node_t newnode = pool_alloc (value_set_node_pool);
683 tree val = get_value_handle (expr);
690 /* For indexed sets, insert the value into the set value bitmap.
691 For all sets, add it to the linked list and increment the list
694 value_insert_into_set_bitmap (set, val);
696 newnode->next = NULL;
697 newnode->expr = expr;
699 if (set->head == NULL)
701 set->head = set->tail = newnode;
705 set->tail->next = newnode;
710 /* Copy the set ORIG to the set DEST. */
713 set_copy (value_set_t dest, value_set_t orig)
715 value_set_node_t node;
717 if (!orig || !orig->head)
720 for (node = orig->head;
724 insert_into_set (dest, node->expr);
728 /* Remove EXPR from SET. */
731 set_remove (value_set_t set, tree expr)
733 value_set_node_t node, prev;
735 /* Remove the value of EXPR from the bitmap, decrement the set
736 length, and remove it from the actual double linked list. */
737 value_remove_from_set_bitmap (set, get_value_handle (expr));
740 for (node = set->head;
742 prev = node, node = node->next)
744 if (node->expr == expr)
747 set->head = node->next;
749 prev->next= node->next;
751 if (node == set->tail)
753 pool_free (value_set_node_pool, node);
759 /* Return true if SET contains the value VAL. */
762 set_contains_value (value_set_t set, tree val)
764 /* All true constants are in every set. */
765 if (TREE_CODE_CLASS (TREE_CODE (val)) == 'c')
767 /* This is only referring to the flag above that we set on
768 values referring to invariants, because we know that we
769 are dealing with one of the value handles we created. */
771 if (TREE_CONSTANT (val))
774 if (set->length == 0)
777 return value_exists_in_set_bitmap (set, val);
780 /* Replace the leader for the value LOOKFOR in SET with EXPR. */
783 set_replace_value (value_set_t set, tree lookfor, tree expr)
785 value_set_node_t node = set->head;
787 /* The lookup is probably more expensive than walking the linked
788 list when we have only a small number of nodes. */
789 if (!set_contains_value (set, lookfor))
792 for (node = set->head;
796 if (get_value_handle (node->expr) == lookfor)
804 /* Return true if the set contains expression (not value) EXPR. */
807 set_contains (value_set_t set, tree expr)
809 value_set_node_t node;
811 for (node = set->head;
815 if (operand_equal_p (node->expr, expr, 0))
821 /* Subtract set B from set A, and return the new set. */
824 set_subtract (value_set_t a, value_set_t b, bool indexed)
826 value_set_t ret = set_new (indexed);
827 value_set_node_t node;
832 if (!set_contains (b, node->expr))
833 insert_into_set (ret, node->expr);
838 /* Return true if two sets are equal. */
841 set_equal (value_set_t a, value_set_t b)
843 value_set_node_t node;
845 if (a->length != b->length)
851 if (!set_contains_value (b, get_value_handle (node->expr)))
857 /* Replace the value for EXPR in SET with EXPR. */
859 value_replace_in_set (value_set_t set, tree expr)
861 tree val = get_value_handle (expr);
863 if (set->length == 0)
866 set_replace_value (set, val, expr);
869 /* Insert the value for EXPR into SET, if it doesn't exist already. */
872 value_insert_into_set (value_set_t set, tree expr)
874 tree val = get_value_handle (expr);
877 /* Constant and invariant values exist everywhere, and thus,
878 actually keeping them in the sets is pointless. */
879 if (TREE_CONSTANT (val))
882 if (!set_contains_value (set, val))
883 insert_into_set (set, expr);
887 /* Print out the value_set SET to OUTFILE. */
890 print_value_set (FILE *outfile, value_set_t set,
891 const char *setname, int blockindex)
893 value_set_node_t node;
894 fprintf (outfile, "%s[%d] := { ", setname, blockindex);
897 for (node = set->head;
901 print_generic_expr (outfile, node->expr, 0);
903 fprintf (outfile, " (");
904 print_generic_expr (outfile, get_value_handle (node->expr), 0);
905 fprintf (outfile, ") ");
908 fprintf (outfile, ", ");
912 fprintf (outfile, " }\n");
915 /* Print out the expressions that have VAL to OUTFILE. */
917 print_value_expressions (FILE *outfile, tree val)
919 var_ann_t va = var_ann (val);
920 if (va && va->expr_set)
921 print_value_set (outfile, va->expr_set,
922 IDENTIFIER_POINTER (DECL_NAME (val)), 0);
927 debug_value_expressions (tree val)
929 print_value_expressions (stderr, val);
933 void debug_value_set (value_set_t, const char *, int);
936 debug_value_set (value_set_t set, const char *setname, int blockindex)
938 print_value_set (stderr, set, setname, blockindex);
941 /* Translate EXPR using phis in PHIBLOCK, so that it has the values of
942 the phis in PRED. Return NULL if we can't find a leader for each
943 part of the translated expression. */
946 phi_translate (tree expr, value_set_t set, basic_block pred,
947 basic_block phiblock)
949 tree phitrans = NULL;
955 /* Phi translations of a given expression don't change, */
956 phitrans = phi_trans_lookup (expr, pred);
961 switch (TREE_CODE_CLASS (TREE_CODE (expr)))
965 tree oldop1 = TREE_OPERAND (expr, 0);
966 tree oldop2 = TREE_OPERAND (expr, 1);
971 newop1 = phi_translate (find_leader (set, oldop1),
972 set, pred, phiblock);
975 newop2 = phi_translate (find_leader (set, oldop2),
976 set, pred, phiblock);
979 if (newop1 != oldop1 || newop2 != oldop2)
981 newexpr = pool_alloc (binary_node_pool);
982 memcpy (newexpr, expr, tree_size (expr));
983 create_tree_ann (newexpr);
984 TREE_OPERAND (newexpr, 0) = newop1 == oldop1 ? oldop1 : get_value_handle (newop1);
985 TREE_OPERAND (newexpr, 1) = newop2 == oldop2 ? oldop2 : get_value_handle (newop2);
986 lookup_or_add (value_table, newexpr);
988 phi_trans_add (oldexpr, newexpr, pred);
992 /* XXX: Until we have PRE of loads working, none will be ANTIC.
999 tree oldop1 = TREE_OPERAND (expr, 0);
1003 newop1 = phi_translate (find_leader (set, oldop1),
1004 set, pred, phiblock);
1007 if (newop1 != oldop1)
1009 newexpr = pool_alloc (unary_node_pool);
1010 memcpy (newexpr, expr, tree_size (expr));
1011 create_tree_ann (newexpr);
1012 TREE_OPERAND (newexpr, 0) = get_value_handle (newop1);
1013 lookup_or_add (value_table, newexpr);
1015 phi_trans_add (oldexpr, newexpr, pred);
1025 if (TREE_CODE (expr) != SSA_NAME)
1027 if (TREE_CODE (SSA_NAME_DEF_STMT (expr)) == PHI_NODE)
1028 phi = SSA_NAME_DEF_STMT (expr);
1032 for (i = 0; i < PHI_NUM_ARGS (phi); i++)
1033 if (PHI_ARG_EDGE (phi, i)->src == pred)
1036 if (is_undefined_value (PHI_ARG_DEF (phi, i)))
1038 val = lookup_or_add (value_table, PHI_ARG_DEF (phi, i));
1039 return PHI_ARG_DEF (phi, i);
1048 phi_translate_set (value_set_t dest, value_set_t set, basic_block pred,
1049 basic_block phiblock)
1051 value_set_node_t node;
1052 for (node = set->head;
1057 translated = phi_translate (node->expr, set, pred, phiblock);
1058 phi_trans_add (node->expr, translated, pred);
1060 if (translated != NULL)
1061 value_insert_into_set (dest, translated);
1065 /* Find the leader for a value (IE the name representing that
1066 value) in a given set, and return it. Return NULL if no leader is
1070 find_leader (value_set_t set, tree val)
1072 value_set_node_t node;
1076 /* True constants represent themselves. */
1077 if (TREE_CODE_CLASS (TREE_CODE (val)) == 'c')
1079 /* Invariants are still represented by values, since they may be
1080 more than a single _CST node. */
1081 if (TREE_CONSTANT (val))
1082 return TREE_CHAIN (val);
1084 if (set->length == 0)
1087 if (value_exists_in_set_bitmap (set, val))
1089 for (node = set->head;
1093 if (get_value_handle (node->expr) == val)
1100 /* Determine if the expression EXPR is valid in SET. This means that
1101 we have a leader for each part of the expression (if it consists of
1102 values), or the expression is an SSA_NAME.
1104 NB: We never should run into a case where we have SSA_NAME +
1105 SSA_NAME or SSA_NAME + value. The sets valid_in_set is called on,
1106 the ANTIC sets, will only ever have SSA_NAME's or binary value
1107 expression (IE VALUE1 + VALUE2) */
1110 valid_in_set (value_set_t set, tree expr)
1112 switch (TREE_CODE_CLASS (TREE_CODE (expr)))
1116 tree op1 = TREE_OPERAND (expr, 0);
1117 tree op2 = TREE_OPERAND (expr, 1);
1118 return set_contains_value (set, op1) && set_contains_value (set, op2);
1123 tree op1 = TREE_OPERAND (expr, 0);
1124 return set_contains_value (set, op1);
1127 /* XXX: Until PRE of loads works, no reference nodes are ANTIC.
1135 if (TREE_CODE (expr) == SSA_NAME)
1145 /* Clean the set of expressions that are no longer valid in SET. This
1146 means expressions that are made up of values we have no leaders for
1150 clean (value_set_t set)
1152 value_set_node_t node;
1153 value_set_node_t next;
1158 if (!valid_in_set (set, node->expr))
1159 set_remove (set, node->expr);
1164 /* Compute the ANTIC set for BLOCK.
1166 ANTIC_OUT[BLOCK] = intersection of ANTIC_IN[b] for all succ(BLOCK), if
1168 ANTIC_OUT[BLOCK] = phi_translate (ANTIC_IN[succ(BLOCK)]) if
1171 ANTIC_IN[BLOCK] = clean(ANTIC_OUT[BLOCK] U EXP_GEN[BLOCK] -
1174 Iterate until fixpointed.
1176 XXX: It would be nice to either write a set_clear, and use it for
1177 antic_out, or to mark the antic_out set as deleted at the end
1178 of this routine, so that the pool can hand the same memory back out
1179 again for the next antic_out. */
1183 compute_antic_aux (basic_block block)
1187 bool changed = false;
1188 value_set_t S, old, ANTIC_OUT;
1189 value_set_node_t node;
1191 ANTIC_OUT = S = NULL;
1192 /* If any edges from predecessors are abnormal, antic_in is empty, so
1193 punt. Remember that the block has an incoming abnormal edge by
1194 setting the BB_VISITED flag. */
1195 if (! (block->flags & BB_VISITED))
1197 for (e = block->pred; e; e = e->pred_next)
1198 if (e->flags & EDGE_ABNORMAL)
1200 block->flags |= BB_VISITED;
1204 if (block->flags & BB_VISITED)
1211 old = set_new (false);
1212 set_copy (old, ANTIC_IN (block));
1213 ANTIC_OUT = set_new (true);
1215 /* If the block has no successors, ANTIC_OUT is empty, because it is
1217 if (block->succ == NULL);
1219 /* If we have one successor, we could have some phi nodes to
1220 translate through. */
1221 else if (block->succ->succ_next == NULL)
1223 phi_translate_set (ANTIC_OUT, ANTIC_IN(block->succ->dest),
1224 block, block->succ->dest);
1226 /* If we have multiple successors, we take the intersection of all of
1230 varray_type worklist;
1233 basic_block bprime, first;
1235 VARRAY_BB_INIT (worklist, 1, "succ");
1239 VARRAY_PUSH_BB (worklist, e->dest);
1242 first = VARRAY_BB (worklist, 0);
1243 set_copy (ANTIC_OUT, ANTIC_IN (first));
1245 for (i = 1; i < VARRAY_ACTIVE_SIZE (worklist); i++)
1247 bprime = VARRAY_BB (worklist, i);
1248 node = ANTIC_OUT->head;
1252 value_set_node_t next = node->next;
1253 val = get_value_handle (node->expr);
1254 if (!set_contains_value (ANTIC_IN (bprime), val))
1255 set_remove (ANTIC_OUT, node->expr);
1259 VARRAY_CLEAR (worklist);
1262 /* Generate ANTIC_OUT - TMP_GEN */
1263 S = set_subtract (ANTIC_OUT, TMP_GEN (block), false);
1265 /* Start ANTIC_IN with EXP_GEN - TMP_GEN */
1266 ANTIC_IN (block) = set_subtract (EXP_GEN (block),TMP_GEN (block), true);
1268 /* Then union in the ANTIC_OUT - TMP_GEN values, to get ANTIC_OUT U
1269 EXP_GEN - TMP_GEN */
1270 for (node = S->head;
1274 value_insert_into_set (ANTIC_IN (block), node->expr);
1276 clean (ANTIC_IN (block));
1279 if (!set_equal (old, ANTIC_IN (block)))
1283 if (dump_file && (dump_flags & TDF_DETAILS))
1286 print_value_set (dump_file, ANTIC_OUT, "ANTIC_OUT", block->index);
1287 print_value_set (dump_file, ANTIC_IN (block), "ANTIC_IN", block->index);
1289 print_value_set (dump_file, S, "S", block->index);
1293 for (son = first_dom_son (CDI_POST_DOMINATORS, block);
1295 son = next_dom_son (CDI_POST_DOMINATORS, son))
1297 changed |= compute_antic_aux (son);
1302 /* Compute ANTIC sets. */
1305 compute_antic (void)
1307 bool changed = true;
1309 int num_iterations = 0;
1312 ANTIC_IN (bb) = set_new (true);
1313 if (bb->flags & BB_VISITED)
1321 changed = compute_antic_aux (EXIT_BLOCK_PTR);
1325 bb->flags &= ~BB_VISITED;
1327 if (num_iterations > 2 && dump_file && (dump_flags & TDF_STATS))
1328 fprintf (dump_file, "compute_antic required %d iterations\n", num_iterations);
1331 /* Get the expressions represented by value VAL. */
1334 get_expr_set (tree val)
1336 var_ann_t va = var_ann (val);
1337 return va->expr_set;
1341 /* Find a leader for an expression, or generate one using
1342 create_expression_by_pieces if it's ANTIC but
1344 BLOCK is the basic_block we are looking for leaders in.
1345 EXPR is the expression to find a leader or generate for.
1346 STMTS is the statement list to put the inserted expressions on.
1347 Returns the SSA_NAME of the LHS of the generated expression or the
1351 find_or_generate_expression (basic_block block, tree expr, tree stmts)
1354 genop = find_leader (AVAIL_OUT (block), expr);
1355 /* Depending on the order we process DOM branches in, the value
1356 may not have propagated to all the dom children yet during
1357 this iteration. In this case, the value will always be in
1358 the NEW_SETS for us already, having been propogated from our
1361 genop = find_leader (NEW_SETS (block), expr);
1362 /* If it's still NULL, see if it is a complex expression, and if
1363 so, generate it recursively, otherwise, abort, because it's
1367 genop = get_expr_set (expr)->head->expr;
1368 if (TREE_CODE_CLASS (TREE_CODE (genop)) != '1'
1369 && TREE_CODE_CLASS (TREE_CODE (genop)) != '2')
1371 genop = create_expression_by_pieces (block, genop, stmts);
1377 /* Create an expression in pieces, so that we can handle very complex
1378 expressions that may be ANTIC, but not necessary GIMPLE.
1379 BLOCK is the basic block the expression will be inserted into,
1380 EXPR is the expression to insert (in value form)
1381 STMTS is a statement list to append the necessary insertions into.
1383 This function will abort if we hit some value that shouldn't be
1384 ANTIC but is (IE there is no leader for it, or its components).
1385 This function may also generate expressions that are themselves
1386 partially or fully redundant. Those that are will be either made
1387 fully redundant during the next iteration of insert (for partially
1388 redundant ones), or eliminated by eliminate (for fully redundant
1392 create_expression_by_pieces (basic_block block, tree expr, tree stmts)
1394 tree name = NULL_TREE;
1395 tree newexpr = NULL_TREE;
1398 switch (TREE_CODE_CLASS (TREE_CODE (expr)))
1402 tree_stmt_iterator tsi;
1403 tree genop1, genop2;
1405 tree op1 = TREE_OPERAND (expr, 0);
1406 tree op2 = TREE_OPERAND (expr, 1);
1407 genop1 = find_or_generate_expression (block, op1, stmts);
1408 genop2 = find_or_generate_expression (block, op2, stmts);
1409 temp = create_tmp_var (TREE_TYPE (expr), "pretmp");
1410 add_referenced_tmp_var (temp);
1411 newexpr = build (TREE_CODE (expr), TREE_TYPE (expr),
1413 newexpr = build (MODIFY_EXPR, TREE_TYPE (expr),
1415 name = make_ssa_name (temp, newexpr);
1416 TREE_OPERAND (newexpr, 0) = name;
1417 tsi = tsi_last (stmts);
1418 tsi_link_after (&tsi, newexpr, TSI_CONTINUE_LINKING);
1419 pre_stats.insertions++;
1424 tree_stmt_iterator tsi;
1427 tree op1 = TREE_OPERAND (expr, 0);
1428 genop1 = find_or_generate_expression (block, op1, stmts);
1429 temp = create_tmp_var (TREE_TYPE (expr), "pretmp");
1430 add_referenced_tmp_var (temp);
1431 newexpr = build (TREE_CODE (expr), TREE_TYPE (expr),
1433 newexpr = build (MODIFY_EXPR, TREE_TYPE (expr),
1435 name = make_ssa_name (temp, newexpr);
1436 TREE_OPERAND (newexpr, 0) = name;
1437 tsi = tsi_last (stmts);
1438 tsi_link_after (&tsi, newexpr, TSI_CONTINUE_LINKING);
1439 pre_stats.insertions++;
1447 v = get_value_handle (expr);
1448 add (value_table, name, v);
1449 insert_into_set (NEW_SETS (block), name);
1450 value_insert_into_set (AVAIL_OUT (block), name);
1451 if (dump_file && (dump_flags & TDF_DETAILS))
1453 fprintf (dump_file, "Inserted ");
1454 print_generic_expr (dump_file, newexpr, 0);
1455 fprintf (dump_file, " in predecessor %d\n", block->index);
1460 /* Perform insertion of partially redundant values.
1461 For BLOCK, do the following:
1462 1. Propagate the NEW_SETS of the dominator into the current block.
1463 If the block has multiple predecessors,
1464 2a. Iterate over the ANTIC expressions for the block to see if
1465 any of them are partially redundant.
1466 2b. If so, insert them into the necessary predecessors to make
1467 the expression fully redundant.
1468 2c. Insert a new PHI merging the values of the predecessors.
1469 2d. Insert the new PHI, and the new expressions, into the
1471 3. Recursively call ourselves on the dominator children of BLOCK.
1475 insert_aux (basic_block block)
1478 bool new_stuff = false;
1484 dom = get_immediate_dominator (CDI_DOMINATORS, block);
1487 e = NEW_SETS (dom)->head;
1490 insert_into_set (NEW_SETS (block), e->expr);
1491 value_replace_in_set (AVAIL_OUT (block), e->expr);
1494 if (block->pred->pred_next)
1496 value_set_node_t node;
1497 for (node = ANTIC_IN (block)->head;
1501 if (TREE_CODE_CLASS (TREE_CODE (node->expr)) == '2'
1502 || TREE_CODE_CLASS (TREE_CODE (node->expr)) == '1')
1506 bool by_some = false;
1507 bool cant_insert = false;
1508 bool all_same = true;
1509 tree first_s = NULL;
1514 val = get_value_handle (node->expr);
1515 if (set_contains_value (PHI_GEN (block), val))
1517 if (set_contains_value (AVAIL_OUT (dom), val))
1519 if (dump_file && (dump_flags & TDF_DETAILS))
1520 fprintf (dump_file, "Found fully redundant value\n");
1524 avail = xcalloc (last_basic_block, sizeof (tree));
1525 for (pred = block->pred;
1527 pred = pred->pred_next)
1532 eprime = phi_translate (node->expr,
1536 /* eprime will generally only be NULL if the
1537 value of the expression, translated
1538 through the PHI for this predecessor, is
1539 undefined. If that is the case, we can't
1540 make the expression fully redundant,
1541 because its value is undefined along a
1542 predecessor path. We can thus break out
1543 early because it doesn't matter what the
1544 rest of the results are. */
1551 vprime = get_value_handle (eprime);
1554 edoubleprime = find_leader (AVAIL_OUT (bprime),
1556 if (edoubleprime == NULL)
1558 avail[bprime->index] = eprime;
1563 avail[bprime->index] = edoubleprime;
1565 if (first_s == NULL)
1566 first_s = edoubleprime;
1567 else if (first_s != edoubleprime)
1569 if (first_s != edoubleprime
1570 && operand_equal_p (first_s, edoubleprime, 0))
1574 /* If we can insert it, it's not the same value
1575 already existing along every predecessor, and
1576 it's defined by some predecessor, it is
1577 partially redundant. */
1578 if (!cant_insert && !all_same && by_some)
1580 tree type = TREE_TYPE (avail[block->pred->src->index]);
1582 if (dump_file && (dump_flags & TDF_DETAILS))
1584 fprintf (dump_file, "Found partial redundancy for expression ");
1585 print_generic_expr (dump_file, node->expr, 0);
1586 fprintf (dump_file, "\n");
1589 /* Make the necessary insertions. */
1590 for (pred = block->pred;
1592 pred = pred->pred_next)
1594 tree stmts = alloc_stmt_list ();
1597 eprime = avail[bprime->index];
1598 if (TREE_CODE_CLASS (TREE_CODE (eprime)) == '2'
1599 || TREE_CODE_CLASS (TREE_CODE (eprime)) == '1')
1601 builtexpr = create_expression_by_pieces (bprime,
1604 bsi_insert_on_edge (pred, stmts);
1605 bsi_commit_edge_inserts (NULL);
1606 avail[bprime->index] = builtexpr;
1609 /* Now build a phi for the new variable. */
1610 temp = create_tmp_var (type, "prephitmp");
1611 add_referenced_tmp_var (temp);
1612 temp = create_phi_node (temp, block);
1613 add (value_table, PHI_RESULT (temp), val);
1616 if (!set_contains_value (AVAIL_OUT (block), val))
1617 insert_into_set (AVAIL_OUT (block),
1621 value_replace_in_set (AVAIL_OUT (block),
1623 for (pred = block->pred;
1625 pred = pred->pred_next)
1627 add_phi_arg (&temp, avail[pred->src->index],
1630 if (dump_file && (dump_flags & TDF_DETAILS))
1632 fprintf (dump_file, "Created phi ");
1633 print_generic_expr (dump_file, temp, 0);
1634 fprintf (dump_file, " in block %d\n", block->index);
1638 insert_into_set (NEW_SETS (block),
1640 insert_into_set (PHI_GEN (block),
1650 for (son = first_dom_son (CDI_DOMINATORS, block);
1652 son = next_dom_son (CDI_DOMINATORS, son))
1654 new_stuff |= insert_aux (son);
1660 /* Perform insertion of partially redundant values. */
1665 bool new_stuff = true;
1667 int num_iterations = 0;
1670 NEW_SETS (bb) = set_new (true);
1676 new_stuff = insert_aux (ENTRY_BLOCK_PTR);
1678 if (num_iterations > 2 && dump_file && (dump_flags & TDF_STATS))
1679 fprintf (dump_file, "insert required %d iterations\n", num_iterations);
1682 /* Return true if EXPR has no defining statement in this procedure,
1683 *AND* isn't a live-on-entry parameter. */
1685 is_undefined_value (tree expr)
1688 #ifdef ENABLE_CHECKING
1689 /* We should never be handed DECL's */
1693 if (TREE_CODE (expr) == SSA_NAME)
1695 /* XXX: Is this the correct test? */
1696 if (TREE_CODE (SSA_NAME_VAR (expr)) == PARM_DECL)
1698 if (IS_EMPTY_STMT (SSA_NAME_DEF_STMT (expr)))
1704 /* Compute the AVAIL set for BLOCK.
1705 This function performs value numbering of the statements in BLOCK.
1706 The AVAIL sets are built from information we glean while doing this
1707 value numbering, since the AVAIL sets contain only entry per
1711 AVAIL_IN[BLOCK] = AVAIL_OUT[dom(BLOCK)].
1712 AVAIL_OUT[BLOCK] = AVAIL_IN[BLOCK] U PHI_GEN[BLOCK] U
1717 compute_avail (basic_block block)
1721 /* For arguments with default definitions, we pretend they are
1722 defined in the entry block. */
1723 if (block == ENTRY_BLOCK_PTR)
1726 for (param = DECL_ARGUMENTS (current_function_decl);
1728 param = TREE_CHAIN (param))
1730 if (default_def (param) != NULL)
1733 tree def = default_def (param);
1734 val = lookup_or_add (value_table, def);
1735 insert_into_set (TMP_GEN (block), def);
1736 value_insert_into_set (AVAIL_OUT (block), def);
1742 block_stmt_iterator bsi;
1746 dom = get_immediate_dominator (CDI_DOMINATORS, block);
1748 set_copy (AVAIL_OUT (block), AVAIL_OUT (dom));
1749 for (phi = phi_nodes (block); phi; phi = PHI_CHAIN (phi))
1751 /* Ignore virtual PHIs until we can do PRE on expressions
1752 with virtual operands. */
1753 if (!is_gimple_reg (SSA_NAME_VAR (PHI_RESULT (phi))))
1756 lookup_or_add (value_table, PHI_RESULT (phi));
1757 value_insert_into_set (AVAIL_OUT (block), PHI_RESULT (phi));
1758 insert_into_set (PHI_GEN (block), PHI_RESULT (phi));
1761 for (bsi = bsi_start (block); !bsi_end_p (bsi); bsi_next (&bsi))
1764 stmt = bsi_stmt (bsi);
1765 get_stmt_operands (stmt);
1767 if (NUM_VUSES (STMT_VUSE_OPS (stmt))
1768 || NUM_V_MUST_DEFS (STMT_V_MUST_DEF_OPS (stmt))
1769 || NUM_V_MAY_DEFS (STMT_V_MAY_DEF_OPS (stmt))
1770 || stmt_ann (stmt)->has_volatile_ops)
1773 for (j = 0; j < NUM_DEFS (STMT_DEF_OPS (stmt)); j++)
1775 tree def = DEF_OP (STMT_DEF_OPS (stmt), j);
1776 lookup_or_add (value_table, def);
1777 insert_into_set (TMP_GEN (block), def);
1778 value_insert_into_set (AVAIL_OUT (block), def);
1780 for (j = 0; j < NUM_USES (STMT_USE_OPS (stmt)); j++)
1782 tree use = USE_OP (STMT_USE_OPS (stmt), j);
1783 if (TREE_CODE (use) == SSA_NAME)
1785 lookup_or_add (value_table, use);
1786 insert_into_set (TMP_GEN (block), use);
1787 value_insert_into_set (AVAIL_OUT (block), use);
1793 if (TREE_CODE (stmt) == MODIFY_EXPR)
1795 op0 = TREE_OPERAND (stmt, 0);
1796 if (TREE_CODE (op0) != SSA_NAME)
1798 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op0))
1800 op1 = TREE_OPERAND (stmt, 1);
1801 STRIP_USELESS_TYPE_CONVERSION (op1);
1802 if (is_gimple_min_invariant (op1))
1804 add (value_table, op0, lookup_or_add (value_table, op1));
1805 insert_into_set (TMP_GEN (block), op0);
1806 value_insert_into_set (AVAIL_OUT (block), op0);
1808 else if (TREE_CODE_CLASS (TREE_CODE (op1)) == '2')
1811 tree val, val1, val2;
1813 bop1 = TREE_OPERAND (op1, 0);
1814 bop2 = TREE_OPERAND (op1, 1);
1815 val1 = lookup_or_add (value_table, bop1);
1816 val2 = lookup_or_add (value_table, bop2);
1818 newt = pool_alloc (binary_node_pool);
1819 memcpy (newt, op1, tree_size (op1));
1820 TREE_OPERAND (newt, 0) = val1;
1821 TREE_OPERAND (newt, 1) = val2;
1822 val = lookup_or_add (value_table, newt);
1823 add (value_table, op0, val);
1824 if (!is_undefined_value (bop1))
1825 value_insert_into_set (EXP_GEN (block), bop1);
1826 if (!is_undefined_value (bop2))
1827 value_insert_into_set (EXP_GEN (block), bop2);
1828 value_insert_into_set (EXP_GEN (block), newt);
1829 insert_into_set (TMP_GEN (block), op0);
1830 value_insert_into_set (AVAIL_OUT (block), op0);
1832 else if (TREE_CODE_CLASS (TREE_CODE (op1)) == '1'
1833 && !is_gimple_cast (op1))
1838 uop = TREE_OPERAND (op1, 0);
1839 val1 = lookup_or_add (value_table, uop);
1840 newt = pool_alloc (unary_node_pool);
1841 memcpy (newt, op1, tree_size (op1));
1842 TREE_OPERAND (newt, 0) = val1;
1843 val = lookup_or_add (value_table, newt);
1844 add (value_table, op0, val);
1845 if (!is_undefined_value (uop))
1846 value_insert_into_set (EXP_GEN (block), uop);
1847 value_insert_into_set (EXP_GEN (block), newt);
1848 insert_into_set (TMP_GEN (block), op0);
1849 value_insert_into_set (AVAIL_OUT (block), op0);
1851 else if (TREE_CODE (op1) == SSA_NAME)
1853 tree val = lookup_or_add (value_table, op1);
1854 add (value_table, op0, val);
1855 if (!is_undefined_value (op1))
1856 value_insert_into_set (EXP_GEN (block), op1);
1857 insert_into_set (TMP_GEN (block), op0);
1858 value_insert_into_set (AVAIL_OUT (block), op0);
1863 for (j = 0; j < NUM_DEFS (STMT_DEF_OPS (stmt)); j++)
1865 tree def = DEF_OP (STMT_DEF_OPS (stmt), j);
1866 lookup_or_add (value_table, def);
1867 insert_into_set (TMP_GEN (block), def);
1868 value_insert_into_set (AVAIL_OUT (block), def);
1872 for (j = 0; j < NUM_USES (STMT_USE_OPS (stmt)); j++)
1874 tree use = USE_OP (STMT_USE_OPS (stmt), j);
1875 if (TREE_CODE (use) == SSA_NAME)
1877 lookup_or_add (value_table, use);
1878 insert_into_set (TMP_GEN (block), use);
1879 value_insert_into_set (AVAIL_OUT (block), use);
1887 for (j = 0; j < NUM_DEFS (STMT_DEF_OPS (stmt)); j++)
1889 tree def = DEF_OP (STMT_DEF_OPS (stmt), j);
1890 lookup_or_add (value_table, def);
1891 insert_into_set (TMP_GEN (block), def);
1892 value_insert_into_set (AVAIL_OUT (block), def);
1894 for (j = 0; j < NUM_USES (STMT_USE_OPS (stmt)); j++)
1896 tree use = USE_OP (STMT_USE_OPS (stmt), j);
1897 if (TREE_CODE (use) == SSA_NAME)
1899 lookup_or_add (value_table, use);
1900 insert_into_set (TMP_GEN (block), use);
1901 value_insert_into_set (AVAIL_OUT (block), use);
1907 for (son = first_dom_son (CDI_DOMINATORS, block);
1909 son = next_dom_son (CDI_DOMINATORS, son))
1910 compute_avail (son);
1914 /* Eliminate fully redundant computations. */
1923 block_stmt_iterator i;
1925 for (i = bsi_start (b); !bsi_end_p (i); bsi_next (&i))
1927 tree stmt = bsi_stmt (i);
1929 if (NUM_VUSES (STMT_VUSE_OPS (stmt))
1930 || NUM_V_MUST_DEFS (STMT_V_MUST_DEF_OPS (stmt))
1931 || NUM_V_MAY_DEFS (STMT_V_MAY_DEF_OPS (stmt))
1932 || stmt_ann (stmt)->has_volatile_ops)
1934 /* Lookup the RHS of the expression, see if we have an
1935 available computation for it. If so, replace the RHS with
1936 the available computation. */
1937 if (TREE_CODE (stmt) == MODIFY_EXPR)
1939 tree t = TREE_OPERAND (stmt, 0);
1940 tree expr = TREE_OPERAND (stmt, 1);
1942 /* There is no point in eliminating NOP_EXPR, it isn't
1943 supposed to generate any code. */
1944 if (TREE_CODE (expr) == NOP_EXPR
1945 || (TREE_CODE_CLASS (TREE_CODE (expr)) != '2'
1946 && TREE_CODE_CLASS (TREE_CODE (expr)) != '1'))
1948 sprime = find_leader (AVAIL_OUT (b),
1949 lookup (value_table, t));
1952 && may_propagate_copy (sprime, TREE_OPERAND (stmt, 1)))
1954 if (dump_file && (dump_flags & TDF_DETAILS))
1956 fprintf (dump_file, "Replaced ");
1957 print_generic_expr (dump_file, expr, 0);
1958 fprintf (dump_file, " with ");
1959 print_generic_expr (dump_file, sprime, 0);
1960 fprintf (dump_file, " in ");
1961 print_generic_stmt (dump_file, stmt, 0);
1963 pre_stats.eliminations++;
1964 propagate_tree_value (&TREE_OPERAND (stmt, 1), sprime);
1973 /* Main entry point to the SSA-PRE pass.
1975 PHASE indicates which dump file from the DUMP_FILES array to use when
1976 dumping debugging information. */
1983 pre_uid = num_referenced_vars;
1984 memset (&pre_stats, 0, sizeof (pre_stats));
1987 bb->aux = xcalloc (1, sizeof (struct bb_value_sets));
1989 phi_translate_table = htab_create (511, expr_pred_trans_hash,
1992 value_table = htab_create (511, val_expr_pair_hash,
1993 val_expr_pair_expr_eq, free);
1994 value_set_pool = create_alloc_pool ("Value sets",
1995 sizeof (struct value_set), 30);
1996 value_set_node_pool = create_alloc_pool ("Value set nodes",
1997 sizeof (struct value_set_node), 30);
1998 calculate_dominance_info (CDI_POST_DOMINATORS);
1999 calculate_dominance_info (CDI_DOMINATORS);
2000 tsize = tree_size (build (PLUS_EXPR, void_type_node, NULL_TREE,
2002 binary_node_pool = create_alloc_pool ("Binary tree nodes", tsize, 30);
2003 tsize = tree_size (build1 (NEGATE_EXPR, void_type_node, NULL_TREE));
2004 unary_node_pool = create_alloc_pool ("Unary tree nodes", tsize, 30);
2008 EXP_GEN (bb) = set_new (true);
2009 PHI_GEN (bb) = set_new (true);
2010 TMP_GEN (bb) = set_new (false);
2011 AVAIL_OUT (bb) = set_new (true);
2014 compute_avail (ENTRY_BLOCK_PTR);
2016 if (dump_file && (dump_flags & TDF_DETAILS))
2020 print_value_set (dump_file, EXP_GEN (bb), "exp_gen", bb->index);
2021 print_value_set (dump_file, TMP_GEN (bb), "tmp_gen", bb->index);
2022 print_value_set (dump_file, AVAIL_OUT (bb), "avail_out", bb->index);
2026 /* Insert can get quite slow on an incredibly large number of basic
2027 blocks due to some quadratic behavior. Until this behavior is
2028 fixed, don't run it when he have an incredibly large number of
2029 bb's. If we aren't going to run insert, there is no point in
2030 computing ANTIC, either, even though it's plenty fast. */
2032 if (n_basic_blocks < 4000)
2040 if (dump_file && (dump_flags & TDF_STATS))
2042 fprintf (dump_file, "Insertions:%d\n", pre_stats.insertions);
2043 fprintf (dump_file, "New PHIs:%d\n", pre_stats.phis);
2044 fprintf (dump_file, "Eliminated:%d\n", pre_stats.eliminations);
2047 free_alloc_pool (value_set_pool);
2048 free_alloc_pool (value_set_node_pool);
2049 free_alloc_pool (binary_node_pool);
2050 free_alloc_pool (unary_node_pool);
2051 htab_delete (value_table);
2052 htab_delete (phi_translate_table);
2059 free_dominance_info (CDI_POST_DOMINATORS);
2065 return flag_tree_pre != 0;
2068 struct tree_opt_pass pass_pre =
2071 gate_pre, /* gate */
2072 execute_pre, /* execute */
2075 0, /* static_pass_number */
2076 TV_TREE_PRE, /* tv_id */
2077 PROP_no_crit_edges | PROP_cfg | PROP_ssa,/* properties_required */
2078 0, /* properties_provided */
2079 0, /* properties_destroyed */
2080 0, /* todo_flags_start */
2081 TODO_dump_func | TODO_ggc_collect | TODO_verify_ssa /* todo_flags_finish */