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