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