1 /* Support routines for Splitting Paths to loop backedges
2 Copyright (C) 2015-2022 Free Software Foundation, Inc.
3 Contributed by Ajit Kumar Agarwal <ajitkum@xilinx.com>.
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 "tree-pass.h"
28 #include "tree-cfg.h"
29 #include "cfganal.h"
30 #include "cfgloop.h"
31 #include "gimple-iterator.h"
32 #include "tracer.h"
33 #include "predict.h"
34 #include "gimple-ssa.h"
35 #include "tree-phinodes.h"
36 #include "ssa-iterators.h"
37 #include "fold-const.h"
38
39 /* Given LATCH, the latch block in a loop, see if the shape of the
40 path reaching LATCH is suitable for being split by duplication.
41 If so, return the block that will be duplicated into its predecessor
42 paths. Else return NULL. */
43
44 static basic_block
find_block_to_duplicate_for_splitting_paths(basic_block latch)45 find_block_to_duplicate_for_splitting_paths (basic_block latch)
46 {
47 /* We should have simple latches at this point. So the latch should
48 have a single successor. This implies the predecessor of the latch
49 likely has the loop exit. And it's that predecessor we're most
50 interested in. To keep things simple, we're going to require that
51 the latch have a single predecessor too. */
52 if (single_succ_p (latch) && single_pred_p (latch))
53 {
54 basic_block bb = get_immediate_dominator (CDI_DOMINATORS, latch);
55 gcc_assert (single_pred_edge (latch)->src == bb);
56
57 /* If BB has been marked as not to be duplicated, then honor that
58 request. */
59 if (ignore_bb_p (bb))
60 return NULL;
61
62 gimple *last = gsi_stmt (gsi_last_nondebug_bb (bb));
63 /* The immediate dominator of the latch must end in a conditional. */
64 if (!last || gimple_code (last) != GIMPLE_COND)
65 return NULL;
66
67 /* We're hoping that BB is a join point for an IF-THEN-ELSE diamond
68 region. Verify that it is.
69
70 First, verify that BB has two predecessors (each arm of the
71 IF-THEN-ELSE) and two successors (the latch and exit) and that
72 all edges are normal. */
73 if (EDGE_COUNT (bb->preds) == 2
74 && !(EDGE_PRED (bb, 0)->flags & EDGE_COMPLEX)
75 && !(EDGE_PRED (bb, 1)->flags & EDGE_COMPLEX)
76 && EDGE_COUNT (bb->succs) == 2
77 && !(EDGE_SUCC (bb, 0)->flags & EDGE_COMPLEX)
78 && !(EDGE_SUCC (bb, 1)->flags & EDGE_COMPLEX))
79 {
80 /* Now verify that BB's immediate dominator ends in a
81 conditional as well. */
82 basic_block bb_idom = get_immediate_dominator (CDI_DOMINATORS, bb);
83 gimple *last = gsi_stmt (gsi_last_nondebug_bb (bb_idom));
84 if (!last || gimple_code (last) != GIMPLE_COND)
85 return NULL;
86
87 /* And that BB's immediate dominator's successors are the
88 predecessors of BB or BB itself. */
89 if (!(EDGE_PRED (bb, 0)->src == bb_idom
90 || find_edge (bb_idom, EDGE_PRED (bb, 0)->src))
91 || !(EDGE_PRED (bb, 1)->src == bb_idom
92 || find_edge (bb_idom, EDGE_PRED (bb, 1)->src)))
93 return NULL;
94
95 /* And that the predecessors of BB each have a single successor
96 or are BB's immediate domiator itself. */
97 if (!(EDGE_PRED (bb, 0)->src == bb_idom
98 || single_succ_p (EDGE_PRED (bb, 0)->src))
99 || !(EDGE_PRED (bb, 1)->src == bb_idom
100 || single_succ_p (EDGE_PRED (bb, 1)->src)))
101 return NULL;
102
103 /* So at this point we have a simple diamond for an IF-THEN-ELSE
104 construct starting at BB_IDOM, with a join point at BB. BB
105 pass control outside the loop or to the loop latch.
106
107 We're going to want to create two duplicates of BB, one for
108 each successor of BB_IDOM. */
109 return bb;
110 }
111 }
112 return NULL;
113 }
114
115 /* Return the number of non-debug statements in a block. */
116 static unsigned int
count_stmts_in_block(basic_block bb)117 count_stmts_in_block (basic_block bb)
118 {
119 gimple_stmt_iterator gsi;
120 unsigned int num_stmts = 0;
121
122 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
123 {
124 gimple *stmt = gsi_stmt (gsi);
125 if (!is_gimple_debug (stmt))
126 num_stmts++;
127 }
128 return num_stmts;
129 }
130
131 /* Return TRUE if CODE represents a tree code that is not likely to
132 be easily if-convertable because it likely expands into multiple
133 insns, FALSE otherwise. */
134 static bool
poor_ifcvt_candidate_code(enum tree_code code)135 poor_ifcvt_candidate_code (enum tree_code code)
136 {
137 return (code == MIN_EXPR
138 || code == MAX_EXPR
139 || code == ABS_EXPR
140 || code == COND_EXPR
141 || code == CALL_EXPR);
142 }
143
144 /* Return TRUE if BB is a reasonable block to duplicate by examining
145 its size, false otherwise. BB will always be a loop latch block.
146
147 Things to consider:
148
149 We do not want to spoil if-conversion if at all possible.
150
151 Most of the benefit seems to be from eliminating the unconditional
152 jump rather than CSE/DCE opportunities. So favor duplicating
153 small latches. A latch with just a conditional branch is ideal.
154
155 CSE/DCE opportunties crop up when statements from the predecessors
156 feed statements in the latch and allow statements in the latch to
157 simplify. */
158
159 static bool
is_feasible_trace(basic_block bb)160 is_feasible_trace (basic_block bb)
161 {
162 basic_block pred1 = EDGE_PRED (bb, 0)->src;
163 basic_block pred2 = EDGE_PRED (bb, 1)->src;
164 int num_stmts_in_join = count_stmts_in_block (bb);
165 int num_stmts_in_pred1
166 = EDGE_COUNT (pred1->succs) == 1 ? count_stmts_in_block (pred1) : 0;
167 int num_stmts_in_pred2
168 = EDGE_COUNT (pred2->succs) == 1 ? count_stmts_in_block (pred2) : 0;
169
170 /* This is meant to catch cases that are likely opportunities for
171 if-conversion. Essentially we look for the case where
172 BB's predecessors are both single statement blocks where
173 the output of that statement feed the same PHI in BB. */
174 if (num_stmts_in_pred1 == 1 && num_stmts_in_pred2 == 1)
175 {
176 gimple *stmt1 = last_and_only_stmt (pred1);
177 gimple *stmt2 = last_and_only_stmt (pred2);
178
179 if (stmt1 && stmt2
180 && gimple_code (stmt1) == GIMPLE_ASSIGN
181 && gimple_code (stmt2) == GIMPLE_ASSIGN)
182 {
183 enum tree_code code1 = gimple_assign_rhs_code (stmt1);
184 enum tree_code code2 = gimple_assign_rhs_code (stmt2);
185
186 if (!poor_ifcvt_candidate_code (code1)
187 && !poor_ifcvt_candidate_code (code2))
188 {
189 tree lhs1 = gimple_assign_lhs (stmt1);
190 tree lhs2 = gimple_assign_lhs (stmt2);
191 gimple_stmt_iterator gsi;
192 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
193 {
194 gimple *phi = gsi_stmt (gsi);
195 if ((gimple_phi_arg_def (phi, 0) == lhs1
196 && gimple_phi_arg_def (phi, 1) == lhs2)
197 || (gimple_phi_arg_def (phi, 1) == lhs1
198 && gimple_phi_arg_def (phi, 0) == lhs2))
199 {
200 if (dump_file && (dump_flags & TDF_DETAILS))
201 fprintf (dump_file,
202 "Block %d appears to be a join point for "
203 "if-convertable diamond.\n",
204 bb->index);
205 return false;
206 }
207 }
208 }
209 }
210 }
211
212 /* Canonicalize the form. */
213 if (num_stmts_in_pred1 == 0 && num_stmts_in_pred2 == 1)
214 {
215 std::swap (pred1, pred2);
216 std::swap (num_stmts_in_pred1, num_stmts_in_pred2);
217 }
218
219 /* Another variant. This one is half-diamond. */
220 if (num_stmts_in_pred1 == 1 && num_stmts_in_pred2 == 0
221 && dominated_by_p (CDI_DOMINATORS, pred1, pred2))
222 {
223 gimple *stmt1 = last_and_only_stmt (pred1);
224
225 /* The only statement in PRED1 must be an assignment that is
226 not a good candidate for if-conversion. This may need some
227 generalization. */
228 if (stmt1 && gimple_code (stmt1) == GIMPLE_ASSIGN)
229 {
230 enum tree_code code1 = gimple_assign_rhs_code (stmt1);
231
232 if (!poor_ifcvt_candidate_code (code1))
233 {
234 tree lhs1 = gimple_assign_lhs (stmt1);
235 tree rhs1 = gimple_assign_rhs1 (stmt1);
236
237 gimple_stmt_iterator gsi;
238 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
239 {
240 gimple *phi = gsi_stmt (gsi);
241 if ((gimple_phi_arg_def (phi, 0) == lhs1
242 && gimple_phi_arg_def (phi, 1) == rhs1)
243 || (gimple_phi_arg_def (phi, 1) == lhs1
244 && gimple_phi_arg_def (phi, 0) == rhs1))
245 {
246 if (dump_file && (dump_flags & TDF_DETAILS))
247 fprintf (dump_file,
248 "Block %d appears to be a join point for "
249 "if-convertable half-diamond.\n",
250 bb->index);
251 return false;
252 }
253 }
254 }
255 }
256 }
257
258 /* Canonicalize the form. */
259 if (single_pred_p (pred1) && single_pred (pred1) == pred2
260 && num_stmts_in_pred1 == 0)
261 std::swap (pred1, pred2);
262
263 /* This is meant to catch another kind of cases that are likely opportunities
264 for if-conversion. After canonicalizing, PRED2 must be an empty block and
265 PRED1 must be the only predecessor of PRED2. Moreover, PRED1 is supposed
266 to end with a cond_stmt which has the same args with the PHI in BB. */
267 if (single_pred_p (pred2) && single_pred (pred2) == pred1
268 && num_stmts_in_pred2 == 0)
269 {
270 gimple *cond_stmt = last_stmt (pred1);
271 if (cond_stmt && gimple_code (cond_stmt) == GIMPLE_COND)
272 {
273 tree lhs = gimple_cond_lhs (cond_stmt);
274 tree rhs = gimple_cond_rhs (cond_stmt);
275
276 gimple_stmt_iterator gsi;
277 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
278 {
279 gimple *phi = gsi_stmt (gsi);
280 if ((operand_equal_p (gimple_phi_arg_def (phi, 0), lhs)
281 && operand_equal_p (gimple_phi_arg_def (phi, 1), rhs))
282 || (operand_equal_p (gimple_phi_arg_def (phi, 0), rhs)
283 && (operand_equal_p (gimple_phi_arg_def (phi, 1), lhs))))
284 {
285 if (dump_file && (dump_flags & TDF_DETAILS))
286 fprintf (dump_file,
287 "Block %d appears to be optimized to a join "
288 "point for if-convertable half-diamond.\n",
289 bb->index);
290 return false;
291 }
292 }
293 }
294 }
295
296 /* If the joiner has no PHIs with useful uses there is zero chance
297 of CSE/DCE/jump-threading possibilities exposed by duplicating it. */
298 bool found_useful_phi = false;
299 for (gphi_iterator si = gsi_start_phis (bb); ! gsi_end_p (si);
300 gsi_next (&si))
301 {
302 gphi *phi = si.phi ();
303 use_operand_p use_p;
304 imm_use_iterator iter;
305 FOR_EACH_IMM_USE_FAST (use_p, iter, gimple_phi_result (phi))
306 {
307 gimple *stmt = USE_STMT (use_p);
308 if (is_gimple_debug (stmt))
309 continue;
310 /* If there's a use in the joiner this might be a CSE/DCE
311 opportunity, but not if the use is in a conditional
312 which makes this a likely if-conversion candidate. */
313 if (gimple_bb (stmt) == bb
314 && (!is_gimple_assign (stmt)
315 || (TREE_CODE_CLASS (gimple_assign_rhs_code (stmt))
316 != tcc_comparison)))
317 {
318 found_useful_phi = true;
319 break;
320 }
321 /* If the use is on a loop header PHI and on one path the
322 value is unchanged this might expose a jump threading
323 opportunity. */
324 if (gimple_code (stmt) == GIMPLE_PHI
325 && gimple_bb (stmt) == bb->loop_father->header
326 /* But for memory the PHI alone isn't good enough. */
327 && ! virtual_operand_p (gimple_phi_result (stmt)))
328 {
329 bool found_unchanged_path = false;
330 for (unsigned i = 0; i < gimple_phi_num_args (phi); ++i)
331 if (gimple_phi_arg_def (phi, i) == gimple_phi_result (stmt))
332 {
333 found_unchanged_path = true;
334 break;
335 }
336 /* If we found an unchanged path this can only be a threading
337 opportunity if we have uses of the loop header PHI result
338 in a stmt dominating the merge block. Otherwise the
339 splitting may prevent if-conversion. */
340 if (found_unchanged_path)
341 {
342 use_operand_p use2_p;
343 imm_use_iterator iter2;
344 FOR_EACH_IMM_USE_FAST (use2_p, iter2, gimple_phi_result (stmt))
345 {
346 gimple *use_stmt = USE_STMT (use2_p);
347 if (is_gimple_debug (use_stmt))
348 continue;
349 basic_block use_bb = gimple_bb (use_stmt);
350 if (use_bb != bb
351 && dominated_by_p (CDI_DOMINATORS, bb, use_bb))
352 {
353 if (gcond *cond = dyn_cast <gcond *> (use_stmt))
354 if (gimple_cond_code (cond) == EQ_EXPR
355 || gimple_cond_code (cond) == NE_EXPR)
356 found_useful_phi = true;
357 break;
358 }
359 }
360 }
361 if (found_useful_phi)
362 break;
363 }
364 }
365 if (found_useful_phi)
366 break;
367 }
368 /* There is one exception namely a controlling condition we can propagate
369 an equivalence from to the joiner. */
370 bool found_cprop_opportunity = false;
371 basic_block dom = get_immediate_dominator (CDI_DOMINATORS, bb);
372 gcond *cond = as_a <gcond *> (last_stmt (dom));
373 if (gimple_cond_code (cond) == EQ_EXPR
374 || gimple_cond_code (cond) == NE_EXPR)
375 for (unsigned i = 0; i < 2; ++i)
376 {
377 tree op = gimple_op (cond, i);
378 if (TREE_CODE (op) == SSA_NAME)
379 {
380 use_operand_p use_p;
381 imm_use_iterator iter;
382 FOR_EACH_IMM_USE_FAST (use_p, iter, op)
383 {
384 if (is_gimple_debug (USE_STMT (use_p)))
385 continue;
386 if (gimple_bb (USE_STMT (use_p)) == bb)
387 {
388 found_cprop_opportunity = true;
389 break;
390 }
391 }
392 }
393 if (found_cprop_opportunity)
394 break;
395 }
396
397 if (! found_useful_phi && ! found_cprop_opportunity)
398 {
399 if (dump_file && (dump_flags & TDF_DETAILS))
400 fprintf (dump_file,
401 "Block %d is a join that does not expose CSE/DCE/jump-thread "
402 "opportunities when duplicated.\n",
403 bb->index);
404 return false;
405 }
406
407 /* We may want something here which looks at dataflow and tries
408 to guess if duplication of BB is likely to result in simplification
409 of instructions in BB in either the original or the duplicate. */
410
411 /* Upper Hard limit on the number statements to copy. */
412 if (num_stmts_in_join
413 >= param_max_jump_thread_duplication_stmts)
414 return false;
415
416 return true;
417 }
418
419 /* If the immediate dominator of the latch of the loop is
420 block with conditional branch, then the loop latch is
421 duplicated to its predecessors path preserving the SSA
422 semantics.
423
424 CFG before transformation.
425
426 2
427 |
428 |
429 +---->3
430 | / \
431 | / \
432 | 4 5
433 | \ /
434 | \ /
435 | 6
436 | / \
437 | / \
438 | 8 7
439 | | |
440 ---+ E
441
442
443
444 Block 8 is the latch. We're going to make copies of block 6 (9 & 10)
445 and wire things up so they look like this:
446
447 2
448 |
449 |
450 +---->3
451 | / \
452 | / \
453 | 4 5
454 | | |
455 | | |
456 | 9 10
457 | |\ /|
458 | | \ / |
459 | | 7 |
460 | | | |
461 | | E |
462 | | |
463 | \ /
464 | \ /
465 +-----8
466
467
468 Blocks 9 and 10 will get merged into blocks 4 & 5 respectively which
469 enables CSE, DCE and other optimizations to occur on a larger block
470 of code. */
471
472 static bool
split_paths()473 split_paths ()
474 {
475 bool changed = false;
476
477 loop_optimizer_init (LOOPS_NORMAL | LOOPS_HAVE_RECORDED_EXITS);
478 initialize_original_copy_tables ();
479 calculate_dominance_info (CDI_DOMINATORS);
480
481 for (auto loop : loops_list (cfun, LI_FROM_INNERMOST))
482 {
483 /* Only split paths if we are optimizing this loop for speed. */
484 if (!optimize_loop_for_speed_p (loop))
485 continue;
486
487 /* See if there is a block that we can duplicate to split the
488 path to the loop latch. */
489 basic_block bb
490 = find_block_to_duplicate_for_splitting_paths (loop->latch);
491
492 /* BB is the merge point for an IF-THEN-ELSE we want to transform.
493
494 Essentially we want to create a duplicate of bb and redirect the
495 first predecessor of BB to the duplicate (leaving the second
496 predecessor as is. This will split the path leading to the latch
497 re-using BB to avoid useless copying. */
498 if (bb && is_feasible_trace (bb))
499 {
500 if (dump_file && (dump_flags & TDF_DETAILS))
501 fprintf (dump_file,
502 "Duplicating join block %d into predecessor paths\n",
503 bb->index);
504 basic_block pred0 = EDGE_PRED (bb, 0)->src;
505 if (EDGE_COUNT (pred0->succs) != 1)
506 pred0 = EDGE_PRED (bb, 1)->src;
507 transform_duplicate (pred0, bb);
508 changed = true;
509
510 /* If BB has an outgoing edge marked as IRREDUCIBLE, then
511 duplicating BB may result in an irreducible region turning
512 into a natural loop.
513
514 Long term we might want to hook this into the block
515 duplication code, but as we've seen with similar changes
516 for edge removal, that can be somewhat risky. */
517 if (EDGE_SUCC (bb, 0)->flags & EDGE_IRREDUCIBLE_LOOP
518 || EDGE_SUCC (bb, 1)->flags & EDGE_IRREDUCIBLE_LOOP)
519 {
520 if (dump_file && (dump_flags & TDF_DETAILS))
521 fprintf (dump_file,
522 "Join block %d has EDGE_IRREDUCIBLE_LOOP set. "
523 "Scheduling loop fixups.\n",
524 bb->index);
525 loops_state_set (LOOPS_NEED_FIXUP);
526 }
527 }
528 }
529
530 loop_optimizer_finalize ();
531 free_original_copy_tables ();
532 return changed;
533 }
534
535 /* Main entry point for splitting paths. Returns TODO_cleanup_cfg if any
536 paths where split, otherwise return zero. */
537
538 static unsigned int
execute_split_paths()539 execute_split_paths ()
540 {
541 /* If we don't have at least 2 real blocks and backedges in the
542 CFG, then there's no point in trying to perform path splitting. */
543 if (n_basic_blocks_for_fn (cfun) <= NUM_FIXED_BLOCKS + 1
544 || !mark_dfs_back_edges ())
545 return 0;
546
547 bool changed = split_paths();
548 if (changed)
549 free_dominance_info (CDI_DOMINATORS);
550
551 return changed ? TODO_cleanup_cfg : 0;
552 }
553
554 static bool
gate_split_paths()555 gate_split_paths ()
556 {
557 return flag_split_paths;
558 }
559
560 namespace {
561
562 const pass_data pass_data_split_paths =
563 {
564 GIMPLE_PASS, /* type */
565 "split-paths", /* name */
566 OPTGROUP_NONE, /* optinfo_flags */
567 TV_SPLIT_PATHS, /* tv_id */
568 PROP_ssa, /* properties_required */
569 0, /* properties_provided */
570 0, /* properties_destroyed */
571 0, /* todo_flags_start */
572 TODO_update_ssa, /* todo_flags_finish */
573 };
574
575 class pass_split_paths : public gimple_opt_pass
576 {
577 public:
pass_split_paths(gcc::context * ctxt)578 pass_split_paths (gcc::context *ctxt)
579 : gimple_opt_pass (pass_data_split_paths, ctxt)
580 {}
581 /* opt_pass methods: */
clone()582 opt_pass * clone () { return new pass_split_paths (m_ctxt); }
gate(function *)583 virtual bool gate (function *) { return gate_split_paths (); }
execute(function *)584 virtual unsigned int execute (function *) { return execute_split_paths (); }
585
586 }; // class pass_split_paths
587
588 } // anon namespace
589
590 gimple_opt_pass *
make_pass_split_paths(gcc::context * ctxt)591 make_pass_split_paths (gcc::context *ctxt)
592 {
593 return new pass_split_paths (ctxt);
594 }
595