2012-11-28 Oleg Raikhman <oleg@adapteva.com>
[official-gcc.git] / gcc / cfgloopanal.c
blob7fdbd4ae7d4f060bd621bb1e9568a3e8e5145621
1 /* Natural loop analysis code for GNU compiler.
2 Copyright (C) 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010
3 Free Software Foundation, Inc.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
10 version.
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15 for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
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 "graphds.h"
32 #include "params.h"
34 struct target_cfgloop default_target_cfgloop;
35 #if SWITCHABLE_TARGET
36 struct target_cfgloop *this_target_cfgloop = &default_target_cfgloop;
37 #endif
39 /* Checks whether BB is executed exactly once in each LOOP iteration. */
41 bool
42 just_once_each_iteration_p (const struct loop *loop, const_basic_block bb)
44 /* It must be executed at least once each iteration. */
45 if (!dominated_by_p (CDI_DOMINATORS, loop->latch, bb))
46 return false;
48 /* And just once. */
49 if (bb->loop_father != loop)
50 return false;
52 /* But this was not enough. We might have some irreducible loop here. */
53 if (bb->flags & BB_IRREDUCIBLE_LOOP)
54 return false;
56 return true;
59 /* Marks blocks and edges that are part of non-recognized loops; i.e. we
60 throw away all latch edges and mark blocks inside any remaining cycle.
61 Everything is a bit complicated due to fact we do not want to do this
62 for parts of cycles that only "pass" through some loop -- i.e. for
63 each cycle, we want to mark blocks that belong directly to innermost
64 loop containing the whole cycle.
66 LOOPS is the loop tree. */
68 #define LOOP_REPR(LOOP) ((LOOP)->num + last_basic_block)
69 #define BB_REPR(BB) ((BB)->index + 1)
71 bool
72 mark_irreducible_loops (void)
74 basic_block act;
75 struct graph_edge *ge;
76 edge e;
77 edge_iterator ei;
78 int src, dest;
79 unsigned depth;
80 struct graph *g;
81 int num = number_of_loops ();
82 struct loop *cloop;
83 bool irred_loop_found = false;
84 int i;
86 gcc_assert (current_loops != NULL);
88 /* Reset the flags. */
89 FOR_BB_BETWEEN (act, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
91 act->flags &= ~BB_IRREDUCIBLE_LOOP;
92 FOR_EACH_EDGE (e, ei, act->succs)
93 e->flags &= ~EDGE_IRREDUCIBLE_LOOP;
96 /* Create the edge lists. */
97 g = new_graph (last_basic_block + num);
99 FOR_BB_BETWEEN (act, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
100 FOR_EACH_EDGE (e, ei, act->succs)
102 /* Ignore edges to exit. */
103 if (e->dest == EXIT_BLOCK_PTR)
104 continue;
106 src = BB_REPR (act);
107 dest = BB_REPR (e->dest);
109 /* Ignore latch edges. */
110 if (e->dest->loop_father->header == e->dest
111 && e->dest->loop_father->latch == act)
112 continue;
114 /* Edges inside a single loop should be left where they are. Edges
115 to subloop headers should lead to representative of the subloop,
116 but from the same place.
118 Edges exiting loops should lead from representative
119 of the son of nearest common ancestor of the loops in that
120 act lays. */
122 if (e->dest->loop_father->header == e->dest)
123 dest = LOOP_REPR (e->dest->loop_father);
125 if (!flow_bb_inside_loop_p (act->loop_father, e->dest))
127 depth = 1 + loop_depth (find_common_loop (act->loop_father,
128 e->dest->loop_father));
129 if (depth == loop_depth (act->loop_father))
130 cloop = act->loop_father;
131 else
132 cloop = (*act->loop_father->superloops)[depth];
134 src = LOOP_REPR (cloop);
137 add_edge (g, src, dest)->data = e;
140 /* Find the strongly connected components. */
141 graphds_scc (g, NULL);
143 /* Mark the irreducible loops. */
144 for (i = 0; i < g->n_vertices; i++)
145 for (ge = g->vertices[i].succ; ge; ge = ge->succ_next)
147 edge real = (edge) ge->data;
148 /* edge E in graph G is irreducible if it connects two vertices in the
149 same scc. */
151 /* All edges should lead from a component with higher number to the
152 one with lower one. */
153 gcc_assert (g->vertices[ge->src].component >= g->vertices[ge->dest].component);
155 if (g->vertices[ge->src].component != g->vertices[ge->dest].component)
156 continue;
158 real->flags |= EDGE_IRREDUCIBLE_LOOP;
159 irred_loop_found = true;
160 if (flow_bb_inside_loop_p (real->src->loop_father, real->dest))
161 real->src->flags |= BB_IRREDUCIBLE_LOOP;
164 free_graph (g);
166 loops_state_set (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS);
167 return irred_loop_found;
170 /* Counts number of insns inside LOOP. */
172 num_loop_insns (const struct loop *loop)
174 basic_block *bbs, bb;
175 unsigned i, ninsns = 0;
176 rtx insn;
178 bbs = get_loop_body (loop);
179 for (i = 0; i < loop->num_nodes; i++)
181 bb = bbs[i];
182 FOR_BB_INSNS (bb, insn)
183 if (NONDEBUG_INSN_P (insn))
184 ninsns++;
186 free (bbs);
188 if (!ninsns)
189 ninsns = 1; /* To avoid division by zero. */
191 return ninsns;
194 /* Counts number of insns executed on average per iteration LOOP. */
196 average_num_loop_insns (const struct loop *loop)
198 basic_block *bbs, bb;
199 unsigned i, binsns, ninsns, ratio;
200 rtx insn;
202 ninsns = 0;
203 bbs = get_loop_body (loop);
204 for (i = 0; i < loop->num_nodes; i++)
206 bb = bbs[i];
208 binsns = 0;
209 FOR_BB_INSNS (bb, insn)
210 if (NONDEBUG_INSN_P (insn))
211 binsns++;
213 ratio = loop->header->frequency == 0
214 ? BB_FREQ_MAX
215 : (bb->frequency * BB_FREQ_MAX) / loop->header->frequency;
216 ninsns += binsns * ratio;
218 free (bbs);
220 ninsns /= BB_FREQ_MAX;
221 if (!ninsns)
222 ninsns = 1; /* To avoid division by zero. */
224 return ninsns;
227 /* Returns expected number of iterations of LOOP, according to
228 measured or guessed profile. No bounding is done on the
229 value. */
231 gcov_type
232 expected_loop_iterations_unbounded (const struct loop *loop)
234 edge e;
235 edge_iterator ei;
237 if (loop->latch->count || loop->header->count)
239 gcov_type count_in, count_latch, expected;
241 count_in = 0;
242 count_latch = 0;
244 FOR_EACH_EDGE (e, ei, loop->header->preds)
245 if (e->src == loop->latch)
246 count_latch = e->count;
247 else
248 count_in += e->count;
250 if (count_in == 0)
251 expected = count_latch * 2;
252 else
253 expected = (count_latch + count_in - 1) / count_in;
255 return expected;
257 else
259 int freq_in, freq_latch;
261 freq_in = 0;
262 freq_latch = 0;
264 FOR_EACH_EDGE (e, ei, loop->header->preds)
265 if (e->src == loop->latch)
266 freq_latch = EDGE_FREQUENCY (e);
267 else
268 freq_in += EDGE_FREQUENCY (e);
270 if (freq_in == 0)
271 return freq_latch * 2;
273 return (freq_latch + freq_in - 1) / freq_in;
277 /* Returns expected number of LOOP iterations. The returned value is bounded
278 by REG_BR_PROB_BASE. */
280 unsigned
281 expected_loop_iterations (const struct loop *loop)
283 gcov_type expected = expected_loop_iterations_unbounded (loop);
284 return (expected > REG_BR_PROB_BASE ? REG_BR_PROB_BASE : expected);
287 /* Returns the maximum level of nesting of subloops of LOOP. */
289 unsigned
290 get_loop_level (const struct loop *loop)
292 const struct loop *ploop;
293 unsigned mx = 0, l;
295 for (ploop = loop->inner; ploop; ploop = ploop->next)
297 l = get_loop_level (ploop);
298 if (l >= mx)
299 mx = l + 1;
301 return mx;
304 /* Returns estimate on cost of computing SEQ. */
306 static unsigned
307 seq_cost (const_rtx seq, bool speed)
309 unsigned cost = 0;
310 rtx set;
312 for (; seq; seq = NEXT_INSN (seq))
314 set = single_set (seq);
315 if (set)
316 cost += set_rtx_cost (set, speed);
317 else
318 cost++;
321 return cost;
324 /* Initialize the constants for computing set costs. */
326 void
327 init_set_costs (void)
329 int speed;
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 target_clobbered_regs = 0;
339 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
340 if (TEST_HARD_REG_BIT (reg_class_contents[GENERAL_REGS], i)
341 && !fixed_regs[i])
343 target_avail_regs++;
344 if (call_used_regs[i])
345 target_clobbered_regs++;
348 target_res_regs = 3;
350 for (speed = 0; speed < 2; speed++)
352 crtl->maybe_hot_insn_p = speed;
353 /* Set up the costs for using extra registers:
355 1) If not many free registers remain, we should prefer having an
356 additional move to decreasing the number of available registers.
357 (TARGET_REG_COST).
358 2) If no registers are available, we need to spill, which may require
359 storing the old value to memory and loading it back
360 (TARGET_SPILL_COST). */
362 start_sequence ();
363 emit_move_insn (reg1, reg2);
364 seq = get_insns ();
365 end_sequence ();
366 target_reg_cost [speed] = seq_cost (seq, speed);
368 start_sequence ();
369 emit_move_insn (mem, reg1);
370 emit_move_insn (reg2, mem);
371 seq = get_insns ();
372 end_sequence ();
373 target_spill_cost [speed] = seq_cost (seq, speed);
375 default_rtl_profile ();
378 /* Estimates cost of increased register pressure caused by making N_NEW new
379 registers live around the loop. N_OLD is the number of registers live
380 around the loop. If CALL_P is true, also take into account that
381 call-used registers may be clobbered in the loop body, reducing the
382 number of available registers before we spill. */
384 unsigned
385 estimate_reg_pressure_cost (unsigned n_new, unsigned n_old, bool speed,
386 bool call_p)
388 unsigned cost;
389 unsigned regs_needed = n_new + n_old;
390 unsigned available_regs = target_avail_regs;
392 /* If there is a call in the loop body, the call-clobbered registers
393 are not available for loop invariants. */
394 if (call_p)
395 available_regs = available_regs - target_clobbered_regs;
397 /* If we have enough registers, we should use them and not restrict
398 the transformations unnecessarily. */
399 if (regs_needed + target_res_regs <= available_regs)
400 return 0;
402 if (regs_needed <= available_regs)
403 /* If we are close to running out of registers, try to preserve
404 them. */
405 cost = target_reg_cost [speed] * n_new;
406 else
407 /* If we run out of registers, it is very expensive to add another
408 one. */
409 cost = target_spill_cost [speed] * n_new;
411 if (optimize && (flag_ira_region == IRA_REGION_ALL
412 || flag_ira_region == IRA_REGION_MIXED)
413 && number_of_loops () <= (unsigned) IRA_MAX_LOOPS_NUM)
414 /* IRA regional allocation deals with high register pressure
415 better. So decrease the cost (to do more accurate the cost
416 calculation for IRA, we need to know how many registers lives
417 through the loop transparently). */
418 cost /= 2;
420 return cost;
423 /* Sets EDGE_LOOP_EXIT flag for all loop exits. */
425 void
426 mark_loop_exit_edges (void)
428 basic_block bb;
429 edge e;
431 if (number_of_loops () <= 1)
432 return;
434 FOR_EACH_BB (bb)
436 edge_iterator ei;
438 FOR_EACH_EDGE (e, ei, bb->succs)
440 if (loop_outer (bb->loop_father)
441 && loop_exit_edge_p (bb->loop_father, e))
442 e->flags |= EDGE_LOOP_EXIT;
443 else
444 e->flags &= ~EDGE_LOOP_EXIT;
449 /* Return exit edge if loop has only one exit that is likely
450 to be executed on runtime (i.e. it is not EH or leading
451 to noreturn call. */
453 edge
454 single_likely_exit (struct loop *loop)
456 edge found = single_exit (loop);
457 vec<edge> exits;
458 unsigned i;
459 edge ex;
461 if (found)
462 return found;
463 exits = get_loop_exit_edges (loop);
464 FOR_EACH_VEC_ELT (exits, i, ex)
466 if (ex->flags & (EDGE_EH | EDGE_ABNORMAL_CALL))
467 continue;
468 /* The constant of 5 is set in a way so noreturn calls are
469 ruled out by this test. The static branch prediction algorithm
470 will not assign such a low probability to conditionals for usual
471 reasons. */
472 if (profile_status != PROFILE_ABSENT
473 && ex->probability < 5 && !ex->count)
474 continue;
475 if (!found)
476 found = ex;
477 else
479 exits.release ();
480 return NULL;
483 exits.release ();
484 return found;
488 /* Gets basic blocks of a LOOP. Header is the 0-th block, rest is in dfs
489 order against direction of edges from latch. Specially, if
490 header != latch, latch is the 1-st block. */
492 vec<basic_block>
493 get_loop_hot_path (const struct loop *loop)
495 basic_block bb = loop->header;
496 vec<basic_block> path = vNULL;
497 bitmap visited = BITMAP_ALLOC (NULL);
499 while (true)
501 edge_iterator ei;
502 edge e;
503 edge best = NULL;
505 path.safe_push (bb);
506 bitmap_set_bit (visited, bb->index);
507 FOR_EACH_EDGE (e, ei, bb->succs)
508 if ((!best || e->probability > best->probability)
509 && !loop_exit_edge_p (loop, e)
510 && !bitmap_bit_p (visited, e->dest->index))
511 best = e;
512 if (!best || best->dest == loop->header)
513 break;
514 bb = best->dest;
516 BITMAP_FREE (visited);
517 return path;