OSDN Git Service

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