/* Natural loop analysis code for GNU compiler.
- Copyright (C) 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010
- Free Software Foundation, Inc.
+ Copyright (C) 2002-2020 Free Software Foundation, Inc.
This file is part of GCC.
#include "config.h"
#include "system.h"
#include "coretypes.h"
-#include "tm.h"
+#include "backend.h"
#include "rtl.h"
-#include "hard-reg-set.h"
-#include "obstack.h"
-#include "basic-block.h"
+#include "tree.h"
+#include "predict.h"
+#include "memmodel.h"
+#include "emit-rtl.h"
#include "cfgloop.h"
+#include "explow.h"
#include "expr.h"
#include "graphds.h"
-#include "params.h"
+#include "sreal.h"
+#include "regs.h"
+#include "function-abi.h"
struct target_cfgloop default_target_cfgloop;
#if SWITCHABLE_TARGET
/* Checks whether BB is executed exactly once in each LOOP iteration. */
bool
-just_once_each_iteration_p (const struct loop *loop, const_basic_block bb)
+just_once_each_iteration_p (const class loop *loop, const_basic_block bb)
{
/* It must be executed at least once each iteration. */
if (!dominated_by_p (CDI_DOMINATORS, loop->latch, bb))
LOOPS is the loop tree. */
-#define LOOP_REPR(LOOP) ((LOOP)->num + last_basic_block)
+#define LOOP_REPR(LOOP) ((LOOP)->num + last_basic_block_for_fn (cfun))
#define BB_REPR(BB) ((BB)->index + 1)
bool
int src, dest;
unsigned depth;
struct graph *g;
- int num = number_of_loops ();
- struct loop *cloop;
+ int num = number_of_loops (cfun);
+ class loop *cloop;
bool irred_loop_found = false;
int i;
gcc_assert (current_loops != NULL);
/* Reset the flags. */
- FOR_BB_BETWEEN (act, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
+ FOR_BB_BETWEEN (act, ENTRY_BLOCK_PTR_FOR_FN (cfun),
+ EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb)
{
act->flags &= ~BB_IRREDUCIBLE_LOOP;
FOR_EACH_EDGE (e, ei, act->succs)
}
/* Create the edge lists. */
- g = new_graph (last_basic_block + num);
+ g = new_graph (last_basic_block_for_fn (cfun) + num);
- FOR_BB_BETWEEN (act, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
+ FOR_BB_BETWEEN (act, ENTRY_BLOCK_PTR_FOR_FN (cfun),
+ EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb)
FOR_EACH_EDGE (e, ei, act->succs)
{
/* Ignore edges to exit. */
- if (e->dest == EXIT_BLOCK_PTR)
+ if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
continue;
src = BB_REPR (act);
if (depth == loop_depth (act->loop_father))
cloop = act->loop_father;
else
- cloop = VEC_index (loop_p, act->loop_father->superloops, depth);
+ cloop = (*act->loop_father->superloops)[depth];
src = LOOP_REPR (cloop);
}
/* Counts number of insns inside LOOP. */
int
-num_loop_insns (const struct loop *loop)
+num_loop_insns (const class loop *loop)
{
basic_block *bbs, bb;
unsigned i, ninsns = 0;
- rtx insn;
+ rtx_insn *insn;
bbs = get_loop_body (loop);
for (i = 0; i < loop->num_nodes; i++)
/* Counts number of insns executed on average per iteration LOOP. */
int
-average_num_loop_insns (const struct loop *loop)
+average_num_loop_insns (const class loop *loop)
{
basic_block *bbs, bb;
- unsigned i, binsns, ninsns, ratio;
- rtx insn;
+ unsigned i, binsns;
+ sreal ninsns;
+ rtx_insn *insn;
ninsns = 0;
bbs = get_loop_body (loop);
if (NONDEBUG_INSN_P (insn))
binsns++;
- ratio = loop->header->frequency == 0
- ? BB_FREQ_MAX
- : (bb->frequency * BB_FREQ_MAX) / loop->header->frequency;
- ninsns += binsns * ratio;
+ ninsns += (sreal)binsns * bb->count.to_sreal_scale (loop->header->count);
+ /* Avoid overflows. */
+ if (ninsns > 1000000)
+ return 100000;
}
free (bbs);
- ninsns /= BB_FREQ_MAX;
- if (!ninsns)
- ninsns = 1; /* To avoid division by zero. */
+ int64_t ret = ninsns.to_int ();
+ if (!ret)
+ ret = 1; /* To avoid division by zero. */
- return ninsns;
+ return ret;
}
/* Returns expected number of iterations of LOOP, according to
- measured or guessed profile. No bounding is done on the
- value. */
+ measured or guessed profile.
+
+ This functions attempts to return "sane" value even if profile
+ information is not good enough to derive osmething.
+ If BY_PROFILE_ONLY is set, this logic is bypassed and function
+ return -1 in those scenarios. */
gcov_type
-expected_loop_iterations_unbounded (const struct loop *loop)
+expected_loop_iterations_unbounded (const class loop *loop,
+ bool *read_profile_p,
+ bool by_profile_only)
{
edge e;
edge_iterator ei;
+ gcov_type expected = -1;
+
+ if (read_profile_p)
+ *read_profile_p = false;
- if (loop->latch->count || loop->header->count)
+ /* If we have no profile at all, use AVG_LOOP_NITER. */
+ if (profile_status_for_fn (cfun) == PROFILE_ABSENT)
{
- gcov_type count_in, count_latch, expected;
-
- count_in = 0;
- count_latch = 0;
+ if (by_profile_only)
+ return -1;
+ expected = param_avg_loop_niter;
+ }
+ else if (loop->latch && (loop->latch->count.initialized_p ()
+ || loop->header->count.initialized_p ()))
+ {
+ profile_count count_in = profile_count::zero (),
+ count_latch = profile_count::zero ();
FOR_EACH_EDGE (e, ei, loop->header->preds)
if (e->src == loop->latch)
- count_latch = e->count;
+ count_latch = e->count ();
else
- count_in += e->count;
+ count_in += e->count ();
- if (count_in == 0)
- expected = count_latch * 2;
+ if (!count_latch.initialized_p ())
+ {
+ if (by_profile_only)
+ return -1;
+ expected = param_avg_loop_niter;
+ }
+ else if (!count_in.nonzero_p ())
+ {
+ if (by_profile_only)
+ return -1;
+ expected = count_latch.to_gcov_type () * 2;
+ }
else
- expected = (count_latch + count_in - 1) / count_in;
-
- return expected;
+ {
+ expected = (count_latch.to_gcov_type () + count_in.to_gcov_type ()
+ - 1) / count_in.to_gcov_type ();
+ if (read_profile_p
+ && count_latch.reliable_p () && count_in.reliable_p ())
+ *read_profile_p = true;
+ }
}
else
{
- int freq_in, freq_latch;
-
- freq_in = 0;
- freq_latch = 0;
-
- FOR_EACH_EDGE (e, ei, loop->header->preds)
- if (e->src == loop->latch)
- freq_latch = EDGE_FREQUENCY (e);
- else
- freq_in += EDGE_FREQUENCY (e);
-
- if (freq_in == 0)
- return freq_latch * 2;
+ if (by_profile_only)
+ return -1;
+ expected = param_avg_loop_niter;
+ }
- return (freq_latch + freq_in - 1) / freq_in;
+ if (!by_profile_only)
+ {
+ HOST_WIDE_INT max = get_max_loop_iterations_int (loop);
+ if (max != -1 && max < expected)
+ return max;
}
+
+ return expected;
}
/* Returns expected number of LOOP iterations. The returned value is bounded
by REG_BR_PROB_BASE. */
unsigned
-expected_loop_iterations (const struct loop *loop)
+expected_loop_iterations (class loop *loop)
{
gcov_type expected = expected_loop_iterations_unbounded (loop);
return (expected > REG_BR_PROB_BASE ? REG_BR_PROB_BASE : expected);
/* Returns the maximum level of nesting of subloops of LOOP. */
unsigned
-get_loop_level (const struct loop *loop)
+get_loop_level (const class loop *loop)
{
- const struct loop *ploop;
+ const class loop *ploop;
unsigned mx = 0, l;
for (ploop = loop->inner; ploop; ploop = ploop->next)
return mx;
}
-/* Returns estimate on cost of computing SEQ. */
-
-static unsigned
-seq_cost (const_rtx seq, bool speed)
-{
- unsigned cost = 0;
- rtx set;
-
- for (; seq; seq = NEXT_INSN (seq))
- {
- set = single_set (seq);
- if (set)
- cost += set_rtx_cost (set, speed);
- else
- cost++;
- }
-
- return cost;
-}
-
/* Initialize the constants for computing set costs. */
void
init_set_costs (void)
{
int speed;
- rtx seq;
- rtx reg1 = gen_raw_REG (SImode, FIRST_PSEUDO_REGISTER);
- rtx reg2 = gen_raw_REG (SImode, FIRST_PSEUDO_REGISTER + 1);
- rtx addr = gen_raw_REG (Pmode, FIRST_PSEUDO_REGISTER + 2);
+ rtx_insn *seq;
+ rtx reg1 = gen_raw_REG (SImode, LAST_VIRTUAL_REGISTER + 1);
+ rtx reg2 = gen_raw_REG (SImode, LAST_VIRTUAL_REGISTER + 2);
+ rtx addr = gen_raw_REG (Pmode, LAST_VIRTUAL_REGISTER + 3);
rtx mem = validize_mem (gen_rtx_MEM (SImode, addr));
unsigned i;
&& !fixed_regs[i])
{
target_avail_regs++;
- if (call_used_regs[i])
+ /* ??? This is only a rough heuristic. It doesn't cope well
+ with alternative ABIs, but that's an optimization rather than
+ correctness issue. */
+ if (default_function_abi.clobbers_full_reg_p (i))
target_clobbered_regs++;
}
if (optimize && (flag_ira_region == IRA_REGION_ALL
|| flag_ira_region == IRA_REGION_MIXED)
- && number_of_loops () <= (unsigned) IRA_MAX_LOOPS_NUM)
+ && number_of_loops (cfun) <= (unsigned) param_ira_max_loops_num)
/* IRA regional allocation deals with high register pressure
better. So decrease the cost (to do more accurate the cost
calculation for IRA, we need to know how many registers lives
basic_block bb;
edge e;
- if (number_of_loops () <= 1)
+ if (number_of_loops (cfun) <= 1)
return;
- FOR_EACH_BB (bb)
+ FOR_EACH_BB_FN (bb, cfun)
{
edge_iterator ei;
to noreturn call. */
edge
-single_likely_exit (struct loop *loop)
+single_likely_exit (class loop *loop, vec<edge> exits)
{
edge found = single_exit (loop);
- VEC (edge, heap) *exits;
unsigned i;
edge ex;
if (found)
return found;
- exits = get_loop_exit_edges (loop);
- FOR_EACH_VEC_ELT (edge, exits, i, ex)
+ FOR_EACH_VEC_ELT (exits, i, ex)
{
- if (ex->flags & (EDGE_EH | EDGE_ABNORMAL_CALL))
- continue;
- /* The constant of 5 is set in a way so noreturn calls are
- ruled out by this test. The static branch prediction algorithm
- will not assign such a low probability to conditionals for usual
- reasons. */
- if (profile_status != PROFILE_ABSENT
- && ex->probability < 5 && !ex->count)
+ if (probably_never_executed_edge_p (cfun, ex)
+ /* We want to rule out paths to noreturns but not low probabilities
+ resulting from adjustments or combining.
+ FIXME: once we have better quality tracking, make this more
+ robust. */
+ || ex->probability <= profile_probability::very_unlikely ())
continue;
if (!found)
found = ex;
else
- {
- VEC_free (edge, heap, exits);
- return NULL;
- }
+ return NULL;
}
- VEC_free (edge, heap, exits);
return found;
}
order against direction of edges from latch. Specially, if
header != latch, latch is the 1-st block. */
-VEC (basic_block, heap) *
-get_loop_hot_path (const struct loop *loop)
+vec<basic_block>
+get_loop_hot_path (const class loop *loop)
{
basic_block bb = loop->header;
- VEC (basic_block, heap) *path = NULL;
+ vec<basic_block> path = vNULL;
bitmap visited = BITMAP_ALLOC (NULL);
while (true)
edge e;
edge best = NULL;
- VEC_safe_push (basic_block, heap, path, bb);
+ path.safe_push (bb);
bitmap_set_bit (visited, bb->index);
FOR_EACH_EDGE (e, ei, bb->succs)
if ((!best || e->probability > best->probability)