OSDN Git Service

2012-01-09 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, n;
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 op[3];
1540             tree type = operand->type;
1541             vn_reference_op_s newop = *operand;
1542             op[0] = operand->op0;
1543             op[1] = operand->op1;
1544             op[2] = operand->op2;
1545             for (n = 0; n < 3; ++n)
1546               {
1547                 unsigned int op_val_id;
1548                 if (!op[n])
1549                   continue;
1550                 if (TREE_CODE (op[n]) != SSA_NAME)
1551                   {
1552                     /* We can't possibly insert these.  */
1553                     if (n != 0
1554                         && !is_gimple_min_invariant (op[n]))
1555                       break;
1556                     continue;
1557                   }
1558                 op_val_id = VN_INFO (op[n])->value_id;
1559                 leader = find_leader_in_sets (op_val_id, set1, set2);
1560                 if (!leader)
1561                   break;
1562                 /* Make sure we do not recursively translate ourselves
1563                    like for translating a[n_1] with the leader for
1564                    n_1 being a[n_1].  */
1565                 if (get_expression_id (leader) != get_expression_id (expr))
1566                   {
1567                     opresult = phi_translate (leader, set1, set2,
1568                                               pred, phiblock);
1569                     if (!opresult)
1570                       break;
1571                     if (opresult != leader)
1572                       {
1573                         tree name = get_representative_for (opresult);
1574                         if (!name)
1575                           break;
1576                         changed |= name != op[n];
1577                         op[n] = name;
1578                       }
1579                   }
1580               }
1581             if (n != 3)
1582               {
1583                 if (newoperands)
1584                   VEC_free (vn_reference_op_s, heap, newoperands);
1585                 return NULL;
1586               }
1587             if (!newoperands)
1588               newoperands = VEC_copy (vn_reference_op_s, heap, operands);
1589             /* We may have changed from an SSA_NAME to a constant */
1590             if (newop.opcode == SSA_NAME && TREE_CODE (op[0]) != SSA_NAME)
1591               newop.opcode = TREE_CODE (op[0]);
1592             newop.type = type;
1593             newop.op0 = op[0];
1594             newop.op1 = op[1];
1595             newop.op2 = op[2];
1596             /* If it transforms a non-constant ARRAY_REF into a constant
1597                one, adjust the constant offset.  */
1598             if (newop.opcode == ARRAY_REF
1599                 && newop.off == -1
1600                 && TREE_CODE (op[0]) == INTEGER_CST
1601                 && TREE_CODE (op[1]) == INTEGER_CST
1602                 && TREE_CODE (op[2]) == INTEGER_CST)
1603               {
1604                 double_int off = tree_to_double_int (op[0]);
1605                 off = double_int_add (off,
1606                                       double_int_neg
1607                                         (tree_to_double_int (op[1])));
1608                 off = double_int_mul (off, tree_to_double_int (op[2]));
1609                 if (double_int_fits_in_shwi_p (off))
1610                   newop.off = off.low;
1611               }
1612             VEC_replace (vn_reference_op_s, newoperands, j, &newop);
1613             /* If it transforms from an SSA_NAME to an address, fold with
1614                a preceding indirect reference.  */
1615             if (j > 0 && op[0] && TREE_CODE (op[0]) == ADDR_EXPR
1616                 && VEC_index (vn_reference_op_s,
1617                               newoperands, j - 1)->opcode == MEM_REF)
1618               vn_reference_fold_indirect (&newoperands, &j);
1619           }
1620         if (i != VEC_length (vn_reference_op_s, operands))
1621           {
1622             if (newoperands)
1623               VEC_free (vn_reference_op_s, heap, newoperands);
1624             return NULL;
1625           }
1626
1627         if (vuse)
1628           {
1629             newvuse = translate_vuse_through_block (newoperands,
1630                                                     ref->set, ref->type,
1631                                                     vuse, phiblock, pred,
1632                                                     &same_valid);
1633             if (newvuse == NULL_TREE)
1634               {
1635                 VEC_free (vn_reference_op_s, heap, newoperands);
1636                 return NULL;
1637               }
1638           }
1639
1640         if (changed || newvuse != vuse)
1641           {
1642             unsigned int new_val_id;
1643             pre_expr constant;
1644             bool converted = false;
1645
1646             tree result = vn_reference_lookup_pieces (newvuse, ref->set,
1647                                                       ref->type,
1648                                                       newoperands,
1649                                                       &newref, VN_WALK);
1650             if (result)
1651               VEC_free (vn_reference_op_s, heap, newoperands);
1652
1653             if (result
1654                 && !useless_type_conversion_p (ref->type, TREE_TYPE (result)))
1655               {
1656                 result = fold_build1 (VIEW_CONVERT_EXPR, ref->type, result);
1657                 converted = true;
1658               }
1659             else if (!result && newref
1660                      && !useless_type_conversion_p (ref->type, newref->type))
1661               {
1662                 VEC_free (vn_reference_op_s, heap, newoperands);
1663                 return NULL;
1664               }
1665
1666             if (result && is_gimple_min_invariant (result))
1667               {
1668                 gcc_assert (!newoperands);
1669                 return get_or_alloc_expr_for_constant (result);
1670               }
1671
1672             expr = (pre_expr) pool_alloc (pre_expr_pool);
1673             expr->kind = REFERENCE;
1674             expr->id = 0;
1675
1676             if (converted)
1677               {
1678                 vn_nary_op_t nary;
1679                 tree nresult;
1680
1681                 gcc_assert (CONVERT_EXPR_P (result)
1682                             || TREE_CODE (result) == VIEW_CONVERT_EXPR);
1683
1684                 nresult = vn_nary_op_lookup_pieces (1, TREE_CODE (result),
1685                                                     TREE_TYPE (result),
1686                                                     &TREE_OPERAND (result, 0),
1687                                                     &nary);
1688                 if (nresult && is_gimple_min_invariant (nresult))
1689                   return get_or_alloc_expr_for_constant (nresult);
1690
1691                 expr->kind = NARY;
1692                 if (nary)
1693                   {
1694                     PRE_EXPR_NARY (expr) = nary;
1695                     constant = fully_constant_expression (expr);
1696                     if (constant != expr)
1697                       return constant;
1698
1699                     new_val_id = nary->value_id;
1700                     get_or_alloc_expression_id (expr);
1701                   }
1702                 else
1703                   {
1704                     new_val_id = get_next_value_id ();
1705                     VEC_safe_grow_cleared (bitmap_set_t, heap,
1706                                            value_expressions,
1707                                            get_max_value_id() + 1);
1708                     nary = vn_nary_op_insert_pieces (1, TREE_CODE (result),
1709                                                      TREE_TYPE (result),
1710                                                      &TREE_OPERAND (result, 0),
1711                                                      NULL_TREE,
1712                                                      new_val_id);
1713                     PRE_EXPR_NARY (expr) = nary;
1714                     constant = fully_constant_expression (expr);
1715                     if (constant != expr)
1716                       return constant;
1717                     get_or_alloc_expression_id (expr);
1718                   }
1719               }
1720             else if (newref)
1721               {
1722                 PRE_EXPR_REFERENCE (expr) = newref;
1723                 constant = fully_constant_expression (expr);
1724                 if (constant != expr)
1725                   return constant;
1726
1727                 new_val_id = newref->value_id;
1728                 get_or_alloc_expression_id (expr);
1729               }
1730             else
1731               {
1732                 if (changed || !same_valid)
1733                   {
1734                     new_val_id = get_next_value_id ();
1735                     VEC_safe_grow_cleared (bitmap_set_t, heap,
1736                                            value_expressions,
1737                                            get_max_value_id() + 1);
1738                   }
1739                 else
1740                   new_val_id = ref->value_id;
1741                 newref = vn_reference_insert_pieces (newvuse, ref->set,
1742                                                      ref->type,
1743                                                      newoperands,
1744                                                      result, new_val_id);
1745                 newoperands = NULL;
1746                 PRE_EXPR_REFERENCE (expr) = newref;
1747                 constant = fully_constant_expression (expr);
1748                 if (constant != expr)
1749                   return constant;
1750                 get_or_alloc_expression_id (expr);
1751               }
1752             add_to_value (new_val_id, expr);
1753           }
1754         VEC_free (vn_reference_op_s, heap, newoperands);
1755         return expr;
1756       }
1757       break;
1758
1759     case NAME:
1760       {
1761         gimple phi = NULL;
1762         edge e;
1763         gimple def_stmt;
1764         tree name = PRE_EXPR_NAME (expr);
1765
1766         def_stmt = SSA_NAME_DEF_STMT (name);
1767         if (gimple_code (def_stmt) == GIMPLE_PHI
1768             && gimple_bb (def_stmt) == phiblock)
1769           phi = def_stmt;
1770         else
1771           return expr;
1772
1773         e = find_edge (pred, gimple_bb (phi));
1774         if (e)
1775           {
1776             tree def = PHI_ARG_DEF (phi, e->dest_idx);
1777             pre_expr newexpr;
1778
1779             if (TREE_CODE (def) == SSA_NAME)
1780               def = VN_INFO (def)->valnum;
1781
1782             /* Handle constant. */
1783             if (is_gimple_min_invariant (def))
1784               return get_or_alloc_expr_for_constant (def);
1785
1786             if (TREE_CODE (def) == SSA_NAME && ssa_undefined_value_p (def))
1787               return NULL;
1788
1789             newexpr = get_or_alloc_expr_for_name (def);
1790             return newexpr;
1791           }
1792       }
1793       return expr;
1794
1795     default:
1796       gcc_unreachable ();
1797     }
1798 }
1799
1800 /* Wrapper around phi_translate_1 providing caching functionality.  */
1801
1802 static pre_expr
1803 phi_translate (pre_expr expr, bitmap_set_t set1, bitmap_set_t set2,
1804                basic_block pred, basic_block phiblock)
1805 {
1806   pre_expr phitrans;
1807
1808   if (!expr)
1809     return NULL;
1810
1811   /* Constants contain no values that need translation.  */
1812   if (expr->kind == CONSTANT)
1813     return expr;
1814
1815   if (value_id_constant_p (get_expr_value_id (expr)))
1816     return expr;
1817
1818   if (expr->kind != NAME)
1819     {
1820       phitrans = phi_trans_lookup (expr, pred);
1821       if (phitrans)
1822         return phitrans;
1823     }
1824
1825   /* Translate.  */
1826   phitrans = phi_translate_1 (expr, set1, set2, pred, phiblock);
1827
1828   /* Don't add empty translations to the cache.  Neither add
1829      translations of NAMEs as those are cheap to translate.  */
1830   if (phitrans
1831       && expr->kind != NAME)
1832     phi_trans_add (expr, phitrans, pred);
1833
1834   return phitrans;
1835 }
1836
1837
1838 /* For each expression in SET, translate the values through phi nodes
1839    in PHIBLOCK using edge PHIBLOCK->PRED, and store the resulting
1840    expressions in DEST.  */
1841
1842 static void
1843 phi_translate_set (bitmap_set_t dest, bitmap_set_t set, basic_block pred,
1844                    basic_block phiblock)
1845 {
1846   VEC (pre_expr, heap) *exprs;
1847   pre_expr expr;
1848   int i;
1849
1850   if (gimple_seq_empty_p (phi_nodes (phiblock)))
1851     {
1852       bitmap_set_copy (dest, set);
1853       return;
1854     }
1855
1856   exprs = sorted_array_from_bitmap_set (set);
1857   FOR_EACH_VEC_ELT (pre_expr, exprs, i, expr)
1858     {
1859       pre_expr translated;
1860       translated = phi_translate (expr, set, NULL, pred, phiblock);
1861       if (!translated)
1862         continue;
1863
1864       /* We might end up with multiple expressions from SET being
1865          translated to the same value.  In this case we do not want
1866          to retain the NARY or REFERENCE expression but prefer a NAME
1867          which would be the leader.  */
1868       if (translated->kind == NAME)
1869         bitmap_value_replace_in_set (dest, translated);
1870       else
1871         bitmap_value_insert_into_set (dest, translated);
1872     }
1873   VEC_free (pre_expr, heap, exprs);
1874 }
1875
1876 /* Find the leader for a value (i.e., the name representing that
1877    value) in a given set, and return it.  If STMT is non-NULL it
1878    makes sure the defining statement for the leader dominates it.
1879    Return NULL if no leader is found.  */
1880
1881 static pre_expr
1882 bitmap_find_leader (bitmap_set_t set, unsigned int val, gimple stmt)
1883 {
1884   if (value_id_constant_p (val))
1885     {
1886       unsigned int i;
1887       bitmap_iterator bi;
1888       bitmap_set_t exprset = VEC_index (bitmap_set_t, value_expressions, val);
1889
1890       FOR_EACH_EXPR_ID_IN_SET (exprset, i, bi)
1891         {
1892           pre_expr expr = expression_for_id (i);
1893           if (expr->kind == CONSTANT)
1894             return expr;
1895         }
1896     }
1897   if (bitmap_set_contains_value (set, val))
1898     {
1899       /* Rather than walk the entire bitmap of expressions, and see
1900          whether any of them has the value we are looking for, we look
1901          at the reverse mapping, which tells us the set of expressions
1902          that have a given value (IE value->expressions with that
1903          value) and see if any of those expressions are in our set.
1904          The number of expressions per value is usually significantly
1905          less than the number of expressions in the set.  In fact, for
1906          large testcases, doing it this way is roughly 5-10x faster
1907          than walking the bitmap.
1908          If this is somehow a significant lose for some cases, we can
1909          choose which set to walk based on which set is smaller.  */
1910       unsigned int i;
1911       bitmap_iterator bi;
1912       bitmap_set_t exprset = VEC_index (bitmap_set_t, value_expressions, val);
1913
1914       EXECUTE_IF_AND_IN_BITMAP (&exprset->expressions,
1915                                 &set->expressions, 0, i, bi)
1916         {
1917           pre_expr val = expression_for_id (i);
1918           /* At the point where stmt is not null, there should always
1919              be an SSA_NAME first in the list of expressions.  */
1920           if (stmt)
1921             {
1922               gimple def_stmt = SSA_NAME_DEF_STMT (PRE_EXPR_NAME (val));
1923               if (gimple_code (def_stmt) != GIMPLE_PHI
1924                   && gimple_bb (def_stmt) == gimple_bb (stmt)
1925                   /* PRE insertions are at the end of the basic-block
1926                      and have UID 0.  */
1927                   && (gimple_uid (def_stmt) == 0
1928                       || gimple_uid (def_stmt) >= gimple_uid (stmt)))
1929                 continue;
1930             }
1931           return val;
1932         }
1933     }
1934   return NULL;
1935 }
1936
1937 /* Determine if EXPR, a memory expression, is ANTIC_IN at the top of
1938    BLOCK by seeing if it is not killed in the block.  Note that we are
1939    only determining whether there is a store that kills it.  Because
1940    of the order in which clean iterates over values, we are guaranteed
1941    that altered operands will have caused us to be eliminated from the
1942    ANTIC_IN set already.  */
1943
1944 static bool
1945 value_dies_in_block_x (pre_expr expr, basic_block block)
1946 {
1947   tree vuse = PRE_EXPR_REFERENCE (expr)->vuse;
1948   vn_reference_t refx = PRE_EXPR_REFERENCE (expr);
1949   gimple def;
1950   gimple_stmt_iterator gsi;
1951   unsigned id = get_expression_id (expr);
1952   bool res = false;
1953   ao_ref ref;
1954
1955   if (!vuse)
1956     return false;
1957
1958   /* Lookup a previously calculated result.  */
1959   if (EXPR_DIES (block)
1960       && bitmap_bit_p (EXPR_DIES (block), id * 2))
1961     return bitmap_bit_p (EXPR_DIES (block), id * 2 + 1);
1962
1963   /* A memory expression {e, VUSE} dies in the block if there is a
1964      statement that may clobber e.  If, starting statement walk from the
1965      top of the basic block, a statement uses VUSE there can be no kill
1966      inbetween that use and the original statement that loaded {e, VUSE},
1967      so we can stop walking.  */
1968   ref.base = NULL_TREE;
1969   for (gsi = gsi_start_bb (block); !gsi_end_p (gsi); gsi_next (&gsi))
1970     {
1971       tree def_vuse, def_vdef;
1972       def = gsi_stmt (gsi);
1973       def_vuse = gimple_vuse (def);
1974       def_vdef = gimple_vdef (def);
1975
1976       /* Not a memory statement.  */
1977       if (!def_vuse)
1978         continue;
1979
1980       /* Not a may-def.  */
1981       if (!def_vdef)
1982         {
1983           /* A load with the same VUSE, we're done.  */
1984           if (def_vuse == vuse)
1985             break;
1986
1987           continue;
1988         }
1989
1990       /* Init ref only if we really need it.  */
1991       if (ref.base == NULL_TREE
1992           && !ao_ref_init_from_vn_reference (&ref, refx->set, refx->type,
1993                                              refx->operands))
1994         {
1995           res = true;
1996           break;
1997         }
1998       /* If the statement may clobber expr, it dies.  */
1999       if (stmt_may_clobber_ref_p_1 (def, &ref))
2000         {
2001           res = true;
2002           break;
2003         }
2004     }
2005
2006   /* Remember the result.  */
2007   if (!EXPR_DIES (block))
2008     EXPR_DIES (block) = BITMAP_ALLOC (&grand_bitmap_obstack);
2009   bitmap_set_bit (EXPR_DIES (block), id * 2);
2010   if (res)
2011     bitmap_set_bit (EXPR_DIES (block), id * 2 + 1);
2012
2013   return res;
2014 }
2015
2016
2017 #define union_contains_value(SET1, SET2, VAL)                   \
2018   (bitmap_set_contains_value ((SET1), (VAL))                    \
2019    || ((SET2) && bitmap_set_contains_value ((SET2), (VAL))))
2020
2021 /* Determine if vn_reference_op_t VRO is legal in SET1 U SET2.
2022  */
2023 static bool
2024 vro_valid_in_sets (bitmap_set_t set1, bitmap_set_t set2,
2025                    vn_reference_op_t vro)
2026 {
2027   if (vro->op0 && TREE_CODE (vro->op0) == SSA_NAME)
2028     {
2029       struct pre_expr_d temp;
2030       temp.kind = NAME;
2031       temp.id = 0;
2032       PRE_EXPR_NAME (&temp) = vro->op0;
2033       temp.id = lookup_expression_id (&temp);
2034       if (temp.id == 0)
2035         return false;
2036       if (!union_contains_value (set1, set2,
2037                                  get_expr_value_id (&temp)))
2038         return false;
2039     }
2040   if (vro->op1 && TREE_CODE (vro->op1) == SSA_NAME)
2041     {
2042       struct pre_expr_d temp;
2043       temp.kind = NAME;
2044       temp.id = 0;
2045       PRE_EXPR_NAME (&temp) = vro->op1;
2046       temp.id = lookup_expression_id (&temp);
2047       if (temp.id == 0)
2048         return false;
2049       if (!union_contains_value (set1, set2,
2050                                  get_expr_value_id (&temp)))
2051         return false;
2052     }
2053
2054   if (vro->op2 && TREE_CODE (vro->op2) == SSA_NAME)
2055     {
2056       struct pre_expr_d temp;
2057       temp.kind = NAME;
2058       temp.id = 0;
2059       PRE_EXPR_NAME (&temp) = vro->op2;
2060       temp.id = lookup_expression_id (&temp);
2061       if (temp.id == 0)
2062         return false;
2063       if (!union_contains_value (set1, set2,
2064                                  get_expr_value_id (&temp)))
2065         return false;
2066     }
2067
2068   return true;
2069 }
2070
2071 /* Determine if the expression EXPR is valid in SET1 U SET2.
2072    ONLY SET2 CAN BE NULL.
2073    This means that we have a leader for each part of the expression
2074    (if it consists of values), or the expression is an SSA_NAME.
2075    For loads/calls, we also see if the vuse is killed in this block.  */
2076
2077 static bool
2078 valid_in_sets (bitmap_set_t set1, bitmap_set_t set2, pre_expr expr,
2079                basic_block block)
2080 {
2081   switch (expr->kind)
2082     {
2083     case NAME:
2084       return bitmap_set_contains_expr (AVAIL_OUT (block), expr);
2085     case NARY:
2086       {
2087         unsigned int i;
2088         vn_nary_op_t nary = PRE_EXPR_NARY (expr);
2089         for (i = 0; i < nary->length; i++)
2090           {
2091             if (TREE_CODE (nary->op[i]) == SSA_NAME)
2092               {
2093                 struct pre_expr_d temp;
2094                 temp.kind = NAME;
2095                 temp.id = 0;
2096                 PRE_EXPR_NAME (&temp) = nary->op[i];
2097                 temp.id = lookup_expression_id (&temp);
2098                 if (temp.id == 0)
2099                   return false;
2100                 if (!union_contains_value (set1, set2,
2101                                            get_expr_value_id (&temp)))
2102                   return false;
2103               }
2104           }
2105         /* If the NARY may trap make sure the block does not contain
2106            a possible exit point.
2107            ???  This is overly conservative if we translate AVAIL_OUT
2108            as the available expression might be after the exit point.  */
2109         if (BB_MAY_NOTRETURN (block)
2110             && vn_nary_may_trap (nary))
2111           return false;
2112         return true;
2113       }
2114       break;
2115     case REFERENCE:
2116       {
2117         vn_reference_t ref = PRE_EXPR_REFERENCE (expr);
2118         vn_reference_op_t vro;
2119         unsigned int i;
2120
2121         FOR_EACH_VEC_ELT (vn_reference_op_s, ref->operands, i, vro)
2122           {
2123             if (!vro_valid_in_sets (set1, set2, vro))
2124               return false;
2125           }
2126         if (ref->vuse)
2127           {
2128             gimple def_stmt = SSA_NAME_DEF_STMT (ref->vuse);
2129             if (!gimple_nop_p (def_stmt)
2130                 && gimple_bb (def_stmt) != block
2131                 && !dominated_by_p (CDI_DOMINATORS,
2132                                     block, gimple_bb (def_stmt)))
2133               return false;
2134           }
2135         return !value_dies_in_block_x (expr, block);
2136       }
2137     default:
2138       gcc_unreachable ();
2139     }
2140 }
2141
2142 /* Clean the set of expressions that are no longer valid in SET1 or
2143    SET2.  This means expressions that are made up of values we have no
2144    leaders for in SET1 or SET2.  This version is used for partial
2145    anticipation, which means it is not valid in either ANTIC_IN or
2146    PA_IN.  */
2147
2148 static void
2149 dependent_clean (bitmap_set_t set1, bitmap_set_t set2, basic_block block)
2150 {
2151   VEC (pre_expr, heap) *exprs = sorted_array_from_bitmap_set (set1);
2152   pre_expr expr;
2153   int i;
2154
2155   FOR_EACH_VEC_ELT (pre_expr, exprs, i, expr)
2156     {
2157       if (!valid_in_sets (set1, set2, expr, block))
2158         bitmap_remove_from_set (set1, expr);
2159     }
2160   VEC_free (pre_expr, heap, exprs);
2161 }
2162
2163 /* Clean the set of expressions that are no longer valid in SET.  This
2164    means expressions that are made up of values we have no leaders for
2165    in SET.  */
2166
2167 static void
2168 clean (bitmap_set_t set, basic_block block)
2169 {
2170   VEC (pre_expr, heap) *exprs = sorted_array_from_bitmap_set (set);
2171   pre_expr expr;
2172   int i;
2173
2174   FOR_EACH_VEC_ELT (pre_expr, exprs, i, expr)
2175     {
2176       if (!valid_in_sets (set, NULL, expr, block))
2177         bitmap_remove_from_set (set, expr);
2178     }
2179   VEC_free (pre_expr, heap, exprs);
2180 }
2181
2182 static sbitmap has_abnormal_preds;
2183
2184 /* List of blocks that may have changed during ANTIC computation and
2185    thus need to be iterated over.  */
2186
2187 static sbitmap changed_blocks;
2188
2189 /* Decide whether to defer a block for a later iteration, or PHI
2190    translate SOURCE to DEST using phis in PHIBLOCK.  Return false if we
2191    should defer the block, and true if we processed it.  */
2192
2193 static bool
2194 defer_or_phi_translate_block (bitmap_set_t dest, bitmap_set_t source,
2195                               basic_block block, basic_block phiblock)
2196 {
2197   if (!BB_VISITED (phiblock))
2198     {
2199       SET_BIT (changed_blocks, block->index);
2200       BB_VISITED (block) = 0;
2201       BB_DEFERRED (block) = 1;
2202       return false;
2203     }
2204   else
2205     phi_translate_set (dest, source, block, phiblock);
2206   return true;
2207 }
2208
2209 /* Compute the ANTIC set for BLOCK.
2210
2211    If succs(BLOCK) > 1 then
2212      ANTIC_OUT[BLOCK] = intersection of ANTIC_IN[b] for all succ(BLOCK)
2213    else if succs(BLOCK) == 1 then
2214      ANTIC_OUT[BLOCK] = phi_translate (ANTIC_IN[succ(BLOCK)])
2215
2216    ANTIC_IN[BLOCK] = clean(ANTIC_OUT[BLOCK] U EXP_GEN[BLOCK] - TMP_GEN[BLOCK])
2217 */
2218
2219 static bool
2220 compute_antic_aux (basic_block block, bool block_has_abnormal_pred_edge)
2221 {
2222   bool changed = false;
2223   bitmap_set_t S, old, ANTIC_OUT;
2224   bitmap_iterator bi;
2225   unsigned int bii;
2226   edge e;
2227   edge_iterator ei;
2228
2229   old = ANTIC_OUT = S = NULL;
2230   BB_VISITED (block) = 1;
2231
2232   /* If any edges from predecessors are abnormal, antic_in is empty,
2233      so do nothing.  */
2234   if (block_has_abnormal_pred_edge)
2235     goto maybe_dump_sets;
2236
2237   old = ANTIC_IN (block);
2238   ANTIC_OUT = bitmap_set_new ();
2239
2240   /* If the block has no successors, ANTIC_OUT is empty.  */
2241   if (EDGE_COUNT (block->succs) == 0)
2242     ;
2243   /* If we have one successor, we could have some phi nodes to
2244      translate through.  */
2245   else if (single_succ_p (block))
2246     {
2247       basic_block succ_bb = single_succ (block);
2248
2249       /* We trade iterations of the dataflow equations for having to
2250          phi translate the maximal set, which is incredibly slow
2251          (since the maximal set often has 300+ members, even when you
2252          have a small number of blocks).
2253          Basically, we defer the computation of ANTIC for this block
2254          until we have processed it's successor, which will inevitably
2255          have a *much* smaller set of values to phi translate once
2256          clean has been run on it.
2257          The cost of doing this is that we technically perform more
2258          iterations, however, they are lower cost iterations.
2259
2260          Timings for PRE on tramp3d-v4:
2261          without maximal set fix: 11 seconds
2262          with maximal set fix/without deferring: 26 seconds
2263          with maximal set fix/with deferring: 11 seconds
2264      */
2265
2266       if (!defer_or_phi_translate_block (ANTIC_OUT, ANTIC_IN (succ_bb),
2267                                         block, succ_bb))
2268         {
2269           changed = true;
2270           goto maybe_dump_sets;
2271         }
2272     }
2273   /* If we have multiple successors, we take the intersection of all of
2274      them.  Note that in the case of loop exit phi nodes, we may have
2275      phis to translate through.  */
2276   else
2277     {
2278       VEC(basic_block, heap) * worklist;
2279       size_t i;
2280       basic_block bprime, first = NULL;
2281
2282       worklist = VEC_alloc (basic_block, heap, EDGE_COUNT (block->succs));
2283       FOR_EACH_EDGE (e, ei, block->succs)
2284         {
2285           if (!first
2286               && BB_VISITED (e->dest))
2287             first = e->dest;
2288           else if (BB_VISITED (e->dest))
2289             VEC_quick_push (basic_block, worklist, e->dest);
2290         }
2291
2292       /* Of multiple successors we have to have visited one already.  */
2293       if (!first)
2294         {
2295           SET_BIT (changed_blocks, block->index);
2296           BB_VISITED (block) = 0;
2297           BB_DEFERRED (block) = 1;
2298           changed = true;
2299           VEC_free (basic_block, heap, worklist);
2300           goto maybe_dump_sets;
2301         }
2302
2303       if (!gimple_seq_empty_p (phi_nodes (first)))
2304         phi_translate_set (ANTIC_OUT, ANTIC_IN (first), block, first);
2305       else
2306         bitmap_set_copy (ANTIC_OUT, ANTIC_IN (first));
2307
2308       FOR_EACH_VEC_ELT (basic_block, worklist, i, bprime)
2309         {
2310           if (!gimple_seq_empty_p (phi_nodes (bprime)))
2311             {
2312               bitmap_set_t tmp = bitmap_set_new ();
2313               phi_translate_set (tmp, ANTIC_IN (bprime), block, bprime);
2314               bitmap_set_and (ANTIC_OUT, tmp);
2315               bitmap_set_free (tmp);
2316             }
2317           else
2318             bitmap_set_and (ANTIC_OUT, ANTIC_IN (bprime));
2319         }
2320       VEC_free (basic_block, heap, worklist);
2321     }
2322
2323   /* Generate ANTIC_OUT - TMP_GEN.  */
2324   S = bitmap_set_subtract (ANTIC_OUT, TMP_GEN (block));
2325
2326   /* Start ANTIC_IN with EXP_GEN - TMP_GEN.  */
2327   ANTIC_IN (block) = bitmap_set_subtract (EXP_GEN (block),
2328                                           TMP_GEN (block));
2329
2330   /* Then union in the ANTIC_OUT - TMP_GEN values,
2331      to get ANTIC_OUT U EXP_GEN - TMP_GEN */
2332   FOR_EACH_EXPR_ID_IN_SET (S, bii, bi)
2333     bitmap_value_insert_into_set (ANTIC_IN (block),
2334                                   expression_for_id (bii));
2335
2336   clean (ANTIC_IN (block), block);
2337
2338   if (!bitmap_set_equal (old, ANTIC_IN (block)))
2339     {
2340       changed = true;
2341       SET_BIT (changed_blocks, block->index);
2342       FOR_EACH_EDGE (e, ei, block->preds)
2343         SET_BIT (changed_blocks, e->src->index);
2344     }
2345   else
2346     RESET_BIT (changed_blocks, block->index);
2347
2348  maybe_dump_sets:
2349   if (dump_file && (dump_flags & TDF_DETAILS))
2350     {
2351       if (!BB_DEFERRED (block) || BB_VISITED (block))
2352         {
2353           if (ANTIC_OUT)
2354             print_bitmap_set (dump_file, ANTIC_OUT, "ANTIC_OUT", block->index);
2355
2356           print_bitmap_set (dump_file, ANTIC_IN (block), "ANTIC_IN",
2357                             block->index);
2358
2359           if (S)
2360             print_bitmap_set (dump_file, S, "S", block->index);
2361         }
2362       else
2363         {
2364           fprintf (dump_file,
2365                    "Block %d was deferred for a future iteration.\n",
2366                    block->index);
2367         }
2368     }
2369   if (old)
2370     bitmap_set_free (old);
2371   if (S)
2372     bitmap_set_free (S);
2373   if (ANTIC_OUT)
2374     bitmap_set_free (ANTIC_OUT);
2375   return changed;
2376 }
2377
2378 /* Compute PARTIAL_ANTIC for BLOCK.
2379
2380    If succs(BLOCK) > 1 then
2381      PA_OUT[BLOCK] = value wise union of PA_IN[b] + all ANTIC_IN not
2382      in ANTIC_OUT for all succ(BLOCK)
2383    else if succs(BLOCK) == 1 then
2384      PA_OUT[BLOCK] = phi_translate (PA_IN[succ(BLOCK)])
2385
2386    PA_IN[BLOCK] = dependent_clean(PA_OUT[BLOCK] - TMP_GEN[BLOCK]
2387                                   - ANTIC_IN[BLOCK])
2388
2389 */
2390 static bool
2391 compute_partial_antic_aux (basic_block block,
2392                            bool block_has_abnormal_pred_edge)
2393 {
2394   bool changed = false;
2395   bitmap_set_t old_PA_IN;
2396   bitmap_set_t PA_OUT;
2397   edge e;
2398   edge_iterator ei;
2399   unsigned long max_pa = PARAM_VALUE (PARAM_MAX_PARTIAL_ANTIC_LENGTH);
2400
2401   old_PA_IN = PA_OUT = NULL;
2402
2403   /* If any edges from predecessors are abnormal, antic_in is empty,
2404      so do nothing.  */
2405   if (block_has_abnormal_pred_edge)
2406     goto maybe_dump_sets;
2407
2408   /* If there are too many partially anticipatable values in the
2409      block, phi_translate_set can take an exponential time: stop
2410      before the translation starts.  */
2411   if (max_pa
2412       && single_succ_p (block)
2413       && bitmap_count_bits (&PA_IN (single_succ (block))->values) > max_pa)
2414     goto maybe_dump_sets;
2415
2416   old_PA_IN = PA_IN (block);
2417   PA_OUT = bitmap_set_new ();
2418
2419   /* If the block has no successors, ANTIC_OUT is empty.  */
2420   if (EDGE_COUNT (block->succs) == 0)
2421     ;
2422   /* If we have one successor, we could have some phi nodes to
2423      translate through.  Note that we can't phi translate across DFS
2424      back edges in partial antic, because it uses a union operation on
2425      the successors.  For recurrences like IV's, we will end up
2426      generating a new value in the set on each go around (i + 3 (VH.1)
2427      VH.1 + 1 (VH.2), VH.2 + 1 (VH.3), etc), forever.  */
2428   else if (single_succ_p (block))
2429     {
2430       basic_block succ = single_succ (block);
2431       if (!(single_succ_edge (block)->flags & EDGE_DFS_BACK))
2432         phi_translate_set (PA_OUT, PA_IN (succ), block, succ);
2433     }
2434   /* If we have multiple successors, we take the union of all of
2435      them.  */
2436   else
2437     {
2438       VEC(basic_block, heap) * worklist;
2439       size_t i;
2440       basic_block bprime;
2441
2442       worklist = VEC_alloc (basic_block, heap, EDGE_COUNT (block->succs));
2443       FOR_EACH_EDGE (e, ei, block->succs)
2444         {
2445           if (e->flags & EDGE_DFS_BACK)
2446             continue;
2447           VEC_quick_push (basic_block, worklist, e->dest);
2448         }
2449       if (VEC_length (basic_block, worklist) > 0)
2450         {
2451           FOR_EACH_VEC_ELT (basic_block, worklist, i, bprime)
2452             {
2453               unsigned int i;
2454               bitmap_iterator bi;
2455
2456               FOR_EACH_EXPR_ID_IN_SET (ANTIC_IN (bprime), i, bi)
2457                 bitmap_value_insert_into_set (PA_OUT,
2458                                               expression_for_id (i));
2459               if (!gimple_seq_empty_p (phi_nodes (bprime)))
2460                 {
2461                   bitmap_set_t pa_in = bitmap_set_new ();
2462                   phi_translate_set (pa_in, PA_IN (bprime), block, bprime);
2463                   FOR_EACH_EXPR_ID_IN_SET (pa_in, i, bi)
2464                     bitmap_value_insert_into_set (PA_OUT,
2465                                                   expression_for_id (i));
2466                   bitmap_set_free (pa_in);
2467                 }
2468               else
2469                 FOR_EACH_EXPR_ID_IN_SET (PA_IN (bprime), i, bi)
2470                   bitmap_value_insert_into_set (PA_OUT,
2471                                                 expression_for_id (i));
2472             }
2473         }
2474       VEC_free (basic_block, heap, worklist);
2475     }
2476
2477   /* PA_IN starts with PA_OUT - TMP_GEN.
2478      Then we subtract things from ANTIC_IN.  */
2479   PA_IN (block) = bitmap_set_subtract (PA_OUT, TMP_GEN (block));
2480
2481   /* For partial antic, we want to put back in the phi results, since
2482      we will properly avoid making them partially antic over backedges.  */
2483   bitmap_ior_into (&PA_IN (block)->values, &PHI_GEN (block)->values);
2484   bitmap_ior_into (&PA_IN (block)->expressions, &PHI_GEN (block)->expressions);
2485
2486   /* PA_IN[block] = PA_IN[block] - ANTIC_IN[block] */
2487   bitmap_set_subtract_values (PA_IN (block), ANTIC_IN (block));
2488
2489   dependent_clean (PA_IN (block), ANTIC_IN (block), block);
2490
2491   if (!bitmap_set_equal (old_PA_IN, PA_IN (block)))
2492     {
2493       changed = true;
2494       SET_BIT (changed_blocks, block->index);
2495       FOR_EACH_EDGE (e, ei, block->preds)
2496         SET_BIT (changed_blocks, e->src->index);
2497     }
2498   else
2499     RESET_BIT (changed_blocks, block->index);
2500
2501  maybe_dump_sets:
2502   if (dump_file && (dump_flags & TDF_DETAILS))
2503     {
2504       if (PA_OUT)
2505         print_bitmap_set (dump_file, PA_OUT, "PA_OUT", block->index);
2506
2507       print_bitmap_set (dump_file, PA_IN (block), "PA_IN", block->index);
2508     }
2509   if (old_PA_IN)
2510     bitmap_set_free (old_PA_IN);
2511   if (PA_OUT)
2512     bitmap_set_free (PA_OUT);
2513   return changed;
2514 }
2515
2516 /* Compute ANTIC and partial ANTIC sets.  */
2517
2518 static void
2519 compute_antic (void)
2520 {
2521   bool changed = true;
2522   int num_iterations = 0;
2523   basic_block block;
2524   int i;
2525
2526   /* If any predecessor edges are abnormal, we punt, so antic_in is empty.
2527      We pre-build the map of blocks with incoming abnormal edges here.  */
2528   has_abnormal_preds = sbitmap_alloc (last_basic_block);
2529   sbitmap_zero (has_abnormal_preds);
2530
2531   FOR_EACH_BB (block)
2532     {
2533       edge_iterator ei;
2534       edge e;
2535
2536       FOR_EACH_EDGE (e, ei, block->preds)
2537         {
2538           e->flags &= ~EDGE_DFS_BACK;
2539           if (e->flags & EDGE_ABNORMAL)
2540             {
2541               SET_BIT (has_abnormal_preds, block->index);
2542               break;
2543             }
2544         }
2545
2546       BB_VISITED (block) = 0;
2547       BB_DEFERRED (block) = 0;
2548
2549       /* While we are here, give empty ANTIC_IN sets to each block.  */
2550       ANTIC_IN (block) = bitmap_set_new ();
2551       PA_IN (block) = bitmap_set_new ();
2552     }
2553
2554   /* At the exit block we anticipate nothing.  */
2555   ANTIC_IN (EXIT_BLOCK_PTR) = bitmap_set_new ();
2556   BB_VISITED (EXIT_BLOCK_PTR) = 1;
2557   PA_IN (EXIT_BLOCK_PTR) = bitmap_set_new ();
2558
2559   changed_blocks = sbitmap_alloc (last_basic_block + 1);
2560   sbitmap_ones (changed_blocks);
2561   while (changed)
2562     {
2563       if (dump_file && (dump_flags & TDF_DETAILS))
2564         fprintf (dump_file, "Starting iteration %d\n", num_iterations);
2565       /* ???  We need to clear our PHI translation cache here as the
2566          ANTIC sets shrink and we restrict valid translations to
2567          those having operands with leaders in ANTIC.  Same below
2568          for PA ANTIC computation.  */
2569       num_iterations++;
2570       changed = false;
2571       for (i = n_basic_blocks - NUM_FIXED_BLOCKS - 1; i >= 0; i--)
2572         {
2573           if (TEST_BIT (changed_blocks, postorder[i]))
2574             {
2575               basic_block block = BASIC_BLOCK (postorder[i]);
2576               changed |= compute_antic_aux (block,
2577                                             TEST_BIT (has_abnormal_preds,
2578                                                       block->index));
2579             }
2580         }
2581       /* Theoretically possible, but *highly* unlikely.  */
2582       gcc_checking_assert (num_iterations < 500);
2583     }
2584
2585   statistics_histogram_event (cfun, "compute_antic iterations",
2586                               num_iterations);
2587
2588   if (do_partial_partial)
2589     {
2590       sbitmap_ones (changed_blocks);
2591       mark_dfs_back_edges ();
2592       num_iterations = 0;
2593       changed = true;
2594       while (changed)
2595         {
2596           if (dump_file && (dump_flags & TDF_DETAILS))
2597             fprintf (dump_file, "Starting iteration %d\n", num_iterations);
2598           num_iterations++;
2599           changed = false;
2600           for (i = n_basic_blocks - NUM_FIXED_BLOCKS - 1 ; i >= 0; i--)
2601             {
2602               if (TEST_BIT (changed_blocks, postorder[i]))
2603                 {
2604                   basic_block block = BASIC_BLOCK (postorder[i]);
2605                   changed
2606                     |= compute_partial_antic_aux (block,
2607                                                   TEST_BIT (has_abnormal_preds,
2608                                                             block->index));
2609                 }
2610             }
2611           /* Theoretically possible, but *highly* unlikely.  */
2612           gcc_checking_assert (num_iterations < 500);
2613         }
2614       statistics_histogram_event (cfun, "compute_partial_antic iterations",
2615                                   num_iterations);
2616     }
2617   sbitmap_free (has_abnormal_preds);
2618   sbitmap_free (changed_blocks);
2619 }
2620
2621 /* Return true if we can value number the call in STMT.  This is true
2622    if we have a pure or constant call to a real function.  */
2623
2624 static bool
2625 can_value_number_call (gimple stmt)
2626 {
2627   if (gimple_call_internal_p (stmt))
2628     return false;
2629   if (gimple_call_flags (stmt) & (ECF_PURE | ECF_CONST))
2630     return true;
2631   return false;
2632 }
2633
2634 /* Return true if OP is a tree which we can perform PRE on.
2635    This may not match the operations we can value number, but in
2636    a perfect world would.  */
2637
2638 static bool
2639 can_PRE_operation (tree op)
2640 {
2641   return UNARY_CLASS_P (op)
2642     || BINARY_CLASS_P (op)
2643     || COMPARISON_CLASS_P (op)
2644     || TREE_CODE (op) == MEM_REF 
2645     || TREE_CODE (op) == COMPONENT_REF
2646     || TREE_CODE (op) == VIEW_CONVERT_EXPR
2647     || TREE_CODE (op) == CALL_EXPR
2648     || TREE_CODE (op) == ARRAY_REF;
2649 }
2650
2651
2652 /* Inserted expressions are placed onto this worklist, which is used
2653    for performing quick dead code elimination of insertions we made
2654    that didn't turn out to be necessary.   */
2655 static bitmap inserted_exprs;
2656
2657 /* Pool allocated fake store expressions are placed onto this
2658    worklist, which, after performing dead code elimination, is walked
2659    to see which expressions need to be put into GC'able memory  */
2660 static VEC(gimple, heap) *need_creation;
2661
2662 /* The actual worker for create_component_ref_by_pieces.  */
2663
2664 static tree
2665 create_component_ref_by_pieces_1 (basic_block block, vn_reference_t ref,
2666                                   unsigned int *operand, gimple_seq *stmts,
2667                                   gimple domstmt)
2668 {
2669   vn_reference_op_t currop = VEC_index (vn_reference_op_s, ref->operands,
2670                                         *operand);
2671   tree genop;
2672   ++*operand;
2673   switch (currop->opcode)
2674     {
2675     case CALL_EXPR:
2676       {
2677         tree folded, sc = NULL_TREE;
2678         unsigned int nargs = 0;
2679         tree fn, *args;
2680         if (TREE_CODE (currop->op0) == FUNCTION_DECL)
2681           fn = currop->op0;
2682         else
2683           {
2684             pre_expr op0 = get_or_alloc_expr_for (currop->op0);
2685             fn = find_or_generate_expression (block, op0, stmts, domstmt);
2686             if (!fn)
2687               return NULL_TREE;
2688           }
2689         if (currop->op1)
2690           {
2691             pre_expr scexpr = get_or_alloc_expr_for (currop->op1);
2692             sc = find_or_generate_expression (block, scexpr, stmts, domstmt);
2693             if (!sc)
2694               return NULL_TREE;
2695           }
2696         args = XNEWVEC (tree, VEC_length (vn_reference_op_s,
2697                                           ref->operands) - 1);
2698         while (*operand < VEC_length (vn_reference_op_s, ref->operands))
2699           {
2700             args[nargs] = create_component_ref_by_pieces_1 (block, ref,
2701                                                             operand, stmts,
2702                                                             domstmt);
2703             if (!args[nargs])
2704               {
2705                 free (args);
2706                 return NULL_TREE;
2707               }
2708             nargs++;
2709           }
2710         folded = build_call_array (currop->type,
2711                                    (TREE_CODE (fn) == FUNCTION_DECL
2712                                     ? build_fold_addr_expr (fn) : fn),
2713                                    nargs, args);
2714         free (args);
2715         if (sc)
2716           CALL_EXPR_STATIC_CHAIN (folded) = sc;
2717         return folded;
2718       }
2719       break;
2720     case MEM_REF:
2721       {
2722         tree baseop = create_component_ref_by_pieces_1 (block, ref, operand,
2723                                                         stmts, domstmt);
2724         tree offset = currop->op0;
2725         if (!baseop)
2726           return NULL_TREE;
2727         if (TREE_CODE (baseop) == ADDR_EXPR
2728             && handled_component_p (TREE_OPERAND (baseop, 0)))
2729           {
2730             HOST_WIDE_INT off;
2731             tree base;
2732             base = get_addr_base_and_unit_offset (TREE_OPERAND (baseop, 0),
2733                                                   &off);
2734             gcc_assert (base);
2735             offset = int_const_binop (PLUS_EXPR, offset,
2736                                       build_int_cst (TREE_TYPE (offset),
2737                                                      off));
2738             baseop = build_fold_addr_expr (base);
2739           }
2740         return fold_build2 (MEM_REF, currop->type, baseop, offset);
2741       }
2742       break;
2743     case TARGET_MEM_REF:
2744       {
2745         pre_expr op0expr, op1expr;
2746         tree genop0 = NULL_TREE, genop1 = NULL_TREE;
2747         vn_reference_op_t nextop = VEC_index (vn_reference_op_s, ref->operands,
2748                                               ++*operand);
2749         tree baseop = create_component_ref_by_pieces_1 (block, ref, operand,
2750                                                         stmts, domstmt);
2751         if (!baseop)
2752           return NULL_TREE;
2753         if (currop->op0)
2754           {
2755             op0expr = get_or_alloc_expr_for (currop->op0);
2756             genop0 = find_or_generate_expression (block, op0expr,
2757                                                   stmts, domstmt);
2758             if (!genop0)
2759               return NULL_TREE;
2760           }
2761         if (nextop->op0)
2762           {
2763             op1expr = get_or_alloc_expr_for (nextop->op0);
2764             genop1 = find_or_generate_expression (block, op1expr,
2765                                                   stmts, domstmt);
2766             if (!genop1)
2767               return NULL_TREE;
2768           }
2769         return build5 (TARGET_MEM_REF, currop->type,
2770                        baseop, currop->op2, genop0, currop->op1, genop1);
2771       }
2772       break;
2773     case ADDR_EXPR:
2774       if (currop->op0)
2775         {
2776           gcc_assert (is_gimple_min_invariant (currop->op0));
2777           return currop->op0;
2778         }
2779       /* Fallthrough.  */
2780     case REALPART_EXPR:
2781     case IMAGPART_EXPR:
2782     case VIEW_CONVERT_EXPR:
2783       {
2784         tree folded;
2785         tree genop0 = create_component_ref_by_pieces_1 (block, ref,
2786                                                         operand,
2787                                                         stmts, domstmt);
2788         if (!genop0)
2789           return NULL_TREE;
2790         folded = fold_build1 (currop->opcode, currop->type,
2791                               genop0);
2792         return folded;
2793       }
2794       break;
2795     case BIT_FIELD_REF:
2796       {
2797         tree folded;
2798         tree genop0 = create_component_ref_by_pieces_1 (block, ref, operand,
2799                                                         stmts, domstmt);
2800         pre_expr op1expr = get_or_alloc_expr_for (currop->op0);
2801         pre_expr op2expr = get_or_alloc_expr_for (currop->op1);
2802         tree genop1;
2803         tree genop2;
2804
2805         if (!genop0)
2806           return NULL_TREE;
2807         genop1 = find_or_generate_expression (block, op1expr, stmts, domstmt);
2808         if (!genop1)
2809           return NULL_TREE;
2810         genop2 = find_or_generate_expression (block, op2expr, stmts, domstmt);
2811         if (!genop2)
2812           return NULL_TREE;
2813         folded = fold_build3 (BIT_FIELD_REF, currop->type, genop0, genop1,
2814                               genop2);
2815         return folded;
2816       }
2817
2818       /* For array ref vn_reference_op's, operand 1 of the array ref
2819          is op0 of the reference op and operand 3 of the array ref is
2820          op1.  */
2821     case ARRAY_RANGE_REF:
2822     case ARRAY_REF:
2823       {
2824         tree genop0;
2825         tree genop1 = currop->op0;
2826         pre_expr op1expr;
2827         tree genop2 = currop->op1;
2828         pre_expr op2expr;
2829         tree genop3 = currop->op2;
2830         pre_expr op3expr;
2831         genop0 = create_component_ref_by_pieces_1 (block, ref, operand,
2832                                                    stmts, domstmt);
2833         if (!genop0)
2834           return NULL_TREE;
2835         op1expr = get_or_alloc_expr_for (genop1);
2836         genop1 = find_or_generate_expression (block, op1expr, stmts, domstmt);
2837         if (!genop1)
2838           return NULL_TREE;
2839         if (genop2)
2840           {
2841             tree domain_type = TYPE_DOMAIN (TREE_TYPE (genop0));
2842             /* Drop zero minimum index if redundant.  */
2843             if (integer_zerop (genop2)
2844                 && (!domain_type
2845                     || integer_zerop (TYPE_MIN_VALUE (domain_type))))
2846               genop2 = NULL_TREE;
2847             else
2848               {
2849                 op2expr = get_or_alloc_expr_for (genop2);
2850                 genop2 = find_or_generate_expression (block, op2expr, stmts,
2851                                                       domstmt);
2852                 if (!genop2)
2853                   return NULL_TREE;
2854               }
2855           }
2856         if (genop3)
2857           {
2858             tree elmt_type = TREE_TYPE (TREE_TYPE (genop0));
2859             /* We can't always put a size in units of the element alignment
2860                here as the element alignment may be not visible.  See
2861                PR43783.  Simply drop the element size for constant
2862                sizes.  */
2863             if (tree_int_cst_equal (genop3, TYPE_SIZE_UNIT (elmt_type)))
2864               genop3 = NULL_TREE;
2865             else
2866               {
2867                 genop3 = size_binop (EXACT_DIV_EXPR, genop3,
2868                                      size_int (TYPE_ALIGN_UNIT (elmt_type)));
2869                 op3expr = get_or_alloc_expr_for (genop3);
2870                 genop3 = find_or_generate_expression (block, op3expr, stmts,
2871                                                       domstmt);
2872                 if (!genop3)
2873                   return NULL_TREE;
2874               }
2875           }
2876         return build4 (currop->opcode, currop->type, genop0, genop1,
2877                        genop2, genop3);
2878       }
2879     case COMPONENT_REF:
2880       {
2881         tree op0;
2882         tree op1;
2883         tree genop2 = currop->op1;
2884         pre_expr op2expr;
2885         op0 = create_component_ref_by_pieces_1 (block, ref, operand,
2886                                                 stmts, domstmt);
2887         if (!op0)
2888           return NULL_TREE;
2889         /* op1 should be a FIELD_DECL, which are represented by
2890            themselves.  */
2891         op1 = currop->op0;
2892         if (genop2)
2893           {
2894             op2expr = get_or_alloc_expr_for (genop2);
2895             genop2 = find_or_generate_expression (block, op2expr, stmts,
2896                                                   domstmt);
2897             if (!genop2)
2898               return NULL_TREE;
2899           }
2900
2901         return fold_build3 (COMPONENT_REF, TREE_TYPE (op1), op0, op1,
2902                             genop2);
2903       }
2904       break;
2905     case SSA_NAME:
2906       {
2907         pre_expr op0expr = get_or_alloc_expr_for (currop->op0);
2908         genop = find_or_generate_expression (block, op0expr, stmts, domstmt);
2909         return genop;
2910       }
2911     case STRING_CST:
2912     case INTEGER_CST:
2913     case COMPLEX_CST:
2914     case VECTOR_CST:
2915     case REAL_CST:
2916     case CONSTRUCTOR:
2917     case VAR_DECL:
2918     case PARM_DECL:
2919     case CONST_DECL:
2920     case RESULT_DECL:
2921     case FUNCTION_DECL:
2922       return currop->op0;
2923
2924     default:
2925       gcc_unreachable ();
2926     }
2927 }
2928
2929 /* For COMPONENT_REF's and ARRAY_REF's, we can't have any intermediates for the
2930    COMPONENT_REF or MEM_REF or ARRAY_REF portion, because we'd end up with
2931    trying to rename aggregates into ssa form directly, which is a no no.
2932
2933    Thus, this routine doesn't create temporaries, it just builds a
2934    single access expression for the array, calling
2935    find_or_generate_expression to build the innermost pieces.
2936
2937    This function is a subroutine of create_expression_by_pieces, and
2938    should not be called on it's own unless you really know what you
2939    are doing.  */
2940
2941 static tree
2942 create_component_ref_by_pieces (basic_block block, vn_reference_t ref,
2943                                 gimple_seq *stmts, gimple domstmt)
2944 {
2945   unsigned int op = 0;
2946   return create_component_ref_by_pieces_1 (block, ref, &op, stmts, domstmt);
2947 }
2948
2949 /* Find a leader for an expression, or generate one using
2950    create_expression_by_pieces if it's ANTIC but
2951    complex.
2952    BLOCK is the basic_block we are looking for leaders in.
2953    EXPR is the expression to find a leader or generate for.
2954    STMTS is the statement list to put the inserted expressions on.
2955    Returns the SSA_NAME of the LHS of the generated expression or the
2956    leader.
2957    DOMSTMT if non-NULL is a statement that should be dominated by
2958    all uses in the generated expression.  If DOMSTMT is non-NULL this
2959    routine can fail and return NULL_TREE.  Otherwise it will assert
2960    on failure.  */
2961
2962 static tree
2963 find_or_generate_expression (basic_block block, pre_expr expr,
2964                              gimple_seq *stmts, gimple domstmt)
2965 {
2966   pre_expr leader = bitmap_find_leader (AVAIL_OUT (block),
2967                                         get_expr_value_id (expr), domstmt);
2968   tree genop = NULL;
2969   if (leader)
2970     {
2971       if (leader->kind == NAME)
2972         genop = PRE_EXPR_NAME (leader);
2973       else if (leader->kind == CONSTANT)
2974         genop = PRE_EXPR_CONSTANT (leader);
2975     }
2976
2977   /* If it's still NULL, it must be a complex expression, so generate
2978      it recursively.  Not so if inserting expressions for values generated
2979      by SCCVN.  */
2980   if (genop == NULL
2981       && !domstmt)
2982     {
2983       bitmap_set_t exprset;
2984       unsigned int lookfor = get_expr_value_id (expr);
2985       bool handled = false;
2986       bitmap_iterator bi;
2987       unsigned int i;
2988
2989       exprset = VEC_index (bitmap_set_t, value_expressions, lookfor);
2990       FOR_EACH_EXPR_ID_IN_SET (exprset, i, bi)
2991         {
2992           pre_expr temp = expression_for_id (i);
2993           if (temp->kind != NAME)
2994             {
2995               handled = true;
2996               genop = create_expression_by_pieces (block, temp, stmts,
2997                                                    domstmt,
2998                                                    get_expr_type (expr));
2999               break;
3000             }
3001         }
3002       if (!handled && domstmt)
3003         return NULL_TREE;
3004
3005       gcc_assert (handled);
3006     }
3007   return genop;
3008 }
3009
3010 #define NECESSARY GF_PLF_1
3011
3012 /* Create an expression in pieces, so that we can handle very complex
3013    expressions that may be ANTIC, but not necessary GIMPLE.
3014    BLOCK is the basic block the expression will be inserted into,
3015    EXPR is the expression to insert (in value form)
3016    STMTS is a statement list to append the necessary insertions into.
3017
3018    This function will die if we hit some value that shouldn't be
3019    ANTIC but is (IE there is no leader for it, or its components).
3020    This function may also generate expressions that are themselves
3021    partially or fully redundant.  Those that are will be either made
3022    fully redundant during the next iteration of insert (for partially
3023    redundant ones), or eliminated by eliminate (for fully redundant
3024    ones).
3025
3026    If DOMSTMT is non-NULL then we make sure that all uses in the
3027    expressions dominate that statement.  In this case the function
3028    can return NULL_TREE to signal failure.  */
3029
3030 static tree
3031 create_expression_by_pieces (basic_block block, pre_expr expr,
3032                              gimple_seq *stmts, gimple domstmt, tree type)
3033 {
3034   tree temp, name;
3035   tree folded;
3036   gimple_seq forced_stmts = NULL;
3037   unsigned int value_id;
3038   gimple_stmt_iterator gsi;
3039   tree exprtype = type ? type : get_expr_type (expr);
3040   pre_expr nameexpr;
3041   gimple newstmt;
3042
3043   switch (expr->kind)
3044     {
3045       /* We may hit the NAME/CONSTANT case if we have to convert types
3046          that value numbering saw through.  */
3047     case NAME:
3048       folded = PRE_EXPR_NAME (expr);
3049       break;
3050     case CONSTANT:
3051       folded = PRE_EXPR_CONSTANT (expr);
3052       break;
3053     case REFERENCE:
3054       {
3055         vn_reference_t ref = PRE_EXPR_REFERENCE (expr);
3056         folded = create_component_ref_by_pieces (block, ref, stmts, domstmt);
3057       }
3058       break;
3059     case NARY:
3060       {
3061         vn_nary_op_t nary = PRE_EXPR_NARY (expr);
3062         tree genop[4];
3063         unsigned i;
3064         for (i = 0; i < nary->length; ++i)
3065           {
3066             pre_expr op = get_or_alloc_expr_for (nary->op[i]);
3067             genop[i] = find_or_generate_expression (block, op,
3068                                                     stmts, domstmt);
3069             if (!genop[i])
3070               return NULL_TREE;
3071             /* Ensure genop[] is properly typed for POINTER_PLUS_EXPR.  It
3072                may have conversions stripped.  */
3073             if (nary->opcode == POINTER_PLUS_EXPR)
3074               {
3075                 if (i == 0)
3076                   genop[i] = fold_convert (nary->type, genop[i]);
3077                 else if (i == 1)
3078                   genop[i] = convert_to_ptrofftype (genop[i]);
3079               }
3080             else
3081               genop[i] = fold_convert (TREE_TYPE (nary->op[i]), genop[i]);
3082           }
3083         if (nary->opcode == CONSTRUCTOR)
3084           {
3085             VEC(constructor_elt,gc) *elts = NULL;
3086             for (i = 0; i < nary->length; ++i)
3087               CONSTRUCTOR_APPEND_ELT (elts, NULL_TREE, genop[i]);
3088             folded = build_constructor (nary->type, elts);
3089           }
3090         else
3091           {
3092             switch (nary->length)
3093               {
3094               case 1:
3095                 folded = fold_build1 (nary->opcode, nary->type,
3096                                       genop[0]);
3097                 break;
3098               case 2:
3099                 folded = fold_build2 (nary->opcode, nary->type,
3100                                       genop[0], genop[1]);
3101                 break;
3102               case 3:
3103                 folded = fold_build3 (nary->opcode, nary->type,
3104                                       genop[0], genop[1], genop[3]);
3105                 break;
3106               default:
3107                 gcc_unreachable ();
3108               }
3109           }
3110       }
3111       break;
3112     default:
3113       return NULL_TREE;
3114     }
3115
3116   if (!useless_type_conversion_p (exprtype, TREE_TYPE (folded)))
3117     folded = fold_convert (exprtype, folded);
3118
3119   /* Force the generated expression to be a sequence of GIMPLE
3120      statements.
3121      We have to call unshare_expr because force_gimple_operand may
3122      modify the tree we pass to it.  */
3123   folded = force_gimple_operand (unshare_expr (folded), &forced_stmts,
3124                                  false, NULL);
3125
3126   /* If we have any intermediate expressions to the value sets, add them
3127      to the value sets and chain them in the instruction stream.  */
3128   if (forced_stmts)
3129     {
3130       gsi = gsi_start (forced_stmts);
3131       for (; !gsi_end_p (gsi); gsi_next (&gsi))
3132         {
3133           gimple stmt = gsi_stmt (gsi);
3134           tree forcedname = gimple_get_lhs (stmt);
3135           pre_expr nameexpr;
3136
3137           if (TREE_CODE (forcedname) == SSA_NAME)
3138             {
3139               bitmap_set_bit (inserted_exprs, SSA_NAME_VERSION (forcedname));
3140               VN_INFO_GET (forcedname)->valnum = forcedname;
3141               VN_INFO (forcedname)->value_id = get_next_value_id ();
3142               nameexpr = get_or_alloc_expr_for_name (forcedname);
3143               add_to_value (VN_INFO (forcedname)->value_id, nameexpr);
3144               if (!in_fre)
3145                 bitmap_value_replace_in_set (NEW_SETS (block), nameexpr);
3146               bitmap_value_replace_in_set (AVAIL_OUT (block), nameexpr);
3147             }
3148           mark_symbols_for_renaming (stmt);
3149         }
3150       gimple_seq_add_seq (stmts, forced_stmts);
3151     }
3152
3153   /* Build and insert the assignment of the end result to the temporary
3154      that we will return.  */
3155   if (!pretemp || exprtype != TREE_TYPE (pretemp))
3156     pretemp = create_tmp_reg (exprtype, "pretmp");
3157
3158   temp = pretemp;
3159   add_referenced_var (temp);
3160
3161   newstmt = gimple_build_assign (temp, folded);
3162   name = make_ssa_name (temp, newstmt);
3163   gimple_assign_set_lhs (newstmt, name);
3164   gimple_set_plf (newstmt, NECESSARY, false);
3165
3166   gimple_seq_add_stmt (stmts, newstmt);
3167   bitmap_set_bit (inserted_exprs, SSA_NAME_VERSION (name));
3168
3169   /* All the symbols in NEWEXPR should be put into SSA form.  */
3170   mark_symbols_for_renaming (newstmt);
3171
3172   /* Fold the last statement.  */
3173   gsi = gsi_last (*stmts);
3174   if (fold_stmt_inplace (&gsi))
3175     update_stmt (gsi_stmt (gsi));
3176
3177   /* Add a value number to the temporary.
3178      The value may already exist in either NEW_SETS, or AVAIL_OUT, because
3179      we are creating the expression by pieces, and this particular piece of
3180      the expression may have been represented.  There is no harm in replacing
3181      here.  */
3182   VN_INFO_GET (name)->valnum = name;
3183   value_id = get_expr_value_id (expr);
3184   VN_INFO (name)->value_id = value_id;
3185   nameexpr = get_or_alloc_expr_for_name (name);
3186   add_to_value (value_id, nameexpr);
3187   if (NEW_SETS (block))
3188     bitmap_value_replace_in_set (NEW_SETS (block), nameexpr);
3189   bitmap_value_replace_in_set (AVAIL_OUT (block), nameexpr);
3190
3191   pre_stats.insertions++;
3192   if (dump_file && (dump_flags & TDF_DETAILS))
3193     {
3194       fprintf (dump_file, "Inserted ");
3195       print_gimple_stmt (dump_file, newstmt, 0, 0);
3196       fprintf (dump_file, " in predecessor %d\n", block->index);
3197     }
3198
3199   return name;
3200 }
3201
3202
3203 /* Returns true if we want to inhibit the insertions of PHI nodes
3204    for the given EXPR for basic block BB (a member of a loop).
3205    We want to do this, when we fear that the induction variable we
3206    create might inhibit vectorization.  */
3207
3208 static bool
3209 inhibit_phi_insertion (basic_block bb, pre_expr expr)
3210 {
3211   vn_reference_t vr = PRE_EXPR_REFERENCE (expr);
3212   VEC (vn_reference_op_s, heap) *ops = vr->operands;
3213   vn_reference_op_t op;
3214   unsigned i;
3215
3216   /* If we aren't going to vectorize we don't inhibit anything.  */
3217   if (!flag_tree_vectorize)
3218     return false;
3219
3220   /* Otherwise we inhibit the insertion when the address of the
3221      memory reference is a simple induction variable.  In other
3222      cases the vectorizer won't do anything anyway (either it's
3223      loop invariant or a complicated expression).  */
3224   FOR_EACH_VEC_ELT (vn_reference_op_s, ops, i, op)
3225     {
3226       switch (op->opcode)
3227         {
3228         case ARRAY_REF:
3229         case ARRAY_RANGE_REF:
3230           if (TREE_CODE (op->op0) != SSA_NAME)
3231             break;
3232           /* Fallthru.  */
3233         case SSA_NAME:
3234           {
3235             basic_block defbb = gimple_bb (SSA_NAME_DEF_STMT (op->op0));
3236             affine_iv iv;
3237             /* Default defs are loop invariant.  */
3238             if (!defbb)
3239               break;
3240             /* Defined outside this loop, also loop invariant.  */
3241             if (!flow_bb_inside_loop_p (bb->loop_father, defbb))
3242               break;
3243             /* If it's a simple induction variable inhibit insertion,
3244                the vectorizer might be interested in this one.  */
3245             if (simple_iv (bb->loop_father, bb->loop_father,
3246                            op->op0, &iv, true))
3247               return true;
3248             /* No simple IV, vectorizer can't do anything, hence no
3249                reason to inhibit the transformation for this operand.  */
3250             break;
3251           }
3252         default:
3253           break;
3254         }
3255     }
3256   return false;
3257 }
3258
3259 /* Insert the to-be-made-available values of expression EXPRNUM for each
3260    predecessor, stored in AVAIL, into the predecessors of BLOCK, and
3261    merge the result with a phi node, given the same value number as
3262    NODE.  Return true if we have inserted new stuff.  */
3263
3264 static bool
3265 insert_into_preds_of_block (basic_block block, unsigned int exprnum,
3266                             pre_expr *avail)
3267 {
3268   pre_expr expr = expression_for_id (exprnum);
3269   pre_expr newphi;
3270   unsigned int val = get_expr_value_id (expr);
3271   edge pred;
3272   bool insertions = false;
3273   bool nophi = false;
3274   basic_block bprime;
3275   pre_expr eprime;
3276   edge_iterator ei;
3277   tree type = get_expr_type (expr);
3278   tree temp;
3279   gimple phi;
3280
3281   if (dump_file && (dump_flags & TDF_DETAILS))
3282     {
3283       fprintf (dump_file, "Found partial redundancy for expression ");
3284       print_pre_expr (dump_file, expr);
3285       fprintf (dump_file, " (%04d)\n", val);
3286     }
3287
3288   /* Make sure we aren't creating an induction variable.  */
3289   if (block->loop_depth > 0 && EDGE_COUNT (block->preds) == 2)
3290     {
3291       bool firstinsideloop = false;
3292       bool secondinsideloop = false;
3293       firstinsideloop = flow_bb_inside_loop_p (block->loop_father,
3294                                                EDGE_PRED (block, 0)->src);
3295       secondinsideloop = flow_bb_inside_loop_p (block->loop_father,
3296                                                 EDGE_PRED (block, 1)->src);
3297       /* Induction variables only have one edge inside the loop.  */
3298       if ((firstinsideloop ^ secondinsideloop)
3299           && (expr->kind != REFERENCE
3300               || inhibit_phi_insertion (block, expr)))
3301         {
3302           if (dump_file && (dump_flags & TDF_DETAILS))
3303             fprintf (dump_file, "Skipping insertion of phi for partial redundancy: Looks like an induction variable\n");
3304           nophi = true;
3305         }
3306     }
3307
3308   /* Make the necessary insertions.  */
3309   FOR_EACH_EDGE (pred, ei, block->preds)
3310     {
3311       gimple_seq stmts = NULL;
3312       tree builtexpr;
3313       bprime = pred->src;
3314       eprime = avail[bprime->index];
3315
3316       if (eprime->kind != NAME && eprime->kind != CONSTANT)
3317         {
3318           builtexpr = create_expression_by_pieces (bprime,
3319                                                    eprime,
3320                                                    &stmts, NULL,
3321                                                    type);
3322           gcc_assert (!(pred->flags & EDGE_ABNORMAL));
3323           gsi_insert_seq_on_edge (pred, stmts);
3324           avail[bprime->index] = get_or_alloc_expr_for_name (builtexpr);
3325           insertions = true;
3326         }
3327       else if (eprime->kind == CONSTANT)
3328         {
3329           /* Constants may not have the right type, fold_convert
3330              should give us back a constant with the right type.
3331           */
3332           tree constant = PRE_EXPR_CONSTANT (eprime);
3333           if (!useless_type_conversion_p (type, TREE_TYPE (constant)))
3334             {
3335               tree builtexpr = fold_convert (type, constant);
3336               if (!is_gimple_min_invariant (builtexpr))
3337                 {
3338                   tree forcedexpr = force_gimple_operand (builtexpr,
3339                                                           &stmts, true,
3340                                                           NULL);
3341                   if (!is_gimple_min_invariant (forcedexpr))
3342                     {
3343                       if (forcedexpr != builtexpr)
3344                         {
3345                           VN_INFO_GET (forcedexpr)->valnum = PRE_EXPR_CONSTANT (eprime);
3346                           VN_INFO (forcedexpr)->value_id = get_expr_value_id (eprime);
3347                         }
3348                       if (stmts)
3349                         {
3350                           gimple_stmt_iterator gsi;
3351                           gsi = gsi_start (stmts);
3352                           for (; !gsi_end_p (gsi); gsi_next (&gsi))
3353                             {
3354                               gimple stmt = gsi_stmt (gsi);
3355                               tree lhs = gimple_get_lhs (stmt);
3356                               if (TREE_CODE (lhs) == SSA_NAME)
3357                                 bitmap_set_bit (inserted_exprs,
3358                                                 SSA_NAME_VERSION (lhs));
3359                               gimple_set_plf (stmt, NECESSARY, false);
3360                             }
3361                           gsi_insert_seq_on_edge (pred, stmts);
3362                         }
3363                       avail[bprime->index] = get_or_alloc_expr_for_name (forcedexpr);
3364                     }
3365                 }
3366               else
3367                 avail[bprime->index] = get_or_alloc_expr_for_constant (builtexpr);
3368             }
3369         }
3370       else if (eprime->kind == NAME)
3371         {
3372           /* We may have to do a conversion because our value
3373              numbering can look through types in certain cases, but
3374              our IL requires all operands of a phi node have the same
3375              type.  */
3376           tree name = PRE_EXPR_NAME (eprime);
3377           if (!useless_type_conversion_p (type, TREE_TYPE (name)))
3378             {
3379               tree builtexpr;
3380               tree forcedexpr;
3381               builtexpr = fold_convert (type, name);
3382               forcedexpr = force_gimple_operand (builtexpr,
3383                                                  &stmts, true,
3384                                                  NULL);
3385
3386               if (forcedexpr != name)
3387                 {
3388                   VN_INFO_GET (forcedexpr)->valnum = VN_INFO (name)->valnum;
3389                   VN_INFO (forcedexpr)->value_id = VN_INFO (name)->value_id;
3390                 }
3391
3392               if (stmts)
3393                 {
3394                   gimple_stmt_iterator gsi;
3395                   gsi = gsi_start (stmts);
3396                   for (; !gsi_end_p (gsi); gsi_next (&gsi))
3397                     {
3398                       gimple stmt = gsi_stmt (gsi);
3399                       tree lhs = gimple_get_lhs (stmt);
3400                       if (TREE_CODE (lhs) == SSA_NAME)
3401                         bitmap_set_bit (inserted_exprs, SSA_NAME_VERSION (lhs));
3402                       gimple_set_plf (stmt, NECESSARY, false);
3403                     }
3404                   gsi_insert_seq_on_edge (pred, stmts);
3405                 }
3406               avail[bprime->index] = get_or_alloc_expr_for_name (forcedexpr);
3407             }
3408         }
3409     }
3410   /* If we didn't want a phi node, and we made insertions, we still have
3411      inserted new stuff, and thus return true.  If we didn't want a phi node,
3412      and didn't make insertions, we haven't added anything new, so return
3413      false.  */
3414   if (nophi && insertions)
3415     return true;
3416   else if (nophi &&&n