From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 26204 invoked by alias); 27 Jul 2015 15:36: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 26191 invoked by uid 89); 27 Jul 2015 15:36:21 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-2.7 required=5.0 tests=AWL,BAYES_00,RP_MATCHES_RCVD,SPF_HELO_PASS,SPF_PASS autolearn=ham version=3.3.2 X-HELO: gate.crashing.org Received: from gate.crashing.org (HELO gate.crashing.org) (63.228.1.57) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (AES256-SHA encrypted) ESMTPS; Mon, 27 Jul 2015 15:36:19 +0000 Received: from gate.crashing.org (localhost.localdomain [127.0.0.1]) by gate.crashing.org (8.14.1/8.13.8) with ESMTP id t6RFaB4E029826; Mon, 27 Jul 2015 10:36:11 -0500 Received: (from segher@localhost) by gate.crashing.org (8.14.1/8.14.1/Submit) id t6RFaAQs029825; Mon, 27 Jul 2015 10:36:10 -0500 Date: Mon, 27 Jul 2015 15:54:00 -0000 From: Segher Boessenkool To: Kyrill Tkachov Cc: GCC Patches , Richard Biener Subject: Re: [PATCH][RFC][match.pd] optimize (X & C) == N when C is power of 2 Message-ID: <20150727153610.GA28606@gate.crashing.org> References: <55B1F2C3.2000903@arm.com> <20150725021950.GA7309@gate.crashing.org> <55B5E7A0.7090202@arm.com> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <55B5E7A0.7090202@arm.com> User-Agent: Mutt/1.4.2.3i X-IsSubscribed: yes X-SW-Source: 2015-07/txt/msg02271.txt.bz2 On Mon, Jul 27, 2015 at 09:11:12AM +0100, Kyrill Tkachov wrote: > On 25/07/15 03:19, Segher Boessenkool wrote: > >On Fri, Jul 24, 2015 at 09:09:39AM +0100, Kyrill Tkachov wrote: > >>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. > >For N = 0 you can transform it to > > > > ((unsigned)X % C) == N > > > >and for 0 < N < C you can transform it to > > > > X > 0 && ((unsigned)X % C) == N (or X >= 0) > > > >and for -C < N < 0 it is > > > > X < 0 && ((unsigned)X % C) == N + C (or X <= 0) > > > >and for other N it is > > > > 0. > > > >For N not a constant, well, do you really care? :-) > > > >(That second case might eventually fold to your original expression). > > Yeah, these avoid the potentially expensive mask, Fun fact: the current code ends up using the exact same mask, for some targets. > but introduce more operations, > which I believe may not be desirable at this stage. It is getting rid of the (expensive) division/modulo. In many cases it could get rid of the sign test, or hoist it to some outer structure, hard to test here though (at least, I have no idea how to do that). > Unless these transformations are ok for match.pd I'll try to implement this > transformation > at RTL expansion time. If you have to do conditional jumps, the RTL optimisers will not be able to do very much :-( Segher