2 Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009
3 Free Software Foundation, Inc.
4 Contributed by Daniel Berlin <dan@dberlin.org> and Steven Bosscher
7 This file is part of GCC.
9 GCC is free software; you can redistribute it and/or modify
10 it under the terms of the GNU General Public License as published by
11 the Free Software Foundation; either version 3, or (at your option)
14 GCC is distributed in the hope that it will be useful,
15 but WITHOUT ANY WARRANTY; without even the implied warranty of
16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 GNU General Public License for more details.
19 You should have received a copy of the GNU General Public License
20 along with GCC; see the file COPYING3. If not see
21 <http://www.gnu.org/licenses/>. */
25 #include "coretypes.h"
29 #include "basic-block.h"
30 #include "diagnostic.h"
31 #include "tree-inline.h"
32 #include "tree-flow.h"
34 #include "tree-dump.h"
38 #include "tree-iterator.h"
40 #include "alloc-pool.h"
42 #include "tree-pass.h"
45 #include "langhooks.h"
47 #include "tree-ssa-sccvn.h"
48 #include "tree-scalar-evolution.h"
54 1. Avail sets can be shared by making an avail_find_leader that
55 walks up the dominator tree and looks in those avail sets.
56 This might affect code optimality, it's unclear right now.
57 2. Strength reduction can be performed by anticipating expressions
58 we can repair later on.
59 3. We can do back-substitution or smarter value numbering to catch
60 commutative expressions split up over multiple statements.
63 /* For ease of terminology, "expression node" in the below refers to
64 every expression node but GIMPLE_ASSIGN, because GIMPLE_ASSIGNs
65 represent the actual statement containing the expressions we care about,
66 and we cache the value number by putting it in the expression. */
70 First we walk the statements to generate the AVAIL sets, the
71 EXP_GEN sets, and the tmp_gen sets. EXP_GEN sets represent the
72 generation of values/expressions by a given block. We use them
73 when computing the ANTIC sets. The AVAIL sets consist of
74 SSA_NAME's that represent values, so we know what values are
75 available in what blocks. AVAIL is a forward dataflow problem. In
76 SSA, values are never killed, so we don't need a kill set, or a
77 fixpoint iteration, in order to calculate the AVAIL sets. In
78 traditional parlance, AVAIL sets tell us the downsafety of the
81 Next, we generate the ANTIC sets. These sets represent the
82 anticipatable expressions. ANTIC is a backwards dataflow
83 problem. An expression is anticipatable in a given block if it could
84 be generated in that block. This means that if we had to perform
85 an insertion in that block, of the value of that expression, we
86 could. Calculating the ANTIC sets requires phi translation of
87 expressions, because the flow goes backwards through phis. We must
88 iterate to a fixpoint of the ANTIC sets, because we have a kill
89 set. Even in SSA form, values are not live over the entire
90 function, only from their definition point onwards. So we have to
91 remove values from the ANTIC set once we go past the definition
92 point of the leaders that make them up.
93 compute_antic/compute_antic_aux performs this computation.
95 Third, we perform insertions to make partially redundant
96 expressions fully redundant.
98 An expression is partially redundant (excluding partial
101 1. It is AVAIL in some, but not all, of the predecessors of a
103 2. It is ANTIC in all the predecessors.
105 In order to make it fully redundant, we insert the expression into
106 the predecessors where it is not available, but is ANTIC.
108 For the partial anticipation case, we only perform insertion if it
109 is partially anticipated in some block, and fully available in all
112 insert/insert_aux/do_regular_insertion/do_partial_partial_insertion
113 performs these steps.
115 Fourth, we eliminate fully redundant expressions.
116 This is a simple statement walk that replaces redundant
117 calculations with the now available values. */
119 /* Representations of value numbers:
121 Value numbers are represented by a representative SSA_NAME. We
122 will create fake SSA_NAME's in situations where we need a
123 representative but do not have one (because it is a complex
124 expression). In order to facilitate storing the value numbers in
125 bitmaps, and keep the number of wasted SSA_NAME's down, we also
126 associate a value_id with each value number, and create full blown
127 ssa_name's only where we actually need them (IE in operands of
128 existing expressions).
130 Theoretically you could replace all the value_id's with
131 SSA_NAME_VERSION, but this would allocate a large number of
132 SSA_NAME's (which are each > 30 bytes) just to get a 4 byte number.
133 It would also require an additional indirection at each point we
136 /* Representation of expressions on value numbers:
138 Expressions consisting of value numbers are represented the same
139 way as our VN internally represents them, with an additional
140 "pre_expr" wrapping around them in order to facilitate storing all
141 of the expressions in the same sets. */
143 /* Representation of sets:
145 The dataflow sets do not need to be sorted in any particular order
146 for the majority of their lifetime, are simply represented as two
147 bitmaps, one that keeps track of values present in the set, and one
148 that keeps track of expressions present in the set.
150 When we need them in topological order, we produce it on demand by
151 transforming the bitmap into an array and sorting it into topo
154 /* Type of expression, used to know which member of the PRE_EXPR union
165 typedef union pre_expr_union_d
170 vn_reference_t reference;
173 typedef struct pre_expr_d
175 enum pre_expr_kind kind;
180 #define PRE_EXPR_NAME(e) (e)->u.name
181 #define PRE_EXPR_NARY(e) (e)->u.nary
182 #define PRE_EXPR_REFERENCE(e) (e)->u.reference
183 #define PRE_EXPR_CONSTANT(e) (e)->u.constant
186 pre_expr_eq (const void *p1, const void *p2)
188 const struct pre_expr_d *e1 = (const struct pre_expr_d *) p1;
189 const struct pre_expr_d *e2 = (const struct pre_expr_d *) p2;
191 if (e1->kind != e2->kind)
197 return vn_constant_eq_with_type (PRE_EXPR_CONSTANT (e1),
198 PRE_EXPR_CONSTANT (e2));
200 return PRE_EXPR_NAME (e1) == PRE_EXPR_NAME (e2);
202 return vn_nary_op_eq (PRE_EXPR_NARY (e1), PRE_EXPR_NARY (e2));
204 return vn_reference_eq (PRE_EXPR_REFERENCE (e1),
205 PRE_EXPR_REFERENCE (e2));
212 pre_expr_hash (const void *p1)
214 const struct pre_expr_d *e = (const struct pre_expr_d *) p1;
218 return vn_hash_constant_with_type (PRE_EXPR_CONSTANT (e));
220 return iterative_hash_hashval_t (SSA_NAME_VERSION (PRE_EXPR_NAME (e)), 0);
222 return PRE_EXPR_NARY (e)->hashcode;
224 return PRE_EXPR_REFERENCE (e)->hashcode;
231 /* Next global expression id number. */
232 static unsigned int next_expression_id;
234 /* Mapping from expression to id number we can use in bitmap sets. */
235 DEF_VEC_P (pre_expr);
236 DEF_VEC_ALLOC_P (pre_expr, heap);
237 static VEC(pre_expr, heap) *expressions;
238 static htab_t expression_to_id;
240 /* Allocate an expression id for EXPR. */
242 static inline unsigned int
243 alloc_expression_id (pre_expr expr)
246 /* Make sure we won't overflow. */
247 gcc_assert (next_expression_id + 1 > next_expression_id);
248 expr->id = next_expression_id++;
249 VEC_safe_push (pre_expr, heap, expressions, expr);
250 slot = htab_find_slot (expression_to_id, expr, INSERT);
253 return next_expression_id - 1;
256 /* Return the expression id for tree EXPR. */
258 static inline unsigned int
259 get_expression_id (const pre_expr expr)
264 static inline unsigned int
265 lookup_expression_id (const pre_expr expr)
269 slot = htab_find_slot (expression_to_id, expr, NO_INSERT);
272 return ((pre_expr)*slot)->id;
275 /* Return the existing expression id for EXPR, or create one if one
276 does not exist yet. */
278 static inline unsigned int
279 get_or_alloc_expression_id (pre_expr expr)
281 unsigned int id = lookup_expression_id (expr);
283 return alloc_expression_id (expr);
284 return expr->id = id;
287 /* Return the expression that has expression id ID */
289 static inline pre_expr
290 expression_for_id (unsigned int id)
292 return VEC_index (pre_expr, expressions, id);
295 /* Free the expression id field in all of our expressions,
296 and then destroy the expressions array. */
299 clear_expression_ids (void)
301 VEC_free (pre_expr, heap, expressions);
304 static alloc_pool pre_expr_pool;
306 /* Given an SSA_NAME NAME, get or create a pre_expr to represent it. */
309 get_or_alloc_expr_for_name (tree name)
311 pre_expr result = (pre_expr) pool_alloc (pre_expr_pool);
312 unsigned int result_id;
316 PRE_EXPR_NAME (result) = name;
317 result_id = lookup_expression_id (result);
320 pool_free (pre_expr_pool, result);
321 result = expression_for_id (result_id);
324 get_or_alloc_expression_id (result);
328 static bool in_fre = false;
330 /* An unordered bitmap set. One bitmap tracks values, the other,
332 typedef struct bitmap_set
338 #define FOR_EACH_EXPR_ID_IN_SET(set, id, bi) \
339 EXECUTE_IF_SET_IN_BITMAP((set)->expressions, 0, (id), (bi))
341 #define FOR_EACH_VALUE_ID_IN_SET(set, id, bi) \
342 EXECUTE_IF_SET_IN_BITMAP((set)->values, 0, (id), (bi))
344 /* Mapping from value id to expressions with that value_id. */
345 DEF_VEC_P (bitmap_set_t);
346 DEF_VEC_ALLOC_P (bitmap_set_t, heap);
347 static VEC(bitmap_set_t, heap) *value_expressions;
349 /* Sets that we need to keep track of. */
350 typedef struct bb_bitmap_sets
352 /* The EXP_GEN set, which represents expressions/values generated in
354 bitmap_set_t exp_gen;
356 /* The PHI_GEN set, which represents PHI results generated in a
358 bitmap_set_t phi_gen;
360 /* The TMP_GEN set, which represents results/temporaries generated
361 in a basic block. IE the LHS of an expression. */
362 bitmap_set_t tmp_gen;
364 /* The AVAIL_OUT set, which represents which values are available in
365 a given basic block. */
366 bitmap_set_t avail_out;
368 /* The ANTIC_IN set, which represents which values are anticipatable
369 in a given basic block. */
370 bitmap_set_t antic_in;
372 /* The PA_IN set, which represents which values are
373 partially anticipatable in a given basic block. */
376 /* The NEW_SETS set, which is used during insertion to augment the
377 AVAIL_OUT set of blocks with the new insertions performed during
378 the current iteration. */
379 bitmap_set_t new_sets;
381 /* A cache for value_dies_in_block_x. */
384 /* True if we have visited this block during ANTIC calculation. */
385 unsigned int visited : 1;
387 /* True we have deferred processing this block during ANTIC
388 calculation until its successor is processed. */
389 unsigned int deferred : 1;
391 /* True when the block contains a call that might not return. */
392 unsigned int contains_may_not_return_call : 1;
395 #define EXP_GEN(BB) ((bb_value_sets_t) ((BB)->aux))->exp_gen
396 #define PHI_GEN(BB) ((bb_value_sets_t) ((BB)->aux))->phi_gen
397 #define TMP_GEN(BB) ((bb_value_sets_t) ((BB)->aux))->tmp_gen
398 #define AVAIL_OUT(BB) ((bb_value_sets_t) ((BB)->aux))->avail_out
399 #define ANTIC_IN(BB) ((bb_value_sets_t) ((BB)->aux))->antic_in
400 #define PA_IN(BB) ((bb_value_sets_t) ((BB)->aux))->pa_in
401 #define NEW_SETS(BB) ((bb_value_sets_t) ((BB)->aux))->new_sets
402 #define EXPR_DIES(BB) ((bb_value_sets_t) ((BB)->aux))->expr_dies
403 #define BB_VISITED(BB) ((bb_value_sets_t) ((BB)->aux))->visited
404 #define BB_DEFERRED(BB) ((bb_value_sets_t) ((BB)->aux))->deferred
405 #define BB_MAY_NOTRETURN(BB) ((bb_value_sets_t) ((BB)->aux))->contains_may_not_return_call
408 /* Basic block list in postorder. */
409 static int *postorder;
411 /* This structure is used to keep track of statistics on what
412 optimization PRE was able to perform. */
415 /* The number of RHS computations eliminated by PRE. */
418 /* The number of new expressions/temporaries generated by PRE. */
421 /* The number of inserts found due to partial anticipation */
424 /* The number of new PHI nodes added by PRE. */
427 /* The number of values found constant. */
432 static bool do_partial_partial;
433 static pre_expr bitmap_find_leader (bitmap_set_t, unsigned int, gimple);
434 static void bitmap_value_insert_into_set (bitmap_set_t, pre_expr);
435 static void bitmap_value_replace_in_set (bitmap_set_t, pre_expr);
436 static void bitmap_set_copy (bitmap_set_t, bitmap_set_t);
437 static bool bitmap_set_contains_value (bitmap_set_t, unsigned int);
438 static void bitmap_insert_into_set (bitmap_set_t, pre_expr);
439 static void bitmap_insert_into_set_1 (bitmap_set_t, pre_expr, bool);
440 static bitmap_set_t bitmap_set_new (void);
441 static tree create_expression_by_pieces (basic_block, pre_expr, gimple_seq *,
443 static tree find_or_generate_expression (basic_block, pre_expr, gimple_seq *,
445 static unsigned int get_expr_value_id (pre_expr);
447 /* We can add and remove elements and entries to and from sets
448 and hash tables, so we use alloc pools for them. */
450 static alloc_pool bitmap_set_pool;
451 static bitmap_obstack grand_bitmap_obstack;
453 /* To avoid adding 300 temporary variables when we only need one, we
454 only create one temporary variable, on demand, and build ssa names
455 off that. We do have to change the variable if the types don't
456 match the current variable's type. */
458 static tree storetemp;
459 static tree prephitemp;
461 /* Set of blocks with statements that have had its EH information
463 static bitmap need_eh_cleanup;
465 /* The phi_translate_table caches phi translations for a given
466 expression and predecessor. */
468 static htab_t phi_translate_table;
470 /* A three tuple {e, pred, v} used to cache phi translations in the
471 phi_translate_table. */
473 typedef struct expr_pred_trans_d
475 /* The expression. */
478 /* The predecessor block along which we translated the expression. */
481 /* The value that resulted from the translation. */
484 /* The hashcode for the expression, pred pair. This is cached for
487 } *expr_pred_trans_t;
488 typedef const struct expr_pred_trans_d *const_expr_pred_trans_t;
490 /* Return the hash value for a phi translation table entry. */
493 expr_pred_trans_hash (const void *p)
495 const_expr_pred_trans_t const ve = (const_expr_pred_trans_t) p;
499 /* Return true if two phi translation table entries are the same.
500 P1 and P2 should point to the expr_pred_trans_t's to be compared.*/
503 expr_pred_trans_eq (const void *p1, const void *p2)
505 const_expr_pred_trans_t const ve1 = (const_expr_pred_trans_t) p1;
506 const_expr_pred_trans_t const ve2 = (const_expr_pred_trans_t) p2;
507 basic_block b1 = ve1->pred;
508 basic_block b2 = ve2->pred;
510 /* If they are not translations for the same basic block, they can't
514 return pre_expr_eq (ve1->e, ve2->e);
517 /* Search in the phi translation table for the translation of
518 expression E in basic block PRED.
519 Return the translated value, if found, NULL otherwise. */
521 static inline pre_expr
522 phi_trans_lookup (pre_expr e, basic_block pred)
525 struct expr_pred_trans_d ept;
529 ept.hashcode = iterative_hash_hashval_t (pre_expr_hash (e), pred->index);
530 slot = htab_find_slot_with_hash (phi_translate_table, &ept, ept.hashcode,
535 return ((expr_pred_trans_t) *slot)->v;
539 /* Add the tuple mapping from {expression E, basic block PRED} to
540 value V, to the phi translation table. */
543 phi_trans_add (pre_expr e, pre_expr v, basic_block pred)
546 expr_pred_trans_t new_pair = XNEW (struct expr_pred_trans_d);
548 new_pair->pred = pred;
550 new_pair->hashcode = iterative_hash_hashval_t (pre_expr_hash (e),
553 slot = htab_find_slot_with_hash (phi_translate_table, new_pair,
554 new_pair->hashcode, INSERT);
557 *slot = (void *) new_pair;
561 /* Add expression E to the expression set of value id V. */
564 add_to_value (unsigned int v, pre_expr e)
568 gcc_assert (get_expr_value_id (e) == v);
570 if (v >= VEC_length (bitmap_set_t, value_expressions))
572 VEC_safe_grow_cleared (bitmap_set_t, heap, value_expressions,
576 set = VEC_index (bitmap_set_t, value_expressions, v);
579 set = bitmap_set_new ();
580 VEC_replace (bitmap_set_t, value_expressions, v, set);
583 bitmap_insert_into_set_1 (set, e, true);
586 /* Create a new bitmap set and return it. */
589 bitmap_set_new (void)
591 bitmap_set_t ret = (bitmap_set_t) pool_alloc (bitmap_set_pool);
592 ret->expressions = BITMAP_ALLOC (&grand_bitmap_obstack);
593 ret->values = BITMAP_ALLOC (&grand_bitmap_obstack);
597 /* Return the value id for a PRE expression EXPR. */
600 get_expr_value_id (pre_expr expr)
607 id = get_constant_value_id (PRE_EXPR_CONSTANT (expr));
610 id = get_or_alloc_constant_value_id (PRE_EXPR_CONSTANT (expr));
611 add_to_value (id, expr);
616 return VN_INFO (PRE_EXPR_NAME (expr))->value_id;
618 return PRE_EXPR_NARY (expr)->value_id;
620 return PRE_EXPR_REFERENCE (expr)->value_id;
626 /* Remove an expression EXPR from a bitmapped set. */
629 bitmap_remove_from_set (bitmap_set_t set, pre_expr expr)
631 unsigned int val = get_expr_value_id (expr);
632 if (!value_id_constant_p (val))
634 bitmap_clear_bit (set->values, val);
635 bitmap_clear_bit (set->expressions, get_expression_id (expr));
640 bitmap_insert_into_set_1 (bitmap_set_t set, pre_expr expr,
641 bool allow_constants)
643 unsigned int val = get_expr_value_id (expr);
644 if (allow_constants || !value_id_constant_p (val))
646 /* We specifically expect this and only this function to be able to
647 insert constants into a set. */
648 bitmap_set_bit (set->values, val);
649 bitmap_set_bit (set->expressions, get_or_alloc_expression_id (expr));
653 /* Insert an expression EXPR into a bitmapped set. */
656 bitmap_insert_into_set (bitmap_set_t set, pre_expr expr)
658 bitmap_insert_into_set_1 (set, expr, false);
661 /* Copy a bitmapped set ORIG, into bitmapped set DEST. */
664 bitmap_set_copy (bitmap_set_t dest, bitmap_set_t orig)
666 bitmap_copy (dest->expressions, orig->expressions);
667 bitmap_copy (dest->values, orig->values);
671 /* Free memory used up by SET. */
673 bitmap_set_free (bitmap_set_t set)
675 BITMAP_FREE (set->expressions);
676 BITMAP_FREE (set->values);
680 /* Generate an topological-ordered array of bitmap set SET. */
682 static VEC(pre_expr, heap) *
683 sorted_array_from_bitmap_set (bitmap_set_t set)
686 bitmap_iterator bi, bj;
687 VEC(pre_expr, heap) *result = NULL;
689 FOR_EACH_VALUE_ID_IN_SET (set, i, bi)
691 /* The number of expressions having a given value is usually
692 relatively small. Thus, rather than making a vector of all
693 the expressions and sorting it by value-id, we walk the values
694 and check in the reverse mapping that tells us what expressions
695 have a given value, to filter those in our set. As a result,
696 the expressions are inserted in value-id order, which means
699 If this is somehow a significant lose for some cases, we can
700 choose which set to walk based on the set size. */
701 bitmap_set_t exprset = VEC_index (bitmap_set_t, value_expressions, i);
702 FOR_EACH_EXPR_ID_IN_SET (exprset, j, bj)
704 if (bitmap_bit_p (set->expressions, j))
705 VEC_safe_push (pre_expr, heap, result, expression_for_id (j));
712 /* Perform bitmapped set operation DEST &= ORIG. */
715 bitmap_set_and (bitmap_set_t dest, bitmap_set_t orig)
722 bitmap temp = BITMAP_ALLOC (&grand_bitmap_obstack);
724 bitmap_and_into (dest->values, orig->values);
725 bitmap_copy (temp, dest->expressions);
726 EXECUTE_IF_SET_IN_BITMAP (temp, 0, i, bi)
728 pre_expr expr = expression_for_id (i);
729 unsigned int value_id = get_expr_value_id (expr);
730 if (!bitmap_bit_p (dest->values, value_id))
731 bitmap_clear_bit (dest->expressions, i);
737 /* Subtract all values and expressions contained in ORIG from DEST. */
740 bitmap_set_subtract (bitmap_set_t dest, bitmap_set_t orig)
742 bitmap_set_t result = bitmap_set_new ();
746 bitmap_and_compl (result->expressions, dest->expressions,
749 FOR_EACH_EXPR_ID_IN_SET (result, i, bi)
751 pre_expr expr = expression_for_id (i);
752 unsigned int value_id = get_expr_value_id (expr);
753 bitmap_set_bit (result->values, value_id);
759 /* Subtract all the values in bitmap set B from bitmap set A. */
762 bitmap_set_subtract_values (bitmap_set_t a, bitmap_set_t b)
766 bitmap temp = BITMAP_ALLOC (&grand_bitmap_obstack);
768 bitmap_copy (temp, a->expressions);
769 EXECUTE_IF_SET_IN_BITMAP (temp, 0, i, bi)
771 pre_expr expr = expression_for_id (i);
772 if (bitmap_set_contains_value (b, get_expr_value_id (expr)))
773 bitmap_remove_from_set (a, expr);
779 /* Return true if bitmapped set SET contains the value VALUE_ID. */
782 bitmap_set_contains_value (bitmap_set_t set, unsigned int value_id)
784 if (value_id_constant_p (value_id))
787 if (!set || bitmap_empty_p (set->expressions))
790 return bitmap_bit_p (set->values, value_id);
794 bitmap_set_contains_expr (bitmap_set_t set, const pre_expr expr)
796 return bitmap_bit_p (set->expressions, get_expression_id (expr));
799 /* Replace an instance of value LOOKFOR with expression EXPR in SET. */
802 bitmap_set_replace_value (bitmap_set_t set, unsigned int lookfor,
805 bitmap_set_t exprset;
809 if (value_id_constant_p (lookfor))
812 if (!bitmap_set_contains_value (set, lookfor))
815 /* The number of expressions having a given value is usually
816 significantly less than the total number of expressions in SET.
817 Thus, rather than check, for each expression in SET, whether it
818 has the value LOOKFOR, we walk the reverse mapping that tells us
819 what expressions have a given value, and see if any of those
820 expressions are in our set. For large testcases, this is about
821 5-10x faster than walking the bitmap. If this is somehow a
822 significant lose for some cases, we can choose which set to walk
823 based on the set size. */
824 exprset = VEC_index (bitmap_set_t, value_expressions, lookfor);
825 FOR_EACH_EXPR_ID_IN_SET (exprset, i, bi)
827 if (bitmap_bit_p (set->expressions, i))
829 bitmap_clear_bit (set->expressions, i);
830 bitmap_set_bit (set->expressions, get_expression_id (expr));
836 /* Return true if two bitmap sets are equal. */
839 bitmap_set_equal (bitmap_set_t a, bitmap_set_t b)
841 return bitmap_equal_p (a->values, b->values);
844 /* Replace an instance of EXPR's VALUE with EXPR in SET if it exists,
845 and add it otherwise. */
848 bitmap_value_replace_in_set (bitmap_set_t set, pre_expr expr)
850 unsigned int val = get_expr_value_id (expr);
852 if (bitmap_set_contains_value (set, val))
853 bitmap_set_replace_value (set, val, expr);
855 bitmap_insert_into_set (set, expr);
858 /* Insert EXPR into SET if EXPR's value is not already present in
862 bitmap_value_insert_into_set (bitmap_set_t set, pre_expr expr)
864 unsigned int val = get_expr_value_id (expr);
866 if (value_id_constant_p (val))
869 if (!bitmap_set_contains_value (set, val))
870 bitmap_insert_into_set (set, expr);
873 /* Print out EXPR to outfile. */
876 print_pre_expr (FILE *outfile, const pre_expr expr)
881 print_generic_expr (outfile, PRE_EXPR_CONSTANT (expr), 0);
884 print_generic_expr (outfile, PRE_EXPR_NAME (expr), 0);
889 vn_nary_op_t nary = PRE_EXPR_NARY (expr);
890 fprintf (outfile, "{%s,", tree_code_name [nary->opcode]);
891 for (i = 0; i < nary->length; i++)
893 print_generic_expr (outfile, nary->op[i], 0);
894 if (i != (unsigned) nary->length - 1)
895 fprintf (outfile, ",");
897 fprintf (outfile, "}");
903 vn_reference_op_t vro;
905 vn_reference_t ref = PRE_EXPR_REFERENCE (expr);
906 fprintf (outfile, "{");
908 VEC_iterate (vn_reference_op_s, ref->operands, i, vro);
911 bool closebrace = false;
912 if (vro->opcode != SSA_NAME
913 && TREE_CODE_CLASS (vro->opcode) != tcc_declaration)
915 fprintf (outfile, "%s", tree_code_name [vro->opcode]);
918 fprintf (outfile, "<");
924 print_generic_expr (outfile, vro->op0, 0);
927 fprintf (outfile, ",");
928 print_generic_expr (outfile, vro->op1, 0);
932 fprintf (outfile, ",");
933 print_generic_expr (outfile, vro->op2, 0);
937 fprintf (outfile, ">");
938 if (i != VEC_length (vn_reference_op_s, ref->operands) - 1)
939 fprintf (outfile, ",");
941 fprintf (outfile, "}");
944 fprintf (outfile, "@");
945 print_generic_expr (outfile, ref->vuse, 0);
951 void debug_pre_expr (pre_expr);
953 /* Like print_pre_expr but always prints to stderr. */
955 debug_pre_expr (pre_expr e)
957 print_pre_expr (stderr, e);
958 fprintf (stderr, "\n");
961 /* Print out SET to OUTFILE. */
964 print_bitmap_set (FILE *outfile, bitmap_set_t set,
965 const char *setname, int blockindex)
967 fprintf (outfile, "%s[%d] := { ", setname, blockindex);
974 FOR_EACH_EXPR_ID_IN_SET (set, i, bi)
976 const pre_expr expr = expression_for_id (i);
979 fprintf (outfile, ", ");
981 print_pre_expr (outfile, expr);
983 fprintf (outfile, " (%04d)", get_expr_value_id (expr));
986 fprintf (outfile, " }\n");
989 void debug_bitmap_set (bitmap_set_t);
992 debug_bitmap_set (bitmap_set_t set)
994 print_bitmap_set (stderr, set, "debug", 0);
997 /* Print out the expressions that have VAL to OUTFILE. */
1000 print_value_expressions (FILE *outfile, unsigned int val)
1002 bitmap_set_t set = VEC_index (bitmap_set_t, value_expressions, val);
1006 sprintf (s, "%04d", val);
1007 print_bitmap_set (outfile, set, s, 0);
1013 debug_value_expressions (unsigned int val)
1015 print_value_expressions (stderr, val);
1018 /* Given a CONSTANT, allocate a new CONSTANT type PRE_EXPR to
1022 get_or_alloc_expr_for_constant (tree constant)
1024 unsigned int result_id;
1025 unsigned int value_id;
1026 pre_expr newexpr = (pre_expr) pool_alloc (pre_expr_pool);
1027 newexpr->kind = CONSTANT;
1028 PRE_EXPR_CONSTANT (newexpr) = constant;
1029 result_id = lookup_expression_id (newexpr);
1032 pool_free (pre_expr_pool, newexpr);
1033 newexpr = expression_for_id (result_id);
1036 value_id = get_or_alloc_constant_value_id (constant);
1037 get_or_alloc_expression_id (newexpr);
1038 add_to_value (value_id, newexpr);
1042 /* Given a value id V, find the actual tree representing the constant
1043 value if there is one, and return it. Return NULL if we can't find
1047 get_constant_for_value_id (unsigned int v)
1049 if (value_id_constant_p (v))
1053 bitmap_set_t exprset = VEC_index (bitmap_set_t, value_expressions, v);
1055 FOR_EACH_EXPR_ID_IN_SET (exprset, i, bi)
1057 pre_expr expr = expression_for_id (i);
1058 if (expr->kind == CONSTANT)
1059 return PRE_EXPR_CONSTANT (expr);
1065 /* Get or allocate a pre_expr for a piece of GIMPLE, and return it.
1066 Currently only supports constants and SSA_NAMES. */
1068 get_or_alloc_expr_for (tree t)
1070 if (TREE_CODE (t) == SSA_NAME)
1071 return get_or_alloc_expr_for_name (t);
1072 else if (is_gimple_min_invariant (t))
1073 return get_or_alloc_expr_for_constant (t);
1076 /* More complex expressions can result from SCCVN expression
1077 simplification that inserts values for them. As they all
1078 do not have VOPs the get handled by the nary ops struct. */
1079 vn_nary_op_t result;
1080 unsigned int result_id;
1081 vn_nary_op_lookup (t, &result);
1084 pre_expr e = (pre_expr) pool_alloc (pre_expr_pool);
1086 PRE_EXPR_NARY (e) = result;
1087 result_id = lookup_expression_id (e);
1090 pool_free (pre_expr_pool, e);
1091 e = expression_for_id (result_id);
1094 alloc_expression_id (e);
1101 /* Return the folded version of T if T, when folded, is a gimple
1102 min_invariant. Otherwise, return T. */
1105 fully_constant_expression (pre_expr e)
1113 vn_nary_op_t nary = PRE_EXPR_NARY (e);
1114 switch (TREE_CODE_CLASS (nary->opcode))
1116 case tcc_expression:
1117 if (nary->opcode == TRUTH_NOT_EXPR)
1119 if (nary->opcode != TRUTH_AND_EXPR
1120 && nary->opcode != TRUTH_OR_EXPR
1121 && nary->opcode != TRUTH_XOR_EXPR)
1125 case tcc_comparison:
1127 /* We have to go from trees to pre exprs to value ids to
1129 tree naryop0 = nary->op[0];
1130 tree naryop1 = nary->op[1];
1132 if (!is_gimple_min_invariant (naryop0))
1134 pre_expr rep0 = get_or_alloc_expr_for (naryop0);
1135 unsigned int vrep0 = get_expr_value_id (rep0);
1136 tree const0 = get_constant_for_value_id (vrep0);
1138 naryop0 = fold_convert (TREE_TYPE (naryop0), const0);
1140 if (!is_gimple_min_invariant (naryop1))
1142 pre_expr rep1 = get_or_alloc_expr_for (naryop1);
1143 unsigned int vrep1 = get_expr_value_id (rep1);
1144 tree const1 = get_constant_for_value_id (vrep1);
1146 naryop1 = fold_convert (TREE_TYPE (naryop1), const1);
1148 result = fold_binary (nary->opcode, nary->type,
1150 if (result && is_gimple_min_invariant (result))
1151 return get_or_alloc_expr_for_constant (result);
1152 /* We might have simplified the expression to a
1153 SSA_NAME for example from x_1 * 1. But we cannot
1154 insert a PHI for x_1 unconditionally as x_1 might
1155 not be available readily. */
1159 if (nary->opcode != REALPART_EXPR
1160 && nary->opcode != IMAGPART_EXPR
1161 && nary->opcode != VIEW_CONVERT_EXPR)
1167 /* We have to go from trees to pre exprs to value ids to
1169 tree naryop0 = nary->op[0];
1170 tree const0, result;
1171 if (is_gimple_min_invariant (naryop0))
1175 pre_expr rep0 = get_or_alloc_expr_for (naryop0);
1176 unsigned int vrep0 = get_expr_value_id (rep0);
1177 const0 = get_constant_for_value_id (vrep0);
1182 tree type1 = TREE_TYPE (nary->op[0]);
1183 const0 = fold_convert (type1, const0);
1184 result = fold_unary (nary->opcode, nary->type, const0);
1186 if (result && is_gimple_min_invariant (result))
1187 return get_or_alloc_expr_for_constant (result);
1196 vn_reference_t ref = PRE_EXPR_REFERENCE (e);
1197 VEC (vn_reference_op_s, heap) *operands = ref->operands;
1198 vn_reference_op_t op;
1200 /* Try to simplify the translated expression if it is
1201 a call to a builtin function with at most two arguments. */
1202 op = VEC_index (vn_reference_op_s, operands, 0);
1203 if (op->opcode == CALL_EXPR
1204 && TREE_CODE (op->op0) == ADDR_EXPR
1205 && TREE_CODE (TREE_OPERAND (op->op0, 0)) == FUNCTION_DECL
1206 && DECL_BUILT_IN (TREE_OPERAND (op->op0, 0))
1207 && VEC_length (vn_reference_op_s, operands) >= 2
1208 && VEC_length (vn_reference_op_s, operands) <= 3)
1210 vn_reference_op_t arg0, arg1 = NULL;
1211 bool anyconst = false;
1212 arg0 = VEC_index (vn_reference_op_s, operands, 1);
1213 if (VEC_length (vn_reference_op_s, operands) > 2)
1214 arg1 = VEC_index (vn_reference_op_s, operands, 2);
1215 if (TREE_CODE_CLASS (arg0->opcode) == tcc_constant
1216 || (arg0->opcode == ADDR_EXPR
1217 && is_gimple_min_invariant (arg0->op0)))
1220 && (TREE_CODE_CLASS (arg1->opcode) == tcc_constant
1221 || (arg1->opcode == ADDR_EXPR
1222 && is_gimple_min_invariant (arg1->op0))))
1226 tree folded = build_call_expr (TREE_OPERAND (op->op0, 0),
1229 arg1 ? arg1->op0 : NULL);
1231 && TREE_CODE (folded) == NOP_EXPR)
1232 folded = TREE_OPERAND (folded, 0);
1234 && is_gimple_min_invariant (folded))
1235 return get_or_alloc_expr_for_constant (folded);
1246 /* Translate the VUSE backwards through phi nodes in PHIBLOCK, so that
1247 it has the value it would have in BLOCK. Set *SAME_VALID to true
1248 in case the new vuse doesn't change the value id of the OPERANDS. */
1251 translate_vuse_through_block (VEC (vn_reference_op_s, heap) *operands,
1252 alias_set_type set, tree type, tree vuse,
1253 basic_block phiblock,
1254 basic_block block, bool *same_valid)
1256 gimple phi = SSA_NAME_DEF_STMT (vuse);
1263 if (gimple_bb (phi) != phiblock)
1266 use_oracle = ao_ref_init_from_vn_reference (&ref, set, type, operands);
1268 /* Use the alias-oracle to find either the PHI node in this block,
1269 the first VUSE used in this block that is equivalent to vuse or
1270 the first VUSE which definition in this block kills the value. */
1271 if (gimple_code (phi) == GIMPLE_PHI)
1272 e = find_edge (block, phiblock);
1273 else if (use_oracle)
1274 while (!stmt_may_clobber_ref_p_1 (phi, &ref))
1276 vuse = gimple_vuse (phi);
1277 phi = SSA_NAME_DEF_STMT (vuse);
1278 if (gimple_bb (phi) != phiblock)
1280 if (gimple_code (phi) == GIMPLE_PHI)
1282 e = find_edge (block, phiblock);
1293 bitmap visited = NULL;
1294 /* Try to find a vuse that dominates this phi node by skipping
1295 non-clobbering statements. */
1296 vuse = get_continuation_for_phi (phi, &ref, &visited);
1298 BITMAP_FREE (visited);
1304 /* If we didn't find any, the value ID can't stay the same,
1305 but return the translated vuse. */
1306 *same_valid = false;
1307 vuse = PHI_ARG_DEF (phi, e->dest_idx);
1309 /* ??? We would like to return vuse here as this is the canonical
1310 upmost vdef that this reference is associated with. But during
1311 insertion of the references into the hash tables we only ever
1312 directly insert with their direct gimple_vuse, hence returning
1313 something else would make us not find the other expression. */
1314 return PHI_ARG_DEF (phi, e->dest_idx);
1320 /* Like bitmap_find_leader, but checks for the value existing in SET1 *or*
1321 SET2. This is used to avoid making a set consisting of the union
1322 of PA_IN and ANTIC_IN during insert. */
1324 static inline pre_expr
1325 find_leader_in_sets (unsigned int val, bitmap_set_t set1, bitmap_set_t set2)
1329 result = bitmap_find_leader (set1, val, NULL);
1330 if (!result && set2)
1331 result = bitmap_find_leader (set2, val, NULL);
1335 /* Get the tree type for our PRE expression e. */
1338 get_expr_type (const pre_expr e)
1343 return TREE_TYPE (PRE_EXPR_NAME (e));
1345 return TREE_TYPE (PRE_EXPR_CONSTANT (e));
1347 return PRE_EXPR_REFERENCE (e)->type;
1349 return PRE_EXPR_NARY (e)->type;
1354 /* Get a representative SSA_NAME for a given expression.
1355 Since all of our sub-expressions are treated as values, we require
1356 them to be SSA_NAME's for simplicity.
1357 Prior versions of GVNPRE used to use "value handles" here, so that
1358 an expression would be VH.11 + VH.10 instead of d_3 + e_6. In
1359 either case, the operands are really values (IE we do not expect
1360 them to be usable without finding leaders). */
1363 get_representative_for (const pre_expr e)
1367 unsigned int value_id = get_expr_value_id (e);
1372 return PRE_EXPR_NAME (e);
1374 return PRE_EXPR_CONSTANT (e);
1378 /* Go through all of the expressions representing this value
1379 and pick out an SSA_NAME. */
1382 bitmap_set_t exprs = VEC_index (bitmap_set_t, value_expressions,
1384 FOR_EACH_EXPR_ID_IN_SET (exprs, i, bi)
1386 pre_expr rep = expression_for_id (i);
1387 if (rep->kind == NAME)
1388 return PRE_EXPR_NAME (rep);
1393 /* If we reached here we couldn't find an SSA_NAME. This can
1394 happen when we've discovered a value that has never appeared in
1395 the program as set to an SSA_NAME, most likely as the result of
1400 "Could not find SSA_NAME representative for expression:");
1401 print_pre_expr (dump_file, e);
1402 fprintf (dump_file, "\n");
1405 exprtype = get_expr_type (e);
1407 /* Build and insert the assignment of the end result to the temporary
1408 that we will return. */
1409 if (!pretemp || exprtype != TREE_TYPE (pretemp))
1411 pretemp = create_tmp_var (exprtype, "pretmp");
1412 get_var_ann (pretemp);
1415 name = make_ssa_name (pretemp, gimple_build_nop ());
1416 VN_INFO_GET (name)->value_id = value_id;
1417 if (e->kind == CONSTANT)
1418 VN_INFO (name)->valnum = PRE_EXPR_CONSTANT (e);
1420 VN_INFO (name)->valnum = name;
1422 add_to_value (value_id, get_or_alloc_expr_for_name (name));
1425 fprintf (dump_file, "Created SSA_NAME representative ");
1426 print_generic_expr (dump_file, name, 0);
1427 fprintf (dump_file, " for expression:");
1428 print_pre_expr (dump_file, e);
1429 fprintf (dump_file, "\n");
1438 /* Translate EXPR using phis in PHIBLOCK, so that it has the values of
1439 the phis in PRED. Return NULL if we can't find a leader for each part
1440 of the translated expression. */
1443 phi_translate (pre_expr expr, bitmap_set_t set1, bitmap_set_t set2,
1444 basic_block pred, basic_block phiblock)
1446 pre_expr oldexpr = expr;
1452 if (value_id_constant_p (get_expr_value_id (expr)))
1455 phitrans = phi_trans_lookup (expr, pred);
1461 /* Constants contain no values that need translation. */
1468 bool changed = false;
1469 vn_nary_op_t nary = PRE_EXPR_NARY (expr);
1470 struct vn_nary_op_s newnary;
1471 /* The NARY structure is only guaranteed to have been
1472 allocated to the nary->length operands. */
1473 memcpy (&newnary, nary, (sizeof (struct vn_nary_op_s)
1474 - sizeof (tree) * (4 - nary->length)));
1476 for (i = 0; i < newnary.length; i++)
1478 if (TREE_CODE (newnary.op[i]) != SSA_NAME)
1482 pre_expr leader, result;
1483 unsigned int op_val_id = VN_INFO (newnary.op[i])->value_id;
1484 leader = find_leader_in_sets (op_val_id, set1, set2);
1485 result = phi_translate (leader, set1, set2, pred, phiblock);
1486 if (result && result != leader)
1488 tree name = get_representative_for (result);
1491 newnary.op[i] = name;
1496 changed |= newnary.op[i] != nary->op[i];
1503 tree result = vn_nary_op_lookup_pieces (newnary.length,
1511 unsigned int new_val_id;
1513 expr = (pre_expr) pool_alloc (pre_expr_pool);
1516 if (result && is_gimple_min_invariant (result))
1517 return get_or_alloc_expr_for_constant (result);
1522 PRE_EXPR_NARY (expr) = nary;
1523 constant = fully_constant_expression (expr);
1524 if (constant != expr)
1527 new_val_id = nary->value_id;
1528 get_or_alloc_expression_id (expr);
1532 new_val_id = get_next_value_id ();
1533 VEC_safe_grow_cleared (bitmap_set_t, heap,
1535 get_max_value_id() + 1);
1536 nary = vn_nary_op_insert_pieces (newnary.length,
1543 result, new_val_id);
1544 PRE_EXPR_NARY (expr) = nary;
1545 constant = fully_constant_expression (expr);
1546 if (constant != expr)
1548 get_or_alloc_expression_id (expr);
1550 add_to_value (new_val_id, expr);
1552 phi_trans_add (oldexpr, expr, pred);
1559 vn_reference_t ref = PRE_EXPR_REFERENCE (expr);
1560 VEC (vn_reference_op_s, heap) *operands = ref->operands;
1561 tree vuse = ref->vuse;
1562 tree newvuse = vuse;
1563 VEC (vn_reference_op_s, heap) *newoperands = NULL;
1564 bool changed = false, same_valid = true;
1566 vn_reference_op_t operand;
1567 vn_reference_t newref;
1570 VEC_iterate (vn_reference_op_s, operands, i, operand); i++, j++)
1574 tree oldop0 = operand->op0;
1575 tree oldop1 = operand->op1;
1576 tree oldop2 = operand->op2;
1580 tree type = operand->type;
1581 vn_reference_op_s newop = *operand;
1583 if (op0 && TREE_CODE (op0) == SSA_NAME)
1585 unsigned int op_val_id = VN_INFO (op0)->value_id;
1586 leader = find_leader_in_sets (op_val_id, set1, set2);
1587 opresult = phi_translate (leader, set1, set2, pred, phiblock);
1588 if (opresult && opresult != leader)
1590 tree name = get_representative_for (opresult);
1598 changed |= op0 != oldop0;
1600 if (op1 && TREE_CODE (op1) == SSA_NAME)
1602 unsigned int op_val_id = VN_INFO (op1)->value_id;
1603 leader = find_leader_in_sets (op_val_id, set1, set2);
1604 opresult = phi_translate (leader, set1, set2, pred, phiblock);
1605 if (opresult && opresult != leader)
1607 tree name = get_representative_for (opresult);
1615 /* We can't possibly insert these. */
1616 else if (op1 && !is_gimple_min_invariant (op1))
1618 changed |= op1 != oldop1;
1619 if (op2 && TREE_CODE (op2) == SSA_NAME)
1621 unsigned int op_val_id = VN_INFO (op2)->value_id;
1622 leader = find_leader_in_sets (op_val_id, set1, set2);
1623 opresult = phi_translate (leader, set1, set2, pred, phiblock);
1624 if (opresult && opresult != leader)
1626 tree name = get_representative_for (opresult);
1634 /* We can't possibly insert these. */
1635 else if (op2 && !is_gimple_min_invariant (op2))
1637 changed |= op2 != oldop2;
1640 newoperands = VEC_copy (vn_reference_op_s, heap, operands);
1641 /* We may have changed from an SSA_NAME to a constant */
1642 if (newop.opcode == SSA_NAME && TREE_CODE (op0) != SSA_NAME)
1643 newop.opcode = TREE_CODE (op0);
1648 VEC_replace (vn_reference_op_s, newoperands, j, &newop);
1649 /* If it transforms from an SSA_NAME to an address, fold with
1650 a preceding indirect reference. */
1651 if (j > 0 && op0 && TREE_CODE (op0) == ADDR_EXPR
1652 && VEC_index (vn_reference_op_s,
1653 newoperands, j - 1)->opcode == INDIRECT_REF)
1654 vn_reference_fold_indirect (&newoperands, &j);
1656 if (i != VEC_length (vn_reference_op_s, operands))
1659 VEC_free (vn_reference_op_s, heap, newoperands);
1665 newvuse = translate_vuse_through_block (newoperands,
1666 ref->set, ref->type,
1667 vuse, phiblock, pred,
1669 if (newvuse == NULL_TREE)
1671 VEC_free (vn_reference_op_s, heap, newoperands);
1676 if (changed || newvuse != vuse)
1678 unsigned int new_val_id;
1681 tree result = vn_reference_lookup_pieces (newvuse, ref->set,
1686 VEC_free (vn_reference_op_s, heap, newoperands);
1688 if (result && is_gimple_min_invariant (result))
1690 gcc_assert (!newoperands);
1691 return get_or_alloc_expr_for_constant (result);
1694 expr = (pre_expr) pool_alloc (pre_expr_pool);
1695 expr->kind = REFERENCE;
1700 PRE_EXPR_REFERENCE (expr) = newref;
1701 constant = fully_constant_expression (expr);
1702 if (constant != expr)
1705 new_val_id = newref->value_id;
1706 get_or_alloc_expression_id (expr);
1710 if (changed || !same_valid)
1712 new_val_id = get_next_value_id ();
1713 VEC_safe_grow_cleared (bitmap_set_t, heap,
1715 get_max_value_id() + 1);
1718 new_val_id = ref->value_id;
1719 newref = vn_reference_insert_pieces (newvuse, ref->set,
1722 result, new_val_id);
1724 PRE_EXPR_REFERENCE (expr) = newref;
1725 constant = fully_constant_expression (expr);
1726 if (constant != expr)
1728 get_or_alloc_expression_id (expr);
1730 add_to_value (new_val_id, expr);
1732 VEC_free (vn_reference_op_s, heap, newoperands);
1733 phi_trans_add (oldexpr, expr, pred);
1743 tree name = PRE_EXPR_NAME (expr);
1745 def_stmt = SSA_NAME_DEF_STMT (name);
1746 if (gimple_code (def_stmt) == GIMPLE_PHI
1747 && gimple_bb (def_stmt) == phiblock)
1752 e = find_edge (pred, gimple_bb (phi));
1755 tree def = PHI_ARG_DEF (phi, e->dest_idx);
1758 if (TREE_CODE (def) == SSA_NAME)
1759 def = VN_INFO (def)->valnum;
1761 /* Handle constant. */
1762 if (is_gimple_min_invariant (def))
1763 return get_or_alloc_expr_for_constant (def);
1765 if (TREE_CODE (def) == SSA_NAME && ssa_undefined_value_p (def))
1768 newexpr = get_or_alloc_expr_for_name (def);
1779 /* For each expression in SET, translate the values through phi nodes
1780 in PHIBLOCK using edge PHIBLOCK->PRED, and store the resulting
1781 expressions in DEST. */
1784 phi_translate_set (bitmap_set_t dest, bitmap_set_t set, basic_block pred,
1785 basic_block phiblock)
1787 VEC (pre_expr, heap) *exprs;
1791 if (!phi_nodes (phiblock))
1793 bitmap_set_copy (dest, set);
1797 exprs = sorted_array_from_bitmap_set (set);
1798 for (i = 0; VEC_iterate (pre_expr, exprs, i, expr); i++)
1800 pre_expr translated;
1801 translated = phi_translate (expr, set, NULL, pred, phiblock);
1803 /* Don't add empty translations to the cache */
1805 phi_trans_add (expr, translated, pred);
1807 if (translated != NULL)
1808 bitmap_value_insert_into_set (dest, translated);
1810 VEC_free (pre_expr, heap, exprs);
1813 /* Find the leader for a value (i.e., the name representing that
1814 value) in a given set, and return it. If STMT is non-NULL it
1815 makes sure the defining statement for the leader dominates it.
1816 Return NULL if no leader is found. */
1819 bitmap_find_leader (bitmap_set_t set, unsigned int val, gimple stmt)
1821 if (value_id_constant_p (val))
1825 bitmap_set_t exprset = VEC_index (bitmap_set_t, value_expressions, val);
1827 FOR_EACH_EXPR_ID_IN_SET (exprset, i, bi)
1829 pre_expr expr = expression_for_id (i);
1830 if (expr->kind == CONSTANT)
1834 if (bitmap_set_contains_value (set, val))
1836 /* Rather than walk the entire bitmap of expressions, and see
1837 whether any of them has the value we are looking for, we look
1838 at the reverse mapping, which tells us the set of expressions
1839 that have a given value (IE value->expressions with that
1840 value) and see if any of those expressions are in our set.
1841 The number of expressions per value is usually significantly
1842 less than the number of expressions in the set. In fact, for
1843 large testcases, doing it this way is roughly 5-10x faster
1844 than walking the bitmap.
1845 If this is somehow a significant lose for some cases, we can
1846 choose which set to walk based on which set is smaller. */
1849 bitmap_set_t exprset = VEC_index (bitmap_set_t, value_expressions, val);
1851 EXECUTE_IF_AND_IN_BITMAP (exprset->expressions,
1852 set->expressions, 0, i, bi)
1854 pre_expr val = expression_for_id (i);
1855 /* At the point where stmt is not null, there should always
1856 be an SSA_NAME first in the list of expressions. */
1859 gimple def_stmt = SSA_NAME_DEF_STMT (PRE_EXPR_NAME (val));
1860 if (gimple_code (def_stmt) != GIMPLE_PHI
1861 && gimple_bb (def_stmt) == gimple_bb (stmt)
1862 && gimple_uid (def_stmt) >= gimple_uid (stmt))
1871 /* Determine if EXPR, a memory expression, is ANTIC_IN at the top of
1872 BLOCK by seeing if it is not killed in the block. Note that we are
1873 only determining whether there is a store that kills it. Because
1874 of the order in which clean iterates over values, we are guaranteed
1875 that altered operands will have caused us to be eliminated from the
1876 ANTIC_IN set already. */
1879 value_dies_in_block_x (pre_expr expr, basic_block block)
1881 tree vuse = PRE_EXPR_REFERENCE (expr)->vuse;
1882 vn_reference_t refx = PRE_EXPR_REFERENCE (expr);
1884 gimple_stmt_iterator gsi;
1885 unsigned id = get_expression_id (expr);
1892 /* Lookup a previously calculated result. */
1893 if (EXPR_DIES (block)
1894 && bitmap_bit_p (EXPR_DIES (block), id * 2))
1895 return bitmap_bit_p (EXPR_DIES (block), id * 2 + 1);
1897 /* A memory expression {e, VUSE} dies in the block if there is a
1898 statement that may clobber e. If, starting statement walk from the
1899 top of the basic block, a statement uses VUSE there can be no kill
1900 inbetween that use and the original statement that loaded {e, VUSE},
1901 so we can stop walking. */
1902 ref.base = NULL_TREE;
1903 for (gsi = gsi_start_bb (block); !gsi_end_p (gsi); gsi_next (&gsi))
1905 tree def_vuse, def_vdef;
1906 def = gsi_stmt (gsi);
1907 def_vuse = gimple_vuse (def);
1908 def_vdef = gimple_vdef (def);
1910 /* Not a memory statement. */
1914 /* Not a may-def. */
1917 /* A load with the same VUSE, we're done. */
1918 if (def_vuse == vuse)
1924 /* Init ref only if we really need it. */
1925 if (ref.base == NULL_TREE
1926 && !ao_ref_init_from_vn_reference (&ref, refx->set, refx->type,
1932 /* If the statement may clobber expr, it dies. */
1933 if (stmt_may_clobber_ref_p_1 (def, &ref))
1940 /* Remember the result. */
1941 if (!EXPR_DIES (block))
1942 EXPR_DIES (block) = BITMAP_ALLOC (&grand_bitmap_obstack);
1943 bitmap_set_bit (EXPR_DIES (block), id * 2);
1945 bitmap_set_bit (EXPR_DIES (block), id * 2 + 1);
1951 #define union_contains_value(SET1, SET2, VAL) \
1952 (bitmap_set_contains_value ((SET1), (VAL)) \
1953 || ((SET2) && bitmap_set_contains_value ((SET2), (VAL))))
1955 /* Determine if vn_reference_op_t VRO is legal in SET1 U SET2.
1958 vro_valid_in_sets (bitmap_set_t set1, bitmap_set_t set2,
1959 vn_reference_op_t vro)
1961 if (vro->op0 && TREE_CODE (vro->op0) == SSA_NAME)
1963 struct pre_expr_d temp;
1966 PRE_EXPR_NAME (&temp) = vro->op0;
1967 temp.id = lookup_expression_id (&temp);
1970 if (!union_contains_value (set1, set2,
1971 get_expr_value_id (&temp)))
1974 if (vro->op1 && TREE_CODE (vro->op1) == SSA_NAME)
1976 struct pre_expr_d temp;
1979 PRE_EXPR_NAME (&temp) = vro->op1;
1980 temp.id = lookup_expression_id (&temp);
1983 if (!union_contains_value (set1, set2,
1984 get_expr_value_id (&temp)))
1988 if (vro->op2 && TREE_CODE (vro->op2) == SSA_NAME)
1990 struct pre_expr_d temp;
1993 PRE_EXPR_NAME (&temp) = vro->op2;
1994 temp.id = lookup_expression_id (&temp);
1997 if (!union_contains_value (set1, set2,
1998 get_expr_value_id (&temp)))
2005 /* Determine if the expression EXPR is valid in SET1 U SET2.
2006 ONLY SET2 CAN BE NULL.
2007 This means that we have a leader for each part of the expression
2008 (if it consists of values), or the expression is an SSA_NAME.
2009 For loads/calls, we also see if the vuse is killed in this block. */
2012 valid_in_sets (bitmap_set_t set1, bitmap_set_t set2, pre_expr expr,
2018 return bitmap_set_contains_expr (AVAIL_OUT (block), expr);
2022 vn_nary_op_t nary = PRE_EXPR_NARY (expr);
2023 for (i = 0; i < nary->length; i++)
2025 if (TREE_CODE (nary->op[i]) == SSA_NAME)
2027 struct pre_expr_d temp;
2030 PRE_EXPR_NAME (&temp) = nary->op[i];
2031 temp.id = lookup_expression_id (&temp);
2034 if (!union_contains_value (set1, set2,
2035 get_expr_value_id (&temp)))
2039 /* If the NARY may trap make sure the block does not contain
2040 a possible exit point.
2041 ??? This is overly conservative if we translate AVAIL_OUT
2042 as the available expression might be after the exit point. */
2043 if (BB_MAY_NOTRETURN (block)
2044 && vn_nary_may_trap (nary))
2051 vn_reference_t ref = PRE_EXPR_REFERENCE (expr);
2052 vn_reference_op_t vro;
2055 for (i = 0; VEC_iterate (vn_reference_op_s, ref->operands, i, vro); i++)
2057 if (!vro_valid_in_sets (set1, set2, vro))
2062 gimple def_stmt = SSA_NAME_DEF_STMT (ref->vuse);
2063 if (!gimple_nop_p (def_stmt)
2064 && gimple_bb (def_stmt) != block
2065 && !dominated_by_p (CDI_DOMINATORS,
2066 block, gimple_bb (def_stmt)))
2069 return !value_dies_in_block_x (expr, block);
2076 /* Clean the set of expressions that are no longer valid in SET1 or
2077 SET2. This means expressions that are made up of values we have no
2078 leaders for in SET1 or SET2. This version is used for partial
2079 anticipation, which means it is not valid in either ANTIC_IN or
2083 dependent_clean (bitmap_set_t set1, bitmap_set_t set2, basic_block block)
2085 VEC (pre_expr, heap) *exprs = sorted_array_from_bitmap_set (set1);
2089 for (i = 0; VEC_iterate (pre_expr, exprs, i, expr); i++)
2091 if (!valid_in_sets (set1, set2, expr, block))
2092 bitmap_remove_from_set (set1, expr);
2094 VEC_free (pre_expr, heap, exprs);
2097 /* Clean the set of expressions that are no longer valid in SET. This
2098 means expressions that are made up of values we have no leaders for
2102 clean (bitmap_set_t set, basic_block block)
2104 VEC (pre_expr, heap) *exprs = sorted_array_from_bitmap_set (set);
2108 for (i = 0; VEC_iterate (pre_expr, exprs, i, expr); i++)
2110 if (!valid_in_sets (set, NULL, expr, block))
2111 bitmap_remove_from_set (set, expr);
2113 VEC_free (pre_expr, heap, exprs);
2116 static sbitmap has_abnormal_preds;
2118 /* List of blocks that may have changed during ANTIC computation and
2119 thus need to be iterated over. */
2121 static sbitmap changed_blocks;
2123 /* Decide whether to defer a block for a later iteration, or PHI
2124 translate SOURCE to DEST using phis in PHIBLOCK. Return false if we
2125 should defer the block, and true if we processed it. */
2128 defer_or_phi_translate_block (bitmap_set_t dest, bitmap_set_t source,
2129 basic_block block, basic_block phiblock)
2131 if (!BB_VISITED (phiblock))
2133 SET_BIT (changed_blocks, block->index);
2134 BB_VISITED (block) = 0;
2135 BB_DEFERRED (block) = 1;
2139 phi_translate_set (dest, source, block, phiblock);
2143 /* Compute the ANTIC set for BLOCK.
2145 If succs(BLOCK) > 1 then
2146 ANTIC_OUT[BLOCK] = intersection of ANTIC_IN[b] for all succ(BLOCK)
2147 else if succs(BLOCK) == 1 then
2148 ANTIC_OUT[BLOCK] = phi_translate (ANTIC_IN[succ(BLOCK)])
2150 ANTIC_IN[BLOCK] = clean(ANTIC_OUT[BLOCK] U EXP_GEN[BLOCK] - TMP_GEN[BLOCK])
2154 compute_antic_aux (basic_block block, bool block_has_abnormal_pred_edge)
2156 bool changed = false;
2157 bitmap_set_t S, old, ANTIC_OUT;
2163 old = ANTIC_OUT = S = NULL;
2164 BB_VISITED (block) = 1;
2166 /* If any edges from predecessors are abnormal, antic_in is empty,
2168 if (block_has_abnormal_pred_edge)
2169 goto maybe_dump_sets;
2171 old = ANTIC_IN (block);
2172 ANTIC_OUT = bitmap_set_new ();
2174 /* If the block has no successors, ANTIC_OUT is empty. */
2175 if (EDGE_COUNT (block->succs) == 0)
2177 /* If we have one successor, we could have some phi nodes to
2178 translate through. */
2179 else if (single_succ_p (block))
2181 basic_block succ_bb = single_succ (block);
2183 /* We trade iterations of the dataflow equations for having to
2184 phi translate the maximal set, which is incredibly slow
2185 (since the maximal set often has 300+ members, even when you
2186 have a small number of blocks).
2187 Basically, we defer the computation of ANTIC for this block
2188 until we have processed it's successor, which will inevitably
2189 have a *much* smaller set of values to phi translate once
2190 clean has been run on it.
2191 The cost of doing this is that we technically perform more
2192 iterations, however, they are lower cost iterations.
2194 Timings for PRE on tramp3d-v4:
2195 without maximal set fix: 11 seconds
2196 with maximal set fix/without deferring: 26 seconds
2197 with maximal set fix/with deferring: 11 seconds
2200 if (!defer_or_phi_translate_block (ANTIC_OUT, ANTIC_IN (succ_bb),
2204 goto maybe_dump_sets;
2207 /* If we have multiple successors, we take the intersection of all of
2208 them. Note that in the case of loop exit phi nodes, we may have
2209 phis to translate through. */
2212 VEC(basic_block, heap) * worklist;
2214 basic_block bprime, first = NULL;
2216 worklist = VEC_alloc (basic_block, heap, EDGE_COUNT (block->succs));
2217 FOR_EACH_EDGE (e, ei, block->succs)
2220 && BB_VISITED (e->dest))
2222 else if (BB_VISITED (e->dest))
2223 VEC_quick_push (basic_block, worklist, e->dest);
2226 /* Of multiple successors we have to have visited one already. */
2229 SET_BIT (changed_blocks, block->index);
2230 BB_VISITED (block) = 0;
2231 BB_DEFERRED (block) = 1;
2233 VEC_free (basic_block, heap, worklist);
2234 goto maybe_dump_sets;
2237 if (phi_nodes (first))
2238 phi_translate_set (ANTIC_OUT, ANTIC_IN (first), block, first);
2240 bitmap_set_copy (ANTIC_OUT, ANTIC_IN (first));
2242 for (i = 0; VEC_iterate (basic_block, worklist, i, bprime); i++)
2244 if (phi_nodes (bprime))
2246 bitmap_set_t tmp = bitmap_set_new ();
2247 phi_translate_set (tmp, ANTIC_IN (bprime), block, bprime);
2248 bitmap_set_and (ANTIC_OUT, tmp);
2249 bitmap_set_free (tmp);
2252 bitmap_set_and (ANTIC_OUT, ANTIC_IN (bprime));
2254 VEC_free (basic_block, heap, worklist);
2257 /* Generate ANTIC_OUT - TMP_GEN. */
2258 S = bitmap_set_subtract (ANTIC_OUT, TMP_GEN (block));
2260 /* Start ANTIC_IN with EXP_GEN - TMP_GEN. */
2261 ANTIC_IN (block) = bitmap_set_subtract (EXP_GEN (block),
2264 /* Then union in the ANTIC_OUT - TMP_GEN values,
2265 to get ANTIC_OUT U EXP_GEN - TMP_GEN */
2266 FOR_EACH_EXPR_ID_IN_SET (S, bii, bi)
2267 bitmap_value_insert_into_set (ANTIC_IN (block),
2268 expression_for_id (bii));
2270 clean (ANTIC_IN (block), block);
2272 /* !old->expressions can happen when we deferred a block. */
2273 if (!old->expressions || !bitmap_set_equal (old, ANTIC_IN (block)))
2276 SET_BIT (changed_blocks, block->index);
2277 FOR_EACH_EDGE (e, ei, block->preds)
2278 SET_BIT (changed_blocks, e->src->index);
2281 RESET_BIT (changed_blocks, block->index);
2284 if (dump_file && (dump_flags & TDF_DETAILS))
2286 if (!BB_DEFERRED (block) || BB_VISITED (block))
2289 print_bitmap_set (dump_file, ANTIC_OUT, "ANTIC_OUT", block->index);
2291 print_bitmap_set (dump_file, ANTIC_IN (block), "ANTIC_IN",
2295 print_bitmap_set (dump_file, S, "S", block->index);
2300 "Block %d was deferred for a future iteration.\n",
2305 bitmap_set_free (old);
2307 bitmap_set_free (S);
2309 bitmap_set_free (ANTIC_OUT);
2313 /* Compute PARTIAL_ANTIC for BLOCK.
2315 If succs(BLOCK) > 1 then
2316 PA_OUT[BLOCK] = value wise union of PA_IN[b] + all ANTIC_IN not
2317 in ANTIC_OUT for all succ(BLOCK)
2318 else if succs(BLOCK) == 1 then
2319 PA_OUT[BLOCK] = phi_translate (PA_IN[succ(BLOCK)])
2321 PA_IN[BLOCK] = dependent_clean(PA_OUT[BLOCK] - TMP_GEN[BLOCK]
2326 compute_partial_antic_aux (basic_block block,
2327 bool block_has_abnormal_pred_edge)
2329 bool changed = false;
2330 bitmap_set_t old_PA_IN;
2331 bitmap_set_t PA_OUT;
2334 unsigned long max_pa = PARAM_VALUE (PARAM_MAX_PARTIAL_ANTIC_LENGTH);
2336 old_PA_IN = PA_OUT = NULL;
2338 /* If any edges from predecessors are abnormal, antic_in is empty,
2340 if (block_has_abnormal_pred_edge)
2341 goto maybe_dump_sets;
2343 /* If there are too many partially anticipatable values in the
2344 block, phi_translate_set can take an exponential time: stop
2345 before the translation starts. */
2347 && single_succ_p (block)
2348 && bitmap_count_bits (PA_IN (single_succ (block))->values) > max_pa)
2349 goto maybe_dump_sets;
2351 old_PA_IN = PA_IN (block);
2352 PA_OUT = bitmap_set_new ();
2354 /* If the block has no successors, ANTIC_OUT is empty. */
2355 if (EDGE_COUNT (block->succs) == 0)
2357 /* If we have one successor, we could have some phi nodes to
2358 translate through. Note that we can't phi translate across DFS
2359 back edges in partial antic, because it uses a union operation on
2360 the successors. For recurrences like IV's, we will end up
2361 generating a new value in the set on each go around (i + 3 (VH.1)
2362 VH.1 + 1 (VH.2), VH.2 + 1 (VH.3), etc), forever. */
2363 else if (single_succ_p (block))
2365 basic_block succ = single_succ (block);
2366 if (!(single_succ_edge (block)->flags & EDGE_DFS_BACK))
2367 phi_translate_set (PA_OUT, PA_IN (succ), block, succ);
2369 /* If we have multiple successors, we take the union of all of
2373 VEC(basic_block, heap) * worklist;
2377 worklist = VEC_alloc (basic_block, heap, EDGE_COUNT (block->succs));
2378 FOR_EACH_EDGE (e, ei, block->succs)
2380 if (e->flags & EDGE_DFS_BACK)
2382 VEC_quick_push (basic_block, worklist, e->dest);
2384 if (VEC_length (basic_block, worklist) > 0)
2386 for (i = 0; VEC_iterate (basic_block, worklist, i, bprime); i++)
2391 FOR_EACH_EXPR_ID_IN_SET (ANTIC_IN (bprime), i, bi)
2392 bitmap_value_insert_into_set (PA_OUT,
2393 expression_for_id (i));
2394 if (phi_nodes (bprime))
2396 bitmap_set_t pa_in = bitmap_set_new ();
2397 phi_translate_set (pa_in, PA_IN (bprime), block, bprime);
2398 FOR_EACH_EXPR_ID_IN_SET (pa_in, i, bi)
2399 bitmap_value_insert_into_set (PA_OUT,
2400 expression_for_id (i));
2401 bitmap_set_free (pa_in);
2404 FOR_EACH_EXPR_ID_IN_SET (PA_IN (bprime), i, bi)
2405 bitmap_value_insert_into_set (PA_OUT,
2406 expression_for_id (i));
2409 VEC_free (basic_block, heap, worklist);
2412 /* PA_IN starts with PA_OUT - TMP_GEN.
2413 Then we subtract things from ANTIC_IN. */
2414 PA_IN (block) = bitmap_set_subtract (PA_OUT, TMP_GEN (block));
2416 /* For partial antic, we want to put back in the phi results, since
2417 we will properly avoid making them partially antic over backedges. */
2418 bitmap_ior_into (PA_IN (block)->values, PHI_GEN (block)->values);
2419 bitmap_ior_into (PA_IN (block)->expressions, PHI_GEN (block)->expressions);
2421 /* PA_IN[block] = PA_IN[block] - ANTIC_IN[block] */
2422 bitmap_set_subtract_values (PA_IN (block), ANTIC_IN (block));
2424 dependent_clean (PA_IN (block), ANTIC_IN (block), block);
2426 if (!bitmap_set_equal (old_PA_IN, PA_IN (block)))
2429 SET_BIT (changed_blocks, block->index);
2430 FOR_EACH_EDGE (e, ei, block->preds)
2431 SET_BIT (changed_blocks, e->src->index);
2434 RESET_BIT (changed_blocks, block->index);
2437 if (dump_file && (dump_flags & TDF_DETAILS))
2440 print_bitmap_set (dump_file, PA_OUT, "PA_OUT", block->index);
2442 print_bitmap_set (dump_file, PA_IN (block), "PA_IN", block->index);
2445 bitmap_set_free (old_PA_IN);
2447 bitmap_set_free (PA_OUT);
2451 /* Compute ANTIC and partial ANTIC sets. */
2454 compute_antic (void)
2456 bool changed = true;
2457 int num_iterations = 0;
2461 /* If any predecessor edges are abnormal, we punt, so antic_in is empty.
2462 We pre-build the map of blocks with incoming abnormal edges here. */
2463 has_abnormal_preds = sbitmap_alloc (last_basic_block);
2464 sbitmap_zero (has_abnormal_preds);
2471 FOR_EACH_EDGE (e, ei, block->preds)
2473 e->flags &= ~EDGE_DFS_BACK;
2474 if (e->flags & EDGE_ABNORMAL)
2476 SET_BIT (has_abnormal_preds, block->index);
2481 BB_VISITED (block) = 0;
2482 BB_DEFERRED (block) = 0;
2484 /* While we are here, give empty ANTIC_IN sets to each block. */
2485 ANTIC_IN (block) = bitmap_set_new ();
2486 PA_IN (block) = bitmap_set_new ();
2489 /* At the exit block we anticipate nothing. */
2490 ANTIC_IN (EXIT_BLOCK_PTR) = bitmap_set_new ();
2491 BB_VISITED (EXIT_BLOCK_PTR) = 1;
2492 PA_IN (EXIT_BLOCK_PTR) = bitmap_set_new ();
2494 changed_blocks = sbitmap_alloc (last_basic_block + 1);
2495 sbitmap_ones (changed_blocks);
2498 if (dump_file && (dump_flags & TDF_DETAILS))
2499 fprintf (dump_file, "Starting iteration %d\n", num_iterations);
2502 for (i = 0; i < n_basic_blocks - NUM_FIXED_BLOCKS; i++)
2504 if (TEST_BIT (changed_blocks, postorder[i]))
2506 basic_block block = BASIC_BLOCK (postorder[i]);
2507 changed |= compute_antic_aux (block,
2508 TEST_BIT (has_abnormal_preds,
2512 #ifdef ENABLE_CHECKING
2513 /* Theoretically possible, but *highly* unlikely. */
2514 gcc_assert (num_iterations < 500);
2518 statistics_histogram_event (cfun, "compute_antic iterations",
2521 if (do_partial_partial)
2523 sbitmap_ones (changed_blocks);
2524 mark_dfs_back_edges ();
2529 if (dump_file && (dump_flags & TDF_DETAILS))
2530 fprintf (dump_file, "Starting iteration %d\n", num_iterations);
2533 for (i = 0; i < n_basic_blocks - NUM_FIXED_BLOCKS; i++)
2535 if (TEST_BIT (changed_blocks, postorder[i]))
2537 basic_block block = BASIC_BLOCK (postorder[i]);
2539 |= compute_partial_antic_aux (block,
2540 TEST_BIT (has_abnormal_preds,
2544 #ifdef ENABLE_CHECKING
2545 /* Theoretically possible, but *highly* unlikely. */
2546 gcc_assert (num_iterations < 500);
2549 statistics_histogram_event (cfun, "compute_partial_antic iterations",
2552 sbitmap_free (has_abnormal_preds);
2553 sbitmap_free (changed_blocks);
2556 /* Return true if we can value number the call in STMT. This is true
2557 if we have a pure or constant call. */
2560 can_value_number_call (gimple stmt)
2562 if (gimple_call_flags (stmt) & (ECF_PURE | ECF_CONST))
2567 /* Return true if OP is a tree which we can perform PRE on.
2568 This may not match the operations we can value number, but in
2569 a perfect world would. */
2572 can_PRE_operation (tree op)
2574 return UNARY_CLASS_P (op)
2575 || BINARY_CLASS_P (op)
2576 || COMPARISON_CLASS_P (op)
2577 || TREE_CODE (op) == INDIRECT_REF
2578 || TREE_CODE (op) == COMPONENT_REF
2579 || TREE_CODE (op) == VIEW_CONVERT_EXPR
2580 || TREE_CODE (op) == CALL_EXPR
2581 || TREE_CODE (op) == ARRAY_REF;
2585 /* Inserted expressions are placed onto this worklist, which is used
2586 for performing quick dead code elimination of insertions we made
2587 that didn't turn out to be necessary. */
2588 static VEC(gimple,heap) *inserted_exprs;
2589 static bitmap inserted_phi_names;
2591 /* Pool allocated fake store expressions are placed onto this
2592 worklist, which, after performing dead code elimination, is walked
2593 to see which expressions need to be put into GC'able memory */
2594 static VEC(gimple, heap) *need_creation;
2596 /* The actual worker for create_component_ref_by_pieces. */
2599 create_component_ref_by_pieces_1 (basic_block block, vn_reference_t ref,
2600 unsigned int *operand, gimple_seq *stmts,
2603 vn_reference_op_t currop = VEC_index (vn_reference_op_s, ref->operands,
2607 switch (currop->opcode)
2611 tree folded, sc = currop->op1;
2612 unsigned int nargs = 0;
2613 tree *args = XNEWVEC (tree, VEC_length (vn_reference_op_s,
2614 ref->operands) - 1);
2615 while (*operand < VEC_length (vn_reference_op_s, ref->operands))
2617 args[nargs] = create_component_ref_by_pieces_1 (block, ref,
2622 folded = build_call_array (currop->type,
2623 TREE_CODE (currop->op0) == FUNCTION_DECL
2624 ? build_fold_addr_expr (currop->op0)
2630 pre_expr scexpr = get_or_alloc_expr_for (sc);
2631 sc = find_or_generate_expression (block, scexpr, stmts, domstmt);
2634 CALL_EXPR_STATIC_CHAIN (folded) = sc;
2639 case TARGET_MEM_REF:
2641 vn_reference_op_t nextop = VEC_index (vn_reference_op_s, ref->operands,
2644 tree genop0 = NULL_TREE;
2645 tree baseop = create_component_ref_by_pieces_1 (block, ref, operand,
2651 op0expr = get_or_alloc_expr_for (currop->op0);
2652 genop0 = find_or_generate_expression (block, op0expr,
2657 if (DECL_P (baseop))
2658 return build6 (TARGET_MEM_REF, currop->type,
2660 genop0, currop->op1, currop->op2,
2661 unshare_expr (nextop->op1));
2663 return build6 (TARGET_MEM_REF, currop->type,
2665 genop0, currop->op1, currop->op2,
2666 unshare_expr (nextop->op1));
2672 gcc_assert (is_gimple_min_invariant (currop->op0));
2678 case VIEW_CONVERT_EXPR:
2681 tree genop0 = create_component_ref_by_pieces_1 (block, ref,
2686 folded = fold_build1 (currop->opcode, currop->type,
2691 case ALIGN_INDIRECT_REF:
2692 case MISALIGNED_INDIRECT_REF:
2696 tree genop1 = create_component_ref_by_pieces_1 (block, ref,
2701 genop1 = fold_convert (build_pointer_type (currop->type),
2704 if (currop->opcode == MISALIGNED_INDIRECT_REF)
2705 folded = fold_build2 (currop->opcode, currop->type,
2706 genop1, currop->op1);
2708 folded = fold_build1 (currop->opcode, currop->type,
2716 tree genop0 = create_component_ref_by_pieces_1 (block, ref, operand,
2718 pre_expr op1expr = get_or_alloc_expr_for (currop->op0);
2719 pre_expr op2expr = get_or_alloc_expr_for (currop->op1);
2725 genop1 = find_or_generate_expression (block, op1expr, stmts, domstmt);
2728 genop2 = find_or_generate_expression (block, op2expr, stmts, domstmt);
2731 folded = fold_build3 (BIT_FIELD_REF, currop->type, genop0, genop1,
2736 /* For array ref vn_reference_op's, operand 1 of the array ref
2737 is op0 of the reference op and operand 3 of the array ref is
2739 case ARRAY_RANGE_REF:
2743 tree genop1 = currop->op0;
2745 tree genop2 = currop->op1;
2747 tree genop3 = currop->op2;
2749 genop0 = create_component_ref_by_pieces_1 (block, ref, operand,
2753 op1expr = get_or_alloc_expr_for (genop1);
2754 genop1 = find_or_generate_expression (block, op1expr, stmts, domstmt);
2759 op2expr = get_or_alloc_expr_for (genop2);
2760 genop2 = find_or_generate_expression (block, op2expr, stmts,
2767 tree elmt_type = TREE_TYPE (TREE_TYPE (genop0));
2768 genop3 = size_binop (EXACT_DIV_EXPR, genop3,
2769 size_int (TYPE_ALIGN_UNIT (elmt_type)));
2770 op3expr = get_or_alloc_expr_for (genop3);
2771 genop3 = find_or_generate_expression (block, op3expr, stmts,
2776 return build4 (currop->opcode, currop->type, genop0, genop1,
2783 tree genop2 = currop->op1;
2785 op0 = create_component_ref_by_pieces_1 (block, ref, operand,
2789 /* op1 should be a FIELD_DECL, which are represented by
2794 op2expr = get_or_alloc_expr_for (genop2);
2795 genop2 = find_or_generate_expression (block, op2expr, stmts,
2801 return fold_build3 (COMPONENT_REF, TREE_TYPE (op1), op0, op1,
2807 pre_expr op0expr = get_or_alloc_expr_for (currop->op0);
2808 genop = find_or_generate_expression (block, op0expr, stmts, domstmt);
2829 /* For COMPONENT_REF's and ARRAY_REF's, we can't have any intermediates for the
2830 COMPONENT_REF or INDIRECT_REF or ARRAY_REF portion, because we'd end up with
2831 trying to rename aggregates into ssa form directly, which is a no no.
2833 Thus, this routine doesn't create temporaries, it just builds a
2834 single access expression for the array, calling
2835 find_or_generate_expression to build the innermost pieces.
2837 This function is a subroutine of create_expression_by_pieces, and
2838 should not be called on it's own unless you really know what you
2842 create_component_ref_by_pieces (basic_block block, vn_reference_t ref,
2843 gimple_seq *stmts, gimple domstmt)
2845 unsigned int op = 0;
2846 return create_component_ref_by_pieces_1 (block, ref, &op, stmts, domstmt);
2849 /* Find a leader for an expression, or generate one using
2850 create_expression_by_pieces if it's ANTIC but
2852 BLOCK is the basic_block we are looking for leaders in.
2853 EXPR is the expression to find a leader or generate for.
2854 STMTS is the statement list to put the inserted expressions on.
2855 Returns the SSA_NAME of the LHS of the generated expression or the
2857 DOMSTMT if non-NULL is a statement that should be dominated by
2858 all uses in the generated expression. If DOMSTMT is non-NULL this
2859 routine can fail and return NULL_TREE. Otherwise it will assert
2863 find_or_generate_expression (basic_block block, pre_expr expr,
2864 gimple_seq *stmts, gimple domstmt)
2866 pre_expr leader = bitmap_find_leader (AVAIL_OUT (block),
2867 get_expr_value_id (expr), domstmt);
2871 if (leader->kind == NAME)
2872 genop = PRE_EXPR_NAME (leader);
2873 else if (leader->kind == CONSTANT)
2874 genop = PRE_EXPR_CONSTANT (leader);
2877 /* If it's still NULL, it must be a complex expression, so generate
2878 it recursively. Not so for FRE though. */
2882 bitmap_set_t exprset;
2883 unsigned int lookfor = get_expr_value_id (expr);
2884 bool handled = false;
2888 exprset = VEC_index (bitmap_set_t, value_expressions, lookfor);
2889 FOR_EACH_EXPR_ID_IN_SET (exprset, i, bi)
2891 pre_expr temp = expression_for_id (i);
2892 if (temp->kind != NAME)
2895 genop = create_expression_by_pieces (block, temp, stmts,
2897 get_expr_type (expr));
2901 if (!handled && domstmt)
2904 gcc_assert (handled);
2909 #define NECESSARY GF_PLF_1
2911 /* Create an expression in pieces, so that we can handle very complex
2912 expressions that may be ANTIC, but not necessary GIMPLE.
2913 BLOCK is the basic block the expression will be inserted into,
2914 EXPR is the expression to insert (in value form)
2915 STMTS is a statement list to append the necessary insertions into.
2917 This function will die if we hit some value that shouldn't be
2918 ANTIC but is (IE there is no leader for it, or its components).
2919 This function may also generate expressions that are themselves
2920 partially or fully redundant. Those that are will be either made
2921 fully redundant during the next iteration of insert (for partially
2922 redundant ones), or eliminated by eliminate (for fully redundant
2925 If DOMSTMT is non-NULL then we make sure that all uses in the
2926 expressions dominate that statement. In this case the function
2927 can return NULL_TREE to signal failure. */
2930 create_expression_by_pieces (basic_block block, pre_expr expr,
2931 gimple_seq *stmts, gimple domstmt, tree type)
2935 gimple_seq forced_stmts = NULL;
2936 unsigned int value_id;
2937 gimple_stmt_iterator gsi;
2938 tree exprtype = type ? type : get_expr_type (expr);
2944 /* We may hit the NAME/CONSTANT case if we have to convert types
2945 that value numbering saw through. */
2947 folded = PRE_EXPR_NAME (expr);
2950 folded = PRE_EXPR_CONSTANT (expr);
2954 vn_reference_t ref = PRE_EXPR_REFERENCE (expr);
2955 folded = create_component_ref_by_pieces (block, ref, stmts, domstmt);
2960 vn_nary_op_t nary = PRE_EXPR_NARY (expr);
2961 switch (nary->length)
2965 pre_expr op1 = get_or_alloc_expr_for (nary->op[0]);
2966 pre_expr op2 = get_or_alloc_expr_for (nary->op[1]);
2967 tree genop1 = find_or_generate_expression (block, op1,
2969 tree genop2 = find_or_generate_expression (block, op2,
2971 if (!genop1 || !genop2)
2973 genop1 = fold_convert (TREE_TYPE (nary->op[0]),
2975 /* Ensure op2 is a sizetype for POINTER_PLUS_EXPR. It
2976 may be a constant with the wrong type. */
2977 if (nary->opcode == POINTER_PLUS_EXPR)
2978 genop2 = fold_convert (sizetype, genop2);
2980 genop2 = fold_convert (TREE_TYPE (nary->op[1]), genop2);
2982 folded = fold_build2 (nary->opcode, nary->type,
2988 pre_expr op1 = get_or_alloc_expr_for (nary->op[0]);
2989 tree genop1 = find_or_generate_expression (block, op1,
2993 genop1 = fold_convert (TREE_TYPE (nary->op[0]), genop1);
2995 folded = fold_build1 (nary->opcode, nary->type,
3008 if (!useless_type_conversion_p (exprtype, TREE_TYPE (folded)))
3009 folded = fold_convert (exprtype, folded);
3011 /* Force the generated expression to be a sequence of GIMPLE
3013 We have to call unshare_expr because force_gimple_operand may
3014 modify the tree we pass to it. */
3015 folded = force_gimple_operand (unshare_expr (folded), &forced_stmts,
3018 /* If we have any intermediate expressions to the value sets, add them
3019 to the value sets and chain them in the instruction stream. */
3022 gsi = gsi_start (forced_stmts);
3023 for (; !gsi_end_p (gsi); gsi_next (&gsi))
3025 gimple stmt = gsi_stmt (gsi);
3026 tree forcedname = gimple_get_lhs (stmt);
3029 VEC_safe_push (gimple, heap, inserted_exprs, stmt);
3030 if (TREE_CODE (forcedname) == SSA_NAME)
3032 VN_INFO_GET (forcedname)->valnum = forcedname;
3033 VN_INFO (forcedname)->value_id = get_next_value_id ();
3034 nameexpr = get_or_alloc_expr_for_name (forcedname);
3035 add_to_value (VN_INFO (forcedname)->value_id, nameexpr);
3037 bitmap_value_replace_in_set (NEW_SETS (block), nameexpr);
3038 bitmap_value_replace_in_set (AVAIL_OUT (block), nameexpr);
3040 mark_symbols_for_renaming (stmt);
3042 gimple_seq_add_seq (stmts, forced_stmts);
3045 /* Build and insert the assignment of the end result to the temporary
3046 that we will return. */
3047 if (!pretemp || exprtype != TREE_TYPE (pretemp))
3049 pretemp = create_tmp_var (exprtype, "pretmp");
3050 get_var_ann (pretemp);
3054 add_referenced_var (temp);
3056 if (TREE_CODE (exprtype) == COMPLEX_TYPE
3057 || TREE_CODE (exprtype) == VECTOR_TYPE)
3058 DECL_GIMPLE_REG_P (temp) = 1;
3060 newstmt = gimple_build_assign (temp, folded);
3061 name = make_ssa_name (temp, newstmt);
3062 gimple_assign_set_lhs (newstmt, name);
3063 gimple_set_plf (newstmt, NECESSARY, false);
3065 gimple_seq_add_stmt (stmts, newstmt);
3066 VEC_safe_push (gimple, heap, inserted_exprs, newstmt);
3068 /* All the symbols in NEWEXPR should be put into SSA form. */
3069 mark_symbols_for_renaming (newstmt);
3071 /* Add a value number to the temporary.
3072 The value may already exist in either NEW_SETS, or AVAIL_OUT, because
3073 we are creating the expression by pieces, and this particular piece of
3074 the expression may have been represented. There is no harm in replacing
3076 VN_INFO_GET (name)->valnum = name;
3077 value_id = get_expr_value_id (expr);
3078 VN_INFO (name)->value_id = value_id;
3079 nameexpr = get_or_alloc_expr_for_name (name);
3080 add_to_value (value_id, nameexpr);
3082 bitmap_value_replace_in_set (NEW_SETS (block), nameexpr);
3083 bitmap_value_replace_in_set (AVAIL_OUT (block), nameexpr);
3085 pre_stats.insertions++;
3086 if (dump_file && (dump_flags & TDF_DETAILS))
3088 fprintf (dump_file, "Inserted ");
3089 print_gimple_stmt (dump_file, newstmt, 0, 0);
3090 fprintf (dump_file, " in predecessor %d\n", block->index);
3097 /* Returns true if we want to inhibit the insertions of PHI nodes
3098 for the given EXPR for basic block BB (a member of a loop).
3099 We want to do this, when we fear that the induction variable we
3100 create might inhibit vectorization. */
3103 inhibit_phi_insertion (basic_block bb, pre_expr expr)
3105 vn_reference_t vr = PRE_EXPR_REFERENCE (expr);
3106 VEC (vn_reference_op_s, heap) *ops = vr->operands;
3107 vn_reference_op_t op;
3110 /* If we aren't going to vectorize we don't inhibit anything. */
3111 if (!flag_tree_vectorize)
3114 /* Otherwise we inhibit the insertion when the address of the
3115 memory reference is a simple induction variable. In other
3116 cases the vectorizer won't do anything anyway (either it's
3117 loop invariant or a complicated expression). */
3118 for (i = 0; VEC_iterate (vn_reference_op_s, ops, i, op); ++i)
3123 case ARRAY_RANGE_REF:
3124 if (TREE_CODE (op->op0) != SSA_NAME)
3129 basic_block defbb = gimple_bb (SSA_NAME_DEF_STMT (op->op0));
3131 /* Default defs are loop invariant. */
3134 /* Defined outside this loop, also loop invariant. */
3135 if (!flow_bb_inside_loop_p (bb->loop_father, defbb))
3137 /* If it's a simple induction variable inhibit insertion,
3138 the vectorizer might be interested in this one. */
3139 if (simple_iv (bb->loop_father, bb->loop_father,
3140 op->op0, &iv, true))
3142 /* No simple IV, vectorizer can't do anything, hence no
3143 reason to inhibit the transformation for this operand. */
3153 /* Insert the to-be-made-available values of expression EXPRNUM for each
3154 predecessor, stored in AVAIL, into the predecessors of BLOCK, and
3155 merge the result with a phi node, given the same value number as
3156 NODE. Return true if we have inserted new stuff. */
3159 insert_into_preds_of_block (basic_block block, unsigned int exprnum,
3162 pre_expr expr = expression_for_id (exprnum);
3164 unsigned int val = get_expr_value_id (expr);
3166 bool insertions = false;
3171 tree type = get_expr_type (expr);
3175 if (dump_file && (dump_flags & TDF_DETAILS))
3177 fprintf (dump_file, "Found partial redundancy for expression ");
3178 print_pre_expr (dump_file, expr);
3179 fprintf (dump_file, " (%04d)\n", val);
3182 /* Make sure we aren't creating an induction variable. */
3183 if (block->loop_depth > 0 && EDGE_COUNT (block->preds) == 2)
3185 bool firstinsideloop = false;
3186 bool secondinsideloop = false;
3187 firstinsideloop = flow_bb_inside_loop_p (block->loop_father,
3188 EDGE_PRED (block, 0)->src);
3189 secondinsideloop = flow_bb_inside_loop_p (block->loop_father,
3190 EDGE_PRED (block, 1)->src);
3191 /* Induction variables only have one edge inside the loop. */
3192 if ((firstinsideloop ^ secondinsideloop)
3193 && (expr->kind != REFERENCE
3194 || inhibit_phi_insertion (block, expr)))
3196 if (dump_file && (dump_flags & TDF_DETAILS))
3197 fprintf (dump_file, "Skipping insertion of phi for partial redundancy: Looks like an induction variable\n");
3202 /* Make the necessary insertions. */
3203 FOR_EACH_EDGE (pred, ei, block->preds)
3205 gimple_seq stmts = NULL;
3208 eprime = avail[bprime->index];
3210 if (eprime->kind != NAME && eprime->kind != CONSTANT)
3212 builtexpr = create_expression_by_pieces (bprime,
3216 gcc_assert (!(pred->flags & EDGE_ABNORMAL));
3217 gsi_insert_seq_on_edge (pred, stmts);
3218 avail[bprime->index] = get_or_alloc_expr_for_name (builtexpr);
3221 else if (eprime->kind == CONSTANT)
3223 /* Constants may not have the right type, fold_convert
3224 should give us back a constant with the right type.
3226 tree constant = PRE_EXPR_CONSTANT (eprime);
3227 if (!useless_type_conversion_p (type, TREE_TYPE (constant)))
3229 tree builtexpr = fold_convert (type, constant);
3230 if (!is_gimple_min_invariant (builtexpr))
3232 tree forcedexpr = force_gimple_operand (builtexpr,
3235 if (!is_gimple_min_invariant (forcedexpr))
3237 if (forcedexpr != builtexpr)
3239 VN_INFO_GET (forcedexpr)->valnum = PRE_EXPR_CONSTANT (eprime);
3240 VN_INFO (forcedexpr)->value_id = get_expr_value_id (eprime);
3244 gimple_stmt_iterator gsi;
3245 gsi = gsi_start (stmts);
3246 for (; !gsi_end_p (gsi); gsi_next (&gsi))
3248 gimple stmt = gsi_stmt (gsi);
3249 VEC_safe_push (gimple, heap, inserted_exprs, stmt);
3250 gimple_set_plf (stmt, NECESSARY, false);
3252 gsi_insert_seq_on_edge (pred, stmts);
3254 avail[bprime->index] = get_or_alloc_expr_for_name (forcedexpr);
3259 else if (eprime->kind == NAME)
3261 /* We may have to do a conversion because our value
3262 numbering can look through types in certain cases, but
3263 our IL requires all operands of a phi node have the same
3265 tree name = PRE_EXPR_NAME (eprime);
3266 if (!useless_type_conversion_p (type, TREE_TYPE (name)))
3270 builtexpr = fold_convert (type, name);
3271 forcedexpr = force_gimple_operand (builtexpr,
3275 if (forcedexpr != name)
3277 VN_INFO_GET (forcedexpr)->valnum = VN_INFO (name)->valnum;
3278 VN_INFO (forcedexpr)->value_id = VN_INFO (name)->value_id;
3283 gimple_stmt_iterator gsi;
3284 gsi = gsi_start (stmts);
3285 for (; !gsi_end_p (gsi); gsi_next (&gsi))
3287 gimple stmt = gsi_stmt (gsi);
3288 VEC_safe_push (gimple, heap, inserted_exprs, stmt);
3289 gimple_set_plf (stmt, NECESSARY, false);
3291 gsi_insert_seq_on_edge (pred, stmts);
3293 avail[bprime->index] = get_or_alloc_expr_for_name (forcedexpr);
3297 /* If we didn't want a phi node, and we made insertions, we still have
3298 inserted new stuff, and thus return true. If we didn't want a phi node,
3299 and didn't make insertions, we haven't added anything new, so return
3301 if (nophi && insertions)
3303 else if (nophi && !insertions)
3306 /* Now build a phi for the new variable. */
3307 if (!prephitemp || TREE_TYPE (prephitemp) != type)
3309 prephitemp = create_tmp_var (type, "prephitmp");
3310 get_var_ann (prephitemp);
3314 add_referenced_var (temp);
3316 if (TREE_CODE (type) == COMPLEX_TYPE
3317 || TREE_CODE (type) == VECTOR_TYPE)
3318 DECL_GIMPLE_REG_P (temp) = 1;
3319 phi = create_phi_node (temp, block);
3321 gimple_set_plf (phi, NECESSARY, false);
3322 VN_INFO_GET (gimple_phi_result (phi))->valnum = gimple_phi_result (phi);
3323 VN_INFO (gimple_phi_result (phi))->value_id = val;
3324 VEC_safe_push (gimple, heap, inserted_exprs, phi);
3325 bitmap_set_bit (inserted_phi_names,
3326 SSA_NAME_VERSION (gimple_phi_result (phi)));
3327 FOR_EACH_EDGE (pred, ei, block->preds)
3329 pre_expr ae = avail[pred->src->index];
3330 gcc_assert (get_expr_type (ae) == type
3331 || useless_type_conversion_p (type, get_expr_type (ae)));
3332 if (ae->kind == CONSTANT)
3333 add_phi_arg (phi, PRE_EXPR_CONSTANT (ae), pred, UNKNOWN_LOCATION);
3335 add_phi_arg (phi, PRE_EXPR_NAME (avail[pred->src->index]), pred,
3339 newphi = get_or_alloc_expr_for_name (gimple_phi_result (phi));
3340 add_to_value (val, newphi);
3342 /* The value should *not* exist in PHI_GEN, or else we wouldn't be doing
3343 this insertion, since we test for the existence of this value in PHI_GEN
3344 before proceeding with the partial redundancy checks in insert_aux.
3346 The value may exist in AVAIL_OUT, in particular, it could be represented
3347 by the expression we are trying to eliminate, in which case we want the
3348 replacement to occur. If it's not existing in AVAIL_OUT, we want it
3351 Similarly, to the PHI_GEN case, the value should not exist in NEW_SETS of
3352 this block, because if it did, it would have existed in our dominator's
3353 AVAIL_OUT, and would have been skipped due to the full redundancy check.
3356 bitmap_insert_into_set (PHI_GEN (block), newphi);
3357 bitmap_value_replace_in_set (AVAIL_OUT (block),
3359 bitmap_insert_into_set (NEW_SETS (block),
3362 if (dump_file && (dump_flags & TDF_DETAILS))
3364 fprintf (dump_file, "Created phi ");
3365 print_gimple_stmt (dump_file, phi, 0, 0);
3366 fprintf (dump_file, " in block %d\n", block->index);
3374 /* Perform insertion of partially redundant values.
3375 For BLOCK, do the following:
3376 1. Propagate the NEW_SETS of the dominator into the current block.
3377 If the block has multiple predecessors,
3378 2a. Iterate over the ANTIC expressions for the block to see if
3379 any of them are partially redundant.
3380 2b. If so, insert them into the necessary predecessors to make
3381 the expression fully redundant.
3382 2c. Insert a new PHI merging the values of the predecessors.
3383 2d. Insert the new PHI, and the new expressions, into the
3385 3. Recursively call ourselves on the dominator children of BLOCK.
3387 Steps 1, 2a, and 3 are done by insert_aux. 2b, 2c and 2d are done by
3388 do_regular_insertion and do_partial_insertion.
3393 do_regular_insertion (basic_block block, basic_block dom)
3395 bool new_stuff = false;
3396 VEC (pre_expr, heap) *exprs = sorted_array_from_bitmap_set (ANTIC_IN (block));
3400 for (i = 0; VEC_iterate (pre_expr, exprs, i, expr); i++)
3402 if (expr->kind != NAME)
3406 bool by_some = false;
3407 bool cant_insert = false;
3408 bool all_same = true;
3409 pre_expr first_s = NULL;
3412 pre_expr eprime = NULL;
3414 pre_expr edoubleprime = NULL;
3415 bool do_insertion = false;
3417 val = get_expr_value_id (expr);
3418 if (bitmap_set_contains_value (PHI_GEN (block), val))
3420 if (bitmap_set_contains_value (AVAIL_OUT (dom), val))
3422 if (dump_file && (dump_flags & TDF_DETAILS))
3423 fprintf (dump_file, "Found fully redundant value\n");
3427 avail = XCNEWVEC (pre_expr, last_basic_block);
3428 FOR_EACH_EDGE (pred, ei, block->preds)
3430 unsigned int vprime;
3432 /* We should never run insertion for the exit block
3433 and so not come across fake pred edges. */
3434 gcc_assert (!(pred->flags & EDGE_FAKE));
3436 eprime = phi_translate (expr, ANTIC_IN (block), NULL,
3439 /* eprime will generally only be NULL if the
3440 value of the expression, translated
3441 through the PHI for this predecessor, is
3442 undefined. If that is the case, we can't
3443 make the expression fully redundant,
3444 because its value is undefined along a
3445 predecessor path. We can thus break out
3446 early because it doesn't matter what the
3447 rest of the results are. */
3454 eprime = fully_constant_expression (eprime);
3455 vprime = get_expr_value_id (eprime);
3456 edoubleprime = bitmap_find_leader (AVAIL_OUT (bprime),
3458 if (edoubleprime == NULL)
3460 avail[bprime->index] = eprime;
3465 avail[bprime->index] = edoubleprime;
3467 /* We want to perform insertions to remove a redundancy on
3468 a path in the CFG we want to optimize for speed. */
3469 if (optimize_edge_for_speed_p (pred))
3470 do_insertion = true;
3471 if (first_s == NULL)
3472 first_s = edoubleprime;
3473 else if (!pre_expr_eq (first_s, edoubleprime))
3477 /* If we can insert it, it's not the same value
3478 already existing along every predecessor, and
3479 it's defined by some predecessor, it is
3480 partially redundant. */
3481 if (!cant_insert && !all_same && by_some && do_insertion
3482 && dbg_cnt (treepre_insert))
3484 if (insert_into_preds_of_block (block, get_expression_id (expr),
3488 /* If all edges produce the same value and that value is
3489 an invariant, then the PHI has the same value on all
3490 edges. Note this. */
3491 else if (!cant_insert && all_same && eprime
3492 && (edoubleprime->kind == CONSTANT
3493 || edoubleprime->kind == NAME)
3494 && !value_id_constant_p (val))
3498 bitmap_set_t exprset = VEC_index (bitmap_set_t,
3499 value_expressions, val);
3501 unsigned int new_val = get_expr_value_id (edoubleprime);
3502 FOR_EACH_EXPR_ID_IN_SET (exprset, j, bi)
3504 pre_expr expr = expression_for_id (j);
3506 if (expr->kind == NAME)
3508 vn_ssa_aux_t info = VN_INFO (PRE_EXPR_NAME (expr));
3509 /* Just reset the value id and valnum so it is
3510 the same as the constant we have discovered. */
3511 if (edoubleprime->kind == CONSTANT)
3513 info->valnum = PRE_EXPR_CONSTANT (edoubleprime);
3514 pre_stats.constified++;
3517 info->valnum = VN_INFO (PRE_EXPR_NAME (edoubleprime))->valnum;
3518 info->value_id = new_val;
3526 VEC_free (pre_expr, heap, exprs);
3531 /* Perform insertion for partially anticipatable expressions. There
3532 is only one case we will perform insertion for these. This case is
3533 if the expression is partially anticipatable, and fully available.
3534 In this case, we know that putting it earlier will enable us to
3535 remove the later computation. */
3539 do_partial_partial_insertion (basic_block block, basic_block dom)
3541 bool new_stuff = false;
3542 VEC (pre_expr, heap) *exprs = sorted_array_from_bitmap_set (PA_IN (block));
3546 for (i = 0; VEC_iterate (pre_expr, exprs, i, expr); i++)
3548 if (expr->kind != NAME)
3553 bool cant_insert = false;
3556 pre_expr eprime = NULL;
3559 val = get_expr_value_id (expr);
3560 if (bitmap_set_contains_value (PHI_GEN (block), val))
3562 if (bitmap_set_contains_value (AVAIL_OUT (dom), val))
3565 avail = XCNEWVEC (pre_expr, last_basic_block);
3566 FOR_EACH_EDGE (pred, ei, block->preds)
3568 unsigned int vprime;
3569 pre_expr edoubleprime;
3571 /* We should never run insertion for the exit block
3572 and so not come across fake pred edges. */
3573 gcc_assert (!(pred->flags & EDGE_FAKE));
3575 eprime = phi_translate (expr, ANTIC_IN (block),
3579 /* eprime will generally only be NULL if the
3580 value of the expression, translated
3581 through the PHI for this predecessor, is
3582 undefined. If that is the case, we can't
3583 make the expression fully redundant,
3584 because its value is undefined along a
3585 predecessor path. We can thus break out
3586 early because it doesn't matter what the
3587 rest of the results are. */
3594 eprime = fully_constant_expression (eprime);
3595 vprime = get_expr_value_id (eprime);
3596 edoubleprime = bitmap_find_leader (AVAIL_OUT (bprime),
3598 if (edoubleprime == NULL)
3604 avail[bprime->index] = edoubleprime;
3608 /* If we can insert it, it's not the same value
3609 already existing along every predecessor, and
3610 it's defined by some predecessor, it is
3611 partially redundant. */
3612 if (!cant_insert && by_all && dbg_cnt (treepre_insert))
3614 pre_stats.pa_insert++;
3615 if (insert_into_preds_of_block (block, get_expression_id (expr),
3623 VEC_free (pre_expr, heap, exprs);
3628 insert_aux (basic_block block)
3631 bool new_stuff = false;
3636 dom = get_immediate_dominator (CDI_DOMINATORS, block);
3641 bitmap_set_t newset = NEW_SETS (dom);
3644 /* Note that we need to value_replace both NEW_SETS, and
3645 AVAIL_OUT. For both the case of NEW_SETS, the value may be
3646 represented by some non-simple expression here that we want
3647 to replace it with. */
3648 FOR_EACH_EXPR_ID_IN_SET (newset, i, bi)
3650 pre_expr expr = expression_for_id (i);
3651 bitmap_value_replace_in_set (NEW_SETS (block), expr);
3652 bitmap_value_replace_in_set (AVAIL_OUT (block), expr);
3655 if (!single_pred_p (block))
3657 new_stuff |= do_regular_insertion (block, dom);
3658 if (do_partial_partial)
3659 new_stuff |= do_partial_partial_insertion (block, dom);
3663 for (son = first_dom_son (CDI_DOMINATORS, block);
3665 son = next_dom_son (CDI_DOMINATORS, son))
3667 new_stuff |= insert_aux (son);
3673 /* Perform insertion of partially redundant values. */
3678 bool new_stuff = true;
3680 int num_iterations = 0;
3683 NEW_SETS (bb) = bitmap_set_new ();
3688 new_stuff = insert_aux (ENTRY_BLOCK_PTR);
3690 statistics_histogram_event (cfun, "insert iterations", num_iterations);
3694 /* Add OP to EXP_GEN (block), and possibly to the maximal set. */
3697 add_to_exp_gen (basic_block block, tree op)
3702 if (TREE_CODE (op) == SSA_NAME && ssa_undefined_value_p (op))
3704 result = get_or_alloc_expr_for_name (op);
3705 bitmap_value_insert_into_set (EXP_GEN (block), result);
3709 /* Create value ids for PHI in BLOCK. */
3712 make_values_for_phi (gimple phi, basic_block block)
3714 tree result = gimple_phi_result (phi);
3716 /* We have no need for virtual phis, as they don't represent
3717 actual computations. */
3718 if (is_gimple_reg (result))
3720 pre_expr e = get_or_alloc_expr_for_name (result);
3721 add_to_value (get_expr_value_id (e), e);
3722 bitmap_insert_into_set (PHI_GEN (block), e);
3723 bitmap_value_insert_into_set (AVAIL_OUT (block), e);
3727 for (i = 0; i < gimple_phi_num_args (phi); ++i)
3729 tree arg = gimple_phi_arg_def (phi, i);
3730 if (TREE_CODE (arg) == SSA_NAME)
3732 e = get_or_alloc_expr_for_name (arg);
3733 add_to_value (get_expr_value_id (e), e);
3740 /* Compute the AVAIL set for all basic blocks.
3742 This function performs value numbering of the statements in each basic
3743 block. The AVAIL sets are built from information we glean while doing
3744 this value numbering, since the AVAIL sets contain only one entry per
3747 AVAIL_IN[BLOCK] = AVAIL_OUT[dom(BLOCK)].
3748 AVAIL_OUT[BLOCK] = AVAIL_IN[BLOCK] U PHI_GEN[BLOCK] U TMP_GEN[BLOCK]. */
3751 compute_avail (void)
3754 basic_block block, son;
3755 basic_block *worklist;
3759 /* We pretend that default definitions are defined in the entry block.
3760 This includes function arguments and the static chain decl. */
3761 for (i = 1; i < num_ssa_names; ++i)
3763 tree name = ssa_name (i);
3766 || !SSA_NAME_IS_DEFAULT_DEF (name)
3767 || has_zero_uses (name)
3768 || !is_gimple_reg (name))
3771 e = get_or_alloc_expr_for_name (name);
3772 add_to_value (get_expr_value_id (e), e);
3774 bitmap_insert_into_set (TMP_GEN (ENTRY_BLOCK_PTR), e);
3775 bitmap_value_insert_into_set (AVAIL_OUT (ENTRY_BLOCK_PTR), e);
3778 /* Allocate the worklist. */
3779 worklist = XNEWVEC (basic_block, n_basic_blocks);
3781 /* Seed the algorithm by putting the dominator children of the entry
3782 block on the worklist. */
3783 for (son = first_dom_son (CDI_DOMINATORS, ENTRY_BLOCK_PTR);
3785 son = next_dom_son (CDI_DOMINATORS, son))
3786 worklist[sp++] = son;
3788 /* Loop until the worklist is empty. */
3791 gimple_stmt_iterator gsi;
3794 unsigned int stmt_uid = 1;
3796 /* Pick a block from the worklist. */
3797 block = worklist[--sp];
3799 /* Initially, the set of available values in BLOCK is that of
3800 its immediate dominator. */
3801 dom = get_immediate_dominator (CDI_DOMINATORS, block);
3803 bitmap_set_copy (AVAIL_OUT (block), AVAIL_OUT (dom));
3805 /* Generate values for PHI nodes. */
3806 for (gsi = gsi_start_phis (block); !gsi_end_p (gsi); gsi_next (&gsi))
3807 make_values_for_phi (gsi_stmt (gsi), block);
3809 BB_MAY_NOTRETURN (block) = 0;
3811 /* Now compute value numbers and populate value sets with all
3812 the expressions computed in BLOCK. */
3813 for (gsi = gsi_start_bb (block); !gsi_end_p (gsi); gsi_next (&gsi))
3818 stmt = gsi_stmt (gsi);
3819 gimple_set_uid (stmt, stmt_uid++);
3821 /* Cache whether the basic-block has any non-visible side-effect
3823 If this isn't a call or it is the last stmt in the
3824 basic-block then the CFG represents things correctly. */
3825 if (is_gimple_call (stmt)
3826 && !stmt_ends_bb_p (stmt))
3828 /* Non-looping const functions always return normally.
3829 Otherwise the call might not return or have side-effects
3830 that forbids hoisting possibly trapping expressions
3832 int flags = gimple_call_flags (stmt);
3833 if (!(flags & ECF_CONST)
3834 || (flags & ECF_LOOPING_CONST_OR_PURE))
3835 BB_MAY_NOTRETURN (block) = 1;
3838 FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_DEF)
3840 pre_expr e = get_or_alloc_expr_for_name (op);
3842 add_to_value (get_expr_value_id (e), e);
3844 bitmap_insert_into_set (TMP_GEN (block), e);
3845 bitmap_value_insert_into_set (AVAIL_OUT (block), e);
3848 if (gimple_has_volatile_ops (stmt)
3849 || stmt_could_throw_p (stmt))
3852 switch (gimple_code (stmt))
3855 FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_USE)
3856 add_to_exp_gen (block, op);
3863 vn_reference_op_t vro;
3864 pre_expr result = NULL;
3865 VEC(vn_reference_op_s, heap) *ops = NULL;
3867 if (!can_value_number_call (stmt))
3870 copy_reference_ops_from_call (stmt, &ops);
3871 vn_reference_lookup_pieces (gimple_vuse (stmt), 0,
3872 gimple_expr_type (stmt),
3874 VEC_free (vn_reference_op_s, heap, ops);
3878 for (i = 0; VEC_iterate (vn_reference_op_s,
3882 if (vro->op0 && TREE_CODE (vro->op0) == SSA_NAME)
3883 add_to_exp_gen (block, vro->op0);
3884 if (vro->op1 && TREE_CODE (vro->op1) == SSA_NAME)
3885 add_to_exp_gen (block, vro->op1);
3886 if (vro->op2 && TREE_CODE (vro->op2) == SSA_NAME)
3887 add_to_exp_gen (block, vro->op2);
3889 result = (pre_expr) pool_alloc (pre_expr_pool);
3890 result->kind = REFERENCE;
3892 PRE_EXPR_REFERENCE (result) = ref;
3894 get_or_alloc_expression_id (result);
3895 add_to_value (get_expr_value_id (result), result);
3897 bitmap_value_insert_into_set (EXP_GEN (block), result);
3903 pre_expr result = NULL;
3904 switch (TREE_CODE_CLASS (gimple_assign_rhs_code (stmt)))
3908 case tcc_comparison:
3913 vn_nary_op_lookup_pieces (gimple_num_ops (stmt) - 1,
3914 gimple_assign_rhs_code (stmt),
3915 gimple_expr_type (stmt),
3916 gimple_assign_rhs1 (stmt),
3917 gimple_assign_rhs2 (stmt),
3918 NULL_TREE, NULL_TREE, &nary);
3923 for (i = 0; i < nary->length; i++)
3924 if (TREE_CODE (nary->op[i]) == SSA_NAME)
3925 add_to_exp_gen (block, nary->op[i]);
3927 result = (pre_expr) pool_alloc (pre_expr_pool);
3928 result->kind = NARY;
3930 PRE_EXPR_NARY (result) = nary;
3934 case tcc_declaration:
3939 vn_reference_op_t vro;
3941 vn_reference_lookup (gimple_assign_rhs1 (stmt),
3947 for (i = 0; VEC_iterate (vn_reference_op_s,
3951 if (vro->op0 && TREE_CODE (vro->op0) == SSA_NAME)
3952 add_to_exp_gen (block, vro->op0);
3953 if (vro->op1 && TREE_CODE (vro->op1) == SSA_NAME)
3954 add_to_exp_gen (block, vro->op1);
3955 if (vro->op2 && TREE_CODE (vro->op2) == SSA_NAME)
3956 add_to_exp_gen (block, vro->op2);
3958 result = (pre_expr) pool_alloc (pre_expr_pool);
3959 result->kind = REFERENCE;
3961 PRE_EXPR_REFERENCE (result) = ref;
3966 /* For any other statement that we don't
3967 recognize, simply add all referenced
3968 SSA_NAMEs to EXP_GEN. */
3969 FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_USE)
3970 add_to_exp_gen (block, op);
3974 get_or_alloc_expression_id (result);
3975 add_to_value (get_expr_value_id (result), result);
3977 bitmap_value_insert_into_set (EXP_GEN (block), result);
3986 /* Put the dominator children of BLOCK on the worklist of blocks
3987 to compute available sets for. */
3988 for (son = first_dom_son (CDI_DOMINATORS, block);
3990 son = next_dom_son (CDI_DOMINATORS, son))
3991 worklist[sp++] = son;
3997 /* Insert the expression for SSA_VN that SCCVN thought would be simpler
3998 than the available expressions for it. The insertion point is
3999 right before the first use in STMT. Returns the SSA_NAME that should
4000 be used for replacement. */
4003 do_SCCVN_insertion (gimple stmt, tree ssa_vn)
4005 basic_block bb = gimple_bb (stmt);
4006 gimple_stmt_iterator gsi;
4007 gimple_seq stmts = NULL;
4011 /* First create a value expression from the expression we want
4012 to insert and associate it with the value handle for SSA_VN. */
4013 e = get_or_alloc_expr_for (vn_get_expr_for (ssa_vn));
4017 /* Then use create_expression_by_pieces to generate a valid
4018 expression to insert at this point of the IL stream. */
4019 expr = create_expression_by_pieces (bb, e, &stmts, stmt, NULL);
4020 if (expr == NULL_TREE)
4022 gsi = gsi_for_stmt (stmt);
4023 gsi_insert_seq_before (&gsi, stmts, GSI_SAME_STMT);
4028 /* Eliminate fully redundant computations. */
4033 VEC (gimple, heap) *to_remove = NULL;
4035 unsigned int todo = 0;
4036 gimple_stmt_iterator gsi;
4042 for (gsi = gsi_start_bb (b); !gsi_end_p (gsi); gsi_next (&gsi))
4044 stmt = gsi_stmt (gsi);
4046 /* Lookup the RHS of the expression, see if we have an
4047 available computation for it. If so, replace the RHS with
4048 the available computation. */
4049 if (gimple_has_lhs (stmt)
4050 && TREE_CODE (gimple_get_lhs (stmt)) == SSA_NAME
4051 && !gimple_assign_ssa_name_copy_p (stmt)
4052 && (!gimple_assign_single_p (stmt)
4053 || !is_gimple_min_invariant (gimple_assign_rhs1 (stmt)))
4054 && !gimple_has_volatile_ops (stmt)
4055 && !has_zero_uses (gimple_get_lhs (stmt)))
4057 tree lhs = gimple_get_lhs (stmt);
4058 tree rhs = NULL_TREE;
4060 pre_expr lhsexpr = get_or_alloc_expr_for_name (lhs);
4061 pre_expr sprimeexpr;
4063 if (gimple_assign_single_p (stmt))
4064 rhs = gimple_assign_rhs1 (stmt);
4066 sprimeexpr = bitmap_find_leader (AVAIL_OUT (b),
4067 get_expr_value_id (lhsexpr),
4072 if (sprimeexpr->kind == CONSTANT)
4073 sprime = PRE_EXPR_CONSTANT (sprimeexpr);
4074 else if (sprimeexpr->kind == NAME)
4075 sprime = PRE_EXPR_NAME (sprimeexpr);
4080 /* If there is no existing leader but SCCVN knows this
4081 value is constant, use that constant. */
4082 if (!sprime && is_gimple_min_invariant (VN_INFO (lhs)->valnum))
4084 sprime = VN_INFO (lhs)->valnum;
4085 if (!useless_type_conversion_p (TREE_TYPE (lhs),
4086 TREE_TYPE (sprime)))
4087 sprime = fold_convert (TREE_TYPE (lhs), sprime);
4089 if (dump_file && (dump_flags & TDF_DETAILS))
4091 fprintf (dump_file, "Replaced ");
4092 print_gimple_expr (dump_file, stmt, 0, 0);
4093 fprintf (dump_file, " with ");
4094 print_generic_expr (dump_file, sprime, 0);
4095 fprintf (dump_file, " in ");
4096 print_gimple_stmt (dump_file, stmt, 0, 0);
4098 pre_stats.eliminations++;
4099 propagate_tree_value_into_stmt (&gsi, sprime);
4100 stmt = gsi_stmt (gsi);
4105 /* If there is no existing usable leader but SCCVN thinks
4106 it has an expression it wants to use as replacement,
4108 if (!sprime || sprime == lhs)
4110 tree val = VN_INFO (lhs)->valnum;
4112 && TREE_CODE (val) == SSA_NAME
4113 && VN_INFO (val)->needs_insertion
4114 && can_PRE_operation (vn_get_expr_for (val)))
4115 sprime = do_SCCVN_insertion (stmt, val);
4119 && (rhs == NULL_TREE
4120 || TREE_CODE (rhs) != SSA_NAME
4121 || may_propagate_copy (rhs, sprime)))
4123 gcc_assert (sprime != rhs);
4125 if (dump_file && (dump_flags & TDF_DETAILS))
4127 fprintf (dump_file, "Replaced ");
4128 print_gimple_expr (dump_file, stmt, 0, 0);
4129 fprintf (dump_file, " with ");
4130 print_generic_expr (dump_file, sprime, 0);
4131 fprintf (dump_file, " in ");
4132 print_gimple_stmt (dump_file, stmt, 0, 0);
4135 if (TREE_CODE (sprime) == SSA_NAME)
4136 gimple_set_plf (SSA_NAME_DEF_STMT (sprime),
4138 /* We need to make sure the new and old types actually match,
4139 which may require adding a simple cast, which fold_convert
4141 if ((!rhs || TREE_CODE (rhs) != SSA_NAME)
4142 && !useless_type_conversion_p (gimple_expr_type (stmt),
4143 TREE_TYPE (sprime)))
4144 sprime = fold_convert (gimple_expr_type (stmt), sprime);
4146 pre_stats.eliminations++;
4147 propagate_tree_value_into_stmt (&gsi, sprime);
4148 stmt = gsi_stmt (gsi);
4151 /* If we removed EH side effects from the statement, clean
4152 its EH information. */
4153 if (maybe_clean_or_replace_eh_stmt (stmt, stmt))
4155 bitmap_set_bit (need_eh_cleanup,
4156 gimple_bb (stmt)->index);
4157 if (dump_file && (dump_flags & TDF_DETAILS))
4158 fprintf (dump_file, " Removed EH side effects.\n");
4162 /* If the statement is a scalar store, see if the expression
4163 has the same value number as its rhs. If so, the store is
4165 else if (gimple_assign_single_p (stmt)
4166 && !is_gimple_reg (gimple_assign_lhs (stmt))
4167 && (TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME
4168 || is_gimple_min_invariant (gimple_assign_rhs1 (stmt))))
4170 tree rhs = gimple_assign_rhs1 (stmt);
4172 val = vn_reference_lookup (gimple_assign_lhs (stmt),
4173 gimple_vuse (stmt), true, NULL);
4174 if (TREE_CODE (rhs) == SSA_NAME)
4175 rhs = VN_INFO (rhs)->valnum;
4177 && operand_equal_p (val, rhs, 0))
4179 if (dump_file && (dump_flags & TDF_DETAILS))
4181 fprintf (dump_file, "Deleted redundant store ");
4182 print_gimple_stmt (dump_file, stmt, 0, 0);
4185 /* Queue stmt for removal. */
4186 VEC_safe_push (gimple, heap, to_remove, stmt);
4189 /* Visit COND_EXPRs and fold the comparison with the
4190 available value-numbers. */
4191 else if (gimple_code (stmt) == GIMPLE_COND)
4193 tree op0 = gimple_cond_lhs (stmt);
4194 tree op1 = gimple_cond_rhs (stmt);
4197 if (TREE_CODE (op0) == SSA_NAME)
4198 op0 = VN_INFO (op0)->valnum;
4199 if (TREE_CODE (op1) == SSA_NAME)
4200 op1 = VN_INFO (op1)->valnum;
4201 result = fold_binary (gimple_cond_code (stmt), boolean_type_node,
4203 if (result && TREE_CODE (result) == INTEGER_CST)
4205 if (integer_zerop (result))
4206 gimple_cond_make_false (stmt);
4208 gimple_cond_make_true (stmt);
4210 todo = TODO_cleanup_cfg;
4213 /* Visit indirect calls and turn them into direct calls if
4215 if (gimple_code (stmt) == GIMPLE_CALL
4216 && TREE_CODE (gimple_call_fn (stmt)) == SSA_NAME)
4218 tree fn = VN_INFO (gimple_call_fn (stmt))->valnum;
4219 if (TREE_CODE (fn) == ADDR_EXPR
4220 && TREE_CODE (TREE_OPERAND (fn, 0)) == FUNCTION_DECL)
4222 if (dump_file && (dump_flags & TDF_DETAILS))
4224 fprintf (dump_file, "Replacing call target with ");
4225 print_generic_expr (dump_file, fn, 0);
4226 fprintf (dump_file, " in ");
4227 print_gimple_stmt (dump_file, stmt, 0, 0);
4230 gimple_call_set_fn (stmt, fn);
4232 if (maybe_clean_or_replace_eh_stmt (stmt, stmt))
4234 bitmap_set_bit (need_eh_cleanup,
4235 gimple_bb (stmt)->index);
4236 if (dump_file && (dump_flags & TDF_DETAILS))
4237 fprintf (dump_file, " Removed EH side effects.\n");
4240 /* Changing an indirect call to a direct call may
4241 have exposed different semantics. This may
4242 require an SSA update. */
4243 todo |= TODO_update_ssa_only_virtuals;
4248 for (gsi = gsi_start_phis (b); !gsi_end_p (gsi);)
4250 gimple stmt, phi = gsi_stmt (gsi);
4251 tree sprime = NULL_TREE, res = PHI_RESULT (phi);
4252 pre_expr sprimeexpr, resexpr;
4253 gimple_stmt_iterator gsi2;
4255 /* We want to perform redundant PHI elimination. Do so by
4256 replacing the PHI with a single copy if possible.
4257 Do not touch inserted, single-argument or virtual PHIs. */
4258 if (gimple_phi_num_args (phi) == 1
4259 || !is_gimple_reg (res)
4260 || bitmap_bit_p (inserted_phi_names, SSA_NAME_VERSION (res)))
4266 resexpr = get_or_alloc_expr_for_name (res);
4267 sprimeexpr = bitmap_find_leader (AVAIL_OUT (b),
4268 get_expr_value_id (resexpr), NULL);
4271 if (sprimeexpr->kind == CONSTANT)
4272 sprime = PRE_EXPR_CONSTANT (sprimeexpr);
4273 else if (sprimeexpr->kind == NAME)
4274 sprime = PRE_EXPR_NAME (sprimeexpr);
4285 if (dump_file && (dump_flags & TDF_DETAILS))
4287 fprintf (dump_file, "Replaced redundant PHI node defining ");
4288 print_generic_expr (dump_file, res, 0);
4289 fprintf (dump_file, " with ");
4290 print_generic_expr (dump_file, sprime, 0);
4291 fprintf (dump_file, "\n");
4294 remove_phi_node (&gsi, false);
4296 if (!useless_type_conversion_p (TREE_TYPE (res), TREE_TYPE (sprime)))
4297 sprime = fold_convert (TREE_TYPE (res), sprime);
4298 stmt = gimple_build_assign (res, sprime);
4299 SSA_NAME_DEF_STMT (res) = stmt;
4300 if (TREE_CODE (sprime) == SSA_NAME)
4301 gimple_set_plf (SSA_NAME_DEF_STMT (sprime),
4303 gsi2 = gsi_after_labels (b);
4304 gsi_insert_before (&gsi2, stmt, GSI_NEW_STMT);
4305 /* Queue the copy for eventual removal. */
4306 VEC_safe_push (gimple, heap, to_remove, stmt);
4307 pre_stats.eliminations++;
4311 /* We cannot remove stmts during BB walk, especially not release SSA
4312 names there as this confuses the VN machinery. The stmts ending
4313 up in to_remove are either stores or simple copies. */
4314 for (i = 0; VEC_iterate (gimple, to_remove, i, stmt); ++i)
4316 tree lhs = gimple_assign_lhs (stmt);
4317 use_operand_p use_p;
4320 /* If there is a single use only, propagate the equivalency
4321 instead of keeping the copy. */
4322 if (TREE_CODE (lhs) == SSA_NAME
4323 && single_imm_use (lhs, &use_p, &use_stmt)
4324 && may_propagate_copy (USE_FROM_PTR (use_p),
4325 gimple_assign_rhs1 (stmt)))
4327 SET_USE (use_p, gimple_assign_rhs1 (stmt));
4328 update_stmt (use_stmt);
4331 /* If this is a store or a now unused copy, remove it. */
4332 if (TREE_CODE (lhs) != SSA_NAME
4333 || has_zero_uses (lhs))
4335 gsi = gsi_for_stmt (stmt);
4336 unlink_stmt_vdef (stmt);
4337 gsi_remove (&gsi, true);
4338 release_defs (stmt);
4341 VEC_free (gimple, heap, to_remove);
4346 /* Borrow a bit of tree-ssa-dce.c for the moment.
4347 XXX: In 4.1, we should be able to just run a DCE pass after PRE, though
4348 this may be a bit faster, and we may want critical edges kept split. */
4350 /* If OP's defining statement has not already been determined to be necessary,
4351 mark that statement necessary. Return the stmt, if it is newly
4354 static inline gimple
4355 mark_operand_necessary (tree op)
4361 if (TREE_CODE (op) != SSA_NAME)
4364 stmt = SSA_NAME_DEF_STMT (op);
4367 if (gimple_plf (stmt, NECESSARY)
4368 || gimple_nop_p (stmt))
4371 gimple_set_plf (stmt, NECESSARY, true);
4375 /* Because we don't follow exactly the standard PRE algorithm, and decide not
4376 to insert PHI nodes sometimes, and because value numbering of casts isn't
4377 perfect, we sometimes end up inserting dead code. This simple DCE-like
4378 pass removes any insertions we made that weren't actually used. */
4381 remove_dead_inserted_code (void)
4383 VEC(gimple,heap) *worklist = NULL;
4387 worklist = VEC_alloc (gimple, heap, VEC_length (gimple, inserted_exprs));
4388 for (i = 0; VEC_iterate (gimple, inserted_exprs, i, t); i++)
4390 if (gimple_plf (t, NECESSARY))
4391 VEC_quick_push (gimple, worklist, t);
4393 while (VEC_length (gimple, worklist) > 0)
4395 t = VEC_pop (gimple, worklist);
4397 /* PHI nodes are somewhat special in that each PHI alternative has
4398 data and control dependencies. All the statements feeding the
4399 PHI node's arguments are always necessary. */
4400 if (gimple_code (t) == GIMPLE_PHI)
4404 VEC_reserve (gimple, heap, worklist, gimple_phi_num_args (t));
4405 for (k = 0; k < gimple_phi_num_args (t); k++)
4407 tree arg = PHI_ARG_DEF (t, k);
4408 if (TREE_CODE (arg) == SSA_NAME)
4410 gimple n = mark_operand_necessary (arg);
4412 VEC_quick_push (gimple, worklist, n);
4418 /* Propagate through the operands. Examine all the USE, VUSE and
4419 VDEF operands in this statement. Mark all the statements
4420 which feed this statement's uses as necessary. */
4424 /* The operands of VDEF expressions are also needed as they
4425 represent potential definitions that may reach this
4426 statement (VDEF operands allow us to follow def-def
4429 FOR_EACH_SSA_TREE_OPERAND (use, t, iter, SSA_OP_ALL_USES)
4431 gimple n = mark_operand_necessary (use);
4433 VEC_safe_push (gimple, heap, worklist, n);
4438 for (i = 0; VEC_iterate (gimple, inserted_exprs, i, t); i++)
4440 if (!gimple_plf (t, NECESSARY))
4442 gimple_stmt_iterator gsi;
4444 if (dump_file && (dump_flags & TDF_DETAILS))
4446 fprintf (dump_file, "Removing unnecessary insertion:");
4447 print_gimple_stmt (dump_file, t, 0, 0);
4450 gsi = gsi_for_stmt (t);
4451 if (gimple_code (t) == GIMPLE_PHI)
4452 remove_phi_node (&gsi, true);
4455 gsi_remove (&gsi, true);
4460 VEC_free (gimple, heap, worklist);
4463 /* Initialize data structures used by PRE. */
4466 init_pre (bool do_fre)
4470 next_expression_id = 1;
4472 VEC_safe_push (pre_expr, heap, expressions, NULL);
4473 value_expressions = VEC_alloc (bitmap_set_t, heap, get_max_value_id () + 1);
4474 VEC_safe_grow_cleared (bitmap_set_t, heap, value_expressions,
4475 get_max_value_id() + 1);
4479 inserted_exprs = NULL;
4480 need_creation = NULL;
4481 pretemp = NULL_TREE;
4482 storetemp = NULL_TREE;
4483 prephitemp = NULL_TREE;
4485 connect_infinite_loops_to_exit ();
4486 memset (&pre_stats, 0, sizeof (pre_stats));
4489 postorder = XNEWVEC (int, n_basic_blocks - NUM_FIXED_BLOCKS);
4490 post_order_compute (postorder, false, false);
4493 bb->aux = XCNEWVEC (struct bb_bitmap_sets, 1);
4495 calculate_dominance_info (CDI_POST_DOMINATORS);
4496 calculate_dominance_info (CDI_DOMINATORS);
4498 bitmap_obstack_initialize (&grand_bitmap_obstack);
4499 inserted_phi_names = BITMAP_ALLOC (&grand_bitmap_obstack);
4500 phi_translate_table = htab_create (5110, expr_pred_trans_hash,
4501 expr_pred_trans_eq, free);
4502 expression_to_id = htab_create (num_ssa_names * 3,
4505 bitmap_set_pool = create_alloc_pool ("Bitmap sets",
4506 sizeof (struct bitmap_set), 30);
4507 pre_expr_pool = create_alloc_pool ("pre_expr nodes",
4508 sizeof (struct pre_expr_d), 30);
4511 EXP_GEN (bb) = bitmap_set_new ();
4512 PHI_GEN (bb) = bitmap_set_new ();
4513 TMP_GEN (bb) = bitmap_set_new ();
4514 AVAIL_OUT (bb) = bitmap_set_new ();
4517 need_eh_cleanup = BITMAP_ALLOC (NULL);
4521 /* Deallocate data structures used by PRE. */
4524 fini_pre (bool do_fre)
4529 VEC_free (bitmap_set_t, heap, value_expressions);
4530 VEC_free (gimple, heap, inserted_exprs);
4531 VEC_free (gimple, heap, need_creation);
4532 bitmap_obstack_release (&grand_bitmap_obstack);
4533 free_alloc_pool (bitmap_set_pool);
4534 free_alloc_pool (pre_expr_pool);
4535 htab_delete (phi_translate_table);
4536 htab_delete (expression_to_id);
4544 free_dominance_info (CDI_POST_DOMINATORS);
4546 if (!bitmap_empty_p (need_eh_cleanup))
4548 gimple_purge_all_dead_eh_edges (need_eh_cleanup);
4549 cleanup_tree_cfg ();
4552 BITMAP_FREE (need_eh_cleanup);
4555 loop_optimizer_finalize ();
4558 /* Main entry point to the SSA-PRE pass. DO_FRE is true if the caller
4559 only wants to do full redundancy elimination. */
4562 execute_pre (bool do_fre)
4564 unsigned int todo = 0;
4566 do_partial_partial = optimize > 2 && optimize_function_for_speed_p (cfun);
4568 /* This has to happen before SCCVN runs because
4569 loop_optimizer_init may create new phis, etc. */
4571 loop_optimizer_init (LOOPS_NORMAL);
4573 if (!run_scc_vn (do_fre))
4577 remove_dead_inserted_code ();
4578 loop_optimizer_finalize ();
4587 /* Collect and value number expressions computed in each basic block. */
4590 if (dump_file && (dump_flags & TDF_DETAILS))
4596 print_bitmap_set (dump_file, EXP_GEN (bb), "exp_gen", bb->index);
4597 print_bitmap_set (dump_file, PHI_GEN (bb), "phi_gen", bb->index);
4598 print_bitmap_set (dump_file, TMP_GEN (bb), "tmp_gen", bb->index);
4599 print_bitmap_set (dump_file, AVAIL_OUT (bb), "avail_out", bb->index);
4603 /* Insert can get quite slow on an incredibly large number of basic
4604 blocks due to some quadratic behavior. Until this behavior is
4605 fixed, don't run it when he have an incredibly large number of
4606 bb's. If we aren't going to run insert, there is no point in
4607 computing ANTIC, either, even though it's plenty fast. */
4608 if (!do_fre && n_basic_blocks < 4000)
4614 /* Remove all the redundant expressions. */
4615 todo |= eliminate ();
4617 statistics_counter_event (cfun, "Insertions", pre_stats.insertions);
4618 statistics_counter_event (cfun, "PA inserted", pre_stats.pa_insert);
4619 statistics_counter_event (cfun, "New PHIs", pre_stats.phis);
4620 statistics_counter_event (cfun, "Eliminated", pre_stats.eliminations);
4621 statistics_counter_event (cfun, "Constified", pre_stats.constified);
4623 /* Make sure to remove fake edges before committing our inserts.
4624 This makes sure we don't end up with extra critical edges that
4625 we would need to split. */
4626 remove_fake_exit_edges ();
4627 gsi_commit_edge_inserts ();
4629 clear_expression_ids ();
4632 remove_dead_inserted_code ();
4640 /* Gate and execute functions for PRE. */
4645 return execute_pre (false);
4651 return flag_tree_pre != 0;
4654 struct gimple_opt_pass pass_pre =
4659 gate_pre, /* gate */
4660 do_pre, /* execute */
4663 0, /* static_pass_number */
4664 TV_TREE_PRE, /* tv_id */
4665 PROP_no_crit_edges | PROP_cfg
4666 | PROP_ssa, /* properties_required */
4667 0, /* properties_provided */
4668 0, /* properties_destroyed */
4669 TODO_rebuild_alias, /* todo_flags_start */
4670 TODO_update_ssa_only_virtuals | TODO_dump_func | TODO_ggc_collect
4671 | TODO_verify_ssa /* todo_flags_finish */
4676 /* Gate and execute functions for FRE. */
4681 return execute_pre (true);
4687 return flag_tree_fre != 0;
4690 struct gimple_opt_pass pass_fre =
4695 gate_fre, /* gate */
4696 execute_fre, /* execute */
4699 0, /* static_pass_number */
4700 TV_TREE_FRE, /* tv_id */
4701 PROP_cfg | PROP_ssa, /* properties_required */
4702 0, /* properties_provided */
4703 0, /* properties_destroyed */
4704 0, /* todo_flags_start */
4705 TODO_dump_func | TODO_ggc_collect | TODO_verify_ssa /* todo_flags_finish */