1 /* Support routines for Splitting Paths to loop backedges
2 Copyright (C) 2015-2020 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"
34 #include "gimple-ssa.h"
35 #include "tree-phinodes.h"
36 #include "ssa-iterators.h"
38 /* Given LATCH, the latch block in a loop, see if the shape of the
39 path reaching LATCH is suitable for being split by duplication.
40 If so, return the block that will be duplicated into its predecessor
41 paths. Else return NULL. */
44 find_block_to_duplicate_for_splitting_paths (basic_block latch
)
46 /* We should have simple latches at this point. So the latch should
47 have a single successor. This implies the predecessor of the latch
48 likely has the loop exit. And it's that predecessor we're most
49 interested in. To keep things simple, we're going to require that
50 the latch have a single predecessor too. */
51 if (single_succ_p (latch
) && single_pred_p (latch
))
53 basic_block bb
= get_immediate_dominator (CDI_DOMINATORS
, latch
);
54 gcc_assert (single_pred_edge (latch
)->src
== bb
);
56 /* If BB has been marked as not to be duplicated, then honor that
61 gimple
*last
= gsi_stmt (gsi_last_nondebug_bb (bb
));
62 /* The immediate dominator of the latch must end in a conditional. */
63 if (!last
|| gimple_code (last
) != GIMPLE_COND
)
66 /* We're hoping that BB is a join point for an IF-THEN-ELSE diamond
67 region. Verify that it is.
69 First, verify that BB has two predecessors (each arm of the
70 IF-THEN-ELSE) and two successors (the latch and exit) and that
71 all edges are normal. */
72 if (EDGE_COUNT (bb
->preds
) == 2
73 && !(EDGE_PRED (bb
, 0)->flags
& EDGE_COMPLEX
)
74 && !(EDGE_PRED (bb
, 1)->flags
& EDGE_COMPLEX
)
75 && EDGE_COUNT (bb
->succs
) == 2
76 && !(EDGE_SUCC (bb
, 0)->flags
& EDGE_COMPLEX
)
77 && !(EDGE_SUCC (bb
, 1)->flags
& EDGE_COMPLEX
))
79 /* Now verify that BB's immediate dominator ends in a
80 conditional as well. */
81 basic_block bb_idom
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
82 gimple
*last
= gsi_stmt (gsi_last_nondebug_bb (bb_idom
));
83 if (!last
|| gimple_code (last
) != GIMPLE_COND
)
86 /* And that BB's immediate dominator's successors are the
87 predecessors of BB or BB itself. */
88 if (!(EDGE_PRED (bb
, 0)->src
== bb_idom
89 || find_edge (bb_idom
, EDGE_PRED (bb
, 0)->src
))
90 || !(EDGE_PRED (bb
, 1)->src
== bb_idom
91 || find_edge (bb_idom
, EDGE_PRED (bb
, 1)->src
)))
94 /* And that the predecessors of BB each have a single successor
95 or are BB's immediate domiator itself. */
96 if (!(EDGE_PRED (bb
, 0)->src
== bb_idom
97 || single_succ_p (EDGE_PRED (bb
, 0)->src
))
98 || !(EDGE_PRED (bb
, 1)->src
== bb_idom
99 || single_succ_p (EDGE_PRED (bb
, 1)->src
)))
102 /* So at this point we have a simple diamond for an IF-THEN-ELSE
103 construct starting at BB_IDOM, with a join point at BB. BB
104 pass control outside the loop or to the loop latch.
106 We're going to want to create two duplicates of BB, one for
107 each successor of BB_IDOM. */
114 /* Return the number of non-debug statements in a block. */
116 count_stmts_in_block (basic_block bb
)
118 gimple_stmt_iterator gsi
;
119 unsigned int num_stmts
= 0;
121 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
123 gimple
*stmt
= gsi_stmt (gsi
);
124 if (!is_gimple_debug (stmt
))
130 /* Return TRUE if CODE represents a tree code that is not likely to
131 be easily if-convertable because it likely expands into multiple
132 insns, FALSE otherwise. */
134 poor_ifcvt_candidate_code (enum tree_code code
)
136 return (code
== MIN_EXPR
140 || code
== CALL_EXPR
);
143 /* Return TRUE if BB is a reasonable block to duplicate by examining
144 its size, false otherwise. BB will always be a loop latch block.
148 We do not want to spoil if-conversion if at all possible.
150 Most of the benefit seems to be from eliminating the unconditional
151 jump rather than CSE/DCE opportunities. So favor duplicating
152 small latches. A latch with just a conditional branch is ideal.
154 CSE/DCE opportunties crop up when statements from the predecessors
155 feed statements in the latch and allow statements in the latch to
159 is_feasible_trace (basic_block bb
)
161 basic_block pred1
= EDGE_PRED (bb
, 0)->src
;
162 basic_block pred2
= EDGE_PRED (bb
, 1)->src
;
163 int num_stmts_in_join
= count_stmts_in_block (bb
);
164 int num_stmts_in_pred1
165 = EDGE_COUNT (pred1
->succs
) == 1 ? count_stmts_in_block (pred1
) : 0;
166 int num_stmts_in_pred2
167 = EDGE_COUNT (pred2
->succs
) == 1 ? count_stmts_in_block (pred2
) : 0;
169 /* This is meant to catch cases that are likely opportunities for
170 if-conversion. Essentially we look for the case where
171 BB's predecessors are both single statement blocks where
172 the output of that statement feed the same PHI in BB. */
173 if (num_stmts_in_pred1
== 1 && num_stmts_in_pred2
== 1)
175 gimple
*stmt1
= last_and_only_stmt (pred1
);
176 gimple
*stmt2
= last_and_only_stmt (pred2
);
179 && gimple_code (stmt1
) == GIMPLE_ASSIGN
180 && gimple_code (stmt2
) == GIMPLE_ASSIGN
)
182 enum tree_code code1
= gimple_assign_rhs_code (stmt1
);
183 enum tree_code code2
= gimple_assign_rhs_code (stmt2
);
185 if (!poor_ifcvt_candidate_code (code1
)
186 && !poor_ifcvt_candidate_code (code2
))
188 tree lhs1
= gimple_assign_lhs (stmt1
);
189 tree lhs2
= gimple_assign_lhs (stmt2
);
190 gimple_stmt_iterator gsi
;
191 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
193 gimple
*phi
= gsi_stmt (gsi
);
194 if ((gimple_phi_arg_def (phi
, 0) == lhs1
195 && gimple_phi_arg_def (phi
, 1) == lhs2
)
196 || (gimple_phi_arg_def (phi
, 1) == lhs1
197 && gimple_phi_arg_def (phi
, 0) == lhs2
))
199 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
201 "Block %d appears to be a join point for "
202 "if-convertable diamond.\n",
211 /* Canonicalize the form. */
212 if (num_stmts_in_pred1
== 0 && num_stmts_in_pred2
== 1)
214 std::swap (pred1
, pred2
);
215 std::swap (num_stmts_in_pred1
, num_stmts_in_pred2
);
218 /* Another variant. This one is half-diamond. */
219 if (num_stmts_in_pred1
== 1 && num_stmts_in_pred2
== 0
220 && dominated_by_p (CDI_DOMINATORS
, pred1
, pred2
))
222 gimple
*stmt1
= last_and_only_stmt (pred1
);
224 /* The only statement in PRED1 must be an assignment that is
225 not a good candidate for if-conversion. This may need some
227 if (stmt1
&& gimple_code (stmt1
) == GIMPLE_ASSIGN
)
229 enum tree_code code1
= gimple_assign_rhs_code (stmt1
);
231 if (!poor_ifcvt_candidate_code (code1
))
233 tree lhs1
= gimple_assign_lhs (stmt1
);
234 tree rhs1
= gimple_assign_rhs1 (stmt1
);
236 gimple_stmt_iterator gsi
;
237 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
239 gimple
*phi
= gsi_stmt (gsi
);
240 if ((gimple_phi_arg_def (phi
, 0) == lhs1
241 && gimple_phi_arg_def (phi
, 1) == rhs1
)
242 || (gimple_phi_arg_def (phi
, 1) == lhs1
243 && gimple_phi_arg_def (phi
, 0) == rhs1
))
245 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
247 "Block %d appears to be a join point for "
248 "if-convertable half-diamond.\n",
257 /* If the joiner has no PHIs with useful uses there is zero chance
258 of CSE/DCE/jump-threading possibilities exposed by duplicating it. */
259 bool found_useful_phi
= false;
260 for (gphi_iterator si
= gsi_start_phis (bb
); ! gsi_end_p (si
);
263 gphi
*phi
= si
.phi ();
265 imm_use_iterator iter
;
266 FOR_EACH_IMM_USE_FAST (use_p
, iter
, gimple_phi_result (phi
))
268 gimple
*stmt
= USE_STMT (use_p
);
269 if (is_gimple_debug (stmt
))
271 /* If there's a use in the joiner this might be a CSE/DCE
272 opportunity, but not if the use is in a conditional
273 which makes this a likely if-conversion candidate. */
274 if (gimple_bb (stmt
) == bb
275 && (!is_gimple_assign (stmt
)
276 || (TREE_CODE_CLASS (gimple_assign_rhs_code (stmt
))
279 found_useful_phi
= true;
282 /* If the use is on a loop header PHI and on one path the
283 value is unchanged this might expose a jump threading
285 if (gimple_code (stmt
) == GIMPLE_PHI
286 && gimple_bb (stmt
) == bb
->loop_father
->header
287 /* But for memory the PHI alone isn't good enough. */
288 && ! virtual_operand_p (gimple_phi_result (stmt
)))
290 bool found_unchanged_path
= false;
291 for (unsigned i
= 0; i
< gimple_phi_num_args (phi
); ++i
)
292 if (gimple_phi_arg_def (phi
, i
) == gimple_phi_result (stmt
))
294 found_unchanged_path
= true;
297 /* If we found an unchanged path this can only be a threading
298 opportunity if we have uses of the loop header PHI result
299 in a stmt dominating the merge block. Otherwise the
300 splitting may prevent if-conversion. */
301 if (found_unchanged_path
)
303 use_operand_p use2_p
;
304 imm_use_iterator iter2
;
305 FOR_EACH_IMM_USE_FAST (use2_p
, iter2
, gimple_phi_result (stmt
))
307 gimple
*use_stmt
= USE_STMT (use2_p
);
308 if (is_gimple_debug (use_stmt
))
310 basic_block use_bb
= gimple_bb (use_stmt
);
312 && dominated_by_p (CDI_DOMINATORS
, bb
, use_bb
))
314 if (gcond
*cond
= dyn_cast
<gcond
*> (use_stmt
))
315 if (gimple_cond_code (cond
) == EQ_EXPR
316 || gimple_cond_code (cond
) == NE_EXPR
)
317 found_useful_phi
= true;
322 if (found_useful_phi
)
326 if (found_useful_phi
)
329 /* There is one exception namely a controlling condition we can propagate
330 an equivalence from to the joiner. */
331 bool found_cprop_opportunity
= false;
332 basic_block dom
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
333 gcond
*cond
= as_a
<gcond
*> (last_stmt (dom
));
334 if (gimple_cond_code (cond
) == EQ_EXPR
335 || gimple_cond_code (cond
) == NE_EXPR
)
336 for (unsigned i
= 0; i
< 2; ++i
)
338 tree op
= gimple_op (cond
, i
);
339 if (TREE_CODE (op
) == SSA_NAME
)
342 imm_use_iterator iter
;
343 FOR_EACH_IMM_USE_FAST (use_p
, iter
, op
)
345 if (is_gimple_debug (USE_STMT (use_p
)))
347 if (gimple_bb (USE_STMT (use_p
)) == bb
)
349 found_cprop_opportunity
= true;
354 if (found_cprop_opportunity
)
358 if (! found_useful_phi
&& ! found_cprop_opportunity
)
360 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
362 "Block %d is a join that does not expose CSE/DCE/jump-thread "
363 "opportunities when duplicated.\n",
368 /* We may want something here which looks at dataflow and tries
369 to guess if duplication of BB is likely to result in simplification
370 of instructions in BB in either the original or the duplicate. */
372 /* Upper Hard limit on the number statements to copy. */
373 if (num_stmts_in_join
374 >= param_max_jump_thread_duplication_stmts
)
380 /* If the immediate dominator of the latch of the loop is
381 block with conditional branch, then the loop latch is
382 duplicated to its predecessors path preserving the SSA
385 CFG before transformation.
405 Block 8 is the latch. We're going to make copies of block 6 (9 & 10)
406 and wire things up so they look like this:
429 Blocks 9 and 10 will get merged into blocks 4 & 5 respectively which
430 enables CSE, DCE and other optimizations to occur on a larger block
436 bool changed
= false;
439 loop_optimizer_init (LOOPS_NORMAL
| LOOPS_HAVE_RECORDED_EXITS
);
440 initialize_original_copy_tables ();
441 calculate_dominance_info (CDI_DOMINATORS
);
443 FOR_EACH_LOOP (loop
, LI_FROM_INNERMOST
)
445 /* Only split paths if we are optimizing this loop for speed. */
446 if (!optimize_loop_for_speed_p (loop
))
449 /* See if there is a block that we can duplicate to split the
450 path to the loop latch. */
452 = find_block_to_duplicate_for_splitting_paths (loop
->latch
);
454 /* BB is the merge point for an IF-THEN-ELSE we want to transform.
456 Essentially we want to create a duplicate of bb and redirect the
457 first predecessor of BB to the duplicate (leaving the second
458 predecessor as is. This will split the path leading to the latch
459 re-using BB to avoid useless copying. */
460 if (bb
&& is_feasible_trace (bb
))
462 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
464 "Duplicating join block %d into predecessor paths\n",
466 basic_block pred0
= EDGE_PRED (bb
, 0)->src
;
467 if (EDGE_COUNT (pred0
->succs
) != 1)
468 pred0
= EDGE_PRED (bb
, 1)->src
;
469 transform_duplicate (pred0
, bb
);
472 /* If BB has an outgoing edge marked as IRREDUCIBLE, then
473 duplicating BB may result in an irreducible region turning
476 Long term we might want to hook this into the block
477 duplication code, but as we've seen with similar changes
478 for edge removal, that can be somewhat risky. */
479 if (EDGE_SUCC (bb
, 0)->flags
& EDGE_IRREDUCIBLE_LOOP
480 || EDGE_SUCC (bb
, 1)->flags
& EDGE_IRREDUCIBLE_LOOP
)
482 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
484 "Join block %d has EDGE_IRREDUCIBLE_LOOP set. "
485 "Scheduling loop fixups.\n",
487 loops_state_set (LOOPS_NEED_FIXUP
);
492 loop_optimizer_finalize ();
493 free_original_copy_tables ();
497 /* Main entry point for splitting paths. Returns TODO_cleanup_cfg if any
498 paths where split, otherwise return zero. */
501 execute_split_paths ()
503 /* If we don't have at least 2 real blocks and backedges in the
504 CFG, then there's no point in trying to perform path splitting. */
505 if (n_basic_blocks_for_fn (cfun
) <= NUM_FIXED_BLOCKS
+ 1
506 || !mark_dfs_back_edges ())
509 bool changed
= split_paths();
511 free_dominance_info (CDI_DOMINATORS
);
513 return changed
? TODO_cleanup_cfg
: 0;
519 return flag_split_paths
;
524 const pass_data pass_data_split_paths
=
526 GIMPLE_PASS
, /* type */
527 "split-paths", /* name */
528 OPTGROUP_NONE
, /* optinfo_flags */
529 TV_SPLIT_PATHS
, /* tv_id */
530 PROP_ssa
, /* properties_required */
531 0, /* properties_provided */
532 0, /* properties_destroyed */
533 0, /* todo_flags_start */
534 TODO_update_ssa
, /* todo_flags_finish */
537 class pass_split_paths
: public gimple_opt_pass
540 pass_split_paths (gcc::context
*ctxt
)
541 : gimple_opt_pass (pass_data_split_paths
, ctxt
)
543 /* opt_pass methods: */
544 opt_pass
* clone () { return new pass_split_paths (m_ctxt
); }
545 virtual bool gate (function
*) { return gate_split_paths (); }
546 virtual unsigned int execute (function
*) { return execute_split_paths (); }
548 }; // class pass_split_paths
553 make_pass_split_paths (gcc::context
*ctxt
)
555 return new pass_split_paths (ctxt
);