[llvm-dev] [RFC] New pass: LoopExitValues
Hal Finkel via llvm-dev
llvm-dev at lists.llvm.org
Tue Sep 15 09:50:57 PDT 2015
----- 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
More information about the llvm-dev
mailing list