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);
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);
383 slot = htab_find_slot_with_hash (phi_translate_table, new_pair,
384 new_pair->hashcode, INSERT);
387 *slot = (void *) new_pair;
390 /* Add expression E to the expression set of value V. */
393 add_to_value (tree v, tree e)
395 /* For values representing non-CST nodes, but still function
396 invariant things we mark TREE_CONSTANT as true and set the tree
397 chain to the actual constant. This is because unlike values
398 involving expressions, which are only available to use where the
399 expressions are live, a function invariant can be remade
400 anywhere, and thus, is available everywhere, just like a constant. */
401 if (TREE_CODE_CLASS (TREE_CODE (v)) == 'c')
403 else if (is_gimple_min_invariant (v))
405 TREE_CONSTANT (v) = true;
410 if (VALUE_HANDLE_EXPR_SET (v) == NULL)
411 VALUE_HANDLE_EXPR_SET (v) = set_new (false);
413 insert_into_set (VALUE_HANDLE_EXPR_SET (v), e);
417 /* Return true if value V exists in the bitmap for SET. */
420 value_exists_in_set_bitmap (value_set_t set, tree v)
425 return bitmap_bit_p (set->values, VALUE_HANDLE_ID (v));
429 /* Remove value V from the bitmap for SET. */
432 value_remove_from_set_bitmap (value_set_t set, tree v)
434 #ifdef ENABLE_CHECKING
442 bitmap_clear_bit (set->values, VALUE_HANDLE_ID (v));
446 /* Insert the value number V into the bitmap of values existing in
450 value_insert_into_set_bitmap (value_set_t set, tree v)
452 #ifdef ENABLE_CHECKING
457 if (set->values == NULL)
459 set->values = BITMAP_GGC_ALLOC ();
460 bitmap_clear (set->values);
463 bitmap_set_bit (set->values, VALUE_HANDLE_ID (v));
467 /* Create a new set. */
470 set_new (bool indexed)
473 ret = pool_alloc (value_set_pool);
474 ret->head = ret->tail = NULL;
476 ret->indexed = indexed;
482 /* Insert EXPR into SET. */
485 insert_into_set (value_set_t set, tree expr)
487 value_set_node_t newnode = pool_alloc (value_set_node_pool);
488 tree val = get_value_handle (expr);
493 /* For indexed sets, insert the value into the set value bitmap.
494 For all sets, add it to the linked list and increment the list
497 value_insert_into_set_bitmap (set, val);
499 newnode->next = NULL;
500 newnode->expr = expr;
502 if (set->head == NULL)
504 set->head = set->tail = newnode;
508 set->tail->next = newnode;
513 /* Copy the set ORIG to the set DEST. */
516 set_copy (value_set_t dest, value_set_t orig)
518 value_set_node_t node;
520 if (!orig || !orig->head)
523 for (node = orig->head;
527 insert_into_set (dest, node->expr);
531 /* Remove EXPR from SET. */
534 set_remove (value_set_t set, tree expr)
536 value_set_node_t node, prev;
538 /* Remove the value of EXPR from the bitmap, decrement the set
539 length, and remove it from the actual double linked list. */
540 value_remove_from_set_bitmap (set, get_value_handle (expr));
543 for (node = set->head;
545 prev = node, node = node->next)
547 if (node->expr == expr)
550 set->head = node->next;
552 prev->next= node->next;
554 if (node == set->tail)
556 pool_free (value_set_node_pool, node);
562 /* Return true if SET contains the value VAL. */
565 set_contains_value (value_set_t set, tree val)
567 /* All true constants are in every set. */
568 if (TREE_CODE_CLASS (TREE_CODE (val)) == 'c')
570 /* This is only referring to the flag above that we set on
571 values referring to invariants, because we know that we
572 are dealing with one of the value handles we created. */
574 if (TREE_CONSTANT (val))
577 if (set->length == 0)
580 return value_exists_in_set_bitmap (set, val);
583 /* Replace the leader for the value LOOKFOR in SET with EXPR. */
586 set_replace_value (value_set_t set, tree lookfor, tree expr)
588 value_set_node_t node = set->head;
590 /* The lookup is probably more expensive than walking the linked
591 list when we have only a small number of nodes. */
592 if (!set_contains_value (set, lookfor))
595 for (node = set->head;
599 if (get_value_handle (node->expr) == lookfor)
607 /* Return true if the set contains expression (not value) EXPR. */
610 set_contains (value_set_t set, tree expr)
612 value_set_node_t node;
614 for (node = set->head;
618 if (operand_equal_p (node->expr, expr, 0))
624 /* Subtract set B from set A, and return the new set. */
627 set_subtract (value_set_t a, value_set_t b, bool indexed)
629 value_set_t ret = set_new (indexed);
630 value_set_node_t node;
635 if (!set_contains (b, node->expr))
636 insert_into_set (ret, node->expr);
641 /* Return true if two sets are equal. */
644 set_equal (value_set_t a, value_set_t b)
646 value_set_node_t node;
648 if (a->length != b->length)
654 if (!set_contains_value (b, get_value_handle (node->expr)))
660 /* Replace the value for EXPR in SET with EXPR. */
662 value_replace_in_set (value_set_t set, tree expr)
664 tree val = get_value_handle (expr);
666 if (set->length == 0)
669 set_replace_value (set, val, expr);
672 /* Insert the value for EXPR into SET, if it doesn't exist already. */
675 value_insert_into_set (value_set_t set, tree expr)
677 tree val = get_value_handle (expr);
679 /* Constant and invariant values exist everywhere, and thus,
680 actually keeping them in the sets is pointless. */
681 if (TREE_CONSTANT (val))
684 if (!set_contains_value (set, val))
685 insert_into_set (set, expr);
689 /* Print out the value_set SET to OUTFILE. */
692 print_value_set (FILE *outfile, value_set_t set,
693 const char *setname, int blockindex)
695 value_set_node_t node;
696 fprintf (outfile, "%s[%d] := { ", setname, blockindex);
699 for (node = set->head;
703 print_generic_expr (outfile, node->expr, 0);
705 fprintf (outfile, " (");
706 print_generic_expr (outfile, get_value_handle (node->expr), 0);
707 fprintf (outfile, ") ");
710 fprintf (outfile, ", ");
714 fprintf (outfile, " }\n");
717 /* Print out the expressions that have VAL to OUTFILE. */
720 print_value_expressions (FILE *outfile, tree val)
722 if (VALUE_HANDLE_EXPR_SET (val))
725 sprintf (s, "VH.%04d", VALUE_HANDLE_ID (val));
726 print_value_set (outfile, VALUE_HANDLE_EXPR_SET (val), s, 0);
732 debug_value_expressions (tree val)
734 print_value_expressions (stderr, val);
738 void debug_value_set (value_set_t, const char *, int);
741 debug_value_set (value_set_t set, const char *setname, int blockindex)
743 print_value_set (stderr, set, setname, blockindex);
746 /* Translate EXPR using phis in PHIBLOCK, so that it has the values of
747 the phis in PRED. Return NULL if we can't find a leader for each
748 part of the translated expression. */
751 phi_translate (tree expr, value_set_t set, basic_block pred,
752 basic_block phiblock)
754 tree phitrans = NULL;
760 /* Phi translations of a given expression don't change, */
761 phitrans = phi_trans_lookup (expr, pred);
766 switch (TREE_CODE_CLASS (TREE_CODE (expr)))
770 tree oldop1 = TREE_OPERAND (expr, 0);
771 tree oldop2 = TREE_OPERAND (expr, 1);
776 newop1 = phi_translate (find_leader (set, oldop1),
777 set, pred, phiblock);
780 newop2 = phi_translate (find_leader (set, oldop2),
781 set, pred, phiblock);
784 if (newop1 != oldop1 || newop2 != oldop2)
786 newexpr = pool_alloc (binary_node_pool);
787 memcpy (newexpr, expr, tree_size (expr));
788 create_tree_ann (newexpr);
789 TREE_OPERAND (newexpr, 0) = newop1 == oldop1 ? oldop1 : get_value_handle (newop1);
790 TREE_OPERAND (newexpr, 1) = newop2 == oldop2 ? oldop2 : get_value_handle (newop2);
791 vn_lookup_or_add (newexpr);
793 phi_trans_add (oldexpr, newexpr, pred);
797 /* XXX: Until we have PRE of loads working, none will be ANTIC.
804 tree oldop1 = TREE_OPERAND (expr, 0);
808 newop1 = phi_translate (find_leader (set, oldop1),
809 set, pred, phiblock);
812 if (newop1 != oldop1)
814 newexpr = pool_alloc (unary_node_pool);
815 memcpy (newexpr, expr, tree_size (expr));
816 create_tree_ann (newexpr);
817 TREE_OPERAND (newexpr, 0) = get_value_handle (newop1);
818 vn_lookup_or_add (newexpr);
820 phi_trans_add (oldexpr, newexpr, pred);
830 if (TREE_CODE (expr) != SSA_NAME)
832 if (TREE_CODE (SSA_NAME_DEF_STMT (expr)) == PHI_NODE)
833 phi = SSA_NAME_DEF_STMT (expr);
837 for (i = 0; i < PHI_NUM_ARGS (phi); i++)
838 if (PHI_ARG_EDGE (phi, i)->src == pred)
841 if (is_undefined_value (PHI_ARG_DEF (phi, i)))
843 val = vn_lookup_or_add (PHI_ARG_DEF (phi, i));
844 return PHI_ARG_DEF (phi, i);
853 phi_translate_set (value_set_t dest, value_set_t set, basic_block pred,
854 basic_block phiblock)
856 value_set_node_t node;
857 for (node = set->head;
862 translated = phi_translate (node->expr, set, pred, phiblock);
863 phi_trans_add (node->expr, translated, pred);
865 if (translated != NULL)
866 value_insert_into_set (dest, translated);
870 /* Find the leader for a value (IE the name representing that
871 value) in a given set, and return it. Return NULL if no leader is
875 find_leader (value_set_t set, tree val)
877 value_set_node_t node;
881 /* True constants represent themselves. */
882 if (TREE_CODE_CLASS (TREE_CODE (val)) == 'c')
884 /* Invariants are still represented by values, since they may be
885 more than a single _CST node. */
886 if (TREE_CONSTANT (val))
887 return TREE_CHAIN (val);
889 if (set->length == 0)
892 if (value_exists_in_set_bitmap (set, val))
894 for (node = set->head;
898 if (get_value_handle (node->expr) == val)
905 /* Determine if the expression EXPR is valid in SET. This means that
906 we have a leader for each part of the expression (if it consists of
907 values), or the expression is an SSA_NAME.
909 NB: We never should run into a case where we have SSA_NAME +
910 SSA_NAME or SSA_NAME + value. The sets valid_in_set is called on,
911 the ANTIC sets, will only ever have SSA_NAME's or binary value
912 expression (IE VALUE1 + VALUE2) */
915 valid_in_set (value_set_t set, tree expr)
917 switch (TREE_CODE_CLASS (TREE_CODE (expr)))
921 tree op1 = TREE_OPERAND (expr, 0);
922 tree op2 = TREE_OPERAND (expr, 1);
923 return set_contains_value (set, op1) && set_contains_value (set, op2);
928 tree op1 = TREE_OPERAND (expr, 0);
929 return set_contains_value (set, op1);
932 /* XXX: Until PRE of loads works, no reference nodes are ANTIC.
940 if (TREE_CODE (expr) == SSA_NAME)
950 /* Clean the set of expressions that are no longer valid in SET. This
951 means expressions that are made up of values we have no leaders for
955 clean (value_set_t set)
957 value_set_node_t node;
958 value_set_node_t next;
963 if (!valid_in_set (set, node->expr))
964 set_remove (set, node->expr);
969 /* Compute the ANTIC set for BLOCK.
971 ANTIC_OUT[BLOCK] = intersection of ANTIC_IN[b] for all succ(BLOCK), if
973 ANTIC_OUT[BLOCK] = phi_translate (ANTIC_IN[succ(BLOCK)]) if
976 ANTIC_IN[BLOCK] = clean(ANTIC_OUT[BLOCK] U EXP_GEN[BLOCK] -
979 Iterate until fixpointed.
981 XXX: It would be nice to either write a set_clear, and use it for
982 antic_out, or to mark the antic_out set as deleted at the end
983 of this routine, so that the pool can hand the same memory back out
984 again for the next antic_out. */
988 compute_antic_aux (basic_block block)
992 bool changed = false;
993 value_set_t S, old, ANTIC_OUT;
994 value_set_node_t node;
996 ANTIC_OUT = S = NULL;
997 /* If any edges from predecessors are abnormal, antic_in is empty, so
998 punt. Remember that the block has an incoming abnormal edge by
999 setting the BB_VISITED flag. */
1000 if (! (block->flags & BB_VISITED))
1002 for (e = block->pred; e; e = e->pred_next)
1003 if (e->flags & EDGE_ABNORMAL)
1005 block->flags |= BB_VISITED;
1009 if (block->flags & BB_VISITED)
1016 old = set_new (false);
1017 set_copy (old, ANTIC_IN (block));
1018 ANTIC_OUT = set_new (true);
1020 /* If the block has no successors, ANTIC_OUT is empty, because it is
1022 if (block->succ == NULL);
1024 /* If we have one successor, we could have some phi nodes to
1025 translate through. */
1026 else if (block->succ->succ_next == NULL)
1028 phi_translate_set (ANTIC_OUT, ANTIC_IN(block->succ->dest),
1029 block, block->succ->dest);
1031 /* If we have multiple successors, we take the intersection of all of
1035 varray_type worklist;
1038 basic_block bprime, first;
1040 VARRAY_BB_INIT (worklist, 1, "succ");
1044 VARRAY_PUSH_BB (worklist, e->dest);
1047 first = VARRAY_BB (worklist, 0);
1048 set_copy (ANTIC_OUT, ANTIC_IN (first));
1050 for (i = 1; i < VARRAY_ACTIVE_SIZE (worklist); i++)
1052 bprime = VARRAY_BB (worklist, i);
1053 node = ANTIC_OUT->head;
1057 value_set_node_t next = node->next;
1058 val = get_value_handle (node->expr);
1059 if (!set_contains_value (ANTIC_IN (bprime), val))
1060 set_remove (ANTIC_OUT, node->expr);
1064 VARRAY_CLEAR (worklist);
1067 /* Generate ANTIC_OUT - TMP_GEN */
1068 S = set_subtract (ANTIC_OUT, TMP_GEN (block), false);
1070 /* Start ANTIC_IN with EXP_GEN - TMP_GEN */
1071 ANTIC_IN (block) = set_subtract (EXP_GEN (block),TMP_GEN (block), true);
1073 /* Then union in the ANTIC_OUT - TMP_GEN values, to get ANTIC_OUT U
1074 EXP_GEN - TMP_GEN */
1075 for (node = S->head;
1079 value_insert_into_set (ANTIC_IN (block), node->expr);
1081 clean (ANTIC_IN (block));
1084 if (!set_equal (old, ANTIC_IN (block)))
1088 if (dump_file && (dump_flags & TDF_DETAILS))
1091 print_value_set (dump_file, ANTIC_OUT, "ANTIC_OUT", block->index);
1092 print_value_set (dump_file, ANTIC_IN (block), "ANTIC_IN", block->index);
1094 print_value_set (dump_file, S, "S", block->index);
1098 for (son = first_dom_son (CDI_POST_DOMINATORS, block);
1100 son = next_dom_son (CDI_POST_DOMINATORS, son))
1102 changed |= compute_antic_aux (son);
1107 /* Compute ANTIC sets. */
1110 compute_antic (void)
1112 bool changed = true;
1114 int num_iterations = 0;
1117 ANTIC_IN (bb) = set_new (true);
1118 if (bb->flags & BB_VISITED)
1126 changed = compute_antic_aux (EXIT_BLOCK_PTR);
1130 bb->flags &= ~BB_VISITED;
1132 if (num_iterations > 2 && dump_file && (dump_flags & TDF_STATS))
1133 fprintf (dump_file, "compute_antic required %d iterations\n", num_iterations);
1137 /* Find a leader for an expression, or generate one using
1138 create_expression_by_pieces if it's ANTIC but
1140 BLOCK is the basic_block we are looking for leaders in.
1141 EXPR is the expression to find a leader or generate for.
1142 STMTS is the statement list to put the inserted expressions on.
1143 Returns the SSA_NAME of the LHS of the generated expression or the
1147 find_or_generate_expression (basic_block block, tree expr, tree stmts)
1150 genop = find_leader (AVAIL_OUT (block), expr);
1151 /* Depending on the order we process DOM branches in, the value
1152 may not have propagated to all the dom children yet during
1153 this iteration. In this case, the value will always be in
1154 the NEW_SETS for us already, having been propagated from our
1157 genop = find_leader (NEW_SETS (block), expr);
1158 /* If it's still NULL, see if it is a complex expression, and if
1159 so, generate it recursively, otherwise, abort, because it's
1163 genop = VALUE_HANDLE_EXPR_SET (expr)->head->expr;
1164 if (TREE_CODE_CLASS (TREE_CODE (genop)) != '1'
1165 && TREE_CODE_CLASS (TREE_CODE (genop)) != '2')
1167 genop = create_expression_by_pieces (block, genop, stmts);
1173 /* Create an expression in pieces, so that we can handle very complex
1174 expressions that may be ANTIC, but not necessary GIMPLE.
1175 BLOCK is the basic block the expression will be inserted into,
1176 EXPR is the expression to insert (in value form)
1177 STMTS is a statement list to append the necessary insertions into.
1179 This function will abort if we hit some value that shouldn't be
1180 ANTIC but is (IE there is no leader for it, or its components).
1181 This function may also generate expressions that are themselves
1182 partially or fully redundant. Those that are will be either made
1183 fully redundant during the next iteration of insert (for partially
1184 redundant ones), or eliminated by eliminate (for fully redundant
1188 create_expression_by_pieces (basic_block block, tree expr, tree stmts)
1190 tree name = NULL_TREE;
1191 tree newexpr = NULL_TREE;
1194 switch (TREE_CODE_CLASS (TREE_CODE (expr)))
1198 tree_stmt_iterator tsi;
1199 tree genop1, genop2;
1201 tree op1 = TREE_OPERAND (expr, 0);
1202 tree op2 = TREE_OPERAND (expr, 1);
1203 genop1 = find_or_generate_expression (block, op1, stmts);
1204 genop2 = find_or_generate_expression (block, op2, stmts);
1205 temp = create_tmp_var (TREE_TYPE (expr), "pretmp");
1206 add_referenced_tmp_var (temp);
1207 newexpr = build (TREE_CODE (expr), TREE_TYPE (expr),
1209 newexpr = build (MODIFY_EXPR, TREE_TYPE (expr),
1211 name = make_ssa_name (temp, newexpr);
1212 TREE_OPERAND (newexpr, 0) = name;
1213 tsi = tsi_last (stmts);
1214 tsi_link_after (&tsi, newexpr, TSI_CONTINUE_LINKING);
1215 pre_stats.insertions++;
1220 tree_stmt_iterator tsi;
1223 tree op1 = TREE_OPERAND (expr, 0);
1224 genop1 = find_or_generate_expression (block, op1, stmts);
1225 temp = create_tmp_var (TREE_TYPE (expr), "pretmp");
1226 add_referenced_tmp_var (temp);
1227 newexpr = build (TREE_CODE (expr), TREE_TYPE (expr),
1229 newexpr = build (MODIFY_EXPR, TREE_TYPE (expr),
1231 name = make_ssa_name (temp, newexpr);
1232 TREE_OPERAND (newexpr, 0) = name;
1233 tsi = tsi_last (stmts);
1234 tsi_link_after (&tsi, newexpr, TSI_CONTINUE_LINKING);
1235 pre_stats.insertions++;
1243 v = get_value_handle (expr);
1245 insert_into_set (NEW_SETS (block), name);
1246 value_insert_into_set (AVAIL_OUT (block), name);
1247 if (dump_file && (dump_flags & TDF_DETAILS))
1249 fprintf (dump_file, "Inserted ");
1250 print_generic_expr (dump_file, newexpr, 0);
1251 fprintf (dump_file, " in predecessor %d\n", block->index);
1256 /* Perform insertion of partially redundant values.
1257 For BLOCK, do the following:
1258 1. Propagate the NEW_SETS of the dominator into the current block.
1259 If the block has multiple predecessors,
1260 2a. Iterate over the ANTIC expressions for the block to see if
1261 any of them are partially redundant.
1262 2b. If so, insert them into the necessary predecessors to make
1263 the expression fully redundant.
1264 2c. Insert a new PHI merging the values of the predecessors.
1265 2d. Insert the new PHI, and the new expressions, into the
1267 3. Recursively call ourselves on the dominator children of BLOCK.
1271 insert_aux (basic_block block)
1274 bool new_stuff = false;
1280 dom = get_immediate_dominator (CDI_DOMINATORS, block);
1283 e = NEW_SETS (dom)->head;
1286 insert_into_set (NEW_SETS (block), e->expr);
1287 value_replace_in_set (AVAIL_OUT (block), e->expr);
1290 if (block->pred->pred_next)
1292 value_set_node_t node;
1293 for (node = ANTIC_IN (block)->head;
1297 if (TREE_CODE_CLASS (TREE_CODE (node->expr)) == '2'
1298 || TREE_CODE_CLASS (TREE_CODE (node->expr)) == '1')
1302 bool by_some = false;
1303 bool cant_insert = false;
1304 bool all_same = true;
1305 tree first_s = NULL;
1310 val = get_value_handle (node->expr);
1311 if (set_contains_value (PHI_GEN (block), val))
1313 if (set_contains_value (AVAIL_OUT (dom), val))
1315 if (dump_file && (dump_flags & TDF_DETAILS))
1316 fprintf (dump_file, "Found fully redundant value\n");
1320 avail = xcalloc (last_basic_block, sizeof (tree));
1321 for (pred = block->pred;
1323 pred = pred->pred_next)
1328 eprime = phi_translate (node->expr,
1332 /* eprime will generally only be NULL if the
1333 value of the expression, translated
1334 through the PHI for this predecessor, is
1335 undefined. If that is the case, we can't
1336 make the expression fully redundant,
1337 because its value is undefined along a
1338 predecessor path. We can thus break out
1339 early because it doesn't matter what the
1340 rest of the results are. */
1347 vprime = get_value_handle (eprime);
1350 edoubleprime = find_leader (AVAIL_OUT (bprime),
1352 if (edoubleprime == NULL)
1354 avail[bprime->index] = eprime;
1359 avail[bprime->index] = edoubleprime;
1361 if (first_s == NULL)
1362 first_s = edoubleprime;
1363 else if (first_s != edoubleprime)
1365 if (first_s != edoubleprime
1366 && operand_equal_p (first_s, edoubleprime, 0))
1370 /* If we can insert it, it's not the same value
1371 already existing along every predecessor, and
1372 it's defined by some predecessor, it is
1373 partially redundant. */
1374 if (!cant_insert && !all_same && by_some)
1376 tree type = TREE_TYPE (avail[block->pred->src->index]);
1378 if (dump_file && (dump_flags & TDF_DETAILS))
1380 fprintf (dump_file, "Found partial redundancy for expression ");
1381 print_generic_expr (dump_file, node->expr, 0);
1382 fprintf (dump_file, "\n");
1385 /* Make the necessary insertions. */
1386 for (pred = block->pred;
1388 pred = pred->pred_next)
1390 tree stmts = alloc_stmt_list ();
1393 eprime = avail[bprime->index];
1394 if (TREE_CODE_CLASS (TREE_CODE (eprime)) == '2'
1395 || TREE_CODE_CLASS (TREE_CODE (eprime)) == '1')
1397 builtexpr = create_expression_by_pieces (bprime,
1400 bsi_insert_on_edge (pred, stmts);
1401 bsi_commit_edge_inserts (NULL);
1402 avail[bprime->index] = builtexpr;
1405 /* Now build a phi for the new variable. */
1406 temp = create_tmp_var (type, "prephitmp");
1407 add_referenced_tmp_var (temp);
1408 temp = create_phi_node (temp, block);
1409 vn_add (PHI_RESULT (temp), val);
1412 if (!set_contains_value (AVAIL_OUT (block), val))
1413 insert_into_set (AVAIL_OUT (block),
1417 value_replace_in_set (AVAIL_OUT (block),
1419 for (pred = block->pred;
1421 pred = pred->pred_next)
1423 add_phi_arg (&temp, avail[pred->src->index],
1426 if (dump_file && (dump_flags & TDF_DETAILS))
1428 fprintf (dump_file, "Created phi ");
1429 print_generic_expr (dump_file, temp, 0);
1430 fprintf (dump_file, " in block %d\n", block->index);
1434 insert_into_set (NEW_SETS (block),
1436 insert_into_set (PHI_GEN (block),
1446 for (son = first_dom_son (CDI_DOMINATORS, block);
1448 son = next_dom_son (CDI_DOMINATORS, son))
1450 new_stuff |= insert_aux (son);
1456 /* Perform insertion of partially redundant values. */
1461 bool new_stuff = true;
1463 int num_iterations = 0;
1466 NEW_SETS (bb) = set_new (true);
1472 new_stuff = insert_aux (ENTRY_BLOCK_PTR);
1474 if (num_iterations > 2 && dump_file && (dump_flags & TDF_STATS))
1475 fprintf (dump_file, "insert required %d iterations\n", num_iterations);
1479 /* Return true if EXPR has no defining statement in this procedure,
1480 *AND* isn't a live-on-entry parameter. */
1483 is_undefined_value (tree expr)
1485 #ifdef ENABLE_CHECKING
1486 /* We should never be handed DECL's */
1491 if (TREE_CODE (expr) == SSA_NAME)
1493 /* XXX: Is this the correct test? */
1494 if (TREE_CODE (SSA_NAME_VAR (expr)) == PARM_DECL)
1496 if (IS_EMPTY_STMT (SSA_NAME_DEF_STMT (expr)))
1503 /* Compute the AVAIL set for BLOCK.
1504 This function performs value numbering of the statements in BLOCK.
1505 The AVAIL sets are built from information we glean while doing this
1506 value numbering, since the AVAIL sets contain only entry per
1510 AVAIL_IN[BLOCK] = AVAIL_OUT[dom(BLOCK)].
1511 AVAIL_OUT[BLOCK] = AVAIL_IN[BLOCK] U PHI_GEN[BLOCK] U
1516 compute_avail (basic_block block)
1520 /* For arguments with default definitions, we pretend they are
1521 defined in the entry block. */
1522 if (block == ENTRY_BLOCK_PTR)
1525 for (param = DECL_ARGUMENTS (current_function_decl);
1527 param = TREE_CHAIN (param))
1529 if (default_def (param) != NULL)
1532 tree def = default_def (param);
1533 val = vn_lookup_or_add (def);
1534 insert_into_set (TMP_GEN (block), def);
1535 value_insert_into_set (AVAIL_OUT (block), def);
1541 block_stmt_iterator bsi;
1545 dom = get_immediate_dominator (CDI_DOMINATORS, block);
1547 set_copy (AVAIL_OUT (block), AVAIL_OUT (dom));
1549 for (phi = phi_nodes (block); phi; phi = PHI_CHAIN (phi))
1551 /* Ignore virtual PHIs until we can do PRE on expressions
1552 with virtual operands. */
1553 if (!is_gimple_reg (SSA_NAME_VAR (PHI_RESULT (phi))))
1556 vn_lookup_or_add (PHI_RESULT (phi));
1557 value_insert_into_set (AVAIL_OUT (block), PHI_RESULT (phi));
1558 insert_into_set (PHI_GEN (block), PHI_RESULT (phi));
1561 for (bsi = bsi_start (block); !bsi_end_p (bsi); bsi_next (&bsi))
1564 stmt = bsi_stmt (bsi);
1565 get_stmt_operands (stmt);
1567 if (NUM_VUSES (STMT_VUSE_OPS (stmt))
1568 || NUM_V_MUST_DEFS (STMT_V_MUST_DEF_OPS (stmt))
1569 || NUM_V_MAY_DEFS (STMT_V_MAY_DEF_OPS (stmt))
1570 || stmt_ann (stmt)->has_volatile_ops)
1573 for (j = 0; j < NUM_DEFS (STMT_DEF_OPS (stmt)); j++)
1575 tree def = DEF_OP (STMT_DEF_OPS (stmt), j);
1576 vn_lookup_or_add (def);
1577 insert_into_set (TMP_GEN (block), def);
1578 value_insert_into_set (AVAIL_OUT (block), def);
1580 for (j = 0; j < NUM_USES (STMT_USE_OPS (stmt)); j++)
1582 tree use = USE_OP (STMT_USE_OPS (stmt), j);
1583 if (TREE_CODE (use) == SSA_NAME)
1585 vn_lookup_or_add (use);
1586 insert_into_set (TMP_GEN (block), use);
1587 value_insert_into_set (AVAIL_OUT (block), use);
1593 if (TREE_CODE (stmt) == MODIFY_EXPR)
1595 op0 = TREE_OPERAND (stmt, 0);
1596 if (TREE_CODE (op0) != SSA_NAME)
1598 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op0))
1600 op1 = TREE_OPERAND (stmt, 1);
1601 STRIP_USELESS_TYPE_CONVERSION (op1);
1602 if (is_gimple_min_invariant (op1))
1604 vn_add (op0, vn_lookup_or_add (op1));
1605 insert_into_set (TMP_GEN (block), op0);
1606 value_insert_into_set (AVAIL_OUT (block), op0);
1608 else if (TREE_CODE_CLASS (TREE_CODE (op1)) == '2')
1611 tree val, val1, val2;
1613 bop1 = TREE_OPERAND (op1, 0);
1614 bop2 = TREE_OPERAND (op1, 1);
1615 val1 = vn_lookup_or_add (bop1);
1616 val2 = vn_lookup_or_add (bop2);
1618 newt = pool_alloc (binary_node_pool);
1619 memcpy (newt, op1, tree_size (op1));
1620 TREE_OPERAND (newt, 0) = val1;
1621 TREE_OPERAND (newt, 1) = val2;
1622 val = vn_lookup_or_add (newt);
1624 if (!is_undefined_value (bop1))
1625 value_insert_into_set (EXP_GEN (block), bop1);
1626 if (!is_undefined_value (bop2))
1627 value_insert_into_set (EXP_GEN (block), bop2);
1628 value_insert_into_set (EXP_GEN (block), newt);
1629 insert_into_set (TMP_GEN (block), op0);
1630 value_insert_into_set (AVAIL_OUT (block), op0);
1632 else if (TREE_CODE_CLASS (TREE_CODE (op1)) == '1'
1633 && !is_gimple_cast (op1))
1638 uop = TREE_OPERAND (op1, 0);
1639 val1 = vn_lookup_or_add (uop);
1640 newt = pool_alloc (unary_node_pool);
1641 memcpy (newt, op1, tree_size (op1));
1642 TREE_OPERAND (newt, 0) = val1;
1643 val = vn_lookup_or_add (newt);
1645 if (!is_undefined_value (uop))
1646 value_insert_into_set (EXP_GEN (block), uop);
1647 value_insert_into_set (EXP_GEN (block), newt);
1648 insert_into_set (TMP_GEN (block), op0);
1649 value_insert_into_set (AVAIL_OUT (block), op0);
1651 else if (TREE_CODE (op1) == SSA_NAME)
1653 tree val = vn_lookup_or_add (op1);
1655 if (!is_undefined_value (op1))
1656 value_insert_into_set (EXP_GEN (block), op1);
1657 insert_into_set (TMP_GEN (block), op0);
1658 value_insert_into_set (AVAIL_OUT (block), op0);
1663 for (j = 0; j < NUM_DEFS (STMT_DEF_OPS (stmt)); j++)
1665 tree def = DEF_OP (STMT_DEF_OPS (stmt), j);
1666 vn_lookup_or_add (def);
1667 insert_into_set (TMP_GEN (block), def);
1668 value_insert_into_set (AVAIL_OUT (block), def);
1672 for (j = 0; j < NUM_USES (STMT_USE_OPS (stmt)); j++)
1674 tree use = USE_OP (STMT_USE_OPS (stmt), j);
1675 if (TREE_CODE (use) == SSA_NAME)
1677 vn_lookup_or_add (use);
1678 insert_into_set (TMP_GEN (block), use);
1679 value_insert_into_set (AVAIL_OUT (block), use);
1687 for (j = 0; j < NUM_DEFS (STMT_DEF_OPS (stmt)); j++)
1689 tree def = DEF_OP (STMT_DEF_OPS (stmt), j);
1690 vn_lookup_or_add (def);
1691 insert_into_set (TMP_GEN (block), def);
1692 value_insert_into_set (AVAIL_OUT (block), def);
1694 for (j = 0; j < NUM_USES (STMT_USE_OPS (stmt)); j++)
1696 tree use = USE_OP (STMT_USE_OPS (stmt), j);
1697 if (TREE_CODE (use) == SSA_NAME)
1699 vn_lookup_or_add (use);
1700 insert_into_set (TMP_GEN (block), use);
1701 value_insert_into_set (AVAIL_OUT (block), use);
1708 for (son = first_dom_son (CDI_DOMINATORS, block);
1710 son = next_dom_son (CDI_DOMINATORS, son))
1711 compute_avail (son);
1715 /* Eliminate fully redundant computations. */
1724 block_stmt_iterator i;
1726 for (i = bsi_start (b); !bsi_end_p (i); bsi_next (&i))
1728 tree stmt = bsi_stmt (i);
1730 if (NUM_VUSES (STMT_VUSE_OPS (stmt))
1731 || NUM_V_MUST_DEFS (STMT_V_MUST_DEF_OPS (stmt))
1732 || NUM_V_MAY_DEFS (STMT_V_MAY_DEF_OPS (stmt))
1733 || stmt_ann (stmt)->has_volatile_ops)
1736 /* Lookup the RHS of the expression, see if we have an
1737 available computation for it. If so, replace the RHS with
1738 the available computation. */
1739 if (TREE_CODE (stmt) == MODIFY_EXPR)
1741 tree t = TREE_OPERAND (stmt, 0);
1742 tree expr = TREE_OPERAND (stmt, 1);
1744 /* There is no point in eliminating NOP_EXPR, it isn't
1745 supposed to generate any code. */
1746 if (TREE_CODE (expr) == NOP_EXPR
1747 || (TREE_CODE_CLASS (TREE_CODE (expr)) != '2'
1748 && TREE_CODE_CLASS (TREE_CODE (expr)) != '1'))
1751 sprime = find_leader (AVAIL_OUT (b), vn_lookup (t));
1754 && may_propagate_copy (sprime, TREE_OPERAND (stmt, 1)))
1756 if (dump_file && (dump_flags & TDF_DETAILS))
1758 fprintf (dump_file, "Replaced ");
1759 print_generic_expr (dump_file, expr, 0);
1760 fprintf (dump_file, " with ");
1761 print_generic_expr (dump_file, sprime, 0);
1762 fprintf (dump_file, " in ");
1763 print_generic_stmt (dump_file, stmt, 0);
1765 pre_stats.eliminations++;
1766 propagate_tree_value (&TREE_OPERAND (stmt, 1), sprime);
1775 /* Main entry point to the SSA-PRE pass.
1777 PHASE indicates which dump file from the DUMP_FILES array to use when
1778 dumping debugging information. */
1785 memset (&pre_stats, 0, sizeof (pre_stats));
1788 bb->aux = xcalloc (1, sizeof (struct bb_value_sets));
1790 phi_translate_table = htab_create (511, expr_pred_trans_hash,
1793 value_set_pool = create_alloc_pool ("Value sets",
1794 sizeof (struct value_set), 30);
1795 value_set_node_pool = create_alloc_pool ("Value set nodes",
1796 sizeof (struct value_set_node), 30);
1797 calculate_dominance_info (CDI_POST_DOMINATORS);
1798 calculate_dominance_info (CDI_DOMINATORS);
1799 tsize = tree_size (build (PLUS_EXPR, void_type_node, NULL_TREE,
1801 binary_node_pool = create_alloc_pool ("Binary tree nodes", tsize, 30);
1802 tsize = tree_size (build1 (NEGATE_EXPR, void_type_node, NULL_TREE));
1803 unary_node_pool = create_alloc_pool ("Unary tree nodes", tsize, 30);
1807 EXP_GEN (bb) = set_new (true);
1808 PHI_GEN (bb) = set_new (true);
1809 TMP_GEN (bb) = set_new (false);
1810 AVAIL_OUT (bb) = set_new (true);
1813 compute_avail (ENTRY_BLOCK_PTR);
1815 if (dump_file && (dump_flags & TDF_DETAILS))
1819 print_value_set (dump_file, EXP_GEN (bb), "exp_gen", bb->index);
1820 print_value_set (dump_file, TMP_GEN (bb), "tmp_gen", bb->index);
1821 print_value_set (dump_file, AVAIL_OUT (bb), "avail_out", bb->index);
1825 /* Insert can get quite slow on an incredibly large number of basic
1826 blocks due to some quadratic behavior. Until this behavior is
1827 fixed, don't run it when he have an incredibly large number of
1828 bb's. If we aren't going to run insert, there is no point in
1829 computing ANTIC, either, even though it's plenty fast. */
1831 if (n_basic_blocks < 4000)
1839 if (dump_file && (dump_flags & TDF_STATS))
1841 fprintf (dump_file, "Insertions:%d\n", pre_stats.insertions);
1842 fprintf (dump_file, "New PHIs:%d\n", pre_stats.phis);
1843 fprintf (dump_file, "Eliminated:%d\n", pre_stats.eliminations);
1846 free_alloc_pool (value_set_pool);
1847 free_alloc_pool (value_set_node_pool);
1848 free_alloc_pool (binary_node_pool);
1849 free_alloc_pool (unary_node_pool);
1850 htab_delete (phi_translate_table);
1857 free_dominance_info (CDI_POST_DOMINATORS);
1863 return flag_tree_pre != 0;
1866 struct tree_opt_pass pass_pre =
1869 gate_pre, /* gate */
1870 execute_pre, /* execute */
1873 0, /* static_pass_number */
1874 TV_TREE_PRE, /* tv_id */
1875 PROP_no_crit_edges | PROP_cfg | PROP_ssa,/* properties_required */
1876 0, /* properties_provided */
1877 0, /* properties_destroyed */
1878 0, /* todo_flags_start */
1879 TODO_dump_func | TODO_ggc_collect | TODO_verify_ssa /* todo_flags_finish */