From patchwork Sat Jul 30 02:40:20 2011 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Sebastian Pop X-Patchwork-Id: 107471 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) by ozlabs.org (Postfix) with SMTP id 22183B6F64 for ; Sat, 30 Jul 2011 12:41:21 +1000 (EST) Received: (qmail 5758 invoked by alias); 30 Jul 2011 02:41:19 -0000 Received: (qmail 5724 invoked by uid 22791); 30 Jul 2011 02:41:17 -0000 X-SWARE-Spam-Status: No, hits=-2.1 required=5.0 tests=AWL, BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, FREEMAIL_FROM, RCVD_IN_DNSWL_LOW, TW_TM, TW_ZJ, TW_ZP X-Spam-Check-By: sourceware.org Received: from mail-qy0-f175.google.com (HELO mail-qy0-f175.google.com) (209.85.216.175) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Sat, 30 Jul 2011 02:41:01 +0000 Received: by qyk30 with SMTP id 30so173876qyk.20 for ; Fri, 29 Jul 2011 19:41:00 -0700 (PDT) Received: by 10.229.65.7 with SMTP id g7mr1020166qci.264.1311993660288; Fri, 29 Jul 2011 19:41:00 -0700 (PDT) MIME-Version: 1.0 Received: by 10.229.239.139 with HTTP; Fri, 29 Jul 2011 19:40:20 -0700 (PDT) In-Reply-To: References: <1311612679-8020-1-git-send-email-sebpop@gmail.com> From: Sebastian Pop Date: Fri, 29 Jul 2011 21:40:20 -0500 Message-ID: Subject: Re: [PATCH] Fix PR47594: Sign extend constants while translating to Graphite To: Richard Guenther Cc: GCC Patches X-IsSubscribed: yes Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org Hi Richi, On Thu, Jul 28, 2011 at 03:58, Richard Guenther 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 7535ba784f9f5f0e7583bf77e5baadb386131bd6 Mon Sep 17 00:00:00 2001 From: Sebastian Pop Date: Fri, 29 Jul 2011 14:35:56 -0500 Subject: [PATCH 2/2] Fix PR47594: Build signed niter expressions 2011-07-23 Sebastian Pop 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 + + 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 * 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 + + PR middle-end/47594 + * gfortran.dg/graphite/run-id-pr47594.f90: New. + 2011-07-29 Rainer Orth 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