From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 26010 invoked by alias); 21 Mar 2012 09:33:56 -0000 Received: (qmail 25999 invoked by uid 22791); 21 Mar 2012 09:33:55 -0000 X-SWARE-Spam-Status: No, hits=-2.3 required=5.0 tests=AWL,BAYES_00,DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FROM,RCVD_IN_DNSWL_LOW X-Spam-Check-By: sourceware.org Received: from mail-iy0-f175.google.com (HELO mail-iy0-f175.google.com) (209.85.210.175) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Wed, 21 Mar 2012 09:33:42 +0000 Received: by iaag37 with SMTP id g37so1391003iaa.20 for ; Wed, 21 Mar 2012 02:33:41 -0700 (PDT) MIME-Version: 1.0 Received: by 10.50.104.166 with SMTP id gf6mr2219424igb.35.1332322421398; Wed, 21 Mar 2012 02:33:41 -0700 (PDT) Received: by 10.42.140.196 with HTTP; Wed, 21 Mar 2012 02:33:41 -0700 (PDT) In-Reply-To: References: <1332119569.2725.17.camel@gnopaine> Date: Wed, 21 Mar 2012 09:33:00 -0000 Message-ID: Subject: Re: [PATCH] Straight line strength reduction, part 1 From: Richard Guenther To: Andrew Pinski Cc: "William J. Schmidt" , gcc-patches@gcc.gnu.org, bergner@vnet.ibm.com, rguenther@suse.de Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable X-IsSubscribed: yes 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/msg01417.txt.bz2 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. =A0I'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. =A0Replacement for candidates with fixed but >> unknown strides are not implemented herein, but that logic can be viewed >> in the larger patch. =A0This 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. =A0It 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 =3D i * 2; b =3D i * 3; c =3D i * 4; to transform it to a =3D i * 2; b =3D a + i; c =3D b + i; but already a =3D i * 2; b =3D i * 4; c =3D 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 ca= ses, 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 ... Bill, experimenting with pattern detection in eliminate () would be a possibility. Thanks, Richard. > Thanks, > Andrew pinski > > >> >> Thanks, >> Bill >> >> >> gcc: >> >> 2012-03-18 =A0Bill Schmidt =A0 >> >> =A0 =A0 =A0 =A0* tree-pass.h (pass_strength_reduction): New decl. >> =A0 =A0 =A0 =A0* tree-ssa-loop-ivopts.c (add_cost): Remove #undef; renam= e to >> =A0 =A0 =A0 =A0add_regs_cost. >> =A0 =A0 =A0 =A0(multiply_regs_cost): New function. >> =A0 =A0 =A0 =A0(add_const_cost): Likewise. >> =A0 =A0 =A0 =A0(extend_or_trunc_cost): Likewise. >> =A0 =A0 =A0 =A0(negate_cost): Likewise. >> =A0 =A0 =A0 =A0(get_address_cost): Rename add_cost to add_regs_cost. >> =A0 =A0 =A0 =A0(force_expr_to_var_cost): Likewise. >> =A0 =A0 =A0 =A0(get_computation_cost_at): Likewise. >> =A0 =A0 =A0 =A0(determine_iv_cost): Likewise. >> =A0 =A0 =A0 =A0* timevar.def (TV_TREE_SLSR): New timevar. >> =A0 =A0 =A0 =A0* tree-ssa-strength-reduction.c: New. >> =A0 =A0 =A0 =A0* tree-flow.h (add_regs_cost): New decl. >> =A0 =A0 =A0 =A0(multiply_regs_cost): Likewise. >> =A0 =A0 =A0 =A0(add_const_cost): Likewise. >> =A0 =A0 =A0 =A0(extend_or_trunc_cost): Likewise. >> =A0 =A0 =A0 =A0(negate_cost): Likewise. >> =A0 =A0 =A0 =A0* Makefile.in (tree-ssa-strength-reduction.o): New depend= encies. >> =A0 =A0 =A0 =A0* passes.c (init_optimization_passes): Add pass_strength_= reduction. >> >> gcc/testsuite: >> >> 2012-03-18 =A0Bill Schmidt =A0 >> >> =A0 =A0 =A0 =A0* gcc.dg/tree-ssa/slsr-1.c: New test. >> =A0 =A0 =A0 =A0* gcc.dg/tree-ssa/slsr-2.c: Likewise. >> =A0 =A0 =A0 =A0* gcc.dg/tree-ssa/slsr-3.c: Likewise. >> =A0 =A0 =A0 =A0* gcc.dg/tree-ssa/slsr-4.c: Likewise. >>