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 SSA_NAME_VERSION (PRE_EXPR_NAME (e));
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 struct pre_expr_d expr;
313 unsigned int result_id;
317 PRE_EXPR_NAME (&expr) = name;
318 result_id = lookup_expression_id (&expr);
320 return expression_for_id (result_id);
322 result = (pre_expr) pool_alloc (pre_expr_pool);
324 PRE_EXPR_NAME (result) = name;
325 alloc_expression_id (result);
329 static bool in_fre = false;
331 /* An unordered bitmap set. One bitmap tracks values, the other,
333 typedef struct bitmap_set
339 #define FOR_EACH_EXPR_ID_IN_SET(set, id, bi) \
340 EXECUTE_IF_SET_IN_BITMAP((set)->expressions, 0, (id), (bi))
342 #define FOR_EACH_VALUE_ID_IN_SET(set, id, bi) \
343 EXECUTE_IF_SET_IN_BITMAP((set)->values, 0, (id), (bi))
345 /* Mapping from value id to expressions with that value_id. */
346 DEF_VEC_P (bitmap_set_t);
347 DEF_VEC_ALLOC_P (bitmap_set_t, heap);
348 static VEC(bitmap_set_t, heap) *value_expressions;
350 /* Sets that we need to keep track of. */
351 typedef struct bb_bitmap_sets
353 /* The EXP_GEN set, which represents expressions/values generated in
355 bitmap_set_t exp_gen;
357 /* The PHI_GEN set, which represents PHI results generated in a
359 bitmap_set_t phi_gen;
361 /* The TMP_GEN set, which represents results/temporaries generated
362 in a basic block. IE the LHS of an expression. */
363 bitmap_set_t tmp_gen;
365 /* The AVAIL_OUT set, which represents which values are available in
366 a given basic block. */
367 bitmap_set_t avail_out;
369 /* The ANTIC_IN set, which represents which values are anticipatable
370 in a given basic block. */
371 bitmap_set_t antic_in;
373 /* The PA_IN set, which represents which values are
374 partially anticipatable in a given basic block. */
377 /* The NEW_SETS set, which is used during insertion to augment the
378 AVAIL_OUT set of blocks with the new insertions performed during
379 the current iteration. */
380 bitmap_set_t new_sets;
382 /* A cache for value_dies_in_block_x. */
385 /* True if we have visited this block during ANTIC calculation. */
386 unsigned int visited : 1;
388 /* True we have deferred processing this block during ANTIC
389 calculation until its successor is processed. */
390 unsigned int deferred : 1;
392 /* True when the block contains a call that might not return. */
393 unsigned int contains_may_not_return_call : 1;
396 #define EXP_GEN(BB) ((bb_value_sets_t) ((BB)->aux))->exp_gen
397 #define PHI_GEN(BB) ((bb_value_sets_t) ((BB)->aux))->phi_gen
398 #define TMP_GEN(BB) ((bb_value_sets_t) ((BB)->aux))->tmp_gen
399 #define AVAIL_OUT(BB) ((bb_value_sets_t) ((BB)->aux))->avail_out
400 #define ANTIC_IN(BB) ((bb_value_sets_t) ((BB)->aux))->antic_in
401 #define PA_IN(BB) ((bb_value_sets_t) ((BB)->aux))->pa_in
402 #define NEW_SETS(BB) ((bb_value_sets_t) ((BB)->aux))->new_sets
403 #define EXPR_DIES(BB) ((bb_value_sets_t) ((BB)->aux))->expr_dies
404 #define BB_VISITED(BB) ((bb_value_sets_t) ((BB)->aux))->visited
405 #define BB_DEFERRED(BB) ((bb_value_sets_t) ((BB)->aux))->deferred
406 #define BB_MAY_NOTRETURN(BB) ((bb_value_sets_t) ((BB)->aux))->contains_may_not_return_call
409 /* Basic block list in postorder. */
410 static int *postorder;
412 /* This structure is used to keep track of statistics on what
413 optimization PRE was able to perform. */
416 /* The number of RHS computations eliminated by PRE. */
419 /* The number of new expressions/temporaries generated by PRE. */
422 /* The number of inserts found due to partial anticipation */
425 /* The number of new PHI nodes added by PRE. */
428 /* The number of values found constant. */
433 static bool do_partial_partial;
434 static pre_expr bitmap_find_leader (bitmap_set_t, unsigned int, gimple);
435 static void bitmap_value_insert_into_set (bitmap_set_t, pre_expr);
436 static void bitmap_value_replace_in_set (bitmap_set_t, pre_expr);
437 static void bitmap_set_copy (bitmap_set_t, bitmap_set_t);
438 static bool bitmap_set_contains_value (bitmap_set_t, unsigned int);
439 static void bitmap_insert_into_set (bitmap_set_t, pre_expr);
440 static void bitmap_insert_into_set_1 (bitmap_set_t, pre_expr,
442 static bitmap_set_t bitmap_set_new (void);
443 static tree create_expression_by_pieces (basic_block, pre_expr, gimple_seq *,
445 static tree find_or_generate_expression (basic_block, pre_expr, gimple_seq *,
447 static unsigned int get_expr_value_id (pre_expr);
449 /* We can add and remove elements and entries to and from sets
450 and hash tables, so we use alloc pools for them. */
452 static alloc_pool bitmap_set_pool;
453 static bitmap_obstack grand_bitmap_obstack;
455 /* To avoid adding 300 temporary variables when we only need one, we
456 only create one temporary variable, on demand, and build ssa names
457 off that. We do have to change the variable if the types don't
458 match the current variable's type. */
460 static tree storetemp;
461 static tree prephitemp;
463 /* Set of blocks with statements that have had its EH information
465 static bitmap need_eh_cleanup;
467 /* The phi_translate_table caches phi translations for a given
468 expression and predecessor. */
470 static htab_t phi_translate_table;
472 /* A three tuple {e, pred, v} used to cache phi translations in the
473 phi_translate_table. */
475 typedef struct expr_pred_trans_d
477 /* The expression. */
480 /* The predecessor block along which we translated the expression. */
483 /* The value that resulted from the translation. */
486 /* The hashcode for the expression, pred pair. This is cached for
489 } *expr_pred_trans_t;
490 typedef const struct expr_pred_trans_d *const_expr_pred_trans_t;
492 /* Return the hash value for a phi translation table entry. */
495 expr_pred_trans_hash (const void *p)
497 const_expr_pred_trans_t const ve = (const_expr_pred_trans_t) p;
501 /* Return true if two phi translation table entries are the same.
502 P1 and P2 should point to the expr_pred_trans_t's to be compared.*/
505 expr_pred_trans_eq (const void *p1, const void *p2)
507 const_expr_pred_trans_t const ve1 = (const_expr_pred_trans_t) p1;
508 const_expr_pred_trans_t const ve2 = (const_expr_pred_trans_t) p2;
509 basic_block b1 = ve1->pred;
510 basic_block b2 = ve2->pred;
512 /* If they are not translations for the same basic block, they can't
516 return pre_expr_eq (ve1->e, ve2->e);
519 /* Search in the phi translation table for the translation of
520 expression E in basic block PRED.
521 Return the translated value, if found, NULL otherwise. */
523 static inline pre_expr
524 phi_trans_lookup (pre_expr e, basic_block pred)
527 struct expr_pred_trans_d ept;
531 ept.hashcode = iterative_hash_hashval_t (pre_expr_hash (e), pred->index);
532 slot = htab_find_slot_with_hash (phi_translate_table, &ept, ept.hashcode,
537 return ((expr_pred_trans_t) *slot)->v;
541 /* Add the tuple mapping from {expression E, basic block PRED} to
542 value V, to the phi translation table. */
545 phi_trans_add (pre_expr e, pre_expr v, basic_block pred)
548 expr_pred_trans_t new_pair = XNEW (struct expr_pred_trans_d);
550 new_pair->pred = pred;
552 new_pair->hashcode = iterative_hash_hashval_t (pre_expr_hash (e),
555 slot = htab_find_slot_with_hash (phi_translate_table, new_pair,
556 new_pair->hashcode, INSERT);
559 *slot = (void *) new_pair;
563 /* Add expression E to the expression set of value id V. */
566 add_to_value (unsigned int v, pre_expr e)
570 gcc_assert (get_expr_value_id (e) == v);
572 if (v >= VEC_length (bitmap_set_t, value_expressions))
574 VEC_safe_grow_cleared (bitmap_set_t, heap, value_expressions,
578 set = VEC_index (bitmap_set_t, value_expressions, v);
581 set = bitmap_set_new ();
582 VEC_replace (bitmap_set_t, value_expressions, v, set);
585 bitmap_insert_into_set_1 (set, e, v, true);
588 /* Create a new bitmap set and return it. */
591 bitmap_set_new (void)
593 bitmap_set_t ret = (bitmap_set_t) pool_alloc (bitmap_set_pool);
594 ret->expressions = BITMAP_ALLOC (&grand_bitmap_obstack);
595 ret->values = BITMAP_ALLOC (&grand_bitmap_obstack);
599 /* Return the value id for a PRE expression EXPR. */
602 get_expr_value_id (pre_expr expr)
609 id = get_constant_value_id (PRE_EXPR_CONSTANT (expr));
612 id = get_or_alloc_constant_value_id (PRE_EXPR_CONSTANT (expr));
613 add_to_value (id, expr);
618 return VN_INFO (PRE_EXPR_NAME (expr))->value_id;
620 return PRE_EXPR_NARY (expr)->value_id;
622 return PRE_EXPR_REFERENCE (expr)->value_id;
628 /* Remove an expression EXPR from a bitmapped set. */
631 bitmap_remove_from_set (bitmap_set_t set, pre_expr expr)
633 unsigned int val = get_expr_value_id (expr);
634 if (!value_id_constant_p (val))
636 bitmap_clear_bit (set->values, val);
637 bitmap_clear_bit (set->expressions, get_expression_id (expr));
642 bitmap_insert_into_set_1 (bitmap_set_t set, pre_expr expr,
643 unsigned int val, bool allow_constants)
645 if (allow_constants || !value_id_constant_p (val))
647 /* We specifically expect this and only this function to be able to
648 insert constants into a set. */
649 bitmap_set_bit (set->values, val);
650 bitmap_set_bit (set->expressions, get_or_alloc_expression_id (expr));
654 /* Insert an expression EXPR into a bitmapped set. */
657 bitmap_insert_into_set (bitmap_set_t set, pre_expr expr)
659 bitmap_insert_into_set_1 (set, expr, get_expr_value_id (expr), false);
662 /* Copy a bitmapped set ORIG, into bitmapped set DEST. */
665 bitmap_set_copy (bitmap_set_t dest, bitmap_set_t orig)
667 bitmap_copy (dest->expressions, orig->expressions);
668 bitmap_copy (dest->values, orig->values);
672 /* Free memory used up by SET. */
674 bitmap_set_free (bitmap_set_t set)
676 BITMAP_FREE (set->expressions);
677 BITMAP_FREE (set->values);
681 /* Generate an topological-ordered array of bitmap set SET. */
683 static VEC(pre_expr, heap) *
684 sorted_array_from_bitmap_set (bitmap_set_t set)
687 bitmap_iterator bi, bj;
688 VEC(pre_expr, heap) *result;
690 /* Pre-allocate roughly enough space for the array. */
691 result = VEC_alloc (pre_expr, heap, bitmap_count_bits (set->values));
693 FOR_EACH_VALUE_ID_IN_SET (set, i, bi)
695 /* The number of expressions having a given value is usually
696 relatively small. Thus, rather than making a vector of all
697 the expressions and sorting it by value-id, we walk the values
698 and check in the reverse mapping that tells us what expressions
699 have a given value, to filter those in our set. As a result,
700 the expressions are inserted in value-id order, which means
703 If this is somehow a significant lose for some cases, we can
704 choose which set to walk based on the set size. */
705 bitmap_set_t exprset = VEC_index (bitmap_set_t, value_expressions, i);
706 FOR_EACH_EXPR_ID_IN_SET (exprset, j, bj)
708 if (bitmap_bit_p (set->expressions, j))
709 VEC_safe_push (pre_expr, heap, result, expression_for_id (j));
716 /* Perform bitmapped set operation DEST &= ORIG. */
719 bitmap_set_and (bitmap_set_t dest, bitmap_set_t orig)
726 bitmap temp = BITMAP_ALLOC (&grand_bitmap_obstack);
728 bitmap_and_into (dest->values, orig->values);
729 bitmap_copy (temp, dest->expressions);
730 EXECUTE_IF_SET_IN_BITMAP (temp, 0, i, bi)
732 pre_expr expr = expression_for_id (i);
733 unsigned int value_id = get_expr_value_id (expr);
734 if (!bitmap_bit_p (dest->values, value_id))
735 bitmap_clear_bit (dest->expressions, i);
741 /* Subtract all values and expressions contained in ORIG from DEST. */
744 bitmap_set_subtract (bitmap_set_t dest, bitmap_set_t orig)
746 bitmap_set_t result = bitmap_set_new ();
750 bitmap_and_compl (result->expressions, dest->expressions,
753 FOR_EACH_EXPR_ID_IN_SET (result, i, bi)
755 pre_expr expr = expression_for_id (i);
756 unsigned int value_id = get_expr_value_id (expr);
757 bitmap_set_bit (result->values, value_id);
763 /* Subtract all the values in bitmap set B from bitmap set A. */
766 bitmap_set_subtract_values (bitmap_set_t a, bitmap_set_t b)
770 bitmap temp = BITMAP_ALLOC (&grand_bitmap_obstack);
772 bitmap_copy (temp, a->expressions);
773 EXECUTE_IF_SET_IN_BITMAP (temp, 0, i, bi)
775 pre_expr expr = expression_for_id (i);
776 if (bitmap_set_contains_value (b, get_expr_value_id (expr)))
777 bitmap_remove_from_set (a, expr);
783 /* Return true if bitmapped set SET contains the value VALUE_ID. */
786 bitmap_set_contains_value (bitmap_set_t set, unsigned int value_id)
788 if (value_id_constant_p (value_id))
791 if (!set || bitmap_empty_p (set->expressions))
794 return bitmap_bit_p (set->values, value_id);
798 bitmap_set_contains_expr (bitmap_set_t set, const pre_expr expr)
800 return bitmap_bit_p (set->expressions, get_expression_id (expr));
803 /* Replace an instance of value LOOKFOR with expression EXPR in SET. */
806 bitmap_set_replace_value (bitmap_set_t set, unsigned int lookfor,
809 bitmap_set_t exprset;
813 if (value_id_constant_p (lookfor))
816 if (!bitmap_set_contains_value (set, lookfor))
819 /* The number of expressions having a given value is usually
820 significantly less than the total number of expressions in SET.
821 Thus, rather than check, for each expression in SET, whether it
822 has the value LOOKFOR, we walk the reverse mapping that tells us
823 what expressions have a given value, and see if any of those
824 expressions are in our set. For large testcases, this is about
825 5-10x faster than walking the bitmap. If this is somehow a
826 significant lose for some cases, we can choose which set to walk
827 based on the set size. */
828 exprset = VEC_index (bitmap_set_t, value_expressions, lookfor);
829 FOR_EACH_EXPR_ID_IN_SET (exprset, i, bi)
831 if (bitmap_bit_p (set->expressions, i))
833 bitmap_clear_bit (set->expressions, i);
834 bitmap_set_bit (set->expressions, get_expression_id (expr));
840 /* Return true if two bitmap sets are equal. */
843 bitmap_set_equal (bitmap_set_t a, bitmap_set_t b)
845 return bitmap_equal_p (a->values, b->values);
848 /* Replace an instance of EXPR's VALUE with EXPR in SET if it exists,
849 and add it otherwise. */
852 bitmap_value_replace_in_set (bitmap_set_t set, pre_expr expr)
854 unsigned int val = get_expr_value_id (expr);
856 if (bitmap_set_contains_value (set, val))
857 bitmap_set_replace_value (set, val, expr);
859 bitmap_insert_into_set (set, expr);
862 /* Insert EXPR into SET if EXPR's value is not already present in
866 bitmap_value_insert_into_set (bitmap_set_t set, pre_expr expr)
868 unsigned int val = get_expr_value_id (expr);
870 if (!bitmap_set_contains_value (set, val))
871 bitmap_insert_into_set_1 (set, expr, val, false);
874 /* Print out EXPR to outfile. */
877 print_pre_expr (FILE *outfile, const pre_expr expr)
882 print_generic_expr (outfile, PRE_EXPR_CONSTANT (expr), 0);
885 print_generic_expr (outfile, PRE_EXPR_NAME (expr), 0);
890 vn_nary_op_t nary = PRE_EXPR_NARY (expr);
891 fprintf (outfile, "{%s,", tree_code_name [nary->opcode]);
892 for (i = 0; i < nary->length; i++)
894 print_generic_expr (outfile, nary->op[i], 0);
895 if (i != (unsigned) nary->length - 1)
896 fprintf (outfile, ",");
898 fprintf (outfile, "}");
904 vn_reference_op_t vro;
906 vn_reference_t ref = PRE_EXPR_REFERENCE (expr);
907 fprintf (outfile, "{");
909 VEC_iterate (vn_reference_op_s, ref->operands, i, vro);
912 bool closebrace = false;
913 if (vro->opcode != SSA_NAME
914 && TREE_CODE_CLASS (vro->opcode) != tcc_declaration)
916 fprintf (outfile, "%s", tree_code_name [vro->opcode]);
919 fprintf (outfile, "<");
925 print_generic_expr (outfile, vro->op0, 0);
928 fprintf (outfile, ",");
929 print_generic_expr (outfile, vro->op1, 0);
933 fprintf (outfile, ",");
934 print_generic_expr (outfile, vro->op2, 0);
938 fprintf (outfile, ">");
939 if (i != VEC_length (vn_reference_op_s, ref->operands) - 1)
940 fprintf (outfile, ",");
942 fprintf (outfile, "}");
945 fprintf (outfile, "@");
946 print_generic_expr (outfile, ref->vuse, 0);
952 void debug_pre_expr (pre_expr);
954 /* Like print_pre_expr but always prints to stderr. */
956 debug_pre_expr (pre_expr e)
958 print_pre_expr (stderr, e);
959 fprintf (stderr, "\n");
962 /* Print out SET to OUTFILE. */
965 print_bitmap_set (FILE *outfile, bitmap_set_t set,
966 const char *setname, int blockindex)
968 fprintf (outfile, "%s[%d] := { ", setname, blockindex);
975 FOR_EACH_EXPR_ID_IN_SET (set, i, bi)
977 const pre_expr expr = expression_for_id (i);
980 fprintf (outfile, ", ");
982 print_pre_expr (outfile, expr);
984 fprintf (outfile, " (%04d)", get_expr_value_id (expr));
987 fprintf (outfile, " }\n");
990 void debug_bitmap_set (bitmap_set_t);
993 debug_bitmap_set (bitmap_set_t set)
995 print_bitmap_set (stderr, set, "debug", 0);
998 /* Print out the expressions that have VAL to OUTFILE. */
1001 print_value_expressions (FILE *outfile, unsigned int val)
1003 bitmap_set_t set = VEC_index (bitmap_set_t, value_expressions, val);
1007 sprintf (s, "%04d", val);
1008 print_bitmap_set (outfile, set, s, 0);
1014 debug_value_expressions (unsigned int val)
1016 print_value_expressions (stderr, val);
1019 /* Given a CONSTANT, allocate a new CONSTANT type PRE_EXPR to
1023 get_or_alloc_expr_for_constant (tree constant)
1025 unsigned int result_id;
1026 unsigned int value_id;
1027 struct pre_expr_d expr;
1030 expr.kind = CONSTANT;
1031 PRE_EXPR_CONSTANT (&expr) = constant;
1032 result_id = lookup_expression_id (&expr);
1034 return expression_for_id (result_id);
1036 newexpr = (pre_expr) pool_alloc (pre_expr_pool);
1037 newexpr->kind = CONSTANT;
1038 PRE_EXPR_CONSTANT (newexpr) = constant;
1039 alloc_expression_id (newexpr);
1040 value_id = get_or_alloc_constant_value_id (constant);
1041 add_to_value (value_id, newexpr);
1045 /* Given a value id V, find the actual tree representing the constant
1046 value if there is one, and return it. Return NULL if we can't find
1050 get_constant_for_value_id (unsigned int v)
1052 if (value_id_constant_p (v))
1056 bitmap_set_t exprset = VEC_index (bitmap_set_t, value_expressions, v);
1058 FOR_EACH_EXPR_ID_IN_SET (exprset, i, bi)
1060 pre_expr expr = expression_for_id (i);
1061 if (expr->kind == CONSTANT)
1062 return PRE_EXPR_CONSTANT (expr);
1068 /* Get or allocate a pre_expr for a piece of GIMPLE, and return it.
1069 Currently only supports constants and SSA_NAMES. */
1071 get_or_alloc_expr_for (tree t)
1073 if (TREE_CODE (t) == SSA_NAME)
1074 return get_or_alloc_expr_for_name (t);
1075 else if (is_gimple_min_invariant (t))
1076 return get_or_alloc_expr_for_constant (t);
1079 /* More complex expressions can result from SCCVN expression
1080 simplification that inserts values for them. As they all
1081 do not have VOPs the get handled by the nary ops struct. */
1082 vn_nary_op_t result;
1083 unsigned int result_id;
1084 vn_nary_op_lookup (t, &result);
1087 pre_expr e = (pre_expr) pool_alloc (pre_expr_pool);
1089 PRE_EXPR_NARY (e) = result;
1090 result_id = lookup_expression_id (e);
1093 pool_free (pre_expr_pool, e);
1094 e = expression_for_id (result_id);
1097 alloc_expression_id (e);
1104 /* Return the folded version of T if T, when folded, is a gimple
1105 min_invariant. Otherwise, return T. */
1108 fully_constant_expression (pre_expr e)
1116 vn_nary_op_t nary = PRE_EXPR_NARY (e);
1117 switch (TREE_CODE_CLASS (nary->opcode))
1119 case tcc_expression:
1120 if (nary->opcode == TRUTH_NOT_EXPR)
1122 if (nary->opcode != TRUTH_AND_EXPR
1123 && nary->opcode != TRUTH_OR_EXPR
1124 && nary->opcode != TRUTH_XOR_EXPR)
1128 case tcc_comparison:
1130 /* We have to go from trees to pre exprs to value ids to
1132 tree naryop0 = nary->op[0];
1133 tree naryop1 = nary->op[1];
1135 if (!is_gimple_min_invariant (naryop0))
1137 pre_expr rep0 = get_or_alloc_expr_for (naryop0);
1138 unsigned int vrep0 = get_expr_value_id (rep0);
1139 tree const0 = get_constant_for_value_id (vrep0);
1141 naryop0 = fold_convert (TREE_TYPE (naryop0), const0);
1143 if (!is_gimple_min_invariant (naryop1))
1145 pre_expr rep1 = get_or_alloc_expr_for (naryop1);
1146 unsigned int vrep1 = get_expr_value_id (rep1);
1147 tree const1 = get_constant_for_value_id (vrep1);
1149 naryop1 = fold_convert (TREE_TYPE (naryop1), const1);
1151 result = fold_binary (nary->opcode, nary->type,
1153 if (result && is_gimple_min_invariant (result))
1154 return get_or_alloc_expr_for_constant (result);
1155 /* We might have simplified the expression to a
1156 SSA_NAME for example from x_1 * 1. But we cannot
1157 insert a PHI for x_1 unconditionally as x_1 might
1158 not be available readily. */
1162 if (nary->opcode != REALPART_EXPR
1163 && nary->opcode != IMAGPART_EXPR
1164 && nary->opcode != VIEW_CONVERT_EXPR)
1170 /* We have to go from trees to pre exprs to value ids to
1172 tree naryop0 = nary->op[0];
1173 tree const0, result;
1174 if (is_gimple_min_invariant (naryop0))
1178 pre_expr rep0 = get_or_alloc_expr_for (naryop0);
1179 unsigned int vrep0 = get_expr_value_id (rep0);
1180 const0 = get_constant_for_value_id (vrep0);
1185 tree type1 = TREE_TYPE (nary->op[0]);
1186 const0 = fold_convert (type1, const0);
1187 result = fold_unary (nary->opcode, nary->type, const0);
1189 if (result && is_gimple_min_invariant (result))
1190 return get_or_alloc_expr_for_constant (result);
1199 vn_reference_t ref = PRE_EXPR_REFERENCE (e);
1200 VEC (vn_reference_op_s, heap) *operands = ref->operands;
1201 vn_reference_op_t op;
1203 /* Try to simplify the translated expression if it is
1204 a call to a builtin function with at most two arguments. */
1205 op = VEC_index (vn_reference_op_s, operands, 0);
1206 if (op->opcode == CALL_EXPR
1207 && TREE_CODE (op->op0) == ADDR_EXPR
1208 && TREE_CODE (TREE_OPERAND (op->op0, 0)) == FUNCTION_DECL
1209 && DECL_BUILT_IN (TREE_OPERAND (op->op0, 0))
1210 && VEC_length (vn_reference_op_s, operands) >= 2
1211 && VEC_length (vn_reference_op_s, operands) <= 3)
1213 vn_reference_op_t arg0, arg1 = NULL;
1214 bool anyconst = false;
1215 arg0 = VEC_index (vn_reference_op_s, operands, 1);
1216 if (VEC_length (vn_reference_op_s, operands) > 2)
1217 arg1 = VEC_index (vn_reference_op_s, operands, 2);
1218 if (TREE_CODE_CLASS (arg0->opcode) == tcc_constant
1219 || (arg0->opcode == ADDR_EXPR
1220 && is_gimple_min_invariant (arg0->op0)))
1223 && (TREE_CODE_CLASS (arg1->opcode) == tcc_constant
1224 || (arg1->opcode == ADDR_EXPR
1225 && is_gimple_min_invariant (arg1->op0))))
1229 tree folded = build_call_expr (TREE_OPERAND (op->op0, 0),
1232 arg1 ? arg1->op0 : NULL);
1234 && TREE_CODE (folded) == NOP_EXPR)
1235 folded = TREE_OPERAND (folded, 0);
1237 && is_gimple_min_invariant (folded))
1238 return get_or_alloc_expr_for_constant (folded);
1249 /* Translate the VUSE backwards through phi nodes in PHIBLOCK, so that
1250 it has the value it would have in BLOCK. Set *SAME_VALID to true
1251 in case the new vuse doesn't change the value id of the OPERANDS. */
1254 translate_vuse_through_block (VEC (vn_reference_op_s, heap) *operands,
1255 alias_set_type set, tree type, tree vuse,
1256 basic_block phiblock,
1257 basic_block block, bool *same_valid)
1259 gimple phi = SSA_NAME_DEF_STMT (vuse);
1266 if (gimple_bb (phi) != phiblock)
1269 use_oracle = ao_ref_init_from_vn_reference (&ref, set, type, operands);
1271 /* Use the alias-oracle to find either the PHI node in this block,
1272 the first VUSE used in this block that is equivalent to vuse or
1273 the first VUSE which definition in this block kills the value. */
1274 if (gimple_code (phi) == GIMPLE_PHI)
1275 e = find_edge (block, phiblock);
1276 else if (use_oracle)
1277 while (!stmt_may_clobber_ref_p_1 (phi, &ref))
1279 vuse = gimple_vuse (phi);
1280 phi = SSA_NAME_DEF_STMT (vuse);
1281 if (gimple_bb (phi) != phiblock)
1283 if (gimple_code (phi) == GIMPLE_PHI)
1285 e = find_edge (block, phiblock);
1296 bitmap visited = NULL;
1297 /* Try to find a vuse that dominates this phi node by skipping
1298 non-clobbering statements. */
1299 vuse = get_continuation_for_phi (phi, &ref, &visited);
1301 BITMAP_FREE (visited);
1307 /* If we didn't find any, the value ID can't stay the same,
1308 but return the translated vuse. */
1309 *same_valid = false;
1310 vuse = PHI_ARG_DEF (phi, e->dest_idx);
1312 /* ??? We would like to return vuse here as this is the canonical
1313 upmost vdef that this reference is associated with. But during
1314 insertion of the references into the hash tables we only ever
1315 directly insert with their direct gimple_vuse, hence returning
1316 something else would make us not find the other expression. */
1317 return PHI_ARG_DEF (phi, e->dest_idx);
1323 /* Like bitmap_find_leader, but checks for the value existing in SET1 *or*
1324 SET2. This is used to avoid making a set consisting of the union
1325 of PA_IN and ANTIC_IN during insert. */
1327 static inline pre_expr
1328 find_leader_in_sets (unsigned int val, bitmap_set_t set1, bitmap_set_t set2)
1332 result = bitmap_find_leader (set1, val, NULL);
1333 if (!result && set2)
1334 result = bitmap_find_leader (set2, val, NULL);
1338 /* Get the tree type for our PRE expression e. */
1341 get_expr_type (const pre_expr e)
1346 return TREE_TYPE (PRE_EXPR_NAME (e));
1348 return TREE_TYPE (PRE_EXPR_CONSTANT (e));
1350 return PRE_EXPR_REFERENCE (e)->type;
1352 return PRE_EXPR_NARY (e)->type;
1357 /* Get a representative SSA_NAME for a given expression.
1358 Since all of our sub-expressions are treated as values, we require
1359 them to be SSA_NAME's for simplicity.
1360 Prior versions of GVNPRE used to use "value handles" here, so that
1361 an expression would be VH.11 + VH.10 instead of d_3 + e_6. In
1362 either case, the operands are really values (IE we do not expect
1363 them to be usable without finding leaders). */
1366 get_representative_for (const pre_expr e)
1370 unsigned int value_id = get_expr_value_id (e);
1375 return PRE_EXPR_NAME (e);
1377 return PRE_EXPR_CONSTANT (e);
1381 /* Go through all of the expressions representing this value
1382 and pick out an SSA_NAME. */
1385 bitmap_set_t exprs = VEC_index (bitmap_set_t, value_expressions,
1387 FOR_EACH_EXPR_ID_IN_SET (exprs, i, bi)
1389 pre_expr rep = expression_for_id (i);
1390 if (rep->kind == NAME)
1391 return PRE_EXPR_NAME (rep);
1396 /* If we reached here we couldn't find an SSA_NAME. This can
1397 happen when we've discovered a value that has never appeared in
1398 the program as set to an SSA_NAME, most likely as the result of
1403 "Could not find SSA_NAME representative for expression:");
1404 print_pre_expr (dump_file, e);
1405 fprintf (dump_file, "\n");
1408 exprtype = get_expr_type (e);
1410 /* Build and insert the assignment of the end result to the temporary
1411 that we will return. */
1412 if (!pretemp || exprtype != TREE_TYPE (pretemp))
1414 pretemp = create_tmp_var (exprtype, "pretmp");
1415 get_var_ann (pretemp);
1418 name = make_ssa_name (pretemp, gimple_build_nop ());
1419 VN_INFO_GET (name)->value_id = value_id;
1420 if (e->kind == CONSTANT)
1421 VN_INFO (name)->valnum = PRE_EXPR_CONSTANT (e);
1423 VN_INFO (name)->valnum = name;
1425 add_to_value (value_id, get_or_alloc_expr_for_name (name));
1428 fprintf (dump_file, "Created SSA_NAME representative ");
1429 print_generic_expr (dump_file, name, 0);
1430 fprintf (dump_file, " for expression:");
1431 print_pre_expr (dump_file, e);
1432 fprintf (dump_file, "\n");
1441 /* Translate EXPR using phis in PHIBLOCK, so that it has the values of
1442 the phis in PRED. Return NULL if we can't find a leader for each part
1443 of the translated expression. */
1446 phi_translate (pre_expr expr, bitmap_set_t set1, bitmap_set_t set2,
1447 basic_block pred, basic_block phiblock)
1449 pre_expr oldexpr = expr;
1455 /* Constants contain no values that need translation. */
1456 if (expr->kind == CONSTANT)
1459 if (value_id_constant_p (get_expr_value_id (expr)))
1462 phitrans = phi_trans_lookup (expr, pred);
1471 bool changed = false;
1472 vn_nary_op_t nary = PRE_EXPR_NARY (expr);
1473 struct vn_nary_op_s newnary;
1474 /* The NARY structure is only guaranteed to have been
1475 allocated to the nary->length operands. */
1476 memcpy (&newnary, nary, (sizeof (struct vn_nary_op_s)
1477 - sizeof (tree) * (4 - nary->length)));
1479 for (i = 0; i < newnary.length; i++)
1481 if (TREE_CODE (newnary.op[i]) != SSA_NAME)
1485 pre_expr leader, result;
1486 unsigned int op_val_id = VN_INFO (newnary.op[i])->value_id;
1487 leader = find_leader_in_sets (op_val_id, set1, set2);
1488 result = phi_translate (leader, set1, set2, pred, phiblock);
1489 if (result && result != leader)
1491 tree name = get_representative_for (result);
1494 newnary.op[i] = name;
1499 changed |= newnary.op[i] != nary->op[i];
1505 unsigned int new_val_id;
1507 tree result = vn_nary_op_lookup_pieces (newnary.length,
1515 if (result && is_gimple_min_invariant (result))
1516 return get_or_alloc_expr_for_constant (result);
1518 expr = (pre_expr) pool_alloc (pre_expr_pool);
1523 PRE_EXPR_NARY (expr) = nary;
1524 constant = fully_constant_expression (expr);
1525 if (constant != expr)
1528 new_val_id = nary->value_id;
1529 get_or_alloc_expression_id (expr);
1533 new_val_id = get_next_value_id ();
1534 VEC_safe_grow_cleared (bitmap_set_t, heap,
1536 get_max_value_id() + 1);
1537 nary = vn_nary_op_insert_pieces (newnary.length,
1544 result, new_val_id);
1545 PRE_EXPR_NARY (expr) = nary;
1546 constant = fully_constant_expression (expr);
1547 if (constant != expr)
1549 get_or_alloc_expression_id (expr);
1551 add_to_value (new_val_id, expr);
1553 phi_trans_add (oldexpr, expr, pred);
1560 vn_reference_t ref = PRE_EXPR_REFERENCE (expr);
1561 VEC (vn_reference_op_s, heap) *operands = ref->operands;
1562 tree vuse = ref->vuse;
1563 tree newvuse = vuse;
1564 VEC (vn_reference_op_s, heap) *newoperands = NULL;
1565 bool changed = false, same_valid = true;
1567 vn_reference_op_t operand;
1568 vn_reference_t newref;
1571 VEC_iterate (vn_reference_op_s, operands, i, operand); i++, j++)
1575 tree oldop0 = operand->op0;
1576 tree oldop1 = operand->op1;
1577 tree oldop2 = operand->op2;
1581 tree type = operand->type;
1582 vn_reference_op_s newop = *operand;
1584 if (op0 && TREE_CODE (op0) == SSA_NAME)
1586 unsigned int op_val_id = VN_INFO (op0)->value_id;
1587 leader = find_leader_in_sets (op_val_id, set1, set2);
1588 opresult = phi_translate (leader, set1, set2, pred, phiblock);
1589 if (opresult && opresult != leader)
1591 tree name = get_representative_for (opresult);
1599 changed |= op0 != oldop0;
1601 if (op1 && TREE_CODE (op1) == SSA_NAME)
1603 unsigned int op_val_id = VN_INFO (op1)->value_id;
1604 leader = find_leader_in_sets (op_val_id, set1, set2);
1605 opresult = phi_translate (leader, set1, set2, pred, phiblock);
1606 if (opresult && opresult != leader)
1608 tree name = get_representative_for (opresult);
1616 /* We can't possibly insert these. */
1617 else if (op1 && !is_gimple_min_invariant (op1))
1619 changed |= op1 != oldop1;
1620 if (op2 && TREE_CODE (op2) == SSA_NAME)
1622 unsigned int op_val_id = VN_INFO (op2)->value_id;
1623 leader = find_leader_in_sets (op_val_id, set1, set2);
1624 opresult = phi_translate (leader, set1, set2, pred, phiblock);
1625 if (opresult && opresult != leader)
1627 tree name = get_representative_for (opresult);
1635 /* We can't possibly insert these. */
1636 else if (op2 && !is_gimple_min_invariant (op2))
1638 changed |= op2 != oldop2;
1641 newoperands = VEC_copy (vn_reference_op_s, heap, operands);
1642 /* We may have changed from an SSA_NAME to a constant */
1643 if (newop.opcode == SSA_NAME && TREE_CODE (op0) != SSA_NAME)
1644 newop.opcode = TREE_CODE (op0);
1649 VEC_replace (vn_reference_op_s, newoperands, j, &newop);
1650 /* If it transforms from an SSA_NAME to an address, fold with
1651 a preceding indirect reference. */
1652 if (j > 0 && op0 && TREE_CODE (op0) == ADDR_EXPR
1653 && VEC_index (vn_reference_op_s,
1654 newoperands, j - 1)->opcode == INDIRECT_REF)
1655 vn_reference_fold_indirect (&newoperands, &j);
1657 if (i != VEC_length (vn_reference_op_s, operands))
1660 VEC_free (vn_reference_op_s, heap, newoperands);
1666 newvuse = translate_vuse_through_block (newoperands,
1667 ref->set, ref->type,
1668 vuse, phiblock, pred,
1670 if (newvuse == NULL_TREE)
1672 VEC_free (vn_reference_op_s, heap, newoperands);
1677 if (changed || newvuse != vuse)
1679 unsigned int new_val_id;
1682 tree result = vn_reference_lookup_pieces (newvuse, ref->set,
1687 VEC_free (vn_reference_op_s, heap, newoperands);
1689 if (result && is_gimple_min_invariant (result))
1691 gcc_assert (!newoperands);
1692 return get_or_alloc_expr_for_constant (result);
1695 expr = (pre_expr) pool_alloc (pre_expr_pool);
1696 expr->kind = REFERENCE;
1701 PRE_EXPR_REFERENCE (expr) = newref;
1702 constant = fully_constant_expression (expr);
1703 if (constant != expr)
1706 new_val_id = newref->value_id;
1707 get_or_alloc_expression_id (expr);
1711 if (changed || !same_valid)
1713 new_val_id = get_next_value_id ();
1714 VEC_safe_grow_cleared (bitmap_set_t, heap,
1716 get_max_value_id() + 1);
1719 new_val_id = ref->value_id;
1720 newref = vn_reference_insert_pieces (newvuse, ref->set,
1723 result, new_val_id);
1725 PRE_EXPR_REFERENCE (expr) = newref;
1726 constant = fully_constant_expression (expr);
1727 if (constant != expr)
1729 get_or_alloc_expression_id (expr);
1731 add_to_value (new_val_id, expr);
1733 VEC_free (vn_reference_op_s, heap, newoperands);
1734 phi_trans_add (oldexpr, expr, pred);
1744 tree name = PRE_EXPR_NAME (expr);
1746 def_stmt = SSA_NAME_DEF_STMT (name);
1747 if (gimple_code (def_stmt) == GIMPLE_PHI
1748 && gimple_bb (def_stmt) == phiblock)
1753 e = find_edge (pred, gimple_bb (phi));
1756 tree def = PHI_ARG_DEF (phi, e->dest_idx);
1759 if (TREE_CODE (def) == SSA_NAME)
1760 def = VN_INFO (def)->valnum;
1762 /* Handle constant. */
1763 if (is_gimple_min_invariant (def))
1764 return get_or_alloc_expr_for_constant (def);
1766 if (TREE_CODE (def) == SSA_NAME && ssa_undefined_value_p (def))
1769 newexpr = get_or_alloc_expr_for_name (def);
1780 /* For each expression in SET, translate the values through phi nodes
1781 in PHIBLOCK using edge PHIBLOCK->PRED, and store the resulting
1782 expressions in DEST. */
1785 phi_translate_set (bitmap_set_t dest, bitmap_set_t set, basic_block pred,
1786 basic_block phiblock)
1788 VEC (pre_expr, heap) *exprs;
1792 if (!phi_nodes (phiblock))
1794 bitmap_set_copy (dest, set);
1798 exprs = sorted_array_from_bitmap_set (set);
1799 for (i = 0; VEC_iterate (pre_expr, exprs, i, expr); i++)
1801 pre_expr translated;
1802 translated = phi_translate (expr, set, NULL, pred, phiblock);
1804 /* Don't add empty translations to the cache */
1806 phi_trans_add (expr, translated, pred);
1808 if (translated != NULL)
1809 bitmap_value_insert_into_set (dest, translated);
1811 VEC_free (pre_expr, heap, exprs);
1814 /* Find the leader for a value (i.e., the name representing that
1815 value) in a given set, and return it. If STMT is non-NULL it
1816 makes sure the defining statement for the leader dominates it.
1817 Return NULL if no leader is found. */
1820 bitmap_find_leader (bitmap_set_t set, unsigned int val, gimple stmt)
1822 if (value_id_constant_p (val))
1826 bitmap_set_t exprset = VEC_index (bitmap_set_t, value_expressions, val);
1828 FOR_EACH_EXPR_ID_IN_SET (exprset, i, bi)
1830 pre_expr expr = expression_for_id (i);
1831 if (expr->kind == CONSTANT)
1835 if (bitmap_set_contains_value (set, val))
1837 /* Rather than walk the entire bitmap of expressions, and see
1838 whether any of them has the value we are looking for, we look
1839 at the reverse mapping, which tells us the set of expressions
1840 that have a given value (IE value->expressions with that
1841 value) and see if any of those expressions are in our set.
1842 The number of expressions per value is usually significantly
1843 less than the number of expressions in the set. In fact, for
1844 large testcases, doing it this way is roughly 5-10x faster
1845 than walking the bitmap.
1846 If this is somehow a significant lose for some cases, we can
1847 choose which set to walk based on which set is smaller. */
1850 bitmap_set_t exprset = VEC_index (bitmap_set_t, value_expressions, val);
1852 EXECUTE_IF_AND_IN_BITMAP (exprset->expressions,
1853 set->expressions, 0, i, bi)
1855 pre_expr val = expression_for_id (i);
1856 /* At the point where stmt is not null, there should always
1857 be an SSA_NAME first in the list of expressions. */
1860 gimple def_stmt = SSA_NAME_DEF_STMT (PRE_EXPR_NAME (val));
1861 if (gimple_code (def_stmt) != GIMPLE_PHI
1862 && gimple_bb (def_stmt) == gimple_bb (stmt)
1863 && gimple_uid (def_stmt) >= gimple_uid (stmt))
1872 /* Determine if EXPR, a memory expression, is ANTIC_IN at the top of
1873 BLOCK by seeing if it is not killed in the block. Note that we are
1874 only determining whether there is a store that kills it. Because
1875 of the order in which clean iterates over values, we are guaranteed
1876 that altered operands will have caused us to be eliminated from the
1877 ANTIC_IN set already. */
1880 value_dies_in_block_x (pre_expr expr, basic_block block)
1882 tree vuse = PRE_EXPR_REFERENCE (expr)->vuse;
1883 vn_reference_t refx = PRE_EXPR_REFERENCE (expr);
1885 gimple_stmt_iterator gsi;
1886 unsigned id = get_expression_id (expr);
1893 /* Lookup a previously calculated result. */
1894 if (EXPR_DIES (block)
1895 && bitmap_bit_p (EXPR_DIES (block), id * 2))
1896 return bitmap_bit_p (EXPR_DIES (block), id * 2 + 1);
1898 /* A memory expression {e, VUSE} dies in the block if there is a
1899 statement that may clobber e. If, starting statement walk from the
1900 top of the basic block, a statement uses VUSE there can be no kill
1901 inbetween that use and the original statement that loaded {e, VUSE},
1902 so we can stop walking. */
1903 ref.base = NULL_TREE;
1904 for (gsi = gsi_start_bb (block); !gsi_end_p (gsi); gsi_next (&gsi))
1906 tree def_vuse, def_vdef;
1907 def = gsi_stmt (gsi);
1908 def_vuse = gimple_vuse (def);
1909 def_vdef = gimple_vdef (def);
1911 /* Not a memory statement. */
1915 /* Not a may-def. */
1918 /* A load with the same VUSE, we're done. */
1919 if (def_vuse == vuse)
1925 /* Init ref only if we really need it. */
1926 if (ref.base == NULL_TREE
1927 && !ao_ref_init_from_vn_reference (&ref, refx->set, refx->type,
1933 /* If the statement may clobber expr, it dies. */
1934 if (stmt_may_clobber_ref_p_1 (def, &ref))
1941 /* Remember the result. */
1942 if (!EXPR_DIES (block))
1943 EXPR_DIES (block) = BITMAP_ALLOC (&grand_bitmap_obstack);
1944 bitmap_set_bit (EXPR_DIES (block), id * 2);
1946 bitmap_set_bit (EXPR_DIES (block), id * 2 + 1);
1952 #define union_contains_value(SET1, SET2, VAL) \
1953 (bitmap_set_contains_value ((SET1), (VAL)) \
1954 || ((SET2) && bitmap_set_contains_value ((SET2), (VAL))))
1956 /* Determine if vn_reference_op_t VRO is legal in SET1 U SET2.
1959 vro_valid_in_sets (bitmap_set_t set1, bitmap_set_t set2,
1960 vn_reference_op_t vro)
1962 if (vro->op0 && TREE_CODE (vro->op0) == SSA_NAME)
1964 struct pre_expr_d temp;
1967 PRE_EXPR_NAME (&temp) = vro->op0;
1968 temp.id = lookup_expression_id (&temp);
1971 if (!union_contains_value (set1, set2,
1972 get_expr_value_id (&temp)))
1975 if (vro->op1 && TREE_CODE (vro->op1) == SSA_NAME)
1977 struct pre_expr_d temp;
1980 PRE_EXPR_NAME (&temp) = vro->op1;
1981 temp.id = lookup_expression_id (&temp);
1984 if (!union_contains_value (set1, set2,
1985 get_expr_value_id (&temp)))
1989 if (vro->op2 && TREE_CODE (vro->op2) == SSA_NAME)
1991 struct pre_expr_d temp;
1994 PRE_EXPR_NAME (&temp) = vro->op2;
1995 temp.id = lookup_expression_id (&temp);
1998 if (!union_contains_value (set1, set2,
1999 get_expr_value_id (&temp)))
2006 /* Determine if the expression EXPR is valid in SET1 U SET2.
2007 ONLY SET2 CAN BE NULL.
2008 This means that we have a leader for each part of the expression
2009 (if it consists of values), or the expression is an SSA_NAME.
2010 For loads/calls, we also see if the vuse is killed in this block. */
2013 valid_in_sets (bitmap_set_t set1, bitmap_set_t set2, pre_expr expr,
2019 return bitmap_set_contains_expr (AVAIL_OUT (block), expr);
2023 vn_nary_op_t nary = PRE_EXPR_NARY (expr);
2024 for (i = 0; i < nary->length; i++)
2026 if (TREE_CODE (nary->op[i]) == SSA_NAME)
2028 struct pre_expr_d temp;
2031 PRE_EXPR_NAME (&temp) = nary->op[i];
2032 temp.id = lookup_expression_id (&temp);
2035 if (!union_contains_value (set1, set2,
2036 get_expr_value_id (&temp)))
2040 /* If the NARY may trap make sure the block does not contain
2041 a possible exit point.
2042 ??? This is overly conservative if we translate AVAIL_OUT
2043 as the available expression might be after the exit point. */
2044 if (BB_MAY_NOTRETURN (block)
2045 && vn_nary_may_trap (nary))
2052 vn_reference_t ref = PRE_EXPR_REFERENCE (expr);
2053 vn_reference_op_t vro;
2056 for (i = 0; VEC_iterate (vn_reference_op_s, ref->operands, i, vro); i++)
2058 if (!vro_valid_in_sets (set1, set2, vro))
2063 gimple def_stmt = SSA_NAME_DEF_STMT (ref->vuse);
2064 if (!gimple_nop_p (def_stmt)
2065 && gimple_bb (def_stmt) != block
2066 && !dominated_by_p (CDI_DOMINATORS,
2067 block, gimple_bb (def_stmt)))
2070 return !value_dies_in_block_x (expr, block);
2077 /* Clean the set of expressions that are no longer valid in SET1 or
2078 SET2. This means expressions that are made up of values we have no
2079 leaders for in SET1 or SET2. This version is used for partial
2080 anticipation, which means it is not valid in either ANTIC_IN or
2084 dependent_clean (bitmap_set_t set1, bitmap_set_t set2, basic_block block)
2086 VEC (pre_expr, heap) *exprs = sorted_array_from_bitmap_set (set1);
2090 for (i = 0; VEC_iterate (pre_expr, exprs, i, expr); i++)
2092 if (!valid_in_sets (set1, set2, expr, block))
2093 bitmap_remove_from_set (set1, expr);
2095 VEC_free (pre_expr, heap, exprs);
2098 /* Clean the set of expressions that are no longer valid in SET. This
2099 means expressions that are made up of values we have no leaders for
2103 clean (bitmap_set_t set, basic_block block)
2105 VEC (pre_expr, heap) *exprs = sorted_array_from_bitmap_set (set);
2109 for (i = 0; VEC_iterate (pre_expr, exprs, i, expr); i++)
2111 if (!valid_in_sets (set, NULL, expr, block))
2112 bitmap_remove_from_set (set, expr);
2114 VEC_free (pre_expr, heap, exprs);
2117 static sbitmap has_abnormal_preds;
2119 /* List of blocks that may have changed during ANTIC computation and
2120 thus need to be iterated over. */
2122 static sbitmap changed_blocks;
2124 /* Decide whether to defer a block for a later iteration, or PHI
2125 translate SOURCE to DEST using phis in PHIBLOCK. Return false if we
2126 should defer the block, and true if we processed it. */
2129 defer_or_phi_translate_block (bitmap_set_t dest, bitmap_set_t source,
2130 basic_block block, basic_block phiblock)
2132 if (!BB_VISITED (phiblock))
2134 SET_BIT (changed_blocks, block->index);
2135 BB_VISITED (block) = 0;
2136 BB_DEFERRED (block) = 1;
2140 phi_translate_set (dest, source, block, phiblock);
2144 /* Compute the ANTIC set for BLOCK.
2146 If succs(BLOCK) > 1 then
2147 ANTIC_OUT[BLOCK] = intersection of ANTIC_IN[b] for all succ(BLOCK)
2148 else if succs(BLOCK) == 1 then
2149 ANTIC_OUT[BLOCK] = phi_translate (ANTIC_IN[succ(BLOCK)])
2151 ANTIC_IN[BLOCK] = clean(ANTIC_OUT[BLOCK] U EXP_GEN[BLOCK] - TMP_GEN[BLOCK])
2155 compute_antic_aux (basic_block block, bool block_has_abnormal_pred_edge)
2157 bool changed = false;
2158 bitmap_set_t S, old, ANTIC_OUT;
2164 old = ANTIC_OUT = S = NULL;
2165 BB_VISITED (block) = 1;
2167 /* If any edges from predecessors are abnormal, antic_in is empty,
2169 if (block_has_abnormal_pred_edge)
2170 goto maybe_dump_sets;
2172 old = ANTIC_IN (block);
2173 ANTIC_OUT = bitmap_set_new ();
2175 /* If the block has no successors, ANTIC_OUT is empty. */
2176 if (EDGE_COUNT (block->succs) == 0)
2178 /* If we have one successor, we could have some phi nodes to
2179 translate through. */
2180 else if (single_succ_p (block))
2182 basic_block succ_bb = single_succ (block);
2184 /* We trade iterations of the dataflow equations for having to
2185 phi translate the maximal set, which is incredibly slow
2186 (since the maximal set often has 300+ members, even when you
2187 have a small number of blocks).
2188 Basically, we defer the computation of ANTIC for this block
2189 until we have processed it's successor, which will inevitably
2190 have a *much* smaller set of values to phi translate once
2191 clean has been run on it.
2192 The cost of doing this is that we technically perform more
2193 iterations, however, they are lower cost iterations.
2195 Timings for PRE on tramp3d-v4:
2196 without maximal set fix: 11 seconds
2197 with maximal set fix/without deferring: 26 seconds
2198 with maximal set fix/with deferring: 11 seconds
2201 if (!defer_or_phi_translate_block (ANTIC_OUT, ANTIC_IN (succ_bb),
2205 goto maybe_dump_sets;
2208 /* If we have multiple successors, we take the intersection of all of
2209 them. Note that in the case of loop exit phi nodes, we may have
2210 phis to translate through. */
2213 VEC(basic_block, heap) * worklist;
2215 basic_block bprime, first = NULL;
2217 worklist = VEC_alloc (basic_block, heap, EDGE_COUNT (block->succs));
2218 FOR_EACH_EDGE (e, ei, block->succs)
2221 && BB_VISITED (e->dest))
2223 else if (BB_VISITED (e->dest))
2224 VEC_quick_push (basic_block, worklist, e->dest);
2227 /* Of multiple successors we have to have visited one already. */
2230 SET_BIT (changed_blocks, block->index);
2231 BB_VISITED (block) = 0;
2232 BB_DEFERRED (block) = 1;
2234 VEC_free (basic_block, heap, worklist);
2235 goto maybe_dump_sets;
2238 if (phi_nodes (first))
2239 phi_translate_set (ANTIC_OUT, ANTIC_IN (first), block, first);
2241 bitmap_set_copy (ANTIC_OUT, ANTIC_IN (first));
2243 for (i = 0; VEC_iterate (basic_block, worklist, i, bprime); i++)
2245 if (phi_nodes (bprime))
2247 bitmap_set_t tmp = bitmap_set_new ();
2248 phi_translate_set (tmp, ANTIC_IN (bprime), block, bprime);
2249 bitmap_set_and (ANTIC_OUT, tmp);
2250 bitmap_set_free (tmp);
2253 bitmap_set_and (ANTIC_OUT, ANTIC_IN (bprime));
2255 VEC_free (basic_block, heap, worklist);
2258 /* Generate ANTIC_OUT - TMP_GEN. */
2259 S = bitmap_set_subtract (ANTIC_OUT, TMP_GEN (block));
2261 /* Start ANTIC_IN with EXP_GEN - TMP_GEN. */
2262 ANTIC_IN (block) = bitmap_set_subtract (EXP_GEN (block),
2265 /* Then union in the ANTIC_OUT - TMP_GEN values,
2266 to get ANTIC_OUT U EXP_GEN - TMP_GEN */
2267 FOR_EACH_EXPR_ID_IN_SET (S, bii, bi)
2268 bitmap_value_insert_into_set (ANTIC_IN (block),
2269 expression_for_id (bii));
2271 clean (ANTIC_IN (block), block);
2273 /* !old->expressions can happen when we deferred a block. */
2274 if (!old->expressions || !bitmap_set_equal (old, ANTIC_IN (block)))
2277 SET_BIT (changed_blocks, block->index);
2278 FOR_EACH_EDGE (e, ei, block->preds)
2279 SET_BIT (changed_blocks, e->src->index);
2282 RESET_BIT (changed_blocks, block->index);
2285 if (dump_file && (dump_flags & TDF_DETAILS))
2287 if (!BB_DEFERRED (block) || BB_VISITED (block))
2290 print_bitmap_set (dump_file, ANTIC_OUT, "ANTIC_OUT", block->index);
2292 print_bitmap_set (dump_file, ANTIC_IN (block), "ANTIC_IN",
2296 print_bitmap_set (dump_file, S, "S", block->index);
2301 "Block %d was deferred for a future iteration.\n",
2306 bitmap_set_free (old);
2308 bitmap_set_free (S);
2310 bitmap_set_free (ANTIC_OUT);
2314 /* Compute PARTIAL_ANTIC for BLOCK.
2316 If succs(BLOCK) > 1 then
2317 PA_OUT[BLOCK] = value wise union of PA_IN[b] + all ANTIC_IN not
2318 in ANTIC_OUT for all succ(BLOCK)
2319 else if succs(BLOCK) == 1 then
2320 PA_OUT[BLOCK] = phi_translate (PA_IN[succ(BLOCK)])
2322 PA_IN[BLOCK] = dependent_clean(PA_OUT[BLOCK] - TMP_GEN[BLOCK]
2327 compute_partial_antic_aux (basic_block block,
2328 bool block_has_abnormal_pred_edge)
2330 bool changed = false;
2331 bitmap_set_t old_PA_IN;
2332 bitmap_set_t PA_OUT;
2335 unsigned long max_pa = PARAM_VALUE (PARAM_MAX_PARTIAL_ANTIC_LENGTH);
2337 old_PA_IN = PA_OUT = NULL;
2339 /* If any edges from predecessors are abnormal, antic_in is empty,
2341 if (block_has_abnormal_pred_edge)
2342 goto maybe_dump_sets;
2344 /* If there are too many partially anticipatable values in the
2345 block, phi_translate_set can take an exponential time: stop
2346 before the translation starts. */
2348 && single_succ_p (block)
2349 && bitmap_count_bits (PA_IN (single_succ (block))->values) > max_pa)
2350 goto maybe_dump_sets;
2352 old_PA_IN = PA_IN (block);
2353 PA_OUT = bitmap_set_new ();
2355 /* If the block has no successors, ANTIC_OUT is empty. */
2356 if (EDGE_COUNT (block->succs) == 0)
2358 /* If we have one successor, we could have some phi nodes to
2359 translate through. Note that we can't phi translate across DFS
2360 back edges in partial antic, because it uses a union operation on
2361 the successors. For recurrences like IV's, we will end up
2362 generating a new value in the set on each go around (i + 3 (VH.1)
2363 VH.1 + 1 (VH.2), VH.2 + 1 (VH.3), etc), forever. */
2364 else if (single_succ_p (block))
2366 basic_block succ = single_succ (block);
2367 if (!(single_succ_edge (block)->flags & EDGE_DFS_BACK))
2368 phi_translate_set (PA_OUT, PA_IN (succ), block, succ);
2370 /* If we have multiple successors, we take the union of all of
2374 VEC(basic_block, heap) * worklist;
2378 worklist = VEC_alloc (basic_block, heap, EDGE_COUNT (block->succs));
2379 FOR_EACH_EDGE (e, ei, block->succs)
2381 if (e->flags & EDGE_DFS_BACK)
2383 VEC_quick_push (basic_block, worklist, e->dest);
2385 if (VEC_length (basic_block, worklist) > 0)
2387 for (i = 0; VEC_iterate (basic_block, worklist, i, bprime); i++)
2392 FOR_EACH_EXPR_ID_IN_SET (ANTIC_IN (bprime), i, bi)
2393 bitmap_value_insert_into_set (PA_OUT,
2394 expression_for_id (i));
2395 if (phi_nodes (bprime))
2397 bitmap_set_t pa_in = bitmap_set_new ();
2398 phi_translate_set (pa_in, PA_IN (bprime), block, bprime);
2399 FOR_EACH_EXPR_ID_IN_SET (pa_in, i, bi)
2400 bitmap_value_insert_into_set (PA_OUT,
2401 expression_for_id (i));
2402 bitmap_set_free (pa_in);
2405 FOR_EACH_EXPR_ID_IN_SET (PA_IN (bprime), i, bi)
2406 bitmap_value_insert_into_set (PA_OUT,
2407 expression_for_id (i));
2410 VEC_free (basic_block, heap, worklist);
2413 /* PA_IN starts with PA_OUT - TMP_GEN.
2414 Then we subtract things from ANTIC_IN. */
2415 PA_IN (block) = bitmap_set_subtract (PA_OUT, TMP_GEN (block));
2417 /* For partial antic, we want to put back in the phi results, since
2418 we will properly avoid making them partially antic over backedges. */
2419 bitmap_ior_into (PA_IN (block)->values, PHI_GEN (block)->values);
2420 bitmap_ior_into (PA_IN (block)->expressions, PHI_GEN (block)->expressions);
2422 /* PA_IN[block] = PA_IN[block] - ANTIC_IN[block] */
2423 bitmap_set_subtract_values (PA_IN (block), ANTIC_IN (block));
2425 dependent_clean (PA_IN (block), ANTIC_IN (block), block);
2427 if (!bitmap_set_equal (old_PA_IN, PA_IN (block)))
2430 SET_BIT (changed_blocks, block->index);
2431 FOR_EACH_EDGE (e, ei, block->preds)
2432 SET_BIT (changed_blocks, e->src->index);
2435 RESET_BIT (changed_blocks, block->index);
2438 if (dump_file && (dump_flags & TDF_DETAILS))
2441 print_bitmap_set (dump_file, PA_OUT, "PA_OUT", block->index);
2443 print_bitmap_set (dump_file, PA_IN (block), "PA_IN", block->index);
2446 bitmap_set_free (old_PA_IN);
2448 bitmap_set_free (PA_OUT);
2452 /* Compute ANTIC and partial ANTIC sets. */
2455 compute_antic (void)
2457 bool changed = true;
2458 int num_iterations = 0;
2462 /* If any predecessor edges are abnormal, we punt, so antic_in is empty.
2463 We pre-build the map of blocks with incoming abnormal edges here. */
2464 has_abnormal_preds = sbitmap_alloc (last_basic_block);
2465 sbitmap_zero (has_abnormal_preds);
2472 FOR_EACH_EDGE (e, ei, block->preds)
2474 e->flags &= ~EDGE_DFS_BACK;
2475 if (e->flags & EDGE_ABNORMAL)
2477 SET_BIT (has_abnormal_preds, block->index);
2482 BB_VISITED (block) = 0;
2483 BB_DEFERRED (block) = 0;
2485 /* While we are here, give empty ANTIC_IN sets to each block. */
2486 ANTIC_IN (block) = bitmap_set_new ();
2487 PA_IN (block) = bitmap_set_new ();
2490 /* At the exit block we anticipate nothing. */
2491 ANTIC_IN (EXIT_BLOCK_PTR) = bitmap_set_new ();
2492 BB_VISITED (EXIT_BLOCK_PTR) = 1;
2493 PA_IN (EXIT_BLOCK_PTR) = bitmap_set_new ();
2495 changed_blocks = sbitmap_alloc (last_basic_block + 1);
2496 sbitmap_ones (changed_blocks);
2499 if (dump_file && (dump_flags & TDF_DETAILS))
2500 fprintf (dump_file, "Starting iteration %d\n", num_iterations);
2503 for (i = 0; i < n_basic_blocks - NUM_FIXED_BLOCKS; i++)
2505 if (TEST_BIT (changed_blocks, postorder[i]))
2507 basic_block block = BASIC_BLOCK (postorder[i]);
2508 changed |= compute_antic_aux (block,
2509 TEST_BIT (has_abnormal_preds,
2513 #ifdef ENABLE_CHECKING
2514 /* Theoretically possible, but *highly* unlikely. */
2515 gcc_assert (num_iterations < 500);
2519 statistics_histogram_event (cfun, "compute_antic iterations",
2522 if (do_partial_partial)
2524 sbitmap_ones (changed_blocks);
2525 mark_dfs_back_edges ();
2530 if (dump_file && (dump_flags & TDF_DETAILS))
2531 fprintf (dump_file, "Starting iteration %d\n", num_iterations);
2534 for (i = 0; i < n_basic_blocks - NUM_FIXED_BLOCKS; i++)
2536 if (TEST_BIT (changed_blocks, postorder[i]))
2538 basic_block block = BASIC_BLOCK (postorder[i]);
2540 |= compute_partial_antic_aux (block,
2541 TEST_BIT (has_abnormal_preds,
2545 #ifdef ENABLE_CHECKING
2546 /* Theoretically possible, but *highly* unlikely. */
2547 gcc_assert (num_iterations < 500);
2550 statistics_histogram_event (cfun, "compute_partial_antic iterations",
2553 sbitmap_free (has_abnormal_preds);
2554 sbitmap_free (changed_blocks);
2557 /* Return true if we can value number the call in STMT. This is true
2558 if we have a pure or constant call. */
2561 can_value_number_call (gimple stmt)
2563 if (gimple_call_flags (stmt) & (ECF_PURE | ECF_CONST))
2568 /* Return true if OP is a tree which we can perform PRE on.
2569 This may not match the operations we can value number, but in
2570 a perfect world would. */
2573 can_PRE_operation (tree op)
2575 return UNARY_CLASS_P (op)
2576 || BINARY_CLASS_P (op)
2577 || COMPARISON_CLASS_P (op)
2578 || TREE_CODE (op) == INDIRECT_REF
2579 || TREE_CODE (op) == COMPONENT_REF
2580 || TREE_CODE (op) == VIEW_CONVERT_EXPR
2581 || TREE_CODE (op) == CALL_EXPR
2582 || TREE_CODE (op) == ARRAY_REF;
2586 /* Inserted expressions are placed onto this worklist, which is used
2587 for performing quick dead code elimination of insertions we made
2588 that didn't turn out to be necessary. */
2589 static VEC(gimple,heap) *inserted_exprs;
2590 static bitmap inserted_phi_names;
2592 /* Pool allocated fake store expressions are placed onto this
2593 worklist, which, after performing dead code elimination, is walked
2594 to see which expressions need to be put into GC'able memory */
2595 static VEC(gimple, heap) *need_creation;
2597 /* The actual worker for create_component_ref_by_pieces. */
2600 create_component_ref_by_pieces_1 (basic_block block, vn_reference_t ref,
2601 unsigned int *operand, gimple_seq *stmts,
2604 vn_reference_op_t currop = VEC_index (vn_reference_op_s, ref->operands,
2608 switch (currop->opcode)
2612 tree folded, sc = currop->op1;
2613 unsigned int nargs = 0;
2614 tree *args = XNEWVEC (tree, VEC_length (vn_reference_op_s,
2615 ref->operands) - 1);
2616 while (*operand < VEC_length (vn_reference_op_s, ref->operands))
2618 args[nargs] = create_component_ref_by_pieces_1 (block, ref,
2623 folded = build_call_array (currop->type,
2624 TREE_CODE (currop->op0) == FUNCTION_DECL
2625 ? build_fold_addr_expr (currop->op0)
2631 pre_expr scexpr = get_or_alloc_expr_for (sc);
2632 sc = find_or_generate_expression (block, scexpr, stmts, domstmt);
2635 CALL_EXPR_STATIC_CHAIN (folded) = sc;
2640 case TARGET_MEM_REF:
2642 vn_reference_op_t nextop = VEC_index (vn_reference_op_s, ref->operands,
2645 tree genop0 = NULL_TREE;
2646 tree baseop = create_component_ref_by_pieces_1 (block, ref, operand,
2652 op0expr = get_or_alloc_expr_for (currop->op0);
2653 genop0 = find_or_generate_expression (block, op0expr,
2658 if (DECL_P (baseop))
2659 return build6 (TARGET_MEM_REF, currop->type,
2661 genop0, currop->op1, currop->op2,
2662 unshare_expr (nextop->op1));
2664 return build6 (TARGET_MEM_REF, currop->type,
2666 genop0, currop->op1, currop->op2,
2667 unshare_expr (nextop->op1));
2673 gcc_assert (is_gimple_min_invariant (currop->op0));
2679 case VIEW_CONVERT_EXPR:
2682 tree genop0 = create_component_ref_by_pieces_1 (block, ref,
2687 folded = fold_build1 (currop->opcode, currop->type,
2692 case ALIGN_INDIRECT_REF:
2693 case MISALIGNED_INDIRECT_REF:
2697 tree genop1 = create_component_ref_by_pieces_1 (block, ref,
2702 genop1 = fold_convert (build_pointer_type (currop->type),
2705 if (currop->opcode == MISALIGNED_INDIRECT_REF)
2706 folded = fold_build2 (currop->opcode, currop->type,
2707 genop1, currop->op1);
2709 folded = fold_build1 (currop->opcode, currop->type,
2717 tree genop0 = create_component_ref_by_pieces_1 (block, ref, operand,
2719 pre_expr op1expr = get_or_alloc_expr_for (currop->op0);
2720 pre_expr op2expr = get_or_alloc_expr_for (currop->op1);
2726 genop1 = find_or_generate_expression (block, op1expr, stmts, domstmt);
2729 genop2 = find_or_generate_expression (block, op2expr, stmts, domstmt);
2732 folded = fold_build3 (BIT_FIELD_REF, currop->type, genop0, genop1,
2737 /* For array ref vn_reference_op's, operand 1 of the array ref
2738 is op0 of the reference op and operand 3 of the array ref is
2740 case ARRAY_RANGE_REF:
2744 tree genop1 = currop->op0;
2746 tree genop2 = currop->op1;
2748 tree genop3 = currop->op2;
2750 genop0 = create_component_ref_by_pieces_1 (block, ref, operand,
2754 op1expr = get_or_alloc_expr_for (genop1);
2755 genop1 = find_or_generate_expression (block, op1expr, stmts, domstmt);
2760 op2expr = get_or_alloc_expr_for (genop2);
2761 genop2 = find_or_generate_expression (block, op2expr, stmts,
2768 tree elmt_type = TREE_TYPE (TREE_TYPE (genop0));
2769 genop3 = size_binop (EXACT_DIV_EXPR, genop3,
2770 size_int (TYPE_ALIGN_UNIT (elmt_type)));
2771 op3expr = get_or_alloc_expr_for (genop3);
2772 genop3 = find_or_generate_expression (block, op3expr, stmts,
2777 return build4 (currop->opcode, currop->type, genop0, genop1,
2784 tree genop2 = currop->op1;
2786 op0 = create_component_ref_by_pieces_1 (block, ref, operand,
2790 /* op1 should be a FIELD_DECL, which are represented by
2795 op2expr = get_or_alloc_expr_for (genop2);
2796 genop2 = find_or_generate_expression (block, op2expr, stmts,
2802 return fold_build3 (COMPONENT_REF, TREE_TYPE (op1), op0, op1,
2808 pre_expr op0expr = get_or_alloc_expr_for (currop->op0);
2809 genop = find_or_generate_expression (block, op0expr, stmts, domstmt);
2830 /* For COMPONENT_REF's and ARRAY_REF's, we can't have any intermediates for the
2831 COMPONENT_REF or INDIRECT_REF or ARRAY_REF portion, because we'd end up with
2832 trying to rename aggregates into ssa form directly, which is a no no.
2834 Thus, this routine doesn't create temporaries, it just builds a
2835 single access expression for the array, calling
2836 find_or_generate_expression to build the innermost pieces.
2838 This function is a subroutine of create_expression_by_pieces, and
2839 should not be called on it's own unless you really know what you
2843 create_component_ref_by_pieces (basic_block block, vn_reference_t ref,
2844 gimple_seq *stmts, gimple domstmt)
2846 unsigned int op = 0;
2847 return create_component_ref_by_pieces_1 (block, ref, &op, stmts, domstmt);
2850 /* Find a leader for an expression, or generate one using
2851 create_expression_by_pieces if it's ANTIC but
2853 BLOCK is the basic_block we are looking for leaders in.
2854 EXPR is the expression to find a leader or generate for.
2855 STMTS is the statement list to put the inserted expressions on.
2856 Returns the SSA_NAME of the LHS of the generated expression or the
2858 DOMSTMT if non-NULL is a statement that should be dominated by
2859 all uses in the generated expression. If DOMSTMT is non-NULL this
2860 routine can fail and return NULL_TREE. Otherwise it will assert
2864 find_or_generate_expression (basic_block block, pre_expr expr,
2865 gimple_seq *stmts, gimple domstmt)
2867 pre_expr leader = bitmap_find_leader (AVAIL_OUT (block),
2868 get_expr_value_id (expr), domstmt);
2872 if (leader->kind == NAME)
2873 genop = PRE_EXPR_NAME (leader);
2874 else if (leader->kind == CONSTANT)
2875 genop = PRE_EXPR_CONSTANT (leader);
2878 /* If it's still NULL, it must be a complex expression, so generate
2879 it recursively. Not so for FRE though. */
2883 bitmap_set_t exprset;
2884 unsigned int lookfor = get_expr_value_id (expr);
2885 bool handled = false;
2889 exprset = VEC_index (bitmap_set_t, value_expressions, lookfor);
2890 FOR_EACH_EXPR_ID_IN_SET (exprset, i, bi)
2892 pre_expr temp = expression_for_id (i);
2893 if (temp->kind != NAME)
2896 genop = create_expression_by_pieces (block, temp, stmts,
2898 get_expr_type (expr));
2902 if (!handled && domstmt)
2905 gcc_assert (handled);
2910 #define NECESSARY GF_PLF_1
2912 /* Create an expression in pieces, so that we can handle very complex
2913 expressions that may be ANTIC, but not necessary GIMPLE.
2914 BLOCK is the basic block the expression will be inserted into,
2915 EXPR is the expression to insert (in value form)
2916 STMTS is a statement list to append the necessary insertions into.
2918 This function will die if we hit some value that shouldn't be
2919 ANTIC but is (IE there is no leader for it, or its components).
2920 This function may also generate expressions that are themselves
2921 partially or fully redundant. Those that are will be either made
2922 fully redundant during the next iteration of insert (for partially
2923 redundant ones), or eliminated by eliminate (for fully redundant
2926 If DOMSTMT is non-NULL then we make sure that all uses in the
2927 expressions dominate that statement. In this case the function
2928 can return NULL_TREE to signal failure. */
2931 create_expression_by_pieces (basic_block block, pre_expr expr,
2932 gimple_seq *stmts, gimple domstmt, tree type)
2936 gimple_seq forced_stmts = NULL;
2937 unsigned int value_id;
2938 gimple_stmt_iterator gsi;
2939 tree exprtype = type ? type : get_expr_type (expr);
2945 /* We may hit the NAME/CONSTANT case if we have to convert types
2946 that value numbering saw through. */
2948 folded = PRE_EXPR_NAME (expr);
2951 folded = PRE_EXPR_CONSTANT (expr);
2955 vn_reference_t ref = PRE_EXPR_REFERENCE (expr);
2956 folded = create_component_ref_by_pieces (block, ref, stmts, domstmt);
2961 vn_nary_op_t nary = PRE_EXPR_NARY (expr);
2962 switch (nary->length)
2966 pre_expr op1 = get_or_alloc_expr_for (nary->op[0]);
2967 pre_expr op2 = get_or_alloc_expr_for (nary->op[1]);
2968 tree genop1 = find_or_generate_expression (block, op1,
2970 tree genop2 = find_or_generate_expression (block, op2,
2972 if (!genop1 || !genop2)
2974 genop1 = fold_convert (TREE_TYPE (nary->op[0]),
2976 /* Ensure op2 is a sizetype for POINTER_PLUS_EXPR. It
2977 may be a constant with the wrong type. */
2978 if (nary->opcode == POINTER_PLUS_EXPR)
2979 genop2 = fold_convert (sizetype, genop2);
2981 genop2 = fold_convert (TREE_TYPE (nary->op[1]), genop2);
2983 folded = fold_build2 (nary->opcode, nary->type,
2989 pre_expr op1 = get_or_alloc_expr_for (nary->op[0]);
2990 tree genop1 = find_or_generate_expression (block, op1,
2994 genop1 = fold_convert (TREE_TYPE (nary->op[0]), genop1);
2996 folded = fold_build1 (nary->opcode, nary->type,
3009 if (!useless_type_conversion_p (exprtype, TREE_TYPE (folded)))
3010 folded = fold_convert (exprtype, folded);
3012 /* Force the generated expression to be a sequence of GIMPLE
3014 We have to call unshare_expr because force_gimple_operand may
3015 modify the tree we pass to it. */
3016 folded = force_gimple_operand (unshare_expr (folded), &forced_stmts,
3019 /* If we have any intermediate expressions to the value sets, add them
3020 to the value sets and chain them in the instruction stream. */
3023 gsi = gsi_start (forced_stmts);
3024 for (; !gsi_end_p (gsi); gsi_next (&gsi))
3026 gimple stmt = gsi_stmt (gsi);
3027 tree forcedname = gimple_get_lhs (stmt);
3030 VEC_safe_push (gimple, heap, inserted_exprs, stmt);
3031 if (TREE_CODE (forcedname) == SSA_NAME)
3033 VN_INFO_GET (forcedname)->valnum = forcedname;
3034 VN_INFO (forcedname)->value_id = get_next_value_id ();
3035 nameexpr = get_or_alloc_expr_for_name (forcedname);
3036 add_to_value (VN_INFO (forcedname)->value_id, nameexpr);
3038 bitmap_value_replace_in_set (NEW_SETS (block), nameexpr);
3039 bitmap_value_replace_in_set (AVAIL_OUT (block), nameexpr);
3041 mark_symbols_for_renaming (stmt);
3043 gimple_seq_add_seq (stmts, forced_stmts);
3046 /* Build and insert the assignment of the end result to the temporary
3047 that we will return. */
3048 if (!pretemp || exprtype != TREE_TYPE (pretemp))
3050 pretemp = create_tmp_var (exprtype, "pretmp");
3051 get_var_ann (pretemp);
3055 add_referenced_var (temp);
3057 if (TREE_CODE (exprtype) == COMPLEX_TYPE
3058 || TREE_CODE (exprtype) == VECTOR_TYPE)
3059 DECL_GIMPLE_REG_P (temp) = 1;
3061 newstmt = gimple_build_assign (temp, folded);
3062 name = make_ssa_name (temp, newstmt);
3063 gimple_assign_set_lhs (newstmt, name);
3064 gimple_set_plf (newstmt, NECESSARY, false);
3066 gimple_seq_add_stmt (stmts, newstmt);
3067 VEC_safe_push (gimple, heap, inserted_exprs, newstmt);
3069 /* All the symbols in NEWEXPR should be put into SSA form. */
3070 mark_symbols_for_renaming (newstmt);
3072 /* Add a value number to the temporary.
3073 The value may already exist in either NEW_SETS, or AVAIL_OUT, because
3074 we are creating the expression by pieces, and this particular piece of
3075 the expression may have been represented. There is no harm in replacing
3077 VN_INFO_GET (name)->valnum = name;
3078 value_id = get_expr_value_id (expr);
3079 VN_INFO (name)->value_id = value_id;
3080 nameexpr = get_or_alloc_expr_for_name (name);
3081 add_to_value (value_id, nameexpr);
3083 bitmap_value_replace_in_set (NEW_SETS (block), nameexpr);
3084 bitmap_value_replace_in_set (AVAIL_OUT (block), nameexpr);
3086 pre_stats.insertions++;
3087 if (dump_file && (dump_flags & TDF_DETAILS))
3089 fprintf (dump_file, "Inserted ");
3090 print_gimple_stmt (dump_file, newstmt, 0, 0);
3091 fprintf (dump_file, " in predecessor %d\n", block->index);
3098 /* Returns true if we want to inhibit the insertions of PHI nodes
3099 for the given EXPR for basic block BB (a member of a loop).
3100 We want to do this, when we fear that the induction variable we
3101 create might inhibit vectorization. */
3104 inhibit_phi_insertion (basic_block bb, pre_expr expr)
3106 vn_reference_t vr = PRE_EXPR_REFERENCE (expr);
3107 VEC (vn_reference_op_s, heap) *ops = vr->operands;
3108 vn_reference_op_t op;
3111 /* If we aren't going to vectorize we don't inhibit anything. */
3112 if (!flag_tree_vectorize)
3115 /* Otherwise we inhibit the insertion when the address of the
3116 memory reference is a simple induction variable. In other
3117 cases the vectorizer won't do anything anyway (either it's
3118 loop invariant or a complicated expression). */
3119 for (i = 0; VEC_iterate (vn_reference_op_s, ops, i, op); ++i)
3124 case ARRAY_RANGE_REF:
3125 if (TREE_CODE (op->op0) != SSA_NAME)
3130 basic_block defbb = gimple_bb (SSA_NAME_DEF_STMT (op->op0));
3132 /* Default defs are loop invariant. */
3135 /* Defined outside this loop, also loop invariant. */
3136 if (!flow_bb_inside_loop_p (bb->loop_father, defbb))
3138 /* If it's a simple induction variable inhibit insertion,
3139 the vectorizer might be interested in this one. */
3140 if (simple_iv (bb->loop_father, bb->loop_father,
3141 op->op0, &iv, true))
3143 /* No simple IV, vectorizer can't do anything, hence no
3144 reason to inhibit the transformation for this operand. */
3154 /* Insert the to-be-made-available values of expression EXPRNUM for each
3155 predecessor, stored in AVAIL, into the predecessors of BLOCK, and
3156 merge the result with a phi node, given the same value number as
3157 NODE. Return true if we have inserted new stuff. */
3160 insert_into_preds_of_block (basic_block block, unsigned int exprnum,
3163 pre_expr expr = expression_for_id (exprnum);
3165 unsigned int val = get_expr_value_id (expr);
3167 bool insertions = false;
3172 tree type = get_expr_type (expr);
3176 if (dump_file && (dump_flags & TDF_DETAILS))
3178 fprintf (dump_file, "Found partial redundancy for expression ");
3179 print_pre_expr (dump_file, expr);
3180 fprintf (dump_file, " (%04d)\n", val);
3183 /* Make sure we aren't creating an induction variable. */
3184 if (block->loop_depth > 0 && EDGE_COUNT (block->preds) == 2)
3186 bool firstinsideloop = false;
3187 bool secondinsideloop = false;
3188 firstinsideloop = flow_bb_inside_loop_p (block->loop_father,
3189 EDGE_PRED (block, 0)->src);
3190 secondinsideloop = flow_bb_inside_loop_p (block->loop_father,
3191 EDGE_PRED (block, 1)->src);
3192 /* Induction variables only have one edge inside the loop. */
3193 if ((firstinsideloop ^ secondinsideloop)
3194 && (expr->kind != REFERENCE
3195 || inhibit_phi_insertion (block, expr)))
3197 if (dump_file && (dump_flags & TDF_DETAILS))
3198 fprintf (dump_file, "Skipping insertion of phi for partial redundancy: Looks like an induction variable\n");
3203 /* Make the necessary insertions. */
3204 FOR_EACH_EDGE (pred, ei, block->preds)
3206 gimple_seq stmts = NULL;
3209 eprime = avail[bprime->index];
3211 if (eprime->kind != NAME && eprime->kind != CONSTANT)
3213 builtexpr = create_expression_by_pieces (bprime,
3217 gcc_assert (!(pred->flags & EDGE_ABNORMAL));
3218 gsi_insert_seq_on_edge (pred, stmts);
3219 avail[bprime->index] = get_or_alloc_expr_for_name (builtexpr);
3222 else if (eprime->kind == CONSTANT)
3224 /* Constants may not have the right type, fold_convert
3225 should give us back a constant with the right type.
3227 tree constant = PRE_EXPR_CONSTANT (eprime);
3228 if (!useless_type_conversion_p (type, TREE_TYPE (constant)))
3230 tree builtexpr = fold_convert (type, constant);
3231 if (!is_gimple_min_invariant (builtexpr))
3233 tree forcedexpr = force_gimple_operand (builtexpr,
3236 if (!is_gimple_min_invariant (forcedexpr))
3238 if (forcedexpr != builtexpr)
3240 VN_INFO_GET (forcedexpr)->valnum = PRE_EXPR_CONSTANT (eprime);
3241 VN_INFO (forcedexpr)->value_id = get_expr_value_id (eprime);
3245 gimple_stmt_iterator gsi;
3246 gsi = gsi_start (stmts);
3247 for (; !gsi_end_p (gsi); gsi_next (&gsi))
3249 gimple stmt = gsi_stmt (gsi);
3250 VEC_safe_push (gimple, heap, inserted_exprs, stmt);
3251 gimple_set_plf (stmt, NECESSARY, false);
3253 gsi_insert_seq_on_edge (pred, stmts);
3255 avail[bprime->index] = get_or_alloc_expr_for_name (forcedexpr);
3260 else if (eprime->kind == NAME)
3262 /* We may have to do a conversion because our value
3263 numbering can look through types in certain cases, but
3264 our IL requires all operands of a phi node have the same
3266 tree name = PRE_EXPR_NAME (eprime);
3267 if (!useless_type_conversion_p (type, TREE_TYPE (name)))
3271 builtexpr = fold_convert (type, name);
3272 forcedexpr = force_gimple_operand (builtexpr,
3276 if (forcedexpr != name)
3278 VN_INFO_GET (forcedexpr)->valnum = VN_INFO (name)->valnum;
3279 VN_INFO (forcedexpr)->value_id = VN_INFO (name)->value_id;
3284 gimple_stmt_iterator gsi;
3285 gsi = gsi_start (stmts);
3286 for (; !gsi_end_p (gsi); gsi_next (&gsi))
3288 gimple stmt = gsi_stmt (gsi);
3289 VEC_safe_push (gimple, heap, inserted_exprs, stmt);
3290 gimple_set_plf (stmt, NECESSARY, false);
3292 gsi_insert_seq_on_edge (pred, stmts);
3294 avail[bprime->index] = get_or_alloc_expr_for_name (forcedexpr);
3298 /* If we didn't want a phi node, and we made insertions, we still have
3299 inserted new stuff, and thus return true. If we didn't want a phi node,
3300 and didn't make insertions, we haven't added anything new, so return
3302 if (nophi && insertions)
3304 else if (nophi && !insertions)
3307 /* Now build a phi for the new variable. */
3308 if (!prephitemp || TREE_TYPE (prephitemp) != type)
3310 prephitemp = create_tmp_var (type, "prephitmp");
3311 get_var_ann (prephitemp);
3315 add_referenced_var (temp);
3317 if (TREE_CODE (type) == COMPLEX_TYPE
3318 || TREE_CODE (type) == VECTOR_TYPE)
3319 DECL_GIMPLE_REG_P (temp) = 1;
3320 phi = create_phi_node (temp, block);
3322 gimple_set_plf (phi, NECESSARY, false);
3323 VN_INFO_GET (gimple_phi_result (phi))->valnum = gimple_phi_result (phi);
3324 VN_INFO (gimple_phi_result (phi))->value_id = val;
3325 VEC_safe_push (gimple, heap, inserted_exprs, phi);
3326 bitmap_set_bit (inserted_phi_names,
3327 SSA_NAME_VERSION (gimple_phi_result (phi)));
3328 FOR_EACH_EDGE (pred, ei, block->preds)
3330 pre_expr ae = avail[pred->src->index];
3331 gcc_assert (get_expr_type (ae) == type
3332 || useless_type_conversion_p (type, get_expr_type (ae)));
3333 if (ae->kind == CONSTANT)
3334 add_phi_arg (phi, PRE_EXPR_CONSTANT (ae), pred, UNKNOWN_LOCATION);
3336 add_phi_arg (phi, PRE_EXPR_NAME (avail[pred->src->index]), pred,
3340 newphi = get_or_alloc_expr_for_name (gimple_phi_result (phi));
3341 add_to_value (val, newphi);
3343 /* The value should *not* exist in PHI_GEN, or else we wouldn't be doing
3344 this insertion, since we test for the existence of this value in PHI_GEN
3345 before proceeding with the partial redundancy checks in insert_aux.
3347 The value may exist in AVAIL_OUT, in particular, it could be represented
3348 by the expression we are trying to eliminate, in which case we want the
3349 replacement to occur. If it's not existing in AVAIL_OUT, we want it
3352 Similarly, to the PHI_GEN case, the value should not exist in NEW_SETS of
3353 this block, because if it did, it would have existed in our dominator's
3354 AVAIL_OUT, and would have been skipped due to the full redundancy check.
3357 bitmap_insert_into_set (PHI_GEN (block), newphi);
3358 bitmap_value_replace_in_set (AVAIL_OUT (block),
3360 bitmap_insert_into_set (NEW_SETS (block),
3363 if (dump_file && (dump_flags & TDF_DETAILS))
3365 fprintf (dump_file, "Created phi ");
3366 print_gimple_stmt (dump_file, phi, 0, 0);
3367 fprintf (dump_file, " in block %d\n", block->index);
3375 /* Perform insertion of partially redundant values.
3376 For BLOCK, do the following:
3377 1. Propagate the NEW_SETS of the dominator into the current block.
3378 If the block has multiple predecessors,
3379 2a. Iterate over the ANTIC expressions for the block to see if
3380 any of them are partially redundant.
3381 2b. If so, insert them into the necessary predecessors to make
3382 the expression fully redundant.
3383 2c. Insert a new PHI merging the values of the predecessors.
3384 2d. Insert the new PHI, and the new expressions, into the
3386 3. Recursively call ourselves on the dominator children of BLOCK.
3388 Steps 1, 2a, and 3 are done by insert_aux. 2b, 2c and 2d are done by
3389 do_regular_insertion and do_partial_insertion.
3394 do_regular_insertion (basic_block block, basic_block dom)
3396 bool new_stuff = false;
3397 VEC (pre_expr, heap) *exprs = sorted_array_from_bitmap_set (ANTIC_IN (block));
3401 for (i = 0; VEC_iterate (pre_expr, exprs, i, expr); i++)
3403 if (expr->kind != NAME)
3407 bool by_some = false;
3408 bool cant_insert = false;
3409 bool all_same = true;
3410 pre_expr first_s = NULL;
3413 pre_expr eprime = NULL;
3415 pre_expr edoubleprime = NULL;
3416 bool do_insertion = false;
3418 val = get_expr_value_id (expr);
3419 if (bitmap_set_contains_value (PHI_GEN (block), val))
3421 if (bitmap_set_contains_value (AVAIL_OUT (dom), val))
3423 if (dump_file && (dump_flags & TDF_DETAILS))
3424 fprintf (dump_file, "Found fully redundant value\n");
3428 avail = XCNEWVEC (pre_expr, last_basic_block);
3429 FOR_EACH_EDGE (pred, ei, block->preds)
3431 unsigned int vprime;
3433 /* We should never run insertion for the exit block
3434 and so not come across fake pred edges. */
3435 gcc_assert (!(pred->flags & EDGE_FAKE));
3437 eprime = phi_translate (expr, ANTIC_IN (block), NULL,
3440 /* eprime will generally only be NULL if the
3441 value of the expression, translated
3442 through the PHI for this predecessor, is
3443 undefined. If that is the case, we can't
3444 make the expression fully redundant,
3445 because its value is undefined along a
3446 predecessor path. We can thus break out
3447 early because it doesn't matter what the
3448 rest of the results are. */
3455 eprime = fully_constant_expression (eprime);
3456 vprime = get_expr_value_id (eprime);
3457 edoubleprime = bitmap_find_leader (AVAIL_OUT (bprime),
3459 if (edoubleprime == NULL)
3461 avail[bprime->index] = eprime;
3466 avail[bprime->index] = edoubleprime;
3468 /* We want to perform insertions to remove a redundancy on
3469 a path in the CFG we want to optimize for speed. */
3470 if (optimize_edge_for_speed_p (pred))
3471 do_insertion = true;
3472 if (first_s == NULL)
3473 first_s = edoubleprime;
3474 else if (!pre_expr_eq (first_s, edoubleprime))
3478 /* If we can insert it, it's not the same value
3479 already existing along every predecessor, and
3480 it's defined by some predecessor, it is
3481 partially redundant. */
3482 if (!cant_insert && !all_same && by_some && do_insertion
3483 && dbg_cnt (treepre_insert))
3485 if (insert_into_preds_of_block (block, get_expression_id (expr),
3489 /* If all edges produce the same value and that value is
3490 an invariant, then the PHI has the same value on all
3491 edges. Note this. */
3492 else if (!cant_insert && all_same && eprime
3493 && (edoubleprime->kind == CONSTANT
3494 || edoubleprime->kind == NAME)
3495 && !value_id_constant_p (val))
3499 bitmap_set_t exprset = VEC_index (bitmap_set_t,
3500 value_expressions, val);
3502 unsigned int new_val = get_expr_value_id (edoubleprime);
3503 FOR_EACH_EXPR_ID_IN_SET (exprset, j, bi)
3505 pre_expr expr = expression_for_id (j);
3507 if (expr->kind == NAME)
3509 vn_ssa_aux_t info = VN_INFO (PRE_EXPR_NAME (expr));
3510 /* Just reset the value id and valnum so it is
3511 the same as the constant we have discovered. */
3512 if (edoubleprime->kind == CONSTANT)
3514 info->valnum = PRE_EXPR_CONSTANT (edoubleprime);
3515 pre_stats.constified++;
3518 info->valnum = VN_INFO (PRE_EXPR_NAME (edoubleprime))->valnum;
3519 info->value_id = new_val;
3527 VEC_free (pre_expr, heap, exprs);
3532 /* Perform insertion for partially anticipatable expressions. There
3533 is only one case we will perform insertion for these. This case is
3534 if the expression is partially anticipatable, and fully available.
3535 In this case, we know that putting it earlier will enable us to
3536 remove the later computation. */
3540 do_partial_partial_insertion (basic_block block, basic_block dom)
3542 bool new_stuff = false;
3543 VEC (pre_expr, heap) *exprs = sorted_array_from_bitmap_set (PA_IN (block));
3547 for (i = 0; VEC_iterate (pre_expr, exprs, i, expr); i++)
3549 if (expr->kind != NAME)
3554 bool cant_insert = false;
3557 pre_expr eprime = NULL;
3560 val = get_expr_value_id (expr);
3561 if (bitmap_set_contains_value (PHI_GEN (block), val))
3563 if (bitmap_set_contains_value (AVAIL_OUT (dom), val))
3566 avail = XCNEWVEC (pre_expr, last_basic_block);
3567 FOR_EACH_EDGE (pred, ei, block->preds)
3569 unsigned int vprime;
3570 pre_expr edoubleprime;
3572 /* We should never run insertion for the exit block
3573 and so not come across fake pred edges. */
3574 gcc_assert (!(pred->flags & EDGE_FAKE));
3576 eprime = phi_translate (expr, ANTIC_IN (block),
3580 /* eprime will generally only be NULL if the
3581 value of the expression, translated
3582 through the PHI for this predecessor, is
3583 undefined. If that is the case, we can't
3584 make the expression fully redundant,
3585 because its value is undefined along a
3586 predecessor path. We can thus break out
3587 early because it doesn't matter what the
3588 rest of the results are. */
3595 eprime = fully_constant_expression (eprime);
3596 vprime = get_expr_value_id (eprime);
3597 edoubleprime = bitmap_find_leader (AVAIL_OUT (bprime),
3599 if (edoubleprime == NULL)
3605 avail[bprime->index] = edoubleprime;
3609 /* If we can insert it, it's not the same value
3610 already existing along every predecessor, and
3611 it's defined by some predecessor, it is
3612 partially redundant. */
3613 if (!cant_insert && by_all && dbg_cnt (treepre_insert))
3615 pre_stats.pa_insert++;
3616 if (insert_into_preds_of_block (block, get_expression_id (expr),
3624 VEC_free (pre_expr, heap, exprs);
3629 insert_aux (basic_block block)
3632 bool new_stuff = false;
3637 dom = get_immediate_dominator (CDI_DOMINATORS, block);
3642 bitmap_set_t newset = NEW_SETS (dom);
3645 /* Note that we need to value_replace both NEW_SETS, and
3646 AVAIL_OUT. For both the case of NEW_SETS, the value may be
3647 represented by some non-simple expression here that we want
3648 to replace it with. */
3649 FOR_EACH_EXPR_ID_IN_SET (newset, i, bi)
3651 pre_expr expr = expression_for_id (i);
3652 bitmap_value_replace_in_set (NEW_SETS (block), expr);
3653 bitmap_value_replace_in_set (AVAIL_OUT (block), expr);
3656 if (!single_pred_p (block))
3658 new_stuff |= do_regular_insertion (block, dom);
3659 if (do_partial_partial)
3660 new_stuff |= do_partial_partial_insertion (block, dom);
3664 for (son = first_dom_son (CDI_DOMINATORS, block);
3666 son = next_dom_son (CDI_DOMINATORS, son))
3668 new_stuff |= insert_aux (son);
3674 /* Perform insertion of partially redundant values. */
3679 bool new_stuff = true;
3681 int num_iterations = 0;
3684 NEW_SETS (bb) = bitmap_set_new ();
3689 new_stuff = insert_aux (ENTRY_BLOCK_PTR);
3691 statistics_histogram_event (cfun, "insert iterations", num_iterations);
3695 /* Add OP to EXP_GEN (block), and possibly to the maximal set. */
3698 add_to_exp_gen (basic_block block, tree op)
3703 if (TREE_CODE (op) == SSA_NAME && ssa_undefined_value_p (op))
3705 result = get_or_alloc_expr_for_name (op);
3706 bitmap_value_insert_into_set (EXP_GEN (block), result);
3710 /* Create value ids for PHI in BLOCK. */
3713 make_values_for_phi (gimple phi, basic_block block)
3715 tree result = gimple_phi_result (phi);
3717 /* We have no need for virtual phis, as they don't represent
3718 actual computations. */
3719 if (is_gimple_reg (result))
3721 pre_expr e = get_or_alloc_expr_for_name (result);
3722 add_to_value (get_expr_value_id (e), e);
3723 bitmap_insert_into_set (PHI_GEN (block), e);
3724 bitmap_value_insert_into_set (AVAIL_OUT (block), e);
3728 for (i = 0; i < gimple_phi_num_args (phi); ++i)
3730 tree arg = gimple_phi_arg_def (phi, i);
3731 if (TREE_CODE (arg) == SSA_NAME)
3733 e = get_or_alloc_expr_for_name (arg);
3734 add_to_value (get_expr_value_id (e), e);
3741 /* Compute the AVAIL set for all basic blocks.
3743 This function performs value numbering of the statements in each basic
3744 block. The AVAIL sets are built from information we glean while doing
3745 this value numbering, since the AVAIL sets contain only one entry per
3748 AVAIL_IN[BLOCK] = AVAIL_OUT[dom(BLOCK)].
3749 AVAIL_OUT[BLOCK] = AVAIL_IN[BLOCK] U PHI_GEN[BLOCK] U TMP_GEN[BLOCK]. */
3752 compute_avail (void)
3755 basic_block block, son;
3756 basic_block *worklist;
3760 /* We pretend that default definitions are defined in the entry block.
3761 This includes function arguments and the static chain decl. */
3762 for (i = 1; i < num_ssa_names; ++i)
3764 tree name = ssa_name (i);
3767 || !SSA_NAME_IS_DEFAULT_DEF (name)
3768 || has_zero_uses (name)
3769 || !is_gimple_reg (name))
3772 e = get_or_alloc_expr_for_name (name);
3773 add_to_value (get_expr_value_id (e), e);
3775 bitmap_insert_into_set (TMP_GEN (ENTRY_BLOCK_PTR), e);
3776 bitmap_value_insert_into_set (AVAIL_OUT (ENTRY_BLOCK_PTR), e);
3779 /* Allocate the worklist. */
3780 worklist = XNEWVEC (basic_block, n_basic_blocks);
3782 /* Seed the algorithm by putting the dominator children of the entry
3783 block on the worklist. */
3784 for (son = first_dom_son (CDI_DOMINATORS, ENTRY_BLOCK_PTR);
3786 son = next_dom_son (CDI_DOMINATORS, son))
3787 worklist[sp++] = son;
3789 /* Loop until the worklist is empty. */
3792 gimple_stmt_iterator gsi;
3795 unsigned int stmt_uid = 1;
3797 /* Pick a block from the worklist. */
3798 block = worklist[--sp];
3800 /* Initially, the set of available values in BLOCK is that of
3801 its immediate dominator. */
3802 dom = get_immediate_dominator (CDI_DOMINATORS, block);
3804 bitmap_set_copy (AVAIL_OUT (block), AVAIL_OUT (dom));
3806 /* Generate values for PHI nodes. */
3807 for (gsi = gsi_start_phis (block); !gsi_end_p (gsi); gsi_next (&gsi))
3808 make_values_for_phi (gsi_stmt (gsi), block);
3810 BB_MAY_NOTRETURN (block) = 0;
3812 /* Now compute value numbers and populate value sets with all
3813 the expressions computed in BLOCK. */
3814 for (gsi = gsi_start_bb (block); !gsi_end_p (gsi); gsi_next (&gsi))
3819 stmt = gsi_stmt (gsi);
3820 gimple_set_uid (stmt, stmt_uid++);
3822 /* Cache whether the basic-block has any non-visible side-effect
3824 If this isn't a call or it is the last stmt in the
3825 basic-block then the CFG represents things correctly. */
3826 if (is_gimple_call (stmt)
3827 && !stmt_ends_bb_p (stmt))
3829 /* Non-looping const functions always return normally.
3830 Otherwise the call might not return or have side-effects
3831 that forbids hoisting possibly trapping expressions
3833 int flags = gimple_call_flags (stmt);
3834 if (!(flags & ECF_CONST)
3835 || (flags & ECF_LOOPING_CONST_OR_PURE))
3836 BB_MAY_NOTRETURN (block) = 1;
3839 FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_DEF)
3841 pre_expr e = get_or_alloc_expr_for_name (op);
3843 add_to_value (get_expr_value_id (e), e);
3845 bitmap_insert_into_set (TMP_GEN (block), e);
3846 bitmap_value_insert_into_set (AVAIL_OUT (block), e);
3849 if (gimple_has_volatile_ops (stmt)
3850 || stmt_could_throw_p (stmt))
3853 switch (gimple_code (stmt))
3856 FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_USE)
3857 add_to_exp_gen (block, op);
3864 vn_reference_op_t vro;
3865 pre_expr result = NULL;
3866 VEC(vn_reference_op_s, heap) *ops = NULL;
3868 if (!can_value_number_call (stmt))
3871 copy_reference_ops_from_call (stmt, &ops);
3872 vn_reference_lookup_pieces (gimple_vuse (stmt), 0,
3873 gimple_expr_type (stmt),
3875 VEC_free (vn_reference_op_s, heap, ops);
3879 for (i = 0; VEC_iterate (vn_reference_op_s,
3883 if (vro->op0 && TREE_CODE (vro->op0) == SSA_NAME)
3884 add_to_exp_gen (block, vro->op0);
3885 if (vro->op1 && TREE_CODE (vro->op1) == SSA_NAME)
3886 add_to_exp_gen (block, vro->op1);
3887 if (vro->op2 && TREE_CODE (vro->op2) == SSA_NAME)
3888 add_to_exp_gen (block, vro->op2);
3890 result = (pre_expr) pool_alloc (pre_expr_pool);
3891 result->kind = REFERENCE;
3893 PRE_EXPR_REFERENCE (result) = ref;
3895 get_or_alloc_expression_id (result);
3896 add_to_value (get_expr_value_id (result), result);
3898 bitmap_value_insert_into_set (EXP_GEN (block), result);
3904 pre_expr result = NULL;
3905 switch (TREE_CODE_CLASS (gimple_assign_rhs_code (stmt)))
3909 case tcc_comparison:
3914 vn_nary_op_lookup_pieces (gimple_num_ops (stmt) - 1,
3915 gimple_assign_rhs_code (stmt),
3916 gimple_expr_type (stmt),
3917 gimple_assign_rhs1 (stmt),
3918 gimple_assign_rhs2 (stmt),
3919 NULL_TREE, NULL_TREE, &nary);
3924 for (i = 0; i < nary->length; i++)
3925 if (TREE_CODE (nary->op[i]) == SSA_NAME)
3926 add_to_exp_gen (block, nary->op[i]);
3928 result = (pre_expr) pool_alloc (pre_expr_pool);
3929 result->kind = NARY;
3931 PRE_EXPR_NARY (result) = nary;
3935 case tcc_declaration:
3940 vn_reference_op_t vro;
3942 vn_reference_lookup (gimple_assign_rhs1 (stmt),
3948 for (i = 0; VEC_iterate (vn_reference_op_s,
3952 if (vro->op0 && TREE_CODE (vro->op0) == SSA_NAME)
3953 add_to_exp_gen (block, vro->op0);
3954 if (vro->op1 && TREE_CODE (vro->op1) == SSA_NAME)
3955 add_to_exp_gen (block, vro->op1);
3956 if (vro->op2 && TREE_CODE (vro->op2) == SSA_NAME)
3957 add_to_exp_gen (block, vro->op2);
3959 result = (pre_expr) pool_alloc (pre_expr_pool);
3960 result->kind = REFERENCE;
3962 PRE_EXPR_REFERENCE (result) = ref;
3967 /* For any other statement that we don't
3968 recognize, simply add all referenced
3969 SSA_NAMEs to EXP_GEN. */
3970 FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_USE)
3971 add_to_exp_gen (block, op);
3975 get_or_alloc_expression_id (result);
3976 add_to_value (get_expr_value_id (result), result);
3978 bitmap_value_insert_into_set (EXP_GEN (block), result);
3987 /* Put the dominator children of BLOCK on the worklist of blocks
3988 to compute available sets for. */
3989 for (son = first_dom_son (CDI_DOMINATORS, block);
3991 son = next_dom_son (CDI_DOMINATORS, son))
3992 worklist[sp++] = son;
3998 /* Insert the expression for SSA_VN that SCCVN thought would be simpler
3999 than the available expressions for it. The insertion point is
4000 right before the first use in STMT. Returns the SSA_NAME that should
4001 be used for replacement. */
4004 do_SCCVN_insertion (gimple stmt, tree ssa_vn)
4006 basic_block bb = gimple_bb (stmt);
4007 gimple_stmt_iterator gsi;
4008 gimple_seq stmts = NULL;
4012 /* First create a value expression from the expression we want
4013 to insert and associate it with the value handle for SSA_VN. */
4014 e = get_or_alloc_expr_for (vn_get_expr_for (ssa_vn));
4018 /* Then use create_expression_by_pieces to generate a valid
4019 expression to insert at this point of the IL stream. */
4020 expr = create_expression_by_pieces (bb, e, &stmts, stmt, NULL);
4021 if (expr == NULL_TREE)
4023 gsi = gsi_for_stmt (stmt);
4024 gsi_insert_seq_before (&gsi, stmts, GSI_SAME_STMT);
4029 /* Eliminate fully redundant computations. */
4034 VEC (gimple, heap) *to_remove = NULL;
4036 unsigned int todo = 0;
4037 gimple_stmt_iterator gsi;
4043 for (gsi = gsi_start_bb (b); !gsi_end_p (gsi); gsi_next (&gsi))
4045 stmt = gsi_stmt (gsi);
4047 /* Lookup the RHS of the expression, see if we have an
4048 available computation for it. If so, replace the RHS with
4049 the available computation. */
4050 if (gimple_has_lhs (stmt)
4051 && TREE_CODE (gimple_get_lhs (stmt)) == SSA_NAME
4052 && !gimple_assign_ssa_name_copy_p (stmt)
4053 && (!gimple_assign_single_p (stmt)
4054 || !is_gimple_min_invariant (gimple_assign_rhs1 (stmt)))
4055 && !gimple_has_volatile_ops (stmt)
4056 && !has_zero_uses (gimple_get_lhs (stmt)))
4058 tree lhs = gimple_get_lhs (stmt);
4059 tree rhs = NULL_TREE;
4061 pre_expr lhsexpr = get_or_alloc_expr_for_name (lhs);
4062 pre_expr sprimeexpr;
4064 if (gimple_assign_single_p (stmt))
4065 rhs = gimple_assign_rhs1 (stmt);
4067 sprimeexpr = bitmap_find_leader (AVAIL_OUT (b),
4068 get_expr_value_id (lhsexpr),
4073 if (sprimeexpr->kind == CONSTANT)
4074 sprime = PRE_EXPR_CONSTANT (sprimeexpr);
4075 else if (sprimeexpr->kind == NAME)
4076 sprime = PRE_EXPR_NAME (sprimeexpr);
4081 /* If there is no existing leader but SCCVN knows this
4082 value is constant, use that constant. */
4083 if (!sprime && is_gimple_min_invariant (VN_INFO (lhs)->valnum))
4085 sprime = VN_INFO (lhs)->valnum;
4086 if (!useless_type_conversion_p (TREE_TYPE (lhs),
4087 TREE_TYPE (sprime)))
4088 sprime = fold_convert (TREE_TYPE (lhs), sprime);
4090 if (dump_file && (dump_flags & TDF_DETAILS))
4092 fprintf (dump_file, "Replaced ");
4093 print_gimple_expr (dump_file, stmt, 0, 0);
4094 fprintf (dump_file, " with ");
4095 print_generic_expr (dump_file, sprime, 0);
4096 fprintf (dump_file, " in ");
4097 print_gimple_stmt (dump_file, stmt, 0, 0);
4099 pre_stats.eliminations++;
4100 propagate_tree_value_into_stmt (&gsi, sprime);
4101 stmt = gsi_stmt (gsi);
4106 /* If there is no existing usable leader but SCCVN thinks
4107 it has an expression it wants to use as replacement,
4109 if (!sprime || sprime == lhs)
4111 tree val = VN_INFO (lhs)->valnum;
4113 && TREE_CODE (val) == SSA_NAME
4114 && VN_INFO (val)->needs_insertion
4115 && can_PRE_operation (vn_get_expr_for (val)))
4116 sprime = do_SCCVN_insertion (stmt, val);
4120 && (rhs == NULL_TREE
4121 || TREE_CODE (rhs) != SSA_NAME
4122 || may_propagate_copy (rhs, sprime)))
4124 gcc_assert (sprime != rhs);
4126 if (dump_file && (dump_flags & TDF_DETAILS))
4128 fprintf (dump_file, "Replaced ");
4129 print_gimple_expr (dump_file, stmt, 0, 0);
4130 fprintf (dump_file, " with ");
4131 print_generic_expr (dump_file, sprime, 0);
4132 fprintf (dump_file, " in ");
4133 print_gimple_stmt (dump_file, stmt, 0, 0);
4136 if (TREE_CODE (sprime) == SSA_NAME)
4137 gimple_set_plf (SSA_NAME_DEF_STMT (sprime),
4139 /* We need to make sure the new and old types actually match,
4140 which may require adding a simple cast, which fold_convert
4142 if ((!rhs || TREE_CODE (rhs) != SSA_NAME)
4143 && !useless_type_conversion_p (gimple_expr_type (stmt),
4144 TREE_TYPE (sprime)))
4145 sprime = fold_convert (gimple_expr_type (stmt), sprime);
4147 pre_stats.eliminations++;
4148 propagate_tree_value_into_stmt (&gsi, sprime);
4149 stmt = gsi_stmt (gsi);
4152 /* If we removed EH side effects from the statement, clean
4153 its EH information. */
4154 if (maybe_clean_or_replace_eh_stmt (stmt, stmt))
4156 bitmap_set_bit (need_eh_cleanup,
4157 gimple_bb (stmt)->index);
4158 if (dump_file && (dump_flags & TDF_DETAILS))
4159 fprintf (dump_file, " Removed EH side effects.\n");
4163 /* If the statement is a scalar store, see if the expression
4164 has the same value number as its rhs. If so, the store is
4166 else if (gimple_assign_single_p (stmt)
4167 && !is_gimple_reg (gimple_assign_lhs (stmt))
4168 && (TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME
4169 || is_gimple_min_invariant (gimple_assign_rhs1 (stmt))))
4171 tree rhs = gimple_assign_rhs1 (stmt);
4173 val = vn_reference_lookup (gimple_assign_lhs (stmt),
4174 gimple_vuse (stmt), true, NULL);
4175 if (TREE_CODE (rhs) == SSA_NAME)
4176 rhs = VN_INFO (rhs)->valnum;
4178 && operand_equal_p (val, rhs, 0))
4180 if (dump_file && (dump_flags & TDF_DETAILS))
4182 fprintf (dump_file, "Deleted redundant store ");
4183 print_gimple_stmt (dump_file, stmt, 0, 0);
4186 /* Queue stmt for removal. */
4187 VEC_safe_push (gimple, heap, to_remove, stmt);
4190 /* Visit COND_EXPRs and fold the comparison with the
4191 available value-numbers. */
4192 else if (gimple_code (stmt) == GIMPLE_COND)
4194 tree op0 = gimple_cond_lhs (stmt);
4195 tree op1 = gimple_cond_rhs (stmt);
4198 if (TREE_CODE (op0) == SSA_NAME)
4199 op0 = VN_INFO (op0)->valnum;
4200 if (TREE_CODE (op1) == SSA_NAME)
4201 op1 = VN_INFO (op1)->valnum;
4202 result = fold_binary (gimple_cond_code (stmt), boolean_type_node,
4204 if (result && TREE_CODE (result) == INTEGER_CST)
4206 if (integer_zerop (result))
4207 gimple_cond_make_false (stmt);
4209 gimple_cond_make_true (stmt);
4211 todo = TODO_cleanup_cfg;
4214 /* Visit indirect calls and turn them into direct calls if
4216 if (gimple_code (stmt) == GIMPLE_CALL
4217 && TREE_CODE (gimple_call_fn (stmt)) == SSA_NAME)
4219 tree fn = VN_INFO (gimple_call_fn (stmt))->valnum;
4220 if (TREE_CODE (fn) == ADDR_EXPR
4221 && TREE_CODE (TREE_OPERAND (fn, 0)) == FUNCTION_DECL)
4223 if (dump_file && (dump_flags & TDF_DETAILS))
4225 fprintf (dump_file, "Replacing call target with ");
4226 print_generic_expr (dump_file, fn, 0);
4227 fprintf (dump_file, " in ");
4228 print_gimple_stmt (dump_file, stmt, 0, 0);
4231 gimple_call_set_fn (stmt, fn);
4233 if (maybe_clean_or_replace_eh_stmt (stmt, stmt))
4235 bitmap_set_bit (need_eh_cleanup,
4236 gimple_bb (stmt)->index);
4237 if (dump_file && (dump_flags & TDF_DETAILS))
4238 fprintf (dump_file, " Removed EH side effects.\n");
4241 /* Changing an indirect call to a direct call may
4242 have exposed different semantics. This may
4243 require an SSA update. */
4244 todo |= TODO_update_ssa_only_virtuals;
4249 for (gsi = gsi_start_phis (b); !gsi_end_p (gsi);)
4251 gimple stmt, phi = gsi_stmt (gsi);
4252 tree sprime = NULL_TREE, res = PHI_RESULT (phi);
4253 pre_expr sprimeexpr, resexpr;
4254 gimple_stmt_iterator gsi2;
4256 /* We want to perform redundant PHI elimination. Do so by
4257 replacing the PHI with a single copy if possible.
4258 Do not touch inserted, single-argument or virtual PHIs. */
4259 if (gimple_phi_num_args (phi) == 1
4260 || !is_gimple_reg (res)
4261 || bitmap_bit_p (inserted_phi_names, SSA_NAME_VERSION (res)))
4267 resexpr = get_or_alloc_expr_for_name (res);
4268 sprimeexpr = bitmap_find_leader (AVAIL_OUT (b),
4269 get_expr_value_id (resexpr), NULL);
4272 if (sprimeexpr->kind == CONSTANT)
4273 sprime = PRE_EXPR_CONSTANT (sprimeexpr);
4274 else if (sprimeexpr->kind == NAME)
4275 sprime = PRE_EXPR_NAME (sprimeexpr);
4286 if (dump_file && (dump_flags & TDF_DETAILS))
4288 fprintf (dump_file, "Replaced redundant PHI node defining ");
4289 print_generic_expr (dump_file, res, 0);
4290 fprintf (dump_file, " with ");
4291 print_generic_expr (dump_file, sprime, 0);
4292 fprintf (dump_file, "\n");
4295 remove_phi_node (&gsi, false);
4297 if (!useless_type_conversion_p (TREE_TYPE (res), TREE_TYPE (sprime)))
4298 sprime = fold_convert (TREE_TYPE (res), sprime);
4299 stmt = gimple_build_assign (res, sprime);
4300 SSA_NAME_DEF_STMT (res) = stmt;
4301 if (TREE_CODE (sprime) == SSA_NAME)
4302 gimple_set_plf (SSA_NAME_DEF_STMT (sprime),
4304 gsi2 = gsi_after_labels (b);
4305 gsi_insert_before (&gsi2, stmt, GSI_NEW_STMT);
4306 /* Queue the copy for eventual removal. */
4307 VEC_safe_push (gimple, heap, to_remove, stmt);
4308 pre_stats.eliminations++;
4312 /* We cannot remove stmts during BB walk, especially not release SSA
4313 names there as this confuses the VN machinery. The stmts ending
4314 up in to_remove are either stores or simple copies. */
4315 for (i = 0; VEC_iterate (gimple, to_remove, i, stmt); ++i)
4317 tree lhs = gimple_assign_lhs (stmt);
4318 use_operand_p use_p;
4321 /* If there is a single use only, propagate the equivalency
4322 instead of keeping the copy. */
4323 if (TREE_CODE (lhs) == SSA_NAME
4324 && single_imm_use (lhs, &use_p, &use_stmt)
4325 && may_propagate_copy (USE_FROM_PTR (use_p),
4326 gimple_assign_rhs1 (stmt)))
4328 SET_USE (use_p, gimple_assign_rhs1 (stmt));
4329 update_stmt (use_stmt);
4332 /* If this is a store or a now unused copy, remove it. */
4333 if (TREE_CODE (lhs) != SSA_NAME
4334 || has_zero_uses (lhs))
4336 gsi = gsi_for_stmt (stmt);
4337 unlink_stmt_vdef (stmt);
4338 gsi_remove (&gsi, true);
4339 release_defs (stmt);
4342 VEC_free (gimple, heap, to_remove);
4347 /* Borrow a bit of tree-ssa-dce.c for the moment.
4348 XXX: In 4.1, we should be able to just run a DCE pass after PRE, though
4349 this may be a bit faster, and we may want critical edges kept split. */
4351 /* If OP's defining statement has not already been determined to be necessary,
4352 mark that statement necessary. Return the stmt, if it is newly
4355 static inline gimple
4356 mark_operand_necessary (tree op)
4362 if (TREE_CODE (op) != SSA_NAME)
4365 stmt = SSA_NAME_DEF_STMT (op);
4368 if (gimple_plf (stmt, NECESSARY)
4369 || gimple_nop_p (stmt))
4372 gimple_set_plf (stmt, NECESSARY, true);
4376 /* Because we don't follow exactly the standard PRE algorithm, and decide not
4377 to insert PHI nodes sometimes, and because value numbering of casts isn't
4378 perfect, we sometimes end up inserting dead code. This simple DCE-like
4379 pass removes any insertions we made that weren't actually used. */
4382 remove_dead_inserted_code (void)
4384 VEC(gimple,heap) *worklist = NULL;
4388 worklist = VEC_alloc (gimple, heap, VEC_length (gimple, inserted_exprs));
4389 for (i = 0; VEC_iterate (gimple, inserted_exprs, i, t); i++)
4391 if (gimple_plf (t, NECESSARY))
4392 VEC_quick_push (gimple, worklist, t);
4394 while (VEC_length (gimple, worklist) > 0)
4396 t = VEC_pop (gimple, worklist);
4398 /* PHI nodes are somewhat special in that each PHI alternative has
4399 data and control dependencies. All the statements feeding the
4400 PHI node's arguments are always necessary. */
4401 if (gimple_code (t) == GIMPLE_PHI)
4405 VEC_reserve (gimple, heap, worklist, gimple_phi_num_args (t));
4406 for (k = 0; k < gimple_phi_num_args (t); k++)
4408 tree arg = PHI_ARG_DEF (t, k);
4409 if (TREE_CODE (arg) == SSA_NAME)
4411 gimple n = mark_operand_necessary (arg);
4413 VEC_quick_push (gimple, worklist, n);
4419 /* Propagate through the operands. Examine all the USE, VUSE and
4420 VDEF operands in this statement. Mark all the statements
4421 which feed this statement's uses as necessary. */
4425 /* The operands of VDEF expressions are also needed as they
4426 represent potential definitions that may reach this
4427 statement (VDEF operands allow us to follow def-def
4430 FOR_EACH_SSA_TREE_OPERAND (use, t, iter, SSA_OP_ALL_USES)
4432 gimple n = mark_operand_necessary (use);
4434 VEC_safe_push (gimple, heap, worklist, n);
4439 for (i = 0; VEC_iterate (gimple, inserted_exprs, i, t); i++)
4441 if (!gimple_plf (t, NECESSARY))
4443 gimple_stmt_iterator gsi;
4445 if (dump_file && (dump_flags & TDF_DETAILS))
4447 fprintf (dump_file, "Removing unnecessary insertion:");
4448 print_gimple_stmt (dump_file, t, 0, 0);
4451 gsi = gsi_for_stmt (t);
4452 if (gimple_code (t) == GIMPLE_PHI)
4453 remove_phi_node (&gsi, true);
4456 gsi_remove (&gsi, true);
4461 VEC_free (gimple, heap, worklist);
4464 /* Initialize data structures used by PRE. */
4467 init_pre (bool do_fre)
4471 next_expression_id = 1;
4473 VEC_safe_push (pre_expr, heap, expressions, NULL);
4474 value_expressions = VEC_alloc (bitmap_set_t, heap, get_max_value_id () + 1);
4475 VEC_safe_grow_cleared (bitmap_set_t, heap, value_expressions,
4476 get_max_value_id() + 1);
4480 inserted_exprs = NULL;
4481 need_creation = NULL;
4482 pretemp = NULL_TREE;
4483 storetemp = NULL_TREE;
4484 prephitemp = NULL_TREE;
4486 connect_infinite_loops_to_exit ();
4487 memset (&pre_stats, 0, sizeof (pre_stats));
4490 postorder = XNEWVEC (int, n_basic_blocks - NUM_FIXED_BLOCKS);
4491 post_order_compute (postorder, false, false);
4494 bb->aux = XCNEWVEC (struct bb_bitmap_sets, 1);
4496 calculate_dominance_info (CDI_POST_DOMINATORS);
4497 calculate_dominance_info (CDI_DOMINATORS);
4499 bitmap_obstack_initialize (&grand_bitmap_obstack);
4500 inserted_phi_names = BITMAP_ALLOC (&grand_bitmap_obstack);
4501 phi_translate_table = htab_create (5110, expr_pred_trans_hash,
4502 expr_pred_trans_eq, free);
4503 expression_to_id = htab_create (num_ssa_names * 3,
4506 bitmap_set_pool = create_alloc_pool ("Bitmap sets",
4507 sizeof (struct bitmap_set), 30);
4508 pre_expr_pool = create_alloc_pool ("pre_expr nodes",
4509 sizeof (struct pre_expr_d), 30);
4512 EXP_GEN (bb) = bitmap_set_new ();
4513 PHI_GEN (bb) = bitmap_set_new ();
4514 TMP_GEN (bb) = bitmap_set_new ();
4515 AVAIL_OUT (bb) = bitmap_set_new ();
4518 need_eh_cleanup = BITMAP_ALLOC (NULL);
4522 /* Deallocate data structures used by PRE. */
4525 fini_pre (bool do_fre)
4530 VEC_free (bitmap_set_t, heap, value_expressions);
4531 VEC_free (gimple, heap, inserted_exprs);
4532 VEC_free (gimple, heap, need_creation);
4533 bitmap_obstack_release (&grand_bitmap_obstack);
4534 free_alloc_pool (bitmap_set_pool);
4535 free_alloc_pool (pre_expr_pool);
4536 htab_delete (phi_translate_table);
4537 htab_delete (expression_to_id);
4545 free_dominance_info (CDI_POST_DOMINATORS);
4547 if (!bitmap_empty_p (need_eh_cleanup))
4549 gimple_purge_all_dead_eh_edges (need_eh_cleanup);
4550 cleanup_tree_cfg ();
4553 BITMAP_FREE (need_eh_cleanup);
4556 loop_optimizer_finalize ();
4559 /* Main entry point to the SSA-PRE pass. DO_FRE is true if the caller
4560 only wants to do full redundancy elimination. */
4563 execute_pre (bool do_fre)
4565 unsigned int todo = 0;
4567 do_partial_partial = optimize > 2 && optimize_function_for_speed_p (cfun);
4569 /* This has to happen before SCCVN runs because
4570 loop_optimizer_init may create new phis, etc. */
4572 loop_optimizer_init (LOOPS_NORMAL);
4574 if (!run_scc_vn (do_fre))
4578 remove_dead_inserted_code ();
4579 loop_optimizer_finalize ();
4588 /* Collect and value number expressions computed in each basic block. */
4591 if (dump_file && (dump_flags & TDF_DETAILS))
4597 print_bitmap_set (dump_file, EXP_GEN (bb), "exp_gen", bb->index);
4598 print_bitmap_set (dump_file, PHI_GEN (bb), "phi_gen", bb->index);
4599 print_bitmap_set (dump_file, TMP_GEN (bb), "tmp_gen", bb->index);
4600 print_bitmap_set (dump_file, AVAIL_OUT (bb), "avail_out", bb->index);
4604 /* Insert can get quite slow on an incredibly large number of basic
4605 blocks due to some quadratic behavior. Until this behavior is
4606 fixed, don't run it when he have an incredibly large number of
4607 bb's. If we aren't going to run insert, there is no point in
4608 computing ANTIC, either, even though it's plenty fast. */
4609 if (!do_fre && n_basic_blocks < 4000)
4615 /* Remove all the redundant expressions. */
4616 todo |= eliminate ();
4618 statistics_counter_event (cfun, "Insertions", pre_stats.insertions);
4619 statistics_counter_event (cfun, "PA inserted", pre_stats.pa_insert);
4620 statistics_counter_event (cfun, "New PHIs", pre_stats.phis);
4621 statistics_counter_event (cfun, "Eliminated", pre_stats.eliminations);
4622 statistics_counter_event (cfun, "Constified", pre_stats.constified);
4624 /* Make sure to remove fake edges before committing our inserts.
4625 This makes sure we don't end up with extra critical edges that
4626 we would need to split. */
4627 remove_fake_exit_edges ();
4628 gsi_commit_edge_inserts ();
4630 clear_expression_ids ();
4633 remove_dead_inserted_code ();
4641 /* Gate and execute functions for PRE. */
4646 return execute_pre (false);
4652 return flag_tree_pre != 0;
4655 struct gimple_opt_pass pass_pre =
4660 gate_pre, /* gate */
4661 do_pre, /* execute */
4664 0, /* static_pass_number */
4665 TV_TREE_PRE, /* tv_id */
4666 PROP_no_crit_edges | PROP_cfg
4667 | PROP_ssa, /* properties_required */
4668 0, /* properties_provided */
4669 0, /* properties_destroyed */
4670 TODO_rebuild_alias, /* todo_flags_start */
4671 TODO_update_ssa_only_virtuals | TODO_dump_func | TODO_ggc_collect
4672 | TODO_verify_ssa /* todo_flags_finish */
4677 /* Gate and execute functions for FRE. */
4682 return execute_pre (true);
4688 return flag_tree_fre != 0;
4691 struct gimple_opt_pass pass_fre =
4696 gate_fre, /* gate */
4697 execute_fre, /* execute */
4700 0, /* static_pass_number */
4701 TV_TREE_FRE, /* tv_id */
4702 PROP_cfg | PROP_ssa, /* properties_required */
4703 0, /* properties_provided */
4704 0, /* properties_destroyed */
4705 0, /* todo_flags_start */
4706 TODO_dump_func | TODO_ggc_collect | TODO_verify_ssa /* todo_flags_finish */