1 /* Natural loop analysis code for GNU compiler.
2 Copyright (C) 2002, 2003, 2004 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, 59 Temple Place - Suite 330, Boston, MA
23 #include "coretypes.h"
26 #include "hard-reg-set.h"
27 #include "basic-block.h"
32 /* Checks whether BB is executed exactly once in each LOOP iteration. */
35 just_once_each_iteration_p (struct loop
*loop
, basic_block bb
)
37 /* It must be executed at least once each iteration. */
38 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, bb
))
42 if (bb
->loop_father
!= loop
)
45 /* But this was not enough. We might have some irreducible loop here. */
46 if (bb
->flags
& BB_IRREDUCIBLE_LOOP
)
52 /* Structure representing edge of a graph. */
56 int src
, dest
; /* Source and destination. */
57 struct edge
*pred_next
, *succ_next
;
58 /* Next edge in predecessor and successor lists. */
59 void *data
; /* Data attached to the edge. */
62 /* Structure representing vertex of a graph. */
66 struct edge
*pred
, *succ
;
67 /* Lists of predecessors and successors. */
68 int component
; /* Number of dfs restarts before reaching the
70 int post
; /* Postorder number. */
73 /* Structure representing a graph. */
77 int n_vertices
; /* Number of vertices. */
78 struct vertex
*vertices
;
82 /* Dumps graph G into F. */
84 extern void dump_graph (FILE *, struct graph
*);
85 void dump_graph (FILE *f
, struct graph
*g
)
90 for (i
= 0; i
< g
->n_vertices
; i
++)
92 if (!g
->vertices
[i
].pred
93 && !g
->vertices
[i
].succ
)
96 fprintf (f
, "%d (%d)\t<-", i
, g
->vertices
[i
].component
);
97 for (e
= g
->vertices
[i
].pred
; e
; e
= e
->pred_next
)
98 fprintf (f
, " %d", e
->src
);
102 for (e
= g
->vertices
[i
].succ
; e
; e
= e
->succ_next
)
103 fprintf (f
, " %d", e
->dest
);
108 /* Creates a new graph with N_VERTICES vertices. */
110 static struct graph
*
111 new_graph (int n_vertices
)
113 struct graph
*g
= xmalloc (sizeof (struct graph
));
115 g
->n_vertices
= n_vertices
;
116 g
->vertices
= xcalloc (n_vertices
, sizeof (struct vertex
));
121 /* Adds an edge from F to T to graph G, with DATA attached. */
124 add_edge (struct graph
*g
, int f
, int t
, void *data
)
126 struct edge
*e
= xmalloc (sizeof (struct edge
));
132 e
->pred_next
= g
->vertices
[t
].pred
;
133 g
->vertices
[t
].pred
= e
;
135 e
->succ_next
= g
->vertices
[f
].succ
;
136 g
->vertices
[f
].succ
= e
;
139 /* Runs dfs search over vertices of G, from NQ vertices in queue QS.
140 The vertices in postorder are stored into QT. If FORWARD is false,
141 backward dfs is run. */
144 dfs (struct graph
*g
, int *qs
, int nq
, int *qt
, bool forward
)
146 int i
, tick
= 0, v
, comp
= 0, top
;
148 struct edge
**stack
= xmalloc (sizeof (struct edge
*) * g
->n_vertices
);
150 for (i
= 0; i
< g
->n_vertices
; i
++)
152 g
->vertices
[i
].component
= -1;
153 g
->vertices
[i
].post
= -1;
156 #define FST_EDGE(V) (forward ? g->vertices[(V)].succ : g->vertices[(V)].pred)
157 #define NEXT_EDGE(E) (forward ? (E)->succ_next : (E)->pred_next)
158 #define EDGE_SRC(E) (forward ? (E)->src : (E)->dest)
159 #define EDGE_DEST(E) (forward ? (E)->dest : (E)->src)
161 for (i
= 0; i
< nq
; i
++)
164 if (g
->vertices
[v
].post
!= -1)
167 g
->vertices
[v
].component
= comp
++;
173 while (e
&& g
->vertices
[EDGE_DEST (e
)].component
!= -1)
180 g
->vertices
[v
].post
= tick
++;
194 g
->vertices
[v
].component
= comp
- 1;
201 /* Marks the edge E in graph G irreducible if it connects two vertices in the
205 check_irred (struct graph
*g
, struct edge
*e
)
209 /* All edges should lead from a component with higher number to the
210 one with lower one. */
211 gcc_assert (g
->vertices
[e
->src
].component
>= g
->vertices
[e
->dest
].component
);
213 if (g
->vertices
[e
->src
].component
!= g
->vertices
[e
->dest
].component
)
216 real
->flags
|= EDGE_IRREDUCIBLE_LOOP
;
217 if (flow_bb_inside_loop_p (real
->src
->loop_father
, real
->dest
))
218 real
->src
->flags
|= BB_IRREDUCIBLE_LOOP
;
221 /* Runs CALLBACK for all edges in G. */
224 for_each_edge (struct graph
*g
,
225 void (callback
) (struct graph
*, struct edge
*))
230 for (i
= 0; i
< g
->n_vertices
; i
++)
231 for (e
= g
->vertices
[i
].succ
; e
; e
= e
->succ_next
)
235 /* Releases the memory occupied by G. */
238 free_graph (struct graph
*g
)
243 for (i
= 0; i
< g
->n_vertices
; i
++)
244 for (e
= g
->vertices
[i
].succ
; e
; e
= n
)
253 /* Marks blocks and edges that are part of non-recognized loops; i.e. we
254 throw away all latch edges and mark blocks inside any remaining cycle.
255 Everything is a bit complicated due to fact we do not want to do this
256 for parts of cycles that only "pass" through some loop -- i.e. for
257 each cycle, we want to mark blocks that belong directly to innermost
258 loop containing the whole cycle.
260 LOOPS is the loop tree. */
262 #define LOOP_REPR(LOOP) ((LOOP)->num + last_basic_block)
263 #define BB_REPR(BB) ((BB)->index + 1)
266 mark_irreducible_loops (struct loops
*loops
)
272 int *queue1
= xmalloc ((last_basic_block
+ loops
->num
) * sizeof (int));
273 int *queue2
= xmalloc ((last_basic_block
+ loops
->num
) * sizeof (int));
277 /* Reset the flags. */
278 FOR_BB_BETWEEN (act
, ENTRY_BLOCK_PTR
, EXIT_BLOCK_PTR
, next_bb
)
280 act
->flags
&= ~BB_IRREDUCIBLE_LOOP
;
281 for (e
= act
->succ
; e
; e
= e
->succ_next
)
282 e
->flags
&= ~EDGE_IRREDUCIBLE_LOOP
;
285 /* Create the edge lists. */
286 g
= new_graph (last_basic_block
+ loops
->num
);
288 FOR_BB_BETWEEN (act
, ENTRY_BLOCK_PTR
, EXIT_BLOCK_PTR
, next_bb
)
289 for (e
= act
->succ
; e
; e
= e
->succ_next
)
291 /* Ignore edges to exit. */
292 if (e
->dest
== EXIT_BLOCK_PTR
)
295 /* And latch edges. */
296 if (e
->dest
->loop_father
->header
== e
->dest
297 && e
->dest
->loop_father
->latch
== act
)
300 /* Edges inside a single loop should be left where they are. Edges
301 to subloop headers should lead to representative of the subloop,
302 but from the same place.
304 Edges exiting loops should lead from representative
305 of the son of nearest common ancestor of the loops in that
309 dest
= BB_REPR (e
->dest
);
311 if (e
->dest
->loop_father
->header
== e
->dest
)
312 dest
= LOOP_REPR (e
->dest
->loop_father
);
314 if (!flow_bb_inside_loop_p (act
->loop_father
, e
->dest
))
316 depth
= find_common_loop (act
->loop_father
,
317 e
->dest
->loop_father
)->depth
+ 1;
318 if (depth
== act
->loop_father
->depth
)
319 cloop
= act
->loop_father
;
321 cloop
= act
->loop_father
->pred
[depth
];
323 src
= LOOP_REPR (cloop
);
326 add_edge (g
, src
, dest
, e
);
329 /* Find the strongly connected components. Use the algorithm of Tarjan --
330 first determine the postorder dfs numbering in reversed graph, then
331 run the dfs on the original graph in the order given by decreasing
332 numbers assigned by the previous pass. */
334 FOR_BB_BETWEEN (act
, ENTRY_BLOCK_PTR
, EXIT_BLOCK_PTR
, next_bb
)
336 queue1
[nq
++] = BB_REPR (act
);
338 for (i
= 1; i
< (int) loops
->num
; i
++)
339 if (loops
->parray
[i
])
340 queue1
[nq
++] = LOOP_REPR (loops
->parray
[i
]);
341 dfs (g
, queue1
, nq
, queue2
, false);
342 for (i
= 0; i
< nq
; i
++)
343 queue1
[i
] = queue2
[nq
- i
- 1];
344 dfs (g
, queue1
, nq
, NULL
, true);
346 /* Mark the irreducible loops. */
347 for_each_edge (g
, check_irred
);
353 loops
->state
|= LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS
;
356 /* Counts number of insns inside LOOP. */
358 num_loop_insns (struct loop
*loop
)
360 basic_block
*bbs
, bb
;
361 unsigned i
, ninsns
= 0;
364 bbs
= get_loop_body (loop
);
365 for (i
= 0; i
< loop
->num_nodes
; i
++)
369 for (insn
= BB_HEAD (bb
); insn
!= BB_END (bb
); insn
= NEXT_INSN (insn
))
378 /* Counts number of insns executed on average per iteration LOOP. */
380 average_num_loop_insns (struct loop
*loop
)
382 basic_block
*bbs
, bb
;
383 unsigned i
, binsns
, ninsns
, ratio
;
387 bbs
= get_loop_body (loop
);
388 for (i
= 0; i
< loop
->num_nodes
; i
++)
393 for (insn
= BB_HEAD (bb
); insn
!= BB_END (bb
); insn
= NEXT_INSN (insn
))
397 ratio
= loop
->header
->frequency
== 0
399 : (bb
->frequency
* BB_FREQ_MAX
) / loop
->header
->frequency
;
400 ninsns
+= binsns
* ratio
;
404 ninsns
/= BB_FREQ_MAX
;
406 ninsns
= 1; /* To avoid division by zero. */
411 /* Returns expected number of LOOP iterations.
412 Compute upper bound on number of iterations in case they do not fit integer
413 to help loop peeling heuristics. Use exact counts if at all possible. */
415 expected_loop_iterations (const struct loop
*loop
)
419 if (loop
->header
->count
)
421 gcov_type count_in
, count_latch
, expected
;
426 for (e
= loop
->header
->pred
; e
; e
= e
->pred_next
)
427 if (e
->src
== loop
->latch
)
428 count_latch
= e
->count
;
430 count_in
+= e
->count
;
433 expected
= count_latch
* 2;
435 expected
= (count_latch
+ count_in
- 1) / count_in
;
437 /* Avoid overflows. */
438 return (expected
> REG_BR_PROB_BASE
? REG_BR_PROB_BASE
: expected
);
442 int freq_in
, freq_latch
;
447 for (e
= loop
->header
->pred
; e
; e
= e
->pred_next
)
448 if (e
->src
== loop
->latch
)
449 freq_latch
= EDGE_FREQUENCY (e
);
451 freq_in
+= EDGE_FREQUENCY (e
);
454 return freq_latch
* 2;
456 return (freq_latch
+ freq_in
- 1) / freq_in
;
460 /* Returns the maximum level of nesting of subloops of LOOP. */
463 get_loop_level (const struct loop
*loop
)
465 const struct loop
*ploop
;
468 for (ploop
= loop
->inner
; ploop
; ploop
= ploop
->next
)
470 l
= get_loop_level (ploop
);
477 /* Returns estimate on cost of computing SEQ. */
485 for (; seq
; seq
= NEXT_INSN (seq
))
487 set
= single_set (seq
);
489 cost
+= rtx_cost (set
, SET
);
497 /* The properties of the target. */
499 unsigned target_avail_regs
; /* Number of available registers. */
500 unsigned target_res_regs
; /* Number of reserved registers. */
501 unsigned target_small_cost
; /* The cost for register when there is a free one. */
502 unsigned target_pres_cost
; /* The cost for register when there are not too many
504 unsigned target_spill_cost
; /* The cost for register when we need to spill. */
506 /* Initialize the constants for computing set costs. */
509 init_set_costs (void)
512 rtx reg1
= gen_raw_REG (SImode
, FIRST_PSEUDO_REGISTER
);
513 rtx reg2
= gen_raw_REG (SImode
, FIRST_PSEUDO_REGISTER
+ 1);
514 rtx addr
= gen_raw_REG (Pmode
, FIRST_PSEUDO_REGISTER
+ 2);
515 rtx mem
= validize_mem (gen_rtx_MEM (SImode
, addr
));
518 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
519 if (TEST_HARD_REG_BIT (reg_class_contents
[GENERAL_REGS
], i
)
525 /* These are really just heuristic values. */
528 emit_move_insn (reg1
, reg2
);
531 target_small_cost
= seq_cost (seq
);
532 target_pres_cost
= 2 * target_small_cost
;
535 emit_move_insn (mem
, reg1
);
536 emit_move_insn (reg2
, mem
);
539 target_spill_cost
= seq_cost (seq
);
542 /* Calculates cost for having SIZE new loop global variables. REGS_USED is the
543 number of global registers used in loop. N_USES is the number of relevant
547 global_cost_for_size (unsigned size
, unsigned regs_used
, unsigned n_uses
)
549 unsigned regs_needed
= regs_used
+ size
;
552 if (regs_needed
+ target_res_regs
<= target_avail_regs
)
553 cost
+= target_small_cost
* size
;
554 else if (regs_needed
<= target_avail_regs
)
555 cost
+= target_pres_cost
* size
;
558 cost
+= target_pres_cost
* size
;
559 cost
+= target_spill_cost
* n_uses
* (regs_needed
- target_avail_regs
) / regs_needed
;