From patchwork Mon Dec 20 22:28:22 2010 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Jakub Jelinek X-Patchwork-Id: 76239 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 28F99B6F1E for ; Tue, 21 Dec 2010 09:28:37 +1100 (EST) Received: (qmail 29419 invoked by alias); 20 Dec 2010 22:28:35 -0000 Received: (qmail 29410 invoked by uid 22791); 20 Dec 2010 22:28:34 -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; Mon, 20 Dec 2010 22:28:26 +0000 Received: from int-mx01.intmail.prod.int.phx2.redhat.com (int-mx01.intmail.prod.int.phx2.redhat.com [10.5.11.11]) by mx1.redhat.com (8.13.8/8.13.8) with ESMTP id oBKMSOTe007016 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=OK); Mon, 20 Dec 2010 17:28:24 -0500 Received: from tyan-ft48-01.lab.bos.redhat.com (tyan-ft48-01.lab.bos.redhat.com [10.16.42.4]) by int-mx01.intmail.prod.int.phx2.redhat.com (8.13.8/8.13.8) with ESMTP id oBKMSNmk032373 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO); Mon, 20 Dec 2010 17:28:24 -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 oBKMSNXt011760; Mon, 20 Dec 2010 23:28:23 +0100 Received: (from jakub@localhost) by tyan-ft48-01.lab.bos.redhat.com (8.14.4/8.14.4/Submit) id oBKMSNuI011759; Mon, 20 Dec 2010 23:28:23 +0100 Date: Mon, 20 Dec 2010 23:28:22 +0100 From: Jakub Jelinek To: Sebastian Pop Cc: gcc-patches@gcc.gnu.org Subject: [PATCH] -ftree-loop-linear fixes (PR tree-optimization/46970) (take 2) Message-ID: <20101220222822.GB16156@tyan-ft48-01.lab.bos.redhat.com> Reply-To: Jakub Jelinek References: <20101217231141.GG2198@tyan-ft48-01.lab.bos.redhat.com> MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: 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 On Sun, Dec 19, 2010 at 11:05:07PM -0600, Sebastian Pop wrote: > The patch looks good to me, but I cannot approve it. > > >   /* 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; > > +    } > > It would be easier to read the following equivalent code: Or a switch, as done in this patch, bootstrapped/regtested on x86_64-linux and i686-linux: 2010-12-20 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-20 21:19:12.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,30 @@ 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) + switch (gimple_cond_code (exit_cond)) + { + case LT_EXPR: + case NE_EXPR: + case GT_EXPR: + extra = -1 * stepint; + break; + case EQ_EXPR: + extra = 1 * stepint; + break; + default: + break; + } + else + switch (gimple_cond_code (exit_cond)) + { + case LE_EXPR: + case GE_EXPR: + extra = 1 * stepint; + break; + default: + break; + } 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; +}