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 57623483 : pre_expr_d::equal (const pre_expr_d *e1, const pre_expr_d *e2)
277 : {
278 57623483 : if (e1->kind != e2->kind)
279 : return false;
280 :
281 36037959 : switch (e1->kind)
282 : {
283 4750103 : case CONSTANT:
284 4750103 : return vn_constant_eq_with_type (PRE_EXPR_CONSTANT (e1),
285 4750103 : PRE_EXPR_CONSTANT (e2));
286 157183 : case NAME:
287 157183 : return PRE_EXPR_NAME (e1) == PRE_EXPR_NAME (e2);
288 22419843 : case NARY:
289 22419843 : return vn_nary_op_eq (PRE_EXPR_NARY (e1), PRE_EXPR_NARY (e2));
290 8710830 : case REFERENCE:
291 8710830 : return vn_reference_eq (PRE_EXPR_REFERENCE (e1),
292 8710830 : PRE_EXPR_REFERENCE (e2), true);
293 0 : default:
294 0 : gcc_unreachable ();
295 : }
296 : }
297 :
298 : /* Hash E. */
299 :
300 : inline hashval_t
301 91978867 : pre_expr_d::hash (const pre_expr_d *e)
302 : {
303 91978867 : switch (e->kind)
304 : {
305 7246004 : case CONSTANT:
306 7246004 : 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 56420988 : case NARY:
310 56420988 : return PRE_EXPR_NARY (e)->hashcode;
311 28311875 : case REFERENCE:
312 28311875 : 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 43850308 : alloc_expression_id (pre_expr expr)
331 : {
332 43850308 : struct pre_expr_d **slot;
333 : /* Make sure we won't overflow. */
334 43850308 : gcc_assert (next_expression_id + 1 > next_expression_id);
335 43850308 : expr->id = next_expression_id++;
336 43850308 : expressions.safe_push (expr);
337 43850308 : if (expr->kind == NAME)
338 : {
339 23927034 : 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 23927034 : unsigned old_len = name_to_id.length ();
343 47854068 : name_to_id.reserve (num_ssa_names - old_len);
344 47854068 : name_to_id.quick_grow_cleared (num_ssa_names);
345 23927034 : gcc_assert (name_to_id[version] == 0);
346 23927034 : name_to_id[version] = expr->id;
347 : }
348 : else
349 : {
350 19923274 : slot = expression_to_id->find_slot (expr, INSERT);
351 19923274 : gcc_assert (!*slot);
352 19923274 : *slot = expr;
353 : }
354 43850308 : return next_expression_id - 1;
355 : }
356 :
357 : /* Return the expression id for tree EXPR. */
358 :
359 : static inline unsigned int
360 258362539 : get_expression_id (const pre_expr expr)
361 : {
362 258362539 : return expr->id;
363 : }
364 :
365 : static inline unsigned int
366 79136504 : lookup_expression_id (const pre_expr expr)
367 : {
368 79136504 : struct pre_expr_d **slot;
369 :
370 79136504 : if (expr->kind == NAME)
371 : {
372 53278503 : unsigned version = SSA_NAME_VERSION (PRE_EXPR_NAME (expr));
373 73201777 : if (name_to_id.length () <= version)
374 : return 0;
375 50300317 : return name_to_id[version];
376 : }
377 : else
378 : {
379 25858001 : slot = expression_to_id->find_slot (expr, NO_INSERT);
380 25858001 : if (!slot)
381 : return 0;
382 5934727 : return ((pre_expr)*slot)->id;
383 : }
384 : }
385 :
386 : /* Return the expression that has expression id ID */
387 :
388 : static inline pre_expr
389 654216920 : expression_for_id (unsigned int id)
390 : {
391 1308433840 : 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 53278503 : get_or_alloc_expr_for_name (tree name)
400 : {
401 53278503 : struct pre_expr_d expr;
402 53278503 : pre_expr result;
403 53278503 : unsigned int result_id;
404 :
405 53278503 : expr.kind = NAME;
406 53278503 : expr.id = 0;
407 53278503 : PRE_EXPR_NAME (&expr) = name;
408 53278503 : result_id = lookup_expression_id (&expr);
409 53278503 : if (result_id != 0)
410 29351469 : return expression_for_id (result_id);
411 :
412 23927034 : result = pre_expr_pool.allocate ();
413 23927034 : result->kind = NAME;
414 23927034 : result->loc = UNKNOWN_LOCATION;
415 23927034 : result->value_id = VN_INFO (name)->value_id;
416 23927034 : PRE_EXPR_NAME (result) = name;
417 23927034 : alloc_expression_id (result);
418 23927034 : 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 13641376 : get_or_alloc_expr_for_nary (vn_nary_op_t nary, unsigned value_id,
427 : location_t loc = UNKNOWN_LOCATION)
428 : {
429 13641376 : struct pre_expr_d expr;
430 13641376 : pre_expr result;
431 13641376 : unsigned int result_id;
432 :
433 13641376 : gcc_assert (value_id == 0 || !value_id_constant_p (value_id));
434 :
435 13641376 : expr.kind = NARY;
436 13641376 : expr.id = 0;
437 13641376 : nary->hashcode = vn_nary_op_compute_hash (nary);
438 13641376 : PRE_EXPR_NARY (&expr) = nary;
439 13641376 : result_id = lookup_expression_id (&expr);
440 13641376 : if (result_id != 0)
441 992216 : return expression_for_id (result_id);
442 :
443 12649160 : result = pre_expr_pool.allocate ();
444 12649160 : result->kind = NARY;
445 12649160 : result->loc = loc;
446 12649160 : result->value_id = value_id ? value_id : get_next_value_id ();
447 12649160 : PRE_EXPR_NARY (result)
448 12649160 : = alloc_vn_nary_op_noinit (nary->length, &pre_expr_obstack);
449 12649160 : memcpy (PRE_EXPR_NARY (result), nary, sizeof_vn_nary_op (nary->length));
450 12649160 : alloc_expression_id (result);
451 12649160 : 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 transferred, otherwise
458 : a copy is made if necessary. */
459 :
460 : static pre_expr
461 7174847 : 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 7174847 : struct pre_expr_d expr;
467 7174847 : pre_expr result;
468 7174847 : unsigned int result_id;
469 :
470 7174847 : expr.kind = REFERENCE;
471 7174847 : expr.id = 0;
472 7174847 : PRE_EXPR_REFERENCE (&expr) = reference;
473 7174847 : result_id = lookup_expression_id (&expr);
474 7174847 : if (result_id != 0)
475 : {
476 747085 : if (move_operands)
477 734725 : reference->operands.release ();
478 747085 : return expression_for_id (result_id);
479 : }
480 :
481 6427762 : result = pre_expr_pool.allocate ();
482 6427762 : result->kind = REFERENCE;
483 6427762 : result->loc = loc;
484 6427762 : result->value_id = value_id ? value_id : get_next_value_id ();
485 6427762 : vn_reference_t ref = XOBNEW (&pre_expr_obstack, struct vn_reference_s);
486 6427762 : *ref = *reference;
487 6427762 : if (!move_operands)
488 450373 : ref->operands = ref->operands.copy ();
489 6427762 : PRE_EXPR_REFERENCE (result) = ref;
490 6427762 : alloc_expression_id (result);
491 6427762 : return result;
492 : }
493 :
494 :
495 : /* An unordered bitmap set. One bitmap tracks values, the other,
496 : expressions. */
497 147041003 : 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 1387793424 : expr_pred_trans_d::is_empty (const expr_pred_trans_d &e)
580 : {
581 1387793424 : return e.e == 0;
582 : }
583 :
584 : inline bool
585 277607827 : expr_pred_trans_d::is_deleted (const expr_pred_trans_d &e)
586 : {
587 277607827 : return e.e == -1u;
588 : }
589 :
590 : inline void
591 2143818 : expr_pred_trans_d::mark_empty (expr_pred_trans_d &e)
592 : {
593 2143818 : e.e = 0;
594 : }
595 :
596 : inline void
597 3683173 : expr_pred_trans_d::mark_deleted (expr_pred_trans_d &e)
598 : {
599 3683173 : 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 217872819 : expr_pred_trans_d::equal (const expr_pred_trans_d &ve1,
610 : const expr_pred_trans_d &ve2)
611 : {
612 217872819 : 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 86080411 : phi_trans_add (expr_pred_trans_t *entry, pre_expr e, basic_block pred)
682 : {
683 86080411 : if (!PHI_TRANS_TABLE (pred))
684 195250 : PHI_TRANS_TABLE (pred) = new hash_table<expr_pred_trans_d> (11);
685 :
686 86080411 : expr_pred_trans_t slot;
687 86080411 : expr_pred_trans_d tem;
688 86080411 : unsigned id = get_expression_id (e);
689 86080411 : tem.e = id;
690 86080411 : slot = PHI_TRANS_TABLE (pred)->find_slot_with_hash (tem, id, INSERT);
691 86080411 : if (slot->e)
692 : {
693 62678237 : *entry = slot;
694 62678237 : return true;
695 : }
696 :
697 23402174 : *entry = slot;
698 23402174 : slot->e = id;
699 23402174 : return false;
700 : }
701 :
702 :
703 : /* Add expression E to the expression set of value id V. */
704 :
705 : static void
706 45589609 : add_to_value (unsigned int v, pre_expr e)
707 : {
708 0 : gcc_checking_assert (get_expr_value_id (e) == v);
709 :
710 45589609 : if (value_id_constant_p (v))
711 : {
712 890410 : if (e->kind != CONSTANT)
713 : return;
714 :
715 846352 : if (-v >= constant_value_expressions.length ())
716 505181 : constant_value_expressions.safe_grow_cleared (-v + 1);
717 :
718 846352 : pre_expr leader = constant_value_expressions[-v];
719 846352 : if (!leader)
720 846352 : constant_value_expressions[-v] = e;
721 : }
722 : else
723 : {
724 44699199 : if (v >= value_expressions.length ())
725 7012953 : value_expressions.safe_grow_cleared (v + 1);
726 :
727 44699199 : bitmap set = value_expressions[v];
728 44699199 : if (!set)
729 : {
730 24976878 : set = BITMAP_ALLOC (&grand_bitmap_obstack);
731 24976878 : value_expressions[v] = set;
732 : }
733 44699199 : 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 147041003 : bitmap_set_new (void)
741 : {
742 147041003 : bitmap_set_t ret = bitmap_set_pool.allocate ();
743 147041003 : bitmap_initialize (&ret->expressions, &grand_bitmap_obstack);
744 147041003 : bitmap_initialize (&ret->values, &grand_bitmap_obstack);
745 147041003 : return ret;
746 : }
747 :
748 : /* Return the value id for a PRE expression EXPR. */
749 :
750 : static unsigned int
751 537621730 : 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 45589609 : 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 1261939 : vn_valnum_from_value_id (unsigned int val)
763 : {
764 1261939 : 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 1261939 : bitmap exprset = value_expressions[val];
773 1261939 : bitmap_iterator bi;
774 1261939 : unsigned int i;
775 1876056 : EXECUTE_IF_SET_IN_BITMAP (exprset, 0, i, bi)
776 : {
777 1531502 : pre_expr vexpr = expression_for_id (i);
778 1531502 : if (vexpr->kind == NAME)
779 917385 : 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 75859548 : bitmap_insert_into_set (bitmap_set_t set, pre_expr expr)
788 : {
789 75859548 : unsigned int val = get_expr_value_id (expr);
790 75859548 : 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 72916361 : bitmap_set_bit (&set->values, val);
796 72916361 : bitmap_set_bit (&set->expressions, get_expression_id (expr));
797 : }
798 75859548 : }
799 :
800 : /* Copy a bitmapped set ORIG, into bitmapped set DEST. */
801 :
802 : static void
803 27146059 : bitmap_set_copy (bitmap_set_t dest, bitmap_set_t orig)
804 : {
805 27146059 : bitmap_copy (&dest->expressions, &orig->expressions);
806 27146059 : bitmap_copy (&dest->values, &orig->values);
807 27146059 : }
808 :
809 :
810 : /* Free memory used up by SET. */
811 : static void
812 73575608 : bitmap_set_free (bitmap_set_t set)
813 : {
814 0 : bitmap_clear (&set->expressions);
815 19657545 : bitmap_clear (&set->values);
816 49715970 : }
817 :
818 :
819 : /* Sort pre_expr after their value-id. */
820 :
821 : static int
822 433485263 : expr_cmp (const void *a_, const void *b_, void *)
823 : {
824 433485263 : pre_expr a = *(pre_expr const *) a_;
825 433485263 : pre_expr b = *(pre_expr const *) b_;
826 433485263 : 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 252297 : prefer (pre_expr a, pre_expr b)
835 : {
836 252297 : if (a->kind == REFERENCE && b->kind == REFERENCE)
837 : {
838 58647 : auto refa = PRE_EXPR_REFERENCE (a);
839 58647 : auto refb = PRE_EXPR_REFERENCE (b);
840 58647 : auto &oprsa = refa->operands;
841 58647 : auto &oprsb = refb->operands;
842 58647 : pre_expr palias = NULL;
843 58647 : if (refa->set == refb->set
844 55341 : && refa->base_set == refb->base_set)
845 : ;
846 13422 : else if ((refb->set == refa->set
847 3306 : || alias_set_subset_of (refb->set, refa->set))
848 14801 : && (refb->base_set == refa->base_set
849 10778 : || alias_set_subset_of (refb->base_set, refa->base_set)))
850 : palias = a;
851 4774 : else if ((refa->set == refb->set
852 1948 : || alias_set_subset_of (refa->set, refb->set))
853 6578 : && (refa->base_set == refb->base_set
854 3951 : || 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 250 : return NULL;
864 58397 : pre_expr p = palias;
865 116794 : if (oprsa.length () > 1 && oprsb.length () > 1)
866 : {
867 58397 : vn_reference_op_t vroa = &oprsa[oprsa.length () - 2];
868 58397 : vn_reference_op_t vrob = &oprsb[oprsb.length () - 2];
869 58397 : 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 58376 : pre_expr palign = NULL;
874 58376 : if (TYPE_ALIGN (vroa->type) < TYPE_ALIGN (vrob->type))
875 : palign = a;
876 58154 : else if (TYPE_ALIGN (vroa->type) > TYPE_ALIGN (vrob->type))
877 : palign = b;
878 480 : if (palign)
879 : {
880 480 : 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 57994 : if (TYPE_SIZE (vroa->type) != TYPE_SIZE (vrob->type))
887 : {
888 4783 : pre_expr psize = NULL;
889 4783 : if (!TYPE_SIZE (vroa->type))
890 : psize = a;
891 4783 : else if (!TYPE_SIZE (vrob->type))
892 : psize = b;
893 4783 : else if (TREE_CODE (TYPE_SIZE (vroa->type)) == INTEGER_CST
894 4783 : && TREE_CODE (TYPE_SIZE (vrob->type)) == INTEGER_CST)
895 : {
896 4777 : int cmp = tree_int_cst_compare (TYPE_SIZE (vroa->type),
897 4777 : TYPE_SIZE (vrob->type));
898 4777 : if (cmp < 0)
899 : psize = a;
900 2693 : else if (cmp > 0)
901 : psize = b;
902 : }
903 : /* ??? What about non-constant sizes? */
904 4777 : if (psize)
905 : {
906 4777 : 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 99159 : return p ? p : b;
917 : }
918 : /* Always prefer an non-REFERENCE, avoiding the above mess. */
919 193650 : else if (a->kind == REFERENCE)
920 : return b;
921 189173 : else if (b->kind == REFERENCE)
922 : return a;
923 156845 : else if (a->kind == b->kind)
924 : ;
925 : /* And prefer NAME over anything else. */
926 11185 : else if (b->kind == NAME)
927 : return b;
928 8354 : else if (a->kind == NAME)
929 8354 : 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 199278730 : pre_expr_DFS (unsigned val, bitmap_set_t set, bitmap exclusions,
942 : bitmap val_visited, vec<pre_expr> &post)
943 : {
944 199278730 : unsigned int i;
945 199278730 : bitmap_iterator bi;
946 :
947 : /* Iterate over all leaders and DFS recurse. Borrowed from
948 : bitmap_find_leader. */
949 199278730 : bitmap exprset = value_expressions[val];
950 199278730 : if (!exprset->first->next)
951 : {
952 472077649 : EXECUTE_IF_SET_IN_BITMAP (exprset, 0, i, bi)
953 301064416 : if (bitmap_bit_p (&set->expressions, i)
954 301064416 : && !bitmap_bit_p (exclusions, i))
955 171271809 : pre_expr_DFS (expression_for_id (i), set, exclusions,
956 : val_visited, post);
957 171013233 : return;
958 : }
959 :
960 57273318 : EXECUTE_IF_AND_IN_BITMAP (exprset, &set->expressions, 0, i, bi)
961 29007821 : if (!bitmap_bit_p (exclusions, i))
962 28656053 : 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 199927862 : pre_expr_DFS (pre_expr expr, bitmap_set_t set, bitmap exclusions,
971 : bitmap val_visited, vec<pre_expr> &post)
972 : {
973 199927862 : switch (expr->kind)
974 : {
975 95842507 : case NARY:
976 95842507 : {
977 95842507 : vn_nary_op_t nary = PRE_EXPR_NARY (expr);
978 259460903 : for (unsigned i = 0; i < nary->length; i++)
979 : {
980 163618396 : if (TREE_CODE (nary->op[i]) != SSA_NAME)
981 46778087 : continue;
982 116840309 : 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 116840309 : if (bitmap_bit_p (&set->values, op_val_id)
986 116840309 : && bitmap_set_bit (val_visited, op_val_id))
987 69117418 : pre_expr_DFS (op_val_id, set, exclusions, val_visited, post);
988 : }
989 : break;
990 : }
991 30118665 : case REFERENCE:
992 30118665 : {
993 30118665 : vn_reference_t ref = PRE_EXPR_REFERENCE (expr);
994 30118665 : vec<vn_reference_op_s> operands = ref->operands;
995 30118665 : vn_reference_op_t operand;
996 119471161 : for (unsigned i = 0; operands.iterate (i, &operand); i++)
997 : {
998 89352496 : tree op[3];
999 89352496 : op[0] = operand->op0;
1000 89352496 : op[1] = operand->op1;
1001 89352496 : op[2] = operand->op2;
1002 357409984 : for (unsigned n = 0; n < 3; ++n)
1003 : {
1004 268057488 : if (!op[n] || TREE_CODE (op[n]) != SSA_NAME)
1005 246548802 : continue;
1006 21508686 : unsigned op_val_id = VN_INFO (op[n])->value_id;
1007 21508686 : if (bitmap_bit_p (&set->values, op_val_id)
1008 21508686 : && bitmap_set_bit (val_visited, op_val_id))
1009 11149118 : pre_expr_DFS (op_val_id, set, exclusions, val_visited, post);
1010 : }
1011 : }
1012 : break;
1013 : }
1014 199927862 : default:;
1015 : }
1016 199927862 : post.quick_push (expr);
1017 199927862 : }
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 18480818 : sorted_array_from_bitmap_set (bitmap_set_t set, bool for_insertion)
1024 : {
1025 18480818 : unsigned int i;
1026 18480818 : bitmap_iterator bi;
1027 18480818 : vec<pre_expr> result;
1028 :
1029 : /* Pre-allocate enough space for the array. */
1030 18480818 : unsigned cnt = bitmap_count_bits (&set->expressions);
1031 18480818 : 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 18480818 : auto_bitmap exclusions;
1036 18480818 : bitmap_tree_view (exclusions);
1037 18480818 : if (for_insertion && cnt > 1)
1038 : {
1039 26657116 : EXECUTE_IF_SET_IN_BITMAP (&set->expressions, 0, i, bi)
1040 24013514 : result.safe_push (expression_for_id (i));
1041 2643602 : result.sort (expr_cmp, NULL);
1042 48019402 : for (unsigned i = 0; i < result.length () - 1; ++i)
1043 21366099 : if (result[i]->value_id == result[i+1]->value_id)
1044 : {
1045 252297 : 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 247775 : if (p == result[i])
1050 46883 : std::swap (result[i], result[i+1]);
1051 247775 : bitmap_set_bit (exclusions, get_expression_id (result[i]));
1052 : }
1053 : else
1054 : {
1055 : /* If neither works for pairwise choosing 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 4532 : if (j == 0
1062 4532 : || result[j - 1]->value_id != result[i]->value_id)
1063 : break;
1064 : for (k = j;; ++k)
1065 : {
1066 9105 : if (result[k]->kind == REFERENCE)
1067 9105 : bitmap_set_bit (exclusions,
1068 9105 : get_expression_id (result[k]));
1069 9105 : if (k == result.length () - 1
1070 9105 : || result[k + 1]->value_id != result[i]->value_id)
1071 : break;
1072 : }
1073 : i = k;
1074 : }
1075 : }
1076 2643602 : result.truncate (0);
1077 : }
1078 :
1079 18480818 : bool single_p = true;
1080 18480818 : auto_bitmap val_visited (&grand_bitmap_obstack);
1081 18480818 : bitmap_tree_view (val_visited);
1082 104614806 : FOR_EACH_VALUE_ID_IN_SET (set, i, bi)
1083 86133988 : if (bitmap_set_bit (val_visited, i))
1084 : {
1085 76437018 : if (!result.is_empty ())
1086 : {
1087 63625072 : single_p = false;
1088 63625072 : result.truncate (0);
1089 : }
1090 76437018 : pre_expr_DFS (i, set, exclusions, val_visited, result);
1091 : /* Mark i as entry that is not forward reachable. Note we do
1092 : have cycles in the value graph so eventually i reaches itself. */
1093 76437018 : bitmap_clear_bit (val_visited, i);
1094 : }
1095 : /* If we didn't by luck visit only a single entry to the value
1096 : graph visit now all not forward reachable values. */
1097 18480818 : if (!single_p)
1098 : {
1099 9654933 : result.truncate (0);
1100 9654933 : auto_bitmap val_visited2 (&grand_bitmap_obstack);
1101 9654933 : bitmap_tree_view (val_visited2);
1102 92093117 : FOR_EACH_VALUE_ID_IN_SET (set, i, bi)
1103 82438184 : if (!bitmap_bit_p (val_visited, i))
1104 : {
1105 42575176 : if (bitmap_set_bit (val_visited2, i))
1106 42575176 : pre_expr_DFS (i, set, exclusions, val_visited2, result);
1107 : else
1108 0 : gcc_unreachable ();
1109 : }
1110 9654933 : if (flag_checking)
1111 : {
1112 9654882 : bitmap_list_view (val_visited2);
1113 9654882 : gcc_assert (bitmap_equal_p (&set->values, val_visited2));
1114 : }
1115 9654933 : }
1116 :
1117 18480818 : return result;
1118 18480818 : }
1119 :
1120 : /* Subtract all expressions contained in ORIG from DEST. */
1121 :
1122 : static bitmap_set_t
1123 32734216 : bitmap_set_subtract_expressions (bitmap_set_t dest, bitmap_set_t orig,
1124 : bool copy_values = false)
1125 : {
1126 32734216 : bitmap_set_t result = bitmap_set_new ();
1127 32734216 : bitmap_iterator bi;
1128 32734216 : unsigned int i;
1129 :
1130 32734216 : bitmap_and_compl (&result->expressions, &dest->expressions,
1131 32734216 : &orig->expressions);
1132 :
1133 32734216 : if (copy_values)
1134 655277 : bitmap_copy (&result->values, &dest->values);
1135 : else
1136 111402622 : FOR_EACH_EXPR_ID_IN_SET (result, i, bi)
1137 : {
1138 79323683 : pre_expr expr = expression_for_id (i);
1139 79323683 : unsigned int value_id = get_expr_value_id (expr);
1140 79323683 : bitmap_set_bit (&result->values, value_id);
1141 : }
1142 :
1143 32734216 : return result;
1144 : }
1145 :
1146 : /* Subtract all values in bitmap set B from bitmap set A. */
1147 :
1148 : static void
1149 1223026 : bitmap_set_subtract_values (bitmap_set_t a, bitmap_set_t b)
1150 : {
1151 1223026 : unsigned int i;
1152 1223026 : bitmap_iterator bi;
1153 1223026 : unsigned to_remove = -1U;
1154 1223026 : bitmap_and_compl_into (&a->values, &b->values);
1155 11486996 : FOR_EACH_EXPR_ID_IN_SET (a, i, bi)
1156 : {
1157 10263970 : if (to_remove != -1U)
1158 : {
1159 1433958 : bitmap_clear_bit (&a->expressions, to_remove);
1160 1433958 : to_remove = -1U;
1161 : }
1162 10263970 : pre_expr expr = expression_for_id (i);
1163 10263970 : if (! bitmap_bit_p (&a->values, get_expr_value_id (expr)))
1164 1492977 : to_remove = i;
1165 : }
1166 1223026 : if (to_remove != -1U)
1167 59019 : bitmap_clear_bit (&a->expressions, to_remove);
1168 1223026 : }
1169 :
1170 :
1171 : /* Return true if bitmapped set SET contains the value VALUE_ID. */
1172 :
1173 : static bool
1174 201704497 : bitmap_set_contains_value (bitmap_set_t set, unsigned int value_id)
1175 : {
1176 0 : if (value_id_constant_p (value_id))
1177 : return true;
1178 :
1179 98876329 : return bitmap_bit_p (&set->values, value_id);
1180 : }
1181 :
1182 : /* Return true if two bitmap sets are equal. */
1183 :
1184 : static bool
1185 15755595 : bitmap_set_equal (bitmap_set_t a, bitmap_set_t b)
1186 : {
1187 0 : return bitmap_equal_p (&a->values, &b->values);
1188 : }
1189 :
1190 : /* Replace an instance of EXPR's VALUE with EXPR in SET if it exists,
1191 : and add it otherwise. Return true if any changes were made. */
1192 :
1193 : static bool
1194 33739052 : bitmap_value_replace_in_set (bitmap_set_t set, pre_expr expr)
1195 : {
1196 33739052 : unsigned int val = get_expr_value_id (expr);
1197 33739052 : if (value_id_constant_p (val))
1198 : return false;
1199 :
1200 33739052 : if (bitmap_set_contains_value (set, val))
1201 : {
1202 : /* The number of expressions having a given value is usually
1203 : significantly less than the total number of expressions in SET.
1204 : Thus, rather than check, for each expression in SET, whether it
1205 : has the value LOOKFOR, we walk the reverse mapping that tells us
1206 : what expressions have a given value, and see if any of those
1207 : expressions are in our set. For large testcases, this is about
1208 : 5-10x faster than walking the bitmap. If this is somehow a
1209 : significant lose for some cases, we can choose which set to walk
1210 : based on the set size. */
1211 14380477 : unsigned int i;
1212 14380477 : bitmap_iterator bi;
1213 14380477 : bitmap exprset = value_expressions[val];
1214 16613409 : EXECUTE_IF_SET_IN_BITMAP (exprset, 0, i, bi)
1215 : {
1216 16613409 : if (bitmap_clear_bit (&set->expressions, i))
1217 : {
1218 14380477 : bitmap_set_bit (&set->expressions, get_expression_id (expr));
1219 14380477 : return i != get_expression_id (expr);
1220 : }
1221 : }
1222 0 : gcc_unreachable ();
1223 : }
1224 :
1225 19358575 : bitmap_insert_into_set (set, expr);
1226 19358575 : return true;
1227 : }
1228 :
1229 : /* Insert EXPR into SET if EXPR's value is not already present in
1230 : SET. */
1231 :
1232 : static void
1233 63434670 : bitmap_value_insert_into_set (bitmap_set_t set, pre_expr expr)
1234 : {
1235 63434670 : unsigned int val = get_expr_value_id (expr);
1236 :
1237 63434670 : gcc_checking_assert (expr->id == get_expression_id (expr));
1238 :
1239 : /* Constant values are always considered to be part of the set. */
1240 63434670 : if (value_id_constant_p (val))
1241 : return;
1242 :
1243 : /* If the value membership changed, add the expression. */
1244 63377204 : if (bitmap_set_bit (&set->values, val))
1245 48967167 : bitmap_set_bit (&set->expressions, expr->id);
1246 : }
1247 :
1248 : /* Print out EXPR to outfile. */
1249 :
1250 : static void
1251 4573 : print_pre_expr (FILE *outfile, const pre_expr expr)
1252 : {
1253 4573 : if (! expr)
1254 : {
1255 0 : fprintf (outfile, "NULL");
1256 0 : return;
1257 : }
1258 4573 : switch (expr->kind)
1259 : {
1260 0 : case CONSTANT:
1261 0 : print_generic_expr (outfile, PRE_EXPR_CONSTANT (expr));
1262 0 : break;
1263 3214 : case NAME:
1264 3214 : print_generic_expr (outfile, PRE_EXPR_NAME (expr));
1265 3214 : break;
1266 1072 : case NARY:
1267 1072 : {
1268 1072 : unsigned int i;
1269 1072 : vn_nary_op_t nary = PRE_EXPR_NARY (expr);
1270 1072 : fprintf (outfile, "{%s,", get_tree_code_name (nary->opcode));
1271 4095 : for (i = 0; i < nary->length; i++)
1272 : {
1273 1951 : print_generic_expr (outfile, nary->op[i]);
1274 1951 : if (i != (unsigned) nary->length - 1)
1275 879 : fprintf (outfile, ",");
1276 : }
1277 1072 : fprintf (outfile, "}");
1278 : }
1279 1072 : break;
1280 :
1281 287 : case REFERENCE:
1282 287 : {
1283 287 : vn_reference_t ref = PRE_EXPR_REFERENCE (expr);
1284 287 : print_vn_reference_ops (outfile, ref->operands);
1285 287 : if (ref->vuse)
1286 : {
1287 275 : fprintf (outfile, "@");
1288 275 : print_generic_expr (outfile, ref->vuse);
1289 : }
1290 : }
1291 : break;
1292 : }
1293 : }
1294 : void debug_pre_expr (pre_expr);
1295 :
1296 : /* Like print_pre_expr but always prints to stderr. */
1297 : DEBUG_FUNCTION void
1298 0 : debug_pre_expr (pre_expr e)
1299 : {
1300 0 : print_pre_expr (stderr, e);
1301 0 : fprintf (stderr, "\n");
1302 0 : }
1303 :
1304 : /* Print out SET to OUTFILE. */
1305 :
1306 : static void
1307 913 : print_bitmap_set (FILE *outfile, bitmap_set_t set,
1308 : const char *setname, int blockindex)
1309 : {
1310 913 : fprintf (outfile, "%s[%d] := { ", setname, blockindex);
1311 913 : if (set)
1312 : {
1313 913 : bool first = true;
1314 913 : unsigned i;
1315 913 : bitmap_iterator bi;
1316 :
1317 5345 : FOR_EACH_EXPR_ID_IN_SET (set, i, bi)
1318 : {
1319 4432 : const pre_expr expr = expression_for_id (i);
1320 :
1321 4432 : if (!first)
1322 3806 : fprintf (outfile, ", ");
1323 4432 : first = false;
1324 4432 : print_pre_expr (outfile, expr);
1325 :
1326 4432 : fprintf (outfile, " (%04d)", get_expr_value_id (expr));
1327 : }
1328 : }
1329 913 : fprintf (outfile, " }\n");
1330 913 : }
1331 :
1332 : void debug_bitmap_set (bitmap_set_t);
1333 :
1334 : DEBUG_FUNCTION void
1335 0 : debug_bitmap_set (bitmap_set_t set)
1336 : {
1337 0 : print_bitmap_set (stderr, set, "debug", 0);
1338 0 : }
1339 :
1340 : void debug_bitmap_sets_for (basic_block);
1341 :
1342 : DEBUG_FUNCTION void
1343 0 : debug_bitmap_sets_for (basic_block bb)
1344 : {
1345 0 : print_bitmap_set (stderr, AVAIL_OUT (bb), "avail_out", bb->index);
1346 0 : print_bitmap_set (stderr, EXP_GEN (bb), "exp_gen", bb->index);
1347 0 : print_bitmap_set (stderr, PHI_GEN (bb), "phi_gen", bb->index);
1348 0 : print_bitmap_set (stderr, TMP_GEN (bb), "tmp_gen", bb->index);
1349 0 : print_bitmap_set (stderr, ANTIC_IN (bb), "antic_in", bb->index);
1350 0 : if (do_partial_partial)
1351 0 : print_bitmap_set (stderr, PA_IN (bb), "pa_in", bb->index);
1352 0 : print_bitmap_set (stderr, NEW_SETS (bb), "new_sets", bb->index);
1353 0 : }
1354 :
1355 : /* Print out the expressions that have VAL to OUTFILE. */
1356 :
1357 : static void
1358 0 : print_value_expressions (FILE *outfile, unsigned int val)
1359 : {
1360 0 : bitmap set = value_expressions[val];
1361 0 : if (set)
1362 : {
1363 0 : bitmap_set x;
1364 0 : char s[10];
1365 0 : sprintf (s, "%04d", val);
1366 0 : x.expressions = *set;
1367 0 : print_bitmap_set (outfile, &x, s, 0);
1368 : }
1369 0 : }
1370 :
1371 :
1372 : DEBUG_FUNCTION void
1373 0 : debug_value_expressions (unsigned int val)
1374 : {
1375 0 : print_value_expressions (stderr, val);
1376 0 : }
1377 :
1378 : /* Given a CONSTANT, allocate a new CONSTANT type PRE_EXPR to
1379 : represent it. */
1380 :
1381 : static pre_expr
1382 5041778 : get_or_alloc_expr_for_constant (tree constant)
1383 : {
1384 5041778 : unsigned int result_id;
1385 5041778 : struct pre_expr_d expr;
1386 5041778 : pre_expr newexpr;
1387 :
1388 5041778 : expr.kind = CONSTANT;
1389 5041778 : PRE_EXPR_CONSTANT (&expr) = constant;
1390 5041778 : result_id = lookup_expression_id (&expr);
1391 5041778 : if (result_id != 0)
1392 4195426 : return expression_for_id (result_id);
1393 :
1394 846352 : newexpr = pre_expr_pool.allocate ();
1395 846352 : newexpr->kind = CONSTANT;
1396 846352 : newexpr->loc = UNKNOWN_LOCATION;
1397 846352 : PRE_EXPR_CONSTANT (newexpr) = constant;
1398 846352 : alloc_expression_id (newexpr);
1399 846352 : newexpr->value_id = get_or_alloc_constant_value_id (constant);
1400 846352 : add_to_value (newexpr->value_id, newexpr);
1401 846352 : return newexpr;
1402 : }
1403 :
1404 : /* Translate the VUSE backwards through phi nodes in E->dest, so that
1405 : it has the value it would have in E->src. Set *SAME_VALID to true
1406 : in case the new vuse doesn't change the value id of the OPERANDS. */
1407 :
1408 : static tree
1409 4543900 : translate_vuse_through_block (vec<vn_reference_op_s> operands,
1410 : alias_set_type set, alias_set_type base_set,
1411 : tree type, tree vuse, edge e, bool *same_valid)
1412 : {
1413 4543900 : basic_block phiblock = e->dest;
1414 4543900 : gimple *def = SSA_NAME_DEF_STMT (vuse);
1415 4543900 : ao_ref ref;
1416 :
1417 4543900 : if (same_valid)
1418 3297234 : *same_valid = true;
1419 :
1420 : /* If value-numbering provided a memory state for this
1421 : that dominates PHIBLOCK we can just use that. */
1422 4543900 : if (gimple_nop_p (def)
1423 4543900 : || (gimple_bb (def) != phiblock
1424 1185768 : && dominated_by_p (CDI_DOMINATORS, phiblock, gimple_bb (def))))
1425 1886100 : return vuse;
1426 :
1427 : /* We have pruned expressions that are killed in PHIBLOCK via
1428 : prune_clobbered_mems but we have not rewritten the VUSE to the one
1429 : live at the start of the block. If there is no virtual PHI to translate
1430 : through return the VUSE live at entry. Otherwise the VUSE to translate
1431 : is the def of the virtual PHI node. */
1432 2657800 : gphi *phi = get_virtual_phi (phiblock);
1433 2657800 : if (!phi)
1434 92573 : return BB_LIVE_VOP_ON_EXIT
1435 : (get_immediate_dominator (CDI_DOMINATORS, phiblock));
1436 :
1437 2565227 : if (same_valid
1438 2565227 : && ao_ref_init_from_vn_reference (&ref, set, base_set, type, operands))
1439 : {
1440 1889967 : bitmap visited = NULL;
1441 : /* Try to find a vuse that dominates this phi node by skipping
1442 : non-clobbering statements. */
1443 1889967 : unsigned int cnt = param_sccvn_max_alias_queries_per_access;
1444 1889967 : vuse = get_continuation_for_phi (phi, &ref, true,
1445 : cnt, &visited, false, NULL, NULL);
1446 1889967 : if (visited)
1447 1878111 : BITMAP_FREE (visited);
1448 : }
1449 : else
1450 : vuse = NULL_TREE;
1451 : /* If we didn't find any, the value ID can't stay the same. */
1452 2565227 : if (!vuse && same_valid)
1453 1632535 : *same_valid = false;
1454 :
1455 : /* ??? We would like to return vuse here as this is the canonical
1456 : upmost vdef that this reference is associated with. But during
1457 : insertion of the references into the hash tables we only ever
1458 : directly insert with their direct gimple_vuse, hence returning
1459 : something else would make us not find the other expression. */
1460 2565227 : return PHI_ARG_DEF (phi, e->dest_idx);
1461 : }
1462 :
1463 : /* Like bitmap_find_leader, but checks for the value existing in SET1 *or*
1464 : SET2 *or* SET3. This is used to avoid making a set consisting of the union
1465 : of PA_IN and ANTIC_IN during insert and phi-translation. */
1466 :
1467 : static inline pre_expr
1468 24305882 : find_leader_in_sets (unsigned int val, bitmap_set_t set1, bitmap_set_t set2,
1469 : bitmap_set_t set3 = NULL)
1470 : {
1471 24305882 : pre_expr result = NULL;
1472 :
1473 24305882 : if (set1)
1474 24176247 : result = bitmap_find_leader (set1, val);
1475 24305882 : if (!result && set2)
1476 1551563 : result = bitmap_find_leader (set2, val);
1477 24305882 : if (!result && set3)
1478 0 : result = bitmap_find_leader (set3, val);
1479 24305882 : return result;
1480 : }
1481 :
1482 : /* Get the tree type for our PRE expression e. */
1483 :
1484 : static tree
1485 7410618 : get_expr_type (const pre_expr e)
1486 : {
1487 7410618 : switch (e->kind)
1488 : {
1489 1003675 : case NAME:
1490 1003675 : return TREE_TYPE (PRE_EXPR_NAME (e));
1491 187696 : case CONSTANT:
1492 187696 : return TREE_TYPE (PRE_EXPR_CONSTANT (e));
1493 1367823 : case REFERENCE:
1494 1367823 : return PRE_EXPR_REFERENCE (e)->type;
1495 4851424 : case NARY:
1496 4851424 : return PRE_EXPR_NARY (e)->type;
1497 : }
1498 0 : gcc_unreachable ();
1499 : }
1500 :
1501 : /* Get a representative SSA_NAME for a given expression that is available in B.
1502 : Since all of our sub-expressions are treated as values, we require
1503 : them to be SSA_NAME's for simplicity.
1504 : Prior versions of GVNPRE used to use "value handles" here, so that
1505 : an expression would be VH.11 + VH.10 instead of d_3 + e_6. In
1506 : either case, the operands are really values (IE we do not expect
1507 : them to be usable without finding leaders). */
1508 :
1509 : static tree
1510 19524913 : get_representative_for (const pre_expr e, basic_block b = NULL)
1511 : {
1512 19524913 : tree name, valnum = NULL_TREE;
1513 19524913 : unsigned int value_id = get_expr_value_id (e);
1514 :
1515 19524913 : switch (e->kind)
1516 : {
1517 8965614 : case NAME:
1518 8965614 : return PRE_EXPR_NAME (e);
1519 1905444 : case CONSTANT:
1520 1905444 : return PRE_EXPR_CONSTANT (e);
1521 8653855 : case NARY:
1522 8653855 : case REFERENCE:
1523 8653855 : {
1524 : /* Go through all of the expressions representing this value
1525 : and pick out an SSA_NAME. */
1526 8653855 : unsigned int i;
1527 8653855 : bitmap_iterator bi;
1528 8653855 : bitmap exprs = value_expressions[value_id];
1529 22355375 : EXECUTE_IF_SET_IN_BITMAP (exprs, 0, i, bi)
1530 : {
1531 18312006 : pre_expr rep = expression_for_id (i);
1532 18312006 : if (rep->kind == NAME)
1533 : {
1534 8337054 : tree name = PRE_EXPR_NAME (rep);
1535 8337054 : valnum = VN_INFO (name)->valnum;
1536 8337054 : gimple *def = SSA_NAME_DEF_STMT (name);
1537 : /* We have to return either a new representative or one
1538 : that can be used for expression simplification and thus
1539 : is available in B. */
1540 8337054 : if (! b
1541 8016765 : || gimple_nop_p (def)
1542 12336164 : || dominated_by_p (CDI_DOMINATORS, b, gimple_bb (def)))
1543 4610486 : return name;
1544 : }
1545 9974952 : else if (rep->kind == CONSTANT)
1546 0 : return PRE_EXPR_CONSTANT (rep);
1547 : }
1548 : }
1549 4043369 : break;
1550 : }
1551 :
1552 : /* If we reached here we couldn't find an SSA_NAME. This can
1553 : happen when we've discovered a value that has never appeared in
1554 : the program as set to an SSA_NAME, as the result of phi translation.
1555 : Create one here.
1556 : ??? We should be able to re-use this when we insert the statement
1557 : to compute it. */
1558 4043369 : name = make_temp_ssa_name (get_expr_type (e), gimple_build_nop (), "pretmp");
1559 4043369 : vn_ssa_aux_t vn_info = VN_INFO (name);
1560 4043369 : vn_info->value_id = value_id;
1561 4043369 : vn_info->valnum = valnum ? valnum : name;
1562 4043369 : vn_info->visited = true;
1563 : /* ??? For now mark this SSA name for release by VN. */
1564 4043369 : vn_info->needs_insertion = true;
1565 4043369 : add_to_value (value_id, get_or_alloc_expr_for_name (name));
1566 4043369 : if (dump_file && (dump_flags & TDF_DETAILS))
1567 : {
1568 47 : fprintf (dump_file, "Created SSA_NAME representative ");
1569 47 : print_generic_expr (dump_file, name);
1570 47 : fprintf (dump_file, " for expression:");
1571 47 : print_pre_expr (dump_file, e);
1572 47 : fprintf (dump_file, " (%04d)\n", value_id);
1573 : }
1574 :
1575 : return name;
1576 : }
1577 :
1578 :
1579 : static pre_expr
1580 : phi_translate (bitmap_set_t, pre_expr, bitmap_set_t, bitmap_set_t, edge);
1581 :
1582 : /* Translate EXPR using phis in PHIBLOCK, so that it has the values of
1583 : the phis in PRED. Return NULL if we can't find a leader for each part
1584 : of the translated expression. */
1585 :
1586 : static pre_expr
1587 49023806 : phi_translate_1 (bitmap_set_t dest,
1588 : pre_expr expr, bitmap_set_t set1, bitmap_set_t set2, edge e)
1589 : {
1590 49023806 : basic_block pred = e->src;
1591 49023806 : basic_block phiblock = e->dest;
1592 49023806 : location_t expr_loc = expr->loc;
1593 49023806 : switch (expr->kind)
1594 : {
1595 18388158 : case NARY:
1596 18388158 : {
1597 18388158 : unsigned int i;
1598 18388158 : bool changed = false;
1599 18388158 : vn_nary_op_t nary = PRE_EXPR_NARY (expr);
1600 18388158 : vn_nary_op_t newnary = XALLOCAVAR (struct vn_nary_op_s,
1601 : sizeof_vn_nary_op (nary->length));
1602 18388158 : memcpy (newnary, nary, sizeof_vn_nary_op (nary->length));
1603 :
1604 43775084 : for (i = 0; i < newnary->length; i++)
1605 : {
1606 28714036 : if (TREE_CODE (newnary->op[i]) != SSA_NAME)
1607 8987234 : continue;
1608 : else
1609 : {
1610 19726802 : pre_expr leader, result;
1611 19726802 : unsigned int op_val_id = VN_INFO (newnary->op[i])->value_id;
1612 19726802 : leader = find_leader_in_sets (op_val_id, set1, set2);
1613 19726802 : result = phi_translate (dest, leader, set1, set2, e);
1614 19726802 : if (result)
1615 : /* If op has a leader in the sets we translate make
1616 : sure to use the value of the translated expression.
1617 : We might need a new representative for that. */
1618 16399692 : newnary->op[i] = get_representative_for (result, pred);
1619 : else if (!result)
1620 : return NULL;
1621 :
1622 16399692 : changed |= newnary->op[i] != nary->op[i];
1623 : }
1624 : }
1625 15061048 : if (changed)
1626 : {
1627 7543053 : unsigned int new_val_id;
1628 :
1629 : /* Try to simplify the new NARY. */
1630 7543053 : tree res = vn_nary_simplify (newnary);
1631 7543053 : if (res)
1632 : {
1633 2427801 : if (is_gimple_min_invariant (res))
1634 1246260 : return get_or_alloc_expr_for_constant (res);
1635 :
1636 : /* For non-CONSTANTs we have to make sure we can eventually
1637 : insert the expression. Which means we need to have a
1638 : leader for it. */
1639 1181541 : gcc_assert (TREE_CODE (res) == SSA_NAME);
1640 :
1641 : /* Do not allow simplifications to non-constants over
1642 : backedges as this will likely result in a loop PHI node
1643 : to be inserted and increased register pressure.
1644 : See PR77498 - this avoids doing predcoms work in
1645 : a less efficient way. */
1646 1181541 : if (e->flags & EDGE_DFS_BACK)
1647 : ;
1648 : else
1649 : {
1650 1098800 : unsigned value_id = VN_INFO (res)->value_id;
1651 : /* We want a leader in ANTIC_OUT or AVAIL_OUT here.
1652 : dest has what we computed into ANTIC_OUT sofar
1653 : so pick from that - since topological sorting
1654 : by sorted_array_from_bitmap_set isn't perfect
1655 : we may lose some cases here. */
1656 2197600 : pre_expr constant = find_leader_in_sets (value_id, dest,
1657 1098800 : AVAIL_OUT (pred));
1658 1098800 : if (constant)
1659 : {
1660 332539 : if (dump_file && (dump_flags & TDF_DETAILS))
1661 : {
1662 7 : fprintf (dump_file, "simplifying ");
1663 7 : print_pre_expr (dump_file, expr);
1664 7 : fprintf (dump_file, " translated %d -> %d to ",
1665 : phiblock->index, pred->index);
1666 7 : PRE_EXPR_NARY (expr) = newnary;
1667 7 : print_pre_expr (dump_file, expr);
1668 7 : PRE_EXPR_NARY (expr) = nary;
1669 7 : fprintf (dump_file, " to ");
1670 7 : print_pre_expr (dump_file, constant);
1671 7 : fprintf (dump_file, "\n");
1672 : }
1673 332539 : return constant;
1674 : }
1675 : }
1676 : }
1677 :
1678 11928508 : tree result = vn_nary_op_lookup_pieces (newnary->length,
1679 5964254 : newnary->opcode,
1680 : newnary->type,
1681 : &newnary->op[0],
1682 : &nary);
1683 5964254 : if (result && is_gimple_min_invariant (result))
1684 0 : return get_or_alloc_expr_for_constant (result);
1685 :
1686 5964254 : if (!nary || nary->predicated_values)
1687 : new_val_id = 0;
1688 : else
1689 819613 : new_val_id = nary->value_id;
1690 5964254 : expr = get_or_alloc_expr_for_nary (newnary, new_val_id, expr_loc);
1691 5964254 : add_to_value (get_expr_value_id (expr), expr);
1692 : }
1693 : return expr;
1694 : }
1695 5014016 : break;
1696 :
1697 5014016 : case REFERENCE:
1698 5014016 : {
1699 5014016 : vn_reference_t ref = PRE_EXPR_REFERENCE (expr);
1700 5014016 : vec<vn_reference_op_s> operands = ref->operands;
1701 5014016 : tree vuse = ref->vuse;
1702 5014016 : tree newvuse = vuse;
1703 5014016 : vec<vn_reference_op_s> newoperands = vNULL;
1704 5014016 : bool changed = false, same_valid = true;
1705 5014016 : unsigned int i, n;
1706 5014016 : vn_reference_op_t operand;
1707 5014016 : vn_reference_t newref;
1708 :
1709 19182682 : for (i = 0; operands.iterate (i, &operand); i++)
1710 : {
1711 14523725 : pre_expr opresult;
1712 14523725 : pre_expr leader;
1713 14523725 : tree op[3];
1714 14523725 : tree type = operand->type;
1715 14523725 : vn_reference_op_s newop = *operand;
1716 14523725 : op[0] = operand->op0;
1717 14523725 : op[1] = operand->op1;
1718 14523725 : op[2] = operand->op2;
1719 57029779 : for (n = 0; n < 3; ++n)
1720 : {
1721 42861113 : unsigned int op_val_id;
1722 42861113 : if (!op[n])
1723 26027352 : continue;
1724 16833761 : if (TREE_CODE (op[n]) != SSA_NAME)
1725 : {
1726 : /* We can't possibly insert these. */
1727 13353481 : if (n != 0
1728 13353481 : && !is_gimple_min_invariant (op[n]))
1729 : break;
1730 13353481 : continue;
1731 : }
1732 3480280 : op_val_id = VN_INFO (op[n])->value_id;
1733 3480280 : leader = find_leader_in_sets (op_val_id, set1, set2);
1734 3480280 : opresult = phi_translate (dest, leader, set1, set2, e);
1735 3480280 : if (opresult)
1736 : {
1737 3125221 : tree name = get_representative_for (opresult);
1738 3125221 : changed |= name != op[n];
1739 3125221 : op[n] = name;
1740 : }
1741 : else if (!opresult)
1742 : break;
1743 : }
1744 14523725 : if (n != 3)
1745 : {
1746 355059 : newoperands.release ();
1747 355059 : return NULL;
1748 : }
1749 : /* When we translate a MEM_REF across a backedge and we have
1750 : restrict info that's not from our functions parameters
1751 : we have to remap it since we now may deal with a different
1752 : instance where the dependence info is no longer valid.
1753 : See PR102970. Note instead of keeping a remapping table
1754 : per backedge we simply throw away restrict info. */
1755 14168666 : if ((newop.opcode == MEM_REF
1756 14168666 : || newop.opcode == TARGET_MEM_REF)
1757 4764099 : && newop.clique > 1
1758 159431 : && (e->flags & EDGE_DFS_BACK))
1759 : {
1760 : newop.clique = 0;
1761 : newop.base = 0;
1762 : changed = true;
1763 : }
1764 14149913 : if (!changed)
1765 11693478 : continue;
1766 2475188 : if (!newoperands.exists ())
1767 1278786 : newoperands = operands.copy ();
1768 : /* We may have changed from an SSA_NAME to a constant */
1769 2475188 : if (newop.opcode == SSA_NAME && TREE_CODE (op[0]) != SSA_NAME)
1770 : newop.opcode = TREE_CODE (op[0]);
1771 2475188 : newop.type = type;
1772 2475188 : newop.op0 = op[0];
1773 2475188 : newop.op1 = op[1];
1774 2475188 : newop.op2 = op[2];
1775 2475188 : newoperands[i] = newop;
1776 : }
1777 9317914 : gcc_checking_assert (i == operands.length ());
1778 :
1779 4658957 : if (vuse)
1780 : {
1781 11138368 : newvuse = translate_vuse_through_block (newoperands.exists ()
1782 4543900 : ? newoperands : operands,
1783 : ref->set, ref->base_set,
1784 : ref->type, vuse, e,
1785 : changed
1786 : ? NULL : &same_valid);
1787 4543900 : if (newvuse == NULL_TREE)
1788 : {
1789 0 : newoperands.release ();
1790 0 : return NULL;
1791 : }
1792 : }
1793 :
1794 4658957 : if (changed || newvuse != vuse)
1795 : {
1796 3272967 : unsigned int new_val_id;
1797 :
1798 5268371 : tree result = vn_reference_lookup_pieces (newvuse, ref->set,
1799 : ref->base_set,
1800 : ref->type,
1801 3272967 : newoperands.exists ()
1802 3272967 : ? newoperands : operands,
1803 : &newref, VN_WALK);
1804 :
1805 : /* We can always insert constants, so if we have a partial
1806 : redundant constant load of another type try to translate it
1807 : to a constant of appropriate type. */
1808 3272967 : if (result && is_gimple_min_invariant (result))
1809 : {
1810 77642 : tree tem = result;
1811 77642 : if (!useless_type_conversion_p (ref->type, TREE_TYPE (result)))
1812 : {
1813 85 : tem = fold_unary (VIEW_CONVERT_EXPR, ref->type, result);
1814 85 : if (tem && !is_gimple_min_invariant (tem))
1815 : tem = NULL_TREE;
1816 : }
1817 77642 : if (tem)
1818 : {
1819 77642 : newoperands.release ();
1820 77642 : return get_or_alloc_expr_for_constant (tem);
1821 : }
1822 : }
1823 :
1824 : /* If we'd have to convert things we would need to validate
1825 : if we can insert the translated expression. So fail
1826 : here for now - we cannot insert an alias with a different
1827 : type in the VN tables either, as that would assert. */
1828 3195325 : if (result
1829 3195325 : && !useless_type_conversion_p (ref->type, TREE_TYPE (result)))
1830 : {
1831 1004 : newoperands.release ();
1832 1004 : return NULL;
1833 : }
1834 2626767 : else if (!result && newref
1835 3194321 : && !useless_type_conversion_p (ref->type, newref->type))
1836 : {
1837 0 : newoperands.release ();
1838 0 : return NULL;
1839 : }
1840 :
1841 3194321 : if (newref)
1842 : {
1843 567554 : new_val_id = newref->value_id;
1844 567554 : newvuse = newref->vuse;
1845 : }
1846 : else
1847 : {
1848 2626767 : if (changed || !same_valid)
1849 : new_val_id = 0;
1850 : else
1851 131536 : new_val_id = ref->value_id;
1852 : }
1853 3194321 : newref = XALLOCAVAR (struct vn_reference_s,
1854 : sizeof (vn_reference_s));
1855 3194321 : memcpy (newref, ref, sizeof (vn_reference_s));
1856 3194321 : newref->next = NULL;
1857 3194321 : newref->value_id = new_val_id;
1858 3194321 : newref->vuse = newvuse;
1859 6388642 : newref->operands
1860 3194321 : = newoperands.exists () ? newoperands : operands.copy ();
1861 3194321 : newoperands = vNULL;
1862 3194321 : newref->type = ref->type;
1863 3194321 : newref->result = result;
1864 3194321 : newref->hashcode = vn_reference_compute_hash (newref);
1865 3194321 : expr = get_or_alloc_expr_for_reference (newref, new_val_id,
1866 : expr_loc, true);
1867 3194321 : add_to_value (get_expr_value_id (expr), expr);
1868 : }
1869 4580311 : newoperands.release ();
1870 4580311 : return expr;
1871 : }
1872 25621632 : break;
1873 :
1874 25621632 : case NAME:
1875 25621632 : {
1876 25621632 : tree name = PRE_EXPR_NAME (expr);
1877 25621632 : gimple *def_stmt = SSA_NAME_DEF_STMT (name);
1878 : /* If the SSA name is defined by a PHI node in this block,
1879 : translate it. */
1880 25621632 : if (gimple_code (def_stmt) == GIMPLE_PHI
1881 25621632 : && gimple_bb (def_stmt) == phiblock)
1882 : {
1883 7996625 : tree def = PHI_ARG_DEF (def_stmt, e->dest_idx);
1884 :
1885 : /* Handle constant. */
1886 7996625 : if (is_gimple_min_invariant (def))
1887 2324314 : return get_or_alloc_expr_for_constant (def);
1888 :
1889 5672311 : return get_or_alloc_expr_for_name (def);
1890 : }
1891 : /* Otherwise return it unchanged - it will get removed if its
1892 : value is not available in PREDs AVAIL_OUT set of expressions
1893 : by the subtraction of TMP_GEN. */
1894 : return expr;
1895 : }
1896 :
1897 0 : default:
1898 0 : gcc_unreachable ();
1899 : }
1900 : }
1901 :
1902 : /* Wrapper around phi_translate_1 providing caching functionality. */
1903 :
1904 : static pre_expr
1905 90136403 : phi_translate (bitmap_set_t dest, pre_expr expr,
1906 : bitmap_set_t set1, bitmap_set_t set2, edge e)
1907 : {
1908 90136403 : expr_pred_trans_t slot = NULL;
1909 90136403 : pre_expr phitrans;
1910 :
1911 90136403 : if (!expr)
1912 : return NULL;
1913 :
1914 : /* Constants contain no values that need translation. */
1915 88300055 : if (expr->kind == CONSTANT)
1916 : return expr;
1917 :
1918 88299869 : if (value_id_constant_p (get_expr_value_id (expr)))
1919 : return expr;
1920 :
1921 : /* Don't add translations of NAMEs as those are cheap to translate. */
1922 88299869 : if (expr->kind != NAME)
1923 : {
1924 62678237 : if (phi_trans_add (&slot, expr, e->src))
1925 39276063 : return slot->v == 0 ? NULL : expression_for_id (slot->v);
1926 : /* Store NULL for the value we want to return in the case of
1927 : recursing. */
1928 23402174 : slot->v = 0;
1929 : }
1930 :
1931 : /* Translate. */
1932 49023806 : basic_block saved_valueize_bb = vn_context_bb;
1933 49023806 : vn_context_bb = e->src;
1934 49023806 : phitrans = phi_translate_1 (dest, expr, set1, set2, e);
1935 49023806 : vn_context_bb = saved_valueize_bb;
1936 :
1937 49023806 : if (slot)
1938 : {
1939 : /* We may have reallocated. */
1940 23402174 : phi_trans_add (&slot, expr, e->src);
1941 23402174 : if (phitrans)
1942 19719001 : slot->v = get_expression_id (phitrans);
1943 : else
1944 : /* Remove failed translations again, they cause insert
1945 : iteration to not pick up new opportunities reliably. */
1946 3683173 : PHI_TRANS_TABLE (e->src)->clear_slot (slot);
1947 : }
1948 :
1949 : return phitrans;
1950 : }
1951 :
1952 :
1953 : /* For each expression in SET, translate the values through phi nodes
1954 : in PHIBLOCK using edge PHIBLOCK->PRED, and store the resulting
1955 : expressions in DEST. */
1956 :
1957 : static void
1958 20648489 : phi_translate_set (bitmap_set_t dest, bitmap_set_t set, edge e)
1959 : {
1960 20648489 : bitmap_iterator bi;
1961 20648489 : unsigned int i;
1962 :
1963 20648489 : if (gimple_seq_empty_p (phi_nodes (e->dest)))
1964 : {
1965 13808194 : bitmap_set_copy (dest, set);
1966 13808194 : return;
1967 : }
1968 :
1969 : /* Allocate the phi-translation cache where we have an idea about
1970 : its size. hash-table implementation internals tell us that
1971 : allocating the table to fit twice the number of elements will
1972 : make sure we do not usually re-allocate. */
1973 6840295 : if (!PHI_TRANS_TABLE (e->src))
1974 5974252 : PHI_TRANS_TABLE (e->src) = new hash_table<expr_pred_trans_d>
1975 5974252 : (2 * bitmap_count_bits (&set->expressions));
1976 45572669 : FOR_EACH_EXPR_ID_IN_SET (set, i, bi)
1977 : {
1978 38732374 : pre_expr expr = expression_for_id (i);
1979 38732374 : pre_expr translated = phi_translate (dest, expr, set, NULL, e);
1980 38732374 : if (!translated)
1981 1836485 : continue;
1982 :
1983 36895889 : bitmap_insert_into_set (dest, translated);
1984 : }
1985 : }
1986 :
1987 : /* Find the leader for a value (i.e., the name representing that
1988 : value) in a given set, and return it. Return NULL if no leader
1989 : is found. */
1990 :
1991 : static pre_expr
1992 56915208 : bitmap_find_leader (bitmap_set_t set, unsigned int val)
1993 : {
1994 56915208 : if (value_id_constant_p (val))
1995 1769093 : return constant_value_expressions[-val];
1996 :
1997 55146115 : if (bitmap_set_contains_value (set, val))
1998 : {
1999 : /* Rather than walk the entire bitmap of expressions, and see
2000 : whether any of them has the value we are looking for, we look
2001 : at the reverse mapping, which tells us the set of expressions
2002 : that have a given value (IE value->expressions with that
2003 : value) and see if any of those expressions are in our set.
2004 : The number of expressions per value is usually significantly
2005 : less than the number of expressions in the set. In fact, for
2006 : large testcases, doing it this way is roughly 5-10x faster
2007 : than walking the bitmap.
2008 : If this is somehow a significant lose for some cases, we can
2009 : choose which set to walk based on which set is smaller. */
2010 25799999 : unsigned int i;
2011 25799999 : bitmap_iterator bi;
2012 25799999 : bitmap exprset = value_expressions[val];
2013 :
2014 25799999 : if (!exprset->first->next)
2015 32734045 : EXECUTE_IF_SET_IN_BITMAP (exprset, 0, i, bi)
2016 30303356 : if (bitmap_bit_p (&set->expressions, i))
2017 23275996 : return expression_for_id (i);
2018 :
2019 6468382 : EXECUTE_IF_AND_IN_BITMAP (exprset, &set->expressions, 0, i, bi)
2020 3944379 : return expression_for_id (i);
2021 : }
2022 : return NULL;
2023 : }
2024 :
2025 : /* Determine if EXPR, a memory expression, is ANTIC_IN at the top of
2026 : BLOCK by seeing if it is not killed in the block. Note that we are
2027 : only determining whether there is a store that kills it. Because
2028 : of the order in which clean iterates over values, we are guaranteed
2029 : that altered operands will have caused us to be eliminated from the
2030 : ANTIC_IN set already. */
2031 :
2032 : static bool
2033 1650759 : value_dies_in_block_x (pre_expr expr, basic_block block)
2034 : {
2035 1650759 : tree vuse = PRE_EXPR_REFERENCE (expr)->vuse;
2036 1650759 : vn_reference_t refx = PRE_EXPR_REFERENCE (expr);
2037 1650759 : gimple *def;
2038 1650759 : gimple_stmt_iterator gsi;
2039 1650759 : unsigned id = get_expression_id (expr);
2040 1650759 : bool res = false;
2041 1650759 : ao_ref ref;
2042 :
2043 1650759 : if (!vuse)
2044 : return false;
2045 :
2046 : /* Lookup a previously calculated result. */
2047 1650759 : if (EXPR_DIES (block)
2048 1650759 : && bitmap_bit_p (EXPR_DIES (block), id * 2))
2049 135035 : return bitmap_bit_p (EXPR_DIES (block), id * 2 + 1);
2050 :
2051 : /* A memory expression {e, VUSE} dies in the block if there is a
2052 : statement that may clobber e. If, starting statement walk from the
2053 : top of the basic block, a statement uses VUSE there can be no kill
2054 : in between that use and the original statement that loaded {e, VUSE},
2055 : so we can stop walking. */
2056 1515724 : ref.base = NULL_TREE;
2057 13715759 : for (gsi = gsi_start_bb (block); !gsi_end_p (gsi); gsi_next (&gsi))
2058 : {
2059 11727287 : tree def_vuse, def_vdef;
2060 11727287 : def = gsi_stmt (gsi);
2061 11727287 : def_vuse = gimple_vuse (def);
2062 11727287 : def_vdef = gimple_vdef (def);
2063 :
2064 : /* Not a memory statement. */
2065 11727287 : if (!def_vuse)
2066 8403222 : continue;
2067 :
2068 : /* Not a may-def. */
2069 3324065 : if (!def_vdef)
2070 : {
2071 : /* A load with the same VUSE, we're done. */
2072 955448 : if (def_vuse == vuse)
2073 : break;
2074 :
2075 668040 : continue;
2076 : }
2077 :
2078 : /* Init ref only if we really need it. */
2079 2368617 : if (ref.base == NULL_TREE
2080 3514651 : && !ao_ref_init_from_vn_reference (&ref, refx->set, refx->base_set,
2081 1146034 : refx->type, refx->operands))
2082 : {
2083 : res = true;
2084 : break;
2085 : }
2086 : /* If the statement may clobber expr, it dies. */
2087 2334461 : if (stmt_may_clobber_ref_p_1 (def, &ref))
2088 : {
2089 : res = true;
2090 : break;
2091 : }
2092 : }
2093 :
2094 : /* Remember the result. */
2095 1515724 : if (!EXPR_DIES (block))
2096 711436 : EXPR_DIES (block) = BITMAP_ALLOC (&grand_bitmap_obstack);
2097 1515724 : bitmap_set_bit (EXPR_DIES (block), id * 2);
2098 1515724 : if (res)
2099 755568 : bitmap_set_bit (EXPR_DIES (block), id * 2 + 1);
2100 :
2101 : return res;
2102 : }
2103 :
2104 :
2105 : /* Determine if OP is valid in SET1 U SET2, which it is when the union
2106 : contains its value-id. */
2107 :
2108 : static bool
2109 274070440 : op_valid_in_sets (bitmap_set_t set1, bitmap_set_t set2, tree op)
2110 : {
2111 274070440 : if (op && TREE_CODE (op) == SSA_NAME)
2112 : {
2113 81656201 : unsigned int value_id = VN_INFO (op)->value_id;
2114 163309326 : if (!(bitmap_set_contains_value (set1, value_id)
2115 2281117 : || (set2 && bitmap_set_contains_value (set2, value_id))))
2116 2329163 : return false;
2117 : }
2118 : return true;
2119 : }
2120 :
2121 : /* Determine if the expression EXPR is valid in SET1 U SET2.
2122 : ONLY SET2 CAN BE NULL.
2123 : This means that we have a leader for each part of the expression
2124 : (if it consists of values), or the expression is an SSA_NAME.
2125 : For loads/calls, we also see if the vuse is killed in this block. */
2126 :
2127 : static bool
2128 130195688 : valid_in_sets (bitmap_set_t set1, bitmap_set_t set2, pre_expr expr)
2129 : {
2130 130195688 : switch (expr->kind)
2131 : {
2132 : case NAME:
2133 : /* By construction all NAMEs are available. Non-available
2134 : NAMEs are removed by subtracting TMP_GEN from the sets. */
2135 : return true;
2136 59089351 : case NARY:
2137 59089351 : {
2138 59089351 : unsigned int i;
2139 59089351 : vn_nary_op_t nary = PRE_EXPR_NARY (expr);
2140 154734646 : for (i = 0; i < nary->length; i++)
2141 97811909 : if (!op_valid_in_sets (set1, set2, nary->op[i]))
2142 : return false;
2143 : return true;
2144 : }
2145 20141985 : break;
2146 20141985 : case REFERENCE:
2147 20141985 : {
2148 20141985 : vn_reference_t ref = PRE_EXPR_REFERENCE (expr);
2149 20141985 : vn_reference_op_t vro;
2150 20141985 : unsigned int i;
2151 :
2152 78840619 : FOR_EACH_VEC_ELT (ref->operands, i, vro)
2153 : {
2154 58861183 : if (!op_valid_in_sets (set1, set2, vro->op0)
2155 58698674 : || !op_valid_in_sets (set1, set2, vro->op1)
2156 117559857 : || !op_valid_in_sets (set1, set2, vro->op2))
2157 162549 : return false;
2158 : }
2159 : return true;
2160 : }
2161 0 : default:
2162 0 : gcc_unreachable ();
2163 : }
2164 : }
2165 :
2166 : /* Clean the set of expressions SET1 that are no longer valid in SET1 or SET2.
2167 : This means expressions that are made up of values we have no leaders for
2168 : in SET1 or SET2. */
2169 :
2170 : static void
2171 14560891 : clean (bitmap_set_t set1, bitmap_set_t set2 = NULL)
2172 : {
2173 14560891 : vec<pre_expr> exprs = sorted_array_from_bitmap_set (set1, false);
2174 15525570 : bool changed;
2175 :
2176 15525570 : do
2177 : {
2178 15525570 : unsigned j = 0;
2179 15525570 : changed = false;
2180 84360323 : for (unsigned i = 0; i < exprs.length (); ++i)
2181 : {
2182 68834753 : pre_expr expr = exprs[i];
2183 68834753 : if (!valid_in_sets (set1, set2, expr))
2184 : {
2185 2329154 : unsigned int val = get_expr_value_id (expr);
2186 2329154 : bitmap_clear_bit (&set1->expressions, get_expression_id (expr));
2187 : /* We are entered with possibly multiple expressions for a value
2188 : so before removing a value from the set see if there's an
2189 : expression for it left. */
2190 2329154 : if (! bitmap_find_leader (set1, val))
2191 : {
2192 2318495 : bitmap_clear_bit (&set1->values, val);
2193 2318495 : changed = true;
2194 : }
2195 : }
2196 : else
2197 : {
2198 66505599 : exprs[j] = expr;
2199 66505599 : ++j;
2200 : }
2201 : }
2202 15525570 : exprs.truncate (j);
2203 : }
2204 : /* As the value graph can have cycles we have to iterate here. */
2205 : while (changed);
2206 14560891 : exprs.release ();
2207 :
2208 14560891 : if (flag_checking)
2209 : {
2210 14560704 : unsigned j;
2211 14560704 : bitmap_iterator bi;
2212 75698936 : FOR_EACH_EXPR_ID_IN_SET (set1, j, bi)
2213 61138232 : gcc_assert (valid_in_sets (set1, set2, expression_for_id (j)));
2214 : }
2215 14560891 : }
2216 :
2217 : /* Clean the set of expressions that are no longer valid in SET because
2218 : they are clobbered in BLOCK or because they trap and may not be executed.
2219 : When CLEAN_TRAPS is true remove all possibly trapping expressions. */
2220 :
2221 : static void
2222 16978621 : prune_clobbered_mems (bitmap_set_t set, basic_block block, bool clean_traps)
2223 : {
2224 16978621 : bitmap_iterator bi;
2225 16978621 : unsigned i;
2226 16978621 : unsigned to_remove = -1U;
2227 16978621 : bool any_removed = false;
2228 :
2229 77460270 : FOR_EACH_EXPR_ID_IN_SET (set, i, bi)
2230 : {
2231 : /* Remove queued expr. */
2232 60481649 : if (to_remove != -1U)
2233 : {
2234 596480 : bitmap_clear_bit (&set->expressions, to_remove);
2235 596480 : any_removed = true;
2236 596480 : to_remove = -1U;
2237 : }
2238 :
2239 60481649 : pre_expr expr = expression_for_id (i);
2240 60481649 : if (expr->kind == REFERENCE)
2241 : {
2242 8173342 : vn_reference_t ref = PRE_EXPR_REFERENCE (expr);
2243 8173342 : if (ref->vuse)
2244 : {
2245 7421545 : gimple *def_stmt = SSA_NAME_DEF_STMT (ref->vuse);
2246 7421545 : if (!gimple_nop_p (def_stmt)
2247 : /* If value-numbering provided a memory state for this
2248 : that dominates BLOCK we're done, otherwise we have
2249 : to check if the value dies in BLOCK. */
2250 9109701 : && !(gimple_bb (def_stmt) != block
2251 3839492 : && dominated_by_p (CDI_DOMINATORS,
2252 3839492 : block, gimple_bb (def_stmt)))
2253 9072304 : && value_dies_in_block_x (expr, block))
2254 : to_remove = i;
2255 : }
2256 : /* If the REFERENCE may trap make sure the block does not contain
2257 : a possible exit point.
2258 : ??? This is overly conservative if we translate AVAIL_OUT
2259 : as the available expression might be after the exit point. */
2260 7487877 : if ((BB_MAY_NOTRETURN (block) || clean_traps)
2261 8425312 : && vn_reference_may_trap (ref))
2262 : to_remove = i;
2263 : }
2264 52308307 : else if (expr->kind == NARY)
2265 : {
2266 27703540 : vn_nary_op_t nary = PRE_EXPR_NARY (expr);
2267 : /* If the NARY may trap make sure the block does not contain
2268 : a possible exit point.
2269 : ??? This is overly conservative if we translate AVAIL_OUT
2270 : as the available expression might be after the exit point. */
2271 23527337 : if ((BB_MAY_NOTRETURN (block) || clean_traps)
2272 28576090 : && vn_nary_may_trap (nary))
2273 : to_remove = i;
2274 : }
2275 : }
2276 :
2277 : /* Remove queued expr. */
2278 16978621 : if (to_remove != -1U)
2279 : {
2280 427584 : bitmap_clear_bit (&set->expressions, to_remove);
2281 427584 : any_removed = true;
2282 : }
2283 :
2284 : /* Above we only removed expressions, now clean the set of values
2285 : which no longer have any corresponding expression. We cannot
2286 : clear the value at the time we remove an expression since there
2287 : may be multiple expressions per value.
2288 : If we'd queue possibly to be removed values we could use
2289 : the bitmap_find_leader way to see if there's still an expression
2290 : for it. For some ratio of to be removed values and number of
2291 : values/expressions in the set this might be faster than rebuilding
2292 : the value-set.
2293 : Note when there's a MAX solution on one edge (clean_traps) do not
2294 : prune values as we need to consider the resulting expression set MAX
2295 : as well. This avoids a later growing ANTIC_IN value-set during
2296 : iteration, when the explicitly represented expression set grows. */
2297 16978621 : if (any_removed && !clean_traps)
2298 : {
2299 493567 : bitmap_clear (&set->values);
2300 2766651 : FOR_EACH_EXPR_ID_IN_SET (set, i, bi)
2301 : {
2302 2273084 : pre_expr expr = expression_for_id (i);
2303 2273084 : unsigned int value_id = get_expr_value_id (expr);
2304 2273084 : bitmap_set_bit (&set->values, value_id);
2305 : }
2306 : }
2307 16978621 : }
2308 :
2309 : /* Compute the ANTIC set for BLOCK.
2310 :
2311 : If succs(BLOCK) > 1 then
2312 : ANTIC_OUT[BLOCK] = intersection of ANTIC_IN[b] for all succ(BLOCK)
2313 : else if succs(BLOCK) == 1 then
2314 : ANTIC_OUT[BLOCK] = phi_translate (ANTIC_IN[succ(BLOCK)])
2315 :
2316 : ANTIC_IN[BLOCK] = clean(ANTIC_OUT[BLOCK] U EXP_GEN[BLOCK] - TMP_GEN[BLOCK])
2317 :
2318 : Note that clean() is deferred until after the iteration. */
2319 :
2320 : static bool
2321 15760001 : compute_antic_aux (basic_block block, bool block_has_abnormal_pred_edge)
2322 : {
2323 15760001 : bitmap_set_t S, old, ANTIC_OUT;
2324 15760001 : edge e;
2325 15760001 : edge_iterator ei;
2326 :
2327 15760001 : bool was_visited = BB_VISITED (block);
2328 15760001 : bool changed = ! BB_VISITED (block);
2329 15760001 : bool any_max_on_edge = false;
2330 :
2331 15760001 : BB_VISITED (block) = 1;
2332 15760001 : old = ANTIC_OUT = S = NULL;
2333 :
2334 : /* If any edges from predecessors are abnormal, antic_in is empty,
2335 : so do nothing. */
2336 15760001 : if (block_has_abnormal_pred_edge)
2337 4406 : goto maybe_dump_sets;
2338 :
2339 15755595 : old = ANTIC_IN (block);
2340 15755595 : ANTIC_OUT = bitmap_set_new ();
2341 :
2342 : /* If the block has no successors, ANTIC_OUT is empty. */
2343 15755595 : if (EDGE_COUNT (block->succs) == 0)
2344 : ;
2345 : /* If we have one successor, we could have some phi nodes to
2346 : translate through. */
2347 15755595 : else if (single_succ_p (block))
2348 : {
2349 10057066 : e = single_succ_edge (block);
2350 10057066 : gcc_assert (BB_VISITED (e->dest));
2351 10057066 : phi_translate_set (ANTIC_OUT, ANTIC_IN (e->dest), e);
2352 : }
2353 : /* If we have multiple successors, we take the intersection of all of
2354 : them. Note that in the case of loop exit phi nodes, we may have
2355 : phis to translate through. */
2356 : else
2357 : {
2358 5698529 : size_t i;
2359 5698529 : edge first = NULL;
2360 :
2361 5698529 : auto_vec<edge> worklist (EDGE_COUNT (block->succs));
2362 17200245 : FOR_EACH_EDGE (e, ei, block->succs)
2363 : {
2364 11501716 : if (!first
2365 6170419 : && BB_VISITED (e->dest))
2366 : first = e;
2367 5803187 : else if (BB_VISITED (e->dest))
2368 5145293 : worklist.quick_push (e);
2369 : else
2370 : {
2371 : /* Unvisited successors get their ANTIC_IN replaced by the
2372 : maximal set to arrive at a maximum ANTIC_IN solution.
2373 : We can ignore them in the intersection operation and thus
2374 : need not explicitly represent that maximum solution. */
2375 657894 : any_max_on_edge = true;
2376 657894 : if (dump_file && (dump_flags & TDF_DETAILS))
2377 18 : fprintf (dump_file, "ANTIC_IN is MAX on %d->%d\n",
2378 18 : e->src->index, e->dest->index);
2379 : }
2380 : }
2381 :
2382 : /* Of multiple successors we have to have visited one already
2383 : which is guaranteed by iteration order. */
2384 5698529 : gcc_assert (first != NULL);
2385 :
2386 5698529 : phi_translate_set (ANTIC_OUT, ANTIC_IN (first->dest), first);
2387 :
2388 : /* If we have multiple successors we need to intersect the ANTIC_OUT
2389 : sets. For values that's a simple intersection but for
2390 : expressions it is a union. Given we want to have a single
2391 : expression per value in our sets we have to canonicalize.
2392 : Avoid randomness and running into cycles like for PR82129 and
2393 : canonicalize the expression we choose to the one with the
2394 : lowest id. This requires we actually compute the union first. */
2395 10843822 : FOR_EACH_VEC_ELT (worklist, i, e)
2396 : {
2397 5145293 : if (!gimple_seq_empty_p (phi_nodes (e->dest)))
2398 : {
2399 2370 : bitmap_set_t tmp = bitmap_set_new ();
2400 2370 : phi_translate_set (tmp, ANTIC_IN (e->dest), e);
2401 2370 : bitmap_and_into (&ANTIC_OUT->values, &tmp->values);
2402 2370 : bitmap_ior_into (&ANTIC_OUT->expressions, &tmp->expressions);
2403 2370 : bitmap_set_free (tmp);
2404 : }
2405 : else
2406 : {
2407 5142923 : bitmap_and_into (&ANTIC_OUT->values, &ANTIC_IN (e->dest)->values);
2408 5142923 : bitmap_ior_into (&ANTIC_OUT->expressions,
2409 5142923 : &ANTIC_IN (e->dest)->expressions);
2410 : }
2411 : }
2412 11397058 : if (! worklist.is_empty ())
2413 : {
2414 : /* Prune expressions not in the value set. */
2415 5044249 : bitmap_iterator bi;
2416 5044249 : unsigned int i;
2417 5044249 : unsigned int to_clear = -1U;
2418 36708934 : FOR_EACH_EXPR_ID_IN_SET (ANTIC_OUT, i, bi)
2419 : {
2420 31664685 : if (to_clear != -1U)
2421 : {
2422 16685070 : bitmap_clear_bit (&ANTIC_OUT->expressions, to_clear);
2423 16685070 : to_clear = -1U;
2424 : }
2425 31664685 : pre_expr expr = expression_for_id (i);
2426 31664685 : unsigned int value_id = get_expr_value_id (expr);
2427 31664685 : if (!bitmap_bit_p (&ANTIC_OUT->values, value_id))
2428 20431731 : to_clear = i;
2429 : }
2430 5044249 : if (to_clear != -1U)
2431 3746661 : bitmap_clear_bit (&ANTIC_OUT->expressions, to_clear);
2432 : }
2433 5698529 : }
2434 :
2435 : /* Dump ANTIC_OUT before it's pruned. */
2436 15755595 : if (dump_file && (dump_flags & TDF_DETAILS))
2437 151 : print_bitmap_set (dump_file, ANTIC_OUT, "ANTIC_OUT", block->index);
2438 :
2439 : /* Prune expressions that are clobbered in block and thus become
2440 : invalid if translated from ANTIC_OUT to ANTIC_IN. */
2441 15755595 : prune_clobbered_mems (ANTIC_OUT, block, any_max_on_edge);
2442 :
2443 : /* Generate ANTIC_OUT - TMP_GEN. Note when there's a MAX solution
2444 : on one edge do not prune values as we need to consider the resulting
2445 : expression set MAX as well. This avoids a later growing ANTIC_IN
2446 : value-set during iteration, when the explicitly represented
2447 : expression set grows. */
2448 15755595 : S = bitmap_set_subtract_expressions (ANTIC_OUT, TMP_GEN (block),
2449 : any_max_on_edge);
2450 :
2451 : /* Start ANTIC_IN with EXP_GEN - TMP_GEN. */
2452 31511190 : ANTIC_IN (block) = bitmap_set_subtract_expressions (EXP_GEN (block),
2453 15755595 : TMP_GEN (block));
2454 :
2455 : /* Then union in the ANTIC_OUT - TMP_GEN values,
2456 : to get ANTIC_OUT U EXP_GEN - TMP_GEN */
2457 15755595 : bitmap_ior_into (&ANTIC_IN (block)->values, &S->values);
2458 15755595 : bitmap_ior_into (&ANTIC_IN (block)->expressions, &S->expressions);
2459 :
2460 : /* clean (ANTIC_IN (block)) is deferred to after the iteration converged
2461 : because it can cause non-convergence, see for example PR81181. */
2462 :
2463 15755595 : if (was_visited
2464 15755595 : && bitmap_and_into (&ANTIC_IN (block)->values, &old->values))
2465 : {
2466 1984 : if (dump_file && (dump_flags & TDF_DETAILS))
2467 0 : fprintf (dump_file, "warning: intersecting with old ANTIC_IN "
2468 : "shrinks the set\n");
2469 : /* Prune expressions not in the value set. */
2470 1984 : bitmap_iterator bi;
2471 1984 : unsigned int i;
2472 1984 : unsigned int to_clear = -1U;
2473 21523 : FOR_EACH_EXPR_ID_IN_SET (ANTIC_IN (block), i, bi)
2474 : {
2475 19539 : if (to_clear != -1U)
2476 : {
2477 1594 : bitmap_clear_bit (&ANTIC_IN (block)->expressions, to_clear);
2478 1594 : to_clear = -1U;
2479 : }
2480 19539 : pre_expr expr = expression_for_id (i);
2481 19539 : unsigned int value_id = get_expr_value_id (expr);
2482 19539 : if (!bitmap_bit_p (&ANTIC_IN (block)->values, value_id))
2483 2977 : to_clear = i;
2484 : }
2485 1984 : if (to_clear != -1U)
2486 1383 : bitmap_clear_bit (&ANTIC_IN (block)->expressions, to_clear);
2487 : }
2488 :
2489 15755595 : if (!bitmap_set_equal (old, ANTIC_IN (block)))
2490 10273936 : changed = true;
2491 :
2492 5481659 : maybe_dump_sets:
2493 15760001 : if (dump_file && (dump_flags & TDF_DETAILS))
2494 : {
2495 151 : if (changed)
2496 129 : fprintf (dump_file, "[changed] ");
2497 151 : print_bitmap_set (dump_file, ANTIC_IN (block), "ANTIC_IN",
2498 : block->index);
2499 :
2500 151 : if (S)
2501 151 : print_bitmap_set (dump_file, S, "S", block->index);
2502 : }
2503 15760001 : if (old)
2504 15755595 : bitmap_set_free (old);
2505 15760001 : if (S)
2506 15755595 : bitmap_set_free (S);
2507 15760001 : if (ANTIC_OUT)
2508 15755595 : bitmap_set_free (ANTIC_OUT);
2509 15760001 : return changed;
2510 : }
2511 :
2512 : /* Compute PARTIAL_ANTIC for BLOCK.
2513 :
2514 : If succs(BLOCK) > 1 then
2515 : PA_OUT[BLOCK] = value wise union of PA_IN[b] + all ANTIC_IN not
2516 : in ANTIC_OUT for all succ(BLOCK)
2517 : else if succs(BLOCK) == 1 then
2518 : PA_OUT[BLOCK] = phi_translate (PA_IN[succ(BLOCK)])
2519 :
2520 : PA_IN[BLOCK] = clean(PA_OUT[BLOCK] - TMP_GEN[BLOCK] - ANTIC_IN[BLOCK])
2521 :
2522 : */
2523 : static void
2524 1224338 : compute_partial_antic_aux (basic_block block,
2525 : bool block_has_abnormal_pred_edge)
2526 : {
2527 1224338 : bitmap_set_t old_PA_IN;
2528 1224338 : bitmap_set_t PA_OUT;
2529 1224338 : edge e;
2530 1224338 : edge_iterator ei;
2531 1224338 : unsigned long max_pa = param_max_partial_antic_length;
2532 :
2533 1224338 : old_PA_IN = PA_OUT = NULL;
2534 :
2535 : /* If any edges from predecessors are abnormal, antic_in is empty,
2536 : so do nothing. */
2537 1224338 : if (block_has_abnormal_pred_edge)
2538 777 : goto maybe_dump_sets;
2539 :
2540 : /* If there are too many partially anticipatable values in the
2541 : block, phi_translate_set can take an exponential time: stop
2542 : before the translation starts. */
2543 1223561 : if (max_pa
2544 1132809 : && single_succ_p (block)
2545 1989723 : && bitmap_count_bits (&PA_IN (single_succ (block))->values) > max_pa)
2546 535 : goto maybe_dump_sets;
2547 :
2548 1223026 : old_PA_IN = PA_IN (block);
2549 1223026 : PA_OUT = bitmap_set_new ();
2550 :
2551 : /* If the block has no successors, ANTIC_OUT is empty. */
2552 1223026 : if (EDGE_COUNT (block->succs) == 0)
2553 : ;
2554 : /* If we have one successor, we could have some phi nodes to
2555 : translate through. Note that we can't phi translate across DFS
2556 : back edges in partial antic, because it uses a union operation on
2557 : the successors. For recurrences like IV's, we will end up
2558 : generating a new value in the set on each go around (i + 3 (VH.1)
2559 : VH.1 + 1 (VH.2), VH.2 + 1 (VH.3), etc), forever. */
2560 1132276 : else if (single_succ_p (block))
2561 : {
2562 765629 : e = single_succ_edge (block);
2563 765629 : if (!(e->flags & EDGE_DFS_BACK))
2564 686912 : phi_translate_set (PA_OUT, PA_IN (e->dest), e);
2565 : }
2566 : /* If we have multiple successors, we take the union of all of
2567 : them. */
2568 : else
2569 : {
2570 366647 : size_t i;
2571 :
2572 366647 : auto_vec<edge> worklist (EDGE_COUNT (block->succs));
2573 1105296 : FOR_EACH_EDGE (e, ei, block->succs)
2574 : {
2575 738649 : if (e->flags & EDGE_DFS_BACK)
2576 316 : continue;
2577 738333 : worklist.quick_push (e);
2578 : }
2579 366647 : if (worklist.length () > 0)
2580 : {
2581 1104980 : FOR_EACH_VEC_ELT (worklist, i, e)
2582 : {
2583 738333 : unsigned int i;
2584 738333 : bitmap_iterator bi;
2585 :
2586 738333 : if (!gimple_seq_empty_p (phi_nodes (e->dest)))
2587 : {
2588 756 : bitmap_set_t antic_in = bitmap_set_new ();
2589 756 : phi_translate_set (antic_in, ANTIC_IN (e->dest), e);
2590 1508 : FOR_EACH_EXPR_ID_IN_SET (antic_in, i, bi)
2591 752 : bitmap_value_insert_into_set (PA_OUT,
2592 : expression_for_id (i));
2593 756 : bitmap_set_free (antic_in);
2594 756 : bitmap_set_t pa_in = bitmap_set_new ();
2595 756 : phi_translate_set (pa_in, PA_IN (e->dest), e);
2596 756 : FOR_EACH_EXPR_ID_IN_SET (pa_in, i, bi)
2597 0 : bitmap_value_insert_into_set (PA_OUT,
2598 : expression_for_id (i));
2599 756 : bitmap_set_free (pa_in);
2600 : }
2601 : else
2602 : {
2603 4729325 : FOR_EACH_EXPR_ID_IN_SET (ANTIC_IN (e->dest), i, bi)
2604 3991748 : bitmap_value_insert_into_set (PA_OUT,
2605 : expression_for_id (i));
2606 7478833 : FOR_EACH_EXPR_ID_IN_SET (PA_IN (e->dest), i, bi)
2607 6741256 : bitmap_value_insert_into_set (PA_OUT,
2608 : expression_for_id (i));
2609 : }
2610 : }
2611 : }
2612 366647 : }
2613 :
2614 : /* Prune expressions that are clobbered in block and thus become
2615 : invalid if translated from PA_OUT to PA_IN. */
2616 1223026 : prune_clobbered_mems (PA_OUT, block, false);
2617 :
2618 : /* PA_IN starts with PA_OUT - TMP_GEN.
2619 : Then we subtract things from ANTIC_IN. */
2620 1223026 : PA_IN (block) = bitmap_set_subtract_expressions (PA_OUT, TMP_GEN (block));
2621 :
2622 : /* For partial antic, we want to put back in the phi results, since
2623 : we will properly avoid making them partially antic over backedges. */
2624 1223026 : bitmap_ior_into (&PA_IN (block)->values, &PHI_GEN (block)->values);
2625 1223026 : bitmap_ior_into (&PA_IN (block)->expressions, &PHI_GEN (block)->expressions);
2626 :
2627 : /* PA_IN[block] = PA_IN[block] - ANTIC_IN[block] */
2628 1223026 : bitmap_set_subtract_values (PA_IN (block), ANTIC_IN (block));
2629 :
2630 1223026 : clean (PA_IN (block), ANTIC_IN (block));
2631 :
2632 1224338 : maybe_dump_sets:
2633 1224338 : if (dump_file && (dump_flags & TDF_DETAILS))
2634 : {
2635 0 : if (PA_OUT)
2636 0 : print_bitmap_set (dump_file, PA_OUT, "PA_OUT", block->index);
2637 :
2638 0 : print_bitmap_set (dump_file, PA_IN (block), "PA_IN", block->index);
2639 : }
2640 1224338 : if (old_PA_IN)
2641 1223026 : bitmap_set_free (old_PA_IN);
2642 1224338 : if (PA_OUT)
2643 1223026 : bitmap_set_free (PA_OUT);
2644 1224338 : }
2645 :
2646 : /* Compute ANTIC and partial ANTIC sets. */
2647 :
2648 : static void
2649 976700 : compute_antic (void)
2650 : {
2651 976700 : bool changed = true;
2652 976700 : int num_iterations = 0;
2653 976700 : basic_block block;
2654 976700 : int i;
2655 976700 : edge_iterator ei;
2656 976700 : edge e;
2657 :
2658 : /* If any predecessor edges are abnormal, we punt, so antic_in is empty.
2659 : We pre-build the map of blocks with incoming abnormal edges here. */
2660 976700 : auto_sbitmap has_abnormal_preds (last_basic_block_for_fn (cfun));
2661 976700 : bitmap_clear (has_abnormal_preds);
2662 :
2663 16267965 : FOR_ALL_BB_FN (block, cfun)
2664 : {
2665 15291265 : BB_VISITED (block) = 0;
2666 :
2667 34486824 : FOR_EACH_EDGE (e, ei, block->preds)
2668 19198953 : if (e->flags & EDGE_ABNORMAL)
2669 : {
2670 3394 : bitmap_set_bit (has_abnormal_preds, block->index);
2671 3394 : break;
2672 : }
2673 :
2674 : /* While we are here, give empty ANTIC_IN sets to each block. */
2675 15291265 : ANTIC_IN (block) = bitmap_set_new ();
2676 15291265 : if (do_partial_partial)
2677 1224338 : PA_IN (block) = bitmap_set_new ();
2678 : }
2679 :
2680 : /* At the exit block we anticipate nothing. */
2681 976700 : BB_VISITED (EXIT_BLOCK_PTR_FOR_FN (cfun)) = 1;
2682 :
2683 : /* For ANTIC computation we need a postorder that also guarantees that
2684 : a block with a single successor is visited after its successor.
2685 : RPO on the inverted CFG has this property. */
2686 976700 : int *rpo = XNEWVEC (int, n_basic_blocks_for_fn (cfun));
2687 976700 : int n = inverted_rev_post_order_compute (cfun, rpo);
2688 :
2689 976700 : auto_sbitmap worklist (last_basic_block_for_fn (cfun) + 1);
2690 976700 : bitmap_clear (worklist);
2691 2835370 : FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR_FOR_FN (cfun)->preds)
2692 1858670 : bitmap_set_bit (worklist, e->src->index);
2693 3021785 : while (changed)
2694 : {
2695 2045085 : if (dump_file && (dump_flags & TDF_DETAILS))
2696 35 : fprintf (dump_file, "Starting iteration %d\n", num_iterations);
2697 : /* ??? We need to clear our PHI translation cache here as the
2698 : ANTIC sets shrink and we restrict valid translations to
2699 : those having operands with leaders in ANTIC. Same below
2700 : for PA ANTIC computation. */
2701 2045085 : num_iterations++;
2702 2045085 : changed = false;
2703 38692086 : for (i = 0; i < n; ++i)
2704 : {
2705 36647001 : if (bitmap_bit_p (worklist, rpo[i]))
2706 : {
2707 15760001 : basic_block block = BASIC_BLOCK_FOR_FN (cfun, rpo[i]);
2708 15760001 : bitmap_clear_bit (worklist, block->index);
2709 15760001 : if (compute_antic_aux (block,
2710 15760001 : bitmap_bit_p (has_abnormal_preds,
2711 : block->index)))
2712 : {
2713 33170078 : FOR_EACH_EDGE (e, ei, block->preds)
2714 18244246 : bitmap_set_bit (worklist, e->src->index);
2715 : changed = true;
2716 : }
2717 : }
2718 : }
2719 : /* Theoretically possible, but *highly* unlikely. */
2720 2045085 : gcc_checking_assert (num_iterations < 500);
2721 : }
2722 :
2723 : /* We have to clean after the dataflow problem converged as cleaning
2724 : can cause non-convergence because it is based on expressions
2725 : rather than values. */
2726 14314565 : FOR_EACH_BB_FN (block, cfun)
2727 13337865 : clean (ANTIC_IN (block));
2728 :
2729 976700 : statistics_histogram_event (cfun, "compute_antic iterations",
2730 : num_iterations);
2731 :
2732 976700 : if (do_partial_partial)
2733 : {
2734 : /* For partial antic we ignore backedges and thus we do not need
2735 : to perform any iteration when we process blocks in rpo. */
2736 1315088 : for (i = 0; i < n; ++i)
2737 : {
2738 1224338 : basic_block block = BASIC_BLOCK_FOR_FN (cfun, rpo[i]);
2739 1224338 : compute_partial_antic_aux (block,
2740 1224338 : bitmap_bit_p (has_abnormal_preds,
2741 : block->index));
2742 : }
2743 : }
2744 :
2745 976700 : free (rpo);
2746 976700 : }
2747 :
2748 :
2749 : /* Inserted expressions are placed onto this worklist, which is used
2750 : for performing quick dead code elimination of insertions we made
2751 : that didn't turn out to be necessary. */
2752 : static bitmap inserted_exprs;
2753 :
2754 : /* The actual worker for create_component_ref_by_pieces. */
2755 :
2756 : static tree
2757 1149813 : create_component_ref_by_pieces_1 (basic_block block, vn_reference_t ref,
2758 : unsigned int *operand, gimple_seq *stmts)
2759 : {
2760 1149813 : vn_reference_op_t currop = &ref->operands[*operand];
2761 1149813 : tree genop;
2762 1149813 : ++*operand;
2763 1149813 : switch (currop->opcode)
2764 : {
2765 0 : case CALL_EXPR:
2766 0 : gcc_unreachable ();
2767 :
2768 400294 : case MEM_REF:
2769 400294 : {
2770 400294 : tree baseop = create_component_ref_by_pieces_1 (block, ref, operand,
2771 : stmts);
2772 400294 : if (!baseop)
2773 : return NULL_TREE;
2774 400290 : tree offset = currop->op0;
2775 400290 : if (TREE_CODE (baseop) == ADDR_EXPR
2776 400290 : && handled_component_p (TREE_OPERAND (baseop, 0)))
2777 : {
2778 102 : poly_int64 off;
2779 102 : tree base;
2780 102 : base = get_addr_base_and_unit_offset (TREE_OPERAND (baseop, 0),
2781 : &off);
2782 102 : gcc_assert (base);
2783 102 : offset = int_const_binop (PLUS_EXPR, offset,
2784 102 : build_int_cst (TREE_TYPE (offset),
2785 : off));
2786 102 : baseop = build_fold_addr_expr (base);
2787 : }
2788 400290 : genop = build2 (MEM_REF, currop->type, baseop, offset);
2789 400290 : MR_DEPENDENCE_CLIQUE (genop) = currop->clique;
2790 400290 : MR_DEPENDENCE_BASE (genop) = currop->base;
2791 400290 : REF_REVERSE_STORAGE_ORDER (genop) = currop->reverse;
2792 400290 : return genop;
2793 : }
2794 :
2795 0 : case TARGET_MEM_REF:
2796 0 : {
2797 0 : tree genop0 = NULL_TREE, genop1 = NULL_TREE;
2798 0 : vn_reference_op_t nextop = &ref->operands[(*operand)++];
2799 0 : tree baseop = create_component_ref_by_pieces_1 (block, ref, operand,
2800 : stmts);
2801 0 : if (!baseop)
2802 : return NULL_TREE;
2803 0 : if (currop->op0)
2804 : {
2805 0 : genop0 = find_or_generate_expression (block, currop->op0, stmts);
2806 0 : if (!genop0)
2807 : return NULL_TREE;
2808 : }
2809 0 : if (nextop->op0)
2810 : {
2811 0 : genop1 = find_or_generate_expression (block, nextop->op0, stmts);
2812 0 : if (!genop1)
2813 : return NULL_TREE;
2814 : }
2815 0 : genop = build5 (TARGET_MEM_REF, currop->type,
2816 : baseop, currop->op2, genop0, currop->op1, genop1);
2817 :
2818 0 : MR_DEPENDENCE_CLIQUE (genop) = currop->clique;
2819 0 : MR_DEPENDENCE_BASE (genop) = currop->base;
2820 0 : return genop;
2821 : }
2822 :
2823 240335 : case ADDR_EXPR:
2824 240335 : if (currop->op0)
2825 : {
2826 238137 : gcc_assert (is_gimple_min_invariant (currop->op0));
2827 238137 : return currop->op0;
2828 : }
2829 : /* Fallthrough. */
2830 6499 : case REALPART_EXPR:
2831 6499 : case IMAGPART_EXPR:
2832 6499 : case VIEW_CONVERT_EXPR:
2833 6499 : {
2834 6499 : tree genop0 = create_component_ref_by_pieces_1 (block, ref, operand,
2835 : stmts);
2836 6499 : if (!genop0)
2837 : return NULL_TREE;
2838 6499 : return build1 (currop->opcode, currop->type, genop0);
2839 : }
2840 :
2841 4 : case WITH_SIZE_EXPR:
2842 4 : {
2843 4 : tree genop0 = create_component_ref_by_pieces_1 (block, ref, operand,
2844 : stmts);
2845 4 : if (!genop0)
2846 : return NULL_TREE;
2847 4 : tree genop1 = find_or_generate_expression (block, currop->op0, stmts);
2848 4 : if (!genop1)
2849 : return NULL_TREE;
2850 4 : return build2 (currop->opcode, currop->type, genop0, genop1);
2851 : }
2852 :
2853 2283 : case BIT_FIELD_REF:
2854 2283 : {
2855 2283 : tree genop0 = create_component_ref_by_pieces_1 (block, ref, operand,
2856 : stmts);
2857 2283 : if (!genop0)
2858 : return NULL_TREE;
2859 2283 : tree op1 = currop->op0;
2860 2283 : tree op2 = currop->op1;
2861 2283 : tree t = build3 (BIT_FIELD_REF, currop->type, genop0, op1, op2);
2862 2283 : REF_REVERSE_STORAGE_ORDER (t) = currop->reverse;
2863 2283 : return t;
2864 : }
2865 :
2866 : /* For array ref vn_reference_op's, operand 1 of the array ref
2867 : is op0 of the reference op and operand 3 of the array ref is
2868 : op1. */
2869 59358 : case ARRAY_RANGE_REF:
2870 59358 : case ARRAY_REF:
2871 59358 : {
2872 59358 : tree genop0;
2873 59358 : tree genop1 = currop->op0;
2874 59358 : tree genop2 = currop->op1;
2875 59358 : tree genop3 = currop->op2;
2876 59358 : genop0 = create_component_ref_by_pieces_1 (block, ref, operand,
2877 : stmts);
2878 59358 : if (!genop0)
2879 : return NULL_TREE;
2880 59358 : genop1 = find_or_generate_expression (block, genop1, stmts);
2881 59358 : if (!genop1)
2882 : return NULL_TREE;
2883 59358 : if (genop2)
2884 : {
2885 59358 : tree domain_type = TYPE_DOMAIN (TREE_TYPE (genop0));
2886 : /* Drop zero minimum index if redundant. */
2887 59358 : if (integer_zerop (genop2)
2888 59358 : && (!domain_type
2889 58327 : || integer_zerop (TYPE_MIN_VALUE (domain_type))))
2890 : genop2 = NULL_TREE;
2891 : else
2892 : {
2893 604 : genop2 = find_or_generate_expression (block, genop2, stmts);
2894 604 : if (!genop2)
2895 : return NULL_TREE;
2896 : }
2897 : }
2898 59358 : if (genop3)
2899 : {
2900 59358 : tree elmt_type = TREE_TYPE (TREE_TYPE (genop0));
2901 : /* We can't always put a size in units of the element alignment
2902 : here as the element alignment may be not visible. See
2903 : PR43783. Simply drop the element size for constant
2904 : sizes. */
2905 59358 : if ((TREE_CODE (genop3) == INTEGER_CST
2906 59354 : && TREE_CODE (TYPE_SIZE_UNIT (elmt_type)) == INTEGER_CST
2907 59354 : && wi::eq_p (wi::to_offset (TYPE_SIZE_UNIT (elmt_type)),
2908 59354 : (wi::to_offset (genop3) * vn_ref_op_align_unit (currop))))
2909 59358 : || (TREE_CODE (genop3) == EXACT_DIV_EXPR
2910 0 : && TREE_CODE (TREE_OPERAND (genop3, 1)) == INTEGER_CST
2911 0 : && operand_equal_p (TREE_OPERAND (genop3, 0), TYPE_SIZE_UNIT (elmt_type))
2912 0 : && wi::eq_p (wi::to_offset (TREE_OPERAND (genop3, 1)),
2913 59354 : vn_ref_op_align_unit (currop))))
2914 : genop3 = NULL_TREE;
2915 : else
2916 : {
2917 4 : genop3 = find_or_generate_expression (block, genop3, stmts);
2918 4 : if (!genop3)
2919 : return NULL_TREE;
2920 : }
2921 : }
2922 59358 : return build4 (currop->opcode, currop->type, genop0, genop1,
2923 59358 : genop2, genop3);
2924 : }
2925 276467 : case COMPONENT_REF:
2926 276467 : {
2927 276467 : tree op0;
2928 276467 : tree op1;
2929 276467 : tree genop2 = currop->op1;
2930 276467 : op0 = create_component_ref_by_pieces_1 (block, ref, operand, stmts);
2931 276467 : if (!op0)
2932 : return NULL_TREE;
2933 : /* op1 should be a FIELD_DECL, which are represented by themselves. */
2934 276459 : op1 = currop->op0;
2935 276459 : if (genop2)
2936 : {
2937 0 : genop2 = find_or_generate_expression (block, genop2, stmts);
2938 0 : if (!genop2)
2939 : return NULL_TREE;
2940 : }
2941 276459 : return build3 (COMPONENT_REF, TREE_TYPE (op1), op0, op1, genop2);
2942 : }
2943 :
2944 164816 : case SSA_NAME:
2945 164816 : {
2946 164816 : genop = find_or_generate_expression (block, currop->op0, stmts);
2947 164816 : return genop;
2948 : }
2949 1955 : case STRING_CST:
2950 1955 : case INTEGER_CST:
2951 1955 : case POLY_INT_CST:
2952 1955 : case COMPLEX_CST:
2953 1955 : case VECTOR_CST:
2954 1955 : case REAL_CST:
2955 1955 : case CONSTRUCTOR:
2956 1955 : case VAR_DECL:
2957 1955 : case PARM_DECL:
2958 1955 : case CONST_DECL:
2959 1955 : case RESULT_DECL:
2960 1955 : case FUNCTION_DECL:
2961 1955 : return currop->op0;
2962 :
2963 0 : default:
2964 0 : gcc_unreachable ();
2965 : }
2966 : }
2967 :
2968 : /* For COMPONENT_REF's and ARRAY_REF's, we can't have any intermediates for the
2969 : COMPONENT_REF or MEM_REF or ARRAY_REF portion, because we'd end up with
2970 : trying to rename aggregates into ssa form directly, which is a no no.
2971 :
2972 : Thus, this routine doesn't create temporaries, it just builds a
2973 : single access expression for the array, calling
2974 : find_or_generate_expression to build the innermost pieces.
2975 :
2976 : This function is a subroutine of create_expression_by_pieces, and
2977 : should not be called on it's own unless you really know what you
2978 : are doing. */
2979 :
2980 : static tree
2981 400323 : create_component_ref_by_pieces (basic_block block, vn_reference_t ref,
2982 : gimple_seq *stmts)
2983 : {
2984 400323 : unsigned int op = 0;
2985 400323 : return create_component_ref_by_pieces_1 (block, ref, &op, stmts);
2986 : }
2987 :
2988 : /* Find a simple leader for an expression, or generate one using
2989 : create_expression_by_pieces from a NARY expression for the value.
2990 : BLOCK is the basic_block we are looking for leaders in.
2991 : OP is the tree expression to find a leader for or generate.
2992 : Returns the leader or NULL_TREE on failure. */
2993 :
2994 : static tree
2995 861270 : find_or_generate_expression (basic_block block, tree op, gimple_seq *stmts)
2996 : {
2997 : /* Constants are always leaders. */
2998 861270 : if (is_gimple_min_invariant (op))
2999 : return op;
3000 :
3001 662167 : gcc_assert (TREE_CODE (op) == SSA_NAME);
3002 662167 : vn_ssa_aux_t info = VN_INFO (op);
3003 662167 : unsigned int lookfor = info->value_id;
3004 662167 : if (value_id_constant_p (lookfor))
3005 3 : return info->valnum;
3006 :
3007 662164 : pre_expr leader = bitmap_find_leader (AVAIL_OUT (block), lookfor);
3008 662164 : if (leader)
3009 : {
3010 627589 : if (leader->kind == NAME)
3011 : {
3012 627589 : tree name = PRE_EXPR_NAME (leader);
3013 627589 : if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name))
3014 : return NULL_TREE;
3015 : return name;
3016 : }
3017 0 : else if (leader->kind == CONSTANT)
3018 0 : return PRE_EXPR_CONSTANT (leader);
3019 :
3020 : /* Defer. */
3021 : return NULL_TREE;
3022 : }
3023 34575 : gcc_assert (!value_id_constant_p (lookfor));
3024 :
3025 : /* It must be a complex expression, so generate it recursively. Note
3026 : that this is only necessary to handle gcc.dg/tree-ssa/ssa-pre28.c
3027 : where the insert algorithm fails to insert a required expression. */
3028 34575 : bitmap exprset = value_expressions[lookfor];
3029 34575 : bitmap_iterator bi;
3030 34575 : unsigned int i;
3031 34575 : if (exprset)
3032 47109 : EXECUTE_IF_SET_IN_BITMAP (exprset, 0, i, bi)
3033 : {
3034 44162 : pre_expr temp = expression_for_id (i);
3035 : /* We cannot insert random REFERENCE expressions at arbitrary
3036 : places. We can insert NARYs which eventually re-materializes
3037 : its operand values. */
3038 44162 : if (temp->kind == NARY)
3039 31624 : return create_expression_by_pieces (block, temp, stmts,
3040 63248 : TREE_TYPE (op));
3041 : }
3042 :
3043 : /* Defer. */
3044 : return NULL_TREE;
3045 : }
3046 :
3047 : /* Create an expression in pieces, so that we can handle very complex
3048 : expressions that may be ANTIC, but not necessary GIMPLE.
3049 : BLOCK is the basic block the expression will be inserted into,
3050 : EXPR is the expression to insert (in value form)
3051 : STMTS is a statement list to append the necessary insertions into.
3052 :
3053 : This function will die if we hit some value that shouldn't be
3054 : ANTIC but is (IE there is no leader for it, or its components).
3055 : The function returns NULL_TREE in case a different antic expression
3056 : has to be inserted first.
3057 : This function may also generate expressions that are themselves
3058 : partially or fully redundant. Those that are will be either made
3059 : fully redundant during the next iteration of insert (for partially
3060 : redundant ones), or eliminated by eliminate (for fully redundant
3061 : ones). */
3062 :
3063 : static tree
3064 2907974 : create_expression_by_pieces (basic_block block, pre_expr expr,
3065 : gimple_seq *stmts, tree type)
3066 : {
3067 2907974 : tree name;
3068 2907974 : tree folded;
3069 2907974 : gimple_seq forced_stmts = NULL;
3070 2907974 : unsigned int value_id;
3071 2907974 : gimple_stmt_iterator gsi;
3072 2907974 : tree exprtype = type ? type : get_expr_type (expr);
3073 2907974 : pre_expr nameexpr;
3074 2907974 : gassign *newstmt;
3075 :
3076 2907974 : switch (expr->kind)
3077 : {
3078 : /* We may hit the NAME/CONSTANT case if we have to convert types
3079 : that value numbering saw through. */
3080 734362 : case NAME:
3081 734362 : folded = PRE_EXPR_NAME (expr);
3082 734362 : if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (folded))
3083 : return NULL_TREE;
3084 734357 : if (useless_type_conversion_p (exprtype, TREE_TYPE (folded)))
3085 : return folded;
3086 : break;
3087 1393517 : case CONSTANT:
3088 1393517 : {
3089 1393517 : folded = PRE_EXPR_CONSTANT (expr);
3090 1393517 : tree tem = fold_convert (exprtype, folded);
3091 1393517 : if (is_gimple_min_invariant (tem))
3092 : return tem;
3093 : break;
3094 : }
3095 403467 : case REFERENCE:
3096 403467 : if (PRE_EXPR_REFERENCE (expr)->operands[0].opcode == CALL_EXPR)
3097 : {
3098 3144 : vn_reference_t ref = PRE_EXPR_REFERENCE (expr);
3099 3144 : unsigned int operand = 1;
3100 3144 : vn_reference_op_t currop = &ref->operands[0];
3101 3144 : tree sc = NULL_TREE;
3102 3144 : tree fn = NULL_TREE;
3103 3144 : if (currop->op0)
3104 : {
3105 3002 : fn = find_or_generate_expression (block, currop->op0, stmts);
3106 3002 : if (!fn)
3107 0 : return NULL_TREE;
3108 : }
3109 3144 : if (currop->op1)
3110 : {
3111 0 : sc = find_or_generate_expression (block, currop->op1, stmts);
3112 0 : if (!sc)
3113 : return NULL_TREE;
3114 : }
3115 6288 : auto_vec<tree> args (ref->operands.length () - 1);
3116 7729 : while (operand < ref->operands.length ())
3117 : {
3118 4585 : tree arg = create_component_ref_by_pieces_1 (block, ref,
3119 4585 : &operand, stmts);
3120 4585 : if (!arg)
3121 0 : return NULL_TREE;
3122 4585 : args.quick_push (arg);
3123 : }
3124 3144 : gcall *call;
3125 3144 : if (currop->op0)
3126 : {
3127 3002 : call = gimple_build_call_vec (fn, args);
3128 3002 : gimple_call_set_fntype (call, currop->type);
3129 : }
3130 : else
3131 142 : call = gimple_build_call_internal_vec ((internal_fn)currop->clique,
3132 : args);
3133 3144 : gimple_set_location (call, expr->loc);
3134 3144 : if (sc)
3135 0 : gimple_call_set_chain (call, sc);
3136 3144 : tree forcedname = make_ssa_name (ref->type);
3137 3144 : gimple_call_set_lhs (call, forcedname);
3138 : /* There's no CCP pass after PRE which would re-compute alignment
3139 : information so make sure we re-materialize this here. */
3140 3144 : if (gimple_call_builtin_p (call, BUILT_IN_ASSUME_ALIGNED)
3141 0 : && args.length () - 2 <= 1
3142 0 : && tree_fits_uhwi_p (args[1])
3143 3144 : && (args.length () != 3 || tree_fits_uhwi_p (args[2])))
3144 : {
3145 0 : unsigned HOST_WIDE_INT halign = tree_to_uhwi (args[1]);
3146 0 : unsigned HOST_WIDE_INT hmisalign
3147 0 : = args.length () == 3 ? tree_to_uhwi (args[2]) : 0;
3148 0 : if ((halign & (halign - 1)) == 0
3149 0 : && (hmisalign & ~(halign - 1)) == 0
3150 0 : && (unsigned int)halign != 0)
3151 0 : set_ptr_info_alignment (get_ptr_info (forcedname),
3152 : halign, hmisalign);
3153 : }
3154 3144 : gimple_set_vuse (call, BB_LIVE_VOP_ON_EXIT (block));
3155 3144 : gimple_seq_add_stmt_without_update (&forced_stmts, call);
3156 3144 : folded = forcedname;
3157 3144 : }
3158 : else
3159 : {
3160 400323 : folded = create_component_ref_by_pieces (block,
3161 : PRE_EXPR_REFERENCE (expr),
3162 : stmts);
3163 400323 : if (!folded)
3164 : return NULL_TREE;
3165 400319 : name = make_temp_ssa_name (exprtype, NULL, "pretmp");
3166 400319 : newstmt = gimple_build_assign (name, folded);
3167 400319 : gimple_set_location (newstmt, expr->loc);
3168 400319 : gimple_seq_add_stmt_without_update (&forced_stmts, newstmt);
3169 400319 : gimple_set_vuse (newstmt, BB_LIVE_VOP_ON_EXIT (block));
3170 400319 : folded = name;
3171 : }
3172 : break;
3173 376628 : case NARY:
3174 376628 : {
3175 376628 : vn_nary_op_t nary = PRE_EXPR_NARY (expr);
3176 376628 : tree *genop = XALLOCAVEC (tree, nary->length);
3177 376628 : unsigned i;
3178 1000091 : for (i = 0; i < nary->length; ++i)
3179 : {
3180 633482 : genop[i] = find_or_generate_expression (block, nary->op[i], stmts);
3181 633482 : if (!genop[i])
3182 : return NULL_TREE;
3183 : /* Ensure genop[] is properly typed for POINTER_PLUS_EXPR. It
3184 : may have conversions stripped. */
3185 623463 : if (nary->opcode == POINTER_PLUS_EXPR)
3186 : {
3187 105854 : if (i == 0)
3188 52946 : genop[i] = gimple_convert (&forced_stmts,
3189 : nary->type, genop[i]);
3190 52908 : else if (i == 1)
3191 52908 : genop[i] = gimple_convert (&forced_stmts,
3192 : sizetype, genop[i]);
3193 : }
3194 : else
3195 517609 : genop[i] = gimple_convert (&forced_stmts,
3196 517609 : TREE_TYPE (nary->op[i]), genop[i]);
3197 : }
3198 366609 : if (nary->opcode == CONSTRUCTOR)
3199 : {
3200 44 : vec<constructor_elt, va_gc> *elts = NULL;
3201 148 : for (i = 0; i < nary->length; ++i)
3202 104 : CONSTRUCTOR_APPEND_ELT (elts, NULL_TREE, genop[i]);
3203 44 : folded = build_constructor (nary->type, elts);
3204 44 : name = make_temp_ssa_name (exprtype, NULL, "pretmp");
3205 44 : newstmt = gimple_build_assign (name, folded);
3206 44 : gimple_set_location (newstmt, expr->loc);
3207 44 : gimple_seq_add_stmt_without_update (&forced_stmts, newstmt);
3208 44 : folded = name;
3209 : }
3210 : else
3211 : {
3212 366565 : switch (nary->length)
3213 : {
3214 111105 : case 1:
3215 111105 : folded = gimple_build (&forced_stmts, expr->loc,
3216 : nary->opcode, nary->type, genop[0]);
3217 111105 : break;
3218 255219 : case 2:
3219 255219 : folded = gimple_build (&forced_stmts, expr->loc, nary->opcode,
3220 : nary->type, genop[0], genop[1]);
3221 255219 : break;
3222 241 : case 3:
3223 241 : folded = gimple_build (&forced_stmts, expr->loc, nary->opcode,
3224 : nary->type, genop[0], genop[1],
3225 : genop[2]);
3226 241 : break;
3227 0 : default:
3228 0 : gcc_unreachable ();
3229 : }
3230 : }
3231 : }
3232 : break;
3233 0 : default:
3234 0 : gcc_unreachable ();
3235 : }
3236 :
3237 865101 : folded = gimple_convert (&forced_stmts, exprtype, folded);
3238 :
3239 : /* If there is nothing to insert, return the simplified result. */
3240 865101 : if (gimple_seq_empty_p (forced_stmts))
3241 : return folded;
3242 : /* If we simplified to a constant return it and discard eventually
3243 : built stmts. */
3244 770014 : if (is_gimple_min_invariant (folded))
3245 : {
3246 0 : gimple_seq_discard (forced_stmts);
3247 0 : return folded;
3248 : }
3249 : /* Likewise if we simplified to sth not queued for insertion. */
3250 770014 : bool found = false;
3251 770014 : gsi = gsi_last (forced_stmts);
3252 770014 : for (; !gsi_end_p (gsi); gsi_prev (&gsi))
3253 : {
3254 770014 : gimple *stmt = gsi_stmt (gsi);
3255 770014 : tree forcedname = gimple_get_lhs (stmt);
3256 770014 : if (forcedname == folded)
3257 : {
3258 : found = true;
3259 : break;
3260 : }
3261 : }
3262 770014 : if (! found)
3263 : {
3264 0 : gimple_seq_discard (forced_stmts);
3265 0 : return folded;
3266 : }
3267 770014 : gcc_assert (TREE_CODE (folded) == SSA_NAME);
3268 :
3269 : /* If we have any intermediate expressions to the value sets, add them
3270 : to the value sets and chain them in the instruction stream. */
3271 770014 : if (forced_stmts)
3272 : {
3273 770014 : gsi = gsi_start (forced_stmts);
3274 1540520 : for (; !gsi_end_p (gsi); gsi_next (&gsi))
3275 : {
3276 770506 : gimple *stmt = gsi_stmt (gsi);
3277 770506 : tree forcedname = gimple_get_lhs (stmt);
3278 770506 : pre_expr nameexpr;
3279 :
3280 770506 : if (forcedname != folded)
3281 : {
3282 492 : vn_ssa_aux_t vn_info = VN_INFO (forcedname);
3283 492 : vn_info->valnum = forcedname;
3284 492 : vn_info->value_id = get_next_value_id ();
3285 492 : nameexpr = get_or_alloc_expr_for_name (forcedname);
3286 492 : add_to_value (vn_info->value_id, nameexpr);
3287 492 : if (NEW_SETS (block))
3288 492 : bitmap_value_replace_in_set (NEW_SETS (block), nameexpr);
3289 492 : bitmap_value_replace_in_set (AVAIL_OUT (block), nameexpr);
3290 : }
3291 :
3292 770506 : bitmap_set_bit (inserted_exprs, SSA_NAME_VERSION (forcedname));
3293 : }
3294 770014 : gimple_seq_add_seq (stmts, forced_stmts);
3295 : }
3296 :
3297 770014 : name = folded;
3298 :
3299 : /* Fold the last statement. */
3300 770014 : gsi = gsi_last (*stmts);
3301 770014 : if (fold_stmt_inplace (&gsi))
3302 204357 : update_stmt (gsi_stmt (gsi));
3303 :
3304 : /* Add a value number to the temporary.
3305 : The value may already exist in either NEW_SETS, or AVAIL_OUT, because
3306 : we are creating the expression by pieces, and this particular piece of
3307 : the expression may have been represented. There is no harm in replacing
3308 : here. */
3309 770014 : value_id = get_expr_value_id (expr);
3310 770014 : vn_ssa_aux_t vn_info = VN_INFO (name);
3311 770014 : vn_info->value_id = value_id;
3312 770014 : vn_info->valnum = vn_valnum_from_value_id (value_id);
3313 770014 : if (vn_info->valnum == NULL_TREE)
3314 245017 : vn_info->valnum = name;
3315 770014 : gcc_assert (vn_info->valnum != NULL_TREE);
3316 770014 : nameexpr = get_or_alloc_expr_for_name (name);
3317 770014 : add_to_value (value_id, nameexpr);
3318 770014 : if (NEW_SETS (block))
3319 547339 : bitmap_value_replace_in_set (NEW_SETS (block), nameexpr);
3320 770014 : bitmap_value_replace_in_set (AVAIL_OUT (block), nameexpr);
3321 :
3322 770014 : pre_stats.insertions++;
3323 770014 : if (dump_file && (dump_flags & TDF_DETAILS))
3324 : {
3325 18 : fprintf (dump_file, "Inserted ");
3326 36 : print_gimple_stmt (dump_file, gsi_stmt (gsi_last (*stmts)), 0);
3327 18 : fprintf (dump_file, " in predecessor %d (%04d)\n",
3328 : block->index, value_id);
3329 : }
3330 :
3331 : return name;
3332 : }
3333 :
3334 :
3335 : /* Insert the to-be-made-available values of expression EXPRNUM for each
3336 : predecessor, stored in AVAIL, into the predecessors of BLOCK, and
3337 : merge the result with a phi node, given the same value number as
3338 : NODE. Return true if we have inserted new stuff. */
3339 :
3340 : static bool
3341 1949820 : insert_into_preds_of_block (basic_block block, unsigned int exprnum,
3342 : vec<pre_expr> &avail)
3343 : {
3344 1949820 : pre_expr expr = expression_for_id (exprnum);
3345 1949820 : pre_expr newphi;
3346 1949820 : unsigned int val = get_expr_value_id (expr);
3347 1949820 : edge pred;
3348 1949820 : bool insertions = false;
3349 1949820 : bool nophi = false;
3350 1949820 : basic_block bprime;
3351 1949820 : pre_expr eprime;
3352 1949820 : edge_iterator ei;
3353 1949820 : tree type = get_expr_type (expr);
3354 1949820 : tree temp;
3355 1949820 : gphi *phi;
3356 :
3357 : /* Make sure we aren't creating an induction variable. */
3358 1949820 : if (bb_loop_depth (block) > 0 && EDGE_COUNT (block->preds) == 2)
3359 : {
3360 1614011 : bool firstinsideloop = false;
3361 1614011 : bool secondinsideloop = false;
3362 4842033 : firstinsideloop = flow_bb_inside_loop_p (block->loop_father,
3363 1614011 : EDGE_PRED (block, 0)->src);
3364 4842033 : secondinsideloop = flow_bb_inside_loop_p (block->loop_father,
3365 1614011 : EDGE_PRED (block, 1)->src);
3366 : /* Induction variables only have one edge inside the loop. */
3367 1614011 : if ((firstinsideloop ^ secondinsideloop)
3368 1537637 : && expr->kind != REFERENCE)
3369 : {
3370 1458296 : if (dump_file && (dump_flags & TDF_DETAILS))
3371 56 : fprintf (dump_file, "Skipping insertion of phi for partial "
3372 : "redundancy: Looks like an induction variable\n");
3373 : nophi = true;
3374 : }
3375 : }
3376 :
3377 : /* Make the necessary insertions. */
3378 6072921 : FOR_EACH_EDGE (pred, ei, block->preds)
3379 : {
3380 : /* When we are not inserting a PHI node do not bother inserting
3381 : into places that do not dominate the anticipated computations. */
3382 4123101 : if (nophi && !dominated_by_p (CDI_DOMINATORS, block, pred->src))
3383 1472413 : continue;
3384 2653656 : gimple_seq stmts = NULL;
3385 2653656 : tree builtexpr;
3386 2653656 : bprime = pred->src;
3387 2653656 : eprime = avail[pred->dest_idx];
3388 2653656 : builtexpr = create_expression_by_pieces (bprime, eprime,
3389 : &stmts, type);
3390 2653656 : gcc_assert (!(pred->flags & EDGE_ABNORMAL));
3391 2653656 : if (!gimple_seq_empty_p (stmts))
3392 : {
3393 522766 : basic_block new_bb = gsi_insert_seq_on_edge_immediate (pred, stmts);
3394 522766 : gcc_assert (! new_bb);
3395 : insertions = true;
3396 : }
3397 2653656 : if (!builtexpr)
3398 : {
3399 : /* We cannot insert a PHI node if we failed to insert
3400 : on one edge. */
3401 2968 : nophi = true;
3402 2968 : continue;
3403 : }
3404 2650688 : if (is_gimple_min_invariant (builtexpr))
3405 1393562 : avail[pred->dest_idx] = get_or_alloc_expr_for_constant (builtexpr);
3406 : else
3407 1257126 : avail[pred->dest_idx] = get_or_alloc_expr_for_name (builtexpr);
3408 : }
3409 : /* If we didn't want a phi node, and we made insertions, we still have
3410 : inserted new stuff, and thus return true. If we didn't want a phi node,
3411 : and didn't make insertions, we haven't added anything new, so return
3412 : false. */
3413 1949820 : if (nophi && insertions)
3414 : return true;
3415 1940926 : else if (nophi && !insertions)
3416 : return false;
3417 :
3418 : /* Now build a phi for the new variable. */
3419 488561 : temp = make_temp_ssa_name (type, NULL, "prephitmp");
3420 488561 : phi = create_phi_node (temp, block);
3421 :
3422 488561 : vn_ssa_aux_t vn_info = VN_INFO (temp);
3423 488561 : vn_info->value_id = val;
3424 488561 : vn_info->valnum = vn_valnum_from_value_id (val);
3425 488561 : if (vn_info->valnum == NULL_TREE)
3426 99012 : vn_info->valnum = temp;
3427 488561 : bitmap_set_bit (inserted_exprs, SSA_NAME_VERSION (temp));
3428 1679932 : FOR_EACH_EDGE (pred, ei, block->preds)
3429 : {
3430 1191371 : pre_expr ae = avail[pred->dest_idx];
3431 1191371 : gcc_assert (get_expr_type (ae) == type
3432 : || useless_type_conversion_p (type, get_expr_type (ae)));
3433 1191371 : if (ae->kind == CONSTANT)
3434 187696 : add_phi_arg (phi, unshare_expr (PRE_EXPR_CONSTANT (ae)),
3435 : pred, UNKNOWN_LOCATION);
3436 : else
3437 1003675 : add_phi_arg (phi, PRE_EXPR_NAME (ae), pred, UNKNOWN_LOCATION);
3438 : }
3439 :
3440 488561 : newphi = get_or_alloc_expr_for_name (temp);
3441 488561 : add_to_value (val, newphi);
3442 :
3443 : /* The value should *not* exist in PHI_GEN, or else we wouldn't be doing
3444 : this insertion, since we test for the existence of this value in PHI_GEN
3445 : before proceeding with the partial redundancy checks in insert_aux.
3446 :
3447 : The value may exist in AVAIL_OUT, in particular, it could be represented
3448 : by the expression we are trying to eliminate, in which case we want the
3449 : replacement to occur. If it's not existing in AVAIL_OUT, we want it
3450 : inserted there.
3451 :
3452 : Similarly, to the PHI_GEN case, the value should not exist in NEW_SETS of
3453 : this block, because if it did, it would have existed in our dominator's
3454 : AVAIL_OUT, and would have been skipped due to the full redundancy check.
3455 : */
3456 :
3457 488561 : bitmap_insert_into_set (PHI_GEN (block), newphi);
3458 488561 : bitmap_value_replace_in_set (AVAIL_OUT (block),
3459 : newphi);
3460 488561 : if (NEW_SETS (block))
3461 488561 : bitmap_insert_into_set (NEW_SETS (block), newphi);
3462 :
3463 : /* If we insert a PHI node for a conversion of another PHI node
3464 : in the same basic-block try to preserve range information.
3465 : This is important so that followup loop passes receive optimal
3466 : number of iteration analysis results. See PR61743. */
3467 488561 : if (expr->kind == NARY
3468 187108 : && CONVERT_EXPR_CODE_P (expr->u.nary->opcode)
3469 56295 : && TREE_CODE (expr->u.nary->op[0]) == SSA_NAME
3470 56120 : && gimple_bb (SSA_NAME_DEF_STMT (expr->u.nary->op[0])) == block
3471 46435 : && INTEGRAL_TYPE_P (type)
3472 45587 : && INTEGRAL_TYPE_P (TREE_TYPE (expr->u.nary->op[0]))
3473 44530 : && (TYPE_PRECISION (type)
3474 44530 : >= TYPE_PRECISION (TREE_TYPE (expr->u.nary->op[0])))
3475 525417 : && SSA_NAME_RANGE_INFO (expr->u.nary->op[0]))
3476 : {
3477 22954 : int_range_max r;
3478 45908 : if (get_range_query (cfun)->range_of_expr (r, expr->u.nary->op[0])
3479 22954 : && !r.undefined_p ()
3480 22954 : && !r.varying_p ()
3481 45908 : && !wi::neg_p (r.lower_bound (), SIGNED)
3482 62762 : && !wi::neg_p (r.upper_bound (), SIGNED))
3483 : {
3484 : /* Just handle extension and sign-changes of all-positive ranges. */
3485 16122 : range_cast (r, type);
3486 16122 : set_range_info (temp, r);
3487 : }
3488 22954 : }
3489 :
3490 488561 : if (dump_file && (dump_flags & TDF_DETAILS))
3491 : {
3492 8 : fprintf (dump_file, "Created phi ");
3493 8 : print_gimple_stmt (dump_file, phi, 0);
3494 8 : fprintf (dump_file, " in block %d (%04d)\n", block->index, val);
3495 : }
3496 488561 : pre_stats.phis++;
3497 488561 : return true;
3498 : }
3499 :
3500 :
3501 :
3502 : /* Perform insertion of partially redundant or hoistable values.
3503 : For BLOCK, do the following:
3504 : 1. Propagate the NEW_SETS of the dominator into the current block.
3505 : If the block has multiple predecessors,
3506 : 2a. Iterate over the ANTIC expressions for the block to see if
3507 : any of them are partially redundant.
3508 : 2b. If so, insert them into the necessary predecessors to make
3509 : the expression fully redundant.
3510 : 2c. Insert a new PHI merging the values of the predecessors.
3511 : 2d. Insert the new PHI, and the new expressions, into the
3512 : NEW_SETS set.
3513 : If the block has multiple successors,
3514 : 3a. Iterate over the ANTIC values for the block to see if
3515 : any of them are good candidates for hoisting.
3516 : 3b. If so, insert expressions computing the values in BLOCK,
3517 : and add the new expressions into the NEW_SETS set.
3518 : 4. Recursively call ourselves on the dominator children of BLOCK.
3519 :
3520 : Steps 1, 2a, and 4 are done by insert_aux. 2b, 2c and 2d are done by
3521 : do_pre_regular_insertion and do_partial_insertion. 3a and 3b are
3522 : done in do_hoist_insertion.
3523 : */
3524 :
3525 : static bool
3526 3723910 : do_pre_regular_insertion (basic_block block, basic_block dom,
3527 : vec<pre_expr> exprs)
3528 : {
3529 3723910 : bool new_stuff = false;
3530 3723910 : pre_expr expr;
3531 3723910 : auto_vec<pre_expr, 2> avail;
3532 3723910 : int i;
3533 :
3534 3723910 : avail.safe_grow (EDGE_COUNT (block->preds), true);
3535 :
3536 25993425 : FOR_EACH_VEC_ELT (exprs, i, expr)
3537 : {
3538 22269515 : if (expr->kind == NARY
3539 22269515 : || expr->kind == REFERENCE)
3540 : {
3541 12598991 : unsigned int val;
3542 12598991 : bool by_some = false;
3543 12598991 : bool cant_insert = false;
3544 12598991 : bool all_same = true;
3545 12598991 : unsigned num_inserts = 0;
3546 12598991 : unsigned num_const = 0;
3547 12598991 : pre_expr first_s = NULL;
3548 12598991 : edge pred;
3549 12598991 : basic_block bprime;
3550 12598991 : pre_expr eprime = NULL;
3551 12598991 : edge_iterator ei;
3552 12598991 : pre_expr edoubleprime = NULL;
3553 12598991 : bool do_insertion = false;
3554 :
3555 12598991 : val = get_expr_value_id (expr);
3556 25197982 : if (bitmap_set_contains_value (PHI_GEN (block), val))
3557 1071361 : continue;
3558 11797696 : if (bitmap_set_contains_value (AVAIL_OUT (dom), val))
3559 : {
3560 270066 : if (dump_file && (dump_flags & TDF_DETAILS))
3561 : {
3562 7 : fprintf (dump_file, "Found fully redundant value: ");
3563 7 : print_pre_expr (dump_file, expr);
3564 7 : fprintf (dump_file, "\n");
3565 : }
3566 270066 : continue;
3567 : }
3568 :
3569 37594361 : FOR_EACH_EDGE (pred, ei, block->preds)
3570 : {
3571 26067578 : unsigned int vprime;
3572 :
3573 : /* We should never run insertion for the exit block
3574 : and so not come across fake pred edges. */
3575 26067578 : gcc_assert (!(pred->flags & EDGE_FAKE));
3576 26067578 : bprime = pred->src;
3577 : /* We are looking at ANTIC_OUT of bprime. */
3578 26067578 : eprime = phi_translate (NULL, expr, ANTIC_IN (block), NULL, pred);
3579 :
3580 : /* eprime will generally only be NULL if the
3581 : value of the expression, translated
3582 : through the PHI for this predecessor, is
3583 : undefined. If that is the case, we can't
3584 : make the expression fully redundant,
3585 : because its value is undefined along a
3586 : predecessor path. We can thus break out
3587 : early because it doesn't matter what the
3588 : rest of the results are. */
3589 26067578 : if (eprime == NULL)
3590 : {
3591 847 : avail[pred->dest_idx] = NULL;
3592 847 : cant_insert = true;
3593 847 : break;
3594 : }
3595 :
3596 26066731 : vprime = get_expr_value_id (eprime);
3597 26066731 : edoubleprime = bitmap_find_leader (AVAIL_OUT (bprime),
3598 : vprime);
3599 26066731 : if (edoubleprime == NULL)
3600 : {
3601 23438793 : avail[pred->dest_idx] = eprime;
3602 23438793 : all_same = false;
3603 23438793 : num_inserts++;
3604 : }
3605 : else
3606 : {
3607 2627938 : avail[pred->dest_idx] = edoubleprime;
3608 2627938 : by_some = true;
3609 2627938 : if (edoubleprime->kind == CONSTANT)
3610 1737022 : num_const++;
3611 : /* We want to perform insertions to remove a redundancy on
3612 : a path in the CFG we want to optimize for speed. */
3613 2627938 : if (optimize_edge_for_speed_p (pred))
3614 2194850 : do_insertion = true;
3615 2627938 : if (first_s == NULL)
3616 : first_s = edoubleprime;
3617 296723 : else if (!pre_expr_d::equal (first_s, edoubleprime))
3618 226564 : all_same = false;
3619 : }
3620 : }
3621 : /* If we can insert it, it's not the same value
3622 : already existing along every predecessor, and
3623 : it's defined by some predecessor, it is
3624 : partially redundant. */
3625 11527630 : if (!cant_insert && !all_same && by_some)
3626 : {
3627 : /* If the expression is redundant on all edges and we need
3628 : to at most insert one copy from a constant do the PHI
3629 : insertion even when not optimizing a path that's to be
3630 : optimized for speed. */
3631 2327825 : if (num_inserts == 0 && num_const <= 1)
3632 : do_insertion = true;
3633 2179091 : if (!do_insertion)
3634 : {
3635 384310 : if (dump_file && (dump_flags & TDF_DETAILS))
3636 : {
3637 0 : fprintf (dump_file, "Skipping partial redundancy for "
3638 : "expression ");
3639 0 : print_pre_expr (dump_file, expr);
3640 0 : fprintf (dump_file, " (%04d), no redundancy on to be "
3641 : "optimized for speed edge\n", val);
3642 : }
3643 : }
3644 1943515 : else if (dbg_cnt (treepre_insert))
3645 : {
3646 1943515 : if (dump_file && (dump_flags & TDF_DETAILS))
3647 : {
3648 64 : fprintf (dump_file, "Found partial redundancy for "
3649 : "expression ");
3650 64 : print_pre_expr (dump_file, expr);
3651 64 : fprintf (dump_file, " (%04d)\n",
3652 : get_expr_value_id (expr));
3653 : }
3654 1943515 : if (insert_into_preds_of_block (block,
3655 : get_expression_id (expr),
3656 : avail))
3657 11527630 : new_stuff = true;
3658 : }
3659 : }
3660 : /* If all edges produce the same value and that value is
3661 : an invariant, then the PHI has the same value on all
3662 : edges. Note this. */
3663 9199805 : else if (!cant_insert
3664 9199805 : && all_same
3665 9199805 : && (edoubleprime->kind != NAME
3666 1782 : || !SSA_NAME_OCCURS_IN_ABNORMAL_PHI
3667 : (PRE_EXPR_NAME (edoubleprime))))
3668 : {
3669 3364 : gcc_assert (edoubleprime->kind == CONSTANT
3670 : || edoubleprime->kind == NAME);
3671 :
3672 3364 : tree temp = make_temp_ssa_name (get_expr_type (expr),
3673 : NULL, "pretmp");
3674 3364 : gassign *assign
3675 3364 : = gimple_build_assign (temp,
3676 3364 : edoubleprime->kind == CONSTANT ?
3677 : PRE_EXPR_CONSTANT (edoubleprime) :
3678 : PRE_EXPR_NAME (edoubleprime));
3679 3364 : gimple_stmt_iterator gsi = gsi_after_labels (block);
3680 3364 : gsi_insert_before (&gsi, assign, GSI_NEW_STMT);
3681 :
3682 3364 : vn_ssa_aux_t vn_info = VN_INFO (temp);
3683 3364 : vn_info->value_id = val;
3684 3364 : vn_info->valnum = vn_valnum_from_value_id (val);
3685 3364 : if (vn_info->valnum == NULL_TREE)
3686 525 : vn_info->valnum = temp;
3687 3364 : bitmap_set_bit (inserted_exprs, SSA_NAME_VERSION (temp));
3688 3364 : pre_expr newe = get_or_alloc_expr_for_name (temp);
3689 3364 : add_to_value (val, newe);
3690 3364 : bitmap_value_replace_in_set (AVAIL_OUT (block), newe);
3691 3364 : bitmap_insert_into_set (NEW_SETS (block), newe);
3692 3364 : bitmap_insert_into_set (PHI_GEN (block), newe);
3693 : }
3694 : }
3695 : }
3696 :
3697 3723910 : return new_stuff;
3698 3723910 : }
3699 :
3700 :
3701 : /* Perform insertion for partially anticipatable expressions. There
3702 : is only one case we will perform insertion for these. This case is
3703 : if the expression is partially anticipatable, and fully available.
3704 : In this case, we know that putting it earlier will enable us to
3705 : remove the later computation. */
3706 :
3707 : static bool
3708 330938 : do_pre_partial_partial_insertion (basic_block block, basic_block dom,
3709 : vec<pre_expr> exprs)
3710 : {
3711 330938 : bool new_stuff = false;
3712 330938 : pre_expr expr;
3713 330938 : auto_vec<pre_expr, 2> avail;
3714 330938 : int i;
3715 :
3716 330938 : avail.safe_grow (EDGE_COUNT (block->preds), true);
3717 :
3718 3149599 : FOR_EACH_VEC_ELT (exprs, i, expr)
3719 : {
3720 2818661 : if (expr->kind == NARY
3721 2818661 : || expr->kind == REFERENCE)
3722 : {
3723 2120393 : unsigned int val;
3724 2120393 : bool by_all = true;
3725 2120393 : bool cant_insert = false;
3726 2120393 : edge pred;
3727 2120393 : basic_block bprime;
3728 2120393 : pre_expr eprime = NULL;
3729 2120393 : edge_iterator ei;
3730 :
3731 2120393 : val = get_expr_value_id (expr);
3732 4240786 : if (bitmap_set_contains_value (PHI_GEN (block), val))
3733 55668 : continue;
3734 2111079 : if (bitmap_set_contains_value (AVAIL_OUT (dom), val))
3735 46354 : continue;
3736 :
3737 2139299 : FOR_EACH_EDGE (pred, ei, block->preds)
3738 : {
3739 2129369 : unsigned int vprime;
3740 2129369 : pre_expr edoubleprime;
3741 :
3742 : /* We should never run insertion for the exit block
3743 : and so not come across fake pred edges. */
3744 2129369 : gcc_assert (!(pred->flags & EDGE_FAKE));
3745 2129369 : bprime = pred->src;
3746 4258738 : eprime = phi_translate (NULL, expr, ANTIC_IN (block),
3747 2129369 : PA_IN (block), pred);
3748 :
3749 : /* eprime will generally only be NULL if the
3750 : value of the expression, translated
3751 : through the PHI for this predecessor, is
3752 : undefined. If that is the case, we can't
3753 : make the expression fully redundant,
3754 : because its value is undefined along a
3755 : predecessor path. We can thus break out
3756 : early because it doesn't matter what the
3757 : rest of the results are. */
3758 2129369 : if (eprime == NULL)
3759 : {
3760 20 : avail[pred->dest_idx] = NULL;
3761 20 : cant_insert = true;
3762 20 : break;
3763 : }
3764 :
3765 2129349 : vprime = get_expr_value_id (eprime);
3766 2129349 : edoubleprime = bitmap_find_leader (AVAIL_OUT (bprime), vprime);
3767 2129349 : avail[pred->dest_idx] = edoubleprime;
3768 2129349 : if (edoubleprime == NULL)
3769 : {
3770 : by_all = false;
3771 : break;
3772 : }
3773 : }
3774 :
3775 : /* If we can insert it, it's not the same value
3776 : already existing along every predecessor, and
3777 : it's defined by some predecessor, it is
3778 : partially redundant. */
3779 2064725 : if (!cant_insert && by_all)
3780 : {
3781 9930 : edge succ;
3782 9930 : bool do_insertion = false;
3783 :
3784 : /* Insert only if we can remove a later expression on a path
3785 : that we want to optimize for speed.
3786 : The phi node that we will be inserting in BLOCK is not free,
3787 : and inserting it for the sake of !optimize_for_speed successor
3788 : may cause regressions on the speed path. */
3789 27565 : FOR_EACH_EDGE (succ, ei, block->succs)
3790 : {
3791 17635 : if (bitmap_set_contains_value (PA_IN (succ->dest), val)
3792 17635 : || bitmap_set_contains_value (ANTIC_IN (succ->dest), val))
3793 : {
3794 9322 : if (optimize_edge_for_speed_p (succ))
3795 17635 : do_insertion = true;
3796 : }
3797 : }
3798 :
3799 9930 : if (!do_insertion)
3800 : {
3801 3625 : if (dump_file && (dump_flags & TDF_DETAILS))
3802 : {
3803 0 : fprintf (dump_file, "Skipping partial partial redundancy "
3804 : "for expression ");
3805 0 : print_pre_expr (dump_file, expr);
3806 0 : fprintf (dump_file, " (%04d), not (partially) anticipated "
3807 : "on any to be optimized for speed edges\n", val);
3808 : }
3809 : }
3810 6305 : else if (dbg_cnt (treepre_insert))
3811 : {
3812 6305 : pre_stats.pa_insert++;
3813 6305 : if (dump_file && (dump_flags & TDF_DETAILS))
3814 : {
3815 0 : fprintf (dump_file, "Found partial partial redundancy "
3816 : "for expression ");
3817 0 : print_pre_expr (dump_file, expr);
3818 0 : fprintf (dump_file, " (%04d)\n",
3819 : get_expr_value_id (expr));
3820 : }
3821 6305 : if (insert_into_preds_of_block (block,
3822 : get_expression_id (expr),
3823 : avail))
3824 9930 : new_stuff = true;
3825 : }
3826 : }
3827 : }
3828 : }
3829 :
3830 330938 : return new_stuff;
3831 330938 : }
3832 :
3833 : /* Insert expressions in BLOCK to compute hoistable values up.
3834 : Return TRUE if something was inserted, otherwise return FALSE.
3835 : The caller has to make sure that BLOCK has at least two successors. */
3836 :
3837 : static bool
3838 4790780 : do_hoist_insertion (basic_block block)
3839 : {
3840 4790780 : edge e;
3841 4790780 : edge_iterator ei;
3842 4790780 : bool new_stuff = false;
3843 4790780 : unsigned i;
3844 4790780 : gimple_stmt_iterator last;
3845 :
3846 : /* At least two successors, or else... */
3847 4790780 : gcc_assert (EDGE_COUNT (block->succs) >= 2);
3848 :
3849 : /* Check that all successors of BLOCK are dominated by block.
3850 : We could use dominated_by_p() for this, but actually there is a much
3851 : quicker check: any successor that is dominated by BLOCK can't have
3852 : more than one predecessor edge. */
3853 14459308 : FOR_EACH_EDGE (e, ei, block->succs)
3854 14318479 : if (! single_pred_p (e->dest))
3855 : return false;
3856 :
3857 : /* Determine the insertion point. If we cannot safely insert before
3858 : the last stmt if we'd have to, bail out. */
3859 4783324 : last = gsi_last_bb (block);
3860 4783324 : if (!gsi_end_p (last)
3861 4782875 : && !is_ctrl_stmt (gsi_stmt (last))
3862 5365140 : && stmt_ends_bb_p (gsi_stmt (last)))
3863 : return false;
3864 :
3865 : /* We have multiple successors, compute ANTIC_OUT by taking the intersection
3866 : of all of ANTIC_IN translating through PHI nodes. Track the union
3867 : of the expression sets so we can pick a representative that is
3868 : fully generatable out of hoistable expressions. */
3869 4202093 : bitmap_set_t ANTIC_OUT = bitmap_set_new ();
3870 4202093 : bool first = true;
3871 12701796 : FOR_EACH_EDGE (e, ei, block->succs)
3872 : {
3873 8499703 : if (first)
3874 : {
3875 4202093 : phi_translate_set (ANTIC_OUT, ANTIC_IN (e->dest), e);
3876 4202093 : first = false;
3877 : }
3878 4297610 : else if (!gimple_seq_empty_p (phi_nodes (e->dest)))
3879 : {
3880 7 : bitmap_set_t tmp = bitmap_set_new ();
3881 7 : phi_translate_set (tmp, ANTIC_IN (e->dest), e);
3882 7 : bitmap_and_into (&ANTIC_OUT->values, &tmp->values);
3883 7 : bitmap_ior_into (&ANTIC_OUT->expressions, &tmp->expressions);
3884 7 : bitmap_set_free (tmp);
3885 : }
3886 : else
3887 : {
3888 4297603 : bitmap_and_into (&ANTIC_OUT->values, &ANTIC_IN (e->dest)->values);
3889 4297603 : bitmap_ior_into (&ANTIC_OUT->expressions,
3890 4297603 : &ANTIC_IN (e->dest)->expressions);
3891 : }
3892 : }
3893 :
3894 : /* Compute the set of hoistable expressions from ANTIC_OUT. First compute
3895 : hoistable values. */
3896 4202093 : bitmap_set hoistable_set;
3897 :
3898 : /* A hoistable value must be in ANTIC_OUT(block)
3899 : but not in AVAIL_OUT(BLOCK). */
3900 4202093 : bitmap_initialize (&hoistable_set.values, &grand_bitmap_obstack);
3901 4202093 : bitmap_and_compl (&hoistable_set.values,
3902 4202093 : &ANTIC_OUT->values, &AVAIL_OUT (block)->values);
3903 :
3904 : /* Short-cut for a common case: hoistable_set is empty. */
3905 4202093 : if (bitmap_empty_p (&hoistable_set.values))
3906 : {
3907 3447618 : bitmap_set_free (ANTIC_OUT);
3908 3447618 : return false;
3909 : }
3910 :
3911 : /* Compute which of the hoistable values is in AVAIL_OUT of
3912 : at least one of the successors of BLOCK. */
3913 754475 : bitmap_head availout_in_some;
3914 754475 : bitmap_initialize (&availout_in_some, &grand_bitmap_obstack);
3915 2277285 : FOR_EACH_EDGE (e, ei, block->succs)
3916 : /* Do not consider expressions solely because their availability
3917 : on loop exits. They'd be ANTIC-IN throughout the whole loop
3918 : and thus effectively hoisted across loops by combination of
3919 : PRE and hoisting. */
3920 1522810 : if (! loop_exit_edge_p (block->loop_father, e))
3921 1356807 : bitmap_ior_and_into (&availout_in_some, &hoistable_set.values,
3922 1356807 : &AVAIL_OUT (e->dest)->values);
3923 754475 : bitmap_clear (&hoistable_set.values);
3924 :
3925 : /* Short-cut for a common case: availout_in_some is empty. */
3926 754475 : if (bitmap_empty_p (&availout_in_some))
3927 : {
3928 613646 : bitmap_set_free (ANTIC_OUT);
3929 613646 : return false;
3930 : }
3931 :
3932 : /* Hack hoistable_set in-place so we can use sorted_array_from_bitmap_set. */
3933 140829 : bitmap_move (&hoistable_set.values, &availout_in_some);
3934 140829 : hoistable_set.expressions = ANTIC_OUT->expressions;
3935 :
3936 : /* Now finally construct the topological-ordered expression set. */
3937 140829 : vec<pre_expr> exprs = sorted_array_from_bitmap_set (&hoistable_set, true);
3938 :
3939 : /* If there are candidate values for hoisting, insert expressions
3940 : strategically to make the hoistable expressions fully redundant. */
3941 140829 : pre_expr expr;
3942 363532 : FOR_EACH_VEC_ELT (exprs, i, expr)
3943 : {
3944 : /* While we try to sort expressions topologically above the
3945 : sorting doesn't work out perfectly. Catch expressions we
3946 : already inserted. */
3947 222703 : unsigned int value_id = get_expr_value_id (expr);
3948 445406 : if (bitmap_set_contains_value (AVAIL_OUT (block), value_id))
3949 : {
3950 0 : if (dump_file && (dump_flags & TDF_DETAILS))
3951 : {
3952 0 : fprintf (dump_file,
3953 : "Already inserted expression for ");
3954 0 : print_pre_expr (dump_file, expr);
3955 0 : fprintf (dump_file, " (%04d)\n", value_id);
3956 : }
3957 28 : continue;
3958 : }
3959 :
3960 : /* If we end up with a punned expression representation and this
3961 : happens to be a float typed one give up - we can't know for
3962 : sure whether all paths perform the floating-point load we are
3963 : about to insert and on some targets this can cause correctness
3964 : issues. See PR88240. */
3965 222703 : if (expr->kind == REFERENCE
3966 97941 : && PRE_EXPR_REFERENCE (expr)->punned
3967 222703 : && FLOAT_TYPE_P (get_expr_type (expr)))
3968 0 : continue;
3969 :
3970 : /* Only hoist if the full expression is available for hoisting.
3971 : This avoids hoisting values that are not common and for
3972 : example evaluate an expression that's not valid to evaluate
3973 : unconditionally (PR112310). */
3974 222703 : if (!valid_in_sets (&hoistable_set, AVAIL_OUT (block), expr))
3975 9 : continue;
3976 :
3977 : /* OK, we should hoist this value. Perform the transformation. */
3978 222694 : pre_stats.hoist_insert++;
3979 222694 : if (dump_file && (dump_flags & TDF_DETAILS))
3980 : {
3981 2 : fprintf (dump_file,
3982 : "Inserting expression in block %d for code hoisting: ",
3983 : block->index);
3984 2 : print_pre_expr (dump_file, expr);
3985 2 : fprintf (dump_file, " (%04d)\n", value_id);
3986 : }
3987 :
3988 222694 : gimple_seq stmts = NULL;
3989 222694 : tree res = create_expression_by_pieces (block, expr, &stmts,
3990 : get_expr_type (expr));
3991 :
3992 : /* Do not return true if expression creation ultimately
3993 : did not insert any statements. */
3994 222694 : if (gimple_seq_empty_p (stmts))
3995 : res = NULL_TREE;
3996 : else
3997 : {
3998 222675 : if (gsi_end_p (last) || is_ctrl_stmt (gsi_stmt (last)))
3999 222675 : gsi_insert_seq_before (&last, stmts, GSI_SAME_STMT);
4000 : else
4001 0 : gsi_insert_seq_after (&last, stmts, GSI_NEW_STMT);
4002 : }
4003 :
4004 : /* Make sure to not return true if expression creation ultimately
4005 : failed but also make sure to insert any stmts produced as they
4006 : are tracked in inserted_exprs. */
4007 222675 : if (! res)
4008 19 : continue;
4009 :
4010 222675 : new_stuff = true;
4011 : }
4012 :
4013 140829 : exprs.release ();
4014 140829 : bitmap_clear (&hoistable_set.values);
4015 140829 : bitmap_set_free (ANTIC_OUT);
4016 :
4017 140829 : return new_stuff;
4018 : }
4019 :
4020 : /* Perform insertion of partially redundant and hoistable values. */
4021 :
4022 : static void
4023 976700 : insert (void)
4024 : {
4025 976700 : basic_block bb;
4026 :
4027 16267965 : FOR_ALL_BB_FN (bb, cfun)
4028 15291265 : NEW_SETS (bb) = bitmap_set_new ();
4029 :
4030 976700 : int *rpo = XNEWVEC (int, n_basic_blocks_for_fn (cfun));
4031 976700 : int *bb_rpo = XNEWVEC (int, last_basic_block_for_fn (cfun) + 1);
4032 976700 : int rpo_num = pre_and_rev_post_order_compute (NULL, rpo, false);
4033 14314565 : for (int i = 0; i < rpo_num; ++i)
4034 13337865 : bb_rpo[rpo[i]] = i;
4035 :
4036 : int num_iterations = 0;
4037 1029240 : bool changed;
4038 1029240 : do
4039 : {
4040 1029240 : num_iterations++;
4041 1029240 : if (dump_file && dump_flags & TDF_DETAILS)
4042 18 : fprintf (dump_file, "Starting insert iteration %d\n", num_iterations);
4043 :
4044 : changed = false;
4045 18627549 : for (int idx = 0; idx < rpo_num; ++idx)
4046 : {
4047 17598309 : basic_block block = BASIC_BLOCK_FOR_FN (cfun, rpo[idx]);
4048 17598309 : basic_block dom = get_immediate_dominator (CDI_DOMINATORS, block);
4049 17598309 : if (dom)
4050 : {
4051 17598309 : unsigned i;
4052 17598309 : bitmap_iterator bi;
4053 17598309 : bitmap_set_t newset;
4054 :
4055 : /* First, update the AVAIL_OUT set with anything we may have
4056 : inserted higher up in the dominator tree. */
4057 17598309 : newset = NEW_SETS (dom);
4058 :
4059 : /* Note that we need to value_replace both NEW_SETS, and
4060 : AVAIL_OUT. For both the case of NEW_SETS, the value may be
4061 : represented by some non-simple expression here that we want
4062 : to replace it with. */
4063 17598309 : bool avail_out_changed = false;
4064 33562704 : FOR_EACH_EXPR_ID_IN_SET (newset, i, bi)
4065 : {
4066 15964395 : pre_expr expr = expression_for_id (i);
4067 15964395 : bitmap_value_replace_in_set (NEW_SETS (block), expr);
4068 15964395 : avail_out_changed
4069 15964395 : |= bitmap_value_replace_in_set (AVAIL_OUT (block), expr);
4070 : }
4071 : /* We need to iterate if AVAIL_OUT of an already processed
4072 : block source changed. */
4073 17598309 : if (avail_out_changed && !changed)
4074 : {
4075 1719282 : edge_iterator ei;
4076 1719282 : edge e;
4077 4090097 : FOR_EACH_EDGE (e, ei, block->succs)
4078 2370815 : if (e->dest->index != EXIT_BLOCK
4079 2263467 : && bb_rpo[e->dest->index] < idx)
4080 2370815 : changed = true;
4081 : }
4082 :
4083 : /* Insert expressions for partial redundancies. */
4084 35195802 : if (flag_tree_pre && !single_pred_p (block))
4085 : {
4086 3451114 : vec<pre_expr> exprs
4087 3451114 : = sorted_array_from_bitmap_set (ANTIC_IN (block), true);
4088 : /* Sorting is not perfect, iterate locally. */
4089 7175024 : while (do_pre_regular_insertion (block, dom, exprs))
4090 : ;
4091 3451114 : exprs.release ();
4092 3451114 : if (do_partial_partial)
4093 : {
4094 327984 : exprs = sorted_array_from_bitmap_set (PA_IN (block),
4095 : true);
4096 658922 : while (do_pre_partial_partial_insertion (block, dom,
4097 : exprs))
4098 : ;
4099 327984 : exprs.release ();
4100 : }
4101 : }
4102 : }
4103 : }
4104 :
4105 : /* Clear the NEW sets before the next iteration. We have already
4106 : fully propagated its contents. */
4107 1029240 : if (changed)
4108 4418064 : FOR_ALL_BB_FN (bb, cfun)
4109 8731048 : bitmap_set_free (NEW_SETS (bb));
4110 : }
4111 : while (changed);
4112 :
4113 976700 : statistics_histogram_event (cfun, "insert iterations", num_iterations);
4114 :
4115 : /* AVAIL_OUT is not needed after insertion so we don't have to
4116 : propagate NEW_SETS from hoist insertion. */
4117 16267965 : FOR_ALL_BB_FN (bb, cfun)
4118 : {
4119 15291265 : bitmap_set_free (NEW_SETS (bb));
4120 15291265 : bitmap_set_pool.remove (NEW_SETS (bb));
4121 15291265 : NEW_SETS (bb) = NULL;
4122 : }
4123 :
4124 : /* Insert expressions for hoisting. Do a backward walk here since
4125 : inserting into BLOCK exposes new opportunities in its predecessors.
4126 : Since PRE and hoist insertions can cause back-to-back iteration
4127 : and we are interested in PRE insertion exposed hoisting opportunities
4128 : but not in hoisting exposed PRE ones do hoist insertion only after
4129 : PRE insertion iteration finished and do not iterate it. */
4130 976700 : if (flag_code_hoisting)
4131 14314016 : for (int idx = rpo_num - 1; idx >= 0; --idx)
4132 : {
4133 13337369 : basic_block block = BASIC_BLOCK_FOR_FN (cfun, rpo[idx]);
4134 18128149 : if (EDGE_COUNT (block->succs) >= 2)
4135 4790780 : changed |= do_hoist_insertion (block);
4136 : }
4137 :
4138 976700 : free (rpo);
4139 976700 : free (bb_rpo);
4140 976700 : }
4141 :
4142 :
4143 : /* Compute the AVAIL set for all basic blocks.
4144 :
4145 : This function performs value numbering of the statements in each basic
4146 : block. The AVAIL sets are built from information we glean while doing
4147 : this value numbering, since the AVAIL sets contain only one entry per
4148 : value.
4149 :
4150 : AVAIL_IN[BLOCK] = AVAIL_OUT[dom(BLOCK)].
4151 : AVAIL_OUT[BLOCK] = AVAIL_IN[BLOCK] U PHI_GEN[BLOCK] U TMP_GEN[BLOCK]. */
4152 :
4153 : static void
4154 976700 : compute_avail (function *fun)
4155 : {
4156 :
4157 976700 : basic_block block, son;
4158 976700 : basic_block *worklist;
4159 976700 : size_t sp = 0;
4160 976700 : unsigned i;
4161 976700 : tree name;
4162 :
4163 : /* We pretend that default definitions are defined in the entry block.
4164 : This includes function arguments and the static chain decl. */
4165 47911217 : FOR_EACH_SSA_NAME (i, name, fun)
4166 : {
4167 34059259 : pre_expr e;
4168 34059259 : if (!SSA_NAME_IS_DEFAULT_DEF (name)
4169 2951906 : || has_zero_uses (name)
4170 36468834 : || virtual_operand_p (name))
4171 32625566 : continue;
4172 :
4173 1433693 : e = get_or_alloc_expr_for_name (name);
4174 1433693 : add_to_value (get_expr_value_id (e), e);
4175 1433693 : bitmap_insert_into_set (TMP_GEN (ENTRY_BLOCK_PTR_FOR_FN (fun)), e);
4176 1433693 : bitmap_value_insert_into_set (AVAIL_OUT (ENTRY_BLOCK_PTR_FOR_FN (fun)),
4177 : e);
4178 : }
4179 :
4180 976700 : if (dump_file && (dump_flags & TDF_DETAILS))
4181 : {
4182 14 : print_bitmap_set (dump_file, TMP_GEN (ENTRY_BLOCK_PTR_FOR_FN (fun)),
4183 : "tmp_gen", ENTRY_BLOCK);
4184 14 : print_bitmap_set (dump_file, AVAIL_OUT (ENTRY_BLOCK_PTR_FOR_FN (fun)),
4185 : "avail_out", ENTRY_BLOCK);
4186 : }
4187 :
4188 : /* Allocate the worklist. */
4189 976700 : worklist = XNEWVEC (basic_block, n_basic_blocks_for_fn (fun));
4190 :
4191 : /* Seed the algorithm by putting the dominator children of the entry
4192 : block on the worklist. */
4193 976700 : for (son = first_dom_son (CDI_DOMINATORS, ENTRY_BLOCK_PTR_FOR_FN (fun));
4194 1953400 : son;
4195 976700 : son = next_dom_son (CDI_DOMINATORS, son))
4196 976700 : worklist[sp++] = son;
4197 :
4198 1953400 : BB_LIVE_VOP_ON_EXIT (ENTRY_BLOCK_PTR_FOR_FN (fun))
4199 976700 : = ssa_default_def (fun, gimple_vop (fun));
4200 :
4201 : /* Loop until the worklist is empty. */
4202 14314565 : while (sp)
4203 : {
4204 13337865 : gimple *stmt;
4205 13337865 : basic_block dom;
4206 :
4207 : /* Pick a block from the worklist. */
4208 13337865 : block = worklist[--sp];
4209 13337865 : vn_context_bb = block;
4210 :
4211 : /* Initially, the set of available values in BLOCK is that of
4212 : its immediate dominator. */
4213 13337865 : dom = get_immediate_dominator (CDI_DOMINATORS, block);
4214 13337865 : if (dom)
4215 : {
4216 13337865 : bitmap_set_copy (AVAIL_OUT (block), AVAIL_OUT (dom));
4217 13337865 : BB_LIVE_VOP_ON_EXIT (block) = BB_LIVE_VOP_ON_EXIT (dom);
4218 : }
4219 :
4220 : /* Generate values for PHI nodes. */
4221 17191435 : for (gphi_iterator gsi = gsi_start_phis (block); !gsi_end_p (gsi);
4222 3853570 : gsi_next (&gsi))
4223 : {
4224 3853570 : tree result = gimple_phi_result (gsi.phi ());
4225 :
4226 : /* We have no need for virtual phis, as they don't represent
4227 : actual computations. */
4228 7707140 : if (virtual_operand_p (result))
4229 : {
4230 1761333 : BB_LIVE_VOP_ON_EXIT (block) = result;
4231 1761333 : continue;
4232 : }
4233 :
4234 2092237 : pre_expr e = get_or_alloc_expr_for_name (result);
4235 2092237 : add_to_value (get_expr_value_id (e), e);
4236 2092237 : bitmap_value_insert_into_set (AVAIL_OUT (block), e);
4237 2092237 : bitmap_insert_into_set (PHI_GEN (block), e);
4238 : }
4239 :
4240 13337865 : BB_MAY_NOTRETURN (block) = 0;
4241 :
4242 : /* Now compute value numbers and populate value sets with all
4243 : the expressions computed in BLOCK. */
4244 13337865 : bool set_bb_may_notreturn = false;
4245 111295568 : for (gimple_stmt_iterator gsi = gsi_start_bb (block); !gsi_end_p (gsi);
4246 84619838 : gsi_next (&gsi))
4247 : {
4248 84619838 : ssa_op_iter iter;
4249 84619838 : tree op;
4250 :
4251 84619838 : stmt = gsi_stmt (gsi);
4252 :
4253 84619838 : if (set_bb_may_notreturn)
4254 : {
4255 2755454 : BB_MAY_NOTRETURN (block) = 1;
4256 2755454 : set_bb_may_notreturn = false;
4257 : }
4258 :
4259 : /* Cache whether the basic-block has any non-visible side-effect
4260 : or control flow.
4261 : If this isn't a call or it is the last stmt in the
4262 : basic-block then the CFG represents things correctly. */
4263 84619838 : if (is_gimple_call (stmt) && !stmt_ends_bb_p (stmt))
4264 : {
4265 : /* Non-looping const functions always return normally.
4266 : Otherwise the call might not return or have side-effects
4267 : that forbids hoisting possibly trapping expressions
4268 : before it. */
4269 3886287 : int flags = gimple_call_flags (stmt);
4270 3886287 : if (!(flags & (ECF_CONST|ECF_PURE))
4271 591537 : || (flags & ECF_LOOPING_CONST_OR_PURE)
4272 4450916 : || stmt_can_throw_external (fun, stmt))
4273 : /* Defer setting of BB_MAY_NOTRETURN to avoid it
4274 : influencing the processing of the call itself. */
4275 : set_bb_may_notreturn = true;
4276 : }
4277 :
4278 99715142 : FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_DEF)
4279 : {
4280 15095304 : pre_expr e = get_or_alloc_expr_for_name (op);
4281 15095304 : add_to_value (get_expr_value_id (e), e);
4282 15095304 : bitmap_insert_into_set (TMP_GEN (block), e);
4283 15095304 : bitmap_value_insert_into_set (AVAIL_OUT (block), e);
4284 : }
4285 :
4286 111858719 : if (gimple_vdef (stmt))
4287 12068514 : BB_LIVE_VOP_ON_EXIT (block) = gimple_vdef (stmt);
4288 :
4289 84619838 : if (gimple_has_side_effects (stmt)
4290 78264914 : || stmt_could_throw_p (fun, stmt)
4291 161723535 : || is_gimple_debug (stmt))
4292 79325081 : continue;
4293 :
4294 47643897 : FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_USE)
4295 : {
4296 22479344 : if (ssa_undefined_value_p (op))
4297 57312 : continue;
4298 22422032 : pre_expr e = get_or_alloc_expr_for_name (op);
4299 22422032 : bitmap_value_insert_into_set (EXP_GEN (block), e);
4300 : }
4301 :
4302 25164553 : switch (gimple_code (stmt))
4303 : {
4304 951733 : case GIMPLE_RETURN:
4305 951733 : continue;
4306 :
4307 562360 : case GIMPLE_CALL:
4308 562360 : {
4309 562360 : vn_reference_t ref;
4310 562360 : vn_reference_s ref1;
4311 562360 : pre_expr result = NULL;
4312 :
4313 562360 : vn_reference_lookup_call (as_a <gcall *> (stmt), &ref, &ref1);
4314 : /* There is no point to PRE a call without a value. */
4315 562360 : if (!ref || !ref->result)
4316 32335 : continue;
4317 :
4318 : /* If the value of the call is not invalidated in
4319 : this block until it is computed, add the expression
4320 : to EXP_GEN. */
4321 530025 : if ((!gimple_vuse (stmt)
4322 304126 : || gimple_code
4323 304126 : (SSA_NAME_DEF_STMT (gimple_vuse (stmt))) == GIMPLE_PHI
4324 277940 : || gimple_bb (SSA_NAME_DEF_STMT
4325 : (gimple_vuse (stmt))) != block)
4326 : /* If the REFERENCE traps and there was a preceding
4327 : point in the block that might not return avoid
4328 : adding the reference to EXP_GEN. */
4329 777586 : && (!BB_MAY_NOTRETURN (block)
4330 10727 : || !vn_reference_may_trap (ref)))
4331 : {
4332 462733 : result = get_or_alloc_expr_for_reference
4333 462733 : (ref, ref->value_id, gimple_location (stmt));
4334 462733 : add_to_value (get_expr_value_id (result), result);
4335 462733 : bitmap_value_insert_into_set (EXP_GEN (block), result);
4336 : }
4337 530025 : continue;
4338 530025 : }
4339 :
4340 18355703 : case GIMPLE_ASSIGN:
4341 18355703 : {
4342 18355703 : pre_expr result = NULL;
4343 18355703 : switch (vn_get_stmt_kind (stmt))
4344 : {
4345 7643287 : case VN_NARY:
4346 7643287 : {
4347 7643287 : enum tree_code code = gimple_assign_rhs_code (stmt);
4348 7643287 : vn_nary_op_t nary;
4349 :
4350 : /* COND_EXPR is awkward in that it contains an
4351 : embedded complex expression.
4352 : Don't even try to shove it through PRE. */
4353 7643287 : if (code == COND_EXPR)
4354 142183 : continue;
4355 :
4356 7639200 : vn_nary_op_lookup_stmt (stmt, &nary);
4357 7639200 : if (!nary || nary->predicated_values)
4358 108211 : continue;
4359 :
4360 7530989 : unsigned value_id = nary->value_id;
4361 7530989 : if (value_id_constant_p (value_id))
4362 0 : continue;
4363 :
4364 : /* Record the un-valueized expression for EXP_GEN. */
4365 7530989 : nary = XALLOCAVAR (struct vn_nary_op_s,
4366 : sizeof_vn_nary_op
4367 : (vn_nary_length_from_stmt (stmt)));
4368 7530989 : init_vn_nary_op_from_stmt (nary, as_a <gassign *> (stmt));
4369 :
4370 : /* If the NARY traps and there was a preceding
4371 : point in the block that might not return avoid
4372 : adding the nary to EXP_GEN. */
4373 7560874 : if (BB_MAY_NOTRETURN (block)
4374 7530989 : && vn_nary_may_trap (nary))
4375 29885 : continue;
4376 :
4377 7501104 : result = get_or_alloc_expr_for_nary
4378 7501104 : (nary, value_id, gimple_location (stmt));
4379 7501104 : break;
4380 : }
4381 :
4382 5171491 : case VN_REFERENCE:
4383 5171491 : {
4384 5171491 : tree rhs1 = gimple_assign_rhs1 (stmt);
4385 : /* There is no point in trying to handle aggregates,
4386 : even when via punning we might get a value number
4387 : corresponding to a register typed load. */
4388 5171491 : if (!is_gimple_reg_type (TREE_TYPE (rhs1)))
4389 1477680 : continue;
4390 4805962 : ao_ref rhs1_ref;
4391 4805962 : ao_ref_init (&rhs1_ref, rhs1);
4392 4805962 : alias_set_type set = ao_ref_alias_set (&rhs1_ref);
4393 4805962 : alias_set_type base_set
4394 4805962 : = ao_ref_base_alias_set (&rhs1_ref);
4395 4805962 : vec<vn_reference_op_s> operands
4396 4805962 : = vn_reference_operands_for_lookup (rhs1);
4397 4805962 : vn_reference_t ref;
4398 :
4399 : /* We handle &MEM[ptr + 5].b[1].c as
4400 : POINTER_PLUS_EXPR. */
4401 4805962 : if (operands[0].opcode == ADDR_EXPR
4402 5069568 : && operands.last ().opcode == SSA_NAME)
4403 : {
4404 263594 : tree ops[2];
4405 263594 : if (vn_pp_nary_for_addr (operands, ops))
4406 : {
4407 176030 : vn_nary_op_t nary;
4408 176030 : vn_nary_op_lookup_pieces (2, POINTER_PLUS_EXPR,
4409 176030 : TREE_TYPE (rhs1), ops,
4410 : &nary);
4411 176030 : operands.release ();
4412 176030 : if (nary && !nary->predicated_values)
4413 : {
4414 176018 : unsigned value_id = nary->value_id;
4415 176018 : if (value_id_constant_p (value_id))
4416 12 : continue;
4417 176018 : result = get_or_alloc_expr_for_nary
4418 176018 : (nary, value_id, gimple_location (stmt));
4419 176018 : break;
4420 : }
4421 12 : continue;
4422 12 : }
4423 : }
4424 :
4425 9259864 : vn_reference_lookup_pieces (gimple_vuse (stmt), set,
4426 4629932 : base_set, TREE_TYPE (rhs1),
4427 : operands, &ref, VN_WALK);
4428 : /* When there is no value recorded or the value was
4429 : recorded for a different type, fail, similar as
4430 : how we do during PHI translation. */
4431 4633035 : if (!ref
4432 4629932 : || !useless_type_conversion_p (TREE_TYPE (rhs1),
4433 : ref->type))
4434 : {
4435 3103 : operands.release ();
4436 3103 : continue;
4437 : }
4438 4626829 : operands.release ();
4439 :
4440 : /* If the REFERENCE traps and there was a preceding
4441 : point in the block that might not return avoid
4442 : adding the reference to EXP_GEN. */
4443 4789762 : if (BB_MAY_NOTRETURN (block)
4444 4626829 : && gimple_could_trap_p_1 (stmt, true, false))
4445 162933 : continue;
4446 :
4447 : /* If the value of the reference is not invalidated in
4448 : this block until it is computed, add the expression
4449 : to EXP_GEN. */
4450 8927792 : if (gimple_vuse (stmt))
4451 : {
4452 4376337 : gimple *def_stmt;
4453 4376337 : bool ok = true;
4454 4376337 : def_stmt = SSA_NAME_DEF_STMT (gimple_vuse (stmt));
4455 7038599 : while (!gimple_nop_p (def_stmt)
4456 6056288 : && gimple_code (def_stmt) != GIMPLE_PHI
4457 11884263 : && gimple_bb (def_stmt) == block)
4458 : {
4459 3608365 : if (stmt_may_clobber_ref_p
4460 3608365 : (def_stmt, gimple_assign_rhs1 (stmt)))
4461 : {
4462 : ok = false;
4463 : break;
4464 : }
4465 2662262 : def_stmt
4466 2662262 : = SSA_NAME_DEF_STMT (gimple_vuse (def_stmt));
4467 : }
4468 4376337 : if (!ok)
4469 946103 : continue;
4470 : }
4471 :
4472 : /* Record the un-valueized expression for EXP_GEN. */
4473 3517793 : copy_reference_ops_from_ref (rhs1, &operands);
4474 3517793 : vn_reference_t newref
4475 3517793 : = XALLOCAVAR (struct vn_reference_s,
4476 : sizeof (vn_reference_s));
4477 3517793 : memset (newref, 0, sizeof (vn_reference_s));
4478 3517793 : newref->value_id = ref->value_id;
4479 3517793 : newref->vuse = ref->vuse;
4480 3517793 : newref->operands = operands;
4481 3517793 : newref->type = TREE_TYPE (rhs1);
4482 3517793 : newref->set = set;
4483 3517793 : newref->base_set = base_set;
4484 3517793 : newref->offset = 0;
4485 3517793 : newref->max_size = -1;
4486 3517793 : newref->result = ref->result;
4487 3517793 : newref->hashcode = vn_reference_compute_hash (newref);
4488 :
4489 3517793 : result = get_or_alloc_expr_for_reference
4490 3517793 : (newref, newref->value_id,
4491 : gimple_location (stmt), true);
4492 3517793 : break;
4493 : }
4494 :
4495 5540925 : default:
4496 5540925 : continue;
4497 5540925 : }
4498 :
4499 11194915 : add_to_value (get_expr_value_id (result), result);
4500 11194915 : bitmap_value_insert_into_set (EXP_GEN (block), result);
4501 11194915 : continue;
4502 11194915 : }
4503 5294757 : default:
4504 5294757 : break;
4505 951733 : }
4506 : }
4507 13337865 : if (set_bb_may_notreturn)
4508 : {
4509 568471 : BB_MAY_NOTRETURN (block) = 1;
4510 568471 : set_bb_may_notreturn = false;
4511 : }
4512 :
4513 13337865 : if (dump_file && (dump_flags & TDF_DETAILS))
4514 : {
4515 108 : print_bitmap_set (dump_file, EXP_GEN (block),
4516 : "exp_gen", block->index);
4517 108 : print_bitmap_set (dump_file, PHI_GEN (block),
4518 : "phi_gen", block->index);
4519 108 : print_bitmap_set (dump_file, TMP_GEN (block),
4520 : "tmp_gen", block->index);
4521 108 : print_bitmap_set (dump_file, AVAIL_OUT (block),
4522 : "avail_out", block->index);
4523 : }
4524 :
4525 : /* Put the dominator children of BLOCK on the worklist of blocks
4526 : to compute available sets for. */
4527 13337865 : for (son = first_dom_son (CDI_DOMINATORS, block);
4528 25699030 : son;
4529 12361165 : son = next_dom_son (CDI_DOMINATORS, son))
4530 12361165 : worklist[sp++] = son;
4531 : }
4532 976700 : vn_context_bb = NULL;
4533 :
4534 976700 : free (worklist);
4535 976700 : }
4536 :
4537 :
4538 : /* Initialize data structures used by PRE. */
4539 :
4540 : static void
4541 976707 : init_pre (void)
4542 : {
4543 976707 : basic_block bb;
4544 :
4545 976707 : next_expression_id = 1;
4546 976707 : expressions.create (0);
4547 976707 : expressions.safe_push (NULL);
4548 976707 : value_expressions.create (get_max_value_id () + 1);
4549 976707 : value_expressions.quick_grow_cleared (get_max_value_id () + 1);
4550 976707 : constant_value_expressions.create (get_max_constant_value_id () + 1);
4551 976707 : constant_value_expressions.quick_grow_cleared (get_max_constant_value_id () + 1);
4552 976707 : name_to_id.create (0);
4553 976707 : gcc_obstack_init (&pre_expr_obstack);
4554 :
4555 976707 : inserted_exprs = BITMAP_ALLOC (NULL);
4556 :
4557 976707 : connect_infinite_loops_to_exit ();
4558 976707 : memset (&pre_stats, 0, sizeof (pre_stats));
4559 :
4560 976707 : alloc_aux_for_blocks (sizeof (struct bb_bitmap_sets));
4561 :
4562 976707 : calculate_dominance_info (CDI_DOMINATORS);
4563 :
4564 976707 : bitmap_obstack_initialize (&grand_bitmap_obstack);
4565 1953414 : expression_to_id = new hash_table<pre_expr_d> (num_ssa_names * 3);
4566 16305536 : FOR_ALL_BB_FN (bb, cfun)
4567 : {
4568 15328829 : EXP_GEN (bb) = bitmap_set_new ();
4569 15328829 : PHI_GEN (bb) = bitmap_set_new ();
4570 15328829 : TMP_GEN (bb) = bitmap_set_new ();
4571 15328829 : AVAIL_OUT (bb) = bitmap_set_new ();
4572 15328829 : PHI_TRANS_TABLE (bb) = NULL;
4573 : }
4574 976707 : }
4575 :
4576 :
4577 : /* Deallocate data structures used by PRE. */
4578 :
4579 : static void
4580 976707 : fini_pre ()
4581 : {
4582 976707 : value_expressions.release ();
4583 976707 : constant_value_expressions.release ();
4584 44827015 : for (unsigned i = 1; i < expressions.length (); ++i)
4585 43850308 : if (expressions[i]->kind == REFERENCE)
4586 6427762 : PRE_EXPR_REFERENCE (expressions[i])->operands.release ();
4587 976707 : expressions.release ();
4588 976707 : bitmap_obstack_release (&grand_bitmap_obstack);
4589 976707 : bitmap_set_pool.release ();
4590 976707 : pre_expr_pool.release ();
4591 976707 : delete expression_to_id;
4592 976707 : expression_to_id = NULL;
4593 976707 : name_to_id.release ();
4594 976707 : obstack_free (&pre_expr_obstack, NULL);
4595 :
4596 976707 : basic_block bb;
4597 16305234 : FOR_ALL_BB_FN (bb, cfun)
4598 15328527 : if (bb->aux && PHI_TRANS_TABLE (bb))
4599 6169210 : delete PHI_TRANS_TABLE (bb);
4600 976707 : free_aux_for_blocks ();
4601 976707 : }
4602 :
4603 : namespace {
4604 :
4605 : const pass_data pass_data_pre =
4606 : {
4607 : GIMPLE_PASS, /* type */
4608 : "pre", /* name */
4609 : OPTGROUP_NONE, /* optinfo_flags */
4610 : TV_TREE_PRE, /* tv_id */
4611 : ( PROP_cfg | PROP_ssa ), /* properties_required */
4612 : 0, /* properties_provided */
4613 : 0, /* properties_destroyed */
4614 : TODO_rebuild_alias, /* todo_flags_start */
4615 : 0, /* todo_flags_finish */
4616 : };
4617 :
4618 : class pass_pre : public gimple_opt_pass
4619 : {
4620 : public:
4621 292371 : pass_pre (gcc::context *ctxt)
4622 584742 : : gimple_opt_pass (pass_data_pre, ctxt)
4623 : {}
4624 :
4625 : /* opt_pass methods: */
4626 1055105 : bool gate (function *) final override
4627 1055105 : { return flag_tree_pre != 0 || flag_code_hoisting != 0; }
4628 : unsigned int execute (function *) final override;
4629 :
4630 : }; // class pass_pre
4631 :
4632 : /* Valueization hook for RPO VN when we are calling back to it
4633 : at ANTIC compute time. */
4634 :
4635 : static tree
4636 113160271 : pre_valueize (tree name)
4637 : {
4638 113160271 : if (TREE_CODE (name) == SSA_NAME)
4639 : {
4640 112894572 : tree tem = VN_INFO (name)->valnum;
4641 112894572 : if (tem != VN_TOP && tem != name)
4642 : {
4643 15768455 : if (TREE_CODE (tem) != SSA_NAME
4644 15768455 : || SSA_NAME_IS_DEFAULT_DEF (tem))
4645 : return tem;
4646 : /* We create temporary SSA names for representatives that
4647 : do not have a definition (yet) but are not default defs either
4648 : assume they are fine to use. */
4649 15763054 : basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (tem));
4650 15763054 : if (! def_bb
4651 15763054 : || dominated_by_p (CDI_DOMINATORS, vn_context_bb, def_bb))
4652 129912 : return tem;
4653 : /* ??? Now we could look for a leader. Ideally we'd somehow
4654 : expose RPO VN leaders and get rid of AVAIL_OUT as well... */
4655 : }
4656 : }
4657 : return name;
4658 : }
4659 :
4660 : unsigned int
4661 976707 : pass_pre::execute (function *fun)
4662 : {
4663 976707 : unsigned int todo = 0;
4664 :
4665 1953414 : do_partial_partial =
4666 976707 : flag_tree_partial_pre && optimize_function_for_speed_p (fun);
4667 :
4668 : /* This has to happen before VN runs because
4669 : loop_optimizer_init may create new phis, etc. */
4670 976707 : loop_optimizer_init (LOOPS_NORMAL);
4671 976707 : split_edges_for_insertion ();
4672 976707 : scev_initialize ();
4673 976707 : calculate_dominance_info (CDI_DOMINATORS);
4674 :
4675 976707 : run_rpo_vn (VN_WALK);
4676 :
4677 976707 : init_pre ();
4678 :
4679 976707 : vn_valueize = pre_valueize;
4680 :
4681 : /* Insert can get quite slow on an incredibly large number of basic
4682 : blocks due to some quadratic behavior. Until this behavior is
4683 : fixed, don't run it when he have an incredibly large number of
4684 : bb's. If we aren't going to run insert, there is no point in
4685 : computing ANTIC, either, even though it's plenty fast nor do
4686 : we require AVAIL. */
4687 976707 : if (n_basic_blocks_for_fn (fun) < 4000)
4688 : {
4689 976700 : compute_avail (fun);
4690 976700 : compute_antic ();
4691 976700 : insert ();
4692 : }
4693 :
4694 : /* Make sure to remove fake edges before committing our inserts.
4695 : This makes sure we don't end up with extra critical edges that
4696 : we would need to split. */
4697 976707 : remove_fake_exit_edges ();
4698 976707 : gsi_commit_edge_inserts ();
4699 :
4700 : /* Eliminate folds statements which might (should not...) end up
4701 : not keeping virtual operands up-to-date. */
4702 976707 : gcc_assert (!need_ssa_update_p (fun));
4703 :
4704 976707 : statistics_counter_event (fun, "Insertions", pre_stats.insertions);
4705 976707 : statistics_counter_event (fun, "PA inserted", pre_stats.pa_insert);
4706 976707 : statistics_counter_event (fun, "HOIST inserted", pre_stats.hoist_insert);
4707 976707 : statistics_counter_event (fun, "New PHIs", pre_stats.phis);
4708 :
4709 976707 : todo |= eliminate_with_rpo_vn (inserted_exprs);
4710 :
4711 976707 : vn_valueize = NULL;
4712 :
4713 976707 : fini_pre ();
4714 :
4715 976707 : scev_finalize ();
4716 976707 : loop_optimizer_finalize ();
4717 :
4718 : /* Perform a CFG cleanup before we run simple_dce_from_worklist since
4719 : unreachable code regions will have not up-to-date SSA form which
4720 : confuses it. */
4721 976707 : bool need_crit_edge_split = false;
4722 976707 : if (todo & TODO_cleanup_cfg)
4723 : {
4724 140066 : cleanup_tree_cfg ();
4725 140066 : need_crit_edge_split = true;
4726 : }
4727 :
4728 : /* Because we don't follow exactly the standard PRE algorithm, and decide not
4729 : to insert PHI nodes sometimes, and because value numbering of casts isn't
4730 : perfect, we sometimes end up inserting dead code. This simple DCE-like
4731 : pass removes any insertions we made that weren't actually used. */
4732 976707 : simple_dce_from_worklist (inserted_exprs);
4733 976707 : BITMAP_FREE (inserted_exprs);
4734 :
4735 : /* TODO: tail_merge_optimize may merge all predecessors of a block, in which
4736 : case we can merge the block with the remaining predecessor of the block.
4737 : It should either:
4738 : - call merge_blocks after each tail merge iteration
4739 : - call merge_blocks after all tail merge iterations
4740 : - mark TODO_cleanup_cfg when necessary. */
4741 976707 : todo |= tail_merge_optimize (need_crit_edge_split);
4742 :
4743 976707 : free_rpo_vn ();
4744 :
4745 : /* Tail merging invalidates the virtual SSA web, together with
4746 : cfg-cleanup opportunities exposed by PRE this will wreck the
4747 : SSA updating machinery. So make sure to run update-ssa
4748 : manually, before eventually scheduling cfg-cleanup as part of
4749 : the todo. */
4750 976707 : update_ssa (TODO_update_ssa_only_virtuals);
4751 :
4752 976707 : return todo;
4753 : }
4754 :
4755 : } // anon namespace
4756 :
4757 : gimple_opt_pass *
4758 292371 : make_pass_pre (gcc::context *ctxt)
4759 : {
4760 292371 : return new pass_pre (ctxt);
4761 : }
|
