[llvm-dev] [RFC] New pass: LoopExitValues

[Hal Finkel via llvm-dev]

----- Original Message -----
> From: "Philip Reames" <listmail at philipreames.com>
> To: "Steve King" <steve at metrokings.com>, "Hal Finkel" <hfinkel at anl.gov>
> Cc: "llvm-dev" <llvm-dev at lists.llvm.org>, "Wei Mi" <wmi at google.com>
> Sent: Monday, September 14, 2015 1:57:06 PM
> Subject: Re: [llvm-dev] [RFC] New pass: LoopExitValues
> 
> On 09/14/2015 11:08 AM, Steve King via llvm-dev wrote:
> > On Fri, Sep 11, 2015 at 10:06 AM, Hal Finkel <hfinkel at anl.gov>
> > wrote:
> >> Also, if these redundant expressions involve induction variables,
> >> then that's something that the IndVarSimplify is already supposed
> >> to do, and if it is missing cases, then we should improve that
> >> pass (and, thus, folding what you've done into IndVarSimplify
> >> might be the right way to go).
> > Hal, thanks for the info.  Turns out IndVarSimplify intentionally
> > creates redundant calculation of loop exit values!
> >
> > //   2. Any use outside of the loop of an expression derived from
> > the indvar
> > //      is changed to compute the derived value outside of the
> > loop, eliminating
> > //      the dependence on the exit value of the induction variable.
> >  If the only
> > //      purpose of the loop is to compute the exit value of some
> > derived
> > //      expression, this transformation will make the loop dead.
> >
> > I understand the stated purpose for the redundancy, but there is no
> > mention of undoing the damage.  The LoopExitValues pass seems to be
> > exactly the cleanup that was missing.  Do passes coming after IVS
> > like
> > LSR need the redundant calculations in place to identify dead loops
> > or
> > should IVS have cleaned up after itself immediately?
> The basic idea of your proposed transform makes sense to me.
> Reversing
> the canonicalization above do remove redundant computation seems like
> a
> worthwhile goal.  However, your transformation would have the effect
> of
> increasing the live range of the variable in the loop and introducing
> an
> extra scheduling dependency.  I'm not entirely sure how that would
> work
> out in practice if the use outside the loop is a ways from the loop
> exit.  Have you given this any thought?  I suspect that the
> profitability heuristic would need tuning to get right (or at least
> not
> wrong for key cases.)

I agree with this, and I think we should pursue kind of cleanup being proposed. We might end up finding issues with live ranges, spilling, rematerialization, etc., but we'll deal with that if/when they come up. We might need to end up weighing the recomputation cost against the spill/reload cost.

> 
> I was also under the impression that LSR was supposed to catch
> exactly
> these type of cases.  It might be that your pass should be part of
> LSR
> instead.  Anyone with more knowledge of LSR (Andy, Sanjoy, Hal) have
> an
> opinion here?

I don't think it will do anything with exit values, and more generally, is concerned only with IV-users within a single loop (and maybe only pointer-typed ones?).

 -Hal

> 
> Philip
> 
> 
> 

-- 
Hal Finkel
Assistant Computational Scientist
Leadership Computing Facility
Argonne National Laboratory