OSDN Git Service

* targhooks.c (default_unwind_emit, default_scalar_mode_supported_p):
[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   gcc_assert (set->indexed);
448
449   if (!set->values)
450     return;
451
452   bitmap_clear_bit (set->values, VALUE_HANDLE_ID (v));
453 }
454
455
456 /* Insert the value number V into the bitmap of values existing in
457    SET.  */
458
459 static inline void
460 value_insert_into_set_bitmap (value_set_t set, tree v)
461 {
462   gcc_assert (set->indexed);
463
464   if (set->values == NULL)
465     {
466       set->values = BITMAP_OBSTACK_ALLOC (&grand_bitmap_obstack);
467       bitmap_clear (set->values);
468     }
469
470   bitmap_set_bit (set->values, VALUE_HANDLE_ID (v));
471 }
472
473
474 /* Create a new bitmap set and return it.  */
475
476 static bitmap_set_t 
477 bitmap_set_new (void)
478 {
479   bitmap_set_t ret = pool_alloc (bitmap_set_pool);
480   ret->expressions = BITMAP_OBSTACK_ALLOC (&grand_bitmap_obstack);
481   ret->values = BITMAP_OBSTACK_ALLOC (&grand_bitmap_obstack);
482   bitmap_clear (ret->expressions);
483   bitmap_clear (ret->values);
484   return ret;
485 }
486
487 /* Create a new set.  */
488
489 static value_set_t
490 set_new  (bool indexed)
491 {
492   value_set_t ret;
493   ret = pool_alloc (value_set_pool);
494   ret->head = ret->tail = NULL;
495   ret->length = 0;
496   ret->indexed = indexed;
497   ret->values = NULL;
498   return ret;
499 }
500
501 /* Insert an expression EXPR into a bitmapped set.  */
502
503 static void
504 bitmap_insert_into_set (bitmap_set_t set, tree expr)
505 {
506   tree val;
507   /* XXX: For now, we only let SSA_NAMES into the bitmap sets.  */
508   gcc_assert (TREE_CODE (expr) == SSA_NAME);
509   val = get_value_handle (expr);
510   
511   gcc_assert (val);
512   if (!is_gimple_min_invariant (val))
513     bitmap_set_bit (set->values, VALUE_HANDLE_ID (val));
514   bitmap_set_bit (set->expressions, SSA_NAME_VERSION (expr));
515 }
516
517 /* Insert EXPR into SET.  */
518
519 static void
520 insert_into_set (value_set_t set, tree expr)
521 {
522   value_set_node_t newnode = pool_alloc (value_set_node_pool);
523   tree val = get_value_handle (expr);
524   gcc_assert (val);
525
526   /* For indexed sets, insert the value into the set value bitmap.
527      For all sets, add it to the linked list and increment the list
528      length.  */
529   if (set->indexed)
530     value_insert_into_set_bitmap (set, val);
531
532   newnode->next = NULL;
533   newnode->expr = expr;
534   set->length ++;
535   if (set->head == NULL)
536     {
537       set->head = set->tail = newnode;
538     }
539   else
540     {
541       set->tail->next = newnode;
542       set->tail = newnode;
543     }
544 }
545
546 /* Copy a bitmapped set ORIG, into bitmapped set DEST.  */
547
548 static void
549 bitmap_set_copy (bitmap_set_t dest, bitmap_set_t orig)
550 {
551   bitmap_copy (dest->expressions, orig->expressions);
552   bitmap_copy (dest->values, orig->values);
553 }
554
555 /* Copy the set ORIG to the set DEST.  */
556
557 static void
558 set_copy (value_set_t dest, value_set_t orig)
559 {
560   value_set_node_t node;
561  
562   if (!orig || !orig->head)
563     return;
564
565   for (node = orig->head;
566        node;
567        node = node->next)
568     {
569       insert_into_set (dest, node->expr);
570     }
571 }
572
573 /* Remove EXPR from SET.  */
574
575 static void
576 set_remove (value_set_t set, tree expr)
577 {
578   value_set_node_t node, prev;
579
580   /* Remove the value of EXPR from the bitmap, decrement the set
581      length, and remove it from the actual double linked list.  */ 
582   value_remove_from_set_bitmap (set, get_value_handle (expr));
583   set->length--;
584   prev = NULL;
585   for (node = set->head; 
586        node != NULL; 
587        prev = node, node = node->next)
588     {
589       if (node->expr == expr)
590         {
591           if (prev == NULL)
592             set->head = node->next;
593           else
594             prev->next= node->next;
595  
596           if (node == set->tail)
597             set->tail = prev;
598           pool_free (value_set_node_pool, node);
599           return;
600         }
601     }
602 }
603
604 /* Return true if SET contains the value VAL.  */
605
606 static bool
607 set_contains_value (value_set_t set, tree val)
608 {
609   /* All constants are in every set.  */
610   if (is_gimple_min_invariant (val))
611     return true;
612   
613   if (set->length == 0)
614     return false;
615   
616   return value_exists_in_set_bitmap (set, val);
617 }
618
619 /* Return true if bitmapped set SET contains the expression EXPR.  */
620 static bool
621 bitmap_set_contains (bitmap_set_t set, tree expr)
622 {
623   /* All constants are in every set.  */
624   if (is_gimple_min_invariant (get_value_handle (expr)))
625     return true;
626
627   /* XXX: Bitmapped sets only contain SSA_NAME's for now.  */
628   if (TREE_CODE (expr) != SSA_NAME)
629     return false;
630   return bitmap_bit_p (set->expressions, SSA_NAME_VERSION (expr));
631 }
632
633   
634 /* Return true if bitmapped set SET contains the value VAL.  */
635
636 static bool
637 bitmap_set_contains_value (bitmap_set_t set, tree val)
638 {
639   if (is_gimple_min_invariant (val))
640     return true;
641   return bitmap_bit_p (set->values, VALUE_HANDLE_ID (val));
642 }
643
644 /* Replace an instance of value LOOKFOR with expression EXPR in SET.  */
645
646 static void
647 bitmap_set_replace_value (bitmap_set_t set, tree lookfor, tree expr)
648 {
649   value_set_t exprset;
650   value_set_node_t node;
651   if (is_gimple_min_invariant (lookfor))
652     return;
653   if (!bitmap_set_contains_value (set, lookfor))
654     return;
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.  */
717
718 static void
719 bitmap_value_replace_in_set (bitmap_set_t set, tree expr)
720 {
721   tree val = get_value_handle (expr);
722   bitmap_set_replace_value (set, val, expr);
723 }
724
725 /* Insert EXPR into SET if EXPR's value is not already present in
726    SET.  */
727
728 static void
729 bitmap_value_insert_into_set (bitmap_set_t set, tree expr)
730 {
731   tree val = get_value_handle (expr);
732
733   if (is_gimple_min_invariant (val))
734     return;
735   
736   if (!bitmap_set_contains_value (set, val))
737     bitmap_insert_into_set (set, expr);
738 }
739
740 /* Insert the value for EXPR into SET, if it doesn't exist already.  */
741
742 static void
743 value_insert_into_set (value_set_t set, tree expr)
744 {
745   tree val = get_value_handle (expr);
746
747   /* Constant and invariant values exist everywhere, and thus,
748      actually keeping them in the sets is pointless.  */
749   if (is_gimple_min_invariant (val))
750     return;
751
752   if (!set_contains_value (set, val))
753     insert_into_set (set, expr);
754 }
755
756
757 /* Print out SET to OUTFILE.  */
758
759 static void
760 bitmap_print_value_set (FILE *outfile, bitmap_set_t set,
761                         const char *setname, int blockindex)
762 {
763   fprintf (outfile, "%s[%d] := { ", setname, blockindex);
764   if (set)
765     {
766       int i;
767       EXECUTE_IF_SET_IN_BITMAP (set->expressions, 0, i,
768       {
769         print_generic_expr (outfile, ssa_name (i), 0);
770         
771         fprintf (outfile, " (");
772         print_generic_expr (outfile, get_value_handle (ssa_name (i)), 0);
773         fprintf (outfile, ") ");
774         if (bitmap_last_set_bit (set->expressions) != i)
775           fprintf (outfile, ", ");
776       });
777     }
778   fprintf (outfile, " }\n");
779 }
780 /* Print out the value_set SET to OUTFILE.  */
781
782 static void
783 print_value_set (FILE *outfile, value_set_t set,
784                  const char *setname, int blockindex)
785 {
786   value_set_node_t node;
787   fprintf (outfile, "%s[%d] := { ", setname, blockindex);
788   if (set)
789     {
790       for (node = set->head;
791            node;
792            node = node->next)
793         {
794           print_generic_expr (outfile, node->expr, 0);
795           
796           fprintf (outfile, " (");
797           print_generic_expr (outfile, get_value_handle (node->expr), 0);
798           fprintf (outfile, ") ");
799                      
800           if (node->next)
801             fprintf (outfile, ", ");
802         }
803     }
804
805   fprintf (outfile, " }\n");
806 }
807
808 /* Print out the expressions that have VAL to OUTFILE.  */
809
810 void
811 print_value_expressions (FILE *outfile, tree val)
812 {
813   if (VALUE_HANDLE_EXPR_SET (val))
814     {
815       char s[10];
816       sprintf (s, "VH.%04d", VALUE_HANDLE_ID (val));
817       print_value_set (outfile, VALUE_HANDLE_EXPR_SET (val), s, 0);
818     }
819 }
820
821
822 void
823 debug_value_expressions (tree val)
824 {
825   print_value_expressions (stderr, val);
826 }
827
828   
829 void debug_value_set (value_set_t, const char *, int);
830
831 void
832 debug_value_set (value_set_t set, const char *setname, int blockindex)
833 {
834   print_value_set (stderr, set, setname, blockindex);
835 }
836
837 /* Translate EXPR using phis in PHIBLOCK, so that it has the values of
838    the phis in PRED.  Return NULL if we can't find a leader for each
839    part of the translated expression.  */
840
841 static tree
842 phi_translate (tree expr, value_set_t set, basic_block pred,
843                basic_block phiblock)
844 {
845   tree phitrans = NULL;
846   tree oldexpr = expr;
847   
848   if (expr == NULL)
849     return NULL;
850
851   /* Phi translations of a given expression don't change,  */
852   phitrans = phi_trans_lookup (expr, pred);
853   if (phitrans)
854     return phitrans;
855   
856   
857   switch (TREE_CODE_CLASS (TREE_CODE (expr)))
858     {
859     case '2':
860       {
861         tree oldop1 = TREE_OPERAND (expr, 0);
862         tree oldop2 = TREE_OPERAND (expr, 1);
863         tree newop1;
864         tree newop2;
865         tree newexpr;
866         
867         newop1 = phi_translate (find_leader (set, oldop1),
868                                 set, pred, phiblock);
869         if (newop1 == NULL)
870           return NULL;
871         newop2 = phi_translate (find_leader (set, oldop2),
872                                 set, pred, phiblock);
873         if (newop2 == NULL)
874           return NULL;
875         if (newop1 != oldop1 || newop2 != oldop2)
876           {
877             newexpr = pool_alloc (binary_node_pool);
878             memcpy (newexpr, expr, tree_size (expr));
879             create_tree_ann (newexpr);
880             TREE_OPERAND (newexpr, 0) = newop1 == oldop1 ? oldop1 : get_value_handle (newop1);
881             TREE_OPERAND (newexpr, 1) = newop2 == oldop2 ? oldop2 : get_value_handle (newop2);
882             vn_lookup_or_add (newexpr, NULL);
883             expr = newexpr;
884             phi_trans_add (oldexpr, newexpr, pred);         
885           }
886       }
887       break;
888       /* XXX: Until we have PRE of loads working, none will be ANTIC.
889        */
890     case 'r':
891       return NULL;
892       break;
893     case '1':
894       {
895         tree oldop1 = TREE_OPERAND (expr, 0);
896         tree newop1;
897         tree newexpr;
898
899         newop1 = phi_translate (find_leader (set, oldop1),
900                                 set, pred, phiblock);
901         if (newop1 == NULL)
902           return NULL;
903         if (newop1 != oldop1)
904           {
905             newexpr = pool_alloc (unary_node_pool);
906             memcpy (newexpr, expr, tree_size (expr));
907             create_tree_ann (newexpr);   
908             TREE_OPERAND (newexpr, 0) = get_value_handle (newop1);
909             vn_lookup_or_add (newexpr, NULL);
910             expr = newexpr;
911             phi_trans_add (oldexpr, newexpr, pred);
912           }
913       }
914       break;
915     case 'd':
916       gcc_unreachable ();
917     case 'x':
918       {
919         tree phi = NULL;
920         int i;
921         gcc_assert (TREE_CODE (expr) == SSA_NAME);
922         if (TREE_CODE (SSA_NAME_DEF_STMT (expr)) == PHI_NODE)
923           phi = SSA_NAME_DEF_STMT (expr);
924         else
925           return expr;
926         
927         for (i = 0; i < PHI_NUM_ARGS (phi); i++)
928           if (PHI_ARG_EDGE (phi, i)->src == pred)
929             {
930               tree val;
931               if (is_undefined_value (PHI_ARG_DEF (phi, i)))
932                 return NULL;
933               val = vn_lookup_or_add (PHI_ARG_DEF (phi, i), NULL);
934               return PHI_ARG_DEF (phi, i);
935             }
936       }
937       break;
938     }
939   return expr;
940 }
941
942 static void
943 phi_translate_set (value_set_t dest, value_set_t set, basic_block pred,
944                    basic_block phiblock)
945 {
946   value_set_node_t node;
947   for (node = set->head;
948        node;
949        node = node->next)
950     {
951       tree translated;
952       translated = phi_translate (node->expr, set, pred, phiblock);
953       phi_trans_add (node->expr, translated, pred);
954       
955       if (translated != NULL)
956         value_insert_into_set (dest, translated);
957     } 
958 }
959
960 /* Find the leader for a value (i.e., the name representing that
961    value) in a given set, and return it.  Return NULL if no leader is
962    found.  */
963
964 static tree
965 bitmap_find_leader (bitmap_set_t set, tree val)
966 {
967   if (val == NULL)
968     return NULL;
969   
970   if (is_gimple_min_invariant (val))
971     return val;
972   if (bitmap_set_contains_value (set, val))
973     {
974       /* Rather than walk the entire bitmap of expressions, and see
975          whether any of them has the value we are looking for, we look
976          at the reverse mapping, which tells us the set of expressions
977          that have a given value (IE value->expressions with that
978          value) and see if any of those expressions are in our set.
979          The number of expressions per value is usually significantly
980          less than the number of expressions in the set.  In fact, for
981          large testcases, doing it this way is roughly 5-10x faster
982          than walking the bitmap.
983          If this is somehow a significant lose for some cases, we can
984          choose which set to walk based on which set is smaller.  */     
985       value_set_t exprset;
986       value_set_node_t node;
987       exprset = VALUE_HANDLE_EXPR_SET (val);
988       for (node = exprset->head; node; node = node->next)
989         {
990           if (TREE_CODE (node->expr) == SSA_NAME)
991             {
992               if (bitmap_bit_p (set->expressions, 
993                                 SSA_NAME_VERSION (node->expr)))
994                 return node->expr;
995             }
996         }
997     }
998   return NULL;
999 }
1000
1001         
1002 /* Find the leader for a value (i.e., the name representing that
1003    value) in a given set, and return it.  Return NULL if no leader is
1004    found.  */
1005
1006 static tree
1007 find_leader (value_set_t set, tree val)
1008 {
1009   value_set_node_t node;
1010
1011   if (val == NULL)
1012     return NULL;
1013
1014   /* Constants represent themselves.  */
1015   if (is_gimple_min_invariant (val))
1016     return val;
1017
1018   if (set->length == 0)
1019     return NULL;
1020   
1021   if (value_exists_in_set_bitmap (set, val))
1022     {
1023       for (node = set->head;
1024            node;
1025            node = node->next)
1026         {
1027           if (get_value_handle (node->expr) == val)
1028             return node->expr;
1029         }
1030     }
1031
1032   return NULL;
1033 }
1034
1035 /* Determine if the expression EXPR is valid in SET.  This means that
1036    we have a leader for each part of the expression (if it consists of
1037    values), or the expression is an SSA_NAME.  
1038
1039    NB:  We never should run into a case where we have SSA_NAME +
1040    SSA_NAME or SSA_NAME + value.  The sets valid_in_set is called on,
1041    the ANTIC sets, will only ever have SSA_NAME's or binary value
1042    expression (IE VALUE1 + VALUE2)  */
1043
1044 static bool
1045 valid_in_set (value_set_t set, tree expr)
1046 {
1047   switch (TREE_CODE_CLASS (TREE_CODE (expr)))
1048     {
1049     case '2':
1050       {
1051         tree op1 = TREE_OPERAND (expr, 0);
1052         tree op2 = TREE_OPERAND (expr, 1);
1053         return set_contains_value (set, op1) && set_contains_value (set, op2);
1054       }
1055       break;
1056     case '1':
1057       {
1058         tree op1 = TREE_OPERAND (expr, 0);
1059         return set_contains_value (set, op1);
1060       }
1061       break;
1062       /* XXX: Until PRE of loads works, no reference nodes are ANTIC.
1063        */
1064     case 'r':
1065       {
1066         return false;
1067       }
1068     case 'x':
1069       {
1070         gcc_assert (TREE_CODE (expr) == SSA_NAME);
1071         return true;
1072       }
1073     case 'c':
1074       gcc_unreachable ();
1075     }
1076   return false;
1077 }
1078
1079 /* Clean the set of expressions that are no longer valid in SET.  This
1080    means expressions that are made up of values we have no leaders for
1081    in SET.  */
1082
1083 static void
1084 clean (value_set_t set)
1085 {
1086   value_set_node_t node;
1087   value_set_node_t next;
1088   node = set->head;
1089   while (node)
1090     {
1091       next = node->next;
1092       if (!valid_in_set (set, node->expr))      
1093         set_remove (set, node->expr);
1094       node = next;
1095     }
1096 }
1097
1098 /* Compute the ANTIC set for BLOCK.
1099
1100 ANTIC_OUT[BLOCK] = intersection of ANTIC_IN[b] for all succ(BLOCK), if
1101 succs(BLOCK) > 1
1102 ANTIC_OUT[BLOCK] = phi_translate (ANTIC_IN[succ(BLOCK)]) if
1103 succs(BLOCK) == 1
1104
1105 ANTIC_IN[BLOCK] = clean(ANTIC_OUT[BLOCK] U EXP_GEN[BLOCK] -
1106 TMP_GEN[BLOCK])
1107
1108 Iterate until fixpointed.
1109
1110 XXX: It would be nice to either write a set_clear, and use it for
1111 antic_out, or to mark the antic_out set as deleted at the end
1112 of this routine, so that the pool can hand the same memory back out
1113 again for the next antic_out.  */
1114
1115
1116 static bool
1117 compute_antic_aux (basic_block block)
1118 {
1119   basic_block son;
1120   edge e;
1121   bool changed = false;
1122   value_set_t S, old, ANTIC_OUT;
1123   value_set_node_t node;
1124   
1125   ANTIC_OUT = S = NULL;
1126   /* If any edges from predecessors are abnormal, antic_in is empty, so
1127      punt.  Remember that the block has an incoming abnormal edge by
1128      setting the BB_VISITED flag.  */
1129   if (! (block->flags & BB_VISITED))
1130     {
1131       for (e = block->pred; e; e = e->pred_next)
1132         if (e->flags & EDGE_ABNORMAL)
1133           {
1134             block->flags |= BB_VISITED;
1135             break;
1136           }
1137     }
1138   if (block->flags & BB_VISITED)
1139     {
1140       S = NULL;
1141       goto visit_sons;
1142     }
1143   
1144
1145   old = set_new (false);
1146   set_copy (old, ANTIC_IN (block));
1147   ANTIC_OUT = set_new (true);
1148
1149   /* If the block has no successors, ANTIC_OUT is empty, because it is
1150      the exit block.  */
1151   if (block->succ == NULL);
1152
1153   /* If we have one successor, we could have some phi nodes to
1154      translate through.  */
1155   else if (block->succ->succ_next == NULL)
1156     {
1157       phi_translate_set (ANTIC_OUT, ANTIC_IN(block->succ->dest),
1158                          block, block->succ->dest);
1159     }
1160   /* If we have multiple successors, we take the intersection of all of
1161      them.  */
1162   else
1163     {
1164       varray_type worklist;
1165       edge e;
1166       size_t i;
1167       basic_block bprime, first;
1168
1169       VARRAY_BB_INIT (worklist, 1, "succ");
1170       e = block->succ;
1171       while (e)
1172         {
1173           VARRAY_PUSH_BB (worklist, e->dest);
1174           e = e->succ_next;
1175         }
1176       first = VARRAY_BB (worklist, 0);
1177       set_copy (ANTIC_OUT, ANTIC_IN (first));
1178
1179       for (i = 1; i < VARRAY_ACTIVE_SIZE (worklist); i++)
1180         {
1181           bprime = VARRAY_BB (worklist, i);
1182           node = ANTIC_OUT->head;
1183           while (node)
1184             {
1185               tree val;
1186               value_set_node_t next = node->next;
1187               val = get_value_handle (node->expr);
1188               if (!set_contains_value (ANTIC_IN (bprime), val))
1189                 set_remove (ANTIC_OUT, node->expr);
1190               node = next;
1191             }
1192         }
1193       VARRAY_CLEAR (worklist);
1194     }
1195
1196   /* Generate ANTIC_OUT - TMP_GEN */
1197   S = bitmap_set_subtract_from_value_set (ANTIC_OUT, TMP_GEN (block), false);
1198
1199   /* Start ANTIC_IN with EXP_GEN - TMP_GEN */
1200   ANTIC_IN (block) = bitmap_set_subtract_from_value_set (EXP_GEN (block), 
1201                                                          TMP_GEN (block),
1202                                                          true);
1203   
1204   /* Then union in the ANTIC_OUT - TMP_GEN values, to get ANTIC_OUT U
1205      EXP_GEN - TMP_GEN */
1206   for (node = S->head;
1207        node;
1208        node = node->next)
1209     {
1210       value_insert_into_set (ANTIC_IN (block), node->expr);
1211     }
1212   clean (ANTIC_IN (block));
1213   
1214
1215   if (!set_equal (old, ANTIC_IN (block)))
1216     changed = true;
1217
1218  visit_sons:
1219   if (dump_file && (dump_flags & TDF_DETAILS))
1220     {
1221       if (ANTIC_OUT)
1222         print_value_set (dump_file, ANTIC_OUT, "ANTIC_OUT", block->index);
1223       print_value_set (dump_file, ANTIC_IN (block), "ANTIC_IN", block->index);
1224       if (S)
1225         print_value_set (dump_file, S, "S", block->index);
1226
1227     }
1228
1229   for (son = first_dom_son (CDI_POST_DOMINATORS, block);
1230        son;
1231        son = next_dom_son (CDI_POST_DOMINATORS, son))
1232     {
1233       changed |= compute_antic_aux (son);
1234     }
1235   return changed;
1236 }
1237
1238 /* Compute ANTIC sets.  */
1239
1240 static void
1241 compute_antic (void)
1242 {
1243   bool changed = true;
1244   basic_block bb;
1245   int num_iterations = 0;
1246   FOR_ALL_BB (bb)
1247     {
1248       ANTIC_IN (bb) = set_new (true);
1249       gcc_assert (!(bb->flags & BB_VISITED));
1250     }
1251
1252   while (changed)
1253     {
1254       num_iterations++;
1255       changed = false;
1256       changed = compute_antic_aux (EXIT_BLOCK_PTR);
1257     }
1258   FOR_ALL_BB (bb)
1259     {
1260       bb->flags &= ~BB_VISITED;
1261     }
1262   if (num_iterations > 2 && dump_file && (dump_flags & TDF_STATS))
1263     fprintf (dump_file, "compute_antic required %d iterations\n", num_iterations);
1264 }
1265
1266
1267 /* Find a leader for an expression, or generate one using
1268    create_expression_by_pieces if it's ANTIC but
1269    complex.  
1270    BLOCK is the basic_block we are looking for leaders in.
1271    EXPR is the expression to find a leader or generate for. 
1272    STMTS is the statement list to put the inserted expressions on.
1273    Returns the SSA_NAME of the LHS of the generated expression or the
1274    leader.  */
1275
1276 static tree
1277 find_or_generate_expression (basic_block block, tree expr, tree stmts)
1278 {
1279   tree genop;
1280   genop = bitmap_find_leader (AVAIL_OUT (block), expr);
1281   /* Depending on the order we process DOM branches in, the value
1282      may not have propagated to all the dom children yet during
1283      this iteration.  In this case, the value will always be in
1284      the NEW_SETS for us already, having been propagated from our
1285      dominator.  */
1286   if (genop == NULL)
1287     genop = bitmap_find_leader (NEW_SETS (block), expr);
1288   /* If it's still NULL, see if it is a complex expression, and if
1289      so, generate it recursively, otherwise, abort, because it's
1290      not really .  */
1291   if (genop == NULL)
1292     {
1293       genop = VALUE_HANDLE_EXPR_SET (expr)->head->expr;
1294       gcc_assert (TREE_CODE_CLASS (TREE_CODE (genop)) == '1'
1295                   || TREE_CODE_CLASS (TREE_CODE (genop)) == '2'
1296                   || TREE_CODE_CLASS (TREE_CODE (genop)) == 'r');
1297       genop = create_expression_by_pieces (block, genop, stmts);
1298     }
1299   return genop;
1300 }
1301
1302   
1303 /* Create an expression in pieces, so that we can handle very complex
1304    expressions that may be ANTIC, but not necessary GIMPLE.  
1305    BLOCK is the basic block the expression will be inserted into,
1306    EXPR is the expression to insert (in value form)
1307    STMTS is a statement list to append the necessary insertions into.
1308
1309    This function will abort if we hit some value that shouldn't be
1310    ANTIC but is (IE there is no leader for it, or its components).
1311    This function may also generate expressions that are themselves
1312    partially or fully redundant.  Those that are will be either made
1313    fully redundant during the next iteration of insert (for partially
1314    redundant ones), or eliminated by eliminate (for fully redundant
1315    ones).  */
1316
1317 static tree
1318 create_expression_by_pieces (basic_block block, tree expr, tree stmts)
1319 {
1320   tree name = NULL_TREE;
1321   tree newexpr = NULL_TREE;
1322   tree v;
1323   
1324   switch (TREE_CODE_CLASS (TREE_CODE (expr)))
1325     {
1326     case '2':
1327       {
1328         tree_stmt_iterator tsi;
1329         tree genop1, genop2;
1330         tree temp;
1331         tree op1 = TREE_OPERAND (expr, 0);
1332         tree op2 = TREE_OPERAND (expr, 1);
1333         genop1 = find_or_generate_expression (block, op1, stmts);
1334         genop2 = find_or_generate_expression (block, op2, stmts);
1335         temp = create_tmp_var (TREE_TYPE (expr), "pretmp");
1336         add_referenced_tmp_var (temp);
1337         newexpr = build (TREE_CODE (expr), TREE_TYPE (expr), 
1338                          genop1, genop2);
1339         newexpr = build (MODIFY_EXPR, TREE_TYPE (expr),
1340                          temp, newexpr);
1341         name = make_ssa_name (temp, newexpr);
1342         TREE_OPERAND (newexpr, 0) = name;
1343         tsi = tsi_last (stmts);
1344         tsi_link_after (&tsi, newexpr, TSI_CONTINUE_LINKING);
1345         pre_stats.insertions++;
1346         break;
1347       }
1348     case '1':
1349       {
1350         tree_stmt_iterator tsi;
1351         tree genop1;
1352         tree temp;
1353         tree op1 = TREE_OPERAND (expr, 0);
1354         genop1 = find_or_generate_expression (block, op1, stmts);
1355         temp = create_tmp_var (TREE_TYPE (expr), "pretmp");
1356         add_referenced_tmp_var (temp);
1357         newexpr = build (TREE_CODE (expr), TREE_TYPE (expr), 
1358                          genop1);
1359         newexpr = build (MODIFY_EXPR, TREE_TYPE (expr),
1360                          temp, newexpr);
1361         name = make_ssa_name (temp, newexpr);
1362         TREE_OPERAND (newexpr, 0) = name;
1363         tsi = tsi_last (stmts);
1364         tsi_link_after (&tsi, newexpr, TSI_CONTINUE_LINKING);
1365         pre_stats.insertions++;
1366
1367         break;
1368       }
1369     default:
1370       gcc_unreachable ();
1371       
1372     }
1373   v = get_value_handle (expr);
1374   vn_add (name, v, NULL);
1375   bitmap_insert_into_set (NEW_SETS (block), name);
1376   bitmap_value_insert_into_set (AVAIL_OUT (block), name);
1377   if (dump_file && (dump_flags & TDF_DETAILS))
1378     {                               
1379       fprintf (dump_file, "Inserted ");
1380       print_generic_expr (dump_file, newexpr, 0);
1381       fprintf (dump_file, " in predecessor %d\n", block->index);
1382     }
1383   return name;
1384 }
1385       
1386 /* Perform insertion of partially redundant values.
1387    For BLOCK, do the following:
1388    1.  Propagate the NEW_SETS of the dominator into the current block.
1389    If the block has multiple predecessors, 
1390        2a. Iterate over the ANTIC expressions for the block to see if
1391            any of them are partially redundant.
1392        2b. If so, insert them into the necessary predecessors to make
1393            the expression fully redundant.
1394        2c. Insert a new PHI merging the values of the predecessors.
1395        2d. Insert the new PHI, and the new expressions, into the
1396            NEW_SETS set.  
1397    3. Recursively call ourselves on the dominator children of BLOCK.
1398
1399 */
1400 static bool
1401 insert_aux (basic_block block)
1402 {
1403   basic_block son;
1404   bool new_stuff = false;
1405
1406   if (block)
1407     {
1408       basic_block dom;
1409       dom = get_immediate_dominator (CDI_DOMINATORS, block);
1410       if (dom)
1411         {
1412           int i;
1413           bitmap_set_t newset = NEW_SETS (dom);
1414           EXECUTE_IF_SET_IN_BITMAP (newset->expressions, 0, i,
1415           {
1416             bitmap_insert_into_set (NEW_SETS (block), ssa_name (i));
1417             bitmap_value_replace_in_set (AVAIL_OUT (block), ssa_name (i));
1418           });
1419           if (block->pred->pred_next)
1420             {
1421               value_set_node_t node;
1422               for (node = ANTIC_IN (block)->head;
1423                    node;
1424                    node = node->next)
1425                 {
1426                   if (TREE_CODE_CLASS (TREE_CODE (node->expr)) == '2'
1427                       || TREE_CODE_CLASS (TREE_CODE (node->expr)) == '1')
1428                     {
1429                       tree *avail;
1430                       tree val;
1431                       bool by_some = false;
1432                       bool cant_insert = false;
1433                       bool all_same = true;
1434                       tree first_s = NULL;
1435                       edge pred;
1436                       basic_block bprime;
1437                       tree eprime;
1438
1439                       val = get_value_handle (node->expr);
1440                       if (bitmap_set_contains_value (PHI_GEN (block), val))
1441                         continue; 
1442                       if (bitmap_set_contains_value (AVAIL_OUT (dom), val))
1443                         {
1444                           if (dump_file && (dump_flags & TDF_DETAILS))
1445                             fprintf (dump_file, "Found fully redundant value\n");
1446                           continue;
1447                         }
1448                                     
1449                       avail = xcalloc (last_basic_block, sizeof (tree));
1450                       for (pred = block->pred;
1451                            pred;
1452                            pred = pred->pred_next)
1453                         {
1454                           tree vprime;
1455                           tree edoubleprime;
1456
1457                           /* This can happen in the very weird case
1458                              that our fake infinite loop edges have caused a
1459                              critical edge to appear.  */
1460                           if (EDGE_CRITICAL_P (pred))
1461                             {
1462                               cant_insert = true;
1463                               break;
1464                             }
1465                           bprime = pred->src;
1466                           eprime = phi_translate (node->expr,
1467                                                   ANTIC_IN (block),
1468                                                   bprime, block);
1469
1470                           /* eprime will generally only be NULL if the
1471                              value of the expression, translated
1472                              through the PHI for this predecessor, is
1473                              undefined.  If that is the case, we can't
1474                              make the expression fully redundant,
1475                              because its value is undefined along a
1476                              predecessor path.  We can thus break out
1477                              early because it doesn't matter what the
1478                              rest of the results are.  */
1479                           if (eprime == NULL)
1480                             {
1481                               cant_insert = true;
1482                               break;
1483                             }
1484
1485                           vprime = get_value_handle (eprime);
1486                           gcc_assert (vprime);
1487                           edoubleprime = bitmap_find_leader (AVAIL_OUT (bprime),
1488                                                              vprime);
1489                           if (edoubleprime == NULL)
1490                             {
1491                               avail[bprime->index] = eprime;
1492                               all_same = false;
1493                             }
1494                           else
1495                             {
1496                               avail[bprime->index] = edoubleprime;
1497                               by_some = true; 
1498                               if (first_s == NULL)
1499                                 first_s = edoubleprime;
1500                               else if (first_s != edoubleprime)
1501                                 all_same = false;
1502                               gcc_assert (first_s == edoubleprime 
1503                                           || !operand_equal_p
1504                                               (first_s, edoubleprime, 0));
1505                             }
1506                         }
1507                       /* If we can insert it, it's not the same value
1508                          already existing along every predecessor, and
1509                          it's defined by some predecessor, it is
1510                          partially redundant.  */
1511                       if (!cant_insert && !all_same && by_some)
1512                         {
1513                           tree type = TREE_TYPE (avail[block->pred->src->index]);
1514                           tree temp;
1515                           if (dump_file && (dump_flags & TDF_DETAILS))
1516                             {
1517                               fprintf (dump_file, "Found partial redundancy for expression ");
1518                               print_generic_expr (dump_file, node->expr, 0);
1519                               fprintf (dump_file, "\n");
1520                             }
1521
1522                           /* Make the necessary insertions.  */
1523                           for (pred = block->pred;
1524                                pred;
1525                                pred = pred->pred_next)
1526                             {
1527                               tree stmts = alloc_stmt_list ();
1528                               tree builtexpr;
1529                               bprime = pred->src;
1530                               eprime = avail[bprime->index];
1531                               if (TREE_CODE_CLASS (TREE_CODE (eprime)) == '2'
1532                                   || TREE_CODE_CLASS (TREE_CODE (eprime)) == '1')
1533                                 {
1534                                   builtexpr = create_expression_by_pieces (bprime,
1535                                                                            eprime,
1536                                                                            stmts);
1537                                   bsi_insert_on_edge (pred, stmts);
1538                                   bsi_commit_edge_inserts (NULL);
1539                                   avail[bprime->index] = builtexpr;
1540                                 }                             
1541                             } 
1542                           /* Now build a phi for the new variable.  */
1543                           temp = create_tmp_var (type, "prephitmp");
1544                           add_referenced_tmp_var (temp);
1545                           temp = create_phi_node (temp, block);
1546                           vn_add (PHI_RESULT (temp), val, NULL);
1547
1548 #if 0
1549                           if (!set_contains_value (AVAIL_OUT (block), val))
1550                             insert_into_set (AVAIL_OUT (block), 
1551                                              PHI_RESULT (temp));
1552                           else
1553 #endif
1554                             bitmap_value_replace_in_set (AVAIL_OUT (block), 
1555                                                          PHI_RESULT (temp));
1556                           for (pred = block->pred;
1557                                pred;
1558                                pred = pred->pred_next)
1559                             {
1560                               add_phi_arg (&temp, avail[pred->src->index],
1561                                            pred);
1562                             }
1563                           if (dump_file && (dump_flags & TDF_DETAILS))
1564                             {
1565                               fprintf (dump_file, "Created phi ");
1566                               print_generic_expr (dump_file, temp, 0);
1567                               fprintf (dump_file, " in block %d\n", block->index);
1568                             }
1569                           pre_stats.phis++;
1570                           new_stuff = true;
1571                           bitmap_insert_into_set (NEW_SETS (block),
1572                                                   PHI_RESULT (temp));
1573                           bitmap_insert_into_set (PHI_GEN (block),
1574                                                   PHI_RESULT (temp));
1575                         }
1576
1577                       free (avail);
1578                     }
1579                 }
1580             }
1581         }
1582     }
1583   for (son = first_dom_son (CDI_DOMINATORS, block);
1584        son;
1585        son = next_dom_son (CDI_DOMINATORS, son))
1586     {
1587       new_stuff |= insert_aux (son);
1588     }
1589
1590   return new_stuff;
1591 }
1592
1593 /* Perform insertion of partially redundant values.  */
1594
1595 static void
1596 insert (void)
1597 {
1598   bool new_stuff = true;
1599   basic_block bb;
1600   int num_iterations = 0;
1601   
1602   FOR_ALL_BB (bb)
1603     NEW_SETS (bb) = bitmap_set_new ();
1604   
1605   while (new_stuff)
1606     {
1607       num_iterations++;
1608       new_stuff = false;
1609       new_stuff = insert_aux (ENTRY_BLOCK_PTR);
1610     }
1611   if (num_iterations > 2 && dump_file && (dump_flags & TDF_STATS))
1612     fprintf (dump_file, "insert required %d iterations\n", num_iterations);
1613 }
1614
1615
1616 /* Return true if VAR is an SSA variable with no defining statement in
1617    this procedure, *AND* isn't a live-on-entry parameter.  */
1618
1619 static bool
1620 is_undefined_value (tree expr)
1621 {
1622   return (TREE_CODE (expr) == SSA_NAME
1623           && IS_EMPTY_STMT (SSA_NAME_DEF_STMT (expr))
1624           /* PARM_DECLs and hard registers are always defined.  */
1625           && TREE_CODE (SSA_NAME_VAR (expr)) != PARM_DECL
1626           && !DECL_HARD_REGISTER (SSA_NAME_VAR (expr)));
1627 }
1628
1629
1630 /* Given an SSA variable VAR and an expression EXPR, compute the value
1631    number for EXPR and create a value handle (VAL) for it.  If VAR and
1632    EXPR are not the same, associate VAL with VAR.  Finally, add VAR to
1633    S1 and its value handle to S2.
1634
1635    VUSES represent the virtual use operands associated with EXPR (if
1636    any). They are used when computing the hash value for EXPR.  */
1637
1638 static inline void
1639 add_to_sets (tree var, tree expr, vuse_optype vuses, bitmap_set_t s1,
1640              bitmap_set_t s2)
1641 {
1642   tree val = vn_lookup_or_add (expr, vuses);
1643
1644   /* VAR and EXPR may be the same when processing statements for which
1645      we are not computing value numbers (e.g., non-assignments, or
1646      statements that make aliased stores).  In those cases, we are
1647      only interested in making VAR available as its own value.  */
1648   if (var != expr)
1649     vn_add (var, val, NULL);
1650
1651   bitmap_insert_into_set (s1, var);
1652   bitmap_value_insert_into_set (s2, var);
1653 }
1654
1655
1656 /* Given a unary or binary expression EXPR, create and return a new
1657    expression with the same structure as EXPR but with its operands
1658    replaced with the value handles of each of the operands of EXPR.
1659    Insert EXPR's operands into the EXP_GEN set for BLOCK.
1660
1661    VUSES represent the virtual use operands associated with EXPR (if
1662    any). They are used when computing the hash value for EXPR.  */
1663
1664 static inline tree
1665 create_value_expr_from (tree expr, basic_block block, vuse_optype vuses)
1666 {
1667   int i;
1668   enum tree_code code = TREE_CODE (expr);
1669   tree vexpr;
1670
1671   gcc_assert (TREE_CODE_CLASS (code) == '1'
1672               || TREE_CODE_CLASS (code) == '2'
1673               || TREE_CODE_CLASS (code) == 'r');
1674
1675   if (TREE_CODE_CLASS (code) == '1')
1676     vexpr = pool_alloc (unary_node_pool);
1677   else if (TREE_CODE_CLASS (code) == 'r')
1678     vexpr = pool_alloc (reference_node_pool);
1679   else
1680     vexpr = pool_alloc (binary_node_pool);
1681
1682   memcpy (vexpr, expr, tree_size (expr));
1683
1684   for (i = 0; i < TREE_CODE_LENGTH (code); i++)
1685     {
1686       tree op = TREE_OPERAND (expr, i);
1687       if (op != NULL)
1688         {
1689           tree val = vn_lookup_or_add (op, vuses);
1690           if (!is_undefined_value (op))
1691             value_insert_into_set (EXP_GEN (block), op);
1692           if (TREE_CODE (val) == VALUE_HANDLE)
1693             TREE_TYPE (val) = TREE_TYPE (TREE_OPERAND (vexpr, i));
1694           TREE_OPERAND (vexpr, i) = val;
1695         }
1696     }
1697
1698   return vexpr;
1699 }
1700
1701
1702 /* Compute the AVAIL set for BLOCK.
1703    This function performs value numbering of the statements in BLOCK. 
1704    The AVAIL sets are built from information we glean while doing this
1705    value numbering, since the AVAIL sets contain only one entry per
1706    value.
1707    
1708    AVAIL_IN[BLOCK] = AVAIL_OUT[dom(BLOCK)].
1709    AVAIL_OUT[BLOCK] = AVAIL_IN[BLOCK] U PHI_GEN[BLOCK] U TMP_GEN[BLOCK].  */
1710
1711 static void
1712 compute_avail (basic_block block)
1713 {
1714   basic_block son;
1715   
1716   /* For arguments with default definitions, we pretend they are
1717      defined in the entry block.  */
1718   if (block == ENTRY_BLOCK_PTR)
1719     {
1720       tree param;
1721       for (param = DECL_ARGUMENTS (current_function_decl);
1722            param;
1723            param = TREE_CHAIN (param))
1724         {
1725           if (default_def (param) != NULL)
1726             {
1727               tree val;
1728               tree def = default_def (param);
1729               val = vn_lookup_or_add (def, NULL);
1730               bitmap_insert_into_set (TMP_GEN (block), def);
1731               bitmap_value_insert_into_set (AVAIL_OUT (block), def);
1732             }
1733         }
1734     }
1735   else if (block)
1736     {
1737       block_stmt_iterator bsi;
1738       tree stmt, phi;
1739       basic_block dom;
1740
1741       /* Initially, the set of available values in BLOCK is that of
1742          its immediate dominator.  */
1743       dom = get_immediate_dominator (CDI_DOMINATORS, block);
1744       if (dom)
1745         bitmap_set_copy (AVAIL_OUT (block), AVAIL_OUT (dom));
1746
1747       /* Generate values for PHI nodes.  */
1748       for (phi = phi_nodes (block); phi; phi = PHI_CHAIN (phi))
1749         /* We have no need for virtual phis, as they don't represent
1750            actual computations.  */
1751         if (is_gimple_reg (PHI_RESULT (phi)))
1752           add_to_sets (PHI_RESULT (phi), PHI_RESULT (phi), NULL,
1753                        PHI_GEN (block), AVAIL_OUT (block));
1754
1755       /* Now compute value numbers and populate value sets with all
1756          the expressions computed in BLOCK.  */
1757       for (bsi = bsi_start (block); !bsi_end_p (bsi); bsi_next (&bsi))
1758         {
1759           stmt_ann_t ann;
1760           size_t j;
1761
1762           stmt = bsi_stmt (bsi);
1763           ann = stmt_ann (stmt);
1764           get_stmt_operands (stmt);
1765
1766           /* We are only interested in assignments of the form
1767              X_i = EXPR, where EXPR represents an "interesting"
1768              computation, it has no volatile operands and X_i
1769              doesn't flow through an abnormal edge.  */
1770           if (TREE_CODE (stmt) == MODIFY_EXPR
1771               && !ann->has_volatile_ops
1772               && TREE_CODE (TREE_OPERAND (stmt, 0)) == SSA_NAME
1773               && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (TREE_OPERAND (stmt, 0)))
1774             {
1775               tree lhs = TREE_OPERAND (stmt, 0);
1776               tree rhs = TREE_OPERAND (stmt, 1);
1777               vuse_optype vuses = STMT_VUSE_OPS (stmt);
1778
1779               STRIP_USELESS_TYPE_CONVERSION (rhs);
1780               if (TREE_CODE (rhs) == SSA_NAME
1781                   || is_gimple_min_invariant (rhs))
1782                 {
1783                   /* Compute a value number for the RHS of the statement
1784                      and add its value to the AVAIL_OUT set for the block.
1785                      Add the LHS to TMP_GEN.  */
1786                   add_to_sets (lhs, rhs, vuses, TMP_GEN (block), 
1787                                AVAIL_OUT (block));
1788                   
1789                   if (TREE_CODE (rhs) == SSA_NAME
1790                       && !is_undefined_value (rhs))
1791                     value_insert_into_set (EXP_GEN (block), rhs);
1792                   continue;
1793                 }          
1794               else if (TREE_CODE_CLASS (TREE_CODE (rhs)) == '1'
1795                        || TREE_CODE_CLASS (TREE_CODE (rhs)) == '2'
1796                        || TREE_CODE (rhs) == INDIRECT_REF)
1797                 {
1798                   /* For binary, unary, and reference expressions,
1799                      create a duplicate expression with the operands
1800                      replaced with the value handles of the original
1801                      RHS.  */
1802                   tree newt = create_value_expr_from (rhs, block, vuses);
1803                   add_to_sets (lhs, newt, vuses, TMP_GEN (block),
1804                                AVAIL_OUT (block));
1805                   value_insert_into_set (EXP_GEN (block), newt);
1806                   continue;
1807                 }
1808             }
1809
1810           /* For any other statement that we don't recognize, simply
1811              make the names generated by the statement available in
1812              AVAIL_OUT and TMP_GEN.  */
1813           for (j = 0; j < NUM_DEFS (STMT_DEF_OPS (stmt)); j++)
1814             {
1815               tree def = DEF_OP (STMT_DEF_OPS (stmt), j);
1816               add_to_sets (def, def, NULL, TMP_GEN (block),
1817                             AVAIL_OUT (block));
1818             }
1819
1820           for (j = 0; j < NUM_USES (STMT_USE_OPS (stmt)); j++)
1821             {
1822               tree use = USE_OP (STMT_USE_OPS (stmt), j);
1823               add_to_sets (use, use, NULL, TMP_GEN (block),
1824                             AVAIL_OUT (block));
1825             }
1826         }
1827     }
1828
1829   /* Compute available sets for the dominator children of BLOCK.  */
1830   for (son = first_dom_son (CDI_DOMINATORS, block);
1831        son;
1832        son = next_dom_son (CDI_DOMINATORS, son))
1833     compute_avail (son);
1834 }
1835
1836
1837 /* Eliminate fully redundant computations.  */
1838
1839 static void
1840 eliminate (void)
1841 {
1842   basic_block b;
1843
1844   FOR_EACH_BB (b)
1845     {
1846       block_stmt_iterator i;
1847       
1848       for (i = bsi_start (b); !bsi_end_p (i); bsi_next (&i))
1849         {
1850           tree stmt = bsi_stmt (i);
1851
1852           /* Lookup the RHS of the expression, see if we have an
1853              available computation for it.  If so, replace the RHS with
1854              the available computation.  */
1855           if (TREE_CODE (stmt) == MODIFY_EXPR
1856               && TREE_CODE (TREE_OPERAND (stmt, 0)) == SSA_NAME
1857               && TREE_CODE (TREE_OPERAND (stmt ,1)) != SSA_NAME
1858               && !is_gimple_min_invariant (TREE_OPERAND (stmt, 1))
1859               && !stmt_ann (stmt)->has_volatile_ops)
1860             {
1861               tree lhs = TREE_OPERAND (stmt, 0);
1862               tree *rhs_p = &TREE_OPERAND (stmt, 1);
1863               tree sprime;
1864
1865               sprime = bitmap_find_leader (AVAIL_OUT (b),
1866                                            vn_lookup (lhs, NULL));
1867               if (sprime 
1868                   && sprime != lhs
1869                   && (TREE_CODE (*rhs_p) != SSA_NAME
1870                       || may_propagate_copy (*rhs_p, sprime)))
1871                 {
1872                   gcc_assert (sprime != *rhs_p);
1873
1874                   if (dump_file && (dump_flags & TDF_DETAILS))
1875                     {
1876                       fprintf (dump_file, "Replaced ");
1877                       print_generic_expr (dump_file, *rhs_p, 0);
1878                       fprintf (dump_file, " with ");
1879                       print_generic_expr (dump_file, sprime, 0);
1880                       fprintf (dump_file, " in ");
1881                       print_generic_stmt (dump_file, stmt, 0);
1882                     }
1883                   pre_stats.eliminations++;
1884                   propagate_tree_value (rhs_p, sprime);
1885                   modify_stmt (stmt);
1886
1887                   /* If we removed EH side effects from the statement, clean
1888                      its EH information.  */
1889                   if (maybe_clean_eh_stmt (stmt))
1890                     {
1891                       bitmap_set_bit (need_eh_cleanup,
1892                                       bb_for_stmt (stmt)->index);
1893                       if (dump_file && (dump_flags & TDF_DETAILS))
1894                         fprintf (dump_file, "  Removed EH side effects.\n");
1895                     }
1896                 }
1897             }
1898         }
1899     }
1900 }
1901
1902
1903 /* Initialize data structures used by PRE.  */
1904
1905 static void
1906 init_pre (void)
1907 {
1908   size_t tsize;
1909   basic_block bb;
1910
1911   connect_infinite_loops_to_exit ();
1912   vn_init ();
1913   memset (&pre_stats, 0, sizeof (pre_stats));
1914
1915   /* If block 0 has more than one predecessor, it means that its PHI
1916      nodes will have arguments coming from block -1.  This creates
1917      problems for several places in PRE that keep local arrays indexed
1918      by block number.  To prevent this, we split the edge coming from
1919      ENTRY_BLOCK_PTR (FIXME, if ENTRY_BLOCK_PTR had an index number
1920      different than -1 we wouldn't have to hack this.  tree-ssa-dce.c
1921      needs a similar change).  */
1922   if (ENTRY_BLOCK_PTR->succ->dest->pred->pred_next)
1923     if (!(ENTRY_BLOCK_PTR->succ->flags & EDGE_ABNORMAL))
1924       split_edge (ENTRY_BLOCK_PTR->succ);
1925
1926   FOR_ALL_BB (bb)
1927     bb->aux = xcalloc (1, sizeof (struct bb_value_sets));
1928
1929   gcc_obstack_init (&grand_bitmap_obstack);
1930   phi_translate_table = htab_create (511, expr_pred_trans_hash,
1931                                      expr_pred_trans_eq, free);
1932   value_set_pool = create_alloc_pool ("Value sets",
1933                                       sizeof (struct value_set), 30);
1934   bitmap_set_pool = create_alloc_pool ("Bitmap sets",
1935                                        sizeof (struct bitmap_set), 30);
1936   value_set_node_pool = create_alloc_pool ("Value set nodes",
1937                                            sizeof (struct value_set_node), 30);
1938   calculate_dominance_info (CDI_POST_DOMINATORS);
1939   calculate_dominance_info (CDI_DOMINATORS);
1940   tsize = tree_size (build (PLUS_EXPR, void_type_node, NULL_TREE, NULL_TREE));
1941   binary_node_pool = create_alloc_pool ("Binary tree nodes", tsize, 30);
1942   tsize = tree_size (build1 (NEGATE_EXPR, void_type_node, NULL_TREE));
1943   unary_node_pool = create_alloc_pool ("Unary tree nodes", tsize, 30);
1944   tsize = tree_size (build (COMPONENT_REF, void_type_node, NULL_TREE,
1945                             NULL_TREE, NULL_TREE));
1946   reference_node_pool = create_alloc_pool ("Reference tree nodes", tsize, 30);
1947   FOR_ALL_BB (bb)
1948     {
1949       EXP_GEN (bb) = set_new (true);
1950       PHI_GEN (bb) = bitmap_set_new ();
1951       TMP_GEN (bb) = bitmap_set_new ();
1952       AVAIL_OUT (bb) = bitmap_set_new ();
1953     }
1954
1955   need_eh_cleanup = BITMAP_XMALLOC ();
1956 }
1957
1958
1959 /* Deallocate data structures used by PRE.  */
1960
1961 static void
1962 fini_pre (void)
1963 {
1964   basic_block bb;
1965
1966   obstack_free (&grand_bitmap_obstack, NULL);
1967   free_alloc_pool (value_set_pool);
1968   free_alloc_pool (bitmap_set_pool);
1969   free_alloc_pool (value_set_node_pool);
1970   free_alloc_pool (binary_node_pool);
1971   free_alloc_pool (reference_node_pool);
1972   free_alloc_pool (unary_node_pool);
1973   htab_delete (phi_translate_table);
1974   remove_fake_exit_edges ();
1975
1976   FOR_ALL_BB (bb)
1977     {
1978       free (bb->aux);
1979       bb->aux = NULL;
1980     }
1981
1982   free_dominance_info (CDI_POST_DOMINATORS);
1983   vn_delete ();
1984
1985   if (bitmap_first_set_bit (need_eh_cleanup) >= 0)
1986     {
1987       tree_purge_all_dead_eh_edges (need_eh_cleanup);
1988       cleanup_tree_cfg ();
1989     }
1990
1991   BITMAP_XFREE (need_eh_cleanup);
1992 }
1993
1994
1995 /* Main entry point to the SSA-PRE pass.  DO_FRE is true if the caller
1996    only wants to do full redundancy elimination.  */
1997
1998 static void
1999 execute_pre (bool do_fre)
2000 {
2001   init_pre ();
2002
2003   /* Collect and value number expressions computed in each basic
2004      block.  */
2005   compute_avail (ENTRY_BLOCK_PTR);
2006
2007   if (dump_file && (dump_flags & TDF_DETAILS))
2008     {
2009       basic_block bb;
2010
2011       FOR_ALL_BB (bb)
2012         {
2013           print_value_set (dump_file, EXP_GEN (bb), "exp_gen", bb->index);
2014           bitmap_print_value_set (dump_file, TMP_GEN (bb), "tmp_gen", 
2015                                   bb->index);
2016           bitmap_print_value_set (dump_file, AVAIL_OUT (bb), "avail_out", 
2017                                   bb->index);
2018         }
2019     }
2020
2021   /* Insert can get quite slow on an incredibly large number of basic
2022      blocks due to some quadratic behavior.  Until this behavior is
2023      fixed, don't run it when he have an incredibly large number of
2024      bb's.  If we aren't going to run insert, there is no point in
2025      computing ANTIC, either, even though it's plenty fast.  */
2026   if (!do_fre && n_basic_blocks < 4000)
2027     {
2028       compute_antic ();
2029       insert ();
2030     }
2031
2032   /* Remove all the redundant expressions.  */
2033   eliminate ();
2034   
2035   if (dump_file && (dump_flags & TDF_STATS))
2036     {
2037       fprintf (dump_file, "Insertions:%d\n", pre_stats.insertions);
2038       fprintf (dump_file, "New PHIs:%d\n", pre_stats.phis);
2039       fprintf (dump_file, "Eliminated:%d\n", pre_stats.eliminations);
2040     }
2041
2042   fini_pre ();
2043 }
2044
2045
2046 /* Gate and execute functions for PRE.  */
2047
2048 static void
2049 do_pre (void)
2050 {
2051   execute_pre (false);
2052 }
2053
2054 static bool
2055 gate_pre (void)
2056 {
2057   return flag_tree_pre != 0;
2058 }
2059
2060 struct tree_opt_pass pass_pre =
2061 {
2062   "pre",                                /* name */
2063   gate_pre,                             /* gate */
2064   do_pre,                               /* execute */
2065   NULL,                                 /* sub */
2066   NULL,                                 /* next */
2067   0,                                    /* static_pass_number */
2068   TV_TREE_PRE,                          /* tv_id */
2069   PROP_no_crit_edges | PROP_cfg
2070     | PROP_ssa | PROP_alias,            /* properties_required */
2071   0,                                    /* properties_provided */
2072   0,                                    /* properties_destroyed */
2073   0,                                    /* todo_flags_start */
2074   TODO_dump_func | TODO_ggc_collect | TODO_verify_ssa, /* todo_flags_finish */
2075   0                                     /* letter */
2076 };
2077
2078
2079 /* Gate and execute functions for FRE.  */
2080
2081 static void
2082 do_fre (void)
2083 {
2084   execute_pre (true);
2085 }
2086
2087 static bool
2088 gate_fre (void)
2089 {
2090   return flag_tree_fre != 0;
2091 }
2092
2093 struct tree_opt_pass pass_fre =
2094 {
2095   "fre",                                /* name */
2096   gate_fre,                             /* gate */
2097   do_fre,                               /* execute */
2098   NULL,                                 /* sub */
2099   NULL,                                 /* next */
2100   0,                                    /* static_pass_number */
2101   TV_TREE_FRE,                          /* tv_id */
2102   PROP_cfg | PROP_ssa | PROP_alias,     /* properties_required */
2103   0,                                    /* properties_provided */
2104   0,                                    /* properties_destroyed */
2105   0,                                    /* todo_flags_start */
2106   TODO_dump_func | TODO_ggc_collect | TODO_verify_ssa, /* todo_flags_finish */
2107   0                                     /* letter */
2108 };