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. Load motion can be performed by value numbering the loads the
53 same as we do other expressions. This requires iterative
54 hashing the vuses into the values. Right now we simply assign
55 a new value every time we see a statement with a vuse.
56 3. Strength reduction can be performed by anticipating expressions
57 we can repair later on.
58 4. We can do back-substitution or smarter value numbering to catch
59 commutative expressions split up over multiple statements.
62 /* For ease of terminology, "expression node" in the below refers to
63 every expression node but MODIFY_EXPR, because MODIFY_EXPR's represent
64 the actual statement containing the expressions we care about, and
65 we cache the value number by putting it in the expression. */
69 First we walk the statements to generate the AVAIL sets, the
70 EXP_GEN sets, and the tmp_gen sets. EXP_GEN sets represent the
71 generation of values/expressions by a given block. We use them
72 when computing the ANTIC sets. The AVAIL sets consist of
73 SSA_NAME's that represent values, so we know what values are
74 available in what blocks. AVAIL is a forward dataflow problem. In
75 SSA, values are never killed, so we don't need a kill set, or a
76 fixpoint iteration, in order to calculate the AVAIL sets. In
77 traditional parlance, AVAIL sets tell us the downsafety of the
80 Next, we generate the ANTIC sets. These sets represent the
81 anticipatable expressions. ANTIC is a backwards dataflow
82 problem.An expression is anticipatable in a given block if it could
83 be generated in that block. This means that if we had to perform
84 an insertion in that block, of the value of that expression, we
85 could. Calculating the ANTIC sets requires phi translation of
86 expressions, because the flow goes backwards through phis. We must
87 iterate to a fixpoint of the ANTIC sets, because we have a kill
88 set. Even in SSA form, values are not live over the entire
89 function, only from their definition point onwards. So we have to
90 remove values from the ANTIC set once we go past the definition
91 point of the leaders that make them up.
92 compute_antic/compute_antic_aux performs this computation.
94 Third, we perform insertions to make partially redundant
95 expressions fully redundant.
97 An expression is partially redundant (excluding partial
100 1. It is AVAIL in some, but not all, of the predecessors of a
102 2. It is ANTIC in all the predecessors.
104 In order to make it fully redundant, we insert the expression into
105 the predecessors where it is not available, but is ANTIC.
106 insert/insert_aux performs this insertion.
108 Fourth, we eliminate fully redundant expressions.
109 This is a simple statement walk that replaces redundant
110 calculations with the now available values. */
112 /* Representations of value numbers:
114 Value numbers are represented using the "value handle" approach.
115 This means that each SSA_NAME (and for other reasons to be
116 disclosed in a moment, expression nodes) has a value handle that
117 can be retrieved through get_value_handle. This value handle, *is*
118 the value number of the SSA_NAME. You can pointer compare the
119 value handles for equivalence purposes.
121 For debugging reasons, the value handle is internally more than
122 just a number, it is a VAR_DECL named "value.x", where x is a
123 unique number for each value number in use. This allows
124 expressions with SSA_NAMES replaced by value handles to still be
125 pretty printed in a sane way. They simply print as "value.3 *
128 Expression nodes have value handles associated with them as a
129 cache. Otherwise, we'd have to look them up again in the hash
130 table This makes significant difference (factor of two or more) on
131 some test cases. They can be thrown away after the pass is
134 /* Representation of expressions on value numbers:
136 In some portions of this code, you will notice we allocate "fake"
137 analogues to the expression we are value numbering, and replace the
138 operands with the values of the expression. Since we work on
139 values, and not just names, we canonicalize expressions to value
140 expressions for use in the ANTIC sets, the EXP_GEN set, etc.
142 This is theoretically unnecessary, it just saves a bunch of
143 repeated get_value_handle and find_leader calls in the remainder of
144 the code, trading off temporary memory usage for speed. The tree
145 nodes aren't actually creating more garbage, since they are
146 allocated in a special pools which are thrown away at the end of
149 All of this also means that if you print the EXP_GEN or ANTIC sets,
150 you will see "value.5 + value.7" in the set, instead of "a_55 +
151 b_66" or something. The only thing that actually cares about
152 seeing the value leaders is phi translation, and it needs to be
153 able to find the leader for a value in an arbitrary block, so this
154 "value expression" form is perfect for it (otherwise you'd do
155 get_value_handle->find_leader->translate->get_value_handle->find_leader).*/
158 /* Representation of sets:
160 There are currently two types of sets used, hopefully to be unified soon.
161 The AVAIL sets do not need to be sorted in any particular order,
162 and thus, are simply represented as two bitmaps, one that keeps
163 track of values present in the set, and one that keeps track of
164 expressions present in the set.
166 The other sets are represented as doubly linked lists kept in topological
167 order, with an optional supporting bitmap of values present in the
168 set. The sets represent values, and the elements can be values or
169 expressions. The elements can appear in different sets, but each
170 element can only appear once in each set.
172 Since each node in the set represents a value, we also want to be
173 able to map expression, set pairs to something that tells us
174 whether the value is present is a set. We use a per-set bitmap for
175 that. The value handles also point to a linked list of the
176 expressions they represent via a tree annotation. This is mainly
177 useful only for debugging, since we don't do identity lookups. */
180 static bool in_fre
= false;
182 /* A value set element. Basically a single linked list of
183 expressions/values. */
184 typedef struct value_set_node
189 /* A pointer to the next element of the value set. */
190 struct value_set_node
*next
;
194 /* A value set. This is a singly linked list of value_set_node
195 elements with a possible bitmap that tells us what values exist in
196 the set. This set must be kept in topologically sorted order. */
197 typedef struct value_set
199 /* The head of the list. Used for iterating over the list in
201 value_set_node_t head
;
203 /* The tail of the list. Used for tail insertions, which are
204 necessary to keep the set in topologically sorted order because
205 of how the set is built. */
206 value_set_node_t tail
;
208 /* The length of the list. */
211 /* True if the set is indexed, which means it contains a backing
212 bitmap for quick determination of whether certain values exist in the
216 /* The bitmap of values that exist in the set. May be NULL in an
217 empty or non-indexed set. */
223 /* An unordered bitmap set. One bitmap tracks values, the other,
225 typedef struct bitmap_set
231 /* Sets that we need to keep track of. */
232 typedef struct bb_value_sets
234 /* The EXP_GEN set, which represents expressions/values generated in
238 /* The PHI_GEN set, which represents PHI results generated in a
240 bitmap_set_t phi_gen
;
242 /* The TMP_GEN set, which represents results/temporaries generated
243 in a basic block. IE the LHS of an expression. */
244 bitmap_set_t tmp_gen
;
246 /* The AVAIL_OUT set, which represents which values are available in
247 a given basic block. */
248 bitmap_set_t avail_out
;
250 /* The ANTIC_IN set, which represents which values are anticiptable
251 in a given basic block. */
252 value_set_t antic_in
;
254 /* The NEW_SETS set, which is used during insertion to augment the
255 AVAIL_OUT set of blocks with the new insertions performed during
256 the current iteration. */
257 bitmap_set_t new_sets
;
260 #define EXP_GEN(BB) ((bb_value_sets_t) ((BB)->aux))->exp_gen
261 #define PHI_GEN(BB) ((bb_value_sets_t) ((BB)->aux))->phi_gen
262 #define TMP_GEN(BB) ((bb_value_sets_t) ((BB)->aux))->tmp_gen
263 #define AVAIL_OUT(BB) ((bb_value_sets_t) ((BB)->aux))->avail_out
264 #define ANTIC_IN(BB) ((bb_value_sets_t) ((BB)->aux))->antic_in
265 #define NEW_SETS(BB) ((bb_value_sets_t) ((BB)->aux))->new_sets
267 /* This structure is used to keep track of statistics on what
268 optimization PRE was able to perform. */
271 /* The number of RHS computations eliminated by PRE. */
274 /* The number of new expressions/temporaries generated by PRE. */
277 /* The number of new PHI nodes added by PRE. */
280 /* The number of values found constant. */
286 static tree
bitmap_find_leader (bitmap_set_t
, tree
);
287 static tree
find_leader (value_set_t
, tree
);
288 static void value_insert_into_set (value_set_t
, tree
);
289 static void bitmap_value_insert_into_set (bitmap_set_t
, tree
);
290 static void bitmap_value_replace_in_set (bitmap_set_t
, tree
);
291 static void insert_into_set (value_set_t
, tree
);
292 static void bitmap_set_copy (bitmap_set_t
, bitmap_set_t
);
293 static bool bitmap_set_contains_value (bitmap_set_t
, tree
);
294 static bitmap_set_t
bitmap_set_new (void);
295 static value_set_t
set_new (bool);
296 static bool is_undefined_value (tree
);
297 static tree
create_expression_by_pieces (basic_block
, tree
, tree
);
300 /* We can add and remove elements and entries to and from sets
301 and hash tables, so we use alloc pools for them. */
303 static alloc_pool value_set_pool
;
304 static alloc_pool bitmap_set_pool
;
305 static alloc_pool value_set_node_pool
;
306 static alloc_pool binary_node_pool
;
307 static alloc_pool unary_node_pool
;
308 static alloc_pool reference_node_pool
;
309 static alloc_pool comparison_node_pool
;
310 static alloc_pool expression_node_pool
;
311 static alloc_pool list_node_pool
;
312 static bitmap_obstack grand_bitmap_obstack
;
314 /* Set of blocks with statements that have had its EH information
316 static bitmap need_eh_cleanup
;
318 /* The phi_translate_table caches phi translations for a given
319 expression and predecessor. */
321 static htab_t phi_translate_table
;
323 /* A three tuple {e, pred, v} used to cache phi translations in the
324 phi_translate_table. */
326 typedef struct expr_pred_trans_d
328 /* The expression. */
331 /* The predecessor block along which we translated the expression. */
334 /* The value that resulted from the translation. */
337 /* The hashcode for the expression, pred pair. This is cached for
340 } *expr_pred_trans_t
;
342 /* Return the hash value for a phi translation table entry. */
345 expr_pred_trans_hash (const void *p
)
347 const expr_pred_trans_t ve
= (expr_pred_trans_t
) p
;
351 /* Return true if two phi translation table entries are the same.
352 P1 and P2 should point to the expr_pred_trans_t's to be compared.*/
355 expr_pred_trans_eq (const void *p1
, const void *p2
)
357 const expr_pred_trans_t ve1
= (expr_pred_trans_t
) p1
;
358 const expr_pred_trans_t ve2
= (expr_pred_trans_t
) p2
;
359 basic_block b1
= ve1
->pred
;
360 basic_block b2
= ve2
->pred
;
363 /* If they are not translations for the same basic block, they can't
368 /* If they are for the same basic block, determine if the
369 expressions are equal. */
370 if (expressions_equal_p (ve1
->e
, ve2
->e
))
376 /* Search in the phi translation table for the translation of
377 expression E in basic block PRED. Return the translated value, if
378 found, NULL otherwise. */
381 phi_trans_lookup (tree e
, basic_block pred
)
384 struct expr_pred_trans_d ept
;
387 ept
.hashcode
= vn_compute (e
, (unsigned long) pred
, NULL
);
388 slot
= htab_find_slot_with_hash (phi_translate_table
, &ept
, ept
.hashcode
,
393 return ((expr_pred_trans_t
) *slot
)->v
;
397 /* Add the tuple mapping from {expression E, basic block PRED} to
398 value V, to the phi translation table. */
401 phi_trans_add (tree e
, tree v
, basic_block pred
)
404 expr_pred_trans_t new_pair
= xmalloc (sizeof (*new_pair
));
406 new_pair
->pred
= pred
;
408 new_pair
->hashcode
= vn_compute (e
, (unsigned long) pred
, NULL
);
409 slot
= htab_find_slot_with_hash (phi_translate_table
, new_pair
,
410 new_pair
->hashcode
, INSERT
);
413 *slot
= (void *) new_pair
;
417 /* Add expression E to the expression set of value V. */
420 add_to_value (tree v
, tree e
)
422 /* Constants have no expression sets. */
423 if (is_gimple_min_invariant (v
))
426 if (VALUE_HANDLE_EXPR_SET (v
) == NULL
)
427 VALUE_HANDLE_EXPR_SET (v
) = set_new (false);
429 insert_into_set (VALUE_HANDLE_EXPR_SET (v
), e
);
433 /* Return true if value V exists in the bitmap for SET. */
436 value_exists_in_set_bitmap (value_set_t set
, tree v
)
441 return bitmap_bit_p (set
->values
, VALUE_HANDLE_ID (v
));
445 /* Remove value V from the bitmap for SET. */
448 value_remove_from_set_bitmap (value_set_t set
, tree v
)
450 gcc_assert (set
->indexed
);
455 bitmap_clear_bit (set
->values
, VALUE_HANDLE_ID (v
));
459 /* Insert the value number V into the bitmap of values existing in
463 value_insert_into_set_bitmap (value_set_t set
, tree v
)
465 gcc_assert (set
->indexed
);
467 if (set
->values
== NULL
)
468 set
->values
= BITMAP_ALLOC (&grand_bitmap_obstack
);
470 bitmap_set_bit (set
->values
, VALUE_HANDLE_ID (v
));
474 /* Create a new bitmap set and return it. */
477 bitmap_set_new (void)
479 bitmap_set_t ret
= pool_alloc (bitmap_set_pool
);
480 ret
->expressions
= BITMAP_ALLOC (&grand_bitmap_obstack
);
481 ret
->values
= BITMAP_ALLOC (&grand_bitmap_obstack
);
485 /* Create a new set. */
488 set_new (bool indexed
)
491 ret
= pool_alloc (value_set_pool
);
492 ret
->head
= ret
->tail
= NULL
;
494 ret
->indexed
= indexed
;
499 /* Insert an expression EXPR into a bitmapped set. */
502 bitmap_insert_into_set (bitmap_set_t set
, tree expr
)
505 /* XXX: For now, we only let SSA_NAMES into the bitmap sets. */
506 gcc_assert (TREE_CODE (expr
) == SSA_NAME
);
507 val
= get_value_handle (expr
);
510 if (!is_gimple_min_invariant (val
))
512 bitmap_set_bit (set
->values
, VALUE_HANDLE_ID (val
));
513 bitmap_set_bit (set
->expressions
, SSA_NAME_VERSION (expr
));
517 /* Insert EXPR into SET. */
520 insert_into_set (value_set_t set
, tree expr
)
522 value_set_node_t newnode
= pool_alloc (value_set_node_pool
);
523 tree val
= get_value_handle (expr
);
526 if (is_gimple_min_invariant (val
))
529 /* For indexed sets, insert the value into the set value bitmap.
530 For all sets, add it to the linked list and increment the list
533 value_insert_into_set_bitmap (set
, val
);
535 newnode
->next
= NULL
;
536 newnode
->expr
= expr
;
538 if (set
->head
== NULL
)
540 set
->head
= set
->tail
= newnode
;
544 set
->tail
->next
= newnode
;
549 /* Copy a bitmapped set ORIG, into bitmapped set DEST. */
552 bitmap_set_copy (bitmap_set_t dest
, bitmap_set_t orig
)
554 bitmap_copy (dest
->expressions
, orig
->expressions
);
555 bitmap_copy (dest
->values
, orig
->values
);
558 /* Copy the set ORIG to the set DEST. */
561 set_copy (value_set_t dest
, value_set_t orig
)
563 value_set_node_t node
;
565 if (!orig
|| !orig
->head
)
568 for (node
= orig
->head
;
572 insert_into_set (dest
, node
->expr
);
576 /* Remove EXPR from SET. */
579 set_remove (value_set_t set
, tree expr
)
581 value_set_node_t node
, prev
;
583 /* Remove the value of EXPR from the bitmap, decrement the set
584 length, and remove it from the actual double linked list. */
585 value_remove_from_set_bitmap (set
, get_value_handle (expr
));
588 for (node
= set
->head
;
590 prev
= node
, node
= node
->next
)
592 if (node
->expr
== expr
)
595 set
->head
= node
->next
;
597 prev
->next
= node
->next
;
599 if (node
== set
->tail
)
601 pool_free (value_set_node_pool
, node
);
607 /* Return true if SET contains the value VAL. */
610 set_contains_value (value_set_t set
, tree val
)
612 /* All constants are in every set. */
613 if (is_gimple_min_invariant (val
))
616 if (set
->length
== 0)
619 return value_exists_in_set_bitmap (set
, val
);
622 /* Return true if bitmapped set SET contains the expression EXPR. */
624 bitmap_set_contains (bitmap_set_t set
, tree expr
)
626 /* All constants are in every set. */
627 if (is_gimple_min_invariant (get_value_handle (expr
)))
630 /* XXX: Bitmapped sets only contain SSA_NAME's for now. */
631 if (TREE_CODE (expr
) != SSA_NAME
)
633 return bitmap_bit_p (set
->expressions
, SSA_NAME_VERSION (expr
));
637 /* Return true if bitmapped set SET contains the value VAL. */
640 bitmap_set_contains_value (bitmap_set_t set
, tree val
)
642 if (is_gimple_min_invariant (val
))
644 return bitmap_bit_p (set
->values
, VALUE_HANDLE_ID (val
));
647 /* Replace an instance of value LOOKFOR with expression EXPR in SET. */
650 bitmap_set_replace_value (bitmap_set_t set
, tree lookfor
, tree expr
)
653 value_set_node_t node
;
654 if (is_gimple_min_invariant (lookfor
))
656 if (!bitmap_set_contains_value (set
, lookfor
))
659 /* The number of expressions having a given value is usually
660 significantly less than the total number of expressions in SET.
661 Thus, rather than check, for each expression in SET, whether it
662 has the value LOOKFOR, we walk the reverse mapping that tells us
663 what expressions have a given value, and see if any of those
664 expressions are in our set. For large testcases, this is about
665 5-10x faster than walking the bitmap. If this is somehow a
666 significant lose for some cases, we can choose which set to walk
667 based on the set size. */
668 exprset
= VALUE_HANDLE_EXPR_SET (lookfor
);
669 for (node
= exprset
->head
; node
; node
= node
->next
)
671 if (TREE_CODE (node
->expr
) == SSA_NAME
)
673 if (bitmap_bit_p (set
->expressions
, SSA_NAME_VERSION (node
->expr
)))
675 bitmap_clear_bit (set
->expressions
, SSA_NAME_VERSION (node
->expr
));
676 bitmap_set_bit (set
->expressions
, SSA_NAME_VERSION (expr
));
683 /* Subtract bitmapped set B from value set A, and return the new set. */
686 bitmap_set_subtract_from_value_set (value_set_t a
, bitmap_set_t b
,
689 value_set_t ret
= set_new (indexed
);
690 value_set_node_t node
;
695 if (!bitmap_set_contains (b
, node
->expr
))
696 insert_into_set (ret
, node
->expr
);
701 /* Return true if two sets are equal. */
704 set_equal (value_set_t a
, value_set_t b
)
706 value_set_node_t node
;
708 if (a
->length
!= b
->length
)
714 if (!set_contains_value (b
, get_value_handle (node
->expr
)))
720 /* Replace an instance of EXPR's VALUE with EXPR in SET if it exists,
721 and add it otherwise. */
724 bitmap_value_replace_in_set (bitmap_set_t set
, tree expr
)
726 tree val
= get_value_handle (expr
);
727 if (bitmap_set_contains_value (set
, val
))
728 bitmap_set_replace_value (set
, val
, expr
);
730 bitmap_insert_into_set (set
, expr
);
733 /* Insert EXPR into SET if EXPR's value is not already present in
737 bitmap_value_insert_into_set (bitmap_set_t set
, tree expr
)
739 tree val
= get_value_handle (expr
);
741 if (is_gimple_min_invariant (val
))
744 if (!bitmap_set_contains_value (set
, val
))
745 bitmap_insert_into_set (set
, expr
);
748 /* Insert the value for EXPR into SET, if it doesn't exist already. */
751 value_insert_into_set (value_set_t set
, tree expr
)
753 tree val
= get_value_handle (expr
);
755 /* Constant and invariant values exist everywhere, and thus,
756 actually keeping them in the sets is pointless. */
757 if (is_gimple_min_invariant (val
))
760 if (!set_contains_value (set
, val
))
761 insert_into_set (set
, expr
);
765 /* Print out SET to OUTFILE. */
768 bitmap_print_value_set (FILE *outfile
, bitmap_set_t set
,
769 const char *setname
, int blockindex
)
771 fprintf (outfile
, "%s[%d] := { ", setname
, blockindex
);
778 EXECUTE_IF_SET_IN_BITMAP (set
->expressions
, 0, i
, bi
)
781 fprintf (outfile
, ", ");
783 print_generic_expr (outfile
, ssa_name (i
), 0);
785 fprintf (outfile
, " (");
786 print_generic_expr (outfile
, get_value_handle (ssa_name (i
)), 0);
787 fprintf (outfile
, ") ");
790 fprintf (outfile
, " }\n");
792 /* Print out the value_set SET to OUTFILE. */
795 print_value_set (FILE *outfile
, value_set_t set
,
796 const char *setname
, int blockindex
)
798 value_set_node_t node
;
799 fprintf (outfile
, "%s[%d] := { ", setname
, blockindex
);
802 for (node
= set
->head
;
806 print_generic_expr (outfile
, node
->expr
, 0);
808 fprintf (outfile
, " (");
809 print_generic_expr (outfile
, get_value_handle (node
->expr
), 0);
810 fprintf (outfile
, ") ");
813 fprintf (outfile
, ", ");
817 fprintf (outfile
, " }\n");
820 /* Print out the expressions that have VAL to OUTFILE. */
823 print_value_expressions (FILE *outfile
, tree val
)
825 if (VALUE_HANDLE_EXPR_SET (val
))
828 sprintf (s
, "VH.%04d", VALUE_HANDLE_ID (val
));
829 print_value_set (outfile
, VALUE_HANDLE_EXPR_SET (val
), s
, 0);
835 debug_value_expressions (tree val
)
837 print_value_expressions (stderr
, val
);
841 void debug_value_set (value_set_t
, const char *, int);
844 debug_value_set (value_set_t set
, const char *setname
, int blockindex
)
846 print_value_set (stderr
, set
, setname
, blockindex
);
849 /* Return the folded version of T if T, when folded, is a gimple
850 min_invariant. Otherwise, return T. */
853 fully_constant_expression (tree t
)
857 if (folded
&& is_gimple_min_invariant (folded
))
862 /* Return a copy of a chain of nodes, chained through the TREE_CHAIN field.
863 For example, this can copy a list made of TREE_LIST nodes.
864 Allocates the nodes in list_node_pool*/
867 pool_copy_list (tree list
)
874 head
= pool_alloc (list_node_pool
);
876 memcpy (head
, list
, tree_size (list
));
879 next
= TREE_CHAIN (list
);
882 TREE_CHAIN (prev
) = pool_alloc (list_node_pool
);
883 memcpy (TREE_CHAIN (prev
), next
, tree_size (next
));
884 prev
= TREE_CHAIN (prev
);
885 next
= TREE_CHAIN (next
);
891 /* Translate EXPR using phis in PHIBLOCK, so that it has the values of
892 the phis in PRED. Return NULL if we can't find a leader for each
893 part of the translated expression. */
896 phi_translate (tree expr
, value_set_t set
, basic_block pred
,
897 basic_block phiblock
)
899 tree phitrans
= NULL
;
905 if (is_gimple_min_invariant (expr
))
908 /* Phi translations of a given expression don't change. */
909 phitrans
= phi_trans_lookup (expr
, pred
);
913 switch (TREE_CODE_CLASS (TREE_CODE (expr
)))
917 if (TREE_CODE (expr
) != CALL_EXPR
)
921 tree oldop0
= TREE_OPERAND (expr
, 0);
922 tree oldarglist
= TREE_OPERAND (expr
, 1);
923 tree oldop2
= TREE_OPERAND (expr
, 2);
930 bool listchanged
= false;
932 /* Call expressions are kind of weird because they have an
933 argument list. We don't want to value number the list
934 as one value number, because that doesn't make much
935 sense, and just breaks the support functions we call,
936 which expect TREE_OPERAND (call_expr, 2) to be a
939 newop0
= phi_translate (find_leader (set
, oldop0
),
940 set
, pred
, phiblock
);
945 newop2
= phi_translate (find_leader (set
, oldop2
),
946 set
, pred
, phiblock
);
951 /* phi translate the argument list piece by piece.
953 We could actually build the list piece by piece here,
954 but it's likely to not be worth the memory we will save,
955 unless you have millions of call arguments. */
957 newarglist
= pool_copy_list (oldarglist
);
958 for (oldwalker
= oldarglist
, newwalker
= newarglist
;
959 oldwalker
&& newwalker
;
960 oldwalker
= TREE_CHAIN (oldwalker
),
961 newwalker
= TREE_CHAIN (newwalker
))
964 tree oldval
= TREE_VALUE (oldwalker
);
968 newval
= phi_translate (find_leader (set
, oldval
),
969 set
, pred
, phiblock
);
972 if (newval
!= oldval
)
975 TREE_VALUE (newwalker
) = get_value_handle (newval
);
980 vn_lookup_or_add (newarglist
, NULL
);
982 if (listchanged
|| (newop0
!= oldop0
) || (oldop2
!= newop2
))
984 newexpr
= pool_alloc (expression_node_pool
);
985 memcpy (newexpr
, expr
, tree_size (expr
));
986 TREE_OPERAND (newexpr
, 0) = newop0
== oldop0
? oldop0
: get_value_handle (newop0
);
987 TREE_OPERAND (newexpr
, 1) = listchanged
? newarglist
: oldarglist
;
988 TREE_OPERAND (newexpr
, 2) = newop2
== oldop2
? oldop2
: get_value_handle (newop2
);
989 create_tree_ann (newexpr
);
990 vn_lookup_or_add (newexpr
, NULL
);
992 phi_trans_add (oldexpr
, newexpr
, pred
);
999 /* XXX: Until we have PRE of loads working, none will be ANTIC. */
1003 case tcc_comparison
:
1005 tree oldop1
= TREE_OPERAND (expr
, 0);
1006 tree oldop2
= TREE_OPERAND (expr
, 1);
1011 newop1
= phi_translate (find_leader (set
, oldop1
),
1012 set
, pred
, phiblock
);
1015 newop2
= phi_translate (find_leader (set
, oldop2
),
1016 set
, pred
, phiblock
);
1019 if (newop1
!= oldop1
|| newop2
!= oldop2
)
1022 newexpr
= pool_alloc (binary_node_pool
);
1023 memcpy (newexpr
, expr
, tree_size (expr
));
1024 TREE_OPERAND (newexpr
, 0) = newop1
== oldop1
? oldop1
: get_value_handle (newop1
);
1025 TREE_OPERAND (newexpr
, 1) = newop2
== oldop2
? oldop2
: get_value_handle (newop2
);
1026 t
= fully_constant_expression (newexpr
);
1029 pool_free (binary_node_pool
, newexpr
);
1034 create_tree_ann (newexpr
);
1035 vn_lookup_or_add (newexpr
, NULL
);
1038 phi_trans_add (oldexpr
, newexpr
, pred
);
1045 tree oldop1
= TREE_OPERAND (expr
, 0);
1049 newop1
= phi_translate (find_leader (set
, oldop1
),
1050 set
, pred
, phiblock
);
1053 if (newop1
!= oldop1
)
1056 newexpr
= pool_alloc (unary_node_pool
);
1057 memcpy (newexpr
, expr
, tree_size (expr
));
1058 TREE_OPERAND (newexpr
, 0) = get_value_handle (newop1
);
1059 t
= fully_constant_expression (newexpr
);
1062 pool_free (unary_node_pool
, newexpr
);
1067 create_tree_ann (newexpr
);
1068 vn_lookup_or_add (newexpr
, NULL
);
1071 phi_trans_add (oldexpr
, newexpr
, pred
);
1076 case tcc_exceptional
:
1080 gcc_assert (TREE_CODE (expr
) == SSA_NAME
);
1081 if (TREE_CODE (SSA_NAME_DEF_STMT (expr
)) == PHI_NODE
)
1082 phi
= SSA_NAME_DEF_STMT (expr
);
1086 e
= find_edge (pred
, bb_for_stmt (phi
));
1089 if (is_undefined_value (PHI_ARG_DEF (phi
, e
->dest_idx
)))
1091 vn_lookup_or_add (PHI_ARG_DEF (phi
, e
->dest_idx
), NULL
);
1092 return PHI_ARG_DEF (phi
, e
->dest_idx
);
1102 /* For each expression in SET, translate the value handles through phi nodes
1103 in PHIBLOCK using edge PHIBLOCK->PRED, and store the resulting
1104 expressions in DEST. */
1107 phi_translate_set (value_set_t dest
, value_set_t set
, basic_block pred
,
1108 basic_block phiblock
)
1110 value_set_node_t node
;
1111 for (node
= set
->head
;
1116 translated
= phi_translate (node
->expr
, set
, pred
, phiblock
);
1117 phi_trans_add (node
->expr
, translated
, pred
);
1119 if (translated
!= NULL
)
1120 value_insert_into_set (dest
, translated
);
1124 /* Find the leader for a value (i.e., the name representing that
1125 value) in a given set, and return it. Return NULL if no leader is
1129 bitmap_find_leader (bitmap_set_t set
, tree val
)
1134 if (is_gimple_min_invariant (val
))
1136 if (bitmap_set_contains_value (set
, val
))
1138 /* Rather than walk the entire bitmap of expressions, and see
1139 whether any of them has the value we are looking for, we look
1140 at the reverse mapping, which tells us the set of expressions
1141 that have a given value (IE value->expressions with that
1142 value) and see if any of those expressions are in our set.
1143 The number of expressions per value is usually significantly
1144 less than the number of expressions in the set. In fact, for
1145 large testcases, doing it this way is roughly 5-10x faster
1146 than walking the bitmap.
1147 If this is somehow a significant lose for some cases, we can
1148 choose which set to walk based on which set is smaller. */
1149 value_set_t exprset
;
1150 value_set_node_t node
;
1151 exprset
= VALUE_HANDLE_EXPR_SET (val
);
1152 for (node
= exprset
->head
; node
; node
= node
->next
)
1154 if (TREE_CODE (node
->expr
) == SSA_NAME
)
1156 if (bitmap_bit_p (set
->expressions
,
1157 SSA_NAME_VERSION (node
->expr
)))
1166 /* Find the leader for a value (i.e., the name representing that
1167 value) in a given set, and return it. Return NULL if no leader is
1171 find_leader (value_set_t set
, tree val
)
1173 value_set_node_t node
;
1178 /* Constants represent themselves. */
1179 if (is_gimple_min_invariant (val
))
1182 if (set
->length
== 0)
1185 if (value_exists_in_set_bitmap (set
, val
))
1187 for (node
= set
->head
;
1191 if (get_value_handle (node
->expr
) == val
)
1199 /* Determine if the expression EXPR is valid in SET. This means that
1200 we have a leader for each part of the expression (if it consists of
1201 values), or the expression is an SSA_NAME.
1203 NB: We never should run into a case where we have SSA_NAME +
1204 SSA_NAME or SSA_NAME + value. The sets valid_in_set is called on,
1205 the ANTIC sets, will only ever have SSA_NAME's or value expressions
1206 (IE VALUE1 + VALUE2, *VALUE1, VALUE1 < VALUE2) */
1209 valid_in_set (value_set_t set
, tree expr
)
1211 switch (TREE_CODE_CLASS (TREE_CODE (expr
)))
1214 case tcc_comparison
:
1216 tree op1
= TREE_OPERAND (expr
, 0);
1217 tree op2
= TREE_OPERAND (expr
, 1);
1218 return set_contains_value (set
, op1
) && set_contains_value (set
, op2
);
1223 tree op1
= TREE_OPERAND (expr
, 0);
1224 return set_contains_value (set
, op1
);
1227 case tcc_expression
:
1229 if (TREE_CODE (expr
) == CALL_EXPR
)
1231 tree op0
= TREE_OPERAND (expr
, 0);
1232 tree arglist
= TREE_OPERAND (expr
, 1);
1233 tree op2
= TREE_OPERAND (expr
, 2);
1235 /* Check the non-list operands first. */
1236 if (!set_contains_value (set
, op0
)
1237 || (op2
&& !set_contains_value (set
, op2
)))
1240 /* Now check the operands. */
1241 for (; arglist
; arglist
= TREE_CHAIN (arglist
))
1243 if (!set_contains_value (set
, TREE_VALUE (arglist
)))
1252 /* XXX: Until PRE of loads works, no reference nodes are ANTIC. */
1255 case tcc_exceptional
:
1256 gcc_assert (TREE_CODE (expr
) == SSA_NAME
);
1259 case tcc_declaration
:
1260 /* VAR_DECL and PARM_DECL are never anticipatable. */
1264 /* No other cases should be encountered. */
1269 /* Clean the set of expressions that are no longer valid in SET. This
1270 means expressions that are made up of values we have no leaders for
1274 clean (value_set_t set
)
1276 value_set_node_t node
;
1277 value_set_node_t next
;
1282 if (!valid_in_set (set
, node
->expr
))
1283 set_remove (set
, node
->expr
);
1288 DEF_VEC_P (basic_block
);
1289 DEF_VEC_ALLOC_P (basic_block
, heap
);
1290 static sbitmap has_abnormal_preds
;
1292 /* Compute the ANTIC set for BLOCK.
1294 If succs(BLOCK) > 1 then
1295 ANTIC_OUT[BLOCK] = intersection of ANTIC_IN[b] for all succ(BLOCK)
1296 else if succs(BLOCK) == 1 then
1297 ANTIC_OUT[BLOCK] = phi_translate (ANTIC_IN[succ(BLOCK)])
1299 ANTIC_IN[BLOCK] = clean(ANTIC_OUT[BLOCK] U EXP_GEN[BLOCK] - TMP_GEN[BLOCK])
1301 XXX: It would be nice to either write a set_clear, and use it for
1302 ANTIC_OUT, or to mark the antic_out set as deleted at the end
1303 of this routine, so that the pool can hand the same memory back out
1304 again for the next ANTIC_OUT. */
1307 compute_antic_aux (basic_block block
, bool block_has_abnormal_pred_edge
)
1310 bool changed
= false;
1311 value_set_t S
, old
, ANTIC_OUT
;
1312 value_set_node_t node
;
1314 ANTIC_OUT
= S
= NULL
;
1316 /* If any edges from predecessors are abnormal, antic_in is empty,
1318 if (block_has_abnormal_pred_edge
)
1319 goto maybe_dump_sets
;
1321 old
= set_new (false);
1322 set_copy (old
, ANTIC_IN (block
));
1323 ANTIC_OUT
= set_new (true);
1325 /* If the block has no successors, ANTIC_OUT is empty. */
1326 if (EDGE_COUNT (block
->succs
) == 0)
1328 /* If we have one successor, we could have some phi nodes to
1329 translate through. */
1330 else if (single_succ_p (block
))
1332 phi_translate_set (ANTIC_OUT
, ANTIC_IN (single_succ (block
)),
1333 block
, single_succ (block
));
1335 /* If we have multiple successors, we take the intersection of all of
1339 VEC(basic_block
, heap
) * worklist
;
1342 basic_block bprime
, first
;
1345 worklist
= VEC_alloc (basic_block
, heap
, EDGE_COUNT (block
->succs
));
1346 FOR_EACH_EDGE (e
, ei
, block
->succs
)
1347 VEC_quick_push (basic_block
, worklist
, e
->dest
);
1348 first
= VEC_index (basic_block
, worklist
, 0);
1349 set_copy (ANTIC_OUT
, ANTIC_IN (first
));
1351 for (i
= 1; VEC_iterate (basic_block
, worklist
, i
, bprime
); i
++)
1353 node
= ANTIC_OUT
->head
;
1357 value_set_node_t next
= node
->next
;
1358 val
= get_value_handle (node
->expr
);
1359 if (!set_contains_value (ANTIC_IN (bprime
), val
))
1360 set_remove (ANTIC_OUT
, node
->expr
);
1364 VEC_free (basic_block
, heap
, worklist
);
1367 /* Generate ANTIC_OUT - TMP_GEN. */
1368 S
= bitmap_set_subtract_from_value_set (ANTIC_OUT
, TMP_GEN (block
), false);
1370 /* Start ANTIC_IN with EXP_GEN - TMP_GEN */
1371 ANTIC_IN (block
) = bitmap_set_subtract_from_value_set (EXP_GEN (block
),
1375 /* Then union in the ANTIC_OUT - TMP_GEN values,
1376 to get ANTIC_OUT U EXP_GEN - TMP_GEN */
1377 for (node
= S
->head
; node
; node
= node
->next
)
1378 value_insert_into_set (ANTIC_IN (block
), node
->expr
);
1380 clean (ANTIC_IN (block
));
1381 if (!set_equal (old
, ANTIC_IN (block
)))
1385 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1388 print_value_set (dump_file
, ANTIC_OUT
, "ANTIC_OUT", block
->index
);
1389 print_value_set (dump_file
, ANTIC_IN (block
), "ANTIC_IN", block
->index
);
1391 print_value_set (dump_file
, S
, "S", block
->index
);
1394 for (son
= first_dom_son (CDI_POST_DOMINATORS
, block
);
1396 son
= next_dom_son (CDI_POST_DOMINATORS
, son
))
1398 changed
|= compute_antic_aux (son
,
1399 TEST_BIT (has_abnormal_preds
, son
->index
));
1404 /* Compute ANTIC sets. */
1407 compute_antic (void)
1409 bool changed
= true;
1410 int num_iterations
= 0;
1413 /* If any predecessor edges are abnormal, we punt, so antic_in is empty.
1414 We pre-build the map of blocks with incoming abnormal edges here. */
1415 has_abnormal_preds
= sbitmap_alloc (last_basic_block
);
1416 sbitmap_zero (has_abnormal_preds
);
1422 FOR_EACH_EDGE (e
, ei
, block
->preds
)
1423 if (e
->flags
& EDGE_ABNORMAL
)
1425 SET_BIT (has_abnormal_preds
, block
->index
);
1429 /* While we are here, give empty ANTIC_IN sets to each block. */
1430 ANTIC_IN (block
) = set_new (true);
1432 /* At the exit block we anticipate nothing. */
1433 ANTIC_IN (EXIT_BLOCK_PTR
) = set_new (true);
1439 changed
= compute_antic_aux (EXIT_BLOCK_PTR
, false);
1442 sbitmap_free (has_abnormal_preds
);
1444 if (dump_file
&& (dump_flags
& TDF_STATS
))
1445 fprintf (dump_file
, "compute_antic required %d iterations\n", num_iterations
);
1448 static VEC(tree
,heap
) *inserted_exprs
;
1449 /* Find a leader for an expression, or generate one using
1450 create_expression_by_pieces if it's ANTIC but
1452 BLOCK is the basic_block we are looking for leaders in.
1453 EXPR is the expression to find a leader or generate for.
1454 STMTS is the statement list to put the inserted expressions on.
1455 Returns the SSA_NAME of the LHS of the generated expression or the
1459 find_or_generate_expression (basic_block block
, tree expr
, tree stmts
)
1461 tree genop
= bitmap_find_leader (AVAIL_OUT (block
), expr
);
1463 /* If it's still NULL, it must be a complex expression, so generate
1467 genop
= VALUE_HANDLE_EXPR_SET (expr
)->head
->expr
;
1468 gcc_assert (UNARY_CLASS_P (genop
)
1469 || BINARY_CLASS_P (genop
)
1470 || COMPARISON_CLASS_P (genop
)
1471 || REFERENCE_CLASS_P (genop
)
1472 || TREE_CODE (genop
) == CALL_EXPR
);
1473 genop
= create_expression_by_pieces (block
, genop
, stmts
);
1478 #define NECESSARY(stmt) stmt->common.asm_written_flag
1479 /* Create an expression in pieces, so that we can handle very complex
1480 expressions that may be ANTIC, but not necessary GIMPLE.
1481 BLOCK is the basic block the expression will be inserted into,
1482 EXPR is the expression to insert (in value form)
1483 STMTS is a statement list to append the necessary insertions into.
1485 This function will die if we hit some value that shouldn't be
1486 ANTIC but is (IE there is no leader for it, or its components).
1487 This function may also generate expressions that are themselves
1488 partially or fully redundant. Those that are will be either made
1489 fully redundant during the next iteration of insert (for partially
1490 redundant ones), or eliminated by eliminate (for fully redundant
1494 create_expression_by_pieces (basic_block block
, tree expr
, tree stmts
)
1497 tree folded
, forced_stmts
, newexpr
;
1499 tree_stmt_iterator tsi
;
1501 switch (TREE_CODE_CLASS (TREE_CODE (expr
)))
1503 case tcc_expression
:
1507 tree genop0
, genop2
;
1509 tree walker
, genwalker
;
1511 gcc_assert (TREE_CODE (expr
) == CALL_EXPR
);
1514 op0
= TREE_OPERAND (expr
, 0);
1515 arglist
= TREE_OPERAND (expr
, 1);
1516 op2
= TREE_OPERAND (expr
, 2);
1518 genop0
= find_or_generate_expression (block
, op0
, stmts
);
1519 genarglist
= copy_list (arglist
);
1520 for (walker
= arglist
, genwalker
= genarglist
;
1521 genwalker
&& walker
;
1522 genwalker
= TREE_CHAIN (genwalker
), walker
= TREE_CHAIN (walker
))
1524 TREE_VALUE (genwalker
) = find_or_generate_expression (block
,
1525 TREE_VALUE (walker
),
1530 genop2
= find_or_generate_expression (block
, op2
, stmts
);
1531 folded
= fold (build (TREE_CODE (expr
), TREE_TYPE (expr
),
1532 genop0
, genarglist
, genop2
));
1540 case tcc_comparison
:
1542 tree op1
= TREE_OPERAND (expr
, 0);
1543 tree op2
= TREE_OPERAND (expr
, 1);
1544 tree genop1
= find_or_generate_expression (block
, op1
, stmts
);
1545 tree genop2
= find_or_generate_expression (block
, op2
, stmts
);
1546 folded
= fold (build (TREE_CODE (expr
), TREE_TYPE (expr
),
1553 tree op1
= TREE_OPERAND (expr
, 0);
1554 tree genop1
= find_or_generate_expression (block
, op1
, stmts
);
1555 folded
= fold (build (TREE_CODE (expr
), TREE_TYPE (expr
),
1564 /* Force the generated expression to be a sequence of GIMPLE
1566 We have to call unshare_expr because force_gimple_operand may
1567 modify the tree we pass to it. */
1568 newexpr
= force_gimple_operand (unshare_expr (folded
), &forced_stmts
,
1571 /* If we have any intermediate expressions to the value sets, add them
1572 to the value sets and chain them on in the instruction stream. */
1575 tsi
= tsi_start (forced_stmts
);
1576 for (; !tsi_end_p (tsi
); tsi_next (&tsi
))
1578 tree stmt
= tsi_stmt (tsi
);
1579 tree forcedname
= TREE_OPERAND (stmt
, 0);
1580 tree forcedexpr
= TREE_OPERAND (stmt
, 1);
1581 tree val
= vn_lookup_or_add (forcedexpr
, NULL
);
1583 VEC_safe_push (tree
, heap
, inserted_exprs
, stmt
);
1584 vn_add (forcedname
, val
, NULL
);
1585 bitmap_value_replace_in_set (NEW_SETS (block
), forcedname
);
1586 bitmap_value_replace_in_set (AVAIL_OUT (block
), forcedname
);
1588 tsi
= tsi_last (stmts
);
1589 tsi_link_after (&tsi
, forced_stmts
, TSI_CONTINUE_LINKING
);
1592 /* Build and insert the assignment of the end result to the temporary
1593 that we will return. */
1594 temp
= create_tmp_var (TREE_TYPE (expr
), "pretmp");
1595 add_referenced_tmp_var (temp
);
1596 if (TREE_CODE (TREE_TYPE (expr
)) == COMPLEX_TYPE
)
1597 DECL_COMPLEX_GIMPLE_REG_P (temp
) = 1;
1598 newexpr
= build (MODIFY_EXPR
, TREE_TYPE (expr
), temp
, newexpr
);
1599 name
= make_ssa_name (temp
, newexpr
);
1600 TREE_OPERAND (newexpr
, 0) = name
;
1601 NECESSARY (newexpr
) = 0;
1602 tsi
= tsi_last (stmts
);
1603 tsi_link_after (&tsi
, newexpr
, TSI_CONTINUE_LINKING
);
1604 VEC_safe_push (tree
, heap
, inserted_exprs
, newexpr
);
1606 /* Add a value handle to the temporary.
1607 The value may already exist in either NEW_SETS, or AVAIL_OUT, because
1608 we are creating the expression by pieces, and this particular piece of
1609 the expression may have been represented. There is no harm in replacing
1611 v
= get_value_handle (expr
);
1612 vn_add (name
, v
, NULL
);
1613 bitmap_value_replace_in_set (NEW_SETS (block
), name
);
1614 bitmap_value_replace_in_set (AVAIL_OUT (block
), name
);
1616 pre_stats
.insertions
++;
1617 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1619 fprintf (dump_file
, "Inserted ");
1620 print_generic_expr (dump_file
, newexpr
, 0);
1621 fprintf (dump_file
, " in predecessor %d\n", block
->index
);
1627 /* Insert the to-be-made-available values of NODE for each predecessor, stored
1628 in AVAIL, into the predecessors of BLOCK, and merge the result with a phi
1629 node, given the same value handle as NODE. The prefix of the phi node is
1630 given with TMPNAME. Return true if we have inserted new stuff. */
1633 insert_into_preds_of_block (basic_block block
, value_set_node_t node
,
1634 tree
*avail
, const char *tmpname
)
1636 tree val
= get_value_handle (node
->expr
);
1638 bool insertions
= false;
1643 tree type
= TREE_TYPE (avail
[EDGE_PRED (block
, 0)->src
->index
]);
1646 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1648 fprintf (dump_file
, "Found partial redundancy for expression ");
1649 print_generic_expr (dump_file
, node
->expr
, 0);
1650 fprintf (dump_file
, "\n");
1653 /* Make sure we aren't creating an induction variable. */
1654 if (block
->loop_depth
> 0 && EDGE_COUNT (block
->preds
) == 2)
1656 bool firstinsideloop
= false;
1657 bool secondinsideloop
= false;
1658 firstinsideloop
= flow_bb_inside_loop_p (block
->loop_father
,
1659 EDGE_PRED (block
, 0)->src
);
1660 secondinsideloop
= flow_bb_inside_loop_p (block
->loop_father
,
1661 EDGE_PRED (block
, 1)->src
);
1662 /* Induction variables only have one edge inside the loop. */
1663 if (firstinsideloop
^ secondinsideloop
)
1665 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1666 fprintf (dump_file
, "Skipping insertion of phi for partial redundancy: Looks like an induction variable\n");
1672 /* Make the necessary insertions. */
1673 FOR_EACH_EDGE (pred
, ei
, block
->preds
)
1675 tree stmts
= alloc_stmt_list ();
1678 eprime
= avail
[bprime
->index
];
1679 if (BINARY_CLASS_P (eprime
)
1680 || COMPARISON_CLASS_P (eprime
)
1681 || UNARY_CLASS_P (eprime
)
1682 || TREE_CODE (eprime
) == CALL_EXPR
)
1684 builtexpr
= create_expression_by_pieces (bprime
,
1687 bsi_insert_on_edge (pred
, stmts
);
1688 avail
[bprime
->index
] = builtexpr
;
1692 /* If we didn't want a phi node, and we made insertions, we still have
1693 inserted new stuff, and thus return true. If we didn't want a phi node,
1694 and didn't make insertions, we haven't added anything new, so return
1696 if (nophi
&& insertions
)
1698 else if (nophi
&& !insertions
)
1701 /* Now build a phi for the new variable. */
1702 temp
= create_tmp_var (type
, tmpname
);
1703 add_referenced_tmp_var (temp
);
1704 if (TREE_CODE (type
) == COMPLEX_TYPE
)
1705 DECL_COMPLEX_GIMPLE_REG_P (temp
) = 1;
1706 temp
= create_phi_node (temp
, block
);
1707 NECESSARY (temp
) = 0;
1708 VEC_safe_push (tree
, heap
, inserted_exprs
, temp
);
1709 FOR_EACH_EDGE (pred
, ei
, block
->preds
)
1710 add_phi_arg (temp
, avail
[pred
->src
->index
], pred
);
1712 vn_add (PHI_RESULT (temp
), val
, NULL
);
1714 /* The value should *not* exist in PHI_GEN, or else we wouldn't be doing
1715 this insertion, since we test for the existence of this value in PHI_GEN
1716 before proceeding with the partial redundancy checks in insert_aux.
1718 The value may exist in AVAIL_OUT, in particular, it could be represented
1719 by the expression we are trying to eliminate, in which case we want the
1720 replacement to occur. If it's not existing in AVAIL_OUT, we want it
1723 Similarly, to the PHI_GEN case, the value should not exist in NEW_SETS of
1724 this block, because if it did, it would have existed in our dominator's
1725 AVAIL_OUT, and would have been skipped due to the full redundancy check.
1728 bitmap_insert_into_set (PHI_GEN (block
),
1730 bitmap_value_replace_in_set (AVAIL_OUT (block
),
1732 bitmap_insert_into_set (NEW_SETS (block
),
1735 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1737 fprintf (dump_file
, "Created phi ");
1738 print_generic_expr (dump_file
, temp
, 0);
1739 fprintf (dump_file
, " in block %d\n", block
->index
);
1747 /* Perform insertion of partially redundant values.
1748 For BLOCK, do the following:
1749 1. Propagate the NEW_SETS of the dominator into the current block.
1750 If the block has multiple predecessors,
1751 2a. Iterate over the ANTIC expressions for the block to see if
1752 any of them are partially redundant.
1753 2b. If so, insert them into the necessary predecessors to make
1754 the expression fully redundant.
1755 2c. Insert a new PHI merging the values of the predecessors.
1756 2d. Insert the new PHI, and the new expressions, into the
1758 3. Recursively call ourselves on the dominator children of BLOCK.
1763 insert_aux (basic_block block
)
1766 bool new_stuff
= false;
1771 dom
= get_immediate_dominator (CDI_DOMINATORS
, block
);
1776 bitmap_set_t newset
= NEW_SETS (dom
);
1779 /* Note that we need to value_replace both NEW_SETS, and
1780 AVAIL_OUT. For both the case of NEW_SETS, the value may be
1781 represented by some non-simple expression here that we want
1782 to replace it with. */
1783 EXECUTE_IF_SET_IN_BITMAP (newset
->expressions
, 0, i
, bi
)
1785 bitmap_value_replace_in_set (NEW_SETS (block
), ssa_name (i
));
1786 bitmap_value_replace_in_set (AVAIL_OUT (block
), ssa_name (i
));
1789 if (!single_pred_p (block
))
1791 value_set_node_t node
;
1792 for (node
= ANTIC_IN (block
)->head
;
1796 if (BINARY_CLASS_P (node
->expr
)
1797 || COMPARISON_CLASS_P (node
->expr
)
1798 || UNARY_CLASS_P (node
->expr
)
1799 || TREE_CODE (node
->expr
) == CALL_EXPR
)
1803 bool by_some
= false;
1804 bool cant_insert
= false;
1805 bool all_same
= true;
1806 tree first_s
= NULL
;
1809 tree eprime
= NULL_TREE
;
1812 val
= get_value_handle (node
->expr
);
1813 if (bitmap_set_contains_value (PHI_GEN (block
), val
))
1815 if (bitmap_set_contains_value (AVAIL_OUT (dom
), val
))
1817 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1818 fprintf (dump_file
, "Found fully redundant value\n");
1822 avail
= xcalloc (last_basic_block
, sizeof (tree
));
1823 FOR_EACH_EDGE (pred
, ei
, block
->preds
)
1828 /* This can happen in the very weird case
1829 that our fake infinite loop edges have caused a
1830 critical edge to appear. */
1831 if (EDGE_CRITICAL_P (pred
))
1837 eprime
= phi_translate (node
->expr
,
1841 /* eprime will generally only be NULL if the
1842 value of the expression, translated
1843 through the PHI for this predecessor, is
1844 undefined. If that is the case, we can't
1845 make the expression fully redundant,
1846 because its value is undefined along a
1847 predecessor path. We can thus break out
1848 early because it doesn't matter what the
1849 rest of the results are. */
1856 eprime
= fully_constant_expression (eprime
);
1857 vprime
= get_value_handle (eprime
);
1858 gcc_assert (vprime
);
1859 edoubleprime
= bitmap_find_leader (AVAIL_OUT (bprime
),
1861 if (edoubleprime
== NULL
)
1863 avail
[bprime
->index
] = eprime
;
1868 avail
[bprime
->index
] = edoubleprime
;
1870 if (first_s
== NULL
)
1871 first_s
= edoubleprime
;
1872 else if (!operand_equal_p (first_s
, edoubleprime
,
1877 /* If we can insert it, it's not the same value
1878 already existing along every predecessor, and
1879 it's defined by some predecessor, it is
1880 partially redundant. */
1881 if (!cant_insert
&& !all_same
&& by_some
)
1883 if (insert_into_preds_of_block (block
, node
, avail
,
1887 /* If all edges produce the same value and that value is
1888 an invariant, then the PHI has the same value on all
1889 edges. Note this. */
1890 else if (!cant_insert
&& all_same
&& eprime
1891 && is_gimple_min_invariant (eprime
)
1892 && !is_gimple_min_invariant (val
))
1894 value_set_t exprset
= VALUE_HANDLE_EXPR_SET (val
);
1895 value_set_node_t node
;
1896 for (node
= exprset
->head
; node
; node
= node
->next
)
1898 if (TREE_CODE (node
->expr
) == SSA_NAME
)
1900 vn_add (node
->expr
, eprime
, NULL
);
1901 pre_stats
.constified
++;
1911 for (son
= first_dom_son (CDI_DOMINATORS
, block
);
1913 son
= next_dom_son (CDI_DOMINATORS
, son
))
1915 new_stuff
|= insert_aux (son
);
1921 /* Perform insertion of partially redundant values. */
1926 bool new_stuff
= true;
1928 int num_iterations
= 0;
1931 NEW_SETS (bb
) = bitmap_set_new ();
1937 new_stuff
= insert_aux (ENTRY_BLOCK_PTR
);
1939 if (num_iterations
> 2 && dump_file
&& (dump_flags
& TDF_STATS
))
1940 fprintf (dump_file
, "insert required %d iterations\n", num_iterations
);
1944 /* Return true if VAR is an SSA variable with no defining statement in
1945 this procedure, *AND* isn't a live-on-entry parameter. */
1948 is_undefined_value (tree expr
)
1950 return (TREE_CODE (expr
) == SSA_NAME
1951 && IS_EMPTY_STMT (SSA_NAME_DEF_STMT (expr
))
1952 /* PARM_DECLs and hard registers are always defined. */
1953 && TREE_CODE (SSA_NAME_VAR (expr
)) != PARM_DECL
);
1957 /* Given an SSA variable VAR and an expression EXPR, compute the value
1958 number for EXPR and create a value handle (VAL) for it. If VAR and
1959 EXPR are not the same, associate VAL with VAR. Finally, add VAR to
1960 S1 and its value handle to S2.
1962 VUSES represent the virtual use operands associated with EXPR (if
1963 any). They are used when computing the hash value for EXPR. */
1966 add_to_sets (tree var
, tree expr
, tree stmt
, bitmap_set_t s1
,
1969 tree val
= vn_lookup_or_add (expr
, stmt
);
1971 /* VAR and EXPR may be the same when processing statements for which
1972 we are not computing value numbers (e.g., non-assignments, or
1973 statements that make aliased stores). In those cases, we are
1974 only interested in making VAR available as its own value. */
1976 vn_add (var
, val
, NULL_TREE
);
1979 bitmap_insert_into_set (s1
, var
);
1980 bitmap_value_insert_into_set (s2
, var
);
1984 /* Given a unary or binary expression EXPR, create and return a new
1985 expression with the same structure as EXPR but with its operands
1986 replaced with the value handles of each of the operands of EXPR.
1988 VUSES represent the virtual use operands associated with EXPR (if
1989 any). They are used when computing the hash value for EXPR.
1990 Insert EXPR's operands into the EXP_GEN set for BLOCK. */
1993 create_value_expr_from (tree expr
, basic_block block
, tree stmt
)
1996 enum tree_code code
= TREE_CODE (expr
);
2000 gcc_assert (TREE_CODE_CLASS (code
) == tcc_unary
2001 || TREE_CODE_CLASS (code
) == tcc_binary
2002 || TREE_CODE_CLASS (code
) == tcc_comparison
2003 || TREE_CODE_CLASS (code
) == tcc_reference
2004 || TREE_CODE_CLASS (code
) == tcc_expression
2005 || TREE_CODE_CLASS (code
) == tcc_exceptional
);
2007 if (TREE_CODE_CLASS (code
) == tcc_unary
)
2008 pool
= unary_node_pool
;
2009 else if (TREE_CODE_CLASS (code
) == tcc_reference
)
2010 pool
= reference_node_pool
;
2011 else if (TREE_CODE_CLASS (code
) == tcc_binary
)
2012 pool
= binary_node_pool
;
2013 else if (TREE_CODE_CLASS (code
) == tcc_comparison
)
2014 pool
= comparison_node_pool
;
2015 else if (TREE_CODE_CLASS (code
) == tcc_exceptional
)
2017 gcc_assert (code
== TREE_LIST
);
2018 pool
= list_node_pool
;
2022 gcc_assert (code
== CALL_EXPR
);
2023 pool
= expression_node_pool
;
2026 vexpr
= pool_alloc (pool
);
2027 memcpy (vexpr
, expr
, tree_size (expr
));
2029 /* This case is only for TREE_LIST's that appear as part of
2030 CALL_EXPR's. Anything else is a bug, but we can't easily verify
2031 this, hence this comment. TREE_LIST is not handled by the
2032 general case below is because they don't have a fixed length, or
2033 operands, so you can't access purpose/value/chain through
2034 TREE_OPERAND macros. */
2036 if (code
== TREE_LIST
)
2038 tree op
= NULL_TREE
;
2039 tree temp
= NULL_TREE
;
2040 if (TREE_CHAIN (vexpr
))
2041 temp
= create_value_expr_from (TREE_CHAIN (vexpr
), block
, stmt
);
2042 TREE_CHAIN (vexpr
) = temp
? temp
: TREE_CHAIN (vexpr
);
2045 /* Recursively value-numberize reference ops. */
2046 if (REFERENCE_CLASS_P (TREE_VALUE (vexpr
)))
2049 op
= TREE_VALUE (vexpr
);
2050 tempop
= create_value_expr_from (op
, block
, stmt
);
2051 op
= tempop
? tempop
: op
;
2053 TREE_VALUE (vexpr
) = vn_lookup_or_add (op
, stmt
);
2057 op
= TREE_VALUE (vexpr
);
2058 TREE_VALUE (vexpr
) = vn_lookup_or_add (TREE_VALUE (vexpr
), NULL
);
2060 /* This is the equivalent of inserting op into EXP_GEN like we
2062 if (!is_undefined_value (op
))
2063 value_insert_into_set (EXP_GEN (block
), op
);
2068 for (i
= 0; i
< TREE_CODE_LENGTH (code
); i
++)
2072 op
= TREE_OPERAND (expr
, i
);
2073 if (op
== NULL_TREE
)
2076 /* If OP is a constant that has overflowed, do not value number
2078 if (CONSTANT_CLASS_P (op
)
2079 && TREE_OVERFLOW (op
))
2081 pool_free (pool
, vexpr
);
2085 /* Recursively value-numberize reference ops and tree lists. */
2086 if (REFERENCE_CLASS_P (op
))
2088 tree tempop
= create_value_expr_from (op
, block
, stmt
);
2089 op
= tempop
? tempop
: op
;
2090 val
= vn_lookup_or_add (op
, stmt
);
2092 else if (TREE_CODE (op
) == TREE_LIST
)
2096 gcc_assert (TREE_CODE (expr
) == CALL_EXPR
);
2097 tempop
= create_value_expr_from (op
, block
, stmt
);
2099 op
= tempop
? tempop
: op
;
2100 vn_lookup_or_add (op
, NULL
);
2101 /* Unlike everywhere else, we do *not* want to replace the
2102 TREE_LIST itself with a value number, because support
2103 functions we call will blow up. */
2107 /* Create a value handle for OP and add it to VEXPR. */
2108 val
= vn_lookup_or_add (op
, NULL
);
2110 if (!is_undefined_value (op
) && TREE_CODE (op
) != TREE_LIST
)
2111 value_insert_into_set (EXP_GEN (block
), op
);
2113 if (TREE_CODE (val
) == VALUE_HANDLE
)
2114 TREE_TYPE (val
) = TREE_TYPE (TREE_OPERAND (vexpr
, i
));
2116 TREE_OPERAND (vexpr
, i
) = val
;
2123 /* Return true if we can value number a call. This is true if we have
2124 a pure or constant call. */
2126 can_value_number_call (tree stmt
)
2128 tree call
= get_call_expr_in (stmt
);
2130 /* This is a temporary restriction until we translate vuses through
2131 phi nodes. This is only needed for PRE, of course. */
2132 if (!in_fre
&& !ZERO_SSA_OPERANDS (stmt
, SSA_OP_ALL_VIRTUALS
))
2134 if (call_expr_flags (call
) & (ECF_PURE
| ECF_CONST
))
2139 /* Compute the AVAIL set for all basic blocks.
2141 This function performs value numbering of the statements in each basic
2142 block. The AVAIL sets are built from information we glean while doing
2143 this value numbering, since the AVAIL sets contain only one entry per
2146 AVAIL_IN[BLOCK] = AVAIL_OUT[dom(BLOCK)].
2147 AVAIL_OUT[BLOCK] = AVAIL_IN[BLOCK] U PHI_GEN[BLOCK] U TMP_GEN[BLOCK]. */
2150 compute_avail (void)
2152 basic_block block
, son
;
2153 basic_block
*worklist
;
2157 /* For arguments with default definitions, we pretend they are
2158 defined in the entry block. */
2159 for (param
= DECL_ARGUMENTS (current_function_decl
);
2161 param
= TREE_CHAIN (param
))
2163 if (default_def (param
) != NULL
)
2165 tree def
= default_def (param
);
2166 vn_lookup_or_add (def
, NULL
);
2167 bitmap_insert_into_set (TMP_GEN (ENTRY_BLOCK_PTR
), def
);
2168 bitmap_value_insert_into_set (AVAIL_OUT (ENTRY_BLOCK_PTR
), def
);
2172 /* Allocate the worklist. */
2173 worklist
= xmalloc (sizeof (basic_block
) * n_basic_blocks
);
2175 /* Seed the algorithm by putting the dominator children of the entry
2176 block on the worklist. */
2177 for (son
= first_dom_son (CDI_DOMINATORS
, ENTRY_BLOCK_PTR
);
2179 son
= next_dom_son (CDI_DOMINATORS
, son
))
2180 worklist
[sp
++] = son
;
2182 /* Loop until the worklist is empty. */
2185 block_stmt_iterator bsi
;
2189 /* Pick a block from the worklist. */
2190 block
= worklist
[--sp
];
2192 /* Initially, the set of available values in BLOCK is that of
2193 its immediate dominator. */
2194 dom
= get_immediate_dominator (CDI_DOMINATORS
, block
);
2196 bitmap_set_copy (AVAIL_OUT (block
), AVAIL_OUT (dom
));
2198 /* Generate values for PHI nodes. */
2199 for (phi
= phi_nodes (block
); phi
; phi
= PHI_CHAIN (phi
))
2200 /* We have no need for virtual phis, as they don't represent
2201 actual computations. */
2202 if (is_gimple_reg (PHI_RESULT (phi
)))
2203 add_to_sets (PHI_RESULT (phi
), PHI_RESULT (phi
), NULL
,
2204 PHI_GEN (block
), AVAIL_OUT (block
));
2206 /* Now compute value numbers and populate value sets with all
2207 the expressions computed in BLOCK. */
2208 for (bsi
= bsi_start (block
); !bsi_end_p (bsi
); bsi_next (&bsi
))
2214 stmt
= bsi_stmt (bsi
);
2215 ann
= stmt_ann (stmt
);
2217 /* We are only interested in assignments of the form
2218 X_i = EXPR, where EXPR represents an "interesting"
2219 computation, it has no volatile operands and X_i
2220 doesn't flow through an abnormal edge. */
2221 if (TREE_CODE (stmt
) == MODIFY_EXPR
2222 && !ann
->has_volatile_ops
2223 && TREE_CODE (TREE_OPERAND (stmt
, 0)) == SSA_NAME
2224 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (TREE_OPERAND (stmt
, 0)))
2226 tree lhs
= TREE_OPERAND (stmt
, 0);
2227 tree rhs
= TREE_OPERAND (stmt
, 1);
2229 STRIP_USELESS_TYPE_CONVERSION (rhs
);
2230 if (UNARY_CLASS_P (rhs
)
2231 || BINARY_CLASS_P (rhs
)
2232 || COMPARISON_CLASS_P (rhs
)
2233 || REFERENCE_CLASS_P (rhs
)
2234 || (TREE_CODE (rhs
) == CALL_EXPR
2235 && can_value_number_call (stmt
)))
2237 /* For binary, unary, and reference expressions,
2238 create a duplicate expression with the operands
2239 replaced with the value handles of the original
2241 tree newt
= create_value_expr_from (rhs
, block
, stmt
);
2244 add_to_sets (lhs
, newt
, stmt
, TMP_GEN (block
),
2246 value_insert_into_set (EXP_GEN (block
), newt
);
2250 else if (TREE_CODE (rhs
) == SSA_NAME
2251 || is_gimple_min_invariant (rhs
)
2252 || TREE_CODE (rhs
) == ADDR_EXPR
2253 || TREE_INVARIANT (rhs
)
2256 /* Compute a value number for the RHS of the statement
2257 and add its value to the AVAIL_OUT set for the block.
2258 Add the LHS to TMP_GEN. */
2259 add_to_sets (lhs
, rhs
, stmt
, TMP_GEN (block
),
2262 if (TREE_CODE (rhs
) == SSA_NAME
2263 && !is_undefined_value (rhs
))
2264 value_insert_into_set (EXP_GEN (block
), rhs
);
2269 /* For any other statement that we don't recognize, simply
2270 make the names generated by the statement available in
2271 AVAIL_OUT and TMP_GEN. */
2272 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, iter
, SSA_OP_DEF
)
2273 add_to_sets (op
, op
, NULL
, TMP_GEN (block
), AVAIL_OUT (block
));
2275 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, iter
, SSA_OP_USE
)
2276 add_to_sets (op
, op
, NULL
, NULL
, AVAIL_OUT (block
));
2279 /* Put the dominator children of BLOCK on the worklist of blocks
2280 to compute available sets for. */
2281 for (son
= first_dom_son (CDI_DOMINATORS
, block
);
2283 son
= next_dom_son (CDI_DOMINATORS
, son
))
2284 worklist
[sp
++] = son
;
2291 /* Eliminate fully redundant computations. */
2300 block_stmt_iterator i
;
2302 for (i
= bsi_start (b
); !bsi_end_p (i
); bsi_next (&i
))
2304 tree stmt
= bsi_stmt (i
);
2306 /* Lookup the RHS of the expression, see if we have an
2307 available computation for it. If so, replace the RHS with
2308 the available computation. */
2309 if (TREE_CODE (stmt
) == MODIFY_EXPR
2310 && TREE_CODE (TREE_OPERAND (stmt
, 0)) == SSA_NAME
2311 && TREE_CODE (TREE_OPERAND (stmt
,1)) != SSA_NAME
2312 && !is_gimple_min_invariant (TREE_OPERAND (stmt
, 1))
2313 && !stmt_ann (stmt
)->has_volatile_ops
)
2315 tree lhs
= TREE_OPERAND (stmt
, 0);
2316 tree
*rhs_p
= &TREE_OPERAND (stmt
, 1);
2319 sprime
= bitmap_find_leader (AVAIL_OUT (b
),
2320 vn_lookup (lhs
, NULL
));
2323 && (TREE_CODE (*rhs_p
) != SSA_NAME
2324 || may_propagate_copy (*rhs_p
, sprime
)))
2326 gcc_assert (sprime
!= *rhs_p
);
2328 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2330 fprintf (dump_file
, "Replaced ");
2331 print_generic_expr (dump_file
, *rhs_p
, 0);
2332 fprintf (dump_file
, " with ");
2333 print_generic_expr (dump_file
, sprime
, 0);
2334 fprintf (dump_file
, " in ");
2335 print_generic_stmt (dump_file
, stmt
, 0);
2337 if (TREE_CODE (sprime
) == SSA_NAME
)
2338 NECESSARY (SSA_NAME_DEF_STMT (sprime
)) = 1;
2339 pre_stats
.eliminations
++;
2340 propagate_tree_value (rhs_p
, sprime
);
2343 /* If we removed EH side effects from the statement, clean
2344 its EH information. */
2345 if (maybe_clean_or_replace_eh_stmt (stmt
, stmt
))
2347 bitmap_set_bit (need_eh_cleanup
,
2348 bb_for_stmt (stmt
)->index
);
2349 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2350 fprintf (dump_file
, " Removed EH side effects.\n");
2358 /* Borrow a bit of tree-ssa-dce.c for the moment.
2359 XXX: In 4.1, we should be able to just run a DCE pass after PRE, though
2360 this may be a bit faster, and we may want critical edges kept split. */
2362 /* If OP's defining statement has not already been determined to be necessary,
2363 mark that statement necessary. Return the stmt, if it is newly
2367 mark_operand_necessary (tree op
)
2373 stmt
= SSA_NAME_DEF_STMT (op
);
2376 if (NECESSARY (stmt
)
2377 || IS_EMPTY_STMT (stmt
))
2380 NECESSARY (stmt
) = 1;
2384 /* Because we don't follow exactly the standard PRE algorithm, and decide not
2385 to insert PHI nodes sometimes, and because value numbering of casts isn't
2386 perfect, we sometimes end up inserting dead code. This simple DCE-like
2387 pass removes any insertions we made that weren't actually used. */
2390 remove_dead_inserted_code (void)
2392 VEC(tree
,heap
) *worklist
= NULL
;
2396 worklist
= VEC_alloc (tree
, heap
, VEC_length (tree
, inserted_exprs
));
2397 for (i
= 0; VEC_iterate (tree
, inserted_exprs
, i
, t
); i
++)
2400 VEC_quick_push (tree
, worklist
, t
);
2402 while (VEC_length (tree
, worklist
) > 0)
2404 t
= VEC_pop (tree
, worklist
);
2405 if (TREE_CODE (t
) == PHI_NODE
)
2407 /* PHI nodes are somewhat special in that each PHI alternative has
2408 data and control dependencies. All the statements feeding the
2409 PHI node's arguments are always necessary. In aggressive mode,
2410 we also consider the control dependent edges leading to the
2411 predecessor block associated with each PHI alternative as
2415 VEC_reserve (tree
, heap
, worklist
, PHI_NUM_ARGS (t
));
2416 for (k
= 0; k
< PHI_NUM_ARGS (t
); k
++)
2418 tree arg
= PHI_ARG_DEF (t
, k
);
2419 if (TREE_CODE (arg
) == SSA_NAME
)
2421 arg
= mark_operand_necessary (arg
);
2423 VEC_quick_push (tree
, worklist
, arg
);
2429 /* Propagate through the operands. Examine all the USE, VUSE and
2430 V_MAY_DEF operands in this statement. Mark all the statements
2431 which feed this statement's uses as necessary. */
2435 /* The operands of V_MAY_DEF expressions are also needed as they
2436 represent potential definitions that may reach this
2437 statement (V_MAY_DEF operands allow us to follow def-def
2440 FOR_EACH_SSA_TREE_OPERAND (use
, t
, iter
, SSA_OP_ALL_USES
)
2442 tree n
= mark_operand_necessary (use
);
2444 VEC_safe_push (tree
, heap
, worklist
, n
);
2448 for (i
= 0; VEC_iterate (tree
, inserted_exprs
, i
, t
); i
++)
2452 block_stmt_iterator bsi
;
2453 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2455 fprintf (dump_file
, "Removing unnecessary insertion:");
2456 print_generic_stmt (dump_file
, t
, 0);
2458 if (TREE_CODE (t
) == PHI_NODE
)
2460 remove_phi_node (t
, NULL
);
2464 bsi
= bsi_for_stmt (t
);
2469 VEC_free (tree
, heap
, worklist
);
2471 /* Initialize data structures used by PRE. */
2474 init_pre (bool do_fre
)
2480 inserted_exprs
= NULL
;
2483 current_loops
= loop_optimizer_init (dump_file
);
2484 connect_infinite_loops_to_exit ();
2485 memset (&pre_stats
, 0, sizeof (pre_stats
));
2487 /* If block 0 has more than one predecessor, it means that its PHI
2488 nodes will have arguments coming from block -1. This creates
2489 problems for several places in PRE that keep local arrays indexed
2490 by block number. To prevent this, we split the edge coming from
2491 ENTRY_BLOCK_PTR (FIXME, if ENTRY_BLOCK_PTR had an index number
2492 different than -1 we wouldn't have to hack this. tree-ssa-dce.c
2493 needs a similar change). */
2494 if (!single_pred_p (single_succ (ENTRY_BLOCK_PTR
)))
2495 if (!(single_succ_edge (ENTRY_BLOCK_PTR
)->flags
& EDGE_ABNORMAL
))
2496 split_edge (single_succ_edge (ENTRY_BLOCK_PTR
));
2499 bb
->aux
= xcalloc (1, sizeof (struct bb_value_sets
));
2501 bitmap_obstack_initialize (&grand_bitmap_obstack
);
2502 phi_translate_table
= htab_create (511, expr_pred_trans_hash
,
2503 expr_pred_trans_eq
, free
);
2504 value_set_pool
= create_alloc_pool ("Value sets",
2505 sizeof (struct value_set
), 30);
2506 bitmap_set_pool
= create_alloc_pool ("Bitmap sets",
2507 sizeof (struct bitmap_set
), 30);
2508 value_set_node_pool
= create_alloc_pool ("Value set nodes",
2509 sizeof (struct value_set_node
), 30);
2510 calculate_dominance_info (CDI_POST_DOMINATORS
);
2511 calculate_dominance_info (CDI_DOMINATORS
);
2512 binary_node_pool
= create_alloc_pool ("Binary tree nodes",
2513 tree_code_size (PLUS_EXPR
), 30);
2514 unary_node_pool
= create_alloc_pool ("Unary tree nodes",
2515 tree_code_size (NEGATE_EXPR
), 30);
2516 reference_node_pool
= create_alloc_pool ("Reference tree nodes",
2517 tree_code_size (ARRAY_REF
), 30);
2518 expression_node_pool
= create_alloc_pool ("Expression tree nodes",
2519 tree_code_size (CALL_EXPR
), 30);
2520 list_node_pool
= create_alloc_pool ("List tree nodes",
2521 tree_code_size (TREE_LIST
), 30);
2522 comparison_node_pool
= create_alloc_pool ("Comparison tree nodes",
2523 tree_code_size (EQ_EXPR
), 30);
2526 EXP_GEN (bb
) = set_new (true);
2527 PHI_GEN (bb
) = bitmap_set_new ();
2528 TMP_GEN (bb
) = bitmap_set_new ();
2529 AVAIL_OUT (bb
) = bitmap_set_new ();
2532 need_eh_cleanup
= BITMAP_ALLOC (NULL
);
2536 /* Deallocate data structures used by PRE. */
2539 fini_pre (bool do_fre
)
2544 VEC_free (tree
, heap
, inserted_exprs
);
2545 bitmap_obstack_release (&grand_bitmap_obstack
);
2546 free_alloc_pool (value_set_pool
);
2547 free_alloc_pool (bitmap_set_pool
);
2548 free_alloc_pool (value_set_node_pool
);
2549 free_alloc_pool (binary_node_pool
);
2550 free_alloc_pool (reference_node_pool
);
2551 free_alloc_pool (unary_node_pool
);
2552 free_alloc_pool (list_node_pool
);
2553 free_alloc_pool (expression_node_pool
);
2554 free_alloc_pool (comparison_node_pool
);
2555 htab_delete (phi_translate_table
);
2556 remove_fake_exit_edges ();
2564 free_dominance_info (CDI_POST_DOMINATORS
);
2567 if (!bitmap_empty_p (need_eh_cleanup
))
2569 tree_purge_all_dead_eh_edges (need_eh_cleanup
);
2570 cleanup_tree_cfg ();
2573 BITMAP_FREE (need_eh_cleanup
);
2575 /* Wipe out pointers to VALUE_HANDLEs. In the not terribly distant
2576 future we will want them to be persistent though. */
2577 for (i
= 0; i
< num_ssa_names
; i
++)
2579 tree name
= ssa_name (i
);
2584 if (SSA_NAME_VALUE (name
)
2585 && TREE_CODE (SSA_NAME_VALUE (name
)) == VALUE_HANDLE
)
2586 SSA_NAME_VALUE (name
) = NULL
;
2588 if (!do_fre
&& current_loops
)
2590 loop_optimizer_finalize (current_loops
, dump_file
);
2591 current_loops
= NULL
;
2596 /* Main entry point to the SSA-PRE pass. DO_FRE is true if the caller
2597 only wants to do full redundancy elimination. */
2600 execute_pre (bool do_fre
)
2604 /* Collect and value number expressions computed in each basic block. */
2607 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2613 print_value_set (dump_file
, EXP_GEN (bb
), "exp_gen", bb
->index
);
2614 bitmap_print_value_set (dump_file
, TMP_GEN (bb
), "tmp_gen",
2616 bitmap_print_value_set (dump_file
, AVAIL_OUT (bb
), "avail_out",
2621 /* Insert can get quite slow on an incredibly large number of basic
2622 blocks due to some quadratic behavior. Until this behavior is
2623 fixed, don't run it when he have an incredibly large number of
2624 bb's. If we aren't going to run insert, there is no point in
2625 computing ANTIC, either, even though it's plenty fast. */
2626 if (!do_fre
&& n_basic_blocks
< 4000)
2632 /* Remove all the redundant expressions. */
2636 if (dump_file
&& (dump_flags
& TDF_STATS
))
2638 fprintf (dump_file
, "Insertions: %d\n", pre_stats
.insertions
);
2639 fprintf (dump_file
, "New PHIs: %d\n", pre_stats
.phis
);
2640 fprintf (dump_file
, "Eliminated: %d\n", pre_stats
.eliminations
);
2641 fprintf (dump_file
, "Constified: %d\n", pre_stats
.constified
);
2644 bsi_commit_edge_inserts ();
2646 remove_dead_inserted_code ();
2652 /* Gate and execute functions for PRE. */
2657 execute_pre (false);
2663 return flag_tree_pre
!= 0;
2666 struct tree_opt_pass pass_pre
=
2669 gate_pre
, /* gate */
2670 do_pre
, /* execute */
2673 0, /* static_pass_number */
2674 TV_TREE_PRE
, /* tv_id */
2675 PROP_no_crit_edges
| PROP_cfg
2676 | PROP_ssa
| PROP_alias
, /* properties_required */
2677 0, /* properties_provided */
2678 0, /* properties_destroyed */
2679 0, /* todo_flags_start */
2680 TODO_update_ssa
| TODO_dump_func
| TODO_ggc_collect
2681 | TODO_verify_ssa
, /* todo_flags_finish */
2686 /* Gate and execute functions for FRE. */
2697 return flag_tree_fre
!= 0;
2700 struct tree_opt_pass pass_fre
=
2703 gate_fre
, /* gate */
2704 execute_fre
, /* execute */
2707 0, /* static_pass_number */
2708 TV_TREE_FRE
, /* tv_id */
2709 PROP_cfg
| PROP_ssa
| PROP_alias
, /* properties_required */
2710 0, /* properties_provided */
2711 0, /* properties_destroyed */
2712 0, /* todo_flags_start */
2713 TODO_dump_func
| TODO_ggc_collect
| TODO_verify_ssa
, /* todo_flags_finish */