1 /* Natural loop analysis code for GNU compiler.
2 Copyright (C) 2002-2015 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"
25 #include "hard-reg-set.h"
34 #include "dominance.h"
36 #include "basic-block.h"
43 struct target_cfgloop default_target_cfgloop
;
45 struct target_cfgloop
*this_target_cfgloop
= &default_target_cfgloop
;
48 /* Checks whether BB is executed exactly once in each LOOP iteration. */
51 just_once_each_iteration_p (const struct loop
*loop
, const_basic_block bb
)
53 /* It must be executed at least once each iteration. */
54 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, bb
))
58 if (bb
->loop_father
!= loop
)
61 /* But this was not enough. We might have some irreducible loop here. */
62 if (bb
->flags
& BB_IRREDUCIBLE_LOOP
)
68 /* Marks blocks and edges that are part of non-recognized loops; i.e. we
69 throw away all latch edges and mark blocks inside any remaining cycle.
70 Everything is a bit complicated due to fact we do not want to do this
71 for parts of cycles that only "pass" through some loop -- i.e. for
72 each cycle, we want to mark blocks that belong directly to innermost
73 loop containing the whole cycle.
75 LOOPS is the loop tree. */
77 #define LOOP_REPR(LOOP) ((LOOP)->num + last_basic_block_for_fn (cfun))
78 #define BB_REPR(BB) ((BB)->index + 1)
81 mark_irreducible_loops (void)
84 struct graph_edge
*ge
;
90 int num
= number_of_loops (cfun
);
92 bool irred_loop_found
= false;
95 gcc_assert (current_loops
!= NULL
);
97 /* Reset the flags. */
98 FOR_BB_BETWEEN (act
, ENTRY_BLOCK_PTR_FOR_FN (cfun
),
99 EXIT_BLOCK_PTR_FOR_FN (cfun
), next_bb
)
101 act
->flags
&= ~BB_IRREDUCIBLE_LOOP
;
102 FOR_EACH_EDGE (e
, ei
, act
->succs
)
103 e
->flags
&= ~EDGE_IRREDUCIBLE_LOOP
;
106 /* Create the edge lists. */
107 g
= new_graph (last_basic_block_for_fn (cfun
) + num
);
109 FOR_BB_BETWEEN (act
, ENTRY_BLOCK_PTR_FOR_FN (cfun
),
110 EXIT_BLOCK_PTR_FOR_FN (cfun
), next_bb
)
111 FOR_EACH_EDGE (e
, ei
, act
->succs
)
113 /* Ignore edges to exit. */
114 if (e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
118 dest
= BB_REPR (e
->dest
);
120 /* Ignore latch edges. */
121 if (e
->dest
->loop_father
->header
== e
->dest
122 && e
->dest
->loop_father
->latch
== act
)
125 /* Edges inside a single loop should be left where they are. Edges
126 to subloop headers should lead to representative of the subloop,
127 but from the same place.
129 Edges exiting loops should lead from representative
130 of the son of nearest common ancestor of the loops in that
133 if (e
->dest
->loop_father
->header
== e
->dest
)
134 dest
= LOOP_REPR (e
->dest
->loop_father
);
136 if (!flow_bb_inside_loop_p (act
->loop_father
, e
->dest
))
138 depth
= 1 + loop_depth (find_common_loop (act
->loop_father
,
139 e
->dest
->loop_father
));
140 if (depth
== loop_depth (act
->loop_father
))
141 cloop
= act
->loop_father
;
143 cloop
= (*act
->loop_father
->superloops
)[depth
];
145 src
= LOOP_REPR (cloop
);
148 add_edge (g
, src
, dest
)->data
= e
;
151 /* Find the strongly connected components. */
152 graphds_scc (g
, NULL
);
154 /* Mark the irreducible loops. */
155 for (i
= 0; i
< g
->n_vertices
; i
++)
156 for (ge
= g
->vertices
[i
].succ
; ge
; ge
= ge
->succ_next
)
158 edge real
= (edge
) ge
->data
;
159 /* edge E in graph G is irreducible if it connects two vertices in the
162 /* All edges should lead from a component with higher number to the
163 one with lower one. */
164 gcc_assert (g
->vertices
[ge
->src
].component
>= g
->vertices
[ge
->dest
].component
);
166 if (g
->vertices
[ge
->src
].component
!= g
->vertices
[ge
->dest
].component
)
169 real
->flags
|= EDGE_IRREDUCIBLE_LOOP
;
170 irred_loop_found
= true;
171 if (flow_bb_inside_loop_p (real
->src
->loop_father
, real
->dest
))
172 real
->src
->flags
|= BB_IRREDUCIBLE_LOOP
;
177 loops_state_set (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS
);
178 return irred_loop_found
;
181 /* Counts number of insns inside LOOP. */
183 num_loop_insns (const struct loop
*loop
)
185 basic_block
*bbs
, bb
;
186 unsigned i
, ninsns
= 0;
189 bbs
= get_loop_body (loop
);
190 for (i
= 0; i
< loop
->num_nodes
; i
++)
193 FOR_BB_INSNS (bb
, insn
)
194 if (NONDEBUG_INSN_P (insn
))
200 ninsns
= 1; /* To avoid division by zero. */
205 /* Counts number of insns executed on average per iteration LOOP. */
207 average_num_loop_insns (const struct loop
*loop
)
209 basic_block
*bbs
, bb
;
210 unsigned i
, binsns
, ninsns
, ratio
;
214 bbs
= get_loop_body (loop
);
215 for (i
= 0; i
< loop
->num_nodes
; i
++)
220 FOR_BB_INSNS (bb
, insn
)
221 if (NONDEBUG_INSN_P (insn
))
224 ratio
= loop
->header
->frequency
== 0
226 : (bb
->frequency
* BB_FREQ_MAX
) / loop
->header
->frequency
;
227 ninsns
+= binsns
* ratio
;
231 ninsns
/= BB_FREQ_MAX
;
233 ninsns
= 1; /* To avoid division by zero. */
238 /* Returns expected number of iterations of LOOP, according to
239 measured or guessed profile. No bounding is done on the
243 expected_loop_iterations_unbounded (const struct loop
*loop
)
248 if (loop
->latch
->count
|| loop
->header
->count
)
250 gcov_type count_in
, count_latch
, expected
;
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;
264 expected
= (count_latch
+ count_in
- 1) / count_in
;
270 int freq_in
, freq_latch
;
275 FOR_EACH_EDGE (e
, ei
, loop
->header
->preds
)
276 if (e
->src
== loop
->latch
)
277 freq_latch
= EDGE_FREQUENCY (e
);
279 freq_in
+= EDGE_FREQUENCY (e
);
282 return freq_latch
* 2;
284 return (freq_latch
+ freq_in
- 1) / freq_in
;
288 /* Returns expected number of LOOP iterations. The returned value is bounded
289 by REG_BR_PROB_BASE. */
292 expected_loop_iterations (const struct loop
*loop
)
294 gcov_type expected
= expected_loop_iterations_unbounded (loop
);
295 return (expected
> REG_BR_PROB_BASE
? REG_BR_PROB_BASE
: expected
);
298 /* Returns the maximum level of nesting of subloops of LOOP. */
301 get_loop_level (const struct loop
*loop
)
303 const struct loop
*ploop
;
306 for (ploop
= loop
->inner
; ploop
; ploop
= ploop
->next
)
308 l
= get_loop_level (ploop
);
315 /* Initialize the constants for computing set costs. */
318 init_set_costs (void)
322 rtx reg1
= gen_raw_REG (SImode
, FIRST_PSEUDO_REGISTER
);
323 rtx reg2
= gen_raw_REG (SImode
, FIRST_PSEUDO_REGISTER
+ 1);
324 rtx addr
= gen_raw_REG (Pmode
, FIRST_PSEUDO_REGISTER
+ 2);
325 rtx mem
= validize_mem (gen_rtx_MEM (SImode
, addr
));
328 target_avail_regs
= 0;
329 target_clobbered_regs
= 0;
330 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
331 if (TEST_HARD_REG_BIT (reg_class_contents
[GENERAL_REGS
], i
)
335 if (call_used_regs
[i
])
336 target_clobbered_regs
++;
341 for (speed
= 0; speed
< 2; speed
++)
343 crtl
->maybe_hot_insn_p
= speed
;
344 /* Set up the costs for using extra registers:
346 1) If not many free registers remain, we should prefer having an
347 additional move to decreasing the number of available registers.
349 2) If no registers are available, we need to spill, which may require
350 storing the old value to memory and loading it back
351 (TARGET_SPILL_COST). */
354 emit_move_insn (reg1
, reg2
);
357 target_reg_cost
[speed
] = seq_cost (seq
, speed
);
360 emit_move_insn (mem
, reg1
);
361 emit_move_insn (reg2
, mem
);
364 target_spill_cost
[speed
] = seq_cost (seq
, speed
);
366 default_rtl_profile ();
369 /* Estimates cost of increased register pressure caused by making N_NEW new
370 registers live around the loop. N_OLD is the number of registers live
371 around the loop. If CALL_P is true, also take into account that
372 call-used registers may be clobbered in the loop body, reducing the
373 number of available registers before we spill. */
376 estimate_reg_pressure_cost (unsigned n_new
, unsigned n_old
, bool speed
,
380 unsigned regs_needed
= n_new
+ n_old
;
381 unsigned available_regs
= target_avail_regs
;
383 /* If there is a call in the loop body, the call-clobbered registers
384 are not available for loop invariants. */
386 available_regs
= available_regs
- target_clobbered_regs
;
388 /* If we have enough registers, we should use them and not restrict
389 the transformations unnecessarily. */
390 if (regs_needed
+ target_res_regs
<= available_regs
)
393 if (regs_needed
<= available_regs
)
394 /* If we are close to running out of registers, try to preserve
396 cost
= target_reg_cost
[speed
] * n_new
;
398 /* If we run out of registers, it is very expensive to add another
400 cost
= target_spill_cost
[speed
] * n_new
;
402 if (optimize
&& (flag_ira_region
== IRA_REGION_ALL
403 || flag_ira_region
== IRA_REGION_MIXED
)
404 && number_of_loops (cfun
) <= (unsigned) IRA_MAX_LOOPS_NUM
)
405 /* IRA regional allocation deals with high register pressure
406 better. So decrease the cost (to do more accurate the cost
407 calculation for IRA, we need to know how many registers lives
408 through the loop transparently). */
414 /* Sets EDGE_LOOP_EXIT flag for all loop exits. */
417 mark_loop_exit_edges (void)
422 if (number_of_loops (cfun
) <= 1)
425 FOR_EACH_BB_FN (bb
, cfun
)
429 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
431 if (loop_outer (bb
->loop_father
)
432 && loop_exit_edge_p (bb
->loop_father
, e
))
433 e
->flags
|= EDGE_LOOP_EXIT
;
435 e
->flags
&= ~EDGE_LOOP_EXIT
;
440 /* Return exit edge if loop has only one exit that is likely
441 to be executed on runtime (i.e. it is not EH or leading
445 single_likely_exit (struct loop
*loop
)
447 edge found
= single_exit (loop
);
454 exits
= get_loop_exit_edges (loop
);
455 FOR_EACH_VEC_ELT (exits
, i
, ex
)
457 if (ex
->flags
& (EDGE_EH
| EDGE_ABNORMAL_CALL
))
459 /* The constant of 5 is set in a way so noreturn calls are
460 ruled out by this test. The static branch prediction algorithm
461 will not assign such a low probability to conditionals for usual
463 if (profile_status_for_fn (cfun
) != PROFILE_ABSENT
464 && ex
->probability
< 5 && !ex
->count
)
479 /* Gets basic blocks of a LOOP. Header is the 0-th block, rest is in dfs
480 order against direction of edges from latch. Specially, if
481 header != latch, latch is the 1-st block. */
484 get_loop_hot_path (const struct loop
*loop
)
486 basic_block bb
= loop
->header
;
487 vec
<basic_block
> path
= vNULL
;
488 bitmap visited
= BITMAP_ALLOC (NULL
);
497 bitmap_set_bit (visited
, bb
->index
);
498 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
499 if ((!best
|| e
->probability
> best
->probability
)
500 && !loop_exit_edge_p (loop
, e
)
501 && !bitmap_bit_p (visited
, e
->dest
->index
))
503 if (!best
|| best
->dest
== loop
->header
)
507 BITMAP_FREE (visited
);