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, 51 Franklin Street, Fifth Floor,
21 Boston, MA 02110-1301, USA. */
25 #include "coretypes.h"
29 #include "basic-block.h"
30 #include "diagnostic.h"
31 #include "tree-inline.h"
32 #include "tree-flow.h"
33 #include "tree-gimple.h"
34 #include "tree-dump.h"
38 #include "tree-iterator.h"
40 #include "alloc-pool.h"
41 #include "tree-pass.h"
44 #include "langhooks.h"
49 1. Avail sets can be shared by making an avail_find_leader that
50 walks up the dominator tree and looks in those avail sets.
51 This might affect code optimality, it's unclear right now.
52 2. Strength reduction can be performed by anticipating expressions
53 we can repair later on.
54 3. We can do back-substitution or smarter value numbering to catch
55 commutative expressions split up over multiple statements.
56 4. ANTIC_SAFE_LOADS could be a lot smarter than it is now.
57 Right now, it is simply calculating loads that occur before
58 any store in a block, instead of loads that occur before
59 stores that affect them. This is relatively more expensive, and
60 it's not clear how much more it will buy us.
63 /* For ease of terminology, "expression node" in the below refers to
64 every expression node but MODIFY_EXPR, because MODIFY_EXPR's represent
65 the actual statement containing the expressions we care about, and
66 we cache the value number by putting it in the expression. */
70 First we walk the statements to generate the AVAIL sets, the
71 EXP_GEN sets, and the tmp_gen sets. EXP_GEN sets represent the
72 generation of values/expressions by a given block. We use them
73 when computing the ANTIC sets. The AVAIL sets consist of
74 SSA_NAME's that represent values, so we know what values are
75 available in what blocks. AVAIL is a forward dataflow problem. In
76 SSA, values are never killed, so we don't need a kill set, or a
77 fixpoint iteration, in order to calculate the AVAIL sets. In
78 traditional parlance, AVAIL sets tell us the downsafety of the
81 Next, we generate the ANTIC sets. These sets represent the
82 anticipatable expressions. ANTIC is a backwards dataflow
83 problem.An expression is anticipatable in a given block if it could
84 be generated in that block. This means that if we had to perform
85 an insertion in that block, of the value of that expression, we
86 could. Calculating the ANTIC sets requires phi translation of
87 expressions, because the flow goes backwards through phis. We must
88 iterate to a fixpoint of the ANTIC sets, because we have a kill
89 set. Even in SSA form, values are not live over the entire
90 function, only from their definition point onwards. So we have to
91 remove values from the ANTIC set once we go past the definition
92 point of the leaders that make them up.
93 compute_antic/compute_antic_aux performs this computation.
95 Third, we perform insertions to make partially redundant
96 expressions fully redundant.
98 An expression is partially redundant (excluding partial
101 1. It is AVAIL in some, but not all, of the predecessors of a
103 2. It is ANTIC in all the predecessors.
105 In order to make it fully redundant, we insert the expression into
106 the predecessors where it is not available, but is ANTIC.
107 insert/insert_aux performs this insertion.
109 Fourth, we eliminate fully redundant expressions.
110 This is a simple statement walk that replaces redundant
111 calculations with the now available values. */
113 /* Representations of value numbers:
115 Value numbers are represented using the "value handle" approach.
116 This means that each SSA_NAME (and for other reasons to be
117 disclosed in a moment, expression nodes) has a value handle that
118 can be retrieved through get_value_handle. This value handle, *is*
119 the value number of the SSA_NAME. You can pointer compare the
120 value handles for equivalence purposes.
122 For debugging reasons, the value handle is internally more than
123 just a number, it is a VAR_DECL named "value.x", where x is a
124 unique number for each value number in use. This allows
125 expressions with SSA_NAMES replaced by value handles to still be
126 pretty printed in a sane way. They simply print as "value.3 *
129 Expression nodes have value handles associated with them as a
130 cache. Otherwise, we'd have to look them up again in the hash
131 table This makes significant difference (factor of two or more) on
132 some test cases. They can be thrown away after the pass is
135 /* Representation of expressions on value numbers:
137 In some portions of this code, you will notice we allocate "fake"
138 analogues to the expression we are value numbering, and replace the
139 operands with the values of the expression. Since we work on
140 values, and not just names, we canonicalize expressions to value
141 expressions for use in the ANTIC sets, the EXP_GEN set, etc.
143 This is theoretically unnecessary, it just saves a bunch of
144 repeated get_value_handle and find_leader calls in the remainder of
145 the code, trading off temporary memory usage for speed. The tree
146 nodes aren't actually creating more garbage, since they are
147 allocated in a special pools which are thrown away at the end of
150 All of this also means that if you print the EXP_GEN or ANTIC sets,
151 you will see "value.5 + value.7" in the set, instead of "a_55 +
152 b_66" or something. The only thing that actually cares about
153 seeing the value leaders is phi translation, and it needs to be
154 able to find the leader for a value in an arbitrary block, so this
155 "value expression" form is perfect for it (otherwise you'd do
156 get_value_handle->find_leader->translate->get_value_handle->find_leader).*/
159 /* Representation of sets:
161 There are currently two types of sets used, hopefully to be unified soon.
162 The AVAIL sets do not need to be sorted in any particular order,
163 and thus, are simply represented as two bitmaps, one that keeps
164 track of values present in the set, and one that keeps track of
165 expressions present in the set.
167 The other sets are represented as doubly linked lists kept in topological
168 order, with an optional supporting bitmap of values present in the
169 set. The sets represent values, and the elements can be values or
170 expressions. The elements can appear in different sets, but each
171 element can only appear once in each set.
173 Since each node in the set represents a value, we also want to be
174 able to map expression, set pairs to something that tells us
175 whether the value is present is a set. We use a per-set bitmap for
176 that. The value handles also point to a linked list of the
177 expressions they represent via a tree annotation. This is mainly
178 useful only for debugging, since we don't do identity lookups. */
181 static bool in_fre
= false;
183 /* A value set element. Basically a single linked list of
184 expressions/values. */
185 typedef struct value_set_node
190 /* A pointer to the next element of the value set. */
191 struct value_set_node
*next
;
195 /* A value set. This is a singly linked list of value_set_node
196 elements with a possible bitmap that tells us what values exist in
197 the set. This set must be kept in topologically sorted order. */
198 typedef struct value_set
200 /* The head of the list. Used for iterating over the list in
202 value_set_node_t head
;
204 /* The tail of the list. Used for tail insertions, which are
205 necessary to keep the set in topologically sorted order because
206 of how the set is built. */
207 value_set_node_t tail
;
209 /* The length of the list. */
212 /* True if the set is indexed, which means it contains a backing
213 bitmap for quick determination of whether certain values exist in the
217 /* The bitmap of values that exist in the set. May be NULL in an
218 empty or non-indexed set. */
224 /* An unordered bitmap set. One bitmap tracks values, the other,
226 typedef struct bitmap_set
232 /* Sets that we need to keep track of. */
233 typedef struct bb_value_sets
235 /* The EXP_GEN set, which represents expressions/values generated in
239 /* The PHI_GEN set, which represents PHI results generated in a
241 bitmap_set_t phi_gen
;
243 /* The TMP_GEN set, which represents results/temporaries generated
244 in a basic block. IE the LHS of an expression. */
245 bitmap_set_t tmp_gen
;
247 /* The AVAIL_OUT set, which represents which values are available in
248 a given basic block. */
249 bitmap_set_t avail_out
;
251 /* The ANTIC_IN set, which represents which values are anticipatable
252 in a given basic block. */
253 value_set_t antic_in
;
255 /* The NEW_SETS set, which is used during insertion to augment the
256 AVAIL_OUT set of blocks with the new insertions performed during
257 the current iteration. */
258 bitmap_set_t new_sets
;
260 /* The RVUSE sets, which are used during ANTIC computation to ensure
261 that we don't mark loads ANTIC once they have died. */
267 /* For actually occuring loads, as long as they occur before all the
268 other stores in the block, we know they are antic at the top of
269 the block, regardless of RVUSE_KILL. */
270 value_set_t antic_safe_loads
;
273 #define EXP_GEN(BB) ((bb_value_sets_t) ((BB)->aux))->exp_gen
274 #define PHI_GEN(BB) ((bb_value_sets_t) ((BB)->aux))->phi_gen
275 #define TMP_GEN(BB) ((bb_value_sets_t) ((BB)->aux))->tmp_gen
276 #define AVAIL_OUT(BB) ((bb_value_sets_t) ((BB)->aux))->avail_out
277 #define ANTIC_IN(BB) ((bb_value_sets_t) ((BB)->aux))->antic_in
278 #define RVUSE_IN(BB) ((bb_value_sets_t) ((BB)->aux))->rvuse_in
279 #define RVUSE_GEN(BB) ((bb_value_sets_t) ((BB)->aux))->rvuse_gen
280 #define RVUSE_KILL(BB) ((bb_value_sets_t) ((BB)->aux))->rvuse_kill
281 #define RVUSE_OUT(BB) ((bb_value_sets_t) ((BB)->aux))->rvuse_out
282 #define NEW_SETS(BB) ((bb_value_sets_t) ((BB)->aux))->new_sets
283 #define ANTIC_SAFE_LOADS(BB) ((bb_value_sets_t) ((BB)->aux))->antic_safe_loads
285 /* This structure is used to keep track of statistics on what
286 optimization PRE was able to perform. */
289 /* The number of RHS computations eliminated by PRE. */
292 /* The number of new expressions/temporaries generated by PRE. */
295 /* The number of new PHI nodes added by PRE. */
298 /* The number of values found constant. */
304 static tree
bitmap_find_leader (bitmap_set_t
, tree
);
305 static tree
find_leader (value_set_t
, tree
);
306 static void value_insert_into_set (value_set_t
, tree
);
307 static void bitmap_value_insert_into_set (bitmap_set_t
, tree
);
308 static void bitmap_value_replace_in_set (bitmap_set_t
, tree
);
309 static void insert_into_set (value_set_t
, tree
);
310 static void bitmap_set_copy (bitmap_set_t
, bitmap_set_t
);
311 static bool bitmap_set_contains_value (bitmap_set_t
, tree
);
312 static bitmap_set_t
bitmap_set_new (void);
313 static value_set_t
set_new (bool);
314 static bool is_undefined_value (tree
);
315 static tree
create_expression_by_pieces (basic_block
, tree
, tree
);
316 static tree
find_or_generate_expression (basic_block
, tree
, tree
);
319 /* We can add and remove elements and entries to and from sets
320 and hash tables, so we use alloc pools for them. */
322 static alloc_pool value_set_pool
;
323 static alloc_pool bitmap_set_pool
;
324 static alloc_pool value_set_node_pool
;
325 static alloc_pool binary_node_pool
;
326 static alloc_pool unary_node_pool
;
327 static alloc_pool reference_node_pool
;
328 static alloc_pool comparison_node_pool
;
329 static alloc_pool expression_node_pool
;
330 static alloc_pool list_node_pool
;
331 static alloc_pool modify_expr_node_pool
;
332 static bitmap_obstack grand_bitmap_obstack
;
334 /* To avoid adding 300 temporary variables when we only need one, we
335 only create one temporary variable, on demand, and build ssa names
336 off that. We do have to change the variable if the types don't
337 match the current variable's type. */
339 static tree storetemp
;
340 static tree mergephitemp
;
341 static tree prephitemp
;
343 /* Set of blocks with statements that have had its EH information
345 static bitmap need_eh_cleanup
;
347 /* The phi_translate_table caches phi translations for a given
348 expression and predecessor. */
350 static htab_t phi_translate_table
;
352 /* A three tuple {e, pred, v} used to cache phi translations in the
353 phi_translate_table. */
355 typedef struct expr_pred_trans_d
357 /* The expression. */
360 /* The predecessor block along which we translated the expression. */
363 /* vuses associated with the expression. */
364 VEC (tree
, gc
) *vuses
;
366 /* The value that resulted from the translation. */
370 /* The hashcode for the expression, pred pair. This is cached for
373 } *expr_pred_trans_t
;
375 /* Return the hash value for a phi translation table entry. */
378 expr_pred_trans_hash (const void *p
)
380 const expr_pred_trans_t ve
= (expr_pred_trans_t
) p
;
384 /* Return true if two phi translation table entries are the same.
385 P1 and P2 should point to the expr_pred_trans_t's to be compared.*/
388 expr_pred_trans_eq (const void *p1
, const void *p2
)
390 const expr_pred_trans_t ve1
= (expr_pred_trans_t
) p1
;
391 const expr_pred_trans_t ve2
= (expr_pred_trans_t
) p2
;
392 basic_block b1
= ve1
->pred
;
393 basic_block b2
= ve2
->pred
;
397 /* If they are not translations for the same basic block, they can't
403 /* If they are for the same basic block, determine if the
404 expressions are equal. */
405 if (!expressions_equal_p (ve1
->e
, ve2
->e
))
408 /* Make sure the vuses are equivalent. */
409 if (ve1
->vuses
== ve2
->vuses
)
412 if (VEC_length (tree
, ve1
->vuses
) != VEC_length (tree
, ve2
->vuses
))
415 for (i
= 0; VEC_iterate (tree
, ve1
->vuses
, i
, vuse1
); i
++)
417 if (VEC_index (tree
, ve2
->vuses
, i
) != vuse1
)
424 /* Search in the phi translation table for the translation of
425 expression E in basic block PRED with vuses VUSES.
426 Return the translated value, if found, NULL otherwise. */
429 phi_trans_lookup (tree e
, basic_block pred
, VEC (tree
, gc
) *vuses
)
432 struct expr_pred_trans_d ept
;
437 ept
.hashcode
= vn_compute (e
, (unsigned long) pred
);
438 slot
= htab_find_slot_with_hash (phi_translate_table
, &ept
, ept
.hashcode
,
443 return ((expr_pred_trans_t
) *slot
)->v
;
447 /* Add the tuple mapping from {expression E, basic block PRED, vuses VUSES} to
448 value V, to the phi translation table. */
451 phi_trans_add (tree e
, tree v
, basic_block pred
, VEC (tree
, gc
) *vuses
)
454 expr_pred_trans_t new_pair
= XNEW (struct expr_pred_trans_d
);
456 new_pair
->pred
= pred
;
457 new_pair
->vuses
= vuses
;
459 new_pair
->hashcode
= vn_compute (e
, (unsigned long) pred
);
460 slot
= htab_find_slot_with_hash (phi_translate_table
, new_pair
,
461 new_pair
->hashcode
, INSERT
);
464 *slot
= (void *) new_pair
;
468 /* Add expression E to the expression set of value V. */
471 add_to_value (tree v
, tree e
)
473 /* Constants have no expression sets. */
474 if (is_gimple_min_invariant (v
))
477 if (VALUE_HANDLE_EXPR_SET (v
) == NULL
)
478 VALUE_HANDLE_EXPR_SET (v
) = set_new (false);
480 insert_into_set (VALUE_HANDLE_EXPR_SET (v
), e
);
484 /* Return true if value V exists in the bitmap for SET. */
487 value_exists_in_set_bitmap (value_set_t set
, tree v
)
492 return bitmap_bit_p (set
->values
, VALUE_HANDLE_ID (v
));
496 /* Remove value V from the bitmap for SET. */
499 value_remove_from_set_bitmap (value_set_t set
, tree v
)
501 gcc_assert (set
->indexed
);
506 bitmap_clear_bit (set
->values
, VALUE_HANDLE_ID (v
));
510 /* Insert the value number V into the bitmap of values existing in
514 value_insert_into_set_bitmap (value_set_t set
, tree v
)
516 gcc_assert (set
->indexed
);
518 if (set
->values
== NULL
)
519 set
->values
= BITMAP_ALLOC (&grand_bitmap_obstack
);
521 bitmap_set_bit (set
->values
, VALUE_HANDLE_ID (v
));
525 /* Create a new bitmap set and return it. */
528 bitmap_set_new (void)
530 bitmap_set_t ret
= (bitmap_set_t
) pool_alloc (bitmap_set_pool
);
531 ret
->expressions
= BITMAP_ALLOC (&grand_bitmap_obstack
);
532 ret
->values
= BITMAP_ALLOC (&grand_bitmap_obstack
);
536 /* Create a new set. */
539 set_new (bool indexed
)
542 ret
= (value_set_t
) pool_alloc (value_set_pool
);
543 ret
->head
= ret
->tail
= NULL
;
545 ret
->indexed
= indexed
;
550 /* Insert an expression EXPR into a bitmapped set. */
553 bitmap_insert_into_set (bitmap_set_t set
, tree expr
)
556 /* XXX: For now, we only let SSA_NAMES into the bitmap sets. */
557 gcc_assert (TREE_CODE (expr
) == SSA_NAME
);
558 val
= get_value_handle (expr
);
561 if (!is_gimple_min_invariant (val
))
563 bitmap_set_bit (set
->values
, VALUE_HANDLE_ID (val
));
564 bitmap_set_bit (set
->expressions
, SSA_NAME_VERSION (expr
));
568 /* Insert EXPR into SET. */
571 insert_into_set (value_set_t set
, tree expr
)
573 value_set_node_t newnode
= (value_set_node_t
) pool_alloc (value_set_node_pool
);
574 tree val
= get_value_handle (expr
);
577 if (is_gimple_min_invariant (val
))
580 /* For indexed sets, insert the value into the set value bitmap.
581 For all sets, add it to the linked list and increment the list
584 value_insert_into_set_bitmap (set
, val
);
586 newnode
->next
= NULL
;
587 newnode
->expr
= expr
;
589 if (set
->head
== NULL
)
591 set
->head
= set
->tail
= newnode
;
595 set
->tail
->next
= newnode
;
600 /* Copy a bitmapped set ORIG, into bitmapped set DEST. */
603 bitmap_set_copy (bitmap_set_t dest
, bitmap_set_t orig
)
605 bitmap_copy (dest
->expressions
, orig
->expressions
);
606 bitmap_copy (dest
->values
, orig
->values
);
609 /* Perform bitmapped set operation DEST &= ORIG. */
612 bitmap_set_and (bitmap_set_t dest
, bitmap_set_t orig
)
616 bitmap temp
= BITMAP_ALLOC (&grand_bitmap_obstack
);
618 bitmap_and_into (dest
->values
, orig
->values
);
619 bitmap_copy (temp
, dest
->expressions
);
620 EXECUTE_IF_SET_IN_BITMAP (temp
, 0, i
, bi
)
622 tree name
= ssa_name (i
);
623 tree val
= get_value_handle (name
);
624 if (!bitmap_bit_p (dest
->values
, VALUE_HANDLE_ID (val
)))
625 bitmap_clear_bit (dest
->expressions
, i
);
630 /* Perform bitmapped value set operation DEST = DEST & ~ORIG. */
633 bitmap_set_and_compl (bitmap_set_t dest
, bitmap_set_t orig
)
637 bitmap temp
= BITMAP_ALLOC (&grand_bitmap_obstack
);
639 bitmap_and_compl_into (dest
->values
, orig
->values
);
640 bitmap_copy (temp
, dest
->expressions
);
641 EXECUTE_IF_SET_IN_BITMAP (temp
, 0, i
, bi
)
643 tree name
= ssa_name (i
);
644 tree val
= get_value_handle (name
);
645 if (!bitmap_bit_p (dest
->values
, VALUE_HANDLE_ID (val
)))
646 bitmap_clear_bit (dest
->expressions
, i
);
650 /* Return true if the bitmap set SET is empty. */
653 bitmap_set_empty_p (bitmap_set_t set
)
655 return bitmap_empty_p (set
->values
);
658 /* Copy the set ORIG to the set DEST. */
661 set_copy (value_set_t dest
, value_set_t orig
)
663 value_set_node_t node
;
665 if (!orig
|| !orig
->head
)
668 for (node
= orig
->head
;
672 insert_into_set (dest
, node
->expr
);
676 /* Remove EXPR from SET. */
679 set_remove (value_set_t set
, tree expr
)
681 value_set_node_t node
, prev
;
683 /* Remove the value of EXPR from the bitmap, decrement the set
684 length, and remove it from the actual double linked list. */
685 value_remove_from_set_bitmap (set
, get_value_handle (expr
));
688 for (node
= set
->head
;
690 prev
= node
, node
= node
->next
)
692 if (node
->expr
== expr
)
695 set
->head
= node
->next
;
697 prev
->next
= node
->next
;
699 if (node
== set
->tail
)
701 pool_free (value_set_node_pool
, node
);
707 /* Return true if SET contains the value VAL. */
710 set_contains_value (value_set_t set
, tree val
)
712 /* All constants are in every set. */
713 if (is_gimple_min_invariant (val
))
716 if (!set
|| set
->length
== 0)
719 return value_exists_in_set_bitmap (set
, val
);
722 /* Return true if bitmapped set SET contains the expression EXPR. */
724 bitmap_set_contains (bitmap_set_t set
, tree expr
)
726 /* All constants are in every set. */
727 if (is_gimple_min_invariant (get_value_handle (expr
)))
730 /* XXX: Bitmapped sets only contain SSA_NAME's for now. */
731 if (TREE_CODE (expr
) != SSA_NAME
)
733 return bitmap_bit_p (set
->expressions
, SSA_NAME_VERSION (expr
));
737 /* Return true if bitmapped set SET contains the value VAL. */
740 bitmap_set_contains_value (bitmap_set_t set
, tree val
)
742 if (is_gimple_min_invariant (val
))
744 return bitmap_bit_p (set
->values
, VALUE_HANDLE_ID (val
));
747 /* Replace an instance of value LOOKFOR with expression EXPR in SET. */
750 bitmap_set_replace_value (bitmap_set_t set
, tree lookfor
, tree expr
)
753 value_set_node_t node
;
754 if (is_gimple_min_invariant (lookfor
))
756 if (!bitmap_set_contains_value (set
, lookfor
))
759 /* The number of expressions having a given value is usually
760 significantly less than the total number of expressions in SET.
761 Thus, rather than check, for each expression in SET, whether it
762 has the value LOOKFOR, we walk the reverse mapping that tells us
763 what expressions have a given value, and see if any of those
764 expressions are in our set. For large testcases, this is about
765 5-10x faster than walking the bitmap. If this is somehow a
766 significant lose for some cases, we can choose which set to walk
767 based on the set size. */
768 exprset
= VALUE_HANDLE_EXPR_SET (lookfor
);
769 for (node
= exprset
->head
; node
; node
= node
->next
)
771 if (TREE_CODE (node
->expr
) == SSA_NAME
)
773 if (bitmap_bit_p (set
->expressions
, SSA_NAME_VERSION (node
->expr
)))
775 bitmap_clear_bit (set
->expressions
, SSA_NAME_VERSION (node
->expr
));
776 bitmap_set_bit (set
->expressions
, SSA_NAME_VERSION (expr
));
783 /* Subtract bitmapped set B from value set A, and return the new set. */
786 bitmap_set_subtract_from_value_set (value_set_t a
, bitmap_set_t b
,
789 value_set_t ret
= set_new (indexed
);
790 value_set_node_t node
;
795 if (!bitmap_set_contains (b
, node
->expr
))
796 insert_into_set (ret
, node
->expr
);
801 /* Return true if two sets are equal. */
804 set_equal (value_set_t a
, value_set_t b
)
806 value_set_node_t node
;
808 if (a
->length
!= b
->length
)
814 if (!set_contains_value (b
, get_value_handle (node
->expr
)))
820 /* Replace an instance of EXPR's VALUE with EXPR in SET if it exists,
821 and add it otherwise. */
824 bitmap_value_replace_in_set (bitmap_set_t set
, tree expr
)
826 tree val
= get_value_handle (expr
);
827 if (bitmap_set_contains_value (set
, val
))
828 bitmap_set_replace_value (set
, val
, expr
);
830 bitmap_insert_into_set (set
, expr
);
833 /* Insert EXPR into SET if EXPR's value is not already present in
837 bitmap_value_insert_into_set (bitmap_set_t set
, tree expr
)
839 tree val
= get_value_handle (expr
);
841 if (is_gimple_min_invariant (val
))
844 if (!bitmap_set_contains_value (set
, val
))
845 bitmap_insert_into_set (set
, expr
);
848 /* Insert the value for EXPR into SET, if it doesn't exist already. */
851 value_insert_into_set (value_set_t set
, tree expr
)
853 tree val
= get_value_handle (expr
);
855 /* Constant and invariant values exist everywhere, and thus,
856 actually keeping them in the sets is pointless. */
857 if (is_gimple_min_invariant (val
))
860 if (!set_contains_value (set
, val
))
861 insert_into_set (set
, expr
);
865 /* Print out SET to OUTFILE. */
868 bitmap_print_value_set (FILE *outfile
, bitmap_set_t set
,
869 const char *setname
, int blockindex
)
871 fprintf (outfile
, "%s[%d] := { ", setname
, blockindex
);
878 EXECUTE_IF_SET_IN_BITMAP (set
->expressions
, 0, i
, bi
)
881 fprintf (outfile
, ", ");
883 print_generic_expr (outfile
, ssa_name (i
), 0);
885 fprintf (outfile
, " (");
886 print_generic_expr (outfile
, get_value_handle (ssa_name (i
)), 0);
887 fprintf (outfile
, ") ");
890 fprintf (outfile
, " }\n");
892 /* Print out the value_set SET to OUTFILE. */
895 print_value_set (FILE *outfile
, value_set_t set
,
896 const char *setname
, int blockindex
)
898 value_set_node_t node
;
899 fprintf (outfile
, "%s[%d] := { ", setname
, blockindex
);
902 for (node
= set
->head
;
906 print_generic_expr (outfile
, node
->expr
, 0);
908 fprintf (outfile
, " (");
909 print_generic_expr (outfile
, get_value_handle (node
->expr
), 0);
910 fprintf (outfile
, ") ");
913 fprintf (outfile
, ", ");
917 fprintf (outfile
, " }\n");
920 /* Print out the expressions that have VAL to OUTFILE. */
923 print_value_expressions (FILE *outfile
, tree val
)
925 if (VALUE_HANDLE_EXPR_SET (val
))
928 sprintf (s
, "VH.%04d", VALUE_HANDLE_ID (val
));
929 print_value_set (outfile
, VALUE_HANDLE_EXPR_SET (val
), s
, 0);
935 debug_value_expressions (tree val
)
937 print_value_expressions (stderr
, val
);
941 void debug_value_set (value_set_t
, const char *, int);
944 debug_value_set (value_set_t set
, const char *setname
, int blockindex
)
946 print_value_set (stderr
, set
, setname
, blockindex
);
949 /* Return the folded version of T if T, when folded, is a gimple
950 min_invariant. Otherwise, return T. */
953 fully_constant_expression (tree t
)
957 if (folded
&& is_gimple_min_invariant (folded
))
962 /* Return a copy of a chain of nodes, chained through the TREE_CHAIN field.
963 For example, this can copy a list made of TREE_LIST nodes.
964 Allocates the nodes in list_node_pool*/
967 pool_copy_list (tree list
)
974 head
= (tree
) pool_alloc (list_node_pool
);
976 memcpy (head
, list
, tree_size (list
));
979 next
= TREE_CHAIN (list
);
982 TREE_CHAIN (prev
) = (tree
) pool_alloc (list_node_pool
);
983 memcpy (TREE_CHAIN (prev
), next
, tree_size (next
));
984 prev
= TREE_CHAIN (prev
);
985 next
= TREE_CHAIN (next
);
990 /* Translate the vuses in the VUSES vector backwards through phi
991 nodes, so that they have the value they would have in BLOCK. */
993 static VEC(tree
, gc
) *
994 translate_vuses_through_block (VEC (tree
, gc
) *vuses
, basic_block block
)
997 VEC(tree
, gc
) *result
= NULL
;
1000 for (i
= 0; VEC_iterate (tree
, vuses
, i
, oldvuse
); i
++)
1002 tree phi
= SSA_NAME_DEF_STMT (oldvuse
);
1003 if (TREE_CODE (phi
) == PHI_NODE
)
1005 edge e
= find_edge (block
, bb_for_stmt (phi
));
1008 tree def
= PHI_ARG_DEF (phi
, e
->dest_idx
);
1012 result
= VEC_copy (tree
, gc
, vuses
);
1013 VEC_replace (tree
, result
, i
, def
);
1020 sort_vuses (result
);
1026 /* Translate EXPR using phis in PHIBLOCK, so that it has the values of
1027 the phis in PRED. Return NULL if we can't find a leader for each
1028 part of the translated expression. */
1031 phi_translate (tree expr
, value_set_t set
, basic_block pred
,
1032 basic_block phiblock
)
1034 tree phitrans
= NULL
;
1035 tree oldexpr
= expr
;
1039 if (is_gimple_min_invariant (expr
))
1042 /* Phi translations of a given expression don't change. */
1047 vh
= get_value_handle (expr
);
1048 if (vh
&& TREE_CODE (vh
) == VALUE_HANDLE
)
1049 phitrans
= phi_trans_lookup (expr
, pred
, VALUE_HANDLE_VUSES (vh
));
1051 phitrans
= phi_trans_lookup (expr
, pred
, NULL
);
1054 phitrans
= phi_trans_lookup (expr
, pred
, NULL
);
1059 switch (TREE_CODE_CLASS (TREE_CODE (expr
)))
1061 case tcc_expression
:
1063 if (TREE_CODE (expr
) != CALL_EXPR
)
1067 tree oldop0
= TREE_OPERAND (expr
, 0);
1068 tree oldarglist
= TREE_OPERAND (expr
, 1);
1069 tree oldop2
= TREE_OPERAND (expr
, 2);
1076 tree vh
= get_value_handle (expr
);
1077 bool listchanged
= false;
1078 VEC (tree
, gc
) *vuses
= VALUE_HANDLE_VUSES (vh
);
1079 VEC (tree
, gc
) *tvuses
;
1081 /* Call expressions are kind of weird because they have an
1082 argument list. We don't want to value number the list
1083 as one value number, because that doesn't make much
1084 sense, and just breaks the support functions we call,
1085 which expect TREE_OPERAND (call_expr, 2) to be a
1088 newop0
= phi_translate (find_leader (set
, oldop0
),
1089 set
, pred
, phiblock
);
1094 newop2
= phi_translate (find_leader (set
, oldop2
),
1095 set
, pred
, phiblock
);
1100 /* phi translate the argument list piece by piece.
1102 We could actually build the list piece by piece here,
1103 but it's likely to not be worth the memory we will save,
1104 unless you have millions of call arguments. */
1106 newarglist
= pool_copy_list (oldarglist
);
1107 for (oldwalker
= oldarglist
, newwalker
= newarglist
;
1108 oldwalker
&& newwalker
;
1109 oldwalker
= TREE_CHAIN (oldwalker
),
1110 newwalker
= TREE_CHAIN (newwalker
))
1113 tree oldval
= TREE_VALUE (oldwalker
);
1117 /* This may seem like a weird place for this
1118 check, but it's actually the easiest place to
1119 do it. We can't do it lower on in the
1120 recursion because it's valid for pieces of a
1121 component ref to be of AGGREGATE_TYPE, as long
1122 as the outermost one is not.
1123 To avoid *that* case, we have a check for
1124 AGGREGATE_TYPE_P in insert_aux. However, that
1125 check will *not* catch this case because here
1126 it occurs in the argument list. */
1127 if (AGGREGATE_TYPE_P (TREE_TYPE (oldval
)))
1129 newval
= phi_translate (find_leader (set
, oldval
),
1130 set
, pred
, phiblock
);
1133 if (newval
!= oldval
)
1136 TREE_VALUE (newwalker
) = get_value_handle (newval
);
1141 vn_lookup_or_add (newarglist
, NULL
);
1143 tvuses
= translate_vuses_through_block (vuses
, pred
);
1145 if (listchanged
|| (newop0
!= oldop0
) || (oldop2
!= newop2
)
1148 newexpr
= (tree
) pool_alloc (expression_node_pool
);
1149 memcpy (newexpr
, expr
, tree_size (expr
));
1150 TREE_OPERAND (newexpr
, 0) = newop0
== oldop0
? oldop0
: get_value_handle (newop0
);
1151 TREE_OPERAND (newexpr
, 1) = listchanged
? newarglist
: oldarglist
;
1152 TREE_OPERAND (newexpr
, 2) = newop2
== oldop2
? oldop2
: get_value_handle (newop2
);
1153 create_tree_ann (newexpr
);
1154 vn_lookup_or_add_with_vuses (newexpr
, tvuses
);
1156 phi_trans_add (oldexpr
, newexpr
, pred
, tvuses
);
1162 case tcc_declaration
:
1164 VEC (tree
, gc
) * oldvuses
= NULL
;
1165 VEC (tree
, gc
) * newvuses
= NULL
;
1167 oldvuses
= VALUE_HANDLE_VUSES (get_value_handle (expr
));
1169 newvuses
= translate_vuses_through_block (oldvuses
, pred
);
1171 if (oldvuses
!= newvuses
)
1172 vn_lookup_or_add_with_vuses (expr
, newvuses
);
1174 phi_trans_add (oldexpr
, expr
, pred
, newvuses
);
1180 tree oldop0
= TREE_OPERAND (expr
, 0);
1189 VEC (tree
, gc
) * oldvuses
= NULL
;
1190 VEC (tree
, gc
) * newvuses
= NULL
;
1192 if (TREE_CODE (expr
) != INDIRECT_REF
1193 && TREE_CODE (expr
) != COMPONENT_REF
1194 && TREE_CODE (expr
) != ARRAY_REF
)
1197 newop0
= phi_translate (find_leader (set
, oldop0
),
1198 set
, pred
, phiblock
);
1202 if (TREE_CODE (expr
) == ARRAY_REF
)
1204 oldop1
= TREE_OPERAND (expr
, 1);
1205 newop1
= phi_translate (find_leader (set
, oldop1
),
1206 set
, pred
, phiblock
);
1210 oldop2
= TREE_OPERAND (expr
, 2);
1213 newop2
= phi_translate (find_leader (set
, oldop2
),
1214 set
, pred
, phiblock
);
1219 oldop3
= TREE_OPERAND (expr
, 3);
1222 newop3
= phi_translate (find_leader (set
, oldop3
),
1223 set
, pred
, phiblock
);
1230 oldvuses
= VALUE_HANDLE_VUSES (get_value_handle (expr
));
1232 newvuses
= translate_vuses_through_block (oldvuses
, pred
);
1234 if (newop0
!= oldop0
|| newvuses
!= oldvuses
1237 || newop3
!= oldop3
)
1241 newexpr
= pool_alloc (reference_node_pool
);
1242 memcpy (newexpr
, expr
, tree_size (expr
));
1243 TREE_OPERAND (newexpr
, 0) = get_value_handle (newop0
);
1244 if (TREE_CODE (expr
) == ARRAY_REF
)
1246 TREE_OPERAND (newexpr
, 1) = get_value_handle (newop1
);
1248 TREE_OPERAND (newexpr
, 2) = get_value_handle (newop2
);
1250 TREE_OPERAND (newexpr
, 3) = get_value_handle (newop3
);
1253 t
= fully_constant_expression (newexpr
);
1257 pool_free (reference_node_pool
, newexpr
);
1262 create_tree_ann (newexpr
);
1263 vn_lookup_or_add_with_vuses (newexpr
, newvuses
);
1266 phi_trans_add (oldexpr
, newexpr
, pred
, newvuses
);
1273 case tcc_comparison
:
1275 tree oldop1
= TREE_OPERAND (expr
, 0);
1276 tree oldop2
= TREE_OPERAND (expr
, 1);
1281 newop1
= phi_translate (find_leader (set
, oldop1
),
1282 set
, pred
, phiblock
);
1285 newop2
= phi_translate (find_leader (set
, oldop2
),
1286 set
, pred
, phiblock
);
1289 if (newop1
!= oldop1
|| newop2
!= oldop2
)
1292 newexpr
= (tree
) pool_alloc (binary_node_pool
);
1293 memcpy (newexpr
, expr
, tree_size (expr
));
1294 TREE_OPERAND (newexpr
, 0) = newop1
== oldop1
? oldop1
: get_value_handle (newop1
);
1295 TREE_OPERAND (newexpr
, 1) = newop2
== oldop2
? oldop2
: get_value_handle (newop2
);
1296 t
= fully_constant_expression (newexpr
);
1299 pool_free (binary_node_pool
, newexpr
);
1304 create_tree_ann (newexpr
);
1305 vn_lookup_or_add (newexpr
, NULL
);
1308 phi_trans_add (oldexpr
, newexpr
, pred
, NULL
);
1315 tree oldop1
= TREE_OPERAND (expr
, 0);
1319 newop1
= phi_translate (find_leader (set
, oldop1
),
1320 set
, pred
, phiblock
);
1323 if (newop1
!= oldop1
)
1326 newexpr
= (tree
) pool_alloc (unary_node_pool
);
1327 memcpy (newexpr
, expr
, tree_size (expr
));
1328 TREE_OPERAND (newexpr
, 0) = get_value_handle (newop1
);
1329 t
= fully_constant_expression (newexpr
);
1332 pool_free (unary_node_pool
, newexpr
);
1337 create_tree_ann (newexpr
);
1338 vn_lookup_or_add (newexpr
, NULL
);
1341 phi_trans_add (oldexpr
, newexpr
, pred
, NULL
);
1346 case tcc_exceptional
:
1350 gcc_assert (TREE_CODE (expr
) == SSA_NAME
);
1351 if (TREE_CODE (SSA_NAME_DEF_STMT (expr
)) == PHI_NODE
)
1352 phi
= SSA_NAME_DEF_STMT (expr
);
1356 e
= find_edge (pred
, bb_for_stmt (phi
));
1359 if (is_undefined_value (PHI_ARG_DEF (phi
, e
->dest_idx
)))
1361 vn_lookup_or_add (PHI_ARG_DEF (phi
, e
->dest_idx
), NULL
);
1362 return PHI_ARG_DEF (phi
, e
->dest_idx
);
1372 /* For each expression in SET, translate the value handles through phi nodes
1373 in PHIBLOCK using edge PHIBLOCK->PRED, and store the resulting
1374 expressions in DEST. */
1377 phi_translate_set (value_set_t dest
, value_set_t set
, basic_block pred
,
1378 basic_block phiblock
)
1380 value_set_node_t node
;
1381 for (node
= set
->head
;
1387 translated
= phi_translate (node
->expr
, set
, pred
, phiblock
);
1389 /* Don't add constants or empty translations to the cache, since
1390 we won't look them up that way, or use the result, anyway. */
1391 if (translated
&& !is_gimple_min_invariant (translated
))
1393 tree vh
= get_value_handle (translated
);
1394 VEC (tree
, gc
) *vuses
;
1396 /* The value handle itself may also be an invariant, in
1397 which case, it has no vuses. */
1398 vuses
= !is_gimple_min_invariant (vh
)
1399 ? VALUE_HANDLE_VUSES (vh
) : NULL
;
1400 phi_trans_add (node
->expr
, translated
, pred
, vuses
);
1403 if (translated
!= NULL
)
1404 value_insert_into_set (dest
, translated
);
1408 /* Find the leader for a value (i.e., the name representing that
1409 value) in a given set, and return it. Return NULL if no leader is
1413 bitmap_find_leader (bitmap_set_t set
, tree val
)
1418 if (is_gimple_min_invariant (val
))
1420 if (bitmap_set_contains_value (set
, val
))
1422 /* Rather than walk the entire bitmap of expressions, and see
1423 whether any of them has the value we are looking for, we look
1424 at the reverse mapping, which tells us the set of expressions
1425 that have a given value (IE value->expressions with that
1426 value) and see if any of those expressions are in our set.
1427 The number of expressions per value is usually significantly
1428 less than the number of expressions in the set. In fact, for
1429 large testcases, doing it this way is roughly 5-10x faster
1430 than walking the bitmap.
1431 If this is somehow a significant lose for some cases, we can
1432 choose which set to walk based on which set is smaller. */
1433 value_set_t exprset
;
1434 value_set_node_t node
;
1435 exprset
= VALUE_HANDLE_EXPR_SET (val
);
1436 for (node
= exprset
->head
; node
; node
= node
->next
)
1438 if (TREE_CODE (node
->expr
) == SSA_NAME
)
1440 if (bitmap_bit_p (set
->expressions
,
1441 SSA_NAME_VERSION (node
->expr
)))
1450 /* Find the leader for a value (i.e., the name representing that
1451 value) in a given set, and return it. Return NULL if no leader is
1455 find_leader (value_set_t set
, tree val
)
1457 value_set_node_t node
;
1462 /* Constants represent themselves. */
1463 if (is_gimple_min_invariant (val
))
1466 if (set
->length
== 0)
1469 if (value_exists_in_set_bitmap (set
, val
))
1471 for (node
= set
->head
;
1475 if (get_value_handle (node
->expr
) == val
)
1483 /* Given the vuse representative map, MAP, and an SSA version number,
1484 ID, return the bitmap of names ID represents, or NULL, if none
1488 get_representative (bitmap
*map
, int id
)
1490 if (map
[id
] != NULL
)
1495 /* A vuse is anticipable at the top of block x, from the bottom of the
1496 block, if it reaches the top of the block, and is not killed in the
1497 block. In effect, we are trying to see if the vuse is transparent
1498 backwards in the block. */
1501 vuses_dies_in_block_x (VEC (tree
, gc
) *vuses
, basic_block block
)
1506 for (i
= 0; VEC_iterate (tree
, vuses
, i
, vuse
); i
++)
1508 /* Any places where this is too conservative, are places
1509 where we created a new version and shouldn't have. */
1511 if (!bitmap_bit_p (RVUSE_IN (block
), SSA_NAME_VERSION (vuse
))
1512 || bitmap_bit_p (RVUSE_KILL (block
), SSA_NAME_VERSION (vuse
)))
1518 /* Determine if the expression EXPR is valid in SET. This means that
1519 we have a leader for each part of the expression (if it consists of
1520 values), or the expression is an SSA_NAME.
1522 NB: We never should run into a case where we have SSA_NAME +
1523 SSA_NAME or SSA_NAME + value. The sets valid_in_set is called on,
1524 the ANTIC sets, will only ever have SSA_NAME's or value expressions
1525 (IE VALUE1 + VALUE2, *VALUE1, VALUE1 < VALUE2) */
1528 valid_in_set (value_set_t set
, tree expr
, basic_block block
)
1530 tree vh
= get_value_handle (expr
);
1531 switch (TREE_CODE_CLASS (TREE_CODE (expr
)))
1534 case tcc_comparison
:
1536 tree op1
= TREE_OPERAND (expr
, 0);
1537 tree op2
= TREE_OPERAND (expr
, 1);
1538 return set_contains_value (set
, op1
) && set_contains_value (set
, op2
);
1543 tree op1
= TREE_OPERAND (expr
, 0);
1544 return set_contains_value (set
, op1
);
1547 case tcc_expression
:
1549 if (TREE_CODE (expr
) == CALL_EXPR
)
1551 tree op0
= TREE_OPERAND (expr
, 0);
1552 tree arglist
= TREE_OPERAND (expr
, 1);
1553 tree op2
= TREE_OPERAND (expr
, 2);
1555 /* Check the non-list operands first. */
1556 if (!set_contains_value (set
, op0
)
1557 || (op2
&& !set_contains_value (set
, op2
)))
1560 /* Now check the operands. */
1561 for (; arglist
; arglist
= TREE_CHAIN (arglist
))
1563 if (!set_contains_value (set
, TREE_VALUE (arglist
)))
1566 return !vuses_dies_in_block_x (VALUE_HANDLE_VUSES (vh
), block
);
1573 if (TREE_CODE (expr
) == INDIRECT_REF
1574 || TREE_CODE (expr
) == COMPONENT_REF
1575 || TREE_CODE (expr
) == ARRAY_REF
)
1577 tree op0
= TREE_OPERAND (expr
, 0);
1578 gcc_assert (is_gimple_min_invariant (op0
)
1579 || TREE_CODE (op0
) == VALUE_HANDLE
);
1580 if (!set_contains_value (set
, op0
))
1582 if (TREE_CODE (expr
) == ARRAY_REF
)
1584 tree op1
= TREE_OPERAND (expr
, 1);
1585 tree op2
= TREE_OPERAND (expr
, 2);
1586 tree op3
= TREE_OPERAND (expr
, 3);
1587 gcc_assert (is_gimple_min_invariant (op1
)
1588 || TREE_CODE (op1
) == VALUE_HANDLE
);
1589 if (!set_contains_value (set
, op1
))
1591 gcc_assert (!op2
|| is_gimple_min_invariant (op2
)
1592 || TREE_CODE (op2
) == VALUE_HANDLE
);
1594 && !set_contains_value (set
, op2
))
1596 gcc_assert (!op3
|| is_gimple_min_invariant (op3
)
1597 || TREE_CODE (op3
) == VALUE_HANDLE
);
1599 && !set_contains_value (set
, op3
))
1602 return set_contains_value (ANTIC_SAFE_LOADS (block
),
1604 || !vuses_dies_in_block_x (VALUE_HANDLE_VUSES (vh
),
1610 case tcc_exceptional
:
1611 gcc_assert (TREE_CODE (expr
) == SSA_NAME
);
1614 case tcc_declaration
:
1615 return !vuses_dies_in_block_x (VALUE_HANDLE_VUSES (vh
), block
);
1618 /* No other cases should be encountered. */
1623 /* Clean the set of expressions that are no longer valid in SET. This
1624 means expressions that are made up of values we have no leaders for
1628 clean (value_set_t set
, basic_block block
)
1630 value_set_node_t node
;
1631 value_set_node_t next
;
1636 if (!valid_in_set (set
, node
->expr
, block
))
1637 set_remove (set
, node
->expr
);
1642 static sbitmap has_abnormal_preds
;
1644 /* Compute the ANTIC set for BLOCK.
1646 If succs(BLOCK) > 1 then
1647 ANTIC_OUT[BLOCK] = intersection of ANTIC_IN[b] for all succ(BLOCK)
1648 else if succs(BLOCK) == 1 then
1649 ANTIC_OUT[BLOCK] = phi_translate (ANTIC_IN[succ(BLOCK)])
1651 ANTIC_IN[BLOCK] = clean(ANTIC_OUT[BLOCK] U EXP_GEN[BLOCK] - TMP_GEN[BLOCK])
1653 XXX: It would be nice to either write a set_clear, and use it for
1654 ANTIC_OUT, or to mark the antic_out set as deleted at the end
1655 of this routine, so that the pool can hand the same memory back out
1656 again for the next ANTIC_OUT. */
1659 compute_antic_aux (basic_block block
, bool block_has_abnormal_pred_edge
)
1662 bool changed
= false;
1663 value_set_t S
, old
, ANTIC_OUT
;
1664 value_set_node_t node
;
1666 ANTIC_OUT
= S
= NULL
;
1668 /* If any edges from predecessors are abnormal, antic_in is empty,
1670 if (block_has_abnormal_pred_edge
)
1671 goto maybe_dump_sets
;
1673 old
= set_new (false);
1674 set_copy (old
, ANTIC_IN (block
));
1675 ANTIC_OUT
= set_new (true);
1677 /* If the block has no successors, ANTIC_OUT is empty. */
1678 if (EDGE_COUNT (block
->succs
) == 0)
1680 /* If we have one successor, we could have some phi nodes to
1681 translate through. */
1682 else if (single_succ_p (block
))
1684 phi_translate_set (ANTIC_OUT
, ANTIC_IN (single_succ (block
)),
1685 block
, single_succ (block
));
1687 /* If we have multiple successors, we take the intersection of all of
1691 VEC(basic_block
, heap
) * worklist
;
1694 basic_block bprime
, first
;
1697 worklist
= VEC_alloc (basic_block
, heap
, EDGE_COUNT (block
->succs
));
1698 FOR_EACH_EDGE (e
, ei
, block
->succs
)
1699 VEC_quick_push (basic_block
, worklist
, e
->dest
);
1700 first
= VEC_index (basic_block
, worklist
, 0);
1701 set_copy (ANTIC_OUT
, ANTIC_IN (first
));
1703 for (i
= 1; VEC_iterate (basic_block
, worklist
, i
, bprime
); i
++)
1705 node
= ANTIC_OUT
->head
;
1709 value_set_node_t next
= node
->next
;
1711 val
= get_value_handle (node
->expr
);
1712 if (!set_contains_value (ANTIC_IN (bprime
), val
))
1713 set_remove (ANTIC_OUT
, node
->expr
);
1717 VEC_free (basic_block
, heap
, worklist
);
1720 /* Generate ANTIC_OUT - TMP_GEN. */
1721 S
= bitmap_set_subtract_from_value_set (ANTIC_OUT
, TMP_GEN (block
), false);
1723 /* Start ANTIC_IN with EXP_GEN - TMP_GEN */
1724 ANTIC_IN (block
) = bitmap_set_subtract_from_value_set (EXP_GEN (block
),
1728 /* Then union in the ANTIC_OUT - TMP_GEN values,
1729 to get ANTIC_OUT U EXP_GEN - TMP_GEN */
1730 for (node
= S
->head
; node
; node
= node
->next
)
1731 value_insert_into_set (ANTIC_IN (block
), node
->expr
);
1733 clean (ANTIC_IN (block
), block
);
1734 if (!set_equal (old
, ANTIC_IN (block
)))
1738 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1741 print_value_set (dump_file
, ANTIC_OUT
, "ANTIC_OUT", block
->index
);
1743 if (ANTIC_SAFE_LOADS (block
))
1744 print_value_set (dump_file
, ANTIC_SAFE_LOADS (block
),
1745 "ANTIC_SAFE_LOADS", block
->index
);
1746 print_value_set (dump_file
, ANTIC_IN (block
), "ANTIC_IN", block
->index
);
1749 print_value_set (dump_file
, S
, "S", block
->index
);
1752 for (son
= first_dom_son (CDI_POST_DOMINATORS
, block
);
1754 son
= next_dom_son (CDI_POST_DOMINATORS
, son
))
1756 changed
|= compute_antic_aux (son
,
1757 TEST_BIT (has_abnormal_preds
, son
->index
));
1762 /* Compute ANTIC sets. */
1765 compute_antic (void)
1767 bool changed
= true;
1768 int num_iterations
= 0;
1771 /* If any predecessor edges are abnormal, we punt, so antic_in is empty.
1772 We pre-build the map of blocks with incoming abnormal edges here. */
1773 has_abnormal_preds
= sbitmap_alloc (last_basic_block
);
1774 sbitmap_zero (has_abnormal_preds
);
1780 FOR_EACH_EDGE (e
, ei
, block
->preds
)
1781 if (e
->flags
& EDGE_ABNORMAL
)
1783 SET_BIT (has_abnormal_preds
, block
->index
);
1787 /* While we are here, give empty ANTIC_IN sets to each block. */
1788 ANTIC_IN (block
) = set_new (true);
1790 /* At the exit block we anticipate nothing. */
1791 ANTIC_IN (EXIT_BLOCK_PTR
) = set_new (true);
1797 changed
= compute_antic_aux (EXIT_BLOCK_PTR
, false);
1800 sbitmap_free (has_abnormal_preds
);
1802 if (dump_file
&& (dump_flags
& TDF_STATS
))
1803 fprintf (dump_file
, "compute_antic required %d iterations\n", num_iterations
);
1806 /* Print the names represented by the bitmap NAMES, to the file OUT. */
1808 dump_bitmap_of_names (FILE *out
, bitmap names
)
1813 fprintf (out
, " { ");
1814 EXECUTE_IF_SET_IN_BITMAP (names
, 0, i
, bi
)
1816 print_generic_expr (out
, ssa_name (i
), 0);
1819 fprintf (out
, "}\n");
1822 /* Compute a set of representative vuse versions for each phi. This
1823 is so we can compute conservative kill sets in terms of all vuses
1824 that are killed, instead of continually walking chains.
1826 We also have to be able kill all names associated with a phi when
1827 the phi dies in order to ensure we don't generate overlapping
1828 live ranges, which are not allowed in virtual SSA. */
1830 static bitmap
*vuse_names
;
1832 compute_vuse_representatives (void)
1836 VEC (tree
, heap
) *phis
= NULL
;
1837 bool changed
= true;
1842 for (phi
= phi_nodes (bb
);
1844 phi
= PHI_CHAIN (phi
))
1845 if (!is_gimple_reg (PHI_RESULT (phi
)))
1846 VEC_safe_push (tree
, heap
, phis
, phi
);
1853 for (i
= 0; VEC_iterate (tree
, phis
, i
, phi
); i
++)
1855 size_t ver
= SSA_NAME_VERSION (PHI_RESULT (phi
));
1859 if (vuse_names
[ver
] == NULL
)
1861 vuse_names
[ver
] = BITMAP_ALLOC (&grand_bitmap_obstack
);
1862 bitmap_set_bit (vuse_names
[ver
], ver
);
1864 FOR_EACH_PHI_ARG (usep
, phi
, iter
, SSA_OP_ALL_USES
)
1866 tree use
= USE_FROM_PTR (usep
);
1867 bitmap usebitmap
= get_representative (vuse_names
,
1868 SSA_NAME_VERSION (use
));
1869 if (usebitmap
!= NULL
)
1871 changed
|= bitmap_ior_into (vuse_names
[ver
],
1876 changed
|= !bitmap_bit_p (vuse_names
[ver
],
1877 SSA_NAME_VERSION (use
));
1879 bitmap_set_bit (vuse_names
[ver
],
1880 SSA_NAME_VERSION (use
));
1886 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1887 for (i
= 0; VEC_iterate (tree
, phis
, i
, phi
); i
++)
1889 bitmap reps
= get_representative (vuse_names
,
1890 SSA_NAME_VERSION (PHI_RESULT (phi
)));
1893 print_generic_expr (dump_file
, PHI_RESULT (phi
), 0);
1894 fprintf (dump_file
, " represents ");
1895 dump_bitmap_of_names (dump_file
, reps
);
1898 VEC_free (tree
, heap
, phis
);
1901 /* Compute reaching vuses and antic safe loads. RVUSE computation is
1902 is a small bit of iterative dataflow to determine what virtual uses
1903 reach what blocks. Because we can't generate overlapping virtual
1904 uses, and virtual uses *do* actually die, this ends up being faster
1905 in most cases than continually walking the virtual use/def chains
1906 to determine whether we are inside a block where a given virtual is
1907 still available to be used.
1909 ANTIC_SAFE_LOADS are those loads that actually occur before any kill to
1910 their vuses in the block,and thus, are safe at the top of the
1920 b = *a is an antic safe load because it still safe to consider it
1921 ANTIC at the top of the block.
1923 We currently compute a conservative approximation to
1924 ANTIC_SAFE_LOADS. We compute those loads that occur before *any*
1925 stores in the block. This is not because it is difficult to
1926 compute the precise answer, but because it is expensive. More
1927 testing is necessary to determine whether it is worth computing the
1931 compute_rvuse_and_antic_safe (void)
1938 bool changed
= true;
1939 unsigned int *first_store_uid
;
1941 first_store_uid
= xcalloc (n_basic_blocks
, sizeof (unsigned int));
1943 compute_vuse_representatives ();
1947 RVUSE_IN (bb
) = BITMAP_ALLOC (&grand_bitmap_obstack
);
1948 RVUSE_GEN (bb
) = BITMAP_ALLOC (&grand_bitmap_obstack
);
1949 RVUSE_KILL (bb
) = BITMAP_ALLOC (&grand_bitmap_obstack
);
1950 RVUSE_OUT (bb
) = BITMAP_ALLOC (&grand_bitmap_obstack
);
1951 ANTIC_SAFE_LOADS (bb
) = NULL
;
1954 /* Mark live on entry */
1955 for (i
= 0; i
< num_ssa_names
; i
++)
1957 tree name
= ssa_name (i
);
1958 if (name
&& !is_gimple_reg (name
)
1959 && IS_EMPTY_STMT (SSA_NAME_DEF_STMT (name
)))
1960 bitmap_set_bit (RVUSE_OUT (ENTRY_BLOCK_PTR
),
1961 SSA_NAME_VERSION (name
));
1964 /* Compute local sets for reaching vuses.
1965 GEN(block) = generated in block and not locally killed.
1966 KILL(block) = set of vuses killed in block.
1971 block_stmt_iterator bsi
;
1976 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
1978 tree stmt
= bsi_stmt (bsi
);
1980 if (first_store_uid
[bb
->index
] == 0
1981 && !ZERO_SSA_OPERANDS (stmt
, SSA_OP_VMAYUSE
| SSA_OP_VMAYDEF
1982 | SSA_OP_VMUSTDEF
| SSA_OP_VMUSTKILL
))
1984 first_store_uid
[bb
->index
] = stmt_ann (stmt
)->uid
;
1988 FOR_EACH_SSA_USE_OPERAND (usep
, stmt
, iter
, SSA_OP_VIRTUAL_KILLS
1991 tree use
= USE_FROM_PTR (usep
);
1992 bitmap repbit
= get_representative (vuse_names
,
1993 SSA_NAME_VERSION (use
));
1996 bitmap_and_compl_into (RVUSE_GEN (bb
), repbit
);
1997 bitmap_ior_into (RVUSE_KILL (bb
), repbit
);
2001 bitmap_set_bit (RVUSE_KILL (bb
), SSA_NAME_VERSION (use
));
2002 bitmap_clear_bit (RVUSE_GEN (bb
), SSA_NAME_VERSION (use
));
2005 FOR_EACH_SSA_DEF_OPERAND (defp
, stmt
, iter
, SSA_OP_VIRTUAL_DEFS
)
2007 tree def
= DEF_FROM_PTR (defp
);
2008 bitmap_set_bit (RVUSE_GEN (bb
), SSA_NAME_VERSION (def
));
2015 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
2017 if (!is_gimple_reg (PHI_RESULT (phi
)))
2022 tree def
= PHI_RESULT (phi
);
2023 /* In reality, the PHI result is generated at the end of
2024 each predecessor block. This will make the value
2025 LVUSE_IN for the bb containing the PHI, which is
2027 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
2028 bitmap_set_bit (RVUSE_GEN (e
->src
), SSA_NAME_VERSION (def
));
2033 /* Solve reaching vuses.
2035 RVUSE_IN[BB] = Union of RVUSE_OUT of predecessors.
2036 RVUSE_OUT[BB] = RVUSE_GEN[BB] U (RVUSE_IN[BB] - RVUSE_KILL[BB])
2038 postorder
= XNEWVEC (int, n_basic_blocks
- NUM_FIXED_BLOCKS
);
2039 pre_and_rev_post_order_compute (NULL
, postorder
, false);
2046 for (j
= 0; j
< n_basic_blocks
- NUM_FIXED_BLOCKS
; j
++)
2050 bb
= BASIC_BLOCK (postorder
[j
]);
2052 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
2053 bitmap_ior_into (RVUSE_IN (bb
), RVUSE_OUT (e
->src
));
2055 changed
|= bitmap_ior_and_compl (RVUSE_OUT (bb
),
2063 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2067 fprintf (dump_file
, "RVUSE_IN (%d) =", bb
->index
);
2068 dump_bitmap_of_names (dump_file
, RVUSE_IN (bb
));
2070 fprintf (dump_file
, "RVUSE_KILL (%d) =", bb
->index
);
2071 dump_bitmap_of_names (dump_file
, RVUSE_KILL (bb
));
2073 fprintf (dump_file
, "RVUSE_GEN (%d) =", bb
->index
);
2074 dump_bitmap_of_names (dump_file
, RVUSE_GEN (bb
));
2076 fprintf (dump_file
, "RVUSE_OUT (%d) =", bb
->index
);
2077 dump_bitmap_of_names (dump_file
, RVUSE_OUT (bb
));
2083 value_set_node_t node
;
2084 if (bitmap_empty_p (RVUSE_KILL (bb
)))
2087 for (node
= EXP_GEN (bb
)->head
; node
; node
= node
->next
)
2089 if (REFERENCE_CLASS_P (node
->expr
))
2091 tree vh
= get_value_handle (node
->expr
);
2092 tree maybe
= bitmap_find_leader (AVAIL_OUT (bb
), vh
);
2096 tree def
= SSA_NAME_DEF_STMT (maybe
);
2098 if (bb_for_stmt (def
) != bb
)
2101 if (TREE_CODE (def
) == PHI_NODE
2102 || stmt_ann (def
)->uid
< first_store_uid
[bb
->index
])
2104 if (ANTIC_SAFE_LOADS (bb
) == NULL
)
2105 ANTIC_SAFE_LOADS (bb
) = set_new (true);
2106 value_insert_into_set (ANTIC_SAFE_LOADS (bb
),
2113 free (first_store_uid
);
2116 /* Return true if we can value number the call in STMT. This is true
2117 if we have a pure or constant call. */
2120 can_value_number_call (tree stmt
)
2122 tree call
= get_call_expr_in (stmt
);
2124 if (call_expr_flags (call
) & (ECF_PURE
| ECF_CONST
))
2129 /* Return true if OP is a tree which we can perform value numbering
2133 can_value_number_operation (tree op
)
2135 return UNARY_CLASS_P (op
)
2136 || BINARY_CLASS_P (op
)
2137 || COMPARISON_CLASS_P (op
)
2138 || REFERENCE_CLASS_P (op
)
2139 || (TREE_CODE (op
) == CALL_EXPR
2140 && can_value_number_call (op
));
2144 /* Return true if OP is a tree which we can perform PRE on
2145 on. This may not match the operations we can value number, but in
2146 a perfect world would. */
2149 can_PRE_operation (tree op
)
2151 return UNARY_CLASS_P (op
)
2152 || BINARY_CLASS_P (op
)
2153 || COMPARISON_CLASS_P (op
)
2154 || TREE_CODE (op
) == INDIRECT_REF
2155 || TREE_CODE (op
) == COMPONENT_REF
2156 || TREE_CODE (op
) == CALL_EXPR
2157 || TREE_CODE (op
) == ARRAY_REF
;
2161 /* Inserted expressions are placed onto this worklist, which is used
2162 for performing quick dead code elimination of insertions we made
2163 that didn't turn out to be necessary. */
2164 static VEC(tree
,heap
) *inserted_exprs
;
2166 /* Pool allocated fake store expressions are placed onto this
2167 worklist, which, after performing dead code elimination, is walked
2168 to see which expressions need to be put into GC'able memory */
2169 static VEC(tree
, heap
) *need_creation
;
2171 /* For COMPONENT_REF's and ARRAY_REF's, we can't have any intermediates for the
2172 COMPONENT_REF or INDIRECT_REF or ARRAY_REF portion, because we'd end up with
2173 trying to rename aggregates into ssa form directly, which is a no
2176 Thus, this routine doesn't create temporaries, it just builds a
2177 single access expression for the array, calling
2178 find_or_generate_expression to build the innermost pieces.
2180 This function is a subroutine of create_expression_by_pieces, and
2181 should not be called on it's own unless you really know what you
2185 create_component_ref_by_pieces (basic_block block
, tree expr
, tree stmts
)
2190 if (TREE_CODE (genop
) == VALUE_HANDLE
)
2192 tree found
= bitmap_find_leader (AVAIL_OUT (block
), expr
);
2197 if (TREE_CODE (genop
) == VALUE_HANDLE
)
2198 genop
= VALUE_HANDLE_EXPR_SET (expr
)->head
->expr
;
2200 switch TREE_CODE (genop
)
2206 op0
= create_component_ref_by_pieces (block
,
2207 TREE_OPERAND (genop
, 0),
2209 op1
= TREE_OPERAND (genop
, 1);
2210 if (TREE_CODE (op1
) == VALUE_HANDLE
)
2211 op1
= find_or_generate_expression (block
, op1
, stmts
);
2212 op2
= TREE_OPERAND (genop
, 2);
2213 if (op2
&& TREE_CODE (op2
) == VALUE_HANDLE
)
2214 op2
= find_or_generate_expression (block
, op2
, stmts
);
2215 op3
= TREE_OPERAND (genop
, 3);
2216 if (op3
&& TREE_CODE (op3
) == VALUE_HANDLE
)
2217 op3
= find_or_generate_expression (block
, op3
, stmts
);
2218 folded
= build4 (ARRAY_REF
, TREE_TYPE (genop
), op0
, op1
,
2226 op0
= create_component_ref_by_pieces (block
,
2227 TREE_OPERAND (genop
, 0),
2229 op1
= VALUE_HANDLE_EXPR_SET (TREE_OPERAND (genop
, 1))->head
->expr
;
2230 folded
= fold_build3 (COMPONENT_REF
, TREE_TYPE (genop
), op0
, op1
,
2237 tree op1
= TREE_OPERAND (genop
, 0);
2238 tree genop1
= find_or_generate_expression (block
, op1
, stmts
);
2240 folded
= fold_build1 (TREE_CODE (genop
), TREE_TYPE (genop
),
2258 /* Find a leader for an expression, or generate one using
2259 create_expression_by_pieces if it's ANTIC but
2261 BLOCK is the basic_block we are looking for leaders in.
2262 EXPR is the expression to find a leader or generate for.
2263 STMTS is the statement list to put the inserted expressions on.
2264 Returns the SSA_NAME of the LHS of the generated expression or the
2268 find_or_generate_expression (basic_block block
, tree expr
, tree stmts
)
2270 tree genop
= bitmap_find_leader (AVAIL_OUT (block
), expr
);
2272 /* If it's still NULL, it must be a complex expression, so generate
2276 genop
= VALUE_HANDLE_EXPR_SET (expr
)->head
->expr
;
2278 gcc_assert (can_PRE_operation (genop
));
2279 genop
= create_expression_by_pieces (block
, genop
, stmts
);
2284 #define NECESSARY(stmt) stmt->common.asm_written_flag
2285 /* Create an expression in pieces, so that we can handle very complex
2286 expressions that may be ANTIC, but not necessary GIMPLE.
2287 BLOCK is the basic block the expression will be inserted into,
2288 EXPR is the expression to insert (in value form)
2289 STMTS is a statement list to append the necessary insertions into.
2291 This function will die if we hit some value that shouldn't be
2292 ANTIC but is (IE there is no leader for it, or its components).
2293 This function may also generate expressions that are themselves
2294 partially or fully redundant. Those that are will be either made
2295 fully redundant during the next iteration of insert (for partially
2296 redundant ones), or eliminated by eliminate (for fully redundant
2300 create_expression_by_pieces (basic_block block
, tree expr
, tree stmts
)
2303 tree folded
, forced_stmts
, newexpr
;
2305 tree_stmt_iterator tsi
;
2307 switch (TREE_CODE_CLASS (TREE_CODE (expr
)))
2309 case tcc_expression
:
2313 tree genop0
, genop2
;
2315 tree walker
, genwalker
;
2317 gcc_assert (TREE_CODE (expr
) == CALL_EXPR
);
2320 op0
= TREE_OPERAND (expr
, 0);
2321 arglist
= TREE_OPERAND (expr
, 1);
2322 op2
= TREE_OPERAND (expr
, 2);
2324 genop0
= find_or_generate_expression (block
, op0
, stmts
);
2325 genarglist
= copy_list (arglist
);
2326 for (walker
= arglist
, genwalker
= genarglist
;
2327 genwalker
&& walker
;
2328 genwalker
= TREE_CHAIN (genwalker
), walker
= TREE_CHAIN (walker
))
2330 TREE_VALUE (genwalker
)
2331 = find_or_generate_expression (block
, TREE_VALUE (walker
),
2336 genop2
= find_or_generate_expression (block
, op2
, stmts
);
2337 folded
= fold_build3 (TREE_CODE (expr
), TREE_TYPE (expr
),
2338 genop0
, genarglist
, genop2
);
2346 if (TREE_CODE (expr
) == COMPONENT_REF
2347 || TREE_CODE (expr
) == ARRAY_REF
)
2349 folded
= create_component_ref_by_pieces (block
, expr
, stmts
);
2353 tree op1
= TREE_OPERAND (expr
, 0);
2354 tree genop1
= find_or_generate_expression (block
, op1
, stmts
);
2356 folded
= fold_build1 (TREE_CODE (expr
), TREE_TYPE (expr
),
2363 case tcc_comparison
:
2365 tree op1
= TREE_OPERAND (expr
, 0);
2366 tree op2
= TREE_OPERAND (expr
, 1);
2367 tree genop1
= find_or_generate_expression (block
, op1
, stmts
);
2368 tree genop2
= find_or_generate_expression (block
, op2
, stmts
);
2369 folded
= fold_build2 (TREE_CODE (expr
), TREE_TYPE (expr
),
2376 tree op1
= TREE_OPERAND (expr
, 0);
2377 tree genop1
= find_or_generate_expression (block
, op1
, stmts
);
2378 folded
= fold_build1 (TREE_CODE (expr
), TREE_TYPE (expr
),
2387 /* Force the generated expression to be a sequence of GIMPLE
2389 We have to call unshare_expr because force_gimple_operand may
2390 modify the tree we pass to it. */
2391 newexpr
= force_gimple_operand (unshare_expr (folded
), &forced_stmts
,
2394 /* If we have any intermediate expressions to the value sets, add them
2395 to the value sets and chain them on in the instruction stream. */
2398 tsi
= tsi_start (forced_stmts
);
2399 for (; !tsi_end_p (tsi
); tsi_next (&tsi
))
2401 tree stmt
= tsi_stmt (tsi
);
2402 tree forcedname
= TREE_OPERAND (stmt
, 0);
2403 tree forcedexpr
= TREE_OPERAND (stmt
, 1);
2404 tree val
= vn_lookup_or_add (forcedexpr
, NULL
);
2406 VEC_safe_push (tree
, heap
, inserted_exprs
, stmt
);
2407 vn_add (forcedname
, val
);
2408 bitmap_value_replace_in_set (NEW_SETS (block
), forcedname
);
2409 bitmap_value_replace_in_set (AVAIL_OUT (block
), forcedname
);
2410 mark_new_vars_to_rename (stmt
);
2412 tsi
= tsi_last (stmts
);
2413 tsi_link_after (&tsi
, forced_stmts
, TSI_CONTINUE_LINKING
);
2416 /* Build and insert the assignment of the end result to the temporary
2417 that we will return. */
2418 if (!pretemp
|| TREE_TYPE (expr
) != TREE_TYPE (pretemp
))
2420 pretemp
= create_tmp_var (TREE_TYPE (expr
), "pretmp");
2421 get_var_ann (pretemp
);
2425 add_referenced_tmp_var (temp
);
2427 if (TREE_CODE (TREE_TYPE (expr
)) == COMPLEX_TYPE
)
2428 DECL_COMPLEX_GIMPLE_REG_P (temp
) = 1;
2430 newexpr
= build2 (MODIFY_EXPR
, TREE_TYPE (expr
), temp
, newexpr
);
2431 name
= make_ssa_name (temp
, newexpr
);
2432 TREE_OPERAND (newexpr
, 0) = name
;
2433 NECESSARY (newexpr
) = 0;
2435 tsi
= tsi_last (stmts
);
2436 tsi_link_after (&tsi
, newexpr
, TSI_CONTINUE_LINKING
);
2437 VEC_safe_push (tree
, heap
, inserted_exprs
, newexpr
);
2438 mark_new_vars_to_rename (newexpr
);
2440 /* Add a value handle to the temporary.
2441 The value may already exist in either NEW_SETS, or AVAIL_OUT, because
2442 we are creating the expression by pieces, and this particular piece of
2443 the expression may have been represented. There is no harm in replacing
2445 v
= get_value_handle (expr
);
2447 bitmap_value_replace_in_set (NEW_SETS (block
), name
);
2448 bitmap_value_replace_in_set (AVAIL_OUT (block
), name
);
2450 pre_stats
.insertions
++;
2451 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2453 fprintf (dump_file
, "Inserted ");
2454 print_generic_expr (dump_file
, newexpr
, 0);
2455 fprintf (dump_file
, " in predecessor %d\n", block
->index
);
2461 /* Insert the to-be-made-available values of NODE for each
2462 predecessor, stored in AVAIL, into the predecessors of BLOCK, and
2463 merge the result with a phi node, given the same value handle as
2464 NODE. Return true if we have inserted new stuff. */
2467 insert_into_preds_of_block (basic_block block
, value_set_node_t node
,
2470 tree val
= get_value_handle (node
->expr
);
2472 bool insertions
= false;
2477 tree type
= TREE_TYPE (avail
[EDGE_PRED (block
, 0)->src
->index
]);
2480 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2482 fprintf (dump_file
, "Found partial redundancy for expression ");
2483 print_generic_expr (dump_file
, node
->expr
, 0);
2484 fprintf (dump_file
, " (");
2485 print_generic_expr (dump_file
, val
, 0);
2486 fprintf (dump_file
, ")");
2487 fprintf (dump_file
, "\n");
2490 /* Make sure we aren't creating an induction variable. */
2491 if (block
->loop_depth
> 0 && EDGE_COUNT (block
->preds
) == 2
2492 && TREE_CODE_CLASS (TREE_CODE (node
->expr
)) != tcc_reference
)
2494 bool firstinsideloop
= false;
2495 bool secondinsideloop
= false;
2496 firstinsideloop
= flow_bb_inside_loop_p (block
->loop_father
,
2497 EDGE_PRED (block
, 0)->src
);
2498 secondinsideloop
= flow_bb_inside_loop_p (block
->loop_father
,
2499 EDGE_PRED (block
, 1)->src
);
2500 /* Induction variables only have one edge inside the loop. */
2501 if (firstinsideloop
^ secondinsideloop
)
2503 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2504 fprintf (dump_file
, "Skipping insertion of phi for partial redundancy: Looks like an induction variable\n");
2510 /* Make the necessary insertions. */
2511 FOR_EACH_EDGE (pred
, ei
, block
->preds
)
2513 tree stmts
= alloc_stmt_list ();
2516 eprime
= avail
[bprime
->index
];
2518 if (can_PRE_operation (eprime
))
2520 #ifdef ENABLE_CHECKING
2523 /* eprime may be an invariant. */
2524 vh
= TREE_CODE (eprime
) == VALUE_HANDLE
2526 : get_value_handle (eprime
);
2528 /* ensure that the virtual uses we need reach our block. */
2529 if (TREE_CODE (vh
) == VALUE_HANDLE
)
2534 VEC_iterate (tree
, VALUE_HANDLE_VUSES (vh
), i
, vuse
);
2537 size_t id
= SSA_NAME_VERSION (vuse
);
2538 gcc_assert (bitmap_bit_p (RVUSE_OUT (bprime
), id
)
2539 || IS_EMPTY_STMT (SSA_NAME_DEF_STMT (vuse
)));
2543 builtexpr
= create_expression_by_pieces (bprime
,
2546 bsi_insert_on_edge (pred
, stmts
);
2547 avail
[bprime
->index
] = builtexpr
;
2551 /* If we didn't want a phi node, and we made insertions, we still have
2552 inserted new stuff, and thus return true. If we didn't want a phi node,
2553 and didn't make insertions, we haven't added anything new, so return
2555 if (nophi
&& insertions
)
2557 else if (nophi
&& !insertions
)
2560 /* Now build a phi for the new variable. */
2561 if (!prephitemp
|| TREE_TYPE (prephitemp
) != type
)
2563 prephitemp
= create_tmp_var (type
, "prephitmp");
2564 get_var_ann (prephitemp
);
2568 add_referenced_tmp_var (temp
);
2570 if (TREE_CODE (type
) == COMPLEX_TYPE
)
2571 DECL_COMPLEX_GIMPLE_REG_P (temp
) = 1;
2572 temp
= create_phi_node (temp
, block
);
2574 NECESSARY (temp
) = 0;
2575 VEC_safe_push (tree
, heap
, inserted_exprs
, temp
);
2576 FOR_EACH_EDGE (pred
, ei
, block
->preds
)
2577 add_phi_arg (temp
, avail
[pred
->src
->index
], pred
);
2579 vn_add (PHI_RESULT (temp
), val
);
2581 /* The value should *not* exist in PHI_GEN, or else we wouldn't be doing
2582 this insertion, since we test for the existence of this value in PHI_GEN
2583 before proceeding with the partial redundancy checks in insert_aux.
2585 The value may exist in AVAIL_OUT, in particular, it could be represented
2586 by the expression we are trying to eliminate, in which case we want the
2587 replacement to occur. If it's not existing in AVAIL_OUT, we want it
2590 Similarly, to the PHI_GEN case, the value should not exist in NEW_SETS of
2591 this block, because if it did, it would have existed in our dominator's
2592 AVAIL_OUT, and would have been skipped due to the full redundancy check.
2595 bitmap_insert_into_set (PHI_GEN (block
),
2597 bitmap_value_replace_in_set (AVAIL_OUT (block
),
2599 bitmap_insert_into_set (NEW_SETS (block
),
2602 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2604 fprintf (dump_file
, "Created phi ");
2605 print_generic_expr (dump_file
, temp
, 0);
2606 fprintf (dump_file
, " in block %d\n", block
->index
);
2614 /* Perform insertion of partially redundant values.
2615 For BLOCK, do the following:
2616 1. Propagate the NEW_SETS of the dominator into the current block.
2617 If the block has multiple predecessors,
2618 2a. Iterate over the ANTIC expressions for the block to see if
2619 any of them are partially redundant.
2620 2b. If so, insert them into the necessary predecessors to make
2621 the expression fully redundant.
2622 2c. Insert a new PHI merging the values of the predecessors.
2623 2d. Insert the new PHI, and the new expressions, into the
2625 3. Recursively call ourselves on the dominator children of BLOCK.
2630 insert_aux (basic_block block
)
2633 bool new_stuff
= false;
2638 dom
= get_immediate_dominator (CDI_DOMINATORS
, block
);
2643 bitmap_set_t newset
= NEW_SETS (dom
);
2646 /* Note that we need to value_replace both NEW_SETS, and
2647 AVAIL_OUT. For both the case of NEW_SETS, the value may be
2648 represented by some non-simple expression here that we want
2649 to replace it with. */
2650 EXECUTE_IF_SET_IN_BITMAP (newset
->expressions
, 0, i
, bi
)
2652 bitmap_value_replace_in_set (NEW_SETS (block
), ssa_name (i
));
2653 bitmap_value_replace_in_set (AVAIL_OUT (block
), ssa_name (i
));
2656 if (!single_pred_p (block
))
2658 value_set_node_t node
;
2659 for (node
= ANTIC_IN (block
)->head
;
2663 if (can_PRE_operation (node
->expr
)
2664 && !AGGREGATE_TYPE_P (TREE_TYPE (node
->expr
)))
2668 bool by_some
= false;
2669 bool cant_insert
= false;
2670 bool all_same
= true;
2671 tree first_s
= NULL
;
2674 tree eprime
= NULL_TREE
;
2677 val
= get_value_handle (node
->expr
);
2678 if (bitmap_set_contains_value (PHI_GEN (block
), val
))
2680 if (bitmap_set_contains_value (AVAIL_OUT (dom
), val
))
2682 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2683 fprintf (dump_file
, "Found fully redundant value\n");
2687 avail
= XCNEWVEC (tree
, last_basic_block
);
2688 FOR_EACH_EDGE (pred
, ei
, block
->preds
)
2693 /* This can happen in the very weird case
2694 that our fake infinite loop edges have caused a
2695 critical edge to appear. */
2696 if (EDGE_CRITICAL_P (pred
))
2702 eprime
= phi_translate (node
->expr
,
2706 /* eprime will generally only be NULL if the
2707 value of the expression, translated
2708 through the PHI for this predecessor, is
2709 undefined. If that is the case, we can't
2710 make the expression fully redundant,
2711 because its value is undefined along a
2712 predecessor path. We can thus break out
2713 early because it doesn't matter what the
2714 rest of the results are. */
2721 eprime
= fully_constant_expression (eprime
);
2722 vprime
= get_value_handle (eprime
);
2723 gcc_assert (vprime
);
2724 edoubleprime
= bitmap_find_leader (AVAIL_OUT (bprime
),
2726 if (edoubleprime
== NULL
)
2728 avail
[bprime
->index
] = eprime
;
2733 avail
[bprime
->index
] = edoubleprime
;
2735 if (first_s
== NULL
)
2736 first_s
= edoubleprime
;
2737 else if (!operand_equal_p (first_s
, edoubleprime
,
2742 /* If we can insert it, it's not the same value
2743 already existing along every predecessor, and
2744 it's defined by some predecessor, it is
2745 partially redundant. */
2746 if (!cant_insert
&& !all_same
&& by_some
)
2748 if (insert_into_preds_of_block (block
, node
, avail
))
2751 /* If all edges produce the same value and that value is
2752 an invariant, then the PHI has the same value on all
2753 edges. Note this. */
2754 else if (!cant_insert
&& all_same
&& eprime
2755 && is_gimple_min_invariant (eprime
)
2756 && !is_gimple_min_invariant (val
))
2758 value_set_t exprset
= VALUE_HANDLE_EXPR_SET (val
);
2759 value_set_node_t node
;
2761 for (node
= exprset
->head
; node
; node
= node
->next
)
2763 if (TREE_CODE (node
->expr
) == SSA_NAME
)
2765 vn_add (node
->expr
, eprime
);
2766 pre_stats
.constified
++;
2776 for (son
= first_dom_son (CDI_DOMINATORS
, block
);
2778 son
= next_dom_son (CDI_DOMINATORS
, son
))
2780 new_stuff
|= insert_aux (son
);
2786 /* Perform insertion of partially redundant values. */
2791 bool new_stuff
= true;
2793 int num_iterations
= 0;
2796 NEW_SETS (bb
) = bitmap_set_new ();
2802 new_stuff
= insert_aux (ENTRY_BLOCK_PTR
);
2804 if (num_iterations
> 2 && dump_file
&& (dump_flags
& TDF_STATS
))
2805 fprintf (dump_file
, "insert required %d iterations\n", num_iterations
);
2809 /* Return true if VAR is an SSA variable with no defining statement in
2810 this procedure, *AND* isn't a live-on-entry parameter. */
2813 is_undefined_value (tree expr
)
2815 return (TREE_CODE (expr
) == SSA_NAME
2816 && IS_EMPTY_STMT (SSA_NAME_DEF_STMT (expr
))
2817 /* PARM_DECLs and hard registers are always defined. */
2818 && TREE_CODE (SSA_NAME_VAR (expr
)) != PARM_DECL
);
2822 /* Given an SSA variable VAR and an expression EXPR, compute the value
2823 number for EXPR and create a value handle (VAL) for it. If VAR and
2824 EXPR are not the same, associate VAL with VAR. Finally, add VAR to
2825 S1 and its value handle to S2.
2827 VUSES represent the virtual use operands associated with EXPR (if
2831 add_to_sets (tree var
, tree expr
, tree stmt
, bitmap_set_t s1
,
2834 tree val
= vn_lookup_or_add (expr
, stmt
);
2836 /* VAR and EXPR may be the same when processing statements for which
2837 we are not computing value numbers (e.g., non-assignments, or
2838 statements that make aliased stores). In those cases, we are
2839 only interested in making VAR available as its own value. */
2844 bitmap_insert_into_set (s1
, var
);
2845 bitmap_value_insert_into_set (s2
, var
);
2849 /* Given a unary or binary expression EXPR, create and return a new
2850 expression with the same structure as EXPR but with its operands
2851 replaced with the value handles of each of the operands of EXPR.
2853 VUSES represent the virtual use operands associated with EXPR (if
2854 any). Insert EXPR's operands into the EXP_GEN set for BLOCK. */
2857 create_value_expr_from (tree expr
, basic_block block
, tree stmt
)
2860 enum tree_code code
= TREE_CODE (expr
);
2864 gcc_assert (TREE_CODE_CLASS (code
) == tcc_unary
2865 || TREE_CODE_CLASS (code
) == tcc_binary
2866 || TREE_CODE_CLASS (code
) == tcc_comparison
2867 || TREE_CODE_CLASS (code
) == tcc_reference
2868 || TREE_CODE_CLASS (code
) == tcc_expression
2869 || TREE_CODE_CLASS (code
) == tcc_exceptional
2870 || TREE_CODE_CLASS (code
) == tcc_declaration
);
2872 if (TREE_CODE_CLASS (code
) == tcc_unary
)
2873 pool
= unary_node_pool
;
2874 else if (TREE_CODE_CLASS (code
) == tcc_reference
)
2875 pool
= reference_node_pool
;
2876 else if (TREE_CODE_CLASS (code
) == tcc_binary
)
2877 pool
= binary_node_pool
;
2878 else if (TREE_CODE_CLASS (code
) == tcc_comparison
)
2879 pool
= comparison_node_pool
;
2880 else if (TREE_CODE_CLASS (code
) == tcc_exceptional
)
2882 gcc_assert (code
== TREE_LIST
);
2883 pool
= list_node_pool
;
2887 gcc_assert (code
== CALL_EXPR
);
2888 pool
= expression_node_pool
;
2891 vexpr
= (tree
) pool_alloc (pool
);
2892 memcpy (vexpr
, expr
, tree_size (expr
));
2894 /* This case is only for TREE_LIST's that appear as part of
2895 CALL_EXPR's. Anything else is a bug, but we can't easily verify
2896 this, hence this comment. TREE_LIST is not handled by the
2897 general case below is because they don't have a fixed length, or
2898 operands, so you can't access purpose/value/chain through
2899 TREE_OPERAND macros. */
2901 if (code
== TREE_LIST
)
2903 tree op
= NULL_TREE
;
2904 tree temp
= NULL_TREE
;
2905 if (TREE_CHAIN (vexpr
))
2906 temp
= create_value_expr_from (TREE_CHAIN (vexpr
), block
, stmt
);
2907 TREE_CHAIN (vexpr
) = temp
? temp
: TREE_CHAIN (vexpr
);
2910 /* Recursively value-numberize reference ops. */
2911 if (REFERENCE_CLASS_P (TREE_VALUE (vexpr
)))
2914 op
= TREE_VALUE (vexpr
);
2915 tempop
= create_value_expr_from (op
, block
, stmt
);
2916 op
= tempop
? tempop
: op
;
2918 TREE_VALUE (vexpr
) = vn_lookup_or_add (op
, stmt
);
2922 op
= TREE_VALUE (vexpr
);
2923 TREE_VALUE (vexpr
) = vn_lookup_or_add (TREE_VALUE (vexpr
), NULL
);
2925 /* This is the equivalent of inserting op into EXP_GEN like we
2927 if (!is_undefined_value (op
))
2928 value_insert_into_set (EXP_GEN (block
), op
);
2933 for (i
= 0; i
< TREE_CODE_LENGTH (code
); i
++)
2937 op
= TREE_OPERAND (expr
, i
);
2938 if (op
== NULL_TREE
)
2941 /* Recursively value-numberize reference ops and tree lists. */
2942 if (REFERENCE_CLASS_P (op
))
2944 tree tempop
= create_value_expr_from (op
, block
, stmt
);
2945 op
= tempop
? tempop
: op
;
2946 val
= vn_lookup_or_add (op
, stmt
);
2948 else if (TREE_CODE (op
) == TREE_LIST
)
2952 gcc_assert (TREE_CODE (expr
) == CALL_EXPR
);
2953 tempop
= create_value_expr_from (op
, block
, stmt
);
2955 op
= tempop
? tempop
: op
;
2956 vn_lookup_or_add (op
, NULL
);
2957 /* Unlike everywhere else, we do *not* want to replace the
2958 TREE_LIST itself with a value number, because support
2959 functions we call will blow up. */
2963 /* Create a value handle for OP and add it to VEXPR. */
2964 val
= vn_lookup_or_add (op
, NULL
);
2966 if (!is_undefined_value (op
) && TREE_CODE (op
) != TREE_LIST
)
2967 value_insert_into_set (EXP_GEN (block
), op
);
2969 if (TREE_CODE (val
) == VALUE_HANDLE
)
2970 TREE_TYPE (val
) = TREE_TYPE (TREE_OPERAND (vexpr
, i
));
2972 TREE_OPERAND (vexpr
, i
) = val
;
2980 /* Insert extra phis to merge values that are fully available from
2981 preds of BLOCK, but have no dominating representative coming from
2985 insert_extra_phis (basic_block block
, basic_block dom
)
2988 if (!single_pred_p (block
))
2993 bitmap_set_t tempset
= bitmap_set_new ();
2995 FOR_EACH_EDGE (e
, ei
, block
->preds
)
2997 /* We cannot handle abnormal incoming edges correctly. */
2998 if (e
->flags
& EDGE_ABNORMAL
)
3003 bitmap_set_copy (tempset
, AVAIL_OUT (e
->src
));
3007 bitmap_set_and (tempset
, AVAIL_OUT (e
->src
));
3011 bitmap_set_and_compl (tempset
, AVAIL_OUT (dom
));
3013 if (!bitmap_set_empty_p (tempset
))
3018 EXECUTE_IF_SET_IN_BITMAP (tempset
->expressions
, 0, i
, bi
)
3020 tree name
= ssa_name (i
);
3021 tree val
= get_value_handle (name
);
3024 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name
))
3028 || TREE_TYPE (name
) != TREE_TYPE (mergephitemp
))
3030 mergephitemp
= create_tmp_var (TREE_TYPE (name
),
3032 get_var_ann (mergephitemp
);
3034 temp
= mergephitemp
;
3036 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3038 fprintf (dump_file
, "Creating phi ");
3039 print_generic_expr (dump_file
, temp
, 0);
3040 fprintf (dump_file
, " to merge available but not dominating values ");
3043 add_referenced_tmp_var (temp
);
3044 temp
= create_phi_node (temp
, block
);
3045 NECESSARY (temp
) = 0;
3046 VEC_safe_push (tree
, heap
, inserted_exprs
, temp
);
3048 FOR_EACH_EDGE (e
, ei
, block
->preds
)
3050 tree leader
= bitmap_find_leader (AVAIL_OUT (e
->src
), val
);
3052 gcc_assert (leader
);
3053 add_phi_arg (temp
, leader
, e
);
3055 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3057 print_generic_expr (dump_file
, leader
, 0);
3058 fprintf (dump_file
, " in block %d,", e
->src
->index
);
3062 vn_add (PHI_RESULT (temp
), val
);
3064 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3065 fprintf (dump_file
, "\n");
3071 /* Given a statement STMT and its right hand side which is a load, try
3072 to look for the expression stored in the location for the load, and
3073 return true if a useful equivalence was recorded for LHS. */
3076 try_look_through_load (tree lhs
, tree mem_ref
, tree stmt
, basic_block block
)
3078 tree store_stmt
= NULL
;
3083 FOR_EACH_SSA_TREE_OPERAND (vuse
, stmt
, i
, SSA_OP_VIRTUAL_USES
)
3087 gcc_assert (TREE_CODE (vuse
) == SSA_NAME
);
3088 def_stmt
= SSA_NAME_DEF_STMT (vuse
);
3090 /* If there is no useful statement for this VUSE, we'll not find a
3091 useful expression to return either. Likewise, if there is a
3092 statement but it is not a simple assignment or it has virtual
3093 uses, we can stop right here. Note that this means we do
3094 not look through PHI nodes, which is intentional. */
3096 || TREE_CODE (def_stmt
) != MODIFY_EXPR
3097 || !ZERO_SSA_OPERANDS (def_stmt
, SSA_OP_VIRTUAL_USES
))
3100 /* If this is not the same statement as one we have looked at for
3101 another VUSE of STMT already, we have two statements producing
3102 something that reaches our STMT. */
3103 if (store_stmt
&& store_stmt
!= def_stmt
)
3107 /* Is this a store to the exact same location as the one we are
3108 loading from in STMT? */
3109 if (!operand_equal_p (TREE_OPERAND (def_stmt
, 0), mem_ref
, 0))
3112 /* Otherwise remember this statement and see if all other VUSEs
3113 come from the same statement. */
3114 store_stmt
= def_stmt
;
3118 /* Alright then, we have visited all VUSEs of STMT and we've determined
3119 that all of them come from the same statement STORE_STMT. See if there
3120 is a useful expression we can deduce from STORE_STMT. */
3121 rhs
= TREE_OPERAND (store_stmt
, 1);
3122 if ((TREE_CODE (rhs
) == SSA_NAME
3123 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs
))
3124 || is_gimple_min_invariant (rhs
)
3125 || TREE_CODE (rhs
) == ADDR_EXPR
3126 || TREE_INVARIANT (rhs
))
3129 /* Yay! Compute a value number for the RHS of the statement and
3130 add its value to the AVAIL_OUT set for the block. Add the LHS
3132 add_to_sets (lhs
, rhs
, store_stmt
, TMP_GEN (block
), AVAIL_OUT (block
));
3133 if (TREE_CODE (rhs
) == SSA_NAME
3134 && !is_undefined_value (rhs
))
3135 value_insert_into_set (EXP_GEN (block
), rhs
);
3142 /* Return a copy of NODE that is stored in the temporary alloc_pool's.
3143 This is made recursively true, so that the operands are stored in
3144 the pool as well. */
3147 poolify_tree (tree node
)
3149 switch (TREE_CODE (node
))
3153 tree temp
= pool_alloc (reference_node_pool
);
3154 memcpy (temp
, node
, tree_size (node
));
3155 TREE_OPERAND (temp
, 0) = poolify_tree (TREE_OPERAND (temp
, 0));
3161 tree temp
= pool_alloc (modify_expr_node_pool
);
3162 memcpy (temp
, node
, tree_size (node
));
3163 TREE_OPERAND (temp
, 0) = poolify_tree (TREE_OPERAND (temp
, 0));
3164 TREE_OPERAND (temp
, 1) = poolify_tree (TREE_OPERAND (temp
, 1));
3181 static tree modify_expr_template
;
3183 /* Allocate a MODIFY_EXPR with TYPE, and operands OP1, OP2 in the
3184 alloc pools and return it. */
3186 poolify_modify_expr (tree type
, tree op1
, tree op2
)
3188 if (modify_expr_template
== NULL
)
3189 modify_expr_template
= build2 (MODIFY_EXPR
, type
, op1
, op2
);
3191 TREE_OPERAND (modify_expr_template
, 0) = op1
;
3192 TREE_OPERAND (modify_expr_template
, 1) = op2
;
3193 TREE_TYPE (modify_expr_template
) = type
;
3195 return poolify_tree (modify_expr_template
);
3199 /* For each real store operation of the form
3200 *a = <value> that we see, create a corresponding fake store of the
3201 form storetmp_<version> = *a.
3203 This enables AVAIL computation to mark the results of stores as
3204 available. Without this, you'd need to do some computation to
3205 mark the result of stores as ANTIC and AVAIL at all the right
3207 To save memory, we keep the store
3208 statements pool allocated until we decide whether they are
3209 necessary or not. */
3212 insert_fake_stores (void)
3218 block_stmt_iterator bsi
;
3219 for (bsi
= bsi_start (block
); !bsi_end_p (bsi
); bsi_next (&bsi
))
3221 tree stmt
= bsi_stmt (bsi
);
3223 /* We can't generate SSA names for stores that are complex
3224 or aggregate. We also want to ignore things whose
3225 virtual uses occur in abnormal phis. */
3227 if (TREE_CODE (stmt
) == MODIFY_EXPR
3228 && TREE_CODE (TREE_OPERAND (stmt
, 0)) == INDIRECT_REF
3229 && !AGGREGATE_TYPE_P (TREE_TYPE (TREE_OPERAND (stmt
, 0)))
3230 && TREE_CODE (TREE_TYPE (TREE_OPERAND (stmt
, 0))) != COMPLEX_TYPE
)
3234 tree lhs
= TREE_OPERAND (stmt
, 0);
3235 tree rhs
= TREE_OPERAND (stmt
, 1);
3237 bool notokay
= false;
3239 FOR_EACH_SSA_DEF_OPERAND (defp
, stmt
, iter
, SSA_OP_VIRTUAL_DEFS
)
3241 tree defvar
= DEF_FROM_PTR (defp
);
3242 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (defvar
))
3252 if (!storetemp
|| TREE_TYPE (rhs
) != TREE_TYPE (storetemp
))
3254 storetemp
= create_tmp_var (TREE_TYPE (rhs
), "storetmp");
3255 get_var_ann (storetemp
);
3258 new = poolify_modify_expr (TREE_TYPE (stmt
), storetemp
, lhs
);
3260 lhs
= make_ssa_name (storetemp
, new);
3261 TREE_OPERAND (new, 0) = lhs
;
3262 create_ssa_artficial_load_stmt (new, stmt
);
3264 NECESSARY (new) = 0;
3265 VEC_safe_push (tree
, heap
, inserted_exprs
, new);
3266 VEC_safe_push (tree
, heap
, need_creation
, new);
3267 bsi_insert_after (&bsi
, new, BSI_NEW_STMT
);
3273 /* Turn the pool allocated fake stores that we created back into real
3274 GC allocated ones if they turned out to be necessary to PRE some
3278 realify_fake_stores (void)
3283 for (i
= 0; VEC_iterate (tree
, need_creation
, i
, stmt
); i
++)
3285 if (NECESSARY (stmt
))
3287 block_stmt_iterator bsi
;
3290 /* Mark the temp variable as referenced */
3291 add_referenced_tmp_var (SSA_NAME_VAR (TREE_OPERAND (stmt
, 0)));
3293 /* Put the new statement in GC memory, fix up the annotation
3294 and SSA_NAME_DEF_STMT on it, and then put it in place of
3295 the old statement in the IR stream. */
3296 newstmt
= unshare_expr (stmt
);
3297 SSA_NAME_DEF_STMT (TREE_OPERAND (newstmt
, 0)) = newstmt
;
3299 newstmt
->common
.ann
= stmt
->common
.ann
;
3301 bsi
= bsi_for_stmt (stmt
);
3302 bsi_replace (&bsi
, newstmt
, true);
3305 release_defs (stmt
);
3310 /* Compute the AVAIL set for all basic blocks.
3312 This function performs value numbering of the statements in each basic
3313 block. The AVAIL sets are built from information we glean while doing
3314 this value numbering, since the AVAIL sets contain only one entry per
3317 AVAIL_IN[BLOCK] = AVAIL_OUT[dom(BLOCK)].
3318 AVAIL_OUT[BLOCK] = AVAIL_IN[BLOCK] U PHI_GEN[BLOCK] U TMP_GEN[BLOCK]. */
3321 compute_avail (void)
3323 basic_block block
, son
;
3324 basic_block
*worklist
;
3327 /* For arguments with default definitions, we pretend they are
3328 defined in the entry block. */
3329 for (param
= DECL_ARGUMENTS (current_function_decl
);
3331 param
= TREE_CHAIN (param
))
3333 if (default_def (param
) != NULL
)
3335 tree def
= default_def (param
);
3336 vn_lookup_or_add (def
, NULL
);
3337 bitmap_insert_into_set (TMP_GEN (ENTRY_BLOCK_PTR
), def
);
3338 bitmap_value_insert_into_set (AVAIL_OUT (ENTRY_BLOCK_PTR
), def
);
3342 /* Likewise for the static chain decl. */
3343 if (cfun
->static_chain_decl
)
3345 param
= cfun
->static_chain_decl
;
3346 if (default_def (param
) != NULL
)
3348 tree def
= default_def (param
);
3349 vn_lookup_or_add (def
, NULL
);
3350 bitmap_insert_into_set (TMP_GEN (ENTRY_BLOCK_PTR
), def
);
3351 bitmap_value_insert_into_set (AVAIL_OUT (ENTRY_BLOCK_PTR
), def
);
3355 /* Allocate the worklist. */
3356 worklist
= XNEWVEC (basic_block
, n_basic_blocks
);
3358 /* Seed the algorithm by putting the dominator children of the entry
3359 block on the worklist. */
3360 for (son
= first_dom_son (CDI_DOMINATORS
, ENTRY_BLOCK_PTR
);
3362 son
= next_dom_son (CDI_DOMINATORS
, son
))
3363 worklist
[sp
++] = son
;
3365 /* Loop until the worklist is empty. */
3368 block_stmt_iterator bsi
;
3371 unsigned int stmt_uid
= 1;
3373 /* Pick a block from the worklist. */
3374 block
= worklist
[--sp
];
3376 /* Initially, the set of available values in BLOCK is that of
3377 its immediate dominator. */
3378 dom
= get_immediate_dominator (CDI_DOMINATORS
, block
);
3380 bitmap_set_copy (AVAIL_OUT (block
), AVAIL_OUT (dom
));
3383 insert_extra_phis (block
, dom
);
3385 /* Generate values for PHI nodes. */
3386 for (phi
= phi_nodes (block
); phi
; phi
= PHI_CHAIN (phi
))
3387 /* We have no need for virtual phis, as they don't represent
3388 actual computations. */
3389 if (is_gimple_reg (PHI_RESULT (phi
)))
3390 add_to_sets (PHI_RESULT (phi
), PHI_RESULT (phi
), NULL
,
3391 PHI_GEN (block
), AVAIL_OUT (block
));
3393 /* Now compute value numbers and populate value sets with all
3394 the expressions computed in BLOCK. */
3395 for (bsi
= bsi_start (block
); !bsi_end_p (bsi
); bsi_next (&bsi
))
3401 stmt
= bsi_stmt (bsi
);
3402 ann
= stmt_ann (stmt
);
3404 ann
->uid
= stmt_uid
++;
3406 /* For regular value numbering, we are only interested in
3407 assignments of the form X_i = EXPR, where EXPR represents
3408 an "interesting" computation, it has no volatile operands
3409 and X_i doesn't flow through an abnormal edge. */
3410 if (TREE_CODE (stmt
) == MODIFY_EXPR
3411 && !ann
->has_volatile_ops
3412 && TREE_CODE (TREE_OPERAND (stmt
, 0)) == SSA_NAME
3413 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (TREE_OPERAND (stmt
, 0)))
3415 tree lhs
= TREE_OPERAND (stmt
, 0);
3416 tree rhs
= TREE_OPERAND (stmt
, 1);
3418 /* Try to look through loads. */
3419 if (TREE_CODE (lhs
) == SSA_NAME
3420 && !ZERO_SSA_OPERANDS (stmt
, SSA_OP_VIRTUAL_USES
)
3421 && try_look_through_load (lhs
, rhs
, stmt
, block
))
3424 STRIP_USELESS_TYPE_CONVERSION (rhs
);
3425 if (can_value_number_operation (rhs
))
3427 /* For value numberable operation, create a
3428 duplicate expression with the operands replaced
3429 with the value handles of the original RHS. */
3430 tree newt
= create_value_expr_from (rhs
, block
, stmt
);
3433 add_to_sets (lhs
, newt
, stmt
, TMP_GEN (block
),
3435 value_insert_into_set (EXP_GEN (block
), newt
);
3439 else if ((TREE_CODE (rhs
) == SSA_NAME
3440 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs
))
3441 || is_gimple_min_invariant (rhs
)
3442 || TREE_CODE (rhs
) == ADDR_EXPR
3443 || TREE_INVARIANT (rhs
)
3446 /* Compute a value number for the RHS of the statement
3447 and add its value to the AVAIL_OUT set for the block.
3448 Add the LHS to TMP_GEN. */
3449 add_to_sets (lhs
, rhs
, stmt
, TMP_GEN (block
),
3452 if (TREE_CODE (rhs
) == SSA_NAME
3453 && !is_undefined_value (rhs
))
3454 value_insert_into_set (EXP_GEN (block
), rhs
);
3459 /* For any other statement that we don't recognize, simply
3460 make the names generated by the statement available in
3461 AVAIL_OUT and TMP_GEN. */
3462 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, iter
, SSA_OP_DEF
)
3463 add_to_sets (op
, op
, NULL
, TMP_GEN (block
), AVAIL_OUT (block
));
3465 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, iter
, SSA_OP_USE
)
3466 add_to_sets (op
, op
, NULL
, NULL
, AVAIL_OUT (block
));
3469 /* Put the dominator children of BLOCK on the worklist of blocks
3470 to compute available sets for. */
3471 for (son
= first_dom_son (CDI_DOMINATORS
, block
);
3473 son
= next_dom_son (CDI_DOMINATORS
, son
))
3474 worklist
[sp
++] = son
;
3481 /* Eliminate fully redundant computations. */
3490 block_stmt_iterator i
;
3492 for (i
= bsi_start (b
); !bsi_end_p (i
); bsi_next (&i
))
3494 tree stmt
= bsi_stmt (i
);
3496 /* Lookup the RHS of the expression, see if we have an
3497 available computation for it. If so, replace the RHS with
3498 the available computation. */
3499 if (TREE_CODE (stmt
) == MODIFY_EXPR
3500 && TREE_CODE (TREE_OPERAND (stmt
, 0)) == SSA_NAME
3501 && TREE_CODE (TREE_OPERAND (stmt
,1)) != SSA_NAME
3502 && !is_gimple_min_invariant (TREE_OPERAND (stmt
, 1))
3503 && !stmt_ann (stmt
)->has_volatile_ops
)
3505 tree lhs
= TREE_OPERAND (stmt
, 0);
3506 tree
*rhs_p
= &TREE_OPERAND (stmt
, 1);
3509 sprime
= bitmap_find_leader (AVAIL_OUT (b
),
3510 vn_lookup (lhs
, NULL
));
3513 && (TREE_CODE (*rhs_p
) != SSA_NAME
3514 || may_propagate_copy (*rhs_p
, sprime
)))
3516 gcc_assert (sprime
!= *rhs_p
);
3518 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3520 fprintf (dump_file
, "Replaced ");
3521 print_generic_expr (dump_file
, *rhs_p
, 0);
3522 fprintf (dump_file
, " with ");
3523 print_generic_expr (dump_file
, sprime
, 0);
3524 fprintf (dump_file
, " in ");
3525 print_generic_stmt (dump_file
, stmt
, 0);
3528 if (TREE_CODE (sprime
) == SSA_NAME
)
3529 NECESSARY (SSA_NAME_DEF_STMT (sprime
)) = 1;
3530 /* We need to make sure the new and old types actually match,
3531 which may require adding a simple cast, which fold_convert
3533 if (TREE_CODE (*rhs_p
) != SSA_NAME
3534 && !tree_ssa_useless_type_conversion_1 (TREE_TYPE (*rhs_p
),
3535 TREE_TYPE (sprime
)))
3536 sprime
= fold_convert (TREE_TYPE (*rhs_p
), sprime
);
3538 pre_stats
.eliminations
++;
3539 propagate_tree_value (rhs_p
, sprime
);
3542 /* If we removed EH side effects from the statement, clean
3543 its EH information. */
3544 if (maybe_clean_or_replace_eh_stmt (stmt
, stmt
))
3546 bitmap_set_bit (need_eh_cleanup
,
3547 bb_for_stmt (stmt
)->index
);
3548 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3549 fprintf (dump_file
, " Removed EH side effects.\n");
3557 /* Borrow a bit of tree-ssa-dce.c for the moment.
3558 XXX: In 4.1, we should be able to just run a DCE pass after PRE, though
3559 this may be a bit faster, and we may want critical edges kept split. */
3561 /* If OP's defining statement has not already been determined to be necessary,
3562 mark that statement necessary. Return the stmt, if it is newly
3566 mark_operand_necessary (tree op
)
3572 if (TREE_CODE (op
) != SSA_NAME
)
3575 stmt
= SSA_NAME_DEF_STMT (op
);
3578 if (NECESSARY (stmt
)
3579 || IS_EMPTY_STMT (stmt
))
3582 NECESSARY (stmt
) = 1;
3586 /* Because we don't follow exactly the standard PRE algorithm, and decide not
3587 to insert PHI nodes sometimes, and because value numbering of casts isn't
3588 perfect, we sometimes end up inserting dead code. This simple DCE-like
3589 pass removes any insertions we made that weren't actually used. */
3592 remove_dead_inserted_code (void)
3594 VEC(tree
,heap
) *worklist
= NULL
;
3598 worklist
= VEC_alloc (tree
, heap
, VEC_length (tree
, inserted_exprs
));
3599 for (i
= 0; VEC_iterate (tree
, inserted_exprs
, i
, t
); i
++)
3602 VEC_quick_push (tree
, worklist
, t
);
3604 while (VEC_length (tree
, worklist
) > 0)
3606 t
= VEC_pop (tree
, worklist
);
3608 /* PHI nodes are somewhat special in that each PHI alternative has
3609 data and control dependencies. All the statements feeding the
3610 PHI node's arguments are always necessary. */
3611 if (TREE_CODE (t
) == PHI_NODE
)
3615 VEC_reserve (tree
, heap
, worklist
, PHI_NUM_ARGS (t
));
3616 for (k
= 0; k
< PHI_NUM_ARGS (t
); k
++)
3618 tree arg
= PHI_ARG_DEF (t
, k
);
3619 if (TREE_CODE (arg
) == SSA_NAME
)
3621 arg
= mark_operand_necessary (arg
);
3623 VEC_quick_push (tree
, worklist
, arg
);
3629 /* Propagate through the operands. Examine all the USE, VUSE and
3630 V_MAY_DEF operands in this statement. Mark all the statements
3631 which feed this statement's uses as necessary. */
3635 /* The operands of V_MAY_DEF expressions are also needed as they
3636 represent potential definitions that may reach this
3637 statement (V_MAY_DEF operands allow us to follow def-def
3640 FOR_EACH_SSA_TREE_OPERAND (use
, t
, iter
, SSA_OP_ALL_USES
)
3642 tree n
= mark_operand_necessary (use
);
3644 VEC_safe_push (tree
, heap
, worklist
, n
);
3649 for (i
= 0; VEC_iterate (tree
, inserted_exprs
, i
, t
); i
++)
3653 block_stmt_iterator bsi
;
3655 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3657 fprintf (dump_file
, "Removing unnecessary insertion:");
3658 print_generic_stmt (dump_file
, t
, 0);
3661 if (TREE_CODE (t
) == PHI_NODE
)
3663 remove_phi_node (t
, NULL
);
3667 bsi
= bsi_for_stmt (t
);
3668 bsi_remove (&bsi
, true);
3673 VEC_free (tree
, heap
, worklist
);
3676 /* Initialize data structures used by PRE. */
3679 init_pre (bool do_fre
)
3685 inserted_exprs
= NULL
;
3686 need_creation
= NULL
;
3687 pretemp
= NULL_TREE
;
3688 storetemp
= NULL_TREE
;
3689 mergephitemp
= NULL_TREE
;
3690 prephitemp
= NULL_TREE
;
3694 current_loops
= loop_optimizer_init (LOOPS_NORMAL
);
3696 connect_infinite_loops_to_exit ();
3697 memset (&pre_stats
, 0, sizeof (pre_stats
));
3699 /* If block 0 has more than one predecessor, it means that its PHI
3700 nodes will have arguments coming from block -1. This creates
3701 problems for several places in PRE that keep local arrays indexed
3702 by block number. To prevent this, we split the edge coming from
3703 ENTRY_BLOCK_PTR (FIXME, if ENTRY_BLOCK_PTR had an index number
3704 different than -1 we wouldn't have to hack this. tree-ssa-dce.c
3705 needs a similar change). */
3706 if (!single_pred_p (single_succ (ENTRY_BLOCK_PTR
)))
3707 if (!(single_succ_edge (ENTRY_BLOCK_PTR
)->flags
& EDGE_ABNORMAL
))
3708 split_edge (single_succ_edge (ENTRY_BLOCK_PTR
));
3711 bb
->aux
= xcalloc (1, sizeof (struct bb_value_sets
));
3713 bitmap_obstack_initialize (&grand_bitmap_obstack
);
3714 phi_translate_table
= htab_create (511, expr_pred_trans_hash
,
3715 expr_pred_trans_eq
, free
);
3716 value_set_pool
= create_alloc_pool ("Value sets",
3717 sizeof (struct value_set
), 30);
3718 bitmap_set_pool
= create_alloc_pool ("Bitmap sets",
3719 sizeof (struct bitmap_set
), 30);
3720 value_set_node_pool
= create_alloc_pool ("Value set nodes",
3721 sizeof (struct value_set_node
), 30);
3722 calculate_dominance_info (CDI_POST_DOMINATORS
);
3723 calculate_dominance_info (CDI_DOMINATORS
);
3724 binary_node_pool
= create_alloc_pool ("Binary tree nodes",
3725 tree_code_size (PLUS_EXPR
), 30);
3726 unary_node_pool
= create_alloc_pool ("Unary tree nodes",
3727 tree_code_size (NEGATE_EXPR
), 30);
3728 reference_node_pool
= create_alloc_pool ("Reference tree nodes",
3729 tree_code_size (ARRAY_REF
), 30);
3730 expression_node_pool
= create_alloc_pool ("Expression tree nodes",
3731 tree_code_size (CALL_EXPR
), 30);
3732 list_node_pool
= create_alloc_pool ("List tree nodes",
3733 tree_code_size (TREE_LIST
), 30);
3734 comparison_node_pool
= create_alloc_pool ("Comparison tree nodes",
3735 tree_code_size (EQ_EXPR
), 30);
3736 modify_expr_node_pool
= create_alloc_pool ("MODIFY_EXPR nodes",
3737 tree_code_size (MODIFY_EXPR
),
3739 modify_expr_template
= NULL
;
3743 EXP_GEN (bb
) = set_new (true);
3744 PHI_GEN (bb
) = bitmap_set_new ();
3745 TMP_GEN (bb
) = bitmap_set_new ();
3746 AVAIL_OUT (bb
) = bitmap_set_new ();
3749 need_eh_cleanup
= BITMAP_ALLOC (NULL
);
3753 /* Deallocate data structures used by PRE. */
3756 fini_pre (bool do_fre
)
3761 VEC_free (tree
, heap
, inserted_exprs
);
3762 VEC_free (tree
, heap
, need_creation
);
3763 bitmap_obstack_release (&grand_bitmap_obstack
);
3764 free_alloc_pool (value_set_pool
);
3765 free_alloc_pool (bitmap_set_pool
);
3766 free_alloc_pool (value_set_node_pool
);
3767 free_alloc_pool (binary_node_pool
);
3768 free_alloc_pool (reference_node_pool
);
3769 free_alloc_pool (unary_node_pool
);
3770 free_alloc_pool (list_node_pool
);
3771 free_alloc_pool (expression_node_pool
);
3772 free_alloc_pool (comparison_node_pool
);
3773 free_alloc_pool (modify_expr_node_pool
);
3774 htab_delete (phi_translate_table
);
3775 remove_fake_exit_edges ();
3783 free_dominance_info (CDI_POST_DOMINATORS
);
3786 if (!bitmap_empty_p (need_eh_cleanup
))
3788 tree_purge_all_dead_eh_edges (need_eh_cleanup
);
3789 cleanup_tree_cfg ();
3792 BITMAP_FREE (need_eh_cleanup
);
3794 /* Wipe out pointers to VALUE_HANDLEs. In the not terribly distant
3795 future we will want them to be persistent though. */
3796 for (i
= 0; i
< num_ssa_names
; i
++)
3798 tree name
= ssa_name (i
);
3803 if (SSA_NAME_VALUE (name
)
3804 && TREE_CODE (SSA_NAME_VALUE (name
)) == VALUE_HANDLE
)
3805 SSA_NAME_VALUE (name
) = NULL
;
3807 if (!do_fre
&& current_loops
)
3809 loop_optimizer_finalize (current_loops
);
3810 current_loops
= NULL
;
3814 /* Main entry point to the SSA-PRE pass. DO_FRE is true if the caller
3815 only wants to do full redundancy elimination. */
3818 execute_pre (bool do_fre
)
3823 insert_fake_stores ();
3825 /* Collect and value number expressions computed in each basic block. */
3828 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3834 print_value_set (dump_file
, EXP_GEN (bb
), "exp_gen", bb
->index
);
3835 bitmap_print_value_set (dump_file
, TMP_GEN (bb
), "tmp_gen",
3837 bitmap_print_value_set (dump_file
, AVAIL_OUT (bb
), "avail_out",
3842 /* Insert can get quite slow on an incredibly large number of basic
3843 blocks due to some quadratic behavior. Until this behavior is
3844 fixed, don't run it when he have an incredibly large number of
3845 bb's. If we aren't going to run insert, there is no point in
3846 computing ANTIC, either, even though it's plenty fast. */
3847 if (!do_fre
&& n_basic_blocks
< 4000)
3849 vuse_names
= XCNEWVEC (bitmap
, num_ssa_names
);
3850 compute_rvuse_and_antic_safe ();
3856 /* Remove all the redundant expressions. */
3860 if (dump_file
&& (dump_flags
& TDF_STATS
))
3862 fprintf (dump_file
, "Insertions: %d\n", pre_stats
.insertions
);
3863 fprintf (dump_file
, "New PHIs: %d\n", pre_stats
.phis
);
3864 fprintf (dump_file
, "Eliminated: %d\n", pre_stats
.eliminations
);
3865 fprintf (dump_file
, "Constified: %d\n", pre_stats
.constified
);
3868 bsi_commit_edge_inserts ();
3872 remove_dead_inserted_code ();
3873 realify_fake_stores ();
3880 /* Gate and execute functions for PRE. */
3885 execute_pre (false);
3892 return flag_tree_pre
!= 0;
3895 struct tree_opt_pass pass_pre
=
3898 gate_pre
, /* gate */
3899 do_pre
, /* execute */
3902 0, /* static_pass_number */
3903 TV_TREE_PRE
, /* tv_id */
3904 PROP_no_crit_edges
| PROP_cfg
3905 | PROP_ssa
| PROP_alias
, /* properties_required */
3906 0, /* properties_provided */
3907 0, /* properties_destroyed */
3908 0, /* todo_flags_start */
3909 TODO_update_ssa_only_virtuals
| TODO_dump_func
| TODO_ggc_collect
3910 | TODO_verify_ssa
, /* todo_flags_finish */
3915 /* Gate and execute functions for FRE. */
3927 return flag_tree_fre
!= 0;
3930 struct tree_opt_pass pass_fre
=
3933 gate_fre
, /* gate */
3934 execute_fre
, /* execute */
3937 0, /* static_pass_number */
3938 TV_TREE_FRE
, /* tv_id */
3939 PROP_cfg
| PROP_ssa
| PROP_alias
, /* properties_required */
3940 0, /* properties_provided */
3941 0, /* properties_destroyed */
3942 0, /* todo_flags_start */
3943 TODO_dump_func
| TODO_ggc_collect
| TODO_verify_ssa
, /* todo_flags_finish */