1 /* Support routines for Splitting Paths to loop backedges
2 Copyright (C) 2015-2019 Free Software Foundation, Inc.
3 Contributed by Ajit Kumar Agarwal <ajitkum@xilinx.com>.
5 This file is part of GCC.
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)
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.
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/>. */
23 #include "coretypes.h"
27 #include "tree-pass.h"
31 #include "gimple-iterator.h"
35 #include "gimple-ssa.h"
36 #include "tree-phinodes.h"
37 #include "ssa-iterators.h"
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. */
45 find_block_to_duplicate_for_splitting_paths (basic_block latch
)
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
))
54 basic_block bb
= get_immediate_dominator (CDI_DOMINATORS
, latch
);
55 gcc_assert (single_pred_edge (latch
)->src
== bb
);
57 /* If BB has been marked as not to be duplicated, then honor that
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
)
67 /* We're hoping that BB is a join point for an IF-THEN-ELSE diamond
68 region. Verify that it is.
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
))
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
)
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
)))
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
)))
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.
107 We're going to want to create two duplicates of BB, one for
108 each successor of BB_IDOM. */
115 /* Return the number of non-debug statements in a block. */
117 count_stmts_in_block (basic_block bb
)
119 gimple_stmt_iterator gsi
;
120 unsigned int num_stmts
= 0;
122 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
124 gimple
*stmt
= gsi_stmt (gsi
);
125 if (!is_gimple_debug (stmt
))
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. */
135 poor_ifcvt_candidate_code (enum tree_code code
)
137 return (code
== MIN_EXPR
141 || code
== CALL_EXPR
);
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.
149 We do not want to spoil if-conversion if at all possible.
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.
155 CSE/DCE opportunties crop up when statements from the predecessors
156 feed statements in the latch and allow statements in the latch to
160 is_feasible_trace (basic_block bb
)
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;
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)
176 gimple
*stmt1
= last_and_only_stmt (pred1
);
177 gimple
*stmt2
= last_and_only_stmt (pred2
);
180 && gimple_code (stmt1
) == GIMPLE_ASSIGN
181 && gimple_code (stmt2
) == GIMPLE_ASSIGN
)
183 enum tree_code code1
= gimple_assign_rhs_code (stmt1
);
184 enum tree_code code2
= gimple_assign_rhs_code (stmt2
);
186 if (!poor_ifcvt_candidate_code (code1
)
187 && !poor_ifcvt_candidate_code (code2
))
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
))
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
))
200 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
202 "Block %d appears to be a join point for "
203 "if-convertable diamond.\n",
212 /* Canonicalize the form. */
213 if (num_stmts_in_pred1
== 0 && num_stmts_in_pred2
== 1)
215 std::swap (pred1
, pred2
);
216 std::swap (num_stmts_in_pred1
, num_stmts_in_pred2
);
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
))
223 gimple
*stmt1
= last_and_only_stmt (pred1
);
225 /* The only statement in PRED1 must be an assignment that is
226 not a good candidate for if-conversion. This may need some
228 if (stmt1
&& gimple_code (stmt1
) == GIMPLE_ASSIGN
)
230 enum tree_code code1
= gimple_assign_rhs_code (stmt1
);
232 if (!poor_ifcvt_candidate_code (code1
))
234 tree lhs1
= gimple_assign_lhs (stmt1
);
235 tree rhs1
= gimple_assign_rhs1 (stmt1
);
237 gimple_stmt_iterator gsi
;
238 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
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
))
246 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
248 "Block %d appears to be a join point for "
249 "if-convertable half-diamond.\n",
258 /* If the joiner has no PHIs with useful uses there is zero chance
259 of CSE/DCE/jump-threading possibilities exposed by duplicating it. */
260 bool found_useful_phi
= false;
261 for (gphi_iterator si
= gsi_start_phis (bb
); ! gsi_end_p (si
);
264 gphi
*phi
= si
.phi ();
266 imm_use_iterator iter
;
267 FOR_EACH_IMM_USE_FAST (use_p
, iter
, gimple_phi_result (phi
))
269 gimple
*stmt
= USE_STMT (use_p
);
270 if (is_gimple_debug (stmt
))
272 /* If there's a use in the joiner this might be a CSE/DCE
274 if (gimple_bb (stmt
) == bb
)
276 found_useful_phi
= true;
279 /* If the use is on a loop header PHI and on one path the
280 value is unchanged this might expose a jump threading
282 if (gimple_code (stmt
) == GIMPLE_PHI
283 && gimple_bb (stmt
) == bb
->loop_father
->header
284 /* But for memory the PHI alone isn't good enough. */
285 && ! virtual_operand_p (gimple_phi_result (stmt
)))
287 bool found_unchanged_path
= false;
288 for (unsigned i
= 0; i
< gimple_phi_num_args (phi
); ++i
)
289 if (gimple_phi_arg_def (phi
, i
) == gimple_phi_result (stmt
))
291 found_unchanged_path
= true;
294 /* If we found an unchanged path this can only be a threading
295 opportunity if we have uses of the loop header PHI result
296 in a stmt dominating the merge block. Otherwise the
297 splitting may prevent if-conversion. */
298 if (found_unchanged_path
)
300 use_operand_p use2_p
;
301 imm_use_iterator iter2
;
302 FOR_EACH_IMM_USE_FAST (use2_p
, iter2
, gimple_phi_result (stmt
))
304 gimple
*use_stmt
= USE_STMT (use2_p
);
305 if (is_gimple_debug (use_stmt
))
307 basic_block use_bb
= gimple_bb (use_stmt
);
309 && dominated_by_p (CDI_DOMINATORS
, bb
, use_bb
))
311 if (gcond
*cond
= dyn_cast
<gcond
*> (use_stmt
))
312 if (gimple_cond_code (cond
) == EQ_EXPR
313 || gimple_cond_code (cond
) == NE_EXPR
)
314 found_useful_phi
= true;
319 if (found_useful_phi
)
323 if (found_useful_phi
)
326 /* There is one exception namely a controlling condition we can propagate
327 an equivalence from to the joiner. */
328 bool found_cprop_opportunity
= false;
329 basic_block dom
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
330 gcond
*cond
= as_a
<gcond
*> (last_stmt (dom
));
331 if (gimple_cond_code (cond
) == EQ_EXPR
332 || gimple_cond_code (cond
) == NE_EXPR
)
333 for (unsigned i
= 0; i
< 2; ++i
)
335 tree op
= gimple_op (cond
, i
);
336 if (TREE_CODE (op
) == SSA_NAME
)
339 imm_use_iterator iter
;
340 FOR_EACH_IMM_USE_FAST (use_p
, iter
, op
)
342 if (is_gimple_debug (USE_STMT (use_p
)))
344 if (gimple_bb (USE_STMT (use_p
)) == bb
)
346 found_cprop_opportunity
= true;
351 if (found_cprop_opportunity
)
355 if (! found_useful_phi
&& ! found_cprop_opportunity
)
357 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
359 "Block %d is a join that does not expose CSE/DCE/jump-thread "
360 "opportunities when duplicated.\n",
365 /* We may want something here which looks at dataflow and tries
366 to guess if duplication of BB is likely to result in simplification
367 of instructions in BB in either the original or the duplicate. */
369 /* Upper Hard limit on the number statements to copy. */
370 if (num_stmts_in_join
371 >= PARAM_VALUE (PARAM_MAX_JUMP_THREAD_DUPLICATION_STMTS
))
377 /* If the immediate dominator of the latch of the loop is
378 block with conditional branch, then the loop latch is
379 duplicated to its predecessors path preserving the SSA
382 CFG before transformation.
402 Block 8 is the latch. We're going to make copies of block 6 (9 & 10)
403 and wire things up so they look like this:
426 Blocks 9 and 10 will get merged into blocks 4 & 5 respectively which
427 enables CSE, DCE and other optimizations to occur on a larger block
433 bool changed
= false;
436 loop_optimizer_init (LOOPS_NORMAL
| LOOPS_HAVE_RECORDED_EXITS
);
437 initialize_original_copy_tables ();
438 calculate_dominance_info (CDI_DOMINATORS
);
440 FOR_EACH_LOOP (loop
, LI_FROM_INNERMOST
)
442 /* Only split paths if we are optimizing this loop for speed. */
443 if (!optimize_loop_for_speed_p (loop
))
446 /* See if there is a block that we can duplicate to split the
447 path to the loop latch. */
449 = find_block_to_duplicate_for_splitting_paths (loop
->latch
);
451 /* BB is the merge point for an IF-THEN-ELSE we want to transform.
453 Essentially we want to create a duplicate of bb and redirect the
454 first predecessor of BB to the duplicate (leaving the second
455 predecessor as is. This will split the path leading to the latch
456 re-using BB to avoid useless copying. */
457 if (bb
&& is_feasible_trace (bb
))
459 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
461 "Duplicating join block %d into predecessor paths\n",
463 basic_block pred0
= EDGE_PRED (bb
, 0)->src
;
464 if (EDGE_COUNT (pred0
->succs
) != 1)
465 pred0
= EDGE_PRED (bb
, 1)->src
;
466 transform_duplicate (pred0
, bb
);
469 /* If BB has an outgoing edge marked as IRREDUCIBLE, then
470 duplicating BB may result in an irreducible region turning
473 Long term we might want to hook this into the block
474 duplication code, but as we've seen with similar changes
475 for edge removal, that can be somewhat risky. */
476 if (EDGE_SUCC (bb
, 0)->flags
& EDGE_IRREDUCIBLE_LOOP
477 || EDGE_SUCC (bb
, 1)->flags
& EDGE_IRREDUCIBLE_LOOP
)
479 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
481 "Join block %d has EDGE_IRREDUCIBLE_LOOP set. "
482 "Scheduling loop fixups.\n",
484 loops_state_set (LOOPS_NEED_FIXUP
);
489 loop_optimizer_finalize ();
490 free_original_copy_tables ();
494 /* Main entry point for splitting paths. Returns TODO_cleanup_cfg if any
495 paths where split, otherwise return zero. */
498 execute_split_paths ()
500 /* If we don't have at least 2 real blocks and backedges in the
501 CFG, then there's no point in trying to perform path splitting. */
502 if (n_basic_blocks_for_fn (cfun
) <= NUM_FIXED_BLOCKS
+ 1
503 || !mark_dfs_back_edges ())
506 bool changed
= split_paths();
508 free_dominance_info (CDI_DOMINATORS
);
510 return changed
? TODO_cleanup_cfg
: 0;
516 return flag_split_paths
;
521 const pass_data pass_data_split_paths
=
523 GIMPLE_PASS
, /* type */
524 "split-paths", /* name */
525 OPTGROUP_NONE
, /* optinfo_flags */
526 TV_SPLIT_PATHS
, /* tv_id */
527 PROP_ssa
, /* properties_required */
528 0, /* properties_provided */
529 0, /* properties_destroyed */
530 0, /* todo_flags_start */
531 TODO_update_ssa
, /* todo_flags_finish */
534 class pass_split_paths
: public gimple_opt_pass
537 pass_split_paths (gcc::context
*ctxt
)
538 : gimple_opt_pass (pass_data_split_paths
, ctxt
)
540 /* opt_pass methods: */
541 opt_pass
* clone () { return new pass_split_paths (m_ctxt
); }
542 virtual bool gate (function
*) { return gate_split_paths (); }
543 virtual unsigned int execute (function
*) { return execute_split_paths (); }
545 }; // class pass_split_paths
550 make_pass_split_paths (gcc::context
*ctxt
)
552 return new pass_split_paths (ctxt
);