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