]>
Commit | Line | Data |
---|---|---|
3d436d2a | 1 | /* Natural loop analysis code for GNU compiler. |
a5544970 | 2 | Copyright (C) 2002-2019 Free Software Foundation, Inc. |
3d436d2a ZD |
3 | |
4 | This file is part of GCC. | |
5 | ||
6 | GCC is free software; you can redistribute it and/or modify it under | |
7 | the terms of the GNU General Public License as published by the Free | |
9dcd6f09 | 8 | Software Foundation; either version 3, or (at your option) any later |
3d436d2a ZD |
9 | version. |
10 | ||
11 | GCC is distributed in the hope that it will be useful, but WITHOUT ANY | |
12 | 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/>. */ | |
3d436d2a ZD |
19 | |
20 | #include "config.h" | |
21 | #include "system.h" | |
22 | #include "coretypes.h" | |
c7131fb2 | 23 | #include "backend.h" |
3d436d2a | 24 | #include "rtl.h" |
c7131fb2 | 25 | #include "tree.h" |
957060b5 | 26 | #include "predict.h" |
4d0cdd0c | 27 | #include "memmodel.h" |
957060b5 AM |
28 | #include "emit-rtl.h" |
29 | #include "cfgloop.h" | |
36566b39 | 30 | #include "explow.h" |
3d436d2a | 31 | #include "expr.h" |
66f97d31 | 32 | #include "graphds.h" |
058e97ec | 33 | #include "params.h" |
692dc070 | 34 | #include "sreal.h" |
3d436d2a | 35 | |
4391924a RS |
36 | struct target_cfgloop default_target_cfgloop; |
37 | #if SWITCHABLE_TARGET | |
38 | struct target_cfgloop *this_target_cfgloop = &default_target_cfgloop; | |
39 | #endif | |
40 | ||
3d436d2a | 41 | /* Checks whether BB is executed exactly once in each LOOP iteration. */ |
f2dca510 | 42 | |
3d436d2a | 43 | bool |
ed7a4b4b | 44 | just_once_each_iteration_p (const struct loop *loop, const_basic_block bb) |
3d436d2a ZD |
45 | { |
46 | /* It must be executed at least once each iteration. */ | |
d47cc544 | 47 | if (!dominated_by_p (CDI_DOMINATORS, loop->latch, bb)) |
3d436d2a ZD |
48 | return false; |
49 | ||
50 | /* And just once. */ | |
51 | if (bb->loop_father != loop) | |
52 | return false; | |
53 | ||
54 | /* But this was not enough. We might have some irreducible loop here. */ | |
55 | if (bb->flags & BB_IRREDUCIBLE_LOOP) | |
56 | return false; | |
57 | ||
58 | return true; | |
59 | } | |
60 | ||
35b07080 ZD |
61 | /* Marks blocks and edges that are part of non-recognized loops; i.e. we |
62 | throw away all latch edges and mark blocks inside any remaining cycle. | |
63 | Everything is a bit complicated due to fact we do not want to do this | |
64 | for parts of cycles that only "pass" through some loop -- i.e. for | |
65 | each cycle, we want to mark blocks that belong directly to innermost | |
cfbe3efe | 66 | loop containing the whole cycle. |
c22cacf3 | 67 | |
cfbe3efe ZD |
68 | LOOPS is the loop tree. */ |
69 | ||
8b1c6fd7 | 70 | #define LOOP_REPR(LOOP) ((LOOP)->num + last_basic_block_for_fn (cfun)) |
cfbe3efe ZD |
71 | #define BB_REPR(BB) ((BB)->index + 1) |
72 | ||
2de58650 | 73 | bool |
d73be268 | 74 | mark_irreducible_loops (void) |
3d436d2a | 75 | { |
3d436d2a | 76 | basic_block act; |
2de58650 | 77 | struct graph_edge *ge; |
cfbe3efe | 78 | edge e; |
628f6a4e | 79 | edge_iterator ei; |
66f97d31 ZD |
80 | int src, dest; |
81 | unsigned depth; | |
cfbe3efe | 82 | struct graph *g; |
0fc822d0 | 83 | int num = number_of_loops (cfun); |
66f97d31 | 84 | struct loop *cloop; |
2de58650 JH |
85 | bool irred_loop_found = false; |
86 | int i; | |
3d436d2a | 87 | |
d51157de ZD |
88 | gcc_assert (current_loops != NULL); |
89 | ||
35b07080 | 90 | /* Reset the flags. */ |
fefa31b5 DM |
91 | FOR_BB_BETWEEN (act, ENTRY_BLOCK_PTR_FOR_FN (cfun), |
92 | EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb) | |
35b07080 ZD |
93 | { |
94 | act->flags &= ~BB_IRREDUCIBLE_LOOP; | |
628f6a4e | 95 | FOR_EACH_EDGE (e, ei, act->succs) |
35b07080 ZD |
96 | e->flags &= ~EDGE_IRREDUCIBLE_LOOP; |
97 | } | |
98 | ||
3d436d2a | 99 | /* Create the edge lists. */ |
8b1c6fd7 | 100 | g = new_graph (last_basic_block_for_fn (cfun) + num); |
cfbe3efe | 101 | |
fefa31b5 DM |
102 | FOR_BB_BETWEEN (act, ENTRY_BLOCK_PTR_FOR_FN (cfun), |
103 | EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb) | |
628f6a4e | 104 | FOR_EACH_EDGE (e, ei, act->succs) |
3d436d2a | 105 | { |
c22cacf3 | 106 | /* Ignore edges to exit. */ |
fefa31b5 | 107 | if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun)) |
3d436d2a | 108 | continue; |
cfbe3efe | 109 | |
598ec7bd ZD |
110 | src = BB_REPR (act); |
111 | dest = BB_REPR (e->dest); | |
cfbe3efe | 112 | |
d51157de ZD |
113 | /* Ignore latch edges. */ |
114 | if (e->dest->loop_father->header == e->dest | |
115 | && e->dest->loop_father->latch == act) | |
116 | continue; | |
117 | ||
118 | /* Edges inside a single loop should be left where they are. Edges | |
119 | to subloop headers should lead to representative of the subloop, | |
120 | but from the same place. | |
cfbe3efe | 121 | |
d51157de ZD |
122 | Edges exiting loops should lead from representative |
123 | of the son of nearest common ancestor of the loops in that | |
124 | act lays. */ | |
125 | ||
126 | if (e->dest->loop_father->header == e->dest) | |
127 | dest = LOOP_REPR (e->dest->loop_father); | |
128 | ||
129 | if (!flow_bb_inside_loop_p (act->loop_father, e->dest)) | |
130 | { | |
131 | depth = 1 + loop_depth (find_common_loop (act->loop_father, | |
132 | e->dest->loop_father)); | |
133 | if (depth == loop_depth (act->loop_father)) | |
134 | cloop = act->loop_father; | |
135 | else | |
9771b263 | 136 | cloop = (*act->loop_father->superloops)[depth]; |
d51157de ZD |
137 | |
138 | src = LOOP_REPR (cloop); | |
3d436d2a | 139 | } |
cfbe3efe | 140 | |
66f97d31 | 141 | add_edge (g, src, dest)->data = e; |
3d436d2a ZD |
142 | } |
143 | ||
66f97d31 ZD |
144 | /* Find the strongly connected components. */ |
145 | graphds_scc (g, NULL); | |
3d436d2a | 146 | |
cfbe3efe | 147 | /* Mark the irreducible loops. */ |
2de58650 JH |
148 | for (i = 0; i < g->n_vertices; i++) |
149 | for (ge = g->vertices[i].succ; ge; ge = ge->succ_next) | |
150 | { | |
151 | edge real = (edge) ge->data; | |
152 | /* edge E in graph G is irreducible if it connects two vertices in the | |
153 | same scc. */ | |
154 | ||
155 | /* All edges should lead from a component with higher number to the | |
156 | one with lower one. */ | |
157 | gcc_assert (g->vertices[ge->src].component >= g->vertices[ge->dest].component); | |
158 | ||
159 | if (g->vertices[ge->src].component != g->vertices[ge->dest].component) | |
160 | continue; | |
161 | ||
162 | real->flags |= EDGE_IRREDUCIBLE_LOOP; | |
163 | irred_loop_found = true; | |
164 | if (flow_bb_inside_loop_p (real->src->loop_father, real->dest)) | |
165 | real->src->flags |= BB_IRREDUCIBLE_LOOP; | |
166 | } | |
3d436d2a | 167 | |
cfbe3efe | 168 | free_graph (g); |
3d436d2a | 169 | |
f87000d0 | 170 | loops_state_set (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS); |
2de58650 | 171 | return irred_loop_found; |
3d436d2a ZD |
172 | } |
173 | ||
174 | /* Counts number of insns inside LOOP. */ | |
175 | int | |
ed7a4b4b | 176 | num_loop_insns (const struct loop *loop) |
3d436d2a ZD |
177 | { |
178 | basic_block *bbs, bb; | |
179 | unsigned i, ninsns = 0; | |
1f75b71e | 180 | rtx_insn *insn; |
3d436d2a ZD |
181 | |
182 | bbs = get_loop_body (loop); | |
183 | for (i = 0; i < loop->num_nodes; i++) | |
184 | { | |
185 | bb = bbs[i]; | |
b5b8b0ac AO |
186 | FOR_BB_INSNS (bb, insn) |
187 | if (NONDEBUG_INSN_P (insn)) | |
91f4cfe3 | 188 | ninsns++; |
3d436d2a | 189 | } |
53a51cef JJ |
190 | free (bbs); |
191 | ||
192 | if (!ninsns) | |
193 | ninsns = 1; /* To avoid division by zero. */ | |
d329e058 | 194 | |
3d436d2a ZD |
195 | return ninsns; |
196 | } | |
197 | ||
198 | /* Counts number of insns executed on average per iteration LOOP. */ | |
199 | int | |
ed7a4b4b | 200 | average_num_loop_insns (const struct loop *loop) |
3d436d2a ZD |
201 | { |
202 | basic_block *bbs, bb; | |
692dc070 JH |
203 | unsigned i, binsns; |
204 | sreal ninsns; | |
1f75b71e | 205 | rtx_insn *insn; |
3d436d2a ZD |
206 | |
207 | ninsns = 0; | |
208 | bbs = get_loop_body (loop); | |
209 | for (i = 0; i < loop->num_nodes; i++) | |
210 | { | |
211 | bb = bbs[i]; | |
212 | ||
b5b8b0ac AO |
213 | binsns = 0; |
214 | FOR_BB_INSNS (bb, insn) | |
215 | if (NONDEBUG_INSN_P (insn)) | |
91f4cfe3 | 216 | binsns++; |
3d436d2a | 217 | |
692dc070 JH |
218 | ninsns += (sreal)binsns * bb->count.to_sreal_scale (loop->header->count); |
219 | /* Avoid overflows. */ | |
220 | if (ninsns > 1000000) | |
221 | return 100000; | |
3d436d2a | 222 | } |
53a51cef | 223 | free (bbs); |
d329e058 | 224 | |
692dc070 JH |
225 | int64_t ret = ninsns.to_int (); |
226 | if (!ret) | |
227 | ret = 1; /* To avoid division by zero. */ | |
3d436d2a | 228 | |
692dc070 | 229 | return ret; |
3d436d2a ZD |
230 | } |
231 | ||
ac84e05e | 232 | /* Returns expected number of iterations of LOOP, according to |
65739a68 JH |
233 | measured or guessed profile. |
234 | ||
235 | This functions attempts to return "sane" value even if profile | |
236 | information is not good enough to derive osmething. | |
237 | If BY_PROFILE_ONLY is set, this logic is bypassed and function | |
238 | return -1 in those scenarios. */ | |
ac84e05e ZD |
239 | |
240 | gcov_type | |
199b1891 | 241 | expected_loop_iterations_unbounded (const struct loop *loop, |
65739a68 JH |
242 | bool *read_profile_p, |
243 | bool by_profile_only) | |
3d436d2a ZD |
244 | { |
245 | edge e; | |
628f6a4e | 246 | edge_iterator ei; |
3995f3a2 | 247 | gcov_type expected = -1; |
97c53806 | 248 | |
199b1891 ML |
249 | if (read_profile_p) |
250 | *read_profile_p = false; | |
97c53806 | 251 | |
4661839e | 252 | /* If we have no profile at all, use AVG_LOOP_NITER. */ |
97c53806 | 253 | if (profile_status_for_fn (cfun) == PROFILE_ABSENT) |
65739a68 JH |
254 | { |
255 | if (by_profile_only) | |
256 | return -1; | |
257 | expected = PARAM_VALUE (PARAM_AVG_LOOP_NITER); | |
258 | } | |
e7a74006 JH |
259 | else if (loop->latch && (loop->latch->count.initialized_p () |
260 | || loop->header->count.initialized_p ())) | |
3d436d2a | 261 | { |
3995f3a2 JH |
262 | profile_count count_in = profile_count::zero (), |
263 | count_latch = profile_count::zero (); | |
3d436d2a | 264 | |
628f6a4e | 265 | FOR_EACH_EDGE (e, ei, loop->header->preds) |
3d436d2a | 266 | if (e->src == loop->latch) |
ef30ab83 | 267 | count_latch = e->count (); |
3d436d2a | 268 | else |
ef30ab83 | 269 | count_in += e->count (); |
3d436d2a | 270 | |
3995f3a2 | 271 | if (!count_latch.initialized_p ()) |
65739a68 JH |
272 | { |
273 | if (by_profile_only) | |
274 | return -1; | |
275 | expected = PARAM_VALUE (PARAM_AVG_LOOP_NITER); | |
276 | } | |
e7a74006 | 277 | else if (!count_in.nonzero_p ()) |
65739a68 JH |
278 | { |
279 | if (by_profile_only) | |
280 | return -1; | |
281 | expected = count_latch.to_gcov_type () * 2; | |
282 | } | |
bade3a00 | 283 | else |
199b1891 | 284 | { |
3995f3a2 JH |
285 | expected = (count_latch.to_gcov_type () + count_in.to_gcov_type () |
286 | - 1) / count_in.to_gcov_type (); | |
e7a74006 JH |
287 | if (read_profile_p |
288 | && count_latch.reliable_p () && count_in.reliable_p ()) | |
199b1891 ML |
289 | *read_profile_p = true; |
290 | } | |
3d436d2a | 291 | } |
e7a74006 | 292 | else |
65739a68 JH |
293 | { |
294 | if (by_profile_only) | |
295 | return -1; | |
296 | expected = PARAM_VALUE (PARAM_AVG_LOOP_NITER); | |
297 | } | |
97c53806 | 298 | |
65739a68 JH |
299 | if (!by_profile_only) |
300 | { | |
301 | HOST_WIDE_INT max = get_max_loop_iterations_int (loop); | |
302 | if (max != -1 && max < expected) | |
303 | return max; | |
304 | } | |
e7a74006 | 305 | |
97c53806 | 306 | return expected; |
3d436d2a | 307 | } |
689ba89d | 308 | |
ac84e05e ZD |
309 | /* Returns expected number of LOOP iterations. The returned value is bounded |
310 | by REG_BR_PROB_BASE. */ | |
311 | ||
312 | unsigned | |
97c53806 | 313 | expected_loop_iterations (struct loop *loop) |
ac84e05e ZD |
314 | { |
315 | gcov_type expected = expected_loop_iterations_unbounded (loop); | |
316 | return (expected > REG_BR_PROB_BASE ? REG_BR_PROB_BASE : expected); | |
317 | } | |
318 | ||
689ba89d ZD |
319 | /* Returns the maximum level of nesting of subloops of LOOP. */ |
320 | ||
321 | unsigned | |
322 | get_loop_level (const struct loop *loop) | |
323 | { | |
324 | const struct loop *ploop; | |
325 | unsigned mx = 0, l; | |
326 | ||
327 | for (ploop = loop->inner; ploop; ploop = ploop->next) | |
328 | { | |
329 | l = get_loop_level (ploop); | |
330 | if (l >= mx) | |
331 | mx = l + 1; | |
332 | } | |
333 | return mx; | |
334 | } | |
5e962776 | 335 | |
5e962776 ZD |
336 | /* Initialize the constants for computing set costs. */ |
337 | ||
338 | void | |
339 | init_set_costs (void) | |
340 | { | |
f40751dd | 341 | int speed; |
1f75b71e | 342 | rtx_insn *seq; |
c3dc5e66 RS |
343 | rtx reg1 = gen_raw_REG (SImode, LAST_VIRTUAL_REGISTER + 1); |
344 | rtx reg2 = gen_raw_REG (SImode, LAST_VIRTUAL_REGISTER + 2); | |
345 | rtx addr = gen_raw_REG (Pmode, LAST_VIRTUAL_REGISTER + 3); | |
5e962776 ZD |
346 | rtx mem = validize_mem (gen_rtx_MEM (SImode, addr)); |
347 | unsigned i; | |
348 | ||
b5deb7b6 | 349 | target_avail_regs = 0; |
bec922f0 | 350 | target_clobbered_regs = 0; |
5e962776 ZD |
351 | for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) |
352 | if (TEST_HARD_REG_BIT (reg_class_contents[GENERAL_REGS], i) | |
353 | && !fixed_regs[i]) | |
bec922f0 SL |
354 | { |
355 | target_avail_regs++; | |
356 | if (call_used_regs[i]) | |
357 | target_clobbered_regs++; | |
358 | } | |
5e962776 | 359 | |
8b11a64c | 360 | target_res_regs = 3; |
5e962776 | 361 | |
f40751dd JH |
362 | for (speed = 0; speed < 2; speed++) |
363 | { | |
364 | crtl->maybe_hot_insn_p = speed; | |
365 | /* Set up the costs for using extra registers: | |
366 | ||
367 | 1) If not many free registers remain, we should prefer having an | |
368 | additional move to decreasing the number of available registers. | |
369 | (TARGET_REG_COST). | |
370 | 2) If no registers are available, we need to spill, which may require | |
371 | storing the old value to memory and loading it back | |
372 | (TARGET_SPILL_COST). */ | |
373 | ||
374 | start_sequence (); | |
375 | emit_move_insn (reg1, reg2); | |
376 | seq = get_insns (); | |
377 | end_sequence (); | |
378 | target_reg_cost [speed] = seq_cost (seq, speed); | |
379 | ||
380 | start_sequence (); | |
381 | emit_move_insn (mem, reg1); | |
382 | emit_move_insn (reg2, mem); | |
383 | seq = get_insns (); | |
384 | end_sequence (); | |
385 | target_spill_cost [speed] = seq_cost (seq, speed); | |
386 | } | |
387 | default_rtl_profile (); | |
5e962776 ZD |
388 | } |
389 | ||
a154b43a ZD |
390 | /* Estimates cost of increased register pressure caused by making N_NEW new |
391 | registers live around the loop. N_OLD is the number of registers live | |
bec922f0 SL |
392 | around the loop. If CALL_P is true, also take into account that |
393 | call-used registers may be clobbered in the loop body, reducing the | |
394 | number of available registers before we spill. */ | |
5e962776 ZD |
395 | |
396 | unsigned | |
bec922f0 SL |
397 | estimate_reg_pressure_cost (unsigned n_new, unsigned n_old, bool speed, |
398 | bool call_p) | |
5e962776 | 399 | { |
058e97ec | 400 | unsigned cost; |
a154b43a | 401 | unsigned regs_needed = n_new + n_old; |
bec922f0 SL |
402 | unsigned available_regs = target_avail_regs; |
403 | ||
404 | /* If there is a call in the loop body, the call-clobbered registers | |
405 | are not available for loop invariants. */ | |
406 | if (call_p) | |
407 | available_regs = available_regs - target_clobbered_regs; | |
5e962776 | 408 | |
a154b43a ZD |
409 | /* If we have enough registers, we should use them and not restrict |
410 | the transformations unnecessarily. */ | |
bec922f0 | 411 | if (regs_needed + target_res_regs <= available_regs) |
a154b43a ZD |
412 | return 0; |
413 | ||
bec922f0 | 414 | if (regs_needed <= available_regs) |
058e97ec VM |
415 | /* If we are close to running out of registers, try to preserve |
416 | them. */ | |
f40751dd | 417 | cost = target_reg_cost [speed] * n_new; |
058e97ec VM |
418 | else |
419 | /* If we run out of registers, it is very expensive to add another | |
420 | one. */ | |
f40751dd | 421 | cost = target_spill_cost [speed] * n_new; |
058e97ec | 422 | |
2af2dbdc VM |
423 | if (optimize && (flag_ira_region == IRA_REGION_ALL |
424 | || flag_ira_region == IRA_REGION_MIXED) | |
0fc822d0 | 425 | && number_of_loops (cfun) <= (unsigned) IRA_MAX_LOOPS_NUM) |
058e97ec VM |
426 | /* IRA regional allocation deals with high register pressure |
427 | better. So decrease the cost (to do more accurate the cost | |
428 | calculation for IRA, we need to know how many registers lives | |
429 | through the loop transparently). */ | |
430 | cost /= 2; | |
431 | ||
432 | return cost; | |
5e962776 ZD |
433 | } |
434 | ||
d73be268 | 435 | /* Sets EDGE_LOOP_EXIT flag for all loop exits. */ |
70388d94 ZD |
436 | |
437 | void | |
d73be268 | 438 | mark_loop_exit_edges (void) |
70388d94 ZD |
439 | { |
440 | basic_block bb; | |
441 | edge e; | |
c22cacf3 | 442 | |
0fc822d0 | 443 | if (number_of_loops (cfun) <= 1) |
70388d94 ZD |
444 | return; |
445 | ||
11cd3bed | 446 | FOR_EACH_BB_FN (bb, cfun) |
70388d94 ZD |
447 | { |
448 | edge_iterator ei; | |
449 | ||
70388d94 ZD |
450 | FOR_EACH_EDGE (e, ei, bb->succs) |
451 | { | |
9ba025a2 | 452 | if (loop_outer (bb->loop_father) |
2ff3e325 | 453 | && loop_exit_edge_p (bb->loop_father, e)) |
70388d94 ZD |
454 | e->flags |= EDGE_LOOP_EXIT; |
455 | else | |
456 | e->flags &= ~EDGE_LOOP_EXIT; | |
457 | } | |
458 | } | |
459 | } | |
460 | ||
f9bf4777 JH |
461 | /* Return exit edge if loop has only one exit that is likely |
462 | to be executed on runtime (i.e. it is not EH or leading | |
463 | to noreturn call. */ | |
464 | ||
465 | edge | |
466 | single_likely_exit (struct loop *loop) | |
467 | { | |
468 | edge found = single_exit (loop); | |
9771b263 | 469 | vec<edge> exits; |
f9bf4777 JH |
470 | unsigned i; |
471 | edge ex; | |
472 | ||
473 | if (found) | |
474 | return found; | |
475 | exits = get_loop_exit_edges (loop); | |
9771b263 | 476 | FOR_EACH_VEC_ELT (exits, i, ex) |
f9bf4777 | 477 | { |
af2bbc51 JH |
478 | if (probably_never_executed_edge_p (cfun, ex) |
479 | /* We want to rule out paths to noreturns but not low probabilities | |
480 | resulting from adjustments or combining. | |
481 | FIXME: once we have better quality tracking, make this more | |
482 | robust. */ | |
483 | || ex->probability <= profile_probability::very_unlikely ()) | |
f9bf4777 JH |
484 | continue; |
485 | if (!found) | |
486 | found = ex; | |
487 | else | |
488 | { | |
9771b263 | 489 | exits.release (); |
f9bf4777 JH |
490 | return NULL; |
491 | } | |
492 | } | |
9771b263 | 493 | exits.release (); |
f9bf4777 JH |
494 | return found; |
495 | } | |
519cac4a JH |
496 | |
497 | ||
498 | /* Gets basic blocks of a LOOP. Header is the 0-th block, rest is in dfs | |
499 | order against direction of edges from latch. Specially, if | |
500 | header != latch, latch is the 1-st block. */ | |
501 | ||
9771b263 | 502 | vec<basic_block> |
519cac4a JH |
503 | get_loop_hot_path (const struct loop *loop) |
504 | { | |
505 | basic_block bb = loop->header; | |
6e1aa848 | 506 | vec<basic_block> path = vNULL; |
519cac4a JH |
507 | bitmap visited = BITMAP_ALLOC (NULL); |
508 | ||
509 | while (true) | |
510 | { | |
511 | edge_iterator ei; | |
512 | edge e; | |
513 | edge best = NULL; | |
514 | ||
9771b263 | 515 | path.safe_push (bb); |
519cac4a JH |
516 | bitmap_set_bit (visited, bb->index); |
517 | FOR_EACH_EDGE (e, ei, bb->succs) | |
518 | if ((!best || e->probability > best->probability) | |
519 | && !loop_exit_edge_p (loop, e) | |
520 | && !bitmap_bit_p (visited, e->dest->index)) | |
521 | best = e; | |
522 | if (!best || best->dest == loop->header) | |
523 | break; | |
524 | bb = best->dest; | |
525 | } | |
526 | BITMAP_FREE (visited); | |
527 | return path; | |
528 | } |