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. */
24 #include "coretypes.h"
30 /* These RTL headers are needed for basic-block.h. */
33 #include "hard-reg-set.h"
34 #include "basic-block.h"
35 #include "diagnostic.h"
36 #include "tree-inline.h"
37 #include "tree-flow.h"
38 #include "tree-gimple.h"
39 #include "tree-dump.h"
43 #include "tree-iterator.h"
45 #include "alloc-pool.h"
46 #include "tree-pass.h"
48 #include "splay-tree.h"
50 #include "langhooks.h"
53 1. Implement load value numbering.
54 2. Speed up insert_aux so that we can use it all the time. It
55 spends most of it's time in quadratic value replacement.
56 3. Avail sets can be shared by making an avail_find_leader that
57 walks up the dominator tree and looks in those avail sets.
58 This might affect code optimality, it's unclear right now.
59 4. Load motion can be performed by value numbering the loads the
60 same as we do other expressions. This requires iterative
61 hashing the vuses into the values. Right now we simply assign
62 a new value every time we see a statement with a vuse.
63 5. Strength reduction can be performed by anticipating expressions
64 we can repair later on.
67 /* For ease of terminology, "expression node" in the below refers to
68 every expression node but MODIFY_EXPR, because MODIFY_EXPR's represent
69 the actual statement containing the expressions we care about, and
70 we cache the value number by putting it in the expression. */
74 First we walk the statements to generate the AVAIL sets, the EXP_GEN
75 sets, and the tmp_gen sets. AVAIL is a forward dataflow
76 problem. EXP_GEN sets represent the generation of
77 values/expressions by a given block. We use them when computing
78 the ANTIC sets. The AVAIL sets consist of SSA_NAME's that
79 represent values, so we know what values are available in what
80 blocks. In SSA, values are never killed, so we don't need a kill
81 set, or a fixpoint iteration, in order to calculate the AVAIL sets.
82 In traditional parlance, AVAIL sets tell us the downsafety of the
85 Next, we generate the ANTIC sets. ANTIC is a backwards dataflow
86 problem. These sets represent the anticipatable expressions. An
87 expression is anticipatable in a given block if it could be
88 generated in that block. This means that if we had to perform an
89 insertion in that block, of the value of that expression, we could.
90 Calculating the ANTIC sets requires phi translation of expressions,
91 because the flow goes backwards through phis. We must iterate to a
92 fixpoint of the ANTIC sets, because we have a kill set.
93 Even in SSA form, values are not live over the entire function,
94 only from their definition point onwards. So we have to remove
95 values from the ANTIC set once we go past the definition point of
96 the leaders that make them up. compute_antic/compute_antic_aux
97 performs this computation.
99 Third, we perform insertions to make partially redundant
100 expressions fully redundant.
102 An expression is partially redundant (excluding partial
105 1. It is AVAIL in some, but not all, of the predecessors of a
107 2. It is ANTIC in all the predecessors.
109 In order to make it fully redundant, we insert the expression into
110 the predecessors where it is not available, but is ANTIC.
111 insert/insert_aux performs this insertion.
113 Fourth, we eliminate fully redundant expressions.
114 This is a simple statement walk that replaces redundant
115 calculations with the now available values. */
117 /* Representations of value numbers:
119 Value numbers are represented using the "value handle" approach.
120 This means that each SSA_NAME (and for other reasons to be
121 disclosed in a moment, expression nodes and constant nodes) has a
122 value handle that can be retrieved through get_value_handle. This
123 value handle, *is* the value number of the SSA_NAME. You can
124 pointer compare the value handles for equivalence purposes.
126 For debugging reasons, the value handle is internally more than
127 just a number, it is a VAR_DECL named "value.x", where x is a
128 unique number for each value number in use. This allows
129 expressions with SSA_NAMES replaced by value handles to still be
130 pretty printed in a sane way. They simply print as "value.3 *
133 Expression nodes have value handles associated with them as a
134 cache. Otherwise, we'd have to look them up again in the hash
135 table This makes significant difference (factor of two or more) on
136 some test cases. They can be thrown away after the Constants have
137 value handles associated with them so that they aren't special
138 cased everywhere, and for consistency sake. This may be changed
139 depending on memory usage vs code maintenance tradeoff. */
141 /* Representation of expressions on value numbers:
143 In some portions of this code, you will notice we allocate "fake"
144 analogues to the expression we are value numbering, and replace the
145 operands with the values of the expression. Since we work on
146 values, and not just names, we canonicalize expressions to value
147 expressions for use in the ANTIC sets, the EXP_GEN set, etc.
149 This is theoretically unnecessary, it just saves a bunch of
150 repeated get_value_handle and find_leader calls in the remainder of
151 the code, trading off temporary memory usage for speed. The tree
152 nodes aren't actually creating more garbage, since they are
153 allocated in a special pools which are thrown away at the end of
156 All of this also means that if you print the EXP_GEN or ANTIC sets,
157 you will see "value.5 + value.7" in the set, instead of "a_55 +
158 b_66" or something. The only thing that actually cares about
159 seeing the value leaders is phi translation, and it needs to be
160 able to find the leader for a value in an arbitrary block, so this
161 "value expression" form is perfect for it (otherwise you'd do
162 get_value_handle->find_leader->translate->get_value_handle->find_leader).*/
165 /* Representation of sets:
167 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 constants,
170 values, or expressions. The elements can appear in different sets,
171 but each element can only appear once in each set.
173 Since each node in the set represents a value, we also want to be
174 able to map expression, set pairs to something that tells us
175 whether the value is present is a set. We use a per-set bitmap for
176 that. The value handles also point to a linked list of the
177 expressions they represent via a tree annotation. This is mainly
178 useful only for debugging, since we don't do identity lookups. */
181 /* A value set element. Basically a single linked list of
182 expressions/constants/values. */
183 typedef struct value_set_node
186 struct value_set_node *next;
190 /* A value set, which is the head of the linked list, and we also keep
191 the tail because we have to append for the topolofical sort. */
192 typedef struct value_set
194 value_set_node_t head;
195 value_set_node_t tail;
202 /* All of the following sets, except for TMP_GEN, are indexed.
203 TMP_GEN is only ever iterated over, we never check what values
205 typedef struct bb_value_sets
210 value_set_t avail_out;
211 value_set_t antic_in;
212 value_set_t new_sets;
215 #define EXP_GEN(BB) ((bb_value_sets_t) ((BB)->aux))->exp_gen
216 #define PHI_GEN(BB) ((bb_value_sets_t) ((BB)->aux))->phi_gen
217 #define TMP_GEN(BB) ((bb_value_sets_t) ((BB)->aux))->tmp_gen
218 #define AVAIL_OUT(BB) ((bb_value_sets_t) ((BB)->aux))->avail_out
219 #define ANTIC_IN(BB) ((bb_value_sets_t) ((BB)->aux))->antic_in
220 #define NEW_SETS(BB) ((bb_value_sets_t) ((BB)->aux))->new_sets
229 static tree find_leader (value_set_t, tree);
230 static void value_insert_into_set (value_set_t, tree);
231 static void insert_into_set (value_set_t, tree);
232 static void add_to_value (tree, tree);
233 static value_set_t set_new (bool);
234 static bool is_undefined_value (tree);
236 /* We can add and remove elements and entries to and from sets
237 and hash tables, so we use alloc pools for them. */
239 static alloc_pool value_set_pool;
240 static alloc_pool value_set_node_pool;
241 static alloc_pool binary_node_pool;
242 static alloc_pool unary_node_pool;
244 /* The value table that maps expressions to values. */
245 static htab_t value_table;
247 /* The phi_translate_table caches phi translations for a given
248 expression and predecessor. */
249 static htab_t phi_translate_table;
252 /* Map expressions to values. These are simple pairs of expressions
253 and the values they represent. To find the value represented by
254 an expression, we use a hash table where the elements are {e,v}
255 pairs, and the expression is the key. */
257 typedef struct val_expr_pair_d
264 /* Hash a {v,e} pair. We really only hash the expression. */
267 val_expr_pair_hash (const void *p)
269 const val_expr_pair_t ve = (val_expr_pair_t) p;
274 /* Are {e2,v2} and {e1,v1} the same? Again, only the expression
278 val_expr_pair_expr_eq (const void *p1, const void *p2)
280 const val_expr_pair_t ve1 = (val_expr_pair_t) p1;
281 const val_expr_pair_t ve2 = (val_expr_pair_t) p2;
289 te1 = TREE_TYPE (e1);
290 te2 = TREE_TYPE (e2);
291 if (TREE_CODE (e1) == TREE_CODE (e2)
292 && (te1 == te2 || lang_hooks.types_compatible_p (te1, te2))
293 && operand_equal_p (e1, e2, 0))
300 /* Get the value handle of EXPR. This is the only correct way to get
301 the value handle for a "thing". */
304 get_value_handle (tree expr)
306 /* We should never see these. */
309 else if (TREE_CODE (expr) == SSA_NAME)
311 return SSA_NAME_VALUE (expr);
313 else if (TREE_CODE_CLASS (TREE_CODE (expr)) == 'c')
315 cst_ann_t ann = cst_ann (expr);
317 return ann->common.value_handle;
320 else if (EXPR_P (expr))
322 expr_ann_t ann = expr_ann (expr);
324 return ann->common.value_handle;
331 /* Set the value handle for E to V */
334 set_value_handle (tree e, tree v)
338 else if (TREE_CODE (e) == SSA_NAME)
339 SSA_NAME_VALUE (e) = v;
340 else if (TREE_CODE_CLASS (TREE_CODE (e)) == 'c')
341 get_cst_ann (e)->common.value_handle = v;
343 get_expr_ann (e)->common.value_handle = v;
346 /* A three tuple {e, pred, v} used to cache phi translations in the
347 phi_translate_table. */
349 typedef struct expr_pred_trans_d
355 } *expr_pred_trans_t;
357 /* Return the hash value for a phi translation table entry. */
360 expr_pred_trans_hash (const void *p)
362 const expr_pred_trans_t ve = (expr_pred_trans_t) p;
366 /* Return true if two phi translation table entries are the same. */
369 expr_pred_trans_eq (const void *p1, const void *p2)
371 const expr_pred_trans_t ve1 = (expr_pred_trans_t) p1;
372 const expr_pred_trans_t ve2 = (expr_pred_trans_t) p2;
375 basic_block b1 = ve1->pred;
376 basic_block b2 = ve2->pred;
386 te1 = TREE_TYPE (e1);
387 te2 = TREE_TYPE (e2);
389 if (TREE_CODE (e1) == TREE_CODE (e2)
390 && (te1 == te2 || lang_hooks.types_compatible_p (te1, te2))
391 && operand_equal_p (e1, e2, 0))
397 /* Search in the phi translation table for the translation of E in
398 PRED. Return the translated value, if found, NULL otherwise. */
401 phi_trans_lookup (tree e, basic_block pred)
404 struct expr_pred_trans_d ugly;
407 ugly.hashcode = iterative_hash_expr (e, (unsigned long) pred);
408 slot = htab_find_slot_with_hash (phi_translate_table, &ugly, ugly.hashcode,
413 return ((expr_pred_trans_t) *slot)->v;
417 /* Add the tuple mapping {e, pred}->v to the phi translation table. */
420 phi_trans_add (tree e, tree v, basic_block pred)
423 expr_pred_trans_t new_pair = xmalloc (sizeof (*new_pair));
425 new_pair->pred = pred;
427 new_pair->hashcode = iterative_hash_expr (e, (unsigned long) pred);
428 slot = htab_find_slot_with_hash (phi_translate_table, new_pair,
429 new_pair->hashcode, INSERT);
432 *slot = (void *) new_pair;
435 /* Search in TABLE for an existing instance of expression E,
436 and return its value, or NULL if none has been set. */
439 lookup (htab_t table, tree e)
442 struct val_expr_pair_d ugly = {NULL, NULL, 0};
444 ugly.hashcode = iterative_hash_expr (e,0);
445 slot = htab_find_slot_with_hash (table, &ugly, ugly.hashcode, NO_INSERT);
449 return ((val_expr_pair_t) *slot)->v;
452 /* Add E to the expression set of V. */
455 add_to_value (tree v, tree e)
457 #if DEBUG_VALUE_EXPRESSIONS
458 var_ann_t va = var_ann (v);
460 /* For values representing numerical constants, we mark
461 TREE_CONSTANT as true and set the tree chain to the actual
462 constant. This is because unlike values involving expressions,
463 which are only available to use where the expressions are live, a
464 constant can be remade anywhere, and thus, is available
466 if (TREE_CODE_CLASS (TREE_CODE (e)) == 'c')
468 TREE_CONSTANT (v) = true;
471 else if (is_gimple_min_invariant (e))
473 TREE_CONSTANT (v) = true;
476 #if DEBUG_VALUE_EXPRESSIONS
477 if (va->expr_set == NULL)
478 va->expr_set = set_new (false);
479 insert_into_set (va->expr_set, e);
483 /* Insert E into TABLE with value V, and add E to the value set for V. */
486 add (htab_t table, tree e, tree v)
490 val_expr_pair_t new_pair = xmalloc (sizeof (struct val_expr_pair_d));
493 new_pair->hashcode = iterative_hash_expr (e, 0);
494 slot = htab_find_slot_with_hash (table, new_pair, new_pair->hashcode,
498 *slot = (void *) new_pair;
499 set_value_handle (e, v);
507 /* Create a new value handle for EXPR. */
509 create_new_value (tree expr)
511 tree a = create_tmp_var_raw (TREE_TYPE (expr), "value");
513 var_ann (a)->uid = pre_uid++;
515 if (dump_file && (dump_flags & TDF_DETAILS))
517 fprintf (dump_file, "Created value ");
518 print_generic_expr (dump_file, a, dump_flags);
519 fprintf (dump_file, " for ");
520 print_generic_expr (dump_file, expr, dump_flags);
521 fprintf (dump_file, "\n");
526 /* Like lookup, but adds V as the value for E if E does not have a value. */
528 lookup_or_add (htab_t table, tree e)
530 tree x = lookup (table, e);
534 v = create_new_value (e);
538 set_value_handle (e, x);
543 /* Search in the bitmap for SET to see if E exists. */
546 value_exists_in_set_bitmap (value_set_t set, tree e)
548 if (TREE_CODE (e) != VAR_DECL)
553 return bitmap_bit_p (set->values, get_var_ann (e)->uid);
556 /* Remove E from the bitmap for SET. */
559 value_remove_from_set_bitmap (value_set_t set, tree e)
561 if (TREE_CODE (e) != VAR_DECL)
563 #ifdef ENABLE_CHECKING
569 bitmap_clear_bit (set->values, get_var_ann (e)->uid);
573 /* Insert the value number E into the bitmap of values existing in
577 value_insert_into_set_bitmap (value_set_t set, tree e)
579 if (TREE_CODE (e) != VAR_DECL)
581 #ifdef ENABLE_CHECKING
585 if (set->values == NULL)
587 set->values = BITMAP_GGC_ALLOC ();
588 bitmap_clear (set->values);
590 bitmap_set_bit (set->values, get_var_ann (e)->uid);
593 /* Create a new set. */
596 set_new (bool indexed)
599 ret = pool_alloc (value_set_pool);
600 ret->head = ret->tail = NULL;
602 ret->indexed = indexed;
608 /* Insert EXPR into SET. */
611 insert_into_set (value_set_t set, tree expr)
613 value_set_node_t newnode = pool_alloc (value_set_node_pool);
614 tree val = get_value_handle (expr);
621 /* For indexed sets, insert the value into the set value bitmap.
622 For all sets, add it to the linked list and increment the list
625 value_insert_into_set_bitmap (set, val);
627 newnode->next = NULL;
628 newnode->expr = expr;
630 if (set->head == NULL)
632 set->head = set->tail = newnode;
636 set->tail->next = newnode;
641 /* Copy the set ORIG to the set DEST. */
644 set_copy (value_set_t dest, value_set_t orig)
646 value_set_node_t node;
648 if (!orig || !orig->head)
651 for (node = orig->head;
655 insert_into_set (dest, node->expr);
659 /* Remove EXPR from SET. */
662 set_remove (value_set_t set, tree expr)
664 value_set_node_t node, prev;
666 /* Remove the value of EXPR from the bitmap, decrement the set
667 length, and remove it from the actual double linked list. */
668 value_remove_from_set_bitmap (set, get_value_handle (expr));
671 for (node = set->head;
673 prev = node, node = node->next)
675 if (node->expr == expr)
678 set->head = node->next;
680 prev->next= node->next;
682 if (node == set->tail)
684 pool_free (value_set_node_pool, node);
690 /* Return true if SET contains the value VAL. */
693 set_contains_value (value_set_t set, tree val)
695 /* This is only referring to the flag above that we set on
696 values referring to numerical constants, because we know that we
697 are dealing with one of the value handles we created. */
698 if (TREE_CONSTANT (val))
701 if (set->length == 0)
704 return value_exists_in_set_bitmap (set, val);
707 /* Replace the leader for the value LOOKFOR in SET with EXPR. */
710 set_replace_value (value_set_t set, tree lookfor, tree expr)
712 value_set_node_t node = set->head;
714 /* The lookup is probably more expensive than walking the linked
715 list when we have only a small number of nodes. */
716 if (!set_contains_value (set, lookfor))
719 for (node = set->head;
723 if (get_value_handle (node->expr) == lookfor)
731 /* Return true if the set contains expression (not value) EXPR. */
734 set_contains (value_set_t set, tree expr)
736 value_set_node_t node;
738 for (node = set->head;
742 if (operand_equal_p (node->expr, expr, 0))
748 /* Subtract set B from set A, and return the new set. */
751 set_subtract (value_set_t a, value_set_t b, bool indexed)
753 value_set_t ret = set_new (indexed);
754 value_set_node_t node;
759 if (!set_contains (b, node->expr))
760 insert_into_set (ret, node->expr);
765 /* Return true if two sets are equal. */
768 set_equal (value_set_t a, value_set_t b)
770 value_set_node_t node;
772 if (a->length != b->length)
778 if (!set_contains_value (b, get_value_handle (node->expr)))
784 /* Replace the value for EXPR in SET with EXPR. */
786 value_replace_in_set (value_set_t set, tree expr)
788 tree val = get_value_handle (expr);
790 if (set->length == 0)
793 set_replace_value (set, val, expr);
796 /* Insert the value for EXPR into SET, if it doesn't exist already. */
799 value_insert_into_set (value_set_t set, tree expr)
801 tree val = get_value_handle (expr);
803 /* Constant values exist everywhere. */
804 if (TREE_CONSTANT (val))
807 if (!set_contains_value (set, val))
808 insert_into_set (set, expr);
812 /* Print out the value_set SET to OUTFILE. */
815 print_value_set (FILE *outfile, value_set_t set,
816 const char *setname, int blockindex)
818 value_set_node_t node;
819 fprintf (outfile, "%s[%d] := { ", setname, blockindex);
822 for (node = set->head;
826 print_generic_expr (outfile, node->expr, 0);
828 fprintf (outfile, ", ");
832 fprintf (outfile, " }\n");
835 /* Print out the expressions that have VAL to OUTFILE. */
837 print_value_expressions (FILE *outfile, tree val)
839 var_ann_t va = var_ann (val);
840 if (va && va->expr_set)
841 print_value_set (outfile, va->expr_set,
842 IDENTIFIER_POINTER (DECL_NAME (val)), 0);
847 debug_value_expressions (tree val)
849 print_value_expressions (stderr, val);
853 void debug_value_set (value_set_t, const char *, int);
856 debug_value_set (value_set_t set, const char *setname, int blockindex)
858 print_value_set (stderr, set, setname, blockindex);
861 /* Translate EXPR using phis in PHIBLOCK, so that it has the values of
862 the phis in PRED. Return NULL if we can't find a leader for each
863 part of the translated expression. */
866 phi_translate (tree expr, value_set_t set, basic_block pred,
867 basic_block phiblock)
869 tree phitrans = NULL;
875 /* Phi translations of a given expression don't change, */
876 phitrans = phi_trans_lookup (expr, pred);
881 switch (TREE_CODE_CLASS (TREE_CODE (expr)))
885 tree oldop1 = TREE_OPERAND (expr, 0);
886 tree oldop2 = TREE_OPERAND (expr, 1);
891 newop1 = phi_translate (find_leader (set, oldop1),
892 set, pred, phiblock);
895 newop2 = phi_translate (find_leader (set, oldop2),
896 set, pred, phiblock);
899 if (newop1 != oldop1 || newop2 != oldop2)
901 newexpr = pool_alloc (binary_node_pool);
902 memcpy (newexpr, expr, tree_size (expr));
903 create_expr_ann (newexpr);
904 TREE_OPERAND (newexpr, 0) = newop1 == oldop1 ? oldop1 : get_value_handle (newop1);
905 TREE_OPERAND (newexpr, 1) = newop2 == oldop2 ? oldop2 : get_value_handle (newop2);
906 lookup_or_add (value_table, newexpr);
908 phi_trans_add (oldexpr, newexpr, pred);
914 tree oldop1 = TREE_OPERAND (expr, 0);
918 newop1 = phi_translate (find_leader (set, oldop1),
919 set, pred, phiblock);
922 if (newop1 != oldop1)
924 newexpr = pool_alloc (unary_node_pool);
925 memcpy (newexpr, expr, tree_size (expr));
926 create_expr_ann (newexpr);
927 TREE_OPERAND (newexpr, 0) = get_value_handle (newop1);
928 lookup_or_add (value_table, newexpr);
930 phi_trans_add (oldexpr, newexpr, pred);
940 if (TREE_CODE (expr) != SSA_NAME)
942 if (TREE_CODE (SSA_NAME_DEF_STMT (expr)) == PHI_NODE)
943 phi = SSA_NAME_DEF_STMT (expr);
947 for (i = 0; i < PHI_NUM_ARGS (phi); i++)
948 if (PHI_ARG_EDGE (phi, i)->src == pred)
951 if (is_undefined_value (PHI_ARG_DEF (phi, i)))
953 val = lookup_or_add (value_table, PHI_ARG_DEF (phi, i));
954 return PHI_ARG_DEF (phi, i);
963 phi_translate_set (value_set_t dest, value_set_t set, basic_block pred,
964 basic_block phiblock)
966 value_set_node_t node;
967 for (node = set->head;
972 translated = phi_translate (node->expr, set, pred, phiblock);
973 phi_trans_add (node->expr, translated, pred);
975 if (translated != NULL)
976 value_insert_into_set (dest, translated);
980 /* Find the leader for a value (IE the name representing that
981 value) in a given set, and return it. Return NULL if no leader is
985 find_leader (value_set_t set, tree val)
987 value_set_node_t node;
992 if (TREE_CONSTANT (val))
993 return TREE_CHAIN (val);
995 if (set->length == 0)
998 if (value_exists_in_set_bitmap (set, val))
1000 for (node = set->head;
1004 if (get_value_handle (node->expr) == val)
1011 /* Determine if the expression EXPR is valid in SET. This means that
1012 we have a leader for each part of the expression (if it consists of
1013 values), or the expression is an SSA_NAME.
1015 NB: We never should run into a case where we have SSA_NAME +
1016 SSA_NAME or SSA_NAME + value. The sets valid_in_set is called on,
1017 the ANTIC sets, will only ever have SSA_NAME's or binary value
1018 expression (IE VALUE1 + VALUE2) */
1021 valid_in_set (value_set_t set, tree expr)
1023 switch (TREE_CODE_CLASS (TREE_CODE (expr)))
1027 tree op1 = TREE_OPERAND (expr, 0);
1028 tree op2 = TREE_OPERAND (expr, 1);
1029 return set_contains_value (set, op1) && set_contains_value (set, op2);
1034 tree op1 = TREE_OPERAND (expr, 0);
1035 return set_contains_value (set, op1);
1040 if (TREE_CODE (expr) == SSA_NAME)
1050 /* Clean the set of expressions that are no longer valid in the
1051 specified set. This means expressions that are made up of values
1052 we have no leaders for in the current set, etc. */
1055 clean (value_set_t set)
1057 value_set_node_t node;
1058 value_set_node_t next;
1063 if (!valid_in_set (set, node->expr))
1064 set_remove (set, node->expr);
1069 /* Compute the ANTIC set for BLOCK.
1071 ANTIC_OUT[BLOCK] = intersection of ANTIC_IN[b] for all succ(BLOCK), if
1073 ANTIC_OUT[BLOCK] = phi_translate (ANTIC_IN[succ(BLOCK)]) if
1076 ANTIC_IN[BLOCK] = clean(ANTIC_OUT[BLOCK] U EXP_GEN[BLOCK] -
1079 Iterate until fixpointed.
1081 XXX: It would be nice to either write a set_clear, and use it for
1082 antic_out, or to mark the antic_out set as deleted at the end
1083 of this routine, so that the pool can hand the same memory back out
1084 again for the next antic_out. */
1088 compute_antic_aux (basic_block block)
1092 bool changed = false;
1093 value_set_t S, old, ANTIC_OUT;
1094 value_set_node_t node;
1096 ANTIC_OUT = S = NULL;
1097 /* If any edges from predecessors are abnormal, antic_in is empty, so
1098 punt. Remember that the block has an incoming abnormal edge by
1099 setting the BB_VISITED flag. */
1100 if (! (block->flags & BB_VISITED))
1102 for (e = block->pred; e; e = e->pred_next)
1103 if (e->flags & EDGE_ABNORMAL)
1105 block->flags |= BB_VISITED;
1109 if (block->flags & BB_VISITED)
1116 old = set_new (false);
1117 set_copy (old, ANTIC_IN (block));
1118 ANTIC_OUT = set_new (true);
1120 /* If the block has no successors, ANTIC_OUT is empty, because it is
1122 if (block->succ == NULL);
1124 /* If we have one successor, we could have some phi nodes to
1125 translate through. */
1126 else if (block->succ->succ_next == NULL)
1128 phi_translate_set (ANTIC_OUT, ANTIC_IN(block->succ->dest),
1129 block, block->succ->dest);
1131 /* If we have multiple successors, we take the intersection of all of
1135 varray_type worklist;
1138 basic_block bprime, first;
1140 VARRAY_BB_INIT (worklist, 1, "succ");
1144 VARRAY_PUSH_BB (worklist, e->dest);
1147 first = VARRAY_BB (worklist, 0);
1148 set_copy (ANTIC_OUT, ANTIC_IN (first));
1150 for (i = 1; i < VARRAY_ACTIVE_SIZE (worklist); i++)
1152 bprime = VARRAY_BB (worklist, i);
1153 node = ANTIC_OUT->head;
1157 value_set_node_t next = node->next;
1158 val = get_value_handle (node->expr);
1159 if (!set_contains_value (ANTIC_IN (bprime), val))
1160 set_remove (ANTIC_OUT, node->expr);
1164 VARRAY_CLEAR (worklist);
1167 /* Generate ANTIC_OUT - TMP_GEN */
1168 S = set_subtract (ANTIC_OUT, TMP_GEN (block), false);
1170 /* Start ANTIC_IN with EXP_GEN - TMP_GEN */
1171 ANTIC_IN (block) = set_subtract (EXP_GEN (block),TMP_GEN (block), true);
1173 /* Then union in the ANTIC_OUT - TMP_GEN values, to get ANTIC_OUT U
1174 EXP_GEN - TMP_GEN */
1175 for (node = S->head;
1179 value_insert_into_set (ANTIC_IN (block), node->expr);
1181 clean (ANTIC_IN (block));
1183 if (!set_equal (old, ANTIC_IN (block)))
1187 if (dump_file && (dump_flags & TDF_DETAILS))
1190 print_value_set (dump_file, ANTIC_OUT, "ANTIC_OUT", block->index);
1191 print_value_set (dump_file, ANTIC_IN (block), "ANTIC_IN", block->index);
1193 print_value_set (dump_file, S, "S", block->index);
1197 for (son = first_dom_son (CDI_POST_DOMINATORS, block);
1199 son = next_dom_son (CDI_POST_DOMINATORS, son))
1201 changed |= compute_antic_aux (son);
1206 /* Compute ANTIC sets. */
1209 compute_antic (void)
1211 bool changed = true;
1213 int num_iterations = 0;
1216 ANTIC_IN (bb) = set_new (true);
1217 bb->flags &= ~BB_VISITED;
1224 changed = compute_antic_aux (EXIT_BLOCK_PTR);
1226 if (num_iterations > 2 && dump_file && (dump_flags & TDF_STATS))
1227 fprintf (dump_file, "compute_antic required %d iterations\n", num_iterations);
1230 /* Perform insertion of partially redundant values.
1231 For BLOCK, do the following:
1232 1. Propagate the NEW_SETS of the dominator into the current block.
1233 If the block has multiple predecessors,
1234 2a. Iterate over the ANTIC expressions for the block to see if
1235 any of them are partially redundant.
1236 2b. If so, insert them into the necessary predecessors to make
1237 the expression fully redundant.
1238 2c. Insert a new PHI merging the values of the predecessors.
1239 2d. Insert the new PHI, and the new expressions, into the
1241 3. Recursively call ourselves on the dominator children of BLOCK.
1245 insert_aux (basic_block block)
1248 bool new_stuff = false;
1254 dom = get_immediate_dominator (CDI_DOMINATORS, block);
1257 e = NEW_SETS (dom)->head;
1260 insert_into_set (NEW_SETS (block), e->expr);
1261 value_replace_in_set (AVAIL_OUT (block), e->expr);
1264 if (block->pred->pred_next)
1266 value_set_node_t node;
1267 for (node = ANTIC_IN (block)->head;
1271 if (TREE_CODE_CLASS (TREE_CODE (node->expr)) == '2'
1272 || TREE_CODE_CLASS (TREE_CODE (node->expr)) == '1')
1276 bool by_some = false;
1277 bool all_same = true;
1278 tree first_s = NULL;
1282 bool cant_insert = false;
1284 val = get_value_handle (node->expr);
1285 if (set_contains_value (PHI_GEN (block), val))
1287 if (set_contains_value (AVAIL_OUT (dom), val))
1289 if (dump_file && (dump_flags & TDF_DETAILS))
1290 fprintf (dump_file, "Found fully redundant value\n");
1294 avail = xcalloc (last_basic_block, sizeof (tree));
1295 for (pred = block->pred;
1297 pred = pred->pred_next)
1302 eprime = phi_translate (node->expr,
1306 /* eprime will generally only be NULL if the
1307 value of the expression, translated
1308 through the PHI for this predecessor, is
1309 undefined. If that is the case, we can't
1310 make the expression fully redundant,
1311 because its value is undefined along a
1312 predecessor path. We can thus break out
1313 early because it doesn't matter what the
1314 rest of the results are. */
1321 vprime = get_value_handle (eprime);
1324 edoubleprime = find_leader (AVAIL_OUT (bprime),
1326 if (edoubleprime == NULL)
1328 avail[bprime->index] = eprime;
1333 avail[bprime->index] = edoubleprime;
1335 if (first_s == NULL)
1336 first_s = edoubleprime;
1337 else if (first_s != edoubleprime)
1339 if (first_s != edoubleprime
1340 && operand_equal_p (first_s, edoubleprime, 0))
1345 if (!cant_insert && !all_same && by_some)
1348 tree type = TREE_TYPE (avail[block->pred->src->index]);
1351 if (dump_file && (dump_flags & TDF_DETAILS))
1353 fprintf (dump_file, "Found partial redundancy for expression ");
1354 print_generic_expr (dump_file, node->expr, 0);
1355 fprintf (dump_file, "\n");
1358 /* Make the necessary insertions. */
1359 for (pred = block->pred;
1361 pred = pred->pred_next)
1364 eprime = avail[bprime->index];
1365 if (TREE_CODE_CLASS (TREE_CODE (eprime)) == '2')
1369 s1 = find_leader (AVAIL_OUT (bprime),
1370 TREE_OPERAND (eprime, 0));
1371 /* Depending on the order we process
1372 DOM branches in, the value may
1373 not have propagated to all the
1374 dom children yet during this
1375 iteration. In this case, the
1376 value will always be in the
1377 NEW_SETS for *our* dominator */
1379 s1 = find_leader (NEW_SETS (dom),
1380 TREE_OPERAND (eprime, 0));
1384 s2 = find_leader (AVAIL_OUT (bprime),
1385 TREE_OPERAND (eprime, 1));
1387 s2 = find_leader (NEW_SETS (dom),
1388 TREE_OPERAND (eprime, 1));
1392 temp = create_tmp_var (TREE_TYPE (eprime),
1394 add_referenced_tmp_var (temp);
1395 newexpr = build (TREE_CODE (eprime),
1398 newexpr = build (MODIFY_EXPR,
1401 temp = make_ssa_name (temp, newexpr);
1402 TREE_OPERAND (newexpr, 0) = temp;
1403 bsi_insert_on_edge (pred, newexpr);
1404 bsi_commit_edge_inserts (NULL);
1406 if (dump_file && (dump_flags & TDF_DETAILS))
1408 fprintf (dump_file, "Inserted ");
1409 print_generic_expr (dump_file, newexpr, 0);
1410 fprintf (dump_file, " in predecessor %d\n", pred->src->index);
1412 pre_stats.insertions++;
1413 v = lookup_or_add (value_table, eprime);
1414 add (value_table, temp, v);
1415 insert_into_set (NEW_SETS (bprime), temp);
1416 value_insert_into_set (AVAIL_OUT (bprime),
1418 avail[bprime->index] = temp;
1420 else if (TREE_CODE_CLASS (TREE_CODE (eprime)) == '1')
1424 s1 = find_leader (AVAIL_OUT (bprime),
1425 TREE_OPERAND (eprime, 0));
1426 /* Depending on the order we process
1427 DOM branches in, the value may not have
1428 propagated to all the dom
1429 children yet in the current
1430 iteration, but it will be in
1431 NEW_SETS if it is not yet
1435 s1 = find_leader (NEW_SETS (dom),
1436 TREE_OPERAND (eprime, 0));
1440 temp = create_tmp_var (TREE_TYPE (eprime),
1442 add_referenced_tmp_var (temp);
1443 newexpr = build (TREE_CODE (eprime),
1446 newexpr = build (MODIFY_EXPR,
1449 temp = make_ssa_name (temp, newexpr);
1450 TREE_OPERAND (newexpr, 0) = temp;
1451 bsi_insert_on_edge (pred, newexpr);
1452 bsi_commit_edge_inserts (NULL);
1454 if (dump_file && (dump_flags & TDF_DETAILS))
1456 fprintf (dump_file, "Inserted ");
1457 print_generic_expr (dump_file, newexpr, 0);
1458 fprintf (dump_file, " in predecessor %d\n", pred->src->index);
1460 pre_stats.insertions++;
1461 v = lookup_or_add (value_table, eprime);
1462 add (value_table, temp, v);
1463 insert_into_set (NEW_SETS (bprime), temp);
1464 value_insert_into_set (AVAIL_OUT (bprime),
1466 avail[bprime->index] = temp;
1469 /* Now build a phi for the new variable. */
1470 temp = create_tmp_var (type, "prephitmp");
1471 add_referenced_tmp_var (temp);
1472 temp = create_phi_node (temp, block);
1473 add (value_table, PHI_RESULT (temp), val);
1476 if (!set_contains_value (AVAIL_OUT (block), val))
1477 insert_into_set (AVAIL_OUT (block),
1481 value_replace_in_set (AVAIL_OUT (block),
1483 for (pred = block->pred;
1485 pred = pred->pred_next)
1487 add_phi_arg (&temp, avail[pred->src->index],
1490 if (dump_file && (dump_flags & TDF_DETAILS))
1492 fprintf (dump_file, "Created phi ");
1493 print_generic_expr (dump_file, temp, 0);
1494 fprintf (dump_file, " in block %d\n", block->index);
1498 insert_into_set (NEW_SETS (block),
1500 insert_into_set (PHI_GEN (block),
1510 for (son = first_dom_son (CDI_DOMINATORS, block);
1512 son = next_dom_son (CDI_DOMINATORS, son))
1514 new_stuff |= insert_aux (son);
1520 /* Perform insertion of partially redundant values. */
1525 bool new_stuff = true;
1527 int num_iterations = 0;
1530 NEW_SETS (bb) = set_new (true);
1536 new_stuff = insert_aux (ENTRY_BLOCK_PTR);
1538 if (num_iterations > 2 && dump_file && (dump_flags & TDF_STATS))
1539 fprintf (dump_file, "insert required %d iterations\n", num_iterations);
1542 /* Return true if EXPR has no defining statement in this procedure,
1543 *AND* isn't a live-on-entry parameter. */
1545 is_undefined_value (tree expr)
1548 #ifdef ENABLE_CHECKING
1549 /* We should never be handed DECL's */
1553 if (TREE_CODE (expr) == SSA_NAME)
1555 /* XXX: Is this the correct test? */
1556 if (TREE_CODE (SSA_NAME_VAR (expr)) == PARM_DECL)
1558 if (IS_EMPTY_STMT (SSA_NAME_DEF_STMT (expr)))
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 entry per
1571 AVAIL_IN[BLOCK] = AVAIL_OUT[dom(BLOCK)].
1572 AVAIL_OUT[BLOCK] = AVAIL_IN[BLOCK] U PHI_GEN[BLOCK] U
1577 compute_avail (basic_block block)
1581 /* For arguments with default definitions, we pretend they are
1582 defined in the entry block. */
1583 if (block == ENTRY_BLOCK_PTR)
1586 for (param = DECL_ARGUMENTS (current_function_decl);
1588 param = TREE_CHAIN (param))
1590 if (default_def (param) != NULL)
1593 tree def = default_def (param);
1594 val = lookup_or_add (value_table, def);
1595 insert_into_set (TMP_GEN (block), def);
1596 value_insert_into_set (AVAIL_OUT (block), def);
1602 block_stmt_iterator bsi;
1606 dom = get_immediate_dominator (CDI_DOMINATORS, block);
1608 set_copy (AVAIL_OUT (block), AVAIL_OUT (dom));
1609 for (phi = phi_nodes (block); phi; phi = TREE_CHAIN (phi))
1611 /* Ignore virtual PHIs until we can do PRE on expressions
1612 with virtual operands. */
1613 if (!is_gimple_reg (SSA_NAME_VAR (PHI_RESULT (phi))))
1616 lookup_or_add (value_table, PHI_RESULT (phi));
1617 value_insert_into_set (AVAIL_OUT (block), PHI_RESULT (phi));
1618 insert_into_set (PHI_GEN (block), PHI_RESULT (phi));
1621 for (bsi = bsi_start (block); !bsi_end_p (bsi); bsi_next (&bsi))
1624 stmt = bsi_stmt (bsi);
1625 get_stmt_operands (stmt);
1627 if (NUM_VUSES (STMT_VUSE_OPS (stmt))
1628 || NUM_V_MUST_DEFS (STMT_V_MUST_DEF_OPS (stmt))
1629 || NUM_V_MAY_DEFS (STMT_V_MAY_DEF_OPS (stmt))
1630 || stmt_ann (stmt)->has_volatile_ops)
1633 for (j = 0; j < NUM_DEFS (STMT_DEF_OPS (stmt)); j++)
1635 tree def = DEF_OP (STMT_DEF_OPS (stmt), j);
1636 lookup_or_add (value_table, def);
1637 insert_into_set (TMP_GEN (block), def);
1638 value_insert_into_set (AVAIL_OUT (block), def);
1642 else if (TREE_CODE (stmt) == RETURN_EXPR
1643 && TREE_OPERAND (stmt, 0)
1644 && TREE_CODE (TREE_OPERAND (stmt, 0)) == MODIFY_EXPR)
1645 stmt = TREE_OPERAND (stmt, 0);
1647 if (TREE_CODE (stmt) == MODIFY_EXPR)
1649 op0 = TREE_OPERAND (stmt, 0);
1650 if (TREE_CODE (op0) != SSA_NAME)
1652 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op0))
1654 op1 = TREE_OPERAND (stmt, 1);
1655 if (TREE_CODE_CLASS (TREE_CODE (op1)) == 'c')
1657 add (value_table, op0, lookup_or_add (value_table, op1));
1658 insert_into_set (TMP_GEN (block), op0);
1659 value_insert_into_set (AVAIL_OUT (block), op0);
1661 else if (TREE_CODE_CLASS (TREE_CODE (op1)) == '2')
1664 tree val, val1, val2;
1666 bop1 = TREE_OPERAND (op1, 0);
1667 bop2 = TREE_OPERAND (op1, 1);
1668 val1 = lookup_or_add (value_table, bop1);
1669 val2 = lookup_or_add (value_table, bop2);
1671 newt = pool_alloc (binary_node_pool);
1672 memcpy (newt, op1, tree_size (op1));
1673 TREE_OPERAND (newt, 0) = val1;
1674 TREE_OPERAND (newt, 1) = val2;
1675 val = lookup_or_add (value_table, newt);
1676 add (value_table, op0, val);
1677 if (!is_undefined_value (bop1))
1678 value_insert_into_set (EXP_GEN (block), bop1);
1679 if (!is_undefined_value (bop2))
1680 value_insert_into_set (EXP_GEN (block), bop2);
1681 value_insert_into_set (EXP_GEN (block), newt);
1682 insert_into_set (TMP_GEN (block), op0);
1683 value_insert_into_set (AVAIL_OUT (block), op0);
1685 else if (TREE_CODE_CLASS (TREE_CODE (op1)) == '1')
1690 uop = TREE_OPERAND (op1, 0);
1691 val1 = lookup_or_add (value_table, uop);
1692 newt = pool_alloc (unary_node_pool);
1693 memcpy (newt, op1, tree_size (op1));
1694 TREE_OPERAND (newt, 0) = val1;
1695 val = lookup_or_add (value_table, newt);
1696 add (value_table, op0, val);
1697 if (!is_undefined_value (uop))
1698 value_insert_into_set (EXP_GEN (block), uop);
1699 value_insert_into_set (EXP_GEN (block), newt);
1700 insert_into_set (TMP_GEN (block), op0);
1701 value_insert_into_set (AVAIL_OUT (block), op0);
1703 else if (TREE_CODE (op1) == SSA_NAME)
1705 tree val = lookup_or_add (value_table, op1);
1706 add (value_table, op0, val);
1707 if (!is_undefined_value (op1))
1708 value_insert_into_set (EXP_GEN (block), op1);
1709 insert_into_set (TMP_GEN (block), op0);
1710 value_insert_into_set (AVAIL_OUT (block), op0);
1715 for (j = 0; j < NUM_DEFS (STMT_DEF_OPS (stmt)); j++)
1717 tree def = DEF_OP (STMT_DEF_OPS (stmt), j);
1718 lookup_or_add (value_table, def);
1719 insert_into_set (TMP_GEN (block), def);
1720 value_insert_into_set (AVAIL_OUT (block), def);
1721 value_insert_into_set (AVAIL_OUT (block), op0);
1728 for (j = 0; j < NUM_DEFS (STMT_DEF_OPS (stmt)); j++)
1730 tree def = DEF_OP (STMT_DEF_OPS (stmt), j);
1731 lookup_or_add (value_table, def);
1732 insert_into_set (TMP_GEN (block), def);
1733 value_insert_into_set (AVAIL_OUT (block), def);
1738 for (son = first_dom_son (CDI_DOMINATORS, block);
1740 son = next_dom_son (CDI_DOMINATORS, son))
1741 compute_avail (son);
1745 /* Eliminate fully redundant computations. */
1754 block_stmt_iterator i;
1756 for (i = bsi_start (b); !bsi_end_p (i); bsi_next (&i))
1758 tree stmt = bsi_stmt (i);
1760 if (NUM_VUSES (STMT_VUSE_OPS (stmt))
1761 || NUM_V_MUST_DEFS (STMT_V_MUST_DEF_OPS (stmt))
1762 || NUM_V_MAY_DEFS (STMT_V_MAY_DEF_OPS (stmt))
1763 || stmt_ann (stmt)->has_volatile_ops)
1765 /* Lookup the RHS of the expression, see if we have an
1766 available computation for it. If so, replace the RHS with
1767 the available computation. */
1768 if (TREE_CODE (stmt) == MODIFY_EXPR)
1770 tree t = TREE_OPERAND (stmt, 0);
1771 tree expr = TREE_OPERAND (stmt, 1);
1773 /* There is no point in eliminating NOP_EXPR, it isn't
1774 supposed to generate any code. */
1775 if (TREE_CODE (expr) == NOP_EXPR
1776 || (TREE_CODE_CLASS (TREE_CODE (expr)) != '2'
1777 && TREE_CODE_CLASS (TREE_CODE (expr)) != '1'))
1779 sprime = find_leader (AVAIL_OUT (b),
1780 lookup (value_table, t));
1783 && may_propagate_copy (sprime, TREE_OPERAND (stmt, 1)))
1785 if (dump_file && (dump_flags & TDF_DETAILS))
1787 fprintf (dump_file, "Replaced ");
1788 print_generic_expr (dump_file, expr, 0);
1789 fprintf (dump_file, " with ");
1790 print_generic_expr (dump_file, sprime, 0);
1791 fprintf (dump_file, " in ");
1792 print_generic_stmt (dump_file, stmt, 0);
1794 pre_stats.eliminations++;
1795 propagate_value (&TREE_OPERAND (stmt, 1), sprime);
1804 /* Main entry point to the SSA-PRE pass.
1806 PHASE indicates which dump file from the DUMP_FILES array to use when
1807 dumping debugging information. */
1814 pre_uid = num_referenced_vars;
1815 memset (&pre_stats, 0, sizeof (pre_stats));
1818 bb->aux = xcalloc (1, sizeof (struct bb_value_sets));
1820 phi_translate_table = htab_create (511, expr_pred_trans_hash,
1823 value_table = htab_create (511, val_expr_pair_hash,
1824 val_expr_pair_expr_eq, free);
1825 value_set_pool = create_alloc_pool ("Value sets",
1826 sizeof (struct value_set), 30);
1827 value_set_node_pool = create_alloc_pool ("Value set nodes",
1828 sizeof (struct value_set_node), 30);
1829 calculate_dominance_info (CDI_POST_DOMINATORS);
1830 calculate_dominance_info (CDI_DOMINATORS);
1831 tsize = tree_size (build (PLUS_EXPR, void_type_node, NULL_TREE,
1833 binary_node_pool = create_alloc_pool ("Binary tree nodes", tsize, 30);
1834 tsize = tree_size (build1 (NEGATE_EXPR, void_type_node, NULL_TREE));
1835 unary_node_pool = create_alloc_pool ("Unary tree nodes", tsize, 30);
1839 EXP_GEN (bb) = set_new (true);
1840 PHI_GEN (bb) = set_new (true);
1841 TMP_GEN (bb) = set_new (false);
1842 AVAIL_OUT (bb) = set_new (true);
1845 compute_avail (ENTRY_BLOCK_PTR);
1847 if (dump_file && (dump_flags & TDF_DETAILS))
1851 print_value_set (dump_file, EXP_GEN (bb), "exp_gen", bb->index);
1852 print_value_set (dump_file, TMP_GEN (bb), "tmp_gen", bb->index);
1853 print_value_set (dump_file, AVAIL_OUT (bb), "avail_out", bb->index);
1857 /* Insert can get quite slow on an incredibly large number of basic
1858 blocks due to some quadratic behavior. Until this behavior is
1859 fixed, don't run it when he have an incredibly large number of
1860 bb's. If we aren't going to run insert, there is no point in
1861 computing ANTIC, either, even though it's plenty fast. */
1863 if (n_basic_blocks < 4000)
1871 if (dump_file && (dump_flags & TDF_STATS))
1873 fprintf (dump_file, "Insertions:%d\n", pre_stats.insertions);
1874 fprintf (dump_file, "New PHIs:%d\n", pre_stats.phis);
1875 fprintf (dump_file, "Eliminated:%d\n", pre_stats.eliminations);
1878 free_alloc_pool (value_set_pool);
1879 free_alloc_pool (value_set_node_pool);
1880 free_alloc_pool (binary_node_pool);
1881 free_alloc_pool (unary_node_pool);
1882 htab_delete (value_table);
1883 htab_delete (phi_translate_table);
1890 free_dominance_info (CDI_POST_DOMINATORS);
1896 return flag_tree_pre != 0;
1899 struct tree_opt_pass pass_pre =
1902 gate_pre, /* gate */
1903 execute_pre, /* execute */
1906 0, /* static_pass_number */
1907 TV_TREE_PRE, /* tv_id */
1908 PROP_no_crit_edges | PROP_cfg | PROP_ssa,/* properties_required */
1909 0, /* properties_provided */
1910 0, /* properties_destroyed */
1911 0, /* todo_flags_start */
1912 TODO_dump_func | TODO_ggc_collect | TODO_verify_ssa /* todo_flags_finish */