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

[Philip Reames via llvm-dev]

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