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"
34 #include "tree-dump.h"
38 #include "tree-iterator.h"
40 #include "alloc-pool.h"
42 #include "tree-pass.h"
45 #include "langhooks.h"
47 #include "tree-ssa-sccvn.h"
53 1. Avail sets can be shared by making an avail_find_leader that
54 walks up the dominator tree and looks in those avail sets.
55 This might affect code optimality, it's unclear right now.
56 2. Strength reduction can be performed by anticipating expressions
57 we can repair later on.
58 3. We can do back-substitution or smarter value numbering to catch
59 commutative expressions split up over multiple statements.
62 /* For ease of terminology, "expression node" in the below refers to
63 every expression node but GIMPLE_ASSIGN, because GIMPLE_ASSIGNs
64 represent the actual statement containing the expressions we care about,
65 and we cache the value number by putting it in the expression. */
69 First we walk the statements to generate the AVAIL sets, the
70 EXP_GEN sets, and the tmp_gen sets. EXP_GEN sets represent the
71 generation of values/expressions by a given block. We use them
72 when computing the ANTIC sets. The AVAIL sets consist of
73 SSA_NAME's that represent values, so we know what values are
74 available in what blocks. AVAIL is a forward dataflow problem. In
75 SSA, values are never killed, so we don't need a kill set, or a
76 fixpoint iteration, in order to calculate the AVAIL sets. In
77 traditional parlance, AVAIL sets tell us the downsafety of the
80 Next, we generate the ANTIC sets. These sets represent the
81 anticipatable expressions. ANTIC is a backwards dataflow
82 problem. An expression is anticipatable in a given block if it could
83 be generated in that block. This means that if we had to perform
84 an insertion in that block, of the value of that expression, we
85 could. Calculating the ANTIC sets requires phi translation of
86 expressions, because the flow goes backwards through phis. We must
87 iterate to a fixpoint of the ANTIC sets, because we have a kill
88 set. Even in SSA form, values are not live over the entire
89 function, only from their definition point onwards. So we have to
90 remove values from the ANTIC set once we go past the definition
91 point of the leaders that make them up.
92 compute_antic/compute_antic_aux performs this computation.
94 Third, we perform insertions to make partially redundant
95 expressions fully redundant.
97 An expression is partially redundant (excluding partial
100 1. It is AVAIL in some, but not all, of the predecessors of a
102 2. It is ANTIC in all the predecessors.
104 In order to make it fully redundant, we insert the expression into
105 the predecessors where it is not available, but is ANTIC.
107 For the partial anticipation case, we only perform insertion if it
108 is partially anticipated in some block, and fully available in all
111 insert/insert_aux/do_regular_insertion/do_partial_partial_insertion
112 performs these steps.
114 Fourth, we eliminate fully redundant expressions.
115 This is a simple statement walk that replaces redundant
116 calculations with the now available values. */
118 /* Representations of value numbers:
120 Value numbers are represented by a representative SSA_NAME. We
121 will create fake SSA_NAME's in situations where we need a
122 representative but do not have one (because it is a complex
123 expression). In order to facilitate storing the value numbers in
124 bitmaps, and keep the number of wasted SSA_NAME's down, we also
125 associate a value_id with each value number, and create full blown
126 ssa_name's only where we actually need them (IE in operands of
127 existing expressions).
129 Theoretically you could replace all the value_id's with
130 SSA_NAME_VERSION, but this would allocate a large number of
131 SSA_NAME's (which are each > 30 bytes) just to get a 4 byte number.
132 It would also require an additional indirection at each point we
135 /* Representation of expressions on value numbers:
137 Expressions consisting of value numbers are represented the same
138 way as our VN internally represents them, with an additional
139 "pre_expr" wrapping around them in order to facilitate storing all
140 of the expressions in the same sets. */
142 /* Representation of sets:
144 The dataflow sets do not need to be sorted in any particular order
145 for the majority of their lifetime, are simply represented as two
146 bitmaps, one that keeps track of values present in the set, and one
147 that keeps track of expressions present in the set.
149 When we need them in topological order, we produce it on demand by
150 transforming the bitmap into an array and sorting it into topo
153 /* Type of expression, used to know which member of the PRE_EXPR union
164 typedef union pre_expr_union_d
169 vn_reference_t reference;
172 typedef struct pre_expr_d
174 enum pre_expr_kind kind;
179 #define PRE_EXPR_NAME(e) (e)->u.name
180 #define PRE_EXPR_NARY(e) (e)->u.nary
181 #define PRE_EXPR_REFERENCE(e) (e)->u.reference
182 #define PRE_EXPR_CONSTANT(e) (e)->u.constant
185 pre_expr_eq (const void *p1, const void *p2)
187 const struct pre_expr_d *e1 = (const struct pre_expr_d *) p1;
188 const struct pre_expr_d *e2 = (const struct pre_expr_d *) p2;
190 if (e1->kind != e2->kind)
196 return vn_constant_eq_with_type (PRE_EXPR_CONSTANT (e1),
197 PRE_EXPR_CONSTANT (e2));
199 return PRE_EXPR_NAME (e1) == PRE_EXPR_NAME (e2);
201 return vn_nary_op_eq (PRE_EXPR_NARY (e1), PRE_EXPR_NARY (e2));
203 return vn_reference_eq (PRE_EXPR_REFERENCE (e1),
204 PRE_EXPR_REFERENCE (e2));
211 pre_expr_hash (const void *p1)
213 const struct pre_expr_d *e = (const struct pre_expr_d *) p1;
217 return vn_hash_constant_with_type (PRE_EXPR_CONSTANT (e));
219 return iterative_hash_expr (PRE_EXPR_NAME (e), 0);
221 return vn_nary_op_compute_hash (PRE_EXPR_NARY (e));
223 return vn_reference_compute_hash (PRE_EXPR_REFERENCE (e));
230 /* Next global expression id number. */
231 static unsigned int next_expression_id;
233 /* Mapping from expression to id number we can use in bitmap sets. */
234 DEF_VEC_P (pre_expr);
235 DEF_VEC_ALLOC_P (pre_expr, heap);
236 static VEC(pre_expr, heap) *expressions;
237 static htab_t expression_to_id;
239 /* Allocate an expression id for EXPR. */
241 static inline unsigned int
242 alloc_expression_id (pre_expr expr)
245 /* Make sure we won't overflow. */
246 gcc_assert (next_expression_id + 1 > next_expression_id);
247 expr->id = next_expression_id++;
248 VEC_safe_push (pre_expr, heap, expressions, expr);
249 slot = htab_find_slot (expression_to_id, expr, INSERT);
252 return next_expression_id - 1;
255 /* Return the expression id for tree EXPR. */
257 static inline unsigned int
258 get_expression_id (const pre_expr expr)
263 static inline unsigned int
264 lookup_expression_id (const pre_expr expr)
268 slot = htab_find_slot (expression_to_id, expr, NO_INSERT);
271 return ((pre_expr)*slot)->id;
274 /* Return the existing expression id for EXPR, or create one if one
275 does not exist yet. */
277 static inline unsigned int
278 get_or_alloc_expression_id (pre_expr expr)
280 unsigned int id = lookup_expression_id (expr);
282 return alloc_expression_id (expr);
283 return expr->id = id;
286 /* Return the expression that has expression id ID */
288 static inline pre_expr
289 expression_for_id (unsigned int id)
291 return VEC_index (pre_expr, expressions, id);
294 /* Free the expression id field in all of our expressions,
295 and then destroy the expressions array. */
298 clear_expression_ids (void)
300 VEC_free (pre_expr, heap, expressions);
303 static alloc_pool pre_expr_pool;
305 /* Given an SSA_NAME NAME, get or create a pre_expr to represent it. */
308 get_or_alloc_expr_for_name (tree name)
310 pre_expr result = (pre_expr) pool_alloc (pre_expr_pool);
311 unsigned int result_id;
315 PRE_EXPR_NAME (result) = name;
316 result_id = lookup_expression_id (result);
319 pool_free (pre_expr_pool, result);
320 result = expression_for_id (result_id);
323 get_or_alloc_expression_id (result);
327 static bool in_fre = false;
329 /* An unordered bitmap set. One bitmap tracks values, the other,
331 typedef struct bitmap_set
337 #define FOR_EACH_EXPR_ID_IN_SET(set, id, bi) \
338 EXECUTE_IF_SET_IN_BITMAP((set)->expressions, 0, (id), (bi))
340 /* Mapping from value id to expressions with that value_id. */
341 DEF_VEC_P (bitmap_set_t);
342 DEF_VEC_ALLOC_P (bitmap_set_t, heap);
343 static VEC(bitmap_set_t, heap) *value_expressions;
345 /* Sets that we need to keep track of. */
346 typedef struct bb_bitmap_sets
348 /* The EXP_GEN set, which represents expressions/values generated in
350 bitmap_set_t exp_gen;
352 /* The PHI_GEN set, which represents PHI results generated in a
354 bitmap_set_t phi_gen;
356 /* The TMP_GEN set, which represents results/temporaries generated
357 in a basic block. IE the LHS of an expression. */
358 bitmap_set_t tmp_gen;
360 /* The AVAIL_OUT set, which represents which values are available in
361 a given basic block. */
362 bitmap_set_t avail_out;
364 /* The ANTIC_IN set, which represents which values are anticipatable
365 in a given basic block. */
366 bitmap_set_t antic_in;
368 /* The PA_IN set, which represents which values are
369 partially anticipatable in a given basic block. */
372 /* The NEW_SETS set, which is used during insertion to augment the
373 AVAIL_OUT set of blocks with the new insertions performed during
374 the current iteration. */
375 bitmap_set_t new_sets;
377 /* True if we have visited this block during ANTIC calculation. */
378 unsigned int visited:1;
380 /* True we have deferred processing this block during ANTIC
381 calculation until its successor is processed. */
382 unsigned int deferred : 1;
385 #define EXP_GEN(BB) ((bb_value_sets_t) ((BB)->aux))->exp_gen
386 #define PHI_GEN(BB) ((bb_value_sets_t) ((BB)->aux))->phi_gen
387 #define TMP_GEN(BB) ((bb_value_sets_t) ((BB)->aux))->tmp_gen
388 #define AVAIL_OUT(BB) ((bb_value_sets_t) ((BB)->aux))->avail_out
389 #define ANTIC_IN(BB) ((bb_value_sets_t) ((BB)->aux))->antic_in
390 #define PA_IN(BB) ((bb_value_sets_t) ((BB)->aux))->pa_in
391 #define NEW_SETS(BB) ((bb_value_sets_t) ((BB)->aux))->new_sets
392 #define BB_VISITED(BB) ((bb_value_sets_t) ((BB)->aux))->visited
393 #define BB_DEFERRED(BB) ((bb_value_sets_t) ((BB)->aux))->deferred
396 /* Maximal set of values, used to initialize the ANTIC problem, which
397 is an intersection problem. */
398 static bitmap_set_t maximal_set;
400 /* Basic block list in postorder. */
401 static int *postorder;
403 /* This structure is used to keep track of statistics on what
404 optimization PRE was able to perform. */
407 /* The number of RHS computations eliminated by PRE. */
410 /* The number of new expressions/temporaries generated by PRE. */
413 /* The number of inserts found due to partial anticipation */
416 /* The number of new PHI nodes added by PRE. */
419 /* The number of values found constant. */
424 static bool do_partial_partial;
425 static pre_expr bitmap_find_leader (bitmap_set_t, unsigned int, gimple);
426 static void bitmap_value_insert_into_set (bitmap_set_t, pre_expr);
427 static void bitmap_value_replace_in_set (bitmap_set_t, pre_expr);
428 static void bitmap_set_copy (bitmap_set_t, bitmap_set_t);
429 static bool bitmap_set_contains_value (bitmap_set_t, unsigned int);
430 static void bitmap_insert_into_set (bitmap_set_t, pre_expr);
431 static void bitmap_insert_into_set_1 (bitmap_set_t, pre_expr, bool);
432 static bitmap_set_t bitmap_set_new (void);
433 static tree create_expression_by_pieces (basic_block, pre_expr, gimple_seq *,
435 static tree find_or_generate_expression (basic_block, pre_expr, gimple_seq *,
438 /* We can add and remove elements and entries to and from sets
439 and hash tables, so we use alloc pools for them. */
441 static alloc_pool bitmap_set_pool;
442 static bitmap_obstack grand_bitmap_obstack;
444 /* To avoid adding 300 temporary variables when we only need one, we
445 only create one temporary variable, on demand, and build ssa names
446 off that. We do have to change the variable if the types don't
447 match the current variable's type. */
449 static tree storetemp;
450 static tree prephitemp;
452 /* Set of blocks with statements that have had its EH information
454 static bitmap need_eh_cleanup;
456 /* Which expressions have been seen during a given phi translation. */
457 static bitmap seen_during_translate;
459 /* The phi_translate_table caches phi translations for a given
460 expression and predecessor. */
462 static htab_t phi_translate_table;
464 /* A three tuple {e, pred, v} used to cache phi translations in the
465 phi_translate_table. */
467 typedef struct expr_pred_trans_d
469 /* The expression. */
472 /* The predecessor block along which we translated the expression. */
475 /* The value that resulted from the translation. */
478 /* The hashcode for the expression, pred pair. This is cached for
481 } *expr_pred_trans_t;
482 typedef const struct expr_pred_trans_d *const_expr_pred_trans_t;
484 /* Return the hash value for a phi translation table entry. */
487 expr_pred_trans_hash (const void *p)
489 const_expr_pred_trans_t const ve = (const_expr_pred_trans_t) p;
493 /* Return true if two phi translation table entries are the same.
494 P1 and P2 should point to the expr_pred_trans_t's to be compared.*/
497 expr_pred_trans_eq (const void *p1, const void *p2)
499 const_expr_pred_trans_t const ve1 = (const_expr_pred_trans_t) p1;
500 const_expr_pred_trans_t const ve2 = (const_expr_pred_trans_t) p2;
501 basic_block b1 = ve1->pred;
502 basic_block b2 = ve2->pred;
504 /* If they are not translations for the same basic block, they can't
508 return pre_expr_eq (ve1->e, ve2->e);
511 /* Search in the phi translation table for the translation of
512 expression E in basic block PRED.
513 Return the translated value, if found, NULL otherwise. */
515 static inline pre_expr
516 phi_trans_lookup (pre_expr e, basic_block pred)
519 struct expr_pred_trans_d ept;
523 ept.hashcode = iterative_hash_hashval_t (pre_expr_hash (e), pred->index);
524 slot = htab_find_slot_with_hash (phi_translate_table, &ept, ept.hashcode,
529 return ((expr_pred_trans_t) *slot)->v;
533 /* Add the tuple mapping from {expression E, basic block PRED} to
534 value V, to the phi translation table. */
537 phi_trans_add (pre_expr e, pre_expr v, basic_block pred)
540 expr_pred_trans_t new_pair = XNEW (struct expr_pred_trans_d);
542 new_pair->pred = pred;
544 new_pair->hashcode = iterative_hash_hashval_t (pre_expr_hash (e),
547 slot = htab_find_slot_with_hash (phi_translate_table, new_pair,
548 new_pair->hashcode, INSERT);
551 *slot = (void *) new_pair;
555 /* Add expression E to the expression set of value id V. */
558 add_to_value (unsigned int v, pre_expr e)
562 if (v >= VEC_length (bitmap_set_t, value_expressions))
564 VEC_safe_grow_cleared (bitmap_set_t, heap, value_expressions,
568 set = VEC_index (bitmap_set_t, value_expressions, v);
571 set = bitmap_set_new ();
572 VEC_replace (bitmap_set_t, value_expressions, v, set);
575 bitmap_insert_into_set_1 (set, e, true);
578 /* Create a new bitmap set and return it. */
581 bitmap_set_new (void)
583 bitmap_set_t ret = (bitmap_set_t) pool_alloc (bitmap_set_pool);
584 ret->expressions = BITMAP_ALLOC (&grand_bitmap_obstack);
585 ret->values = BITMAP_ALLOC (&grand_bitmap_obstack);
589 /* Return the value id for a PRE expression EXPR. */
592 get_expr_value_id (pre_expr expr)
599 id = get_constant_value_id (PRE_EXPR_CONSTANT (expr));
602 id = get_or_alloc_constant_value_id (PRE_EXPR_CONSTANT (expr));
603 add_to_value (id, expr);
608 return VN_INFO (PRE_EXPR_NAME (expr))->value_id;
610 return PRE_EXPR_NARY (expr)->value_id;
612 return PRE_EXPR_REFERENCE (expr)->value_id;
618 /* Remove an expression EXPR from a bitmapped set. */
621 bitmap_remove_from_set (bitmap_set_t set, pre_expr expr)
623 unsigned int val = get_expr_value_id (expr);
624 if (!value_id_constant_p (val))
626 bitmap_clear_bit (set->values, val);
627 bitmap_clear_bit (set->expressions, get_expression_id (expr));
632 bitmap_insert_into_set_1 (bitmap_set_t set, pre_expr expr,
633 bool allow_constants)
635 unsigned int val = get_expr_value_id (expr);
636 if (allow_constants || !value_id_constant_p (val))
638 /* We specifically expect this and only this function to be able to
639 insert constants into a set. */
640 bitmap_set_bit (set->values, val);
641 bitmap_set_bit (set->expressions, get_or_alloc_expression_id (expr));
645 /* Insert an expression EXPR into a bitmapped set. */
648 bitmap_insert_into_set (bitmap_set_t set, pre_expr expr)
650 bitmap_insert_into_set_1 (set, expr, false);
653 /* Copy a bitmapped set ORIG, into bitmapped set DEST. */
656 bitmap_set_copy (bitmap_set_t dest, bitmap_set_t orig)
658 bitmap_copy (dest->expressions, orig->expressions);
659 bitmap_copy (dest->values, orig->values);
663 /* Free memory used up by SET. */
665 bitmap_set_free (bitmap_set_t set)
667 BITMAP_FREE (set->expressions);
668 BITMAP_FREE (set->values);
672 /* A comparison function for use in qsort to top sort a bitmap set. Simply
673 subtracts value ids, since they are created with leaves before
674 their parent users (IE topological order). */
677 value_id_compare (const void *pa, const void *pb)
679 const unsigned int vha = get_expr_value_id (*((const pre_expr *)pa));
680 const unsigned int vhb = get_expr_value_id (*((const pre_expr *)pb));
685 /* Generate an topological-ordered array of bitmap set SET. */
687 static VEC(pre_expr, heap) *
688 sorted_array_from_bitmap_set (bitmap_set_t set)
692 VEC(pre_expr, heap) *result = NULL;
694 FOR_EACH_EXPR_ID_IN_SET (set, i, bi)
695 VEC_safe_push (pre_expr, heap, result, expression_for_id (i));
697 qsort (VEC_address (pre_expr, result), VEC_length (pre_expr, result),
698 sizeof (pre_expr), value_id_compare);
703 /* Perform bitmapped set operation DEST &= ORIG. */
706 bitmap_set_and (bitmap_set_t dest, bitmap_set_t orig)
713 bitmap temp = BITMAP_ALLOC (&grand_bitmap_obstack);
715 bitmap_and_into (dest->values, orig->values);
716 bitmap_copy (temp, dest->expressions);
717 EXECUTE_IF_SET_IN_BITMAP (temp, 0, i, bi)
719 pre_expr expr = expression_for_id (i);
720 unsigned int value_id = get_expr_value_id (expr);
721 if (!bitmap_bit_p (dest->values, value_id))
722 bitmap_clear_bit (dest->expressions, i);
728 /* Subtract all values and expressions contained in ORIG from DEST. */
731 bitmap_set_subtract (bitmap_set_t dest, bitmap_set_t orig)
733 bitmap_set_t result = bitmap_set_new ();
737 bitmap_and_compl (result->expressions, dest->expressions,
740 FOR_EACH_EXPR_ID_IN_SET (result, i, bi)
742 pre_expr expr = expression_for_id (i);
743 unsigned int value_id = get_expr_value_id (expr);
744 bitmap_set_bit (result->values, value_id);
750 /* Subtract all the values in bitmap set B from bitmap set A. */
753 bitmap_set_subtract_values (bitmap_set_t a, bitmap_set_t b)
757 bitmap temp = BITMAP_ALLOC (&grand_bitmap_obstack);
759 bitmap_copy (temp, a->expressions);
760 EXECUTE_IF_SET_IN_BITMAP (temp, 0, i, bi)
762 pre_expr expr = expression_for_id (i);
763 if (bitmap_set_contains_value (b, get_expr_value_id (expr)))
764 bitmap_remove_from_set (a, expr);
770 /* Return true if bitmapped set SET contains the value VALUE_ID. */
773 bitmap_set_contains_value (bitmap_set_t set, unsigned int value_id)
775 if (value_id_constant_p (value_id))
778 if (!set || bitmap_empty_p (set->expressions))
781 return bitmap_bit_p (set->values, value_id);
785 bitmap_set_contains_expr (bitmap_set_t set, const pre_expr expr)
787 return bitmap_bit_p (set->expressions, get_expression_id (expr));
790 /* Replace an instance of value LOOKFOR with expression EXPR in SET. */
793 bitmap_set_replace_value (bitmap_set_t set, unsigned int lookfor,
796 bitmap_set_t exprset;
800 if (value_id_constant_p (lookfor))
803 if (!bitmap_set_contains_value (set, lookfor))
806 /* The number of expressions having a given value is usually
807 significantly less than the total number of expressions in SET.
808 Thus, rather than check, for each expression in SET, whether it
809 has the value LOOKFOR, we walk the reverse mapping that tells us
810 what expressions have a given value, and see if any of those
811 expressions are in our set. For large testcases, this is about
812 5-10x faster than walking the bitmap. If this is somehow a
813 significant lose for some cases, we can choose which set to walk
814 based on the set size. */
815 exprset = VEC_index (bitmap_set_t, value_expressions, lookfor);
816 FOR_EACH_EXPR_ID_IN_SET (exprset, i, bi)
818 if (bitmap_bit_p (set->expressions, i))
820 bitmap_clear_bit (set->expressions, i);
821 bitmap_set_bit (set->expressions, get_expression_id (expr));
827 /* Return true if two bitmap sets are equal. */
830 bitmap_set_equal (bitmap_set_t a, bitmap_set_t b)
832 return bitmap_equal_p (a->values, b->values);
835 /* Replace an instance of EXPR's VALUE with EXPR in SET if it exists,
836 and add it otherwise. */
839 bitmap_value_replace_in_set (bitmap_set_t set, pre_expr expr)
841 unsigned int val = get_expr_value_id (expr);
843 if (bitmap_set_contains_value (set, val))
844 bitmap_set_replace_value (set, val, expr);
846 bitmap_insert_into_set (set, expr);
849 /* Insert EXPR into SET if EXPR's value is not already present in
853 bitmap_value_insert_into_set (bitmap_set_t set, pre_expr expr)
855 unsigned int val = get_expr_value_id (expr);
857 if (value_id_constant_p (val))
860 if (!bitmap_set_contains_value (set, val))
861 bitmap_insert_into_set (set, expr);
864 /* Print out EXPR to outfile. */
867 print_pre_expr (FILE *outfile, const pre_expr expr)
872 print_generic_expr (outfile, PRE_EXPR_CONSTANT (expr), 0);
875 print_generic_expr (outfile, PRE_EXPR_NAME (expr), 0);
880 vn_nary_op_t nary = PRE_EXPR_NARY (expr);
881 fprintf (outfile, "{%s,", tree_code_name [nary->opcode]);
882 for (i = 0; i < nary->length; i++)
884 print_generic_expr (outfile, nary->op[i], 0);
885 if (i != (unsigned) nary->length - 1)
886 fprintf (outfile, ",");
888 fprintf (outfile, "}");
894 vn_reference_op_t vro;
896 vn_reference_t ref = PRE_EXPR_REFERENCE (expr);
897 fprintf (outfile, "{");
899 VEC_iterate (vn_reference_op_s, ref->operands, i, vro);
902 if (vro->opcode != SSA_NAME
903 && TREE_CODE_CLASS (vro->opcode) != tcc_declaration)
904 fprintf (outfile, "%s ", tree_code_name [vro->opcode]);
908 fprintf (outfile, "<");
909 print_generic_expr (outfile, vro->op0, 0);
912 fprintf (outfile, ",");
913 print_generic_expr (outfile, vro->op1, 0);
916 fprintf (outfile, ">");
918 if (i != VEC_length (vn_reference_op_s, ref->operands) - 1)
919 fprintf (outfile, ",");
921 fprintf (outfile, "}");
926 void debug_pre_expr (pre_expr);
928 /* Like print_pre_expr but always prints to stderr. */
930 debug_pre_expr (pre_expr e)
932 print_pre_expr (stderr, e);
933 fprintf (stderr, "\n");
936 /* Print out SET to OUTFILE. */
939 print_bitmap_set (FILE *outfile, bitmap_set_t set,
940 const char *setname, int blockindex)
942 fprintf (outfile, "%s[%d] := { ", setname, blockindex);
949 FOR_EACH_EXPR_ID_IN_SET (set, i, bi)
951 const pre_expr expr = expression_for_id (i);
954 fprintf (outfile, ", ");
956 print_pre_expr (outfile, expr);
958 fprintf (outfile, " (%04d)", get_expr_value_id (expr));
961 fprintf (outfile, " }\n");
964 void debug_bitmap_set (bitmap_set_t);
967 debug_bitmap_set (bitmap_set_t set)
969 print_bitmap_set (stderr, set, "debug", 0);
972 /* Print out the expressions that have VAL to OUTFILE. */
975 print_value_expressions (FILE *outfile, unsigned int val)
977 bitmap_set_t set = VEC_index (bitmap_set_t, value_expressions, val);
981 sprintf (s, "%04d", val);
982 print_bitmap_set (outfile, set, s, 0);
988 debug_value_expressions (unsigned int val)
990 print_value_expressions (stderr, val);
993 /* Given a CONSTANT, allocate a new CONSTANT type PRE_EXPR to
997 get_or_alloc_expr_for_constant (tree constant)
999 unsigned int result_id;
1000 unsigned int value_id;
1001 pre_expr newexpr = (pre_expr) pool_alloc (pre_expr_pool);
1002 newexpr->kind = CONSTANT;
1003 PRE_EXPR_CONSTANT (newexpr) = constant;
1004 result_id = lookup_expression_id (newexpr);
1007 pool_free (pre_expr_pool, newexpr);
1008 newexpr = expression_for_id (result_id);
1011 value_id = get_or_alloc_constant_value_id (constant);
1012 get_or_alloc_expression_id (newexpr);
1013 add_to_value (value_id, newexpr);
1017 /* Given a value id V, find the actual tree representing the constant
1018 value if there is one, and return it. Return NULL if we can't find
1022 get_constant_for_value_id (unsigned int v)
1024 if (value_id_constant_p (v))
1028 bitmap_set_t exprset = VEC_index (bitmap_set_t, value_expressions, v);
1030 FOR_EACH_EXPR_ID_IN_SET (exprset, i, bi)
1032 pre_expr expr = expression_for_id (i);
1033 if (expr->kind == CONSTANT)
1034 return PRE_EXPR_CONSTANT (expr);
1040 /* Get or allocate a pre_expr for a piece of GIMPLE, and return it.
1041 Currently only supports constants and SSA_NAMES. */
1043 get_or_alloc_expr_for (tree t)
1045 if (TREE_CODE (t) == SSA_NAME)
1046 return get_or_alloc_expr_for_name (t);
1047 else if (is_gimple_min_invariant (t))
1048 return get_or_alloc_expr_for_constant (t);
1051 /* More complex expressions can result from SCCVN expression
1052 simplification that inserts values for them. As they all
1053 do not have VOPs the get handled by the nary ops struct. */
1054 vn_nary_op_t result;
1055 unsigned int result_id;
1056 vn_nary_op_lookup (t, &result);
1059 pre_expr e = (pre_expr) pool_alloc (pre_expr_pool);
1061 PRE_EXPR_NARY (e) = result;
1062 result_id = lookup_expression_id (e);
1065 pool_free (pre_expr_pool, e);
1066 e = expression_for_id (result_id);
1069 alloc_expression_id (e);
1076 /* Return the folded version of T if T, when folded, is a gimple
1077 min_invariant. Otherwise, return T. */
1080 fully_constant_expression (pre_expr e)
1088 vn_nary_op_t nary = PRE_EXPR_NARY (e);
1089 switch (TREE_CODE_CLASS (nary->opcode))
1093 /* We have to go from trees to pre exprs to value ids to
1095 tree naryop0 = nary->op[0];
1096 tree naryop1 = nary->op[1];
1097 tree const0, const1, result;
1098 if (is_gimple_min_invariant (naryop0))
1102 pre_expr rep0 = get_or_alloc_expr_for (naryop0);
1103 unsigned int vrep0 = get_expr_value_id (rep0);
1104 const0 = get_constant_for_value_id (vrep0);
1106 if (is_gimple_min_invariant (naryop1))
1110 pre_expr rep1 = get_or_alloc_expr_for (naryop1);
1111 unsigned int vrep1 = get_expr_value_id (rep1);
1112 const1 = get_constant_for_value_id (vrep1);
1115 if (const0 && const1)
1117 tree type1 = TREE_TYPE (nary->op[0]);
1118 tree type2 = TREE_TYPE (nary->op[1]);
1119 const0 = fold_convert (type1, const0);
1120 const1 = fold_convert (type2, const1);
1121 result = fold_binary (nary->opcode, nary->type, const0,
1124 if (result && is_gimple_min_invariant (result))
1125 return get_or_alloc_expr_for_constant (result);
1130 /* We have to go from trees to pre exprs to value ids to
1132 tree naryop0 = nary->op[0];
1133 tree const0, result;
1134 if (is_gimple_min_invariant (naryop0))
1138 pre_expr rep0 = get_or_alloc_expr_for (naryop0);
1139 unsigned int vrep0 = get_expr_value_id (rep0);
1140 const0 = get_constant_for_value_id (vrep0);
1145 tree type1 = TREE_TYPE (nary->op[0]);
1146 const0 = fold_convert (type1, const0);
1147 result = fold_unary (nary->opcode, nary->type, const0);
1150 if (result && is_gimple_min_invariant (result))
1151 return get_or_alloc_expr_for_constant (result);
1164 /* Translate the vuses in the VUSES vector backwards through phi nodes
1165 in PHIBLOCK, so that they have the value they would have in
1168 static VEC(tree, gc) *
1169 translate_vuses_through_block (VEC (tree, gc) *vuses,
1170 basic_block phiblock,
1174 VEC(tree, gc) *result = NULL;
1177 for (i = 0; VEC_iterate (tree, vuses, i, oldvuse); i++)
1179 gimple phi = SSA_NAME_DEF_STMT (oldvuse);
1180 if (gimple_code (phi) == GIMPLE_PHI
1181 && gimple_bb (phi) == phiblock)
1183 edge e = find_edge (block, gimple_bb (phi));
1186 tree def = PHI_ARG_DEF (phi, e->dest_idx);
1190 result = VEC_copy (tree, gc, vuses);
1191 VEC_replace (tree, result, i, def);
1197 /* We avoid creating a new copy of the vuses unless something
1198 actually changed, so result can be NULL. */
1201 sort_vuses (result);
1208 /* Like find_leader, but checks for the value existing in SET1 *or*
1209 SET2. This is used to avoid making a set consisting of the union
1210 of PA_IN and ANTIC_IN during insert. */
1212 static inline pre_expr
1213 find_leader_in_sets (unsigned int val, bitmap_set_t set1, bitmap_set_t set2)
1217 result = bitmap_find_leader (set1, val, NULL);
1218 if (!result && set2)
1219 result = bitmap_find_leader (set2, val, NULL);
1223 /* Get the tree type for our PRE expression e. */
1226 get_expr_type (const pre_expr e)
1231 return TREE_TYPE (PRE_EXPR_NAME (e));
1233 return TREE_TYPE (PRE_EXPR_CONSTANT (e));
1236 vn_reference_op_t vro;
1238 gcc_assert (PRE_EXPR_REFERENCE (e)->operands);
1239 vro = VEC_index (vn_reference_op_s,
1240 PRE_EXPR_REFERENCE (e)->operands,
1242 /* We don't store type along with COMPONENT_REF because it is
1243 always the same as FIELD_DECL's type. */
1246 gcc_assert (vro->opcode == COMPONENT_REF);
1247 return TREE_TYPE (vro->op0);
1253 return PRE_EXPR_NARY (e)->type;
1258 /* Get a representative SSA_NAME for a given expression.
1259 Since all of our sub-expressions are treated as values, we require
1260 them to be SSA_NAME's for simplicity.
1261 Prior versions of GVNPRE used to use "value handles" here, so that
1262 an expression would be VH.11 + VH.10 instead of d_3 + e_6. In
1263 either case, the operands are really values (IE we do not expect
1264 them to be usable without finding leaders). */
1267 get_representative_for (const pre_expr e)
1271 unsigned int value_id = get_expr_value_id (e);
1276 return PRE_EXPR_NAME (e);
1278 return PRE_EXPR_CONSTANT (e);
1282 /* Go through all of the expressions representing this value
1283 and pick out an SSA_NAME. */
1286 bitmap_set_t exprs = VEC_index (bitmap_set_t, value_expressions,
1288 FOR_EACH_EXPR_ID_IN_SET (exprs, i, bi)
1290 pre_expr rep = expression_for_id (i);
1291 if (rep->kind == NAME)
1292 return PRE_EXPR_NAME (rep);
1297 /* If we reached here we couldn't find an SSA_NAME. This can
1298 happen when we've discovered a value that has never appeared in
1299 the program as set to an SSA_NAME, most likely as the result of
1304 "Could not find SSA_NAME representative for expression:");
1305 print_pre_expr (dump_file, e);
1306 fprintf (dump_file, "\n");
1309 exprtype = get_expr_type (e);
1311 /* Build and insert the assignment of the end result to the temporary
1312 that we will return. */
1313 if (!pretemp || exprtype != TREE_TYPE (pretemp))
1315 pretemp = create_tmp_var (exprtype, "pretmp");
1316 get_var_ann (pretemp);
1319 name = make_ssa_name (pretemp, gimple_build_nop ());
1320 VN_INFO_GET (name)->value_id = value_id;
1321 if (e->kind == CONSTANT)
1322 VN_INFO (name)->valnum = PRE_EXPR_CONSTANT (e);
1324 VN_INFO (name)->valnum = name;
1326 add_to_value (value_id, get_or_alloc_expr_for_name (name));
1329 fprintf (dump_file, "Created SSA_NAME representative ");
1330 print_generic_expr (dump_file, name, 0);
1331 fprintf (dump_file, " for expression:");
1332 print_pre_expr (dump_file, e);
1333 fprintf (dump_file, "\n");
1342 /* Translate EXPR using phis in PHIBLOCK, so that it has the values of
1343 the phis in PRED. SEEN is a bitmap saying which expression we have
1344 translated since we started translation of the toplevel expression.
1345 Return NULL if we can't find a leader for each part of the
1346 translated expression. */
1349 phi_translate_1 (pre_expr expr, bitmap_set_t set1, bitmap_set_t set2,
1350 basic_block pred, basic_block phiblock, bitmap seen)
1352 pre_expr oldexpr = expr;
1358 if (value_id_constant_p (get_expr_value_id (expr)))
1361 phitrans = phi_trans_lookup (expr, pred);
1365 /* Prevent cycles when we have recursively dependent leaders. This
1366 can only happen when phi translating the maximal set. */
1369 unsigned int expr_id = get_expression_id (expr);
1370 if (bitmap_bit_p (seen, expr_id))
1372 bitmap_set_bit (seen, expr_id);
1377 /* Constants contain no values that need translation. */
1384 bool changed = false;
1385 vn_nary_op_t nary = PRE_EXPR_NARY (expr);
1386 struct vn_nary_op_s newnary;
1387 /* The NARY structure is only guaranteed to have been
1388 allocated to the nary->length operands. */
1389 memcpy (&newnary, nary, (sizeof (struct vn_nary_op_s)
1390 - sizeof (tree) * (4 - nary->length)));
1392 for (i = 0; i < newnary.length; i++)
1394 if (TREE_CODE (newnary.op[i]) != SSA_NAME)
1398 unsigned int op_val_id = VN_INFO (newnary.op[i])->value_id;
1399 pre_expr leader = find_leader_in_sets (op_val_id, set1, set2);
1400 pre_expr result = phi_translate_1 (leader, set1, set2,
1401 pred, phiblock, seen);
1402 if (result && result != leader)
1404 tree name = get_representative_for (result);
1407 newnary.op[i] = name;
1412 changed |= newnary.op[i] != nary->op[i];
1419 tree result = vn_nary_op_lookup_pieces (newnary.length,
1427 unsigned int new_val_id;
1429 expr = (pre_expr) pool_alloc (pre_expr_pool);
1432 if (result && is_gimple_min_invariant (result))
1433 return get_or_alloc_expr_for_constant (result);
1438 PRE_EXPR_NARY (expr) = nary;
1439 constant = fully_constant_expression (expr);
1440 if (constant != expr)
1443 new_val_id = nary->value_id;
1444 get_or_alloc_expression_id (expr);
1448 new_val_id = get_next_value_id ();
1449 VEC_safe_grow_cleared (bitmap_set_t, heap,
1451 get_max_value_id() + 1);
1452 nary = vn_nary_op_insert_pieces (newnary.length,
1459 result, new_val_id);
1460 PRE_EXPR_NARY (expr) = nary;
1461 constant = fully_constant_expression (expr);
1462 if (constant != expr)
1464 get_or_alloc_expression_id (expr);
1466 add_to_value (new_val_id, expr);
1468 phi_trans_add (oldexpr, expr, pred);
1474 vn_reference_t ref = PRE_EXPR_REFERENCE (expr);
1475 VEC (vn_reference_op_s, heap) *operands = ref->operands;
1476 VEC (tree, gc) *vuses = ref->vuses;
1477 VEC (tree, gc) *newvuses = vuses;
1478 VEC (vn_reference_op_s, heap) *newoperands = NULL;
1479 bool changed = false;
1481 vn_reference_op_t operand;
1482 vn_reference_t newref;
1484 for (i = 0; VEC_iterate (vn_reference_op_s, operands, i, operand); i++)
1488 tree oldop0 = operand->op0;
1489 tree oldop1 = operand->op1;
1490 tree oldop2 = operand->op2;
1494 tree type = operand->type;
1495 vn_reference_op_s newop = *operand;
1497 if (op0 && TREE_CODE (op0) == SSA_NAME)
1499 unsigned int op_val_id = VN_INFO (op0)->value_id;
1500 leader = find_leader_in_sets (op_val_id, set1, set2);
1501 opresult = phi_translate_1 (leader, set1, set2,
1502 pred, phiblock, seen);
1503 if (opresult && opresult != leader)
1505 tree name = get_representative_for (opresult);
1513 changed |= op0 != oldop0;
1515 if (op1 && TREE_CODE (op1) == SSA_NAME)
1517 unsigned int op_val_id = VN_INFO (op1)->value_id;
1518 leader = find_leader_in_sets (op_val_id, set1, set2);
1519 opresult = phi_translate_1 (leader, set1, set2,
1520 pred, phiblock, seen);
1521 if (opresult && opresult != leader)
1523 tree name = get_representative_for (opresult);
1531 changed |= op1 != oldop1;
1532 if (op2 && TREE_CODE (op2) == SSA_NAME)
1534 unsigned int op_val_id = VN_INFO (op2)->value_id;
1535 leader = find_leader_in_sets (op_val_id, set1, set2);
1536 opresult = phi_translate_1 (leader, set1, set2,
1537 pred, phiblock, seen);
1538 if (opresult && opresult != leader)
1540 tree name = get_representative_for (opresult);
1548 changed |= op2 != oldop2;
1551 newoperands = VEC_copy (vn_reference_op_s, heap, operands);
1552 /* We may have changed from an SSA_NAME to a constant */
1553 if (newop.opcode == SSA_NAME && TREE_CODE (op0) != SSA_NAME)
1554 newop.opcode = TREE_CODE (op0);
1559 VEC_replace (vn_reference_op_s, newoperands, i, &newop);
1561 if (i != VEC_length (vn_reference_op_s, operands))
1564 VEC_free (vn_reference_op_s, heap, newoperands);
1568 newvuses = translate_vuses_through_block (vuses, phiblock, pred);
1569 changed |= newvuses != vuses;
1573 tree result = vn_reference_lookup_pieces (newvuses,
1576 unsigned int new_val_id;
1579 VEC_free (vn_reference_op_s, heap, newoperands);
1581 if (result && is_gimple_min_invariant (result))
1583 gcc_assert (!newoperands);
1584 return get_or_alloc_expr_for_constant (result);
1587 expr = (pre_expr) pool_alloc (pre_expr_pool);
1588 expr->kind = REFERENCE;
1593 PRE_EXPR_REFERENCE (expr) = newref;
1594 new_val_id = newref->value_id;
1595 get_or_alloc_expression_id (expr);
1599 new_val_id = get_next_value_id ();
1600 VEC_safe_grow_cleared (bitmap_set_t, heap, value_expressions,
1601 get_max_value_id() + 1);
1602 newref = vn_reference_insert_pieces (newvuses,
1604 result, new_val_id);
1606 PRE_EXPR_REFERENCE (expr) = newref;
1607 get_or_alloc_expression_id (expr);
1609 add_to_value (new_val_id, expr);
1611 VEC_free (vn_reference_op_s, heap, newoperands);
1612 phi_trans_add (oldexpr, expr, pred);
1621 tree name = PRE_EXPR_NAME (expr);
1623 def_stmt = SSA_NAME_DEF_STMT (name);
1624 if (gimple_code (def_stmt) == GIMPLE_PHI
1625 && gimple_bb (def_stmt) == phiblock)
1630 e = find_edge (pred, gimple_bb (phi));
1633 tree def = PHI_ARG_DEF (phi, e->dest_idx);
1636 /* Handle constant. */
1637 if (is_gimple_min_invariant (def))
1638 return get_or_alloc_expr_for_constant (def);
1640 if (TREE_CODE (def) == SSA_NAME && ssa_undefined_value_p (def))
1643 newexpr = get_or_alloc_expr_for_name (def);
1654 /* Translate EXPR using phis in PHIBLOCK, so that it has the values of
1656 Return NULL if we can't find a leader for each part of the
1657 translated expression. */
1660 phi_translate (pre_expr expr, bitmap_set_t set1, bitmap_set_t set2,
1661 basic_block pred, basic_block phiblock)
1663 bitmap_clear (seen_during_translate);
1664 return phi_translate_1 (expr, set1, set2, pred, phiblock,
1665 seen_during_translate);
1668 /* For each expression in SET, translate the values through phi nodes
1669 in PHIBLOCK using edge PHIBLOCK->PRED, and store the resulting
1670 expressions in DEST. */
1673 phi_translate_set (bitmap_set_t dest, bitmap_set_t set, basic_block pred,
1674 basic_block phiblock)
1676 VEC (pre_expr, heap) *exprs;
1680 if (!phi_nodes (phiblock))
1682 bitmap_set_copy (dest, set);
1686 exprs = sorted_array_from_bitmap_set (set);
1687 for (i = 0; VEC_iterate (pre_expr, exprs, i, expr); i++)
1689 pre_expr translated;
1690 translated = phi_translate (expr, set, NULL, pred, phiblock);
1692 /* Don't add constants or empty translations to the cache, since
1693 we won't look them up that way, or use the result, anyway. */
1694 if (translated && !value_id_constant_p (get_expr_value_id (translated)))
1695 phi_trans_add (expr, translated, pred);
1697 if (translated != NULL)
1698 bitmap_value_insert_into_set (dest, translated);
1700 VEC_free (pre_expr, heap, exprs);
1703 /* Find the leader for a value (i.e., the name representing that
1704 value) in a given set, and return it. If STMT is non-NULL it
1705 makes sure the defining statement for the leader dominates it.
1706 Return NULL if no leader is found. */
1709 bitmap_find_leader (bitmap_set_t set, unsigned int val, gimple stmt)
1711 if (value_id_constant_p (val))
1715 bitmap_set_t exprset = VEC_index (bitmap_set_t, value_expressions, val);
1717 FOR_EACH_EXPR_ID_IN_SET (exprset, i, bi)
1719 pre_expr expr = expression_for_id (i);
1720 if (expr->kind == CONSTANT)
1724 if (bitmap_set_contains_value (set, val))
1726 /* Rather than walk the entire bitmap of expressions, and see
1727 whether any of them has the value we are looking for, we look
1728 at the reverse mapping, which tells us the set of expressions
1729 that have a given value (IE value->expressions with that
1730 value) and see if any of those expressions are in our set.
1731 The number of expressions per value is usually significantly
1732 less than the number of expressions in the set. In fact, for
1733 large testcases, doing it this way is roughly 5-10x faster
1734 than walking the bitmap.
1735 If this is somehow a significant lose for some cases, we can
1736 choose which set to walk based on which set is smaller. */
1739 bitmap_set_t exprset = VEC_index (bitmap_set_t, value_expressions, val);
1741 EXECUTE_IF_AND_IN_BITMAP (exprset->expressions,
1742 set->expressions, 0, i, bi)
1744 pre_expr val = expression_for_id (i);
1745 /* At the point where stmt is not null, there should always
1746 be an SSA_NAME first in the list of expressions. */
1749 gimple def_stmt = SSA_NAME_DEF_STMT (PRE_EXPR_NAME (val));
1750 if (gimple_code (def_stmt) != GIMPLE_PHI
1751 && gimple_bb (def_stmt) == gimple_bb (stmt)
1752 && gimple_uid (def_stmt) >= gimple_uid (stmt))
1761 /* Determine if EXPR, a memory expression, is ANTIC_IN at the top of
1762 BLOCK by seeing if it is not killed in the block. Note that we are
1763 only determining whether there is a store that kills it. Because
1764 of the order in which clean iterates over values, we are guaranteed
1765 that altered operands will have caused us to be eliminated from the
1766 ANTIC_IN set already. */
1769 value_dies_in_block_x (pre_expr expr, basic_block block)
1773 VEC (tree, gc) *vuses = PRE_EXPR_REFERENCE (expr)->vuses;
1775 /* Conservatively, a value dies if it's vuses are defined in this
1776 block, unless they come from phi nodes (which are merge operations,
1777 rather than stores. */
1778 for (i = 0; VEC_iterate (tree, vuses, i, vuse); i++)
1780 gimple def = SSA_NAME_DEF_STMT (vuse);
1782 if (gimple_bb (def) != block)
1784 if (gimple_code (def) == GIMPLE_PHI)
1792 #define union_contains_value(SET1, SET2, VAL) \
1793 (bitmap_set_contains_value ((SET1), (VAL)) \
1794 || ((SET2) && bitmap_set_contains_value ((SET2), (VAL))))
1796 /* Determine if vn_reference_op_t VRO is legal in SET1 U SET2.
1799 vro_valid_in_sets (bitmap_set_t set1, bitmap_set_t set2,
1800 vn_reference_op_t vro)
1802 if (vro->op0 && TREE_CODE (vro->op0) == SSA_NAME)
1804 struct pre_expr_d temp;
1807 PRE_EXPR_NAME (&temp) = vro->op0;
1808 temp.id = lookup_expression_id (&temp);
1811 if (!union_contains_value (set1, set2,
1812 get_expr_value_id (&temp)))
1815 if (vro->op1 && TREE_CODE (vro->op1) == SSA_NAME)
1817 struct pre_expr_d temp;
1820 PRE_EXPR_NAME (&temp) = vro->op1;
1821 temp.id = lookup_expression_id (&temp);
1824 if (!union_contains_value (set1, set2,
1825 get_expr_value_id (&temp)))
1829 if (vro->op2 && TREE_CODE (vro->op2) == SSA_NAME)
1831 struct pre_expr_d temp;
1834 PRE_EXPR_NAME (&temp) = vro->op2;
1835 temp.id = lookup_expression_id (&temp);
1838 if (!union_contains_value (set1, set2,
1839 get_expr_value_id (&temp)))
1846 /* Determine if the expression EXPR is valid in SET1 U SET2.
1847 ONLY SET2 CAN BE NULL.
1848 This means that we have a leader for each part of the expression
1849 (if it consists of values), or the expression is an SSA_NAME.
1850 For loads/calls, we also see if the vuses are killed in this block.
1854 valid_in_sets (bitmap_set_t set1, bitmap_set_t set2, pre_expr expr,
1860 return bitmap_set_contains_expr (AVAIL_OUT (block), expr);
1864 vn_nary_op_t nary = PRE_EXPR_NARY (expr);
1865 for (i = 0; i < nary->length; i++)
1867 if (TREE_CODE (nary->op[i]) == SSA_NAME)
1869 struct pre_expr_d temp;
1872 PRE_EXPR_NAME (&temp) = nary->op[i];
1873 temp.id = lookup_expression_id (&temp);
1876 if (!union_contains_value (set1, set2,
1877 get_expr_value_id (&temp)))
1886 vn_reference_t ref = PRE_EXPR_REFERENCE (expr);
1887 vn_reference_op_t vro;
1890 for (i = 0; VEC_iterate (vn_reference_op_s, ref->operands, i, vro); i++)
1892 if (!vro_valid_in_sets (set1, set2, vro))
1895 return !value_dies_in_block_x (expr, block);
1902 /* Clean the set of expressions that are no longer valid in SET1 or
1903 SET2. This means expressions that are made up of values we have no
1904 leaders for in SET1 or SET2. This version is used for partial
1905 anticipation, which means it is not valid in either ANTIC_IN or
1909 dependent_clean (bitmap_set_t set1, bitmap_set_t set2, basic_block block)
1911 VEC (pre_expr, heap) *exprs = sorted_array_from_bitmap_set (set1);
1915 for (i = 0; VEC_iterate (pre_expr, exprs, i, expr); i++)
1917 if (!valid_in_sets (set1, set2, expr, block))
1918 bitmap_remove_from_set (set1, expr);
1920 VEC_free (pre_expr, heap, exprs);
1923 /* Clean the set of expressions that are no longer valid in SET. This
1924 means expressions that are made up of values we have no leaders for
1928 clean (bitmap_set_t set, basic_block block)
1930 VEC (pre_expr, heap) *exprs = sorted_array_from_bitmap_set (set);
1934 for (i = 0; VEC_iterate (pre_expr, exprs, i, expr); i++)
1936 if (!valid_in_sets (set, NULL, expr, block))
1937 bitmap_remove_from_set (set, expr);
1939 VEC_free (pre_expr, heap, exprs);
1942 static sbitmap has_abnormal_preds;
1944 /* List of blocks that may have changed during ANTIC computation and
1945 thus need to be iterated over. */
1947 static sbitmap changed_blocks;
1949 /* Decide whether to defer a block for a later iteration, or PHI
1950 translate SOURCE to DEST using phis in PHIBLOCK. Return false if we
1951 should defer the block, and true if we processed it. */
1954 defer_or_phi_translate_block (bitmap_set_t dest, bitmap_set_t source,
1955 basic_block block, basic_block phiblock)
1957 if (!BB_VISITED (phiblock))
1959 SET_BIT (changed_blocks, block->index);
1960 BB_VISITED (block) = 0;
1961 BB_DEFERRED (block) = 1;
1965 phi_translate_set (dest, source, block, phiblock);
1969 /* Compute the ANTIC set for BLOCK.
1971 If succs(BLOCK) > 1 then
1972 ANTIC_OUT[BLOCK] = intersection of ANTIC_IN[b] for all succ(BLOCK)
1973 else if succs(BLOCK) == 1 then
1974 ANTIC_OUT[BLOCK] = phi_translate (ANTIC_IN[succ(BLOCK)])
1976 ANTIC_IN[BLOCK] = clean(ANTIC_OUT[BLOCK] U EXP_GEN[BLOCK] - TMP_GEN[BLOCK])
1980 compute_antic_aux (basic_block block, bool block_has_abnormal_pred_edge)
1982 bool changed = false;
1983 bitmap_set_t S, old, ANTIC_OUT;
1989 old = ANTIC_OUT = S = NULL;
1990 BB_VISITED (block) = 1;
1992 /* If any edges from predecessors are abnormal, antic_in is empty,
1994 if (block_has_abnormal_pred_edge)
1995 goto maybe_dump_sets;
1997 old = ANTIC_IN (block);
1998 ANTIC_OUT = bitmap_set_new ();
2000 /* If the block has no successors, ANTIC_OUT is empty. */
2001 if (EDGE_COUNT (block->succs) == 0)
2003 /* If we have one successor, we could have some phi nodes to
2004 translate through. */
2005 else if (single_succ_p (block))
2007 basic_block succ_bb = single_succ (block);
2009 /* We trade iterations of the dataflow equations for having to
2010 phi translate the maximal set, which is incredibly slow
2011 (since the maximal set often has 300+ members, even when you
2012 have a small number of blocks).
2013 Basically, we defer the computation of ANTIC for this block
2014 until we have processed it's successor, which will inevitably
2015 have a *much* smaller set of values to phi translate once
2016 clean has been run on it.
2017 The cost of doing this is that we technically perform more
2018 iterations, however, they are lower cost iterations.
2020 Timings for PRE on tramp3d-v4:
2021 without maximal set fix: 11 seconds
2022 with maximal set fix/without deferring: 26 seconds
2023 with maximal set fix/with deferring: 11 seconds
2026 if (!defer_or_phi_translate_block (ANTIC_OUT, ANTIC_IN (succ_bb),
2030 goto maybe_dump_sets;
2033 /* If we have multiple successors, we take the intersection of all of
2034 them. Note that in the case of loop exit phi nodes, we may have
2035 phis to translate through. */
2038 VEC(basic_block, heap) * worklist;
2040 basic_block bprime, first;
2042 worklist = VEC_alloc (basic_block, heap, EDGE_COUNT (block->succs));
2043 FOR_EACH_EDGE (e, ei, block->succs)
2044 VEC_quick_push (basic_block, worklist, e->dest);
2045 first = VEC_index (basic_block, worklist, 0);
2047 if (phi_nodes (first))
2049 bitmap_set_t from = ANTIC_IN (first);
2051 if (!BB_VISITED (first))
2053 phi_translate_set (ANTIC_OUT, from, block, first);
2057 if (!BB_VISITED (first))
2058 bitmap_set_copy (ANTIC_OUT, maximal_set);
2060 bitmap_set_copy (ANTIC_OUT, ANTIC_IN (first));
2063 for (i = 1; VEC_iterate (basic_block, worklist, i, bprime); i++)
2065 if (phi_nodes (bprime))
2067 bitmap_set_t tmp = bitmap_set_new ();
2068 bitmap_set_t from = ANTIC_IN (bprime);
2070 if (!BB_VISITED (bprime))
2072 phi_translate_set (tmp, from, block, bprime);
2073 bitmap_set_and (ANTIC_OUT, tmp);
2074 bitmap_set_free (tmp);
2078 if (!BB_VISITED (bprime))
2079 bitmap_set_and (ANTIC_OUT, maximal_set);
2081 bitmap_set_and (ANTIC_OUT, ANTIC_IN (bprime));
2084 VEC_free (basic_block, heap, worklist);
2087 /* Generate ANTIC_OUT - TMP_GEN. */
2088 S = bitmap_set_subtract (ANTIC_OUT, TMP_GEN (block));
2090 /* Start ANTIC_IN with EXP_GEN - TMP_GEN. */
2091 ANTIC_IN (block) = bitmap_set_subtract (EXP_GEN (block),
2094 /* Then union in the ANTIC_OUT - TMP_GEN values,
2095 to get ANTIC_OUT U EXP_GEN - TMP_GEN */
2096 FOR_EACH_EXPR_ID_IN_SET (S, bii, bi)
2097 bitmap_value_insert_into_set (ANTIC_IN (block),
2098 expression_for_id (bii));
2100 clean (ANTIC_IN (block), block);
2102 /* !old->expressions can happen when we deferred a block. */
2103 if (!old->expressions || !bitmap_set_equal (old, ANTIC_IN (block)))
2106 SET_BIT (changed_blocks, block->index);
2107 FOR_EACH_EDGE (e, ei, block->preds)
2108 SET_BIT (changed_blocks, e->src->index);
2111 RESET_BIT (changed_blocks, block->index);
2114 if (dump_file && (dump_flags & TDF_DETAILS))
2116 if (!BB_DEFERRED (block) || BB_VISITED (block))
2119 print_bitmap_set (dump_file, ANTIC_OUT, "ANTIC_OUT", block->index);
2121 print_bitmap_set (dump_file, ANTIC_IN (block), "ANTIC_IN",
2125 print_bitmap_set (dump_file, S, "S", block->index);
2130 "Block %d was deferred for a future iteration.\n",
2135 bitmap_set_free (old);
2137 bitmap_set_free (S);
2139 bitmap_set_free (ANTIC_OUT);
2143 /* Compute PARTIAL_ANTIC for BLOCK.
2145 If succs(BLOCK) > 1 then
2146 PA_OUT[BLOCK] = value wise union of PA_IN[b] + all ANTIC_IN not
2147 in ANTIC_OUT for all succ(BLOCK)
2148 else if succs(BLOCK) == 1 then
2149 PA_OUT[BLOCK] = phi_translate (PA_IN[succ(BLOCK)])
2151 PA_IN[BLOCK] = dependent_clean(PA_OUT[BLOCK] - TMP_GEN[BLOCK]
2156 compute_partial_antic_aux (basic_block block,
2157 bool block_has_abnormal_pred_edge)
2159 bool changed = false;
2160 bitmap_set_t old_PA_IN;
2161 bitmap_set_t PA_OUT;
2164 unsigned long max_pa = PARAM_VALUE (PARAM_MAX_PARTIAL_ANTIC_LENGTH);
2166 old_PA_IN = PA_OUT = NULL;
2168 /* If any edges from predecessors are abnormal, antic_in is empty,
2170 if (block_has_abnormal_pred_edge)
2171 goto maybe_dump_sets;
2173 /* If there are too many partially anticipatable values in the
2174 block, phi_translate_set can take an exponential time: stop
2175 before the translation starts. */
2177 && single_succ_p (block)
2178 && bitmap_count_bits (PA_IN (single_succ (block))->values) > max_pa)
2179 goto maybe_dump_sets;
2181 old_PA_IN = PA_IN (block);
2182 PA_OUT = bitmap_set_new ();
2184 /* If the block has no successors, ANTIC_OUT is empty. */
2185 if (EDGE_COUNT (block->succs) == 0)
2187 /* If we have one successor, we could have some phi nodes to
2188 translate through. Note that we can't phi translate across DFS
2189 back edges in partial antic, because it uses a union operation on
2190 the successors. For recurrences like IV's, we will end up
2191 generating a new value in the set on each go around (i + 3 (VH.1)
2192 VH.1 + 1 (VH.2), VH.2 + 1 (VH.3), etc), forever. */
2193 else if (single_succ_p (block))
2195 basic_block succ = single_succ (block);
2196 if (!(single_succ_edge (block)->flags & EDGE_DFS_BACK))
2197 phi_translate_set (PA_OUT, PA_IN (succ), block, succ);
2199 /* If we have multiple successors, we take the union of all of
2203 VEC(basic_block, heap) * worklist;
2207 worklist = VEC_alloc (basic_block, heap, EDGE_COUNT (block->succs));
2208 FOR_EACH_EDGE (e, ei, block->succs)
2210 if (e->flags & EDGE_DFS_BACK)
2212 VEC_quick_push (basic_block, worklist, e->dest);
2214 if (VEC_length (basic_block, worklist) > 0)
2216 for (i = 0; VEC_iterate (basic_block, worklist, i, bprime); i++)
2221 FOR_EACH_EXPR_ID_IN_SET (ANTIC_IN (bprime), i, bi)
2222 bitmap_value_insert_into_set (PA_OUT,
2223 expression_for_id (i));
2224 if (phi_nodes (bprime))
2226 bitmap_set_t pa_in = bitmap_set_new ();
2227 phi_translate_set (pa_in, PA_IN (bprime), block, bprime);
2228 FOR_EACH_EXPR_ID_IN_SET (pa_in, i, bi)
2229 bitmap_value_insert_into_set (PA_OUT,
2230 expression_for_id (i));
2231 bitmap_set_free (pa_in);
2234 FOR_EACH_EXPR_ID_IN_SET (PA_IN (bprime), i, bi)
2235 bitmap_value_insert_into_set (PA_OUT,
2236 expression_for_id (i));
2239 VEC_free (basic_block, heap, worklist);
2242 /* PA_IN starts with PA_OUT - TMP_GEN.
2243 Then we subtract things from ANTIC_IN. */
2244 PA_IN (block) = bitmap_set_subtract (PA_OUT, TMP_GEN (block));
2246 /* For partial antic, we want to put back in the phi results, since
2247 we will properly avoid making them partially antic over backedges. */
2248 bitmap_ior_into (PA_IN (block)->values, PHI_GEN (block)->values);
2249 bitmap_ior_into (PA_IN (block)->expressions, PHI_GEN (block)->expressions);
2251 /* PA_IN[block] = PA_IN[block] - ANTIC_IN[block] */
2252 bitmap_set_subtract_values (PA_IN (block), ANTIC_IN (block));
2254 dependent_clean (PA_IN (block), ANTIC_IN (block), block);
2256 if (!bitmap_set_equal (old_PA_IN, PA_IN (block)))
2259 SET_BIT (changed_blocks, block->index);
2260 FOR_EACH_EDGE (e, ei, block->preds)
2261 SET_BIT (changed_blocks, e->src->index);
2264 RESET_BIT (changed_blocks, block->index);
2267 if (dump_file && (dump_flags & TDF_DETAILS))
2270 print_bitmap_set (dump_file, PA_OUT, "PA_OUT", block->index);
2272 print_bitmap_set (dump_file, PA_IN (block), "PA_IN", block->index);
2275 bitmap_set_free (old_PA_IN);
2277 bitmap_set_free (PA_OUT);
2281 /* Compute ANTIC and partial ANTIC sets. */
2284 compute_antic (void)
2286 bool changed = true;
2287 int num_iterations = 0;
2291 /* If any predecessor edges are abnormal, we punt, so antic_in is empty.
2292 We pre-build the map of blocks with incoming abnormal edges here. */
2293 has_abnormal_preds = sbitmap_alloc (last_basic_block);
2294 sbitmap_zero (has_abnormal_preds);
2301 FOR_EACH_EDGE (e, ei, block->preds)
2303 e->flags &= ~EDGE_DFS_BACK;
2304 if (e->flags & EDGE_ABNORMAL)
2306 SET_BIT (has_abnormal_preds, block->index);
2311 BB_VISITED (block) = 0;
2312 BB_DEFERRED (block) = 0;
2313 /* While we are here, give empty ANTIC_IN sets to each block. */
2314 ANTIC_IN (block) = bitmap_set_new ();
2315 PA_IN (block) = bitmap_set_new ();
2318 /* At the exit block we anticipate nothing. */
2319 ANTIC_IN (EXIT_BLOCK_PTR) = bitmap_set_new ();
2320 BB_VISITED (EXIT_BLOCK_PTR) = 1;
2321 PA_IN (EXIT_BLOCK_PTR) = bitmap_set_new ();
2323 changed_blocks = sbitmap_alloc (last_basic_block + 1);
2324 sbitmap_ones (changed_blocks);
2327 if (dump_file && (dump_flags & TDF_DETAILS))
2328 fprintf (dump_file, "Starting iteration %d\n", num_iterations);
2331 for (i = 0; i < last_basic_block - NUM_FIXED_BLOCKS; i++)
2333 if (TEST_BIT (changed_blocks, postorder[i]))
2335 basic_block block = BASIC_BLOCK (postorder[i]);
2336 changed |= compute_antic_aux (block,
2337 TEST_BIT (has_abnormal_preds,
2341 #ifdef ENABLE_CHECKING
2342 /* Theoretically possible, but *highly* unlikely. */
2343 gcc_assert (num_iterations < 500);
2347 statistics_histogram_event (cfun, "compute_antic iterations",
2350 if (do_partial_partial)
2352 sbitmap_ones (changed_blocks);
2353 mark_dfs_back_edges ();
2358 if (dump_file && (dump_flags & TDF_DETAILS))
2359 fprintf (dump_file, "Starting iteration %d\n", num_iterations);
2362 for (i = 0; i < last_basic_block - NUM_FIXED_BLOCKS; i++)
2364 if (TEST_BIT (changed_blocks, postorder[i]))
2366 basic_block block = BASIC_BLOCK (postorder[i]);
2368 |= compute_partial_antic_aux (block,
2369 TEST_BIT (has_abnormal_preds,
2373 #ifdef ENABLE_CHECKING
2374 /* Theoretically possible, but *highly* unlikely. */
2375 gcc_assert (num_iterations < 500);
2378 statistics_histogram_event (cfun, "compute_partial_antic iterations",
2381 sbitmap_free (has_abnormal_preds);
2382 sbitmap_free (changed_blocks);
2385 /* Return true if we can value number the call in STMT. This is true
2386 if we have a pure or constant call. */
2389 can_value_number_call (gimple stmt)
2391 if (gimple_call_flags (stmt) & (ECF_PURE | ECF_CONST))
2396 /* Return true if OP is an exception handler related operation, such as
2397 FILTER_EXPR or EXC_PTR_EXPR. */
2400 is_exception_related (gimple stmt)
2402 return (is_gimple_assign (stmt)
2403 && (gimple_assign_rhs_code (stmt) == FILTER_EXPR
2404 || gimple_assign_rhs_code (stmt) == EXC_PTR_EXPR));
2407 /* Return true if OP is a tree which we can perform PRE on
2408 on. This may not match the operations we can value number, but in
2409 a perfect world would. */
2412 can_PRE_operation (tree op)
2414 return UNARY_CLASS_P (op)
2415 || BINARY_CLASS_P (op)
2416 || COMPARISON_CLASS_P (op)
2417 || TREE_CODE (op) == INDIRECT_REF
2418 || TREE_CODE (op) == COMPONENT_REF
2419 || TREE_CODE (op) == VIEW_CONVERT_EXPR
2420 || TREE_CODE (op) == CALL_EXPR
2421 || TREE_CODE (op) == ARRAY_REF;
2425 /* Inserted expressions are placed onto this worklist, which is used
2426 for performing quick dead code elimination of insertions we made
2427 that didn't turn out to be necessary. */
2428 static VEC(gimple,heap) *inserted_exprs;
2430 /* Pool allocated fake store expressions are placed onto this
2431 worklist, which, after performing dead code elimination, is walked
2432 to see which expressions need to be put into GC'able memory */
2433 static VEC(gimple, heap) *need_creation;
2435 /* The actual worker for create_component_ref_by_pieces. */
2438 create_component_ref_by_pieces_1 (basic_block block, vn_reference_t ref,
2439 unsigned int *operand, gimple_seq *stmts,
2442 vn_reference_op_t currop = VEC_index (vn_reference_op_s, ref->operands,
2446 switch (currop->opcode)
2450 tree folded, sc = currop->op1;
2451 unsigned int nargs = 0;
2452 tree *args = XNEWVEC (tree, VEC_length (vn_reference_op_s,
2453 ref->operands) - 1);
2454 while (*operand < VEC_length (vn_reference_op_s, ref->operands))
2456 args[nargs] = create_component_ref_by_pieces_1 (block, ref,
2461 folded = build_call_array (currop->type,
2462 TREE_CODE (currop->op0) == FUNCTION_DECL
2463 ? build_fold_addr_expr (currop->op0)
2469 pre_expr scexpr = get_or_alloc_expr_for (sc);
2470 sc = find_or_generate_expression (block, scexpr, stmts, domstmt);
2473 CALL_EXPR_STATIC_CHAIN (folded) = sc;
2481 gcc_assert (is_gimple_min_invariant (currop->op0));
2487 case VIEW_CONVERT_EXPR:
2490 tree genop0 = create_component_ref_by_pieces_1 (block, ref,
2495 folded = fold_build1 (currop->opcode, currop->type,
2500 case ALIGN_INDIRECT_REF:
2501 case MISALIGNED_INDIRECT_REF:
2505 tree genop1 = create_component_ref_by_pieces_1 (block, ref,
2510 genop1 = fold_convert (build_pointer_type (currop->type),
2513 if (currop->opcode == MISALIGNED_INDIRECT_REF)
2514 folded = fold_build2 (currop->opcode, currop->type,
2515 genop1, currop->op1);
2517 folded = fold_build1 (currop->opcode, currop->type,
2525 tree genop0 = create_component_ref_by_pieces_1 (block, ref, operand,
2527 pre_expr op1expr = get_or_alloc_expr_for (currop->op0);
2528 pre_expr op2expr = get_or_alloc_expr_for (currop->op1);
2534 genop1 = find_or_generate_expression (block, op1expr, stmts, domstmt);
2537 genop2 = find_or_generate_expression (block, op2expr, stmts, domstmt);
2540 folded = fold_build3 (BIT_FIELD_REF, currop->type, genop0, genop1,
2545 /* For array ref vn_reference_op's, operand 1 of the array ref
2546 is op0 of the reference op and operand 3 of the array ref is
2548 case ARRAY_RANGE_REF:
2552 tree genop1 = currop->op0;
2554 tree genop2 = currop->op1;
2557 genop0 = create_component_ref_by_pieces_1 (block, ref, operand,
2561 op1expr = get_or_alloc_expr_for (genop1);
2562 genop1 = find_or_generate_expression (block, op1expr, stmts, domstmt);
2567 op2expr = get_or_alloc_expr_for (genop2);
2568 genop2 = find_or_generate_expression (block, op2expr, stmts,
2574 genop3 = currop->op2;
2575 return build4 (currop->opcode, currop->type, genop0, genop1,
2582 tree genop2 = currop->op1;
2584 op0 = create_component_ref_by_pieces_1 (block, ref, operand,
2588 /* op1 should be a FIELD_DECL, which are represented by
2593 op2expr = get_or_alloc_expr_for (genop2);
2594 genop2 = find_or_generate_expression (block, op2expr, stmts,
2600 return fold_build3 (COMPONENT_REF, TREE_TYPE (op1), op0, op1,
2606 pre_expr op0expr = get_or_alloc_expr_for (currop->op0);
2607 genop = find_or_generate_expression (block, op0expr, stmts, domstmt);
2628 /* For COMPONENT_REF's and ARRAY_REF's, we can't have any intermediates for the
2629 COMPONENT_REF or INDIRECT_REF or ARRAY_REF portion, because we'd end up with
2630 trying to rename aggregates into ssa form directly, which is a no no.
2632 Thus, this routine doesn't create temporaries, it just builds a
2633 single access expression for the array, calling
2634 find_or_generate_expression to build the innermost pieces.
2636 This function is a subroutine of create_expression_by_pieces, and
2637 should not be called on it's own unless you really know what you
2641 create_component_ref_by_pieces (basic_block block, vn_reference_t ref,
2642 gimple_seq *stmts, gimple domstmt)
2644 unsigned int op = 0;
2645 return create_component_ref_by_pieces_1 (block, ref, &op, stmts, domstmt);
2648 /* Find a leader for an expression, or generate one using
2649 create_expression_by_pieces if it's ANTIC but
2651 BLOCK is the basic_block we are looking for leaders in.
2652 EXPR is the expression to find a leader or generate for.
2653 STMTS is the statement list to put the inserted expressions on.
2654 Returns the SSA_NAME of the LHS of the generated expression or the
2656 DOMSTMT if non-NULL is a statement that should be dominated by
2657 all uses in the generated expression. If DOMSTMT is non-NULL this
2658 routine can fail and return NULL_TREE. Otherwise it will assert
2662 find_or_generate_expression (basic_block block, pre_expr expr,
2663 gimple_seq *stmts, gimple domstmt)
2665 pre_expr leader = bitmap_find_leader (AVAIL_OUT (block),
2666 get_expr_value_id (expr), domstmt);
2670 if (leader->kind == NAME)
2671 genop = PRE_EXPR_NAME (leader);
2672 else if (leader->kind == CONSTANT)
2673 genop = PRE_EXPR_CONSTANT (leader);
2676 /* If it's still NULL, it must be a complex expression, so generate
2680 bitmap_set_t exprset;
2681 unsigned int lookfor = get_expr_value_id (expr);
2682 bool handled = false;
2686 exprset = VEC_index (bitmap_set_t, value_expressions, lookfor);
2687 FOR_EACH_EXPR_ID_IN_SET (exprset, i, bi)
2689 pre_expr temp = expression_for_id (i);
2690 if (temp->kind != NAME)
2693 genop = create_expression_by_pieces (block, temp, stmts,
2695 get_expr_type (expr));
2699 if (!handled && domstmt)
2702 gcc_assert (handled);
2707 #define NECESSARY GF_PLF_1
2709 /* Create an expression in pieces, so that we can handle very complex
2710 expressions that may be ANTIC, but not necessary GIMPLE.
2711 BLOCK is the basic block the expression will be inserted into,
2712 EXPR is the expression to insert (in value form)
2713 STMTS is a statement list to append the necessary insertions into.
2715 This function will die if we hit some value that shouldn't be
2716 ANTIC but is (IE there is no leader for it, or its components).
2717 This function may also generate expressions that are themselves
2718 partially or fully redundant. Those that are will be either made
2719 fully redundant during the next iteration of insert (for partially
2720 redundant ones), or eliminated by eliminate (for fully redundant
2723 If DOMSTMT is non-NULL then we make sure that all uses in the
2724 expressions dominate that statement. In this case the function
2725 can return NULL_TREE to signal failure. */
2728 create_expression_by_pieces (basic_block block, pre_expr expr,
2729 gimple_seq *stmts, gimple domstmt, tree type)
2732 tree folded, newexpr;
2733 gimple_seq forced_stmts;
2734 unsigned int value_id;
2735 gimple_stmt_iterator gsi;
2736 tree exprtype = type ? type : get_expr_type (expr);
2742 /* We may hit the NAME/CONSTANT case if we have to convert types
2743 that value numbering saw through. */
2745 folded = PRE_EXPR_NAME (expr);
2748 folded = PRE_EXPR_CONSTANT (expr);
2752 vn_reference_t ref = PRE_EXPR_REFERENCE (expr);
2753 folded = create_component_ref_by_pieces (block, ref, stmts, domstmt);
2758 vn_nary_op_t nary = PRE_EXPR_NARY (expr);
2759 switch (nary->length)
2763 pre_expr op1 = get_or_alloc_expr_for (nary->op[0]);
2764 pre_expr op2 = get_or_alloc_expr_for (nary->op[1]);
2765 tree genop1 = find_or_generate_expression (block, op1,
2767 tree genop2 = find_or_generate_expression (block, op2,
2769 if (!genop1 || !genop2)
2771 genop1 = fold_convert (TREE_TYPE (nary->op[0]),
2773 /* Ensure op2 is a sizetype for POINTER_PLUS_EXPR. It
2774 may be a constant with the wrong type. */
2775 if (nary->opcode == POINTER_PLUS_EXPR)
2776 genop2 = fold_convert (sizetype, genop2);
2778 genop2 = fold_convert (TREE_TYPE (nary->op[1]), genop2);
2780 folded = fold_build2 (nary->opcode, nary->type,
2786 pre_expr op1 = get_or_alloc_expr_for (nary->op[0]);
2787 tree genop1 = find_or_generate_expression (block, op1,
2791 genop1 = fold_convert (TREE_TYPE (nary->op[0]), genop1);
2793 folded = fold_build1 (nary->opcode, nary->type,
2805 folded = fold_convert (exprtype, folded);
2806 /* Force the generated expression to be a sequence of GIMPLE
2808 We have to call unshare_expr because force_gimple_operand may
2809 modify the tree we pass to it. */
2810 newexpr = force_gimple_operand (unshare_expr (folded), &forced_stmts,
2813 /* If we have any intermediate expressions to the value sets, add them
2814 to the value sets and chain them in the instruction stream. */
2817 gsi = gsi_start (forced_stmts);
2818 for (; !gsi_end_p (gsi); gsi_next (&gsi))
2820 gimple stmt = gsi_stmt (gsi);
2821 tree forcedname = gimple_get_lhs (stmt);
2824 VEC_safe_push (gimple, heap, inserted_exprs, stmt);
2825 if (TREE_CODE (forcedname) == SSA_NAME)
2827 VN_INFO_GET (forcedname)->valnum = forcedname;
2828 VN_INFO (forcedname)->value_id = get_next_value_id ();
2829 nameexpr = get_or_alloc_expr_for_name (forcedname);
2830 add_to_value (VN_INFO (forcedname)->value_id, nameexpr);
2831 bitmap_value_replace_in_set (NEW_SETS (block), nameexpr);
2832 bitmap_value_replace_in_set (AVAIL_OUT (block), nameexpr);
2834 mark_symbols_for_renaming (stmt);
2836 gimple_seq_add_seq (stmts, forced_stmts);
2839 /* Build and insert the assignment of the end result to the temporary
2840 that we will return. */
2841 if (!pretemp || exprtype != TREE_TYPE (pretemp))
2843 pretemp = create_tmp_var (exprtype, "pretmp");
2844 get_var_ann (pretemp);
2848 add_referenced_var (temp);
2850 if (TREE_CODE (exprtype) == COMPLEX_TYPE
2851 || TREE_CODE (exprtype) == VECTOR_TYPE)
2852 DECL_GIMPLE_REG_P (temp) = 1;
2854 newstmt = gimple_build_assign (temp, newexpr);
2855 name = make_ssa_name (temp, newstmt);
2856 gimple_assign_set_lhs (newstmt, name);
2857 gimple_set_plf (newstmt, NECESSARY, false);
2859 gimple_seq_add_stmt (stmts, newstmt);
2860 VEC_safe_push (gimple, heap, inserted_exprs, newstmt);
2862 /* All the symbols in NEWEXPR should be put into SSA form. */
2863 mark_symbols_for_renaming (newstmt);
2865 /* Add a value number to the temporary.
2866 The value may already exist in either NEW_SETS, or AVAIL_OUT, because
2867 we are creating the expression by pieces, and this particular piece of
2868 the expression may have been represented. There is no harm in replacing
2870 VN_INFO_GET (name)->valnum = name;
2871 value_id = get_expr_value_id (expr);
2872 VN_INFO (name)->value_id = value_id;
2873 nameexpr = get_or_alloc_expr_for_name (name);
2874 add_to_value (value_id, nameexpr);
2876 bitmap_value_replace_in_set (NEW_SETS (block), nameexpr);
2877 bitmap_value_replace_in_set (AVAIL_OUT (block), nameexpr);
2879 pre_stats.insertions++;
2880 if (dump_file && (dump_flags & TDF_DETAILS))
2882 fprintf (dump_file, "Inserted ");
2883 print_gimple_stmt (dump_file, newstmt, 0, 0);
2884 fprintf (dump_file, " in predecessor %d\n", block->index);
2891 /* Insert the to-be-made-available values of expression EXPRNUM for each
2892 predecessor, stored in AVAIL, into the predecessors of BLOCK, and
2893 merge the result with a phi node, given the same value number as
2894 NODE. Return true if we have inserted new stuff. */
2897 insert_into_preds_of_block (basic_block block, unsigned int exprnum,
2900 pre_expr expr = expression_for_id (exprnum);
2902 unsigned int val = get_expr_value_id (expr);
2904 bool insertions = false;
2909 tree type = get_expr_type (expr);
2913 if (dump_file && (dump_flags & TDF_DETAILS))
2915 fprintf (dump_file, "Found partial redundancy for expression ");
2916 print_pre_expr (dump_file, expr);
2917 fprintf (dump_file, " (%04d)\n", val);
2920 /* Make sure we aren't creating an induction variable. */
2921 if (block->loop_depth > 0 && EDGE_COUNT (block->preds) == 2
2922 && expr->kind != REFERENCE)
2924 bool firstinsideloop = false;
2925 bool secondinsideloop = false;
2926 firstinsideloop = flow_bb_inside_loop_p (block->loop_father,
2927 EDGE_PRED (block, 0)->src);
2928 secondinsideloop = flow_bb_inside_loop_p (block->loop_father,
2929 EDGE_PRED (block, 1)->src);
2930 /* Induction variables only have one edge inside the loop. */
2931 if (firstinsideloop ^ secondinsideloop)
2933 if (dump_file && (dump_flags & TDF_DETAILS))
2934 fprintf (dump_file, "Skipping insertion of phi for partial redundancy: Looks like an induction variable\n");
2940 /* Make the necessary insertions. */
2941 FOR_EACH_EDGE (pred, ei, block->preds)
2943 gimple_seq stmts = NULL;
2946 eprime = avail[bprime->index];
2948 if (eprime->kind != NAME && eprime->kind != CONSTANT)
2950 builtexpr = create_expression_by_pieces (bprime,
2954 gcc_assert (!(pred->flags & EDGE_ABNORMAL));
2955 gsi_insert_seq_on_edge (pred, stmts);
2956 avail[bprime->index] = get_or_alloc_expr_for_name (builtexpr);
2959 else if (eprime->kind == CONSTANT)
2961 /* Constants may not have the right type, fold_convert
2962 should give us back a constant with the right type.
2964 tree constant = PRE_EXPR_CONSTANT (eprime);
2965 if (TREE_TYPE (constant) != type)
2967 tree builtexpr = fold_convert (type, constant);
2968 if (is_gimple_min_invariant (builtexpr))
2970 PRE_EXPR_CONSTANT (eprime) = builtexpr;
2974 tree forcedexpr = force_gimple_operand (builtexpr,
2977 if (is_gimple_min_invariant (forcedexpr))
2979 PRE_EXPR_CONSTANT (eprime) = forcedexpr;
2983 if (forcedexpr != builtexpr)
2985 VN_INFO_GET (forcedexpr)->valnum = PRE_EXPR_CONSTANT (eprime);
2986 VN_INFO (forcedexpr)->value_id = get_expr_value_id (eprime);
2990 gimple_stmt_iterator gsi;
2991 gsi = gsi_start (stmts);
2992 for (; !gsi_end_p (gsi); gsi_next (&gsi))
2994 gimple stmt = gsi_stmt (gsi);
2995 VEC_safe_push (gimple, heap, inserted_exprs, stmt);
2996 gimple_set_plf (stmt, NECESSARY, false);
2998 gsi_insert_seq_on_edge (pred, stmts);
3000 avail[bprime->index] = get_or_alloc_expr_for_name (forcedexpr);
3005 else if (eprime->kind == NAME)
3007 /* We may have to do a conversion because our value
3008 numbering can look through types in certain cases, but
3009 our IL requires all operands of a phi node have the same
3011 tree name = PRE_EXPR_NAME (eprime);
3012 if (!useless_type_conversion_p (type, TREE_TYPE (name)))
3016 builtexpr = fold_convert (type, name);
3017 forcedexpr = force_gimple_operand (builtexpr,
3021 if (forcedexpr != name)
3023 VN_INFO_GET (forcedexpr)->valnum = VN_INFO (name)->valnum;
3024 VN_INFO (forcedexpr)->value_id = VN_INFO (name)->value_id;
3029 gimple_stmt_iterator gsi;
3030 gsi = gsi_start (stmts);
3031 for (; !gsi_end_p (gsi); gsi_next (&gsi))
3033 gimple stmt = gsi_stmt (gsi);
3034 VEC_safe_push (gimple, heap, inserted_exprs, stmt);
3035 gimple_set_plf (stmt, NECESSARY, false);
3037 gsi_insert_seq_on_edge (pred, stmts);
3039 avail[bprime->index] = get_or_alloc_expr_for_name (forcedexpr);
3043 /* If we didn't want a phi node, and we made insertions, we still have
3044 inserted new stuff, and thus return true. If we didn't want a phi node,
3045 and didn't make insertions, we haven't added anything new, so return
3047 if (nophi && insertions)
3049 else if (nophi && !insertions)
3052 /* Now build a phi for the new variable. */
3053 if (!prephitemp || TREE_TYPE (prephitemp) != type)
3055 prephitemp = create_tmp_var (type, "prephitmp");
3056 get_var_ann (prephitemp);
3060 add_referenced_var (temp);
3062 if (TREE_CODE (type) == COMPLEX_TYPE
3063 || TREE_CODE (type) == VECTOR_TYPE)
3064 DECL_GIMPLE_REG_P (temp) = 1;
3066 phi = create_phi_node (temp, block);
3067 FOR_EACH_EDGE (pred, ei, block->preds)
3069 pre_expr ae = avail[pred->src->index];
3070 gcc_assert (get_expr_type (ae) == type
3071 || useless_type_conversion_p (type, get_expr_type (ae)));
3072 if (ae->kind == CONSTANT)
3073 add_phi_arg (phi, PRE_EXPR_CONSTANT (ae), pred);
3075 add_phi_arg (phi, PRE_EXPR_NAME (avail[pred->src->index]), pred);
3077 /* If the PHI node is already available, use it. */
3078 if ((res = vn_phi_lookup (phi)) != NULL_TREE)
3080 gimple_stmt_iterator gsi = gsi_for_stmt (phi);
3081 remove_phi_node (&gsi, true);
3083 add_to_value (val, get_or_alloc_expr_for_name (res));
3087 gimple_set_plf (phi, NECESSARY, false);
3088 VN_INFO_GET (gimple_phi_result (phi))->valnum = gimple_phi_result (phi);
3089 VN_INFO (gimple_phi_result (phi))->value_id = val;
3090 VEC_safe_push (gimple, heap, inserted_exprs, phi);
3092 newphi = get_or_alloc_expr_for_name (gimple_phi_result (phi));
3093 add_to_value (val, newphi);
3095 /* The value should *not* exist in PHI_GEN, or else we wouldn't be doing
3096 this insertion, since we test for the existence of this value in PHI_GEN
3097 before proceeding with the partial redundancy checks in insert_aux.
3099 The value may exist in AVAIL_OUT, in particular, it could be represented
3100 by the expression we are trying to eliminate, in which case we want the
3101 replacement to occur. If it's not existing in AVAIL_OUT, we want it
3104 Similarly, to the PHI_GEN case, the value should not exist in NEW_SETS of
3105 this block, because if it did, it would have existed in our dominator's
3106 AVAIL_OUT, and would have been skipped due to the full redundancy check.
3109 bitmap_insert_into_set (PHI_GEN (block), newphi);
3110 bitmap_value_replace_in_set (AVAIL_OUT (block),
3112 bitmap_insert_into_set (NEW_SETS (block),
3115 if (dump_file && (dump_flags & TDF_DETAILS))
3117 fprintf (dump_file, "Created phi ");
3118 print_gimple_stmt (dump_file, phi, 0, 0);
3119 fprintf (dump_file, " in block %d\n", block->index);
3127 /* Perform insertion of partially redundant values.
3128 For BLOCK, do the following:
3129 1. Propagate the NEW_SETS of the dominator into the current block.
3130 If the block has multiple predecessors,
3131 2a. Iterate over the ANTIC expressions for the block to see if
3132 any of them are partially redundant.
3133 2b. If so, insert them into the necessary predecessors to make
3134 the expression fully redundant.
3135 2c. Insert a new PHI merging the values of the predecessors.
3136 2d. Insert the new PHI, and the new expressions, into the
3138 3. Recursively call ourselves on the dominator children of BLOCK.
3140 Steps 1, 2a, and 3 are done by insert_aux. 2b, 2c and 2d are done by
3141 do_regular_insertion and do_partial_insertion.
3146 do_regular_insertion (basic_block block, basic_block dom)
3148 bool new_stuff = false;
3149 VEC (pre_expr, heap) *exprs = sorted_array_from_bitmap_set (ANTIC_IN (block));
3153 for (i = 0; VEC_iterate (pre_expr, exprs, i, expr); i++)
3155 if (expr->kind != NAME)
3159 bool by_some = false;
3160 bool cant_insert = false;
3161 bool all_same = true;
3162 pre_expr first_s = NULL;
3165 pre_expr eprime = NULL;
3167 pre_expr edoubleprime;
3169 val = get_expr_value_id (expr);
3170 if (bitmap_set_contains_value (PHI_GEN (block), val))
3172 if (bitmap_set_contains_value (AVAIL_OUT (dom), val))
3174 if (dump_file && (dump_flags & TDF_DETAILS))
3175 fprintf (dump_file, "Found fully redundant value\n");
3179 avail = XCNEWVEC (pre_expr, last_basic_block);
3180 FOR_EACH_EDGE (pred, ei, block->preds)
3182 unsigned int vprime;
3184 /* We should never run insertion for the exit block
3185 and so not come across fake pred edges. */
3186 gcc_assert (!(pred->flags & EDGE_FAKE));
3188 eprime = phi_translate (expr, ANTIC_IN (block), NULL,
3191 /* eprime will generally only be NULL if the
3192 value of the expression, translated
3193 through the PHI for this predecessor, is
3194 undefined. If that is the case, we can't
3195 make the expression fully redundant,
3196 because its value is undefined along a
3197 predecessor path. We can thus break out
3198 early because it doesn't matter what the
3199 rest of the results are. */
3206 eprime = fully_constant_expression (eprime);
3207 vprime = get_expr_value_id (eprime);
3208 edoubleprime = bitmap_find_leader (AVAIL_OUT (bprime),
3210 if (edoubleprime == NULL)
3212 avail[bprime->index] = eprime;
3217 avail[bprime->index] = edoubleprime;
3219 if (first_s == NULL)
3220 first_s = edoubleprime;
3221 else if (!pre_expr_eq (first_s, edoubleprime))
3225 /* If we can insert it, it's not the same value
3226 already existing along every predecessor, and
3227 it's defined by some predecessor, it is
3228 partially redundant. */
3229 if (!cant_insert && !all_same && by_some && dbg_cnt (treepre_insert))
3231 if (insert_into_preds_of_block (block, get_expression_id (expr),
3235 /* If all edges produce the same value and that value is
3236 an invariant, then the PHI has the same value on all
3237 edges. Note this. */
3238 else if (!cant_insert && all_same && eprime
3239 && (edoubleprime->kind == CONSTANT
3240 || edoubleprime->kind == NAME)
3241 && !value_id_constant_p (val))
3245 bitmap_set_t exprset = VEC_index (bitmap_set_t,
3246 value_expressions, val);
3248 unsigned int new_val = get_expr_value_id (edoubleprime);
3249 FOR_EACH_EXPR_ID_IN_SET (exprset, j, bi)
3251 pre_expr expr = expression_for_id (j);
3253 if (expr->kind == NAME)
3255 vn_ssa_aux_t info = VN_INFO (PRE_EXPR_NAME (expr));
3256 /* Just reset the value id and valnum so it is
3257 the same as the constant we have discovered. */
3258 if (edoubleprime->kind == CONSTANT)
3260 info->valnum = PRE_EXPR_CONSTANT (edoubleprime);
3261 pre_stats.constified++;
3264 info->valnum = PRE_EXPR_NAME (edoubleprime);
3265 info->value_id = new_val;
3273 VEC_free (pre_expr, heap, exprs);
3278 /* Perform insertion for partially anticipatable expressions. There
3279 is only one case we will perform insertion for these. This case is
3280 if the expression is partially anticipatable, and fully available.
3281 In this case, we know that putting it earlier will enable us to
3282 remove the later computation. */
3286 do_partial_partial_insertion (basic_block block, basic_block dom)
3288 bool new_stuff = false;
3289 VEC (pre_expr, heap) *exprs = sorted_array_from_bitmap_set (PA_IN (block));
3293 for (i = 0; VEC_iterate (pre_expr, exprs, i, expr); i++)
3295 if (expr->kind != NAME)
3300 bool cant_insert = false;
3303 pre_expr eprime = NULL;
3306 val = get_expr_value_id (expr);
3307 if (bitmap_set_contains_value (PHI_GEN (block), val))
3309 if (bitmap_set_contains_value (AVAIL_OUT (dom), val))
3312 avail = XCNEWVEC (pre_expr, last_basic_block);
3313 FOR_EACH_EDGE (pred, ei, block->preds)
3315 unsigned int vprime;
3316 pre_expr edoubleprime;
3318 /* We should never run insertion for the exit block
3319 and so not come across fake pred edges. */
3320 gcc_assert (!(pred->flags & EDGE_FAKE));
3322 eprime = phi_translate (expr, ANTIC_IN (block),
3326 /* eprime will generally only be NULL if the
3327 value of the expression, translated
3328 through the PHI for this predecessor, is
3329 undefined. If that is the case, we can't
3330 make the expression fully redundant,
3331 because its value is undefined along a
3332 predecessor path. We can thus break out
3333 early because it doesn't matter what the
3334 rest of the results are. */
3341 eprime = fully_constant_expression (eprime);
3342 vprime = get_expr_value_id (eprime);
3343 edoubleprime = bitmap_find_leader (AVAIL_OUT (bprime),
3345 if (edoubleprime == NULL)
3351 avail[bprime->index] = edoubleprime;
3355 /* If we can insert it, it's not the same value
3356 already existing along every predecessor, and
3357 it's defined by some predecessor, it is
3358 partially redundant. */
3359 if (!cant_insert && by_all && dbg_cnt (treepre_insert))
3361 pre_stats.pa_insert++;
3362 if (insert_into_preds_of_block (block, get_expression_id (expr),
3370 VEC_free (pre_expr, heap, exprs);
3375 insert_aux (basic_block block)
3378 bool new_stuff = false;
3383 dom = get_immediate_dominator (CDI_DOMINATORS, block);
3388 bitmap_set_t newset = NEW_SETS (dom);
3391 /* Note that we need to value_replace both NEW_SETS, and
3392 AVAIL_OUT. For both the case of NEW_SETS, the value may be
3393 represented by some non-simple expression here that we want
3394 to replace it with. */
3395 FOR_EACH_EXPR_ID_IN_SET (newset, i, bi)
3397 pre_expr expr = expression_for_id (i);
3398 bitmap_value_replace_in_set (NEW_SETS (block), expr);
3399 bitmap_value_replace_in_set (AVAIL_OUT (block), expr);
3402 if (!single_pred_p (block))
3404 new_stuff |= do_regular_insertion (block, dom);
3405 if (do_partial_partial)
3406 new_stuff |= do_partial_partial_insertion (block, dom);
3410 for (son = first_dom_son (CDI_DOMINATORS, block);
3412 son = next_dom_son (CDI_DOMINATORS, son))
3414 new_stuff |= insert_aux (son);
3420 /* Perform insertion of partially redundant values. */
3425 bool new_stuff = true;
3427 int num_iterations = 0;
3430 NEW_SETS (bb) = bitmap_set_new ();
3435 new_stuff = insert_aux (ENTRY_BLOCK_PTR);
3437 statistics_histogram_event (cfun, "insert iterations", num_iterations);
3441 /* Add OP to EXP_GEN (block), and possibly to the maximal set if it is
3442 not defined by a phi node.
3443 PHI nodes can't go in the maximal sets because they are not in
3444 TMP_GEN, so it is possible to get into non-monotonic situations
3445 during ANTIC calculation, because it will *add* bits. */
3448 add_to_exp_gen (basic_block block, tree op)
3453 if (TREE_CODE (op) == SSA_NAME && ssa_undefined_value_p (op))
3455 result = get_or_alloc_expr_for_name (op);
3456 bitmap_value_insert_into_set (EXP_GEN (block), result);
3457 if (TREE_CODE (op) != SSA_NAME
3458 || gimple_code (SSA_NAME_DEF_STMT (op)) != GIMPLE_PHI)
3459 bitmap_value_insert_into_set (maximal_set, result);
3463 /* Create value ids for PHI in BLOCK. */
3466 make_values_for_phi (gimple phi, basic_block block)
3468 tree result = gimple_phi_result (phi);
3470 /* We have no need for virtual phis, as they don't represent
3471 actual computations. */
3472 if (is_gimple_reg (result))
3474 pre_expr e = get_or_alloc_expr_for_name (result);
3475 add_to_value (get_expr_value_id (e), e);
3476 bitmap_insert_into_set (PHI_GEN (block), e);
3477 bitmap_value_insert_into_set (AVAIL_OUT (block), e);
3481 /* Compute the AVAIL set for all basic blocks.
3483 This function performs value numbering of the statements in each basic
3484 block. The AVAIL sets are built from information we glean while doing
3485 this value numbering, since the AVAIL sets contain only one entry per
3488 AVAIL_IN[BLOCK] = AVAIL_OUT[dom(BLOCK)].
3489 AVAIL_OUT[BLOCK] = AVAIL_IN[BLOCK] U PHI_GEN[BLOCK] U TMP_GEN[BLOCK]. */
3492 compute_avail (void)
3495 basic_block block, son;
3496 basic_block *worklist;
3500 /* For arguments with default definitions, we pretend they are
3501 defined in the entry block. */
3502 for (param = DECL_ARGUMENTS (current_function_decl);
3504 param = TREE_CHAIN (param))
3506 if (gimple_default_def (cfun, param) != NULL)
3508 tree def = gimple_default_def (cfun, param);
3509 pre_expr e = get_or_alloc_expr_for_name (def);
3511 add_to_value (get_expr_value_id (e), e);
3514 bitmap_insert_into_set (TMP_GEN (ENTRY_BLOCK_PTR), e);
3515 bitmap_value_insert_into_set (maximal_set, e);
3517 bitmap_value_insert_into_set (AVAIL_OUT (ENTRY_BLOCK_PTR), e);
3521 /* Likewise for the static chain decl. */
3522 if (cfun->static_chain_decl)
3524 param = cfun->static_chain_decl;
3525 if (gimple_default_def (cfun, param) != NULL)
3527 tree def = gimple_default_def (cfun, param);
3528 pre_expr e = get_or_alloc_expr_for_name (def);
3530 add_to_value (get_expr_value_id (e), e);
3533 bitmap_insert_into_set (TMP_GEN (ENTRY_BLOCK_PTR), e);
3534 bitmap_value_insert_into_set (maximal_set, e);
3536 bitmap_value_insert_into_set (AVAIL_OUT (ENTRY_BLOCK_PTR), e);
3540 /* Allocate the worklist. */
3541 worklist = XNEWVEC (basic_block, n_basic_blocks);
3543 /* Seed the algorithm by putting the dominator children of the entry
3544 block on the worklist. */
3545 for (son = first_dom_son (CDI_DOMINATORS, ENTRY_BLOCK_PTR);
3547 son = next_dom_son (CDI_DOMINATORS, son))
3548 worklist[sp++] = son;
3550 /* Loop until the worklist is empty. */
3553 gimple_stmt_iterator gsi;
3556 unsigned int stmt_uid = 1;
3558 /* Pick a block from the worklist. */
3559 block = worklist[--sp];
3561 /* Initially, the set of available values in BLOCK is that of
3562 its immediate dominator. */
3563 dom = get_immediate_dominator (CDI_DOMINATORS, block);
3565 bitmap_set_copy (AVAIL_OUT (block), AVAIL_OUT (dom));
3567 /* Generate values for PHI nodes. */
3568 for (gsi = gsi_start_phis (block); !gsi_end_p (gsi); gsi_next (&gsi))
3569 make_values_for_phi (gsi_stmt (gsi), block);
3571 /* Now compute value numbers and populate value sets with all
3572 the expressions computed in BLOCK. */
3573 for (gsi = gsi_start_bb (block); !gsi_end_p (gsi); gsi_next (&gsi))
3578 stmt = gsi_stmt (gsi);
3579 gimple_set_uid (stmt, stmt_uid++);
3581 FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_DEF)
3583 pre_expr e = get_or_alloc_expr_for_name (op);
3585 add_to_value (get_expr_value_id (e), e);
3588 bitmap_insert_into_set (TMP_GEN (block), e);
3589 bitmap_value_insert_into_set (maximal_set, e);
3591 bitmap_value_insert_into_set (AVAIL_OUT (block), e);
3594 if (gimple_has_volatile_ops (stmt)
3595 || stmt_could_throw_p (stmt))
3598 switch (gimple_code (stmt))
3601 FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_USE)
3602 add_to_exp_gen (block, op);
3609 vn_reference_op_t vro;
3610 pre_expr result = NULL;
3611 VEC(vn_reference_op_s, heap) *ops = NULL;
3613 if (!can_value_number_call (stmt))
3616 copy_reference_ops_from_call (stmt, &ops);
3617 vn_reference_lookup_pieces (shared_vuses_from_stmt (stmt),
3619 VEC_free (vn_reference_op_s, heap, ops);
3623 for (i = 0; VEC_iterate (vn_reference_op_s,
3627 if (vro->op0 && TREE_CODE (vro->op0) == SSA_NAME)
3628 add_to_exp_gen (block, vro->op0);
3629 if (vro->op1 && TREE_CODE (vro->op1) == SSA_NAME)
3630 add_to_exp_gen (block, vro->op1);
3631 if (vro->op2 && TREE_CODE (vro->op2) == SSA_NAME)
3632 add_to_exp_gen (block, vro->op2);
3634 result = (pre_expr) pool_alloc (pre_expr_pool);
3635 result->kind = REFERENCE;
3637 PRE_EXPR_REFERENCE (result) = ref;
3639 get_or_alloc_expression_id (result);
3640 add_to_value (get_expr_value_id (result), result);
3643 bitmap_value_insert_into_set (EXP_GEN (block),
3645 bitmap_value_insert_into_set (maximal_set, result);
3652 pre_expr result = NULL;
3653 switch (TREE_CODE_CLASS (gimple_assign_rhs_code (stmt)))
3656 if (is_exception_related (stmt))
3663 vn_nary_op_lookup_pieces (gimple_num_ops (stmt) - 1,
3664 gimple_assign_rhs_code (stmt),
3665 gimple_expr_type (stmt),
3666 gimple_assign_rhs1 (stmt),
3667 gimple_assign_rhs2 (stmt),
3668 NULL_TREE, NULL_TREE, &nary);
3673 for (i = 0; i < nary->length; i++)
3674 if (TREE_CODE (nary->op[i]) == SSA_NAME)
3675 add_to_exp_gen (block, nary->op[i]);
3677 result = (pre_expr) pool_alloc (pre_expr_pool);
3678 result->kind = NARY;
3680 PRE_EXPR_NARY (result) = nary;
3684 case tcc_declaration:
3689 vn_reference_op_t vro;
3691 vn_reference_lookup (gimple_assign_rhs1 (stmt),
3692 shared_vuses_from_stmt (stmt),
3697 for (i = 0; VEC_iterate (vn_reference_op_s,
3701 if (vro->op0 && TREE_CODE (vro->op0) == SSA_NAME)
3702 add_to_exp_gen (block, vro->op0);
3703 if (vro->op1 && TREE_CODE (vro->op1) == SSA_NAME)
3704 add_to_exp_gen (block, vro->op1);
3705 if (vro->op2 && TREE_CODE (vro->op2) == SSA_NAME)
3706 add_to_exp_gen (block, vro->op2);
3708 result = (pre_expr) pool_alloc (pre_expr_pool);
3709 result->kind = REFERENCE;
3711 PRE_EXPR_REFERENCE (result) = ref;
3716 /* For any other statement that we don't
3717 recognize, simply add all referenced
3718 SSA_NAMEs to EXP_GEN. */
3719 FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_USE)
3720 add_to_exp_gen (block, op);
3724 get_or_alloc_expression_id (result);
3725 add_to_value (get_expr_value_id (result), result);
3728 bitmap_value_insert_into_set (EXP_GEN (block), result);
3729 bitmap_value_insert_into_set (maximal_set, result);
3739 /* Put the dominator children of BLOCK on the worklist of blocks
3740 to compute available sets for. */
3741 for (son = first_dom_son (CDI_DOMINATORS, block);
3743 son = next_dom_son (CDI_DOMINATORS, son))
3744 worklist[sp++] = son;
3750 /* Insert the expression for SSA_VN that SCCVN thought would be simpler
3751 than the available expressions for it. The insertion point is
3752 right before the first use in STMT. Returns the SSA_NAME that should
3753 be used for replacement. */
3756 do_SCCVN_insertion (gimple stmt, tree ssa_vn)
3758 basic_block bb = gimple_bb (stmt);
3759 gimple_stmt_iterator gsi;
3760 gimple_seq stmts = NULL;
3764 /* First create a value expression from the expression we want
3765 to insert and associate it with the value handle for SSA_VN. */
3766 e = get_or_alloc_expr_for (vn_get_expr_for (ssa_vn));
3770 /* Then use create_expression_by_pieces to generate a valid
3771 expression to insert at this point of the IL stream. */
3772 expr = create_expression_by_pieces (bb, e, &stmts, stmt, NULL);
3773 if (expr == NULL_TREE)
3775 gsi = gsi_for_stmt (stmt);
3776 gsi_insert_seq_before (&gsi, stmts, GSI_SAME_STMT);
3781 /* Eliminate fully redundant computations. */
3787 unsigned int todo = 0;
3791 gimple_stmt_iterator i;
3793 for (i = gsi_start_bb (b); !gsi_end_p (i); gsi_next (&i))
3795 gimple stmt = gsi_stmt (i);
3797 /* Lookup the RHS of the expression, see if we have an
3798 available computation for it. If so, replace the RHS with
3799 the available computation. */
3800 if (gimple_has_lhs (stmt)
3801 && TREE_CODE (gimple_get_lhs (stmt)) == SSA_NAME
3802 && !gimple_assign_ssa_name_copy_p (stmt)
3803 && (!gimple_assign_single_p (stmt)
3804 || !is_gimple_min_invariant (gimple_assign_rhs1 (stmt)))
3805 && !gimple_has_volatile_ops (stmt)
3806 && !has_zero_uses (gimple_get_lhs (stmt)))
3808 tree lhs = gimple_get_lhs (stmt);
3809 tree rhs = NULL_TREE;
3811 pre_expr lhsexpr = get_or_alloc_expr_for_name (lhs);
3812 pre_expr sprimeexpr;
3814 if (gimple_assign_single_p (stmt))
3815 rhs = gimple_assign_rhs1 (stmt);
3817 sprimeexpr = bitmap_find_leader (AVAIL_OUT (b),
3818 get_expr_value_id (lhsexpr),
3823 if (sprimeexpr->kind == CONSTANT)
3824 sprime = PRE_EXPR_CONSTANT (sprimeexpr);
3825 else if (sprimeexpr->kind == NAME)
3826 sprime = PRE_EXPR_NAME (sprimeexpr);
3831 /* If there is no existing leader but SCCVN knows this
3832 value is constant, use that constant. */
3833 if (!sprime && is_gimple_min_invariant (VN_INFO (lhs)->valnum))
3835 sprime = fold_convert (TREE_TYPE (lhs),
3836 VN_INFO (lhs)->valnum);
3838 if (dump_file && (dump_flags & TDF_DETAILS))
3840 fprintf (dump_file, "Replaced ");
3841 print_gimple_expr (dump_file, stmt, 0, 0);
3842 fprintf (dump_file, " with ");
3843 print_generic_expr (dump_file, sprime, 0);
3844 fprintf (dump_file, " in ");
3845 print_gimple_stmt (dump_file, stmt, 0, 0);
3847 pre_stats.eliminations++;
3848 propagate_tree_value_into_stmt (&i, sprime);
3849 stmt = gsi_stmt (i);
3854 /* If there is no existing usable leader but SCCVN thinks
3855 it has an expression it wants to use as replacement,
3857 if (!sprime || sprime == lhs)
3859 tree val = VN_INFO (lhs)->valnum;
3861 && TREE_CODE (val) == SSA_NAME
3862 && VN_INFO (val)->needs_insertion
3863 && can_PRE_operation (vn_get_expr_for (val)))
3864 sprime = do_SCCVN_insertion (stmt, val);
3868 && (rhs == NULL_TREE
3869 || TREE_CODE (rhs) != SSA_NAME
3870 || may_propagate_copy (rhs, sprime)))
3872 gcc_assert (sprime != rhs);
3874 if (dump_file && (dump_flags & TDF_DETAILS))
3876 fprintf (dump_file, "Replaced ");
3877 print_gimple_expr (dump_file, stmt, 0, 0);
3878 fprintf (dump_file, " with ");
3879 print_generic_expr (dump_file, sprime, 0);
3880 fprintf (dump_file, " in ");
3881 print_gimple_stmt (dump_file, stmt, 0, 0);
3884 if (TREE_CODE (sprime) == SSA_NAME)
3885 gimple_set_plf (SSA_NAME_DEF_STMT (sprime),
3887 /* We need to make sure the new and old types actually match,
3888 which may require adding a simple cast, which fold_convert
3890 if ((!rhs || TREE_CODE (rhs) != SSA_NAME)
3891 && !useless_type_conversion_p (gimple_expr_type (stmt),
3892 TREE_TYPE (sprime)))
3893 sprime = fold_convert (gimple_expr_type (stmt), sprime);
3895 pre_stats.eliminations++;
3896 propagate_tree_value_into_stmt (&i, sprime);
3897 stmt = gsi_stmt (i);
3900 /* If we removed EH side effects from the statement, clean
3901 its EH information. */
3902 if (maybe_clean_or_replace_eh_stmt (stmt, stmt))
3904 bitmap_set_bit (need_eh_cleanup,
3905 gimple_bb (stmt)->index);
3906 if (dump_file && (dump_flags & TDF_DETAILS))
3907 fprintf (dump_file, " Removed EH side effects.\n");
3911 /* Visit COND_EXPRs and fold the comparison with the
3912 available value-numbers. */
3913 else if (gimple_code (stmt) == GIMPLE_COND)
3915 tree op0 = gimple_cond_lhs (stmt);
3916 tree op1 = gimple_cond_rhs (stmt);
3919 if (TREE_CODE (op0) == SSA_NAME)
3920 op0 = VN_INFO (op0)->valnum;
3921 if (TREE_CODE (op1) == SSA_NAME)
3922 op1 = VN_INFO (op1)->valnum;
3923 result = fold_binary (gimple_cond_code (stmt), boolean_type_node,
3925 if (result && TREE_CODE (result) == INTEGER_CST)
3927 if (integer_zerop (result))
3928 gimple_cond_make_false (stmt);
3930 gimple_cond_make_true (stmt);
3932 todo = TODO_cleanup_cfg;
3941 /* Borrow a bit of tree-ssa-dce.c for the moment.
3942 XXX: In 4.1, we should be able to just run a DCE pass after PRE, though
3943 this may be a bit faster, and we may want critical edges kept split. */
3945 /* If OP's defining statement has not already been determined to be necessary,
3946 mark that statement necessary. Return the stmt, if it is newly
3949 static inline gimple
3950 mark_operand_necessary (tree op)
3956 if (TREE_CODE (op) != SSA_NAME)
3959 stmt = SSA_NAME_DEF_STMT (op);
3962 if (gimple_plf (stmt, NECESSARY)
3963 || gimple_nop_p (stmt))
3966 gimple_set_plf (stmt, NECESSARY, true);
3970 /* Because we don't follow exactly the standard PRE algorithm, and decide not
3971 to insert PHI nodes sometimes, and because value numbering of casts isn't
3972 perfect, we sometimes end up inserting dead code. This simple DCE-like
3973 pass removes any insertions we made that weren't actually used. */
3976 remove_dead_inserted_code (void)
3978 VEC(gimple,heap) *worklist = NULL;
3982 worklist = VEC_alloc (gimple, heap, VEC_length (gimple, inserted_exprs));
3983 for (i = 0; VEC_iterate (gimple, inserted_exprs, i, t); i++)
3985 if (gimple_plf (t, NECESSARY))
3986 VEC_quick_push (gimple, worklist, t);
3988 while (VEC_length (gimple, worklist) > 0)
3990 t = VEC_pop (gimple, worklist);
3992 /* PHI nodes are somewhat special in that each PHI alternative has
3993 data and control dependencies. All the statements feeding the
3994 PHI node's arguments are always necessary. */
3995 if (gimple_code (t) == GIMPLE_PHI)
3999 VEC_reserve (gimple, heap, worklist, gimple_phi_num_args (t));
4000 for (k = 0; k < gimple_phi_num_args (t); k++)
4002 tree arg = PHI_ARG_DEF (t, k);
4003 if (TREE_CODE (arg) == SSA_NAME)
4005 gimple n = mark_operand_necessary (arg);
4007 VEC_quick_push (gimple, worklist, n);
4013 /* Propagate through the operands. Examine all the USE, VUSE and
4014 VDEF operands in this statement. Mark all the statements
4015 which feed this statement's uses as necessary. */
4019 /* The operands of VDEF expressions are also needed as they
4020 represent potential definitions that may reach this
4021 statement (VDEF operands allow us to follow def-def
4024 FOR_EACH_SSA_TREE_OPERAND (use, t, iter, SSA_OP_ALL_USES)
4026 gimple n = mark_operand_necessary (use);
4028 VEC_safe_push (gimple, heap, worklist, n);
4033 for (i = 0; VEC_iterate (gimple, inserted_exprs, i, t); i++)
4035 if (!gimple_plf (t, NECESSARY))
4037 gimple_stmt_iterator gsi;
4039 if (dump_file && (dump_flags & TDF_DETAILS))
4041 fprintf (dump_file, "Removing unnecessary insertion:");
4042 print_gimple_stmt (dump_file, t, 0, 0);
4045 gsi = gsi_for_stmt (t);
4046 if (gimple_code (t) == GIMPLE_PHI)
4047 remove_phi_node (&gsi, true);
4049 gsi_remove (&gsi, true);
4053 VEC_free (gimple, heap, worklist);
4056 /* Initialize data structures used by PRE. */
4059 init_pre (bool do_fre)
4063 next_expression_id = 1;
4065 VEC_safe_push (pre_expr, heap, expressions, NULL);
4066 value_expressions = VEC_alloc (bitmap_set_t, heap, get_max_value_id () + 1);
4067 VEC_safe_grow_cleared (bitmap_set_t, heap, value_expressions,
4068 get_max_value_id() + 1);
4072 inserted_exprs = NULL;
4073 need_creation = NULL;
4074 pretemp = NULL_TREE;
4075 storetemp = NULL_TREE;
4076 prephitemp = NULL_TREE;
4078 connect_infinite_loops_to_exit ();
4079 memset (&pre_stats, 0, sizeof (pre_stats));
4082 postorder = XNEWVEC (int, n_basic_blocks - NUM_FIXED_BLOCKS);
4083 post_order_compute (postorder, false, false);
4086 bb->aux = XCNEWVEC (struct bb_bitmap_sets, 1);
4088 calculate_dominance_info (CDI_POST_DOMINATORS);
4089 calculate_dominance_info (CDI_DOMINATORS);
4091 bitmap_obstack_initialize (&grand_bitmap_obstack);
4092 phi_translate_table = htab_create (5110, expr_pred_trans_hash,
4093 expr_pred_trans_eq, free);
4094 expression_to_id = htab_create (num_ssa_names * 3,
4097 seen_during_translate = BITMAP_ALLOC (&grand_bitmap_obstack);
4098 bitmap_set_pool = create_alloc_pool ("Bitmap sets",
4099 sizeof (struct bitmap_set), 30);
4100 pre_expr_pool = create_alloc_pool ("pre_expr nodes",
4101 sizeof (struct pre_expr_d), 30);
4104 EXP_GEN (bb) = bitmap_set_new ();
4105 PHI_GEN (bb) = bitmap_set_new ();
4106 TMP_GEN (bb) = bitmap_set_new ();
4107 AVAIL_OUT (bb) = bitmap_set_new ();
4109 maximal_set = in_fre ? NULL : bitmap_set_new ();
4111 need_eh_cleanup = BITMAP_ALLOC (NULL);
4115 /* Deallocate data structures used by PRE. */
4118 fini_pre (bool do_fre)
4123 VEC_free (bitmap_set_t, heap, value_expressions);
4124 VEC_free (gimple, heap, inserted_exprs);
4125 VEC_free (gimple, heap, need_creation);
4126 bitmap_obstack_release (&grand_bitmap_obstack);
4127 free_alloc_pool (bitmap_set_pool);
4128 free_alloc_pool (pre_expr_pool);
4129 htab_delete (phi_translate_table);
4130 htab_delete (expression_to_id);
4138 free_dominance_info (CDI_POST_DOMINATORS);
4140 if (!bitmap_empty_p (need_eh_cleanup))
4142 gimple_purge_all_dead_eh_edges (need_eh_cleanup);
4143 cleanup_tree_cfg ();
4146 BITMAP_FREE (need_eh_cleanup);
4149 loop_optimizer_finalize ();
4152 /* Main entry point to the SSA-PRE pass. DO_FRE is true if the caller
4153 only wants to do full redundancy elimination. */
4156 execute_pre (bool do_fre ATTRIBUTE_UNUSED)
4158 unsigned int todo = 0;
4160 do_partial_partial = optimize > 2;
4162 /* This has to happen before SCCVN runs because
4163 loop_optimizer_init may create new phis, etc. */
4165 loop_optimizer_init (LOOPS_NORMAL);
4167 if (!run_scc_vn (do_fre))
4171 remove_dead_inserted_code ();
4172 loop_optimizer_finalize ();
4180 /* Collect and value number expressions computed in each basic block. */
4183 if (dump_file && (dump_flags & TDF_DETAILS))
4189 print_bitmap_set (dump_file, EXP_GEN (bb), "exp_gen", bb->index);
4190 print_bitmap_set (dump_file, TMP_GEN (bb), "tmp_gen",
4192 print_bitmap_set (dump_file, AVAIL_OUT (bb), "avail_out",
4197 /* Insert can get quite slow on an incredibly large number of basic
4198 blocks due to some quadratic behavior. Until this behavior is
4199 fixed, don't run it when he have an incredibly large number of
4200 bb's. If we aren't going to run insert, there is no point in
4201 computing ANTIC, either, even though it's plenty fast. */
4202 if (!do_fre && n_basic_blocks < 4000)
4208 /* Remove all the redundant expressions. */
4209 todo |= eliminate ();
4211 statistics_counter_event (cfun, "Insertions", pre_stats.insertions);
4212 statistics_counter_event (cfun, "PA inserted", pre_stats.pa_insert);
4213 statistics_counter_event (cfun, "New PHIs", pre_stats.phis);
4214 statistics_counter_event (cfun, "Eliminated", pre_stats.eliminations);
4215 statistics_counter_event (cfun, "Constified", pre_stats.constified);
4217 /* Make sure to remove fake edges before committing our inserts.
4218 This makes sure we don't end up with extra critical edges that
4219 we would need to split. */
4220 remove_fake_exit_edges ();
4221 gsi_commit_edge_inserts ();
4223 clear_expression_ids ();
4226 remove_dead_inserted_code ();
4233 /* Gate and execute functions for PRE. */
4238 return TODO_rebuild_alias | execute_pre (false);
4244 /* PRE tends to generate bigger code. */
4245 return flag_tree_pre != 0 && optimize_function_for_speed_p (cfun);
4248 struct gimple_opt_pass pass_pre =
4253 gate_pre, /* gate */
4254 do_pre, /* execute */
4257 0, /* static_pass_number */
4258 TV_TREE_PRE, /* tv_id */
4259 PROP_no_crit_edges | PROP_cfg
4260 | PROP_ssa | PROP_alias, /* properties_required */
4261 0, /* properties_provided */
4262 0, /* properties_destroyed */
4263 0, /* todo_flags_start */
4264 TODO_update_ssa_only_virtuals | TODO_dump_func | TODO_ggc_collect
4265 | TODO_verify_ssa /* todo_flags_finish */
4270 /* Gate and execute functions for FRE. */
4275 return execute_pre (true);
4281 return flag_tree_fre != 0;
4284 struct gimple_opt_pass pass_fre =
4289 gate_fre, /* gate */
4290 execute_fre, /* execute */
4293 0, /* static_pass_number */
4294 TV_TREE_FRE, /* tv_id */
4295 PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */
4296 0, /* properties_provided */
4297 0, /* properties_destroyed */
4298 0, /* todo_flags_start */
4299 TODO_dump_func | TODO_ggc_collect | TODO_verify_ssa /* todo_flags_finish */