Merge branch 'vendor/GCC47'
[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         tree name = PRE_EXPR_NAME (expr);
1760         gimple def_stmt = SSA_NAME_DEF_STMT (name);
1761         /* If the SSA name is defined by a PHI node in this block,
1762            translate it.  */
1763         if (gimple_code (def_stmt) == GIMPLE_PHI
1764             && gimple_bb (def_stmt) == phiblock)
1765           {
1766             edge e = find_edge (pred, gimple_bb (def_stmt));
1767             tree def = PHI_ARG_DEF (def_stmt, e->dest_idx);
1768
1769             /* Handle constant. */
1770             if (is_gimple_min_invariant (def))
1771               return get_or_alloc_expr_for_constant (def);
1772
1773             return get_or_alloc_expr_for_name (def);
1774           }
1775         /* Otherwise return it unchanged - it will get cleaned if its
1776            value is not available in PREDs AVAIL_OUT set of expressions.  */
1777         return expr;
1778       }
1779
1780     default:
1781       gcc_unreachable ();
1782     }
1783 }
1784
1785 /* Wrapper around phi_translate_1 providing caching functionality.  */
1786
1787 static pre_expr
1788 phi_translate (pre_expr expr, bitmap_set_t set1, bitmap_set_t set2,
1789                basic_block pred, basic_block phiblock)
1790 {
1791   pre_expr phitrans;
1792
1793   if (!expr)
1794     return NULL;
1795
1796   /* Constants contain no values that need translation.  */
1797   if (expr->kind == CONSTANT)
1798     return expr;
1799
1800   if (value_id_constant_p (get_expr_value_id (expr)))
1801     return expr;
1802
1803   if (expr->kind != NAME)
1804     {
1805       phitrans = phi_trans_lookup (expr, pred);
1806       if (phitrans)
1807         return phitrans;
1808     }
1809
1810   /* Translate.  */
1811   phitrans = phi_translate_1 (expr, set1, set2, pred, phiblock);
1812
1813   /* Don't add empty translations to the cache.  Neither add
1814      translations of NAMEs as those are cheap to translate.  */
1815   if (phitrans
1816       && expr->kind != NAME)
1817     phi_trans_add (expr, phitrans, pred);
1818
1819   return phitrans;
1820 }
1821
1822
1823 /* For each expression in SET, translate the values through phi nodes
1824    in PHIBLOCK using edge PHIBLOCK->PRED, and store the resulting
1825    expressions in DEST.  */
1826
1827 static void
1828 phi_translate_set (bitmap_set_t dest, bitmap_set_t set, basic_block pred,
1829                    basic_block phiblock)
1830 {
1831   VEC (pre_expr, heap) *exprs;
1832   pre_expr expr;
1833   int i;
1834
1835   if (gimple_seq_empty_p (phi_nodes (phiblock)))
1836     {
1837       bitmap_set_copy (dest, set);
1838       return;
1839     }
1840
1841   exprs = sorted_array_from_bitmap_set (set);
1842   FOR_EACH_VEC_ELT (pre_expr, exprs, i, expr)
1843     {
1844       pre_expr translated;
1845       translated = phi_translate (expr, set, NULL, pred, phiblock);
1846       if (!translated)
1847         continue;
1848
1849       /* We might end up with multiple expressions from SET being
1850          translated to the same value.  In this case we do not want
1851          to retain the NARY or REFERENCE expression but prefer a NAME
1852          which would be the leader.  */
1853       if (translated->kind == NAME)
1854         bitmap_value_replace_in_set (dest, translated);
1855       else
1856         bitmap_value_insert_into_set (dest, translated);
1857     }
1858   VEC_free (pre_expr, heap, exprs);
1859 }
1860
1861 /* Find the leader for a value (i.e., the name representing that
1862    value) in a given set, and return it.  If STMT is non-NULL it
1863    makes sure the defining statement for the leader dominates it.
1864    Return NULL if no leader is found.  */
1865
1866 static pre_expr
1867 bitmap_find_leader (bitmap_set_t set, unsigned int val, gimple stmt)
1868 {
1869   if (value_id_constant_p (val))
1870     {
1871       unsigned int i;
1872       bitmap_iterator bi;
1873       bitmap_set_t exprset = VEC_index (bitmap_set_t, value_expressions, val);
1874
1875       FOR_EACH_EXPR_ID_IN_SET (exprset, i, bi)
1876         {
1877           pre_expr expr = expression_for_id (i);
1878           if (expr->kind == CONSTANT)
1879             return expr;
1880         }
1881     }
1882   if (bitmap_set_contains_value (set, val))
1883     {
1884       /* Rather than walk the entire bitmap of expressions, and see
1885          whether any of them has the value we are looking for, we look
1886          at the reverse mapping, which tells us the set of expressions
1887          that have a given value (IE value->expressions with that
1888          value) and see if any of those expressions are in our set.
1889          The number of expressions per value is usually significantly
1890          less than the number of expressions in the set.  In fact, for
1891          large testcases, doing it this way is roughly 5-10x faster
1892          than walking the bitmap.
1893          If this is somehow a significant lose for some cases, we can
1894          choose which set to walk based on which set is smaller.  */
1895       unsigned int i;
1896       bitmap_iterator bi;
1897       bitmap_set_t exprset = VEC_index (bitmap_set_t, value_expressions, val);
1898
1899       EXECUTE_IF_AND_IN_BITMAP (&exprset->expressions,
1900                                 &set->expressions, 0, i, bi)
1901         {
1902           pre_expr val = expression_for_id (i);
1903           /* At the point where stmt is not null, there should always
1904              be an SSA_NAME first in the list of expressions.  */
1905           if (stmt)
1906             {
1907               gimple def_stmt = SSA_NAME_DEF_STMT (PRE_EXPR_NAME (val));
1908               if (gimple_code (def_stmt) != GIMPLE_PHI
1909                   && gimple_bb (def_stmt) == gimple_bb (stmt)
1910                   /* PRE insertions are at the end of the basic-block
1911                      and have UID 0.  */
1912                   && (gimple_uid (def_stmt) == 0
1913                       || gimple_uid (def_stmt) >= gimple_uid (stmt)))
1914                 continue;
1915             }
1916           return val;
1917         }
1918     }
1919   return NULL;
1920 }
1921
1922 /* Determine if EXPR, a memory expression, is ANTIC_IN at the top of
1923    BLOCK by seeing if it is not killed in the block.  Note that we are
1924    only determining whether there is a store that kills it.  Because
1925    of the order in which clean iterates over values, we are guaranteed
1926    that altered operands will have caused us to be eliminated from the
1927    ANTIC_IN set already.  */
1928
1929 static bool
1930 value_dies_in_block_x (pre_expr expr, basic_block block)
1931 {
1932   tree vuse = PRE_EXPR_REFERENCE (expr)->vuse;
1933   vn_reference_t refx = PRE_EXPR_REFERENCE (expr);
1934   gimple def;
1935   gimple_stmt_iterator gsi;
1936   unsigned id = get_expression_id (expr);
1937   bool res = false;
1938   ao_ref ref;
1939
1940   if (!vuse)
1941     return false;
1942
1943   /* Lookup a previously calculated result.  */
1944   if (EXPR_DIES (block)
1945       && bitmap_bit_p (EXPR_DIES (block), id * 2))
1946     return bitmap_bit_p (EXPR_DIES (block), id * 2 + 1);
1947
1948   /* A memory expression {e, VUSE} dies in the block if there is a
1949      statement that may clobber e.  If, starting statement walk from the
1950      top of the basic block, a statement uses VUSE there can be no kill
1951      inbetween that use and the original statement that loaded {e, VUSE},
1952      so we can stop walking.  */
1953   ref.base = NULL_TREE;
1954   for (gsi = gsi_start_bb (block); !gsi_end_p (gsi); gsi_next (&gsi))
1955     {
1956       tree def_vuse, def_vdef;
1957       def = gsi_stmt (gsi);
1958       def_vuse = gimple_vuse (def);
1959       def_vdef = gimple_vdef (def);
1960
1961       /* Not a memory statement.  */
1962       if (!def_vuse)
1963         continue;
1964
1965       /* Not a may-def.  */
1966       if (!def_vdef)
1967         {
1968           /* A load with the same VUSE, we're done.  */
1969           if (def_vuse == vuse)
1970             break;
1971
1972           continue;
1973         }
1974
1975       /* Init ref only if we really need it.  */
1976       if (ref.base == NULL_TREE
1977           && !ao_ref_init_from_vn_reference (&ref, refx->set, refx->type,
1978                                              refx->operands))
1979         {
1980           res = true;
1981           break;
1982         }
1983       /* If the statement may clobber expr, it dies.  */
1984       if (stmt_may_clobber_ref_p_1 (def, &ref))
1985         {
1986           res = true;
1987           break;
1988         }
1989     }
1990
1991   /* Remember the result.  */
1992   if (!EXPR_DIES (block))
1993     EXPR_DIES (block) = BITMAP_ALLOC (&grand_bitmap_obstack);
1994   bitmap_set_bit (EXPR_DIES (block), id * 2);
1995   if (res)
1996     bitmap_set_bit (EXPR_DIES (block), id * 2 + 1);
1997
1998   return res;
1999 }
2000
2001
2002 #define union_contains_value(SET1, SET2, VAL)                   \
2003   (bitmap_set_contains_value ((SET1), (VAL))                    \
2004    || ((SET2) && bitmap_set_contains_value ((SET2), (VAL))))
2005
2006 /* Determine if vn_reference_op_t VRO is legal in SET1 U SET2.
2007  */
2008 static bool
2009 vro_valid_in_sets (bitmap_set_t set1, bitmap_set_t set2,
2010                    vn_reference_op_t vro)
2011 {
2012   if (vro->op0 && TREE_CODE (vro->op0) == SSA_NAME)
2013     {
2014       struct pre_expr_d temp;
2015       temp.kind = NAME;
2016       temp.id = 0;
2017       PRE_EXPR_NAME (&temp) = vro->op0;
2018       temp.id = lookup_expression_id (&temp);
2019       if (temp.id == 0)
2020         return false;
2021       if (!union_contains_value (set1, set2,
2022                                  get_expr_value_id (&temp)))
2023         return false;
2024     }
2025   if (vro->op1 && TREE_CODE (vro->op1) == SSA_NAME)
2026     {
2027       struct pre_expr_d temp;
2028       temp.kind = NAME;
2029       temp.id = 0;
2030       PRE_EXPR_NAME (&temp) = vro->op1;
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
2039   if (vro->op2 && TREE_CODE (vro->op2) == SSA_NAME)
2040     {
2041       struct pre_expr_d temp;
2042       temp.kind = NAME;
2043       temp.id = 0;
2044       PRE_EXPR_NAME (&temp) = vro->op2;
2045       temp.id = lookup_expression_id (&temp);
2046       if (temp.id == 0)
2047         return false;
2048       if (!union_contains_value (set1, set2,
2049                                  get_expr_value_id (&temp)))
2050         return false;
2051     }
2052
2053   return true;
2054 }
2055
2056 /* Determine if the expression EXPR is valid in SET1 U SET2.
2057    ONLY SET2 CAN BE NULL.
2058    This means that we have a leader for each part of the expression
2059    (if it consists of values), or the expression is an SSA_NAME.
2060    For loads/calls, we also see if the vuse is killed in this block.  */
2061
2062 static bool
2063 valid_in_sets (bitmap_set_t set1, bitmap_set_t set2, pre_expr expr,
2064                basic_block block)
2065 {
2066   switch (expr->kind)
2067     {
2068     case NAME:
2069       return bitmap_set_contains_expr (AVAIL_OUT (block), expr);
2070     case NARY:
2071       {
2072         unsigned int i;
2073         vn_nary_op_t nary = PRE_EXPR_NARY (expr);
2074         for (i = 0; i < nary->length; i++)
2075           {
2076             if (TREE_CODE (nary->op[i]) == SSA_NAME)
2077               {
2078                 struct pre_expr_d temp;
2079                 temp.kind = NAME;
2080                 temp.id = 0;
2081                 PRE_EXPR_NAME (&temp) = nary->op[i];
2082                 temp.id = lookup_expression_id (&temp);
2083                 if (temp.id == 0)
2084                   return false;
2085                 if (!union_contains_value (set1, set2,
2086                                            get_expr_value_id (&temp)))
2087                   return false;
2088               }
2089           }
2090         /* If the NARY may trap make sure the block does not contain
2091            a possible exit point.
2092            ???  This is overly conservative if we translate AVAIL_OUT
2093            as the available expression might be after the exit point.  */
2094         if (BB_MAY_NOTRETURN (block)
2095             && vn_nary_may_trap (nary))
2096           return false;
2097         return true;
2098       }
2099       break;
2100     case REFERENCE:
2101       {
2102         vn_reference_t ref = PRE_EXPR_REFERENCE (expr);
2103         vn_reference_op_t vro;
2104         unsigned int i;
2105
2106         FOR_EACH_VEC_ELT (vn_reference_op_s, ref->operands, i, vro)
2107           {
2108             if (!vro_valid_in_sets (set1, set2, vro))
2109               return false;
2110           }
2111         if (ref->vuse)
2112           {
2113             gimple def_stmt = SSA_NAME_DEF_STMT (ref->vuse);
2114             if (!gimple_nop_p (def_stmt)
2115                 && gimple_bb (def_stmt) != block
2116                 && !dominated_by_p (CDI_DOMINATORS,
2117                                     block, gimple_bb (def_stmt)))
2118               return false;
2119           }
2120         return !value_dies_in_block_x (expr, block);
2121       }
2122     default:
2123       gcc_unreachable ();
2124     }
2125 }
2126
2127 /* Clean the set of expressions that are no longer valid in SET1 or
2128    SET2.  This means expressions that are made up of values we have no
2129    leaders for in SET1 or SET2.  This version is used for partial
2130    anticipation, which means it is not valid in either ANTIC_IN or
2131    PA_IN.  */
2132
2133 static void
2134 dependent_clean (bitmap_set_t set1, bitmap_set_t set2, basic_block block)
2135 {
2136   VEC (pre_expr, heap) *exprs = sorted_array_from_bitmap_set (set1);
2137   pre_expr expr;
2138   int i;
2139
2140   FOR_EACH_VEC_ELT (pre_expr, exprs, i, expr)
2141     {
2142       if (!valid_in_sets (set1, set2, expr, block))
2143         bitmap_remove_from_set (set1, expr);
2144     }
2145   VEC_free (pre_expr, heap, exprs);
2146 }
2147
2148 /* Clean the set of expressions that are no longer valid in SET.  This
2149    means expressions that are made up of values we have no leaders for
2150    in SET.  */
2151
2152 static void
2153 clean (bitmap_set_t set, basic_block block)
2154 {
2155   VEC (pre_expr, heap) *exprs = sorted_array_from_bitmap_set (set);
2156   pre_expr expr;
2157   int i;
2158
2159   FOR_EACH_VEC_ELT (pre_expr, exprs, i, expr)
2160     {
2161       if (!valid_in_sets (set, NULL, expr, block))
2162         bitmap_remove_from_set (set, expr);
2163     }
2164   VEC_free (pre_expr, heap, exprs);
2165 }
2166
2167 static sbitmap has_abnormal_preds;
2168
2169 /* List of blocks that may have changed during ANTIC computation and
2170    thus need to be iterated over.  */
2171
2172 static sbitmap changed_blocks;
2173
2174 /* Decide whether to defer a block for a later iteration, or PHI
2175    translate SOURCE to DEST using phis in PHIBLOCK.  Return false if we
2176    should defer the block, and true if we processed it.  */
2177
2178 static bool
2179 defer_or_phi_translate_block (bitmap_set_t dest, bitmap_set_t source,
2180                               basic_block block, basic_block phiblock)
2181 {
2182   if (!BB_VISITED (phiblock))
2183     {
2184       SET_BIT (changed_blocks, block->index);
2185       BB_VISITED (block) = 0;
2186       BB_DEFERRED (block) = 1;
2187       return false;
2188     }
2189   else
2190     phi_translate_set (dest, source, block, phiblock);
2191   return true;
2192 }
2193
2194 /* Compute the ANTIC set for BLOCK.
2195
2196    If succs(BLOCK) > 1 then
2197      ANTIC_OUT[BLOCK] = intersection of ANTIC_IN[b] for all succ(BLOCK)
2198    else if succs(BLOCK) == 1 then
2199      ANTIC_OUT[BLOCK] = phi_translate (ANTIC_IN[succ(BLOCK)])
2200
2201    ANTIC_IN[BLOCK] = clean(ANTIC_OUT[BLOCK] U EXP_GEN[BLOCK] - TMP_GEN[BLOCK])
2202 */
2203
2204 static bool
2205 compute_antic_aux (basic_block block, bool block_has_abnormal_pred_edge)
2206 {
2207   bool changed = false;
2208   bitmap_set_t S, old, ANTIC_OUT;
2209   bitmap_iterator bi;
2210   unsigned int bii;
2211   edge e;
2212   edge_iterator ei;
2213
2214   old = ANTIC_OUT = S = NULL;
2215   BB_VISITED (block) = 1;
2216
2217   /* If any edges from predecessors are abnormal, antic_in is empty,
2218      so do nothing.  */
2219   if (block_has_abnormal_pred_edge)
2220     goto maybe_dump_sets;
2221
2222   old = ANTIC_IN (block);
2223   ANTIC_OUT = bitmap_set_new ();
2224
2225   /* If the block has no successors, ANTIC_OUT is empty.  */
2226   if (EDGE_COUNT (block->succs) == 0)
2227     ;
2228   /* If we have one successor, we could have some phi nodes to
2229      translate through.  */
2230   else if (single_succ_p (block))
2231     {
2232       basic_block succ_bb = single_succ (block);
2233
2234       /* We trade iterations of the dataflow equations for having to
2235          phi translate the maximal set, which is incredibly slow
2236          (since the maximal set often has 300+ members, even when you
2237          have a small number of blocks).
2238          Basically, we defer the computation of ANTIC for this block
2239          until we have processed it's successor, which will inevitably
2240          have a *much* smaller set of values to phi translate once
2241          clean has been run on it.
2242          The cost of doing this is that we technically perform more
2243          iterations, however, they are lower cost iterations.
2244
2245          Timings for PRE on tramp3d-v4:
2246          without maximal set fix: 11 seconds
2247          with maximal set fix/without deferring: 26 seconds
2248          with maximal set fix/with deferring: 11 seconds
2249      */
2250
2251       if (!defer_or_phi_translate_block (ANTIC_OUT, ANTIC_IN (succ_bb),
2252                                         block, succ_bb))
2253         {
2254           changed = true;
2255           goto maybe_dump_sets;
2256         }
2257     }
2258   /* If we have multiple successors, we take the intersection of all of
2259      them.  Note that in the case of loop exit phi nodes, we may have
2260      phis to translate through.  */
2261   else
2262     {
2263       VEC(basic_block, heap) * worklist;
2264       size_t i;
2265       basic_block bprime, first = NULL;
2266
2267       worklist = VEC_alloc (basic_block, heap, EDGE_COUNT (block->succs));
2268       FOR_EACH_EDGE (e, ei, block->succs)
2269         {
2270           if (!first
2271               && BB_VISITED (e->dest))
2272             first = e->dest;
2273           else if (BB_VISITED (e->dest))
2274             VEC_quick_push (basic_block, worklist, e->dest);
2275         }
2276
2277       /* Of multiple successors we have to have visited one already.  */
2278       if (!first)
2279         {
2280           SET_BIT (changed_blocks, block->index);
2281           BB_VISITED (block) = 0;
2282           BB_DEFERRED (block) = 1;
2283           changed = true;
2284           VEC_free (basic_block, heap, worklist);
2285           goto maybe_dump_sets;
2286         }
2287
2288       if (!gimple_seq_empty_p (phi_nodes (first)))
2289         phi_translate_set (ANTIC_OUT, ANTIC_IN (first), block, first);
2290       else
2291         bitmap_set_copy (ANTIC_OUT, ANTIC_IN (first));
2292
2293       FOR_EACH_VEC_ELT (basic_block, worklist, i, bprime)
2294         {
2295           if (!gimple_seq_empty_p (phi_nodes (bprime)))
2296             {
2297               bitmap_set_t tmp = bitmap_set_new ();
2298               phi_translate_set (tmp, ANTIC_IN (bprime), block, bprime);
2299               bitmap_set_and (ANTIC_OUT, tmp);
2300               bitmap_set_free (tmp);
2301             }
2302           else
2303             bitmap_set_and (ANTIC_OUT, ANTIC_IN (bprime));
2304         }
2305       VEC_free (basic_block, heap, worklist);
2306     }
2307
2308   /* Generate ANTIC_OUT - TMP_GEN.  */
2309   S = bitmap_set_subtract (ANTIC_OUT, TMP_GEN (block));
2310
2311   /* Start ANTIC_IN with EXP_GEN - TMP_GEN.  */
2312   ANTIC_IN (block) = bitmap_set_subtract (EXP_GEN (block),
2313                                           TMP_GEN (block));
2314
2315   /* Then union in the ANTIC_OUT - TMP_GEN values,
2316      to get ANTIC_OUT U EXP_GEN - TMP_GEN */
2317   FOR_EACH_EXPR_ID_IN_SET (S, bii, bi)
2318     bitmap_value_insert_into_set (ANTIC_IN (block),
2319                                   expression_for_id (bii));
2320
2321   clean (ANTIC_IN (block), block);
2322
2323   if (!bitmap_set_equal (old, ANTIC_IN (block)))
2324     {
2325       changed = true;
2326       SET_BIT (changed_blocks, block->index);
2327       FOR_EACH_EDGE (e, ei, block->preds)
2328         SET_BIT (changed_blocks, e->src->index);
2329     }
2330   else
2331     RESET_BIT (changed_blocks, block->index);
2332
2333  maybe_dump_sets:
2334   if (dump_file && (dump_flags & TDF_DETAILS))
2335     {
2336       if (!BB_DEFERRED (block) || BB_VISITED (block))
2337         {
2338           if (ANTIC_OUT)
2339             print_bitmap_set (dump_file, ANTIC_OUT, "ANTIC_OUT", block->index);
2340
2341           print_bitmap_set (dump_file, ANTIC_IN (block), "ANTIC_IN",
2342                             block->index);
2343
2344           if (S)
2345             print_bitmap_set (dump_file, S, "S", block->index);
2346         }
2347       else
2348         {
2349           fprintf (dump_file,
2350                    "Block %d was deferred for a future iteration.\n",
2351                    block->index);
2352         }
2353     }
2354   if (old)
2355     bitmap_set_free (old);
2356   if (S)
2357     bitmap_set_free (S);
2358   if (ANTIC_OUT)
2359     bitmap_set_free (ANTIC_OUT);
2360   return changed;
2361 }
2362
2363 /* Compute PARTIAL_ANTIC for BLOCK.
2364
2365    If succs(BLOCK) > 1 then
2366      PA_OUT[BLOCK] = value wise union of PA_IN[b] + all ANTIC_IN not
2367      in ANTIC_OUT for all succ(BLOCK)
2368    else if succs(BLOCK) == 1 then
2369      PA_OUT[BLOCK] = phi_translate (PA_IN[succ(BLOCK)])
2370
2371    PA_IN[BLOCK] = dependent_clean(PA_OUT[BLOCK] - TMP_GEN[BLOCK]
2372                                   - ANTIC_IN[BLOCK])
2373
2374 */
2375 static bool
2376 compute_partial_antic_aux (basic_block block,
2377                            bool block_has_abnormal_pred_edge)
2378 {
2379   bool changed = false;
2380   bitmap_set_t old_PA_IN;
2381   bitmap_set_t PA_OUT;
2382   edge e;
2383   edge_iterator ei;
2384   unsigned long max_pa = PARAM_VALUE (PARAM_MAX_PARTIAL_ANTIC_LENGTH);
2385
2386   old_PA_IN = PA_OUT = NULL;
2387
2388   /* If any edges from predecessors are abnormal, antic_in is empty,
2389      so do nothing.  */
2390   if (block_has_abnormal_pred_edge)
2391     goto maybe_dump_sets;
2392
2393   /* If there are too many partially anticipatable values in the
2394      block, phi_translate_set can take an exponential time: stop
2395      before the translation starts.  */
2396   if (max_pa
2397       && single_succ_p (block)
2398       && bitmap_count_bits (&PA_IN (single_succ (block))->values) > max_pa)
2399     goto maybe_dump_sets;
2400
2401   old_PA_IN = PA_IN (block);
2402   PA_OUT = bitmap_set_new ();
2403
2404   /* If the block has no successors, ANTIC_OUT is empty.  */
2405   if (EDGE_COUNT (block->succs) == 0)
2406     ;
2407   /* If we have one successor, we could have some phi nodes to
2408      translate through.  Note that we can't phi translate across DFS
2409      back edges in partial antic, because it uses a union operation on
2410      the successors.  For recurrences like IV's, we will end up
2411      generating a new value in the set on each go around (i + 3 (VH.1)
2412      VH.1 + 1 (VH.2), VH.2 + 1 (VH.3), etc), forever.  */
2413   else if (single_succ_p (block))
2414     {
2415       basic_block succ = single_succ (block);
2416       if (!(single_succ_edge (block)->flags & EDGE_DFS_BACK))
2417         phi_translate_set (PA_OUT, PA_IN (succ), block, succ);
2418     }
2419   /* If we have multiple successors, we take the union of all of
2420      them.  */
2421   else
2422     {
2423       VEC(basic_block, heap) * worklist;
2424       size_t i;
2425       basic_block bprime;
2426
2427       worklist = VEC_alloc (basic_block, heap, EDGE_COUNT (block->succs));
2428       FOR_EACH_EDGE (e, ei, block->succs)
2429         {
2430           if (e->flags & EDGE_DFS_BACK)
2431             continue;
2432           VEC_quick_push (basic_block, worklist, e->dest);
2433         }
2434       if (VEC_length (basic_block, worklist) > 0)
2435         {
2436           FOR_EACH_VEC_ELT (basic_block, worklist, i, bprime)
2437             {
2438               unsigned int i;
2439               bitmap_iterator bi;
2440
2441               FOR_EACH_EXPR_ID_IN_SET (ANTIC_IN (bprime), i, bi)
2442                 bitmap_value_insert_into_set (PA_OUT,
2443                                               expression_for_id (i));
2444               if (!gimple_seq_empty_p (phi_nodes (bprime)))
2445                 {
2446                   bitmap_set_t pa_in = bitmap_set_new ();
2447                   phi_translate_set (pa_in, PA_IN (bprime), block, bprime);
2448                   FOR_EACH_EXPR_ID_IN_SET (pa_in, i, bi)
2449                     bitmap_value_insert_into_set (PA_OUT,
2450                                                   expression_for_id (i));
2451                   bitmap_set_free (pa_in);
2452                 }
2453               else
2454                 FOR_EACH_EXPR_ID_IN_SET (PA_IN (bprime), i, bi)
2455                   bitmap_value_insert_into_set (PA_OUT,
2456                                                 expression_for_id (i));
2457             }
2458         }
2459       VEC_free (basic_block, heap, worklist);
2460     }
2461
2462   /* PA_IN starts with PA_OUT - TMP_GEN.
2463      Then we subtract things from ANTIC_IN.  */
2464   PA_IN (block) = bitmap_set_subtract (PA_OUT, TMP_GEN (block));
2465
2466   /* For partial antic, we want to put back in the phi results, since
2467      we will properly avoid making them partially antic over backedges.  */
2468   bitmap_ior_into (&PA_IN (block)->values, &PHI_GEN (block)->values);
2469   bitmap_ior_into (&PA_IN (block)->expressions, &PHI_GEN (block)->expressions);
2470
2471   /* PA_IN[block] = PA_IN[block] - ANTIC_IN[block] */
2472   bitmap_set_subtract_values (PA_IN (block), ANTIC_IN (block));
2473
2474   dependent_clean (PA_IN (block), ANTIC_IN (block), block);
2475
2476   if (!bitmap_set_equal (old_PA_IN, PA_IN (block)))
2477     {
2478       changed = true;
2479       SET_BIT (changed_blocks, block->index);
2480       FOR_EACH_EDGE (e, ei, block->preds)
2481         SET_BIT (changed_blocks, e->src->index);
2482     }
2483   else
2484     RESET_BIT (changed_blocks, block->index);
2485
2486  maybe_dump_sets:
2487   if (dump_file && (dump_flags & TDF_DETAILS))
2488     {
2489       if (PA_OUT)
2490         print_bitmap_set (dump_file, PA_OUT, "PA_OUT", block->index);
2491
2492       print_bitmap_set (dump_file, PA_IN (block), "PA_IN", block->index);
2493     }
2494   if (old_PA_IN)
2495     bitmap_set_free (old_PA_IN);
2496   if (PA_OUT)
2497     bitmap_set_free (PA_OUT);
2498   return changed;
2499 }
2500
2501 /* Compute ANTIC and partial ANTIC sets.  */
2502
2503 static void
2504 compute_antic (void)
2505 {
2506   bool changed = true;
2507   int num_iterations = 0;
2508   basic_block block;
2509   int i;
2510
2511   /* If any predecessor edges are abnormal, we punt, so antic_in is empty.
2512      We pre-build the map of blocks with incoming abnormal edges here.  */
2513   has_abnormal_preds = sbitmap_alloc (last_basic_block);
2514   sbitmap_zero (has_abnormal_preds);
2515
2516   FOR_EACH_BB (block)
2517     {
2518       edge_iterator ei;
2519       edge e;
2520
2521       FOR_EACH_EDGE (e, ei, block->preds)
2522         {
2523           e->flags &= ~EDGE_DFS_BACK;
2524           if (e->flags & EDGE_ABNORMAL)
2525             {
2526               SET_BIT (has_abnormal_preds, block->index);
2527               break;
2528             }
2529         }
2530
2531       BB_VISITED (block) = 0;
2532       BB_DEFERRED (block) = 0;
2533
2534       /* While we are here, give empty ANTIC_IN sets to each block.  */
2535       ANTIC_IN (block) = bitmap_set_new ();
2536       PA_IN (block) = bitmap_set_new ();
2537     }
2538
2539   /* At the exit block we anticipate nothing.  */
2540   ANTIC_IN (EXIT_BLOCK_PTR) = bitmap_set_new ();
2541   BB_VISITED (EXIT_BLOCK_PTR) = 1;
2542   PA_IN (EXIT_BLOCK_PTR) = bitmap_set_new ();
2543
2544   changed_blocks = sbitmap_alloc (last_basic_block + 1);
2545   sbitmap_ones (changed_blocks);
2546   while (changed)
2547     {
2548       if (dump_file && (dump_flags & TDF_DETAILS))
2549         fprintf (dump_file, "Starting iteration %d\n", num_iterations);
2550       /* ???  We need to clear our PHI translation cache here as the
2551          ANTIC sets shrink and we restrict valid translations to
2552          those having operands with leaders in ANTIC.  Same below
2553          for PA ANTIC computation.  */
2554       num_iterations++;
2555       changed = false;
2556       for (i = n_basic_blocks - NUM_FIXED_BLOCKS - 1; i >= 0; i--)
2557         {
2558           if (TEST_BIT (changed_blocks, postorder[i]))
2559             {
2560               basic_block block = BASIC_BLOCK (postorder[i]);
2561               changed |= compute_antic_aux (block,
2562                                             TEST_BIT (has_abnormal_preds,
2563                                                       block->index));
2564             }
2565         }
2566       /* Theoretically possible, but *highly* unlikely.  */
2567       gcc_checking_assert (num_iterations < 500);
2568     }
2569
2570   statistics_histogram_event (cfun, "compute_antic iterations",
2571                               num_iterations);
2572
2573   if (do_partial_partial)
2574     {
2575       sbitmap_ones (changed_blocks);
2576       mark_dfs_back_edges ();
2577       num_iterations = 0;
2578       changed = true;
2579       while (changed)
2580         {
2581           if (dump_file && (dump_flags & TDF_DETAILS))
2582             fprintf (dump_file, "Starting iteration %d\n", num_iterations);
2583           num_iterations++;
2584           changed = false;
2585           for (i = n_basic_blocks - NUM_FIXED_BLOCKS - 1 ; i >= 0; i--)
2586             {
2587               if (TEST_BIT (changed_blocks, postorder[i]))
2588                 {
2589                   basic_block block = BASIC_BLOCK (postorder[i]);
2590                   changed
2591                     |= compute_partial_antic_aux (block,
2592                                                   TEST_BIT (has_abnormal_preds,
2593                                                             block->index));
2594                 }
2595             }
2596           /* Theoretically possible, but *highly* unlikely.  */
2597           gcc_checking_assert (num_iterations < 500);
2598         }
2599       statistics_histogram_event (cfun, "compute_partial_antic iterations",
2600                                   num_iterations);
2601     }
2602   sbitmap_free (has_abnormal_preds);
2603   sbitmap_free (changed_blocks);
2604 }
2605
2606 /* Return true if OP is a tree which we can perform PRE on.
2607    This may not match the operations we can value number, but in
2608    a perfect world would.  */
2609
2610 static bool
2611 can_PRE_operation (tree op)
2612 {
2613   return UNARY_CLASS_P (op)
2614     || BINARY_CLASS_P (op)
2615     || COMPARISON_CLASS_P (op)
2616     || TREE_CODE (op) == MEM_REF 
2617     || TREE_CODE (op) == COMPONENT_REF
2618     || TREE_CODE (op) == VIEW_CONVERT_EXPR
2619     || TREE_CODE (op) == CALL_EXPR
2620     || TREE_CODE (op) == ARRAY_REF;
2621 }
2622
2623
2624 /* Inserted expressions are placed onto this worklist, which is used
2625    for performing quick dead code elimination of insertions we made
2626    that didn't turn out to be necessary.   */
2627 static bitmap inserted_exprs;
2628
2629 /* Pool allocated fake store expressions are placed onto this
2630    worklist, which, after performing dead code elimination, is walked
2631    to see which expressions need to be put into GC'able memory  */
2632 static VEC(gimple, heap) *need_creation;
2633
2634 /* The actual worker for create_component_ref_by_pieces.  */
2635
2636 static tree
2637 create_component_ref_by_pieces_1 (basic_block block, vn_reference_t ref,
2638                                   unsigned int *operand, gimple_seq *stmts,
2639                                   gimple domstmt)
2640 {
2641   vn_reference_op_t currop = VEC_index (vn_reference_op_s, ref->operands,
2642                                         *operand);
2643   tree genop;
2644   ++*operand;
2645   switch (currop->opcode)
2646     {
2647     case CALL_EXPR:
2648       {
2649         tree folded, sc = NULL_TREE;
2650         unsigned int nargs = 0;
2651         tree fn, *args;
2652         if (TREE_CODE (currop->op0) == FUNCTION_DECL)
2653           fn = currop->op0;
2654         else
2655           {
2656             pre_expr op0 = get_or_alloc_expr_for (currop->op0);
2657             fn = find_or_generate_expression (block, op0, stmts, domstmt);
2658             if (!fn)
2659               return NULL_TREE;
2660           }
2661         if (currop->op1)
2662           {
2663             pre_expr scexpr = get_or_alloc_expr_for (currop->op1);
2664             sc = find_or_generate_expression (block, scexpr, stmts, domstmt);
2665             if (!sc)
2666               return NULL_TREE;
2667           }
2668         args = XNEWVEC (tree, VEC_length (vn_reference_op_s,
2669                                           ref->operands) - 1);
2670         while (*operand < VEC_length (vn_reference_op_s, ref->operands))
2671           {
2672             args[nargs] = create_component_ref_by_pieces_1 (block, ref,
2673                                                             operand, stmts,
2674                                                             domstmt);
2675             if (!args[nargs])
2676               {
2677                 free (args);
2678                 return NULL_TREE;
2679               }
2680             nargs++;
2681           }
2682         folded = build_call_array (currop->type,
2683                                    (TREE_CODE (fn) == FUNCTION_DECL
2684                                     ? build_fold_addr_expr (fn) : fn),
2685                                    nargs, args);
2686         free (args);
2687         if (sc)
2688           CALL_EXPR_STATIC_CHAIN (folded) = sc;
2689         return folded;
2690       }
2691       break;
2692     case MEM_REF:
2693       {
2694         tree baseop = create_component_ref_by_pieces_1 (block, ref, operand,
2695                                                         stmts, domstmt);
2696         tree offset = currop->op0;
2697         if (!baseop)
2698           return NULL_TREE;
2699         if (TREE_CODE (baseop) == ADDR_EXPR
2700             && handled_component_p (TREE_OPERAND (baseop, 0)))
2701           {
2702             HOST_WIDE_INT off;
2703             tree base;
2704             base = get_addr_base_and_unit_offset (TREE_OPERAND (baseop, 0),
2705                                                   &off);
2706             gcc_assert (base);
2707             offset = int_const_binop (PLUS_EXPR, offset,
2708                                       build_int_cst (TREE_TYPE (offset),
2709                                                      off));
2710             baseop = build_fold_addr_expr (base);
2711           }
2712         return fold_build2 (MEM_REF, currop->type, baseop, offset);
2713       }
2714       break;
2715     case TARGET_MEM_REF:
2716       {
2717         pre_expr op0expr, op1expr;
2718         tree genop0 = NULL_TREE, genop1 = NULL_TREE;
2719         vn_reference_op_t nextop = VEC_index (vn_reference_op_s, ref->operands,
2720                                               ++*operand);
2721         tree baseop = create_component_ref_by_pieces_1 (block, ref, operand,
2722                                                         stmts, domstmt);
2723         if (!baseop)
2724           return NULL_TREE;
2725         if (currop->op0)
2726           {
2727             op0expr = get_or_alloc_expr_for (currop->op0);
2728             genop0 = find_or_generate_expression (block, op0expr,
2729                                                   stmts, domstmt);
2730             if (!genop0)
2731               return NULL_TREE;
2732           }
2733         if (nextop->op0)
2734           {
2735             op1expr = get_or_alloc_expr_for (nextop->op0);
2736             genop1 = find_or_generate_expression (block, op1expr,
2737                                                   stmts, domstmt);
2738             if (!genop1)
2739               return NULL_TREE;
2740           }
2741         return build5 (TARGET_MEM_REF, currop->type,
2742                        baseop, currop->op2, genop0, currop->op1, genop1);
2743       }
2744       break;
2745     case ADDR_EXPR:
2746       if (currop->op0)
2747         {
2748           gcc_assert (is_gimple_min_invariant (currop->op0));
2749           return currop->op0;
2750         }
2751       /* Fallthrough.  */
2752     case REALPART_EXPR:
2753     case IMAGPART_EXPR:
2754     case VIEW_CONVERT_EXPR:
2755       {
2756         tree folded;
2757         tree genop0 = create_component_ref_by_pieces_1 (block, ref,
2758                                                         operand,
2759                                                         stmts, domstmt);
2760         if (!genop0)
2761           return NULL_TREE;
2762         folded = fold_build1 (currop->opcode, currop->type,
2763                               genop0);
2764         return folded;
2765       }
2766       break;
2767     case WITH_SIZE_EXPR:
2768       {
2769         tree genop0 = create_component_ref_by_pieces_1 (block, ref, operand,
2770                                                         stmts, domstmt);
2771         pre_expr op1expr = get_or_alloc_expr_for (currop->op0);
2772         tree genop1;
2773
2774         if (!genop0)
2775           return NULL_TREE;
2776
2777         genop1 = find_or_generate_expression (block, op1expr, stmts, domstmt);
2778         if (!genop1)
2779           return NULL_TREE;
2780
2781         return fold_build2 (currop->opcode, currop->type, genop0, genop1);
2782       }
2783       break;
2784     case BIT_FIELD_REF:
2785       {
2786         tree folded;
2787         tree genop0 = create_component_ref_by_pieces_1 (block, ref, operand,
2788                                                         stmts, domstmt);
2789         pre_expr op1expr = get_or_alloc_expr_for (currop->op0);
2790         pre_expr op2expr = get_or_alloc_expr_for (currop->op1);
2791         tree genop1;
2792         tree genop2;
2793
2794         if (!genop0)
2795           return NULL_TREE;
2796         genop1 = find_or_generate_expression (block, op1expr, stmts, domstmt);
2797         if (!genop1)
2798           return NULL_TREE;
2799         genop2 = find_or_generate_expression (block, op2expr, stmts, domstmt);
2800         if (!genop2)
2801           return NULL_TREE;
2802         folded = fold_build3 (BIT_FIELD_REF, currop->type, genop0, genop1,
2803                               genop2);
2804         return folded;
2805       }
2806
2807       /* For array ref vn_reference_op's, operand 1 of the array ref
2808          is op0 of the reference op and operand 3 of the array ref is
2809          op1.  */
2810     case ARRAY_RANGE_REF:
2811     case ARRAY_REF:
2812       {
2813         tree genop0;
2814         tree genop1 = currop->op0;
2815         pre_expr op1expr;
2816         tree genop2 = currop->op1;
2817         pre_expr op2expr;
2818         tree genop3 = currop->op2;
2819         pre_expr op3expr;
2820         genop0 = create_component_ref_by_pieces_1 (block, ref, operand,
2821                                                    stmts, domstmt);
2822         if (!genop0)
2823           return NULL_TREE;
2824         op1expr = get_or_alloc_expr_for (genop1);
2825         genop1 = find_or_generate_expression (block, op1expr, stmts, domstmt);
2826         if (!genop1)
2827           return NULL_TREE;
2828         if (genop2)
2829           {
2830             tree domain_type = TYPE_DOMAIN (TREE_TYPE (genop0));
2831             /* Drop zero minimum index if redundant.  */
2832             if (integer_zerop (genop2)
2833                 && (!domain_type
2834                     || integer_zerop (TYPE_MIN_VALUE (domain_type))))
2835               genop2 = NULL_TREE;
2836             else
2837               {
2838                 op2expr = get_or_alloc_expr_for (genop2);
2839                 genop2 = find_or_generate_expression (block, op2expr, stmts,
2840                                                       domstmt);
2841                 if (!genop2)
2842                   return NULL_TREE;
2843               }
2844           }
2845         if (genop3)
2846           {
2847             tree elmt_type = TREE_TYPE (TREE_TYPE (genop0));
2848             /* We can't always put a size in units of the element alignment
2849                here as the element alignment may be not visible.  See
2850                PR43783.  Simply drop the element size for constant
2851                sizes.  */
2852             if (tree_int_cst_equal (genop3, TYPE_SIZE_UNIT (elmt_type)))
2853               genop3 = NULL_TREE;
2854             else
2855               {
2856                 genop3 = size_binop (EXACT_DIV_EXPR, genop3,
2857                                      size_int (TYPE_ALIGN_UNIT (elmt_type)));
2858                 op3expr = get_or_alloc_expr_for (genop3);
2859                 genop3 = find_or_generate_expression (block, op3expr, stmts,
2860                                                       domstmt);
2861                 if (!genop3)
2862                   return NULL_TREE;
2863               }
2864           }
2865         return build4 (currop->opcode, currop->type, genop0, genop1,
2866                        genop2, genop3);
2867       }
2868     case COMPONENT_REF:
2869       {
2870         tree op0;
2871         tree op1;
2872         tree genop2 = currop->op1;
2873         pre_expr op2expr;
2874         op0 = create_component_ref_by_pieces_1 (block, ref, operand,
2875                                                 stmts, domstmt);
2876         if (!op0)
2877           return NULL_TREE;
2878         /* op1 should be a FIELD_DECL, which are represented by
2879            themselves.  */
2880         op1 = currop->op0;
2881         if (genop2)
2882           {
2883             op2expr = get_or_alloc_expr_for (genop2);
2884             genop2 = find_or_generate_expression (block, op2expr, stmts,
2885                                                   domstmt);
2886             if (!genop2)
2887               return NULL_TREE;
2888           }
2889
2890         return fold_build3 (COMPONENT_REF, TREE_TYPE (op1), op0, op1,
2891                             genop2);
2892       }
2893       break;
2894     case SSA_NAME:
2895       {
2896         pre_expr op0expr = get_or_alloc_expr_for (currop->op0);
2897         genop = find_or_generate_expression (block, op0expr, stmts, domstmt);
2898         return genop;
2899       }
2900     case STRING_CST:
2901     case INTEGER_CST:
2902     case COMPLEX_CST:
2903     case VECTOR_CST:
2904     case REAL_CST:
2905     case CONSTRUCTOR:
2906     case VAR_DECL:
2907     case PARM_DECL:
2908     case CONST_DECL:
2909     case RESULT_DECL:
2910     case FUNCTION_DECL:
2911       return currop->op0;
2912
2913     default:
2914       gcc_unreachable ();
2915     }
2916 }
2917
2918 /* For COMPONENT_REF's and ARRAY_REF's, we can't have any intermediates for the
2919    COMPONENT_REF or MEM_REF or ARRAY_REF portion, because we'd end up with
2920    trying to rename aggregates into ssa form directly, which is a no no.
2921
2922    Thus, this routine doesn't create temporaries, it just builds a
2923    single access expression for the array, calling
2924    find_or_generate_expression to build the innermost pieces.
2925
2926    This function is a subroutine of create_expression_by_pieces, and
2927    should not be called on it's own unless you really know what you
2928    are doing.  */
2929
2930 static tree
2931 create_component_ref_by_pieces (basic_block block, vn_reference_t ref,
2932                                 gimple_seq *stmts, gimple domstmt)
2933 {
2934   unsigned int op = 0;
2935   return create_component_ref_by_pieces_1 (block, ref, &op, stmts, domstmt);
2936 }
2937
2938 /* Find a leader for an expression, or generate one using
2939    create_expression_by_pieces if it's ANTIC but
2940    complex.
2941    BLOCK is the basic_block we are looking for leaders in.
2942    EXPR is the expression to find a leader or generate for.
2943    STMTS is the statement list to put the inserted expressions on.
2944    Returns the SSA_NAME of the LHS of the generated expression or the
2945    leader.
2946    DOMSTMT if non-NULL is a statement that should be dominated by
2947    all uses in the generated expression.  If DOMSTMT is non-NULL this
2948    routine can fail and return NULL_TREE.  Otherwise it will assert
2949    on failure.  */
2950
2951 static tree
2952 find_or_generate_expression (basic_block block, pre_expr expr,
2953                              gimple_seq *stmts, gimple domstmt)
2954 {
2955   pre_expr leader = bitmap_find_leader (AVAIL_OUT (block),
2956                                         get_expr_value_id (expr), domstmt);
2957   tree genop = NULL;
2958   if (leader)
2959     {
2960       if (leader->kind == NAME)
2961         genop = PRE_EXPR_NAME (leader);
2962       else if (leader->kind == CONSTANT)
2963         genop = PRE_EXPR_CONSTANT (leader);
2964     }
2965
2966   /* If it's still NULL, it must be a complex expression, so generate
2967      it recursively.  Not so if inserting expressions for values generated
2968      by SCCVN.  */
2969   if (genop == NULL
2970       && !domstmt)
2971     {
2972       bitmap_set_t exprset;
2973       unsigned int lookfor = get_expr_value_id (expr);
2974       bool handled = false;
2975       bitmap_iterator bi;
2976       unsigned int i;
2977
2978       exprset = VEC_index (bitmap_set_t, value_expressions, lookfor);
2979       FOR_EACH_EXPR_ID_IN_SET (exprset, i, bi)
2980         {
2981           pre_expr temp = expression_for_id (i);
2982           if (temp->kind != NAME)
2983             {
2984               handled = true;
2985               genop = create_expression_by_pieces (block, temp, stmts,
2986                                                    domstmt,
2987                                                    get_expr_type (expr));
2988               break;
2989             }
2990         }
2991       if (!handled && domstmt)
2992         return NULL_TREE;
2993
2994       gcc_assert (handled);
2995     }
2996   return genop;
2997 }
2998
2999 #define NECESSARY GF_PLF_1
3000
3001 /* Create an expression in pieces, so that we can handle very complex
3002    expressions that may be ANTIC, but not necessary GIMPLE.
3003    BLOCK is the basic block the expression will be inserted into,
3004    EXPR is the expression to insert (in value form)
3005    STMTS is a statement list to append the necessary insertions into.
3006
3007    This function will die if we hit some value that shouldn't be
3008    ANTIC but is (IE there is no leader for it, or its components).
3009    This function may also generate expressions that are themselves
3010    partially or fully redundant.  Those that are will be either made
3011    fully redundant during the next iteration of insert (for partially
3012    redundant ones), or eliminated by eliminate (for fully redundant
3013    ones).
3014
3015    If DOMSTMT is non-NULL then we make sure that all uses in the
3016    expressions dominate that statement.  In this case the function
3017    can return NULL_TREE to signal failure.  */
3018
3019 static tree
3020 create_expression_by_pieces (basic_block block, pre_expr expr,
3021                              gimple_seq *stmts, gimple domstmt, tree type)
3022 {
3023   tree temp, name;
3024   tree folded;
3025   gimple_seq forced_stmts = NULL;
3026   unsigned int value_id;
3027   gimple_stmt_iterator gsi;
3028   tree exprtype = type ? type : get_expr_type (expr);
3029   pre_expr nameexpr;
3030   gimple newstmt;
3031
3032   switch (expr->kind)
3033     {
3034       /* We may hit the NAME/CONSTANT case if we have to convert types
3035          that value numbering saw through.  */
3036     case NAME:
3037       folded = PRE_EXPR_NAME (expr);
3038       break;
3039     case CONSTANT:
3040       folded = PRE_EXPR_CONSTANT (expr);
3041       break;
3042     case REFERENCE:
3043       {
3044         vn_reference_t ref = PRE_EXPR_REFERENCE (expr);
3045         folded = create_component_ref_by_pieces (block, ref, stmts, domstmt);
3046       }
3047       break;
3048     case NARY:
3049       {
3050         vn_nary_op_t nary = PRE_EXPR_NARY (expr);
3051         tree *genop = XALLOCAVEC (tree, nary->length);
3052         unsigned i;
3053         for (i = 0; i < nary->length; ++i)
3054           {
3055             pre_expr op = get_or_alloc_expr_for (nary->op[i]);
3056             genop[i] = find_or_generate_expression (block, op,
3057                                                     stmts, domstmt);
3058             if (!genop[i])
3059               return NULL_TREE;
3060             /* Ensure genop[] is properly typed for POINTER_PLUS_EXPR.  It
3061                may have conversions stripped.  */
3062             if (nary->opcode == POINTER_PLUS_EXPR)
3063               {
3064                 if (i == 0)
3065                   genop[i] = fold_convert (nary->type, genop[i]);
3066                 else if (i == 1)
3067                   genop[i] = convert_to_ptrofftype (genop[i]);
3068               }
3069             else
3070               genop[i] = fold_convert (TREE_TYPE (nary->op[i]), genop[i]);
3071           }
3072         if (nary->opcode == CONSTRUCTOR)
3073           {
3074             VEC(constructor_elt,gc) *elts = NULL;
3075             for (i = 0; i < nary->length; ++i)
3076               CONSTRUCTOR_APPEND_ELT (elts, NULL_TREE, genop[i]);
3077             folded = build_constructor (nary->type, elts);
3078           }
3079         else
3080           {
3081             switch (nary->length)
3082               {
3083               case 1:
3084                 folded = fold_build1 (nary->opcode, nary->type,
3085                                       genop[0]);
3086                 break;
3087               case 2:
3088                 folded = fold_build2 (nary->opcode, nary->type,
3089                                       genop[0], genop[1]);
3090                 break;
3091               case 3:
3092                 folded = fold_build3 (nary->opcode, nary->type,
3093                                       genop[0], genop[1], genop[2]);
3094                 break;
3095               default:
3096                 gcc_unreachable ();
3097               }
3098           }
3099       }
3100       break;
3101     default:
3102       return NULL_TREE;
3103     }
3104
3105   if (!useless_type_conversion_p (exprtype, TREE_TYPE (folded)))
3106     folded = fold_convert (exprtype, folded);
3107
3108   /* Force the generated expression to be a sequence of GIMPLE
3109      statements.
3110      We have to call unshare_expr because force_gimple_operand may
3111      modify the tree we pass to it.  */
3112   folded = force_gimple_operand (unshare_expr (folded), &forced_stmts,
3113                                  false, NULL);
3114
3115   /* If we have any intermediate expressions to the value sets, add them
3116      to the value sets and chain them in the instruction stream.  */
3117   if (forced_stmts)
3118     {
3119       gsi = gsi_start (forced_stmts);
3120       for (; !gsi_end_p (gsi); gsi_next (&gsi))
3121         {
3122           gimple stmt = gsi_stmt (gsi);
3123           tree forcedname = gimple_get_lhs (stmt);
3124           pre_expr nameexpr;
3125
3126           if (TREE_CODE (forcedname) == SSA_NAME)
3127             {
3128               bitmap_set_bit (inserted_exprs, SSA_NAME_VERSION (forcedname));
3129               VN_INFO_GET (forcedname)->valnum = forcedname;
3130               VN_INFO (forcedname)->value_id = get_next_value_id ();
3131               nameexpr = get_or_alloc_expr_for_name (forcedname);
3132               add_to_value (VN_INFO (forcedname)->value_id, nameexpr);
3133               if (!in_fre)
3134                 bitmap_value_replace_in_set (NEW_SETS (block), nameexpr);
3135               bitmap_value_replace_in_set (AVAIL_OUT (block), nameexpr);
3136             }
3137           mark_symbols_for_renaming (stmt);
3138         }
3139       gimple_seq_add_seq (stmts, forced_stmts);
3140     }
3141
3142   /* Build and insert the assignment of the end result to the temporary
3143      that we will return.  */
3144   if (!pretemp || exprtype != TREE_TYPE (pretemp))
3145     pretemp = create_tmp_reg (exprtype, "pretmp");
3146
3147   temp = pretemp;
3148   add_referenced_var (temp);
3149
3150   newstmt = gimple_build_assign (temp, folded);
3151   name = make_ssa_name (temp, newstmt);
3152   gimple_assign_set_lhs (newstmt, name);
3153   gimple_set_plf (newstmt, NECESSARY, false);
3154
3155   gimple_seq_add_stmt (stmts, newstmt);
3156   bitmap_set_bit (inserted_exprs, SSA_NAME_VERSION (name));
3157
3158   /* All the symbols in NEWEXPR should be put into SSA form.  */
3159   mark_symbols_for_renaming (newstmt);
3160
3161   /* Fold the last statement.  */
3162   gsi = gsi_last (*stmts);
3163   if (fold_stmt_inplace (&gsi))
3164     update_stmt (gsi_stmt (gsi));
3165
3166   /* Add a value number to the temporary.
3167      The value may already exist in either NEW_SETS, or AVAIL_OUT, because
3168      we are creating the expression by pieces, and this particular piece of
3169      the expression may have been represented.  There is no harm in replacing
3170      here.  */
3171   VN_INFO_GET (name)->valnum = name;
3172   value_id = get_expr_value_id (expr);
3173   VN_INFO (name)->value_id = value_id;
3174   nameexpr = get_or_alloc_expr_for_name (name);
3175   add_to_value (value_id, nameexpr);
3176   if (NEW_SETS (block))
3177     bitmap_value_replace_in_set (NEW_SETS (block), nameexpr);
3178   bitmap_value_replace_in_set (AVAIL_OUT (block), nameexpr);
3179
3180   pre_stats.insertions++;
3181   if (dump_file && (dump_flags & TDF_DETAILS))
3182     {
3183       fprintf (dump_file, "Inserted ");
3184       print_gimple_stmt (dump_file, newstmt, 0, 0);
3185       fprintf (dump_file, " in predecessor %d\n", block->index);
3186     }
3187
3188   return name;
3189 }
3190
3191
3192 /* Returns true if we want to inhibit the insertions of PHI nodes
3193    for the given EXPR for basic block BB (a member of a loop).
3194    We want to do this, when we fear that the induction variable we
3195    create might inhibit vectorization.  */
3196
3197 static bool
3198 inhibit_phi_insertion (basic_block bb, pre_expr expr)
3199 {
3200   vn_reference_t vr = PRE_EXPR_REFERENCE (expr);
3201   VEC (vn_reference_op_s, heap) *ops = vr->operands;
3202   vn_reference_op_t op;
3203   unsigned i;
3204
3205   /* If we aren't going to vectorize we don't inhibit anything.  */
3206   if (!flag_tree_vectorize)
3207     return false;
3208
3209   /* Otherwise we inhibit the insertion when the address of the
3210      memory reference is a simple induction variable.  In other
3211      cases the vectorizer won't do anything anyway (either it's
3212      loop invariant or a complicated expression).  */
3213   FOR_EACH_VEC_ELT (vn_reference_op_s, ops, i, op)
3214     {
3215       switch (op->opcode)
3216         {
3217         case ARRAY_REF:
3218         case ARRAY_RANGE_REF:
3219           if (TREE_CODE (op->op0) != SSA_NAME)
3220             break;
3221           /* Fallthru.  */
3222         case SSA_NAME:
3223           {
3224             basic_block defbb = gimple_bb (SSA_NAME_DEF_STMT (op->op0));
3225             affine_iv iv;
3226             /* Default defs are loop invariant.  */
3227             if (!defbb)
3228               break;
3229             /* Defined outside this loop, also loop invariant.  */
3230             if (!flow_bb_inside_loop_p (bb->loop_father, defbb))
3231               break;
3232             /* If it's a simple induction variable inhibit insertion,
3233                the vectorizer might be interested in this one.  */
3234             if (simple_iv (bb->loop_father, bb->loop_father,
3235                            op->op0, &iv, true))
3236               return true;
3237             /* No simple IV, vectorizer can't do anything, hence no
3238                reason to inhibit the transformation for this operand.  */
3239             break;
3240           }
3241         default:
3242           break;
3243         }
3244     }
3245   return false;
3246 }
3247
3248 /* Insert the to-be-made-available values of expression EXPRNUM for each
3249    predecessor, stored in AVAIL, into the predecessors of BLOCK, and
3250    merge the result with a phi node, given the same value number as
3251    NODE.  Return true if we have inserted new stuff.  */
3252
3253 static bool
3254 insert_into_preds_of_block (basic_block block, unsigned int exprnum,
3255                             pre_expr *avail)
3256 {
3257   pre_expr expr = expression_for_id (exprnum);
3258   pre_expr newphi;
3259   unsigned int val = get_expr_value_id (expr);
3260   edge pred;
3261   bool insertions = false;
3262   bool nophi = false;
3263   basic_block bprime;
3264   pre_expr eprime;
3265   edge_iterator ei;
3266   tree type = get_expr_type (expr);
3267   tree temp;
3268   gimple phi;
3269
3270   if (dump_file && (dump_flags & TDF_DETAILS))
3271     {
3272       fprintf (dump_file, "Found partial redundancy for expression ");
3273       print_pre_expr (dump_file, expr);
3274       fprintf (dump_file, " (%04d)\n", val);
3275     }
3276
3277   /* Make sure we aren't creating an induction variable.  */
3278   if (block->loop_depth > 0 && EDGE_COUNT (block->preds) == 2)
3279     {
3280       bool firstinsideloop = false;
3281       bool secondinsideloop = false;
3282       firstinsideloop = flow_bb_inside_loop_p (block->loop_father,
3283                                                EDGE_PRED (block, 0)->src);
3284       secondinsideloop = flow_bb_inside_loop_p (block->loop_father,
3285                                                 EDGE_PRED (block, 1)->src);
3286       /* Induction variables only have one edge inside the loop.  */
3287       if ((firstinsideloop ^ secondinsideloop)
3288           && (expr->kind != REFERENCE
3289               || inhibit_phi_insertion (block, expr)))
3290         {
3291           if (dump_file && (dump_flags & TDF_DETAILS))
3292             fprintf (dump_file, "Skipping insertion of phi for partial redundancy: Looks like an induction variable\n");
3293           nophi = true;
3294         }
3295     }
3296
3297   /* Make the necessary insertions.  */
3298   FOR_EACH_EDGE (pred, ei, block->preds)
3299     {
3300       gimple_seq stmts = NULL;
3301       tree builtexpr;
3302       bprime = pred->src;
3303       eprime = avail[bprime->index];
3304
3305       if (eprime->kind != NAME && eprime->kind != CONSTANT)
3306         {
3307           builtexpr = create_expression_by_pieces (bprime,
3308                                                    eprime,
3309                                                    &stmts, NULL,
3310                                                    type);
3311           gcc_assert (!(pred->flags & EDGE_ABNORMAL));
3312           gsi_insert_seq_on_edge (pred, stmts);
3313           avail[bprime->index] = get_or_alloc_expr_for_name (builtexpr);
3314           insertions = true;
3315         }
3316       else if (eprime->kind == CONSTANT)
3317         {
3318           /* Constants may not have the right type, fold_convert
3319              should give us back a constant with the right type.
3320           */
3321           tree constant = PRE_EXPR_CONSTANT (eprime);
3322           if (!useless_type_conversion_p (type, TREE_TYPE (constant)))
3323             {
3324               tree builtexpr = fold_convert (type, constant);
3325               if (!is_gimple_min_invariant (builtexpr))
3326                 {
3327                   tree forcedexpr = force_gimple_operand (builtexpr,
3328                                                           &stmts, true,
3329                                                           NULL);
3330                   if (!is_gimple_min_invariant (forcedexpr))
3331                     {
3332                       if (forcedexpr != builtexpr)
3333                         {
3334                           VN_INFO_GET (forcedexpr)->valnum = PRE_EXPR_CONSTANT (eprime);
3335                           VN_INFO (forcedexpr)->value_id = get_expr_value_id (eprime);
3336                         }
3337                       if (stmts)
3338                         {
3339                           gimple_stmt_iterator gsi;
3340                           gsi = gsi_start (stmts);
3341                           for (; !gsi_end_p (gsi); gsi_next (&gsi))
3342                             {
3343                               gimple stmt = gsi_stmt (gsi);
3344                               tree lhs = gimple_get_lhs (stmt);
3345                               if (TREE_CODE (lhs) == SSA_NAME)
3346                                 bitmap_set_bit (inserted_exprs,
3347                                                 SSA_NAME_VERSION (lhs));
3348                               gimple_set_plf (stmt, NECESSARY, false);
3349                             }
3350                           gsi_insert_seq_on_edge (pred, stmts);
3351                         }
3352                       avail[bprime->index] = get_or_alloc_expr_for_name (forcedexpr);
3353                     }
3354                 }
3355               else
3356                 avail[bprime->index] = get_or_alloc_expr_for_constant (builtexpr);
3357             }
3358         }
3359       else if (eprime->kind == NAME)
3360         {
3361           /* We may have to do a conversion because our value
3362              numbering can look through types in certain cases, but
3363              our IL requires all operands of a phi node have the same
3364              type.  */
3365           tree name = PRE_EXPR_NAME (eprime);
3366           if (!useless_type_conversion_p (type, TREE_TYPE (name)))
3367             {
3368               tree builtexpr;
3369               tree forcedexpr;
3370               builtexpr = fold_convert (type, name);
3371               forcedexpr = force_gimple_operand (builtexpr,
3372                                                  &stmts, true,
3373                                                  NULL);
3374
3375               if (forcedexpr != name)
3376                 {
3377                   VN_INFO_GET (forcedexpr)->valnum = VN_INFO (name)->valnum;
3378                   VN_INFO (forcedexpr)->value_id = VN_INFO (name)->value_id;
3379                 }
3380
3381               if (stmts)
3382                 {
3383                   gimple_stmt_iterator gsi;
3384                   gsi = gsi_start (stmts);
3385                   for (; !gsi_end_p (gsi); gsi_next (&gsi))
3386                     {
3387                       gimple stmt = gsi_stmt (gsi);
3388                       tree lhs = gimple_get_lhs (stmt);
3389                       if (TREE_CODE (lhs) == SSA_NAME)
3390                         bitmap_set_bit (inserted_exprs, SSA_NAME_VERSION (lhs));
3391                       gimple_set_plf (stmt, NECESSARY, false);
3392                     }
3393                   gsi_insert_seq_on_edge (pred, stmts);
3394                 }
3395               avail[bprime->index] = get_or_alloc_expr_for_name (forcedexpr);
3396             }
3397         }
3398     }
3399   /* If we didn't want a phi node, and we made insertions, we still have
3400      inserted new stuff, and thus return true.  If we didn't want a phi node,
3401      and didn't make insertions, we haven't added anything new, so return
3402      false.  */
3403   if (nophi && insertions)
3404     return true;
3405   else if (nophi && !insertions)
3406     return false;
3407
3408   /* Now build a phi for the new variable.  */
3409   if (!prephitemp || TREE_TYPE (prephitemp) != type)
3410     prephitemp = create_tmp_var (type, "prephitmp");
3411
3412   temp = prephitemp;
3413   add_referenced_var (temp);
3414
3415   if (TREE_CODE (type) == COMPLEX_TYPE
3416       || TREE_CODE (type) == VECTOR_TYPE)
3417     DECL_GIMPLE_REG_P (temp) = 1;
3418   phi = create_phi_node (temp, block);
3419
3420   gimple_set_plf (phi, NECESSARY, false);
3421   VN_INFO_GET (gimple_phi_result (phi))->valnum = gimple_phi_result (phi);
3422   VN_INFO (gimple_phi_result (phi))->value_id = val;
3423   bitmap_set_bit (inserted_exprs, SSA_NAME_VERSION (gimple_phi_result (phi)));
3424   FOR_EACH_EDGE (pred, ei, block->preds)
3425     {
3426       pre_expr ae = avail[pred->src->index];
3427       gcc_assert (get_expr_type (ae) == type
3428                   || useless_type_conversion_p (type, get_expr_type (ae)));
3429       if (ae->kind == CONSTANT)
3430         add_phi_arg (phi, PRE_EXPR_CONSTANT (ae), pred, UNKNOWN_LOCATION);
3431       else
3432         add_phi_arg (phi, PRE_EXPR_NAME (avail[pred->src->index]), pred,
3433                      UNKNOWN_LOCATION);
3434     }
3435
3436   newphi = get_or_alloc_expr_for_name (gimple_phi_result (phi));
3437   add_to_value (val, newphi);
3438
3439   /* The value should *not* exist in PHI_GEN, or else we wouldn't be doing
3440      this insertion, since we test for the existence of this value in PHI_GEN
3441      before proceeding with the partial redundancy checks in insert_aux.
3442
3443      The value may exist in AVAIL_OUT, in particular, it could be represented
3444      by the expression we are trying to eliminate, in which case we want the
3445      replacement to occur.  If it's not existing in AVAIL_OUT, we want it
3446      inserted there.
3447
3448      Similarly, to the PHI_GEN case, the value should not exist in NEW_SETS of
3449      this block, because if it did, it would have existed in our dominator's
3450      AVAIL_OUT, and would have been skipped due to the full redundancy check.
3451   */
3452
3453   bitmap_insert_into_set (PHI_GEN (block), newphi);
3454   bitmap_value_replace_in_set (AVAIL_OUT (block),
3455                                newphi);
3456   bitmap_insert_into_set (NEW_SETS (block),
3457                           newphi);
3458
3459   if (dump_file && (dump_flags & TDF_DETAILS))
3460     {
3461       fprintf (dump_file, "Created phi ");
3462       print_gimple_stmt (dump_file, phi, 0, 0);
3463       fprintf (dump_file, " in block %d\n", block->index);
3464     }
3465   pre_stats.phis++;
3466   return true;
3467 }
3468
3469
3470
3471 /* Perform insertion of partially redundant values.
3472    For BLOCK, do the following:
3473    1.  Propagate the NEW_SETS of the dominator into the current block.
3474    If the block has multiple predecessors,
3475        2a. Iterate over the ANTIC expressions for the block to see if
3476            any of them are partially redundant.
3477        2b. If so, insert them into the necessary predecessors to make
3478            the expression fully redundant.
3479        2c. Insert a new PHI merging the values of the predecessors.
3480        2d. Insert the new PHI, and the new expressions, into the
3481            NEW_SETS set.
3482    3. Recursively call ourselves on the dominator children of BLOCK.
3483
3484    Steps 1, 2a, and 3 are done by insert_aux. 2b, 2c and 2d are done by
3485    do_regular_insertion and do_partial_insertion.
3486
3487 */
3488
3489 static bool
3490 do_regular_insertion (basic_block block, basic_block dom)
3491 {
3492   bool new_stuff = false;
3493   VEC (pre_expr, heap) *exprs = sorted_array_from_bitmap_set (ANTIC_IN (block));
3494   pre_expr expr;
3495   int i;
3496
3497   FOR_EACH_VEC_ELT (pre_expr, exprs, i, expr)
3498     {
3499       if (expr->kind == NARY
3500           || expr->kind == REFERENCE)
3501         {
3502           pre_expr *avail;
3503           unsigned int val;
3504           bool by_some = false;
3505           bool cant_insert = false;
3506           bool all_same = true;
3507           pre_expr first_s = NULL;
3508           edge pred;
3509           basic_block bprime;
3510           pre_expr eprime = NULL;
3511           edge_iterator ei;
3512           pre_expr edoubleprime = NULL;
3513           bool do_insertion = false;
3514
3515           val = get_expr_value_id (expr);
3516           if (bitmap_set_contains_value (PHI_GEN (block), val))
3517             continue;
3518           if (bitmap_set_contains_value (AVAIL_OUT (dom), val))
3519             {
3520               if (dump_file && (dump_flags & TDF_DETAILS))
3521                 fprintf (dump_file, "Found fully redundant value\n");
3522               continue;
3523             }
3524
3525           avail = XCNEWVEC (pre_expr, last_basic_block);
3526           FOR_EACH_EDGE (pred, ei, block->preds)
3527             {
3528               unsigned int vprime;
3529
3530               /* We should never run insertion for the exit block
3531                  and so not come across fake pred edges.  */
3532               gcc_assert (!(pred->flags & EDGE_FAKE));
3533               bprime = pred->src;
3534               eprime = phi_translate (expr, ANTIC_IN (block), NULL,
3535                                       bprime, block);
3536
3537               /* eprime will generally only be NULL if the
3538                  value of the expression, translated
3539                  through the PHI for this predecessor, is
3540                  undefined.  If that is the case, we can't
3541                  make the expression fully redundant,
3542                  because its value is undefined along a
3543                  predecessor path.  We can thus break out
3544                  early because it doesn't matter what the
3545                  rest of the results are.  */
3546               if (eprime == NULL)
3547                 {
3548                   cant_insert = true;
3549                   break;
3550                 }
3551
3552               eprime = fully_constant_expression (eprime);
3553               vprime = get_expr_value_id (eprime);
3554               edoubleprime = bitmap_find_leader (AVAIL_OUT (bprime),
3555                                                  vprime, NULL);
3556               if (edoubleprime == NULL)
3557                 {
3558                   avail[bprime->index] = eprime;
3559                   all_same = false;
3560                 }
3561               else
3562                 {
3563                   avail[bprime->index] = edoubleprime;
3564                   by_some = true;
3565                   /* We want to perform insertions to remove a redundancy on
3566                      a path in the CFG we want to optimize for speed.  */
3567                   if (optimize_edge_for_speed_p (pred))
3568                     do_insertion = true;
3569                   if (first_s == NULL)
3570                     first_s = edoubleprime;
3571                   else if (!pre_expr_eq (first_s, edoubleprime))
3572                     all_same = false;
3573                 }
3574             }
3575           /* If we can insert it, it's not the same value
3576              already existing along every predecessor, and
3577              it's defined by some predecessor, it is
3578              partially redundant.  */
3579           if (!cant_insert && !all_same && by_some)
3580             {
3581               if (!do_insertion)
3582                 {
3583                   if (dump_file && (dump_flags & TDF_DETAILS))
3584                     {
3585                       fprintf (dump_file, "Skipping partial redundancy for "
3586                                "expression ");
3587                       print_pre_expr (dump_file, expr);
3588                       fprintf (dump_file, " (%04d), no redundancy on to be "
3589                                "optimized for speed edge\n", val);
3590                     }
3591                 }
3592               else if (dbg_cnt (treepre_insert)
3593                        && insert_into_preds_of_block (block,
3594                                                       get_expression_id (expr),
3595                                                       avail))
3596                 new_stuff = true;
3597             }
3598           /* If all edges produce the same value and that value is
3599              an invariant, then the PHI has the same value on all
3600              edges.  Note this.  */
3601           else if (!cant_insert && all_same)
3602             {
3603               tree exprtype = get_expr_type (expr);
3604               tree temp;
3605               gimple assign;
3606               pre_expr newe;
3607               gimple_stmt_iterator gsi;
3608
3609               gcc_assert (edoubleprime->kind == CONSTANT
3610                           || edoubleprime->kind == NAME);
3611
3612               if (!pretemp || TREE_TYPE (pretemp) != exprtype)
3613                 {
3614                   pretemp = create_tmp_reg (exprtype, "pretmp");
3615                   add_referenced_var (pretemp);
3616                 }
3617               temp = make_ssa_name (pretemp, NULL);
3618               assign = gimple_build_assign (temp,
3619                                             edoubleprime->kind == CONSTANT ? PRE_EXPR_CONSTANT (edoubleprime) : PRE_EXPR_NAME (edoubleprime));
3620               gsi = gsi_after_labels (block);
3621               gsi_insert_before (&gsi, assign, GSI_NEW_STMT);
3622
3623               gimple_set_plf (assign, NECESSARY, false);
3624               VN_INFO_GET (temp)->value_id = val;
3625               VN_INFO (temp)->valnum = temp;
3626               bitmap_set_bit (inserted_exprs, SSA_NAME_VERSION (temp));
3627               newe = get_or_alloc_expr_for_name (temp);
3628               add_to_value (val, newe);
3629               bitmap_value_replace_in_set (AVAIL_OUT (block), newe);
3630               bitmap_insert_into_set (NEW_SETS (block), newe);
3631             }
3632           free (avail);
3633         }
3634     }
3635
3636   VEC_free (pre_expr, heap, exprs);
3637   return new_stuff;
3638 }
3639
3640
3641 /* Perform insertion for partially anticipatable expressions.  There
3642    is only one case we will perform insertion for these.  This case is
3643    if the expression is partially anticipatable, and fully available.
3644    In this case, we know that putting it earlier will enable us to
3645    remove the later computation.  */
3646
3647
3648 static bool
3649 do_partial_partial_insertion (basic_block block, basic_block dom)
3650 {
3651   bool new_stuff = false;
3652   VEC (pre_expr, heap) *exprs = sorted_array_from_bitmap_set (PA_IN (block));
3653   pre_expr expr;
3654   int i;
3655
3656   FOR_EACH_VEC_ELT (pre_expr, exprs, i, expr)
3657     {
3658       if (expr->kind == NARY
3659           || expr->kind == REFERENCE)
3660         {
3661           pre_expr *avail;
3662           unsigned int val;
3663           bool by_all = true;
3664           bool cant_insert = false;
3665           edge pred;
3666           basic_block bprime;
3667           pre_expr eprime = NULL;
3668           edge_iterator ei;
3669
3670           val = get_expr_value_id (expr);
3671           if (bitmap_set_contains_value (PHI_GEN (block), val))
3672             continue;
3673           if (bitmap_set_contains_value (AVAIL_OUT (dom), val))
3674             continue;
3675
3676           avail = XCNEWVEC (pre_expr, last_basic_block);
3677           FOR_EACH_EDGE (pred, ei, block->preds)
3678             {
3679               unsigned int vprime;
3680               pre_expr edoubleprime;
3681
3682               /* We should never run insertion for the exit block
3683                  and so not come across fake pred edges.  */
3684               gcc_assert (!(pred->flags & EDGE_FAKE));
3685               bprime = pred->src;
3686               eprime = phi_translate (expr, ANTIC_IN (block),
3687                                       PA_IN (block),
3688                                       bprime, block);
3689
3690               /* eprime will generally only be NULL if the
3691                  value of the expression, translated
3692                  through the PHI for this predecessor, is
3693                  undefined.  If that is the case, we can't
3694                  make the expression fully redundant,
3695                  because its value is undefined along a
3696                  predecessor path.  We can thus break out
3697                  early because it doesn't matter what the
3698                  rest of the results are.  */
3699               if (eprime == NULL)
3700                 {
3701                   cant_insert = true;
3702                   break;
3703                 }
3704
3705               eprime = fully_constant_expression (eprime);
3706               vprime = get_expr_value_id (eprime);
3707               edoubleprime = bitmap_find_leader (AVAIL_OUT (bprime),
3708                                                  vprime, NULL);
3709               if (edoubleprime == NULL)
3710                 {
3711                   by_all = false;
3712                   break;
3713                 }
3714               else
3715                 avail[bprime->index] = edoubleprime;
3716
3717             }
3718
3719           /* If we can insert it, it's not the same value
3720              already existing along every predecessor, and
3721              it's defined by some predecessor, it is
3722              partially redundant.  */
3723           if (!cant_insert && by_all && dbg_cnt (treepre_insert))
3724             {
3725               pre_stats.pa_insert++;
3726               if (insert_into_preds_of_block (block, get_expression_id (expr),
3727                                               avail))
3728                 new_stuff = true;
3729             }
3730           free (avail);
3731         }
3732     }
3733
3734   VEC_free (pre_expr, heap, exprs);
3735   return new_stuff;
3736 }
3737
3738 static bool
3739 insert_aux (basic_block block)
3740 {
3741   basic_block son;
3742   bool new_stuff = false;
3743
3744   if (block)
3745     {
3746       basic_block dom;
3747       dom = get_immediate_dominator (CDI_DOMINATORS, block);
3748       if (dom)
3749         {
3750           unsigned i;
3751           bitmap_iterator bi;
3752           bitmap_set_t newset = NEW_SETS (dom);
3753           if (newset)
3754             {
3755               /* Note that we need to value_replace both NEW_SETS, and
3756                  AVAIL_OUT. For both the case of NEW_SETS, the value may be
3757                  represented by some non-simple expression here that we want
3758                  to replace it with.  */
3759               FOR_EACH_EXPR_ID_IN_SET (newset, i, bi)
3760                 {
3761                   pre_expr expr = expression_for_id (i);
3762                   bitmap_value_replace_in_set (NEW_SETS (block), expr);
3763                   bitmap_value_replace_in_set (AVAIL_OUT (block), expr);
3764                 }
3765             }
3766           if (!single_pred_p (block))
3767             {
3768               new_stuff |= do_regular_insertion (block, dom);
3769               if (do_partial_partial)
3770                 new_stuff |= do_partial_partial_insertion (block, dom);
3771             }
3772         }
3773     }
3774   for (son = first_dom_son (CDI_DOMINATORS, block);
3775        son;
3776        son = next_dom_son (CDI_DOMINATORS, son))
3777     {
3778       new_stuff |= insert_aux (son);
3779     }
3780
3781   return new_stuff;
3782 }
3783
3784 /* Perform insertion of partially redundant values.  */
3785
3786 static void
3787 insert (void)
3788 {
3789   bool new_stuff = true;
3790   basic_block bb;
3791   int num_iterations = 0;
3792
3793   FOR_ALL_BB (bb)
3794     NEW_SETS (bb) = bitmap_set_new ();
3795
3796   while (new_stuff)
3797     {
3798       num_iterations++;
3799       new_stuff = insert_aux (ENTRY_BLOCK_PTR);
3800     }
3801   statistics_histogram_event (cfun, "insert iterations", num_iterations);
3802 }
3803
3804
3805 /* Add OP to EXP_GEN (block), and possibly to the maximal set.  */
3806
3807 static void
3808 add_to_exp_gen (basic_block block, tree op)
3809 {
3810   if (!in_fre)
3811     {
3812       pre_expr result;
3813       if (TREE_CODE (op) == SSA_NAME && ssa_undefined_value_p (op))
3814         return;
3815       result = get_or_alloc_expr_for_name (op);
3816       bitmap_value_insert_into_set (EXP_GEN (block), result);
3817     }
3818 }
3819
3820 /* Create value ids for PHI in BLOCK.  */
3821
3822 static void
3823 make_values_for_phi (gimple phi, basic_block block)
3824 {
3825   tree result = gimple_phi_result (phi);
3826
3827   /* We have no need for virtual phis, as they don't represent
3828      actual computations.  */
3829   if (is_gimple_reg (result))
3830     {
3831       pre_expr e = get_or_alloc_expr_for_name (result);
3832       add_to_value (get_expr_value_id (e), e);
3833       bitmap_insert_into_set (PHI_GEN (block), e);
3834       bitmap_value_insert_into_set (AVAIL_OUT (block), e);
3835       if (!in_fre)
3836         {
3837           unsigned i;
3838           for (i = 0; i < gimple_phi_num_args (phi); ++i)
3839             {
3840               tree arg = gimple_phi_arg_def (phi, i);
3841               if (TREE_CODE (arg) == SSA_NAME)
3842                 {
3843                   e = get_or_alloc_expr_for_name (arg);
3844                   add_to_value (get_expr_value_id (e), e);
3845                 }
3846             }
3847         }
3848     }
3849 }
3850
3851 /* Compute the AVAIL set for all basic blocks.
3852
3853    This function performs value numbering of the statements in each basic
3854    block.  The AVAIL sets are built from information we glean while doing
3855    this value numbering, since the AVAIL sets contain only one entry per
3856    value.
3857
3858    AVAIL_IN[BLOCK] = AVAIL_OUT[dom(BLOCK)].
3859    AVAIL_OUT[BLOCK] = AVAIL_IN[BLOCK] U PHI_GEN[BLOCK] U TMP_GEN[BLOCK].  */
3860
3861 static void
3862 compute_avail (void)
3863 {
3864
3865   basic_block block, son;
3866   basic_block *worklist;
3867   size_t sp = 0;
3868   unsigned i;
3869
3870   /* We pretend that default definitions are defined in the entry block.
3871      This includes function arguments and the static chain decl.  */
3872   for (i = 1; i < num_ssa_names; ++i)
3873     {
3874       tree name = ssa_name (i);
3875       pre_expr e;
3876       if (!name
3877           || !SSA_NAME_IS_DEFAULT_DEF (name)
3878           || has_zero_uses (name)
3879           || !is_gimple_reg (name))
3880         continue;
3881
3882       e = get_or_alloc_expr_for_name (name);
3883       add_to_value (get_expr_value_id (e), e);
3884       if (!in_fre)
3885         bitmap_insert_into_set (TMP_GEN (ENTRY_BLOCK_PTR), e);
3886       bitmap_value_insert_into_set (AVAIL_OUT (ENTRY_BLOCK_PTR), e);
3887     }
3888
3889   /* Allocate the worklist.  */
3890   worklist = XNEWVEC (basic_block, n_basic_blocks);
3891
3892   /* Seed the algorithm by putting the dominator children of the entry
3893      block on the worklist.  */
3894   for (son = first_dom_son (CDI_DOMINATORS, ENTRY_BLOCK_PTR);
3895        son;
3896        son = next_dom_son (CDI_DOMINATORS, son))
3897     worklist[sp++] = son;
3898
3899   /* Loop until the worklist is empty.  */
3900   while (sp)
3901     {
3902       gimple_stmt_iterator gsi;
3903       gimple stmt;
3904       basic_block dom;
3905       unsigned int stmt_uid = 1;
3906
3907       /* Pick a block from the worklist.  */
3908       block = worklist[--sp];
3909
3910       /* Initially, the set of available values in BLOCK is that of
3911          its immediate dominator.  */
3912       dom = get_immediate_dominator (CDI_DOMINATORS, block);
3913       if (dom)
3914         bitmap_set_copy (AVAIL_OUT (block), AVAIL_OUT (dom));
3915
3916       /* Generate values for PHI nodes.  */
3917       for (gsi = gsi_start_phis (block); !gsi_end_p (gsi); gsi_next (&gsi))
3918         make_values_for_phi (gsi_stmt (gsi), block);
3919
3920       BB_MAY_NOTRETURN (block) = 0;
3921
3922       /* Now compute value numbers and populate value sets with all
3923          the expressions computed in BLOCK.  */
3924       for (gsi = gsi_start_bb (block); !gsi_end_p (gsi); gsi_next (&gsi))
3925         {
3926           ssa_op_iter iter;
3927           tree op;
3928
3929           stmt = gsi_stmt (gsi);
3930           gimple_set_uid (stmt, stmt_uid++);
3931
3932           /* Cache whether the basic-block has any non-visible side-effect
3933              or control flow.
3934              If this isn't a call or it is the last stmt in the
3935              basic-block then the CFG represents things correctly.  */
3936           if (is_gimple_call (stmt) && !stmt_ends_bb_p (stmt))
3937             {
3938               /* Non-looping const functions always return normally.
3939                  Otherwise the call might not return or have side-effects
3940                  that forbids hoisting possibly trapping expressions
3941                  before it.  */
3942               int flags = gimple_call_flags (stmt);
3943               if (!(flags & ECF_CONST)
3944                   || (flags & ECF_LOOPING_CONST_OR_PURE))
3945                 BB_MAY_NOTRETURN (block) = 1;
3946             }
3947
3948           FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_DEF)
3949             {
3950               pre_expr e = get_or_alloc_expr_for_name (op);
3951