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? Regards, -steve
Philip Reames via llvm-dev
2015-Sep-14 18:57 UTC
[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 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? Philip
----- Original Message -----> From: "Steve King" <steve at metrokings.com> > To: "Hal Finkel" <hfinkel at anl.gov> > Cc: "Gerolf Hoflehner" <ghoflehner at apple.com>, "llvm-dev" <llvm-dev at lists.llvm.org>, "Wei Mi" <wmi at google.com> > Sent: Monday, September 14, 2015 1:08:08 PM > Subject: Re: [llvm-dev] [RFC] New pass: LoopExitValues > > 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?IndVarSimplify deletes dead instructions, and then dead PHIs, but these depend on the in-this-case-temporary redundancy to trivialize dead loops (I assume that SimplifyCFG later removes the remaining now-empty loop blocks). -Hal> > Regards, > -steve >-- Hal Finkel Assistant Computational Scientist Leadership Computing Facility Argonne National Laboratory
----- 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
On Mon, Sep 14, 2015 at 11:57 AM, Philip Reames <listmail at philipreames.com> wrote:> 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.) >Assuming we should not interfere with the (hopefully) temporary redundancy created by IndVarSimplify, then why would the live range created here be of special concern vs. the live range of all the other variables in a given function?