[llvm-dev] RFC for a design change in LoopStrengthReduce / ScalarEvolution

[Hal Finkel via llvm-dev]

----- Original Message -----
> From: "Sanjoy Das" <sanjoy at playingwithpointers.com>
> To: "Hal Finkel" <hfinkel at anl.gov>
> Cc: "llvm-dev" <llvm-dev at lists.llvm.org>, "Andrew Trick" <atrick at apple.com>, "Quentin Colombet"
> <qcolombet at apple.com>, "Dan Gohman" <dan433584 at gmail.com>
> Sent: Tuesday, August 18, 2015 12:35:50 AM
> Subject: Re: [llvm-dev] RFC for a design change in LoopStrengthReduce / ScalarEvolution
> 
> > Of course, and the point is that, for example, on x86_64, the zext
> > here is free. I'm still trying to understand the problem...
> >
> > In the example you provided in your previous e-mail, we choose the
> > solution:
> >
> >   `GEP @Global, zext(V)` -> `GEP (@Global + zext VStart), {i64
> >   0,+,1}`
> >   `V` -> `trunc({i64 0,+,1}) + VStart`
> >
> > instead of the actually-better solution:
> >
> >   `GEP @Global, zext(V)` -> `GEP @Global, zext({VStart,+,1})`
> >   `V` -> `{VStart,+,1}`
> >
> > where LSR never considers the latter case because it transforms:
> >
> >   `zext({VStart,+,1})` to `{zext VStart,+,1}`
> >
> > and, thus, never considers the formula with zext on the outside?
> > Your proposed solution is that LSR should be able to create:
> >
> >   zext(opaque({VStart,+,1}))
> >
> > forcing it to keep all extensions as the outermost operators. Is
> > that right?
> 
> Yes, precisely.
> 
> > Will this interfere with SCEV's ability to prove wrapping
> > properties of those expressions? If so, does that matter?
> 
> SCEV won't be able (by design) to prove no-overflow for
> `opaque({VStart,+,1})` but it should still be able to prove no
> overflow for `{VStart,+,1}` as usual.
> 
> > Sure, but fixing LSR by creating a local-handicapping mechanism for
> > SCEV seems somehow unfortunate. Are we going to oscillate from
> > picking
> > from one part of the solution space to picking from a different
> > part,
> > without particular regard for which might be better?
> 
> While I found the SCEVOpaqueExpr idea easier to reason with, by no
> means am I suggesting that it is clearly the better solution.  :)
> 
> Would you rather this be solved fully within LSR instead?

I don't claim to understand LSR well enough to have an informed preference here, and of course, this might also depend on *how* you solve it in LSR. That having been said, in an abstract sense, solving the problem without blocking analysis within SCEV seems like something should at least be explored. Also, it seems like doing this in LSR can provide benefits the SCEV-based approach can't (but I could have misunderstood and the two proposed solutions search equivalent parts of the solution space).

Thanks again,
Hal

> 
> -- Sanjoy
> 

-- 
Hal Finkel
Assistant Computational Scientist
Leadership Computing Facility
Argonne National Laboratory