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"
33 /* Checks whether BB is executed exactly once in each LOOP iteration. */
36 just_once_each_iteration_p (const struct loop
*loop
, basic_block bb
)
38 /* It must be executed at least once each iteration. */
39 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, bb
))
43 if (bb
->loop_father
!= loop
)
46 /* But this was not enough. We might have some irreducible loop here. */
47 if (bb
->flags
& BB_IRREDUCIBLE_LOOP
)
53 /* Structure representing edge of a graph. */
57 int src
, dest
; /* Source and destination. */
58 struct edge
*pred_next
, *succ_next
;
59 /* Next edge in predecessor and successor lists. */
60 void *data
; /* Data attached to the edge. */
63 /* Structure representing vertex of a graph. */
67 struct edge
*pred
, *succ
;
68 /* Lists of predecessors and successors. */
69 int component
; /* Number of dfs restarts before reaching the
71 int post
; /* Postorder number. */
74 /* Structure representing a graph. */
78 int n_vertices
; /* Number of vertices. */
79 struct vertex
*vertices
;
83 /* Dumps graph G into F. */
85 extern void dump_graph (FILE *, struct graph
*);
88 dump_graph (FILE *f
, struct graph
*g
)
93 for (i
= 0; i
< g
->n_vertices
; i
++)
95 if (!g
->vertices
[i
].pred
96 && !g
->vertices
[i
].succ
)
99 fprintf (f
, "%d (%d)\t<-", i
, g
->vertices
[i
].component
);
100 for (e
= g
->vertices
[i
].pred
; e
; e
= e
->pred_next
)
101 fprintf (f
, " %d", e
->src
);
105 for (e
= g
->vertices
[i
].succ
; e
; e
= e
->succ_next
)
106 fprintf (f
, " %d", e
->dest
);
111 /* Creates a new graph with N_VERTICES vertices. */
113 static struct graph
*
114 new_graph (int n_vertices
)
116 struct graph
*g
= XNEW (struct graph
);
118 g
->n_vertices
= n_vertices
;
119 g
->vertices
= XCNEWVEC (struct vertex
, n_vertices
);
124 /* Adds an edge from F to T to graph G, with DATA attached. */
127 add_edge (struct graph
*g
, int f
, int t
, void *data
)
129 struct edge
*e
= xmalloc (sizeof (struct edge
));
135 e
->pred_next
= g
->vertices
[t
].pred
;
136 g
->vertices
[t
].pred
= e
;
138 e
->succ_next
= g
->vertices
[f
].succ
;
139 g
->vertices
[f
].succ
= e
;
142 /* Runs dfs search over vertices of G, from NQ vertices in queue QS.
143 The vertices in postorder are stored into QT. If FORWARD is false,
144 backward dfs is run. */
147 dfs (struct graph
*g
, int *qs
, int nq
, int *qt
, bool forward
)
149 int i
, tick
= 0, v
, comp
= 0, top
;
151 struct edge
**stack
= xmalloc (sizeof (struct edge
*) * g
->n_vertices
);
153 for (i
= 0; i
< g
->n_vertices
; i
++)
155 g
->vertices
[i
].component
= -1;
156 g
->vertices
[i
].post
= -1;
159 #define FST_EDGE(V) (forward ? g->vertices[(V)].succ : g->vertices[(V)].pred)
160 #define NEXT_EDGE(E) (forward ? (E)->succ_next : (E)->pred_next)
161 #define EDGE_SRC(E) (forward ? (E)->src : (E)->dest)
162 #define EDGE_DEST(E) (forward ? (E)->dest : (E)->src)
164 for (i
= 0; i
< nq
; i
++)
167 if (g
->vertices
[v
].post
!= -1)
170 g
->vertices
[v
].component
= comp
++;
176 while (e
&& g
->vertices
[EDGE_DEST (e
)].component
!= -1)
183 g
->vertices
[v
].post
= tick
++;
197 g
->vertices
[v
].component
= comp
- 1;
204 /* Marks the edge E in graph G irreducible if it connects two vertices in the
208 check_irred (struct graph
*g
, struct edge
*e
)
212 /* All edges should lead from a component with higher number to the
213 one with lower one. */
214 gcc_assert (g
->vertices
[e
->src
].component
>= g
->vertices
[e
->dest
].component
);
216 if (g
->vertices
[e
->src
].component
!= g
->vertices
[e
->dest
].component
)
219 real
->flags
|= EDGE_IRREDUCIBLE_LOOP
;
220 if (flow_bb_inside_loop_p (real
->src
->loop_father
, real
->dest
))
221 real
->src
->flags
|= BB_IRREDUCIBLE_LOOP
;
224 /* Runs CALLBACK for all edges in G. */
227 for_each_edge (struct graph
*g
,
228 void (callback
) (struct graph
*, struct edge
*))
233 for (i
= 0; i
< g
->n_vertices
; i
++)
234 for (e
= g
->vertices
[i
].succ
; e
; e
= e
->succ_next
)
238 /* Releases the memory occupied by G. */
241 free_graph (struct graph
*g
)
246 for (i
= 0; i
< g
->n_vertices
; i
++)
247 for (e
= g
->vertices
[i
].succ
; e
; e
= n
)
256 /* Marks blocks and edges that are part of non-recognized loops; i.e. we
257 throw away all latch edges and mark blocks inside any remaining cycle.
258 Everything is a bit complicated due to fact we do not want to do this
259 for parts of cycles that only "pass" through some loop -- i.e. for
260 each cycle, we want to mark blocks that belong directly to innermost
261 loop containing the whole cycle.
263 LOOPS is the loop tree. */
265 #define LOOP_REPR(LOOP) ((LOOP)->num + last_basic_block)
266 #define BB_REPR(BB) ((BB)->index + 1)
269 mark_irreducible_loops (void)
276 int num
= number_of_loops ();
277 int *queue1
= XNEWVEC (int, last_basic_block
+ num
);
278 int *queue2
= XNEWVEC (int, last_basic_block
+ num
);
281 struct loop
*cloop
, *loop
;
284 gcc_assert (current_loops
!= NULL
);
286 /* Reset the flags. */
287 FOR_BB_BETWEEN (act
, ENTRY_BLOCK_PTR
, EXIT_BLOCK_PTR
, next_bb
)
289 act
->flags
&= ~BB_IRREDUCIBLE_LOOP
;
290 FOR_EACH_EDGE (e
, ei
, act
->succs
)
291 e
->flags
&= ~EDGE_IRREDUCIBLE_LOOP
;
294 /* Create the edge lists. */
295 g
= new_graph (last_basic_block
+ num
);
297 FOR_BB_BETWEEN (act
, ENTRY_BLOCK_PTR
, EXIT_BLOCK_PTR
, next_bb
)
298 FOR_EACH_EDGE (e
, ei
, act
->succs
)
300 /* Ignore edges to exit. */
301 if (e
->dest
== EXIT_BLOCK_PTR
)
305 dest
= BB_REPR (e
->dest
);
307 /* Ignore latch edges. */
308 if (e
->dest
->loop_father
->header
== e
->dest
309 && e
->dest
->loop_father
->latch
== act
)
312 /* Edges inside a single loop should be left where they are. Edges
313 to subloop headers should lead to representative of the subloop,
314 but from the same place.
316 Edges exiting loops should lead from representative
317 of the son of nearest common ancestor of the loops in that
320 if (e
->dest
->loop_father
->header
== e
->dest
)
321 dest
= LOOP_REPR (e
->dest
->loop_father
);
323 if (!flow_bb_inside_loop_p (act
->loop_father
, e
->dest
))
325 depth
= 1 + loop_depth (find_common_loop (act
->loop_father
,
326 e
->dest
->loop_father
));
327 if (depth
== loop_depth (act
->loop_father
))
328 cloop
= act
->loop_father
;
330 cloop
= VEC_index (loop_p
, act
->loop_father
->superloops
, depth
);
332 src
= LOOP_REPR (cloop
);
335 add_edge (g
, src
, dest
, e
);
338 /* Find the strongly connected components. Use the algorithm of Tarjan --
339 first determine the postorder dfs numbering in reversed graph, then
340 run the dfs on the original graph in the order given by decreasing
341 numbers assigned by the previous pass. */
343 FOR_BB_BETWEEN (act
, ENTRY_BLOCK_PTR
, EXIT_BLOCK_PTR
, next_bb
)
345 queue1
[nq
++] = BB_REPR (act
);
348 FOR_EACH_LOOP (li
, loop
, 0)
350 queue1
[nq
++] = LOOP_REPR (loop
);
352 dfs (g
, queue1
, nq
, queue2
, false);
353 for (i
= 0; i
< nq
; i
++)
354 queue1
[i
] = queue2
[nq
- i
- 1];
355 dfs (g
, queue1
, nq
, NULL
, true);
357 /* Mark the irreducible loops. */
358 for_each_edge (g
, check_irred
);
364 current_loops
->state
|= LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS
;
367 /* Counts number of insns inside LOOP. */
369 num_loop_insns (struct loop
*loop
)
371 basic_block
*bbs
, bb
;
372 unsigned i
, ninsns
= 0;
375 bbs
= get_loop_body (loop
);
376 for (i
= 0; i
< loop
->num_nodes
; i
++)
380 for (insn
= BB_HEAD (bb
); insn
!= BB_END (bb
); insn
= NEXT_INSN (insn
))
389 /* Counts number of insns executed on average per iteration LOOP. */
391 average_num_loop_insns (struct loop
*loop
)
393 basic_block
*bbs
, bb
;
394 unsigned i
, binsns
, ninsns
, ratio
;
398 bbs
= get_loop_body (loop
);
399 for (i
= 0; i
< loop
->num_nodes
; i
++)
404 for (insn
= BB_HEAD (bb
); insn
!= BB_END (bb
); insn
= NEXT_INSN (insn
))
408 ratio
= loop
->header
->frequency
== 0
410 : (bb
->frequency
* BB_FREQ_MAX
) / loop
->header
->frequency
;
411 ninsns
+= binsns
* ratio
;
415 ninsns
/= BB_FREQ_MAX
;
417 ninsns
= 1; /* To avoid division by zero. */
422 /* Returns expected number of iterations of LOOP, according to
423 measured or guessed profile. No bounding is done on the
427 expected_loop_iterations_unbounded (const struct loop
*loop
)
432 if (loop
->latch
->count
|| loop
->header
->count
)
434 gcov_type count_in
, count_latch
, expected
;
439 FOR_EACH_EDGE (e
, ei
, loop
->header
->preds
)
440 if (e
->src
== loop
->latch
)
441 count_latch
= e
->count
;
443 count_in
+= e
->count
;
446 expected
= count_latch
* 2;
448 expected
= (count_latch
+ count_in
- 1) / count_in
;
454 int freq_in
, freq_latch
;
459 FOR_EACH_EDGE (e
, ei
, loop
->header
->preds
)
460 if (e
->src
== loop
->latch
)
461 freq_latch
= EDGE_FREQUENCY (e
);
463 freq_in
+= EDGE_FREQUENCY (e
);
466 return freq_latch
* 2;
468 return (freq_latch
+ freq_in
- 1) / freq_in
;
472 /* Returns expected number of LOOP iterations. The returned value is bounded
473 by REG_BR_PROB_BASE. */
476 expected_loop_iterations (const struct loop
*loop
)
478 gcov_type expected
= expected_loop_iterations_unbounded (loop
);
479 return (expected
> REG_BR_PROB_BASE
? REG_BR_PROB_BASE
: expected
);
482 /* Returns the maximum level of nesting of subloops of LOOP. */
485 get_loop_level (const struct loop
*loop
)
487 const struct loop
*ploop
;
490 for (ploop
= loop
->inner
; ploop
; ploop
= ploop
->next
)
492 l
= get_loop_level (ploop
);
499 /* Returns estimate on cost of computing SEQ. */
507 for (; seq
; seq
= NEXT_INSN (seq
))
509 set
= single_set (seq
);
511 cost
+= rtx_cost (set
, SET
);
519 /* The properties of the target. */
521 unsigned target_avail_regs
; /* Number of available registers. */
522 unsigned target_res_regs
; /* Number of registers reserved for temporary
524 unsigned target_reg_cost
; /* The cost for register when there still
525 is some reserve, but we are approaching
526 the number of available registers. */
527 unsigned target_spill_cost
; /* The cost for register when we need
530 /* Initialize the constants for computing set costs. */
533 init_set_costs (void)
536 rtx reg1
= gen_raw_REG (SImode
, FIRST_PSEUDO_REGISTER
);
537 rtx reg2
= gen_raw_REG (SImode
, FIRST_PSEUDO_REGISTER
+ 1);
538 rtx addr
= gen_raw_REG (Pmode
, FIRST_PSEUDO_REGISTER
+ 2);
539 rtx mem
= validize_mem (gen_rtx_MEM (SImode
, addr
));
542 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
543 if (TEST_HARD_REG_BIT (reg_class_contents
[GENERAL_REGS
], i
)
549 /* Set up the costs for using extra registers:
551 1) If not many free registers remain, we should prefer having an
552 additional move to decreasing the number of available registers.
554 2) If no registers are available, we need to spill, which may require
555 storing the old value to memory and loading it back
556 (TARGET_SPILL_COST). */
559 emit_move_insn (reg1
, reg2
);
562 target_reg_cost
= seq_cost (seq
);
565 emit_move_insn (mem
, reg1
);
566 emit_move_insn (reg2
, mem
);
569 target_spill_cost
= seq_cost (seq
);
572 /* Estimates cost of increased register pressure caused by making N_NEW new
573 registers live around the loop. N_OLD is the number of registers live
577 estimate_reg_pressure_cost (unsigned n_new
, unsigned n_old
)
579 unsigned regs_needed
= n_new
+ n_old
;
581 /* If we have enough registers, we should use them and not restrict
582 the transformations unnecessarily. */
583 if (regs_needed
+ target_res_regs
<= target_avail_regs
)
586 /* If we are close to running out of registers, try to preserve them. */
587 if (regs_needed
<= target_avail_regs
)
588 return target_reg_cost
* n_new
;
590 /* If we run out of registers, it is very expensive to add another one. */
591 return target_spill_cost
* n_new
;
594 /* Sets EDGE_LOOP_EXIT flag for all loop exits. */
597 mark_loop_exit_edges (void)
602 if (number_of_loops () <= 1)
609 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
611 if (loop_outer (bb
->loop_father
)
612 && loop_exit_edge_p (bb
->loop_father
, e
))
613 e
->flags
|= EDGE_LOOP_EXIT
;
615 e
->flags
&= ~EDGE_LOOP_EXIT
;