From patchwork Fri Dec 17 23:11:41 2010 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jakub Jelinek X-Patchwork-Id: 76003 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 98CB61007D3 for ; Sat, 18 Dec 2010 10:12:10 +1100 (EST) Received: (qmail 28006 invoked by alias); 17 Dec 2010 23:12:01 -0000 Received: (qmail 27941 invoked by uid 22791); 17 Dec 2010 23:11:59 -0000 X-SWARE-Spam-Status: No, hits=-6.3 required=5.0 tests=AWL, BAYES_00, RCVD_IN_DNSWL_HI, SPF_HELO_PASS, TW_TM, T_RP_MATCHES_RCVD X-Spam-Check-By: sourceware.org Received: from mx1.redhat.com (HELO mx1.redhat.com) (209.132.183.28) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Fri, 17 Dec 2010 23:11:52 +0000 Received: from int-mx02.intmail.prod.int.phx2.redhat.com (int-mx02.intmail.prod.int.phx2.redhat.com [10.5.11.12]) by mx1.redhat.com (8.13.8/8.13.8) with ESMTP id oBHNBptA006743 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=OK); Fri, 17 Dec 2010 18:11:51 -0500 Received: from tyan-ft48-01.lab.bos.redhat.com (tyan-ft48-01.lab.bos.redhat.com [10.16.42.4]) by int-mx02.intmail.prod.int.phx2.redhat.com (8.13.8/8.13.8) with ESMTP id oBHNBoa6013580 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO); Fri, 17 Dec 2010 18:11:51 -0500 Received: from tyan-ft48-01.lab.bos.redhat.com (localhost.localdomain [127.0.0.1]) by tyan-ft48-01.lab.bos.redhat.com (8.14.4/8.14.4) with ESMTP id oBHNBo3I002646; Sat, 18 Dec 2010 00:11:50 +0100 Received: (from jakub@localhost) by tyan-ft48-01.lab.bos.redhat.com (8.14.4/8.14.4/Submit) id oBHNBfJd002644; Sat, 18 Dec 2010 00:11:41 +0100 Date: Sat, 18 Dec 2010 00:11:41 +0100 From: Jakub Jelinek To: gcc-patches@gcc.gnu.org Cc: Sebastian Pop Subject: [PATCH] -ftree-loop-linear fixes (PR tree-optimization/46970) Message-ID: <20101217231141.GG2198@tyan-ft48-01.lab.bos.redhat.com> Reply-To: Jakub Jelinek MIME-Version: 1.0 Content-Disposition: inline User-Agent: Mutt/1.5.21 (2010-09-15) 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! gcc_loop_to_lambda_loop doesn't reject both when loop exit condition's SSA_NAME defined in the loop has defining statement a phi, or some statement where a single ssa use of it has defining statement a phi, but actually seems to expect only the latter case, because for the new iv it uses in the exit condition the incremented iv instead of the phi result. Additionally, it doesn't check whether the statement really in the middle is an increment by step, nor whether step isn't e.g. 0x100000001ULL when it stores into a host int LL_STEP field. This patch tries to fix that. The upper bound adjustment still looks unsafe to me in case it overflows, but that has been a problem before the patch and is not solved by the patch and would probably need much bigger changes in lambda-code.c. Bootstrapped/regtested on x86_64-linux and i686-linux. 2010-12-17 Jakub Jelinek PR tree-optimization/46970 * lambda-code.c (gcc_loop_to_lambda_loop): Give up if step doesn't fit into host int or if def stmt of inductionvar is neither PHI nor increment by step. If exit condition compares induction variable before increment, adjust ubound differently. * gcc.dg/pr46970-1.c: New test. * gcc.dg/pr46970-2.c: New test. Jakub --- gcc/lambda-code.c.jj 2010-08-20 16:05:41.000000000 +0200 +++ gcc/lambda-code.c 2010-12-17 17:57:32.000000000 +0100 @@ -1289,7 +1289,7 @@ gcc_loop_to_lambda_loop (struct loop *lo if (gimple_code (phi) != GIMPLE_PHI) { tree op = SINGLE_SSA_TREE_OPERAND (phi, SSA_OP_USE); - if (!op) + if (!op || !is_gimple_assign (phi)) { if (dump_file && (dump_flags & TDF_DETAILS)) @@ -1332,7 +1332,9 @@ gcc_loop_to_lambda_loop (struct loop *lo return NULL; } - if (TREE_CODE (step) != INTEGER_CST) + if (!host_integerp (step, 0) + || (HOST_WIDE_INT) TREE_INT_CST_LOW (step) + != (int) TREE_INT_CST_LOW (step)) { if (dump_file && (dump_flags & TDF_DETAILS)) @@ -1366,6 +1368,32 @@ gcc_loop_to_lambda_loop (struct loop *lo return NULL; } + if (SSA_NAME_DEF_STMT (inductionvar) != phi) + { + gimple stmt = SSA_NAME_DEF_STMT (inductionvar); + tree rhs2; + int stepintval = stepint; + switch (gimple_assign_rhs_code (stmt)) + { + case MINUS_EXPR: + stepintval = -stepint; + /* FALLTHRU */ + case PLUS_EXPR: + case POINTER_PLUS_EXPR: + rhs2 = gimple_assign_rhs2 (stmt); + if (TREE_CODE (rhs2) == INTEGER_CST + && (HOST_WIDE_INT) TREE_INT_CST_LOW (rhs2) == stepintval + && TREE_INT_CST_HIGH (rhs2) == (stepintval >= 0 ? 0 : -1)) + break; + /* FALLTHRU */ + default: + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, + "Unable to convert loop: Cannot find PHI node for induction variable\n"); + return NULL; + } + } + if (flow_bb_inside_loop_p (loop, gimple_phi_arg_edge (phi, 0)->src)) { lboundvar = PHI_ARG_DEF (phi, 1); @@ -1417,14 +1445,24 @@ gcc_loop_to_lambda_loop (struct loop *lo /* We might have some leftover. */ - if (gimple_cond_code (exit_cond) == LT_EXPR) - extra = -1 * stepint; - else if (gimple_cond_code (exit_cond) == NE_EXPR) - extra = -1 * stepint; - else if (gimple_cond_code (exit_cond) == GT_EXPR) - extra = -1 * stepint; - else if (gimple_cond_code (exit_cond) == EQ_EXPR) - extra = 1 * stepint; + if (SSA_NAME_DEF_STMT (inductionvar) != phi) + { + if (gimple_cond_code (exit_cond) == LT_EXPR) + extra = -1 * stepint; + else if (gimple_cond_code (exit_cond) == NE_EXPR) + extra = -1 * stepint; + else if (gimple_cond_code (exit_cond) == GT_EXPR) + extra = -1 * stepint; + else if (gimple_cond_code (exit_cond) == EQ_EXPR) + extra = 1 * stepint; + } + else + { + if (gimple_cond_code (exit_cond) == LE_EXPR) + extra = 1 * stepint; + else if (gimple_cond_code (exit_cond) == GE_EXPR) + extra = 1 * stepint; + } ubound = gcc_tree_to_linear_expression (depth, uboundvar, outerinductionvars, --- gcc/testsuite/gcc.dg/pr46970-1.c.jj 2010-12-17 16:08:01.000000000 +0100 +++ gcc/testsuite/gcc.dg/pr46970-1.c 2010-12-17 16:07:46.000000000 +0100 @@ -0,0 +1,27 @@ +/* PR tree-optimization/46970 */ +/* { dg-do run } */ +/* { dg-options "-Os -ftree-loop-linear" } */ + +int +foo (int n, int *a) +{ + int i, j; + + for (i = 0; i < n; i++) + for (j = 0; j < n; j++) + a[j] = i + n; + + for (j = 0; j < n; j++) + if (a[j] != i + n - 1) + __builtin_abort (); + + return 0; +} + +int +main () +{ + int a[16]; + foo (16, a); + return 0; +} --- gcc/testsuite/gcc.dg/pr46970-2.c.jj 2010-12-17 18:01:05.000000000 +0100 +++ gcc/testsuite/gcc.dg/pr46970-2.c 2010-12-17 16:43:46.000000000 +0100 @@ -0,0 +1,28 @@ +/* { dg-do run } */ +/* { dg-options "-O2 -ftree-loop-linear" } */ +/* { dg-require-effective-target size32plus } */ + +double u[1782225]; + +__attribute__((noinline, noclone)) int +foo (int N, int *res) +{ + unsigned int i, j; + double sum = 0; + for (i = 0; i < N; i++) + for (j = 0; j < N; j++) + sum = sum + u[i + 1335 * j]; + *res = sum + N; +} + +int +main (void) +{ + int i; + for (i = 0; i < 1782225; i++) + u[i] = 1.0; + foo (64, &i); + if (i != 4160) + __builtin_abort (); + return 0; +}