OSDN Git Service

2008-08-19 Richard Guenther <rguenther@suse.de>
[pf3gnuchains/gcc-fork.git] / gcc / tree-ssa-pre.c
1 /* SSA-PRE for trees.
2    Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007
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, true);
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         if (currop->opcode == MISALIGNED_INDIRECT_REF)
2503           folded = fold_build2 (currop->opcode, currop->type,
2504                                 genop1, currop->op1);
2505         else
2506           folded = fold_build1 (currop->opcode, currop->type,
2507                                 genop1);
2508         return folded;
2509       }
2510       break;
2511     case BIT_FIELD_REF:
2512       {
2513         tree folded;
2514         tree genop0 = create_component_ref_by_pieces_1 (block, ref, operand,
2515                                                         stmts, domstmt);
2516         pre_expr op1expr = get_or_alloc_expr_for (currop->op0);
2517         pre_expr op2expr = get_or_alloc_expr_for (currop->op1);
2518         tree genop1;
2519         tree genop2;
2520
2521         if (!genop0)
2522           return NULL_TREE;
2523         genop1 = find_or_generate_expression (block, op1expr, stmts, domstmt);
2524         if (!genop1)
2525           return NULL_TREE;
2526         genop2 = find_or_generate_expression (block, op2expr, stmts, domstmt);
2527         if (!genop2)
2528           return NULL_TREE;
2529         folded = fold_build3 (BIT_FIELD_REF, currop->type, genop0, genop1,
2530                               genop2);
2531         return folded;
2532       }
2533
2534       /* For array ref vn_reference_op's, operand 1 of the array ref
2535          is op0 of the reference op and operand 3 of the array ref is
2536          op1.  */
2537     case ARRAY_RANGE_REF:
2538     case ARRAY_REF:
2539       {
2540         tree genop0;
2541         tree genop1 = currop->op0;
2542         pre_expr op1expr;
2543         tree genop2 = currop->op1;
2544         pre_expr op2expr;
2545         tree genop3;
2546         genop0 = create_component_ref_by_pieces_1 (block, ref, operand,
2547                                                    stmts, domstmt);
2548         if (!genop0)
2549           return NULL_TREE;
2550         op1expr = get_or_alloc_expr_for (genop1);
2551         genop1 = find_or_generate_expression (block, op1expr, stmts, domstmt);
2552         if (!genop1)
2553           return NULL_TREE;
2554         if (genop2)
2555           {
2556             op2expr = get_or_alloc_expr_for (genop2);
2557             genop2 = find_or_generate_expression (block, op2expr, stmts,
2558                                                   domstmt);
2559             if (!genop2)
2560               return NULL_TREE;
2561           }
2562
2563         genop3 = currop->op2;
2564         return build4 (currop->opcode, currop->type, genop0, genop1,
2565                        genop2, genop3);
2566       }
2567     case COMPONENT_REF:
2568       {
2569         tree op0;
2570         tree op1;
2571         tree genop2 = currop->op1;
2572         pre_expr op2expr;
2573         op0 = create_component_ref_by_pieces_1 (block, ref, operand,
2574                                                 stmts, domstmt);
2575         if (!op0)
2576           return NULL_TREE;
2577         /* op1 should be a FIELD_DECL, which are represented by
2578            themselves.  */
2579         op1 = currop->op0;
2580         if (genop2)
2581           {
2582             op2expr = get_or_alloc_expr_for (genop2);
2583             genop2 = find_or_generate_expression (block, op2expr, stmts,
2584                                                   domstmt);
2585             if (!genop2)
2586               return NULL_TREE;
2587           }
2588
2589         return fold_build3 (COMPONENT_REF, TREE_TYPE (op1), op0, op1,
2590                             genop2);
2591       }
2592       break;
2593     case SSA_NAME:
2594       {
2595         pre_expr op0expr = get_or_alloc_expr_for (currop->op0);
2596         genop = find_or_generate_expression (block, op0expr, stmts, domstmt);
2597         return genop;
2598       }
2599     case STRING_CST:
2600     case INTEGER_CST:
2601     case COMPLEX_CST:
2602     case VECTOR_CST:
2603     case REAL_CST:
2604     case CONSTRUCTOR:
2605     case VAR_DECL:
2606     case PARM_DECL:
2607     case CONST_DECL:
2608     case RESULT_DECL:
2609     case FUNCTION_DECL:
2610       return currop->op0;
2611
2612     default:
2613       gcc_unreachable ();
2614     }
2615 }
2616
2617 /* For COMPONENT_REF's and ARRAY_REF's, we can't have any intermediates for the
2618    COMPONENT_REF or INDIRECT_REF or ARRAY_REF portion, because we'd end up with
2619    trying to rename aggregates into ssa form directly, which is a no no.
2620
2621    Thus, this routine doesn't create temporaries, it just builds a
2622    single access expression for the array, calling
2623    find_or_generate_expression to build the innermost pieces.
2624
2625    This function is a subroutine of create_expression_by_pieces, and
2626    should not be called on it's own unless you really know what you
2627    are doing.  */
2628
2629 static tree
2630 create_component_ref_by_pieces (basic_block block, vn_reference_t ref,
2631                                 gimple_seq *stmts, gimple domstmt)
2632 {
2633   unsigned int op = 0;
2634   return create_component_ref_by_pieces_1 (block, ref, &op, stmts, domstmt);
2635 }
2636
2637 /* Find a leader for an expression, or generate one using
2638    create_expression_by_pieces if it's ANTIC but
2639    complex.
2640    BLOCK is the basic_block we are looking for leaders in.
2641    EXPR is the expression to find a leader or generate for.
2642    STMTS is the statement list to put the inserted expressions on.
2643    Returns the SSA_NAME of the LHS of the generated expression or the
2644    leader.
2645    DOMSTMT if non-NULL is a statement that should be dominated by
2646    all uses in the generated expression.  If DOMSTMT is non-NULL this
2647    routine can fail and return NULL_TREE.  Otherwise it will assert
2648    on failure.  */
2649
2650 static tree
2651 find_or_generate_expression (basic_block block, pre_expr expr,
2652                              gimple_seq *stmts, gimple domstmt)
2653 {
2654   pre_expr leader = bitmap_find_leader (AVAIL_OUT (block),
2655                                         get_expr_value_id (expr), domstmt);
2656   tree genop = NULL;
2657   if (leader)
2658     {
2659       if (leader->kind == NAME)
2660         genop = PRE_EXPR_NAME (leader);
2661       else if (leader->kind == CONSTANT)
2662         genop = PRE_EXPR_CONSTANT (leader);
2663     }
2664
2665   /* If it's still NULL, it must be a complex expression, so generate
2666      it recursively.  */
2667   if (genop == NULL)
2668     {
2669       bitmap_set_t exprset;
2670       unsigned int lookfor = get_expr_value_id (expr);
2671       bool handled = false;
2672       bitmap_iterator bi;
2673       unsigned int i;
2674
2675       exprset = VEC_index (bitmap_set_t, value_expressions, lookfor);
2676       FOR_EACH_EXPR_ID_IN_SET (exprset, i, bi)
2677         {
2678           pre_expr temp = expression_for_id (i);
2679           if (temp->kind != NAME)
2680             {
2681               handled = true;
2682               genop = create_expression_by_pieces (block, temp, stmts,
2683                                                    domstmt,
2684                                                    get_expr_type (expr));
2685               break;
2686             }
2687         }
2688       if (!handled && domstmt)
2689         return NULL_TREE;
2690
2691       gcc_assert (handled);
2692     }
2693   return genop;
2694 }
2695
2696 #define NECESSARY GF_PLF_1
2697
2698 /* Create an expression in pieces, so that we can handle very complex
2699    expressions that may be ANTIC, but not necessary GIMPLE.
2700    BLOCK is the basic block the expression will be inserted into,
2701    EXPR is the expression to insert (in value form)
2702    STMTS is a statement list to append the necessary insertions into.
2703
2704    This function will die if we hit some value that shouldn't be
2705    ANTIC but is (IE there is no leader for it, or its components).
2706    This function may also generate expressions that are themselves
2707    partially or fully redundant.  Those that are will be either made
2708    fully redundant during the next iteration of insert (for partially
2709    redundant ones), or eliminated by eliminate (for fully redundant
2710    ones).
2711
2712    If DOMSTMT is non-NULL then we make sure that all uses in the
2713    expressions dominate that statement.  In this case the function
2714    can return NULL_TREE to signal failure.  */
2715
2716 static tree
2717 create_expression_by_pieces (basic_block block, pre_expr expr,
2718                              gimple_seq *stmts, gimple domstmt, tree type)
2719 {
2720   tree temp, name;
2721   tree folded, newexpr;
2722   gimple_seq forced_stmts;
2723   unsigned int value_id;
2724   gimple_stmt_iterator gsi;
2725   tree exprtype = type ? type : get_expr_type (expr);
2726   pre_expr nameexpr;
2727   gimple newstmt;
2728
2729   switch (expr->kind)
2730     {
2731       /* We may hit the NAME/CONSTANT case if we have to convert types
2732          that value numbering saw through.  */
2733     case NAME:
2734       folded = PRE_EXPR_NAME (expr);
2735       break;
2736     case CONSTANT:
2737       folded = PRE_EXPR_CONSTANT (expr);
2738       break;
2739     case REFERENCE:
2740       {
2741         vn_reference_t ref = PRE_EXPR_REFERENCE (expr);
2742         folded = create_component_ref_by_pieces (block, ref, stmts, domstmt);
2743       }
2744       break;
2745     case NARY:
2746       {
2747         vn_nary_op_t nary = PRE_EXPR_NARY (expr);
2748         switch (nary->length)
2749           {
2750           case 2:
2751             {
2752               pre_expr op1 = get_or_alloc_expr_for (nary->op[0]);
2753               pre_expr op2 = get_or_alloc_expr_for (nary->op[1]);
2754               tree genop1 = find_or_generate_expression (block, op1,
2755                                                          stmts, domstmt);
2756               tree genop2 = find_or_generate_expression (block, op2,
2757                                                          stmts, domstmt);
2758               if (!genop1 || !genop2)
2759                 return NULL_TREE;
2760               genop1 = fold_convert (TREE_TYPE (nary->op[0]),
2761                                      genop1);
2762               /* Ensure op2 is a sizetype for POINTER_PLUS_EXPR.  It
2763                  may be a constant with the wrong type.  */
2764               if (nary->opcode == POINTER_PLUS_EXPR)
2765                 genop2 = fold_convert (sizetype, genop2);
2766               else
2767                 genop2 = fold_convert (TREE_TYPE (nary->op[1]), genop2);
2768               
2769               folded = fold_build2 (nary->opcode, nary->type,
2770                                     genop1, genop2);
2771             }
2772             break;
2773           case 1:
2774             {
2775               pre_expr op1 = get_or_alloc_expr_for (nary->op[0]);
2776               tree genop1 = find_or_generate_expression (block, op1,
2777                                                          stmts, domstmt);
2778               if (!genop1)
2779                 return NULL_TREE;
2780               genop1 = fold_convert (TREE_TYPE (nary->op[0]), genop1);
2781
2782               folded = fold_build1 (nary->opcode, nary->type,
2783                                     genop1);
2784             }
2785             break;
2786           default:
2787             return NULL_TREE;
2788           }
2789       }
2790       break;
2791     default:
2792       return NULL_TREE;
2793     }
2794   folded = fold_convert (exprtype, folded);
2795   /* Force the generated expression to be a sequence of GIMPLE
2796      statements.
2797      We have to call unshare_expr because force_gimple_operand may
2798      modify the tree we pass to it.  */
2799   newexpr = force_gimple_operand (unshare_expr (folded), &forced_stmts,
2800                                   false, NULL);
2801
2802   /* If we have any intermediate expressions to the value sets, add them
2803      to the value sets and chain them in the instruction stream.  */
2804   if (forced_stmts)
2805     {
2806       gsi = gsi_start (forced_stmts);
2807       for (; !gsi_end_p (gsi); gsi_next (&gsi))
2808         {
2809           gimple stmt = gsi_stmt (gsi);
2810           tree forcedname = gimple_get_lhs (stmt);
2811           pre_expr nameexpr;
2812
2813           VEC_safe_push (gimple, heap, inserted_exprs, stmt);
2814           if (TREE_CODE (forcedname) == SSA_NAME)
2815             {
2816               VN_INFO_GET (forcedname)->valnum = forcedname;
2817               VN_INFO (forcedname)->value_id = get_next_value_id ();
2818               nameexpr = get_or_alloc_expr_for_name (forcedname);
2819               add_to_value (VN_INFO (forcedname)->value_id, nameexpr);
2820               bitmap_value_replace_in_set (NEW_SETS (block), nameexpr);
2821               bitmap_value_replace_in_set (AVAIL_OUT (block), nameexpr);
2822             }
2823           mark_symbols_for_renaming (stmt);
2824         }
2825       gimple_seq_add_seq (stmts, forced_stmts);
2826     }
2827
2828   /* Build and insert the assignment of the end result to the temporary
2829      that we will return.  */
2830   if (!pretemp || exprtype != TREE_TYPE (pretemp))
2831     {
2832       pretemp = create_tmp_var (exprtype, "pretmp");
2833       get_var_ann (pretemp);
2834     }
2835
2836   temp = pretemp;
2837   add_referenced_var (temp);
2838
2839   if (TREE_CODE (exprtype) == COMPLEX_TYPE
2840       || TREE_CODE (exprtype) == VECTOR_TYPE)
2841     DECL_GIMPLE_REG_P (temp) = 1;
2842
2843   newstmt = gimple_build_assign (temp, newexpr);
2844   name = make_ssa_name (temp, newstmt);
2845   gimple_assign_set_lhs (newstmt, name);
2846   gimple_set_plf (newstmt, NECESSARY, false);
2847
2848   gimple_seq_add_stmt (stmts, newstmt);
2849   VEC_safe_push (gimple, heap, inserted_exprs, newstmt);
2850
2851   /* All the symbols in NEWEXPR should be put into SSA form.  */
2852   mark_symbols_for_renaming (newstmt);
2853
2854   /* Add a value number to the temporary.
2855      The value may already exist in either NEW_SETS, or AVAIL_OUT, because
2856      we are creating the expression by pieces, and this particular piece of
2857      the expression may have been represented.  There is no harm in replacing
2858      here.  */
2859   VN_INFO_GET (name)->valnum = name;
2860   value_id = get_expr_value_id (expr);
2861   VN_INFO (name)->value_id = value_id;
2862   nameexpr = get_or_alloc_expr_for_name (name);
2863   add_to_value (value_id, nameexpr);
2864   if (!in_fre)
2865     bitmap_value_replace_in_set (NEW_SETS (block), nameexpr);
2866   bitmap_value_replace_in_set (AVAIL_OUT (block), nameexpr);
2867
2868   pre_stats.insertions++;
2869   if (dump_file && (dump_flags & TDF_DETAILS))
2870     {
2871       fprintf (dump_file, "Inserted ");
2872       print_gimple_stmt (dump_file, newstmt, 0, 0);
2873       fprintf (dump_file, " in predecessor %d\n", block->index);
2874     }
2875
2876   return name;
2877 }
2878
2879
2880 /* Insert the to-be-made-available values of expression EXPRNUM for each
2881    predecessor, stored in AVAIL, into the predecessors of BLOCK, and
2882    merge the result with a phi node, given the same value number as
2883    NODE.  Return true if we have inserted new stuff.  */
2884
2885 static bool
2886 insert_into_preds_of_block (basic_block block, unsigned int exprnum,
2887                             pre_expr *avail)
2888 {
2889   pre_expr expr = expression_for_id (exprnum);
2890   pre_expr newphi;
2891   unsigned int val = get_expr_value_id (expr);
2892   edge pred;
2893   bool insertions = false;
2894   bool nophi = false;
2895   basic_block bprime;
2896   pre_expr eprime;
2897   edge_iterator ei;
2898   tree type = get_expr_type (expr);
2899   tree temp;
2900   gimple phi;
2901
2902   if (dump_file && (dump_flags & TDF_DETAILS))
2903     {
2904       fprintf (dump_file, "Found partial redundancy for expression ");
2905       print_pre_expr (dump_file, expr);
2906       fprintf (dump_file, " (%04d)\n", val);
2907     }
2908
2909   /* Make sure we aren't creating an induction variable.  */
2910   if (block->loop_depth > 0 && EDGE_COUNT (block->preds) == 2
2911       && expr->kind != REFERENCE)
2912     {
2913       bool firstinsideloop = false;
2914       bool secondinsideloop = false;
2915       firstinsideloop = flow_bb_inside_loop_p (block->loop_father,
2916                                                EDGE_PRED (block, 0)->src);
2917       secondinsideloop = flow_bb_inside_loop_p (block->loop_father,
2918                                                 EDGE_PRED (block, 1)->src);
2919       /* Induction variables only have one edge inside the loop.  */
2920       if (firstinsideloop ^ secondinsideloop)
2921         {
2922           if (dump_file && (dump_flags & TDF_DETAILS))
2923             fprintf (dump_file, "Skipping insertion of phi for partial redundancy: Looks like an induction variable\n");
2924           nophi = true;
2925         }
2926     }
2927
2928
2929   /* Make the necessary insertions.  */
2930   FOR_EACH_EDGE (pred, ei, block->preds)
2931     {
2932       gimple_seq stmts = NULL;
2933       tree builtexpr;
2934       bprime = pred->src;
2935       eprime = avail[bprime->index];
2936
2937       if (eprime->kind != NAME && eprime->kind != CONSTANT)
2938         {
2939           builtexpr = create_expression_by_pieces (bprime,
2940                                                    eprime,
2941                                                    &stmts, NULL,
2942                                                    type);
2943           gcc_assert (!(pred->flags & EDGE_ABNORMAL));
2944           gsi_insert_seq_on_edge (pred, stmts);
2945           avail[bprime->index] = get_or_alloc_expr_for_name (builtexpr);
2946           insertions = true;
2947         }
2948       else if (eprime->kind == CONSTANT)
2949         {
2950           /* Constants may not have the right type, fold_convert
2951              should give us back a constant with the right type.
2952           */
2953           tree constant = PRE_EXPR_CONSTANT (eprime);
2954           if (TREE_TYPE (constant) != type)
2955             {
2956               tree builtexpr = fold_convert (type, constant);
2957               if (is_gimple_min_invariant (builtexpr))
2958                 {
2959                   PRE_EXPR_CONSTANT (eprime) = builtexpr;
2960                 }
2961               else
2962                 {
2963                   tree forcedexpr = force_gimple_operand (builtexpr,
2964                                                           &stmts, true,
2965                                                           NULL);
2966                   if (is_gimple_min_invariant (forcedexpr))
2967                     {
2968                       PRE_EXPR_CONSTANT (eprime) = forcedexpr;
2969                     }
2970                   else
2971                     {
2972                       if (forcedexpr != builtexpr)
2973                         {
2974                           VN_INFO_GET (forcedexpr)->valnum = PRE_EXPR_CONSTANT (eprime);
2975                           VN_INFO (forcedexpr)->value_id = get_expr_value_id (eprime);
2976                         }
2977                       if (stmts)
2978                         {
2979                           gimple_stmt_iterator gsi;
2980                           gsi = gsi_start (stmts);
2981                           for (; !gsi_end_p (gsi); gsi_next (&gsi))
2982                             {
2983                               gimple stmt = gsi_stmt (gsi);
2984                               VEC_safe_push (gimple, heap, inserted_exprs, stmt);
2985                               gimple_set_plf (stmt, NECESSARY, false);
2986                             }
2987                           gsi_insert_seq_on_edge (pred, stmts);
2988                         }
2989                       avail[bprime->index] = get_or_alloc_expr_for_name (forcedexpr);
2990                     }
2991                 }
2992             }
2993         }
2994       else if (eprime->kind == NAME)
2995         {
2996           /* We may have to do a conversion because our value
2997              numbering can look through types in certain cases, but
2998              our IL requires all operands of a phi node have the same
2999              type.  */
3000           tree name = PRE_EXPR_NAME (eprime);
3001           if (!useless_type_conversion_p (type, TREE_TYPE (name)))
3002             {
3003               tree builtexpr;
3004               tree forcedexpr;
3005               builtexpr = fold_convert (type, name);
3006               forcedexpr = force_gimple_operand (builtexpr,
3007                                                  &stmts, true,
3008                                                  NULL);
3009
3010               if (forcedexpr != name)
3011                 {
3012                   VN_INFO_GET (forcedexpr)->valnum = VN_INFO (name)->valnum;
3013                   VN_INFO (forcedexpr)->value_id = VN_INFO (name)->value_id;
3014                 }
3015
3016               if (stmts)
3017                 {
3018                   gimple_stmt_iterator gsi;
3019                   gsi = gsi_start (stmts);
3020                   for (; !gsi_end_p (gsi); gsi_next (&gsi))
3021                     {
3022                       gimple stmt = gsi_stmt (gsi);
3023                       VEC_safe_push (gimple, heap, inserted_exprs, stmt);
3024                       gimple_set_plf (stmt, NECESSARY, false);
3025                     }
3026                   gsi_insert_seq_on_edge (pred, stmts);
3027                 }
3028               avail[bprime->index] = get_or_alloc_expr_for_name (forcedexpr);
3029             }
3030         }
3031     }
3032   /* If we didn't want a phi node, and we made insertions, we still have
3033      inserted new stuff, and thus return true.  If we didn't want a phi node,
3034      and didn't make insertions, we haven't added anything new, so return
3035      false.  */
3036   if (nophi && insertions)
3037     return true;
3038   else if (nophi && !insertions)
3039     return false;
3040
3041   /* Now build a phi for the new variable.  */
3042   if (!prephitemp || TREE_TYPE (prephitemp) != type)
3043     {
3044       prephitemp = create_tmp_var (type, "prephitmp");
3045       get_var_ann (prephitemp);
3046     }
3047
3048   temp = prephitemp;
3049   add_referenced_var (temp);
3050
3051   if (TREE_CODE (type) == COMPLEX_TYPE
3052       || TREE_CODE (type) == VECTOR_TYPE)
3053     DECL_GIMPLE_REG_P (temp) = 1;
3054   phi = create_phi_node (temp, block);
3055
3056   gimple_set_plf (phi, NECESSARY, false);
3057   VN_INFO_GET (gimple_phi_result (phi))->valnum = gimple_phi_result (phi);
3058   VN_INFO (gimple_phi_result (phi))->value_id = val;
3059   VEC_safe_push (gimple, heap, inserted_exprs, phi);
3060   FOR_EACH_EDGE (pred, ei, block->preds)
3061     {
3062       pre_expr ae = avail[pred->src->index];
3063       gcc_assert (get_expr_type (ae) == type
3064                   || useless_type_conversion_p (type, get_expr_type (ae)));
3065       if (ae->kind == CONSTANT)
3066         add_phi_arg (phi, PRE_EXPR_CONSTANT (ae), pred);
3067       else
3068         add_phi_arg (phi, PRE_EXPR_NAME (avail[pred->src->index]), pred);
3069     }
3070
3071   newphi = get_or_alloc_expr_for_name (gimple_phi_result (phi));
3072   add_to_value (val, newphi);
3073
3074   /* The value should *not* exist in PHI_GEN, or else we wouldn't be doing
3075      this insertion, since we test for the existence of this value in PHI_GEN
3076      before proceeding with the partial redundancy checks in insert_aux.
3077
3078      The value may exist in AVAIL_OUT, in particular, it could be represented
3079      by the expression we are trying to eliminate, in which case we want the
3080      replacement to occur.  If it's not existing in AVAIL_OUT, we want it
3081      inserted there.
3082
3083      Similarly, to the PHI_GEN case, the value should not exist in NEW_SETS of
3084      this block, because if it did, it would have existed in our dominator's
3085      AVAIL_OUT, and would have been skipped due to the full redundancy check.
3086   */
3087
3088   bitmap_insert_into_set (PHI_GEN (block), newphi);
3089   bitmap_value_replace_in_set (AVAIL_OUT (block),
3090                                newphi);
3091   bitmap_insert_into_set (NEW_SETS (block),
3092                           newphi);
3093
3094   if (dump_file && (dump_flags & TDF_DETAILS))
3095     {
3096       fprintf (dump_file, "Created phi ");
3097       print_gimple_stmt (dump_file, phi, 0, 0);
3098       fprintf (dump_file, " in block %d\n", block->index);
3099     }
3100   pre_stats.phis++;
3101   return true;
3102 }
3103
3104
3105
3106 /* Perform insertion of partially redundant values.
3107    For BLOCK, do the following:
3108    1.  Propagate the NEW_SETS of the dominator into the current block.
3109    If the block has multiple predecessors,
3110        2a. Iterate over the ANTIC expressions for the block to see if
3111            any of them are partially redundant.
3112        2b. If so, insert them into the necessary predecessors to make
3113            the expression fully redundant.
3114        2c. Insert a new PHI merging the values of the predecessors.
3115        2d. Insert the new PHI, and the new expressions, into the
3116            NEW_SETS set.
3117    3. Recursively call ourselves on the dominator children of BLOCK.
3118
3119    Steps 1, 2a, and 3 are done by insert_aux. 2b, 2c and 2d are done by
3120    do_regular_insertion and do_partial_insertion.
3121
3122 */
3123
3124 static bool
3125 do_regular_insertion (basic_block block, basic_block dom)
3126 {
3127   bool new_stuff = false;
3128   VEC (pre_expr, heap) *exprs = sorted_array_from_bitmap_set (ANTIC_IN (block));
3129   pre_expr expr;
3130   int i;
3131
3132   for (i = 0; VEC_iterate (pre_expr, exprs, i, expr); i++)
3133     {
3134       if (expr->kind != NAME)
3135         {
3136           pre_expr *avail;
3137           unsigned int val;
3138           bool by_some = false;
3139           bool cant_insert = false;
3140           bool all_same = true;
3141           pre_expr first_s = NULL;
3142           edge pred;
3143           basic_block bprime;
3144           pre_expr eprime = NULL;
3145           edge_iterator ei;
3146           pre_expr edoubleprime;
3147
3148           val = get_expr_value_id (expr);
3149           if (bitmap_set_contains_value (PHI_GEN (block), val))
3150             continue;
3151           if (bitmap_set_contains_value (AVAIL_OUT (dom), val))
3152             {
3153               if (dump_file && (dump_flags & TDF_DETAILS))
3154                 fprintf (dump_file, "Found fully redundant value\n");
3155               continue;
3156             }
3157
3158           avail = XCNEWVEC (pre_expr, last_basic_block);
3159           FOR_EACH_EDGE (pred, ei, block->preds)
3160             {
3161               unsigned int vprime;
3162
3163               /* This can happen in the very weird case
3164                  that our fake infinite loop edges have caused a
3165                  critical edge to appear.  */
3166               if (EDGE_CRITICAL_P (pred))
3167                 {
3168                   cant_insert = true;
3169                   break;
3170                 }
3171               bprime = pred->src;
3172               eprime = phi_translate (expr, ANTIC_IN (block), NULL,
3173                                       bprime, block);
3174
3175               /* eprime will generally only be NULL if the
3176                  value of the expression, translated
3177                  through the PHI for this predecessor, is
3178                  undefined.  If that is the case, we can't
3179                  make the expression fully redundant,
3180                  because its value is undefined along a
3181                  predecessor path.  We can thus break out
3182                  early because it doesn't matter what the
3183                  rest of the results are.  */
3184               if (eprime == NULL)
3185                 {
3186                   cant_insert = true;
3187                   break;
3188                 }
3189
3190               eprime = fully_constant_expression (eprime);
3191               vprime = get_expr_value_id (eprime);
3192               edoubleprime = bitmap_find_leader (AVAIL_OUT (bprime),
3193                                                  vprime, NULL);
3194               if (edoubleprime == NULL)
3195                 {
3196                   avail[bprime->index] = eprime;
3197                   all_same = false;
3198                 }
3199               else
3200                 {
3201                   avail[bprime->index] = edoubleprime;
3202                   by_some = true;
3203                   if (first_s == NULL)
3204                     first_s = edoubleprime;
3205                   else if (!pre_expr_eq (first_s, edoubleprime))
3206                     all_same = false;
3207                 }
3208             }
3209           /* If we can insert it, it's not the same value
3210              already existing along every predecessor, and
3211              it's defined by some predecessor, it is
3212              partially redundant.  */
3213           if (!cant_insert && !all_same && by_some && dbg_cnt (treepre_insert))
3214             {
3215               if (insert_into_preds_of_block (block, get_expression_id (expr),
3216                                               avail))
3217                 new_stuff = true;
3218             }
3219           /* If all edges produce the same value and that value is
3220              an invariant, then the PHI has the same value on all
3221              edges.  Note this.  */
3222           else if (!cant_insert && all_same && eprime
3223                    && (edoubleprime->kind == CONSTANT
3224                        || edoubleprime->kind == NAME)
3225                    && !value_id_constant_p (val))
3226             {
3227               unsigned int j;
3228               bitmap_iterator bi;
3229               bitmap_set_t exprset = VEC_index (bitmap_set_t,
3230                                                 value_expressions, val);
3231
3232               unsigned int new_val = get_expr_value_id (edoubleprime);
3233               FOR_EACH_EXPR_ID_IN_SET (exprset, j, bi)
3234                 {
3235                   pre_expr expr = expression_for_id (j);
3236
3237                   if (expr->kind == NAME)
3238                     {
3239                       vn_ssa_aux_t info = VN_INFO (PRE_EXPR_NAME (expr));
3240                       /* Just reset the value id and valnum so it is
3241                          the same as the constant we have discovered.  */
3242                       if (edoubleprime->kind == CONSTANT)
3243                         {
3244                           info->valnum = PRE_EXPR_CONSTANT (edoubleprime);
3245                           pre_stats.constified++;
3246                         }
3247                       else
3248                         info->valnum = PRE_EXPR_NAME (edoubleprime);
3249                       info->value_id = new_val;
3250                     }
3251                 }
3252             }
3253           free (avail);
3254         }
3255     }
3256
3257   VEC_free (pre_expr, heap, exprs);
3258   return new_stuff;
3259 }
3260
3261
3262 /* Perform insertion for partially anticipatable expressions.  There
3263    is only one case we will perform insertion for these.  This case is
3264    if the expression is partially anticipatable, and fully available.
3265    In this case, we know that putting it earlier will enable us to
3266    remove the later computation.  */
3267
3268
3269 static bool
3270 do_partial_partial_insertion (basic_block block, basic_block dom)
3271 {
3272   bool new_stuff = false;
3273   VEC (pre_expr, heap) *exprs = sorted_array_from_bitmap_set (PA_IN (block));
3274   pre_expr expr;
3275   int i;
3276
3277   for (i = 0; VEC_iterate (pre_expr, exprs, i, expr); i++)
3278     {
3279       if (expr->kind != NAME)
3280         {
3281           pre_expr *avail;
3282           unsigned int val;
3283           bool by_all = true;
3284           bool cant_insert = false;
3285           edge pred;
3286           basic_block bprime;
3287           pre_expr eprime = NULL;
3288           edge_iterator ei;
3289
3290           val = get_expr_value_id (expr);
3291           if (bitmap_set_contains_value (PHI_GEN (block), val))
3292             continue;
3293           if (bitmap_set_contains_value (AVAIL_OUT (dom), val))
3294             continue;
3295
3296           avail = XCNEWVEC (pre_expr, last_basic_block);
3297           FOR_EACH_EDGE (pred, ei, block->preds)
3298             {
3299               unsigned int vprime;
3300               pre_expr edoubleprime;
3301
3302               /* This can happen in the very weird case
3303                  that our fake infinite loop edges have caused a
3304                  critical edge to appear.  */
3305               if (EDGE_CRITICAL_P (pred))
3306                 {
3307                   cant_insert = true;
3308                   break;
3309                 }
3310               bprime = pred->src;
3311               eprime = phi_translate (expr, ANTIC_IN (block),
3312                                       PA_IN (block),
3313                                       bprime, block);
3314
3315               /* eprime will generally only be NULL if the
3316                  value of the expression, translated
3317                  through the PHI for this predecessor, is
3318                  undefined.  If that is the case, we can't
3319                  make the expression fully redundant,
3320                  because its value is undefined along a
3321                  predecessor path.  We can thus break out
3322                  early because it doesn't matter what the
3323                  rest of the results are.  */
3324               if (eprime == NULL)
3325                 {
3326                   cant_insert = true;
3327                   break;
3328                 }
3329
3330               eprime = fully_constant_expression (eprime);
3331               vprime = get_expr_value_id (eprime);
3332               edoubleprime = bitmap_find_leader (AVAIL_OUT (bprime),
3333                                                  vprime, NULL);
3334               if (edoubleprime == NULL)
3335                 {
3336                   by_all = false;
3337                   break;
3338                 }
3339               else
3340                 avail[bprime->index] = edoubleprime;
3341
3342             }
3343
3344           /* If we can insert it, it's not the same value
3345              already existing along every predecessor, and
3346              it's defined by some predecessor, it is
3347              partially redundant.  */
3348           if (!cant_insert && by_all && dbg_cnt (treepre_insert))
3349             {
3350               pre_stats.pa_insert++;
3351               if (insert_into_preds_of_block (block, get_expression_id (expr),
3352                                               avail))
3353                 new_stuff = true;
3354             }
3355           free (avail);
3356         }
3357     }
3358
3359   VEC_free (pre_expr, heap, exprs);
3360   return new_stuff;
3361 }
3362
3363 static bool
3364 insert_aux (basic_block block)
3365 {
3366   basic_block son;
3367   bool new_stuff = false;
3368
3369   if (block)
3370     {
3371       basic_block dom;
3372       dom = get_immediate_dominator (CDI_DOMINATORS, block);
3373       if (dom)
3374         {
3375           unsigned i;
3376           bitmap_iterator bi;
3377           bitmap_set_t newset = NEW_SETS (dom);
3378           if (newset)
3379             {
3380               /* Note that we need to value_replace both NEW_SETS, and
3381                  AVAIL_OUT. For both the case of NEW_SETS, the value may be
3382                  represented by some non-simple expression here that we want
3383                  to replace it with.  */
3384               FOR_EACH_EXPR_ID_IN_SET (newset, i, bi)
3385                 {
3386                   pre_expr expr = expression_for_id (i);
3387                   bitmap_value_replace_in_set (NEW_SETS (block), expr);
3388                   bitmap_value_replace_in_set (AVAIL_OUT (block), expr);
3389                 }
3390             }
3391           if (!single_pred_p (block))
3392             {
3393               new_stuff |= do_regular_insertion (block, dom);
3394               if (do_partial_partial)
3395                 new_stuff |= do_partial_partial_insertion (block, dom);
3396             }
3397         }
3398     }
3399   for (son = first_dom_son (CDI_DOMINATORS, block);
3400        son;
3401        son = next_dom_son (CDI_DOMINATORS, son))
3402     {
3403       new_stuff |= insert_aux (son);
3404     }
3405
3406   return new_stuff;
3407 }
3408
3409 /* Perform insertion of partially redundant values.  */
3410
3411 static void
3412 insert (void)
3413 {
3414   bool new_stuff = true;
3415   basic_block bb;
3416   int num_iterations = 0;
3417
3418   FOR_ALL_BB (bb)
3419     NEW_SETS (bb) = bitmap_set_new ();
3420
3421   while (new_stuff)
3422     {
3423       num_iterations++;
3424       new_stuff = insert_aux (ENTRY_BLOCK_PTR);
3425     }
3426   statistics_histogram_event (cfun, "insert iterations", num_iterations);
3427 }
3428
3429
3430 /* Add OP to EXP_GEN (block), and possibly to the maximal set if it is
3431    not defined by a phi node.
3432    PHI nodes can't go in the maximal sets because they are not in
3433    TMP_GEN, so it is possible to get into non-monotonic situations
3434    during ANTIC calculation, because it will *add* bits.  */
3435
3436 static void
3437 add_to_exp_gen (basic_block block, tree op)
3438 {
3439   if (!in_fre)
3440     {
3441       pre_expr result;