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

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

----- Original Message -----
> From: "Steve King" <steve at metrokings.com>
> To: "Wei Mi" <wmi at google.com>, "Hal Finkel"
<hfinkel at anl.gov>, "Philip Reames" <listmail at
philipreames.com>,
> "llvm-dev" <llvm-dev at lists.llvm.org>
> Sent: Wednesday, September 23, 2015 1:25:21 PM
> Subject: Re: [llvm-dev] [RFC] New pass: LoopExitValues
> 
> 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?
Sure; post the patch as you have it so we can look at what's going on.

 -Hal
> 
> Regards,
> -steve
> 
-- 
Hal Finkel
Assistant Computational Scientist
Leadership Computing Facility
Argonne National Laboratory

On Wed, Sep 23, 2015 at 12:00 PM, Hal Finkel <hfinkel at anl.gov>
wrote:
>>
>> Should we try the patch in it's current location, namely after LSR?
>
> Sure; post the patch as you have it so we can look at what's going on.
>
http://reviews.llvm.org/D12494

One particular point: The algorithm checks that SCEV's are equal when
their raw pointers are equal.  Is that a future-proof feature of
SCEVs?