]>
Commit | Line | Data |
---|---|---|
e12d0591 | 1 | /* Loop unswitching. |
711789cc | 2 | Copyright (C) 2004-2013 Free Software Foundation, Inc. |
48e1416a | 3 | |
e12d0591 | 4 | This file is part of GCC. |
48e1416a | 5 | |
e12d0591 | 6 | GCC is free software; you can redistribute it and/or modify it |
7 | under the terms of the GNU General Public License as published by the | |
8c4c00c1 | 8 | Free Software Foundation; either version 3, or (at your option) any |
e12d0591 | 9 | later version. |
48e1416a | 10 | |
e12d0591 | 11 | GCC is distributed in the hope that it will be useful, but WITHOUT |
12 | ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or | |
13 | FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License | |
14 | for more details. | |
48e1416a | 15 | |
e12d0591 | 16 | You should have received a copy of the GNU General Public License |
8c4c00c1 | 17 | along with GCC; see the file COPYING3. If not see |
18 | <http://www.gnu.org/licenses/>. */ | |
e12d0591 | 19 | |
20 | #include "config.h" | |
21 | #include "system.h" | |
22 | #include "coretypes.h" | |
23 | #include "tm.h" | |
24 | #include "tree.h" | |
e12d0591 | 25 | #include "tm_p.h" |
e12d0591 | 26 | #include "basic-block.h" |
bc61cadb | 27 | #include "tree-ssa-alias.h" |
28 | #include "internal-fn.h" | |
29 | #include "gimple-expr.h" | |
30 | #include "is-a.h" | |
e795d6e1 | 31 | #include "gimple.h" |
a8783bee | 32 | #include "gimplify.h" |
073c1fd5 | 33 | #include "gimple-ssa.h" |
34 | #include "tree-cfg.h" | |
35 | #include "tree-phinodes.h" | |
36 | #include "ssa-iterators.h" | |
05d9c18a | 37 | #include "tree-ssa-loop-niter.h" |
073c1fd5 | 38 | #include "tree-ssa-loop.h" |
39 | #include "tree-into-ssa.h" | |
e12d0591 | 40 | #include "cfgloop.h" |
e12d0591 | 41 | #include "params.h" |
42 | #include "tree-pass.h" | |
bc8bb825 | 43 | #include "tree-inline.h" |
e12d0591 | 44 | |
45 | /* This file implements the loop unswitching, i.e. transformation of loops like | |
46 | ||
47 | while (A) | |
48 | { | |
49 | if (inv) | |
50 | B; | |
51 | ||
52 | X; | |
53 | ||
54 | if (!inv) | |
55 | C; | |
56 | } | |
57 | ||
58 | where inv is the loop invariant, into | |
59 | ||
60 | if (inv) | |
61 | { | |
62 | while (A) | |
63 | { | |
64 | B; | |
65 | X; | |
66 | } | |
67 | } | |
68 | else | |
69 | { | |
70 | while (A) | |
71 | { | |
72 | X; | |
73 | C; | |
74 | } | |
75 | } | |
76 | ||
77 | Inv is considered invariant iff the values it compares are both invariant; | |
78 | tree-ssa-loop-im.c ensures that all the suitable conditions are in this | |
79 | shape. */ | |
80 | ||
7194de72 | 81 | static struct loop *tree_unswitch_loop (struct loop *, basic_block, tree); |
82 | static bool tree_unswitch_single_loop (struct loop *, int); | |
e12d0591 | 83 | static tree tree_may_unswitch_on (basic_block, struct loop *); |
84 | ||
7194de72 | 85 | /* Main entry point. Perform loop unswitching on all suitable loops. */ |
e12d0591 | 86 | |
4c641bf8 | 87 | unsigned int |
7194de72 | 88 | tree_ssa_unswitch_loops (void) |
e12d0591 | 89 | { |
e12d0591 | 90 | struct loop *loop; |
91 | bool changed = false; | |
a9ef9877 | 92 | HOST_WIDE_INT iterations; |
e12d0591 | 93 | |
94 | /* Go through inner loops (only original ones). */ | |
f21d4d00 | 95 | FOR_EACH_LOOP (loop, LI_ONLY_INNERMOST) |
e12d0591 | 96 | { |
fd731bfb | 97 | if (dump_file && (dump_flags & TDF_DETAILS)) |
98 | fprintf (dump_file, ";; Considering loop %d\n", loop->num); | |
99 | ||
100 | /* Do not unswitch in cold regions. */ | |
101 | if (optimize_loop_for_size_p (loop)) | |
102 | { | |
103 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
104 | fprintf (dump_file, ";; Not unswitching cold loops\n"); | |
105 | continue; | |
106 | } | |
107 | ||
108 | /* The loop should not be too large, to limit code growth. */ | |
109 | if (tree_num_loop_insns (loop, &eni_size_weights) | |
110 | > (unsigned) PARAM_VALUE (PARAM_MAX_UNSWITCH_INSNS)) | |
111 | { | |
112 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
113 | fprintf (dump_file, ";; Not unswitching, loop too big\n"); | |
114 | continue; | |
115 | } | |
116 | ||
a9ef9877 | 117 | /* If the loop is not expected to iterate, there is no need |
118 | for unswitching. */ | |
119 | iterations = estimated_loop_iterations_int (loop); | |
120 | if (iterations >= 0 && iterations <= 1) | |
121 | { | |
122 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
123 | fprintf (dump_file, ";; Not unswitching, loop is not expected to iterate\n"); | |
124 | continue; | |
125 | } | |
126 | ||
7194de72 | 127 | changed |= tree_unswitch_single_loop (loop, 0); |
e12d0591 | 128 | } |
129 | ||
e12d0591 | 130 | if (changed) |
4c641bf8 | 131 | return TODO_cleanup_cfg; |
132 | return 0; | |
e12d0591 | 133 | } |
134 | ||
135 | /* Checks whether we can unswitch LOOP on condition at end of BB -- one of its | |
136 | basic blocks (for what it means see comments below). */ | |
137 | ||
138 | static tree | |
139 | tree_may_unswitch_on (basic_block bb, struct loop *loop) | |
140 | { | |
75a70cf9 | 141 | gimple stmt, def; |
142 | tree cond, use; | |
e12d0591 | 143 | basic_block def_bb; |
b66731e8 | 144 | ssa_op_iter iter; |
e12d0591 | 145 | |
146 | /* BB must end in a simple conditional jump. */ | |
147 | stmt = last_stmt (bb); | |
75a70cf9 | 148 | if (!stmt || gimple_code (stmt) != GIMPLE_COND) |
e12d0591 | 149 | return NULL_TREE; |
150 | ||
293bf172 | 151 | /* To keep the things simple, we do not directly remove the conditions, |
152 | but just replace tests with 0 != 0 resp. 1 != 0. Prevent the infinite | |
153 | loop where we would unswitch again on such a condition. */ | |
154 | if (gimple_cond_true_p (stmt) || gimple_cond_false_p (stmt)) | |
155 | return NULL_TREE; | |
156 | ||
e12d0591 | 157 | /* Condition must be invariant. */ |
b66731e8 | 158 | FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE) |
e12d0591 | 159 | { |
b66731e8 | 160 | def = SSA_NAME_DEF_STMT (use); |
75a70cf9 | 161 | def_bb = gimple_bb (def); |
e12d0591 | 162 | if (def_bb |
163 | && flow_bb_inside_loop_p (loop, def_bb)) | |
164 | return NULL_TREE; | |
165 | } | |
166 | ||
a92910ae | 167 | cond = build2 (gimple_cond_code (stmt), boolean_type_node, |
168 | gimple_cond_lhs (stmt), gimple_cond_rhs (stmt)); | |
75a70cf9 | 169 | |
e12d0591 | 170 | return cond; |
171 | } | |
172 | ||
173 | /* Simplifies COND using checks in front of the entry of the LOOP. Just very | |
174 | simplish (sufficient to prevent us from duplicating loop in unswitching | |
93d66711 | 175 | unnecessarily). */ |
e12d0591 | 176 | |
177 | static tree | |
178 | simplify_using_entry_checks (struct loop *loop, tree cond) | |
179 | { | |
180 | edge e = loop_preheader_edge (loop); | |
75a70cf9 | 181 | gimple stmt; |
e12d0591 | 182 | |
183 | while (1) | |
184 | { | |
185 | stmt = last_stmt (e->src); | |
186 | if (stmt | |
75a70cf9 | 187 | && gimple_code (stmt) == GIMPLE_COND |
188 | && gimple_cond_code (stmt) == TREE_CODE (cond) | |
189 | && operand_equal_p (gimple_cond_lhs (stmt), | |
190 | TREE_OPERAND (cond, 0), 0) | |
191 | && operand_equal_p (gimple_cond_rhs (stmt), | |
192 | TREE_OPERAND (cond, 1), 0)) | |
e12d0591 | 193 | return (e->flags & EDGE_TRUE_VALUE |
194 | ? boolean_true_node | |
195 | : boolean_false_node); | |
196 | ||
ea091dfd | 197 | if (!single_pred_p (e->src)) |
e12d0591 | 198 | return cond; |
199 | ||
ea091dfd | 200 | e = single_pred_edge (e->src); |
34154e27 | 201 | if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun)) |
e12d0591 | 202 | return cond; |
203 | } | |
204 | } | |
205 | ||
206 | /* Unswitch single LOOP. NUM is number of unswitchings done; we do not allow | |
207 | it to grow too much, it is too easy to create example on that the code would | |
208 | grow exponentially. */ | |
209 | ||
210 | static bool | |
7194de72 | 211 | tree_unswitch_single_loop (struct loop *loop, int num) |
e12d0591 | 212 | { |
213 | basic_block *bbs; | |
214 | struct loop *nloop; | |
293bf172 | 215 | unsigned i, found; |
75a70cf9 | 216 | tree cond = NULL_TREE; |
217 | gimple stmt; | |
e12d0591 | 218 | bool changed = false; |
219 | ||
e12d0591 | 220 | i = 0; |
221 | bbs = get_loop_body (loop); | |
293bf172 | 222 | found = loop->num_nodes; |
48e1416a | 223 | |
e12d0591 | 224 | while (1) |
225 | { | |
226 | /* Find a bb to unswitch on. */ | |
227 | for (; i < loop->num_nodes; i++) | |
228 | if ((cond = tree_may_unswitch_on (bbs[i], loop))) | |
229 | break; | |
230 | ||
231 | if (i == loop->num_nodes) | |
232 | { | |
293bf172 | 233 | if (dump_file |
234 | && num > PARAM_VALUE (PARAM_MAX_UNSWITCH_LEVEL) | |
235 | && (dump_flags & TDF_DETAILS)) | |
236 | fprintf (dump_file, ";; Not unswitching anymore, hit max level\n"); | |
237 | ||
238 | if (found == loop->num_nodes) | |
239 | { | |
240 | free (bbs); | |
241 | return changed; | |
242 | } | |
243 | break; | |
e12d0591 | 244 | } |
245 | ||
246 | cond = simplify_using_entry_checks (loop, cond); | |
247 | stmt = last_stmt (bbs[i]); | |
248 | if (integer_nonzerop (cond)) | |
249 | { | |
250 | /* Remove false path. */ | |
75a70cf9 | 251 | gimple_cond_set_condition_from_tree (stmt, boolean_true_node); |
e12d0591 | 252 | changed = true; |
253 | } | |
254 | else if (integer_zerop (cond)) | |
255 | { | |
256 | /* Remove true path. */ | |
75a70cf9 | 257 | gimple_cond_set_condition_from_tree (stmt, boolean_false_node); |
e12d0591 | 258 | changed = true; |
259 | } | |
293bf172 | 260 | /* Do not unswitch too much. */ |
261 | else if (num > PARAM_VALUE (PARAM_MAX_UNSWITCH_LEVEL)) | |
262 | { | |
263 | i++; | |
264 | continue; | |
265 | } | |
266 | /* In nested tree_unswitch_single_loop first optimize all conditions | |
267 | using entry checks, then discover still reachable blocks in the | |
268 | loop and find the condition only among those still reachable bbs. */ | |
269 | else if (num != 0) | |
270 | { | |
271 | if (found == loop->num_nodes) | |
272 | found = i; | |
273 | i++; | |
274 | continue; | |
275 | } | |
e12d0591 | 276 | else |
293bf172 | 277 | { |
278 | found = i; | |
279 | break; | |
280 | } | |
e12d0591 | 281 | |
22aa74c4 | 282 | update_stmt (stmt); |
e12d0591 | 283 | i++; |
284 | } | |
285 | ||
293bf172 | 286 | if (num != 0) |
287 | { | |
288 | basic_block *tos, *worklist; | |
289 | ||
290 | /* When called recursively, first do a quick discovery | |
291 | of reachable bbs after the above changes and only | |
292 | consider conditions in still reachable bbs. */ | |
293 | tos = worklist = XNEWVEC (basic_block, loop->num_nodes); | |
294 | ||
295 | for (i = 0; i < loop->num_nodes; i++) | |
296 | bbs[i]->flags &= ~BB_REACHABLE; | |
297 | ||
298 | /* Start with marking header. */ | |
299 | *tos++ = bbs[0]; | |
300 | bbs[0]->flags |= BB_REACHABLE; | |
301 | ||
302 | /* Iterate: find everything reachable from what we've already seen | |
303 | within the same innermost loop. Don't look through false edges | |
304 | if condition is always true or true edges if condition is | |
305 | always false. */ | |
306 | while (tos != worklist) | |
307 | { | |
308 | basic_block b = *--tos; | |
309 | edge e; | |
310 | edge_iterator ei; | |
311 | int flags = 0; | |
312 | ||
313 | if (EDGE_COUNT (b->succs) == 2) | |
314 | { | |
315 | gimple stmt = last_stmt (b); | |
316 | if (stmt | |
317 | && gimple_code (stmt) == GIMPLE_COND) | |
318 | { | |
319 | if (gimple_cond_true_p (stmt)) | |
320 | flags = EDGE_FALSE_VALUE; | |
321 | else if (gimple_cond_false_p (stmt)) | |
322 | flags = EDGE_TRUE_VALUE; | |
323 | } | |
324 | } | |
325 | ||
326 | FOR_EACH_EDGE (e, ei, b->succs) | |
327 | { | |
328 | basic_block dest = e->dest; | |
329 | ||
330 | if (dest->loop_father == loop | |
331 | && !(dest->flags & BB_REACHABLE) | |
332 | && !(e->flags & flags)) | |
333 | { | |
334 | *tos++ = dest; | |
335 | dest->flags |= BB_REACHABLE; | |
336 | } | |
337 | } | |
338 | } | |
339 | ||
340 | free (worklist); | |
341 | ||
342 | /* Find a bb to unswitch on. */ | |
343 | for (; found < loop->num_nodes; found++) | |
344 | if ((bbs[found]->flags & BB_REACHABLE) | |
345 | && (cond = tree_may_unswitch_on (bbs[found], loop))) | |
346 | break; | |
347 | ||
348 | if (found == loop->num_nodes) | |
349 | { | |
350 | free (bbs); | |
351 | return changed; | |
352 | } | |
353 | } | |
354 | ||
e12d0591 | 355 | if (dump_file && (dump_flags & TDF_DETAILS)) |
356 | fprintf (dump_file, ";; Unswitching loop\n"); | |
357 | ||
01020a5f | 358 | initialize_original_copy_tables (); |
e12d0591 | 359 | /* Unswitch the loop on this condition. */ |
293bf172 | 360 | nloop = tree_unswitch_loop (loop, bbs[found], cond); |
e12d0591 | 361 | if (!nloop) |
16c6b1e7 | 362 | { |
363 | free_original_copy_tables (); | |
5faf8533 | 364 | free (bbs); |
16c6b1e7 | 365 | return changed; |
366 | } | |
e12d0591 | 367 | |
095dcfa3 | 368 | /* Update the SSA form after unswitching. */ |
369 | update_ssa (TODO_update_ssa); | |
01020a5f | 370 | free_original_copy_tables (); |
095dcfa3 | 371 | |
e12d0591 | 372 | /* Invoke itself on modified loops. */ |
7194de72 | 373 | tree_unswitch_single_loop (nloop, num + 1); |
374 | tree_unswitch_single_loop (loop, num + 1); | |
5faf8533 | 375 | free (bbs); |
e12d0591 | 376 | return true; |
377 | } | |
378 | ||
379 | /* Unswitch a LOOP w.r. to given basic block UNSWITCH_ON. We only support | |
380 | unswitching of innermost loops. COND is the condition determining which | |
381 | loop is entered -- the new loop is entered if COND is true. Returns NULL | |
382 | if impossible, new loop otherwise. */ | |
383 | ||
384 | static struct loop * | |
7194de72 | 385 | tree_unswitch_loop (struct loop *loop, |
e12d0591 | 386 | basic_block unswitch_on, tree cond) |
387 | { | |
7cef6c97 | 388 | unsigned prob_true; |
389 | edge edge_true, edge_false; | |
e12d0591 | 390 | |
391 | /* Some sanity checking. */ | |
392 | gcc_assert (flow_bb_inside_loop_p (loop, unswitch_on)); | |
cd665a06 | 393 | gcc_assert (EDGE_COUNT (unswitch_on->succs) == 2); |
e12d0591 | 394 | gcc_assert (loop->inner == NULL); |
395 | ||
7cef6c97 | 396 | extract_true_false_edges_from_block (unswitch_on, &edge_true, &edge_false); |
397 | prob_true = edge_true->probability; | |
48e1416a | 398 | return loop_version (loop, unshare_expr (cond), |
7cef6c97 | 399 | NULL, prob_true, prob_true, |
400 | REG_BR_PROB_BASE - prob_true, false); | |
e12d0591 | 401 | } |
f86b328b | 402 | |
403 | /* Loop unswitching pass. */ | |
404 | ||
405 | static unsigned int | |
406 | tree_ssa_loop_unswitch (void) | |
407 | { | |
408 | if (number_of_loops (cfun) <= 1) | |
409 | return 0; | |
410 | ||
411 | return tree_ssa_unswitch_loops (); | |
412 | } | |
413 | ||
414 | static bool | |
415 | gate_tree_ssa_loop_unswitch (void) | |
416 | { | |
417 | return flag_unswitch_loops != 0; | |
418 | } | |
419 | ||
420 | namespace { | |
421 | ||
422 | const pass_data pass_data_tree_unswitch = | |
423 | { | |
424 | GIMPLE_PASS, /* type */ | |
425 | "unswitch", /* name */ | |
426 | OPTGROUP_LOOP, /* optinfo_flags */ | |
427 | true, /* has_gate */ | |
428 | true, /* has_execute */ | |
429 | TV_TREE_LOOP_UNSWITCH, /* tv_id */ | |
430 | PROP_cfg, /* properties_required */ | |
431 | 0, /* properties_provided */ | |
432 | 0, /* properties_destroyed */ | |
433 | 0, /* todo_flags_start */ | |
434 | 0, /* todo_flags_finish */ | |
435 | }; | |
436 | ||
437 | class pass_tree_unswitch : public gimple_opt_pass | |
438 | { | |
439 | public: | |
440 | pass_tree_unswitch (gcc::context *ctxt) | |
441 | : gimple_opt_pass (pass_data_tree_unswitch, ctxt) | |
442 | {} | |
443 | ||
444 | /* opt_pass methods: */ | |
445 | bool gate () { return gate_tree_ssa_loop_unswitch (); } | |
446 | unsigned int execute () { return tree_ssa_loop_unswitch (); } | |
447 | ||
448 | }; // class pass_tree_unswitch | |
449 | ||
450 | } // anon namespace | |
451 | ||
452 | gimple_opt_pass * | |
453 | make_pass_tree_unswitch (gcc::context *ctxt) | |
454 | { | |
455 | return new pass_tree_unswitch (ctxt); | |
456 | } | |
457 | ||
458 |