|
0
|
1 /* Induction variable canonicalization.
|
|
|
2 Copyright (C) 2004, 2005, 2007, 2008 Free Software Foundation, Inc.
|
|
|
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
|
|
|
8 Free Software Foundation; either version 3, or (at your option) any
|
|
|
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
|
|
|
17 along with GCC; see the file COPYING3. If not see
|
|
|
18 <http://www.gnu.org/licenses/>. */
|
|
|
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
|
|
|
57 /* Specifies types of loops that may be unrolled. */
|
|
|
58
|
|
|
59 enum unroll_level
|
|
|
60 {
|
|
|
61 UL_SINGLE_ITER, /* Only loops that exit immediately in the first
|
|
|
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
|
|
|
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;
|
|
|
75 tree type, var;
|
|
|
76 gimple cond;
|
|
|
77 gimple_stmt_iterator incr_at;
|
|
|
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);
|
|
|
88 in = EDGE_SUCC (exit->src, 0);
|
|
|
89 if (in == exit)
|
|
|
90 in = EDGE_SUCC (exit->src, 1);
|
|
|
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);
|
|
|
98 niter = fold_build2 (PLUS_EXPR, type,
|
|
|
99 niter,
|
|
|
100 build_int_cst (type, 1));
|
|
|
101 incr_at = gsi_last_bb (in->src);
|
|
|
102 create_iv (niter,
|
|
|
103 build_int_cst (type, -1),
|
|
|
104 NULL_TREE, loop,
|
|
|
105 &incr_at, false, NULL, &var);
|
|
|
106
|
|
|
107 cmp = (exit->flags & EDGE_TRUE_VALUE) ? EQ_EXPR : NE_EXPR;
|
|
|
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));
|
|
|
111 update_stmt (cond);
|
|
|
112 }
|
|
|
113
|
|
|
114 /* Computes an estimated number of insns in LOOP, weighted by WEIGHTS. */
|
|
|
115
|
|
|
116 unsigned
|
|
|
117 tree_num_loop_insns (struct loop *loop, eni_weights *weights)
|
|
|
118 {
|
|
|
119 basic_block *body = get_loop_body (loop);
|
|
|
120 gimple_stmt_iterator gsi;
|
|
|
121 unsigned size = 1, i;
|
|
|
122
|
|
|
123 for (i = 0; i < loop->num_nodes; i++)
|
|
|
124 for (gsi = gsi_start_bb (body[i]); !gsi_end_p (gsi); gsi_next (&gsi))
|
|
|
125 size += estimate_num_insns (gsi_stmt (gsi), weights);
|
|
|
126 free (body);
|
|
|
127
|
|
|
128 return size;
|
|
|
129 }
|
|
|
130
|
|
|
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
|
|
|
157 /* Tries to unroll LOOP completely, i.e. NITER times.
|
|
|
158 UL determines which loops we are allowed to unroll.
|
|
|
159 EXIT is the exit of the loop that should be eliminated. */
|
|
|
160
|
|
|
161 static bool
|
|
|
162 try_unroll_loop_completely (struct loop *loop,
|
|
|
163 edge exit, tree niter,
|
|
|
164 enum unroll_level ul)
|
|
|
165 {
|
|
|
166 unsigned HOST_WIDE_INT n_unroll, ninsns, max_unroll, unr_insns;
|
|
|
167 gimple cond;
|
|
|
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 {
|
|
|
182 if (ul == UL_SINGLE_ITER)
|
|
|
183 return false;
|
|
|
184
|
|
|
185 ninsns = tree_num_loop_insns (loop, &eni_size_weights);
|
|
|
186
|
|
|
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
|
|
|
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
|
|
|
206 if (ul == UL_NO_GROWTH
|
|
|
207 && unr_insns > ninsns)
|
|
|
208 {
|
|
|
209 if (dump_file && (dump_flags & TDF_DETAILS))
|
|
|
210 fprintf (dump_file, "Not unrolling loop %d.\n", loop->num);
|
|
|
211 return false;
|
|
|
212 }
|
|
|
213 }
|
|
|
214
|
|
|
215 if (n_unroll)
|
|
|
216 {
|
|
|
217 sbitmap wont_exit;
|
|
|
218 edge e;
|
|
|
219 unsigned i;
|
|
|
220 VEC (edge, heap) *to_remove = NULL;
|
|
|
221
|
|
|
222 initialize_original_copy_tables ();
|
|
|
223 wont_exit = sbitmap_alloc (n_unroll + 1);
|
|
|
224 sbitmap_ones (wont_exit);
|
|
|
225 RESET_BIT (wont_exit, 0);
|
|
|
226
|
|
|
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))
|
|
|
232 {
|
|
|
233 free_original_copy_tables ();
|
|
|
234 free (wont_exit);
|
|
|
235 return false;
|
|
|
236 }
|
|
|
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);
|
|
|
245 free (wont_exit);
|
|
|
246 free_original_copy_tables ();
|
|
|
247 }
|
|
|
248
|
|
|
249 cond = last_stmt (exit->src);
|
|
|
250 if (exit->flags & EDGE_TRUE_VALUE)
|
|
|
251 gimple_cond_make_true (cond);
|
|
|
252 else
|
|
|
253 gimple_cond_make_false (cond);
|
|
|
254 update_stmt (cond);
|
|
|
255 update_ssa (TODO_update_ssa);
|
|
|
256
|
|
|
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
|
|
|
263 /* Adds a canonical induction variable to LOOP if suitable.
|
|
|
264 CREATE_IV is true if we may create a new iv. UL determines
|
|
|
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. */
|
|
|
268
|
|
|
269 static bool
|
|
|
270 canonicalize_loop_induction_variables (struct loop *loop,
|
|
|
271 bool create_iv, enum unroll_level ul,
|
|
|
272 bool try_eval)
|
|
|
273 {
|
|
|
274 edge exit = NULL;
|
|
|
275 tree niter;
|
|
|
276
|
|
|
277 niter = number_of_latch_executions (loop);
|
|
|
278 if (TREE_CODE (niter) == INTEGER_CST)
|
|
|
279 {
|
|
|
280 exit = single_exit (loop);
|
|
|
281 if (!just_once_each_iteration_p (loop, exit->src))
|
|
|
282 return false;
|
|
|
283 }
|
|
|
284 else
|
|
|
285 {
|
|
|
286 /* If the loop has more than one exit, try checking all of them
|
|
|
287 for # of iterations determinable through scev. */
|
|
|
288 if (!single_exit (loop))
|
|
|
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 }
|
|
|
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
|
|
|
309 if (try_unroll_loop_completely (loop, exit, niter, ul))
|
|
|
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
|
|
|
319 to the suitable loops. */
|
|
|
320
|
|
|
321 unsigned int
|
|
|
322 canonicalize_induction_variables (void)
|
|
|
323 {
|
|
|
324 loop_iterator li;
|
|
|
325 struct loop *loop;
|
|
|
326 bool changed = false;
|
|
|
327
|
|
|
328 FOR_EACH_LOOP (li, loop, 0)
|
|
|
329 {
|
|
|
330 changed |= canonicalize_loop_induction_variables (loop,
|
|
|
331 true, UL_SINGLE_ITER,
|
|
|
332 true);
|
|
|
333 }
|
|
|
334
|
|
|
335 /* Clean up the information about numbers of iterations, since brute force
|
|
|
336 evaluation could reveal new information. */
|
|
|
337 scev_reset ();
|
|
|
338
|
|
|
339 if (changed)
|
|
|
340 return TODO_cleanup_cfg;
|
|
|
341 return 0;
|
|
|
342 }
|
|
|
343
|
|
|
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. */
|
|
|
347
|
|
|
348 unsigned int
|
|
|
349 tree_unroll_loops_completely (bool may_increase_size, bool unroll_outer)
|
|
|
350 {
|
|
|
351 loop_iterator li;
|
|
|
352 struct loop *loop;
|
|
|
353 bool changed;
|
|
|
354 enum unroll_level ul;
|
|
|
355
|
|
|
356 do
|
|
|
357 {
|
|
|
358 changed = false;
|
|
|
359
|
|
|
360 FOR_EACH_LOOP (li, loop, LI_ONLY_INNERMOST)
|
|
|
361 {
|
|
|
362 if (may_increase_size && optimize_loop_for_speed_p (loop)
|
|
|
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. */
|
|
|
379 if (cleanup_tree_cfg ())
|
|
|
380 update_ssa (TODO_update_ssa_only_virtuals);
|
|
|
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);
|
|
|
388
|
|
|
389 return 0;
|
|
|
390 }
|
|
|
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;
|
|
|
399 basic_block *body;
|
|
|
400 gimple_stmt_iterator gsi;
|
|
|
401 unsigned i;
|
|
|
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. */
|
|
|
411 if (!number_of_iterations_exit (loop, exit, &niter, false))
|
|
|
412 return false;
|
|
|
413
|
|
|
414 /* Values of all loop exit phi nodes must be invariants. */
|
|
|
415 for (gsi = gsi_start(phi_nodes (exit->dest)); !gsi_end_p (gsi); gsi_next (&gsi))
|
|
|
416 {
|
|
|
417 gimple phi = gsi_stmt (gsi);
|
|
|
418 tree def;
|
|
|
419
|
|
|
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
|
|
|
441 for (gsi = gsi_start_bb (body[i]); !gsi_end_p (gsi); gsi_next (&gsi))
|
|
|
442 {
|
|
|
443 gimple stmt = gsi_stmt (gsi);
|
|
|
444
|
|
|
445 if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_VIRTUAL_DEFS)
|
|
|
446 || gimple_has_volatile_ops (stmt))
|
|
|
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. */
|
|
|
454 switch (gimple_code (stmt))
|
|
|
455 {
|
|
|
456 case GIMPLE_CALL:
|
|
|
457 if (gimple_has_side_effects (stmt))
|
|
|
458 {
|
|
|
459 free (body);
|
|
|
460 return false;
|
|
|
461 }
|
|
|
462 break;
|
|
|
463
|
|
|
464 case GIMPLE_ASM:
|
|
|
465 /* We cannot remove volatile assembler. */
|
|
|
466 if (gimple_asm_volatile_p (stmt))
|
|
|
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 {
|
|
|
488 edge exit = single_dom_exit (loop), non_exit;
|
|
|
489 gimple cond_stmt = last_stmt (exit->src);
|
|
|
490 basic_block *body;
|
|
|
491 unsigned n_before, freq_in, freq_h;
|
|
|
492 gcov_type exit_count = exit->count;
|
|
|
493
|
|
|
494 if (dump_file)
|
|
|
495 fprintf (dump_file, "Removing empty loop %d\n", loop->num);
|
|
|
496
|
|
|
497 non_exit = EDGE_SUCC (exit->src, 0);
|
|
|
498 if (non_exit == exit)
|
|
|
499 non_exit = EDGE_SUCC (exit->src, 1);
|
|
|
500
|
|
|
501 if (exit->flags & EDGE_TRUE_VALUE)
|
|
|
502 gimple_cond_make_true (cond_stmt);
|
|
|
503 else
|
|
|
504 gimple_cond_make_false (cond_stmt);
|
|
|
505 update_stmt (cond_stmt);
|
|
|
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;
|
|
|
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
|
|
|
557 /* Remove the empty loops. */
|
|
|
558
|
|
|
559 unsigned int
|
|
|
560 remove_empty_loops (void)
|
|
|
561 {
|
|
|
562 bool changed = false;
|
|
|
563 struct loop *loop;
|
|
|
564
|
|
|
565 for (loop = current_loops->tree_root->inner; loop; loop = loop->next)
|
|
|
566 try_remove_empty_loop (loop, &changed);
|
|
|
567
|
|
|
568 if (changed)
|
|
|
569 {
|
|
|
570 scev_reset ();
|
|
|
571 return TODO_cleanup_cfg;
|
|
|
572 }
|
|
|
573 return 0;
|
|
|
574 }
|
|
|
575
|
