From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 48740 invoked by alias); 9 Jun 2015 13:44:21 -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 48728 invoked by uid 89); 9 Jun 2015 13:44:20 -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,KAM_LAZY_DOMAIN_SECURITY,SPF_HELO_PASS,T_RP_MATCHES_RCVD autolearn=no version=3.3.2 X-HELO: mx1.redhat.com Received: from mx1.redhat.com (HELO mx1.redhat.com) (209.132.183.28) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (AES256-GCM-SHA384 encrypted) ESMTPS; Tue, 09 Jun 2015 13:44:19 +0000 Received: from int-mx09.intmail.prod.int.phx2.redhat.com (int-mx09.intmail.prod.int.phx2.redhat.com [10.5.11.22]) by mx1.redhat.com (Postfix) with ESMTPS id C1B53AB12E; Tue, 9 Jun 2015 13:44:17 +0000 (UTC) Received: from redhat.com (ovpn-204-44.brq.redhat.com [10.40.204.44]) by int-mx09.intmail.prod.int.phx2.redhat.com (8.14.4/8.14.4) with ESMTP id t59DiA8P005797 (version=TLSv1/SSLv3 cipher=AES256-SHA bits=256 verify=NO); Tue, 9 Jun 2015 09:44:13 -0400 Date: Tue, 09 Jun 2015 13:46:00 -0000 From: Marek Polacek To: Richard Biener Cc: Marc Glisse , Jakub Jelinek , GCC Patches , Richard Biener Subject: Re: [PATCH] Optimize (CST1 << A) == CST2 (PR tree-optimization/66299) Message-ID: <20150609134410.GT2756@redhat.com> References: <20150528121545.GE27320@redhat.com> <20150528123436.GM10247@tucnak.redhat.com> <20150608151055.GR2756@redhat.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: User-Agent: Mutt/1.5.23 (2014-03-12) X-SW-Source: 2015-06/txt/msg00674.txt.bz2 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? 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