2 Copyright (C) 2001, 2002, 2003, 2004 Free Software Foundation, Inc.
3 Contributed by Daniel Berlin <dan@dberlin.org> and Steven Bosscher
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify
9 it under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 2, or (at your option)
13 GCC is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 GNU General Public License for more details.
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING. If not, write to
20 the Free Software Foundation, 59 Temple Place - Suite 330,
21 Boston, MA 02111-1307, USA. */
25 #include "coretypes.h"
30 #include "basic-block.h"
31 #include "diagnostic.h"
32 #include "tree-inline.h"
33 #include "tree-flow.h"
34 #include "tree-gimple.h"
35 #include "tree-dump.h"
39 #include "tree-iterator.h"
41 #include "alloc-pool.h"
42 #include "tree-pass.h"
44 #include "splay-tree.h"
46 #include "langhooks.h"
50 1. Implement load value numbering.
51 2. Speed up insert_aux so that we can use it all the time. It
52 spends most of it's time in quadratic value replacement.
53 3. Avail sets can be shared by making an avail_find_leader that
54 walks up the dominator tree and looks in those avail sets.
55 This might affect code optimality, it's unclear right now.
56 4. Load motion can be performed by value numbering the loads the
57 same as we do other expressions. This requires iterative
58 hashing the vuses into the values. Right now we simply assign
59 a new value every time we see a statement with a vuse.
60 5. Strength reduction can be performed by anticipating expressions
61 we can repair later on.
62 6. Our canonicalization of expressions during lookups don't take
63 constants into account very well. In particular, we don't fold
64 anywhere, so we can get situations where we stupidly think
65 something is a new value (a + 1 + 1 vs a + 2). This is somewhat
66 expensive to fix, but it does expose a lot more eliminations.
67 It may or not be worth it, depending on how critical you
68 consider PRE vs just plain GRE.
71 /* For ease of terminology, "expression node" in the below refers to
72 every expression node but MODIFY_EXPR, because MODIFY_EXPR's represent
73 the actual statement containing the expressions we care about, and
74 we cache the value number by putting it in the expression. */
78 First we walk the statements to generate the AVAIL sets, the
79 EXP_GEN sets, and the tmp_gen sets. EXP_GEN sets represent the
80 generation of values/expressions by a given block. We use them
81 when computing the ANTIC sets. The AVAIL sets consist of
82 SSA_NAME's that represent values, so we know what values are
83 available in what blocks. AVAIL is a forward dataflow problem. In
84 SSA, values are never killed, so we don't need a kill set, or a
85 fixpoint iteration, in order to calculate the AVAIL sets. In
86 traditional parlance, AVAIL sets tell us the downsafety of the
89 Next, we generate the ANTIC sets. These sets represent the
90 anticipatable expressions. ANTIC is a backwards dataflow
91 problem.An expression is anticipatable in a given block if it could
92 be generated in that block. This means that if we had to perform
93 an insertion in that block, of the value of that expression, we
94 could. Calculating the ANTIC sets requires phi translation of
95 expressions, because the flow goes backwards through phis. We must
96 iterate to a fixpoint of the ANTIC sets, because we have a kill
97 set. Even in SSA form, values are not live over the entire
98 function, only from their definition point onwards. So we have to
99 remove values from the ANTIC set once we go past the definition
100 point of the leaders that make them up.
101 compute_antic/compute_antic_aux performs this computation.
103 Third, we perform insertions to make partially redundant
104 expressions fully redundant.
106 An expression is partially redundant (excluding partial
109 1. It is AVAIL in some, but not all, of the predecessors of a
111 2. It is ANTIC in all the predecessors.
113 In order to make it fully redundant, we insert the expression into
114 the predecessors where it is not available, but is ANTIC.
115 insert/insert_aux performs this insertion.
117 Fourth, we eliminate fully redundant expressions.
118 This is a simple statement walk that replaces redundant
119 calculations with the now available values. */
121 /* Representations of value numbers:
123 Value numbers are represented using the "value handle" approach.
124 This means that each SSA_NAME (and for other reasons to be
125 disclosed in a moment, expression nodes) has a value handle that
126 can be retrieved through get_value_handle. This value handle, *is*
127 the value number of the SSA_NAME. You can pointer compare the
128 value handles for equivalence purposes.
130 For debugging reasons, the value handle is internally more than
131 just a number, it is a VAR_DECL named "value.x", where x is a
132 unique number for each value number in use. This allows
133 expressions with SSA_NAMES replaced by value handles to still be
134 pretty printed in a sane way. They simply print as "value.3 *
137 Expression nodes have value handles associated with them as a
138 cache. Otherwise, we'd have to look them up again in the hash
139 table This makes significant difference (factor of two or more) on
140 some test cases. They can be thrown away after the pass is
143 /* Representation of expressions on value numbers:
145 In some portions of this code, you will notice we allocate "fake"
146 analogues to the expression we are value numbering, and replace the
147 operands with the values of the expression. Since we work on
148 values, and not just names, we canonicalize expressions to value
149 expressions for use in the ANTIC sets, the EXP_GEN set, etc.
151 This is theoretically unnecessary, it just saves a bunch of
152 repeated get_value_handle and find_leader calls in the remainder of
153 the code, trading off temporary memory usage for speed. The tree
154 nodes aren't actually creating more garbage, since they are
155 allocated in a special pools which are thrown away at the end of
158 All of this also means that if you print the EXP_GEN or ANTIC sets,
159 you will see "value.5 + value.7" in the set, instead of "a_55 +
160 b_66" or something. The only thing that actually cares about
161 seeing the value leaders is phi translation, and it needs to be
162 able to find the leader for a value in an arbitrary block, so this
163 "value expression" form is perfect for it (otherwise you'd do
164 get_value_handle->find_leader->translate->get_value_handle->find_leader).*/
167 /* Representation of sets:
169 Sets are represented as doubly linked lists kept in topological
170 order, with an optional supporting bitmap of values present in the
171 set. The sets represent values, and the elements can be values or
172 expressions. The elements can appear in different sets, but each
173 element can only appear once in each set.
175 Since each node in the set represents a value, we also want to be
176 able to map expression, set pairs to something that tells us
177 whether the value is present is a set. We use a per-set bitmap for
178 that. The value handles also point to a linked list of the
179 expressions they represent via a tree annotation. This is mainly
180 useful only for debugging, since we don't do identity lookups. */
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. */
223 /* All of the following sets, except for TMP_GEN, are indexed.
224 TMP_GEN is only ever iterated over, we never check what values
227 typedef struct bb_value_sets
229 /* The EXP_GEN set, which represents expressions/values generated in
233 /* The PHI_GEN set, which represents PHI results generated in a
237 /* The TMP_GEN set, which represents results/temporaries genererated
238 in a basic block. IE the LHS of an expression. */
241 /* The AVAIL_OUT set, which represents which values are available in
242 a given basic block. */
243 value_set_t avail_out
;
245 /* The ANTIC_IN set, which represents which values are anticiptable
246 in a given basic block. */
247 value_set_t antic_in
;
249 /* The NEW_SETS set, which is used during insertion to augment the
250 AVAIL_OUT set of blocks with the new insertions performed during
251 the current iteration. */
252 value_set_t new_sets
;
255 #define EXP_GEN(BB) ((bb_value_sets_t) ((BB)->aux))->exp_gen
256 #define PHI_GEN(BB) ((bb_value_sets_t) ((BB)->aux))->phi_gen
257 #define TMP_GEN(BB) ((bb_value_sets_t) ((BB)->aux))->tmp_gen
258 #define AVAIL_OUT(BB) ((bb_value_sets_t) ((BB)->aux))->avail_out
259 #define ANTIC_IN(BB) ((bb_value_sets_t) ((BB)->aux))->antic_in
260 #define NEW_SETS(BB) ((bb_value_sets_t) ((BB)->aux))->new_sets
262 /* This structure is used to keep track of statistics on what
263 optimization PRE was able to perform. */
266 /* The number of RHS computations eliminated by PRE. */
269 /* The number of new expressions/temporaries generated by PRE. */
272 /* The number of new PHI nodes added by PRE. */
276 static tree
find_leader (value_set_t
, tree
);
277 static void value_insert_into_set (value_set_t
, tree
);
278 static void insert_into_set (value_set_t
, tree
);
279 static value_set_t
set_new (bool);
280 static bool is_undefined_value (tree
);
281 static tree
create_expression_by_pieces (basic_block
, tree
, tree
);
283 /* We can add and remove elements and entries to and from sets
284 and hash tables, so we use alloc pools for them. */
286 static alloc_pool value_set_pool
;
287 static alloc_pool value_set_node_pool
;
288 static alloc_pool binary_node_pool
;
289 static alloc_pool unary_node_pool
;
292 /* The phi_translate_table caches phi translations for a given
293 expression and predecessor. */
295 static htab_t phi_translate_table
;
297 /* A three tuple {e, pred, v} used to cache phi translations in the
298 phi_translate_table. */
300 typedef struct expr_pred_trans_d
302 /* The expression. */
305 /* The predecessor block along which we translated the expression. */
308 /* The value that resulted from the translation. */
311 /* The hashcode for the expression, pred pair. This is cached for
314 } *expr_pred_trans_t
;
316 /* Return the hash value for a phi translation table entry. */
319 expr_pred_trans_hash (const void *p
)
321 const expr_pred_trans_t ve
= (expr_pred_trans_t
) p
;
325 /* Return true if two phi translation table entries are the same.
326 P1 and P2 should point to the expr_pred_trans_t's to be compared.*/
329 expr_pred_trans_eq (const void *p1
, const void *p2
)
331 const expr_pred_trans_t ve1
= (expr_pred_trans_t
) p1
;
332 const expr_pred_trans_t ve2
= (expr_pred_trans_t
) p2
;
333 basic_block b1
= ve1
->pred
;
334 basic_block b2
= ve2
->pred
;
337 /* If they are not translations for the same basic block, they can't
342 /* If they are for the same basic block, determine if the
343 expressions are equal. */
344 if (expressions_equal_p (ve1
->e
, ve2
->e
))
350 /* Search in the phi translation table for the translation of
351 expression E in basic block PRED. Return the translated value, if
352 found, NULL otherwise. */
355 phi_trans_lookup (tree e
, basic_block pred
)
358 struct expr_pred_trans_d ept
;
361 ept
.hashcode
= vn_compute (e
, (unsigned long) pred
, NULL
);
362 slot
= htab_find_slot_with_hash (phi_translate_table
, &ept
, ept
.hashcode
,
367 return ((expr_pred_trans_t
) *slot
)->v
;
371 /* Add the tuple mapping from {expression E, basic block PRED} to
372 value V, to the phi translation table. */
375 phi_trans_add (tree e
, tree v
, basic_block pred
)
378 expr_pred_trans_t new_pair
= xmalloc (sizeof (*new_pair
));
380 new_pair
->pred
= pred
;
382 new_pair
->hashcode
= vn_compute (e
, (unsigned long) pred
, NULL
);
383 slot
= htab_find_slot_with_hash (phi_translate_table
, new_pair
,
384 new_pair
->hashcode
, INSERT
);
387 *slot
= (void *) new_pair
;
391 /* Add expression E to the expression set of value V. */
394 add_to_value (tree v
, tree e
)
396 /* For values representing non-CST nodes, but still function
397 invariant things we mark TREE_CONSTANT as true and set the tree
398 chain to the actual constant. This is because unlike values
399 involving expressions, which are only available to use where the
400 expressions are live, a function invariant can be remade
401 anywhere, and thus, is available everywhere, just like a constant. */
402 if (TREE_CODE_CLASS (TREE_CODE (v
)) == 'c')
404 else if (is_gimple_min_invariant (v
))
406 TREE_CONSTANT (v
) = true;
411 if (VALUE_HANDLE_EXPR_SET (v
) == NULL
)
412 VALUE_HANDLE_EXPR_SET (v
) = set_new (false);
414 insert_into_set (VALUE_HANDLE_EXPR_SET (v
), e
);
418 /* Return true if value V exists in the bitmap for SET. */
421 value_exists_in_set_bitmap (value_set_t set
, tree v
)
426 return bitmap_bit_p (set
->values
, VALUE_HANDLE_ID (v
));
430 /* Remove value V from the bitmap for SET. */
433 value_remove_from_set_bitmap (value_set_t set
, tree v
)
435 #ifdef ENABLE_CHECKING
443 bitmap_clear_bit (set
->values
, VALUE_HANDLE_ID (v
));
447 /* Insert the value number V into the bitmap of values existing in
451 value_insert_into_set_bitmap (value_set_t set
, tree v
)
453 #ifdef ENABLE_CHECKING
458 if (set
->values
== NULL
)
460 set
->values
= BITMAP_GGC_ALLOC ();
461 bitmap_clear (set
->values
);
464 bitmap_set_bit (set
->values
, VALUE_HANDLE_ID (v
));
468 /* Create a new set. */
471 set_new (bool indexed
)
474 ret
= pool_alloc (value_set_pool
);
475 ret
->head
= ret
->tail
= NULL
;
477 ret
->indexed
= indexed
;
483 /* Insert EXPR into SET. */
486 insert_into_set (value_set_t set
, tree expr
)
488 value_set_node_t newnode
= pool_alloc (value_set_node_pool
);
489 tree val
= get_value_handle (expr
);
494 /* For indexed sets, insert the value into the set value bitmap.
495 For all sets, add it to the linked list and increment the list
498 value_insert_into_set_bitmap (set
, val
);
500 newnode
->next
= NULL
;
501 newnode
->expr
= expr
;
503 if (set
->head
== NULL
)
505 set
->head
= set
->tail
= newnode
;
509 set
->tail
->next
= newnode
;
514 /* Copy the set ORIG to the set DEST. */
517 set_copy (value_set_t dest
, value_set_t orig
)
519 value_set_node_t node
;
521 if (!orig
|| !orig
->head
)
524 for (node
= orig
->head
;
528 insert_into_set (dest
, node
->expr
);
532 /* Remove EXPR from SET. */
535 set_remove (value_set_t set
, tree expr
)
537 value_set_node_t node
, prev
;
539 /* Remove the value of EXPR from the bitmap, decrement the set
540 length, and remove it from the actual double linked list. */
541 value_remove_from_set_bitmap (set
, get_value_handle (expr
));
544 for (node
= set
->head
;
546 prev
= node
, node
= node
->next
)
548 if (node
->expr
== expr
)
551 set
->head
= node
->next
;
553 prev
->next
= node
->next
;
555 if (node
== set
->tail
)
557 pool_free (value_set_node_pool
, node
);
563 /* Return true if SET contains the value VAL. */
566 set_contains_value (value_set_t set
, tree val
)
568 /* All true constants are in every set. */
569 if (TREE_CODE_CLASS (TREE_CODE (val
)) == 'c')
571 /* This is only referring to the flag above that we set on
572 values referring to invariants, because we know that we
573 are dealing with one of the value handles we created. */
575 if (TREE_CONSTANT (val
))
578 if (set
->length
== 0)
581 return value_exists_in_set_bitmap (set
, val
);
584 /* Replace the leader for the value LOOKFOR in SET with EXPR. */
587 set_replace_value (value_set_t set
, tree lookfor
, tree expr
)
589 value_set_node_t node
= set
->head
;
591 /* The lookup is probably more expensive than walking the linked
592 list when we have only a small number of nodes. */
593 if (!set_contains_value (set
, lookfor
))
596 for (node
= set
->head
;
600 if (get_value_handle (node
->expr
) == lookfor
)
608 /* Return true if the set contains expression (not value) EXPR. */
611 set_contains (value_set_t set
, tree expr
)
613 value_set_node_t node
;
615 for (node
= set
->head
;
619 if (operand_equal_p (node
->expr
, expr
, 0))
625 /* Subtract set B from set A, and return the new set. */
628 set_subtract (value_set_t a
, value_set_t b
, bool indexed
)
630 value_set_t ret
= set_new (indexed
);
631 value_set_node_t node
;
636 if (!set_contains (b
, node
->expr
))
637 insert_into_set (ret
, node
->expr
);
642 /* Return true if two sets are equal. */
645 set_equal (value_set_t a
, value_set_t b
)
647 value_set_node_t node
;
649 if (a
->length
!= b
->length
)
655 if (!set_contains_value (b
, get_value_handle (node
->expr
)))
661 /* Replace the value for EXPR in SET with EXPR. */
663 value_replace_in_set (value_set_t set
, tree expr
)
665 tree val
= get_value_handle (expr
);
667 if (set
->length
== 0)
670 set_replace_value (set
, val
, expr
);
673 /* Insert the value for EXPR into SET, if it doesn't exist already. */
676 value_insert_into_set (value_set_t set
, tree expr
)
678 tree val
= get_value_handle (expr
);
680 /* Constant and invariant values exist everywhere, and thus,
681 actually keeping them in the sets is pointless. */
682 if (TREE_CONSTANT (val
))
685 if (!set_contains_value (set
, val
))
686 insert_into_set (set
, expr
);
690 /* Print out the value_set SET to OUTFILE. */
693 print_value_set (FILE *outfile
, value_set_t set
,
694 const char *setname
, int blockindex
)
696 value_set_node_t node
;
697 fprintf (outfile
, "%s[%d] := { ", setname
, blockindex
);
700 for (node
= set
->head
;
704 print_generic_expr (outfile
, node
->expr
, 0);
706 fprintf (outfile
, " (");
707 print_generic_expr (outfile
, get_value_handle (node
->expr
), 0);
708 fprintf (outfile
, ") ");
711 fprintf (outfile
, ", ");
715 fprintf (outfile
, " }\n");
718 /* Print out the expressions that have VAL to OUTFILE. */
721 print_value_expressions (FILE *outfile
, tree val
)
723 if (VALUE_HANDLE_EXPR_SET (val
))
726 sprintf (s
, "VH.%04d", VALUE_HANDLE_ID (val
));
727 print_value_set (outfile
, VALUE_HANDLE_EXPR_SET (val
), s
, 0);
733 debug_value_expressions (tree val
)
735 print_value_expressions (stderr
, val
);
739 void debug_value_set (value_set_t
, const char *, int);
742 debug_value_set (value_set_t set
, const char *setname
, int blockindex
)
744 print_value_set (stderr
, set
, setname
, blockindex
);
747 /* Translate EXPR using phis in PHIBLOCK, so that it has the values of
748 the phis in PRED. Return NULL if we can't find a leader for each
749 part of the translated expression. */
752 phi_translate (tree expr
, value_set_t set
, basic_block pred
,
753 basic_block phiblock
)
755 tree phitrans
= NULL
;
761 /* Phi translations of a given expression don't change, */
762 phitrans
= phi_trans_lookup (expr
, pred
);
767 switch (TREE_CODE_CLASS (TREE_CODE (expr
)))
771 tree oldop1
= TREE_OPERAND (expr
, 0);
772 tree oldop2
= TREE_OPERAND (expr
, 1);
777 newop1
= phi_translate (find_leader (set
, oldop1
),
778 set
, pred
, phiblock
);
781 newop2
= phi_translate (find_leader (set
, oldop2
),
782 set
, pred
, phiblock
);
785 if (newop1
!= oldop1
|| newop2
!= oldop2
)
787 newexpr
= pool_alloc (binary_node_pool
);
788 memcpy (newexpr
, expr
, tree_size (expr
));
789 create_tree_ann (newexpr
);
790 TREE_OPERAND (newexpr
, 0) = newop1
== oldop1
? oldop1
: get_value_handle (newop1
);
791 TREE_OPERAND (newexpr
, 1) = newop2
== oldop2
? oldop2
: get_value_handle (newop2
);
792 vn_lookup_or_add (newexpr
, NULL
);
794 phi_trans_add (oldexpr
, newexpr
, pred
);
798 /* XXX: Until we have PRE of loads working, none will be ANTIC.
805 tree oldop1
= TREE_OPERAND (expr
, 0);
809 newop1
= phi_translate (find_leader (set
, oldop1
),
810 set
, pred
, phiblock
);
813 if (newop1
!= oldop1
)
815 newexpr
= pool_alloc (unary_node_pool
);
816 memcpy (newexpr
, expr
, tree_size (expr
));
817 create_tree_ann (newexpr
);
818 TREE_OPERAND (newexpr
, 0) = get_value_handle (newop1
);
819 vn_lookup_or_add (newexpr
, NULL
);
821 phi_trans_add (oldexpr
, newexpr
, pred
);
831 if (TREE_CODE (expr
) != SSA_NAME
)
833 if (TREE_CODE (SSA_NAME_DEF_STMT (expr
)) == PHI_NODE
)
834 phi
= SSA_NAME_DEF_STMT (expr
);
838 for (i
= 0; i
< PHI_NUM_ARGS (phi
); i
++)
839 if (PHI_ARG_EDGE (phi
, i
)->src
== pred
)
842 if (is_undefined_value (PHI_ARG_DEF (phi
, i
)))
844 val
= vn_lookup_or_add (PHI_ARG_DEF (phi
, i
), NULL
);
845 return PHI_ARG_DEF (phi
, i
);
854 phi_translate_set (value_set_t dest
, value_set_t set
, basic_block pred
,
855 basic_block phiblock
)
857 value_set_node_t node
;
858 for (node
= set
->head
;
863 translated
= phi_translate (node
->expr
, set
, pred
, phiblock
);
864 phi_trans_add (node
->expr
, translated
, pred
);
866 if (translated
!= NULL
)
867 value_insert_into_set (dest
, translated
);
871 /* Find the leader for a value (i.e., the name representing that
872 value) in a given set, and return it. Return NULL if no leader is
876 find_leader (value_set_t set
, tree val
)
878 value_set_node_t node
;
883 /* True constants represent themselves. */
884 if (TREE_CODE_CLASS (TREE_CODE (val
)) == 'c')
887 /* Invariants are still represented by values, since they may be
888 more than a single _CST node. */
889 if (TREE_CONSTANT (val
))
890 return TREE_CHAIN (val
);
892 if (set
->length
== 0)
895 if (value_exists_in_set_bitmap (set
, val
))
897 for (node
= set
->head
;
901 if (get_value_handle (node
->expr
) == val
)
909 /* Determine if the expression EXPR is valid in SET. This means that
910 we have a leader for each part of the expression (if it consists of
911 values), or the expression is an SSA_NAME.
913 NB: We never should run into a case where we have SSA_NAME +
914 SSA_NAME or SSA_NAME + value. The sets valid_in_set is called on,
915 the ANTIC sets, will only ever have SSA_NAME's or binary value
916 expression (IE VALUE1 + VALUE2) */
919 valid_in_set (value_set_t set
, tree expr
)
921 switch (TREE_CODE_CLASS (TREE_CODE (expr
)))
925 tree op1
= TREE_OPERAND (expr
, 0);
926 tree op2
= TREE_OPERAND (expr
, 1);
927 return set_contains_value (set
, op1
) && set_contains_value (set
, op2
);
932 tree op1
= TREE_OPERAND (expr
, 0);
933 return set_contains_value (set
, op1
);
936 /* XXX: Until PRE of loads works, no reference nodes are ANTIC.
944 if (TREE_CODE (expr
) == SSA_NAME
)
954 /* Clean the set of expressions that are no longer valid in SET. This
955 means expressions that are made up of values we have no leaders for
959 clean (value_set_t set
)
961 value_set_node_t node
;
962 value_set_node_t next
;
967 if (!valid_in_set (set
, node
->expr
))
968 set_remove (set
, node
->expr
);
973 /* Compute the ANTIC set for BLOCK.
975 ANTIC_OUT[BLOCK] = intersection of ANTIC_IN[b] for all succ(BLOCK), if
977 ANTIC_OUT[BLOCK] = phi_translate (ANTIC_IN[succ(BLOCK)]) if
980 ANTIC_IN[BLOCK] = clean(ANTIC_OUT[BLOCK] U EXP_GEN[BLOCK] -
983 Iterate until fixpointed.
985 XXX: It would be nice to either write a set_clear, and use it for
986 antic_out, or to mark the antic_out set as deleted at the end
987 of this routine, so that the pool can hand the same memory back out
988 again for the next antic_out. */
992 compute_antic_aux (basic_block block
)
996 bool changed
= false;
997 value_set_t S
, old
, ANTIC_OUT
;
998 value_set_node_t node
;
1000 ANTIC_OUT
= S
= NULL
;
1001 /* If any edges from predecessors are abnormal, antic_in is empty, so
1002 punt. Remember that the block has an incoming abnormal edge by
1003 setting the BB_VISITED flag. */
1004 if (! (block
->flags
& BB_VISITED
))
1006 for (e
= block
->pred
; e
; e
= e
->pred_next
)
1007 if (e
->flags
& EDGE_ABNORMAL
)
1009 block
->flags
|= BB_VISITED
;
1013 if (block
->flags
& BB_VISITED
)
1020 old
= set_new (false);
1021 set_copy (old
, ANTIC_IN (block
));
1022 ANTIC_OUT
= set_new (true);
1024 /* If the block has no successors, ANTIC_OUT is empty, because it is
1026 if (block
->succ
== NULL
);
1028 /* If we have one successor, we could have some phi nodes to
1029 translate through. */
1030 else if (block
->succ
->succ_next
== NULL
)
1032 phi_translate_set (ANTIC_OUT
, ANTIC_IN(block
->succ
->dest
),
1033 block
, block
->succ
->dest
);
1035 /* If we have multiple successors, we take the intersection of all of
1039 varray_type worklist
;
1042 basic_block bprime
, first
;
1044 VARRAY_BB_INIT (worklist
, 1, "succ");
1048 VARRAY_PUSH_BB (worklist
, e
->dest
);
1051 first
= VARRAY_BB (worklist
, 0);
1052 set_copy (ANTIC_OUT
, ANTIC_IN (first
));
1054 for (i
= 1; i
< VARRAY_ACTIVE_SIZE (worklist
); i
++)
1056 bprime
= VARRAY_BB (worklist
, i
);
1057 node
= ANTIC_OUT
->head
;
1061 value_set_node_t next
= node
->next
;
1062 val
= get_value_handle (node
->expr
);
1063 if (!set_contains_value (ANTIC_IN (bprime
), val
))
1064 set_remove (ANTIC_OUT
, node
->expr
);
1068 VARRAY_CLEAR (worklist
);
1071 /* Generate ANTIC_OUT - TMP_GEN */
1072 S
= set_subtract (ANTIC_OUT
, TMP_GEN (block
), false);
1074 /* Start ANTIC_IN with EXP_GEN - TMP_GEN */
1075 ANTIC_IN (block
) = set_subtract (EXP_GEN (block
),TMP_GEN (block
), true);
1077 /* Then union in the ANTIC_OUT - TMP_GEN values, to get ANTIC_OUT U
1078 EXP_GEN - TMP_GEN */
1079 for (node
= S
->head
;
1083 value_insert_into_set (ANTIC_IN (block
), node
->expr
);
1085 clean (ANTIC_IN (block
));
1088 if (!set_equal (old
, ANTIC_IN (block
)))
1092 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1095 print_value_set (dump_file
, ANTIC_OUT
, "ANTIC_OUT", block
->index
);
1096 print_value_set (dump_file
, ANTIC_IN (block
), "ANTIC_IN", block
->index
);
1098 print_value_set (dump_file
, S
, "S", block
->index
);
1102 for (son
= first_dom_son (CDI_POST_DOMINATORS
, block
);
1104 son
= next_dom_son (CDI_POST_DOMINATORS
, son
))
1106 changed
|= compute_antic_aux (son
);
1111 /* Compute ANTIC sets. */
1114 compute_antic (void)
1116 bool changed
= true;
1118 int num_iterations
= 0;
1121 ANTIC_IN (bb
) = set_new (true);
1122 if (bb
->flags
& BB_VISITED
)
1130 changed
= compute_antic_aux (EXIT_BLOCK_PTR
);
1134 bb
->flags
&= ~BB_VISITED
;
1136 if (num_iterations
> 2 && dump_file
&& (dump_flags
& TDF_STATS
))
1137 fprintf (dump_file
, "compute_antic required %d iterations\n", num_iterations
);
1141 /* Find a leader for an expression, or generate one using
1142 create_expression_by_pieces if it's ANTIC but
1144 BLOCK is the basic_block we are looking for leaders in.
1145 EXPR is the expression to find a leader or generate for.
1146 STMTS is the statement list to put the inserted expressions on.
1147 Returns the SSA_NAME of the LHS of the generated expression or the
1151 find_or_generate_expression (basic_block block
, tree expr
, tree stmts
)
1154 genop
= find_leader (AVAIL_OUT (block
), expr
);
1155 /* Depending on the order we process DOM branches in, the value
1156 may not have propagated to all the dom children yet during
1157 this iteration. In this case, the value will always be in
1158 the NEW_SETS for us already, having been propagated from our
1161 genop
= find_leader (NEW_SETS (block
), expr
);
1162 /* If it's still NULL, see if it is a complex expression, and if
1163 so, generate it recursively, otherwise, abort, because it's
1167 genop
= VALUE_HANDLE_EXPR_SET (expr
)->head
->expr
;
1168 if (TREE_CODE_CLASS (TREE_CODE (genop
)) != '1'
1169 && TREE_CODE_CLASS (TREE_CODE (genop
)) != '2')
1171 genop
= create_expression_by_pieces (block
, genop
, stmts
);
1177 /* Create an expression in pieces, so that we can handle very complex
1178 expressions that may be ANTIC, but not necessary GIMPLE.
1179 BLOCK is the basic block the expression will be inserted into,
1180 EXPR is the expression to insert (in value form)
1181 STMTS is a statement list to append the necessary insertions into.
1183 This function will abort if we hit some value that shouldn't be
1184 ANTIC but is (IE there is no leader for it, or its components).
1185 This function may also generate expressions that are themselves
1186 partially or fully redundant. Those that are will be either made
1187 fully redundant during the next iteration of insert (for partially
1188 redundant ones), or eliminated by eliminate (for fully redundant
1192 create_expression_by_pieces (basic_block block
, tree expr
, tree stmts
)
1194 tree name
= NULL_TREE
;
1195 tree newexpr
= NULL_TREE
;
1198 switch (TREE_CODE_CLASS (TREE_CODE (expr
)))
1202 tree_stmt_iterator tsi
;
1203 tree genop1
, genop2
;
1205 tree op1
= TREE_OPERAND (expr
, 0);
1206 tree op2
= TREE_OPERAND (expr
, 1);
1207 genop1
= find_or_generate_expression (block
, op1
, stmts
);
1208 genop2
= find_or_generate_expression (block
, op2
, stmts
);
1209 temp
= create_tmp_var (TREE_TYPE (expr
), "pretmp");
1210 add_referenced_tmp_var (temp
);
1211 newexpr
= build (TREE_CODE (expr
), TREE_TYPE (expr
),
1213 newexpr
= build (MODIFY_EXPR
, TREE_TYPE (expr
),
1215 name
= make_ssa_name (temp
, newexpr
);
1216 TREE_OPERAND (newexpr
, 0) = name
;
1217 tsi
= tsi_last (stmts
);
1218 tsi_link_after (&tsi
, newexpr
, TSI_CONTINUE_LINKING
);
1219 pre_stats
.insertions
++;
1224 tree_stmt_iterator tsi
;
1227 tree op1
= TREE_OPERAND (expr
, 0);
1228 genop1
= find_or_generate_expression (block
, op1
, stmts
);
1229 temp
= create_tmp_var (TREE_TYPE (expr
), "pretmp");
1230 add_referenced_tmp_var (temp
);
1231 newexpr
= build (TREE_CODE (expr
), TREE_TYPE (expr
),
1233 newexpr
= build (MODIFY_EXPR
, TREE_TYPE (expr
),
1235 name
= make_ssa_name (temp
, newexpr
);
1236 TREE_OPERAND (newexpr
, 0) = name
;
1237 tsi
= tsi_last (stmts
);
1238 tsi_link_after (&tsi
, newexpr
, TSI_CONTINUE_LINKING
);
1239 pre_stats
.insertions
++;
1247 v
= get_value_handle (expr
);
1248 vn_add (name
, v
, NULL
);
1249 insert_into_set (NEW_SETS (block
), name
);
1250 value_insert_into_set (AVAIL_OUT (block
), name
);
1251 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1253 fprintf (dump_file
, "Inserted ");
1254 print_generic_expr (dump_file
, newexpr
, 0);
1255 fprintf (dump_file
, " in predecessor %d\n", block
->index
);
1260 /* Perform insertion of partially redundant values.
1261 For BLOCK, do the following:
1262 1. Propagate the NEW_SETS of the dominator into the current block.
1263 If the block has multiple predecessors,
1264 2a. Iterate over the ANTIC expressions for the block to see if
1265 any of them are partially redundant.
1266 2b. If so, insert them into the necessary predecessors to make
1267 the expression fully redundant.
1268 2c. Insert a new PHI merging the values of the predecessors.
1269 2d. Insert the new PHI, and the new expressions, into the
1271 3. Recursively call ourselves on the dominator children of BLOCK.
1275 insert_aux (basic_block block
)
1278 bool new_stuff
= false;
1284 dom
= get_immediate_dominator (CDI_DOMINATORS
, block
);
1287 e
= NEW_SETS (dom
)->head
;
1290 insert_into_set (NEW_SETS (block
), e
->expr
);
1291 value_replace_in_set (AVAIL_OUT (block
), e
->expr
);
1294 if (block
->pred
->pred_next
)
1296 value_set_node_t node
;
1297 for (node
= ANTIC_IN (block
)->head
;
1301 if (TREE_CODE_CLASS (TREE_CODE (node
->expr
)) == '2'
1302 || TREE_CODE_CLASS (TREE_CODE (node
->expr
)) == '1')
1306 bool by_some
= false;
1307 bool cant_insert
= false;
1308 bool all_same
= true;
1309 tree first_s
= NULL
;
1314 val
= get_value_handle (node
->expr
);
1315 if (set_contains_value (PHI_GEN (block
), val
))
1317 if (set_contains_value (AVAIL_OUT (dom
), val
))
1319 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1320 fprintf (dump_file
, "Found fully redundant value\n");
1324 avail
= xcalloc (last_basic_block
, sizeof (tree
));
1325 for (pred
= block
->pred
;
1327 pred
= pred
->pred_next
)
1332 eprime
= phi_translate (node
->expr
,
1336 /* eprime will generally only be NULL if the
1337 value of the expression, translated
1338 through the PHI for this predecessor, is
1339 undefined. If that is the case, we can't
1340 make the expression fully redundant,
1341 because its value is undefined along a
1342 predecessor path. We can thus break out
1343 early because it doesn't matter what the
1344 rest of the results are. */
1351 vprime
= get_value_handle (eprime
);
1354 edoubleprime
= find_leader (AVAIL_OUT (bprime
),
1356 if (edoubleprime
== NULL
)
1358 avail
[bprime
->index
] = eprime
;
1363 avail
[bprime
->index
] = edoubleprime
;
1365 if (first_s
== NULL
)
1366 first_s
= edoubleprime
;
1367 else if (first_s
!= edoubleprime
)
1369 if (first_s
!= edoubleprime
1370 && operand_equal_p (first_s
, edoubleprime
, 0))
1374 /* If we can insert it, it's not the same value
1375 already existing along every predecessor, and
1376 it's defined by some predecessor, it is
1377 partially redundant. */
1378 if (!cant_insert
&& !all_same
&& by_some
)
1380 tree type
= TREE_TYPE (avail
[block
->pred
->src
->index
]);
1382 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1384 fprintf (dump_file
, "Found partial redundancy for expression ");
1385 print_generic_expr (dump_file
, node
->expr
, 0);
1386 fprintf (dump_file
, "\n");
1389 /* Make the necessary insertions. */
1390 for (pred
= block
->pred
;
1392 pred
= pred
->pred_next
)
1394 tree stmts
= alloc_stmt_list ();
1397 eprime
= avail
[bprime
->index
];
1398 if (TREE_CODE_CLASS (TREE_CODE (eprime
)) == '2'
1399 || TREE_CODE_CLASS (TREE_CODE (eprime
)) == '1')
1401 builtexpr
= create_expression_by_pieces (bprime
,
1404 bsi_insert_on_edge (pred
, stmts
);
1405 bsi_commit_edge_inserts (NULL
);
1406 avail
[bprime
->index
] = builtexpr
;
1409 /* Now build a phi for the new variable. */
1410 temp
= create_tmp_var (type
, "prephitmp");
1411 add_referenced_tmp_var (temp
);
1412 temp
= create_phi_node (temp
, block
);
1413 vn_add (PHI_RESULT (temp
), val
, NULL
);
1416 if (!set_contains_value (AVAIL_OUT (block
), val
))
1417 insert_into_set (AVAIL_OUT (block
),
1421 value_replace_in_set (AVAIL_OUT (block
),
1423 for (pred
= block
->pred
;
1425 pred
= pred
->pred_next
)
1427 add_phi_arg (&temp
, avail
[pred
->src
->index
],
1430 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1432 fprintf (dump_file
, "Created phi ");
1433 print_generic_expr (dump_file
, temp
, 0);
1434 fprintf (dump_file
, " in block %d\n", block
->index
);
1438 insert_into_set (NEW_SETS (block
),
1440 insert_into_set (PHI_GEN (block
),
1450 for (son
= first_dom_son (CDI_DOMINATORS
, block
);
1452 son
= next_dom_son (CDI_DOMINATORS
, son
))
1454 new_stuff
|= insert_aux (son
);
1460 /* Perform insertion of partially redundant values. */
1465 bool new_stuff
= true;
1467 int num_iterations
= 0;
1470 NEW_SETS (bb
) = set_new (true);
1476 new_stuff
= insert_aux (ENTRY_BLOCK_PTR
);
1478 if (num_iterations
> 2 && dump_file
&& (dump_flags
& TDF_STATS
))
1479 fprintf (dump_file
, "insert required %d iterations\n", num_iterations
);
1483 /* Return true if VAR is an SSA variable with no defining statement in
1484 this procedure, *AND* isn't a live-on-entry parameter. */
1487 is_undefined_value (tree expr
)
1489 return (TREE_CODE (expr
) == SSA_NAME
1490 && IS_EMPTY_STMT (SSA_NAME_DEF_STMT (expr
))
1491 /* PARM_DECLs and hard registers are always defined. */
1492 && TREE_CODE (SSA_NAME_VAR (expr
)) != PARM_DECL
1493 && !DECL_HARD_REGISTER (SSA_NAME_VAR (expr
)));
1497 /* Given an SSA variable VAR and an expression EXPR, compute the value
1498 number for EXPR and create a value handle (VAL) for it. If VAR and
1499 EXPR are not the same, associate VAL with VAR. Finally, add VAR to
1500 S1 and its value handle to S2.
1502 VUSES represent the virtual use operands associated with EXPR (if
1503 any). They are used when computing the hash value for EXPR. */
1506 add_to_sets (tree var
, tree expr
, vuse_optype vuses
, value_set_t s1
,
1509 tree val
= vn_lookup_or_add (expr
, vuses
);
1511 /* VAR and EXPR may be the same when processing statements for which
1512 we are not computing value numbers (e.g., non-assignments, or
1513 statements that make aliased stores). In those cases, we are
1514 only interested in making VAR available as its own value. */
1516 vn_add (var
, val
, vuses
);
1518 insert_into_set (s1
, var
);
1519 value_insert_into_set (s2
, var
);
1523 /* Given a unary or binary expression EXPR, create and return a new
1524 expresion with the same structure as EXPR but with its operands
1525 replaced with the value handles of each of the operands of EXPR.
1526 Insert EXPR's operands into the EXP_GEN set for BLOCK.
1528 VUSES represent the virtual use operands associated with EXPR (if
1529 any). They are used when computing the hash value for EXPR. */
1532 create_value_expr_from (tree expr
, basic_block block
, vuse_optype vuses
)
1535 enum tree_code code
= TREE_CODE (expr
);
1538 #if defined ENABLE_CHECKING
1539 if (TREE_CODE_CLASS (code
) != '1'
1540 && TREE_CODE_CLASS (code
) != '2')
1544 if (TREE_CODE_CLASS (code
) == '1')
1545 vexpr
= pool_alloc (unary_node_pool
);
1547 vexpr
= pool_alloc (binary_node_pool
);
1549 memcpy (vexpr
, expr
, tree_size (expr
));
1551 for (i
= 0; i
< TREE_CODE_LENGTH (code
); i
++)
1553 tree op
= TREE_OPERAND (expr
, i
);
1554 tree val
= vn_lookup_or_add (op
, vuses
);
1555 if (!is_undefined_value (op
))
1556 value_insert_into_set (EXP_GEN (block
), op
);
1557 TREE_OPERAND (vexpr
, i
) = val
;
1564 /* Compute the AVAIL set for BLOCK.
1565 This function performs value numbering of the statements in BLOCK.
1566 The AVAIL sets are built from information we glean while doing this
1567 value numbering, since the AVAIL sets contain only one entry per
1570 AVAIL_IN[BLOCK] = AVAIL_OUT[dom(BLOCK)].
1571 AVAIL_OUT[BLOCK] = AVAIL_IN[BLOCK] U PHI_GEN[BLOCK] U TMP_GEN[BLOCK]. */
1574 compute_avail (basic_block block
)
1578 /* For arguments with default definitions, we pretend they are
1579 defined in the entry block. */
1580 if (block
== ENTRY_BLOCK_PTR
)
1583 for (param
= DECL_ARGUMENTS (current_function_decl
);
1585 param
= TREE_CHAIN (param
))
1587 if (default_def (param
) != NULL
)
1590 tree def
= default_def (param
);
1591 val
= vn_lookup_or_add (def
, NULL
);
1592 insert_into_set (TMP_GEN (block
), def
);
1593 value_insert_into_set (AVAIL_OUT (block
), def
);
1599 block_stmt_iterator bsi
;
1603 /* Initially, the set of available values in BLOCK is that of
1604 its immediate dominator. */
1605 dom
= get_immediate_dominator (CDI_DOMINATORS
, block
);
1607 set_copy (AVAIL_OUT (block
), AVAIL_OUT (dom
));
1609 /* Generate values for PHI nodes. */
1610 for (phi
= phi_nodes (block
); phi
; phi
= PHI_CHAIN (phi
))
1611 add_to_sets (PHI_RESULT (phi
), PHI_RESULT (phi
), NULL
,
1612 PHI_GEN (block
), AVAIL_OUT (block
));
1614 /* Now compute value numbers and populate value sets with all
1615 the expressions computed in BLOCK. */
1616 for (bsi
= bsi_start (block
); !bsi_end_p (bsi
); bsi_next (&bsi
))
1621 stmt
= bsi_stmt (bsi
);
1622 ann
= stmt_ann (stmt
);
1623 get_stmt_operands (stmt
);
1625 /* We are only interested in assignments of the form
1626 X_i = EXPR, where EXPR represents an "interesting"
1627 computation, it has no volatile operands and X_i
1628 doesn't flow through an abnormal edge. */
1629 if (TREE_CODE (stmt
) == MODIFY_EXPR
1630 && !ann
->has_volatile_ops
1631 && TREE_CODE (TREE_OPERAND (stmt
, 0)) == SSA_NAME
1632 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (TREE_OPERAND (stmt
, 0)))
1634 tree lhs
= TREE_OPERAND (stmt
, 0);
1635 tree rhs
= TREE_OPERAND (stmt
, 1);
1636 vuse_optype vuses
= STMT_VUSE_OPS (stmt
);
1638 STRIP_USELESS_TYPE_CONVERSION (rhs
);
1640 if (TREE_CODE_CLASS (TREE_CODE (rhs
)) == '1'
1641 || TREE_CODE_CLASS (TREE_CODE (rhs
)) == '2')
1643 /* For binary and unary expressions, create a duplicate
1644 expression with the operands replaced with the value
1645 handles of the original RHS. */
1646 tree newt
= create_value_expr_from (rhs
, block
, vuses
);
1647 add_to_sets (lhs
, newt
, vuses
, TMP_GEN (block
),
1649 value_insert_into_set (EXP_GEN (block
), newt
);
1652 else if (TREE_CODE (rhs
) == SSA_NAME
1653 || is_gimple_min_invariant (rhs
))
1655 /* Compute a value number for the RHS of the statement
1656 and add its value to the AVAIL_OUT set for the block.
1657 Add the LHS to TMP_GEN. */
1658 add_to_sets (lhs
, rhs
, vuses
, TMP_GEN (block
),
1661 if (TREE_CODE (rhs
) == SSA_NAME
1662 && !is_undefined_value (rhs
))
1663 value_insert_into_set (EXP_GEN (block
), rhs
);
1668 /* For any other statement that we don't recognize, simply
1669 make the names generated by the statement available in
1670 AVAIL_OUT and TMP_GEN. */
1671 for (j
= 0; j
< NUM_DEFS (STMT_DEF_OPS (stmt
)); j
++)
1673 tree def
= DEF_OP (STMT_DEF_OPS (stmt
), j
);
1674 add_to_sets (def
, def
, NULL
, TMP_GEN (block
),
1678 for (j
= 0; j
< NUM_USES (STMT_USE_OPS (stmt
)); j
++)
1680 tree use
= USE_OP (STMT_USE_OPS (stmt
), j
);
1681 add_to_sets (use
, use
, NULL
, TMP_GEN (block
),
1687 /* Compute available sets for the dominator children of BLOCK. */
1688 for (son
= first_dom_son (CDI_DOMINATORS
, block
);
1690 son
= next_dom_son (CDI_DOMINATORS
, son
))
1691 compute_avail (son
);
1695 /* Eliminate fully redundant computations. */
1704 block_stmt_iterator i
;
1706 for (i
= bsi_start (b
); !bsi_end_p (i
); bsi_next (&i
))
1708 tree stmt
= bsi_stmt (i
);
1710 /* Lookup the RHS of the expression, see if we have an
1711 available computation for it. If so, replace the RHS with
1712 the available computation. */
1713 if (TREE_CODE (stmt
) == MODIFY_EXPR
1714 && TREE_CODE (TREE_OPERAND (stmt
, 0)) == SSA_NAME
1715 && TREE_CODE (TREE_OPERAND (stmt
,1)) != SSA_NAME
1716 && !is_gimple_min_invariant (TREE_OPERAND (stmt
, 1))
1717 && !stmt_ann (stmt
)->has_volatile_ops
)
1719 tree lhs
= TREE_OPERAND (stmt
, 0);
1720 tree
*rhs_p
= &TREE_OPERAND (stmt
, 1);
1722 vuse_optype vuses
= STMT_VUSE_OPS (stmt
);
1724 sprime
= find_leader (AVAIL_OUT (b
), vn_lookup (lhs
, vuses
));
1727 && (TREE_CODE (*rhs_p
) != SSA_NAME
1728 || may_propagate_copy (*rhs_p
, sprime
)))
1730 if (sprime
== *rhs_p
)
1733 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1735 fprintf (dump_file
, "Replaced ");
1736 print_generic_expr (dump_file
, *rhs_p
, 0);
1737 fprintf (dump_file
, " with ");
1738 print_generic_expr (dump_file
, sprime
, 0);
1739 fprintf (dump_file
, " in ");
1740 print_generic_stmt (dump_file
, stmt
, 0);
1742 pre_stats
.eliminations
++;
1743 propagate_tree_value (rhs_p
, sprime
);
1752 /* Initialize data structures used by PRE. */
1761 memset (&pre_stats
, 0, sizeof (pre_stats
));
1763 bb
->aux
= xcalloc (1, sizeof (struct bb_value_sets
));
1765 phi_translate_table
= htab_create (511, expr_pred_trans_hash
,
1766 expr_pred_trans_eq
, free
);
1767 value_set_pool
= create_alloc_pool ("Value sets",
1768 sizeof (struct value_set
), 30);
1769 value_set_node_pool
= create_alloc_pool ("Value set nodes",
1770 sizeof (struct value_set_node
), 30);
1771 calculate_dominance_info (CDI_POST_DOMINATORS
);
1772 calculate_dominance_info (CDI_DOMINATORS
);
1773 tsize
= tree_size (build (PLUS_EXPR
, void_type_node
, NULL_TREE
, NULL_TREE
));
1774 binary_node_pool
= create_alloc_pool ("Binary tree nodes", tsize
, 30);
1775 tsize
= tree_size (build1 (NEGATE_EXPR
, void_type_node
, NULL_TREE
));
1776 unary_node_pool
= create_alloc_pool ("Unary tree nodes", tsize
, 30);
1780 EXP_GEN (bb
) = set_new (true);
1781 PHI_GEN (bb
) = set_new (true);
1782 TMP_GEN (bb
) = set_new (false);
1783 AVAIL_OUT (bb
) = set_new (true);
1788 /* Deallocate data structures used by PRE. */
1795 free_alloc_pool (value_set_pool
);
1796 free_alloc_pool (value_set_node_pool
);
1797 free_alloc_pool (binary_node_pool
);
1798 free_alloc_pool (unary_node_pool
);
1799 htab_delete (phi_translate_table
);
1806 free_dominance_info (CDI_POST_DOMINATORS
);
1811 /* Main entry point to the SSA-PRE pass. DO_FRE is true if the caller
1812 only wants to do full redundancy elimination. */
1815 execute_pre (bool do_fre
)
1819 /* Collect and value number expressions computed in each basic
1821 compute_avail (ENTRY_BLOCK_PTR
);
1823 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1829 print_value_set (dump_file
, EXP_GEN (bb
), "exp_gen", bb
->index
);
1830 print_value_set (dump_file
, TMP_GEN (bb
), "tmp_gen", bb
->index
);
1831 print_value_set (dump_file
, AVAIL_OUT (bb
), "avail_out", bb
->index
);
1835 /* Insert can get quite slow on an incredibly large number of basic
1836 blocks due to some quadratic behavior. Until this behavior is
1837 fixed, don't run it when he have an incredibly large number of
1838 bb's. If we aren't going to run insert, there is no point in
1839 computing ANTIC, either, even though it's plenty fast. */
1840 if (!do_fre
&& n_basic_blocks
< 4000)
1846 /* Remove all the redundant expressions. */
1849 if (dump_file
&& (dump_flags
& TDF_STATS
))
1851 fprintf (dump_file
, "Insertions:%d\n", pre_stats
.insertions
);
1852 fprintf (dump_file
, "New PHIs:%d\n", pre_stats
.phis
);
1853 fprintf (dump_file
, "Eliminated:%d\n", pre_stats
.eliminations
);
1860 /* Gate and execute functions for PRE. */
1865 execute_pre (false);
1871 return flag_tree_pre
!= 0;
1874 struct tree_opt_pass pass_pre
=
1877 gate_pre
, /* gate */
1878 do_pre
, /* execute */
1881 0, /* static_pass_number */
1882 TV_TREE_PRE
, /* tv_id */
1883 PROP_no_crit_edges
| PROP_cfg
| PROP_ssa
,/* properties_required */
1884 0, /* properties_provided */
1885 0, /* properties_destroyed */
1886 0, /* todo_flags_start */
1887 TODO_dump_func
| TODO_ggc_collect
| TODO_verify_ssa
/* todo_flags_finish */
1891 /* Gate and execute functions for FRE. */
1902 return flag_tree_fre
!= 0;
1905 struct tree_opt_pass pass_fre
=
1908 gate_fre
, /* gate */
1909 do_fre
, /* execute */
1912 0, /* static_pass_number */
1913 TV_TREE_FRE
, /* tv_id */
1914 PROP_no_crit_edges
| PROP_cfg
| PROP_ssa
,/* properties_required */
1915 0, /* properties_provided */
1916 0, /* properties_destroyed */
1917 0, /* todo_flags_start */
1918 TODO_dump_func
| TODO_ggc_collect
| TODO_verify_ssa
/* todo_flags_finish */