Hi Richi,
On Thu, Jul 28, 2011 at 03:58, Richard Guenther <rguent...@suse.de> wrote:
> So maybe we can instead try to avoid using unsigned arithmetic
> for symbolic niters if the source does not have it unsigned?
Ok, so what about the attached patch that makes niter use the original
type as much as possible? I.e. for the trivial cases that don't use division.
Regstrap in progress on amd64-linux.
Sebastian
From 992e0e8c7b15610bf7b9092f0723fb77e323de3a Mon Sep 17 00:00:00 2001
From: Sebastian Pop <seb...@gmail.com>
Date: Fri, 29 Jul 2011 11:08:47 -0500
Subject: [PATCH 1/2] Use build_zero_cst or build_one_cst.
---
gcc/tree-ssa-loop-niter.c | 32 ++++++++++++++++----------------
1 files changed, 16 insertions(+), 16 deletions(-)
diff --git a/gcc/tree-ssa-loop-niter.c b/gcc/tree-ssa-loop-niter.c
index 4acfc67..2ee3f6e 100644
--- a/gcc/tree-ssa-loop-niter.c
+++ b/gcc/tree-ssa-loop-niter.c
@@ -101,7 +101,7 @@ split_to_var_and_offset (tree expr, tree *var, mpz_t offset)
break;
case INTEGER_CST:
- *var = build_int_cst_type (type, 0);
+ *var = build_zero_cst (type);
off = tree_to_double_int (expr);
mpz_set_double_int (offset, off, TYPE_UNSIGNED (type));
break;
@@ -522,7 +522,7 @@ inverse (tree x, tree mask)
}
else
{
- rslt = build_int_cst (type, 1);
+ rslt = build_one_cst (type);
for (; ctr; ctr--)
{
rslt = int_const_binop (MULT_EXPR, rslt, x);
@@ -670,7 +670,7 @@ number_of_iterations_ne (tree type, affine_iv *iv, tree final,
- tree_low_cst (bits, 1)));
d = fold_binary_to_constant (LSHIFT_EXPR, niter_type,
- build_int_cst (niter_type, 1), bits);
+ build_one_cst (niter_type), bits);
s = fold_binary_to_constant (RSHIFT_EXPR, niter_type, s, bits);
if (!exit_must_be_taken)
@@ -679,7 +679,7 @@ number_of_iterations_ne (tree type, affine_iv *iv, tree final,
assumptions for divisibility of c. */
assumption = fold_build2 (FLOOR_MOD_EXPR, niter_type, c, d);
assumption = fold_build2 (EQ_EXPR, boolean_type_node,
- assumption, build_int_cst (niter_type, 0));
+ assumption, build_zero_cst (niter_type));
if (!integer_nonzerop (assumption))
niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
niter->assumptions, assumption);
@@ -846,7 +846,7 @@ assert_no_overflow_lt (tree type, affine_iv *iv0, affine_iv *iv1,
}
else
diff = fold_build2 (MINUS_EXPR, niter_type, step,
- build_int_cst (niter_type, 1));
+ build_one_cst (niter_type));
bound = fold_build2 (MINUS_EXPR, type,
TYPE_MAX_VALUE (type), fold_convert (type, diff));
assumption = fold_build2 (LE_EXPR, boolean_type_node,
@@ -867,7 +867,7 @@ assert_no_overflow_lt (tree type, affine_iv *iv0, affine_iv *iv1,
}
else
diff = fold_build2 (MINUS_EXPR, niter_type, step,
- build_int_cst (niter_type, 1));
+ build_one_cst (niter_type));
bound = fold_build2 (PLUS_EXPR, type,
TYPE_MIN_VALUE (type), fold_convert (type, diff));
assumption = fold_build2 (GE_EXPR, boolean_type_node,
@@ -963,7 +963,7 @@ assert_loop_rolls_lt (tree type, affine_iv *iv0, affine_iv *iv1,
if (integer_nonzerop (iv0->step))
{
diff = fold_build2 (MINUS_EXPR, type1,
- iv0->step, build_int_cst (type1, 1));
+ iv0->step, build_one_cst (type1));
/* We need to know that iv0->base >= MIN + iv0->step - 1. Since
0 address never belongs to any object, we can assume this for
@@ -985,7 +985,7 @@ assert_loop_rolls_lt (tree type, affine_iv *iv0, affine_iv *iv1,
else
{
diff = fold_build2 (PLUS_EXPR, type1,
- iv1->step, build_int_cst (type1, 1));
+ iv1->step, build_one_cst (type1));
if (!POINTER_TYPE_P (type))
{
@@ -1083,7 +1083,7 @@ number_of_iterations_lt (tree type, affine_iv *iv0, affine_iv *iv1,
{
affine_iv zps;
- zps.base = build_int_cst (niter_type, 0);
+ zps.base = build_zero_cst (niter_type);
zps.step = step;
/* number_of_iterations_lt_to_ne will add assumptions that ensure that
zps does not overflow. */
@@ -1102,7 +1102,7 @@ number_of_iterations_lt (tree type, affine_iv *iv0, affine_iv *iv1,
assert_loop_rolls_lt (type, iv0, iv1, niter, bnds);
s = fold_build2 (MINUS_EXPR, niter_type,
- step, build_int_cst (niter_type, 1));
+ step, build_one_cst (niter_type));
delta = fold_build2 (PLUS_EXPR, niter_type, delta, s);
niter->niter = fold_build2 (FLOOR_DIV_EXPR, niter_type, delta, step);
@@ -1167,13 +1167,13 @@ number_of_iterations_le (tree type, affine_iv *iv0, affine_iv *iv1,
iv1->base = fold_build_pointer_plus_hwi (iv1->base, 1);
else
iv1->base = fold_build2 (PLUS_EXPR, type1, iv1->base,
- build_int_cst (type1, 1));
+ build_one_cst (type1));
}
else if (POINTER_TYPE_P (type))
iv0->base = fold_build_pointer_plus_hwi (iv0->base, -1);
else
iv0->base = fold_build2 (MINUS_EXPR, type1,
- iv0->base, build_int_cst (type1, 1));
+ iv0->base, build_one_cst (type1));
bounds_add (bnds, double_int_one, type1);
@@ -1282,7 +1282,7 @@ number_of_iterations_cond (struct loop *loop,
iv0->step = fold_binary_to_constant (MINUS_EXPR, type,
iv0->step, iv1->step);
iv0->no_overflow = false;
- iv1->step = build_int_cst (type, 0);
+ iv1->step = build_zero_cst (type);
iv1->no_overflow = true;
}
@@ -1305,7 +1305,7 @@ number_of_iterations_cond (struct loop *loop,
/* If the loop exits immediately, there is nothing to do. */
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_zero_cst (unsigned_type_for (type));
niter->max = double_int_zero;
return true;
}
@@ -1946,7 +1946,7 @@ find_loop_niter (struct loop *loop, edge *exit)
{
/* We exit in the first iteration through this exit.
We won't find anything better. */
- niter = build_int_cst (unsigned_type_node, 0);
+ niter = build_zero_cst (unsigned_type_node);
*exit = ex;
break;
}
@@ -3017,7 +3017,7 @@ estimate_numbers_of_iterations_loop (struct loop *loop, bool use_undefined_p)
type = TREE_TYPE (niter);
if (TREE_CODE (niter_desc.may_be_zero) != INTEGER_CST)
niter = build3 (COND_EXPR, type, niter_desc.may_be_zero,
- build_int_cst (type, 0),
+ build_zero_cst (type),
niter);
record_estimate (loop, niter, niter_desc.max,
last_stmt (ex->src),
--
1.7.4.1
From 7535ba784f9f5f0e7583bf77e5baadb386131bd6 Mon Sep 17 00:00:00 2001
From: Sebastian Pop <seb...@gmail.com>
Date: Fri, 29 Jul 2011 14:35:56 -0500
Subject: [PATCH 2/2] Fix PR47594: Build signed niter expressions
2011-07-23 Sebastian Pop <sebastian....@amd.com>
PR middle-end/47594
* graphite-scop-detection.c (graphite_can_represent_scev): Return false
on TYPE_UNSIGNED.
* graphite-sese-to-poly.c (scan_tree_for_params_int): Do not call
double_int_sext.
* tree-ssa-loop-niter.c (number_of_iterations_ne): Use the signed types
for the trivial case, then convert to unsigned.
(number_of_iterations_lt): Use the original signed types.
(number_of_iterations_cond): Same.
(find_loop_niter): Build signed integer constant.
(loop_niter_by_eval): Same.
---
gcc/ChangeLog | 14 ++++++++
gcc/graphite-scop-detection.c | 6 +++
gcc/graphite-sese-to-poly.c | 7 +---
gcc/testsuite/ChangeLog | 5 +++
.../gfortran.dg/graphite/run-id-pr47594.f90 | 35 ++++++++++++++++++++
gcc/tree-ssa-loop-niter.c | 29 ++++++++++------
6 files changed, 79 insertions(+), 17 deletions(-)
create mode 100644 gcc/testsuite/gfortran.dg/graphite/run-id-pr47594.f90
diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 738144d..9b22eed 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,17 @@
+2011-07-23 Sebastian Pop <sebastian....@amd.com>
+
+ PR middle-end/47594
+ * graphite-scop-detection.c (graphite_can_represent_scev): Return false
+ on TYPE_UNSIGNED.
+ * graphite-sese-to-poly.c (scan_tree_for_params_int): Do not call
+ double_int_sext.
+ * tree-ssa-loop-niter.c (number_of_iterations_ne): Use the signed types
+ for the trivial case, then convert to unsigned.
+ (number_of_iterations_lt): Use the original signed types.
+ (number_of_iterations_cond): Same.
+ (find_loop_niter): Build signed integer constant.
+ (loop_niter_by_eval): Same.
+
2011-07-29 Uros Bizjak <ubiz...@gmail.com>
* config/i386/predicates.md (tp_or_register_operand): Remove predicate.
diff --git a/gcc/graphite-scop-detection.c b/gcc/graphite-scop-detection.c
index 3460568..403ff23 100644
--- a/gcc/graphite-scop-detection.c
+++ b/gcc/graphite-scop-detection.c
@@ -196,6 +196,12 @@ graphite_can_represent_scev (tree scev)
if (chrec_contains_undetermined (scev))
return false;
+ /* FIXME: As long as Graphite cannot handle wrap around effects of
+ induction variables, we discard them. */
+ if (TYPE_UNSIGNED (TREE_TYPE (scev))
+ && !POINTER_TYPE_P (TREE_TYPE (scev)))
+ return false;
+
switch (TREE_CODE (scev))
{
case PLUS_EXPR:
diff --git a/gcc/graphite-sese-to-poly.c b/gcc/graphite-sese-to-poly.c
index 7e23c9d..d15f0b3 100644
--- a/gcc/graphite-sese-to-poly.c
+++ b/gcc/graphite-sese-to-poly.c
@@ -647,14 +647,9 @@ scan_tree_for_params_int (tree cst, ppl_Linear_Expression_t expr, mpz_t k)
{
mpz_t val;
ppl_Coefficient_t coef;
- tree type = TREE_TYPE (cst);
mpz_init (val);
-
- /* Necessary to not get "-1 = 2^n - 1". */
- mpz_set_double_int (val, double_int_sext (tree_to_double_int (cst),
- TYPE_PRECISION (type)), false);
-
+ tree_int_to_gmp (cst, val);
mpz_mul (val, val, k);
ppl_new_Coefficient (&coef);
ppl_assign_Coefficient_from_mpz_t (coef, val);
diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
index cf5ee2b..55f2e91 100644
--- a/gcc/testsuite/ChangeLog
+++ b/gcc/testsuite/ChangeLog
@@ -1,3 +1,8 @@
+2011-07-23 Sebastian Pop <sebastian....@amd.com>
+
+ PR middle-end/47594
+ * gfortran.dg/graphite/run-id-pr47594.f90: New.
+
2011-07-29 Rainer Orth <r...@cebitec.uni-bielefeld.de>
PR tree-optimization/47407
diff --git a/gcc/testsuite/gfortran.dg/graphite/run-id-pr47594.f90 b/gcc/testsuite/gfortran.dg/graphite/run-id-pr47594.f90
new file mode 100644
index 0000000..7f36fc6
--- /dev/null
+++ b/gcc/testsuite/gfortran.dg/graphite/run-id-pr47594.f90
@@ -0,0 +1,35 @@
+! { dg-options "-O2 -fgraphite-identity" }
+
+ Subroutine foo (N, M)
+ Integer N
+ Integer M
+ integer A(8,16)
+ integer B(8)
+
+ B = (/ 2, 3, 5, 7, 11, 13, 17, 23 /)
+
+ do I = 1, N
+ do J = I, M
+ A(J,2) = B(J)
+ end do
+ end do
+
+ do I = 1, N
+ do J = I, M
+ if (A(J,2) /= B(J)) then
+ call abort ()
+ endif
+ end do
+ end do
+
+ Return
+ end
+
+
+ program main
+
+ Call foo (16, 8)
+
+ stop
+ end
+
diff --git a/gcc/tree-ssa-loop-niter.c b/gcc/tree-ssa-loop-niter.c
index 2ee3f6e..285577d 100644
--- a/gcc/tree-ssa-loop-niter.c
+++ b/gcc/tree-ssa-loop-niter.c
@@ -618,7 +618,7 @@ number_of_iterations_ne (tree type, affine_iv *iv, tree final,
struct tree_niter_desc *niter, bool exit_must_be_taken,
bounds *bnds)
{
- tree niter_type = unsigned_type_for (type);
+ tree niter_type = POINTER_TYPE_P (type) ? unsigned_type_for (type) : type;
tree s, c, d, bits, assumption, tmp, bound;
mpz_t max;
@@ -627,10 +627,9 @@ number_of_iterations_ne (tree type, affine_iv *iv, tree final,
niter->cmp = NE_EXPR;
/* Rearrange the terms so that we get inequality S * i <> C, with S
- positive. Also cast everything to the unsigned type. If IV does
- not overflow, BNDS bounds the value of C. Also, this is the
- case if the computation |FINAL - IV->base| does not overflow, i.e.,
- if BNDS->below in the result is nonnegative. */
+ positive. If IV does not overflow, BNDS bounds the value of C.
+ Also, this is the case if the computation |FINAL - IV->base| does
+ not overflow, i.e., if BNDS->below in the result is nonnegative. */
if (tree_int_cst_sign_bit (iv->step))
{
s = fold_convert (niter_type,
@@ -663,7 +662,12 @@ number_of_iterations_ne (tree type, affine_iv *iv, tree final,
/* Let nsd (step, size of mode) = d. If d does not divide c, the loop
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). To compute this, we
+ need unsigned types, otherwise we end on overflows. */
+ niter_type = unsigned_type_for (type);
+ s = fold_convert (niter_type, s);
+ c = fold_convert (niter_type, c);
+
bits = num_ending_zeros (s);
bound = build_low_bits_mask (niter_type,
(TYPE_PRECISION (niter_type)
@@ -1022,7 +1026,7 @@ number_of_iterations_lt (tree type, affine_iv *iv0, affine_iv *iv1,
struct tree_niter_desc *niter,
bool exit_must_be_taken, bounds *bnds)
{
- tree niter_type = unsigned_type_for (type);
+ tree niter_type = POINTER_TYPE_P (type) ? unsigned_type_for (type) : type;
tree delta, step, s;
mpz_t mstep, tmp;
@@ -1098,7 +1102,10 @@ number_of_iterations_lt (tree type, affine_iv *iv0, affine_iv *iv1,
/* 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,
- otherwise the loop does not roll. */
+ otherwise the loop does not roll. To compute the division, we
+ use unsigned types. */
+ niter_type = unsigned_type_for (type);
+ step = fold_convert (niter_type, step);
assert_loop_rolls_lt (type, iv0, iv1, niter, bnds);
s = fold_build2 (MINUS_EXPR, niter_type,
@@ -1305,7 +1312,7 @@ number_of_iterations_cond (struct loop *loop,
/* If the loop exits immediately, there is nothing to do. */
if (integer_zerop (fold_build2 (code, boolean_type_node, iv0->base, iv1->base)))
{
- niter->niter = build_zero_cst (unsigned_type_for (type));
+ niter->niter = build_zero_cst (type);
niter->max = double_int_zero;
return true;
}
@@ -1946,7 +1953,7 @@ find_loop_niter (struct loop *loop, edge *exit)
{
/* We exit in the first iteration through this exit.
We won't find anything better. */
- niter = build_zero_cst (unsigned_type_node);
+ niter = build_zero_cst (integer_type_node);
*exit = ex;
break;
}
@@ -2250,7 +2257,7 @@ loop_niter_by_eval (struct loop *loop, edge exit)
fprintf (dump_file,
"Proved that loop %d iterates %d times using brute force.\n",
loop->num, i);
- return build_int_cst (unsigned_type_node, i);
+ return build_int_cst (integer_type_node, i);
}
for (j = 0; j < 2; j++)
--
1.7.4.1
