1 /* Full and partial redundancy elimination and code hoisting on SSA GIMPLE.
2 Copyright (C) 2001-2022 Free Software Foundation, Inc.
3 Contributed by Daniel Berlin <dan@dberlin.org> and Steven Bosscher
4 <stevenb@suse.de>
5
6 This file is part of GCC.
7
8 GCC is free software; you can redistribute it and/or modify
9 it under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 3, or (at your option)
11 any later version.
12
13 GCC is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 GNU General Public License for more details.
17
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
21
22 #include "config.h"
23 #include "system.h"
24 #include "coretypes.h"
25 #include "backend.h"
26 #include "rtl.h"
27 #include "tree.h"
28 #include "gimple.h"
29 #include "predict.h"
30 #include "alloc-pool.h"
31 #include "tree-pass.h"
32 #include "ssa.h"
33 #include "cgraph.h"
34 #include "gimple-pretty-print.h"
35 #include "fold-const.h"
36 #include "cfganal.h"
37 #include "gimple-fold.h"
38 #include "tree-eh.h"
39 #include "gimplify.h"
40 #include "gimple-iterator.h"
41 #include "tree-cfg.h"
42 #include "tree-into-ssa.h"
43 #include "tree-dfa.h"
44 #include "tree-ssa.h"
45 #include "cfgloop.h"
46 #include "tree-ssa-sccvn.h"
47 #include "tree-scalar-evolution.h"
48 #include "dbgcnt.h"
49 #include "domwalk.h"
50 #include "tree-ssa-propagate.h"
51 #include "tree-ssa-dce.h"
52 #include "tree-cfgcleanup.h"
53 #include "alias.h"
54 #include "gimple-range.h"
55
56 /* Even though this file is called tree-ssa-pre.cc, we actually
57 implement a bit more than just PRE here. All of them piggy-back
58 on GVN which is implemented in tree-ssa-sccvn.cc.
59
60 1. Full Redundancy Elimination (FRE)
61 This is the elimination phase of GVN.
62
63 2. Partial Redundancy Elimination (PRE)
64 This is adds computation of AVAIL_OUT and ANTIC_IN and
65 doing expression insertion to form GVN-PRE.
66
67 3. Code hoisting
68 This optimization uses the ANTIC_IN sets computed for PRE
69 to move expressions further up than PRE would do, to make
70 multiple computations of the same value fully redundant.
71 This pass is explained below (after the explanation of the
72 basic algorithm for PRE).
73 */
74
75 /* TODO:
76
77 1. Avail sets can be shared by making an avail_find_leader that
78 walks up the dominator tree and looks in those avail sets.
79 This might affect code optimality, it's unclear right now.
80 Currently the AVAIL_OUT sets are the remaining quadraticness in
81 memory of GVN-PRE.
82 2. Strength reduction can be performed by anticipating expressions
83 we can repair later on.
84 3. We can do back-substitution or smarter value numbering to catch
85 commutative expressions split up over multiple statements.
86 */
87
88 /* For ease of terminology, "expression node" in the below refers to
89 every expression node but GIMPLE_ASSIGN, because GIMPLE_ASSIGNs
90 represent the actual statement containing the expressions we care about,
91 and we cache the value number by putting it in the expression. */
92
93 /* Basic algorithm for Partial Redundancy Elimination:
94
95 First we walk the statements to generate the AVAIL sets, the
96 EXP_GEN sets, and the tmp_gen sets. EXP_GEN sets represent the
97 generation of values/expressions by a given block. We use them
98 when computing the ANTIC sets. The AVAIL sets consist of
99 SSA_NAME's that represent values, so we know what values are
100 available in what blocks. AVAIL is a forward dataflow problem. In
101 SSA, values are never killed, so we don't need a kill set, or a
102 fixpoint iteration, in order to calculate the AVAIL sets. In
103 traditional parlance, AVAIL sets tell us the downsafety of the
104 expressions/values.
105
106 Next, we generate the ANTIC sets. These sets represent the
107 anticipatable expressions. ANTIC is a backwards dataflow
108 problem. An expression is anticipatable in a given block if it could
109 be generated in that block. This means that if we had to perform
110 an insertion in that block, of the value of that expression, we
111 could. Calculating the ANTIC sets requires phi translation of
112 expressions, because the flow goes backwards through phis. We must
113 iterate to a fixpoint of the ANTIC sets, because we have a kill
114 set. Even in SSA form, values are not live over the entire
115 function, only from their definition point onwards. So we have to
116 remove values from the ANTIC set once we go past the definition
117 point of the leaders that make them up.
118 compute_antic/compute_antic_aux performs this computation.
119
120 Third, we perform insertions to make partially redundant
121 expressions fully redundant.
122
123 An expression is partially redundant (excluding partial
124 anticipation) if:
125
126 1. It is AVAIL in some, but not all, of the predecessors of a
127 given block.
128 2. It is ANTIC in all the predecessors.
129
130 In order to make it fully redundant, we insert the expression into
131 the predecessors where it is not available, but is ANTIC.
132
133 When optimizing for size, we only eliminate the partial redundancy
134 if we need to insert in only one predecessor. This avoids almost
135 completely the code size increase that PRE usually causes.
136
137 For the partial anticipation case, we only perform insertion if it
138 is partially anticipated in some block, and fully available in all
139 of the predecessors.
140
141 do_pre_regular_insertion/do_pre_partial_partial_insertion
142 performs these steps, driven by insert/insert_aux.
143
144 Fourth, we eliminate fully redundant expressions.
145 This is a simple statement walk that replaces redundant
146 calculations with the now available values. */
147
148 /* Basic algorithm for Code Hoisting:
149
150 Code hoisting is: Moving value computations up in the control flow
151 graph to make multiple copies redundant. Typically this is a size
152 optimization, but there are cases where it also is helpful for speed.
153
154 A simple code hoisting algorithm is implemented that piggy-backs on
155 the PRE infrastructure. For code hoisting, we have to know ANTIC_OUT
156 which is effectively ANTIC_IN - AVAIL_OUT. The latter two have to be
157 computed for PRE, and we can use them to perform a limited version of
158 code hoisting, too.
159
160 For the purpose of this implementation, a value is hoistable to a basic
161 block B if the following properties are met:
162
163 1. The value is in ANTIC_IN(B) -- the value will be computed on all
164 paths from B to function exit and it can be computed in B);
165
166 2. The value is not in AVAIL_OUT(B) -- there would be no need to
167 compute the value again and make it available twice;
168
169 3. All successors of B are dominated by B -- makes sure that inserting
170 a computation of the value in B will make the remaining
171 computations fully redundant;
172
173 4. At least one successor has the value in AVAIL_OUT -- to avoid
174 hoisting values up too far;
175
176 5. There are at least two successors of B -- hoisting in straight
177 line code is pointless.
178
179 The third condition is not strictly necessary, but it would complicate
180 the hoisting pass a lot. In fact, I don't know of any code hoisting
181 algorithm that does not have this requirement. Fortunately, experiments
182 have show that most candidate hoistable values are in regions that meet
183 this condition (e.g. diamond-shape regions).
184
185 The forth condition is necessary to avoid hoisting things up too far
186 away from the uses of the value. Nothing else limits the algorithm
187 from hoisting everything up as far as ANTIC_IN allows. Experiments
188 with SPEC and CSiBE have shown that hoisting up too far results in more
189 spilling, less benefits for code size, and worse benchmark scores.
190 Fortunately, in practice most of the interesting hoisting opportunities
191 are caught despite this limitation.
192
193 For hoistable values that meet all conditions, expressions are inserted
194 to make the calculation of the hoistable value fully redundant. We
195 perform code hoisting insertions after each round of PRE insertions,
196 because code hoisting never exposes new PRE opportunities, but PRE can
197 create new code hoisting opportunities.
198
199 The code hoisting algorithm is implemented in do_hoist_insert, driven
200 by insert/insert_aux. */
201
202 /* Representations of value numbers:
203
204 Value numbers are represented by a representative SSA_NAME. We
205 will create fake SSA_NAME's in situations where we need a
206 representative but do not have one (because it is a complex
207 expression). In order to facilitate storing the value numbers in
208 bitmaps, and keep the number of wasted SSA_NAME's down, we also
209 associate a value_id with each value number, and create full blown
210 ssa_name's only where we actually need them (IE in operands of
211 existing expressions).
212
213 Theoretically you could replace all the value_id's with
214 SSA_NAME_VERSION, but this would allocate a large number of
215 SSA_NAME's (which are each > 30 bytes) just to get a 4 byte number.
216 It would also require an additional indirection at each point we
217 use the value id. */
218
219 /* Representation of expressions on value numbers:
220
221 Expressions consisting of value numbers are represented the same
222 way as our VN internally represents them, with an additional
223 "pre_expr" wrapping around them in order to facilitate storing all
224 of the expressions in the same sets. */
225
226 /* Representation of sets:
227
228 The dataflow sets do not need to be sorted in any particular order
229 for the majority of their lifetime, are simply represented as two
230 bitmaps, one that keeps track of values present in the set, and one
231 that keeps track of expressions present in the set.
232
233 When we need them in topological order, we produce it on demand by
234 transforming the bitmap into an array and sorting it into topo
235 order. */
236
237 /* Type of expression, used to know which member of the PRE_EXPR union
238 is valid. */
239
240 enum pre_expr_kind
241 {
242 NAME,
243 NARY,
244 REFERENCE,
245 CONSTANT
246 };
247
248 union pre_expr_union
249 {
250 tree name;
251 tree constant;
252 vn_nary_op_t nary;
253 vn_reference_t reference;
254 };
255
256 typedef struct pre_expr_d : nofree_ptr_hash <pre_expr_d>
257 {
258 enum pre_expr_kind kind;
259 unsigned int id;
260 unsigned value_id;
261 location_t loc;
262 pre_expr_union u;
263
264 /* hash_table support. */
265 static inline hashval_t hash (const pre_expr_d *);
266 static inline int equal (const pre_expr_d *, const pre_expr_d *);
267 } *pre_expr;
268
269 #define PRE_EXPR_NAME(e) (e)->u.name
270 #define PRE_EXPR_NARY(e) (e)->u.nary
271 #define PRE_EXPR_REFERENCE(e) (e)->u.reference
272 #define PRE_EXPR_CONSTANT(e) (e)->u.constant
273
274 /* Compare E1 and E1 for equality. */
275
276 inline int
equal(const pre_expr_d * e1,const pre_expr_d * e2)277 pre_expr_d::equal (const pre_expr_d *e1, const pre_expr_d *e2)
278 {
279 if (e1->kind != e2->kind)
280 return false;
281
282 switch (e1->kind)
283 {
284 case CONSTANT:
285 return vn_constant_eq_with_type (PRE_EXPR_CONSTANT (e1),
286 PRE_EXPR_CONSTANT (e2));
287 case NAME:
288 return PRE_EXPR_NAME (e1) == PRE_EXPR_NAME (e2);
289 case NARY:
290 return vn_nary_op_eq (PRE_EXPR_NARY (e1), PRE_EXPR_NARY (e2));
291 case REFERENCE:
292 return vn_reference_eq (PRE_EXPR_REFERENCE (e1),
293 PRE_EXPR_REFERENCE (e2));
294 default:
295 gcc_unreachable ();
296 }
297 }
298
299 /* Hash E. */
300
301 inline hashval_t
hash(const pre_expr_d * e)302 pre_expr_d::hash (const pre_expr_d *e)
303 {
304 switch (e->kind)
305 {
306 case CONSTANT:
307 return vn_hash_constant_with_type (PRE_EXPR_CONSTANT (e));
308 case NAME:
309 return SSA_NAME_VERSION (PRE_EXPR_NAME (e));
310 case NARY:
311 return PRE_EXPR_NARY (e)->hashcode;
312 case REFERENCE:
313 return PRE_EXPR_REFERENCE (e)->hashcode;
314 default:
315 gcc_unreachable ();
316 }
317 }
318
319 /* Next global expression id number. */
320 static unsigned int next_expression_id;
321
322 /* Mapping from expression to id number we can use in bitmap sets. */
323 static vec<pre_expr> expressions;
324 static hash_table<pre_expr_d> *expression_to_id;
325 static vec<unsigned> name_to_id;
326 static obstack pre_expr_obstack;
327
328 /* Allocate an expression id for EXPR. */
329
330 static inline unsigned int
alloc_expression_id(pre_expr expr)331 alloc_expression_id (pre_expr expr)
332 {
333 struct pre_expr_d **slot;
334 /* Make sure we won't overflow. */
335 gcc_assert (next_expression_id + 1 > next_expression_id);
336 expr->id = next_expression_id++;
337 expressions.safe_push (expr);
338 if (expr->kind == NAME)
339 {
340 unsigned version = SSA_NAME_VERSION (PRE_EXPR_NAME (expr));
341 /* vec::safe_grow_cleared allocates no headroom. Avoid frequent
342 re-allocations by using vec::reserve upfront. */
343 unsigned old_len = name_to_id.length ();
344 name_to_id.reserve (num_ssa_names - old_len);
345 name_to_id.quick_grow_cleared (num_ssa_names);
346 gcc_assert (name_to_id[version] == 0);
347 name_to_id[version] = expr->id;
348 }
349 else
350 {
351 slot = expression_to_id->find_slot (expr, INSERT);
352 gcc_assert (!*slot);
353 *slot = expr;
354 }
355 return next_expression_id - 1;
356 }
357
358 /* Return the expression id for tree EXPR. */
359
360 static inline unsigned int
get_expression_id(const pre_expr expr)361 get_expression_id (const pre_expr expr)
362 {
363 return expr->id;
364 }
365
366 static inline unsigned int
lookup_expression_id(const pre_expr expr)367 lookup_expression_id (const pre_expr expr)
368 {
369 struct pre_expr_d **slot;
370
371 if (expr->kind == NAME)
372 {
373 unsigned version = SSA_NAME_VERSION (PRE_EXPR_NAME (expr));
374 if (name_to_id.length () <= version)
375 return 0;
376 return name_to_id[version];
377 }
378 else
379 {
380 slot = expression_to_id->find_slot (expr, NO_INSERT);
381 if (!slot)
382 return 0;
383 return ((pre_expr)*slot)->id;
384 }
385 }
386
387 /* Return the existing expression id for EXPR, or create one if one
388 does not exist yet. */
389
390 static inline unsigned int
get_or_alloc_expression_id(pre_expr expr)391 get_or_alloc_expression_id (pre_expr expr)
392 {
393 unsigned int id = lookup_expression_id (expr);
394 if (id == 0)
395 return alloc_expression_id (expr);
396 return expr->id = id;
397 }
398
399 /* Return the expression that has expression id ID */
400
401 static inline pre_expr
expression_for_id(unsigned int id)402 expression_for_id (unsigned int id)
403 {
404 return expressions[id];
405 }
406
407 static object_allocator<pre_expr_d> pre_expr_pool ("pre_expr nodes");
408
409 /* Given an SSA_NAME NAME, get or create a pre_expr to represent it. */
410
411 static pre_expr
get_or_alloc_expr_for_name(tree name)412 get_or_alloc_expr_for_name (tree name)
413 {
414 struct pre_expr_d expr;
415 pre_expr result;
416 unsigned int result_id;
417
418 expr.kind = NAME;
419 expr.id = 0;
420 PRE_EXPR_NAME (&expr) = name;
421 result_id = lookup_expression_id (&expr);
422 if (result_id != 0)
423 return expression_for_id (result_id);
424
425 result = pre_expr_pool.allocate ();
426 result->kind = NAME;
427 result->loc = UNKNOWN_LOCATION;
428 result->value_id = VN_INFO (name)->value_id;
429 PRE_EXPR_NAME (result) = name;
430 alloc_expression_id (result);
431 return result;
432 }
433
434 /* Given an NARY, get or create a pre_expr to represent it. Assign
435 VALUE_ID to it or allocate a new value-id if it is zero. Record
436 LOC as the original location of the expression. */
437
438 static pre_expr
get_or_alloc_expr_for_nary(vn_nary_op_t nary,unsigned value_id,location_t loc=UNKNOWN_LOCATION)439 get_or_alloc_expr_for_nary (vn_nary_op_t nary, unsigned value_id,
440 location_t loc = UNKNOWN_LOCATION)
441 {
442 struct pre_expr_d expr;
443 pre_expr result;
444 unsigned int result_id;
445
446 gcc_assert (value_id == 0 || !value_id_constant_p (value_id));
447
448 expr.kind = NARY;
449 expr.id = 0;
450 nary->hashcode = vn_nary_op_compute_hash (nary);
451 PRE_EXPR_NARY (&expr) = nary;
452 result_id = lookup_expression_id (&expr);
453 if (result_id != 0)
454 return expression_for_id (result_id);
455
456 result = pre_expr_pool.allocate ();
457 result->kind = NARY;
458 result->loc = loc;
459 result->value_id = value_id ? value_id : get_next_value_id ();
460 PRE_EXPR_NARY (result)
461 = alloc_vn_nary_op_noinit (nary->length, &pre_expr_obstack);
462 memcpy (PRE_EXPR_NARY (result), nary, sizeof_vn_nary_op (nary->length));
463 alloc_expression_id (result);
464 return result;
465 }
466
467 /* Given an REFERENCE, get or create a pre_expr to represent it. */
468
469 static pre_expr
get_or_alloc_expr_for_reference(vn_reference_t reference,location_t loc=UNKNOWN_LOCATION)470 get_or_alloc_expr_for_reference (vn_reference_t reference,
471 location_t loc = UNKNOWN_LOCATION)
472 {
473 struct pre_expr_d expr;
474 pre_expr result;
475 unsigned int result_id;
476
477 expr.kind = REFERENCE;
478 expr.id = 0;
479 PRE_EXPR_REFERENCE (&expr) = reference;
480 result_id = lookup_expression_id (&expr);
481 if (result_id != 0)
482 return expression_for_id (result_id);
483
484 result = pre_expr_pool.allocate ();
485 result->kind = REFERENCE;
486 result->loc = loc;
487 result->value_id = reference->value_id;
488 PRE_EXPR_REFERENCE (result) = reference;
489 alloc_expression_id (result);
490 return result;
491 }
492
493
494 /* An unordered bitmap set. One bitmap tracks values, the other,
495 expressions. */
496 typedef class bitmap_set
497 {
498 public:
499 bitmap_head expressions;
500 bitmap_head values;
501 } *bitmap_set_t;
502
503 #define FOR_EACH_EXPR_ID_IN_SET(set, id, bi) \
504 EXECUTE_IF_SET_IN_BITMAP (&(set)->expressions, 0, (id), (bi))
505
506 #define FOR_EACH_VALUE_ID_IN_SET(set, id, bi) \
507 EXECUTE_IF_SET_IN_BITMAP (&(set)->values, 0, (id), (bi))
508
509 /* Mapping from value id to expressions with that value_id. */
510 static vec<bitmap> value_expressions;
511 /* We just record a single expression for each constant value,
512 one of kind CONSTANT. */
513 static vec<pre_expr> constant_value_expressions;
514
515
516 /* This structure is used to keep track of statistics on what
517 optimization PRE was able to perform. */
518 static struct
519 {
520 /* The number of new expressions/temporaries generated by PRE. */
521 int insertions;
522
523 /* The number of inserts found due to partial anticipation */
524 int pa_insert;
525
526 /* The number of inserts made for code hoisting. */
527 int hoist_insert;
528
529 /* The number of new PHI nodes added by PRE. */
530 int phis;
531 } pre_stats;
532
533 static bool do_partial_partial;
534 static pre_expr bitmap_find_leader (bitmap_set_t, unsigned int);
535 static void bitmap_value_insert_into_set (bitmap_set_t, pre_expr);
536 static bool bitmap_value_replace_in_set (bitmap_set_t, pre_expr);
537 static void bitmap_set_copy (bitmap_set_t, bitmap_set_t);
538 static bool bitmap_set_contains_value (bitmap_set_t, unsigned int);
539 static void bitmap_insert_into_set (bitmap_set_t, pre_expr);
540 static bitmap_set_t bitmap_set_new (void);
541 static tree create_expression_by_pieces (basic_block, pre_expr, gimple_seq *,
542 tree);
543 static tree find_or_generate_expression (basic_block, tree, gimple_seq *);
544 static unsigned int get_expr_value_id (pre_expr);
545
546 /* We can add and remove elements and entries to and from sets
547 and hash tables, so we use alloc pools for them. */
548
549 static object_allocator<bitmap_set> bitmap_set_pool ("Bitmap sets");
550 static bitmap_obstack grand_bitmap_obstack;
551
552 /* A three tuple {e, pred, v} used to cache phi translations in the
553 phi_translate_table. */
554
555 typedef struct expr_pred_trans_d : public typed_noop_remove <expr_pred_trans_d>
556 {
557 typedef expr_pred_trans_d value_type;
558 typedef expr_pred_trans_d compare_type;
559
560 /* The expression ID. */
561 unsigned e;
562
563 /* The value expression ID that resulted from the translation. */
564 unsigned v;
565
566 /* hash_table support. */
567 static inline void mark_empty (expr_pred_trans_d &);
568 static inline bool is_empty (const expr_pred_trans_d &);
569 static inline void mark_deleted (expr_pred_trans_d &);
570 static inline bool is_deleted (const expr_pred_trans_d &);
571 static const bool empty_zero_p = true;
572 static inline hashval_t hash (const expr_pred_trans_d &);
573 static inline int equal (const expr_pred_trans_d &, const expr_pred_trans_d &);
574 } *expr_pred_trans_t;
575 typedef const struct expr_pred_trans_d *const_expr_pred_trans_t;
576
577 inline bool
is_empty(const expr_pred_trans_d & e)578 expr_pred_trans_d::is_empty (const expr_pred_trans_d &e)
579 {
580 return e.e == 0;
581 }
582
583 inline bool
is_deleted(const expr_pred_trans_d & e)584 expr_pred_trans_d::is_deleted (const expr_pred_trans_d &e)
585 {
586 return e.e == -1u;
587 }
588
589 inline void
mark_empty(expr_pred_trans_d & e)590 expr_pred_trans_d::mark_empty (expr_pred_trans_d &e)
591 {
592 e.e = 0;
593 }
594
595 inline void
mark_deleted(expr_pred_trans_d & e)596 expr_pred_trans_d::mark_deleted (expr_pred_trans_d &e)
597 {
598 e.e = -1u;
599 }
600
601 inline hashval_t
hash(const expr_pred_trans_d & e)602 expr_pred_trans_d::hash (const expr_pred_trans_d &e)
603 {
604 return e.e;
605 }
606
607 inline int
equal(const expr_pred_trans_d & ve1,const expr_pred_trans_d & ve2)608 expr_pred_trans_d::equal (const expr_pred_trans_d &ve1,
609 const expr_pred_trans_d &ve2)
610 {
611 return ve1.e == ve2.e;
612 }
613
614 /* Sets that we need to keep track of. */
615 typedef struct bb_bitmap_sets
616 {
617 /* The EXP_GEN set, which represents expressions/values generated in
618 a basic block. */
619 bitmap_set_t exp_gen;
620
621 /* The PHI_GEN set, which represents PHI results generated in a
622 basic block. */
623 bitmap_set_t phi_gen;
624
625 /* The TMP_GEN set, which represents results/temporaries generated
626 in a basic block. IE the LHS of an expression. */
627 bitmap_set_t tmp_gen;
628
629 /* The AVAIL_OUT set, which represents which values are available in
630 a given basic block. */
631 bitmap_set_t avail_out;
632
633 /* The ANTIC_IN set, which represents which values are anticipatable
634 in a given basic block. */
635 bitmap_set_t antic_in;
636
637 /* The PA_IN set, which represents which values are
638 partially anticipatable in a given basic block. */
639 bitmap_set_t pa_in;
640
641 /* The NEW_SETS set, which is used during insertion to augment the
642 AVAIL_OUT set of blocks with the new insertions performed during
643 the current iteration. */
644 bitmap_set_t new_sets;
645
646 /* A cache for value_dies_in_block_x. */
647 bitmap expr_dies;
648
649 /* The live virtual operand on successor edges. */
650 tree vop_on_exit;
651
652 /* PHI translate cache for the single successor edge. */
653 hash_table<expr_pred_trans_d> *phi_translate_table;
654
655 /* True if we have visited this block during ANTIC calculation. */
656 unsigned int visited : 1;
657
658 /* True when the block contains a call that might not return. */
659 unsigned int contains_may_not_return_call : 1;
660 } *bb_value_sets_t;
661
662 #define EXP_GEN(BB) ((bb_value_sets_t) ((BB)->aux))->exp_gen
663 #define PHI_GEN(BB) ((bb_value_sets_t) ((BB)->aux))->phi_gen
664 #define TMP_GEN(BB) ((bb_value_sets_t) ((BB)->aux))->tmp_gen
665 #define AVAIL_OUT(BB) ((bb_value_sets_t) ((BB)->aux))->avail_out
666 #define ANTIC_IN(BB) ((bb_value_sets_t) ((BB)->aux))->antic_in
667 #define PA_IN(BB) ((bb_value_sets_t) ((BB)->aux))->pa_in
668 #define NEW_SETS(BB) ((bb_value_sets_t) ((BB)->aux))->new_sets
669 #define EXPR_DIES(BB) ((bb_value_sets_t) ((BB)->aux))->expr_dies
670 #define PHI_TRANS_TABLE(BB) ((bb_value_sets_t) ((BB)->aux))->phi_translate_table
671 #define BB_VISITED(BB) ((bb_value_sets_t) ((BB)->aux))->visited
672 #define BB_MAY_NOTRETURN(BB) ((bb_value_sets_t) ((BB)->aux))->contains_may_not_return_call
673 #define BB_LIVE_VOP_ON_EXIT(BB) ((bb_value_sets_t) ((BB)->aux))->vop_on_exit
674
675
676 /* Add the tuple mapping from {expression E, basic block PRED} to
677 the phi translation table and return whether it pre-existed. */
678
679 static inline bool
phi_trans_add(expr_pred_trans_t * entry,pre_expr e,basic_block pred)680 phi_trans_add (expr_pred_trans_t *entry, pre_expr e, basic_block pred)
681 {
682 if (!PHI_TRANS_TABLE (pred))
683 PHI_TRANS_TABLE (pred) = new hash_table<expr_pred_trans_d> (11);
684
685 expr_pred_trans_t slot;
686 expr_pred_trans_d tem;
687 unsigned id = get_expression_id (e);
688 tem.e = id;
689 slot = PHI_TRANS_TABLE (pred)->find_slot_with_hash (tem, id, INSERT);
690 if (slot->e)
691 {
692 *entry = slot;
693 return true;
694 }
695
696 *entry = slot;
697 slot->e = id;
698 return false;
699 }
700
701
702 /* Add expression E to the expression set of value id V. */
703
704 static void
add_to_value(unsigned int v,pre_expr e)705 add_to_value (unsigned int v, pre_expr e)
706 {
707 gcc_checking_assert (get_expr_value_id (e) == v);
708
709 if (value_id_constant_p (v))
710 {
711 if (e->kind != CONSTANT)
712 return;
713
714 if (-v >= constant_value_expressions.length ())
715 constant_value_expressions.safe_grow_cleared (-v + 1);
716
717 pre_expr leader = constant_value_expressions[-v];
718 if (!leader)
719 constant_value_expressions[-v] = e;
720 }
721 else
722 {
723 if (v >= value_expressions.length ())
724 value_expressions.safe_grow_cleared (v + 1);
725
726 bitmap set = value_expressions[v];
727 if (!set)
728 {
729 set = BITMAP_ALLOC (&grand_bitmap_obstack);
730 value_expressions[v] = set;
731 }
732 bitmap_set_bit (set, get_or_alloc_expression_id (e));
733 }
734 }
735
736 /* Create a new bitmap set and return it. */
737
738 static bitmap_set_t
bitmap_set_new(void)739 bitmap_set_new (void)
740 {
741 bitmap_set_t ret = bitmap_set_pool.allocate ();
742 bitmap_initialize (&ret->expressions, &grand_bitmap_obstack);
743 bitmap_initialize (&ret->values, &grand_bitmap_obstack);
744 return ret;
745 }
746
747 /* Return the value id for a PRE expression EXPR. */
748
749 static unsigned int
get_expr_value_id(pre_expr expr)750 get_expr_value_id (pre_expr expr)
751 {
752 /* ??? We cannot assert that expr has a value-id (it can be 0), because
753 we assign value-ids only to expressions that have a result
754 in set_hashtable_value_ids. */
755 return expr->value_id;
756 }
757
758 /* Return a VN valnum (SSA name or constant) for the PRE value-id VAL. */
759
760 static tree
vn_valnum_from_value_id(unsigned int val)761 vn_valnum_from_value_id (unsigned int val)
762 {
763 if (value_id_constant_p (val))
764 {
765 pre_expr vexpr = constant_value_expressions[-val];
766 if (vexpr)
767 return PRE_EXPR_CONSTANT (vexpr);
768 return NULL_TREE;
769 }
770
771 bitmap exprset = value_expressions[val];
772 bitmap_iterator bi;
773 unsigned int i;
774 EXECUTE_IF_SET_IN_BITMAP (exprset, 0, i, bi)
775 {
776 pre_expr vexpr = expression_for_id (i);
777 if (vexpr->kind == NAME)
778 return VN_INFO (PRE_EXPR_NAME (vexpr))->valnum;
779 }
780 return NULL_TREE;
781 }
782
783 /* Insert an expression EXPR into a bitmapped set. */
784
785 static void
bitmap_insert_into_set(bitmap_set_t set,pre_expr expr)786 bitmap_insert_into_set (bitmap_set_t set, pre_expr expr)
787 {
788 unsigned int val = get_expr_value_id (expr);
789 if (! value_id_constant_p (val))
790 {
791 /* Note this is the only function causing multiple expressions
792 for the same value to appear in a set. This is needed for
793 TMP_GEN, PHI_GEN and NEW_SETs. */
794 bitmap_set_bit (&set->values, val);
795 bitmap_set_bit (&set->expressions, get_or_alloc_expression_id (expr));
796 }
797 }
798
799 /* Copy a bitmapped set ORIG, into bitmapped set DEST. */
800
801 static void
bitmap_set_copy(bitmap_set_t dest,bitmap_set_t orig)802 bitmap_set_copy (bitmap_set_t dest, bitmap_set_t orig)
803 {
804 bitmap_copy (&dest->expressions, &orig->expressions);
805 bitmap_copy (&dest->values, &orig->values);
806 }
807
808
809 /* Free memory used up by SET. */
810 static void
bitmap_set_free(bitmap_set_t set)811 bitmap_set_free (bitmap_set_t set)
812 {
813 bitmap_clear (&set->expressions);
814 bitmap_clear (&set->values);
815 }
816
817 static void
818 pre_expr_DFS (pre_expr expr, bitmap_set_t set, bitmap val_visited,
819 vec<pre_expr> &post);
820
821 /* DFS walk leaders of VAL to their operands with leaders in SET, collecting
822 expressions in SET in postorder into POST. */
823
824 static void
pre_expr_DFS(unsigned val,bitmap_set_t set,bitmap val_visited,vec<pre_expr> & post)825 pre_expr_DFS (unsigned val, bitmap_set_t set, bitmap val_visited,
826 vec<pre_expr> &post)
827 {
828 unsigned int i;
829 bitmap_iterator bi;
830
831 /* Iterate over all leaders and DFS recurse. Borrowed from
832 bitmap_find_leader. */
833 bitmap exprset = value_expressions[val];
834 if (!exprset->first->next)
835 {
836 EXECUTE_IF_SET_IN_BITMAP (exprset, 0, i, bi)
837 if (bitmap_bit_p (&set->expressions, i))
838 pre_expr_DFS (expression_for_id (i), set, val_visited, post);
839 return;
840 }
841
842 EXECUTE_IF_AND_IN_BITMAP (exprset, &set->expressions, 0, i, bi)
843 pre_expr_DFS (expression_for_id (i), set, val_visited, post);
844 }
845
846 /* DFS walk EXPR to its operands with leaders in SET, collecting
847 expressions in SET in postorder into POST. */
848
849 static void
pre_expr_DFS(pre_expr expr,bitmap_set_t set,bitmap val_visited,vec<pre_expr> & post)850 pre_expr_DFS (pre_expr expr, bitmap_set_t set, bitmap val_visited,
851 vec<pre_expr> &post)
852 {
853 switch (expr->kind)
854 {
855 case NARY:
856 {
857 vn_nary_op_t nary = PRE_EXPR_NARY (expr);
858 for (unsigned i = 0; i < nary->length; i++)
859 {
860 if (TREE_CODE (nary->op[i]) != SSA_NAME)
861 continue;
862 unsigned int op_val_id = VN_INFO (nary->op[i])->value_id;
863 /* If we already found a leader for the value we've
864 recursed already. Avoid the costly bitmap_find_leader. */
865 if (bitmap_bit_p (&set->values, op_val_id)
866 && bitmap_set_bit (val_visited, op_val_id))
867 pre_expr_DFS (op_val_id, set, val_visited, post);
868 }
869 break;
870 }
871 case REFERENCE:
872 {
873 vn_reference_t ref = PRE_EXPR_REFERENCE (expr);
874 vec<vn_reference_op_s> operands = ref->operands;
875 vn_reference_op_t operand;
876 for (unsigned i = 0; operands.iterate (i, &operand); i++)
877 {
878 tree op[3];
879 op[0] = operand->op0;
880 op[1] = operand->op1;
881 op[2] = operand->op2;
882 for (unsigned n = 0; n < 3; ++n)
883 {
884 if (!op[n] || TREE_CODE (op[n]) != SSA_NAME)
885 continue;
886 unsigned op_val_id = VN_INFO (op[n])->value_id;
887 if (bitmap_bit_p (&set->values, op_val_id)
888 && bitmap_set_bit (val_visited, op_val_id))
889 pre_expr_DFS (op_val_id, set, val_visited, post);
890 }
891 }
892 break;
893 }
894 default:;
895 }
896 post.quick_push (expr);
897 }
898
899 /* Generate an topological-ordered array of bitmap set SET. */
900
901 static vec<pre_expr>
sorted_array_from_bitmap_set(bitmap_set_t set)902 sorted_array_from_bitmap_set (bitmap_set_t set)
903 {
904 unsigned int i;
905 bitmap_iterator bi;
906 vec<pre_expr> result;
907
908 /* Pre-allocate enough space for the array. */
909 result.create (bitmap_count_bits (&set->expressions));
910
911 auto_bitmap val_visited (&grand_bitmap_obstack);
912 bitmap_tree_view (val_visited);
913 FOR_EACH_VALUE_ID_IN_SET (set, i, bi)
914 if (bitmap_set_bit (val_visited, i))
915 pre_expr_DFS (i, set, val_visited, result);
916
917 return result;
918 }
919
920 /* Subtract all expressions contained in ORIG from DEST. */
921
922 static bitmap_set_t
bitmap_set_subtract_expressions(bitmap_set_t dest,bitmap_set_t orig)923 bitmap_set_subtract_expressions (bitmap_set_t dest, bitmap_set_t orig)
924 {
925 bitmap_set_t result = bitmap_set_new ();
926 bitmap_iterator bi;
927 unsigned int i;
928
929 bitmap_and_compl (&result->expressions, &dest->expressions,
930 &orig->expressions);
931
932 FOR_EACH_EXPR_ID_IN_SET (result, i, bi)
933 {
934 pre_expr expr = expression_for_id (i);
935 unsigned int value_id = get_expr_value_id (expr);
936 bitmap_set_bit (&result->values, value_id);
937 }
938
939 return result;
940 }
941
942 /* Subtract all values in bitmap set B from bitmap set A. */
943
944 static void
bitmap_set_subtract_values(bitmap_set_t a,bitmap_set_t b)945 bitmap_set_subtract_values (bitmap_set_t a, bitmap_set_t b)
946 {
947 unsigned int i;
948 bitmap_iterator bi;
949 unsigned to_remove = -1U;
950 bitmap_and_compl_into (&a->values, &b->values);
951 FOR_EACH_EXPR_ID_IN_SET (a, i, bi)
952 {
953 if (to_remove != -1U)
954 {
955 bitmap_clear_bit (&a->expressions, to_remove);
956 to_remove = -1U;
957 }
958 pre_expr expr = expression_for_id (i);
959 if (! bitmap_bit_p (&a->values, get_expr_value_id (expr)))
960 to_remove = i;
961 }
962 if (to_remove != -1U)
963 bitmap_clear_bit (&a->expressions, to_remove);
964 }
965
966
967 /* Return true if bitmapped set SET contains the value VALUE_ID. */
968
969 static bool
bitmap_set_contains_value(bitmap_set_t set,unsigned int value_id)970 bitmap_set_contains_value (bitmap_set_t set, unsigned int value_id)
971 {
972 if (value_id_constant_p (value_id))
973 return true;
974
975 return bitmap_bit_p (&set->values, value_id);
976 }
977
978 /* Return true if two bitmap sets are equal. */
979
980 static bool
bitmap_set_equal(bitmap_set_t a,bitmap_set_t b)981 bitmap_set_equal (bitmap_set_t a, bitmap_set_t b)
982 {
983 return bitmap_equal_p (&a->values, &b->values);
984 }
985
986 /* Replace an instance of EXPR's VALUE with EXPR in SET if it exists,
987 and add it otherwise. Return true if any changes were made. */
988
989 static bool
bitmap_value_replace_in_set(bitmap_set_t set,pre_expr expr)990 bitmap_value_replace_in_set (bitmap_set_t set, pre_expr expr)
991 {
992 unsigned int val = get_expr_value_id (expr);
993 if (value_id_constant_p (val))
994 return false;
995
996 if (bitmap_set_contains_value (set, val))
997 {
998 /* The number of expressions having a given value is usually
999 significantly less than the total number of expressions in SET.
1000 Thus, rather than check, for each expression in SET, whether it
1001 has the value LOOKFOR, we walk the reverse mapping that tells us
1002 what expressions have a given value, and see if any of those
1003 expressions are in our set. For large testcases, this is about
1004 5-10x faster than walking the bitmap. If this is somehow a
1005 significant lose for some cases, we can choose which set to walk
1006 based on the set size. */
1007 unsigned int i;
1008 bitmap_iterator bi;
1009 bitmap exprset = value_expressions[val];
1010 EXECUTE_IF_SET_IN_BITMAP (exprset, 0, i, bi)
1011 {
1012 if (bitmap_clear_bit (&set->expressions, i))
1013 {
1014 bitmap_set_bit (&set->expressions, get_expression_id (expr));
1015 return i != get_expression_id (expr);
1016 }
1017 }
1018 gcc_unreachable ();
1019 }
1020
1021 bitmap_insert_into_set (set, expr);
1022 return true;
1023 }
1024
1025 /* Insert EXPR into SET if EXPR's value is not already present in
1026 SET. */
1027
1028 static void
bitmap_value_insert_into_set(bitmap_set_t set,pre_expr expr)1029 bitmap_value_insert_into_set (bitmap_set_t set, pre_expr expr)
1030 {
1031 unsigned int val = get_expr_value_id (expr);
1032
1033 gcc_checking_assert (expr->id == get_or_alloc_expression_id (expr));
1034
1035 /* Constant values are always considered to be part of the set. */
1036 if (value_id_constant_p (val))
1037 return;
1038
1039 /* If the value membership changed, add the expression. */
1040 if (bitmap_set_bit (&set->values, val))
1041 bitmap_set_bit (&set->expressions, expr->id);
1042 }
1043
1044 /* Print out EXPR to outfile. */
1045
1046 static void
print_pre_expr(FILE * outfile,const pre_expr expr)1047 print_pre_expr (FILE *outfile, const pre_expr expr)
1048 {
1049 if (! expr)
1050 {
1051 fprintf (outfile, "NULL");
1052 return;
1053 }
1054 switch (expr->kind)
1055 {
1056 case CONSTANT:
1057 print_generic_expr (outfile, PRE_EXPR_CONSTANT (expr));
1058 break;
1059 case NAME:
1060 print_generic_expr (outfile, PRE_EXPR_NAME (expr));
1061 break;
1062 case NARY:
1063 {
1064 unsigned int i;
1065 vn_nary_op_t nary = PRE_EXPR_NARY (expr);
1066 fprintf (outfile, "{%s,", get_tree_code_name (nary->opcode));
1067 for (i = 0; i < nary->length; i++)
1068 {
1069 print_generic_expr (outfile, nary->op[i]);
1070 if (i != (unsigned) nary->length - 1)
1071 fprintf (outfile, ",");
1072 }
1073 fprintf (outfile, "}");
1074 }
1075 break;
1076
1077 case REFERENCE:
1078 {
1079 vn_reference_t ref = PRE_EXPR_REFERENCE (expr);
1080 print_vn_reference_ops (outfile, ref->operands);
1081 if (ref->vuse)
1082 {
1083 fprintf (outfile, "@");
1084 print_generic_expr (outfile, ref->vuse);
1085 }
1086 }
1087 break;
1088 }
1089 }
1090 void debug_pre_expr (pre_expr);
1091
1092 /* Like print_pre_expr but always prints to stderr. */
1093 DEBUG_FUNCTION void
debug_pre_expr(pre_expr e)1094 debug_pre_expr (pre_expr e)
1095 {
1096 print_pre_expr (stderr, e);
1097 fprintf (stderr, "\n");
1098 }
1099
1100 /* Print out SET to OUTFILE. */
1101
1102 static void
print_bitmap_set(FILE * outfile,bitmap_set_t set,const char * setname,int blockindex)1103 print_bitmap_set (FILE *outfile, bitmap_set_t set,
1104 const char *setname, int blockindex)
1105 {
1106 fprintf (outfile, "%s[%d] := { ", setname, blockindex);
1107 if (set)
1108 {
1109 bool first = true;
1110 unsigned i;
1111 bitmap_iterator bi;
1112
1113 FOR_EACH_EXPR_ID_IN_SET (set, i, bi)
1114 {
1115 const pre_expr expr = expression_for_id (i);
1116
1117 if (!first)
1118 fprintf (outfile, ", ");
1119 first = false;
1120 print_pre_expr (outfile, expr);
1121
1122 fprintf (outfile, " (%04d)", get_expr_value_id (expr));
1123 }
1124 }
1125 fprintf (outfile, " }\n");
1126 }
1127
1128 void debug_bitmap_set (bitmap_set_t);
1129
1130 DEBUG_FUNCTION void
debug_bitmap_set(bitmap_set_t set)1131 debug_bitmap_set (bitmap_set_t set)
1132 {
1133 print_bitmap_set (stderr, set, "debug", 0);
1134 }
1135
1136 void debug_bitmap_sets_for (basic_block);
1137
1138 DEBUG_FUNCTION void
debug_bitmap_sets_for(basic_block bb)1139 debug_bitmap_sets_for (basic_block bb)
1140 {
1141 print_bitmap_set (stderr, AVAIL_OUT (bb), "avail_out", bb->index);
1142 print_bitmap_set (stderr, EXP_GEN (bb), "exp_gen", bb->index);
1143 print_bitmap_set (stderr, PHI_GEN (bb), "phi_gen", bb->index);
1144 print_bitmap_set (stderr, TMP_GEN (bb), "tmp_gen", bb->index);
1145 print_bitmap_set (stderr, ANTIC_IN (bb), "antic_in", bb->index);
1146 if (do_partial_partial)
1147 print_bitmap_set (stderr, PA_IN (bb), "pa_in", bb->index);
1148 print_bitmap_set (stderr, NEW_SETS (bb), "new_sets", bb->index);
1149 }
1150
1151 /* Print out the expressions that have VAL to OUTFILE. */
1152
1153 static void
print_value_expressions(FILE * outfile,unsigned int val)1154 print_value_expressions (FILE *outfile, unsigned int val)
1155 {
1156 bitmap set = value_expressions[val];
1157 if (set)
1158 {
1159 bitmap_set x;
1160 char s[10];
1161 sprintf (s, "%04d", val);
1162 x.expressions = *set;
1163 print_bitmap_set (outfile, &x, s, 0);
1164 }
1165 }
1166
1167
1168 DEBUG_FUNCTION void
debug_value_expressions(unsigned int val)1169 debug_value_expressions (unsigned int val)
1170 {
1171 print_value_expressions (stderr, val);
1172 }
1173
1174 /* Given a CONSTANT, allocate a new CONSTANT type PRE_EXPR to
1175 represent it. */
1176
1177 static pre_expr
get_or_alloc_expr_for_constant(tree constant)1178 get_or_alloc_expr_for_constant (tree constant)
1179 {
1180 unsigned int result_id;
1181 struct pre_expr_d expr;
1182 pre_expr newexpr;
1183
1184 expr.kind = CONSTANT;
1185 PRE_EXPR_CONSTANT (&expr) = constant;
1186 result_id = lookup_expression_id (&expr);
1187 if (result_id != 0)
1188 return expression_for_id (result_id);
1189
1190 newexpr = pre_expr_pool.allocate ();
1191 newexpr->kind = CONSTANT;
1192 newexpr->loc = UNKNOWN_LOCATION;
1193 PRE_EXPR_CONSTANT (newexpr) = constant;
1194 alloc_expression_id (newexpr);
1195 newexpr->value_id = get_or_alloc_constant_value_id (constant);
1196 add_to_value (newexpr->value_id, newexpr);
1197 return newexpr;
1198 }
1199
1200 /* Return the folded version of T if T, when folded, is a gimple
1201 min_invariant or an SSA name. Otherwise, return T. */
1202
1203 static pre_expr
fully_constant_expression(pre_expr e)1204 fully_constant_expression (pre_expr e)
1205 {
1206 switch (e->kind)
1207 {
1208 case CONSTANT:
1209 return e;
1210 case NARY:
1211 {
1212 vn_nary_op_t nary = PRE_EXPR_NARY (e);
1213 tree res = vn_nary_simplify (nary);
1214 if (!res)
1215 return e;
1216 if (is_gimple_min_invariant (res))
1217 return get_or_alloc_expr_for_constant (res);
1218 if (TREE_CODE (res) == SSA_NAME)
1219 return get_or_alloc_expr_for_name (res);
1220 return e;
1221 }
1222 case REFERENCE:
1223 {
1224 vn_reference_t ref = PRE_EXPR_REFERENCE (e);
1225 tree folded;
1226 if ((folded = fully_constant_vn_reference_p (ref)))
1227 return get_or_alloc_expr_for_constant (folded);
1228 return e;
1229 }
1230 default:
1231 return e;
1232 }
1233 }
1234
1235 /* Translate the VUSE backwards through phi nodes in E->dest, so that
1236 it has the value it would have in E->src. Set *SAME_VALID to true
1237 in case the new vuse doesn't change the value id of the OPERANDS. */
1238
1239 static tree
translate_vuse_through_block(vec<vn_reference_op_s> operands,alias_set_type set,alias_set_type base_set,tree type,tree vuse,edge e,bool * same_valid)1240 translate_vuse_through_block (vec<vn_reference_op_s> operands,
1241 alias_set_type set, alias_set_type base_set,
1242 tree type, tree vuse, edge e, bool *same_valid)
1243 {
1244 basic_block phiblock = e->dest;
1245 gimple *phi = SSA_NAME_DEF_STMT (vuse);
1246 ao_ref ref;
1247
1248 if (same_valid)
1249 *same_valid = true;
1250
1251 /* If value-numbering provided a memory state for this
1252 that dominates PHIBLOCK we can just use that. */
1253 if (gimple_nop_p (phi)
1254 || (gimple_bb (phi) != phiblock
1255 && dominated_by_p (CDI_DOMINATORS, phiblock, gimple_bb (phi))))
1256 return vuse;
1257
1258 /* We have pruned expressions that are killed in PHIBLOCK via
1259 prune_clobbered_mems but we have not rewritten the VUSE to the one
1260 live at the start of the block. If there is no virtual PHI to translate
1261 through return the VUSE live at entry. Otherwise the VUSE to translate
1262 is the def of the virtual PHI node. */
1263 phi = get_virtual_phi (phiblock);
1264 if (!phi)
1265 return BB_LIVE_VOP_ON_EXIT
1266 (get_immediate_dominator (CDI_DOMINATORS, phiblock));
1267
1268 if (same_valid
1269 && ao_ref_init_from_vn_reference (&ref, set, base_set, type, operands))
1270 {
1271 bitmap visited = NULL;
1272 /* Try to find a vuse that dominates this phi node by skipping
1273 non-clobbering statements. */
1274 unsigned int cnt = param_sccvn_max_alias_queries_per_access;
1275 vuse = get_continuation_for_phi (phi, &ref, true,
1276 cnt, &visited, false, NULL, NULL);
1277 if (visited)
1278 BITMAP_FREE (visited);
1279 }
1280 else
1281 vuse = NULL_TREE;
1282 /* If we didn't find any, the value ID can't stay the same. */
1283 if (!vuse && same_valid)
1284 *same_valid = false;
1285
1286 /* ??? We would like to return vuse here as this is the canonical
1287 upmost vdef that this reference is associated with. But during
1288 insertion of the references into the hash tables we only ever
1289 directly insert with their direct gimple_vuse, hence returning
1290 something else would make us not find the other expression. */
1291 return PHI_ARG_DEF (phi, e->dest_idx);
1292 }
1293
1294 /* Like bitmap_find_leader, but checks for the value existing in SET1 *or*
1295 SET2 *or* SET3. This is used to avoid making a set consisting of the union
1296 of PA_IN and ANTIC_IN during insert and phi-translation. */
1297
1298 static inline pre_expr
find_leader_in_sets(unsigned int val,bitmap_set_t set1,bitmap_set_t set2,bitmap_set_t set3=NULL)1299 find_leader_in_sets (unsigned int val, bitmap_set_t set1, bitmap_set_t set2,
1300 bitmap_set_t set3 = NULL)
1301 {
1302 pre_expr result = NULL;
1303
1304 if (set1)
1305 result = bitmap_find_leader (set1, val);
1306 if (!result && set2)
1307 result = bitmap_find_leader (set2, val);
1308 if (!result && set3)
1309 result = bitmap_find_leader (set3, val);
1310 return result;
1311 }
1312
1313 /* Get the tree type for our PRE expression e. */
1314
1315 static tree
get_expr_type(const pre_expr e)1316 get_expr_type (const pre_expr e)
1317 {
1318 switch (e->kind)
1319 {
1320 case NAME:
1321 return TREE_TYPE (PRE_EXPR_NAME (e));
1322 case CONSTANT:
1323 return TREE_TYPE (PRE_EXPR_CONSTANT (e));
1324 case REFERENCE:
1325 return PRE_EXPR_REFERENCE (e)->type;
1326 case NARY:
1327 return PRE_EXPR_NARY (e)->type;
1328 }
1329 gcc_unreachable ();
1330 }
1331
1332 /* Get a representative SSA_NAME for a given expression that is available in B.
1333 Since all of our sub-expressions are treated as values, we require
1334 them to be SSA_NAME's for simplicity.
1335 Prior versions of GVNPRE used to use "value handles" here, so that
1336 an expression would be VH.11 + VH.10 instead of d_3 + e_6. In
1337 either case, the operands are really values (IE we do not expect
1338 them to be usable without finding leaders). */
1339
1340 static tree
get_representative_for(const pre_expr e,basic_block b=NULL)1341 get_representative_for (const pre_expr e, basic_block b = NULL)
1342 {
1343 tree name, valnum = NULL_TREE;
1344 unsigned int value_id = get_expr_value_id (e);
1345
1346 switch (e->kind)
1347 {
1348 case NAME:
1349 return PRE_EXPR_NAME (e);
1350 case CONSTANT:
1351 return PRE_EXPR_CONSTANT (e);
1352 case NARY:
1353 case REFERENCE:
1354 {
1355 /* Go through all of the expressions representing this value
1356 and pick out an SSA_NAME. */
1357 unsigned int i;
1358 bitmap_iterator bi;
1359 bitmap exprs = value_expressions[value_id];
1360 EXECUTE_IF_SET_IN_BITMAP (exprs, 0, i, bi)
1361 {
1362 pre_expr rep = expression_for_id (i);
1363 if (rep->kind == NAME)
1364 {
1365 tree name = PRE_EXPR_NAME (rep);
1366 valnum = VN_INFO (name)->valnum;
1367 gimple *def = SSA_NAME_DEF_STMT (name);
1368 /* We have to return either a new representative or one
1369 that can be used for expression simplification and thus
1370 is available in B. */
1371 if (! b
1372 || gimple_nop_p (def)
1373 || dominated_by_p (CDI_DOMINATORS, b, gimple_bb (def)))
1374 return name;
1375 }
1376 else if (rep->kind == CONSTANT)
1377 return PRE_EXPR_CONSTANT (rep);
1378 }
1379 }
1380 break;
1381 }
1382
1383 /* If we reached here we couldn't find an SSA_NAME. This can
1384 happen when we've discovered a value that has never appeared in
1385 the program as set to an SSA_NAME, as the result of phi translation.
1386 Create one here.
1387 ??? We should be able to re-use this when we insert the statement
1388 to compute it. */
1389 name = make_temp_ssa_name (get_expr_type (e), gimple_build_nop (), "pretmp");
1390 vn_ssa_aux_t vn_info = VN_INFO (name);
1391 vn_info->value_id = value_id;
1392 vn_info->valnum = valnum ? valnum : name;
1393 vn_info->visited = true;
1394 /* ??? For now mark this SSA name for release by VN. */
1395 vn_info->needs_insertion = true;
1396 add_to_value (value_id, get_or_alloc_expr_for_name (name));
1397 if (dump_file && (dump_flags & TDF_DETAILS))
1398 {
1399 fprintf (dump_file, "Created SSA_NAME representative ");
1400 print_generic_expr (dump_file, name);
1401 fprintf (dump_file, " for expression:");
1402 print_pre_expr (dump_file, e);
1403 fprintf (dump_file, " (%04d)\n", value_id);
1404 }
1405
1406 return name;
1407 }
1408
1409
1410 static pre_expr
1411 phi_translate (bitmap_set_t, pre_expr, bitmap_set_t, bitmap_set_t, edge);
1412
1413 /* Translate EXPR using phis in PHIBLOCK, so that it has the values of
1414 the phis in PRED. Return NULL if we can't find a leader for each part
1415 of the translated expression. */
1416
1417 static pre_expr
phi_translate_1(bitmap_set_t dest,pre_expr expr,bitmap_set_t set1,bitmap_set_t set2,edge e)1418 phi_translate_1 (bitmap_set_t dest,
1419 pre_expr expr, bitmap_set_t set1, bitmap_set_t set2, edge e)
1420 {
1421 basic_block pred = e->src;
1422 basic_block phiblock = e->dest;
1423 location_t expr_loc = expr->loc;
1424 switch (expr->kind)
1425 {
1426 case NARY:
1427 {
1428 unsigned int i;
1429 bool changed = false;
1430 vn_nary_op_t nary = PRE_EXPR_NARY (expr);
1431 vn_nary_op_t newnary = XALLOCAVAR (struct vn_nary_op_s,
1432 sizeof_vn_nary_op (nary->length));
1433 memcpy (newnary, nary, sizeof_vn_nary_op (nary->length));
1434
1435 for (i = 0; i < newnary->length; i++)
1436 {
1437 if (TREE_CODE (newnary->op[i]) != SSA_NAME)
1438 continue;
1439 else
1440 {
1441 pre_expr leader, result;
1442 unsigned int op_val_id = VN_INFO (newnary->op[i])->value_id;
1443 leader = find_leader_in_sets (op_val_id, set1, set2);
1444 result = phi_translate (dest, leader, set1, set2, e);
1445 if (result && result != leader)
1446 /* If op has a leader in the sets we translate make
1447 sure to use the value of the translated expression.
1448 We might need a new representative for that. */
1449 newnary->op[i] = get_representative_for (result, pred);
1450 else if (!result)
1451 return NULL;
1452
1453 changed |= newnary->op[i] != nary->op[i];
1454 }
1455 }
1456 if (changed)
1457 {
1458 pre_expr constant;
1459 unsigned int new_val_id;
1460
1461 PRE_EXPR_NARY (expr) = newnary;
1462 constant = fully_constant_expression (expr);
1463 PRE_EXPR_NARY (expr) = nary;
1464 if (constant != expr)
1465 {
1466 /* For non-CONSTANTs we have to make sure we can eventually
1467 insert the expression. Which means we need to have a
1468 leader for it. */
1469 if (constant->kind != CONSTANT)
1470 {
1471 /* Do not allow simplifications to non-constants over
1472 backedges as this will likely result in a loop PHI node
1473 to be inserted and increased register pressure.
1474 See PR77498 - this avoids doing predcoms work in
1475 a less efficient way. */
1476 if (e->flags & EDGE_DFS_BACK)
1477 ;
1478 else
1479 {
1480 unsigned value_id = get_expr_value_id (constant);
1481 /* We want a leader in ANTIC_OUT or AVAIL_OUT here.
1482 dest has what we computed into ANTIC_OUT sofar
1483 so pick from that - since topological sorting
1484 by sorted_array_from_bitmap_set isn't perfect
1485 we may lose some cases here. */
1486 constant = find_leader_in_sets (value_id, dest,
1487 AVAIL_OUT (pred));
1488 if (constant)
1489 {
1490 if (dump_file && (dump_flags & TDF_DETAILS))
1491 {
1492 fprintf (dump_file, "simplifying ");
1493 print_pre_expr (dump_file, expr);
1494 fprintf (dump_file, " translated %d -> %d to ",
1495 phiblock->index, pred->index);
1496 PRE_EXPR_NARY (expr) = newnary;
1497 print_pre_expr (dump_file, expr);
1498 PRE_EXPR_NARY (expr) = nary;
1499 fprintf (dump_file, " to ");
1500 print_pre_expr (dump_file, constant);
1501 fprintf (dump_file, "\n");
1502 }
1503 return constant;
1504 }
1505 }
1506 }
1507 else
1508 return constant;
1509 }
1510
1511 tree result = vn_nary_op_lookup_pieces (newnary->length,
1512 newnary->opcode,
1513 newnary->type,
1514 &newnary->op[0],
1515 &nary);
1516 if (result && is_gimple_min_invariant (result))
1517 return get_or_alloc_expr_for_constant (result);
1518
1519 if (!nary || nary->predicated_values)
1520 new_val_id = 0;
1521 else
1522 new_val_id = nary->value_id;
1523 expr = get_or_alloc_expr_for_nary (newnary, new_val_id, expr_loc);
1524 add_to_value (get_expr_value_id (expr), expr);
1525 }
1526 return expr;
1527 }
1528 break;
1529
1530 case REFERENCE:
1531 {
1532 vn_reference_t ref = PRE_EXPR_REFERENCE (expr);
1533 vec<vn_reference_op_s> operands = ref->operands;
1534 tree vuse = ref->vuse;
1535 tree newvuse = vuse;
1536 vec<vn_reference_op_s> newoperands = vNULL;
1537 bool changed = false, same_valid = true;
1538 unsigned int i, n;
1539 vn_reference_op_t operand;
1540 vn_reference_t newref;
1541
1542 for (i = 0; operands.iterate (i, &operand); i++)
1543 {
1544 pre_expr opresult;
1545 pre_expr leader;
1546 tree op[3];
1547 tree type = operand->type;
1548 vn_reference_op_s newop = *operand;
1549 op[0] = operand->op0;
1550 op[1] = operand->op1;
1551 op[2] = operand->op2;
1552 for (n = 0; n < 3; ++n)
1553 {
1554 unsigned int op_val_id;
1555 if (!op[n])
1556 continue;
1557 if (TREE_CODE (op[n]) != SSA_NAME)
1558 {
1559 /* We can't possibly insert these. */
1560 if (n != 0
1561 && !is_gimple_min_invariant (op[n]))
1562 break;
1563 continue;
1564 }
1565 op_val_id = VN_INFO (op[n])->value_id;
1566 leader = find_leader_in_sets (op_val_id, set1, set2);
1567 opresult = phi_translate (dest, leader, set1, set2, e);
1568 if (opresult && opresult != leader)
1569 {
1570 tree name = get_representative_for (opresult);
1571 changed |= name != op[n];
1572 op[n] = name;
1573 }
1574 else if (!opresult)
1575 break;
1576 }
1577 if (n != 3)
1578 {
1579 newoperands.release ();
1580 return NULL;
1581 }
1582 /* When we translate a MEM_REF across a backedge and we have
1583 restrict info that's not from our functions parameters
1584 we have to remap it since we now may deal with a different
1585 instance where the dependence info is no longer valid.
1586 See PR102970. Note instead of keeping a remapping table
1587 per backedge we simply throw away restrict info. */
1588 if ((newop.opcode == MEM_REF
1589 || newop.opcode == TARGET_MEM_REF)
1590 && newop.clique > 1
1591 && (e->flags & EDGE_DFS_BACK))
1592 {
1593 newop.clique = 0;
1594 newop.base = 0;
1595 changed = true;
1596 }
1597 if (!changed)
1598 continue;
1599 if (!newoperands.exists ())
1600 newoperands = operands.copy ();
1601 /* We may have changed from an SSA_NAME to a constant */
1602 if (newop.opcode == SSA_NAME && TREE_CODE (op[0]) != SSA_NAME)
1603 newop.opcode = TREE_CODE (op[0]);
1604 newop.type = type;
1605 newop.op0 = op[0];
1606 newop.op1 = op[1];
1607 newop.op2 = op[2];
1608 newoperands[i] = newop;
1609 }
1610 gcc_checking_assert (i == operands.length ());
1611
1612 if (vuse)
1613 {
1614 newvuse = translate_vuse_through_block (newoperands.exists ()
1615 ? newoperands : operands,
1616 ref->set, ref->base_set,
1617 ref->type, vuse, e,
1618 changed
1619 ? NULL : &same_valid);
1620 if (newvuse == NULL_TREE)
1621 {
1622 newoperands.release ();
1623 return NULL;
1624 }
1625 }
1626
1627 if (changed || newvuse != vuse)
1628 {
1629 unsigned int new_val_id;
1630
1631 tree result = vn_reference_lookup_pieces (newvuse, ref->set,
1632 ref->base_set,
1633 ref->type,
1634 newoperands.exists ()
1635 ? newoperands : operands,
1636 &newref, VN_WALK);
1637 if (result)
1638 newoperands.release ();
1639
1640 /* We can always insert constants, so if we have a partial
1641 redundant constant load of another type try to translate it
1642 to a constant of appropriate type. */
1643 if (result && is_gimple_min_invariant (result))
1644 {
1645 tree tem = result;
1646 if (!useless_type_conversion_p (ref->type, TREE_TYPE (result)))
1647 {
1648 tem = fold_unary (VIEW_CONVERT_EXPR, ref->type, result);
1649 if (tem && !is_gimple_min_invariant (tem))
1650 tem = NULL_TREE;
1651 }
1652 if (tem)
1653 return get_or_alloc_expr_for_constant (tem);
1654 }
1655
1656 /* If we'd have to convert things we would need to validate
1657 if we can insert the translated expression. So fail
1658 here for now - we cannot insert an alias with a different
1659 type in the VN tables either, as that would assert. */
1660 if (result
1661 && !useless_type_conversion_p (ref->type, TREE_TYPE (result)))
1662 return NULL;
1663 else if (!result && newref
1664 && !useless_type_conversion_p (ref->type, newref->type))
1665 {
1666 newoperands.release ();
1667 return NULL;
1668 }
1669
1670 if (newref)
1671 new_val_id = newref->value_id;
1672 else
1673 {
1674 if (changed || !same_valid)
1675 new_val_id = get_next_value_id ();
1676 else
1677 new_val_id = ref->value_id;
1678 if (!newoperands.exists ())
1679 newoperands = operands.copy ();
1680 newref = vn_reference_insert_pieces (newvuse, ref->set,
1681 ref->base_set, ref->type,
1682 newoperands,
1683 result, new_val_id);
1684 newoperands = vNULL;
1685 }
1686 expr = get_or_alloc_expr_for_reference (newref, expr_loc);
1687 add_to_value (new_val_id, expr);
1688 }
1689 newoperands.release ();
1690 return expr;
1691 }
1692 break;
1693
1694 case NAME:
1695 {
1696 tree name = PRE_EXPR_NAME (expr);
1697 gimple *def_stmt = SSA_NAME_DEF_STMT (name);
1698 /* If the SSA name is defined by a PHI node in this block,
1699 translate it. */
1700 if (gimple_code (def_stmt) == GIMPLE_PHI
1701 && gimple_bb (def_stmt) == phiblock)
1702 {
1703 tree def = PHI_ARG_DEF (def_stmt, e->dest_idx);
1704
1705 /* Handle constant. */
1706 if (is_gimple_min_invariant (def))
1707 return get_or_alloc_expr_for_constant (def);
1708
1709 return get_or_alloc_expr_for_name (def);
1710 }
1711 /* Otherwise return it unchanged - it will get removed if its
1712 value is not available in PREDs AVAIL_OUT set of expressions
1713 by the subtraction of TMP_GEN. */
1714 return expr;
1715 }
1716
1717 default:
1718 gcc_unreachable ();
1719 }
1720 }
1721
1722 /* Wrapper around phi_translate_1 providing caching functionality. */
1723
1724 static pre_expr
phi_translate(bitmap_set_t dest,pre_expr expr,bitmap_set_t set1,bitmap_set_t set2,edge e)1725 phi_translate (bitmap_set_t dest, pre_expr expr,
1726 bitmap_set_t set1, bitmap_set_t set2, edge e)
1727 {
1728 expr_pred_trans_t slot = NULL;
1729 pre_expr phitrans;
1730
1731 if (!expr)
1732 return NULL;
1733
1734 /* Constants contain no values that need translation. */
1735 if (expr->kind == CONSTANT)
1736 return expr;
1737
1738 if (value_id_constant_p (get_expr_value_id (expr)))
1739 return expr;
1740
1741 /* Don't add translations of NAMEs as those are cheap to translate. */
1742 if (expr->kind != NAME)
1743 {
1744 if (phi_trans_add (&slot, expr, e->src))
1745 return slot->v == 0 ? NULL : expression_for_id (slot->v);
1746 /* Store NULL for the value we want to return in the case of
1747 recursing. */
1748 slot->v = 0;
1749 }
1750
1751 /* Translate. */
1752 basic_block saved_valueize_bb = vn_context_bb;
1753 vn_context_bb = e->src;
1754 phitrans = phi_translate_1 (dest, expr, set1, set2, e);
1755 vn_context_bb = saved_valueize_bb;
1756
1757 if (slot)
1758 {
1759 /* We may have reallocated. */
1760 phi_trans_add (&slot, expr, e->src);
1761 if (phitrans)
1762 slot->v = get_expression_id (phitrans);
1763 else
1764 /* Remove failed translations again, they cause insert
1765 iteration to not pick up new opportunities reliably. */
1766 PHI_TRANS_TABLE (e->src)->clear_slot (slot);
1767 }
1768
1769 return phitrans;
1770 }
1771
1772
1773 /* For each expression in SET, translate the values through phi nodes
1774 in PHIBLOCK using edge PHIBLOCK->PRED, and store the resulting
1775 expressions in DEST. */
1776
1777 static void
phi_translate_set(bitmap_set_t dest,bitmap_set_t set,edge e)1778 phi_translate_set (bitmap_set_t dest, bitmap_set_t set, edge e)
1779 {
1780 bitmap_iterator bi;
1781 unsigned int i;
1782
1783 if (gimple_seq_empty_p (phi_nodes (e->dest)))
1784 {
1785 bitmap_set_copy (dest, set);
1786 return;
1787 }
1788
1789 /* Allocate the phi-translation cache where we have an idea about
1790 its size. hash-table implementation internals tell us that
1791 allocating the table to fit twice the number of elements will
1792 make sure we do not usually re-allocate. */
1793 if (!PHI_TRANS_TABLE (e->src))
1794 PHI_TRANS_TABLE (e->src) = new hash_table<expr_pred_trans_d>
1795 (2 * bitmap_count_bits (&set->expressions));
1796 FOR_EACH_EXPR_ID_IN_SET (set, i, bi)
1797 {
1798 pre_expr expr = expression_for_id (i);
1799 pre_expr translated = phi_translate (dest, expr, set, NULL, e);
1800 if (!translated)
1801 continue;
1802
1803 bitmap_insert_into_set (dest, translated);
1804 }
1805 }
1806
1807 /* Find the leader for a value (i.e., the name representing that
1808 value) in a given set, and return it. Return NULL if no leader
1809 is found. */
1810
1811 static pre_expr
bitmap_find_leader(bitmap_set_t set,unsigned int val)1812 bitmap_find_leader (bitmap_set_t set, unsigned int val)
1813 {
1814 if (value_id_constant_p (val))
1815 return constant_value_expressions[-val];
1816
1817 if (bitmap_set_contains_value (set, val))
1818 {
1819 /* Rather than walk the entire bitmap of expressions, and see
1820 whether any of them has the value we are looking for, we look
1821 at the reverse mapping, which tells us the set of expressions
1822 that have a given value (IE value->expressions with that
1823 value) and see if any of those expressions are in our set.
1824 The number of expressions per value is usually significantly
1825 less than the number of expressions in the set. In fact, for
1826 large testcases, doing it this way is roughly 5-10x faster
1827 than walking the bitmap.
1828 If this is somehow a significant lose for some cases, we can
1829 choose which set to walk based on which set is smaller. */
1830 unsigned int i;
1831 bitmap_iterator bi;
1832 bitmap exprset = value_expressions[val];
1833
1834 if (!exprset->first->next)
1835 EXECUTE_IF_SET_IN_BITMAP (exprset, 0, i, bi)
1836 if (bitmap_bit_p (&set->expressions, i))
1837 return expression_for_id (i);
1838
1839 EXECUTE_IF_AND_IN_BITMAP (exprset, &set->expressions, 0, i, bi)
1840 return expression_for_id (i);
1841 }
1842 return NULL;
1843 }
1844
1845 /* Determine if EXPR, a memory expression, is ANTIC_IN at the top of
1846 BLOCK by seeing if it is not killed in the block. Note that we are
1847 only determining whether there is a store that kills it. Because
1848 of the order in which clean iterates over values, we are guaranteed
1849 that altered operands will have caused us to be eliminated from the
1850 ANTIC_IN set already. */
1851
1852 static bool
value_dies_in_block_x(pre_expr expr,basic_block block)1853 value_dies_in_block_x (pre_expr expr, basic_block block)
1854 {
1855 tree vuse = PRE_EXPR_REFERENCE (expr)->vuse;
1856 vn_reference_t refx = PRE_EXPR_REFERENCE (expr);
1857 gimple *def;
1858 gimple_stmt_iterator gsi;
1859 unsigned id = get_expression_id (expr);
1860 bool res = false;
1861 ao_ref ref;
1862
1863 if (!vuse)
1864 return false;
1865
1866 /* Lookup a previously calculated result. */
1867 if (EXPR_DIES (block)
1868 && bitmap_bit_p (EXPR_DIES (block), id * 2))
1869 return bitmap_bit_p (EXPR_DIES (block), id * 2 + 1);
1870
1871 /* A memory expression {e, VUSE} dies in the block if there is a
1872 statement that may clobber e. If, starting statement walk from the
1873 top of the basic block, a statement uses VUSE there can be no kill
1874 inbetween that use and the original statement that loaded {e, VUSE},
1875 so we can stop walking. */
1876 ref.base = NULL_TREE;
1877 for (gsi = gsi_start_bb (block); !gsi_end_p (gsi); gsi_next (&gsi))
1878 {
1879 tree def_vuse, def_vdef;
1880 def = gsi_stmt (gsi);
1881 def_vuse = gimple_vuse (def);
1882 def_vdef = gimple_vdef (def);
1883
1884 /* Not a memory statement. */
1885 if (!def_vuse)
1886 continue;
1887
1888 /* Not a may-def. */
1889 if (!def_vdef)
1890 {
1891 /* A load with the same VUSE, we're done. */
1892 if (def_vuse == vuse)
1893 break;
1894
1895 continue;
1896 }
1897
1898 /* Init ref only if we really need it. */
1899 if (ref.base == NULL_TREE
1900 && !ao_ref_init_from_vn_reference (&ref, refx->set, refx->base_set,
1901 refx->type, refx->operands))
1902 {
1903 res = true;
1904 break;
1905 }
1906 /* If the statement may clobber expr, it dies. */
1907 if (stmt_may_clobber_ref_p_1 (def, &ref))
1908 {
1909 res = true;
1910 break;
1911 }
1912 }
1913
1914 /* Remember the result. */
1915 if (!EXPR_DIES (block))
1916 EXPR_DIES (block) = BITMAP_ALLOC (&grand_bitmap_obstack);
1917 bitmap_set_bit (EXPR_DIES (block), id * 2);
1918 if (res)
1919 bitmap_set_bit (EXPR_DIES (block), id * 2 + 1);
1920
1921 return res;
1922 }
1923
1924
1925 /* Determine if OP is valid in SET1 U SET2, which it is when the union
1926 contains its value-id. */
1927
1928 static bool
op_valid_in_sets(bitmap_set_t set1,bitmap_set_t set2,tree op)1929 op_valid_in_sets (bitmap_set_t set1, bitmap_set_t set2, tree op)
1930 {
1931 if (op && TREE_CODE (op) == SSA_NAME)
1932 {
1933 unsigned int value_id = VN_INFO (op)->value_id;
1934 if (!(bitmap_set_contains_value (set1, value_id)
1935 || (set2 && bitmap_set_contains_value (set2, value_id))))
1936 return false;
1937 }
1938 return true;
1939 }
1940
1941 /* Determine if the expression EXPR is valid in SET1 U SET2.
1942 ONLY SET2 CAN BE NULL.
1943 This means that we have a leader for each part of the expression
1944 (if it consists of values), or the expression is an SSA_NAME.
1945 For loads/calls, we also see if the vuse is killed in this block. */
1946
1947 static bool
valid_in_sets(bitmap_set_t set1,bitmap_set_t set2,pre_expr expr)1948 valid_in_sets (bitmap_set_t set1, bitmap_set_t set2, pre_expr expr)
1949 {
1950 switch (expr->kind)
1951 {
1952 case NAME:
1953 /* By construction all NAMEs are available. Non-available
1954 NAMEs are removed by subtracting TMP_GEN from the sets. */
1955 return true;
1956 case NARY:
1957 {
1958 unsigned int i;
1959 vn_nary_op_t nary = PRE_EXPR_NARY (expr);
1960 for (i = 0; i < nary->length; i++)
1961 if (!op_valid_in_sets (set1, set2, nary->op[i]))
1962 return false;
1963 return true;
1964 }
1965 break;
1966 case REFERENCE:
1967 {
1968 vn_reference_t ref = PRE_EXPR_REFERENCE (expr);
1969 vn_reference_op_t vro;
1970 unsigned int i;
1971
1972 FOR_EACH_VEC_ELT (ref->operands, i, vro)
1973 {
1974 if (!op_valid_in_sets (set1, set2, vro->op0)
1975 || !op_valid_in_sets (set1, set2, vro->op1)
1976 || !op_valid_in_sets (set1, set2, vro->op2))
1977 return false;
1978 }
1979 return true;
1980 }
1981 default:
1982 gcc_unreachable ();
1983 }
1984 }
1985
1986 /* Clean the set of expressions SET1 that are no longer valid in SET1 or SET2.
1987 This means expressions that are made up of values we have no leaders for
1988 in SET1 or SET2. */
1989
1990 static void
clean(bitmap_set_t set1,bitmap_set_t set2=NULL)1991 clean (bitmap_set_t set1, bitmap_set_t set2 = NULL)
1992 {
1993 vec<pre_expr> exprs = sorted_array_from_bitmap_set (set1);
1994 pre_expr expr;
1995 int i;
1996
1997 FOR_EACH_VEC_ELT (exprs, i, expr)
1998 {
1999 if (!valid_in_sets (set1, set2, expr))
2000 {
2001 unsigned int val = get_expr_value_id (expr);
2002 bitmap_clear_bit (&set1->expressions, get_expression_id (expr));
2003 /* We are entered with possibly multiple expressions for a value
2004 so before removing a value from the set see if there's an
2005 expression for it left. */
2006 if (! bitmap_find_leader (set1, val))
2007 bitmap_clear_bit (&set1->values, val);
2008 }
2009 }
2010 exprs.release ();
2011
2012 if (flag_checking)
2013 {
2014 unsigned j;
2015 bitmap_iterator bi;
2016 FOR_EACH_EXPR_ID_IN_SET (set1, j, bi)
2017 gcc_assert (valid_in_sets (set1, set2, expression_for_id (j)));
2018 }
2019 }
2020
2021 /* Clean the set of expressions that are no longer valid in SET because
2022 they are clobbered in BLOCK or because they trap and may not be executed. */
2023
2024 static void
prune_clobbered_mems(bitmap_set_t set,basic_block block)2025 prune_clobbered_mems (bitmap_set_t set, basic_block block)
2026 {
2027 bitmap_iterator bi;
2028 unsigned i;
2029 unsigned to_remove = -1U;
2030 bool any_removed = false;
2031
2032 FOR_EACH_EXPR_ID_IN_SET (set, i, bi)
2033 {
2034 /* Remove queued expr. */
2035 if (to_remove != -1U)
2036 {
2037 bitmap_clear_bit (&set->expressions, to_remove);
2038 any_removed = true;
2039 to_remove = -1U;
2040 }
2041
2042 pre_expr expr = expression_for_id (i);
2043 if (expr->kind == REFERENCE)
2044 {
2045 vn_reference_t ref = PRE_EXPR_REFERENCE (expr);
2046 if (ref->vuse)
2047 {
2048 gimple *def_stmt = SSA_NAME_DEF_STMT (ref->vuse);
2049 if (!gimple_nop_p (def_stmt)
2050 /* If value-numbering provided a memory state for this
2051 that dominates BLOCK we're done, otherwise we have
2052 to check if the value dies in BLOCK. */
2053 && !(gimple_bb (def_stmt) != block
2054 && dominated_by_p (CDI_DOMINATORS,
2055 block, gimple_bb (def_stmt)))
2056 && value_dies_in_block_x (expr, block))
2057 to_remove = i;
2058 }
2059 /* If the REFERENCE may trap make sure the block does not contain
2060 a possible exit point.
2061 ??? This is overly conservative if we translate AVAIL_OUT
2062 as the available expression might be after the exit point. */
2063 if (BB_MAY_NOTRETURN (block)
2064 && vn_reference_may_trap (ref))
2065 to_remove = i;
2066 }
2067 else if (expr->kind == NARY)
2068 {
2069 vn_nary_op_t nary = PRE_EXPR_NARY (expr);
2070 /* If the NARY may trap make sure the block does not contain
2071 a possible exit point.
2072 ??? This is overly conservative if we translate AVAIL_OUT
2073 as the available expression might be after the exit point. */
2074 if (BB_MAY_NOTRETURN (block)
2075 && vn_nary_may_trap (nary))
2076 to_remove = i;
2077 }
2078 }
2079
2080 /* Remove queued expr. */
2081 if (to_remove != -1U)
2082 {
2083 bitmap_clear_bit (&set->expressions, to_remove);
2084 any_removed = true;
2085 }
2086
2087 /* Above we only removed expressions, now clean the set of values
2088 which no longer have any corresponding expression. We cannot
2089 clear the value at the time we remove an expression since there
2090 may be multiple expressions per value.
2091 If we'd queue possibly to be removed values we could use
2092 the bitmap_find_leader way to see if there's still an expression
2093 for it. For some ratio of to be removed values and number of
2094 values/expressions in the set this might be faster than rebuilding
2095 the value-set. */
2096 if (any_removed)
2097 {
2098 bitmap_clear (&set->values);
2099 FOR_EACH_EXPR_ID_IN_SET (set, i, bi)
2100 {
2101 pre_expr expr = expression_for_id (i);
2102 unsigned int value_id = get_expr_value_id (expr);
2103 bitmap_set_bit (&set->values, value_id);
2104 }
2105 }
2106 }
2107
2108 /* Compute the ANTIC set for BLOCK.
2109
2110 If succs(BLOCK) > 1 then
2111 ANTIC_OUT[BLOCK] = intersection of ANTIC_IN[b] for all succ(BLOCK)
2112 else if succs(BLOCK) == 1 then
2113 ANTIC_OUT[BLOCK] = phi_translate (ANTIC_IN[succ(BLOCK)])
2114
2115 ANTIC_IN[BLOCK] = clean(ANTIC_OUT[BLOCK] U EXP_GEN[BLOCK] - TMP_GEN[BLOCK])
2116
2117 Note that clean() is deferred until after the iteration. */
2118
2119 static bool
compute_antic_aux(basic_block block,bool block_has_abnormal_pred_edge)2120 compute_antic_aux (basic_block block, bool block_has_abnormal_pred_edge)
2121 {
2122 bitmap_set_t S, old, ANTIC_OUT;
2123 edge e;
2124 edge_iterator ei;
2125
2126 bool was_visited = BB_VISITED (block);
2127 bool changed = ! BB_VISITED (block);
2128 BB_VISITED (block) = 1;
2129 old = ANTIC_OUT = S = NULL;
2130
2131 /* If any edges from predecessors are abnormal, antic_in is empty,
2132 so do nothing. */
2133 if (block_has_abnormal_pred_edge)
2134 goto maybe_dump_sets;
2135
2136 old = ANTIC_IN (block);
2137 ANTIC_OUT = bitmap_set_new ();
2138
2139 /* If the block has no successors, ANTIC_OUT is empty. */
2140 if (EDGE_COUNT (block->succs) == 0)
2141 ;
2142 /* If we have one successor, we could have some phi nodes to
2143 translate through. */
2144 else if (single_succ_p (block))
2145 {
2146 e = single_succ_edge (block);
2147 gcc_assert (BB_VISITED (e->dest));
2148 phi_translate_set (ANTIC_OUT, ANTIC_IN (e->dest), e);
2149 }
2150 /* If we have multiple successors, we take the intersection of all of
2151 them. Note that in the case of loop exit phi nodes, we may have
2152 phis to translate through. */
2153 else
2154 {
2155 size_t i;
2156 edge first = NULL;
2157
2158 auto_vec<edge> worklist (EDGE_COUNT (block->succs));
2159 FOR_EACH_EDGE (e, ei, block->succs)
2160 {
2161 if (!first
2162 && BB_VISITED (e->dest))
2163 first = e;
2164 else if (BB_VISITED (e->dest))
2165 worklist.quick_push (e);
2166 else
2167 {
2168 /* Unvisited successors get their ANTIC_IN replaced by the
2169 maximal set to arrive at a maximum ANTIC_IN solution.
2170 We can ignore them in the intersection operation and thus
2171 need not explicitely represent that maximum solution. */
2172 if (dump_file && (dump_flags & TDF_DETAILS))
2173 fprintf (dump_file, "ANTIC_IN is MAX on %d->%d\n",
2174 e->src->index, e->dest->index);
2175 }
2176 }
2177
2178 /* Of multiple successors we have to have visited one already
2179 which is guaranteed by iteration order. */
2180 gcc_assert (first != NULL);
2181
2182 phi_translate_set (ANTIC_OUT, ANTIC_IN (first->dest), first);
2183
2184 /* If we have multiple successors we need to intersect the ANTIC_OUT
2185 sets. For values that's a simple intersection but for
2186 expressions it is a union. Given we want to have a single
2187 expression per value in our sets we have to canonicalize.
2188 Avoid randomness and running into cycles like for PR82129 and
2189 canonicalize the expression we choose to the one with the
2190 lowest id. This requires we actually compute the union first. */
2191 FOR_EACH_VEC_ELT (worklist, i, e)
2192 {
2193 if (!gimple_seq_empty_p (phi_nodes (e->dest)))
2194 {
2195 bitmap_set_t tmp = bitmap_set_new ();
2196 phi_translate_set (tmp, ANTIC_IN (e->dest), e);
2197 bitmap_and_into (&ANTIC_OUT->values, &tmp->values);
2198 bitmap_ior_into (&ANTIC_OUT->expressions, &tmp->expressions);
2199 bitmap_set_free (tmp);
2200 }
2201 else
2202 {
2203 bitmap_and_into (&ANTIC_OUT->values, &ANTIC_IN (e->dest)->values);
2204 bitmap_ior_into (&ANTIC_OUT->expressions,
2205 &ANTIC_IN (e->dest)->expressions);
2206 }
2207 }
2208 if (! worklist.is_empty ())
2209 {
2210 /* Prune expressions not in the value set. */
2211 bitmap_iterator bi;
2212 unsigned int i;
2213 unsigned int to_clear = -1U;
2214 FOR_EACH_EXPR_ID_IN_SET (ANTIC_OUT, i, bi)
2215 {
2216 if (to_clear != -1U)
2217 {
2218 bitmap_clear_bit (&ANTIC_OUT->expressions, to_clear);
2219 to_clear = -1U;
2220 }
2221 pre_expr expr = expression_for_id (i);
2222 unsigned int value_id = get_expr_value_id (expr);
2223 if (!bitmap_bit_p (&ANTIC_OUT->values, value_id))
2224 to_clear = i;
2225 }
2226 if (to_clear != -1U)
2227 bitmap_clear_bit (&ANTIC_OUT->expressions, to_clear);
2228 }
2229 }
2230
2231 /* Prune expressions that are clobbered in block and thus become
2232 invalid if translated from ANTIC_OUT to ANTIC_IN. */
2233 prune_clobbered_mems (ANTIC_OUT, block);
2234
2235 /* Generate ANTIC_OUT - TMP_GEN. */
2236 S = bitmap_set_subtract_expressions (ANTIC_OUT, TMP_GEN (block));
2237
2238 /* Start ANTIC_IN with EXP_GEN - TMP_GEN. */
2239 ANTIC_IN (block) = bitmap_set_subtract_expressions (EXP_GEN (block),
2240 TMP_GEN (block));
2241
2242 /* Then union in the ANTIC_OUT - TMP_GEN values,
2243 to get ANTIC_OUT U EXP_GEN - TMP_GEN */
2244 bitmap_ior_into (&ANTIC_IN (block)->values, &S->values);
2245 bitmap_ior_into (&ANTIC_IN (block)->expressions, &S->expressions);
2246
2247 /* clean (ANTIC_IN (block)) is defered to after the iteration converged
2248 because it can cause non-convergence, see for example PR81181. */
2249
2250 /* Intersect ANTIC_IN with the old ANTIC_IN. This is required until
2251 we properly represent the maximum expression set, thus not prune
2252 values without expressions during the iteration. */
2253 if (was_visited
2254 && bitmap_and_into (&ANTIC_IN (block)->values, &old->values))
2255 {
2256 if (dump_file && (dump_flags & TDF_DETAILS))
2257 fprintf (dump_file, "warning: intersecting with old ANTIC_IN "
2258 "shrinks the set\n");
2259 /* Prune expressions not in the value set. */
2260 bitmap_iterator bi;
2261 unsigned int i;
2262 unsigned int to_clear = -1U;
2263 FOR_EACH_EXPR_ID_IN_SET (ANTIC_IN (block), i, bi)
2264 {
2265 if (to_clear != -1U)
2266 {
2267 bitmap_clear_bit (&ANTIC_IN (block)->expressions, to_clear);
2268 to_clear = -1U;
2269 }
2270 pre_expr expr = expression_for_id (i);
2271 unsigned int value_id = get_expr_value_id (expr);
2272 if (!bitmap_bit_p (&ANTIC_IN (block)->values, value_id))
2273 to_clear = i;
2274 }
2275 if (to_clear != -1U)
2276 bitmap_clear_bit (&ANTIC_IN (block)->expressions, to_clear);
2277 }
2278
2279 if (!bitmap_set_equal (old, ANTIC_IN (block)))
2280 changed = true;
2281
2282 maybe_dump_sets:
2283 if (dump_file && (dump_flags & TDF_DETAILS))
2284 {
2285 if (ANTIC_OUT)
2286 print_bitmap_set (dump_file, ANTIC_OUT, "ANTIC_OUT", block->index);
2287
2288 if (changed)
2289 fprintf (dump_file, "[changed] ");
2290 print_bitmap_set (dump_file, ANTIC_IN (block), "ANTIC_IN",
2291 block->index);
2292
2293 if (S)
2294 print_bitmap_set (dump_file, S, "S", block->index);
2295 }
2296 if (old)
2297 bitmap_set_free (old);
2298 if (S)
2299 bitmap_set_free (S);
2300 if (ANTIC_OUT)
2301 bitmap_set_free (ANTIC_OUT);
2302 return changed;
2303 }
2304
2305 /* Compute PARTIAL_ANTIC for BLOCK.
2306
2307 If succs(BLOCK) > 1 then
2308 PA_OUT[BLOCK] = value wise union of PA_IN[b] + all ANTIC_IN not
2309 in ANTIC_OUT for all succ(BLOCK)
2310 else if succs(BLOCK) == 1 then
2311 PA_OUT[BLOCK] = phi_translate (PA_IN[succ(BLOCK)])
2312
2313 PA_IN[BLOCK] = clean(PA_OUT[BLOCK] - TMP_GEN[BLOCK] - ANTIC_IN[BLOCK])
2314
2315 */
2316 static void
compute_partial_antic_aux(basic_block block,bool block_has_abnormal_pred_edge)2317 compute_partial_antic_aux (basic_block block,
2318 bool block_has_abnormal_pred_edge)
2319 {
2320 bitmap_set_t old_PA_IN;
2321 bitmap_set_t PA_OUT;
2322 edge e;
2323 edge_iterator ei;
2324 unsigned long max_pa = param_max_partial_antic_length;
2325
2326 old_PA_IN = PA_OUT = NULL;
2327
2328 /* If any edges from predecessors are abnormal, antic_in is empty,
2329 so do nothing. */
2330 if (block_has_abnormal_pred_edge)
2331 goto maybe_dump_sets;
2332
2333 /* If there are too many partially anticipatable values in the
2334 block, phi_translate_set can take an exponential time: stop
2335 before the translation starts. */
2336 if (max_pa
2337 && single_succ_p (block)
2338 && bitmap_count_bits (&PA_IN (single_succ (block))->values) > max_pa)
2339 goto maybe_dump_sets;
2340
2341 old_PA_IN = PA_IN (block);
2342 PA_OUT = bitmap_set_new ();
2343
2344 /* If the block has no successors, ANTIC_OUT is empty. */
2345 if (EDGE_COUNT (block->succs) == 0)
2346 ;
2347 /* If we have one successor, we could have some phi nodes to
2348 translate through. Note that we can't phi translate across DFS
2349 back edges in partial antic, because it uses a union operation on
2350 the successors. For recurrences like IV's, we will end up
2351 generating a new value in the set on each go around (i + 3 (VH.1)
2352 VH.1 + 1 (VH.2), VH.2 + 1 (VH.3), etc), forever. */
2353 else if (single_succ_p (block))
2354 {
2355 e = single_succ_edge (block);
2356 if (!(e->flags & EDGE_DFS_BACK))
2357 phi_translate_set (PA_OUT, PA_IN (e->dest), e);
2358 }
2359 /* If we have multiple successors, we take the union of all of
2360 them. */
2361 else
2362 {
2363 size_t i;
2364
2365 auto_vec<edge> worklist (EDGE_COUNT (block->succs));
2366 FOR_EACH_EDGE (e, ei, block->succs)
2367 {
2368 if (e->flags & EDGE_DFS_BACK)
2369 continue;
2370 worklist.quick_push (e);
2371 }
2372 if (worklist.length () > 0)
2373 {
2374 FOR_EACH_VEC_ELT (worklist, i, e)
2375 {
2376 unsigned int i;
2377 bitmap_iterator bi;
2378
2379 FOR_EACH_EXPR_ID_IN_SET (ANTIC_IN (e->dest), i, bi)
2380 bitmap_value_insert_into_set (PA_OUT,
2381 expression_for_id (i));
2382 if (!gimple_seq_empty_p (phi_nodes (e->dest)))
2383 {
2384 bitmap_set_t pa_in = bitmap_set_new ();
2385 phi_translate_set (pa_in, PA_IN (e->dest), e);
2386 FOR_EACH_EXPR_ID_IN_SET (pa_in, i, bi)
2387 bitmap_value_insert_into_set (PA_OUT,
2388 expression_for_id (i));
2389 bitmap_set_free (pa_in);
2390 }
2391 else
2392 FOR_EACH_EXPR_ID_IN_SET (PA_IN (e->dest), i, bi)
2393 bitmap_value_insert_into_set (PA_OUT,
2394 expression_for_id (i));
2395 }
2396 }
2397 }
2398
2399 /* Prune expressions that are clobbered in block and thus become
2400 invalid if translated from PA_OUT to PA_IN. */
2401 prune_clobbered_mems (PA_OUT, block);
2402
2403 /* PA_IN starts with PA_OUT - TMP_GEN.
2404 Then we subtract things from ANTIC_IN. */
2405 PA_IN (block) = bitmap_set_subtract_expressions (PA_OUT, TMP_GEN (block));
2406
2407 /* For partial antic, we want to put back in the phi results, since
2408 we will properly avoid making them partially antic over backedges. */
2409 bitmap_ior_into (&PA_IN (block)->values, &PHI_GEN (block)->values);
2410 bitmap_ior_into (&PA_IN (block)->expressions, &PHI_GEN (block)->expressions);
2411
2412 /* PA_IN[block] = PA_IN[block] - ANTIC_IN[block] */
2413 bitmap_set_subtract_values (PA_IN (block), ANTIC_IN (block));
2414
2415 clean (PA_IN (block), ANTIC_IN (block));
2416
2417 maybe_dump_sets:
2418 if (dump_file && (dump_flags & TDF_DETAILS))
2419 {
2420 if (PA_OUT)
2421 print_bitmap_set (dump_file, PA_OUT, "PA_OUT", block->index);
2422
2423 print_bitmap_set (dump_file, PA_IN (block), "PA_IN", block->index);
2424 }
2425 if (old_PA_IN)
2426 bitmap_set_free (old_PA_IN);
2427 if (PA_OUT)
2428 bitmap_set_free (PA_OUT);
2429 }
2430
2431 /* Compute ANTIC and partial ANTIC sets. */
2432
2433 static void
compute_antic(void)2434 compute_antic (void)
2435 {
2436 bool changed = true;
2437 int num_iterations = 0;
2438 basic_block block;
2439 int i;
2440 edge_iterator ei;
2441 edge e;
2442
2443 /* If any predecessor edges are abnormal, we punt, so antic_in is empty.
2444 We pre-build the map of blocks with incoming abnormal edges here. */
2445 auto_sbitmap has_abnormal_preds (last_basic_block_for_fn (cfun));
2446 bitmap_clear (has_abnormal_preds);
2447
2448 FOR_ALL_BB_FN (block, cfun)
2449 {
2450 BB_VISITED (block) = 0;
2451
2452 FOR_EACH_EDGE (e, ei, block->preds)
2453 if (e->flags & EDGE_ABNORMAL)
2454 {
2455 bitmap_set_bit (has_abnormal_preds, block->index);
2456 break;
2457 }
2458
2459 /* While we are here, give empty ANTIC_IN sets to each block. */
2460 ANTIC_IN (block) = bitmap_set_new ();
2461 if (do_partial_partial)
2462 PA_IN (block) = bitmap_set_new ();
2463 }
2464
2465 /* At the exit block we anticipate nothing. */
2466 BB_VISITED (EXIT_BLOCK_PTR_FOR_FN (cfun)) = 1;
2467
2468 /* For ANTIC computation we need a postorder that also guarantees that
2469 a block with a single successor is visited after its successor.
2470 RPO on the inverted CFG has this property. */
2471 auto_vec<int, 20> postorder;
2472 inverted_post_order_compute (&postorder);
2473
2474 auto_sbitmap worklist (last_basic_block_for_fn (cfun) + 1);
2475 bitmap_clear (worklist);
2476 FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR_FOR_FN (cfun)->preds)
2477 bitmap_set_bit (worklist, e->src->index);
2478 while (changed)
2479 {
2480 if (dump_file && (dump_flags & TDF_DETAILS))
2481 fprintf (dump_file, "Starting iteration %d\n", num_iterations);
2482 /* ??? We need to clear our PHI translation cache here as the
2483 ANTIC sets shrink and we restrict valid translations to
2484 those having operands with leaders in ANTIC. Same below
2485 for PA ANTIC computation. */
2486 num_iterations++;
2487 changed = false;
2488 for (i = postorder.length () - 1; i >= 0; i--)
2489 {
2490 if (bitmap_bit_p (worklist, postorder[i]))
2491 {
2492 basic_block block = BASIC_BLOCK_FOR_FN (cfun, postorder[i]);
2493 bitmap_clear_bit (worklist, block->index);
2494 if (compute_antic_aux (block,
2495 bitmap_bit_p (has_abnormal_preds,
2496 block->index)))
2497 {
2498 FOR_EACH_EDGE (e, ei, block->preds)
2499 bitmap_set_bit (worklist, e->src->index);
2500 changed = true;
2501 }
2502 }
2503 }
2504 /* Theoretically possible, but *highly* unlikely. */
2505 gcc_checking_assert (num_iterations < 500);
2506 }
2507
2508 /* We have to clean after the dataflow problem converged as cleaning
2509 can cause non-convergence because it is based on expressions
2510 rather than values. */
2511 FOR_EACH_BB_FN (block, cfun)
2512 clean (ANTIC_IN (block));
2513
2514 statistics_histogram_event (cfun, "compute_antic iterations",
2515 num_iterations);
2516
2517 if (do_partial_partial)
2518 {
2519 /* For partial antic we ignore backedges and thus we do not need
2520 to perform any iteration when we process blocks in postorder. */
2521 for (i = postorder.length () - 1; i >= 0; i--)
2522 {
2523 basic_block block = BASIC_BLOCK_FOR_FN (cfun, postorder[i]);
2524 compute_partial_antic_aux (block,
2525 bitmap_bit_p (has_abnormal_preds,
2526 block->index));
2527 }
2528 }
2529 }
2530
2531
2532 /* Inserted expressions are placed onto this worklist, which is used
2533 for performing quick dead code elimination of insertions we made
2534 that didn't turn out to be necessary. */
2535 static bitmap inserted_exprs;
2536
2537 /* The actual worker for create_component_ref_by_pieces. */
2538
2539 static tree
create_component_ref_by_pieces_1(basic_block block,vn_reference_t ref,unsigned int * operand,gimple_seq * stmts)2540 create_component_ref_by_pieces_1 (basic_block block, vn_reference_t ref,
2541 unsigned int *operand, gimple_seq *stmts)
2542 {
2543 vn_reference_op_t currop = &ref->operands[*operand];
2544 tree genop;
2545 ++*operand;
2546 switch (currop->opcode)
2547 {
2548 case CALL_EXPR:
2549 gcc_unreachable ();
2550
2551 case MEM_REF:
2552 {
2553 tree baseop = create_component_ref_by_pieces_1 (block, ref, operand,
2554 stmts);
2555 if (!baseop)
2556 return NULL_TREE;
2557 tree offset = currop->op0;
2558 if (TREE_CODE (baseop) == ADDR_EXPR
2559 && handled_component_p (TREE_OPERAND (baseop, 0)))
2560 {
2561 poly_int64 off;
2562 tree base;
2563 base = get_addr_base_and_unit_offset (TREE_OPERAND (baseop, 0),
2564 &off);
2565 gcc_assert (base);
2566 offset = int_const_binop (PLUS_EXPR, offset,
2567 build_int_cst (TREE_TYPE (offset),
2568 off));
2569 baseop = build_fold_addr_expr (base);
2570 }
2571 genop = build2 (MEM_REF, currop->type, baseop, offset);
2572 MR_DEPENDENCE_CLIQUE (genop) = currop->clique;
2573 MR_DEPENDENCE_BASE (genop) = currop->base;
2574 REF_REVERSE_STORAGE_ORDER (genop) = currop->reverse;
2575 return genop;
2576 }
2577
2578 case TARGET_MEM_REF:
2579 {
2580 tree genop0 = NULL_TREE, genop1 = NULL_TREE;
2581 vn_reference_op_t nextop = &ref->operands[(*operand)++];
2582 tree baseop = create_component_ref_by_pieces_1 (block, ref, operand,
2583 stmts);
2584 if (!baseop)
2585 return NULL_TREE;
2586 if (currop->op0)
2587 {
2588 genop0 = find_or_generate_expression (block, currop->op0, stmts);
2589 if (!genop0)
2590 return NULL_TREE;
2591 }
2592 if (nextop->op0)
2593 {
2594 genop1 = find_or_generate_expression (block, nextop->op0, stmts);
2595 if (!genop1)
2596 return NULL_TREE;
2597 }
2598 genop = build5 (TARGET_MEM_REF, currop->type,
2599 baseop, currop->op2, genop0, currop->op1, genop1);
2600
2601 MR_DEPENDENCE_CLIQUE (genop) = currop->clique;
2602 MR_DEPENDENCE_BASE (genop) = currop->base;
2603 return genop;
2604 }
2605
2606 case ADDR_EXPR:
2607 if (currop->op0)
2608 {
2609 gcc_assert (is_gimple_min_invariant (currop->op0));
2610 return currop->op0;
2611 }
2612 /* Fallthrough. */
2613 case REALPART_EXPR:
2614 case IMAGPART_EXPR:
2615 case VIEW_CONVERT_EXPR:
2616 {
2617 tree genop0 = create_component_ref_by_pieces_1 (block, ref, operand,
2618 stmts);
2619 if (!genop0)
2620 return NULL_TREE;
2621 return fold_build1 (currop->opcode, currop->type, genop0);
2622 }
2623
2624 case WITH_SIZE_EXPR:
2625 {
2626 tree genop0 = create_component_ref_by_pieces_1 (block, ref, operand,
2627 stmts);
2628 if (!genop0)
2629 return NULL_TREE;
2630 tree genop1 = find_or_generate_expression (block, currop->op0, stmts);
2631 if (!genop1)
2632 return NULL_TREE;
2633 return fold_build2 (currop->opcode, currop->type, genop0, genop1);
2634 }
2635
2636 case BIT_FIELD_REF:
2637 {
2638 tree genop0 = create_component_ref_by_pieces_1 (block, ref, operand,
2639 stmts);
2640 if (!genop0)
2641 return NULL_TREE;
2642 tree op1 = currop->op0;
2643 tree op2 = currop->op1;
2644 tree t = build3 (BIT_FIELD_REF, currop->type, genop0, op1, op2);
2645 REF_REVERSE_STORAGE_ORDER (t) = currop->reverse;
2646 return fold (t);
2647 }
2648
2649 /* For array ref vn_reference_op's, operand 1 of the array ref
2650 is op0 of the reference op and operand 3 of the array ref is
2651 op1. */
2652 case ARRAY_RANGE_REF:
2653 case ARRAY_REF:
2654 {
2655 tree genop0;
2656 tree genop1 = currop->op0;
2657 tree genop2 = currop->op1;
2658 tree genop3 = currop->op2;
2659 genop0 = create_component_ref_by_pieces_1 (block, ref, operand,
2660 stmts);
2661 if (!genop0)
2662 return NULL_TREE;
2663 genop1 = find_or_generate_expression (block, genop1, stmts);
2664 if (!genop1)
2665 return NULL_TREE;
2666 if (genop2)
2667 {
2668 tree domain_type = TYPE_DOMAIN (TREE_TYPE (genop0));
2669 /* Drop zero minimum index if redundant. */
2670 if (integer_zerop (genop2)
2671 && (!domain_type
2672 || integer_zerop (TYPE_MIN_VALUE (domain_type))))
2673 genop2 = NULL_TREE;
2674 else
2675 {
2676 genop2 = find_or_generate_expression (block, genop2, stmts);
2677 if (!genop2)
2678 return NULL_TREE;
2679 }
2680 }
2681 if (genop3)
2682 {
2683 tree elmt_type = TREE_TYPE (TREE_TYPE (genop0));
2684 /* We can't always put a size in units of the element alignment
2685 here as the element alignment may be not visible. See
2686 PR43783. Simply drop the element size for constant
2687 sizes. */
2688 if (TREE_CODE (genop3) == INTEGER_CST
2689 && TREE_CODE (TYPE_SIZE_UNIT (elmt_type)) == INTEGER_CST
2690 && wi::eq_p (wi::to_offset (TYPE_SIZE_UNIT (elmt_type)),
2691 (wi::to_offset (genop3)
2692 * vn_ref_op_align_unit (currop))))
2693 genop3 = NULL_TREE;
2694 else
2695 {
2696 genop3 = find_or_generate_expression (block, genop3, stmts);
2697 if (!genop3)
2698 return NULL_TREE;
2699 }
2700 }
2701 return build4 (currop->opcode, currop->type, genop0, genop1,
2702 genop2, genop3);
2703 }
2704 case COMPONENT_REF:
2705 {
2706 tree op0;
2707 tree op1;
2708 tree genop2 = currop->op1;
2709 op0 = create_component_ref_by_pieces_1 (block, ref, operand, stmts);
2710 if (!op0)
2711 return NULL_TREE;
2712 /* op1 should be a FIELD_DECL, which are represented by themselves. */
2713 op1 = currop->op0;
2714 if (genop2)
2715 {
2716 genop2 = find_or_generate_expression (block, genop2, stmts);
2717 if (!genop2)
2718 return NULL_TREE;
2719 }
2720 return fold_build3 (COMPONENT_REF, TREE_TYPE (op1), op0, op1, genop2);
2721 }
2722
2723 case SSA_NAME:
2724 {
2725 genop = find_or_generate_expression (block, currop->op0, stmts);
2726 return genop;
2727 }
2728 case STRING_CST:
2729 case INTEGER_CST:
2730 case POLY_INT_CST:
2731 case COMPLEX_CST:
2732 case VECTOR_CST:
2733 case REAL_CST:
2734 case CONSTRUCTOR:
2735 case VAR_DECL:
2736 case PARM_DECL:
2737 case CONST_DECL:
2738 case RESULT_DECL:
2739 case FUNCTION_DECL:
2740 return currop->op0;
2741
2742 default:
2743 gcc_unreachable ();
2744 }
2745 }
2746
2747 /* For COMPONENT_REF's and ARRAY_REF's, we can't have any intermediates for the
2748 COMPONENT_REF or MEM_REF or ARRAY_REF portion, because we'd end up with
2749 trying to rename aggregates into ssa form directly, which is a no no.
2750
2751 Thus, this routine doesn't create temporaries, it just builds a
2752 single access expression for the array, calling
2753 find_or_generate_expression to build the innermost pieces.
2754
2755 This function is a subroutine of create_expression_by_pieces, and
2756 should not be called on it's own unless you really know what you
2757 are doing. */
2758
2759 static tree
create_component_ref_by_pieces(basic_block block,vn_reference_t ref,gimple_seq * stmts)2760 create_component_ref_by_pieces (basic_block block, vn_reference_t ref,
2761 gimple_seq *stmts)
2762 {
2763 unsigned int op = 0;
2764 return create_component_ref_by_pieces_1 (block, ref, &op, stmts);
2765 }
2766
2767 /* Find a simple leader for an expression, or generate one using
2768 create_expression_by_pieces from a NARY expression for the value.
2769 BLOCK is the basic_block we are looking for leaders in.
2770 OP is the tree expression to find a leader for or generate.
2771 Returns the leader or NULL_TREE on failure. */
2772
2773 static tree
find_or_generate_expression(basic_block block,tree op,gimple_seq * stmts)2774 find_or_generate_expression (basic_block block, tree op, gimple_seq *stmts)
2775 {
2776 /* Constants are always leaders. */
2777 if (is_gimple_min_invariant (op))
2778 return op;
2779
2780 gcc_assert (TREE_CODE (op) == SSA_NAME);
2781 vn_ssa_aux_t info = VN_INFO (op);
2782 unsigned int lookfor = info->value_id;
2783 if (value_id_constant_p (lookfor))
2784 return info->valnum;
2785
2786 pre_expr leader = bitmap_find_leader (AVAIL_OUT (block), lookfor);
2787 if (leader)
2788 {
2789 if (leader->kind == NAME)
2790 return PRE_EXPR_NAME (leader);
2791 else if (leader->kind == CONSTANT)
2792 return PRE_EXPR_CONSTANT (leader);
2793
2794 /* Defer. */
2795 return NULL_TREE;
2796 }
2797 gcc_assert (!value_id_constant_p (lookfor));
2798
2799 /* It must be a complex expression, so generate it recursively. Note
2800 that this is only necessary to handle gcc.dg/tree-ssa/ssa-pre28.c
2801 where the insert algorithm fails to insert a required expression. */
2802 bitmap exprset = value_expressions[lookfor];
2803 bitmap_iterator bi;
2804 unsigned int i;
2805 EXECUTE_IF_SET_IN_BITMAP (exprset, 0, i, bi)
2806 {
2807 pre_expr temp = expression_for_id (i);
2808 /* We cannot insert random REFERENCE expressions at arbitrary
2809 places. We can insert NARYs which eventually re-materializes
2810 its operand values. */
2811 if (temp->kind == NARY)
2812 return create_expression_by_pieces (block, temp, stmts,
2813 TREE_TYPE (op));
2814 }
2815
2816 /* Defer. */
2817 return NULL_TREE;
2818 }
2819
2820 /* Create an expression in pieces, so that we can handle very complex
2821 expressions that may be ANTIC, but not necessary GIMPLE.
2822 BLOCK is the basic block the expression will be inserted into,
2823 EXPR is the expression to insert (in value form)
2824 STMTS is a statement list to append the necessary insertions into.
2825
2826 This function will die if we hit some value that shouldn't be
2827 ANTIC but is (IE there is no leader for it, or its components).
2828 The function returns NULL_TREE in case a different antic expression
2829 has to be inserted first.
2830 This function may also generate expressions that are themselves
2831 partially or fully redundant. Those that are will be either made
2832 fully redundant during the next iteration of insert (for partially
2833 redundant ones), or eliminated by eliminate (for fully redundant
2834 ones). */
2835
2836 static tree
create_expression_by_pieces(basic_block block,pre_expr expr,gimple_seq * stmts,tree type)2837 create_expression_by_pieces (basic_block block, pre_expr expr,
2838 gimple_seq *stmts, tree type)
2839 {
2840 tree name;
2841 tree folded;
2842 gimple_seq forced_stmts = NULL;
2843 unsigned int value_id;
2844 gimple_stmt_iterator gsi;
2845 tree exprtype = type ? type : get_expr_type (expr);
2846 pre_expr nameexpr;
2847 gassign *newstmt;
2848
2849 switch (expr->kind)
2850 {
2851 /* We may hit the NAME/CONSTANT case if we have to convert types
2852 that value numbering saw through. */
2853 case NAME:
2854 folded = PRE_EXPR_NAME (expr);
2855 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (folded))
2856 return NULL_TREE;
2857 if (useless_type_conversion_p (exprtype, TREE_TYPE (folded)))
2858 return folded;
2859 break;
2860 case CONSTANT:
2861 {
2862 folded = PRE_EXPR_CONSTANT (expr);
2863 tree tem = fold_convert (exprtype, folded);
2864 if (is_gimple_min_invariant (tem))
2865 return tem;
2866 break;
2867 }
2868 case REFERENCE:
2869 if (PRE_EXPR_REFERENCE (expr)->operands[0].opcode == CALL_EXPR)
2870 {
2871 vn_reference_t ref = PRE_EXPR_REFERENCE (expr);
2872 unsigned int operand = 1;
2873 vn_reference_op_t currop = &ref->operands[0];
2874 tree sc = NULL_TREE;
2875 tree fn = NULL_TREE;
2876 if (currop->op0)
2877 {
2878 fn = find_or_generate_expression (block, currop->op0, stmts);
2879 if (!fn)
2880 return NULL_TREE;
2881 }
2882 if (currop->op1)
2883 {
2884 sc = find_or_generate_expression (block, currop->op1, stmts);
2885 if (!sc)
2886 return NULL_TREE;
2887 }
2888 auto_vec<tree> args (ref->operands.length () - 1);
2889 while (operand < ref->operands.length ())
2890 {
2891 tree arg = create_component_ref_by_pieces_1 (block, ref,
2892 &operand, stmts);
2893 if (!arg)
2894 return NULL_TREE;
2895 args.quick_push (arg);
2896 }
2897 gcall *call;
2898 if (currop->op0)
2899 {
2900 call = gimple_build_call_vec (fn, args);
2901 gimple_call_set_fntype (call, currop->type);
2902 }
2903 else
2904 call = gimple_build_call_internal_vec ((internal_fn)currop->clique,
2905 args);
2906 gimple_set_location (call, expr->loc);
2907 if (sc)
2908 gimple_call_set_chain (call, sc);
2909 tree forcedname = make_ssa_name (ref->type);
2910 gimple_call_set_lhs (call, forcedname);
2911 /* There's no CCP pass after PRE which would re-compute alignment
2912 information so make sure we re-materialize this here. */
2913 if (gimple_call_builtin_p (call, BUILT_IN_ASSUME_ALIGNED)
2914 && args.length () - 2 <= 1
2915 && tree_fits_uhwi_p (args[1])
2916 && (args.length () != 3 || tree_fits_uhwi_p (args[2])))
2917 {
2918 unsigned HOST_WIDE_INT halign = tree_to_uhwi (args[1]);
2919 unsigned HOST_WIDE_INT hmisalign
2920 = args.length () == 3 ? tree_to_uhwi (args[2]) : 0;
2921 if ((halign & (halign - 1)) == 0
2922 && (hmisalign & ~(halign - 1)) == 0
2923 && (unsigned int)halign != 0)
2924 set_ptr_info_alignment (get_ptr_info (forcedname),
2925 halign, hmisalign);
2926 }
2927 gimple_set_vuse (call, BB_LIVE_VOP_ON_EXIT (block));
2928 gimple_seq_add_stmt_without_update (&forced_stmts, call);
2929 folded = forcedname;
2930 }
2931 else
2932 {
2933 folded = create_component_ref_by_pieces (block,
2934 PRE_EXPR_REFERENCE (expr),
2935 stmts);
2936 if (!folded)
2937 return NULL_TREE;
2938 name = make_temp_ssa_name (exprtype, NULL, "pretmp");
2939 newstmt = gimple_build_assign (name, folded);
2940 gimple_set_location (newstmt, expr->loc);
2941 gimple_seq_add_stmt_without_update (&forced_stmts, newstmt);
2942 gimple_set_vuse (newstmt, BB_LIVE_VOP_ON_EXIT (block));
2943 folded = name;
2944 }
2945 break;
2946 case NARY:
2947 {
2948 vn_nary_op_t nary = PRE_EXPR_NARY (expr);
2949 tree *genop = XALLOCAVEC (tree, nary->length);
2950 unsigned i;
2951 for (i = 0; i < nary->length; ++i)
2952 {
2953 genop[i] = find_or_generate_expression (block, nary->op[i], stmts);
2954 if (!genop[i])
2955 return NULL_TREE;
2956 /* Ensure genop[] is properly typed for POINTER_PLUS_EXPR. It
2957 may have conversions stripped. */
2958 if (nary->opcode == POINTER_PLUS_EXPR)
2959 {
2960 if (i == 0)
2961 genop[i] = gimple_convert (&forced_stmts,
2962 nary->type, genop[i]);
2963 else if (i == 1)
2964 genop[i] = gimple_convert (&forced_stmts,
2965 sizetype, genop[i]);
2966 }
2967 else
2968 genop[i] = gimple_convert (&forced_stmts,
2969 TREE_TYPE (nary->op[i]), genop[i]);
2970 }
2971 if (nary->opcode == CONSTRUCTOR)
2972 {
2973 vec<constructor_elt, va_gc> *elts = NULL;
2974 for (i = 0; i < nary->length; ++i)
2975 CONSTRUCTOR_APPEND_ELT (elts, NULL_TREE, genop[i]);
2976 folded = build_constructor (nary->type, elts);
2977 name = make_temp_ssa_name (exprtype, NULL, "pretmp");
2978 newstmt = gimple_build_assign (name, folded);
2979 gimple_set_location (newstmt, expr->loc);
2980 gimple_seq_add_stmt_without_update (&forced_stmts, newstmt);
2981 folded = name;
2982 }
2983 else
2984 {
2985 switch (nary->length)
2986 {
2987 case 1:
2988 folded = gimple_build (&forced_stmts, expr->loc,
2989 nary->opcode, nary->type, genop[0]);
2990 break;
2991 case 2:
2992 folded = gimple_build (&forced_stmts, expr->loc, nary->opcode,
2993 nary->type, genop[0], genop[1]);
2994 break;
2995 case 3:
2996 folded = gimple_build (&forced_stmts, expr->loc, nary->opcode,
2997 nary->type, genop[0], genop[1],
2998 genop[2]);
2999 break;
3000 default:
3001 gcc_unreachable ();
3002 }
3003 }
3004 }
3005 break;
3006 default:
3007 gcc_unreachable ();
3008 }
3009
3010 folded = gimple_convert (&forced_stmts, exprtype, folded);
3011
3012 /* If there is nothing to insert, return the simplified result. */
3013 if (gimple_seq_empty_p (forced_stmts))
3014 return folded;
3015 /* If we simplified to a constant return it and discard eventually
3016 built stmts. */
3017 if (is_gimple_min_invariant (folded))
3018 {
3019 gimple_seq_discard (forced_stmts);
3020 return folded;
3021 }
3022 /* Likewise if we simplified to sth not queued for insertion. */
3023 bool found = false;
3024 gsi = gsi_last (forced_stmts);
3025 for (; !gsi_end_p (gsi); gsi_prev (&gsi))
3026 {
3027 gimple *stmt = gsi_stmt (gsi);
3028 tree forcedname = gimple_get_lhs (stmt);
3029 if (forcedname == folded)
3030 {
3031 found = true;
3032 break;
3033 }
3034 }
3035 if (! found)
3036 {
3037 gimple_seq_discard (forced_stmts);
3038 return folded;
3039 }
3040 gcc_assert (TREE_CODE (folded) == SSA_NAME);
3041
3042 /* If we have any intermediate expressions to the value sets, add them
3043 to the value sets and chain them in the instruction stream. */
3044 if (forced_stmts)
3045 {
3046 gsi = gsi_start (forced_stmts);
3047 for (; !gsi_end_p (gsi); gsi_next (&gsi))
3048 {
3049 gimple *stmt = gsi_stmt (gsi);
3050 tree forcedname = gimple_get_lhs (stmt);
3051 pre_expr nameexpr;
3052
3053 if (forcedname != folded)
3054 {
3055 vn_ssa_aux_t vn_info = VN_INFO (forcedname);
3056 vn_info->valnum = forcedname;
3057 vn_info->value_id = get_next_value_id ();
3058 nameexpr = get_or_alloc_expr_for_name (forcedname);
3059 add_to_value (vn_info->value_id, nameexpr);
3060 if (NEW_SETS (block))
3061 bitmap_value_replace_in_set (NEW_SETS (block), nameexpr);
3062 bitmap_value_replace_in_set (AVAIL_OUT (block), nameexpr);
3063 }
3064
3065 bitmap_set_bit (inserted_exprs, SSA_NAME_VERSION (forcedname));
3066 }
3067 gimple_seq_add_seq (stmts, forced_stmts);
3068 }
3069
3070 name = folded;
3071
3072 /* Fold the last statement. */
3073 gsi = gsi_last (*stmts);
3074 if (fold_stmt_inplace (&gsi))
3075 update_stmt (gsi_stmt (gsi));
3076
3077 /* Add a value number to the temporary.
3078 The value may already exist in either NEW_SETS, or AVAIL_OUT, because
3079 we are creating the expression by pieces, and this particular piece of
3080 the expression may have been represented. There is no harm in replacing
3081 here. */
3082 value_id = get_expr_value_id (expr);
3083 vn_ssa_aux_t vn_info = VN_INFO (name);
3084 vn_info->value_id = value_id;
3085 vn_info->valnum = vn_valnum_from_value_id (value_id);
3086 if (vn_info->valnum == NULL_TREE)
3087 vn_info->valnum = name;
3088 gcc_assert (vn_info->valnum != NULL_TREE);
3089 nameexpr = get_or_alloc_expr_for_name (name);
3090 add_to_value (value_id, nameexpr);
3091 if (NEW_SETS (block))
3092 bitmap_value_replace_in_set (NEW_SETS (block), nameexpr);
3093 bitmap_value_replace_in_set (AVAIL_OUT (block), nameexpr);
3094
3095 pre_stats.insertions++;
3096 if (dump_file && (dump_flags & TDF_DETAILS))
3097 {
3098 fprintf (dump_file, "Inserted ");
3099 print_gimple_stmt (dump_file, gsi_stmt (gsi_last (*stmts)), 0);
3100 fprintf (dump_file, " in predecessor %d (%04d)\n",
3101 block->index, value_id);
3102 }
3103
3104 return name;
3105 }
3106
3107
3108 /* Insert the to-be-made-available values of expression EXPRNUM for each
3109 predecessor, stored in AVAIL, into the predecessors of BLOCK, and
3110 merge the result with a phi node, given the same value number as
3111 NODE. Return true if we have inserted new stuff. */
3112
3113 static bool
insert_into_preds_of_block(basic_block block,unsigned int exprnum,vec<pre_expr> & avail)3114 insert_into_preds_of_block (basic_block block, unsigned int exprnum,
3115 vec<pre_expr> &avail)
3116 {
3117 pre_expr expr = expression_for_id (exprnum);
3118 pre_expr newphi;
3119 unsigned int val = get_expr_value_id (expr);
3120 edge pred;
3121 bool insertions = false;
3122 bool nophi = false;
3123 basic_block bprime;
3124 pre_expr eprime;
3125 edge_iterator ei;
3126 tree type = get_expr_type (expr);
3127 tree temp;
3128 gphi *phi;
3129
3130 /* Make sure we aren't creating an induction variable. */
3131 if (bb_loop_depth (block) > 0 && EDGE_COUNT (block->preds) == 2)
3132 {
3133 bool firstinsideloop = false;
3134 bool secondinsideloop = false;
3135 firstinsideloop = flow_bb_inside_loop_p (block->loop_father,
3136 EDGE_PRED (block, 0)->src);
3137 secondinsideloop = flow_bb_inside_loop_p (block->loop_father,
3138 EDGE_PRED (block, 1)->src);
3139 /* Induction variables only have one edge inside the loop. */
3140 if ((firstinsideloop ^ secondinsideloop)
3141 && expr->kind != REFERENCE)
3142 {
3143 if (dump_file && (dump_flags & TDF_DETAILS))
3144 fprintf (dump_file, "Skipping insertion of phi for partial "
3145 "redundancy: Looks like an induction variable\n");
3146 nophi = true;
3147 }
3148 }
3149
3150 /* Make the necessary insertions. */
3151 FOR_EACH_EDGE (pred, ei, block->preds)
3152 {
3153 /* When we are not inserting a PHI node do not bother inserting
3154 into places that do not dominate the anticipated computations. */
3155 if (nophi && !dominated_by_p (CDI_DOMINATORS, block, pred->src))
3156 continue;
3157 gimple_seq stmts = NULL;
3158 tree builtexpr;
3159 bprime = pred->src;
3160 eprime = avail[pred->dest_idx];
3161 builtexpr = create_expression_by_pieces (bprime, eprime,
3162 &stmts, type);
3163 gcc_assert (!(pred->flags & EDGE_ABNORMAL));
3164 if (!gimple_seq_empty_p (stmts))
3165 {
3166 basic_block new_bb = gsi_insert_seq_on_edge_immediate (pred, stmts);
3167 gcc_assert (! new_bb);
3168 insertions = true;
3169 }
3170 if (!builtexpr)
3171 {
3172 /* We cannot insert a PHI node if we failed to insert
3173 on one edge. */
3174 nophi = true;
3175 continue;
3176 }
3177 if (is_gimple_min_invariant (builtexpr))
3178 avail[pred->dest_idx] = get_or_alloc_expr_for_constant (builtexpr);
3179 else
3180 avail[pred->dest_idx] = get_or_alloc_expr_for_name (builtexpr);
3181 }
3182 /* If we didn't want a phi node, and we made insertions, we still have
3183 inserted new stuff, and thus return true. If we didn't want a phi node,
3184 and didn't make insertions, we haven't added anything new, so return
3185 false. */
3186 if (nophi && insertions)
3187 return true;
3188 else if (nophi && !insertions)
3189 return false;
3190
3191 /* Now build a phi for the new variable. */
3192 temp = make_temp_ssa_name (type, NULL, "prephitmp");
3193 phi = create_phi_node (temp, block);
3194
3195 vn_ssa_aux_t vn_info = VN_INFO (temp);
3196 vn_info->value_id = val;
3197 vn_info->valnum = vn_valnum_from_value_id (val);
3198 if (vn_info->valnum == NULL_TREE)
3199 vn_info->valnum = temp;
3200 bitmap_set_bit (inserted_exprs, SSA_NAME_VERSION (temp));
3201 FOR_EACH_EDGE (pred, ei, block->preds)
3202 {
3203 pre_expr ae = avail[pred->dest_idx];
3204 gcc_assert (get_expr_type (ae) == type
3205 || useless_type_conversion_p (type, get_expr_type (ae)));
3206 if (ae->kind == CONSTANT)
3207 add_phi_arg (phi, unshare_expr (PRE_EXPR_CONSTANT (ae)),
3208 pred, UNKNOWN_LOCATION);
3209 else
3210 add_phi_arg (phi, PRE_EXPR_NAME (ae), pred, UNKNOWN_LOCATION);
3211 }
3212
3213 newphi = get_or_alloc_expr_for_name (temp);
3214 add_to_value (val, newphi);
3215
3216 /* The value should *not* exist in PHI_GEN, or else we wouldn't be doing
3217 this insertion, since we test for the existence of this value in PHI_GEN
3218 before proceeding with the partial redundancy checks in insert_aux.
3219
3220 The value may exist in AVAIL_OUT, in particular, it could be represented
3221 by the expression we are trying to eliminate, in which case we want the
3222 replacement to occur. If it's not existing in AVAIL_OUT, we want it
3223 inserted there.
3224
3225 Similarly, to the PHI_GEN case, the value should not exist in NEW_SETS of
3226 this block, because if it did, it would have existed in our dominator's
3227 AVAIL_OUT, and would have been skipped due to the full redundancy check.
3228 */
3229
3230 bitmap_insert_into_set (PHI_GEN (block), newphi);
3231 bitmap_value_replace_in_set (AVAIL_OUT (block),
3232 newphi);
3233 if (NEW_SETS (block))
3234 bitmap_insert_into_set (NEW_SETS (block), newphi);
3235
3236 /* If we insert a PHI node for a conversion of another PHI node
3237 in the same basic-block try to preserve range information.
3238 This is important so that followup loop passes receive optimal
3239 number of iteration analysis results. See PR61743. */
3240 if (expr->kind == NARY
3241 && CONVERT_EXPR_CODE_P (expr->u.nary->opcode)
3242 && TREE_CODE (expr->u.nary->op[0]) == SSA_NAME
3243 && gimple_bb (SSA_NAME_DEF_STMT (expr->u.nary->op[0])) == block
3244 && INTEGRAL_TYPE_P (type)
3245 && INTEGRAL_TYPE_P (TREE_TYPE (expr->u.nary->op[0]))
3246 && (TYPE_PRECISION (type)
3247 >= TYPE_PRECISION (TREE_TYPE (expr->u.nary->op[0])))
3248 && SSA_NAME_RANGE_INFO (expr->u.nary->op[0]))
3249 {
3250 value_range r;
3251 if (get_range_query (cfun)->range_of_expr (r, expr->u.nary->op[0])
3252 && r.kind () == VR_RANGE
3253 && !wi::neg_p (r.lower_bound (), SIGNED)
3254 && !wi::neg_p (r.upper_bound (), SIGNED))
3255 /* Just handle extension and sign-changes of all-positive ranges. */
3256 set_range_info (temp, VR_RANGE,
3257 wide_int_storage::from (r.lower_bound (),
3258 TYPE_PRECISION (type),
3259 TYPE_SIGN (type)),
3260 wide_int_storage::from (r.upper_bound (),
3261 TYPE_PRECISION (type),
3262 TYPE_SIGN (type)));
3263 }
3264
3265 if (dump_file && (dump_flags & TDF_DETAILS))
3266 {
3267 fprintf (dump_file, "Created phi ");
3268 print_gimple_stmt (dump_file, phi, 0);
3269 fprintf (dump_file, " in block %d (%04d)\n", block->index, val);
3270 }
3271 pre_stats.phis++;
3272 return true;
3273 }
3274
3275
3276
3277 /* Perform insertion of partially redundant or hoistable values.
3278 For BLOCK, do the following:
3279 1. Propagate the NEW_SETS of the dominator into the current block.
3280 If the block has multiple predecessors,
3281 2a. Iterate over the ANTIC expressions for the block to see if
3282 any of them are partially redundant.
3283 2b. If so, insert them into the necessary predecessors to make
3284 the expression fully redundant.
3285 2c. Insert a new PHI merging the values of the predecessors.
3286 2d. Insert the new PHI, and the new expressions, into the
3287 NEW_SETS set.
3288 If the block has multiple successors,
3289 3a. Iterate over the ANTIC values for the block to see if
3290 any of them are good candidates for hoisting.
3291 3b. If so, insert expressions computing the values in BLOCK,
3292 and add the new expressions into the NEW_SETS set.
3293 4. Recursively call ourselves on the dominator children of BLOCK.
3294
3295 Steps 1, 2a, and 4 are done by insert_aux. 2b, 2c and 2d are done by
3296 do_pre_regular_insertion and do_partial_insertion. 3a and 3b are
3297 done in do_hoist_insertion.
3298 */
3299
3300 static bool
do_pre_regular_insertion(basic_block block,basic_block dom,vec<pre_expr> exprs)3301 do_pre_regular_insertion (basic_block block, basic_block dom,
3302 vec<pre_expr> exprs)
3303 {
3304 bool new_stuff = false;
3305 pre_expr expr;
3306 auto_vec<pre_expr, 2> avail;
3307 int i;
3308
3309 avail.safe_grow (EDGE_COUNT (block->preds), true);
3310
3311 FOR_EACH_VEC_ELT (exprs, i, expr)
3312 {
3313 if (expr->kind == NARY
3314 || expr->kind == REFERENCE)
3315 {
3316 unsigned int val;
3317 bool by_some = false;
3318 bool cant_insert = false;
3319 bool all_same = true;
3320 pre_expr first_s = NULL;
3321 edge pred;
3322 basic_block bprime;
3323 pre_expr eprime = NULL;
3324 edge_iterator ei;
3325 pre_expr edoubleprime = NULL;
3326 bool do_insertion = false;
3327
3328 val = get_expr_value_id (expr);
3329 if (bitmap_set_contains_value (PHI_GEN (block), val))
3330 continue;
3331 if (bitmap_set_contains_value (AVAIL_OUT (dom), val))
3332 {
3333 if (dump_file && (dump_flags & TDF_DETAILS))
3334 {
3335 fprintf (dump_file, "Found fully redundant value: ");
3336 print_pre_expr (dump_file, expr);
3337 fprintf (dump_file, "\n");
3338 }
3339 continue;
3340 }
3341
3342 FOR_EACH_EDGE (pred, ei, block->preds)
3343 {
3344 unsigned int vprime;
3345
3346 /* We should never run insertion for the exit block
3347 and so not come across fake pred edges. */
3348 gcc_assert (!(pred->flags & EDGE_FAKE));
3349 bprime = pred->src;
3350 /* We are looking at ANTIC_OUT of bprime. */
3351 eprime = phi_translate (NULL, expr, ANTIC_IN (block), NULL, pred);
3352
3353 /* eprime will generally only be NULL if the
3354 value of the expression, translated
3355 through the PHI for this predecessor, is
3356 undefined. If that is the case, we can't
3357 make the expression fully redundant,
3358 because its value is undefined along a
3359 predecessor path. We can thus break out
3360 early because it doesn't matter what the
3361 rest of the results are. */
3362 if (eprime == NULL)
3363 {
3364 avail[pred->dest_idx] = NULL;
3365 cant_insert = true;
3366 break;
3367 }
3368
3369 vprime = get_expr_value_id (eprime);
3370 edoubleprime = bitmap_find_leader (AVAIL_OUT (bprime),
3371 vprime);
3372 if (edoubleprime == NULL)
3373 {
3374 avail[pred->dest_idx] = eprime;
3375 all_same = false;
3376 }
3377 else
3378 {
3379 avail[pred->dest_idx] = edoubleprime;
3380 by_some = true;
3381 /* We want to perform insertions to remove a redundancy on
3382 a path in the CFG we want to optimize for speed. */
3383 if (optimize_edge_for_speed_p (pred))
3384 do_insertion = true;
3385 if (first_s == NULL)
3386 first_s = edoubleprime;
3387 else if (!pre_expr_d::equal (first_s, edoubleprime))
3388 all_same = false;
3389 }
3390 }
3391 /* If we can insert it, it's not the same value
3392 already existing along every predecessor, and
3393 it's defined by some predecessor, it is
3394 partially redundant. */
3395 if (!cant_insert && !all_same && by_some)
3396 {
3397 if (!do_insertion)
3398 {
3399 if (dump_file && (dump_flags & TDF_DETAILS))
3400 {
3401 fprintf (dump_file, "Skipping partial redundancy for "
3402 "expression ");
3403 print_pre_expr (dump_file, expr);
3404 fprintf (dump_file, " (%04d), no redundancy on to be "
3405 "optimized for speed edge\n", val);
3406 }
3407 }
3408 else if (dbg_cnt (treepre_insert))
3409 {
3410 if (dump_file && (dump_flags & TDF_DETAILS))
3411 {
3412 fprintf (dump_file, "Found partial redundancy for "
3413 "expression ");
3414 print_pre_expr (dump_file, expr);
3415 fprintf (dump_file, " (%04d)\n",
3416 get_expr_value_id (expr));
3417 }
3418 if (insert_into_preds_of_block (block,
3419 get_expression_id (expr),
3420 avail))
3421 new_stuff = true;
3422 }
3423 }
3424 /* If all edges produce the same value and that value is
3425 an invariant, then the PHI has the same value on all
3426 edges. Note this. */
3427 else if (!cant_insert
3428 && all_same
3429 && (edoubleprime->kind != NAME
3430 || !SSA_NAME_OCCURS_IN_ABNORMAL_PHI
3431 (PRE_EXPR_NAME (edoubleprime))))
3432 {
3433 gcc_assert (edoubleprime->kind == CONSTANT
3434 || edoubleprime->kind == NAME);
3435
3436 tree temp = make_temp_ssa_name (get_expr_type (expr),
3437 NULL, "pretmp");
3438 gassign *assign
3439 = gimple_build_assign (temp,
3440 edoubleprime->kind == CONSTANT ?
3441 PRE_EXPR_CONSTANT (edoubleprime) :
3442 PRE_EXPR_NAME (edoubleprime));
3443 gimple_stmt_iterator gsi = gsi_after_labels (block);
3444 gsi_insert_before (&gsi, assign, GSI_NEW_STMT);
3445
3446 vn_ssa_aux_t vn_info = VN_INFO (temp);
3447 vn_info->value_id = val;
3448 vn_info->valnum = vn_valnum_from_value_id (val);
3449 if (vn_info->valnum == NULL_TREE)
3450 vn_info->valnum = temp;
3451 bitmap_set_bit (inserted_exprs, SSA_NAME_VERSION (temp));
3452 pre_expr newe = get_or_alloc_expr_for_name (temp);
3453 add_to_value (val, newe);
3454 bitmap_value_replace_in_set (AVAIL_OUT (block), newe);
3455 bitmap_insert_into_set (NEW_SETS (block), newe);
3456 bitmap_insert_into_set (PHI_GEN (block), newe);
3457 }
3458 }
3459 }
3460
3461 return new_stuff;
3462 }
3463
3464
3465 /* Perform insertion for partially anticipatable expressions. There
3466 is only one case we will perform insertion for these. This case is
3467 if the expression is partially anticipatable, and fully available.
3468 In this case, we know that putting it earlier will enable us to
3469 remove the later computation. */
3470
3471 static bool
do_pre_partial_partial_insertion(basic_block block,basic_block dom,vec<pre_expr> exprs)3472 do_pre_partial_partial_insertion (basic_block block, basic_block dom,
3473 vec<pre_expr> exprs)
3474 {
3475 bool new_stuff = false;
3476 pre_expr expr;
3477 auto_vec<pre_expr, 2> avail;
3478 int i;
3479
3480 avail.safe_grow (EDGE_COUNT (block->preds), true);
3481
3482 FOR_EACH_VEC_ELT (exprs, i, expr)
3483 {
3484 if (expr->kind == NARY
3485 || expr->kind == REFERENCE)
3486 {
3487 unsigned int val;
3488 bool by_all = true;
3489 bool cant_insert = false;
3490 edge pred;
3491 basic_block bprime;
3492 pre_expr eprime = NULL;
3493 edge_iterator ei;
3494
3495 val = get_expr_value_id (expr);
3496 if (bitmap_set_contains_value (PHI_GEN (block), val))
3497 continue;
3498 if (bitmap_set_contains_value (AVAIL_OUT (dom), val))
3499 continue;
3500
3501 FOR_EACH_EDGE (pred, ei, block->preds)
3502 {
3503 unsigned int vprime;
3504 pre_expr edoubleprime;
3505
3506 /* We should never run insertion for the exit block
3507 and so not come across fake pred edges. */
3508 gcc_assert (!(pred->flags & EDGE_FAKE));
3509 bprime = pred->src;
3510 eprime = phi_translate (NULL, expr, ANTIC_IN (block),
3511 PA_IN (block), pred);
3512
3513 /* eprime will generally only be NULL if the
3514 value of the expression, translated
3515 through the PHI for this predecessor, is
3516 undefined. If that is the case, we can't
3517 make the expression fully redundant,
3518 because its value is undefined along a
3519 predecessor path. We can thus break out
3520 early because it doesn't matter what the
3521 rest of the results are. */
3522 if (eprime == NULL)
3523 {
3524 avail[pred->dest_idx] = NULL;
3525 cant_insert = true;
3526 break;
3527 }
3528
3529 vprime = get_expr_value_id (eprime);
3530 edoubleprime = bitmap_find_leader (AVAIL_OUT (bprime), vprime);
3531 avail[pred->dest_idx] = edoubleprime;
3532 if (edoubleprime == NULL)
3533 {
3534 by_all = false;
3535 break;
3536 }
3537 }
3538
3539 /* If we can insert it, it's not the same value
3540 already existing along every predecessor, and
3541 it's defined by some predecessor, it is
3542 partially redundant. */
3543 if (!cant_insert && by_all)
3544 {
3545 edge succ;
3546 bool do_insertion = false;
3547
3548 /* Insert only if we can remove a later expression on a path
3549 that we want to optimize for speed.
3550 The phi node that we will be inserting in BLOCK is not free,
3551 and inserting it for the sake of !optimize_for_speed successor
3552 may cause regressions on the speed path. */
3553 FOR_EACH_EDGE (succ, ei, block->succs)
3554 {
3555 if (bitmap_set_contains_value (PA_IN (succ->dest), val)
3556 || bitmap_set_contains_value (ANTIC_IN (succ->dest), val))
3557 {
3558 if (optimize_edge_for_speed_p (succ))
3559 do_insertion = true;
3560 }
3561 }
3562
3563 if (!do_insertion)
3564 {
3565 if (dump_file && (dump_flags & TDF_DETAILS))
3566 {
3567 fprintf (dump_file, "Skipping partial partial redundancy "
3568 "for expression ");
3569 print_pre_expr (dump_file, expr);
3570 fprintf (dump_file, " (%04d), not (partially) anticipated "
3571 "on any to be optimized for speed edges\n", val);
3572 }
3573 }
3574 else if (dbg_cnt (treepre_insert))
3575 {
3576 pre_stats.pa_insert++;
3577 if (dump_file && (dump_flags & TDF_DETAILS))
3578 {
3579 fprintf (dump_file, "Found partial partial redundancy "
3580 "for expression ");
3581 print_pre_expr (dump_file, expr);
3582 fprintf (dump_file, " (%04d)\n",
3583 get_expr_value_id (expr));
3584 }
3585 if (insert_into_preds_of_block (block,
3586 get_expression_id (expr),
3587 avail))
3588 new_stuff = true;
3589 }
3590 }
3591 }
3592 }
3593
3594 return new_stuff;
3595 }
3596
3597 /* Insert expressions in BLOCK to compute hoistable values up.
3598 Return TRUE if something was inserted, otherwise return FALSE.
3599 The caller has to make sure that BLOCK has at least two successors. */
3600
3601 static bool
do_hoist_insertion(basic_block block)3602 do_hoist_insertion (basic_block block)
3603 {
3604 edge e;
3605 edge_iterator ei;
3606 bool new_stuff = false;
3607 unsigned i;
3608 gimple_stmt_iterator last;
3609
3610 /* At least two successors, or else... */
3611 gcc_assert (EDGE_COUNT (block->succs) >= 2);
3612
3613 /* Check that all successors of BLOCK are dominated by block.
3614 We could use dominated_by_p() for this, but actually there is a much
3615 quicker check: any successor that is dominated by BLOCK can't have
3616 more than one predecessor edge. */
3617 FOR_EACH_EDGE (e, ei, block->succs)
3618 if (! single_pred_p (e->dest))
3619 return false;
3620
3621 /* Determine the insertion point. If we cannot safely insert before
3622 the last stmt if we'd have to, bail out. */
3623 last = gsi_last_bb (block);
3624 if (!gsi_end_p (last)
3625 && !is_ctrl_stmt (gsi_stmt (last))
3626 && stmt_ends_bb_p (gsi_stmt (last)))
3627 return false;
3628
3629 /* Compute the set of hoistable expressions from ANTIC_IN. First compute
3630 hoistable values. */
3631 bitmap_set hoistable_set;
3632
3633 /* A hoistable value must be in ANTIC_IN(block)
3634 but not in AVAIL_OUT(BLOCK). */
3635 bitmap_initialize (&hoistable_set.values, &grand_bitmap_obstack);
3636 bitmap_and_compl (&hoistable_set.values,
3637 &ANTIC_IN (block)->values, &AVAIL_OUT (block)->values);
3638
3639 /* Short-cut for a common case: hoistable_set is empty. */
3640 if (bitmap_empty_p (&hoistable_set.values))
3641 return false;
3642
3643 /* Compute which of the hoistable values is in AVAIL_OUT of
3644 at least one of the successors of BLOCK. */
3645 bitmap_head availout_in_some;
3646 bitmap_initialize (&availout_in_some, &grand_bitmap_obstack);
3647 FOR_EACH_EDGE (e, ei, block->succs)
3648 /* Do not consider expressions solely because their availability
3649 on loop exits. They'd be ANTIC-IN throughout the whole loop
3650 and thus effectively hoisted across loops by combination of
3651 PRE and hoisting. */
3652 if (! loop_exit_edge_p (block->loop_father, e))
3653 bitmap_ior_and_into (&availout_in_some, &hoistable_set.values,
3654 &AVAIL_OUT (e->dest)->values);
3655 bitmap_clear (&hoistable_set.values);
3656
3657 /* Short-cut for a common case: availout_in_some is empty. */
3658 if (bitmap_empty_p (&availout_in_some))
3659 return false;
3660
3661 /* Hack hoitable_set in-place so we can use sorted_array_from_bitmap_set. */
3662 bitmap_move (&hoistable_set.values, &availout_in_some);
3663 hoistable_set.expressions = ANTIC_IN (block)->expressions;
3664
3665 /* Now finally construct the topological-ordered expression set. */
3666 vec<pre_expr> exprs = sorted_array_from_bitmap_set (&hoistable_set);
3667
3668 bitmap_clear (&hoistable_set.values);
3669
3670 /* If there are candidate values for hoisting, insert expressions
3671 strategically to make the hoistable expressions fully redundant. */
3672 pre_expr expr;
3673 FOR_EACH_VEC_ELT (exprs, i, expr)
3674 {
3675 /* While we try to sort expressions topologically above the
3676 sorting doesn't work out perfectly. Catch expressions we
3677 already inserted. */
3678 unsigned int value_id = get_expr_value_id (expr);
3679 if (bitmap_set_contains_value (AVAIL_OUT (block), value_id))
3680 {
3681 if (dump_file && (dump_flags & TDF_DETAILS))
3682 {
3683 fprintf (dump_file,
3684 "Already inserted expression for ");
3685 print_pre_expr (dump_file, expr);
3686 fprintf (dump_file, " (%04d)\n", value_id);
3687 }
3688 continue;
3689 }
3690
3691 /* If we end up with a punned expression representation and this
3692 happens to be a float typed one give up - we can't know for
3693 sure whether all paths perform the floating-point load we are
3694 about to insert and on some targets this can cause correctness
3695 issues. See PR88240. */
3696 if (expr->kind == REFERENCE
3697 && PRE_EXPR_REFERENCE (expr)->punned
3698 && FLOAT_TYPE_P (get_expr_type (expr)))
3699 continue;
3700
3701 /* OK, we should hoist this value. Perform the transformation. */
3702 pre_stats.hoist_insert++;
3703 if (dump_file && (dump_flags & TDF_DETAILS))
3704 {
3705 fprintf (dump_file,
3706 "Inserting expression in block %d for code hoisting: ",
3707 block->index);
3708 print_pre_expr (dump_file, expr);
3709 fprintf (dump_file, " (%04d)\n", value_id);
3710 }
3711
3712 gimple_seq stmts = NULL;
3713 tree res = create_expression_by_pieces (block, expr, &stmts,
3714 get_expr_type (expr));
3715
3716 /* Do not return true if expression creation ultimately
3717 did not insert any statements. */
3718 if (gimple_seq_empty_p (stmts))
3719 res = NULL_TREE;
3720 else
3721 {
3722 if (gsi_end_p (last) || is_ctrl_stmt (gsi_stmt (last)))
3723 gsi_insert_seq_before (&last, stmts, GSI_SAME_STMT);
3724 else
3725 gsi_insert_seq_after (&last, stmts, GSI_NEW_STMT);
3726 }
3727
3728 /* Make sure to not return true if expression creation ultimately
3729 failed but also make sure to insert any stmts produced as they
3730 are tracked in inserted_exprs. */
3731 if (! res)
3732 continue;
3733
3734 new_stuff = true;
3735 }
3736
3737 exprs.release ();
3738
3739 return new_stuff;
3740 }
3741
3742 /* Perform insertion of partially redundant and hoistable values. */
3743
3744 static void
insert(void)3745 insert (void)
3746 {
3747 basic_block bb;
3748
3749 FOR_ALL_BB_FN (bb, cfun)
3750 NEW_SETS (bb) = bitmap_set_new ();
3751
3752 int *rpo = XNEWVEC (int, n_basic_blocks_for_fn (cfun));
3753 int *bb_rpo = XNEWVEC (int, last_basic_block_for_fn (cfun) + 1);
3754 int rpo_num = pre_and_rev_post_order_compute (NULL, rpo, false);
3755 for (int i = 0; i < rpo_num; ++i)
3756 bb_rpo[rpo[i]] = i;
3757
3758 int num_iterations = 0;
3759 bool changed;
3760 do
3761 {
3762 num_iterations++;
3763 if (dump_file && dump_flags & TDF_DETAILS)
3764 fprintf (dump_file, "Starting insert iteration %d\n", num_iterations);
3765
3766 changed = false;
3767 for (int idx = 0; idx < rpo_num; ++idx)
3768 {
3769 basic_block block = BASIC_BLOCK_FOR_FN (cfun, rpo[idx]);
3770 basic_block dom = get_immediate_dominator (CDI_DOMINATORS, block);
3771 if (dom)
3772 {
3773 unsigned i;
3774 bitmap_iterator bi;
3775 bitmap_set_t newset;
3776
3777 /* First, update the AVAIL_OUT set with anything we may have
3778 inserted higher up in the dominator tree. */
3779 newset = NEW_SETS (dom);
3780
3781 /* Note that we need to value_replace both NEW_SETS, and
3782 AVAIL_OUT. For both the case of NEW_SETS, the value may be
3783 represented by some non-simple expression here that we want
3784 to replace it with. */
3785 bool avail_out_changed = false;
3786 FOR_EACH_EXPR_ID_IN_SET (newset, i, bi)
3787 {
3788 pre_expr expr = expression_for_id (i);
3789 bitmap_value_replace_in_set (NEW_SETS (block), expr);
3790 avail_out_changed
3791 |= bitmap_value_replace_in_set (AVAIL_OUT (block), expr);
3792 }
3793 /* We need to iterate if AVAIL_OUT of an already processed
3794 block source changed. */
3795 if (avail_out_changed && !changed)
3796 {
3797 edge_iterator ei;
3798 edge e;
3799 FOR_EACH_EDGE (e, ei, block->succs)
3800 if (e->dest->index != EXIT_BLOCK
3801 && bb_rpo[e->dest->index] < idx)
3802 changed = true;
3803 }
3804
3805 /* Insert expressions for partial redundancies. */
3806 if (flag_tree_pre && !single_pred_p (block))
3807 {
3808 vec<pre_expr> exprs
3809 = sorted_array_from_bitmap_set (ANTIC_IN (block));
3810 /* Sorting is not perfect, iterate locally. */
3811 while (do_pre_regular_insertion (block, dom, exprs))
3812 ;
3813 exprs.release ();
3814 if (do_partial_partial)
3815 {
3816 exprs = sorted_array_from_bitmap_set (PA_IN (block));
3817 while (do_pre_partial_partial_insertion (block, dom,
3818 exprs))
3819 ;
3820 exprs.release ();
3821 }
3822 }
3823 }
3824 }
3825
3826 /* Clear the NEW sets before the next iteration. We have already
3827 fully propagated its contents. */
3828 if (changed)
3829 FOR_ALL_BB_FN (bb, cfun)
3830 bitmap_set_free (NEW_SETS (bb));
3831 }
3832 while (changed);
3833
3834 statistics_histogram_event (cfun, "insert iterations", num_iterations);
3835
3836 /* AVAIL_OUT is not needed after insertion so we don't have to
3837 propagate NEW_SETS from hoist insertion. */
3838 FOR_ALL_BB_FN (bb, cfun)
3839 {
3840 bitmap_set_free (NEW_SETS (bb));
3841 bitmap_set_pool.remove (NEW_SETS (bb));
3842 NEW_SETS (bb) = NULL;
3843 }
3844
3845 /* Insert expressions for hoisting. Do a backward walk here since
3846 inserting into BLOCK exposes new opportunities in its predecessors.
3847 Since PRE and hoist insertions can cause back-to-back iteration
3848 and we are interested in PRE insertion exposed hoisting opportunities
3849 but not in hoisting exposed PRE ones do hoist insertion only after
3850 PRE insertion iteration finished and do not iterate it. */
3851 if (flag_code_hoisting)
3852 for (int idx = rpo_num - 1; idx >= 0; --idx)
3853 {
3854 basic_block block = BASIC_BLOCK_FOR_FN (cfun, rpo[idx]);
3855 if (EDGE_COUNT (block->succs) >= 2)
3856 changed |= do_hoist_insertion (block);
3857 }
3858
3859 free (rpo);
3860 free (bb_rpo);
3861 }
3862
3863
3864 /* Compute the AVAIL set for all basic blocks.
3865
3866 This function performs value numbering of the statements in each basic
3867 block. The AVAIL sets are built from information we glean while doing
3868 this value numbering, since the AVAIL sets contain only one entry per
3869 value.
3870
3871 AVAIL_IN[BLOCK] = AVAIL_OUT[dom(BLOCK)].
3872 AVAIL_OUT[BLOCK] = AVAIL_IN[BLOCK] U PHI_GEN[BLOCK] U TMP_GEN[BLOCK]. */
3873
3874 static void
compute_avail(function * fun)3875 compute_avail (function *fun)
3876 {
3877
3878 basic_block block, son;
3879 basic_block *worklist;
3880 size_t sp = 0;
3881 unsigned i;
3882 tree name;
3883
3884 /* We pretend that default definitions are defined in the entry block.
3885 This includes function arguments and the static chain decl. */
3886 FOR_EACH_SSA_NAME (i, name, fun)
3887 {
3888 pre_expr e;
3889 if (!SSA_NAME_IS_DEFAULT_DEF (name)
3890 || has_zero_uses (name)
3891 || virtual_operand_p (name))
3892 continue;
3893
3894 e = get_or_alloc_expr_for_name (name);
3895 add_to_value (get_expr_value_id (e), e);
3896 bitmap_insert_into_set (TMP_GEN (ENTRY_BLOCK_PTR_FOR_FN (fun)), e);
3897 bitmap_value_insert_into_set (AVAIL_OUT (ENTRY_BLOCK_PTR_FOR_FN (fun)),
3898 e);
3899 }
3900
3901 if (dump_file && (dump_flags & TDF_DETAILS))
3902 {
3903 print_bitmap_set (dump_file, TMP_GEN (ENTRY_BLOCK_PTR_FOR_FN (fun)),
3904 "tmp_gen", ENTRY_BLOCK);
3905 print_bitmap_set (dump_file, AVAIL_OUT (ENTRY_BLOCK_PTR_FOR_FN (fun)),
3906 "avail_out", ENTRY_BLOCK);
3907 }
3908
3909 /* Allocate the worklist. */
3910 worklist = XNEWVEC (basic_block, n_basic_blocks_for_fn (fun));
3911
3912 /* Seed the algorithm by putting the dominator children of the entry
3913 block on the worklist. */
3914 for (son = first_dom_son (CDI_DOMINATORS, ENTRY_BLOCK_PTR_FOR_FN (fun));
3915 son;
3916 son = next_dom_son (CDI_DOMINATORS, son))
3917 worklist[sp++] = son;
3918
3919 BB_LIVE_VOP_ON_EXIT (ENTRY_BLOCK_PTR_FOR_FN (fun))
3920 = ssa_default_def (fun, gimple_vop (fun));
3921
3922 /* Loop until the worklist is empty. */
3923 while (sp)
3924 {
3925 gimple *stmt;
3926 basic_block dom;
3927
3928 /* Pick a block from the worklist. */
3929 block = worklist[--sp];
3930 vn_context_bb = block;
3931
3932 /* Initially, the set of available values in BLOCK is that of
3933 its immediate dominator. */
3934 dom = get_immediate_dominator (CDI_DOMINATORS, block);
3935 if (dom)
3936 {
3937 bitmap_set_copy (AVAIL_OUT (block), AVAIL_OUT (dom));
3938 BB_LIVE_VOP_ON_EXIT (block) = BB_LIVE_VOP_ON_EXIT (dom);
3939 }
3940
3941 /* Generate values for PHI nodes. */
3942 for (gphi_iterator gsi = gsi_start_phis (block); !gsi_end_p (gsi);
3943 gsi_next (&gsi))
3944 {
3945 tree result = gimple_phi_result (gsi.phi ());
3946
3947 /* We have no need for virtual phis, as they don't represent
3948 actual computations. */
3949 if (virtual_operand_p (result))
3950 {
3951 BB_LIVE_VOP_ON_EXIT (block) = result;
3952 continue;
3953 }
3954
3955 pre_expr e = get_or_alloc_expr_for_name (result);
3956 add_to_value (get_expr_value_id (e), e);
3957 bitmap_value_insert_into_set (AVAIL_OUT (block), e);
3958 bitmap_insert_into_set (PHI_GEN (block), e);
3959 }
3960
3961 BB_MAY_NOTRETURN (block) = 0;
3962
3963 /* Now compute value numbers and populate value sets with all
3964 the expressions computed in BLOCK. */
3965 bool set_bb_may_notreturn = false;
3966 for (gimple_stmt_iterator gsi = gsi_start_bb (block); !gsi_end_p (gsi);
3967 gsi_next (&gsi))
3968 {
3969 ssa_op_iter iter;
3970 tree op;
3971
3972 stmt = gsi_stmt (gsi);
3973
3974 if (set_bb_may_notreturn)
3975 {
3976 BB_MAY_NOTRETURN (block) = 1;
3977 set_bb_may_notreturn = false;
3978 }
3979
3980 /* Cache whether the basic-block has any non-visible side-effect
3981 or control flow.
3982 If this isn't a call or it is the last stmt in the
3983 basic-block then the CFG represents things correctly. */
3984 if (is_gimple_call (stmt) && !stmt_ends_bb_p (stmt))
3985 {
3986 /* Non-looping const functions always return normally.
3987 Otherwise the call might not return or have side-effects
3988 that forbids hoisting possibly trapping expressions
3989 before it. */
3990 int flags = gimple_call_flags (stmt);
3991 if (!(flags & (ECF_CONST|ECF_PURE))
3992 || (flags & ECF_LOOPING_CONST_OR_PURE)
3993 || stmt_can_throw_external (fun, stmt))
3994 /* Defer setting of BB_MAY_NOTRETURN to avoid it
3995 influencing the processing of the call itself. */
3996 set_bb_may_notreturn = true;
3997 }
3998
3999 FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_DEF)
4000 {
4001 pre_expr e = get_or_alloc_expr_for_name (op);
4002 add_to_value (get_expr_value_id (e), e);
4003 bitmap_insert_into_set (TMP_GEN (block), e);
4004 bitmap_value_insert_into_set (AVAIL_OUT (block), e);
4005 }
4006
4007 if (gimple_vdef (stmt))
4008 BB_LIVE_VOP_ON_EXIT (block) = gimple_vdef (stmt);
4009
4010 if (gimple_has_side_effects (stmt)
4011 || stmt_could_throw_p (fun, stmt)
4012 || is_gimple_debug (stmt))
4013 continue;
4014
4015 FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_USE)
4016 {
4017 if (ssa_undefined_value_p (op))
4018 continue;
4019 pre_expr e = get_or_alloc_expr_for_name (op);
4020 bitmap_value_insert_into_set (EXP_GEN (block), e);
4021 }
4022
4023 switch (gimple_code (stmt))
4024 {
4025 case GIMPLE_RETURN:
4026 continue;
4027
4028 case GIMPLE_CALL:
4029 {
4030 vn_reference_t ref;
4031 vn_reference_s ref1;
4032 pre_expr result = NULL;
4033
4034 vn_reference_lookup_call (as_a <gcall *> (stmt), &ref, &ref1);
4035 /* There is no point to PRE a call without a value. */
4036 if (!ref || !ref->result)
4037 continue;
4038
4039 /* If the value of the call is not invalidated in
4040 this block until it is computed, add the expression
4041 to EXP_GEN. */
4042 if ((!gimple_vuse (stmt)
4043 || gimple_code
4044 (SSA_NAME_DEF_STMT (gimple_vuse (stmt))) == GIMPLE_PHI
4045 || gimple_bb (SSA_NAME_DEF_STMT
4046 (gimple_vuse (stmt))) != block)
4047 /* If the REFERENCE traps and there was a preceding
4048 point in the block that might not return avoid
4049 adding the reference to EXP_GEN. */
4050 && (!BB_MAY_NOTRETURN (block)
4051 || !vn_reference_may_trap (ref)))
4052 {
4053 result = get_or_alloc_expr_for_reference
4054 (ref, gimple_location (stmt));
4055 add_to_value (get_expr_value_id (result), result);
4056 bitmap_value_insert_into_set (EXP_GEN (block), result);
4057 }
4058 continue;
4059 }
4060
4061 case GIMPLE_ASSIGN:
4062 {
4063 pre_expr result = NULL;
4064 switch (vn_get_stmt_kind (stmt))
4065 {
4066 case VN_NARY:
4067 {
4068 enum tree_code code = gimple_assign_rhs_code (stmt);
4069 vn_nary_op_t nary;
4070
4071 /* COND_EXPR is awkward in that it contains an
4072 embedded complex expression.
4073 Don't even try to shove it through PRE. */
4074 if (code == COND_EXPR)
4075 continue;
4076
4077 vn_nary_op_lookup_stmt (stmt, &nary);
4078 if (!nary || nary->predicated_values)
4079 continue;
4080
4081 unsigned value_id = nary->value_id;
4082 if (value_id_constant_p (value_id))
4083 continue;
4084
4085 /* Record the un-valueized expression for EXP_GEN. */
4086 nary = XALLOCAVAR (struct vn_nary_op_s,
4087 sizeof_vn_nary_op
4088 (vn_nary_length_from_stmt (stmt)));
4089 init_vn_nary_op_from_stmt (nary, as_a <gassign *> (stmt));
4090
4091 /* If the NARY traps and there was a preceding
4092 point in the block that might not return avoid
4093 adding the nary to EXP_GEN. */
4094 if (BB_MAY_NOTRETURN (block)
4095 && vn_nary_may_trap (nary))
4096 continue;
4097
4098 result = get_or_alloc_expr_for_nary
4099 (nary, value_id, gimple_location (stmt));
4100 break;
4101 }
4102
4103 case VN_REFERENCE:
4104 {
4105 tree rhs1 = gimple_assign_rhs1 (stmt);
4106 ao_ref rhs1_ref;
4107 ao_ref_init (&rhs1_ref, rhs1);
4108 alias_set_type set = ao_ref_alias_set (&rhs1_ref);
4109 alias_set_type base_set
4110 = ao_ref_base_alias_set (&rhs1_ref);
4111 vec<vn_reference_op_s> operands
4112 = vn_reference_operands_for_lookup (rhs1);
4113 vn_reference_t ref;
4114 vn_reference_lookup_pieces (gimple_vuse (stmt), set,
4115 base_set, TREE_TYPE (rhs1),
4116 operands, &ref, VN_WALK);
4117 if (!ref)
4118 {
4119 operands.release ();
4120 continue;
4121 }
4122
4123 /* If the REFERENCE traps and there was a preceding
4124 point in the block that might not return avoid
4125 adding the reference to EXP_GEN. */
4126 if (BB_MAY_NOTRETURN (block)
4127 && vn_reference_may_trap (ref))
4128 {
4129 operands.release ();
4130 continue;
4131 }
4132
4133 /* If the value of the reference is not invalidated in
4134 this block until it is computed, add the expression
4135 to EXP_GEN. */
4136 if (gimple_vuse (stmt))
4137 {
4138 gimple *def_stmt;
4139 bool ok = true;
4140 def_stmt = SSA_NAME_DEF_STMT (gimple_vuse (stmt));
4141 while (!gimple_nop_p (def_stmt)
4142 && gimple_code (def_stmt) != GIMPLE_PHI
4143 && gimple_bb (def_stmt) == block)
4144 {
4145 if (stmt_may_clobber_ref_p
4146 (def_stmt, gimple_assign_rhs1 (stmt)))
4147 {
4148 ok = false;
4149 break;
4150 }
4151 def_stmt
4152 = SSA_NAME_DEF_STMT (gimple_vuse (def_stmt));
4153 }
4154 if (!ok)
4155 {
4156 operands.release ();
4157 continue;
4158 }
4159 }
4160
4161 /* If the load was value-numbered to another
4162 load make sure we do not use its expression
4163 for insertion if it wouldn't be a valid
4164 replacement. */
4165 /* At the momemt we have a testcase
4166 for hoist insertion of aligned vs. misaligned
4167 variants in gcc.dg/torture/pr65270-1.c thus
4168 with just alignment to be considered we can
4169 simply replace the expression in the hashtable
4170 with the most conservative one. */
4171 vn_reference_op_t ref1 = &ref->operands.last ();
4172 while (ref1->opcode != TARGET_MEM_REF
4173 && ref1->opcode != MEM_REF
4174 && ref1 != &ref->operands[0])
4175 --ref1;
4176 vn_reference_op_t ref2 = &operands.last ();
4177 while (ref2->opcode != TARGET_MEM_REF
4178 && ref2->opcode != MEM_REF
4179 && ref2 != &operands[0])
4180 --ref2;
4181 if ((ref1->opcode == TARGET_MEM_REF
4182 || ref1->opcode == MEM_REF)
4183 && (TYPE_ALIGN (ref1->type)
4184 > TYPE_ALIGN (ref2->type)))
4185 ref1->type
4186 = build_aligned_type (ref1->type,
4187 TYPE_ALIGN (ref2->type));
4188 /* TBAA behavior is an obvious part so make sure
4189 that the hashtable one covers this as well
4190 by adjusting the ref alias set and its base. */
4191 if (ref->set == set
4192 || alias_set_subset_of (set, ref->set))
4193 ;
4194 else if (ref1->opcode != ref2->opcode
4195 || (ref1->opcode != MEM_REF
4196 && ref1->opcode != TARGET_MEM_REF))
4197 {
4198 /* With mismatching base opcodes or bases
4199 other than MEM_REF or TARGET_MEM_REF we
4200 can't do any easy TBAA adjustment. */
4201 operands.release ();
4202 continue;
4203 }
4204 else if (alias_set_subset_of (ref->set, set))
4205 {
4206 ref->set = set;
4207 if (ref1->opcode == MEM_REF)
4208 ref1->op0
4209 = wide_int_to_tree (TREE_TYPE (ref2->op0),
4210 wi::to_wide (ref1->op0));
4211 else
4212 ref1->op2
4213 = wide_int_to_tree (TREE_TYPE (ref2->op2),
4214 wi::to_wide (ref1->op2));
4215 }
4216 else
4217 {
4218 ref->set = 0;
4219 ref->base_set = 0;
4220 if (ref1->opcode == MEM_REF)
4221 ref1->op0
4222 = wide_int_to_tree (ptr_type_node,
4223 wi::to_wide (ref1->op0));
4224 else
4225 ref1->op2
4226 = wide_int_to_tree (ptr_type_node,
4227 wi::to_wide (ref1->op2));
4228 }
4229 operands.release ();
4230
4231 result = get_or_alloc_expr_for_reference
4232 (ref, gimple_location (stmt));
4233 break;
4234 }
4235
4236 default:
4237 continue;
4238 }
4239
4240 add_to_value (get_expr_value_id (result), result);
4241 bitmap_value_insert_into_set (EXP_GEN (block), result);
4242 continue;
4243 }
4244 default:
4245 break;
4246 }
4247 }
4248 if (set_bb_may_notreturn)
4249 {
4250 BB_MAY_NOTRETURN (block) = 1;
4251 set_bb_may_notreturn = false;
4252 }
4253
4254 if (dump_file && (dump_flags & TDF_DETAILS))
4255 {
4256 print_bitmap_set (dump_file, EXP_GEN (block),
4257 "exp_gen", block->index);
4258 print_bitmap_set (dump_file, PHI_GEN (block),
4259 "phi_gen", block->index);
4260 print_bitmap_set (dump_file, TMP_GEN (block),
4261 "tmp_gen", block->index);
4262 print_bitmap_set (dump_file, AVAIL_OUT (block),
4263 "avail_out", block->index);
4264 }
4265
4266 /* Put the dominator children of BLOCK on the worklist of blocks
4267 to compute available sets for. */
4268 for (son = first_dom_son (CDI_DOMINATORS, block);
4269 son;
4270 son = next_dom_son (CDI_DOMINATORS, son))
4271 worklist[sp++] = son;
4272 }
4273 vn_context_bb = NULL;
4274
4275 free (worklist);
4276 }
4277
4278
4279 /* Initialize data structures used by PRE. */
4280
4281 static void
init_pre(void)4282 init_pre (void)
4283 {
4284 basic_block bb;
4285
4286 next_expression_id = 1;
4287 expressions.create (0);
4288 expressions.safe_push (NULL);
4289 value_expressions.create (get_max_value_id () + 1);
4290 value_expressions.quick_grow_cleared (get_max_value_id () + 1);
4291 constant_value_expressions.create (get_max_constant_value_id () + 1);
4292 constant_value_expressions.quick_grow_cleared (get_max_constant_value_id () + 1);
4293 name_to_id.create (0);
4294 gcc_obstack_init (&pre_expr_obstack);
4295
4296 inserted_exprs = BITMAP_ALLOC (NULL);
4297
4298 connect_infinite_loops_to_exit ();
4299 memset (&pre_stats, 0, sizeof (pre_stats));
4300
4301 alloc_aux_for_blocks (sizeof (struct bb_bitmap_sets));
4302
4303 calculate_dominance_info (CDI_DOMINATORS);
4304
4305 bitmap_obstack_initialize (&grand_bitmap_obstack);
4306 expression_to_id = new hash_table<pre_expr_d> (num_ssa_names * 3);
4307 FOR_ALL_BB_FN (bb, cfun)
4308 {
4309 EXP_GEN (bb) = bitmap_set_new ();
4310 PHI_GEN (bb) = bitmap_set_new ();
4311 TMP_GEN (bb) = bitmap_set_new ();
4312 AVAIL_OUT (bb) = bitmap_set_new ();
4313 PHI_TRANS_TABLE (bb) = NULL;
4314 }
4315 }
4316
4317
4318 /* Deallocate data structures used by PRE. */
4319
4320 static void
fini_pre()4321 fini_pre ()
4322 {
4323 value_expressions.release ();
4324 constant_value_expressions.release ();
4325 expressions.release ();
4326 bitmap_obstack_release (&grand_bitmap_obstack);
4327 bitmap_set_pool.release ();
4328 pre_expr_pool.release ();
4329 delete expression_to_id;
4330 expression_to_id = NULL;
4331 name_to_id.release ();
4332 obstack_free (&pre_expr_obstack, NULL);
4333
4334 basic_block bb;
4335 FOR_ALL_BB_FN (bb, cfun)
4336 if (bb->aux && PHI_TRANS_TABLE (bb))
4337 delete PHI_TRANS_TABLE (bb);
4338 free_aux_for_blocks ();
4339 }
4340
4341 namespace {
4342
4343 const pass_data pass_data_pre =
4344 {
4345 GIMPLE_PASS, /* type */
4346 "pre", /* name */
4347 OPTGROUP_NONE, /* optinfo_flags */
4348 TV_TREE_PRE, /* tv_id */
4349 ( PROP_cfg | PROP_ssa ), /* properties_required */
4350 0, /* properties_provided */
4351 0, /* properties_destroyed */
4352 TODO_rebuild_alias, /* todo_flags_start */
4353 0, /* todo_flags_finish */
4354 };
4355
4356 class pass_pre : public gimple_opt_pass
4357 {
4358 public:
pass_pre(gcc::context * ctxt)4359 pass_pre (gcc::context *ctxt)
4360 : gimple_opt_pass (pass_data_pre, ctxt)
4361 {}
4362
4363 /* opt_pass methods: */
gate(function *)4364 virtual bool gate (function *)
4365 { return flag_tree_pre != 0 || flag_code_hoisting != 0; }
4366 virtual unsigned int execute (function *);
4367
4368 }; // class pass_pre
4369
4370 /* Valueization hook for RPO VN when we are calling back to it
4371 at ANTIC compute time. */
4372
4373 static tree
pre_valueize(tree name)4374 pre_valueize (tree name)
4375 {
4376 if (TREE_CODE (name) == SSA_NAME)
4377 {
4378 tree tem = VN_INFO (name)->valnum;
4379 if (tem != VN_TOP && tem != name)
4380 {
4381 if (TREE_CODE (tem) != SSA_NAME
4382 || SSA_NAME_IS_DEFAULT_DEF (tem))
4383 return tem;
4384 /* We create temporary SSA names for representatives that
4385 do not have a definition (yet) but are not default defs either
4386 assume they are fine to use. */
4387 basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (tem));
4388 if (! def_bb
4389 || dominated_by_p (CDI_DOMINATORS, vn_context_bb, def_bb))
4390 return tem;
4391 /* ??? Now we could look for a leader. Ideally we'd somehow
4392 expose RPO VN leaders and get rid of AVAIL_OUT as well... */
4393 }
4394 }
4395 return name;
4396 }
4397
4398 unsigned int
execute(function * fun)4399 pass_pre::execute (function *fun)
4400 {
4401 unsigned int todo = 0;
4402
4403 do_partial_partial =
4404 flag_tree_partial_pre && optimize_function_for_speed_p (fun);
4405
4406 /* This has to happen before VN runs because
4407 loop_optimizer_init may create new phis, etc. */
4408 loop_optimizer_init (LOOPS_NORMAL);
4409 split_edges_for_insertion ();
4410 scev_initialize ();
4411 calculate_dominance_info (CDI_DOMINATORS);
4412
4413 run_rpo_vn (VN_WALK);
4414
4415 init_pre ();
4416
4417 vn_valueize = pre_valueize;
4418
4419 /* Insert can get quite slow on an incredibly large number of basic
4420 blocks due to some quadratic behavior. Until this behavior is
4421 fixed, don't run it when he have an incredibly large number of
4422 bb's. If we aren't going to run insert, there is no point in
4423 computing ANTIC, either, even though it's plenty fast nor do
4424 we require AVAIL. */
4425 if (n_basic_blocks_for_fn (fun) < 4000)
4426 {
4427 compute_avail (fun);
4428 compute_antic ();
4429 insert ();
4430 }
4431
4432 /* Make sure to remove fake edges before committing our inserts.
4433 This makes sure we don't end up with extra critical edges that
4434 we would need to split. */
4435 remove_fake_exit_edges ();
4436 gsi_commit_edge_inserts ();
4437
4438 /* Eliminate folds statements which might (should not...) end up
4439 not keeping virtual operands up-to-date. */
4440 gcc_assert (!need_ssa_update_p (fun));
4441
4442 statistics_counter_event (fun, "Insertions", pre_stats.insertions);
4443 statistics_counter_event (fun, "PA inserted", pre_stats.pa_insert);
4444 statistics_counter_event (fun, "HOIST inserted", pre_stats.hoist_insert);
4445 statistics_counter_event (fun, "New PHIs", pre_stats.phis);
4446
4447 todo |= eliminate_with_rpo_vn (inserted_exprs);
4448
4449 vn_valueize = NULL;
4450
4451 fini_pre ();
4452
4453 scev_finalize ();
4454 loop_optimizer_finalize ();
4455
4456 /* Perform a CFG cleanup before we run simple_dce_from_worklist since
4457 unreachable code regions will have not up-to-date SSA form which
4458 confuses it. */
4459 bool need_crit_edge_split = false;
4460 if (todo & TODO_cleanup_cfg)
4461 {
4462 cleanup_tree_cfg ();
4463 need_crit_edge_split = true;
4464 }
4465
4466 /* Because we don't follow exactly the standard PRE algorithm, and decide not
4467 to insert PHI nodes sometimes, and because value numbering of casts isn't
4468 perfect, we sometimes end up inserting dead code. This simple DCE-like
4469 pass removes any insertions we made that weren't actually used. */
4470 simple_dce_from_worklist (inserted_exprs);
4471 BITMAP_FREE (inserted_exprs);
4472
4473 /* TODO: tail_merge_optimize may merge all predecessors of a block, in which
4474 case we can merge the block with the remaining predecessor of the block.
4475 It should either:
4476 - call merge_blocks after each tail merge iteration
4477 - call merge_blocks after all tail merge iterations
4478 - mark TODO_cleanup_cfg when necessary. */
4479 todo |= tail_merge_optimize (need_crit_edge_split);
4480
4481 free_rpo_vn ();
4482
4483 /* Tail merging invalidates the virtual SSA web, together with
4484 cfg-cleanup opportunities exposed by PRE this will wreck the
4485 SSA updating machinery. So make sure to run update-ssa
4486 manually, before eventually scheduling cfg-cleanup as part of
4487 the todo. */
4488 update_ssa (TODO_update_ssa_only_virtuals);
4489
4490 return todo;
4491 }
4492
4493 } // anon namespace
4494
4495 gimple_opt_pass *
make_pass_pre(gcc::context * ctxt)4496 make_pass_pre (gcc::context *ctxt)
4497 {
4498 return new pass_pre (ctxt);
4499 }
4500