OSDN Git Service

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