From patchwork Tue Oct 19 09:43:40 2010 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Dmitry Melnik X-Patchwork-Id: 68294 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]) by ozlabs.org (Postfix) with SMTP id 002DFB70DC for ; Tue, 19 Oct 2010 20:43:55 +1100 (EST) Received: (qmail 19042 invoked by alias); 19 Oct 2010 09:43:53 -0000 Received: (qmail 18846 invoked by uid 22791); 19 Oct 2010 09:43:51 -0000 X-SWARE-Spam-Status: No, hits=-1.0 required=5.0 tests=AWL, BAYES_00, T_RP_MATCHES_RCVD X-Spam-Check-By: sourceware.org Received: from smtp.ispras.ru (HELO smtp.ispras.ru) (83.149.198.201) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Tue, 19 Oct 2010 09:43:44 +0000 Received: from ispserv.ispras.ru (ispserv.ispras.ru [83.149.198.72]) by smtp.ispras.ru (Postfix) with ESMTP id 84F135D4082; Tue, 19 Oct 2010 13:41:40 +0400 (MSD) Received: from [10.10.3.58] (winnie.ispras.ru [83.149.198.236]) by ispserv.ispras.ru (Postfix) with ESMTP id 7F4EB3FC48; Tue, 19 Oct 2010 13:43:41 +0400 (MSD) Message-ID: <4CBD684C.9020208@ispras.ru> Date: Tue, 19 Oct 2010 13:43:40 +0400 From: Dmitry Melnik User-Agent: Mozilla/5.0 (X11; U; Linux x86_64; en-US; rv:1.9.1.10) Gecko/20100528 Thunderbird/3.0.5 MIME-Version: 1.0 To: gcc-patches@gcc.gnu.org CC: jakub@redhat.com, rth@redhat.com Subject: Re: [PATCH] Fold integer divisions to arithmetic shifts References: <4CB7289A.7080608@ispras.ru> <20101014163208.GQ2082@tyan-ft48-01.lab.bos.redhat.com> In-Reply-To: <20101014163208.GQ2082@tyan-ft48-01.lab.bos.redhat.com> 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 On 10/14/2010 08:32 PM, Jakub Jelinek wrote: > Consider > long long x = foo (); > x = (x & -0x200000000LL) / 0x200000000LL; > The above code would optimize this as > x = x >> -1; > on 32-bit HWI targets. Also, I think checking that arg1 is actually > INTEGER_CST would be desirable too (integer_pow2p can return true > even for COMPLEX_CST and then tree_int_cst_sgn accesses something the > COMPLEX_CST doesn't have). I've modified the patch similarly to http://gcc.gnu.org/ml/gcc-patches/2010-10/msg01282.html, added check for INTEGER_CST, and modified test to check for shift operation in 'optimized' dump. Bootstrapped and regtested on x86_64 and i686. Ok now? --- Best regards, Dmitry 2010-10-13 Dmitry Melnik gcc/ * fold-const.c (fold_binary_loc): New transformation. gcc/testsuite/ * gcc.dg/20101013-1.c: New test. diff --git a/gcc/fold-const.c b/gcc/fold-const.c index 8146920..80fb248 100644 --- a/gcc/fold-const.c +++ b/gcc/fold-const.c @@ -11599,6 +11599,31 @@ fold_binary_loc (location_t loc, return NULL_TREE; case TRUNC_DIV_EXPR: + /* Optimize (X & (-A)) / A where A is a power of 2, + to X >> log2(A) */ + if (TREE_CODE (arg0) == BIT_AND_EXPR + && !TYPE_UNSIGNED (type) && TREE_CODE (arg1) == INTEGER_CST + && integer_pow2p (arg1) && tree_int_cst_sgn (arg1) > 0) + { + tree sum = fold_binary_loc (loc, PLUS_EXPR, TREE_TYPE (arg1), + arg1, TREE_OPERAND (arg0, 1)); + if (sum && integer_zerop (sum)) { + unsigned long pow2; + + if (TREE_INT_CST_LOW (arg1)) + pow2 = exact_log2 (TREE_INT_CST_LOW (arg1)); + else + pow2 = exact_log2 (TREE_INT_CST_HIGH (arg1)) + + HOST_BITS_PER_WIDE_INT; + + return fold_build2_loc (loc, RSHIFT_EXPR, type, + TREE_OPERAND (arg0, 0), + build_int_cst (NULL_TREE, pow2)); + } + } + + /* Fall thru */ + case FLOOR_DIV_EXPR: /* Simplify A / (B << N) where A and B are positive and B is a power of 2, to A >> (N + log2(B)). */ diff --git a/gcc/testsuite/gcc.dg/20101013-1.c b/gcc/testsuite/gcc.dg/20101013-1.c new file mode 100644 index 0000000..b5bd3a7 --- /dev/null +++ b/gcc/testsuite/gcc.dg/20101013-1.c @@ -0,0 +1,11 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-optimized" } */ + +int foo(int a) +{ + int x = (a & (~15)) / 16; + return x; +} + +/* { dg-final { scan-tree-dump ">>" "optimized" } } */ +/* { dg-final { cleanup-tree-dump "optimized" } } */