From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 10881 invoked by alias); 14 Jan 2015 13:55:03 -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 10456 invoked by uid 89); 14 Jan 2015 13:54:57 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-2.2 required=5.0 tests=AWL,BAYES_00,FREEMAIL_FROM,RCVD_IN_DNSWL_LOW,SPF_PASS autolearn=ham version=3.3.2 X-HELO: mail-ob0-f173.google.com Received: from mail-ob0-f173.google.com (HELO mail-ob0-f173.google.com) (209.85.214.173) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (AES128-SHA encrypted) ESMTPS; Wed, 14 Jan 2015 13:54:52 +0000 Received: by mail-ob0-f173.google.com with SMTP id nt9so8025625obb.4 for ; Wed, 14 Jan 2015 05:54:50 -0800 (PST) MIME-Version: 1.0 X-Received: by 10.60.103.228 with SMTP id fz4mr2504617oeb.54.1421243690761; Wed, 14 Jan 2015 05:54:50 -0800 (PST) Received: by 10.76.69.196 with HTTP; Wed, 14 Jan 2015 05:54:50 -0800 (PST) In-Reply-To: <87sifdv9dk.fsf@rasmusvillemoes.dk> References: <877fwquwug.fsf@rasmusvillemoes.dk> <87sifdv9dk.fsf@rasmusvillemoes.dk> Date: Wed, 14 Jan 2015 14:01:00 -0000 Message-ID: Subject: Re: RFC: Two minor optimization patterns From: Richard Biener To: Rasmus Villemoes Cc: Andrew Pinski , GCC Patches Content-Type: text/plain; charset=UTF-8 X-IsSubscribed: yes X-SW-Source: 2015-01/txt/msg01057.txt.bz2 On Wed, Jan 14, 2015 at 1:23 PM, Rasmus Villemoes wrote: > On Wed, Jan 14 2015, Richard Biener wrote: > >> On Tue, Jan 13, 2015 at 11:47 PM, Andrew Pinski wrote: >>> On Tue, Jan 13, 2015 at 2:41 PM, Rasmus Villemoes wrote: >>>> [My first attempt at submitting a patch for gcc, so please forgive me >>>> if I'm not following the right protocol.] >>> >>> There are a few things missing. For one, a testcase or two for the >>> added optimizations. > > I'll see what I can come up with. Thanks for the pointers. > >>>> Sometimes rounding a variable to the next even integer is written x += x >>>> & 1. This usually means using an extra register (and hence at least an >>>> extra mov instruction) compared to the equivalent x = (x + 1) & ~1. The >>>> first pattern below tries to do this transformation. >>>> >>>> While playing with various ways of rounding down, I noticed that gcc >>>> already optimizes all of x-(x&3), x^(x&3) and x&~(x&3) to simply >>>> x&~3. >> >> Does it also handle x+(x&3)? > > I'm not sure what 'it' refers to, and I'm also not sure how you think > x+(x&3) could be rewritten. I was just guessing. >> Where does it handle x - (x&3)? > > If by 'it' you mean gcc, I tried looking for a pattern matching this, > but couldn't find it, so I don't know where it is handled. I can just > see by running gcc-5.0 -fdump-tree-original -O2 -c opt.c that "x - (x & > 3)" is rewritten as x & -4 (which is of course the same as x & ~3). That's done in fold-const.c:fold_binary_loc here: /* Fold A - (A & B) into ~B & A. */ if (!TREE_SIDE_EFFECTS (arg0) && TREE_CODE (arg1) == BIT_AND_EXPR) { ... (note that patterns are not fully moved to match.pd yet) > Btw, > I now see that neither x&~(x&3) or x&~(x&y) are rewritten that early, > but objdump -d shows that the end result is the same. > >> That is, doesn't the pattern also work for constants other than 1? > > Here I assume that 'the pattern' refers to the first pattern, and the > answer is 'not immediately'. To round up a number to the next multiple > of 2^k we need to add the negative of that number modulo 2^k. It just so > happens that for k=1 we have x==-x for both possible values of x. So > with a little tweak, this does in fact lead to an optimization > opportunity, namely x + ((-x) & m) -> (x + m) & ~m whenever m is one > less than a power of 2. I don't know how to check for m satisfying this > in the match.pd language. you'd need to write some C code involving trees in a if/with. We do have a integer_pow2p predicate but not a integer_one_less_than_pow2p one. > >> Please put it before the abs simplifications after the last one handing >> bit_and/bit_ior. > > OK, will do. Thanks, Richard. > Rasmus