From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 38491 invoked by alias); 9 Jun 2015 14:06:58 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Received: (qmail 38279 invoked by uid 89); 9 Jun 2015 14:06:57 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-1.3 required=5.0 tests=AWL,BAYES_50,KAM_LAZY_DOMAIN_SECURITY,T_RP_MATCHES_RCVD autolearn=no version=3.3.2 X-HELO: mx2.suse.de Received: from cantor2.suse.de (HELO mx2.suse.de) (195.135.220.15) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (CAMELLIA256-SHA encrypted) ESMTPS; Tue, 09 Jun 2015 14:06:47 +0000 Received: from relay1.suse.de (charybdis-ext.suse.de [195.135.220.254]) by mx2.suse.de (Postfix) with ESMTP id 0E125AC8A; Tue, 9 Jun 2015 14:06:44 +0000 (UTC) Date: Tue, 09 Jun 2015 14:11:00 -0000 From: Richard Biener To: Marek Polacek cc: Richard Biener , Marc Glisse , Jakub Jelinek , GCC Patches Subject: Re: [PATCH] Optimize (CST1 << A) == CST2 (PR tree-optimization/66299) In-Reply-To: <20150609134410.GT2756@redhat.com> Message-ID: References: <20150528121545.GE27320@redhat.com> <20150528123436.GM10247@tucnak.redhat.com> <20150608151055.GR2756@redhat.com> <20150609134410.GT2756@redhat.com> User-Agent: Alpine 2.11 (LSU 23 2013-08-11) MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII X-SW-Source: 2015-06/txt/msg00678.txt.bz2 On Tue, 9 Jun 2015, Marek Polacek wrote: > On Tue, Jun 09, 2015 at 09:53:21AM +0200, Richard Biener wrote: > > >> +/* (CST1 << A) == CST2 -> A == ctz (CST2) - ctz (CST1) > > >> + (CST1 << A) != CST2 -> A != ctz (CST2) - ctz (CST1) > > >> + if CST2 != 0. */ > > >> +(for cmp (ne eq) > > >> + (simplify > > >> + (cmp (lshift INTEGER_CST@0 @1) INTEGER_CST@2) > > >> + (with { > > >> + unsigned int cand = wi::ctz (@2) - wi::ctz (@0); } > > >> + (if (!integer_zerop (@2) > > > > > > > > > You can probably use directly wi::ne_p (@2, 0) here. Shouldn't this be > > > indented one space more? > > > > Yes, one space more. I suppose using integer_zerop might in theory > > allow for handling vector shifts at some point ...? > > Fixed the formatting. But I kept the integer_zerop. > > > >> + && wi::eq_p (wi::lshift (@0, cand), @2)) > > >> + (cmp @1 { build_int_cst (TREE_TYPE (@1), cand); }))))) > > > > > > > > > Making 'cand' signed, you could return 0 when cand<0, like (2< > > could also return 0 when the candidate turns out not to work: (3< > > > Sounds like a good improvement. > > Yeah, it makes sense to do that while I'm on this. Done, and a new > test added. > > > Otherwise the patch looks ok to me as well - mind doing the improvement above? > > Thank you both. How does this look now? > > Bootstrapped/regtested on x86_64-linux, ok for trunk? Ok. Thanks, Richard. > 2015-06-09 Marek Polacek > > PR tree-optimization/66299 > * match.pd ((CST1 << A) == CST2 -> A == ctz (CST2) - ctz (CST1) > ((CST1 << A) != CST2 -> A != ctz (CST2) - ctz (CST1)): New > patterns. > > * gcc.dg/pr66299-1.c: New test. > * gcc.dg/pr66299-2.c: New test. > * gcc.dg/pr66299-3.c: New test. > > diff --git gcc/match.pd gcc/match.pd > index abd7851..560b218 100644 > --- gcc/match.pd > +++ gcc/match.pd > @@ -676,6 +676,21 @@ along with GCC; see the file COPYING3. If not see > (cmp (bit_and (lshift integer_onep @0) integer_onep) integer_zerop) > (icmp @0 { build_zero_cst (TREE_TYPE (@0)); }))) > > +/* (CST1 << A) == CST2 -> A == ctz (CST2) - ctz (CST1) > + (CST1 << A) != CST2 -> A != ctz (CST2) - ctz (CST1) > + if CST2 != 0. */ > +(for cmp (ne eq) > + (simplify > + (cmp (lshift INTEGER_CST@0 @1) INTEGER_CST@2) > + (with { int cand = wi::ctz (@2) - wi::ctz (@0); } > + (if (cand < 0 > + || (!integer_zerop (@2) > + && wi::ne_p (wi::lshift (@0, cand), @2))) > + { constant_boolean_node (cmp == NE_EXPR, type); }) > + (if (!integer_zerop (@2) > + && wi::eq_p (wi::lshift (@0, cand), @2)) > + (cmp @1 { build_int_cst (TREE_TYPE (@1), cand); }))))) > + > /* Simplifications of conversions. */ > > /* Basic strip-useless-type-conversions / strip_nops. */ > diff --git gcc/testsuite/gcc.dg/pr66299-1.c gcc/testsuite/gcc.dg/pr66299-1.c > index e69de29..e75146b 100644 > --- gcc/testsuite/gcc.dg/pr66299-1.c > +++ gcc/testsuite/gcc.dg/pr66299-1.c > @@ -0,0 +1,92 @@ > +/* PR tree-optimization/66299 */ > +/* { dg-do run } */ > +/* { dg-options "-fdump-tree-original" } */ > + > +void > +test1 (int x) > +{ > + if ((0 << x) != 0 > + || (1 << x) != 2 > + || (2 << x) != 4 > + || (3 << x) != 6 > + || (4 << x) != 8 > + || (5 << x) != 10 > + || (6 << x) != 12 > + || (7 << x) != 14 > + || (8 << x) != 16 > + || (9 << x) != 18 > + || (10 << x) != 20) > + __builtin_abort (); > +} > + > +void > +test2 (int x) > +{ > + if (!((0 << x) == 0 > + && (1 << x) == 4 > + && (2 << x) == 8 > + && (3 << x) == 12 > + && (4 << x) == 16 > + && (5 << x) == 20 > + && (6 << x) == 24 > + && (7 << x) == 28 > + && (8 << x) == 32 > + && (9 << x) == 36 > + && (10 << x) == 40)) > + __builtin_abort (); > +} > + > +void > +test3 (unsigned int x) > +{ > + if ((0U << x) != 0U > + || (1U << x) != 16U > + || (2U << x) != 32U > + || (3U << x) != 48U > + || (4U << x) != 64U > + || (5U << x) != 80U > + || (6U << x) != 96U > + || (7U << x) != 112U > + || (8U << x) != 128U > + || (9U << x) != 144U > + || (10U << x) != 160U) > + __builtin_abort (); > +} > + > +void > +test4 (unsigned int x) > +{ > + if (!((0U << x) == 0U > + || (1U << x) == 8U > + || (2U << x) == 16U > + || (3U << x) == 24U > + || (4U << x) == 32U > + || (5U << x) == 40U > + || (6U << x) == 48U > + || (7U << x) == 56U > + || (8U << x) == 64U > + || (9U << x) == 72U > + || (10U << x) == 80U)) > + __builtin_abort (); > +} > + > +void > +test5 (int x) > +{ > + if ((0 << x) == 1 > + || (0 << x) != 0 > + || (0x8001U << x) != 0x20000U) > + __builtin_abort (); > +} > + > +int > +main (void) > +{ > + test1 (1); > + test2 (2); > + test3 (4U); > + test4 (3U); > + test5 (17); > +} > + > +/* { dg-final { scan-tree-dump-not "<<" "original" } } */ > diff --git gcc/testsuite/gcc.dg/pr66299-2.c gcc/testsuite/gcc.dg/pr66299-2.c > index e69de29..45e9218 100644 > --- gcc/testsuite/gcc.dg/pr66299-2.c > +++ gcc/testsuite/gcc.dg/pr66299-2.c > @@ -0,0 +1,33 @@ > +/* PR tree-optimization/66299 */ > +/* { dg-do run } */ > +/* { dg-options "-fdump-tree-optimized -O" } */ > + > +void > +test1 (int x, unsigned u) > +{ > + if ((1U << x) != 64 > + || (2 << x) != u > + || (x << x) != 384 > + || (3 << x) == 9 > + || (x << 14) != 98304U > + || (1 << x) == 14 > + || (3 << 2) != 12) > + __builtin_abort (); > +} > + > +void > +test2 (int x) > +{ > + unsigned int t = ((unsigned int) 1U << x); > + if (t != 2U) > + __builtin_abort (); > +} > + > +int > +main (void) > +{ > + test1 (6, 128U); > + test2 (1); > +} > + > +/* { dg-final { scan-tree-dump-not "<<" "optimized" } } */ > diff --git gcc/testsuite/gcc.dg/pr66299-3.c gcc/testsuite/gcc.dg/pr66299-3.c > index e69de29..ffee049 100644 > --- gcc/testsuite/gcc.dg/pr66299-3.c > +++ gcc/testsuite/gcc.dg/pr66299-3.c > @@ -0,0 +1,68 @@ > +/* PR tree-optimization/66299 */ > +/* { dg-do run } */ > +/* { dg-options "-fdump-tree-original" } */ > + > +void __attribute__ ((noinline, noclone)) > +test1 (int x) > +{ > + if ((2 << x) == 1 > + || (8 << x) == 1 > + || (8 << x) == 2 > + || (3072 << x) == 3 > + || (294912 << x) == 9 > + || (45056 << x) == 11 > + || (2176 << x) == 17) > + __builtin_abort (); > +} > + > +void __attribute__ ((noinline, noclone)) > +test2 (int x) > +{ > + if ((2 << x) != 1 > + && (8 << x) != 1 > + && (8 << x) != 2 > + && (3072 << x) != 3 > + && (294912 << x) != 9 > + && (45056 << x) != 11 > + && (2176 << x) != 17) > + ; > + else > + __builtin_abort (); > +} > + > +void __attribute__ ((noinline, noclone)) > +test3 (int x) > +{ > + if ((3 << x) == 4 > + || (1 << x) == 12 > + || (40 << x) == 1024 > + || (2 << x) == 84 > + || (3 << x) == 16384 > + || (10 << x) == 6144) > + __builtin_abort (); > +} > + > +void __attribute__ ((noinline, noclone)) > +test4 (int x) > +{ > + if ((3 << x) != 4 > + && (1 << x) != 12 > + && (40 << x) != 1024 > + && (2 << x) != 84 > + && (3 << x) != 16384 > + && (10 << x) != 6144) > + ; > + else > + __builtin_abort (); > +} > + > +int > +main (void) > +{ > + test1 (0); > + test2 (1); > + test3 (1); > + test4 (2); > +} > + > +/* { dg-final { scan-tree-dump-not "(<<|==|!=)" "original" } } */ > > Marek > > -- Richard Biener SUSE LINUX GmbH, GF: Felix Imendoerffer, Jane Smithard, Dilip Upmanyu, Graham Norton, HRB 21284 (AG Nuernberg)