/* 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, 2008 Free Software Foundation,
|
Copyright (C) 2004, 2005, 2006, 2007, 2008 Free Software Foundation,
|
Inc.
|
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"
|
#include "gmp.h"
|
#include "gmp.h"
|
|
|
#define SWAP(X, Y) do { affine_iv *tmp = (X); (X) = (Y); (Y) = tmp; } while (0)
|
#define SWAP(X, Y) do { affine_iv *tmp = (X); (X) = (Y); (Y) = tmp; } while (0)
|
|
|
/* 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
|
|
|
/*
|
/*
|
|
|
Analysis of number of iterations of an affine exit test.
|
Analysis of number of iterations of an affine exit test.
|
|
|
*/
|
*/
|
|
|
/* Bounds on some value, BELOW <= X <= UP. */
|
/* Bounds on some value, BELOW <= X <= UP. */
|
|
|
typedef struct
|
typedef struct
|
{
|
{
|
mpz_t below, up;
|
mpz_t below, up;
|
} bounds;
|
} bounds;
|
|
|
|
|
/* Splits expression EXPR to a variable part VAR and constant OFFSET. */
|
/* Splits expression EXPR to a variable part VAR and constant OFFSET. */
|
|
|
static void
|
static void
|
split_to_var_and_offset (tree expr, tree *var, mpz_t offset)
|
split_to_var_and_offset (tree expr, tree *var, mpz_t offset)
|
{
|
{
|
tree type = TREE_TYPE (expr);
|
tree type = TREE_TYPE (expr);
|
tree op0, op1;
|
tree op0, op1;
|
double_int off;
|
double_int off;
|
bool negate = false;
|
bool negate = false;
|
|
|
*var = expr;
|
*var = expr;
|
mpz_set_ui (offset, 0);
|
mpz_set_ui (offset, 0);
|
|
|
switch (TREE_CODE (expr))
|
switch (TREE_CODE (expr))
|
{
|
{
|
case MINUS_EXPR:
|
case MINUS_EXPR:
|
negate = true;
|
negate = true;
|
/* Fallthru. */
|
/* Fallthru. */
|
|
|
case PLUS_EXPR:
|
case PLUS_EXPR:
|
case POINTER_PLUS_EXPR:
|
case POINTER_PLUS_EXPR:
|
op0 = TREE_OPERAND (expr, 0);
|
op0 = TREE_OPERAND (expr, 0);
|
op1 = TREE_OPERAND (expr, 1);
|
op1 = TREE_OPERAND (expr, 1);
|
|
|
if (TREE_CODE (op1) != INTEGER_CST)
|
if (TREE_CODE (op1) != INTEGER_CST)
|
break;
|
break;
|
|
|
*var = op0;
|
*var = op0;
|
/* Always sign extend the offset. */
|
/* Always sign extend the offset. */
|
off = tree_to_double_int (op1);
|
off = tree_to_double_int (op1);
|
if (negate)
|
if (negate)
|
off = double_int_neg (off);
|
off = double_int_neg (off);
|
off = double_int_sext (off, TYPE_PRECISION (type));
|
off = double_int_sext (off, TYPE_PRECISION (type));
|
mpz_set_double_int (offset, off, false);
|
mpz_set_double_int (offset, off, false);
|
break;
|
break;
|
|
|
case INTEGER_CST:
|
case INTEGER_CST:
|
*var = build_int_cst_type (type, 0);
|
*var = build_int_cst_type (type, 0);
|
off = tree_to_double_int (expr);
|
off = tree_to_double_int (expr);
|
mpz_set_double_int (offset, off, TYPE_UNSIGNED (type));
|
mpz_set_double_int (offset, off, TYPE_UNSIGNED (type));
|
break;
|
break;
|
|
|
default:
|
default:
|
break;
|
break;
|
}
|
}
|
}
|
}
|
|
|
/* Stores estimate on the minimum/maximum value of the expression VAR + OFF
|
/* Stores estimate on the minimum/maximum value of the expression VAR + OFF
|
in TYPE to MIN and MAX. */
|
in TYPE to MIN and MAX. */
|
|
|
static void
|
static void
|
determine_value_range (tree type, tree var, mpz_t off,
|
determine_value_range (tree type, tree var, mpz_t off,
|
mpz_t min, mpz_t max)
|
mpz_t min, mpz_t max)
|
{
|
{
|
/* If the expression is a constant, we know its value exactly. */
|
/* If the expression is a constant, we know its value exactly. */
|
if (integer_zerop (var))
|
if (integer_zerop (var))
|
{
|
{
|
mpz_set (min, off);
|
mpz_set (min, off);
|
mpz_set (max, off);
|
mpz_set (max, off);
|
return;
|
return;
|
}
|
}
|
|
|
/* If the computation may wrap, we know nothing about the value, except for
|
/* If the computation may wrap, we know nothing about the value, except for
|
the range of the type. */
|
the range of the type. */
|
get_type_static_bounds (type, min, max);
|
get_type_static_bounds (type, min, max);
|
if (!nowrap_type_p (type))
|
if (!nowrap_type_p (type))
|
return;
|
return;
|
|
|
/* Since the addition of OFF does not wrap, if OFF is positive, then we may
|
/* Since the addition of OFF does not wrap, if OFF is positive, then we may
|
add it to MIN, otherwise to MAX. */
|
add it to MIN, otherwise to MAX. */
|
if (mpz_sgn (off) < 0)
|
if (mpz_sgn (off) < 0)
|
mpz_add (max, max, off);
|
mpz_add (max, max, off);
|
else
|
else
|
mpz_add (min, min, off);
|
mpz_add (min, min, off);
|
}
|
}
|
|
|
/* Stores the bounds on the difference of the values of the expressions
|
/* Stores the bounds on the difference of the values of the expressions
|
(var + X) and (var + Y), computed in TYPE, to BNDS. */
|
(var + X) and (var + Y), computed in TYPE, to BNDS. */
|
|
|
static void
|
static void
|
bound_difference_of_offsetted_base (tree type, mpz_t x, mpz_t y,
|
bound_difference_of_offsetted_base (tree type, mpz_t x, mpz_t y,
|
bounds *bnds)
|
bounds *bnds)
|
{
|
{
|
int rel = mpz_cmp (x, y);
|
int rel = mpz_cmp (x, y);
|
bool may_wrap = !nowrap_type_p (type);
|
bool may_wrap = !nowrap_type_p (type);
|
mpz_t m;
|
mpz_t m;
|
|
|
/* If X == Y, then the expressions are always equal.
|
/* If X == Y, then the expressions are always equal.
|
If X > Y, there are the following possibilities:
|
If X > Y, there are the following possibilities:
|
a) neither of var + X and var + Y overflow or underflow, or both of
|
a) neither of var + X and var + Y overflow or underflow, or both of
|
them do. Then their difference is X - Y.
|
them do. Then their difference is X - Y.
|
b) var + X overflows, and var + Y does not. Then the values of the
|
b) var + X overflows, and var + Y does not. Then the values of the
|
expressions are var + X - M and var + Y, where M is the range of
|
expressions are var + X - M and var + Y, where M is the range of
|
the type, and their difference is X - Y - M.
|
the type, and their difference is X - Y - M.
|
c) var + Y underflows and var + X does not. Their difference again
|
c) var + Y underflows and var + X does not. Their difference again
|
is M - X + Y.
|
is M - X + Y.
|
Therefore, if the arithmetics in type does not overflow, then the
|
Therefore, if the arithmetics in type does not overflow, then the
|
bounds are (X - Y, X - Y), otherwise they are (X - Y - M, X - Y)
|
bounds are (X - Y, X - Y), otherwise they are (X - Y - M, X - Y)
|
Similarly, if X < Y, the bounds are either (X - Y, X - Y) or
|
Similarly, if X < Y, the bounds are either (X - Y, X - Y) or
|
(X - Y, X - Y + M). */
|
(X - Y, X - Y + M). */
|
|
|
if (rel == 0)
|
if (rel == 0)
|
{
|
{
|
mpz_set_ui (bnds->below, 0);
|
mpz_set_ui (bnds->below, 0);
|
mpz_set_ui (bnds->up, 0);
|
mpz_set_ui (bnds->up, 0);
|
return;
|
return;
|
}
|
}
|
|
|
mpz_init (m);
|
mpz_init (m);
|
mpz_set_double_int (m, double_int_mask (TYPE_PRECISION (type)), true);
|
mpz_set_double_int (m, double_int_mask (TYPE_PRECISION (type)), true);
|
mpz_add_ui (m, m, 1);
|
mpz_add_ui (m, m, 1);
|
mpz_sub (bnds->up, x, y);
|
mpz_sub (bnds->up, x, y);
|
mpz_set (bnds->below, bnds->up);
|
mpz_set (bnds->below, bnds->up);
|
|
|
if (may_wrap)
|
if (may_wrap)
|
{
|
{
|
if (rel > 0)
|
if (rel > 0)
|
mpz_sub (bnds->below, bnds->below, m);
|
mpz_sub (bnds->below, bnds->below, m);
|
else
|
else
|
mpz_add (bnds->up, bnds->up, m);
|
mpz_add (bnds->up, bnds->up, m);
|
}
|
}
|
|
|
mpz_clear (m);
|
mpz_clear (m);
|
}
|
}
|
|
|
/* From condition C0 CMP C1 derives information regarding the
|
/* From condition C0 CMP C1 derives information regarding the
|
difference of values of VARX + OFFX and VARY + OFFY, computed in TYPE,
|
difference of values of VARX + OFFX and VARY + OFFY, computed in TYPE,
|
and stores it to BNDS. */
|
and stores it to BNDS. */
|
|
|
static void
|
static void
|
refine_bounds_using_guard (tree type, tree varx, mpz_t offx,
|
refine_bounds_using_guard (tree type, tree varx, mpz_t offx,
|
tree vary, mpz_t offy,
|
tree vary, mpz_t offy,
|
tree c0, enum tree_code cmp, tree c1,
|
tree c0, enum tree_code cmp, tree c1,
|
bounds *bnds)
|
bounds *bnds)
|
{
|
{
|
tree varc0, varc1, tmp, ctype;
|
tree varc0, varc1, tmp, ctype;
|
mpz_t offc0, offc1, loffx, loffy, bnd;
|
mpz_t offc0, offc1, loffx, loffy, bnd;
|
bool lbound = false;
|
bool lbound = false;
|
bool no_wrap = nowrap_type_p (type);
|
bool no_wrap = nowrap_type_p (type);
|
bool x_ok, y_ok;
|
bool x_ok, y_ok;
|
|
|
switch (cmp)
|
switch (cmp)
|
{
|
{
|
case LT_EXPR:
|
case LT_EXPR:
|
case LE_EXPR:
|
case LE_EXPR:
|
case GT_EXPR:
|
case GT_EXPR:
|
case GE_EXPR:
|
case GE_EXPR:
|
STRIP_SIGN_NOPS (c0);
|
STRIP_SIGN_NOPS (c0);
|
STRIP_SIGN_NOPS (c1);
|
STRIP_SIGN_NOPS (c1);
|
ctype = TREE_TYPE (c0);
|
ctype = TREE_TYPE (c0);
|
if (!useless_type_conversion_p (ctype, type))
|
if (!useless_type_conversion_p (ctype, type))
|
return;
|
return;
|
|
|
break;
|
break;
|
|
|
case EQ_EXPR:
|
case EQ_EXPR:
|
/* We could derive quite precise information from EQ_EXPR, however, such
|
/* We could derive quite precise information from EQ_EXPR, however, such
|
a guard is unlikely to appear, so we do not bother with handling
|
a guard is unlikely to appear, so we do not bother with handling
|
it. */
|
it. */
|
return;
|
return;
|
|
|
case NE_EXPR:
|
case NE_EXPR:
|
/* NE_EXPR comparisons do not contain much of useful information, except for
|
/* NE_EXPR comparisons do not contain much of useful information, except for
|
special case of comparing with the bounds of the type. */
|
special case of comparing with the bounds of the type. */
|
if (TREE_CODE (c1) != INTEGER_CST
|
if (TREE_CODE (c1) != INTEGER_CST
|
|| !INTEGRAL_TYPE_P (type))
|
|| !INTEGRAL_TYPE_P (type))
|
return;
|
return;
|
|
|
/* Ensure that the condition speaks about an expression in the same type
|
/* Ensure that the condition speaks about an expression in the same type
|
as X and Y. */
|
as X and Y. */
|
ctype = TREE_TYPE (c0);
|
ctype = TREE_TYPE (c0);
|
if (TYPE_PRECISION (ctype) != TYPE_PRECISION (type))
|
if (TYPE_PRECISION (ctype) != TYPE_PRECISION (type))
|
return;
|
return;
|
c0 = fold_convert (type, c0);
|
c0 = fold_convert (type, c0);
|
c1 = fold_convert (type, c1);
|
c1 = fold_convert (type, c1);
|
|
|
if (TYPE_MIN_VALUE (type)
|
if (TYPE_MIN_VALUE (type)
|
&& operand_equal_p (c1, TYPE_MIN_VALUE (type), 0))
|
&& operand_equal_p (c1, TYPE_MIN_VALUE (type), 0))
|
{
|
{
|
cmp = GT_EXPR;
|
cmp = GT_EXPR;
|
break;
|
break;
|
}
|
}
|
if (TYPE_MAX_VALUE (type)
|
if (TYPE_MAX_VALUE (type)
|
&& operand_equal_p (c1, TYPE_MAX_VALUE (type), 0))
|
&& operand_equal_p (c1, TYPE_MAX_VALUE (type), 0))
|
{
|
{
|
cmp = LT_EXPR;
|
cmp = LT_EXPR;
|
break;
|
break;
|
}
|
}
|
|
|
return;
|
return;
|
default:
|
default:
|
return;
|
return;
|
}
|
}
|
|
|
mpz_init (offc0);
|
mpz_init (offc0);
|
mpz_init (offc1);
|
mpz_init (offc1);
|
split_to_var_and_offset (expand_simple_operations (c0), &varc0, offc0);
|
split_to_var_and_offset (expand_simple_operations (c0), &varc0, offc0);
|
split_to_var_and_offset (expand_simple_operations (c1), &varc1, offc1);
|
split_to_var_and_offset (expand_simple_operations (c1), &varc1, offc1);
|
|
|
/* We are only interested in comparisons of expressions based on VARX and
|
/* We are only interested in comparisons of expressions based on VARX and
|
VARY. TODO -- we might also be able to derive some bounds from
|
VARY. TODO -- we might also be able to derive some bounds from
|
expressions containing just one of the variables. */
|
expressions containing just one of the variables. */
|
|
|
if (operand_equal_p (varx, varc1, 0))
|
if (operand_equal_p (varx, varc1, 0))
|
{
|
{
|
tmp = varc0; varc0 = varc1; varc1 = tmp;
|
tmp = varc0; varc0 = varc1; varc1 = tmp;
|
mpz_swap (offc0, offc1);
|
mpz_swap (offc0, offc1);
|
cmp = swap_tree_comparison (cmp);
|
cmp = swap_tree_comparison (cmp);
|
}
|
}
|
|
|
if (!operand_equal_p (varx, varc0, 0)
|
if (!operand_equal_p (varx, varc0, 0)
|
|| !operand_equal_p (vary, varc1, 0))
|
|| !operand_equal_p (vary, varc1, 0))
|
goto end;
|
goto end;
|
|
|
mpz_init_set (loffx, offx);
|
mpz_init_set (loffx, offx);
|
mpz_init_set (loffy, offy);
|
mpz_init_set (loffy, offy);
|
|
|
if (cmp == GT_EXPR || cmp == GE_EXPR)
|
if (cmp == GT_EXPR || cmp == GE_EXPR)
|
{
|
{
|
tmp = varx; varx = vary; vary = tmp;
|
tmp = varx; varx = vary; vary = tmp;
|
mpz_swap (offc0, offc1);
|
mpz_swap (offc0, offc1);
|
mpz_swap (loffx, loffy);
|
mpz_swap (loffx, loffy);
|
cmp = swap_tree_comparison (cmp);
|
cmp = swap_tree_comparison (cmp);
|
lbound = true;
|
lbound = true;
|
}
|
}
|
|
|
/* If there is no overflow, the condition implies that
|
/* If there is no overflow, the condition implies that
|
|
|
(VARX + OFFX) cmp (VARY + OFFY) + (OFFX - OFFY + OFFC1 - OFFC0).
|
(VARX + OFFX) cmp (VARY + OFFY) + (OFFX - OFFY + OFFC1 - OFFC0).
|
|
|
The overflows and underflows may complicate things a bit; each
|
The overflows and underflows may complicate things a bit; each
|
overflow decreases the appropriate offset by M, and underflow
|
overflow decreases the appropriate offset by M, and underflow
|
increases it by M. The above inequality would not necessarily be
|
increases it by M. The above inequality would not necessarily be
|
true if
|
true if
|
|
|
-- VARX + OFFX underflows and VARX + OFFC0 does not, or
|
-- VARX + OFFX underflows and VARX + OFFC0 does not, or
|
VARX + OFFC0 overflows, but VARX + OFFX does not.
|
VARX + OFFC0 overflows, but VARX + OFFX does not.
|
This may only happen if OFFX < OFFC0.
|
This may only happen if OFFX < OFFC0.
|
-- VARY + OFFY overflows and VARY + OFFC1 does not, or
|
-- VARY + OFFY overflows and VARY + OFFC1 does not, or
|
VARY + OFFC1 underflows and VARY + OFFY does not.
|
VARY + OFFC1 underflows and VARY + OFFY does not.
|
This may only happen if OFFY > OFFC1. */
|
This may only happen if OFFY > OFFC1. */
|
|
|
if (no_wrap)
|
if (no_wrap)
|
{
|
{
|
x_ok = true;
|
x_ok = true;
|
y_ok = true;
|
y_ok = true;
|
}
|
}
|
else
|
else
|
{
|
{
|
x_ok = (integer_zerop (varx)
|
x_ok = (integer_zerop (varx)
|
|| mpz_cmp (loffx, offc0) >= 0);
|
|| mpz_cmp (loffx, offc0) >= 0);
|
y_ok = (integer_zerop (vary)
|
y_ok = (integer_zerop (vary)
|
|| mpz_cmp (loffy, offc1) <= 0);
|
|| mpz_cmp (loffy, offc1) <= 0);
|
}
|
}
|
|
|
if (x_ok && y_ok)
|
if (x_ok && y_ok)
|
{
|
{
|
mpz_init (bnd);
|
mpz_init (bnd);
|
mpz_sub (bnd, loffx, loffy);
|
mpz_sub (bnd, loffx, loffy);
|
mpz_add (bnd, bnd, offc1);
|
mpz_add (bnd, bnd, offc1);
|
mpz_sub (bnd, bnd, offc0);
|
mpz_sub (bnd, bnd, offc0);
|
|
|
if (cmp == LT_EXPR)
|
if (cmp == LT_EXPR)
|
mpz_sub_ui (bnd, bnd, 1);
|
mpz_sub_ui (bnd, bnd, 1);
|
|
|
if (lbound)
|
if (lbound)
|
{
|
{
|
mpz_neg (bnd, bnd);
|
mpz_neg (bnd, bnd);
|
if (mpz_cmp (bnds->below, bnd) < 0)
|
if (mpz_cmp (bnds->below, bnd) < 0)
|
mpz_set (bnds->below, bnd);
|
mpz_set (bnds->below, bnd);
|
}
|
}
|
else
|
else
|
{
|
{
|
if (mpz_cmp (bnd, bnds->up) < 0)
|
if (mpz_cmp (bnd, bnds->up) < 0)
|
mpz_set (bnds->up, bnd);
|
mpz_set (bnds->up, bnd);
|
}
|
}
|
mpz_clear (bnd);
|
mpz_clear (bnd);
|
}
|
}
|
|
|
mpz_clear (loffx);
|
mpz_clear (loffx);
|
mpz_clear (loffy);
|
mpz_clear (loffy);
|
end:
|
end:
|
mpz_clear (offc0);
|
mpz_clear (offc0);
|
mpz_clear (offc1);
|
mpz_clear (offc1);
|
}
|
}
|
|
|
/* Stores the bounds on the value of the expression X - Y in LOOP to BNDS.
|
/* Stores the bounds on the value of the expression X - Y in LOOP to BNDS.
|
The subtraction is considered to be performed in arbitrary precision,
|
The subtraction is considered to be performed in arbitrary precision,
|
without overflows.
|
without overflows.
|
|
|
We do not attempt to be too clever regarding the value ranges of X and
|
We do not attempt to be too clever regarding the value ranges of X and
|
Y; most of the time, they are just integers or ssa names offsetted by
|
Y; most of the time, they are just integers or ssa names offsetted by
|
integer. However, we try to use the information contained in the
|
integer. However, we try to use the information contained in the
|
comparisons before the loop (usually created by loop header copying). */
|
comparisons before the loop (usually created by loop header copying). */
|
|
|
static void
|
static void
|
bound_difference (struct loop *loop, tree x, tree y, bounds *bnds)
|
bound_difference (struct loop *loop, tree x, tree y, bounds *bnds)
|
{
|
{
|
tree type = TREE_TYPE (x);
|
tree type = TREE_TYPE (x);
|
tree varx, vary;
|
tree varx, vary;
|
mpz_t offx, offy;
|
mpz_t offx, offy;
|
mpz_t minx, maxx, miny, maxy;
|
mpz_t minx, maxx, miny, maxy;
|
int cnt = 0;
|
int cnt = 0;
|
edge e;
|
edge e;
|
basic_block bb;
|
basic_block bb;
|
tree c0, c1;
|
tree c0, c1;
|
gimple cond;
|
gimple cond;
|
enum tree_code cmp;
|
enum tree_code cmp;
|
|
|
/* Get rid of unnecessary casts, but preserve the value of
|
/* Get rid of unnecessary casts, but preserve the value of
|
the expressions. */
|
the expressions. */
|
STRIP_SIGN_NOPS (x);
|
STRIP_SIGN_NOPS (x);
|
STRIP_SIGN_NOPS (y);
|
STRIP_SIGN_NOPS (y);
|
|
|
mpz_init (bnds->below);
|
mpz_init (bnds->below);
|
mpz_init (bnds->up);
|
mpz_init (bnds->up);
|
mpz_init (offx);
|
mpz_init (offx);
|
mpz_init (offy);
|
mpz_init (offy);
|
split_to_var_and_offset (x, &varx, offx);
|
split_to_var_and_offset (x, &varx, offx);
|
split_to_var_and_offset (y, &vary, offy);
|
split_to_var_and_offset (y, &vary, offy);
|
|
|
if (!integer_zerop (varx)
|
if (!integer_zerop (varx)
|
&& operand_equal_p (varx, vary, 0))
|
&& operand_equal_p (varx, vary, 0))
|
{
|
{
|
/* Special case VARX == VARY -- we just need to compare the
|
/* Special case VARX == VARY -- we just need to compare the
|
offsets. The matters are a bit more complicated in the
|
offsets. The matters are a bit more complicated in the
|
case addition of offsets may wrap. */
|
case addition of offsets may wrap. */
|
bound_difference_of_offsetted_base (type, offx, offy, bnds);
|
bound_difference_of_offsetted_base (type, offx, offy, bnds);
|
}
|
}
|
else
|
else
|
{
|
{
|
/* Otherwise, use the value ranges to determine the initial
|
/* Otherwise, use the value ranges to determine the initial
|
estimates on below and up. */
|
estimates on below and up. */
|
mpz_init (minx);
|
mpz_init (minx);
|
mpz_init (maxx);
|
mpz_init (maxx);
|
mpz_init (miny);
|
mpz_init (miny);
|
mpz_init (maxy);
|
mpz_init (maxy);
|
determine_value_range (type, varx, offx, minx, maxx);
|
determine_value_range (type, varx, offx, minx, maxx);
|
determine_value_range (type, vary, offy, miny, maxy);
|
determine_value_range (type, vary, offy, miny, maxy);
|
|
|
mpz_sub (bnds->below, minx, maxy);
|
mpz_sub (bnds->below, minx, maxy);
|
mpz_sub (bnds->up, maxx, miny);
|
mpz_sub (bnds->up, maxx, miny);
|
mpz_clear (minx);
|
mpz_clear (minx);
|
mpz_clear (maxx);
|
mpz_clear (maxx);
|
mpz_clear (miny);
|
mpz_clear (miny);
|
mpz_clear (maxy);
|
mpz_clear (maxy);
|
}
|
}
|
|
|
/* If both X and Y are constants, we cannot get any more precise. */
|
/* If both X and Y are constants, we cannot get any more precise. */
|
if (integer_zerop (varx) && integer_zerop (vary))
|
if (integer_zerop (varx) && integer_zerop (vary))
|
goto end;
|
goto end;
|
|
|
/* Now walk the dominators of the loop header and use the entry
|
/* Now walk the dominators of the loop header and use the entry
|
guards to refine the estimates. */
|
guards to refine the estimates. */
|
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 = last_stmt (e->src);
|
cond = last_stmt (e->src);
|
c0 = gimple_cond_lhs (cond);
|
c0 = gimple_cond_lhs (cond);
|
cmp = gimple_cond_code (cond);
|
cmp = gimple_cond_code (cond);
|
c1 = gimple_cond_rhs (cond);
|
c1 = gimple_cond_rhs (cond);
|
|
|
if (e->flags & EDGE_FALSE_VALUE)
|
if (e->flags & EDGE_FALSE_VALUE)
|
cmp = invert_tree_comparison (cmp, false);
|
cmp = invert_tree_comparison (cmp, false);
|
|
|
refine_bounds_using_guard (type, varx, offx, vary, offy,
|
refine_bounds_using_guard (type, varx, offx, vary, offy,
|
c0, cmp, c1, bnds);
|
c0, cmp, c1, bnds);
|
++cnt;
|
++cnt;
|
}
|
}
|
|
|
end:
|
end:
|
mpz_clear (offx);
|
mpz_clear (offx);
|
mpz_clear (offy);
|
mpz_clear (offy);
|
}
|
}
|
|
|
/* Update the bounds in BNDS that restrict the value of X to the bounds
|
/* Update the bounds in BNDS that restrict the value of X to the bounds
|
that restrict the value of X + DELTA. X can be obtained as a
|
that restrict the value of X + DELTA. X can be obtained as a
|
difference of two values in TYPE. */
|
difference of two values in TYPE. */
|
|
|
static void
|
static void
|
bounds_add (bounds *bnds, double_int delta, tree type)
|
bounds_add (bounds *bnds, double_int delta, tree type)
|
{
|
{
|
mpz_t mdelta, max;
|
mpz_t mdelta, max;
|
|
|
mpz_init (mdelta);
|
mpz_init (mdelta);
|
mpz_set_double_int (mdelta, delta, false);
|
mpz_set_double_int (mdelta, delta, false);
|
|
|
mpz_init (max);
|
mpz_init (max);
|
mpz_set_double_int (max, double_int_mask (TYPE_PRECISION (type)), true);
|
mpz_set_double_int (max, double_int_mask (TYPE_PRECISION (type)), true);
|
|
|
mpz_add (bnds->up, bnds->up, mdelta);
|
mpz_add (bnds->up, bnds->up, mdelta);
|
mpz_add (bnds->below, bnds->below, mdelta);
|
mpz_add (bnds->below, bnds->below, mdelta);
|
|
|
if (mpz_cmp (bnds->up, max) > 0)
|
if (mpz_cmp (bnds->up, max) > 0)
|
mpz_set (bnds->up, max);
|
mpz_set (bnds->up, max);
|
|
|
mpz_neg (max, max);
|
mpz_neg (max, max);
|
if (mpz_cmp (bnds->below, max) < 0)
|
if (mpz_cmp (bnds->below, max) < 0)
|
mpz_set (bnds->below, max);
|
mpz_set (bnds->below, max);
|
|
|
mpz_clear (mdelta);
|
mpz_clear (mdelta);
|
mpz_clear (max);
|
mpz_clear (max);
|
}
|
}
|
|
|
/* Update the bounds in BNDS that restrict the value of X to the bounds
|
/* Update the bounds in BNDS that restrict the value of X to the bounds
|
that restrict the value of -X. */
|
that restrict the value of -X. */
|
|
|
static void
|
static void
|
bounds_negate (bounds *bnds)
|
bounds_negate (bounds *bnds)
|
{
|
{
|
mpz_t tmp;
|
mpz_t tmp;
|
|
|
mpz_init_set (tmp, bnds->up);
|
mpz_init_set (tmp, bnds->up);
|
mpz_neg (bnds->up, bnds->below);
|
mpz_neg (bnds->up, bnds->below);
|
mpz_neg (bnds->below, tmp);
|
mpz_neg (bnds->below, tmp);
|
mpz_clear (tmp);
|
mpz_clear (tmp);
|
}
|
}
|
|
|
/* 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;
|
}
|
}
|
|
|
/* Derives the upper bound BND on the number of executions of loop with exit
|
/* Derives the upper bound BND on the number of executions of loop with exit
|
condition S * i <> C, assuming that this exit is taken. If
|
condition S * i <> C, assuming that this exit is taken. If
|
NO_OVERFLOW is true, then the control variable of the loop does not
|
NO_OVERFLOW is true, then the control variable of the loop does not
|
overflow. If NO_OVERFLOW is true or BNDS.below >= 0, then BNDS.up
|
overflow. If NO_OVERFLOW is true or BNDS.below >= 0, then BNDS.up
|
contains the upper bound on the value of C. */
|
contains the upper bound on the value of C. */
|
|
|
static void
|
static void
|
number_of_iterations_ne_max (mpz_t bnd, bool no_overflow, tree c, tree s,
|
number_of_iterations_ne_max (mpz_t bnd, bool no_overflow, tree c, tree s,
|
bounds *bnds)
|
bounds *bnds)
|
{
|
{
|
double_int max;
|
double_int max;
|
mpz_t d;
|
mpz_t d;
|
|
|
/* If the control variable does not overflow, the number of iterations is
|
/* If the control variable does not overflow, the number of iterations is
|
at most c / s. Otherwise it is at most the period of the control
|
at most c / s. Otherwise it is at most the period of the control
|
variable. */
|
variable. */
|
if (!no_overflow && !multiple_of_p (TREE_TYPE (c), c, s))
|
if (!no_overflow && !multiple_of_p (TREE_TYPE (c), c, s))
|
{
|
{
|
max = double_int_mask (TYPE_PRECISION (TREE_TYPE (c))
|
max = double_int_mask (TYPE_PRECISION (TREE_TYPE (c))
|
- tree_low_cst (num_ending_zeros (s), 1));
|
- tree_low_cst (num_ending_zeros (s), 1));
|
mpz_set_double_int (bnd, max, true);
|
mpz_set_double_int (bnd, max, true);
|
return;
|
return;
|
}
|
}
|
|
|
/* Determine the upper bound on C. */
|
/* Determine the upper bound on C. */
|
if (no_overflow || mpz_sgn (bnds->below) >= 0)
|
if (no_overflow || mpz_sgn (bnds->below) >= 0)
|
mpz_set (bnd, bnds->up);
|
mpz_set (bnd, bnds->up);
|
else if (TREE_CODE (c) == INTEGER_CST)
|
else if (TREE_CODE (c) == INTEGER_CST)
|
mpz_set_double_int (bnd, tree_to_double_int (c), true);
|
mpz_set_double_int (bnd, tree_to_double_int (c), true);
|
else
|
else
|
mpz_set_double_int (bnd, double_int_mask (TYPE_PRECISION (TREE_TYPE (c))),
|
mpz_set_double_int (bnd, double_int_mask (TYPE_PRECISION (TREE_TYPE (c))),
|
true);
|
true);
|
|
|
mpz_init (d);
|
mpz_init (d);
|
mpz_set_double_int (d, tree_to_double_int (s), true);
|
mpz_set_double_int (d, tree_to_double_int (s), true);
|
mpz_fdiv_q (bnd, bnd, d);
|
mpz_fdiv_q (bnd, bnd, d);
|
mpz_clear (d);
|
mpz_clear (d);
|
}
|
}
|
|
|
/* 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. EXIT_MUST_BE_TAKEN is true if
|
iterations is stored to NITER. EXIT_MUST_BE_TAKEN 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). BNDS contains the
|
NITER->assumptions to make sure this is the case). BNDS contains the
|
bounds on the difference FINAL - IV->base. */
|
bounds on the difference FINAL - IV->base. */
|
|
|
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 exit_must_be_taken,
|
struct tree_niter_desc *niter, bool exit_must_be_taken,
|
bounds *bnds)
|
bounds *bnds)
|
{
|
{
|
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;
|
mpz_t max;
|
mpz_t max;
|
|
|
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. If IV does
|
positive. Also cast everything to the unsigned type. If IV does
|
not overflow, BNDS bounds the value of C. Also, this is the
|
not overflow, BNDS bounds the value of C. Also, this is the
|
case if the computation |FINAL - IV->base| does not overflow, i.e.,
|
case if the computation |FINAL - IV->base| does not overflow, i.e.,
|
if BNDS->below in the result is nonnegative. */
|
if BNDS->below in the result is nonnegative. */
|
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));
|
bounds_negate (bnds);
|
bounds_negate (bnds);
|
}
|
}
|
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));
|
}
|
}
|
|
|
mpz_init (max);
|
mpz_init (max);
|
number_of_iterations_ne_max (max, iv->no_overflow, c, s, bnds);
|
number_of_iterations_ne_max (max, iv->no_overflow, c, s, bnds);
|
niter->max = mpz_get_double_int (niter_type, max, false);
|
niter->max = mpz_get_double_int (niter_type, max, false);
|
mpz_clear (max);
|
mpz_clear (max);
|
|
|
/* 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 (!exit_must_be_taken)
|
if (!exit_must_be_taken)
|
{
|
{
|
/* If we cannot assume that the exit is taken eventually, record the
|
/* If we cannot assume that the exit is taken eventually, 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 (!integer_nonzerop (assumption))
|
if (!integer_nonzerop (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. BNDS bounds the value of IV1->base - IV0->base,
|
we return false. BNDS bounds the value of IV1->base - IV0->base,
|
and will be updated by the same amount as DELTA. EXIT_MUST_BE_TAKEN is
|
and will be updated by the same amount as DELTA. EXIT_MUST_BE_TAKEN is
|
true if we know that the exit must be taken eventually. */
|
true if we know that the exit must be taken eventually. */
|
|
|
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,
|
bool exit_must_be_taken, bounds *bnds)
|
bool exit_must_be_taken, bounds *bnds)
|
{
|
{
|
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;
|
mpz_t mmod;
|
mpz_t mmod;
|
tree assumption = boolean_true_node, bound, noloop;
|
tree assumption = boolean_true_node, bound, noloop;
|
bool ret = false, fv_comp_no_overflow;
|
bool ret = false, fv_comp_no_overflow;
|
tree type1 = type;
|
tree type1 = type;
|
if (POINTER_TYPE_P (type))
|
if (POINTER_TYPE_P (type))
|
type1 = sizetype;
|
type1 = sizetype;
|
|
|
if (TREE_CODE (mod) != INTEGER_CST)
|
if (TREE_CODE (mod) != INTEGER_CST)
|
return false;
|
return false;
|
if (integer_nonzerop (mod))
|
if (integer_nonzerop (mod))
|
mod = fold_build2 (MINUS_EXPR, niter_type, step, mod);
|
mod = fold_build2 (MINUS_EXPR, niter_type, step, mod);
|
tmod = fold_convert (type1, mod);
|
tmod = fold_convert (type1, mod);
|
|
|
mpz_init (mmod);
|
mpz_init (mmod);
|
mpz_set_double_int (mmod, tree_to_double_int (mod), true);
|
mpz_set_double_int (mmod, tree_to_double_int (mod), true);
|
mpz_neg (mmod, mmod);
|
mpz_neg (mmod, mmod);
|
|
|
/* If the induction variable does not overflow and the exit is taken,
|
/* If the induction variable does not overflow and the exit is taken,
|
then the computation of the final value does not overflow. This is
|
then the computation of the final value does not overflow. This is
|
also obviously the case if the new final value is equal to the
|
also obviously the case if the new final value is equal to the
|
current one. Finally, we postulate this for pointer type variables,
|
current one. Finally, we postulate this for pointer type variables,
|
as the code cannot rely on the object to that the pointer points being
|
as the code cannot rely on the object to that the pointer points being
|
placed at the end of the address space (and more pragmatically,
|
placed at the end of the address space (and more pragmatically,
|
TYPE_{MIN,MAX}_VALUE is not defined for pointers). */
|
TYPE_{MIN,MAX}_VALUE is not defined for pointers). */
|
if (integer_zerop (mod) || POINTER_TYPE_P (type))
|
if (integer_zerop (mod) || POINTER_TYPE_P (type))
|
fv_comp_no_overflow = true;
|
fv_comp_no_overflow = true;
|
else if (!exit_must_be_taken)
|
else if (!exit_must_be_taken)
|
fv_comp_no_overflow = false;
|
fv_comp_no_overflow = false;
|
else
|
else
|
fv_comp_no_overflow =
|
fv_comp_no_overflow =
|
(iv0->no_overflow && integer_nonzerop (iv0->step))
|
(iv0->no_overflow && integer_nonzerop (iv0->step))
|
|| (iv1->no_overflow && integer_nonzerop (iv1->step));
|
|| (iv1->no_overflow && integer_nonzerop (iv1->step));
|
|
|
if (integer_nonzerop (iv0->step))
|
if (integer_nonzerop (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 (!fv_comp_no_overflow)
|
if (!fv_comp_no_overflow)
|
{
|
{
|
bound = fold_build2 (MINUS_EXPR, type1,
|
bound = fold_build2 (MINUS_EXPR, type1,
|
TYPE_MAX_VALUE (type1), tmod);
|
TYPE_MAX_VALUE (type1), tmod);
|
assumption = fold_build2 (LE_EXPR, boolean_type_node,
|
assumption = fold_build2 (LE_EXPR, boolean_type_node,
|
iv1->base, bound);
|
iv1->base, bound);
|
if (integer_zerop (assumption))
|
if (integer_zerop (assumption))
|
goto end;
|
goto end;
|
}
|
}
|
if (mpz_cmp (mmod, bnds->below) < 0)
|
if (mpz_cmp (mmod, bnds->below) < 0)
|
noloop = boolean_false_node;
|
noloop = boolean_false_node;
|
else if (POINTER_TYPE_P (type))
|
else if (POINTER_TYPE_P (type))
|
noloop = fold_build2 (GT_EXPR, boolean_type_node,
|
noloop = fold_build2 (GT_EXPR, boolean_type_node,
|
iv0->base,
|
iv0->base,
|
fold_build2 (POINTER_PLUS_EXPR, type,
|
fold_build2 (POINTER_PLUS_EXPR, type,
|
iv1->base, tmod));
|
iv1->base, tmod));
|
else
|
else
|
noloop = fold_build2 (GT_EXPR, boolean_type_node,
|
noloop = fold_build2 (GT_EXPR, boolean_type_node,
|
iv0->base,
|
iv0->base,
|
fold_build2 (PLUS_EXPR, type1,
|
fold_build2 (PLUS_EXPR, type1,
|
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 (!fv_comp_no_overflow)
|
if (!fv_comp_no_overflow)
|
{
|
{
|
bound = fold_build2 (PLUS_EXPR, type1,
|
bound = fold_build2 (PLUS_EXPR, type1,
|
TYPE_MIN_VALUE (type1), tmod);
|
TYPE_MIN_VALUE (type1), tmod);
|
assumption = fold_build2 (GE_EXPR, boolean_type_node,
|
assumption = fold_build2 (GE_EXPR, boolean_type_node,
|
iv0->base, bound);
|
iv0->base, bound);
|
if (integer_zerop (assumption))
|
if (integer_zerop (assumption))
|
goto end;
|
goto end;
|
}
|
}
|
if (mpz_cmp (mmod, bnds->below) < 0)
|
if (mpz_cmp (mmod, bnds->below) < 0)
|
noloop = boolean_false_node;
|
noloop = boolean_false_node;
|
else if (POINTER_TYPE_P (type))
|
else if (POINTER_TYPE_P (type))
|
noloop = fold_build2 (GT_EXPR, boolean_type_node,
|
noloop = fold_build2 (GT_EXPR, boolean_type_node,
|
fold_build2 (POINTER_PLUS_EXPR, type,
|
fold_build2 (POINTER_PLUS_EXPR, type,
|
iv0->base,
|
iv0->base,
|
fold_build1 (NEGATE_EXPR,
|
fold_build1 (NEGATE_EXPR,
|
type1, tmod)),
|
type1, tmod)),
|
iv1->base);
|
iv1->base);
|
else
|
else
|
noloop = fold_build2 (GT_EXPR, boolean_type_node,
|
noloop = fold_build2 (GT_EXPR, boolean_type_node,
|
fold_build2 (MINUS_EXPR, type1,
|
fold_build2 (MINUS_EXPR, type1,
|
iv0->base, tmod),
|
iv0->base, tmod),
|
iv1->base);
|
iv1->base);
|
}
|
}
|
|
|
if (!integer_nonzerop (assumption))
|
if (!integer_nonzerop (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 (!integer_zerop (noloop))
|
if (!integer_zerop (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);
|
bounds_add (bnds, tree_to_double_int (mod), type);
|
bounds_add (bnds, tree_to_double_int (mod), type);
|
*delta = fold_build2 (PLUS_EXPR, niter_type, *delta, mod);
|
*delta = fold_build2 (PLUS_EXPR, niter_type, *delta, mod);
|
|
|
ret = true;
|
ret = true;
|
end:
|
end:
|
mpz_clear (mmod);
|
mpz_clear (mmod);
|
return ret;
|
return ret;
|
}
|
}
|
|
|
/* 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 (integer_nonzerop (iv0->step))
|
if (integer_nonzerop (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 (integer_zerop (assumption))
|
if (integer_zerop (assumption))
|
return false;
|
return false;
|
if (!integer_nonzerop (assumption))
|
if (!integer_nonzerop (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. BNDS
|
is IV0 < IV1 rolls. TYPE is the type of the control iv. BNDS
|
bounds the value of IV1->base - IV0->base. */
|
bounds the value of IV1->base - IV0->base. */
|
|
|
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, bounds *bnds)
|
struct tree_niter_desc *niter, bounds *bnds)
|
{
|
{
|
tree assumption = boolean_true_node, bound, diff;
|
tree assumption = boolean_true_node, bound, diff;
|
tree mbz, mbzl, mbzr, type1;
|
tree mbz, mbzl, mbzr, type1;
|
bool rolls_p, no_overflow_p;
|
bool rolls_p, no_overflow_p;
|
double_int dstep;
|
double_int dstep;
|
mpz_t mstep, max;
|
mpz_t mstep, max;
|
|
|
/* We are going to compute the number of iterations as
|
/* We are going to compute the number of iterations as
|
(iv1->base - iv0->base + step - 1) / step, computed in the unsigned
|
(iv1->base - iv0->base + step - 1) / step, computed in the unsigned
|
variant of TYPE. This formula only works if
|
variant of TYPE. This formula only works if
|
|
|
-step + 1 <= (iv1->base - iv0->base) <= MAX - step + 1
|
-step + 1 <= (iv1->base - iv0->base) <= MAX - step + 1
|
|
|
(where MAX is the maximum value of the unsigned variant of TYPE, and
|
(where MAX is the maximum value of the unsigned variant of TYPE, and
|
the computations in this formula are performed in full precision
|
the computations in this formula are performed in full precision
|
(without overflows).
|
(without overflows).
|
|
|
Usually, for loops with exit condition iv0->base + step * i < iv1->base,
|
Usually, for loops with exit condition iv0->base + step * i < iv1->base,
|
we have a condition of form iv0->base - step < iv1->base before the loop,
|
we have a condition of form iv0->base - step < iv1->base before the loop,
|
and for loops iv0->base < iv1->base - step * i the condition
|
and for loops iv0->base < iv1->base - step * i the condition
|
iv0->base < iv1->base + step, due to loop header copying, which enable us
|
iv0->base < iv1->base + step, due to loop header copying, which enable us
|
to prove the lower bound.
|
to prove the lower bound.
|
|
|
The upper bound is more complicated. Unless the expressions for initial
|
The upper bound is more complicated. Unless the expressions for initial
|
and final value themselves contain enough information, we usually cannot
|
and final value themselves contain enough information, we usually cannot
|
derive it from the context. */
|
derive it from the context. */
|
|
|
/* First check whether the answer does not follow from the bounds we gathered
|
/* First check whether the answer does not follow from the bounds we gathered
|
before. */
|
before. */
|
if (integer_nonzerop (iv0->step))
|
if (integer_nonzerop (iv0->step))
|
dstep = tree_to_double_int (iv0->step);
|
dstep = tree_to_double_int (iv0->step);
|
else
|
else
|
{
|
{
|
dstep = double_int_sext (tree_to_double_int (iv1->step),
|
dstep = double_int_sext (tree_to_double_int (iv1->step),
|
TYPE_PRECISION (type));
|
TYPE_PRECISION (type));
|
dstep = double_int_neg (dstep);
|
dstep = double_int_neg (dstep);
|
}
|
}
|
|
|
mpz_init (mstep);
|
mpz_init (mstep);
|
mpz_set_double_int (mstep, dstep, true);
|
mpz_set_double_int (mstep, dstep, true);
|
mpz_neg (mstep, mstep);
|
mpz_neg (mstep, mstep);
|
mpz_add_ui (mstep, mstep, 1);
|
mpz_add_ui (mstep, mstep, 1);
|
|
|
rolls_p = mpz_cmp (mstep, bnds->below) <= 0;
|
rolls_p = mpz_cmp (mstep, bnds->below) <= 0;
|
|
|
mpz_init (max);
|
mpz_init (max);
|
mpz_set_double_int (max, double_int_mask (TYPE_PRECISION (type)), true);
|
mpz_set_double_int (max, double_int_mask (TYPE_PRECISION (type)), true);
|
mpz_add (max, max, mstep);
|
mpz_add (max, max, mstep);
|
no_overflow_p = (mpz_cmp (bnds->up, max) <= 0
|
no_overflow_p = (mpz_cmp (bnds->up, max) <= 0
|
/* For pointers, only values lying inside a single object
|
/* For pointers, only values lying inside a single object
|
can be compared or manipulated by pointer arithmetics.
|
can be compared or manipulated by pointer arithmetics.
|
Gcc in general does not allow or handle objects larger
|
Gcc in general does not allow or handle objects larger
|
than half of the address space, hence the upper bound
|
than half of the address space, hence the upper bound
|
is satisfied for pointers. */
|
is satisfied for pointers. */
|
|| POINTER_TYPE_P (type));
|
|| POINTER_TYPE_P (type));
|
mpz_clear (mstep);
|
mpz_clear (mstep);
|
mpz_clear (max);
|
mpz_clear (max);
|
|
|
if (rolls_p && no_overflow_p)
|
if (rolls_p && no_overflow_p)
|
return;
|
return;
|
|
|
type1 = type;
|
type1 = type;
|
if (POINTER_TYPE_P (type))
|
if (POINTER_TYPE_P (type))
|
type1 = sizetype;
|
type1 = sizetype;
|
|
|
/* Now the hard part; we must formulate the assumption(s) as expressions, and
|
/* Now the hard part; we must formulate the assumption(s) as expressions, and
|
we must be careful not to introduce overflow. */
|
we must be careful not to introduce overflow. */
|
|
|
if (integer_nonzerop (iv0->step))
|
if (integer_nonzerop (iv0->step))
|
{
|
{
|
diff = fold_build2 (MINUS_EXPR, type1,
|
diff = fold_build2 (MINUS_EXPR, type1,
|
iv0->step, build_int_cst (type1, 1));
|
iv0->step, build_int_cst (type1, 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, type1,
|
bound = fold_build2 (PLUS_EXPR, type1,
|
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, type1,
|
mbzl = fold_build2 (MINUS_EXPR, type1,
|
fold_convert (type1, iv0->base), diff);
|
fold_convert (type1, iv0->base), diff);
|
mbzr = fold_convert (type1, iv1->base);
|
mbzr = fold_convert (type1, iv1->base);
|
}
|
}
|
else
|
else
|
{
|
{
|
diff = fold_build2 (PLUS_EXPR, type1,
|
diff = fold_build2 (PLUS_EXPR, type1,
|
iv1->step, build_int_cst (type1, 1));
|
iv1->step, build_int_cst (type1, 1));
|
|
|
if (!POINTER_TYPE_P (type))
|
if (!POINTER_TYPE_P (type))
|
{
|
{
|
bound = fold_build2 (PLUS_EXPR, type1,
|
bound = fold_build2 (PLUS_EXPR, type1,
|
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 = fold_convert (type1, iv0->base);
|
mbzl = fold_convert (type1, iv0->base);
|
mbzr = fold_build2 (MINUS_EXPR, type1,
|
mbzr = fold_build2 (MINUS_EXPR, type1,
|
fold_convert (type1, iv1->base), diff);
|
fold_convert (type1, iv1->base), diff);
|
}
|
}
|
|
|
if (!integer_nonzerop (assumption))
|
if (!integer_nonzerop (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 (!rolls_p)
|
if (!rolls_p)
|
{
|
{
|
mbz = fold_build2 (GT_EXPR, boolean_type_node, mbzl, mbzr);
|
mbz = fold_build2 (GT_EXPR, boolean_type_node, mbzl, mbzr);
|
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. BNDS bounds the difference
|
iterations is stored to NITER. BNDS bounds the difference
|
IV1->base - IV0->base. EXIT_MUST_BE_TAKEN is true if we know
|
IV1->base - IV0->base. EXIT_MUST_BE_TAKEN is true if we know
|
that the exit must be taken eventually. */
|
that the exit must be taken eventually. */
|
|
|
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 exit_must_be_taken, bounds *bnds)
|
bool exit_must_be_taken, bounds *bnds)
|
{
|
{
|
tree niter_type = unsigned_type_for (type);
|
tree niter_type = unsigned_type_for (type);
|
tree delta, step, s;
|
tree delta, step, s;
|
mpz_t mstep, tmp;
|
mpz_t mstep, tmp;
|
|
|
if (integer_nonzerop (iv0->step))
|
if (integer_nonzerop (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 ((integer_onep (iv0->step) && integer_zerop (iv1->step))
|
if ((integer_onep (iv0->step) && integer_zerop (iv1->step))
|
|| (integer_all_onesp (iv1->step) && integer_zerop (iv0->step)))
|
|| (integer_all_onesp (iv1->step) && integer_zerop (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.
|
|
|
First try to derive a lower bound on the value of
|
First try to derive a lower bound on the value of
|
iv1->base - iv0->base, computed in full precision. If the difference
|
iv1->base - iv0->base, computed in full precision. If the difference
|
is nonnegative, we are done, otherwise we must record the
|
is nonnegative, we are done, otherwise we must record the
|
condition. */
|
condition. */
|
|
|
if (mpz_sgn (bnds->below) < 0)
|
if (mpz_sgn (bnds->below) < 0)
|
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;
|
niter->max = mpz_get_double_int (niter_type, bnds->up, false);
|
niter->max = mpz_get_double_int (niter_type, bnds->up, false);
|
return true;
|
return true;
|
}
|
}
|
|
|
if (integer_nonzerop (iv0->step))
|
if (integer_nonzerop (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,
|
exit_must_be_taken, bnds))
|
exit_must_be_taken, bnds))
|
{
|
{
|
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, bnds);
|
return number_of_iterations_ne (type, &zps, delta, niter, true, bnds);
|
}
|
}
|
|
|
/* 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, bnds);
|
assert_loop_rolls_lt (type, iv0, iv1, niter, bnds);
|
|
|
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);
|
|
|
mpz_init (mstep);
|
mpz_init (mstep);
|
mpz_init (tmp);
|
mpz_init (tmp);
|
mpz_set_double_int (mstep, tree_to_double_int (step), true);
|
mpz_set_double_int (mstep, tree_to_double_int (step), true);
|
mpz_add (tmp, bnds->up, mstep);
|
mpz_add (tmp, bnds->up, mstep);
|
mpz_sub_ui (tmp, tmp, 1);
|
mpz_sub_ui (tmp, tmp, 1);
|
mpz_fdiv_q (tmp, tmp, mstep);
|
mpz_fdiv_q (tmp, tmp, mstep);
|
niter->max = mpz_get_double_int (niter_type, tmp, false);
|
niter->max = mpz_get_double_int (niter_type, tmp, false);
|
mpz_clear (mstep);
|
mpz_clear (mstep);
|
mpz_clear (tmp);
|
mpz_clear (tmp);
|
|
|
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. EXIT_MUST_BE_TAKEN is true if
|
iterations is stored to NITER. EXIT_MUST_BE_TAKEN 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). BNDS bounds the difference IV1->base - IV0->base. */
|
is the case). BNDS bounds the difference IV1->base - IV0->base. */
|
|
|
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 exit_must_be_taken,
|
struct tree_niter_desc *niter, bool exit_must_be_taken,
|
bounds *bnds)
|
bounds *bnds)
|
{
|
{
|
tree assumption;
|
tree assumption;
|
tree type1 = type;
|
tree type1 = type;
|
if (POINTER_TYPE_P (type))
|
if (POINTER_TYPE_P (type))
|
type1 = sizetype;
|
type1 = sizetype;
|
|
|
/* 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. We do not check
|
equal to this value, the loop rolls forever. We do not check
|
this condition for pointer type ivs, as the code cannot rely on
|
this condition for pointer type ivs, as the code cannot rely on
|
the object to that the pointer points being placed at the end of
|
the object to that the pointer points being placed at the end of
|
the address space (and more pragmatically, TYPE_{MIN,MAX}_VALUE is
|
the address space (and more pragmatically, TYPE_{MIN,MAX}_VALUE is
|
not defined for pointers). */
|
not defined for pointers). */
|
|
|
if (!exit_must_be_taken && !POINTER_TYPE_P (type))
|
if (!exit_must_be_taken && !POINTER_TYPE_P (type))
|
{
|
{
|
if (integer_nonzerop (iv0->step))
|
if (integer_nonzerop (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 (integer_zerop (assumption))
|
if (integer_zerop (assumption))
|
return false;
|
return false;
|
if (!integer_nonzerop (assumption))
|
if (!integer_nonzerop (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 (integer_nonzerop (iv0->step))
|
if (integer_nonzerop (iv0->step))
|
{
|
{
|
if (POINTER_TYPE_P (type))
|
if (POINTER_TYPE_P (type))
|
iv1->base = fold_build2 (POINTER_PLUS_EXPR, type, iv1->base,
|
iv1->base = fold_build2 (POINTER_PLUS_EXPR, type, iv1->base,
|
build_int_cst (type1, 1));
|
build_int_cst (type1, 1));
|
else
|
else
|
iv1->base = fold_build2 (PLUS_EXPR, type1, iv1->base,
|
iv1->base = fold_build2 (PLUS_EXPR, type1, iv1->base,
|
build_int_cst (type1, 1));
|
build_int_cst (type1, 1));
|
}
|
}
|
else if (POINTER_TYPE_P (type))
|
else if (POINTER_TYPE_P (type))
|
iv0->base = fold_build2 (POINTER_PLUS_EXPR, type, iv0->base,
|
iv0->base = fold_build2 (POINTER_PLUS_EXPR, type, iv0->base,
|
fold_build1 (NEGATE_EXPR, type1,
|
fold_build1 (NEGATE_EXPR, type1,
|
build_int_cst (type1, 1)));
|
build_int_cst (type1, 1)));
|
else
|
else
|
iv0->base = fold_build2 (MINUS_EXPR, type1,
|
iv0->base = fold_build2 (MINUS_EXPR, type1,
|
iv0->base, build_int_cst (type1, 1));
|
iv0->base, build_int_cst (type1, 1));
|
|
|
bounds_add (bnds, double_int_one, type1);
|
bounds_add (bnds, double_int_one, type1);
|
|
|
return number_of_iterations_lt (type, iv0, iv1, niter, exit_must_be_taken,
|
return number_of_iterations_lt (type, iv0, iv1, niter, exit_must_be_taken,
|
bnds);
|
bnds);
|
}
|
}
|
|
|
/* Dumps description of affine induction variable IV to FILE. */
|
/* Dumps description of affine induction variable IV to FILE. */
|
|
|
static void
|
static void
|
dump_affine_iv (FILE *file, affine_iv *iv)
|
dump_affine_iv (FILE *file, affine_iv *iv)
|
{
|
{
|
if (!integer_zerop (iv->step))
|
if (!integer_zerop (iv->step))
|
fprintf (file, "[");
|
fprintf (file, "[");
|
|
|
print_generic_expr (dump_file, iv->base, TDF_SLIM);
|
print_generic_expr (dump_file, iv->base, TDF_SLIM);
|
|
|
if (!integer_zerop (iv->step))
|
if (!integer_zerop (iv->step))
|
{
|
{
|
fprintf (file, ", + , ");
|
fprintf (file, ", + , ");
|
print_generic_expr (dump_file, iv->step, TDF_SLIM);
|
print_generic_expr (dump_file, iv->step, TDF_SLIM);
|
fprintf (file, "]%s", iv->no_overflow ? "(no_overflow)" : "");
|
fprintf (file, "]%s", iv->no_overflow ? "(no_overflow)" : "");
|
}
|
}
|
}
|
}
|
|
|
/* 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).
|
|
|
LOOP is the loop whose number of iterations we are determining.
|
LOOP is the loop whose number of iterations we are determining.
|
|
|
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 (struct loop *loop,
|
number_of_iterations_cond (struct loop *loop,
|
tree type, affine_iv *iv0, enum tree_code code,
|
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 exit_must_be_taken = false, ret;
|
bool exit_must_be_taken = false, ret;
|
bounds bnds;
|
bounds bnds;
|
|
|
/* 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->max = double_int_zero;
|
niter->max = double_int_zero;
|
|
|
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 && integer_zerop (iv0->step)))
|
|| (code == NE_EXPR && integer_zerop (iv0->step)))
|
{
|
{
|
SWAP (iv0, iv1);
|
SWAP (iv0, iv1);
|
code = swap_tree_comparison (code);
|
code = swap_tree_comparison (code);
|
}
|
}
|
|
|
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). */
|
avoid undefined behavior by casting to size_t and back). */
|
iv0->no_overflow = true;
|
iv0->no_overflow = true;
|
iv1->no_overflow = true;
|
iv1->no_overflow = true;
|
}
|
}
|
|
|
/* If the control induction variable does not overflow and the only exit
|
/* If the control induction variable does not overflow and the only exit
|
from the loop is the one that we analyze, we know it must be taken
|
from the loop is the one that we analyze, we know it must be taken
|
eventually. */
|
eventually. */
|
if (only_exit)
|
if (only_exit)
|
{
|
{
|
if (!integer_zerop (iv0->step) && iv0->no_overflow)
|
if (!integer_zerop (iv0->step) && iv0->no_overflow)
|
exit_must_be_taken = true;
|
exit_must_be_taken = true;
|
else if (!integer_zerop (iv1->step) && iv1->no_overflow)
|
else if (!integer_zerop (iv1->step) && iv1->no_overflow)
|
exit_must_be_taken = true;
|
exit_must_be_taken = true;
|
}
|
}
|
|
|
/* 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 (!integer_zerop (iv0->step) && !integer_zerop (iv1->step))
|
if (!integer_zerop (iv0->step) && !integer_zerop (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 = build_int_cst (type, 0);
|
iv1->step = build_int_cst (type, 0);
|
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 (integer_zerop (iv0->step) && integer_zerop (iv1->step))
|
if (integer_zerop (iv0->step) && integer_zerop (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 (!integer_zerop (iv1->step) && !tree_int_cst_sign_bit (iv1->step))
|
if (!integer_zerop (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 (integer_zerop (fold_build2 (code, boolean_type_node, iv0->base, iv1->base)))
|
if (integer_zerop (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);
|
niter->max = double_int_zero;
|
niter->max = double_int_zero;
|
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. */
|
bound_difference (loop, iv1->base, iv0->base, &bnds);
|
bound_difference (loop, iv1->base, iv0->base, &bnds);
|
|
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
{
|
{
|
fprintf (dump_file,
|
fprintf (dump_file,
|
"Analyzing # of iterations of loop %d\n", loop->num);
|
"Analyzing # of iterations of loop %d\n", loop->num);
|
|
|
fprintf (dump_file, " exit condition ");
|
fprintf (dump_file, " exit condition ");
|
dump_affine_iv (dump_file, iv0);
|
dump_affine_iv (dump_file, iv0);
|
fprintf (dump_file, " %s ",
|
fprintf (dump_file, " %s ",
|
code == NE_EXPR ? "!="
|
code == NE_EXPR ? "!="
|
: code == LT_EXPR ? "<"
|
: code == LT_EXPR ? "<"
|
: "<=");
|
: "<=");
|
dump_affine_iv (dump_file, iv1);
|
dump_affine_iv (dump_file, iv1);
|
fprintf (dump_file, "\n");
|
fprintf (dump_file, "\n");
|
|
|
fprintf (dump_file, " bounds on difference of bases: ");
|
fprintf (dump_file, " bounds on difference of bases: ");
|
mpz_out_str (dump_file, 10, bnds.below);
|
mpz_out_str (dump_file, 10, bnds.below);
|
fprintf (dump_file, " ... ");
|
fprintf (dump_file, " ... ");
|
mpz_out_str (dump_file, 10, bnds.up);
|
mpz_out_str (dump_file, 10, bnds.up);
|
fprintf (dump_file, "\n");
|
fprintf (dump_file, "\n");
|
}
|
}
|
|
|
switch (code)
|
switch (code)
|
{
|
{
|
case NE_EXPR:
|
case NE_EXPR:
|
gcc_assert (integer_zerop (iv1->step));
|
gcc_assert (integer_zerop (iv1->step));
|
ret = number_of_iterations_ne (type, iv0, iv1->base, niter,
|
ret = number_of_iterations_ne (type, iv0, iv1->base, niter,
|
exit_must_be_taken, &bnds);
|
exit_must_be_taken, &bnds);
|
break;
|
break;
|
|
|
case LT_EXPR:
|
case LT_EXPR:
|
ret = number_of_iterations_lt (type, iv0, iv1, niter, exit_must_be_taken,
|
ret = number_of_iterations_lt (type, iv0, iv1, niter, exit_must_be_taken,
|
&bnds);
|
&bnds);
|
break;
|
break;
|
|
|
case LE_EXPR:
|
case LE_EXPR:
|
ret = number_of_iterations_le (type, iv0, iv1, niter, exit_must_be_taken,
|
ret = number_of_iterations_le (type, iv0, iv1, niter, exit_must_be_taken,
|
&bnds);
|
&bnds);
|
break;
|
break;
|
|
|
default:
|
default:
|
gcc_unreachable ();
|
gcc_unreachable ();
|
}
|
}
|
|
|
mpz_clear (bnds.up);
|
mpz_clear (bnds.up);
|
mpz_clear (bnds.below);
|
mpz_clear (bnds.below);
|
|
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
{
|
{
|
if (ret)
|
if (ret)
|
{
|
{
|
fprintf (dump_file, " result:\n");
|
fprintf (dump_file, " result:\n");
|
if (!integer_nonzerop (niter->assumptions))
|
if (!integer_nonzerop (niter->assumptions))
|
{
|
{
|
fprintf (dump_file, " under assumptions ");
|
fprintf (dump_file, " under assumptions ");
|
print_generic_expr (dump_file, niter->assumptions, TDF_SLIM);
|
print_generic_expr (dump_file, niter->assumptions, TDF_SLIM);
|
fprintf (dump_file, "\n");
|
fprintf (dump_file, "\n");
|
}
|
}
|
|
|
if (!integer_zerop (niter->may_be_zero))
|
if (!integer_zerop (niter->may_be_zero))
|
{
|
{
|
fprintf (dump_file, " zero if ");
|
fprintf (dump_file, " zero if ");
|
print_generic_expr (dump_file, niter->may_be_zero, TDF_SLIM);
|
print_generic_expr (dump_file, niter->may_be_zero, TDF_SLIM);
|
fprintf (dump_file, "\n");
|
fprintf (dump_file, "\n");
|
}
|
}
|
|
|
fprintf (dump_file, " # of iterations ");
|
fprintf (dump_file, " # of iterations ");
|
print_generic_expr (dump_file, niter->niter, TDF_SLIM);
|
print_generic_expr (dump_file, niter->niter, TDF_SLIM);
|
fprintf (dump_file, ", bounded by ");
|
fprintf (dump_file, ", bounded by ");
|
dump_double_int (dump_file, niter->max, true);
|
dump_double_int (dump_file, niter->max, true);
|
fprintf (dump_file, "\n");
|
fprintf (dump_file, "\n");
|
}
|
}
|
else
|
else
|
fprintf (dump_file, " failed\n\n");
|
fprintf (dump_file, " failed\n\n");
|
}
|
}
|
return ret;
|
return ret;
|
}
|
}
|
|
|
/* 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_tree)
|
simplify_replace_tree (tree expr, tree old, tree new_tree)
|
{
|
{
|
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_tree);
|
return unshare_expr (new_tree);
|
|
|
if (!EXPR_P (expr))
|
if (!EXPR_P (expr))
|
return expr;
|
return expr;
|
|
|
n = TREE_OPERAND_LENGTH (expr);
|
n = TREE_OPERAND_LENGTH (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_tree);
|
se = simplify_replace_tree (e, old, new_tree);
|
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, e1;
|
tree ret = NULL_TREE, e, ee, e1;
|
enum tree_code code;
|
enum tree_code code;
|
gimple stmt;
|
gimple stmt;
|
|
|
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_OPERAND_LENGTH (expr);
|
n = TREE_OPERAND_LENGTH (expr);
|
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 (gimple_code (stmt) == GIMPLE_PHI)
|
if (gimple_code (stmt) == GIMPLE_PHI)
|
{
|
{
|
basic_block src, dest;
|
basic_block src, dest;
|
|
|
if (gimple_phi_num_args (stmt) != 1)
|
if (gimple_phi_num_args (stmt) != 1)
|
return expr;
|
return expr;
|
e = PHI_ARG_DEF (stmt, 0);
|
e = PHI_ARG_DEF (stmt, 0);
|
|
|
/* Avoid propagating through loop exit phi nodes, which
|
/* Avoid propagating through loop exit phi nodes, which
|
could break loop-closed SSA form restrictions. */
|
could break loop-closed SSA form restrictions. */
|
dest = gimple_bb (stmt);
|
dest = gimple_bb (stmt);
|
src = single_pred (dest);
|
src = single_pred (dest);
|
if (TREE_CODE (e) == SSA_NAME
|
if (TREE_CODE (e) == SSA_NAME
|
&& src->loop_father != dest->loop_father)
|
&& src->loop_father != dest->loop_father)
|
return expr;
|
return expr;
|
|
|
return expand_simple_operations (e);
|
return expand_simple_operations (e);
|
}
|
}
|
if (gimple_code (stmt) != GIMPLE_ASSIGN)
|
if (gimple_code (stmt) != GIMPLE_ASSIGN)
|
return expr;
|
return expr;
|
|
|
e = gimple_assign_rhs1 (stmt);
|
e = gimple_assign_rhs1 (stmt);
|
code = gimple_assign_rhs_code (stmt);
|
code = gimple_assign_rhs_code (stmt);
|
if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS)
|
if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS)
|
{
|
{
|
if (is_gimple_min_invariant (e))
|
if (is_gimple_min_invariant (e))
|
return e;
|
return e;
|
|
|
if (code == SSA_NAME)
|
if (code == SSA_NAME)
|
return expand_simple_operations (e);
|
return expand_simple_operations (e);
|
|
|
return expr;
|
return expr;
|
}
|
}
|
|
|
switch (code)
|
switch (code)
|
{
|
{
|
CASE_CONVERT:
|
CASE_CONVERT:
|
/* Casts are simple. */
|
/* Casts are simple. */
|
ee = expand_simple_operations (e);
|
ee = expand_simple_operations (e);
|
return fold_build1 (code, TREE_TYPE (expr), ee);
|
return fold_build1 (code, TREE_TYPE (expr), ee);
|
|
|
case PLUS_EXPR:
|
case PLUS_EXPR:
|
case MINUS_EXPR:
|
case MINUS_EXPR:
|
case POINTER_PLUS_EXPR:
|
case POINTER_PLUS_EXPR:
|
/* And increments and decrements by a constant are simple. */
|
/* And increments and decrements by a constant are simple. */
|
e1 = gimple_assign_rhs2 (stmt);
|
e1 = gimple_assign_rhs2 (stmt);
|
if (!is_gimple_min_invariant (e1))
|
if (!is_gimple_min_invariant (e1))
|
return expr;
|
return expr;
|
|
|
ee = expand_simple_operations (e);
|
ee = expand_simple_operations (e);
|
return fold_build2 (code, TREE_TYPE (expr), ee, e1);
|
return fold_build2 (code, TREE_TYPE (expr), ee, e1);
|
|
|
default:
|
default:
|
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). */
|
|
|
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 (integer_zerop (e) || integer_nonzerop (e))
|
if (integer_zerop (e) || integer_nonzerop (e))
|
return e;
|
return e;
|
|
|
e = simplify_replace_tree (expr, e1, e0);
|
e = simplify_replace_tree (expr, e1, e0);
|
if (integer_zerop (e) || integer_nonzerop (e))
|
if (integer_zerop (e) || integer_nonzerop (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 (integer_zerop (e))
|
if (integer_zerop (e))
|
return e;
|
return e;
|
e = simplify_replace_tree (cond, e1, e0);
|
e = simplify_replace_tree (cond, e1, e0);
|
if (integer_zerop (e))
|
if (integer_zerop (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 (integer_zerop (e))
|
if (integer_zerop (e))
|
return boolean_true_node;
|
return boolean_true_node;
|
e = simplify_replace_tree (cond, e1, e0);
|
e = simplify_replace_tree (cond, e1, e0);
|
if (integer_zerop (e))
|
if (integer_zerop (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 (e && integer_nonzerop (e))
|
if (e && integer_nonzerop (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 && integer_zerop (e))
|
if (e && integer_zerop (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);
|
}
|
}
|
|
|
/* Tries to simplify EXPR using the conditions on entry to LOOP.
|
/* Tries to simplify EXPR using the conditions on entry to LOOP.
|
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)
|
{
|
{
|
edge e;
|
edge e;
|
basic_block bb;
|
basic_block bb;
|
gimple stmt;
|
gimple stmt;
|
tree cond;
|
tree 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;
|
|
|
stmt = last_stmt (e->src);
|
stmt = last_stmt (e->src);
|
cond = fold_build2 (gimple_cond_code (stmt),
|
cond = fold_build2 (gimple_cond_code (stmt),
|
boolean_type_node,
|
boolean_type_node,
|
gimple_cond_lhs (stmt),
|
gimple_cond_lhs (stmt),
|
gimple_cond_rhs (stmt));
|
gimple_cond_rhs (stmt));
|
if (e->flags & EDGE_FALSE_VALUE)
|
if (e->flags & EDGE_FALSE_VALUE)
|
cond = invert_truthvalue (cond);
|
cond = invert_truthvalue (cond);
|
expr = tree_simplify_using_condition (cond, expr);
|
expr = tree_simplify_using_condition (cond, expr);
|
++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. */
|
|
|
bool
|
bool
|
loop_only_exit_p (const struct loop *loop, const_edge exit)
|
loop_only_exit_p (const struct loop *loop, const_edge exit)
|
{
|
{
|
basic_block *body;
|
basic_block *body;
|
gimple_stmt_iterator bsi;
|
gimple_stmt_iterator bsi;
|
unsigned i;
|
unsigned i;
|
gimple call;
|
gimple call;
|
|
|
if (exit != single_exit (loop))
|
if (exit != single_exit (loop))
|
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 = gsi_start_bb (body[i]); !gsi_end_p (bsi); gsi_next (&bsi))
|
for (bsi = gsi_start_bb (body[i]); !gsi_end_p (bsi); gsi_next (&bsi))
|
{
|
{
|
call = gsi_stmt (bsi);
|
call = gsi_stmt (bsi);
|
if (gimple_code (call) != GIMPLE_CALL)
|
if (gimple_code (call) != GIMPLE_CALL)
|
continue;
|
continue;
|
|
|
if (gimple_has_side_effects (call))
|
if (gimple_has_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)
|
{
|
{
|
gimple stmt;
|
gimple stmt;
|
tree type;
|
tree 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 || gimple_code (stmt) != GIMPLE_COND)
|
if (!stmt || gimple_code (stmt) != GIMPLE_COND)
|
return false;
|
return false;
|
|
|
/* We want the condition for staying inside loop. */
|
/* We want the condition for staying inside loop. */
|
code = gimple_cond_code (stmt);
|
code = gimple_cond_code (stmt);
|
if (exit->flags & EDGE_TRUE_VALUE)
|
if (exit->flags & EDGE_TRUE_VALUE)
|
code = invert_tree_comparison (code, false);
|
code = invert_tree_comparison (code, false);
|
|
|
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 = gimple_cond_lhs (stmt);
|
op0 = gimple_cond_lhs (stmt);
|
op1 = gimple_cond_rhs (stmt);
|
op1 = gimple_cond_rhs (stmt);
|
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, loop_containing_stmt (stmt), op0, &iv0, false))
|
if (!simple_iv (loop, loop_containing_stmt (stmt), op0, &iv0, false))
|
return false;
|
return false;
|
if (!simple_iv (loop, loop_containing_stmt (stmt), op1, &iv1, false))
|
if (!simple_iv (loop, loop_containing_stmt (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 number of iterations. */
|
computing the number 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 (loop, type, &iv0, code, &iv1, niter,
|
if (!number_of_iterations_cond (loop, 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->assumptions
|
niter->assumptions
|
= simplify_using_initial_conditions (loop,
|
= simplify_using_initial_conditions (loop,
|
niter->assumptions);
|
niter->assumptions);
|
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);
|
|
|
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 = gimple_location (stmt);
|
location_t loc = gimple_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 (!integer_zerop (iv1.step)
|
if (!integer_zerop (iv1.step)
|
? (integer_zerop (iv0.step)
|
? (integer_zerop (iv0.step)
|
&& (integer_onep (iv1.step) || integer_all_onesp (iv1.step)))
|
&& (integer_onep (iv1.step) || integer_all_onesp (iv1.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");
|
|
|
warning_at ((LOCATION_LINE (loc) > 0) ? loc : input_location,
|
warning_at ((LOCATION_LINE (loc) > 0) ? loc : input_location,
|
OPT_Wunsafe_loop_optimizations, "%s", gettext (wording));
|
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 i;
|
unsigned i;
|
VEC (edge, heap) *exits = get_loop_exit_edges (loop);
|
VEC (edge, heap) *exits = get_loop_exit_edges (loop);
|
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; VEC_iterate (edge, exits, i, ex); i++)
|
for (i = 0; VEC_iterate (edge, exits, i, ex); 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 (integer_nonzerop (desc.may_be_zero))
|
if (integer_nonzerop (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 (!integer_zerop (desc.may_be_zero))
|
if (!integer_zerop (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;
|
}
|
}
|
}
|
}
|
VEC_free (edge, heap, exits);
|
VEC_free (edge, heap, exits);
|
|
|
return niter ? niter : chrec_dont_know;
|
return niter ? niter : chrec_dont_know;
|
}
|
}
|
|
|
/* Return true if loop is known to have bounded number of iterations. */
|
/* Return true if loop is known to have bounded number of iterations. */
|
|
|
bool
|
bool
|
finite_loop_p (struct loop *loop)
|
finite_loop_p (struct loop *loop)
|
{
|
{
|
unsigned i;
|
unsigned i;
|
VEC (edge, heap) *exits;
|
VEC (edge, heap) *exits;
|
edge ex;
|
edge ex;
|
struct tree_niter_desc desc;
|
struct tree_niter_desc desc;
|
bool finite = false;
|
bool finite = false;
|
|
|
if (flag_unsafe_loop_optimizations)
|
if (flag_unsafe_loop_optimizations)
|
return true;
|
return true;
|
if ((TREE_READONLY (current_function_decl)
|
if ((TREE_READONLY (current_function_decl)
|
|| DECL_PURE_P (current_function_decl))
|
|| DECL_PURE_P (current_function_decl))
|
&& !DECL_LOOPING_CONST_OR_PURE_P (current_function_decl))
|
&& !DECL_LOOPING_CONST_OR_PURE_P (current_function_decl))
|
{
|
{
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
fprintf (dump_file, "Found loop %i to be finite: it is within pure or const function.\n",
|
fprintf (dump_file, "Found loop %i to be finite: it is within pure or const function.\n",
|
loop->num);
|
loop->num);
|
return true;
|
return true;
|
}
|
}
|
|
|
exits = get_loop_exit_edges (loop);
|
exits = get_loop_exit_edges (loop);
|
for (i = 0; VEC_iterate (edge, exits, i, ex); i++)
|
for (i = 0; VEC_iterate (edge, exits, i, ex); 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))
|
{
|
{
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
{
|
{
|
fprintf (dump_file, "Found loop %i to be finite: iterating ", loop->num);
|
fprintf (dump_file, "Found loop %i to be finite: iterating ", loop->num);
|
print_generic_expr (dump_file, desc.niter, TDF_SLIM);
|
print_generic_expr (dump_file, desc.niter, TDF_SLIM);
|
fprintf (dump_file, " times\n");
|
fprintf (dump_file, " times\n");
|
}
|
}
|
finite = true;
|
finite = true;
|
break;
|
break;
|
}
|
}
|
}
|
}
|
VEC_free (edge, heap, exits);
|
VEC_free (edge, heap, exits);
|
return finite;
|
return finite;
|
}
|
}
|
|
|
/*
|
/*
|
|
|
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 gimple
|
static gimple
|
chain_of_csts_start (struct loop *loop, tree x)
|
chain_of_csts_start (struct loop *loop, tree x)
|
{
|
{
|
gimple stmt = SSA_NAME_DEF_STMT (x);
|
gimple stmt = SSA_NAME_DEF_STMT (x);
|
tree use;
|
tree use;
|
basic_block bb = gimple_bb (stmt);
|
basic_block bb = gimple_bb (stmt);
|
enum tree_code code;
|
enum tree_code code;
|
|
|
if (!bb
|
if (!bb
|
|| !flow_bb_inside_loop_p (loop, bb))
|
|| !flow_bb_inside_loop_p (loop, bb))
|
return NULL;
|
return NULL;
|
|
|
if (gimple_code (stmt) == GIMPLE_PHI)
|
if (gimple_code (stmt) == GIMPLE_PHI)
|
{
|
{
|
if (bb == loop->header)
|
if (bb == loop->header)
|
return stmt;
|
return stmt;
|
|
|
return NULL;
|
return NULL;
|
}
|
}
|
|
|
if (gimple_code (stmt) != GIMPLE_ASSIGN)
|
if (gimple_code (stmt) != GIMPLE_ASSIGN)
|
return NULL;
|
return NULL;
|
|
|
code = gimple_assign_rhs_code (stmt);
|
code = gimple_assign_rhs_code (stmt);
|
if (gimple_references_memory_p (stmt)
|
if (gimple_references_memory_p (stmt)
|
|| TREE_CODE_CLASS (code) == tcc_reference
|
|| TREE_CODE_CLASS (code) == tcc_reference
|
|| (code == ADDR_EXPR
|
|| (code == ADDR_EXPR
|
&& !is_gimple_min_invariant (gimple_assign_rhs1 (stmt))))
|
&& !is_gimple_min_invariant (gimple_assign_rhs1 (stmt))))
|
return NULL;
|
return NULL;
|
|
|
use = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_USE);
|
use = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_USE);
|
if (use == NULL_TREE)
|
if (use == NULL_TREE)
|
return NULL;
|
return NULL;
|
|
|
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, otherwise NULL is returned. */
|
If such phi node exists, it is returned, otherwise NULL is returned. */
|
|
|
static gimple
|
static gimple
|
get_base_for (struct loop *loop, tree x)
|
get_base_for (struct loop *loop, tree x)
|
{
|
{
|
gimple phi;
|
gimple phi;
|
tree init, next;
|
tree init, next;
|
|
|
if (is_gimple_min_invariant (x))
|
if (is_gimple_min_invariant (x))
|
return NULL;
|
return NULL;
|
|
|
phi = chain_of_csts_start (loop, x);
|
phi = chain_of_csts_start (loop, x);
|
if (!phi)
|
if (!phi)
|
return NULL;
|
return NULL;
|
|
|
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;
|
return NULL;
|
|
|
if (!is_gimple_min_invariant (init))
|
if (!is_gimple_min_invariant (init))
|
return NULL;
|
return NULL;
|
|
|
if (chain_of_csts_start (loop, next) != phi)
|
if (chain_of_csts_start (loop, next) != phi)
|
return NULL;
|
return NULL;
|
|
|
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)
|
{
|
{
|
gimple stmt;
|
gimple stmt;
|
|
|
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 (gimple_code (stmt) == GIMPLE_PHI)
|
if (gimple_code (stmt) == GIMPLE_PHI)
|
return base;
|
return base;
|
|
|
gcc_assert (is_gimple_assign (stmt));
|
gcc_assert (is_gimple_assign (stmt));
|
|
|
/* STMT must be either an assignment of a single SSA name or an
|
/* STMT must be either an assignment of a single SSA name or an
|
expression involving an SSA name and a constant. Try to fold that
|
expression involving an SSA name and a constant. Try to fold that
|
expression using the value for the SSA name. */
|
expression using the value for the SSA name. */
|
if (gimple_assign_ssa_name_copy_p (stmt))
|
if (gimple_assign_ssa_name_copy_p (stmt))
|
return get_val_for (gimple_assign_rhs1 (stmt), base);
|
return get_val_for (gimple_assign_rhs1 (stmt), base);
|
else if (gimple_assign_rhs_class (stmt) == GIMPLE_UNARY_RHS
|
else if (gimple_assign_rhs_class (stmt) == GIMPLE_UNARY_RHS
|
&& TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME)
|
&& TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME)
|
{
|
{
|
return fold_build1 (gimple_assign_rhs_code (stmt),
|
return fold_build1 (gimple_assign_rhs_code (stmt),
|
gimple_expr_type (stmt),
|
gimple_expr_type (stmt),
|
get_val_for (gimple_assign_rhs1 (stmt), base));
|
get_val_for (gimple_assign_rhs1 (stmt), base));
|
}
|
}
|
else if (gimple_assign_rhs_class (stmt) == GIMPLE_BINARY_RHS)
|
else if (gimple_assign_rhs_class (stmt) == GIMPLE_BINARY_RHS)
|
{
|
{
|
tree rhs1 = gimple_assign_rhs1 (stmt);
|
tree rhs1 = gimple_assign_rhs1 (stmt);
|
tree rhs2 = gimple_assign_rhs2 (stmt);
|
tree rhs2 = gimple_assign_rhs2 (stmt);
|
if (TREE_CODE (rhs1) == SSA_NAME)
|
if (TREE_CODE (rhs1) == SSA_NAME)
|
rhs1 = get_val_for (rhs1, base);
|
rhs1 = get_val_for (rhs1, base);
|
else if (TREE_CODE (rhs2) == SSA_NAME)
|
else if (TREE_CODE (rhs2) == SSA_NAME)
|
rhs2 = get_val_for (rhs2, base);
|
rhs2 = get_val_for (rhs2, base);
|
else
|
else
|
gcc_unreachable ();
|
gcc_unreachable ();
|
return fold_build2 (gimple_assign_rhs_code (stmt),
|
return fold_build2 (gimple_assign_rhs_code (stmt),
|
gimple_expr_type (stmt), rhs1, rhs2);
|
gimple_expr_type (stmt), rhs1, rhs2);
|
}
|
}
|
else
|
else
|
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 acnd;
|
tree acnd;
|
tree op[2], val[2], next[2], aval[2];
|
tree op[2], val[2], next[2], aval[2];
|
gimple phi, cond;
|
gimple phi, cond;
|
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 || gimple_code (cond) != GIMPLE_COND)
|
if (!cond || gimple_code (cond) != GIMPLE_COND)
|
return chrec_dont_know;
|
return chrec_dont_know;
|
|
|
cmp = gimple_cond_code (cond);
|
cmp = gimple_cond_code (cond);
|
if (exit->flags & EDGE_TRUE_VALUE)
|
if (exit->flags & EDGE_TRUE_VALUE)
|
cmp = invert_tree_comparison (cmp, false);
|
cmp = invert_tree_comparison (cmp, false);
|
|
|
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:
|
op[0] = gimple_cond_lhs (cond);
|
op[0] = gimple_cond_lhs (cond);
|
op[1] = gimple_cond_rhs (cond);
|
op[1] = gimple_cond_rhs (cond);
|
break;
|
break;
|
|
|
default:
|
default:
|
return chrec_dont_know;
|
return chrec_dont_know;
|
}
|
}
|
|
|
for (j = 0; j < 2; j++)
|
for (j = 0; j < 2; j++)
|
{
|
{
|
if (is_gimple_min_invariant (op[j]))
|
if (is_gimple_min_invariant (op[j]))
|
{
|
{
|
val[j] = op[j];
|
val[j] = op[j];
|
next[j] = NULL_TREE;
|
next[j] = NULL_TREE;
|
op[j] = NULL_TREE;
|
op[j] = NULL_TREE;
|
}
|
}
|
else
|
else
|
{
|
{
|
phi = get_base_for (loop, op[j]);
|
phi = get_base_for (loop, op[j]);
|
if (!phi)
|
if (!phi)
|
return chrec_dont_know;
|
return chrec_dont_know;
|
val[j] = PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop));
|
val[j] = PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop));
|
next[j] = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (loop));
|
next[j] = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (loop));
|
}
|
}
|
}
|
}
|
|
|
/* 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 && integer_zerop (acnd))
|
if (acnd && integer_zerop (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 i;
|
unsigned i;
|
VEC (edge, heap) *exits = get_loop_exit_edges (loop);
|
VEC (edge, heap) *exits = get_loop_exit_edges (loop);
|
edge ex;
|
edge ex;
|
tree niter = NULL_TREE, aniter;
|
tree niter = NULL_TREE, aniter;
|
|
|
*exit = NULL;
|
*exit = NULL;
|
|
|
/* Loops with multiple exits are expensive to handle and less important. */
|
/* Loops with multiple exits are expensive to handle and less important. */
|
if (!flag_expensive_optimizations
|
if (!flag_expensive_optimizations
|
&& VEC_length (edge, exits) > 1)
|
&& VEC_length (edge, exits) > 1)
|
return chrec_dont_know;
|
return chrec_dont_know;
|
|
|
for (i = 0; VEC_iterate (edge, exits, i, ex); i++)
|
for (i = 0; VEC_iterate (edge, exits, i, ex); 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;
|
}
|
}
|
VEC_free (edge, heap, exits);
|
VEC_free (edge, heap, 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.
|
|
|
*/
|
*/
|
|
|
static double_int derive_constant_upper_bound_ops (tree, tree,
|
static double_int derive_constant_upper_bound_ops (tree, tree,
|
enum tree_code, tree);
|
enum tree_code, tree);
|
|
|
/* Returns a constant upper bound on the value of the right-hand side of
|
/* Returns a constant upper bound on the value of the right-hand side of
|
an assignment statement STMT. */
|
an assignment statement STMT. */
|
|
|
static double_int
|
static double_int
|
derive_constant_upper_bound_assign (gimple stmt)
|
derive_constant_upper_bound_assign (gimple stmt)
|
{
|
{
|
enum tree_code code = gimple_assign_rhs_code (stmt);
|
enum tree_code code = gimple_assign_rhs_code (stmt);
|
tree op0 = gimple_assign_rhs1 (stmt);
|
tree op0 = gimple_assign_rhs1 (stmt);
|
tree op1 = gimple_assign_rhs2 (stmt);
|
tree op1 = gimple_assign_rhs2 (stmt);
|
|
|
return derive_constant_upper_bound_ops (TREE_TYPE (gimple_assign_lhs (stmt)),
|
return derive_constant_upper_bound_ops (TREE_TYPE (gimple_assign_lhs (stmt)),
|
op0, code, op1);
|
op0, code, op1);
|
}
|
}
|
|
|
/* 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. */
|
|
|
static double_int
|
static double_int
|
derive_constant_upper_bound (tree val)
|
derive_constant_upper_bound (tree val)
|
{
|
{
|
enum tree_code code;
|
enum tree_code code;
|
tree op0, op1;
|
tree op0, op1;
|
|
|
extract_ops_from_tree (val, &code, &op0, &op1);
|
extract_ops_from_tree (val, &code, &op0, &op1);
|
return derive_constant_upper_bound_ops (TREE_TYPE (val), op0, code, op1);
|
return derive_constant_upper_bound_ops (TREE_TYPE (val), op0, code, op1);
|
}
|
}
|
|
|
/* Returns a constant upper bound on the value of expression OP0 CODE OP1,
|
/* Returns a constant upper bound on the value of expression OP0 CODE OP1,
|
whose type is TYPE. The expression is considered to be unsigned. If
|
whose type is TYPE. The expression is considered to be unsigned. If
|
its type is signed, its value must be nonnegative. */
|
its type is signed, its value must be nonnegative. */
|
|
|
static double_int
|
static double_int
|
derive_constant_upper_bound_ops (tree type, tree op0,
|
derive_constant_upper_bound_ops (tree type, tree op0,
|
enum tree_code code, tree op1)
|
enum tree_code code, tree op1)
|
{
|
{
|
tree subtype, maxt;
|
tree subtype, maxt;
|
double_int bnd, max, mmax, cst;
|
double_int bnd, max, mmax, cst;
|
gimple stmt;
|
gimple stmt;
|
|
|
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 (code)
|
switch (code)
|
{
|
{
|
case INTEGER_CST:
|
case INTEGER_CST:
|
return tree_to_double_int (op0);
|
return tree_to_double_int (op0);
|
|
|
CASE_CONVERT:
|
CASE_CONVERT:
|
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)
|
&& !tree_expr_nonnegative_p (op0))
|
&& !tree_expr_nonnegative_p (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);
|
bnd = derive_constant_upper_bound (op0);
|
|
|
/* 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 POINTER_PLUS_EXPR:
|
case POINTER_PLUS_EXPR:
|
case MINUS_EXPR:
|
case MINUS_EXPR:
|
if (TREE_CODE (op1) != INTEGER_CST
|
if (TREE_CODE (op1) != INTEGER_CST
|
|| !tree_expr_nonnegative_p (op0))
|
|| !tree_expr_nonnegative_p (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 (code != MINUS_EXPR)
|
if (code != MINUS_EXPR)
|
cst = double_int_neg (cst);
|
cst = double_int_neg (cst);
|
|
|
bnd = derive_constant_upper_bound (op0);
|
bnd = derive_constant_upper_bound (op0);
|
|
|
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
|
buggy programs that use overflowing signed arithmetics even with
|
buggy 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))
|
{
|
{
|
tree tem = fold_binary (GE_EXPR, boolean_type_node, op0,
|
tree tem = fold_binary (GE_EXPR, boolean_type_node, op0,
|
double_int_to_tree (type, cst));
|
double_int_to_tree (type, cst));
|
if (!tem || integer_nonzerop (tem))
|
if (!tem || integer_nonzerop (tem))
|
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:
|
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);
|
bnd = derive_constant_upper_bound (op0);
|
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);
|
|
|
case BIT_AND_EXPR:
|
case BIT_AND_EXPR:
|
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;
|
return tree_to_double_int (op1);
|
return tree_to_double_int (op1);
|
|
|
case SSA_NAME:
|
case SSA_NAME:
|
stmt = SSA_NAME_DEF_STMT (op0);
|
stmt = SSA_NAME_DEF_STMT (op0);
|
if (gimple_code (stmt) != GIMPLE_ASSIGN
|
if (gimple_code (stmt) != GIMPLE_ASSIGN
|
|| gimple_assign_lhs (stmt) != op0)
|
|| gimple_assign_lhs (stmt) != op0)
|
return max;
|
return max;
|
return derive_constant_upper_bound_assign (stmt);
|
return derive_constant_upper_bound_assign (stmt);
|
|
|
default:
|
default:
|
return max;
|
return max;
|
}
|
}
|
}
|
}
|
|
|
/* Records that every statement in LOOP is executed I_BOUND times.
|
/* Records that every statement in LOOP is executed I_BOUND times.
|
REALISTIC is true if I_BOUND is expected to be close to the real number
|
REALISTIC is true if I_BOUND is expected to be close to the real number
|
of iterations. UPPER is true if we are sure the loop iterates at most
|
of iterations. UPPER is true if we are sure the loop iterates at most
|
I_BOUND times. */
|
I_BOUND times. */
|
|
|
static void
|
static void
|
record_niter_bound (struct loop *loop, double_int i_bound, bool realistic,
|
record_niter_bound (struct loop *loop, double_int i_bound, bool realistic,
|
bool upper)
|
bool upper)
|
{
|
{
|
/* Update the bounds only when there is no previous estimation, or when the current
|
/* Update the bounds only when there is no previous estimation, or when the current
|
estimation is smaller. */
|
estimation is smaller. */
|
if (upper
|
if (upper
|
&& (!loop->any_upper_bound
|
&& (!loop->any_upper_bound
|
|| double_int_ucmp (i_bound, loop->nb_iterations_upper_bound) < 0))
|
|| double_int_ucmp (i_bound, loop->nb_iterations_upper_bound) < 0))
|
{
|
{
|
loop->any_upper_bound = true;
|
loop->any_upper_bound = true;
|
loop->nb_iterations_upper_bound = i_bound;
|
loop->nb_iterations_upper_bound = i_bound;
|
}
|
}
|
if (realistic
|
if (realistic
|
&& (!loop->any_estimate
|
&& (!loop->any_estimate
|
|| double_int_ucmp (i_bound, loop->nb_iterations_estimate) < 0))
|
|| double_int_ucmp (i_bound, loop->nb_iterations_estimate) < 0))
|
{
|
{
|
loop->any_estimate = true;
|
loop->any_estimate = true;
|
loop->nb_iterations_estimate = i_bound;
|
loop->nb_iterations_estimate = i_bound;
|
}
|
}
|
}
|
}
|
|
|
/* Records that AT_STMT is executed at most BOUND + 1 times in LOOP. IS_EXIT
|
/* Records that AT_STMT is executed at most BOUND + 1 times in LOOP. IS_EXIT
|
is true if the loop is exited immediately after STMT, and this exit
|
is true if the loop is exited immediately after STMT, and this exit
|
is taken at last when the STMT is executed BOUND + 1 times.
|
is taken at last when the STMT is executed BOUND + 1 times.
|
REALISTIC is true if BOUND is expected to be close to the real number
|
REALISTIC is true if BOUND is expected to be close to the real number
|
of iterations. UPPER is true if we are sure the loop iterates at most
|
of iterations. UPPER is true if we are sure the loop iterates at most
|
BOUND times. I_BOUND is an unsigned double_int upper estimate on BOUND. */
|
BOUND times. I_BOUND is an unsigned double_int upper estimate on BOUND. */
|
|
|
static void
|
static void
|
record_estimate (struct loop *loop, tree bound, double_int i_bound,
|
record_estimate (struct loop *loop, tree bound, double_int i_bound,
|
gimple at_stmt, bool is_exit, bool realistic, bool upper)
|
gimple at_stmt, bool is_exit, bool realistic, bool upper)
|
{
|
{
|
double_int delta;
|
double_int delta;
|
edge exit;
|
edge exit;
|
|
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
{
|
{
|
fprintf (dump_file, "Statement %s", is_exit ? "(exit)" : "");
|
fprintf (dump_file, "Statement %s", is_exit ? "(exit)" : "");
|
print_gimple_stmt (dump_file, at_stmt, 0, TDF_SLIM);
|
print_gimple_stmt (dump_file, at_stmt, 0, TDF_SLIM);
|
fprintf (dump_file, " is %sexecuted at most ",
|
fprintf (dump_file, " is %sexecuted at most ",
|
upper ? "" : "probably ");
|
upper ? "" : "probably ");
|
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 ");
|
dump_double_int (dump_file, i_bound, true);
|
dump_double_int (dump_file, i_bound, true);
|
fprintf (dump_file, ") + 1 times in loop %d.\n", loop->num);
|
fprintf (dump_file, ") + 1 times in loop %d.\n", loop->num);
|
}
|
}
|
|
|
/* If the I_BOUND is just an estimate of BOUND, it rarely is close to the
|
/* If the I_BOUND is just an estimate of BOUND, it rarely is close to the
|
real number of iterations. */
|
real number of iterations. */
|
if (TREE_CODE (bound) != INTEGER_CST)
|
if (TREE_CODE (bound) != INTEGER_CST)
|
realistic = false;
|
realistic = false;
|
if (!upper && !realistic)
|
if (!upper && !realistic)
|
return;
|
return;
|
|
|
/* If we have a guaranteed upper bound, record it in the appropriate
|
/* If we have a guaranteed upper bound, record it in the appropriate
|
list. */
|
list. */
|
if (upper)
|
if (upper)
|
{
|
{
|
struct nb_iter_bound *elt = GGC_NEW (struct nb_iter_bound);
|
struct nb_iter_bound *elt = GGC_NEW (struct nb_iter_bound);
|
|
|
elt->bound = i_bound;
|
elt->bound = i_bound;
|
elt->stmt = at_stmt;
|
elt->stmt = at_stmt;
|
elt->is_exit = is_exit;
|
elt->is_exit = is_exit;
|
elt->next = loop->bounds;
|
elt->next = loop->bounds;
|
loop->bounds = elt;
|
loop->bounds = elt;
|
}
|
}
|
|
|
/* Update the number of iteration estimates according to the bound.
|
/* Update the number of iteration estimates according to the bound.
|
If at_stmt is an exit, then every statement in the loop is
|
If at_stmt is an exit, then every statement in the loop is
|
executed at most BOUND + 1 times. If it is not an exit, then
|
executed at most BOUND + 1 times. If it is not an exit, then
|
some of the statements before it could be executed BOUND + 2
|
some of the statements before it could be executed BOUND + 2
|
times, if an exit of LOOP is before stmt. */
|
times, if an exit of LOOP is before stmt. */
|
exit = single_exit (loop);
|
exit = single_exit (loop);
|
if (is_exit
|
if (is_exit
|
|| (exit != NULL
|
|| (exit != NULL
|
&& dominated_by_p (CDI_DOMINATORS,
|
&& dominated_by_p (CDI_DOMINATORS,
|
exit->src, gimple_bb (at_stmt))))
|
exit->src, gimple_bb (at_stmt))))
|
delta = double_int_one;
|
delta = double_int_one;
|
else
|
else
|
delta = double_int_two;
|
delta = double_int_two;
|
i_bound = double_int_add (i_bound, delta);
|
i_bound = double_int_add (i_bound, delta);
|
|
|
/* If an overflow occurred, ignore the result. */
|
/* If an overflow occurred, ignore the result. */
|
if (double_int_ucmp (i_bound, delta) < 0)
|
if (double_int_ucmp (i_bound, delta) < 0)
|
return;
|
return;
|
|
|
record_niter_bound (loop, i_bound, realistic, upper);
|
record_niter_bound (loop, i_bound, realistic, upper);
|
}
|
}
|
|
|
/* Record the estimate on number of iterations of LOOP based on the fact that
|
/* Record the estimate on number of iterations of LOOP based on the fact that
|
the induction variable BASE + STEP * i evaluated in STMT does not wrap and
|
the induction variable BASE + STEP * i evaluated in STMT does not wrap and
|
its values belong to the range <LOW, HIGH>. REALISTIC is true if the
|
its values belong to the range <LOW, HIGH>. REALISTIC is true if the
|
estimated number of iterations is expected to be close to the real one.
|
estimated number of iterations is expected to be close to the real one.
|
UPPER is true if we are sure the induction variable does not wrap. */
|
UPPER is true if we are sure the induction variable does not wrap. */
|
|
|
static void
|
static void
|
record_nonwrapping_iv (struct loop *loop, tree base, tree step, gimple stmt,
|
record_nonwrapping_iv (struct loop *loop, tree base, tree step, gimple stmt,
|
tree low, tree high, bool realistic, bool upper)
|
tree low, tree high, bool realistic, bool upper)
|
{
|
{
|
tree niter_bound, extreme, delta;
|
tree niter_bound, extreme, delta;
|
tree type = TREE_TYPE (base), unsigned_type;
|
tree type = TREE_TYPE (base), unsigned_type;
|
double_int max;
|
double_int max;
|
|
|
if (TREE_CODE (step) != INTEGER_CST || integer_zerop (step))
|
if (TREE_CODE (step) != INTEGER_CST || integer_zerop (step))
|
return;
|
return;
|
|
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
{
|
{
|
fprintf (dump_file, "Induction variable (");
|
fprintf (dump_file, "Induction variable (");
|
print_generic_expr (dump_file, TREE_TYPE (base), TDF_SLIM);
|
print_generic_expr (dump_file, TREE_TYPE (base), TDF_SLIM);
|
fprintf (dump_file, ") ");
|
fprintf (dump_file, ") ");
|
print_generic_expr (dump_file, base, TDF_SLIM);
|
print_generic_expr (dump_file, base, TDF_SLIM);
|
fprintf (dump_file, " + ");
|
fprintf (dump_file, " + ");
|
print_generic_expr (dump_file, step, TDF_SLIM);
|
print_generic_expr (dump_file, step, TDF_SLIM);
|
fprintf (dump_file, " * iteration does not wrap in statement ");
|
fprintf (dump_file, " * iteration does not wrap in statement ");
|
print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
|
print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
|
fprintf (dump_file, " in loop %d.\n", loop->num);
|
fprintf (dump_file, " in loop %d.\n", loop->num);
|
}
|
}
|
|
|
unsigned_type = unsigned_type_for (type);
|
unsigned_type = unsigned_type_for (type);
|
base = fold_convert (unsigned_type, base);
|
base = fold_convert (unsigned_type, base);
|
step = fold_convert (unsigned_type, step);
|
step = fold_convert (unsigned_type, step);
|
|
|
if (tree_int_cst_sign_bit (step))
|
if (tree_int_cst_sign_bit (step))
|
{
|
{
|
extreme = fold_convert (unsigned_type, low);
|
extreme = fold_convert (unsigned_type, low);
|
if (TREE_CODE (base) != INTEGER_CST)
|
if (TREE_CODE (base) != INTEGER_CST)
|
base = fold_convert (unsigned_type, high);
|
base = fold_convert (unsigned_type, high);
|
delta = fold_build2 (MINUS_EXPR, unsigned_type, base, extreme);
|
delta = fold_build2 (MINUS_EXPR, unsigned_type, base, extreme);
|
step = fold_build1 (NEGATE_EXPR, unsigned_type, step);
|
step = fold_build1 (NEGATE_EXPR, unsigned_type, step);
|
}
|
}
|
else
|
else
|
{
|
{
|
extreme = fold_convert (unsigned_type, high);
|
extreme = fold_convert (unsigned_type, high);
|
if (TREE_CODE (base) != INTEGER_CST)
|
if (TREE_CODE (base) != INTEGER_CST)
|
base = fold_convert (unsigned_type, low);
|
base = fold_convert (unsigned_type, low);
|
delta = fold_build2 (MINUS_EXPR, unsigned_type, extreme, base);
|
delta = fold_build2 (MINUS_EXPR, unsigned_type, extreme, base);
|
}
|
}
|
|
|
/* STMT is executed at most NITER_BOUND + 1 times, since otherwise the value
|
/* STMT is executed at most NITER_BOUND + 1 times, since otherwise the value
|
would get out of the range. */
|
would get out of the range. */
|
niter_bound = fold_build2 (FLOOR_DIV_EXPR, unsigned_type, delta, step);
|
niter_bound = fold_build2 (FLOOR_DIV_EXPR, unsigned_type, delta, step);
|
max = derive_constant_upper_bound (niter_bound);
|
max = derive_constant_upper_bound (niter_bound);
|
record_estimate (loop, niter_bound, max, stmt, false, realistic, upper);
|
record_estimate (loop, niter_bound, max, stmt, false, realistic, upper);
|
}
|
}
|
|
|
/* Returns true if REF is a reference to an array at the end of a dynamically
|
/* Returns true if REF is a reference to an array at the end of a dynamically
|
allocated structure. If this is the case, the array may be allocated larger
|
allocated structure. If this is the case, the array may be allocated larger
|
than its upper bound implies. */
|
than its upper bound implies. */
|
|
|
bool
|
bool
|
array_at_struct_end_p (tree ref)
|
array_at_struct_end_p (tree ref)
|
{
|
{
|
tree base = get_base_address (ref);
|
tree base = get_base_address (ref);
|
tree parent, field;
|
tree parent, field;
|
|
|
/* Unless the reference is through a pointer, the size of the array matches
|
/* Unless the reference is through a pointer, the size of the array matches
|
its declaration. */
|
its declaration. */
|
if (!base || !INDIRECT_REF_P (base))
|
if (!base || !INDIRECT_REF_P (base))
|
return false;
|
return false;
|
|
|
for (;handled_component_p (ref); ref = parent)
|
for (;handled_component_p (ref); ref = parent)
|
{
|
{
|
parent = TREE_OPERAND (ref, 0);
|
parent = TREE_OPERAND (ref, 0);
|
|
|
if (TREE_CODE (ref) == COMPONENT_REF)
|
if (TREE_CODE (ref) == COMPONENT_REF)
|
{
|
{
|
/* All fields of a union are at its end. */
|
/* All fields of a union are at its end. */
|
if (TREE_CODE (TREE_TYPE (parent)) == UNION_TYPE)
|
if (TREE_CODE (TREE_TYPE (parent)) == UNION_TYPE)
|
continue;
|
continue;
|
|
|
/* Unless the field is at the end of the struct, we are done. */
|
/* Unless the field is at the end of the struct, we are done. */
|
field = TREE_OPERAND (ref, 1);
|
field = TREE_OPERAND (ref, 1);
|
if (TREE_CHAIN (field))
|
if (TREE_CHAIN (field))
|
return false;
|
return false;
|
}
|
}
|
|
|
/* The other options are ARRAY_REF, ARRAY_RANGE_REF, VIEW_CONVERT_EXPR.
|
/* The other options are ARRAY_REF, ARRAY_RANGE_REF, VIEW_CONVERT_EXPR.
|
In all these cases, we might be accessing the last element, and
|
In all these cases, we might be accessing the last element, and
|
although in practice this will probably never happen, it is legal for
|
although in practice this will probably never happen, it is legal for
|
the indices of this last element to exceed the bounds of the array.
|
the indices of this last element to exceed the bounds of the array.
|
Therefore, continue checking. */
|
Therefore, continue checking. */
|
}
|
}
|
|
|
gcc_assert (INDIRECT_REF_P (ref));
|
gcc_assert (INDIRECT_REF_P (ref));
|
return true;
|
return true;
|
}
|
}
|
|
|
/* Determine information about number of iterations a LOOP from the index
|
/* Determine information about number of iterations a LOOP from the index
|
IDX of a data reference accessed in STMT. RELIABLE is true if STMT is
|
IDX of a data reference accessed in STMT. RELIABLE is true if STMT is
|
guaranteed to be executed in every iteration of LOOP. Callback for
|
guaranteed to be executed in every iteration of LOOP. Callback for
|
for_each_index. */
|
for_each_index. */
|
|
|
struct ilb_data
|
struct ilb_data
|
{
|
{
|
struct loop *loop;
|
struct loop *loop;
|
gimple stmt;
|
gimple stmt;
|
bool reliable;
|
bool reliable;
|
};
|
};
|
|
|
static bool
|
static bool
|
idx_infer_loop_bounds (tree base, tree *idx, void *dta)
|
idx_infer_loop_bounds (tree base, tree *idx, void *dta)
|
{
|
{
|
struct ilb_data *data = (struct ilb_data *) dta;
|
struct ilb_data *data = (struct ilb_data *) dta;
|
tree ev, init, step;
|
tree ev, init, step;
|
tree low, high, type, next;
|
tree low, high, type, next;
|
bool sign, upper = data->reliable, at_end = false;
|
bool sign, upper = data->reliable, at_end = false;
|
struct loop *loop = data->loop;
|
struct loop *loop = data->loop;
|
|
|
if (TREE_CODE (base) != ARRAY_REF)
|
if (TREE_CODE (base) != ARRAY_REF)
|
return true;
|
return true;
|
|
|
/* For arrays at the end of the structure, we are not guaranteed that they
|
/* For arrays at the end of the structure, we are not guaranteed that they
|
do not really extend over their declared size. However, for arrays of
|
do not really extend over their declared size. However, for arrays of
|
size greater than one, this is unlikely to be intended. */
|
size greater than one, this is unlikely to be intended. */
|
if (array_at_struct_end_p (base))
|
if (array_at_struct_end_p (base))
|
{
|
{
|
at_end = true;
|
at_end = true;
|
upper = false;
|
upper = false;
|
}
|
}
|
|
|
ev = instantiate_parameters (loop, analyze_scalar_evolution (loop, *idx));
|
ev = instantiate_parameters (loop, analyze_scalar_evolution (loop, *idx));
|
init = initial_condition (ev);
|
init = initial_condition (ev);
|
step = evolution_part_in_loop_num (ev, loop->num);
|
step = evolution_part_in_loop_num (ev, loop->num);
|
|
|
if (!init
|
if (!init
|
|| !step
|
|| !step
|
|| TREE_CODE (step) != INTEGER_CST
|
|| TREE_CODE (step) != INTEGER_CST
|
|| integer_zerop (step)
|
|| integer_zerop (step)
|
|| tree_contains_chrecs (init, NULL)
|
|| tree_contains_chrecs (init, NULL)
|
|| chrec_contains_symbols_defined_in_loop (init, loop->num))
|
|| chrec_contains_symbols_defined_in_loop (init, loop->num))
|
return true;
|
return true;
|
|
|
low = array_ref_low_bound (base);
|
low = array_ref_low_bound (base);
|
high = array_ref_up_bound (base);
|
high = array_ref_up_bound (base);
|
|
|
/* The case of nonconstant bounds could be handled, but it would be
|
/* The case of nonconstant bounds could be handled, but it would be
|
complicated. */
|
complicated. */
|
if (TREE_CODE (low) != INTEGER_CST
|
if (TREE_CODE (low) != INTEGER_CST
|
|| !high
|
|| !high
|
|| TREE_CODE (high) != INTEGER_CST)
|
|| TREE_CODE (high) != INTEGER_CST)
|
return true;
|
return true;
|
sign = tree_int_cst_sign_bit (step);
|
sign = tree_int_cst_sign_bit (step);
|
type = TREE_TYPE (step);
|
type = TREE_TYPE (step);
|
|
|
/* The array of length 1 at the end of a structure most likely extends
|
/* The array of length 1 at the end of a structure most likely extends
|
beyond its bounds. */
|
beyond its bounds. */
|
if (at_end
|
if (at_end
|
&& operand_equal_p (low, high, 0))
|
&& operand_equal_p (low, high, 0))
|
return true;
|
return true;
|
|
|
/* In case the relevant bound of the array does not fit in type, or
|
/* In case the relevant bound of the array does not fit in type, or
|
it does, but bound + step (in type) still belongs into the range of the
|
it does, but bound + step (in type) still belongs into the range of the
|
array, the index may wrap and still stay within the range of the array
|
array, the index may wrap and still stay within the range of the array
|
(consider e.g. if the array is indexed by the full range of
|
(consider e.g. if the array is indexed by the full range of
|
unsigned char).
|
unsigned char).
|
|
|
To make things simpler, we require both bounds to fit into type, although
|
To make things simpler, we require both bounds to fit into type, although
|
there are cases where this would not be strictly necessary. */
|
there are cases where this would not be strictly necessary. */
|
if (!int_fits_type_p (high, type)
|
if (!int_fits_type_p (high, type)
|
|| !int_fits_type_p (low, type))
|
|| !int_fits_type_p (low, type))
|
return true;
|
return true;
|
low = fold_convert (type, low);
|
low = fold_convert (type, low);
|
high = fold_convert (type, high);
|
high = fold_convert (type, high);
|
|
|
if (sign)
|
if (sign)
|
next = fold_binary (PLUS_EXPR, type, low, step);
|
next = fold_binary (PLUS_EXPR, type, low, step);
|
else
|
else
|
next = fold_binary (PLUS_EXPR, type, high, step);
|
next = fold_binary (PLUS_EXPR, type, high, step);
|
|
|
if (tree_int_cst_compare (low, next) <= 0
|
if (tree_int_cst_compare (low, next) <= 0
|
&& tree_int_cst_compare (next, high) <= 0)
|
&& tree_int_cst_compare (next, high) <= 0)
|
return true;
|
return true;
|
|
|
record_nonwrapping_iv (loop, init, step, data->stmt, low, high, true, upper);
|
record_nonwrapping_iv (loop, init, step, data->stmt, low, high, true, upper);
|
return true;
|
return true;
|
}
|
}
|
|
|
/* Determine information about number of iterations a LOOP from the bounds
|
/* Determine information about number of iterations a LOOP from the bounds
|
of arrays in the data reference REF accessed in STMT. RELIABLE is true if
|
of arrays in the data reference REF accessed in STMT. RELIABLE is true if
|
STMT is guaranteed to be executed in every iteration of LOOP.*/
|
STMT is guaranteed to be executed in every iteration of LOOP.*/
|
|
|
static void
|
static void
|
infer_loop_bounds_from_ref (struct loop *loop, gimple stmt, tree ref,
|
infer_loop_bounds_from_ref (struct loop *loop, gimple stmt, tree ref,
|
bool reliable)
|
bool reliable)
|
{
|
{
|
struct ilb_data data;
|
struct ilb_data data;
|
|
|
data.loop = loop;
|
data.loop = loop;
|
data.stmt = stmt;
|
data.stmt = stmt;
|
data.reliable = reliable;
|
data.reliable = reliable;
|
for_each_index (&ref, idx_infer_loop_bounds, &data);
|
for_each_index (&ref, idx_infer_loop_bounds, &data);
|
}
|
}
|
|
|
/* Determine information about number of iterations of a LOOP from the way
|
/* Determine information about number of iterations of a LOOP from the way
|
arrays are used in STMT. RELIABLE is true if STMT is guaranteed to be
|
arrays are used in STMT. RELIABLE is true if STMT is guaranteed to be
|
executed in every iteration of LOOP. */
|
executed in every iteration of LOOP. */
|
|
|
static void
|
static void
|
infer_loop_bounds_from_array (struct loop *loop, gimple stmt, bool reliable)
|
infer_loop_bounds_from_array (struct loop *loop, gimple stmt, bool reliable)
|
{
|
{
|
if (is_gimple_assign (stmt))
|
if (is_gimple_assign (stmt))
|
{
|
{
|
tree op0 = gimple_assign_lhs (stmt);
|
tree op0 = gimple_assign_lhs (stmt);
|
tree op1 = gimple_assign_rhs1 (stmt);
|
tree op1 = gimple_assign_rhs1 (stmt);
|
|
|
/* For each memory access, analyze its access function
|
/* For each memory access, analyze its access function
|
and record a bound on the loop iteration domain. */
|
and record a bound on the loop iteration domain. */
|
if (REFERENCE_CLASS_P (op0))
|
if (REFERENCE_CLASS_P (op0))
|
infer_loop_bounds_from_ref (loop, stmt, op0, reliable);
|
infer_loop_bounds_from_ref (loop, stmt, op0, reliable);
|
|
|
if (REFERENCE_CLASS_P (op1))
|
if (REFERENCE_CLASS_P (op1))
|
infer_loop_bounds_from_ref (loop, stmt, op1, reliable);
|
infer_loop_bounds_from_ref (loop, stmt, op1, reliable);
|
}
|
}
|
else if (is_gimple_call (stmt))
|
else if (is_gimple_call (stmt))
|
{
|
{
|
tree arg, lhs;
|
tree arg, lhs;
|
unsigned i, n = gimple_call_num_args (stmt);
|
unsigned i, n = gimple_call_num_args (stmt);
|
|
|
lhs = gimple_call_lhs (stmt);
|
lhs = gimple_call_lhs (stmt);
|
if (lhs && REFERENCE_CLASS_P (lhs))
|
if (lhs && REFERENCE_CLASS_P (lhs))
|
infer_loop_bounds_from_ref (loop, stmt, lhs, reliable);
|
infer_loop_bounds_from_ref (loop, stmt, lhs, reliable);
|
|
|
for (i = 0; i < n; i++)
|
for (i = 0; i < n; i++)
|
{
|
{
|
arg = gimple_call_arg (stmt, i);
|
arg = gimple_call_arg (stmt, i);
|
if (REFERENCE_CLASS_P (arg))
|
if (REFERENCE_CLASS_P (arg))
|
infer_loop_bounds_from_ref (loop, stmt, arg, reliable);
|
infer_loop_bounds_from_ref (loop, stmt, arg, reliable);
|
}
|
}
|
}
|
}
|
}
|
}
|
|
|
/* Determine information about number of iterations of a LOOP from the fact
|
/* Determine information about number of iterations of a LOOP from the fact
|
that signed arithmetics in STMT does not overflow. */
|
that signed arithmetics in STMT does not overflow. */
|
|
|
static void
|
static void
|
infer_loop_bounds_from_signedness (struct loop *loop, gimple stmt)
|
infer_loop_bounds_from_signedness (struct loop *loop, gimple stmt)
|
{
|
{
|
tree def, base, step, scev, type, low, high;
|
tree def, base, step, scev, type, low, high;
|
|
|
if (gimple_code (stmt) != GIMPLE_ASSIGN)
|
if (gimple_code (stmt) != GIMPLE_ASSIGN)
|
return;
|
return;
|
|
|
def = gimple_assign_lhs (stmt);
|
def = gimple_assign_lhs (stmt);
|
|
|
if (TREE_CODE (def) != SSA_NAME)
|
if (TREE_CODE (def) != SSA_NAME)
|
return;
|
return;
|
|
|
type = TREE_TYPE (def);
|
type = TREE_TYPE (def);
|
if (!INTEGRAL_TYPE_P (type)
|
if (!INTEGRAL_TYPE_P (type)
|
|| !TYPE_OVERFLOW_UNDEFINED (type))
|
|| !TYPE_OVERFLOW_UNDEFINED (type))
|
return;
|
return;
|
|
|
scev = instantiate_parameters (loop, analyze_scalar_evolution (loop, def));
|
scev = instantiate_parameters (loop, analyze_scalar_evolution (loop, def));
|
if (chrec_contains_undetermined (scev))
|
if (chrec_contains_undetermined (scev))
|
return;
|
return;
|
|
|
base = initial_condition_in_loop_num (scev, loop->num);
|
base = 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 (!base || !step
|
if (!base || !step
|
|| TREE_CODE (step) != INTEGER_CST
|
|| TREE_CODE (step) != INTEGER_CST
|
|| tree_contains_chrecs (base, NULL)
|
|| tree_contains_chrecs (base, NULL)
|
|| chrec_contains_symbols_defined_in_loop (base, loop->num))
|
|| chrec_contains_symbols_defined_in_loop (base, loop->num))
|
return;
|
return;
|
|
|
low = lower_bound_in_type (type, type);
|
low = lower_bound_in_type (type, type);
|
high = upper_bound_in_type (type, type);
|
high = upper_bound_in_type (type, type);
|
|
|
record_nonwrapping_iv (loop, base, step, stmt, low, high, false, true);
|
record_nonwrapping_iv (loop, base, step, stmt, low, high, false, true);
|
}
|
}
|
|
|
/* 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 *bbs;
|
basic_block *bbs;
|
gimple_stmt_iterator bsi;
|
gimple_stmt_iterator bsi;
|
basic_block bb;
|
basic_block bb;
|
bool reliable;
|
bool reliable;
|
|
|
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. However, we can use it as a guess. */
|
# of iterations of the loop. However, we can use it as a guess. */
|
reliable = dominated_by_p (CDI_DOMINATORS, loop->latch, bb);
|
reliable = dominated_by_p (CDI_DOMINATORS, loop->latch, bb);
|
|
|
for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
|
for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
|
{
|
{
|
gimple stmt = gsi_stmt (bsi);
|
gimple stmt = gsi_stmt (bsi);
|
|
|
infer_loop_bounds_from_array (loop, stmt, reliable);
|
infer_loop_bounds_from_array (loop, stmt, reliable);
|
|
|
if (reliable)
|
if (reliable)
|
infer_loop_bounds_from_signedness (loop, stmt);
|
infer_loop_bounds_from_signedness (loop, stmt);
|
}
|
}
|
|
|
}
|
}
|
|
|
free (bbs);
|
free (bbs);
|
}
|
}
|
|
|
/* Converts VAL to double_int. */
|
/* Converts VAL to double_int. */
|
|
|
static double_int
|
static double_int
|
gcov_type_to_double_int (gcov_type val)
|
gcov_type_to_double_int (gcov_type val)
|
{
|
{
|
double_int ret;
|
double_int ret;
|
|
|
ret.low = (unsigned HOST_WIDE_INT) val;
|
ret.low = (unsigned HOST_WIDE_INT) val;
|
/* If HOST_BITS_PER_WIDE_INT == HOST_BITS_PER_WIDEST_INT, avoid shifting by
|
/* If HOST_BITS_PER_WIDE_INT == HOST_BITS_PER_WIDEST_INT, avoid shifting by
|
the size of type. */
|
the size of type. */
|
val >>= HOST_BITS_PER_WIDE_INT - 1;
|
val >>= HOST_BITS_PER_WIDE_INT - 1;
|
val >>= 1;
|
val >>= 1;
|
ret.high = (unsigned HOST_WIDE_INT) val;
|
ret.high = (unsigned HOST_WIDE_INT) val;
|
|
|
return ret;
|
return ret;
|
}
|
}
|
|
|
/* Records estimates on numbers of iterations of LOOP. */
|
/* Records estimates on numbers of iterations of LOOP. */
|
|
|
void
|
void
|
estimate_numbers_of_iterations_loop (struct loop *loop)
|
estimate_numbers_of_iterations_loop (struct loop *loop)
|
{
|
{
|
VEC (edge, heap) *exits;
|
VEC (edge, heap) *exits;
|
tree niter, type;
|
tree niter, type;
|
unsigned i;
|
unsigned i;
|
struct tree_niter_desc niter_desc;
|
struct tree_niter_desc niter_desc;
|
edge ex;
|
edge ex;
|
double_int bound;
|
double_int bound;
|
|
|
/* Give up if we already have tried to compute an estimation. */
|
/* Give up if we already have tried to compute an estimation. */
|
if (loop->estimate_state != EST_NOT_COMPUTED)
|
if (loop->estimate_state != EST_NOT_COMPUTED)
|
return;
|
return;
|
loop->estimate_state = EST_AVAILABLE;
|
loop->estimate_state = EST_AVAILABLE;
|
loop->any_upper_bound = false;
|
loop->any_upper_bound = false;
|
loop->any_estimate = false;
|
loop->any_estimate = false;
|
|
|
exits = get_loop_exit_edges (loop);
|
exits = get_loop_exit_edges (loop);
|
for (i = 0; VEC_iterate (edge, exits, i, ex); i++)
|
for (i = 0; VEC_iterate (edge, exits, i, ex); i++)
|
{
|
{
|
if (!number_of_iterations_exit (loop, ex, &niter_desc, false))
|
if (!number_of_iterations_exit (loop, ex, &niter_desc, false))
|
continue;
|
continue;
|
|
|
niter = niter_desc.niter;
|
niter = niter_desc.niter;
|
type = TREE_TYPE (niter);
|
type = TREE_TYPE (niter);
|
if (TREE_CODE (niter_desc.may_be_zero) != INTEGER_CST)
|
if (TREE_CODE (niter_desc.may_be_zero) != INTEGER_CST)
|
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, niter_desc.max,
|
record_estimate (loop, niter, niter_desc.max,
|
last_stmt (ex->src),
|
last_stmt (ex->src),
|
true, true, true);
|
true, true, true);
|
}
|
}
|
VEC_free (edge, heap, exits);
|
VEC_free (edge, heap, exits);
|
|
|
infer_loop_bounds_from_undefined (loop);
|
infer_loop_bounds_from_undefined (loop);
|
|
|
/* If we have a measured profile, use it to estimate the number of
|
/* If we have a measured profile, use it to estimate the number of
|
iterations. */
|
iterations. */
|
if (loop->header->count != 0)
|
if (loop->header->count != 0)
|
{
|
{
|
gcov_type nit = expected_loop_iterations_unbounded (loop) + 1;
|
gcov_type nit = expected_loop_iterations_unbounded (loop) + 1;
|
bound = gcov_type_to_double_int (nit);
|
bound = gcov_type_to_double_int (nit);
|
record_niter_bound (loop, bound, true, false);
|
record_niter_bound (loop, bound, true, false);
|
}
|
}
|
|
|
/* If an upper bound is smaller than the realistic estimate of the
|
/* If an upper bound is smaller than the realistic estimate of the
|
number of iterations, use the upper bound instead. */
|
number of iterations, use the upper bound instead. */
|
if (loop->any_upper_bound
|
if (loop->any_upper_bound
|
&& loop->any_estimate
|
&& loop->any_estimate
|
&& double_int_ucmp (loop->nb_iterations_upper_bound,
|
&& double_int_ucmp (loop->nb_iterations_upper_bound,
|
loop->nb_iterations_estimate) < 0)
|
loop->nb_iterations_estimate) < 0)
|
loop->nb_iterations_estimate = loop->nb_iterations_upper_bound;
|
loop->nb_iterations_estimate = loop->nb_iterations_upper_bound;
|
}
|
}
|
|
|
/* Records estimates on numbers of iterations of loops. */
|
/* Records estimates on numbers of iterations of loops. */
|
|
|
void
|
void
|
estimate_numbers_of_iterations (void)
|
estimate_numbers_of_iterations (void)
|
{
|
{
|
loop_iterator li;
|
loop_iterator li;
|
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_EACH_LOOP (li, loop, 0)
|
FOR_EACH_LOOP (li, loop, 0)
|
{
|
{
|
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. */
|
|
|
bool
|
bool
|
stmt_dominates_stmt_p (gimple s1, gimple s2)
|
stmt_dominates_stmt_p (gimple s1, gimple s2)
|
{
|
{
|
basic_block bb1 = gimple_bb (s1), bb2 = gimple_bb (s2);
|
basic_block bb1 = gimple_bb (s1), bb2 = gimple_bb (s2);
|
|
|
if (!bb1
|
if (!bb1
|
|| s1 == s2)
|
|| s1 == s2)
|
return true;
|
return true;
|
|
|
if (bb1 == bb2)
|
if (bb1 == bb2)
|
{
|
{
|
gimple_stmt_iterator bsi;
|
gimple_stmt_iterator bsi;
|
|
|
if (gimple_code (s2) == GIMPLE_PHI)
|
if (gimple_code (s2) == GIMPLE_PHI)
|
return false;
|
return false;
|
|
|
if (gimple_code (s1) == GIMPLE_PHI)
|
if (gimple_code (s1) == GIMPLE_PHI)
|
return true;
|
return true;
|
|
|
for (bsi = gsi_start_bb (bb1); gsi_stmt (bsi) != s2; gsi_next (&bsi))
|
for (bsi = gsi_start_bb (bb1); gsi_stmt (bsi) != s2; gsi_next (&bsi))
|
if (gsi_stmt (bsi) == s1)
|
if (gsi_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 bound on
|
STMT in the loop is at most NITER, according to the bound on
|
the number of executions of the statement NITER_BOUND->stmt recorded in
|
the number of executions of the statement NITER_BOUND->stmt recorded in
|
NITER_BOUND. If STMT is NULL, we must prove this bound for all
|
NITER_BOUND. If STMT is NULL, we must prove this bound for all
|
statements in the loop. */
|
statements in the loop. */
|
|
|
static bool
|
static bool
|
n_of_executions_at_most (gimple stmt,
|
n_of_executions_at_most (gimple stmt,
|
struct nb_iter_bound *niter_bound,
|
struct nb_iter_bound *niter_bound,
|
tree niter)
|
tree niter)
|
{
|
{
|
double_int bound = niter_bound->bound;
|
double_int bound = niter_bound->bound;
|
tree nit_type = TREE_TYPE (niter), e;
|
tree nit_type = TREE_TYPE (niter), e;
|
enum tree_code cmp;
|
enum tree_code cmp;
|
|
|
gcc_assert (TYPE_UNSIGNED (nit_type));
|
gcc_assert (TYPE_UNSIGNED (nit_type));
|
|
|
/* If the bound does not even fit into NIT_TYPE, it cannot tell us that
|
/* If the bound does not even fit into NIT_TYPE, it cannot tell us that
|
the number of iterations is small. */
|
the number of iterations is small. */
|
if (!double_int_fits_to_tree_p (nit_type, bound))
|
if (!double_int_fits_to_tree_p (nit_type, bound))
|
return false;
|
return false;
|
|
|
/* We know that NITER_BOUND->stmt is executed at most NITER_BOUND->bound + 1
|
/* We know that NITER_BOUND->stmt is executed at most NITER_BOUND->bound + 1
|
times. This means that:
|
times. This means that:
|
|
|
-- if NITER_BOUND->is_exit is true, then everything before
|
-- if NITER_BOUND->is_exit is true, then everything before
|
NITER_BOUND->stmt is executed at most NITER_BOUND->bound + 1
|
NITER_BOUND->stmt is executed at most NITER_BOUND->bound + 1
|
times, and everything after it at most NITER_BOUND->bound times.
|
times, and everything after it at most NITER_BOUND->bound times.
|
|
|
-- If NITER_BOUND->is_exit is false, then if we can prove that when STMT
|
-- If NITER_BOUND->is_exit is false, then if we can prove that when STMT
|
is executed, then NITER_BOUND->stmt is executed as well in the same
|
is executed, then NITER_BOUND->stmt is executed as well in the same
|
iteration (we conclude that if both statements belong to the same
|
iteration (we conclude that if both statements belong to the same
|
basic block, or if STMT is after NITER_BOUND->stmt), then STMT
|
basic block, or if STMT is after NITER_BOUND->stmt), then STMT
|
is executed at most NITER_BOUND->bound + 1 times. Otherwise STMT is
|
is executed at most NITER_BOUND->bound + 1 times. Otherwise STMT is
|
executed at most NITER_BOUND->bound + 2 times. */
|
executed at most NITER_BOUND->bound + 2 times. */
|
|
|
if (niter_bound->is_exit)
|
if (niter_bound->is_exit)
|
{
|
{
|
if (stmt
|
if (stmt
|
&& stmt != niter_bound->stmt
|
&& stmt != niter_bound->stmt
|
&& stmt_dominates_stmt_p (niter_bound->stmt, stmt))
|
&& stmt_dominates_stmt_p (niter_bound->stmt, stmt))
|
cmp = GE_EXPR;
|
cmp = GE_EXPR;
|
else
|
else
|
cmp = GT_EXPR;
|
cmp = GT_EXPR;
|
}
|
}
|
else
|
else
|
{
|
{
|
if (!stmt
|
if (!stmt
|
|| (gimple_bb (stmt) != gimple_bb (niter_bound->stmt)
|
|| (gimple_bb (stmt) != gimple_bb (niter_bound->stmt)
|
&& !stmt_dominates_stmt_p (niter_bound->stmt, stmt)))
|
&& !stmt_dominates_stmt_p (niter_bound->stmt, stmt)))
|
{
|
{
|
bound = double_int_add (bound, double_int_one);
|
bound = double_int_add (bound, double_int_one);
|
if (double_int_zero_p (bound)
|
if (double_int_zero_p (bound)
|
|| !double_int_fits_to_tree_p (nit_type, bound))
|
|| !double_int_fits_to_tree_p (nit_type, bound))
|
return false;
|
return false;
|
}
|
}
|
cmp = GT_EXPR;
|
cmp = GT_EXPR;
|
}
|
}
|
|
|
e = fold_binary (cmp, boolean_type_node,
|
e = fold_binary (cmp, boolean_type_node,
|
niter, double_int_to_tree (nit_type, bound));
|
niter, double_int_to_tree (nit_type, bound));
|
return e && integer_nonzerop (e);
|
return e && integer_nonzerop (e);
|
}
|
}
|
|
|
/* 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,
|
gimple at_stmt, struct loop *loop,
|
gimple 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))
|
return true;
|
return true;
|
|
|
if (integer_zerop (step))
|
if (integer_zerop (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 (TREE_TYPE (base)))
|
if (use_overflow_semantics && nowrap_type_p (TREE_TYPE (base)))
|
return false;
|
return false;
|
|
|
/* To be able to use estimates on number of iterations of the loop,
|
/* To be able to use estimates on number of iterations of the loop,
|
we must have an upper bound on the absolute value of the step. */
|
we must have an upper bound on the absolute value of the step. */
|
if (TREE_CODE (step) != INTEGER_CST)
|
if (TREE_CODE (step) != INTEGER_CST)
|
return true;
|
return true;
|
|
|
/* 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->estimate_state = EST_NOT_COMPUTED;
|
loop->estimate_state = EST_NOT_COMPUTED;
|
for (bound = loop->bounds; bound; bound = next)
|
for (bound = loop->bounds; bound; bound = next)
|
{
|
{
|
next = bound->next;
|
next = bound->next;
|
ggc_free (bound);
|
ggc_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 (void)
|
free_numbers_of_iterations_estimates (void)
|
{
|
{
|
loop_iterator li;
|
loop_iterator li;
|
struct loop *loop;
|
struct loop *loop;
|
|
|
FOR_EACH_LOOP (li, loop, 0)
|
FOR_EACH_LOOP (li, loop, 0)
|
{
|
{
|
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);
|
}
|
}
|
|
|
