From patchwork Wed Sep 30 16:27:17 2015 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Michael Collison X-Patchwork-Id: 54335 Return-Path: X-Original-To: linaro@patches.linaro.org Delivered-To: linaro@patches.linaro.org Received: from mail-la0-f72.google.com (mail-la0-f72.google.com [209.85.215.72]) by patches.linaro.org (Postfix) with ESMTPS id AA61222E23 for ; Wed, 30 Sep 2015 16:27:42 +0000 (UTC) Received: by labjc2 with SMTP id jc2sf16403161lab.1 for ; Wed, 30 Sep 2015 09:27:41 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:delivered-to:mailing-list:precedence:list-id :list-unsubscribe:list-archive:list-post:list-help:sender :delivered-to:message-id:date:from:user-agent:mime-version:to:cc :subject:references:in-reply-to:content-type:x-original-sender :x-original-authentication-results; bh=yUUSjhEMF3oZR2jwEAvwl5chX8aroNig9haqNx8l/rY=; b=Krlo8BOTjV+8Nlh1AVuDPZ1DFMiwp6dQv3/0ihrBZ+aIXjOwV+qeQE55TgOgMyA1gT aGAKv7FJmVl3YGKAm55x8JOz+HBIu+jOA02G8HkZceuX38Rx958SiaJH5jaxNitO2gUe A/x+etSaz6B2607U790SyfFSLBTtnenWsOE298t3bVGHhsDifih+l1HDu0cWwkWqChO3 ieAB2PWQcjjgWfH3wC73B+nNdNCqmh3OkpN7fVC6g0/VuL/hX5PLFoHfNQlO29HnpzDG xeKC09arvjAVJOdBCQ9f2x0sF8+Jw6TARq9n5jKvHhBcCf2qjoINWHecj46uw9MUtW+v eisw== X-Gm-Message-State: ALoCoQm/LTst2funeEm5RemwLuAmioO6N2HNhcMihrLYzA47glyzESkVv1y4ONSVpsrQcxOFVIPP X-Received: by 10.112.138.170 with SMTP id qr10mr726387lbb.4.1443630461533; Wed, 30 Sep 2015 09:27:41 -0700 (PDT) X-BeenThere: patchwork-forward@linaro.org Received: by 10.152.23.233 with SMTP id p9ls53895laf.24.gmail; Wed, 30 Sep 2015 09:27:41 -0700 (PDT) X-Received: by 10.25.209.80 with SMTP id i77mr940675lfg.92.1443630461391; Wed, 30 Sep 2015 09:27:41 -0700 (PDT) Received: from mail-la0-x230.google.com (mail-la0-x230.google.com. [2a00:1450:4010:c03::230]) by mx.google.com with ESMTPS id v2si82550lav.3.2015.09.30.09.27.41 for (version=TLSv1.2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Wed, 30 Sep 2015 09:27:41 -0700 (PDT) Received-SPF: pass (google.com: domain of patch+caf_=patchwork-forward=linaro.org@linaro.org designates 2a00:1450:4010:c03::230 as permitted sender) client-ip=2a00:1450:4010:c03::230; Received: by labzv5 with SMTP id zv5so53198764lab.1 for ; Wed, 30 Sep 2015 09:27:41 -0700 (PDT) X-Received: by 10.25.210.206 with SMTP id j197mr961179lfg.86.1443630460889; Wed, 30 Sep 2015 09:27:40 -0700 (PDT) X-Forwarded-To: patchwork-forward@linaro.org X-Forwarded-For: patch@linaro.org patchwork-forward@linaro.org Delivered-To: patch@linaro.org Received: by 10.112.59.35 with SMTP id w3csp66269lbq; Wed, 30 Sep 2015 09:27:39 -0700 (PDT) X-Received: by 10.66.138.11 with SMTP id qm11mr5935892pab.126.1443630458930; Wed, 30 Sep 2015 09:27:38 -0700 (PDT) Received: from sourceware.org (server1.sourceware.org. [209.132.180.131]) by mx.google.com with ESMTPS id cs1si1862519pbb.133.2015.09.30.09.27.38 for (version=TLSv1.2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Wed, 30 Sep 2015 09:27:38 -0700 (PDT) Received-SPF: pass (google.com: domain of gcc-patches-return-408746-patch=linaro.org@gcc.gnu.org designates 209.132.180.131 as permitted sender) client-ip=209.132.180.131; Received: (qmail 15193 invoked by alias); 30 Sep 2015 16:27:24 -0000 Mailing-List: list patchwork-forward@linaro.org; contact patchwork-forward+owners@linaro.org Precedence: list 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 15176 invoked by uid 89); 30 Sep 2015 16:27:24 -0000 X-Virus-Found: No X-Spam-SWARE-Status: No, score=-2.3 required=5.0 tests=AWL, BAYES_00, RCVD_IN_DNSWL_LOW, SPF_PASS autolearn=ham version=3.3.2 X-HELO: mail-pa0-f42.google.com Received: from mail-pa0-f42.google.com (HELO mail-pa0-f42.google.com) (209.85.220.42) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (AES128-GCM-SHA256 encrypted) ESMTPS; Wed, 30 Sep 2015 16:27:22 +0000 Received: by pacfv12 with SMTP id fv12so46046655pac.2 for ; Wed, 30 Sep 2015 09:27:20 -0700 (PDT) X-Received: by 10.68.179.33 with SMTP id dd1mr6000691pbc.134.1443630440344; Wed, 30 Sep 2015 09:27:20 -0700 (PDT) Received: from [192.168.1.14] (ip70-176-202-128.ph.ph.cox.net. [70.176.202.128]) by smtp.googlemail.com with ESMTPSA id po4sm1548708pbb.64.2015.09.30.09.27.19 (version=TLSv1/SSLv3 cipher=OTHER); Wed, 30 Sep 2015 09:27:19 -0700 (PDT) Message-ID: <560C0D65.2010300@linaro.org> Date: Wed, 30 Sep 2015 09:27:17 -0700 From: Michael Collison User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:31.0) Gecko/20100101 Thunderbird/31.4.0 MIME-Version: 1.0 To: Richard Biener CC: GCC Patches , Jeff Law , Marc Glisse Subject: Re: [PATCH] Optimize certain end of loop conditions into min/max operation References: <55B5A884.4060105@linaro.org> <55B65A4B.3050705@redhat.com> <55BBA052.2060900@redhat.com> <55BBBBE6.2070207@linaro.org> <55BBBE2E.1020408@redhat.com> <55FBAFD1.9080300@linaro.org> <560B8F51.6030108@linaro.org> In-Reply-To: X-Original-Sender: michael.collison@linaro.org X-Original-Authentication-Results: mx.google.com; spf=pass (google.com: domain of patch+caf_=patchwork-forward=linaro.org@linaro.org designates 2a00:1450:4010:c03::230 as permitted sender) smtp.mailfrom=patch+caf_=patchwork-forward=linaro.org@linaro.org; dkim=pass header.i=@gcc.gnu.org X-Google-Group-Id: 836684582541 The current patch is attached. 2015-09-30 Michael Collison Andrew Pinski * match.pd ((x < y) && (x < z) -> x < min (y,z), (x > y) and (x > z) -> x > max (y,z)) * testsuite/gcc.dg/tree-ssa/minmax-loopend.c: New test. On 09/30/2015 01:14 AM, Richard Biener wrote: > On Wed, Sep 30, 2015 at 9:29 AM, Michael Collison > wrote: >> Richard and Marc, >> >> What is ':s'? I don't see any documentation for it. So you would like me to >> remove :c and add :s? > There is documentation for both in the internals manual. > > I don't have enough context to say whether you should remove "them" or > not. What's > the current patch? If you made the suggested changes you should be left with > only required :s and :c. > > Richard. > >> >> On 09/18/2015 02:23 AM, Richard Biener wrote: >>> On Fri, Sep 18, 2015 at 9:38 AM, Marc Glisse wrote: >>>> Just a couple extra points. We can end up with a mix of < and >, which >>>> might >>>> prevent from matching: >>>> >>>> _3 = b_1(D) > a_2(D); >>>> _5 = a_2(D) < c_4(D); >>>> _8 = _3 & _5; >>>> >>>> Just like with &, we could also transform: >>>> x < y | x < z ---> x < max(y, z) >>>> >>>> (but maybe wait to make sure reviewers are ok with the first >>>> transformation >>>> before generalizing) >>> Please merge the patterns as suggested and do the :c/:s changes as well. >>> >>> The issue with getting mixed < and > is indeed there - I've wanted to >>> extend :c to handle tcc_comparison in some way at some point but >>> didn't get to how best to implement that yet... >>> >>> So to fix that currently you have to replicate the merged pattern >>> with swapped comparison operands. >>> >>> Otherwise I'm fine with the general approach. >>> >>> Richard. >>> >>>> On Fri, 18 Sep 2015, Marc Glisse wrote: >>>> >>>>> On Thu, 17 Sep 2015, Michael Collison wrote: >>>>> >>>>>> Here is the the patch modified with test cases for MIN_EXPR and >>>>>> MAX_EXPR >>>>>> expressions. I need some assistance; this test case will fail on >>>>>> targets >>>>>> that don't have support for MIN/MAX such as 68k. Is there any way to >>>>>> remedy >>>>>> this short of enumerating whether a target support MIN/MAX in >>>>>> testsuite/lib/target_support? >>>>>> >>>>>> 2015-07-24 Michael Collison >>>>>> Andrew Pinski >>>>>> >>>>>> * match.pd ((x < y) && (x < z) -> x < min (y,z), >>>>>> (x > y) and (x > z) -> x > max (y,z)) >>>>>> * testsuite/gcc.dg/tree-ssa/minmax-loopend.c: New test. >>>>>> >>>>>> diff --git a/gcc/match.pd b/gcc/match.pd >>>>>> index 5e8fd32..8691710 100644 >>>>>> --- a/gcc/match.pd >>>>>> +++ b/gcc/match.pd >>>>>> @@ -1793,3 +1793,17 @@ along with GCC; see the file COPYING3. If not >>>>>> see >>>>>> (convert (bit_and (op (convert:utype @0) (convert:utype @1)) >>>>>> (convert:utype @4))))))) >>>>>> >>>>>> + >>>>>> +/* Transform (@0 < @1 and @0 < @2) to use min */ >>>>>> +(for op (lt le) >>>>>> +(simplify >>>>> >>>>> You seem to be missing all indentation. >>>>> >>>>>> +(bit_and:c (op @0 @1) (op @0 @2)) >>>>> >>>>> :c seems useless here. On the other hand, it might make sense to use >>>>> op:s >>>>> since this is mostly useful if it removes the 2 original comparisons. >>>>> >>>>>> +(if (INTEGRAL_TYPE_P (TREE_TYPE (@0))) >>>>> >>>>> How did you chose this restriction? It seems safe enough, but the >>>>> transformation could make sense in other cases as well. It can always be >>>>> generalized later though. >>>>> >>>>>> +(op @0 (min @1 @2))))) >>>>>> + >>>>>> +/* Transform (@0 > @1 and @0 > @2) to use max */ >>>>>> +(for op (gt ge) >>>>> >>>>> Note that you could unify the patterns with something like: >>>>> (for op (lt le gt ge) >>>>> ext (min min max max) >>>>> (simplify ... >>>>> >>>>>> +(simplify >>>>>> +(bit_and:c (op @0 @1) (op @0 @2)) >>>>>> +(if (INTEGRAL_TYPE_P (TREE_TYPE (@0))) >>>>>> +(op @0 (max @1 @2))))) >>>>>> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/minmax-loopend.c >>>>>> b/gcc/testsuite/gcc.dg/tree-ssa/minmax-loopend.c >>>>>> new file mode 100644 >>>>>> index 0000000..cc0189a >>>>>> --- /dev/null >>>>>> +++ b/gcc/testsuite/gcc.dg/tree-ssa/minmax-loopend.c >>>>>> @@ -0,0 +1,23 @@ >>>>>> +/* { dg-do compile } */ >>>>>> +/* { dg-options "-O2 -fdump-tree-optimized" } */ >>>>>> + >>>>>> +#define N 1024 >>>>>> + >>>>>> +int a[N], b[N], c[N]; >>>>>> + >>>>>> +void add (unsigned int m, unsigned int n) >>>>>> +{ >>>>>> + unsigned int i; >>>>>> + for (i = 0; i < m && i < n; ++i) >>>>> >>>>> Maybe writing '&' instead of '&&' would make it depend less on the >>>>> target. >>>>> Also, both tests seem to be for GENERIC (i.e. I expect that you are >>>>> already >>>>> seeing the optimized version with -fdump-tree-original or >>>>> -fdump-tree-gimple). Maybe something as simple as: >>>>> int f(long a, long b, long c) { >>>>> int cmp1 = a < b; >>>>> int cmp2 = a < c; >>>>> return cmp1 & cmp2; >>>>> } >>>>> >>>>>> + a[i] = b[i] + c[i]; >>>>>> +} >>>>>> + >>>>>> +void add2 (unsigned int m, unsigned int n) >>>>>> +{ >>>>>> + unsigned int i; >>>>>> + for (i = N-1; i > m && i > n; --i) >>>>>> + a[i] = b[i] + c[i]; >>>>>> +} >>>>>> + >>>>>> +/* { dg-final { scan-tree-dump "MIN_EXPR" 1 "optimized" } } */ >>>>>> +/* { dg-final { scan-tree-dump "MAX_EXPR" 1 "optimized" } } */ >>>>> >>>>> >>>> -- >>>> Marc Glisse >> >> -- >> Michael Collison >> Linaro Toolchain Working Group >> michael.collison@linaro.org >> diff --git a/gcc/match.pd b/gcc/match.pd index 5e8fd32..77cb91d 100644 --- a/gcc/match.pd +++ b/gcc/match.pd @@ -1793,3 +1793,13 @@ along with GCC; see the file COPYING3. If not see (convert (bit_and (op (convert:utype @0) (convert:utype @1)) (convert:utype @4))))))) + +/* Transform (@0 < @1 and @0 < @2) to use min, + (@0 > @1 and @0 > @2) to use max */ +(for op (lt le gt ge) + ext (min min max max) +(simplify +(bit_and:c (op @0 @1) (op @0 @2)) +(if (INTEGRAL_TYPE_P (TREE_TYPE (@0))) +(op @0 (ext @1 @2))))) + diff --git a/gcc/testsuite/gcc.dg/tree-ssa/minmax-loopend.c b/gcc/testsuite/gcc.dg/tree-ssa/minmax-loopend.c new file mode 100644 index 0000000..dfe6120 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/minmax-loopend.c @@ -0,0 +1,17 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-optimized" } */ + +int min_test(long a, long b, long c) { + int cmp1 = a < b; + int cmp2 = a < c; + return cmp1 & cmp2; +} + +int max_test (long a, long b, long c) { + int cmp1 = a > b; + int cmp2 = a > c; + return cmp1 & cmp2; +} + +/* { dg-final { scan-tree-dump "MIN_EXPR" 1 "optimized" } } */ +/* { dg-final { scan-tree-dump "MAX_EXPR" 1 "optimized" } } */ -- 1.9.1