1 /* Support routines for Splitting Paths to loop backedges
2 Copyright (C) 2015 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"
30 #include "gimple-iterator.h"
34 /* Given LATCH, the latch block in a loop, see if the shape of the
35 path reaching LATCH is suitable for being split by duplication.
36 If so, return the block that will be duplicated into its predecessor
37 paths. Else return NULL. */
40 find_block_to_duplicate_for_splitting_paths (basic_block latch
)
42 /* We should have simple latches at this point. So the latch should
43 have a single successor. This implies the predecessor of the latch
44 likely has the loop exit. And it's that predecessor we're most
45 interested in. To keep things simple, we're going to require that
46 the latch have a single predecessor too. */
47 if (single_succ_p (latch
) && single_pred_p (latch
))
49 basic_block bb
= get_immediate_dominator (CDI_DOMINATORS
, latch
);
50 gcc_assert (single_pred_edge (latch
)->src
== bb
);
52 /* If BB has been marked as not to be duplicated, then honor that
57 gimple
*last
= gsi_stmt (gsi_last_nondebug_bb (bb
));
58 /* The immediate dominator of the latch must end in a conditional. */
59 if (!last
|| gimple_code (last
) != GIMPLE_COND
)
62 /* We're hoping that BB is a join point for an IF-THEN-ELSE diamond
63 region. Verify that it is.
65 First, verify that BB has two predecessors (each arm of the
66 IF-THEN-ELSE) and two successors (the latch and exit). */
67 if (EDGE_COUNT (bb
->preds
) == 2 && EDGE_COUNT (bb
->succs
) == 2)
69 /* Now verify that BB's immediate dominator ends in a
70 conditional as well. */
71 basic_block bb_idom
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
72 gimple
*last
= gsi_stmt (gsi_last_nondebug_bb (bb_idom
));
73 if (!last
|| gimple_code (last
) != GIMPLE_COND
)
76 /* And that BB's immediate dominator's successors are the
77 the predecessors of BB. */
78 if (!find_edge (bb_idom
, EDGE_PRED (bb
, 0)->src
)
79 || !find_edge (bb_idom
, EDGE_PRED (bb
, 1)->src
))
82 /* So at this point we have a simple diamond for an IF-THEN-ELSE
83 construct starting at BB_IDOM, with a join point at BB. BB
84 pass control outside the loop or to the loop latch.
86 We're going to want to create two duplicates of BB, one for
87 each successor of BB_IDOM. */
94 /* Return TRUE if BB is a reasonable block to duplicate by examining
95 its size, false otherwise. BB will always be a loop latch block.
97 Should this use the same tests as we do for jump threading? */
100 is_feasible_trace (basic_block bb
)
103 gimple_stmt_iterator gsi
;
105 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
107 gimple
*stmt
= gsi_stmt (gsi
);
108 if (!is_gimple_debug (stmt
))
112 /* We may want to limit how many statements we copy. */
119 /* If the immediate dominator of the latch of the loop is
120 block with conditional branch, then the loop latch is
121 duplicated to its predecessors path preserving the SSA
124 CFG before transformation.
144 Block 8 is the latch. We're going to make copies of block 6 (9 & 10)
145 and wire things up so they look like this:
168 Blocks 9 and 10 will get merged into blocks 4 & 5 respectively which
169 enables CSE, DCE and other optimizations to occur on a larger block
175 bool changed
= false;
178 loop_optimizer_init (LOOPS_NORMAL
| LOOPS_HAVE_RECORDED_EXITS
);
179 initialize_original_copy_tables ();
180 calculate_dominance_info (CDI_DOMINATORS
);
182 FOR_EACH_LOOP (loop
, LI_FROM_INNERMOST
)
184 /* Only split paths if we are optimizing this loop for speed. */
185 if (!optimize_loop_for_speed_p (loop
))
188 /* See if there is a block that we can duplicate to split the
189 path to the loop latch. */
191 = find_block_to_duplicate_for_splitting_paths (loop
->latch
);
193 /* BB is the merge point for an IF-THEN-ELSE we want to transform.
195 Essentially we want to create two duplicates of BB and append
196 a duplicate to the THEN and ELSE clauses. This will split the
197 path leading to the latch. BB will be unreachable and removed. */
198 if (bb
&& is_feasible_trace (bb
))
200 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
202 "Duplicating join block %d into predecessor paths\n",
204 basic_block pred0
= EDGE_PRED (bb
, 0)->src
;
205 basic_block pred1
= EDGE_PRED (bb
, 1)->src
;
206 transform_duplicate (pred0
, bb
);
207 transform_duplicate (pred1
, bb
);
212 loop_optimizer_finalize ();
213 free_original_copy_tables ();
217 /* Main entry point for splitting paths. Returns TODO_cleanup_cfg if any
218 paths where split, otherwise return zero. */
221 execute_split_paths ()
223 /* If we don't have at least 2 real blocks and backedges in the
224 CFG, then there's no point in trying to perform path splitting. */
225 if (n_basic_blocks_for_fn (cfun
) <= NUM_FIXED_BLOCKS
+ 1
226 || !mark_dfs_back_edges ())
229 bool changed
= split_paths();
231 free_dominance_info (CDI_DOMINATORS
);
233 return changed
? TODO_cleanup_cfg
: 0;
239 return flag_split_paths
;
244 const pass_data pass_data_split_paths
=
246 GIMPLE_PASS
, /* type */
247 "split-paths", /* name */
248 OPTGROUP_NONE
, /* optinfo_flags */
249 TV_SPLIT_PATHS
, /* tv_id */
250 PROP_ssa
, /* properties_required */
251 0, /* properties_provided */
252 0, /* properties_destroyed */
253 0, /* todo_flags_start */
254 TODO_update_ssa
, /* todo_flags_finish */
257 class pass_split_paths
: public gimple_opt_pass
260 pass_split_paths (gcc::context
*ctxt
)
261 : gimple_opt_pass (pass_data_split_paths
, ctxt
)
263 /* opt_pass methods: */
264 opt_pass
* clone () { return new pass_split_paths (m_ctxt
); }
265 virtual bool gate (function
*) { return gate_split_paths (); }
266 virtual unsigned int execute (function
*) { return execute_split_paths (); }
268 }; // class pass_split_paths
273 make_pass_split_paths (gcc::context
*ctxt
)
275 return new pass_split_paths (ctxt
);