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