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). */
72 if (EDGE_COUNT (bb
->preds
) == 2 && EDGE_COUNT (bb
->succs
) == 2)
74 /* Now verify that BB's immediate dominator ends in a
75 conditional as well. */
76 basic_block bb_idom
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
77 gimple
*last
= gsi_stmt (gsi_last_nondebug_bb (bb_idom
));
78 if (!last
|| gimple_code (last
) != GIMPLE_COND
)
81 /* And that BB's immediate dominator's successors are the
82 predecessors of BB or BB itself. */
83 if (!(EDGE_PRED (bb
, 0)->src
== bb_idom
84 || find_edge (bb_idom
, EDGE_PRED (bb
, 0)->src
))
85 || !(EDGE_PRED (bb
, 1)->src
== bb_idom
86 || find_edge (bb_idom
, EDGE_PRED (bb
, 1)->src
)))
89 /* And that the predecessors of BB each have a single successor
90 or are BB's immediate domiator itself. */
91 if (!(EDGE_PRED (bb
, 0)->src
== bb_idom
92 || single_succ_p (EDGE_PRED (bb
, 0)->src
))
93 || !(EDGE_PRED (bb
, 1)->src
== bb_idom
94 || single_succ_p (EDGE_PRED (bb
, 1)->src
)))
97 /* So at this point we have a simple diamond for an IF-THEN-ELSE
98 construct starting at BB_IDOM, with a join point at BB. BB
99 pass control outside the loop or to the loop latch.
101 We're going to want to create two duplicates of BB, one for
102 each successor of BB_IDOM. */
109 /* Return the number of non-debug statements in a block. */
111 count_stmts_in_block (basic_block bb
)
113 gimple_stmt_iterator gsi
;
114 unsigned int num_stmts
= 0;
116 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
118 gimple
*stmt
= gsi_stmt (gsi
);
119 if (!is_gimple_debug (stmt
))
125 /* Return TRUE if CODE represents a tree code that is not likely to
126 be easily if-convertable because it likely expands into multiple
127 insns, FALSE otherwise. */
129 poor_ifcvt_candidate_code (enum tree_code code
)
131 return (code
== MIN_EXPR
135 || code
== CALL_EXPR
);
138 /* Return TRUE if BB is a reasonable block to duplicate by examining
139 its size, false otherwise. BB will always be a loop latch block.
143 We do not want to spoil if-conversion if at all possible.
145 Most of the benefit seems to be from eliminating the unconditional
146 jump rather than CSE/DCE opportunities. So favor duplicating
147 small latches. A latch with just a conditional branch is ideal.
149 CSE/DCE opportunties crop up when statements from the predecessors
150 feed statements in the latch and allow statements in the latch to
154 is_feasible_trace (basic_block bb
)
156 basic_block pred1
= EDGE_PRED (bb
, 0)->src
;
157 basic_block pred2
= EDGE_PRED (bb
, 1)->src
;
158 int num_stmts_in_join
= count_stmts_in_block (bb
);
159 int num_stmts_in_pred1
160 = EDGE_COUNT (pred1
->succs
) == 1 ? count_stmts_in_block (pred1
) : 0;
161 int num_stmts_in_pred2
162 = EDGE_COUNT (pred2
->succs
) == 1 ? count_stmts_in_block (pred2
) : 0;
164 /* This is meant to catch cases that are likely opportunities for
165 if-conversion. Essentially we look for the case where
166 BB's predecessors are both single statement blocks where
167 the output of that statement feed the same PHI in BB. */
168 if (num_stmts_in_pred1
== 1 && num_stmts_in_pred2
== 1)
170 gimple
*stmt1
= last_and_only_stmt (pred1
);
171 gimple
*stmt2
= last_and_only_stmt (pred2
);
174 && gimple_code (stmt1
) == GIMPLE_ASSIGN
175 && gimple_code (stmt2
) == GIMPLE_ASSIGN
)
177 enum tree_code code1
= gimple_assign_rhs_code (stmt1
);
178 enum tree_code code2
= gimple_assign_rhs_code (stmt2
);
180 if (!poor_ifcvt_candidate_code (code1
)
181 && !poor_ifcvt_candidate_code (code2
))
183 tree lhs1
= gimple_assign_lhs (stmt1
);
184 tree lhs2
= gimple_assign_lhs (stmt2
);
185 gimple_stmt_iterator gsi
;
186 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
188 gimple
*phi
= gsi_stmt (gsi
);
189 if ((gimple_phi_arg_def (phi
, 0) == lhs1
190 && gimple_phi_arg_def (phi
, 1) == lhs2
)
191 || (gimple_phi_arg_def (phi
, 1) == lhs1
192 && gimple_phi_arg_def (phi
, 0) == lhs2
))
194 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
196 "Block %d appears to be a join point for "
197 "if-convertable diamond.\n",
206 /* Canonicalize the form. */
207 if (num_stmts_in_pred1
== 0 && num_stmts_in_pred2
== 1)
209 std::swap (pred1
, pred2
);
210 std::swap (num_stmts_in_pred1
, num_stmts_in_pred2
);
213 /* Another variant. This one is half-diamond. */
214 if (num_stmts_in_pred1
== 1 && num_stmts_in_pred2
== 0
215 && dominated_by_p (CDI_DOMINATORS
, pred1
, pred2
))
217 gimple
*stmt1
= last_and_only_stmt (pred1
);
219 /* The only statement in PRED1 must be an assignment that is
220 not a good candidate for if-conversion. This may need some
222 if (stmt1
&& gimple_code (stmt1
) == GIMPLE_ASSIGN
)
224 enum tree_code code1
= gimple_assign_rhs_code (stmt1
);
226 if (!poor_ifcvt_candidate_code (code1
))
228 tree lhs1
= gimple_assign_lhs (stmt1
);
229 tree rhs1
= gimple_assign_rhs1 (stmt1
);
231 gimple_stmt_iterator gsi
;
232 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
234 gimple
*phi
= gsi_stmt (gsi
);
235 if ((gimple_phi_arg_def (phi
, 0) == lhs1
236 && gimple_phi_arg_def (phi
, 1) == rhs1
)
237 || (gimple_phi_arg_def (phi
, 1) == lhs1
238 && gimple_phi_arg_def (phi
, 0) == rhs1
))
240 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
242 "Block %d appears to be a join point for "
243 "if-convertable half-diamond.\n",
252 /* If the joiner has no PHIs with useful uses there is zero chance
253 of CSE/DCE/jump-threading possibilities exposed by duplicating it. */
254 bool found_useful_phi
= false;
255 for (gphi_iterator si
= gsi_start_phis (bb
); ! gsi_end_p (si
);
258 gphi
*phi
= si
.phi ();
260 imm_use_iterator iter
;
261 FOR_EACH_IMM_USE_FAST (use_p
, iter
, gimple_phi_result (phi
))
263 gimple
*stmt
= USE_STMT (use_p
);
264 if (is_gimple_debug (stmt
))
266 /* If there's a use in the joiner this might be a CSE/DCE
268 if (gimple_bb (stmt
) == bb
)
270 found_useful_phi
= true;
273 /* If the use is on a loop header PHI and on one path the
274 value is unchanged this might expose a jump threading
276 if (gimple_code (stmt
) == GIMPLE_PHI
277 && gimple_bb (stmt
) == bb
->loop_father
->header
278 /* But for memory the PHI alone isn't good enough. */
279 && ! virtual_operand_p (gimple_phi_result (stmt
)))
281 bool found_unchanged_path
= false;
282 for (unsigned i
= 0; i
< gimple_phi_num_args (phi
); ++i
)
283 if (gimple_phi_arg_def (phi
, i
) == gimple_phi_result (stmt
))
285 found_unchanged_path
= true;
288 /* If we found an unchanged path this can only be a threading
289 opportunity if we have uses of the loop header PHI result
290 in a stmt dominating the merge block. Otherwise the
291 splitting may prevent if-conversion. */
292 if (found_unchanged_path
)
294 use_operand_p use2_p
;
295 imm_use_iterator iter2
;
296 FOR_EACH_IMM_USE_FAST (use2_p
, iter2
, gimple_phi_result (stmt
))
298 gimple
*use_stmt
= USE_STMT (use2_p
);
299 if (is_gimple_debug (use_stmt
))
301 basic_block use_bb
= gimple_bb (use_stmt
);
303 && dominated_by_p (CDI_DOMINATORS
, bb
, use_bb
))
305 if (gcond
*cond
= dyn_cast
<gcond
*> (use_stmt
))
306 if (gimple_cond_code (cond
) == EQ_EXPR
307 || gimple_cond_code (cond
) == NE_EXPR
)
308 found_useful_phi
= true;
313 if (found_useful_phi
)
317 if (found_useful_phi
)
320 /* There is one exception namely a controlling condition we can propagate
321 an equivalence from to the joiner. */
322 bool found_cprop_opportunity
= false;
323 basic_block dom
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
324 gcond
*cond
= as_a
<gcond
*> (last_stmt (dom
));
325 if (gimple_cond_code (cond
) == EQ_EXPR
326 || gimple_cond_code (cond
) == NE_EXPR
)
327 for (unsigned i
= 0; i
< 2; ++i
)
329 tree op
= gimple_op (cond
, i
);
330 if (TREE_CODE (op
) == SSA_NAME
)
333 imm_use_iterator iter
;
334 FOR_EACH_IMM_USE_FAST (use_p
, iter
, op
)
336 if (is_gimple_debug (USE_STMT (use_p
)))
338 if (gimple_bb (USE_STMT (use_p
)) == bb
)
340 found_cprop_opportunity
= true;
345 if (found_cprop_opportunity
)
349 if (! found_useful_phi
&& ! found_cprop_opportunity
)
351 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
353 "Block %d is a join that does not expose CSE/DCE/jump-thread "
354 "opportunities when duplicated.\n",
359 /* We may want something here which looks at dataflow and tries
360 to guess if duplication of BB is likely to result in simplification
361 of instructions in BB in either the original or the duplicate. */
363 /* Upper Hard limit on the number statements to copy. */
364 if (num_stmts_in_join
365 >= PARAM_VALUE (PARAM_MAX_JUMP_THREAD_DUPLICATION_STMTS
))
371 /* If the immediate dominator of the latch of the loop is
372 block with conditional branch, then the loop latch is
373 duplicated to its predecessors path preserving the SSA
376 CFG before transformation.
396 Block 8 is the latch. We're going to make copies of block 6 (9 & 10)
397 and wire things up so they look like this:
420 Blocks 9 and 10 will get merged into blocks 4 & 5 respectively which
421 enables CSE, DCE and other optimizations to occur on a larger block
427 bool changed
= false;
430 loop_optimizer_init (LOOPS_NORMAL
| LOOPS_HAVE_RECORDED_EXITS
);
431 initialize_original_copy_tables ();
432 calculate_dominance_info (CDI_DOMINATORS
);
434 FOR_EACH_LOOP (loop
, LI_FROM_INNERMOST
)
436 /* Only split paths if we are optimizing this loop for speed. */
437 if (!optimize_loop_for_speed_p (loop
))
440 /* See if there is a block that we can duplicate to split the
441 path to the loop latch. */
443 = find_block_to_duplicate_for_splitting_paths (loop
->latch
);
445 /* BB is the merge point for an IF-THEN-ELSE we want to transform.
447 Essentially we want to create a duplicate of bb and redirect the
448 first predecessor of BB to the duplicate (leaving the second
449 predecessor as is. This will split the path leading to the latch
450 re-using BB to avoid useless copying. */
451 if (bb
&& is_feasible_trace (bb
))
453 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
455 "Duplicating join block %d into predecessor paths\n",
457 basic_block pred0
= EDGE_PRED (bb
, 0)->src
;
458 if (EDGE_COUNT (pred0
->succs
) != 1)
459 pred0
= EDGE_PRED (bb
, 1)->src
;
460 transform_duplicate (pred0
, bb
);
463 /* If BB has an outgoing edge marked as IRREDUCIBLE, then
464 duplicating BB may result in an irreducible region turning
467 Long term we might want to hook this into the block
468 duplication code, but as we've seen with similar changes
469 for edge removal, that can be somewhat risky. */
470 if (EDGE_SUCC (bb
, 0)->flags
& EDGE_IRREDUCIBLE_LOOP
471 || EDGE_SUCC (bb
, 1)->flags
& EDGE_IRREDUCIBLE_LOOP
)
473 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
475 "Join block %d has EDGE_IRREDUCIBLE_LOOP set. "
476 "Scheduling loop fixups.\n",
478 loops_state_set (LOOPS_NEED_FIXUP
);
483 loop_optimizer_finalize ();
484 free_original_copy_tables ();
488 /* Main entry point for splitting paths. Returns TODO_cleanup_cfg if any
489 paths where split, otherwise return zero. */
492 execute_split_paths ()
494 /* If we don't have at least 2 real blocks and backedges in the
495 CFG, then there's no point in trying to perform path splitting. */
496 if (n_basic_blocks_for_fn (cfun
) <= NUM_FIXED_BLOCKS
+ 1
497 || !mark_dfs_back_edges ())
500 bool changed
= split_paths();
502 free_dominance_info (CDI_DOMINATORS
);
504 return changed
? TODO_cleanup_cfg
: 0;
510 return flag_split_paths
;
515 const pass_data pass_data_split_paths
=
517 GIMPLE_PASS
, /* type */
518 "split-paths", /* name */
519 OPTGROUP_NONE
, /* optinfo_flags */
520 TV_SPLIT_PATHS
, /* tv_id */
521 PROP_ssa
, /* properties_required */
522 0, /* properties_provided */
523 0, /* properties_destroyed */
524 0, /* todo_flags_start */
525 TODO_update_ssa
, /* todo_flags_finish */
528 class pass_split_paths
: public gimple_opt_pass
531 pass_split_paths (gcc::context
*ctxt
)
532 : gimple_opt_pass (pass_data_split_paths
, ctxt
)
534 /* opt_pass methods: */
535 opt_pass
* clone () { return new pass_split_paths (m_ctxt
); }
536 virtual bool gate (function
*) { return gate_split_paths (); }
537 virtual unsigned int execute (function
*) { return execute_split_paths (); }
539 }; // class pass_split_paths
544 make_pass_split_paths (gcc::context
*ctxt
)
546 return new pass_split_paths (ctxt
);