2 Copyright (C) 2001, 2002, 2003, 2004 Free Software Foundation, Inc.
3 Contributed by Daniel Berlin <dan@dberlin.org> and Steven Bosscher
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify
9 it under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 2, or (at your option)
13 GCC is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 GNU General Public License for more details.
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING. If not, write to
20 the Free Software Foundation, 59 Temple Place - Suite 330,
21 Boston, MA 02111-1307, USA. */
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"
44 #include "splay-tree.h"
46 #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. Our canonicalization of expressions during lookups don't take
60 constants into account very well. In particular, we don't fold
61 anywhere, so we can get situations where we stupidly think
62 something is a new value (a + 1 + 1 vs a + 2). This is somewhat
63 expensive to fix, but it does expose a lot more eliminations.
64 It may or not be worth it, depending on how critical you
65 consider PRE vs just plain GRE.
68 /* For ease of terminology, "expression node" in the below refers to
69 every expression node but MODIFY_EXPR, because MODIFY_EXPR's represent
70 the actual statement containing the expressions we care about, and
71 we cache the value number by putting it in the expression. */
75 First we walk the statements to generate the AVAIL sets, the
76 EXP_GEN sets, and the tmp_gen sets. EXP_GEN sets represent the
77 generation of values/expressions by a given block. We use them
78 when computing the ANTIC sets. The AVAIL sets consist of
79 SSA_NAME's that represent values, so we know what values are
80 available in what blocks. AVAIL is a forward dataflow problem. In
81 SSA, values are never killed, so we don't need a kill set, or a
82 fixpoint iteration, in order to calculate the AVAIL sets. In
83 traditional parlance, AVAIL sets tell us the downsafety of the
86 Next, we generate the ANTIC sets. These sets represent the
87 anticipatable expressions. ANTIC is a backwards dataflow
88 problem.An expression is anticipatable in a given block if it could
89 be generated in that block. This means that if we had to perform
90 an insertion in that block, of the value of that expression, we
91 could. Calculating the ANTIC sets requires phi translation of
92 expressions, because the flow goes backwards through phis. We must
93 iterate to a fixpoint of the ANTIC sets, because we have a kill
94 set. Even in SSA form, values are not live over the entire
95 function, only from their definition point onwards. So we have to
96 remove values from the ANTIC set once we go past the definition
97 point of the leaders that make them up.
98 compute_antic/compute_antic_aux performs this computation.
100 Third, we perform insertions to make partially redundant
101 expressions fully redundant.
103 An expression is partially redundant (excluding partial
106 1. It is AVAIL in some, but not all, of the predecessors of a
108 2. It is ANTIC in all the predecessors.
110 In order to make it fully redundant, we insert the expression into
111 the predecessors where it is not available, but is ANTIC.
112 insert/insert_aux performs this insertion.
114 Fourth, we eliminate fully redundant expressions.
115 This is a simple statement walk that replaces redundant
116 calculations with the now available values. */
118 /* Representations of value numbers:
120 Value numbers are represented using the "value handle" approach.
121 This means that each SSA_NAME (and for other reasons to be
122 disclosed in a moment, expression nodes) has a value handle that
123 can be retrieved through get_value_handle. This value handle, *is*
124 the value number of the SSA_NAME. You can pointer compare the
125 value handles for equivalence purposes.
127 For debugging reasons, the value handle is internally more than
128 just a number, it is a VAR_DECL named "value.x", where x is a
129 unique number for each value number in use. This allows
130 expressions with SSA_NAMES replaced by value handles to still be
131 pretty printed in a sane way. They simply print as "value.3 *
134 Expression nodes have value handles associated with them as a
135 cache. Otherwise, we'd have to look them up again in the hash
136 table This makes significant difference (factor of two or more) on
137 some test cases. They can be thrown away after the pass is
140 /* Representation of expressions on value numbers:
142 In some portions of this code, you will notice we allocate "fake"
143 analogues to the expression we are value numbering, and replace the
144 operands with the values of the expression. Since we work on
145 values, and not just names, we canonicalize expressions to value
146 expressions for use in the ANTIC sets, the EXP_GEN set, etc.
148 This is theoretically unnecessary, it just saves a bunch of
149 repeated get_value_handle and find_leader calls in the remainder of
150 the code, trading off temporary memory usage for speed. The tree
151 nodes aren't actually creating more garbage, since they are
152 allocated in a special pools which are thrown away at the end of
155 All of this also means that if you print the EXP_GEN or ANTIC sets,
156 you will see "value.5 + value.7" in the set, instead of "a_55 +
157 b_66" or something. The only thing that actually cares about
158 seeing the value leaders is phi translation, and it needs to be
159 able to find the leader for a value in an arbitrary block, so this
160 "value expression" form is perfect for it (otherwise you'd do
161 get_value_handle->find_leader->translate->get_value_handle->find_leader).*/
164 /* Representation of sets:
166 There are currently two types of sets used, hopefully to be unified soon.
167 The AVAIL sets do not need to be sorted in any particular order,
168 and thus, are simply represented as two bitmaps, one that keeps
169 track of values present in the set, and one that keeps track of
170 expressions present in the set.
172 The other sets are represented as doubly linked lists kept in topological
173 order, with an optional supporting bitmap of values present in the
174 set. The sets represent values, and the elements can be values or
175 expressions. The elements can appear in different sets, but each
176 element can only appear once in each set.
178 Since each node in the set represents a value, we also want to be
179 able to map expression, set pairs to something that tells us
180 whether the value is present is a set. We use a per-set bitmap for
181 that. The value handles also point to a linked list of the
182 expressions they represent via a tree annotation. This is mainly
183 useful only for debugging, since we don't do identity lookups. */
186 /* A value set element. Basically a single linked list of
187 expressions/values. */
188 typedef struct value_set_node
193 /* A pointer to the next element of the value set. */
194 struct value_set_node
*next
;
198 /* A value set. This is a singly linked list of value_set_node
199 elements with a possible bitmap that tells us what values exist in
200 the set. This set must be kept in topologically sorted order. */
201 typedef struct value_set
203 /* The head of the list. Used for iterating over the list in
205 value_set_node_t head
;
207 /* The tail of the list. Used for tail insertions, which are
208 necessary to keep the set in topologically sorted order because
209 of how the set is built. */
210 value_set_node_t tail
;
212 /* The length of the list. */
215 /* True if the set is indexed, which means it contains a backing
216 bitmap for quick determination of whether certain values exist in the
220 /* The bitmap of values that exist in the set. May be NULL in an
221 empty or non-indexed set. */
227 /* An unordered bitmap set. One bitmap tracks values, the other,
229 typedef struct bitmap_set
235 /* Sets that we need to keep track of. */
236 typedef struct bb_value_sets
238 /* The EXP_GEN set, which represents expressions/values generated in
242 /* The PHI_GEN set, which represents PHI results generated in a
244 bitmap_set_t phi_gen
;
246 /* The TMP_GEN set, which represents results/temporaries generated
247 in a basic block. IE the LHS of an expression. */
248 bitmap_set_t tmp_gen
;
250 /* The AVAIL_OUT set, which represents which values are available in
251 a given basic block. */
252 bitmap_set_t avail_out
;
254 /* The ANTIC_IN set, which represents which values are anticiptable
255 in a given basic block. */
256 value_set_t antic_in
;
258 /* The NEW_SETS set, which is used during insertion to augment the
259 AVAIL_OUT set of blocks with the new insertions performed during
260 the current iteration. */
261 bitmap_set_t new_sets
;
264 #define EXP_GEN(BB) ((bb_value_sets_t) ((BB)->aux))->exp_gen
265 #define PHI_GEN(BB) ((bb_value_sets_t) ((BB)->aux))->phi_gen
266 #define TMP_GEN(BB) ((bb_value_sets_t) ((BB)->aux))->tmp_gen
267 #define AVAIL_OUT(BB) ((bb_value_sets_t) ((BB)->aux))->avail_out
268 #define ANTIC_IN(BB) ((bb_value_sets_t) ((BB)->aux))->antic_in
269 #define NEW_SETS(BB) ((bb_value_sets_t) ((BB)->aux))->new_sets
271 /* This structure is used to keep track of statistics on what
272 optimization PRE was able to perform. */
275 /* The number of RHS computations eliminated by PRE. */
278 /* The number of new expressions/temporaries generated by PRE. */
281 /* The number of new PHI nodes added by PRE. */
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 struct obstack grand_bitmap_obstack
;
311 /* Set of blocks with statements that have had its EH information
313 static bitmap need_eh_cleanup
;
315 /* The phi_translate_table caches phi translations for a given
316 expression and predecessor. */
318 static htab_t phi_translate_table
;
320 /* A three tuple {e, pred, v} used to cache phi translations in the
321 phi_translate_table. */
323 typedef struct expr_pred_trans_d
325 /* The expression. */
328 /* The predecessor block along which we translated the expression. */
331 /* The value that resulted from the translation. */
334 /* The hashcode for the expression, pred pair. This is cached for
337 } *expr_pred_trans_t
;
339 /* Return the hash value for a phi translation table entry. */
342 expr_pred_trans_hash (const void *p
)
344 const expr_pred_trans_t ve
= (expr_pred_trans_t
) p
;
348 /* Return true if two phi translation table entries are the same.
349 P1 and P2 should point to the expr_pred_trans_t's to be compared.*/
352 expr_pred_trans_eq (const void *p1
, const void *p2
)
354 const expr_pred_trans_t ve1
= (expr_pred_trans_t
) p1
;
355 const expr_pred_trans_t ve2
= (expr_pred_trans_t
) p2
;
356 basic_block b1
= ve1
->pred
;
357 basic_block b2
= ve2
->pred
;
360 /* If they are not translations for the same basic block, they can't
365 /* If they are for the same basic block, determine if the
366 expressions are equal. */
367 if (expressions_equal_p (ve1
->e
, ve2
->e
))
373 /* Search in the phi translation table for the translation of
374 expression E in basic block PRED. Return the translated value, if
375 found, NULL otherwise. */
378 phi_trans_lookup (tree e
, basic_block pred
)
381 struct expr_pred_trans_d ept
;
384 ept
.hashcode
= vn_compute (e
, (unsigned long) pred
, NULL
);
385 slot
= htab_find_slot_with_hash (phi_translate_table
, &ept
, ept
.hashcode
,
390 return ((expr_pred_trans_t
) *slot
)->v
;
394 /* Add the tuple mapping from {expression E, basic block PRED} to
395 value V, to the phi translation table. */
398 phi_trans_add (tree e
, tree v
, basic_block pred
)
401 expr_pred_trans_t new_pair
= xmalloc (sizeof (*new_pair
));
403 new_pair
->pred
= pred
;
405 new_pair
->hashcode
= vn_compute (e
, (unsigned long) pred
, NULL
);
406 slot
= htab_find_slot_with_hash (phi_translate_table
, new_pair
,
407 new_pair
->hashcode
, INSERT
);
410 *slot
= (void *) new_pair
;
414 /* Add expression E to the expression set of value V. */
417 add_to_value (tree v
, tree e
)
419 /* Constants have no expression sets. */
420 if (is_gimple_min_invariant (v
))
423 if (VALUE_HANDLE_EXPR_SET (v
) == NULL
)
424 VALUE_HANDLE_EXPR_SET (v
) = set_new (false);
426 insert_into_set (VALUE_HANDLE_EXPR_SET (v
), e
);
430 /* Return true if value V exists in the bitmap for SET. */
433 value_exists_in_set_bitmap (value_set_t set
, tree v
)
438 return bitmap_bit_p (set
->values
, VALUE_HANDLE_ID (v
));
442 /* Remove value V from the bitmap for SET. */
445 value_remove_from_set_bitmap (value_set_t set
, tree v
)
447 gcc_assert (set
->indexed
);
452 bitmap_clear_bit (set
->values
, VALUE_HANDLE_ID (v
));
456 /* Insert the value number V into the bitmap of values existing in
460 value_insert_into_set_bitmap (value_set_t set
, tree v
)
462 gcc_assert (set
->indexed
);
464 if (set
->values
== NULL
)
466 set
->values
= BITMAP_OBSTACK_ALLOC (&grand_bitmap_obstack
);
467 bitmap_clear (set
->values
);
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_OBSTACK_ALLOC (&grand_bitmap_obstack
);
481 ret
->values
= BITMAP_OBSTACK_ALLOC (&grand_bitmap_obstack
);
482 bitmap_clear (ret
->expressions
);
483 bitmap_clear (ret
->values
);
487 /* Create a new set. */
490 set_new (bool indexed
)
493 ret
= pool_alloc (value_set_pool
);
494 ret
->head
= ret
->tail
= NULL
;
496 ret
->indexed
= indexed
;
501 /* Insert an expression EXPR into a bitmapped set. */
504 bitmap_insert_into_set (bitmap_set_t set
, tree expr
)
507 /* XXX: For now, we only let SSA_NAMES into the bitmap sets. */
508 gcc_assert (TREE_CODE (expr
) == SSA_NAME
);
509 val
= get_value_handle (expr
);
512 if (!is_gimple_min_invariant (val
))
514 bitmap_set_bit (set
->values
, VALUE_HANDLE_ID (val
));
515 bitmap_set_bit (set
->expressions
, SSA_NAME_VERSION (expr
));
519 /* Insert EXPR into SET. */
522 insert_into_set (value_set_t set
, tree expr
)
524 value_set_node_t newnode
= pool_alloc (value_set_node_pool
);
525 tree val
= get_value_handle (expr
);
528 if (is_gimple_min_invariant (val
))
531 /* For indexed sets, insert the value into the set value bitmap.
532 For all sets, add it to the linked list and increment the list
535 value_insert_into_set_bitmap (set
, val
);
537 newnode
->next
= NULL
;
538 newnode
->expr
= expr
;
540 if (set
->head
== NULL
)
542 set
->head
= set
->tail
= newnode
;
546 set
->tail
->next
= newnode
;
551 /* Copy a bitmapped set ORIG, into bitmapped set DEST. */
554 bitmap_set_copy (bitmap_set_t dest
, bitmap_set_t orig
)
556 bitmap_copy (dest
->expressions
, orig
->expressions
);
557 bitmap_copy (dest
->values
, orig
->values
);
560 /* Copy the set ORIG to the set DEST. */
563 set_copy (value_set_t dest
, value_set_t orig
)
565 value_set_node_t node
;
567 if (!orig
|| !orig
->head
)
570 for (node
= orig
->head
;
574 insert_into_set (dest
, node
->expr
);
578 /* Remove EXPR from SET. */
581 set_remove (value_set_t set
, tree expr
)
583 value_set_node_t node
, prev
;
585 /* Remove the value of EXPR from the bitmap, decrement the set
586 length, and remove it from the actual double linked list. */
587 value_remove_from_set_bitmap (set
, get_value_handle (expr
));
590 for (node
= set
->head
;
592 prev
= node
, node
= node
->next
)
594 if (node
->expr
== expr
)
597 set
->head
= node
->next
;
599 prev
->next
= node
->next
;
601 if (node
== set
->tail
)
603 pool_free (value_set_node_pool
, node
);
609 /* Return true if SET contains the value VAL. */
612 set_contains_value (value_set_t set
, tree val
)
614 /* All constants are in every set. */
615 if (is_gimple_min_invariant (val
))
618 if (set
->length
== 0)
621 return value_exists_in_set_bitmap (set
, val
);
624 /* Return true if bitmapped set SET contains the expression EXPR. */
626 bitmap_set_contains (bitmap_set_t set
, tree expr
)
628 /* All constants are in every set. */
629 if (is_gimple_min_invariant (get_value_handle (expr
)))
632 /* XXX: Bitmapped sets only contain SSA_NAME's for now. */
633 if (TREE_CODE (expr
) != SSA_NAME
)
635 return bitmap_bit_p (set
->expressions
, SSA_NAME_VERSION (expr
));
639 /* Return true if bitmapped set SET contains the value VAL. */
642 bitmap_set_contains_value (bitmap_set_t set
, tree val
)
644 if (is_gimple_min_invariant (val
))
646 return bitmap_bit_p (set
->values
, VALUE_HANDLE_ID (val
));
649 /* Replace an instance of value LOOKFOR with expression EXPR in SET. */
652 bitmap_set_replace_value (bitmap_set_t set
, tree lookfor
, tree expr
)
655 value_set_node_t node
;
656 if (is_gimple_min_invariant (lookfor
))
658 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. */
724 bitmap_value_replace_in_set (bitmap_set_t set
, tree expr
)
726 tree val
= get_value_handle (expr
);
727 bitmap_set_replace_value (set
, val
, expr
);
730 /* Insert EXPR into SET if EXPR's value is not already present in
734 bitmap_value_insert_into_set (bitmap_set_t set
, tree expr
)
736 tree val
= get_value_handle (expr
);
738 if (is_gimple_min_invariant (val
))
741 if (!bitmap_set_contains_value (set
, val
))
742 bitmap_insert_into_set (set
, expr
);
745 /* Insert the value for EXPR into SET, if it doesn't exist already. */
748 value_insert_into_set (value_set_t set
, tree expr
)
750 tree val
= get_value_handle (expr
);
752 /* Constant and invariant values exist everywhere, and thus,
753 actually keeping them in the sets is pointless. */
754 if (is_gimple_min_invariant (val
))
757 if (!set_contains_value (set
, val
))
758 insert_into_set (set
, expr
);
762 /* Print out SET to OUTFILE. */
765 bitmap_print_value_set (FILE *outfile
, bitmap_set_t set
,
766 const char *setname
, int blockindex
)
768 fprintf (outfile
, "%s[%d] := { ", setname
, blockindex
);
775 EXECUTE_IF_SET_IN_BITMAP (set
->expressions
, 0, i
, bi
)
778 fprintf (outfile
, ", ");
780 print_generic_expr (outfile
, ssa_name (i
), 0);
782 fprintf (outfile
, " (");
783 print_generic_expr (outfile
, get_value_handle (ssa_name (i
)), 0);
784 fprintf (outfile
, ") ");
787 fprintf (outfile
, " }\n");
789 /* Print out the value_set SET to OUTFILE. */
792 print_value_set (FILE *outfile
, value_set_t set
,
793 const char *setname
, int blockindex
)
795 value_set_node_t node
;
796 fprintf (outfile
, "%s[%d] := { ", setname
, blockindex
);
799 for (node
= set
->head
;
803 print_generic_expr (outfile
, node
->expr
, 0);
805 fprintf (outfile
, " (");
806 print_generic_expr (outfile
, get_value_handle (node
->expr
), 0);
807 fprintf (outfile
, ") ");
810 fprintf (outfile
, ", ");
814 fprintf (outfile
, " }\n");
817 /* Print out the expressions that have VAL to OUTFILE. */
820 print_value_expressions (FILE *outfile
, tree val
)
822 if (VALUE_HANDLE_EXPR_SET (val
))
825 sprintf (s
, "VH.%04d", VALUE_HANDLE_ID (val
));
826 print_value_set (outfile
, VALUE_HANDLE_EXPR_SET (val
), s
, 0);
832 debug_value_expressions (tree val
)
834 print_value_expressions (stderr
, val
);
838 void debug_value_set (value_set_t
, const char *, int);
841 debug_value_set (value_set_t set
, const char *setname
, int blockindex
)
843 print_value_set (stderr
, set
, setname
, blockindex
);
846 /* Translate EXPR using phis in PHIBLOCK, so that it has the values of
847 the phis in PRED. Return NULL if we can't find a leader for each
848 part of the translated expression. */
851 phi_translate (tree expr
, value_set_t set
, basic_block pred
,
852 basic_block phiblock
)
854 tree phitrans
= NULL
;
860 if (is_gimple_min_invariant (expr
))
863 /* Phi translations of a given expression don't change. */
864 phitrans
= phi_trans_lookup (expr
, pred
);
868 switch (TREE_CODE_CLASS (TREE_CODE (expr
)))
871 /* XXX: Until we have PRE of loads working, none will be ANTIC. */
876 tree oldop1
= TREE_OPERAND (expr
, 0);
877 tree oldop2
= TREE_OPERAND (expr
, 1);
882 newop1
= phi_translate (find_leader (set
, oldop1
),
883 set
, pred
, phiblock
);
886 newop2
= phi_translate (find_leader (set
, oldop2
),
887 set
, pred
, phiblock
);
890 if (newop1
!= oldop1
|| newop2
!= oldop2
)
892 newexpr
= pool_alloc (binary_node_pool
);
893 memcpy (newexpr
, expr
, tree_size (expr
));
894 create_tree_ann (newexpr
);
895 TREE_OPERAND (newexpr
, 0) = newop1
== oldop1
? oldop1
: get_value_handle (newop1
);
896 TREE_OPERAND (newexpr
, 1) = newop2
== oldop2
? oldop2
: get_value_handle (newop2
);
897 vn_lookup_or_add (newexpr
, NULL
);
899 phi_trans_add (oldexpr
, newexpr
, pred
);
906 tree oldop1
= TREE_OPERAND (expr
, 0);
910 newop1
= phi_translate (find_leader (set
, oldop1
),
911 set
, pred
, phiblock
);
914 if (newop1
!= oldop1
)
916 newexpr
= pool_alloc (unary_node_pool
);
917 memcpy (newexpr
, expr
, tree_size (expr
));
918 create_tree_ann (newexpr
);
919 TREE_OPERAND (newexpr
, 0) = get_value_handle (newop1
);
920 vn_lookup_or_add (newexpr
, NULL
);
922 phi_trans_add (oldexpr
, newexpr
, pred
);
927 case tcc_exceptional
:
931 gcc_assert (TREE_CODE (expr
) == SSA_NAME
);
932 if (TREE_CODE (SSA_NAME_DEF_STMT (expr
)) == PHI_NODE
)
933 phi
= SSA_NAME_DEF_STMT (expr
);
937 for (i
= 0; i
< PHI_NUM_ARGS (phi
); i
++)
938 if (PHI_ARG_EDGE (phi
, i
)->src
== pred
)
941 if (is_undefined_value (PHI_ARG_DEF (phi
, i
)))
943 val
= vn_lookup_or_add (PHI_ARG_DEF (phi
, i
), NULL
);
944 return PHI_ARG_DEF (phi
, i
);
955 phi_translate_set (value_set_t dest
, value_set_t set
, basic_block pred
,
956 basic_block phiblock
)
958 value_set_node_t node
;
959 for (node
= set
->head
;
964 translated
= phi_translate (node
->expr
, set
, pred
, phiblock
);
965 phi_trans_add (node
->expr
, translated
, pred
);
967 if (translated
!= NULL
)
968 value_insert_into_set (dest
, translated
);
972 /* Find the leader for a value (i.e., the name representing that
973 value) in a given set, and return it. Return NULL if no leader is
977 bitmap_find_leader (bitmap_set_t set
, tree val
)
982 if (is_gimple_min_invariant (val
))
984 if (bitmap_set_contains_value (set
, val
))
986 /* Rather than walk the entire bitmap of expressions, and see
987 whether any of them has the value we are looking for, we look
988 at the reverse mapping, which tells us the set of expressions
989 that have a given value (IE value->expressions with that
990 value) and see if any of those expressions are in our set.
991 The number of expressions per value is usually significantly
992 less than the number of expressions in the set. In fact, for
993 large testcases, doing it this way is roughly 5-10x faster
994 than walking the bitmap.
995 If this is somehow a significant lose for some cases, we can
996 choose which set to walk based on which set is smaller. */
998 value_set_node_t node
;
999 exprset
= VALUE_HANDLE_EXPR_SET (val
);
1000 for (node
= exprset
->head
; node
; node
= node
->next
)
1002 if (TREE_CODE (node
->expr
) == SSA_NAME
)
1004 if (bitmap_bit_p (set
->expressions
,
1005 SSA_NAME_VERSION (node
->expr
)))
1014 /* Find the leader for a value (i.e., the name representing that
1015 value) in a given set, and return it. Return NULL if no leader is
1019 find_leader (value_set_t set
, tree val
)
1021 value_set_node_t node
;
1026 /* Constants represent themselves. */
1027 if (is_gimple_min_invariant (val
))
1030 if (set
->length
== 0)
1033 if (value_exists_in_set_bitmap (set
, val
))
1035 for (node
= set
->head
;
1039 if (get_value_handle (node
->expr
) == val
)
1047 /* Determine if the expression EXPR is valid in SET. This means that
1048 we have a leader for each part of the expression (if it consists of
1049 values), or the expression is an SSA_NAME.
1051 NB: We never should run into a case where we have SSA_NAME +
1052 SSA_NAME or SSA_NAME + value. The sets valid_in_set is called on,
1053 the ANTIC sets, will only ever have SSA_NAME's or binary value
1054 expression (IE VALUE1 + VALUE2) */
1057 valid_in_set (value_set_t set
, tree expr
)
1059 switch (TREE_CODE_CLASS (TREE_CODE (expr
)))
1063 tree op1
= TREE_OPERAND (expr
, 0);
1064 tree op2
= TREE_OPERAND (expr
, 1);
1065 return set_contains_value (set
, op1
) && set_contains_value (set
, op2
);
1070 tree op1
= TREE_OPERAND (expr
, 0);
1071 return set_contains_value (set
, op1
);
1075 /* XXX: Until PRE of loads works, no reference nodes are ANTIC. */
1078 case tcc_exceptional
:
1079 gcc_assert (TREE_CODE (expr
) == SSA_NAME
);
1083 /* No other cases should be encountered. */
1088 /* Clean the set of expressions that are no longer valid in SET. This
1089 means expressions that are made up of values we have no leaders for
1093 clean (value_set_t set
)
1095 value_set_node_t node
;
1096 value_set_node_t next
;
1101 if (!valid_in_set (set
, node
->expr
))
1102 set_remove (set
, node
->expr
);
1107 DEF_VEC_MALLOC_P (basic_block
);
1109 /* Compute the ANTIC set for BLOCK.
1111 ANTIC_OUT[BLOCK] = intersection of ANTIC_IN[b] for all succ(BLOCK), if
1113 ANTIC_OUT[BLOCK] = phi_translate (ANTIC_IN[succ(BLOCK)]) if
1116 ANTIC_IN[BLOCK] = clean(ANTIC_OUT[BLOCK] U EXP_GEN[BLOCK] -
1119 Iterate until fixpointed.
1121 XXX: It would be nice to either write a set_clear, and use it for
1122 antic_out, or to mark the antic_out set as deleted at the end
1123 of this routine, so that the pool can hand the same memory back out
1124 again for the next antic_out. */
1128 compute_antic_aux (basic_block block
)
1132 bool changed
= false;
1133 value_set_t S
, old
, ANTIC_OUT
;
1134 value_set_node_t node
;
1136 ANTIC_OUT
= S
= NULL
;
1137 /* If any edges from predecessors are abnormal, antic_in is empty, so
1138 punt. Remember that the block has an incoming abnormal edge by
1139 setting the BB_VISITED flag. */
1140 if (! (block
->flags
& BB_VISITED
))
1143 FOR_EACH_EDGE (e
, ei
, block
->preds
)
1144 if (e
->flags
& EDGE_ABNORMAL
)
1146 block
->flags
|= BB_VISITED
;
1150 if (block
->flags
& BB_VISITED
)
1157 old
= set_new (false);
1158 set_copy (old
, ANTIC_IN (block
));
1159 ANTIC_OUT
= set_new (true);
1161 /* If the block has no successors, ANTIC_OUT is empty, because it is
1163 if (EDGE_COUNT (block
->succs
) == 0);
1165 /* If we have one successor, we could have some phi nodes to
1166 translate through. */
1167 else if (EDGE_COUNT (block
->succs
) == 1)
1169 phi_translate_set (ANTIC_OUT
, ANTIC_IN(EDGE_SUCC (block
, 0)->dest
),
1170 block
, EDGE_SUCC (block
, 0)->dest
);
1172 /* If we have multiple successors, we take the intersection of all of
1176 VEC (basic_block
) * worklist
;
1179 basic_block bprime
, first
;
1182 worklist
= VEC_alloc (basic_block
, 2);
1183 FOR_EACH_EDGE (e
, ei
, block
->succs
)
1184 VEC_safe_push (basic_block
, worklist
, e
->dest
);
1185 first
= VEC_index (basic_block
, worklist
, 0);
1186 set_copy (ANTIC_OUT
, ANTIC_IN (first
));
1188 for (i
= 1; VEC_iterate (basic_block
, worklist
, i
, bprime
); i
++)
1190 node
= ANTIC_OUT
->head
;
1194 value_set_node_t next
= node
->next
;
1195 val
= get_value_handle (node
->expr
);
1196 if (!set_contains_value (ANTIC_IN (bprime
), val
))
1197 set_remove (ANTIC_OUT
, node
->expr
);
1201 VEC_free (basic_block
, worklist
);
1204 /* Generate ANTIC_OUT - TMP_GEN. */
1205 S
= bitmap_set_subtract_from_value_set (ANTIC_OUT
, TMP_GEN (block
), false);
1207 /* Start ANTIC_IN with EXP_GEN - TMP_GEN */
1208 ANTIC_IN (block
) = bitmap_set_subtract_from_value_set (EXP_GEN (block
),
1212 /* Then union in the ANTIC_OUT - TMP_GEN values, to get ANTIC_OUT U
1213 EXP_GEN - TMP_GEN */
1214 for (node
= S
->head
;
1218 value_insert_into_set (ANTIC_IN (block
), node
->expr
);
1220 clean (ANTIC_IN (block
));
1223 if (!set_equal (old
, ANTIC_IN (block
)))
1227 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1230 print_value_set (dump_file
, ANTIC_OUT
, "ANTIC_OUT", block
->index
);
1231 print_value_set (dump_file
, ANTIC_IN (block
), "ANTIC_IN", block
->index
);
1233 print_value_set (dump_file
, S
, "S", block
->index
);
1237 for (son
= first_dom_son (CDI_POST_DOMINATORS
, block
);
1239 son
= next_dom_son (CDI_POST_DOMINATORS
, son
))
1241 changed
|= compute_antic_aux (son
);
1246 /* Compute ANTIC sets. */
1249 compute_antic (void)
1251 bool changed
= true;
1253 int num_iterations
= 0;
1256 ANTIC_IN (bb
) = set_new (true);
1257 gcc_assert (!(bb
->flags
& BB_VISITED
));
1264 changed
= compute_antic_aux (EXIT_BLOCK_PTR
);
1268 bb
->flags
&= ~BB_VISITED
;
1270 if (num_iterations
> 2 && dump_file
&& (dump_flags
& TDF_STATS
))
1271 fprintf (dump_file
, "compute_antic required %d iterations\n", num_iterations
);
1275 /* Find a leader for an expression, or generate one using
1276 create_expression_by_pieces if it's ANTIC but
1278 BLOCK is the basic_block we are looking for leaders in.
1279 EXPR is the expression to find a leader or generate for.
1280 STMTS is the statement list to put the inserted expressions on.
1281 Returns the SSA_NAME of the LHS of the generated expression or the
1285 find_or_generate_expression (basic_block block
, tree expr
, tree stmts
)
1288 genop
= bitmap_find_leader (AVAIL_OUT (block
), expr
);
1289 /* Depending on the order we process DOM branches in, the value
1290 may not have propagated to all the dom children yet during
1291 this iteration. In this case, the value will always be in
1292 the NEW_SETS for us already, having been propagated from our
1295 genop
= bitmap_find_leader (NEW_SETS (block
), expr
);
1296 /* If it's still NULL, see if it is a complex expression, and if
1297 so, generate it recursively, otherwise, abort, because it's
1301 genop
= VALUE_HANDLE_EXPR_SET (expr
)->head
->expr
;
1302 gcc_assert (UNARY_CLASS_P (genop
)
1303 || BINARY_CLASS_P (genop
)
1304 || REFERENCE_CLASS_P (genop
));
1305 genop
= create_expression_by_pieces (block
, genop
, stmts
);
1311 /* Create an expression in pieces, so that we can handle very complex
1312 expressions that may be ANTIC, but not necessary GIMPLE.
1313 BLOCK is the basic block the expression will be inserted into,
1314 EXPR is the expression to insert (in value form)
1315 STMTS is a statement list to append the necessary insertions into.
1317 This function will abort if we hit some value that shouldn't be
1318 ANTIC but is (IE there is no leader for it, or its components).
1319 This function may also generate expressions that are themselves
1320 partially or fully redundant. Those that are will be either made
1321 fully redundant during the next iteration of insert (for partially
1322 redundant ones), or eliminated by eliminate (for fully redundant
1326 create_expression_by_pieces (basic_block block
, tree expr
, tree stmts
)
1328 tree name
= NULL_TREE
;
1329 tree newexpr
= NULL_TREE
;
1332 switch (TREE_CODE_CLASS (TREE_CODE (expr
)))
1336 tree_stmt_iterator tsi
;
1337 tree genop1
, genop2
;
1339 tree op1
= TREE_OPERAND (expr
, 0);
1340 tree op2
= TREE_OPERAND (expr
, 1);
1341 genop1
= find_or_generate_expression (block
, op1
, stmts
);
1342 genop2
= find_or_generate_expression (block
, op2
, stmts
);
1343 temp
= create_tmp_var (TREE_TYPE (expr
), "pretmp");
1344 add_referenced_tmp_var (temp
);
1345 newexpr
= build (TREE_CODE (expr
), TREE_TYPE (expr
),
1347 newexpr
= build (MODIFY_EXPR
, TREE_TYPE (expr
),
1349 name
= make_ssa_name (temp
, newexpr
);
1350 TREE_OPERAND (newexpr
, 0) = name
;
1351 tsi
= tsi_last (stmts
);
1352 tsi_link_after (&tsi
, newexpr
, TSI_CONTINUE_LINKING
);
1353 pre_stats
.insertions
++;
1358 tree_stmt_iterator tsi
;
1361 tree op1
= TREE_OPERAND (expr
, 0);
1362 genop1
= find_or_generate_expression (block
, op1
, stmts
);
1363 temp
= create_tmp_var (TREE_TYPE (expr
), "pretmp");
1364 add_referenced_tmp_var (temp
);
1365 newexpr
= build (TREE_CODE (expr
), TREE_TYPE (expr
),
1367 newexpr
= build (MODIFY_EXPR
, TREE_TYPE (expr
),
1369 name
= make_ssa_name (temp
, newexpr
);
1370 TREE_OPERAND (newexpr
, 0) = name
;
1371 tsi
= tsi_last (stmts
);
1372 tsi_link_after (&tsi
, newexpr
, TSI_CONTINUE_LINKING
);
1373 pre_stats
.insertions
++;
1381 v
= get_value_handle (expr
);
1382 vn_add (name
, v
, NULL
);
1383 bitmap_insert_into_set (NEW_SETS (block
), name
);
1384 bitmap_value_insert_into_set (AVAIL_OUT (block
), name
);
1385 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1387 fprintf (dump_file
, "Inserted ");
1388 print_generic_expr (dump_file
, newexpr
, 0);
1389 fprintf (dump_file
, " in predecessor %d\n", block
->index
);
1394 /* Perform insertion of partially redundant values.
1395 For BLOCK, do the following:
1396 1. Propagate the NEW_SETS of the dominator into the current block.
1397 If the block has multiple predecessors,
1398 2a. Iterate over the ANTIC expressions for the block to see if
1399 any of them are partially redundant.
1400 2b. If so, insert them into the necessary predecessors to make
1401 the expression fully redundant.
1402 2c. Insert a new PHI merging the values of the predecessors.
1403 2d. Insert the new PHI, and the new expressions, into the
1405 3. Recursively call ourselves on the dominator children of BLOCK.
1409 insert_aux (basic_block block
)
1412 bool new_stuff
= false;
1417 dom
= get_immediate_dominator (CDI_DOMINATORS
, block
);
1423 bitmap_set_t newset
= NEW_SETS (dom
);
1424 EXECUTE_IF_SET_IN_BITMAP (newset
->expressions
, 0, i
, bi
)
1426 bitmap_insert_into_set (NEW_SETS (block
), ssa_name (i
));
1427 bitmap_value_replace_in_set (AVAIL_OUT (block
), ssa_name (i
));
1429 if (EDGE_COUNT (block
->preds
) > 1)
1431 value_set_node_t node
;
1432 for (node
= ANTIC_IN (block
)->head
;
1436 if (BINARY_CLASS_P (node
->expr
)
1437 || UNARY_CLASS_P (node
->expr
))
1441 bool by_some
= false;
1442 bool cant_insert
= false;
1443 bool all_same
= true;
1444 tree first_s
= NULL
;
1450 val
= get_value_handle (node
->expr
);
1451 if (bitmap_set_contains_value (PHI_GEN (block
), val
))
1453 if (bitmap_set_contains_value (AVAIL_OUT (dom
), val
))
1455 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1456 fprintf (dump_file
, "Found fully redundant value\n");
1460 avail
= xcalloc (last_basic_block
, sizeof (tree
));
1461 FOR_EACH_EDGE (pred
, ei
, block
->preds
)
1466 /* This can happen in the very weird case
1467 that our fake infinite loop edges have caused a
1468 critical edge to appear. */
1469 if (EDGE_CRITICAL_P (pred
))
1475 eprime
= phi_translate (node
->expr
,
1479 /* eprime will generally only be NULL if the
1480 value of the expression, translated
1481 through the PHI for this predecessor, is
1482 undefined. If that is the case, we can't
1483 make the expression fully redundant,
1484 because its value is undefined along a
1485 predecessor path. We can thus break out
1486 early because it doesn't matter what the
1487 rest of the results are. */
1494 vprime
= get_value_handle (eprime
);
1495 gcc_assert (vprime
);
1496 edoubleprime
= bitmap_find_leader (AVAIL_OUT (bprime
),
1498 if (edoubleprime
== NULL
)
1500 avail
[bprime
->index
] = eprime
;
1505 avail
[bprime
->index
] = edoubleprime
;
1507 if (first_s
== NULL
)
1508 first_s
= edoubleprime
;
1509 else if (first_s
!= edoubleprime
)
1511 gcc_assert (first_s
== edoubleprime
1513 (first_s
, edoubleprime
, 0));
1516 /* If we can insert it, it's not the same value
1517 already existing along every predecessor, and
1518 it's defined by some predecessor, it is
1519 partially redundant. */
1520 if (!cant_insert
&& !all_same
&& by_some
)
1522 tree type
= TREE_TYPE (avail
[EDGE_PRED (block
, 0)->src
->index
]);
1524 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1526 fprintf (dump_file
, "Found partial redundancy for expression ");
1527 print_generic_expr (dump_file
, node
->expr
, 0);
1528 fprintf (dump_file
, "\n");
1531 /* Make the necessary insertions. */
1532 FOR_EACH_EDGE (pred
, ei
, block
->preds
)
1534 tree stmts
= alloc_stmt_list ();
1537 eprime
= avail
[bprime
->index
];
1538 if (BINARY_CLASS_P (eprime
)
1539 || UNARY_CLASS_P (eprime
))
1541 builtexpr
= create_expression_by_pieces (bprime
,
1544 bsi_insert_on_edge (pred
, stmts
);
1545 avail
[bprime
->index
] = builtexpr
;
1548 /* Now build a phi for the new variable. */
1549 temp
= create_tmp_var (type
, "prephitmp");
1550 add_referenced_tmp_var (temp
);
1551 temp
= create_phi_node (temp
, block
);
1552 vn_add (PHI_RESULT (temp
), val
, NULL
);
1555 if (!set_contains_value (AVAIL_OUT (block
), val
))
1556 insert_into_set (AVAIL_OUT (block
),
1560 bitmap_value_replace_in_set (AVAIL_OUT (block
),
1562 FOR_EACH_EDGE (pred
, ei
, block
->preds
)
1564 add_phi_arg (&temp
, avail
[pred
->src
->index
],
1567 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1569 fprintf (dump_file
, "Created phi ");
1570 print_generic_expr (dump_file
, temp
, 0);
1571 fprintf (dump_file
, " in block %d\n", block
->index
);
1575 bitmap_insert_into_set (NEW_SETS (block
),
1577 bitmap_insert_into_set (PHI_GEN (block
),
1587 for (son
= first_dom_son (CDI_DOMINATORS
, block
);
1589 son
= next_dom_son (CDI_DOMINATORS
, son
))
1591 new_stuff
|= insert_aux (son
);
1597 /* Perform insertion of partially redundant values. */
1602 bool new_stuff
= true;
1604 int num_iterations
= 0;
1607 NEW_SETS (bb
) = bitmap_set_new ();
1613 new_stuff
= insert_aux (ENTRY_BLOCK_PTR
);
1615 if (num_iterations
> 2 && dump_file
&& (dump_flags
& TDF_STATS
))
1616 fprintf (dump_file
, "insert required %d iterations\n", num_iterations
);
1620 /* Return true if VAR is an SSA variable with no defining statement in
1621 this procedure, *AND* isn't a live-on-entry parameter. */
1624 is_undefined_value (tree expr
)
1626 return (TREE_CODE (expr
) == SSA_NAME
1627 && IS_EMPTY_STMT (SSA_NAME_DEF_STMT (expr
))
1628 /* PARM_DECLs and hard registers are always defined. */
1629 && TREE_CODE (SSA_NAME_VAR (expr
)) != PARM_DECL
);
1633 /* Given an SSA variable VAR and an expression EXPR, compute the value
1634 number for EXPR and create a value handle (VAL) for it. If VAR and
1635 EXPR are not the same, associate VAL with VAR. Finally, add VAR to
1636 S1 and its value handle to S2.
1638 VUSES represent the virtual use operands associated with EXPR (if
1639 any). They are used when computing the hash value for EXPR. */
1642 add_to_sets (tree var
, tree expr
, vuse_optype vuses
, bitmap_set_t s1
,
1645 tree val
= vn_lookup_or_add (expr
, vuses
);
1647 /* VAR and EXPR may be the same when processing statements for which
1648 we are not computing value numbers (e.g., non-assignments, or
1649 statements that make aliased stores). In those cases, we are
1650 only interested in making VAR available as its own value. */
1652 vn_add (var
, val
, NULL
);
1654 bitmap_insert_into_set (s1
, var
);
1655 bitmap_value_insert_into_set (s2
, var
);
1659 /* Given a unary or binary expression EXPR, create and return a new
1660 expression with the same structure as EXPR but with its operands
1661 replaced with the value handles of each of the operands of EXPR.
1662 Insert EXPR's operands into the EXP_GEN set for BLOCK.
1664 VUSES represent the virtual use operands associated with EXPR (if
1665 any). They are used when computing the hash value for EXPR. */
1668 create_value_expr_from (tree expr
, basic_block block
, vuse_optype vuses
)
1671 enum tree_code code
= TREE_CODE (expr
);
1674 gcc_assert (TREE_CODE_CLASS (code
) == tcc_unary
1675 || TREE_CODE_CLASS (code
) == tcc_binary
1676 || TREE_CODE_CLASS (code
) == tcc_reference
);
1678 if (TREE_CODE_CLASS (code
) == tcc_unary
)
1679 vexpr
= pool_alloc (unary_node_pool
);
1680 else if (TREE_CODE_CLASS (code
) == tcc_reference
)
1681 vexpr
= pool_alloc (reference_node_pool
);
1683 vexpr
= pool_alloc (binary_node_pool
);
1685 memcpy (vexpr
, expr
, tree_size (expr
));
1687 for (i
= 0; i
< TREE_CODE_LENGTH (code
); i
++)
1689 tree op
= TREE_OPERAND (expr
, i
);
1692 tree val
= vn_lookup_or_add (op
, vuses
);
1693 if (!is_undefined_value (op
))
1694 value_insert_into_set (EXP_GEN (block
), op
);
1695 if (TREE_CODE (val
) == VALUE_HANDLE
)
1696 TREE_TYPE (val
) = TREE_TYPE (TREE_OPERAND (vexpr
, i
));
1697 TREE_OPERAND (vexpr
, i
) = val
;
1705 /* Compute the AVAIL set for BLOCK.
1706 This function performs value numbering of the statements in BLOCK.
1707 The AVAIL sets are built from information we glean while doing this
1708 value numbering, since the AVAIL sets contain only one entry per
1711 AVAIL_IN[BLOCK] = AVAIL_OUT[dom(BLOCK)].
1712 AVAIL_OUT[BLOCK] = AVAIL_IN[BLOCK] U PHI_GEN[BLOCK] U TMP_GEN[BLOCK]. */
1715 compute_avail (basic_block block
)
1719 /* For arguments with default definitions, we pretend they are
1720 defined in the entry block. */
1721 if (block
== ENTRY_BLOCK_PTR
)
1724 for (param
= DECL_ARGUMENTS (current_function_decl
);
1726 param
= TREE_CHAIN (param
))
1728 if (default_def (param
) != NULL
)
1731 tree def
= default_def (param
);
1732 val
= vn_lookup_or_add (def
, NULL
);
1733 bitmap_insert_into_set (TMP_GEN (block
), def
);
1734 bitmap_value_insert_into_set (AVAIL_OUT (block
), def
);
1740 block_stmt_iterator bsi
;
1744 /* Initially, the set of available values in BLOCK is that of
1745 its immediate dominator. */
1746 dom
= get_immediate_dominator (CDI_DOMINATORS
, block
);
1748 bitmap_set_copy (AVAIL_OUT (block
), AVAIL_OUT (dom
));
1750 /* Generate values for PHI nodes. */
1751 for (phi
= phi_nodes (block
); phi
; phi
= PHI_CHAIN (phi
))
1752 /* We have no need for virtual phis, as they don't represent
1753 actual computations. */
1754 if (is_gimple_reg (PHI_RESULT (phi
)))
1755 add_to_sets (PHI_RESULT (phi
), PHI_RESULT (phi
), NULL
,
1756 PHI_GEN (block
), AVAIL_OUT (block
));
1758 /* Now compute value numbers and populate value sets with all
1759 the expressions computed in BLOCK. */
1760 for (bsi
= bsi_start (block
); !bsi_end_p (bsi
); bsi_next (&bsi
))
1765 stmt
= bsi_stmt (bsi
);
1766 ann
= stmt_ann (stmt
);
1767 get_stmt_operands (stmt
);
1769 /* We are only interested in assignments of the form
1770 X_i = EXPR, where EXPR represents an "interesting"
1771 computation, it has no volatile operands and X_i
1772 doesn't flow through an abnormal edge. */
1773 if (TREE_CODE (stmt
) == MODIFY_EXPR
1774 && !ann
->has_volatile_ops
1775 && TREE_CODE (TREE_OPERAND (stmt
, 0)) == SSA_NAME
1776 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (TREE_OPERAND (stmt
, 0)))
1778 tree lhs
= TREE_OPERAND (stmt
, 0);
1779 tree rhs
= TREE_OPERAND (stmt
, 1);
1780 vuse_optype vuses
= STMT_VUSE_OPS (stmt
);
1782 STRIP_USELESS_TYPE_CONVERSION (rhs
);
1783 if (TREE_CODE (rhs
) == SSA_NAME
1784 || is_gimple_min_invariant (rhs
))
1786 /* Compute a value number for the RHS of the statement
1787 and add its value to the AVAIL_OUT set for the block.
1788 Add the LHS to TMP_GEN. */
1789 add_to_sets (lhs
, rhs
, vuses
, TMP_GEN (block
),
1792 if (TREE_CODE (rhs
) == SSA_NAME
1793 && !is_undefined_value (rhs
))
1794 value_insert_into_set (EXP_GEN (block
), rhs
);
1797 else if (UNARY_CLASS_P (rhs
) || BINARY_CLASS_P (rhs
)
1798 || TREE_CODE (rhs
) == INDIRECT_REF
)
1800 /* For binary, unary, and reference expressions,
1801 create a duplicate expression with the operands
1802 replaced with the value handles of the original
1804 tree newt
= create_value_expr_from (rhs
, block
, vuses
);
1805 add_to_sets (lhs
, newt
, vuses
, TMP_GEN (block
),
1807 value_insert_into_set (EXP_GEN (block
), newt
);
1812 /* For any other statement that we don't recognize, simply
1813 make the names generated by the statement available in
1814 AVAIL_OUT and TMP_GEN. */
1815 for (j
= 0; j
< NUM_DEFS (STMT_DEF_OPS (stmt
)); j
++)
1817 tree def
= DEF_OP (STMT_DEF_OPS (stmt
), j
);
1818 add_to_sets (def
, def
, NULL
, TMP_GEN (block
),
1822 for (j
= 0; j
< NUM_USES (STMT_USE_OPS (stmt
)); j
++)
1824 tree use
= USE_OP (STMT_USE_OPS (stmt
), j
);
1825 add_to_sets (use
, use
, NULL
, TMP_GEN (block
),
1831 /* Compute available sets for the dominator children of BLOCK. */
1832 for (son
= first_dom_son (CDI_DOMINATORS
, block
);
1834 son
= next_dom_son (CDI_DOMINATORS
, son
))
1835 compute_avail (son
);
1839 /* Eliminate fully redundant computations. */
1848 block_stmt_iterator i
;
1850 for (i
= bsi_start (b
); !bsi_end_p (i
); bsi_next (&i
))
1852 tree stmt
= bsi_stmt (i
);
1854 /* Lookup the RHS of the expression, see if we have an
1855 available computation for it. If so, replace the RHS with
1856 the available computation. */
1857 if (TREE_CODE (stmt
) == MODIFY_EXPR
1858 && TREE_CODE (TREE_OPERAND (stmt
, 0)) == SSA_NAME
1859 && TREE_CODE (TREE_OPERAND (stmt
,1)) != SSA_NAME
1860 && !is_gimple_min_invariant (TREE_OPERAND (stmt
, 1))
1861 && !stmt_ann (stmt
)->has_volatile_ops
)
1863 tree lhs
= TREE_OPERAND (stmt
, 0);
1864 tree
*rhs_p
= &TREE_OPERAND (stmt
, 1);
1867 sprime
= bitmap_find_leader (AVAIL_OUT (b
),
1868 vn_lookup (lhs
, NULL
));
1871 && (TREE_CODE (*rhs_p
) != SSA_NAME
1872 || may_propagate_copy (*rhs_p
, sprime
)))
1874 gcc_assert (sprime
!= *rhs_p
);
1876 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1878 fprintf (dump_file
, "Replaced ");
1879 print_generic_expr (dump_file
, *rhs_p
, 0);
1880 fprintf (dump_file
, " with ");
1881 print_generic_expr (dump_file
, sprime
, 0);
1882 fprintf (dump_file
, " in ");
1883 print_generic_stmt (dump_file
, stmt
, 0);
1885 pre_stats
.eliminations
++;
1886 propagate_tree_value (rhs_p
, sprime
);
1889 /* If we removed EH side effects from the statement, clean
1890 its EH information. */
1891 if (maybe_clean_eh_stmt (stmt
))
1893 bitmap_set_bit (need_eh_cleanup
,
1894 bb_for_stmt (stmt
)->index
);
1895 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1896 fprintf (dump_file
, " Removed EH side effects.\n");
1905 /* Initialize data structures used by PRE. */
1912 connect_infinite_loops_to_exit ();
1914 memset (&pre_stats
, 0, sizeof (pre_stats
));
1916 /* If block 0 has more than one predecessor, it means that its PHI
1917 nodes will have arguments coming from block -1. This creates
1918 problems for several places in PRE that keep local arrays indexed
1919 by block number. To prevent this, we split the edge coming from
1920 ENTRY_BLOCK_PTR (FIXME, if ENTRY_BLOCK_PTR had an index number
1921 different than -1 we wouldn't have to hack this. tree-ssa-dce.c
1922 needs a similar change). */
1923 if (EDGE_COUNT (EDGE_SUCC (ENTRY_BLOCK_PTR
, 0)->dest
->preds
) > 1)
1924 if (!(EDGE_SUCC (ENTRY_BLOCK_PTR
, 0)->flags
& EDGE_ABNORMAL
))
1925 split_edge (EDGE_SUCC (ENTRY_BLOCK_PTR
, 0));
1928 bb
->aux
= xcalloc (1, sizeof (struct bb_value_sets
));
1930 gcc_obstack_init (&grand_bitmap_obstack
);
1931 phi_translate_table
= htab_create (511, expr_pred_trans_hash
,
1932 expr_pred_trans_eq
, free
);
1933 value_set_pool
= create_alloc_pool ("Value sets",
1934 sizeof (struct value_set
), 30);
1935 bitmap_set_pool
= create_alloc_pool ("Bitmap sets",
1936 sizeof (struct bitmap_set
), 30);
1937 value_set_node_pool
= create_alloc_pool ("Value set nodes",
1938 sizeof (struct value_set_node
), 30);
1939 calculate_dominance_info (CDI_POST_DOMINATORS
);
1940 calculate_dominance_info (CDI_DOMINATORS
);
1941 binary_node_pool
= create_alloc_pool ("Binary tree nodes",
1942 tree_code_size (PLUS_EXPR
), 30);
1943 unary_node_pool
= create_alloc_pool ("Unary tree nodes",
1944 tree_code_size (NEGATE_EXPR
), 30);
1945 reference_node_pool
= create_alloc_pool ("Reference tree nodes",
1946 tree_code_size (ARRAY_REF
), 30);
1949 EXP_GEN (bb
) = set_new (true);
1950 PHI_GEN (bb
) = bitmap_set_new ();
1951 TMP_GEN (bb
) = bitmap_set_new ();
1952 AVAIL_OUT (bb
) = bitmap_set_new ();
1955 need_eh_cleanup
= BITMAP_XMALLOC ();
1959 /* Deallocate data structures used by PRE. */
1967 bsi_commit_edge_inserts (NULL
);
1969 obstack_free (&grand_bitmap_obstack
, NULL
);
1970 free_alloc_pool (value_set_pool
);
1971 free_alloc_pool (bitmap_set_pool
);
1972 free_alloc_pool (value_set_node_pool
);
1973 free_alloc_pool (binary_node_pool
);
1974 free_alloc_pool (reference_node_pool
);
1975 free_alloc_pool (unary_node_pool
);
1976 htab_delete (phi_translate_table
);
1977 remove_fake_exit_edges ();
1985 free_dominance_info (CDI_POST_DOMINATORS
);
1988 if (!bitmap_empty_p (need_eh_cleanup
))
1990 tree_purge_all_dead_eh_edges (need_eh_cleanup
);
1991 cleanup_tree_cfg ();
1994 BITMAP_XFREE (need_eh_cleanup
);
1996 /* Wipe out pointers to VALUE_HANDLEs. In the not terribly distant
1997 future we will want them to be persistent though. */
1998 for (i
= 0; i
< num_ssa_names
; i
++)
2000 tree name
= ssa_name (i
);
2005 if (SSA_NAME_VALUE (name
)
2006 && TREE_CODE (SSA_NAME_VALUE (name
)) == VALUE_HANDLE
)
2007 SSA_NAME_VALUE (name
) = NULL
;
2012 /* Main entry point to the SSA-PRE pass. DO_FRE is true if the caller
2013 only wants to do full redundancy elimination. */
2016 execute_pre (bool do_fre
)
2020 /* Collect and value number expressions computed in each basic
2022 compute_avail (ENTRY_BLOCK_PTR
);
2024 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2030 print_value_set (dump_file
, EXP_GEN (bb
), "exp_gen", bb
->index
);
2031 bitmap_print_value_set (dump_file
, TMP_GEN (bb
), "tmp_gen",
2033 bitmap_print_value_set (dump_file
, AVAIL_OUT (bb
), "avail_out",
2038 /* Insert can get quite slow on an incredibly large number of basic
2039 blocks due to some quadratic behavior. Until this behavior is
2040 fixed, don't run it when he have an incredibly large number of
2041 bb's. If we aren't going to run insert, there is no point in
2042 computing ANTIC, either, even though it's plenty fast. */
2043 if (!do_fre
&& n_basic_blocks
< 4000)
2049 /* Remove all the redundant expressions. */
2052 if (dump_file
&& (dump_flags
& TDF_STATS
))
2054 fprintf (dump_file
, "Insertions:%d\n", pre_stats
.insertions
);
2055 fprintf (dump_file
, "New PHIs:%d\n", pre_stats
.phis
);
2056 fprintf (dump_file
, "Eliminated:%d\n", pre_stats
.eliminations
);
2063 /* Gate and execute functions for PRE. */
2068 execute_pre (false);
2074 return flag_tree_pre
!= 0;
2077 struct tree_opt_pass pass_pre
=
2080 gate_pre
, /* gate */
2081 do_pre
, /* execute */
2084 0, /* static_pass_number */
2085 TV_TREE_PRE
, /* tv_id */
2086 PROP_no_crit_edges
| PROP_cfg
2087 | PROP_ssa
| PROP_alias
, /* properties_required */
2088 0, /* properties_provided */
2089 0, /* properties_destroyed */
2090 0, /* todo_flags_start */
2091 TODO_dump_func
| TODO_ggc_collect
| TODO_verify_ssa
, /* todo_flags_finish */
2096 /* Gate and execute functions for FRE. */
2107 return flag_tree_fre
!= 0;
2110 struct tree_opt_pass pass_fre
=
2113 gate_fre
, /* gate */
2114 do_fre
, /* execute */
2117 0, /* static_pass_number */
2118 TV_TREE_FRE
, /* tv_id */
2119 PROP_cfg
| PROP_ssa
| PROP_alias
, /* properties_required */
2120 0, /* properties_provided */
2121 0, /* properties_destroyed */
2122 0, /* todo_flags_start */
2123 TODO_dump_func
| TODO_ggc_collect
| TODO_verify_ssa
, /* todo_flags_finish */