OSDN Git Service

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