2 Copyright (C) 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc.
3 Contributed by Daniel Berlin <dan@dberlin.org> and Steven Bosscher
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify
9 it under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 2, or (at your option)
13 GCC is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 GNU General Public License for more details.
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING. If not, write to
20 the Free Software Foundation, 59 Temple Place - Suite 330,
21 Boston, MA 02111-1307, USA. */
25 #include "coretypes.h"
30 #include "basic-block.h"
31 #include "diagnostic.h"
32 #include "tree-inline.h"
33 #include "tree-flow.h"
34 #include "tree-gimple.h"
35 #include "tree-dump.h"
39 #include "tree-iterator.h"
41 #include "alloc-pool.h"
42 #include "tree-pass.h"
45 #include "langhooks.h"
50 1. Avail sets can be shared by making an avail_find_leader that
51 walks up the dominator tree and looks in those avail sets.
52 This might affect code optimality, it's unclear right now.
53 2. Load motion can be performed by value numbering the loads the
54 same as we do other expressions. This requires iterative
55 hashing the vuses into the values. Right now we simply assign
56 a new value every time we see a statement with a vuse.
57 3. Strength reduction can be performed by anticipating expressions
58 we can repair later on.
59 4. We can do back-substitution or smarter value numbering to catch
60 commutative expressions split up over multiple statements.
63 /* For ease of terminology, "expression node" in the below refers to
64 every expression node but MODIFY_EXPR, because MODIFY_EXPR's represent
65 the actual statement containing the expressions we care about, and
66 we cache the value number by putting it in the expression. */
70 First we walk the statements to generate the AVAIL sets, the
71 EXP_GEN sets, and the tmp_gen sets. EXP_GEN sets represent the
72 generation of values/expressions by a given block. We use them
73 when computing the ANTIC sets. The AVAIL sets consist of
74 SSA_NAME's that represent values, so we know what values are
75 available in what blocks. AVAIL is a forward dataflow problem. In
76 SSA, values are never killed, so we don't need a kill set, or a
77 fixpoint iteration, in order to calculate the AVAIL sets. In
78 traditional parlance, AVAIL sets tell us the downsafety of the
81 Next, we generate the ANTIC sets. These sets represent the
82 anticipatable expressions. ANTIC is a backwards dataflow
83 problem.An expression is anticipatable in a given block if it could
84 be generated in that block. This means that if we had to perform
85 an insertion in that block, of the value of that expression, we
86 could. Calculating the ANTIC sets requires phi translation of
87 expressions, because the flow goes backwards through phis. We must
88 iterate to a fixpoint of the ANTIC sets, because we have a kill
89 set. Even in SSA form, values are not live over the entire
90 function, only from their definition point onwards. So we have to
91 remove values from the ANTIC set once we go past the definition
92 point of the leaders that make them up.
93 compute_antic/compute_antic_aux performs this computation.
95 Third, we perform insertions to make partially redundant
96 expressions fully redundant.
98 An expression is partially redundant (excluding partial
101 1. It is AVAIL in some, but not all, of the predecessors of a
103 2. It is ANTIC in all the predecessors.
105 In order to make it fully redundant, we insert the expression into
106 the predecessors where it is not available, but is ANTIC.
107 insert/insert_aux performs this insertion.
109 Fourth, we eliminate fully redundant expressions.
110 This is a simple statement walk that replaces redundant
111 calculations with the now available values. */
113 /* Representations of value numbers:
115 Value numbers are represented using the "value handle" approach.
116 This means that each SSA_NAME (and for other reasons to be
117 disclosed in a moment, expression nodes) has a value handle that
118 can be retrieved through get_value_handle. This value handle, *is*
119 the value number of the SSA_NAME. You can pointer compare the
120 value handles for equivalence purposes.
122 For debugging reasons, the value handle is internally more than
123 just a number, it is a VAR_DECL named "value.x", where x is a
124 unique number for each value number in use. This allows
125 expressions with SSA_NAMES replaced by value handles to still be
126 pretty printed in a sane way. They simply print as "value.3 *
129 Expression nodes have value handles associated with them as a
130 cache. Otherwise, we'd have to look them up again in the hash
131 table This makes significant difference (factor of two or more) on
132 some test cases. They can be thrown away after the pass is
135 /* Representation of expressions on value numbers:
137 In some portions of this code, you will notice we allocate "fake"
138 analogues to the expression we are value numbering, and replace the
139 operands with the values of the expression. Since we work on
140 values, and not just names, we canonicalize expressions to value
141 expressions for use in the ANTIC sets, the EXP_GEN set, etc.
143 This is theoretically unnecessary, it just saves a bunch of
144 repeated get_value_handle and find_leader calls in the remainder of
145 the code, trading off temporary memory usage for speed. The tree
146 nodes aren't actually creating more garbage, since they are
147 allocated in a special pools which are thrown away at the end of
150 All of this also means that if you print the EXP_GEN or ANTIC sets,
151 you will see "value.5 + value.7" in the set, instead of "a_55 +
152 b_66" or something. The only thing that actually cares about
153 seeing the value leaders is phi translation, and it needs to be
154 able to find the leader for a value in an arbitrary block, so this
155 "value expression" form is perfect for it (otherwise you'd do
156 get_value_handle->find_leader->translate->get_value_handle->find_leader).*/
159 /* Representation of sets:
161 There are currently two types of sets used, hopefully to be unified soon.
162 The AVAIL sets do not need to be sorted in any particular order,
163 and thus, are simply represented as two bitmaps, one that keeps
164 track of values present in the set, and one that keeps track of
165 expressions present in the set.
167 The other sets are represented as doubly linked lists kept in topological
168 order, with an optional supporting bitmap of values present in the
169 set. The sets represent values, and the elements can be values or
170 expressions. The elements can appear in different sets, but each
171 element can only appear once in each set.
173 Since each node in the set represents a value, we also want to be
174 able to map expression, set pairs to something that tells us
175 whether the value is present is a set. We use a per-set bitmap for
176 that. The value handles also point to a linked list of the
177 expressions they represent via a tree annotation. This is mainly
178 useful only for debugging, since we don't do identity lookups. */
181 /* A value set element. Basically a single linked list of
182 expressions/values. */
183 typedef struct value_set_node
188 /* A pointer to the next element of the value set. */
189 struct value_set_node *next;
193 /* A value set. This is a singly linked list of value_set_node
194 elements with a possible bitmap that tells us what values exist in
195 the set. This set must be kept in topologically sorted order. */
196 typedef struct value_set
198 /* The head of the list. Used for iterating over the list in
200 value_set_node_t head;
202 /* The tail of the list. Used for tail insertions, which are
203 necessary to keep the set in topologically sorted order because
204 of how the set is built. */
205 value_set_node_t tail;
207 /* The length of the list. */
210 /* True if the set is indexed, which means it contains a backing
211 bitmap for quick determination of whether certain values exist in the
215 /* The bitmap of values that exist in the set. May be NULL in an
216 empty or non-indexed set. */
222 /* An unordered bitmap set. One bitmap tracks values, the other,
224 typedef struct bitmap_set
230 /* Sets that we need to keep track of. */
231 typedef struct bb_value_sets
233 /* The EXP_GEN set, which represents expressions/values generated in
237 /* The PHI_GEN set, which represents PHI results generated in a
239 bitmap_set_t phi_gen;
241 /* The TMP_GEN set, which represents results/temporaries generated
242 in a basic block. IE the LHS of an expression. */
243 bitmap_set_t tmp_gen;
245 /* The AVAIL_OUT set, which represents which values are available in
246 a given basic block. */
247 bitmap_set_t avail_out;
249 /* The ANTIC_IN set, which represents which values are anticiptable
250 in a given basic block. */
251 value_set_t antic_in;
253 /* The NEW_SETS set, which is used during insertion to augment the
254 AVAIL_OUT set of blocks with the new insertions performed during
255 the current iteration. */
256 bitmap_set_t new_sets;
259 #define EXP_GEN(BB) ((bb_value_sets_t) ((BB)->aux))->exp_gen
260 #define PHI_GEN(BB) ((bb_value_sets_t) ((BB)->aux))->phi_gen
261 #define TMP_GEN(BB) ((bb_value_sets_t) ((BB)->aux))->tmp_gen
262 #define AVAIL_OUT(BB) ((bb_value_sets_t) ((BB)->aux))->avail_out
263 #define ANTIC_IN(BB) ((bb_value_sets_t) ((BB)->aux))->antic_in
264 #define NEW_SETS(BB) ((bb_value_sets_t) ((BB)->aux))->new_sets
266 /* This structure is used to keep track of statistics on what
267 optimization PRE was able to perform. */
270 /* The number of RHS computations eliminated by PRE. */
273 /* The number of new expressions/temporaries generated by PRE. */
276 /* The number of new PHI nodes added by PRE. */
279 /* The number of values found constant. */
285 static tree bitmap_find_leader (bitmap_set_t, tree);
286 static tree find_leader (value_set_t, tree);
287 static void value_insert_into_set (value_set_t, tree);
288 static void bitmap_value_insert_into_set (bitmap_set_t, tree);
289 static void bitmap_value_replace_in_set (bitmap_set_t, tree);
290 static void insert_into_set (value_set_t, tree);
291 static void bitmap_set_copy (bitmap_set_t, bitmap_set_t);
292 static bool bitmap_set_contains_value (bitmap_set_t, tree);
293 static bitmap_set_t bitmap_set_new (void);
294 static value_set_t set_new (bool);
295 static bool is_undefined_value (tree);
296 static tree create_expression_by_pieces (basic_block, tree, tree);
299 /* We can add and remove elements and entries to and from sets
300 and hash tables, so we use alloc pools for them. */
302 static alloc_pool value_set_pool;
303 static alloc_pool bitmap_set_pool;
304 static alloc_pool value_set_node_pool;
305 static alloc_pool binary_node_pool;
306 static alloc_pool unary_node_pool;
307 static alloc_pool reference_node_pool;
308 static bitmap_obstack grand_bitmap_obstack;
310 /* Set of blocks with statements that have had its EH information
312 static bitmap need_eh_cleanup;
314 /* The phi_translate_table caches phi translations for a given
315 expression and predecessor. */
317 static htab_t phi_translate_table;
319 /* A three tuple {e, pred, v} used to cache phi translations in the
320 phi_translate_table. */
322 typedef struct expr_pred_trans_d
324 /* The expression. */
327 /* The predecessor block along which we translated the expression. */
330 /* The value that resulted from the translation. */
333 /* The hashcode for the expression, pred pair. This is cached for
336 } *expr_pred_trans_t;
338 /* Return the hash value for a phi translation table entry. */
341 expr_pred_trans_hash (const void *p)
343 const expr_pred_trans_t ve = (expr_pred_trans_t) p;
347 /* Return true if two phi translation table entries are the same.
348 P1 and P2 should point to the expr_pred_trans_t's to be compared.*/
351 expr_pred_trans_eq (const void *p1, const void *p2)
353 const expr_pred_trans_t ve1 = (expr_pred_trans_t) p1;
354 const expr_pred_trans_t ve2 = (expr_pred_trans_t) p2;
355 basic_block b1 = ve1->pred;
356 basic_block b2 = ve2->pred;
359 /* If they are not translations for the same basic block, they can't
364 /* If they are for the same basic block, determine if the
365 expressions are equal. */
366 if (expressions_equal_p (ve1->e, ve2->e))
372 /* Search in the phi translation table for the translation of
373 expression E in basic block PRED. Return the translated value, if
374 found, NULL otherwise. */
377 phi_trans_lookup (tree e, basic_block pred)
380 struct expr_pred_trans_d ept;
383 ept.hashcode = vn_compute (e, (unsigned long) pred, NULL);
384 slot = htab_find_slot_with_hash (phi_translate_table, &ept, ept.hashcode,
389 return ((expr_pred_trans_t) *slot)->v;
393 /* Add the tuple mapping from {expression E, basic block PRED} to
394 value V, to the phi translation table. */
397 phi_trans_add (tree e, tree v, basic_block pred)
400 expr_pred_trans_t new_pair = xmalloc (sizeof (*new_pair));
402 new_pair->pred = pred;
404 new_pair->hashcode = vn_compute (e, (unsigned long) pred, NULL);
405 slot = htab_find_slot_with_hash (phi_translate_table, new_pair,
406 new_pair->hashcode, INSERT);
409 *slot = (void *) new_pair;
413 /* Add expression E to the expression set of value V. */
416 add_to_value (tree v, tree e)
418 /* Constants have no expression sets. */
419 if (is_gimple_min_invariant (v))
422 if (VALUE_HANDLE_EXPR_SET (v) == NULL)
423 VALUE_HANDLE_EXPR_SET (v) = set_new (false);
425 insert_into_set (VALUE_HANDLE_EXPR_SET (v), e);
429 /* Return true if value V exists in the bitmap for SET. */
432 value_exists_in_set_bitmap (value_set_t set, tree v)
437 return bitmap_bit_p (set->values, VALUE_HANDLE_ID (v));
441 /* Remove value V from the bitmap for SET. */
444 value_remove_from_set_bitmap (value_set_t set, tree v)
446 gcc_assert (set->indexed);
451 bitmap_clear_bit (set->values, VALUE_HANDLE_ID (v));
455 /* Insert the value number V into the bitmap of values existing in
459 value_insert_into_set_bitmap (value_set_t set, tree v)
461 gcc_assert (set->indexed);
463 if (set->values == NULL)
464 set->values = BITMAP_ALLOC (&grand_bitmap_obstack);
466 bitmap_set_bit (set->values, VALUE_HANDLE_ID (v));
470 /* Create a new bitmap set and return it. */
473 bitmap_set_new (void)
475 bitmap_set_t ret = pool_alloc (bitmap_set_pool);
476 ret->expressions = BITMAP_ALLOC (&grand_bitmap_obstack);
477 ret->values = BITMAP_ALLOC (&grand_bitmap_obstack);
481 /* Create a new set. */
484 set_new (bool indexed)
487 ret = pool_alloc (value_set_pool);
488 ret->head = ret->tail = NULL;
490 ret->indexed = indexed;
495 /* Insert an expression EXPR into a bitmapped set. */
498 bitmap_insert_into_set (bitmap_set_t set, tree expr)
501 /* XXX: For now, we only let SSA_NAMES into the bitmap sets. */
502 gcc_assert (TREE_CODE (expr) == SSA_NAME);
503 val = get_value_handle (expr);
506 if (!is_gimple_min_invariant (val))
508 bitmap_set_bit (set->values, VALUE_HANDLE_ID (val));
509 bitmap_set_bit (set->expressions, SSA_NAME_VERSION (expr));
513 /* Insert EXPR into SET. */
516 insert_into_set (value_set_t set, tree expr)
518 value_set_node_t newnode = pool_alloc (value_set_node_pool);
519 tree val = get_value_handle (expr);
522 if (is_gimple_min_invariant (val))
525 /* For indexed sets, insert the value into the set value bitmap.
526 For all sets, add it to the linked list and increment the list
529 value_insert_into_set_bitmap (set, val);
531 newnode->next = NULL;
532 newnode->expr = expr;
534 if (set->head == NULL)
536 set->head = set->tail = newnode;
540 set->tail->next = newnode;
545 /* Copy a bitmapped set ORIG, into bitmapped set DEST. */
548 bitmap_set_copy (bitmap_set_t dest, bitmap_set_t orig)
550 bitmap_copy (dest->expressions, orig->expressions);
551 bitmap_copy (dest->values, orig->values);
554 /* Copy the set ORIG to the set DEST. */
557 set_copy (value_set_t dest, value_set_t orig)
559 value_set_node_t node;
561 if (!orig || !orig->head)
564 for (node = orig->head;
568 insert_into_set (dest, node->expr);
572 /* Remove EXPR from SET. */
575 set_remove (value_set_t set, tree expr)
577 value_set_node_t node, prev;
579 /* Remove the value of EXPR from the bitmap, decrement the set
580 length, and remove it from the actual double linked list. */
581 value_remove_from_set_bitmap (set, get_value_handle (expr));
584 for (node = set->head;
586 prev = node, node = node->next)
588 if (node->expr == expr)
591 set->head = node->next;
593 prev->next= node->next;
595 if (node == set->tail)
597 pool_free (value_set_node_pool, node);
603 /* Return true if SET contains the value VAL. */
606 set_contains_value (value_set_t set, tree val)
608 /* All constants are in every set. */
609 if (is_gimple_min_invariant (val))
612 if (set->length == 0)
615 return value_exists_in_set_bitmap (set, val);
618 /* Return true if bitmapped set SET contains the expression EXPR. */
620 bitmap_set_contains (bitmap_set_t set, tree expr)
622 /* All constants are in every set. */
623 if (is_gimple_min_invariant (get_value_handle (expr)))
626 /* XXX: Bitmapped sets only contain SSA_NAME's for now. */
627 if (TREE_CODE (expr) != SSA_NAME)
629 return bitmap_bit_p (set->expressions, SSA_NAME_VERSION (expr));
633 /* Return true if bitmapped set SET contains the value VAL. */
636 bitmap_set_contains_value (bitmap_set_t set, tree val)
638 if (is_gimple_min_invariant (val))
640 return bitmap_bit_p (set->values, VALUE_HANDLE_ID (val));
643 /* Replace an instance of value LOOKFOR with expression EXPR in SET. */
646 bitmap_set_replace_value (bitmap_set_t set, tree lookfor, tree expr)
649 value_set_node_t node;
650 if (is_gimple_min_invariant (lookfor))
652 if (!bitmap_set_contains_value (set, lookfor))
655 /* The number of expressions having a given value is usually
656 significantly less than the total number of expressions in SET.
657 Thus, rather than check, for each expression in SET, whether it
658 has the value LOOKFOR, we walk the reverse mapping that tells us
659 what expressions have a given value, and see if any of those
660 expressions are in our set. For large testcases, this is about
661 5-10x faster than walking the bitmap. If this is somehow a
662 significant lose for some cases, we can choose which set to walk
663 based on the set size. */
664 exprset = VALUE_HANDLE_EXPR_SET (lookfor);
665 for (node = exprset->head; node; node = node->next)
667 if (TREE_CODE (node->expr) == SSA_NAME)
669 if (bitmap_bit_p (set->expressions, SSA_NAME_VERSION (node->expr)))
671 bitmap_clear_bit (set->expressions, SSA_NAME_VERSION (node->expr));
672 bitmap_set_bit (set->expressions, SSA_NAME_VERSION (expr));
679 /* Subtract bitmapped set B from value set A, and return the new set. */
682 bitmap_set_subtract_from_value_set (value_set_t a, bitmap_set_t b,
685 value_set_t ret = set_new (indexed);
686 value_set_node_t node;
691 if (!bitmap_set_contains (b, node->expr))
692 insert_into_set (ret, node->expr);
697 /* Return true if two sets are equal. */
700 set_equal (value_set_t a, value_set_t b)
702 value_set_node_t node;
704 if (a->length != b->length)
710 if (!set_contains_value (b, get_value_handle (node->expr)))
716 /* Replace an instance of EXPR's VALUE with EXPR in SET if it exists,
717 and add it otherwise. */
720 bitmap_value_replace_in_set (bitmap_set_t set, tree expr)
722 tree val = get_value_handle (expr);
723 if (bitmap_set_contains_value (set, val))
724 bitmap_set_replace_value (set, val, expr);
726 bitmap_insert_into_set (set, expr);
729 /* Insert EXPR into SET if EXPR's value is not already present in
733 bitmap_value_insert_into_set (bitmap_set_t set, tree expr)
735 tree val = get_value_handle (expr);
737 if (is_gimple_min_invariant (val))
740 if (!bitmap_set_contains_value (set, val))
741 bitmap_insert_into_set (set, expr);
744 /* Insert the value for EXPR into SET, if it doesn't exist already. */
747 value_insert_into_set (value_set_t set, tree expr)
749 tree val = get_value_handle (expr);
751 /* Constant and invariant values exist everywhere, and thus,
752 actually keeping them in the sets is pointless. */
753 if (is_gimple_min_invariant (val))
756 if (!set_contains_value (set, val))
757 insert_into_set (set, expr);
761 /* Print out SET to OUTFILE. */
764 bitmap_print_value_set (FILE *outfile, bitmap_set_t set,
765 const char *setname, int blockindex)
767 fprintf (outfile, "%s[%d] := { ", setname, blockindex);
774 EXECUTE_IF_SET_IN_BITMAP (set->expressions, 0, i, bi)
777 fprintf (outfile, ", ");
779 print_generic_expr (outfile, ssa_name (i), 0);
781 fprintf (outfile, " (");
782 print_generic_expr (outfile, get_value_handle (ssa_name (i)), 0);
783 fprintf (outfile, ") ");
786 fprintf (outfile, " }\n");
788 /* Print out the value_set SET to OUTFILE. */
791 print_value_set (FILE *outfile, value_set_t set,
792 const char *setname, int blockindex)
794 value_set_node_t node;
795 fprintf (outfile, "%s[%d] := { ", setname, blockindex);
798 for (node = set->head;
802 print_generic_expr (outfile, node->expr, 0);
804 fprintf (outfile, " (");
805 print_generic_expr (outfile, get_value_handle (node->expr), 0);
806 fprintf (outfile, ") ");
809 fprintf (outfile, ", ");
813 fprintf (outfile, " }\n");
816 /* Print out the expressions that have VAL to OUTFILE. */
819 print_value_expressions (FILE *outfile, tree val)
821 if (VALUE_HANDLE_EXPR_SET (val))
824 sprintf (s, "VH.%04d", VALUE_HANDLE_ID (val));
825 print_value_set (outfile, VALUE_HANDLE_EXPR_SET (val), s, 0);
831 debug_value_expressions (tree val)
833 print_value_expressions (stderr, val);
837 void debug_value_set (value_set_t, const char *, int);
840 debug_value_set (value_set_t set, const char *setname, int blockindex)
842 print_value_set (stderr, set, setname, blockindex);
845 /* Translate EXPR using phis in PHIBLOCK, so that it has the values of
846 the phis in PRED. Return NULL if we can't find a leader for each
847 part of the translated expression. */
850 phi_translate (tree expr, value_set_t set, basic_block pred,
851 basic_block phiblock)
853 tree phitrans = NULL;
859 if (is_gimple_min_invariant (expr))
862 /* Phi translations of a given expression don't change. */
863 phitrans = phi_trans_lookup (expr, pred);
867 switch (TREE_CODE_CLASS (TREE_CODE (expr)))
870 /* XXX: Until we have PRE of loads working, none will be ANTIC. */
876 tree oldop1 = TREE_OPERAND (expr, 0);
877 tree oldop2 = TREE_OPERAND (expr, 1);
882 newop1 = phi_translate (find_leader (set, oldop1),
883 set, pred, phiblock);
886 newop2 = phi_translate (find_leader (set, oldop2),
887 set, pred, phiblock);
890 if (newop1 != oldop1 || newop2 != oldop2)
892 newexpr = pool_alloc (binary_node_pool);
893 memcpy (newexpr, expr, tree_size (expr));
894 create_tree_ann (newexpr);
895 TREE_OPERAND (newexpr, 0) = newop1 == oldop1 ? oldop1 : get_value_handle (newop1);
896 TREE_OPERAND (newexpr, 1) = newop2 == oldop2 ? oldop2 : get_value_handle (newop2);
897 vn_lookup_or_add (newexpr, NULL);
899 phi_trans_add (oldexpr, newexpr, pred);
906 tree oldop1 = TREE_OPERAND (expr, 0);
910 newop1 = phi_translate (find_leader (set, oldop1),
911 set, pred, phiblock);
914 if (newop1 != oldop1)
916 newexpr = pool_alloc (unary_node_pool);
917 memcpy (newexpr, expr, tree_size (expr));
918 create_tree_ann (newexpr);
919 TREE_OPERAND (newexpr, 0) = get_value_handle (newop1);
920 vn_lookup_or_add (newexpr, NULL);
922 phi_trans_add (oldexpr, newexpr, pred);
927 case tcc_exceptional:
931 gcc_assert (TREE_CODE (expr) == SSA_NAME);
932 if (TREE_CODE (SSA_NAME_DEF_STMT (expr)) == PHI_NODE)
933 phi = SSA_NAME_DEF_STMT (expr);
937 e = find_edge (pred, bb_for_stmt (phi));
940 if (is_undefined_value (PHI_ARG_DEF (phi, e->dest_idx)))
942 vn_lookup_or_add (PHI_ARG_DEF (phi, e->dest_idx), NULL);
943 return PHI_ARG_DEF (phi, e->dest_idx);
954 phi_translate_set (value_set_t dest, value_set_t set, basic_block pred,
955 basic_block phiblock)
957 value_set_node_t node;
958 for (node = set->head;
963 translated = phi_translate (node->expr, set, pred, phiblock);
964 phi_trans_add (node->expr, translated, pred);
966 if (translated != NULL)
967 value_insert_into_set (dest, translated);
971 /* Find the leader for a value (i.e., the name representing that
972 value) in a given set, and return it. Return NULL if no leader is
976 bitmap_find_leader (bitmap_set_t set, tree val)
981 if (is_gimple_min_invariant (val))
983 if (bitmap_set_contains_value (set, val))
985 /* Rather than walk the entire bitmap of expressions, and see
986 whether any of them has the value we are looking for, we look
987 at the reverse mapping, which tells us the set of expressions
988 that have a given value (IE value->expressions with that
989 value) and see if any of those expressions are in our set.
990 The number of expressions per value is usually significantly
991 less than the number of expressions in the set. In fact, for
992 large testcases, doing it this way is roughly 5-10x faster
993 than walking the bitmap.
994 If this is somehow a significant lose for some cases, we can
995 choose which set to walk based on which set is smaller. */
997 value_set_node_t node;
998 exprset = VALUE_HANDLE_EXPR_SET (val);
999 for (node = exprset->head; node; node = node->next)
1001 if (TREE_CODE (node->expr) == SSA_NAME)
1003 if (bitmap_bit_p (set->expressions,
1004 SSA_NAME_VERSION (node->expr)))
1013 /* Find the leader for a value (i.e., the name representing that
1014 value) in a given set, and return it. Return NULL if no leader is
1018 find_leader (value_set_t set, tree val)
1020 value_set_node_t node;
1025 /* Constants represent themselves. */
1026 if (is_gimple_min_invariant (val))
1029 if (set->length == 0)
1032 if (value_exists_in_set_bitmap (set, val))
1034 for (node = set->head;
1038 if (get_value_handle (node->expr) == val)
1046 /* Determine if the expression EXPR is valid in SET. This means that
1047 we have a leader for each part of the expression (if it consists of
1048 values), or the expression is an SSA_NAME.
1050 NB: We never should run into a case where we have SSA_NAME +
1051 SSA_NAME or SSA_NAME + value. The sets valid_in_set is called on,
1052 the ANTIC sets, will only ever have SSA_NAME's or binary value
1053 expression (IE VALUE1 + VALUE2) */
1056 valid_in_set (value_set_t set, tree expr)
1058 switch (TREE_CODE_CLASS (TREE_CODE (expr)))
1061 case tcc_comparison:
1063 tree op1 = TREE_OPERAND (expr, 0);
1064 tree op2 = TREE_OPERAND (expr, 1);
1065 return set_contains_value (set, op1) && set_contains_value (set, op2);
1070 tree op1 = TREE_OPERAND (expr, 0);
1071 return set_contains_value (set, op1);
1075 /* XXX: Until PRE of loads works, no reference nodes are ANTIC. */
1078 case tcc_exceptional:
1079 gcc_assert (TREE_CODE (expr) == SSA_NAME);
1082 case tcc_declaration:
1083 /* VAR_DECL and PARM_DECL are never anticipatable. */
1087 /* No other cases should be encountered. */
1092 /* Clean the set of expressions that are no longer valid in SET. This
1093 means expressions that are made up of values we have no leaders for
1097 clean (value_set_t set)
1099 value_set_node_t node;
1100 value_set_node_t next;
1105 if (!valid_in_set (set, node->expr))
1106 set_remove (set, node->expr);
1111 DEF_VEC_MALLOC_P (basic_block);
1112 static sbitmap has_abnormal_preds;
1114 /* Compute the ANTIC set for BLOCK.
1116 If succs(BLOCK) > 1 then
1117 ANTIC_OUT[BLOCK] = intersection of ANTIC_IN[b] for all succ(BLOCK)
1118 else if succs(BLOCK) == 1 then
1119 ANTIC_OUT[BLOCK] = phi_translate (ANTIC_IN[succ(BLOCK)])
1121 ANTIC_IN[BLOCK] = clean(ANTIC_OUT[BLOCK] U EXP_GEN[BLOCK] - TMP_GEN[BLOCK])
1123 XXX: It would be nice to either write a set_clear, and use it for
1124 ANTIC_OUT, or to mark the antic_out set as deleted at the end
1125 of this routine, so that the pool can hand the same memory back out
1126 again for the next ANTIC_OUT. */
1129 compute_antic_aux (basic_block block, bool block_has_abnormal_pred_edge)
1132 bool changed = false;
1133 value_set_t S, old, ANTIC_OUT;
1134 value_set_node_t node;
1136 ANTIC_OUT = S = NULL;
1138 /* If any edges from predecessors are abnormal, antic_in is empty,
1140 if (block_has_abnormal_pred_edge)
1141 goto maybe_dump_sets;
1143 old = set_new (false);
1144 set_copy (old, ANTIC_IN (block));
1145 ANTIC_OUT = set_new (true);
1147 /* If the block has no successors, ANTIC_OUT is empty. */
1148 if (EDGE_COUNT (block->succs) == 0)
1150 /* If we have one successor, we could have some phi nodes to
1151 translate through. */
1152 else if (single_succ_p (block))
1154 phi_translate_set (ANTIC_OUT, ANTIC_IN(single_succ (block)),
1155 block, single_succ (block));
1157 /* If we have multiple successors, we take the intersection of all of
1161 VEC (basic_block) * worklist;
1164 basic_block bprime, first;
1167 worklist = VEC_alloc (basic_block, 2);
1168 FOR_EACH_EDGE (e, ei, block->succs)
1169 VEC_safe_push (basic_block, worklist, e->dest);
1170 first = VEC_index (basic_block, worklist, 0);
1171 set_copy (ANTIC_OUT, ANTIC_IN (first));
1173 for (i = 1; VEC_iterate (basic_block, worklist, i, bprime); i++)
1175 node = ANTIC_OUT->head;
1179 value_set_node_t next = node->next;
1180 val = get_value_handle (node->expr);
1181 if (!set_contains_value (ANTIC_IN (bprime), val))
1182 set_remove (ANTIC_OUT, node->expr);
1186 VEC_free (basic_block, worklist);
1189 /* Generate ANTIC_OUT - TMP_GEN. */
1190 S = bitmap_set_subtract_from_value_set (ANTIC_OUT, TMP_GEN (block), false);
1192 /* Start ANTIC_IN with EXP_GEN - TMP_GEN */
1193 ANTIC_IN (block) = bitmap_set_subtract_from_value_set (EXP_GEN (block),
1197 /* Then union in the ANTIC_OUT - TMP_GEN values,
1198 to get ANTIC_OUT U EXP_GEN - TMP_GEN */
1199 for (node = S->head; node; node = node->next)
1200 value_insert_into_set (ANTIC_IN (block), node->expr);
1202 clean (ANTIC_IN (block));
1203 if (!set_equal (old, ANTIC_IN (block)))
1207 if (dump_file && (dump_flags & TDF_DETAILS))
1210 print_value_set (dump_file, ANTIC_OUT, "ANTIC_OUT", block->index);
1211 print_value_set (dump_file, ANTIC_IN (block), "ANTIC_IN", block->index);
1213 print_value_set (dump_file, S, "S", block->index);
1216 for (son = first_dom_son (CDI_POST_DOMINATORS, block);
1218 son = next_dom_son (CDI_POST_DOMINATORS, son))
1220 changed |= compute_antic_aux (son,
1221 TEST_BIT (has_abnormal_preds, son->index));
1226 /* Compute ANTIC sets. */
1229 compute_antic (void)
1231 bool changed = true;
1232 int num_iterations = 0;
1235 /* If any predecessor edges are abnormal, we punt, so antic_in is empty.
1236 We pre-build the map of blocks with incoming abnormal edges here. */
1237 has_abnormal_preds = sbitmap_alloc (last_basic_block);
1238 sbitmap_zero (has_abnormal_preds);
1244 FOR_EACH_EDGE (e, ei, block->preds)
1245 if (e->flags & EDGE_ABNORMAL)
1247 SET_BIT (has_abnormal_preds, block->index);
1251 /* While we are here, give empty ANTIC_IN sets to each block. */
1252 ANTIC_IN (block) = set_new (true);
1254 /* At the exit block we anticipate nothing. */
1255 ANTIC_IN (EXIT_BLOCK_PTR) = set_new (true);
1261 changed = compute_antic_aux (EXIT_BLOCK_PTR, false);
1264 sbitmap_free (has_abnormal_preds);
1266 if (dump_file && (dump_flags & TDF_STATS))
1267 fprintf (dump_file, "compute_antic required %d iterations\n", num_iterations);
1270 static VEC(tree_on_heap) *inserted_exprs;
1271 /* Find a leader for an expression, or generate one using
1272 create_expression_by_pieces if it's ANTIC but
1274 BLOCK is the basic_block we are looking for leaders in.
1275 EXPR is the expression to find a leader or generate for.
1276 STMTS is the statement list to put the inserted expressions on.
1277 Returns the SSA_NAME of the LHS of the generated expression or the
1281 find_or_generate_expression (basic_block block, tree expr, tree stmts)
1283 tree genop = bitmap_find_leader (AVAIL_OUT (block), expr);
1285 /* If it's still NULL, see if it is a complex expression, and if
1286 so, generate it recursively, otherwise, abort, because it's
1290 genop = VALUE_HANDLE_EXPR_SET (expr)->head->expr;
1291 gcc_assert (UNARY_CLASS_P (genop)
1292 || BINARY_CLASS_P (genop)
1293 || COMPARISON_CLASS_P (genop)
1294 || REFERENCE_CLASS_P (genop));
1295 genop = create_expression_by_pieces (block, genop, stmts);
1300 #define NECESSARY(stmt) stmt->common.asm_written_flag
1301 /* Create an expression in pieces, so that we can handle very complex
1302 expressions that may be ANTIC, but not necessary GIMPLE.
1303 BLOCK is the basic block the expression will be inserted into,
1304 EXPR is the expression to insert (in value form)
1305 STMTS is a statement list to append the necessary insertions into.
1307 This function will abort if we hit some value that shouldn't be
1308 ANTIC but is (IE there is no leader for it, or its components).
1309 This function may also generate expressions that are themselves
1310 partially or fully redundant. Those that are will be either made
1311 fully redundant during the next iteration of insert (for partially
1312 redundant ones), or eliminated by eliminate (for fully redundant
1316 create_expression_by_pieces (basic_block block, tree expr, tree stmts)
1318 tree name = NULL_TREE;
1319 tree newexpr = NULL_TREE;
1322 switch (TREE_CODE_CLASS (TREE_CODE (expr)))
1325 case tcc_comparison:
1327 tree_stmt_iterator tsi;
1329 tree genop1, genop2;
1332 tree op1 = TREE_OPERAND (expr, 0);
1333 tree op2 = TREE_OPERAND (expr, 1);
1334 genop1 = find_or_generate_expression (block, op1, stmts);
1335 genop2 = find_or_generate_expression (block, op2, stmts);
1336 temp = create_tmp_var (TREE_TYPE (expr), "pretmp");
1337 add_referenced_tmp_var (temp);
1339 folded = fold (build (TREE_CODE (expr), TREE_TYPE (expr),
1341 newexpr = force_gimple_operand (folded, &forced_stmts, false, NULL);
1344 tsi = tsi_start (forced_stmts);
1345 for (; !tsi_end_p (tsi); tsi_next (&tsi))
1347 tree stmt = tsi_stmt (tsi);
1348 tree forcedname = TREE_OPERAND (stmt, 0);
1349 tree forcedexpr = TREE_OPERAND (stmt, 1);
1350 tree val = vn_lookup_or_add (forcedexpr, NULL);
1351 vn_add (forcedname, val, NULL);
1352 bitmap_value_replace_in_set (NEW_SETS (block), forcedname);
1353 bitmap_value_replace_in_set (AVAIL_OUT (block), forcedname);
1356 tsi = tsi_last (stmts);
1357 tsi_link_after (&tsi, forced_stmts, TSI_CONTINUE_LINKING);
1359 newexpr = build (MODIFY_EXPR, TREE_TYPE (expr),
1361 NECESSARY (newexpr) = 0;
1362 name = make_ssa_name (temp, newexpr);
1363 TREE_OPERAND (newexpr, 0) = name;
1364 tsi = tsi_last (stmts);
1365 tsi_link_after (&tsi, newexpr, TSI_CONTINUE_LINKING);
1366 VEC_safe_push (tree_on_heap, inserted_exprs, newexpr);
1367 pre_stats.insertions++;
1372 tree_stmt_iterator tsi;
1377 tree op1 = TREE_OPERAND (expr, 0);
1378 genop1 = find_or_generate_expression (block, op1, stmts);
1379 temp = create_tmp_var (TREE_TYPE (expr), "pretmp");
1380 add_referenced_tmp_var (temp);
1381 folded = fold (build (TREE_CODE (expr), TREE_TYPE (expr),
1383 newexpr = force_gimple_operand (folded, &forced_stmts, false, NULL);
1386 tsi = tsi_start (forced_stmts);
1387 for (; !tsi_end_p (tsi); tsi_next (&tsi))
1389 tree stmt = tsi_stmt (tsi);
1390 tree forcedname = TREE_OPERAND (stmt, 0);
1391 tree forcedexpr = TREE_OPERAND (stmt, 1);
1392 tree val = vn_lookup_or_add (forcedexpr, NULL);
1393 vn_add (forcedname, val, NULL);
1394 bitmap_value_replace_in_set (NEW_SETS (block), forcedname);
1395 bitmap_value_replace_in_set (AVAIL_OUT (block), forcedname);
1397 tsi = tsi_last (stmts);
1398 tsi_link_after (&tsi, forced_stmts, TSI_CONTINUE_LINKING);
1400 newexpr = build (MODIFY_EXPR, TREE_TYPE (expr),
1402 name = make_ssa_name (temp, newexpr);
1403 TREE_OPERAND (newexpr, 0) = name;
1404 NECESSARY (newexpr) = 0;
1405 tsi = tsi_last (stmts);
1406 tsi_link_after (&tsi, newexpr, TSI_CONTINUE_LINKING);
1407 VEC_safe_push (tree_on_heap, inserted_exprs, newexpr);
1408 pre_stats.insertions++;
1416 v = get_value_handle (expr);
1417 vn_add (name, v, NULL);
1419 /* The value may already exist in either NEW_SETS, or AVAIL_OUT, because
1420 we are creating the expression by pieces, and this particular piece of
1421 the expression may have been represented. There is no harm in replacing
1423 bitmap_value_replace_in_set (NEW_SETS (block), name);
1424 bitmap_value_replace_in_set (AVAIL_OUT (block), name);
1425 if (dump_file && (dump_flags & TDF_DETAILS))
1427 fprintf (dump_file, "Inserted ");
1428 print_generic_expr (dump_file, newexpr, 0);
1429 fprintf (dump_file, " in predecessor %d\n", block->index);
1434 /* Return the folded version of T if T, when folded, is a gimple
1435 min_invariant. Otherwise, return T. */
1438 fully_constant_expression (tree t)
1442 if (folded && is_gimple_min_invariant (folded))
1447 /* Insert the to-be-made-available values of NODE for each predecessor, stored
1448 in AVAIL, into the predecessors of BLOCK, and merge the result with a phi
1449 node, given the same value handle as NODE. The prefix of the phi node is
1450 given with TMPNAME. Return true if we have inserted new stuff. */
1453 insert_into_preds_of_block (basic_block block, value_set_node_t node,
1454 tree *avail, const char *tmpname)
1456 tree val = get_value_handle (node->expr);
1458 bool insertions = false;
1463 tree type = TREE_TYPE (avail[EDGE_PRED (block, 0)->src->index]);
1466 if (dump_file && (dump_flags & TDF_DETAILS))
1468 fprintf (dump_file, "Found partial redundancy for expression ");
1469 print_generic_expr (dump_file, node->expr, 0);
1470 fprintf (dump_file, "\n");
1473 /* Make sure we aren't creating an induction variable. */
1474 if (block->loop_depth > 0 && EDGE_COUNT (block->preds) == 2)
1476 bool firstinsideloop = false;
1477 bool secondinsideloop = false;
1478 firstinsideloop = flow_bb_inside_loop_p (block->loop_father,
1479 EDGE_PRED (block, 0)->src);
1480 secondinsideloop = flow_bb_inside_loop_p (block->loop_father,
1481 EDGE_PRED (block, 1)->src);
1482 /* Induction variables only have one edge inside the loop. */
1483 if (firstinsideloop ^ secondinsideloop)
1485 if (dump_file && (dump_flags & TDF_DETAILS))
1486 fprintf (dump_file, "Skipping insertion of phi for partial redundancy: Looks like an induction variable\n");
1492 /* Make the necessary insertions. */
1493 FOR_EACH_EDGE (pred, ei, block->preds)
1495 tree stmts = alloc_stmt_list ();
1498 eprime = avail[bprime->index];
1499 if (BINARY_CLASS_P (eprime)
1500 || COMPARISON_CLASS_P (eprime)
1501 || UNARY_CLASS_P (eprime))
1503 builtexpr = create_expression_by_pieces (bprime,
1506 bsi_insert_on_edge (pred, stmts);
1507 avail[bprime->index] = builtexpr;
1511 /* If we didn't want a phi node, and we made insertions, we still have
1512 inserted new stuff, and thus return true. If we didn't want a phi node,
1513 and didn't make insertions, we haven't added anything new, so return
1515 if (nophi && insertions)
1517 else if (nophi && !insertions)
1520 /* Now build a phi for the new variable. */
1521 temp = create_tmp_var (type, tmpname);
1522 add_referenced_tmp_var (temp);
1523 temp = create_phi_node (temp, block);
1524 NECESSARY (temp) = 0;
1525 VEC_safe_push (tree_on_heap, inserted_exprs, temp);
1526 FOR_EACH_EDGE (pred, ei, block->preds)
1527 add_phi_arg (temp, avail[pred->src->index], pred);
1529 vn_add (PHI_RESULT (temp), val, NULL);
1531 /* The value should *not* exist in PHI_GEN, or else we wouldn't be doing
1532 this insertion, since we test for the existence of this value in PHI_GEN
1533 before proceeding with the partial redundancy checks in insert_aux.
1535 The value may exist in AVAIL_OUT, in particular, it could be represented
1536 by the expression we are trying to eliminate, in which case we want the
1537 replacement to occur. If it's not existing in AVAIL_OUT, we want it
1540 Similarly, to the PHI_GEN case, the value should not exist in NEW_SETS of
1541 this block, because if it did, it would have existed in our dominator's
1542 AVAIL_OUT, and would have been skipped due to the full redundancy check.
1545 bitmap_insert_into_set (PHI_GEN (block),
1547 bitmap_value_replace_in_set (AVAIL_OUT (block),
1549 bitmap_insert_into_set (NEW_SETS (block),
1552 if (dump_file && (dump_flags & TDF_DETAILS))
1554 fprintf (dump_file, "Created phi ");
1555 print_generic_expr (dump_file, temp, 0);
1556 fprintf (dump_file, " in block %d\n", block->index);
1564 /* Perform insertion of partially redundant values.
1565 For BLOCK, do the following:
1566 1. Propagate the NEW_SETS of the dominator into the current block.
1567 If the block has multiple predecessors,
1568 2a. Iterate over the ANTIC expressions for the block to see if
1569 any of them are partially redundant.
1570 2b. If so, insert them into the necessary predecessors to make
1571 the expression fully redundant.
1572 2c. Insert a new PHI merging the values of the predecessors.
1573 2d. Insert the new PHI, and the new expressions, into the
1575 3. Recursively call ourselves on the dominator children of BLOCK.
1580 insert_aux (basic_block block)
1583 bool new_stuff = false;
1588 dom = get_immediate_dominator (CDI_DOMINATORS, block);
1593 bitmap_set_t newset = NEW_SETS (dom);
1596 /* Note that we need to value_replace both NEW_SETS, and
1597 AVAIL_OUT. For both the case of NEW_SETS, the value may be
1598 represented by some non-simple expression here that we want
1599 to replace it with. */
1600 EXECUTE_IF_SET_IN_BITMAP (newset->expressions, 0, i, bi)
1602 bitmap_value_replace_in_set (NEW_SETS (block), ssa_name (i));
1603 bitmap_value_replace_in_set (AVAIL_OUT (block), ssa_name (i));
1606 if (!single_pred_p (block))
1608 value_set_node_t node;
1609 for (node = ANTIC_IN (block)->head;
1613 if (BINARY_CLASS_P (node->expr)
1614 || COMPARISON_CLASS_P (node->expr)
1615 || UNARY_CLASS_P (node->expr))
1619 bool by_some = false;
1620 bool cant_insert = false;
1621 bool all_same = true;
1622 tree first_s = NULL;
1625 tree eprime = NULL_TREE;
1628 val = get_value_handle (node->expr);
1629 if (bitmap_set_contains_value (PHI_GEN (block), val))
1631 if (bitmap_set_contains_value (AVAIL_OUT (dom), val))
1633 if (dump_file && (dump_flags & TDF_DETAILS))
1634 fprintf (dump_file, "Found fully redundant value\n");
1638 avail = xcalloc (last_basic_block, sizeof (tree));
1639 FOR_EACH_EDGE (pred, ei, block->preds)
1644 /* This can happen in the very weird case
1645 that our fake infinite loop edges have caused a
1646 critical edge to appear. */
1647 if (EDGE_CRITICAL_P (pred))
1653 eprime = phi_translate (node->expr,
1657 /* eprime will generally only be NULL if the
1658 value of the expression, translated
1659 through the PHI for this predecessor, is
1660 undefined. If that is the case, we can't
1661 make the expression fully redundant,
1662 because its value is undefined along a
1663 predecessor path. We can thus break out
1664 early because it doesn't matter what the
1665 rest of the results are. */
1672 eprime = fully_constant_expression (eprime);
1673 vprime = get_value_handle (eprime);
1674 gcc_assert (vprime);
1675 edoubleprime = bitmap_find_leader (AVAIL_OUT (bprime),
1677 if (edoubleprime == NULL)
1679 avail[bprime->index] = eprime;
1684 avail[bprime->index] = edoubleprime;
1686 if (first_s == NULL)
1687 first_s = edoubleprime;
1688 else if (!operand_equal_p (first_s, edoubleprime,
1693 /* If we can insert it, it's not the same value
1694 already existing along every predecessor, and
1695 it's defined by some predecessor, it is
1696 partially redundant. */
1697 if (!cant_insert && !all_same && by_some)
1699 if (insert_into_preds_of_block (block, node, avail,
1703 /* If all edges produce the same value and that value is
1704 an invariant, then the PHI has the same value on all
1705 edges. Note this. */
1706 else if (!cant_insert && all_same && eprime
1707 && is_gimple_min_invariant (eprime)
1708 && !is_gimple_min_invariant (val))
1710 value_set_t exprset = VALUE_HANDLE_EXPR_SET (val);
1711 value_set_node_t node;
1712 for (node = exprset->head; node; node = node->next)
1714 if (TREE_CODE (node->expr) == SSA_NAME)
1716 vn_add (node->expr, eprime, NULL);
1717 pre_stats.constified++;
1727 for (son = first_dom_son (CDI_DOMINATORS, block);
1729 son = next_dom_son (CDI_DOMINATORS, son))
1731 new_stuff |= insert_aux (son);
1737 /* Perform insertion of partially redundant values. */
1742 bool new_stuff = true;
1744 int num_iterations = 0;
1747 NEW_SETS (bb) = bitmap_set_new ();
1753 new_stuff = insert_aux (ENTRY_BLOCK_PTR);
1755 if (num_iterations > 2 && dump_file && (dump_flags & TDF_STATS))
1756 fprintf (dump_file, "insert required %d iterations\n", num_iterations);
1760 /* Return true if VAR is an SSA variable with no defining statement in
1761 this procedure, *AND* isn't a live-on-entry parameter. */
1764 is_undefined_value (tree expr)
1766 return (TREE_CODE (expr) == SSA_NAME
1767 && IS_EMPTY_STMT (SSA_NAME_DEF_STMT (expr))
1768 /* PARM_DECLs and hard registers are always defined. */
1769 && TREE_CODE (SSA_NAME_VAR (expr)) != PARM_DECL);
1773 /* Given an SSA variable VAR and an expression EXPR, compute the value
1774 number for EXPR and create a value handle (VAL) for it. If VAR and
1775 EXPR are not the same, associate VAL with VAR. Finally, add VAR to
1776 S1 and its value handle to S2.
1778 VUSES represent the virtual use operands associated with EXPR (if
1779 any). They are used when computing the hash value for EXPR. */
1782 add_to_sets (tree var, tree expr, vuse_optype vuses, bitmap_set_t s1,
1785 tree val = vn_lookup_or_add (expr, vuses);
1787 /* VAR and EXPR may be the same when processing statements for which
1788 we are not computing value numbers (e.g., non-assignments, or
1789 statements that make aliased stores). In those cases, we are
1790 only interested in making VAR available as its own value. */
1792 vn_add (var, val, NULL);
1795 bitmap_insert_into_set (s1, var);
1796 bitmap_value_insert_into_set (s2, var);
1800 /* Given a unary or binary expression EXPR, create and return a new
1801 expression with the same structure as EXPR but with its operands
1802 replaced with the value handles of each of the operands of EXPR.
1804 VUSES represent the virtual use operands associated with EXPR (if
1805 any). They are used when computing the hash value for EXPR.
1806 Insert EXPR's operands into the EXP_GEN set for BLOCK. */
1809 create_value_expr_from (tree expr, basic_block block,
1814 enum tree_code code = TREE_CODE (expr);
1818 gcc_assert (TREE_CODE_CLASS (code) == tcc_unary
1819 || TREE_CODE_CLASS (code) == tcc_binary
1820 || TREE_CODE_CLASS (code) == tcc_comparison
1821 || TREE_CODE_CLASS (code) == tcc_reference);
1823 if (TREE_CODE_CLASS (code) == tcc_unary)
1824 pool = unary_node_pool;
1825 else if (TREE_CODE_CLASS (code) == tcc_reference)
1826 pool = reference_node_pool;
1828 pool = binary_node_pool;
1830 vexpr = pool_alloc (pool);
1831 memcpy (vexpr, expr, tree_size (expr));
1833 for (i = 0; i < TREE_CODE_LENGTH (code); i++)
1837 op = TREE_OPERAND (expr, i);
1838 if (op == NULL_TREE)
1841 /* If OP is a constant that has overflowed, do not value number
1843 if (TREE_CODE_CLASS (TREE_CODE (op)) == tcc_constant
1844 && TREE_OVERFLOW (op))
1846 pool_free (pool, vexpr);
1850 /* Recursively value-numberize reference ops */
1851 if (TREE_CODE_CLASS (TREE_CODE (op)) == tcc_reference)
1853 tree tempop = create_value_expr_from (op, block, vuses);
1854 op = tempop ? tempop : op;
1855 val = vn_lookup_or_add (op, vuses);
1858 /* Create a value handle for OP and add it to VEXPR. */
1859 val = vn_lookup_or_add (op, NULL);
1861 if (!is_undefined_value (op))
1862 value_insert_into_set (EXP_GEN (block), op);
1864 if (TREE_CODE (val) == VALUE_HANDLE)
1865 TREE_TYPE (val) = TREE_TYPE (TREE_OPERAND (vexpr, i));
1867 TREE_OPERAND (vexpr, i) = val;
1874 /* Compute the AVAIL set for all basic blocks.
1876 This function performs value numbering of the statements in each basic
1877 block. The AVAIL sets are built from information we glean while doing
1878 this value numbering, since the AVAIL sets contain only one entry per
1881 AVAIL_IN[BLOCK] = AVAIL_OUT[dom(BLOCK)].
1882 AVAIL_OUT[BLOCK] = AVAIL_IN[BLOCK] U PHI_GEN[BLOCK] U TMP_GEN[BLOCK]. */
1885 compute_avail (void)
1887 basic_block block, son;
1888 basic_block *worklist;
1892 /* For arguments with default definitions, we pretend they are
1893 defined in the entry block. */
1894 for (param = DECL_ARGUMENTS (current_function_decl);
1896 param = TREE_CHAIN (param))
1898 if (default_def (param) != NULL)
1900 tree def = default_def (param);
1901 vn_lookup_or_add (def, NULL);
1902 bitmap_insert_into_set (TMP_GEN (ENTRY_BLOCK_PTR), def);
1903 bitmap_value_insert_into_set (AVAIL_OUT (ENTRY_BLOCK_PTR), def);
1907 /* Allocate the worklist. */
1908 worklist = xmalloc (sizeof (basic_block) * n_basic_blocks);
1910 /* Seed the algorithm by putting the dominator children of the entry
1911 block on the worklist. */
1912 for (son = first_dom_son (CDI_DOMINATORS, ENTRY_BLOCK_PTR);
1914 son = next_dom_son (CDI_DOMINATORS, son))
1915 worklist[sp++] = son;
1917 /* Loop until the worklist is empty. */
1920 block_stmt_iterator bsi;
1924 /* Pick a block from the worklist. */
1925 block = worklist[--sp];
1927 /* Initially, the set of available values in BLOCK is that of
1928 its immediate dominator. */
1929 dom = get_immediate_dominator (CDI_DOMINATORS, block);
1931 bitmap_set_copy (AVAIL_OUT (block), AVAIL_OUT (dom));
1933 /* Generate values for PHI nodes. */
1934 for (phi = phi_nodes (block); phi; phi = PHI_CHAIN (phi))
1935 /* We have no need for virtual phis, as they don't represent
1936 actual computations. */
1937 if (is_gimple_reg (PHI_RESULT (phi)))
1938 add_to_sets (PHI_RESULT (phi), PHI_RESULT (phi), NULL,
1939 PHI_GEN (block), AVAIL_OUT (block));
1941 /* Now compute value numbers and populate value sets with all
1942 the expressions computed in BLOCK. */
1943 for (bsi = bsi_start (block); !bsi_end_p (bsi); bsi_next (&bsi))
1948 stmt = bsi_stmt (bsi);
1949 ann = stmt_ann (stmt);
1950 get_stmt_operands (stmt);
1952 /* We are only interested in assignments of the form
1953 X_i = EXPR, where EXPR represents an "interesting"
1954 computation, it has no volatile operands and X_i
1955 doesn't flow through an abnormal edge. */
1956 if (TREE_CODE (stmt) == MODIFY_EXPR
1957 && !ann->has_volatile_ops
1958 && TREE_CODE (TREE_OPERAND (stmt, 0)) == SSA_NAME
1959 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (TREE_OPERAND (stmt, 0)))
1961 tree lhs = TREE_OPERAND (stmt, 0);
1962 tree rhs = TREE_OPERAND (stmt, 1);
1963 vuse_optype vuses = STMT_VUSE_OPS (stmt);
1965 STRIP_USELESS_TYPE_CONVERSION (rhs);
1966 if (UNARY_CLASS_P (rhs)
1967 || BINARY_CLASS_P (rhs)
1968 || COMPARISON_CLASS_P (rhs)
1969 || REFERENCE_CLASS_P (rhs))
1971 /* For binary, unary, and reference expressions,
1972 create a duplicate expression with the operands
1973 replaced with the value handles of the original
1975 tree newt = create_value_expr_from (rhs, block, vuses);
1978 add_to_sets (lhs, newt, vuses, TMP_GEN (block),
1980 value_insert_into_set (EXP_GEN (block), newt);
1984 else if (TREE_CODE (rhs) == SSA_NAME
1985 || is_gimple_min_invariant (rhs)
1986 || TREE_CODE (rhs) == ADDR_EXPR
1989 /* Compute a value number for the RHS of the statement
1990 and add its value to the AVAIL_OUT set for the block.
1991 Add the LHS to TMP_GEN. */
1992 add_to_sets (lhs, rhs, vuses, TMP_GEN (block),
1995 if (TREE_CODE (rhs) == SSA_NAME
1996 && !is_undefined_value (rhs))
1997 value_insert_into_set (EXP_GEN (block), rhs);
2002 /* For any other statement that we don't recognize, simply
2003 make the names generated by the statement available in
2004 AVAIL_OUT and TMP_GEN. */
2005 for (j = 0; j < NUM_DEFS (STMT_DEF_OPS (stmt)); j++)
2007 tree def = DEF_OP (STMT_DEF_OPS (stmt), j);
2008 add_to_sets (def, def, NULL, TMP_GEN (block),
2012 for (j = 0; j < NUM_USES (STMT_USE_OPS (stmt)); j++)
2014 tree use = USE_OP (STMT_USE_OPS (stmt), j);
2015 add_to_sets (use, use, NULL, NULL, AVAIL_OUT (block));
2019 /* Put the dominator children of BLOCK on the worklist of blocks
2020 to compute available sets for. */
2021 for (son = first_dom_son (CDI_DOMINATORS, block);
2023 son = next_dom_son (CDI_DOMINATORS, son))
2024 worklist[sp++] = son;
2031 /* Eliminate fully redundant computations. */
2040 block_stmt_iterator i;
2042 for (i = bsi_start (b); !bsi_end_p (i); bsi_next (&i))
2044 tree stmt = bsi_stmt (i);
2046 /* Lookup the RHS of the expression, see if we have an
2047 available computation for it. If so, replace the RHS with
2048 the available computation. */
2049 if (TREE_CODE (stmt) == MODIFY_EXPR
2050 && TREE_CODE (TREE_OPERAND (stmt, 0)) == SSA_NAME
2051 && TREE_CODE (TREE_OPERAND (stmt ,1)) != SSA_NAME
2052 && !is_gimple_min_invariant (TREE_OPERAND (stmt, 1))
2053 && !stmt_ann (stmt)->has_volatile_ops)
2055 tree lhs = TREE_OPERAND (stmt, 0);
2056 tree *rhs_p = &TREE_OPERAND (stmt, 1);
2059 sprime = bitmap_find_leader (AVAIL_OUT (b),
2060 vn_lookup (lhs, NULL));
2063 && (TREE_CODE (*rhs_p) != SSA_NAME
2064 || may_propagate_copy (*rhs_p, sprime)))
2066 gcc_assert (sprime != *rhs_p);
2068 if (dump_file && (dump_flags & TDF_DETAILS))
2070 fprintf (dump_file, "Replaced ");
2071 print_generic_expr (dump_file, *rhs_p, 0);
2072 fprintf (dump_file, " with ");
2073 print_generic_expr (dump_file, sprime, 0);
2074 fprintf (dump_file, " in ");
2075 print_generic_stmt (dump_file, stmt, 0);
2077 if (TREE_CODE (sprime) == SSA_NAME)
2078 NECESSARY (SSA_NAME_DEF_STMT (sprime)) = 1;
2079 pre_stats.eliminations++;
2080 propagate_tree_value (rhs_p, sprime);
2083 /* If we removed EH side effects from the statement, clean
2084 its EH information. */
2085 if (maybe_clean_eh_stmt (stmt))
2087 bitmap_set_bit (need_eh_cleanup,
2088 bb_for_stmt (stmt)->index);
2089 if (dump_file && (dump_flags & TDF_DETAILS))
2090 fprintf (dump_file, " Removed EH side effects.\n");
2098 /* Borrow a bit of tree-ssa-dce.c for the moment.
2099 XXX: In 4.1, we should be able to just run a DCE pass after PRE, though
2100 this may be a bit faster, and we may want critical edges kept split. */
2102 /* If OP's defining statement has not already been determined to be necessary,
2103 mark that statement necessary. and place it on the WORKLIST. */
2106 mark_operand_necessary (tree op, VEC(tree_on_heap) **worklist)
2112 stmt = SSA_NAME_DEF_STMT (op);
2115 if (NECESSARY (stmt)
2116 || IS_EMPTY_STMT (stmt))
2119 NECESSARY (stmt) = 1;
2120 VEC_safe_push (tree_on_heap, *worklist, stmt);
2123 /* Because we don't follow exactly the standard PRE algorithm, and decide not
2124 to insert PHI nodes sometimes, and because value numbering of casts isn't
2125 perfect, we sometimes end up inserting dead code. This simple DCE-like
2126 pass removes any insertions we made that weren't actually used. */
2129 remove_dead_inserted_code (void)
2131 VEC (tree_on_heap) *worklist = NULL;
2135 for (i = 0; VEC_iterate (tree_on_heap, inserted_exprs, i, t); i++)
2138 VEC_safe_push (tree_on_heap, worklist, t);
2140 while (VEC_length (tree_on_heap, worklist) > 0)
2142 t = VEC_pop (tree_on_heap, worklist);
2143 if (TREE_CODE (t) == PHI_NODE)
2145 /* PHI nodes are somewhat special in that each PHI alternative has
2146 data and control dependencies. All the statements feeding the
2147 PHI node's arguments are always necessary. In aggressive mode,
2148 we also consider the control dependent edges leading to the
2149 predecessor block associated with each PHI alternative as
2152 for (k = 0; k < PHI_NUM_ARGS (t); k++)
2154 tree arg = PHI_ARG_DEF (t, k);
2155 if (TREE_CODE (arg) == SSA_NAME)
2156 mark_operand_necessary (arg, &worklist);
2161 /* Propagate through the operands. Examine all the USE, VUSE and
2162 V_MAY_DEF operands in this statement. Mark all the statements
2163 which feed this statement's uses as necessary. */
2167 get_stmt_operands (t);
2169 /* The operands of V_MAY_DEF expressions are also needed as they
2170 represent potential definitions that may reach this
2171 statement (V_MAY_DEF operands allow us to follow def-def
2174 FOR_EACH_SSA_TREE_OPERAND (use, t, iter, SSA_OP_ALL_USES)
2175 mark_operand_necessary (use, &worklist);
2178 for (i = 0; VEC_iterate (tree_on_heap, inserted_exprs, i, t); i++)
2182 block_stmt_iterator bsi;
2183 if (dump_file && (dump_flags & TDF_DETAILS))
2185 fprintf (dump_file, "Removing unnecessary insertion:");
2186 print_generic_stmt (dump_file, t, 0);
2188 if (TREE_CODE (t) == PHI_NODE)
2190 remove_phi_node (t, NULL);
2194 bsi = bsi_for_stmt (t);
2199 VEC_free (tree_on_heap, worklist);
2201 /* Initialize data structures used by PRE. */
2204 init_pre (bool do_fre)
2208 inserted_exprs = NULL;
2211 current_loops = loop_optimizer_init (dump_file);
2212 connect_infinite_loops_to_exit ();
2213 memset (&pre_stats, 0, sizeof (pre_stats));
2215 /* If block 0 has more than one predecessor, it means that its PHI
2216 nodes will have arguments coming from block -1. This creates
2217 problems for several places in PRE that keep local arrays indexed
2218 by block number. To prevent this, we split the edge coming from
2219 ENTRY_BLOCK_PTR (FIXME, if ENTRY_BLOCK_PTR had an index number
2220 different than -1 we wouldn't have to hack this. tree-ssa-dce.c
2221 needs a similar change). */
2222 if (!single_pred_p (single_succ (ENTRY_BLOCK_PTR)))
2223 if (!(single_succ_edge (ENTRY_BLOCK_PTR)->flags & EDGE_ABNORMAL))
2224 split_edge (single_succ_edge (ENTRY_BLOCK_PTR));
2227 bb->aux = xcalloc (1, sizeof (struct bb_value_sets));
2229 bitmap_obstack_initialize (&grand_bitmap_obstack);
2230 phi_translate_table = htab_create (511, expr_pred_trans_hash,
2231 expr_pred_trans_eq, free);
2232 value_set_pool = create_alloc_pool ("Value sets",
2233 sizeof (struct value_set), 30);
2234 bitmap_set_pool = create_alloc_pool ("Bitmap sets",
2235 sizeof (struct bitmap_set), 30);
2236 value_set_node_pool = create_alloc_pool ("Value set nodes",
2237 sizeof (struct value_set_node), 30);
2238 calculate_dominance_info (CDI_POST_DOMINATORS);
2239 calculate_dominance_info (CDI_DOMINATORS);
2240 binary_node_pool = create_alloc_pool ("Binary tree nodes",
2241 tree_code_size (PLUS_EXPR), 30);
2242 unary_node_pool = create_alloc_pool ("Unary tree nodes",
2243 tree_code_size (NEGATE_EXPR), 30);
2244 reference_node_pool = create_alloc_pool ("Reference tree nodes",
2245 tree_code_size (ARRAY_REF), 30);
2248 EXP_GEN (bb) = set_new (true);
2249 PHI_GEN (bb) = bitmap_set_new ();
2250 TMP_GEN (bb) = bitmap_set_new ();
2251 AVAIL_OUT (bb) = bitmap_set_new ();
2254 need_eh_cleanup = BITMAP_ALLOC (NULL);
2258 /* Deallocate data structures used by PRE. */
2261 fini_pre (bool do_fre)
2266 VEC_free (tree_on_heap, inserted_exprs);
2267 bitmap_obstack_release (&grand_bitmap_obstack);
2268 free_alloc_pool (value_set_pool);
2269 free_alloc_pool (bitmap_set_pool);
2270 free_alloc_pool (value_set_node_pool);
2271 free_alloc_pool (binary_node_pool);
2272 free_alloc_pool (reference_node_pool);
2273 free_alloc_pool (unary_node_pool);
2274 htab_delete (phi_translate_table);
2275 remove_fake_exit_edges ();
2283 free_dominance_info (CDI_POST_DOMINATORS);
2286 if (!bitmap_empty_p (need_eh_cleanup))
2288 tree_purge_all_dead_eh_edges (need_eh_cleanup);
2289 cleanup_tree_cfg ();
2292 BITMAP_FREE (need_eh_cleanup);
2294 /* Wipe out pointers to VALUE_HANDLEs. In the not terribly distant
2295 future we will want them to be persistent though. */
2296 for (i = 0; i < num_ssa_names; i++)
2298 tree name = ssa_name (i);
2303 if (SSA_NAME_VALUE (name)
2304 && TREE_CODE (SSA_NAME_VALUE (name)) == VALUE_HANDLE)
2305 SSA_NAME_VALUE (name) = NULL;
2307 if (!do_fre && current_loops)
2309 loop_optimizer_finalize (current_loops, dump_file);
2310 current_loops = NULL;
2315 /* Main entry point to the SSA-PRE pass. DO_FRE is true if the caller
2316 only wants to do full redundancy elimination. */
2319 execute_pre (bool do_fre)
2323 /* Collect and value number expressions computed in each basic block. */
2326 if (dump_file && (dump_flags & TDF_DETAILS))
2332 print_value_set (dump_file, EXP_GEN (bb), "exp_gen", bb->index);
2333 bitmap_print_value_set (dump_file, TMP_GEN (bb), "tmp_gen",
2335 bitmap_print_value_set (dump_file, AVAIL_OUT (bb), "avail_out",
2340 /* Insert can get quite slow on an incredibly large number of basic
2341 blocks due to some quadratic behavior. Until this behavior is
2342 fixed, don't run it when he have an incredibly large number of
2343 bb's. If we aren't going to run insert, there is no point in
2344 computing ANTIC, either, even though it's plenty fast. */
2345 if (!do_fre && n_basic_blocks < 4000)
2351 /* Remove all the redundant expressions. */
2355 if (dump_file && (dump_flags & TDF_STATS))
2357 fprintf (dump_file, "Insertions: %d\n", pre_stats.insertions);
2358 fprintf (dump_file, "New PHIs: %d\n", pre_stats.phis);
2359 fprintf (dump_file, "Eliminated: %d\n", pre_stats.eliminations);
2360 fprintf (dump_file, "Constified: %d\n", pre_stats.constified);
2363 bsi_commit_edge_inserts ();
2365 remove_dead_inserted_code ();
2371 /* Gate and execute functions for PRE. */
2376 execute_pre (false);
2382 return flag_tree_pre != 0;
2385 struct tree_opt_pass pass_pre =
2388 gate_pre, /* gate */
2389 do_pre, /* execute */
2392 0, /* static_pass_number */
2393 TV_TREE_PRE, /* tv_id */
2394 PROP_no_crit_edges | PROP_cfg
2395 | PROP_ssa | PROP_alias, /* properties_required */
2396 0, /* properties_provided */
2397 0, /* properties_destroyed */
2398 0, /* todo_flags_start */
2399 TODO_dump_func | TODO_ggc_collect | TODO_verify_ssa, /* todo_flags_finish */
2404 /* Gate and execute functions for FRE. */
2415 return flag_tree_fre != 0;
2418 struct tree_opt_pass pass_fre =
2421 gate_fre, /* gate */
2422 execute_fre, /* execute */
2425 0, /* static_pass_number */
2426 TV_TREE_FRE, /* tv_id */
2427 PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */
2428 0, /* properties_provided */
2429 0, /* properties_destroyed */
2430 0, /* todo_flags_start */
2431 TODO_dump_func | TODO_ggc_collect | TODO_verify_ssa, /* todo_flags_finish */