OSDN Git Service

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