1 /* Natural loop analysis code for GNU compiler.
2 Copyright (C) 2002-2023 Free Software Foundation, Inc.
4 This file is part of GCC.
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
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
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/>. */
22 #include "coretypes.h"
35 #include "function-abi.h"
37 struct target_cfgloop default_target_cfgloop
;
39 struct target_cfgloop
*this_target_cfgloop
= &default_target_cfgloop
;
42 /* Checks whether BB is executed exactly once in each LOOP iteration. */
45 just_once_each_iteration_p (const class loop
*loop
, const_basic_block bb
)
47 /* It must be executed at least once each iteration. */
48 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, bb
))
52 if (bb
->loop_father
!= loop
)
55 /* But this was not enough. We might have some irreducible loop here. */
56 if (bb
->flags
& BB_IRREDUCIBLE_LOOP
)
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.
69 LOOPS is the loop tree. */
71 #define LOOP_REPR(LOOP) ((LOOP)->num + last_basic_block_for_fn (cfun))
72 #define BB_REPR(BB) ((BB)->index + 1)
75 mark_irreducible_loops (void)
78 struct graph_edge
*ge
;
84 int num
= number_of_loops (cfun
);
86 bool irred_loop_found
= false;
89 gcc_assert (current_loops
!= NULL
);
91 /* Reset the flags. */
92 FOR_BB_BETWEEN (act
, ENTRY_BLOCK_PTR_FOR_FN (cfun
),
93 EXIT_BLOCK_PTR_FOR_FN (cfun
), next_bb
)
95 act
->flags
&= ~BB_IRREDUCIBLE_LOOP
;
96 FOR_EACH_EDGE (e
, ei
, act
->succs
)
97 e
->flags
&= ~EDGE_IRREDUCIBLE_LOOP
;
100 /* Create the edge lists. */
101 g
= new_graph (last_basic_block_for_fn (cfun
) + num
);
103 FOR_BB_BETWEEN (act
, ENTRY_BLOCK_PTR_FOR_FN (cfun
),
104 EXIT_BLOCK_PTR_FOR_FN (cfun
), next_bb
)
105 FOR_EACH_EDGE (e
, ei
, act
->succs
)
107 /* Ignore edges to exit. */
108 if (e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
112 dest
= BB_REPR (e
->dest
);
114 /* Ignore latch edges. */
115 if (e
->dest
->loop_father
->header
== e
->dest
116 && dominated_by_p (CDI_DOMINATORS
, act
, e
->dest
))
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.
123 Edges exiting loops should lead from representative
124 of the son of nearest common ancestor of the loops in that
127 if (e
->dest
->loop_father
->header
== e
->dest
)
128 dest
= LOOP_REPR (e
->dest
->loop_father
);
130 if (!flow_bb_inside_loop_p (act
->loop_father
, e
->dest
))
132 depth
= 1 + loop_depth (find_common_loop (act
->loop_father
,
133 e
->dest
->loop_father
));
134 if (depth
== loop_depth (act
->loop_father
))
135 cloop
= act
->loop_father
;
137 cloop
= (*act
->loop_father
->superloops
)[depth
];
139 src
= LOOP_REPR (cloop
);
142 add_edge (g
, src
, dest
)->data
= e
;
145 /* Find the strongly connected components. */
146 graphds_scc (g
, NULL
);
148 /* Mark the irreducible loops. */
149 for (i
= 0; i
< g
->n_vertices
; i
++)
150 for (ge
= g
->vertices
[i
].succ
; ge
; ge
= ge
->succ_next
)
152 edge real
= (edge
) ge
->data
;
153 /* edge E in graph G is irreducible if it connects two vertices in the
156 /* All edges should lead from a component with higher number to the
157 one with lower one. */
158 gcc_assert (g
->vertices
[ge
->src
].component
>= g
->vertices
[ge
->dest
].component
);
160 if (g
->vertices
[ge
->src
].component
!= g
->vertices
[ge
->dest
].component
)
163 real
->flags
|= EDGE_IRREDUCIBLE_LOOP
;
164 irred_loop_found
= true;
165 if (flow_bb_inside_loop_p (real
->src
->loop_father
, real
->dest
))
166 real
->src
->flags
|= BB_IRREDUCIBLE_LOOP
;
171 loops_state_set (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS
);
172 return irred_loop_found
;
175 /* Counts number of insns inside LOOP. */
177 num_loop_insns (const class loop
*loop
)
179 basic_block
*bbs
, bb
;
180 unsigned i
, ninsns
= 0;
183 bbs
= get_loop_body (loop
);
184 for (i
= 0; i
< loop
->num_nodes
; i
++)
187 FOR_BB_INSNS (bb
, insn
)
188 if (NONDEBUG_INSN_P (insn
))
194 ninsns
= 1; /* To avoid division by zero. */
199 /* Counts number of insns executed on average per iteration LOOP. */
201 average_num_loop_insns (const class loop
*loop
)
203 basic_block
*bbs
, bb
;
209 bbs
= get_loop_body (loop
);
210 for (i
= 0; i
< loop
->num_nodes
; i
++)
215 FOR_BB_INSNS (bb
, insn
)
216 if (NONDEBUG_INSN_P (insn
))
219 ninsns
+= (sreal
)binsns
* bb
->count
.to_sreal_scale (loop
->header
->count
);
220 /* Avoid overflows. */
221 if (ninsns
> 1000000)
229 int64_t ret
= ninsns
.to_int ();
231 ret
= 1; /* To avoid division by zero. */
236 /* Return true if BB profile can be used to determine the expected number of
237 iterations (that is number of executions of latch edge(s) for each
238 entry of the loop. If this is the case initialize RET with the number
241 RELIABLE is set if profile indiates that the returned value should be
242 realistic estimate. (This is the case if we read profile and did not
243 messed it up yet and not the case of guessed profiles.)
245 This function uses only CFG profile. We track more reliable info in
246 loop_info structure and for loop optimization heuristics more relevant
247 is get_estimated_loop_iterations API. */
250 expected_loop_iterations_by_profile (const class loop
*loop
, sreal
*ret
,
253 profile_count header_count
= loop
->header
->count
;
257 /* TODO: For single exit loops we can use loop exit edge probability.
258 It also may be reliable while loop itself was adjusted. */
259 if (!header_count
.initialized_p ()
260 || !header_count
.nonzero_p ())
263 profile_count count_in
= profile_count::zero ();
267 /* For single-latch loops avoid querying dominators. */
271 FOR_EACH_EDGE (e
, ei
, loop
->header
->preds
)
272 if (e
->src
!= loop
->latch
)
273 count_in
+= e
->count ();
276 /* If latch is not found, loop is inconsistent. */
277 gcc_checking_assert (found
);
280 FOR_EACH_EDGE (e
, ei
, loop
->header
->preds
)
281 if (!dominated_by_p (CDI_DOMINATORS
, e
->src
, loop
->header
))
282 count_in
+= e
->count ();
285 /* Number of iterations is number of executions of latch edge. */
286 *ret
= (header_count
- count_in
).to_sreal_scale (count_in
, &known
);
291 /* Header should have at least count_in many executions.
292 Give up on clearly inconsistent profile. */
293 if (header_count
< count_in
&& header_count
.differs_from_p (count_in
))
295 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
296 fprintf (dump_file
, "Inconsistent bb profile of loop %i\n",
301 *reliable
= count_in
.reliable_p () && header_count
.reliable_p ();
306 /* Return true if loop CFG profile may be unrealistically flat.
307 This is a common case, since average loops iterate only about 5 times.
308 In the case we do not have profile feedback or do not know real number of
309 iterations during profile estimation, we are likely going to predict it with
310 similar low iteration count. For static loop profiles we also artificially
311 cap profile of loops with known large iteration count so they do not appear
312 significantly more hot than other loops with unknown iteration counts.
314 For loop optimization heuristics we ignore CFG profile and instead
315 use get_estimated_loop_iterations API which returns estimate
316 only when it is realistic. For unknown counts some optimizations,
317 like vectorizer or unroller make guess that iteration count will
318 be large. In this case we need to avoid scaling down the profile
319 after the loop transform. */
322 maybe_flat_loop_profile (const class loop
*loop
)
327 if (!expected_loop_iterations_by_profile (loop
, &ret
, &reliable
))
330 /* Reliable CFG estimates ought never be flat. Sanity check with
331 nb_iterations_estimate. If those differ, it is a but in profile
335 int64_t intret
= ret
.to_nearest_int ();
336 if (loop
->any_estimate
337 && (wi::ltu_p (intret
* 2, loop
->nb_iterations_estimate
)
338 || wi::gtu_p (intret
, loop
->nb_iterations_estimate
* 2)))
340 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
342 "Loop %i has inconsistent iterations estimates: "
343 "reliable CFG based iteration estimate is %f "
344 "while nb_iterations_estimate is %i\n",
347 (int)loop
->nb_iterations_estimate
.to_shwi ());
353 /* Allow some margin of error and see if we are close to known bounds.
354 sreal (9,-3) is 9/8 */
355 int64_t intret
= (ret
* sreal (9, -3)).to_nearest_int ();
356 if (loop
->any_upper_bound
&& wi::geu_p (intret
, loop
->nb_iterations_upper_bound
))
358 if (loop
->any_likely_upper_bound
359 && wi::geu_p (intret
, loop
->nb_iterations_likely_upper_bound
))
361 if (loop
->any_estimate
362 && wi::geu_p (intret
, loop
->nb_iterations_estimate
))
367 /* Returns expected number of iterations of LOOP, according to
368 measured or guessed profile.
370 This functions attempts to return "sane" value even if profile
371 information is not good enough to derive osmething. */
374 expected_loop_iterations_unbounded (const class loop
*loop
,
375 bool *read_profile_p
)
377 gcov_type expected
= -1;
380 *read_profile_p
= false;
382 sreal sreal_expected
;
383 if (expected_loop_iterations_by_profile
384 (loop
, &sreal_expected
, read_profile_p
))
385 expected
= sreal_expected
.to_nearest_int ();
387 expected
= param_avg_loop_niter
;
389 HOST_WIDE_INT max
= get_max_loop_iterations_int (loop
);
390 if (max
!= -1 && max
< expected
)
396 /* Returns expected number of LOOP iterations. The returned value is bounded
397 by REG_BR_PROB_BASE. */
400 expected_loop_iterations (class loop
*loop
)
402 gcov_type expected
= expected_loop_iterations_unbounded (loop
);
403 return (expected
> REG_BR_PROB_BASE
? REG_BR_PROB_BASE
: expected
);
406 /* Returns the maximum level of nesting of subloops of LOOP. */
409 get_loop_level (const class loop
*loop
)
411 const class loop
*ploop
;
414 for (ploop
= loop
->inner
; ploop
; ploop
= ploop
->next
)
416 l
= get_loop_level (ploop
);
423 /* Initialize the constants for computing set costs. */
426 init_set_costs (void)
430 rtx reg1
= gen_raw_REG (SImode
, LAST_VIRTUAL_REGISTER
+ 1);
431 rtx reg2
= gen_raw_REG (SImode
, LAST_VIRTUAL_REGISTER
+ 2);
432 rtx addr
= gen_raw_REG (Pmode
, LAST_VIRTUAL_REGISTER
+ 3);
433 rtx mem
= validize_mem (gen_rtx_MEM (SImode
, addr
));
436 target_avail_regs
= 0;
437 target_clobbered_regs
= 0;
438 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
439 if (TEST_HARD_REG_BIT (reg_class_contents
[GENERAL_REGS
], i
)
443 /* ??? This is only a rough heuristic. It doesn't cope well
444 with alternative ABIs, but that's an optimization rather than
445 correctness issue. */
446 if (default_function_abi
.clobbers_full_reg_p (i
))
447 target_clobbered_regs
++;
452 for (speed
= 0; speed
< 2; speed
++)
454 crtl
->maybe_hot_insn_p
= speed
;
455 /* Set up the costs for using extra registers:
457 1) If not many free registers remain, we should prefer having an
458 additional move to decreasing the number of available registers.
460 2) If no registers are available, we need to spill, which may require
461 storing the old value to memory and loading it back
462 (TARGET_SPILL_COST). */
465 emit_move_insn (reg1
, reg2
);
468 target_reg_cost
[speed
] = seq_cost (seq
, speed
);
471 emit_move_insn (mem
, reg1
);
472 emit_move_insn (reg2
, mem
);
475 target_spill_cost
[speed
] = seq_cost (seq
, speed
);
477 default_rtl_profile ();
480 /* Estimates cost of increased register pressure caused by making N_NEW new
481 registers live around the loop. N_OLD is the number of registers live
482 around the loop. If CALL_P is true, also take into account that
483 call-used registers may be clobbered in the loop body, reducing the
484 number of available registers before we spill. */
487 estimate_reg_pressure_cost (unsigned n_new
, unsigned n_old
, bool speed
,
491 unsigned regs_needed
= n_new
+ n_old
;
492 unsigned available_regs
= target_avail_regs
;
494 /* If there is a call in the loop body, the call-clobbered registers
495 are not available for loop invariants. */
497 available_regs
= available_regs
- target_clobbered_regs
;
499 /* If we have enough registers, we should use them and not restrict
500 the transformations unnecessarily. */
501 if (regs_needed
+ target_res_regs
<= available_regs
)
504 if (regs_needed
<= available_regs
)
505 /* If we are close to running out of registers, try to preserve
507 cost
= target_reg_cost
[speed
] * n_new
;
509 /* If we run out of registers, it is very expensive to add another
511 cost
= target_spill_cost
[speed
] * n_new
;
513 if (optimize
&& (flag_ira_region
== IRA_REGION_ALL
514 || flag_ira_region
== IRA_REGION_MIXED
)
515 && number_of_loops (cfun
) <= (unsigned) param_ira_max_loops_num
)
516 /* IRA regional allocation deals with high register pressure
517 better. So decrease the cost (to do more accurate the cost
518 calculation for IRA, we need to know how many registers lives
519 through the loop transparently). */
525 /* Sets EDGE_LOOP_EXIT flag for all loop exits. */
528 mark_loop_exit_edges (void)
533 if (number_of_loops (cfun
) <= 1)
536 FOR_EACH_BB_FN (bb
, cfun
)
540 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
542 if (loop_outer (bb
->loop_father
)
543 && loop_exit_edge_p (bb
->loop_father
, e
))
544 e
->flags
|= EDGE_LOOP_EXIT
;
546 e
->flags
&= ~EDGE_LOOP_EXIT
;
551 /* Return exit edge if loop has only one exit that is likely
552 to be executed on runtime (i.e. it is not EH or leading
556 single_likely_exit (class loop
*loop
, const vec
<edge
> &exits
)
558 edge found
= single_exit (loop
);
564 FOR_EACH_VEC_ELT (exits
, i
, ex
)
566 if (probably_never_executed_edge_p (cfun
, ex
)
567 /* We want to rule out paths to noreturns but not low probabilities
568 resulting from adjustments or combining.
569 FIXME: once we have better quality tracking, make this more
571 || ex
->probability
<= profile_probability::very_unlikely ())
582 /* Gets basic blocks of a LOOP. Header is the 0-th block, rest is in dfs
583 order against direction of edges from latch. Specially, if
584 header != latch, latch is the 1-st block. */
586 auto_vec
<basic_block
>
587 get_loop_hot_path (const class loop
*loop
)
589 basic_block bb
= loop
->header
;
590 auto_vec
<basic_block
> path
;
591 bitmap visited
= BITMAP_ALLOC (NULL
);
600 bitmap_set_bit (visited
, bb
->index
);
601 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
602 if ((!best
|| e
->probability
> best
->probability
)
603 && !loop_exit_edge_p (loop
, e
)
604 && !bitmap_bit_p (visited
, e
->dest
->index
))
606 if (!best
|| best
->dest
== loop
->header
)
610 BITMAP_FREE (visited
);