/* 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-2019 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"
struct target_cfgloop default_target_cfgloop;
#if SWITCHABLE_TARGET
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 ();
+ int num = number_of_loops (cfun);
struct 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);
{
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++)
average_num_loop_insns (const struct 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 struct 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_VALUE (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_VALUE (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_VALUE (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 (struct loop *loop)
{
gcov_type expected = expected_loop_iterations_unbounded (loop);
return (expected > REG_BR_PROB_BASE ? REG_BR_PROB_BASE : expected);
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;
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) 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;
exits = get_loop_exit_edges (loop);
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;