/* Functions to determine/estimate number of iterations of a loop.
|
/* Functions to determine/estimate number of iterations of a loop.
|
Copyright (C) 2004, 2005, 2006, 2007 Free Software Foundation, Inc.
|
Copyright (C) 2004, 2005, 2006, 2007 Free Software Foundation, Inc.
|
|
|
This file is part of GCC.
|
This file is part of GCC.
|
|
|
GCC is free software; you can redistribute it and/or modify it
|
GCC is free software; you can redistribute it and/or modify it
|
under the terms of the GNU General Public License as published by the
|
under the terms of the GNU General Public License as published by the
|
Free Software Foundation; either version 3, or (at your option) any
|
Free Software Foundation; either version 3, or (at your option) any
|
later version.
|
later version.
|
|
|
GCC is distributed in the hope that it will be useful, but WITHOUT
|
GCC is distributed in the hope that it will be useful, but WITHOUT
|
ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
|
ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
|
FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
|
FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
|
for more details.
|
for more details.
|
|
|
You should have received a copy of the GNU General Public License
|
You should have received a copy of the GNU General Public License
|
along with GCC; see the file COPYING3. If not see
|
along with GCC; see the file COPYING3. If not see
|
<http://www.gnu.org/licenses/>. */
|
<http://www.gnu.org/licenses/>. */
|
|
|
#include "config.h"
|
#include "config.h"
|
#include "system.h"
|
#include "system.h"
|
#include "coretypes.h"
|
#include "coretypes.h"
|
#include "tm.h"
|
#include "tm.h"
|
#include "tree.h"
|
#include "tree.h"
|
#include "rtl.h"
|
#include "rtl.h"
|
#include "tm_p.h"
|
#include "tm_p.h"
|
#include "hard-reg-set.h"
|
#include "hard-reg-set.h"
|
#include "basic-block.h"
|
#include "basic-block.h"
|
#include "output.h"
|
#include "output.h"
|
#include "diagnostic.h"
|
#include "diagnostic.h"
|
#include "intl.h"
|
#include "intl.h"
|
#include "tree-flow.h"
|
#include "tree-flow.h"
|
#include "tree-dump.h"
|
#include "tree-dump.h"
|
#include "cfgloop.h"
|
#include "cfgloop.h"
|
#include "tree-pass.h"
|
#include "tree-pass.h"
|
#include "ggc.h"
|
#include "ggc.h"
|
#include "tree-chrec.h"
|
#include "tree-chrec.h"
|
#include "tree-scalar-evolution.h"
|
#include "tree-scalar-evolution.h"
|
#include "tree-data-ref.h"
|
#include "tree-data-ref.h"
|
#include "params.h"
|
#include "params.h"
|
#include "flags.h"
|
#include "flags.h"
|
#include "toplev.h"
|
#include "toplev.h"
|
#include "tree-inline.h"
|
#include "tree-inline.h"
|
|
|
#define SWAP(X, Y) do { void *tmp = (X); (X) = (Y); (Y) = tmp; } while (0)
|
#define SWAP(X, Y) do { void *tmp = (X); (X) = (Y); (Y) = tmp; } while (0)
|
|
|
|
|
/*
|
/*
|
|
|
Analysis of number of iterations of an affine exit test.
|
Analysis of number of iterations of an affine exit test.
|
|
|
*/
|
*/
|
|
|
/* Returns true if ARG is either NULL_TREE or constant zero. Unlike
|
/* Returns true if ARG is either NULL_TREE or constant zero. Unlike
|
integer_zerop, it does not care about overflow flags. */
|
integer_zerop, it does not care about overflow flags. */
|
|
|
bool
|
bool
|
zero_p (tree arg)
|
zero_p (tree arg)
|
{
|
{
|
if (!arg)
|
if (!arg)
|
return true;
|
return true;
|
|
|
if (TREE_CODE (arg) != INTEGER_CST)
|
if (TREE_CODE (arg) != INTEGER_CST)
|
return false;
|
return false;
|
|
|
return (TREE_INT_CST_LOW (arg) == 0 && TREE_INT_CST_HIGH (arg) == 0);
|
return (TREE_INT_CST_LOW (arg) == 0 && TREE_INT_CST_HIGH (arg) == 0);
|
}
|
}
|
|
|
/* Returns true if ARG a nonzero constant. Unlike integer_nonzerop, it does
|
/* Returns true if ARG a nonzero constant. Unlike integer_nonzerop, it does
|
not care about overflow flags. */
|
not care about overflow flags. */
|
|
|
static bool
|
static bool
|
nonzero_p (tree arg)
|
nonzero_p (tree arg)
|
{
|
{
|
if (!arg)
|
if (!arg)
|
return false;
|
return false;
|
|
|
if (TREE_CODE (arg) != INTEGER_CST)
|
if (TREE_CODE (arg) != INTEGER_CST)
|
return false;
|
return false;
|
|
|
return (TREE_INT_CST_LOW (arg) != 0 || TREE_INT_CST_HIGH (arg) != 0);
|
return (TREE_INT_CST_LOW (arg) != 0 || TREE_INT_CST_HIGH (arg) != 0);
|
}
|
}
|
|
|
/* Returns inverse of X modulo 2^s, where MASK = 2^s-1. */
|
/* Returns inverse of X modulo 2^s, where MASK = 2^s-1. */
|
|
|
static tree
|
static tree
|
inverse (tree x, tree mask)
|
inverse (tree x, tree mask)
|
{
|
{
|
tree type = TREE_TYPE (x);
|
tree type = TREE_TYPE (x);
|
tree rslt;
|
tree rslt;
|
unsigned ctr = tree_floor_log2 (mask);
|
unsigned ctr = tree_floor_log2 (mask);
|
|
|
if (TYPE_PRECISION (type) <= HOST_BITS_PER_WIDE_INT)
|
if (TYPE_PRECISION (type) <= HOST_BITS_PER_WIDE_INT)
|
{
|
{
|
unsigned HOST_WIDE_INT ix;
|
unsigned HOST_WIDE_INT ix;
|
unsigned HOST_WIDE_INT imask;
|
unsigned HOST_WIDE_INT imask;
|
unsigned HOST_WIDE_INT irslt = 1;
|
unsigned HOST_WIDE_INT irslt = 1;
|
|
|
gcc_assert (cst_and_fits_in_hwi (x));
|
gcc_assert (cst_and_fits_in_hwi (x));
|
gcc_assert (cst_and_fits_in_hwi (mask));
|
gcc_assert (cst_and_fits_in_hwi (mask));
|
|
|
ix = int_cst_value (x);
|
ix = int_cst_value (x);
|
imask = int_cst_value (mask);
|
imask = int_cst_value (mask);
|
|
|
for (; ctr; ctr--)
|
for (; ctr; ctr--)
|
{
|
{
|
irslt *= ix;
|
irslt *= ix;
|
ix *= ix;
|
ix *= ix;
|
}
|
}
|
irslt &= imask;
|
irslt &= imask;
|
|
|
rslt = build_int_cst_type (type, irslt);
|
rslt = build_int_cst_type (type, irslt);
|
}
|
}
|
else
|
else
|
{
|
{
|
rslt = build_int_cst (type, 1);
|
rslt = build_int_cst (type, 1);
|
for (; ctr; ctr--)
|
for (; ctr; ctr--)
|
{
|
{
|
rslt = int_const_binop (MULT_EXPR, rslt, x, 0);
|
rslt = int_const_binop (MULT_EXPR, rslt, x, 0);
|
x = int_const_binop (MULT_EXPR, x, x, 0);
|
x = int_const_binop (MULT_EXPR, x, x, 0);
|
}
|
}
|
rslt = int_const_binop (BIT_AND_EXPR, rslt, mask, 0);
|
rslt = int_const_binop (BIT_AND_EXPR, rslt, mask, 0);
|
}
|
}
|
|
|
return rslt;
|
return rslt;
|
}
|
}
|
|
|
/* Determines number of iterations of loop whose ending condition
|
/* Determines number of iterations of loop whose ending condition
|
is IV <> FINAL. TYPE is the type of the iv. The number of
|
is IV <> FINAL. TYPE is the type of the iv. The number of
|
iterations is stored to NITER. NEVER_INFINITE is true if
|
iterations is stored to NITER. NEVER_INFINITE is true if
|
we know that the exit must be taken eventually, i.e., that the IV
|
we know that the exit must be taken eventually, i.e., that the IV
|
ever reaches the value FINAL (we derived this earlier, and possibly set
|
ever reaches the value FINAL (we derived this earlier, and possibly set
|
NITER->assumptions to make sure this is the case). */
|
NITER->assumptions to make sure this is the case). */
|
|
|
static bool
|
static bool
|
number_of_iterations_ne (tree type, affine_iv *iv, tree final,
|
number_of_iterations_ne (tree type, affine_iv *iv, tree final,
|
struct tree_niter_desc *niter, bool never_infinite)
|
struct tree_niter_desc *niter, bool never_infinite)
|
{
|
{
|
tree niter_type = unsigned_type_for (type);
|
tree niter_type = unsigned_type_for (type);
|
tree s, c, d, bits, assumption, tmp, bound;
|
tree s, c, d, bits, assumption, tmp, bound;
|
|
|
niter->control = *iv;
|
niter->control = *iv;
|
niter->bound = final;
|
niter->bound = final;
|
niter->cmp = NE_EXPR;
|
niter->cmp = NE_EXPR;
|
|
|
/* Rearrange the terms so that we get inequality s * i <> c, with s
|
/* Rearrange the terms so that we get inequality s * i <> c, with s
|
positive. Also cast everything to the unsigned type. */
|
positive. Also cast everything to the unsigned type. */
|
if (tree_int_cst_sign_bit (iv->step))
|
if (tree_int_cst_sign_bit (iv->step))
|
{
|
{
|
s = fold_convert (niter_type,
|
s = fold_convert (niter_type,
|
fold_build1 (NEGATE_EXPR, type, iv->step));
|
fold_build1 (NEGATE_EXPR, type, iv->step));
|
c = fold_build2 (MINUS_EXPR, niter_type,
|
c = fold_build2 (MINUS_EXPR, niter_type,
|
fold_convert (niter_type, iv->base),
|
fold_convert (niter_type, iv->base),
|
fold_convert (niter_type, final));
|
fold_convert (niter_type, final));
|
}
|
}
|
else
|
else
|
{
|
{
|
s = fold_convert (niter_type, iv->step);
|
s = fold_convert (niter_type, iv->step);
|
c = fold_build2 (MINUS_EXPR, niter_type,
|
c = fold_build2 (MINUS_EXPR, niter_type,
|
fold_convert (niter_type, final),
|
fold_convert (niter_type, final),
|
fold_convert (niter_type, iv->base));
|
fold_convert (niter_type, iv->base));
|
}
|
}
|
|
|
/* First the trivial cases -- when the step is 1. */
|
/* First the trivial cases -- when the step is 1. */
|
if (integer_onep (s))
|
if (integer_onep (s))
|
{
|
{
|
niter->niter = c;
|
niter->niter = c;
|
return true;
|
return true;
|
}
|
}
|
|
|
/* Let nsd (step, size of mode) = d. If d does not divide c, the loop
|
/* Let nsd (step, size of mode) = d. If d does not divide c, the loop
|
is infinite. Otherwise, the number of iterations is
|
is infinite. Otherwise, the number of iterations is
|
(inverse(s/d) * (c/d)) mod (size of mode/d). */
|
(inverse(s/d) * (c/d)) mod (size of mode/d). */
|
bits = num_ending_zeros (s);
|
bits = num_ending_zeros (s);
|
bound = build_low_bits_mask (niter_type,
|
bound = build_low_bits_mask (niter_type,
|
(TYPE_PRECISION (niter_type)
|
(TYPE_PRECISION (niter_type)
|
- tree_low_cst (bits, 1)));
|
- tree_low_cst (bits, 1)));
|
|
|
d = fold_binary_to_constant (LSHIFT_EXPR, niter_type,
|
d = fold_binary_to_constant (LSHIFT_EXPR, niter_type,
|
build_int_cst (niter_type, 1), bits);
|
build_int_cst (niter_type, 1), bits);
|
s = fold_binary_to_constant (RSHIFT_EXPR, niter_type, s, bits);
|
s = fold_binary_to_constant (RSHIFT_EXPR, niter_type, s, bits);
|
|
|
if (!never_infinite)
|
if (!never_infinite)
|
{
|
{
|
/* If we cannot assume that the loop is not infinite, record the
|
/* If we cannot assume that the loop is not infinite, record the
|
assumptions for divisibility of c. */
|
assumptions for divisibility of c. */
|
assumption = fold_build2 (FLOOR_MOD_EXPR, niter_type, c, d);
|
assumption = fold_build2 (FLOOR_MOD_EXPR, niter_type, c, d);
|
assumption = fold_build2 (EQ_EXPR, boolean_type_node,
|
assumption = fold_build2 (EQ_EXPR, boolean_type_node,
|
assumption, build_int_cst (niter_type, 0));
|
assumption, build_int_cst (niter_type, 0));
|
if (!nonzero_p (assumption))
|
if (!nonzero_p (assumption))
|
niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
|
niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
|
niter->assumptions, assumption);
|
niter->assumptions, assumption);
|
}
|
}
|
|
|
c = fold_build2 (EXACT_DIV_EXPR, niter_type, c, d);
|
c = fold_build2 (EXACT_DIV_EXPR, niter_type, c, d);
|
tmp = fold_build2 (MULT_EXPR, niter_type, c, inverse (s, bound));
|
tmp = fold_build2 (MULT_EXPR, niter_type, c, inverse (s, bound));
|
niter->niter = fold_build2 (BIT_AND_EXPR, niter_type, tmp, bound);
|
niter->niter = fold_build2 (BIT_AND_EXPR, niter_type, tmp, bound);
|
return true;
|
return true;
|
}
|
}
|
|
|
/* Checks whether we can determine the final value of the control variable
|
/* Checks whether we can determine the final value of the control variable
|
of the loop with ending condition IV0 < IV1 (computed in TYPE).
|
of the loop with ending condition IV0 < IV1 (computed in TYPE).
|
DELTA is the difference IV1->base - IV0->base, STEP is the absolute value
|
DELTA is the difference IV1->base - IV0->base, STEP is the absolute value
|
of the step. The assumptions necessary to ensure that the computation
|
of the step. The assumptions necessary to ensure that the computation
|
of the final value does not overflow are recorded in NITER. If we
|
of the final value does not overflow are recorded in NITER. If we
|
find the final value, we adjust DELTA and return TRUE. Otherwise
|
find the final value, we adjust DELTA and return TRUE. Otherwise
|
we return false. */
|
we return false. */
|
|
|
static bool
|
static bool
|
number_of_iterations_lt_to_ne (tree type, affine_iv *iv0, affine_iv *iv1,
|
number_of_iterations_lt_to_ne (tree type, affine_iv *iv0, affine_iv *iv1,
|
struct tree_niter_desc *niter,
|
struct tree_niter_desc *niter,
|
tree *delta, tree step)
|
tree *delta, tree step)
|
{
|
{
|
tree niter_type = TREE_TYPE (step);
|
tree niter_type = TREE_TYPE (step);
|
tree mod = fold_build2 (FLOOR_MOD_EXPR, niter_type, *delta, step);
|
tree mod = fold_build2 (FLOOR_MOD_EXPR, niter_type, *delta, step);
|
tree tmod;
|
tree tmod;
|
tree assumption = boolean_true_node, bound, noloop;
|
tree assumption = boolean_true_node, bound, noloop;
|
|
|
if (TREE_CODE (mod) != INTEGER_CST)
|
if (TREE_CODE (mod) != INTEGER_CST)
|
return false;
|
return false;
|
if (nonzero_p (mod))
|
if (nonzero_p (mod))
|
mod = fold_build2 (MINUS_EXPR, niter_type, step, mod);
|
mod = fold_build2 (MINUS_EXPR, niter_type, step, mod);
|
tmod = fold_convert (type, mod);
|
tmod = fold_convert (type, mod);
|
|
|
if (nonzero_p (iv0->step))
|
if (nonzero_p (iv0->step))
|
{
|
{
|
/* The final value of the iv is iv1->base + MOD, assuming that this
|
/* The final value of the iv is iv1->base + MOD, assuming that this
|
computation does not overflow, and that
|
computation does not overflow, and that
|
iv0->base <= iv1->base + MOD. */
|
iv0->base <= iv1->base + MOD. */
|
if (!iv1->no_overflow && !zero_p (mod))
|
if (!iv1->no_overflow && !zero_p (mod))
|
{
|
{
|
bound = fold_build2 (MINUS_EXPR, type,
|
bound = fold_build2 (MINUS_EXPR, type,
|
TYPE_MAX_VALUE (type), tmod);
|
TYPE_MAX_VALUE (type), tmod);
|
assumption = fold_build2 (LE_EXPR, boolean_type_node,
|
assumption = fold_build2 (LE_EXPR, boolean_type_node,
|
iv1->base, bound);
|
iv1->base, bound);
|
if (zero_p (assumption))
|
if (zero_p (assumption))
|
return false;
|
return false;
|
}
|
}
|
noloop = fold_build2 (GT_EXPR, boolean_type_node,
|
noloop = fold_build2 (GT_EXPR, boolean_type_node,
|
iv0->base,
|
iv0->base,
|
fold_build2 (PLUS_EXPR, type,
|
fold_build2 (PLUS_EXPR, type,
|
iv1->base, tmod));
|
iv1->base, tmod));
|
}
|
}
|
else
|
else
|
{
|
{
|
/* The final value of the iv is iv0->base - MOD, assuming that this
|
/* The final value of the iv is iv0->base - MOD, assuming that this
|
computation does not overflow, and that
|
computation does not overflow, and that
|
iv0->base - MOD <= iv1->base. */
|
iv0->base - MOD <= iv1->base. */
|
if (!iv0->no_overflow && !zero_p (mod))
|
if (!iv0->no_overflow && !zero_p (mod))
|
{
|
{
|
bound = fold_build2 (PLUS_EXPR, type,
|
bound = fold_build2 (PLUS_EXPR, type,
|
TYPE_MIN_VALUE (type), tmod);
|
TYPE_MIN_VALUE (type), tmod);
|
assumption = fold_build2 (GE_EXPR, boolean_type_node,
|
assumption = fold_build2 (GE_EXPR, boolean_type_node,
|
iv0->base, bound);
|
iv0->base, bound);
|
if (zero_p (assumption))
|
if (zero_p (assumption))
|
return false;
|
return false;
|
}
|
}
|
noloop = fold_build2 (GT_EXPR, boolean_type_node,
|
noloop = fold_build2 (GT_EXPR, boolean_type_node,
|
fold_build2 (MINUS_EXPR, type,
|
fold_build2 (MINUS_EXPR, type,
|
iv0->base, tmod),
|
iv0->base, tmod),
|
iv1->base);
|
iv1->base);
|
}
|
}
|
|
|
if (!nonzero_p (assumption))
|
if (!nonzero_p (assumption))
|
niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
|
niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
|
niter->assumptions,
|
niter->assumptions,
|
assumption);
|
assumption);
|
if (!zero_p (noloop))
|
if (!zero_p (noloop))
|
niter->may_be_zero = fold_build2 (TRUTH_OR_EXPR, boolean_type_node,
|
niter->may_be_zero = fold_build2 (TRUTH_OR_EXPR, boolean_type_node,
|
niter->may_be_zero,
|
niter->may_be_zero,
|
noloop);
|
noloop);
|
*delta = fold_build2 (PLUS_EXPR, niter_type, *delta, mod);
|
*delta = fold_build2 (PLUS_EXPR, niter_type, *delta, mod);
|
return true;
|
return true;
|
}
|
}
|
|
|
/* Add assertions to NITER that ensure that the control variable of the loop
|
/* Add assertions to NITER that ensure that the control variable of the loop
|
with ending condition IV0 < IV1 does not overflow. Types of IV0 and IV1
|
with ending condition IV0 < IV1 does not overflow. Types of IV0 and IV1
|
are TYPE. Returns false if we can prove that there is an overflow, true
|
are TYPE. Returns false if we can prove that there is an overflow, true
|
otherwise. STEP is the absolute value of the step. */
|
otherwise. STEP is the absolute value of the step. */
|
|
|
static bool
|
static bool
|
assert_no_overflow_lt (tree type, affine_iv *iv0, affine_iv *iv1,
|
assert_no_overflow_lt (tree type, affine_iv *iv0, affine_iv *iv1,
|
struct tree_niter_desc *niter, tree step)
|
struct tree_niter_desc *niter, tree step)
|
{
|
{
|
tree bound, d, assumption, diff;
|
tree bound, d, assumption, diff;
|
tree niter_type = TREE_TYPE (step);
|
tree niter_type = TREE_TYPE (step);
|
|
|
if (nonzero_p (iv0->step))
|
if (nonzero_p (iv0->step))
|
{
|
{
|
/* for (i = iv0->base; i < iv1->base; i += iv0->step) */
|
/* for (i = iv0->base; i < iv1->base; i += iv0->step) */
|
if (iv0->no_overflow)
|
if (iv0->no_overflow)
|
return true;
|
return true;
|
|
|
/* If iv0->base is a constant, we can determine the last value before
|
/* If iv0->base is a constant, we can determine the last value before
|
overflow precisely; otherwise we conservatively assume
|
overflow precisely; otherwise we conservatively assume
|
MAX - STEP + 1. */
|
MAX - STEP + 1. */
|
|
|
if (TREE_CODE (iv0->base) == INTEGER_CST)
|
if (TREE_CODE (iv0->base) == INTEGER_CST)
|
{
|
{
|
d = fold_build2 (MINUS_EXPR, niter_type,
|
d = fold_build2 (MINUS_EXPR, niter_type,
|
fold_convert (niter_type, TYPE_MAX_VALUE (type)),
|
fold_convert (niter_type, TYPE_MAX_VALUE (type)),
|
fold_convert (niter_type, iv0->base));
|
fold_convert (niter_type, iv0->base));
|
diff = fold_build2 (FLOOR_MOD_EXPR, niter_type, d, step);
|
diff = fold_build2 (FLOOR_MOD_EXPR, niter_type, d, step);
|
}
|
}
|
else
|
else
|
diff = fold_build2 (MINUS_EXPR, niter_type, step,
|
diff = fold_build2 (MINUS_EXPR, niter_type, step,
|
build_int_cst (niter_type, 1));
|
build_int_cst (niter_type, 1));
|
bound = fold_build2 (MINUS_EXPR, type,
|
bound = fold_build2 (MINUS_EXPR, type,
|
TYPE_MAX_VALUE (type), fold_convert (type, diff));
|
TYPE_MAX_VALUE (type), fold_convert (type, diff));
|
assumption = fold_build2 (LE_EXPR, boolean_type_node,
|
assumption = fold_build2 (LE_EXPR, boolean_type_node,
|
iv1->base, bound);
|
iv1->base, bound);
|
}
|
}
|
else
|
else
|
{
|
{
|
/* for (i = iv1->base; i > iv0->base; i += iv1->step) */
|
/* for (i = iv1->base; i > iv0->base; i += iv1->step) */
|
if (iv1->no_overflow)
|
if (iv1->no_overflow)
|
return true;
|
return true;
|
|
|
if (TREE_CODE (iv1->base) == INTEGER_CST)
|
if (TREE_CODE (iv1->base) == INTEGER_CST)
|
{
|
{
|
d = fold_build2 (MINUS_EXPR, niter_type,
|
d = fold_build2 (MINUS_EXPR, niter_type,
|
fold_convert (niter_type, iv1->base),
|
fold_convert (niter_type, iv1->base),
|
fold_convert (niter_type, TYPE_MIN_VALUE (type)));
|
fold_convert (niter_type, TYPE_MIN_VALUE (type)));
|
diff = fold_build2 (FLOOR_MOD_EXPR, niter_type, d, step);
|
diff = fold_build2 (FLOOR_MOD_EXPR, niter_type, d, step);
|
}
|
}
|
else
|
else
|
diff = fold_build2 (MINUS_EXPR, niter_type, step,
|
diff = fold_build2 (MINUS_EXPR, niter_type, step,
|
build_int_cst (niter_type, 1));
|
build_int_cst (niter_type, 1));
|
bound = fold_build2 (PLUS_EXPR, type,
|
bound = fold_build2 (PLUS_EXPR, type,
|
TYPE_MIN_VALUE (type), fold_convert (type, diff));
|
TYPE_MIN_VALUE (type), fold_convert (type, diff));
|
assumption = fold_build2 (GE_EXPR, boolean_type_node,
|
assumption = fold_build2 (GE_EXPR, boolean_type_node,
|
iv0->base, bound);
|
iv0->base, bound);
|
}
|
}
|
|
|
if (zero_p (assumption))
|
if (zero_p (assumption))
|
return false;
|
return false;
|
if (!nonzero_p (assumption))
|
if (!nonzero_p (assumption))
|
niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
|
niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
|
niter->assumptions, assumption);
|
niter->assumptions, assumption);
|
|
|
iv0->no_overflow = true;
|
iv0->no_overflow = true;
|
iv1->no_overflow = true;
|
iv1->no_overflow = true;
|
return true;
|
return true;
|
}
|
}
|
|
|
/* Add an assumption to NITER that a loop whose ending condition
|
/* Add an assumption to NITER that a loop whose ending condition
|
is IV0 < IV1 rolls. TYPE is the type of the control iv. */
|
is IV0 < IV1 rolls. TYPE is the type of the control iv. */
|
|
|
static void
|
static void
|
assert_loop_rolls_lt (tree type, affine_iv *iv0, affine_iv *iv1,
|
assert_loop_rolls_lt (tree type, affine_iv *iv0, affine_iv *iv1,
|
struct tree_niter_desc *niter)
|
struct tree_niter_desc *niter)
|
{
|
{
|
tree assumption = boolean_true_node, bound, diff;
|
tree assumption = boolean_true_node, bound, diff;
|
tree mbz, mbzl, mbzr;
|
tree mbz, mbzl, mbzr;
|
|
|
if (nonzero_p (iv0->step))
|
if (nonzero_p (iv0->step))
|
{
|
{
|
diff = fold_build2 (MINUS_EXPR, type,
|
diff = fold_build2 (MINUS_EXPR, type,
|
iv0->step, build_int_cst (type, 1));
|
iv0->step, build_int_cst (type, 1));
|
|
|
/* We need to know that iv0->base >= MIN + iv0->step - 1. Since
|
/* We need to know that iv0->base >= MIN + iv0->step - 1. Since
|
0 address never belongs to any object, we can assume this for
|
0 address never belongs to any object, we can assume this for
|
pointers. */
|
pointers. */
|
if (!POINTER_TYPE_P (type))
|
if (!POINTER_TYPE_P (type))
|
{
|
{
|
bound = fold_build2 (PLUS_EXPR, type,
|
bound = fold_build2 (PLUS_EXPR, type,
|
TYPE_MIN_VALUE (type), diff);
|
TYPE_MIN_VALUE (type), diff);
|
assumption = fold_build2 (GE_EXPR, boolean_type_node,
|
assumption = fold_build2 (GE_EXPR, boolean_type_node,
|
iv0->base, bound);
|
iv0->base, bound);
|
}
|
}
|
|
|
/* And then we can compute iv0->base - diff, and compare it with
|
/* And then we can compute iv0->base - diff, and compare it with
|
iv1->base. */
|
iv1->base. */
|
mbzl = fold_build2 (MINUS_EXPR, type, iv0->base, diff);
|
mbzl = fold_build2 (MINUS_EXPR, type, iv0->base, diff);
|
mbzr = iv1->base;
|
mbzr = iv1->base;
|
}
|
}
|
else
|
else
|
{
|
{
|
diff = fold_build2 (PLUS_EXPR, type,
|
diff = fold_build2 (PLUS_EXPR, type,
|
iv1->step, build_int_cst (type, 1));
|
iv1->step, build_int_cst (type, 1));
|
|
|
if (!POINTER_TYPE_P (type))
|
if (!POINTER_TYPE_P (type))
|
{
|
{
|
bound = fold_build2 (PLUS_EXPR, type,
|
bound = fold_build2 (PLUS_EXPR, type,
|
TYPE_MAX_VALUE (type), diff);
|
TYPE_MAX_VALUE (type), diff);
|
assumption = fold_build2 (LE_EXPR, boolean_type_node,
|
assumption = fold_build2 (LE_EXPR, boolean_type_node,
|
iv1->base, bound);
|
iv1->base, bound);
|
}
|
}
|
|
|
mbzl = iv0->base;
|
mbzl = iv0->base;
|
mbzr = fold_build2 (MINUS_EXPR, type, iv1->base, diff);
|
mbzr = fold_build2 (MINUS_EXPR, type, iv1->base, diff);
|
}
|
}
|
|
|
mbz = fold_build2 (GT_EXPR, boolean_type_node, mbzl, mbzr);
|
mbz = fold_build2 (GT_EXPR, boolean_type_node, mbzl, mbzr);
|
|
|
if (!nonzero_p (assumption))
|
if (!nonzero_p (assumption))
|
niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
|
niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
|
niter->assumptions, assumption);
|
niter->assumptions, assumption);
|
if (!zero_p (mbz))
|
if (!zero_p (mbz))
|
niter->may_be_zero = fold_build2 (TRUTH_OR_EXPR, boolean_type_node,
|
niter->may_be_zero = fold_build2 (TRUTH_OR_EXPR, boolean_type_node,
|
niter->may_be_zero, mbz);
|
niter->may_be_zero, mbz);
|
}
|
}
|
|
|
/* Determines number of iterations of loop whose ending condition
|
/* Determines number of iterations of loop whose ending condition
|
is IV0 < IV1. TYPE is the type of the iv. The number of
|
is IV0 < IV1. TYPE is the type of the iv. The number of
|
iterations is stored to NITER. */
|
iterations is stored to NITER. */
|
|
|
static bool
|
static bool
|
number_of_iterations_lt (tree type, affine_iv *iv0, affine_iv *iv1,
|
number_of_iterations_lt (tree type, affine_iv *iv0, affine_iv *iv1,
|
struct tree_niter_desc *niter,
|
struct tree_niter_desc *niter,
|
bool never_infinite ATTRIBUTE_UNUSED)
|
bool never_infinite ATTRIBUTE_UNUSED)
|
{
|
{
|
tree niter_type = unsigned_type_for (type);
|
tree niter_type = unsigned_type_for (type);
|
tree delta, step, s;
|
tree delta, step, s;
|
|
|
if (nonzero_p (iv0->step))
|
if (nonzero_p (iv0->step))
|
{
|
{
|
niter->control = *iv0;
|
niter->control = *iv0;
|
niter->cmp = LT_EXPR;
|
niter->cmp = LT_EXPR;
|
niter->bound = iv1->base;
|
niter->bound = iv1->base;
|
}
|
}
|
else
|
else
|
{
|
{
|
niter->control = *iv1;
|
niter->control = *iv1;
|
niter->cmp = GT_EXPR;
|
niter->cmp = GT_EXPR;
|
niter->bound = iv0->base;
|
niter->bound = iv0->base;
|
}
|
}
|
|
|
delta = fold_build2 (MINUS_EXPR, niter_type,
|
delta = fold_build2 (MINUS_EXPR, niter_type,
|
fold_convert (niter_type, iv1->base),
|
fold_convert (niter_type, iv1->base),
|
fold_convert (niter_type, iv0->base));
|
fold_convert (niter_type, iv0->base));
|
|
|
/* First handle the special case that the step is +-1. */
|
/* First handle the special case that the step is +-1. */
|
if ((iv0->step && integer_onep (iv0->step)
|
if ((iv0->step && integer_onep (iv0->step)
|
&& zero_p (iv1->step))
|
&& zero_p (iv1->step))
|
|| (iv1->step && integer_all_onesp (iv1->step)
|
|| (iv1->step && integer_all_onesp (iv1->step)
|
&& zero_p (iv0->step)))
|
&& zero_p (iv0->step)))
|
{
|
{
|
/* for (i = iv0->base; i < iv1->base; i++)
|
/* for (i = iv0->base; i < iv1->base; i++)
|
|
|
or
|
or
|
|
|
for (i = iv1->base; i > iv0->base; i--).
|
for (i = iv1->base; i > iv0->base; i--).
|
|
|
In both cases # of iterations is iv1->base - iv0->base, assuming that
|
In both cases # of iterations is iv1->base - iv0->base, assuming that
|
iv1->base >= iv0->base. */
|
iv1->base >= iv0->base. */
|
niter->may_be_zero = fold_build2 (LT_EXPR, boolean_type_node,
|
niter->may_be_zero = fold_build2 (LT_EXPR, boolean_type_node,
|
iv1->base, iv0->base);
|
iv1->base, iv0->base);
|
niter->niter = delta;
|
niter->niter = delta;
|
return true;
|
return true;
|
}
|
}
|
|
|
if (nonzero_p (iv0->step))
|
if (nonzero_p (iv0->step))
|
step = fold_convert (niter_type, iv0->step);
|
step = fold_convert (niter_type, iv0->step);
|
else
|
else
|
step = fold_convert (niter_type,
|
step = fold_convert (niter_type,
|
fold_build1 (NEGATE_EXPR, type, iv1->step));
|
fold_build1 (NEGATE_EXPR, type, iv1->step));
|
|
|
/* If we can determine the final value of the control iv exactly, we can
|
/* If we can determine the final value of the control iv exactly, we can
|
transform the condition to != comparison. In particular, this will be
|
transform the condition to != comparison. In particular, this will be
|
the case if DELTA is constant. */
|
the case if DELTA is constant. */
|
if (number_of_iterations_lt_to_ne (type, iv0, iv1, niter, &delta, step))
|
if (number_of_iterations_lt_to_ne (type, iv0, iv1, niter, &delta, step))
|
{
|
{
|
affine_iv zps;
|
affine_iv zps;
|
|
|
zps.base = build_int_cst (niter_type, 0);
|
zps.base = build_int_cst (niter_type, 0);
|
zps.step = step;
|
zps.step = step;
|
/* number_of_iterations_lt_to_ne will add assumptions that ensure that
|
/* number_of_iterations_lt_to_ne will add assumptions that ensure that
|
zps does not overflow. */
|
zps does not overflow. */
|
zps.no_overflow = true;
|
zps.no_overflow = true;
|
|
|
return number_of_iterations_ne (type, &zps, delta, niter, true);
|
return number_of_iterations_ne (type, &zps, delta, niter, true);
|
}
|
}
|
|
|
/* Make sure that the control iv does not overflow. */
|
/* Make sure that the control iv does not overflow. */
|
if (!assert_no_overflow_lt (type, iv0, iv1, niter, step))
|
if (!assert_no_overflow_lt (type, iv0, iv1, niter, step))
|
return false;
|
return false;
|
|
|
/* We determine the number of iterations as (delta + step - 1) / step. For
|
/* We determine the number of iterations as (delta + step - 1) / step. For
|
this to work, we must know that iv1->base >= iv0->base - step + 1,
|
this to work, we must know that iv1->base >= iv0->base - step + 1,
|
otherwise the loop does not roll. */
|
otherwise the loop does not roll. */
|
assert_loop_rolls_lt (type, iv0, iv1, niter);
|
assert_loop_rolls_lt (type, iv0, iv1, niter);
|
|
|
s = fold_build2 (MINUS_EXPR, niter_type,
|
s = fold_build2 (MINUS_EXPR, niter_type,
|
step, build_int_cst (niter_type, 1));
|
step, build_int_cst (niter_type, 1));
|
delta = fold_build2 (PLUS_EXPR, niter_type, delta, s);
|
delta = fold_build2 (PLUS_EXPR, niter_type, delta, s);
|
niter->niter = fold_build2 (FLOOR_DIV_EXPR, niter_type, delta, step);
|
niter->niter = fold_build2 (FLOOR_DIV_EXPR, niter_type, delta, step);
|
return true;
|
return true;
|
}
|
}
|
|
|
/* Determines number of iterations of loop whose ending condition
|
/* Determines number of iterations of loop whose ending condition
|
is IV0 <= IV1. TYPE is the type of the iv. The number of
|
is IV0 <= IV1. TYPE is the type of the iv. The number of
|
iterations is stored to NITER. NEVER_INFINITE is true if
|
iterations is stored to NITER. NEVER_INFINITE is true if
|
we know that this condition must eventually become false (we derived this
|
we know that this condition must eventually become false (we derived this
|
earlier, and possibly set NITER->assumptions to make sure this
|
earlier, and possibly set NITER->assumptions to make sure this
|
is the case). */
|
is the case). */
|
|
|
static bool
|
static bool
|
number_of_iterations_le (tree type, affine_iv *iv0, affine_iv *iv1,
|
number_of_iterations_le (tree type, affine_iv *iv0, affine_iv *iv1,
|
struct tree_niter_desc *niter, bool never_infinite)
|
struct tree_niter_desc *niter, bool never_infinite)
|
{
|
{
|
tree assumption;
|
tree assumption;
|
|
|
/* Say that IV0 is the control variable. Then IV0 <= IV1 iff
|
/* Say that IV0 is the control variable. Then IV0 <= IV1 iff
|
IV0 < IV1 + 1, assuming that IV1 is not equal to the greatest
|
IV0 < IV1 + 1, assuming that IV1 is not equal to the greatest
|
value of the type. This we must know anyway, since if it is
|
value of the type. This we must know anyway, since if it is
|
equal to this value, the loop rolls forever. */
|
equal to this value, the loop rolls forever. */
|
|
|
if (!never_infinite)
|
if (!never_infinite)
|
{
|
{
|
if (nonzero_p (iv0->step))
|
if (nonzero_p (iv0->step))
|
assumption = fold_build2 (NE_EXPR, boolean_type_node,
|
assumption = fold_build2 (NE_EXPR, boolean_type_node,
|
iv1->base, TYPE_MAX_VALUE (type));
|
iv1->base, TYPE_MAX_VALUE (type));
|
else
|
else
|
assumption = fold_build2 (NE_EXPR, boolean_type_node,
|
assumption = fold_build2 (NE_EXPR, boolean_type_node,
|
iv0->base, TYPE_MIN_VALUE (type));
|
iv0->base, TYPE_MIN_VALUE (type));
|
|
|
if (zero_p (assumption))
|
if (zero_p (assumption))
|
return false;
|
return false;
|
if (!nonzero_p (assumption))
|
if (!nonzero_p (assumption))
|
niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
|
niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
|
niter->assumptions, assumption);
|
niter->assumptions, assumption);
|
}
|
}
|
|
|
if (nonzero_p (iv0->step))
|
if (nonzero_p (iv0->step))
|
iv1->base = fold_build2 (PLUS_EXPR, type,
|
iv1->base = fold_build2 (PLUS_EXPR, type,
|
iv1->base, build_int_cst (type, 1));
|
iv1->base, build_int_cst (type, 1));
|
else
|
else
|
iv0->base = fold_build2 (MINUS_EXPR, type,
|
iv0->base = fold_build2 (MINUS_EXPR, type,
|
iv0->base, build_int_cst (type, 1));
|
iv0->base, build_int_cst (type, 1));
|
return number_of_iterations_lt (type, iv0, iv1, niter, never_infinite);
|
return number_of_iterations_lt (type, iv0, iv1, niter, never_infinite);
|
}
|
}
|
|
|
/* Determine the number of iterations according to condition (for staying
|
/* Determine the number of iterations according to condition (for staying
|
inside loop) which compares two induction variables using comparison
|
inside loop) which compares two induction variables using comparison
|
operator CODE. The induction variable on left side of the comparison
|
operator CODE. The induction variable on left side of the comparison
|
is IV0, the right-hand side is IV1. Both induction variables must have
|
is IV0, the right-hand side is IV1. Both induction variables must have
|
type TYPE, which must be an integer or pointer type. The steps of the
|
type TYPE, which must be an integer or pointer type. The steps of the
|
ivs must be constants (or NULL_TREE, which is interpreted as constant zero).
|
ivs must be constants (or NULL_TREE, which is interpreted as constant zero).
|
|
|
ONLY_EXIT is true if we are sure this is the only way the loop could be
|
ONLY_EXIT is true if we are sure this is the only way the loop could be
|
exited (including possibly non-returning function calls, exceptions, etc.)
|
exited (including possibly non-returning function calls, exceptions, etc.)
|
-- in this case we can use the information whether the control induction
|
-- in this case we can use the information whether the control induction
|
variables can overflow or not in a more efficient way.
|
variables can overflow or not in a more efficient way.
|
|
|
The results (number of iterations and assumptions as described in
|
The results (number of iterations and assumptions as described in
|
comments at struct tree_niter_desc in tree-flow.h) are stored to NITER.
|
comments at struct tree_niter_desc in tree-flow.h) are stored to NITER.
|
Returns false if it fails to determine number of iterations, true if it
|
Returns false if it fails to determine number of iterations, true if it
|
was determined (possibly with some assumptions). */
|
was determined (possibly with some assumptions). */
|
|
|
static bool
|
static bool
|
number_of_iterations_cond (tree type, affine_iv *iv0, enum tree_code code,
|
number_of_iterations_cond (tree type, affine_iv *iv0, enum tree_code code,
|
affine_iv *iv1, struct tree_niter_desc *niter,
|
affine_iv *iv1, struct tree_niter_desc *niter,
|
bool only_exit)
|
bool only_exit)
|
{
|
{
|
bool never_infinite;
|
bool never_infinite;
|
|
|
/* The meaning of these assumptions is this:
|
/* The meaning of these assumptions is this:
|
if !assumptions
|
if !assumptions
|
then the rest of information does not have to be valid
|
then the rest of information does not have to be valid
|
if may_be_zero then the loop does not roll, even if
|
if may_be_zero then the loop does not roll, even if
|
niter != 0. */
|
niter != 0. */
|
niter->assumptions = boolean_true_node;
|
niter->assumptions = boolean_true_node;
|
niter->may_be_zero = boolean_false_node;
|
niter->may_be_zero = boolean_false_node;
|
niter->niter = NULL_TREE;
|
niter->niter = NULL_TREE;
|
niter->additional_info = boolean_true_node;
|
niter->additional_info = boolean_true_node;
|
|
|
niter->bound = NULL_TREE;
|
niter->bound = NULL_TREE;
|
niter->cmp = ERROR_MARK;
|
niter->cmp = ERROR_MARK;
|
|
|
/* Make < comparison from > ones, and for NE_EXPR comparisons, ensure that
|
/* Make < comparison from > ones, and for NE_EXPR comparisons, ensure that
|
the control variable is on lhs. */
|
the control variable is on lhs. */
|
if (code == GE_EXPR || code == GT_EXPR
|
if (code == GE_EXPR || code == GT_EXPR
|
|| (code == NE_EXPR && zero_p (iv0->step)))
|
|| (code == NE_EXPR && zero_p (iv0->step)))
|
{
|
{
|
SWAP (iv0, iv1);
|
SWAP (iv0, iv1);
|
code = swap_tree_comparison (code);
|
code = swap_tree_comparison (code);
|
}
|
}
|
|
|
if (!only_exit)
|
if (!only_exit)
|
{
|
{
|
/* If this is not the only possible exit from the loop, the information
|
/* If this is not the only possible exit from the loop, the information
|
that the induction variables cannot overflow as derived from
|
that the induction variables cannot overflow as derived from
|
signedness analysis cannot be relied upon. We use them e.g. in the
|
signedness analysis cannot be relied upon. We use them e.g. in the
|
following way: given loop for (i = 0; i <= n; i++), if i is
|
following way: given loop for (i = 0; i <= n; i++), if i is
|
signed, it cannot overflow, thus this loop is equivalent to
|
signed, it cannot overflow, thus this loop is equivalent to
|
for (i = 0; i < n + 1; i++); however, if n == MAX, but the loop
|
for (i = 0; i < n + 1; i++); however, if n == MAX, but the loop
|
is exited in some other way before i overflows, this transformation
|
is exited in some other way before i overflows, this transformation
|
is incorrect (the new loop exits immediately). */
|
is incorrect (the new loop exits immediately). */
|
iv0->no_overflow = false;
|
iv0->no_overflow = false;
|
iv1->no_overflow = false;
|
iv1->no_overflow = false;
|
}
|
}
|
|
|
if (POINTER_TYPE_P (type))
|
if (POINTER_TYPE_P (type))
|
{
|
{
|
/* Comparison of pointers is undefined unless both iv0 and iv1 point
|
/* Comparison of pointers is undefined unless both iv0 and iv1 point
|
to the same object. If they do, the control variable cannot wrap
|
to the same object. If they do, the control variable cannot wrap
|
(as wrap around the bounds of memory will never return a pointer
|
(as wrap around the bounds of memory will never return a pointer
|
that would be guaranteed to point to the same object, even if we
|
that would be guaranteed to point to the same object, even if we
|
avoid undefined behavior by casting to size_t and back). The
|
avoid undefined behavior by casting to size_t and back). The
|
restrictions on pointer arithmetics and comparisons of pointers
|
restrictions on pointer arithmetics and comparisons of pointers
|
ensure that using the no-overflow assumptions is correct in this
|
ensure that using the no-overflow assumptions is correct in this
|
case even if ONLY_EXIT is false. */
|
case even if ONLY_EXIT is false. */
|
iv0->no_overflow = true;
|
iv0->no_overflow = true;
|
iv1->no_overflow = true;
|
iv1->no_overflow = true;
|
}
|
}
|
|
|
/* If the control induction variable does not overflow, the loop obviously
|
/* If the control induction variable does not overflow, the loop obviously
|
cannot be infinite. */
|
cannot be infinite. */
|
if (!zero_p (iv0->step) && iv0->no_overflow)
|
if (!zero_p (iv0->step) && iv0->no_overflow)
|
never_infinite = true;
|
never_infinite = true;
|
else if (!zero_p (iv1->step) && iv1->no_overflow)
|
else if (!zero_p (iv1->step) && iv1->no_overflow)
|
never_infinite = true;
|
never_infinite = true;
|
else
|
else
|
never_infinite = false;
|
never_infinite = false;
|
|
|
/* We can handle the case when neither of the sides of the comparison is
|
/* We can handle the case when neither of the sides of the comparison is
|
invariant, provided that the test is NE_EXPR. This rarely occurs in
|
invariant, provided that the test is NE_EXPR. This rarely occurs in
|
practice, but it is simple enough to manage. */
|
practice, but it is simple enough to manage. */
|
if (!zero_p (iv0->step) && !zero_p (iv1->step))
|
if (!zero_p (iv0->step) && !zero_p (iv1->step))
|
{
|
{
|
if (code != NE_EXPR)
|
if (code != NE_EXPR)
|
return false;
|
return false;
|
|
|
iv0->step = fold_binary_to_constant (MINUS_EXPR, type,
|
iv0->step = fold_binary_to_constant (MINUS_EXPR, type,
|
iv0->step, iv1->step);
|
iv0->step, iv1->step);
|
iv0->no_overflow = false;
|
iv0->no_overflow = false;
|
iv1->step = NULL_TREE;
|
iv1->step = NULL_TREE;
|
iv1->no_overflow = true;
|
iv1->no_overflow = true;
|
}
|
}
|
|
|
/* If the result of the comparison is a constant, the loop is weird. More
|
/* If the result of the comparison is a constant, the loop is weird. More
|
precise handling would be possible, but the situation is not common enough
|
precise handling would be possible, but the situation is not common enough
|
to waste time on it. */
|
to waste time on it. */
|
if (zero_p (iv0->step) && zero_p (iv1->step))
|
if (zero_p (iv0->step) && zero_p (iv1->step))
|
return false;
|
return false;
|
|
|
/* Ignore loops of while (i-- < 10) type. */
|
/* Ignore loops of while (i-- < 10) type. */
|
if (code != NE_EXPR)
|
if (code != NE_EXPR)
|
{
|
{
|
if (iv0->step && tree_int_cst_sign_bit (iv0->step))
|
if (iv0->step && tree_int_cst_sign_bit (iv0->step))
|
return false;
|
return false;
|
|
|
if (!zero_p (iv1->step) && !tree_int_cst_sign_bit (iv1->step))
|
if (!zero_p (iv1->step) && !tree_int_cst_sign_bit (iv1->step))
|
return false;
|
return false;
|
}
|
}
|
|
|
/* If the loop exits immediately, there is nothing to do. */
|
/* If the loop exits immediately, there is nothing to do. */
|
if (zero_p (fold_build2 (code, boolean_type_node, iv0->base, iv1->base)))
|
if (zero_p (fold_build2 (code, boolean_type_node, iv0->base, iv1->base)))
|
{
|
{
|
niter->niter = build_int_cst (unsigned_type_for (type), 0);
|
niter->niter = build_int_cst (unsigned_type_for (type), 0);
|
return true;
|
return true;
|
}
|
}
|
|
|
/* OK, now we know we have a senseful loop. Handle several cases, depending
|
/* OK, now we know we have a senseful loop. Handle several cases, depending
|
on what comparison operator is used. */
|
on what comparison operator is used. */
|
switch (code)
|
switch (code)
|
{
|
{
|
case NE_EXPR:
|
case NE_EXPR:
|
gcc_assert (zero_p (iv1->step));
|
gcc_assert (zero_p (iv1->step));
|
return number_of_iterations_ne (type, iv0, iv1->base, niter, never_infinite);
|
return number_of_iterations_ne (type, iv0, iv1->base, niter, never_infinite);
|
case LT_EXPR:
|
case LT_EXPR:
|
return number_of_iterations_lt (type, iv0, iv1, niter, never_infinite);
|
return number_of_iterations_lt (type, iv0, iv1, niter, never_infinite);
|
case LE_EXPR:
|
case LE_EXPR:
|
return number_of_iterations_le (type, iv0, iv1, niter, never_infinite);
|
return number_of_iterations_le (type, iv0, iv1, niter, never_infinite);
|
default:
|
default:
|
gcc_unreachable ();
|
gcc_unreachable ();
|
}
|
}
|
}
|
}
|
|
|
/* Substitute NEW for OLD in EXPR and fold the result. */
|
/* Substitute NEW for OLD in EXPR and fold the result. */
|
|
|
static tree
|
static tree
|
simplify_replace_tree (tree expr, tree old, tree new)
|
simplify_replace_tree (tree expr, tree old, tree new)
|
{
|
{
|
unsigned i, n;
|
unsigned i, n;
|
tree ret = NULL_TREE, e, se;
|
tree ret = NULL_TREE, e, se;
|
|
|
if (!expr)
|
if (!expr)
|
return NULL_TREE;
|
return NULL_TREE;
|
|
|
if (expr == old
|
if (expr == old
|
|| operand_equal_p (expr, old, 0))
|
|| operand_equal_p (expr, old, 0))
|
return unshare_expr (new);
|
return unshare_expr (new);
|
|
|
if (!EXPR_P (expr))
|
if (!EXPR_P (expr))
|
return expr;
|
return expr;
|
|
|
n = TREE_CODE_LENGTH (TREE_CODE (expr));
|
n = TREE_CODE_LENGTH (TREE_CODE (expr));
|
for (i = 0; i < n; i++)
|
for (i = 0; i < n; i++)
|
{
|
{
|
e = TREE_OPERAND (expr, i);
|
e = TREE_OPERAND (expr, i);
|
se = simplify_replace_tree (e, old, new);
|
se = simplify_replace_tree (e, old, new);
|
if (e == se)
|
if (e == se)
|
continue;
|
continue;
|
|
|
if (!ret)
|
if (!ret)
|
ret = copy_node (expr);
|
ret = copy_node (expr);
|
|
|
TREE_OPERAND (ret, i) = se;
|
TREE_OPERAND (ret, i) = se;
|
}
|
}
|
|
|
return (ret ? fold (ret) : expr);
|
return (ret ? fold (ret) : expr);
|
}
|
}
|
|
|
/* Expand definitions of ssa names in EXPR as long as they are simple
|
/* Expand definitions of ssa names in EXPR as long as they are simple
|
enough, and return the new expression. */
|
enough, and return the new expression. */
|
|
|
tree
|
tree
|
expand_simple_operations (tree expr)
|
expand_simple_operations (tree expr)
|
{
|
{
|
unsigned i, n;
|
unsigned i, n;
|
tree ret = NULL_TREE, e, ee, stmt;
|
tree ret = NULL_TREE, e, ee, stmt;
|
enum tree_code code;
|
enum tree_code code;
|
|
|
if (expr == NULL_TREE)
|
if (expr == NULL_TREE)
|
return expr;
|
return expr;
|
|
|
if (is_gimple_min_invariant (expr))
|
if (is_gimple_min_invariant (expr))
|
return expr;
|
return expr;
|
|
|
code = TREE_CODE (expr);
|
code = TREE_CODE (expr);
|
if (IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code)))
|
if (IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code)))
|
{
|
{
|
n = TREE_CODE_LENGTH (code);
|
n = TREE_CODE_LENGTH (code);
|
for (i = 0; i < n; i++)
|
for (i = 0; i < n; i++)
|
{
|
{
|
e = TREE_OPERAND (expr, i);
|
e = TREE_OPERAND (expr, i);
|
ee = expand_simple_operations (e);
|
ee = expand_simple_operations (e);
|
if (e == ee)
|
if (e == ee)
|
continue;
|
continue;
|
|
|
if (!ret)
|
if (!ret)
|
ret = copy_node (expr);
|
ret = copy_node (expr);
|
|
|
TREE_OPERAND (ret, i) = ee;
|
TREE_OPERAND (ret, i) = ee;
|
}
|
}
|
|
|
if (!ret)
|
if (!ret)
|
return expr;
|
return expr;
|
|
|
fold_defer_overflow_warnings ();
|
fold_defer_overflow_warnings ();
|
ret = fold (ret);
|
ret = fold (ret);
|
fold_undefer_and_ignore_overflow_warnings ();
|
fold_undefer_and_ignore_overflow_warnings ();
|
return ret;
|
return ret;
|
}
|
}
|
|
|
if (TREE_CODE (expr) != SSA_NAME)
|
if (TREE_CODE (expr) != SSA_NAME)
|
return expr;
|
return expr;
|
|
|
stmt = SSA_NAME_DEF_STMT (expr);
|
stmt = SSA_NAME_DEF_STMT (expr);
|
if (TREE_CODE (stmt) != MODIFY_EXPR)
|
if (TREE_CODE (stmt) != MODIFY_EXPR)
|
return expr;
|
return expr;
|
|
|
e = TREE_OPERAND (stmt, 1);
|
e = TREE_OPERAND (stmt, 1);
|
if (/* Casts are simple. */
|
if (/* Casts are simple. */
|
TREE_CODE (e) != NOP_EXPR
|
TREE_CODE (e) != NOP_EXPR
|
&& TREE_CODE (e) != CONVERT_EXPR
|
&& TREE_CODE (e) != CONVERT_EXPR
|
/* Copies are simple. */
|
/* Copies are simple. */
|
&& TREE_CODE (e) != SSA_NAME
|
&& TREE_CODE (e) != SSA_NAME
|
/* Assignments of invariants are simple. */
|
/* Assignments of invariants are simple. */
|
&& !is_gimple_min_invariant (e)
|
&& !is_gimple_min_invariant (e)
|
/* And increments and decrements by a constant are simple. */
|
/* And increments and decrements by a constant are simple. */
|
&& !((TREE_CODE (e) == PLUS_EXPR
|
&& !((TREE_CODE (e) == PLUS_EXPR
|
|| TREE_CODE (e) == MINUS_EXPR)
|
|| TREE_CODE (e) == MINUS_EXPR)
|
&& is_gimple_min_invariant (TREE_OPERAND (e, 1))))
|
&& is_gimple_min_invariant (TREE_OPERAND (e, 1))))
|
return expr;
|
return expr;
|
|
|
return expand_simple_operations (e);
|
return expand_simple_operations (e);
|
}
|
}
|
|
|
/* Tries to simplify EXPR using the condition COND. Returns the simplified
|
/* Tries to simplify EXPR using the condition COND. Returns the simplified
|
expression (or EXPR unchanged, if no simplification was possible). */
|
expression (or EXPR unchanged, if no simplification was possible). */
|
|
|
static tree
|
static tree
|
tree_simplify_using_condition_1 (tree cond, tree expr)
|
tree_simplify_using_condition_1 (tree cond, tree expr)
|
{
|
{
|
bool changed;
|
bool changed;
|
tree e, te, e0, e1, e2, notcond;
|
tree e, te, e0, e1, e2, notcond;
|
enum tree_code code = TREE_CODE (expr);
|
enum tree_code code = TREE_CODE (expr);
|
|
|
if (code == INTEGER_CST)
|
if (code == INTEGER_CST)
|
return expr;
|
return expr;
|
|
|
if (code == TRUTH_OR_EXPR
|
if (code == TRUTH_OR_EXPR
|
|| code == TRUTH_AND_EXPR
|
|| code == TRUTH_AND_EXPR
|
|| code == COND_EXPR)
|
|| code == COND_EXPR)
|
{
|
{
|
changed = false;
|
changed = false;
|
|
|
e0 = tree_simplify_using_condition_1 (cond, TREE_OPERAND (expr, 0));
|
e0 = tree_simplify_using_condition_1 (cond, TREE_OPERAND (expr, 0));
|
if (TREE_OPERAND (expr, 0) != e0)
|
if (TREE_OPERAND (expr, 0) != e0)
|
changed = true;
|
changed = true;
|
|
|
e1 = tree_simplify_using_condition_1 (cond, TREE_OPERAND (expr, 1));
|
e1 = tree_simplify_using_condition_1 (cond, TREE_OPERAND (expr, 1));
|
if (TREE_OPERAND (expr, 1) != e1)
|
if (TREE_OPERAND (expr, 1) != e1)
|
changed = true;
|
changed = true;
|
|
|
if (code == COND_EXPR)
|
if (code == COND_EXPR)
|
{
|
{
|
e2 = tree_simplify_using_condition_1 (cond, TREE_OPERAND (expr, 2));
|
e2 = tree_simplify_using_condition_1 (cond, TREE_OPERAND (expr, 2));
|
if (TREE_OPERAND (expr, 2) != e2)
|
if (TREE_OPERAND (expr, 2) != e2)
|
changed = true;
|
changed = true;
|
}
|
}
|
else
|
else
|
e2 = NULL_TREE;
|
e2 = NULL_TREE;
|
|
|
if (changed)
|
if (changed)
|
{
|
{
|
if (code == COND_EXPR)
|
if (code == COND_EXPR)
|
expr = fold_build3 (code, boolean_type_node, e0, e1, e2);
|
expr = fold_build3 (code, boolean_type_node, e0, e1, e2);
|
else
|
else
|
expr = fold_build2 (code, boolean_type_node, e0, e1);
|
expr = fold_build2 (code, boolean_type_node, e0, e1);
|
}
|
}
|
|
|
return expr;
|
return expr;
|
}
|
}
|
|
|
/* In case COND is equality, we may be able to simplify EXPR by copy/constant
|
/* In case COND is equality, we may be able to simplify EXPR by copy/constant
|
propagation, and vice versa. Fold does not handle this, since it is
|
propagation, and vice versa. Fold does not handle this, since it is
|
considered too expensive. */
|
considered too expensive. */
|
if (TREE_CODE (cond) == EQ_EXPR)
|
if (TREE_CODE (cond) == EQ_EXPR)
|
{
|
{
|
e0 = TREE_OPERAND (cond, 0);
|
e0 = TREE_OPERAND (cond, 0);
|
e1 = TREE_OPERAND (cond, 1);
|
e1 = TREE_OPERAND (cond, 1);
|
|
|
/* We know that e0 == e1. Check whether we cannot simplify expr
|
/* We know that e0 == e1. Check whether we cannot simplify expr
|
using this fact. */
|
using this fact. */
|
e = simplify_replace_tree (expr, e0, e1);
|
e = simplify_replace_tree (expr, e0, e1);
|
if (zero_p (e) || nonzero_p (e))
|
if (zero_p (e) || nonzero_p (e))
|
return e;
|
return e;
|
|
|
e = simplify_replace_tree (expr, e1, e0);
|
e = simplify_replace_tree (expr, e1, e0);
|
if (zero_p (e) || nonzero_p (e))
|
if (zero_p (e) || nonzero_p (e))
|
return e;
|
return e;
|
}
|
}
|
if (TREE_CODE (expr) == EQ_EXPR)
|
if (TREE_CODE (expr) == EQ_EXPR)
|
{
|
{
|
e0 = TREE_OPERAND (expr, 0);
|
e0 = TREE_OPERAND (expr, 0);
|
e1 = TREE_OPERAND (expr, 1);
|
e1 = TREE_OPERAND (expr, 1);
|
|
|
/* If e0 == e1 (EXPR) implies !COND, then EXPR cannot be true. */
|
/* If e0 == e1 (EXPR) implies !COND, then EXPR cannot be true. */
|
e = simplify_replace_tree (cond, e0, e1);
|
e = simplify_replace_tree (cond, e0, e1);
|
if (zero_p (e))
|
if (zero_p (e))
|
return e;
|
return e;
|
e = simplify_replace_tree (cond, e1, e0);
|
e = simplify_replace_tree (cond, e1, e0);
|
if (zero_p (e))
|
if (zero_p (e))
|
return e;
|
return e;
|
}
|
}
|
if (TREE_CODE (expr) == NE_EXPR)
|
if (TREE_CODE (expr) == NE_EXPR)
|
{
|
{
|
e0 = TREE_OPERAND (expr, 0);
|
e0 = TREE_OPERAND (expr, 0);
|
e1 = TREE_OPERAND (expr, 1);
|
e1 = TREE_OPERAND (expr, 1);
|
|
|
/* If e0 == e1 (!EXPR) implies !COND, then EXPR must be true. */
|
/* If e0 == e1 (!EXPR) implies !COND, then EXPR must be true. */
|
e = simplify_replace_tree (cond, e0, e1);
|
e = simplify_replace_tree (cond, e0, e1);
|
if (zero_p (e))
|
if (zero_p (e))
|
return boolean_true_node;
|
return boolean_true_node;
|
e = simplify_replace_tree (cond, e1, e0);
|
e = simplify_replace_tree (cond, e1, e0);
|
if (zero_p (e))
|
if (zero_p (e))
|
return boolean_true_node;
|
return boolean_true_node;
|
}
|
}
|
|
|
te = expand_simple_operations (expr);
|
te = expand_simple_operations (expr);
|
|
|
/* Check whether COND ==> EXPR. */
|
/* Check whether COND ==> EXPR. */
|
notcond = invert_truthvalue (cond);
|
notcond = invert_truthvalue (cond);
|
e = fold_binary (TRUTH_OR_EXPR, boolean_type_node, notcond, te);
|
e = fold_binary (TRUTH_OR_EXPR, boolean_type_node, notcond, te);
|
if (nonzero_p (e))
|
if (nonzero_p (e))
|
return e;
|
return e;
|
|
|
/* Check whether COND ==> not EXPR. */
|
/* Check whether COND ==> not EXPR. */
|
e = fold_binary (TRUTH_AND_EXPR, boolean_type_node, cond, te);
|
e = fold_binary (TRUTH_AND_EXPR, boolean_type_node, cond, te);
|
if (e && zero_p (e))
|
if (e && zero_p (e))
|
return e;
|
return e;
|
|
|
return expr;
|
return expr;
|
}
|
}
|
|
|
/* Tries to simplify EXPR using the condition COND. Returns the simplified
|
/* Tries to simplify EXPR using the condition COND. Returns the simplified
|
expression (or EXPR unchanged, if no simplification was possible).
|
expression (or EXPR unchanged, if no simplification was possible).
|
Wrapper around tree_simplify_using_condition_1 that ensures that chains
|
Wrapper around tree_simplify_using_condition_1 that ensures that chains
|
of simple operations in definitions of ssa names in COND are expanded,
|
of simple operations in definitions of ssa names in COND are expanded,
|
so that things like casts or incrementing the value of the bound before
|
so that things like casts or incrementing the value of the bound before
|
the loop do not cause us to fail. */
|
the loop do not cause us to fail. */
|
|
|
static tree
|
static tree
|
tree_simplify_using_condition (tree cond, tree expr)
|
tree_simplify_using_condition (tree cond, tree expr)
|
{
|
{
|
cond = expand_simple_operations (cond);
|
cond = expand_simple_operations (cond);
|
|
|
return tree_simplify_using_condition_1 (cond, expr);
|
return tree_simplify_using_condition_1 (cond, expr);
|
}
|
}
|
|
|
/* The maximum number of dominator BBs we search for conditions
|
/* The maximum number of dominator BBs we search for conditions
|
of loop header copies we use for simplifying a conditional
|
of loop header copies we use for simplifying a conditional
|
expression. */
|
expression. */
|
#define MAX_DOMINATORS_TO_WALK 8
|
#define MAX_DOMINATORS_TO_WALK 8
|
|
|
/* Tries to simplify EXPR using the conditions on entry to LOOP.
|
/* Tries to simplify EXPR using the conditions on entry to LOOP.
|
Record the conditions used for simplification to CONDS_USED.
|
Record the conditions used for simplification to CONDS_USED.
|
Returns the simplified expression (or EXPR unchanged, if no
|
Returns the simplified expression (or EXPR unchanged, if no
|
simplification was possible).*/
|
simplification was possible).*/
|
|
|
static tree
|
static tree
|
simplify_using_initial_conditions (struct loop *loop, tree expr,
|
simplify_using_initial_conditions (struct loop *loop, tree expr,
|
tree *conds_used)
|
tree *conds_used)
|
{
|
{
|
edge e;
|
edge e;
|
basic_block bb;
|
basic_block bb;
|
tree exp, cond;
|
tree exp, cond;
|
int cnt = 0;
|
int cnt = 0;
|
|
|
if (TREE_CODE (expr) == INTEGER_CST)
|
if (TREE_CODE (expr) == INTEGER_CST)
|
return expr;
|
return expr;
|
|
|
/* Limit walking the dominators to avoid quadraticness in
|
/* Limit walking the dominators to avoid quadraticness in
|
the number of BBs times the number of loops in degenerate
|
the number of BBs times the number of loops in degenerate
|
cases. */
|
cases. */
|
for (bb = loop->header;
|
for (bb = loop->header;
|
bb != ENTRY_BLOCK_PTR && cnt < MAX_DOMINATORS_TO_WALK;
|
bb != ENTRY_BLOCK_PTR && cnt < MAX_DOMINATORS_TO_WALK;
|
bb = get_immediate_dominator (CDI_DOMINATORS, bb))
|
bb = get_immediate_dominator (CDI_DOMINATORS, bb))
|
{
|
{
|
if (!single_pred_p (bb))
|
if (!single_pred_p (bb))
|
continue;
|
continue;
|
e = single_pred_edge (bb);
|
e = single_pred_edge (bb);
|
|
|
if (!(e->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
|
if (!(e->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
|
continue;
|
continue;
|
|
|
cond = COND_EXPR_COND (last_stmt (e->src));
|
cond = COND_EXPR_COND (last_stmt (e->src));
|
if (e->flags & EDGE_FALSE_VALUE)
|
if (e->flags & EDGE_FALSE_VALUE)
|
cond = invert_truthvalue (cond);
|
cond = invert_truthvalue (cond);
|
exp = tree_simplify_using_condition (cond, expr);
|
exp = tree_simplify_using_condition (cond, expr);
|
|
|
if (exp != expr)
|
if (exp != expr)
|
*conds_used = fold_build2 (TRUTH_AND_EXPR,
|
*conds_used = fold_build2 (TRUTH_AND_EXPR,
|
boolean_type_node,
|
boolean_type_node,
|
*conds_used,
|
*conds_used,
|
cond);
|
cond);
|
|
|
expr = exp;
|
expr = exp;
|
++cnt;
|
++cnt;
|
}
|
}
|
|
|
return expr;
|
return expr;
|
}
|
}
|
|
|
/* Tries to simplify EXPR using the evolutions of the loop invariants
|
/* Tries to simplify EXPR using the evolutions of the loop invariants
|
in the superloops of LOOP. Returns the simplified expression
|
in the superloops of LOOP. Returns the simplified expression
|
(or EXPR unchanged, if no simplification was possible). */
|
(or EXPR unchanged, if no simplification was possible). */
|
|
|
static tree
|
static tree
|
simplify_using_outer_evolutions (struct loop *loop, tree expr)
|
simplify_using_outer_evolutions (struct loop *loop, tree expr)
|
{
|
{
|
enum tree_code code = TREE_CODE (expr);
|
enum tree_code code = TREE_CODE (expr);
|
bool changed;
|
bool changed;
|
tree e, e0, e1, e2;
|
tree e, e0, e1, e2;
|
|
|
if (is_gimple_min_invariant (expr))
|
if (is_gimple_min_invariant (expr))
|
return expr;
|
return expr;
|
|
|
if (code == TRUTH_OR_EXPR
|
if (code == TRUTH_OR_EXPR
|
|| code == TRUTH_AND_EXPR
|
|| code == TRUTH_AND_EXPR
|
|| code == COND_EXPR)
|
|| code == COND_EXPR)
|
{
|
{
|
changed = false;
|
changed = false;
|
|
|
e0 = simplify_using_outer_evolutions (loop, TREE_OPERAND (expr, 0));
|
e0 = simplify_using_outer_evolutions (loop, TREE_OPERAND (expr, 0));
|
if (TREE_OPERAND (expr, 0) != e0)
|
if (TREE_OPERAND (expr, 0) != e0)
|
changed = true;
|
changed = true;
|
|
|
e1 = simplify_using_outer_evolutions (loop, TREE_OPERAND (expr, 1));
|
e1 = simplify_using_outer_evolutions (loop, TREE_OPERAND (expr, 1));
|
if (TREE_OPERAND (expr, 1) != e1)
|
if (TREE_OPERAND (expr, 1) != e1)
|
changed = true;
|
changed = true;
|
|
|
if (code == COND_EXPR)
|
if (code == COND_EXPR)
|
{
|
{
|
e2 = simplify_using_outer_evolutions (loop, TREE_OPERAND (expr, 2));
|
e2 = simplify_using_outer_evolutions (loop, TREE_OPERAND (expr, 2));
|
if (TREE_OPERAND (expr, 2) != e2)
|
if (TREE_OPERAND (expr, 2) != e2)
|
changed = true;
|
changed = true;
|
}
|
}
|
else
|
else
|
e2 = NULL_TREE;
|
e2 = NULL_TREE;
|
|
|
if (changed)
|
if (changed)
|
{
|
{
|
if (code == COND_EXPR)
|
if (code == COND_EXPR)
|
expr = fold_build3 (code, boolean_type_node, e0, e1, e2);
|
expr = fold_build3 (code, boolean_type_node, e0, e1, e2);
|
else
|
else
|
expr = fold_build2 (code, boolean_type_node, e0, e1);
|
expr = fold_build2 (code, boolean_type_node, e0, e1);
|
}
|
}
|
|
|
return expr;
|
return expr;
|
}
|
}
|
|
|
e = instantiate_parameters (loop, expr);
|
e = instantiate_parameters (loop, expr);
|
if (is_gimple_min_invariant (e))
|
if (is_gimple_min_invariant (e))
|
return e;
|
return e;
|
|
|
return expr;
|
return expr;
|
}
|
}
|
|
|
/* Returns true if EXIT is the only possible exit from LOOP. */
|
/* Returns true if EXIT is the only possible exit from LOOP. */
|
|
|
static bool
|
static bool
|
loop_only_exit_p (struct loop *loop, edge exit)
|
loop_only_exit_p (struct loop *loop, edge exit)
|
{
|
{
|
basic_block *body;
|
basic_block *body;
|
block_stmt_iterator bsi;
|
block_stmt_iterator bsi;
|
unsigned i;
|
unsigned i;
|
tree call;
|
tree call;
|
|
|
if (exit != loop->single_exit)
|
if (exit != loop->single_exit)
|
return false;
|
return false;
|
|
|
body = get_loop_body (loop);
|
body = get_loop_body (loop);
|
for (i = 0; i < loop->num_nodes; i++)
|
for (i = 0; i < loop->num_nodes; i++)
|
{
|
{
|
for (bsi = bsi_start (body[0]); !bsi_end_p (bsi); bsi_next (&bsi))
|
for (bsi = bsi_start (body[0]); !bsi_end_p (bsi); bsi_next (&bsi))
|
{
|
{
|
call = get_call_expr_in (bsi_stmt (bsi));
|
call = get_call_expr_in (bsi_stmt (bsi));
|
if (call && TREE_SIDE_EFFECTS (call))
|
if (call && TREE_SIDE_EFFECTS (call))
|
{
|
{
|
free (body);
|
free (body);
|
return false;
|
return false;
|
}
|
}
|
}
|
}
|
}
|
}
|
|
|
free (body);
|
free (body);
|
return true;
|
return true;
|
}
|
}
|
|
|
/* Stores description of number of iterations of LOOP derived from
|
/* Stores description of number of iterations of LOOP derived from
|
EXIT (an exit edge of the LOOP) in NITER. Returns true if some
|
EXIT (an exit edge of the LOOP) in NITER. Returns true if some
|
useful information could be derived (and fields of NITER has
|
useful information could be derived (and fields of NITER has
|
meaning described in comments at struct tree_niter_desc
|
meaning described in comments at struct tree_niter_desc
|
declaration), false otherwise. If WARN is true and
|
declaration), false otherwise. If WARN is true and
|
-Wunsafe-loop-optimizations was given, warn if the optimizer is going to use
|
-Wunsafe-loop-optimizations was given, warn if the optimizer is going to use
|
potentially unsafe assumptions. */
|
potentially unsafe assumptions. */
|
|
|
bool
|
bool
|
number_of_iterations_exit (struct loop *loop, edge exit,
|
number_of_iterations_exit (struct loop *loop, edge exit,
|
struct tree_niter_desc *niter,
|
struct tree_niter_desc *niter,
|
bool warn)
|
bool warn)
|
{
|
{
|
tree stmt, cond, type;
|
tree stmt, cond, type;
|
tree op0, op1;
|
tree op0, op1;
|
enum tree_code code;
|
enum tree_code code;
|
affine_iv iv0, iv1;
|
affine_iv iv0, iv1;
|
|
|
if (!dominated_by_p (CDI_DOMINATORS, loop->latch, exit->src))
|
if (!dominated_by_p (CDI_DOMINATORS, loop->latch, exit->src))
|
return false;
|
return false;
|
|
|
niter->assumptions = boolean_false_node;
|
niter->assumptions = boolean_false_node;
|
stmt = last_stmt (exit->src);
|
stmt = last_stmt (exit->src);
|
if (!stmt || TREE_CODE (stmt) != COND_EXPR)
|
if (!stmt || TREE_CODE (stmt) != COND_EXPR)
|
return false;
|
return false;
|
|
|
/* We want the condition for staying inside loop. */
|
/* We want the condition for staying inside loop. */
|
cond = COND_EXPR_COND (stmt);
|
cond = COND_EXPR_COND (stmt);
|
if (exit->flags & EDGE_TRUE_VALUE)
|
if (exit->flags & EDGE_TRUE_VALUE)
|
cond = invert_truthvalue (cond);
|
cond = invert_truthvalue (cond);
|
|
|
code = TREE_CODE (cond);
|
code = TREE_CODE (cond);
|
switch (code)
|
switch (code)
|
{
|
{
|
case GT_EXPR:
|
case GT_EXPR:
|
case GE_EXPR:
|
case GE_EXPR:
|
case NE_EXPR:
|
case NE_EXPR:
|
case LT_EXPR:
|
case LT_EXPR:
|
case LE_EXPR:
|
case LE_EXPR:
|
break;
|
break;
|
|
|
default:
|
default:
|
return false;
|
return false;
|
}
|
}
|
|
|
op0 = TREE_OPERAND (cond, 0);
|
op0 = TREE_OPERAND (cond, 0);
|
op1 = TREE_OPERAND (cond, 1);
|
op1 = TREE_OPERAND (cond, 1);
|
type = TREE_TYPE (op0);
|
type = TREE_TYPE (op0);
|
|
|
if (TREE_CODE (type) != INTEGER_TYPE
|
if (TREE_CODE (type) != INTEGER_TYPE
|
&& !POINTER_TYPE_P (type))
|
&& !POINTER_TYPE_P (type))
|
return false;
|
return false;
|
|
|
if (!simple_iv (loop, stmt, op0, &iv0, false))
|
if (!simple_iv (loop, stmt, op0, &iv0, false))
|
return false;
|
return false;
|
if (!simple_iv (loop, stmt, op1, &iv1, false))
|
if (!simple_iv (loop, stmt, op1, &iv1, false))
|
return false;
|
return false;
|
|
|
/* We don't want to see undefined signed overflow warnings while
|
/* We don't want to see undefined signed overflow warnings while
|
computing the nmber of iterations. */
|
computing the nmber of iterations. */
|
fold_defer_overflow_warnings ();
|
fold_defer_overflow_warnings ();
|
|
|
iv0.base = expand_simple_operations (iv0.base);
|
iv0.base = expand_simple_operations (iv0.base);
|
iv1.base = expand_simple_operations (iv1.base);
|
iv1.base = expand_simple_operations (iv1.base);
|
if (!number_of_iterations_cond (type, &iv0, code, &iv1, niter,
|
if (!number_of_iterations_cond (type, &iv0, code, &iv1, niter,
|
loop_only_exit_p (loop, exit)))
|
loop_only_exit_p (loop, exit)))
|
{
|
{
|
fold_undefer_and_ignore_overflow_warnings ();
|
fold_undefer_and_ignore_overflow_warnings ();
|
return false;
|
return false;
|
}
|
}
|
|
|
if (optimize >= 3)
|
if (optimize >= 3)
|
{
|
{
|
niter->assumptions = simplify_using_outer_evolutions (loop,
|
niter->assumptions = simplify_using_outer_evolutions (loop,
|
niter->assumptions);
|
niter->assumptions);
|
niter->may_be_zero = simplify_using_outer_evolutions (loop,
|
niter->may_be_zero = simplify_using_outer_evolutions (loop,
|
niter->may_be_zero);
|
niter->may_be_zero);
|
niter->niter = simplify_using_outer_evolutions (loop, niter->niter);
|
niter->niter = simplify_using_outer_evolutions (loop, niter->niter);
|
}
|
}
|
|
|
niter->additional_info = boolean_true_node;
|
niter->additional_info = boolean_true_node;
|
niter->assumptions
|
niter->assumptions
|
= simplify_using_initial_conditions (loop,
|
= simplify_using_initial_conditions (loop,
|
niter->assumptions,
|
niter->assumptions,
|
&niter->additional_info);
|
&niter->additional_info);
|
niter->may_be_zero
|
niter->may_be_zero
|
= simplify_using_initial_conditions (loop,
|
= simplify_using_initial_conditions (loop,
|
niter->may_be_zero,
|
niter->may_be_zero,
|
&niter->additional_info);
|
&niter->additional_info);
|
|
|
fold_undefer_and_ignore_overflow_warnings ();
|
fold_undefer_and_ignore_overflow_warnings ();
|
|
|
if (integer_onep (niter->assumptions))
|
if (integer_onep (niter->assumptions))
|
return true;
|
return true;
|
|
|
/* With -funsafe-loop-optimizations we assume that nothing bad can happen.
|
/* With -funsafe-loop-optimizations we assume that nothing bad can happen.
|
But if we can prove that there is overflow or some other source of weird
|
But if we can prove that there is overflow or some other source of weird
|
behavior, ignore the loop even with -funsafe-loop-optimizations. */
|
behavior, ignore the loop even with -funsafe-loop-optimizations. */
|
if (integer_zerop (niter->assumptions))
|
if (integer_zerop (niter->assumptions))
|
return false;
|
return false;
|
|
|
if (flag_unsafe_loop_optimizations)
|
if (flag_unsafe_loop_optimizations)
|
niter->assumptions = boolean_true_node;
|
niter->assumptions = boolean_true_node;
|
|
|
if (warn)
|
if (warn)
|
{
|
{
|
const char *wording;
|
const char *wording;
|
location_t loc = EXPR_LOCATION (stmt);
|
location_t loc = EXPR_LOCATION (stmt);
|
|
|
/* We can provide a more specific warning if one of the operator is
|
/* We can provide a more specific warning if one of the operator is
|
constant and the other advances by +1 or -1. */
|
constant and the other advances by +1 or -1. */
|
if (!zero_p (iv1.step)
|
if (!zero_p (iv1.step)
|
? (zero_p (iv0.step)
|
? (zero_p (iv0.step)
|
&& (integer_onep (iv1.step) || integer_all_onesp (iv1.step)))
|
&& (integer_onep (iv1.step) || integer_all_onesp (iv1.step)))
|
: (iv0.step
|
: (iv0.step
|
&& (integer_onep (iv0.step) || integer_all_onesp (iv0.step))))
|
&& (integer_onep (iv0.step) || integer_all_onesp (iv0.step))))
|
wording =
|
wording =
|
flag_unsafe_loop_optimizations
|
flag_unsafe_loop_optimizations
|
? N_("assuming that the loop is not infinite")
|
? N_("assuming that the loop is not infinite")
|
: N_("cannot optimize possibly infinite loops");
|
: N_("cannot optimize possibly infinite loops");
|
else
|
else
|
wording =
|
wording =
|
flag_unsafe_loop_optimizations
|
flag_unsafe_loop_optimizations
|
? N_("assuming that the loop counter does not overflow")
|
? N_("assuming that the loop counter does not overflow")
|
: N_("cannot optimize loop, the loop counter may overflow");
|
: N_("cannot optimize loop, the loop counter may overflow");
|
|
|
if (LOCATION_LINE (loc) > 0)
|
if (LOCATION_LINE (loc) > 0)
|
warning (OPT_Wunsafe_loop_optimizations, "%H%s", &loc, gettext (wording));
|
warning (OPT_Wunsafe_loop_optimizations, "%H%s", &loc, gettext (wording));
|
else
|
else
|
warning (OPT_Wunsafe_loop_optimizations, "%s", gettext (wording));
|
warning (OPT_Wunsafe_loop_optimizations, "%s", gettext (wording));
|
}
|
}
|
|
|
return flag_unsafe_loop_optimizations;
|
return flag_unsafe_loop_optimizations;
|
}
|
}
|
|
|
/* Try to determine the number of iterations of LOOP. If we succeed,
|
/* Try to determine the number of iterations of LOOP. If we succeed,
|
expression giving number of iterations is returned and *EXIT is
|
expression giving number of iterations is returned and *EXIT is
|
set to the edge from that the information is obtained. Otherwise
|
set to the edge from that the information is obtained. Otherwise
|
chrec_dont_know is returned. */
|
chrec_dont_know is returned. */
|
|
|
tree
|
tree
|
find_loop_niter (struct loop *loop, edge *exit)
|
find_loop_niter (struct loop *loop, edge *exit)
|
{
|
{
|
unsigned n_exits, i;
|
unsigned n_exits, i;
|
edge *exits = get_loop_exit_edges (loop, &n_exits);
|
edge *exits = get_loop_exit_edges (loop, &n_exits);
|
edge ex;
|
edge ex;
|
tree niter = NULL_TREE, aniter;
|
tree niter = NULL_TREE, aniter;
|
struct tree_niter_desc desc;
|
struct tree_niter_desc desc;
|
|
|
*exit = NULL;
|
*exit = NULL;
|
for (i = 0; i < n_exits; i++)
|
for (i = 0; i < n_exits; i++)
|
{
|
{
|
ex = exits[i];
|
ex = exits[i];
|
if (!just_once_each_iteration_p (loop, ex->src))
|
if (!just_once_each_iteration_p (loop, ex->src))
|
continue;
|
continue;
|
|
|
if (!number_of_iterations_exit (loop, ex, &desc, false))
|
if (!number_of_iterations_exit (loop, ex, &desc, false))
|
continue;
|
continue;
|
|
|
if (nonzero_p (desc.may_be_zero))
|
if (nonzero_p (desc.may_be_zero))
|
{
|
{
|
/* We exit in the first iteration through this exit.
|
/* We exit in the first iteration through this exit.
|
We won't find anything better. */
|
We won't find anything better. */
|
niter = build_int_cst (unsigned_type_node, 0);
|
niter = build_int_cst (unsigned_type_node, 0);
|
*exit = ex;
|
*exit = ex;
|
break;
|
break;
|
}
|
}
|
|
|
if (!zero_p (desc.may_be_zero))
|
if (!zero_p (desc.may_be_zero))
|
continue;
|
continue;
|
|
|
aniter = desc.niter;
|
aniter = desc.niter;
|
|
|
if (!niter)
|
if (!niter)
|
{
|
{
|
/* Nothing recorded yet. */
|
/* Nothing recorded yet. */
|
niter = aniter;
|
niter = aniter;
|
*exit = ex;
|
*exit = ex;
|
continue;
|
continue;
|
}
|
}
|
|
|
/* Prefer constants, the lower the better. */
|
/* Prefer constants, the lower the better. */
|
if (TREE_CODE (aniter) != INTEGER_CST)
|
if (TREE_CODE (aniter) != INTEGER_CST)
|
continue;
|
continue;
|
|
|
if (TREE_CODE (niter) != INTEGER_CST)
|
if (TREE_CODE (niter) != INTEGER_CST)
|
{
|
{
|
niter = aniter;
|
niter = aniter;
|
*exit = ex;
|
*exit = ex;
|
continue;
|
continue;
|
}
|
}
|
|
|
if (tree_int_cst_lt (aniter, niter))
|
if (tree_int_cst_lt (aniter, niter))
|
{
|
{
|
niter = aniter;
|
niter = aniter;
|
*exit = ex;
|
*exit = ex;
|
continue;
|
continue;
|
}
|
}
|
}
|
}
|
free (exits);
|
free (exits);
|
|
|
return niter ? niter : chrec_dont_know;
|
return niter ? niter : chrec_dont_know;
|
}
|
}
|
|
|
/*
|
/*
|
|
|
Analysis of a number of iterations of a loop by a brute-force evaluation.
|
Analysis of a number of iterations of a loop by a brute-force evaluation.
|
|
|
*/
|
*/
|
|
|
/* Bound on the number of iterations we try to evaluate. */
|
/* Bound on the number of iterations we try to evaluate. */
|
|
|
#define MAX_ITERATIONS_TO_TRACK \
|
#define MAX_ITERATIONS_TO_TRACK \
|
((unsigned) PARAM_VALUE (PARAM_MAX_ITERATIONS_TO_TRACK))
|
((unsigned) PARAM_VALUE (PARAM_MAX_ITERATIONS_TO_TRACK))
|
|
|
/* Returns the loop phi node of LOOP such that ssa name X is derived from its
|
/* Returns the loop phi node of LOOP such that ssa name X is derived from its
|
result by a chain of operations such that all but exactly one of their
|
result by a chain of operations such that all but exactly one of their
|
operands are constants. */
|
operands are constants. */
|
|
|
static tree
|
static tree
|
chain_of_csts_start (struct loop *loop, tree x)
|
chain_of_csts_start (struct loop *loop, tree x)
|
{
|
{
|
tree stmt = SSA_NAME_DEF_STMT (x);
|
tree stmt = SSA_NAME_DEF_STMT (x);
|
tree use;
|
tree use;
|
basic_block bb = bb_for_stmt (stmt);
|
basic_block bb = bb_for_stmt (stmt);
|
|
|
if (!bb
|
if (!bb
|
|| !flow_bb_inside_loop_p (loop, bb))
|
|| !flow_bb_inside_loop_p (loop, bb))
|
return NULL_TREE;
|
return NULL_TREE;
|
|
|
if (TREE_CODE (stmt) == PHI_NODE)
|
if (TREE_CODE (stmt) == PHI_NODE)
|
{
|
{
|
if (bb == loop->header)
|
if (bb == loop->header)
|
return stmt;
|
return stmt;
|
|
|
return NULL_TREE;
|
return NULL_TREE;
|
}
|
}
|
|
|
if (TREE_CODE (stmt) != MODIFY_EXPR)
|
if (TREE_CODE (stmt) != MODIFY_EXPR)
|
return NULL_TREE;
|
return NULL_TREE;
|
|
|
if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS))
|
if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS))
|
return NULL_TREE;
|
return NULL_TREE;
|
if (SINGLE_SSA_DEF_OPERAND (stmt, SSA_OP_DEF) == NULL_DEF_OPERAND_P)
|
if (SINGLE_SSA_DEF_OPERAND (stmt, SSA_OP_DEF) == NULL_DEF_OPERAND_P)
|
return NULL_TREE;
|
return NULL_TREE;
|
|
|
use = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_USE);
|
use = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_USE);
|
if (use == NULL_USE_OPERAND_P)
|
if (use == NULL_USE_OPERAND_P)
|
return NULL_TREE;
|
return NULL_TREE;
|
|
|
return chain_of_csts_start (loop, use);
|
return chain_of_csts_start (loop, use);
|
}
|
}
|
|
|
/* Determines whether the expression X is derived from a result of a phi node
|
/* Determines whether the expression X is derived from a result of a phi node
|
in header of LOOP such that
|
in header of LOOP such that
|
|
|
* the derivation of X consists only from operations with constants
|
* the derivation of X consists only from operations with constants
|
* the initial value of the phi node is constant
|
* the initial value of the phi node is constant
|
* the value of the phi node in the next iteration can be derived from the
|
* the value of the phi node in the next iteration can be derived from the
|
value in the current iteration by a chain of operations with constants.
|
value in the current iteration by a chain of operations with constants.
|
|
|
If such phi node exists, it is returned. If X is a constant, X is returned
|
If such phi node exists, it is returned. If X is a constant, X is returned
|
unchanged. Otherwise NULL_TREE is returned. */
|
unchanged. Otherwise NULL_TREE is returned. */
|
|
|
static tree
|
static tree
|
get_base_for (struct loop *loop, tree x)
|
get_base_for (struct loop *loop, tree x)
|
{
|
{
|
tree phi, init, next;
|
tree phi, init, next;
|
|
|
if (is_gimple_min_invariant (x))
|
if (is_gimple_min_invariant (x))
|
return x;
|
return x;
|
|
|
phi = chain_of_csts_start (loop, x);
|
phi = chain_of_csts_start (loop, x);
|
if (!phi)
|
if (!phi)
|
return NULL_TREE;
|
return NULL_TREE;
|
|
|
init = PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop));
|
init = PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop));
|
next = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (loop));
|
next = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (loop));
|
|
|
if (TREE_CODE (next) != SSA_NAME)
|
if (TREE_CODE (next) != SSA_NAME)
|
return NULL_TREE;
|
return NULL_TREE;
|
|
|
if (!is_gimple_min_invariant (init))
|
if (!is_gimple_min_invariant (init))
|
return NULL_TREE;
|
return NULL_TREE;
|
|
|
if (chain_of_csts_start (loop, next) != phi)
|
if (chain_of_csts_start (loop, next) != phi)
|
return NULL_TREE;
|
return NULL_TREE;
|
|
|
return phi;
|
return phi;
|
}
|
}
|
|
|
/* Given an expression X, then
|
/* Given an expression X, then
|
|
|
* if X is NULL_TREE, we return the constant BASE.
|
* if X is NULL_TREE, we return the constant BASE.
|
* otherwise X is a SSA name, whose value in the considered loop is derived
|
* otherwise X is a SSA name, whose value in the considered loop is derived
|
by a chain of operations with constant from a result of a phi node in
|
by a chain of operations with constant from a result of a phi node in
|
the header of the loop. Then we return value of X when the value of the
|
the header of the loop. Then we return value of X when the value of the
|
result of this phi node is given by the constant BASE. */
|
result of this phi node is given by the constant BASE. */
|
|
|
static tree
|
static tree
|
get_val_for (tree x, tree base)
|
get_val_for (tree x, tree base)
|
{
|
{
|
tree stmt, nx, val;
|
tree stmt, nx, val;
|
use_operand_p op;
|
use_operand_p op;
|
ssa_op_iter iter;
|
ssa_op_iter iter;
|
|
|
gcc_assert (is_gimple_min_invariant (base));
|
gcc_assert (is_gimple_min_invariant (base));
|
|
|
if (!x)
|
if (!x)
|
return base;
|
return base;
|
|
|
stmt = SSA_NAME_DEF_STMT (x);
|
stmt = SSA_NAME_DEF_STMT (x);
|
if (TREE_CODE (stmt) == PHI_NODE)
|
if (TREE_CODE (stmt) == PHI_NODE)
|
return base;
|
return base;
|
|
|
FOR_EACH_SSA_USE_OPERAND (op, stmt, iter, SSA_OP_USE)
|
FOR_EACH_SSA_USE_OPERAND (op, stmt, iter, SSA_OP_USE)
|
{
|
{
|
nx = USE_FROM_PTR (op);
|
nx = USE_FROM_PTR (op);
|
val = get_val_for (nx, base);
|
val = get_val_for (nx, base);
|
SET_USE (op, val);
|
SET_USE (op, val);
|
val = fold (TREE_OPERAND (stmt, 1));
|
val = fold (TREE_OPERAND (stmt, 1));
|
SET_USE (op, nx);
|
SET_USE (op, nx);
|
/* only iterate loop once. */
|
/* only iterate loop once. */
|
return val;
|
return val;
|
}
|
}
|
|
|
/* Should never reach here. */
|
/* Should never reach here. */
|
gcc_unreachable();
|
gcc_unreachable();
|
}
|
}
|
|
|
/* Tries to count the number of iterations of LOOP till it exits by EXIT
|
/* Tries to count the number of iterations of LOOP till it exits by EXIT
|
by brute force -- i.e. by determining the value of the operands of the
|
by brute force -- i.e. by determining the value of the operands of the
|
condition at EXIT in first few iterations of the loop (assuming that
|
condition at EXIT in first few iterations of the loop (assuming that
|
these values are constant) and determining the first one in that the
|
these values are constant) and determining the first one in that the
|
condition is not satisfied. Returns the constant giving the number
|
condition is not satisfied. Returns the constant giving the number
|
of the iterations of LOOP if successful, chrec_dont_know otherwise. */
|
of the iterations of LOOP if successful, chrec_dont_know otherwise. */
|
|
|
tree
|
tree
|
loop_niter_by_eval (struct loop *loop, edge exit)
|
loop_niter_by_eval (struct loop *loop, edge exit)
|
{
|
{
|
tree cond, cnd, acnd;
|
tree cond, cnd, acnd;
|
tree op[2], val[2], next[2], aval[2], phi[2];
|
tree op[2], val[2], next[2], aval[2], phi[2];
|
unsigned i, j;
|
unsigned i, j;
|
enum tree_code cmp;
|
enum tree_code cmp;
|
|
|
cond = last_stmt (exit->src);
|
cond = last_stmt (exit->src);
|
if (!cond || TREE_CODE (cond) != COND_EXPR)
|
if (!cond || TREE_CODE (cond) != COND_EXPR)
|
return chrec_dont_know;
|
return chrec_dont_know;
|
|
|
cnd = COND_EXPR_COND (cond);
|
cnd = COND_EXPR_COND (cond);
|
if (exit->flags & EDGE_TRUE_VALUE)
|
if (exit->flags & EDGE_TRUE_VALUE)
|
cnd = invert_truthvalue (cnd);
|
cnd = invert_truthvalue (cnd);
|
|
|
cmp = TREE_CODE (cnd);
|
cmp = TREE_CODE (cnd);
|
switch (cmp)
|
switch (cmp)
|
{
|
{
|
case EQ_EXPR:
|
case EQ_EXPR:
|
case NE_EXPR:
|
case NE_EXPR:
|
case GT_EXPR:
|
case GT_EXPR:
|
case GE_EXPR:
|
case GE_EXPR:
|
case LT_EXPR:
|
case LT_EXPR:
|
case LE_EXPR:
|
case LE_EXPR:
|
for (j = 0; j < 2; j++)
|
for (j = 0; j < 2; j++)
|
op[j] = TREE_OPERAND (cnd, j);
|
op[j] = TREE_OPERAND (cnd, j);
|
break;
|
break;
|
|
|
default:
|
default:
|
return chrec_dont_know;
|
return chrec_dont_know;
|
}
|
}
|
|
|
for (j = 0; j < 2; j++)
|
for (j = 0; j < 2; j++)
|
{
|
{
|
phi[j] = get_base_for (loop, op[j]);
|
phi[j] = get_base_for (loop, op[j]);
|
if (!phi[j])
|
if (!phi[j])
|
return chrec_dont_know;
|
return chrec_dont_know;
|
}
|
}
|
|
|
for (j = 0; j < 2; j++)
|
for (j = 0; j < 2; j++)
|
{
|
{
|
if (TREE_CODE (phi[j]) == PHI_NODE)
|
if (TREE_CODE (phi[j]) == PHI_NODE)
|
{
|
{
|
val[j] = PHI_ARG_DEF_FROM_EDGE (phi[j], loop_preheader_edge (loop));
|
val[j] = PHI_ARG_DEF_FROM_EDGE (phi[j], loop_preheader_edge (loop));
|
next[j] = PHI_ARG_DEF_FROM_EDGE (phi[j], loop_latch_edge (loop));
|
next[j] = PHI_ARG_DEF_FROM_EDGE (phi[j], loop_latch_edge (loop));
|
}
|
}
|
else
|
else
|
{
|
{
|
val[j] = phi[j];
|
val[j] = phi[j];
|
next[j] = NULL_TREE;
|
next[j] = NULL_TREE;
|
op[j] = NULL_TREE;
|
op[j] = NULL_TREE;
|
}
|
}
|
}
|
}
|
|
|
/* Don't issue signed overflow warnings. */
|
/* Don't issue signed overflow warnings. */
|
fold_defer_overflow_warnings ();
|
fold_defer_overflow_warnings ();
|
|
|
for (i = 0; i < MAX_ITERATIONS_TO_TRACK; i++)
|
for (i = 0; i < MAX_ITERATIONS_TO_TRACK; i++)
|
{
|
{
|
for (j = 0; j < 2; j++)
|
for (j = 0; j < 2; j++)
|
aval[j] = get_val_for (op[j], val[j]);
|
aval[j] = get_val_for (op[j], val[j]);
|
|
|
acnd = fold_binary (cmp, boolean_type_node, aval[0], aval[1]);
|
acnd = fold_binary (cmp, boolean_type_node, aval[0], aval[1]);
|
if (acnd && zero_p (acnd))
|
if (acnd && zero_p (acnd))
|
{
|
{
|
fold_undefer_and_ignore_overflow_warnings ();
|
fold_undefer_and_ignore_overflow_warnings ();
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
fprintf (dump_file,
|
fprintf (dump_file,
|
"Proved that loop %d iterates %d times using brute force.\n",
|
"Proved that loop %d iterates %d times using brute force.\n",
|
loop->num, i);
|
loop->num, i);
|
return build_int_cst (unsigned_type_node, i);
|
return build_int_cst (unsigned_type_node, i);
|
}
|
}
|
|
|
for (j = 0; j < 2; j++)
|
for (j = 0; j < 2; j++)
|
{
|
{
|
val[j] = get_val_for (next[j], val[j]);
|
val[j] = get_val_for (next[j], val[j]);
|
if (!is_gimple_min_invariant (val[j]))
|
if (!is_gimple_min_invariant (val[j]))
|
{
|
{
|
fold_undefer_and_ignore_overflow_warnings ();
|
fold_undefer_and_ignore_overflow_warnings ();
|
return chrec_dont_know;
|
return chrec_dont_know;
|
}
|
}
|
}
|
}
|
}
|
}
|
|
|
fold_undefer_and_ignore_overflow_warnings ();
|
fold_undefer_and_ignore_overflow_warnings ();
|
|
|
return chrec_dont_know;
|
return chrec_dont_know;
|
}
|
}
|
|
|
/* Finds the exit of the LOOP by that the loop exits after a constant
|
/* Finds the exit of the LOOP by that the loop exits after a constant
|
number of iterations and stores the exit edge to *EXIT. The constant
|
number of iterations and stores the exit edge to *EXIT. The constant
|
giving the number of iterations of LOOP is returned. The number of
|
giving the number of iterations of LOOP is returned. The number of
|
iterations is determined using loop_niter_by_eval (i.e. by brute force
|
iterations is determined using loop_niter_by_eval (i.e. by brute force
|
evaluation). If we are unable to find the exit for that loop_niter_by_eval
|
evaluation). If we are unable to find the exit for that loop_niter_by_eval
|
determines the number of iterations, chrec_dont_know is returned. */
|
determines the number of iterations, chrec_dont_know is returned. */
|
|
|
tree
|
tree
|
find_loop_niter_by_eval (struct loop *loop, edge *exit)
|
find_loop_niter_by_eval (struct loop *loop, edge *exit)
|
{
|
{
|
unsigned n_exits, i;
|
unsigned n_exits, i;
|
edge *exits = get_loop_exit_edges (loop, &n_exits);
|
edge *exits = get_loop_exit_edges (loop, &n_exits);
|
edge ex;
|
edge ex;
|
tree niter = NULL_TREE, aniter;
|
tree niter = NULL_TREE, aniter;
|
|
|
*exit = NULL;
|
*exit = NULL;
|
for (i = 0; i < n_exits; i++)
|
for (i = 0; i < n_exits; i++)
|
{
|
{
|
ex = exits[i];
|
ex = exits[i];
|
if (!just_once_each_iteration_p (loop, ex->src))
|
if (!just_once_each_iteration_p (loop, ex->src))
|
continue;
|
continue;
|
|
|
aniter = loop_niter_by_eval (loop, ex);
|
aniter = loop_niter_by_eval (loop, ex);
|
if (chrec_contains_undetermined (aniter))
|
if (chrec_contains_undetermined (aniter))
|
continue;
|
continue;
|
|
|
if (niter
|
if (niter
|
&& !tree_int_cst_lt (aniter, niter))
|
&& !tree_int_cst_lt (aniter, niter))
|
continue;
|
continue;
|
|
|
niter = aniter;
|
niter = aniter;
|
*exit = ex;
|
*exit = ex;
|
}
|
}
|
free (exits);
|
free (exits);
|
|
|
return niter ? niter : chrec_dont_know;
|
return niter ? niter : chrec_dont_know;
|
}
|
}
|
|
|
/*
|
/*
|
|
|
Analysis of upper bounds on number of iterations of a loop.
|
Analysis of upper bounds on number of iterations of a loop.
|
|
|
*/
|
*/
|
|
|
/* Returns true if we can prove that COND ==> VAL >= 0. */
|
/* Returns true if we can prove that COND ==> VAL >= 0. */
|
|
|
static bool
|
static bool
|
implies_nonnegative_p (tree cond, tree val)
|
implies_nonnegative_p (tree cond, tree val)
|
{
|
{
|
tree type = TREE_TYPE (val);
|
tree type = TREE_TYPE (val);
|
tree compare;
|
tree compare;
|
|
|
if (tree_expr_nonnegative_p (val))
|
if (tree_expr_nonnegative_p (val))
|
return true;
|
return true;
|
|
|
if (nonzero_p (cond))
|
if (nonzero_p (cond))
|
return false;
|
return false;
|
|
|
compare = fold_build2 (GE_EXPR,
|
compare = fold_build2 (GE_EXPR,
|
boolean_type_node, val, build_int_cst (type, 0));
|
boolean_type_node, val, build_int_cst (type, 0));
|
compare = tree_simplify_using_condition_1 (cond, compare);
|
compare = tree_simplify_using_condition_1 (cond, compare);
|
|
|
return nonzero_p (compare);
|
return nonzero_p (compare);
|
}
|
}
|
|
|
/* Returns true if we can prove that COND ==> A >= B. */
|
/* Returns true if we can prove that COND ==> A >= B. */
|
|
|
static bool
|
static bool
|
implies_ge_p (tree cond, tree a, tree b)
|
implies_ge_p (tree cond, tree a, tree b)
|
{
|
{
|
tree compare = fold_build2 (GE_EXPR, boolean_type_node, a, b);
|
tree compare = fold_build2 (GE_EXPR, boolean_type_node, a, b);
|
|
|
if (nonzero_p (compare))
|
if (nonzero_p (compare))
|
return true;
|
return true;
|
|
|
if (nonzero_p (cond))
|
if (nonzero_p (cond))
|
return false;
|
return false;
|
|
|
compare = tree_simplify_using_condition_1 (cond, compare);
|
compare = tree_simplify_using_condition_1 (cond, compare);
|
|
|
return nonzero_p (compare);
|
return nonzero_p (compare);
|
}
|
}
|
|
|
/* Returns a constant upper bound on the value of expression VAL. VAL
|
/* Returns a constant upper bound on the value of expression VAL. VAL
|
is considered to be unsigned. If its type is signed, its value must
|
is considered to be unsigned. If its type is signed, its value must
|
be nonnegative.
|
be nonnegative.
|
|
|
The condition ADDITIONAL must be satisfied (for example, if VAL is
|
The condition ADDITIONAL must be satisfied (for example, if VAL is
|
"(unsigned) n" and ADDITIONAL is "n > 0", then we can derive that
|
"(unsigned) n" and ADDITIONAL is "n > 0", then we can derive that
|
VAL is at most (unsigned) MAX_INT). */
|
VAL is at most (unsigned) MAX_INT). */
|
|
|
static double_int
|
static double_int
|
derive_constant_upper_bound (tree val, tree additional)
|
derive_constant_upper_bound (tree val, tree additional)
|
{
|
{
|
tree type = TREE_TYPE (val);
|
tree type = TREE_TYPE (val);
|
tree op0, op1, subtype, maxt;
|
tree op0, op1, subtype, maxt;
|
double_int bnd, max, mmax, cst;
|
double_int bnd, max, mmax, cst;
|
|
|
if (INTEGRAL_TYPE_P (type))
|
if (INTEGRAL_TYPE_P (type))
|
maxt = TYPE_MAX_VALUE (type);
|
maxt = TYPE_MAX_VALUE (type);
|
else
|
else
|
maxt = upper_bound_in_type (type, type);
|
maxt = upper_bound_in_type (type, type);
|
|
|
max = tree_to_double_int (maxt);
|
max = tree_to_double_int (maxt);
|
|
|
switch (TREE_CODE (val))
|
switch (TREE_CODE (val))
|
{
|
{
|
case INTEGER_CST:
|
case INTEGER_CST:
|
return tree_to_double_int (val);
|
return tree_to_double_int (val);
|
|
|
case NOP_EXPR:
|
case NOP_EXPR:
|
case CONVERT_EXPR:
|
case CONVERT_EXPR:
|
op0 = TREE_OPERAND (val, 0);
|
op0 = TREE_OPERAND (val, 0);
|
subtype = TREE_TYPE (op0);
|
subtype = TREE_TYPE (op0);
|
if (!TYPE_UNSIGNED (subtype)
|
if (!TYPE_UNSIGNED (subtype)
|
/* If TYPE is also signed, the fact that VAL is nonnegative implies
|
/* If TYPE is also signed, the fact that VAL is nonnegative implies
|
that OP0 is nonnegative. */
|
that OP0 is nonnegative. */
|
&& TYPE_UNSIGNED (type)
|
&& TYPE_UNSIGNED (type)
|
&& !implies_nonnegative_p (additional, op0))
|
&& !implies_nonnegative_p (additional, op0))
|
{
|
{
|
/* If we cannot prove that the casted expression is nonnegative,
|
/* If we cannot prove that the casted expression is nonnegative,
|
we cannot establish more useful upper bound than the precision
|
we cannot establish more useful upper bound than the precision
|
of the type gives us. */
|
of the type gives us. */
|
return max;
|
return max;
|
}
|
}
|
|
|
/* We now know that op0 is an nonnegative value. Try deriving an upper
|
/* We now know that op0 is an nonnegative value. Try deriving an upper
|
bound for it. */
|
bound for it. */
|
bnd = derive_constant_upper_bound (op0, additional);
|
bnd = derive_constant_upper_bound (op0, additional);
|
|
|
/* If the bound does not fit in TYPE, max. value of TYPE could be
|
/* If the bound does not fit in TYPE, max. value of TYPE could be
|
attained. */
|
attained. */
|
if (double_int_ucmp (max, bnd) < 0)
|
if (double_int_ucmp (max, bnd) < 0)
|
return max;
|
return max;
|
|
|
return bnd;
|
return bnd;
|
|
|
case PLUS_EXPR:
|
case PLUS_EXPR:
|
case MINUS_EXPR:
|
case MINUS_EXPR:
|
op0 = TREE_OPERAND (val, 0);
|
op0 = TREE_OPERAND (val, 0);
|
op1 = TREE_OPERAND (val, 1);
|
op1 = TREE_OPERAND (val, 1);
|
|
|
if (TREE_CODE (op1) != INTEGER_CST
|
if (TREE_CODE (op1) != INTEGER_CST
|
|| !implies_nonnegative_p (additional, op0))
|
|| !implies_nonnegative_p (additional, op0))
|
return max;
|
return max;
|
|
|
/* Canonicalize to OP0 - CST. Consider CST to be signed, in order to
|
/* Canonicalize to OP0 - CST. Consider CST to be signed, in order to
|
choose the most logical way how to treat this constant regardless
|
choose the most logical way how to treat this constant regardless
|
of the signedness of the type. */
|
of the signedness of the type. */
|
cst = tree_to_double_int (op1);
|
cst = tree_to_double_int (op1);
|
cst = double_int_sext (cst, TYPE_PRECISION (type));
|
cst = double_int_sext (cst, TYPE_PRECISION (type));
|
if (TREE_CODE (val) == PLUS_EXPR)
|
if (TREE_CODE (val) == PLUS_EXPR)
|
cst = double_int_neg (cst);
|
cst = double_int_neg (cst);
|
|
|
bnd = derive_constant_upper_bound (op0, additional);
|
bnd = derive_constant_upper_bound (op0, additional);
|
|
|
if (double_int_negative_p (cst))
|
if (double_int_negative_p (cst))
|
{
|
{
|
cst = double_int_neg (cst);
|
cst = double_int_neg (cst);
|
/* Avoid CST == 0x80000... */
|
/* Avoid CST == 0x80000... */
|
if (double_int_negative_p (cst))
|
if (double_int_negative_p (cst))
|
return max;;
|
return max;;
|
|
|
/* OP0 + CST. We need to check that
|
/* OP0 + CST. We need to check that
|
BND <= MAX (type) - CST. */
|
BND <= MAX (type) - CST. */
|
|
|
mmax = double_int_add (max, double_int_neg (cst));
|
mmax = double_int_add (max, double_int_neg (cst));
|
if (double_int_ucmp (bnd, mmax) > 0)
|
if (double_int_ucmp (bnd, mmax) > 0)
|
return max;
|
return max;
|
|
|
return double_int_add (bnd, cst);
|
return double_int_add (bnd, cst);
|
}
|
}
|
else
|
else
|
{
|
{
|
/* OP0 - CST, where CST >= 0.
|
/* OP0 - CST, where CST >= 0.
|
|
|
If TYPE is signed, we have already verified that OP0 >= 0, and we
|
If TYPE is signed, we have already verified that OP0 >= 0, and we
|
know that the result is nonnegative. This implies that
|
know that the result is nonnegative. This implies that
|
VAL <= BND - CST.
|
VAL <= BND - CST.
|
|
|
If TYPE is unsigned, we must additionally know that OP0 >= CST,
|
If TYPE is unsigned, we must additionally know that OP0 >= CST,
|
otherwise the operation underflows.
|
otherwise the operation underflows.
|
*/
|
*/
|
|
|
/* This should only happen if the type is unsigned; however, for
|
/* This should only happen if the type is unsigned; however, for
|
programs that use overflowing signed arithmetics even with
|
programs that use overflowing signed arithmetics even with
|
-fno-wrapv, this condition may also be true for signed values. */
|
-fno-wrapv, this condition may also be true for signed values. */
|
if (double_int_ucmp (bnd, cst) < 0)
|
if (double_int_ucmp (bnd, cst) < 0)
|
return max;
|
return max;
|
|
|
if (TYPE_UNSIGNED (type)
|
if (TYPE_UNSIGNED (type)
|
&& !implies_ge_p (additional,
|
&& !implies_ge_p (additional,
|
op0, double_int_to_tree (type, cst)))
|
op0, double_int_to_tree (type, cst)))
|
return max;
|
return max;
|
|
|
bnd = double_int_add (bnd, double_int_neg (cst));
|
bnd = double_int_add (bnd, double_int_neg (cst));
|
}
|
}
|
|
|
return bnd;
|
return bnd;
|
|
|
case FLOOR_DIV_EXPR:
|
case FLOOR_DIV_EXPR:
|
case EXACT_DIV_EXPR:
|
case EXACT_DIV_EXPR:
|
op0 = TREE_OPERAND (val, 0);
|
op0 = TREE_OPERAND (val, 0);
|
op1 = TREE_OPERAND (val, 1);
|
op1 = TREE_OPERAND (val, 1);
|
if (TREE_CODE (op1) != INTEGER_CST
|
if (TREE_CODE (op1) != INTEGER_CST
|
|| tree_int_cst_sign_bit (op1))
|
|| tree_int_cst_sign_bit (op1))
|
return max;
|
return max;
|
|
|
bnd = derive_constant_upper_bound (op0, additional);
|
bnd = derive_constant_upper_bound (op0, additional);
|
return double_int_udiv (bnd, tree_to_double_int (op1), FLOOR_DIV_EXPR);
|
return double_int_udiv (bnd, tree_to_double_int (op1), FLOOR_DIV_EXPR);
|
|
|
default:
|
default:
|
return max;
|
return max;
|
}
|
}
|
}
|
}
|
|
|
/* Records that AT_STMT is executed at most BOUND times in LOOP. The
|
/* Records that AT_STMT is executed at most BOUND times in LOOP. The
|
additional condition ADDITIONAL is recorded with the bound. */
|
additional condition ADDITIONAL is recorded with the bound. */
|
|
|
void
|
void
|
record_estimate (struct loop *loop, tree bound, tree additional, tree at_stmt)
|
record_estimate (struct loop *loop, tree bound, tree additional, tree at_stmt)
|
{
|
{
|
struct nb_iter_bound *elt = xmalloc (sizeof (struct nb_iter_bound));
|
struct nb_iter_bound *elt = xmalloc (sizeof (struct nb_iter_bound));
|
double_int i_bound = derive_constant_upper_bound (bound, additional);
|
double_int i_bound = derive_constant_upper_bound (bound, additional);
|
tree c_bound = double_int_to_tree (unsigned_type_for (TREE_TYPE (bound)),
|
tree c_bound = double_int_to_tree (unsigned_type_for (TREE_TYPE (bound)),
|
i_bound);
|
i_bound);
|
|
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
{
|
{
|
fprintf (dump_file, "Statements after ");
|
fprintf (dump_file, "Statements after ");
|
print_generic_expr (dump_file, at_stmt, TDF_SLIM);
|
print_generic_expr (dump_file, at_stmt, TDF_SLIM);
|
fprintf (dump_file, " are executed at most ");
|
fprintf (dump_file, " are executed at most ");
|
print_generic_expr (dump_file, bound, TDF_SLIM);
|
print_generic_expr (dump_file, bound, TDF_SLIM);
|
fprintf (dump_file, " (bounded by ");
|
fprintf (dump_file, " (bounded by ");
|
print_generic_expr (dump_file, c_bound, TDF_SLIM);
|
print_generic_expr (dump_file, c_bound, TDF_SLIM);
|
fprintf (dump_file, ") times in loop %d.\n", loop->num);
|
fprintf (dump_file, ") times in loop %d.\n", loop->num);
|
}
|
}
|
|
|
elt->bound = c_bound;
|
elt->bound = c_bound;
|
elt->at_stmt = at_stmt;
|
elt->at_stmt = at_stmt;
|
elt->next = loop->bounds;
|
elt->next = loop->bounds;
|
loop->bounds = elt;
|
loop->bounds = elt;
|
}
|
}
|
|
|
/* Initialize LOOP->ESTIMATED_NB_ITERATIONS with the lowest safe
|
/* Initialize LOOP->ESTIMATED_NB_ITERATIONS with the lowest safe
|
approximation of the number of iterations for LOOP. */
|
approximation of the number of iterations for LOOP. */
|
|
|
static void
|
static void
|
compute_estimated_nb_iterations (struct loop *loop)
|
compute_estimated_nb_iterations (struct loop *loop)
|
{
|
{
|
struct nb_iter_bound *bound;
|
struct nb_iter_bound *bound;
|
|
|
for (bound = loop->bounds; bound; bound = bound->next)
|
for (bound = loop->bounds; bound; bound = bound->next)
|
{
|
{
|
if (TREE_CODE (bound->bound) != INTEGER_CST)
|
if (TREE_CODE (bound->bound) != INTEGER_CST)
|
continue;
|
continue;
|
|
|
/* Update only when there is no previous estimation, or when the current
|
/* Update only when there is no previous estimation, or when the current
|
estimation is smaller. */
|
estimation is smaller. */
|
if (chrec_contains_undetermined (loop->estimated_nb_iterations)
|
if (chrec_contains_undetermined (loop->estimated_nb_iterations)
|
|| tree_int_cst_lt (bound->bound, loop->estimated_nb_iterations))
|
|| tree_int_cst_lt (bound->bound, loop->estimated_nb_iterations))
|
loop->estimated_nb_iterations = bound->bound;
|
loop->estimated_nb_iterations = bound->bound;
|
}
|
}
|
}
|
}
|
|
|
/* The following analyzers are extracting informations on the bounds
|
/* The following analyzers are extracting informations on the bounds
|
of LOOP from the following undefined behaviors:
|
of LOOP from the following undefined behaviors:
|
|
|
- data references should not access elements over the statically
|
- data references should not access elements over the statically
|
allocated size,
|
allocated size,
|
|
|
- signed variables should not overflow when flag_wrapv is not set.
|
- signed variables should not overflow when flag_wrapv is not set.
|
*/
|
*/
|
|
|
static void
|
static void
|
infer_loop_bounds_from_undefined (struct loop *loop)
|
infer_loop_bounds_from_undefined (struct loop *loop)
|
{
|
{
|
unsigned i;
|
unsigned i;
|
basic_block bb, *bbs;
|
basic_block bb, *bbs;
|
block_stmt_iterator bsi;
|
block_stmt_iterator bsi;
|
|
|
bbs = get_loop_body (loop);
|
bbs = get_loop_body (loop);
|
|
|
for (i = 0; i < loop->num_nodes; i++)
|
for (i = 0; i < loop->num_nodes; i++)
|
{
|
{
|
bb = bbs[i];
|
bb = bbs[i];
|
|
|
/* If BB is not executed in each iteration of the loop, we cannot
|
/* If BB is not executed in each iteration of the loop, we cannot
|
use the operations in it to infer reliable upper bound on the
|
use the operations in it to infer reliable upper bound on the
|
# of iterations of the loop. */
|
# of iterations of the loop. */
|
if (!dominated_by_p (CDI_DOMINATORS, loop->latch, bb))
|
if (!dominated_by_p (CDI_DOMINATORS, loop->latch, bb))
|
continue;
|
continue;
|
|
|
for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
|
for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
|
{
|
{
|
tree stmt = bsi_stmt (bsi);
|
tree stmt = bsi_stmt (bsi);
|
|
|
switch (TREE_CODE (stmt))
|
switch (TREE_CODE (stmt))
|
{
|
{
|
case MODIFY_EXPR:
|
case MODIFY_EXPR:
|
{
|
{
|
tree op0 = TREE_OPERAND (stmt, 0);
|
tree op0 = TREE_OPERAND (stmt, 0);
|
tree op1 = TREE_OPERAND (stmt, 1);
|
tree op1 = TREE_OPERAND (stmt, 1);
|
|
|
/* For each array access, analyze its access function
|
/* For each array access, analyze its access function
|
and record a bound on the loop iteration domain. */
|
and record a bound on the loop iteration domain. */
|
if (TREE_CODE (op1) == ARRAY_REF
|
if (TREE_CODE (op1) == ARRAY_REF
|
&& !array_ref_contains_indirect_ref (op1))
|
&& !array_ref_contains_indirect_ref (op1))
|
estimate_iters_using_array (stmt, op1);
|
estimate_iters_using_array (stmt, op1);
|
|
|
if (TREE_CODE (op0) == ARRAY_REF
|
if (TREE_CODE (op0) == ARRAY_REF
|
&& !array_ref_contains_indirect_ref (op0))
|
&& !array_ref_contains_indirect_ref (op0))
|
estimate_iters_using_array (stmt, op0);
|
estimate_iters_using_array (stmt, op0);
|
|
|
/* For each signed type variable in LOOP, analyze its
|
/* For each signed type variable in LOOP, analyze its
|
scalar evolution and record a bound of the loop
|
scalar evolution and record a bound of the loop
|
based on the type's ranges. */
|
based on the type's ranges. */
|
else if (!flag_wrapv && TREE_CODE (op0) == SSA_NAME)
|
else if (!flag_wrapv && TREE_CODE (op0) == SSA_NAME)
|
{
|
{
|
tree init, step, diff, estimation;
|
tree init, step, diff, estimation;
|
tree scev = instantiate_parameters
|
tree scev = instantiate_parameters
|
(loop, analyze_scalar_evolution (loop, op0));
|
(loop, analyze_scalar_evolution (loop, op0));
|
tree type = chrec_type (scev);
|
tree type = chrec_type (scev);
|
|
|
if (chrec_contains_undetermined (scev)
|
if (chrec_contains_undetermined (scev)
|
|| TYPE_OVERFLOW_WRAPS (type))
|
|| TYPE_OVERFLOW_WRAPS (type))
|
break;
|
break;
|
|
|
init = initial_condition_in_loop_num (scev, loop->num);
|
init = initial_condition_in_loop_num (scev, loop->num);
|
step = evolution_part_in_loop_num (scev, loop->num);
|
step = evolution_part_in_loop_num (scev, loop->num);
|
|
|
if (init == NULL_TREE
|
if (init == NULL_TREE
|
|| step == NULL_TREE
|
|| step == NULL_TREE
|
|| TREE_CODE (init) != INTEGER_CST
|
|| TREE_CODE (init) != INTEGER_CST
|
|| TREE_CODE (step) != INTEGER_CST
|
|| TREE_CODE (step) != INTEGER_CST
|
|| TYPE_MIN_VALUE (type) == NULL_TREE
|
|| TYPE_MIN_VALUE (type) == NULL_TREE
|
|| TYPE_MAX_VALUE (type) == NULL_TREE)
|
|| TYPE_MAX_VALUE (type) == NULL_TREE)
|
break;
|
break;
|
|
|
if (integer_nonzerop (step))
|
if (integer_nonzerop (step))
|
{
|
{
|
tree utype;
|
tree utype;
|
|
|
if (tree_int_cst_lt (step, integer_zero_node))
|
if (tree_int_cst_lt (step, integer_zero_node))
|
diff = fold_build2 (MINUS_EXPR, type, init,
|
diff = fold_build2 (MINUS_EXPR, type, init,
|
TYPE_MIN_VALUE (type));
|
TYPE_MIN_VALUE (type));
|
else
|
else
|
diff = fold_build2 (MINUS_EXPR, type,
|
diff = fold_build2 (MINUS_EXPR, type,
|
TYPE_MAX_VALUE (type), init);
|
TYPE_MAX_VALUE (type), init);
|
|
|
utype = unsigned_type_for (type);
|
utype = unsigned_type_for (type);
|
estimation = fold_build2 (CEIL_DIV_EXPR, type, diff,
|
estimation = fold_build2 (CEIL_DIV_EXPR, type, diff,
|
step);
|
step);
|
record_estimate (loop,
|
record_estimate (loop,
|
fold_convert (utype, estimation),
|
fold_convert (utype, estimation),
|
boolean_true_node, stmt);
|
boolean_true_node, stmt);
|
}
|
}
|
}
|
}
|
|
|
break;
|
break;
|
}
|
}
|
|
|
case CALL_EXPR:
|
case CALL_EXPR:
|
{
|
{
|
tree args;
|
tree args;
|
|
|
for (args = TREE_OPERAND (stmt, 1); args;
|
for (args = TREE_OPERAND (stmt, 1); args;
|
args = TREE_CHAIN (args))
|
args = TREE_CHAIN (args))
|
if (TREE_CODE (TREE_VALUE (args)) == ARRAY_REF
|
if (TREE_CODE (TREE_VALUE (args)) == ARRAY_REF
|
&& !array_ref_contains_indirect_ref (TREE_VALUE (args)))
|
&& !array_ref_contains_indirect_ref (TREE_VALUE (args)))
|
estimate_iters_using_array (stmt, TREE_VALUE (args));
|
estimate_iters_using_array (stmt, TREE_VALUE (args));
|
|
|
break;
|
break;
|
}
|
}
|
|
|
default:
|
default:
|
break;
|
break;
|
}
|
}
|
}
|
}
|
}
|
}
|
|
|
compute_estimated_nb_iterations (loop);
|
compute_estimated_nb_iterations (loop);
|
free (bbs);
|
free (bbs);
|
}
|
}
|
|
|
/* Records estimates on numbers of iterations of LOOP. */
|
/* Records estimates on numbers of iterations of LOOP. */
|
|
|
static void
|
static void
|
estimate_numbers_of_iterations_loop (struct loop *loop)
|
estimate_numbers_of_iterations_loop (struct loop *loop)
|
{
|
{
|
edge *exits;
|
edge *exits;
|
tree niter, type;
|
tree niter, type;
|
unsigned i, n_exits;
|
unsigned i, n_exits;
|
struct tree_niter_desc niter_desc;
|
struct tree_niter_desc niter_desc;
|
|
|
/* Give up if we already have tried to compute an estimation. */
|
/* Give up if we already have tried to compute an estimation. */
|
if (loop->estimated_nb_iterations == chrec_dont_know
|
if (loop->estimated_nb_iterations == chrec_dont_know
|
/* Or when we already have an estimation. */
|
/* Or when we already have an estimation. */
|
|| (loop->estimated_nb_iterations != NULL_TREE
|
|| (loop->estimated_nb_iterations != NULL_TREE
|
&& TREE_CODE (loop->estimated_nb_iterations) == INTEGER_CST))
|
&& TREE_CODE (loop->estimated_nb_iterations) == INTEGER_CST))
|
return;
|
return;
|
else
|
else
|
loop->estimated_nb_iterations = chrec_dont_know;
|
loop->estimated_nb_iterations = chrec_dont_know;
|
|
|
exits = get_loop_exit_edges (loop, &n_exits);
|
exits = get_loop_exit_edges (loop, &n_exits);
|
for (i = 0; i < n_exits; i++)
|
for (i = 0; i < n_exits; i++)
|
{
|
{
|
if (!number_of_iterations_exit (loop, exits[i], &niter_desc, false))
|
if (!number_of_iterations_exit (loop, exits[i], &niter_desc, false))
|
continue;
|
continue;
|
|
|
niter = niter_desc.niter;
|
niter = niter_desc.niter;
|
type = TREE_TYPE (niter);
|
type = TREE_TYPE (niter);
|
if (!zero_p (niter_desc.may_be_zero)
|
if (!zero_p (niter_desc.may_be_zero)
|
&& !nonzero_p (niter_desc.may_be_zero))
|
&& !nonzero_p (niter_desc.may_be_zero))
|
niter = build3 (COND_EXPR, type, niter_desc.may_be_zero,
|
niter = build3 (COND_EXPR, type, niter_desc.may_be_zero,
|
build_int_cst (type, 0),
|
build_int_cst (type, 0),
|
niter);
|
niter);
|
record_estimate (loop, niter,
|
record_estimate (loop, niter,
|
niter_desc.additional_info,
|
niter_desc.additional_info,
|
last_stmt (exits[i]->src));
|
last_stmt (exits[i]->src));
|
}
|
}
|
free (exits);
|
free (exits);
|
|
|
if (chrec_contains_undetermined (loop->estimated_nb_iterations))
|
if (chrec_contains_undetermined (loop->estimated_nb_iterations))
|
infer_loop_bounds_from_undefined (loop);
|
infer_loop_bounds_from_undefined (loop);
|
}
|
}
|
|
|
/* Records estimates on numbers of iterations of LOOPS. */
|
/* Records estimates on numbers of iterations of LOOPS. */
|
|
|
void
|
void
|
estimate_numbers_of_iterations (struct loops *loops)
|
estimate_numbers_of_iterations (struct loops *loops)
|
{
|
{
|
unsigned i;
|
unsigned i;
|
struct loop *loop;
|
struct loop *loop;
|
|
|
/* We don't want to issue signed overflow warnings while getting
|
/* We don't want to issue signed overflow warnings while getting
|
loop iteration estimates. */
|
loop iteration estimates. */
|
fold_defer_overflow_warnings ();
|
fold_defer_overflow_warnings ();
|
|
|
for (i = 1; i < loops->num; i++)
|
for (i = 1; i < loops->num; i++)
|
{
|
{
|
loop = loops->parray[i];
|
loop = loops->parray[i];
|
if (loop)
|
if (loop)
|
estimate_numbers_of_iterations_loop (loop);
|
estimate_numbers_of_iterations_loop (loop);
|
}
|
}
|
|
|
fold_undefer_and_ignore_overflow_warnings ();
|
fold_undefer_and_ignore_overflow_warnings ();
|
}
|
}
|
|
|
/* Returns true if statement S1 dominates statement S2. */
|
/* Returns true if statement S1 dominates statement S2. */
|
|
|
static bool
|
static bool
|
stmt_dominates_stmt_p (tree s1, tree s2)
|
stmt_dominates_stmt_p (tree s1, tree s2)
|
{
|
{
|
basic_block bb1 = bb_for_stmt (s1), bb2 = bb_for_stmt (s2);
|
basic_block bb1 = bb_for_stmt (s1), bb2 = bb_for_stmt (s2);
|
|
|
if (!bb1
|
if (!bb1
|
|| s1 == s2)
|
|| s1 == s2)
|
return true;
|
return true;
|
|
|
if (bb1 == bb2)
|
if (bb1 == bb2)
|
{
|
{
|
block_stmt_iterator bsi;
|
block_stmt_iterator bsi;
|
|
|
for (bsi = bsi_start (bb1); bsi_stmt (bsi) != s2; bsi_next (&bsi))
|
for (bsi = bsi_start (bb1); bsi_stmt (bsi) != s2; bsi_next (&bsi))
|
if (bsi_stmt (bsi) == s1)
|
if (bsi_stmt (bsi) == s1)
|
return true;
|
return true;
|
|
|
return false;
|
return false;
|
}
|
}
|
|
|
return dominated_by_p (CDI_DOMINATORS, bb2, bb1);
|
return dominated_by_p (CDI_DOMINATORS, bb2, bb1);
|
}
|
}
|
|
|
/* Returns true when we can prove that the number of executions of
|
/* Returns true when we can prove that the number of executions of
|
STMT in the loop is at most NITER, according to the fact
|
STMT in the loop is at most NITER, according to the fact
|
that the statement NITER_BOUND->at_stmt is executed at most
|
that the statement NITER_BOUND->at_stmt is executed at most
|
NITER_BOUND->bound times. */
|
NITER_BOUND->bound times. */
|
|
|
static bool
|
static bool
|
n_of_executions_at_most (tree stmt,
|
n_of_executions_at_most (tree stmt,
|
struct nb_iter_bound *niter_bound,
|
struct nb_iter_bound *niter_bound,
|
tree niter)
|
tree niter)
|
{
|
{
|
tree cond;
|
tree cond;
|
tree bound = niter_bound->bound;
|
tree bound = niter_bound->bound;
|
tree bound_type = TREE_TYPE (bound);
|
tree bound_type = TREE_TYPE (bound);
|
tree nit_type = TREE_TYPE (niter);
|
tree nit_type = TREE_TYPE (niter);
|
enum tree_code cmp;
|
enum tree_code cmp;
|
|
|
gcc_assert (TYPE_UNSIGNED (bound_type)
|
gcc_assert (TYPE_UNSIGNED (bound_type)
|
&& TYPE_UNSIGNED (nit_type)
|
&& TYPE_UNSIGNED (nit_type)
|
&& is_gimple_min_invariant (bound));
|
&& is_gimple_min_invariant (bound));
|
if (TYPE_PRECISION (nit_type) > TYPE_PRECISION (bound_type))
|
if (TYPE_PRECISION (nit_type) > TYPE_PRECISION (bound_type))
|
bound = fold_convert (nit_type, bound);
|
bound = fold_convert (nit_type, bound);
|
else
|
else
|
niter = fold_convert (bound_type, niter);
|
niter = fold_convert (bound_type, niter);
|
|
|
/* After the statement niter_bound->at_stmt we know that anything is
|
/* After the statement niter_bound->at_stmt we know that anything is
|
executed at most BOUND times. */
|
executed at most BOUND times. */
|
if (stmt && stmt_dominates_stmt_p (niter_bound->at_stmt, stmt))
|
if (stmt && stmt_dominates_stmt_p (niter_bound->at_stmt, stmt))
|
cmp = GE_EXPR;
|
cmp = GE_EXPR;
|
/* Before the statement niter_bound->at_stmt we know that anything
|
/* Before the statement niter_bound->at_stmt we know that anything
|
is executed at most BOUND + 1 times. */
|
is executed at most BOUND + 1 times. */
|
else
|
else
|
cmp = GT_EXPR;
|
cmp = GT_EXPR;
|
|
|
cond = fold_binary (cmp, boolean_type_node, niter, bound);
|
cond = fold_binary (cmp, boolean_type_node, niter, bound);
|
return nonzero_p (cond);
|
return nonzero_p (cond);
|
}
|
}
|
|
|
/* Returns true if the arithmetics in TYPE can be assumed not to wrap. */
|
/* Returns true if the arithmetics in TYPE can be assumed not to wrap. */
|
|
|
bool
|
bool
|
nowrap_type_p (tree type)
|
nowrap_type_p (tree type)
|
{
|
{
|
if (INTEGRAL_TYPE_P (type)
|
if (INTEGRAL_TYPE_P (type)
|
&& TYPE_OVERFLOW_UNDEFINED (type))
|
&& TYPE_OVERFLOW_UNDEFINED (type))
|
return true;
|
return true;
|
|
|
if (POINTER_TYPE_P (type))
|
if (POINTER_TYPE_P (type))
|
return true;
|
return true;
|
|
|
return false;
|
return false;
|
}
|
}
|
|
|
/* Return false only when the induction variable BASE + STEP * I is
|
/* Return false only when the induction variable BASE + STEP * I is
|
known to not overflow: i.e. when the number of iterations is small
|
known to not overflow: i.e. when the number of iterations is small
|
enough with respect to the step and initial condition in order to
|
enough with respect to the step and initial condition in order to
|
keep the evolution confined in TYPEs bounds. Return true when the
|
keep the evolution confined in TYPEs bounds. Return true when the
|
iv is known to overflow or when the property is not computable.
|
iv is known to overflow or when the property is not computable.
|
|
|
USE_OVERFLOW_SEMANTICS is true if this function should assume that
|
USE_OVERFLOW_SEMANTICS is true if this function should assume that
|
the rules for overflow of the given language apply (e.g., that signed
|
the rules for overflow of the given language apply (e.g., that signed
|
arithmetics in C does not overflow). */
|
arithmetics in C does not overflow). */
|
|
|
bool
|
bool
|
scev_probably_wraps_p (tree base, tree step,
|
scev_probably_wraps_p (tree base, tree step,
|
tree at_stmt, struct loop *loop,
|
tree at_stmt, struct loop *loop,
|
bool use_overflow_semantics)
|
bool use_overflow_semantics)
|
{
|
{
|
struct nb_iter_bound *bound;
|
struct nb_iter_bound *bound;
|
tree delta, step_abs;
|
tree delta, step_abs;
|
tree unsigned_type, valid_niter;
|
tree unsigned_type, valid_niter;
|
tree type = TREE_TYPE (step);
|
tree type = TREE_TYPE (step);
|
|
|
/* FIXME: We really need something like
|
/* FIXME: We really need something like
|
http://gcc.gnu.org/ml/gcc-patches/2005-06/msg02025.html.
|
http://gcc.gnu.org/ml/gcc-patches/2005-06/msg02025.html.
|
|
|
We used to test for the following situation that frequently appears
|
We used to test for the following situation that frequently appears
|
during address arithmetics:
|
during address arithmetics:
|
|
|
D.1621_13 = (long unsigned intD.4) D.1620_12;
|
D.1621_13 = (long unsigned intD.4) D.1620_12;
|
D.1622_14 = D.1621_13 * 8;
|
D.1622_14 = D.1621_13 * 8;
|
D.1623_15 = (doubleD.29 *) D.1622_14;
|
D.1623_15 = (doubleD.29 *) D.1622_14;
|
|
|
And derived that the sequence corresponding to D_14
|
And derived that the sequence corresponding to D_14
|
can be proved to not wrap because it is used for computing a
|
can be proved to not wrap because it is used for computing a
|
memory access; however, this is not really the case -- for example,
|
memory access; however, this is not really the case -- for example,
|
if D_12 = (unsigned char) [254,+,1], then D_14 has values
|
if D_12 = (unsigned char) [254,+,1], then D_14 has values
|
2032, 2040, 0, 8, ..., but the code is still legal. */
|
2032, 2040, 0, 8, ..., but the code is still legal. */
|
|
|
if (chrec_contains_undetermined (base)
|
if (chrec_contains_undetermined (base)
|
|| chrec_contains_undetermined (step)
|
|| chrec_contains_undetermined (step)
|
|| TREE_CODE (step) != INTEGER_CST)
|
|| TREE_CODE (step) != INTEGER_CST)
|
return true;
|
return true;
|
|
|
if (zero_p (step))
|
if (zero_p (step))
|
return false;
|
return false;
|
|
|
/* If we can use the fact that signed and pointer arithmetics does not
|
/* If we can use the fact that signed and pointer arithmetics does not
|
wrap, we are done. */
|
wrap, we are done. */
|
if (use_overflow_semantics && nowrap_type_p (type))
|
if (use_overflow_semantics && nowrap_type_p (type))
|
return false;
|
return false;
|
|
|
/* Don't issue signed overflow warnings. */
|
/* Don't issue signed overflow warnings. */
|
fold_defer_overflow_warnings ();
|
fold_defer_overflow_warnings ();
|
|
|
/* Otherwise, compute the number of iterations before we reach the
|
/* Otherwise, compute the number of iterations before we reach the
|
bound of the type, and verify that the loop is exited before this
|
bound of the type, and verify that the loop is exited before this
|
occurs. */
|
occurs. */
|
unsigned_type = unsigned_type_for (type);
|
unsigned_type = unsigned_type_for (type);
|
base = fold_convert (unsigned_type, base);
|
base = fold_convert (unsigned_type, base);
|
|
|
if (tree_int_cst_sign_bit (step))
|
if (tree_int_cst_sign_bit (step))
|
{
|
{
|
tree extreme = fold_convert (unsigned_type,
|
tree extreme = fold_convert (unsigned_type,
|
lower_bound_in_type (type, type));
|
lower_bound_in_type (type, type));
|
delta = fold_build2 (MINUS_EXPR, unsigned_type, base, extreme);
|
delta = fold_build2 (MINUS_EXPR, unsigned_type, base, extreme);
|
step_abs = fold_build1 (NEGATE_EXPR, unsigned_type,
|
step_abs = fold_build1 (NEGATE_EXPR, unsigned_type,
|
fold_convert (unsigned_type, step));
|
fold_convert (unsigned_type, step));
|
}
|
}
|
else
|
else
|
{
|
{
|
tree extreme = fold_convert (unsigned_type,
|
tree extreme = fold_convert (unsigned_type,
|
upper_bound_in_type (type, type));
|
upper_bound_in_type (type, type));
|
delta = fold_build2 (MINUS_EXPR, unsigned_type, extreme, base);
|
delta = fold_build2 (MINUS_EXPR, unsigned_type, extreme, base);
|
step_abs = fold_convert (unsigned_type, step);
|
step_abs = fold_convert (unsigned_type, step);
|
}
|
}
|
|
|
valid_niter = fold_build2 (FLOOR_DIV_EXPR, unsigned_type, delta, step_abs);
|
valid_niter = fold_build2 (FLOOR_DIV_EXPR, unsigned_type, delta, step_abs);
|
|
|
estimate_numbers_of_iterations_loop (loop);
|
estimate_numbers_of_iterations_loop (loop);
|
for (bound = loop->bounds; bound; bound = bound->next)
|
for (bound = loop->bounds; bound; bound = bound->next)
|
{
|
{
|
if (n_of_executions_at_most (at_stmt, bound, valid_niter))
|
if (n_of_executions_at_most (at_stmt, bound, valid_niter))
|
{
|
{
|
fold_undefer_and_ignore_overflow_warnings ();
|
fold_undefer_and_ignore_overflow_warnings ();
|
return false;
|
return false;
|
}
|
}
|
}
|
}
|
|
|
fold_undefer_and_ignore_overflow_warnings ();
|
fold_undefer_and_ignore_overflow_warnings ();
|
|
|
/* At this point we still don't have a proof that the iv does not
|
/* At this point we still don't have a proof that the iv does not
|
overflow: give up. */
|
overflow: give up. */
|
return true;
|
return true;
|
}
|
}
|
|
|
/* Frees the information on upper bounds on numbers of iterations of LOOP. */
|
/* Frees the information on upper bounds on numbers of iterations of LOOP. */
|
|
|
void
|
void
|
free_numbers_of_iterations_estimates_loop (struct loop *loop)
|
free_numbers_of_iterations_estimates_loop (struct loop *loop)
|
{
|
{
|
struct nb_iter_bound *bound, *next;
|
struct nb_iter_bound *bound, *next;
|
|
|
loop->nb_iterations = NULL;
|
loop->nb_iterations = NULL;
|
loop->estimated_nb_iterations = NULL;
|
loop->estimated_nb_iterations = NULL;
|
for (bound = loop->bounds; bound; bound = next)
|
for (bound = loop->bounds; bound; bound = next)
|
{
|
{
|
next = bound->next;
|
next = bound->next;
|
free (bound);
|
free (bound);
|
}
|
}
|
|
|
loop->bounds = NULL;
|
loop->bounds = NULL;
|
}
|
}
|
|
|
/* Frees the information on upper bounds on numbers of iterations of LOOPS. */
|
/* Frees the information on upper bounds on numbers of iterations of LOOPS. */
|
|
|
void
|
void
|
free_numbers_of_iterations_estimates (struct loops *loops)
|
free_numbers_of_iterations_estimates (struct loops *loops)
|
{
|
{
|
unsigned i;
|
unsigned i;
|
struct loop *loop;
|
struct loop *loop;
|
|
|
for (i = 1; i < loops->num; i++)
|
for (i = 1; i < loops->num; i++)
|
{
|
{
|
loop = loops->parray[i];
|
loop = loops->parray[i];
|
if (loop)
|
if (loop)
|
free_numbers_of_iterations_estimates_loop (loop);
|
free_numbers_of_iterations_estimates_loop (loop);
|
}
|
}
|
}
|
}
|
|
|
/* Substitute value VAL for ssa name NAME inside expressions held
|
/* Substitute value VAL for ssa name NAME inside expressions held
|
at LOOP. */
|
at LOOP. */
|
|
|
void
|
void
|
substitute_in_loop_info (struct loop *loop, tree name, tree val)
|
substitute_in_loop_info (struct loop *loop, tree name, tree val)
|
{
|
{
|
loop->nb_iterations = simplify_replace_tree (loop->nb_iterations, name, val);
|
loop->nb_iterations = simplify_replace_tree (loop->nb_iterations, name, val);
|
loop->estimated_nb_iterations
|
loop->estimated_nb_iterations
|
= simplify_replace_tree (loop->estimated_nb_iterations, name, val);
|
= simplify_replace_tree (loop->estimated_nb_iterations, name, val);
|
}
|
}
|
|
|
