Line data Source code
1 : /* Code sinking for trees
2 : Copyright (C) 2001-2026 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 687980 : find_bb_for_arg (gphi *phi, tree def)
84 : {
85 687980 : size_t i;
86 687980 : bool foundone = false;
87 687980 : basic_block result = NULL;
88 2227962 : for (i = 0; i < gimple_phi_num_args (phi); i++)
89 1556940 : if (PHI_ARG_DEF (phi, i) == def)
90 : {
91 704938 : if (foundone)
92 : return NULL;
93 687980 : foundone = true;
94 687980 : 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 13413445 : all_immediate_uses_same_place (def_operand_p def_p)
109 : {
110 13413445 : tree var = DEF_FROM_PTR (def_p);
111 13413445 : imm_use_iterator imm_iter;
112 13413445 : use_operand_p use_p;
113 :
114 13413445 : gimple *firstuse = NULL;
115 42222136 : FOR_EACH_IMM_USE_FAST (use_p, imm_iter, var)
116 : {
117 19279822 : if (is_gimple_debug (USE_STMT (use_p)))
118 1874837 : continue;
119 17404985 : if (firstuse == NULL)
120 : firstuse = USE_STMT (use_p);
121 : else
122 3991540 : if (firstuse != USE_STMT (use_p))
123 3884576 : return false;
124 3884576 : }
125 :
126 9528869 : return true;
127 : }
128 :
129 : /* Find the nearest common dominator of all of the immediate uses in IMM. */
130 :
131 : static basic_block
132 12617052 : nearest_common_dominator_of_uses (def_operand_p def_p, bool *debug_stmts)
133 : {
134 12617052 : tree var = DEF_FROM_PTR (def_p);
135 12617052 : auto_bitmap blocks;
136 12617052 : basic_block commondom;
137 12617052 : unsigned int j;
138 12617052 : bitmap_iterator bi;
139 12617052 : imm_use_iterator imm_iter;
140 12617052 : use_operand_p use_p;
141 :
142 57564098 : FOR_EACH_IMM_USE_FAST (use_p, imm_iter, var)
143 : {
144 32329994 : gimple *usestmt = USE_STMT (use_p);
145 32329994 : basic_block useblock;
146 :
147 32329994 : if (gphi *phi = dyn_cast <gphi *> (usestmt))
148 : {
149 3744673 : int idx = PHI_ARG_INDEX_FROM_USE (use_p);
150 :
151 3744673 : useblock = gimple_phi_arg_edge (phi, idx)->src;
152 : }
153 28585321 : else if (is_gimple_debug (usestmt))
154 : {
155 6959397 : *debug_stmts = true;
156 6959397 : continue;
157 : }
158 : else
159 : {
160 21625924 : useblock = gimple_bb (usestmt);
161 : }
162 :
163 : /* Short circuit. Nothing dominates the entry block. */
164 25370597 : if (useblock == ENTRY_BLOCK_PTR_FOR_FN (cfun))
165 0 : return NULL;
166 :
167 25370597 : bitmap_set_bit (blocks, useblock->index);
168 0 : }
169 12617052 : commondom = BASIC_BLOCK_FOR_FN (cfun, bitmap_first_set_bit (blocks));
170 34897446 : EXECUTE_IF_SET_IN_BITMAP (blocks, 0, j, bi)
171 22280394 : commondom = nearest_common_dominator (CDI_DOMINATORS, commondom,
172 22280394 : BASIC_BLOCK_FOR_FN (cfun, j));
173 : return commondom;
174 12617052 : }
175 :
176 : /* Return whether sinking STMT from EARLY_BB to BEST_BB should be avoided. */
177 :
178 : static bool
179 4339291 : 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 4339291 : 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 4339190 : if (best_bb == early_bb->loop_father->latch
190 4339190 : && 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 4058767 : if (best_bb->loop_father == early_bb->loop_father
196 2864875 : && loop_outer (best_bb->loop_father)
197 762885 : && !best_bb->loop_father->inner
198 435598 : && gimple_vuse (stmt)
199 178690 : && !gimple_vdef (stmt)
200 165686 : && flag_tree_loop_vectorize
201 156242 : && !(cfun->curr_properties & PROP_loop_opts_done)
202 113611 : && dominated_by_p (CDI_DOMINATORS, best_bb->loop_father->latch, early_bb)
203 4146333 : && !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 16544433 : 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 16544433 : while (late_bb != early_bb
224 16845432 : && do_not_sink (stmt, early_bb, late_bb))
225 300999 : late_bb = get_immediate_dominator (CDI_DOMINATORS, late_bb);
226 :
227 16544433 : basic_block best_bb = late_bb;
228 16544433 : basic_block temp_bb = late_bb;
229 19728071 : while (temp_bb != early_bb)
230 : {
231 : /* Walk up the dominator tree, hopefully we'll find a shallower
232 : loop nest. */
233 3183638 : temp_bb = get_immediate_dominator (CDI_DOMINATORS, temp_bb);
234 :
235 : /* Do not consider blocks we do not want to sink to. */
236 3183638 : 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 3183394 : 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 2619344 : else if (bb_loop_depth (temp_bb) > bb_loop_depth (best_bb))
246 : ;
247 :
248 : /* Likewise an irreducible region inside an otherwise same loop
249 : depth. */
250 2359166 : else if ((temp_bb->flags & BB_IRREDUCIBLE_LOOP)
251 5450 : && !(best_bb->flags & BB_IRREDUCIBLE_LOOP))
252 : ;
253 :
254 : /* But sink the least distance, if the new candidate on the same
255 : loop depth is post-dominated by the current best block pick
256 : the new candidate. */
257 2358947 : else if (dominated_by_p (CDI_POST_DOMINATORS, temp_bb, best_bb))
258 : best_bb = temp_bb;
259 :
260 : /* Avoid sinking across a conditional branching to exceptional
261 : code. In practice this does not reduce the number of dynamic
262 : executions of the sunk statement (this includes EH and
263 : branches leading to abort for example). Treat this case as
264 : post-dominating. */
265 3491963 : else if (single_pred_p (best_bb)
266 1526324 : && single_pred_edge (best_bb)->src == temp_bb
267 2724798 : && (single_pred_edge (best_bb)->flags & EDGE_FALLTHRU
268 982607 : || (single_pred_edge (best_bb)->probability
269 2772979 : >= profile_probability::always ())))
270 1393108 : best_bb = temp_bb;
271 : }
272 :
273 16544433 : gcc_checking_assert (best_bb == early_bb
274 : || !do_not_sink (stmt, early_bb, best_bb));
275 :
276 16544433 : return best_bb;
277 : }
278 :
279 : /* Given a statement (STMT) and the basic block it is currently in (FROMBB),
280 : determine the location to sink the statement to, if any.
281 : Returns true if there is such location; in that case, TOGSI points to the
282 : statement before that STMT should be moved. */
283 :
284 : static bool
285 118259864 : statement_sink_location (gimple *stmt, basic_block frombb,
286 : gimple_stmt_iterator *togsi, bool *zero_uses_p,
287 : virtual_operand_live &vop_live)
288 : {
289 118259864 : gimple *use;
290 118259864 : use_operand_p one_use = NULL_USE_OPERAND_P;
291 118259864 : basic_block sinkbb;
292 118259864 : use_operand_p use_p;
293 118259864 : def_operand_p def_p;
294 118259864 : ssa_op_iter iter;
295 118259864 : imm_use_iterator imm_iter;
296 :
297 118259864 : *zero_uses_p = false;
298 :
299 : /* We only can sink assignments and const/pure calls that are guaranteed
300 : to return exactly once. */
301 118259864 : int cf;
302 118259864 : if (!is_gimple_assign (stmt)
303 118259864 : && (!is_gimple_call (stmt)
304 5295464 : || !((cf = gimple_call_flags (stmt)) & (ECF_CONST|ECF_PURE))
305 1054299 : || (cf & (ECF_LOOPING_CONST_OR_PURE|ECF_RETURNS_TWICE))))
306 85769852 : return false;
307 :
308 : /* We only can sink stmts with a single definition. */
309 32490012 : def_p = single_ssa_def_operand (stmt, SSA_OP_ALL_DEFS);
310 32490012 : if (def_p == NULL_DEF_OPERAND_P)
311 : return false;
312 :
313 : /* There are a few classes of things we can't or don't move, some because we
314 : don't have code to handle it, some because it's not profitable and some
315 : because it's not legal.
316 :
317 : We can't sink things that may be global stores, at least not without
318 : calculating a lot more information, because we may cause it to no longer
319 : be seen by an external routine that needs it depending on where it gets
320 : moved to.
321 :
322 : We can't sink statements that end basic blocks without splitting the
323 : incoming edge for the sink location to place it there.
324 :
325 : We can't sink statements that have volatile operands.
326 :
327 : We don't want to sink dead code, so anything with 0 immediate uses is not
328 : sunk.
329 :
330 : Don't sink BLKmode assignments if current function has any local explicit
331 : register variables, as BLKmode assignments may involve memcpy or memset
332 : calls or, on some targets, inline expansion thereof that sometimes need
333 : to use specific hard registers.
334 :
335 : */
336 32489950 : if (stmt_ends_bb_p (stmt)
337 32309836 : || gimple_has_side_effects (stmt)
338 62843203 : || (cfun->has_local_explicit_reg_vars
339 1654 : && TYPE_MODE (TREE_TYPE (gimple_get_lhs (stmt))) == BLKmode))
340 2136698 : return false;
341 :
342 : /* Return if there are no immediate uses of this stmt. */
343 30353252 : if (has_zero_uses (DEF_FROM_PTR (def_p)))
344 : {
345 106216 : *zero_uses_p = true;
346 106216 : return false;
347 : }
348 :
349 30247036 : if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (DEF_FROM_PTR (def_p)))
350 : return false;
351 :
352 74399615 : FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
353 : {
354 44154856 : tree use = USE_FROM_PTR (use_p);
355 44154856 : if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (use))
356 : return false;
357 : }
358 :
359 30244759 : use = NULL;
360 :
361 : /* If stmt is a store the one and only use needs to be a VUSE on
362 : the live path. */
363 30244759 : if (virtual_operand_p (DEF_FROM_PTR (def_p)))
364 : {
365 8098838 : tree lhs = gimple_get_lhs (stmt);
366 8098838 : ao_ref ref;
367 8098838 : ao_ref_init (&ref, lhs);
368 25229839 : FOR_EACH_IMM_USE_FAST (use_p, imm_iter, DEF_FROM_PTR (def_p))
369 : {
370 10729682 : gimple *use_stmt = USE_STMT (use_p);
371 :
372 : /* A killing definition is not a use. */
373 10729682 : if (gimple_vdef (use_stmt)
374 11236613 : && ((gimple_has_lhs (use_stmt)
375 6763685 : && operand_equal_p (lhs,
376 6763685 : gimple_get_lhs (use_stmt), 0))
377 7856797 : || stmt_kills_ref_p (use_stmt, &ref)))
378 : {
379 : /* If use_stmt is or might be a nop assignment then USE_STMT
380 : acts as a use as well as definition. */
381 51413 : if (stmt != use_stmt
382 51413 : && ref_maybe_used_by_stmt_p (use_stmt, &ref))
383 : {
384 2127 : if (use && use != use_stmt)
385 : return false;
386 : use = use_stmt;
387 : }
388 51323 : continue;
389 : }
390 :
391 10678269 : if (is_a <gphi *> (use_stmt)
392 10678269 : || ref_maybe_used_by_stmt_p (use_stmt, &ref))
393 : {
394 3389286 : if (use && use != use_stmt)
395 : return false;
396 2365862 : use = use_stmt;
397 2365862 : continue;
398 : }
399 :
400 22400410 : if (gimple_vdef (use_stmt))
401 : {
402 6079264 : if (stmt_may_clobber_ref_p_1 (use_stmt, &ref, false))
403 : return false;
404 : /* We do not look past VDEFs, so treat them as sink location. */
405 5657516 : if (use && use != use_stmt)
406 : return false;
407 : use = use_stmt;
408 : }
409 1697519 : }
410 6401319 : if (!use)
411 : return false;
412 : }
413 : /* If all the immediate uses are not in the same place, find the nearest
414 : common dominator of all the immediate uses. For PHI nodes, we have to
415 : find the nearest common dominator of all of the predecessor blocks, since
416 : that is where insertion would have to take place. */
417 22145921 : else if (gimple_vuse (stmt)
418 22145921 : || !all_immediate_uses_same_place (def_p))
419 : {
420 12617052 : bool debug_stmts = false;
421 12617052 : basic_block commondom = nearest_common_dominator_of_uses (def_p,
422 : &debug_stmts);
423 :
424 12617052 : if (commondom == frombb)
425 : return false;
426 :
427 : /* If this is a load then do not sink past any stores. */
428 2052490 : if (gimple_vuse (stmt))
429 : {
430 : /* Do not sink loads from hard registers. */
431 793667 : if (gimple_assign_single_p (stmt)
432 790506 : && VAR_P (gimple_assign_rhs1 (stmt))
433 816960 : && DECL_HARD_REGISTER (gimple_assign_rhs1 (stmt)))
434 : return false;
435 :
436 : /* When the live virtual operand at the intended sink location is
437 : not the same as the one from the load walk up the dominator tree
438 : for a new candidate location. */
439 : while (commondom != frombb
440 3502670 : && vop_live.get_live_in (commondom) != gimple_vuse (stmt))
441 1151085 : commondom = get_immediate_dominator (CDI_DOMINATORS, commondom);
442 793661 : if (commondom == frombb)
443 : return false;
444 : }
445 :
446 : /* Our common dominator has to be dominated by frombb in order to be a
447 : trivially safe place to put this statement, since it has multiple
448 : uses. */
449 639417 : if (!dominated_by_p (CDI_DOMINATORS, commondom, frombb))
450 : return false;
451 :
452 639417 : commondom = select_best_block (frombb, commondom, stmt);
453 :
454 639417 : if (commondom == frombb)
455 : return false;
456 :
457 386919 : *togsi = gsi_after_labels (commondom);
458 :
459 386919 : return true;
460 : }
461 : else
462 : {
463 19479325 : FOR_EACH_IMM_USE_FAST (one_use, imm_iter, DEF_FROM_PTR (def_p))
464 : {
465 9950456 : if (is_gimple_debug (USE_STMT (one_use)))
466 421587 : continue;
467 : break;
468 9528869 : }
469 9528869 : use = USE_STMT (one_use);
470 : }
471 :
472 15921974 : if (gimple_code (use) != GIMPLE_PHI)
473 : {
474 15233994 : sinkbb = select_best_block (frombb, gimple_bb (use), stmt);
475 :
476 15233994 : if (sinkbb == frombb)
477 : return false;
478 :
479 : /* The SSA update for sinking of stores cannot insert PHIs, the
480 : sink location has to lead to exit without crossing any CFG
481 : merge points to paths not dominated by the sink location. */
482 356509 : if (gimple_vdef (stmt)
483 105546936 : && (!single_succ_p (sinkbb)
484 6453 : || single_succ (sinkbb)->index != EXIT_BLOCK))
485 : return false;
486 :
487 347646 : *togsi = gsi_after_labels (sinkbb);
488 :
489 347646 : return true;
490 : }
491 :
492 687980 : sinkbb = find_bb_for_arg (as_a <gphi *> (use), DEF_FROM_PTR (def_p));
493 :
494 : /* This can happen if there are multiple uses in a PHI. */
495 687980 : if (!sinkbb)
496 : return false;
497 :
498 671022 : basic_block bestbb = select_best_block (frombb, sinkbb, stmt);
499 671022 : if (bestbb == frombb
500 : /* When we sink a store make sure there's not a path to any of
501 : the possibly skipped killing defs as that wrecks the virtual
502 : operand update, requiring inserting of a PHI node. */
503 114803 : || (gimple_vdef (stmt)
504 3597 : && bestbb != sinkbb
505 21 : && !dominated_by_p (CDI_POST_DOMINATORS, bestbb, sinkbb))
506 : /* Likewise avoid placing VDEFs into an irreducible region. */
507 782228 : || (gimple_vdef (stmt)
508 3577 : && (bestbb->flags & BB_IRREDUCIBLE_LOOP)))
509 559830 : return false;
510 :
511 111192 : *togsi = gsi_after_labels (bestbb);
512 :
513 111192 : return true;
514 : }
515 :
516 : /* Very simplistic code to sink common stores from the predecessor through
517 : our virtual PHI. We do this before sinking stmts from BB as it might
518 : expose sinking opportunities of the merged stores.
519 : Once we have partial dead code elimination through sth like SSU-PRE this
520 : should be moved there. */
521 :
522 : static unsigned
523 32312396 : sink_common_stores_to_bb (basic_block bb)
524 : {
525 32312396 : unsigned todo = 0;
526 32312396 : gphi *phi;
527 :
528 32312396 : if (EDGE_COUNT (bb->preds) > 1
529 30202366 : && (phi = get_virtual_phi (bb)))
530 : {
531 : /* Repeat until no more common stores are found. */
532 3780711 : while (1)
533 : {
534 3714482 : gimple *first_store = NULL;
535 3714482 : auto_vec <tree, 5> vdefs;
536 3714482 : gimple_stmt_iterator gsi;
537 :
538 : /* Search for common stores defined by all virtual PHI args.
539 : ??? Common stores not present in all predecessors could
540 : be handled by inserting a forwarder to sink to. Generally
541 : this involves deciding which stores to do this for if
542 : multiple common stores are present for different sets of
543 : predecessors. See PR11832 for an interesting case. */
544 4549348 : for (unsigned i = 0; i < gimple_phi_num_args (phi); ++i)
545 : {
546 4480103 : tree arg = gimple_phi_arg_def (phi, i);
547 4480103 : gimple *def = SSA_NAME_DEF_STMT (arg);
548 4480103 : if (! is_gimple_assign (def)
549 1943932 : || stmt_can_throw_internal (cfun, def)
550 1929318 : || (gimple_phi_arg_edge (phi, i)->flags & EDGE_ABNORMAL)
551 6409417 : || stmt_references_abnormal_ssa_name (def))
552 : {
553 : /* ??? We could handle some cascading with the def being
554 : another PHI. We'd have to insert multiple PHIs for
555 : the rhs then though (if they are not all equal). */
556 : first_store = NULL;
557 3645237 : break;
558 : }
559 : /* ??? Do not try to do anything fancy with aliasing, thus
560 : do not sink across non-aliased loads (or even stores,
561 : so different store order will make the sinking fail). */
562 1929299 : bool all_uses_on_phi = true;
563 1929299 : imm_use_iterator iter;
564 1929299 : use_operand_p use_p;
565 5309031 : FOR_EACH_IMM_USE_FAST (use_p, iter, arg)
566 2448233 : if (USE_STMT (use_p) != phi)
567 : {
568 : all_uses_on_phi = false;
569 : break;
570 1929299 : }
571 1929299 : if (! all_uses_on_phi)
572 : {
573 : first_store = NULL;
574 : break;
575 : }
576 : /* Check all stores are to the same LHS. */
577 931499 : if (! first_store)
578 : first_store = def;
579 : /* ??? We could handle differing SSA uses in the LHS by inserting
580 : PHIs for them. */
581 259494 : else if (! operand_equal_p (gimple_assign_lhs (first_store),
582 259494 : gimple_assign_lhs (def), 0)
583 422355 : || (gimple_clobber_p (first_store)
584 162861 : != gimple_clobber_p (def)))
585 : {
586 : first_store = NULL;
587 : break;
588 : }
589 834866 : vdefs.safe_push (arg);
590 : }
591 3714482 : if (! first_store)
592 : break;
593 :
594 : /* Check if we need a PHI node to merge the stored values. */
595 69245 : bool allsame = true;
596 69245 : if (!gimple_clobber_p (first_store))
597 87536 : for (unsigned i = 1; i < vdefs.length (); ++i)
598 : {
599 80799 : gimple *def = SSA_NAME_DEF_STMT (vdefs[i]);
600 80799 : if (! operand_equal_p (gimple_assign_rhs1 (first_store),
601 80799 : gimple_assign_rhs1 (def), 0))
602 : {
603 : allsame = false;
604 : break;
605 : }
606 : }
607 :
608 : /* We cannot handle aggregate values if we need to merge them. */
609 69245 : tree type = TREE_TYPE (gimple_assign_lhs (first_store));
610 69245 : if (! allsame
611 69245 : && ! is_gimple_reg_type (type))
612 : break;
613 :
614 66229 : if (dump_enabled_p ())
615 : {
616 18 : dump_printf_loc (MSG_OPTIMIZED_LOCATIONS,
617 9 : first_store,
618 : "sinking common stores %sto ",
619 : allsame ? "with same value " : "");
620 9 : dump_generic_expr (MSG_OPTIMIZED_LOCATIONS, TDF_SLIM,
621 : gimple_assign_lhs (first_store));
622 9 : dump_printf (MSG_OPTIMIZED_LOCATIONS, "\n");
623 : }
624 :
625 : /* Insert a PHI to merge differing stored values if necessary.
626 : Note that in general inserting PHIs isn't a very good idea as
627 : it makes the job of coalescing and register allocation harder.
628 : Even common SSA uses on the rhs/lhs might extend their lifetime
629 : across multiple edges by this code motion which makes
630 : register allocation harder. */
631 66229 : tree from;
632 66229 : if (! allsame)
633 : {
634 51650 : from = make_ssa_name (type);
635 51650 : gphi *newphi = create_phi_node (from, bb);
636 216095 : for (unsigned i = 0; i < vdefs.length (); ++i)
637 : {
638 164445 : gimple *def = SSA_NAME_DEF_STMT (vdefs[i]);
639 164445 : add_phi_arg (newphi, gimple_assign_rhs1 (def),
640 164445 : EDGE_PRED (bb, i), UNKNOWN_LOCATION);
641 : }
642 : }
643 : else
644 14579 : from = gimple_assign_rhs1 (first_store);
645 :
646 : /* Remove all stores. */
647 537860 : for (unsigned i = 0; i < vdefs.length (); ++i)
648 202701 : TREE_VISITED (vdefs[i]) = 1;
649 268930 : for (unsigned i = 0; i < vdefs.length (); ++i)
650 : /* If we have more than one use of a VDEF on the PHI make sure
651 : we remove the defining stmt only once. */
652 202701 : if (TREE_VISITED (vdefs[i]))
653 : {
654 199246 : TREE_VISITED (vdefs[i]) = 0;
655 199246 : gimple *def = SSA_NAME_DEF_STMT (vdefs[i]);
656 199246 : gsi = gsi_for_stmt (def);
657 199246 : unlink_stmt_vdef (def);
658 199246 : gsi_remove (&gsi, true);
659 199246 : release_defs (def);
660 : }
661 :
662 : /* Insert the first store at the beginning of the merge BB. */
663 66229 : gimple_set_vdef (first_store, gimple_phi_result (phi));
664 132458 : SSA_NAME_DEF_STMT (gimple_vdef (first_store)) = first_store;
665 66229 : gimple_phi_set_result (phi, make_ssa_name (gimple_vop (cfun)));
666 66229 : gimple_set_vuse (first_store, gimple_phi_result (phi));
667 66229 : gimple_assign_set_rhs1 (first_store, from);
668 : /* ??? Should we reset first_stores location? */
669 66229 : gsi = gsi_after_labels (bb);
670 66229 : gsi_insert_before (&gsi, first_store, GSI_SAME_STMT);
671 66229 : sink_stats.commoned++;
672 :
673 66229 : todo |= TODO_cleanup_cfg;
674 3714482 : }
675 :
676 : /* We could now have empty predecessors that we could remove,
677 : forming a proper CFG for further sinking. Note that even
678 : CFG cleanup doesn't do this fully at the moment and it
679 : doesn't preserve post-dominators in the process either.
680 : The mergephi pass might do it though. gcc.dg/tree-ssa/ssa-sink-13.c
681 : shows this nicely if you disable tail merging or (same effect)
682 : make the stored values unequal. */
683 : }
684 :
685 32312396 : return todo;
686 : }
687 :
688 : /* Perform code sinking on BB */
689 :
690 : static unsigned
691 32312396 : sink_code_in_bb (basic_block bb, virtual_operand_live &vop_live)
692 : {
693 32312396 : gimple_stmt_iterator gsi;
694 32312396 : edge_iterator ei;
695 32312396 : edge e;
696 32312396 : bool last = true;
697 32312396 : unsigned todo = 0;
698 :
699 : /* Sink common stores from the predecessor through our virtual PHI. */
700 32312396 : todo |= sink_common_stores_to_bb (bb);
701 :
702 : /* If this block doesn't dominate anything, there can't be any place to sink
703 : the statements to. */
704 32312396 : if (first_dom_son (CDI_DOMINATORS, bb) == NULL)
705 : return todo;
706 :
707 : /* We can't move things across abnormal edges, so don't try. */
708 38092931 : FOR_EACH_EDGE (e, ei, bb->succs)
709 24157197 : if (e->flags & EDGE_ABNORMAL)
710 : return todo;
711 :
712 146131332 : for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi);)
713 : {
714 118259864 : gimple *stmt = gsi_stmt (gsi);
715 118259864 : gimple_stmt_iterator togsi;
716 118259864 : bool zero_uses_p;
717 :
718 118259864 : if (!statement_sink_location (stmt, bb, &togsi, &zero_uses_p, vop_live))
719 : {
720 117414107 : gimple_stmt_iterator saved = gsi;
721 117414107 : if (!gsi_end_p (gsi))
722 117414107 : gsi_prev (&gsi);
723 : /* If we face a dead stmt remove it as it possibly blocks
724 : sinking of uses. */
725 117414107 : if (zero_uses_p
726 106216 : && !gimple_vdef (stmt)
727 117516524 : && (cfun->can_delete_dead_exceptions
728 77013 : || !stmt_could_throw_p (cfun, stmt)))
729 : {
730 54982 : gsi_remove (&saved, true);
731 54982 : release_defs (stmt);
732 : }
733 : else
734 : last = false;
735 117414107 : continue;
736 117414107 : }
737 845757 : if (dump_file)
738 : {
739 37 : fprintf (dump_file, "Sinking ");
740 37 : print_gimple_stmt (dump_file, stmt, 0, TDF_VOPS);
741 37 : fprintf (dump_file, " from bb %d to bb %d\n",
742 37 : bb->index, (gsi_bb (togsi))->index);
743 : }
744 :
745 : /* Update virtual operands of statements in the path we
746 : do not sink to. */
747 1691514 : if (gimple_vdef (stmt))
748 : {
749 4296 : imm_use_iterator iter;
750 4296 : use_operand_p use_p;
751 4296 : gimple *vuse_stmt;
752 :
753 22776 : FOR_EACH_IMM_USE_STMT (vuse_stmt, iter, gimple_vdef (stmt))
754 14184 : if (gimple_code (vuse_stmt) != GIMPLE_PHI
755 14184 : && !dominated_by_p (CDI_DOMINATORS, gimple_bb (vuse_stmt),
756 10621 : gsi_bb (togsi)))
757 28968 : FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
758 23608 : SET_USE (use_p, gimple_vuse (stmt));
759 : }
760 :
761 : /* If this is the end of the basic block, we need to insert at the end
762 : of the basic block. */
763 845757 : if (gsi_end_p (togsi))
764 133587 : gsi_move_to_bb_end (&gsi, gsi_bb (togsi));
765 : else
766 712170 : gsi_move_before (&gsi, &togsi);
767 :
768 845757 : sink_stats.sunk++;
769 :
770 : /* If we've just removed the last statement of the BB, the
771 : gsi_end_p() test below would fail, but gsi_prev() would have
772 : succeeded, and we want it to succeed. So we keep track of
773 : whether we're at the last statement and pick up the new last
774 : statement. */
775 845757 : if (last)
776 : {
777 10910 : gsi = gsi_last_bb (bb);
778 10910 : continue;
779 : }
780 :
781 834847 : last = false;
782 834847 : if (!gsi_end_p (gsi))
783 1669694 : gsi_prev (&gsi);
784 :
785 : }
786 :
787 : return todo;
788 : }
789 :
790 : /* Perform code sinking.
791 : This moves code down the flowgraph when we know it would be
792 : profitable to do so, or it wouldn't increase the number of
793 : executions of the statement.
794 :
795 : IE given
796 :
797 : a_1 = b + c;
798 : if (<something>)
799 : {
800 : }
801 : else
802 : {
803 : foo (&b, &c);
804 : a_5 = b + c;
805 : }
806 : a_6 = PHI (a_5, a_1);
807 : USE a_6.
808 :
809 : we'll transform this into:
810 :
811 : if (<something>)
812 : {
813 : a_1 = b + c;
814 : }
815 : else
816 : {
817 : foo (&b, &c);
818 : a_5 = b + c;
819 : }
820 : a_6 = PHI (a_5, a_1);
821 : USE a_6.
822 :
823 : Note that this reduces the number of computations of a = b + c to 1
824 : when we take the else edge, instead of 2.
825 : */
826 : namespace {
827 :
828 : const pass_data pass_data_sink_code =
829 : {
830 : GIMPLE_PASS, /* type */
831 : "sink", /* name */
832 : OPTGROUP_NONE, /* optinfo_flags */
833 : TV_TREE_SINK, /* tv_id */
834 : /* PROP_no_crit_edges is ensured by running split_edges_for_insertion in
835 : pass_data_sink_code::execute (). */
836 : ( PROP_cfg | PROP_ssa ), /* properties_required */
837 : 0, /* properties_provided */
838 : 0, /* properties_destroyed */
839 : 0, /* todo_flags_start */
840 : TODO_update_ssa, /* todo_flags_finish */
841 : };
842 :
843 : class pass_sink_code : public gimple_opt_pass
844 : {
845 : public:
846 584742 : pass_sink_code (gcc::context *ctxt)
847 1169484 : : gimple_opt_pass (pass_data_sink_code, ctxt), unsplit_edges (false)
848 : {}
849 :
850 : /* opt_pass methods: */
851 2110210 : bool gate (function *) final override { return flag_tree_sink != 0; }
852 : unsigned int execute (function *) final override;
853 292371 : opt_pass *clone (void) final override { return new pass_sink_code (m_ctxt); }
854 584742 : void set_pass_param (unsigned n, bool param) final override
855 : {
856 584742 : gcc_assert (n == 0);
857 584742 : unsplit_edges = param;
858 584742 : }
859 :
860 : private:
861 : bool unsplit_edges;
862 : }; // class pass_sink_code
863 :
864 : unsigned int
865 2110030 : pass_sink_code::execute (function *fun)
866 : {
867 2110030 : loop_optimizer_init (LOOPS_NORMAL);
868 2110030 : split_edges_for_insertion ();
869 : /* Arrange for the critical edge splitting to be undone if requested. */
870 2110030 : unsigned todo = unsplit_edges ? TODO_cleanup_cfg : 0;
871 2110030 : connect_infinite_loops_to_exit ();
872 2110030 : mark_dfs_back_edges (fun);
873 2110030 : memset (&sink_stats, 0, sizeof (sink_stats));
874 2110030 : calculate_dominance_info (CDI_DOMINATORS);
875 2110030 : calculate_dominance_info (CDI_POST_DOMINATORS);
876 :
877 2110030 : virtual_operand_live vop_live;
878 :
879 2110030 : int *rpo = XNEWVEC (int, n_basic_blocks_for_fn (cfun));
880 2110030 : int n = inverted_rev_post_order_compute (fun, rpo);
881 34422426 : for (int i = 0; i < n; ++i)
882 32312396 : todo |= sink_code_in_bb (BASIC_BLOCK_FOR_FN (fun, rpo[i]), vop_live);
883 2110030 : free (rpo);
884 :
885 2110030 : statistics_counter_event (fun, "Sunk statements", sink_stats.sunk);
886 2110030 : statistics_counter_event (fun, "Commoned stores", sink_stats.commoned);
887 2110030 : free_dominance_info (CDI_POST_DOMINATORS);
888 2110030 : remove_fake_exit_edges ();
889 2110030 : loop_optimizer_finalize ();
890 :
891 2110030 : return todo;
892 2110030 : }
893 :
894 : } // anon namespace
895 :
896 : gimple_opt_pass *
897 292371 : make_pass_sink_code (gcc::context *ctxt)
898 : {
899 292371 : return new pass_sink_code (ctxt);
900 : }
|
