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

[Steve King via llvm-dev]

On Mon, Sep 21, 2015 at 11:13 AM, Wei Mi <wmi at google.com> wrote:
> Maybe it can follow the "Delete dead loops" pass which is after
> Induction Variable Simplification pass, so it will not affect existing
> exitvalue rewriting optimization in Induction Variable Simplification
> to find out and delete dead loops?
>
> Existing pass pipeline:
>         Loop-Closed SSA Form Pass
>         Loop Pass Manager
>           Induction Variable Simplification
>           Recognize loop idioms
>           Delete dead loops
>                                                            <=== New
> LoopExitValues
>         Function TargetTransformInfo
>         Loop Pass Manager
>           Unroll loops
>         Memory Dependence Analysis
>

I tried Wei's suggested location for the LEV pass shown above.
Placing the pass here fails to find any SCEV redundancy in the test
case because none exists yet.  The reason is that the relevant SCEV's
are off-by-1.  Some nitty-gritty:
In Pass N of the outer loop, the inner loop exits with %add = (N * %Size) - 1
To be useful, Pass N+1 of the outer loop needs some inner loop exit
value = (N * %Size).

This mismatch does not jibe with my previous IR hacking experiment.  I
tried the hack again and the assembly was not equivalent.  Somehow I
fooled myself before.

In the current patch, LEV runs after LSR and does find redundant
SCEVs.  Running the pass here would also mop up hypothetical SCEV
redundancy from any previous pass, but I understand the goal is to
avoid such redundancy in the first place.

Should we try the patch in it's current location, namely after LSR?

Regards,
-steve