Merge branch 'vendor/GCC47'
[dragonfly.git] / contrib / gcc-4.7 / gcc / tree-ssa-pre.c
CommitLineData
e4b17023
JM
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
7This file is part of GCC.
8
9GCC is free software; you can redistribute it and/or modify
10it under the terms of the GNU General Public License as published by
11the Free Software Foundation; either version 3, or (at your option)
12any later version.
13
14GCC is distributed in the hope that it will be useful,
15but WITHOUT ANY WARRANTY; without even the implied warranty of
16MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17GNU General Public License for more details.
18
19You should have received a copy of the GNU General Public License
20along 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
156enum pre_expr_kind
157{
158 NAME,
159 NARY,
160 REFERENCE,
161 CONSTANT
162};
163
164typedef 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
172typedef 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
184static int
185pre_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
210static hashval_t
211pre_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. */
231static unsigned int next_expression_id;
232
233/* Mapping from expression to id number we can use in bitmap sets. */
234DEF_VEC_P (pre_expr);
235DEF_VEC_ALLOC_P (pre_expr, heap);
236static VEC(pre_expr, heap) *expressions;
237static htab_t expression_to_id;
238static VEC(unsigned, heap) *name_to_id;
239
240/* Allocate an expression id for EXPR. */
241
242static inline unsigned int
243alloc_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
272static inline unsigned int
273get_expression_id (const pre_expr expr)
274{
275 return expr->id;
276}
277
278static inline unsigned int
279lookup_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
302static inline unsigned int
303get_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
313static inline pre_expr
314expression_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
322static void
323clear_expression_ids (void)
324{
325 VEC_free (pre_expr, heap, expressions);
326}
327
328static alloc_pool pre_expr_pool;
329
330/* Given an SSA_NAME NAME, get or create a pre_expr to represent it. */
331
332static pre_expr
333get_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
353static bool in_fre = false;
354
355/* An unordered bitmap set. One bitmap tracks values, the other,
356 expressions. */
357typedef 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. */
370DEF_VEC_P (bitmap_set_t);
371DEF_VEC_ALLOC_P (bitmap_set_t, heap);
372static VEC(bitmap_set_t, heap) *value_expressions;
373
374/* Sets that we need to keep track of. */
375typedef 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. */
434static int *postorder;
435
436/* This structure is used to keep track of statistics on what
437 optimization PRE was able to perform. */
438static 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;
e4b17023
JM
451} pre_stats;
452
453static bool do_partial_partial;
454static pre_expr bitmap_find_leader (bitmap_set_t, unsigned int, gimple);
455static void bitmap_value_insert_into_set (bitmap_set_t, pre_expr);
456static void bitmap_value_replace_in_set (bitmap_set_t, pre_expr);
457static void bitmap_set_copy (bitmap_set_t, bitmap_set_t);
458static bool bitmap_set_contains_value (bitmap_set_t, unsigned int);
459static void bitmap_insert_into_set (bitmap_set_t, pre_expr);
460static void bitmap_insert_into_set_1 (bitmap_set_t, pre_expr,
461 unsigned int, bool);
462static bitmap_set_t bitmap_set_new (void);
463static tree create_expression_by_pieces (basic_block, pre_expr, gimple_seq *,
464 gimple, tree);
465static tree find_or_generate_expression (basic_block, pre_expr, gimple_seq *,
466 gimple);
467static 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
472static alloc_pool bitmap_set_pool;
473static 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. */
479static tree pretemp;
480static tree storetemp;
481static tree prephitemp;
482
483/* Set of blocks with statements that have had their EH properties changed. */
484static bitmap need_eh_cleanup;
485
486/* Set of blocks with statements that have had their AB properties changed. */
487static bitmap need_ab_cleanup;
488
489/* The phi_translate_table caches phi translations for a given
490 expression and predecessor. */
491
492static 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
497typedef 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;
512typedef const struct expr_pred_trans_d *const_expr_pred_trans_t;
513
514/* Return the hash value for a phi translation table entry. */
515
516static hashval_t
517expr_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
526static int
527expr_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
545static inline pre_expr
546phi_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
566static inline void
567phi_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
586void
587add_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
611static bitmap_set_t
612bitmap_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
622static unsigned int
623get_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
651static void
652bitmap_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
662static void
663bitmap_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
677static void
678bitmap_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
685static void
686bitmap_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. */
694static void
695bitmap_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
704static VEC(pre_expr, heap) *
705sorted_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
739static void
740bitmap_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
765static bitmap_set_t
766bitmap_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
787static void
788bitmap_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
809static bool
810bitmap_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
821static inline bool
822bitmap_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
829static void
830bitmap_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 }
5ce9237c
JM
861
862 gcc_unreachable ();
e4b17023
JM
863}
864
865/* Return true if two bitmap sets are equal. */
866
867static bool
868bitmap_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
876static void
877bitmap_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
890static void
891bitmap_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
908static void
909print_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}
984void debug_pre_expr (pre_expr);
985
986/* Like print_pre_expr but always prints to stderr. */
987DEBUG_FUNCTION void
988debug_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
996static void
997print_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
1022void debug_bitmap_set (bitmap_set_t);
1023
1024DEBUG_FUNCTION void
1025debug_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
1032void
1033print_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
1045DEBUG_FUNCTION void
1046debug_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
1054static pre_expr
1055get_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
1081static tree
1082get_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. */
1102static pre_expr
1103get_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
1139static pre_expr
1140fully_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
1238static tree
1239translate_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
1312static inline pre_expr
1313find_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
1325static tree
1326get_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
1350static tree
1351get_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
1425static pre_expr
1426phi_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
1433static pre_expr
1434phi_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 {
e4b17023 1759 tree name = PRE_EXPR_NAME (expr);
95d28233
JM
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. */
e4b17023
JM
1763 if (gimple_code (def_stmt) == GIMPLE_PHI
1764 && gimple_bb (def_stmt) == phiblock)
e4b17023 1765 {
95d28233
JM
1766 edge e = find_edge (pred, gimple_bb (def_stmt));
1767 tree def = PHI_ARG_DEF (def_stmt, e->dest_idx);
e4b17023
JM
1768
1769 /* Handle constant. */
1770 if (is_gimple_min_invariant (def))
1771 return get_or_alloc_expr_for_constant (def);
1772
95d28233 1773 return get_or_alloc_expr_for_name (def);
e4b17023 1774 }
95d28233
JM
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;
e4b17023 1778 }
e4b17023
JM
1779
1780 default:
1781 gcc_unreachable ();
1782 }
1783}
1784
1785/* Wrapper around phi_translate_1 providing caching functionality. */
1786
1787static pre_expr
1788phi_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
1827static void
1828phi_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
1866static pre_expr
1867bitmap_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
1929static bool
1930value_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 */
2008static bool
2009vro_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
2062static bool
2063valid_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
2133static void
2134dependent_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
2152static void
2153clean (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
2167static 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
2172static 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
2178static bool
2179defer_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
2204static bool
2205compute_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*/
2375static bool
2376compute_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
2503static void
2504compute_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
2610static bool
2611can_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. */
2627static 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 */
2632static VEC(gimple, heap) *need_creation;
2633
2634/* The actual worker for create_component_ref_by_pieces. */
2635
2636static tree
2637create_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
2930static tree
2931create_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
2951static tree
2952find_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
3019static tree
3020create_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);
5ce9237c 3051 tree *genop = XALLOCAVEC (tree, nary->length);
e4b17023
JM
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,
5ce9237c 3093 genop[0], genop[1], genop[2]);
e4b17023
JM
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
3197static bool
3198inhibit_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
3253static bool
3254insert_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
3489static bool
3490do_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 {
5ce9237c
JM
3499 if (expr->kind == NARY
3500 || expr->kind == REFERENCE)
e4b17023
JM
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. */
5ce9237c 3601 else if (!cant_insert && all_same)
e4b17023 3602 {
5ce9237c
JM
3603 tree exprtype = get_expr_type (expr);
3604 tree temp;
3605 gimple assign;
3606 pre_expr newe;
3607 gimple_stmt_iterator gsi;
e4b17023 3608
5ce9237c
JM
3609 gcc_assert (edoubleprime->kind == CONSTANT
3610 || edoubleprime->kind == NAME);
e4b17023 3611
5ce9237c
JM
3612 if (!pretemp || TREE_TYPE (pretemp) != exprtype)
3613 {
3614 pretemp = create_tmp_reg (exprtype, "pretmp");
3615 add_referenced_var (pretemp);
e4b17023 3616 }
5ce9237c
JM
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);
e4b17023
JM
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
3648static bool
3649do_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 {
5ce9237c
JM
3658 if (expr->kind == NARY
3659 || expr->kind == REFERENCE)
e4b17023
JM
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
3738static bool
3739insert_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)