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. */
875 tree oldop1
= TREE_OPERAND (expr
, 0);
876 tree oldop2
= TREE_OPERAND (expr
, 1);
881 newop1
= phi_translate (find_leader (set
, oldop1
),
882 set
, pred
, phiblock
);
885 newop2
= phi_translate (find_leader (set
, oldop2
),
886 set
, pred
, phiblock
);
889 if (newop1
!= oldop1
|| newop2
!= oldop2
)
891 newexpr
= pool_alloc (binary_node_pool
);
892 memcpy (newexpr
, expr
, tree_size (expr
));
893 create_tree_ann (newexpr
);
894 TREE_OPERAND (newexpr
, 0) = newop1
== oldop1
? oldop1
: get_value_handle (newop1
);
895 TREE_OPERAND (newexpr
, 1) = newop2
== oldop2
? oldop2
: get_value_handle (newop2
);
896 vn_lookup_or_add (newexpr
, NULL
);
898 phi_trans_add (oldexpr
, newexpr
, pred
);
905 tree oldop1
= TREE_OPERAND (expr
, 0);
909 newop1
= phi_translate (find_leader (set
, oldop1
),
910 set
, pred
, phiblock
);
913 if (newop1
!= oldop1
)
915 newexpr
= pool_alloc (unary_node_pool
);
916 memcpy (newexpr
, expr
, tree_size (expr
));
917 create_tree_ann (newexpr
);
918 TREE_OPERAND (newexpr
, 0) = get_value_handle (newop1
);
919 vn_lookup_or_add (newexpr
, NULL
);
921 phi_trans_add (oldexpr
, newexpr
, pred
);
926 case tcc_exceptional
:
930 gcc_assert (TREE_CODE (expr
) == SSA_NAME
);
931 if (TREE_CODE (SSA_NAME_DEF_STMT (expr
)) == PHI_NODE
)
932 phi
= SSA_NAME_DEF_STMT (expr
);
936 e
= find_edge (pred
, bb_for_stmt (phi
));
939 if (is_undefined_value (PHI_ARG_DEF (phi
, e
->dest_idx
)))
941 vn_lookup_or_add (PHI_ARG_DEF (phi
, e
->dest_idx
), NULL
);
942 return PHI_ARG_DEF (phi
, e
->dest_idx
);
953 phi_translate_set (value_set_t dest
, value_set_t set
, basic_block pred
,
954 basic_block phiblock
)
956 value_set_node_t node
;
957 for (node
= set
->head
;
962 translated
= phi_translate (node
->expr
, set
, pred
, phiblock
);
963 phi_trans_add (node
->expr
, translated
, pred
);
965 if (translated
!= NULL
)
966 value_insert_into_set (dest
, translated
);
970 /* Find the leader for a value (i.e., the name representing that
971 value) in a given set, and return it. Return NULL if no leader is
975 bitmap_find_leader (bitmap_set_t set
, tree val
)
980 if (is_gimple_min_invariant (val
))
982 if (bitmap_set_contains_value (set
, val
))
984 /* Rather than walk the entire bitmap of expressions, and see
985 whether any of them has the value we are looking for, we look
986 at the reverse mapping, which tells us the set of expressions
987 that have a given value (IE value->expressions with that
988 value) and see if any of those expressions are in our set.
989 The number of expressions per value is usually significantly
990 less than the number of expressions in the set. In fact, for
991 large testcases, doing it this way is roughly 5-10x faster
992 than walking the bitmap.
993 If this is somehow a significant lose for some cases, we can
994 choose which set to walk based on which set is smaller. */
996 value_set_node_t node
;
997 exprset
= VALUE_HANDLE_EXPR_SET (val
);
998 for (node
= exprset
->head
; node
; node
= node
->next
)
1000 if (TREE_CODE (node
->expr
) == SSA_NAME
)
1002 if (bitmap_bit_p (set
->expressions
,
1003 SSA_NAME_VERSION (node
->expr
)))
1012 /* Find the leader for a value (i.e., the name representing that
1013 value) in a given set, and return it. Return NULL if no leader is
1017 find_leader (value_set_t set
, tree val
)
1019 value_set_node_t node
;
1024 /* Constants represent themselves. */
1025 if (is_gimple_min_invariant (val
))
1028 if (set
->length
== 0)
1031 if (value_exists_in_set_bitmap (set
, val
))
1033 for (node
= set
->head
;
1037 if (get_value_handle (node
->expr
) == val
)
1045 /* Determine if the expression EXPR is valid in SET. This means that
1046 we have a leader for each part of the expression (if it consists of
1047 values), or the expression is an SSA_NAME.
1049 NB: We never should run into a case where we have SSA_NAME +
1050 SSA_NAME or SSA_NAME + value. The sets valid_in_set is called on,
1051 the ANTIC sets, will only ever have SSA_NAME's or binary value
1052 expression (IE VALUE1 + VALUE2) */
1055 valid_in_set (value_set_t set
, tree expr
)
1057 switch (TREE_CODE_CLASS (TREE_CODE (expr
)))
1061 tree op1
= TREE_OPERAND (expr
, 0);
1062 tree op2
= TREE_OPERAND (expr
, 1);
1063 return set_contains_value (set
, op1
) && set_contains_value (set
, op2
);
1068 tree op1
= TREE_OPERAND (expr
, 0);
1069 return set_contains_value (set
, op1
);
1073 /* XXX: Until PRE of loads works, no reference nodes are ANTIC. */
1076 case tcc_exceptional
:
1077 gcc_assert (TREE_CODE (expr
) == SSA_NAME
);
1081 /* No other cases should be encountered. */
1086 /* Clean the set of expressions that are no longer valid in SET. This
1087 means expressions that are made up of values we have no leaders for
1091 clean (value_set_t set
)
1093 value_set_node_t node
;
1094 value_set_node_t next
;
1099 if (!valid_in_set (set
, node
->expr
))
1100 set_remove (set
, node
->expr
);
1105 DEF_VEC_MALLOC_P (basic_block
);
1106 static sbitmap has_abnormal_preds
;
1108 /* Compute the ANTIC set for BLOCK.
1110 If succs(BLOCK) > 1 then
1111 ANTIC_OUT[BLOCK] = intersection of ANTIC_IN[b] for all succ(BLOCK)
1112 else if succs(BLOCK) == 1 then
1113 ANTIC_OUT[BLOCK] = phi_translate (ANTIC_IN[succ(BLOCK)])
1115 ANTIC_IN[BLOCK] = clean(ANTIC_OUT[BLOCK] U EXP_GEN[BLOCK] - TMP_GEN[BLOCK])
1117 XXX: It would be nice to either write a set_clear, and use it for
1118 ANTIC_OUT, or to mark the antic_out set as deleted at the end
1119 of this routine, so that the pool can hand the same memory back out
1120 again for the next ANTIC_OUT. */
1123 compute_antic_aux (basic_block block
, bool block_has_abnormal_pred_edge
)
1126 bool changed
= false;
1127 value_set_t S
, old
, ANTIC_OUT
;
1128 value_set_node_t node
;
1130 ANTIC_OUT
= S
= NULL
;
1132 /* If any edges from predecessors are abnormal, antic_in is empty,
1134 if (block_has_abnormal_pred_edge
)
1135 goto maybe_dump_sets
;
1137 old
= set_new (false);
1138 set_copy (old
, ANTIC_IN (block
));
1139 ANTIC_OUT
= set_new (true);
1141 /* If the block has no successors, ANTIC_OUT is empty. */
1142 if (EDGE_COUNT (block
->succs
) == 0)
1144 /* If we have one successor, we could have some phi nodes to
1145 translate through. */
1146 else if (single_succ_p (block
))
1148 phi_translate_set (ANTIC_OUT
, ANTIC_IN(single_succ (block
)),
1149 block
, single_succ (block
));
1151 /* If we have multiple successors, we take the intersection of all of
1155 VEC (basic_block
) * worklist
;
1158 basic_block bprime
, first
;
1161 worklist
= VEC_alloc (basic_block
, 2);
1162 FOR_EACH_EDGE (e
, ei
, block
->succs
)
1163 VEC_safe_push (basic_block
, worklist
, e
->dest
);
1164 first
= VEC_index (basic_block
, worklist
, 0);
1165 set_copy (ANTIC_OUT
, ANTIC_IN (first
));
1167 for (i
= 1; VEC_iterate (basic_block
, worklist
, i
, bprime
); i
++)
1169 node
= ANTIC_OUT
->head
;
1173 value_set_node_t next
= node
->next
;
1174 val
= get_value_handle (node
->expr
);
1175 if (!set_contains_value (ANTIC_IN (bprime
), val
))
1176 set_remove (ANTIC_OUT
, node
->expr
);
1180 VEC_free (basic_block
, worklist
);
1183 /* Generate ANTIC_OUT - TMP_GEN. */
1184 S
= bitmap_set_subtract_from_value_set (ANTIC_OUT
, TMP_GEN (block
), false);
1186 /* Start ANTIC_IN with EXP_GEN - TMP_GEN */
1187 ANTIC_IN (block
) = bitmap_set_subtract_from_value_set (EXP_GEN (block
),
1191 /* Then union in the ANTIC_OUT - TMP_GEN values,
1192 to get ANTIC_OUT U EXP_GEN - TMP_GEN */
1193 for (node
= S
->head
; node
; node
= node
->next
)
1194 value_insert_into_set (ANTIC_IN (block
), node
->expr
);
1196 clean (ANTIC_IN (block
));
1197 if (!set_equal (old
, ANTIC_IN (block
)))
1201 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1204 print_value_set (dump_file
, ANTIC_OUT
, "ANTIC_OUT", block
->index
);
1205 print_value_set (dump_file
, ANTIC_IN (block
), "ANTIC_IN", block
->index
);
1207 print_value_set (dump_file
, S
, "S", block
->index
);
1210 for (son
= first_dom_son (CDI_POST_DOMINATORS
, block
);
1212 son
= next_dom_son (CDI_POST_DOMINATORS
, son
))
1214 changed
|= compute_antic_aux (son
,
1215 TEST_BIT (has_abnormal_preds
, son
->index
));
1220 /* Compute ANTIC sets. */
1223 compute_antic (void)
1225 bool changed
= true;
1226 int num_iterations
= 0;
1229 /* If any predecessor edges are abnormal, we punt, so antic_in is empty.
1230 We pre-build the map of blocks with incoming abnormal edges here. */
1231 has_abnormal_preds
= sbitmap_alloc (last_basic_block
);
1232 sbitmap_zero (has_abnormal_preds
);
1238 FOR_EACH_EDGE (e
, ei
, block
->preds
)
1239 if (e
->flags
& EDGE_ABNORMAL
)
1241 SET_BIT (has_abnormal_preds
, block
->index
);
1245 /* While we are here, give empty ANTIC_IN sets to each block. */
1246 ANTIC_IN (block
) = set_new (true);
1248 /* At the exit block we anticipate nothing. */
1249 ANTIC_IN (EXIT_BLOCK_PTR
) = set_new (true);
1255 changed
= compute_antic_aux (EXIT_BLOCK_PTR
, false);
1258 sbitmap_free (has_abnormal_preds
);
1260 if (dump_file
&& (dump_flags
& TDF_STATS
))
1261 fprintf (dump_file
, "compute_antic required %d iterations\n", num_iterations
);
1264 static VEC(tree_on_heap
) *inserted_exprs
;
1265 /* Find a leader for an expression, or generate one using
1266 create_expression_by_pieces if it's ANTIC but
1268 BLOCK is the basic_block we are looking for leaders in.
1269 EXPR is the expression to find a leader or generate for.
1270 STMTS is the statement list to put the inserted expressions on.
1271 Returns the SSA_NAME of the LHS of the generated expression or the
1275 find_or_generate_expression (basic_block block
, tree expr
, tree stmts
)
1277 tree genop
= bitmap_find_leader (AVAIL_OUT (block
), expr
);
1279 /* If it's still NULL, see if it is a complex expression, and if
1280 so, generate it recursively, otherwise, abort, because it's
1284 genop
= VALUE_HANDLE_EXPR_SET (expr
)->head
->expr
;
1285 gcc_assert (UNARY_CLASS_P (genop
)
1286 || BINARY_CLASS_P (genop
)
1287 || REFERENCE_CLASS_P (genop
));
1288 genop
= create_expression_by_pieces (block
, genop
, stmts
);
1293 #define NECESSARY(stmt) stmt->common.asm_written_flag
1294 /* Create an expression in pieces, so that we can handle very complex
1295 expressions that may be ANTIC, but not necessary GIMPLE.
1296 BLOCK is the basic block the expression will be inserted into,
1297 EXPR is the expression to insert (in value form)
1298 STMTS is a statement list to append the necessary insertions into.
1300 This function will abort if we hit some value that shouldn't be
1301 ANTIC but is (IE there is no leader for it, or its components).
1302 This function may also generate expressions that are themselves
1303 partially or fully redundant. Those that are will be either made
1304 fully redundant during the next iteration of insert (for partially
1305 redundant ones), or eliminated by eliminate (for fully redundant
1309 create_expression_by_pieces (basic_block block
, tree expr
, tree stmts
)
1311 tree name
= NULL_TREE
;
1312 tree newexpr
= NULL_TREE
;
1315 switch (TREE_CODE_CLASS (TREE_CODE (expr
)))
1319 tree_stmt_iterator tsi
;
1320 tree genop1
, genop2
;
1322 tree op1
= TREE_OPERAND (expr
, 0);
1323 tree op2
= TREE_OPERAND (expr
, 1);
1324 genop1
= find_or_generate_expression (block
, op1
, stmts
);
1325 genop2
= find_or_generate_expression (block
, op2
, stmts
);
1326 temp
= create_tmp_var (TREE_TYPE (expr
), "pretmp");
1327 add_referenced_tmp_var (temp
);
1328 newexpr
= fold (build (TREE_CODE (expr
), TREE_TYPE (expr
),
1330 newexpr
= build (MODIFY_EXPR
, TREE_TYPE (expr
),
1332 NECESSARY (newexpr
) = 0;
1333 name
= make_ssa_name (temp
, newexpr
);
1334 TREE_OPERAND (newexpr
, 0) = name
;
1335 tsi
= tsi_last (stmts
);
1336 tsi_link_after (&tsi
, newexpr
, TSI_CONTINUE_LINKING
);
1337 VEC_safe_push (tree_on_heap
, inserted_exprs
, newexpr
);
1338 pre_stats
.insertions
++;
1343 tree_stmt_iterator tsi
;
1346 tree op1
= TREE_OPERAND (expr
, 0);
1347 genop1
= find_or_generate_expression (block
, op1
, stmts
);
1348 temp
= create_tmp_var (TREE_TYPE (expr
), "pretmp");
1349 add_referenced_tmp_var (temp
);
1350 newexpr
= fold (build (TREE_CODE (expr
), TREE_TYPE (expr
),
1352 newexpr
= build (MODIFY_EXPR
, TREE_TYPE (expr
),
1354 name
= make_ssa_name (temp
, newexpr
);
1355 TREE_OPERAND (newexpr
, 0) = name
;
1356 NECESSARY (newexpr
) = 0;
1357 tsi
= tsi_last (stmts
);
1358 tsi_link_after (&tsi
, newexpr
, TSI_CONTINUE_LINKING
);
1359 VEC_safe_push (tree_on_heap
, inserted_exprs
, newexpr
);
1360 pre_stats
.insertions
++;
1368 v
= get_value_handle (expr
);
1369 vn_add (name
, v
, NULL
);
1371 /* The value may already exist in either NEW_SETS, or AVAIL_OUT, because
1372 we are creating the expression by pieces, and this particular piece of
1373 the expression may have been represented. There is no harm in replacing
1375 bitmap_value_replace_in_set (NEW_SETS (block
), name
);
1376 bitmap_value_replace_in_set (AVAIL_OUT (block
), name
);
1377 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1379 fprintf (dump_file
, "Inserted ");
1380 print_generic_expr (dump_file
, newexpr
, 0);
1381 fprintf (dump_file
, " in predecessor %d\n", block
->index
);
1386 /* Return the folded version of T if T, when folded, is a gimple
1387 min_invariant. Otherwise, return T. */
1390 fully_constant_expression (tree t
)
1394 if (folded
&& is_gimple_min_invariant (folded
))
1399 /* Insert the to-be-made-available values of NODE for each predecessor, stored
1400 in AVAIL, into the predecessors of BLOCK, and merge the result with a phi
1401 node, given the same value handle as NODE. The prefix of the phi node is
1402 given with TMPNAME. Return true if we have inserted new stuff. */
1405 insert_into_preds_of_block (basic_block block
, value_set_node_t node
,
1406 tree
*avail
, const char *tmpname
)
1408 tree val
= get_value_handle (node
->expr
);
1410 bool insertions
= false;
1415 tree type
= TREE_TYPE (avail
[EDGE_PRED (block
, 0)->src
->index
]);
1418 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1420 fprintf (dump_file
, "Found partial redundancy for expression ");
1421 print_generic_expr (dump_file
, node
->expr
, 0);
1422 fprintf (dump_file
, "\n");
1425 /* Make sure we aren't creating an induction variable. */
1426 if (block
->loop_depth
> 0 && EDGE_COUNT (block
->preds
) == 2)
1428 bool firstinsideloop
= false;
1429 bool secondinsideloop
= false;
1430 firstinsideloop
= flow_bb_inside_loop_p (block
->loop_father
,
1431 EDGE_PRED (block
, 0)->src
);
1432 secondinsideloop
= flow_bb_inside_loop_p (block
->loop_father
,
1433 EDGE_PRED (block
, 1)->src
);
1434 /* Induction variables only have one edge inside the loop. */
1435 if (firstinsideloop
^ secondinsideloop
)
1437 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1438 fprintf (dump_file
, "Skipping insertion of phi for partial redundancy: Looks like an induction variable\n");
1444 /* Make the necessary insertions. */
1445 FOR_EACH_EDGE (pred
, ei
, block
->preds
)
1447 tree stmts
= alloc_stmt_list ();
1450 eprime
= avail
[bprime
->index
];
1451 if (BINARY_CLASS_P (eprime
)
1452 || UNARY_CLASS_P (eprime
))
1454 builtexpr
= create_expression_by_pieces (bprime
,
1457 bsi_insert_on_edge (pred
, stmts
);
1458 avail
[bprime
->index
] = builtexpr
;
1462 /* If we didn't want a phi node, and we made insertions, we still have
1463 inserted new stuff, and thus return true. If we didn't want a phi node,
1464 and didn't make insertions, we haven't added anything new, so return
1466 if (nophi
&& insertions
)
1468 else if (nophi
&& !insertions
)
1471 /* Now build a phi for the new variable. */
1472 temp
= create_tmp_var (type
, tmpname
);
1473 add_referenced_tmp_var (temp
);
1474 temp
= create_phi_node (temp
, block
);
1475 NECESSARY (temp
) = 0;
1476 VEC_safe_push (tree_on_heap
, inserted_exprs
, temp
);
1477 FOR_EACH_EDGE (pred
, ei
, block
->preds
)
1478 add_phi_arg (temp
, avail
[pred
->src
->index
], pred
);
1480 vn_add (PHI_RESULT (temp
), val
, NULL
);
1482 /* The value should *not* exist in PHI_GEN, or else we wouldn't be doing
1483 this insertion, since we test for the existence of this value in PHI_GEN
1484 before proceeding with the partial redundancy checks in insert_aux.
1486 The value may exist in AVAIL_OUT, in particular, it could be represented
1487 by the expression we are trying to eliminate, in which case we want the
1488 replacement to occur. If it's not existing in AVAIL_OUT, we want it
1491 Similarly, to the PHI_GEN case, the value should not exist in NEW_SETS of
1492 this block, because if it did, it would have existed in our dominator's
1493 AVAIL_OUT, and would have been skipped due to the full redundancy check.
1496 bitmap_insert_into_set (PHI_GEN (block
),
1498 bitmap_value_replace_in_set (AVAIL_OUT (block
),
1500 bitmap_insert_into_set (NEW_SETS (block
),
1503 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1505 fprintf (dump_file
, "Created phi ");
1506 print_generic_expr (dump_file
, temp
, 0);
1507 fprintf (dump_file
, " in block %d\n", block
->index
);
1515 /* Perform insertion of partially redundant values.
1516 For BLOCK, do the following:
1517 1. Propagate the NEW_SETS of the dominator into the current block.
1518 If the block has multiple predecessors,
1519 2a. Iterate over the ANTIC expressions for the block to see if
1520 any of them are partially redundant.
1521 2b. If so, insert them into the necessary predecessors to make
1522 the expression fully redundant.
1523 2c. Insert a new PHI merging the values of the predecessors.
1524 2d. Insert the new PHI, and the new expressions, into the
1526 3. Recursively call ourselves on the dominator children of BLOCK.
1531 insert_aux (basic_block block
)
1534 bool new_stuff
= false;
1539 dom
= get_immediate_dominator (CDI_DOMINATORS
, block
);
1544 bitmap_set_t newset
= NEW_SETS (dom
);
1547 /* Note that we need to value_replace both NEW_SETS, and
1548 AVAIL_OUT. For both the case of NEW_SETS, the value may be
1549 represented by some non-simple expression here that we want
1550 to replace it with. */
1551 EXECUTE_IF_SET_IN_BITMAP (newset
->expressions
, 0, i
, bi
)
1553 bitmap_value_replace_in_set (NEW_SETS (block
), ssa_name (i
));
1554 bitmap_value_replace_in_set (AVAIL_OUT (block
), ssa_name (i
));
1557 if (!single_pred_p (block
))
1559 value_set_node_t node
;
1560 for (node
= ANTIC_IN (block
)->head
;
1564 if (BINARY_CLASS_P (node
->expr
)
1565 || UNARY_CLASS_P (node
->expr
))
1569 bool by_some
= false;
1570 bool cant_insert
= false;
1571 bool all_same
= true;
1572 tree first_s
= NULL
;
1575 tree eprime
= NULL_TREE
;
1578 val
= get_value_handle (node
->expr
);
1579 if (bitmap_set_contains_value (PHI_GEN (block
), val
))
1581 if (bitmap_set_contains_value (AVAIL_OUT (dom
), val
))
1583 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1584 fprintf (dump_file
, "Found fully redundant value\n");
1588 avail
= xcalloc (last_basic_block
, sizeof (tree
));
1589 FOR_EACH_EDGE (pred
, ei
, block
->preds
)
1594 /* This can happen in the very weird case
1595 that our fake infinite loop edges have caused a
1596 critical edge to appear. */
1597 if (EDGE_CRITICAL_P (pred
))
1603 eprime
= phi_translate (node
->expr
,
1607 /* eprime will generally only be NULL if the
1608 value of the expression, translated
1609 through the PHI for this predecessor, is
1610 undefined. If that is the case, we can't
1611 make the expression fully redundant,
1612 because its value is undefined along a
1613 predecessor path. We can thus break out
1614 early because it doesn't matter what the
1615 rest of the results are. */
1622 eprime
= fully_constant_expression (eprime
);
1623 vprime
= get_value_handle (eprime
);
1624 gcc_assert (vprime
);
1625 edoubleprime
= bitmap_find_leader (AVAIL_OUT (bprime
),
1627 if (edoubleprime
== NULL
)
1629 avail
[bprime
->index
] = eprime
;
1634 avail
[bprime
->index
] = edoubleprime
;
1636 if (first_s
== NULL
)
1637 first_s
= edoubleprime
;
1638 else if (!operand_equal_p (first_s
, edoubleprime
,
1643 /* If we can insert it, it's not the same value
1644 already existing along every predecessor, and
1645 it's defined by some predecessor, it is
1646 partially redundant. */
1647 if (!cant_insert
&& !all_same
&& by_some
)
1649 if (insert_into_preds_of_block (block
, node
, avail
,
1653 /* If all edges produce the same value and that value is
1654 an invariant, then the PHI has the same value on all
1655 edges. Note this. */
1656 else if (all_same
&& eprime
1657 && is_gimple_min_invariant (eprime
)
1658 && !is_gimple_min_invariant (val
))
1660 value_set_t exprset
= VALUE_HANDLE_EXPR_SET (val
);
1661 value_set_node_t node
;
1662 for (node
= exprset
->head
; node
; node
= node
->next
)
1664 if (TREE_CODE (node
->expr
) == SSA_NAME
)
1666 vn_add (node
->expr
, eprime
, NULL
);
1667 pre_stats
.constified
++;
1677 for (son
= first_dom_son (CDI_DOMINATORS
, block
);
1679 son
= next_dom_son (CDI_DOMINATORS
, son
))
1681 new_stuff
|= insert_aux (son
);
1687 /* Perform insertion of partially redundant values. */
1692 bool new_stuff
= true;
1694 int num_iterations
= 0;
1697 NEW_SETS (bb
) = bitmap_set_new ();
1703 new_stuff
= insert_aux (ENTRY_BLOCK_PTR
);
1705 if (num_iterations
> 2 && dump_file
&& (dump_flags
& TDF_STATS
))
1706 fprintf (dump_file
, "insert required %d iterations\n", num_iterations
);
1710 /* Return true if VAR is an SSA variable with no defining statement in
1711 this procedure, *AND* isn't a live-on-entry parameter. */
1714 is_undefined_value (tree expr
)
1716 return (TREE_CODE (expr
) == SSA_NAME
1717 && IS_EMPTY_STMT (SSA_NAME_DEF_STMT (expr
))
1718 /* PARM_DECLs and hard registers are always defined. */
1719 && TREE_CODE (SSA_NAME_VAR (expr
)) != PARM_DECL
);
1723 /* Given an SSA variable VAR and an expression EXPR, compute the value
1724 number for EXPR and create a value handle (VAL) for it. If VAR and
1725 EXPR are not the same, associate VAL with VAR. Finally, add VAR to
1726 S1 and its value handle to S2.
1728 VUSES represent the virtual use operands associated with EXPR (if
1729 any). They are used when computing the hash value for EXPR. */
1732 add_to_sets (tree var
, tree expr
, vuse_optype vuses
, bitmap_set_t s1
,
1735 tree val
= vn_lookup_or_add (expr
, vuses
);
1737 /* VAR and EXPR may be the same when processing statements for which
1738 we are not computing value numbers (e.g., non-assignments, or
1739 statements that make aliased stores). In those cases, we are
1740 only interested in making VAR available as its own value. */
1742 vn_add (var
, val
, NULL
);
1745 bitmap_insert_into_set (s1
, var
);
1746 bitmap_value_insert_into_set (s2
, var
);
1750 /* Given a unary or binary expression EXPR, create and return a new
1751 expression with the same structure as EXPR but with its operands
1752 replaced with the value handles of each of the operands of EXPR.
1753 Insert EXPR's operands into the EXP_GEN set for BLOCK.
1755 VUSES represent the virtual use operands associated with EXPR (if
1756 any). They are used when computing the hash value for EXPR. */
1759 create_value_expr_from (tree expr
, basic_block block
, vuse_optype vuses
)
1762 enum tree_code code
= TREE_CODE (expr
);
1765 gcc_assert (TREE_CODE_CLASS (code
) == tcc_unary
1766 || TREE_CODE_CLASS (code
) == tcc_binary
1767 || TREE_CODE_CLASS (code
) == tcc_reference
);
1769 if (TREE_CODE_CLASS (code
) == tcc_unary
)
1770 vexpr
= pool_alloc (unary_node_pool
);
1771 else if (TREE_CODE_CLASS (code
) == tcc_reference
)
1772 vexpr
= pool_alloc (reference_node_pool
);
1774 vexpr
= pool_alloc (binary_node_pool
);
1776 memcpy (vexpr
, expr
, tree_size (expr
));
1778 for (i
= 0; i
< TREE_CODE_LENGTH (code
); i
++)
1780 tree op
= TREE_OPERAND (expr
, i
);
1783 tree val
= vn_lookup_or_add (op
, vuses
);
1784 if (!is_undefined_value (op
))
1785 value_insert_into_set (EXP_GEN (block
), op
);
1786 if (TREE_CODE (val
) == VALUE_HANDLE
)
1787 TREE_TYPE (val
) = TREE_TYPE (TREE_OPERAND (vexpr
, i
));
1788 TREE_OPERAND (vexpr
, i
) = val
;
1796 /* Compute the AVAIL set for all basic blocks.
1798 This function performs value numbering of the statements in each basic
1799 block. The AVAIL sets are built from information we glean while doing
1800 this value numbering, since the AVAIL sets contain only one entry per
1803 AVAIL_IN[BLOCK] = AVAIL_OUT[dom(BLOCK)].
1804 AVAIL_OUT[BLOCK] = AVAIL_IN[BLOCK] U PHI_GEN[BLOCK] U TMP_GEN[BLOCK]. */
1807 compute_avail (void)
1809 basic_block block
, son
;
1810 basic_block
*worklist
;
1814 /* For arguments with default definitions, we pretend they are
1815 defined in the entry block. */
1816 for (param
= DECL_ARGUMENTS (current_function_decl
);
1818 param
= TREE_CHAIN (param
))
1820 if (default_def (param
) != NULL
)
1822 tree def
= default_def (param
);
1823 vn_lookup_or_add (def
, NULL
);
1824 bitmap_insert_into_set (TMP_GEN (ENTRY_BLOCK_PTR
), def
);
1825 bitmap_value_insert_into_set (AVAIL_OUT (ENTRY_BLOCK_PTR
), def
);
1829 /* Allocate the worklist. */
1830 worklist
= xmalloc (sizeof (basic_block
) * n_basic_blocks
);
1832 /* Seed the algorithm by putting the dominator children of the entry
1833 block on the worklist. */
1834 for (son
= first_dom_son (CDI_DOMINATORS
, ENTRY_BLOCK_PTR
);
1836 son
= next_dom_son (CDI_DOMINATORS
, son
))
1837 worklist
[sp
++] = son
;
1839 /* Loop until the worklist is empty. */
1842 block_stmt_iterator bsi
;
1846 /* Pick a block from the worklist. */
1847 block
= worklist
[--sp
];
1849 /* Initially, the set of available values in BLOCK is that of
1850 its immediate dominator. */
1851 dom
= get_immediate_dominator (CDI_DOMINATORS
, block
);
1853 bitmap_set_copy (AVAIL_OUT (block
), AVAIL_OUT (dom
));
1855 /* Generate values for PHI nodes. */
1856 for (phi
= phi_nodes (block
); phi
; phi
= PHI_CHAIN (phi
))
1857 /* We have no need for virtual phis, as they don't represent
1858 actual computations. */
1859 if (is_gimple_reg (PHI_RESULT (phi
)))
1860 add_to_sets (PHI_RESULT (phi
), PHI_RESULT (phi
), NULL
,
1861 PHI_GEN (block
), AVAIL_OUT (block
));
1863 /* Now compute value numbers and populate value sets with all
1864 the expressions computed in BLOCK. */
1865 for (bsi
= bsi_start (block
); !bsi_end_p (bsi
); bsi_next (&bsi
))
1870 stmt
= bsi_stmt (bsi
);
1871 ann
= stmt_ann (stmt
);
1872 get_stmt_operands (stmt
);
1874 /* We are only interested in assignments of the form
1875 X_i = EXPR, where EXPR represents an "interesting"
1876 computation, it has no volatile operands and X_i
1877 doesn't flow through an abnormal edge. */
1878 if (TREE_CODE (stmt
) == MODIFY_EXPR
1879 && !ann
->has_volatile_ops
1880 && TREE_CODE (TREE_OPERAND (stmt
, 0)) == SSA_NAME
1881 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (TREE_OPERAND (stmt
, 0)))
1883 tree lhs
= TREE_OPERAND (stmt
, 0);
1884 tree rhs
= TREE_OPERAND (stmt
, 1);
1885 vuse_optype vuses
= STMT_VUSE_OPS (stmt
);
1887 STRIP_USELESS_TYPE_CONVERSION (rhs
);
1888 if (TREE_CODE (rhs
) == SSA_NAME
1889 || is_gimple_min_invariant (rhs
))
1891 /* Compute a value number for the RHS of the statement
1892 and add its value to the AVAIL_OUT set for the block.
1893 Add the LHS to TMP_GEN. */
1894 add_to_sets (lhs
, rhs
, vuses
, TMP_GEN (block
),
1897 if (TREE_CODE (rhs
) == SSA_NAME
1898 && !is_undefined_value (rhs
))
1899 value_insert_into_set (EXP_GEN (block
), rhs
);
1902 else if (UNARY_CLASS_P (rhs
) || BINARY_CLASS_P (rhs
)
1903 || TREE_CODE (rhs
) == INDIRECT_REF
)
1905 /* For binary, unary, and reference expressions,
1906 create a duplicate expression with the operands
1907 replaced with the value handles of the original
1909 tree newt
= create_value_expr_from (rhs
, block
, vuses
);
1910 add_to_sets (lhs
, newt
, vuses
, TMP_GEN (block
),
1912 value_insert_into_set (EXP_GEN (block
), newt
);
1917 /* For any other statement that we don't recognize, simply
1918 make the names generated by the statement available in
1919 AVAIL_OUT and TMP_GEN. */
1920 for (j
= 0; j
< NUM_DEFS (STMT_DEF_OPS (stmt
)); j
++)
1922 tree def
= DEF_OP (STMT_DEF_OPS (stmt
), j
);
1923 add_to_sets (def
, def
, NULL
, TMP_GEN (block
),
1927 for (j
= 0; j
< NUM_USES (STMT_USE_OPS (stmt
)); j
++)
1929 tree use
= USE_OP (STMT_USE_OPS (stmt
), j
);
1930 add_to_sets (use
, use
, NULL
, NULL
, AVAIL_OUT (block
));
1934 /* Put the dominator children of BLOCK on the worklist of blocks
1935 to compute available sets for. */
1936 for (son
= first_dom_son (CDI_DOMINATORS
, block
);
1938 son
= next_dom_son (CDI_DOMINATORS
, son
))
1939 worklist
[sp
++] = son
;
1946 /* Eliminate fully redundant computations. */
1955 block_stmt_iterator i
;
1957 for (i
= bsi_start (b
); !bsi_end_p (i
); bsi_next (&i
))
1959 tree stmt
= bsi_stmt (i
);
1961 /* Lookup the RHS of the expression, see if we have an
1962 available computation for it. If so, replace the RHS with
1963 the available computation. */
1964 if (TREE_CODE (stmt
) == MODIFY_EXPR
1965 && TREE_CODE (TREE_OPERAND (stmt
, 0)) == SSA_NAME
1966 && TREE_CODE (TREE_OPERAND (stmt
,1)) != SSA_NAME
1967 && !is_gimple_min_invariant (TREE_OPERAND (stmt
, 1))
1968 && !stmt_ann (stmt
)->has_volatile_ops
)
1970 tree lhs
= TREE_OPERAND (stmt
, 0);
1971 tree
*rhs_p
= &TREE_OPERAND (stmt
, 1);
1974 sprime
= bitmap_find_leader (AVAIL_OUT (b
),
1975 vn_lookup (lhs
, NULL
));
1978 && (TREE_CODE (*rhs_p
) != SSA_NAME
1979 || may_propagate_copy (*rhs_p
, sprime
)))
1981 gcc_assert (sprime
!= *rhs_p
);
1983 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1985 fprintf (dump_file
, "Replaced ");
1986 print_generic_expr (dump_file
, *rhs_p
, 0);
1987 fprintf (dump_file
, " with ");
1988 print_generic_expr (dump_file
, sprime
, 0);
1989 fprintf (dump_file
, " in ");
1990 print_generic_stmt (dump_file
, stmt
, 0);
1992 if (TREE_CODE (sprime
) == SSA_NAME
)
1993 NECESSARY (SSA_NAME_DEF_STMT (sprime
)) = 1;
1994 pre_stats
.eliminations
++;
1995 propagate_tree_value (rhs_p
, sprime
);
1998 /* If we removed EH side effects from the statement, clean
1999 its EH information. */
2000 if (maybe_clean_eh_stmt (stmt
))
2002 bitmap_set_bit (need_eh_cleanup
,
2003 bb_for_stmt (stmt
)->index
);
2004 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2005 fprintf (dump_file
, " Removed EH side effects.\n");
2013 /* Borrow a bit of tree-ssa-dce.c for the moment.
2014 XXX: In 4.1, we should be able to just run a DCE pass after PRE, though
2015 this may be a bit faster, and we may want critical edges kept split. */
2017 /* If OP's defining statement has not already been determined to be necessary,
2018 mark that statement necessary. and place it on the WORKLIST. */
2021 mark_operand_necessary (tree op
, VEC(tree_on_heap
) **worklist
)
2027 stmt
= SSA_NAME_DEF_STMT (op
);
2030 if (NECESSARY (stmt
)
2031 || IS_EMPTY_STMT (stmt
))
2034 NECESSARY (stmt
) = 1;
2035 VEC_safe_push (tree_on_heap
, *worklist
, stmt
);
2038 /* Because we don't follow exactly the standard PRE algorithm, and decide not
2039 to insert PHI nodes sometimes, and because value numbering of casts isn't
2040 perfect, we sometimes end up inserting dead code. This simple DCE-like
2041 pass removes any insertions we made that weren't actually used. */
2044 remove_dead_inserted_code (void)
2046 VEC (tree_on_heap
) *worklist
= NULL
;
2050 for (i
= 0; VEC_iterate (tree_on_heap
, inserted_exprs
, i
, t
); i
++)
2053 VEC_safe_push (tree_on_heap
, worklist
, t
);
2055 while (VEC_length (tree_on_heap
, worklist
) > 0)
2057 t
= VEC_pop (tree_on_heap
, worklist
);
2058 if (TREE_CODE (t
) == PHI_NODE
)
2060 /* PHI nodes are somewhat special in that each PHI alternative has
2061 data and control dependencies. All the statements feeding the
2062 PHI node's arguments are always necessary. In aggressive mode,
2063 we also consider the control dependent edges leading to the
2064 predecessor block associated with each PHI alternative as
2067 for (k
= 0; k
< PHI_NUM_ARGS (t
); k
++)
2069 tree arg
= PHI_ARG_DEF (t
, k
);
2070 if (TREE_CODE (arg
) == SSA_NAME
)
2071 mark_operand_necessary (arg
, &worklist
);
2076 /* Propagate through the operands. Examine all the USE, VUSE and
2077 V_MAY_DEF operands in this statement. Mark all the statements
2078 which feed this statement's uses as necessary. */
2082 get_stmt_operands (t
);
2084 /* The operands of V_MAY_DEF expressions are also needed as they
2085 represent potential definitions that may reach this
2086 statement (V_MAY_DEF operands allow us to follow def-def
2089 FOR_EACH_SSA_TREE_OPERAND (use
, t
, iter
, SSA_OP_ALL_USES
)
2090 mark_operand_necessary (use
, &worklist
);
2093 for (i
= 0; VEC_iterate (tree_on_heap
, inserted_exprs
, i
, t
); i
++)
2097 block_stmt_iterator bsi
;
2098 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2100 fprintf (dump_file
, "Removing unnecessary insertion:");
2101 print_generic_stmt (dump_file
, t
, 0);
2103 if (TREE_CODE (t
) == PHI_NODE
)
2105 remove_phi_node (t
, NULL
);
2109 bsi
= bsi_for_stmt (t
);
2114 VEC_free (tree_on_heap
, worklist
);
2116 /* Initialize data structures used by PRE. */
2119 init_pre (bool do_fre
)
2123 inserted_exprs
= NULL
;
2126 current_loops
= loop_optimizer_init (dump_file
);
2127 connect_infinite_loops_to_exit ();
2128 memset (&pre_stats
, 0, sizeof (pre_stats
));
2130 /* If block 0 has more than one predecessor, it means that its PHI
2131 nodes will have arguments coming from block -1. This creates
2132 problems for several places in PRE that keep local arrays indexed
2133 by block number. To prevent this, we split the edge coming from
2134 ENTRY_BLOCK_PTR (FIXME, if ENTRY_BLOCK_PTR had an index number
2135 different than -1 we wouldn't have to hack this. tree-ssa-dce.c
2136 needs a similar change). */
2137 if (!single_pred_p (single_succ (ENTRY_BLOCK_PTR
)))
2138 if (!(single_succ_edge (ENTRY_BLOCK_PTR
)->flags
& EDGE_ABNORMAL
))
2139 split_edge (single_succ_edge (ENTRY_BLOCK_PTR
));
2142 bb
->aux
= xcalloc (1, sizeof (struct bb_value_sets
));
2144 bitmap_obstack_initialize (&grand_bitmap_obstack
);
2145 phi_translate_table
= htab_create (511, expr_pred_trans_hash
,
2146 expr_pred_trans_eq
, free
);
2147 value_set_pool
= create_alloc_pool ("Value sets",
2148 sizeof (struct value_set
), 30);
2149 bitmap_set_pool
= create_alloc_pool ("Bitmap sets",
2150 sizeof (struct bitmap_set
), 30);
2151 value_set_node_pool
= create_alloc_pool ("Value set nodes",
2152 sizeof (struct value_set_node
), 30);
2153 calculate_dominance_info (CDI_POST_DOMINATORS
);
2154 calculate_dominance_info (CDI_DOMINATORS
);
2155 binary_node_pool
= create_alloc_pool ("Binary tree nodes",
2156 tree_code_size (PLUS_EXPR
), 30);
2157 unary_node_pool
= create_alloc_pool ("Unary tree nodes",
2158 tree_code_size (NEGATE_EXPR
), 30);
2159 reference_node_pool
= create_alloc_pool ("Reference tree nodes",
2160 tree_code_size (ARRAY_REF
), 30);
2163 EXP_GEN (bb
) = set_new (true);
2164 PHI_GEN (bb
) = bitmap_set_new ();
2165 TMP_GEN (bb
) = bitmap_set_new ();
2166 AVAIL_OUT (bb
) = bitmap_set_new ();
2169 need_eh_cleanup
= BITMAP_ALLOC (NULL
);
2173 /* Deallocate data structures used by PRE. */
2176 fini_pre (bool do_fre
)
2181 VEC_free (tree_on_heap
, inserted_exprs
);
2182 bitmap_obstack_release (&grand_bitmap_obstack
);
2183 free_alloc_pool (value_set_pool
);
2184 free_alloc_pool (bitmap_set_pool
);
2185 free_alloc_pool (value_set_node_pool
);
2186 free_alloc_pool (binary_node_pool
);
2187 free_alloc_pool (reference_node_pool
);
2188 free_alloc_pool (unary_node_pool
);
2189 htab_delete (phi_translate_table
);
2190 remove_fake_exit_edges ();
2198 free_dominance_info (CDI_POST_DOMINATORS
);
2201 if (!bitmap_empty_p (need_eh_cleanup
))
2203 tree_purge_all_dead_eh_edges (need_eh_cleanup
);
2204 cleanup_tree_cfg ();
2207 BITMAP_FREE (need_eh_cleanup
);
2209 /* Wipe out pointers to VALUE_HANDLEs. In the not terribly distant
2210 future we will want them to be persistent though. */
2211 for (i
= 0; i
< num_ssa_names
; i
++)
2213 tree name
= ssa_name (i
);
2218 if (SSA_NAME_VALUE (name
)
2219 && TREE_CODE (SSA_NAME_VALUE (name
)) == VALUE_HANDLE
)
2220 SSA_NAME_VALUE (name
) = NULL
;
2222 if (!do_fre
&& current_loops
)
2224 loop_optimizer_finalize (current_loops
, dump_file
);
2225 current_loops
= NULL
;
2230 /* Main entry point to the SSA-PRE pass. DO_FRE is true if the caller
2231 only wants to do full redundancy elimination. */
2234 execute_pre (bool do_fre
)
2238 /* Collect and value number expressions computed in each basic block. */
2241 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2247 print_value_set (dump_file
, EXP_GEN (bb
), "exp_gen", bb
->index
);
2248 bitmap_print_value_set (dump_file
, TMP_GEN (bb
), "tmp_gen",
2250 bitmap_print_value_set (dump_file
, AVAIL_OUT (bb
), "avail_out",
2255 /* Insert can get quite slow on an incredibly large number of basic
2256 blocks due to some quadratic behavior. Until this behavior is
2257 fixed, don't run it when he have an incredibly large number of
2258 bb's. If we aren't going to run insert, there is no point in
2259 computing ANTIC, either, even though it's plenty fast. */
2260 if (!do_fre
&& n_basic_blocks
< 4000)
2266 /* Remove all the redundant expressions. */
2270 if (dump_file
&& (dump_flags
& TDF_STATS
))
2272 fprintf (dump_file
, "Insertions:%d\n", pre_stats
.insertions
);
2273 fprintf (dump_file
, "New PHIs:%d\n", pre_stats
.phis
);
2274 fprintf (dump_file
, "Eliminated:%d\n", pre_stats
.eliminations
);
2275 fprintf (dump_file
, "Constified:%d\n", pre_stats
.constified
);
2278 bsi_commit_edge_inserts ();
2280 remove_dead_inserted_code ();
2286 /* Gate and execute functions for PRE. */
2291 execute_pre (false);
2297 return flag_tree_pre
!= 0;
2300 struct tree_opt_pass pass_pre
=
2303 gate_pre
, /* gate */
2304 do_pre
, /* execute */
2307 0, /* static_pass_number */
2308 TV_TREE_PRE
, /* tv_id */
2309 PROP_no_crit_edges
| PROP_cfg
2310 | PROP_ssa
| PROP_alias
, /* properties_required */
2311 0, /* properties_provided */
2312 0, /* properties_destroyed */
2313 0, /* todo_flags_start */
2314 TODO_dump_func
| TODO_ggc_collect
| TODO_verify_ssa
, /* todo_flags_finish */
2319 /* Gate and execute functions for FRE. */
2330 return flag_tree_fre
!= 0;
2333 struct tree_opt_pass pass_fre
=
2336 gate_fre
, /* gate */
2337 do_fre
, /* execute */
2340 0, /* static_pass_number */
2341 TV_TREE_FRE
, /* tv_id */
2342 PROP_cfg
| PROP_ssa
| PROP_alias
, /* properties_required */
2343 0, /* properties_provided */
2344 0, /* properties_destroyed */
2345 0, /* todo_flags_start */
2346 TODO_dump_func
| TODO_ggc_collect
| TODO_verify_ssa
, /* todo_flags_finish */