From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 2321 invoked by alias); 21 Mar 2012 13:53:20 -0000 Received: (qmail 2311 invoked by uid 22791); 21 Mar 2012 13:53:16 -0000 X-SWARE-Spam-Status: No, hits=-5.8 required=5.0 tests=AWL,BAYES_00,RCVD_IN_DNSWL_HI,T_RP_MATCHES_RCVD X-Spam-Check-By: sourceware.org Received: from cantor2.suse.de (HELO mx2.suse.de) (195.135.220.15) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Wed, 21 Mar 2012 13:53:02 +0000 Received: from relay1.suse.de (unknown [195.135.220.254]) (using TLSv1 with cipher DHE-RSA-AES256-SHA (256/256 bits)) (No client certificate requested) by mx2.suse.de (Postfix) with ESMTP id CBCAC9735A; Wed, 21 Mar 2012 14:53:00 +0100 (CET) Date: Wed, 21 Mar 2012 13:53:00 -0000 From: Richard Guenther To: "William J. Schmidt" Cc: Richard Guenther , Andrew Pinski , gcc-patches@gcc.gnu.org, bergner@vnet.ibm.com Subject: Re: [PATCH] Straight line strength reduction, part 1 In-Reply-To: <1332337224.28560.34.camel@gnopaine> Message-ID: References: <1332119569.2725.17.camel@gnopaine> <1332337224.28560.34.camel@gnopaine> MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII 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 X-SW-Source: 2012-03/txt/msg01431.txt.bz2 On Wed, 21 Mar 2012, William J. Schmidt wrote: > On Wed, 2012-03-21 at 10:33 +0100, Richard Guenther wrote: > > On Mon, Mar 19, 2012 at 2:19 AM, Andrew Pinski wrote: > > > On Sun, Mar 18, 2012 at 6:12 PM, William J. Schmidt > > > wrote: > > >> Greetings, > > >> > > >> Now that we're into stage 1 again, I'd like to submit the first round of > > >> changes for dominator-based strength reduction, which will address > > >> issues from PR22586, PR35308, PR46556, and perhaps others. I'm > > >> attaching two patches: the smaller (slsr-part1) is the patch I'm > > >> submitting for approval today, while the larger (slsr-fyi) is for > > >> reference only, but may be useful if questions arise about how the small > > >> patch fits into the intended whole. > > >> > > >> This patch contains the logic for identifying strength reduction > > >> candidates, and makes replacements only for those candidates where the > > >> stride is a fixed constant. Replacement for candidates with fixed but > > >> unknown strides are not implemented herein, but that logic can be viewed > > >> in the larger patch. This patch does not address strength reduction of > > >> data reference expressions, or candidates with conditional increments; > > >> those issues will be dealt with in future patches. > > >> > > >> The cost model is built on the one used by tree-ssa-ivopts.c, and I've > > >> added some new instruction costs to that model in place. It might > > >> eventually be good to divorce that modeling code from IVOPTS, but that's > > >> an orthogonal patch and somewhat messy. > > > > > > I think this is the wrong way to do straight line strength reduction > > > considering we have a nice value numbering system which should be easy > > > to extended to support it. > > > > Well, it is easy to handle very specific easy cases like > > > > a = i * 2; > > b = i * 3; > > c = i * 4; > > > > to transform it to > > > > a = i * 2; > > b = a + i; > > c = b + i; > > > > but already > > > > a = i * 2; > > b = i * 4; > > c = i * 6; > > > > would need extra special code. The easy case could be handled in eliminate () > > by, when seeing A * CST, looking up A * (CST - 1) and if that > > succeeds, transform > > it to VAL + A. Cost issues are increasing the lifetime of VAL. I've done this > > simple case at some point, but it failed to handle the common associated cases, > > when we transform (a + 1) * 2, (a + 1) * 3, etc. to a * 2 + 2, a * 3 + > > 3, etc. I think > > it is the re-association in case of a strength-reduction opportunity > > that makes the > > separate pass better? How would you suggest handling this case in the > > VN framework? Detect the a * 3 + 3 pattern and then do two lookups, one for > > a * 2 and one for val + 2? But then we still don't have a value for a + 1 > > to re-use ... > > And it becomes even more difficult with more complex scenarios. > Consider: > > a = x + (3 * s); > b = x + (5 * s); > c = x + (7 * s); > > The framework I've developed recognizes that this group of instructions > is related, and that it is profitable to replace them as follows: > > a = x + (3 * s); > t = 2 * s; > b = a + t; > c = b + t; > > The introduced multiply by 2 (one shift) is far cheaper than the two > multiplies that it replaces. However, suppose you have instead: > > a = x + (2 * s); > b = x + (8 * s); > > Now it isn't profitable to replace this by: > > a = x + (2 * s); > t = 6 * s; > b = a + t; > > since a multiply by 6 (2 shifts, one add) is more costly than a multiply > by 8 (one shift). To make these decisions correctly requires analyzing > all the related statements together, which value numbering as it stands > is not equipped to do. Logic to handle these cases is included in my > larger "fyi" patch. > > As another example, consider conditionally-executed increments: > > a = i * 5; > if (...) > i = i + 1; > b = i * 5; > > This can be correctly and profitably strength-reduced as: > > a = i * 5; > t = a; > if (...) > { > i = i + 1; > t = t + 5; > } > b = t; > > (This is an approximation to the actual phi representation, which I've > omitted for clarity.) Again, this kind of analysis is not something > that fits naturally into value numbering. I don't yet have this in the > "fyi" patch, but have it largely working in a private version. > > My conclusion is that if strength reduction is done in value numbering, > it must either be a very limited form of strength reduction, or the kind > of logic I've developed that considers chains of related candidates > together must be "glued onto" value numbering. I think the latter would > be a mistake, as it would introduce much unnecessary complexity to what > is currently a very clean approach to PRE; the strength reduction would > become an ugly wart that people would complain about. I think it's far > cleaner to keep the two issues separate. I agree. > > > > Bill, experimenting with pattern detection in eliminate () would be a > > possibility. > > For the reasons expressed above, I don't think that would get very far > or make anyone very happy... > > I appreciate Andrew's view that value numbering is a logical place to do > strength reduction, but after considering the problem over the last few > months I have to disagree. If you don't mind, at this point I would > prefer to have my current patch considered on its merits. Yes, I plan to have a detailed look at it later and appreciate your work here. Thanks, Richard