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