/* Rtl-level induction variable analysis.
- Copyright (C) 2004-2015 Free Software Foundation, Inc.
+ Copyright (C) 2004-2019 Free Software Foundation, Inc.
This file is part of GCC.
The available functions are:
- iv_analyze (insn, reg, iv): Stores the description of the induction variable
- corresponding to the use of register REG in INSN to IV. Returns true if
- REG is an induction variable in INSN. false otherwise.
- If use of REG is not found in INSN, following insns are scanned (so that
- we may call this function on insn returned by get_condition).
+ iv_analyze (insn, mode, reg, iv): Stores the description of the induction
+ variable corresponding to the use of register REG in INSN to IV, given
+ that REG has mode MODE. Returns true if REG is an induction variable
+ in INSN. false otherwise. If a use of REG is not found in INSN,
+ the following insns are scanned (so that we may call this function
+ on insns returned by get_condition).
iv_analyze_result (insn, def, iv): Stores to IV the description of the iv
corresponding to DEF, which is a register defined in INSN.
- iv_analyze_expr (insn, rhs, mode, iv): Stores to IV the description of iv
+ iv_analyze_expr (insn, mode, expr, iv): Stores to IV the description of iv
corresponding to expression EXPR evaluated at INSN. All registers used bu
- EXPR must also be used in INSN.
+ EXPR must also be used in INSN. MODE is the mode of EXPR.
*/
#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 "predict.h"
-#include "vec.h"
-#include "hashtab.h"
-#include "hash-set.h"
-#include "machmode.h"
-#include "input.h"
-#include "function.h"
-#include "dominance.h"
-#include "cfg.h"
-#include "basic-block.h"
-#include "cfgloop.h"
-#include "symtab.h"
-#include "flags.h"
-#include "statistics.h"
-#include "double-int.h"
-#include "real.h"
-#include "fixed-value.h"
-#include "alias.h"
-#include "wide-int.h"
-#include "inchash.h"
-#include "tree.h"
-#include "insn-config.h"
-#include "expmed.h"
-#include "dojump.h"
-#include "explow.h"
-#include "calls.h"
+#include "df.h"
+#include "memmodel.h"
#include "emit-rtl.h"
-#include "varasm.h"
-#include "stmt.h"
-#include "expr.h"
-#include "intl.h"
#include "diagnostic-core.h"
-#include "df.h"
-#include "hash-table.h"
+#include "cfgloop.h"
+#include "intl.h"
#include "dumpfile.h"
#include "rtl-iter.h"
/* Hashtable helper. */
-struct biv_entry_hasher : typed_free_remove <biv_entry>
+struct biv_entry_hasher : free_ptr_hash <biv_entry>
{
- typedef biv_entry *value_type;
typedef rtx_def *compare_type;
static inline hashval_t hash (const biv_entry *);
static inline bool equal (const biv_entry *, const rtx_def *);
static hash_table<biv_entry_hasher> *bivs;
-static bool iv_analyze_op (rtx_insn *, rtx, struct rtx_iv *);
+static bool iv_analyze_op (rtx_insn *, scalar_int_mode, rtx, struct rtx_iv *);
/* Return the RTX code corresponding to the IV extend code EXTEND. */
static inline enum rtx_code
fprintf (file, " (first special)");
}
-/* Generates a subreg to get the least significant part of EXPR (in mode
- INNER_MODE) to OUTER_MODE. */
-
-rtx
-lowpart_subreg (machine_mode outer_mode, rtx expr,
- machine_mode inner_mode)
-{
- return simplify_gen_subreg (outer_mode, expr, inner_mode,
- subreg_lowpart_offset (outer_mode, inner_mode));
-}
-
static void
check_iv_ref_table_size (void)
{
consistency with other iv manipulation functions that may fail). */
static bool
-iv_constant (struct rtx_iv *iv, rtx cst, machine_mode mode)
+iv_constant (struct rtx_iv *iv, scalar_int_mode mode, rtx cst)
{
- if (mode == VOIDmode)
- mode = GET_MODE (cst);
-
iv->mode = mode;
iv->base = cst;
iv->step = const0_rtx;
/* Evaluates application of subreg to MODE on IV. */
static bool
-iv_subreg (struct rtx_iv *iv, machine_mode mode)
+iv_subreg (struct rtx_iv *iv, scalar_int_mode mode)
{
/* If iv is invariant, just calculate the new value. */
if (iv->step == const0_rtx
/* Evaluates application of EXTEND to MODE on IV. */
static bool
-iv_extend (struct rtx_iv *iv, enum iv_extend_code extend, machine_mode mode)
+iv_extend (struct rtx_iv *iv, enum iv_extend_code extend, scalar_int_mode mode)
{
/* If iv is invariant, just calculate the new value. */
if (iv->step == const0_rtx
static bool
iv_add (struct rtx_iv *iv0, struct rtx_iv *iv1, enum rtx_code op)
{
- machine_mode mode;
+ scalar_int_mode mode;
rtx arg;
/* Extend the constant to extend_mode of the other operand if necessary. */
static bool
iv_mult (struct rtx_iv *iv, rtx mby)
{
- machine_mode mode = iv->extend_mode;
+ scalar_int_mode mode = iv->extend_mode;
if (GET_MODE (mby) != VOIDmode
&& GET_MODE (mby) != mode)
static bool
iv_shift (struct rtx_iv *iv, rtx mby)
{
- machine_mode mode = iv->extend_mode;
+ scalar_int_mode mode = iv->extend_mode;
if (GET_MODE (mby) != VOIDmode
&& GET_MODE (mby) != mode)
at get_biv_step. */
static bool
-get_biv_step_1 (df_ref def, rtx reg,
- rtx *inner_step, machine_mode *inner_mode,
- enum iv_extend_code *extend, machine_mode outer_mode,
+get_biv_step_1 (df_ref def, scalar_int_mode outer_mode, rtx reg,
+ rtx *inner_step, scalar_int_mode *inner_mode,
+ enum iv_extend_code *extend,
rtx *outer_step)
{
rtx set, rhs, op0 = NULL_RTX, op1 = NULL_RTX;
- rtx next, nextr, tmp;
+ rtx next, nextr;
enum rtx_code code;
rtx_insn *insn = DF_REF_INSN (def);
df_ref next_def;
op1 = XEXP (rhs, 1);
if (code == PLUS && CONSTANT_P (op0))
- {
- tmp = op0; op0 = op1; op1 = tmp;
- }
+ std::swap (op0, op1);
if (!simple_reg_p (op0)
|| !CONSTANT_P (op1))
*inner_mode = outer_mode;
*outer_step = const0_rtx;
}
- else if (!get_biv_step_1 (next_def, reg,
- inner_step, inner_mode, extend, outer_mode,
+ else if (!get_biv_step_1 (next_def, outer_mode, reg,
+ inner_step, inner_mode, extend,
outer_step))
return false;
if (GET_CODE (next) == SUBREG)
{
- machine_mode amode = GET_MODE (next);
-
- if (GET_MODE_SIZE (amode) > GET_MODE_SIZE (*inner_mode))
+ scalar_int_mode amode;
+ if (!is_a <scalar_int_mode> (GET_MODE (next), &amode)
+ || GET_MODE_SIZE (amode) > GET_MODE_SIZE (*inner_mode))
return false;
*inner_mode = amode;
LAST_DEF is the definition of REG that dominates loop latch. */
static bool
-get_biv_step (df_ref last_def, rtx reg, rtx *inner_step,
- machine_mode *inner_mode, enum iv_extend_code *extend,
- machine_mode *outer_mode, rtx *outer_step)
+get_biv_step (df_ref last_def, scalar_int_mode outer_mode, rtx reg,
+ rtx *inner_step, scalar_int_mode *inner_mode,
+ enum iv_extend_code *extend, rtx *outer_step)
{
- *outer_mode = GET_MODE (reg);
-
- if (!get_biv_step_1 (last_def, reg,
- inner_step, inner_mode, extend, *outer_mode,
+ if (!get_biv_step_1 (last_def, outer_mode, reg,
+ inner_step, inner_mode, extend,
outer_step))
return false;
- gcc_assert ((*inner_mode == *outer_mode) != (*extend != IV_UNKNOWN_EXTEND));
- gcc_assert (*inner_mode != *outer_mode || *outer_step == const0_rtx);
+ gcc_assert ((*inner_mode == outer_mode) != (*extend != IV_UNKNOWN_EXTEND));
+ gcc_assert (*inner_mode != outer_mode || *outer_step == const0_rtx);
return true;
}
}
/* Determines whether DEF is a biv and if so, stores its description
- to *IV. */
+ to *IV. OUTER_MODE is the mode of DEF. */
static bool
-iv_analyze_biv (rtx def, struct rtx_iv *iv)
+iv_analyze_biv (scalar_int_mode outer_mode, rtx def, struct rtx_iv *iv)
{
rtx inner_step, outer_step;
- machine_mode inner_mode, outer_mode;
+ scalar_int_mode inner_mode;
enum iv_extend_code extend;
df_ref last_def;
if (!CONSTANT_P (def))
return false;
- return iv_constant (iv, def, VOIDmode);
+ return iv_constant (iv, outer_mode, def);
}
if (!latch_dominating_def (def, &last_def))
}
if (!last_def)
- return iv_constant (iv, def, VOIDmode);
+ return iv_constant (iv, outer_mode, def);
if (analyzed_for_bivness_p (def, iv))
{
return iv->base != NULL_RTX;
}
- if (!get_biv_step (last_def, def, &inner_step, &inner_mode, &extend,
- &outer_mode, &outer_step))
+ if (!get_biv_step (last_def, outer_mode, def, &inner_step, &inner_mode,
+ &extend, &outer_step))
{
iv->base = NULL_RTX;
goto end;
The mode of the induction variable is MODE. */
bool
-iv_analyze_expr (rtx_insn *insn, rtx rhs, machine_mode mode,
+iv_analyze_expr (rtx_insn *insn, scalar_int_mode mode, rtx rhs,
struct rtx_iv *iv)
{
rtx mby = NULL_RTX;
rtx op0 = NULL_RTX, op1 = NULL_RTX;
struct rtx_iv iv0, iv1;
enum rtx_code code = GET_CODE (rhs);
- machine_mode omode = mode;
+ scalar_int_mode omode = mode;
- iv->mode = VOIDmode;
iv->base = NULL_RTX;
iv->step = NULL_RTX;
if (CONSTANT_P (rhs)
|| REG_P (rhs)
|| code == SUBREG)
- {
- if (!iv_analyze_op (insn, rhs, iv))
- return false;
-
- if (iv->mode == VOIDmode)
- {
- iv->mode = mode;
- iv->extend_mode = mode;
- }
-
- return true;
- }
+ return iv_analyze_op (insn, mode, rhs, iv);
switch (code)
{
case ZERO_EXTEND:
case NEG:
op0 = XEXP (rhs, 0);
- omode = GET_MODE (op0);
+ /* We don't know how many bits there are in a sign-extended constant. */
+ if (!is_a <scalar_int_mode> (GET_MODE (op0), &omode))
+ return false;
break;
case PLUS:
}
if (op0
- && !iv_analyze_expr (insn, op0, omode, &iv0))
+ && !iv_analyze_expr (insn, omode, op0, &iv0))
return false;
if (op1
- && !iv_analyze_expr (insn, op1, omode, &iv1))
+ && !iv_analyze_expr (insn, omode, op1, &iv1))
return false;
switch (code)
return iv->base != NULL_RTX;
}
- iv->mode = VOIDmode;
iv->base = NULL_RTX;
iv->step = NULL_RTX;
- if (!REG_P (reg))
+ scalar_int_mode mode;
+ if (!REG_P (reg) || !is_a <scalar_int_mode> (GET_MODE (reg), &mode))
return false;
set = single_set (insn);
else
rhs = SET_SRC (set);
- iv_analyze_expr (insn, rhs, GET_MODE (reg), iv);
+ iv_analyze_expr (insn, mode, rhs, iv);
record_iv (def, iv);
if (dump_file)
return iv->base != NULL_RTX;
}
-/* Analyzes operand OP of INSN and stores the result to *IV. */
+/* Analyzes operand OP of INSN and stores the result to *IV. MODE is the
+ mode of OP. */
static bool
-iv_analyze_op (rtx_insn *insn, rtx op, struct rtx_iv *iv)
+iv_analyze_op (rtx_insn *insn, scalar_int_mode mode, rtx op, struct rtx_iv *iv)
{
df_ref def = NULL;
enum iv_grd_result res;
res = GRD_INVARIANT;
else if (GET_CODE (op) == SUBREG)
{
- if (!subreg_lowpart_p (op))
+ scalar_int_mode inner_mode;
+ if (!subreg_lowpart_p (op)
+ || !is_a <scalar_int_mode> (GET_MODE (SUBREG_REG (op)), &inner_mode))
return false;
- if (!iv_analyze_op (insn, SUBREG_REG (op), iv))
+ if (!iv_analyze_op (insn, inner_mode, SUBREG_REG (op), iv))
return false;
- return iv_subreg (iv, GET_MODE (op));
+ return iv_subreg (iv, mode);
}
else
{
if (res == GRD_INVARIANT)
{
- iv_constant (iv, op, VOIDmode);
+ iv_constant (iv, mode, op);
if (dump_file)
{
}
if (res == GRD_MAYBE_BIV)
- return iv_analyze_biv (op, iv);
+ return iv_analyze_biv (mode, op, iv);
return iv_analyze_def (def, iv);
}
-/* Analyzes value VAL at INSN and stores the result to *IV. */
+/* Analyzes value VAL at INSN and stores the result to *IV. MODE is the
+ mode of VAL. */
bool
-iv_analyze (rtx_insn *insn, rtx val, struct rtx_iv *iv)
+iv_analyze (rtx_insn *insn, scalar_int_mode mode, rtx val, struct rtx_iv *iv)
{
rtx reg;
insn = NEXT_INSN (insn);
}
- return iv_analyze_op (insn, val, iv);
+ return iv_analyze_op (insn, mode, val, iv);
}
/* Analyzes definition of DEF in INSN and stores the result to IV. */
}
/* Checks whether definition of register REG in INSN is a basic induction
- variable. IV analysis must have been initialized (via a call to
+ variable. MODE is the mode of REG.
+
+ IV analysis must have been initialized (via a call to
iv_analysis_loop_init) for this function to produce a result. */
bool
-biv_p (rtx_insn *insn, rtx reg)
+biv_p (rtx_insn *insn, scalar_int_mode mode, rtx reg)
{
struct rtx_iv iv;
df_ref def, last_def;
if (last_def != def)
return false;
- if (!iv_analyze_biv (reg, &iv))
+ if (!iv_analyze_biv (mode, reg, &iv))
return false;
return iv.step != const0_rtx;
&& CONST_INT_P (XEXP (opb0, 1))
/* Avoid overflows. */
&& ((unsigned HOST_WIDE_INT) INTVAL (XEXP (opb0, 1))
- != ((unsigned HOST_WIDE_INT) 1 << (HOST_BITS_PER_WIDE_INT - 1)))
+ != (HOST_WIDE_INT_1U << (HOST_BITS_PER_WIDE_INT - 1)))
&& rtx_equal_p (XEXP (opb0, 0), op0))
return INTVAL (op1) == -INTVAL (XEXP (opb0, 1));
if (GET_CODE (b) == GEU
&& CONST_INT_P (XEXP (opb0, 1))
/* Avoid overflows. */
&& ((unsigned HOST_WIDE_INT) INTVAL (XEXP (opb0, 1))
- != ((unsigned HOST_WIDE_INT) 1 << (HOST_BITS_PER_WIDE_INT - 1)))
+ != (HOST_WIDE_INT_1U << (HOST_BITS_PER_WIDE_INT - 1)))
&& rtx_equal_p (XEXP (opb0, 0), op0))
return INTVAL (op1) == -INTVAL (XEXP (opb0, 1));
}
for (pnote = &cond_list; *pnote; pnote = pnote_next)
{
- rtx note = *pnote;
+ rtx_expr_list *note = *pnote;
rtx old_cond = XEXP (note, 0);
pnote_next = (rtx_expr_list **)&XEXP (note, 1);
/* Likewise for the conditions. */
for (pnote = &cond_list; *pnote; pnote = pnote_next)
{
- rtx note = *pnote;
+ rtx_expr_list *note = *pnote;
rtx old_cond = XEXP (note, 0);
pnote_next = (rtx_expr_list **)&XEXP (note, 1);
is SIGNED_P to DESC. */
static void
-shorten_into_mode (struct rtx_iv *iv, machine_mode mode,
+shorten_into_mode (struct rtx_iv *iv, scalar_int_mode mode,
enum rtx_code cond, bool signed_p, struct niter_desc *desc)
{
rtx mmin, mmax, cond_over, cond_under;
canonicalize_iv_subregs (struct rtx_iv *iv0, struct rtx_iv *iv1,
enum rtx_code cond, struct niter_desc *desc)
{
- machine_mode comp_mode;
+ scalar_int_mode comp_mode;
bool signed_p;
/* If the ivs behave specially in the first iteration, or are
struct niter_desc *desc)
{
rtx op0, op1, delta, step, bound, may_xform, tmp, tmp0, tmp1;
- struct rtx_iv iv0, iv1, tmp_iv;
+ struct rtx_iv iv0, iv1;
rtx assumption, may_not_xform;
enum rtx_code cond;
- machine_mode mode, comp_mode;
+ machine_mode nonvoid_mode;
+ scalar_int_mode comp_mode;
rtx mmin, mmax, mode_mmin, mode_mmax;
- uint64_t s, size, d, inv, max;
- int64_t up, down, inc, step_val;
+ uint64_t s, size, d, inv, max, up, down;
+ int64_t inc, step_val;
int was_sharp = false;
rtx old_niter;
bool step_is_pow2;
cond = GET_CODE (condition);
gcc_assert (COMPARISON_P (condition));
- mode = GET_MODE (XEXP (condition, 0));
- if (mode == VOIDmode)
- mode = GET_MODE (XEXP (condition, 1));
+ nonvoid_mode = GET_MODE (XEXP (condition, 0));
+ if (nonvoid_mode == VOIDmode)
+ nonvoid_mode = GET_MODE (XEXP (condition, 1));
/* The constant comparisons should be folded. */
- gcc_assert (mode != VOIDmode);
+ gcc_assert (nonvoid_mode != VOIDmode);
/* We only handle integers or pointers. */
- if (GET_MODE_CLASS (mode) != MODE_INT
- && GET_MODE_CLASS (mode) != MODE_PARTIAL_INT)
+ scalar_int_mode mode;
+ if (!is_a <scalar_int_mode> (nonvoid_mode, &mode))
goto fail;
op0 = XEXP (condition, 0);
- if (!iv_analyze (insn, op0, &iv0))
+ if (!iv_analyze (insn, mode, op0, &iv0))
goto fail;
- if (iv0.extend_mode == VOIDmode)
- iv0.mode = iv0.extend_mode = mode;
op1 = XEXP (condition, 1);
- if (!iv_analyze (insn, op1, &iv1))
+ if (!iv_analyze (insn, mode, op1, &iv1))
goto fail;
- if (iv1.extend_mode == VOIDmode)
- iv1.mode = iv1.extend_mode = mode;
if (GET_MODE_BITSIZE (iv0.extend_mode) > HOST_BITS_PER_WIDE_INT
|| GET_MODE_BITSIZE (iv1.extend_mode) > HOST_BITS_PER_WIDE_INT)
case GT:
case GEU:
case GTU:
- tmp_iv = iv0; iv0 = iv1; iv1 = tmp_iv;
+ std::swap (iv0, iv1);
cond = swap_condition (cond);
break;
case NE:
down = INTVAL (CONST_INT_P (iv0.base)
? iv0.base
: mode_mmin);
- max = (uint64_t) (up - down) / inc + 1;
+ max = (up - down) / inc + 1;
if (!desc->infinite
&& !desc->assumptions)
record_niter_bound (loop, max, false, true);
fprintf (dump_file, " upper bound: %li\n",
(long)get_max_loop_iterations_int (loop));
+ fprintf (dump_file, " likely upper bound: %li\n",
+ (long)get_likely_max_loop_iterations_int (loop));
fprintf (dump_file, " realistic bound: %li\n",
(long)get_estimated_loop_iterations_int (loop));
}
iv_analysis_loop_init (loop);
find_simple_exit (loop, desc);
loop->simple_loop_desc = desc;
-
- if (desc->simple_p && (desc->assumptions || desc->infinite))
- {
- const char *wording;
-
- /* Assume that no overflow happens and that the loop is finite.
- We already warned at the tree level if we ran optimizations there. */
- if (!flag_tree_loop_optimize && warn_unsafe_loop_optimizations)
- {
- if (desc->infinite)
- {
- wording =
- flag_unsafe_loop_optimizations
- ? N_("assuming that the loop is not infinite")
- : N_("cannot optimize possibly infinite loops");
- warning (OPT_Wunsafe_loop_optimizations, "%s",
- gettext (wording));
- }
- if (desc->assumptions)
- {
- wording =
- flag_unsafe_loop_optimizations
- ? N_("assuming that the loop counter does not overflow")
- : N_("cannot optimize loop, the loop counter may overflow");
- warning (OPT_Wunsafe_loop_optimizations, "%s",
- gettext (wording));
- }
- }
-
- if (flag_unsafe_loop_optimizations)
- {
- desc->assumptions = NULL_RTX;
- desc->infinite = NULL_RTX;
- }
- }
-
return desc;
}
projects / thirdparty / gcc.git / blobdiff