1 /* Natural loop analysis code for GNU compiler.
2 Copyright (C) 2002, 2003, 2004, 2005, 2006 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 2, 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 COPYING. If not, write to the Free
18 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
23 #include "coretypes.h"
26 #include "hard-reg-set.h"
28 #include "basic-block.h"
34 /* Checks whether BB is executed exactly once in each LOOP iteration. */
37 just_once_each_iteration_p (const struct loop
*loop
, basic_block bb
)
39 /* It must be executed at least once each iteration. */
40 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, bb
))
44 if (bb
->loop_father
!= loop
)
47 /* But this was not enough. We might have some irreducible loop here. */
48 if (bb
->flags
& BB_IRREDUCIBLE_LOOP
)
54 /* Marks the edge E in graph G irreducible if it connects two vertices in the
58 check_irred (struct graph
*g
, struct graph_edge
*e
)
60 edge real
= (edge
) e
->data
;
62 /* All edges should lead from a component with higher number to the
63 one with lower one. */
64 gcc_assert (g
->vertices
[e
->src
].component
>= g
->vertices
[e
->dest
].component
);
66 if (g
->vertices
[e
->src
].component
!= g
->vertices
[e
->dest
].component
)
69 real
->flags
|= EDGE_IRREDUCIBLE_LOOP
;
70 if (flow_bb_inside_loop_p (real
->src
->loop_father
, real
->dest
))
71 real
->src
->flags
|= BB_IRREDUCIBLE_LOOP
;
74 /* Marks blocks and edges that are part of non-recognized loops; i.e. we
75 throw away all latch edges and mark blocks inside any remaining cycle.
76 Everything is a bit complicated due to fact we do not want to do this
77 for parts of cycles that only "pass" through some loop -- i.e. for
78 each cycle, we want to mark blocks that belong directly to innermost
79 loop containing the whole cycle.
81 LOOPS is the loop tree. */
83 #define LOOP_REPR(LOOP) ((LOOP)->num + last_basic_block)
84 #define BB_REPR(BB) ((BB)->index + 1)
87 mark_irreducible_loops (void)
95 int num
= number_of_loops ();
98 gcc_assert (current_loops
!= NULL
);
100 /* Reset the flags. */
101 FOR_BB_BETWEEN (act
, ENTRY_BLOCK_PTR
, EXIT_BLOCK_PTR
, next_bb
)
103 act
->flags
&= ~BB_IRREDUCIBLE_LOOP
;
104 FOR_EACH_EDGE (e
, ei
, act
->succs
)
105 e
->flags
&= ~EDGE_IRREDUCIBLE_LOOP
;
108 /* Create the edge lists. */
109 g
= new_graph (last_basic_block
+ num
);
111 FOR_BB_BETWEEN (act
, ENTRY_BLOCK_PTR
, EXIT_BLOCK_PTR
, next_bb
)
112 FOR_EACH_EDGE (e
, ei
, act
->succs
)
114 /* Ignore edges to exit. */
115 if (e
->dest
== EXIT_BLOCK_PTR
)
119 dest
= BB_REPR (e
->dest
);
121 /* Ignore latch edges. */
122 if (e
->dest
->loop_father
->header
== e
->dest
123 && e
->dest
->loop_father
->latch
== act
)
126 /* Edges inside a single loop should be left where they are. Edges
127 to subloop headers should lead to representative of the subloop,
128 but from the same place.
130 Edges exiting loops should lead from representative
131 of the son of nearest common ancestor of the loops in that
134 if (e
->dest
->loop_father
->header
== e
->dest
)
135 dest
= LOOP_REPR (e
->dest
->loop_father
);
137 if (!flow_bb_inside_loop_p (act
->loop_father
, e
->dest
))
139 depth
= 1 + loop_depth (find_common_loop (act
->loop_father
,
140 e
->dest
->loop_father
));
141 if (depth
== loop_depth (act
->loop_father
))
142 cloop
= act
->loop_father
;
144 cloop
= VEC_index (loop_p
, act
->loop_father
->superloops
, depth
);
146 src
= LOOP_REPR (cloop
);
149 add_edge (g
, src
, dest
)->data
= e
;
152 /* Find the strongly connected components. */
153 graphds_scc (g
, NULL
);
155 /* Mark the irreducible loops. */
156 for_each_edge (g
, check_irred
);
160 current_loops
->state
|= LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS
;
163 /* Counts number of insns inside LOOP. */
165 num_loop_insns (struct loop
*loop
)
167 basic_block
*bbs
, bb
;
168 unsigned i
, ninsns
= 0;
171 bbs
= get_loop_body (loop
);
172 for (i
= 0; i
< loop
->num_nodes
; i
++)
176 for (insn
= BB_HEAD (bb
); insn
!= BB_END (bb
); insn
= NEXT_INSN (insn
))
185 /* Counts number of insns executed on average per iteration LOOP. */
187 average_num_loop_insns (struct loop
*loop
)
189 basic_block
*bbs
, bb
;
190 unsigned i
, binsns
, ninsns
, ratio
;
194 bbs
= get_loop_body (loop
);
195 for (i
= 0; i
< loop
->num_nodes
; i
++)
200 for (insn
= BB_HEAD (bb
); insn
!= BB_END (bb
); insn
= NEXT_INSN (insn
))
204 ratio
= loop
->header
->frequency
== 0
206 : (bb
->frequency
* BB_FREQ_MAX
) / loop
->header
->frequency
;
207 ninsns
+= binsns
* ratio
;
211 ninsns
/= BB_FREQ_MAX
;
213 ninsns
= 1; /* To avoid division by zero. */
218 /* Returns expected number of iterations of LOOP, according to
219 measured or guessed profile. No bounding is done on the
223 expected_loop_iterations_unbounded (const struct loop
*loop
)
228 if (loop
->latch
->count
|| loop
->header
->count
)
230 gcov_type count_in
, count_latch
, expected
;
235 FOR_EACH_EDGE (e
, ei
, loop
->header
->preds
)
236 if (e
->src
== loop
->latch
)
237 count_latch
= e
->count
;
239 count_in
+= e
->count
;
242 expected
= count_latch
* 2;
244 expected
= (count_latch
+ count_in
- 1) / count_in
;
250 int freq_in
, freq_latch
;
255 FOR_EACH_EDGE (e
, ei
, loop
->header
->preds
)
256 if (e
->src
== loop
->latch
)
257 freq_latch
= EDGE_FREQUENCY (e
);
259 freq_in
+= EDGE_FREQUENCY (e
);
262 return freq_latch
* 2;
264 return (freq_latch
+ freq_in
- 1) / freq_in
;
268 /* Returns expected number of LOOP iterations. The returned value is bounded
269 by REG_BR_PROB_BASE. */
272 expected_loop_iterations (const struct loop
*loop
)
274 gcov_type expected
= expected_loop_iterations_unbounded (loop
);
275 return (expected
> REG_BR_PROB_BASE
? REG_BR_PROB_BASE
: expected
);
278 /* Returns the maximum level of nesting of subloops of LOOP. */
281 get_loop_level (const struct loop
*loop
)
283 const struct loop
*ploop
;
286 for (ploop
= loop
->inner
; ploop
; ploop
= ploop
->next
)
288 l
= get_loop_level (ploop
);
295 /* Returns estimate on cost of computing SEQ. */
303 for (; seq
; seq
= NEXT_INSN (seq
))
305 set
= single_set (seq
);
307 cost
+= rtx_cost (set
, SET
);
315 /* The properties of the target. */
317 unsigned target_avail_regs
; /* Number of available registers. */
318 unsigned target_res_regs
; /* Number of registers reserved for temporary
320 unsigned target_reg_cost
; /* The cost for register when there still
321 is some reserve, but we are approaching
322 the number of available registers. */
323 unsigned target_spill_cost
; /* The cost for register when we need
326 /* Initialize the constants for computing set costs. */
329 init_set_costs (void)
332 rtx reg1
= gen_raw_REG (SImode
, FIRST_PSEUDO_REGISTER
);
333 rtx reg2
= gen_raw_REG (SImode
, FIRST_PSEUDO_REGISTER
+ 1);
334 rtx addr
= gen_raw_REG (Pmode
, FIRST_PSEUDO_REGISTER
+ 2);
335 rtx mem
= validize_mem (gen_rtx_MEM (SImode
, addr
));
338 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
339 if (TEST_HARD_REG_BIT (reg_class_contents
[GENERAL_REGS
], i
)
345 /* Set up the costs for using extra registers:
347 1) If not many free registers remain, we should prefer having an
348 additional move to decreasing the number of available registers.
350 2) If no registers are available, we need to spill, which may require
351 storing the old value to memory and loading it back
352 (TARGET_SPILL_COST). */
355 emit_move_insn (reg1
, reg2
);
358 target_reg_cost
= seq_cost (seq
);
361 emit_move_insn (mem
, reg1
);
362 emit_move_insn (reg2
, mem
);
365 target_spill_cost
= seq_cost (seq
);
368 /* Estimates cost of increased register pressure caused by making N_NEW new
369 registers live around the loop. N_OLD is the number of registers live
373 estimate_reg_pressure_cost (unsigned n_new
, unsigned n_old
)
375 unsigned regs_needed
= n_new
+ n_old
;
377 /* If we have enough registers, we should use them and not restrict
378 the transformations unnecessarily. */
379 if (regs_needed
+ target_res_regs
<= target_avail_regs
)
382 /* If we are close to running out of registers, try to preserve them. */
383 if (regs_needed
<= target_avail_regs
)
384 return target_reg_cost
* n_new
;
386 /* If we run out of registers, it is very expensive to add another one. */
387 return target_spill_cost
* n_new
;
390 /* Sets EDGE_LOOP_EXIT flag for all loop exits. */
393 mark_loop_exit_edges (void)
398 if (number_of_loops () <= 1)
405 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
407 if (loop_outer (bb
->loop_father
)
408 && loop_exit_edge_p (bb
->loop_father
, e
))
409 e
->flags
|= EDGE_LOOP_EXIT
;
411 e
->flags
&= ~EDGE_LOOP_EXIT
;