OSDN Git Service

2010-04-22 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 VEC(gimple,heap) *inserted_exprs;
2612 static bitmap inserted_phi_names;
2613
2614 /* Pool allocated fake store expressions are placed onto this
2615    worklist, which, after performing dead code elimination, is walked
2616    to see which expressions need to be put into GC'able memory  */
2617 static VEC(gimple, heap) *need_creation;
2618
2619 /* The actual worker for create_component_ref_by_pieces.  */
2620
2621 static tree
2622 create_component_ref_by_pieces_1 (basic_block block, vn_reference_t ref,
2623                                   unsigned int *operand, gimple_seq *stmts,
2624                                   gimple domstmt)
2625 {
2626   vn_reference_op_t currop = VEC_index (vn_reference_op_s, ref->operands,
2627                                         *operand);
2628   tree genop;
2629   ++*operand;
2630   switch (currop->opcode)
2631     {
2632     case CALL_EXPR:
2633       {
2634         tree folded, sc = NULL_TREE;
2635         unsigned int nargs = 0;
2636         tree fn, *args;
2637         if (TREE_CODE (currop->op0) == FUNCTION_DECL)
2638           fn = currop->op0;
2639         else
2640           {
2641             pre_expr op0 = get_or_alloc_expr_for (currop->op0);
2642             fn = find_or_generate_expression (block, op0, stmts, domstmt);
2643             if (!fn)
2644               return NULL_TREE;
2645           }
2646         if (currop->op1)
2647           {
2648             pre_expr scexpr = get_or_alloc_expr_for (currop->op1);
2649             sc = find_or_generate_expression (block, scexpr, stmts, domstmt);
2650             if (!sc)
2651               return NULL_TREE;
2652           }
2653         args = XNEWVEC (tree, VEC_length (vn_reference_op_s,
2654                                           ref->operands) - 1);
2655         while (*operand < VEC_length (vn_reference_op_s, ref->operands))
2656           {
2657             args[nargs] = create_component_ref_by_pieces_1 (block, ref,
2658                                                             operand, stmts,
2659                                                             domstmt);
2660             if (!args[nargs])
2661               {
2662                 free (args);
2663                 return NULL_TREE;
2664               }
2665             nargs++;
2666           }
2667         folded = build_call_array (currop->type,
2668                                    (TREE_CODE (fn) == FUNCTION_DECL
2669                                     ? build_fold_addr_expr (fn) : fn),
2670                                    nargs, args);
2671         free (args);
2672         if (sc)
2673           CALL_EXPR_STATIC_CHAIN (folded) = sc;
2674         return folded;
2675       }
2676       break;
2677     case TARGET_MEM_REF:
2678       {
2679         vn_reference_op_t nextop = VEC_index (vn_reference_op_s, ref->operands,
2680                                               *operand);
2681         pre_expr op0expr;
2682         tree genop0 = NULL_TREE;
2683         tree baseop = create_component_ref_by_pieces_1 (block, ref, operand,
2684                                                         stmts, domstmt);
2685         if (!baseop)
2686           return NULL_TREE;
2687         if (currop->op0)
2688           {
2689             op0expr = get_or_alloc_expr_for (currop->op0);
2690             genop0 = find_or_generate_expression (block, op0expr,
2691                                                   stmts, domstmt);
2692             if (!genop0)
2693               return NULL_TREE;
2694           }
2695         if (DECL_P (baseop))
2696           return build6 (TARGET_MEM_REF, currop->type,
2697                          baseop, NULL_TREE,
2698                          genop0, currop->op1, currop->op2,
2699                          unshare_expr (nextop->op1));
2700         else
2701           return build6 (TARGET_MEM_REF, currop->type,
2702                          NULL_TREE, baseop,
2703                          genop0, currop->op1, currop->op2,
2704                          unshare_expr (nextop->op1));
2705       }
2706       break;
2707     case ADDR_EXPR:
2708       if (currop->op0)
2709         {
2710           gcc_assert (is_gimple_min_invariant (currop->op0));
2711           return currop->op0;
2712         }
2713       /* Fallthrough.  */
2714     case REALPART_EXPR:
2715     case IMAGPART_EXPR:
2716     case VIEW_CONVERT_EXPR:
2717       {
2718         tree folded;
2719         tree genop0 = create_component_ref_by_pieces_1 (block, ref,
2720                                                         operand,
2721                                                         stmts, domstmt);
2722         if (!genop0)
2723           return NULL_TREE;
2724         folded = fold_build1 (currop->opcode, currop->type,
2725                               genop0);
2726         return folded;
2727       }
2728       break;
2729     case ALIGN_INDIRECT_REF:
2730     case MISALIGNED_INDIRECT_REF:
2731     case INDIRECT_REF:
2732       {
2733         tree folded;
2734         tree genop1 = create_component_ref_by_pieces_1 (block, ref,
2735                                                         operand,
2736                                                         stmts, domstmt);
2737         if (!genop1)
2738           return NULL_TREE;
2739         genop1 = fold_convert (build_pointer_type (currop->type),
2740                                genop1);
2741
2742         if (currop->opcode == MISALIGNED_INDIRECT_REF)
2743           folded = fold_build2 (currop->opcode, currop->type,
2744                                 genop1, currop->op1);
2745         else
2746           folded = fold_build1 (currop->opcode, currop->type,
2747                                 genop1);
2748         return folded;
2749       }
2750       break;
2751     case BIT_FIELD_REF:
2752       {
2753         tree folded;
2754         tree genop0 = create_component_ref_by_pieces_1 (block, ref, operand,
2755                                                         stmts, domstmt);
2756         pre_expr op1expr = get_or_alloc_expr_for (currop->op0);
2757         pre_expr op2expr = get_or_alloc_expr_for (currop->op1);
2758         tree genop1;
2759         tree genop2;
2760
2761         if (!genop0)
2762           return NULL_TREE;
2763         genop1 = find_or_generate_expression (block, op1expr, stmts, domstmt);
2764         if (!genop1)
2765           return NULL_TREE;
2766         genop2 = find_or_generate_expression (block, op2expr, stmts, domstmt);
2767         if (!genop2)
2768           return NULL_TREE;
2769         folded = fold_build3 (BIT_FIELD_REF, currop->type, genop0, genop1,
2770                               genop2);
2771         return folded;
2772       }
2773
2774       /* For array ref vn_reference_op's, operand 1 of the array ref
2775          is op0 of the reference op and operand 3 of the array ref is
2776          op1.  */
2777     case ARRAY_RANGE_REF:
2778     case ARRAY_REF:
2779       {
2780         tree genop0;
2781         tree genop1 = currop->op0;
2782         pre_expr op1expr;
2783         tree genop2 = currop->op1;
2784         pre_expr op2expr;
2785         tree genop3 = currop->op2;
2786         pre_expr op3expr;
2787         genop0 = create_component_ref_by_pieces_1 (block, ref, operand,
2788                                                    stmts, domstmt);
2789         if (!genop0)
2790           return NULL_TREE;
2791         op1expr = get_or_alloc_expr_for (genop1);
2792         genop1 = find_or_generate_expression (block, op1expr, stmts, domstmt);
2793         if (!genop1)
2794           return NULL_TREE;
2795         if (genop2)
2796           {
2797             /* Drop zero minimum index.  */
2798             if (tree_int_cst_equal (genop2, integer_zero_node))
2799               genop2 = NULL_TREE;
2800             else
2801               {
2802                 op2expr = get_or_alloc_expr_for (genop2);
2803                 genop2 = find_or_generate_expression (block, op2expr, stmts,
2804                                                       domstmt);
2805                 if (!genop2)
2806                   return NULL_TREE;
2807               }
2808           }
2809         if (genop3)
2810           {
2811             tree elmt_type = TREE_TYPE (TREE_TYPE (genop0));
2812             /* We can't always put a size in units of the element alignment
2813                here as the element alignment may be not visible.  See
2814                PR43783.  Simply drop the element size for constant
2815                sizes.  */
2816             if (tree_int_cst_equal (genop3, TYPE_SIZE_UNIT (elmt_type)))
2817               genop3 = NULL_TREE;
2818             else
2819               {
2820                 genop3 = size_binop (EXACT_DIV_EXPR, genop3,
2821                                      size_int (TYPE_ALIGN_UNIT (elmt_type)));
2822                 op3expr = get_or_alloc_expr_for (genop3);
2823                 genop3 = find_or_generate_expression (block, op3expr, stmts,
2824                                                       domstmt);
2825                 if (!genop3)
2826                   return NULL_TREE;
2827               }
2828           }
2829         return build4 (currop->opcode, currop->type, genop0, genop1,
2830                        genop2, genop3);
2831       }
2832     case COMPONENT_REF:
2833       {
2834         tree op0;
2835         tree op1;
2836         tree genop2 = currop->op1;
2837         pre_expr op2expr;
2838         op0 = create_component_ref_by_pieces_1 (block, ref, operand,
2839                                                 stmts, domstmt);
2840         if (!op0)
2841           return NULL_TREE;
2842         /* op1 should be a FIELD_DECL, which are represented by
2843            themselves.  */
2844         op1 = currop->op0;
2845         if (genop2)
2846           {
2847             op2expr = get_or_alloc_expr_for (genop2);
2848             genop2 = find_or_generate_expression (block, op2expr, stmts,
2849                                                   domstmt);
2850             if (!genop2)
2851               return NULL_TREE;
2852           }
2853
2854         return fold_build3 (COMPONENT_REF, TREE_TYPE (op1), op0, op1,
2855                             genop2);
2856       }
2857       break;
2858     case SSA_NAME:
2859       {
2860         pre_expr op0expr = get_or_alloc_expr_for (currop->op0);
2861         genop = find_or_generate_expression (block, op0expr, stmts, domstmt);
2862         return genop;
2863       }
2864     case STRING_CST:
2865     case INTEGER_CST:
2866     case COMPLEX_CST:
2867     case VECTOR_CST:
2868     case REAL_CST:
2869     case CONSTRUCTOR:
2870     case VAR_DECL:
2871     case PARM_DECL:
2872     case CONST_DECL:
2873     case RESULT_DECL:
2874     case FUNCTION_DECL:
2875       return currop->op0;
2876
2877     default:
2878       gcc_unreachable ();
2879     }
2880 }
2881
2882 /* For COMPONENT_REF's and ARRAY_REF's, we can't have any intermediates for the
2883    COMPONENT_REF or INDIRECT_REF or ARRAY_REF portion, because we'd end up with
2884    trying to rename aggregates into ssa form directly, which is a no no.
2885
2886    Thus, this routine doesn't create temporaries, it just builds a
2887    single access expression for the array, calling
2888    find_or_generate_expression to build the innermost pieces.
2889
2890    This function is a subroutine of create_expression_by_pieces, and
2891    should not be called on it's own unless you really know what you
2892    are doing.  */
2893
2894 static tree
2895 create_component_ref_by_pieces (basic_block block, vn_reference_t ref,
2896                                 gimple_seq *stmts, gimple domstmt)
2897 {
2898   unsigned int op = 0;
2899   return create_component_ref_by_pieces_1 (block, ref, &op, stmts, domstmt);
2900 }
2901
2902 /* Find a leader for an expression, or generate one using
2903    create_expression_by_pieces if it's ANTIC but
2904    complex.
2905    BLOCK is the basic_block we are looking for leaders in.
2906    EXPR is the expression to find a leader or generate for.
2907    STMTS is the statement list to put the inserted expressions on.
2908    Returns the SSA_NAME of the LHS of the generated expression or the
2909    leader.
2910    DOMSTMT if non-NULL is a statement that should be dominated by
2911    all uses in the generated expression.  If DOMSTMT is non-NULL this
2912    routine can fail and return NULL_TREE.  Otherwise it will assert
2913    on failure.  */
2914
2915 static tree
2916 find_or_generate_expression (basic_block block, pre_expr expr,
2917                              gimple_seq *stmts, gimple domstmt)
2918 {
2919   pre_expr leader = bitmap_find_leader (AVAIL_OUT (block),
2920                                         get_expr_value_id (expr), domstmt);
2921   tree genop = NULL;
2922   if (leader)
2923     {
2924       if (leader->kind == NAME)
2925         genop = PRE_EXPR_NAME (leader);
2926       else if (leader->kind == CONSTANT)
2927         genop = PRE_EXPR_CONSTANT (leader);
2928     }
2929
2930   /* If it's still NULL, it must be a complex expression, so generate
2931      it recursively.  Not so for FRE though.  */
2932   if (genop == NULL
2933       && !in_fre)
2934     {
2935       bitmap_set_t exprset;
2936       unsigned int lookfor = get_expr_value_id (expr);
2937       bool handled = false;
2938       bitmap_iterator bi;
2939       unsigned int i;
2940
2941       exprset = VEC_index (bitmap_set_t, value_expressions, lookfor);
2942       FOR_EACH_EXPR_ID_IN_SET (exprset, i, bi)
2943         {
2944           pre_expr temp = expression_for_id (i);
2945           if (temp->kind != NAME)
2946             {
2947               handled = true;
2948               genop = create_expression_by_pieces (block, temp, stmts,
2949                                                    domstmt,
2950                                                    get_expr_type (expr));
2951               break;
2952             }
2953         }
2954       if (!handled && domstmt)
2955         return NULL_TREE;
2956
2957       gcc_assert (handled);
2958     }
2959   return genop;
2960 }
2961
2962 #define NECESSARY GF_PLF_1
2963
2964 /* Create an expression in pieces, so that we can handle very complex
2965    expressions that may be ANTIC, but not necessary GIMPLE.
2966    BLOCK is the basic block the expression will be inserted into,
2967    EXPR is the expression to insert (in value form)
2968    STMTS is a statement list to append the necessary insertions into.
2969
2970    This function will die if we hit some value that shouldn't be
2971    ANTIC but is (IE there is no leader for it, or its components).
2972    This function may also generate expressions that are themselves
2973    partially or fully redundant.  Those that are will be either made
2974    fully redundant during the next iteration of insert (for partially
2975    redundant ones), or eliminated by eliminate (for fully redundant
2976    ones).
2977
2978    If DOMSTMT is non-NULL then we make sure that all uses in the
2979    expressions dominate that statement.  In this case the function
2980    can return NULL_TREE to signal failure.  */
2981
2982 static tree
2983 create_expression_by_pieces (basic_block block, pre_expr expr,
2984                              gimple_seq *stmts, gimple domstmt, tree type)
2985 {
2986   tree temp, name;
2987   tree folded;
2988   gimple_seq forced_stmts = NULL;
2989   unsigned int value_id;
2990   gimple_stmt_iterator gsi;
2991   tree exprtype = type ? type : get_expr_type (expr);
2992   pre_expr nameexpr;
2993   gimple newstmt;
2994
2995   switch (expr->kind)
2996     {
2997       /* We may hit the NAME/CONSTANT case if we have to convert types
2998          that value numbering saw through.  */
2999     case NAME:
3000       folded = PRE_EXPR_NAME (expr);
3001       break;
3002     case CONSTANT:
3003       folded = PRE_EXPR_CONSTANT (expr);
3004       break;
3005     case REFERENCE:
3006       {
3007         vn_reference_t ref = PRE_EXPR_REFERENCE (expr);
3008         folded = create_component_ref_by_pieces (block, ref, stmts, domstmt);
3009       }
3010       break;
3011     case NARY:
3012       {
3013         vn_nary_op_t nary = PRE_EXPR_NARY (expr);
3014         switch (nary->length)
3015           {
3016           case 2:
3017             {
3018               pre_expr op1 = get_or_alloc_expr_for (nary->op[0]);
3019               pre_expr op2 = get_or_alloc_expr_for (nary->op[1]);
3020               tree genop1 = find_or_generate_expression (block, op1,
3021                                                          stmts, domstmt);
3022               tree genop2 = find_or_generate_expression (block, op2,
3023                                                          stmts, domstmt);
3024               if (!genop1 || !genop2)
3025                 return NULL_TREE;
3026               /* Ensure op2 is a sizetype for POINTER_PLUS_EXPR.  It
3027                  may be a constant with the wrong type.  */
3028               if (nary->opcode == POINTER_PLUS_EXPR)
3029                 {
3030                   genop1 = fold_convert (nary->type, genop1);
3031                   genop2 = fold_convert (sizetype, genop2);
3032                 }
3033               else
3034                 {
3035                   genop1 = fold_convert (TREE_TYPE (nary->op[0]), genop1);
3036                   genop2 = fold_convert (TREE_TYPE (nary->op[1]), genop2);
3037                 }
3038
3039               folded = fold_build2 (nary->opcode, nary->type,
3040                                     genop1, genop2);
3041             }
3042             break;
3043           case 1:
3044             {
3045               pre_expr op1 = get_or_alloc_expr_for (nary->op[0]);
3046               tree genop1 = find_or_generate_expression (block, op1,
3047                                                          stmts, domstmt);
3048               if (!genop1)
3049                 return NULL_TREE;
3050               genop1 = fold_convert (TREE_TYPE (nary->op[0]), genop1);
3051
3052               folded = fold_build1 (nary->opcode, nary->type,
3053                                     genop1);
3054             }
3055             break;
3056           default:
3057             return NULL_TREE;
3058           }
3059       }
3060       break;
3061     default:
3062       return NULL_TREE;
3063     }
3064
3065   if (!useless_type_conversion_p (exprtype, TREE_TYPE (folded)))
3066     folded = fold_convert (exprtype, folded);
3067
3068   /* Force the generated expression to be a sequence of GIMPLE
3069      statements.
3070      We have to call unshare_expr because force_gimple_operand may
3071      modify the tree we pass to it.  */
3072   folded = force_gimple_operand (unshare_expr (folded), &forced_stmts,
3073                                  false, NULL);
3074
3075   /* If we have any intermediate expressions to the value sets, add them
3076      to the value sets and chain them in the instruction stream.  */
3077   if (forced_stmts)
3078     {
3079       gsi = gsi_start (forced_stmts);
3080       for (; !gsi_end_p (gsi); gsi_next (&gsi))
3081         {
3082           gimple stmt = gsi_stmt (gsi);
3083           tree forcedname = gimple_get_lhs (stmt);
3084           pre_expr nameexpr;
3085
3086           VEC_safe_push (gimple, heap, inserted_exprs, stmt);
3087           if (TREE_CODE (forcedname) == SSA_NAME)
3088             {
3089               VN_INFO_GET (forcedname)->valnum = forcedname;
3090               VN_INFO (forcedname)->value_id = get_next_value_id ();
3091               nameexpr = get_or_alloc_expr_for_name (forcedname);
3092               add_to_value (VN_INFO (forcedname)->value_id, nameexpr);
3093               if (!in_fre)
3094                 bitmap_value_replace_in_set (NEW_SETS (block), nameexpr);
3095               bitmap_value_replace_in_set (AVAIL_OUT (block), nameexpr);
3096             }
3097           mark_symbols_for_renaming (stmt);
3098         }
3099       gimple_seq_add_seq (stmts, forced_stmts);
3100     }
3101
3102   /* Build and insert the assignment of the end result to the temporary
3103      that we will return.  */
3104   if (!pretemp || exprtype != TREE_TYPE (pretemp))
3105     {
3106       pretemp = create_tmp_reg (exprtype, "pretmp");
3107       get_var_ann (pretemp);
3108     }
3109
3110   temp = pretemp;
3111   add_referenced_var (temp);
3112
3113   newstmt = gimple_build_assign (temp, folded);
3114   name = make_ssa_name (temp, newstmt);
3115   gimple_assign_set_lhs (newstmt, name);
3116   gimple_set_plf (newstmt, NECESSARY, false);
3117
3118   gimple_seq_add_stmt (stmts, newstmt);
3119   VEC_safe_push (gimple, heap, inserted_exprs, newstmt);
3120
3121   /* All the symbols in NEWEXPR should be put into SSA form.  */
3122   mark_symbols_for_renaming (newstmt);
3123
3124   /* Add a value number to the temporary.
3125      The value may already exist in either NEW_SETS, or AVAIL_OUT, because
3126      we are creating the expression by pieces, and this particular piece of
3127      the expression may have been represented.  There is no harm in replacing
3128      here.  */
3129   VN_INFO_GET (name)->valnum = name;
3130   value_id = get_expr_value_id (expr);
3131   VN_INFO (name)->value_id = value_id;
3132   nameexpr = get_or_alloc_expr_for_name (name);
3133   add_to_value (value_id, nameexpr);
3134   if (!in_fre)
3135     bitmap_value_replace_in_set (NEW_SETS (block), nameexpr);
3136   bitmap_value_replace_in_set (AVAIL_OUT (block), nameexpr);
3137
3138   pre_stats.insertions++;
3139   if (dump_file && (dump_flags & TDF_DETAILS))
3140     {
3141       fprintf (dump_file, "Inserted ");
3142       print_gimple_stmt (dump_file, newstmt, 0, 0);
3143       fprintf (dump_file, " in predecessor %d\n", block->index);
3144     }
3145
3146   return name;
3147 }
3148
3149
3150 /* Returns true if we want to inhibit the insertions of PHI nodes
3151    for the given EXPR for basic block BB (a member of a loop).
3152    We want to do this, when we fear that the induction variable we
3153    create might inhibit vectorization.  */
3154
3155 static bool
3156 inhibit_phi_insertion (basic_block bb, pre_expr expr)
3157 {
3158   vn_reference_t vr = PRE_EXPR_REFERENCE (expr);
3159   VEC (vn_reference_op_s, heap) *ops = vr->operands;
3160   vn_reference_op_t op;
3161   unsigned i;
3162
3163   /* If we aren't going to vectorize we don't inhibit anything.  */
3164   if (!flag_tree_vectorize)
3165     return false;
3166
3167   /* Otherwise we inhibit the insertion when the address of the
3168      memory reference is a simple induction variable.  In other
3169      cases the vectorizer won't do anything anyway (either it's
3170      loop invariant or a complicated expression).  */
3171   for (i = 0; VEC_iterate (vn_reference_op_s, ops, i, op); ++i)
3172     {
3173       switch (op->opcode)
3174         {
3175         case ARRAY_REF:
3176         case ARRAY_RANGE_REF:
3177           if (TREE_CODE (op->op0) != SSA_NAME)
3178             break;
3179           /* Fallthru.  */
3180         case SSA_NAME:
3181           {
3182             basic_block defbb = gimple_bb (SSA_NAME_DEF_STMT (op->op0));
3183             affine_iv iv;
3184             /* Default defs are loop invariant.  */
3185             if (!defbb)
3186               break;
3187             /* Defined outside this loop, also loop invariant.  */
3188             if (!flow_bb_inside_loop_p (bb->loop_father, defbb))
3189               break;
3190             /* If it's a simple induction variable inhibit insertion,
3191                the vectorizer might be interested in this one.  */
3192             if (simple_iv (bb->loop_father, bb->loop_father,
3193                            op->op0, &iv, true))
3194               return true;
3195             /* No simple IV, vectorizer can't do anything, hence no
3196                reason to inhibit the transformation for this operand.  */
3197             break;
3198           }
3199         default:
3200           break;
3201         }
3202     }
3203   return false;
3204 }
3205
3206 /* Insert the to-be-made-available values of expression EXPRNUM for each
3207    predecessor, stored in AVAIL, into the predecessors of BLOCK, and
3208    merge the result with a phi node, given the same value number as
3209    NODE.  Return true if we have inserted new stuff.  */
3210
3211 static bool
3212 insert_into_preds_of_block (basic_block block, unsigned int exprnum,
3213                             pre_expr *avail)
3214 {
3215   pre_expr expr = expression_for_id (exprnum);
3216   pre_expr newphi;
3217   unsigned int val = get_expr_value_id (expr);
3218   edge pred;
3219   bool insertions = false;
3220   bool nophi = false;
3221   basic_block bprime;
3222   pre_expr eprime;
3223   edge_iterator ei;
3224   tree type = get_expr_type (expr);
3225   tree temp;
3226   gimple phi;
3227
3228   if (dump_file && (dump_flags & TDF_DETAILS))
3229     {
3230       fprintf (dump_file, "Found partial redundancy for expression ");
3231       print_pre_expr (dump_file, expr);
3232       fprintf (dump_file, " (%04d)\n", val);
3233     }
3234
3235   /* Make sure we aren't creating an induction variable.  */
3236   if (block->loop_depth > 0 && EDGE_COUNT (block->preds) == 2)
3237     {
3238       bool firstinsideloop = false;
3239       bool secondinsideloop = false;
3240       firstinsideloop = flow_bb_inside_loop_p (block->loop_father,
3241                                                EDGE_PRED (block, 0)->src);
3242       secondinsideloop = flow_bb_inside_loop_p (block->loop_father,
3243                                                 EDGE_PRED (block, 1)->src);
3244       /* Induction variables only have one edge inside the loop.  */
3245       if ((firstinsideloop ^ secondinsideloop)
3246           && (expr->kind != REFERENCE
3247               || inhibit_phi_insertion (block, expr)))
3248         {
3249           if (dump_file && (dump_flags & TDF_DETAILS))
3250             fprintf (dump_file, "Skipping insertion of phi for partial redundancy: Looks like an induction variable\n");
3251           nophi = true;
3252         }
3253     }
3254
3255   /* Make the necessary insertions.  */
3256   FOR_EACH_EDGE (pred, ei, block->preds)
3257     {
3258       gimple_seq stmts = NULL;
3259       tree builtexpr;
3260       bprime = pred->src;
3261       eprime = avail[bprime->index];
3262
3263       if (eprime->kind != NAME && eprime->kind != CONSTANT)
3264         {
3265           builtexpr = create_expression_by_pieces (bprime,
3266                                                    eprime,
3267                                                    &stmts, NULL,
3268                                                    type);
3269           gcc_assert (!(pred->flags & EDGE_ABNORMAL));
3270           gsi_insert_seq_on_edge (pred, stmts);
3271           avail[bprime->index] = get_or_alloc_expr_for_name (builtexpr);
3272           insertions = true;
3273         }
3274       else if (eprime->kind == CONSTANT)
3275         {
3276           /* Constants may not have the right type, fold_convert
3277              should give us back a constant with the right type.
3278           */
3279           tree constant = PRE_EXPR_CONSTANT (eprime);
3280           if (!useless_type_conversion_p (type, TREE_TYPE (constant)))
3281             {
3282               tree builtexpr = fold_convert (type, constant);
3283               if (!is_gimple_min_invariant (builtexpr))
3284                 {
3285                   tree forcedexpr = force_gimple_operand (builtexpr,
3286                                                           &stmts, true,
3287                                                           NULL);
3288                   if (!is_gimple_min_invariant (forcedexpr))
3289                     {
3290                       if (forcedexpr != builtexpr)
3291                         {
3292                           VN_INFO_GET (forcedexpr)->valnum = PRE_EXPR_CONSTANT (eprime);
3293                           VN_INFO (forcedexpr)->value_id = get_expr_value_id (eprime);
3294                         }
3295                       if (stmts)
3296                         {
3297                           gimple_stmt_iterator gsi;
3298                           gsi = gsi_start (stmts);
3299                           for (; !gsi_end_p (gsi); gsi_next (&gsi))
3300                             {
3301                               gimple stmt = gsi_stmt (gsi);
3302                               VEC_safe_push (gimple, heap, inserted_exprs, stmt);
3303                               gimple_set_plf (stmt, NECESSARY, false);
3304                             }
3305                           gsi_insert_seq_on_edge (pred, stmts);
3306                         }
3307                       avail[bprime->index] = get_or_alloc_expr_for_name (forcedexpr);
3308                     }
3309                 }
3310             }
3311         }
3312       else if (eprime->kind == NAME)
3313         {
3314           /* We may have to do a conversion because our value
3315              numbering can look through types in certain cases, but
3316              our IL requires all operands of a phi node have the same
3317              type.  */
3318           tree name = PRE_EXPR_NAME (eprime);
3319           if (!useless_type_conversion_p (type, TREE_TYPE (name)))
3320             {
3321               tree builtexpr;
3322               tree forcedexpr;
3323               builtexpr = fold_convert (type, name);
3324               forcedexpr = force_gimple_operand (builtexpr,
3325                                                  &stmts, true,
3326                                                  NULL);
3327
3328               if (forcedexpr != name)
3329                 {
3330                   VN_INFO_GET (forcedexpr)->valnum = VN_INFO (name)->valnum;
3331                   VN_INFO (forcedexpr)->value_id = VN_INFO (name)->value_id;
3332                 }
3333
3334               if (stmts)
3335                 {
3336                   gimple_stmt_iterator gsi;
3337                   gsi = gsi_start (stmts);
3338                   for (; !gsi_end_p (gsi); gsi_next (&gsi))
3339                     {
3340                       gimple stmt = gsi_stmt (gsi);
3341                       VEC_safe_push (gimple, heap, inserted_exprs, stmt);
3342                       gimple_set_plf (stmt, NECESSARY, false);
3343                     }
3344                   gsi_insert_seq_on_edge (pred, stmts);
3345                 }
3346               avail[bprime->index] = get_or_alloc_expr_for_name (forcedexpr);
3347             }
3348         }
3349     }
3350   /* If we didn't want a phi node, and we made insertions, we still have
3351      inserted new stuff, and thus return true.  If we didn't want a phi node,
3352      and didn't make insertions, we haven't added anything new, so return
3353      false.  */
3354   if (nophi && insertions)
3355     return true;
3356   else if (nophi && !insertions)
3357     return false;
3358
3359   /* Now build a phi for the new variable.  */
3360   if (!prephitemp || TREE_TYPE (prephitemp) != type)
3361     {
3362       prephitemp = create_tmp_var (type, "prephitmp");
3363       get_var_ann (prephitemp);
3364     }
3365
3366   temp = prephitemp;
3367   add_referenced_var (temp);
3368
3369   if (TREE_CODE (type) == COMPLEX_TYPE
3370       || TREE_CODE (type) == VECTOR_TYPE)
3371     DECL_GIMPLE_REG_P (temp) = 1;
3372   phi = create_phi_node (temp, block);
3373
3374   gimple_set_plf (phi, NECESSARY, false);
3375   VN_INFO_GET (gimple_phi_result (phi))->valnum = gimple_phi_result (phi);
3376   VN_INFO (gimple_phi_result (phi))->value_id = val;
3377   VEC_safe_push (gimple, heap, inserted_exprs, phi);
3378   bitmap_set_bit (inserted_phi_names,
3379                   SSA_NAME_VERSION (gimple_phi_result (phi)));
3380   FOR_EACH_EDGE (pred, ei, block->preds)
3381     {
3382       pre_expr ae = avail[pred->src->index];
3383       gcc_assert (get_expr_type (ae) == type
3384                   || useless_type_conversion_p (type, get_expr_type (ae)));
3385       if (ae->kind == CONSTANT)
3386         add_phi_arg (phi, PRE_EXPR_CONSTANT (ae), pred, UNKNOWN_LOCATION);
3387       else
3388         add_phi_arg (phi, PRE_EXPR_NAME (avail[pred->src->index]), pred,
3389                      UNKNOWN_LOCATION);
3390     }
3391
3392   newphi = get_or_alloc_expr_for_name (gimple_phi_result (phi));
3393   add_to_value (val, newphi);
3394
3395   /* The value should *not* exist in PHI_GEN, or else we wouldn't be doing
3396      this insertion, since we test for the existence of this value in PHI_GEN
3397      before proceeding with the partial redundancy checks in insert_aux.
3398
3399      The value may exist in AVAIL_OUT, in particular, it could be represented
3400      by the expression we are trying to eliminate, in which case we want the
3401      replacement to occur.  If it's not existing in AVAIL_OUT, we want it
3402      inserted there.
3403
3404      Similarly, to the PHI_GEN case, the value should not exist in NEW_SETS of
3405      this block, because if it did, it would have existed in our dominator's
3406      AVAIL_OUT, and would have been skipped due to the full redundancy check.
3407   */
3408
3409   bitmap_insert_into_set (PHI_GEN (block), newphi);
3410   bitmap_value_replace_in_set (AVAIL_OUT (block),
3411                                newphi);
3412   bitmap_insert_into_set (NEW_SETS (block),
3413                           newphi);
3414
3415   if (dump_file && (dump_flags & TDF_DETAILS))
3416     {
3417       fprintf (dump_file, "Created phi ");
3418       print_gimple_stmt (dump_file, phi, 0, 0);
3419       fprintf (dump_file, " in block %d\n", block->index);
3420     }
3421   pre_stats.phis++;
3422   return true;
3423 }
3424
3425
3426
3427 /* Perform insertion of partially redundant values.
3428    For BLOCK, do the following:
3429    1.  Propagate the NEW_SETS of the dominator into the current block.
3430    If the block has multiple predecessors,
3431        2a. Iterate over the ANTIC expressions for the block to see if
3432            any of them are partially redundant.
3433        2b. If so, insert them into the necessary predecessors to make
3434            the expression fully redundant.
3435        2c.