Makefile.am: Add install-pdf target as copied from automake v1.10 rules.
[official-gcc.git] / gcc / cfgloopanal.c
blob5a9189787eae1727a0eac86b7e49dc5a23cdeda0
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
9 version.
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
14 for more details.
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
19 02110-1301, USA. */
21 #include "config.h"
22 #include "system.h"
23 #include "coretypes.h"
24 #include "tm.h"
25 #include "rtl.h"
26 #include "hard-reg-set.h"
27 #include "obstack.h"
28 #include "basic-block.h"
29 #include "cfgloop.h"
30 #include "expr.h"
31 #include "output.h"
33 /* Checks whether BB is executed exactly once in each LOOP iteration. */
35 bool
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))
40 return false;
42 /* And just once. */
43 if (bb->loop_father != loop)
44 return false;
46 /* But this was not enough. We might have some irreducible loop here. */
47 if (bb->flags & BB_IRREDUCIBLE_LOOP)
48 return false;
50 return true;
53 /* Structure representing edge of a graph. */
55 struct edge
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. */
65 struct vertex
67 struct edge *pred, *succ;
68 /* Lists of predecessors and successors. */
69 int component; /* Number of dfs restarts before reaching the
70 vertex. */
71 int post; /* Postorder number. */
74 /* Structure representing a graph. */
76 struct graph
78 int n_vertices; /* Number of vertices. */
79 struct vertex *vertices;
80 /* The vertices. */
83 /* Dumps graph G into F. */
85 extern void dump_graph (FILE *, struct graph *);
87 void
88 dump_graph (FILE *f, struct graph *g)
90 int i;
91 struct edge *e;
93 for (i = 0; i < g->n_vertices; i++)
95 if (!g->vertices[i].pred
96 && !g->vertices[i].succ)
97 continue;
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);
102 fprintf (f, "\n");
104 fprintf (f, "\t->");
105 for (e = g->vertices[i].succ; e; e = e->succ_next)
106 fprintf (f, " %d", e->dest);
107 fprintf (f, "\n");
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);
121 return g;
124 /* Adds an edge from F to T to graph G, with DATA attached. */
126 static void
127 add_edge (struct graph *g, int f, int t, void *data)
129 struct edge *e = xmalloc (sizeof (struct edge));
131 e->src = f;
132 e->dest = t;
133 e->data = data;
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. */
146 static void
147 dfs (struct graph *g, int *qs, int nq, int *qt, bool forward)
149 int i, tick = 0, v, comp = 0, top;
150 struct edge *e;
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++)
166 v = qs[i];
167 if (g->vertices[v].post != -1)
168 continue;
170 g->vertices[v].component = comp++;
171 e = FST_EDGE (v);
172 top = 0;
174 while (1)
176 while (e && g->vertices[EDGE_DEST (e)].component != -1)
177 e = NEXT_EDGE (e);
179 if (!e)
181 if (qt)
182 qt[tick] = v;
183 g->vertices[v].post = tick++;
185 if (!top)
186 break;
188 e = stack[--top];
189 v = EDGE_SRC (e);
190 e = NEXT_EDGE (e);
191 continue;
194 stack[top++] = e;
195 v = EDGE_DEST (e);
196 e = FST_EDGE (v);
197 g->vertices[v].component = comp - 1;
201 free (stack);
204 /* Marks the edge E in graph G irreducible if it connects two vertices in the
205 same scc. */
207 static void
208 check_irred (struct graph *g, struct edge *e)
210 edge real = e->data;
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)
217 return;
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. */
226 static void
227 for_each_edge (struct graph *g,
228 void (callback) (struct graph *, struct edge *))
230 struct edge *e;
231 int i;
233 for (i = 0; i < g->n_vertices; i++)
234 for (e = g->vertices[i].succ; e; e = e->succ_next)
235 callback (g, e);
238 /* Releases the memory occupied by G. */
240 static void
241 free_graph (struct graph *g)
243 struct edge *e, *n;
244 int i;
246 for (i = 0; i < g->n_vertices; i++)
247 for (e = g->vertices[i].succ; e; e = n)
249 n = e->succ_next;
250 free (e);
252 free (g->vertices);
253 free (g);
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)
268 void
269 mark_irreducible_loops (void)
271 basic_block act;
272 edge e;
273 edge_iterator ei;
274 int i, src, dest;
275 struct graph *g;
276 int num = current_loops ? number_of_loops () : 1;
277 int *queue1 = XNEWVEC (int, last_basic_block + num);
278 int *queue2 = XNEWVEC (int, last_basic_block + num);
279 int nq, depth;
280 struct loop *cloop, *loop;
281 loop_iterator li;
283 /* Reset the flags. */
284 FOR_BB_BETWEEN (act, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
286 act->flags &= ~BB_IRREDUCIBLE_LOOP;
287 FOR_EACH_EDGE (e, ei, act->succs)
288 e->flags &= ~EDGE_IRREDUCIBLE_LOOP;
291 /* Create the edge lists. */
292 g = new_graph (last_basic_block + num);
294 FOR_BB_BETWEEN (act, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
295 FOR_EACH_EDGE (e, ei, act->succs)
297 /* Ignore edges to exit. */
298 if (e->dest == EXIT_BLOCK_PTR)
299 continue;
301 src = BB_REPR (act);
302 dest = BB_REPR (e->dest);
304 if (current_loops)
306 /* Ignore latch edges. */
307 if (e->dest->loop_father->header == e->dest
308 && e->dest->loop_father->latch == act)
309 continue;
311 /* Edges inside a single loop should be left where they are. Edges
312 to subloop headers should lead to representative of the subloop,
313 but from the same place.
315 Edges exiting loops should lead from representative
316 of the son of nearest common ancestor of the loops in that
317 act lays. */
319 if (e->dest->loop_father->header == e->dest)
320 dest = LOOP_REPR (e->dest->loop_father);
322 if (!flow_bb_inside_loop_p (act->loop_father, e->dest))
324 depth = find_common_loop (act->loop_father,
325 e->dest->loop_father)->depth + 1;
326 if (depth == act->loop_father->depth)
327 cloop = act->loop_father;
328 else
329 cloop = act->loop_father->pred[depth];
331 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. */
342 nq = 0;
343 FOR_BB_BETWEEN (act, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
345 queue1[nq++] = BB_REPR (act);
348 if (current_loops)
350 FOR_EACH_LOOP (li, loop, 0)
352 queue1[nq++] = LOOP_REPR (loop);
355 dfs (g, queue1, nq, queue2, false);
356 for (i = 0; i < nq; i++)
357 queue1[i] = queue2[nq - i - 1];
358 dfs (g, queue1, nq, NULL, true);
360 /* Mark the irreducible loops. */
361 for_each_edge (g, check_irred);
363 free_graph (g);
364 free (queue1);
365 free (queue2);
367 if (current_loops)
368 current_loops->state |= LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS;
371 /* Counts number of insns inside LOOP. */
373 num_loop_insns (struct loop *loop)
375 basic_block *bbs, bb;
376 unsigned i, ninsns = 0;
377 rtx insn;
379 bbs = get_loop_body (loop);
380 for (i = 0; i < loop->num_nodes; i++)
382 bb = bbs[i];
383 ninsns++;
384 for (insn = BB_HEAD (bb); insn != BB_END (bb); insn = NEXT_INSN (insn))
385 if (INSN_P (insn))
386 ninsns++;
388 free(bbs);
390 return ninsns;
393 /* Counts number of insns executed on average per iteration LOOP. */
395 average_num_loop_insns (struct loop *loop)
397 basic_block *bbs, bb;
398 unsigned i, binsns, ninsns, ratio;
399 rtx insn;
401 ninsns = 0;
402 bbs = get_loop_body (loop);
403 for (i = 0; i < loop->num_nodes; i++)
405 bb = bbs[i];
407 binsns = 1;
408 for (insn = BB_HEAD (bb); insn != BB_END (bb); insn = NEXT_INSN (insn))
409 if (INSN_P (insn))
410 binsns++;
412 ratio = loop->header->frequency == 0
413 ? BB_FREQ_MAX
414 : (bb->frequency * BB_FREQ_MAX) / loop->header->frequency;
415 ninsns += binsns * ratio;
417 free(bbs);
419 ninsns /= BB_FREQ_MAX;
420 if (!ninsns)
421 ninsns = 1; /* To avoid division by zero. */
423 return ninsns;
426 /* Returns expected number of LOOP iterations.
427 Compute upper bound on number of iterations in case they do not fit integer
428 to help loop peeling heuristics. Use exact counts if at all possible. */
429 unsigned
430 expected_loop_iterations (const struct loop *loop)
432 edge e;
433 edge_iterator ei;
435 if (loop->latch->count || loop->header->count)
437 gcov_type count_in, count_latch, expected;
439 count_in = 0;
440 count_latch = 0;
442 FOR_EACH_EDGE (e, ei, loop->header->preds)
443 if (e->src == loop->latch)
444 count_latch = e->count;
445 else
446 count_in += e->count;
448 if (count_in == 0)
449 expected = count_latch * 2;
450 else
451 expected = (count_latch + count_in - 1) / count_in;
453 /* Avoid overflows. */
454 return (expected > REG_BR_PROB_BASE ? REG_BR_PROB_BASE : expected);
456 else
458 int freq_in, freq_latch;
460 freq_in = 0;
461 freq_latch = 0;
463 FOR_EACH_EDGE (e, ei, loop->header->preds)
464 if (e->src == loop->latch)
465 freq_latch = EDGE_FREQUENCY (e);
466 else
467 freq_in += EDGE_FREQUENCY (e);
469 if (freq_in == 0)
470 return freq_latch * 2;
472 return (freq_latch + freq_in - 1) / freq_in;
476 /* Returns the maximum level of nesting of subloops of LOOP. */
478 unsigned
479 get_loop_level (const struct loop *loop)
481 const struct loop *ploop;
482 unsigned mx = 0, l;
484 for (ploop = loop->inner; ploop; ploop = ploop->next)
486 l = get_loop_level (ploop);
487 if (l >= mx)
488 mx = l + 1;
490 return mx;
493 /* Returns estimate on cost of computing SEQ. */
495 static unsigned
496 seq_cost (rtx seq)
498 unsigned cost = 0;
499 rtx set;
501 for (; seq; seq = NEXT_INSN (seq))
503 set = single_set (seq);
504 if (set)
505 cost += rtx_cost (set, SET);
506 else
507 cost++;
510 return cost;
513 /* The properties of the target. */
515 unsigned target_avail_regs; /* Number of available registers. */
516 unsigned target_res_regs; /* Number of reserved registers. */
517 unsigned target_small_cost; /* The cost for register when there is a free one. */
518 unsigned target_pres_cost; /* The cost for register when there are not too many
519 free ones. */
520 unsigned target_spill_cost; /* The cost for register when we need to spill. */
522 /* Initialize the constants for computing set costs. */
524 void
525 init_set_costs (void)
527 rtx seq;
528 rtx reg1 = gen_raw_REG (SImode, FIRST_PSEUDO_REGISTER);
529 rtx reg2 = gen_raw_REG (SImode, FIRST_PSEUDO_REGISTER + 1);
530 rtx addr = gen_raw_REG (Pmode, FIRST_PSEUDO_REGISTER + 2);
531 rtx mem = validize_mem (gen_rtx_MEM (SImode, addr));
532 unsigned i;
534 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
535 if (TEST_HARD_REG_BIT (reg_class_contents[GENERAL_REGS], i)
536 && !fixed_regs[i])
537 target_avail_regs++;
539 target_res_regs = 3;
541 /* These are really just heuristic values. */
543 start_sequence ();
544 emit_move_insn (reg1, reg2);
545 seq = get_insns ();
546 end_sequence ();
547 target_small_cost = seq_cost (seq);
548 target_pres_cost = 2 * target_small_cost;
550 start_sequence ();
551 emit_move_insn (mem, reg1);
552 emit_move_insn (reg2, mem);
553 seq = get_insns ();
554 end_sequence ();
555 target_spill_cost = seq_cost (seq);
558 /* Calculates cost for having SIZE new loop global variables. REGS_USED is the
559 number of global registers used in loop. N_USES is the number of relevant
560 variable uses. */
562 unsigned
563 global_cost_for_size (unsigned size, unsigned regs_used, unsigned n_uses)
565 unsigned regs_needed = regs_used + size;
566 unsigned cost = 0;
568 if (regs_needed + target_res_regs <= target_avail_regs)
569 cost += target_small_cost * size;
570 else if (regs_needed <= target_avail_regs)
571 cost += target_pres_cost * size;
572 else
574 cost += target_pres_cost * size;
575 cost += target_spill_cost * n_uses * (regs_needed - target_avail_regs) / regs_needed;
578 return cost;
581 /* Sets EDGE_LOOP_EXIT flag for all loop exits. */
583 void
584 mark_loop_exit_edges (void)
586 basic_block bb;
587 edge e;
589 if (!current_loops)
590 return;
592 FOR_EACH_BB (bb)
594 edge_iterator ei;
596 FOR_EACH_EDGE (e, ei, bb->succs)
598 if (bb->loop_father->outer
599 && loop_exit_edge_p (bb->loop_father, e))
600 e->flags |= EDGE_LOOP_EXIT;
601 else
602 e->flags &= ~EDGE_LOOP_EXIT;