From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 67875 invoked by alias); 28 May 2015 12:37:17 -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 67857 invoked by uid 89); 28 May 2015 12:37:16 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-0.6 required=5.0 tests=AWL,BAYES_50,FREEMAIL_FROM,RCVD_IN_DNSWL_LOW,SPF_PASS autolearn=ham version=3.3.2 X-HELO: mail-oi0-f41.google.com Received: from mail-oi0-f41.google.com (HELO mail-oi0-f41.google.com) (209.85.218.41) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (AES128-GCM-SHA256 encrypted) ESMTPS; Thu, 28 May 2015 12:37:13 +0000 Received: by oifu123 with SMTP id u123so30946353oif.1 for ; Thu, 28 May 2015 05:37:11 -0700 (PDT) MIME-Version: 1.0 X-Received: by 10.202.228.71 with SMTP id b68mr2141208oih.58.1432816631697; Thu, 28 May 2015 05:37:11 -0700 (PDT) Received: by 10.76.115.167 with HTTP; Thu, 28 May 2015 05:37:11 -0700 (PDT) In-Reply-To: <20150528121545.GE27320@redhat.com> References: <20150528121545.GE27320@redhat.com> Date: Thu, 28 May 2015 13:16:00 -0000 Message-ID: Subject: Re: [PATCH] Optimize (CST1 << A) == CST2 (PR tree-optimization/66299) From: Richard Biener To: Marek Polacek Cc: GCC Patches Content-Type: text/plain; charset=UTF-8 X-IsSubscribed: yes X-SW-Source: 2015-05/txt/msg02634.txt.bz2 On Thu, May 28, 2015 at 2:15 PM, Marek Polacek wrote: > This PR points out that we weren't able to optimize 1 << x == 2 to just > x == 1. This is my attempt to fix that: if we see (CST1 << A) == CST2 > and CST2 is a multiple of CST1, use log2 to get rid of the shift, but > only if the result of the shift is a natural number (including zero). > > If CST2 is not a multiple of CST1, then the whole expression can be > discarded, but I'd like to do that as a follow-up. > (It would help if our current match.pd grammar allowed us to use "else", > any plans on doing that?) > > Bootstrapped/regtested on x86_64-linux, ok for trunk? > > 2015-05-28 Marek Polacek > > PR tree-optimization/66299 > * match.pd ((CST1 << A) == CST2 -> A == log2 (CST2 / CST1), > (CST1 << A) != CST2 -> A != log2 (CST2 / CST1)): New > patterns. > > * gcc.dg/pr66299-1.c: New test. > * gcc.dg/pr66299-2.c: New test. > > diff --git gcc/match.pd gcc/match.pd > index abd7851..5d07a70 100644 > --- gcc/match.pd > +++ gcc/match.pd > @@ -676,6 +676,19 @@ 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 == log2 (CST2 / CST1) > + (CST1 << A) != CST2 -> A != log2 (CST2 / CST1) > + if CST2 is a multiple of CST1. */ > +(for cmp (ne eq) > + (simplify > + (cmp (lshift@3 INTEGER_CST@0 @1) INTEGER_CST@2) > + (if ((TREE_CODE (@3) != SSA_NAME || has_single_use (@3)) I think we have the single_use (@3) helper now. Not sure why you restrict this here though - we are only creating new constants. Ok with dropping the single-use check. > + && wi::multiple_of_p (@2, @0, TYPE_SIGN (type))) > + (with { > + int shift = wi::exact_log2 (wi::div_trunc (@2, @0, TYPE_SIGN (type))); } > + (if (shift != -1) > + (cmp @1 { build_int_cst (TREE_TYPE (@1), shift); })))))) so with else you mean (if (shift != -1) ... (else-expr ...)) ? Sure that's possible. Today you can write (if (shift != -1) ...) (if (shift == -1) ...) or (if (shift != -1) ....) (else-expr) which is equivalent if the if is the only one at the nesting level and the then-expr doesn't contain any further ones. That is, it is equivalent to if () ...; else-expr; thus the fall-thru So (if ...) would get an optional else-expr, yes, that sounds useful. I think we already have some (if A ..) (if !A ..) in match.pd. Thanks, Richard. > + > /* 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..9d41275 100644 > --- gcc/testsuite/gcc.dg/pr66299-1.c > +++ gcc/testsuite/gcc.dg/pr66299-1.c > @@ -0,0 +1,83 @@ > +/* 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 (); > +} > + > +int > +main (void) > +{ > + test1 (1); > + test2 (2); > + test3 (4U); > + test4 (3U); > +} > + > +/* { dg-final { scan-tree-dump-not "<<" "original" } } */ > +/* { dg-final { cleanup-tree-dump "original" } } */ > diff --git gcc/testsuite/gcc.dg/pr66299-2.c gcc/testsuite/gcc.dg/pr66299-2.c > index e69de29..dde0549 100644 > --- gcc/testsuite/gcc.dg/pr66299-2.c > +++ gcc/testsuite/gcc.dg/pr66299-2.c > @@ -0,0 +1,34 @@ > +/* 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" } } */ > +/* { dg-final { cleanup-tree-dump "optimized" } } */ > > Marek