OSDN Git Service

PR tree-optimization/17340
[pf3gnuchains/gcc-fork.git] / gcc / tree-ssa-pre.c
1 /* SSA-PRE for trees.
2    Copyright (C) 2001, 2002, 2003, 2004 Free Software Foundation, Inc.
3    Contributed by Daniel Berlin <dan@dberlin.org> and Steven Bosscher
4    <stevenb@suse.de> 
5
6 This file is part of GCC.
7
8 GCC is free software; you can redistribute it and/or modify
9 it under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 2, or (at your option)
11 any later version.
12
13 GCC is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
16 GNU General Public License for more details.
17
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING.  If not, write to
20 the Free Software Foundation, 59 Temple Place - Suite 330,
21 Boston, MA 02111-1307, USA.  */
22
23 #include "config.h"
24 #include "system.h"
25 #include "coretypes.h"
26 #include "tm.h"
27 #include "errors.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 "tree-pass.h"
43 #include "flags.h"
44 #include "bitmap.h"
45 #include "langhooks.h"
46
47 /* TODO:
48    
49    1. Avail sets can be shared by making an avail_find_leader that
50       walks up the dominator tree and looks in those avail sets.
51       This might affect code optimality, it's unclear right now.
52    2. Load motion can be performed by value numbering the loads the
53       same as we do other expressions.  This requires iterative
54       hashing the vuses into the values.  Right now we simply assign
55       a new value every time we see a statement with a vuse.
56    3. Strength reduction can be performed by anticipating expressions
57       we can repair later on.
58    4. Our canonicalization of expressions during lookups don't take
59       constants into account very well.  In particular, we don't fold
60       anywhere, so we can get situations where we stupidly think
61       something is a new value (a + 1 + 1 vs a + 2).  This is somewhat
62       expensive to fix, but it does expose a lot more eliminations.
63       It may or not be worth it, depending on how critical you
64       consider PRE vs just plain GRE.
65 */   
66
67 /* For ease of terminology, "expression node" in the below refers to
68    every expression node but MODIFY_EXPR, because MODIFY_EXPR's represent
69    the actual statement containing the expressions we care about, and
70    we cache the value number by putting it in the expression.  */
71
72 /* Basic algorithm
73    
74    First we walk the statements to generate the AVAIL sets, the
75    EXP_GEN sets, and the tmp_gen sets.  EXP_GEN sets represent the
76    generation of values/expressions by a given block.  We use them
77    when computing the ANTIC sets.  The AVAIL sets consist of
78    SSA_NAME's that represent values, so we know what values are
79    available in what blocks.  AVAIL is a forward dataflow problem.  In
80    SSA, values are never killed, so we don't need a kill set, or a
81    fixpoint iteration, in order to calculate the AVAIL sets.  In
82    traditional parlance, AVAIL sets tell us the downsafety of the
83    expressions/values.
84    
85    Next, we generate the ANTIC sets.  These sets represent the
86    anticipatable expressions.  ANTIC is a backwards dataflow
87    problem.An expression is anticipatable in a given block if it could
88    be generated in that block.  This means that if we had to perform
89    an insertion in that block, of the value of that expression, we
90    could.  Calculating the ANTIC sets requires phi translation of
91    expressions, because the flow goes backwards through phis.  We must
92    iterate to a fixpoint of the ANTIC sets, because we have a kill
93    set.  Even in SSA form, values are not live over the entire
94    function, only from their definition point onwards.  So we have to
95    remove values from the ANTIC set once we go past the definition
96    point of the leaders that make them up.
97    compute_antic/compute_antic_aux performs this computation.
98
99    Third, we perform insertions to make partially redundant
100    expressions fully redundant.
101
102    An expression is partially redundant (excluding partial
103    anticipation) if:
104
105    1. It is AVAIL in some, but not all, of the predecessors of a
106       given block.
107    2. It is ANTIC in all the predecessors.
108
109    In order to make it fully redundant, we insert the expression into
110    the predecessors where it is not available, but is ANTIC.
111    insert/insert_aux performs this insertion.
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 VAR_DECL named "value.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 "value.3 *
131    value.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 "value.5 + value.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 /* A value set element.  Basically a single linked list of
186    expressions/values.  */
187 typedef struct value_set_node
188 {
189   /* An expression.  */
190   tree expr;
191
192   /* A pointer to the next element of the value set.  */
193   struct value_set_node *next;
194 } *value_set_node_t;
195
196
197 /* A value set.  This is a singly linked list of value_set_node
198    elements with a possible bitmap that tells us what values exist in
199    the set.  This set must be kept in topologically sorted order.  */
200 typedef struct value_set
201 {
202   /* The head of the list.  Used for iterating over the list in
203      order.  */
204   value_set_node_t head;
205
206   /* The tail of the list.  Used for tail insertions, which are
207      necessary to keep the set in topologically sorted order because
208      of how the set is built.  */
209   value_set_node_t tail;
210   
211   /* The length of the list.  */
212   size_t length;
213   
214   /* True if the set is indexed, which means it contains a backing
215      bitmap for quick determination of whether certain values exist in the
216      set.  */
217   bool indexed;
218   
219   /* The bitmap of values that exist in the set.  May be NULL in an
220      empty or non-indexed set.  */
221   bitmap values;
222   
223 } *value_set_t;
224
225
226 /* An unordered bitmap set.  One bitmap tracks values, the other,
227    expressions.  */
228 typedef struct bitmap_set
229 {
230   bitmap expressions;
231   bitmap values;
232 } *bitmap_set_t;
233
234 /* Sets that we need to keep track of.  */
235 typedef struct bb_value_sets
236 {
237   /* The EXP_GEN set, which represents expressions/values generated in
238      a basic block.  */
239   value_set_t exp_gen;
240
241   /* The PHI_GEN set, which represents PHI results generated in a
242      basic block.  */
243   bitmap_set_t phi_gen;
244
245   /* The TMP_GEN set, which represents results/temporaries generated
246      in a basic block. IE the LHS of an expression.  */
247   bitmap_set_t tmp_gen;
248
249   /* The AVAIL_OUT set, which represents which values are available in
250      a given basic block.  */
251   bitmap_set_t avail_out;
252
253   /* The ANTIC_IN set, which represents which values are anticiptable
254      in a given basic block.  */
255   value_set_t antic_in;
256
257   /* The NEW_SETS set, which is used during insertion to augment the
258      AVAIL_OUT set of blocks with the new insertions performed during
259      the current iteration.  */
260   bitmap_set_t new_sets;
261 } *bb_value_sets_t;
262
263 #define EXP_GEN(BB)     ((bb_value_sets_t) ((BB)->aux))->exp_gen
264 #define PHI_GEN(BB)     ((bb_value_sets_t) ((BB)->aux))->phi_gen
265 #define TMP_GEN(BB)     ((bb_value_sets_t) ((BB)->aux))->tmp_gen
266 #define AVAIL_OUT(BB)   ((bb_value_sets_t) ((BB)->aux))->avail_out
267 #define ANTIC_IN(BB)    ((bb_value_sets_t) ((BB)->aux))->antic_in
268 #define NEW_SETS(BB)    ((bb_value_sets_t) ((BB)->aux))->new_sets
269
270 /* This structure is used to keep track of statistics on what
271    optimization PRE was able to perform.  */
272 static struct
273 {
274   /* The number of RHS computations eliminated by PRE.  */
275   int eliminations;
276
277   /* The number of new expressions/temporaries generated by PRE.  */
278   int insertions;
279
280   /* The number of new PHI nodes added by PRE.  */
281   int phis;
282 } pre_stats;
283
284
285 static tree bitmap_find_leader (bitmap_set_t, tree);
286 static tree find_leader (value_set_t, tree);
287 static void value_insert_into_set (value_set_t, tree);
288 static void bitmap_value_insert_into_set (bitmap_set_t, tree);
289 static void bitmap_value_replace_in_set (bitmap_set_t, tree);
290 static void insert_into_set (value_set_t, tree);
291 static void bitmap_set_copy (bitmap_set_t, bitmap_set_t);
292 static bool bitmap_set_contains_value (bitmap_set_t, tree);
293 static bitmap_set_t bitmap_set_new (void);
294 static value_set_t set_new  (bool);
295 static bool is_undefined_value (tree);
296 static tree create_expression_by_pieces (basic_block, tree, tree);
297
298
299 /* We can add and remove elements and entries to and from sets
300    and hash tables, so we use alloc pools for them.  */
301
302 static alloc_pool value_set_pool;
303 static alloc_pool bitmap_set_pool;
304 static alloc_pool value_set_node_pool;
305 static alloc_pool binary_node_pool;
306 static alloc_pool unary_node_pool;
307 static alloc_pool reference_node_pool;
308 static bitmap_obstack grand_bitmap_obstack;
309
310 /* Set of blocks with statements that have had its EH information
311    cleaned up.  */
312 static bitmap need_eh_cleanup;
313
314 /* The phi_translate_table caches phi translations for a given
315    expression and predecessor.  */
316
317 static htab_t phi_translate_table;
318
319 /* A three tuple {e, pred, v} used to cache phi translations in the
320    phi_translate_table.  */
321
322 typedef struct expr_pred_trans_d
323 {
324   /* The expression.  */
325   tree e;
326
327   /* The predecessor block along which we translated the expression.  */
328   basic_block pred;
329
330   /* The value that resulted from the translation.  */
331   tree v;
332
333   /* The hashcode for the expression, pred pair. This is cached for
334      speed reasons.  */
335   hashval_t hashcode;
336 } *expr_pred_trans_t;
337
338 /* Return the hash value for a phi translation table entry.  */
339
340 static hashval_t
341 expr_pred_trans_hash (const void *p)
342 {
343   const expr_pred_trans_t ve = (expr_pred_trans_t) p;
344   return ve->hashcode;
345 }
346
347 /* Return true if two phi translation table entries are the same.
348    P1 and P2 should point to the expr_pred_trans_t's to be compared.*/
349
350 static int
351 expr_pred_trans_eq (const void *p1, const void *p2)
352 {
353   const expr_pred_trans_t ve1 = (expr_pred_trans_t) p1;
354   const expr_pred_trans_t ve2 = (expr_pred_trans_t) p2;
355   basic_block b1 = ve1->pred;
356   basic_block b2 = ve2->pred;
357
358   
359   /* If they are not translations for the same basic block, they can't
360      be equal.  */
361   if (b1 != b2)
362     return false;
363
364   /* If they are for the same basic block, determine if the
365      expressions are equal.  */  
366   if (expressions_equal_p (ve1->e, ve2->e))
367     return true;
368   
369   return false;
370 }
371
372 /* Search in the phi translation table for the translation of
373    expression E in basic block PRED. Return the translated value, if
374    found, NULL otherwise.  */ 
375
376 static inline tree
377 phi_trans_lookup (tree e, basic_block pred)
378 {
379   void **slot;
380   struct expr_pred_trans_d ept;
381   ept.e = e;
382   ept.pred = pred;
383   ept.hashcode = vn_compute (e, (unsigned long) pred, NULL);
384   slot = htab_find_slot_with_hash (phi_translate_table, &ept, ept.hashcode,
385                                    NO_INSERT);
386   if (!slot)
387     return NULL;
388   else
389     return ((expr_pred_trans_t) *slot)->v;
390 }
391
392
393 /* Add the tuple mapping from {expression E, basic block PRED} to
394    value V, to the phi translation table.  */
395
396 static inline void
397 phi_trans_add (tree e, tree v, basic_block pred)
398 {
399   void **slot;
400   expr_pred_trans_t new_pair = xmalloc (sizeof (*new_pair));
401   new_pair->e = e;
402   new_pair->pred = pred;
403   new_pair->v = v;
404   new_pair->hashcode = vn_compute (e, (unsigned long) pred, NULL);
405   slot = htab_find_slot_with_hash (phi_translate_table, new_pair,
406                                    new_pair->hashcode, INSERT);
407   if (*slot)
408     free (*slot);
409   *slot = (void *) new_pair;
410 }
411
412
413 /* Add expression E to the expression set of value V.  */
414
415 void
416 add_to_value (tree v, tree e)
417 {
418   /* Constants have no expression sets.  */
419   if (is_gimple_min_invariant (v))
420     return;
421
422   if (VALUE_HANDLE_EXPR_SET (v) == NULL)
423     VALUE_HANDLE_EXPR_SET (v) = set_new (false);
424
425   insert_into_set (VALUE_HANDLE_EXPR_SET (v), e);
426 }
427
428
429 /* Return true if value V exists in the bitmap for SET.  */
430
431 static inline bool
432 value_exists_in_set_bitmap (value_set_t set, tree v)
433 {
434   if (!set->values)
435     return false;
436
437   return bitmap_bit_p (set->values, VALUE_HANDLE_ID (v));
438 }
439
440
441 /* Remove value V from the bitmap for SET.  */
442
443 static void
444 value_remove_from_set_bitmap (value_set_t set, tree v)
445 {
446   gcc_assert (set->indexed);
447
448   if (!set->values)
449     return;
450
451   bitmap_clear_bit (set->values, VALUE_HANDLE_ID (v));
452 }
453
454
455 /* Insert the value number V into the bitmap of values existing in
456    SET.  */
457
458 static inline void
459 value_insert_into_set_bitmap (value_set_t set, tree v)
460 {
461   gcc_assert (set->indexed);
462
463   if (set->values == NULL)
464     set->values = BITMAP_ALLOC (&grand_bitmap_obstack);
465
466   bitmap_set_bit (set->values, VALUE_HANDLE_ID (v));
467 }
468
469
470 /* Create a new bitmap set and return it.  */
471
472 static bitmap_set_t 
473 bitmap_set_new (void)
474 {
475   bitmap_set_t ret = pool_alloc (bitmap_set_pool);
476   ret->expressions = BITMAP_ALLOC (&grand_bitmap_obstack);
477   ret->values = BITMAP_ALLOC (&grand_bitmap_obstack);
478   return ret;
479 }
480
481 /* Create a new set.  */
482
483 static value_set_t
484 set_new  (bool indexed)
485 {
486   value_set_t ret;
487   ret = pool_alloc (value_set_pool);
488   ret->head = ret->tail = NULL;
489   ret->length = 0;
490   ret->indexed = indexed;
491   ret->values = NULL;
492   return ret;
493 }
494
495 /* Insert an expression EXPR into a bitmapped set.  */
496
497 static void
498 bitmap_insert_into_set (bitmap_set_t set, tree expr)
499 {
500   tree val;
501   /* XXX: For now, we only let SSA_NAMES into the bitmap sets.  */
502   gcc_assert (TREE_CODE (expr) == SSA_NAME);
503   val = get_value_handle (expr);
504   
505   gcc_assert (val);
506   if (!is_gimple_min_invariant (val))
507   {
508     bitmap_set_bit (set->values, VALUE_HANDLE_ID (val));
509     bitmap_set_bit (set->expressions, SSA_NAME_VERSION (expr));
510   }
511 }
512
513 /* Insert EXPR into SET.  */
514
515 static void
516 insert_into_set (value_set_t set, tree expr)
517 {
518   value_set_node_t newnode = pool_alloc (value_set_node_pool);
519   tree val = get_value_handle (expr);
520   gcc_assert (val);
521   
522   if (is_gimple_min_invariant (val))
523     return;
524
525   /* For indexed sets, insert the value into the set value bitmap.
526      For all sets, add it to the linked list and increment the list
527      length.  */
528   if (set->indexed)
529     value_insert_into_set_bitmap (set, val);
530
531   newnode->next = NULL;
532   newnode->expr = expr;
533   set->length ++;
534   if (set->head == NULL)
535     {
536       set->head = set->tail = newnode;
537     }
538   else
539     {
540       set->tail->next = newnode;
541       set->tail = newnode;
542     }
543 }
544
545 /* Copy a bitmapped set ORIG, into bitmapped set DEST.  */
546
547 static void
548 bitmap_set_copy (bitmap_set_t dest, bitmap_set_t orig)
549 {
550   bitmap_copy (dest->expressions, orig->expressions);
551   bitmap_copy (dest->values, orig->values);
552 }
553
554 /* Copy the set ORIG to the set DEST.  */
555
556 static void
557 set_copy (value_set_t dest, value_set_t orig)
558 {
559   value_set_node_t node;
560  
561   if (!orig || !orig->head)
562     return;
563
564   for (node = orig->head;
565        node;
566        node = node->next)
567     {
568       insert_into_set (dest, node->expr);
569     }
570 }
571
572 /* Remove EXPR from SET.  */
573
574 static void
575 set_remove (value_set_t set, tree expr)
576 {
577   value_set_node_t node, prev;
578
579   /* Remove the value of EXPR from the bitmap, decrement the set
580      length, and remove it from the actual double linked list.  */ 
581   value_remove_from_set_bitmap (set, get_value_handle (expr));
582   set->length--;
583   prev = NULL;
584   for (node = set->head; 
585        node != NULL; 
586        prev = node, node = node->next)
587     {
588       if (node->expr == expr)
589         {
590           if (prev == NULL)
591             set->head = node->next;
592           else
593             prev->next= node->next;
594  
595           if (node == set->tail)
596             set->tail = prev;
597           pool_free (value_set_node_pool, node);
598           return;
599         }
600     }
601 }
602
603 /* Return true if SET contains the value VAL.  */
604
605 static bool
606 set_contains_value (value_set_t set, tree val)
607 {
608   /* All constants are in every set.  */
609   if (is_gimple_min_invariant (val))
610     return true;
611   
612   if (set->length == 0)
613     return false;
614   
615   return value_exists_in_set_bitmap (set, val);
616 }
617
618 /* Return true if bitmapped set SET contains the expression EXPR.  */
619 static bool
620 bitmap_set_contains (bitmap_set_t set, tree expr)
621 {
622   /* All constants are in every set.  */
623   if (is_gimple_min_invariant (get_value_handle (expr)))
624     return true;
625
626   /* XXX: Bitmapped sets only contain SSA_NAME's for now.  */
627   if (TREE_CODE (expr) != SSA_NAME)
628     return false;
629   return bitmap_bit_p (set->expressions, SSA_NAME_VERSION (expr));
630 }
631
632   
633 /* Return true if bitmapped set SET contains the value VAL.  */
634
635 static bool
636 bitmap_set_contains_value (bitmap_set_t set, tree val)
637 {
638   if (is_gimple_min_invariant (val))
639     return true;
640   return bitmap_bit_p (set->values, VALUE_HANDLE_ID (val));
641 }
642
643 /* Replace an instance of value LOOKFOR with expression EXPR in SET.  */
644
645 static void
646 bitmap_set_replace_value (bitmap_set_t set, tree lookfor, tree expr)
647 {
648   value_set_t exprset;
649   value_set_node_t node;
650   if (is_gimple_min_invariant (lookfor))
651     return;
652   if (!bitmap_set_contains_value (set, lookfor))
653     return;
654
655   /* The number of expressions having a given value is usually
656      significantly less than the total number of expressions in SET.
657      Thus, rather than check, for each expression in SET, whether it
658      has the value LOOKFOR, we walk the reverse mapping that tells us
659      what expressions have a given value, and see if any of those
660      expressions are in our set.  For large testcases, this is about
661      5-10x faster than walking the bitmap.  If this is somehow a
662      significant lose for some cases, we can choose which set to walk
663      based on the set size.  */
664   exprset = VALUE_HANDLE_EXPR_SET (lookfor);
665   for (node = exprset->head; node; node = node->next)
666     {
667       if (TREE_CODE (node->expr) == SSA_NAME)
668         {
669           if (bitmap_bit_p (set->expressions, SSA_NAME_VERSION (node->expr)))
670             {
671               bitmap_clear_bit (set->expressions, SSA_NAME_VERSION (node->expr));
672               bitmap_set_bit (set->expressions, SSA_NAME_VERSION (expr));
673               return;
674             }
675         }
676     }
677 }
678
679 /* Subtract bitmapped set B from value set A, and return the new set.  */
680
681 static value_set_t
682 bitmap_set_subtract_from_value_set (value_set_t a, bitmap_set_t b,
683                                     bool indexed)
684 {
685   value_set_t ret = set_new (indexed);
686   value_set_node_t node;
687   for (node = a->head;
688        node;
689        node = node->next)
690     {
691       if (!bitmap_set_contains (b, node->expr))
692         insert_into_set (ret, node->expr);
693     }
694   return ret;
695 }
696
697 /* Return true if two sets are equal.  */
698
699 static bool
700 set_equal (value_set_t a, value_set_t b)
701 {
702   value_set_node_t node;
703
704   if (a->length != b->length)
705     return false;
706   for (node = a->head;
707        node;
708        node = node->next)
709     {
710       if (!set_contains_value (b, get_value_handle (node->expr)))
711         return false;
712     }
713   return true;
714 }
715
716 /* Replace an instance of EXPR's VALUE with EXPR in SET if it exists,
717    and add it otherwise. */
718
719 static void
720 bitmap_value_replace_in_set (bitmap_set_t set, tree expr)
721 {
722   tree val = get_value_handle (expr);
723   if (bitmap_set_contains_value (set, val))
724     bitmap_set_replace_value (set, val, expr);
725   else
726     bitmap_insert_into_set (set, expr);
727 }
728
729 /* Insert EXPR into SET if EXPR's value is not already present in
730    SET.  */
731
732 static void
733 bitmap_value_insert_into_set (bitmap_set_t set, tree expr)
734 {
735   tree val = get_value_handle (expr);
736
737   if (is_gimple_min_invariant (val))
738     return;
739   
740   if (!bitmap_set_contains_value (set, val))
741     bitmap_insert_into_set (set, expr);
742 }
743
744 /* Insert the value for EXPR into SET, if it doesn't exist already.  */
745
746 static void
747 value_insert_into_set (value_set_t set, tree expr)
748 {
749   tree val = get_value_handle (expr);
750
751   /* Constant and invariant values exist everywhere, and thus,
752      actually keeping them in the sets is pointless.  */
753   if (is_gimple_min_invariant (val))
754     return;
755
756   if (!set_contains_value (set, val))
757     insert_into_set (set, expr);
758 }
759
760
761 /* Print out SET to OUTFILE.  */
762
763 static void
764 bitmap_print_value_set (FILE *outfile, bitmap_set_t set,
765                         const char *setname, int blockindex)
766 {
767   fprintf (outfile, "%s[%d] := { ", setname, blockindex);
768   if (set)
769     {
770       bool first = true;
771       unsigned i;
772       bitmap_iterator bi;
773
774       EXECUTE_IF_SET_IN_BITMAP (set->expressions, 0, i, bi)
775         {
776           if (!first)
777             fprintf (outfile, ", ");
778           first = false;
779           print_generic_expr (outfile, ssa_name (i), 0);
780         
781           fprintf (outfile, " (");
782           print_generic_expr (outfile, get_value_handle (ssa_name (i)), 0);
783           fprintf (outfile, ") ");
784         }
785     }
786   fprintf (outfile, " }\n");
787 }
788 /* Print out the value_set SET to OUTFILE.  */
789
790 static void
791 print_value_set (FILE *outfile, value_set_t set,
792                  const char *setname, int blockindex)
793 {
794   value_set_node_t node;
795   fprintf (outfile, "%s[%d] := { ", setname, blockindex);
796   if (set)
797     {
798       for (node = set->head;
799            node;
800            node = node->next)
801         {
802           print_generic_expr (outfile, node->expr, 0);
803           
804           fprintf (outfile, " (");
805           print_generic_expr (outfile, get_value_handle (node->expr), 0);
806           fprintf (outfile, ") ");
807                      
808           if (node->next)
809             fprintf (outfile, ", ");
810         }
811     }
812
813   fprintf (outfile, " }\n");
814 }
815
816 /* Print out the expressions that have VAL to OUTFILE.  */
817
818 void
819 print_value_expressions (FILE *outfile, tree val)
820 {
821   if (VALUE_HANDLE_EXPR_SET (val))
822     {
823       char s[10];
824       sprintf (s, "VH.%04d", VALUE_HANDLE_ID (val));
825       print_value_set (outfile, VALUE_HANDLE_EXPR_SET (val), s, 0);
826     }
827 }
828
829
830 void
831 debug_value_expressions (tree val)
832 {
833   print_value_expressions (stderr, val);
834 }
835
836   
837 void debug_value_set (value_set_t, const char *, int);
838
839 void
840 debug_value_set (value_set_t set, const char *setname, int blockindex)
841 {
842   print_value_set (stderr, set, setname, blockindex);
843 }
844
845 /* Translate EXPR using phis in PHIBLOCK, so that it has the values of
846    the phis in PRED.  Return NULL if we can't find a leader for each
847    part of the translated expression.  */
848
849 static tree
850 phi_translate (tree expr, value_set_t set, basic_block pred,
851                basic_block phiblock)
852 {
853   tree phitrans = NULL;
854   tree oldexpr = expr;
855   
856   if (expr == NULL)
857     return NULL;
858
859   if (is_gimple_min_invariant (expr))
860     return expr;
861
862   /* Phi translations of a given expression don't change.  */
863   phitrans = phi_trans_lookup (expr, pred);
864   if (phitrans)
865     return phitrans;
866   
867   switch (TREE_CODE_CLASS (TREE_CODE (expr)))
868     {
869     case tcc_reference:
870       /* XXX: Until we have PRE of loads working, none will be ANTIC.  */
871       return NULL;
872
873     case tcc_binary:
874       {
875         tree oldop1 = TREE_OPERAND (expr, 0);
876         tree oldop2 = TREE_OPERAND (expr, 1);
877         tree newop1;
878         tree newop2;
879         tree newexpr;
880         
881         newop1 = phi_translate (find_leader (set, oldop1),
882                                 set, pred, phiblock);
883         if (newop1 == NULL)
884           return NULL;
885         newop2 = phi_translate (find_leader (set, oldop2),
886                                 set, pred, phiblock);
887         if (newop2 == NULL)
888           return NULL;
889         if (newop1 != oldop1 || newop2 != oldop2)
890           {
891             newexpr = pool_alloc (binary_node_pool);
892             memcpy (newexpr, expr, tree_size (expr));
893             create_tree_ann (newexpr);
894             TREE_OPERAND (newexpr, 0) = newop1 == oldop1 ? oldop1 : get_value_handle (newop1);
895             TREE_OPERAND (newexpr, 1) = newop2 == oldop2 ? oldop2 : get_value_handle (newop2);
896             vn_lookup_or_add (newexpr, NULL);
897             expr = newexpr;
898             phi_trans_add (oldexpr, newexpr, pred);         
899           }
900       }
901       return expr;
902
903     case tcc_unary:
904       {
905         tree oldop1 = TREE_OPERAND (expr, 0);
906         tree newop1;
907         tree newexpr;
908
909         newop1 = phi_translate (find_leader (set, oldop1),
910                                 set, pred, phiblock);
911         if (newop1 == NULL)
912           return NULL;
913         if (newop1 != oldop1)
914           {
915             newexpr = pool_alloc (unary_node_pool);
916             memcpy (newexpr, expr, tree_size (expr));
917             create_tree_ann (newexpr);   
918             TREE_OPERAND (newexpr, 0) = get_value_handle (newop1);
919             vn_lookup_or_add (newexpr, NULL);
920             expr = newexpr;
921             phi_trans_add (oldexpr, newexpr, pred);
922           }
923       }
924       return expr;
925
926     case tcc_exceptional:
927       {
928         tree phi = NULL;
929         edge e;
930         gcc_assert (TREE_CODE (expr) == SSA_NAME);
931         if (TREE_CODE (SSA_NAME_DEF_STMT (expr)) == PHI_NODE)
932           phi = SSA_NAME_DEF_STMT (expr);
933         else
934           return expr;
935         
936         e = find_edge (pred, bb_for_stmt (phi));
937         if (e)
938           {
939             if (is_undefined_value (PHI_ARG_DEF (phi, e->dest_idx)))
940               return NULL;
941             vn_lookup_or_add (PHI_ARG_DEF (phi, e->dest_idx), NULL);
942             return PHI_ARG_DEF (phi, e->dest_idx);
943           }
944       }
945       return expr;
946
947     default:
948       gcc_unreachable ();
949     }
950 }
951
952 static void
953 phi_translate_set (value_set_t dest, value_set_t set, basic_block pred,
954                    basic_block phiblock)
955 {
956   value_set_node_t node;
957   for (node = set->head;
958        node;
959        node = node->next)
960     {
961       tree translated;
962       translated = phi_translate (node->expr, set, pred, phiblock);
963       phi_trans_add (node->expr, translated, pred);
964       
965       if (translated != NULL)
966         value_insert_into_set (dest, translated);
967     } 
968 }
969
970 /* Find the leader for a value (i.e., the name representing that
971    value) in a given set, and return it.  Return NULL if no leader is
972    found.  */
973
974 static tree
975 bitmap_find_leader (bitmap_set_t set, tree val)
976 {
977   if (val == NULL)
978     return NULL;
979   
980   if (is_gimple_min_invariant (val))
981     return val;
982   if (bitmap_set_contains_value (set, val))
983     {
984       /* Rather than walk the entire bitmap of expressions, and see
985          whether any of them has the value we are looking for, we look
986          at the reverse mapping, which tells us the set of expressions
987          that have a given value (IE value->expressions with that
988          value) and see if any of those expressions are in our set.
989          The number of expressions per value is usually significantly
990          less than the number of expressions in the set.  In fact, for
991          large testcases, doing it this way is roughly 5-10x faster
992          than walking the bitmap.
993          If this is somehow a significant lose for some cases, we can
994          choose which set to walk based on which set is smaller.  */     
995       value_set_t exprset;
996       value_set_node_t node;
997       exprset = VALUE_HANDLE_EXPR_SET (val);
998       for (node = exprset->head; node; node = node->next)
999         {
1000           if (TREE_CODE (node->expr) == SSA_NAME)
1001             {
1002               if (bitmap_bit_p (set->expressions, 
1003                                 SSA_NAME_VERSION (node->expr)))
1004                 return node->expr;
1005             }
1006         }
1007     }
1008   return NULL;
1009 }
1010
1011         
1012 /* Find the leader for a value (i.e., the name representing that
1013    value) in a given set, and return it.  Return NULL if no leader is
1014    found.  */
1015
1016 static tree
1017 find_leader (value_set_t set, tree val)
1018 {
1019   value_set_node_t node;
1020
1021   if (val == NULL)
1022     return NULL;
1023
1024   /* Constants represent themselves.  */
1025   if (is_gimple_min_invariant (val))
1026     return val;
1027
1028   if (set->length == 0)
1029     return NULL;
1030   
1031   if (value_exists_in_set_bitmap (set, val))
1032     {
1033       for (node = set->head;
1034            node;
1035            node = node->next)
1036         {
1037           if (get_value_handle (node->expr) == val)
1038             return node->expr;
1039         }
1040     }
1041
1042   return NULL;
1043 }
1044
1045 /* Determine if the expression EXPR is valid in SET.  This means that
1046    we have a leader for each part of the expression (if it consists of
1047    values), or the expression is an SSA_NAME.  
1048
1049    NB:  We never should run into a case where we have SSA_NAME +
1050    SSA_NAME or SSA_NAME + value.  The sets valid_in_set is called on,
1051    the ANTIC sets, will only ever have SSA_NAME's or binary value
1052    expression (IE VALUE1 + VALUE2)  */
1053
1054 static bool
1055 valid_in_set (value_set_t set, tree expr)
1056 {
1057   switch (TREE_CODE_CLASS (TREE_CODE (expr)))
1058     {
1059     case tcc_binary:
1060       {
1061         tree op1 = TREE_OPERAND (expr, 0);
1062         tree op2 = TREE_OPERAND (expr, 1);
1063         return set_contains_value (set, op1) && set_contains_value (set, op2);
1064       }
1065
1066     case tcc_unary:
1067       {
1068         tree op1 = TREE_OPERAND (expr, 0);
1069         return set_contains_value (set, op1);
1070       }
1071
1072     case tcc_reference:
1073       /* XXX: Until PRE of loads works, no reference nodes are ANTIC.  */
1074       return false;
1075
1076     case tcc_exceptional:
1077       gcc_assert (TREE_CODE (expr) == SSA_NAME);
1078       return true;
1079
1080     default:
1081       /* No other cases should be encountered.  */
1082       gcc_unreachable (); 
1083    }
1084 }
1085
1086 /* Clean the set of expressions that are no longer valid in SET.  This
1087    means expressions that are made up of values we have no leaders for
1088    in SET.  */
1089
1090 static void
1091 clean (value_set_t set)
1092 {
1093   value_set_node_t node;
1094   value_set_node_t next;
1095   node = set->head;
1096   while (node)
1097     {
1098       next = node->next;
1099       if (!valid_in_set (set, node->expr))      
1100         set_remove (set, node->expr);
1101       node = next;
1102     }
1103 }
1104
1105 DEF_VEC_MALLOC_P (basic_block);
1106
1107 /* Compute the ANTIC set for BLOCK.
1108
1109    If succs(BLOCK) > 1 then
1110      ANTIC_OUT[BLOCK] = intersection of ANTIC_IN[b] for all succ(BLOCK)
1111    else if succs(BLOCK) == 1 then
1112      ANTIC_OUT[BLOCK] = phi_translate (ANTIC_IN[succ(BLOCK)])
1113
1114    ANTIC_IN[BLOCK] = clean(ANTIC_OUT[BLOCK] U EXP_GEN[BLOCK] - TMP_GEN[BLOCK])
1115
1116    Iterate until fixpointed.
1117
1118    XXX: It would be nice to either write a set_clear, and use it for
1119    ANTIC_OUT, or to mark the antic_out set as deleted at the end
1120    of this routine, so that the pool can hand the same memory back out
1121    again for the next ANTIC_OUT.  */
1122
1123
1124 static bool
1125 compute_antic_aux (basic_block block)
1126 {
1127   basic_block son;
1128   edge e;
1129   bool changed = false;
1130   value_set_t S, old, ANTIC_OUT;
1131   value_set_node_t node;
1132   
1133   ANTIC_OUT = S = NULL;
1134   /* If any edges from predecessors are abnormal, antic_in is empty, so
1135      punt.  Remember that the block has an incoming abnormal edge by
1136      setting the BB_VISITED flag.  */
1137   if (! (block->flags & BB_VISITED))
1138     {
1139       edge_iterator ei;
1140       FOR_EACH_EDGE (e, ei, block->preds)
1141         if (e->flags & EDGE_ABNORMAL)
1142           {
1143             block->flags |= BB_VISITED;
1144             break;
1145           }
1146     }
1147   if (block->flags & BB_VISITED)
1148     {
1149       S = NULL;
1150       goto visit_sons;
1151     }
1152   
1153
1154   old = set_new (false);
1155   set_copy (old, ANTIC_IN (block));
1156   ANTIC_OUT = set_new (true);
1157
1158   /* If the block has no successors, ANTIC_OUT is empty, because it is
1159      the exit block.  */
1160   if (EDGE_COUNT (block->succs) == 0);
1161
1162   /* If we have one successor, we could have some phi nodes to
1163      translate through.  */
1164   else if (EDGE_COUNT (block->succs) == 1)
1165     {
1166       phi_translate_set (ANTIC_OUT, ANTIC_IN(EDGE_SUCC (block, 0)->dest),
1167                          block, EDGE_SUCC (block, 0)->dest);
1168     }
1169   /* If we have multiple successors, we take the intersection of all of
1170      them.  */
1171   else
1172     {
1173       VEC (basic_block) * worklist;
1174       edge e;
1175       size_t i;
1176       basic_block bprime, first;
1177       edge_iterator ei;
1178
1179       worklist = VEC_alloc (basic_block, 2);
1180       FOR_EACH_EDGE (e, ei, block->succs)
1181         VEC_safe_push (basic_block, worklist, e->dest);
1182       first = VEC_index (basic_block, worklist, 0);
1183       set_copy (ANTIC_OUT, ANTIC_IN (first));
1184
1185       for (i = 1; VEC_iterate (basic_block, worklist, i, bprime); i++)
1186         {
1187           node = ANTIC_OUT->head;
1188           while (node)
1189             {
1190               tree val;
1191               value_set_node_t next = node->next;
1192               val = get_value_handle (node->expr);
1193               if (!set_contains_value (ANTIC_IN (bprime), val))
1194                 set_remove (ANTIC_OUT, node->expr);
1195               node = next;
1196             }
1197         }
1198       VEC_free (basic_block, worklist);
1199     }
1200
1201   /* Generate ANTIC_OUT - TMP_GEN.  */
1202   S = bitmap_set_subtract_from_value_set (ANTIC_OUT, TMP_GEN (block), false);
1203
1204   /* Start ANTIC_IN with EXP_GEN - TMP_GEN */
1205   ANTIC_IN (block) = bitmap_set_subtract_from_value_set (EXP_GEN (block), 
1206                                                          TMP_GEN (block),
1207                                                          true);
1208   
1209   /* Then union in the ANTIC_OUT - TMP_GEN values, to get ANTIC_OUT U
1210      EXP_GEN - TMP_GEN */
1211   for (node = S->head;
1212        node;
1213        node = node->next)
1214     {
1215       value_insert_into_set (ANTIC_IN (block), node->expr);
1216     }
1217   clean (ANTIC_IN (block));
1218   
1219
1220   if (!set_equal (old, ANTIC_IN (block)))
1221     changed = true;
1222
1223  visit_sons:
1224   if (dump_file && (dump_flags & TDF_DETAILS))
1225     {
1226       if (ANTIC_OUT)
1227         print_value_set (dump_file, ANTIC_OUT, "ANTIC_OUT", block->index);
1228       print_value_set (dump_file, ANTIC_IN (block), "ANTIC_IN", block->index);
1229       if (S)
1230         print_value_set (dump_file, S, "S", block->index);
1231
1232     }
1233
1234   for (son = first_dom_son (CDI_POST_DOMINATORS, block);
1235        son;
1236        son = next_dom_son (CDI_POST_DOMINATORS, son))
1237     {
1238       changed |= compute_antic_aux (son);
1239     }
1240   return changed;
1241 }
1242
1243 /* Compute ANTIC sets.  */
1244
1245 static void
1246 compute_antic (void)
1247 {
1248   bool changed = true;
1249   basic_block bb;
1250   int num_iterations = 0;
1251   FOR_ALL_BB (bb)
1252     {
1253       ANTIC_IN (bb) = set_new (true);
1254       gcc_assert (!(bb->flags & BB_VISITED));
1255     }
1256
1257   while (changed)
1258     {
1259       num_iterations++;
1260       changed = false;
1261       changed = compute_antic_aux (EXIT_BLOCK_PTR);
1262     }
1263   FOR_ALL_BB (bb)
1264     {
1265       bb->flags &= ~BB_VISITED;
1266     }
1267   if (num_iterations > 2 && dump_file && (dump_flags & TDF_STATS))
1268     fprintf (dump_file, "compute_antic required %d iterations\n", num_iterations);
1269 }
1270
1271
1272 /* Find a leader for an expression, or generate one using
1273    create_expression_by_pieces if it's ANTIC but
1274    complex.  
1275    BLOCK is the basic_block we are looking for leaders in.
1276    EXPR is the expression to find a leader or generate for. 
1277    STMTS is the statement list to put the inserted expressions on.
1278    Returns the SSA_NAME of the LHS of the generated expression or the
1279    leader.  */
1280
1281 static tree
1282 find_or_generate_expression (basic_block block, tree expr, tree stmts)
1283 {
1284   tree genop = bitmap_find_leader (AVAIL_OUT (block), expr);
1285
1286   /* If it's still NULL, see if it is a complex expression, and if
1287      so, generate it recursively, otherwise, abort, because it's
1288      not really .  */
1289   if (genop == NULL)
1290     {
1291       genop = VALUE_HANDLE_EXPR_SET (expr)->head->expr;
1292       gcc_assert (UNARY_CLASS_P (genop)
1293                   || BINARY_CLASS_P (genop)
1294                   || REFERENCE_CLASS_P (genop));
1295       genop = create_expression_by_pieces (block, genop, stmts);
1296     }
1297   return genop;
1298 }
1299
1300   
1301 /* Create an expression in pieces, so that we can handle very complex
1302    expressions that may be ANTIC, but not necessary GIMPLE.  
1303    BLOCK is the basic block the expression will be inserted into,
1304    EXPR is the expression to insert (in value form)
1305    STMTS is a statement list to append the necessary insertions into.
1306
1307    This function will abort if we hit some value that shouldn't be
1308    ANTIC but is (IE there is no leader for it, or its components).
1309    This function may also generate expressions that are themselves
1310    partially or fully redundant.  Those that are will be either made
1311    fully redundant during the next iteration of insert (for partially
1312    redundant ones), or eliminated by eliminate (for fully redundant
1313    ones).  */
1314
1315 static tree
1316 create_expression_by_pieces (basic_block block, tree expr, tree stmts)
1317 {
1318   tree name = NULL_TREE;
1319   tree newexpr = NULL_TREE;
1320   tree v;
1321   
1322   switch (TREE_CODE_CLASS (TREE_CODE (expr)))
1323     {
1324     case tcc_binary:
1325       {
1326         tree_stmt_iterator tsi;
1327         tree genop1, genop2;
1328         tree temp;
1329         tree op1 = TREE_OPERAND (expr, 0);
1330         tree op2 = TREE_OPERAND (expr, 1);
1331         genop1 = find_or_generate_expression (block, op1, stmts);
1332         genop2 = find_or_generate_expression (block, op2, stmts);
1333         temp = create_tmp_var (TREE_TYPE (expr), "pretmp");
1334         add_referenced_tmp_var (temp);
1335         newexpr = build (TREE_CODE (expr), TREE_TYPE (expr), 
1336                          genop1, genop2);
1337         newexpr = build (MODIFY_EXPR, TREE_TYPE (expr),
1338                          temp, newexpr);
1339         name = make_ssa_name (temp, newexpr);
1340         TREE_OPERAND (newexpr, 0) = name;
1341         tsi = tsi_last (stmts);
1342         tsi_link_after (&tsi, newexpr, TSI_CONTINUE_LINKING);
1343         pre_stats.insertions++;
1344         break;
1345       }
1346     case tcc_unary:
1347       {
1348         tree_stmt_iterator tsi;
1349         tree genop1;
1350         tree temp;
1351         tree op1 = TREE_OPERAND (expr, 0);
1352         genop1 = find_or_generate_expression (block, op1, stmts);
1353         temp = create_tmp_var (TREE_TYPE (expr), "pretmp");
1354         add_referenced_tmp_var (temp);
1355         newexpr = build (TREE_CODE (expr), TREE_TYPE (expr), 
1356                          genop1);
1357         newexpr = build (MODIFY_EXPR, TREE_TYPE (expr),
1358                          temp, newexpr);
1359         name = make_ssa_name (temp, newexpr);
1360         TREE_OPERAND (newexpr, 0) = name;
1361         tsi = tsi_last (stmts);
1362         tsi_link_after (&tsi, newexpr, TSI_CONTINUE_LINKING);
1363         pre_stats.insertions++;
1364
1365         break;
1366       }
1367     default:
1368       gcc_unreachable ();
1369       
1370     }
1371   v = get_value_handle (expr);
1372   vn_add (name, v, NULL);
1373
1374   /* The value may already exist in either NEW_SETS, or AVAIL_OUT, because
1375      we are creating the expression by pieces, and this particular piece of
1376      the expression may have been represented.  There is no harm in replacing
1377      here.  */
1378   bitmap_value_replace_in_set (NEW_SETS (block), name); 
1379   bitmap_value_replace_in_set (AVAIL_OUT (block), name);
1380   if (dump_file && (dump_flags & TDF_DETAILS))
1381     {                               
1382       fprintf (dump_file, "Inserted ");
1383       print_generic_expr (dump_file, newexpr, 0);
1384       fprintf (dump_file, " in predecessor %d\n", block->index);
1385     }
1386   return name;
1387 }
1388
1389 /* Insert the to-be-made-available values of NODE for each predecessor, stored
1390    in AVAIL, into the predecessors of BLOCK, and merge the result with a phi
1391    node, given the same value handle as NODE.  The prefix of the phi node is
1392    given with TMPNAME*/
1393
1394 static bool
1395 insert_into_preds_of_block (basic_block block, value_set_node_t node,
1396                             tree *avail, const char *tmpname)
1397 {
1398   tree val = get_value_handle (node->expr);
1399   edge pred;
1400   basic_block bprime;
1401   tree eprime;
1402   edge_iterator ei;
1403   tree type = TREE_TYPE (avail[EDGE_PRED (block, 0)->src->index]);
1404   tree temp;
1405   
1406   if (dump_file && (dump_flags & TDF_DETAILS))
1407     {
1408       fprintf (dump_file, "Found partial redundancy for expression ");
1409       print_generic_expr (dump_file, node->expr, 0);
1410       fprintf (dump_file, "\n");
1411     }
1412
1413   /* Make the necessary insertions.  */
1414   FOR_EACH_EDGE (pred, ei, block->preds)
1415     {
1416       tree stmts = alloc_stmt_list ();
1417       tree builtexpr;
1418       bprime = pred->src;
1419       eprime = avail[bprime->index];
1420       if (BINARY_CLASS_P (eprime)
1421           || UNARY_CLASS_P (eprime))
1422         {
1423           builtexpr = create_expression_by_pieces (bprime,
1424                                                    eprime,
1425                                                    stmts);
1426           bsi_insert_on_edge (pred, stmts);
1427           avail[bprime->index] = builtexpr;
1428         }                             
1429     }
1430   /* Now build a phi for the new variable.  */
1431   temp = create_tmp_var (type, tmpname);
1432   add_referenced_tmp_var (temp);
1433   temp = create_phi_node (temp, block);
1434  
1435   FOR_EACH_EDGE (pred, ei, block->preds)
1436     add_phi_arg (temp, avail[pred->src->index], pred);
1437   
1438   vn_add (PHI_RESULT (temp), val, NULL);
1439   
1440   /* The value should *not* exist in PHI_GEN, or else we wouldn't be doing
1441      this insertion, since we test for the existence of this value in PHI_GEN
1442      before proceeding with the partial redundancy checks in insert_aux.
1443      
1444      The value may exist in AVAIL_OUT, in particular, it could be represented
1445      by the expression we are trying to eliminate, in which case we want the
1446      replacement to occur.  If it's not existing in AVAIL_OUT, we want it
1447      inserted there.
1448      
1449      Similarly, to the PHI_GEN case, the value should not exist in NEW_SETS of
1450      this block, because if it did, it would have existed in our dominator's
1451      AVAIL_OUT, and would have been skipped due to the full redundancy check.
1452   */
1453
1454   bitmap_insert_into_set (PHI_GEN (block),
1455                           PHI_RESULT (temp));
1456   bitmap_value_replace_in_set (AVAIL_OUT (block), 
1457                                PHI_RESULT (temp));
1458   bitmap_insert_into_set (NEW_SETS (block),
1459                           PHI_RESULT (temp));
1460   
1461   if (dump_file && (dump_flags & TDF_DETAILS))
1462     {
1463       fprintf (dump_file, "Created phi ");
1464       print_generic_expr (dump_file, temp, 0);
1465       fprintf (dump_file, " in block %d\n", block->index);
1466     }
1467   pre_stats.phis++;
1468   return true;
1469 }
1470
1471
1472       
1473 /* Perform insertion of partially redundant values.
1474    For BLOCK, do the following:
1475    1.  Propagate the NEW_SETS of the dominator into the current block.
1476    If the block has multiple predecessors, 
1477        2a. Iterate over the ANTIC expressions for the block to see if
1478            any of them are partially redundant.
1479        2b. If so, insert them into the necessary predecessors to make
1480            the expression fully redundant.
1481        2c. Insert a new PHI merging the values of the predecessors.
1482        2d. Insert the new PHI, and the new expressions, into the
1483            NEW_SETS set.  
1484    3. Recursively call ourselves on the dominator children of BLOCK.
1485
1486 */
1487
1488 static bool
1489 insert_aux (basic_block block)
1490 {
1491   basic_block son;
1492   bool new_stuff = false;
1493
1494   if (block)
1495     {
1496       basic_block dom;
1497       dom = get_immediate_dominator (CDI_DOMINATORS, block);
1498       if (dom)
1499         {
1500           unsigned i;
1501           bitmap_iterator bi;
1502           bitmap_set_t newset = NEW_SETS (dom);
1503           if (newset)
1504             {
1505               /* Note that we need to value_replace both NEW_SETS, and
1506                  AVAIL_OUT. For both the case of NEW_SETS, the value may be
1507                  represented by some non-simple expression here that we want
1508                  to replace it with.  */
1509               EXECUTE_IF_SET_IN_BITMAP (newset->expressions, 0, i, bi)
1510                 {
1511                   bitmap_value_replace_in_set (NEW_SETS (block), ssa_name (i));
1512                   bitmap_value_replace_in_set (AVAIL_OUT (block), ssa_name (i));
1513                 }
1514             }
1515           if (EDGE_COUNT (block->preds) > 1)
1516             {
1517               value_set_node_t node;
1518               for (node = ANTIC_IN (block)->head;
1519                    node;
1520                    node = node->next)
1521                 {
1522                   if (BINARY_CLASS_P (node->expr)
1523                       || UNARY_CLASS_P (node->expr))
1524                     {
1525                       tree *avail;
1526                       tree val;
1527                       bool by_some = false;
1528                       bool cant_insert = false;
1529                       bool all_same = true;
1530                       tree first_s = NULL;
1531                       edge pred;
1532                       basic_block bprime;
1533                       tree eprime = NULL_TREE;
1534                       edge_iterator ei;
1535
1536                       val = get_value_handle (node->expr);
1537                       if (bitmap_set_contains_value (PHI_GEN (block), val))
1538                         continue; 
1539                       if (bitmap_set_contains_value (AVAIL_OUT (dom), val))
1540                         {
1541                           if (dump_file && (dump_flags & TDF_DETAILS))
1542                             fprintf (dump_file, "Found fully redundant value\n");
1543                           continue;
1544                         }
1545                                               
1546                       avail = xcalloc (last_basic_block, sizeof (tree));
1547                       FOR_EACH_EDGE (pred, ei, block->preds)
1548                         {
1549                           tree vprime;
1550                           tree edoubleprime;
1551
1552                           /* This can happen in the very weird case
1553                              that our fake infinite loop edges have caused a
1554                              critical edge to appear.  */
1555                           if (EDGE_CRITICAL_P (pred))
1556                             {
1557                               cant_insert = true;
1558                               break;
1559                             }
1560                           bprime = pred->src;
1561                           eprime = phi_translate (node->expr,
1562                                                   ANTIC_IN (block),
1563                                                   bprime, block);
1564
1565                           /* eprime will generally only be NULL if the
1566                              value of the expression, translated
1567                              through the PHI for this predecessor, is
1568                              undefined.  If that is the case, we can't
1569                              make the expression fully redundant,
1570                              because its value is undefined along a
1571                              predecessor path.  We can thus break out
1572                              early because it doesn't matter what the
1573                              rest of the results are.  */
1574                           if (eprime == NULL)
1575                             {
1576                               cant_insert = true;
1577                               break;
1578                             }
1579
1580                           vprime = get_value_handle (eprime);
1581                           gcc_assert (vprime);
1582                           edoubleprime = bitmap_find_leader (AVAIL_OUT (bprime),
1583                                                              vprime);
1584                           if (edoubleprime == NULL)
1585                             {
1586                               avail[bprime->index] = eprime;
1587                               all_same = false;
1588                             }
1589                           else
1590                             {
1591                               avail[bprime->index] = edoubleprime;
1592                               by_some = true; 
1593                               if (first_s == NULL)
1594                                 first_s = edoubleprime;
1595                               else if (!operand_equal_p (first_s, edoubleprime,
1596                                                          0))
1597                                 all_same = false;
1598                             }
1599                         }
1600                       /* If we can insert it, it's not the same value
1601                          already existing along every predecessor, and
1602                          it's defined by some predecessor, it is
1603                          partially redundant.  */
1604                       if (!cant_insert && !all_same && by_some)
1605                         {
1606                           if (insert_into_preds_of_block (block, node, avail, 
1607                                                           "prephitmp"))
1608                             new_stuff = true;
1609                         }
1610
1611                       free (avail);
1612                     }
1613                 }
1614             }
1615         }
1616     }
1617   for (son = first_dom_son (CDI_DOMINATORS, block);
1618        son;
1619        son = next_dom_son (CDI_DOMINATORS, son))
1620     {
1621       new_stuff |= insert_aux (son);
1622     }
1623
1624   return new_stuff;
1625 }
1626
1627 /* Perform insertion of partially redundant values.  */
1628
1629 static void
1630 insert (void)
1631 {
1632   bool new_stuff = true;
1633   basic_block bb;
1634   int num_iterations = 0;
1635   
1636   FOR_ALL_BB (bb)
1637     NEW_SETS (bb) = bitmap_set_new ();
1638   
1639   while (new_stuff)
1640     {
1641       num_iterations++;
1642       new_stuff = false;
1643       new_stuff = insert_aux (ENTRY_BLOCK_PTR);
1644     }
1645   if (num_iterations > 2 && dump_file && (dump_flags & TDF_STATS))
1646     fprintf (dump_file, "insert required %d iterations\n", num_iterations);
1647 }
1648
1649
1650 /* Return true if VAR is an SSA variable with no defining statement in
1651    this procedure, *AND* isn't a live-on-entry parameter.  */
1652
1653 static bool
1654 is_undefined_value (tree expr)
1655 {
1656   return (TREE_CODE (expr) == SSA_NAME
1657           && IS_EMPTY_STMT (SSA_NAME_DEF_STMT (expr))
1658           /* PARM_DECLs and hard registers are always defined.  */
1659           && TREE_CODE (SSA_NAME_VAR (expr)) != PARM_DECL);
1660 }
1661
1662
1663 /* Given an SSA variable VAR and an expression EXPR, compute the value
1664    number for EXPR and create a value handle (VAL) for it.  If VAR and
1665    EXPR are not the same, associate VAL with VAR.  Finally, add VAR to
1666    S1 and its value handle to S2.
1667
1668    VUSES represent the virtual use operands associated with EXPR (if
1669    any). They are used when computing the hash value for EXPR.  */
1670
1671 static inline void
1672 add_to_sets (tree var, tree expr, vuse_optype vuses, bitmap_set_t s1,
1673              bitmap_set_t s2)
1674 {
1675   tree val = vn_lookup_or_add (expr, vuses);
1676
1677   /* VAR and EXPR may be the same when processing statements for which
1678      we are not computing value numbers (e.g., non-assignments, or
1679      statements that make aliased stores).  In those cases, we are
1680      only interested in making VAR available as its own value.  */
1681   if (var != expr)
1682     vn_add (var, val, NULL);
1683
1684   bitmap_insert_into_set (s1, var);
1685   bitmap_value_insert_into_set (s2, var);
1686 }
1687
1688
1689 /* Given a unary or binary expression EXPR, create and return a new
1690    expression with the same structure as EXPR but with its operands
1691    replaced with the value handles of each of the operands of EXPR.
1692    Insert EXPR's operands into the EXP_GEN set for BLOCK.
1693
1694    VUSES represent the virtual use operands associated with EXPR (if
1695    any). They are used when computing the hash value for EXPR.  */
1696
1697 static inline tree
1698 create_value_expr_from (tree expr, basic_block block, vuse_optype vuses)
1699 {
1700   int i;
1701   enum tree_code code = TREE_CODE (expr);
1702   tree vexpr;
1703
1704   gcc_assert (TREE_CODE_CLASS (code) == tcc_unary
1705               || TREE_CODE_CLASS (code) == tcc_binary
1706               || TREE_CODE_CLASS (code) == tcc_reference);
1707
1708   if (TREE_CODE_CLASS (code) == tcc_unary)
1709     vexpr = pool_alloc (unary_node_pool);
1710   else if (TREE_CODE_CLASS (code) == tcc_reference)
1711     vexpr = pool_alloc (reference_node_pool);
1712   else
1713     vexpr = pool_alloc (binary_node_pool);
1714
1715   memcpy (vexpr, expr, tree_size (expr));
1716
1717   for (i = 0; i < TREE_CODE_LENGTH (code); i++)
1718     {
1719       tree op = TREE_OPERAND (expr, i);
1720       if (op != NULL)
1721         {
1722           tree val = vn_lookup_or_add (op, vuses);
1723           if (!is_undefined_value (op))
1724             value_insert_into_set (EXP_GEN (block), op);
1725           if (TREE_CODE (val) == VALUE_HANDLE)
1726             TREE_TYPE (val) = TREE_TYPE (TREE_OPERAND (vexpr, i));
1727           TREE_OPERAND (vexpr, i) = val;
1728         }
1729     }
1730
1731   return vexpr;
1732 }
1733
1734
1735 /* Compute the AVAIL set for all basic blocks.
1736
1737    This function performs value numbering of the statements in each basic
1738    block.  The AVAIL sets are built from information we glean while doing
1739    this value numbering, since the AVAIL sets contain only one entry per
1740    value.
1741    
1742    AVAIL_IN[BLOCK] = AVAIL_OUT[dom(BLOCK)].
1743    AVAIL_OUT[BLOCK] = AVAIL_IN[BLOCK] U PHI_GEN[BLOCK] U TMP_GEN[BLOCK].  */
1744
1745 static void
1746 compute_avail (void)
1747 {
1748   basic_block block, son;
1749   basic_block *worklist;
1750   size_t sp = 0;
1751   tree param;
1752
1753   /* For arguments with default definitions, we pretend they are
1754      defined in the entry block.  */
1755   for (param = DECL_ARGUMENTS (current_function_decl);
1756        param;
1757        param = TREE_CHAIN (param))
1758     {
1759       if (default_def (param) != NULL)
1760         {
1761           tree val;
1762           tree def = default_def (param);
1763           val = vn_lookup_or_add (def, NULL);
1764           bitmap_insert_into_set (TMP_GEN (ENTRY_BLOCK_PTR), def);
1765           bitmap_value_insert_into_set (AVAIL_OUT (ENTRY_BLOCK_PTR), def);
1766         }
1767     }
1768
1769   /* Allocate the worklist.  */
1770   worklist = xmalloc (sizeof (basic_block) * n_basic_blocks);
1771
1772   /* Seed the algorithm by putting the dominator children of the entry
1773      block on the worklist.  */
1774   for (son = first_dom_son (CDI_DOMINATORS, ENTRY_BLOCK_PTR);
1775        son;
1776        son = next_dom_son (CDI_DOMINATORS, son))
1777     worklist[sp++] = son;
1778
1779   /* Loop until the worklist is empty.  */
1780   while (sp)
1781     {
1782       block_stmt_iterator bsi;
1783       tree stmt, phi;
1784       basic_block dom;
1785
1786       /* Pick a block from the worklist.  */
1787       block = worklist[--sp];
1788
1789       /* Initially, the set of available values in BLOCK is that of
1790          its immediate dominator.  */
1791       dom = get_immediate_dominator (CDI_DOMINATORS, block);
1792       if (dom)
1793         bitmap_set_copy (AVAIL_OUT (block), AVAIL_OUT (dom));
1794
1795       /* Generate values for PHI nodes.  */
1796       for (phi = phi_nodes (block); phi; phi = PHI_CHAIN (phi))
1797         /* We have no need for virtual phis, as they don't represent
1798            actual computations.  */
1799         if (is_gimple_reg (PHI_RESULT (phi)))
1800           add_to_sets (PHI_RESULT (phi), PHI_RESULT (phi), NULL,
1801                        PHI_GEN (block), AVAIL_OUT (block));
1802
1803       /* Now compute value numbers and populate value sets with all
1804          the expressions computed in BLOCK.  */
1805       for (bsi = bsi_start (block); !bsi_end_p (bsi); bsi_next (&bsi))
1806         {
1807           stmt_ann_t ann;
1808           size_t j;
1809
1810           stmt = bsi_stmt (bsi);
1811           ann = stmt_ann (stmt);
1812           get_stmt_operands (stmt);
1813
1814           /* We are only interested in assignments of the form
1815              X_i = EXPR, where EXPR represents an "interesting"
1816              computation, it has no volatile operands and X_i
1817              doesn't flow through an abnormal edge.  */
1818           if (TREE_CODE (stmt) == MODIFY_EXPR
1819               && !ann->has_volatile_ops
1820               && TREE_CODE (TREE_OPERAND (stmt, 0)) == SSA_NAME
1821               && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (TREE_OPERAND (stmt, 0)))
1822             {
1823               tree lhs = TREE_OPERAND (stmt, 0);
1824               tree rhs = TREE_OPERAND (stmt, 1);
1825               vuse_optype vuses = STMT_VUSE_OPS (stmt);
1826
1827               STRIP_USELESS_TYPE_CONVERSION (rhs);
1828               if (TREE_CODE (rhs) == SSA_NAME
1829                   || is_gimple_min_invariant (rhs))
1830                 {
1831                   /* Compute a value number for the RHS of the statement
1832                      and add its value to the AVAIL_OUT set for the block.
1833                      Add the LHS to TMP_GEN.  */
1834                   add_to_sets (lhs, rhs, vuses, TMP_GEN (block), 
1835                                AVAIL_OUT (block));
1836                   
1837                   if (TREE_CODE (rhs) == SSA_NAME
1838                       && !is_undefined_value (rhs))
1839                     value_insert_into_set (EXP_GEN (block), rhs);
1840                   continue;
1841                 }          
1842               else if (UNARY_CLASS_P (rhs) || BINARY_CLASS_P (rhs)
1843                        || TREE_CODE (rhs) == INDIRECT_REF)
1844                 {
1845                   /* For binary, unary, and reference expressions,
1846                      create a duplicate expression with the operands
1847                      replaced with the value handles of the original
1848                      RHS.  */
1849                   tree newt = create_value_expr_from (rhs, block, vuses);
1850                   add_to_sets (lhs, newt, vuses, TMP_GEN (block),
1851                                AVAIL_OUT (block));
1852                   value_insert_into_set (EXP_GEN (block), newt);
1853                   continue;
1854                 }
1855             }
1856
1857           /* For any other statement that we don't recognize, simply
1858              make the names generated by the statement available in
1859              AVAIL_OUT and TMP_GEN.  */
1860           for (j = 0; j < NUM_DEFS (STMT_DEF_OPS (stmt)); j++)
1861             {
1862               tree def = DEF_OP (STMT_DEF_OPS (stmt), j);
1863               add_to_sets (def, def, NULL, TMP_GEN (block),
1864                             AVAIL_OUT (block));
1865             }
1866
1867           for (j = 0; j < NUM_USES (STMT_USE_OPS (stmt)); j++)
1868             {
1869               tree use = USE_OP (STMT_USE_OPS (stmt), j);
1870               add_to_sets (use, use, NULL, TMP_GEN (block),
1871                             AVAIL_OUT (block));
1872             }
1873         }
1874
1875       /* Put the dominator children of BLOCK on the worklist of blocks
1876          to compute available sets for.  */
1877       for (son = first_dom_son (CDI_DOMINATORS, block);
1878            son;
1879            son = next_dom_son (CDI_DOMINATORS, son))
1880         worklist[sp++] = son;
1881     }
1882
1883   free (worklist);
1884 }
1885
1886
1887 /* Eliminate fully redundant computations.  */
1888
1889 static void
1890 eliminate (void)
1891 {
1892   basic_block b;
1893
1894   FOR_EACH_BB (b)
1895     {
1896       block_stmt_iterator i;
1897       
1898       for (i = bsi_start (b); !bsi_end_p (i); bsi_next (&i))
1899         {
1900           tree stmt = bsi_stmt (i);
1901
1902           /* Lookup the RHS of the expression, see if we have an
1903              available computation for it.  If so, replace the RHS with
1904              the available computation.  */
1905           if (TREE_CODE (stmt) == MODIFY_EXPR
1906               && TREE_CODE (TREE_OPERAND (stmt, 0)) == SSA_NAME
1907               && TREE_CODE (TREE_OPERAND (stmt ,1)) != SSA_NAME
1908               && !is_gimple_min_invariant (TREE_OPERAND (stmt, 1))
1909               && !stmt_ann (stmt)->has_volatile_ops)
1910             {
1911               tree lhs = TREE_OPERAND (stmt, 0);
1912               tree *rhs_p = &TREE_OPERAND (stmt, 1);
1913               tree sprime;
1914
1915               sprime = bitmap_find_leader (AVAIL_OUT (b),
1916                                            vn_lookup (lhs, NULL));
1917               if (sprime 
1918                   && sprime != lhs
1919                   && (TREE_CODE (*rhs_p) != SSA_NAME
1920                       || may_propagate_copy (*rhs_p, sprime)))
1921                 {
1922                   gcc_assert (sprime != *rhs_p);
1923
1924                   if (dump_file && (dump_flags & TDF_DETAILS))
1925                     {
1926                       fprintf (dump_file, "Replaced ");
1927                       print_generic_expr (dump_file, *rhs_p, 0);
1928                       fprintf (dump_file, " with ");
1929                       print_generic_expr (dump_file, sprime, 0);
1930                       fprintf (dump_file, " in ");
1931                       print_generic_stmt (dump_file, stmt, 0);
1932                     }
1933                   pre_stats.eliminations++;
1934                   propagate_tree_value (rhs_p, sprime);
1935                   modify_stmt (stmt);
1936
1937                   /* If we removed EH side effects from the statement, clean
1938                      its EH information.  */
1939                   if (maybe_clean_eh_stmt (stmt))
1940                     {
1941                       bitmap_set_bit (need_eh_cleanup,
1942                                       bb_for_stmt (stmt)->index);
1943                       if (dump_file && (dump_flags & TDF_DETAILS))
1944                         fprintf (dump_file, "  Removed EH side effects.\n");
1945                     }
1946                 }
1947             }
1948         }
1949     }
1950 }
1951
1952
1953 /* Initialize data structures used by PRE.  */
1954
1955 static void
1956 init_pre (void)
1957 {
1958   basic_block bb;
1959
1960   connect_infinite_loops_to_exit ();
1961   vn_init ();
1962   memset (&pre_stats, 0, sizeof (pre_stats));
1963
1964   /* If block 0 has more than one predecessor, it means that its PHI
1965      nodes will have arguments coming from block -1.  This creates
1966      problems for several places in PRE that keep local arrays indexed
1967      by block number.  To prevent this, we split the edge coming from
1968      ENTRY_BLOCK_PTR (FIXME, if ENTRY_BLOCK_PTR had an index number
1969      different than -1 we wouldn't have to hack this.  tree-ssa-dce.c
1970      needs a similar change).  */
1971   if (EDGE_COUNT (EDGE_SUCC (ENTRY_BLOCK_PTR, 0)->dest->preds) > 1)
1972     if (!(EDGE_SUCC (ENTRY_BLOCK_PTR, 0)->flags & EDGE_ABNORMAL))
1973       split_edge (EDGE_SUCC (ENTRY_BLOCK_PTR, 0));
1974
1975   FOR_ALL_BB (bb)
1976     bb->aux = xcalloc (1, sizeof (struct bb_value_sets));
1977
1978   bitmap_obstack_initialize (&grand_bitmap_obstack);
1979   phi_translate_table = htab_create (511, expr_pred_trans_hash,
1980                                      expr_pred_trans_eq, free);
1981   value_set_pool = create_alloc_pool ("Value sets",
1982                                       sizeof (struct value_set), 30);
1983   bitmap_set_pool = create_alloc_pool ("Bitmap sets",
1984                                        sizeof (struct bitmap_set), 30);
1985   value_set_node_pool = create_alloc_pool ("Value set nodes",
1986                                            sizeof (struct value_set_node), 30);
1987   calculate_dominance_info (CDI_POST_DOMINATORS);
1988   calculate_dominance_info (CDI_DOMINATORS);
1989   binary_node_pool = create_alloc_pool ("Binary tree nodes",
1990                                         tree_code_size (PLUS_EXPR), 30);
1991   unary_node_pool = create_alloc_pool ("Unary tree nodes",
1992                                        tree_code_size (NEGATE_EXPR), 30);
1993   reference_node_pool = create_alloc_pool ("Reference tree nodes",
1994                                            tree_code_size (ARRAY_REF), 30);
1995   FOR_ALL_BB (bb)
1996     {
1997       EXP_GEN (bb) = set_new (true);
1998       PHI_GEN (bb) = bitmap_set_new ();
1999       TMP_GEN (bb) = bitmap_set_new ();
2000       AVAIL_OUT (bb) = bitmap_set_new ();
2001     }
2002
2003   need_eh_cleanup = BITMAP_XMALLOC ();
2004 }
2005
2006
2007 /* Deallocate data structures used by PRE.  */
2008
2009 static void
2010 fini_pre (void)
2011 {
2012   basic_block bb;
2013   unsigned int i;
2014
2015   bsi_commit_edge_inserts ();
2016
2017   bitmap_obstack_release (&grand_bitmap_obstack);
2018   free_alloc_pool (value_set_pool);
2019   free_alloc_pool (bitmap_set_pool);
2020   free_alloc_pool (value_set_node_pool);
2021   free_alloc_pool (binary_node_pool);
2022   free_alloc_pool (reference_node_pool);
2023   free_alloc_pool (unary_node_pool);
2024   htab_delete (phi_translate_table);
2025   remove_fake_exit_edges ();
2026
2027   FOR_ALL_BB (bb)
2028     {
2029       free (bb->aux);
2030       bb->aux = NULL;
2031     }
2032
2033   free_dominance_info (CDI_POST_DOMINATORS);
2034   vn_delete ();
2035
2036   if (!bitmap_empty_p (need_eh_cleanup))
2037     {
2038       tree_purge_all_dead_eh_edges (need_eh_cleanup);
2039       cleanup_tree_cfg ();
2040     }
2041
2042   BITMAP_XFREE (need_eh_cleanup);
2043
2044   /* Wipe out pointers to VALUE_HANDLEs.  In the not terribly distant
2045      future we will want them to be persistent though.  */
2046   for (i = 0; i < num_ssa_names; i++)
2047     {
2048       tree name = ssa_name (i);
2049
2050       if (!name)
2051         continue;
2052
2053       if (SSA_NAME_VALUE (name)
2054           && TREE_CODE (SSA_NAME_VALUE (name)) == VALUE_HANDLE)
2055         SSA_NAME_VALUE (name) = NULL;
2056     }
2057 }
2058
2059
2060 /* Main entry point to the SSA-PRE pass.  DO_FRE is true if the caller
2061    only wants to do full redundancy elimination.  */
2062
2063 static void
2064 execute_pre (bool do_fre)
2065 {
2066   init_pre ();
2067
2068   /* Collect and value number expressions computed in each basic block.  */
2069   compute_avail ();
2070
2071   if (dump_file && (dump_flags & TDF_DETAILS))
2072     {
2073       basic_block bb;
2074
2075       FOR_ALL_BB (bb)
2076         {
2077           print_value_set (dump_file, EXP_GEN (bb), "exp_gen", bb->index);
2078           bitmap_print_value_set (dump_file, TMP_GEN (bb), "tmp_gen", 
2079                                   bb->index);
2080           bitmap_print_value_set (dump_file, AVAIL_OUT (bb), "avail_out", 
2081                                   bb->index);
2082         }
2083     }
2084
2085   /* Insert can get quite slow on an incredibly large number of basic
2086      blocks due to some quadratic behavior.  Until this behavior is
2087      fixed, don't run it when he have an incredibly large number of
2088      bb's.  If we aren't going to run insert, there is no point in
2089      computing ANTIC, either, even though it's plenty fast.  */
2090   if (!do_fre && n_basic_blocks < 4000)
2091     {
2092       compute_antic ();
2093       insert ();
2094     }
2095
2096   /* Remove all the redundant expressions.  */
2097   eliminate ();
2098   
2099   if (dump_file && (dump_flags & TDF_STATS))
2100     {
2101       fprintf (dump_file, "Insertions:%d\n", pre_stats.insertions);
2102       fprintf (dump_file, "New PHIs:%d\n", pre_stats.phis);
2103       fprintf (dump_file, "Eliminated:%d\n", pre_stats.eliminations);
2104     }
2105
2106   fini_pre ();
2107 }
2108
2109
2110 /* Gate and execute functions for PRE.  */
2111
2112 static void
2113 do_pre (void)
2114 {
2115   execute_pre (false);
2116 }
2117
2118 static bool
2119 gate_pre (void)
2120 {
2121   return flag_tree_pre != 0;
2122 }
2123
2124 struct tree_opt_pass pass_pre =
2125 {
2126   "pre",                                /* name */
2127   gate_pre,                             /* gate */
2128   do_pre,                               /* execute */
2129   NULL,                                 /* sub */
2130   NULL,                                 /* next */
2131   0,                                    /* static_pass_number */
2132   TV_TREE_PRE,                          /* tv_id */
2133   PROP_no_crit_edges | PROP_cfg
2134     | PROP_ssa | PROP_alias,            /* properties_required */
2135   0,                                    /* properties_provided */
2136   0,                                    /* properties_destroyed */
2137   0,                                    /* todo_flags_start */
2138   TODO_dump_func | TODO_ggc_collect | TODO_verify_ssa, /* todo_flags_finish */
2139   0                                     /* letter */
2140 };
2141
2142
2143 /* Gate and execute functions for FRE.  */
2144
2145 static void
2146 do_fre (void)
2147 {
2148   execute_pre (true);
2149 }
2150
2151 static bool
2152 gate_fre (void)
2153 {
2154   return flag_tree_fre != 0;
2155 }
2156
2157 struct tree_opt_pass pass_fre =
2158 {
2159   "fre",                                /* name */
2160   gate_fre,                             /* gate */
2161   do_fre,                               /* execute */
2162   NULL,                                 /* sub */
2163   NULL,                                 /* next */
2164   0,                                    /* static_pass_number */
2165   TV_TREE_FRE,                          /* tv_id */
2166   PROP_cfg | PROP_ssa | PROP_alias,     /* properties_required */
2167   0,                                    /* properties_provided */
2168   0,                                    /* properties_destroyed */
2169   0,                                    /* todo_flags_start */
2170   TODO_dump_func | TODO_ggc_collect | TODO_verify_ssa, /* todo_flags_finish */
2171   0                                     /* letter */
2172 };