OSDN Git Service

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