Merge branch 'vendor/GCC50' - gcc 5.0 snapshot 1 FEB 2015
[dragonfly.git] / contrib / gcc-5.0 / gcc / tree-ssa-pre.c
1 /* SSA-PRE for trees.
2    Copyright (C) 2001-2015 Free Software Foundation, Inc.
3    Contributed by Daniel Berlin <dan@dberlin.org> and Steven Bosscher
4    <stevenb@suse.de>
5
6 This file is part of GCC.
7
8 GCC is free software; you can redistribute it and/or modify
9 it under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 3, or (at your option)
11 any later version.
12
13 GCC is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
16 GNU General Public License for more details.
17
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3.  If not see
20 <http://www.gnu.org/licenses/>.  */
21
22 #include "config.h"
23 #include "system.h"
24 #include "coretypes.h"
25 #include "tm.h"
26 #include "hash-set.h"
27 #include "machmode.h"
28 #include "vec.h"
29 #include "double-int.h"
30 #include "input.h"
31 #include "alias.h"
32 #include "symtab.h"
33 #include "wide-int.h"
34 #include "inchash.h"
35 #include "tree.h"
36 #include "fold-const.h"
37 #include "predict.h"
38 #include "hard-reg-set.h"
39 #include "function.h"
40 #include "dominance.h"
41 #include "cfg.h"
42 #include "cfganal.h"
43 #include "basic-block.h"
44 #include "gimple-pretty-print.h"
45 #include "tree-inline.h"
46 #include "hash-table.h"
47 #include "tree-ssa-alias.h"
48 #include "internal-fn.h"
49 #include "gimple-fold.h"
50 #include "tree-eh.h"
51 #include "gimple-expr.h"
52 #include "is-a.h"
53 #include "gimple.h"
54 #include "gimplify.h"
55 #include "gimple-iterator.h"
56 #include "gimplify-me.h"
57 #include "gimple-ssa.h"
58 #include "tree-cfg.h"
59 #include "tree-phinodes.h"
60 #include "ssa-iterators.h"
61 #include "stringpool.h"
62 #include "tree-ssanames.h"
63 #include "tree-ssa-loop.h"
64 #include "tree-into-ssa.h"
65 #include "hashtab.h"
66 #include "rtl.h"
67 #include "flags.h"
68 #include "statistics.h"
69 #include "real.h"
70 #include "fixed-value.h"
71 #include "insn-config.h"
72 #include "expmed.h"
73 #include "dojump.h"
74 #include "explow.h"
75 #include "calls.h"
76 #include "emit-rtl.h"
77 #include "varasm.h"
78 #include "stmt.h"
79 #include "expr.h"
80 #include "tree-dfa.h"
81 #include "tree-ssa.h"
82 #include "tree-iterator.h"
83 #include "alloc-pool.h"
84 #include "obstack.h"
85 #include "tree-pass.h"
86 #include "langhooks.h"
87 #include "cfgloop.h"
88 #include "tree-ssa-sccvn.h"
89 #include "tree-scalar-evolution.h"
90 #include "params.h"
91 #include "dbgcnt.h"
92 #include "domwalk.h"
93 #include "hash-map.h"
94 #include "plugin-api.h"
95 #include "ipa-ref.h"
96 #include "cgraph.h"
97 #include "symbol-summary.h"
98 #include "ipa-prop.h"
99 #include "tree-ssa-propagate.h"
100 #include "ipa-utils.h"
101
102 /* TODO:
103
104    1. Avail sets can be shared by making an avail_find_leader that
105       walks up the dominator tree and looks in those avail sets.
106       This might affect code optimality, it's unclear right now.
107    2. Strength reduction can be performed by anticipating expressions
108       we can repair later on.
109    3. We can do back-substitution or smarter value numbering to catch
110       commutative expressions split up over multiple statements.
111 */
112
113 /* For ease of terminology, "expression node" in the below refers to
114    every expression node but GIMPLE_ASSIGN, because GIMPLE_ASSIGNs
115    represent the actual statement containing the expressions we care about,
116    and we cache the value number by putting it in the expression.  */
117
118 /* Basic algorithm
119
120    First we walk the statements to generate the AVAIL sets, the
121    EXP_GEN sets, and the tmp_gen sets.  EXP_GEN sets represent the
122    generation of values/expressions by a given block.  We use them
123    when computing the ANTIC sets.  The AVAIL sets consist of
124    SSA_NAME's that represent values, so we know what values are
125    available in what blocks.  AVAIL is a forward dataflow problem.  In
126    SSA, values are never killed, so we don't need a kill set, or a
127    fixpoint iteration, in order to calculate the AVAIL sets.  In
128    traditional parlance, AVAIL sets tell us the downsafety of the
129    expressions/values.
130
131    Next, we generate the ANTIC sets.  These sets represent the
132    anticipatable expressions.  ANTIC is a backwards dataflow
133    problem.  An expression is anticipatable in a given block if it could
134    be generated in that block.  This means that if we had to perform
135    an insertion in that block, of the value of that expression, we
136    could.  Calculating the ANTIC sets requires phi translation of
137    expressions, because the flow goes backwards through phis.  We must
138    iterate to a fixpoint of the ANTIC sets, because we have a kill
139    set.  Even in SSA form, values are not live over the entire
140    function, only from their definition point onwards.  So we have to
141    remove values from the ANTIC set once we go past the definition
142    point of the leaders that make them up.
143    compute_antic/compute_antic_aux performs this computation.
144
145    Third, we perform insertions to make partially redundant
146    expressions fully redundant.
147
148    An expression is partially redundant (excluding partial
149    anticipation) if:
150
151    1. It is AVAIL in some, but not all, of the predecessors of a
152       given block.
153    2. It is ANTIC in all the predecessors.
154
155    In order to make it fully redundant, we insert the expression into
156    the predecessors where it is not available, but is ANTIC.
157
158    For the partial anticipation case, we only perform insertion if it
159    is partially anticipated in some block, and fully available in all
160    of the predecessors.
161
162    insert/insert_aux/do_regular_insertion/do_partial_partial_insertion
163    performs these steps.
164
165    Fourth, we eliminate fully redundant expressions.
166    This is a simple statement walk that replaces redundant
167    calculations with the now available values.  */
168
169 /* Representations of value numbers:
170
171    Value numbers are represented by a representative SSA_NAME.  We
172    will create fake SSA_NAME's in situations where we need a
173    representative but do not have one (because it is a complex
174    expression).  In order to facilitate storing the value numbers in
175    bitmaps, and keep the number of wasted SSA_NAME's down, we also
176    associate a value_id with each value number, and create full blown
177    ssa_name's only where we actually need them (IE in operands of
178    existing expressions).
179
180    Theoretically you could replace all the value_id's with
181    SSA_NAME_VERSION, but this would allocate a large number of
182    SSA_NAME's (which are each > 30 bytes) just to get a 4 byte number.
183    It would also require an additional indirection at each point we
184    use the value id.  */
185
186 /* Representation of expressions on value numbers:
187
188    Expressions consisting of value numbers are represented the same
189    way as our VN internally represents them, with an additional
190    "pre_expr" wrapping around them in order to facilitate storing all
191    of the expressions in the same sets.  */
192
193 /* Representation of sets:
194
195    The dataflow sets do not need to be sorted in any particular order
196    for the majority of their lifetime, are simply represented as two
197    bitmaps, one that keeps track of values present in the set, and one
198    that keeps track of expressions present in the set.
199
200    When we need them in topological order, we produce it on demand by
201    transforming the bitmap into an array and sorting it into topo
202    order.  */
203
204 /* Type of expression, used to know which member of the PRE_EXPR union
205    is valid.  */
206
207 enum pre_expr_kind
208 {
209     NAME,
210     NARY,
211     REFERENCE,
212     CONSTANT
213 };
214
215 typedef union pre_expr_union_d
216 {
217   tree name;
218   tree constant;
219   vn_nary_op_t nary;
220   vn_reference_t reference;
221 } pre_expr_union;
222
223 typedef struct pre_expr_d : typed_noop_remove <pre_expr_d>
224 {
225   enum pre_expr_kind kind;
226   unsigned int id;
227   pre_expr_union u;
228
229   /* hash_table support.  */
230   typedef pre_expr_d value_type;
231   typedef pre_expr_d compare_type;
232   static inline hashval_t hash (const pre_expr_d *);
233   static inline int equal (const pre_expr_d *, const pre_expr_d *);
234 } *pre_expr;
235
236 #define PRE_EXPR_NAME(e) (e)->u.name
237 #define PRE_EXPR_NARY(e) (e)->u.nary
238 #define PRE_EXPR_REFERENCE(e) (e)->u.reference
239 #define PRE_EXPR_CONSTANT(e) (e)->u.constant
240
241 /* Compare E1 and E1 for equality.  */
242
243 inline int
244 pre_expr_d::equal (const value_type *e1, const compare_type *e2)
245 {
246   if (e1->kind != e2->kind)
247     return false;
248
249   switch (e1->kind)
250     {
251     case CONSTANT:
252       return vn_constant_eq_with_type (PRE_EXPR_CONSTANT (e1),
253                                        PRE_EXPR_CONSTANT (e2));
254     case NAME:
255       return PRE_EXPR_NAME (e1) == PRE_EXPR_NAME (e2);
256     case NARY:
257       return vn_nary_op_eq (PRE_EXPR_NARY (e1), PRE_EXPR_NARY (e2));
258     case REFERENCE:
259       return vn_reference_eq (PRE_EXPR_REFERENCE (e1),
260                               PRE_EXPR_REFERENCE (e2));
261     default:
262       gcc_unreachable ();
263     }
264 }
265
266 /* Hash E.  */
267
268 inline hashval_t
269 pre_expr_d::hash (const value_type *e)
270 {
271   switch (e->kind)
272     {
273     case CONSTANT:
274       return vn_hash_constant_with_type (PRE_EXPR_CONSTANT (e));
275     case NAME:
276       return SSA_NAME_VERSION (PRE_EXPR_NAME (e));
277     case NARY:
278       return PRE_EXPR_NARY (e)->hashcode;
279     case REFERENCE:
280       return PRE_EXPR_REFERENCE (e)->hashcode;
281     default:
282       gcc_unreachable ();
283     }
284 }
285
286 /* Next global expression id number.  */
287 static unsigned int next_expression_id;
288
289 /* Mapping from expression to id number we can use in bitmap sets.  */
290 static vec<pre_expr> expressions;
291 static hash_table<pre_expr_d> *expression_to_id;
292 static vec<unsigned> name_to_id;
293
294 /* Allocate an expression id for EXPR.  */
295
296 static inline unsigned int
297 alloc_expression_id (pre_expr expr)
298 {
299   struct pre_expr_d **slot;
300   /* Make sure we won't overflow. */
301   gcc_assert (next_expression_id + 1 > next_expression_id);
302   expr->id = next_expression_id++;
303   expressions.safe_push (expr);
304   if (expr->kind == NAME)
305     {
306       unsigned version = SSA_NAME_VERSION (PRE_EXPR_NAME (expr));
307       /* vec::safe_grow_cleared allocates no headroom.  Avoid frequent
308          re-allocations by using vec::reserve upfront.  */
309       unsigned old_len = name_to_id.length ();
310       name_to_id.reserve (num_ssa_names - old_len);
311       name_to_id.quick_grow_cleared (num_ssa_names);
312       gcc_assert (name_to_id[version] == 0);
313       name_to_id[version] = expr->id;
314     }
315   else
316     {
317       slot = expression_to_id->find_slot (expr, INSERT);
318       gcc_assert (!*slot);
319       *slot = expr;
320     }
321   return next_expression_id - 1;
322 }
323
324 /* Return the expression id for tree EXPR.  */
325
326 static inline unsigned int
327 get_expression_id (const pre_expr expr)
328 {
329   return expr->id;
330 }
331
332 static inline unsigned int
333 lookup_expression_id (const pre_expr expr)
334 {
335   struct pre_expr_d **slot;
336
337   if (expr->kind == NAME)
338     {
339       unsigned version = SSA_NAME_VERSION (PRE_EXPR_NAME (expr));
340       if (name_to_id.length () <= version)
341         return 0;
342       return name_to_id[version];
343     }
344   else
345     {
346       slot = expression_to_id->find_slot (expr, NO_INSERT);
347       if (!slot)
348         return 0;
349       return ((pre_expr)*slot)->id;
350     }
351 }
352
353 /* Return the existing expression id for EXPR, or create one if one
354    does not exist yet.  */
355
356 static inline unsigned int
357 get_or_alloc_expression_id (pre_expr expr)
358 {
359   unsigned int id = lookup_expression_id (expr);
360   if (id == 0)
361     return alloc_expression_id (expr);
362   return expr->id = id;
363 }
364
365 /* Return the expression that has expression id ID */
366
367 static inline pre_expr
368 expression_for_id (unsigned int id)
369 {
370   return expressions[id];
371 }
372
373 /* Free the expression id field in all of our expressions,
374    and then destroy the expressions array.  */
375
376 static void
377 clear_expression_ids (void)
378 {
379   expressions.release ();
380 }
381
382 static alloc_pool pre_expr_pool;
383
384 /* Given an SSA_NAME NAME, get or create a pre_expr to represent it.  */
385
386 static pre_expr
387 get_or_alloc_expr_for_name (tree name)
388 {
389   struct pre_expr_d expr;
390   pre_expr result;
391   unsigned int result_id;
392
393   expr.kind = NAME;
394   expr.id = 0;
395   PRE_EXPR_NAME (&expr) = name;
396   result_id = lookup_expression_id (&expr);
397   if (result_id != 0)
398     return expression_for_id (result_id);
399
400   result = (pre_expr) pool_alloc (pre_expr_pool);
401   result->kind = NAME;
402   PRE_EXPR_NAME (result) = name;
403   alloc_expression_id (result);
404   return result;
405 }
406
407 /* An unordered bitmap set.  One bitmap tracks values, the other,
408    expressions.  */
409 typedef struct bitmap_set
410 {
411   bitmap_head expressions;
412   bitmap_head values;
413 } *bitmap_set_t;
414
415 #define FOR_EACH_EXPR_ID_IN_SET(set, id, bi)            \
416   EXECUTE_IF_SET_IN_BITMAP (&(set)->expressions, 0, (id), (bi))
417
418 #define FOR_EACH_VALUE_ID_IN_SET(set, id, bi)           \
419   EXECUTE_IF_SET_IN_BITMAP (&(set)->values, 0, (id), (bi))
420
421 /* Mapping from value id to expressions with that value_id.  */
422 static vec<bitmap> value_expressions;
423
424 /* Sets that we need to keep track of.  */
425 typedef struct bb_bitmap_sets
426 {
427   /* The EXP_GEN set, which represents expressions/values generated in
428      a basic block.  */
429   bitmap_set_t exp_gen;
430
431   /* The PHI_GEN set, which represents PHI results generated in a
432      basic block.  */
433   bitmap_set_t phi_gen;
434
435   /* The TMP_GEN set, which represents results/temporaries generated
436      in a basic block. IE the LHS of an expression.  */
437   bitmap_set_t tmp_gen;
438
439   /* The AVAIL_OUT set, which represents which values are available in
440      a given basic block.  */
441   bitmap_set_t avail_out;
442
443   /* The ANTIC_IN set, which represents which values are anticipatable
444      in a given basic block.  */
445   bitmap_set_t antic_in;
446
447   /* The PA_IN set, which represents which values are
448      partially anticipatable in a given basic block.  */
449   bitmap_set_t pa_in;
450
451   /* The NEW_SETS set, which is used during insertion to augment the
452      AVAIL_OUT set of blocks with the new insertions performed during
453      the current iteration.  */
454   bitmap_set_t new_sets;
455
456   /* A cache for value_dies_in_block_x.  */
457   bitmap expr_dies;
458
459   /* The live virtual operand on successor edges.  */
460   tree vop_on_exit;
461
462   /* True if we have visited this block during ANTIC calculation.  */
463   unsigned int visited : 1;
464
465   /* True when the block contains a call that might not return.  */
466   unsigned int contains_may_not_return_call : 1;
467 } *bb_value_sets_t;
468
469 #define EXP_GEN(BB)     ((bb_value_sets_t) ((BB)->aux))->exp_gen
470 #define PHI_GEN(BB)     ((bb_value_sets_t) ((BB)->aux))->phi_gen
471 #define TMP_GEN(BB)     ((bb_value_sets_t) ((BB)->aux))->tmp_gen
472 #define AVAIL_OUT(BB)   ((bb_value_sets_t) ((BB)->aux))->avail_out
473 #define ANTIC_IN(BB)    ((bb_value_sets_t) ((BB)->aux))->antic_in
474 #define PA_IN(BB)       ((bb_value_sets_t) ((BB)->aux))->pa_in
475 #define NEW_SETS(BB)    ((bb_value_sets_t) ((BB)->aux))->new_sets
476 #define EXPR_DIES(BB)   ((bb_value_sets_t) ((BB)->aux))->expr_dies
477 #define BB_VISITED(BB)  ((bb_value_sets_t) ((BB)->aux))->visited
478 #define BB_MAY_NOTRETURN(BB) ((bb_value_sets_t) ((BB)->aux))->contains_may_not_return_call
479 #define BB_LIVE_VOP_ON_EXIT(BB) ((bb_value_sets_t) ((BB)->aux))->vop_on_exit
480
481
482 /* Basic block list in postorder.  */
483 static int *postorder;
484 static int postorder_num;
485
486 /* This structure is used to keep track of statistics on what
487    optimization PRE was able to perform.  */
488 static struct
489 {
490   /* The number of RHS computations eliminated by PRE.  */
491   int eliminations;
492
493   /* The number of new expressions/temporaries generated by PRE.  */
494   int insertions;
495
496   /* The number of inserts found due to partial anticipation  */
497   int pa_insert;
498
499   /* The number of new PHI nodes added by PRE.  */
500   int phis;
501 } pre_stats;
502
503 static bool do_partial_partial;
504 static pre_expr bitmap_find_leader (bitmap_set_t, unsigned int);
505 static void bitmap_value_insert_into_set (bitmap_set_t, pre_expr);
506 static void bitmap_value_replace_in_set (bitmap_set_t, pre_expr);
507 static void bitmap_set_copy (bitmap_set_t, bitmap_set_t);
508 static bool bitmap_set_contains_value (bitmap_set_t, unsigned int);
509 static void bitmap_insert_into_set (bitmap_set_t, pre_expr);
510 static void bitmap_insert_into_set_1 (bitmap_set_t, pre_expr,
511                                       unsigned int, bool);
512 static bitmap_set_t bitmap_set_new (void);
513 static tree create_expression_by_pieces (basic_block, pre_expr, gimple_seq *,
514                                          tree);
515 static tree find_or_generate_expression (basic_block, tree, gimple_seq *);
516 static unsigned int get_expr_value_id (pre_expr);
517
518 /* We can add and remove elements and entries to and from sets
519    and hash tables, so we use alloc pools for them.  */
520
521 static alloc_pool bitmap_set_pool;
522 static bitmap_obstack grand_bitmap_obstack;
523
524 /* Set of blocks with statements that have had their EH properties changed.  */
525 static bitmap need_eh_cleanup;
526
527 /* Set of blocks with statements that have had their AB properties changed.  */
528 static bitmap need_ab_cleanup;
529
530 /* A three tuple {e, pred, v} used to cache phi translations in the
531    phi_translate_table.  */
532
533 typedef struct expr_pred_trans_d : typed_free_remove<expr_pred_trans_d>
534 {
535   /* The expression.  */
536   pre_expr e;
537
538   /* The predecessor block along which we translated the expression.  */
539   basic_block pred;
540
541   /* The value that resulted from the translation.  */
542   pre_expr v;
543
544   /* The hashcode for the expression, pred pair. This is cached for
545      speed reasons.  */
546   hashval_t hashcode;
547
548   /* hash_table support.  */
549   typedef expr_pred_trans_d value_type;
550   typedef expr_pred_trans_d compare_type;
551   static inline hashval_t hash (const value_type *);
552   static inline int equal (const value_type *, const compare_type *);
553 } *expr_pred_trans_t;
554 typedef const struct expr_pred_trans_d *const_expr_pred_trans_t;
555
556 inline hashval_t
557 expr_pred_trans_d::hash (const expr_pred_trans_d *e)
558 {
559   return e->hashcode;
560 }
561
562 inline int
563 expr_pred_trans_d::equal (const value_type *ve1,
564                           const compare_type *ve2)
565 {
566   basic_block b1 = ve1->pred;
567   basic_block b2 = ve2->pred;
568
569   /* If they are not translations for the same basic block, they can't
570      be equal.  */
571   if (b1 != b2)
572     return false;
573   return pre_expr_d::equal (ve1->e, ve2->e);
574 }
575
576 /* The phi_translate_table caches phi translations for a given
577    expression and predecessor.  */
578 static hash_table<expr_pred_trans_d> *phi_translate_table;
579
580 /* Add the tuple mapping from {expression E, basic block PRED} to
581    the phi translation table and return whether it pre-existed.  */
582
583 static inline bool
584 phi_trans_add (expr_pred_trans_t *entry, pre_expr e, basic_block pred)
585 {
586   expr_pred_trans_t *slot;
587   expr_pred_trans_d tem;
588   hashval_t hash = iterative_hash_hashval_t (pre_expr_d::hash (e),
589                                              pred->index);
590   tem.e = e;
591   tem.pred = pred;
592   tem.hashcode = hash;
593   slot = phi_translate_table->find_slot_with_hash (&tem, hash, INSERT);
594   if (*slot)
595     {
596       *entry = *slot;
597       return true;
598     }
599
600   *entry = *slot = XNEW (struct expr_pred_trans_d);
601   (*entry)->e = e;
602   (*entry)->pred = pred;
603   (*entry)->hashcode = hash;
604   return false;
605 }
606
607
608 /* Add expression E to the expression set of value id V.  */
609
610 static void
611 add_to_value (unsigned int v, pre_expr e)
612 {
613   bitmap set;
614
615   gcc_checking_assert (get_expr_value_id (e) == v);
616
617   if (v >= value_expressions.length ())
618     {
619       value_expressions.safe_grow_cleared (v + 1);
620     }
621
622   set = value_expressions[v];
623   if (!set)
624     {
625       set = BITMAP_ALLOC (&grand_bitmap_obstack);
626       value_expressions[v] = set;
627     }
628
629   bitmap_set_bit (set, get_or_alloc_expression_id (e));
630 }
631
632 /* Create a new bitmap set and return it.  */
633
634 static bitmap_set_t
635 bitmap_set_new (void)
636 {
637   bitmap_set_t ret = (bitmap_set_t) pool_alloc (bitmap_set_pool);
638   bitmap_initialize (&ret->expressions, &grand_bitmap_obstack);
639   bitmap_initialize (&ret->values, &grand_bitmap_obstack);
640   return ret;
641 }
642
643 /* Return the value id for a PRE expression EXPR.  */
644
645 static unsigned int
646 get_expr_value_id (pre_expr expr)
647 {
648   unsigned int id;
649   switch (expr->kind)
650     {
651     case CONSTANT:
652       id = get_constant_value_id (PRE_EXPR_CONSTANT (expr));
653       break;
654     case NAME:
655       id = VN_INFO (PRE_EXPR_NAME (expr))->value_id;
656       break;
657     case NARY:
658       id = PRE_EXPR_NARY (expr)->value_id;
659       break;
660     case REFERENCE:
661       id = PRE_EXPR_REFERENCE (expr)->value_id;
662       break;
663     default:
664       gcc_unreachable ();
665     }
666   /* ???  We cannot assert that expr has a value-id (it can be 0), because
667      we assign value-ids only to expressions that have a result
668      in set_hashtable_value_ids.  */
669   return id;
670 }
671
672 /* Return a SCCVN valnum (SSA name or constant) for the PRE value-id VAL.  */
673
674 static tree
675 sccvn_valnum_from_value_id (unsigned int val)
676 {
677   bitmap_iterator bi;
678   unsigned int i;
679   bitmap exprset = value_expressions[val];
680   EXECUTE_IF_SET_IN_BITMAP (exprset, 0, i, bi)
681     {
682       pre_expr vexpr = expression_for_id (i);
683       if (vexpr->kind == NAME)
684         return VN_INFO (PRE_EXPR_NAME (vexpr))->valnum;
685       else if (vexpr->kind == CONSTANT)
686         return PRE_EXPR_CONSTANT (vexpr);
687     }
688   return NULL_TREE;
689 }
690
691 /* Remove an expression EXPR from a bitmapped set.  */
692
693 static void
694 bitmap_remove_from_set (bitmap_set_t set, pre_expr expr)
695 {
696   unsigned int val  = get_expr_value_id (expr);
697   if (!value_id_constant_p (val))
698     {
699       bitmap_clear_bit (&set->values, val);
700       bitmap_clear_bit (&set->expressions, get_expression_id (expr));
701     }
702 }
703
704 static void
705 bitmap_insert_into_set_1 (bitmap_set_t set, pre_expr expr,
706                           unsigned int val, bool allow_constants)
707 {
708   if (allow_constants || !value_id_constant_p (val))
709     {
710       /* We specifically expect this and only this function to be able to
711          insert constants into a set.  */
712       bitmap_set_bit (&set->values, val);
713       bitmap_set_bit (&set->expressions, get_or_alloc_expression_id (expr));
714     }
715 }
716
717 /* Insert an expression EXPR into a bitmapped set.  */
718
719 static void
720 bitmap_insert_into_set (bitmap_set_t set, pre_expr expr)
721 {
722   bitmap_insert_into_set_1 (set, expr, get_expr_value_id (expr), false);
723 }
724
725 /* Copy a bitmapped set ORIG, into bitmapped set DEST.  */
726
727 static void
728 bitmap_set_copy (bitmap_set_t dest, bitmap_set_t orig)
729 {
730   bitmap_copy (&dest->expressions, &orig->expressions);
731   bitmap_copy (&dest->values, &orig->values);
732 }
733
734
735 /* Free memory used up by SET.  */
736 static void
737 bitmap_set_free (bitmap_set_t set)
738 {
739   bitmap_clear (&set->expressions);
740   bitmap_clear (&set->values);
741 }
742
743
744 /* Generate an topological-ordered array of bitmap set SET.  */
745
746 static vec<pre_expr> 
747 sorted_array_from_bitmap_set (bitmap_set_t set)
748 {
749   unsigned int i, j;
750   bitmap_iterator bi, bj;
751   vec<pre_expr> result;
752
753   /* Pre-allocate enough space for the array.  */
754   result.create (bitmap_count_bits (&set->expressions));
755
756   FOR_EACH_VALUE_ID_IN_SET (set, i, bi)
757     {
758       /* The number of expressions having a given value is usually
759          relatively small.  Thus, rather than making a vector of all
760          the expressions and sorting it by value-id, we walk the values
761          and check in the reverse mapping that tells us what expressions
762          have a given value, to filter those in our set.  As a result,
763          the expressions are inserted in value-id order, which means
764          topological order.
765
766          If this is somehow a significant lose for some cases, we can
767          choose which set to walk based on the set size.  */
768       bitmap exprset = value_expressions[i];
769       EXECUTE_IF_SET_IN_BITMAP (exprset, 0, j, bj)
770         {
771           if (bitmap_bit_p (&set->expressions, j))
772             result.quick_push (expression_for_id (j));
773         }
774     }
775
776   return result;
777 }
778
779 /* Perform bitmapped set operation DEST &= ORIG.  */
780
781 static void
782 bitmap_set_and (bitmap_set_t dest, bitmap_set_t orig)
783 {
784   bitmap_iterator bi;
785   unsigned int i;
786
787   if (dest != orig)
788     {
789       bitmap_head temp;
790       bitmap_initialize (&temp, &grand_bitmap_obstack);
791
792       bitmap_and_into (&dest->values, &orig->values);
793       bitmap_copy (&temp, &dest->expressions);
794       EXECUTE_IF_SET_IN_BITMAP (&temp, 0, i, bi)
795         {
796           pre_expr expr = expression_for_id (i);
797           unsigned int value_id = get_expr_value_id (expr);
798           if (!bitmap_bit_p (&dest->values, value_id))
799             bitmap_clear_bit (&dest->expressions, i);
800         }
801       bitmap_clear (&temp);
802     }
803 }
804
805 /* Subtract all values and expressions contained in ORIG from DEST.  */
806
807 static bitmap_set_t
808 bitmap_set_subtract (bitmap_set_t dest, bitmap_set_t orig)
809 {
810   bitmap_set_t result = bitmap_set_new ();
811   bitmap_iterator bi;
812   unsigned int i;
813
814   bitmap_and_compl (&result->expressions, &dest->expressions,
815                     &orig->expressions);
816
817   FOR_EACH_EXPR_ID_IN_SET (result, i, bi)
818     {
819       pre_expr expr = expression_for_id (i);
820       unsigned int value_id = get_expr_value_id (expr);
821       bitmap_set_bit (&result->values, value_id);
822     }
823
824   return result;
825 }
826
827 /* Subtract all the values in bitmap set B from bitmap set A.  */
828
829 static void
830 bitmap_set_subtract_values (bitmap_set_t a, bitmap_set_t b)
831 {
832   unsigned int i;
833   bitmap_iterator bi;
834   bitmap_head temp;
835
836   bitmap_initialize (&temp, &grand_bitmap_obstack);
837
838   bitmap_copy (&temp, &a->expressions);
839   EXECUTE_IF_SET_IN_BITMAP (&temp, 0, i, bi)
840     {
841       pre_expr expr = expression_for_id (i);
842       if (bitmap_set_contains_value (b, get_expr_value_id (expr)))
843         bitmap_remove_from_set (a, expr);
844     }
845   bitmap_clear (&temp);
846 }
847
848
849 /* Return true if bitmapped set SET contains the value VALUE_ID.  */
850
851 static bool
852 bitmap_set_contains_value (bitmap_set_t set, unsigned int value_id)
853 {
854   if (value_id_constant_p (value_id))
855     return true;
856
857   if (!set || bitmap_empty_p (&set->expressions))
858     return false;
859
860   return bitmap_bit_p (&set->values, value_id);
861 }
862
863 static inline bool
864 bitmap_set_contains_expr (bitmap_set_t set, const pre_expr expr)
865 {
866   return bitmap_bit_p (&set->expressions, get_expression_id (expr));
867 }
868
869 /* Replace an instance of value LOOKFOR with expression EXPR in SET.  */
870
871 static void
872 bitmap_set_replace_value (bitmap_set_t set, unsigned int lookfor,
873                           const pre_expr expr)
874 {
875   bitmap exprset;
876   unsigned int i;
877   bitmap_iterator bi;
878
879   if (value_id_constant_p (lookfor))
880     return;
881
882   if (!bitmap_set_contains_value (set, lookfor))
883     return;
884
885   /* The number of expressions having a given value is usually
886      significantly less than the total number of expressions in SET.
887      Thus, rather than check, for each expression in SET, whether it
888      has the value LOOKFOR, we walk the reverse mapping that tells us
889      what expressions have a given value, and see if any of those
890      expressions are in our set.  For large testcases, this is about
891      5-10x faster than walking the bitmap.  If this is somehow a
892      significant lose for some cases, we can choose which set to walk
893      based on the set size.  */
894   exprset = value_expressions[lookfor];
895   EXECUTE_IF_SET_IN_BITMAP (exprset, 0, i, bi)
896     {
897       if (bitmap_clear_bit (&set->expressions, i))
898         {
899           bitmap_set_bit (&set->expressions, get_expression_id (expr));
900           return;
901         }
902     }
903
904   gcc_unreachable ();
905 }
906
907 /* Return true if two bitmap sets are equal.  */
908
909 static bool
910 bitmap_set_equal (bitmap_set_t a, bitmap_set_t b)
911 {
912   return bitmap_equal_p (&a->values, &b->values);
913 }
914
915 /* Replace an instance of EXPR's VALUE with EXPR in SET if it exists,
916    and add it otherwise.  */
917
918 static void
919 bitmap_value_replace_in_set (bitmap_set_t set, pre_expr expr)
920 {
921   unsigned int val = get_expr_value_id (expr);
922
923   if (bitmap_set_contains_value (set, val))
924     bitmap_set_replace_value (set, val, expr);
925   else
926     bitmap_insert_into_set (set, expr);
927 }
928
929 /* Insert EXPR into SET if EXPR's value is not already present in
930    SET.  */
931
932 static void
933 bitmap_value_insert_into_set (bitmap_set_t set, pre_expr expr)
934 {
935   unsigned int val = get_expr_value_id (expr);
936
937   gcc_checking_assert (expr->id == get_or_alloc_expression_id (expr));
938
939   /* Constant values are always considered to be part of the set.  */
940   if (value_id_constant_p (val))
941     return;
942
943   /* If the value membership changed, add the expression.  */
944   if (bitmap_set_bit (&set->values, val))
945     bitmap_set_bit (&set->expressions, expr->id);
946 }
947
948 /* Print out EXPR to outfile.  */
949
950 static void
951 print_pre_expr (FILE *outfile, const pre_expr expr)
952 {
953   switch (expr->kind)
954     {
955     case CONSTANT:
956       print_generic_expr (outfile, PRE_EXPR_CONSTANT (expr), 0);
957       break;
958     case NAME:
959       print_generic_expr (outfile, PRE_EXPR_NAME (expr), 0);
960       break;
961     case NARY:
962       {
963         unsigned int i;
964         vn_nary_op_t nary = PRE_EXPR_NARY (expr);
965         fprintf (outfile, "{%s,", get_tree_code_name (nary->opcode));
966         for (i = 0; i < nary->length; i++)
967           {
968             print_generic_expr (outfile, nary->op[i], 0);
969             if (i != (unsigned) nary->length - 1)
970               fprintf (outfile, ",");
971           }
972         fprintf (outfile, "}");
973       }
974       break;
975
976     case REFERENCE:
977       {
978         vn_reference_op_t vro;
979         unsigned int i;
980         vn_reference_t ref = PRE_EXPR_REFERENCE (expr);
981         fprintf (outfile, "{");
982         for (i = 0;
983              ref->operands.iterate (i, &vro);
984              i++)
985           {
986             bool closebrace = false;
987             if (vro->opcode != SSA_NAME
988                 && TREE_CODE_CLASS (vro->opcode) != tcc_declaration)
989               {
990                 fprintf (outfile, "%s", get_tree_code_name (vro->opcode));
991                 if (vro->op0)
992                   {
993                     fprintf (outfile, "<");
994                     closebrace = true;
995                   }
996               }
997             if (vro->op0)
998               {
999                 print_generic_expr (outfile, vro->op0, 0);
1000                 if (vro->op1)
1001                   {
1002                     fprintf (outfile, ",");
1003                     print_generic_expr (outfile, vro->op1, 0);
1004                   }
1005                 if (vro->op2)
1006                   {
1007                     fprintf (outfile, ",");
1008                     print_generic_expr (outfile, vro->op2, 0);
1009                   }
1010               }
1011             if (closebrace)
1012                 fprintf (outfile, ">");
1013             if (i != ref->operands.length () - 1)
1014               fprintf (outfile, ",");
1015           }
1016         fprintf (outfile, "}");
1017         if (ref->vuse)
1018           {
1019             fprintf (outfile, "@");
1020             print_generic_expr (outfile, ref->vuse, 0);
1021           }
1022       }
1023       break;
1024     }
1025 }
1026 void debug_pre_expr (pre_expr);
1027
1028 /* Like print_pre_expr but always prints to stderr.  */
1029 DEBUG_FUNCTION void
1030 debug_pre_expr (pre_expr e)
1031 {
1032   print_pre_expr (stderr, e);
1033   fprintf (stderr, "\n");
1034 }
1035
1036 /* Print out SET to OUTFILE.  */
1037
1038 static void
1039 print_bitmap_set (FILE *outfile, bitmap_set_t set,
1040                   const char *setname, int blockindex)
1041 {
1042   fprintf (outfile, "%s[%d] := { ", setname, blockindex);
1043   if (set)
1044     {
1045       bool first = true;
1046       unsigned i;
1047       bitmap_iterator bi;
1048
1049       FOR_EACH_EXPR_ID_IN_SET (set, i, bi)
1050         {
1051           const pre_expr expr = expression_for_id (i);
1052
1053           if (!first)
1054             fprintf (outfile, ", ");
1055           first = false;
1056           print_pre_expr (outfile, expr);
1057
1058           fprintf (outfile, " (%04d)", get_expr_value_id (expr));
1059         }
1060     }
1061   fprintf (outfile, " }\n");
1062 }
1063
1064 void debug_bitmap_set (bitmap_set_t);
1065
1066 DEBUG_FUNCTION void
1067 debug_bitmap_set (bitmap_set_t set)
1068 {
1069   print_bitmap_set (stderr, set, "debug", 0);
1070 }
1071
1072 void debug_bitmap_sets_for (basic_block);
1073
1074 DEBUG_FUNCTION void
1075 debug_bitmap_sets_for (basic_block bb)
1076 {
1077   print_bitmap_set (stderr, AVAIL_OUT (bb), "avail_out", bb->index);
1078   print_bitmap_set (stderr, EXP_GEN (bb), "exp_gen", bb->index);
1079   print_bitmap_set (stderr, PHI_GEN (bb), "phi_gen", bb->index);
1080   print_bitmap_set (stderr, TMP_GEN (bb), "tmp_gen", bb->index);
1081   print_bitmap_set (stderr, ANTIC_IN (bb), "antic_in", bb->index);
1082   if (do_partial_partial)
1083     print_bitmap_set (stderr, PA_IN (bb), "pa_in", bb->index);
1084   print_bitmap_set (stderr, NEW_SETS (bb), "new_sets", bb->index);
1085 }
1086
1087 /* Print out the expressions that have VAL to OUTFILE.  */
1088
1089 static void
1090 print_value_expressions (FILE *outfile, unsigned int val)
1091 {
1092   bitmap set = value_expressions[val];
1093   if (set)
1094     {
1095       bitmap_set x;
1096       char s[10];
1097       sprintf (s, "%04d", val);
1098       x.expressions = *set;
1099       print_bitmap_set (outfile, &x, s, 0);
1100     }
1101 }
1102
1103
1104 DEBUG_FUNCTION void
1105 debug_value_expressions (unsigned int val)
1106 {
1107   print_value_expressions (stderr, val);
1108 }
1109
1110 /* Given a CONSTANT, allocate a new CONSTANT type PRE_EXPR to
1111    represent it.  */
1112
1113 static pre_expr
1114 get_or_alloc_expr_for_constant (tree constant)
1115 {
1116   unsigned int result_id;
1117   unsigned int value_id;
1118   struct pre_expr_d expr;
1119   pre_expr newexpr;
1120
1121   expr.kind = CONSTANT;
1122   PRE_EXPR_CONSTANT (&expr) = constant;
1123   result_id = lookup_expression_id (&expr);
1124   if (result_id != 0)
1125     return expression_for_id (result_id);
1126
1127   newexpr = (pre_expr) pool_alloc (pre_expr_pool);
1128   newexpr->kind = CONSTANT;
1129   PRE_EXPR_CONSTANT (newexpr) = constant;
1130   alloc_expression_id (newexpr);
1131   value_id = get_or_alloc_constant_value_id (constant);
1132   add_to_value (value_id, newexpr);
1133   return newexpr;
1134 }
1135
1136 /* Given a value id V, find the actual tree representing the constant
1137    value if there is one, and return it. Return NULL if we can't find
1138    a constant.  */
1139
1140 static tree
1141 get_constant_for_value_id (unsigned int v)
1142 {
1143   if (value_id_constant_p (v))
1144     {
1145       unsigned int i;
1146       bitmap_iterator bi;
1147       bitmap exprset = value_expressions[v];
1148
1149       EXECUTE_IF_SET_IN_BITMAP (exprset, 0, i, bi)
1150         {
1151           pre_expr expr = expression_for_id (i);
1152           if (expr->kind == CONSTANT)
1153             return PRE_EXPR_CONSTANT (expr);
1154         }
1155     }
1156   return NULL;
1157 }
1158
1159 /* Get or allocate a pre_expr for a piece of GIMPLE, and return it.
1160    Currently only supports constants and SSA_NAMES.  */
1161 static pre_expr
1162 get_or_alloc_expr_for (tree t)
1163 {
1164   if (TREE_CODE (t) == SSA_NAME)
1165     return get_or_alloc_expr_for_name (t);
1166   else if (is_gimple_min_invariant (t))
1167     return get_or_alloc_expr_for_constant (t);
1168   else
1169     {
1170       /* More complex expressions can result from SCCVN expression
1171          simplification that inserts values for them.  As they all
1172          do not have VOPs the get handled by the nary ops struct.  */
1173       vn_nary_op_t result;
1174       unsigned int result_id;
1175       vn_nary_op_lookup (t, &result);
1176       if (result != NULL)
1177         {
1178           pre_expr e = (pre_expr) pool_alloc (pre_expr_pool);
1179           e->kind = NARY;
1180           PRE_EXPR_NARY (e) = result;
1181           result_id = lookup_expression_id (e);
1182           if (result_id != 0)
1183             {
1184               pool_free (pre_expr_pool, e);
1185               e = expression_for_id (result_id);
1186               return e;
1187             }
1188           alloc_expression_id (e);
1189           return e;
1190         }
1191     }
1192   return NULL;
1193 }
1194
1195 /* Return the folded version of T if T, when folded, is a gimple
1196    min_invariant.  Otherwise, return T.  */
1197
1198 static pre_expr
1199 fully_constant_expression (pre_expr e)
1200 {
1201   switch (e->kind)
1202     {
1203     case CONSTANT:
1204       return e;
1205     case NARY:
1206       {
1207         vn_nary_op_t nary = PRE_EXPR_NARY (e);
1208         switch (TREE_CODE_CLASS (nary->opcode))
1209           {
1210           case tcc_binary:
1211           case tcc_comparison:
1212             {
1213               /* We have to go from trees to pre exprs to value ids to
1214                  constants.  */
1215               tree naryop0 = nary->op[0];
1216               tree naryop1 = nary->op[1];
1217               tree result;
1218               if (!is_gimple_min_invariant (naryop0))
1219                 {
1220                   pre_expr rep0 = get_or_alloc_expr_for (naryop0);
1221                   unsigned int vrep0 = get_expr_value_id (rep0);
1222                   tree const0 = get_constant_for_value_id (vrep0);
1223                   if (const0)
1224                     naryop0 = fold_convert (TREE_TYPE (naryop0), const0);
1225                 }
1226               if (!is_gimple_min_invariant (naryop1))
1227                 {
1228                   pre_expr rep1 = get_or_alloc_expr_for (naryop1);
1229                   unsigned int vrep1 = get_expr_value_id (rep1);
1230                   tree const1 = get_constant_for_value_id (vrep1);
1231                   if (const1)
1232                     naryop1 = fold_convert (TREE_TYPE (naryop1), const1);
1233                 }
1234               result = fold_binary (nary->opcode, nary->type,
1235                                     naryop0, naryop1);
1236               if (result && is_gimple_min_invariant (result))
1237                 return get_or_alloc_expr_for_constant (result);
1238               /* We might have simplified the expression to a
1239                  SSA_NAME for example from x_1 * 1.  But we cannot
1240                  insert a PHI for x_1 unconditionally as x_1 might
1241                  not be available readily.  */
1242               return e;
1243             }
1244           case tcc_reference:
1245             if (nary->opcode != REALPART_EXPR
1246                 && nary->opcode != IMAGPART_EXPR
1247                 && nary->opcode != VIEW_CONVERT_EXPR)
1248               return e;
1249             /* Fallthrough.  */
1250           case tcc_unary:
1251             {
1252               /* We have to go from trees to pre exprs to value ids to
1253                  constants.  */
1254               tree naryop0 = nary->op[0];
1255               tree const0, result;
1256               if (is_gimple_min_invariant (naryop0))
1257                 const0 = naryop0;
1258               else
1259                 {
1260                   pre_expr rep0 = get_or_alloc_expr_for (naryop0);
1261                   unsigned int vrep0 = get_expr_value_id (rep0);
1262                   const0 = get_constant_for_value_id (vrep0);
1263                 }
1264               result = NULL;
1265               if (const0)
1266                 {
1267                   tree type1 = TREE_TYPE (nary->op[0]);
1268                   const0 = fold_convert (type1, const0);
1269                   result = fold_unary (nary->opcode, nary->type, const0);
1270                 }
1271               if (result && is_gimple_min_invariant (result))
1272                 return get_or_alloc_expr_for_constant (result);
1273               return e;
1274             }
1275           default:
1276             return e;
1277           }
1278       }
1279     case REFERENCE:
1280       {
1281         vn_reference_t ref = PRE_EXPR_REFERENCE (e);
1282         tree folded;
1283         if ((folded = fully_constant_vn_reference_p (ref)))
1284           return get_or_alloc_expr_for_constant (folded);
1285         return e;
1286       }
1287     default:
1288       return e;
1289     }
1290   return e;
1291 }
1292
1293 /* Translate the VUSE backwards through phi nodes in PHIBLOCK, so that
1294    it has the value it would have in BLOCK.  Set *SAME_VALID to true
1295    in case the new vuse doesn't change the value id of the OPERANDS.  */
1296
1297 static tree
1298 translate_vuse_through_block (vec<vn_reference_op_s> operands,
1299                               alias_set_type set, tree type, tree vuse,
1300                               basic_block phiblock,
1301                               basic_block block, bool *same_valid)
1302 {
1303   gimple phi = SSA_NAME_DEF_STMT (vuse);
1304   ao_ref ref;
1305   edge e = NULL;
1306   bool use_oracle;
1307
1308   *same_valid = true;
1309
1310   if (gimple_bb (phi) != phiblock)
1311     return vuse;
1312
1313   use_oracle = ao_ref_init_from_vn_reference (&ref, set, type, operands);
1314
1315   /* Use the alias-oracle to find either the PHI node in this block,
1316      the first VUSE used in this block that is equivalent to vuse or
1317      the first VUSE which definition in this block kills the value.  */
1318   if (gimple_code (phi) == GIMPLE_PHI)
1319     e = find_edge (block, phiblock);
1320   else if (use_oracle)
1321     while (!stmt_may_clobber_ref_p_1 (phi, &ref))
1322       {
1323         vuse = gimple_vuse (phi);
1324         phi = SSA_NAME_DEF_STMT (vuse);
1325         if (gimple_bb (phi) != phiblock)
1326           return vuse;
1327         if (gimple_code (phi) == GIMPLE_PHI)
1328           {
1329             e = find_edge (block, phiblock);
1330             break;
1331           }
1332       }
1333   else
1334     return NULL_TREE;
1335
1336   if (e)
1337     {
1338       if (use_oracle)
1339         {
1340           bitmap visited = NULL;
1341           unsigned int cnt;
1342           /* Try to find a vuse that dominates this phi node by skipping
1343              non-clobbering statements.  */
1344           vuse = get_continuation_for_phi (phi, &ref, &cnt, &visited, false,
1345                                            NULL, NULL);
1346           if (visited)
1347             BITMAP_FREE (visited);
1348         }
1349       else
1350         vuse = NULL_TREE;
1351       if (!vuse)
1352         {
1353           /* If we didn't find any, the value ID can't stay the same,
1354              but return the translated vuse.  */
1355           *same_valid = false;
1356           vuse = PHI_ARG_DEF (phi, e->dest_idx);
1357         }
1358       /* ??? We would like to return vuse here as this is the canonical
1359          upmost vdef that this reference is associated with.  But during
1360          insertion of the references into the hash tables we only ever
1361          directly insert with their direct gimple_vuse, hence returning
1362          something else would make us not find the other expression.  */
1363       return PHI_ARG_DEF (phi, e->dest_idx);
1364     }
1365
1366   return NULL_TREE;
1367 }
1368
1369 /* Like bitmap_find_leader, but checks for the value existing in SET1 *or*
1370    SET2.  This is used to avoid making a set consisting of the union
1371    of PA_IN and ANTIC_IN during insert.  */
1372
1373 static inline pre_expr
1374 find_leader_in_sets (unsigned int val, bitmap_set_t set1, bitmap_set_t set2)
1375 {
1376   pre_expr result;
1377
1378   result = bitmap_find_leader (set1, val);
1379   if (!result && set2)
1380     result = bitmap_find_leader (set2, val);
1381   return result;
1382 }
1383
1384 /* Get the tree type for our PRE expression e.  */
1385
1386 static tree
1387 get_expr_type (const pre_expr e)
1388 {
1389   switch (e->kind)
1390     {
1391     case NAME:
1392       return TREE_TYPE (PRE_EXPR_NAME (e));
1393     case CONSTANT:
1394       return TREE_TYPE (PRE_EXPR_CONSTANT (e));
1395     case REFERENCE:
1396       return PRE_EXPR_REFERENCE (e)->type;
1397     case NARY:
1398       return PRE_EXPR_NARY (e)->type;
1399     }
1400   gcc_unreachable ();
1401 }
1402
1403 /* Get a representative SSA_NAME for a given expression.
1404    Since all of our sub-expressions are treated as values, we require
1405    them to be SSA_NAME's for simplicity.
1406    Prior versions of GVNPRE used to use "value handles" here, so that
1407    an expression would be VH.11 + VH.10 instead of d_3 + e_6.  In
1408    either case, the operands are really values (IE we do not expect
1409    them to be usable without finding leaders).  */
1410
1411 static tree
1412 get_representative_for (const pre_expr e)
1413 {
1414   tree name;
1415   unsigned int value_id = get_expr_value_id (e);
1416
1417   switch (e->kind)
1418     {
1419     case NAME:
1420       return PRE_EXPR_NAME (e);
1421     case CONSTANT:
1422       return PRE_EXPR_CONSTANT (e);
1423     case NARY:
1424     case REFERENCE:
1425       {
1426         /* Go through all of the expressions representing this value
1427            and pick out an SSA_NAME.  */
1428         unsigned int i;
1429         bitmap_iterator bi;
1430         bitmap exprs = value_expressions[value_id];
1431         EXECUTE_IF_SET_IN_BITMAP (exprs, 0, i, bi)
1432           {
1433             pre_expr rep = expression_for_id (i);
1434             if (rep->kind == NAME)
1435               return PRE_EXPR_NAME (rep);
1436             else if (rep->kind == CONSTANT)
1437               return PRE_EXPR_CONSTANT (rep);
1438           }
1439       }
1440       break;
1441     }
1442
1443   /* If we reached here we couldn't find an SSA_NAME.  This can
1444      happen when we've discovered a value that has never appeared in
1445      the program as set to an SSA_NAME, as the result of phi translation.
1446      Create one here.
1447      ???  We should be able to re-use this when we insert the statement
1448      to compute it.  */
1449   name = make_temp_ssa_name (get_expr_type (e), gimple_build_nop (), "pretmp");
1450   VN_INFO_GET (name)->value_id = value_id;
1451   VN_INFO (name)->valnum = name;
1452   /* ???  For now mark this SSA name for release by SCCVN.  */
1453   VN_INFO (name)->needs_insertion = true;
1454   add_to_value (value_id, get_or_alloc_expr_for_name (name));
1455   if (dump_file && (dump_flags & TDF_DETAILS))
1456     {
1457       fprintf (dump_file, "Created SSA_NAME representative ");
1458       print_generic_expr (dump_file, name, 0);
1459       fprintf (dump_file, " for expression:");
1460       print_pre_expr (dump_file, e);
1461       fprintf (dump_file, " (%04d)\n", value_id);
1462     }
1463
1464   return name;
1465 }
1466
1467
1468
1469 static pre_expr
1470 phi_translate (pre_expr expr, bitmap_set_t set1, bitmap_set_t set2,
1471                basic_block pred, basic_block phiblock);
1472
1473 /* Translate EXPR using phis in PHIBLOCK, so that it has the values of
1474    the phis in PRED.  Return NULL if we can't find a leader for each part
1475    of the translated expression.  */
1476
1477 static pre_expr
1478 phi_translate_1 (pre_expr expr, bitmap_set_t set1, bitmap_set_t set2,
1479                  basic_block pred, basic_block phiblock)
1480 {
1481   switch (expr->kind)
1482     {
1483     case NARY:
1484       {
1485         unsigned int i;
1486         bool changed = false;
1487         vn_nary_op_t nary = PRE_EXPR_NARY (expr);
1488         vn_nary_op_t newnary = XALLOCAVAR (struct vn_nary_op_s,
1489                                            sizeof_vn_nary_op (nary->length));
1490         memcpy (newnary, nary, sizeof_vn_nary_op (nary->length));
1491
1492         for (i = 0; i < newnary->length; i++)
1493           {
1494             if (TREE_CODE (newnary->op[i]) != SSA_NAME)
1495               continue;
1496             else
1497               {
1498                 pre_expr leader, result;
1499                 unsigned int op_val_id = VN_INFO (newnary->op[i])->value_id;
1500                 leader = find_leader_in_sets (op_val_id, set1, set2);
1501                 result = phi_translate (leader, set1, set2, pred, phiblock);
1502                 if (result && result != leader)
1503                   {
1504                     tree name = get_representative_for (result);
1505                     if (!name)
1506                       return NULL;
1507                     newnary->op[i] = name;
1508                   }
1509                 else if (!result)
1510                   return NULL;
1511
1512                 changed |= newnary->op[i] != nary->op[i];
1513               }
1514           }
1515         if (changed)
1516           {
1517             pre_expr constant;
1518             unsigned int new_val_id;
1519
1520             tree result = vn_nary_op_lookup_pieces (newnary->length,
1521                                                     newnary->opcode,
1522                                                     newnary->type,
1523                                                     &newnary->op[0],
1524                                                     &nary);
1525             if (result && is_gimple_min_invariant (result))
1526               return get_or_alloc_expr_for_constant (result);
1527
1528             expr = (pre_expr) pool_alloc (pre_expr_pool);
1529             expr->kind = NARY;
1530             expr->id = 0;
1531             if (nary)
1532               {
1533                 PRE_EXPR_NARY (expr) = nary;
1534                 constant = fully_constant_expression (expr);
1535                 if (constant != expr)
1536                   return constant;
1537
1538                 new_val_id = nary->value_id;
1539                 get_or_alloc_expression_id (expr);
1540               }
1541             else
1542               {
1543                 new_val_id = get_next_value_id ();
1544                 value_expressions.safe_grow_cleared (get_max_value_id () + 1);
1545                 nary = vn_nary_op_insert_pieces (newnary->length,
1546                                                  newnary->opcode,
1547                                                  newnary->type,
1548                                                  &newnary->op[0],
1549                                                  result, new_val_id);
1550                 PRE_EXPR_NARY (expr) = nary;
1551                 constant = fully_constant_expression (expr);
1552                 if (constant != expr)
1553                   return constant;
1554                 get_or_alloc_expression_id (expr);
1555               }
1556             add_to_value (new_val_id, expr);
1557           }
1558         return expr;
1559       }
1560       break;
1561
1562     case REFERENCE:
1563       {
1564         vn_reference_t ref = PRE_EXPR_REFERENCE (expr);
1565         vec<vn_reference_op_s> operands = ref->operands;
1566         tree vuse = ref->vuse;
1567         tree newvuse = vuse;
1568         vec<vn_reference_op_s> newoperands = vNULL;
1569         bool changed = false, same_valid = true;
1570         unsigned int i, n;
1571         vn_reference_op_t operand;
1572         vn_reference_t newref;
1573
1574         for (i = 0; operands.iterate (i, &operand); i++)
1575           {
1576             pre_expr opresult;
1577             pre_expr leader;
1578             tree op[3];
1579             tree type = operand->type;
1580             vn_reference_op_s newop = *operand;
1581             op[0] = operand->op0;
1582             op[1] = operand->op1;
1583             op[2] = operand->op2;
1584             for (n = 0; n < 3; ++n)
1585               {
1586                 unsigned int op_val_id;
1587                 if (!op[n])
1588                   continue;
1589                 if (TREE_CODE (op[n]) != SSA_NAME)
1590                   {
1591                     /* We can't possibly insert these.  */
1592                     if (n != 0
1593                         && !is_gimple_min_invariant (op[n]))
1594                       break;
1595                     continue;
1596                   }
1597                 op_val_id = VN_INFO (op[n])->value_id;
1598                 leader = find_leader_in_sets (op_val_id, set1, set2);
1599                 if (!leader)
1600                   break;
1601                 opresult = phi_translate (leader, set1, set2, pred, phiblock);
1602                 if (!opresult)
1603                   break;
1604                 if (opresult != leader)
1605                   {
1606                     tree name = get_representative_for (opresult);
1607                     if (!name)
1608                       break;
1609                     changed |= name != op[n];
1610                     op[n] = name;
1611                   }
1612               }
1613             if (n != 3)
1614               {
1615                 newoperands.release ();
1616                 return NULL;
1617               }
1618             if (!changed)
1619               continue;
1620             if (!newoperands.exists ())
1621               newoperands = operands.copy ();
1622             /* We may have changed from an SSA_NAME to a constant */
1623             if (newop.opcode == SSA_NAME && TREE_CODE (op[0]) != SSA_NAME)
1624               newop.opcode = TREE_CODE (op[0]);
1625             newop.type = type;
1626             newop.op0 = op[0];
1627             newop.op1 = op[1];
1628             newop.op2 = op[2];
1629             newoperands[i] = newop;
1630           }
1631         gcc_checking_assert (i == operands.length ());
1632
1633         if (vuse)
1634           {
1635             newvuse = translate_vuse_through_block (newoperands.exists ()
1636                                                     ? newoperands : operands,
1637                                                     ref->set, ref->type,
1638                                                     vuse, phiblock, pred,
1639                                                     &same_valid);
1640             if (newvuse == NULL_TREE)
1641               {
1642                 newoperands.release ();
1643                 return NULL;
1644               }
1645           }
1646
1647         if (changed || newvuse != vuse)
1648           {
1649             unsigned int new_val_id;
1650             pre_expr constant;
1651
1652             tree result = vn_reference_lookup_pieces (newvuse, ref->set,
1653                                                       ref->type,
1654                                                       newoperands.exists ()
1655                                                       ? newoperands : operands,
1656                                                       &newref, VN_WALK);
1657             if (result)
1658               newoperands.release ();
1659
1660             /* We can always insert constants, so if we have a partial
1661                redundant constant load of another type try to translate it
1662                to a constant of appropriate type.  */
1663             if (result && is_gimple_min_invariant (result))
1664               {
1665                 tree tem = result;
1666                 if (!useless_type_conversion_p (ref->type, TREE_TYPE (result)))
1667                   {
1668                     tem = fold_unary (VIEW_CONVERT_EXPR, ref->type, result);
1669                     if (tem && !is_gimple_min_invariant (tem))
1670                       tem = NULL_TREE;
1671                   }
1672                 if (tem)
1673                   return get_or_alloc_expr_for_constant (tem);
1674               }
1675
1676             /* If we'd have to convert things we would need to validate
1677                if we can insert the translated expression.  So fail
1678                here for now - we cannot insert an alias with a different
1679                type in the VN tables either, as that would assert.  */
1680             if (result
1681                 && !useless_type_conversion_p (ref->type, TREE_TYPE (result)))
1682               return NULL;
1683             else if (!result && newref
1684                      && !useless_type_conversion_p (ref->type, newref->type))
1685               {
1686                 newoperands.release ();
1687                 return NULL;
1688               }
1689
1690             expr = (pre_expr) pool_alloc (pre_expr_pool);
1691             expr->kind = REFERENCE;
1692             expr->id = 0;
1693
1694             if (newref)
1695               {
1696                 PRE_EXPR_REFERENCE (expr) = newref;
1697                 constant = fully_constant_expression (expr);
1698                 if (constant != expr)
1699                   return constant;
1700
1701                 new_val_id = newref->value_id;
1702                 get_or_alloc_expression_id (expr);
1703               }
1704             else
1705               {
1706                 if (changed || !same_valid)
1707                   {
1708                     new_val_id = get_next_value_id ();
1709                     value_expressions.safe_grow_cleared
1710                       (get_max_value_id () + 1);
1711                   }
1712                 else
1713                   new_val_id = ref->value_id;
1714                 if (!newoperands.exists ())
1715                   newoperands = operands.copy ();
1716                 newref = vn_reference_insert_pieces (newvuse, ref->set,
1717                                                      ref->type,
1718                                                      newoperands,
1719                                                      result, new_val_id);
1720                 newoperands = vNULL;
1721                 PRE_EXPR_REFERENCE (expr) = newref;
1722                 constant = fully_constant_expression (expr);
1723                 if (constant != expr)
1724                   return constant;
1725                 get_or_alloc_expression_id (expr);
1726               }
1727             add_to_value (new_val_id, expr);
1728           }
1729         newoperands.release ();
1730         return expr;
1731       }
1732       break;
1733
1734     case NAME:
1735       {
1736         tree name = PRE_EXPR_NAME (expr);
1737         gimple def_stmt = SSA_NAME_DEF_STMT (name);
1738         /* If the SSA name is defined by a PHI node in this block,
1739            translate it.  */
1740         if (gimple_code (def_stmt) == GIMPLE_PHI
1741             && gimple_bb (def_stmt) == phiblock)
1742           {
1743             edge e = find_edge (pred, gimple_bb (def_stmt));
1744             tree def = PHI_ARG_DEF (def_stmt, e->dest_idx);
1745
1746             /* Handle constant. */
1747             if (is_gimple_min_invariant (def))
1748               return get_or_alloc_expr_for_constant (def);
1749
1750             return get_or_alloc_expr_for_name (def);
1751           }
1752         /* Otherwise return it unchanged - it will get removed if its
1753            value is not available in PREDs AVAIL_OUT set of expressions
1754            by the subtraction of TMP_GEN.  */
1755         return expr;
1756       }
1757
1758     default:
1759       gcc_unreachable ();
1760     }
1761 }
1762
1763 /* Wrapper around phi_translate_1 providing caching functionality.  */
1764
1765 static pre_expr
1766 phi_translate (pre_expr expr, bitmap_set_t set1, bitmap_set_t set2,
1767                basic_block pred, basic_block phiblock)
1768 {
1769   expr_pred_trans_t slot = NULL;
1770   pre_expr phitrans;
1771
1772   if (!expr)
1773     return NULL;
1774
1775   /* Constants contain no values that need translation.  */
1776   if (expr->kind == CONSTANT)
1777     return expr;
1778
1779   if (value_id_constant_p (get_expr_value_id (expr)))
1780     return expr;
1781
1782   /* Don't add translations of NAMEs as those are cheap to translate.  */
1783   if (expr->kind != NAME)
1784     {
1785       if (phi_trans_add (&slot, expr, pred))
1786         return slot->v;
1787       /* Store NULL for the value we want to return in the case of
1788          recursing.  */
1789       slot->v = NULL;
1790     }
1791
1792   /* Translate.  */
1793   phitrans = phi_translate_1 (expr, set1, set2, pred, phiblock);
1794
1795   if (slot)
1796     {
1797       if (phitrans)
1798         slot->v = phitrans;
1799       else
1800         /* Remove failed translations again, they cause insert
1801            iteration to not pick up new opportunities reliably.  */
1802         phi_translate_table->remove_elt_with_hash (slot, slot->hashcode);
1803     }
1804
1805   return phitrans;
1806 }
1807
1808
1809 /* For each expression in SET, translate the values through phi nodes
1810    in PHIBLOCK using edge PHIBLOCK->PRED, and store the resulting
1811    expressions in DEST.  */
1812
1813 static void
1814 phi_translate_set (bitmap_set_t dest, bitmap_set_t set, basic_block pred,
1815                    basic_block phiblock)
1816 {
1817   vec<pre_expr> exprs;
1818   pre_expr expr;
1819   int i;
1820
1821   if (gimple_seq_empty_p (phi_nodes (phiblock)))
1822     {
1823       bitmap_set_copy (dest, set);
1824       return;
1825     }
1826
1827   exprs = sorted_array_from_bitmap_set (set);
1828   FOR_EACH_VEC_ELT (exprs, i, expr)
1829     {
1830       pre_expr translated;
1831       translated = phi_translate (expr, set, NULL, pred, phiblock);
1832       if (!translated)
1833         continue;
1834
1835       /* We might end up with multiple expressions from SET being
1836          translated to the same value.  In this case we do not want
1837          to retain the NARY or REFERENCE expression but prefer a NAME
1838          which would be the leader.  */
1839       if (translated->kind == NAME)
1840         bitmap_value_replace_in_set (dest, translated);
1841       else
1842         bitmap_value_insert_into_set (dest, translated);
1843     }
1844   exprs.release ();
1845 }
1846
1847 /* Find the leader for a value (i.e., the name representing that
1848    value) in a given set, and return it.  Return NULL if no leader
1849    is found.  */
1850
1851 static pre_expr
1852 bitmap_find_leader (bitmap_set_t set, unsigned int val)
1853 {
1854   if (value_id_constant_p (val))
1855     {
1856       unsigned int i;
1857       bitmap_iterator bi;
1858       bitmap exprset = value_expressions[val];
1859
1860       EXECUTE_IF_SET_IN_BITMAP (exprset, 0, i, bi)
1861         {
1862           pre_expr expr = expression_for_id (i);
1863           if (expr->kind == CONSTANT)
1864             return expr;
1865         }
1866     }
1867   if (bitmap_set_contains_value (set, val))
1868     {
1869       /* Rather than walk the entire bitmap of expressions, and see
1870          whether any of them has the value we are looking for, we look
1871          at the reverse mapping, which tells us the set of expressions
1872          that have a given value (IE value->expressions with that
1873          value) and see if any of those expressions are in our set.
1874          The number of expressions per value is usually significantly
1875          less than the number of expressions in the set.  In fact, for
1876          large testcases, doing it this way is roughly 5-10x faster
1877          than walking the bitmap.
1878          If this is somehow a significant lose for some cases, we can
1879          choose which set to walk based on which set is smaller.  */
1880       unsigned int i;
1881       bitmap_iterator bi;
1882       bitmap exprset = value_expressions[val];
1883
1884       EXECUTE_IF_AND_IN_BITMAP (exprset, &set->expressions, 0, i, bi)
1885         return expression_for_id (i);
1886     }
1887   return NULL;
1888 }
1889
1890 /* Determine if EXPR, a memory expression, is ANTIC_IN at the top of
1891    BLOCK by seeing if it is not killed in the block.  Note that we are
1892    only determining whether there is a store that kills it.  Because
1893    of the order in which clean iterates over values, we are guaranteed
1894    that altered operands will have caused us to be eliminated from the
1895    ANTIC_IN set already.  */
1896
1897 static bool
1898 value_dies_in_block_x (pre_expr expr, basic_block block)
1899 {
1900   tree vuse = PRE_EXPR_REFERENCE (expr)->vuse;
1901   vn_reference_t refx = PRE_EXPR_REFERENCE (expr);
1902   gimple def;
1903   gimple_stmt_iterator gsi;
1904   unsigned id = get_expression_id (expr);
1905   bool res = false;
1906   ao_ref ref;
1907
1908   if (!vuse)
1909     return false;
1910
1911   /* Lookup a previously calculated result.  */
1912   if (EXPR_DIES (block)
1913       && bitmap_bit_p (EXPR_DIES (block), id * 2))
1914     return bitmap_bit_p (EXPR_DIES (block), id * 2 + 1);
1915
1916   /* A memory expression {e, VUSE} dies in the block if there is a
1917      statement that may clobber e.  If, starting statement walk from the
1918      top of the basic block, a statement uses VUSE there can be no kill
1919      inbetween that use and the original statement that loaded {e, VUSE},
1920      so we can stop walking.  */
1921   ref.base = NULL_TREE;
1922   for (gsi = gsi_start_bb (block); !gsi_end_p (gsi); gsi_next (&gsi))
1923     {
1924       tree def_vuse, def_vdef;
1925       def = gsi_stmt (gsi);
1926       def_vuse = gimple_vuse (def);
1927       def_vdef = gimple_vdef (def);
1928
1929       /* Not a memory statement.  */
1930       if (!def_vuse)
1931         continue;
1932
1933       /* Not a may-def.  */
1934       if (!def_vdef)
1935         {
1936           /* A load with the same VUSE, we're done.  */
1937           if (def_vuse == vuse)
1938             break;
1939
1940           continue;
1941         }
1942
1943       /* Init ref only if we really need it.  */
1944       if (ref.base == NULL_TREE
1945           && !ao_ref_init_from_vn_reference (&ref, refx->set, refx->type,
1946                                              refx->operands))
1947         {
1948           res = true;
1949           break;
1950         }
1951       /* If the statement may clobber expr, it dies.  */
1952       if (stmt_may_clobber_ref_p_1 (def, &ref))
1953         {
1954           res = true;
1955           break;
1956         }
1957     }
1958
1959   /* Remember the result.  */
1960   if (!EXPR_DIES (block))
1961     EXPR_DIES (block) = BITMAP_ALLOC (&grand_bitmap_obstack);
1962   bitmap_set_bit (EXPR_DIES (block), id * 2);
1963   if (res)
1964     bitmap_set_bit (EXPR_DIES (block), id * 2 + 1);
1965
1966   return res;
1967 }
1968
1969
1970 /* Determine if OP is valid in SET1 U SET2, which it is when the union
1971    contains its value-id.  */
1972
1973 static bool
1974 op_valid_in_sets (bitmap_set_t set1, bitmap_set_t set2, tree op)
1975 {
1976   if (op && TREE_CODE (op) == SSA_NAME)
1977     {
1978       unsigned int value_id = VN_INFO (op)->value_id;
1979       if (!(bitmap_set_contains_value (set1, value_id)
1980             || (set2 && bitmap_set_contains_value  (set2, value_id))))
1981         return false;
1982     }
1983   return true;
1984 }
1985
1986 /* Determine if the expression EXPR is valid in SET1 U SET2.
1987    ONLY SET2 CAN BE NULL.
1988    This means that we have a leader for each part of the expression
1989    (if it consists of values), or the expression is an SSA_NAME.
1990    For loads/calls, we also see if the vuse is killed in this block.  */
1991
1992 static bool
1993 valid_in_sets (bitmap_set_t set1, bitmap_set_t set2, pre_expr expr)
1994 {
1995   switch (expr->kind)
1996     {
1997     case NAME:
1998       /* By construction all NAMEs are available.  Non-available
1999          NAMEs are removed by subtracting TMP_GEN from the sets.  */
2000       return true;
2001     case NARY:
2002       {
2003         unsigned int i;
2004         vn_nary_op_t nary = PRE_EXPR_NARY (expr);
2005         for (i = 0; i < nary->length; i++)
2006           if (!op_valid_in_sets (set1, set2, nary->op[i]))
2007             return false;
2008         return true;
2009       }
2010       break;
2011     case REFERENCE:
2012       {
2013         vn_reference_t ref = PRE_EXPR_REFERENCE (expr);
2014         vn_reference_op_t vro;
2015         unsigned int i;
2016
2017         FOR_EACH_VEC_ELT (ref->operands, i, vro)
2018           {
2019             if (!op_valid_in_sets (set1, set2, vro->op0)
2020                 || !op_valid_in_sets (set1, set2, vro->op1)
2021                 || !op_valid_in_sets (set1, set2, vro->op2))
2022               return false;
2023           }
2024         return true;
2025       }
2026     default:
2027       gcc_unreachable ();
2028     }
2029 }
2030
2031 /* Clean the set of expressions that are no longer valid in SET1 or
2032    SET2.  This means expressions that are made up of values we have no
2033    leaders for in SET1 or SET2.  This version is used for partial
2034    anticipation, which means it is not valid in either ANTIC_IN or
2035    PA_IN.  */
2036
2037 static void
2038 dependent_clean (bitmap_set_t set1, bitmap_set_t set2)
2039 {
2040   vec<pre_expr> exprs = sorted_array_from_bitmap_set (set1);
2041   pre_expr expr;
2042   int i;
2043
2044   FOR_EACH_VEC_ELT (exprs, i, expr)
2045     {
2046       if (!valid_in_sets (set1, set2, expr))
2047         bitmap_remove_from_set (set1, expr);
2048     }
2049   exprs.release ();
2050 }
2051
2052 /* Clean the set of expressions that are no longer valid in SET.  This
2053    means expressions that are made up of values we have no leaders for
2054    in SET.  */
2055
2056 static void
2057 clean (bitmap_set_t set)
2058 {
2059   vec<pre_expr> exprs = sorted_array_from_bitmap_set (set);
2060   pre_expr expr;
2061   int i;
2062
2063   FOR_EACH_VEC_ELT (exprs, i, expr)
2064     {
2065       if (!valid_in_sets (set, NULL, expr))
2066         bitmap_remove_from_set (set, expr);
2067     }
2068   exprs.release ();
2069 }
2070
2071 /* Clean the set of expressions that are no longer valid in SET because
2072    they are clobbered in BLOCK or because they trap and may not be executed.  */
2073
2074 static void
2075 prune_clobbered_mems (bitmap_set_t set, basic_block block)
2076 {
2077   bitmap_iterator bi;
2078   unsigned i;
2079
2080   FOR_EACH_EXPR_ID_IN_SET (set, i, bi)
2081     {
2082       pre_expr expr = expression_for_id (i);
2083       if (expr->kind == REFERENCE)
2084         {
2085           vn_reference_t ref = PRE_EXPR_REFERENCE (expr);
2086           if (ref->vuse)
2087             {
2088               gimple def_stmt = SSA_NAME_DEF_STMT (ref->vuse);
2089               if (!gimple_nop_p (def_stmt)
2090                   && ((gimple_bb (def_stmt) != block
2091                        && !dominated_by_p (CDI_DOMINATORS,
2092                                            block, gimple_bb (def_stmt)))
2093                       || (gimple_bb (def_stmt) == block
2094                           && value_dies_in_block_x (expr, block))))
2095                 bitmap_remove_from_set (set, expr);
2096             }
2097         }
2098       else if (expr->kind == NARY)
2099         {
2100           vn_nary_op_t nary = PRE_EXPR_NARY (expr);
2101           /* If the NARY may trap make sure the block does not contain
2102              a possible exit point.
2103              ???  This is overly conservative if we translate AVAIL_OUT
2104              as the available expression might be after the exit point.  */
2105           if (BB_MAY_NOTRETURN (block)
2106               && vn_nary_may_trap (nary))
2107             bitmap_remove_from_set (set, expr);
2108         }
2109     }
2110 }
2111
2112 static sbitmap has_abnormal_preds;
2113
2114 /* List of blocks that may have changed during ANTIC computation and
2115    thus need to be iterated over.  */
2116
2117 static sbitmap changed_blocks;
2118
2119 /* Compute the ANTIC set for BLOCK.
2120
2121    If succs(BLOCK) > 1 then
2122      ANTIC_OUT[BLOCK] = intersection of ANTIC_IN[b] for all succ(BLOCK)
2123    else if succs(BLOCK) == 1 then
2124      ANTIC_OUT[BLOCK] = phi_translate (ANTIC_IN[succ(BLOCK)])
2125
2126    ANTIC_IN[BLOCK] = clean(ANTIC_OUT[BLOCK] U EXP_GEN[BLOCK] - TMP_GEN[BLOCK])
2127 */
2128
2129 static bool
2130 compute_antic_aux (basic_block block, bool block_has_abnormal_pred_edge)
2131 {
2132   bool changed = false;
2133   bitmap_set_t S, old, ANTIC_OUT;
2134   bitmap_iterator bi;
2135   unsigned int bii;
2136   edge e;
2137   edge_iterator ei;
2138
2139   old = ANTIC_OUT = S = NULL;
2140   BB_VISITED (block) = 1;
2141
2142   /* If any edges from predecessors are abnormal, antic_in is empty,
2143      so do nothing.  */
2144   if (block_has_abnormal_pred_edge)
2145     goto maybe_dump_sets;
2146
2147   old = ANTIC_IN (block);
2148   ANTIC_OUT = bitmap_set_new ();
2149
2150   /* If the block has no successors, ANTIC_OUT is empty.  */
2151   if (EDGE_COUNT (block->succs) == 0)
2152     ;
2153   /* If we have one successor, we could have some phi nodes to
2154      translate through.  */
2155   else if (single_succ_p (block))
2156     {
2157       basic_block succ_bb = single_succ (block);
2158       gcc_assert (BB_VISITED (succ_bb));
2159       phi_translate_set (ANTIC_OUT, ANTIC_IN (succ_bb), block, succ_bb);
2160     }
2161   /* If we have multiple successors, we take the intersection of all of
2162      them.  Note that in the case of loop exit phi nodes, we may have
2163      phis to translate through.  */
2164   else
2165     {
2166       size_t i;
2167       basic_block bprime, first = NULL;
2168
2169       auto_vec<basic_block> worklist (EDGE_COUNT (block->succs));
2170       FOR_EACH_EDGE (e, ei, block->succs)
2171         {
2172           if (!first
2173               && BB_VISITED (e->dest))
2174             first = e->dest;
2175           else if (BB_VISITED (e->dest))
2176             worklist.quick_push (e->dest);
2177         }
2178
2179       /* Of multiple successors we have to have visited one already
2180          which is guaranteed by iteration order.  */
2181       gcc_assert (first != NULL);
2182
2183       phi_translate_set (ANTIC_OUT, ANTIC_IN (first), block, first);
2184
2185       FOR_EACH_VEC_ELT (worklist, i, bprime)
2186         {
2187           if (!gimple_seq_empty_p (phi_nodes (bprime)))
2188             {
2189               bitmap_set_t tmp = bitmap_set_new ();
2190               phi_translate_set (tmp, ANTIC_IN (bprime), block, bprime);
2191               bitmap_set_and (ANTIC_OUT, tmp);
2192               bitmap_set_free (tmp);
2193             }
2194           else
2195             bitmap_set_and (ANTIC_OUT, ANTIC_IN (bprime));
2196         }
2197     }
2198
2199   /* Prune expressions that are clobbered in block and thus become
2200      invalid if translated from ANTIC_OUT to ANTIC_IN.  */
2201   prune_clobbered_mems (ANTIC_OUT, block);
2202
2203   /* Generate ANTIC_OUT - TMP_GEN.  */
2204   S = bitmap_set_subtract (ANTIC_OUT, TMP_GEN (block));
2205
2206   /* Start ANTIC_IN with EXP_GEN - TMP_GEN.  */
2207   ANTIC_IN (block) = bitmap_set_subtract (EXP_GEN (block),
2208                                           TMP_GEN (block));
2209
2210   /* Then union in the ANTIC_OUT - TMP_GEN values,
2211      to get ANTIC_OUT U EXP_GEN - TMP_GEN */
2212   FOR_EACH_EXPR_ID_IN_SET (S, bii, bi)
2213     bitmap_value_insert_into_set (ANTIC_IN (block),
2214                                   expression_for_id (bii));
2215
2216   clean (ANTIC_IN (block));
2217
2218   if (!bitmap_set_equal (old, ANTIC_IN (block)))
2219     {
2220       changed = true;
2221       bitmap_set_bit (changed_blocks, block->index);
2222       FOR_EACH_EDGE (e, ei, block->preds)
2223         bitmap_set_bit (changed_blocks, e->src->index);
2224     }
2225   else
2226     bitmap_clear_bit (changed_blocks, block->index);
2227
2228  maybe_dump_sets:
2229   if (dump_file && (dump_flags & TDF_DETAILS))
2230     {
2231       if (ANTIC_OUT)
2232         print_bitmap_set (dump_file, ANTIC_OUT, "ANTIC_OUT", block->index);
2233
2234       print_bitmap_set (dump_file, ANTIC_IN (block), "ANTIC_IN",
2235                         block->index);
2236
2237       if (S)
2238         print_bitmap_set (dump_file, S, "S", block->index);
2239     }
2240   if (old)
2241     bitmap_set_free (old);
2242   if (S)
2243     bitmap_set_free (S);
2244   if (ANTIC_OUT)
2245     bitmap_set_free (ANTIC_OUT);
2246   return changed;
2247 }
2248
2249 /* Compute PARTIAL_ANTIC for BLOCK.
2250
2251    If succs(BLOCK) > 1 then
2252      PA_OUT[BLOCK] = value wise union of PA_IN[b] + all ANTIC_IN not
2253      in ANTIC_OUT for all succ(BLOCK)
2254    else if succs(BLOCK) == 1 then
2255      PA_OUT[BLOCK] = phi_translate (PA_IN[succ(BLOCK)])
2256
2257    PA_IN[BLOCK] = dependent_clean(PA_OUT[BLOCK] - TMP_GEN[BLOCK]
2258                                   - ANTIC_IN[BLOCK])
2259
2260 */
2261 static bool
2262 compute_partial_antic_aux (basic_block block,
2263                            bool block_has_abnormal_pred_edge)
2264 {
2265   bool changed = false;
2266   bitmap_set_t old_PA_IN;
2267   bitmap_set_t PA_OUT;
2268   edge e;
2269   edge_iterator ei;
2270   unsigned long max_pa = PARAM_VALUE (PARAM_MAX_PARTIAL_ANTIC_LENGTH);
2271
2272   old_PA_IN = PA_OUT = NULL;
2273
2274   /* If any edges from predecessors are abnormal, antic_in is empty,
2275      so do nothing.  */
2276   if (block_has_abnormal_pred_edge)
2277     goto maybe_dump_sets;
2278
2279   /* If there are too many partially anticipatable values in the
2280      block, phi_translate_set can take an exponential time: stop
2281      before the translation starts.  */
2282   if (max_pa
2283       && single_succ_p (block)
2284       && bitmap_count_bits (&PA_IN (single_succ (block))->values) > max_pa)
2285     goto maybe_dump_sets;
2286
2287   old_PA_IN = PA_IN (block);
2288   PA_OUT = bitmap_set_new ();
2289
2290   /* If the block has no successors, ANTIC_OUT is empty.  */
2291   if (EDGE_COUNT (block->succs) == 0)
2292     ;
2293   /* If we have one successor, we could have some phi nodes to
2294      translate through.  Note that we can't phi translate across DFS
2295      back edges in partial antic, because it uses a union operation on
2296      the successors.  For recurrences like IV's, we will end up
2297      generating a new value in the set on each go around (i + 3 (VH.1)
2298      VH.1 + 1 (VH.2), VH.2 + 1 (VH.3), etc), forever.  */
2299   else if (single_succ_p (block))
2300     {
2301       basic_block succ = single_succ (block);
2302       if (!(single_succ_edge (block)->flags & EDGE_DFS_BACK))
2303         phi_translate_set (PA_OUT, PA_IN (succ), block, succ);
2304     }
2305   /* If we have multiple successors, we take the union of all of
2306      them.  */
2307   else
2308     {
2309       size_t i;
2310       basic_block bprime;
2311
2312       auto_vec<basic_block> worklist (EDGE_COUNT (block->succs));
2313       FOR_EACH_EDGE (e, ei, block->succs)
2314         {
2315           if (e->flags & EDGE_DFS_BACK)
2316             continue;
2317           worklist.quick_push (e->dest);
2318         }
2319       if (worklist.length () > 0)
2320         {
2321           FOR_EACH_VEC_ELT (worklist, i, bprime)
2322             {
2323               unsigned int i;
2324               bitmap_iterator bi;
2325
2326               FOR_EACH_EXPR_ID_IN_SET (ANTIC_IN (bprime), i, bi)
2327                 bitmap_value_insert_into_set (PA_OUT,
2328                                               expression_for_id (i));
2329               if (!gimple_seq_empty_p (phi_nodes (bprime)))
2330                 {
2331                   bitmap_set_t pa_in = bitmap_set_new ();
2332                   phi_translate_set (pa_in, PA_IN (bprime), block, bprime);
2333                   FOR_EACH_EXPR_ID_IN_SET (pa_in, i, bi)
2334                     bitmap_value_insert_into_set (PA_OUT,
2335                                                   expression_for_id (i));
2336                   bitmap_set_free (pa_in);
2337                 }
2338               else
2339                 FOR_EACH_EXPR_ID_IN_SET (PA_IN (bprime), i, bi)
2340                   bitmap_value_insert_into_set (PA_OUT,
2341                                                 expression_for_id (i));
2342             }
2343         }
2344     }
2345
2346   /* Prune expressions that are clobbered in block and thus become
2347      invalid if translated from PA_OUT to PA_IN.  */
2348   prune_clobbered_mems (PA_OUT, block);
2349
2350   /* PA_IN starts with PA_OUT - TMP_GEN.
2351      Then we subtract things from ANTIC_IN.  */
2352   PA_IN (block) = bitmap_set_subtract (PA_OUT, TMP_GEN (block));
2353
2354   /* For partial antic, we want to put back in the phi results, since
2355      we will properly avoid making them partially antic over backedges.  */
2356   bitmap_ior_into (&PA_IN (block)->values, &PHI_GEN (block)->values);
2357   bitmap_ior_into (&PA_IN (block)->expressions, &PHI_GEN (block)->expressions);
2358
2359   /* PA_IN[block] = PA_IN[block] - ANTIC_IN[block] */
2360   bitmap_set_subtract_values (PA_IN (block), ANTIC_IN (block));
2361
2362   dependent_clean (PA_IN (block), ANTIC_IN (block));
2363
2364   if (!bitmap_set_equal (old_PA_IN, PA_IN (block)))
2365     {
2366       changed = true;
2367       bitmap_set_bit (changed_blocks, block->index);
2368       FOR_EACH_EDGE (e, ei, block->preds)
2369         bitmap_set_bit (changed_blocks, e->src->index);
2370     }
2371   else
2372     bitmap_clear_bit (changed_blocks, block->index);
2373
2374  maybe_dump_sets:
2375   if (dump_file && (dump_flags & TDF_DETAILS))
2376     {
2377       if (PA_OUT)
2378         print_bitmap_set (dump_file, PA_OUT, "PA_OUT", block->index);
2379
2380       print_bitmap_set (dump_file, PA_IN (block), "PA_IN", block->index);
2381     }
2382   if (old_PA_IN)
2383     bitmap_set_free (old_PA_IN);
2384   if (PA_OUT)
2385     bitmap_set_free (PA_OUT);
2386   return changed;
2387 }
2388
2389 /* Compute ANTIC and partial ANTIC sets.  */
2390
2391 static void
2392 compute_antic (void)
2393 {
2394   bool changed = true;
2395   int num_iterations = 0;
2396   basic_block block;
2397   int i;
2398
2399   /* If any predecessor edges are abnormal, we punt, so antic_in is empty.
2400      We pre-build the map of blocks with incoming abnormal edges here.  */
2401   has_abnormal_preds = sbitmap_alloc (last_basic_block_for_fn (cfun));
2402   bitmap_clear (has_abnormal_preds);
2403
2404   FOR_ALL_BB_FN (block, cfun)
2405     {
2406       edge_iterator ei;
2407       edge e;
2408
2409       FOR_EACH_EDGE (e, ei, block->preds)
2410         {
2411           e->flags &= ~EDGE_DFS_BACK;
2412           if (e->flags & EDGE_ABNORMAL)
2413             {
2414               bitmap_set_bit (has_abnormal_preds, block->index);
2415               break;
2416             }
2417         }
2418
2419       BB_VISITED (block) = 0;
2420
2421       /* While we are here, give empty ANTIC_IN sets to each block.  */
2422       ANTIC_IN (block) = bitmap_set_new ();
2423       PA_IN (block) = bitmap_set_new ();
2424     }
2425
2426   /* At the exit block we anticipate nothing.  */
2427   BB_VISITED (EXIT_BLOCK_PTR_FOR_FN (cfun)) = 1;
2428
2429   changed_blocks = sbitmap_alloc (last_basic_block_for_fn (cfun) + 1);
2430   bitmap_ones (changed_blocks);
2431   while (changed)
2432     {
2433       if (dump_file && (dump_flags & TDF_DETAILS))
2434         fprintf (dump_file, "Starting iteration %d\n", num_iterations);
2435       /* ???  We need to clear our PHI translation cache here as the
2436          ANTIC sets shrink and we restrict valid translations to
2437          those having operands with leaders in ANTIC.  Same below
2438          for PA ANTIC computation.  */
2439       num_iterations++;
2440       changed = false;
2441       for (i = postorder_num - 1; i >= 0; i--)
2442         {
2443           if (bitmap_bit_p (changed_blocks, postorder[i]))
2444             {
2445               basic_block block = BASIC_BLOCK_FOR_FN (cfun, postorder[i]);
2446               changed |= compute_antic_aux (block,
2447                                             bitmap_bit_p (has_abnormal_preds,
2448                                                       block->index));
2449             }
2450         }
2451       /* Theoretically possible, but *highly* unlikely.  */
2452       gcc_checking_assert (num_iterations < 500);
2453     }
2454
2455   statistics_histogram_event (cfun, "compute_antic iterations",
2456                               num_iterations);
2457
2458   if (do_partial_partial)
2459     {
2460       bitmap_ones (changed_blocks);
2461       mark_dfs_back_edges ();
2462       num_iterations = 0;
2463       changed = true;
2464       while (changed)
2465         {
2466           if (dump_file && (dump_flags & TDF_DETAILS))
2467             fprintf (dump_file, "Starting iteration %d\n", num_iterations);
2468           num_iterations++;
2469           changed = false;
2470           for (i = postorder_num - 1 ; i >= 0; i--)
2471             {
2472               if (bitmap_bit_p (changed_blocks, postorder[i]))
2473                 {
2474                   basic_block block = BASIC_BLOCK_FOR_FN (cfun, postorder[i]);
2475                   changed
2476                     |= compute_partial_antic_aux (block,
2477                                                   bitmap_bit_p (has_abnormal_preds,
2478                                                             block->index));
2479                 }
2480             }
2481           /* Theoretically possible, but *highly* unlikely.  */
2482           gcc_checking_assert (num_iterations < 500);
2483         }
2484       statistics_histogram_event (cfun, "compute_partial_antic iterations",
2485                                   num_iterations);
2486     }
2487   sbitmap_free (has_abnormal_preds);
2488   sbitmap_free (changed_blocks);
2489 }
2490
2491
2492 /* Inserted expressions are placed onto this worklist, which is used
2493    for performing quick dead code elimination of insertions we made
2494    that didn't turn out to be necessary.   */
2495 static bitmap inserted_exprs;
2496
2497 /* The actual worker for create_component_ref_by_pieces.  */
2498
2499 static tree
2500 create_component_ref_by_pieces_1 (basic_block block, vn_reference_t ref,
2501                                   unsigned int *operand, gimple_seq *stmts)
2502 {
2503   vn_reference_op_t currop = &ref->operands[*operand];
2504   tree genop;
2505   ++*operand;
2506   switch (currop->opcode)
2507     {
2508     case CALL_EXPR:
2509       {
2510         tree folded, sc = NULL_TREE;
2511         unsigned int nargs = 0;
2512         tree fn, *args;
2513         if (TREE_CODE (currop->op0) == FUNCTION_DECL)
2514           fn = currop->op0;
2515         else
2516           fn = find_or_generate_expression (block, currop->op0, stmts);
2517         if (!fn)
2518           return NULL_TREE;
2519         if (currop->op1)
2520           {
2521             sc = find_or_generate_expression (block, currop->op1, stmts);
2522             if (!sc)
2523               return NULL_TREE;
2524           }
2525         args = XNEWVEC (tree, ref->operands.length () - 1);
2526         while (*operand < ref->operands.length ())
2527           {
2528             args[nargs] = create_component_ref_by_pieces_1 (block, ref,
2529                                                             operand, stmts);
2530             if (!args[nargs])
2531               return NULL_TREE;
2532             nargs++;
2533           }
2534         folded = build_call_array (currop->type,
2535                                    (TREE_CODE (fn) == FUNCTION_DECL
2536                                     ? build_fold_addr_expr (fn) : fn),
2537                                    nargs, args);
2538         if (currop->with_bounds)
2539           CALL_WITH_BOUNDS_P (folded) = true;
2540         free (args);
2541         if (sc)
2542           CALL_EXPR_STATIC_CHAIN (folded) = sc;
2543         return folded;
2544       }
2545
2546     case MEM_REF:
2547       {
2548         tree baseop = create_component_ref_by_pieces_1 (block, ref, operand,
2549                                                         stmts);
2550         if (!baseop)
2551           return NULL_TREE;
2552         tree offset = currop->op0;
2553         if (TREE_CODE (baseop) == ADDR_EXPR
2554             && handled_component_p (TREE_OPERAND (baseop, 0)))
2555           {
2556             HOST_WIDE_INT off;
2557             tree base;
2558             base = get_addr_base_and_unit_offset (TREE_OPERAND (baseop, 0),
2559                                                   &off);
2560             gcc_assert (base);
2561             offset = int_const_binop (PLUS_EXPR, offset,
2562                                       build_int_cst (TREE_TYPE (offset),
2563                                                      off));
2564             baseop = build_fold_addr_expr (base);
2565           }
2566         return fold_build2 (MEM_REF, currop->type, baseop, offset);
2567       }
2568
2569     case TARGET_MEM_REF:
2570       {
2571         tree genop0 = NULL_TREE, genop1 = NULL_TREE;
2572         vn_reference_op_t nextop = &ref->operands[++*operand];
2573         tree baseop = create_component_ref_by_pieces_1 (block, ref, operand,
2574                                                         stmts);
2575         if (!baseop)
2576           return NULL_TREE;
2577         if (currop->op0)
2578           {
2579             genop0 = find_or_generate_expression (block, currop->op0, stmts);
2580             if (!genop0)
2581               return NULL_TREE;
2582           }
2583         if (nextop->op0)
2584           {
2585             genop1 = find_or_generate_expression (block, nextop->op0, stmts);
2586             if (!genop1)
2587               return NULL_TREE;
2588           }
2589         return build5 (TARGET_MEM_REF, currop->type,
2590                        baseop, currop->op2, genop0, currop->op1, genop1);
2591       }
2592
2593     case ADDR_EXPR:
2594       if (currop->op0)
2595         {
2596           gcc_assert (is_gimple_min_invariant (currop->op0));
2597           return currop->op0;
2598         }
2599       /* Fallthrough.  */
2600     case REALPART_EXPR:
2601     case IMAGPART_EXPR:
2602     case VIEW_CONVERT_EXPR:
2603       {
2604         tree genop0 = create_component_ref_by_pieces_1 (block, ref, operand,
2605                                                         stmts);
2606         if (!genop0)
2607           return NULL_TREE;
2608         return fold_build1 (currop->opcode, currop->type, genop0);
2609       }
2610
2611     case WITH_SIZE_EXPR:
2612       {
2613         tree genop0 = create_component_ref_by_pieces_1 (block, ref, operand,
2614                                                         stmts);
2615         if (!genop0)
2616           return NULL_TREE;
2617         tree genop1 = find_or_generate_expression (block, currop->op0, stmts);
2618         if (!genop1)
2619           return NULL_TREE;
2620         return fold_build2 (currop->opcode, currop->type, genop0, genop1);
2621       }
2622
2623     case BIT_FIELD_REF:
2624       {
2625         tree genop0 = create_component_ref_by_pieces_1 (block, ref, operand,
2626                                                         stmts);
2627         if (!genop0)
2628           return NULL_TREE;
2629         tree op1 = currop->op0;
2630         tree op2 = currop->op1;
2631         return fold_build3 (BIT_FIELD_REF, currop->type, genop0, op1, op2);
2632       }
2633
2634       /* For array ref vn_reference_op's, operand 1 of the array ref
2635          is op0 of the reference op and operand 3 of the array ref is
2636          op1.  */
2637     case ARRAY_RANGE_REF:
2638     case ARRAY_REF:
2639       {
2640         tree genop0;
2641         tree genop1 = currop->op0;
2642         tree genop2 = currop->op1;
2643         tree genop3 = currop->op2;
2644         genop0 = create_component_ref_by_pieces_1 (block, ref, operand,
2645                                                    stmts);
2646         if (!genop0)
2647           return NULL_TREE;
2648         genop1 = find_or_generate_expression (block, genop1, stmts);
2649         if (!genop1)
2650           return NULL_TREE;
2651         if (genop2)
2652           {
2653             tree domain_type = TYPE_DOMAIN (TREE_TYPE (genop0));
2654             /* Drop zero minimum index if redundant.  */
2655             if (integer_zerop (genop2)
2656                 && (!domain_type
2657                     || integer_zerop (TYPE_MIN_VALUE (domain_type))))
2658               genop2 = NULL_TREE;
2659             else
2660               {
2661                 genop2 = find_or_generate_expression (block, genop2, stmts);
2662                 if (!genop2)
2663                   return NULL_TREE;
2664               }
2665           }
2666         if (genop3)
2667           {
2668             tree elmt_type = TREE_TYPE (TREE_TYPE (genop0));
2669             /* We can't always put a size in units of the element alignment
2670                here as the element alignment may be not visible.  See
2671                PR43783.  Simply drop the element size for constant
2672                sizes.  */
2673             if (tree_int_cst_equal (genop3, TYPE_SIZE_UNIT (elmt_type)))
2674               genop3 = NULL_TREE;
2675             else
2676               {
2677                 genop3 = size_binop (EXACT_DIV_EXPR, genop3,
2678                                      size_int (TYPE_ALIGN_UNIT (elmt_type)));
2679                 genop3 = find_or_generate_expression (block, genop3, stmts);
2680                 if (!genop3)
2681                   return NULL_TREE;
2682               }
2683           }
2684         return build4 (currop->opcode, currop->type, genop0, genop1,
2685                        genop2, genop3);
2686       }
2687     case COMPONENT_REF:
2688       {
2689         tree op0;
2690         tree op1;
2691         tree genop2 = currop->op1;
2692         op0 = create_component_ref_by_pieces_1 (block, ref, operand, stmts);
2693         if (!op0)
2694           return NULL_TREE;
2695         /* op1 should be a FIELD_DECL, which are represented by themselves.  */
2696         op1 = currop->op0;
2697         if (genop2)
2698           {
2699             genop2 = find_or_generate_expression (block, genop2, stmts);
2700             if (!genop2)
2701               return NULL_TREE;
2702           }
2703         return fold_build3 (COMPONENT_REF, TREE_TYPE (op1), op0, op1, genop2);
2704       }
2705
2706     case SSA_NAME:
2707       {
2708         genop = find_or_generate_expression (block, currop->op0, stmts);
2709         return genop;
2710       }
2711     case STRING_CST:
2712     case INTEGER_CST:
2713     case COMPLEX_CST:
2714     case VECTOR_CST:
2715     case REAL_CST:
2716     case CONSTRUCTOR:
2717     case VAR_DECL:
2718     case PARM_DECL:
2719     case CONST_DECL:
2720     case RESULT_DECL:
2721     case FUNCTION_DECL:
2722       return currop->op0;
2723
2724     default:
2725       gcc_unreachable ();
2726     }
2727 }
2728
2729 /* For COMPONENT_REF's and ARRAY_REF's, we can't have any intermediates for the
2730    COMPONENT_REF or MEM_REF or ARRAY_REF portion, because we'd end up with
2731    trying to rename aggregates into ssa form directly, which is a no no.
2732
2733    Thus, this routine doesn't create temporaries, it just builds a
2734    single access expression for the array, calling
2735    find_or_generate_expression to build the innermost pieces.
2736
2737    This function is a subroutine of create_expression_by_pieces, and
2738    should not be called on it's own unless you really know what you
2739    are doing.  */
2740
2741 static tree
2742 create_component_ref_by_pieces (basic_block block, vn_reference_t ref,
2743                                 gimple_seq *stmts)
2744 {
2745   unsigned int op = 0;
2746   return create_component_ref_by_pieces_1 (block, ref, &op, stmts);
2747 }
2748
2749 /* Find a simple leader for an expression, or generate one using
2750    create_expression_by_pieces from a NARY expression for the value.
2751    BLOCK is the basic_block we are looking for leaders in.
2752    OP is the tree expression to find a leader for or generate.
2753    Returns the leader or NULL_TREE on failure.  */
2754
2755 static tree
2756 find_or_generate_expression (basic_block block, tree op, gimple_seq *stmts)
2757 {
2758   pre_expr expr = get_or_alloc_expr_for (op);
2759   unsigned int lookfor = get_expr_value_id (expr);
2760   pre_expr leader = bitmap_find_leader (AVAIL_OUT (block), lookfor);
2761   if (leader)
2762     {
2763       if (leader->kind == NAME)
2764         return PRE_EXPR_NAME (leader);
2765       else if (leader->kind == CONSTANT)
2766         return PRE_EXPR_CONSTANT (leader);
2767
2768       /* Defer.  */
2769       return NULL_TREE;
2770     }
2771
2772   /* It must be a complex expression, so generate it recursively.  Note
2773      that this is only necessary to handle gcc.dg/tree-ssa/ssa-pre28.c
2774      where the insert algorithm fails to insert a required expression.  */
2775   bitmap exprset = value_expressions[lookfor];
2776   bitmap_iterator bi;
2777   unsigned int i;
2778   EXECUTE_IF_SET_IN_BITMAP (exprset, 0, i, bi)
2779     {
2780       pre_expr temp = expression_for_id (i);
2781       /* We cannot insert random REFERENCE expressions at arbitrary
2782          places.  We can insert NARYs which eventually re-materializes
2783          its operand values.  */
2784       if (temp->kind == NARY)
2785         return create_expression_by_pieces (block, temp, stmts,
2786                                             get_expr_type (expr));
2787     }
2788
2789   /* Defer.  */
2790   return NULL_TREE;
2791 }
2792
2793 #define NECESSARY GF_PLF_1
2794
2795 /* Create an expression in pieces, so that we can handle very complex
2796    expressions that may be ANTIC, but not necessary GIMPLE.
2797    BLOCK is the basic block the expression will be inserted into,
2798    EXPR is the expression to insert (in value form)
2799    STMTS is a statement list to append the necessary insertions into.
2800
2801    This function will die if we hit some value that shouldn't be
2802    ANTIC but is (IE there is no leader for it, or its components).
2803    The function returns NULL_TREE in case a different antic expression
2804    has to be inserted first.
2805    This function may also generate expressions that are themselves
2806    partially or fully redundant.  Those that are will be either made
2807    fully redundant during the next iteration of insert (for partially
2808    redundant ones), or eliminated by eliminate (for fully redundant
2809    ones).  */
2810
2811 static tree
2812 create_expression_by_pieces (basic_block block, pre_expr expr,
2813                              gimple_seq *stmts, tree type)
2814 {
2815   tree name;
2816   tree folded;
2817   gimple_seq forced_stmts = NULL;
2818   unsigned int value_id;
2819   gimple_stmt_iterator gsi;
2820   tree exprtype = type ? type : get_expr_type (expr);
2821   pre_expr nameexpr;
2822   gassign *newstmt;
2823
2824   switch (expr->kind)
2825     {
2826       /* We may hit the NAME/CONSTANT case if we have to convert types
2827          that value numbering saw through.  */
2828     case NAME:
2829       folded = PRE_EXPR_NAME (expr);
2830       break;
2831     case CONSTANT:
2832       folded = PRE_EXPR_CONSTANT (expr);
2833       break;
2834     case REFERENCE:
2835       {
2836         vn_reference_t ref = PRE_EXPR_REFERENCE (expr);
2837         folded = create_component_ref_by_pieces (block, ref, stmts);
2838         if (!folded)
2839           return NULL_TREE;
2840       }
2841       break;
2842     case NARY:
2843       {
2844         vn_nary_op_t nary = PRE_EXPR_NARY (expr);
2845         tree *genop = XALLOCAVEC (tree, nary->length);
2846         unsigned i;
2847         for (i = 0; i < nary->length; ++i)
2848           {
2849             genop[i] = find_or_generate_expression (block, nary->op[i], stmts);
2850             if (!genop[i])
2851               return NULL_TREE;
2852             /* Ensure genop[] is properly typed for POINTER_PLUS_EXPR.  It
2853                may have conversions stripped.  */
2854             if (nary->opcode == POINTER_PLUS_EXPR)
2855               {
2856                 if (i == 0)
2857                   genop[i] = gimple_convert (&forced_stmts,
2858                                              nary->type, genop[i]);
2859                 else if (i == 1)
2860                   genop[i] = gimple_convert (&forced_stmts,
2861                                              sizetype, genop[i]);
2862               }
2863             else
2864               genop[i] = gimple_convert (&forced_stmts,
2865                                          TREE_TYPE (nary->op[i]), genop[i]);
2866           }
2867         if (nary->opcode == CONSTRUCTOR)
2868           {
2869             vec<constructor_elt, va_gc> *elts = NULL;
2870             for (i = 0; i < nary->length; ++i)
2871               CONSTRUCTOR_APPEND_ELT (elts, NULL_TREE, genop[i]);
2872             folded = build_constructor (nary->type, elts);
2873           }
2874         else
2875           {
2876             switch (nary->length)
2877               {
2878               case 1:
2879                 folded = fold_build1 (nary->opcode, nary->type,
2880                                       genop[0]);
2881                 break;
2882               case 2:
2883                 folded = fold_build2 (nary->opcode, nary->type,
2884                                       genop[0], genop[1]);
2885                 break;
2886               case 3:
2887                 folded = fold_build3 (nary->opcode, nary->type,
2888                                       genop[0], genop[1], genop[2]);
2889                 break;
2890               default:
2891                 gcc_unreachable ();
2892               }
2893           }
2894       }
2895       break;
2896     default:
2897       gcc_unreachable ();
2898     }
2899
2900   if (!useless_type_conversion_p (exprtype, TREE_TYPE (folded)))
2901     folded = fold_convert (exprtype, folded);
2902
2903   /* Force the generated expression to be a sequence of GIMPLE
2904      statements.
2905      We have to call unshare_expr because force_gimple_operand may
2906      modify the tree we pass to it.  */
2907   gimple_seq tem = NULL;
2908   folded = force_gimple_operand (unshare_expr (folded), &tem,
2909                                  false, NULL);
2910   gimple_seq_add_seq_without_update (&forced_stmts, tem);
2911
2912   /* If we have any intermediate expressions to the value sets, add them
2913      to the value sets and chain them in the instruction stream.  */
2914   if (forced_stmts)
2915     {
2916       gsi = gsi_start (forced_stmts);
2917       for (; !gsi_end_p (gsi); gsi_next (&gsi))
2918         {
2919           gimple stmt = gsi_stmt (gsi);
2920           tree forcedname = gimple_get_lhs (stmt);
2921           pre_expr nameexpr;
2922
2923           if (TREE_CODE (forcedname) == SSA_NAME)
2924             {
2925               bitmap_set_bit (inserted_exprs, SSA_NAME_VERSION (forcedname));
2926               VN_INFO_GET (forcedname)->valnum = forcedname;
2927               VN_INFO (forcedname)->value_id = get_next_value_id ();
2928               nameexpr = get_or_alloc_expr_for_name (forcedname);
2929               add_to_value (VN_INFO (forcedname)->value_id, nameexpr);
2930               bitmap_value_replace_in_set (NEW_SETS (block), nameexpr);
2931               bitmap_value_replace_in_set (AVAIL_OUT (block), nameexpr);
2932             }
2933
2934           gimple_set_vuse (stmt, BB_LIVE_VOP_ON_EXIT (block));
2935           gimple_set_modified (stmt, true);
2936         }
2937       gimple_seq_add_seq (stmts, forced_stmts);
2938     }
2939
2940   name = make_temp_ssa_name (exprtype, NULL, "pretmp");
2941   newstmt = gimple_build_assign (name, folded);
2942   gimple_set_vuse (newstmt, BB_LIVE_VOP_ON_EXIT (block));
2943   gimple_set_modified (newstmt, true);
2944   gimple_set_plf (newstmt, NECESSARY, false);
2945
2946   gimple_seq_add_stmt (stmts, newstmt);
2947   bitmap_set_bit (inserted_exprs, SSA_NAME_VERSION (name));
2948
2949   /* Fold the last statement.  */
2950   gsi = gsi_last (*stmts);
2951   if (fold_stmt_inplace (&gsi))
2952     update_stmt (gsi_stmt (gsi));
2953
2954   /* Add a value number to the temporary.
2955      The value may already exist in either NEW_SETS, or AVAIL_OUT, because
2956      we are creating the expression by pieces, and this particular piece of
2957      the expression may have been represented.  There is no harm in replacing
2958      here.  */
2959   value_id = get_expr_value_id (expr);
2960   VN_INFO_GET (name)->value_id = value_id;
2961   VN_INFO (name)->valnum = sccvn_valnum_from_value_id (value_id);
2962   if (VN_INFO (name)->valnum == NULL_TREE)
2963     VN_INFO (name)->valnum = name;
2964   gcc_assert (VN_INFO (name)->valnum != NULL_TREE);
2965   nameexpr = get_or_alloc_expr_for_name (name);
2966   add_to_value (value_id, nameexpr);
2967   if (NEW_SETS (block))
2968     bitmap_value_replace_in_set (NEW_SETS (block), nameexpr);
2969   bitmap_value_replace_in_set (AVAIL_OUT (block), nameexpr);
2970
2971   pre_stats.insertions++;
2972   if (dump_file && (dump_flags & TDF_DETAILS))
2973     {
2974       fprintf (dump_file, "Inserted ");
2975       print_gimple_stmt (dump_file, newstmt, 0, 0);
2976       fprintf (dump_file, " in predecessor %d (%04d)\n",
2977                block->index, value_id);
2978     }
2979
2980   return name;
2981 }
2982
2983
2984 /* Insert the to-be-made-available values of expression EXPRNUM for each
2985    predecessor, stored in AVAIL, into the predecessors of BLOCK, and
2986    merge the result with a phi node, given the same value number as
2987    NODE.  Return true if we have inserted new stuff.  */
2988
2989 static bool
2990 insert_into_preds_of_block (basic_block block, unsigned int exprnum,
2991                             vec<pre_expr> avail)
2992 {
2993   pre_expr expr = expression_for_id (exprnum);
2994   pre_expr newphi;
2995   unsigned int val = get_expr_value_id (expr);
2996   edge pred;
2997   bool insertions = false;
2998   bool nophi = false;
2999   basic_block bprime;
3000   pre_expr eprime;
3001   edge_iterator ei;
3002   tree type = get_expr_type (expr);
3003   tree temp;
3004   gphi *phi;
3005
3006   /* Make sure we aren't creating an induction variable.  */
3007   if (bb_loop_depth (block) > 0 && EDGE_COUNT (block->preds) == 2)
3008     {
3009       bool firstinsideloop = false;
3010       bool secondinsideloop = false;
3011       firstinsideloop = flow_bb_inside_loop_p (block->loop_father,
3012                                                EDGE_PRED (block, 0)->src);
3013       secondinsideloop = flow_bb_inside_loop_p (block->loop_father,
3014                                                 EDGE_PRED (block, 1)->src);
3015       /* Induction variables only have one edge inside the loop.  */
3016       if ((firstinsideloop ^ secondinsideloop)
3017           && expr->kind != REFERENCE)
3018         {
3019           if (dump_file && (dump_flags & TDF_DETAILS))
3020             fprintf (dump_file, "Skipping insertion of phi for partial redundancy: Looks like an induction variable\n");
3021           nophi = true;
3022         }
3023     }
3024
3025   /* Make the necessary insertions.  */
3026   FOR_EACH_EDGE (pred, ei, block->preds)
3027     {
3028       gimple_seq stmts = NULL;
3029       tree builtexpr;
3030       bprime = pred->src;
3031       eprime = avail[pred->dest_idx];
3032
3033       if (eprime->kind != NAME && eprime->kind != CONSTANT)
3034         {
3035           builtexpr = create_expression_by_pieces (bprime, eprime,
3036                                                    &stmts, type);
3037           gcc_assert (!(pred->flags & EDGE_ABNORMAL));
3038           gsi_insert_seq_on_edge (pred, stmts);
3039           if (!builtexpr)
3040             {
3041               /* We cannot insert a PHI node if we failed to insert
3042                  on one edge.  */
3043               nophi = true;
3044               continue;
3045             }
3046           avail[pred->dest_idx] = get_or_alloc_expr_for_name (builtexpr);
3047           insertions = true;
3048         }
3049       else if (eprime->kind == CONSTANT)
3050         {
3051           /* Constants may not have the right type, fold_convert
3052              should give us back a constant with the right type.  */
3053           tree constant = PRE_EXPR_CONSTANT (eprime);
3054           if (!useless_type_conversion_p (type, TREE_TYPE (constant)))
3055             {
3056               tree builtexpr = fold_convert (type, constant);
3057               if (!is_gimple_min_invariant (builtexpr))
3058                 {
3059                   tree forcedexpr = force_gimple_operand (builtexpr,
3060                                                           &stmts, true,
3061                                                           NULL);
3062                   if (!is_gimple_min_invariant (forcedexpr))
3063                     {
3064                       if (forcedexpr != builtexpr)
3065                         {
3066                           VN_INFO_GET (forcedexpr)->valnum = PRE_EXPR_CONSTANT (eprime);
3067                           VN_INFO (forcedexpr)->value_id = get_expr_value_id (eprime);
3068                         }
3069                       if (stmts)
3070                         {
3071                           gimple_stmt_iterator gsi;
3072                           gsi = gsi_start (stmts);
3073                           for (; !gsi_end_p (gsi); gsi_next (&gsi))
3074                             {
3075                               gimple stmt = gsi_stmt (gsi);
3076                               tree lhs = gimple_get_lhs (stmt);
3077                               if (TREE_CODE (lhs) == SSA_NAME)
3078                                 bitmap_set_bit (inserted_exprs,
3079                                                 SSA_NAME_VERSION (lhs));
3080                               gimple_set_plf (stmt, NECESSARY, false);
3081                             }
3082                           gsi_insert_seq_on_edge (pred, stmts);
3083                         }
3084                       avail[pred->dest_idx]
3085                         = get_or_alloc_expr_for_name (forcedexpr);
3086                     }
3087                 }
3088               else
3089                 avail[pred->dest_idx]
3090                     = get_or_alloc_expr_for_constant (builtexpr);
3091             }
3092         }
3093       else if (eprime->kind == NAME)
3094         {
3095           /* We may have to do a conversion because our value
3096              numbering can look through types in certain cases, but
3097              our IL requires all operands of a phi node have the same
3098              type.  */
3099           tree name = PRE_EXPR_NAME (eprime);
3100           if (!useless_type_conversion_p (type, TREE_TYPE (name)))
3101             {
3102               tree builtexpr;
3103               tree forcedexpr;
3104               builtexpr = fold_convert (type, name);
3105               forcedexpr = force_gimple_operand (builtexpr,
3106                                                  &stmts, true,
3107                                                  NULL);
3108
3109               if (forcedexpr != name)
3110                 {
3111                   VN_INFO_GET (forcedexpr)->valnum = VN_INFO (name)->valnum;
3112                   VN_INFO (forcedexpr)->value_id = VN_INFO (name)->value_id;
3113                 }
3114
3115               if (stmts)
3116                 {
3117                   gimple_stmt_iterator gsi;
3118                   gsi = gsi_start (stmts);
3119                   for (; !gsi_end_p (gsi); gsi_next (&gsi))
3120                     {
3121                       gimple stmt = gsi_stmt (gsi);
3122                       tree lhs = gimple_get_lhs (stmt);
3123                       if (TREE_CODE (lhs) == SSA_NAME)
3124                         bitmap_set_bit (inserted_exprs, SSA_NAME_VERSION (lhs));
3125                       gimple_set_plf (stmt, NECESSARY, false);
3126                     }
3127                   gsi_insert_seq_on_edge (pred, stmts);
3128                 }
3129               avail[pred->dest_idx] = get_or_alloc_expr_for_name (forcedexpr);
3130             }
3131         }
3132     }
3133   /* If we didn't want a phi node, and we made insertions, we still have
3134      inserted new stuff, and thus return true.  If we didn't want a phi node,
3135      and didn't make insertions, we haven't added anything new, so return
3136      false.  */
3137   if (nophi && insertions)
3138     return true;
3139   else if (nophi && !insertions)
3140     return false;
3141
3142   /* Now build a phi for the new variable.  */
3143   temp = make_temp_ssa_name (type, NULL, "prephitmp");
3144   phi = create_phi_node (temp, block);
3145
3146   gimple_set_plf (phi, NECESSARY, false);
3147   VN_INFO_GET (temp)->value_id = val;
3148   VN_INFO (temp)->valnum = sccvn_valnum_from_value_id (val);
3149   if (VN_INFO (temp)->valnum == NULL_TREE)
3150     VN_INFO (temp)->valnum = temp;
3151   bitmap_set_bit (inserted_exprs, SSA_NAME_VERSION (temp));
3152   FOR_EACH_EDGE (pred, ei, block->preds)
3153     {
3154       pre_expr ae = avail[pred->dest_idx];
3155       gcc_assert (get_expr_type (ae) == type
3156                   || useless_type_conversion_p (type, get_expr_type (ae)));
3157       if (ae->kind == CONSTANT)
3158         add_phi_arg (phi, unshare_expr (PRE_EXPR_CONSTANT (ae)),
3159                      pred, UNKNOWN_LOCATION);
3160       else
3161         add_phi_arg (phi, PRE_EXPR_NAME (ae), pred, UNKNOWN_LOCATION);
3162     }
3163
3164   newphi = get_or_alloc_expr_for_name (temp);
3165   add_to_value (val, newphi);
3166
3167   /* The value should *not* exist in PHI_GEN, or else we wouldn't be doing
3168      this insertion, since we test for the existence of this value in PHI_GEN
3169      before proceeding with the partial redundancy checks in insert_aux.
3170
3171      The value may exist in AVAIL_OUT, in particular, it could be represented
3172      by the expression we are trying to eliminate, in which case we want the
3173      replacement to occur.  If it's not existing in AVAIL_OUT, we want it
3174      inserted there.
3175
3176      Similarly, to the PHI_GEN case, the value should not exist in NEW_SETS of
3177      this block, because if it did, it would have existed in our dominator's
3178      AVAIL_OUT, and would have been skipped due to the full redundancy check.
3179   */
3180
3181   bitmap_insert_into_set (PHI_GEN (block), newphi);
3182   bitmap_value_replace_in_set (AVAIL_OUT (block),
3183                                newphi);
3184   bitmap_insert_into_set (NEW_SETS (block),
3185                           newphi);
3186
3187   /* If we insert a PHI node for a conversion of another PHI node
3188      in the same basic-block try to preserve range information.
3189      This is important so that followup loop passes receive optimal
3190      number of iteration analysis results.  See PR61743.  */
3191   if (expr->kind == NARY
3192       && CONVERT_EXPR_CODE_P (expr->u.nary->opcode)
3193       && TREE_CODE (expr->u.nary->op[0]) == SSA_NAME
3194       && gimple_bb (SSA_NAME_DEF_STMT (expr->u.nary->op[0])) == block
3195       && INTEGRAL_TYPE_P (type)
3196       && INTEGRAL_TYPE_P (TREE_TYPE (expr->u.nary->op[0]))
3197       && (TYPE_PRECISION (type)
3198           >= TYPE_PRECISION (TREE_TYPE (expr->u.nary->op[0])))
3199       && SSA_NAME_RANGE_INFO (expr->u.nary->op[0]))
3200     {
3201       wide_int min, max;
3202       if (get_range_info (expr->u.nary->op[0], &min, &max) == VR_RANGE
3203           && !wi::neg_p (min, SIGNED)
3204           && !wi::neg_p (max, SIGNED))
3205         /* Just handle extension and sign-changes of all-positive ranges.  */
3206         set_range_info (temp,
3207                         SSA_NAME_RANGE_TYPE (expr->u.nary->op[0]),
3208                         wide_int_storage::from (min, TYPE_PRECISION (type),
3209                                                 TYPE_SIGN (type)),
3210                         wide_int_storage::from (max, TYPE_PRECISION (type),
3211                                                 TYPE_SIGN (type)));
3212     }
3213
3214   if (dump_file && (dump_flags & TDF_DETAILS))
3215     {
3216       fprintf (dump_file, "Created phi ");
3217       print_gimple_stmt (dump_file, phi, 0, 0);
3218       fprintf (dump_file, " in block %d (%04d)\n", block->index, val);
3219     }
3220   pre_stats.phis++;
3221   return true;
3222 }
3223
3224
3225
3226 /* Perform insertion of partially redundant values.
3227    For BLOCK, do the following:
3228    1.  Propagate the NEW_SETS of the dominator into the current block.
3229    If the block has multiple predecessors,
3230        2a. Iterate over the ANTIC expressions for the block to see if
3231            any of them are partially redundant.
3232        2b. If so, insert them into the necessary predecessors to make
3233            the expression fully redundant.
3234        2c. Insert a new PHI merging the values of the predecessors.
3235        2d. Insert the new PHI, and the new expressions, into the
3236            NEW_SETS set.
3237    3. Recursively call ourselves on the dominator children of BLOCK.
3238
3239    Steps 1, 2a, and 3 are done by insert_aux. 2b, 2c and 2d are done by
3240    do_regular_insertion and do_partial_insertion.
3241
3242 */
3243
3244 static bool
3245 do_regular_insertion (basic_block block, basic_block dom)
3246 {
3247   bool new_stuff = false;
3248   vec<pre_expr> exprs;
3249   pre_expr expr;
3250   auto_vec<pre_expr> avail;
3251   int i;
3252
3253   exprs = sorted_array_from_bitmap_set (ANTIC_IN (block));
3254   avail.safe_grow (EDGE_COUNT (block->preds));
3255
3256   FOR_EACH_VEC_ELT (exprs, i, expr)
3257     {
3258       if (expr->kind == NARY
3259           || expr->kind == REFERENCE)
3260         {
3261           unsigned int val;
3262           bool by_some = false;
3263           bool cant_insert = false;
3264           bool all_same = true;
3265           pre_expr first_s = NULL;
3266           edge pred;
3267           basic_block bprime;
3268           pre_expr eprime = NULL;
3269           edge_iterator ei;
3270           pre_expr edoubleprime = NULL;
3271           bool do_insertion = false;
3272
3273           val = get_expr_value_id (expr);
3274           if (bitmap_set_contains_value (PHI_GEN (block), val))
3275             continue;
3276           if (bitmap_set_contains_value (AVAIL_OUT (dom), val))
3277             {
3278               if (dump_file && (dump_flags & TDF_DETAILS))
3279                 {
3280                   fprintf (dump_file, "Found fully redundant value: ");
3281                   print_pre_expr (dump_file, expr);
3282                   fprintf (dump_file, "\n");
3283                 }
3284               continue;
3285             }
3286
3287           FOR_EACH_EDGE (pred, ei, block->preds)
3288             {
3289               unsigned int vprime;
3290
3291               /* We should never run insertion for the exit block
3292                  and so not come across fake pred edges.  */
3293               gcc_assert (!(pred->flags & EDGE_FAKE));
3294               bprime = pred->src;
3295               eprime = phi_translate (expr, ANTIC_IN (block), NULL,
3296                                       bprime, block);
3297
3298               /* eprime will generally only be NULL if the
3299                  value of the expression, translated
3300                  through the PHI for this predecessor, is
3301                  undefined.  If that is the case, we can't
3302                  make the expression fully redundant,
3303                  because its value is undefined along a
3304                  predecessor path.  We can thus break out
3305                  early because it doesn't matter what the
3306                  rest of the results are.  */
3307               if (eprime == NULL)
3308                 {
3309                   avail[pred->dest_idx] = NULL;
3310                   cant_insert = true;
3311                   break;
3312                 }
3313
3314               eprime = fully_constant_expression (eprime);
3315               vprime = get_expr_value_id (eprime);
3316               edoubleprime = bitmap_find_leader (AVAIL_OUT (bprime),
3317                                                  vprime);
3318               if (edoubleprime == NULL)
3319                 {
3320                   avail[pred->dest_idx] = eprime;
3321                   all_same = false;
3322                 }
3323               else
3324                 {
3325                   avail[pred->dest_idx] = edoubleprime;
3326                   by_some = true;
3327                   /* We want to perform insertions to remove a redundancy on
3328                      a path in the CFG we want to optimize for speed.  */
3329                   if (optimize_edge_for_speed_p (pred))
3330                     do_insertion = true;
3331                   if (first_s == NULL)
3332                     first_s = edoubleprime;
3333                   else if (!pre_expr_d::equal (first_s, edoubleprime))
3334                     all_same = false;
3335                 }
3336             }
3337           /* If we can insert it, it's not the same value
3338              already existing along every predecessor, and
3339              it's defined by some predecessor, it is
3340              partially redundant.  */
3341           if (!cant_insert && !all_same && by_some)
3342             {
3343               if (!do_insertion)
3344                 {
3345                   if (dump_file && (dump_flags & TDF_DETAILS))
3346                     {
3347                       fprintf (dump_file, "Skipping partial redundancy for "
3348                                "expression ");
3349                       print_pre_expr (dump_file, expr);
3350                       fprintf (dump_file, " (%04d), no redundancy on to be "
3351                                "optimized for speed edge\n", val);
3352                     }
3353                 }
3354               else if (dbg_cnt (treepre_insert))
3355                 {
3356                   if (dump_file && (dump_flags & TDF_DETAILS))
3357                     {
3358                       fprintf (dump_file, "Found partial redundancy for "
3359                                "expression ");
3360                       print_pre_expr (dump_file, expr);
3361                       fprintf (dump_file, " (%04d)\n",
3362                                get_expr_value_id (expr));
3363                     }
3364                   if (insert_into_preds_of_block (block,
3365                                                   get_expression_id (expr),
3366                                                   avail))
3367                     new_stuff = true;
3368                 }
3369             }
3370           /* If all edges produce the same value and that value is
3371              an invariant, then the PHI has the same value on all
3372              edges.  Note this.  */
3373           else if (!cant_insert && all_same)
3374             {
3375               gcc_assert (edoubleprime->kind == CONSTANT
3376                           || edoubleprime->kind == NAME);
3377
3378               tree temp = make_temp_ssa_name (get_expr_type (expr),
3379                                               NULL, "pretmp");
3380               gassign *assign
3381                 = gimple_build_assign (temp,
3382                                        edoubleprime->kind == CONSTANT ?
3383                                        PRE_EXPR_CONSTANT (edoubleprime) :
3384                                        PRE_EXPR_NAME (edoubleprime));
3385               gimple_stmt_iterator gsi = gsi_after_labels (block);
3386               gsi_insert_before (&gsi, assign, GSI_NEW_STMT);
3387
3388               gimple_set_plf (assign, NECESSARY, false);
3389               VN_INFO_GET (temp)->value_id = val;
3390               VN_INFO (temp)->valnum = sccvn_valnum_from_value_id (val);
3391               if (VN_INFO (temp)->valnum == NULL_TREE)
3392                 VN_INFO (temp)->valnum = temp;
3393               bitmap_set_bit (inserted_exprs, SSA_NAME_VERSION (temp));
3394               pre_expr newe = get_or_alloc_expr_for_name (temp);
3395               add_to_value (val, newe);
3396               bitmap_value_replace_in_set (AVAIL_OUT (block), newe);
3397               bitmap_insert_into_set (NEW_SETS (block), newe);
3398             }
3399         }
3400     }
3401
3402   exprs.release ();
3403   return new_stuff;
3404 }
3405
3406
3407 /* Perform insertion for partially anticipatable expressions.  There
3408    is only one case we will perform insertion for these.  This case is
3409    if the expression is partially anticipatable, and fully available.
3410    In this case, we know that putting it earlier will enable us to
3411    remove the later computation.  */
3412
3413
3414 static bool
3415 do_partial_partial_insertion (basic_block block, basic_block dom)
3416 {
3417   bool new_stuff = false;
3418   vec<pre_expr> exprs;
3419   pre_expr expr;
3420   auto_vec<pre_expr> avail;
3421   int i;
3422
3423   exprs = sorted_array_from_bitmap_set (PA_IN (block));
3424   avail.safe_grow (EDGE_COUNT (block->preds));
3425
3426   FOR_EACH_VEC_ELT (exprs, i, expr)
3427     {
3428       if (expr->kind == NARY
3429           || expr->kind == REFERENCE)
3430         {
3431           unsigned int val;
3432           bool by_all = true;
3433           bool cant_insert = false;
3434           edge pred;
3435           basic_block bprime;
3436           pre_expr eprime = NULL;
3437           edge_iterator ei;
3438
3439           val = get_expr_value_id (expr);
3440           if (bitmap_set_contains_value (PHI_GEN (block), val))
3441             continue;
3442           if (bitmap_set_contains_value (AVAIL_OUT (dom), val))
3443             continue;
3444
3445           FOR_EACH_EDGE (pred, ei, block->preds)
3446             {
3447               unsigned int vprime;
3448               pre_expr edoubleprime;
3449
3450               /* We should never run insertion for the exit block
3451                  and so not come across fake pred edges.  */
3452               gcc_assert (!(pred->flags & EDGE_FAKE));
3453               bprime = pred->src;
3454               eprime = phi_translate (expr, ANTIC_IN (block),
3455                                       PA_IN (block),
3456                                       bprime, block);
3457
3458               /* eprime will generally only be NULL if the
3459                  value of the expression, translated
3460                  through the PHI for this predecessor, is
3461                  undefined.  If that is the case, we can't
3462                  make the expression fully redundant,
3463                  because its value is undefined along a
3464                  predecessor path.  We can thus break out
3465                  early because it doesn't matter what the
3466                  rest of the results are.  */
3467               if (eprime == NULL)
3468                 {
3469                   avail[pred->dest_idx] = NULL;
3470                   cant_insert = true;
3471                   break;
3472                 }
3473
3474               eprime = fully_constant_expression (eprime);
3475               vprime = get_expr_value_id (eprime);
3476               edoubleprime = bitmap_find_leader (AVAIL_OUT (bprime), vprime);
3477               avail[pred->dest_idx] = edoubleprime;
3478               if (edoubleprime == NULL)
3479                 {
3480                   by_all = false;
3481                   break;
3482                 }
3483             }
3484
3485           /* If we can insert it, it's not the same value
3486              already existing along every predecessor, and
3487              it's defined by some predecessor, it is
3488              partially redundant.  */
3489           if (!cant_insert && by_all)
3490             {
3491               edge succ;
3492               bool do_insertion = false;
3493
3494               /* Insert only if we can remove a later expression on a path
3495                  that we want to optimize for speed.
3496                  The phi node that we will be inserting in BLOCK is not free,
3497                  and inserting it for the sake of !optimize_for_speed successor
3498                  may cause regressions on the speed path.  */
3499               FOR_EACH_EDGE (succ, ei, block->succs)
3500                 {
3501                   if (bitmap_set_contains_value (PA_IN (succ->dest), val)
3502                       || bitmap_set_contains_value (ANTIC_IN (succ->dest), val))
3503                     {
3504                       if (optimize_edge_for_speed_p (succ))
3505                         do_insertion = true;
3506                     }
3507                 }
3508
3509               if (!do_insertion)
3510                 {
3511                   if (dump_file && (dump_flags & TDF_DETAILS))
3512                     {
3513                       fprintf (dump_file, "Skipping partial partial redundancy "
3514                                "for expression ");
3515                       print_pre_expr (dump_file, expr);
3516                       fprintf (dump_file, " (%04d), not (partially) anticipated "
3517                                "on any to be optimized for speed edges\n", val);
3518                     }
3519                 }
3520               else if (dbg_cnt (treepre_insert))
3521                 {
3522                   pre_stats.pa_insert++;
3523                   if (dump_file && (dump_flags & TDF_DETAILS))
3524                     {
3525                       fprintf (dump_file, "Found partial partial redundancy "
3526                                "for expression ");
3527                       print_pre_expr (dump_file, expr);
3528                       fprintf (dump_file, " (%04d)\n",
3529                                get_expr_value_id (expr));
3530                     }
3531                   if (insert_into_preds_of_block (block,
3532                                                   get_expression_id (expr),
3533                                                   avail))
3534                     new_stuff = true;
3535                 }          
3536             } 
3537         }
3538     }
3539
3540   exprs.release ();
3541   return new_stuff;
3542 }
3543
3544 static bool
3545 insert_aux (basic_block block)
3546 {
3547   basic_block son;
3548   bool new_stuff = false;
3549
3550   if (block)
3551     {
3552       basic_block dom;
3553       dom = get_immediate_dominator (CDI_DOMINATORS, block);
3554       if (dom)
3555         {
3556           unsigned i;
3557           bitmap_iterator bi;
3558           bitmap_set_t newset = NEW_SETS (dom);
3559           if (newset)
3560             {
3561               /* Note that we need to value_replace both NEW_SETS, and
3562                  AVAIL_OUT. For both the case of NEW_SETS, the value may be
3563                  represented by some non-simple expression here that we want
3564                  to replace it with.  */
3565               FOR_EACH_EXPR_ID_IN_SET (newset, i, bi)
3566                 {
3567                   pre_expr expr = expression_for_id (i);
3568                   bitmap_value_replace_in_set (NEW_SETS (block), expr);
3569                   bitmap_value_replace_in_set (AVAIL_OUT (block), expr);
3570                 }
3571             }
3572           if (!single_pred_p (block))
3573             {
3574               new_stuff |= do_regular_insertion (block, dom);
3575               if (do_partial_partial)
3576                 new_stuff |= do_partial_partial_insertion (block, dom);
3577             }
3578         }
3579     }
3580   for (son = first_dom_son (CDI_DOMINATORS, block);
3581        son;
3582        son = next_dom_son (CDI_DOMINATORS, son))
3583     {
3584       new_stuff |= insert_aux (son);
3585     }
3586
3587   return new_stuff;
3588 }
3589
3590 /* Perform insertion of partially redundant values.  */
3591
3592 static void
3593 insert (void)
3594 {
3595   bool new_stuff = true;
3596   basic_block bb;
3597   int num_iterations = 0;
3598
3599   FOR_ALL_BB_FN (bb, cfun)
3600     NEW_SETS (bb) = bitmap_set_new ();
3601
3602   while (new_stuff)
3603     {
3604       num_iterations++;
3605       if (dump_file && dump_flags & TDF_DETAILS)
3606         fprintf (dump_file, "Starting insert iteration %d\n", num_iterations);
3607       new_stuff = insert_aux (ENTRY_BLOCK_PTR_FOR_FN (cfun));
3608
3609       /* Clear the NEW sets before the next iteration.  We have already
3610          fully propagated its contents.  */
3611       if (new_stuff)
3612         FOR_ALL_BB_FN (bb, cfun)
3613           bitmap_set_free (NEW_SETS (bb));
3614     }
3615   statistics_histogram_event (cfun, "insert iterations", num_iterations);
3616 }
3617
3618
3619 /* Compute the AVAIL set for all basic blocks.
3620
3621    This function performs value numbering of the statements in each basic
3622    block.  The AVAIL sets are built from information we glean while doing
3623    this value numbering, since the AVAIL sets contain only one entry per
3624    value.
3625
3626    AVAIL_IN[BLOCK] = AVAIL_OUT[dom(BLOCK)].
3627    AVAIL_OUT[BLOCK] = AVAIL_IN[BLOCK] U PHI_GEN[BLOCK] U TMP_GEN[BLOCK].  */
3628
3629 static void
3630 compute_avail (void)
3631 {
3632
3633   basic_block block, son;
3634   basic_block *worklist;
3635   size_t sp = 0;
3636   unsigned i;
3637
3638   /* We pretend that default definitions are defined in the entry block.
3639      This includes function arguments and the static chain decl.  */
3640   for (i = 1; i < num_ssa_names; ++i)
3641     {
3642       tree name = ssa_name (i);
3643       pre_expr e;
3644       if (!name
3645           || !SSA_NAME_IS_DEFAULT_DEF (name)
3646           || has_zero_uses (name)
3647           || virtual_operand_p (name))
3648         continue;
3649
3650       e = get_or_alloc_expr_for_name (name);
3651       add_to_value (get_expr_value_id (e), e);
3652       bitmap_insert_into_set (TMP_GEN (ENTRY_BLOCK_PTR_FOR_FN (cfun)), e);
3653       bitmap_value_insert_into_set (AVAIL_OUT (ENTRY_BLOCK_PTR_FOR_FN (cfun)),
3654                                     e);
3655     }
3656
3657   if (dump_file && (dump_flags & TDF_DETAILS))
3658     {
3659       print_bitmap_set (dump_file, TMP_GEN (ENTRY_BLOCK_PTR_FOR_FN (cfun)),
3660                         "tmp_gen", ENTRY_BLOCK);
3661       print_bitmap_set (dump_file, AVAIL_OUT (ENTRY_BLOCK_PTR_FOR_FN (cfun)),
3662                         "avail_out", ENTRY_BLOCK);
3663     }
3664
3665   /* Allocate the worklist.  */
3666   worklist = XNEWVEC (basic_block, n_basic_blocks_for_fn (cfun));
3667
3668   /* Seed the algorithm by putting the dominator children of the entry
3669      block on the worklist.  */
3670   for (son = first_dom_son (CDI_DOMINATORS, ENTRY_BLOCK_PTR_FOR_FN (cfun));
3671        son;
3672        son = next_dom_son (CDI_DOMINATORS, son))
3673     worklist[sp++] = son;
3674
3675   BB_LIVE_VOP_ON_EXIT (ENTRY_BLOCK_PTR_FOR_FN (cfun))
3676     = ssa_default_def (cfun, gimple_vop (cfun));
3677
3678   /* Loop until the worklist is empty.  */
3679   while (sp)
3680     {
3681       gimple stmt;
3682       basic_block dom;
3683
3684       /* Pick a block from the worklist.  */
3685       block = worklist[--sp];
3686
3687       /* Initially, the set of available values in BLOCK is that of
3688          its immediate dominator.  */
3689       dom = get_immediate_dominator (CDI_DOMINATORS, block);
3690       if (dom)
3691         {
3692           bitmap_set_copy (AVAIL_OUT (block), AVAIL_OUT (dom));
3693           BB_LIVE_VOP_ON_EXIT (block) = BB_LIVE_VOP_ON_EXIT (dom);
3694         }
3695
3696       /* Generate values for PHI nodes.  */
3697       for (gphi_iterator gsi = gsi_start_phis (block); !gsi_end_p (gsi);
3698            gsi_next (&gsi))
3699         {
3700           tree result = gimple_phi_result (gsi.phi ());
3701
3702           /* We have no need for virtual phis, as they don't represent
3703              actual computations.  */
3704           if (virtual_operand_p (result))
3705             {
3706               BB_LIVE_VOP_ON_EXIT (block) = result;
3707               continue;
3708             }
3709
3710           pre_expr e = get_or_alloc_expr_for_name (result);
3711           add_to_value (get_expr_value_id (e), e);
3712           bitmap_value_insert_into_set (AVAIL_OUT (block), e);
3713           bitmap_insert_into_set (PHI_GEN (block), e);
3714         }
3715
3716       BB_MAY_NOTRETURN (block) = 0;
3717
3718       /* Now compute value numbers and populate value sets with all
3719          the expressions computed in BLOCK.  */
3720       for (gimple_stmt_iterator gsi = gsi_start_bb (block); !gsi_end_p (gsi);
3721            gsi_next (&gsi))
3722         {
3723           ssa_op_iter iter;
3724           tree op;
3725
3726           stmt = gsi_stmt (gsi);
3727
3728           /* Cache whether the basic-block has any non-visible side-effect
3729              or control flow.
3730              If this isn't a call or it is the last stmt in the
3731              basic-block then the CFG represents things correctly.  */
3732           if (is_gimple_call (stmt) && !stmt_ends_bb_p (stmt))
3733             {
3734               /* Non-looping const functions always return normally.
3735                  Otherwise the call might not return or have side-effects
3736                  that forbids hoisting possibly trapping expressions
3737                  before it.  */
3738               int flags = gimple_call_flags (stmt);
3739               if (!(flags & ECF_CONST)
3740                   || (flags & ECF_LOOPING_CONST_OR_PURE))
3741                 BB_MAY_NOTRETURN (block) = 1;
3742             }
3743
3744           FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_DEF)
3745             {
3746               pre_expr e = get_or_alloc_expr_for_name (op);
3747
3748               add_to_value (get_expr_value_id (e), e);
3749               bitmap_insert_into_set (TMP_GEN (block), e);
3750               bitmap_value_insert_into_set (AVAIL_OUT (block), e);
3751             }
3752
3753           if (gimple_vdef (stmt))
3754             BB_LIVE_VOP_ON_EXIT (block) = gimple_vdef (stmt);
3755
3756           if (gimple_has_side_effects (stmt)
3757               || stmt_could_throw_p (stmt)
3758               || is_gimple_debug (stmt))
3759             continue;
3760
3761           FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_USE)
3762             {
3763               if (ssa_undefined_value_p (op))
3764                 continue;
3765               pre_expr e = get_or_alloc_expr_for_name (op);
3766               bitmap_value_insert_into_set (EXP_GEN (block), e);
3767             }
3768
3769           switch (gimple_code (stmt))
3770             {
3771             case GIMPLE_RETURN:
3772               continue;
3773
3774             case GIMPLE_CALL:
3775               {
3776                 vn_reference_t ref;
3777                 vn_reference_s ref1;
3778                 pre_expr result = NULL;
3779
3780                 /* We can value number only calls to real functions.  */
3781                 if (gimple_call_internal_p (stmt))
3782                   continue;
3783
3784                 vn_reference_lookup_call (as_a <gcall *> (stmt), &ref, &ref1);
3785                 if (!ref)
3786                   continue;
3787
3788                 /* If the value of the call is not invalidated in
3789                    this block until it is computed, add the expression
3790                    to EXP_GEN.  */
3791                 if (!gimple_vuse (stmt)
3792                     || gimple_code
3793                          (SSA_NAME_DEF_STMT (gimple_vuse (stmt))) == GIMPLE_PHI
3794                     || gimple_bb (SSA_NAME_DEF_STMT
3795                                     (gimple_vuse (stmt))) != block)
3796                   {
3797                     result = (pre_expr) pool_alloc (pre_expr_pool);
3798                     result->kind = REFERENCE;
3799                     result->id = 0;
3800                     PRE_EXPR_REFERENCE (result) = ref;
3801
3802                     get_or_alloc_expression_id (result);
3803                     add_to_value (get_expr_value_id (result), result);
3804                     bitmap_value_insert_into_set (EXP_GEN (block), result);
3805                   }
3806                 continue;
3807               }
3808
3809             case GIMPLE_ASSIGN:
3810               {
3811                 pre_expr result = NULL;
3812                 switch (vn_get_stmt_kind (stmt))
3813                   {
3814                   case VN_NARY:
3815                     {
3816                       enum tree_code code = gimple_assign_rhs_code (stmt);
3817                       vn_nary_op_t nary;
3818
3819                       /* COND_EXPR and VEC_COND_EXPR are awkward in
3820                          that they contain an embedded complex expression.
3821                          Don't even try to shove those through PRE.  */
3822                       if (code == COND_EXPR
3823                           || code == VEC_COND_EXPR)
3824                         continue;
3825
3826                       vn_nary_op_lookup_stmt (stmt, &nary);
3827                       if (!nary)
3828                         continue;
3829
3830                       /* If the NARY traps and there was a preceding
3831                          point in the block that might not return avoid
3832                          adding the nary to EXP_GEN.  */
3833                       if (BB_MAY_NOTRETURN (block)
3834                           && vn_nary_may_trap (nary))
3835                         continue;
3836
3837                       result = (pre_expr) pool_alloc (pre_expr_pool);
3838                       result->kind = NARY;
3839                       result->id = 0;
3840                       PRE_EXPR_NARY (result) = nary;
3841                       break;
3842                     }
3843
3844                   case VN_REFERENCE:
3845                     {
3846                       vn_reference_t ref;
3847                       vn_reference_lookup (gimple_assign_rhs1 (stmt),
3848                                            gimple_vuse (stmt),
3849                                            VN_WALK, &ref);
3850                       if (!ref)
3851                         continue;
3852
3853                       /* If the value of the reference is not invalidated in
3854                          this block until it is computed, add the expression
3855                          to EXP_GEN.  */
3856                       if (gimple_vuse (stmt))
3857                         {
3858                           gimple def_stmt;
3859                           bool ok = true;
3860                           def_stmt = SSA_NAME_DEF_STMT (gimple_vuse (stmt));
3861                           while (!gimple_nop_p (def_stmt)
3862                                  && gimple_code (def_stmt) != GIMPLE_PHI
3863                                  && gimple_bb (def_stmt) == block)
3864                             {
3865                               if (stmt_may_clobber_ref_p
3866                                     (def_stmt, gimple_assign_rhs1 (stmt)))
3867                                 {
3868                                   ok = false;
3869                                   break;
3870                                 }
3871                               def_stmt
3872                                 = SSA_NAME_DEF_STMT (gimple_vuse (def_stmt));
3873                             }
3874                           if (!ok)
3875                             continue;
3876                         }
3877
3878                       result = (pre_expr) pool_alloc (pre_expr_pool);
3879                       result->kind = REFERENCE;
3880                       result->id = 0;
3881                       PRE_EXPR_REFERENCE (result) = ref;
3882                       break;
3883                     }
3884
3885                   default:
3886                     continue;
3887                   }
3888
3889                 get_or_alloc_expression_id (result);
3890                 add_to_value (get_expr_value_id (result), result);
3891                 bitmap_value_insert_into_set (EXP_GEN (block), result);
3892                 continue;
3893               }
3894             default:
3895               break;
3896             }
3897         }
3898
3899       if (dump_file && (dump_flags & TDF_DETAILS))
3900         {
3901           print_bitmap_set (dump_file, EXP_GEN (block),
3902                             "exp_gen", block->index);
3903           print_bitmap_set (dump_file, PHI_GEN (block),
3904                             "phi_gen", block->index);
3905           print_bitmap_set (dump_file, TMP_GEN (block),
3906                             "tmp_gen", block->index);
3907           print_bitmap_set (dump_file, AVAIL_OUT (block),
3908                             "avail_out", block->index);
3909         }
3910
3911       /* Put the dominator children of BLOCK on the worklist of blocks
3912          to compute available sets for.  */
3913       for (son = first_dom_son (CDI_DOMINATORS, block);
3914            son;
3915            son = next_dom_son (CDI_DOMINATORS, son))
3916         worklist[sp++] = son;
3917     }
3918
3919   free (worklist);
3920 }
3921
3922
3923 /* Local state for the eliminate domwalk.  */
3924 static vec<gimple> el_to_remove;
3925 static unsigned int el_todo;
3926 static vec<tree> el_avail;
3927 static vec<tree> el_avail_stack;
3928
3929 /* Return a leader for OP that is available at the current point of the
3930    eliminate domwalk.  */
3931
3932 static tree
3933 eliminate_avail (tree op)
3934 {
3935   tree valnum = VN_INFO (op)->valnum;
3936   if (TREE_CODE (valnum) == SSA_NAME)
3937     {
3938       if (SSA_NAME_IS_DEFAULT_DEF (valnum))
3939         return valnum;
3940       if (el_avail.length () > SSA_NAME_VERSION (valnum))
3941         return el_avail[SSA_NAME_VERSION (valnum)];
3942     }
3943   else if (is_gimple_min_invariant (valnum))
3944     return valnum;
3945   return NULL_TREE;
3946 }
3947
3948 /* At the current point of the eliminate domwalk make OP available.  */
3949
3950 static void
3951 eliminate_push_avail (tree op)
3952 {
3953   tree valnum = VN_INFO (op)->valnum;
3954   if (TREE_CODE (valnum) == SSA_N