annotate gcc/gimple-ssa-split-paths.c @ 120:f93fa5091070

fix conv1.c
author mir3636
date Thu, 08 Mar 2018 14:53:42 +0900
parents 04ced10e8804
children 84e7813d76e9
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
111
kono
parents:
diff changeset
1 /* Support routines for Splitting Paths to loop backedges
kono
parents:
diff changeset
2 Copyright (C) 2015-2017 Free Software Foundation, Inc.
kono
parents:
diff changeset
3 Contributed by Ajit Kumar Agarwal <ajitkum@xilinx.com>.
kono
parents:
diff changeset
4
kono
parents:
diff changeset
5 This file is part of GCC.
kono
parents:
diff changeset
6
kono
parents:
diff changeset
7 GCC is free software; you can redistribute it and/or modify
kono
parents:
diff changeset
8 it under the terms of the GNU General Public License as published by
kono
parents:
diff changeset
9 the Free Software Foundation; either version 3, or (at your option)
kono
parents:
diff changeset
10 any later version.
kono
parents:
diff changeset
11
kono
parents:
diff changeset
12 GCC is distributed in the hope that it will be useful,
kono
parents:
diff changeset
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
kono
parents:
diff changeset
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
kono
parents:
diff changeset
15 GNU General Public License for more details.
kono
parents:
diff changeset
16
kono
parents:
diff changeset
17 You should have received a copy of the GNU General Public License
kono
parents:
diff changeset
18 along with GCC; see the file COPYING3. If not see
kono
parents:
diff changeset
19 <http://www.gnu.org/licenses/>. */
kono
parents:
diff changeset
20
kono
parents:
diff changeset
21 #include "config.h"
kono
parents:
diff changeset
22 #include "system.h"
kono
parents:
diff changeset
23 #include "coretypes.h"
kono
parents:
diff changeset
24 #include "backend.h"
kono
parents:
diff changeset
25 #include "tree.h"
kono
parents:
diff changeset
26 #include "gimple.h"
kono
parents:
diff changeset
27 #include "tree-pass.h"
kono
parents:
diff changeset
28 #include "tree-cfg.h"
kono
parents:
diff changeset
29 #include "cfganal.h"
kono
parents:
diff changeset
30 #include "cfgloop.h"
kono
parents:
diff changeset
31 #include "gimple-iterator.h"
kono
parents:
diff changeset
32 #include "tracer.h"
kono
parents:
diff changeset
33 #include "predict.h"
kono
parents:
diff changeset
34 #include "params.h"
kono
parents:
diff changeset
35 #include "gimple-ssa.h"
kono
parents:
diff changeset
36 #include "tree-phinodes.h"
kono
parents:
diff changeset
37 #include "ssa-iterators.h"
kono
parents:
diff changeset
38
kono
parents:
diff changeset
39 /* Given LATCH, the latch block in a loop, see if the shape of the
kono
parents:
diff changeset
40 path reaching LATCH is suitable for being split by duplication.
kono
parents:
diff changeset
41 If so, return the block that will be duplicated into its predecessor
kono
parents:
diff changeset
42 paths. Else return NULL. */
kono
parents:
diff changeset
43
kono
parents:
diff changeset
44 static basic_block
kono
parents:
diff changeset
45 find_block_to_duplicate_for_splitting_paths (basic_block latch)
kono
parents:
diff changeset
46 {
kono
parents:
diff changeset
47 /* We should have simple latches at this point. So the latch should
kono
parents:
diff changeset
48 have a single successor. This implies the predecessor of the latch
kono
parents:
diff changeset
49 likely has the loop exit. And it's that predecessor we're most
kono
parents:
diff changeset
50 interested in. To keep things simple, we're going to require that
kono
parents:
diff changeset
51 the latch have a single predecessor too. */
kono
parents:
diff changeset
52 if (single_succ_p (latch) && single_pred_p (latch))
kono
parents:
diff changeset
53 {
kono
parents:
diff changeset
54 basic_block bb = get_immediate_dominator (CDI_DOMINATORS, latch);
kono
parents:
diff changeset
55 gcc_assert (single_pred_edge (latch)->src == bb);
kono
parents:
diff changeset
56
kono
parents:
diff changeset
57 /* If BB has been marked as not to be duplicated, then honor that
kono
parents:
diff changeset
58 request. */
kono
parents:
diff changeset
59 if (ignore_bb_p (bb))
kono
parents:
diff changeset
60 return NULL;
kono
parents:
diff changeset
61
kono
parents:
diff changeset
62 gimple *last = gsi_stmt (gsi_last_nondebug_bb (bb));
kono
parents:
diff changeset
63 /* The immediate dominator of the latch must end in a conditional. */
kono
parents:
diff changeset
64 if (!last || gimple_code (last) != GIMPLE_COND)
kono
parents:
diff changeset
65 return NULL;
kono
parents:
diff changeset
66
kono
parents:
diff changeset
67 /* We're hoping that BB is a join point for an IF-THEN-ELSE diamond
kono
parents:
diff changeset
68 region. Verify that it is.
kono
parents:
diff changeset
69
kono
parents:
diff changeset
70 First, verify that BB has two predecessors (each arm of the
kono
parents:
diff changeset
71 IF-THEN-ELSE) and two successors (the latch and exit). */
kono
parents:
diff changeset
72 if (EDGE_COUNT (bb->preds) == 2 && EDGE_COUNT (bb->succs) == 2)
kono
parents:
diff changeset
73 {
kono
parents:
diff changeset
74 /* Now verify that BB's immediate dominator ends in a
kono
parents:
diff changeset
75 conditional as well. */
kono
parents:
diff changeset
76 basic_block bb_idom = get_immediate_dominator (CDI_DOMINATORS, bb);
kono
parents:
diff changeset
77 gimple *last = gsi_stmt (gsi_last_nondebug_bb (bb_idom));
kono
parents:
diff changeset
78 if (!last || gimple_code (last) != GIMPLE_COND)
kono
parents:
diff changeset
79 return NULL;
kono
parents:
diff changeset
80
kono
parents:
diff changeset
81 /* And that BB's immediate dominator's successors are the
kono
parents:
diff changeset
82 predecessors of BB or BB itself. */
kono
parents:
diff changeset
83 if (!(EDGE_PRED (bb, 0)->src == bb_idom
kono
parents:
diff changeset
84 || find_edge (bb_idom, EDGE_PRED (bb, 0)->src))
kono
parents:
diff changeset
85 || !(EDGE_PRED (bb, 1)->src == bb_idom
kono
parents:
diff changeset
86 || find_edge (bb_idom, EDGE_PRED (bb, 1)->src)))
kono
parents:
diff changeset
87 return NULL;
kono
parents:
diff changeset
88
kono
parents:
diff changeset
89 /* And that the predecessors of BB each have a single successor
kono
parents:
diff changeset
90 or are BB's immediate domiator itself. */
kono
parents:
diff changeset
91 if (!(EDGE_PRED (bb, 0)->src == bb_idom
kono
parents:
diff changeset
92 || single_succ_p (EDGE_PRED (bb, 0)->src))
kono
parents:
diff changeset
93 || !(EDGE_PRED (bb, 1)->src == bb_idom
kono
parents:
diff changeset
94 || single_succ_p (EDGE_PRED (bb, 1)->src)))
kono
parents:
diff changeset
95 return NULL;
kono
parents:
diff changeset
96
kono
parents:
diff changeset
97 /* So at this point we have a simple diamond for an IF-THEN-ELSE
kono
parents:
diff changeset
98 construct starting at BB_IDOM, with a join point at BB. BB
kono
parents:
diff changeset
99 pass control outside the loop or to the loop latch.
kono
parents:
diff changeset
100
kono
parents:
diff changeset
101 We're going to want to create two duplicates of BB, one for
kono
parents:
diff changeset
102 each successor of BB_IDOM. */
kono
parents:
diff changeset
103 return bb;
kono
parents:
diff changeset
104 }
kono
parents:
diff changeset
105 }
kono
parents:
diff changeset
106 return NULL;
kono
parents:
diff changeset
107 }
kono
parents:
diff changeset
108
kono
parents:
diff changeset
109 /* Return the number of non-debug statements in a block. */
kono
parents:
diff changeset
110 static unsigned int
kono
parents:
diff changeset
111 count_stmts_in_block (basic_block bb)
kono
parents:
diff changeset
112 {
kono
parents:
diff changeset
113 gimple_stmt_iterator gsi;
kono
parents:
diff changeset
114 unsigned int num_stmts = 0;
kono
parents:
diff changeset
115
kono
parents:
diff changeset
116 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
kono
parents:
diff changeset
117 {
kono
parents:
diff changeset
118 gimple *stmt = gsi_stmt (gsi);
kono
parents:
diff changeset
119 if (!is_gimple_debug (stmt))
kono
parents:
diff changeset
120 num_stmts++;
kono
parents:
diff changeset
121 }
kono
parents:
diff changeset
122 return num_stmts;
kono
parents:
diff changeset
123 }
kono
parents:
diff changeset
124
kono
parents:
diff changeset
125 /* Return TRUE if CODE represents a tree code that is not likely to
kono
parents:
diff changeset
126 be easily if-convertable because it likely expands into multiple
kono
parents:
diff changeset
127 insns, FALSE otherwise. */
kono
parents:
diff changeset
128 static bool
kono
parents:
diff changeset
129 poor_ifcvt_candidate_code (enum tree_code code)
kono
parents:
diff changeset
130 {
kono
parents:
diff changeset
131 return (code == MIN_EXPR
kono
parents:
diff changeset
132 || code == MAX_EXPR
kono
parents:
diff changeset
133 || code == ABS_EXPR
kono
parents:
diff changeset
134 || code == COND_EXPR
kono
parents:
diff changeset
135 || code == CALL_EXPR);
kono
parents:
diff changeset
136 }
kono
parents:
diff changeset
137
kono
parents:
diff changeset
138 /* Return TRUE if BB is a reasonable block to duplicate by examining
kono
parents:
diff changeset
139 its size, false otherwise. BB will always be a loop latch block.
kono
parents:
diff changeset
140
kono
parents:
diff changeset
141 Things to consider:
kono
parents:
diff changeset
142
kono
parents:
diff changeset
143 We do not want to spoil if-conversion if at all possible.
kono
parents:
diff changeset
144
kono
parents:
diff changeset
145 Most of the benefit seems to be from eliminating the unconditional
kono
parents:
diff changeset
146 jump rather than CSE/DCE opportunities. So favor duplicating
kono
parents:
diff changeset
147 small latches. A latch with just a conditional branch is ideal.
kono
parents:
diff changeset
148
kono
parents:
diff changeset
149 CSE/DCE opportunties crop up when statements from the predecessors
kono
parents:
diff changeset
150 feed statements in the latch and allow statements in the latch to
kono
parents:
diff changeset
151 simplify. */
kono
parents:
diff changeset
152
kono
parents:
diff changeset
153 static bool
kono
parents:
diff changeset
154 is_feasible_trace (basic_block bb)
kono
parents:
diff changeset
155 {
kono
parents:
diff changeset
156 basic_block pred1 = EDGE_PRED (bb, 0)->src;
kono
parents:
diff changeset
157 basic_block pred2 = EDGE_PRED (bb, 1)->src;
kono
parents:
diff changeset
158 int num_stmts_in_join = count_stmts_in_block (bb);
kono
parents:
diff changeset
159 int num_stmts_in_pred1
kono
parents:
diff changeset
160 = EDGE_COUNT (pred1->succs) == 1 ? count_stmts_in_block (pred1) : 0;
kono
parents:
diff changeset
161 int num_stmts_in_pred2
kono
parents:
diff changeset
162 = EDGE_COUNT (pred2->succs) == 1 ? count_stmts_in_block (pred2) : 0;
kono
parents:
diff changeset
163
kono
parents:
diff changeset
164 /* This is meant to catch cases that are likely opportunities for
kono
parents:
diff changeset
165 if-conversion. Essentially we look for the case where
kono
parents:
diff changeset
166 BB's predecessors are both single statement blocks where
kono
parents:
diff changeset
167 the output of that statement feed the same PHI in BB. */
kono
parents:
diff changeset
168 if (num_stmts_in_pred1 == 1 && num_stmts_in_pred2 == 1)
kono
parents:
diff changeset
169 {
kono
parents:
diff changeset
170 gimple *stmt1 = last_and_only_stmt (pred1);
kono
parents:
diff changeset
171 gimple *stmt2 = last_and_only_stmt (pred2);
kono
parents:
diff changeset
172
kono
parents:
diff changeset
173 if (stmt1 && stmt2
kono
parents:
diff changeset
174 && gimple_code (stmt1) == GIMPLE_ASSIGN
kono
parents:
diff changeset
175 && gimple_code (stmt2) == GIMPLE_ASSIGN)
kono
parents:
diff changeset
176 {
kono
parents:
diff changeset
177 enum tree_code code1 = gimple_assign_rhs_code (stmt1);
kono
parents:
diff changeset
178 enum tree_code code2 = gimple_assign_rhs_code (stmt2);
kono
parents:
diff changeset
179
kono
parents:
diff changeset
180 if (!poor_ifcvt_candidate_code (code1)
kono
parents:
diff changeset
181 && !poor_ifcvt_candidate_code (code2))
kono
parents:
diff changeset
182 {
kono
parents:
diff changeset
183 tree lhs1 = gimple_assign_lhs (stmt1);
kono
parents:
diff changeset
184 tree lhs2 = gimple_assign_lhs (stmt2);
kono
parents:
diff changeset
185 gimple_stmt_iterator gsi;
kono
parents:
diff changeset
186 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
kono
parents:
diff changeset
187 {
kono
parents:
diff changeset
188 gimple *phi = gsi_stmt (gsi);
kono
parents:
diff changeset
189 if ((gimple_phi_arg_def (phi, 0) == lhs1
kono
parents:
diff changeset
190 && gimple_phi_arg_def (phi, 1) == lhs2)
kono
parents:
diff changeset
191 || (gimple_phi_arg_def (phi, 1) == lhs1
kono
parents:
diff changeset
192 && gimple_phi_arg_def (phi, 0) == lhs2))
kono
parents:
diff changeset
193 {
kono
parents:
diff changeset
194 if (dump_file && (dump_flags & TDF_DETAILS))
kono
parents:
diff changeset
195 fprintf (dump_file,
kono
parents:
diff changeset
196 "Block %d appears to be a join point for "
kono
parents:
diff changeset
197 "if-convertable diamond.\n",
kono
parents:
diff changeset
198 bb->index);
kono
parents:
diff changeset
199 return false;
kono
parents:
diff changeset
200 }
kono
parents:
diff changeset
201 }
kono
parents:
diff changeset
202 }
kono
parents:
diff changeset
203 }
kono
parents:
diff changeset
204 }
kono
parents:
diff changeset
205
kono
parents:
diff changeset
206 /* If the joiner has no PHIs with useful uses there is zero chance
kono
parents:
diff changeset
207 of CSE/DCE/jump-threading possibilities exposed by duplicating it. */
kono
parents:
diff changeset
208 bool found_useful_phi = false;
kono
parents:
diff changeset
209 for (gphi_iterator si = gsi_start_phis (bb); ! gsi_end_p (si);
kono
parents:
diff changeset
210 gsi_next (&si))
kono
parents:
diff changeset
211 {
kono
parents:
diff changeset
212 gphi *phi = si.phi ();
kono
parents:
diff changeset
213 use_operand_p use_p;
kono
parents:
diff changeset
214 imm_use_iterator iter;
kono
parents:
diff changeset
215 FOR_EACH_IMM_USE_FAST (use_p, iter, gimple_phi_result (phi))
kono
parents:
diff changeset
216 {
kono
parents:
diff changeset
217 gimple *stmt = USE_STMT (use_p);
kono
parents:
diff changeset
218 if (is_gimple_debug (stmt))
kono
parents:
diff changeset
219 continue;
kono
parents:
diff changeset
220 /* If there's a use in the joiner this might be a CSE/DCE
kono
parents:
diff changeset
221 opportunity. */
kono
parents:
diff changeset
222 if (gimple_bb (stmt) == bb)
kono
parents:
diff changeset
223 {
kono
parents:
diff changeset
224 found_useful_phi = true;
kono
parents:
diff changeset
225 break;
kono
parents:
diff changeset
226 }
kono
parents:
diff changeset
227 /* If the use is on a loop header PHI and on one path the
kono
parents:
diff changeset
228 value is unchanged this might expose a jump threading
kono
parents:
diff changeset
229 opportunity. */
kono
parents:
diff changeset
230 if (gimple_code (stmt) == GIMPLE_PHI
kono
parents:
diff changeset
231 && gimple_bb (stmt) == bb->loop_father->header
kono
parents:
diff changeset
232 /* But for memory the PHI alone isn't good enough. */
kono
parents:
diff changeset
233 && ! virtual_operand_p (gimple_phi_result (stmt)))
kono
parents:
diff changeset
234 {
kono
parents:
diff changeset
235 bool found_unchanged_path = false;
kono
parents:
diff changeset
236 for (unsigned i = 0; i < gimple_phi_num_args (phi); ++i)
kono
parents:
diff changeset
237 if (gimple_phi_arg_def (phi, i) == gimple_phi_result (stmt))
kono
parents:
diff changeset
238 {
kono
parents:
diff changeset
239 found_unchanged_path = true;
kono
parents:
diff changeset
240 break;
kono
parents:
diff changeset
241 }
kono
parents:
diff changeset
242 /* If we found an unchanged path this can only be a threading
kono
parents:
diff changeset
243 opportunity if we have uses of the loop header PHI result
kono
parents:
diff changeset
244 in a stmt dominating the merge block. Otherwise the
kono
parents:
diff changeset
245 splitting may prevent if-conversion. */
kono
parents:
diff changeset
246 if (found_unchanged_path)
kono
parents:
diff changeset
247 {
kono
parents:
diff changeset
248 use_operand_p use2_p;
kono
parents:
diff changeset
249 imm_use_iterator iter2;
kono
parents:
diff changeset
250 FOR_EACH_IMM_USE_FAST (use2_p, iter2, gimple_phi_result (stmt))
kono
parents:
diff changeset
251 {
kono
parents:
diff changeset
252 gimple *use_stmt = USE_STMT (use2_p);
kono
parents:
diff changeset
253 if (is_gimple_debug (use_stmt))
kono
parents:
diff changeset
254 continue;
kono
parents:
diff changeset
255 basic_block use_bb = gimple_bb (use_stmt);
kono
parents:
diff changeset
256 if (use_bb != bb
kono
parents:
diff changeset
257 && dominated_by_p (CDI_DOMINATORS, bb, use_bb))
kono
parents:
diff changeset
258 {
kono
parents:
diff changeset
259 if (gcond *cond = dyn_cast <gcond *> (use_stmt))
kono
parents:
diff changeset
260 if (gimple_cond_code (cond) == EQ_EXPR
kono
parents:
diff changeset
261 || gimple_cond_code (cond) == NE_EXPR)
kono
parents:
diff changeset
262 found_useful_phi = true;
kono
parents:
diff changeset
263 break;
kono
parents:
diff changeset
264 }
kono
parents:
diff changeset
265 }
kono
parents:
diff changeset
266 }
kono
parents:
diff changeset
267 if (found_useful_phi)
kono
parents:
diff changeset
268 break;
kono
parents:
diff changeset
269 }
kono
parents:
diff changeset
270 }
kono
parents:
diff changeset
271 if (found_useful_phi)
kono
parents:
diff changeset
272 break;
kono
parents:
diff changeset
273 }
kono
parents:
diff changeset
274 /* There is one exception namely a controlling condition we can propagate
kono
parents:
diff changeset
275 an equivalence from to the joiner. */
kono
parents:
diff changeset
276 bool found_cprop_opportunity = false;
kono
parents:
diff changeset
277 basic_block dom = get_immediate_dominator (CDI_DOMINATORS, bb);
kono
parents:
diff changeset
278 gcond *cond = as_a <gcond *> (last_stmt (dom));
kono
parents:
diff changeset
279 if (gimple_cond_code (cond) == EQ_EXPR
kono
parents:
diff changeset
280 || gimple_cond_code (cond) == NE_EXPR)
kono
parents:
diff changeset
281 for (unsigned i = 0; i < 2; ++i)
kono
parents:
diff changeset
282 {
kono
parents:
diff changeset
283 tree op = gimple_op (cond, i);
kono
parents:
diff changeset
284 if (TREE_CODE (op) == SSA_NAME)
kono
parents:
diff changeset
285 {
kono
parents:
diff changeset
286 use_operand_p use_p;
kono
parents:
diff changeset
287 imm_use_iterator iter;
kono
parents:
diff changeset
288 FOR_EACH_IMM_USE_FAST (use_p, iter, op)
kono
parents:
diff changeset
289 {
kono
parents:
diff changeset
290 if (is_gimple_debug (USE_STMT (use_p)))
kono
parents:
diff changeset
291 continue;
kono
parents:
diff changeset
292 if (gimple_bb (USE_STMT (use_p)) == bb)
kono
parents:
diff changeset
293 {
kono
parents:
diff changeset
294 found_cprop_opportunity = true;
kono
parents:
diff changeset
295 break;
kono
parents:
diff changeset
296 }
kono
parents:
diff changeset
297 }
kono
parents:
diff changeset
298 }
kono
parents:
diff changeset
299 if (found_cprop_opportunity)
kono
parents:
diff changeset
300 break;
kono
parents:
diff changeset
301 }
kono
parents:
diff changeset
302
kono
parents:
diff changeset
303 if (! found_useful_phi && ! found_cprop_opportunity)
kono
parents:
diff changeset
304 {
kono
parents:
diff changeset
305 if (dump_file && (dump_flags & TDF_DETAILS))
kono
parents:
diff changeset
306 fprintf (dump_file,
kono
parents:
diff changeset
307 "Block %d is a join that does not expose CSE/DCE/jump-thread "
kono
parents:
diff changeset
308 "opportunities when duplicated.\n",
kono
parents:
diff changeset
309 bb->index);
kono
parents:
diff changeset
310 return false;
kono
parents:
diff changeset
311 }
kono
parents:
diff changeset
312
kono
parents:
diff changeset
313 /* We may want something here which looks at dataflow and tries
kono
parents:
diff changeset
314 to guess if duplication of BB is likely to result in simplification
kono
parents:
diff changeset
315 of instructions in BB in either the original or the duplicate. */
kono
parents:
diff changeset
316
kono
parents:
diff changeset
317 /* Upper Hard limit on the number statements to copy. */
kono
parents:
diff changeset
318 if (num_stmts_in_join
kono
parents:
diff changeset
319 >= PARAM_VALUE (PARAM_MAX_JUMP_THREAD_DUPLICATION_STMTS))
kono
parents:
diff changeset
320 return false;
kono
parents:
diff changeset
321
kono
parents:
diff changeset
322 return true;
kono
parents:
diff changeset
323 }
kono
parents:
diff changeset
324
kono
parents:
diff changeset
325 /* If the immediate dominator of the latch of the loop is
kono
parents:
diff changeset
326 block with conditional branch, then the loop latch is
kono
parents:
diff changeset
327 duplicated to its predecessors path preserving the SSA
kono
parents:
diff changeset
328 semantics.
kono
parents:
diff changeset
329
kono
parents:
diff changeset
330 CFG before transformation.
kono
parents:
diff changeset
331
kono
parents:
diff changeset
332 2
kono
parents:
diff changeset
333 |
kono
parents:
diff changeset
334 |
kono
parents:
diff changeset
335 +---->3
kono
parents:
diff changeset
336 | / \
kono
parents:
diff changeset
337 | / \
kono
parents:
diff changeset
338 | 4 5
kono
parents:
diff changeset
339 | \ /
kono
parents:
diff changeset
340 | \ /
kono
parents:
diff changeset
341 | 6
kono
parents:
diff changeset
342 | / \
kono
parents:
diff changeset
343 | / \
kono
parents:
diff changeset
344 | 8 7
kono
parents:
diff changeset
345 | | |
kono
parents:
diff changeset
346 ---+ E
kono
parents:
diff changeset
347
kono
parents:
diff changeset
348
kono
parents:
diff changeset
349
kono
parents:
diff changeset
350 Block 8 is the latch. We're going to make copies of block 6 (9 & 10)
kono
parents:
diff changeset
351 and wire things up so they look like this:
kono
parents:
diff changeset
352
kono
parents:
diff changeset
353 2
kono
parents:
diff changeset
354 |
kono
parents:
diff changeset
355 |
kono
parents:
diff changeset
356 +---->3
kono
parents:
diff changeset
357 | / \
kono
parents:
diff changeset
358 | / \
kono
parents:
diff changeset
359 | 4 5
kono
parents:
diff changeset
360 | | |
kono
parents:
diff changeset
361 | | |
kono
parents:
diff changeset
362 | 9 10
kono
parents:
diff changeset
363 | |\ /|
kono
parents:
diff changeset
364 | | \ / |
kono
parents:
diff changeset
365 | | 7 |
kono
parents:
diff changeset
366 | | | |
kono
parents:
diff changeset
367 | | E |
kono
parents:
diff changeset
368 | | |
kono
parents:
diff changeset
369 | \ /
kono
parents:
diff changeset
370 | \ /
kono
parents:
diff changeset
371 +-----8
kono
parents:
diff changeset
372
kono
parents:
diff changeset
373
kono
parents:
diff changeset
374 Blocks 9 and 10 will get merged into blocks 4 & 5 respectively which
kono
parents:
diff changeset
375 enables CSE, DCE and other optimizations to occur on a larger block
kono
parents:
diff changeset
376 of code. */
kono
parents:
diff changeset
377
kono
parents:
diff changeset
378 static bool
kono
parents:
diff changeset
379 split_paths ()
kono
parents:
diff changeset
380 {
kono
parents:
diff changeset
381 bool changed = false;
kono
parents:
diff changeset
382 loop_p loop;
kono
parents:
diff changeset
383
kono
parents:
diff changeset
384 loop_optimizer_init (LOOPS_NORMAL | LOOPS_HAVE_RECORDED_EXITS);
kono
parents:
diff changeset
385 initialize_original_copy_tables ();
kono
parents:
diff changeset
386 calculate_dominance_info (CDI_DOMINATORS);
kono
parents:
diff changeset
387
kono
parents:
diff changeset
388 FOR_EACH_LOOP (loop, LI_FROM_INNERMOST)
kono
parents:
diff changeset
389 {
kono
parents:
diff changeset
390 /* Only split paths if we are optimizing this loop for speed. */
kono
parents:
diff changeset
391 if (!optimize_loop_for_speed_p (loop))
kono
parents:
diff changeset
392 continue;
kono
parents:
diff changeset
393
kono
parents:
diff changeset
394 /* See if there is a block that we can duplicate to split the
kono
parents:
diff changeset
395 path to the loop latch. */
kono
parents:
diff changeset
396 basic_block bb
kono
parents:
diff changeset
397 = find_block_to_duplicate_for_splitting_paths (loop->latch);
kono
parents:
diff changeset
398
kono
parents:
diff changeset
399 /* BB is the merge point for an IF-THEN-ELSE we want to transform.
kono
parents:
diff changeset
400
kono
parents:
diff changeset
401 Essentially we want to create a duplicate of bb and redirect the
kono
parents:
diff changeset
402 first predecessor of BB to the duplicate (leaving the second
kono
parents:
diff changeset
403 predecessor as is. This will split the path leading to the latch
kono
parents:
diff changeset
404 re-using BB to avoid useless copying. */
kono
parents:
diff changeset
405 if (bb && is_feasible_trace (bb))
kono
parents:
diff changeset
406 {
kono
parents:
diff changeset
407 if (dump_file && (dump_flags & TDF_DETAILS))
kono
parents:
diff changeset
408 fprintf (dump_file,
kono
parents:
diff changeset
409 "Duplicating join block %d into predecessor paths\n",
kono
parents:
diff changeset
410 bb->index);
kono
parents:
diff changeset
411 basic_block pred0 = EDGE_PRED (bb, 0)->src;
kono
parents:
diff changeset
412 if (EDGE_COUNT (pred0->succs) != 1)
kono
parents:
diff changeset
413 pred0 = EDGE_PRED (bb, 1)->src;
kono
parents:
diff changeset
414 transform_duplicate (pred0, bb);
kono
parents:
diff changeset
415 changed = true;
kono
parents:
diff changeset
416
kono
parents:
diff changeset
417 /* If BB has an outgoing edge marked as IRREDUCIBLE, then
kono
parents:
diff changeset
418 duplicating BB may result in an irreducible region turning
kono
parents:
diff changeset
419 into a natural loop.
kono
parents:
diff changeset
420
kono
parents:
diff changeset
421 Long term we might want to hook this into the block
kono
parents:
diff changeset
422 duplication code, but as we've seen with similar changes
kono
parents:
diff changeset
423 for edge removal, that can be somewhat risky. */
kono
parents:
diff changeset
424 if (EDGE_SUCC (bb, 0)->flags & EDGE_IRREDUCIBLE_LOOP
kono
parents:
diff changeset
425 || EDGE_SUCC (bb, 1)->flags & EDGE_IRREDUCIBLE_LOOP)
kono
parents:
diff changeset
426 {
kono
parents:
diff changeset
427 if (dump_file && (dump_flags & TDF_DETAILS))
kono
parents:
diff changeset
428 fprintf (dump_file,
kono
parents:
diff changeset
429 "Join block %d has EDGE_IRREDUCIBLE_LOOP set. "
kono
parents:
diff changeset
430 "Scheduling loop fixups.\n",
kono
parents:
diff changeset
431 bb->index);
kono
parents:
diff changeset
432 loops_state_set (LOOPS_NEED_FIXUP);
kono
parents:
diff changeset
433 }
kono
parents:
diff changeset
434 }
kono
parents:
diff changeset
435 }
kono
parents:
diff changeset
436
kono
parents:
diff changeset
437 loop_optimizer_finalize ();
kono
parents:
diff changeset
438 free_original_copy_tables ();
kono
parents:
diff changeset
439 return changed;
kono
parents:
diff changeset
440 }
kono
parents:
diff changeset
441
kono
parents:
diff changeset
442 /* Main entry point for splitting paths. Returns TODO_cleanup_cfg if any
kono
parents:
diff changeset
443 paths where split, otherwise return zero. */
kono
parents:
diff changeset
444
kono
parents:
diff changeset
445 static unsigned int
kono
parents:
diff changeset
446 execute_split_paths ()
kono
parents:
diff changeset
447 {
kono
parents:
diff changeset
448 /* If we don't have at least 2 real blocks and backedges in the
kono
parents:
diff changeset
449 CFG, then there's no point in trying to perform path splitting. */
kono
parents:
diff changeset
450 if (n_basic_blocks_for_fn (cfun) <= NUM_FIXED_BLOCKS + 1
kono
parents:
diff changeset
451 || !mark_dfs_back_edges ())
kono
parents:
diff changeset
452 return 0;
kono
parents:
diff changeset
453
kono
parents:
diff changeset
454 bool changed = split_paths();
kono
parents:
diff changeset
455 if (changed)
kono
parents:
diff changeset
456 free_dominance_info (CDI_DOMINATORS);
kono
parents:
diff changeset
457
kono
parents:
diff changeset
458 return changed ? TODO_cleanup_cfg : 0;
kono
parents:
diff changeset
459 }
kono
parents:
diff changeset
460
kono
parents:
diff changeset
461 static bool
kono
parents:
diff changeset
462 gate_split_paths ()
kono
parents:
diff changeset
463 {
kono
parents:
diff changeset
464 return flag_split_paths;
kono
parents:
diff changeset
465 }
kono
parents:
diff changeset
466
kono
parents:
diff changeset
467 namespace {
kono
parents:
diff changeset
468
kono
parents:
diff changeset
469 const pass_data pass_data_split_paths =
kono
parents:
diff changeset
470 {
kono
parents:
diff changeset
471 GIMPLE_PASS, /* type */
kono
parents:
diff changeset
472 "split-paths", /* name */
kono
parents:
diff changeset
473 OPTGROUP_NONE, /* optinfo_flags */
kono
parents:
diff changeset
474 TV_SPLIT_PATHS, /* tv_id */
kono
parents:
diff changeset
475 PROP_ssa, /* properties_required */
kono
parents:
diff changeset
476 0, /* properties_provided */
kono
parents:
diff changeset
477 0, /* properties_destroyed */
kono
parents:
diff changeset
478 0, /* todo_flags_start */
kono
parents:
diff changeset
479 TODO_update_ssa, /* todo_flags_finish */
kono
parents:
diff changeset
480 };
kono
parents:
diff changeset
481
kono
parents:
diff changeset
482 class pass_split_paths : public gimple_opt_pass
kono
parents:
diff changeset
483 {
kono
parents:
diff changeset
484 public:
kono
parents:
diff changeset
485 pass_split_paths (gcc::context *ctxt)
kono
parents:
diff changeset
486 : gimple_opt_pass (pass_data_split_paths, ctxt)
kono
parents:
diff changeset
487 {}
kono
parents:
diff changeset
488 /* opt_pass methods: */
kono
parents:
diff changeset
489 opt_pass * clone () { return new pass_split_paths (m_ctxt); }
kono
parents:
diff changeset
490 virtual bool gate (function *) { return gate_split_paths (); }
kono
parents:
diff changeset
491 virtual unsigned int execute (function *) { return execute_split_paths (); }
kono
parents:
diff changeset
492
kono
parents:
diff changeset
493 }; // class pass_split_paths
kono
parents:
diff changeset
494
kono
parents:
diff changeset
495 } // anon namespace
kono
parents:
diff changeset
496
kono
parents:
diff changeset
497 gimple_opt_pass *
kono
parents:
diff changeset
498 make_pass_split_paths (gcc::context *ctxt)
kono
parents:
diff changeset
499 {
kono
parents:
diff changeset
500 return new pass_split_paths (ctxt);
kono
parents:
diff changeset
501 }