1 /* Natural loop analysis code for GNU compiler.
2 Copyright (C) 2002, 2003, 2004, 2005 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"
28 #include "basic-block.h"
33 /* Checks whether BB is executed exactly once in each LOOP iteration. */
36 just_once_each_iteration_p (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
*);
86 void dump_graph (FILE *f
, struct graph
*g
)
91 for (i
= 0; i
< g
->n_vertices
; i
++)
93 if (!g
->vertices
[i
].pred
94 && !g
->vertices
[i
].succ
)
97 fprintf (f
, "%d (%d)\t<-", i
, g
->vertices
[i
].component
);
98 for (e
= g
->vertices
[i
].pred
; e
; e
= e
->pred_next
)
99 fprintf (f
, " %d", e
->src
);
103 for (e
= g
->vertices
[i
].succ
; e
; e
= e
->succ_next
)
104 fprintf (f
, " %d", e
->dest
);
109 /* Creates a new graph with N_VERTICES vertices. */
111 static struct graph
*
112 new_graph (int n_vertices
)
114 struct graph
*g
= xmalloc (sizeof (struct graph
));
116 g
->n_vertices
= n_vertices
;
117 g
->vertices
= xcalloc (n_vertices
, sizeof (struct vertex
));
122 /* Adds an edge from F to T to graph G, with DATA attached. */
125 add_edge (struct graph
*g
, int f
, int t
, void *data
)
127 struct edge
*e
= xmalloc (sizeof (struct edge
));
133 e
->pred_next
= g
->vertices
[t
].pred
;
134 g
->vertices
[t
].pred
= e
;
136 e
->succ_next
= g
->vertices
[f
].succ
;
137 g
->vertices
[f
].succ
= e
;
140 /* Runs dfs search over vertices of G, from NQ vertices in queue QS.
141 The vertices in postorder are stored into QT. If FORWARD is false,
142 backward dfs is run. */
145 dfs (struct graph
*g
, int *qs
, int nq
, int *qt
, bool forward
)
147 int i
, tick
= 0, v
, comp
= 0, top
;
149 struct edge
**stack
= xmalloc (sizeof (struct edge
*) * g
->n_vertices
);
151 for (i
= 0; i
< g
->n_vertices
; i
++)
153 g
->vertices
[i
].component
= -1;
154 g
->vertices
[i
].post
= -1;
157 #define FST_EDGE(V) (forward ? g->vertices[(V)].succ : g->vertices[(V)].pred)
158 #define NEXT_EDGE(E) (forward ? (E)->succ_next : (E)->pred_next)
159 #define EDGE_SRC(E) (forward ? (E)->src : (E)->dest)
160 #define EDGE_DEST(E) (forward ? (E)->dest : (E)->src)
162 for (i
= 0; i
< nq
; i
++)
165 if (g
->vertices
[v
].post
!= -1)
168 g
->vertices
[v
].component
= comp
++;
174 while (e
&& g
->vertices
[EDGE_DEST (e
)].component
!= -1)
181 g
->vertices
[v
].post
= tick
++;
195 g
->vertices
[v
].component
= comp
- 1;
202 /* Marks the edge E in graph G irreducible if it connects two vertices in the
206 check_irred (struct graph
*g
, struct edge
*e
)
210 /* All edges should lead from a component with higher number to the
211 one with lower one. */
212 gcc_assert (g
->vertices
[e
->src
].component
>= g
->vertices
[e
->dest
].component
);
214 if (g
->vertices
[e
->src
].component
!= g
->vertices
[e
->dest
].component
)
217 real
->flags
|= EDGE_IRREDUCIBLE_LOOP
;
218 if (flow_bb_inside_loop_p (real
->src
->loop_father
, real
->dest
))
219 real
->src
->flags
|= BB_IRREDUCIBLE_LOOP
;
222 /* Runs CALLBACK for all edges in G. */
225 for_each_edge (struct graph
*g
,
226 void (callback
) (struct graph
*, struct edge
*))
231 for (i
= 0; i
< g
->n_vertices
; i
++)
232 for (e
= g
->vertices
[i
].succ
; e
; e
= e
->succ_next
)
236 /* Releases the memory occupied by G. */
239 free_graph (struct graph
*g
)
244 for (i
= 0; i
< g
->n_vertices
; i
++)
245 for (e
= g
->vertices
[i
].succ
; e
; e
= n
)
254 /* Marks blocks and edges that are part of non-recognized loops; i.e. we
255 throw away all latch edges and mark blocks inside any remaining cycle.
256 Everything is a bit complicated due to fact we do not want to do this
257 for parts of cycles that only "pass" through some loop -- i.e. for
258 each cycle, we want to mark blocks that belong directly to innermost
259 loop containing the whole cycle.
261 LOOPS is the loop tree. */
263 #define LOOP_REPR(LOOP) ((LOOP)->num + last_basic_block)
264 #define BB_REPR(BB) ((BB)->index + 1)
267 mark_irreducible_loops (struct loops
*loops
)
274 int *queue1
= xmalloc ((last_basic_block
+ loops
->num
) * sizeof (int));
275 int *queue2
= xmalloc ((last_basic_block
+ loops
->num
) * sizeof (int));
279 /* Reset the flags. */
280 FOR_BB_BETWEEN (act
, ENTRY_BLOCK_PTR
, EXIT_BLOCK_PTR
, next_bb
)
282 act
->flags
&= ~BB_IRREDUCIBLE_LOOP
;
283 FOR_EACH_EDGE (e
, ei
, act
->succs
)
284 e
->flags
&= ~EDGE_IRREDUCIBLE_LOOP
;
287 /* Create the edge lists. */
288 g
= new_graph (last_basic_block
+ loops
->num
);
290 FOR_BB_BETWEEN (act
, ENTRY_BLOCK_PTR
, EXIT_BLOCK_PTR
, next_bb
)
291 FOR_EACH_EDGE (e
, ei
, act
->succs
)
293 /* Ignore edges to exit. */
294 if (e
->dest
== EXIT_BLOCK_PTR
)
297 /* And latch edges. */
298 if (e
->dest
->loop_father
->header
== e
->dest
299 && e
->dest
->loop_father
->latch
== act
)
302 /* Edges inside a single loop should be left where they are. Edges
303 to subloop headers should lead to representative of the subloop,
304 but from the same place.
306 Edges exiting loops should lead from representative
307 of the son of nearest common ancestor of the loops in that
311 dest
= BB_REPR (e
->dest
);
313 if (e
->dest
->loop_father
->header
== e
->dest
)
314 dest
= LOOP_REPR (e
->dest
->loop_father
);
316 if (!flow_bb_inside_loop_p (act
->loop_father
, e
->dest
))
318 depth
= find_common_loop (act
->loop_father
,
319 e
->dest
->loop_father
)->depth
+ 1;
320 if (depth
== act
->loop_father
->depth
)
321 cloop
= act
->loop_father
;
323 cloop
= act
->loop_father
->pred
[depth
];
325 src
= LOOP_REPR (cloop
);
328 add_edge (g
, src
, dest
, e
);
331 /* Find the strongly connected components. Use the algorithm of Tarjan --
332 first determine the postorder dfs numbering in reversed graph, then
333 run the dfs on the original graph in the order given by decreasing
334 numbers assigned by the previous pass. */
336 FOR_BB_BETWEEN (act
, ENTRY_BLOCK_PTR
, EXIT_BLOCK_PTR
, next_bb
)
338 queue1
[nq
++] = BB_REPR (act
);
340 for (i
= 1; i
< (int) loops
->num
; i
++)
341 if (loops
->parray
[i
])
342 queue1
[nq
++] = LOOP_REPR (loops
->parray
[i
]);
343 dfs (g
, queue1
, nq
, queue2
, false);
344 for (i
= 0; i
< nq
; i
++)
345 queue1
[i
] = queue2
[nq
- i
- 1];
346 dfs (g
, queue1
, nq
, NULL
, true);
348 /* Mark the irreducible loops. */
349 for_each_edge (g
, check_irred
);
355 loops
->state
|= LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS
;
358 /* Counts number of insns inside LOOP. */
360 num_loop_insns (struct loop
*loop
)
362 basic_block
*bbs
, bb
;
363 unsigned i
, ninsns
= 0;
366 bbs
= get_loop_body (loop
);
367 for (i
= 0; i
< loop
->num_nodes
; i
++)
371 for (insn
= BB_HEAD (bb
); insn
!= BB_END (bb
); insn
= NEXT_INSN (insn
))
380 /* Counts number of insns executed on average per iteration LOOP. */
382 average_num_loop_insns (struct loop
*loop
)
384 basic_block
*bbs
, bb
;
385 unsigned i
, binsns
, ninsns
, ratio
;
389 bbs
= get_loop_body (loop
);
390 for (i
= 0; i
< loop
->num_nodes
; i
++)
395 for (insn
= BB_HEAD (bb
); insn
!= BB_END (bb
); insn
= NEXT_INSN (insn
))
399 ratio
= loop
->header
->frequency
== 0
401 : (bb
->frequency
* BB_FREQ_MAX
) / loop
->header
->frequency
;
402 ninsns
+= binsns
* ratio
;
406 ninsns
/= BB_FREQ_MAX
;
408 ninsns
= 1; /* To avoid division by zero. */
413 /* Returns expected number of LOOP iterations.
414 Compute upper bound on number of iterations in case they do not fit integer
415 to help loop peeling heuristics. Use exact counts if at all possible. */
417 expected_loop_iterations (const struct loop
*loop
)
422 if (loop
->header
->count
)
424 gcov_type count_in
, count_latch
, expected
;
429 FOR_EACH_EDGE (e
, ei
, loop
->header
->preds
)
430 if (e
->src
== loop
->latch
)
431 count_latch
= e
->count
;
433 count_in
+= e
->count
;
436 expected
= count_latch
* 2;
438 expected
= (count_latch
+ count_in
- 1) / count_in
;
440 /* Avoid overflows. */
441 return (expected
> REG_BR_PROB_BASE
? REG_BR_PROB_BASE
: expected
);
445 int freq_in
, freq_latch
;
450 FOR_EACH_EDGE (e
, ei
, loop
->header
->preds
)
451 if (e
->src
== loop
->latch
)
452 freq_latch
= EDGE_FREQUENCY (e
);
454 freq_in
+= EDGE_FREQUENCY (e
);
457 return freq_latch
* 2;
459 return (freq_latch
+ freq_in
- 1) / freq_in
;
463 /* Returns the maximum level of nesting of subloops of LOOP. */
466 get_loop_level (const struct loop
*loop
)
468 const struct loop
*ploop
;
471 for (ploop
= loop
->inner
; ploop
; ploop
= ploop
->next
)
473 l
= get_loop_level (ploop
);
480 /* Returns estimate on cost of computing SEQ. */
488 for (; seq
; seq
= NEXT_INSN (seq
))
490 set
= single_set (seq
);
492 cost
+= rtx_cost (set
, SET
);
500 /* The properties of the target. */
502 unsigned target_avail_regs
; /* Number of available registers. */
503 unsigned target_res_regs
; /* Number of reserved registers. */
504 unsigned target_small_cost
; /* The cost for register when there is a free one. */
505 unsigned target_pres_cost
; /* The cost for register when there are not too many
507 unsigned target_spill_cost
; /* The cost for register when we need to spill. */
509 /* Initialize the constants for computing set costs. */
512 init_set_costs (void)
515 rtx reg1
= gen_raw_REG (SImode
, FIRST_PSEUDO_REGISTER
);
516 rtx reg2
= gen_raw_REG (SImode
, FIRST_PSEUDO_REGISTER
+ 1);
517 rtx addr
= gen_raw_REG (Pmode
, FIRST_PSEUDO_REGISTER
+ 2);
518 rtx mem
= validize_mem (gen_rtx_MEM (SImode
, addr
));
521 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
522 if (TEST_HARD_REG_BIT (reg_class_contents
[GENERAL_REGS
], i
)
528 /* These are really just heuristic values. */
531 emit_move_insn (reg1
, reg2
);
534 target_small_cost
= seq_cost (seq
);
535 target_pres_cost
= 2 * target_small_cost
;
538 emit_move_insn (mem
, reg1
);
539 emit_move_insn (reg2
, mem
);
542 target_spill_cost
= seq_cost (seq
);
545 /* Calculates cost for having SIZE new loop global variables. REGS_USED is the
546 number of global registers used in loop. N_USES is the number of relevant
550 global_cost_for_size (unsigned size
, unsigned regs_used
, unsigned n_uses
)
552 unsigned regs_needed
= regs_used
+ size
;
555 if (regs_needed
+ target_res_regs
<= target_avail_regs
)
556 cost
+= target_small_cost
* size
;
557 else if (regs_needed
<= target_avail_regs
)
558 cost
+= target_pres_cost
* size
;
561 cost
+= target_pres_cost
* size
;
562 cost
+= target_spill_cost
* n_uses
* (regs_needed
- target_avail_regs
) / regs_needed
;
568 /* Sets EDGE_LOOP_EXIT flag for all exits of LOOPS. */
571 mark_loop_exit_edges (struct loops
*loops
)
583 /* Do not mark exits from the fake outermost loop. */
584 if (!bb
->loop_father
->outer
)
587 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
589 if (loop_exit_edge_p (bb
->loop_father
, e
))
590 e
->flags
|= EDGE_LOOP_EXIT
;
592 e
->flags
&= ~EDGE_LOOP_EXIT
;