From patchwork Fri Jul 24 08:09:39 2015 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Kyrylo Tkachov X-Patchwork-Id: 499621 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]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 007A3140D19 for ; Fri, 24 Jul 2015 18:09:53 +1000 (AEST) Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.b=W3+VTMD8; dkim-atps=neutral DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender :message-id:date:from:mime-version:to:cc:subject:content-type; q=dns; s=default; b=qnm47ZARe6xSkQs/yBFV+gJXo4tMXugjSYWVtTgSJIe vmFfH2ZxfeRFFJUXZI/TFbDAFxFVEEuvbna7ylaSdkaR617Ej4RrL5pNsf/TmsSw 8eMch69D/I4GQd5m8M6EtZ745Oo94edVc04Fr5pPhMRWouiD9LWnvTy2n1Z9nBYM = DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender :message-id:date:from:mime-version:to:cc:subject:content-type; s=default; bh=nscaQanWLbF96rVp8mZlkFyFpSo=; b=W3+VTMD8qs8KB5dhH zJqhHb3rrk10q9rpvmJ6Ozw9T5KsboqlbHaC7zMCC0Y+FE8j8DMb/B2z3gcWnge3 aNGNogAB1Obh3Ev02hwIwtrjCqeaq0ewSXLpt9W9z+JCzflM5N/vhSA6zpDqldf4 bGlkxtcZNN5tFoOxzQ0tFcwSx8= Received: (qmail 54083 invoked by alias); 24 Jul 2015 08:09:47 -0000 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 Received: (qmail 54074 invoked by uid 89); 24 Jul 2015 08:09:47 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-1.7 required=5.0 tests=AWL, BAYES_00, SPF_PASS autolearn=ham version=3.3.2 X-HELO: eu-smtp-delivery-143.mimecast.com Received: from eu-smtp-delivery-143.mimecast.com (HELO eu-smtp-delivery-143.mimecast.com) (146.101.78.143) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Fri, 24 Jul 2015 08:09:45 +0000 Received: from cam-owa1.Emea.Arm.com (fw-tnat.cambridge.arm.com [217.140.96.140]) by eu-smtp-1.mimecast.com with ESMTP id uk-mta-35-br-4zqtYSqGmOn1Ra78D5A-1; Fri, 24 Jul 2015 09:09:39 +0100 Received: from [10.2.207.50] ([10.1.2.79]) by cam-owa1.Emea.Arm.com with Microsoft SMTPSVC(6.0.3790.3959); Fri, 24 Jul 2015 09:09:39 +0100 Message-ID: <55B1F2C3.2000903@arm.com> Date: Fri, 24 Jul 2015 09:09:39 +0100 From: Kyrill Tkachov User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:31.0) Gecko/20100101 Thunderbird/31.2.0 MIME-Version: 1.0 To: GCC Patches CC: Richard Biener Subject: [PATCH][RFC][match.pd] optimize (X & C) == N when C is power of 2 X-MC-Unique: br-4zqtYSqGmOn1Ra78D5A-1 X-IsSubscribed: yes Hi all, This transformation folds (X % C) == N into X & ((1 << (size - 1)) | (C - 1))) == N for constants C and N where N is positive and C is a power of 2. The idea is similar to the existing X % C -> X & (C - 1) transformation for unsigned values but this time when we have the comparison we use the C - 1 mask (all 1s for power of 2 N) orred with the sign bit. At runtime, if X is positive then X & ((1 << (size - 1)) | (C - 1))) calculates X % C, which is compared against the positive N. If X is negative then X & ((1 << (size - 1)) | (C - 1))) doesn't calculate X % C but since we also catch the set sign bit, it will never compare equal to N (which is positive), so we still get the right comparison result. I don't have much experience with writing match.pd patterns, so I appreciate any feedback on how to write this properly. Bootstrapped and tested on arm, aarch64, x86_64. Thanks, Kyrill 2015-07-24 Kyrylo Tkachov * match.pd ((X % C) == N -> (X & ((1 << (size - 1)) | (C - 1))) == N): Transform when N is positive and C is a power of 2. 2015-07-24 Kyrylo Tkachov * gcc.dg/fold-mod-cmp-1.c: New test. commit af785bad5cb32ef2bc35503ebbe65414b67ef8b1 Author: Kyrylo Tkachov Date: Tue Jul 14 18:20:28 2015 +0100 [match.pd] optimize (X & C) == N when C is power of 2 diff --git a/gcc/match.pd b/gcc/match.pd index 9cf0278..02ad708 100644 --- a/gcc/match.pd +++ b/gcc/match.pd @@ -266,7 +266,9 @@ along with GCC; see the file COPYING3. If not see /* Optimize TRUNC_MOD_EXPR by a power of two into a BIT_AND_EXPR, i.e. "X % C" into "X & (C - 1)", if X and C are positive. Also optimize A % (C << N) where C is a power of 2, - to A & ((C << N) - 1). */ + to A & ((C << N) - 1). + Optimize (X % C) == N into (X & ((1 << (size - 1)) | (C - 1))) == N + when C is signed, a power of 2 and N is positive. */ (match (power_of_two_cand @1) INTEGER_CST@1) (match (power_of_two_cand @1) @@ -278,7 +280,17 @@ along with GCC; see the file COPYING3. If not see || tree_expr_nonnegative_p (@0)) && tree_nop_conversion_p (type, TREE_TYPE (@3)) && integer_pow2p (@2) && tree_int_cst_sgn (@2) > 0) - (bit_and @0 (convert (minus @1 { build_int_cst (TREE_TYPE (@1), 1); })))))) + (bit_and @0 (convert (minus @1 { build_int_cst (TREE_TYPE (@1), 1); }))))) + + (simplify + (eq (mod @0 (INTEGER_CST@1)) INTEGER_CST@2) + (if (integer_pow2p (@1) && tree_expr_nonnegative_p (@2) + && tree_to_uhwi (@2) < tree_to_uhwi (@1)) + (eq (bit_and @0 + (bit_ior (minus @1 { build_int_cst (TREE_TYPE (@1), 1); }) + { build_int_cst (type, 1 << (tree_to_uhwi (TYPE_SIZE (type)) - 1)); }) + ) + @2)))) /* X % Y is smaller than Y. */ (for cmp (lt ge) diff --git a/gcc/testsuite/gcc.dg/fold-mod-cmp-1.c b/gcc/testsuite/gcc.dg/fold-mod-cmp-1.c new file mode 100644 index 0000000..9dcf313 --- /dev/null +++ b/gcc/testsuite/gcc.dg/fold-mod-cmp-1.c @@ -0,0 +1,12 @@ +/* { dg-do compile } */ +/* { dg-options "-fdump-tree-original" } */ + +int +modcmp (int a) +{ + return (a % 32) == 6; +} + +/* The above should be simplified to (a & -2147483617) == 6. */ +/* { dg-final { scan-tree-dump "& -2147483617" "original" } } */ +/* { dg-final { scan-tree-dump "== 6" "original" } } */