1 /* Natural loop analysis code for GNU compiler.
2 Copyright (C) 2002-2019 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"
36 #include "function-abi.h"
38 struct target_cfgloop default_target_cfgloop
;
40 struct target_cfgloop
*this_target_cfgloop
= &default_target_cfgloop
;
43 /* Checks whether BB is executed exactly once in each LOOP iteration. */
46 just_once_each_iteration_p (const class loop
*loop
, const_basic_block bb
)
48 /* It must be executed at least once each iteration. */
49 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, bb
))
53 if (bb
->loop_father
!= loop
)
56 /* But this was not enough. We might have some irreducible loop here. */
57 if (bb
->flags
& BB_IRREDUCIBLE_LOOP
)
63 /* Marks blocks and edges that are part of non-recognized loops; i.e. we
64 throw away all latch edges and mark blocks inside any remaining cycle.
65 Everything is a bit complicated due to fact we do not want to do this
66 for parts of cycles that only "pass" through some loop -- i.e. for
67 each cycle, we want to mark blocks that belong directly to innermost
68 loop containing the whole cycle.
70 LOOPS is the loop tree. */
72 #define LOOP_REPR(LOOP) ((LOOP)->num + last_basic_block_for_fn (cfun))
73 #define BB_REPR(BB) ((BB)->index + 1)
76 mark_irreducible_loops (void)
79 struct graph_edge
*ge
;
85 int num
= number_of_loops (cfun
);
87 bool irred_loop_found
= false;
90 gcc_assert (current_loops
!= NULL
);
92 /* Reset the flags. */
93 FOR_BB_BETWEEN (act
, ENTRY_BLOCK_PTR_FOR_FN (cfun
),
94 EXIT_BLOCK_PTR_FOR_FN (cfun
), next_bb
)
96 act
->flags
&= ~BB_IRREDUCIBLE_LOOP
;
97 FOR_EACH_EDGE (e
, ei
, act
->succs
)
98 e
->flags
&= ~EDGE_IRREDUCIBLE_LOOP
;
101 /* Create the edge lists. */
102 g
= new_graph (last_basic_block_for_fn (cfun
) + num
);
104 FOR_BB_BETWEEN (act
, ENTRY_BLOCK_PTR_FOR_FN (cfun
),
105 EXIT_BLOCK_PTR_FOR_FN (cfun
), next_bb
)
106 FOR_EACH_EDGE (e
, ei
, act
->succs
)
108 /* Ignore edges to exit. */
109 if (e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
113 dest
= BB_REPR (e
->dest
);
115 /* Ignore latch edges. */
116 if (e
->dest
->loop_father
->header
== e
->dest
117 && e
->dest
->loop_father
->latch
== act
)
120 /* Edges inside a single loop should be left where they are. Edges
121 to subloop headers should lead to representative of the subloop,
122 but from the same place.
124 Edges exiting loops should lead from representative
125 of the son of nearest common ancestor of the loops in that
128 if (e
->dest
->loop_father
->header
== e
->dest
)
129 dest
= LOOP_REPR (e
->dest
->loop_father
);
131 if (!flow_bb_inside_loop_p (act
->loop_father
, e
->dest
))
133 depth
= 1 + loop_depth (find_common_loop (act
->loop_father
,
134 e
->dest
->loop_father
));
135 if (depth
== loop_depth (act
->loop_father
))
136 cloop
= act
->loop_father
;
138 cloop
= (*act
->loop_father
->superloops
)[depth
];
140 src
= LOOP_REPR (cloop
);
143 add_edge (g
, src
, dest
)->data
= e
;
146 /* Find the strongly connected components. */
147 graphds_scc (g
, NULL
);
149 /* Mark the irreducible loops. */
150 for (i
= 0; i
< g
->n_vertices
; i
++)
151 for (ge
= g
->vertices
[i
].succ
; ge
; ge
= ge
->succ_next
)
153 edge real
= (edge
) ge
->data
;
154 /* edge E in graph G is irreducible if it connects two vertices in the
157 /* All edges should lead from a component with higher number to the
158 one with lower one. */
159 gcc_assert (g
->vertices
[ge
->src
].component
>= g
->vertices
[ge
->dest
].component
);
161 if (g
->vertices
[ge
->src
].component
!= g
->vertices
[ge
->dest
].component
)
164 real
->flags
|= EDGE_IRREDUCIBLE_LOOP
;
165 irred_loop_found
= true;
166 if (flow_bb_inside_loop_p (real
->src
->loop_father
, real
->dest
))
167 real
->src
->flags
|= BB_IRREDUCIBLE_LOOP
;
172 loops_state_set (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS
);
173 return irred_loop_found
;
176 /* Counts number of insns inside LOOP. */
178 num_loop_insns (const class loop
*loop
)
180 basic_block
*bbs
, bb
;
181 unsigned i
, ninsns
= 0;
184 bbs
= get_loop_body (loop
);
185 for (i
= 0; i
< loop
->num_nodes
; i
++)
188 FOR_BB_INSNS (bb
, insn
)
189 if (NONDEBUG_INSN_P (insn
))
195 ninsns
= 1; /* To avoid division by zero. */
200 /* Counts number of insns executed on average per iteration LOOP. */
202 average_num_loop_insns (const class loop
*loop
)
204 basic_block
*bbs
, bb
;
210 bbs
= get_loop_body (loop
);
211 for (i
= 0; i
< loop
->num_nodes
; i
++)
216 FOR_BB_INSNS (bb
, insn
)
217 if (NONDEBUG_INSN_P (insn
))
220 ninsns
+= (sreal
)binsns
* bb
->count
.to_sreal_scale (loop
->header
->count
);
221 /* Avoid overflows. */
222 if (ninsns
> 1000000)
227 int64_t ret
= ninsns
.to_int ();
229 ret
= 1; /* To avoid division by zero. */
234 /* Returns expected number of iterations of LOOP, according to
235 measured or guessed profile.
237 This functions attempts to return "sane" value even if profile
238 information is not good enough to derive osmething.
239 If BY_PROFILE_ONLY is set, this logic is bypassed and function
240 return -1 in those scenarios. */
243 expected_loop_iterations_unbounded (const class loop
*loop
,
244 bool *read_profile_p
,
245 bool by_profile_only
)
249 gcov_type expected
= -1;
252 *read_profile_p
= false;
254 /* If we have no profile at all, use AVG_LOOP_NITER. */
255 if (profile_status_for_fn (cfun
) == PROFILE_ABSENT
)
259 expected
= PARAM_VALUE (PARAM_AVG_LOOP_NITER
);
261 else if (loop
->latch
&& (loop
->latch
->count
.initialized_p ()
262 || loop
->header
->count
.initialized_p ()))
264 profile_count count_in
= profile_count::zero (),
265 count_latch
= profile_count::zero ();
267 FOR_EACH_EDGE (e
, ei
, loop
->header
->preds
)
268 if (e
->src
== loop
->latch
)
269 count_latch
= e
->count ();
271 count_in
+= e
->count ();
273 if (!count_latch
.initialized_p ())
277 expected
= PARAM_VALUE (PARAM_AVG_LOOP_NITER
);
279 else if (!count_in
.nonzero_p ())
283 expected
= count_latch
.to_gcov_type () * 2;
287 expected
= (count_latch
.to_gcov_type () + count_in
.to_gcov_type ()
288 - 1) / count_in
.to_gcov_type ();
290 && count_latch
.reliable_p () && count_in
.reliable_p ())
291 *read_profile_p
= true;
298 expected
= PARAM_VALUE (PARAM_AVG_LOOP_NITER
);
301 if (!by_profile_only
)
303 HOST_WIDE_INT max
= get_max_loop_iterations_int (loop
);
304 if (max
!= -1 && max
< expected
)
311 /* Returns expected number of LOOP iterations. The returned value is bounded
312 by REG_BR_PROB_BASE. */
315 expected_loop_iterations (class loop
*loop
)
317 gcov_type expected
= expected_loop_iterations_unbounded (loop
);
318 return (expected
> REG_BR_PROB_BASE
? REG_BR_PROB_BASE
: expected
);
321 /* Returns the maximum level of nesting of subloops of LOOP. */
324 get_loop_level (const class loop
*loop
)
326 const class loop
*ploop
;
329 for (ploop
= loop
->inner
; ploop
; ploop
= ploop
->next
)
331 l
= get_loop_level (ploop
);
338 /* Initialize the constants for computing set costs. */
341 init_set_costs (void)
345 rtx reg1
= gen_raw_REG (SImode
, LAST_VIRTUAL_REGISTER
+ 1);
346 rtx reg2
= gen_raw_REG (SImode
, LAST_VIRTUAL_REGISTER
+ 2);
347 rtx addr
= gen_raw_REG (Pmode
, LAST_VIRTUAL_REGISTER
+ 3);
348 rtx mem
= validize_mem (gen_rtx_MEM (SImode
, addr
));
351 target_avail_regs
= 0;
352 target_clobbered_regs
= 0;
353 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
354 if (TEST_HARD_REG_BIT (reg_class_contents
[GENERAL_REGS
], i
)
358 /* ??? This is only a rough heuristic. It doesn't cope well
359 with alternative ABIs, but that's an optimization rather than
360 correctness issue. */
361 if (default_function_abi
.clobbers_full_reg_p (i
))
362 target_clobbered_regs
++;
367 for (speed
= 0; speed
< 2; speed
++)
369 crtl
->maybe_hot_insn_p
= speed
;
370 /* Set up the costs for using extra registers:
372 1) If not many free registers remain, we should prefer having an
373 additional move to decreasing the number of available registers.
375 2) If no registers are available, we need to spill, which may require
376 storing the old value to memory and loading it back
377 (TARGET_SPILL_COST). */
380 emit_move_insn (reg1
, reg2
);
383 target_reg_cost
[speed
] = seq_cost (seq
, speed
);
386 emit_move_insn (mem
, reg1
);
387 emit_move_insn (reg2
, mem
);
390 target_spill_cost
[speed
] = seq_cost (seq
, speed
);
392 default_rtl_profile ();
395 /* Estimates cost of increased register pressure caused by making N_NEW new
396 registers live around the loop. N_OLD is the number of registers live
397 around the loop. If CALL_P is true, also take into account that
398 call-used registers may be clobbered in the loop body, reducing the
399 number of available registers before we spill. */
402 estimate_reg_pressure_cost (unsigned n_new
, unsigned n_old
, bool speed
,
406 unsigned regs_needed
= n_new
+ n_old
;
407 unsigned available_regs
= target_avail_regs
;
409 /* If there is a call in the loop body, the call-clobbered registers
410 are not available for loop invariants. */
412 available_regs
= available_regs
- target_clobbered_regs
;
414 /* If we have enough registers, we should use them and not restrict
415 the transformations unnecessarily. */
416 if (regs_needed
+ target_res_regs
<= available_regs
)
419 if (regs_needed
<= available_regs
)
420 /* If we are close to running out of registers, try to preserve
422 cost
= target_reg_cost
[speed
] * n_new
;
424 /* If we run out of registers, it is very expensive to add another
426 cost
= target_spill_cost
[speed
] * n_new
;
428 if (optimize
&& (flag_ira_region
== IRA_REGION_ALL
429 || flag_ira_region
== IRA_REGION_MIXED
)
430 && number_of_loops (cfun
) <= (unsigned) IRA_MAX_LOOPS_NUM
)
431 /* IRA regional allocation deals with high register pressure
432 better. So decrease the cost (to do more accurate the cost
433 calculation for IRA, we need to know how many registers lives
434 through the loop transparently). */
440 /* Sets EDGE_LOOP_EXIT flag for all loop exits. */
443 mark_loop_exit_edges (void)
448 if (number_of_loops (cfun
) <= 1)
451 FOR_EACH_BB_FN (bb
, cfun
)
455 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
457 if (loop_outer (bb
->loop_father
)
458 && loop_exit_edge_p (bb
->loop_father
, e
))
459 e
->flags
|= EDGE_LOOP_EXIT
;
461 e
->flags
&= ~EDGE_LOOP_EXIT
;
466 /* Return exit edge if loop has only one exit that is likely
467 to be executed on runtime (i.e. it is not EH or leading
471 single_likely_exit (class loop
*loop
)
473 edge found
= single_exit (loop
);
480 exits
= get_loop_exit_edges (loop
);
481 FOR_EACH_VEC_ELT (exits
, i
, ex
)
483 if (probably_never_executed_edge_p (cfun
, ex
)
484 /* We want to rule out paths to noreturns but not low probabilities
485 resulting from adjustments or combining.
486 FIXME: once we have better quality tracking, make this more
488 || ex
->probability
<= profile_probability::very_unlikely ())
503 /* Gets basic blocks of a LOOP. Header is the 0-th block, rest is in dfs
504 order against direction of edges from latch. Specially, if
505 header != latch, latch is the 1-st block. */
508 get_loop_hot_path (const class loop
*loop
)
510 basic_block bb
= loop
->header
;
511 vec
<basic_block
> path
= vNULL
;
512 bitmap visited
= BITMAP_ALLOC (NULL
);
521 bitmap_set_bit (visited
, bb
->index
);
522 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
523 if ((!best
|| e
->probability
> best
->probability
)
524 && !loop_exit_edge_p (loop
, e
)
525 && !bitmap_bit_p (visited
, e
->dest
->index
))
527 if (!best
|| best
->dest
== loop
->header
)
531 BITMAP_FREE (visited
);