From: Sebastian Pop <sebpop@gmail.com>
To: gcc-patches@gcc.gnu.org
Cc: rguenther@suse.de, Sebastian Pop <sebpop@gmail.com>
Subject: [PATCH 2/2] Fix PR47594: Build signed niter expressions
Date: Tue, 02 Aug 2011 05:03:00 -0000 [thread overview]
Message-ID: <1312261287-13124-3-git-send-email-sebpop@gmail.com> (raw)
In-Reply-To: <1312261287-13124-1-git-send-email-sebpop@gmail.com>
2011-07-23 Sebastian Pop <sebastian.pop@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 | 63 ++++++++++++++++----
6 files changed, 113 insertions(+), 17 deletions(-)
create mode 100644 gcc/testsuite/gfortran.dg/graphite/run-id-pr47594.f90
diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 580c12f..33bd7b4 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,17 @@
+2011-07-23 Sebastian Pop <sebastian.pop@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-08-01 Richard Henderson <rth@redhat.com>
PR target/49881
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 4ff8a10..1f8d049 100644
--- a/gcc/testsuite/ChangeLog
+++ b/gcc/testsuite/ChangeLog
@@ -1,3 +1,8 @@
+2011-07-23 Sebastian Pop <sebastian.pop@amd.com>
+
+ PR middle-end/47594
+ * gfortran.dg/graphite/run-id-pr47594.f90: New.
+
2011-08-01 Jason Merrill <jason@redhat.com>
PR c++/49932
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..3bd9511 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,
@@ -648,6 +647,30 @@ number_of_iterations_ne (tree type, affine_iv *iv, tree final,
fold_convert (niter_type, iv->base));
}
+ if ((TREE_CODE_CLASS (TREE_CODE (c)) == tcc_constant && TREE_OVERFLOW (c))
+ || (TREE_CODE_CLASS (TREE_CODE (s)) == tcc_constant && TREE_OVERFLOW (s)))
+ {
+ niter_type = unsigned_type_for (type);
+
+ if (tree_int_cst_sign_bit (iv->step))
+ {
+ s = fold_convert (niter_type,
+ fold_build1 (NEGATE_EXPR, type, iv->step));
+ c = fold_build2 (MINUS_EXPR, niter_type,
+ fold_convert (niter_type, iv->base),
+ fold_convert (niter_type, final));
+ bounds_negate (bnds);
+ }
+ else
+ {
+ s = fold_convert (niter_type, iv->step);
+ c = fold_build2 (MINUS_EXPR, niter_type,
+ fold_convert (niter_type, final),
+ fold_convert (niter_type, iv->base));
+
+ }
+ }
+
mpz_init (max);
number_of_iterations_ne_max (max, iv->no_overflow, c, s, bnds,
exit_must_be_taken);
@@ -663,7 +686,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 +1050,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;
@@ -1043,6 +1071,15 @@ number_of_iterations_lt (tree type, affine_iv *iv0, affine_iv *iv1,
fold_convert (niter_type, iv1->base),
fold_convert (niter_type, iv0->base));
+ if (TREE_CODE_CLASS (TREE_CODE (delta)) == tcc_constant
+ && TREE_OVERFLOW (delta))
+ {
+ niter_type = unsigned_type_for (type);
+ delta = fold_build2 (MINUS_EXPR, niter_type,
+ fold_convert (niter_type, iv1->base),
+ fold_convert (niter_type, iv0->base));
+ }
+
/* First handle the special case that the step is +-1. */
if ((integer_onep (iv0->step) && integer_zerop (iv1->step))
|| (integer_all_onesp (iv1->step) && integer_zerop (iv0->step)))
@@ -1098,7 +1135,11 @@ 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);
+ delta = fold_convert (niter_type, delta);
assert_loop_rolls_lt (type, iv0, iv1, niter, bnds);
s = fold_build2 (MINUS_EXPR, niter_type,
@@ -1305,7 +1346,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 +1987,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 +2291,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
next prev parent reply other threads:[~2011-08-02 5:03 UTC|newest]
Thread overview: 16+ messages / expand[flat|nested] mbox.gz Atom feed top
2011-07-25 17:07 [PATCH] Fix PR47594: Sign extend constants while translating to Graphite Sebastian Pop
[not found] ` <alpine.LNX.2.00.1107261020220.810@zhemvz.fhfr.qr>
2011-07-26 14:33 ` Sebastian Pop
2011-07-26 14:35 ` Richard Guenther
2011-07-26 14:50 ` Sebastian Pop
2011-07-26 15:26 ` Richard Guenther
2011-07-27 16:51 ` Sebastian Pop
2011-07-28 9:31 ` Richard Guenther
2011-07-30 7:37 ` Sebastian Pop
[not found] ` <20110730133351.GA1564@bromo.med.uc.edu>
2011-07-30 17:09 ` Sebastian Pop
2011-08-02 5:02 ` [PATCH 0/2] Fix PR47594 Sebastian Pop
2011-08-02 5:03 ` [PATCH 1/2] Use build_zero_cst or build_one_cst Sebastian Pop
2011-08-02 8:53 ` Richard Guenther
2011-08-02 5:03 ` Sebastian Pop [this message]
2011-08-02 7:48 ` [PATCH 2/2] Fix PR47594: Build signed niter expressions Zdenek Dvorak
2011-08-02 9:51 ` Richard Guenther
2011-08-02 15:10 ` Sebastian Pop
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=1312261287-13124-3-git-send-email-sebpop@gmail.com \
--to=sebpop@gmail.com \
--cc=gcc-patches@gcc.gnu.org \
--cc=rguenther@suse.de \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).