2 Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009
3 Free Software Foundation, Inc.
4 Contributed by Daniel Berlin <dan@dberlin.org> and Steven Bosscher
7 This file is part of GCC.
9 GCC is free software; you can redistribute it and/or modify
10 it under the terms of the GNU General Public License as published by
11 the Free Software Foundation; either version 3, or (at your option)
14 GCC is distributed in the hope that it will be useful,
15 but WITHOUT ANY WARRANTY; without even the implied warranty of
16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 GNU General Public License for more details.
19 You should have received a copy of the GNU General Public License
20 along with GCC; see the file COPYING3. If not see
21 <http://www.gnu.org/licenses/>. */
25 #include "coretypes.h"
29 #include "basic-block.h"
30 #include "diagnostic.h"
31 #include "tree-inline.h"
32 #include "tree-flow.h"
34 #include "tree-dump.h"
38 #include "tree-iterator.h"
40 #include "alloc-pool.h"
42 #include "tree-pass.h"
45 #include "langhooks.h"
47 #include "tree-ssa-sccvn.h"
53 1. 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 2. Strength reduction can be performed by anticipating expressions
57 we can repair later on.
58 3. We can do back-substitution or smarter value numbering to catch
59 commutative expressions split up over multiple statements.
62 /* For ease of terminology, "expression node" in the below refers to
63 every expression node but GIMPLE_ASSIGN, because GIMPLE_ASSIGNs
64 represent the actual statement containing the expressions we care about,
65 and we cache the value number by putting it in the expression. */
69 First we walk the statements to generate the AVAIL sets, the
70 EXP_GEN sets, and the tmp_gen sets. EXP_GEN sets represent the
71 generation of values/expressions by a given block. We use them
72 when computing the ANTIC sets. The AVAIL sets consist of
73 SSA_NAME's that represent values, so we know what values are
74 available in what blocks. AVAIL is a forward dataflow problem. In
75 SSA, values are never killed, so we don't need a kill set, or a
76 fixpoint iteration, in order to calculate the AVAIL sets. In
77 traditional parlance, AVAIL sets tell us the downsafety of the
80 Next, we generate the ANTIC sets. These sets represent the
81 anticipatable expressions. ANTIC is a backwards dataflow
82 problem. An expression is anticipatable in a given block if it could
83 be generated in that block. This means that if we had to perform
84 an insertion in that block, of the value of that expression, we
85 could. Calculating the ANTIC sets requires phi translation of
86 expressions, because the flow goes backwards through phis. We must
87 iterate to a fixpoint of the ANTIC sets, because we have a kill
88 set. Even in SSA form, values are not live over the entire
89 function, only from their definition point onwards. So we have to
90 remove values from the ANTIC set once we go past the definition
91 point of the leaders that make them up.
92 compute_antic/compute_antic_aux performs this computation.
94 Third, we perform insertions to make partially redundant
95 expressions fully redundant.
97 An expression is partially redundant (excluding partial
100 1. It is AVAIL in some, but not all, of the predecessors of a
102 2. It is ANTIC in all the predecessors.
104 In order to make it fully redundant, we insert the expression into
105 the predecessors where it is not available, but is ANTIC.
107 For the partial anticipation case, we only perform insertion if it
108 is partially anticipated in some block, and fully available in all
111 insert/insert_aux/do_regular_insertion/do_partial_partial_insertion
112 performs these steps.
114 Fourth, we eliminate fully redundant expressions.
115 This is a simple statement walk that replaces redundant
116 calculations with the now available values. */
118 /* Representations of value numbers:
120 Value numbers are represented by a representative SSA_NAME. We
121 will create fake SSA_NAME's in situations where we need a
122 representative but do not have one (because it is a complex
123 expression). In order to facilitate storing the value numbers in
124 bitmaps, and keep the number of wasted SSA_NAME's down, we also
125 associate a value_id with each value number, and create full blown
126 ssa_name's only where we actually need them (IE in operands of
127 existing expressions).
129 Theoretically you could replace all the value_id's with
130 SSA_NAME_VERSION, but this would allocate a large number of
131 SSA_NAME's (which are each > 30 bytes) just to get a 4 byte number.
132 It would also require an additional indirection at each point we
135 /* Representation of expressions on value numbers:
137 Expressions consisting of value numbers are represented the same
138 way as our VN internally represents them, with an additional
139 "pre_expr" wrapping around them in order to facilitate storing all
140 of the expressions in the same sets. */
142 /* Representation of sets:
144 The dataflow sets do not need to be sorted in any particular order
145 for the majority of their lifetime, are simply represented as two
146 bitmaps, one that keeps track of values present in the set, and one
147 that keeps track of expressions present in the set.
149 When we need them in topological order, we produce it on demand by
150 transforming the bitmap into an array and sorting it into topo
153 /* Type of expression, used to know which member of the PRE_EXPR union
164 typedef union pre_expr_union_d
169 vn_reference_t reference;
172 typedef struct pre_expr_d
174 enum pre_expr_kind kind;
179 #define PRE_EXPR_NAME(e) (e)->u.name
180 #define PRE_EXPR_NARY(e) (e)->u.nary
181 #define PRE_EXPR_REFERENCE(e) (e)->u.reference
182 #define PRE_EXPR_CONSTANT(e) (e)->u.constant
185 pre_expr_eq (const void *p1, const void *p2)
187 const struct pre_expr_d *e1 = (const struct pre_expr_d *) p1;
188 const struct pre_expr_d *e2 = (const struct pre_expr_d *) p2;
190 if (e1->kind != e2->kind)
196 return vn_constant_eq_with_type (PRE_EXPR_CONSTANT (e1),
197 PRE_EXPR_CONSTANT (e2));
199 return PRE_EXPR_NAME (e1) == PRE_EXPR_NAME (e2);
201 return vn_nary_op_eq (PRE_EXPR_NARY (e1), PRE_EXPR_NARY (e2));
203 return vn_reference_eq (PRE_EXPR_REFERENCE (e1),
204 PRE_EXPR_REFERENCE (e2));
211 pre_expr_hash (const void *p1)
213 const struct pre_expr_d *e = (const struct pre_expr_d *) p1;
217 return vn_hash_constant_with_type (PRE_EXPR_CONSTANT (e));
219 return iterative_hash_hashval_t (SSA_NAME_VERSION (PRE_EXPR_NAME (e)), 0);
221 return PRE_EXPR_NARY (e)->hashcode;
223 return PRE_EXPR_REFERENCE (e)->hashcode;
230 /* Next global expression id number. */
231 static unsigned int next_expression_id;
233 /* Mapping from expression to id number we can use in bitmap sets. */
234 DEF_VEC_P (pre_expr);
235 DEF_VEC_ALLOC_P (pre_expr, heap);
236 static VEC(pre_expr, heap) *expressions;
237 static htab_t expression_to_id;
239 /* Allocate an expression id for EXPR. */
241 static inline unsigned int
242 alloc_expression_id (pre_expr expr)
245 /* Make sure we won't overflow. */
246 gcc_assert (next_expression_id + 1 > next_expression_id);
247 expr->id = next_expression_id++;
248 VEC_safe_push (pre_expr, heap, expressions, expr);
249 slot = htab_find_slot (expression_to_id, expr, INSERT);
252 return next_expression_id - 1;
255 /* Return the expression id for tree EXPR. */
257 static inline unsigned int
258 get_expression_id (const pre_expr expr)
263 static inline unsigned int
264 lookup_expression_id (const pre_expr expr)
268 slot = htab_find_slot (expression_to_id, expr, NO_INSERT);
271 return ((pre_expr)*slot)->id;
274 /* Return the existing expression id for EXPR, or create one if one
275 does not exist yet. */
277 static inline unsigned int
278 get_or_alloc_expression_id (pre_expr expr)
280 unsigned int id = lookup_expression_id (expr);
282 return alloc_expression_id (expr);
283 return expr->id = id;
286 /* Return the expression that has expression id ID */
288 static inline pre_expr
289 expression_for_id (unsigned int id)
291 return VEC_index (pre_expr, expressions, id);
294 /* Free the expression id field in all of our expressions,
295 and then destroy the expressions array. */
298 clear_expression_ids (void)
300 VEC_free (pre_expr, heap, expressions);
303 static alloc_pool pre_expr_pool;
305 /* Given an SSA_NAME NAME, get or create a pre_expr to represent it. */
308 get_or_alloc_expr_for_name (tree name)
310 pre_expr result = (pre_expr) pool_alloc (pre_expr_pool);
311 unsigned int result_id;
315 PRE_EXPR_NAME (result) = name;
316 result_id = lookup_expression_id (result);
319 pool_free (pre_expr_pool, result);
320 result = expression_for_id (result_id);
323 get_or_alloc_expression_id (result);
327 static bool in_fre = false;
329 /* An unordered bitmap set. One bitmap tracks values, the other,
331 typedef struct bitmap_set
337 #define FOR_EACH_EXPR_ID_IN_SET(set, id, bi) \
338 EXECUTE_IF_SET_IN_BITMAP((set)->expressions, 0, (id), (bi))
340 #define FOR_EACH_VALUE_ID_IN_SET(set, id, bi) \
341 EXECUTE_IF_SET_IN_BITMAP((set)->values, 0, (id), (bi))
343 /* Mapping from value id to expressions with that value_id. */
344 DEF_VEC_P (bitmap_set_t);
345 DEF_VEC_ALLOC_P (bitmap_set_t, heap);
346 static VEC(bitmap_set_t, heap) *value_expressions;
348 /* Sets that we need to keep track of. */
349 typedef struct bb_bitmap_sets
351 /* The EXP_GEN set, which represents expressions/values generated in
353 bitmap_set_t exp_gen;
355 /* The PHI_GEN set, which represents PHI results generated in a
357 bitmap_set_t phi_gen;
359 /* The TMP_GEN set, which represents results/temporaries generated
360 in a basic block. IE the LHS of an expression. */
361 bitmap_set_t tmp_gen;
363 /* The AVAIL_OUT set, which represents which values are available in
364 a given basic block. */
365 bitmap_set_t avail_out;
367 /* The ANTIC_IN set, which represents which values are anticipatable
368 in a given basic block. */
369 bitmap_set_t antic_in;
371 /* The PA_IN set, which represents which values are
372 partially anticipatable in a given basic block. */
375 /* The NEW_SETS set, which is used during insertion to augment the
376 AVAIL_OUT set of blocks with the new insertions performed during
377 the current iteration. */
378 bitmap_set_t new_sets;
380 /* True if we have visited this block during ANTIC calculation. */
381 unsigned int visited:1;
383 /* True we have deferred processing this block during ANTIC
384 calculation until its successor is processed. */
385 unsigned int deferred : 1;
388 #define EXP_GEN(BB) ((bb_value_sets_t) ((BB)->aux))->exp_gen
389 #define PHI_GEN(BB) ((bb_value_sets_t) ((BB)->aux))->phi_gen
390 #define TMP_GEN(BB) ((bb_value_sets_t) ((BB)->aux))->tmp_gen
391 #define AVAIL_OUT(BB) ((bb_value_sets_t) ((BB)->aux))->avail_out
392 #define ANTIC_IN(BB) ((bb_value_sets_t) ((BB)->aux))->antic_in
393 #define PA_IN(BB) ((bb_value_sets_t) ((BB)->aux))->pa_in
394 #define NEW_SETS(BB) ((bb_value_sets_t) ((BB)->aux))->new_sets
395 #define BB_VISITED(BB) ((bb_value_sets_t) ((BB)->aux))->visited
396 #define BB_DEFERRED(BB) ((bb_value_sets_t) ((BB)->aux))->deferred
399 /* Maximal set of values, used to initialize the ANTIC problem, which
400 is an intersection problem. */
401 static bitmap_set_t maximal_set;
403 /* Basic block list in postorder. */
404 static int *postorder;
406 /* This structure is used to keep track of statistics on what
407 optimization PRE was able to perform. */
410 /* The number of RHS computations eliminated by PRE. */
413 /* The number of new expressions/temporaries generated by PRE. */
416 /* The number of inserts found due to partial anticipation */
419 /* The number of new PHI nodes added by PRE. */
422 /* The number of values found constant. */
427 static bool do_partial_partial;
428 static pre_expr bitmap_find_leader (bitmap_set_t, unsigned int, gimple);
429 static void bitmap_value_insert_into_set (bitmap_set_t, pre_expr);
430 static void bitmap_value_replace_in_set (bitmap_set_t, pre_expr);
431 static void bitmap_set_copy (bitmap_set_t, bitmap_set_t);
432 static bool bitmap_set_contains_value (bitmap_set_t, unsigned int);
433 static void bitmap_insert_into_set (bitmap_set_t, pre_expr);
434 static void bitmap_insert_into_set_1 (bitmap_set_t, pre_expr, bool);
435 static bitmap_set_t bitmap_set_new (void);
436 static tree create_expression_by_pieces (basic_block, pre_expr, gimple_seq *,
438 static tree find_or_generate_expression (basic_block, pre_expr, gimple_seq *,
440 static unsigned int get_expr_value_id (pre_expr);
442 /* We can add and remove elements and entries to and from sets
443 and hash tables, so we use alloc pools for them. */
445 static alloc_pool bitmap_set_pool;
446 static bitmap_obstack grand_bitmap_obstack;
448 /* To avoid adding 300 temporary variables when we only need one, we
449 only create one temporary variable, on demand, and build ssa names
450 off that. We do have to change the variable if the types don't
451 match the current variable's type. */
453 static tree storetemp;
454 static tree prephitemp;
456 /* Set of blocks with statements that have had its EH information
458 static bitmap need_eh_cleanup;
460 /* Which expressions have been seen during a given phi translation. */
461 static bitmap seen_during_translate;
463 /* The phi_translate_table caches phi translations for a given
464 expression and predecessor. */
466 static htab_t phi_translate_table;
468 /* A three tuple {e, pred, v} used to cache phi translations in the
469 phi_translate_table. */
471 typedef struct expr_pred_trans_d
473 /* The expression. */
476 /* The predecessor block along which we translated the expression. */
479 /* The value that resulted from the translation. */
482 /* The hashcode for the expression, pred pair. This is cached for
485 } *expr_pred_trans_t;
486 typedef const struct expr_pred_trans_d *const_expr_pred_trans_t;
488 /* Return the hash value for a phi translation table entry. */
491 expr_pred_trans_hash (const void *p)
493 const_expr_pred_trans_t const ve = (const_expr_pred_trans_t) p;
497 /* Return true if two phi translation table entries are the same.
498 P1 and P2 should point to the expr_pred_trans_t's to be compared.*/
501 expr_pred_trans_eq (const void *p1, const void *p2)
503 const_expr_pred_trans_t const ve1 = (const_expr_pred_trans_t) p1;
504 const_expr_pred_trans_t const ve2 = (const_expr_pred_trans_t) p2;
505 basic_block b1 = ve1->pred;
506 basic_block b2 = ve2->pred;
508 /* If they are not translations for the same basic block, they can't
512 return pre_expr_eq (ve1->e, ve2->e);
515 /* Search in the phi translation table for the translation of
516 expression E in basic block PRED.
517 Return the translated value, if found, NULL otherwise. */
519 static inline pre_expr
520 phi_trans_lookup (pre_expr e, basic_block pred)
523 struct expr_pred_trans_d ept;
527 ept.hashcode = iterative_hash_hashval_t (pre_expr_hash (e), pred->index);
528 slot = htab_find_slot_with_hash (phi_translate_table, &ept, ept.hashcode,
533 return ((expr_pred_trans_t) *slot)->v;
537 /* Add the tuple mapping from {expression E, basic block PRED} to
538 value V, to the phi translation table. */
541 phi_trans_add (pre_expr e, pre_expr v, basic_block pred)
544 expr_pred_trans_t new_pair = XNEW (struct expr_pred_trans_d);
546 new_pair->pred = pred;
548 new_pair->hashcode = iterative_hash_hashval_t (pre_expr_hash (e),
551 slot = htab_find_slot_with_hash (phi_translate_table, new_pair,
552 new_pair->hashcode, INSERT);
555 *slot = (void *) new_pair;
559 /* Add expression E to the expression set of value id V. */
562 add_to_value (unsigned int v, pre_expr e)
566 gcc_assert (get_expr_value_id (e) == v);
568 if (v >= VEC_length (bitmap_set_t, value_expressions))
570 VEC_safe_grow_cleared (bitmap_set_t, heap, value_expressions,
574 set = VEC_index (bitmap_set_t, value_expressions, v);
577 set = bitmap_set_new ();
578 VEC_replace (bitmap_set_t, value_expressions, v, set);
581 bitmap_insert_into_set_1 (set, e, true);
584 /* Create a new bitmap set and return it. */
587 bitmap_set_new (void)
589 bitmap_set_t ret = (bitmap_set_t) pool_alloc (bitmap_set_pool);
590 ret->expressions = BITMAP_ALLOC (&grand_bitmap_obstack);
591 ret->values = BITMAP_ALLOC (&grand_bitmap_obstack);
595 /* Return the value id for a PRE expression EXPR. */
598 get_expr_value_id (pre_expr expr)
605 id = get_constant_value_id (PRE_EXPR_CONSTANT (expr));
608 id = get_or_alloc_constant_value_id (PRE_EXPR_CONSTANT (expr));
609 add_to_value (id, expr);
614 return VN_INFO (PRE_EXPR_NAME (expr))->value_id;
616 return PRE_EXPR_NARY (expr)->value_id;
618 return PRE_EXPR_REFERENCE (expr)->value_id;
624 /* Remove an expression EXPR from a bitmapped set. */
627 bitmap_remove_from_set (bitmap_set_t set, pre_expr expr)
629 unsigned int val = get_expr_value_id (expr);
630 if (!value_id_constant_p (val))
632 bitmap_clear_bit (set->values, val);
633 bitmap_clear_bit (set->expressions, get_expression_id (expr));
638 bitmap_insert_into_set_1 (bitmap_set_t set, pre_expr expr,
639 bool allow_constants)
641 unsigned int val = get_expr_value_id (expr);
642 if (allow_constants || !value_id_constant_p (val))
644 /* We specifically expect this and only this function to be able to
645 insert constants into a set. */
646 bitmap_set_bit (set->values, val);
647 bitmap_set_bit (set->expressions, get_or_alloc_expression_id (expr));
651 /* Insert an expression EXPR into a bitmapped set. */
654 bitmap_insert_into_set (bitmap_set_t set, pre_expr expr)
656 bitmap_insert_into_set_1 (set, expr, false);
659 /* Copy a bitmapped set ORIG, into bitmapped set DEST. */
662 bitmap_set_copy (bitmap_set_t dest, bitmap_set_t orig)
664 bitmap_copy (dest->expressions, orig->expressions);
665 bitmap_copy (dest->values, orig->values);
669 /* Free memory used up by SET. */
671 bitmap_set_free (bitmap_set_t set)
673 BITMAP_FREE (set->expressions);
674 BITMAP_FREE (set->values);
678 /* Generate an topological-ordered array of bitmap set SET. */
680 static VEC(pre_expr, heap) *
681 sorted_array_from_bitmap_set (bitmap_set_t set)
684 bitmap_iterator bi, bj;
685 VEC(pre_expr, heap) *result = NULL;
687 FOR_EACH_VALUE_ID_IN_SET (set, i, bi)
689 /* The number of expressions having a given value is usually
690 relatively small. Thus, rather than making a vector of all
691 the expressions and sorting it by value-id, we walk the values
692 and check in the reverse mapping that tells us what expressions
693 have a given value, to filter those in our set. As a result,
694 the expressions are inserted in value-id order, which means
697 If this is somehow a significant lose for some cases, we can
698 choose which set to walk based on the set size. */
699 bitmap_set_t exprset = VEC_index (bitmap_set_t, value_expressions, i);
700 FOR_EACH_EXPR_ID_IN_SET (exprset, j, bj)
702 if (bitmap_bit_p (set->expressions, j))
703 VEC_safe_push (pre_expr, heap, result, expression_for_id (j));
710 /* Perform bitmapped set operation DEST &= ORIG. */
713 bitmap_set_and (bitmap_set_t dest, bitmap_set_t orig)
720 bitmap temp = BITMAP_ALLOC (&grand_bitmap_obstack);
722 bitmap_and_into (dest->values, orig->values);
723 bitmap_copy (temp, dest->expressions);
724 EXECUTE_IF_SET_IN_BITMAP (temp, 0, i, bi)
726 pre_expr expr = expression_for_id (i);
727 unsigned int value_id = get_expr_value_id (expr);
728 if (!bitmap_bit_p (dest->values, value_id))
729 bitmap_clear_bit (dest->expressions, i);
735 /* Subtract all values and expressions contained in ORIG from DEST. */
738 bitmap_set_subtract (bitmap_set_t dest, bitmap_set_t orig)
740 bitmap_set_t result = bitmap_set_new ();
744 bitmap_and_compl (result->expressions, dest->expressions,
747 FOR_EACH_EXPR_ID_IN_SET (result, i, bi)
749 pre_expr expr = expression_for_id (i);
750 unsigned int value_id = get_expr_value_id (expr);
751 bitmap_set_bit (result->values, value_id);
757 /* Subtract all the values in bitmap set B from bitmap set A. */
760 bitmap_set_subtract_values (bitmap_set_t a, bitmap_set_t b)
764 bitmap temp = BITMAP_ALLOC (&grand_bitmap_obstack);
766 bitmap_copy (temp, a->expressions);
767 EXECUTE_IF_SET_IN_BITMAP (temp, 0, i, bi)
769 pre_expr expr = expression_for_id (i);
770 if (bitmap_set_contains_value (b, get_expr_value_id (expr)))
771 bitmap_remove_from_set (a, expr);
777 /* Return true if bitmapped set SET contains the value VALUE_ID. */
780 bitmap_set_contains_value (bitmap_set_t set, unsigned int value_id)
782 if (value_id_constant_p (value_id))
785 if (!set || bitmap_empty_p (set->expressions))
788 return bitmap_bit_p (set->values, value_id);
792 bitmap_set_contains_expr (bitmap_set_t set, const pre_expr expr)
794 return bitmap_bit_p (set->expressions, get_expression_id (expr));
797 /* Replace an instance of value LOOKFOR with expression EXPR in SET. */
800 bitmap_set_replace_value (bitmap_set_t set, unsigned int lookfor,
803 bitmap_set_t exprset;
807 if (value_id_constant_p (lookfor))
810 if (!bitmap_set_contains_value (set, lookfor))
813 /* The number of expressions having a given value is usually
814 significantly less than the total number of expressions in SET.
815 Thus, rather than check, for each expression in SET, whether it
816 has the value LOOKFOR, we walk the reverse mapping that tells us
817 what expressions have a given value, and see if any of those
818 expressions are in our set. For large testcases, this is about
819 5-10x faster than walking the bitmap. If this is somehow a
820 significant lose for some cases, we can choose which set to walk
821 based on the set size. */
822 exprset = VEC_index (bitmap_set_t, value_expressions, lookfor);
823 FOR_EACH_EXPR_ID_IN_SET (exprset, i, bi)
825 if (bitmap_bit_p (set->expressions, i))
827 bitmap_clear_bit (set->expressions, i);
828 bitmap_set_bit (set->expressions, get_expression_id (expr));
834 /* Return true if two bitmap sets are equal. */
837 bitmap_set_equal (bitmap_set_t a, bitmap_set_t b)
839 return bitmap_equal_p (a->values, b->values);
842 /* Replace an instance of EXPR's VALUE with EXPR in SET if it exists,
843 and add it otherwise. */
846 bitmap_value_replace_in_set (bitmap_set_t set, pre_expr expr)
848 unsigned int val = get_expr_value_id (expr);
850 if (bitmap_set_contains_value (set, val))
851 bitmap_set_replace_value (set, val, expr);
853 bitmap_insert_into_set (set, expr);
856 /* Insert EXPR into SET if EXPR's value is not already present in
860 bitmap_value_insert_into_set (bitmap_set_t set, pre_expr expr)
862 unsigned int val = get_expr_value_id (expr);
864 if (value_id_constant_p (val))
867 if (!bitmap_set_contains_value (set, val))
868 bitmap_insert_into_set (set, expr);
871 /* Print out EXPR to outfile. */
874 print_pre_expr (FILE *outfile, const pre_expr expr)
879 print_generic_expr (outfile, PRE_EXPR_CONSTANT (expr), 0);
882 print_generic_expr (outfile, PRE_EXPR_NAME (expr), 0);
887 vn_nary_op_t nary = PRE_EXPR_NARY (expr);
888 fprintf (outfile, "{%s,", tree_code_name [nary->opcode]);
889 for (i = 0; i < nary->length; i++)
891 print_generic_expr (outfile, nary->op[i], 0);
892 if (i != (unsigned) nary->length - 1)
893 fprintf (outfile, ",");
895 fprintf (outfile, "}");
901 vn_reference_op_t vro;
903 vn_reference_t ref = PRE_EXPR_REFERENCE (expr);
904 fprintf (outfile, "{");
906 VEC_iterate (vn_reference_op_s, ref->operands, i, vro);
909 if (vro->opcode != SSA_NAME
910 && TREE_CODE_CLASS (vro->opcode) != tcc_declaration)
911 fprintf (outfile, "%s ", tree_code_name [vro->opcode]);
915 fprintf (outfile, "<");
916 print_generic_expr (outfile, vro->op0, 0);
919 fprintf (outfile, ",");
920 print_generic_expr (outfile, vro->op1, 0);
923 fprintf (outfile, ">");
925 if (i != VEC_length (vn_reference_op_s, ref->operands) - 1)
926 fprintf (outfile, ",");
928 fprintf (outfile, "}");
933 void debug_pre_expr (pre_expr);
935 /* Like print_pre_expr but always prints to stderr. */
937 debug_pre_expr (pre_expr e)
939 print_pre_expr (stderr, e);
940 fprintf (stderr, "\n");
943 /* Print out SET to OUTFILE. */
946 print_bitmap_set (FILE *outfile, bitmap_set_t set,
947 const char *setname, int blockindex)
949 fprintf (outfile, "%s[%d] := { ", setname, blockindex);
956 FOR_EACH_EXPR_ID_IN_SET (set, i, bi)
958 const pre_expr expr = expression_for_id (i);
961 fprintf (outfile, ", ");
963 print_pre_expr (outfile, expr);
965 fprintf (outfile, " (%04d)", get_expr_value_id (expr));
968 fprintf (outfile, " }\n");
971 void debug_bitmap_set (bitmap_set_t);
974 debug_bitmap_set (bitmap_set_t set)
976 print_bitmap_set (stderr, set, "debug", 0);
979 /* Print out the expressions that have VAL to OUTFILE. */
982 print_value_expressions (FILE *outfile, unsigned int val)
984 bitmap_set_t set = VEC_index (bitmap_set_t, value_expressions, val);
988 sprintf (s, "%04d", val);
989 print_bitmap_set (outfile, set, s, 0);
995 debug_value_expressions (unsigned int val)
997 print_value_expressions (stderr, val);
1000 /* Given a CONSTANT, allocate a new CONSTANT type PRE_EXPR to
1004 get_or_alloc_expr_for_constant (tree constant)
1006 unsigned int result_id;
1007 unsigned int value_id;
1008 pre_expr newexpr = (pre_expr) pool_alloc (pre_expr_pool);
1009 newexpr->kind = CONSTANT;
1010 PRE_EXPR_CONSTANT (newexpr) = constant;
1011 result_id = lookup_expression_id (newexpr);
1014 pool_free (pre_expr_pool, newexpr);
1015 newexpr = expression_for_id (result_id);
1018 value_id = get_or_alloc_constant_value_id (constant);
1019 get_or_alloc_expression_id (newexpr);
1020 add_to_value (value_id, newexpr);
1024 /* Given a value id V, find the actual tree representing the constant
1025 value if there is one, and return it. Return NULL if we can't find
1029 get_constant_for_value_id (unsigned int v)
1031 if (value_id_constant_p (v))
1035 bitmap_set_t exprset = VEC_index (bitmap_set_t, value_expressions, v);
1037 FOR_EACH_EXPR_ID_IN_SET (exprset, i, bi)
1039 pre_expr expr = expression_for_id (i);
1040 if (expr->kind == CONSTANT)
1041 return PRE_EXPR_CONSTANT (expr);
1047 /* Get or allocate a pre_expr for a piece of GIMPLE, and return it.
1048 Currently only supports constants and SSA_NAMES. */
1050 get_or_alloc_expr_for (tree t)
1052 if (TREE_CODE (t) == SSA_NAME)
1053 return get_or_alloc_expr_for_name (t);
1054 else if (is_gimple_min_invariant (t)
1055 || TREE_CODE (t) == EXC_PTR_EXPR
1056 || TREE_CODE (t) == FILTER_EXPR)
1057 return get_or_alloc_expr_for_constant (t);
1060 /* More complex expressions can result from SCCVN expression
1061 simplification that inserts values for them. As they all
1062 do not have VOPs the get handled by the nary ops struct. */
1063 vn_nary_op_t result;
1064 unsigned int result_id;
1065 vn_nary_op_lookup (t, &result);
1068 pre_expr e = (pre_expr) pool_alloc (pre_expr_pool);
1070 PRE_EXPR_NARY (e) = result;
1071 result_id = lookup_expression_id (e);
1074 pool_free (pre_expr_pool, e);
1075 e = expression_for_id (result_id);
1078 alloc_expression_id (e);
1085 /* Return the folded version of T if T, when folded, is a gimple
1086 min_invariant. Otherwise, return T. */
1089 fully_constant_expression (pre_expr e)
1097 vn_nary_op_t nary = PRE_EXPR_NARY (e);
1098 switch (TREE_CODE_CLASS (nary->opcode))
1100 case tcc_expression:
1101 if (nary->opcode == TRUTH_NOT_EXPR)
1103 if (nary->opcode != TRUTH_AND_EXPR
1104 && nary->opcode != TRUTH_OR_EXPR
1105 && nary->opcode != TRUTH_XOR_EXPR)
1109 case tcc_comparison:
1111 /* We have to go from trees to pre exprs to value ids to
1113 tree naryop0 = nary->op[0];
1114 tree naryop1 = nary->op[1];
1116 if (!is_gimple_min_invariant (naryop0))
1118 pre_expr rep0 = get_or_alloc_expr_for (naryop0);
1119 unsigned int vrep0 = get_expr_value_id (rep0);
1120 tree const0 = get_constant_for_value_id (vrep0);
1122 naryop0 = fold_convert (TREE_TYPE (naryop0), const0);
1124 if (!is_gimple_min_invariant (naryop1))
1126 pre_expr rep1 = get_or_alloc_expr_for (naryop1);
1127 unsigned int vrep1 = get_expr_value_id (rep1);
1128 tree const1 = get_constant_for_value_id (vrep1);
1130 naryop1 = fold_convert (TREE_TYPE (naryop1), const1);
1132 result = fold_binary (nary->opcode, nary->type,
1134 if (result && is_gimple_min_invariant (result))
1135 return get_or_alloc_expr_for_constant (result);
1136 /* We might have simplified the expression to a
1137 SSA_NAME for example from x_1 * 1. But we cannot
1138 insert a PHI for x_1 unconditionally as x_1 might
1139 not be available readily. */
1143 if (nary->opcode != REALPART_EXPR
1144 && nary->opcode != IMAGPART_EXPR
1145 && nary->opcode != VIEW_CONVERT_EXPR)
1151 /* We have to go from trees to pre exprs to value ids to
1153 tree naryop0 = nary->op[0];
1154 tree const0, result;
1155 if (is_gimple_min_invariant (naryop0))
1159 pre_expr rep0 = get_or_alloc_expr_for (naryop0);
1160 unsigned int vrep0 = get_expr_value_id (rep0);
1161 const0 = get_constant_for_value_id (vrep0);
1166 tree type1 = TREE_TYPE (nary->op[0]);
1167 const0 = fold_convert (type1, const0);
1168 result = fold_unary (nary->opcode, nary->type, const0);
1170 if (result && is_gimple_min_invariant (result))
1171 return get_or_alloc_expr_for_constant (result);
1180 vn_reference_t ref = PRE_EXPR_REFERENCE (e);
1181 VEC (vn_reference_op_s, heap) *operands = ref->operands;
1182 vn_reference_op_t op;
1184 /* Try to simplify the translated expression if it is
1185 a call to a builtin function with at most two arguments. */
1186 op = VEC_index (vn_reference_op_s, operands, 0);
1187 if (op->opcode == CALL_EXPR
1188 && TREE_CODE (op->op0) == ADDR_EXPR
1189 && TREE_CODE (TREE_OPERAND (op->op0, 0)) == FUNCTION_DECL
1190 && DECL_BUILT_IN (TREE_OPERAND (op->op0, 0))
1191 && VEC_length (vn_reference_op_s, operands) >= 2
1192 && VEC_length (vn_reference_op_s, operands) <= 3)
1194 vn_reference_op_t arg0, arg1 = NULL;
1195 bool anyconst = false;
1196 arg0 = VEC_index (vn_reference_op_s, operands, 1);
1197 if (VEC_length (vn_reference_op_s, operands) > 2)
1198 arg1 = VEC_index (vn_reference_op_s, operands, 2);
1199 if (TREE_CODE_CLASS (arg0->opcode) == tcc_constant
1200 || (arg0->opcode == ADDR_EXPR
1201 && is_gimple_min_invariant (arg0->op0)))
1204 && (TREE_CODE_CLASS (arg1->opcode) == tcc_constant
1205 || (arg1->opcode == ADDR_EXPR
1206 && is_gimple_min_invariant (arg1->op0))))
1210 tree folded = build_call_expr (TREE_OPERAND (op->op0, 0),
1213 arg1 ? arg1->op0 : NULL);
1215 && TREE_CODE (folded) == NOP_EXPR)
1216 folded = TREE_OPERAND (folded, 0);
1218 && is_gimple_min_invariant (folded))
1219 return get_or_alloc_expr_for_constant (folded);
1230 /* Translate the vuses in the VUSES vector backwards through phi nodes
1231 in PHIBLOCK, so that they have the value they would have in
1234 static VEC(tree, gc) *
1235 translate_vuses_through_block (VEC (tree, gc) *vuses,
1236 basic_block phiblock,
1240 VEC(tree, gc) *result = NULL;
1243 for (i = 0; VEC_iterate (tree, vuses, i, oldvuse); i++)
1245 gimple phi = SSA_NAME_DEF_STMT (oldvuse);
1246 if (gimple_code (phi) == GIMPLE_PHI
1247 && gimple_bb (phi) == phiblock)
1249 edge e = find_edge (block, gimple_bb (phi));
1252 tree def = PHI_ARG_DEF (phi, e->dest_idx);
1256 result = VEC_copy (tree, gc, vuses);
1257 VEC_replace (tree, result, i, def);
1263 /* We avoid creating a new copy of the vuses unless something
1264 actually changed, so result can be NULL. */
1267 sort_vuses (result);
1274 /* Like find_leader, but checks for the value existing in SET1 *or*
1275 SET2. This is used to avoid making a set consisting of the union
1276 of PA_IN and ANTIC_IN during insert. */
1278 static inline pre_expr
1279 find_leader_in_sets (unsigned int val, bitmap_set_t set1, bitmap_set_t set2)
1283 result = bitmap_find_leader (set1, val, NULL);
1284 if (!result && set2)
1285 result = bitmap_find_leader (set2, val, NULL);
1289 /* Get the tree type for our PRE expression e. */
1292 get_expr_type (const pre_expr e)
1297 return TREE_TYPE (PRE_EXPR_NAME (e));
1299 return TREE_TYPE (PRE_EXPR_CONSTANT (e));
1302 vn_reference_op_t vro;
1304 gcc_assert (PRE_EXPR_REFERENCE (e)->operands);
1305 vro = VEC_index (vn_reference_op_s,
1306 PRE_EXPR_REFERENCE (e)->operands,
1308 /* We don't store type along with COMPONENT_REF because it is
1309 always the same as FIELD_DECL's type. */
1312 gcc_assert (vro->opcode == COMPONENT_REF);
1313 return TREE_TYPE (vro->op0);
1319 return PRE_EXPR_NARY (e)->type;
1324 /* Get a representative SSA_NAME for a given expression.
1325 Since all of our sub-expressions are treated as values, we require
1326 them to be SSA_NAME's for simplicity.
1327 Prior versions of GVNPRE used to use "value handles" here, so that
1328 an expression would be VH.11 + VH.10 instead of d_3 + e_6. In
1329 either case, the operands are really values (IE we do not expect
1330 them to be usable without finding leaders). */
1333 get_representative_for (const pre_expr e)
1337 unsigned int value_id = get_expr_value_id (e);
1342 return PRE_EXPR_NAME (e);
1344 return PRE_EXPR_CONSTANT (e);
1348 /* Go through all of the expressions representing this value
1349 and pick out an SSA_NAME. */
1352 bitmap_set_t exprs = VEC_index (bitmap_set_t, value_expressions,
1354 FOR_EACH_EXPR_ID_IN_SET (exprs, i, bi)
1356 pre_expr rep = expression_for_id (i);
1357 if (rep->kind == NAME)
1358 return PRE_EXPR_NAME (rep);
1363 /* If we reached here we couldn't find an SSA_NAME. This can
1364 happen when we've discovered a value that has never appeared in
1365 the program as set to an SSA_NAME, most likely as the result of
1370 "Could not find SSA_NAME representative for expression:");
1371 print_pre_expr (dump_file, e);
1372 fprintf (dump_file, "\n");
1375 exprtype = get_expr_type (e);
1377 /* Build and insert the assignment of the end result to the temporary
1378 that we will return. */
1379 if (!pretemp || exprtype != TREE_TYPE (pretemp))
1381 pretemp = create_tmp_var (exprtype, "pretmp");
1382 get_var_ann (pretemp);
1385 name = make_ssa_name (pretemp, gimple_build_nop ());
1386 VN_INFO_GET (name)->value_id = value_id;
1387 if (e->kind == CONSTANT)
1388 VN_INFO (name)->valnum = PRE_EXPR_CONSTANT (e);
1390 VN_INFO (name)->valnum = name;
1392 add_to_value (value_id, get_or_alloc_expr_for_name (name));
1395 fprintf (dump_file, "Created SSA_NAME representative ");
1396 print_generic_expr (dump_file, name, 0);
1397 fprintf (dump_file, " for expression:");
1398 print_pre_expr (dump_file, e);
1399 fprintf (dump_file, "\n");
1408 /* Translate EXPR using phis in PHIBLOCK, so that it has the values of
1409 the phis in PRED. SEEN is a bitmap saying which expression we have
1410 translated since we started translation of the toplevel expression.
1411 Return NULL if we can't find a leader for each part of the
1412 translated expression. */
1415 phi_translate_1 (pre_expr expr, bitmap_set_t set1, bitmap_set_t set2,
1416 basic_block pred, basic_block phiblock, bitmap seen)
1418 pre_expr oldexpr = expr;
1424 if (value_id_constant_p (get_expr_value_id (expr)))
1427 phitrans = phi_trans_lookup (expr, pred);
1431 /* Prevent cycles when we have recursively dependent leaders. This
1432 can only happen when phi translating the maximal set. */
1435 unsigned int expr_id = get_expression_id (expr);
1436 if (bitmap_bit_p (seen, expr_id))
1438 bitmap_set_bit (seen, expr_id);
1443 /* Constants contain no values that need translation. */
1450 bool changed = false;
1451 vn_nary_op_t nary = PRE_EXPR_NARY (expr);
1452 struct vn_nary_op_s newnary;
1453 /* The NARY structure is only guaranteed to have been
1454 allocated to the nary->length operands. */
1455 memcpy (&newnary, nary, (sizeof (struct vn_nary_op_s)
1456 - sizeof (tree) * (4 - nary->length)));
1458 for (i = 0; i < newnary.length; i++)
1460 if (TREE_CODE (newnary.op[i]) != SSA_NAME)
1464 unsigned int op_val_id = VN_INFO (newnary.op[i])->value_id;
1465 pre_expr leader = find_leader_in_sets (op_val_id, set1, set2);
1466 pre_expr result = phi_translate_1 (leader, set1, set2,
1467 pred, phiblock, seen);
1468 if (result && result != leader)
1470 tree name = get_representative_for (result);
1473 newnary.op[i] = name;
1478 changed |= newnary.op[i] != nary->op[i];
1485 tree result = vn_nary_op_lookup_pieces (newnary.length,
1493 unsigned int new_val_id;
1495 expr = (pre_expr) pool_alloc (pre_expr_pool);
1498 if (result && is_gimple_min_invariant (result))
1499 return get_or_alloc_expr_for_constant (result);
1504 PRE_EXPR_NARY (expr) = nary;
1505 constant = fully_constant_expression (expr);
1506 if (constant != expr)
1509 new_val_id = nary->value_id;
1510 get_or_alloc_expression_id (expr);
1514 new_val_id = get_next_value_id ();
1515 VEC_safe_grow_cleared (bitmap_set_t, heap,
1517 get_max_value_id() + 1);
1518 nary = vn_nary_op_insert_pieces (newnary.length,
1525 result, new_val_id);
1526 PRE_EXPR_NARY (expr) = nary;
1527 constant = fully_constant_expression (expr);
1528 if (constant != expr)
1530 get_or_alloc_expression_id (expr);
1532 add_to_value (new_val_id, expr);
1534 phi_trans_add (oldexpr, expr, pred);
1541 vn_reference_t ref = PRE_EXPR_REFERENCE (expr);
1542 VEC (vn_reference_op_s, heap) *operands = ref->operands;
1543 VEC (tree, gc) *vuses = ref->vuses;
1544 VEC (tree, gc) *newvuses = vuses;
1545 VEC (vn_reference_op_s, heap) *newoperands = NULL;
1546 bool changed = false;
1548 vn_reference_op_t operand;
1549 vn_reference_t newref;
1551 for (i = 0; VEC_iterate (vn_reference_op_s, operands, i, operand); i++)
1555 tree oldop0 = operand->op0;
1556 tree oldop1 = operand->op1;
1557 tree oldop2 = operand->op2;
1561 tree type = operand->type;
1562 vn_reference_op_s newop = *operand;
1564 if (op0 && TREE_CODE (op0) == SSA_NAME)
1566 unsigned int op_val_id = VN_INFO (op0)->value_id;
1567 leader = find_leader_in_sets (op_val_id, set1, set2);
1568 opresult = phi_translate_1 (leader, set1, set2,
1569 pred, phiblock, seen);
1570 if (opresult && opresult != leader)
1572 tree name = get_representative_for (opresult);
1580 changed |= op0 != oldop0;
1582 if (op1 && TREE_CODE (op1) == SSA_NAME)
1584 unsigned int op_val_id = VN_INFO (op1)->value_id;
1585 leader = find_leader_in_sets (op_val_id, set1, set2);
1586 opresult = phi_translate_1 (leader, set1, set2,
1587 pred, phiblock, seen);
1588 if (opresult && opresult != leader)
1590 tree name = get_representative_for (opresult);
1598 changed |= op1 != oldop1;
1599 if (op2 && TREE_CODE (op2) == SSA_NAME)
1601 unsigned int op_val_id = VN_INFO (op2)->value_id;
1602 leader = find_leader_in_sets (op_val_id, set1, set2);
1603 opresult = phi_translate_1 (leader, set1, set2,
1604 pred, phiblock, seen);
1605 if (opresult && opresult != leader)
1607 tree name = get_representative_for (opresult);
1615 changed |= op2 != oldop2;
1618 newoperands = VEC_copy (vn_reference_op_s, heap, operands);
1619 /* We may have changed from an SSA_NAME to a constant */
1620 if (newop.opcode == SSA_NAME && TREE_CODE (op0) != SSA_NAME)
1621 newop.opcode = TREE_CODE (op0);
1626 VEC_replace (vn_reference_op_s, newoperands, i, &newop);
1628 if (i != VEC_length (vn_reference_op_s, operands))
1631 VEC_free (vn_reference_op_s, heap, newoperands);
1635 newvuses = translate_vuses_through_block (vuses, phiblock, pred);
1636 changed |= newvuses != vuses;
1640 unsigned int new_val_id;
1643 tree result = vn_reference_lookup_pieces (newvuses,
1647 VEC_free (vn_reference_op_s, heap, newoperands);
1649 if (result && is_gimple_min_invariant (result))
1651 gcc_assert (!newoperands);
1652 return get_or_alloc_expr_for_constant (result);
1655 expr = (pre_expr) pool_alloc (pre_expr_pool);
1656 expr->kind = REFERENCE;
1661 PRE_EXPR_REFERENCE (expr) = newref;
1662 constant = fully_constant_expression (expr);
1663 if (constant != expr)
1666 new_val_id = newref->value_id;
1667 get_or_alloc_expression_id (expr);
1671 new_val_id = get_next_value_id ();
1672 VEC_safe_grow_cleared (bitmap_set_t, heap, value_expressions,
1673 get_max_value_id() + 1);
1674 newref = vn_reference_insert_pieces (newvuses,
1676 result, new_val_id);
1678 PRE_EXPR_REFERENCE (expr) = newref;
1679 constant = fully_constant_expression (expr);
1680 if (constant != expr)
1682 get_or_alloc_expression_id (expr);
1684 add_to_value (new_val_id, expr);
1686 VEC_free (vn_reference_op_s, heap, newoperands);
1687 phi_trans_add (oldexpr, expr, pred);
1697 tree name = PRE_EXPR_NAME (expr);
1699 def_stmt = SSA_NAME_DEF_STMT (name);
1700 if (gimple_code (def_stmt) == GIMPLE_PHI
1701 && gimple_bb (def_stmt) == phiblock)
1706 e = find_edge (pred, gimple_bb (phi));
1709 tree def = PHI_ARG_DEF (phi, e->dest_idx);
1712 if (TREE_CODE (def) == SSA_NAME)
1713 def = VN_INFO (def)->valnum;
1715 /* Handle constant. */
1716 if (is_gimple_min_invariant (def))
1717 return get_or_alloc_expr_for_constant (def);
1719 if (TREE_CODE (def) == SSA_NAME && ssa_undefined_value_p (def))
1722 newexpr = get_or_alloc_expr_for_name (def);
1733 /* Translate EXPR using phis in PHIBLOCK, so that it has the values of
1735 Return NULL if we can't find a leader for each part of the
1736 translated expression. */
1739 phi_translate (pre_expr expr, bitmap_set_t set1, bitmap_set_t set2,
1740 basic_block pred, basic_block phiblock)
1742 bitmap_clear (seen_during_translate);
1743 return phi_translate_1 (expr, set1, set2, pred, phiblock,
1744 seen_during_translate);
1747 /* For each expression in SET, translate the values through phi nodes
1748 in PHIBLOCK using edge PHIBLOCK->PRED, and store the resulting
1749 expressions in DEST. */
1752 phi_translate_set (bitmap_set_t dest, bitmap_set_t set, basic_block pred,
1753 basic_block phiblock)
1755 VEC (pre_expr, heap) *exprs;
1759 if (!phi_nodes (phiblock))
1761 bitmap_set_copy (dest, set);
1765 exprs = sorted_array_from_bitmap_set (set);
1766 for (i = 0; VEC_iterate (pre_expr, exprs, i, expr); i++)
1768 pre_expr translated;
1769 translated = phi_translate (expr, set, NULL, pred, phiblock);
1771 /* Don't add empty translations to the cache */
1773 phi_trans_add (expr, translated, pred);
1775 if (translated != NULL)
1776 bitmap_value_insert_into_set (dest, translated);
1778 VEC_free (pre_expr, heap, exprs);
1781 /* Find the leader for a value (i.e., the name representing that
1782 value) in a given set, and return it. If STMT is non-NULL it
1783 makes sure the defining statement for the leader dominates it.
1784 Return NULL if no leader is found. */
1787 bitmap_find_leader (bitmap_set_t set, unsigned int val, gimple stmt)
1789 if (value_id_constant_p (val))
1793 bitmap_set_t exprset = VEC_index (bitmap_set_t, value_expressions, val);
1795 FOR_EACH_EXPR_ID_IN_SET (exprset, i, bi)
1797 pre_expr expr = expression_for_id (i);
1798 if (expr->kind == CONSTANT)
1802 if (bitmap_set_contains_value (set, val))
1804 /* Rather than walk the entire bitmap of expressions, and see
1805 whether any of them has the value we are looking for, we look
1806 at the reverse mapping, which tells us the set of expressions
1807 that have a given value (IE value->expressions with that
1808 value) and see if any of those expressions are in our set.
1809 The number of expressions per value is usually significantly
1810 less than the number of expressions in the set. In fact, for
1811 large testcases, doing it this way is roughly 5-10x faster
1812 than walking the bitmap.
1813 If this is somehow a significant lose for some cases, we can
1814 choose which set to walk based on which set is smaller. */
1817 bitmap_set_t exprset = VEC_index (bitmap_set_t, value_expressions, val);
1819 EXECUTE_IF_AND_IN_BITMAP (exprset->expressions,
1820 set->expressions, 0, i, bi)
1822 pre_expr val = expression_for_id (i);
1823 /* At the point where stmt is not null, there should always
1824 be an SSA_NAME first in the list of expressions. */
1827 gimple def_stmt = SSA_NAME_DEF_STMT (PRE_EXPR_NAME (val));
1828 if (gimple_code (def_stmt) != GIMPLE_PHI
1829 && gimple_bb (def_stmt) == gimple_bb (stmt)
1830 && gimple_uid (def_stmt) >= gimple_uid (stmt))
1839 /* Determine if EXPR, a memory expression, is ANTIC_IN at the top of
1840 BLOCK by seeing if it is not killed in the block. Note that we are
1841 only determining whether there is a store that kills it. Because
1842 of the order in which clean iterates over values, we are guaranteed
1843 that altered operands will have caused us to be eliminated from the
1844 ANTIC_IN set already. */
1847 value_dies_in_block_x (pre_expr expr, basic_block block)
1851 VEC (tree, gc) *vuses = PRE_EXPR_REFERENCE (expr)->vuses;
1853 /* Conservatively, a value dies if it's vuses are defined in this
1854 block, unless they come from phi nodes (which are merge operations,
1855 rather than stores. */
1856 for (i = 0; VEC_iterate (tree, vuses, i, vuse); i++)
1858 gimple def = SSA_NAME_DEF_STMT (vuse);
1860 if (gimple_bb (def) != block)
1862 if (gimple_code (def) == GIMPLE_PHI)
1870 #define union_contains_value(SET1, SET2, VAL) \
1871 (bitmap_set_contains_value ((SET1), (VAL)) \
1872 || ((SET2) && bitmap_set_contains_value ((SET2), (VAL))))
1874 /* Determine if vn_reference_op_t VRO is legal in SET1 U SET2.
1877 vro_valid_in_sets (bitmap_set_t set1, bitmap_set_t set2,
1878 vn_reference_op_t vro)
1880 if (vro->op0 && TREE_CODE (vro->op0) == SSA_NAME)
1882 struct pre_expr_d temp;
1885 PRE_EXPR_NAME (&temp) = vro->op0;
1886 temp.id = lookup_expression_id (&temp);
1889 if (!union_contains_value (set1, set2,
1890 get_expr_value_id (&temp)))
1893 if (vro->op1 && TREE_CODE (vro->op1) == SSA_NAME)
1895 struct pre_expr_d temp;
1898 PRE_EXPR_NAME (&temp) = vro->op1;
1899 temp.id = lookup_expression_id (&temp);
1902 if (!union_contains_value (set1, set2,
1903 get_expr_value_id (&temp)))
1907 if (vro->op2 && TREE_CODE (vro->op2) == SSA_NAME)
1909 struct pre_expr_d temp;
1912 PRE_EXPR_NAME (&temp) = vro->op2;
1913 temp.id = lookup_expression_id (&temp);
1916 if (!union_contains_value (set1, set2,
1917 get_expr_value_id (&temp)))
1924 /* Determine if the expression EXPR is valid in SET1 U SET2.
1925 ONLY SET2 CAN BE NULL.
1926 This means that we have a leader for each part of the expression
1927 (if it consists of values), or the expression is an SSA_NAME.
1928 For loads/calls, we also see if the vuses are killed in this block.
1932 valid_in_sets (bitmap_set_t set1, bitmap_set_t set2, pre_expr expr,
1938 return bitmap_set_contains_expr (AVAIL_OUT (block), expr);
1942 vn_nary_op_t nary = PRE_EXPR_NARY (expr);
1943 for (i = 0; i < nary->length; i++)
1945 if (TREE_CODE (nary->op[i]) == SSA_NAME)
1947 struct pre_expr_d temp;
1950 PRE_EXPR_NAME (&temp) = nary->op[i];
1951 temp.id = lookup_expression_id (&temp);
1954 if (!union_contains_value (set1, set2,
1955 get_expr_value_id (&temp)))
1964 vn_reference_t ref = PRE_EXPR_REFERENCE (expr);
1965 vn_reference_op_t vro;
1968 for (i = 0; VEC_iterate (vn_reference_op_s, ref->operands, i, vro); i++)
1970 if (!vro_valid_in_sets (set1, set2, vro))
1973 return !value_dies_in_block_x (expr, block);
1980 /* Clean the set of expressions that are no longer valid in SET1 or
1981 SET2. This means expressions that are made up of values we have no
1982 leaders for in SET1 or SET2. This version is used for partial
1983 anticipation, which means it is not valid in either ANTIC_IN or
1987 dependent_clean (bitmap_set_t set1, bitmap_set_t set2, basic_block block)
1989 VEC (pre_expr, heap) *exprs = sorted_array_from_bitmap_set (set1);
1993 for (i = 0; VEC_iterate (pre_expr, exprs, i, expr); i++)
1995 if (!valid_in_sets (set1, set2, expr, block))
1996 bitmap_remove_from_set (set1, expr);
1998 VEC_free (pre_expr, heap, exprs);
2001 /* Clean the set of expressions that are no longer valid in SET. This
2002 means expressions that are made up of values we have no leaders for
2006 clean (bitmap_set_t set, basic_block block)
2008 VEC (pre_expr, heap) *exprs = sorted_array_from_bitmap_set (set);
2012 for (i = 0; VEC_iterate (pre_expr, exprs, i, expr); i++)
2014 if (!valid_in_sets (set, NULL, expr, block))
2015 bitmap_remove_from_set (set, expr);
2017 VEC_free (pre_expr, heap, exprs);
2020 static sbitmap has_abnormal_preds;
2022 /* List of blocks that may have changed during ANTIC computation and
2023 thus need to be iterated over. */
2025 static sbitmap changed_blocks;
2027 /* Decide whether to defer a block for a later iteration, or PHI
2028 translate SOURCE to DEST using phis in PHIBLOCK. Return false if we
2029 should defer the block, and true if we processed it. */
2032 defer_or_phi_translate_block (bitmap_set_t dest, bitmap_set_t source,
2033 basic_block block, basic_block phiblock)
2035 if (!BB_VISITED (phiblock))
2037 SET_BIT (changed_blocks, block->index);
2038 BB_VISITED (block) = 0;
2039 BB_DEFERRED (block) = 1;
2043 phi_translate_set (dest, source, block, phiblock);
2047 /* Compute the ANTIC set for BLOCK.
2049 If succs(BLOCK) > 1 then
2050 ANTIC_OUT[BLOCK] = intersection of ANTIC_IN[b] for all succ(BLOCK)
2051 else if succs(BLOCK) == 1 then
2052 ANTIC_OUT[BLOCK] = phi_translate (ANTIC_IN[succ(BLOCK)])
2054 ANTIC_IN[BLOCK] = clean(ANTIC_OUT[BLOCK] U EXP_GEN[BLOCK] - TMP_GEN[BLOCK])
2058 compute_antic_aux (basic_block block, bool block_has_abnormal_pred_edge)
2060 bool changed = false;
2061 bitmap_set_t S, old, ANTIC_OUT;
2067 old = ANTIC_OUT = S = NULL;
2068 BB_VISITED (block) = 1;
2070 /* If any edges from predecessors are abnormal, antic_in is empty,
2072 if (block_has_abnormal_pred_edge)
2073 goto maybe_dump_sets;
2075 old = ANTIC_IN (block);
2076 ANTIC_OUT = bitmap_set_new ();
2078 /* If the block has no successors, ANTIC_OUT is empty. */
2079 if (EDGE_COUNT (block->succs) == 0)
2081 /* If we have one successor, we could have some phi nodes to
2082 translate through. */
2083 else if (single_succ_p (block))
2085 basic_block succ_bb = single_succ (block);
2087 /* We trade iterations of the dataflow equations for having to
2088 phi translate the maximal set, which is incredibly slow
2089 (since the maximal set often has 300+ members, even when you
2090 have a small number of blocks).
2091 Basically, we defer the computation of ANTIC for this block
2092 until we have processed it's successor, which will inevitably
2093 have a *much* smaller set of values to phi translate once
2094 clean has been run on it.
2095 The cost of doing this is that we technically perform more
2096 iterations, however, they are lower cost iterations.
2098 Timings for PRE on tramp3d-v4:
2099 without maximal set fix: 11 seconds
2100 with maximal set fix/without deferring: 26 seconds
2101 with maximal set fix/with deferring: 11 seconds
2104 if (!defer_or_phi_translate_block (ANTIC_OUT, ANTIC_IN (succ_bb),
2108 goto maybe_dump_sets;
2111 /* If we have multiple successors, we take the intersection of all of
2112 them. Note that in the case of loop exit phi nodes, we may have
2113 phis to translate through. */
2116 VEC(basic_block, heap) * worklist;
2118 basic_block bprime, first;
2120 worklist = VEC_alloc (basic_block, heap, EDGE_COUNT (block->succs));
2121 FOR_EACH_EDGE (e, ei, block->succs)
2122 VEC_quick_push (basic_block, worklist, e->dest);
2123 first = VEC_index (basic_block, worklist, 0);
2125 if (phi_nodes (first))
2127 bitmap_set_t from = ANTIC_IN (first);
2129 if (!BB_VISITED (first))
2131 phi_translate_set (ANTIC_OUT, from, block, first);
2135 if (!BB_VISITED (first))
2136 bitmap_set_copy (ANTIC_OUT, maximal_set);
2138 bitmap_set_copy (ANTIC_OUT, ANTIC_IN (first));
2141 for (i = 1; VEC_iterate (basic_block, worklist, i, bprime); i++)
2143 if (phi_nodes (bprime))
2145 bitmap_set_t tmp = bitmap_set_new ();
2146 bitmap_set_t from = ANTIC_IN (bprime);
2148 if (!BB_VISITED (bprime))
2150 phi_translate_set (tmp, from, block, bprime);
2151 bitmap_set_and (ANTIC_OUT, tmp);
2152 bitmap_set_free (tmp);
2156 if (!BB_VISITED (bprime))
2157 bitmap_set_and (ANTIC_OUT, maximal_set);
2159 bitmap_set_and (ANTIC_OUT, ANTIC_IN (bprime));
2162 VEC_free (basic_block, heap, worklist);
2165 /* Generate ANTIC_OUT - TMP_GEN. */
2166 S = bitmap_set_subtract (ANTIC_OUT, TMP_GEN (block));
2168 /* Start ANTIC_IN with EXP_GEN - TMP_GEN. */
2169 ANTIC_IN (block) = bitmap_set_subtract (EXP_GEN (block),
2172 /* Then union in the ANTIC_OUT - TMP_GEN values,
2173 to get ANTIC_OUT U EXP_GEN - TMP_GEN */
2174 FOR_EACH_EXPR_ID_IN_SET (S, bii, bi)
2175 bitmap_value_insert_into_set (ANTIC_IN (block),
2176 expression_for_id (bii));
2178 clean (ANTIC_IN (block), block);
2180 /* !old->expressions can happen when we deferred a block. */
2181 if (!old->expressions || !bitmap_set_equal (old, ANTIC_IN (block)))
2184 SET_BIT (changed_blocks, block->index);
2185 FOR_EACH_EDGE (e, ei, block->preds)
2186 SET_BIT (changed_blocks, e->src->index);
2189 RESET_BIT (changed_blocks, block->index);
2192 if (dump_file && (dump_flags & TDF_DETAILS))
2194 if (!BB_DEFERRED (block) || BB_VISITED (block))
2197 print_bitmap_set (dump_file, ANTIC_OUT, "ANTIC_OUT", block->index);
2199 print_bitmap_set (dump_file, ANTIC_IN (block), "ANTIC_IN",
2203 print_bitmap_set (dump_file, S, "S", block->index);
2208 "Block %d was deferred for a future iteration.\n",
2213 bitmap_set_free (old);
2215 bitmap_set_free (S);
2217 bitmap_set_free (ANTIC_OUT);
2221 /* Compute PARTIAL_ANTIC for BLOCK.
2223 If succs(BLOCK) > 1 then
2224 PA_OUT[BLOCK] = value wise union of PA_IN[b] + all ANTIC_IN not
2225 in ANTIC_OUT for all succ(BLOCK)
2226 else if succs(BLOCK) == 1 then
2227 PA_OUT[BLOCK] = phi_translate (PA_IN[succ(BLOCK)])
2229 PA_IN[BLOCK] = dependent_clean(PA_OUT[BLOCK] - TMP_GEN[BLOCK]
2234 compute_partial_antic_aux (basic_block block,
2235 bool block_has_abnormal_pred_edge)
2237 bool changed = false;
2238 bitmap_set_t old_PA_IN;
2239 bitmap_set_t PA_OUT;
2242 unsigned long max_pa = PARAM_VALUE (PARAM_MAX_PARTIAL_ANTIC_LENGTH);
2244 old_PA_IN = PA_OUT = NULL;
2246 /* If any edges from predecessors are abnormal, antic_in is empty,
2248 if (block_has_abnormal_pred_edge)
2249 goto maybe_dump_sets;
2251 /* If there are too many partially anticipatable values in the
2252 block, phi_translate_set can take an exponential time: stop
2253 before the translation starts. */
2255 && single_succ_p (block)
2256 && bitmap_count_bits (PA_IN (single_succ (block))->values) > max_pa)
2257 goto maybe_dump_sets;
2259 old_PA_IN = PA_IN (block);
2260 PA_OUT = bitmap_set_new ();
2262 /* If the block has no successors, ANTIC_OUT is empty. */
2263 if (EDGE_COUNT (block->succs) == 0)
2265 /* If we have one successor, we could have some phi nodes to
2266 translate through. Note that we can't phi translate across DFS
2267 back edges in partial antic, because it uses a union operation on
2268 the successors. For recurrences like IV's, we will end up
2269 generating a new value in the set on each go around (i + 3 (VH.1)
2270 VH.1 + 1 (VH.2), VH.2 + 1 (VH.3), etc), forever. */
2271 else if (single_succ_p (block))
2273 basic_block succ = single_succ (block);
2274 if (!(single_succ_edge (block)->flags & EDGE_DFS_BACK))
2275 phi_translate_set (PA_OUT, PA_IN (succ), block, succ);
2277 /* If we have multiple successors, we take the union of all of
2281 VEC(basic_block, heap) * worklist;
2285 worklist = VEC_alloc (basic_block, heap, EDGE_COUNT (block->succs));
2286 FOR_EACH_EDGE (e, ei, block->succs)
2288 if (e->flags & EDGE_DFS_BACK)
2290 VEC_quick_push (basic_block, worklist, e->dest);
2292 if (VEC_length (basic_block, worklist) > 0)
2294 for (i = 0; VEC_iterate (basic_block, worklist, i, bprime); i++)
2299 FOR_EACH_EXPR_ID_IN_SET (ANTIC_IN (bprime), i, bi)
2300 bitmap_value_insert_into_set (PA_OUT,
2301 expression_for_id (i));
2302 if (phi_nodes (bprime))
2304 bitmap_set_t pa_in = bitmap_set_new ();
2305 phi_translate_set (pa_in, PA_IN (bprime), block, bprime);
2306 FOR_EACH_EXPR_ID_IN_SET (pa_in, i, bi)
2307 bitmap_value_insert_into_set (PA_OUT,
2308 expression_for_id (i));
2309 bitmap_set_free (pa_in);
2312 FOR_EACH_EXPR_ID_IN_SET (PA_IN (bprime), i, bi)
2313 bitmap_value_insert_into_set (PA_OUT,
2314 expression_for_id (i));
2317 VEC_free (basic_block, heap, worklist);
2320 /* PA_IN starts with PA_OUT - TMP_GEN.
2321 Then we subtract things from ANTIC_IN. */
2322 PA_IN (block) = bitmap_set_subtract (PA_OUT, TMP_GEN (block));
2324 /* For partial antic, we want to put back in the phi results, since
2325 we will properly avoid making them partially antic over backedges. */
2326 bitmap_ior_into (PA_IN (block)->values, PHI_GEN (block)->values);
2327 bitmap_ior_into (PA_IN (block)->expressions, PHI_GEN (block)->expressions);
2329 /* PA_IN[block] = PA_IN[block] - ANTIC_IN[block] */
2330 bitmap_set_subtract_values (PA_IN (block), ANTIC_IN (block));
2332 dependent_clean (PA_IN (block), ANTIC_IN (block), block);
2334 if (!bitmap_set_equal (old_PA_IN, PA_IN (block)))
2337 SET_BIT (changed_blocks, block->index);
2338 FOR_EACH_EDGE (e, ei, block->preds)
2339 SET_BIT (changed_blocks, e->src->index);
2342 RESET_BIT (changed_blocks, block->index);
2345 if (dump_file && (dump_flags & TDF_DETAILS))
2348 print_bitmap_set (dump_file, PA_OUT, "PA_OUT", block->index);
2350 print_bitmap_set (dump_file, PA_IN (block), "PA_IN", block->index);
2353 bitmap_set_free (old_PA_IN);
2355 bitmap_set_free (PA_OUT);
2359 /* Compute ANTIC and partial ANTIC sets. */
2362 compute_antic (void)
2364 bool changed = true;
2365 int num_iterations = 0;
2369 /* If any predecessor edges are abnormal, we punt, so antic_in is empty.
2370 We pre-build the map of blocks with incoming abnormal edges here. */
2371 has_abnormal_preds = sbitmap_alloc (last_basic_block);
2372 sbitmap_zero (has_abnormal_preds);
2379 FOR_EACH_EDGE (e, ei, block->preds)
2381 e->flags &= ~EDGE_DFS_BACK;
2382 if (e->flags & EDGE_ABNORMAL)
2384 SET_BIT (has_abnormal_preds, block->index);
2389 BB_VISITED (block) = 0;
2390 BB_DEFERRED (block) = 0;
2391 /* While we are here, give empty ANTIC_IN sets to each block. */
2392 ANTIC_IN (block) = bitmap_set_new ();
2393 PA_IN (block) = bitmap_set_new ();
2396 /* At the exit block we anticipate nothing. */
2397 ANTIC_IN (EXIT_BLOCK_PTR) = bitmap_set_new ();
2398 BB_VISITED (EXIT_BLOCK_PTR) = 1;
2399 PA_IN (EXIT_BLOCK_PTR) = bitmap_set_new ();
2401 changed_blocks = sbitmap_alloc (last_basic_block + 1);
2402 sbitmap_ones (changed_blocks);
2405 if (dump_file && (dump_flags & TDF_DETAILS))
2406 fprintf (dump_file, "Starting iteration %d\n", num_iterations);
2409 for (i = 0; i < n_basic_blocks - NUM_FIXED_BLOCKS; i++)
2411 if (TEST_BIT (changed_blocks, postorder[i]))
2413 basic_block block = BASIC_BLOCK (postorder[i]);
2414 changed |= compute_antic_aux (block,
2415 TEST_BIT (has_abnormal_preds,
2419 #ifdef ENABLE_CHECKING
2420 /* Theoretically possible, but *highly* unlikely. */
2421 gcc_assert (num_iterations < 500);
2425 statistics_histogram_event (cfun, "compute_antic iterations",
2428 if (do_partial_partial)
2430 sbitmap_ones (changed_blocks);
2431 mark_dfs_back_edges ();
2436 if (dump_file && (dump_flags & TDF_DETAILS))
2437 fprintf (dump_file, "Starting iteration %d\n", num_iterations);
2440 for (i = 0; i < n_basic_blocks - NUM_FIXED_BLOCKS; i++)
2442 if (TEST_BIT (changed_blocks, postorder[i]))
2444 basic_block block = BASIC_BLOCK (postorder[i]);
2446 |= compute_partial_antic_aux (block,
2447 TEST_BIT (has_abnormal_preds,
2451 #ifdef ENABLE_CHECKING
2452 /* Theoretically possible, but *highly* unlikely. */
2453 gcc_assert (num_iterations < 500);
2456 statistics_histogram_event (cfun, "compute_partial_antic iterations",
2459 sbitmap_free (has_abnormal_preds);
2460 sbitmap_free (changed_blocks);
2463 /* Return true if we can value number the call in STMT. This is true
2464 if we have a pure or constant call. */
2467 can_value_number_call (gimple stmt)
2469 if (gimple_call_flags (stmt) & (ECF_PURE | ECF_CONST))
2474 /* Return true if OP is an exception handler related operation, such as
2475 FILTER_EXPR or EXC_PTR_EXPR. */
2478 is_exception_related (gimple stmt)
2480 return (is_gimple_assign (stmt)
2481 && (gimple_assign_rhs_code (stmt) == FILTER_EXPR
2482 || gimple_assign_rhs_code (stmt) == EXC_PTR_EXPR));
2485 /* Return true if OP is a tree which we can perform PRE on
2486 on. This may not match the operations we can value number, but in
2487 a perfect world would. */
2490 can_PRE_operation (tree op)
2492 return UNARY_CLASS_P (op)
2493 || BINARY_CLASS_P (op)
2494 || COMPARISON_CLASS_P (op)
2495 || TREE_CODE (op) == INDIRECT_REF
2496 || TREE_CODE (op) == COMPONENT_REF
2497 || TREE_CODE (op) == VIEW_CONVERT_EXPR
2498 || TREE_CODE (op) == CALL_EXPR
2499 || TREE_CODE (op) == ARRAY_REF;
2503 /* Inserted expressions are placed onto this worklist, which is used
2504 for performing quick dead code elimination of insertions we made
2505 that didn't turn out to be necessary. */
2506 static VEC(gimple,heap) *inserted_exprs;
2508 /* Pool allocated fake store expressions are placed onto this
2509 worklist, which, after performing dead code elimination, is walked
2510 to see which expressions need to be put into GC'able memory */
2511 static VEC(gimple, heap) *need_creation;
2513 /* The actual worker for create_component_ref_by_pieces. */
2516 create_component_ref_by_pieces_1 (basic_block block, vn_reference_t ref,
2517 unsigned int *operand, gimple_seq *stmts,
2520 vn_reference_op_t currop = VEC_index (vn_reference_op_s, ref->operands,
2524 switch (currop->opcode)
2528 tree folded, sc = currop->op1;
2529 unsigned int nargs = 0;
2530 tree *args = XNEWVEC (tree, VEC_length (vn_reference_op_s,
2531 ref->operands) - 1);
2532 while (*operand < VEC_length (vn_reference_op_s, ref->operands))
2534 args[nargs] = create_component_ref_by_pieces_1 (block, ref,
2539 folded = build_call_array (currop->type,
2540 TREE_CODE (currop->op0) == FUNCTION_DECL
2541 ? build_fold_addr_expr (currop->op0)
2547 pre_expr scexpr = get_or_alloc_expr_for (sc);
2548 sc = find_or_generate_expression (block, scexpr, stmts, domstmt);
2551 CALL_EXPR_STATIC_CHAIN (folded) = sc;
2559 gcc_assert (is_gimple_min_invariant (currop->op0));
2565 case VIEW_CONVERT_EXPR:
2568 tree genop0 = create_component_ref_by_pieces_1 (block, ref,
2573 folded = fold_build1 (currop->opcode, currop->type,
2578 case ALIGN_INDIRECT_REF:
2579 case MISALIGNED_INDIRECT_REF:
2583 tree genop1 = create_component_ref_by_pieces_1 (block, ref,
2588 genop1 = fold_convert (build_pointer_type (currop->type),
2591 if (currop->opcode == MISALIGNED_INDIRECT_REF)
2592 folded = fold_build2 (currop->opcode, currop->type,
2593 genop1, currop->op1);
2595 folded = fold_build1 (currop->opcode, currop->type,
2603 tree genop0 = create_component_ref_by_pieces_1 (block, ref, operand,
2605 pre_expr op1expr = get_or_alloc_expr_for (currop->op0);
2606 pre_expr op2expr = get_or_alloc_expr_for (currop->op1);
2612 genop1 = find_or_generate_expression (block, op1expr, stmts, domstmt);
2615 genop2 = find_or_generate_expression (block, op2expr, stmts, domstmt);
2618 folded = fold_build3 (BIT_FIELD_REF, currop->type, genop0, genop1,
2623 /* For array ref vn_reference_op's, operand 1 of the array ref
2624 is op0 of the reference op and operand 3 of the array ref is
2626 case ARRAY_RANGE_REF:
2630 tree genop1 = currop->op0;
2632 tree genop2 = currop->op1;
2635 genop0 = create_component_ref_by_pieces_1 (block, ref, operand,
2639 op1expr = get_or_alloc_expr_for (genop1);
2640 genop1 = find_or_generate_expression (block, op1expr, stmts, domstmt);
2645 op2expr = get_or_alloc_expr_for (genop2);
2646 genop2 = find_or_generate_expression (block, op2expr, stmts,
2652 genop3 = currop->op2;
2653 return build4 (currop->opcode, currop->type, genop0, genop1,
2660 tree genop2 = currop->op1;
2662 op0 = create_component_ref_by_pieces_1 (block, ref, operand,
2666 /* op1 should be a FIELD_DECL, which are represented by
2671 op2expr = get_or_alloc_expr_for (genop2);
2672 genop2 = find_or_generate_expression (block, op2expr, stmts,
2678 return fold_build3 (COMPONENT_REF, TREE_TYPE (op1), op0, op1,
2684 pre_expr op0expr = get_or_alloc_expr_for (currop->op0);
2685 genop = find_or_generate_expression (block, op0expr, stmts, domstmt);
2706 /* For COMPONENT_REF's and ARRAY_REF's, we can't have any intermediates for the
2707 COMPONENT_REF or INDIRECT_REF or ARRAY_REF portion, because we'd end up with
2708 trying to rename aggregates into ssa form directly, which is a no no.
2710 Thus, this routine doesn't create temporaries, it just builds a
2711 single access expression for the array, calling
2712 find_or_generate_expression to build the innermost pieces.
2714 This function is a subroutine of create_expression_by_pieces, and
2715 should not be called on it's own unless you really know what you
2719 create_component_ref_by_pieces (basic_block block, vn_reference_t ref,
2720 gimple_seq *stmts, gimple domstmt)
2722 unsigned int op = 0;
2723 return create_component_ref_by_pieces_1 (block, ref, &op, stmts, domstmt);
2726 /* Find a leader for an expression, or generate one using
2727 create_expression_by_pieces if it's ANTIC but
2729 BLOCK is the basic_block we are looking for leaders in.
2730 EXPR is the expression to find a leader or generate for.
2731 STMTS is the statement list to put the inserted expressions on.
2732 Returns the SSA_NAME of the LHS of the generated expression or the
2734 DOMSTMT if non-NULL is a statement that should be dominated by
2735 all uses in the generated expression. If DOMSTMT is non-NULL this
2736 routine can fail and return NULL_TREE. Otherwise it will assert
2740 find_or_generate_expression (basic_block block, pre_expr expr,
2741 gimple_seq *stmts, gimple domstmt)
2743 pre_expr leader = bitmap_find_leader (AVAIL_OUT (block),
2744 get_expr_value_id (expr), domstmt);
2748 if (leader->kind == NAME)
2749 genop = PRE_EXPR_NAME (leader);
2750 else if (leader->kind == CONSTANT)
2751 genop = PRE_EXPR_CONSTANT (leader);
2754 /* If it's still NULL, it must be a complex expression, so generate
2755 it recursively. Not so for FRE though. */
2759 bitmap_set_t exprset;
2760 unsigned int lookfor = get_expr_value_id (expr);
2761 bool handled = false;
2765 exprset = VEC_index (bitmap_set_t, value_expressions, lookfor);
2766 FOR_EACH_EXPR_ID_IN_SET (exprset, i, bi)
2768 pre_expr temp = expression_for_id (i);
2769 if (temp->kind != NAME)
2772 genop = create_expression_by_pieces (block, temp, stmts,
2774 get_expr_type (expr));
2778 if (!handled && domstmt)
2781 gcc_assert (handled);
2786 #define NECESSARY GF_PLF_1
2788 /* Create an expression in pieces, so that we can handle very complex
2789 expressions that may be ANTIC, but not necessary GIMPLE.
2790 BLOCK is the basic block the expression will be inserted into,
2791 EXPR is the expression to insert (in value form)
2792 STMTS is a statement list to append the necessary insertions into.
2794 This function will die if we hit some value that shouldn't be
2795 ANTIC but is (IE there is no leader for it, or its components).
2796 This function may also generate expressions that are themselves
2797 partially or fully redundant. Those that are will be either made
2798 fully redundant during the next iteration of insert (for partially
2799 redundant ones), or eliminated by eliminate (for fully redundant
2802 If DOMSTMT is non-NULL then we make sure that all uses in the
2803 expressions dominate that statement. In this case the function
2804 can return NULL_TREE to signal failure. */
2807 create_expression_by_pieces (basic_block block, pre_expr expr,
2808 gimple_seq *stmts, gimple domstmt, tree type)
2811 tree folded, newexpr;
2812 gimple_seq forced_stmts;
2813 unsigned int value_id;
2814 gimple_stmt_iterator gsi;
2815 tree exprtype = type ? type : get_expr_type (expr);
2821 /* We may hit the NAME/CONSTANT case if we have to convert types
2822 that value numbering saw through. */
2824 folded = PRE_EXPR_NAME (expr);
2827 folded = PRE_EXPR_CONSTANT (expr);
2831 vn_reference_t ref = PRE_EXPR_REFERENCE (expr);
2832 folded = create_component_ref_by_pieces (block, ref, stmts, domstmt);
2837 vn_nary_op_t nary = PRE_EXPR_NARY (expr);
2838 switch (nary->length)
2842 pre_expr op1 = get_or_alloc_expr_for (nary->op[0]);
2843 pre_expr op2 = get_or_alloc_expr_for (nary->op[1]);
2844 tree genop1 = find_or_generate_expression (block, op1,
2846 tree genop2 = find_or_generate_expression (block, op2,
2848 if (!genop1 || !genop2)
2850 genop1 = fold_convert (TREE_TYPE (nary->op[0]),
2852 /* Ensure op2 is a sizetype for POINTER_PLUS_EXPR. It
2853 may be a constant with the wrong type. */
2854 if (nary->opcode == POINTER_PLUS_EXPR)
2855 genop2 = fold_convert (sizetype, genop2);
2857 genop2 = fold_convert (TREE_TYPE (nary->op[1]), genop2);
2859 folded = fold_build2 (nary->opcode, nary->type,
2865 pre_expr op1 = get_or_alloc_expr_for (nary->op[0]);
2866 tree genop1 = find_or_generate_expression (block, op1,
2870 genop1 = fold_convert (TREE_TYPE (nary->op[0]), genop1);
2872 folded = fold_build1 (nary->opcode, nary->type,
2884 folded = fold_convert (exprtype, folded);
2885 /* Force the generated expression to be a sequence of GIMPLE
2887 We have to call unshare_expr because force_gimple_operand may
2888 modify the tree we pass to it. */
2889 newexpr = force_gimple_operand (unshare_expr (folded), &forced_stmts,
2892 /* If we have any intermediate expressions to the value sets, add them
2893 to the value sets and chain them in the instruction stream. */
2896 gsi = gsi_start (forced_stmts);
2897 for (; !gsi_end_p (gsi); gsi_next (&gsi))
2899 gimple stmt = gsi_stmt (gsi);
2900 tree forcedname = gimple_get_lhs (stmt);
2903 VEC_safe_push (gimple, heap, inserted_exprs, stmt);
2904 if (TREE_CODE (forcedname) == SSA_NAME)
2906 VN_INFO_GET (forcedname)->valnum = forcedname;
2907 VN_INFO (forcedname)->value_id = get_next_value_id ();
2908 nameexpr = get_or_alloc_expr_for_name (forcedname);
2909 add_to_value (VN_INFO (forcedname)->value_id, nameexpr);
2911 bitmap_value_replace_in_set (NEW_SETS (block), nameexpr);
2912 bitmap_value_replace_in_set (AVAIL_OUT (block), nameexpr);
2914 mark_symbols_for_renaming (stmt);
2916 gimple_seq_add_seq (stmts, forced_stmts);
2919 /* Build and insert the assignment of the end result to the temporary
2920 that we will return. */
2921 if (!pretemp || exprtype != TREE_TYPE (pretemp))
2923 pretemp = create_tmp_var (exprtype, "pretmp");
2924 get_var_ann (pretemp);
2928 add_referenced_var (temp);
2930 if (TREE_CODE (exprtype) == COMPLEX_TYPE
2931 || TREE_CODE (exprtype) == VECTOR_TYPE)
2932 DECL_GIMPLE_REG_P (temp) = 1;
2934 newstmt = gimple_build_assign (temp, newexpr);
2935 name = make_ssa_name (temp, newstmt);
2936 gimple_assign_set_lhs (newstmt, name);
2937 gimple_set_plf (newstmt, NECESSARY, false);
2939 gimple_seq_add_stmt (stmts, newstmt);
2940 VEC_safe_push (gimple, heap, inserted_exprs, newstmt);
2942 /* All the symbols in NEWEXPR should be put into SSA form. */
2943 mark_symbols_for_renaming (newstmt);
2945 /* Add a value number to the temporary.
2946 The value may already exist in either NEW_SETS, or AVAIL_OUT, because
2947 we are creating the expression by pieces, and this particular piece of
2948 the expression may have been represented. There is no harm in replacing
2950 VN_INFO_GET (name)->valnum = name;
2951 value_id = get_expr_value_id (expr);
2952 VN_INFO (name)->value_id = value_id;
2953 nameexpr = get_or_alloc_expr_for_name (name);
2954 add_to_value (value_id, nameexpr);
2956 bitmap_value_replace_in_set (NEW_SETS (block), nameexpr);
2957 bitmap_value_replace_in_set (AVAIL_OUT (block), nameexpr);
2959 pre_stats.insertions++;
2960 if (dump_file && (dump_flags & TDF_DETAILS))
2962 fprintf (dump_file, "Inserted ");
2963 print_gimple_stmt (dump_file, newstmt, 0, 0);
2964 fprintf (dump_file, " in predecessor %d\n", block->index);
2971 /* Insert the to-be-made-available values of expression EXPRNUM for each
2972 predecessor, stored in AVAIL, into the predecessors of BLOCK, and
2973 merge the result with a phi node, given the same value number as
2974 NODE. Return true if we have inserted new stuff. */
2977 insert_into_preds_of_block (basic_block block, unsigned int exprnum,
2980 pre_expr expr = expression_for_id (exprnum);
2982 unsigned int val = get_expr_value_id (expr);
2984 bool insertions = false;
2989 tree type = get_expr_type (expr);
2993 if (dump_file && (dump_flags & TDF_DETAILS))
2995 fprintf (dump_file, "Found partial redundancy for expression ");
2996 print_pre_expr (dump_file, expr);
2997 fprintf (dump_file, " (%04d)\n", val);
3000 /* Make sure we aren't creating an induction variable. */
3001 if (block->loop_depth > 0 && EDGE_COUNT (block->preds) == 2
3002 && expr->kind != REFERENCE)
3004 bool firstinsideloop = false;
3005 bool secondinsideloop = false;
3006 firstinsideloop = flow_bb_inside_loop_p (block->loop_father,
3007 EDGE_PRED (block, 0)->src);
3008 secondinsideloop = flow_bb_inside_loop_p (block->loop_father,
3009 EDGE_PRED (block, 1)->src);
3010 /* Induction variables only have one edge inside the loop. */
3011 if (firstinsideloop ^ secondinsideloop)
3013 if (dump_file && (dump_flags & TDF_DETAILS))
3014 fprintf (dump_file, "Skipping insertion of phi for partial redundancy: Looks like an induction variable\n");
3019 /* Make sure we are not inserting trapping expressions. */
3020 FOR_EACH_EDGE (pred, ei, block->preds)
3023 eprime = avail[bprime->index];
3024 if (eprime->kind == NARY
3025 && vn_nary_may_trap (PRE_EXPR_NARY (eprime)))
3029 /* Make the necessary insertions. */
3030 FOR_EACH_EDGE (pred, ei, block->preds)
3032 gimple_seq stmts = NULL;
3035 eprime = avail[bprime->index];
3037 if (eprime->kind != NAME && eprime->kind != CONSTANT)
3039 builtexpr = create_expression_by_pieces (bprime,
3043 gcc_assert (!(pred->flags & EDGE_ABNORMAL));
3044 gsi_insert_seq_on_edge (pred, stmts);
3045 avail[bprime->index] = get_or_alloc_expr_for_name (builtexpr);
3048 else if (eprime->kind == CONSTANT)
3050 /* Constants may not have the right type, fold_convert
3051 should give us back a constant with the right type.
3053 tree constant = PRE_EXPR_CONSTANT (eprime);
3054 if (!useless_type_conversion_p (type, TREE_TYPE (constant)))
3056 tree builtexpr = fold_convert (type, constant);
3057 if (!is_gimple_min_invariant (builtexpr))
3059 tree forcedexpr = force_gimple_operand (builtexpr,
3062 if (!is_gimple_min_invariant (forcedexpr))
3064 if (forcedexpr != builtexpr)
3066 VN_INFO_GET (forcedexpr)->valnum = PRE_EXPR_CONSTANT (eprime);
3067 VN_INFO (forcedexpr)->value_id = get_expr_value_id (eprime);
3071 gimple_stmt_iterator gsi;
3072 gsi = gsi_start (stmts);
3073 for (; !gsi_end_p (gsi); gsi_next (&gsi))
3075 gimple stmt = gsi_stmt (gsi);
3076 VEC_safe_push (gimple, heap, inserted_exprs, stmt);
3077 gimple_set_plf (stmt, NECESSARY, false);
3079 gsi_insert_seq_on_edge (pred, stmts);
3081 avail[bprime->index] = get_or_alloc_expr_for_name (forcedexpr);
3086 else if (eprime->kind == NAME)
3088 /* We may have to do a conversion because our value
3089 numbering can look through types in certain cases, but
3090 our IL requires all operands of a phi node have the same
3092 tree name = PRE_EXPR_NAME (eprime);
3093 if (!useless_type_conversion_p (type, TREE_TYPE (name)))
3097 builtexpr = fold_convert (type, name);
3098 forcedexpr = force_gimple_operand (builtexpr,
3102 if (forcedexpr != name)
3104 VN_INFO_GET (forcedexpr)->valnum = VN_INFO (name)->valnum;
3105 VN_INFO (forcedexpr)->value_id = VN_INFO (name)->value_id;
3110 gimple_stmt_iterator gsi;
3111 gsi = gsi_start (stmts);
3112 for (; !gsi_end_p (gsi); gsi_next (&gsi))
3114 gimple stmt = gsi_stmt (gsi);
3115 VEC_safe_push (gimple, heap, inserted_exprs, stmt);
3116 gimple_set_plf (stmt, NECESSARY, false);
3118 gsi_insert_seq_on_edge (pred, stmts);
3120 avail[bprime->index] = get_or_alloc_expr_for_name (forcedexpr);
3124 /* If we didn't want a phi node, and we made insertions, we still have
3125 inserted new stuff, and thus return true. If we didn't want a phi node,
3126 and didn't make insertions, we haven't added anything new, so return
3128 if (nophi && insertions)
3130 else if (nophi && !insertions)
3133 /* Now build a phi for the new variable. */
3134 if (!prephitemp || TREE_TYPE (prephitemp) != type)
3136 prephitemp = create_tmp_var (type, "prephitmp");
3137 get_var_ann (prephitemp);
3141 add_referenced_var (temp);
3143 if (TREE_CODE (type) == COMPLEX_TYPE
3144 || TREE_CODE (type) == VECTOR_TYPE)
3145 DECL_GIMPLE_REG_P (temp) = 1;
3146 phi = create_phi_node (temp, block);
3148 gimple_set_plf (phi, NECESSARY, false);
3149 VN_INFO_GET (gimple_phi_result (phi))->valnum = gimple_phi_result (phi);
3150 VN_INFO (gimple_phi_result (phi))->value_id = val;
3151 VEC_safe_push (gimple, heap, inserted_exprs, phi);
3152 FOR_EACH_EDGE (pred, ei, block->preds)
3154 pre_expr ae = avail[pred->src->index];
3155 gcc_assert (get_expr_type (ae) == type
3156 || useless_type_conversion_p (type, get_expr_type (ae)));
3157 if (ae->kind == CONSTANT)
3158 add_phi_arg (phi, PRE_EXPR_CONSTANT (ae), pred);
3160 add_phi_arg (phi, PRE_EXPR_NAME (avail[pred->src->index]), pred);
3163 newphi = get_or_alloc_expr_for_name (gimple_phi_result (phi));
3164 add_to_value (val, newphi);
3166 /* The value should *not* exist in PHI_GEN, or else we wouldn't be doing
3167 this insertion, since we test for the existence of this value in PHI_GEN
3168 before proceeding with the partial redundancy checks in insert_aux.
3170 The value may exist in AVAIL_OUT, in particular, it could be represented
3171 by the expression we are trying to eliminate, in which case we want the
3172 replacement to occur. If it's not existing in AVAIL_OUT, we want it
3175 Similarly, to the PHI_GEN case, the value should not exist in NEW_SETS of
3176 this block, because if it did, it would have existed in our dominator's
3177 AVAIL_OUT, and would have been skipped due to the full redundancy check.
3180 bitmap_insert_into_set (PHI_GEN (block), newphi);
3181 bitmap_value_replace_in_set (AVAIL_OUT (block),
3183 bitmap_insert_into_set (NEW_SETS (block),
3186 if (dump_file && (dump_flags & TDF_DETAILS))
3188 fprintf (dump_file, "Created phi ");
3189 print_gimple_stmt (dump_file, phi, 0, 0);
3190 fprintf (dump_file, " in block %d\n", block->index);
3198 /* Perform insertion of partially redundant values.
3199 For BLOCK, do the following:
3200 1. Propagate the NEW_SETS of the dominator into the current block.
3201 If the block has multiple predecessors,
3202 2a. Iterate over the ANTIC expressions for the block to see if
3203 any of them are partially redundant.
3204 2b. If so, insert them into the necessary predecessors to make
3205 the expression fully redundant.
3206 2c. Insert a new PHI merging the values of the predecessors.
3207 2d. Insert the new PHI, and the new expressions, into the
3209 3. Recursively call ourselves on the dominator children of BLOCK.
3211 Steps 1, 2a, and 3 are done by insert_aux. 2b, 2c and 2d are done by
3212 do_regular_insertion and do_partial_insertion.
3217 do_regular_insertion (basic_block block, basic_block dom)
3219 bool new_stuff = false;
3220 VEC (pre_expr, heap) *exprs = sorted_array_from_bitmap_set (ANTIC_IN (block));
3224 for (i = 0; VEC_iterate (pre_expr, exprs, i, expr); i++)
3226 if (expr->kind != NAME)
3230 bool by_some = false;
3231 bool cant_insert = false;
3232 bool all_same = true;
3233 pre_expr first_s = NULL;
3236 pre_expr eprime = NULL;
3238 pre_expr edoubleprime = NULL;
3240 val = get_expr_value_id (expr);
3241 if (bitmap_set_contains_value (PHI_GEN (block), val))
3243 if (bitmap_set_contains_value (AVAIL_OUT (dom), val))
3245 if (dump_file && (dump_flags & TDF_DETAILS))
3246 fprintf (dump_file, "Found fully redundant value\n");
3250 avail = XCNEWVEC (pre_expr, last_basic_block);
3251 FOR_EACH_EDGE (pred, ei, block->preds)
3253 unsigned int vprime;
3255 /* We should never run insertion for the exit block
3256 and so not come across fake pred edges. */
3257 gcc_assert (!(pred->flags & EDGE_FAKE));
3259 eprime = phi_translate (expr, ANTIC_IN (block), NULL,
3262 /* eprime will generally only be NULL if the
3263 value of the expression, translated
3264 through the PHI for this predecessor, is
3265 undefined. If that is the case, we can't
3266 make the expression fully redundant,
3267 because its value is undefined along a
3268 predecessor path. We can thus break out
3269 early because it doesn't matter what the
3270 rest of the results are. */
3277 eprime = fully_constant_expression (eprime);
3278 vprime = get_expr_value_id (eprime);
3279 edoubleprime = bitmap_find_leader (AVAIL_OUT (bprime),
3281 if (edoubleprime == NULL)
3283 avail[bprime->index] = eprime;
3288 avail[bprime->index] = edoubleprime;
3290 if (first_s == NULL)
3291 first_s = edoubleprime;
3292 else if (!pre_expr_eq (first_s, edoubleprime))
3296 /* If we can insert it, it's not the same value
3297 already existing along every predecessor, and
3298 it's defined by some predecessor, it is
3299 partially redundant. */
3300 if (!cant_insert && !all_same && by_some && dbg_cnt (treepre_insert))
3302 if (insert_into_preds_of_block (block, get_expression_id (expr),
3306 /* If all edges produce the same value and that value is
3307 an invariant, then the PHI has the same value on all
3308 edges. Note this. */
3309 else if (!cant_insert && all_same && eprime
3310 && (edoubleprime->kind == CONSTANT
3311 || edoubleprime->kind == NAME)
3312 && !value_id_constant_p (val))
3316 bitmap_set_t exprset = VEC_index (bitmap_set_t,
3317 value_expressions, val);
3319 unsigned int new_val = get_expr_value_id (edoubleprime);
3320 FOR_EACH_EXPR_ID_IN_SET (exprset, j, bi)
3322 pre_expr expr = expression_for_id (j);
3324 if (expr->kind == NAME)
3326 vn_ssa_aux_t info = VN_INFO (PRE_EXPR_NAME (expr));
3327 /* Just reset the value id and valnum so it is
3328 the same as the constant we have discovered. */
3329 if (edoubleprime->kind == CONSTANT)
3331 info->valnum = PRE_EXPR_CONSTANT (edoubleprime);
3332 pre_stats.constified++;
3335 info->valnum = VN_INFO (PRE_EXPR_NAME (edoubleprime))->valnum;
3336 info->value_id = new_val;
3344 VEC_free (pre_expr, heap, exprs);
3349 /* Perform insertion for partially anticipatable expressions. There
3350 is only one case we will perform insertion for these. This case is
3351 if the expression is partially anticipatable, and fully available.
3352 In this case, we know that putting it earlier will enable us to
3353 remove the later computation. */
3357 do_partial_partial_insertion (basic_block block, basic_block dom)
3359 bool new_stuff = false;
3360 VEC (pre_expr, heap) *exprs = sorted_array_from_bitmap_set (PA_IN (block));
3364 for (i = 0; VEC_iterate (pre_expr, exprs, i, expr); i++)
3366 if (expr->kind != NAME)
3371 bool cant_insert = false;
3374 pre_expr eprime = NULL;
3377 val = get_expr_value_id (expr);
3378 if (bitmap_set_contains_value (PHI_GEN (block), val))
3380 if (bitmap_set_contains_value (AVAIL_OUT (dom), val))
3383 avail = XCNEWVEC (pre_expr, last_basic_block);
3384 FOR_EACH_EDGE (pred, ei, block->preds)
3386 unsigned int vprime;
3387 pre_expr edoubleprime;
3389 /* We should never run insertion for the exit block
3390 and so not come across fake pred edges. */
3391 gcc_assert (!(pred->flags & EDGE_FAKE));
3393 eprime = phi_translate (expr, ANTIC_IN (block),
3397 /* eprime will generally only be NULL if the
3398 value of the expression, translated
3399 through the PHI for this predecessor, is
3400 undefined. If that is the case, we can't
3401 make the expression fully redundant,
3402 because its value is undefined along a
3403 predecessor path. We can thus break out
3404 early because it doesn't matter what the
3405 rest of the results are. */
3412 eprime = fully_constant_expression (eprime);
3413 vprime = get_expr_value_id (eprime);
3414 edoubleprime = bitmap_find_leader (AVAIL_OUT (bprime),
3416 if (edoubleprime == NULL)
3422 avail[bprime->index] = edoubleprime;
3426 /* If we can insert it, it's not the same value
3427 already existing along every predecessor, and
3428 it's defined by some predecessor, it is
3429 partially redundant. */
3430 if (!cant_insert && by_all && dbg_cnt (treepre_insert))
3432 pre_stats.pa_insert++;
3433 if (insert_into_preds_of_block (block, get_expression_id (expr),
3441 VEC_free (pre_expr, heap, exprs);
3446 insert_aux (basic_block block)
3449 bool new_stuff = false;
3454 dom = get_immediate_dominator (CDI_DOMINATORS, block);
3459 bitmap_set_t newset = NEW_SETS (dom);
3462 /* Note that we need to value_replace both NEW_SETS, and
3463 AVAIL_OUT. For both the case of NEW_SETS, the value may be
3464 represented by some non-simple expression here that we want
3465 to replace it with. */
3466 FOR_EACH_EXPR_ID_IN_SET (newset, i, bi)
3468 pre_expr expr = expression_for_id (i);
3469 bitmap_value_replace_in_set (NEW_SETS (block), expr);
3470 bitmap_value_replace_in_set (AVAIL_OUT (block), expr);
3473 if (!single_pred_p (block))
3475 new_stuff |= do_regular_insertion (block, dom);
3476 if (do_partial_partial)
3477 new_stuff |= do_partial_partial_insertion (block, dom);
3481 for (son = first_dom_son (CDI_DOMINATORS, block);
3483 son = next_dom_son (CDI_DOMINATORS, son))
3485 new_stuff |= insert_aux (son);
3491 /* Perform insertion of partially redundant values. */
3496 bool new_stuff = true;
3498 int num_iterations = 0;
3501 NEW_SETS (bb) = bitmap_set_new ();
3506 new_stuff = insert_aux (ENTRY_BLOCK_PTR);
3508 statistics_histogram_event (cfun, "insert iterations", num_iterations);
3512 /* Add OP to EXP_GEN (block), and possibly to the maximal set if it is
3513 not defined by a phi node.
3514 PHI nodes can't go in the maximal sets because they are not in
3515 TMP_GEN, so it is possible to get into non-monotonic situations
3516 during ANTIC calculation, because it will *add* bits. */
3519 add_to_exp_gen (basic_block block, tree op)
3524 if (TREE_CODE (op) == SSA_NAME && ssa_undefined_value_p (op))
3526 result = get_or_alloc_expr_for_name (op);
3527 bitmap_value_insert_into_set (EXP_GEN (block), result);
3528 if (TREE_CODE (op) != SSA_NAME
3529 || gimple_code (SSA_NAME_DEF_STMT (op)) != GIMPLE_PHI)
3530 bitmap_value_insert_into_set (maximal_set, result);
3534 /* Create value ids for PHI in BLOCK. */
3537 make_values_for_phi (gimple phi, basic_block block)
3539 tree result = gimple_phi_result (phi);
3541 /* We have no need for virtual phis, as they don't represent
3542 actual computations. */
3543 if (is_gimple_reg (result))
3545 pre_expr e = get_or_alloc_expr_for_name (result);
3546 add_to_value (get_expr_value_id (e), e);
3547 bitmap_insert_into_set (PHI_GEN (block), e);
3548 bitmap_value_insert_into_set (AVAIL_OUT (block), e);
3552 /* Compute the AVAIL set for all basic blocks.
3554 This function performs value numbering of the statements in each basic
3555 block. The AVAIL sets are built from information we glean while doing
3556 this value numbering, since the AVAIL sets contain only one entry per
3559 AVAIL_IN[BLOCK] = AVAIL_OUT[dom(BLOCK)].
3560 AVAIL_OUT[BLOCK] = AVAIL_IN[BLOCK] U PHI_GEN[BLOCK] U TMP_GEN[BLOCK]. */
3563 compute_avail (void)
3566 basic_block block, son;
3567 basic_block *worklist;
3571 /* We pretend that default definitions are defined in the entry block.
3572 This includes function arguments and the static chain decl. */
3573 for (i = 1; i < num_ssa_names; ++i)
3575 tree name = ssa_name (i);
3578 || !SSA_NAME_IS_DEFAULT_DEF (name)
3579 || has_zero_uses (name)
3580 || !is_gimple_reg (name))
3583 e = get_or_alloc_expr_for_name (name);
3584 add_to_value (get_expr_value_id (e), e);
3587 bitmap_insert_into_set (TMP_GEN (ENTRY_BLOCK_PTR), e);
3588 bitmap_value_insert_into_set (maximal_set, e);
3590 bitmap_value_insert_into_set (AVAIL_OUT (ENTRY_BLOCK_PTR), e);
3593 /* Allocate the worklist. */
3594 worklist = XNEWVEC (basic_block, n_basic_blocks);
3596 /* Seed the algorithm by putting the dominator children of the entry
3597 block on the worklist. */
3598 for (son = first_dom_son (CDI_DOMINATORS, ENTRY_BLOCK_PTR);
3600 son = next_dom_son (CDI_DOMINATORS, son))
3601 worklist[sp++] = son;
3603 /* Loop until the worklist is empty. */
3606 gimple_stmt_iterator gsi;
3609 unsigned int stmt_uid = 1;
3611 /* Pick a block from the worklist. */
3612 block = worklist[--sp];
3614 /* Initially, the set of available values in BLOCK is that of
3615 its immediate dominator. */
3616 dom = get_immediate_dominator (CDI_DOMINATORS, block);
3618 bitmap_set_copy (AVAIL_OUT (block), AVAIL_OUT (dom));
3620 /* Generate values for PHI nodes. */
3621 for (gsi = gsi_start_phis (block); !gsi_end_p (gsi); gsi_next (&gsi))
3622 make_values_for_phi (gsi_stmt (gsi), block);
3624 /* Now compute value numbers and populate value sets with all
3625 the expressions computed in BLOCK. */
3626 for (gsi = gsi_start_bb (block); !gsi_end_p (gsi); gsi_next (&gsi))
3631 stmt = gsi_stmt (gsi);
3632 gimple_set_uid (stmt, stmt_uid++);
3634 FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_DEF)
3636 pre_expr e = get_or_alloc_expr_for_name (op);
3638 add_to_value (get_expr_value_id (e), e);
3640 bitmap_insert_into_set (TMP_GEN (block), e);
3641 bitmap_value_insert_into_set (AVAIL_OUT (block), e);
3644 if (gimple_has_volatile_ops (stmt)
3645 || stmt_could_throw_p (stmt))
3648 switch (gimple_code (stmt))
3651 FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_USE)
3652 add_to_exp_gen (block, op);
3659 vn_reference_op_t vro;
3660 pre_expr result = NULL;
3661 VEC(vn_reference_op_s, heap) *ops = NULL;
3663 if (!can_value_number_call (stmt))
3666 copy_reference_ops_from_call (stmt, &ops);
3667 vn_reference_lookup_pieces (shared_vuses_from_stmt (stmt),
3669 VEC_free (vn_reference_op_s, heap, ops);
3673 for (i = 0; VEC_iterate (vn_reference_op_s,
3677 if (vro->op0 && TREE_CODE (vro->op0) == SSA_NAME)
3678 add_to_exp_gen (block, vro->op0);
3679 if (vro->op1 && TREE_CODE (vro->op1) == SSA_NAME)
3680 add_to_exp_gen (block, vro->op1);
3681 if (vro->op2 && TREE_CODE (vro->op2) == SSA_NAME)
3682 add_to_exp_gen (block, vro->op2);
3684 result = (pre_expr) pool_alloc (pre_expr_pool);
3685 result->kind = REFERENCE;
3687 PRE_EXPR_REFERENCE (result) = ref;
3689 get_or_alloc_expression_id (result);
3690 add_to_value (get_expr_value_id (result), result);
3693 bitmap_value_insert_into_set (EXP_GEN (block),
3695 bitmap_value_insert_into_set (maximal_set, result);
3702 pre_expr result = NULL;
3703 switch (TREE_CODE_CLASS (gimple_assign_rhs_code (stmt)))
3706 if (is_exception_related (stmt))
3709 case tcc_comparison:
3714 vn_nary_op_lookup_pieces (gimple_num_ops (stmt) - 1,
3715 gimple_assign_rhs_code (stmt),
3716 gimple_expr_type (stmt),
3717 gimple_assign_rhs1 (stmt),
3718 gimple_assign_rhs2 (stmt),
3719 NULL_TREE, NULL_TREE, &nary);
3724 for (i = 0; i < nary->length; i++)
3725 if (TREE_CODE (nary->op[i]) == SSA_NAME)
3726 add_to_exp_gen (block, nary->op[i]);
3728 result = (pre_expr) pool_alloc (pre_expr_pool);
3729 result->kind = NARY;
3731 PRE_EXPR_NARY (result) = nary;
3735 case tcc_declaration:
3740 vn_reference_op_t vro;
3742 vn_reference_lookup (gimple_assign_rhs1 (stmt),
3743 shared_vuses_from_stmt (stmt),
3748 for (i = 0; VEC_iterate (vn_reference_op_s,
3752 if (vro->op0 && TREE_CODE (vro->op0) == SSA_NAME)
3753 add_to_exp_gen (block, vro->op0);
3754 if (vro->op1 && TREE_CODE (vro->op1) == SSA_NAME)
3755 add_to_exp_gen (block, vro->op1);
3756 if (vro->op2 && TREE_CODE (vro->op2) == SSA_NAME)
3757 add_to_exp_gen (block, vro->op2);
3759 result = (pre_expr) pool_alloc (pre_expr_pool);
3760 result->kind = REFERENCE;
3762 PRE_EXPR_REFERENCE (result) = ref;
3767 /* For any other statement that we don't
3768 recognize, simply add all referenced
3769 SSA_NAMEs to EXP_GEN. */
3770 FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_USE)
3771 add_to_exp_gen (block, op);
3775 get_or_alloc_expression_id (result);
3776 add_to_value (get_expr_value_id (result), result);
3779 bitmap_value_insert_into_set (EXP_GEN (block), result);
3780 bitmap_value_insert_into_set (maximal_set, result);
3790 /* Put the dominator children of BLOCK on the worklist of blocks
3791 to compute available sets for. */
3792 for (son = first_dom_son (CDI_DOMINATORS, block);
3794 son = next_dom_son (CDI_DOMINATORS, son))
3795 worklist[sp++] = son;
3801 /* Insert the expression for SSA_VN that SCCVN thought would be simpler
3802 than the available expressions for it. The insertion point is
3803 right before the first use in STMT. Returns the SSA_NAME that should
3804 be used for replacement. */
3807 do_SCCVN_insertion (gimple stmt, tree ssa_vn)
3809 basic_block bb = gimple_bb (stmt);
3810 gimple_stmt_iterator gsi;
3811 gimple_seq stmts = NULL;
3815 /* First create a value expression from the expression we want
3816 to insert and associate it with the value handle for SSA_VN. */
3817 e = get_or_alloc_expr_for (vn_get_expr_for (ssa_vn));
3821 /* Then use create_expression_by_pieces to generate a valid
3822 expression to insert at this point of the IL stream. */
3823 expr = create_expression_by_pieces (bb, e, &stmts, stmt, NULL);
3824 if (expr == NULL_TREE)
3826 gsi = gsi_for_stmt (stmt);
3827 gsi_insert_seq_before (&gsi, stmts, GSI_SAME_STMT);
3832 /* Eliminate fully redundant computations. */
3838 unsigned int todo = 0;
3842 gimple_stmt_iterator i;
3844 for (i = gsi_start_bb (b); !gsi_end_p (i);)
3846 gimple stmt = gsi_stmt (i);
3848 /* Lookup the RHS of the expression, see if we have an
3849 available computation for it. If so, replace the RHS with
3850 the available computation. */
3851 if (gimple_has_lhs (stmt)
3852 && TREE_CODE (gimple_get_lhs (stmt)) == SSA_NAME
3853 && !gimple_assign_ssa_name_copy_p (stmt)
3854 && (!gimple_assign_single_p (stmt)
3855 || !is_gimple_min_invariant (gimple_assign_rhs1 (stmt)))
3856 && !gimple_has_volatile_ops (stmt)
3857 && !has_zero_uses (gimple_get_lhs (stmt)))
3859 tree lhs = gimple_get_lhs (stmt);
3860 tree rhs = NULL_TREE;
3862 pre_expr lhsexpr = get_or_alloc_expr_for_name (lhs);
3863 pre_expr sprimeexpr;
3865 if (gimple_assign_single_p (stmt))
3866 rhs = gimple_assign_rhs1 (stmt);
3868 sprimeexpr = bitmap_find_leader (AVAIL_OUT (b),
3869 get_expr_value_id (lhsexpr),
3874 if (sprimeexpr->kind == CONSTANT)
3875 sprime = PRE_EXPR_CONSTANT (sprimeexpr);
3876 else if (sprimeexpr->kind == NAME)
3877 sprime = PRE_EXPR_NAME (sprimeexpr);
3882 /* If there is no existing leader but SCCVN knows this
3883 value is constant, use that constant. */
3884 if (!sprime && is_gimple_min_invariant (VN_INFO (lhs)->valnum))
3886 sprime = fold_convert (TREE_TYPE (lhs),
3887 VN_INFO (lhs)->valnum);
3889 if (dump_file && (dump_flags & TDF_DETAILS))
3891 fprintf (dump_file, "Replaced ");
3892 print_gimple_expr (dump_file, stmt, 0, 0);
3893 fprintf (dump_file, " with ");
3894 print_generic_expr (dump_file, sprime, 0);
3895 fprintf (dump_file, " in ");
3896 print_gimple_stmt (dump_file, stmt, 0, 0);
3898 pre_stats.eliminations++;
3899 propagate_tree_value_into_stmt (&i, sprime);
3900 stmt = gsi_stmt (i);
3906 /* If there is no existing usable leader but SCCVN thinks
3907 it has an expression it wants to use as replacement,
3909 if (!sprime || sprime == lhs)
3911 tree val = VN_INFO (lhs)->valnum;
3913 && TREE_CODE (val) == SSA_NAME
3914 && VN_INFO (val)->needs_insertion
3915 && can_PRE_operation (vn_get_expr_for (val)))
3916 sprime = do_SCCVN_insertion (stmt, val);
3920 && (rhs == NULL_TREE
3921 || TREE_CODE (rhs) != SSA_NAME
3922 || may_propagate_copy (rhs, sprime)))
3924 gcc_assert (sprime != rhs);
3926 if (dump_file && (dump_flags & TDF_DETAILS))
3928 fprintf (dump_file, "Replaced ");
3929 print_gimple_expr (dump_file, stmt, 0, 0);
3930 fprintf (dump_file, " with ");
3931 print_generic_expr (dump_file, sprime, 0);
3932 fprintf (dump_file, " in ");
3933 print_gimple_stmt (dump_file, stmt, 0, 0);
3936 if (TREE_CODE (sprime) == SSA_NAME)
3937 gimple_set_plf (SSA_NAME_DEF_STMT (sprime),
3939 /* We need to make sure the new and old types actually match,
3940 which may require adding a simple cast, which fold_convert
3942 if ((!rhs || TREE_CODE (rhs) != SSA_NAME)
3943 && !useless_type_conversion_p (gimple_expr_type (stmt),
3944 TREE_TYPE (sprime)))
3945 sprime = fold_convert (gimple_expr_type (stmt), sprime);
3947 pre_stats.eliminations++;
3948 propagate_tree_value_into_stmt (&i, sprime);
3949 stmt = gsi_stmt (i);
3952 /* If we removed EH side effects from the statement, clean
3953 its EH information. */
3954 if (maybe_clean_or_replace_eh_stmt (stmt, stmt))
3956 bitmap_set_bit (need_eh_cleanup,
3957 gimple_bb (stmt)->index);
3958 if (dump_file && (dump_flags & TDF_DETAILS))
3959 fprintf (dump_file, " Removed EH side effects.\n");
3963 /* If the statement is a scalar store, see if the expression
3964 has the same value number as its rhs. If so, the store is
3966 else if (gimple_assign_single_p (stmt)
3967 && !is_gimple_reg (gimple_assign_lhs (stmt))
3968 && (TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME
3969 || is_gimple_min_invariant (gimple_assign_rhs1 (stmt))))
3971 tree rhs = gimple_assign_rhs1 (stmt);
3973 val = vn_reference_lookup (gimple_assign_lhs (stmt),
3974 shared_vuses_from_stmt (stmt),
3976 if (TREE_CODE (rhs) == SSA_NAME)
3977 rhs = VN_INFO (rhs)->valnum;
3979 && operand_equal_p (val, rhs, 0))
3985 imm_use_iterator ui;
3988 if (dump_file && (dump_flags & TDF_DETAILS))
3990 fprintf (dump_file, "Deleted dead store ");
3991 print_gimple_stmt (dump_file, stmt, 0, 0);
3994 /* Propagate all may-uses to the uses of their defs. */
3995 FOR_EACH_SSA_VDEF_OPERAND (def, usevec, stmt, oi)
3997 tree vuse = VUSE_ELEMENT_VAR (*usevec, 0);
3998 tree vdef = DEF_FROM_PTR (def);
4000 /* If the vdef is used in an abnormal PHI node we
4001 have to propagate that flag to the vuse as well. */
4002 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (vdef))
4003 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (vuse) = 1;
4005 FOR_EACH_IMM_USE_STMT (use_stmt, ui, vdef)
4006 FOR_EACH_IMM_USE_ON_STMT (use, ui)
4007 SET_USE (use, vuse);
4010 gsi_remove (&i, true);
4011 release_defs (stmt);
4015 /* Visit COND_EXPRs and fold the comparison with the
4016 available value-numbers. */
4017 else if (gimple_code (stmt) == GIMPLE_COND)
4019 tree op0 = gimple_cond_lhs (stmt);
4020 tree op1 = gimple_cond_rhs (stmt);
4023 if (TREE_CODE (op0) == SSA_NAME)
4024 op0 = VN_INFO (op0)->valnum;
4025 if (TREE_CODE (op1) == SSA_NAME)
4026 op1 = VN_INFO (op1)->valnum;
4027 result = fold_binary (gimple_cond_code (stmt), boolean_type_node,
4029 if (result && TREE_CODE (result) == INTEGER_CST)
4031 if (integer_zerop (result))
4032 gimple_cond_make_false (stmt);
4034 gimple_cond_make_true (stmt);
4036 todo = TODO_cleanup_cfg;
4047 /* Borrow a bit of tree-ssa-dce.c for the moment.
4048 XXX: In 4.1, we should be able to just run a DCE pass after PRE, though
4049 this may be a bit faster, and we may want critical edges kept split. */
4051 /* If OP's defining statement has not already been determined to be necessary,
4052 mark that statement necessary. Return the stmt, if it is newly
4055 static inline gimple
4056 mark_operand_necessary (tree op)
4062 if (TREE_CODE (op) != SSA_NAME)
4065 stmt = SSA_NAME_DEF_STMT (op);
4068 if (gimple_plf (stmt, NECESSARY)
4069 || gimple_nop_p (stmt))
4072 gimple_set_plf (stmt, NECESSARY, true);
4076 /* Because we don't follow exactly the standard PRE algorithm, and decide not
4077 to insert PHI nodes sometimes, and because value numbering of casts isn't
4078 perfect, we sometimes end up inserting dead code. This simple DCE-like
4079 pass removes any insertions we made that weren't actually used. */
4082 remove_dead_inserted_code (void)
4084 VEC(gimple,heap) *worklist = NULL;
4088 worklist = VEC_alloc (gimple, heap, VEC_length (gimple, inserted_exprs));
4089 for (i = 0; VEC_iterate (gimple, inserted_exprs, i, t); i++)
4091 if (gimple_plf (t, NECESSARY))
4092 VEC_quick_push (gimple, worklist, t);
4094 while (VEC_length (gimple, worklist) > 0)
4096 t = VEC_pop (gimple, worklist);
4098 /* PHI nodes are somewhat special in that each PHI alternative has
4099 data and control dependencies. All the statements feeding the
4100 PHI node's arguments are always necessary. */
4101 if (gimple_code (t) == GIMPLE_PHI)
4105 VEC_reserve (gimple, heap, worklist, gimple_phi_num_args (t));
4106 for (k = 0; k < gimple_phi_num_args (t); k++)
4108 tree arg = PHI_ARG_DEF (t, k);
4109 if (TREE_CODE (arg) == SSA_NAME)
4111 gimple n = mark_operand_necessary (arg);
4113 VEC_quick_push (gimple, worklist, n);
4119 /* Propagate through the operands. Examine all the USE, VUSE and
4120 VDEF operands in this statement. Mark all the statements
4121 which feed this statement's uses as necessary. */
4125 /* The operands of VDEF expressions are also needed as they
4126 represent potential definitions that may reach this
4127 statement (VDEF operands allow us to follow def-def
4130 FOR_EACH_SSA_TREE_OPERAND (use, t, iter, SSA_OP_ALL_USES)
4132 gimple n = mark_operand_necessary (use);
4134 VEC_safe_push (gimple, heap, worklist, n);
4139 for (i = 0; VEC_iterate (gimple, inserted_exprs, i, t); i++)
4141 if (!gimple_plf (t, NECESSARY))
4143 gimple_stmt_iterator gsi;
4145 if (dump_file && (dump_flags & TDF_DETAILS))
4147 fprintf (dump_file, "Removing unnecessary insertion:");
4148 print_gimple_stmt (dump_file, t, 0, 0);
4151 gsi = gsi_for_stmt (t);
4152 if (gimple_code (t) == GIMPLE_PHI)
4153 remove_phi_node (&gsi, true);
4155 gsi_remove (&gsi, true);
4159 VEC_free (gimple, heap, worklist);
4162 /* Initialize data structures used by PRE. */
4165 init_pre (bool do_fre)
4169 next_expression_id = 1;
4171 VEC_safe_push (pre_expr, heap, expressions, NULL);
4172 value_expressions = VEC_alloc (bitmap_set_t, heap, get_max_value_id () + 1);
4173 VEC_safe_grow_cleared (bitmap_set_t, heap, value_expressions,
4174 get_max_value_id() + 1);
4178 inserted_exprs = NULL;
4179 need_creation = NULL;
4180 pretemp = NULL_TREE;
4181 storetemp = NULL_TREE;
4182 prephitemp = NULL_TREE;
4184 connect_infinite_loops_to_exit ();
4185 memset (&pre_stats, 0, sizeof (pre_stats));
4188 postorder = XNEWVEC (int, n_basic_blocks - NUM_FIXED_BLOCKS);
4189 post_order_compute (postorder, false, false);
4192 bb->aux = XCNEWVEC (struct bb_bitmap_sets, 1);
4194 calculate_dominance_info (CDI_POST_DOMINATORS);
4195 calculate_dominance_info (CDI_DOMINATORS);
4197 bitmap_obstack_initialize (&grand_bitmap_obstack);
4198 phi_translate_table = htab_create (5110, expr_pred_trans_hash,
4199 expr_pred_trans_eq, free);
4200 expression_to_id = htab_create (num_ssa_names * 3,
4203 seen_during_translate = BITMAP_ALLOC (&grand_bitmap_obstack);
4204 bitmap_set_pool = create_alloc_pool ("Bitmap sets",
4205 sizeof (struct bitmap_set), 30);
4206 pre_expr_pool = create_alloc_pool ("pre_expr nodes",
4207 sizeof (struct pre_expr_d), 30);
4210 EXP_GEN (bb) = bitmap_set_new ();
4211 PHI_GEN (bb) = bitmap_set_new ();
4212 TMP_GEN (bb) = bitmap_set_new ();
4213 AVAIL_OUT (bb) = bitmap_set_new ();
4215 maximal_set = in_fre ? NULL : bitmap_set_new ();
4217 need_eh_cleanup = BITMAP_ALLOC (NULL);
4221 /* Deallocate data structures used by PRE. */
4224 fini_pre (bool do_fre)
4229 VEC_free (bitmap_set_t, heap, value_expressions);
4230 VEC_free (gimple, heap, inserted_exprs);
4231 VEC_free (gimple, heap, need_creation);
4232 bitmap_obstack_release (&grand_bitmap_obstack);
4233 free_alloc_pool (bitmap_set_pool);
4234 free_alloc_pool (pre_expr_pool);
4235 htab_delete (phi_translate_table);
4236 htab_delete (expression_to_id);
4244 free_dominance_info (CDI_POST_DOMINATORS);
4246 if (!bitmap_empty_p (need_eh_cleanup))
4248 gimple_purge_all_dead_eh_edges (need_eh_cleanup);
4249 cleanup_tree_cfg ();
4252 BITMAP_FREE (need_eh_cleanup);
4255 loop_optimizer_finalize ();
4258 /* Main entry point to the SSA-PRE pass. DO_FRE is true if the caller
4259 only wants to do full redundancy elimination. */
4262 execute_pre (bool do_fre ATTRIBUTE_UNUSED)
4264 unsigned int todo = 0;
4266 do_partial_partial = optimize > 2;
4268 /* This has to happen before SCCVN runs because
4269 loop_optimizer_init may create new phis, etc. */
4271 loop_optimizer_init (LOOPS_NORMAL);
4273 if (!run_scc_vn (do_fre))
4277 remove_dead_inserted_code ();
4278 loop_optimizer_finalize ();
4286 /* Collect and value number expressions computed in each basic block. */
4289 if (dump_file && (dump_flags & TDF_DETAILS))
4295 print_bitmap_set (dump_file, EXP_GEN (bb), "exp_gen", bb->index);
4296 print_bitmap_set (dump_file, TMP_GEN (bb), "tmp_gen",
4298 print_bitmap_set (dump_file, AVAIL_OUT (bb), "avail_out",
4303 /* Insert can get quite slow on an incredibly large number of basic
4304 blocks due to some quadratic behavior. Until this behavior is
4305 fixed, don't run it when he have an incredibly large number of
4306 bb's. If we aren't going to run insert, there is no point in
4307 computing ANTIC, either, even though it's plenty fast. */
4308 if (!do_fre && n_basic_blocks < 4000)
4314 /* Remove all the redundant expressions. */
4315 todo |= eliminate ();
4317 statistics_counter_event (cfun, "Insertions", pre_stats.insertions);
4318 statistics_counter_event (cfun, "PA inserted", pre_stats.pa_insert);
4319 statistics_counter_event (cfun, "New PHIs", pre_stats.phis);
4320 statistics_counter_event (cfun, "Eliminated", pre_stats.eliminations);
4321 statistics_counter_event (cfun, "Constified", pre_stats.constified);
4323 /* Make sure to remove fake edges before committing our inserts.
4324 This makes sure we don't end up with extra critical edges that
4325 we would need to split. */
4326 remove_fake_exit_edges ();
4327 gsi_commit_edge_inserts ();
4329 clear_expression_ids ();
4332 remove_dead_inserted_code ();
4339 /* Gate and execute functions for PRE. */
4344 return TODO_rebuild_alias | execute_pre (false);
4350 /* PRE tends to generate bigger code. */
4351 return flag_tree_pre != 0 && optimize_function_for_speed_p (cfun);
4354 struct gimple_opt_pass pass_pre =
4359 gate_pre, /* gate */
4360 do_pre, /* execute */
4363 0, /* static_pass_number */
4364 TV_TREE_PRE, /* tv_id */
4365 PROP_no_crit_edges | PROP_cfg
4366 | PROP_ssa | PROP_alias, /* properties_required */
4367 0, /* properties_provided */
4368 0, /* properties_destroyed */
4369 0, /* todo_flags_start */
4370 TODO_update_ssa_only_virtuals | TODO_dump_func | TODO_ggc_collect
4371 | TODO_verify_ssa /* todo_flags_finish */
4376 /* Gate and execute functions for FRE. */
4381 return execute_pre (true);
4387 return flag_tree_fre != 0;
4390 struct gimple_opt_pass pass_fre =
4395 gate_fre, /* gate */
4396 execute_fre, /* execute */
4399 0, /* static_pass_number */
4400 TV_TREE_FRE, /* tv_id */
4401 PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */
4402 0, /* properties_provided */
4403 0, /* properties_destroyed */
4404 0, /* todo_flags_start */
4405 TODO_dump_func | TODO_ggc_collect | TODO_verify_ssa /* todo_flags_finish */