llvm dev - Aug 2015 - RFC for a design change in LoopStrengthReduce / ScalarEvolution

> To back up for a second, how much of this is self-inflicted damage?
> IndVarSimplify likes to preemptively widen induction variables. Is
> that why you have the extensions here in the first place?
In the specific example I was talking about the zext came from our
frontend (our FE used to insert these extensions for reasons that are
no longer relevant).  But you can easily get the same behavior from an
expression like `a[(unsigned long)i]`.

This looked like a fairly straightforward LSR problem to me,
especially because SCEV already has all the smarts to infer the
required properties.  The only thing missing the right framing of the
problem (i.e. framing it in a way such that we can implement a
maintainable solution).

-- Sanjoy

----- 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: Monday, August 17, 2015 4:38:15 PM
> Subject: Re: [llvm-dev] RFC for a design change in LoopStrengthReduce /
ScalarEvolution
> 
> > To back up for a second, how much of this is self-inflicted damage?
> > IndVarSimplify likes to preemptively widen induction variables. Is
> > that why you have the extensions here in the first place?
> 
> In the specific example I was talking about the zext came from our
> frontend (our FE used to insert these extensions for reasons that are
> no longer relevant).  But you can easily get the same behavior from
> an
> expression like `a[(unsigned long)i]`.
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?
Will this interfere with SCEV's ability to prove wrapping properties of
those expressions? If so, does that matter?
> 
> This looked like a fairly straightforward LSR problem to me,
> especially because SCEV already has all the smarts to infer the
> required properties.  The only thing missing the right framing of the
> problem (i.e. framing it in a way such that we can implement a
> maintainable solution).
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?

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

> 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?

-- Sanjoy