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