On Mon, Mar 19, 2012 at 2:19 AM, Andrew Pinski <pins...@gmail.com> wrote: > On Sun, Mar 18, 2012 at 6:12 PM, William J. Schmidt > <wschm...@linux.vnet.ibm.com> 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 ... Bill, experimenting with pattern detection in eliminate () would be a possibility. Thanks, Richard. > Thanks, > Andrew pinski > > >> >> Thanks, >> Bill >> >> >> gcc: >> >> 2012-03-18 Bill Schmidt <wschm...@linux.vnet.ibm.com> >> >> * tree-pass.h (pass_strength_reduction): New decl. >> * tree-ssa-loop-ivopts.c (add_cost): Remove #undef; rename to >> add_regs_cost. >> (multiply_regs_cost): New function. >> (add_const_cost): Likewise. >> (extend_or_trunc_cost): Likewise. >> (negate_cost): Likewise. >> (get_address_cost): Rename add_cost to add_regs_cost. >> (force_expr_to_var_cost): Likewise. >> (get_computation_cost_at): Likewise. >> (determine_iv_cost): Likewise. >> * timevar.def (TV_TREE_SLSR): New timevar. >> * tree-ssa-strength-reduction.c: New. >> * tree-flow.h (add_regs_cost): New decl. >> (multiply_regs_cost): Likewise. >> (add_const_cost): Likewise. >> (extend_or_trunc_cost): Likewise. >> (negate_cost): Likewise. >> * Makefile.in (tree-ssa-strength-reduction.o): New dependencies. >> * passes.c (init_optimization_passes): Add pass_strength_reduction. >> >> gcc/testsuite: >> >> 2012-03-18 Bill Schmidt <wschm...@linux.vnet.ibm.com> >> >> * gcc.dg/tree-ssa/slsr-1.c: New test. >> * gcc.dg/tree-ssa/slsr-2.c: Likewise. >> * gcc.dg/tree-ssa/slsr-3.c: Likewise. >> * gcc.dg/tree-ssa/slsr-4.c: Likewise. >>
