1 /* Natural loop analysis code for GNU compiler.
2 Copyright (C) 2002-2020 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 && e
->dest
->loop_father
->latch
== act
)
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)
226 int64_t ret
= ninsns
.to_int ();
228 ret
= 1; /* To avoid division by zero. */
233 /* Returns expected number of iterations of LOOP, according to
234 measured or guessed profile.
236 This functions attempts to return "sane" value even if profile
237 information is not good enough to derive osmething.
238 If BY_PROFILE_ONLY is set, this logic is bypassed and function
239 return -1 in those scenarios. */
242 expected_loop_iterations_unbounded (const class loop
*loop
,
243 bool *read_profile_p
,
244 bool by_profile_only
)
248 gcov_type expected
= -1;
251 *read_profile_p
= false;
253 /* If we have no profile at all, use AVG_LOOP_NITER. */
254 if (profile_status_for_fn (cfun
) == PROFILE_ABSENT
)
258 expected
= param_avg_loop_niter
;
260 else if (loop
->latch
&& (loop
->latch
->count
.initialized_p ()
261 || loop
->header
->count
.initialized_p ()))
263 profile_count count_in
= profile_count::zero (),
264 count_latch
= profile_count::zero ();
266 FOR_EACH_EDGE (e
, ei
, loop
->header
->preds
)
267 if (e
->src
== loop
->latch
)
268 count_latch
= e
->count ();
270 count_in
+= e
->count ();
272 if (!count_latch
.initialized_p ())
276 expected
= param_avg_loop_niter
;
278 else if (!count_in
.nonzero_p ())
282 expected
= count_latch
.to_gcov_type () * 2;
286 expected
= (count_latch
.to_gcov_type () + count_in
.to_gcov_type ()
287 - 1) / count_in
.to_gcov_type ();
289 && count_latch
.reliable_p () && count_in
.reliable_p ())
290 *read_profile_p
= true;
297 expected
= param_avg_loop_niter
;
300 if (!by_profile_only
)
302 HOST_WIDE_INT max
= get_max_loop_iterations_int (loop
);
303 if (max
!= -1 && max
< expected
)
310 /* Returns expected number of LOOP iterations. The returned value is bounded
311 by REG_BR_PROB_BASE. */
314 expected_loop_iterations (class loop
*loop
)
316 gcov_type expected
= expected_loop_iterations_unbounded (loop
);
317 return (expected
> REG_BR_PROB_BASE
? REG_BR_PROB_BASE
: expected
);
320 /* Returns the maximum level of nesting of subloops of LOOP. */
323 get_loop_level (const class loop
*loop
)
325 const class loop
*ploop
;
328 for (ploop
= loop
->inner
; ploop
; ploop
= ploop
->next
)
330 l
= get_loop_level (ploop
);
337 /* Initialize the constants for computing set costs. */
340 init_set_costs (void)
344 rtx reg1
= gen_raw_REG (SImode
, LAST_VIRTUAL_REGISTER
+ 1);
345 rtx reg2
= gen_raw_REG (SImode
, LAST_VIRTUAL_REGISTER
+ 2);
346 rtx addr
= gen_raw_REG (Pmode
, LAST_VIRTUAL_REGISTER
+ 3);
347 rtx mem
= validize_mem (gen_rtx_MEM (SImode
, addr
));
350 target_avail_regs
= 0;
351 target_clobbered_regs
= 0;
352 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
353 if (TEST_HARD_REG_BIT (reg_class_contents
[GENERAL_REGS
], i
)
357 /* ??? This is only a rough heuristic. It doesn't cope well
358 with alternative ABIs, but that's an optimization rather than
359 correctness issue. */
360 if (default_function_abi
.clobbers_full_reg_p (i
))
361 target_clobbered_regs
++;
366 for (speed
= 0; speed
< 2; speed
++)
368 crtl
->maybe_hot_insn_p
= speed
;
369 /* Set up the costs for using extra registers:
371 1) If not many free registers remain, we should prefer having an
372 additional move to decreasing the number of available registers.
374 2) If no registers are available, we need to spill, which may require
375 storing the old value to memory and loading it back
376 (TARGET_SPILL_COST). */
379 emit_move_insn (reg1
, reg2
);
382 target_reg_cost
[speed
] = seq_cost (seq
, speed
);
385 emit_move_insn (mem
, reg1
);
386 emit_move_insn (reg2
, mem
);
389 target_spill_cost
[speed
] = seq_cost (seq
, speed
);
391 default_rtl_profile ();
394 /* Estimates cost of increased register pressure caused by making N_NEW new
395 registers live around the loop. N_OLD is the number of registers live
396 around the loop. If CALL_P is true, also take into account that
397 call-used registers may be clobbered in the loop body, reducing the
398 number of available registers before we spill. */
401 estimate_reg_pressure_cost (unsigned n_new
, unsigned n_old
, bool speed
,
405 unsigned regs_needed
= n_new
+ n_old
;
406 unsigned available_regs
= target_avail_regs
;
408 /* If there is a call in the loop body, the call-clobbered registers
409 are not available for loop invariants. */
411 available_regs
= available_regs
- target_clobbered_regs
;
413 /* If we have enough registers, we should use them and not restrict
414 the transformations unnecessarily. */
415 if (regs_needed
+ target_res_regs
<= available_regs
)
418 if (regs_needed
<= available_regs
)
419 /* If we are close to running out of registers, try to preserve
421 cost
= target_reg_cost
[speed
] * n_new
;
423 /* If we run out of registers, it is very expensive to add another
425 cost
= target_spill_cost
[speed
] * n_new
;
427 if (optimize
&& (flag_ira_region
== IRA_REGION_ALL
428 || flag_ira_region
== IRA_REGION_MIXED
)
429 && number_of_loops (cfun
) <= (unsigned) param_ira_max_loops_num
)
430 /* IRA regional allocation deals with high register pressure
431 better. So decrease the cost (to do more accurate the cost
432 calculation for IRA, we need to know how many registers lives
433 through the loop transparently). */
439 /* Sets EDGE_LOOP_EXIT flag for all loop exits. */
442 mark_loop_exit_edges (void)
447 if (number_of_loops (cfun
) <= 1)
450 FOR_EACH_BB_FN (bb
, cfun
)
454 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
456 if (loop_outer (bb
->loop_father
)
457 && loop_exit_edge_p (bb
->loop_father
, e
))
458 e
->flags
|= EDGE_LOOP_EXIT
;
460 e
->flags
&= ~EDGE_LOOP_EXIT
;
465 /* Return exit edge if loop has only one exit that is likely
466 to be executed on runtime (i.e. it is not EH or leading
470 single_likely_exit (class loop
*loop
, vec
<edge
> exits
)
472 edge found
= single_exit (loop
);
478 FOR_EACH_VEC_ELT (exits
, i
, ex
)
480 if (probably_never_executed_edge_p (cfun
, ex
)
481 /* We want to rule out paths to noreturns but not low probabilities
482 resulting from adjustments or combining.
483 FIXME: once we have better quality tracking, make this more
485 || ex
->probability
<= profile_probability::very_unlikely ())
496 /* Gets basic blocks of a LOOP. Header is the 0-th block, rest is in dfs
497 order against direction of edges from latch. Specially, if
498 header != latch, latch is the 1-st block. */
501 get_loop_hot_path (const class loop
*loop
)
503 basic_block bb
= loop
->header
;
504 vec
<basic_block
> path
= vNULL
;
505 bitmap visited
= BITMAP_ALLOC (NULL
);
514 bitmap_set_bit (visited
, bb
->index
);
515 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
516 if ((!best
|| e
->probability
> best
->probability
)
517 && !loop_exit_edge_p (loop
, e
)
518 && !bitmap_bit_p (visited
, e
->dest
->index
))
520 if (!best
|| best
->dest
== loop
->header
)
524 BITMAP_FREE (visited
);