OSDN Git Service

29cd567e9374c638dfed91de51789bf66136f93c
[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 ANTIC_OUT[BLOCK] = intersection of ANTIC_IN[b] for all succ(BLOCK), if
1110 succs(BLOCK) > 1
1111 ANTIC_OUT[BLOCK] = phi_translate (ANTIC_IN[succ(BLOCK)]) if
1112 succs(BLOCK) == 1
1113
1114 ANTIC_IN[BLOCK] = clean(ANTIC_OUT[BLOCK] U EXP_GEN[BLOCK] -
1115 TMP_GEN[BLOCK])
1116
1117 Iterate until fixpointed.
1118
1119 XXX: It would be nice to either write a set_clear, and use it for
1120 antic_out, or to mark the antic_out set as deleted at the end
1121 of this routine, so that the pool can hand the same memory back out
1122 again for the next antic_out.  */
1123
1124
1125 static bool
1126 compute_antic_aux (basic_block block)
1127 {
1128   basic_block son;
1129   edge e;
1130   bool changed = false;
1131   value_set_t S, old, ANTIC_OUT;
1132   value_set_node_t node;
1133   
1134   ANTIC_OUT = S = NULL;
1135   /* If any edges from predecessors are abnormal, antic_in is empty, so
1136      punt.  Remember that the block has an incoming abnormal edge by
1137      setting the BB_VISITED flag.  */
1138   if (! (block->flags & BB_VISITED))
1139     {
1140       edge_iterator ei;
1141       FOR_EACH_EDGE (e, ei, block->preds)
1142         if (e->flags & EDGE_ABNORMAL)
1143           {
1144             block->flags |= BB_VISITED;
1145             break;
1146           }
1147     }
1148   if (block->flags & BB_VISITED)
1149     {
1150       S = NULL;
1151       goto visit_sons;
1152     }
1153   
1154
1155   old = set_new (false);
1156   set_copy (old, ANTIC_IN (block));
1157   ANTIC_OUT = set_new (true);
1158
1159   /* If the block has no successors, ANTIC_OUT is empty, because it is
1160      the exit block.  */
1161   if (EDGE_COUNT (block->succs) == 0);
1162
1163   /* If we have one successor, we could have some phi nodes to
1164      translate through.  */
1165   else if (EDGE_COUNT (block->succs) == 1)
1166     {
1167       phi_translate_set (ANTIC_OUT, ANTIC_IN(EDGE_SUCC (block, 0)->dest),
1168                          block, EDGE_SUCC (block, 0)->dest);
1169     }
1170   /* If we have multiple successors, we take the intersection of all of
1171      them.  */
1172   else
1173     {
1174       VEC (basic_block) * worklist;
1175       edge e;
1176       size_t i;
1177       basic_block bprime, first;
1178       edge_iterator ei;
1179
1180       worklist = VEC_alloc (basic_block, 2);
1181       FOR_EACH_EDGE (e, ei, block->succs)
1182         VEC_safe_push (basic_block, worklist, e->dest);
1183       first = VEC_index (basic_block, worklist, 0);
1184       set_copy (ANTIC_OUT, ANTIC_IN (first));
1185
1186       for (i = 1; VEC_iterate (basic_block, worklist, i, bprime); i++)
1187         {
1188           node = ANTIC_OUT->head;
1189           while (node)
1190             {
1191               tree val;
1192               value_set_node_t next = node->next;
1193               val = get_value_handle (node->expr);
1194               if (!set_contains_value (ANTIC_IN (bprime), val))
1195                 set_remove (ANTIC_OUT, node->expr);
1196               node = next;
1197             }
1198         }
1199       VEC_free (basic_block, worklist);
1200     }
1201
1202   /* Generate ANTIC_OUT - TMP_GEN.  */
1203   S = bitmap_set_subtract_from_value_set (ANTIC_OUT, TMP_GEN (block), false);
1204
1205   /* Start ANTIC_IN with EXP_GEN - TMP_GEN */
1206   ANTIC_IN (block) = bitmap_set_subtract_from_value_set (EXP_GEN (block), 
1207                                                          TMP_GEN (block),
1208                                                          true);
1209   
1210   /* Then union in the ANTIC_OUT - TMP_GEN values, to get ANTIC_OUT U
1211      EXP_GEN - TMP_GEN */
1212   for (node = S->head;
1213        node;
1214        node = node->next)
1215     {
1216       value_insert_into_set (ANTIC_IN (block), node->expr);
1217     }
1218   clean (ANTIC_IN (block));
1219   
1220
1221   if (!set_equal (old, ANTIC_IN (block)))
1222     changed = true;
1223
1224  visit_sons:
1225   if (dump_file && (dump_flags & TDF_DETAILS))
1226     {
1227       if (ANTIC_OUT)
1228         print_value_set (dump_file, ANTIC_OUT, "ANTIC_OUT", block->index);
1229       print_value_set (dump_file, ANTIC_IN (block), "ANTIC_IN", block->index);
1230       if (S)
1231         print_value_set (dump_file, S, "S", block->index);
1232
1233     }
1234
1235   for (son = first_dom_son (CDI_POST_DOMINATORS, block);
1236        son;
1237        son = next_dom_son (CDI_POST_DOMINATORS, son))
1238     {
1239       changed |= compute_antic_aux (son);
1240     }
1241   return changed;
1242 }
1243
1244 /* Compute ANTIC sets.  */
1245
1246 static void
1247 compute_antic (void)
1248 {
1249   bool changed = true;
1250   basic_block bb;
1251   int num_iterations = 0;
1252   FOR_ALL_BB (bb)
1253     {
1254       ANTIC_IN (bb) = set_new (true);
1255       gcc_assert (!(bb->flags & BB_VISITED));
1256     }
1257
1258   while (changed)
1259     {
1260       num_iterations++;
1261       changed = false;
1262       changed = compute_antic_aux (EXIT_BLOCK_PTR);
1263     }
1264   FOR_ALL_BB (bb)
1265     {
1266       bb->flags &= ~BB_VISITED;
1267     }
1268   if (num_iterations > 2 && dump_file && (dump_flags & TDF_STATS))
1269     fprintf (dump_file, "compute_antic required %d iterations\n", num_iterations);
1270 }
1271
1272
1273 /* Find a leader for an expression, or generate one using
1274    create_expression_by_pieces if it's ANTIC but
1275    complex.  
1276    BLOCK is the basic_block we are looking for leaders in.
1277    EXPR is the expression to find a leader or generate for. 
1278    STMTS is the statement list to put the inserted expressions on.
1279    Returns the SSA_NAME of the LHS of the generated expression or the
1280    leader.  */
1281
1282 static tree
1283 find_or_generate_expression (basic_block block, tree expr, tree stmts)
1284 {
1285   tree genop = bitmap_find_leader (AVAIL_OUT (block), expr);
1286
1287   /* If it's still NULL, see if it is a complex expression, and if
1288      so, generate it recursively, otherwise, abort, because it's
1289      not really .  */
1290   if (genop == NULL)
1291     {
1292       genop = VALUE_HANDLE_EXPR_SET (expr)->head->expr;
1293       gcc_assert (UNARY_CLASS_P (genop)
1294                   || BINARY_CLASS_P (genop)
1295                   || REFERENCE_CLASS_P (genop));
1296       genop = create_expression_by_pieces (block, genop, stmts);
1297     }
1298   return genop;
1299 }
1300
1301   
1302 /* Create an expression in pieces, so that we can handle very complex
1303    expressions that may be ANTIC, but not necessary GIMPLE.  
1304    BLOCK is the basic block the expression will be inserted into,
1305    EXPR is the expression to insert (in value form)
1306    STMTS is a statement list to append the necessary insertions into.
1307
1308    This function will abort if we hit some value that shouldn't be
1309    ANTIC but is (IE there is no leader for it, or its components).
1310    This function may also generate expressions that are themselves
1311    partially or fully redundant.  Those that are will be either made
1312    fully redundant during the next iteration of insert (for partially
1313    redundant ones), or eliminated by eliminate (for fully redundant
1314    ones).  */
1315
1316 static tree
1317 create_expression_by_pieces (basic_block block, tree expr, tree stmts)
1318 {
1319   tree name = NULL_TREE;
1320   tree newexpr = NULL_TREE;
1321   tree v;
1322   
1323   switch (TREE_CODE_CLASS (TREE_CODE (expr)))
1324     {
1325     case tcc_binary:
1326       {
1327         tree_stmt_iterator tsi;
1328         tree genop1, genop2;
1329         tree temp;
1330         tree op1 = TREE_OPERAND (expr, 0);
1331         tree op2 = TREE_OPERAND (expr, 1);
1332         genop1 = find_or_generate_expression (block, op1, stmts);
1333         genop2 = find_or_generate_expression (block, op2, stmts);
1334         temp = create_tmp_var (TREE_TYPE (expr), "pretmp");
1335         add_referenced_tmp_var (temp);
1336         newexpr = build (TREE_CODE (expr), TREE_TYPE (expr), 
1337                          genop1, genop2);
1338         newexpr = build (MODIFY_EXPR, TREE_TYPE (expr),
1339                          temp, newexpr);
1340         name = make_ssa_name (temp, newexpr);
1341         TREE_OPERAND (newexpr, 0) = name;
1342         tsi = tsi_last (stmts);
1343         tsi_link_after (&tsi, newexpr, TSI_CONTINUE_LINKING);
1344         pre_stats.insertions++;
1345         break;
1346       }
1347     case tcc_unary:
1348       {
1349         tree_stmt_iterator tsi;
1350         tree genop1;
1351         tree temp;
1352         tree op1 = TREE_OPERAND (expr, 0);
1353         genop1 = find_or_generate_expression (block, op1, stmts);
1354         temp = create_tmp_var (TREE_TYPE (expr), "pretmp");
1355         add_referenced_tmp_var (temp);
1356         newexpr = build (TREE_CODE (expr), TREE_TYPE (expr), 
1357                          genop1);
1358         newexpr = build (MODIFY_EXPR, TREE_TYPE (expr),
1359                          temp, newexpr);
1360         name = make_ssa_name (temp, newexpr);
1361         TREE_OPERAND (newexpr, 0) = name;
1362         tsi = tsi_last (stmts);
1363         tsi_link_after (&tsi, newexpr, TSI_CONTINUE_LINKING);
1364         pre_stats.insertions++;
1365
1366         break;
1367       }
1368     default:
1369       gcc_unreachable ();
1370       
1371     }
1372   v = get_value_handle (expr);
1373   vn_add (name, v, NULL);
1374
1375   /* The value may already exist in either NEW_SETS, or AVAIL_OUT, because
1376      we are creating the expression by pieces, and this particular piece of
1377      the expression may have been represented.  There is no harm in replacing
1378      here.  */
1379   bitmap_value_replace_in_set (NEW_SETS (block), name); 
1380   bitmap_value_replace_in_set (AVAIL_OUT (block), name);
1381   if (dump_file && (dump_flags & TDF_DETAILS))
1382     {                               
1383       fprintf (dump_file, "Inserted ");
1384       print_generic_expr (dump_file, newexpr, 0);
1385       fprintf (dump_file, " in predecessor %d\n", block->index);
1386     }
1387   return name;
1388 }
1389
1390 /* Insert the to-be-made-available values of NODE for each predecessor, stored
1391    in AVAIL, into the predecessors of BLOCK, and merge the result with a phi
1392    node, given the same value handle as NODE.  The prefix of the phi node is
1393    given with TMPNAME*/
1394
1395 static bool
1396 insert_into_preds_of_block (basic_block block, value_set_node_t node,
1397                             tree *avail, const char *tmpname)
1398 {
1399   tree val = get_value_handle (node->expr);
1400   edge pred;
1401   basic_block bprime;
1402   tree eprime;
1403   edge_iterator ei;
1404   tree type = TREE_TYPE (avail[EDGE_PRED (block, 0)->src->index]);
1405   tree temp;
1406   
1407   if (dump_file && (dump_flags & TDF_DETAILS))
1408     {
1409       fprintf (dump_file, "Found partial redundancy for expression ");
1410       print_generic_expr (dump_file, node->expr, 0);
1411       fprintf (dump_file, "\n");
1412     }
1413
1414   /* Make the necessary insertions.  */
1415   FOR_EACH_EDGE (pred, ei, block->preds)
1416     {
1417       tree stmts = alloc_stmt_list ();
1418       tree builtexpr;
1419       bprime = pred->src;
1420       eprime = avail[bprime->index];
1421       if (BINARY_CLASS_P (eprime)
1422           || UNARY_CLASS_P (eprime))
1423         {
1424           builtexpr = create_expression_by_pieces (bprime,
1425                                                    eprime,
1426                                                    stmts);
1427           bsi_insert_on_edge (pred, stmts);
1428           avail[bprime->index] = builtexpr;
1429         }                             
1430     }
1431   /* Now build a phi for the new variable.  */
1432   temp = create_tmp_var (type, tmpname);
1433   add_referenced_tmp_var (temp);
1434   temp = create_phi_node (temp, block);
1435  
1436   FOR_EACH_EDGE (pred, ei, block->preds)
1437     add_phi_arg (temp, avail[pred->src->index], pred);
1438   
1439   vn_add (PHI_RESULT (temp), val, NULL);
1440   
1441   /* The value should *not* exist in PHI_GEN, or else we wouldn't be doing
1442      this insertion, since we test for the existence of this value in PHI_GEN
1443      before proceeding with the partial redundancy checks in insert_aux.
1444      
1445      The value may exist in AVAIL_OUT, in particular, it could be represented
1446      by the expression we are trying to eliminate, in which case we want the
1447      replacement to occur.  If it's not existing in AVAIL_OUT, we want it
1448      inserted there.
1449      
1450      Similarly, to the PHI_GEN case, the value should not exist in NEW_SETS of
1451      this block, because if it did, it would have existed in our dominator's
1452      AVAIL_OUT, and would have been skipped due to the full redundancy check.
1453   */
1454
1455   bitmap_insert_into_set (PHI_GEN (block),
1456                           PHI_RESULT (temp));
1457   bitmap_value_replace_in_set (AVAIL_OUT (block), 
1458                                PHI_RESULT (temp));
1459   bitmap_insert_into_set (NEW_SETS (block),
1460                           PHI_RESULT (temp));
1461   
1462   if (dump_file && (dump_flags & TDF_DETAILS))
1463     {
1464       fprintf (dump_file, "Created phi ");
1465       print_generic_expr (dump_file, temp, 0);
1466       fprintf (dump_file, " in block %d\n", block->index);
1467     }
1468   pre_stats.phis++;
1469   return true;
1470 }
1471
1472
1473       
1474 /* Perform insertion of partially redundant values.
1475    For BLOCK, do the following:
1476    1.  Propagate the NEW_SETS of the dominator into the current block.
1477    If the block has multiple predecessors, 
1478        2a. Iterate over the ANTIC expressions for the block to see if
1479            any of them are partially redundant.
1480        2b. If so, insert them into the necessary predecessors to make
1481            the expression fully redundant.
1482        2c. Insert a new PHI merging the values of the predecessors.
1483        2d. Insert the new PHI, and the new expressions, into the
1484            NEW_SETS set.  
1485    3. Recursively call ourselves on the dominator children of BLOCK.
1486
1487 */
1488
1489 static bool
1490 insert_aux (basic_block block)
1491 {
1492   basic_block son;
1493   bool new_stuff = false;
1494
1495   if (block)
1496     {
1497       basic_block dom;
1498       dom = get_immediate_dominator (CDI_DOMINATORS, block);
1499       if (dom)
1500         {
1501           unsigned i;
1502           bitmap_iterator bi;
1503           bitmap_set_t newset = NEW_SETS (dom);
1504           if (newset)
1505             {
1506               /* Note that we need to value_replace both NEW_SETS, and
1507                  AVAIL_OUT. For both the case of NEW_SETS, the value may be
1508                  represented by some non-simple expression here that we want
1509                  to replace it with.  */
1510               EXECUTE_IF_SET_IN_BITMAP (newset->expressions, 0, i, bi)
1511                 {
1512                   bitmap_value_replace_in_set (NEW_SETS (block), ssa_name (i));
1513                   bitmap_value_replace_in_set (AVAIL_OUT (block), ssa_name (i));
1514                 }
1515             }
1516           if (EDGE_COUNT (block->preds) > 1)
1517             {
1518               value_set_node_t node;
1519               for (node = ANTIC_IN (block)->head;
1520                    node;
1521                    node = node->next)
1522                 {
1523                   if (BINARY_CLASS_P (node->expr)
1524                       || UNARY_CLASS_P (node->expr))
1525                     {
1526                       tree *avail;
1527                       tree val;
1528                       bool by_some = false;
1529                       bool cant_insert = false;
1530                       bool all_same = true;
1531                       tree first_s = NULL;
1532                       edge pred;
1533                       basic_block bprime;
1534                       tree eprime = NULL_TREE;
1535                       edge_iterator ei;
1536
1537                       val = get_value_handle (node->expr);
1538                       if (bitmap_set_contains_value (PHI_GEN (block), val))
1539                         continue; 
1540                       if (bitmap_set_contains_value (AVAIL_OUT (dom), val))
1541                         {
1542                           if (dump_file && (dump_flags & TDF_DETAILS))
1543                             fprintf (dump_file, "Found fully redundant value\n");
1544                           continue;
1545                         }
1546                                               
1547                       avail = xcalloc (last_basic_block, sizeof (tree));
1548                       FOR_EACH_EDGE (pred, ei, block->preds)
1549                         {
1550                           tree vprime;
1551                           tree edoubleprime;
1552
1553                           /* This can happen in the very weird case
1554                              that our fake infinite loop edges have caused a
1555                              critical edge to appear.  */
1556                           if (EDGE_CRITICAL_P (pred))
1557                             {
1558                               cant_insert = true;
1559                               break;
1560                             }
1561                           bprime = pred->src;
1562                           eprime = phi_translate (node->expr,
1563                                                   ANTIC_IN (block),
1564                                                   bprime, block);
1565
1566                           /* eprime will generally only be NULL if the
1567                              value of the expression, translated
1568                              through the PHI for this predecessor, is
1569                              undefined.  If that is the case, we can't
1570                              make the expression fully redundant,
1571                              because its value is undefined along a
1572                              predecessor path.  We can thus break out
1573                              early because it doesn't matter what the
1574                              rest of the results are.  */
1575                           if (eprime == NULL)
1576                             {
1577                               cant_insert = true;
1578                               break;
1579                             }
1580
1581                           vprime = get_value_handle (eprime);
1582                           gcc_assert (vprime);
1583                           edoubleprime = bitmap_find_leader (AVAIL_OUT (bprime),
1584                                                              vprime);
1585                           if (edoubleprime == NULL)
1586                             {
1587                               avail[bprime->index] = eprime;
1588                               all_same = false;
1589                             }
1590                           else
1591                             {
1592                               avail[bprime->index] = edoubleprime;
1593                               by_some = true; 
1594                               if (first_s == NULL)
1595                                 first_s = edoubleprime;
1596                               else if (!operand_equal_p (first_s, edoubleprime,
1597                                                          0))
1598                                 all_same = false;
1599                             }
1600                         }
1601                       /* If we can insert it, it's not the same value
1602                          already existing along every predecessor, and
1603                          it's defined by some predecessor, it is
1604                          partially redundant.  */
1605                       if (!cant_insert && !all_same && by_some)
1606                         {
1607                           if (insert_into_preds_of_block (block, node, avail, 
1608                                                           "prephitmp"))
1609                             new_stuff = true;
1610                         }
1611
1612                       free (avail);
1613                     }
1614                 }
1615             }
1616         }
1617     }
1618   for (son = first_dom_son (CDI_DOMINATORS, block);
1619        son;
1620        son = next_dom_son (CDI_DOMINATORS, son))
1621     {
1622       new_stuff |= insert_aux (son);
1623     }
1624
1625   return new_stuff;
1626 }
1627
1628 /* Perform insertion of partially redundant values.  */
1629
1630 static void
1631 insert (void)
1632 {
1633   bool new_stuff = true;
1634   basic_block bb;
1635   int num_iterations = 0;
1636   
1637   FOR_ALL_BB (bb)
1638     NEW_SETS (bb) = bitmap_set_new ();
1639   
1640   while (new_stuff)
1641     {
1642       num_iterations++;
1643       new_stuff = false;
1644       new_stuff = insert_aux (ENTRY_BLOCK_PTR);
1645     }
1646   if (num_iterations > 2 && dump_file && (dump_flags & TDF_STATS))
1647     fprintf (dump_file, "insert required %d iterations\n", num_iterations);
1648 }
1649
1650
1651 /* Return true if VAR is an SSA variable with no defining statement in
1652    this procedure, *AND* isn't a live-on-entry parameter.  */
1653
1654 static bool
1655 is_undefined_value (tree expr)
1656 {
1657   return (TREE_CODE (expr) == SSA_NAME
1658           && IS_EMPTY_STMT (SSA_NAME_DEF_STMT (expr))
1659           /* PARM_DECLs and hard registers are always defined.  */
1660           && TREE_CODE (SSA_NAME_VAR (expr)) != PARM_DECL);
1661 }
1662
1663
1664 /* Given an SSA variable VAR and an expression EXPR, compute the value
1665    number for EXPR and create a value handle (VAL) for it.  If VAR and
1666    EXPR are not the same, associate VAL with VAR.  Finally, add VAR to
1667    S1 and its value handle to S2.
1668
1669    VUSES represent the virtual use operands associated with EXPR (if
1670    any). They are used when computing the hash value for EXPR.  */
1671
1672 static inline void
1673 add_to_sets (tree var, tree expr, vuse_optype vuses, bitmap_set_t s1,
1674              bitmap_set_t s2)
1675 {
1676   tree val = vn_lookup_or_add (expr, vuses);
1677
1678   /* VAR and EXPR may be the same when processing statements for which
1679      we are not computing value numbers (e.g., non-assignments, or
1680      statements that make aliased stores).  In those cases, we are
1681      only interested in making VAR available as its own value.  */
1682   if (var != expr)
1683     vn_add (var, val, NULL);
1684
1685   bitmap_insert_into_set (s1, var);
1686   bitmap_value_insert_into_set (s2, var);
1687 }
1688
1689
1690 /* Given a unary or binary expression EXPR, create and return a new
1691    expression with the same structure as EXPR but with its operands
1692    replaced with the value handles of each of the operands of EXPR.
1693    Insert EXPR's operands into the EXP_GEN set for BLOCK.
1694
1695    VUSES represent the virtual use operands associated with EXPR (if
1696    any). They are used when computing the hash value for EXPR.  */
1697
1698 static inline tree
1699 create_value_expr_from (tree expr, basic_block block, vuse_optype vuses)
1700 {
1701   int i;
1702   enum tree_code code = TREE_CODE (expr);
1703   tree vexpr;
1704
1705   gcc_assert (TREE_CODE_CLASS (code) == tcc_unary
1706               || TREE_CODE_CLASS (code) == tcc_binary
1707               || TREE_CODE_CLASS (code) == tcc_reference);
1708
1709   if (TREE_CODE_CLASS (code) == tcc_unary)
1710     vexpr = pool_alloc (unary_node_pool);
1711   else if (TREE_CODE_CLASS (code) == tcc_reference)
1712     vexpr = pool_alloc (reference_node_pool);
1713   else
1714     vexpr = pool_alloc (binary_node_pool);
1715
1716   memcpy (vexpr, expr, tree_size (expr));
1717
1718   for (i = 0; i < TREE_CODE_LENGTH (code); i++)
1719     {
1720       tree op = TREE_OPERAND (expr, i);
1721       if (op != NULL)
1722         {
1723           tree val = vn_lookup_or_add (op, vuses);
1724           if (!is_undefined_value (op))
1725             value_insert_into_set (EXP_GEN (block), op);
1726           if (TREE_CODE (val) == VALUE_HANDLE)
1727             TREE_TYPE (val) = TREE_TYPE (TREE_OPERAND (vexpr, i));
1728           TREE_OPERAND (vexpr, i) = val;
1729         }
1730     }
1731
1732   return vexpr;
1733 }
1734
1735
1736 /* Compute the AVAIL set for BLOCK.
1737    This function performs value numbering of the statements in BLOCK. 
1738    The AVAIL sets are built from information we glean while doing this
1739    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 (basic_block block)
1747 {
1748   basic_block son;
1749   
1750   /* For arguments with default definitions, we pretend they are
1751      defined in the entry block.  */
1752   if (block == ENTRY_BLOCK_PTR)
1753     {
1754       tree param;
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 (block), def);
1765               bitmap_value_insert_into_set (AVAIL_OUT (block), def);
1766             }
1767         }
1768     }
1769   else if (block)
1770     {
1771       block_stmt_iterator bsi;
1772       tree stmt, phi;
1773       basic_block dom;
1774
1775       /* Initially, the set of available values in BLOCK is that of
1776          its immediate dominator.  */
1777       dom = get_immediate_dominator (CDI_DOMINATORS, block);
1778       if (dom)
1779         bitmap_set_copy (AVAIL_OUT (block), AVAIL_OUT (dom));
1780
1781       /* Generate values for PHI nodes.  */
1782       for (phi = phi_nodes (block); phi; phi = PHI_CHAIN (phi))
1783         /* We have no need for virtual phis, as they don't represent
1784            actual computations.  */
1785         if (is_gimple_reg (PHI_RESULT (phi)))
1786           add_to_sets (PHI_RESULT (phi), PHI_RESULT (phi), NULL,
1787                        PHI_GEN (block), AVAIL_OUT (block));
1788
1789       /* Now compute value numbers and populate value sets with all
1790          the expressions computed in BLOCK.  */
1791       for (bsi = bsi_start (block); !bsi_end_p (bsi); bsi_next (&bsi))
1792         {
1793           stmt_ann_t ann;
1794           size_t j;
1795
1796           stmt = bsi_stmt (bsi);
1797           ann = stmt_ann (stmt);
1798           get_stmt_operands (stmt);
1799
1800           /* We are only interested in assignments of the form
1801              X_i = EXPR, where EXPR represents an "interesting"
1802              computation, it has no volatile operands and X_i
1803              doesn't flow through an abnormal edge.  */
1804           if (TREE_CODE (stmt) == MODIFY_EXPR
1805               && !ann->has_volatile_ops
1806               && TREE_CODE (TREE_OPERAND (stmt, 0)) == SSA_NAME
1807               && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (TREE_OPERAND (stmt, 0)))
1808             {
1809               tree lhs = TREE_OPERAND (stmt, 0);
1810               tree rhs = TREE_OPERAND (stmt, 1);
1811               vuse_optype vuses = STMT_VUSE_OPS (stmt);
1812
1813               STRIP_USELESS_TYPE_CONVERSION (rhs);
1814               if (TREE_CODE (rhs) == SSA_NAME
1815                   || is_gimple_min_invariant (rhs))
1816                 {
1817                   /* Compute a value number for the RHS of the statement
1818                      and add its value to the AVAIL_OUT set for the block.
1819                      Add the LHS to TMP_GEN.  */
1820                   add_to_sets (lhs, rhs, vuses, TMP_GEN (block), 
1821                                AVAIL_OUT (block));
1822                   
1823                   if (TREE_CODE (rhs) == SSA_NAME
1824                       && !is_undefined_value (rhs))
1825                     value_insert_into_set (EXP_GEN (block), rhs);
1826                   continue;
1827                 }          
1828               else if (UNARY_CLASS_P (rhs) || BINARY_CLASS_P (rhs)
1829                        || TREE_CODE (rhs) == INDIRECT_REF)
1830                 {
1831                   /* For binary, unary, and reference expressions,
1832                      create a duplicate expression with the operands
1833                      replaced with the value handles of the original
1834                      RHS.  */
1835                   tree newt = create_value_expr_from (rhs, block, vuses);
1836                   add_to_sets (lhs, newt, vuses, TMP_GEN (block),
1837                                AVAIL_OUT (block));
1838                   value_insert_into_set (EXP_GEN (block), newt);
1839                   continue;
1840                 }
1841             }
1842
1843           /* For any other statement that we don't recognize, simply
1844              make the names generated by the statement available in
1845              AVAIL_OUT and TMP_GEN.  */
1846           for (j = 0; j < NUM_DEFS (STMT_DEF_OPS (stmt)); j++)
1847             {
1848               tree def = DEF_OP (STMT_DEF_OPS (stmt), j);
1849               add_to_sets (def, def, NULL, TMP_GEN (block),
1850                             AVAIL_OUT (block));
1851             }
1852
1853           for (j = 0; j < NUM_USES (STMT_USE_OPS (stmt)); j++)
1854             {
1855               tree use = USE_OP (STMT_USE_OPS (stmt), j);
1856               add_to_sets (use, use, NULL, TMP_GEN (block),
1857                             AVAIL_OUT (block));
1858             }
1859         }
1860     }
1861
1862   /* Compute available sets for the dominator children of BLOCK.  */
1863   for (son = first_dom_son (CDI_DOMINATORS, block);
1864        son;
1865        son = next_dom_son (CDI_DOMINATORS, son))
1866     compute_avail (son);
1867 }
1868
1869
1870 /* Eliminate fully redundant computations.  */
1871
1872 static void
1873 eliminate (void)
1874 {
1875   basic_block b;
1876
1877   FOR_EACH_BB (b)
1878     {
1879       block_stmt_iterator i;
1880       
1881       for (i = bsi_start (b); !bsi_end_p (i); bsi_next (&i))
1882         {
1883           tree stmt = bsi_stmt (i);
1884
1885           /* Lookup the RHS of the expression, see if we have an
1886              available computation for it.  If so, replace the RHS with
1887              the available computation.  */
1888           if (TREE_CODE (stmt) == MODIFY_EXPR
1889               && TREE_CODE (TREE_OPERAND (stmt, 0)) == SSA_NAME
1890               && TREE_CODE (TREE_OPERAND (stmt ,1)) != SSA_NAME
1891               && !is_gimple_min_invariant (TREE_OPERAND (stmt, 1))
1892               && !stmt_ann (stmt)->has_volatile_ops)
1893             {
1894               tree lhs = TREE_OPERAND (stmt, 0);
1895               tree *rhs_p = &TREE_OPERAND (stmt, 1);
1896               tree sprime;
1897
1898               sprime = bitmap_find_leader (AVAIL_OUT (b),
1899                                            vn_lookup (lhs, NULL));
1900               if (sprime 
1901                   && sprime != lhs
1902                   && (TREE_CODE (*rhs_p) != SSA_NAME
1903                       || may_propagate_copy (*rhs_p, sprime)))
1904                 {
1905                   gcc_assert (sprime != *rhs_p);
1906
1907                   if (dump_file && (dump_flags & TDF_DETAILS))
1908                     {
1909                       fprintf (dump_file, "Replaced ");
1910                       print_generic_expr (dump_file, *rhs_p, 0);
1911                       fprintf (dump_file, " with ");
1912                       print_generic_expr (dump_file, sprime, 0);
1913                       fprintf (dump_file, " in ");
1914                       print_generic_stmt (dump_file, stmt, 0);
1915                     }
1916                   pre_stats.eliminations++;
1917                   propagate_tree_value (rhs_p, sprime);
1918                   modify_stmt (stmt);
1919
1920                   /* If we removed EH side effects from the statement, clean
1921                      its EH information.  */
1922                   if (maybe_clean_eh_stmt (stmt))
1923                     {
1924                       bitmap_set_bit (need_eh_cleanup,
1925                                       bb_for_stmt (stmt)->index);
1926                       if (dump_file && (dump_flags & TDF_DETAILS))
1927                         fprintf (dump_file, "  Removed EH side effects.\n");
1928                     }
1929                 }
1930             }
1931         }
1932     }
1933 }
1934
1935
1936 /* Initialize data structures used by PRE.  */
1937
1938 static void
1939 init_pre (void)
1940 {
1941   basic_block bb;
1942
1943   connect_infinite_loops_to_exit ();
1944   vn_init ();
1945   memset (&pre_stats, 0, sizeof (pre_stats));
1946
1947   /* If block 0 has more than one predecessor, it means that its PHI
1948      nodes will have arguments coming from block -1.  This creates
1949      problems for several places in PRE that keep local arrays indexed
1950      by block number.  To prevent this, we split the edge coming from
1951      ENTRY_BLOCK_PTR (FIXME, if ENTRY_BLOCK_PTR had an index number
1952      different than -1 we wouldn't have to hack this.  tree-ssa-dce.c
1953      needs a similar change).  */
1954   if (EDGE_COUNT (EDGE_SUCC (ENTRY_BLOCK_PTR, 0)->dest->preds) > 1)
1955     if (!(EDGE_SUCC (ENTRY_BLOCK_PTR, 0)->flags & EDGE_ABNORMAL))
1956       split_edge (EDGE_SUCC (ENTRY_BLOCK_PTR, 0));
1957
1958   FOR_ALL_BB (bb)
1959     bb->aux = xcalloc (1, sizeof (struct bb_value_sets));
1960
1961   bitmap_obstack_initialize (&grand_bitmap_obstack);
1962   phi_translate_table = htab_create (511, expr_pred_trans_hash,
1963                                      expr_pred_trans_eq, free);
1964   value_set_pool = create_alloc_pool ("Value sets",
1965                                       sizeof (struct value_set), 30);
1966   bitmap_set_pool = create_alloc_pool ("Bitmap sets",
1967                                        sizeof (struct bitmap_set), 30);
1968   value_set_node_pool = create_alloc_pool ("Value set nodes",
1969                                            sizeof (struct value_set_node), 30);
1970   calculate_dominance_info (CDI_POST_DOMINATORS);
1971   calculate_dominance_info (CDI_DOMINATORS);
1972   binary_node_pool = create_alloc_pool ("Binary tree nodes",
1973                                         tree_code_size (PLUS_EXPR), 30);
1974   unary_node_pool = create_alloc_pool ("Unary tree nodes",
1975                                        tree_code_size (NEGATE_EXPR), 30);
1976   reference_node_pool = create_alloc_pool ("Reference tree nodes",
1977                                            tree_code_size (ARRAY_REF), 30);
1978   FOR_ALL_BB (bb)
1979     {
1980       EXP_GEN (bb) = set_new (true);
1981       PHI_GEN (bb) = bitmap_set_new ();
1982       TMP_GEN (bb) = bitmap_set_new ();
1983       AVAIL_OUT (bb) = bitmap_set_new ();
1984     }
1985
1986   need_eh_cleanup = BITMAP_XMALLOC ();
1987 }
1988
1989
1990 /* Deallocate data structures used by PRE.  */
1991
1992 static void
1993 fini_pre (void)
1994 {
1995   basic_block bb;
1996   unsigned int i;
1997
1998   bsi_commit_edge_inserts ();
1999
2000   bitmap_obstack_release (&grand_bitmap_obstack);
2001   free_alloc_pool (value_set_pool);
2002   free_alloc_pool (bitmap_set_pool);
2003   free_alloc_pool (value_set_node_pool);
2004   free_alloc_pool (binary_node_pool);
2005   free_alloc_pool (reference_node_pool);
2006   free_alloc_pool (unary_node_pool);
2007   htab_delete (phi_translate_table);
2008   remove_fake_exit_edges ();
2009
2010   FOR_ALL_BB (bb)
2011     {
2012       free (bb->aux);
2013       bb->aux = NULL;
2014     }
2015
2016   free_dominance_info (CDI_POST_DOMINATORS);
2017   vn_delete ();
2018
2019   if (!bitmap_empty_p (need_eh_cleanup))
2020     {
2021       tree_purge_all_dead_eh_edges (need_eh_cleanup);
2022       cleanup_tree_cfg ();
2023     }
2024
2025   BITMAP_XFREE (need_eh_cleanup);
2026
2027   /* Wipe out pointers to VALUE_HANDLEs.  In the not terribly distant
2028      future we will want them to be persistent though.  */
2029   for (i = 0; i < num_ssa_names; i++)
2030     {
2031       tree name = ssa_name (i);
2032
2033       if (!name)
2034         continue;
2035
2036       if (SSA_NAME_VALUE (name)
2037           && TREE_CODE (SSA_NAME_VALUE (name)) == VALUE_HANDLE)
2038         SSA_NAME_VALUE (name) = NULL;
2039     }
2040 }
2041
2042
2043 /* Main entry point to the SSA-PRE pass.  DO_FRE is true if the caller
2044    only wants to do full redundancy elimination.  */
2045
2046 static void
2047 execute_pre (bool do_fre)
2048 {
2049   init_pre ();
2050
2051   /* Collect and value number expressions computed in each basic
2052      block.  */
2053   compute_avail (ENTRY_BLOCK_PTR);
2054
2055   if (dump_file && (dump_flags & TDF_DETAILS))
2056     {
2057       basic_block bb;
2058
2059       FOR_ALL_BB (bb)
2060         {
2061           print_value_set (dump_file, EXP_GEN (bb), "exp_gen", bb->index);
2062           bitmap_print_value_set (dump_file, TMP_GEN (bb), "tmp_gen", 
2063                                   bb->index);
2064           bitmap_print_value_set (dump_file, AVAIL_OUT (bb), "avail_out", 
2065                                   bb->index);
2066         }
2067     }
2068
2069   /* Insert can get quite slow on an incredibly large number of basic
2070      blocks due to some quadratic behavior.  Until this behavior is
2071      fixed, don't run it when he have an incredibly large number of
2072      bb's.  If we aren't going to run insert, there is no point in
2073      computing ANTIC, either, even though it's plenty fast.  */
2074   if (!do_fre && n_basic_blocks < 4000)
2075     {
2076       compute_antic ();
2077       insert ();
2078     }
2079
2080   /* Remove all the redundant expressions.  */
2081   eliminate ();
2082   
2083   if (dump_file && (dump_flags & TDF_STATS))
2084     {
2085       fprintf (dump_file, "Insertions:%d\n", pre_stats.insertions);
2086       fprintf (dump_file, "New PHIs:%d\n", pre_stats.phis);
2087       fprintf (dump_file, "Eliminated:%d\n", pre_stats.eliminations);
2088     }
2089
2090   fini_pre ();
2091 }
2092
2093
2094 /* Gate and execute functions for PRE.  */
2095
2096 static void
2097 do_pre (void)
2098 {
2099   execute_pre (false);
2100 }
2101
2102 static bool
2103 gate_pre (void)
2104 {
2105   return flag_tree_pre != 0;
2106 }
2107
2108 struct tree_opt_pass pass_pre =
2109 {
2110   "pre",                                /* name */
2111   gate_pre,                             /* gate */
2112   do_pre,                               /* execute */
2113   NULL,                                 /* sub */
2114   NULL,                                 /* next */
2115   0,                                    /* static_pass_number */
2116   TV_TREE_PRE,                          /* tv_id */
2117   PROP_no_crit_edges | PROP_cfg
2118     | PROP_ssa | PROP_alias,            /* properties_required */
2119   0,                                    /* properties_provided */
2120   0,                                    /* properties_destroyed */
2121   0,                                    /* todo_flags_start */
2122   TODO_dump_func | TODO_ggc_collect | TODO_verify_ssa, /* todo_flags_finish */
2123   0                                     /* letter */
2124 };
2125
2126
2127 /* Gate and execute functions for FRE.  */
2128
2129 static void
2130 do_fre (void)
2131 {
2132   execute_pre (true);
2133 }
2134
2135 static bool
2136 gate_fre (void)
2137 {
2138   return flag_tree_fre != 0;
2139 }
2140
2141 struct tree_opt_pass pass_fre =
2142 {
2143   "fre",                                /* name */
2144   gate_fre,                             /* gate */
2145   do_fre,                               /* execute */
2146   NULL,                                 /* sub */
2147   NULL,                                 /* next */
2148   0,                                    /* static_pass_number */
2149   TV_TREE_FRE,                          /* tv_id */
2150   PROP_cfg | PROP_ssa | PROP_alias,     /* properties_required */
2151   0,                                    /* properties_provided */
2152   0,                                    /* properties_destroyed */
2153   0,                                    /* todo_flags_start */
2154   TODO_dump_func | TODO_ggc_collect | TODO_verify_ssa, /* todo_flags_finish */
2155   0                                     /* letter */
2156 };