OSDN Git Service

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