OSDN Git Service

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