1 /* Natural loop analysis code for GNU compiler.
2 Copyright (C) 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009
3 Free Software Foundation, Inc.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
23 #include "coretypes.h"
26 #include "hard-reg-set.h"
28 #include "basic-block.h"
35 /* Checks whether BB is executed exactly once in each LOOP iteration. */
38 just_once_each_iteration_p (const struct loop
*loop
, const_basic_block bb
)
40 /* It must be executed at least once each iteration. */
41 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, bb
))
45 if (bb
->loop_father
!= loop
)
48 /* But this was not enough. We might have some irreducible loop here. */
49 if (bb
->flags
& BB_IRREDUCIBLE_LOOP
)
55 /* Marks the edge E in graph G irreducible if it connects two vertices in the
59 check_irred (struct graph
*g
, struct graph_edge
*e
)
61 edge real
= (edge
) e
->data
;
63 /* All edges should lead from a component with higher number to the
64 one with lower one. */
65 gcc_assert (g
->vertices
[e
->src
].component
>= g
->vertices
[e
->dest
].component
);
67 if (g
->vertices
[e
->src
].component
!= g
->vertices
[e
->dest
].component
)
70 real
->flags
|= EDGE_IRREDUCIBLE_LOOP
;
71 if (flow_bb_inside_loop_p (real
->src
->loop_father
, real
->dest
))
72 real
->src
->flags
|= BB_IRREDUCIBLE_LOOP
;
75 /* Marks blocks and edges that are part of non-recognized loops; i.e. we
76 throw away all latch edges and mark blocks inside any remaining cycle.
77 Everything is a bit complicated due to fact we do not want to do this
78 for parts of cycles that only "pass" through some loop -- i.e. for
79 each cycle, we want to mark blocks that belong directly to innermost
80 loop containing the whole cycle.
82 LOOPS is the loop tree. */
84 #define LOOP_REPR(LOOP) ((LOOP)->num + last_basic_block)
85 #define BB_REPR(BB) ((BB)->index + 1)
88 mark_irreducible_loops (void)
96 int num
= number_of_loops ();
99 gcc_assert (current_loops
!= NULL
);
101 /* Reset the flags. */
102 FOR_BB_BETWEEN (act
, ENTRY_BLOCK_PTR
, EXIT_BLOCK_PTR
, next_bb
)
104 act
->flags
&= ~BB_IRREDUCIBLE_LOOP
;
105 FOR_EACH_EDGE (e
, ei
, act
->succs
)
106 e
->flags
&= ~EDGE_IRREDUCIBLE_LOOP
;
109 /* Create the edge lists. */
110 g
= new_graph (last_basic_block
+ num
);
112 FOR_BB_BETWEEN (act
, ENTRY_BLOCK_PTR
, EXIT_BLOCK_PTR
, next_bb
)
113 FOR_EACH_EDGE (e
, ei
, act
->succs
)
115 /* Ignore edges to exit. */
116 if (e
->dest
== EXIT_BLOCK_PTR
)
120 dest
= BB_REPR (e
->dest
);
122 /* Ignore latch edges. */
123 if (e
->dest
->loop_father
->header
== e
->dest
124 && e
->dest
->loop_father
->latch
== act
)
127 /* Edges inside a single loop should be left where they are. Edges
128 to subloop headers should lead to representative of the subloop,
129 but from the same place.
131 Edges exiting loops should lead from representative
132 of the son of nearest common ancestor of the loops in that
135 if (e
->dest
->loop_father
->header
== e
->dest
)
136 dest
= LOOP_REPR (e
->dest
->loop_father
);
138 if (!flow_bb_inside_loop_p (act
->loop_father
, e
->dest
))
140 depth
= 1 + loop_depth (find_common_loop (act
->loop_father
,
141 e
->dest
->loop_father
));
142 if (depth
== loop_depth (act
->loop_father
))
143 cloop
= act
->loop_father
;
145 cloop
= VEC_index (loop_p
, act
->loop_father
->superloops
, depth
);
147 src
= LOOP_REPR (cloop
);
150 add_edge (g
, src
, dest
)->data
= e
;
153 /* Find the strongly connected components. */
154 graphds_scc (g
, NULL
);
156 /* Mark the irreducible loops. */
157 for_each_edge (g
, check_irred
);
161 loops_state_set (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS
);
164 /* Counts number of insns inside LOOP. */
166 num_loop_insns (const struct loop
*loop
)
168 basic_block
*bbs
, bb
;
169 unsigned i
, ninsns
= 0;
172 bbs
= get_loop_body (loop
);
173 for (i
= 0; i
< loop
->num_nodes
; i
++)
177 for (insn
= BB_HEAD (bb
); insn
!= BB_END (bb
); insn
= NEXT_INSN (insn
))
186 /* Counts number of insns executed on average per iteration LOOP. */
188 average_num_loop_insns (const struct loop
*loop
)
190 basic_block
*bbs
, bb
;
191 unsigned i
, binsns
, ninsns
, ratio
;
195 bbs
= get_loop_body (loop
);
196 for (i
= 0; i
< loop
->num_nodes
; i
++)
201 for (insn
= BB_HEAD (bb
); insn
!= BB_END (bb
); insn
= NEXT_INSN (insn
))
205 ratio
= loop
->header
->frequency
== 0
207 : (bb
->frequency
* BB_FREQ_MAX
) / loop
->header
->frequency
;
208 ninsns
+= binsns
* ratio
;
212 ninsns
/= BB_FREQ_MAX
;
214 ninsns
= 1; /* To avoid division by zero. */
219 /* Returns expected number of iterations of LOOP, according to
220 measured or guessed profile. No bounding is done on the
224 expected_loop_iterations_unbounded (const struct loop
*loop
)
229 if (loop
->latch
->count
|| loop
->header
->count
)
231 gcov_type count_in
, count_latch
, expected
;
236 FOR_EACH_EDGE (e
, ei
, loop
->header
->preds
)
237 if (e
->src
== loop
->latch
)
238 count_latch
= e
->count
;
240 count_in
+= e
->count
;
243 expected
= count_latch
* 2;
245 expected
= (count_latch
+ count_in
- 1) / count_in
;
251 int freq_in
, freq_latch
;
256 FOR_EACH_EDGE (e
, ei
, loop
->header
->preds
)
257 if (e
->src
== loop
->latch
)
258 freq_latch
= EDGE_FREQUENCY (e
);
260 freq_in
+= EDGE_FREQUENCY (e
);
263 return freq_latch
* 2;
265 return (freq_latch
+ freq_in
- 1) / freq_in
;
269 /* Returns expected number of LOOP iterations. The returned value is bounded
270 by REG_BR_PROB_BASE. */
273 expected_loop_iterations (const struct loop
*loop
)
275 gcov_type expected
= expected_loop_iterations_unbounded (loop
);
276 return (expected
> REG_BR_PROB_BASE
? REG_BR_PROB_BASE
: expected
);
279 /* Returns the maximum level of nesting of subloops of LOOP. */
282 get_loop_level (const struct loop
*loop
)
284 const struct loop
*ploop
;
287 for (ploop
= loop
->inner
; ploop
; ploop
= ploop
->next
)
289 l
= get_loop_level (ploop
);
296 /* Returns estimate on cost of computing SEQ. */
299 seq_cost (const_rtx seq
, bool speed
)
304 for (; seq
; seq
= NEXT_INSN (seq
))
306 set
= single_set (seq
);
308 cost
+= rtx_cost (set
, SET
, speed
);
316 /* The properties of the target. */
318 unsigned target_avail_regs
; /* Number of available registers. */
319 unsigned target_res_regs
; /* Number of registers reserved for temporary
321 unsigned target_reg_cost
[2]; /* The cost for register when there still
322 is some reserve, but we are approaching
323 the number of available registers. */
324 unsigned target_spill_cost
[2]; /* The cost for register when we need
327 /* Initialize the constants for computing set costs. */
330 init_set_costs (void)
334 rtx reg1
= gen_raw_REG (SImode
, FIRST_PSEUDO_REGISTER
);
335 rtx reg2
= gen_raw_REG (SImode
, FIRST_PSEUDO_REGISTER
+ 1);
336 rtx addr
= gen_raw_REG (Pmode
, FIRST_PSEUDO_REGISTER
+ 2);
337 rtx mem
= validize_mem (gen_rtx_MEM (SImode
, addr
));
340 target_avail_regs
= 0;
341 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
342 if (TEST_HARD_REG_BIT (reg_class_contents
[GENERAL_REGS
], i
)
348 for (speed
= 0; speed
< 2; speed
++)
350 crtl
->maybe_hot_insn_p
= speed
;
351 /* Set up the costs for using extra registers:
353 1) If not many free registers remain, we should prefer having an
354 additional move to decreasing the number of available registers.
356 2) If no registers are available, we need to spill, which may require
357 storing the old value to memory and loading it back
358 (TARGET_SPILL_COST). */
361 emit_move_insn (reg1
, reg2
);
364 target_reg_cost
[speed
] = seq_cost (seq
, speed
);
367 emit_move_insn (mem
, reg1
);
368 emit_move_insn (reg2
, mem
);
371 target_spill_cost
[speed
] = seq_cost (seq
, speed
);
373 default_rtl_profile ();
376 /* Estimates cost of increased register pressure caused by making N_NEW new
377 registers live around the loop. N_OLD is the number of registers live
381 estimate_reg_pressure_cost (unsigned n_new
, unsigned n_old
, bool speed
)
384 unsigned regs_needed
= n_new
+ n_old
;
386 /* If we have enough registers, we should use them and not restrict
387 the transformations unnecessarily. */
388 if (regs_needed
+ target_res_regs
<= target_avail_regs
)
391 if (regs_needed
<= target_avail_regs
)
392 /* If we are close to running out of registers, try to preserve
394 cost
= target_reg_cost
[speed
] * n_new
;
396 /* If we run out of registers, it is very expensive to add another
398 cost
= target_spill_cost
[speed
] * n_new
;
400 if (optimize
&& (flag_ira_region
== IRA_REGION_ALL
401 || flag_ira_region
== IRA_REGION_MIXED
)
402 && number_of_loops () <= (unsigned) IRA_MAX_LOOPS_NUM
)
403 /* IRA regional allocation deals with high register pressure
404 better. So decrease the cost (to do more accurate the cost
405 calculation for IRA, we need to know how many registers lives
406 through the loop transparently). */
412 /* Sets EDGE_LOOP_EXIT flag for all loop exits. */
415 mark_loop_exit_edges (void)
420 if (number_of_loops () <= 1)
427 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
429 if (loop_outer (bb
->loop_father
)
430 && loop_exit_edge_p (bb
->loop_father
, e
))
431 e
->flags
|= EDGE_LOOP_EXIT
;
433 e
->flags
&= ~EDGE_LOOP_EXIT
;