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