Branch data Line data Source code
1 : : /* Code sinking for trees
2 : : Copyright (C) 2001-2025 Free Software Foundation, Inc.
3 : : Contributed by Daniel Berlin <dan@dberlin.org>
4 : :
5 : : This file is part of GCC.
6 : :
7 : : GCC is free software; you can redistribute it and/or modify
8 : : it under the terms of the GNU General Public License as published by
9 : : the Free Software Foundation; either version 3, or (at your option)
10 : : any later version.
11 : :
12 : : GCC is distributed in the hope that it will be useful,
13 : : but WITHOUT ANY WARRANTY; without even the implied warranty of
14 : : MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 : : GNU General Public License for more details.
16 : :
17 : : You should have received a copy of the GNU General Public License
18 : : along with GCC; see the file COPYING3. If not see
19 : : <http://www.gnu.org/licenses/>. */
20 : :
21 : : #include "config.h"
22 : : #include "system.h"
23 : : #include "coretypes.h"
24 : : #include "backend.h"
25 : : #include "tree.h"
26 : : #include "gimple.h"
27 : : #include "cfghooks.h"
28 : : #include "tree-pass.h"
29 : : #include "ssa.h"
30 : : #include "gimple-pretty-print.h"
31 : : #include "fold-const.h"
32 : : #include "stor-layout.h"
33 : : #include "cfganal.h"
34 : : #include "gimple-iterator.h"
35 : : #include "tree-cfg.h"
36 : : #include "cfgloop.h"
37 : : #include "tree-eh.h"
38 : : #include "tree-ssa-live.h"
39 : : #include "tree-dfa.h"
40 : :
41 : : /* TODO:
42 : : 1. Sinking store only using scalar promotion (IE without moving the RHS):
43 : :
44 : : *q = p;
45 : : p = p + 1;
46 : : if (something)
47 : : *q = <not p>;
48 : : else
49 : : y = *q;
50 : :
51 : :
52 : : should become
53 : : sinktemp = p;
54 : : p = p + 1;
55 : : if (something)
56 : : *q = <not p>;
57 : : else
58 : : {
59 : : *q = sinktemp;
60 : : y = *q
61 : : }
62 : : Store copy propagation will take care of the store elimination above.
63 : :
64 : :
65 : : 2. Sinking using Partial Dead Code Elimination. */
66 : :
67 : :
68 : : static struct
69 : : {
70 : : /* The number of statements sunk down the flowgraph by code sinking. */
71 : : int sunk;
72 : :
73 : : /* The number of stores commoned and sunk down by store commoning. */
74 : : int commoned;
75 : : } sink_stats;
76 : :
77 : :
78 : : /* Given a PHI, and one of its arguments (DEF), find the edge for
79 : : that argument and return it. If the argument occurs twice in the PHI node,
80 : : we return NULL. */
81 : :
82 : : static basic_block
83 : 667728 : find_bb_for_arg (gphi *phi, tree def)
84 : : {
85 : 667728 : size_t i;
86 : 667728 : bool foundone = false;
87 : 667728 : basic_block result = NULL;
88 : 2110417 : for (i = 0; i < gimple_phi_num_args (phi); i++)
89 : 1458593 : if (PHI_ARG_DEF (phi, i) == def)
90 : : {
91 : 683632 : if (foundone)
92 : : return NULL;
93 : 667728 : foundone = true;
94 : 667728 : result = gimple_phi_arg_edge (phi, i)->src;
95 : : }
96 : : return result;
97 : : }
98 : :
99 : : /* When the first immediate use is in a statement, then return true if all
100 : : immediate uses in IMM are in the same statement.
101 : : We could also do the case where the first immediate use is in a phi node,
102 : : and all the other uses are in phis in the same basic block, but this
103 : : requires some expensive checking later (you have to make sure no def/vdef
104 : : in the statement occurs for multiple edges in the various phi nodes it's
105 : : used in, so that you only have one place you can sink it to. */
106 : :
107 : : static bool
108 : 12951291 : all_immediate_uses_same_place (def_operand_p def_p)
109 : : {
110 : 12951291 : tree var = DEF_FROM_PTR (def_p);
111 : 12951291 : imm_use_iterator imm_iter;
112 : 12951291 : use_operand_p use_p;
113 : :
114 : 12951291 : gimple *firstuse = NULL;
115 : 27694761 : FOR_EACH_IMM_USE_FAST (use_p, imm_iter, var)
116 : : {
117 : 18476079 : if (is_gimple_debug (USE_STMT (use_p)))
118 : 1697155 : continue;
119 : 16778924 : if (firstuse == NULL)
120 : : firstuse = USE_STMT (use_p);
121 : : else
122 : 3827633 : if (firstuse != USE_STMT (use_p))
123 : : return false;
124 : : }
125 : :
126 : : return true;
127 : : }
128 : :
129 : : /* Find the nearest common dominator of all of the immediate uses in IMM. */
130 : :
131 : : static basic_block
132 : 12431663 : nearest_common_dominator_of_uses (def_operand_p def_p, bool *debug_stmts)
133 : : {
134 : 12431663 : tree var = DEF_FROM_PTR (def_p);
135 : 12431663 : auto_bitmap blocks;
136 : 12431663 : basic_block commondom;
137 : 12431663 : unsigned int j;
138 : 12431663 : bitmap_iterator bi;
139 : 12431663 : imm_use_iterator imm_iter;
140 : 12431663 : use_operand_p use_p;
141 : :
142 : 43450286 : FOR_EACH_IMM_USE_FAST (use_p, imm_iter, var)
143 : : {
144 : 31018623 : gimple *usestmt = USE_STMT (use_p);
145 : 31018623 : basic_block useblock;
146 : :
147 : 31018623 : if (gphi *phi = dyn_cast <gphi *> (usestmt))
148 : : {
149 : 3701411 : int idx = PHI_ARG_INDEX_FROM_USE (use_p);
150 : :
151 : 3701411 : useblock = gimple_phi_arg_edge (phi, idx)->src;
152 : : }
153 : 27317212 : else if (is_gimple_debug (usestmt))
154 : : {
155 : 6469947 : *debug_stmts = true;
156 : 6469947 : continue;
157 : : }
158 : : else
159 : : {
160 : 20847265 : useblock = gimple_bb (usestmt);
161 : : }
162 : :
163 : : /* Short circuit. Nothing dominates the entry block. */
164 : 24548676 : if (useblock == ENTRY_BLOCK_PTR_FOR_FN (cfun))
165 : : return NULL;
166 : :
167 : 24548676 : bitmap_set_bit (blocks, useblock->index);
168 : : }
169 : 12431663 : commondom = BASIC_BLOCK_FOR_FN (cfun, bitmap_first_set_bit (blocks));
170 : 34021809 : EXECUTE_IF_SET_IN_BITMAP (blocks, 0, j, bi)
171 : 21590146 : commondom = nearest_common_dominator (CDI_DOMINATORS, commondom,
172 : 21590146 : BASIC_BLOCK_FOR_FN (cfun, j));
173 : : return commondom;
174 : 12431663 : }
175 : :
176 : : /* Return whether sinking STMT from EARLY_BB to BEST_BB should be avoided. */
177 : :
178 : : static bool
179 : 4300575 : do_not_sink (gimple *stmt, basic_block early_bb, basic_block best_bb)
180 : : {
181 : : /* Placing a statement before a setjmp-like function would be invalid
182 : : (it cannot be reevaluated when execution follows an abnormal edge).
183 : : If we selected a block with abnormal predecessors, just punt. */
184 : 4300575 : if (bb_has_abnormal_pred (best_bb))
185 : : return true;
186 : :
187 : : /* If the latch block is empty, don't make it non-empty by sinking
188 : : something into it. */
189 : 4300489 : if (best_bb == early_bb->loop_father->latch
190 : 4300489 : && empty_block_p (best_bb))
191 : : return true;
192 : :
193 : : /* Avoid turning an unconditional read into a conditional one when we
194 : : still might want to perform vectorization. */
195 : 4032839 : if (best_bb->loop_father == early_bb->loop_father
196 : 2863510 : && loop_outer (best_bb->loop_father)
197 : 739963 : && !best_bb->loop_father->inner
198 : 433816 : && gimple_vuse (stmt)
199 : 168704 : && !gimple_vdef (stmt)
200 : 141917 : && flag_tree_loop_vectorize
201 : 136194 : && !(cfun->curr_properties & PROP_loop_opts_done)
202 : 93461 : && dominated_by_p (CDI_DOMINATORS, best_bb->loop_father->latch, early_bb)
203 : 4101868 : && !dominated_by_p (CDI_DOMINATORS, best_bb->loop_father->latch, best_bb))
204 : : return true;
205 : :
206 : : return false;
207 : : }
208 : :
209 : : /* Given EARLY_BB and LATE_BB, two blocks in a path through the dominator
210 : : tree, return the best basic block between them (inclusive) to place
211 : : statements.
212 : :
213 : : We want the most control dependent block in the shallowest loop nest.
214 : :
215 : : If the resulting block is in a shallower loop nest, then use it. */
216 : :
217 : : static basic_block
218 : 16201391 : select_best_block (basic_block early_bb,
219 : : basic_block late_bb,
220 : : gimple *stmt)
221 : : {
222 : : /* First pick a block we do not disqualify. */
223 : 16201391 : while (late_bb != early_bb
224 : 16490036 : && do_not_sink (stmt, early_bb, late_bb))
225 : 288645 : late_bb = get_immediate_dominator (CDI_DOMINATORS, late_bb);
226 : :
227 : 16201391 : basic_block best_bb = late_bb;
228 : 16201391 : basic_block temp_bb = late_bb;
229 : 19360798 : while (temp_bb != early_bb)
230 : : {
231 : : /* Walk up the dominator tree, hopefully we'll find a shallower
232 : : loop nest. */
233 : 3159407 : temp_bb = get_immediate_dominator (CDI_DOMINATORS, temp_bb);
234 : :
235 : : /* Do not consider blocks we do not want to sink to. */
236 : 3159407 : if (temp_bb != early_bb && do_not_sink (stmt, early_bb, temp_bb))
237 : : ;
238 : :
239 : : /* If we've moved into a lower loop nest, then that becomes
240 : : our best block. */
241 : 3159162 : else if (bb_loop_depth (temp_bb) < bb_loop_depth (best_bb))
242 : : best_bb = temp_bb;
243 : :
244 : : /* A higher loop nest is always worse. */
245 : 2614981 : else if (bb_loop_depth (temp_bb) > bb_loop_depth (best_bb))
246 : : ;
247 : :
248 : : /* But sink the least distance, if the new candidate on the same
249 : : loop depth is post-dominated by the current best block pick
250 : : the new candidate. */
251 : 2357189 : else if (dominated_by_p (CDI_POST_DOMINATORS, temp_bb, best_bb))
252 : : best_bb = temp_bb;
253 : :
254 : : /* Avoid sinking across a conditional branching to exceptional
255 : : code. In practice this does not reduce the number of dynamic
256 : : executions of the sunk statement (this includes EH and
257 : : branches leading to abort for example). Treat this case as
258 : : post-dominating. */
259 : 3492974 : else if (single_pred_p (best_bb)
260 : 1519079 : && single_pred_edge (best_bb)->src == temp_bb
261 : 2740980 : && (single_pred_edge (best_bb)->flags & EDGE_FALLTHRU
262 : 979113 : || (single_pred_edge (best_bb)->probability
263 : 2761159 : >= profile_probability::always ())))
264 : 1377193 : best_bb = temp_bb;
265 : : }
266 : :
267 : 16201391 : gcc_checking_assert (best_bb == early_bb
268 : : || (!do_not_sink (stmt, early_bb, best_bb)
269 : : && ((bb_loop_depth (best_bb)
270 : : < bb_loop_depth (early_bb))
271 : : || !dominated_by_p (CDI_POST_DOMINATORS,
272 : : early_bb, best_bb))));
273 : :
274 : 16201391 : return best_bb;
275 : : }
276 : :
277 : : /* Given a statement (STMT) and the basic block it is currently in (FROMBB),
278 : : determine the location to sink the statement to, if any.
279 : : Returns true if there is such location; in that case, TOGSI points to the
280 : : statement before that STMT should be moved. */
281 : :
282 : : static bool
283 : 116087638 : statement_sink_location (gimple *stmt, basic_block frombb,
284 : : gimple_stmt_iterator *togsi, bool *zero_uses_p,
285 : : virtual_operand_live &vop_live)
286 : : {
287 : 116087638 : gimple *use;
288 : 116087638 : use_operand_p one_use = NULL_USE_OPERAND_P;
289 : 116087638 : basic_block sinkbb;
290 : 116087638 : use_operand_p use_p;
291 : 116087638 : def_operand_p def_p;
292 : 116087638 : ssa_op_iter iter;
293 : 116087638 : imm_use_iterator imm_iter;
294 : :
295 : 116087638 : *zero_uses_p = false;
296 : :
297 : : /* We only can sink assignments and const/pure calls that are guaranteed
298 : : to return exactly once. */
299 : 116087638 : int cf;
300 : 116087638 : if (!is_gimple_assign (stmt)
301 : 116087638 : && (!is_gimple_call (stmt)
302 : 5315478 : || !((cf = gimple_call_flags (stmt)) & (ECF_CONST|ECF_PURE))
303 : 1040328 : || (cf & (ECF_LOOPING_CONST_OR_PURE|ECF_RETURNS_TWICE))))
304 : 83592080 : return false;
305 : :
306 : : /* We only can sink stmts with a single definition. */
307 : 32495558 : def_p = single_ssa_def_operand (stmt, SSA_OP_ALL_DEFS);
308 : 32495558 : if (def_p == NULL_DEF_OPERAND_P)
309 : : return false;
310 : :
311 : : /* There are a few classes of things we can't or don't move, some because we
312 : : don't have code to handle it, some because it's not profitable and some
313 : : because it's not legal.
314 : :
315 : : We can't sink things that may be global stores, at least not without
316 : : calculating a lot more information, because we may cause it to no longer
317 : : be seen by an external routine that needs it depending on where it gets
318 : : moved to.
319 : :
320 : : We can't sink statements that end basic blocks without splitting the
321 : : incoming edge for the sink location to place it there.
322 : :
323 : : We can't sink statements that have volatile operands.
324 : :
325 : : We don't want to sink dead code, so anything with 0 immediate uses is not
326 : : sunk.
327 : :
328 : : Don't sink BLKmode assignments if current function has any local explicit
329 : : register variables, as BLKmode assignments may involve memcpy or memset
330 : : calls or, on some targets, inline expansion thereof that sometimes need
331 : : to use specific hard registers.
332 : :
333 : : */
334 : 32495499 : if (stmt_ends_bb_p (stmt)
335 : 32261674 : || gimple_has_side_effects (stmt)
336 : 62339163 : || (cfun->has_local_explicit_reg_vars
337 : 1626 : && TYPE_MODE (TREE_TYPE (gimple_get_lhs (stmt))) == BLKmode))
338 : 2651836 : return false;
339 : :
340 : : /* Return if there are no immediate uses of this stmt. */
341 : 29843663 : if (has_zero_uses (DEF_FROM_PTR (def_p)))
342 : : {
343 : 105570 : *zero_uses_p = true;
344 : 105570 : return false;
345 : : }
346 : :
347 : 29738093 : if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (DEF_FROM_PTR (def_p)))
348 : : return false;
349 : :
350 : 73090010 : FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
351 : : {
352 : 43353968 : tree use = USE_FROM_PTR (use_p);
353 : 43353968 : if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (use))
354 : : return false;
355 : : }
356 : :
357 : 29736042 : use = NULL;
358 : :
359 : : /* If stmt is a store the one and only use needs to be a VUSE on
360 : : the live path. */
361 : 29736042 : if (virtual_operand_p (DEF_FROM_PTR (def_p)))
362 : : {
363 : 8085697 : tree lhs = gimple_get_lhs (stmt);
364 : 8085697 : ao_ref ref;
365 : 8085697 : ao_ref_init (&ref, lhs);
366 : 17173516 : FOR_EACH_IMM_USE_FAST (use_p, imm_iter, DEF_FROM_PTR (def_p))
367 : : {
368 : 10795459 : gimple *use_stmt = USE_STMT (use_p);
369 : :
370 : : /* A killing definition is not a use. */
371 : 10795459 : if (gimple_vdef (use_stmt)
372 : 11303408 : && ((gimple_has_lhs (use_stmt)
373 : 6715961 : && operand_equal_p (lhs,
374 : 6715961 : gimple_get_lhs (use_stmt), 0))
375 : 7806249 : || stmt_kills_ref_p (use_stmt, &ref)))
376 : : {
377 : : /* If use_stmt is or might be a nop assignment then USE_STMT
378 : : acts as a use as well as definition. */
379 : 52881 : if (stmt != use_stmt
380 : 52881 : && ref_maybe_used_by_stmt_p (use_stmt, &ref))
381 : : {
382 : 961 : if (use && use != use_stmt)
383 : 1720460 : return false;
384 : : use = use_stmt;
385 : : }
386 : 52868 : continue;
387 : : }
388 : :
389 : 10742578 : if (is_a <gphi *> (use_stmt)
390 : 10742578 : || ref_maybe_used_by_stmt_p (use_stmt, &ref))
391 : : {
392 : 3456471 : if (use && use != use_stmt)
393 : : return false;
394 : 2403579 : use = use_stmt;
395 : 2403579 : continue;
396 : : }
397 : :
398 : 22365308 : if (gimple_vdef (use_stmt))
399 : : {
400 : 5991382 : if (stmt_may_clobber_ref_p_1 (use_stmt, &ref, false))
401 : : return false;
402 : : /* We do not look past VDEFs, so treat them as sink location. */
403 : 5561363 : if (use && use != use_stmt)
404 : : return false;
405 : : use = use_stmt;
406 : : }
407 : : }
408 : 6378057 : if (!use)
409 : : return false;
410 : : }
411 : : /* If all the immediate uses are not in the same place, find the nearest
412 : : common dominator of all the immediate uses. For PHI nodes, we have to
413 : : find the nearest common dominator of all of the predecessor blocks, since
414 : : that is where insertion would have to take place. */
415 : 21650345 : else if (gimple_vuse (stmt)
416 : 21650345 : || !all_immediate_uses_same_place (def_p))
417 : : {
418 : 12431663 : bool debug_stmts = false;
419 : 12431663 : basic_block commondom = nearest_common_dominator_of_uses (def_p,
420 : : &debug_stmts);
421 : :
422 : 12431663 : if (commondom == frombb)
423 : : return false;
424 : :
425 : : /* If this is a load then do not sink past any stores. */
426 : 2096472 : if (gimple_vuse (stmt))
427 : : {
428 : : /* Do not sink loads from hard registers. */
429 : 815347 : if (gimple_assign_single_p (stmt)
430 : 812239 : && VAR_P (gimple_assign_rhs1 (stmt))
431 : 837846 : && DECL_HARD_REGISTER (gimple_assign_rhs1 (stmt)))
432 : : return false;
433 : :
434 : : /* When the live virtual operand at the intended sink location is
435 : : not the same as the one from the load walk up the dominator tree
436 : : for a new candidate location. */
437 : : while (commondom != frombb
438 : 3632994 : && vop_live.get_live_in (commondom) != gimple_vuse (stmt))
439 : 1208583 : commondom = get_immediate_dominator (CDI_DOMINATORS, commondom);
440 : 815341 : if (commondom == frombb)
441 : : return false;
442 : : }
443 : :
444 : : /* Our common dominator has to be dominated by frombb in order to be a
445 : : trivially safe place to put this statement, since it has multiple
446 : : uses. */
447 : 633376 : if (!dominated_by_p (CDI_DOMINATORS, commondom, frombb))
448 : : return false;
449 : :
450 : 633376 : commondom = select_best_block (frombb, commondom, stmt);
451 : :
452 : 633376 : if (commondom == frombb)
453 : : return false;
454 : :
455 : 381980 : *togsi = gsi_after_labels (commondom);
456 : :
457 : 381980 : return true;
458 : : }
459 : : else
460 : : {
461 : 9531295 : FOR_EACH_IMM_USE_FAST (one_use, imm_iter, DEF_FROM_PTR (def_p))
462 : : {
463 : 9531295 : if (is_gimple_debug (USE_STMT (one_use)))
464 : 312613 : continue;
465 : : break;
466 : : }
467 : 9218682 : use = USE_STMT (one_use);
468 : : }
469 : :
470 : 15583919 : if (gimple_code (use) != GIMPLE_PHI)
471 : : {
472 : 14916191 : sinkbb = select_best_block (frombb, gimple_bb (use), stmt);
473 : :
474 : 14916191 : if (sinkbb == frombb)
475 : : return false;
476 : :
477 : : /* The SSA update for sinking of stores cannot insert PHIs, the
478 : : sink location has to lead to exit without crossing any CFG
479 : : merge points to paths not dominated by the sink location. */
480 : 356121 : if (gimple_vdef (stmt)
481 : 103558548 : && (!single_succ_p (sinkbb)
482 : 5870 : || single_succ (sinkbb)->index != EXIT_BLOCK))
483 : : return false;
484 : :
485 : 349188 : *togsi = gsi_after_labels (sinkbb);
486 : :
487 : 349188 : return true;
488 : : }
489 : :
490 : 667728 : sinkbb = find_bb_for_arg (as_a <gphi *> (use), DEF_FROM_PTR (def_p));
491 : :
492 : : /* This can happen if there are multiple uses in a PHI. */
493 : 667728 : if (!sinkbb)
494 : : return false;
495 : :
496 : 651824 : basic_block bestbb = select_best_block (frombb, sinkbb, stmt);
497 : 651824 : if (bestbb == frombb
498 : : /* When we sink a store make sure there's not a path to any of
499 : : the possibly skipped killing defs as that wrecks the virtual
500 : : operand update, requiring inserting of a PHI node. */
501 : 766246 : || (gimple_vdef (stmt)
502 : 8934 : && bestbb != sinkbb
503 : 4193 : && !dominated_by_p (CDI_POST_DOMINATORS, bestbb, sinkbb)))
504 : 541594 : return false;
505 : :
506 : 110230 : *togsi = gsi_after_labels (bestbb);
507 : :
508 : 110230 : return true;
509 : : }
510 : :
511 : : /* Very simplistic code to sink common stores from the predecessor through
512 : : our virtual PHI. We do this before sinking stmts from BB as it might
513 : : expose sinking opportunities of the merged stores.
514 : : Once we have partial dead code elimination through sth like SSU-PRE this
515 : : should be moved there. */
516 : :
517 : : static unsigned
518 : 32652442 : sink_common_stores_to_bb (basic_block bb)
519 : : {
520 : 32652442 : unsigned todo = 0;
521 : 32652442 : gphi *phi;
522 : :
523 : 32652442 : if (EDGE_COUNT (bb->preds) > 1
524 : 30585622 : && (phi = get_virtual_phi (bb)))
525 : : {
526 : : /* Repeat until no more common stores are found. */
527 : 4012991 : while (1)
528 : : {
529 : 3938961 : gimple *first_store = NULL;
530 : 3938961 : auto_vec <tree, 5> vdefs;
531 : 3938961 : gimple_stmt_iterator gsi;
532 : :
533 : : /* Search for common stores defined by all virtual PHI args.
534 : : ??? Common stores not present in all predecessors could
535 : : be handled by inserting a forwarder to sink to. Generally
536 : : this involves deciding which stores to do this for if
537 : : multiple common stores are present for different sets of
538 : : predecessors. See PR11832 for an interesting case. */
539 : 4796052 : for (unsigned i = 0; i < gimple_phi_num_args (phi); ++i)
540 : : {
541 : 4718375 : tree arg = gimple_phi_arg_def (phi, i);
542 : 4718375 : gimple *def = SSA_NAME_DEF_STMT (arg);
543 : 4718375 : if (! is_gimple_assign (def)
544 : 2001884 : || stmt_can_throw_internal (cfun, def)
545 : 1973134 : || (gimple_phi_arg_edge (phi, i)->flags & EDGE_ABNORMAL)
546 : 6691507 : || stmt_references_abnormal_ssa_name (def))
547 : : {
548 : : /* ??? We could handle some cascading with the def being
549 : : another PHI. We'd have to insert multiple PHIs for
550 : : the rhs then though (if they are not all equal). */
551 : : first_store = NULL;
552 : 3861284 : break;
553 : : }
554 : : /* ??? Do not try to do anything fancy with aliasing, thus
555 : : do not sink across non-aliased loads (or even stores,
556 : : so different store order will make the sinking fail). */
557 : 1973117 : bool all_uses_on_phi = true;
558 : 1973117 : imm_use_iterator iter;
559 : 1973117 : use_operand_p use_p;
560 : 3473625 : FOR_EACH_IMM_USE_FAST (use_p, iter, arg)
561 : 2525361 : if (USE_STMT (use_p) != phi)
562 : : {
563 : : all_uses_on_phi = false;
564 : : break;
565 : : }
566 : 1973117 : if (! all_uses_on_phi)
567 : : {
568 : : first_store = NULL;
569 : : break;
570 : : }
571 : : /* Check all stores are to the same LHS. */
572 : 948264 : if (! first_store)
573 : : first_store = def;
574 : : /* ??? We could handle differing SSA uses in the LHS by inserting
575 : : PHIs for them. */
576 : 259004 : else if (! operand_equal_p (gimple_assign_lhs (first_store),
577 : 259004 : gimple_assign_lhs (def), 0)
578 : 426835 : || (gimple_clobber_p (first_store)
579 : 167831 : != gimple_clobber_p (def)))
580 : : {
581 : : first_store = NULL;
582 : : break;
583 : : }
584 : 857091 : vdefs.safe_push (arg);
585 : : }
586 : 3938961 : if (! first_store)
587 : : break;
588 : :
589 : : /* Check if we need a PHI node to merge the stored values. */
590 : 77677 : bool allsame = true;
591 : 77677 : if (!gimple_clobber_p (first_store))
592 : 96843 : for (unsigned i = 1; i < vdefs.length (); ++i)
593 : : {
594 : 88950 : gimple *def = SSA_NAME_DEF_STMT (vdefs[i]);
595 : 88950 : if (! operand_equal_p (gimple_assign_rhs1 (first_store),
596 : 88950 : gimple_assign_rhs1 (def), 0))
597 : : {
598 : : allsame = false;
599 : : break;
600 : : }
601 : : }
602 : :
603 : : /* We cannot handle aggregate values if we need to merge them. */
604 : 77677 : tree type = TREE_TYPE (gimple_assign_lhs (first_store));
605 : 77677 : if (! allsame
606 : 77677 : && ! is_gimple_reg_type (type))
607 : : break;
608 : :
609 : 74030 : if (dump_enabled_p ())
610 : : {
611 : 10 : dump_printf_loc (MSG_OPTIMIZED_LOCATIONS,
612 : 5 : first_store,
613 : : "sinking common stores %sto ",
614 : : allsame ? "with same value " : "");
615 : 5 : dump_generic_expr (MSG_OPTIMIZED_LOCATIONS, TDF_SLIM,
616 : : gimple_assign_lhs (first_store));
617 : 5 : dump_printf (MSG_OPTIMIZED_LOCATIONS, "\n");
618 : : }
619 : :
620 : : /* Insert a PHI to merge differing stored values if necessary.
621 : : Note that in general inserting PHIs isn't a very good idea as
622 : : it makes the job of coalescing and register allocation harder.
623 : : Even common SSA uses on the rhs/lhs might extend their lifetime
624 : : across multiple edges by this code motion which makes
625 : : register allocation harder. */
626 : 74030 : tree from;
627 : 74030 : if (! allsame)
628 : : {
629 : 57264 : from = make_ssa_name (type);
630 : 57264 : gphi *newphi = create_phi_node (from, bb);
631 : 228577 : for (unsigned i = 0; i < vdefs.length (); ++i)
632 : : {
633 : 171313 : gimple *def = SSA_NAME_DEF_STMT (vdefs[i]);
634 : 171313 : add_phi_arg (newphi, gimple_assign_rhs1 (def),
635 : 171313 : EDGE_PRED (bb, i), UNKNOWN_LOCATION);
636 : : }
637 : : }
638 : : else
639 : 16766 : from = gimple_assign_rhs1 (first_store);
640 : :
641 : : /* Remove all stores. */
642 : 578344 : for (unsigned i = 0; i < vdefs.length (); ++i)
643 : 215142 : TREE_VISITED (vdefs[i]) = 1;
644 : 289172 : for (unsigned i = 0; i < vdefs.length (); ++i)
645 : : /* If we have more than one use of a VDEF on the PHI make sure
646 : : we remove the defining stmt only once. */
647 : 215142 : if (TREE_VISITED (vdefs[i]))
648 : : {
649 : 211931 : TREE_VISITED (vdefs[i]) = 0;
650 : 211931 : gimple *def = SSA_NAME_DEF_STMT (vdefs[i]);
651 : 211931 : gsi = gsi_for_stmt (def);
652 : 211931 : unlink_stmt_vdef (def);
653 : 211931 : gsi_remove (&gsi, true);
654 : 211931 : release_defs (def);
655 : : }
656 : :
657 : : /* Insert the first store at the beginning of the merge BB. */
658 : 74030 : gimple_set_vdef (first_store, gimple_phi_result (phi));
659 : 148060 : SSA_NAME_DEF_STMT (gimple_vdef (first_store)) = first_store;
660 : 74030 : gimple_phi_set_result (phi, make_ssa_name (gimple_vop (cfun)));
661 : 74030 : gimple_set_vuse (first_store, gimple_phi_result (phi));
662 : 74030 : gimple_assign_set_rhs1 (first_store, from);
663 : : /* ??? Should we reset first_stores location? */
664 : 74030 : gsi = gsi_after_labels (bb);
665 : 74030 : gsi_insert_before (&gsi, first_store, GSI_SAME_STMT);
666 : 74030 : sink_stats.commoned++;
667 : :
668 : 74030 : todo |= TODO_cleanup_cfg;
669 : 3938961 : }
670 : :
671 : : /* We could now have empty predecessors that we could remove,
672 : : forming a proper CFG for further sinking. Note that even
673 : : CFG cleanup doesn't do this fully at the moment and it
674 : : doesn't preserve post-dominators in the process either.
675 : : The mergephi pass might do it though. gcc.dg/tree-ssa/ssa-sink-13.c
676 : : shows this nicely if you disable tail merging or (same effect)
677 : : make the stored values unequal. */
678 : : }
679 : :
680 : 32652442 : return todo;
681 : : }
682 : :
683 : : /* Perform code sinking on BB */
684 : :
685 : : static unsigned
686 : 32652442 : sink_code_in_bb (basic_block bb, virtual_operand_live &vop_live)
687 : : {
688 : 32652442 : gimple_stmt_iterator gsi;
689 : 32652442 : edge_iterator ei;
690 : 32652442 : edge e;
691 : 32652442 : bool last = true;
692 : 32652442 : unsigned todo = 0;
693 : :
694 : : /* Sink common stores from the predecessor through our virtual PHI. */
695 : 32652442 : todo |= sink_common_stores_to_bb (bb);
696 : :
697 : : /* If this block doesn't dominate anything, there can't be any place to sink
698 : : the statements to. */
699 : 32652442 : if (first_dom_son (CDI_DOMINATORS, bb) == NULL)
700 : : return todo;
701 : :
702 : : /* We can't move things across abnormal edges, so don't try. */
703 : 38385357 : FOR_EACH_EDGE (e, ei, bb->succs)
704 : 24357932 : if (e->flags & EDGE_ABNORMAL)
705 : : return todo;
706 : :
707 : 144142488 : for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi);)
708 : : {
709 : 116087638 : gimple *stmt = gsi_stmt (gsi);
710 : 116087638 : gimple_stmt_iterator togsi;
711 : 116087638 : bool zero_uses_p;
712 : :
713 : 116087638 : if (!statement_sink_location (stmt, bb, &togsi, &zero_uses_p, vop_live))
714 : : {
715 : 115246240 : gimple_stmt_iterator saved = gsi;
716 : 115246240 : if (!gsi_end_p (gsi))
717 : 115246240 : gsi_prev (&gsi);
718 : : /* If we face a dead stmt remove it as it possibly blocks
719 : : sinking of uses. */
720 : 115246240 : if (zero_uses_p
721 : 105570 : && !gimple_vdef (stmt)
722 : 115348020 : && (cfun->can_delete_dead_exceptions
723 : 80323 : || !stmt_could_throw_p (cfun, stmt)))
724 : : {
725 : 49555 : gsi_remove (&saved, true);
726 : 49555 : release_defs (stmt);
727 : : }
728 : : else
729 : : last = false;
730 : 115246240 : continue;
731 : 115246240 : }
732 : 841398 : if (dump_file)
733 : : {
734 : 37 : fprintf (dump_file, "Sinking ");
735 : 37 : print_gimple_stmt (dump_file, stmt, 0, TDF_VOPS);
736 : 37 : fprintf (dump_file, " from bb %d to bb %d\n",
737 : 37 : bb->index, (gsi_bb (togsi))->index);
738 : : }
739 : :
740 : : /* Update virtual operands of statements in the path we
741 : : do not sink to. */
742 : 1682796 : if (gimple_vdef (stmt))
743 : : {
744 : 5642 : imm_use_iterator iter;
745 : 5642 : use_operand_p use_p;
746 : 5642 : gimple *vuse_stmt;
747 : :
748 : 23930 : FOR_EACH_IMM_USE_STMT (vuse_stmt, iter, gimple_vdef (stmt))
749 : 18288 : if (gimple_code (vuse_stmt) != GIMPLE_PHI
750 : 18288 : && !dominated_by_p (CDI_DOMINATORS, gimple_bb (vuse_stmt),
751 : 13546 : gsi_bb (togsi)))
752 : 36918 : FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
753 : 30254 : SET_USE (use_p, gimple_vuse (stmt));
754 : : }
755 : :
756 : : /* If this is the end of the basic block, we need to insert at the end
757 : : of the basic block. */
758 : 841398 : if (gsi_end_p (togsi))
759 : 131237 : gsi_move_to_bb_end (&gsi, gsi_bb (togsi));
760 : : else
761 : 710161 : gsi_move_before (&gsi, &togsi);
762 : :
763 : 841398 : sink_stats.sunk++;
764 : :
765 : : /* If we've just removed the last statement of the BB, the
766 : : gsi_end_p() test below would fail, but gsi_prev() would have
767 : : succeeded, and we want it to succeed. So we keep track of
768 : : whether we're at the last statement and pick up the new last
769 : : statement. */
770 : 841398 : if (last)
771 : : {
772 : 1012 : gsi = gsi_last_bb (bb);
773 : 1012 : continue;
774 : : }
775 : :
776 : 840386 : last = false;
777 : 840386 : if (!gsi_end_p (gsi))
778 : 1680772 : gsi_prev (&gsi);
779 : :
780 : : }
781 : :
782 : : return todo;
783 : : }
784 : :
785 : : /* Perform code sinking.
786 : : This moves code down the flowgraph when we know it would be
787 : : profitable to do so, or it wouldn't increase the number of
788 : : executions of the statement.
789 : :
790 : : IE given
791 : :
792 : : a_1 = b + c;
793 : : if (<something>)
794 : : {
795 : : }
796 : : else
797 : : {
798 : : foo (&b, &c);
799 : : a_5 = b + c;
800 : : }
801 : : a_6 = PHI (a_5, a_1);
802 : : USE a_6.
803 : :
804 : : we'll transform this into:
805 : :
806 : : if (<something>)
807 : : {
808 : : a_1 = b + c;
809 : : }
810 : : else
811 : : {
812 : : foo (&b, &c);
813 : : a_5 = b + c;
814 : : }
815 : : a_6 = PHI (a_5, a_1);
816 : : USE a_6.
817 : :
818 : : Note that this reduces the number of computations of a = b + c to 1
819 : : when we take the else edge, instead of 2.
820 : : */
821 : : namespace {
822 : :
823 : : const pass_data pass_data_sink_code =
824 : : {
825 : : GIMPLE_PASS, /* type */
826 : : "sink", /* name */
827 : : OPTGROUP_NONE, /* optinfo_flags */
828 : : TV_TREE_SINK, /* tv_id */
829 : : /* PROP_no_crit_edges is ensured by running split_edges_for_insertion in
830 : : pass_data_sink_code::execute (). */
831 : : ( PROP_cfg | PROP_ssa ), /* properties_required */
832 : : 0, /* properties_provided */
833 : : 0, /* properties_destroyed */
834 : : 0, /* todo_flags_start */
835 : : TODO_update_ssa, /* todo_flags_finish */
836 : : };
837 : :
838 : : class pass_sink_code : public gimple_opt_pass
839 : : {
840 : : public:
841 : 562828 : pass_sink_code (gcc::context *ctxt)
842 : 1125656 : : gimple_opt_pass (pass_data_sink_code, ctxt), unsplit_edges (false)
843 : : {}
844 : :
845 : : /* opt_pass methods: */
846 : 2066974 : bool gate (function *) final override { return flag_tree_sink != 0; }
847 : : unsigned int execute (function *) final override;
848 : 281414 : opt_pass *clone (void) final override { return new pass_sink_code (m_ctxt); }
849 : 562828 : void set_pass_param (unsigned n, bool param) final override
850 : : {
851 : 562828 : gcc_assert (n == 0);
852 : 562828 : unsplit_edges = param;
853 : 562828 : }
854 : :
855 : : private:
856 : : bool unsplit_edges;
857 : : }; // class pass_sink_code
858 : :
859 : : unsigned int
860 : 2066820 : pass_sink_code::execute (function *fun)
861 : : {
862 : 2066820 : loop_optimizer_init (LOOPS_NORMAL);
863 : 2066820 : split_edges_for_insertion ();
864 : : /* Arrange for the critical edge splitting to be undone if requested. */
865 : 2066820 : unsigned todo = unsplit_edges ? TODO_cleanup_cfg : 0;
866 : 2066820 : connect_infinite_loops_to_exit ();
867 : 2066820 : mark_dfs_back_edges (fun);
868 : 2066820 : memset (&sink_stats, 0, sizeof (sink_stats));
869 : 2066820 : calculate_dominance_info (CDI_DOMINATORS);
870 : 2066820 : calculate_dominance_info (CDI_POST_DOMINATORS);
871 : :
872 : 2066820 : virtual_operand_live vop_live;
873 : :
874 : 2066820 : int *rpo = XNEWVEC (int, n_basic_blocks_for_fn (cfun));
875 : 2066820 : int n = inverted_rev_post_order_compute (fun, rpo);
876 : 34719262 : for (int i = 0; i < n; ++i)
877 : 32652442 : todo |= sink_code_in_bb (BASIC_BLOCK_FOR_FN (fun, rpo[i]), vop_live);
878 : 2066820 : free (rpo);
879 : :
880 : 2066820 : statistics_counter_event (fun, "Sunk statements", sink_stats.sunk);
881 : 2066820 : statistics_counter_event (fun, "Commoned stores", sink_stats.commoned);
882 : 2066820 : free_dominance_info (CDI_POST_DOMINATORS);
883 : 2066820 : remove_fake_exit_edges ();
884 : 2066820 : loop_optimizer_finalize ();
885 : :
886 : 2066820 : return todo;
887 : 2066820 : }
888 : :
889 : : } // anon namespace
890 : :
891 : : gimple_opt_pass *
892 : 281414 : make_pass_sink_code (gcc::context *ctxt)
893 : : {
894 : 281414 : return new pass_sink_code (ctxt);
895 : : }
|