This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: [PATCH][RFC][match.pd] optimize (X & C) == N when C is power of 2
- From: Segher Boessenkool <segher at kernel dot crashing dot org>
- To: Kyrill Tkachov <kyrylo dot tkachov at arm dot com>
- Cc: GCC Patches <gcc-patches at gcc dot gnu dot org>, Richard Biener <rguenther at suse dot de>
- Date: Mon, 27 Jul 2015 10:36:10 -0500
- Subject: Re: [PATCH][RFC][match.pd] optimize (X & C) == N when C is power of 2
- Authentication-results: sourceware.org; auth=none
- References: <55B1F2C3 dot 2000903 at arm dot com> <20150725021950 dot GA7309 at gate dot crashing dot org> <55B5E7A0 dot 7090202 at arm dot com>
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