OSDN Git Service

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