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