2008-05-15 Richard Guenther <rguenther@suse.de>
[official-gcc.git] / gcc / cfgloopanal.c
blobc00d1c501be93703e362ac52a3a976904158992a
1 /* Natural loop analysis code for GNU compiler.
2 Copyright (C) 2002, 2003, 2004, 2005, 2006, 2007 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 3, 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 COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
20 #include "config.h"
21 #include "system.h"
22 #include "coretypes.h"
23 #include "tm.h"
24 #include "rtl.h"
25 #include "hard-reg-set.h"
26 #include "obstack.h"
27 #include "basic-block.h"
28 #include "cfgloop.h"
29 #include "expr.h"
30 #include "output.h"
31 #include "graphds.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, const_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 /* Marks the edge E in graph G irreducible if it connects two vertices in the
54 same scc. */
56 static void
57 check_irred (struct graph *g, struct graph_edge *e)
59 edge real = (edge) e->data;
61 /* All edges should lead from a component with higher number to the
62 one with lower one. */
63 gcc_assert (g->vertices[e->src].component >= g->vertices[e->dest].component);
65 if (g->vertices[e->src].component != g->vertices[e->dest].component)
66 return;
68 real->flags |= EDGE_IRREDUCIBLE_LOOP;
69 if (flow_bb_inside_loop_p (real->src->loop_father, real->dest))
70 real->src->flags |= BB_IRREDUCIBLE_LOOP;
73 /* Marks blocks and edges that are part of non-recognized loops; i.e. we
74 throw away all latch edges and mark blocks inside any remaining cycle.
75 Everything is a bit complicated due to fact we do not want to do this
76 for parts of cycles that only "pass" through some loop -- i.e. for
77 each cycle, we want to mark blocks that belong directly to innermost
78 loop containing the whole cycle.
80 LOOPS is the loop tree. */
82 #define LOOP_REPR(LOOP) ((LOOP)->num + last_basic_block)
83 #define BB_REPR(BB) ((BB)->index + 1)
85 void
86 mark_irreducible_loops (void)
88 basic_block act;
89 edge e;
90 edge_iterator ei;
91 int src, dest;
92 unsigned depth;
93 struct graph *g;
94 int num = number_of_loops ();
95 struct loop *cloop;
97 gcc_assert (current_loops != NULL);
99 /* Reset the flags. */
100 FOR_BB_BETWEEN (act, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
102 act->flags &= ~BB_IRREDUCIBLE_LOOP;
103 FOR_EACH_EDGE (e, ei, act->succs)
104 e->flags &= ~EDGE_IRREDUCIBLE_LOOP;
107 /* Create the edge lists. */
108 g = new_graph (last_basic_block + num);
110 FOR_BB_BETWEEN (act, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
111 FOR_EACH_EDGE (e, ei, act->succs)
113 /* Ignore edges to exit. */
114 if (e->dest == EXIT_BLOCK_PTR)
115 continue;
117 src = BB_REPR (act);
118 dest = BB_REPR (e->dest);
120 /* Ignore latch edges. */
121 if (e->dest->loop_father->header == e->dest
122 && e->dest->loop_father->latch == act)
123 continue;
125 /* Edges inside a single loop should be left where they are. Edges
126 to subloop headers should lead to representative of the subloop,
127 but from the same place.
129 Edges exiting loops should lead from representative
130 of the son of nearest common ancestor of the loops in that
131 act lays. */
133 if (e->dest->loop_father->header == e->dest)
134 dest = LOOP_REPR (e->dest->loop_father);
136 if (!flow_bb_inside_loop_p (act->loop_father, e->dest))
138 depth = 1 + loop_depth (find_common_loop (act->loop_father,
139 e->dest->loop_father));
140 if (depth == loop_depth (act->loop_father))
141 cloop = act->loop_father;
142 else
143 cloop = VEC_index (loop_p, act->loop_father->superloops, depth);
145 src = LOOP_REPR (cloop);
148 add_edge (g, src, dest)->data = e;
151 /* Find the strongly connected components. */
152 graphds_scc (g, NULL);
154 /* Mark the irreducible loops. */
155 for_each_edge (g, check_irred);
157 free_graph (g);
159 loops_state_set (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS);
162 /* Counts number of insns inside LOOP. */
164 num_loop_insns (const struct loop *loop)
166 basic_block *bbs, bb;
167 unsigned i, ninsns = 0;
168 rtx insn;
170 bbs = get_loop_body (loop);
171 for (i = 0; i < loop->num_nodes; i++)
173 bb = bbs[i];
174 ninsns++;
175 for (insn = BB_HEAD (bb); insn != BB_END (bb); insn = NEXT_INSN (insn))
176 if (INSN_P (insn))
177 ninsns++;
179 free(bbs);
181 return ninsns;
184 /* Counts number of insns executed on average per iteration LOOP. */
186 average_num_loop_insns (const struct loop *loop)
188 basic_block *bbs, bb;
189 unsigned i, binsns, ninsns, ratio;
190 rtx insn;
192 ninsns = 0;
193 bbs = get_loop_body (loop);
194 for (i = 0; i < loop->num_nodes; i++)
196 bb = bbs[i];
198 binsns = 1;
199 for (insn = BB_HEAD (bb); insn != BB_END (bb); insn = NEXT_INSN (insn))
200 if (INSN_P (insn))
201 binsns++;
203 ratio = loop->header->frequency == 0
204 ? BB_FREQ_MAX
205 : (bb->frequency * BB_FREQ_MAX) / loop->header->frequency;
206 ninsns += binsns * ratio;
208 free(bbs);
210 ninsns /= BB_FREQ_MAX;
211 if (!ninsns)
212 ninsns = 1; /* To avoid division by zero. */
214 return ninsns;
217 /* Returns expected number of iterations of LOOP, according to
218 measured or guessed profile. No bounding is done on the
219 value. */
221 gcov_type
222 expected_loop_iterations_unbounded (const struct loop *loop)
224 edge e;
225 edge_iterator ei;
227 if (loop->latch->count || loop->header->count)
229 gcov_type count_in, count_latch, expected;
231 count_in = 0;
232 count_latch = 0;
234 FOR_EACH_EDGE (e, ei, loop->header->preds)
235 if (e->src == loop->latch)
236 count_latch = e->count;
237 else
238 count_in += e->count;
240 if (count_in == 0)
241 expected = count_latch * 2;
242 else
243 expected = (count_latch + count_in - 1) / count_in;
245 return expected;
247 else
249 int freq_in, freq_latch;
251 freq_in = 0;
252 freq_latch = 0;
254 FOR_EACH_EDGE (e, ei, loop->header->preds)
255 if (e->src == loop->latch)
256 freq_latch = EDGE_FREQUENCY (e);
257 else
258 freq_in += EDGE_FREQUENCY (e);
260 if (freq_in == 0)
261 return freq_latch * 2;
263 return (freq_latch + freq_in - 1) / freq_in;
267 /* Returns expected number of LOOP iterations. The returned value is bounded
268 by REG_BR_PROB_BASE. */
270 unsigned
271 expected_loop_iterations (const struct loop *loop)
273 gcov_type expected = expected_loop_iterations_unbounded (loop);
274 return (expected > REG_BR_PROB_BASE ? REG_BR_PROB_BASE : expected);
277 /* Returns the maximum level of nesting of subloops of LOOP. */
279 unsigned
280 get_loop_level (const struct loop *loop)
282 const struct loop *ploop;
283 unsigned mx = 0, l;
285 for (ploop = loop->inner; ploop; ploop = ploop->next)
287 l = get_loop_level (ploop);
288 if (l >= mx)
289 mx = l + 1;
291 return mx;
294 /* Returns estimate on cost of computing SEQ. */
296 static unsigned
297 seq_cost (const_rtx seq)
299 unsigned cost = 0;
300 rtx set;
302 for (; seq; seq = NEXT_INSN (seq))
304 set = single_set (seq);
305 if (set)
306 cost += rtx_cost (set, SET);
307 else
308 cost++;
311 return cost;
314 /* The properties of the target. */
316 unsigned target_avail_regs; /* Number of available registers. */
317 unsigned target_res_regs; /* Number of registers reserved for temporary
318 expressions. */
319 unsigned target_reg_cost; /* The cost for register when there still
320 is some reserve, but we are approaching
321 the number of available registers. */
322 unsigned target_spill_cost; /* The cost for register when we need
323 to spill. */
325 /* Initialize the constants for computing set costs. */
327 void
328 init_set_costs (void)
330 rtx seq;
331 rtx reg1 = gen_raw_REG (SImode, FIRST_PSEUDO_REGISTER);
332 rtx reg2 = gen_raw_REG (SImode, FIRST_PSEUDO_REGISTER + 1);
333 rtx addr = gen_raw_REG (Pmode, FIRST_PSEUDO_REGISTER + 2);
334 rtx mem = validize_mem (gen_rtx_MEM (SImode, addr));
335 unsigned i;
337 target_avail_regs = 0;
338 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
339 if (TEST_HARD_REG_BIT (reg_class_contents[GENERAL_REGS], i)
340 && !fixed_regs[i])
341 target_avail_regs++;
343 target_res_regs = 3;
345 /* Set up the costs for using extra registers:
347 1) If not many free registers remain, we should prefer having an
348 additional move to decreasing the number of available registers.
349 (TARGET_REG_COST).
350 2) If no registers are available, we need to spill, which may require
351 storing the old value to memory and loading it back
352 (TARGET_SPILL_COST). */
354 start_sequence ();
355 emit_move_insn (reg1, reg2);
356 seq = get_insns ();
357 end_sequence ();
358 target_reg_cost = seq_cost (seq);
360 start_sequence ();
361 emit_move_insn (mem, reg1);
362 emit_move_insn (reg2, mem);
363 seq = get_insns ();
364 end_sequence ();
365 target_spill_cost = seq_cost (seq);
368 /* Estimates cost of increased register pressure caused by making N_NEW new
369 registers live around the loop. N_OLD is the number of registers live
370 around the loop. */
372 unsigned
373 estimate_reg_pressure_cost (unsigned n_new, unsigned n_old)
375 unsigned regs_needed = n_new + n_old;
377 /* If we have enough registers, we should use them and not restrict
378 the transformations unnecessarily. */
379 if (regs_needed + target_res_regs <= target_avail_regs)
380 return 0;
382 /* If we are close to running out of registers, try to preserve them. */
383 if (regs_needed <= target_avail_regs)
384 return target_reg_cost * n_new;
386 /* If we run out of registers, it is very expensive to add another one. */
387 return target_spill_cost * n_new;
390 /* Sets EDGE_LOOP_EXIT flag for all loop exits. */
392 void
393 mark_loop_exit_edges (void)
395 basic_block bb;
396 edge e;
398 if (number_of_loops () <= 1)
399 return;
401 FOR_EACH_BB (bb)
403 edge_iterator ei;
405 FOR_EACH_EDGE (e, ei, bb->succs)
407 if (loop_outer (bb->loop_father)
408 && loop_exit_edge_p (bb->loop_father, e))
409 e->flags |= EDGE_LOOP_EXIT;
410 else
411 e->flags &= ~EDGE_LOOP_EXIT;