]>
Commit | Line | Data |
---|---|---|
82b85a85 | 1 | /* Induction variable canonicalization. |
726a989a | 2 | Copyright (C) 2004, 2005, 2007, 2008 Free Software Foundation, Inc. |
82b85a85 ZD |
3 | |
4 | This file is part of GCC. | |
5 | ||
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 | |
9dcd6f09 | 8 | Free Software Foundation; either version 3, or (at your option) any |
82b85a85 ZD |
9 | later version. |
10 | ||
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. | |
15 | ||
16 | You should have received a copy of the GNU General Public License | |
9dcd6f09 NC |
17 | along with GCC; see the file COPYING3. If not see |
18 | <http://www.gnu.org/licenses/>. */ | |
82b85a85 ZD |
19 | |
20 | /* This pass detects the loops that iterate a constant number of times, | |
21 | adds a canonical induction variable (step -1, tested against 0) | |
22 | and replaces the exit test. This enables the less powerful rtl | |
23 | level analysis to use this information. | |
24 | ||
25 | This might spoil the code in some cases (by increasing register pressure). | |
26 | Note that in the case the new variable is not needed, ivopts will get rid | |
27 | of it, so it might only be a problem when there are no other linear induction | |
28 | variables. In that case the created optimization possibilities are likely | |
29 | to pay up. | |
30 | ||
31 | Additionally in case we detect that it is beneficial to unroll the | |
32 | loop completely, we do it right here to expose the optimization | |
33 | possibilities to the following passes. */ | |
34 | ||
35 | #include "config.h" | |
36 | #include "system.h" | |
37 | #include "coretypes.h" | |
38 | #include "tm.h" | |
39 | #include "tree.h" | |
40 | #include "rtl.h" | |
41 | #include "tm_p.h" | |
42 | #include "hard-reg-set.h" | |
43 | #include "basic-block.h" | |
44 | #include "output.h" | |
45 | #include "diagnostic.h" | |
46 | #include "tree-flow.h" | |
47 | #include "tree-dump.h" | |
48 | #include "cfgloop.h" | |
49 | #include "tree-pass.h" | |
50 | #include "ggc.h" | |
51 | #include "tree-chrec.h" | |
52 | #include "tree-scalar-evolution.h" | |
53 | #include "params.h" | |
54 | #include "flags.h" | |
55 | #include "tree-inline.h" | |
56 | ||
91a01f21 ZD |
57 | /* Specifies types of loops that may be unrolled. */ |
58 | ||
59 | enum unroll_level | |
60 | { | |
bb22512c | 61 | UL_SINGLE_ITER, /* Only loops that exit immediately in the first |
91a01f21 ZD |
62 | iteration. */ |
63 | UL_NO_GROWTH, /* Only loops whose unrolling will not cause increase | |
64 | of code size. */ | |
65 | UL_ALL /* All suitable loops. */ | |
66 | }; | |
67 | ||
82b85a85 ZD |
68 | /* Adds a canonical induction variable to LOOP iterating NITER times. EXIT |
69 | is the exit edge whose condition is replaced. */ | |
70 | ||
71 | static void | |
72 | create_canonical_iv (struct loop *loop, edge exit, tree niter) | |
73 | { | |
74 | edge in; | |
726a989a RB |
75 | tree type, var; |
76 | gimple cond; | |
77 | gimple_stmt_iterator incr_at; | |
82b85a85 ZD |
78 | enum tree_code cmp; |
79 | ||
80 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
81 | { | |
82 | fprintf (dump_file, "Added canonical iv to loop %d, ", loop->num); | |
83 | print_generic_expr (dump_file, niter, TDF_SLIM); | |
84 | fprintf (dump_file, " iterations.\n"); | |
85 | } | |
86 | ||
87 | cond = last_stmt (exit->src); | |
628f6a4e | 88 | in = EDGE_SUCC (exit->src, 0); |
82b85a85 | 89 | if (in == exit) |
628f6a4e | 90 | in = EDGE_SUCC (exit->src, 1); |
82b85a85 ZD |
91 | |
92 | /* Note that we do not need to worry about overflows, since | |
93 | type of niter is always unsigned and all comparisons are | |
94 | just for equality/nonequality -- i.e. everything works | |
95 | with a modulo arithmetics. */ | |
96 | ||
97 | type = TREE_TYPE (niter); | |
987b67bc KH |
98 | niter = fold_build2 (PLUS_EXPR, type, |
99 | niter, | |
100 | build_int_cst (type, 1)); | |
726a989a | 101 | incr_at = gsi_last_bb (in->src); |
82b85a85 | 102 | create_iv (niter, |
57decb7e | 103 | build_int_cst (type, -1), |
82b85a85 ZD |
104 | NULL_TREE, loop, |
105 | &incr_at, false, NULL, &var); | |
106 | ||
107 | cmp = (exit->flags & EDGE_TRUE_VALUE) ? EQ_EXPR : NE_EXPR; | |
726a989a RB |
108 | gimple_cond_set_code (cond, cmp); |
109 | gimple_cond_set_lhs (cond, var); | |
110 | gimple_cond_set_rhs (cond, build_int_cst (type, 0)); | |
f430bae8 | 111 | update_stmt (cond); |
82b85a85 ZD |
112 | } |
113 | ||
7f9bc51b | 114 | /* Computes an estimated number of insns in LOOP, weighted by WEIGHTS. */ |
82b85a85 ZD |
115 | |
116 | unsigned | |
7f9bc51b | 117 | tree_num_loop_insns (struct loop *loop, eni_weights *weights) |
82b85a85 ZD |
118 | { |
119 | basic_block *body = get_loop_body (loop); | |
726a989a | 120 | gimple_stmt_iterator gsi; |
82b85a85 ZD |
121 | unsigned size = 1, i; |
122 | ||
123 | for (i = 0; i < loop->num_nodes; i++) | |
726a989a RB |
124 | for (gsi = gsi_start_bb (body[i]); !gsi_end_p (gsi); gsi_next (&gsi)) |
125 | size += estimate_num_insns (gsi_stmt (gsi), weights); | |
82b85a85 ZD |
126 | free (body); |
127 | ||
128 | return size; | |
129 | } | |
130 | ||
91a01f21 ZD |
131 | /* Estimate number of insns of completely unrolled loop. We assume |
132 | that the size of the unrolled loop is decreased in the | |
133 | following way (the numbers of insns are based on what | |
134 | estimate_num_insns returns for appropriate statements): | |
135 | ||
136 | 1) exit condition gets removed (2 insns) | |
137 | 2) increment of the control variable gets removed (2 insns) | |
138 | 3) All remaining statements are likely to get simplified | |
139 | due to constant propagation. Hard to estimate; just | |
140 | as a heuristics we decrease the rest by 1/3. | |
141 | ||
142 | NINSNS is the number of insns in the loop before unrolling. | |
143 | NUNROLL is the number of times the loop is unrolled. */ | |
144 | ||
145 | static unsigned HOST_WIDE_INT | |
146 | estimated_unrolled_size (unsigned HOST_WIDE_INT ninsns, | |
147 | unsigned HOST_WIDE_INT nunroll) | |
148 | { | |
149 | HOST_WIDE_INT unr_insns = 2 * ((HOST_WIDE_INT) ninsns - 4) / 3; | |
150 | if (unr_insns <= 0) | |
151 | unr_insns = 1; | |
152 | unr_insns *= (nunroll + 1); | |
153 | ||
154 | return unr_insns; | |
155 | } | |
156 | ||
d73be268 ZD |
157 | /* Tries to unroll LOOP completely, i.e. NITER times. |
158 | UL determines which loops we are allowed to unroll. | |
91a01f21 | 159 | EXIT is the exit of the loop that should be eliminated. */ |
82b85a85 ZD |
160 | |
161 | static bool | |
d73be268 | 162 | try_unroll_loop_completely (struct loop *loop, |
82b85a85 | 163 | edge exit, tree niter, |
91a01f21 | 164 | enum unroll_level ul) |
82b85a85 | 165 | { |
91a01f21 | 166 | unsigned HOST_WIDE_INT n_unroll, ninsns, max_unroll, unr_insns; |
726a989a | 167 | gimple cond; |
82b85a85 ZD |
168 | |
169 | if (loop->inner) | |
170 | return false; | |
171 | ||
172 | if (!host_integerp (niter, 1)) | |
173 | return false; | |
174 | n_unroll = tree_low_cst (niter, 1); | |
175 | ||
176 | max_unroll = PARAM_VALUE (PARAM_MAX_COMPLETELY_PEEL_TIMES); | |
177 | if (n_unroll > max_unroll) | |
178 | return false; | |
179 | ||
180 | if (n_unroll) | |
181 | { | |
91a01f21 | 182 | if (ul == UL_SINGLE_ITER) |
82b85a85 ZD |
183 | return false; |
184 | ||
7f9bc51b | 185 | ninsns = tree_num_loop_insns (loop, &eni_size_weights); |
82b85a85 ZD |
186 | |
187 | if (n_unroll * ninsns | |
188 | > (unsigned) PARAM_VALUE (PARAM_MAX_COMPLETELY_PEELED_INSNS)) | |
189 | return false; | |
91a01f21 | 190 | |
d6e840ee RG |
191 | unr_insns = estimated_unrolled_size (ninsns, n_unroll); |
192 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
193 | { | |
194 | fprintf (dump_file, " Loop size: %d\n", (int) ninsns); | |
195 | fprintf (dump_file, " Estimated size after unrolling: %d\n", | |
196 | (int) unr_insns); | |
197 | } | |
198 | ||
199 | if (ul == UL_NO_GROWTH | |
200 | && unr_insns > ninsns) | |
91a01f21 | 201 | { |
91a01f21 | 202 | if (dump_file && (dump_flags & TDF_DETAILS)) |
d6e840ee RG |
203 | fprintf (dump_file, "Not unrolling loop %d.\n", loop->num); |
204 | return false; | |
91a01f21 | 205 | } |
82b85a85 ZD |
206 | } |
207 | ||
82b85a85 ZD |
208 | if (n_unroll) |
209 | { | |
178df94f | 210 | sbitmap wont_exit; |
6c74788e SP |
211 | edge e; |
212 | unsigned i; | |
213 | VEC (edge, heap) *to_remove = NULL; | |
178df94f | 214 | |
6580ee77 | 215 | initialize_original_copy_tables (); |
178df94f JH |
216 | wont_exit = sbitmap_alloc (n_unroll + 1); |
217 | sbitmap_ones (wont_exit); | |
218 | RESET_BIT (wont_exit, 0); | |
219 | ||
726a989a RB |
220 | if (!gimple_duplicate_loop_to_header_edge (loop, loop_preheader_edge (loop), |
221 | n_unroll, wont_exit, | |
222 | exit, &to_remove, | |
223 | DLTHE_FLAG_UPDATE_FREQ | |
224 | | DLTHE_FLAG_COMPLETTE_PEEL)) | |
82b85a85 | 225 | { |
6580ee77 | 226 | free_original_copy_tables (); |
178df94f | 227 | free (wont_exit); |
82b85a85 ZD |
228 | return false; |
229 | } | |
6c74788e SP |
230 | |
231 | for (i = 0; VEC_iterate (edge, to_remove, i, e); i++) | |
232 | { | |
233 | bool ok = remove_path (e); | |
234 | gcc_assert (ok); | |
235 | } | |
236 | ||
237 | VEC_free (edge, heap, to_remove); | |
178df94f | 238 | free (wont_exit); |
6580ee77 | 239 | free_original_copy_tables (); |
82b85a85 | 240 | } |
82b85a85 | 241 | |
6c74788e | 242 | cond = last_stmt (exit->src); |
726a989a RB |
243 | if (exit->flags & EDGE_TRUE_VALUE) |
244 | gimple_cond_make_true (cond); | |
245 | else | |
246 | gimple_cond_make_false (cond); | |
6c74788e | 247 | update_stmt (cond); |
84d65814 DN |
248 | update_ssa (TODO_update_ssa); |
249 | ||
82b85a85 ZD |
250 | if (dump_file && (dump_flags & TDF_DETAILS)) |
251 | fprintf (dump_file, "Unrolled loop %d completely.\n", loop->num); | |
252 | ||
253 | return true; | |
254 | } | |
255 | ||
d73be268 ZD |
256 | /* Adds a canonical induction variable to LOOP if suitable. |
257 | CREATE_IV is true if we may create a new iv. UL determines | |
91a01f21 ZD |
258 | which loops we are allowed to completely unroll. If TRY_EVAL is true, we try |
259 | to determine the number of iterations of a loop by direct evaluation. | |
260 | Returns true if cfg is changed. */ | |
82b85a85 ZD |
261 | |
262 | static bool | |
d73be268 | 263 | canonicalize_loop_induction_variables (struct loop *loop, |
91a01f21 | 264 | bool create_iv, enum unroll_level ul, |
82b85a85 ZD |
265 | bool try_eval) |
266 | { | |
267 | edge exit = NULL; | |
268 | tree niter; | |
269 | ||
a14865db | 270 | niter = number_of_latch_executions (loop); |
82b85a85 ZD |
271 | if (TREE_CODE (niter) == INTEGER_CST) |
272 | { | |
ac8f6c69 | 273 | exit = single_exit (loop); |
82b85a85 ZD |
274 | if (!just_once_each_iteration_p (loop, exit->src)) |
275 | return false; | |
82b85a85 | 276 | } |
ca4c3169 ZD |
277 | else |
278 | { | |
279 | /* If the loop has more than one exit, try checking all of them | |
280 | for # of iterations determinable through scev. */ | |
ac8f6c69 | 281 | if (!single_exit (loop)) |
ca4c3169 ZD |
282 | niter = find_loop_niter (loop, &exit); |
283 | ||
284 | /* Finally if everything else fails, try brute force evaluation. */ | |
285 | if (try_eval | |
286 | && (chrec_contains_undetermined (niter) | |
287 | || TREE_CODE (niter) != INTEGER_CST)) | |
288 | niter = find_loop_niter_by_eval (loop, &exit); | |
289 | ||
290 | if (chrec_contains_undetermined (niter) | |
291 | || TREE_CODE (niter) != INTEGER_CST) | |
292 | return false; | |
293 | } | |
82b85a85 ZD |
294 | |
295 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
296 | { | |
297 | fprintf (dump_file, "Loop %d iterates ", loop->num); | |
298 | print_generic_expr (dump_file, niter, TDF_SLIM); | |
299 | fprintf (dump_file, " times.\n"); | |
300 | } | |
301 | ||
d73be268 | 302 | if (try_unroll_loop_completely (loop, exit, niter, ul)) |
82b85a85 ZD |
303 | return true; |
304 | ||
305 | if (create_iv) | |
306 | create_canonical_iv (loop, exit, niter); | |
307 | ||
308 | return false; | |
309 | } | |
310 | ||
311 | /* The main entry point of the pass. Adds canonical induction variables | |
d73be268 | 312 | to the suitable loops. */ |
82b85a85 | 313 | |
c7f965b6 | 314 | unsigned int |
d73be268 | 315 | canonicalize_induction_variables (void) |
82b85a85 | 316 | { |
42fd6772 | 317 | loop_iterator li; |
82b85a85 | 318 | struct loop *loop; |
2b271002 | 319 | bool changed = false; |
82b85a85 | 320 | |
42fd6772 | 321 | FOR_EACH_LOOP (li, loop, 0) |
82b85a85 | 322 | { |
42fd6772 ZD |
323 | changed |= canonicalize_loop_induction_variables (loop, |
324 | true, UL_SINGLE_ITER, | |
325 | true); | |
82b85a85 ZD |
326 | } |
327 | ||
47bcd07d ZD |
328 | /* Clean up the information about numbers of iterations, since brute force |
329 | evaluation could reveal new information. */ | |
330 | scev_reset (); | |
331 | ||
82b85a85 | 332 | if (changed) |
c7f965b6 AP |
333 | return TODO_cleanup_cfg; |
334 | return 0; | |
82b85a85 ZD |
335 | } |
336 | ||
91a01f21 ZD |
337 | /* Unroll LOOPS completely if they iterate just few times. Unless |
338 | MAY_INCREASE_SIZE is true, perform the unrolling only if the | |
339 | size of the code does not increase. */ | |
82b85a85 | 340 | |
c7f965b6 | 341 | unsigned int |
d6e840ee | 342 | tree_unroll_loops_completely (bool may_increase_size, bool unroll_outer) |
82b85a85 | 343 | { |
42fd6772 | 344 | loop_iterator li; |
82b85a85 | 345 | struct loop *loop; |
d6e840ee | 346 | bool changed; |
178df94f | 347 | enum unroll_level ul; |
82b85a85 | 348 | |
d6e840ee | 349 | do |
82b85a85 | 350 | { |
d6e840ee | 351 | changed = false; |
82b85a85 | 352 | |
d6e840ee RG |
353 | FOR_EACH_LOOP (li, loop, LI_ONLY_INNERMOST) |
354 | { | |
355 | if (may_increase_size && maybe_hot_bb_p (loop->header) | |
356 | /* Unroll outermost loops only if asked to do so or they do | |
357 | not cause code growth. */ | |
358 | && (unroll_outer | |
359 | || loop_outer (loop_outer (loop)))) | |
360 | ul = UL_ALL; | |
361 | else | |
362 | ul = UL_NO_GROWTH; | |
363 | changed |= canonicalize_loop_induction_variables | |
364 | (loop, false, ul, !flag_tree_loop_ivcanon); | |
365 | } | |
366 | ||
367 | if (changed) | |
368 | { | |
369 | /* This will take care of removing completely unrolled loops | |
370 | from the loop structures so we can continue unrolling now | |
371 | innermost loops. */ | |
ace4eb90 RG |
372 | if (cleanup_tree_cfg ()) |
373 | update_ssa (TODO_update_ssa_only_virtuals); | |
d6e840ee RG |
374 | |
375 | /* Clean up the information about numbers of iterations, since | |
376 | complete unrolling might have invalidated it. */ | |
377 | scev_reset (); | |
378 | } | |
379 | } | |
380 | while (changed); | |
47bcd07d | 381 | |
c7f965b6 | 382 | return 0; |
82b85a85 | 383 | } |
b7eae7b8 ZD |
384 | |
385 | /* Checks whether LOOP is empty. */ | |
386 | ||
387 | static bool | |
388 | empty_loop_p (struct loop *loop) | |
389 | { | |
390 | edge exit; | |
391 | struct tree_niter_desc niter; | |
b7eae7b8 | 392 | basic_block *body; |
726a989a | 393 | gimple_stmt_iterator gsi; |
b7eae7b8 | 394 | unsigned i; |
b7eae7b8 ZD |
395 | |
396 | /* If the loop has multiple exits, it is too hard for us to handle. | |
397 | Similarly, if the exit is not dominating, we cannot determine | |
398 | whether the loop is not infinite. */ | |
399 | exit = single_dom_exit (loop); | |
400 | if (!exit) | |
401 | return false; | |
402 | ||
403 | /* The loop must be finite. */ | |
f9cc1a70 | 404 | if (!number_of_iterations_exit (loop, exit, &niter, false)) |
b7eae7b8 ZD |
405 | return false; |
406 | ||
407 | /* Values of all loop exit phi nodes must be invariants. */ | |
726a989a | 408 | for (gsi = gsi_start(phi_nodes (exit->dest)); !gsi_end_p (gsi); gsi_next (&gsi)) |
b7eae7b8 | 409 | { |
726a989a RB |
410 | gimple phi = gsi_stmt (gsi); |
411 | tree def; | |
412 | ||
b7eae7b8 ZD |
413 | if (!is_gimple_reg (PHI_RESULT (phi))) |
414 | continue; | |
415 | ||
416 | def = PHI_ARG_DEF_FROM_EDGE (phi, exit); | |
417 | ||
418 | if (!expr_invariant_in_loop_p (loop, def)) | |
419 | return false; | |
420 | } | |
421 | ||
422 | /* And there should be no memory modifying or from other reasons | |
423 | unremovable statements. */ | |
424 | body = get_loop_body (loop); | |
425 | for (i = 0; i < loop->num_nodes; i++) | |
426 | { | |
427 | /* Irreducible region might be infinite. */ | |
428 | if (body[i]->flags & BB_IRREDUCIBLE_LOOP) | |
429 | { | |
430 | free (body); | |
431 | return false; | |
432 | } | |
433 | ||
726a989a | 434 | for (gsi = gsi_start_bb (body[i]); !gsi_end_p (gsi); gsi_next (&gsi)) |
b7eae7b8 | 435 | { |
726a989a RB |
436 | gimple stmt = gsi_stmt (gsi); |
437 | ||
b7eae7b8 | 438 | if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_VIRTUAL_DEFS) |
726a989a | 439 | || gimple_has_volatile_ops (stmt)) |
b7eae7b8 ZD |
440 | { |
441 | free (body); | |
442 | return false; | |
443 | } | |
444 | ||
445 | /* Also, asm statements and calls may have side effects and we | |
446 | cannot change the number of times they are executed. */ | |
726a989a | 447 | switch (gimple_code (stmt)) |
b7eae7b8 | 448 | { |
726a989a RB |
449 | case GIMPLE_CALL: |
450 | if (gimple_has_side_effects (stmt)) | |
b7eae7b8 ZD |
451 | { |
452 | free (body); | |
453 | return false; | |
454 | } | |
455 | break; | |
456 | ||
726a989a | 457 | case GIMPLE_ASM: |
b7eae7b8 | 458 | /* We cannot remove volatile assembler. */ |
726a989a | 459 | if (gimple_asm_volatile_p (stmt)) |
b7eae7b8 ZD |
460 | { |
461 | free (body); | |
462 | return false; | |
463 | } | |
464 | break; | |
465 | ||
466 | default: | |
467 | break; | |
468 | } | |
469 | } | |
470 | } | |
471 | free (body); | |
472 | ||
473 | return true; | |
474 | } | |
475 | ||
476 | /* Remove LOOP by making it exit in the first iteration. */ | |
477 | ||
478 | static void | |
479 | remove_empty_loop (struct loop *loop) | |
480 | { | |
37261a5c | 481 | edge exit = single_dom_exit (loop), non_exit; |
726a989a | 482 | gimple cond_stmt = last_stmt (exit->src); |
37261a5c ZD |
483 | basic_block *body; |
484 | unsigned n_before, freq_in, freq_h; | |
485 | gcov_type exit_count = exit->count; | |
486 | ||
b44e7f07 ZD |
487 | if (dump_file) |
488 | fprintf (dump_file, "Removing empty loop %d\n", loop->num); | |
489 | ||
37261a5c ZD |
490 | non_exit = EDGE_SUCC (exit->src, 0); |
491 | if (non_exit == exit) | |
492 | non_exit = EDGE_SUCC (exit->src, 1); | |
b7eae7b8 ZD |
493 | |
494 | if (exit->flags & EDGE_TRUE_VALUE) | |
726a989a | 495 | gimple_cond_make_true (cond_stmt); |
b7eae7b8 | 496 | else |
726a989a | 497 | gimple_cond_make_false (cond_stmt); |
b7eae7b8 | 498 | update_stmt (cond_stmt); |
37261a5c ZD |
499 | |
500 | /* Let us set the probabilities of the edges coming from the exit block. */ | |
501 | exit->probability = REG_BR_PROB_BASE; | |
502 | non_exit->probability = 0; | |
503 | non_exit->count = 0; | |
504 | ||
505 | /* Update frequencies and counts. Everything before | |
506 | the exit needs to be scaled FREQ_IN/FREQ_H times, | |
507 | where FREQ_IN is the frequency of the entry edge | |
508 | and FREQ_H is the frequency of the loop header. | |
509 | Everything after the exit has zero frequency. */ | |
510 | freq_h = loop->header->frequency; | |
511 | freq_in = EDGE_FREQUENCY (loop_preheader_edge (loop)); | |
512 | if (freq_h != 0) | |
513 | { | |
514 | body = get_loop_body_in_dom_order (loop); | |
515 | for (n_before = 1; n_before <= loop->num_nodes; n_before++) | |
516 | if (body[n_before - 1] == exit->src) | |
517 | break; | |
518 | scale_bbs_frequencies_int (body, n_before, freq_in, freq_h); | |
519 | scale_bbs_frequencies_int (body + n_before, loop->num_nodes - n_before, | |
520 | 0, 1); | |
521 | free (body); | |
522 | } | |
523 | ||
524 | /* Number of executions of exit is not changed, thus we need to restore | |
525 | the original value. */ | |
526 | exit->count = exit_count; | |
b7eae7b8 ZD |
527 | } |
528 | ||
529 | /* Removes LOOP if it is empty. Returns true if LOOP is removed. CHANGED | |
530 | is set to true if LOOP or any of its subloops is removed. */ | |
531 | ||
532 | static bool | |
533 | try_remove_empty_loop (struct loop *loop, bool *changed) | |
534 | { | |
535 | bool nonempty_subloop = false; | |
536 | struct loop *sub; | |
537 | ||
538 | /* First, all subloops must be removed. */ | |
539 | for (sub = loop->inner; sub; sub = sub->next) | |
540 | nonempty_subloop |= !try_remove_empty_loop (sub, changed); | |
541 | ||
542 | if (nonempty_subloop || !empty_loop_p (loop)) | |
543 | return false; | |
544 | ||
545 | remove_empty_loop (loop); | |
546 | *changed = true; | |
547 | return true; | |
548 | } | |
549 | ||
d73be268 | 550 | /* Remove the empty loops. */ |
b7eae7b8 | 551 | |
c7f965b6 | 552 | unsigned int |
d73be268 | 553 | remove_empty_loops (void) |
b7eae7b8 ZD |
554 | { |
555 | bool changed = false; | |
556 | struct loop *loop; | |
557 | ||
d73be268 | 558 | for (loop = current_loops->tree_root->inner; loop; loop = loop->next) |
b7eae7b8 ZD |
559 | try_remove_empty_loop (loop, &changed); |
560 | ||
561 | if (changed) | |
562 | { | |
563 | scev_reset (); | |
c7f965b6 | 564 | return TODO_cleanup_cfg; |
b7eae7b8 | 565 | } |
c7f965b6 | 566 | return 0; |
b7eae7b8 | 567 | } |
726a989a | 568 |