[AArch64] Improve scheduling model for X-Gene
[official-gcc.git] / gcc / cfgloopanal.c
blob78a3c9387aafdca121fd585f825271075e99de31
1 /* Natural loop analysis code for GNU compiler.
2 Copyright (C) 2002-2017 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 "backend.h"
24 #include "rtl.h"
25 #include "tree.h"
26 #include "predict.h"
27 #include "memmodel.h"
28 #include "emit-rtl.h"
29 #include "cfgloop.h"
30 #include "explow.h"
31 #include "expr.h"
32 #include "graphds.h"
33 #include "params.h"
35 struct target_cfgloop default_target_cfgloop;
36 #if SWITCHABLE_TARGET
37 struct target_cfgloop *this_target_cfgloop = &default_target_cfgloop;
38 #endif
40 /* Checks whether BB is executed exactly once in each LOOP iteration. */
42 bool
43 just_once_each_iteration_p (const struct loop *loop, const_basic_block bb)
45 /* It must be executed at least once each iteration. */
46 if (!dominated_by_p (CDI_DOMINATORS, loop->latch, bb))
47 return false;
49 /* And just once. */
50 if (bb->loop_father != loop)
51 return false;
53 /* But this was not enough. We might have some irreducible loop here. */
54 if (bb->flags & BB_IRREDUCIBLE_LOOP)
55 return false;
57 return true;
60 /* Marks blocks and edges that are part of non-recognized loops; i.e. we
61 throw away all latch edges and mark blocks inside any remaining cycle.
62 Everything is a bit complicated due to fact we do not want to do this
63 for parts of cycles that only "pass" through some loop -- i.e. for
64 each cycle, we want to mark blocks that belong directly to innermost
65 loop containing the whole cycle.
67 LOOPS is the loop tree. */
69 #define LOOP_REPR(LOOP) ((LOOP)->num + last_basic_block_for_fn (cfun))
70 #define BB_REPR(BB) ((BB)->index + 1)
72 bool
73 mark_irreducible_loops (void)
75 basic_block act;
76 struct graph_edge *ge;
77 edge e;
78 edge_iterator ei;
79 int src, dest;
80 unsigned depth;
81 struct graph *g;
82 int num = number_of_loops (cfun);
83 struct loop *cloop;
84 bool irred_loop_found = false;
85 int i;
87 gcc_assert (current_loops != NULL);
89 /* Reset the flags. */
90 FOR_BB_BETWEEN (act, ENTRY_BLOCK_PTR_FOR_FN (cfun),
91 EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb)
93 act->flags &= ~BB_IRREDUCIBLE_LOOP;
94 FOR_EACH_EDGE (e, ei, act->succs)
95 e->flags &= ~EDGE_IRREDUCIBLE_LOOP;
98 /* Create the edge lists. */
99 g = new_graph (last_basic_block_for_fn (cfun) + num);
101 FOR_BB_BETWEEN (act, ENTRY_BLOCK_PTR_FOR_FN (cfun),
102 EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb)
103 FOR_EACH_EDGE (e, ei, act->succs)
105 /* Ignore edges to exit. */
106 if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
107 continue;
109 src = BB_REPR (act);
110 dest = BB_REPR (e->dest);
112 /* Ignore latch edges. */
113 if (e->dest->loop_father->header == e->dest
114 && e->dest->loop_father->latch == act)
115 continue;
117 /* Edges inside a single loop should be left where they are. Edges
118 to subloop headers should lead to representative of the subloop,
119 but from the same place.
121 Edges exiting loops should lead from representative
122 of the son of nearest common ancestor of the loops in that
123 act lays. */
125 if (e->dest->loop_father->header == e->dest)
126 dest = LOOP_REPR (e->dest->loop_father);
128 if (!flow_bb_inside_loop_p (act->loop_father, e->dest))
130 depth = 1 + loop_depth (find_common_loop (act->loop_father,
131 e->dest->loop_father));
132 if (depth == loop_depth (act->loop_father))
133 cloop = act->loop_father;
134 else
135 cloop = (*act->loop_father->superloops)[depth];
137 src = LOOP_REPR (cloop);
140 add_edge (g, src, dest)->data = e;
143 /* Find the strongly connected components. */
144 graphds_scc (g, NULL);
146 /* Mark the irreducible loops. */
147 for (i = 0; i < g->n_vertices; i++)
148 for (ge = g->vertices[i].succ; ge; ge = ge->succ_next)
150 edge real = (edge) ge->data;
151 /* edge E in graph G is irreducible if it connects two vertices in the
152 same scc. */
154 /* All edges should lead from a component with higher number to the
155 one with lower one. */
156 gcc_assert (g->vertices[ge->src].component >= g->vertices[ge->dest].component);
158 if (g->vertices[ge->src].component != g->vertices[ge->dest].component)
159 continue;
161 real->flags |= EDGE_IRREDUCIBLE_LOOP;
162 irred_loop_found = true;
163 if (flow_bb_inside_loop_p (real->src->loop_father, real->dest))
164 real->src->flags |= BB_IRREDUCIBLE_LOOP;
167 free_graph (g);
169 loops_state_set (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS);
170 return irred_loop_found;
173 /* Counts number of insns inside LOOP. */
175 num_loop_insns (const struct loop *loop)
177 basic_block *bbs, bb;
178 unsigned i, ninsns = 0;
179 rtx_insn *insn;
181 bbs = get_loop_body (loop);
182 for (i = 0; i < loop->num_nodes; i++)
184 bb = bbs[i];
185 FOR_BB_INSNS (bb, insn)
186 if (NONDEBUG_INSN_P (insn))
187 ninsns++;
189 free (bbs);
191 if (!ninsns)
192 ninsns = 1; /* To avoid division by zero. */
194 return ninsns;
197 /* Counts number of insns executed on average per iteration LOOP. */
199 average_num_loop_insns (const struct loop *loop)
201 basic_block *bbs, bb;
202 unsigned i, binsns, ninsns, ratio;
203 rtx_insn *insn;
205 ninsns = 0;
206 bbs = get_loop_body (loop);
207 for (i = 0; i < loop->num_nodes; i++)
209 bb = bbs[i];
211 binsns = 0;
212 FOR_BB_INSNS (bb, insn)
213 if (NONDEBUG_INSN_P (insn))
214 binsns++;
216 ratio = loop->header->count.to_frequency (cfun) == 0
217 ? BB_FREQ_MAX
218 : (bb->count.to_frequency (cfun) * BB_FREQ_MAX)
219 / loop->header->count.to_frequency (cfun);
220 ninsns += binsns * ratio;
222 free (bbs);
224 ninsns /= BB_FREQ_MAX;
225 if (!ninsns)
226 ninsns = 1; /* To avoid division by zero. */
228 return ninsns;
231 /* Returns expected number of iterations of LOOP, according to
232 measured or guessed profile. No bounding is done on the
233 value. */
235 gcov_type
236 expected_loop_iterations_unbounded (const struct loop *loop,
237 bool *read_profile_p)
239 edge e;
240 edge_iterator ei;
241 gcov_type expected = -1;
243 if (read_profile_p)
244 *read_profile_p = false;
246 /* If we have no profile at all, use AVG_LOOP_NITER. */
247 if (profile_status_for_fn (cfun) == PROFILE_ABSENT)
248 expected = PARAM_VALUE (PARAM_AVG_LOOP_NITER);
249 else if (loop->latch && (loop->latch->count.initialized_p ()
250 || loop->header->count.initialized_p ()))
252 profile_count count_in = profile_count::zero (),
253 count_latch = profile_count::zero ();
255 FOR_EACH_EDGE (e, ei, loop->header->preds)
256 if (e->src == loop->latch)
257 count_latch = e->count ();
258 else
259 count_in += e->count ();
261 if (!count_latch.initialized_p ())
262 expected = PARAM_VALUE (PARAM_AVG_LOOP_NITER);
263 else if (!count_in.nonzero_p ())
264 expected = count_latch.to_gcov_type () * 2;
265 else
267 expected = (count_latch.to_gcov_type () + count_in.to_gcov_type ()
268 - 1) / count_in.to_gcov_type ();
269 if (read_profile_p
270 && count_latch.reliable_p () && count_in.reliable_p ())
271 *read_profile_p = true;
274 else
275 expected = PARAM_VALUE (PARAM_AVG_LOOP_NITER);
277 HOST_WIDE_INT max = get_max_loop_iterations_int (loop);
278 if (max != -1 && max < expected)
279 return max;
281 return expected;
284 /* Returns expected number of LOOP iterations. The returned value is bounded
285 by REG_BR_PROB_BASE. */
287 unsigned
288 expected_loop_iterations (struct loop *loop)
290 gcov_type expected = expected_loop_iterations_unbounded (loop);
291 return (expected > REG_BR_PROB_BASE ? REG_BR_PROB_BASE : expected);
294 /* Returns the maximum level of nesting of subloops of LOOP. */
296 unsigned
297 get_loop_level (const struct loop *loop)
299 const struct loop *ploop;
300 unsigned mx = 0, l;
302 for (ploop = loop->inner; ploop; ploop = ploop->next)
304 l = get_loop_level (ploop);
305 if (l >= mx)
306 mx = l + 1;
308 return mx;
311 /* Initialize the constants for computing set costs. */
313 void
314 init_set_costs (void)
316 int speed;
317 rtx_insn *seq;
318 rtx reg1 = gen_raw_REG (SImode, LAST_VIRTUAL_REGISTER + 1);
319 rtx reg2 = gen_raw_REG (SImode, LAST_VIRTUAL_REGISTER + 2);
320 rtx addr = gen_raw_REG (Pmode, LAST_VIRTUAL_REGISTER + 3);
321 rtx mem = validize_mem (gen_rtx_MEM (SImode, addr));
322 unsigned i;
324 target_avail_regs = 0;
325 target_clobbered_regs = 0;
326 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
327 if (TEST_HARD_REG_BIT (reg_class_contents[GENERAL_REGS], i)
328 && !fixed_regs[i])
330 target_avail_regs++;
331 if (call_used_regs[i])
332 target_clobbered_regs++;
335 target_res_regs = 3;
337 for (speed = 0; speed < 2; speed++)
339 crtl->maybe_hot_insn_p = speed;
340 /* Set up the costs for using extra registers:
342 1) If not many free registers remain, we should prefer having an
343 additional move to decreasing the number of available registers.
344 (TARGET_REG_COST).
345 2) If no registers are available, we need to spill, which may require
346 storing the old value to memory and loading it back
347 (TARGET_SPILL_COST). */
349 start_sequence ();
350 emit_move_insn (reg1, reg2);
351 seq = get_insns ();
352 end_sequence ();
353 target_reg_cost [speed] = seq_cost (seq, speed);
355 start_sequence ();
356 emit_move_insn (mem, reg1);
357 emit_move_insn (reg2, mem);
358 seq = get_insns ();
359 end_sequence ();
360 target_spill_cost [speed] = seq_cost (seq, speed);
362 default_rtl_profile ();
365 /* Estimates cost of increased register pressure caused by making N_NEW new
366 registers live around the loop. N_OLD is the number of registers live
367 around the loop. If CALL_P is true, also take into account that
368 call-used registers may be clobbered in the loop body, reducing the
369 number of available registers before we spill. */
371 unsigned
372 estimate_reg_pressure_cost (unsigned n_new, unsigned n_old, bool speed,
373 bool call_p)
375 unsigned cost;
376 unsigned regs_needed = n_new + n_old;
377 unsigned available_regs = target_avail_regs;
379 /* If there is a call in the loop body, the call-clobbered registers
380 are not available for loop invariants. */
381 if (call_p)
382 available_regs = available_regs - target_clobbered_regs;
384 /* If we have enough registers, we should use them and not restrict
385 the transformations unnecessarily. */
386 if (regs_needed + target_res_regs <= available_regs)
387 return 0;
389 if (regs_needed <= available_regs)
390 /* If we are close to running out of registers, try to preserve
391 them. */
392 cost = target_reg_cost [speed] * n_new;
393 else
394 /* If we run out of registers, it is very expensive to add another
395 one. */
396 cost = target_spill_cost [speed] * n_new;
398 if (optimize && (flag_ira_region == IRA_REGION_ALL
399 || flag_ira_region == IRA_REGION_MIXED)
400 && number_of_loops (cfun) <= (unsigned) IRA_MAX_LOOPS_NUM)
401 /* IRA regional allocation deals with high register pressure
402 better. So decrease the cost (to do more accurate the cost
403 calculation for IRA, we need to know how many registers lives
404 through the loop transparently). */
405 cost /= 2;
407 return cost;
410 /* Sets EDGE_LOOP_EXIT flag for all loop exits. */
412 void
413 mark_loop_exit_edges (void)
415 basic_block bb;
416 edge e;
418 if (number_of_loops (cfun) <= 1)
419 return;
421 FOR_EACH_BB_FN (bb, cfun)
423 edge_iterator ei;
425 FOR_EACH_EDGE (e, ei, bb->succs)
427 if (loop_outer (bb->loop_father)
428 && loop_exit_edge_p (bb->loop_father, e))
429 e->flags |= EDGE_LOOP_EXIT;
430 else
431 e->flags &= ~EDGE_LOOP_EXIT;
436 /* Return exit edge if loop has only one exit that is likely
437 to be executed on runtime (i.e. it is not EH or leading
438 to noreturn call. */
440 edge
441 single_likely_exit (struct loop *loop)
443 edge found = single_exit (loop);
444 vec<edge> exits;
445 unsigned i;
446 edge ex;
448 if (found)
449 return found;
450 exits = get_loop_exit_edges (loop);
451 FOR_EACH_VEC_ELT (exits, i, ex)
453 if (probably_never_executed_edge_p (cfun, ex)
454 /* We want to rule out paths to noreturns but not low probabilities
455 resulting from adjustments or combining.
456 FIXME: once we have better quality tracking, make this more
457 robust. */
458 || ex->probability <= profile_probability::very_unlikely ())
459 continue;
460 if (!found)
461 found = ex;
462 else
464 exits.release ();
465 return NULL;
468 exits.release ();
469 return found;
473 /* Gets basic blocks of a LOOP. Header is the 0-th block, rest is in dfs
474 order against direction of edges from latch. Specially, if
475 header != latch, latch is the 1-st block. */
477 vec<basic_block>
478 get_loop_hot_path (const struct loop *loop)
480 basic_block bb = loop->header;
481 vec<basic_block> path = vNULL;
482 bitmap visited = BITMAP_ALLOC (NULL);
484 while (true)
486 edge_iterator ei;
487 edge e;
488 edge best = NULL;
490 path.safe_push (bb);
491 bitmap_set_bit (visited, bb->index);
492 FOR_EACH_EDGE (e, ei, bb->succs)
493 if ((!best || e->probability > best->probability)
494 && !loop_exit_edge_p (loop, e)
495 && !bitmap_bit_p (visited, e->dest->index))
496 best = e;
497 if (!best || best->dest == loop->header)
498 break;
499 bb = best->dest;
501 BITMAP_FREE (visited);
502 return path;