1 /* Natural loop analysis code for GNU compiler.
2 Copyright (C) 2002-2016 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"
34 struct target_cfgloop default_target_cfgloop
;
36 struct target_cfgloop
*this_target_cfgloop
= &default_target_cfgloop
;
39 /* Checks whether BB is executed exactly once in each LOOP iteration. */
42 just_once_each_iteration_p (const struct loop
*loop
, const_basic_block bb
)
44 /* It must be executed at least once each iteration. */
45 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, bb
))
49 if (bb
->loop_father
!= loop
)
52 /* But this was not enough. We might have some irreducible loop here. */
53 if (bb
->flags
& BB_IRREDUCIBLE_LOOP
)
59 /* Marks blocks and edges that are part of non-recognized loops; i.e. we
60 throw away all latch edges and mark blocks inside any remaining cycle.
61 Everything is a bit complicated due to fact we do not want to do this
62 for parts of cycles that only "pass" through some loop -- i.e. for
63 each cycle, we want to mark blocks that belong directly to innermost
64 loop containing the whole cycle.
66 LOOPS is the loop tree. */
68 #define LOOP_REPR(LOOP) ((LOOP)->num + last_basic_block_for_fn (cfun))
69 #define BB_REPR(BB) ((BB)->index + 1)
72 mark_irreducible_loops (void)
75 struct graph_edge
*ge
;
81 int num
= number_of_loops (cfun
);
83 bool irred_loop_found
= false;
86 gcc_assert (current_loops
!= NULL
);
88 /* Reset the flags. */
89 FOR_BB_BETWEEN (act
, ENTRY_BLOCK_PTR_FOR_FN (cfun
),
90 EXIT_BLOCK_PTR_FOR_FN (cfun
), next_bb
)
92 act
->flags
&= ~BB_IRREDUCIBLE_LOOP
;
93 FOR_EACH_EDGE (e
, ei
, act
->succs
)
94 e
->flags
&= ~EDGE_IRREDUCIBLE_LOOP
;
97 /* Create the edge lists. */
98 g
= new_graph (last_basic_block_for_fn (cfun
) + num
);
100 FOR_BB_BETWEEN (act
, ENTRY_BLOCK_PTR_FOR_FN (cfun
),
101 EXIT_BLOCK_PTR_FOR_FN (cfun
), next_bb
)
102 FOR_EACH_EDGE (e
, ei
, act
->succs
)
104 /* Ignore edges to exit. */
105 if (e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
109 dest
= BB_REPR (e
->dest
);
111 /* Ignore latch edges. */
112 if (e
->dest
->loop_father
->header
== e
->dest
113 && e
->dest
->loop_father
->latch
== act
)
116 /* Edges inside a single loop should be left where they are. Edges
117 to subloop headers should lead to representative of the subloop,
118 but from the same place.
120 Edges exiting loops should lead from representative
121 of the son of nearest common ancestor of the loops in that
124 if (e
->dest
->loop_father
->header
== e
->dest
)
125 dest
= LOOP_REPR (e
->dest
->loop_father
);
127 if (!flow_bb_inside_loop_p (act
->loop_father
, e
->dest
))
129 depth
= 1 + loop_depth (find_common_loop (act
->loop_father
,
130 e
->dest
->loop_father
));
131 if (depth
== loop_depth (act
->loop_father
))
132 cloop
= act
->loop_father
;
134 cloop
= (*act
->loop_father
->superloops
)[depth
];
136 src
= LOOP_REPR (cloop
);
139 add_edge (g
, src
, dest
)->data
= e
;
142 /* Find the strongly connected components. */
143 graphds_scc (g
, NULL
);
145 /* Mark the irreducible loops. */
146 for (i
= 0; i
< g
->n_vertices
; i
++)
147 for (ge
= g
->vertices
[i
].succ
; ge
; ge
= ge
->succ_next
)
149 edge real
= (edge
) ge
->data
;
150 /* edge E in graph G is irreducible if it connects two vertices in the
153 /* All edges should lead from a component with higher number to the
154 one with lower one. */
155 gcc_assert (g
->vertices
[ge
->src
].component
>= g
->vertices
[ge
->dest
].component
);
157 if (g
->vertices
[ge
->src
].component
!= g
->vertices
[ge
->dest
].component
)
160 real
->flags
|= EDGE_IRREDUCIBLE_LOOP
;
161 irred_loop_found
= true;
162 if (flow_bb_inside_loop_p (real
->src
->loop_father
, real
->dest
))
163 real
->src
->flags
|= BB_IRREDUCIBLE_LOOP
;
168 loops_state_set (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS
);
169 return irred_loop_found
;
172 /* Counts number of insns inside LOOP. */
174 num_loop_insns (const struct loop
*loop
)
176 basic_block
*bbs
, bb
;
177 unsigned i
, ninsns
= 0;
180 bbs
= get_loop_body (loop
);
181 for (i
= 0; i
< loop
->num_nodes
; i
++)
184 FOR_BB_INSNS (bb
, insn
)
185 if (NONDEBUG_INSN_P (insn
))
191 ninsns
= 1; /* To avoid division by zero. */
196 /* Counts number of insns executed on average per iteration LOOP. */
198 average_num_loop_insns (const struct loop
*loop
)
200 basic_block
*bbs
, bb
;
201 unsigned i
, binsns
, ninsns
, ratio
;
205 bbs
= get_loop_body (loop
);
206 for (i
= 0; i
< loop
->num_nodes
; i
++)
211 FOR_BB_INSNS (bb
, insn
)
212 if (NONDEBUG_INSN_P (insn
))
215 ratio
= loop
->header
->frequency
== 0
217 : (bb
->frequency
* BB_FREQ_MAX
) / loop
->header
->frequency
;
218 ninsns
+= binsns
* ratio
;
222 ninsns
/= BB_FREQ_MAX
;
224 ninsns
= 1; /* To avoid division by zero. */
229 /* Returns expected number of iterations of LOOP, according to
230 measured or guessed profile. No bounding is done on the
234 expected_loop_iterations_unbounded (const struct loop
*loop
,
235 bool *read_profile_p
)
242 *read_profile_p
= false;
244 /* Average loop rolls about 3 times. If we have no profile at all, it is
246 if (profile_status_for_fn (cfun
) == PROFILE_ABSENT
)
248 else if (loop
->latch
->count
|| loop
->header
->count
)
250 gcov_type count_in
, count_latch
;
255 FOR_EACH_EDGE (e
, ei
, loop
->header
->preds
)
256 if (e
->src
== loop
->latch
)
257 count_latch
= e
->count
;
259 count_in
+= e
->count
;
262 expected
= count_latch
* 2;
265 expected
= (count_latch
+ count_in
- 1) / count_in
;
267 *read_profile_p
= true;
272 int freq_in
, freq_latch
;
277 FOR_EACH_EDGE (e
, ei
, loop
->header
->preds
)
278 if (e
->src
== loop
->latch
)
279 freq_latch
= EDGE_FREQUENCY (e
);
281 freq_in
+= EDGE_FREQUENCY (e
);
285 /* If we have no profile at all, expect 3 iterations. */
289 expected
= freq_latch
* 2;
292 expected
= (freq_latch
+ freq_in
- 1) / freq_in
;
295 HOST_WIDE_INT max
= get_max_loop_iterations_int (loop
);
296 if (max
!= -1 && max
< expected
)
301 /* Returns expected number of LOOP iterations. The returned value is bounded
302 by REG_BR_PROB_BASE. */
305 expected_loop_iterations (struct loop
*loop
)
307 gcov_type expected
= expected_loop_iterations_unbounded (loop
);
308 return (expected
> REG_BR_PROB_BASE
? REG_BR_PROB_BASE
: expected
);
311 /* Returns the maximum level of nesting of subloops of LOOP. */
314 get_loop_level (const struct loop
*loop
)
316 const struct loop
*ploop
;
319 for (ploop
= loop
->inner
; ploop
; ploop
= ploop
->next
)
321 l
= get_loop_level (ploop
);
328 /* Initialize the constants for computing set costs. */
331 init_set_costs (void)
335 rtx reg1
= gen_raw_REG (SImode
, LAST_VIRTUAL_REGISTER
+ 1);
336 rtx reg2
= gen_raw_REG (SImode
, LAST_VIRTUAL_REGISTER
+ 2);
337 rtx addr
= gen_raw_REG (Pmode
, LAST_VIRTUAL_REGISTER
+ 3);
338 rtx mem
= validize_mem (gen_rtx_MEM (SImode
, addr
));
341 target_avail_regs
= 0;
342 target_clobbered_regs
= 0;
343 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
344 if (TEST_HARD_REG_BIT (reg_class_contents
[GENERAL_REGS
], i
)
348 if (call_used_regs
[i
])
349 target_clobbered_regs
++;
354 for (speed
= 0; speed
< 2; speed
++)
356 crtl
->maybe_hot_insn_p
= speed
;
357 /* Set up the costs for using extra registers:
359 1) If not many free registers remain, we should prefer having an
360 additional move to decreasing the number of available registers.
362 2) If no registers are available, we need to spill, which may require
363 storing the old value to memory and loading it back
364 (TARGET_SPILL_COST). */
367 emit_move_insn (reg1
, reg2
);
370 target_reg_cost
[speed
] = seq_cost (seq
, speed
);
373 emit_move_insn (mem
, reg1
);
374 emit_move_insn (reg2
, mem
);
377 target_spill_cost
[speed
] = seq_cost (seq
, speed
);
379 default_rtl_profile ();
382 /* Estimates cost of increased register pressure caused by making N_NEW new
383 registers live around the loop. N_OLD is the number of registers live
384 around the loop. If CALL_P is true, also take into account that
385 call-used registers may be clobbered in the loop body, reducing the
386 number of available registers before we spill. */
389 estimate_reg_pressure_cost (unsigned n_new
, unsigned n_old
, bool speed
,
393 unsigned regs_needed
= n_new
+ n_old
;
394 unsigned available_regs
= target_avail_regs
;
396 /* If there is a call in the loop body, the call-clobbered registers
397 are not available for loop invariants. */
399 available_regs
= available_regs
- target_clobbered_regs
;
401 /* If we have enough registers, we should use them and not restrict
402 the transformations unnecessarily. */
403 if (regs_needed
+ target_res_regs
<= available_regs
)
406 if (regs_needed
<= available_regs
)
407 /* If we are close to running out of registers, try to preserve
409 cost
= target_reg_cost
[speed
] * n_new
;
411 /* If we run out of registers, it is very expensive to add another
413 cost
= target_spill_cost
[speed
] * n_new
;
415 if (optimize
&& (flag_ira_region
== IRA_REGION_ALL
416 || flag_ira_region
== IRA_REGION_MIXED
)
417 && number_of_loops (cfun
) <= (unsigned) IRA_MAX_LOOPS_NUM
)
418 /* IRA regional allocation deals with high register pressure
419 better. So decrease the cost (to do more accurate the cost
420 calculation for IRA, we need to know how many registers lives
421 through the loop transparently). */
427 /* Sets EDGE_LOOP_EXIT flag for all loop exits. */
430 mark_loop_exit_edges (void)
435 if (number_of_loops (cfun
) <= 1)
438 FOR_EACH_BB_FN (bb
, cfun
)
442 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
444 if (loop_outer (bb
->loop_father
)
445 && loop_exit_edge_p (bb
->loop_father
, e
))
446 e
->flags
|= EDGE_LOOP_EXIT
;
448 e
->flags
&= ~EDGE_LOOP_EXIT
;
453 /* Return exit edge if loop has only one exit that is likely
454 to be executed on runtime (i.e. it is not EH or leading
458 single_likely_exit (struct loop
*loop
)
460 edge found
= single_exit (loop
);
467 exits
= get_loop_exit_edges (loop
);
468 FOR_EACH_VEC_ELT (exits
, i
, ex
)
470 if (ex
->flags
& (EDGE_EH
| EDGE_ABNORMAL_CALL
))
472 /* The constant of 5 is set in a way so noreturn calls are
473 ruled out by this test. The static branch prediction algorithm
474 will not assign such a low probability to conditionals for usual
476 if (profile_status_for_fn (cfun
) != PROFILE_ABSENT
477 && ex
->probability
< 5 && !ex
->count
)
492 /* Gets basic blocks of a LOOP. Header is the 0-th block, rest is in dfs
493 order against direction of edges from latch. Specially, if
494 header != latch, latch is the 1-st block. */
497 get_loop_hot_path (const struct loop
*loop
)
499 basic_block bb
= loop
->header
;
500 vec
<basic_block
> path
= vNULL
;
501 bitmap visited
= BITMAP_ALLOC (NULL
);
510 bitmap_set_bit (visited
, bb
->index
);
511 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
512 if ((!best
|| e
->probability
> best
->probability
)
513 && !loop_exit_edge_p (loop
, e
)
514 && !bitmap_bit_p (visited
, e
->dest
->index
))
516 if (!best
|| best
->dest
== loop
->header
)
520 BITMAP_FREE (visited
);