Branch data Line data Source code
1 : : /* Natural loop analysis code for GNU compiler.
2 : : Copyright (C) 2002-2025 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 under
7 : : the terms of the GNU General Public License as published by the Free
8 : : Software Foundation; either version 3, or (at your option) any later
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
17 : : along with GCC; see the file COPYING3. If not see
18 : : <http://www.gnu.org/licenses/>. */
19 : :
20 : : #include "config.h"
21 : : #include "system.h"
22 : : #include "coretypes.h"
23 : : #include "backend.h"
24 : : #include "rtl.h"
25 : : #include "tree.h"
26 : : #include "predict.h"
27 : : #include "memmodel.h"
28 : : #include "emit-rtl.h"
29 : : #include "cfgloop.h"
30 : : #include "explow.h"
31 : : #include "expr.h"
32 : : #include "graphds.h"
33 : : #include "sreal.h"
34 : : #include "regs.h"
35 : : #include "function-abi.h"
36 : :
37 : : struct target_cfgloop default_target_cfgloop;
38 : : #if SWITCHABLE_TARGET
39 : : struct target_cfgloop *this_target_cfgloop = &default_target_cfgloop;
40 : : #endif
41 : :
42 : : /* Checks whether BB is executed exactly once in each LOOP iteration. */
43 : :
44 : : bool
45 : 4349816 : just_once_each_iteration_p (const class loop *loop, const_basic_block bb)
46 : : {
47 : : /* It must be executed at least once each iteration. */
48 : 4349816 : if (!dominated_by_p (CDI_DOMINATORS, loop->latch, bb))
49 : : return false;
50 : :
51 : : /* And just once. */
52 : 3817965 : if (bb->loop_father != loop)
53 : : return false;
54 : :
55 : : /* But this was not enough. We might have some irreducible loop here. */
56 : 3796203 : if (bb->flags & BB_IRREDUCIBLE_LOOP)
57 : 21 : return false;
58 : :
59 : : return true;
60 : : }
61 : :
62 : : /* Marks blocks and edges that are part of non-recognized loops; i.e. we
63 : : throw away all latch edges and mark blocks inside any remaining cycle.
64 : : Everything is a bit complicated due to fact we do not want to do this
65 : : for parts of cycles that only "pass" through some loop -- i.e. for
66 : : each cycle, we want to mark blocks that belong directly to innermost
67 : : loop containing the whole cycle.
68 : :
69 : : LOOPS is the loop tree. */
70 : :
71 : : #define LOOP_REPR(LOOP) ((LOOP)->num + last_basic_block_for_fn (cfun))
72 : : #define BB_REPR(BB) ((BB)->index + 1)
73 : :
74 : : bool
75 : 58187741 : mark_irreducible_loops (void)
76 : : {
77 : 58187741 : basic_block act;
78 : 58187741 : struct graph_edge *ge;
79 : 58187741 : edge e;
80 : 58187741 : edge_iterator ei;
81 : 58187741 : int src, dest;
82 : 58187741 : unsigned depth;
83 : 58187741 : struct graph *g;
84 : 58187741 : int num = number_of_loops (cfun);
85 : 58187741 : class loop *cloop;
86 : 58187741 : bool irred_loop_found = false;
87 : 58187741 : int i;
88 : :
89 : 58187741 : gcc_assert (current_loops != NULL);
90 : :
91 : : /* Reset the flags. */
92 : 732716017 : FOR_BB_BETWEEN (act, ENTRY_BLOCK_PTR_FOR_FN (cfun),
93 : : EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb)
94 : : {
95 : 674528276 : act->flags &= ~BB_IRREDUCIBLE_LOOP;
96 : 1593495812 : FOR_EACH_EDGE (e, ei, act->succs)
97 : 918967536 : e->flags &= ~EDGE_IRREDUCIBLE_LOOP;
98 : : }
99 : :
100 : : /* Create the edge lists. */
101 : 58187741 : g = new_graph (last_basic_block_for_fn (cfun) + num);
102 : :
103 : 732716017 : FOR_BB_BETWEEN (act, ENTRY_BLOCK_PTR_FOR_FN (cfun),
104 : : EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb)
105 : 1593495812 : FOR_EACH_EDGE (e, ei, act->succs)
106 : : {
107 : : /* Ignore edges to exit. */
108 : 918967536 : if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
109 : 57232437 : continue;
110 : :
111 : 861735099 : src = BB_REPR (act);
112 : 861735099 : dest = BB_REPR (e->dest);
113 : :
114 : : /* Ignore latch edges. */
115 : 901719403 : if (e->dest->loop_father->header == e->dest
116 : 861735099 : && dominated_by_p (CDI_DOMINATORS, act, e->dest))
117 : 39984304 : continue;
118 : :
119 : : /* Edges inside a single loop should be left where they are. Edges
120 : : to subloop headers should lead to representative of the subloop,
121 : : but from the same place.
122 : :
123 : : Edges exiting loops should lead from representative
124 : : of the son of nearest common ancestor of the loops in that
125 : : act lays. */
126 : :
127 : 821750795 : if (e->dest->loop_father->header == e->dest)
128 : 39984632 : dest = LOOP_REPR (e->dest->loop_father);
129 : :
130 : 821750795 : if (!flow_bb_inside_loop_p (act->loop_father, e->dest))
131 : : {
132 : 71693486 : depth = 1 + loop_depth (find_common_loop (act->loop_father,
133 : 71693486 : e->dest->loop_father));
134 : 143386972 : if (depth == loop_depth (act->loop_father))
135 : : cloop = act->loop_father;
136 : : else
137 : 4842299 : cloop = (*act->loop_father->superloops)[depth];
138 : :
139 : 71693486 : src = LOOP_REPR (cloop);
140 : : }
141 : :
142 : 821750795 : add_edge (g, src, dest)->data = e;
143 : : }
144 : :
145 : : /* Find the strongly connected components. */
146 : 58187741 : graphds_scc (g, NULL);
147 : :
148 : : /* Mark the irreducible loops. */
149 : 942879447 : for (i = 0; i < g->n_vertices; i++)
150 : 1706442501 : for (ge = g->vertices[i].succ; ge; ge = ge->succ_next)
151 : : {
152 : 821750795 : edge real = (edge) ge->data;
153 : : /* edge E in graph G is irreducible if it connects two vertices in the
154 : : same scc. */
155 : :
156 : : /* All edges should lead from a component with higher number to the
157 : : one with lower one. */
158 : 821750795 : gcc_assert (g->vertices[ge->src].component >= g->vertices[ge->dest].component);
159 : :
160 : 821750795 : if (g->vertices[ge->src].component != g->vertices[ge->dest].component)
161 : 820258208 : continue;
162 : :
163 : 1492587 : real->flags |= EDGE_IRREDUCIBLE_LOOP;
164 : 1492587 : irred_loop_found = true;
165 : 1492587 : if (flow_bb_inside_loop_p (real->src->loop_father, real->dest))
166 : 1397872 : real->src->flags |= BB_IRREDUCIBLE_LOOP;
167 : : }
168 : :
169 : 58187741 : free_graph (g);
170 : :
171 : 58187741 : loops_state_set (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS);
172 : 58187741 : return irred_loop_found;
173 : : }
174 : :
175 : : /* Counts number of insns inside LOOP. */
176 : : int
177 : 377230 : num_loop_insns (const class loop *loop)
178 : : {
179 : 377230 : basic_block *bbs, bb;
180 : 377230 : unsigned i, ninsns = 0;
181 : 377230 : rtx_insn *insn;
182 : :
183 : 377230 : bbs = get_loop_body (loop);
184 : 2333495 : for (i = 0; i < loop->num_nodes; i++)
185 : : {
186 : 1579035 : bb = bbs[i];
187 : 17091751 : FOR_BB_INSNS (bb, insn)
188 : 15512716 : if (NONDEBUG_INSN_P (insn))
189 : 7023744 : ninsns++;
190 : : }
191 : 377230 : free (bbs);
192 : :
193 : 377230 : if (!ninsns)
194 : : ninsns = 1; /* To avoid division by zero. */
195 : :
196 : 377230 : return ninsns;
197 : : }
198 : :
199 : : /* Counts number of insns executed on average per iteration LOOP. */
200 : : int
201 : 377104 : average_num_loop_insns (const class loop *loop)
202 : : {
203 : 377104 : basic_block *bbs, bb;
204 : 377104 : unsigned i, binsns;
205 : 377104 : sreal ninsns;
206 : 377104 : rtx_insn *insn;
207 : :
208 : 377104 : ninsns = 0;
209 : 377104 : bbs = get_loop_body (loop);
210 : 2331954 : for (i = 0; i < loop->num_nodes; i++)
211 : : {
212 : 1577757 : bb = bbs[i];
213 : :
214 : 1577757 : binsns = 0;
215 : 17083061 : FOR_BB_INSNS (bb, insn)
216 : 15505304 : if (NONDEBUG_INSN_P (insn))
217 : 7018497 : binsns++;
218 : :
219 : 1577757 : ninsns += (sreal)binsns * bb->count.to_sreal_scale (loop->header->count);
220 : : /* Avoid overflows. */
221 : 1577757 : if (ninsns > 1000000)
222 : : {
223 : 11 : free (bbs);
224 : 11 : return 1000000;
225 : : }
226 : : }
227 : 377093 : free (bbs);
228 : :
229 : 377093 : int64_t ret = ninsns.to_int ();
230 : 377093 : if (!ret)
231 : 4902 : ret = 1; /* To avoid division by zero. */
232 : :
233 : 377093 : return ret;
234 : : }
235 : :
236 : : /* Compute how many times loop is entered. */
237 : :
238 : : profile_count
239 : 8223076 : loop_count_in (const class loop *loop)
240 : : {
241 : : /* Compute number of invocations of the loop. */
242 : 8223076 : profile_count count_in = profile_count::zero ();
243 : 8223076 : edge e;
244 : 8223076 : edge_iterator ei;
245 : 8223076 : bool found_latch = false;
246 : :
247 : 8223076 : if (loops_state_satisfies_p (LOOPS_MAY_HAVE_MULTIPLE_LATCHES))
248 : 2773 : FOR_EACH_EDGE (e, ei, loop->header->preds)
249 : 1891 : if (!flow_bb_inside_loop_p (loop, e->src))
250 : 1000 : count_in += e->count ();
251 : : else
252 : : found_latch = true;
253 : : else
254 : 24666582 : FOR_EACH_EDGE (e, ei, loop->header->preds)
255 : 16444388 : if (e->src != loop->latch)
256 : 8222194 : count_in += e->count ();
257 : : else
258 : : found_latch = true;
259 : 8223076 : gcc_checking_assert (found_latch);
260 : 8223076 : return count_in;
261 : : }
262 : :
263 : : /* Return true if BB profile can be used to determine the expected number of
264 : : iterations (that is number of executions of latch edge(s) for each
265 : : entry of the loop. If this is the case initialize RET with the number
266 : : of iterations.
267 : :
268 : : RELIABLE is set if profile indiates that the returned value should be
269 : : realistic estimate. (This is the case if we read profile and did not
270 : : messed it up yet and not the case of guessed profiles.)
271 : :
272 : : This function uses only CFG profile. We track more reliable info in
273 : : loop_info structure and for loop optimization heuristics more relevant
274 : : is get_estimated_loop_iterations API. */
275 : :
276 : : bool
277 : 9207642 : expected_loop_iterations_by_profile (const class loop *loop, sreal *ret,
278 : : bool *reliable)
279 : : {
280 : 9207642 : profile_count header_count = loop->header->count;
281 : 9207642 : if (reliable)
282 : 8999710 : *reliable = false;
283 : :
284 : : /* TODO: For single exit loops we can use loop exit edge probability.
285 : : It also may be reliable while loop itself was adjusted. */
286 : 9207642 : if (!header_count.initialized_p ()
287 : 9360184 : || !header_count.nonzero_p ())
288 : : return false;
289 : :
290 : 8127227 : profile_count count_in = loop_count_in (loop);
291 : :
292 : 8127227 : bool known;
293 : : /* Number of iterations is number of executions of latch edge. */
294 : 8127227 : *ret = (header_count - count_in).to_sreal_scale (count_in, &known);
295 : 8127227 : if (!known)
296 : : return false;
297 : 8116683 : if (reliable)
298 : : {
299 : : /* Header should have at least count_in many executions.
300 : : Give up on clearly inconsistent profile. */
301 : 7909303 : if (header_count < count_in && header_count.differs_from_p (count_in))
302 : : {
303 : 15192 : if (dump_file && (dump_flags & TDF_DETAILS))
304 : 0 : fprintf (dump_file, "Inconsistent bb profile of loop %i\n",
305 : 0 : loop->num);
306 : 15192 : *reliable = false;
307 : : }
308 : : else
309 : 15787966 : *reliable = count_in.reliable_p () && header_count.reliable_p ();
310 : : }
311 : : return true;
312 : : }
313 : :
314 : : /* Return true if loop CFG profile may be unrealistically flat.
315 : : This is a common case, since average loops iterate only about 5 times.
316 : : In the case we do not have profile feedback or do not know real number of
317 : : iterations during profile estimation, we are likely going to predict it with
318 : : similar low iteration count. For static loop profiles we also artificially
319 : : cap profile of loops with known large iteration count so they do not appear
320 : : significantly more hot than other loops with unknown iteration counts.
321 : :
322 : : For loop optimization heuristics we ignore CFG profile and instead
323 : : use get_estimated_loop_iterations API which returns estimate
324 : : only when it is realistic. For unknown counts some optimizations,
325 : : like vectorizer or unroller make guess that iteration count will
326 : : be large. In this case we need to avoid scaling down the profile
327 : : after the loop transform. */
328 : :
329 : : bool
330 : 86554 : maybe_flat_loop_profile (const class loop *loop)
331 : : {
332 : 86554 : bool reliable;
333 : 86554 : sreal ret;
334 : :
335 : 86554 : if (!expected_loop_iterations_by_profile (loop, &ret, &reliable))
336 : : return true;
337 : :
338 : : /* Reliable CFG estimates ought never be flat. Sanity check with
339 : : nb_iterations_estimate. If those differ, it is a but in profile
340 : : updating code */
341 : 86525 : if (reliable)
342 : : {
343 : 49 : int64_t intret = ret.to_nearest_int ();
344 : 49 : if (loop->any_estimate
345 : 49 : && (wi::ltu_p (intret * 2, loop->nb_iterations_estimate)
346 : 47 : || wi::gtu_p (intret, loop->nb_iterations_estimate * 2)))
347 : : {
348 : 0 : if (dump_file && (dump_flags & TDF_DETAILS))
349 : 0 : fprintf (dump_file,
350 : : "Loop %i has inconsistent iterations estimates: "
351 : : "reliable CFG based iteration estimate is %f "
352 : : "while nb_iterations_estimate is %i\n",
353 : 0 : loop->num,
354 : : ret.to_double (),
355 : 0 : (int)loop->nb_iterations_estimate.to_shwi ());
356 : 0 : return true;
357 : : }
358 : 49 : return false;
359 : : }
360 : :
361 : : /* Allow some margin of error and see if we are close to known bounds.
362 : : sreal (9,-3) is 9/8 */
363 : 86476 : int64_t intret = (ret * sreal (9, -3)).to_nearest_int ();
364 : 86476 : if (loop->any_upper_bound && wi::geu_p (intret, loop->nb_iterations_upper_bound))
365 : : return false;
366 : 60324 : if (loop->any_likely_upper_bound
367 : 60324 : && wi::geu_p (intret, loop->nb_iterations_likely_upper_bound))
368 : : return false;
369 : 60275 : if (loop->any_estimate
370 : 60275 : && wi::geu_p (intret, loop->nb_iterations_estimate))
371 : : return false;
372 : : return true;
373 : : }
374 : :
375 : : /* Returns expected number of iterations of LOOP, according to
376 : : measured or guessed profile.
377 : :
378 : : This functions attempts to return "sane" value even if profile
379 : : information is not good enough to derive osmething. */
380 : :
381 : : gcov_type
382 : 37 : expected_loop_iterations_unbounded (const class loop *loop,
383 : : bool *read_profile_p)
384 : : {
385 : 37 : gcov_type expected = -1;
386 : :
387 : 37 : if (read_profile_p)
388 : 0 : *read_profile_p = false;
389 : :
390 : 37 : sreal sreal_expected;
391 : 37 : if (expected_loop_iterations_by_profile
392 : 37 : (loop, &sreal_expected, read_profile_p))
393 : 37 : expected = sreal_expected.to_nearest_int ();
394 : : else
395 : 0 : expected = param_avg_loop_niter;
396 : :
397 : 37 : HOST_WIDE_INT max = get_max_loop_iterations_int (loop);
398 : 37 : if (max != -1 && max < expected)
399 : 0 : return max;
400 : :
401 : : return expected;
402 : : }
403 : :
404 : : /* Returns expected number of LOOP iterations. The returned value is bounded
405 : : by REG_BR_PROB_BASE. */
406 : :
407 : : unsigned
408 : 37 : expected_loop_iterations (class loop *loop)
409 : : {
410 : 37 : gcov_type expected = expected_loop_iterations_unbounded (loop);
411 : 37 : return (expected > REG_BR_PROB_BASE ? REG_BR_PROB_BASE : expected);
412 : : }
413 : :
414 : : /* Returns the maximum level of nesting of subloops of LOOP. */
415 : :
416 : : unsigned
417 : 0 : get_loop_level (const class loop *loop)
418 : : {
419 : 0 : const class loop *ploop;
420 : 0 : unsigned mx = 0, l;
421 : :
422 : 0 : for (ploop = loop->inner; ploop; ploop = ploop->next)
423 : : {
424 : 0 : l = get_loop_level (ploop);
425 : 0 : if (l >= mx)
426 : 0 : mx = l + 1;
427 : : }
428 : 0 : return mx;
429 : : }
430 : :
431 : : /* Initialize the constants for computing set costs. */
432 : :
433 : : void
434 : 210350 : init_set_costs (void)
435 : : {
436 : 210350 : int speed;
437 : 210350 : rtx_insn *seq;
438 : 210350 : rtx reg1 = gen_raw_REG (SImode, LAST_VIRTUAL_REGISTER + 1);
439 : 210350 : rtx reg2 = gen_raw_REG (SImode, LAST_VIRTUAL_REGISTER + 2);
440 : 210350 : rtx addr = gen_raw_REG (Pmode, LAST_VIRTUAL_REGISTER + 3);
441 : 210350 : rtx mem = validize_mem (gen_rtx_MEM (SImode, addr));
442 : 210350 : unsigned i;
443 : :
444 : 210350 : target_avail_regs = 0;
445 : 210350 : target_clobbered_regs = 0;
446 : 19562550 : for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
447 : 19352200 : if (TEST_HARD_REG_BIT (reg_class_contents[GENERAL_REGS], i)
448 : 19352200 : && !fixed_regs[i])
449 : : {
450 : 3111633 : target_avail_regs++;
451 : : /* ??? This is only a rough heuristic. It doesn't cope well
452 : : with alternative ABIs, but that's an optimization rather than
453 : : correctness issue. */
454 : 3111633 : if (default_function_abi.clobbers_full_reg_p (i))
455 : 1859982 : target_clobbered_regs++;
456 : : }
457 : :
458 : 210350 : target_res_regs = 3;
459 : :
460 : 631050 : for (speed = 0; speed < 2; speed++)
461 : : {
462 : 420700 : crtl->maybe_hot_insn_p = speed;
463 : : /* Set up the costs for using extra registers:
464 : :
465 : : 1) If not many free registers remain, we should prefer having an
466 : : additional move to decreasing the number of available registers.
467 : : (TARGET_REG_COST).
468 : : 2) If no registers are available, we need to spill, which may require
469 : : storing the old value to memory and loading it back
470 : : (TARGET_SPILL_COST). */
471 : :
472 : 420700 : start_sequence ();
473 : 420700 : emit_move_insn (reg1, reg2);
474 : 420700 : seq = get_insns ();
475 : 420700 : end_sequence ();
476 : 420700 : target_reg_cost [speed] = seq_cost (seq, speed);
477 : :
478 : 420700 : start_sequence ();
479 : 420700 : emit_move_insn (mem, reg1);
480 : 420700 : emit_move_insn (reg2, mem);
481 : 420700 : seq = get_insns ();
482 : 420700 : end_sequence ();
483 : 420700 : target_spill_cost [speed] = seq_cost (seq, speed);
484 : : }
485 : 210350 : default_rtl_profile ();
486 : 210350 : }
487 : :
488 : : /* Estimates cost of increased register pressure caused by making N_NEW new
489 : : registers live around the loop. N_OLD is the number of registers live
490 : : around the loop. If CALL_P is true, also take into account that
491 : : call-used registers may be clobbered in the loop body, reducing the
492 : : number of available registers before we spill. */
493 : :
494 : : unsigned
495 : 4010826 : estimate_reg_pressure_cost (unsigned n_new, unsigned n_old, bool speed,
496 : : bool call_p)
497 : : {
498 : 4010826 : unsigned cost;
499 : 4010826 : unsigned regs_needed = n_new + n_old;
500 : 4010826 : unsigned available_regs = target_avail_regs;
501 : :
502 : : /* If there is a call in the loop body, the call-clobbered registers
503 : : are not available for loop invariants. */
504 : 4010826 : if (call_p)
505 : 2679900 : available_regs = available_regs - target_clobbered_regs;
506 : :
507 : : /* If we have enough registers, we should use them and not restrict
508 : : the transformations unnecessarily. */
509 : 4010826 : if (regs_needed + target_res_regs <= available_regs)
510 : : return 0;
511 : :
512 : 1542391 : if (regs_needed <= available_regs)
513 : : /* If we are close to running out of registers, try to preserve
514 : : them. */
515 : 1194366 : cost = target_reg_cost [speed] * n_new;
516 : : else
517 : : /* If we run out of registers, it is very expensive to add another
518 : : one. */
519 : 348025 : cost = target_spill_cost [speed] * n_new;
520 : :
521 : 3084782 : if (optimize && (flag_ira_region == IRA_REGION_ALL
522 : 1542391 : || flag_ira_region == IRA_REGION_MIXED)
523 : 4573261 : && number_of_loops (cfun) <= (unsigned) param_ira_max_loops_num)
524 : : /* IRA regional allocation deals with high register pressure
525 : : better. So decrease the cost (to do more accurate the cost
526 : : calculation for IRA, we need to know how many registers lives
527 : : through the loop transparently). */
528 : 1502468 : cost /= 2;
529 : :
530 : : return cost;
531 : : }
532 : :
533 : : /* Sets EDGE_LOOP_EXIT flag for all loop exits. */
534 : :
535 : : void
536 : 3001569 : mark_loop_exit_edges (void)
537 : : {
538 : 3001569 : basic_block bb;
539 : 3001569 : edge e;
540 : :
541 : 6003138 : if (number_of_loops (cfun) <= 1)
542 : 2380343 : return;
543 : :
544 : 19305997 : FOR_EACH_BB_FN (bb, cfun)
545 : : {
546 : 18684771 : edge_iterator ei;
547 : :
548 : 46870024 : FOR_EACH_EDGE (e, ei, bb->succs)
549 : : {
550 : 28185253 : if (loop_outer (bb->loop_father)
551 : 28185253 : && loop_exit_edge_p (bb->loop_father, e))
552 : 3203741 : e->flags |= EDGE_LOOP_EXIT;
553 : : else
554 : 24981512 : e->flags &= ~EDGE_LOOP_EXIT;
555 : : }
556 : : }
557 : : }
558 : :
559 : : /* Return exit edge if loop has only one exit that is likely
560 : : to be executed on runtime (i.e. it is not EH or leading
561 : : to noreturn call. */
562 : :
563 : : edge
564 : 6948079 : single_likely_exit (class loop *loop, const vec<edge> &exits)
565 : : {
566 : 6948079 : edge found = single_exit (loop);
567 : 6948079 : unsigned i;
568 : 6948079 : edge ex;
569 : :
570 : 6948079 : if (found)
571 : : return found;
572 : 7350710 : FOR_EACH_VEC_ELT (exits, i, ex)
573 : : {
574 : 6635956 : if (probably_never_executed_edge_p (cfun, ex)
575 : : /* We want to rule out paths to noreturns but not low probabilities
576 : : resulting from adjustments or combining.
577 : : FIXME: once we have better quality tracking, make this more
578 : : robust. */
579 : 6635956 : || ex->probability <= profile_probability::very_unlikely ())
580 : 2962745 : continue;
581 : 3673211 : if (!found)
582 : : found = ex;
583 : : else
584 : : return NULL;
585 : : }
586 : : return found;
587 : : }
588 : :
589 : :
590 : : /* Gets basic blocks of a LOOP. Header is the 0-th block, rest is in dfs
591 : : order against direction of edges from latch. Specially, if
592 : : header != latch, latch is the 1-st block. */
593 : :
594 : : auto_vec<basic_block>
595 : 454315 : get_loop_hot_path (const class loop *loop)
596 : : {
597 : 454315 : basic_block bb = loop->header;
598 : 454315 : auto_vec<basic_block> path;
599 : 454315 : bitmap visited = BITMAP_ALLOC (NULL);
600 : :
601 : 2871289 : while (true)
602 : : {
603 : 1662802 : edge_iterator ei;
604 : 1662802 : edge e;
605 : 1662802 : edge best = NULL;
606 : :
607 : 1662802 : path.safe_push (bb);
608 : 1662802 : bitmap_set_bit (visited, bb->index);
609 : 4319691 : FOR_EACH_EDGE (e, ei, bb->succs)
610 : 3194507 : if ((!best || e->probability > best->probability)
611 : 2256633 : && !loop_exit_edge_p (loop, e)
612 : 4450820 : && !bitmap_bit_p (visited, e->dest->index))
613 : : best = e;
614 : 1662802 : if (!best || best->dest == loop->header)
615 : : break;
616 : 1208487 : bb = best->dest;
617 : 1208487 : }
618 : 454315 : BITMAP_FREE (visited);
619 : 454315 : return path;
620 : : }
|
