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