From patchwork Thu Nov 7 14:32:37 2013 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jakub Jelinek X-Patchwork-Id: 289369 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]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (Client did not present a certificate) by ozlabs.org (Postfix) with ESMTPS id 606492C00E4 for ; Fri, 8 Nov 2013 01:33:01 +1100 (EST) DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:date :from:to:cc:subject:message-id:reply-to:references:mime-version :content-type:in-reply-to; q=dns; s=default; b=v0Z/MhSwluSnn2smP S1rBkMl42jiaCKk/XAVD8NlREhv7BWCsy0X/Nkdu/XrtNyYSwoeIcsKfuUZgNjpp WuwR+J/1Icusvh+JRZfhbVpJMjVLTMqKB+hhDg5bF5s0Text+I5zjiVm38sl005Z IADS8Cz9rHY26BizWgZ7OqjMH4= DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:date :from:to:cc:subject:message-id:reply-to:references:mime-version :content-type:in-reply-to; s=default; bh=csRavJ1Gh2vAzaV8zN4vKB7 JGTU=; b=jy2uKPR58HKlMFmna48nGHBsU/hwWJ0UjogmmTqpkcT2SdOYKAXYaLc iDNkKtSS4RPo/7Ac6uKSCqfKFgPVRIDNQ9NcvQuQGKx1RPgbNYt18azNU5RJbVqP nar1wRcGKmTJLalqHBiCC2M3upsCsY4Dy/Mis7SkSC2VAjmKNymk= Received: (qmail 29167 invoked by alias); 7 Nov 2013 14:32:50 -0000 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 Received: (qmail 29151 invoked by uid 89); 7 Nov 2013 14:32:50 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=0.5 required=5.0 tests=AWL, BAYES_50, RDNS_NONE, SPAM_SUBJECT, SPF_HELO_PASS, SPF_PASS autolearn=no version=3.3.2 X-HELO: mx1.redhat.com Received: from Unknown (HELO mx1.redhat.com) (209.132.183.28) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Thu, 07 Nov 2013 14:32:48 +0000 Received: from int-mx11.intmail.prod.int.phx2.redhat.com (int-mx11.intmail.prod.int.phx2.redhat.com [10.5.11.24]) by mx1.redhat.com (8.14.4/8.14.4) with ESMTP id rA7EWepQ029200 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=OK); Thu, 7 Nov 2013 09:32:40 -0500 Received: from tucnak.zalov.cz (vpn1-6-38.ams2.redhat.com [10.36.6.38]) by int-mx11.intmail.prod.int.phx2.redhat.com (8.14.4/8.14.4) with ESMTP id rA7EWcAs008848 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO); Thu, 7 Nov 2013 09:32:40 -0500 Received: from tucnak.zalov.cz (localhost [127.0.0.1]) by tucnak.zalov.cz (8.14.7/8.14.7) with ESMTP id rA7EWc17018395; Thu, 7 Nov 2013 15:32:38 +0100 Received: (from jakub@localhost) by tucnak.zalov.cz (8.14.7/8.14.7/Submit) id rA7EWbi0018394; Thu, 7 Nov 2013 15:32:37 +0100 Date: Thu, 7 Nov 2013 15:32:37 +0100 From: Jakub Jelinek To: Jeff Law Cc: Richard Biener , Cong Hou , GCC Patches Subject: Re: [PATCH] Use get_range_info during number of iterations analysis Message-ID: <20131107143237.GC27813@tucnak.zalov.cz> Reply-To: Jakub Jelinek References: <527953A4.4030601@redhat.com> <20131106171342.GF27813@tucnak.zalov.cz> <20131106172300.GG27813@tucnak.zalov.cz> <527AC0D0.4040803@redhat.com> MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: <527AC0D0.4040803@redhat.com> User-Agent: Mutt/1.5.21 (2010-09-15) X-IsSubscribed: yes On Wed, Nov 06, 2013 at 03:21:04PM -0700, Jeff Law wrote: > >2013-11-06 Jakub Jelinek > > > > * tree-ssa-loop-niter.c: Include tree-ssanames.h. > > (determine_value_range): Add loop argument. Use get_range_info to > > improve range. > > (bound_difference): Adjust caller. > Clever, using the range from the PHI in the loop header. While it > may be too wide, it's likely going to be a lot better than nothing. > > Add a testcase and this is OK. Ok, thanks, here is what I've committed after another bootstrap/regtest. 2013-11-07 Jakub Jelinek * tree-ssa-loop-niter.c: Include tree-ssanames.h. (determine_value_range): Add loop argument. Use get_range_info to improve range. (bound_difference): Adjust caller. * gcc.dg/tree-ssa/loop-39.c: New test. Jakub --- gcc/tree-ssa-loop-niter.c.jj 2013-10-24 10:19:21.000000000 +0200 +++ gcc/tree-ssa-loop-niter.c 2013-11-07 11:49:37.568083138 +0100 @@ -45,6 +45,7 @@ along with GCC; see the file COPYING3. #include "diagnostic-core.h" #include "tree-inline.h" #include "tree-pass.h" +#include "tree-ssanames.h" #define SWAP(X, Y) do { affine_iv *tmp = (X); (X) = (Y); (Y) = tmp; } while (0) @@ -119,9 +120,12 @@ split_to_var_and_offset (tree expr, tree in TYPE to MIN and MAX. */ static void -determine_value_range (tree type, tree var, mpz_t off, +determine_value_range (struct loop *loop, tree type, tree var, mpz_t off, mpz_t min, mpz_t max) { + double_int minv, maxv; + enum value_range_type rtype = VR_VARYING; + /* If the expression is a constant, we know its value exactly. */ if (integer_zerop (var)) { @@ -130,9 +134,73 @@ determine_value_range (tree type, tree v return; } + get_type_static_bounds (type, min, max); + + /* See if we have some range info from VRP. */ + if (TREE_CODE (var) == SSA_NAME && INTEGRAL_TYPE_P (type)) + { + edge e = loop_preheader_edge (loop); + gimple_stmt_iterator gsi; + + /* Either for VAR itself... */ + rtype = get_range_info (var, &minv, &maxv); + /* Or for PHI results in loop->header where VAR is used as + PHI argument from the loop preheader edge. */ + for (gsi = gsi_start_phis (loop->header); !gsi_end_p (gsi); gsi_next (&gsi)) + { + gimple phi = gsi_stmt (gsi); + double_int minc, maxc; + if (PHI_ARG_DEF_FROM_EDGE (phi, e) == var + && (get_range_info (gimple_phi_result (phi), &minc, &maxc) + == VR_RANGE)) + { + if (rtype != VR_RANGE) + { + rtype = VR_RANGE; + minv = minc; + maxv = maxc; + } + else + { + minv = minv.max (minc, TYPE_UNSIGNED (type)); + maxv = maxv.min (maxc, TYPE_UNSIGNED (type)); + gcc_assert (minv.cmp (maxv, TYPE_UNSIGNED (type)) <= 0); + } + } + } + if (rtype == VR_RANGE) + { + mpz_t minm, maxm; + gcc_assert (minv.cmp (maxv, TYPE_UNSIGNED (type)) <= 0); + mpz_init (minm); + mpz_init (maxm); + mpz_set_double_int (minm, minv, TYPE_UNSIGNED (type)); + mpz_set_double_int (maxm, maxv, TYPE_UNSIGNED (type)); + mpz_add (minm, minm, off); + mpz_add (maxm, maxm, off); + /* If the computation may not wrap or off is zero, then this + is always fine. If off is negative and minv + off isn't + smaller than type's minimum, or off is positive and + maxv + off isn't bigger than type's maximum, use the more + precise range too. */ + if (nowrap_type_p (type) + || mpz_sgn (off) == 0 + || (mpz_sgn (off) < 0 && mpz_cmp (minm, min) >= 0) + || (mpz_sgn (off) > 0 && mpz_cmp (maxm, max) <= 0)) + { + mpz_set (min, minm); + mpz_set (max, maxm); + mpz_clear (minm); + mpz_clear (maxm); + return; + } + mpz_clear (minm); + mpz_clear (maxm); + } + } + /* If the computation may wrap, we know nothing about the value, except for the range of the type. */ - get_type_static_bounds (type, min, max); if (!nowrap_type_p (type)) return; @@ -405,8 +473,8 @@ bound_difference (struct loop *loop, tre mpz_init (maxx); mpz_init (miny); mpz_init (maxy); - determine_value_range (type, varx, offx, minx, maxx); - determine_value_range (type, vary, offy, miny, maxy); + determine_value_range (loop, type, varx, offx, minx, maxx); + determine_value_range (loop, type, vary, offy, miny, maxy); mpz_sub (bnds->below, minx, maxy); mpz_sub (bnds->up, maxx, miny); --- gcc/testsuite/gcc.dg/tree-ssa/loop-39.c.jj 2013-11-07 11:52:01.871309995 +0100 +++ gcc/testsuite/gcc.dg/tree-ssa/loop-39.c 2013-11-07 11:54:30.549496152 +0100 @@ -0,0 +1,26 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-sccp-details" } */ + +int +foo (unsigned int n) +{ + int i, r = 1; + if (n > 0) + { + asm (""); + if (n < 10) + { + asm (""); + do + { + --n; + r *= 2; + } + while (n > 0); + } + } + return r + n; +} + +/* { dg-final { scan-tree-dump "# of iterations \[^\n\r]*, bounded by 8" "sccp" } } */ +/* { dg-final { cleanup-tree-dump "sccp" } } */