2 Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007
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"
33 #include "tree-gimple.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_MODIFY_STMT, because GIMPLE_MODIFY_STMT's
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)
197 tree const0 = PRE_EXPR_CONSTANT (e1);
198 tree const1 = PRE_EXPR_CONSTANT (e2);
199 return TREE_TYPE (const1) == TREE_TYPE (const0)
200 && expressions_equal_p (const0, const1);
204 return PRE_EXPR_NAME (e1) == PRE_EXPR_NAME (e2);
206 return vn_nary_op_eq (PRE_EXPR_NARY (e1), PRE_EXPR_NARY (e2));
208 return vn_reference_eq (PRE_EXPR_REFERENCE (e1),
209 PRE_EXPR_REFERENCE (e2));
216 pre_expr_hash (const void *p1)
218 const struct pre_expr_d *e = (const struct pre_expr_d *) p1;
222 return iterative_hash_expr (PRE_EXPR_CONSTANT (e), 0);
224 return iterative_hash_expr (PRE_EXPR_NAME (e), 0);
226 return vn_nary_op_compute_hash (PRE_EXPR_NARY (e));
228 return vn_reference_compute_hash (PRE_EXPR_REFERENCE (e));
235 /* Next global expression id number. */
236 static unsigned int next_expression_id;
238 /* Mapping from expression to id number we can use in bitmap sets. */
239 DEF_VEC_P (pre_expr);
240 DEF_VEC_ALLOC_P (pre_expr, heap);
241 static VEC(pre_expr, heap) *expressions;
242 static htab_t expression_to_id;
244 /* Allocate an expression id for EXPR. */
246 static inline unsigned int
247 alloc_expression_id (pre_expr expr)
250 /* Make sure we won't overflow. */
251 gcc_assert (next_expression_id + 1 > next_expression_id);
252 expr->id = next_expression_id++;
253 VEC_safe_push (pre_expr, heap, expressions, expr);
254 slot = htab_find_slot (expression_to_id, expr, INSERT);
257 return next_expression_id - 1;
260 /* Return the expression id for tree EXPR. */
262 static inline unsigned int
263 get_expression_id (const pre_expr expr)
268 static inline unsigned int
269 lookup_expression_id (const pre_expr expr)
273 slot = htab_find_slot (expression_to_id, expr, NO_INSERT);
276 return ((pre_expr)*slot)->id;
279 /* Return the existing expression id for EXPR, or create one if one
280 does not exist yet. */
282 static inline unsigned int
283 get_or_alloc_expression_id (pre_expr expr)
285 unsigned int id = lookup_expression_id (expr);
287 return alloc_expression_id (expr);
288 return expr->id = id;
291 /* Return the expression that has expression id ID */
293 static inline pre_expr
294 expression_for_id (unsigned int id)
296 return VEC_index (pre_expr, expressions, id);
299 /* Free the expression id field in all of our expressions,
300 and then destroy the expressions array. */
303 clear_expression_ids (void)
305 VEC_free (pre_expr, heap, expressions);
308 static alloc_pool pre_expr_pool;
310 /* Given an SSA_NAME NAME, get or create a pre_expr to represent it. */
313 get_or_alloc_expr_for_name (tree name)
315 pre_expr result = (pre_expr) pool_alloc (pre_expr_pool);
316 unsigned int result_id;
320 PRE_EXPR_NAME (result) = name;
321 result_id = lookup_expression_id (result);
324 pre_expr newresult = expression_for_id (result_id);
325 pool_free (pre_expr_pool, result);
329 get_or_alloc_expression_id (result);
333 static bool in_fre = false;
335 /* An unordered bitmap set. One bitmap tracks values, the other,
337 typedef struct bitmap_set
343 #define FOR_EACH_EXPR_ID_IN_SET(set, id, bi) \
344 EXECUTE_IF_SET_IN_BITMAP((set)->expressions, 0, (id), (bi))
346 /* Mapping from value id to expressions with that value_id. */
347 DEF_VEC_P (bitmap_set_t);
348 DEF_VEC_ALLOC_P (bitmap_set_t, heap);
349 static VEC(bitmap_set_t, heap) *value_expressions;
351 /* Sets that we need to keep track of. */
352 typedef struct bb_bitmap_sets
354 /* The EXP_GEN set, which represents expressions/values generated in
356 bitmap_set_t exp_gen;
358 /* The PHI_GEN set, which represents PHI results generated in a
360 bitmap_set_t phi_gen;
362 /* The TMP_GEN set, which represents results/temporaries generated
363 in a basic block. IE the LHS of an expression. */
364 bitmap_set_t tmp_gen;
366 /* The AVAIL_OUT set, which represents which values are available in
367 a given basic block. */
368 bitmap_set_t avail_out;
370 /* The ANTIC_IN set, which represents which values are anticipatable
371 in a given basic block. */
372 bitmap_set_t antic_in;
374 /* The PA_IN set, which represents which values are
375 partially anticipatable in a given basic block. */
378 /* The NEW_SETS set, which is used during insertion to augment the
379 AVAIL_OUT set of blocks with the new insertions performed during
380 the current iteration. */
381 bitmap_set_t new_sets;
383 /* True if we have visited this block during ANTIC calculation. */
384 unsigned int visited:1;
386 /* True we have deferred processing this block during ANTIC
387 calculation until its successor is processed. */
388 unsigned int deferred : 1;
391 #define EXP_GEN(BB) ((bb_value_sets_t) ((BB)->aux))->exp_gen
392 #define PHI_GEN(BB) ((bb_value_sets_t) ((BB)->aux))->phi_gen
393 #define TMP_GEN(BB) ((bb_value_sets_t) ((BB)->aux))->tmp_gen
394 #define AVAIL_OUT(BB) ((bb_value_sets_t) ((BB)->aux))->avail_out
395 #define ANTIC_IN(BB) ((bb_value_sets_t) ((BB)->aux))->antic_in
396 #define PA_IN(BB) ((bb_value_sets_t) ((BB)->aux))->pa_in
397 #define NEW_SETS(BB) ((bb_value_sets_t) ((BB)->aux))->new_sets
398 #define BB_VISITED(BB) ((bb_value_sets_t) ((BB)->aux))->visited
399 #define BB_DEFERRED(BB) ((bb_value_sets_t) ((BB)->aux))->deferred
402 /* Maximal set of values, used to initialize the ANTIC problem, which
403 is an intersection problem. */
404 static bitmap_set_t maximal_set;
406 /* Basic block list in postorder. */
407 static int *postorder;
409 /* This structure is used to keep track of statistics on what
410 optimization PRE was able to perform. */
413 /* The number of RHS computations eliminated by PRE. */
416 /* The number of new expressions/temporaries generated by PRE. */
419 /* The number of inserts found due to partial anticipation */
422 /* The number of new PHI nodes added by PRE. */
425 /* The number of values found constant. */
430 static bool do_partial_partial;
431 static pre_expr bitmap_find_leader (bitmap_set_t, unsigned int , tree);
432 static void bitmap_value_insert_into_set (bitmap_set_t, pre_expr);
433 static void bitmap_value_replace_in_set (bitmap_set_t, pre_expr);
434 static void bitmap_set_copy (bitmap_set_t, bitmap_set_t);
435 static bool bitmap_set_contains_value (bitmap_set_t, unsigned int);
436 static void bitmap_insert_into_set (bitmap_set_t, pre_expr);
437 static void bitmap_insert_into_set_1 (bitmap_set_t, pre_expr, bool);
438 static bitmap_set_t bitmap_set_new (void);
439 static tree create_expression_by_pieces (basic_block, pre_expr, tree, tree,
441 static tree find_or_generate_expression (basic_block, pre_expr, tree, tree);
443 /* We can add and remove elements and entries to and from sets
444 and hash tables, so we use alloc pools for them. */
446 static alloc_pool bitmap_set_pool;
447 static bitmap_obstack grand_bitmap_obstack;
449 /* To avoid adding 300 temporary variables when we only need one, we
450 only create one temporary variable, on demand, and build ssa names
451 off that. We do have to change the variable if the types don't
452 match the current variable's type. */
454 static tree storetemp;
455 static tree prephitemp;
457 /* Set of blocks with statements that have had its EH information
459 static bitmap need_eh_cleanup;
461 /* Which expressions have been seen during a given phi translation. */
462 static bitmap seen_during_translate;
464 /* The phi_translate_table caches phi translations for a given
465 expression and predecessor. */
467 static htab_t phi_translate_table;
469 /* A three tuple {e, pred, v} used to cache phi translations in the
470 phi_translate_table. */
472 typedef struct expr_pred_trans_d
474 /* The expression. */
477 /* The predecessor block along which we translated the expression. */
480 /* The value that resulted from the translation. */
483 /* The hashcode for the expression, pred pair. This is cached for
486 } *expr_pred_trans_t;
487 typedef const struct expr_pred_trans_d *const_expr_pred_trans_t;
489 /* Return the hash value for a phi translation table entry. */
492 expr_pred_trans_hash (const void *p)
494 const_expr_pred_trans_t const ve = (const_expr_pred_trans_t) p;
498 /* Return true if two phi translation table entries are the same.
499 P1 and P2 should point to the expr_pred_trans_t's to be compared.*/
502 expr_pred_trans_eq (const void *p1, const void *p2)
504 const_expr_pred_trans_t const ve1 = (const_expr_pred_trans_t) p1;
505 const_expr_pred_trans_t const ve2 = (const_expr_pred_trans_t) p2;
506 basic_block b1 = ve1->pred;
507 basic_block b2 = ve2->pred;
509 /* If they are not translations for the same basic block, they can't
513 return pre_expr_eq (ve1->e, ve2->e);
516 /* Search in the phi translation table for the translation of
517 expression E in basic block PRED.
518 Return the translated value, if found, NULL otherwise. */
520 static inline pre_expr
521 phi_trans_lookup (pre_expr e, basic_block pred)
524 struct expr_pred_trans_d ept;
528 ept.hashcode = iterative_hash_hashval_t (pre_expr_hash (e), pred->index);
529 slot = htab_find_slot_with_hash (phi_translate_table, &ept, ept.hashcode,
534 return ((expr_pred_trans_t) *slot)->v;
538 /* Add the tuple mapping from {expression E, basic block PRED} to
539 value V, to the phi translation table. */
542 phi_trans_add (pre_expr e, pre_expr v, basic_block pred)
545 expr_pred_trans_t new_pair = XNEW (struct expr_pred_trans_d);
547 new_pair->pred = pred;
549 new_pair->hashcode = iterative_hash_hashval_t (pre_expr_hash (e),
552 slot = htab_find_slot_with_hash (phi_translate_table, new_pair,
553 new_pair->hashcode, INSERT);
556 *slot = (void *) new_pair;
560 /* Add expression E to the expression set of value id V. */
563 add_to_value (unsigned int v, pre_expr e)
567 if (v >= VEC_length (bitmap_set_t, value_expressions))
569 VEC_safe_grow_cleared (bitmap_set_t, heap, value_expressions,
573 set = VEC_index (bitmap_set_t, value_expressions, v);
576 set = bitmap_set_new ();
577 VEC_replace (bitmap_set_t, value_expressions, v, set);
580 bitmap_insert_into_set_1 (set, e, true);
583 /* Create a new bitmap set and return it. */
586 bitmap_set_new (void)
588 bitmap_set_t ret = (bitmap_set_t) pool_alloc (bitmap_set_pool);
589 ret->expressions = BITMAP_ALLOC (&grand_bitmap_obstack);
590 ret->values = BITMAP_ALLOC (&grand_bitmap_obstack);
594 /* Return the value id for a PRE expression EXPR. */
597 get_expr_value_id (pre_expr expr)
604 id = get_constant_value_id (PRE_EXPR_CONSTANT (expr));
607 id = get_or_alloc_constant_value_id (PRE_EXPR_CONSTANT (expr));
608 add_to_value (id, expr);
613 return VN_INFO (PRE_EXPR_NAME (expr))->value_id;
615 return PRE_EXPR_NARY (expr)->value_id;
617 return PRE_EXPR_REFERENCE (expr)->value_id;
623 /* Remove an expression EXPR from a bitmapped set. */
626 bitmap_remove_from_set (bitmap_set_t set, pre_expr expr)
628 unsigned int val = get_expr_value_id (expr);
629 if (!value_id_constant_p (val))
631 bitmap_clear_bit (set->values, val);
632 bitmap_clear_bit (set->expressions, get_expression_id (expr));
637 bitmap_insert_into_set_1 (bitmap_set_t set, pre_expr expr,
638 bool allow_constants)
640 unsigned int val = get_expr_value_id (expr);
641 if (allow_constants || !value_id_constant_p (val))
643 /* We specifically expect this and only this function to be able to
644 insert constants into a set. */
645 bitmap_set_bit (set->values, val);
646 bitmap_set_bit (set->expressions, get_or_alloc_expression_id (expr));
650 /* Insert an expression EXPR into a bitmapped set. */
653 bitmap_insert_into_set (bitmap_set_t set, pre_expr expr)
655 bitmap_insert_into_set_1 (set, expr, false);
658 /* Copy a bitmapped set ORIG, into bitmapped set DEST. */
661 bitmap_set_copy (bitmap_set_t dest, bitmap_set_t orig)
663 bitmap_copy (dest->expressions, orig->expressions);
664 bitmap_copy (dest->values, orig->values);
668 /* Free memory used up by SET. */
670 bitmap_set_free (bitmap_set_t set)
672 BITMAP_FREE (set->expressions);
673 BITMAP_FREE (set->values);
677 /* A comparison function for use in qsort to top sort a bitmap set. Simply
678 subtracts value ids, since they are created with leaves before
679 their parent users (IE topological order). */
682 value_id_compare (const void *pa, const void *pb)
684 const unsigned int vha = get_expr_value_id (*((const pre_expr *)pa));
685 const unsigned int vhb = get_expr_value_id (*((const pre_expr *)pb));
690 /* Generate an topological-ordered array of bitmap set SET. */
692 static VEC(pre_expr, heap) *
693 sorted_array_from_bitmap_set (bitmap_set_t set)
697 VEC(pre_expr, heap) *result = NULL;
699 FOR_EACH_EXPR_ID_IN_SET (set, i, bi)
700 VEC_safe_push (pre_expr, heap, result, expression_for_id (i));
702 qsort (VEC_address (pre_expr, result), VEC_length (pre_expr, result),
703 sizeof (pre_expr), value_id_compare);
708 /* Perform bitmapped set operation DEST &= ORIG. */
711 bitmap_set_and (bitmap_set_t dest, bitmap_set_t orig)
718 bitmap temp = BITMAP_ALLOC (&grand_bitmap_obstack);
720 bitmap_and_into (dest->values, orig->values);
721 bitmap_copy (temp, dest->expressions);
722 EXECUTE_IF_SET_IN_BITMAP (temp, 0, i, bi)
724 pre_expr expr = expression_for_id (i);
725 unsigned int value_id = get_expr_value_id (expr);
726 if (!bitmap_bit_p (dest->values, value_id))
727 bitmap_clear_bit (dest->expressions, i);
733 /* Subtract all values and expressions contained in ORIG from DEST. */
736 bitmap_set_subtract (bitmap_set_t dest, bitmap_set_t orig)
738 bitmap_set_t result = bitmap_set_new ();
742 bitmap_and_compl (result->expressions, dest->expressions,
745 FOR_EACH_EXPR_ID_IN_SET (result, i, bi)
747 pre_expr expr = expression_for_id (i);
748 unsigned int value_id = get_expr_value_id (expr);
749 bitmap_set_bit (result->values, value_id);
755 /* Subtract all the values in bitmap set B from bitmap set A. */
758 bitmap_set_subtract_values (bitmap_set_t a, bitmap_set_t b)
762 bitmap temp = BITMAP_ALLOC (&grand_bitmap_obstack);
764 bitmap_copy (temp, a->expressions);
765 EXECUTE_IF_SET_IN_BITMAP (temp, 0, i, bi)
767 pre_expr expr = expression_for_id (i);
768 if (bitmap_set_contains_value (b, get_expr_value_id (expr)))
769 bitmap_remove_from_set (a, expr);
775 /* Return true if bitmapped set SET contains the value VALUE_ID. */
778 bitmap_set_contains_value (bitmap_set_t set, unsigned int value_id)
780 if (value_id_constant_p (value_id))
783 if (!set || bitmap_empty_p (set->expressions))
786 return bitmap_bit_p (set->values, value_id);
790 bitmap_set_contains_expr (bitmap_set_t set, const pre_expr expr)
792 return bitmap_bit_p (set->expressions, get_expression_id (expr));
795 /* Replace an instance of value LOOKFOR with expression EXPR in SET. */
798 bitmap_set_replace_value (bitmap_set_t set, unsigned int lookfor,
801 bitmap_set_t exprset;
805 if (value_id_constant_p (lookfor))
808 if (!bitmap_set_contains_value (set, lookfor))
811 /* The number of expressions having a given value is usually
812 significantly less than the total number of expressions in SET.
813 Thus, rather than check, for each expression in SET, whether it
814 has the value LOOKFOR, we walk the reverse mapping that tells us
815 what expressions have a given value, and see if any of those
816 expressions are in our set. For large testcases, this is about
817 5-10x faster than walking the bitmap. If this is somehow a
818 significant lose for some cases, we can choose which set to walk
819 based on the set size. */
820 exprset = VEC_index (bitmap_set_t, value_expressions, lookfor);
821 FOR_EACH_EXPR_ID_IN_SET (exprset, i, bi)
823 if (bitmap_bit_p (set->expressions, i))
825 bitmap_clear_bit (set->expressions, i);
826 bitmap_set_bit (set->expressions, get_expression_id (expr));
832 /* Return true if two bitmap sets are equal. */
835 bitmap_set_equal (bitmap_set_t a, bitmap_set_t b)
837 return bitmap_equal_p (a->values, b->values);
840 /* Replace an instance of EXPR's VALUE with EXPR in SET if it exists,
841 and add it otherwise. */
844 bitmap_value_replace_in_set (bitmap_set_t set, pre_expr expr)
846 unsigned int val = get_expr_value_id (expr);
848 if (bitmap_set_contains_value (set, val))
849 bitmap_set_replace_value (set, val, expr);
851 bitmap_insert_into_set (set, expr);
854 /* Insert EXPR into SET if EXPR's value is not already present in
858 bitmap_value_insert_into_set (bitmap_set_t set, pre_expr expr)
860 unsigned int val = get_expr_value_id (expr);
862 if (value_id_constant_p (val))
865 if (!bitmap_set_contains_value (set, val))
866 bitmap_insert_into_set (set, expr);
869 /* Print out EXPR to outfile. */
872 print_pre_expr (FILE *outfile, const pre_expr expr)
877 print_generic_expr (outfile, PRE_EXPR_CONSTANT (expr), 0);
880 print_generic_expr (outfile, PRE_EXPR_NAME (expr), 0);
885 vn_nary_op_t nary = PRE_EXPR_NARY (expr);
886 fprintf (outfile, "{%s,", tree_code_name [nary->opcode]);
887 for (i = 0; i < nary->length; i++)
889 print_generic_expr (outfile, nary->op[i], 0);
890 if (i != (unsigned) nary->length - 1)
891 fprintf (outfile, ",");
893 fprintf (outfile, "}");
899 vn_reference_op_t vro;
901 vn_reference_t ref = PRE_EXPR_REFERENCE (expr);
902 fprintf (outfile, "{");
904 VEC_iterate (vn_reference_op_s, ref->operands, i, vro);
907 if (vro->opcode != SSA_NAME
908 && TREE_CODE_CLASS (vro->opcode) != tcc_declaration)
909 fprintf (outfile, "%s ", tree_code_name [vro->opcode]);
913 fprintf (outfile, "<");
914 print_generic_expr (outfile, vro->op0, 0);
917 fprintf (outfile, ",");
918 print_generic_expr (outfile, vro->op1, 0);
921 fprintf (outfile, ">");
923 if (i != VEC_length (vn_reference_op_s, ref->operands) - 1)
924 fprintf (outfile, ",");
926 fprintf (outfile, "}");
931 void debug_pre_expr (pre_expr);
933 /* Like print_pre_expr but always prints to stderr. */
935 debug_pre_expr (pre_expr e)
937 print_pre_expr (stderr, e);
938 fprintf (stderr, "\n");
941 /* Print out SET to OUTFILE. */
944 print_bitmap_set (FILE *outfile, bitmap_set_t set,
945 const char *setname, int blockindex)
947 fprintf (outfile, "%s[%d] := { ", setname, blockindex);
954 FOR_EACH_EXPR_ID_IN_SET (set, i, bi)
956 const pre_expr expr = expression_for_id (i);
959 fprintf (outfile, ", ");
961 print_pre_expr (outfile, expr);
963 fprintf (outfile, " (%04d)", get_expr_value_id (expr));
966 fprintf (outfile, " }\n");
969 void debug_bitmap_set (bitmap_set_t);
972 debug_bitmap_set (bitmap_set_t set)
974 print_bitmap_set (stderr, set, "debug", 0);
977 /* Print out the expressions that have VAL to OUTFILE. */
980 print_value_expressions (FILE *outfile, unsigned int val)
982 bitmap_set_t set = VEC_index (bitmap_set_t, value_expressions, val);
986 sprintf (s, "%04d", val);
987 print_bitmap_set (outfile, set, s, 0);
993 debug_value_expressions (unsigned int val)
995 print_value_expressions (stderr, val);
998 /* Given a CONSTANT, allocate a new CONSTANT type PRE_EXPR to
1002 get_or_alloc_expr_for_constant (tree constant)
1004 unsigned int result_id;
1005 unsigned int value_id;
1006 pre_expr newexpr = (pre_expr) pool_alloc (pre_expr_pool);
1007 newexpr->kind = CONSTANT;
1008 PRE_EXPR_CONSTANT (newexpr) = constant;
1009 result_id = lookup_expression_id (newexpr);
1012 pre_expr newresult = expression_for_id (result_id);
1013 pool_free (pre_expr_pool, newexpr);
1014 newexpr = newresult;
1017 value_id = get_or_alloc_constant_value_id (constant);
1018 get_or_alloc_expression_id (newexpr);
1019 add_to_value (value_id, newexpr);
1023 /* Given a value id V, find the actual tree representing the constant
1024 value if there is one, and return it. Return NULL if we can't find
1028 get_constant_for_value_id (unsigned int v, tree type)
1030 if (value_id_constant_p (v))
1034 bitmap_set_t exprset = VEC_index (bitmap_set_t, value_expressions, v);
1036 FOR_EACH_EXPR_ID_IN_SET (exprset, i, bi)
1038 pre_expr expr = expression_for_id (i);
1039 if (expr->kind == CONSTANT
1040 && TREE_TYPE (PRE_EXPR_CONSTANT (expr)) == type)
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 return get_or_alloc_expr_for_constant (t);
1059 /* Return the folded version of T if T, when folded, is a gimple
1060 min_invariant. Otherwise, return T. */
1063 fully_constant_expression (pre_expr e)
1071 vn_nary_op_t nary = PRE_EXPR_NARY (e);
1072 switch (TREE_CODE_CLASS (nary->opcode))
1076 /* We have to go from trees to pre exprs to value ids to
1078 tree naryop0 = nary->op[0];
1079 tree naryop1 = nary->op[1];
1080 pre_expr rep0 = get_or_alloc_expr_for (naryop0);
1081 pre_expr rep1 = get_or_alloc_expr_for (naryop1);
1082 unsigned int vrep0 = get_expr_value_id (rep0);
1083 unsigned int vrep1 = get_expr_value_id (rep1);
1084 tree const0 = get_constant_for_value_id (vrep0,
1085 TREE_TYPE (nary->op[0]));
1086 tree const1 = get_constant_for_value_id (vrep1,
1087 TREE_TYPE (nary->op[1]));
1089 if (const0 && const1)
1091 tree type1 = TREE_TYPE (nary->op[0]);
1092 tree type2 = TREE_TYPE (nary->op[1]);
1093 const0 = fold_convert (type1, const0);
1094 const1 = fold_convert (type2, const1);
1095 result = fold_binary (nary->opcode, nary->type, const0,
1098 if (result && is_gimple_min_invariant (result))
1099 return get_or_alloc_expr_for_constant (result);
1104 /* We have to go from trees to pre exprs to value ids to
1106 tree naryop0 = nary->op[0];
1107 pre_expr rep0 = get_or_alloc_expr_for (naryop0);
1108 unsigned int vrep0 = get_expr_value_id (rep0);
1109 tree const0 = get_constant_for_value_id (vrep0,
1110 TREE_TYPE (nary->op[0]));
1114 tree type1 = TREE_TYPE (nary->op[0]);
1115 const0 = fold_convert (type1, const0);
1116 result = fold_unary (nary->opcode, nary->type, const0);
1119 if (result && is_gimple_min_invariant (result))
1120 return get_or_alloc_expr_for_constant (result);
1133 /* Translate the vuses in the VUSES vector backwards through phi nodes
1134 in PHIBLOCK, so that they have the value they would have in
1137 static VEC(tree, gc) *
1138 translate_vuses_through_block (VEC (tree, gc) *vuses,
1139 basic_block phiblock,
1143 VEC(tree, gc) *result = NULL;
1146 for (i = 0; VEC_iterate (tree, vuses, i, oldvuse); i++)
1148 tree phi = SSA_NAME_DEF_STMT (oldvuse);
1149 if (TREE_CODE (phi) == PHI_NODE
1150 && bb_for_stmt (phi) == phiblock)
1152 edge e = find_edge (block, bb_for_stmt (phi));
1155 tree def = PHI_ARG_DEF (phi, e->dest_idx);
1159 result = VEC_copy (tree, gc, vuses);
1160 VEC_replace (tree, result, i, def);
1166 /* We avoid creating a new copy of the vuses unless something
1167 actually changed, so result can be NULL. */
1170 sort_vuses (result);
1177 /* Like find_leader, but checks for the value existing in SET1 *or*
1178 SET2. This is used to avoid making a set consisting of the union
1179 of PA_IN and ANTIC_IN during insert. */
1181 static inline pre_expr
1182 find_leader_in_sets (unsigned int val, bitmap_set_t set1, bitmap_set_t set2)
1186 result = bitmap_find_leader (set1, val, NULL_TREE);
1187 if (!result && set2)
1188 result = bitmap_find_leader (set2, val, NULL_TREE);
1192 /* Get the tree type for our PRE expression e. */
1195 get_expr_type (const pre_expr e)
1200 return TREE_TYPE (PRE_EXPR_NAME (e));
1202 return TREE_TYPE (PRE_EXPR_CONSTANT (e));
1205 vn_reference_op_t vro;
1207 gcc_assert (PRE_EXPR_REFERENCE (e)->operands);
1208 vro = VEC_index (vn_reference_op_s,
1209 PRE_EXPR_REFERENCE (e)->operands,
1211 /* We don't store type along with COMPONENT_REF because it is
1212 always the same as FIELD_DECL's type. */
1215 gcc_assert (vro->opcode == COMPONENT_REF);
1216 return TREE_TYPE (vro->op0);
1222 return PRE_EXPR_NARY (e)->type;
1227 /* Get a representative SSA_NAME for a given expression.
1228 Since all of our sub-expressions are treated as values, we require
1229 them to be SSA_NAME's for simplicity.
1230 Prior versions of GVNPRE used to use "value handles" here, so that
1231 an expression would be VH.11 + VH.10 instead of d_3 + e_6. In
1232 either case, the operands are really values (IE we do not expect
1233 them to be usable without finding leaders). */
1236 get_representative_for (const pre_expr e)
1240 unsigned int value_id = get_expr_value_id (e);
1245 return PRE_EXPR_NAME (e);
1250 /* Go through all of the expressions representing this value
1251 and pick out an SSA_NAME. */
1254 bitmap_set_t exprs = VEC_index (bitmap_set_t, value_expressions,
1256 FOR_EACH_EXPR_ID_IN_SET (exprs, i, bi)
1258 pre_expr rep = expression_for_id (i);
1259 if (rep->kind == NAME)
1260 return PRE_EXPR_NAME (rep);
1265 /* If we reached here we couldn't find an SSA_NAME. This can
1266 happen when we've discovered a value that has never appeared in
1267 the program as set to an SSA_NAME, most likely as the result of
1272 "Could not find SSA_NAME representative for expression:");
1273 print_pre_expr (dump_file, e);
1274 fprintf (dump_file, "\n");
1277 exprtype = get_expr_type (e);
1279 /* Build and insert the assignment of the end result to the temporary
1280 that we will return. */
1281 if (!pretemp || exprtype != TREE_TYPE (pretemp))
1283 pretemp = create_tmp_var (exprtype, "pretmp");
1284 get_var_ann (pretemp);
1287 name = make_ssa_name (pretemp, build_empty_stmt ());
1288 VN_INFO_GET (name)->value_id = value_id;
1289 if (e->kind == CONSTANT)
1290 VN_INFO (name)->valnum = PRE_EXPR_CONSTANT (e);
1292 VN_INFO (name)->valnum = name;
1294 add_to_value (value_id, get_or_alloc_expr_for_name (name));
1297 fprintf (dump_file, "Created SSA_NAME representative ");
1298 print_generic_expr (dump_file, name, 0);
1299 fprintf (dump_file, " for expression:");
1300 print_pre_expr (dump_file, e);
1301 fprintf (dump_file, "\n");
1310 /* Translate EXPR using phis in PHIBLOCK, so that it has the values of
1311 the phis in PRED. SEEN is a bitmap saying which expression we have
1312 translated since we started translation of the toplevel expression.
1313 Return NULL if we can't find a leader for each part of the
1314 translated expression. */
1317 phi_translate_1 (pre_expr expr, bitmap_set_t set1, bitmap_set_t set2,
1318 basic_block pred, basic_block phiblock, bitmap seen)
1320 pre_expr oldexpr = expr;
1326 if (value_id_constant_p (get_expr_value_id (expr)))
1329 phitrans = phi_trans_lookup (expr, pred);
1333 /* Prevent cycles when we have recursively dependent leaders. This
1334 can only happen when phi translating the maximal set. */
1337 unsigned int expr_id = get_expression_id (expr);
1338 if (bitmap_bit_p (seen, expr_id))
1340 bitmap_set_bit (seen, expr_id);
1345 /* Constants contain no values that need translation. */
1352 bool changed = false;
1353 vn_nary_op_t nary = PRE_EXPR_NARY (expr);
1354 struct vn_nary_op_s newnary;
1355 /* The NARY structure is only guaranteed to have been
1356 allocated to the nary->length operands. */
1357 memcpy (&newnary, nary, (sizeof (struct vn_nary_op_s)
1358 - sizeof (tree) * (4 - nary->length)));
1360 for (i = 0; i < newnary.length; i++)
1362 if (TREE_CODE (newnary.op[i]) != SSA_NAME)
1366 unsigned int op_val_id = VN_INFO (newnary.op[i])->value_id;
1367 pre_expr leader = find_leader_in_sets (op_val_id, set1, set2);
1368 pre_expr result = phi_translate_1 (leader, set1, set2,
1369 pred, phiblock, seen);
1370 if (result && result != leader)
1372 tree name = get_representative_for (result);
1375 newnary.op[i] = name;
1380 changed |= newnary.op[i] != nary->op[i];
1387 tree result = vn_nary_op_lookup_pieces (newnary.length,
1395 unsigned int new_val_id;
1397 expr = (pre_expr) pool_alloc (pre_expr_pool);
1400 if (result && is_gimple_min_invariant (result))
1401 return get_or_alloc_expr_for_constant (result);
1406 PRE_EXPR_NARY (expr) = nary;
1407 constant = fully_constant_expression (expr);
1408 if (constant != expr)
1411 new_val_id = nary->value_id;
1412 get_or_alloc_expression_id (expr);
1416 new_val_id = get_next_value_id ();
1417 VEC_safe_grow_cleared (bitmap_set_t, heap,
1419 get_max_value_id() + 1);
1420 nary = vn_nary_op_insert_pieces (newnary.length,
1427 result, new_val_id);
1428 PRE_EXPR_NARY (expr) = nary;
1429 constant = fully_constant_expression (expr);
1430 if (constant != expr)
1432 get_or_alloc_expression_id (expr);
1434 add_to_value (new_val_id, expr);
1436 phi_trans_add (oldexpr, expr, pred);
1442 vn_reference_t ref = PRE_EXPR_REFERENCE (expr);
1443 VEC (vn_reference_op_s, heap) *operands = ref->operands;
1444 VEC (tree, gc) *vuses = ref->vuses;
1445 VEC (tree, gc) *newvuses = vuses;
1446 VEC (vn_reference_op_s, heap) *newoperands = NULL;
1447 bool changed = false;
1449 vn_reference_op_t operand;
1450 vn_reference_t newref;
1452 for (i = 0; VEC_iterate (vn_reference_op_s, operands, i, operand); i++)
1456 tree oldop0 = operand->op0;
1457 tree oldop1 = operand->op1;
1458 tree oldop2 = operand->op2;
1462 tree type = operand->type;
1463 vn_reference_op_s newop = *operand;
1465 if (op0 && TREE_CODE (op0) == SSA_NAME)
1467 unsigned int op_val_id = VN_INFO (op0)->value_id;
1468 leader = find_leader_in_sets (op_val_id, set1, set2);
1469 opresult = phi_translate_1 (leader, set1, set2,
1470 pred, phiblock, seen);
1471 if (opresult && opresult != leader)
1473 tree name = get_representative_for (opresult);
1481 changed |= op0 != oldop0;
1483 if (op1 && TREE_CODE (op1) == SSA_NAME)
1485 unsigned int op_val_id = VN_INFO (op1)->value_id;
1486 leader = find_leader_in_sets (op_val_id, set1, set2);
1487 opresult = phi_translate_1 (leader, set1, set2,
1488 pred, phiblock, seen);
1489 if (opresult && opresult != leader)
1491 tree name = get_representative_for (opresult);
1499 changed |= op1 != oldop1;
1500 if (op2 && TREE_CODE (op2) == SSA_NAME)
1502 unsigned int op_val_id = VN_INFO (op2)->value_id;
1503 leader = find_leader_in_sets (op_val_id, set1, set2);
1504 opresult = phi_translate_1 (leader, set1, set2,
1505 pred, phiblock, seen);
1506 if (opresult && opresult != leader)
1508 tree name = get_representative_for (opresult);
1516 changed |= op2 != oldop2;
1519 newoperands = VEC_copy (vn_reference_op_s, heap, operands);
1520 /* We may have changed from an SSA_NAME to a constant */
1521 if (newop.opcode == SSA_NAME && TREE_CODE (op0) != SSA_NAME)
1522 newop.opcode = TREE_CODE (op0);
1527 VEC_replace (vn_reference_op_s, newoperands, i, &newop);
1530 newvuses = translate_vuses_through_block (vuses, phiblock, pred);
1531 changed |= newvuses != vuses;
1535 tree result = vn_reference_lookup_pieces (newvuses,
1538 unsigned int new_val_id;
1541 VEC_free (vn_reference_op_s, heap, newoperands);
1543 if (result && is_gimple_min_invariant (result))
1544 return get_or_alloc_expr_for_constant (result);
1546 expr = (pre_expr) pool_alloc (pre_expr_pool);
1547 expr->kind = REFERENCE;
1552 PRE_EXPR_REFERENCE (expr) = newref;
1553 new_val_id = newref->value_id;
1554 get_or_alloc_expression_id (expr);
1558 new_val_id = get_next_value_id ();
1559 VEC_safe_grow_cleared (bitmap_set_t, heap, value_expressions,
1560 get_max_value_id() + 1);
1561 newref = vn_reference_insert_pieces (newvuses,
1563 result, new_val_id);
1564 PRE_EXPR_REFERENCE (expr) = newref;
1565 get_or_alloc_expression_id (expr);
1567 add_to_value (new_val_id, expr);
1569 phi_trans_add (oldexpr, expr, pred);
1578 tree name = PRE_EXPR_NAME (expr);
1580 def_stmt = SSA_NAME_DEF_STMT (name);
1581 if (TREE_CODE (def_stmt) == PHI_NODE
1582 && bb_for_stmt (def_stmt) == phiblock)
1587 e = find_edge (pred, bb_for_stmt (phi));
1590 tree def = PHI_ARG_DEF (phi, e->dest_idx);
1593 /* Handle constant. */
1594 if (is_gimple_min_invariant (def))
1595 return get_or_alloc_expr_for_constant (def);
1597 if (TREE_CODE (def) == SSA_NAME && ssa_undefined_value_p (def))
1600 newexpr = get_or_alloc_expr_for_name (def);
1611 /* Translate EXPR using phis in PHIBLOCK, so that it has the values of
1613 Return NULL if we can't find a leader for each part of the
1614 translated expression. */
1617 phi_translate (pre_expr expr, bitmap_set_t set1, bitmap_set_t set2,
1618 basic_block pred, basic_block phiblock)
1620 bitmap_clear (seen_during_translate);
1621 return phi_translate_1 (expr, set1, set2, pred, phiblock,
1622 seen_during_translate);
1625 /* For each expression in SET, translate the values through phi nodes
1626 in PHIBLOCK using edge PHIBLOCK->PRED, and store the resulting
1627 expressions in DEST. */
1630 phi_translate_set (bitmap_set_t dest, bitmap_set_t set, basic_block pred,
1631 basic_block phiblock)
1633 VEC (pre_expr, heap) *exprs;
1637 if (!phi_nodes (phiblock))
1639 bitmap_set_copy (dest, set);
1643 exprs = sorted_array_from_bitmap_set (set);
1644 for (i = 0; VEC_iterate (pre_expr, exprs, i, expr); i++)
1646 pre_expr translated;
1647 translated = phi_translate (expr, set, NULL, pred, phiblock);
1649 /* Don't add constants or empty translations to the cache, since
1650 we won't look them up that way, or use the result, anyway. */
1651 if (translated && !value_id_constant_p (get_expr_value_id (translated)))
1652 phi_trans_add (expr, translated, pred);
1654 if (translated != NULL)
1655 bitmap_value_insert_into_set (dest, translated);
1657 VEC_free (pre_expr, heap, exprs);
1660 /* Find the leader for a value (i.e., the name representing that
1661 value) in a given set, and return it. If STMT is non-NULL it
1662 makes sure the defining statement for the leader dominates it.
1663 Return NULL if no leader is found. */
1666 bitmap_find_leader (bitmap_set_t set, unsigned int val, tree stmt)
1668 if (value_id_constant_p (val))
1672 bitmap_set_t exprset = VEC_index (bitmap_set_t, value_expressions, val);
1674 FOR_EACH_EXPR_ID_IN_SET (exprset, i, bi)
1676 pre_expr expr = expression_for_id (i);
1677 if (expr->kind == CONSTANT)
1681 if (bitmap_set_contains_value (set, val))
1683 /* Rather than walk the entire bitmap of expressions, and see
1684 whether any of them has the value we are looking for, we look
1685 at the reverse mapping, which tells us the set of expressions
1686 that have a given value (IE value->expressions with that
1687 value) and see if any of those expressions are in our set.
1688 The number of expressions per value is usually significantly
1689 less than the number of expressions in the set. In fact, for
1690 large testcases, doing it this way is roughly 5-10x faster
1691 than walking the bitmap.
1692 If this is somehow a significant lose for some cases, we can
1693 choose which set to walk based on which set is smaller. */
1696 bitmap_set_t exprset = VEC_index (bitmap_set_t, value_expressions, val);
1698 EXECUTE_IF_AND_IN_BITMAP (exprset->expressions,
1699 set->expressions, 0, i, bi)
1701 pre_expr val = expression_for_id (i);
1702 /* At the point where stmt is not null, there should always
1703 be an SSA_NAME first in the list of expressions. */
1706 tree def_stmt = SSA_NAME_DEF_STMT (PRE_EXPR_NAME (val));
1707 if (TREE_CODE (def_stmt) != PHI_NODE
1708 && bb_for_stmt (def_stmt) == bb_for_stmt (stmt)
1709 && stmt_ann (def_stmt)->uid >= stmt_ann (stmt)->uid)
1718 /* Determine if EXPR, a memory expression, is ANTIC_IN at the top of
1719 BLOCK by seeing if it is not killed in the block. Note that we are
1720 only determining whether there is a store that kills it. Because
1721 of the order in which clean iterates over values, we are guaranteed
1722 that altered operands will have caused us to be eliminated from the
1723 ANTIC_IN set already. */
1726 value_dies_in_block_x (pre_expr expr, basic_block block)
1730 VEC (tree, gc) *vuses = PRE_EXPR_REFERENCE (expr)->vuses;
1732 /* Conservatively, a value dies if it's vuses are defined in this
1733 block, unless they come from phi nodes (which are merge operations,
1734 rather than stores. */
1735 for (i = 0; VEC_iterate (tree, vuses, i, vuse); i++)
1737 tree def = SSA_NAME_DEF_STMT (vuse);
1739 if (bb_for_stmt (def) != block)
1741 if (TREE_CODE (def) == PHI_NODE)
1749 #define union_contains_value(SET1, SET2, VAL) \
1750 (bitmap_set_contains_value ((SET1), (VAL)) \
1751 || ((SET2) && bitmap_set_contains_value ((SET2), (VAL))))
1753 /* Determine if vn_reference_op_t VRO is legal in SET1 U SET2.
1756 vro_valid_in_sets (bitmap_set_t set1, bitmap_set_t set2,
1757 vn_reference_op_t vro)
1759 if (vro->op0 && TREE_CODE (vro->op0) == SSA_NAME)
1761 struct pre_expr_d temp;
1764 PRE_EXPR_NAME (&temp) = vro->op0;
1765 temp.id = lookup_expression_id (&temp);
1768 if (!union_contains_value (set1, set2,
1769 get_expr_value_id (&temp)))
1772 if (vro->op1 && TREE_CODE (vro->op1) == SSA_NAME)
1774 struct pre_expr_d temp;
1777 PRE_EXPR_NAME (&temp) = vro->op1;
1778 temp.id = lookup_expression_id (&temp);
1781 if (!union_contains_value (set1, set2,
1782 get_expr_value_id (&temp)))
1786 if (vro->op2 && TREE_CODE (vro->op2) == SSA_NAME)
1788 struct pre_expr_d temp;
1791 PRE_EXPR_NAME (&temp) = vro->op2;
1792 temp.id = lookup_expression_id (&temp);
1795 if (!union_contains_value (set1, set2,
1796 get_expr_value_id (&temp)))
1803 /* Determine if the expression EXPR is valid in SET1 U SET2.
1804 ONLY SET2 CAN BE NULL.
1805 This means that we have a leader for each part of the expression
1806 (if it consists of values), or the expression is an SSA_NAME.
1807 For loads/calls, we also see if the vuses are killed in this block.
1811 valid_in_sets (bitmap_set_t set1, bitmap_set_t set2, pre_expr expr,
1817 return bitmap_set_contains_expr (AVAIL_OUT (block), expr);
1821 vn_nary_op_t nary = PRE_EXPR_NARY (expr);
1822 for (i = 0; i < nary->length; i++)
1824 if (TREE_CODE (nary->op[i]) == SSA_NAME)
1826 struct pre_expr_d temp;
1829 PRE_EXPR_NAME (&temp) = nary->op[i];
1830 temp.id = lookup_expression_id (&temp);
1833 if (!union_contains_value (set1, set2,
1834 get_expr_value_id (&temp)))
1843 vn_reference_t ref = PRE_EXPR_REFERENCE (expr);
1844 vn_reference_op_t vro;
1847 for (i = 0; VEC_iterate (vn_reference_op_s, ref->operands, i, vro); i++)
1849 if (!vro_valid_in_sets (set1, set2, vro))
1852 return !value_dies_in_block_x (expr, block);
1859 /* Clean the set of expressions that are no longer valid in SET1 or
1860 SET2. This means expressions that are made up of values we have no
1861 leaders for in SET1 or SET2. This version is used for partial
1862 anticipation, which means it is not valid in either ANTIC_IN or
1866 dependent_clean (bitmap_set_t set1, bitmap_set_t set2, basic_block block)
1868 VEC (pre_expr, heap) *exprs = sorted_array_from_bitmap_set (set1);
1872 for (i = 0; VEC_iterate (pre_expr, exprs, i, expr); i++)
1874 if (!valid_in_sets (set1, set2, expr, block))
1875 bitmap_remove_from_set (set1, expr);
1877 VEC_free (pre_expr, heap, exprs);
1880 /* Clean the set of expressions that are no longer valid in SET. This
1881 means expressions that are made up of values we have no leaders for
1885 clean (bitmap_set_t set, basic_block block)
1887 VEC (pre_expr, heap) *exprs = sorted_array_from_bitmap_set (set);
1891 for (i = 0; VEC_iterate (pre_expr, exprs, i, expr); i++)
1893 if (!valid_in_sets (set, NULL, expr, block))
1894 bitmap_remove_from_set (set, expr);
1896 VEC_free (pre_expr, heap, exprs);
1899 static sbitmap has_abnormal_preds;
1901 /* List of blocks that may have changed during ANTIC computation and
1902 thus need to be iterated over. */
1904 static sbitmap changed_blocks;
1906 /* Decide whether to defer a block for a later iteration, or PHI
1907 translate SOURCE to DEST using phis in PHIBLOCK. Return false if we
1908 should defer the block, and true if we processed it. */
1911 defer_or_phi_translate_block (bitmap_set_t dest, bitmap_set_t source,
1912 basic_block block, basic_block phiblock)
1914 if (!BB_VISITED (phiblock))
1916 SET_BIT (changed_blocks, block->index);
1917 BB_VISITED (block) = 0;
1918 BB_DEFERRED (block) = 1;
1922 phi_translate_set (dest, source, block, phiblock);
1926 /* Compute the ANTIC set for BLOCK.
1928 If succs(BLOCK) > 1 then
1929 ANTIC_OUT[BLOCK] = intersection of ANTIC_IN[b] for all succ(BLOCK)
1930 else if succs(BLOCK) == 1 then
1931 ANTIC_OUT[BLOCK] = phi_translate (ANTIC_IN[succ(BLOCK)])
1933 ANTIC_IN[BLOCK] = clean(ANTIC_OUT[BLOCK] U EXP_GEN[BLOCK] - TMP_GEN[BLOCK])
1937 compute_antic_aux (basic_block block, bool block_has_abnormal_pred_edge)
1939 bool changed = false;
1940 bitmap_set_t S, old, ANTIC_OUT;
1946 old = ANTIC_OUT = S = NULL;
1947 BB_VISITED (block) = 1;
1949 /* If any edges from predecessors are abnormal, antic_in is empty,
1951 if (block_has_abnormal_pred_edge)
1952 goto maybe_dump_sets;
1954 old = ANTIC_IN (block);
1955 ANTIC_OUT = bitmap_set_new ();
1957 /* If the block has no successors, ANTIC_OUT is empty. */
1958 if (EDGE_COUNT (block->succs) == 0)
1960 /* If we have one successor, we could have some phi nodes to
1961 translate through. */
1962 else if (single_succ_p (block))
1964 basic_block succ_bb = single_succ (block);
1966 /* We trade iterations of the dataflow equations for having to
1967 phi translate the maximal set, which is incredibly slow
1968 (since the maximal set often has 300+ members, even when you
1969 have a small number of blocks).
1970 Basically, we defer the computation of ANTIC for this block
1971 until we have processed it's successor, which will inevitably
1972 have a *much* smaller set of values to phi translate once
1973 clean has been run on it.
1974 The cost of doing this is that we technically perform more
1975 iterations, however, they are lower cost iterations.
1977 Timings for PRE on tramp3d-v4:
1978 without maximal set fix: 11 seconds
1979 with maximal set fix/without deferring: 26 seconds
1980 with maximal set fix/with deferring: 11 seconds
1983 if (!defer_or_phi_translate_block (ANTIC_OUT, ANTIC_IN (succ_bb),
1987 goto maybe_dump_sets;
1990 /* If we have multiple successors, we take the intersection of all of
1991 them. Note that in the case of loop exit phi nodes, we may have
1992 phis to translate through. */
1995 VEC(basic_block, heap) * worklist;
1997 basic_block bprime, first;
1999 worklist = VEC_alloc (basic_block, heap, EDGE_COUNT (block->succs));
2000 FOR_EACH_EDGE (e, ei, block->succs)
2001 VEC_quick_push (basic_block, worklist, e->dest);
2002 first = VEC_index (basic_block, worklist, 0);
2004 if (phi_nodes (first))
2006 bitmap_set_t from = ANTIC_IN (first);
2008 if (!BB_VISITED (first))
2010 phi_translate_set (ANTIC_OUT, from, block, first);
2014 if (!BB_VISITED (first))
2015 bitmap_set_copy (ANTIC_OUT, maximal_set);
2017 bitmap_set_copy (ANTIC_OUT, ANTIC_IN (first));
2020 for (i = 1; VEC_iterate (basic_block, worklist, i, bprime); i++)
2022 if (phi_nodes (bprime))
2024 bitmap_set_t tmp = bitmap_set_new ();
2025 bitmap_set_t from = ANTIC_IN (bprime);
2027 if (!BB_VISITED (bprime))
2029 phi_translate_set (tmp, from, block, bprime);
2030 bitmap_set_and (ANTIC_OUT, tmp);
2031 bitmap_set_free (tmp);
2035 if (!BB_VISITED (bprime))
2036 bitmap_set_and (ANTIC_OUT, maximal_set);
2038 bitmap_set_and (ANTIC_OUT, ANTIC_IN (bprime));
2041 VEC_free (basic_block, heap, worklist);
2044 /* Generate ANTIC_OUT - TMP_GEN. */
2045 S = bitmap_set_subtract (ANTIC_OUT, TMP_GEN (block));
2047 /* Start ANTIC_IN with EXP_GEN - TMP_GEN. */
2048 ANTIC_IN (block) = bitmap_set_subtract (EXP_GEN (block),
2051 /* Then union in the ANTIC_OUT - TMP_GEN values,
2052 to get ANTIC_OUT U EXP_GEN - TMP_GEN */
2053 FOR_EACH_EXPR_ID_IN_SET (S, bii, bi)
2054 bitmap_value_insert_into_set (ANTIC_IN (block),
2055 expression_for_id (bii));
2057 clean (ANTIC_IN (block), block);
2059 /* !old->expressions can happen when we deferred a block. */
2060 if (!old->expressions || !bitmap_set_equal (old, ANTIC_IN (block)))
2063 SET_BIT (changed_blocks, block->index);
2064 FOR_EACH_EDGE (e, ei, block->preds)
2065 SET_BIT (changed_blocks, e->src->index);
2068 RESET_BIT (changed_blocks, block->index);
2071 if (dump_file && (dump_flags & TDF_DETAILS))
2073 if (!BB_DEFERRED (block) || BB_VISITED (block))
2076 print_bitmap_set (dump_file, ANTIC_OUT, "ANTIC_OUT", block->index);
2078 print_bitmap_set (dump_file, ANTIC_IN (block), "ANTIC_IN",
2082 print_bitmap_set (dump_file, S, "S", block->index);
2087 "Block %d was deferred for a future iteration.\n",
2092 bitmap_set_free (old);
2094 bitmap_set_free (S);
2096 bitmap_set_free (ANTIC_OUT);
2100 /* Compute PARTIAL_ANTIC for BLOCK.
2102 If succs(BLOCK) > 1 then
2103 PA_OUT[BLOCK] = value wise union of PA_IN[b] + all ANTIC_IN not
2104 in ANTIC_OUT for all succ(BLOCK)
2105 else if succs(BLOCK) == 1 then
2106 PA_OUT[BLOCK] = phi_translate (PA_IN[succ(BLOCK)])
2108 PA_IN[BLOCK] = dependent_clean(PA_OUT[BLOCK] - TMP_GEN[BLOCK]
2113 compute_partial_antic_aux (basic_block block,
2114 bool block_has_abnormal_pred_edge)
2116 bool changed = false;
2117 bitmap_set_t old_PA_IN;
2118 bitmap_set_t PA_OUT;
2121 unsigned long max_pa = PARAM_VALUE (PARAM_MAX_PARTIAL_ANTIC_LENGTH);
2123 old_PA_IN = PA_OUT = NULL;
2125 /* If any edges from predecessors are abnormal, antic_in is empty,
2127 if (block_has_abnormal_pred_edge)
2128 goto maybe_dump_sets;
2130 /* If there are too many partially anticipatable values in the
2131 block, phi_translate_set can take an exponential time: stop
2132 before the translation starts. */
2134 && single_succ_p (block)
2135 && bitmap_count_bits (PA_IN (single_succ (block))->values) > max_pa)
2136 goto maybe_dump_sets;
2138 old_PA_IN = PA_IN (block);
2139 PA_OUT = bitmap_set_new ();
2141 /* If the block has no successors, ANTIC_OUT is empty. */
2142 if (EDGE_COUNT (block->succs) == 0)
2144 /* If we have one successor, we could have some phi nodes to
2145 translate through. Note that we can't phi translate across DFS
2146 back edges in partial antic, because it uses a union operation on
2147 the successors. For recurrences like IV's, we will end up
2148 generating a new value in the set on each go around (i + 3 (VH.1)
2149 VH.1 + 1 (VH.2), VH.2 + 1 (VH.3), etc), forever. */
2150 else if (single_succ_p (block))
2152 basic_block succ = single_succ (block);
2153 if (!(single_succ_edge (block)->flags & EDGE_DFS_BACK))
2154 phi_translate_set (PA_OUT, PA_IN (succ), block, succ);
2156 /* If we have multiple successors, we take the union of all of
2160 VEC(basic_block, heap) * worklist;
2164 worklist = VEC_alloc (basic_block, heap, EDGE_COUNT (block->succs));
2165 FOR_EACH_EDGE (e, ei, block->succs)
2167 if (e->flags & EDGE_DFS_BACK)
2169 VEC_quick_push (basic_block, worklist, e->dest);
2171 if (VEC_length (basic_block, worklist) > 0)
2173 for (i = 0; VEC_iterate (basic_block, worklist, i, bprime); i++)
2178 FOR_EACH_EXPR_ID_IN_SET (ANTIC_IN (bprime), i, bi)
2179 bitmap_value_insert_into_set (PA_OUT,
2180 expression_for_id (i));
2181 if (phi_nodes (bprime))
2183 bitmap_set_t pa_in = bitmap_set_new ();
2184 phi_translate_set (pa_in, PA_IN (bprime), block, bprime);
2185 FOR_EACH_EXPR_ID_IN_SET (pa_in, i, bi)
2186 bitmap_value_insert_into_set (PA_OUT,
2187 expression_for_id (i));
2188 bitmap_set_free (pa_in);
2191 FOR_EACH_EXPR_ID_IN_SET (PA_IN (bprime), i, bi)
2192 bitmap_value_insert_into_set (PA_OUT,
2193 expression_for_id (i));
2196 VEC_free (basic_block, heap, worklist);
2199 /* PA_IN starts with PA_OUT - TMP_GEN.
2200 Then we subtract things from ANTIC_IN. */
2201 PA_IN (block) = bitmap_set_subtract (PA_OUT, TMP_GEN (block));
2203 /* For partial antic, we want to put back in the phi results, since
2204 we will properly avoid making them partially antic over backedges. */
2205 bitmap_ior_into (PA_IN (block)->values, PHI_GEN (block)->values);
2206 bitmap_ior_into (PA_IN (block)->expressions, PHI_GEN (block)->expressions);
2208 /* PA_IN[block] = PA_IN[block] - ANTIC_IN[block] */
2209 bitmap_set_subtract_values (PA_IN (block), ANTIC_IN (block));
2211 dependent_clean (PA_IN (block), ANTIC_IN (block), block);
2213 if (!bitmap_set_equal (old_PA_IN, PA_IN (block)))
2216 SET_BIT (changed_blocks, block->index);
2217 FOR_EACH_EDGE (e, ei, block->preds)
2218 SET_BIT (changed_blocks, e->src->index);
2221 RESET_BIT (changed_blocks, block->index);
2224 if (dump_file && (dump_flags & TDF_DETAILS))
2227 print_bitmap_set (dump_file, PA_OUT, "PA_OUT", block->index);
2229 print_bitmap_set (dump_file, PA_IN (block), "PA_IN", block->index);
2232 bitmap_set_free (old_PA_IN);
2234 bitmap_set_free (PA_OUT);
2238 /* Compute ANTIC and partial ANTIC sets. */
2241 compute_antic (void)
2243 bool changed = true;
2244 int num_iterations = 0;
2248 /* If any predecessor edges are abnormal, we punt, so antic_in is empty.
2249 We pre-build the map of blocks with incoming abnormal edges here. */
2250 has_abnormal_preds = sbitmap_alloc (last_basic_block);
2251 sbitmap_zero (has_abnormal_preds);
2258 FOR_EACH_EDGE (e, ei, block->preds)
2260 e->flags &= ~EDGE_DFS_BACK;
2261 if (e->flags & EDGE_ABNORMAL)
2263 SET_BIT (has_abnormal_preds, block->index);
2268 BB_VISITED (block) = 0;
2269 BB_DEFERRED (block) = 0;
2270 /* While we are here, give empty ANTIC_IN sets to each block. */
2271 ANTIC_IN (block) = bitmap_set_new ();
2272 PA_IN (block) = bitmap_set_new ();
2275 /* At the exit block we anticipate nothing. */
2276 ANTIC_IN (EXIT_BLOCK_PTR) = bitmap_set_new ();
2277 BB_VISITED (EXIT_BLOCK_PTR) = 1;
2278 PA_IN (EXIT_BLOCK_PTR) = bitmap_set_new ();
2280 changed_blocks = sbitmap_alloc (last_basic_block + 1);
2281 sbitmap_ones (changed_blocks);
2284 if (dump_file && (dump_flags & TDF_DETAILS))
2285 fprintf (dump_file, "Starting iteration %d\n", num_iterations);
2288 for (i = 0; i < last_basic_block - NUM_FIXED_BLOCKS; i++)
2290 if (TEST_BIT (changed_blocks, postorder[i]))
2292 basic_block block = BASIC_BLOCK (postorder[i]);
2293 changed |= compute_antic_aux (block,
2294 TEST_BIT (has_abnormal_preds,
2298 #ifdef ENABLE_CHECKING
2299 /* Theoretically possible, but *highly* unlikely. */
2300 gcc_assert (num_iterations < 500);
2304 statistics_histogram_event (cfun, "compute_antic iterations",
2307 if (do_partial_partial)
2309 sbitmap_ones (changed_blocks);
2310 mark_dfs_back_edges ();
2315 if (dump_file && (dump_flags & TDF_DETAILS))
2316 fprintf (dump_file, "Starting iteration %d\n", num_iterations);
2319 for (i = 0; i < last_basic_block - NUM_FIXED_BLOCKS; i++)
2321 if (TEST_BIT (changed_blocks, postorder[i]))
2323 basic_block block = BASIC_BLOCK (postorder[i]);
2325 |= compute_partial_antic_aux (block,
2326 TEST_BIT (has_abnormal_preds,
2330 #ifdef ENABLE_CHECKING
2331 /* Theoretically possible, but *highly* unlikely. */
2332 gcc_assert (num_iterations < 500);
2335 statistics_histogram_event (cfun, "compute_partial_antic iterations",
2338 sbitmap_free (has_abnormal_preds);
2339 sbitmap_free (changed_blocks);
2342 /* Return true if we can value number the call in STMT. This is true
2343 if we have a pure or constant call. */
2346 can_value_number_call (tree stmt)
2348 tree call = get_call_expr_in (stmt);
2350 if (call_expr_flags (call) & (ECF_PURE | ECF_CONST))
2355 /* Return true if OP is an exception handler related operation, such as
2356 FILTER_EXPR or EXC_PTR_EXPR. */
2359 is_exception_related (tree op)
2361 return TREE_CODE (op) == FILTER_EXPR || TREE_CODE (op) == EXC_PTR_EXPR;
2364 /* Return true if OP is a tree which we can perform PRE on
2365 on. This may not match the operations we can value number, but in
2366 a perfect world would. */
2369 can_PRE_operation (tree op)
2371 return UNARY_CLASS_P (op)
2372 || BINARY_CLASS_P (op)
2373 || COMPARISON_CLASS_P (op)
2374 || TREE_CODE (op) == INDIRECT_REF
2375 || TREE_CODE (op) == COMPONENT_REF
2376 || TREE_CODE (op) == VIEW_CONVERT_EXPR
2377 || TREE_CODE (op) == CALL_EXPR
2378 || TREE_CODE (op) == ARRAY_REF;
2382 /* Inserted expressions are placed onto this worklist, which is used
2383 for performing quick dead code elimination of insertions we made
2384 that didn't turn out to be necessary. */
2385 static VEC(tree,heap) *inserted_exprs;
2387 /* Pool allocated fake store expressions are placed onto this
2388 worklist, which, after performing dead code elimination, is walked
2389 to see which expressions need to be put into GC'able memory */
2390 static VEC(tree, heap) *need_creation;
2392 /* For COMPONENT_REF's and ARRAY_REF's, we can't have any intermediates for the
2393 COMPONENT_REF or INDIRECT_REF or ARRAY_REF portion, because we'd end up with
2394 trying to rename aggregates into ssa form directly, which is a no
2397 Thus, this routine doesn't create temporaries, it just builds a
2398 single access expression for the array, calling
2399 find_or_generate_expression to build the innermost pieces.
2401 This function is a subroutine of create_expression_by_pieces, and
2402 should not be called on it's own unless you really know what you
2406 create_component_ref_by_pieces (basic_block block, vn_reference_t ref,
2407 unsigned int operand,
2412 vn_reference_op_t currop = VEC_index (vn_reference_op_s, ref->operands,
2415 switch (currop->opcode)
2421 vn_reference_op_t declop = VEC_index (vn_reference_op_s,
2423 unsigned int nargs = VEC_length (vn_reference_op_s, ref->operands) - 2;
2424 tree *args = XNEWVEC (tree, nargs);
2426 for (i = 0; i < nargs; i++)
2428 args[i] = create_component_ref_by_pieces (block, ref,
2429 operand + 2 + i, stmts,
2432 folded = build_call_array (currop->type, declop->op0, nargs, args);
2439 case VIEW_CONVERT_EXPR:
2442 tree genop0 = create_component_ref_by_pieces (block, ref,
2448 folded = fold_build1 (currop->opcode, currop->type,
2453 case ALIGN_INDIRECT_REF:
2454 case MISALIGNED_INDIRECT_REF:
2457 /* Inside a CALL_EXPR op0 is the actual indirect_ref. */
2461 tree op0 = TREE_OPERAND (currop->op0, 0);
2462 pre_expr op0expr = get_or_alloc_expr_for (op0);
2463 tree genop0 = find_or_generate_expression (block, op0expr, stmts,
2467 folded = fold_build1 (currop->opcode, currop->type,
2475 tree genop1 = create_component_ref_by_pieces (block, ref,
2481 genop1 = fold_convert (build_pointer_type (currop->type),
2484 folded = fold_build1 (currop->opcode, currop->type,
2493 tree genop0 = create_component_ref_by_pieces (block, ref, operand + 1,
2496 pre_expr op1expr = get_or_alloc_expr_for (currop->op0);
2497 pre_expr op2expr = get_or_alloc_expr_for (currop->op1);
2503 genop1 = find_or_generate_expression (block, op1expr, stmts, domstmt);
2506 genop2 = find_or_generate_expression (block, op2expr, stmts, domstmt);
2509 folded = fold_build3 (BIT_FIELD_REF, currop->type, genop0, genop1,
2514 /* For array ref vn_reference_op's, operand 1 of the array ref
2515 is op0 of the reference op and operand 3 of the array ref is
2517 case ARRAY_RANGE_REF:
2520 vn_reference_op_t op0expr;
2522 tree genop1 = currop->op0;
2524 tree genop2 = currop->op1;
2527 op0expr = VEC_index (vn_reference_op_s, ref->operands, operand + 1);
2528 genop0 = create_component_ref_by_pieces (block, ref, operand + 1,
2533 op1expr = get_or_alloc_expr_for (genop1);
2534 genop1 = find_or_generate_expression (block, op1expr, stmts, domstmt);
2539 op2expr = get_or_alloc_expr_for (genop2);
2540 genop2 = find_or_generate_expression (block, op2expr, stmts,
2546 genop3 = currop->op2;
2547 return build4 (currop->opcode, currop->type, genop0, genop1,
2554 tree genop2 = currop->op1;
2556 op0 = create_component_ref_by_pieces (block, ref, operand + 1,
2557 stmts, domstmt, in_call);
2560 /* op1 should be a FIELD_DECL, which are represented by
2565 op2expr = get_or_alloc_expr_for (genop2);
2566 genop2 = find_or_generate_expression (block, op2expr, stmts,
2572 return fold_build3 (COMPONENT_REF, TREE_TYPE (op1), op0, op1,
2578 pre_expr op0expr = get_or_alloc_expr_for (currop->op0);
2579 genop = find_or_generate_expression (block, op0expr, stmts, domstmt);
2593 /* For ADDR_EXPR in a CALL_EXPR, op0 is actually the entire
2594 ADDR_EXPR, not just it's operand. */
2596 if (currop->opcode == ADDR_EXPR)
2597 gcc_assert (currop->op0 != NULL);
2605 /* Find a leader for an expression, or generate one using
2606 create_expression_by_pieces if it's ANTIC but
2608 BLOCK is the basic_block we are looking for leaders in.
2609 EXPR is the expression to find a leader or generate for.
2610 STMTS is the statement list to put the inserted expressions on.
2611 Returns the SSA_NAME of the LHS of the generated expression or the
2613 DOMSTMT if non-NULL is a statement that should be dominated by
2614 all uses in the generated expression. If DOMSTMT is non-NULL this
2615 routine can fail and return NULL_TREE. Otherwise it will assert
2619 find_or_generate_expression (basic_block block, pre_expr expr, tree stmts,
2625 if (expr->kind == CONSTANT)
2626 return PRE_EXPR_CONSTANT (expr);
2628 leader = bitmap_find_leader (AVAIL_OUT (block),
2629 get_expr_value_id (expr), domstmt);
2632 if (leader->kind == NAME)
2633 genop = PRE_EXPR_NAME (leader);
2634 else if (leader->kind == CONSTANT)
2635 genop = PRE_EXPR_CONSTANT (leader);
2638 /* If it's still NULL, it must be a complex expression, so generate
2642 bitmap_set_t exprset;
2643 unsigned int lookfor = get_expr_value_id (expr);
2644 bool handled = false;
2648 exprset = VEC_index (bitmap_set_t, value_expressions, lookfor);
2649 FOR_EACH_EXPR_ID_IN_SET (exprset, i, bi)
2651 pre_expr temp = expression_for_id (i);
2652 if (temp->kind != NAME)
2655 genop = create_expression_by_pieces (block, temp, stmts,
2657 get_expr_type (expr));
2661 if (!handled && domstmt)
2664 gcc_assert (handled);
2669 #define NECESSARY(stmt) stmt->base.asm_written_flag
2671 /* Create an expression in pieces, so that we can handle very complex
2672 expressions that may be ANTIC, but not necessary GIMPLE.
2673 BLOCK is the basic block the expression will be inserted into,
2674 EXPR is the expression to insert (in value form)
2675 STMTS is a statement list to append the necessary insertions into.
2677 This function will die if we hit some value that shouldn't be
2678 ANTIC but is (IE there is no leader for it, or its components).
2679 This function may also generate expressions that are themselves
2680 partially or fully redundant. Those that are will be either made
2681 fully redundant during the next iteration of insert (for partially
2682 redundant ones), or eliminated by eliminate (for fully redundant
2685 If DOMSTMT is non-NULL then we make sure that all uses in the
2686 expressions dominate that statement. In this case the function
2687 can return NULL_TREE to signal failure. */
2690 create_expression_by_pieces (basic_block block, pre_expr expr, tree stmts,
2695 tree folded, forced_stmts, newexpr;
2696 unsigned int value_id;
2697 tree_stmt_iterator tsi;
2698 tree exprtype = type ? type : get_expr_type (expr);
2703 /* We may hit the NAME/CONSTANT case if we have to convert types
2704 that value numbering saw through. */
2706 folded = PRE_EXPR_NAME (expr);
2709 folded = PRE_EXPR_CONSTANT (expr);
2713 vn_reference_t ref = PRE_EXPR_REFERENCE (expr);
2714 folded = create_component_ref_by_pieces (block, ref, 0, stmts,
2720 vn_nary_op_t nary = PRE_EXPR_NARY (expr);
2721 switch (nary->length)
2725 pre_expr op1 = get_or_alloc_expr_for (nary->op[0]);
2726 pre_expr op2 = get_or_alloc_expr_for (nary->op[1]);
2727 tree genop1 = find_or_generate_expression (block, op1,
2729 tree genop2 = find_or_generate_expression (block, op2,
2731 if (!genop1 || !genop2)
2734 genop1 = fold_convert (TREE_TYPE (nary->op[0]),
2736 genop2 = fold_convert (TREE_TYPE (nary->op[1]), genop2);
2738 folded = fold_build2 (nary->opcode, nary->type,
2744 pre_expr op1 = get_or_alloc_expr_for (nary->op[0]);
2745 tree genop1 = find_or_generate_expression (block, op1,
2749 genop1 = fold_convert (TREE_TYPE (nary->op[0]), genop1);
2751 folded = fold_build1 (nary->opcode, nary->type,
2763 folded = fold_convert (exprtype, folded);
2764 /* Force the generated expression to be a sequence of GIMPLE
2766 We have to call unshare_expr because force_gimple_operand may
2767 modify the tree we pass to it. */
2768 newexpr = force_gimple_operand (unshare_expr (folded), &forced_stmts,
2771 /* If we have any intermediate expressions to the value sets, add them
2772 to the value sets and chain them in the instruction stream. */
2775 tsi = tsi_start (forced_stmts);
2776 for (; !tsi_end_p (tsi); tsi_next (&tsi))
2778 tree stmt = tsi_stmt (tsi);
2779 tree forcedname = GIMPLE_STMT_OPERAND (stmt, 0);
2782 VEC_safe_push (tree, heap, inserted_exprs, stmt);
2783 if (TREE_CODE (forcedname) == SSA_NAME)
2785 VN_INFO_GET (forcedname)->valnum = forcedname;
2786 VN_INFO (forcedname)->value_id = get_next_value_id ();
2787 nameexpr = get_or_alloc_expr_for_name (forcedname);
2788 add_to_value (VN_INFO (forcedname)->value_id, nameexpr);
2789 bitmap_value_replace_in_set (NEW_SETS (block), nameexpr);
2790 bitmap_value_replace_in_set (AVAIL_OUT (block), nameexpr);
2792 mark_symbols_for_renaming (stmt);
2794 tsi = tsi_last (stmts);
2795 tsi_link_after (&tsi, forced_stmts, TSI_CONTINUE_LINKING);
2798 /* Build and insert the assignment of the end result to the temporary
2799 that we will return. */
2800 if (!pretemp || exprtype != TREE_TYPE (pretemp))
2802 pretemp = create_tmp_var (exprtype, "pretmp");
2803 get_var_ann (pretemp);
2807 add_referenced_var (temp);
2809 if (TREE_CODE (exprtype) == COMPLEX_TYPE
2810 || TREE_CODE (exprtype) == VECTOR_TYPE)
2811 DECL_GIMPLE_REG_P (temp) = 1;
2813 newexpr = build_gimple_modify_stmt (temp, newexpr);
2814 name = make_ssa_name (temp, newexpr);
2815 GIMPLE_STMT_OPERAND (newexpr, 0) = name;
2816 NECESSARY (newexpr) = 0;
2818 tsi = tsi_last (stmts);
2819 tsi_link_after (&tsi, newexpr, TSI_CONTINUE_LINKING);
2820 VEC_safe_push (tree, heap, inserted_exprs, newexpr);
2822 /* All the symbols in NEWEXPR should be put into SSA form. */
2823 mark_symbols_for_renaming (newexpr);
2825 /* Add a value number to the temporary.
2826 The value may already exist in either NEW_SETS, or AVAIL_OUT, because
2827 we are creating the expression by pieces, and this particular piece of
2828 the expression may have been represented. There is no harm in replacing
2830 VN_INFO_GET (name)->valnum = name;
2831 value_id = get_expr_value_id (expr);
2832 VN_INFO (name)->value_id = value_id;
2833 nameexpr = get_or_alloc_expr_for_name (name);
2834 add_to_value (value_id, nameexpr);
2836 bitmap_value_replace_in_set (NEW_SETS (block), nameexpr);
2837 bitmap_value_replace_in_set (AVAIL_OUT (block), nameexpr);
2839 pre_stats.insertions++;
2840 if (dump_file && (dump_flags & TDF_DETAILS))
2842 fprintf (dump_file, "Inserted ");
2843 print_generic_expr (dump_file, newexpr, 0);
2844 fprintf (dump_file, " in predecessor %d\n", block->index);
2851 /* Insert the to-be-made-available values of expression EXPRNUM for each
2852 predecessor, stored in AVAIL, into the predecessors of BLOCK, and
2853 merge the result with a phi node, given the same value number as
2854 NODE. Return true if we have inserted new stuff. */
2857 insert_into_preds_of_block (basic_block block, unsigned int exprnum,
2860 pre_expr expr = expression_for_id (exprnum);
2862 unsigned int val = get_expr_value_id (expr);
2864 bool insertions = false;
2869 tree type = get_expr_type (expr);
2872 if (dump_file && (dump_flags & TDF_DETAILS))
2874 fprintf (dump_file, "Found partial redundancy for expression ");
2875 print_pre_expr (dump_file, expr);
2876 fprintf (dump_file, " (%04d)\n", val);
2879 /* Make sure we aren't creating an induction variable. */
2880 if (block->loop_depth > 0 && EDGE_COUNT (block->preds) == 2
2881 && expr->kind != REFERENCE)
2883 bool firstinsideloop = false;
2884 bool secondinsideloop = false;
2885 firstinsideloop = flow_bb_inside_loop_p (block->loop_father,
2886 EDGE_PRED (block, 0)->src);
2887 secondinsideloop = flow_bb_inside_loop_p (block->loop_father,
2888 EDGE_PRED (block, 1)->src);
2889 /* Induction variables only have one edge inside the loop. */
2890 if (firstinsideloop ^ secondinsideloop)
2892 if (dump_file && (dump_flags & TDF_DETAILS))
2893 fprintf (dump_file, "Skipping insertion of phi for partial redundancy: Looks like an induction variable\n");
2899 /* Make the necessary insertions. */
2900 FOR_EACH_EDGE (pred, ei, block->preds)
2902 tree stmts = alloc_stmt_list ();
2905 eprime = avail[bprime->index];
2907 if (eprime->kind != NAME && eprime->kind != CONSTANT)
2909 builtexpr = create_expression_by_pieces (bprime,
2913 gcc_assert (!(pred->flags & EDGE_ABNORMAL));
2914 bsi_insert_on_edge (pred, stmts);
2915 avail[bprime->index] = get_or_alloc_expr_for_name (builtexpr);
2918 else if (eprime->kind == CONSTANT)
2920 /* Constants may not have the right type, fold_convert
2921 should give us back a constant with the right type.
2923 tree constant = PRE_EXPR_CONSTANT (eprime);
2924 if (TREE_TYPE (constant) != type)
2926 tree builtexpr = fold_convert (type, constant);
2927 if (is_gimple_min_invariant (builtexpr))
2929 PRE_EXPR_CONSTANT (eprime) = builtexpr;
2933 tree forcedexpr = force_gimple_operand (builtexpr,
2936 if (is_gimple_min_invariant (forcedexpr))
2938 PRE_EXPR_CONSTANT (eprime) = forcedexpr;
2942 if (forcedexpr != builtexpr)
2944 VN_INFO_GET (forcedexpr)->valnum = PRE_EXPR_CONSTANT (eprime);
2945 VN_INFO (forcedexpr)->value_id = get_expr_value_id (eprime);
2949 tree_stmt_iterator tsi;
2950 tsi = tsi_start (stmts);
2951 for (; !tsi_end_p (tsi); tsi_next (&tsi))
2953 tree stmt = tsi_stmt (tsi);
2954 tree lhs = GIMPLE_STMT_OPERAND (stmt, 0);
2955 VEC_safe_push (tree, heap, inserted_exprs, stmt);
2956 NECESSARY (lhs) = 0;
2958 bsi_insert_on_edge (pred, stmts);
2960 NECESSARY (forcedexpr) = 0;
2961 avail[bprime->index] = get_or_alloc_expr_for_name (forcedexpr);
2966 else if (eprime->kind == NAME)
2968 /* We may have to do a conversion because our value
2969 numbering can look through types in certain cases, but
2970 our IL requires all operands of a phi node have the same
2972 tree name = PRE_EXPR_NAME (eprime);
2973 if (!useless_type_conversion_p (type, TREE_TYPE (name)))
2977 builtexpr = fold_convert (type, name);
2978 forcedexpr = force_gimple_operand (builtexpr,
2982 if (forcedexpr != name)
2984 VN_INFO_GET (forcedexpr)->valnum = VN_INFO (name)->valnum;
2985 VN_INFO (forcedexpr)->value_id = VN_INFO (name)->value_id;
2990 tree_stmt_iterator tsi;
2991 tsi = tsi_start (stmts);
2992 for (; !tsi_end_p (tsi); tsi_next (&tsi))
2994 tree stmt = tsi_stmt (tsi);
2995 tree lhs = GIMPLE_STMT_OPERAND (stmt, 0);
2996 VEC_safe_push (tree, heap, inserted_exprs, stmt);
2997 NECESSARY (lhs) = 0;
2999 bsi_insert_on_edge (pred, stmts);
3001 NECESSARY (forcedexpr) = 0;
3002 avail[bprime->index] = get_or_alloc_expr_for_name (forcedexpr);
3006 /* If we didn't want a phi node, and we made insertions, we still have
3007 inserted new stuff, and thus return true. If we didn't want a phi node,
3008 and didn't make insertions, we haven't added anything new, so return
3010 if (nophi && insertions)
3012 else if (nophi && !insertions)
3015 /* Now build a phi for the new variable. */
3016 if (!prephitemp || TREE_TYPE (prephitemp) != type)
3018 prephitemp = create_tmp_var (type, "prephitmp");
3019 get_var_ann (prephitemp);
3023 add_referenced_var (temp);
3025 if (TREE_CODE (type) == COMPLEX_TYPE
3026 || TREE_CODE (type) == VECTOR_TYPE)
3027 DECL_GIMPLE_REG_P (temp) = 1;
3028 temp = create_phi_node (temp, block);
3030 NECESSARY (temp) = 0;
3031 VN_INFO_GET (PHI_RESULT (temp))->valnum = PHI_RESULT (temp);
3032 VN_INFO (PHI_RESULT (temp))->value_id = val;
3033 VEC_safe_push (tree, heap, inserted_exprs, temp);
3034 FOR_EACH_EDGE (pred, ei, block->preds)
3036 pre_expr ae = avail[pred->src->index];
3037 gcc_assert (get_expr_type (ae) == type
3038 || useless_type_conversion_p (type, get_expr_type (ae)));
3039 if (ae->kind == CONSTANT)
3040 add_phi_arg (temp, PRE_EXPR_CONSTANT (ae), pred);
3042 add_phi_arg (temp, PRE_EXPR_NAME (avail[pred->src->index]), pred);
3045 newphi = get_or_alloc_expr_for_name (PHI_RESULT (temp));
3046 add_to_value (val, newphi);
3048 /* The value should *not* exist in PHI_GEN, or else we wouldn't be doing
3049 this insertion, since we test for the existence of this value in PHI_GEN
3050 before proceeding with the partial redundancy checks in insert_aux.
3052 The value may exist in AVAIL_OUT, in particular, it could be represented
3053 by the expression we are trying to eliminate, in which case we want the
3054 replacement to occur. If it's not existing in AVAIL_OUT, we want it
3057 Similarly, to the PHI_GEN case, the value should not exist in NEW_SETS of
3058 this block, because if it did, it would have existed in our dominator's
3059 AVAIL_OUT, and would have been skipped due to the full redundancy check.
3062 bitmap_insert_into_set (PHI_GEN (block), newphi);
3063 bitmap_value_replace_in_set (AVAIL_OUT (block),
3065 bitmap_insert_into_set (NEW_SETS (block),
3068 if (dump_file && (dump_flags & TDF_DETAILS))
3070 fprintf (dump_file, "Created phi ");
3071 print_generic_expr (dump_file, temp, 0);
3072 fprintf (dump_file, " in block %d\n", block->index);
3080 /* Perform insertion of partially redundant values.
3081 For BLOCK, do the following:
3082 1. Propagate the NEW_SETS of the dominator into the current block.
3083 If the block has multiple predecessors,
3084 2a. Iterate over the ANTIC expressions for the block to see if
3085 any of them are partially redundant.
3086 2b. If so, insert them into the necessary predecessors to make
3087 the expression fully redundant.
3088 2c. Insert a new PHI merging the values of the predecessors.
3089 2d. Insert the new PHI, and the new expressions, into the
3091 3. Recursively call ourselves on the dominator children of BLOCK.
3093 Steps 1, 2a, and 3 are done by insert_aux. 2b, 2c and 2d are done by
3094 do_regular_insertion and do_partial_insertion.
3099 do_regular_insertion (basic_block block, basic_block dom)
3101 bool new_stuff = false;
3102 VEC (pre_expr, heap) *exprs = sorted_array_from_bitmap_set (ANTIC_IN (block));
3106 for (i = 0; VEC_iterate (pre_expr, exprs, i, expr); i++)
3108 if (expr->kind != NAME)
3112 bool by_some = false;
3113 bool cant_insert = false;
3114 bool all_same = true;
3115 pre_expr first_s = NULL;
3118 pre_expr eprime = NULL;
3121 val = get_expr_value_id (expr);
3122 if (bitmap_set_contains_value (PHI_GEN (block), val))
3124 if (bitmap_set_contains_value (AVAIL_OUT (dom), val))
3126 if (dump_file && (dump_flags & TDF_DETAILS))
3127 fprintf (dump_file, "Found fully redundant value\n");
3131 avail = XCNEWVEC (pre_expr, last_basic_block);
3132 FOR_EACH_EDGE (pred, ei, block->preds)
3134 unsigned int vprime;
3135 pre_expr edoubleprime;
3137 /* This can happen in the very weird case
3138 that our fake infinite loop edges have caused a
3139 critical edge to appear. */
3140 if (EDGE_CRITICAL_P (pred))
3146 eprime = phi_translate (expr, ANTIC_IN (block), NULL,
3149 /* eprime will generally only be NULL if the
3150 value of the expression, translated
3151 through the PHI for this predecessor, is
3152 undefined. If that is the case, we can't
3153 make the expression fully redundant,
3154 because its value is undefined along a
3155 predecessor path. We can thus break out
3156 early because it doesn't matter what the
3157 rest of the results are. */
3164 eprime = fully_constant_expression (eprime);
3165 if (eprime->kind == CONSTANT)
3167 edoubleprime = eprime;
3171 vprime = get_expr_value_id (eprime);
3172 edoubleprime = bitmap_find_leader (AVAIL_OUT (bprime),
3175 if (edoubleprime == NULL)
3177 avail[bprime->index] = eprime;
3182 avail[bprime->index] = edoubleprime;
3184 if (first_s == NULL)
3185 first_s = edoubleprime;
3186 else if (!pre_expr_eq (first_s, edoubleprime))
3190 /* If we can insert it, it's not the same value
3191 already existing along every predecessor, and
3192 it's defined by some predecessor, it is
3193 partially redundant. */
3194 if (!cant_insert && !all_same && by_some && dbg_cnt (treepre_insert))
3196 if (insert_into_preds_of_block (block, get_expression_id (expr),
3200 /* If all edges produce the same value and that value is
3201 an invariant, then the PHI has the same value on all
3202 edges. Note this. */
3203 else if (!cant_insert && all_same && eprime
3204 && eprime->kind == CONSTANT
3205 && !value_id_constant_p (val))
3209 bitmap_set_t exprset = VEC_index (bitmap_set_t,
3210 value_expressions, val);
3212 unsigned int new_val = get_expr_value_id (eprime);
3213 FOR_EACH_EXPR_ID_IN_SET (exprset, j, bi)
3215 pre_expr expr = expression_for_id (j);
3217 if (expr->kind == NAME)
3219 vn_ssa_aux_t info = VN_INFO (PRE_EXPR_NAME (expr));
3220 /* Just reset the value id and valnum so it is
3221 the same as the constant we have discovered. */
3222 info->valnum = PRE_EXPR_CONSTANT (eprime);
3223 info->value_id = new_val;
3224 pre_stats.constified++;
3232 VEC_free (pre_expr, heap, exprs);
3237 /* Perform insertion for partially anticipatable expressions. There
3238 is only one case we will perform insertion for these. This case is
3239 if the expression is partially anticipatable, and fully available.
3240 In this case, we know that putting it earlier will enable us to
3241 remove the later computation. */
3245 do_partial_partial_insertion (basic_block block, basic_block dom)
3247 bool new_stuff = false;
3248 VEC (pre_expr, heap) *exprs = sorted_array_from_bitmap_set (PA_IN (block));
3252 for (i = 0; VEC_iterate (pre_expr, exprs, i, expr); i++)
3254 if (expr->kind != NAME)
3259 bool cant_insert = false;
3262 pre_expr eprime = NULL;
3265 val = get_expr_value_id (expr);
3266 if (bitmap_set_contains_value (PHI_GEN (block), val))
3268 if (bitmap_set_contains_value (AVAIL_OUT (dom), val))
3271 avail = XCNEWVEC (pre_expr, last_basic_block);
3272 FOR_EACH_EDGE (pred, ei, block->preds)
3274 unsigned int vprime;
3275 pre_expr edoubleprime;
3277 /* This can happen in the very weird case
3278 that our fake infinite loop edges have caused a
3279 critical edge to appear. */
3280 if (EDGE_CRITICAL_P (pred))
3286 eprime = phi_translate (expr, ANTIC_IN (block),
3290 /* eprime will generally only be NULL if the
3291 value of the expression, translated
3292 through the PHI for this predecessor, is
3293 undefined. If that is the case, we can't
3294 make the expression fully redundant,
3295 because its value is undefined along a
3296 predecessor path. We can thus break out
3297 early because it doesn't matter what the
3298 rest of the results are. */
3305 eprime = fully_constant_expression (eprime);
3306 if (eprime->kind == CONSTANT)
3308 edoubleprime = eprime;
3312 vprime = get_expr_value_id (eprime);
3313 edoubleprime = bitmap_find_leader (AVAIL_OUT (bprime),
3317 if (edoubleprime == NULL)
3323 avail[bprime->index] = edoubleprime;
3327 /* If we can insert it, it's not the same value
3328 already existing along every predecessor, and
3329 it's defined by some predecessor, it is
3330 partially redundant. */
3331 if (!cant_insert && by_all && dbg_cnt (treepre_insert))
3333 pre_stats.pa_insert++;
3334 if (insert_into_preds_of_block (block, get_expression_id (expr),
3342 VEC_free (pre_expr, heap, exprs);
3347 insert_aux (basic_block block)
3350 bool new_stuff = false;
3355 dom = get_immediate_dominator (CDI_DOMINATORS, block);
3360 bitmap_set_t newset = NEW_SETS (dom);
3363 /* Note that we need to value_replace both NEW_SETS, and
3364 AVAIL_OUT. For both the case of NEW_SETS, the value may be
3365 represented by some non-simple expression here that we want
3366 to replace it with. */
3367 FOR_EACH_EXPR_ID_IN_SET (newset, i, bi)
3369 pre_expr expr = expression_for_id (i);
3370 bitmap_value_replace_in_set (NEW_SETS (block), expr);
3371 bitmap_value_replace_in_set (AVAIL_OUT (block), expr);
3374 if (!single_pred_p (block))
3376 new_stuff |= do_regular_insertion (block, dom);
3377 if (do_partial_partial)
3378 new_stuff |= do_partial_partial_insertion (block, dom);
3382 for (son = first_dom_son (CDI_DOMINATORS, block);
3384 son = next_dom_son (CDI_DOMINATORS, son))
3386 new_stuff |= insert_aux (son);
3392 /* Perform insertion of partially redundant values. */
3397 bool new_stuff = true;
3399 int num_iterations = 0;
3402 NEW_SETS (bb) = bitmap_set_new ();
3407 new_stuff = insert_aux (ENTRY_BLOCK_PTR);
3409 statistics_histogram_event (cfun, "insert iterations", num_iterations);
3413 /* Add OP to EXP_GEN (block), and possibly to the maximal set if it is
3414 not defined by a phi node.
3415 PHI nodes can't go in the maximal sets because they are not in
3416 TMP_GEN, so it is possible to get into non-monotonic situations
3417 during ANTIC calculation, because it will *add* bits. */
3420 add_to_exp_gen (basic_block block, tree op)
3425 if (TREE_CODE (op) == SSA_NAME && ssa_undefined_value_p (op))
3427 result = get_or_alloc_expr_for_name (op);
3428 bitmap_value_insert_into_set (EXP_GEN (block), result);
3429 if (TREE_CODE (op) != SSA_NAME
3430 || TREE_CODE (SSA_NAME_DEF_STMT (op)) != PHI_NODE)
3431 bitmap_value_insert_into_set (maximal_set, result);
3435 /* For each real store operation of the form
3436 *a = <value> that we see, create a corresponding fake store of the
3437 form storetmp_<version> = *a.
3439 This enables AVAIL computation to mark the results of stores as
3440 available. Without this, you'd need to do some computation to
3441 mark the result of stores as ANTIC and AVAIL at all the right
3443 To save memory, we keep the store
3444 statements pool allocated until we decide whether they are
3445 necessary or not. */
3448 insert_fake_stores (void)
3454 block_stmt_iterator bsi;
3455 for (bsi = bsi_start (block); !bsi_end_p (bsi); bsi_next (&bsi))
3457 tree stmt = bsi_stmt (bsi);
3459 /* We can't generate SSA names for stores that are complex
3460 or aggregate. We also want to ignore things whose
3461 virtual uses occur in abnormal phis. */
3463 if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT
3464 && (TREE_CODE (GIMPLE_STMT_OPERAND (stmt, 0)) == INDIRECT_REF
3465 || handled_component_p (GIMPLE_STMT_OPERAND (stmt, 0)))
3466 && !AGGREGATE_TYPE_P (TREE_TYPE (GIMPLE_STMT_OPERAND (stmt, 0))))
3470 tree lhs = GIMPLE_STMT_OPERAND (stmt, 0);
3471 tree rhs = GIMPLE_STMT_OPERAND (stmt, 1);
3472 tree new_tree, new_lhs;
3473 bool notokay = false;
3475 FOR_EACH_SSA_DEF_OPERAND (defp, stmt, iter, SSA_OP_VIRTUAL_DEFS)
3477 tree defvar = DEF_FROM_PTR (defp);
3478 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (defvar))
3488 if (!storetemp || TREE_TYPE (rhs) != TREE_TYPE (storetemp))
3490 storetemp = create_tmp_var (TREE_TYPE (rhs), "storetmp");
3491 if (TREE_CODE (TREE_TYPE (storetemp)) == VECTOR_TYPE
3492 || TREE_CODE (TREE_TYPE (storetemp)) == COMPLEX_TYPE)
3493 DECL_GIMPLE_REG_P (storetemp) = 1;
3494 get_var_ann (storetemp);
3497 new_tree = build_gimple_modify_stmt (NULL_TREE, lhs);
3498 new_lhs = make_ssa_name (storetemp, new_tree);
3499 GIMPLE_STMT_OPERAND (new_tree, 0) = new_lhs;
3500 create_ssa_artificial_load_stmt (new_tree, stmt, false);
3502 NECESSARY (new_tree) = 0;
3503 VEC_safe_push (tree, heap, inserted_exprs, new_tree);
3504 VEC_safe_push (tree, heap, need_creation, new_tree);
3505 bsi_insert_after (&bsi, new_tree, BSI_NEW_STMT);
3511 /* Turn the pool allocated fake stores that we created back into real
3512 GC allocated ones if they turned out to be necessary to PRE some
3516 realify_fake_stores (void)
3521 for (i = 0; VEC_iterate (tree, need_creation, i, stmt); i++)
3523 if (NECESSARY (stmt))
3525 block_stmt_iterator bsi, bsi2;
3528 /* Mark the temp variable as referenced */
3529 add_referenced_var (SSA_NAME_VAR (GIMPLE_STMT_OPERAND (stmt, 0)));
3531 /* Put the statement before the store in the IR stream
3532 as a plain ssa name copy. */
3533 bsi = bsi_for_stmt (stmt);
3535 rhs = GIMPLE_STMT_OPERAND (bsi_stmt (bsi), 1);
3536 GIMPLE_STMT_OPERAND (stmt, 1) = rhs;
3537 bsi2 = bsi_for_stmt (stmt);
3538 bsi_remove (&bsi2, true);
3539 bsi_insert_before (&bsi, stmt, BSI_SAME_STMT);
3542 release_defs (stmt);
3546 /* Create value ids for PHI in BLOCK. */
3549 make_values_for_phi (tree phi, basic_block block)
3551 tree result = PHI_RESULT (phi);
3552 /* We have no need for virtual phis, as they don't represent
3553 actual computations. */
3554 if (is_gimple_reg (result))
3556 pre_expr e = get_or_alloc_expr_for_name (result);
3557 add_to_value (get_expr_value_id (e), e);
3558 bitmap_insert_into_set (PHI_GEN (block), e);
3559 bitmap_value_insert_into_set (AVAIL_OUT (block), e);
3563 /* Compute the AVAIL set for all basic blocks.
3565 This function performs value numbering of the statements in each basic
3566 block. The AVAIL sets are built from information we glean while doing
3567 this value numbering, since the AVAIL sets contain only one entry per
3570 AVAIL_IN[BLOCK] = AVAIL_OUT[dom(BLOCK)].
3571 AVAIL_OUT[BLOCK] = AVAIL_IN[BLOCK] U PHI_GEN[BLOCK] U TMP_GEN[BLOCK]. */
3574 compute_avail (void)
3577 basic_block block, son;
3578 basic_block *worklist;
3582 /* For arguments with default definitions, we pretend they are
3583 defined in the entry block. */
3584 for (param = DECL_ARGUMENTS (current_function_decl);
3586 param = TREE_CHAIN (param))
3588 if (gimple_default_def (cfun, param) != NULL)
3590 tree def = gimple_default_def (cfun, param);
3591 pre_expr e = get_or_alloc_expr_for_name (def);
3593 add_to_value (get_expr_value_id (e), e);
3596 bitmap_insert_into_set (TMP_GEN (ENTRY_BLOCK_PTR), e);
3597 bitmap_value_insert_into_set (maximal_set, e);
3599 bitmap_value_insert_into_set (AVAIL_OUT (ENTRY_BLOCK_PTR), e);
3603 /* Likewise for the static chain decl. */
3604 if (cfun->static_chain_decl)
3606 param = cfun->static_chain_decl;
3607 if (gimple_default_def (cfun, param) != NULL)
3609 tree def = gimple_default_def (cfun, param);
3610 pre_expr e = get_or_alloc_expr_for_name (def);
3612 add_to_value (get_expr_value_id (e), e);
3615 bitmap_insert_into_set (TMP_GEN (ENTRY_BLOCK_PTR), e);
3616 bitmap_value_insert_into_set (maximal_set, e);
3618 bitmap_value_insert_into_set (AVAIL_OUT (ENTRY_BLOCK_PTR), e);
3622 /* Allocate the worklist. */
3623 worklist = XNEWVEC (basic_block, n_basic_blocks);
3625 /* Seed the algorithm by putting the dominator children of the entry
3626 block on the worklist. */
3627 for (son = first_dom_son (CDI_DOMINATORS, ENTRY_BLOCK_PTR);
3629 son = next_dom_son (CDI_DOMINATORS, son))
3630 worklist[sp++] = son;
3632 /* Loop until the worklist is empty. */
3635 block_stmt_iterator bsi;
3638 unsigned int stmt_uid = 1;
3640 /* Pick a block from the worklist. */
3641 block = worklist[--sp];
3643 /* Initially, the set of available values in BLOCK is that of
3644 its immediate dominator. */
3645 dom = get_immediate_dominator (CDI_DOMINATORS, block);
3647 bitmap_set_copy (AVAIL_OUT (block), AVAIL_OUT (dom));
3649 /* Generate values for PHI nodes. */
3650 for (phi = phi_nodes (block); phi; phi = PHI_CHAIN (phi))
3651 make_values_for_phi (phi, block);
3653 /* Now compute value numbers and populate value sets with all
3654 the expressions computed in BLOCK. */
3655 for (bsi = bsi_start (block); !bsi_end_p (bsi); bsi_next (&bsi))
3661 stmt = bsi_stmt (bsi);
3662 ann = stmt_ann (stmt);
3664 set_gimple_stmt_uid (stmt, stmt_uid++);
3666 FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_DEF)
3668 pre_expr e = get_or_alloc_expr_for_name (op);
3670 add_to_value (get_expr_value_id (e), e);
3673 bitmap_insert_into_set (TMP_GEN (block), e);
3674 bitmap_value_insert_into_set (maximal_set, e);
3676 bitmap_value_insert_into_set (AVAIL_OUT (block), e);
3679 switch (TREE_CODE (stmt))
3682 if (!ann->has_volatile_ops)
3683 FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_USE)
3684 add_to_exp_gen (block, op);
3686 case GIMPLE_MODIFY_STMT:
3688 tree rhs = GIMPLE_STMT_OPERAND (stmt, 1);
3689 if (!ann->has_volatile_ops
3690 && !tree_could_throw_p (stmt))
3692 pre_expr result = NULL;
3693 switch (TREE_CODE_CLASS (TREE_CODE (rhs)))
3696 if (is_exception_related (rhs))
3703 vn_nary_op_lookup (rhs, &nary);
3708 for (i = 0; i < nary->length; i++)
3709 if (TREE_CODE (nary->op[i]) == SSA_NAME)
3710 add_to_exp_gen (block, nary->op[i]);
3712 result = (pre_expr) pool_alloc (pre_expr_pool);
3713 result->kind = NARY;
3715 PRE_EXPR_NARY (result) = nary;
3719 if (!can_value_number_call (rhs))
3722 case tcc_declaration:
3727 vn_reference_op_t vro;
3729 vn_reference_lookup (rhs,
3730 shared_vuses_from_stmt (stmt),
3735 for (i = 0; VEC_iterate (vn_reference_op_s,
3739 if (vro->op0 && TREE_CODE (vro->op0) == SSA_NAME)
3740 add_to_exp_gen (block, vro->op0);
3741 if (vro->op1 && TREE_CODE (vro->op1) == SSA_NAME)
3742 add_to_exp_gen (block, vro->op1);
3744 result = (pre_expr) pool_alloc (pre_expr_pool);
3745 result->kind = REFERENCE;
3747 PRE_EXPR_REFERENCE (result) = ref;
3752 /* For any other statement that we don't
3753 recognize, simply add all referenced
3754 SSA_NAMEs to EXP_GEN. */
3755 FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_USE)
3756 add_to_exp_gen (block, op);
3760 get_or_alloc_expression_id (result);
3761 add_to_value (get_expr_value_id (result), result);
3764 bitmap_value_insert_into_set (EXP_GEN (block),
3766 bitmap_value_insert_into_set (maximal_set, result);
3779 /* Put the dominator children of BLOCK on the worklist of blocks
3780 to compute available sets for. */
3781 for (son = first_dom_son (CDI_DOMINATORS, block);
3783 son = next_dom_son (CDI_DOMINATORS, son))
3784 worklist[sp++] = son;
3790 /* Insert the expression for SSA_VN that SCCVN thought would be simpler
3791 than the available expressions for it. The insertion point is
3792 right before the first use in STMT. Returns the SSA_NAME that should
3793 be used for replacement. */
3796 do_SCCVN_insertion (tree stmt, tree ssa_vn)
3798 basic_block bb = bb_for_stmt (stmt);
3799 block_stmt_iterator bsi;
3803 /* First create a value expression from the expression we want
3804 to insert and associate it with the value handle for SSA_VN. */
3806 /* TODO: Handle complex expressions. */
3807 e = get_or_alloc_expr_for (VN_INFO (ssa_vn)->expr);
3811 /* Then use create_expression_by_pieces to generate a valid
3812 expression to insert at this point of the IL stream. */
3813 stmts = alloc_stmt_list ();
3814 expr = create_expression_by_pieces (bb, e, stmts, stmt,
3816 if (expr == NULL_TREE)
3818 bsi = bsi_for_stmt (stmt);
3819 bsi_insert_before (&bsi, stmts, BSI_SAME_STMT);
3824 /* Eliminate fully redundant computations. */
3830 unsigned int todo = 0;
3834 block_stmt_iterator i;
3836 for (i = bsi_start (b); !bsi_end_p (i); bsi_next (&i))
3838 tree stmt = bsi_stmt (i);
3840 /* Lookup the RHS of the expression, see if we have an
3841 available computation for it. If so, replace the RHS with
3842 the available computation. */
3843 if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT
3844 && TREE_CODE (GIMPLE_STMT_OPERAND (stmt, 0)) == SSA_NAME
3845 && TREE_CODE (GIMPLE_STMT_OPERAND (stmt, 1)) != SSA_NAME
3846 && !is_gimple_min_invariant (GIMPLE_STMT_OPERAND (stmt, 1))
3847 && !stmt_ann (stmt)->has_volatile_ops)
3849 tree lhs = GIMPLE_STMT_OPERAND (stmt, 0);
3850 tree *rhs_p = &GIMPLE_STMT_OPERAND (stmt, 1);
3852 pre_expr lhsexpr = get_or_alloc_expr_for_name (lhs);
3853 pre_expr sprimeexpr;
3855 sprimeexpr = bitmap_find_leader (AVAIL_OUT (b),
3856 get_expr_value_id (lhsexpr),
3861 if (sprimeexpr->kind == CONSTANT)
3862 sprime = PRE_EXPR_CONSTANT (sprimeexpr);
3863 else if (sprimeexpr->kind == NAME)
3864 sprime = PRE_EXPR_NAME (sprimeexpr);
3869 /* If there is no existing leader but SCCVN knows this
3870 value is constant, use that constant. */
3871 if (!sprime && is_gimple_min_invariant (VN_INFO (lhs)->valnum))
3873 sprime = fold_convert (TREE_TYPE (lhs),
3874 VN_INFO (lhs)->valnum);
3876 if (dump_file && (dump_flags & TDF_DETAILS))
3878 fprintf (dump_file, "Replaced ");
3879 print_generic_expr (dump_file, *rhs_p, 0);
3880 fprintf (dump_file, " with ");
3881 print_generic_expr (dump_file, sprime, 0);
3882 fprintf (dump_file, " in ");
3883 print_generic_stmt (dump_file, stmt, 0);
3885 pre_stats.eliminations++;
3886 propagate_tree_value (rhs_p, sprime);
3891 /* If there is no existing usable leader but SCCVN thinks
3892 it has an expression it wants to use as replacement,
3894 if (!sprime || sprime == lhs)
3896 tree val = VN_INFO (lhs)->valnum;
3898 && TREE_CODE (val) == SSA_NAME
3899 && VN_INFO (val)->needs_insertion
3900 && can_PRE_operation (VN_INFO (val)->expr))
3901 sprime = do_SCCVN_insertion (stmt, val);
3905 && (TREE_CODE (*rhs_p) != SSA_NAME
3906 || may_propagate_copy (*rhs_p, sprime)))
3908 gcc_assert (sprime != *rhs_p);
3910 if (dump_file && (dump_flags & TDF_DETAILS))
3912 fprintf (dump_file, "Replaced ");
3913 print_generic_expr (dump_file, *rhs_p, 0);
3914 fprintf (dump_file, " with ");
3915 print_generic_expr (dump_file, sprime, 0);
3916 fprintf (dump_file, " in ");
3917 print_generic_stmt (dump_file, stmt, 0);
3920 if (TREE_CODE (sprime) == SSA_NAME)
3921 NECESSARY (SSA_NAME_DEF_STMT (sprime)) = 1;
3922 /* We need to make sure the new and old types actually match,
3923 which may require adding a simple cast, which fold_convert
3925 if (TREE_CODE (*rhs_p) != SSA_NAME
3926 && !useless_type_conversion_p (TREE_TYPE (*rhs_p),
3927 TREE_TYPE (sprime)))
3928 sprime = fold_convert (TREE_TYPE (*rhs_p), sprime);
3930 pre_stats.eliminations++;
3931 propagate_tree_value (rhs_p, sprime);
3934 /* If we removed EH side effects from the statement, clean
3935 its EH information. */
3936 if (maybe_clean_or_replace_eh_stmt (stmt, stmt))
3938 bitmap_set_bit (need_eh_cleanup,
3939 bb_for_stmt (stmt)->index);
3940 if (dump_file && (dump_flags & TDF_DETAILS))
3941 fprintf (dump_file, " Removed EH side effects.\n");
3945 /* Visit COND_EXPRs and fold the comparison with the
3946 available value-numbers. */
3947 else if (TREE_CODE (stmt) == COND_EXPR
3948 && COMPARISON_CLASS_P (COND_EXPR_COND (stmt)))
3950 tree cond = COND_EXPR_COND (stmt);
3951 tree op0 = TREE_OPERAND (cond, 0);
3952 tree op1 = TREE_OPERAND (cond, 1);
3955 if (TREE_CODE (op0) == SSA_NAME)
3956 op0 = VN_INFO (op0)->valnum;
3957 if (TREE_CODE (op1) == SSA_NAME)
3958 op1 = VN_INFO (op1)->valnum;
3959 result = fold_binary (TREE_CODE (cond), TREE_TYPE (cond),
3961 if (result && TREE_CODE (result) == INTEGER_CST)
3963 COND_EXPR_COND (stmt) = result;
3965 todo = TODO_cleanup_cfg;
3968 else if (TREE_CODE (stmt) == COND_EXPR
3969 && TREE_CODE (COND_EXPR_COND (stmt)) == SSA_NAME)
3971 tree op = COND_EXPR_COND (stmt);
3972 op = VN_INFO (op)->valnum;
3973 if (TREE_CODE (op) == INTEGER_CST)
3975 COND_EXPR_COND (stmt) = integer_zerop (op)
3976 ? boolean_false_node : boolean_true_node;
3978 todo = TODO_cleanup_cfg;
3987 /* Borrow a bit of tree-ssa-dce.c for the moment.
3988 XXX: In 4.1, we should be able to just run a DCE pass after PRE, though
3989 this may be a bit faster, and we may want critical edges kept split. */
3991 /* If OP's defining statement has not already been determined to be necessary,
3992 mark that statement necessary. Return the stmt, if it is newly
3996 mark_operand_necessary (tree op)
4002 if (TREE_CODE (op) != SSA_NAME)
4005 stmt = SSA_NAME_DEF_STMT (op);
4008 if (NECESSARY (stmt)
4009 || IS_EMPTY_STMT (stmt))
4012 NECESSARY (stmt) = 1;
4016 /* Because we don't follow exactly the standard PRE algorithm, and decide not
4017 to insert PHI nodes sometimes, and because value numbering of casts isn't
4018 perfect, we sometimes end up inserting dead code. This simple DCE-like
4019 pass removes any insertions we made that weren't actually used. */
4022 remove_dead_inserted_code (void)
4024 VEC(tree,heap) *worklist = NULL;
4028 worklist = VEC_alloc (tree, heap, VEC_length (tree, inserted_exprs));
4029 for (i = 0; VEC_iterate (tree, inserted_exprs, i, t); i++)
4032 VEC_quick_push (tree, worklist, t);
4034 while (VEC_length (tree, worklist) > 0)
4036 t = VEC_pop (tree, worklist);
4038 /* PHI nodes are somewhat special in that each PHI alternative has
4039 data and control dependencies. All the statements feeding the
4040 PHI node's arguments are always necessary. */
4041 if (TREE_CODE (t) == PHI_NODE)
4045 VEC_reserve (tree, heap, worklist, PHI_NUM_ARGS (t));
4046 for (k = 0; k < PHI_NUM_ARGS (t); k++)
4048 tree arg = PHI_ARG_DEF (t, k);
4049 if (TREE_CODE (arg) == SSA_NAME)
4051 arg = mark_operand_necessary (arg);
4053 VEC_quick_push (tree, worklist, arg);
4059 /* Propagate through the operands. Examine all the USE, VUSE and
4060 VDEF operands in this statement. Mark all the statements
4061 which feed this statement's uses as necessary. */
4065 /* The operands of VDEF expressions are also needed as they
4066 represent potential definitions that may reach this
4067 statement (VDEF operands allow us to follow def-def
4070 FOR_EACH_SSA_TREE_OPERAND (use, t, iter, SSA_OP_ALL_USES)
4072 tree n = mark_operand_necessary (use);
4074 VEC_safe_push (tree, heap, worklist, n);
4079 for (i = 0; VEC_iterate (tree, inserted_exprs, i, t); i++)
4083 block_stmt_iterator bsi;
4085 if (dump_file && (dump_flags & TDF_DETAILS))
4087 fprintf (dump_file, "Removing unnecessary insertion:");
4088 print_generic_stmt (dump_file, t, 0);
4091 if (TREE_CODE (t) == PHI_NODE)
4093 remove_phi_node (t, NULL_TREE, true);
4097 bsi = bsi_for_stmt (t);
4098 bsi_remove (&bsi, true);
4103 VEC_free (tree, heap, worklist);
4106 /* Initialize data structures used by PRE. */
4109 init_pre (bool do_fre)
4113 next_expression_id = 1;
4115 VEC_safe_push (pre_expr, heap, expressions, NULL);
4116 value_expressions = VEC_alloc (bitmap_set_t, heap, get_max_value_id () + 1);
4117 VEC_safe_grow_cleared (bitmap_set_t, heap, value_expressions,
4118 get_max_value_id() + 1);
4122 inserted_exprs = NULL;
4123 need_creation = NULL;
4124 pretemp = NULL_TREE;
4125 storetemp = NULL_TREE;
4126 prephitemp = NULL_TREE;
4128 connect_infinite_loops_to_exit ();
4129 memset (&pre_stats, 0, sizeof (pre_stats));
4132 postorder = XNEWVEC (int, n_basic_blocks - NUM_FIXED_BLOCKS);
4133 post_order_compute (postorder, false, false);
4136 bb->aux = XCNEWVEC (struct bb_bitmap_sets, 1);
4138 calculate_dominance_info (CDI_POST_DOMINATORS);
4139 calculate_dominance_info (CDI_DOMINATORS);
4141 bitmap_obstack_initialize (&grand_bitmap_obstack);
4142 phi_translate_table = htab_create (5110, expr_pred_trans_hash,
4143 expr_pred_trans_eq, free);
4144 expression_to_id = htab_create (num_ssa_names * 3,
4147 seen_during_translate = BITMAP_ALLOC (&grand_bitmap_obstack);
4148 bitmap_set_pool = create_alloc_pool ("Bitmap sets",
4149 sizeof (struct bitmap_set), 30);
4150 pre_expr_pool = create_alloc_pool ("pre_expr nodes",
4151 sizeof (struct pre_expr_d), 30);
4154 EXP_GEN (bb) = bitmap_set_new ();
4155 PHI_GEN (bb) = bitmap_set_new ();
4156 TMP_GEN (bb) = bitmap_set_new ();
4157 AVAIL_OUT (bb) = bitmap_set_new ();
4159 maximal_set = in_fre ? NULL : bitmap_set_new ();
4161 need_eh_cleanup = BITMAP_ALLOC (NULL);
4165 /* Deallocate data structures used by PRE. */
4173 VEC_free (bitmap_set_t, heap, value_expressions);
4174 VEC_free (tree, heap, inserted_exprs);
4175 VEC_free (tree, heap, need_creation);
4176 bitmap_obstack_release (&grand_bitmap_obstack);
4177 free_alloc_pool (bitmap_set_pool);
4178 free_alloc_pool (pre_expr_pool);
4179 htab_delete (phi_translate_table);
4180 htab_delete (expression_to_id);
4181 remove_fake_exit_edges ();
4189 free_dominance_info (CDI_POST_DOMINATORS);
4191 if (!bitmap_empty_p (need_eh_cleanup))
4193 tree_purge_all_dead_eh_edges (need_eh_cleanup);
4194 cleanup_tree_cfg ();
4197 BITMAP_FREE (need_eh_cleanup);
4199 if (current_loops != NULL)
4200 loop_optimizer_finalize ();
4203 /* Main entry point to the SSA-PRE pass. DO_FRE is true if the caller
4204 only wants to do full redundancy elimination. */
4207 execute_pre (bool do_fre)
4209 unsigned int todo = 0;
4211 do_partial_partial = optimize > 2;
4213 /* This has to happen before SCCVN runs because
4214 loop_optimizer_init may create new phis, etc. */
4216 loop_optimizer_init (LOOPS_NORMAL);
4218 insert_fake_stores ();
4220 if (!run_scc_vn (do_fre))
4224 remove_dead_inserted_code ();
4225 loop_optimizer_finalize ();
4233 /* Collect and value number expressions computed in each basic block. */
4236 if (dump_file && (dump_flags & TDF_DETAILS))
4242 print_bitmap_set (dump_file, EXP_GEN (bb), "exp_gen", bb->index);
4243 print_bitmap_set (dump_file, TMP_GEN (bb), "tmp_gen",
4245 print_bitmap_set (dump_file, AVAIL_OUT (bb), "avail_out",
4250 /* Insert can get quite slow on an incredibly large number of basic
4251 blocks due to some quadratic behavior. Until this behavior is
4252 fixed, don't run it when he have an incredibly large number of
4253 bb's. If we aren't going to run insert, there is no point in
4254 computing ANTIC, either, even though it's plenty fast. */
4255 if (!do_fre && n_basic_blocks < 4000)
4261 /* Remove all the redundant expressions. */
4262 todo |= eliminate ();
4264 statistics_counter_event (cfun, "Insertions", pre_stats.insertions);
4265 statistics_counter_event (cfun, "PA inserted", pre_stats.pa_insert);
4266 statistics_counter_event (cfun, "New PHIs", pre_stats.phis);
4267 statistics_counter_event (cfun, "Eliminated", pre_stats.eliminations);
4268 statistics_counter_event (cfun, "Constified", pre_stats.constified);
4269 bsi_commit_edge_inserts ();
4271 clear_expression_ids ();
4275 remove_dead_inserted_code ();
4277 realify_fake_stores ();
4285 /* Gate and execute functions for PRE. */
4290 return TODO_rebuild_alias | execute_pre (false);
4296 return flag_tree_pre != 0;
4299 struct gimple_opt_pass pass_pre =
4304 gate_pre, /* gate */
4305 do_pre, /* execute */
4308 0, /* static_pass_number */
4309 TV_TREE_PRE, /* tv_id */
4310 PROP_no_crit_edges | PROP_cfg
4311 | PROP_ssa | PROP_alias, /* properties_required */
4312 0, /* properties_provided */
4313 0, /* properties_destroyed */
4314 0, /* todo_flags_start */
4315 TODO_update_ssa_only_virtuals | TODO_dump_func | TODO_ggc_collect
4316 | TODO_verify_ssa /* todo_flags_finish */
4321 /* Gate and execute functions for FRE. */
4326 return execute_pre (true);
4332 return flag_tree_fre != 0;
4335 struct gimple_opt_pass pass_fre =
4340 gate_fre, /* gate */
4341 execute_fre, /* execute */
4344 0, /* static_pass_number */
4345 TV_TREE_FRE, /* tv_id */
4346 PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */
4347 0, /* properties_provided */
4348 0, /* properties_destroyed */
4349 0, /* todo_flags_start */
4350 TODO_dump_func | TODO_ggc_collect | TODO_verify_ssa /* todo_flags_finish */