]>
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 | 186 | |
d6e840ee RG |
187 | unr_insns = estimated_unrolled_size (ninsns, n_unroll); |
188 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
189 | { | |
190 | fprintf (dump_file, " Loop size: %d\n", (int) ninsns); | |
191 | fprintf (dump_file, " Estimated size after unrolling: %d\n", | |
192 | (int) unr_insns); | |
193 | } | |
194 | ||
678e7c65 RG |
195 | if (unr_insns > ninsns |
196 | && (unr_insns | |
197 | > (unsigned) PARAM_VALUE (PARAM_MAX_COMPLETELY_PEELED_INSNS))) | |
198 | { | |
199 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
200 | fprintf (dump_file, "Not unrolling loop %d " | |
201 | "(--param max-completely-peeled-insns limit reached).\n", | |
202 | loop->num); | |
203 | return false; | |
204 | } | |
205 | ||
d6e840ee RG |
206 | if (ul == UL_NO_GROWTH |
207 | && unr_insns > ninsns) | |
91a01f21 | 208 | { |
91a01f21 | 209 | if (dump_file && (dump_flags & TDF_DETAILS)) |
d6e840ee RG |
210 | fprintf (dump_file, "Not unrolling loop %d.\n", loop->num); |
211 | return false; | |
91a01f21 | 212 | } |
82b85a85 ZD |
213 | } |
214 | ||
82b85a85 ZD |
215 | if (n_unroll) |
216 | { | |
178df94f | 217 | sbitmap wont_exit; |
6c74788e SP |
218 | edge e; |
219 | unsigned i; | |
220 | VEC (edge, heap) *to_remove = NULL; | |
178df94f | 221 | |
6580ee77 | 222 | initialize_original_copy_tables (); |
178df94f JH |
223 | wont_exit = sbitmap_alloc (n_unroll + 1); |
224 | sbitmap_ones (wont_exit); | |
225 | RESET_BIT (wont_exit, 0); | |
226 | ||
726a989a RB |
227 | if (!gimple_duplicate_loop_to_header_edge (loop, loop_preheader_edge (loop), |
228 | n_unroll, wont_exit, | |
229 | exit, &to_remove, | |
230 | DLTHE_FLAG_UPDATE_FREQ | |
231 | | DLTHE_FLAG_COMPLETTE_PEEL)) | |
82b85a85 | 232 | { |
6580ee77 | 233 | free_original_copy_tables (); |
178df94f | 234 | free (wont_exit); |
82b85a85 ZD |
235 | return false; |
236 | } | |
6c74788e SP |
237 | |
238 | for (i = 0; VEC_iterate (edge, to_remove, i, e); i++) | |
239 | { | |
240 | bool ok = remove_path (e); | |
241 | gcc_assert (ok); | |
242 | } | |
243 | ||
244 | VEC_free (edge, heap, to_remove); | |
178df94f | 245 | free (wont_exit); |
6580ee77 | 246 | free_original_copy_tables (); |
82b85a85 | 247 | } |
82b85a85 | 248 | |
6c74788e | 249 | cond = last_stmt (exit->src); |
726a989a RB |
250 | if (exit->flags & EDGE_TRUE_VALUE) |
251 | gimple_cond_make_true (cond); | |
252 | else | |
253 | gimple_cond_make_false (cond); | |
6c74788e | 254 | update_stmt (cond); |
84d65814 DN |
255 | update_ssa (TODO_update_ssa); |
256 | ||
82b85a85 ZD |
257 | if (dump_file && (dump_flags & TDF_DETAILS)) |
258 | fprintf (dump_file, "Unrolled loop %d completely.\n", loop->num); | |
259 | ||
260 | return true; | |
261 | } | |
262 | ||
d73be268 ZD |
263 | /* Adds a canonical induction variable to LOOP if suitable. |
264 | CREATE_IV is true if we may create a new iv. UL determines | |
91a01f21 ZD |
265 | which loops we are allowed to completely unroll. If TRY_EVAL is true, we try |
266 | to determine the number of iterations of a loop by direct evaluation. | |
267 | Returns true if cfg is changed. */ | |
82b85a85 ZD |
268 | |
269 | static bool | |
d73be268 | 270 | canonicalize_loop_induction_variables (struct loop *loop, |
91a01f21 | 271 | bool create_iv, enum unroll_level ul, |
82b85a85 ZD |
272 | bool try_eval) |
273 | { | |
274 | edge exit = NULL; | |
275 | tree niter; | |
276 | ||
a14865db | 277 | niter = number_of_latch_executions (loop); |
82b85a85 ZD |
278 | if (TREE_CODE (niter) == INTEGER_CST) |
279 | { | |
ac8f6c69 | 280 | exit = single_exit (loop); |
82b85a85 ZD |
281 | if (!just_once_each_iteration_p (loop, exit->src)) |
282 | return false; | |
82b85a85 | 283 | } |
ca4c3169 ZD |
284 | else |
285 | { | |
286 | /* If the loop has more than one exit, try checking all of them | |
287 | for # of iterations determinable through scev. */ | |
ac8f6c69 | 288 | if (!single_exit (loop)) |
ca4c3169 ZD |
289 | niter = find_loop_niter (loop, &exit); |
290 | ||
291 | /* Finally if everything else fails, try brute force evaluation. */ | |
292 | if (try_eval | |
293 | && (chrec_contains_undetermined (niter) | |
294 | || TREE_CODE (niter) != INTEGER_CST)) | |
295 | niter = find_loop_niter_by_eval (loop, &exit); | |
296 | ||
297 | if (chrec_contains_undetermined (niter) | |
298 | || TREE_CODE (niter) != INTEGER_CST) | |
299 | return false; | |
300 | } | |
82b85a85 ZD |
301 | |
302 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
303 | { | |
304 | fprintf (dump_file, "Loop %d iterates ", loop->num); | |
305 | print_generic_expr (dump_file, niter, TDF_SLIM); | |
306 | fprintf (dump_file, " times.\n"); | |
307 | } | |
308 | ||
d73be268 | 309 | if (try_unroll_loop_completely (loop, exit, niter, ul)) |
82b85a85 ZD |
310 | return true; |
311 | ||
312 | if (create_iv) | |
313 | create_canonical_iv (loop, exit, niter); | |
314 | ||
315 | return false; | |
316 | } | |
317 | ||
318 | /* The main entry point of the pass. Adds canonical induction variables | |
d73be268 | 319 | to the suitable loops. */ |
82b85a85 | 320 | |
c7f965b6 | 321 | unsigned int |
d73be268 | 322 | canonicalize_induction_variables (void) |
82b85a85 | 323 | { |
42fd6772 | 324 | loop_iterator li; |
82b85a85 | 325 | struct loop *loop; |
2b271002 | 326 | bool changed = false; |
82b85a85 | 327 | |
42fd6772 | 328 | FOR_EACH_LOOP (li, loop, 0) |
82b85a85 | 329 | { |
42fd6772 ZD |
330 | changed |= canonicalize_loop_induction_variables (loop, |
331 | true, UL_SINGLE_ITER, | |
332 | true); | |
82b85a85 ZD |
333 | } |
334 | ||
47bcd07d ZD |
335 | /* Clean up the information about numbers of iterations, since brute force |
336 | evaluation could reveal new information. */ | |
337 | scev_reset (); | |
338 | ||
82b85a85 | 339 | if (changed) |
c7f965b6 AP |
340 | return TODO_cleanup_cfg; |
341 | return 0; | |
82b85a85 ZD |
342 | } |
343 | ||
91a01f21 ZD |
344 | /* Unroll LOOPS completely if they iterate just few times. Unless |
345 | MAY_INCREASE_SIZE is true, perform the unrolling only if the | |
346 | size of the code does not increase. */ | |
82b85a85 | 347 | |
c7f965b6 | 348 | unsigned int |
d6e840ee | 349 | tree_unroll_loops_completely (bool may_increase_size, bool unroll_outer) |
82b85a85 | 350 | { |
42fd6772 | 351 | loop_iterator li; |
82b85a85 | 352 | struct loop *loop; |
d6e840ee | 353 | bool changed; |
178df94f | 354 | enum unroll_level ul; |
82b85a85 | 355 | |
d6e840ee | 356 | do |
82b85a85 | 357 | { |
d6e840ee | 358 | changed = false; |
82b85a85 | 359 | |
d6e840ee RG |
360 | FOR_EACH_LOOP (li, loop, LI_ONLY_INNERMOST) |
361 | { | |
efd8f750 | 362 | if (may_increase_size && optimize_loop_for_speed_p (loop) |
d6e840ee RG |
363 | /* Unroll outermost loops only if asked to do so or they do |
364 | not cause code growth. */ | |
365 | && (unroll_outer | |
366 | || loop_outer (loop_outer (loop)))) | |
367 | ul = UL_ALL; | |
368 | else | |
369 | ul = UL_NO_GROWTH; | |
370 | changed |= canonicalize_loop_induction_variables | |
371 | (loop, false, ul, !flag_tree_loop_ivcanon); | |
372 | } | |
373 | ||
374 | if (changed) | |
375 | { | |
376 | /* This will take care of removing completely unrolled loops | |
377 | from the loop structures so we can continue unrolling now | |
378 | innermost loops. */ | |
ace4eb90 RG |
379 | if (cleanup_tree_cfg ()) |
380 | update_ssa (TODO_update_ssa_only_virtuals); | |
d6e840ee RG |
381 | |
382 | /* Clean up the information about numbers of iterations, since | |
383 | complete unrolling might have invalidated it. */ | |
384 | scev_reset (); | |
385 | } | |
386 | } | |
387 | while (changed); | |
47bcd07d | 388 | |
c7f965b6 | 389 | return 0; |
82b85a85 | 390 | } |
b7eae7b8 ZD |
391 | |
392 | /* Checks whether LOOP is empty. */ | |
393 | ||
394 | static bool | |
395 | empty_loop_p (struct loop *loop) | |
396 | { | |
397 | edge exit; | |
398 | struct tree_niter_desc niter; | |
b7eae7b8 | 399 | basic_block *body; |
726a989a | 400 | gimple_stmt_iterator gsi; |
b7eae7b8 | 401 | unsigned i; |
b7eae7b8 ZD |
402 | |
403 | /* If the loop has multiple exits, it is too hard for us to handle. | |
404 | Similarly, if the exit is not dominating, we cannot determine | |
405 | whether the loop is not infinite. */ | |
406 | exit = single_dom_exit (loop); | |
407 | if (!exit) | |
408 | return false; | |
409 | ||
410 | /* The loop must be finite. */ | |
f9cc1a70 | 411 | if (!number_of_iterations_exit (loop, exit, &niter, false)) |
b7eae7b8 ZD |
412 | return false; |
413 | ||
414 | /* Values of all loop exit phi nodes must be invariants. */ | |
726a989a | 415 | for (gsi = gsi_start(phi_nodes (exit->dest)); !gsi_end_p (gsi); gsi_next (&gsi)) |
b7eae7b8 | 416 | { |
726a989a RB |
417 | gimple phi = gsi_stmt (gsi); |
418 | tree def; | |
419 | ||
b7eae7b8 ZD |
420 | if (!is_gimple_reg (PHI_RESULT (phi))) |
421 | continue; | |
422 | ||
423 | def = PHI_ARG_DEF_FROM_EDGE (phi, exit); | |
424 | ||
425 | if (!expr_invariant_in_loop_p (loop, def)) | |
426 | return false; | |
427 | } | |
428 | ||
429 | /* And there should be no memory modifying or from other reasons | |
430 | unremovable statements. */ | |
431 | body = get_loop_body (loop); | |
432 | for (i = 0; i < loop->num_nodes; i++) | |
433 | { | |
434 | /* Irreducible region might be infinite. */ | |
435 | if (body[i]->flags & BB_IRREDUCIBLE_LOOP) | |
436 | { | |
437 | free (body); | |
438 | return false; | |
439 | } | |
440 | ||
726a989a | 441 | for (gsi = gsi_start_bb (body[i]); !gsi_end_p (gsi); gsi_next (&gsi)) |
b7eae7b8 | 442 | { |
726a989a RB |
443 | gimple stmt = gsi_stmt (gsi); |
444 | ||
b7eae7b8 | 445 | if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_VIRTUAL_DEFS) |
726a989a | 446 | || gimple_has_volatile_ops (stmt)) |
b7eae7b8 ZD |
447 | { |
448 | free (body); | |
449 | return false; | |
450 | } | |
451 | ||
452 | /* Also, asm statements and calls may have side effects and we | |
453 | cannot change the number of times they are executed. */ | |
726a989a | 454 | switch (gimple_code (stmt)) |
b7eae7b8 | 455 | { |
726a989a RB |
456 | case GIMPLE_CALL: |
457 | if (gimple_has_side_effects (stmt)) | |
b7eae7b8 ZD |
458 | { |
459 | free (body); | |
460 | return false; | |
461 | } | |
462 | break; | |
463 | ||
726a989a | 464 | case GIMPLE_ASM: |
b7eae7b8 | 465 | /* We cannot remove volatile assembler. */ |
726a989a | 466 | if (gimple_asm_volatile_p (stmt)) |
b7eae7b8 ZD |
467 | { |
468 | free (body); | |
469 | return false; | |
470 | } | |
471 | break; | |
472 | ||
473 | default: | |
474 | break; | |
475 | } | |
476 | } | |
477 | } | |
478 | free (body); | |
479 | ||
480 | return true; | |
481 | } | |
482 | ||
483 | /* Remove LOOP by making it exit in the first iteration. */ | |
484 | ||
485 | static void | |
486 | remove_empty_loop (struct loop *loop) | |
487 | { | |
37261a5c | 488 | edge exit = single_dom_exit (loop), non_exit; |
726a989a | 489 | gimple cond_stmt = last_stmt (exit->src); |
37261a5c ZD |
490 | basic_block *body; |
491 | unsigned n_before, freq_in, freq_h; | |
492 | gcov_type exit_count = exit->count; | |
493 | ||
b44e7f07 ZD |
494 | if (dump_file) |
495 | fprintf (dump_file, "Removing empty loop %d\n", loop->num); | |
496 | ||
37261a5c ZD |
497 | non_exit = EDGE_SUCC (exit->src, 0); |
498 | if (non_exit == exit) | |
499 | non_exit = EDGE_SUCC (exit->src, 1); | |
b7eae7b8 ZD |
500 | |
501 | if (exit->flags & EDGE_TRUE_VALUE) | |
726a989a | 502 | gimple_cond_make_true (cond_stmt); |
b7eae7b8 | 503 | else |
726a989a | 504 | gimple_cond_make_false (cond_stmt); |
b7eae7b8 | 505 | update_stmt (cond_stmt); |
37261a5c ZD |
506 | |
507 | /* Let us set the probabilities of the edges coming from the exit block. */ | |
508 | exit->probability = REG_BR_PROB_BASE; | |
509 | non_exit->probability = 0; | |
510 | non_exit->count = 0; | |
511 | ||
512 | /* Update frequencies and counts. Everything before | |
513 | the exit needs to be scaled FREQ_IN/FREQ_H times, | |
514 | where FREQ_IN is the frequency of the entry edge | |
515 | and FREQ_H is the frequency of the loop header. | |
516 | Everything after the exit has zero frequency. */ | |
517 | freq_h = loop->header->frequency; | |
518 | freq_in = EDGE_FREQUENCY (loop_preheader_edge (loop)); | |
519 | if (freq_h != 0) | |
520 | { | |
521 | body = get_loop_body_in_dom_order (loop); | |
522 | for (n_before = 1; n_before <= loop->num_nodes; n_before++) | |
523 | if (body[n_before - 1] == exit->src) | |
524 | break; | |
525 | scale_bbs_frequencies_int (body, n_before, freq_in, freq_h); | |
526 | scale_bbs_frequencies_int (body + n_before, loop->num_nodes - n_before, | |
527 | 0, 1); | |
528 | free (body); | |
529 | } | |
530 | ||
531 | /* Number of executions of exit is not changed, thus we need to restore | |
532 | the original value. */ | |
533 | exit->count = exit_count; | |
b7eae7b8 ZD |
534 | } |
535 | ||
536 | /* Removes LOOP if it is empty. Returns true if LOOP is removed. CHANGED | |
537 | is set to true if LOOP or any of its subloops is removed. */ | |
538 | ||
539 | static bool | |
540 | try_remove_empty_loop (struct loop *loop, bool *changed) | |
541 | { | |
542 | bool nonempty_subloop = false; | |
543 | struct loop *sub; | |
544 | ||
545 | /* First, all subloops must be removed. */ | |
546 | for (sub = loop->inner; sub; sub = sub->next) | |
547 | nonempty_subloop |= !try_remove_empty_loop (sub, changed); | |
548 | ||
549 | if (nonempty_subloop || !empty_loop_p (loop)) | |
550 | return false; | |
551 | ||
552 | remove_empty_loop (loop); | |
553 | *changed = true; | |
554 | return true; | |
555 | } | |
556 | ||
d73be268 | 557 | /* Remove the empty loops. */ |
b7eae7b8 | 558 | |
c7f965b6 | 559 | unsigned int |
d73be268 | 560 | remove_empty_loops (void) |
b7eae7b8 ZD |
561 | { |
562 | bool changed = false; | |
563 | struct loop *loop; | |
564 | ||
d73be268 | 565 | for (loop = current_loops->tree_root->inner; loop; loop = loop->next) |
b7eae7b8 ZD |
566 | try_remove_empty_loop (loop, &changed); |
567 | ||
568 | if (changed) | |
569 | { | |
570 | scev_reset (); | |
c7f965b6 | 571 | return TODO_cleanup_cfg; |
b7eae7b8 | 572 | } |
c7f965b6 | 573 | return 0; |
b7eae7b8 | 574 | } |
726a989a | 575 |