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
);
953 /* For each expression in SET, translate the value handles through phi nodes
954 in PHIBLOCK using edge PHIBLOCK->PRED, and store the resulting
955 expressions in DEST. */
958 phi_translate_set (value_set_t dest
, value_set_t set
, basic_block pred
,
959 basic_block phiblock
)
961 value_set_node_t node
;
962 for (node
= set
->head
;
967 translated
= phi_translate (node
->expr
, set
, pred
, phiblock
);
968 phi_trans_add (node
->expr
, translated
, pred
);
970 if (translated
!= NULL
)
971 value_insert_into_set (dest
, translated
);
975 /* Find the leader for a value (i.e., the name representing that
976 value) in a given set, and return it. Return NULL if no leader is
980 bitmap_find_leader (bitmap_set_t set
, tree val
)
985 if (is_gimple_min_invariant (val
))
987 if (bitmap_set_contains_value (set
, val
))
989 /* Rather than walk the entire bitmap of expressions, and see
990 whether any of them has the value we are looking for, we look
991 at the reverse mapping, which tells us the set of expressions
992 that have a given value (IE value->expressions with that
993 value) and see if any of those expressions are in our set.
994 The number of expressions per value is usually significantly
995 less than the number of expressions in the set. In fact, for
996 large testcases, doing it this way is roughly 5-10x faster
997 than walking the bitmap.
998 If this is somehow a significant lose for some cases, we can
999 choose which set to walk based on which set is smaller. */
1000 value_set_t exprset
;
1001 value_set_node_t node
;
1002 exprset
= VALUE_HANDLE_EXPR_SET (val
);
1003 for (node
= exprset
->head
; node
; node
= node
->next
)
1005 if (TREE_CODE (node
->expr
) == SSA_NAME
)
1007 if (bitmap_bit_p (set
->expressions
,
1008 SSA_NAME_VERSION (node
->expr
)))
1017 /* Find the leader for a value (i.e., the name representing that
1018 value) in a given set, and return it. Return NULL if no leader is
1022 find_leader (value_set_t set
, tree val
)
1024 value_set_node_t node
;
1029 /* Constants represent themselves. */
1030 if (is_gimple_min_invariant (val
))
1033 if (set
->length
== 0)
1036 if (value_exists_in_set_bitmap (set
, val
))
1038 for (node
= set
->head
;
1042 if (get_value_handle (node
->expr
) == val
)
1050 /* Determine if the expression EXPR is valid in SET. This means that
1051 we have a leader for each part of the expression (if it consists of
1052 values), or the expression is an SSA_NAME.
1054 NB: We never should run into a case where we have SSA_NAME +
1055 SSA_NAME or SSA_NAME + value. The sets valid_in_set is called on,
1056 the ANTIC sets, will only ever have SSA_NAME's or binary value
1057 expression (IE VALUE1 + VALUE2) */
1060 valid_in_set (value_set_t set
, tree expr
)
1062 switch (TREE_CODE_CLASS (TREE_CODE (expr
)))
1065 case tcc_comparison
:
1067 tree op1
= TREE_OPERAND (expr
, 0);
1068 tree op2
= TREE_OPERAND (expr
, 1);
1069 return set_contains_value (set
, op1
) && set_contains_value (set
, op2
);
1074 tree op1
= TREE_OPERAND (expr
, 0);
1075 return set_contains_value (set
, op1
);
1079 /* XXX: Until PRE of loads works, no reference nodes are ANTIC. */
1082 case tcc_exceptional
:
1083 gcc_assert (TREE_CODE (expr
) == SSA_NAME
);
1086 case tcc_declaration
:
1087 /* VAR_DECL and PARM_DECL are never anticipatable. */
1091 /* No other cases should be encountered. */
1096 /* Clean the set of expressions that are no longer valid in SET. This
1097 means expressions that are made up of values we have no leaders for
1101 clean (value_set_t set
)
1103 value_set_node_t node
;
1104 value_set_node_t next
;
1109 if (!valid_in_set (set
, node
->expr
))
1110 set_remove (set
, node
->expr
);
1115 DEF_VEC_P (basic_block
);
1116 DEF_VEC_ALLOC_P (basic_block
, heap
);
1117 static sbitmap has_abnormal_preds
;
1119 /* Compute the ANTIC set for BLOCK.
1121 If succs(BLOCK) > 1 then
1122 ANTIC_OUT[BLOCK] = intersection of ANTIC_IN[b] for all succ(BLOCK)
1123 else if succs(BLOCK) == 1 then
1124 ANTIC_OUT[BLOCK] = phi_translate (ANTIC_IN[succ(BLOCK)])
1126 ANTIC_IN[BLOCK] = clean(ANTIC_OUT[BLOCK] U EXP_GEN[BLOCK] - TMP_GEN[BLOCK])
1128 XXX: It would be nice to either write a set_clear, and use it for
1129 ANTIC_OUT, or to mark the antic_out set as deleted at the end
1130 of this routine, so that the pool can hand the same memory back out
1131 again for the next ANTIC_OUT. */
1134 compute_antic_aux (basic_block block
, bool block_has_abnormal_pred_edge
)
1137 bool changed
= false;
1138 value_set_t S
, old
, ANTIC_OUT
;
1139 value_set_node_t node
;
1141 ANTIC_OUT
= S
= NULL
;
1143 /* If any edges from predecessors are abnormal, antic_in is empty,
1145 if (block_has_abnormal_pred_edge
)
1146 goto maybe_dump_sets
;
1148 old
= set_new (false);
1149 set_copy (old
, ANTIC_IN (block
));
1150 ANTIC_OUT
= set_new (true);
1152 /* If the block has no successors, ANTIC_OUT is empty. */
1153 if (EDGE_COUNT (block
->succs
) == 0)
1155 /* If we have one successor, we could have some phi nodes to
1156 translate through. */
1157 else if (single_succ_p (block
))
1159 phi_translate_set (ANTIC_OUT
, ANTIC_IN(single_succ (block
)),
1160 block
, single_succ (block
));
1162 /* If we have multiple successors, we take the intersection of all of
1166 VEC(basic_block
, heap
) * worklist
;
1169 basic_block bprime
, first
;
1172 worklist
= VEC_alloc (basic_block
, heap
, EDGE_COUNT (block
->succs
));
1173 FOR_EACH_EDGE (e
, ei
, block
->succs
)
1174 VEC_quick_push (basic_block
, worklist
, e
->dest
);
1175 first
= VEC_index (basic_block
, worklist
, 0);
1176 set_copy (ANTIC_OUT
, ANTIC_IN (first
));
1178 for (i
= 1; VEC_iterate (basic_block
, worklist
, i
, bprime
); i
++)
1180 node
= ANTIC_OUT
->head
;
1184 value_set_node_t next
= node
->next
;
1185 val
= get_value_handle (node
->expr
);
1186 if (!set_contains_value (ANTIC_IN (bprime
), val
))
1187 set_remove (ANTIC_OUT
, node
->expr
);
1191 VEC_free (basic_block
, heap
, worklist
);
1194 /* Generate ANTIC_OUT - TMP_GEN. */
1195 S
= bitmap_set_subtract_from_value_set (ANTIC_OUT
, TMP_GEN (block
), false);
1197 /* Start ANTIC_IN with EXP_GEN - TMP_GEN */
1198 ANTIC_IN (block
) = bitmap_set_subtract_from_value_set (EXP_GEN (block
),
1202 /* Then union in the ANTIC_OUT - TMP_GEN values,
1203 to get ANTIC_OUT U EXP_GEN - TMP_GEN */
1204 for (node
= S
->head
; node
; node
= node
->next
)
1205 value_insert_into_set (ANTIC_IN (block
), node
->expr
);
1207 clean (ANTIC_IN (block
));
1208 if (!set_equal (old
, ANTIC_IN (block
)))
1212 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1215 print_value_set (dump_file
, ANTIC_OUT
, "ANTIC_OUT", block
->index
);
1216 print_value_set (dump_file
, ANTIC_IN (block
), "ANTIC_IN", block
->index
);
1218 print_value_set (dump_file
, S
, "S", block
->index
);
1221 for (son
= first_dom_son (CDI_POST_DOMINATORS
, block
);
1223 son
= next_dom_son (CDI_POST_DOMINATORS
, son
))
1225 changed
|= compute_antic_aux (son
,
1226 TEST_BIT (has_abnormal_preds
, son
->index
));
1231 /* Compute ANTIC sets. */
1234 compute_antic (void)
1236 bool changed
= true;
1237 int num_iterations
= 0;
1240 /* If any predecessor edges are abnormal, we punt, so antic_in is empty.
1241 We pre-build the map of blocks with incoming abnormal edges here. */
1242 has_abnormal_preds
= sbitmap_alloc (last_basic_block
);
1243 sbitmap_zero (has_abnormal_preds
);
1249 FOR_EACH_EDGE (e
, ei
, block
->preds
)
1250 if (e
->flags
& EDGE_ABNORMAL
)
1252 SET_BIT (has_abnormal_preds
, block
->index
);
1256 /* While we are here, give empty ANTIC_IN sets to each block. */
1257 ANTIC_IN (block
) = set_new (true);
1259 /* At the exit block we anticipate nothing. */
1260 ANTIC_IN (EXIT_BLOCK_PTR
) = set_new (true);
1266 changed
= compute_antic_aux (EXIT_BLOCK_PTR
, false);
1269 sbitmap_free (has_abnormal_preds
);
1271 if (dump_file
&& (dump_flags
& TDF_STATS
))
1272 fprintf (dump_file
, "compute_antic required %d iterations\n", num_iterations
);
1275 static VEC(tree
,heap
) *inserted_exprs
;
1276 /* Find a leader for an expression, or generate one using
1277 create_expression_by_pieces if it's ANTIC but
1279 BLOCK is the basic_block we are looking for leaders in.
1280 EXPR is the expression to find a leader or generate for.
1281 STMTS is the statement list to put the inserted expressions on.
1282 Returns the SSA_NAME of the LHS of the generated expression or the
1286 find_or_generate_expression (basic_block block
, tree expr
, tree stmts
)
1288 tree genop
= bitmap_find_leader (AVAIL_OUT (block
), expr
);
1290 /* If it's still NULL, it must be a complex expression, so generate
1294 genop
= VALUE_HANDLE_EXPR_SET (expr
)->head
->expr
;
1295 gcc_assert (UNARY_CLASS_P (genop
)
1296 || BINARY_CLASS_P (genop
)
1297 || COMPARISON_CLASS_P (genop
)
1298 || REFERENCE_CLASS_P (genop
));
1299 genop
= create_expression_by_pieces (block
, genop
, stmts
);
1304 #define NECESSARY(stmt) stmt->common.asm_written_flag
1305 /* Create an expression in pieces, so that we can handle very complex
1306 expressions that may be ANTIC, but not necessary GIMPLE.
1307 BLOCK is the basic block the expression will be inserted into,
1308 EXPR is the expression to insert (in value form)
1309 STMTS is a statement list to append the necessary insertions into.
1311 This function will die if we hit some value that shouldn't be
1312 ANTIC but is (IE there is no leader for it, or its components).
1313 This function may also generate expressions that are themselves
1314 partially or fully redundant. Those that are will be either made
1315 fully redundant during the next iteration of insert (for partially
1316 redundant ones), or eliminated by eliminate (for fully redundant
1320 create_expression_by_pieces (basic_block block
, tree expr
, tree stmts
)
1322 tree name
= NULL_TREE
;
1323 tree newexpr
= NULL_TREE
;
1326 switch (TREE_CODE_CLASS (TREE_CODE (expr
)))
1329 case tcc_comparison
:
1331 tree_stmt_iterator tsi
;
1333 tree genop1
, genop2
;
1336 tree op1
= TREE_OPERAND (expr
, 0);
1337 tree op2
= TREE_OPERAND (expr
, 1);
1338 genop1
= find_or_generate_expression (block
, op1
, stmts
);
1339 genop2
= find_or_generate_expression (block
, op2
, stmts
);
1340 temp
= create_tmp_var (TREE_TYPE (expr
), "pretmp");
1341 add_referenced_tmp_var (temp
);
1343 folded
= fold (build (TREE_CODE (expr
), TREE_TYPE (expr
),
1345 newexpr
= force_gimple_operand (folded
, &forced_stmts
, false, NULL
);
1348 tsi
= tsi_start (forced_stmts
);
1349 for (; !tsi_end_p (tsi
); tsi_next (&tsi
))
1351 tree stmt
= tsi_stmt (tsi
);
1352 tree forcedname
= TREE_OPERAND (stmt
, 0);
1353 tree forcedexpr
= TREE_OPERAND (stmt
, 1);
1354 tree val
= vn_lookup_or_add (forcedexpr
, NULL
);
1355 vn_add (forcedname
, val
, NULL
);
1356 bitmap_value_replace_in_set (NEW_SETS (block
), forcedname
);
1357 bitmap_value_replace_in_set (AVAIL_OUT (block
), forcedname
);
1360 tsi
= tsi_last (stmts
);
1361 tsi_link_after (&tsi
, forced_stmts
, TSI_CONTINUE_LINKING
);
1363 newexpr
= build (MODIFY_EXPR
, TREE_TYPE (expr
),
1365 NECESSARY (newexpr
) = 0;
1366 name
= make_ssa_name (temp
, newexpr
);
1367 TREE_OPERAND (newexpr
, 0) = name
;
1368 tsi
= tsi_last (stmts
);
1369 tsi_link_after (&tsi
, newexpr
, TSI_CONTINUE_LINKING
);
1370 VEC_safe_push (tree
, heap
, inserted_exprs
, newexpr
);
1371 pre_stats
.insertions
++;
1376 tree_stmt_iterator tsi
;
1377 tree forced_stmts
= NULL
;
1381 tree op1
= TREE_OPERAND (expr
, 0);
1382 genop1
= find_or_generate_expression (block
, op1
, stmts
);
1383 temp
= create_tmp_var (TREE_TYPE (expr
), "pretmp");
1384 add_referenced_tmp_var (temp
);
1385 folded
= fold (build (TREE_CODE (expr
), TREE_TYPE (expr
),
1387 /* If the generated operand is already GIMPLE min_invariant
1388 just use it instead of calling force_gimple_operand on it,
1389 since that may make it not invariant by copying it into an
1391 if (!is_gimple_min_invariant (genop1
))
1392 newexpr
= force_gimple_operand (folded
, &forced_stmts
, false, NULL
);
1397 tsi
= tsi_start (forced_stmts
);
1398 for (; !tsi_end_p (tsi
); tsi_next (&tsi
))
1400 tree stmt
= tsi_stmt (tsi
);
1401 tree forcedname
= TREE_OPERAND (stmt
, 0);
1402 tree forcedexpr
= TREE_OPERAND (stmt
, 1);
1403 tree val
= vn_lookup_or_add (forcedexpr
, NULL
);
1404 vn_add (forcedname
, val
, NULL
);
1405 bitmap_value_replace_in_set (NEW_SETS (block
), forcedname
);
1406 bitmap_value_replace_in_set (AVAIL_OUT (block
), forcedname
);
1408 tsi
= tsi_last (stmts
);
1409 tsi_link_after (&tsi
, forced_stmts
, TSI_CONTINUE_LINKING
);
1411 newexpr
= build (MODIFY_EXPR
, TREE_TYPE (expr
),
1413 name
= make_ssa_name (temp
, newexpr
);
1414 TREE_OPERAND (newexpr
, 0) = name
;
1415 NECESSARY (newexpr
) = 0;
1416 tsi
= tsi_last (stmts
);
1417 tsi_link_after (&tsi
, newexpr
, TSI_CONTINUE_LINKING
);
1418 VEC_safe_push (tree
, heap
, inserted_exprs
, newexpr
);
1419 pre_stats
.insertions
++;
1427 v
= get_value_handle (expr
);
1428 vn_add (name
, v
, NULL
);
1430 /* The value may already exist in either NEW_SETS, or AVAIL_OUT, because
1431 we are creating the expression by pieces, and this particular piece of
1432 the expression may have been represented. There is no harm in replacing
1434 bitmap_value_replace_in_set (NEW_SETS (block
), name
);
1435 bitmap_value_replace_in_set (AVAIL_OUT (block
), name
);
1436 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1438 fprintf (dump_file
, "Inserted ");
1439 print_generic_expr (dump_file
, newexpr
, 0);
1440 fprintf (dump_file
, " in predecessor %d\n", block
->index
);
1445 /* Return the folded version of T if T, when folded, is a gimple
1446 min_invariant. Otherwise, return T. */
1449 fully_constant_expression (tree t
)
1453 if (folded
&& is_gimple_min_invariant (folded
))
1458 /* Insert the to-be-made-available values of NODE for each predecessor, stored
1459 in AVAIL, into the predecessors of BLOCK, and merge the result with a phi
1460 node, given the same value handle as NODE. The prefix of the phi node is
1461 given with TMPNAME. Return true if we have inserted new stuff. */
1464 insert_into_preds_of_block (basic_block block
, value_set_node_t node
,
1465 tree
*avail
, const char *tmpname
)
1467 tree val
= get_value_handle (node
->expr
);
1469 bool insertions
= false;
1474 tree type
= TREE_TYPE (avail
[EDGE_PRED (block
, 0)->src
->index
]);
1477 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1479 fprintf (dump_file
, "Found partial redundancy for expression ");
1480 print_generic_expr (dump_file
, node
->expr
, 0);
1481 fprintf (dump_file
, "\n");
1484 /* Make sure we aren't creating an induction variable. */
1485 if (block
->loop_depth
> 0 && EDGE_COUNT (block
->preds
) == 2)
1487 bool firstinsideloop
= false;
1488 bool secondinsideloop
= false;
1489 firstinsideloop
= flow_bb_inside_loop_p (block
->loop_father
,
1490 EDGE_PRED (block
, 0)->src
);
1491 secondinsideloop
= flow_bb_inside_loop_p (block
->loop_father
,
1492 EDGE_PRED (block
, 1)->src
);
1493 /* Induction variables only have one edge inside the loop. */
1494 if (firstinsideloop
^ secondinsideloop
)
1496 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1497 fprintf (dump_file
, "Skipping insertion of phi for partial redundancy: Looks like an induction variable\n");
1503 /* Make the necessary insertions. */
1504 FOR_EACH_EDGE (pred
, ei
, block
->preds
)
1506 tree stmts
= alloc_stmt_list ();
1509 eprime
= avail
[bprime
->index
];
1510 if (BINARY_CLASS_P (eprime
)
1511 || COMPARISON_CLASS_P (eprime
)
1512 || UNARY_CLASS_P (eprime
))
1514 builtexpr
= create_expression_by_pieces (bprime
,
1517 bsi_insert_on_edge (pred
, stmts
);
1518 avail
[bprime
->index
] = builtexpr
;
1522 /* If we didn't want a phi node, and we made insertions, we still have
1523 inserted new stuff, and thus return true. If we didn't want a phi node,
1524 and didn't make insertions, we haven't added anything new, so return
1526 if (nophi
&& insertions
)
1528 else if (nophi
&& !insertions
)
1531 /* Now build a phi for the new variable. */
1532 temp
= create_tmp_var (type
, tmpname
);
1533 add_referenced_tmp_var (temp
);
1534 temp
= create_phi_node (temp
, block
);
1535 NECESSARY (temp
) = 0;
1536 VEC_safe_push (tree
, heap
, inserted_exprs
, temp
);
1537 FOR_EACH_EDGE (pred
, ei
, block
->preds
)
1538 add_phi_arg (temp
, avail
[pred
->src
->index
], pred
);
1540 vn_add (PHI_RESULT (temp
), val
, NULL
);
1542 /* The value should *not* exist in PHI_GEN, or else we wouldn't be doing
1543 this insertion, since we test for the existence of this value in PHI_GEN
1544 before proceeding with the partial redundancy checks in insert_aux.
1546 The value may exist in AVAIL_OUT, in particular, it could be represented
1547 by the expression we are trying to eliminate, in which case we want the
1548 replacement to occur. If it's not existing in AVAIL_OUT, we want it
1551 Similarly, to the PHI_GEN case, the value should not exist in NEW_SETS of
1552 this block, because if it did, it would have existed in our dominator's
1553 AVAIL_OUT, and would have been skipped due to the full redundancy check.
1556 bitmap_insert_into_set (PHI_GEN (block
),
1558 bitmap_value_replace_in_set (AVAIL_OUT (block
),
1560 bitmap_insert_into_set (NEW_SETS (block
),
1563 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1565 fprintf (dump_file
, "Created phi ");
1566 print_generic_expr (dump_file
, temp
, 0);
1567 fprintf (dump_file
, " in block %d\n", block
->index
);
1575 /* Perform insertion of partially redundant values.
1576 For BLOCK, do the following:
1577 1. Propagate the NEW_SETS of the dominator into the current block.
1578 If the block has multiple predecessors,
1579 2a. Iterate over the ANTIC expressions for the block to see if
1580 any of them are partially redundant.
1581 2b. If so, insert them into the necessary predecessors to make
1582 the expression fully redundant.
1583 2c. Insert a new PHI merging the values of the predecessors.
1584 2d. Insert the new PHI, and the new expressions, into the
1586 3. Recursively call ourselves on the dominator children of BLOCK.
1591 insert_aux (basic_block block
)
1594 bool new_stuff
= false;
1599 dom
= get_immediate_dominator (CDI_DOMINATORS
, block
);
1604 bitmap_set_t newset
= NEW_SETS (dom
);
1607 /* Note that we need to value_replace both NEW_SETS, and
1608 AVAIL_OUT. For both the case of NEW_SETS, the value may be
1609 represented by some non-simple expression here that we want
1610 to replace it with. */
1611 EXECUTE_IF_SET_IN_BITMAP (newset
->expressions
, 0, i
, bi
)
1613 bitmap_value_replace_in_set (NEW_SETS (block
), ssa_name (i
));
1614 bitmap_value_replace_in_set (AVAIL_OUT (block
), ssa_name (i
));
1617 if (!single_pred_p (block
))
1619 value_set_node_t node
;
1620 for (node
= ANTIC_IN (block
)->head
;
1624 if (BINARY_CLASS_P (node
->expr
)
1625 || COMPARISON_CLASS_P (node
->expr
)
1626 || UNARY_CLASS_P (node
->expr
))
1630 bool by_some
= false;
1631 bool cant_insert
= false;
1632 bool all_same
= true;
1633 tree first_s
= NULL
;
1636 tree eprime
= NULL_TREE
;
1639 val
= get_value_handle (node
->expr
);
1640 if (bitmap_set_contains_value (PHI_GEN (block
), val
))
1642 if (bitmap_set_contains_value (AVAIL_OUT (dom
), val
))
1644 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1645 fprintf (dump_file
, "Found fully redundant value\n");
1649 avail
= xcalloc (last_basic_block
, sizeof (tree
));
1650 FOR_EACH_EDGE (pred
, ei
, block
->preds
)
1655 /* This can happen in the very weird case
1656 that our fake infinite loop edges have caused a
1657 critical edge to appear. */
1658 if (EDGE_CRITICAL_P (pred
))
1664 eprime
= phi_translate (node
->expr
,
1668 /* eprime will generally only be NULL if the
1669 value of the expression, translated
1670 through the PHI for this predecessor, is
1671 undefined. If that is the case, we can't
1672 make the expression fully redundant,
1673 because its value is undefined along a
1674 predecessor path. We can thus break out
1675 early because it doesn't matter what the
1676 rest of the results are. */
1683 eprime
= fully_constant_expression (eprime
);
1684 vprime
= get_value_handle (eprime
);
1685 gcc_assert (vprime
);
1686 edoubleprime
= bitmap_find_leader (AVAIL_OUT (bprime
),
1688 if (edoubleprime
== NULL
)
1690 avail
[bprime
->index
] = eprime
;
1695 avail
[bprime
->index
] = edoubleprime
;
1697 if (first_s
== NULL
)
1698 first_s
= edoubleprime
;
1699 else if (!operand_equal_p (first_s
, edoubleprime
,
1704 /* If we can insert it, it's not the same value
1705 already existing along every predecessor, and
1706 it's defined by some predecessor, it is
1707 partially redundant. */
1708 if (!cant_insert
&& !all_same
&& by_some
)
1710 if (insert_into_preds_of_block (block
, node
, avail
,
1714 /* If all edges produce the same value and that value is
1715 an invariant, then the PHI has the same value on all
1716 edges. Note this. */
1717 else if (!cant_insert
&& all_same
&& eprime
1718 && is_gimple_min_invariant (eprime
)
1719 && !is_gimple_min_invariant (val
))
1721 value_set_t exprset
= VALUE_HANDLE_EXPR_SET (val
);
1722 value_set_node_t node
;
1723 for (node
= exprset
->head
; node
; node
= node
->next
)
1725 if (TREE_CODE (node
->expr
) == SSA_NAME
)
1727 vn_add (node
->expr
, eprime
, NULL
);
1728 pre_stats
.constified
++;
1738 for (son
= first_dom_son (CDI_DOMINATORS
, block
);
1740 son
= next_dom_son (CDI_DOMINATORS
, son
))
1742 new_stuff
|= insert_aux (son
);
1748 /* Perform insertion of partially redundant values. */
1753 bool new_stuff
= true;
1755 int num_iterations
= 0;
1758 NEW_SETS (bb
) = bitmap_set_new ();
1764 new_stuff
= insert_aux (ENTRY_BLOCK_PTR
);
1766 if (num_iterations
> 2 && dump_file
&& (dump_flags
& TDF_STATS
))
1767 fprintf (dump_file
, "insert required %d iterations\n", num_iterations
);
1771 /* Return true if VAR is an SSA variable with no defining statement in
1772 this procedure, *AND* isn't a live-on-entry parameter. */
1775 is_undefined_value (tree expr
)
1777 return (TREE_CODE (expr
) == SSA_NAME
1778 && IS_EMPTY_STMT (SSA_NAME_DEF_STMT (expr
))
1779 /* PARM_DECLs and hard registers are always defined. */
1780 && TREE_CODE (SSA_NAME_VAR (expr
)) != PARM_DECL
);
1784 /* Given an SSA variable VAR and an expression EXPR, compute the value
1785 number for EXPR and create a value handle (VAL) for it. If VAR and
1786 EXPR are not the same, associate VAL with VAR. Finally, add VAR to
1787 S1 and its value handle to S2.
1789 VUSES represent the virtual use operands associated with EXPR (if
1790 any). They are used when computing the hash value for EXPR. */
1793 add_to_sets (tree var
, tree expr
, vuse_optype vuses
, bitmap_set_t s1
,
1796 tree val
= vn_lookup_or_add (expr
, vuses
);
1798 /* VAR and EXPR may be the same when processing statements for which
1799 we are not computing value numbers (e.g., non-assignments, or
1800 statements that make aliased stores). In those cases, we are
1801 only interested in making VAR available as its own value. */
1803 vn_add (var
, val
, NULL
);
1806 bitmap_insert_into_set (s1
, var
);
1807 bitmap_value_insert_into_set (s2
, var
);
1811 /* Given a unary or binary expression EXPR, create and return a new
1812 expression with the same structure as EXPR but with its operands
1813 replaced with the value handles of each of the operands of EXPR.
1815 VUSES represent the virtual use operands associated with EXPR (if
1816 any). They are used when computing the hash value for EXPR.
1817 Insert EXPR's operands into the EXP_GEN set for BLOCK. */
1820 create_value_expr_from (tree expr
, basic_block block
,
1825 enum tree_code code
= TREE_CODE (expr
);
1829 gcc_assert (TREE_CODE_CLASS (code
) == tcc_unary
1830 || TREE_CODE_CLASS (code
) == tcc_binary
1831 || TREE_CODE_CLASS (code
) == tcc_comparison
1832 || TREE_CODE_CLASS (code
) == tcc_reference
);
1834 if (TREE_CODE_CLASS (code
) == tcc_unary
)
1835 pool
= unary_node_pool
;
1836 else if (TREE_CODE_CLASS (code
) == tcc_reference
)
1837 pool
= reference_node_pool
;
1839 pool
= binary_node_pool
;
1841 vexpr
= pool_alloc (pool
);
1842 memcpy (vexpr
, expr
, tree_size (expr
));
1844 for (i
= 0; i
< TREE_CODE_LENGTH (code
); i
++)
1848 op
= TREE_OPERAND (expr
, i
);
1849 if (op
== NULL_TREE
)
1852 /* If OP is a constant that has overflowed, do not value number
1854 if (TREE_CODE_CLASS (TREE_CODE (op
)) == tcc_constant
1855 && TREE_OVERFLOW (op
))
1857 pool_free (pool
, vexpr
);
1861 /* Recursively value-numberize reference ops */
1862 if (TREE_CODE_CLASS (TREE_CODE (op
)) == tcc_reference
)
1864 tree tempop
= create_value_expr_from (op
, block
, vuses
);
1865 op
= tempop
? tempop
: op
;
1866 val
= vn_lookup_or_add (op
, vuses
);
1869 /* Create a value handle for OP and add it to VEXPR. */
1870 val
= vn_lookup_or_add (op
, NULL
);
1872 if (!is_undefined_value (op
))
1873 value_insert_into_set (EXP_GEN (block
), op
);
1875 if (TREE_CODE (val
) == VALUE_HANDLE
)
1876 TREE_TYPE (val
) = TREE_TYPE (TREE_OPERAND (vexpr
, i
));
1878 TREE_OPERAND (vexpr
, i
) = val
;
1885 /* Compute the AVAIL set for all basic blocks.
1887 This function performs value numbering of the statements in each basic
1888 block. The AVAIL sets are built from information we glean while doing
1889 this value numbering, since the AVAIL sets contain only one entry per
1892 AVAIL_IN[BLOCK] = AVAIL_OUT[dom(BLOCK)].
1893 AVAIL_OUT[BLOCK] = AVAIL_IN[BLOCK] U PHI_GEN[BLOCK] U TMP_GEN[BLOCK]. */
1896 compute_avail (void)
1898 basic_block block
, son
;
1899 basic_block
*worklist
;
1903 /* For arguments with default definitions, we pretend they are
1904 defined in the entry block. */
1905 for (param
= DECL_ARGUMENTS (current_function_decl
);
1907 param
= TREE_CHAIN (param
))
1909 if (default_def (param
) != NULL
)
1911 tree def
= default_def (param
);
1912 vn_lookup_or_add (def
, NULL
);
1913 bitmap_insert_into_set (TMP_GEN (ENTRY_BLOCK_PTR
), def
);
1914 bitmap_value_insert_into_set (AVAIL_OUT (ENTRY_BLOCK_PTR
), def
);
1918 /* Allocate the worklist. */
1919 worklist
= xmalloc (sizeof (basic_block
) * n_basic_blocks
);
1921 /* Seed the algorithm by putting the dominator children of the entry
1922 block on the worklist. */
1923 for (son
= first_dom_son (CDI_DOMINATORS
, ENTRY_BLOCK_PTR
);
1925 son
= next_dom_son (CDI_DOMINATORS
, son
))
1926 worklist
[sp
++] = son
;
1928 /* Loop until the worklist is empty. */
1931 block_stmt_iterator bsi
;
1935 /* Pick a block from the worklist. */
1936 block
= worklist
[--sp
];
1938 /* Initially, the set of available values in BLOCK is that of
1939 its immediate dominator. */
1940 dom
= get_immediate_dominator (CDI_DOMINATORS
, block
);
1942 bitmap_set_copy (AVAIL_OUT (block
), AVAIL_OUT (dom
));
1944 /* Generate values for PHI nodes. */
1945 for (phi
= phi_nodes (block
); phi
; phi
= PHI_CHAIN (phi
))
1946 /* We have no need for virtual phis, as they don't represent
1947 actual computations. */
1948 if (is_gimple_reg (PHI_RESULT (phi
)))
1949 add_to_sets (PHI_RESULT (phi
), PHI_RESULT (phi
), NULL
,
1950 PHI_GEN (block
), AVAIL_OUT (block
));
1952 /* Now compute value numbers and populate value sets with all
1953 the expressions computed in BLOCK. */
1954 for (bsi
= bsi_start (block
); !bsi_end_p (bsi
); bsi_next (&bsi
))
1959 stmt
= bsi_stmt (bsi
);
1960 ann
= stmt_ann (stmt
);
1962 /* We are only interested in assignments of the form
1963 X_i = EXPR, where EXPR represents an "interesting"
1964 computation, it has no volatile operands and X_i
1965 doesn't flow through an abnormal edge. */
1966 if (TREE_CODE (stmt
) == MODIFY_EXPR
1967 && !ann
->has_volatile_ops
1968 && TREE_CODE (TREE_OPERAND (stmt
, 0)) == SSA_NAME
1969 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (TREE_OPERAND (stmt
, 0)))
1971 tree lhs
= TREE_OPERAND (stmt
, 0);
1972 tree rhs
= TREE_OPERAND (stmt
, 1);
1973 vuse_optype vuses
= STMT_VUSE_OPS (stmt
);
1975 STRIP_USELESS_TYPE_CONVERSION (rhs
);
1976 if (UNARY_CLASS_P (rhs
)
1977 || BINARY_CLASS_P (rhs
)
1978 || COMPARISON_CLASS_P (rhs
)
1979 || REFERENCE_CLASS_P (rhs
))
1981 /* For binary, unary, and reference expressions,
1982 create a duplicate expression with the operands
1983 replaced with the value handles of the original
1985 tree newt
= create_value_expr_from (rhs
, block
, vuses
);
1988 add_to_sets (lhs
, newt
, vuses
, TMP_GEN (block
),
1990 value_insert_into_set (EXP_GEN (block
), newt
);
1994 else if (TREE_CODE (rhs
) == SSA_NAME
1995 || is_gimple_min_invariant (rhs
)
1996 || TREE_CODE (rhs
) == ADDR_EXPR
1997 || TREE_INVARIANT (rhs
)
2000 /* Compute a value number for the RHS of the statement
2001 and add its value to the AVAIL_OUT set for the block.
2002 Add the LHS to TMP_GEN. */
2003 add_to_sets (lhs
, rhs
, vuses
, TMP_GEN (block
),
2006 if (TREE_CODE (rhs
) == SSA_NAME
2007 && !is_undefined_value (rhs
))
2008 value_insert_into_set (EXP_GEN (block
), rhs
);
2013 /* For any other statement that we don't recognize, simply
2014 make the names generated by the statement available in
2015 AVAIL_OUT and TMP_GEN. */
2016 for (j
= 0; j
< NUM_DEFS (STMT_DEF_OPS (stmt
)); j
++)
2018 tree def
= DEF_OP (STMT_DEF_OPS (stmt
), j
);
2019 add_to_sets (def
, def
, NULL
, TMP_GEN (block
),
2023 for (j
= 0; j
< NUM_USES (STMT_USE_OPS (stmt
)); j
++)
2025 tree use
= USE_OP (STMT_USE_OPS (stmt
), j
);
2026 add_to_sets (use
, use
, NULL
, NULL
, AVAIL_OUT (block
));
2030 /* Put the dominator children of BLOCK on the worklist of blocks
2031 to compute available sets for. */
2032 for (son
= first_dom_son (CDI_DOMINATORS
, block
);
2034 son
= next_dom_son (CDI_DOMINATORS
, son
))
2035 worklist
[sp
++] = son
;
2042 /* Eliminate fully redundant computations. */
2051 block_stmt_iterator i
;
2053 for (i
= bsi_start (b
); !bsi_end_p (i
); bsi_next (&i
))
2055 tree stmt
= bsi_stmt (i
);
2057 /* Lookup the RHS of the expression, see if we have an
2058 available computation for it. If so, replace the RHS with
2059 the available computation. */
2060 if (TREE_CODE (stmt
) == MODIFY_EXPR
2061 && TREE_CODE (TREE_OPERAND (stmt
, 0)) == SSA_NAME
2062 && TREE_CODE (TREE_OPERAND (stmt
,1)) != SSA_NAME
2063 && !is_gimple_min_invariant (TREE_OPERAND (stmt
, 1))
2064 && !stmt_ann (stmt
)->has_volatile_ops
)
2066 tree lhs
= TREE_OPERAND (stmt
, 0);
2067 tree
*rhs_p
= &TREE_OPERAND (stmt
, 1);
2070 sprime
= bitmap_find_leader (AVAIL_OUT (b
),
2071 vn_lookup (lhs
, NULL
));
2074 && (TREE_CODE (*rhs_p
) != SSA_NAME
2075 || may_propagate_copy (*rhs_p
, sprime
)))
2077 gcc_assert (sprime
!= *rhs_p
);
2079 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2081 fprintf (dump_file
, "Replaced ");
2082 print_generic_expr (dump_file
, *rhs_p
, 0);
2083 fprintf (dump_file
, " with ");
2084 print_generic_expr (dump_file
, sprime
, 0);
2085 fprintf (dump_file
, " in ");
2086 print_generic_stmt (dump_file
, stmt
, 0);
2088 if (TREE_CODE (sprime
) == SSA_NAME
)
2089 NECESSARY (SSA_NAME_DEF_STMT (sprime
)) = 1;
2090 pre_stats
.eliminations
++;
2091 propagate_tree_value (rhs_p
, sprime
);
2094 /* If we removed EH side effects from the statement, clean
2095 its EH information. */
2096 if (maybe_clean_eh_stmt (stmt
))
2098 bitmap_set_bit (need_eh_cleanup
,
2099 bb_for_stmt (stmt
)->index
);
2100 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2101 fprintf (dump_file
, " Removed EH side effects.\n");
2109 /* Borrow a bit of tree-ssa-dce.c for the moment.
2110 XXX: In 4.1, we should be able to just run a DCE pass after PRE, though
2111 this may be a bit faster, and we may want critical edges kept split. */
2113 /* If OP's defining statement has not already been determined to be necessary,
2114 mark that statement necessary. Return the stmt, if it is newly
2118 mark_operand_necessary (tree op
)
2124 stmt
= SSA_NAME_DEF_STMT (op
);
2127 if (NECESSARY (stmt
)
2128 || IS_EMPTY_STMT (stmt
))
2131 NECESSARY (stmt
) = 1;
2135 /* Because we don't follow exactly the standard PRE algorithm, and decide not
2136 to insert PHI nodes sometimes, and because value numbering of casts isn't
2137 perfect, we sometimes end up inserting dead code. This simple DCE-like
2138 pass removes any insertions we made that weren't actually used. */
2141 remove_dead_inserted_code (void)
2143 VEC(tree
,heap
) *worklist
= NULL
;
2147 worklist
= VEC_alloc (tree
, heap
, VEC_length (tree
, inserted_exprs
));
2148 for (i
= 0; VEC_iterate (tree
, inserted_exprs
, i
, t
); i
++)
2151 VEC_quick_push (tree
, worklist
, t
);
2153 while (VEC_length (tree
, worklist
) > 0)
2155 t
= VEC_pop (tree
, worklist
);
2156 if (TREE_CODE (t
) == PHI_NODE
)
2158 /* PHI nodes are somewhat special in that each PHI alternative has
2159 data and control dependencies. All the statements feeding the
2160 PHI node's arguments are always necessary. In aggressive mode,
2161 we also consider the control dependent edges leading to the
2162 predecessor block associated with each PHI alternative as
2166 VEC_reserve (tree
, heap
, worklist
, PHI_NUM_ARGS (t
));
2167 for (k
= 0; k
< PHI_NUM_ARGS (t
); k
++)
2169 tree arg
= PHI_ARG_DEF (t
, k
);
2170 if (TREE_CODE (arg
) == SSA_NAME
)
2172 arg
= mark_operand_necessary (arg
);
2174 VEC_quick_push (tree
, worklist
, arg
);
2180 /* Propagate through the operands. Examine all the USE, VUSE and
2181 V_MAY_DEF operands in this statement. Mark all the statements
2182 which feed this statement's uses as necessary. */
2186 /* The operands of V_MAY_DEF expressions are also needed as they
2187 represent potential definitions that may reach this
2188 statement (V_MAY_DEF operands allow us to follow def-def
2191 FOR_EACH_SSA_TREE_OPERAND (use
, t
, iter
, SSA_OP_ALL_USES
)
2193 tree n
= mark_operand_necessary (use
);
2195 VEC_safe_push (tree
, heap
, worklist
, n
);
2199 for (i
= 0; VEC_iterate (tree
, inserted_exprs
, i
, t
); i
++)
2203 block_stmt_iterator bsi
;
2204 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2206 fprintf (dump_file
, "Removing unnecessary insertion:");
2207 print_generic_stmt (dump_file
, t
, 0);
2209 if (TREE_CODE (t
) == PHI_NODE
)
2211 remove_phi_node (t
, NULL
);
2215 bsi
= bsi_for_stmt (t
);
2220 VEC_free (tree
, heap
, worklist
);
2222 /* Initialize data structures used by PRE. */
2225 init_pre (bool do_fre
)
2229 inserted_exprs
= NULL
;
2232 current_loops
= loop_optimizer_init (dump_file
);
2233 connect_infinite_loops_to_exit ();
2234 memset (&pre_stats
, 0, sizeof (pre_stats
));
2236 /* If block 0 has more than one predecessor, it means that its PHI
2237 nodes will have arguments coming from block -1. This creates
2238 problems for several places in PRE that keep local arrays indexed
2239 by block number. To prevent this, we split the edge coming from
2240 ENTRY_BLOCK_PTR (FIXME, if ENTRY_BLOCK_PTR had an index number
2241 different than -1 we wouldn't have to hack this. tree-ssa-dce.c
2242 needs a similar change). */
2243 if (!single_pred_p (single_succ (ENTRY_BLOCK_PTR
)))
2244 if (!(single_succ_edge (ENTRY_BLOCK_PTR
)->flags
& EDGE_ABNORMAL
))
2245 split_edge (single_succ_edge (ENTRY_BLOCK_PTR
));
2248 bb
->aux
= xcalloc (1, sizeof (struct bb_value_sets
));
2250 bitmap_obstack_initialize (&grand_bitmap_obstack
);
2251 phi_translate_table
= htab_create (511, expr_pred_trans_hash
,
2252 expr_pred_trans_eq
, free
);
2253 value_set_pool
= create_alloc_pool ("Value sets",
2254 sizeof (struct value_set
), 30);
2255 bitmap_set_pool
= create_alloc_pool ("Bitmap sets",
2256 sizeof (struct bitmap_set
), 30);
2257 value_set_node_pool
= create_alloc_pool ("Value set nodes",
2258 sizeof (struct value_set_node
), 30);
2259 calculate_dominance_info (CDI_POST_DOMINATORS
);
2260 calculate_dominance_info (CDI_DOMINATORS
);
2261 binary_node_pool
= create_alloc_pool ("Binary tree nodes",
2262 tree_code_size (PLUS_EXPR
), 30);
2263 unary_node_pool
= create_alloc_pool ("Unary tree nodes",
2264 tree_code_size (NEGATE_EXPR
), 30);
2265 reference_node_pool
= create_alloc_pool ("Reference tree nodes",
2266 tree_code_size (ARRAY_REF
), 30);
2269 EXP_GEN (bb
) = set_new (true);
2270 PHI_GEN (bb
) = bitmap_set_new ();
2271 TMP_GEN (bb
) = bitmap_set_new ();
2272 AVAIL_OUT (bb
) = bitmap_set_new ();
2275 need_eh_cleanup
= BITMAP_ALLOC (NULL
);
2279 /* Deallocate data structures used by PRE. */
2282 fini_pre (bool do_fre
)
2287 VEC_free (tree
, heap
, inserted_exprs
);
2288 bitmap_obstack_release (&grand_bitmap_obstack
);
2289 free_alloc_pool (value_set_pool
);
2290 free_alloc_pool (bitmap_set_pool
);
2291 free_alloc_pool (value_set_node_pool
);
2292 free_alloc_pool (binary_node_pool
);
2293 free_alloc_pool (reference_node_pool
);
2294 free_alloc_pool (unary_node_pool
);
2295 htab_delete (phi_translate_table
);
2296 remove_fake_exit_edges ();
2304 free_dominance_info (CDI_POST_DOMINATORS
);
2307 if (!bitmap_empty_p (need_eh_cleanup
))
2309 tree_purge_all_dead_eh_edges (need_eh_cleanup
);
2310 cleanup_tree_cfg ();
2313 BITMAP_FREE (need_eh_cleanup
);
2315 /* Wipe out pointers to VALUE_HANDLEs. In the not terribly distant
2316 future we will want them to be persistent though. */
2317 for (i
= 0; i
< num_ssa_names
; i
++)
2319 tree name
= ssa_name (i
);
2324 if (SSA_NAME_VALUE (name
)
2325 && TREE_CODE (SSA_NAME_VALUE (name
)) == VALUE_HANDLE
)
2326 SSA_NAME_VALUE (name
) = NULL
;
2328 if (!do_fre
&& current_loops
)
2330 loop_optimizer_finalize (current_loops
, dump_file
);
2331 current_loops
= NULL
;
2336 /* Main entry point to the SSA-PRE pass. DO_FRE is true if the caller
2337 only wants to do full redundancy elimination. */
2340 execute_pre (bool do_fre
)
2344 /* Collect and value number expressions computed in each basic block. */
2347 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2353 print_value_set (dump_file
, EXP_GEN (bb
), "exp_gen", bb
->index
);
2354 bitmap_print_value_set (dump_file
, TMP_GEN (bb
), "tmp_gen",
2356 bitmap_print_value_set (dump_file
, AVAIL_OUT (bb
), "avail_out",
2361 /* Insert can get quite slow on an incredibly large number of basic
2362 blocks due to some quadratic behavior. Until this behavior is
2363 fixed, don't run it when he have an incredibly large number of
2364 bb's. If we aren't going to run insert, there is no point in
2365 computing ANTIC, either, even though it's plenty fast. */
2366 if (!do_fre
&& n_basic_blocks
< 4000)
2372 /* Remove all the redundant expressions. */
2376 if (dump_file
&& (dump_flags
& TDF_STATS
))
2378 fprintf (dump_file
, "Insertions: %d\n", pre_stats
.insertions
);
2379 fprintf (dump_file
, "New PHIs: %d\n", pre_stats
.phis
);
2380 fprintf (dump_file
, "Eliminated: %d\n", pre_stats
.eliminations
);
2381 fprintf (dump_file
, "Constified: %d\n", pre_stats
.constified
);
2384 bsi_commit_edge_inserts ();
2386 remove_dead_inserted_code ();
2392 /* Gate and execute functions for PRE. */
2397 execute_pre (false);
2403 return flag_tree_pre
!= 0;
2406 struct tree_opt_pass pass_pre
=
2409 gate_pre
, /* gate */
2410 do_pre
, /* execute */
2413 0, /* static_pass_number */
2414 TV_TREE_PRE
, /* tv_id */
2415 PROP_no_crit_edges
| PROP_cfg
2416 | PROP_ssa
| PROP_alias
, /* properties_required */
2417 0, /* properties_provided */
2418 0, /* properties_destroyed */
2419 0, /* todo_flags_start */
2420 TODO_dump_func
| TODO_ggc_collect
| TODO_verify_ssa
, /* todo_flags_finish */
2425 /* Gate and execute functions for FRE. */
2436 return flag_tree_fre
!= 0;
2439 struct tree_opt_pass pass_fre
=
2442 gate_fre
, /* gate */
2443 execute_fre
, /* execute */
2446 0, /* static_pass_number */
2447 TV_TREE_FRE
, /* tv_id */
2448 PROP_cfg
| PROP_ssa
| PROP_alias
, /* properties_required */
2449 0, /* properties_provided */
2450 0, /* properties_destroyed */
2451 0, /* todo_flags_start */
2452 TODO_dump_func
| TODO_ggc_collect
| TODO_verify_ssa
, /* todo_flags_finish */