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 static bool in_fre
= false;
183 /* A value set element. Basically a single linked list of
184 expressions/values. */
185 typedef struct value_set_node
190 /* A pointer to the next element of the value set. */
191 struct value_set_node
*next
;
195 /* A value set. This is a singly linked list of value_set_node
196 elements with a possible bitmap that tells us what values exist in
197 the set. This set must be kept in topologically sorted order. */
198 typedef struct value_set
200 /* The head of the list. Used for iterating over the list in
202 value_set_node_t head
;
204 /* The tail of the list. Used for tail insertions, which are
205 necessary to keep the set in topologically sorted order because
206 of how the set is built. */
207 value_set_node_t tail
;
209 /* The length of the list. */
212 /* True if the set is indexed, which means it contains a backing
213 bitmap for quick determination of whether certain values exist in the
217 /* The bitmap of values that exist in the set. May be NULL in an
218 empty or non-indexed set. */
224 /* An unordered bitmap set. One bitmap tracks values, the other,
226 typedef struct bitmap_set
232 /* Sets that we need to keep track of. */
233 typedef struct bb_value_sets
235 /* The EXP_GEN set, which represents expressions/values generated in
239 /* The PHI_GEN set, which represents PHI results generated in a
241 bitmap_set_t phi_gen
;
243 /* The TMP_GEN set, which represents results/temporaries generated
244 in a basic block. IE the LHS of an expression. */
245 bitmap_set_t tmp_gen
;
247 /* The AVAIL_OUT set, which represents which values are available in
248 a given basic block. */
249 bitmap_set_t avail_out
;
251 /* The ANTIC_IN set, which represents which values are anticiptable
252 in a given basic block. */
253 value_set_t antic_in
;
255 /* The NEW_SETS set, which is used during insertion to augment the
256 AVAIL_OUT set of blocks with the new insertions performed during
257 the current iteration. */
258 bitmap_set_t new_sets
;
261 #define EXP_GEN(BB) ((bb_value_sets_t) ((BB)->aux))->exp_gen
262 #define PHI_GEN(BB) ((bb_value_sets_t) ((BB)->aux))->phi_gen
263 #define TMP_GEN(BB) ((bb_value_sets_t) ((BB)->aux))->tmp_gen
264 #define AVAIL_OUT(BB) ((bb_value_sets_t) ((BB)->aux))->avail_out
265 #define ANTIC_IN(BB) ((bb_value_sets_t) ((BB)->aux))->antic_in
266 #define NEW_SETS(BB) ((bb_value_sets_t) ((BB)->aux))->new_sets
268 /* This structure is used to keep track of statistics on what
269 optimization PRE was able to perform. */
272 /* The number of RHS computations eliminated by PRE. */
275 /* The number of new expressions/temporaries generated by PRE. */
278 /* The number of new PHI nodes added by PRE. */
281 /* The number of values found constant. */
287 static tree
bitmap_find_leader (bitmap_set_t
, tree
);
288 static tree
find_leader (value_set_t
, tree
);
289 static void value_insert_into_set (value_set_t
, tree
);
290 static void bitmap_value_insert_into_set (bitmap_set_t
, tree
);
291 static void bitmap_value_replace_in_set (bitmap_set_t
, tree
);
292 static void insert_into_set (value_set_t
, tree
);
293 static void bitmap_set_copy (bitmap_set_t
, bitmap_set_t
);
294 static bool bitmap_set_contains_value (bitmap_set_t
, tree
);
295 static bitmap_set_t
bitmap_set_new (void);
296 static value_set_t
set_new (bool);
297 static bool is_undefined_value (tree
);
298 static tree
create_expression_by_pieces (basic_block
, tree
, tree
);
301 /* We can add and remove elements and entries to and from sets
302 and hash tables, so we use alloc pools for them. */
304 static alloc_pool value_set_pool
;
305 static alloc_pool bitmap_set_pool
;
306 static alloc_pool value_set_node_pool
;
307 static alloc_pool binary_node_pool
;
308 static alloc_pool unary_node_pool
;
309 static alloc_pool reference_node_pool
;
310 static alloc_pool comparison_node_pool
;
311 static alloc_pool expression_node_pool
;
312 static alloc_pool list_node_pool
;
313 static bitmap_obstack grand_bitmap_obstack
;
315 /* Set of blocks with statements that have had its EH information
317 static bitmap need_eh_cleanup
;
319 /* The phi_translate_table caches phi translations for a given
320 expression and predecessor. */
322 static htab_t phi_translate_table
;
324 /* A three tuple {e, pred, v} used to cache phi translations in the
325 phi_translate_table. */
327 typedef struct expr_pred_trans_d
329 /* The expression. */
332 /* The predecessor block along which we translated the expression. */
335 /* The value that resulted from the translation. */
338 /* The hashcode for the expression, pred pair. This is cached for
341 } *expr_pred_trans_t
;
343 /* Return the hash value for a phi translation table entry. */
346 expr_pred_trans_hash (const void *p
)
348 const expr_pred_trans_t ve
= (expr_pred_trans_t
) p
;
352 /* Return true if two phi translation table entries are the same.
353 P1 and P2 should point to the expr_pred_trans_t's to be compared.*/
356 expr_pred_trans_eq (const void *p1
, const void *p2
)
358 const expr_pred_trans_t ve1
= (expr_pred_trans_t
) p1
;
359 const expr_pred_trans_t ve2
= (expr_pred_trans_t
) p2
;
360 basic_block b1
= ve1
->pred
;
361 basic_block b2
= ve2
->pred
;
364 /* If they are not translations for the same basic block, they can't
369 /* If they are for the same basic block, determine if the
370 expressions are equal. */
371 if (expressions_equal_p (ve1
->e
, ve2
->e
))
377 /* Search in the phi translation table for the translation of
378 expression E in basic block PRED. Return the translated value, if
379 found, NULL otherwise. */
382 phi_trans_lookup (tree e
, basic_block pred
)
385 struct expr_pred_trans_d ept
;
388 ept
.hashcode
= vn_compute (e
, (unsigned long) pred
, NULL
);
389 slot
= htab_find_slot_with_hash (phi_translate_table
, &ept
, ept
.hashcode
,
394 return ((expr_pred_trans_t
) *slot
)->v
;
398 /* Add the tuple mapping from {expression E, basic block PRED} to
399 value V, to the phi translation table. */
402 phi_trans_add (tree e
, tree v
, basic_block pred
)
405 expr_pred_trans_t new_pair
= xmalloc (sizeof (*new_pair
));
407 new_pair
->pred
= pred
;
409 new_pair
->hashcode
= vn_compute (e
, (unsigned long) pred
, NULL
);
410 slot
= htab_find_slot_with_hash (phi_translate_table
, new_pair
,
411 new_pair
->hashcode
, INSERT
);
414 *slot
= (void *) new_pair
;
418 /* Add expression E to the expression set of value V. */
421 add_to_value (tree v
, tree e
)
423 /* Constants have no expression sets. */
424 if (is_gimple_min_invariant (v
))
427 if (VALUE_HANDLE_EXPR_SET (v
) == NULL
)
428 VALUE_HANDLE_EXPR_SET (v
) = set_new (false);
430 insert_into_set (VALUE_HANDLE_EXPR_SET (v
), e
);
434 /* Return true if value V exists in the bitmap for SET. */
437 value_exists_in_set_bitmap (value_set_t set
, tree v
)
442 return bitmap_bit_p (set
->values
, VALUE_HANDLE_ID (v
));
446 /* Remove value V from the bitmap for SET. */
449 value_remove_from_set_bitmap (value_set_t set
, tree v
)
451 gcc_assert (set
->indexed
);
456 bitmap_clear_bit (set
->values
, VALUE_HANDLE_ID (v
));
460 /* Insert the value number V into the bitmap of values existing in
464 value_insert_into_set_bitmap (value_set_t set
, tree v
)
466 gcc_assert (set
->indexed
);
468 if (set
->values
== NULL
)
469 set
->values
= BITMAP_ALLOC (&grand_bitmap_obstack
);
471 bitmap_set_bit (set
->values
, VALUE_HANDLE_ID (v
));
475 /* Create a new bitmap set and return it. */
478 bitmap_set_new (void)
480 bitmap_set_t ret
= pool_alloc (bitmap_set_pool
);
481 ret
->expressions
= BITMAP_ALLOC (&grand_bitmap_obstack
);
482 ret
->values
= BITMAP_ALLOC (&grand_bitmap_obstack
);
486 /* Create a new set. */
489 set_new (bool indexed
)
492 ret
= pool_alloc (value_set_pool
);
493 ret
->head
= ret
->tail
= NULL
;
495 ret
->indexed
= indexed
;
500 /* Insert an expression EXPR into a bitmapped set. */
503 bitmap_insert_into_set (bitmap_set_t set
, tree expr
)
506 /* XXX: For now, we only let SSA_NAMES into the bitmap sets. */
507 gcc_assert (TREE_CODE (expr
) == SSA_NAME
);
508 val
= get_value_handle (expr
);
511 if (!is_gimple_min_invariant (val
))
513 bitmap_set_bit (set
->values
, VALUE_HANDLE_ID (val
));
514 bitmap_set_bit (set
->expressions
, SSA_NAME_VERSION (expr
));
518 /* Insert EXPR into SET. */
521 insert_into_set (value_set_t set
, tree expr
)
523 value_set_node_t newnode
= pool_alloc (value_set_node_pool
);
524 tree val
= get_value_handle (expr
);
527 if (is_gimple_min_invariant (val
))
530 /* For indexed sets, insert the value into the set value bitmap.
531 For all sets, add it to the linked list and increment the list
534 value_insert_into_set_bitmap (set
, val
);
536 newnode
->next
= NULL
;
537 newnode
->expr
= expr
;
539 if (set
->head
== NULL
)
541 set
->head
= set
->tail
= newnode
;
545 set
->tail
->next
= newnode
;
550 /* Copy a bitmapped set ORIG, into bitmapped set DEST. */
553 bitmap_set_copy (bitmap_set_t dest
, bitmap_set_t orig
)
555 bitmap_copy (dest
->expressions
, orig
->expressions
);
556 bitmap_copy (dest
->values
, orig
->values
);
559 /* Copy the set ORIG to the set DEST. */
562 set_copy (value_set_t dest
, value_set_t orig
)
564 value_set_node_t node
;
566 if (!orig
|| !orig
->head
)
569 for (node
= orig
->head
;
573 insert_into_set (dest
, node
->expr
);
577 /* Remove EXPR from SET. */
580 set_remove (value_set_t set
, tree expr
)
582 value_set_node_t node
, prev
;
584 /* Remove the value of EXPR from the bitmap, decrement the set
585 length, and remove it from the actual double linked list. */
586 value_remove_from_set_bitmap (set
, get_value_handle (expr
));
589 for (node
= set
->head
;
591 prev
= node
, node
= node
->next
)
593 if (node
->expr
== expr
)
596 set
->head
= node
->next
;
598 prev
->next
= node
->next
;
600 if (node
== set
->tail
)
602 pool_free (value_set_node_pool
, node
);
608 /* Return true if SET contains the value VAL. */
611 set_contains_value (value_set_t set
, tree val
)
613 /* All constants are in every set. */
614 if (is_gimple_min_invariant (val
))
617 if (set
->length
== 0)
620 return value_exists_in_set_bitmap (set
, val
);
623 /* Return true if bitmapped set SET contains the expression EXPR. */
625 bitmap_set_contains (bitmap_set_t set
, tree expr
)
627 /* All constants are in every set. */
628 if (is_gimple_min_invariant (get_value_handle (expr
)))
631 /* XXX: Bitmapped sets only contain SSA_NAME's for now. */
632 if (TREE_CODE (expr
) != SSA_NAME
)
634 return bitmap_bit_p (set
->expressions
, SSA_NAME_VERSION (expr
));
638 /* Return true if bitmapped set SET contains the value VAL. */
641 bitmap_set_contains_value (bitmap_set_t set
, tree val
)
643 if (is_gimple_min_invariant (val
))
645 return bitmap_bit_p (set
->values
, VALUE_HANDLE_ID (val
));
648 /* Replace an instance of value LOOKFOR with expression EXPR in SET. */
651 bitmap_set_replace_value (bitmap_set_t set
, tree lookfor
, tree expr
)
654 value_set_node_t node
;
655 if (is_gimple_min_invariant (lookfor
))
657 if (!bitmap_set_contains_value (set
, lookfor
))
660 /* The number of expressions having a given value is usually
661 significantly less than the total number of expressions in SET.
662 Thus, rather than check, for each expression in SET, whether it
663 has the value LOOKFOR, we walk the reverse mapping that tells us
664 what expressions have a given value, and see if any of those
665 expressions are in our set. For large testcases, this is about
666 5-10x faster than walking the bitmap. If this is somehow a
667 significant lose for some cases, we can choose which set to walk
668 based on the set size. */
669 exprset
= VALUE_HANDLE_EXPR_SET (lookfor
);
670 for (node
= exprset
->head
; node
; node
= node
->next
)
672 if (TREE_CODE (node
->expr
) == SSA_NAME
)
674 if (bitmap_bit_p (set
->expressions
, SSA_NAME_VERSION (node
->expr
)))
676 bitmap_clear_bit (set
->expressions
, SSA_NAME_VERSION (node
->expr
));
677 bitmap_set_bit (set
->expressions
, SSA_NAME_VERSION (expr
));
684 /* Subtract bitmapped set B from value set A, and return the new set. */
687 bitmap_set_subtract_from_value_set (value_set_t a
, bitmap_set_t b
,
690 value_set_t ret
= set_new (indexed
);
691 value_set_node_t node
;
696 if (!bitmap_set_contains (b
, node
->expr
))
697 insert_into_set (ret
, node
->expr
);
702 /* Return true if two sets are equal. */
705 set_equal (value_set_t a
, value_set_t b
)
707 value_set_node_t node
;
709 if (a
->length
!= b
->length
)
715 if (!set_contains_value (b
, get_value_handle (node
->expr
)))
721 /* Replace an instance of EXPR's VALUE with EXPR in SET if it exists,
722 and add it otherwise. */
725 bitmap_value_replace_in_set (bitmap_set_t set
, tree expr
)
727 tree val
= get_value_handle (expr
);
728 if (bitmap_set_contains_value (set
, val
))
729 bitmap_set_replace_value (set
, val
, expr
);
731 bitmap_insert_into_set (set
, expr
);
734 /* Insert EXPR into SET if EXPR's value is not already present in
738 bitmap_value_insert_into_set (bitmap_set_t set
, tree expr
)
740 tree val
= get_value_handle (expr
);
742 if (is_gimple_min_invariant (val
))
745 if (!bitmap_set_contains_value (set
, val
))
746 bitmap_insert_into_set (set
, expr
);
749 /* Insert the value for EXPR into SET, if it doesn't exist already. */
752 value_insert_into_set (value_set_t set
, tree expr
)
754 tree val
= get_value_handle (expr
);
756 /* Constant and invariant values exist everywhere, and thus,
757 actually keeping them in the sets is pointless. */
758 if (is_gimple_min_invariant (val
))
761 if (!set_contains_value (set
, val
))
762 insert_into_set (set
, expr
);
766 /* Print out SET to OUTFILE. */
769 bitmap_print_value_set (FILE *outfile
, bitmap_set_t set
,
770 const char *setname
, int blockindex
)
772 fprintf (outfile
, "%s[%d] := { ", setname
, blockindex
);
779 EXECUTE_IF_SET_IN_BITMAP (set
->expressions
, 0, i
, bi
)
782 fprintf (outfile
, ", ");
784 print_generic_expr (outfile
, ssa_name (i
), 0);
786 fprintf (outfile
, " (");
787 print_generic_expr (outfile
, get_value_handle (ssa_name (i
)), 0);
788 fprintf (outfile
, ") ");
791 fprintf (outfile
, " }\n");
793 /* Print out the value_set SET to OUTFILE. */
796 print_value_set (FILE *outfile
, value_set_t set
,
797 const char *setname
, int blockindex
)
799 value_set_node_t node
;
800 fprintf (outfile
, "%s[%d] := { ", setname
, blockindex
);
803 for (node
= set
->head
;
807 print_generic_expr (outfile
, node
->expr
, 0);
809 fprintf (outfile
, " (");
810 print_generic_expr (outfile
, get_value_handle (node
->expr
), 0);
811 fprintf (outfile
, ") ");
814 fprintf (outfile
, ", ");
818 fprintf (outfile
, " }\n");
821 /* Print out the expressions that have VAL to OUTFILE. */
824 print_value_expressions (FILE *outfile
, tree val
)
826 if (VALUE_HANDLE_EXPR_SET (val
))
829 sprintf (s
, "VH.%04d", VALUE_HANDLE_ID (val
));
830 print_value_set (outfile
, VALUE_HANDLE_EXPR_SET (val
), s
, 0);
836 debug_value_expressions (tree val
)
838 print_value_expressions (stderr
, val
);
842 void debug_value_set (value_set_t
, const char *, int);
845 debug_value_set (value_set_t set
, const char *setname
, int blockindex
)
847 print_value_set (stderr
, set
, setname
, blockindex
);
850 /* Return the folded version of T if T, when folded, is a gimple
851 min_invariant. Otherwise, return T. */
854 fully_constant_expression (tree t
)
858 if (folded
&& is_gimple_min_invariant (folded
))
863 /* Return a copy of a chain of nodes, chained through the TREE_CHAIN field.
864 For example, this can copy a list made of TREE_LIST nodes.
865 Allocates the nodes in list_node_pool*/
868 pool_copy_list (tree list
)
875 head
= pool_alloc (list_node_pool
);
877 memcpy (head
, list
, tree_size (list
));
880 next
= TREE_CHAIN (list
);
883 TREE_CHAIN (prev
) = pool_alloc (list_node_pool
);
884 memcpy (TREE_CHAIN (prev
), next
, tree_size (next
));
885 prev
= TREE_CHAIN (prev
);
886 next
= TREE_CHAIN (next
);
892 /* Translate EXPR using phis in PHIBLOCK, so that it has the values of
893 the phis in PRED. Return NULL if we can't find a leader for each
894 part of the translated expression. */
897 phi_translate (tree expr
, value_set_t set
, basic_block pred
,
898 basic_block phiblock
)
900 tree phitrans
= NULL
;
906 if (is_gimple_min_invariant (expr
))
909 /* Phi translations of a given expression don't change. */
910 phitrans
= phi_trans_lookup (expr
, pred
);
914 switch (TREE_CODE_CLASS (TREE_CODE (expr
)))
918 if (TREE_CODE (expr
) != CALL_EXPR
)
922 tree oldop0
= TREE_OPERAND (expr
, 0);
923 tree oldarglist
= TREE_OPERAND (expr
, 1);
924 tree oldop2
= TREE_OPERAND (expr
, 2);
931 bool listchanged
= false;
933 /* Call expressions are kind of weird because they have an
934 argument list. We don't want to value number the list
935 as one value number, because that doesn't make much
936 sense, and just breaks the support functions we call,
937 which expect TREE_OPERAND (call_expr, 2) to be a
940 newop0
= phi_translate (find_leader (set
, oldop0
),
941 set
, pred
, phiblock
);
946 newop2
= phi_translate (find_leader (set
, oldop2
),
947 set
, pred
, phiblock
);
952 /* phi translate the argument list piece by piece.
954 We could actually build the list piece by piece here,
955 but it's likely to not be worth the memory we will save,
956 unless you have millions of call arguments. */
958 newarglist
= pool_copy_list (oldarglist
);
959 for (oldwalker
= oldarglist
, newwalker
= newarglist
;
960 oldwalker
&& newwalker
;
961 oldwalker
= TREE_CHAIN (oldwalker
),
962 newwalker
= TREE_CHAIN (newwalker
))
965 tree oldval
= TREE_VALUE (oldwalker
);
969 newval
= phi_translate (find_leader (set
, oldval
),
970 set
, pred
, phiblock
);
973 if (newval
!= oldval
)
976 TREE_VALUE (newwalker
) = get_value_handle (newval
);
981 vn_lookup_or_add (newarglist
, NULL
);
983 if (listchanged
|| (newop0
!= oldop0
) || (oldop2
!= newop2
))
985 newexpr
= pool_alloc (expression_node_pool
);
986 memcpy (newexpr
, expr
, tree_size (expr
));
987 TREE_OPERAND (newexpr
, 0) = newop0
== oldop0
? oldop0
: get_value_handle (newop0
);
988 TREE_OPERAND (newexpr
, 1) = listchanged
? newarglist
: oldarglist
;
989 TREE_OPERAND (newexpr
, 2) = newop2
== oldop2
? oldop2
: get_value_handle (newop2
);
990 create_tree_ann (newexpr
);
991 vn_lookup_or_add (newexpr
, NULL
);
993 phi_trans_add (oldexpr
, newexpr
, pred
);
1000 /* XXX: Until we have PRE of loads working, none will be ANTIC. */
1004 case tcc_comparison
:
1006 tree oldop1
= TREE_OPERAND (expr
, 0);
1007 tree oldop2
= TREE_OPERAND (expr
, 1);
1012 newop1
= phi_translate (find_leader (set
, oldop1
),
1013 set
, pred
, phiblock
);
1016 newop2
= phi_translate (find_leader (set
, oldop2
),
1017 set
, pred
, phiblock
);
1020 if (newop1
!= oldop1
|| newop2
!= oldop2
)
1023 newexpr
= pool_alloc (binary_node_pool
);
1024 memcpy (newexpr
, expr
, tree_size (expr
));
1025 TREE_OPERAND (newexpr
, 0) = newop1
== oldop1
? oldop1
: get_value_handle (newop1
);
1026 TREE_OPERAND (newexpr
, 1) = newop2
== oldop2
? oldop2
: get_value_handle (newop2
);
1027 t
= fully_constant_expression (newexpr
);
1030 pool_free (binary_node_pool
, newexpr
);
1035 create_tree_ann (newexpr
);
1036 vn_lookup_or_add (newexpr
, NULL
);
1039 phi_trans_add (oldexpr
, newexpr
, pred
);
1046 tree oldop1
= TREE_OPERAND (expr
, 0);
1050 newop1
= phi_translate (find_leader (set
, oldop1
),
1051 set
, pred
, phiblock
);
1054 if (newop1
!= oldop1
)
1057 newexpr
= pool_alloc (unary_node_pool
);
1058 memcpy (newexpr
, expr
, tree_size (expr
));
1059 TREE_OPERAND (newexpr
, 0) = get_value_handle (newop1
);
1060 t
= fully_constant_expression (newexpr
);
1063 pool_free (unary_node_pool
, newexpr
);
1068 create_tree_ann (newexpr
);
1069 vn_lookup_or_add (newexpr
, NULL
);
1072 phi_trans_add (oldexpr
, newexpr
, pred
);
1077 case tcc_exceptional
:
1081 gcc_assert (TREE_CODE (expr
) == SSA_NAME
);
1082 if (TREE_CODE (SSA_NAME_DEF_STMT (expr
)) == PHI_NODE
)
1083 phi
= SSA_NAME_DEF_STMT (expr
);
1087 e
= find_edge (pred
, bb_for_stmt (phi
));
1090 if (is_undefined_value (PHI_ARG_DEF (phi
, e
->dest_idx
)))
1092 vn_lookup_or_add (PHI_ARG_DEF (phi
, e
->dest_idx
), NULL
);
1093 return PHI_ARG_DEF (phi
, e
->dest_idx
);
1103 /* For each expression in SET, translate the value handles through phi nodes
1104 in PHIBLOCK using edge PHIBLOCK->PRED, and store the resulting
1105 expressions in DEST. */
1108 phi_translate_set (value_set_t dest
, value_set_t set
, basic_block pred
,
1109 basic_block phiblock
)
1111 value_set_node_t node
;
1112 for (node
= set
->head
;
1117 translated
= phi_translate (node
->expr
, set
, pred
, phiblock
);
1118 phi_trans_add (node
->expr
, translated
, pred
);
1120 if (translated
!= NULL
)
1121 value_insert_into_set (dest
, translated
);
1125 /* Find the leader for a value (i.e., the name representing that
1126 value) in a given set, and return it. Return NULL if no leader is
1130 bitmap_find_leader (bitmap_set_t set
, tree val
)
1135 if (is_gimple_min_invariant (val
))
1137 if (bitmap_set_contains_value (set
, val
))
1139 /* Rather than walk the entire bitmap of expressions, and see
1140 whether any of them has the value we are looking for, we look
1141 at the reverse mapping, which tells us the set of expressions
1142 that have a given value (IE value->expressions with that
1143 value) and see if any of those expressions are in our set.
1144 The number of expressions per value is usually significantly
1145 less than the number of expressions in the set. In fact, for
1146 large testcases, doing it this way is roughly 5-10x faster
1147 than walking the bitmap.
1148 If this is somehow a significant lose for some cases, we can
1149 choose which set to walk based on which set is smaller. */
1150 value_set_t exprset
;
1151 value_set_node_t node
;
1152 exprset
= VALUE_HANDLE_EXPR_SET (val
);
1153 for (node
= exprset
->head
; node
; node
= node
->next
)
1155 if (TREE_CODE (node
->expr
) == SSA_NAME
)
1157 if (bitmap_bit_p (set
->expressions
,
1158 SSA_NAME_VERSION (node
->expr
)))
1167 /* Find the leader for a value (i.e., the name representing that
1168 value) in a given set, and return it. Return NULL if no leader is
1172 find_leader (value_set_t set
, tree val
)
1174 value_set_node_t node
;
1179 /* Constants represent themselves. */
1180 if (is_gimple_min_invariant (val
))
1183 if (set
->length
== 0)
1186 if (value_exists_in_set_bitmap (set
, val
))
1188 for (node
= set
->head
;
1192 if (get_value_handle (node
->expr
) == val
)
1200 /* Determine if the expression EXPR is valid in SET. This means that
1201 we have a leader for each part of the expression (if it consists of
1202 values), or the expression is an SSA_NAME.
1204 NB: We never should run into a case where we have SSA_NAME +
1205 SSA_NAME or SSA_NAME + value. The sets valid_in_set is called on,
1206 the ANTIC sets, will only ever have SSA_NAME's or value expressions
1207 (IE VALUE1 + VALUE2, *VALUE1, VALUE1 < VALUE2) */
1210 valid_in_set (value_set_t set
, tree expr
)
1212 switch (TREE_CODE_CLASS (TREE_CODE (expr
)))
1215 case tcc_comparison
:
1217 tree op1
= TREE_OPERAND (expr
, 0);
1218 tree op2
= TREE_OPERAND (expr
, 1);
1219 return set_contains_value (set
, op1
) && set_contains_value (set
, op2
);
1224 tree op1
= TREE_OPERAND (expr
, 0);
1225 return set_contains_value (set
, op1
);
1228 case tcc_expression
:
1230 if (TREE_CODE (expr
) == CALL_EXPR
)
1232 tree op0
= TREE_OPERAND (expr
, 0);
1233 tree arglist
= TREE_OPERAND (expr
, 1);
1234 tree op2
= TREE_OPERAND (expr
, 2);
1236 /* Check the non-list operands first. */
1237 if (!set_contains_value (set
, op0
)
1238 || (op2
&& !set_contains_value (set
, op2
)))
1241 /* Now check the operands. */
1242 for (; arglist
; arglist
= TREE_CHAIN (arglist
))
1244 if (!set_contains_value (set
, TREE_VALUE (arglist
)))
1253 /* XXX: Until PRE of loads works, no reference nodes are ANTIC. */
1256 case tcc_exceptional
:
1257 gcc_assert (TREE_CODE (expr
) == SSA_NAME
);
1260 case tcc_declaration
:
1261 /* VAR_DECL and PARM_DECL are never anticipatable. */
1265 /* No other cases should be encountered. */
1270 /* Clean the set of expressions that are no longer valid in SET. This
1271 means expressions that are made up of values we have no leaders for
1275 clean (value_set_t set
)
1277 value_set_node_t node
;
1278 value_set_node_t next
;
1283 if (!valid_in_set (set
, node
->expr
))
1284 set_remove (set
, node
->expr
);
1289 DEF_VEC_P (basic_block
);
1290 DEF_VEC_ALLOC_P (basic_block
, heap
);
1291 static sbitmap has_abnormal_preds
;
1293 /* Compute the ANTIC set for BLOCK.
1295 If succs(BLOCK) > 1 then
1296 ANTIC_OUT[BLOCK] = intersection of ANTIC_IN[b] for all succ(BLOCK)
1297 else if succs(BLOCK) == 1 then
1298 ANTIC_OUT[BLOCK] = phi_translate (ANTIC_IN[succ(BLOCK)])
1300 ANTIC_IN[BLOCK] = clean(ANTIC_OUT[BLOCK] U EXP_GEN[BLOCK] - TMP_GEN[BLOCK])
1302 XXX: It would be nice to either write a set_clear, and use it for
1303 ANTIC_OUT, or to mark the antic_out set as deleted at the end
1304 of this routine, so that the pool can hand the same memory back out
1305 again for the next ANTIC_OUT. */
1308 compute_antic_aux (basic_block block
, bool block_has_abnormal_pred_edge
)
1311 bool changed
= false;
1312 value_set_t S
, old
, ANTIC_OUT
;
1313 value_set_node_t node
;
1315 ANTIC_OUT
= S
= NULL
;
1317 /* If any edges from predecessors are abnormal, antic_in is empty,
1319 if (block_has_abnormal_pred_edge
)
1320 goto maybe_dump_sets
;
1322 old
= set_new (false);
1323 set_copy (old
, ANTIC_IN (block
));
1324 ANTIC_OUT
= set_new (true);
1326 /* If the block has no successors, ANTIC_OUT is empty. */
1327 if (EDGE_COUNT (block
->succs
) == 0)
1329 /* If we have one successor, we could have some phi nodes to
1330 translate through. */
1331 else if (single_succ_p (block
))
1333 phi_translate_set (ANTIC_OUT
, ANTIC_IN (single_succ (block
)),
1334 block
, single_succ (block
));
1336 /* If we have multiple successors, we take the intersection of all of
1340 VEC(basic_block
, heap
) * worklist
;
1343 basic_block bprime
, first
;
1346 worklist
= VEC_alloc (basic_block
, heap
, EDGE_COUNT (block
->succs
));
1347 FOR_EACH_EDGE (e
, ei
, block
->succs
)
1348 VEC_quick_push (basic_block
, worklist
, e
->dest
);
1349 first
= VEC_index (basic_block
, worklist
, 0);
1350 set_copy (ANTIC_OUT
, ANTIC_IN (first
));
1352 for (i
= 1; VEC_iterate (basic_block
, worklist
, i
, bprime
); i
++)
1354 node
= ANTIC_OUT
->head
;
1358 value_set_node_t next
= node
->next
;
1359 val
= get_value_handle (node
->expr
);
1360 if (!set_contains_value (ANTIC_IN (bprime
), val
))
1361 set_remove (ANTIC_OUT
, node
->expr
);
1365 VEC_free (basic_block
, heap
, worklist
);
1368 /* Generate ANTIC_OUT - TMP_GEN. */
1369 S
= bitmap_set_subtract_from_value_set (ANTIC_OUT
, TMP_GEN (block
), false);
1371 /* Start ANTIC_IN with EXP_GEN - TMP_GEN */
1372 ANTIC_IN (block
) = bitmap_set_subtract_from_value_set (EXP_GEN (block
),
1376 /* Then union in the ANTIC_OUT - TMP_GEN values,
1377 to get ANTIC_OUT U EXP_GEN - TMP_GEN */
1378 for (node
= S
->head
; node
; node
= node
->next
)
1379 value_insert_into_set (ANTIC_IN (block
), node
->expr
);
1381 clean (ANTIC_IN (block
));
1382 if (!set_equal (old
, ANTIC_IN (block
)))
1386 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1389 print_value_set (dump_file
, ANTIC_OUT
, "ANTIC_OUT", block
->index
);
1390 print_value_set (dump_file
, ANTIC_IN (block
), "ANTIC_IN", block
->index
);
1392 print_value_set (dump_file
, S
, "S", block
->index
);
1395 for (son
= first_dom_son (CDI_POST_DOMINATORS
, block
);
1397 son
= next_dom_son (CDI_POST_DOMINATORS
, son
))
1399 changed
|= compute_antic_aux (son
,
1400 TEST_BIT (has_abnormal_preds
, son
->index
));
1405 /* Compute ANTIC sets. */
1408 compute_antic (void)
1410 bool changed
= true;
1411 int num_iterations
= 0;
1414 /* If any predecessor edges are abnormal, we punt, so antic_in is empty.
1415 We pre-build the map of blocks with incoming abnormal edges here. */
1416 has_abnormal_preds
= sbitmap_alloc (last_basic_block
);
1417 sbitmap_zero (has_abnormal_preds
);
1423 FOR_EACH_EDGE (e
, ei
, block
->preds
)
1424 if (e
->flags
& EDGE_ABNORMAL
)
1426 SET_BIT (has_abnormal_preds
, block
->index
);
1430 /* While we are here, give empty ANTIC_IN sets to each block. */
1431 ANTIC_IN (block
) = set_new (true);
1433 /* At the exit block we anticipate nothing. */
1434 ANTIC_IN (EXIT_BLOCK_PTR
) = set_new (true);
1440 changed
= compute_antic_aux (EXIT_BLOCK_PTR
, false);
1443 sbitmap_free (has_abnormal_preds
);
1445 if (dump_file
&& (dump_flags
& TDF_STATS
))
1446 fprintf (dump_file
, "compute_antic required %d iterations\n", num_iterations
);
1449 static VEC(tree
,heap
) *inserted_exprs
;
1450 /* Find a leader for an expression, or generate one using
1451 create_expression_by_pieces if it's ANTIC but
1453 BLOCK is the basic_block we are looking for leaders in.
1454 EXPR is the expression to find a leader or generate for.
1455 STMTS is the statement list to put the inserted expressions on.
1456 Returns the SSA_NAME of the LHS of the generated expression or the
1460 find_or_generate_expression (basic_block block
, tree expr
, tree stmts
)
1462 tree genop
= bitmap_find_leader (AVAIL_OUT (block
), expr
);
1464 /* If it's still NULL, it must be a complex expression, so generate
1468 genop
= VALUE_HANDLE_EXPR_SET (expr
)->head
->expr
;
1469 gcc_assert (UNARY_CLASS_P (genop
)
1470 || BINARY_CLASS_P (genop
)
1471 || COMPARISON_CLASS_P (genop
)
1472 || REFERENCE_CLASS_P (genop
)
1473 || TREE_CODE (genop
) == CALL_EXPR
);
1474 genop
= create_expression_by_pieces (block
, genop
, stmts
);
1479 #define NECESSARY(stmt) stmt->common.asm_written_flag
1480 /* Create an expression in pieces, so that we can handle very complex
1481 expressions that may be ANTIC, but not necessary GIMPLE.
1482 BLOCK is the basic block the expression will be inserted into,
1483 EXPR is the expression to insert (in value form)
1484 STMTS is a statement list to append the necessary insertions into.
1486 This function will die if we hit some value that shouldn't be
1487 ANTIC but is (IE there is no leader for it, or its components).
1488 This function may also generate expressions that are themselves
1489 partially or fully redundant. Those that are will be either made
1490 fully redundant during the next iteration of insert (for partially
1491 redundant ones), or eliminated by eliminate (for fully redundant
1495 create_expression_by_pieces (basic_block block
, tree expr
, tree stmts
)
1498 tree folded
, forced_stmts
, newexpr
;
1500 tree_stmt_iterator tsi
;
1502 switch (TREE_CODE_CLASS (TREE_CODE (expr
)))
1504 case tcc_expression
:
1508 tree genop0
, genop2
;
1510 tree walker
, genwalker
;
1512 gcc_assert (TREE_CODE (expr
) == CALL_EXPR
);
1515 op0
= TREE_OPERAND (expr
, 0);
1516 arglist
= TREE_OPERAND (expr
, 1);
1517 op2
= TREE_OPERAND (expr
, 2);
1519 genop0
= find_or_generate_expression (block
, op0
, stmts
);
1520 genarglist
= copy_list (arglist
);
1521 for (walker
= arglist
, genwalker
= genarglist
;
1522 genwalker
&& walker
;
1523 genwalker
= TREE_CHAIN (genwalker
), walker
= TREE_CHAIN (walker
))
1525 TREE_VALUE (genwalker
) = find_or_generate_expression (block
,
1526 TREE_VALUE (walker
),
1531 genop2
= find_or_generate_expression (block
, op2
, stmts
);
1532 folded
= fold (build (TREE_CODE (expr
), TREE_TYPE (expr
),
1533 genop0
, genarglist
, genop2
));
1541 case tcc_comparison
:
1543 tree op1
= TREE_OPERAND (expr
, 0);
1544 tree op2
= TREE_OPERAND (expr
, 1);
1545 tree genop1
= find_or_generate_expression (block
, op1
, stmts
);
1546 tree genop2
= find_or_generate_expression (block
, op2
, stmts
);
1547 folded
= fold (build (TREE_CODE (expr
), TREE_TYPE (expr
),
1554 tree op1
= TREE_OPERAND (expr
, 0);
1555 tree genop1
= find_or_generate_expression (block
, op1
, stmts
);
1556 folded
= fold (build (TREE_CODE (expr
), TREE_TYPE (expr
),
1565 /* Force the generated expression to be a sequence of GIMPLE
1567 We have to call unshare_expr because force_gimple_operand may
1568 modify the tree we pass to it. */
1569 newexpr
= force_gimple_operand (unshare_expr (folded
), &forced_stmts
,
1572 /* If we have any intermediate expressions to the value sets, add them
1573 to the value sets and chain them on in the instruction stream. */
1576 tsi
= tsi_start (forced_stmts
);
1577 for (; !tsi_end_p (tsi
); tsi_next (&tsi
))
1579 tree stmt
= tsi_stmt (tsi
);
1580 tree forcedname
= TREE_OPERAND (stmt
, 0);
1581 tree forcedexpr
= TREE_OPERAND (stmt
, 1);
1582 tree val
= vn_lookup_or_add (forcedexpr
, NULL
);
1584 VEC_safe_push (tree
, heap
, inserted_exprs
, stmt
);
1585 vn_add (forcedname
, val
, NULL
);
1586 bitmap_value_replace_in_set (NEW_SETS (block
), forcedname
);
1587 bitmap_value_replace_in_set (AVAIL_OUT (block
), forcedname
);
1589 tsi
= tsi_last (stmts
);
1590 tsi_link_after (&tsi
, forced_stmts
, TSI_CONTINUE_LINKING
);
1593 /* Build and insert the assignment of the end result to the temporary
1594 that we will return. */
1595 temp
= create_tmp_var (TREE_TYPE (expr
), "pretmp");
1596 add_referenced_tmp_var (temp
);
1597 newexpr
= build (MODIFY_EXPR
, TREE_TYPE (expr
), temp
, newexpr
);
1598 name
= make_ssa_name (temp
, newexpr
);
1599 TREE_OPERAND (newexpr
, 0) = name
;
1600 NECESSARY (newexpr
) = 0;
1601 tsi
= tsi_last (stmts
);
1602 tsi_link_after (&tsi
, newexpr
, TSI_CONTINUE_LINKING
);
1603 VEC_safe_push (tree
, heap
, inserted_exprs
, newexpr
);
1605 /* Add a value handle to the temporary.
1606 The value may already exist in either NEW_SETS, or AVAIL_OUT, because
1607 we are creating the expression by pieces, and this particular piece of
1608 the expression may have been represented. There is no harm in replacing
1610 v
= get_value_handle (expr
);
1611 vn_add (name
, v
, NULL
);
1612 bitmap_value_replace_in_set (NEW_SETS (block
), name
);
1613 bitmap_value_replace_in_set (AVAIL_OUT (block
), name
);
1615 pre_stats
.insertions
++;
1616 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1618 fprintf (dump_file
, "Inserted ");
1619 print_generic_expr (dump_file
, newexpr
, 0);
1620 fprintf (dump_file
, " in predecessor %d\n", block
->index
);
1626 /* Insert the to-be-made-available values of NODE for each predecessor, stored
1627 in AVAIL, into the predecessors of BLOCK, and merge the result with a phi
1628 node, given the same value handle as NODE. The prefix of the phi node is
1629 given with TMPNAME. Return true if we have inserted new stuff. */
1632 insert_into_preds_of_block (basic_block block
, value_set_node_t node
,
1633 tree
*avail
, const char *tmpname
)
1635 tree val
= get_value_handle (node
->expr
);
1637 bool insertions
= false;
1642 tree type
= TREE_TYPE (avail
[EDGE_PRED (block
, 0)->src
->index
]);
1645 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1647 fprintf (dump_file
, "Found partial redundancy for expression ");
1648 print_generic_expr (dump_file
, node
->expr
, 0);
1649 fprintf (dump_file
, "\n");
1652 /* Make sure we aren't creating an induction variable. */
1653 if (block
->loop_depth
> 0 && EDGE_COUNT (block
->preds
) == 2)
1655 bool firstinsideloop
= false;
1656 bool secondinsideloop
= false;
1657 firstinsideloop
= flow_bb_inside_loop_p (block
->loop_father
,
1658 EDGE_PRED (block
, 0)->src
);
1659 secondinsideloop
= flow_bb_inside_loop_p (block
->loop_father
,
1660 EDGE_PRED (block
, 1)->src
);
1661 /* Induction variables only have one edge inside the loop. */
1662 if (firstinsideloop
^ secondinsideloop
)
1664 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1665 fprintf (dump_file
, "Skipping insertion of phi for partial redundancy: Looks like an induction variable\n");
1671 /* Make the necessary insertions. */
1672 FOR_EACH_EDGE (pred
, ei
, block
->preds
)
1674 tree stmts
= alloc_stmt_list ();
1677 eprime
= avail
[bprime
->index
];
1678 if (BINARY_CLASS_P (eprime
)
1679 || COMPARISON_CLASS_P (eprime
)
1680 || UNARY_CLASS_P (eprime
)
1681 || TREE_CODE (eprime
) == CALL_EXPR
)
1683 builtexpr
= create_expression_by_pieces (bprime
,
1686 bsi_insert_on_edge (pred
, stmts
);
1687 avail
[bprime
->index
] = builtexpr
;
1691 /* If we didn't want a phi node, and we made insertions, we still have
1692 inserted new stuff, and thus return true. If we didn't want a phi node,
1693 and didn't make insertions, we haven't added anything new, so return
1695 if (nophi
&& insertions
)
1697 else if (nophi
&& !insertions
)
1700 /* Now build a phi for the new variable. */
1701 temp
= create_tmp_var (type
, tmpname
);
1702 add_referenced_tmp_var (temp
);
1703 temp
= create_phi_node (temp
, block
);
1704 NECESSARY (temp
) = 0;
1705 VEC_safe_push (tree
, heap
, inserted_exprs
, temp
);
1706 FOR_EACH_EDGE (pred
, ei
, block
->preds
)
1707 add_phi_arg (temp
, avail
[pred
->src
->index
], pred
);
1709 vn_add (PHI_RESULT (temp
), val
, NULL
);
1711 /* The value should *not* exist in PHI_GEN, or else we wouldn't be doing
1712 this insertion, since we test for the existence of this value in PHI_GEN
1713 before proceeding with the partial redundancy checks in insert_aux.
1715 The value may exist in AVAIL_OUT, in particular, it could be represented
1716 by the expression we are trying to eliminate, in which case we want the
1717 replacement to occur. If it's not existing in AVAIL_OUT, we want it
1720 Similarly, to the PHI_GEN case, the value should not exist in NEW_SETS of
1721 this block, because if it did, it would have existed in our dominator's
1722 AVAIL_OUT, and would have been skipped due to the full redundancy check.
1725 bitmap_insert_into_set (PHI_GEN (block
),
1727 bitmap_value_replace_in_set (AVAIL_OUT (block
),
1729 bitmap_insert_into_set (NEW_SETS (block
),
1732 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1734 fprintf (dump_file
, "Created phi ");
1735 print_generic_expr (dump_file
, temp
, 0);
1736 fprintf (dump_file
, " in block %d\n", block
->index
);
1744 /* Perform insertion of partially redundant values.
1745 For BLOCK, do the following:
1746 1. Propagate the NEW_SETS of the dominator into the current block.
1747 If the block has multiple predecessors,
1748 2a. Iterate over the ANTIC expressions for the block to see if
1749 any of them are partially redundant.
1750 2b. If so, insert them into the necessary predecessors to make
1751 the expression fully redundant.
1752 2c. Insert a new PHI merging the values of the predecessors.
1753 2d. Insert the new PHI, and the new expressions, into the
1755 3. Recursively call ourselves on the dominator children of BLOCK.
1760 insert_aux (basic_block block
)
1763 bool new_stuff
= false;
1768 dom
= get_immediate_dominator (CDI_DOMINATORS
, block
);
1773 bitmap_set_t newset
= NEW_SETS (dom
);
1776 /* Note that we need to value_replace both NEW_SETS, and
1777 AVAIL_OUT. For both the case of NEW_SETS, the value may be
1778 represented by some non-simple expression here that we want
1779 to replace it with. */
1780 EXECUTE_IF_SET_IN_BITMAP (newset
->expressions
, 0, i
, bi
)
1782 bitmap_value_replace_in_set (NEW_SETS (block
), ssa_name (i
));
1783 bitmap_value_replace_in_set (AVAIL_OUT (block
), ssa_name (i
));
1786 if (!single_pred_p (block
))
1788 value_set_node_t node
;
1789 for (node
= ANTIC_IN (block
)->head
;
1793 if (BINARY_CLASS_P (node
->expr
)
1794 || COMPARISON_CLASS_P (node
->expr
)
1795 || UNARY_CLASS_P (node
->expr
)
1796 || TREE_CODE (node
->expr
) == CALL_EXPR
)
1800 bool by_some
= false;
1801 bool cant_insert
= false;
1802 bool all_same
= true;
1803 tree first_s
= NULL
;
1806 tree eprime
= NULL_TREE
;
1809 val
= get_value_handle (node
->expr
);
1810 if (bitmap_set_contains_value (PHI_GEN (block
), val
))
1812 if (bitmap_set_contains_value (AVAIL_OUT (dom
), val
))
1814 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1815 fprintf (dump_file
, "Found fully redundant value\n");
1819 avail
= xcalloc (last_basic_block
, sizeof (tree
));
1820 FOR_EACH_EDGE (pred
, ei
, block
->preds
)
1825 /* This can happen in the very weird case
1826 that our fake infinite loop edges have caused a
1827 critical edge to appear. */
1828 if (EDGE_CRITICAL_P (pred
))
1834 eprime
= phi_translate (node
->expr
,
1838 /* eprime will generally only be NULL if the
1839 value of the expression, translated
1840 through the PHI for this predecessor, is
1841 undefined. If that is the case, we can't
1842 make the expression fully redundant,
1843 because its value is undefined along a
1844 predecessor path. We can thus break out
1845 early because it doesn't matter what the
1846 rest of the results are. */
1853 eprime
= fully_constant_expression (eprime
);
1854 vprime
= get_value_handle (eprime
);
1855 gcc_assert (vprime
);
1856 edoubleprime
= bitmap_find_leader (AVAIL_OUT (bprime
),
1858 if (edoubleprime
== NULL
)
1860 avail
[bprime
->index
] = eprime
;
1865 avail
[bprime
->index
] = edoubleprime
;
1867 if (first_s
== NULL
)
1868 first_s
= edoubleprime
;
1869 else if (!operand_equal_p (first_s
, edoubleprime
,
1874 /* If we can insert it, it's not the same value
1875 already existing along every predecessor, and
1876 it's defined by some predecessor, it is
1877 partially redundant. */
1878 if (!cant_insert
&& !all_same
&& by_some
)
1880 if (insert_into_preds_of_block (block
, node
, avail
,
1884 /* If all edges produce the same value and that value is
1885 an invariant, then the PHI has the same value on all
1886 edges. Note this. */
1887 else if (!cant_insert
&& all_same
&& eprime
1888 && is_gimple_min_invariant (eprime
)
1889 && !is_gimple_min_invariant (val
))
1891 value_set_t exprset
= VALUE_HANDLE_EXPR_SET (val
);
1892 value_set_node_t node
;
1893 for (node
= exprset
->head
; node
; node
= node
->next
)
1895 if (TREE_CODE (node
->expr
) == SSA_NAME
)
1897 vn_add (node
->expr
, eprime
, NULL
);
1898 pre_stats
.constified
++;
1908 for (son
= first_dom_son (CDI_DOMINATORS
, block
);
1910 son
= next_dom_son (CDI_DOMINATORS
, son
))
1912 new_stuff
|= insert_aux (son
);
1918 /* Perform insertion of partially redundant values. */
1923 bool new_stuff
= true;
1925 int num_iterations
= 0;
1928 NEW_SETS (bb
) = bitmap_set_new ();
1934 new_stuff
= insert_aux (ENTRY_BLOCK_PTR
);
1936 if (num_iterations
> 2 && dump_file
&& (dump_flags
& TDF_STATS
))
1937 fprintf (dump_file
, "insert required %d iterations\n", num_iterations
);
1941 /* Return true if VAR is an SSA variable with no defining statement in
1942 this procedure, *AND* isn't a live-on-entry parameter. */
1945 is_undefined_value (tree expr
)
1947 return (TREE_CODE (expr
) == SSA_NAME
1948 && IS_EMPTY_STMT (SSA_NAME_DEF_STMT (expr
))
1949 /* PARM_DECLs and hard registers are always defined. */
1950 && TREE_CODE (SSA_NAME_VAR (expr
)) != PARM_DECL
);
1954 /* Given an SSA variable VAR and an expression EXPR, compute the value
1955 number for EXPR and create a value handle (VAL) for it. If VAR and
1956 EXPR are not the same, associate VAL with VAR. Finally, add VAR to
1957 S1 and its value handle to S2.
1959 VUSES represent the virtual use operands associated with EXPR (if
1960 any). They are used when computing the hash value for EXPR. */
1963 add_to_sets (tree var
, tree expr
, tree stmt
, bitmap_set_t s1
,
1966 tree val
= vn_lookup_or_add (expr
, stmt
);
1968 /* VAR and EXPR may be the same when processing statements for which
1969 we are not computing value numbers (e.g., non-assignments, or
1970 statements that make aliased stores). In those cases, we are
1971 only interested in making VAR available as its own value. */
1973 vn_add (var
, val
, NULL_TREE
);
1976 bitmap_insert_into_set (s1
, var
);
1977 bitmap_value_insert_into_set (s2
, var
);
1981 /* Given a unary or binary expression EXPR, create and return a new
1982 expression with the same structure as EXPR but with its operands
1983 replaced with the value handles of each of the operands of EXPR.
1985 VUSES represent the virtual use operands associated with EXPR (if
1986 any). They are used when computing the hash value for EXPR.
1987 Insert EXPR's operands into the EXP_GEN set for BLOCK. */
1990 create_value_expr_from (tree expr
, basic_block block
, tree stmt
)
1993 enum tree_code code
= TREE_CODE (expr
);
1997 gcc_assert (TREE_CODE_CLASS (code
) == tcc_unary
1998 || TREE_CODE_CLASS (code
) == tcc_binary
1999 || TREE_CODE_CLASS (code
) == tcc_comparison
2000 || TREE_CODE_CLASS (code
) == tcc_reference
2001 || TREE_CODE_CLASS (code
) == tcc_expression
2002 || TREE_CODE_CLASS (code
) == tcc_exceptional
);
2004 if (TREE_CODE_CLASS (code
) == tcc_unary
)
2005 pool
= unary_node_pool
;
2006 else if (TREE_CODE_CLASS (code
) == tcc_reference
)
2007 pool
= reference_node_pool
;
2008 else if (TREE_CODE_CLASS (code
) == tcc_binary
)
2009 pool
= binary_node_pool
;
2010 else if (TREE_CODE_CLASS (code
) == tcc_comparison
)
2011 pool
= comparison_node_pool
;
2012 else if (TREE_CODE_CLASS (code
) == tcc_exceptional
)
2014 gcc_assert (code
== TREE_LIST
);
2015 pool
= list_node_pool
;
2019 gcc_assert (code
== CALL_EXPR
);
2020 pool
= expression_node_pool
;
2023 vexpr
= pool_alloc (pool
);
2024 memcpy (vexpr
, expr
, tree_size (expr
));
2026 /* This case is only for TREE_LIST's that appear as part of
2027 CALL_EXPR's. Anything else is a bug, but we can't easily verify
2028 this, hence this comment. TREE_LIST is not handled by the
2029 general case below is because they don't have a fixed length, or
2030 operands, so you can't access purpose/value/chain through
2031 TREE_OPERAND macros. */
2033 if (code
== TREE_LIST
)
2035 tree op
= NULL_TREE
;
2036 tree temp
= NULL_TREE
;
2037 if (TREE_CHAIN (vexpr
))
2038 temp
= create_value_expr_from (TREE_CHAIN (vexpr
), block
, stmt
);
2039 TREE_CHAIN (vexpr
) = temp
? temp
: TREE_CHAIN (vexpr
);
2042 /* Recursively value-numberize reference ops. */
2043 if (REFERENCE_CLASS_P (TREE_VALUE (vexpr
)))
2046 op
= TREE_VALUE (vexpr
);
2047 tempop
= create_value_expr_from (op
, block
, stmt
);
2048 op
= tempop
? tempop
: op
;
2050 TREE_VALUE (vexpr
) = vn_lookup_or_add (op
, stmt
);
2054 op
= TREE_VALUE (vexpr
);
2055 TREE_VALUE (vexpr
) = vn_lookup_or_add (TREE_VALUE (vexpr
), NULL
);
2057 /* This is the equivalent of inserting op into EXP_GEN like we
2059 if (!is_undefined_value (op
))
2060 value_insert_into_set (EXP_GEN (block
), op
);
2065 for (i
= 0; i
< TREE_CODE_LENGTH (code
); i
++)
2069 op
= TREE_OPERAND (expr
, i
);
2070 if (op
== NULL_TREE
)
2073 /* If OP is a constant that has overflowed, do not value number
2075 if (CONSTANT_CLASS_P (op
)
2076 && TREE_OVERFLOW (op
))
2078 pool_free (pool
, vexpr
);
2082 /* Recursively value-numberize reference ops and tree lists. */
2083 if (REFERENCE_CLASS_P (op
))
2085 tree tempop
= create_value_expr_from (op
, block
, stmt
);
2086 op
= tempop
? tempop
: op
;
2087 val
= vn_lookup_or_add (op
, stmt
);
2089 else if (TREE_CODE (op
) == TREE_LIST
)
2093 gcc_assert (TREE_CODE (expr
) == CALL_EXPR
);
2094 tempop
= create_value_expr_from (op
, block
, stmt
);
2096 op
= tempop
? tempop
: op
;
2097 vn_lookup_or_add (op
, NULL
);
2098 /* Unlike everywhere else, we do *not* want to replace the
2099 TREE_LIST itself with a value number, because support
2100 functions we call will blow up. */
2104 /* Create a value handle for OP and add it to VEXPR. */
2105 val
= vn_lookup_or_add (op
, NULL
);
2107 if (!is_undefined_value (op
) && TREE_CODE (op
) != TREE_LIST
)
2108 value_insert_into_set (EXP_GEN (block
), op
);
2110 if (TREE_CODE (val
) == VALUE_HANDLE
)
2111 TREE_TYPE (val
) = TREE_TYPE (TREE_OPERAND (vexpr
, i
));
2113 TREE_OPERAND (vexpr
, i
) = val
;
2120 /* Return true if we can value number a call. This is true if we have
2121 a pure or constant call. */
2123 can_value_number_call (tree stmt
)
2125 tree call
= get_call_expr_in (stmt
);
2127 /* This is a temporary restriction until we translate vuses through
2128 phi nodes. This is only needed for PRE, of course. */
2129 if (!in_fre
&& !ZERO_SSA_OPERANDS (stmt
, SSA_OP_ALL_VIRTUALS
))
2131 if (call_expr_flags (call
) & (ECF_PURE
| ECF_CONST
))
2136 /* Compute the AVAIL set for all basic blocks.
2138 This function performs value numbering of the statements in each basic
2139 block. The AVAIL sets are built from information we glean while doing
2140 this value numbering, since the AVAIL sets contain only one entry per
2143 AVAIL_IN[BLOCK] = AVAIL_OUT[dom(BLOCK)].
2144 AVAIL_OUT[BLOCK] = AVAIL_IN[BLOCK] U PHI_GEN[BLOCK] U TMP_GEN[BLOCK]. */
2147 compute_avail (void)
2149 basic_block block
, son
;
2150 basic_block
*worklist
;
2154 /* For arguments with default definitions, we pretend they are
2155 defined in the entry block. */
2156 for (param
= DECL_ARGUMENTS (current_function_decl
);
2158 param
= TREE_CHAIN (param
))
2160 if (default_def (param
) != NULL
)
2162 tree def
= default_def (param
);
2163 vn_lookup_or_add (def
, NULL
);
2164 bitmap_insert_into_set (TMP_GEN (ENTRY_BLOCK_PTR
), def
);
2165 bitmap_value_insert_into_set (AVAIL_OUT (ENTRY_BLOCK_PTR
), def
);
2169 /* Allocate the worklist. */
2170 worklist
= xmalloc (sizeof (basic_block
) * n_basic_blocks
);
2172 /* Seed the algorithm by putting the dominator children of the entry
2173 block on the worklist. */
2174 for (son
= first_dom_son (CDI_DOMINATORS
, ENTRY_BLOCK_PTR
);
2176 son
= next_dom_son (CDI_DOMINATORS
, son
))
2177 worklist
[sp
++] = son
;
2179 /* Loop until the worklist is empty. */
2182 block_stmt_iterator bsi
;
2186 /* Pick a block from the worklist. */
2187 block
= worklist
[--sp
];
2189 /* Initially, the set of available values in BLOCK is that of
2190 its immediate dominator. */
2191 dom
= get_immediate_dominator (CDI_DOMINATORS
, block
);
2193 bitmap_set_copy (AVAIL_OUT (block
), AVAIL_OUT (dom
));
2195 /* Generate values for PHI nodes. */
2196 for (phi
= phi_nodes (block
); phi
; phi
= PHI_CHAIN (phi
))
2197 /* We have no need for virtual phis, as they don't represent
2198 actual computations. */
2199 if (is_gimple_reg (PHI_RESULT (phi
)))
2200 add_to_sets (PHI_RESULT (phi
), PHI_RESULT (phi
), NULL
,
2201 PHI_GEN (block
), AVAIL_OUT (block
));
2203 /* Now compute value numbers and populate value sets with all
2204 the expressions computed in BLOCK. */
2205 for (bsi
= bsi_start (block
); !bsi_end_p (bsi
); bsi_next (&bsi
))
2211 stmt
= bsi_stmt (bsi
);
2212 ann
= stmt_ann (stmt
);
2214 /* We are only interested in assignments of the form
2215 X_i = EXPR, where EXPR represents an "interesting"
2216 computation, it has no volatile operands and X_i
2217 doesn't flow through an abnormal edge. */
2218 if (TREE_CODE (stmt
) == MODIFY_EXPR
2219 && !ann
->has_volatile_ops
2220 && TREE_CODE (TREE_OPERAND (stmt
, 0)) == SSA_NAME
2221 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (TREE_OPERAND (stmt
, 0)))
2223 tree lhs
= TREE_OPERAND (stmt
, 0);
2224 tree rhs
= TREE_OPERAND (stmt
, 1);
2226 STRIP_USELESS_TYPE_CONVERSION (rhs
);
2227 if (UNARY_CLASS_P (rhs
)
2228 || BINARY_CLASS_P (rhs
)
2229 || COMPARISON_CLASS_P (rhs
)
2230 || REFERENCE_CLASS_P (rhs
)
2231 || (TREE_CODE (rhs
) == CALL_EXPR
2232 && can_value_number_call (stmt
)))
2234 /* For binary, unary, and reference expressions,
2235 create a duplicate expression with the operands
2236 replaced with the value handles of the original
2238 tree newt
= create_value_expr_from (rhs
, block
, stmt
);
2241 add_to_sets (lhs
, newt
, stmt
, TMP_GEN (block
),
2243 value_insert_into_set (EXP_GEN (block
), newt
);
2247 else if (TREE_CODE (rhs
) == SSA_NAME
2248 || is_gimple_min_invariant (rhs
)
2249 || TREE_CODE (rhs
) == ADDR_EXPR
2250 || TREE_INVARIANT (rhs
)
2253 /* Compute a value number for the RHS of the statement
2254 and add its value to the AVAIL_OUT set for the block.
2255 Add the LHS to TMP_GEN. */
2256 add_to_sets (lhs
, rhs
, stmt
, TMP_GEN (block
),
2259 if (TREE_CODE (rhs
) == SSA_NAME
2260 && !is_undefined_value (rhs
))
2261 value_insert_into_set (EXP_GEN (block
), rhs
);
2266 /* For any other statement that we don't recognize, simply
2267 make the names generated by the statement available in
2268 AVAIL_OUT and TMP_GEN. */
2269 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, iter
, SSA_OP_DEF
)
2270 add_to_sets (op
, op
, NULL
, TMP_GEN (block
), AVAIL_OUT (block
));
2272 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, iter
, SSA_OP_USE
)
2273 add_to_sets (op
, op
, NULL
, NULL
, AVAIL_OUT (block
));
2276 /* Put the dominator children of BLOCK on the worklist of blocks
2277 to compute available sets for. */
2278 for (son
= first_dom_son (CDI_DOMINATORS
, block
);
2280 son
= next_dom_son (CDI_DOMINATORS
, son
))
2281 worklist
[sp
++] = son
;
2288 /* Eliminate fully redundant computations. */
2297 block_stmt_iterator i
;
2299 for (i
= bsi_start (b
); !bsi_end_p (i
); bsi_next (&i
))
2301 tree stmt
= bsi_stmt (i
);
2303 /* Lookup the RHS of the expression, see if we have an
2304 available computation for it. If so, replace the RHS with
2305 the available computation. */
2306 if (TREE_CODE (stmt
) == MODIFY_EXPR
2307 && TREE_CODE (TREE_OPERAND (stmt
, 0)) == SSA_NAME
2308 && TREE_CODE (TREE_OPERAND (stmt
,1)) != SSA_NAME
2309 && !is_gimple_min_invariant (TREE_OPERAND (stmt
, 1))
2310 && !stmt_ann (stmt
)->has_volatile_ops
)
2312 tree lhs
= TREE_OPERAND (stmt
, 0);
2313 tree
*rhs_p
= &TREE_OPERAND (stmt
, 1);
2316 sprime
= bitmap_find_leader (AVAIL_OUT (b
),
2317 vn_lookup (lhs
, NULL
));
2320 && (TREE_CODE (*rhs_p
) != SSA_NAME
2321 || may_propagate_copy (*rhs_p
, sprime
)))
2323 gcc_assert (sprime
!= *rhs_p
);
2325 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2327 fprintf (dump_file
, "Replaced ");
2328 print_generic_expr (dump_file
, *rhs_p
, 0);
2329 fprintf (dump_file
, " with ");
2330 print_generic_expr (dump_file
, sprime
, 0);
2331 fprintf (dump_file
, " in ");
2332 print_generic_stmt (dump_file
, stmt
, 0);
2334 if (TREE_CODE (sprime
) == SSA_NAME
)
2335 NECESSARY (SSA_NAME_DEF_STMT (sprime
)) = 1;
2336 pre_stats
.eliminations
++;
2337 propagate_tree_value (rhs_p
, sprime
);
2340 /* If we removed EH side effects from the statement, clean
2341 its EH information. */
2342 if (maybe_clean_or_replace_eh_stmt (stmt
, stmt
))
2344 bitmap_set_bit (need_eh_cleanup
,
2345 bb_for_stmt (stmt
)->index
);
2346 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2347 fprintf (dump_file
, " Removed EH side effects.\n");
2355 /* Borrow a bit of tree-ssa-dce.c for the moment.
2356 XXX: In 4.1, we should be able to just run a DCE pass after PRE, though
2357 this may be a bit faster, and we may want critical edges kept split. */
2359 /* If OP's defining statement has not already been determined to be necessary,
2360 mark that statement necessary. Return the stmt, if it is newly
2364 mark_operand_necessary (tree op
)
2370 stmt
= SSA_NAME_DEF_STMT (op
);
2373 if (NECESSARY (stmt
)
2374 || IS_EMPTY_STMT (stmt
))
2377 NECESSARY (stmt
) = 1;
2381 /* Because we don't follow exactly the standard PRE algorithm, and decide not
2382 to insert PHI nodes sometimes, and because value numbering of casts isn't
2383 perfect, we sometimes end up inserting dead code. This simple DCE-like
2384 pass removes any insertions we made that weren't actually used. */
2387 remove_dead_inserted_code (void)
2389 VEC(tree
,heap
) *worklist
= NULL
;
2393 worklist
= VEC_alloc (tree
, heap
, VEC_length (tree
, inserted_exprs
));
2394 for (i
= 0; VEC_iterate (tree
, inserted_exprs
, i
, t
); i
++)
2397 VEC_quick_push (tree
, worklist
, t
);
2399 while (VEC_length (tree
, worklist
) > 0)
2401 t
= VEC_pop (tree
, worklist
);
2402 if (TREE_CODE (t
) == PHI_NODE
)
2404 /* PHI nodes are somewhat special in that each PHI alternative has
2405 data and control dependencies. All the statements feeding the
2406 PHI node's arguments are always necessary. In aggressive mode,
2407 we also consider the control dependent edges leading to the
2408 predecessor block associated with each PHI alternative as
2412 VEC_reserve (tree
, heap
, worklist
, PHI_NUM_ARGS (t
));
2413 for (k
= 0; k
< PHI_NUM_ARGS (t
); k
++)
2415 tree arg
= PHI_ARG_DEF (t
, k
);
2416 if (TREE_CODE (arg
) == SSA_NAME
)
2418 arg
= mark_operand_necessary (arg
);
2420 VEC_quick_push (tree
, worklist
, arg
);
2426 /* Propagate through the operands. Examine all the USE, VUSE and
2427 V_MAY_DEF operands in this statement. Mark all the statements
2428 which feed this statement's uses as necessary. */
2432 /* The operands of V_MAY_DEF expressions are also needed as they
2433 represent potential definitions that may reach this
2434 statement (V_MAY_DEF operands allow us to follow def-def
2437 FOR_EACH_SSA_TREE_OPERAND (use
, t
, iter
, SSA_OP_ALL_USES
)
2439 tree n
= mark_operand_necessary (use
);
2441 VEC_safe_push (tree
, heap
, worklist
, n
);
2445 for (i
= 0; VEC_iterate (tree
, inserted_exprs
, i
, t
); i
++)
2449 block_stmt_iterator bsi
;
2450 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2452 fprintf (dump_file
, "Removing unnecessary insertion:");
2453 print_generic_stmt (dump_file
, t
, 0);
2455 if (TREE_CODE (t
) == PHI_NODE
)
2457 remove_phi_node (t
, NULL
);
2461 bsi
= bsi_for_stmt (t
);
2466 VEC_free (tree
, heap
, worklist
);
2468 /* Initialize data structures used by PRE. */
2471 init_pre (bool do_fre
)
2477 inserted_exprs
= NULL
;
2480 current_loops
= loop_optimizer_init (dump_file
);
2481 connect_infinite_loops_to_exit ();
2482 memset (&pre_stats
, 0, sizeof (pre_stats
));
2484 /* If block 0 has more than one predecessor, it means that its PHI
2485 nodes will have arguments coming from block -1. This creates
2486 problems for several places in PRE that keep local arrays indexed
2487 by block number. To prevent this, we split the edge coming from
2488 ENTRY_BLOCK_PTR (FIXME, if ENTRY_BLOCK_PTR had an index number
2489 different than -1 we wouldn't have to hack this. tree-ssa-dce.c
2490 needs a similar change). */
2491 if (!single_pred_p (single_succ (ENTRY_BLOCK_PTR
)))
2492 if (!(single_succ_edge (ENTRY_BLOCK_PTR
)->flags
& EDGE_ABNORMAL
))
2493 split_edge (single_succ_edge (ENTRY_BLOCK_PTR
));
2496 bb
->aux
= xcalloc (1, sizeof (struct bb_value_sets
));
2498 bitmap_obstack_initialize (&grand_bitmap_obstack
);
2499 phi_translate_table
= htab_create (511, expr_pred_trans_hash
,
2500 expr_pred_trans_eq
, free
);
2501 value_set_pool
= create_alloc_pool ("Value sets",
2502 sizeof (struct value_set
), 30);
2503 bitmap_set_pool
= create_alloc_pool ("Bitmap sets",
2504 sizeof (struct bitmap_set
), 30);
2505 value_set_node_pool
= create_alloc_pool ("Value set nodes",
2506 sizeof (struct value_set_node
), 30);
2507 calculate_dominance_info (CDI_POST_DOMINATORS
);
2508 calculate_dominance_info (CDI_DOMINATORS
);
2509 binary_node_pool
= create_alloc_pool ("Binary tree nodes",
2510 tree_code_size (PLUS_EXPR
), 30);
2511 unary_node_pool
= create_alloc_pool ("Unary tree nodes",
2512 tree_code_size (NEGATE_EXPR
), 30);
2513 reference_node_pool
= create_alloc_pool ("Reference tree nodes",
2514 tree_code_size (ARRAY_REF
), 30);
2515 expression_node_pool
= create_alloc_pool ("Expression tree nodes",
2516 tree_code_size (CALL_EXPR
), 30);
2517 list_node_pool
= create_alloc_pool ("List tree nodes",
2518 tree_code_size (TREE_LIST
), 30);
2519 comparison_node_pool
= create_alloc_pool ("Comparison tree nodes",
2520 tree_code_size (EQ_EXPR
), 30);
2523 EXP_GEN (bb
) = set_new (true);
2524 PHI_GEN (bb
) = bitmap_set_new ();
2525 TMP_GEN (bb
) = bitmap_set_new ();
2526 AVAIL_OUT (bb
) = bitmap_set_new ();
2529 need_eh_cleanup
= BITMAP_ALLOC (NULL
);
2533 /* Deallocate data structures used by PRE. */
2536 fini_pre (bool do_fre
)
2541 VEC_free (tree
, heap
, inserted_exprs
);
2542 bitmap_obstack_release (&grand_bitmap_obstack
);
2543 free_alloc_pool (value_set_pool
);
2544 free_alloc_pool (bitmap_set_pool
);
2545 free_alloc_pool (value_set_node_pool
);
2546 free_alloc_pool (binary_node_pool
);
2547 free_alloc_pool (reference_node_pool
);
2548 free_alloc_pool (unary_node_pool
);
2549 free_alloc_pool (list_node_pool
);
2550 free_alloc_pool (expression_node_pool
);
2551 free_alloc_pool (comparison_node_pool
);
2552 htab_delete (phi_translate_table
);
2553 remove_fake_exit_edges ();
2561 free_dominance_info (CDI_POST_DOMINATORS
);
2564 if (!bitmap_empty_p (need_eh_cleanup
))
2566 tree_purge_all_dead_eh_edges (need_eh_cleanup
);
2567 cleanup_tree_cfg ();
2570 BITMAP_FREE (need_eh_cleanup
);
2572 /* Wipe out pointers to VALUE_HANDLEs. In the not terribly distant
2573 future we will want them to be persistent though. */
2574 for (i
= 0; i
< num_ssa_names
; i
++)
2576 tree name
= ssa_name (i
);
2581 if (SSA_NAME_VALUE (name
)
2582 && TREE_CODE (SSA_NAME_VALUE (name
)) == VALUE_HANDLE
)
2583 SSA_NAME_VALUE (name
) = NULL
;
2585 if (!do_fre
&& current_loops
)
2587 loop_optimizer_finalize (current_loops
, dump_file
);
2588 current_loops
= NULL
;
2593 /* Main entry point to the SSA-PRE pass. DO_FRE is true if the caller
2594 only wants to do full redundancy elimination. */
2597 execute_pre (bool do_fre
)
2601 /* Collect and value number expressions computed in each basic block. */
2604 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2610 print_value_set (dump_file
, EXP_GEN (bb
), "exp_gen", bb
->index
);
2611 bitmap_print_value_set (dump_file
, TMP_GEN (bb
), "tmp_gen",
2613 bitmap_print_value_set (dump_file
, AVAIL_OUT (bb
), "avail_out",
2618 /* Insert can get quite slow on an incredibly large number of basic
2619 blocks due to some quadratic behavior. Until this behavior is
2620 fixed, don't run it when he have an incredibly large number of
2621 bb's. If we aren't going to run insert, there is no point in
2622 computing ANTIC, either, even though it's plenty fast. */
2623 if (!do_fre
&& n_basic_blocks
< 4000)
2629 /* Remove all the redundant expressions. */
2633 if (dump_file
&& (dump_flags
& TDF_STATS
))
2635 fprintf (dump_file
, "Insertions: %d\n", pre_stats
.insertions
);
2636 fprintf (dump_file
, "New PHIs: %d\n", pre_stats
.phis
);
2637 fprintf (dump_file
, "Eliminated: %d\n", pre_stats
.eliminations
);
2638 fprintf (dump_file
, "Constified: %d\n", pre_stats
.constified
);
2641 bsi_commit_edge_inserts ();
2643 remove_dead_inserted_code ();
2649 /* Gate and execute functions for PRE. */
2654 execute_pre (false);
2660 return flag_tree_pre
!= 0;
2663 struct tree_opt_pass pass_pre
=
2666 gate_pre
, /* gate */
2667 do_pre
, /* execute */
2670 0, /* static_pass_number */
2671 TV_TREE_PRE
, /* tv_id */
2672 PROP_no_crit_edges
| PROP_cfg
2673 | PROP_ssa
| PROP_alias
, /* properties_required */
2674 0, /* properties_provided */
2675 0, /* properties_destroyed */
2676 0, /* todo_flags_start */
2677 TODO_update_ssa
| TODO_dump_func
| TODO_ggc_collect
2678 | TODO_verify_ssa
, /* todo_flags_finish */
2683 /* Gate and execute functions for FRE. */
2694 return flag_tree_fre
!= 0;
2697 struct tree_opt_pass pass_fre
=
2700 gate_fre
, /* gate */
2701 execute_fre
, /* execute */
2704 0, /* static_pass_number */
2705 TV_TREE_FRE
, /* tv_id */
2706 PROP_cfg
| PROP_ssa
| PROP_alias
, /* properties_required */
2707 0, /* properties_provided */
2708 0, /* properties_destroyed */
2709 0, /* todo_flags_start */
2710 TODO_dump_func
| TODO_ggc_collect
| TODO_verify_ssa
, /* todo_flags_finish */