2016-05-04 Thomas Preud'homme <thomas.preudhomme@arm.com>
[official-gcc.git] / gcc / gimple-ssa-split-paths.c
blobd566f64c70be4acc52582716d5637dcf9ff513df
1 /* Support routines for Splitting Paths to loop backedges
2 Copyright (C) 2015-2016 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)
10 any later version.
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/>. */
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 "params.h"
36 /* Given LATCH, the latch block in a loop, see if the shape of the
37 path reaching LATCH is suitable for being split by duplication.
38 If so, return the block that will be duplicated into its predecessor
39 paths. Else return NULL. */
41 static basic_block
42 find_block_to_duplicate_for_splitting_paths (basic_block latch)
44 /* We should have simple latches at this point. So the latch should
45 have a single successor. This implies the predecessor of the latch
46 likely has the loop exit. And it's that predecessor we're most
47 interested in. To keep things simple, we're going to require that
48 the latch have a single predecessor too. */
49 if (single_succ_p (latch) && single_pred_p (latch))
51 basic_block bb = get_immediate_dominator (CDI_DOMINATORS, latch);
52 gcc_assert (single_pred_edge (latch)->src == bb);
54 /* If BB has been marked as not to be duplicated, then honor that
55 request. */
56 if (ignore_bb_p (bb))
57 return NULL;
59 gimple *last = gsi_stmt (gsi_last_nondebug_bb (bb));
60 /* The immediate dominator of the latch must end in a conditional. */
61 if (!last || gimple_code (last) != GIMPLE_COND)
62 return NULL;
64 /* We're hoping that BB is a join point for an IF-THEN-ELSE diamond
65 region. Verify that it is.
67 First, verify that BB has two predecessors (each arm of the
68 IF-THEN-ELSE) and two successors (the latch and exit). */
69 if (EDGE_COUNT (bb->preds) == 2 && EDGE_COUNT (bb->succs) == 2)
71 /* Now verify that BB's immediate dominator ends in a
72 conditional as well. */
73 basic_block bb_idom = get_immediate_dominator (CDI_DOMINATORS, bb);
74 gimple *last = gsi_stmt (gsi_last_nondebug_bb (bb_idom));
75 if (!last || gimple_code (last) != GIMPLE_COND)
76 return NULL;
78 /* And that BB's immediate dominator's successors are the
79 predecessors of BB. */
80 if (!find_edge (bb_idom, EDGE_PRED (bb, 0)->src)
81 || !find_edge (bb_idom, EDGE_PRED (bb, 1)->src))
82 return NULL;
84 /* And that the predecessors of BB each have a single successor. */
85 if (!single_succ_p (EDGE_PRED (bb, 0)->src)
86 || !single_succ_p (EDGE_PRED (bb, 1)->src))
87 return NULL;
89 /* So at this point we have a simple diamond for an IF-THEN-ELSE
90 construct starting at BB_IDOM, with a join point at BB. BB
91 pass control outside the loop or to the loop latch.
93 We're going to want to create two duplicates of BB, one for
94 each successor of BB_IDOM. */
95 return bb;
98 return NULL;
101 /* Return the number of non-debug statements in a block. */
102 static unsigned int
103 count_stmts_in_block (basic_block bb)
105 gimple_stmt_iterator gsi;
106 unsigned int num_stmts = 0;
108 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
110 gimple *stmt = gsi_stmt (gsi);
111 if (!is_gimple_debug (stmt))
112 num_stmts++;
114 return num_stmts;
117 /* Return TRUE if CODE represents a tree code that is not likely to
118 be easily if-convertable because it likely expands into multiple
119 insns, FALSE otherwise. */
120 static bool
121 poor_ifcvt_candidate_code (enum tree_code code)
123 return (code == MIN_EXPR
124 || code == MAX_EXPR
125 || code == ABS_EXPR
126 || code == COND_EXPR
127 || code == CALL_EXPR);
130 /* Return TRUE if BB is a reasonable block to duplicate by examining
131 its size, false otherwise. BB will always be a loop latch block.
133 Things to consider:
135 We do not want to spoil if-conversion if at all possible.
137 Most of the benefit seems to be from eliminating the unconditional
138 jump rather than CSE/DCE opportunities. So favor duplicating
139 small latches. A latch with just a conditional branch is ideal.
141 CSE/DCE opportunties crop up when statements from the predecessors
142 feed statements in the latch and allow statements in the latch to
143 simplify. */
145 static bool
146 is_feasible_trace (basic_block bb)
148 basic_block pred1 = EDGE_PRED (bb, 0)->src;
149 basic_block pred2 = EDGE_PRED (bb, 1)->src;
150 int num_stmts_in_join = count_stmts_in_block (bb);
151 int num_stmts_in_pred1 = count_stmts_in_block (pred1);
152 int num_stmts_in_pred2 = count_stmts_in_block (pred2);
154 /* This is meant to catch cases that are likely opportunities for
155 if-conversion. Essentially we look for the case where
156 BB's predecessors are both single statement blocks where
157 the output of that statement feed the same PHI in BB. */
158 if (num_stmts_in_pred1 == 1 && num_stmts_in_pred2 == 1)
160 gimple *stmt1 = last_and_only_stmt (pred1);
161 gimple *stmt2 = last_and_only_stmt (pred2);
163 if (stmt1 && stmt2
164 && gimple_code (stmt1) == GIMPLE_ASSIGN
165 && gimple_code (stmt2) == GIMPLE_ASSIGN)
167 enum tree_code code1 = gimple_assign_rhs_code (stmt1);
168 enum tree_code code2 = gimple_assign_rhs_code (stmt2);
170 if (!poor_ifcvt_candidate_code (code1)
171 && !poor_ifcvt_candidate_code (code2))
173 tree lhs1 = gimple_assign_lhs (stmt1);
174 tree lhs2 = gimple_assign_lhs (stmt2);
175 gimple_stmt_iterator gsi;
176 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
178 gimple *phi = gsi_stmt (gsi);
179 if ((gimple_phi_arg_def (phi, 0) == lhs1
180 && gimple_phi_arg_def (phi, 1) == lhs2)
181 || (gimple_phi_arg_def (phi, 1) == lhs1
182 && gimple_phi_arg_def (phi, 0) == lhs2))
184 if (dump_file && (dump_flags & TDF_DETAILS))
185 fprintf (dump_file,
186 "Block %d appears to be a join point for "
187 "if-convertable diamond.\n",
188 bb->index);
189 return false;
196 /* We may want something here which looks at dataflow and tries
197 to guess if duplication of BB is likely to result in simplification
198 of instructions in BB in either the original or the duplicate. */
200 /* Upper Hard limit on the number statements to copy. */
201 if (num_stmts_in_join
202 >= PARAM_VALUE (PARAM_MAX_JUMP_THREAD_DUPLICATION_STMTS))
203 return false;
205 return true;
208 /* If the immediate dominator of the latch of the loop is
209 block with conditional branch, then the loop latch is
210 duplicated to its predecessors path preserving the SSA
211 semantics.
213 CFG before transformation.
218 +---->3
219 | / \
220 | / \
221 | 4 5
222 | \ /
223 | \ /
225 | / \
226 | / \
227 | 8 7
228 | | |
229 ---+ E
233 Block 8 is the latch. We're going to make copies of block 6 (9 & 10)
234 and wire things up so they look like this:
239 +---->3
240 | / \
241 | / \
242 | 4 5
243 | | |
244 | | |
245 | 9 10
246 | |\ /|
247 | | \ / |
248 | | 7 |
249 | | | |
250 | | E |
251 | | |
252 | \ /
253 | \ /
254 +-----8
257 Blocks 9 and 10 will get merged into blocks 4 & 5 respectively which
258 enables CSE, DCE and other optimizations to occur on a larger block
259 of code. */
261 static bool
262 split_paths ()
264 bool changed = false;
265 loop_p loop;
267 loop_optimizer_init (LOOPS_NORMAL | LOOPS_HAVE_RECORDED_EXITS);
268 initialize_original_copy_tables ();
269 calculate_dominance_info (CDI_DOMINATORS);
271 FOR_EACH_LOOP (loop, LI_FROM_INNERMOST)
273 /* Only split paths if we are optimizing this loop for speed. */
274 if (!optimize_loop_for_speed_p (loop))
275 continue;
277 /* See if there is a block that we can duplicate to split the
278 path to the loop latch. */
279 basic_block bb
280 = find_block_to_duplicate_for_splitting_paths (loop->latch);
282 /* BB is the merge point for an IF-THEN-ELSE we want to transform.
284 Essentially we want to create a duplicate of bb and redirect the
285 first predecessor of BB to the duplicate (leaving the second
286 predecessor as is. This will split the path leading to the latch
287 re-using BB to avoid useless copying. */
288 if (bb && is_feasible_trace (bb))
290 if (dump_file && (dump_flags & TDF_DETAILS))
291 fprintf (dump_file,
292 "Duplicating join block %d into predecessor paths\n",
293 bb->index);
294 basic_block pred0 = EDGE_PRED (bb, 0)->src;
295 transform_duplicate (pred0, bb);
296 changed = true;
298 /* If BB has an outgoing edge marked as IRREDUCIBLE, then
299 duplicating BB may result in an irreducible region turning
300 into a natural loop.
302 Long term we might want to hook this into the block
303 duplication code, but as we've seen with similar changes
304 for edge removal, that can be somewhat risky. */
305 if (EDGE_SUCC (bb, 0)->flags & EDGE_IRREDUCIBLE_LOOP
306 || EDGE_SUCC (bb, 1)->flags & EDGE_IRREDUCIBLE_LOOP)
308 if (dump_file && (dump_flags & TDF_DETAILS))
309 fprintf (dump_file,
310 "Join block %d has EDGE_IRREDUCIBLE_LOOP set. "
311 "Scheduling loop fixups.\n",
312 bb->index);
313 loops_state_set (LOOPS_NEED_FIXUP);
318 loop_optimizer_finalize ();
319 free_original_copy_tables ();
320 return changed;
323 /* Main entry point for splitting paths. Returns TODO_cleanup_cfg if any
324 paths where split, otherwise return zero. */
326 static unsigned int
327 execute_split_paths ()
329 /* If we don't have at least 2 real blocks and backedges in the
330 CFG, then there's no point in trying to perform path splitting. */
331 if (n_basic_blocks_for_fn (cfun) <= NUM_FIXED_BLOCKS + 1
332 || !mark_dfs_back_edges ())
333 return 0;
335 bool changed = split_paths();
336 if (changed)
337 free_dominance_info (CDI_DOMINATORS);
339 return changed ? TODO_cleanup_cfg : 0;
342 static bool
343 gate_split_paths ()
345 return flag_split_paths;
348 namespace {
350 const pass_data pass_data_split_paths =
352 GIMPLE_PASS, /* type */
353 "split-paths", /* name */
354 OPTGROUP_NONE, /* optinfo_flags */
355 TV_SPLIT_PATHS, /* tv_id */
356 PROP_ssa, /* properties_required */
357 0, /* properties_provided */
358 0, /* properties_destroyed */
359 0, /* todo_flags_start */
360 TODO_update_ssa, /* todo_flags_finish */
363 class pass_split_paths : public gimple_opt_pass
365 public:
366 pass_split_paths (gcc::context *ctxt)
367 : gimple_opt_pass (pass_data_split_paths, ctxt)
369 /* opt_pass methods: */
370 opt_pass * clone () { return new pass_split_paths (m_ctxt); }
371 virtual bool gate (function *) { return gate_split_paths (); }
372 virtual unsigned int execute (function *) { return execute_split_paths (); }
374 }; // class pass_split_paths
376 } // anon namespace
378 gimple_opt_pass *
379 make_pass_split_paths (gcc::context *ctxt)
381 return new pass_split_paths (ctxt);