2 Copyright (C) 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc.
3 Contributed by Daniel Berlin <dan@dberlin.org> and Steven Bosscher
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify
9 it under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 2, or (at your option)
13 GCC is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 GNU General Public License for more details.
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING. If not, write to
20 the Free Software Foundation, 51 Franklin Street, Fifth Floor,
21 Boston, MA 02110-1301, USA. */
25 #include "coretypes.h"
29 #include "basic-block.h"
30 #include "diagnostic.h"
31 #include "tree-inline.h"
32 #include "tree-flow.h"
33 #include "tree-gimple.h"
34 #include "tree-dump.h"
38 #include "tree-iterator.h"
40 #include "alloc-pool.h"
41 #include "tree-pass.h"
44 #include "langhooks.h"
49 1. Avail sets can be shared by making an avail_find_leader that
50 walks up the dominator tree and looks in those avail sets.
51 This might affect code optimality, it's unclear right now.
52 2. Strength reduction can be performed by anticipating expressions
53 we can repair later on.
54 3. We can do back-substitution or smarter value numbering to catch
55 commutative expressions split up over multiple statements.
56 4. ANTIC_SAFE_LOADS could be a lot smarter than it is now.
57 Right now, it is simply calculating loads that occur before
58 any store in a block, instead of loads that occur before
59 stores that affect them. This is relatively more expensive, and
60 it's not clear how much more it will buy us.
63 /* For ease of terminology, "expression node" in the below refers to
64 every expression node but MODIFY_EXPR, because MODIFY_EXPR's represent
65 the actual statement containing the expressions we care about, and
66 we cache the value number by putting it in the expression. */
70 First we walk the statements to generate the AVAIL sets, the
71 EXP_GEN sets, and the tmp_gen sets. EXP_GEN sets represent the
72 generation of values/expressions by a given block. We use them
73 when computing the ANTIC sets. The AVAIL sets consist of
74 SSA_NAME's that represent values, so we know what values are
75 available in what blocks. AVAIL is a forward dataflow problem. In
76 SSA, values are never killed, so we don't need a kill set, or a
77 fixpoint iteration, in order to calculate the AVAIL sets. In
78 traditional parlance, AVAIL sets tell us the downsafety of the
81 Next, we generate the ANTIC sets. These sets represent the
82 anticipatable expressions. ANTIC is a backwards dataflow
83 problem.An expression is anticipatable in a given block if it could
84 be generated in that block. This means that if we had to perform
85 an insertion in that block, of the value of that expression, we
86 could. Calculating the ANTIC sets requires phi translation of
87 expressions, because the flow goes backwards through phis. We must
88 iterate to a fixpoint of the ANTIC sets, because we have a kill
89 set. Even in SSA form, values are not live over the entire
90 function, only from their definition point onwards. So we have to
91 remove values from the ANTIC set once we go past the definition
92 point of the leaders that make them up.
93 compute_antic/compute_antic_aux performs this computation.
95 Third, we perform insertions to make partially redundant
96 expressions fully redundant.
98 An expression is partially redundant (excluding partial
101 1. It is AVAIL in some, but not all, of the predecessors of a
103 2. It is ANTIC in all the predecessors.
105 In order to make it fully redundant, we insert the expression into
106 the predecessors where it is not available, but is ANTIC.
107 insert/insert_aux performs this insertion.
109 Fourth, we eliminate fully redundant expressions.
110 This is a simple statement walk that replaces redundant
111 calculations with the now available values. */
113 /* Representations of value numbers:
115 Value numbers are represented using the "value handle" approach.
116 This means that each SSA_NAME (and for other reasons to be
117 disclosed in a moment, expression nodes) has a value handle that
118 can be retrieved through get_value_handle. This value handle, *is*
119 the value number of the SSA_NAME. You can pointer compare the
120 value handles for equivalence purposes.
122 For debugging reasons, the value handle is internally more than
123 just a number, it is a VAR_DECL named "value.x", where x is a
124 unique number for each value number in use. This allows
125 expressions with SSA_NAMES replaced by value handles to still be
126 pretty printed in a sane way. They simply print as "value.3 *
129 Expression nodes have value handles associated with them as a
130 cache. Otherwise, we'd have to look them up again in the hash
131 table This makes significant difference (factor of two or more) on
132 some test cases. They can be thrown away after the pass is
135 /* Representation of expressions on value numbers:
137 In some portions of this code, you will notice we allocate "fake"
138 analogues to the expression we are value numbering, and replace the
139 operands with the values of the expression. Since we work on
140 values, and not just names, we canonicalize expressions to value
141 expressions for use in the ANTIC sets, the EXP_GEN set, etc.
143 This is theoretically unnecessary, it just saves a bunch of
144 repeated get_value_handle and find_leader calls in the remainder of
145 the code, trading off temporary memory usage for speed. The tree
146 nodes aren't actually creating more garbage, since they are
147 allocated in a special pools which are thrown away at the end of
150 All of this also means that if you print the EXP_GEN or ANTIC sets,
151 you will see "value.5 + value.7" in the set, instead of "a_55 +
152 b_66" or something. The only thing that actually cares about
153 seeing the value leaders is phi translation, and it needs to be
154 able to find the leader for a value in an arbitrary block, so this
155 "value expression" form is perfect for it (otherwise you'd do
156 get_value_handle->find_leader->translate->get_value_handle->find_leader).*/
159 /* Representation of sets:
161 There are currently two types of sets used, hopefully to be unified soon.
162 The AVAIL sets do not need to be sorted in any particular order,
163 and thus, are simply represented as two bitmaps, one that keeps
164 track of values present in the set, and one that keeps track of
165 expressions present in the set.
167 The other sets are represented as doubly linked lists kept in topological
168 order, with an optional supporting bitmap of values present in the
169 set. The sets represent values, and the elements can be values or
170 expressions. The elements can appear in different sets, but each
171 element can only appear once in each set.
173 Since each node in the set represents a value, we also want to be
174 able to map expression, set pairs to something that tells us
175 whether the value is present is a set. We use a per-set bitmap for
176 that. The value handles also point to a linked list of the
177 expressions they represent via a tree annotation. This is mainly
178 useful only for debugging, since we don't do identity lookups. */
181 static bool in_fre = false;
183 /* A value set element. Basically a single linked list of
184 expressions/values. */
185 typedef struct value_set_node
190 /* A pointer to the next element of the value set. */
191 struct value_set_node *next;
195 /* A value set. This is a singly linked list of value_set_node
196 elements with a possible bitmap that tells us what values exist in
197 the set. This set must be kept in topologically sorted order. */
198 typedef struct value_set
200 /* The head of the list. Used for iterating over the list in
202 value_set_node_t head;
204 /* The tail of the list. Used for tail insertions, which are
205 necessary to keep the set in topologically sorted order because
206 of how the set is built. */
207 value_set_node_t tail;
209 /* The length of the list. */
212 /* True if the set is indexed, which means it contains a backing
213 bitmap for quick determination of whether certain values exist in the
217 /* The bitmap of values that exist in the set. May be NULL in an
218 empty or non-indexed set. */
224 /* An unordered bitmap set. One bitmap tracks values, the other,
226 typedef struct bitmap_set
232 /* Sets that we need to keep track of. */
233 typedef struct bb_value_sets
235 /* The EXP_GEN set, which represents expressions/values generated in
239 /* The PHI_GEN set, which represents PHI results generated in a
241 bitmap_set_t phi_gen;
243 /* The TMP_GEN set, which represents results/temporaries generated
244 in a basic block. IE the LHS of an expression. */
245 bitmap_set_t tmp_gen;
247 /* The AVAIL_OUT set, which represents which values are available in
248 a given basic block. */
249 bitmap_set_t avail_out;
251 /* The ANTIC_IN set, which represents which values are anticipatable
252 in a given basic block. */
253 value_set_t antic_in;
255 /* The NEW_SETS set, which is used during insertion to augment the
256 AVAIL_OUT set of blocks with the new insertions performed during
257 the current iteration. */
258 bitmap_set_t new_sets;
260 /* The RVUSE sets, which are used during ANTIC computation to ensure
261 that we don't mark loads ANTIC once they have died. */
267 /* For actually occurring loads, as long as they occur before all the
268 other stores in the block, we know they are antic at the top of
269 the block, regardless of RVUSE_KILL. */
270 value_set_t antic_safe_loads;
273 #define EXP_GEN(BB) ((bb_value_sets_t) ((BB)->aux))->exp_gen
274 #define PHI_GEN(BB) ((bb_value_sets_t) ((BB)->aux))->phi_gen
275 #define TMP_GEN(BB) ((bb_value_sets_t) ((BB)->aux))->tmp_gen
276 #define AVAIL_OUT(BB) ((bb_value_sets_t) ((BB)->aux))->avail_out
277 #define ANTIC_IN(BB) ((bb_value_sets_t) ((BB)->aux))->antic_in
278 #define RVUSE_IN(BB) ((bb_value_sets_t) ((BB)->aux))->rvuse_in
279 #define RVUSE_GEN(BB) ((bb_value_sets_t) ((BB)->aux))->rvuse_gen
280 #define RVUSE_KILL(BB) ((bb_value_sets_t) ((BB)->aux))->rvuse_kill
281 #define RVUSE_OUT(BB) ((bb_value_sets_t) ((BB)->aux))->rvuse_out
282 #define NEW_SETS(BB) ((bb_value_sets_t) ((BB)->aux))->new_sets
283 #define ANTIC_SAFE_LOADS(BB) ((bb_value_sets_t) ((BB)->aux))->antic_safe_loads
285 /* This structure is used to keep track of statistics on what
286 optimization PRE was able to perform. */
289 /* The number of RHS computations eliminated by PRE. */
292 /* The number of new expressions/temporaries generated by PRE. */
295 /* The number of new PHI nodes added by PRE. */
298 /* The number of values found constant. */
304 static tree bitmap_find_leader (bitmap_set_t, tree);
305 static tree find_leader (value_set_t, tree);
306 static void value_insert_into_set (value_set_t, tree);
307 static void bitmap_value_insert_into_set (bitmap_set_t, tree);
308 static void bitmap_value_replace_in_set (bitmap_set_t, tree);
309 static void insert_into_set (value_set_t, tree);
310 static void bitmap_set_copy (bitmap_set_t, bitmap_set_t);
311 static bool bitmap_set_contains_value (bitmap_set_t, tree);
312 static bitmap_set_t bitmap_set_new (void);
313 static value_set_t set_new (bool);
314 static bool is_undefined_value (tree);
315 static tree create_expression_by_pieces (basic_block, tree, tree);
316 static tree find_or_generate_expression (basic_block, tree, tree);
319 /* We can add and remove elements and entries to and from sets
320 and hash tables, so we use alloc pools for them. */
322 static alloc_pool value_set_pool;
323 static alloc_pool bitmap_set_pool;
324 static alloc_pool value_set_node_pool;
325 static alloc_pool binary_node_pool;
326 static alloc_pool unary_node_pool;
327 static alloc_pool reference_node_pool;
328 static alloc_pool comparison_node_pool;
329 static alloc_pool expression_node_pool;
330 static alloc_pool list_node_pool;
331 static alloc_pool modify_expr_node_pool;
332 static bitmap_obstack grand_bitmap_obstack;
334 /* To avoid adding 300 temporary variables when we only need one, we
335 only create one temporary variable, on demand, and build ssa names
336 off that. We do have to change the variable if the types don't
337 match the current variable's type. */
339 static tree storetemp;
340 static tree mergephitemp;
341 static tree prephitemp;
343 /* Set of blocks with statements that have had its EH information
345 static bitmap need_eh_cleanup;
347 /* The phi_translate_table caches phi translations for a given
348 expression and predecessor. */
350 static htab_t phi_translate_table;
352 /* A three tuple {e, pred, v} used to cache phi translations in the
353 phi_translate_table. */
355 typedef struct expr_pred_trans_d
357 /* The expression. */
360 /* The predecessor block along which we translated the expression. */
363 /* vuses associated with the expression. */
364 VEC (tree, gc) *vuses;
366 /* The value that resulted from the translation. */
370 /* The hashcode for the expression, pred pair. This is cached for
373 } *expr_pred_trans_t;
375 /* Return the hash value for a phi translation table entry. */
378 expr_pred_trans_hash (const void *p)
380 const expr_pred_trans_t ve = (expr_pred_trans_t) p;
384 /* Return true if two phi translation table entries are the same.
385 P1 and P2 should point to the expr_pred_trans_t's to be compared.*/
388 expr_pred_trans_eq (const void *p1, const void *p2)
390 const expr_pred_trans_t ve1 = (expr_pred_trans_t) p1;
391 const expr_pred_trans_t ve2 = (expr_pred_trans_t) p2;
392 basic_block b1 = ve1->pred;
393 basic_block b2 = ve2->pred;
397 /* If they are not translations for the same basic block, they can't
403 /* If they are for the same basic block, determine if the
404 expressions are equal. */
405 if (!expressions_equal_p (ve1->e, ve2->e))
408 /* Make sure the vuses are equivalent. */
409 if (ve1->vuses == ve2->vuses)
412 if (VEC_length (tree, ve1->vuses) != VEC_length (tree, ve2->vuses))
415 for (i = 0; VEC_iterate (tree, ve1->vuses, i, vuse1); i++)
417 if (VEC_index (tree, ve2->vuses, i) != vuse1)
424 /* Search in the phi translation table for the translation of
425 expression E in basic block PRED with vuses VUSES.
426 Return the translated value, if found, NULL otherwise. */
429 phi_trans_lookup (tree e, basic_block pred, VEC (tree, gc) *vuses)
432 struct expr_pred_trans_d ept;
437 ept.hashcode = vn_compute (e, (unsigned long) pred);
438 slot = htab_find_slot_with_hash (phi_translate_table, &ept, ept.hashcode,
443 return ((expr_pred_trans_t) *slot)->v;
447 /* Add the tuple mapping from {expression E, basic block PRED, vuses VUSES} to
448 value V, to the phi translation table. */
451 phi_trans_add (tree e, tree v, basic_block pred, VEC (tree, gc) *vuses)
454 expr_pred_trans_t new_pair = XNEW (struct expr_pred_trans_d);
456 new_pair->pred = pred;
457 new_pair->vuses = vuses;
459 new_pair->hashcode = vn_compute (e, (unsigned long) pred);
460 slot = htab_find_slot_with_hash (phi_translate_table, new_pair,
461 new_pair->hashcode, INSERT);
464 *slot = (void *) new_pair;
468 /* Add expression E to the expression set of value V. */
471 add_to_value (tree v, tree e)
473 /* Constants have no expression sets. */
474 if (is_gimple_min_invariant (v))
477 if (VALUE_HANDLE_EXPR_SET (v) == NULL)
478 VALUE_HANDLE_EXPR_SET (v) = set_new (false);
480 insert_into_set (VALUE_HANDLE_EXPR_SET (v), e);
484 /* Return true if value V exists in the bitmap for SET. */
487 value_exists_in_set_bitmap (value_set_t set, tree v)
492 return bitmap_bit_p (set->values, VALUE_HANDLE_ID (v));
496 /* Remove value V from the bitmap for SET. */
499 value_remove_from_set_bitmap (value_set_t set, tree v)
501 gcc_assert (set->indexed);
506 bitmap_clear_bit (set->values, VALUE_HANDLE_ID (v));
510 /* Insert the value number V into the bitmap of values existing in
514 value_insert_into_set_bitmap (value_set_t set, tree v)
516 gcc_assert (set->indexed);
518 if (set->values == NULL)
519 set->values = BITMAP_ALLOC (&grand_bitmap_obstack);
521 bitmap_set_bit (set->values, VALUE_HANDLE_ID (v));
525 /* Create a new bitmap set and return it. */
528 bitmap_set_new (void)
530 bitmap_set_t ret = (bitmap_set_t) pool_alloc (bitmap_set_pool);
531 ret->expressions = BITMAP_ALLOC (&grand_bitmap_obstack);
532 ret->values = BITMAP_ALLOC (&grand_bitmap_obstack);
536 /* Create a new set. */
539 set_new (bool indexed)
542 ret = (value_set_t) pool_alloc (value_set_pool);
543 ret->head = ret->tail = NULL;
545 ret->indexed = indexed;
550 /* Insert an expression EXPR into a bitmapped set. */
553 bitmap_insert_into_set (bitmap_set_t set, tree expr)
556 /* XXX: For now, we only let SSA_NAMES into the bitmap sets. */
557 gcc_assert (TREE_CODE (expr) == SSA_NAME);
558 val = get_value_handle (expr);
561 if (!is_gimple_min_invariant (val))
563 bitmap_set_bit (set->values, VALUE_HANDLE_ID (val));
564 bitmap_set_bit (set->expressions, SSA_NAME_VERSION (expr));
568 /* Insert EXPR into SET. */
571 insert_into_set (value_set_t set, tree expr)
573 value_set_node_t newnode = (value_set_node_t) pool_alloc (value_set_node_pool);
574 tree val = get_value_handle (expr);
577 if (is_gimple_min_invariant (val))
580 /* For indexed sets, insert the value into the set value bitmap.
581 For all sets, add it to the linked list and increment the list
584 value_insert_into_set_bitmap (set, val);
586 newnode->next = NULL;
587 newnode->expr = expr;
589 if (set->head == NULL)
591 set->head = set->tail = newnode;
595 set->tail->next = newnode;
600 /* Copy a bitmapped set ORIG, into bitmapped set DEST. */
603 bitmap_set_copy (bitmap_set_t dest, bitmap_set_t orig)
605 bitmap_copy (dest->expressions, orig->expressions);
606 bitmap_copy (dest->values, orig->values);
609 /* Perform bitmapped set operation DEST &= ORIG. */
612 bitmap_set_and (bitmap_set_t dest, bitmap_set_t orig)
616 bitmap temp = BITMAP_ALLOC (&grand_bitmap_obstack);
618 bitmap_and_into (dest->values, orig->values);
619 bitmap_copy (temp, dest->expressions);
620 EXECUTE_IF_SET_IN_BITMAP (temp, 0, i, bi)
622 tree name = ssa_name (i);
623 tree val = get_value_handle (name);
624 if (!bitmap_bit_p (dest->values, VALUE_HANDLE_ID (val)))
625 bitmap_clear_bit (dest->expressions, i);
630 /* Perform bitmapped value set operation DEST = DEST & ~ORIG. */
633 bitmap_set_and_compl (bitmap_set_t dest, bitmap_set_t orig)
637 bitmap temp = BITMAP_ALLOC (&grand_bitmap_obstack);
639 bitmap_and_compl_into (dest->values, orig->values);
640 bitmap_copy (temp, dest->expressions);
641 EXECUTE_IF_SET_IN_BITMAP (temp, 0, i, bi)
643 tree name = ssa_name (i);
644 tree val = get_value_handle (name);
645 if (!bitmap_bit_p (dest->values, VALUE_HANDLE_ID (val)))
646 bitmap_clear_bit (dest->expressions, i);
651 /* Return true if the bitmap set SET is empty. */
654 bitmap_set_empty_p (bitmap_set_t set)
656 return bitmap_empty_p (set->values);
659 /* Copy the set ORIG to the set DEST. */
662 set_copy (value_set_t dest, value_set_t orig)
664 value_set_node_t node;
666 if (!orig || !orig->head)
669 for (node = orig->head;
673 insert_into_set (dest, node->expr);
677 /* Remove EXPR from SET. */
680 set_remove (value_set_t set, tree expr)
682 value_set_node_t node, prev;
684 /* Remove the value of EXPR from the bitmap, decrement the set
685 length, and remove it from the actual double linked list. */
686 value_remove_from_set_bitmap (set, get_value_handle (expr));
689 for (node = set->head;
691 prev = node, node = node->next)
693 if (node->expr == expr)
696 set->head = node->next;
698 prev->next= node->next;
700 if (node == set->tail)
702 pool_free (value_set_node_pool, node);
708 /* Return true if SET contains the value VAL. */
711 set_contains_value (value_set_t set, tree val)
713 /* All constants are in every set. */
714 if (is_gimple_min_invariant (val))
717 if (!set || set->length == 0)
720 return value_exists_in_set_bitmap (set, val);
723 /* Return true if bitmapped set SET contains the expression EXPR. */
725 bitmap_set_contains (bitmap_set_t set, tree expr)
727 /* All constants are in every set. */
728 if (is_gimple_min_invariant (get_value_handle (expr)))
731 /* XXX: Bitmapped sets only contain SSA_NAME's for now. */
732 if (TREE_CODE (expr) != SSA_NAME)
734 return bitmap_bit_p (set->expressions, SSA_NAME_VERSION (expr));
738 /* Return true if bitmapped set SET contains the value VAL. */
741 bitmap_set_contains_value (bitmap_set_t set, tree val)
743 if (is_gimple_min_invariant (val))
745 return bitmap_bit_p (set->values, VALUE_HANDLE_ID (val));
748 /* Replace an instance of value LOOKFOR with expression EXPR in SET. */
751 bitmap_set_replace_value (bitmap_set_t set, tree lookfor, tree expr)
754 value_set_node_t node;
755 if (is_gimple_min_invariant (lookfor))
757 if (!bitmap_set_contains_value (set, lookfor))
760 /* The number of expressions having a given value is usually
761 significantly less than the total number of expressions in SET.
762 Thus, rather than check, for each expression in SET, whether it
763 has the value LOOKFOR, we walk the reverse mapping that tells us
764 what expressions have a given value, and see if any of those
765 expressions are in our set. For large testcases, this is about
766 5-10x faster than walking the bitmap. If this is somehow a
767 significant lose for some cases, we can choose which set to walk
768 based on the set size. */
769 exprset = VALUE_HANDLE_EXPR_SET (lookfor);
770 for (node = exprset->head; node; node = node->next)
772 if (TREE_CODE (node->expr) == SSA_NAME)
774 if (bitmap_bit_p (set->expressions, SSA_NAME_VERSION (node->expr)))
776 bitmap_clear_bit (set->expressions, SSA_NAME_VERSION (node->expr));
777 bitmap_set_bit (set->expressions, SSA_NAME_VERSION (expr));
784 /* Subtract bitmapped set B from value set A, and return the new set. */
787 bitmap_set_subtract_from_value_set (value_set_t a, bitmap_set_t b,
790 value_set_t ret = set_new (indexed);
791 value_set_node_t node;
796 if (!bitmap_set_contains (b, node->expr))
797 insert_into_set (ret, node->expr);
802 /* Return true if two sets are equal. */
805 set_equal (value_set_t a, value_set_t b)
807 value_set_node_t node;
809 if (a->length != b->length)
815 if (!set_contains_value (b, get_value_handle (node->expr)))
821 /* Replace an instance of EXPR's VALUE with EXPR in SET if it exists,
822 and add it otherwise. */
825 bitmap_value_replace_in_set (bitmap_set_t set, tree expr)
827 tree val = get_value_handle (expr);
828 if (bitmap_set_contains_value (set, val))
829 bitmap_set_replace_value (set, val, expr);
831 bitmap_insert_into_set (set, expr);
834 /* Insert EXPR into SET if EXPR's value is not already present in
838 bitmap_value_insert_into_set (bitmap_set_t set, tree expr)
840 tree val = get_value_handle (expr);
842 if (is_gimple_min_invariant (val))
845 if (!bitmap_set_contains_value (set, val))
846 bitmap_insert_into_set (set, expr);
849 /* Insert the value for EXPR into SET, if it doesn't exist already. */
852 value_insert_into_set (value_set_t set, tree expr)
854 tree val = get_value_handle (expr);
856 /* Constant and invariant values exist everywhere, and thus,
857 actually keeping them in the sets is pointless. */
858 if (is_gimple_min_invariant (val))
861 if (!set_contains_value (set, val))
862 insert_into_set (set, expr);
866 /* Print out SET to OUTFILE. */
869 bitmap_print_value_set (FILE *outfile, bitmap_set_t set,
870 const char *setname, int blockindex)
872 fprintf (outfile, "%s[%d] := { ", setname, blockindex);
879 EXECUTE_IF_SET_IN_BITMAP (set->expressions, 0, i, bi)
882 fprintf (outfile, ", ");
884 print_generic_expr (outfile, ssa_name (i), 0);
886 fprintf (outfile, " (");
887 print_generic_expr (outfile, get_value_handle (ssa_name (i)), 0);
888 fprintf (outfile, ") ");
891 fprintf (outfile, " }\n");
893 /* Print out the value_set SET to OUTFILE. */
896 print_value_set (FILE *outfile, value_set_t set,
897 const char *setname, int blockindex)
899 value_set_node_t node;
900 fprintf (outfile, "%s[%d] := { ", setname, blockindex);
903 for (node = set->head;
907 print_generic_expr (outfile, node->expr, 0);
909 fprintf (outfile, " (");
910 print_generic_expr (outfile, get_value_handle (node->expr), 0);
911 fprintf (outfile, ") ");
914 fprintf (outfile, ", ");
918 fprintf (outfile, " }\n");
921 /* Print out the expressions that have VAL to OUTFILE. */
924 print_value_expressions (FILE *outfile, tree val)
926 if (VALUE_HANDLE_EXPR_SET (val))
929 sprintf (s, "VH.%04d", VALUE_HANDLE_ID (val));
930 print_value_set (outfile, VALUE_HANDLE_EXPR_SET (val), s, 0);
936 debug_value_expressions (tree val)
938 print_value_expressions (stderr, val);
942 void debug_value_set (value_set_t, const char *, int);
945 debug_value_set (value_set_t set, const char *setname, int blockindex)
947 print_value_set (stderr, set, setname, blockindex);
950 /* Return the folded version of T if T, when folded, is a gimple
951 min_invariant. Otherwise, return T. */
954 fully_constant_expression (tree t)
958 if (folded && is_gimple_min_invariant (folded))
963 /* Return a copy of a chain of nodes, chained through the TREE_CHAIN field.
964 For example, this can copy a list made of TREE_LIST nodes.
965 Allocates the nodes in list_node_pool*/
968 pool_copy_list (tree list)
975 head = (tree) pool_alloc (list_node_pool);
977 memcpy (head, list, tree_size (list));
980 next = TREE_CHAIN (list);
983 TREE_CHAIN (prev) = (tree) pool_alloc (list_node_pool);
984 memcpy (TREE_CHAIN (prev), next, tree_size (next));
985 prev = TREE_CHAIN (prev);
986 next = TREE_CHAIN (next);
991 /* Translate the vuses in the VUSES vector backwards through phi
992 nodes, so that they have the value they would have in BLOCK. */
994 static VEC(tree, gc) *
995 translate_vuses_through_block (VEC (tree, gc) *vuses, basic_block block)
998 VEC(tree, gc) *result = NULL;
1001 for (i = 0; VEC_iterate (tree, vuses, i, oldvuse); i++)
1003 tree phi = SSA_NAME_DEF_STMT (oldvuse);
1004 if (TREE_CODE (phi) == PHI_NODE)
1006 edge e = find_edge (block, bb_for_stmt (phi));
1009 tree def = PHI_ARG_DEF (phi, e->dest_idx);
1013 result = VEC_copy (tree, gc, vuses);
1014 VEC_replace (tree, result, i, def);
1021 sort_vuses (result);
1027 /* Translate EXPR using phis in PHIBLOCK, so that it has the values of
1028 the phis in PRED. Return NULL if we can't find a leader for each
1029 part of the translated expression. */
1032 phi_translate (tree expr, value_set_t set, basic_block pred,
1033 basic_block phiblock)
1035 tree phitrans = NULL;
1036 tree oldexpr = expr;
1040 if (is_gimple_min_invariant (expr))
1043 /* Phi translations of a given expression don't change. */
1048 vh = get_value_handle (expr);
1049 if (vh && TREE_CODE (vh) == VALUE_HANDLE)
1050 phitrans = phi_trans_lookup (expr, pred, VALUE_HANDLE_VUSES (vh));
1052 phitrans = phi_trans_lookup (expr, pred, NULL);
1055 phitrans = phi_trans_lookup (expr, pred, NULL);
1060 switch (TREE_CODE_CLASS (TREE_CODE (expr)))
1062 case tcc_expression:
1064 if (TREE_CODE (expr) != CALL_EXPR)
1068 tree oldop0 = TREE_OPERAND (expr, 0);
1069 tree oldarglist = TREE_OPERAND (expr, 1);
1070 tree oldop2 = TREE_OPERAND (expr, 2);
1077 tree vh = get_value_handle (expr);
1078 bool listchanged = false;
1079 bool invariantarg = false;
1080 VEC (tree, gc) *vuses = VALUE_HANDLE_VUSES (vh);
1081 VEC (tree, gc) *tvuses;
1083 /* Call expressions are kind of weird because they have an
1084 argument list. We don't want to value number the list
1085 as one value number, because that doesn't make much
1086 sense, and just breaks the support functions we call,
1087 which expect TREE_OPERAND (call_expr, 2) to be a
1090 newop0 = phi_translate (find_leader (set, oldop0),
1091 set, pred, phiblock);
1096 newop2 = phi_translate (find_leader (set, oldop2),
1097 set, pred, phiblock);
1102 /* phi translate the argument list piece by piece.
1104 We could actually build the list piece by piece here,
1105 but it's likely to not be worth the memory we will save,
1106 unless you have millions of call arguments. */
1108 newarglist = pool_copy_list (oldarglist);
1109 for (oldwalker = oldarglist, newwalker = newarglist;
1110 oldwalker && newwalker;
1111 oldwalker = TREE_CHAIN (oldwalker),
1112 newwalker = TREE_CHAIN (newwalker))
1115 tree oldval = TREE_VALUE (oldwalker);
1119 /* This may seem like a weird place for this
1120 check, but it's actually the easiest place to
1121 do it. We can't do it lower on in the
1122 recursion because it's valid for pieces of a
1123 component ref to be of AGGREGATE_TYPE, as long
1124 as the outermost one is not.
1125 To avoid *that* case, we have a check for
1126 AGGREGATE_TYPE_P in insert_aux. However, that
1127 check will *not* catch this case because here
1128 it occurs in the argument list. */
1129 if (AGGREGATE_TYPE_P (TREE_TYPE (oldval)))
1131 newval = phi_translate (find_leader (set, oldval),
1132 set, pred, phiblock);
1135 if (newval != oldval)
1138 invariantarg |= is_gimple_min_invariant (newval);
1139 TREE_VALUE (newwalker) = get_value_handle (newval);
1144 /* In case of new invariant args we might try to fold the call
1148 tree tmp = fold_ternary (CALL_EXPR, TREE_TYPE (expr),
1149 newop0, newarglist, newop2);
1152 STRIP_TYPE_NOPS (tmp);
1153 if (is_gimple_min_invariant (tmp))
1159 vn_lookup_or_add (newarglist, NULL);
1161 tvuses = translate_vuses_through_block (vuses, pred);
1163 if (listchanged || (newop0 != oldop0) || (oldop2 != newop2)
1166 newexpr = (tree) pool_alloc (expression_node_pool);
1167 memcpy (newexpr, expr, tree_size (expr));
1168 TREE_OPERAND (newexpr, 0) = newop0 == oldop0 ? oldop0 : get_value_handle (newop0);
1169 TREE_OPERAND (newexpr, 1) = listchanged ? newarglist : oldarglist;
1170 TREE_OPERAND (newexpr, 2) = newop2 == oldop2 ? oldop2 : get_value_handle (newop2);
1171 newexpr->common.ann = NULL;
1172 vn_lookup_or_add_with_vuses (newexpr, tvuses);
1174 phi_trans_add (oldexpr, newexpr, pred, tvuses);
1180 case tcc_declaration:
1182 VEC (tree, gc) * oldvuses = NULL;
1183 VEC (tree, gc) * newvuses = NULL;
1185 oldvuses = VALUE_HANDLE_VUSES (get_value_handle (expr));
1187 newvuses = translate_vuses_through_block (oldvuses, pred);
1189 if (oldvuses != newvuses)
1190 vn_lookup_or_add_with_vuses (expr, newvuses);
1192 phi_trans_add (oldexpr, expr, pred, newvuses);
1198 tree oldop0 = TREE_OPERAND (expr, 0);
1207 VEC (tree, gc) * oldvuses = NULL;
1208 VEC (tree, gc) * newvuses = NULL;
1210 if (TREE_CODE (expr) != INDIRECT_REF
1211 && TREE_CODE (expr) != COMPONENT_REF
1212 && TREE_CODE (expr) != ARRAY_REF)
1215 newop0 = phi_translate (find_leader (set, oldop0),
1216 set, pred, phiblock);
1220 if (TREE_CODE (expr) == ARRAY_REF)
1222 oldop1 = TREE_OPERAND (expr, 1);
1223 newop1 = phi_translate (find_leader (set, oldop1),
1224 set, pred, phiblock);
1228 oldop2 = TREE_OPERAND (expr, 2);
1231 newop2 = phi_translate (find_leader (set, oldop2),
1232 set, pred, phiblock);
1237 oldop3 = TREE_OPERAND (expr, 3);
1240 newop3 = phi_translate (find_leader (set, oldop3),
1241 set, pred, phiblock);
1248 oldvuses = VALUE_HANDLE_VUSES (get_value_handle (expr));
1250 newvuses = translate_vuses_through_block (oldvuses, pred);
1252 if (newop0 != oldop0 || newvuses != oldvuses
1255 || newop3 != oldop3)
1259 newexpr = pool_alloc (reference_node_pool);
1260 memcpy (newexpr, expr, tree_size (expr));
1261 TREE_OPERAND (newexpr, 0) = get_value_handle (newop0);
1262 if (TREE_CODE (expr) == ARRAY_REF)
1264 TREE_OPERAND (newexpr, 1) = get_value_handle (newop1);
1266 TREE_OPERAND (newexpr, 2) = get_value_handle (newop2);
1268 TREE_OPERAND (newexpr, 3) = get_value_handle (newop3);
1271 t = fully_constant_expression (newexpr);
1275 pool_free (reference_node_pool, newexpr);
1280 newexpr->common.ann = NULL;
1281 vn_lookup_or_add_with_vuses (newexpr, newvuses);
1284 phi_trans_add (oldexpr, newexpr, pred, newvuses);
1291 case tcc_comparison:
1293 tree oldop1 = TREE_OPERAND (expr, 0);
1294 tree oldop2 = TREE_OPERAND (expr, 1);
1299 newop1 = phi_translate (find_leader (set, oldop1),
1300 set, pred, phiblock);
1303 newop2 = phi_translate (find_leader (set, oldop2),
1304 set, pred, phiblock);
1307 if (newop1 != oldop1 || newop2 != oldop2)
1310 newexpr = (tree) pool_alloc (binary_node_pool);
1311 memcpy (newexpr, expr, tree_size (expr));
1312 TREE_OPERAND (newexpr, 0) = newop1 == oldop1 ? oldop1 : get_value_handle (newop1);
1313 TREE_OPERAND (newexpr, 1) = newop2 == oldop2 ? oldop2 : get_value_handle (newop2);
1314 t = fully_constant_expression (newexpr);
1317 pool_free (binary_node_pool, newexpr);
1322 newexpr->common.ann = NULL;
1323 vn_lookup_or_add (newexpr, NULL);
1326 phi_trans_add (oldexpr, newexpr, pred, NULL);
1333 tree oldop1 = TREE_OPERAND (expr, 0);
1337 newop1 = phi_translate (find_leader (set, oldop1),
1338 set, pred, phiblock);
1341 if (newop1 != oldop1)
1344 newexpr = (tree) pool_alloc (unary_node_pool);
1345 memcpy (newexpr, expr, tree_size (expr));
1346 TREE_OPERAND (newexpr, 0) = get_value_handle (newop1);
1347 t = fully_constant_expression (newexpr);
1350 pool_free (unary_node_pool, newexpr);
1355 newexpr->common.ann = NULL;
1356 vn_lookup_or_add (newexpr, NULL);
1359 phi_trans_add (oldexpr, newexpr, pred, NULL);
1364 case tcc_exceptional:
1368 gcc_assert (TREE_CODE (expr) == SSA_NAME);
1369 if (TREE_CODE (SSA_NAME_DEF_STMT (expr)) == PHI_NODE)
1370 phi = SSA_NAME_DEF_STMT (expr);
1374 e = find_edge (pred, bb_for_stmt (phi));
1377 if (is_undefined_value (PHI_ARG_DEF (phi, e->dest_idx)))
1379 vn_lookup_or_add (PHI_ARG_DEF (phi, e->dest_idx), NULL);
1380 return PHI_ARG_DEF (phi, e->dest_idx);
1390 /* For each expression in SET, translate the value handles through phi nodes
1391 in PHIBLOCK using edge PHIBLOCK->PRED, and store the resulting
1392 expressions in DEST. */
1395 phi_translate_set (value_set_t dest, value_set_t set, basic_block pred,
1396 basic_block phiblock)
1398 value_set_node_t node;
1399 for (node = set->head;
1405 translated = phi_translate (node->expr, set, pred, phiblock);
1407 /* Don't add constants or empty translations to the cache, since
1408 we won't look them up that way, or use the result, anyway. */
1409 if (translated && !is_gimple_min_invariant (translated))
1411 tree vh = get_value_handle (translated);
1412 VEC (tree, gc) *vuses;
1414 /* The value handle itself may also be an invariant, in
1415 which case, it has no vuses. */
1416 vuses = !is_gimple_min_invariant (vh)
1417 ? VALUE_HANDLE_VUSES (vh) : NULL;
1418 phi_trans_add (node->expr, translated, pred, vuses);
1421 if (translated != NULL)
1422 value_insert_into_set (dest, translated);
1426 /* Find the leader for a value (i.e., the name representing that
1427 value) in a given set, and return it. Return NULL if no leader is
1431 bitmap_find_leader (bitmap_set_t set, tree val)
1436 if (is_gimple_min_invariant (val))
1438 if (bitmap_set_contains_value (set, val))
1440 /* Rather than walk the entire bitmap of expressions, and see
1441 whether any of them has the value we are looking for, we look
1442 at the reverse mapping, which tells us the set of expressions
1443 that have a given value (IE value->expressions with that
1444 value) and see if any of those expressions are in our set.
1445 The number of expressions per value is usually significantly
1446 less than the number of expressions in the set. In fact, for
1447 large testcases, doing it this way is roughly 5-10x faster
1448 than walking the bitmap.
1449 If this is somehow a significant lose for some cases, we can
1450 choose which set to walk based on which set is smaller. */
1451 value_set_t exprset;
1452 value_set_node_t node;
1453 exprset = VALUE_HANDLE_EXPR_SET (val);
1454 for (node = exprset->head; node; node = node->next)
1456 if (TREE_CODE (node->expr) == SSA_NAME)
1458 if (bitmap_bit_p (set->expressions,
1459 SSA_NAME_VERSION (node->expr)))
1468 /* Find the leader for a value (i.e., the name representing that
1469 value) in a given set, and return it. Return NULL if no leader is
1473 find_leader (value_set_t set, tree val)
1475 value_set_node_t node;
1480 /* Constants represent themselves. */
1481 if (is_gimple_min_invariant (val))
1484 if (set->length == 0)
1487 if (value_exists_in_set_bitmap (set, val))
1489 for (node = set->head;
1493 if (get_value_handle (node->expr) == val)
1501 /* Given the vuse representative map, MAP, and an SSA version number,
1502 ID, return the bitmap of names ID represents, or NULL, if none
1506 get_representative (bitmap *map, int id)
1508 if (map[id] != NULL)
1513 /* A vuse is anticipable at the top of block x, from the bottom of the
1514 block, if it reaches the top of the block, and is not killed in the
1515 block. In effect, we are trying to see if the vuse is transparent
1516 backwards in the block. */
1519 vuses_dies_in_block_x (VEC (tree, gc) *vuses, basic_block block)
1524 for (i = 0; VEC_iterate (tree, vuses, i, vuse); i++)
1526 /* Any places where this is too conservative, are places
1527 where we created a new version and shouldn't have. */
1529 if (!bitmap_bit_p (RVUSE_IN (block), SSA_NAME_VERSION (vuse))
1530 || bitmap_bit_p (RVUSE_KILL (block), SSA_NAME_VERSION (vuse)))
1536 /* Determine if the expression EXPR is valid in SET. This means that
1537 we have a leader for each part of the expression (if it consists of
1538 values), or the expression is an SSA_NAME.
1540 NB: We never should run into a case where we have SSA_NAME +
1541 SSA_NAME or SSA_NAME + value. The sets valid_in_set is called on,
1542 the ANTIC sets, will only ever have SSA_NAME's or value expressions
1543 (IE VALUE1 + VALUE2, *VALUE1, VALUE1 < VALUE2) */
1546 valid_in_set (value_set_t set, tree expr, basic_block block)
1548 tree vh = get_value_handle (expr);
1549 switch (TREE_CODE_CLASS (TREE_CODE (expr)))
1552 case tcc_comparison:
1554 tree op1 = TREE_OPERAND (expr, 0);
1555 tree op2 = TREE_OPERAND (expr, 1);
1556 return set_contains_value (set, op1) && set_contains_value (set, op2);
1561 tree op1 = TREE_OPERAND (expr, 0);
1562 return set_contains_value (set, op1);
1565 case tcc_expression:
1567 if (TREE_CODE (expr) == CALL_EXPR)
1569 tree op0 = TREE_OPERAND (expr, 0);
1570 tree arglist = TREE_OPERAND (expr, 1);
1571 tree op2 = TREE_OPERAND (expr, 2);
1573 /* Check the non-list operands first. */
1574 if (!set_contains_value (set, op0)
1575 || (op2 && !set_contains_value (set, op2)))
1578 /* Now check the operands. */
1579 for (; arglist; arglist = TREE_CHAIN (arglist))
1581 if (!set_contains_value (set, TREE_VALUE (arglist)))
1584 return !vuses_dies_in_block_x (VALUE_HANDLE_VUSES (vh), block);
1591 if (TREE_CODE (expr) == INDIRECT_REF
1592 || TREE_CODE (expr) == COMPONENT_REF
1593 || TREE_CODE (expr) == ARRAY_REF)
1595 tree op0 = TREE_OPERAND (expr, 0);
1596 gcc_assert (is_gimple_min_invariant (op0)
1597 || TREE_CODE (op0) == VALUE_HANDLE);
1598 if (!set_contains_value (set, op0))
1600 if (TREE_CODE (expr) == ARRAY_REF)
1602 tree op1 = TREE_OPERAND (expr, 1);
1603 tree op2 = TREE_OPERAND (expr, 2);
1604 tree op3 = TREE_OPERAND (expr, 3);
1605 gcc_assert (is_gimple_min_invariant (op1)
1606 || TREE_CODE (op1) == VALUE_HANDLE);
1607 if (!set_contains_value (set, op1))
1609 gcc_assert (!op2 || is_gimple_min_invariant (op2)
1610 || TREE_CODE (op2) == VALUE_HANDLE);
1612 && !set_contains_value (set, op2))
1614 gcc_assert (!op3 || is_gimple_min_invariant (op3)
1615 || TREE_CODE (op3) == VALUE_HANDLE);
1617 && !set_contains_value (set, op3))
1620 return set_contains_value (ANTIC_SAFE_LOADS (block),
1622 || !vuses_dies_in_block_x (VALUE_HANDLE_VUSES (vh),
1628 case tcc_exceptional:
1629 gcc_assert (TREE_CODE (expr) == SSA_NAME);
1632 case tcc_declaration:
1633 return !vuses_dies_in_block_x (VALUE_HANDLE_VUSES (vh), block);
1636 /* No other cases should be encountered. */
1641 /* Clean the set of expressions that are no longer valid in SET. This
1642 means expressions that are made up of values we have no leaders for
1646 clean (value_set_t set, basic_block block)
1648 value_set_node_t node;
1649 value_set_node_t next;
1654 if (!valid_in_set (set, node->expr, block))
1655 set_remove (set, node->expr);
1660 static sbitmap has_abnormal_preds;
1662 /* Compute the ANTIC set for BLOCK.
1664 If succs(BLOCK) > 1 then
1665 ANTIC_OUT[BLOCK] = intersection of ANTIC_IN[b] for all succ(BLOCK)
1666 else if succs(BLOCK) == 1 then
1667 ANTIC_OUT[BLOCK] = phi_translate (ANTIC_IN[succ(BLOCK)])
1669 ANTIC_IN[BLOCK] = clean(ANTIC_OUT[BLOCK] U EXP_GEN[BLOCK] - TMP_GEN[BLOCK])
1671 XXX: It would be nice to either write a set_clear, and use it for
1672 ANTIC_OUT, or to mark the antic_out set as deleted at the end
1673 of this routine, so that the pool can hand the same memory back out
1674 again for the next ANTIC_OUT. */
1677 compute_antic_aux (basic_block block, bool block_has_abnormal_pred_edge)
1680 bool changed = false;
1681 value_set_t S, old, ANTIC_OUT;
1682 value_set_node_t node;
1684 ANTIC_OUT = S = NULL;
1686 /* If any edges from predecessors are abnormal, antic_in is empty,
1688 if (block_has_abnormal_pred_edge)
1689 goto maybe_dump_sets;
1691 old = set_new (false);
1692 set_copy (old, ANTIC_IN (block));
1693 ANTIC_OUT = set_new (true);
1695 /* If the block has no successors, ANTIC_OUT is empty. */
1696 if (EDGE_COUNT (block->succs) == 0)
1698 /* If we have one successor, we could have some phi nodes to
1699 translate through. */
1700 else if (single_succ_p (block))
1702 phi_translate_set (ANTIC_OUT, ANTIC_IN (single_succ (block)),
1703 block, single_succ (block));
1705 /* If we have multiple successors, we take the intersection of all of
1709 VEC(basic_block, heap) * worklist;
1712 basic_block bprime, first;
1715 worklist = VEC_alloc (basic_block, heap, EDGE_COUNT (block->succs));
1716 FOR_EACH_EDGE (e, ei, block->succs)
1717 VEC_quick_push (basic_block, worklist, e->dest);
1718 first = VEC_index (basic_block, worklist, 0);
1719 set_copy (ANTIC_OUT, ANTIC_IN (first));
1721 for (i = 1; VEC_iterate (basic_block, worklist, i, bprime); i++)
1723 node = ANTIC_OUT->head;
1727 value_set_node_t next = node->next;
1729 val = get_value_handle (node->expr);
1730 if (!set_contains_value (ANTIC_IN (bprime), val))
1731 set_remove (ANTIC_OUT, node->expr);
1735 VEC_free (basic_block, heap, worklist);
1738 /* Generate ANTIC_OUT - TMP_GEN. */
1739 S = bitmap_set_subtract_from_value_set (ANTIC_OUT, TMP_GEN (block), false);
1741 /* Start ANTIC_IN with EXP_GEN - TMP_GEN */
1742 ANTIC_IN (block) = bitmap_set_subtract_from_value_set (EXP_GEN (block),
1746 /* Then union in the ANTIC_OUT - TMP_GEN values,
1747 to get ANTIC_OUT U EXP_GEN - TMP_GEN */
1748 for (node = S->head; node; node = node->next)
1749 value_insert_into_set (ANTIC_IN (block), node->expr);
1751 clean (ANTIC_IN (block), block);
1752 if (!set_equal (old, ANTIC_IN (block)))
1756 if (dump_file && (dump_flags & TDF_DETAILS))
1759 print_value_set (dump_file, ANTIC_OUT, "ANTIC_OUT", block->index);
1761 if (ANTIC_SAFE_LOADS (block))
1762 print_value_set (dump_file, ANTIC_SAFE_LOADS (block),
1763 "ANTIC_SAFE_LOADS", block->index);
1764 print_value_set (dump_file, ANTIC_IN (block), "ANTIC_IN", block->index);
1767 print_value_set (dump_file, S, "S", block->index);
1770 for (son = first_dom_son (CDI_POST_DOMINATORS, block);
1772 son = next_dom_son (CDI_POST_DOMINATORS, son))
1774 changed |= compute_antic_aux (son,
1775 TEST_BIT (has_abnormal_preds, son->index));
1780 /* Compute ANTIC sets. */
1783 compute_antic (void)
1785 bool changed = true;
1786 int num_iterations = 0;
1789 /* If any predecessor edges are abnormal, we punt, so antic_in is empty.
1790 We pre-build the map of blocks with incoming abnormal edges here. */
1791 has_abnormal_preds = sbitmap_alloc (last_basic_block);
1792 sbitmap_zero (has_abnormal_preds);
1798 FOR_EACH_EDGE (e, ei, block->preds)
1799 if (e->flags & EDGE_ABNORMAL)
1801 SET_BIT (has_abnormal_preds, block->index);
1805 /* While we are here, give empty ANTIC_IN sets to each block. */
1806 ANTIC_IN (block) = set_new (true);
1808 /* At the exit block we anticipate nothing. */
1809 ANTIC_IN (EXIT_BLOCK_PTR) = set_new (true);
1815 changed = compute_antic_aux (EXIT_BLOCK_PTR, false);
1818 sbitmap_free (has_abnormal_preds);
1820 if (dump_file && (dump_flags & TDF_STATS))
1821 fprintf (dump_file, "compute_antic required %d iterations\n", num_iterations);
1824 /* Print the names represented by the bitmap NAMES, to the file OUT. */
1826 dump_bitmap_of_names (FILE *out, bitmap names)
1831 fprintf (out, " { ");
1832 EXECUTE_IF_SET_IN_BITMAP (names, 0, i, bi)
1834 print_generic_expr (out, ssa_name (i), 0);
1837 fprintf (out, "}\n");
1840 /* Compute a set of representative vuse versions for each phi. This
1841 is so we can compute conservative kill sets in terms of all vuses
1842 that are killed, instead of continually walking chains.
1844 We also have to be able kill all names associated with a phi when
1845 the phi dies in order to ensure we don't generate overlapping
1846 live ranges, which are not allowed in virtual SSA. */
1848 static bitmap *vuse_names;
1850 compute_vuse_representatives (void)
1854 VEC (tree, heap) *phis = NULL;
1855 bool changed = true;
1860 for (phi = phi_nodes (bb);
1862 phi = PHI_CHAIN (phi))
1863 if (!is_gimple_reg (PHI_RESULT (phi)))
1864 VEC_safe_push (tree, heap, phis, phi);
1871 for (i = 0; VEC_iterate (tree, phis, i, phi); i++)
1873 size_t ver = SSA_NAME_VERSION (PHI_RESULT (phi));
1877 if (vuse_names[ver] == NULL)
1879 vuse_names[ver] = BITMAP_ALLOC (&grand_bitmap_obstack);
1880 bitmap_set_bit (vuse_names[ver], ver);
1882 FOR_EACH_PHI_ARG (usep, phi, iter, SSA_OP_ALL_USES)
1884 tree use = USE_FROM_PTR (usep);
1885 bitmap usebitmap = get_representative (vuse_names,
1886 SSA_NAME_VERSION (use));
1887 if (usebitmap != NULL)
1889 changed |= bitmap_ior_into (vuse_names[ver],
1894 changed |= !bitmap_bit_p (vuse_names[ver],
1895 SSA_NAME_VERSION (use));
1897 bitmap_set_bit (vuse_names[ver],
1898 SSA_NAME_VERSION (use));
1904 if (dump_file && (dump_flags & TDF_DETAILS))
1905 for (i = 0; VEC_iterate (tree, phis, i, phi); i++)
1907 bitmap reps = get_representative (vuse_names,
1908 SSA_NAME_VERSION (PHI_RESULT (phi)));
1911 print_generic_expr (dump_file, PHI_RESULT (phi), 0);
1912 fprintf (dump_file, " represents ");
1913 dump_bitmap_of_names (dump_file, reps);
1916 VEC_free (tree, heap, phis);
1919 /* Compute reaching vuses and antic safe loads. RVUSE computation is
1920 is a small bit of iterative dataflow to determine what virtual uses
1921 reach what blocks. Because we can't generate overlapping virtual
1922 uses, and virtual uses *do* actually die, this ends up being faster
1923 in most cases than continually walking the virtual use/def chains
1924 to determine whether we are inside a block where a given virtual is
1925 still available to be used.
1927 ANTIC_SAFE_LOADS are those loads that actually occur before any kill to
1928 their vuses in the block,and thus, are safe at the top of the
1938 b = *a is an antic safe load because it still safe to consider it
1939 ANTIC at the top of the block.
1941 We currently compute a conservative approximation to
1942 ANTIC_SAFE_LOADS. We compute those loads that occur before *any*
1943 stores in the block. This is not because it is difficult to
1944 compute the precise answer, but because it is expensive. More
1945 testing is necessary to determine whether it is worth computing the
1949 compute_rvuse_and_antic_safe (void)
1956 bool changed = true;
1957 unsigned int *first_store_uid;
1959 first_store_uid = xcalloc (n_basic_blocks, sizeof (unsigned int));
1961 compute_vuse_representatives ();
1965 RVUSE_IN (bb) = BITMAP_ALLOC (&grand_bitmap_obstack);
1966 RVUSE_GEN (bb) = BITMAP_ALLOC (&grand_bitmap_obstack);
1967 RVUSE_KILL (bb) = BITMAP_ALLOC (&grand_bitmap_obstack);
1968 RVUSE_OUT (bb) = BITMAP_ALLOC (&grand_bitmap_obstack);
1969 ANTIC_SAFE_LOADS (bb) = NULL;
1972 /* Mark live on entry */
1973 for (i = 0; i < num_ssa_names; i++)
1975 tree name = ssa_name (i);
1976 if (name && !is_gimple_reg (name)
1977 && IS_EMPTY_STMT (SSA_NAME_DEF_STMT (name)))
1978 bitmap_set_bit (RVUSE_OUT (ENTRY_BLOCK_PTR),
1979 SSA_NAME_VERSION (name));
1982 /* Compute local sets for reaching vuses.
1983 GEN(block) = generated in block and not locally killed.
1984 KILL(block) = set of vuses killed in block.
1989 block_stmt_iterator bsi;
1994 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
1996 tree stmt = bsi_stmt (bsi);
1998 if (first_store_uid[bb->index] == 0
1999 && !ZERO_SSA_OPERANDS (stmt, SSA_OP_VMAYUSE | SSA_OP_VMAYDEF
2000 | SSA_OP_VMUSTDEF | SSA_OP_VMUSTKILL))
2002 first_store_uid[bb->index] = stmt_ann (stmt)->uid;
2006 FOR_EACH_SSA_USE_OPERAND (usep, stmt, iter, SSA_OP_VIRTUAL_KILLS
2009 tree use = USE_FROM_PTR (usep);
2010 bitmap repbit = get_representative (vuse_names,
2011 SSA_NAME_VERSION (use));
2014 bitmap_and_compl_into (RVUSE_GEN (bb), repbit);
2015 bitmap_ior_into (RVUSE_KILL (bb), repbit);
2019 bitmap_set_bit (RVUSE_KILL (bb), SSA_NAME_VERSION (use));
2020 bitmap_clear_bit (RVUSE_GEN (bb), SSA_NAME_VERSION (use));
2023 FOR_EACH_SSA_DEF_OPERAND (defp, stmt, iter, SSA_OP_VIRTUAL_DEFS)
2025 tree def = DEF_FROM_PTR (defp);
2026 bitmap_set_bit (RVUSE_GEN (bb), SSA_NAME_VERSION (def));
2033 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
2035 if (!is_gimple_reg (PHI_RESULT (phi)))
2040 tree def = PHI_RESULT (phi);
2041 /* In reality, the PHI result is generated at the end of
2042 each predecessor block. This will make the value
2043 LVUSE_IN for the bb containing the PHI, which is
2045 FOR_EACH_EDGE (e, ei, bb->preds)
2046 bitmap_set_bit (RVUSE_GEN (e->src), SSA_NAME_VERSION (def));
2051 /* Solve reaching vuses.
2053 RVUSE_IN[BB] = Union of RVUSE_OUT of predecessors.
2054 RVUSE_OUT[BB] = RVUSE_GEN[BB] U (RVUSE_IN[BB] - RVUSE_KILL[BB])
2056 postorder = XNEWVEC (int, n_basic_blocks - NUM_FIXED_BLOCKS);
2057 pre_and_rev_post_order_compute (NULL, postorder, false);
2064 for (j = 0; j < n_basic_blocks - NUM_FIXED_BLOCKS; j++)
2068 bb = BASIC_BLOCK (postorder[j]);
2070 FOR_EACH_EDGE (e, ei, bb->preds)
2071 bitmap_ior_into (RVUSE_IN (bb), RVUSE_OUT (e->src));
2073 changed |= bitmap_ior_and_compl (RVUSE_OUT (bb),
2081 if (dump_file && (dump_flags & TDF_DETAILS))
2085 fprintf (dump_file, "RVUSE_IN (%d) =", bb->index);
2086 dump_bitmap_of_names (dump_file, RVUSE_IN (bb));
2088 fprintf (dump_file, "RVUSE_KILL (%d) =", bb->index);
2089 dump_bitmap_of_names (dump_file, RVUSE_KILL (bb));
2091 fprintf (dump_file, "RVUSE_GEN (%d) =", bb->index);
2092 dump_bitmap_of_names (dump_file, RVUSE_GEN (bb));
2094 fprintf (dump_file, "RVUSE_OUT (%d) =", bb->index);
2095 dump_bitmap_of_names (dump_file, RVUSE_OUT (bb));
2101 value_set_node_t node;
2102 if (bitmap_empty_p (RVUSE_KILL (bb)))
2105 for (node = EXP_GEN (bb)->head; node; node = node->next)
2107 if (REFERENCE_CLASS_P (node->expr))
2109 tree vh = get_value_handle (node->expr);
2110 tree maybe = bitmap_find_leader (AVAIL_OUT (bb), vh);
2114 tree def = SSA_NAME_DEF_STMT (maybe);
2116 if (bb_for_stmt (def) != bb)
2119 if (TREE_CODE (def) == PHI_NODE
2120 || stmt_ann (def)->uid < first_store_uid[bb->index])
2122 if (ANTIC_SAFE_LOADS (bb) == NULL)
2123 ANTIC_SAFE_LOADS (bb) = set_new (true);
2124 value_insert_into_set (ANTIC_SAFE_LOADS (bb),
2131 free (first_store_uid);
2134 /* Return true if we can value number the call in STMT. This is true
2135 if we have a pure or constant call. */
2138 can_value_number_call (tree stmt)
2140 tree call = get_call_expr_in (stmt);
2142 if (call_expr_flags (call) & (ECF_PURE | ECF_CONST))
2147 /* Return true if OP is a tree which we can perform value numbering
2151 can_value_number_operation (tree op)
2153 return UNARY_CLASS_P (op)
2154 || BINARY_CLASS_P (op)
2155 || COMPARISON_CLASS_P (op)
2156 || REFERENCE_CLASS_P (op)
2157 || (TREE_CODE (op) == CALL_EXPR
2158 && can_value_number_call (op));
2162 /* Return true if OP is a tree which we can perform PRE on
2163 on. This may not match the operations we can value number, but in
2164 a perfect world would. */
2167 can_PRE_operation (tree op)
2169 return UNARY_CLASS_P (op)
2170 || BINARY_CLASS_P (op)
2171 || COMPARISON_CLASS_P (op)
2172 || TREE_CODE (op) == INDIRECT_REF
2173 || TREE_CODE (op) == COMPONENT_REF
2174 || TREE_CODE (op) == CALL_EXPR
2175 || TREE_CODE (op) == ARRAY_REF;
2179 /* Inserted expressions are placed onto this worklist, which is used
2180 for performing quick dead code elimination of insertions we made
2181 that didn't turn out to be necessary. */
2182 static VEC(tree,heap) *inserted_exprs;
2184 /* Pool allocated fake store expressions are placed onto this
2185 worklist, which, after performing dead code elimination, is walked
2186 to see which expressions need to be put into GC'able memory */
2187 static VEC(tree, heap) *need_creation;
2189 /* For COMPONENT_REF's and ARRAY_REF's, we can't have any intermediates for the
2190 COMPONENT_REF or INDIRECT_REF or ARRAY_REF portion, because we'd end up with
2191 trying to rename aggregates into ssa form directly, which is a no
2194 Thus, this routine doesn't create temporaries, it just builds a
2195 single access expression for the array, calling
2196 find_or_generate_expression to build the innermost pieces.
2198 This function is a subroutine of create_expression_by_pieces, and
2199 should not be called on it's own unless you really know what you
2203 create_component_ref_by_pieces (basic_block block, tree expr, tree stmts)
2208 if (TREE_CODE (genop) == VALUE_HANDLE)
2210 tree found = bitmap_find_leader (AVAIL_OUT (block), expr);
2215 if (TREE_CODE (genop) == VALUE_HANDLE)
2216 genop = VALUE_HANDLE_EXPR_SET (expr)->head->expr;
2218 switch TREE_CODE (genop)
2224 op0 = create_component_ref_by_pieces (block,
2225 TREE_OPERAND (genop, 0),
2227 op1 = TREE_OPERAND (genop, 1);
2228 if (TREE_CODE (op1) == VALUE_HANDLE)
2229 op1 = find_or_generate_expression (block, op1, stmts);
2230 op2 = TREE_OPERAND (genop, 2);
2231 if (op2 && TREE_CODE (op2) == VALUE_HANDLE)
2232 op2 = find_or_generate_expression (block, op2, stmts);
2233 op3 = TREE_OPERAND (genop, 3);
2234 if (op3 && TREE_CODE (op3) == VALUE_HANDLE)
2235 op3 = find_or_generate_expression (block, op3, stmts);
2236 folded = build4 (ARRAY_REF, TREE_TYPE (genop), op0, op1,
2244 op0 = create_component_ref_by_pieces (block,
2245 TREE_OPERAND (genop, 0),
2247 op1 = VALUE_HANDLE_EXPR_SET (TREE_OPERAND (genop, 1))->head->expr;
2248 folded = fold_build3 (COMPONENT_REF, TREE_TYPE (genop), op0, op1,
2255 tree op1 = TREE_OPERAND (genop, 0);
2256 tree genop1 = find_or_generate_expression (block, op1, stmts);
2258 folded = fold_build1 (TREE_CODE (genop), TREE_TYPE (genop),
2276 /* Find a leader for an expression, or generate one using
2277 create_expression_by_pieces if it's ANTIC but
2279 BLOCK is the basic_block we are looking for leaders in.
2280 EXPR is the expression to find a leader or generate for.
2281 STMTS is the statement list to put the inserted expressions on.
2282 Returns the SSA_NAME of the LHS of the generated expression or the
2286 find_or_generate_expression (basic_block block, tree expr, tree stmts)
2288 tree genop = bitmap_find_leader (AVAIL_OUT (block), expr);
2290 /* If it's still NULL, it must be a complex expression, so generate
2294 genop = VALUE_HANDLE_EXPR_SET (expr)->head->expr;
2296 gcc_assert (can_PRE_operation (genop));
2297 genop = create_expression_by_pieces (block, genop, stmts);
2302 #define NECESSARY(stmt) stmt->common.asm_written_flag
2303 /* Create an expression in pieces, so that we can handle very complex
2304 expressions that may be ANTIC, but not necessary GIMPLE.
2305 BLOCK is the basic block the expression will be inserted into,
2306 EXPR is the expression to insert (in value form)
2307 STMTS is a statement list to append the necessary insertions into.
2309 This function will die if we hit some value that shouldn't be
2310 ANTIC but is (IE there is no leader for it, or its components).
2311 This function may also generate expressions that are themselves
2312 partially or fully redundant. Those that are will be either made
2313 fully redundant during the next iteration of insert (for partially
2314 redundant ones), or eliminated by eliminate (for fully redundant
2318 create_expression_by_pieces (basic_block block, tree expr, tree stmts)
2321 tree folded, forced_stmts, newexpr;
2323 tree_stmt_iterator tsi;
2325 switch (TREE_CODE_CLASS (TREE_CODE (expr)))
2327 case tcc_expression:
2331 tree genop0, genop2;
2333 tree walker, genwalker;
2335 gcc_assert (TREE_CODE (expr) == CALL_EXPR);
2338 op0 = TREE_OPERAND (expr, 0);
2339 arglist = TREE_OPERAND (expr, 1);
2340 op2 = TREE_OPERAND (expr, 2);
2342 genop0 = find_or_generate_expression (block, op0, stmts);
2343 genarglist = copy_list (arglist);
2344 for (walker = arglist, genwalker = genarglist;
2345 genwalker && walker;
2346 genwalker = TREE_CHAIN (genwalker), walker = TREE_CHAIN (walker))
2348 TREE_VALUE (genwalker)
2349 = find_or_generate_expression (block, TREE_VALUE (walker),
2354 genop2 = find_or_generate_expression (block, op2, stmts);
2355 folded = fold_build3 (TREE_CODE (expr), TREE_TYPE (expr),
2356 genop0, genarglist, genop2);
2364 if (TREE_CODE (expr) == COMPONENT_REF
2365 || TREE_CODE (expr) == ARRAY_REF)
2367 folded = create_component_ref_by_pieces (block, expr, stmts);
2371 tree op1 = TREE_OPERAND (expr, 0);
2372 tree genop1 = find_or_generate_expression (block, op1, stmts);
2374 folded = fold_build1 (TREE_CODE (expr), TREE_TYPE (expr),
2381 case tcc_comparison:
2383 tree op1 = TREE_OPERAND (expr, 0);
2384 tree op2 = TREE_OPERAND (expr, 1);
2385 tree genop1 = find_or_generate_expression (block, op1, stmts);
2386 tree genop2 = find_or_generate_expression (block, op2, stmts);
2387 folded = fold_build2 (TREE_CODE (expr), TREE_TYPE (expr),
2394 tree op1 = TREE_OPERAND (expr, 0);
2395 tree genop1 = find_or_generate_expression (block, op1, stmts);
2396 folded = fold_build1 (TREE_CODE (expr), TREE_TYPE (expr),
2405 /* Force the generated expression to be a sequence of GIMPLE
2407 We have to call unshare_expr because force_gimple_operand may
2408 modify the tree we pass to it. */
2409 newexpr = force_gimple_operand (unshare_expr (folded), &forced_stmts,
2412 /* If we have any intermediate expressions to the value sets, add them
2413 to the value sets and chain them on in the instruction stream. */
2416 tsi = tsi_start (forced_stmts);
2417 for (; !tsi_end_p (tsi); tsi_next (&tsi))
2419 tree stmt = tsi_stmt (tsi);
2420 tree forcedname = TREE_OPERAND (stmt, 0);
2421 tree forcedexpr = TREE_OPERAND (stmt, 1);
2422 tree val = vn_lookup_or_add (forcedexpr, NULL);
2424 VEC_safe_push (tree, heap, inserted_exprs, stmt);
2425 vn_add (forcedname, val);
2426 bitmap_value_replace_in_set (NEW_SETS (block), forcedname);
2427 bitmap_value_replace_in_set (AVAIL_OUT (block), forcedname);
2428 mark_new_vars_to_rename (stmt);
2430 tsi = tsi_last (stmts);
2431 tsi_link_after (&tsi, forced_stmts, TSI_CONTINUE_LINKING);
2434 /* Build and insert the assignment of the end result to the temporary
2435 that we will return. */
2436 if (!pretemp || TREE_TYPE (expr) != TREE_TYPE (pretemp))
2438 pretemp = create_tmp_var (TREE_TYPE (expr), "pretmp");
2439 get_var_ann (pretemp);
2443 add_referenced_var (temp);
2445 if (TREE_CODE (TREE_TYPE (expr)) == COMPLEX_TYPE)
2446 DECL_COMPLEX_GIMPLE_REG_P (temp) = 1;
2448 newexpr = build2 (MODIFY_EXPR, TREE_TYPE (expr), temp, newexpr);
2449 name = make_ssa_name (temp, newexpr);
2450 TREE_OPERAND (newexpr, 0) = name;
2451 NECESSARY (newexpr) = 0;
2453 tsi = tsi_last (stmts);
2454 tsi_link_after (&tsi, newexpr, TSI_CONTINUE_LINKING);
2455 VEC_safe_push (tree, heap, inserted_exprs, newexpr);
2456 mark_new_vars_to_rename (newexpr);
2458 /* Add a value handle to the temporary.
2459 The value may already exist in either NEW_SETS, or AVAIL_OUT, because
2460 we are creating the expression by pieces, and this particular piece of
2461 the expression may have been represented. There is no harm in replacing
2463 v = get_value_handle (expr);
2465 bitmap_value_replace_in_set (NEW_SETS (block), name);
2466 bitmap_value_replace_in_set (AVAIL_OUT (block), name);
2468 pre_stats.insertions++;
2469 if (dump_file && (dump_flags & TDF_DETAILS))
2471 fprintf (dump_file, "Inserted ");
2472 print_generic_expr (dump_file, newexpr, 0);
2473 fprintf (dump_file, " in predecessor %d\n", block->index);
2479 /* Insert the to-be-made-available values of NODE for each
2480 predecessor, stored in AVAIL, into the predecessors of BLOCK, and
2481 merge the result with a phi node, given the same value handle as
2482 NODE. Return true if we have inserted new stuff. */
2485 insert_into_preds_of_block (basic_block block, value_set_node_t node,
2488 tree val = get_value_handle (node->expr);
2490 bool insertions = false;
2495 tree type = TREE_TYPE (avail[EDGE_PRED (block, 0)->src->index]);
2498 if (dump_file && (dump_flags & TDF_DETAILS))
2500 fprintf (dump_file, "Found partial redundancy for expression ");
2501 print_generic_expr (dump_file, node->expr, 0);
2502 fprintf (dump_file, " (");
2503 print_generic_expr (dump_file, val, 0);
2504 fprintf (dump_file, ")");
2505 fprintf (dump_file, "\n");
2508 /* Make sure we aren't creating an induction variable. */
2509 if (block->loop_depth > 0 && EDGE_COUNT (block->preds) == 2
2510 && TREE_CODE_CLASS (TREE_CODE (node->expr)) != tcc_reference )
2512 bool firstinsideloop = false;
2513 bool secondinsideloop = false;
2514 firstinsideloop = flow_bb_inside_loop_p (block->loop_father,
2515 EDGE_PRED (block, 0)->src);
2516 secondinsideloop = flow_bb_inside_loop_p (block->loop_father,
2517 EDGE_PRED (block, 1)->src);
2518 /* Induction variables only have one edge inside the loop. */
2519 if (firstinsideloop ^ secondinsideloop)
2521 if (dump_file && (dump_flags & TDF_DETAILS))
2522 fprintf (dump_file, "Skipping insertion of phi for partial redundancy: Looks like an induction variable\n");
2528 /* Make the necessary insertions. */
2529 FOR_EACH_EDGE (pred, ei, block->preds)
2531 tree stmts = alloc_stmt_list ();
2534 eprime = avail[bprime->index];
2536 if (can_PRE_operation (eprime))
2538 #ifdef ENABLE_CHECKING
2541 /* eprime may be an invariant. */
2542 vh = TREE_CODE (eprime) == VALUE_HANDLE
2544 : get_value_handle (eprime);
2546 /* ensure that the virtual uses we need reach our block. */
2547 if (TREE_CODE (vh) == VALUE_HANDLE)
2552 VEC_iterate (tree, VALUE_HANDLE_VUSES (vh), i, vuse);
2555 size_t id = SSA_NAME_VERSION (vuse);
2556 gcc_assert (bitmap_bit_p (RVUSE_OUT (bprime), id)
2557 || IS_EMPTY_STMT (SSA_NAME_DEF_STMT (vuse)));
2561 builtexpr = create_expression_by_pieces (bprime,
2564 bsi_insert_on_edge (pred, stmts);
2565 avail[bprime->index] = builtexpr;
2569 /* If we didn't want a phi node, and we made insertions, we still have
2570 inserted new stuff, and thus return true. If we didn't want a phi node,
2571 and didn't make insertions, we haven't added anything new, so return
2573 if (nophi && insertions)
2575 else if (nophi && !insertions)
2578 /* Now build a phi for the new variable. */
2579 if (!prephitemp || TREE_TYPE (prephitemp) != type)
2581 prephitemp = create_tmp_var (type, "prephitmp");
2582 get_var_ann (prephitemp);
2586 add_referenced_var (temp);
2588 if (TREE_CODE (type) == COMPLEX_TYPE)
2589 DECL_COMPLEX_GIMPLE_REG_P (temp) = 1;
2590 temp = create_phi_node (temp, block);
2592 NECESSARY (temp) = 0;
2593 VEC_safe_push (tree, heap, inserted_exprs, temp);
2594 FOR_EACH_EDGE (pred, ei, block->preds)
2595 add_phi_arg (temp, avail[pred->src->index], pred);
2597 vn_add (PHI_RESULT (temp), val);
2599 /* The value should *not* exist in PHI_GEN, or else we wouldn't be doing
2600 this insertion, since we test for the existence of this value in PHI_GEN
2601 before proceeding with the partial redundancy checks in insert_aux.
2603 The value may exist in AVAIL_OUT, in particular, it could be represented
2604 by the expression we are trying to eliminate, in which case we want the
2605 replacement to occur. If it's not existing in AVAIL_OUT, we want it
2608 Similarly, to the PHI_GEN case, the value should not exist in NEW_SETS of
2609 this block, because if it did, it would have existed in our dominator's
2610 AVAIL_OUT, and would have been skipped due to the full redundancy check.
2613 bitmap_insert_into_set (PHI_GEN (block),
2615 bitmap_value_replace_in_set (AVAIL_OUT (block),
2617 bitmap_insert_into_set (NEW_SETS (block),
2620 if (dump_file && (dump_flags & TDF_DETAILS))
2622 fprintf (dump_file, "Created phi ");
2623 print_generic_expr (dump_file, temp, 0);
2624 fprintf (dump_file, " in block %d\n", block->index);
2632 /* Perform insertion of partially redundant values.
2633 For BLOCK, do the following:
2634 1. Propagate the NEW_SETS of the dominator into the current block.
2635 If the block has multiple predecessors,
2636 2a. Iterate over the ANTIC expressions for the block to see if
2637 any of them are partially redundant.
2638 2b. If so, insert them into the necessary predecessors to make
2639 the expression fully redundant.
2640 2c. Insert a new PHI merging the values of the predecessors.
2641 2d. Insert the new PHI, and the new expressions, into the
2643 3. Recursively call ourselves on the dominator children of BLOCK.
2648 insert_aux (basic_block block)
2651 bool new_stuff = false;
2656 dom = get_immediate_dominator (CDI_DOMINATORS, block);
2661 bitmap_set_t newset = NEW_SETS (dom);
2664 /* Note that we need to value_replace both NEW_SETS, and
2665 AVAIL_OUT. For both the case of NEW_SETS, the value may be
2666 represented by some non-simple expression here that we want
2667 to replace it with. */
2668 EXECUTE_IF_SET_IN_BITMAP (newset->expressions, 0, i, bi)
2670 bitmap_value_replace_in_set (NEW_SETS (block), ssa_name (i));
2671 bitmap_value_replace_in_set (AVAIL_OUT (block), ssa_name (i));
2674 if (!single_pred_p (block))
2676 value_set_node_t node;
2677 for (node = ANTIC_IN (block)->head;
2681 if (can_PRE_operation (node->expr)
2682 && !AGGREGATE_TYPE_P (TREE_TYPE (node->expr)))
2686 bool by_some = false;
2687 bool cant_insert = false;
2688 bool all_same = true;
2689 tree first_s = NULL;
2692 tree eprime = NULL_TREE;
2695 val = get_value_handle (node->expr);
2696 if (bitmap_set_contains_value (PHI_GEN (block), val))
2698 if (bitmap_set_contains_value (AVAIL_OUT (dom), val))
2700 if (dump_file && (dump_flags & TDF_DETAILS))
2701 fprintf (dump_file, "Found fully redundant value\n");
2705 avail = XCNEWVEC (tree, last_basic_block);
2706 FOR_EACH_EDGE (pred, ei, block->preds)
2711 /* This can happen in the very weird case
2712 that our fake infinite loop edges have caused a
2713 critical edge to appear. */
2714 if (EDGE_CRITICAL_P (pred))
2720 eprime = phi_translate (node->expr,
2724 /* eprime will generally only be NULL if the
2725 value of the expression, translated
2726 through the PHI for this predecessor, is
2727 undefined. If that is the case, we can't
2728 make the expression fully redundant,
2729 because its value is undefined along a
2730 predecessor path. We can thus break out
2731 early because it doesn't matter what the
2732 rest of the results are. */
2739 eprime = fully_constant_expression (eprime);
2740 vprime = get_value_handle (eprime);
2741 gcc_assert (vprime);
2742 edoubleprime = bitmap_find_leader (AVAIL_OUT (bprime),
2744 if (edoubleprime == NULL)
2746 avail[bprime->index] = eprime;
2751 avail[bprime->index] = edoubleprime;
2753 if (first_s == NULL)
2754 first_s = edoubleprime;
2755 else if (!operand_equal_p (first_s, edoubleprime,
2760 /* If we can insert it, it's not the same value
2761 already existing along every predecessor, and
2762 it's defined by some predecessor, it is
2763 partially redundant. */
2764 if (!cant_insert && !all_same && by_some)
2766 if (insert_into_preds_of_block (block, node, avail))
2769 /* If all edges produce the same value and that value is
2770 an invariant, then the PHI has the same value on all
2771 edges. Note this. */
2772 else if (!cant_insert && all_same && eprime
2773 && is_gimple_min_invariant (eprime)
2774 && !is_gimple_min_invariant (val))
2776 value_set_t exprset = VALUE_HANDLE_EXPR_SET (val);
2777 value_set_node_t node;
2779 for (node = exprset->head; node; node = node->next)
2781 if (TREE_CODE (node->expr) == SSA_NAME)
2783 vn_add (node->expr, eprime);
2784 pre_stats.constified++;
2794 for (son = first_dom_son (CDI_DOMINATORS, block);
2796 son = next_dom_son (CDI_DOMINATORS, son))
2798 new_stuff |= insert_aux (son);
2804 /* Perform insertion of partially redundant values. */
2809 bool new_stuff = true;
2811 int num_iterations = 0;
2814 NEW_SETS (bb) = bitmap_set_new ();
2820 new_stuff = insert_aux (ENTRY_BLOCK_PTR);
2822 if (num_iterations > 2 && dump_file && (dump_flags & TDF_STATS))
2823 fprintf (dump_file, "insert required %d iterations\n", num_iterations);
2827 /* Return true if VAR is an SSA variable with no defining statement in
2828 this procedure, *AND* isn't a live-on-entry parameter. */
2831 is_undefined_value (tree expr)
2833 return (TREE_CODE (expr) == SSA_NAME
2834 && IS_EMPTY_STMT (SSA_NAME_DEF_STMT (expr))
2835 /* PARM_DECLs and hard registers are always defined. */
2836 && TREE_CODE (SSA_NAME_VAR (expr)) != PARM_DECL);
2840 /* Given an SSA variable VAR and an expression EXPR, compute the value
2841 number for EXPR and create a value handle (VAL) for it. If VAR and
2842 EXPR are not the same, associate VAL with VAR. Finally, add VAR to
2843 S1 and its value handle to S2.
2845 VUSES represent the virtual use operands associated with EXPR (if
2849 add_to_sets (tree var, tree expr, tree stmt, bitmap_set_t s1,
2852 tree val = vn_lookup_or_add (expr, stmt);
2854 /* VAR and EXPR may be the same when processing statements for which
2855 we are not computing value numbers (e.g., non-assignments, or
2856 statements that make aliased stores). In those cases, we are
2857 only interested in making VAR available as its own value. */
2862 bitmap_insert_into_set (s1, var);
2863 bitmap_value_insert_into_set (s2, var);
2867 /* Given a unary or binary expression EXPR, create and return a new
2868 expression with the same structure as EXPR but with its operands
2869 replaced with the value handles of each of the operands of EXPR.
2871 VUSES represent the virtual use operands associated with EXPR (if
2872 any). Insert EXPR's operands into the EXP_GEN set for BLOCK. */
2875 create_value_expr_from (tree expr, basic_block block, tree stmt)
2878 enum tree_code code = TREE_CODE (expr);
2882 gcc_assert (TREE_CODE_CLASS (code) == tcc_unary
2883 || TREE_CODE_CLASS (code) == tcc_binary
2884 || TREE_CODE_CLASS (code) == tcc_comparison
2885 || TREE_CODE_CLASS (code) == tcc_reference
2886 || TREE_CODE_CLASS (code) == tcc_expression
2887 || TREE_CODE_CLASS (code) == tcc_exceptional
2888 || TREE_CODE_CLASS (code) == tcc_declaration);
2890 if (TREE_CODE_CLASS (code) == tcc_unary)
2891 pool = unary_node_pool;
2892 else if (TREE_CODE_CLASS (code) == tcc_reference)
2893 pool = reference_node_pool;
2894 else if (TREE_CODE_CLASS (code) == tcc_binary)
2895 pool = binary_node_pool;
2896 else if (TREE_CODE_CLASS (code) == tcc_comparison)
2897 pool = comparison_node_pool;
2898 else if (TREE_CODE_CLASS (code) == tcc_exceptional)
2900 gcc_assert (code == TREE_LIST);
2901 pool = list_node_pool;
2905 gcc_assert (code == CALL_EXPR);
2906 pool = expression_node_pool;
2909 vexpr = (tree) pool_alloc (pool);
2910 memcpy (vexpr, expr, tree_size (expr));
2912 /* This case is only for TREE_LIST's that appear as part of
2913 CALL_EXPR's. Anything else is a bug, but we can't easily verify
2914 this, hence this comment. TREE_LIST is not handled by the
2915 general case below is because they don't have a fixed length, or
2916 operands, so you can't access purpose/value/chain through
2917 TREE_OPERAND macros. */
2919 if (code == TREE_LIST)
2921 tree op = NULL_TREE;
2922 tree temp = NULL_TREE;
2923 if (TREE_CHAIN (vexpr))
2924 temp = create_value_expr_from (TREE_CHAIN (vexpr), block, stmt);
2925 TREE_CHAIN (vexpr) = temp ? temp : TREE_CHAIN (vexpr);
2928 /* Recursively value-numberize reference ops. */
2929 if (REFERENCE_CLASS_P (TREE_VALUE (vexpr)))
2932 op = TREE_VALUE (vexpr);
2933 tempop = create_value_expr_from (op, block, stmt);
2934 op = tempop ? tempop : op;
2936 TREE_VALUE (vexpr) = vn_lookup_or_add (op, stmt);
2940 op = TREE_VALUE (vexpr);
2941 TREE_VALUE (vexpr) = vn_lookup_or_add (TREE_VALUE (vexpr), NULL);
2943 /* This is the equivalent of inserting op into EXP_GEN like we
2945 if (!is_undefined_value (op))
2946 value_insert_into_set (EXP_GEN (block), op);
2951 for (i = 0; i < TREE_CODE_LENGTH (code); i++)
2955 op = TREE_OPERAND (expr, i);
2956 if (op == NULL_TREE)
2959 /* Recursively value-numberize reference ops and tree lists. */
2960 if (REFERENCE_CLASS_P (op))
2962 tree tempop = create_value_expr_from (op, block, stmt);
2963 op = tempop ? tempop : op;
2964 val = vn_lookup_or_add (op, stmt);
2966 else if (TREE_CODE (op) == TREE_LIST)
2970 gcc_assert (TREE_CODE (expr) == CALL_EXPR);
2971 tempop = create_value_expr_from (op, block, stmt);
2973 op = tempop ? tempop : op;
2974 vn_lookup_or_add (op, NULL);
2975 /* Unlike everywhere else, we do *not* want to replace the
2976 TREE_LIST itself with a value number, because support
2977 functions we call will blow up. */
2981 /* Create a value handle for OP and add it to VEXPR. */
2982 val = vn_lookup_or_add (op, NULL);
2984 if (!is_undefined_value (op) && TREE_CODE (op) != TREE_LIST)
2985 value_insert_into_set (EXP_GEN (block), op);
2987 if (TREE_CODE (val) == VALUE_HANDLE)
2988 TREE_TYPE (val) = TREE_TYPE (TREE_OPERAND (vexpr, i));
2990 TREE_OPERAND (vexpr, i) = val;
2998 /* Insert extra phis to merge values that are fully available from
2999 preds of BLOCK, but have no dominating representative coming from
3003 insert_extra_phis (basic_block block, basic_block dom)
3006 if (!single_pred_p (block))
3011 bitmap_set_t tempset = bitmap_set_new ();
3013 FOR_EACH_EDGE (e, ei, block->preds)
3015 /* We cannot handle abnormal incoming edges correctly. */
3016 if (e->flags & EDGE_ABNORMAL)
3021 bitmap_set_copy (tempset, AVAIL_OUT (e->src));
3025 bitmap_set_and (tempset, AVAIL_OUT (e->src));
3029 bitmap_set_and_compl (tempset, AVAIL_OUT (dom));
3031 if (!bitmap_set_empty_p (tempset))
3036 EXECUTE_IF_SET_IN_BITMAP (tempset->expressions, 0, i, bi)
3038 tree name = ssa_name (i);
3039 tree val = get_value_handle (name);
3042 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name))
3046 || TREE_TYPE (name) != TREE_TYPE (mergephitemp))
3048 mergephitemp = create_tmp_var (TREE_TYPE (name),
3050 get_var_ann (mergephitemp);
3052 temp = mergephitemp;
3054 if (dump_file && (dump_flags & TDF_DETAILS))
3056 fprintf (dump_file, "Creating phi ");
3057 print_generic_expr (dump_file, temp, 0);
3058 fprintf (dump_file, " to merge available but not dominating values ");
3061 add_referenced_var (temp);
3062 temp = create_phi_node (temp, block);
3063 NECESSARY (temp) = 0;
3064 VEC_safe_push (tree, heap, inserted_exprs, temp);
3066 FOR_EACH_EDGE (e, ei, block->preds)
3068 tree leader = bitmap_find_leader (AVAIL_OUT (e->src), val);
3070 gcc_assert (leader);
3071 add_phi_arg (temp, leader, e);
3073 if (dump_file && (dump_flags & TDF_DETAILS))
3075 print_generic_expr (dump_file, leader, 0);
3076 fprintf (dump_file, " in block %d,", e->src->index);
3080 vn_add (PHI_RESULT (temp), val);
3082 if (dump_file && (dump_flags & TDF_DETAILS))
3083 fprintf (dump_file, "\n");
3089 /* Given a statement STMT and its right hand side which is a load, try
3090 to look for the expression stored in the location for the load, and
3091 return true if a useful equivalence was recorded for LHS. */
3094 try_look_through_load (tree lhs, tree mem_ref, tree stmt, basic_block block)
3096 tree store_stmt = NULL;
3101 FOR_EACH_SSA_TREE_OPERAND (vuse, stmt, i, SSA_OP_VIRTUAL_USES)
3105 gcc_assert (TREE_CODE (vuse) == SSA_NAME);
3106 def_stmt = SSA_NAME_DEF_STMT (vuse);
3108 /* If there is no useful statement for this VUSE, we'll not find a
3109 useful expression to return either. Likewise, if there is a
3110 statement but it is not a simple assignment or it has virtual
3111 uses, we can stop right here. Note that this means we do
3112 not look through PHI nodes, which is intentional. */
3114 || TREE_CODE (def_stmt) != MODIFY_EXPR
3115 || !ZERO_SSA_OPERANDS (def_stmt, SSA_OP_VIRTUAL_USES))
3118 /* If this is not the same statement as one we have looked at for
3119 another VUSE of STMT already, we have two statements producing
3120 something that reaches our STMT. */
3121 if (store_stmt && store_stmt != def_stmt)
3125 /* Is this a store to the exact same location as the one we are
3126 loading from in STMT? */
3127 if (!operand_equal_p (TREE_OPERAND (def_stmt, 0), mem_ref, 0))
3130 /* Otherwise remember this statement and see if all other VUSEs
3131 come from the same statement. */
3132 store_stmt = def_stmt;
3136 /* Alright then, we have visited all VUSEs of STMT and we've determined
3137 that all of them come from the same statement STORE_STMT. See if there
3138 is a useful expression we can deduce from STORE_STMT. */
3139 rhs = TREE_OPERAND (store_stmt, 1);
3140 if ((TREE_CODE (rhs) == SSA_NAME
3141 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs))
3142 || is_gimple_min_invariant (rhs)
3143 || TREE_CODE (rhs) == ADDR_EXPR
3144 || TREE_INVARIANT (rhs))
3147 /* Yay! Compute a value number for the RHS of the statement and
3148 add its value to the AVAIL_OUT set for the block. Add the LHS
3150 add_to_sets (lhs, rhs, store_stmt, TMP_GEN (block), AVAIL_OUT (block));
3151 if (TREE_CODE (rhs) == SSA_NAME
3152 && !is_undefined_value (rhs))
3153 value_insert_into_set (EXP_GEN (block), rhs);
3160 /* Return a copy of NODE that is stored in the temporary alloc_pool's.
3161 This is made recursively true, so that the operands are stored in
3162 the pool as well. */
3165 poolify_tree (tree node)
3167 switch (TREE_CODE (node))
3171 tree temp = pool_alloc (reference_node_pool);
3172 memcpy (temp, node, tree_size (node));
3173 TREE_OPERAND (temp, 0) = poolify_tree (TREE_OPERAND (temp, 0));
3179 tree temp = pool_alloc (modify_expr_node_pool);
3180 memcpy (temp, node, tree_size (node));
3181 TREE_OPERAND (temp, 0) = poolify_tree (TREE_OPERAND (temp, 0));
3182 TREE_OPERAND (temp, 1) = poolify_tree (TREE_OPERAND (temp, 1));
3199 static tree modify_expr_template;
3201 /* Allocate a MODIFY_EXPR with TYPE, and operands OP1, OP2 in the
3202 alloc pools and return it. */
3204 poolify_modify_expr (tree type, tree op1, tree op2)
3206 if (modify_expr_template == NULL)
3207 modify_expr_template = build2 (MODIFY_EXPR, type, op1, op2);
3209 TREE_OPERAND (modify_expr_template, 0) = op1;
3210 TREE_OPERAND (modify_expr_template, 1) = op2;
3211 TREE_TYPE (modify_expr_template) = type;
3213 return poolify_tree (modify_expr_template);
3217 /* For each real store operation of the form
3218 *a = <value> that we see, create a corresponding fake store of the
3219 form storetmp_<version> = *a.
3221 This enables AVAIL computation to mark the results of stores as
3222 available. Without this, you'd need to do some computation to
3223 mark the result of stores as ANTIC and AVAIL at all the right
3225 To save memory, we keep the store
3226 statements pool allocated until we decide whether they are
3227 necessary or not. */
3230 insert_fake_stores (void)
3236 block_stmt_iterator bsi;
3237 for (bsi = bsi_start (block); !bsi_end_p (bsi); bsi_next (&bsi))
3239 tree stmt = bsi_stmt (bsi);
3241 /* We can't generate SSA names for stores that are complex
3242 or aggregate. We also want to ignore things whose
3243 virtual uses occur in abnormal phis. */
3245 if (TREE_CODE (stmt) == MODIFY_EXPR
3246 && TREE_CODE (TREE_OPERAND (stmt, 0)) == INDIRECT_REF
3247 && !AGGREGATE_TYPE_P (TREE_TYPE (TREE_OPERAND (stmt, 0)))
3248 && TREE_CODE (TREE_TYPE (TREE_OPERAND (stmt, 0))) != COMPLEX_TYPE)
3252 tree lhs = TREE_OPERAND (stmt, 0);
3253 tree rhs = TREE_OPERAND (stmt, 1);
3255 bool notokay = false;
3257 FOR_EACH_SSA_DEF_OPERAND (defp, stmt, iter, SSA_OP_VIRTUAL_DEFS)
3259 tree defvar = DEF_FROM_PTR (defp);
3260 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (defvar))
3270 if (!storetemp || TREE_TYPE (rhs) != TREE_TYPE (storetemp))
3272 storetemp = create_tmp_var (TREE_TYPE (rhs), "storetmp");
3273 get_var_ann (storetemp);
3276 new = poolify_modify_expr (TREE_TYPE (stmt), storetemp, lhs);
3278 lhs = make_ssa_name (storetemp, new);
3279 TREE_OPERAND (new, 0) = lhs;
3280 create_ssa_artficial_load_stmt (new, stmt);
3282 NECESSARY (new) = 0;
3283 VEC_safe_push (tree, heap, inserted_exprs, new);
3284 VEC_safe_push (tree, heap, need_creation, new);
3285 bsi_insert_after (&bsi, new, BSI_NEW_STMT);
3291 /* Turn the pool allocated fake stores that we created back into real
3292 GC allocated ones if they turned out to be necessary to PRE some
3296 realify_fake_stores (void)
3301 for (i = 0; VEC_iterate (tree, need_creation, i, stmt); i++)
3303 if (NECESSARY (stmt))
3305 block_stmt_iterator bsi;
3308 /* Mark the temp variable as referenced */
3309 add_referenced_var (SSA_NAME_VAR (TREE_OPERAND (stmt, 0)));
3311 /* Put the new statement in GC memory, fix up the
3312 SSA_NAME_DEF_STMT on it, and then put it in place of
3313 the old statement before the store in the IR stream
3314 as a plain ssa name copy. */
3315 bsi = bsi_for_stmt (stmt);
3317 newstmt = build2 (MODIFY_EXPR, void_type_node,
3318 TREE_OPERAND (stmt, 0),
3319 TREE_OPERAND (bsi_stmt (bsi), 1));
3320 SSA_NAME_DEF_STMT (TREE_OPERAND (newstmt, 0)) = newstmt;
3321 bsi_insert_before (&bsi, newstmt, BSI_SAME_STMT);
3322 bsi = bsi_for_stmt (stmt);
3323 bsi_remove (&bsi, true);
3326 release_defs (stmt);
3330 /* Tree-combine a value number expression *EXPR_P that does a type
3331 conversion with the value number expression of its operand.
3332 Returns true, if *EXPR_P simplifies to a value number or
3333 gimple min-invariant expression different from EXPR_P and
3334 sets *EXPR_P to the simplified expression value number.
3335 Otherwise returns false and does not change *EXPR_P. */
3338 try_combine_conversion (tree *expr_p)
3340 tree expr = *expr_p;
3343 if (!((TREE_CODE (expr) == NOP_EXPR
3344 || TREE_CODE (expr) == CONVERT_EXPR)
3345 && TREE_CODE (TREE_OPERAND (expr, 0)) == VALUE_HANDLE
3346 && !VALUE_HANDLE_VUSES (TREE_OPERAND (expr, 0))))
3349 t = fold_unary (TREE_CODE (expr), TREE_TYPE (expr),
3350 VALUE_HANDLE_EXPR_SET (TREE_OPERAND (expr, 0))->head->expr);
3354 /* Strip useless type conversions, which is safe in the optimizers but
3355 not generally in fold. */
3356 STRIP_USELESS_TYPE_CONVERSION (t);
3358 /* Disallow value expressions we have no value number for already, as
3359 we would miss a leader for it here. */
3360 if (!(TREE_CODE (t) == VALUE_HANDLE
3361 || is_gimple_min_invariant (t)))
3362 t = vn_lookup (t, NULL);
3372 /* Compute the AVAIL set for all basic blocks.
3374 This function performs value numbering of the statements in each basic
3375 block. The AVAIL sets are built from information we glean while doing
3376 this value numbering, since the AVAIL sets contain only one entry per
3379 AVAIL_IN[BLOCK] = AVAIL_OUT[dom(BLOCK)].
3380 AVAIL_OUT[BLOCK] = AVAIL_IN[BLOCK] U PHI_GEN[BLOCK] U TMP_GEN[BLOCK]. */
3383 compute_avail (void)
3385 basic_block block, son;
3386 basic_block *worklist;
3389 /* For arguments with default definitions, we pretend they are
3390 defined in the entry block. */
3391 for (param = DECL_ARGUMENTS (current_function_decl);
3393 param = TREE_CHAIN (param))
3395 if (default_def (param) != NULL)
3397 tree def = default_def (param);
3398 vn_lookup_or_add (def, NULL);
3399 bitmap_insert_into_set (TMP_GEN (ENTRY_BLOCK_PTR), def);
3400 bitmap_value_insert_into_set (AVAIL_OUT (ENTRY_BLOCK_PTR), def);
3404 /* Likewise for the static chain decl. */
3405 if (cfun->static_chain_decl)
3407 param = cfun->static_chain_decl;
3408 if (default_def (param) != NULL)
3410 tree def = default_def (param);
3411 vn_lookup_or_add (def, NULL);
3412 bitmap_insert_into_set (TMP_GEN (ENTRY_BLOCK_PTR), def);
3413 bitmap_value_insert_into_set (AVAIL_OUT (ENTRY_BLOCK_PTR), def);
3417 /* Allocate the worklist. */
3418 worklist = XNEWVEC (basic_block, n_basic_blocks);
3420 /* Seed the algorithm by putting the dominator children of the entry
3421 block on the worklist. */
3422 for (son = first_dom_son (CDI_DOMINATORS, ENTRY_BLOCK_PTR);
3424 son = next_dom_son (CDI_DOMINATORS, son))
3425 worklist[sp++] = son;
3427 /* Loop until the worklist is empty. */
3430 block_stmt_iterator bsi;
3433 unsigned int stmt_uid = 1;
3435 /* Pick a block from the worklist. */
3436 block = worklist[--sp];
3438 /* Initially, the set of available values in BLOCK is that of
3439 its immediate dominator. */
3440 dom = get_immediate_dominator (CDI_DOMINATORS, block);
3442 bitmap_set_copy (AVAIL_OUT (block), AVAIL_OUT (dom));
3445 insert_extra_phis (block, dom);
3447 /* Generate values for PHI nodes. */
3448 for (phi = phi_nodes (block); phi; phi = PHI_CHAIN (phi))
3449 /* We have no need for virtual phis, as they don't represent
3450 actual computations. */
3451 if (is_gimple_reg (PHI_RESULT (phi)))
3452 add_to_sets (PHI_RESULT (phi), PHI_RESULT (phi), NULL,
3453 PHI_GEN (block), AVAIL_OUT (block));
3455 /* Now compute value numbers and populate value sets with all
3456 the expressions computed in BLOCK. */
3457 for (bsi = bsi_start (block); !bsi_end_p (bsi); bsi_next (&bsi))
3463 stmt = bsi_stmt (bsi);
3464 ann = stmt_ann (stmt);
3466 ann->uid = stmt_uid++;
3468 /* For regular value numbering, we are only interested in
3469 assignments of the form X_i = EXPR, where EXPR represents
3470 an "interesting" computation, it has no volatile operands
3471 and X_i doesn't flow through an abnormal edge. */
3472 if (TREE_CODE (stmt) == MODIFY_EXPR
3473 && !ann->has_volatile_ops
3474 && TREE_CODE (TREE_OPERAND (stmt, 0)) == SSA_NAME
3475 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (TREE_OPERAND (stmt, 0)))
3477 tree lhs = TREE_OPERAND (stmt, 0);
3478 tree rhs = TREE_OPERAND (stmt, 1);
3480 /* Try to look through loads. */
3481 if (TREE_CODE (lhs) == SSA_NAME
3482 && !ZERO_SSA_OPERANDS (stmt, SSA_OP_VIRTUAL_USES)
3483 && try_look_through_load (lhs, rhs, stmt, block))
3486 STRIP_USELESS_TYPE_CONVERSION (rhs);
3487 if (can_value_number_operation (rhs))
3489 /* For value numberable operation, create a
3490 duplicate expression with the operands replaced
3491 with the value handles of the original RHS. */
3492 tree newt = create_value_expr_from (rhs, block, stmt);
3495 /* If we can combine a conversion expression
3496 with the expression for its operand just
3497 record the value number for it. */
3498 if (try_combine_conversion (&newt))
3502 tree val = vn_lookup_or_add (newt, stmt);
3504 value_insert_into_set (EXP_GEN (block), newt);
3506 bitmap_insert_into_set (TMP_GEN (block), lhs);
3507 bitmap_value_insert_into_set (AVAIL_OUT (block), lhs);
3511 else if ((TREE_CODE (rhs) == SSA_NAME
3512 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs))
3513 || is_gimple_min_invariant (rhs)
3514 || TREE_CODE (rhs) == ADDR_EXPR
3515 || TREE_INVARIANT (rhs)
3518 /* Compute a value number for the RHS of the statement
3519 and add its value to the AVAIL_OUT set for the block.
3520 Add the LHS to TMP_GEN. */
3521 add_to_sets (lhs, rhs, stmt, TMP_GEN (block),
3524 if (TREE_CODE (rhs) == SSA_NAME
3525 && !is_undefined_value (rhs))
3526 value_insert_into_set (EXP_GEN (block), rhs);
3531 /* For any other statement that we don't recognize, simply
3532 make the names generated by the statement available in
3533 AVAIL_OUT and TMP_GEN. */
3534 FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_DEF)
3535 add_to_sets (op, op, NULL, TMP_GEN (block), AVAIL_OUT (block));
3537 FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_USE)
3538 add_to_sets (op, op, NULL, NULL , AVAIL_OUT (block));
3541 /* Put the dominator children of BLOCK on the worklist of blocks
3542 to compute available sets for. */
3543 for (son = first_dom_son (CDI_DOMINATORS, block);
3545 son = next_dom_son (CDI_DOMINATORS, son))
3546 worklist[sp++] = son;
3553 /* Eliminate fully redundant computations. */
3562 block_stmt_iterator i;
3564 for (i = bsi_start (b); !bsi_end_p (i); bsi_next (&i))
3566 tree stmt = bsi_stmt (i);
3568 /* Lookup the RHS of the expression, see if we have an
3569 available computation for it. If so, replace the RHS with
3570 the available computation. */
3571 if (TREE_CODE (stmt) == MODIFY_EXPR
3572 && TREE_CODE (TREE_OPERAND (stmt, 0)) == SSA_NAME
3573 && TREE_CODE (TREE_OPERAND (stmt ,1)) != SSA_NAME
3574 && !is_gimple_min_invariant (TREE_OPERAND (stmt, 1))
3575 && !stmt_ann (stmt)->has_volatile_ops)
3577 tree lhs = TREE_OPERAND (stmt, 0);
3578 tree *rhs_p = &TREE_OPERAND (stmt, 1);
3581 sprime = bitmap_find_leader (AVAIL_OUT (b),
3582 vn_lookup (lhs, NULL));
3585 && (TREE_CODE (*rhs_p) != SSA_NAME
3586 || may_propagate_copy (*rhs_p, sprime)))
3588 gcc_assert (sprime != *rhs_p);
3590 if (dump_file && (dump_flags & TDF_DETAILS))
3592 fprintf (dump_file, "Replaced ");
3593 print_generic_expr (dump_file, *rhs_p, 0);
3594 fprintf (dump_file, " with ");
3595 print_generic_expr (dump_file, sprime, 0);
3596 fprintf (dump_file, " in ");
3597 print_generic_stmt (dump_file, stmt, 0);
3600 if (TREE_CODE (sprime) == SSA_NAME)
3601 NECESSARY (SSA_NAME_DEF_STMT (sprime)) = 1;
3602 /* We need to make sure the new and old types actually match,
3603 which may require adding a simple cast, which fold_convert
3605 if (TREE_CODE (*rhs_p) != SSA_NAME
3606 && !tree_ssa_useless_type_conversion_1 (TREE_TYPE (*rhs_p),
3607 TREE_TYPE (sprime)))
3608 sprime = fold_convert (TREE_TYPE (*rhs_p), sprime);
3610 pre_stats.eliminations++;
3611 propagate_tree_value (rhs_p, sprime);
3614 /* If we removed EH side effects from the statement, clean
3615 its EH information. */
3616 if (maybe_clean_or_replace_eh_stmt (stmt, stmt))
3618 bitmap_set_bit (need_eh_cleanup,
3619 bb_for_stmt (stmt)->index);
3620 if (dump_file && (dump_flags & TDF_DETAILS))
3621 fprintf (dump_file, " Removed EH side effects.\n");
3629 /* Borrow a bit of tree-ssa-dce.c for the moment.
3630 XXX: In 4.1, we should be able to just run a DCE pass after PRE, though
3631 this may be a bit faster, and we may want critical edges kept split. */
3633 /* If OP's defining statement has not already been determined to be necessary,
3634 mark that statement necessary. Return the stmt, if it is newly
3638 mark_operand_necessary (tree op)
3644 if (TREE_CODE (op) != SSA_NAME)
3647 stmt = SSA_NAME_DEF_STMT (op);
3650 if (NECESSARY (stmt)
3651 || IS_EMPTY_STMT (stmt))
3654 NECESSARY (stmt) = 1;
3658 /* Because we don't follow exactly the standard PRE algorithm, and decide not
3659 to insert PHI nodes sometimes, and because value numbering of casts isn't
3660 perfect, we sometimes end up inserting dead code. This simple DCE-like
3661 pass removes any insertions we made that weren't actually used. */
3664 remove_dead_inserted_code (void)
3666 VEC(tree,heap) *worklist = NULL;
3670 worklist = VEC_alloc (tree, heap, VEC_length (tree, inserted_exprs));
3671 for (i = 0; VEC_iterate (tree, inserted_exprs, i, t); i++)
3674 VEC_quick_push (tree, worklist, t);
3676 while (VEC_length (tree, worklist) > 0)
3678 t = VEC_pop (tree, worklist);
3680 /* PHI nodes are somewhat special in that each PHI alternative has
3681 data and control dependencies. All the statements feeding the
3682 PHI node's arguments are always necessary. */
3683 if (TREE_CODE (t) == PHI_NODE)
3687 VEC_reserve (tree, heap, worklist, PHI_NUM_ARGS (t));
3688 for (k = 0; k < PHI_NUM_ARGS (t); k++)
3690 tree arg = PHI_ARG_DEF (t, k);
3691 if (TREE_CODE (arg) == SSA_NAME)
3693 arg = mark_operand_necessary (arg);
3695 VEC_quick_push (tree, worklist, arg);
3701 /* Propagate through the operands. Examine all the USE, VUSE and
3702 V_MAY_DEF operands in this statement. Mark all the statements
3703 which feed this statement's uses as necessary. */
3707 /* The operands of V_MAY_DEF expressions are also needed as they
3708 represent potential definitions that may reach this
3709 statement (V_MAY_DEF operands allow us to follow def-def
3712 FOR_EACH_SSA_TREE_OPERAND (use, t, iter, SSA_OP_ALL_USES)
3714 tree n = mark_operand_necessary (use);
3716 VEC_safe_push (tree, heap, worklist, n);
3721 for (i = 0; VEC_iterate (tree, inserted_exprs, i, t); i++)
3725 block_stmt_iterator bsi;
3727 if (dump_file && (dump_flags & TDF_DETAILS))
3729 fprintf (dump_file, "Removing unnecessary insertion:");
3730 print_generic_stmt (dump_file, t, 0);
3733 if (TREE_CODE (t) == PHI_NODE)
3735 remove_phi_node (t, NULL);
3739 bsi = bsi_for_stmt (t);
3740 bsi_remove (&bsi, true);
3745 VEC_free (tree, heap, worklist);
3748 /* Initialize data structures used by PRE. */
3751 init_pre (bool do_fre)
3757 inserted_exprs = NULL;
3758 need_creation = NULL;
3759 pretemp = NULL_TREE;
3760 storetemp = NULL_TREE;
3761 mergephitemp = NULL_TREE;
3762 prephitemp = NULL_TREE;
3766 current_loops = loop_optimizer_init (LOOPS_NORMAL);
3768 connect_infinite_loops_to_exit ();
3769 memset (&pre_stats, 0, sizeof (pre_stats));
3771 /* If block 0 has more than one predecessor, it means that its PHI
3772 nodes will have arguments coming from block -1. This creates
3773 problems for several places in PRE that keep local arrays indexed
3774 by block number. To prevent this, we split the edge coming from
3775 ENTRY_BLOCK_PTR (FIXME, if ENTRY_BLOCK_PTR had an index number
3776 different than -1 we wouldn't have to hack this. tree-ssa-dce.c
3777 needs a similar change). */
3778 if (!single_pred_p (single_succ (ENTRY_BLOCK_PTR)))
3779 if (!(single_succ_edge (ENTRY_BLOCK_PTR)->flags & EDGE_ABNORMAL))
3780 split_edge (single_succ_edge (ENTRY_BLOCK_PTR));
3783 bb->aux = xcalloc (1, sizeof (struct bb_value_sets));
3785 bitmap_obstack_initialize (&grand_bitmap_obstack);
3786 phi_translate_table = htab_create (511, expr_pred_trans_hash,
3787 expr_pred_trans_eq, free);
3788 value_set_pool = create_alloc_pool ("Value sets",
3789 sizeof (struct value_set), 30);
3790 bitmap_set_pool = create_alloc_pool ("Bitmap sets",
3791 sizeof (struct bitmap_set), 30);
3792 value_set_node_pool = create_alloc_pool ("Value set nodes",
3793 sizeof (struct value_set_node), 30);
3794 calculate_dominance_info (CDI_POST_DOMINATORS);
3795 calculate_dominance_info (CDI_DOMINATORS);
3796 binary_node_pool = create_alloc_pool ("Binary tree nodes",
3797 tree_code_size (PLUS_EXPR), 30);
3798 unary_node_pool = create_alloc_pool ("Unary tree nodes",
3799 tree_code_size (NEGATE_EXPR), 30);
3800 reference_node_pool = create_alloc_pool ("Reference tree nodes",
3801 tree_code_size (ARRAY_REF), 30);
3802 expression_node_pool = create_alloc_pool ("Expression tree nodes",
3803 tree_code_size (CALL_EXPR), 30);
3804 list_node_pool = create_alloc_pool ("List tree nodes",
3805 tree_code_size (TREE_LIST), 30);
3806 comparison_node_pool = create_alloc_pool ("Comparison tree nodes",
3807 tree_code_size (EQ_EXPR), 30);
3808 modify_expr_node_pool = create_alloc_pool ("MODIFY_EXPR nodes",
3809 tree_code_size (MODIFY_EXPR),
3811 modify_expr_template = NULL;
3815 EXP_GEN (bb) = set_new (true);
3816 PHI_GEN (bb) = bitmap_set_new ();
3817 TMP_GEN (bb) = bitmap_set_new ();
3818 AVAIL_OUT (bb) = bitmap_set_new ();
3821 need_eh_cleanup = BITMAP_ALLOC (NULL);
3825 /* Deallocate data structures used by PRE. */
3828 fini_pre (bool do_fre)
3833 VEC_free (tree, heap, inserted_exprs);
3834 VEC_free (tree, heap, need_creation);
3835 bitmap_obstack_release (&grand_bitmap_obstack);
3836 free_alloc_pool (value_set_pool);
3837 free_alloc_pool (bitmap_set_pool);
3838 free_alloc_pool (value_set_node_pool);
3839 free_alloc_pool (binary_node_pool);
3840 free_alloc_pool (reference_node_pool);
3841 free_alloc_pool (unary_node_pool);
3842 free_alloc_pool (list_node_pool);
3843 free_alloc_pool (expression_node_pool);
3844 free_alloc_pool (comparison_node_pool);
3845 free_alloc_pool (modify_expr_node_pool);
3846 htab_delete (phi_translate_table);
3847 remove_fake_exit_edges ();
3855 free_dominance_info (CDI_POST_DOMINATORS);
3858 if (!bitmap_empty_p (need_eh_cleanup))
3860 tree_purge_all_dead_eh_edges (need_eh_cleanup);
3861 cleanup_tree_cfg ();
3864 BITMAP_FREE (need_eh_cleanup);
3866 /* Wipe out pointers to VALUE_HANDLEs. In the not terribly distant
3867 future we will want them to be persistent though. */
3868 for (i = 0; i < num_ssa_names; i++)
3870 tree name = ssa_name (i);
3875 if (SSA_NAME_VALUE (name)
3876 && TREE_CODE (SSA_NAME_VALUE (name)) == VALUE_HANDLE)
3877 SSA_NAME_VALUE (name) = NULL;
3879 if (!do_fre && current_loops)
3881 loop_optimizer_finalize (current_loops);
3882 current_loops = NULL;
3886 /* Main entry point to the SSA-PRE pass. DO_FRE is true if the caller
3887 only wants to do full redundancy elimination. */
3890 execute_pre (bool do_fre)
3895 insert_fake_stores ();
3897 /* Collect and value number expressions computed in each basic block. */
3900 if (dump_file && (dump_flags & TDF_DETAILS))
3906 print_value_set (dump_file, EXP_GEN (bb), "exp_gen", bb->index);
3907 bitmap_print_value_set (dump_file, TMP_GEN (bb), "tmp_gen",
3909 bitmap_print_value_set (dump_file, AVAIL_OUT (bb), "avail_out",
3914 /* Insert can get quite slow on an incredibly large number of basic
3915 blocks due to some quadratic behavior. Until this behavior is
3916 fixed, don't run it when he have an incredibly large number of
3917 bb's. If we aren't going to run insert, there is no point in
3918 computing ANTIC, either, even though it's plenty fast. */
3919 if (!do_fre && n_basic_blocks < 4000)
3921 vuse_names = XCNEWVEC (bitmap, num_ssa_names);
3922 compute_rvuse_and_antic_safe ();
3928 /* Remove all the redundant expressions. */
3932 if (dump_file && (dump_flags & TDF_STATS))
3934 fprintf (dump_file, "Insertions: %d\n", pre_stats.insertions);
3935 fprintf (dump_file, "New PHIs: %d\n", pre_stats.phis);
3936 fprintf (dump_file, "Eliminated: %d\n", pre_stats.eliminations);
3937 fprintf (dump_file, "Constified: %d\n", pre_stats.constified);
3940 bsi_commit_edge_inserts ();
3944 remove_dead_inserted_code ();
3945 realify_fake_stores ();
3952 /* Gate and execute functions for PRE. */
3957 execute_pre (false);
3964 return flag_tree_pre != 0;
3967 struct tree_opt_pass pass_pre =
3970 gate_pre, /* gate */
3971 do_pre, /* execute */
3974 0, /* static_pass_number */
3975 TV_TREE_PRE, /* tv_id */
3976 PROP_no_crit_edges | PROP_cfg
3977 | PROP_ssa | PROP_alias, /* properties_required */
3978 0, /* properties_provided */
3979 0, /* properties_destroyed */
3980 0, /* todo_flags_start */
3981 TODO_update_ssa_only_virtuals | TODO_dump_func | TODO_ggc_collect
3982 | TODO_verify_ssa, /* todo_flags_finish */
3987 /* Gate and execute functions for FRE. */
3999 return flag_tree_fre != 0;
4002 struct tree_opt_pass pass_fre =
4005 gate_fre, /* gate */
4006 execute_fre, /* execute */
4009 0, /* static_pass_number */
4010 TV_TREE_FRE, /* tv_id */
4011 PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */
4012 0, /* properties_provided */
4013 0, /* properties_destroyed */
4014 0, /* todo_flags_start */
4015 TODO_dump_func | TODO_ggc_collect | TODO_verify_ssa, /* todo_flags_finish */