OSDN Git Service

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