[LLVMdev] Deriving undefined behavior from nsw/inbounds/poison for scalar evolution

[Bjarke Roune]

Hi Andy, thanks for the feedback and background information.

On Wed, Jul 1, 2015 at 11:50 AM, Andrew Trick <atrick at apple.com> wrote:

> [...]
>
I think your approach to strengthening SCEV by using a poison value
> analysis is legitimate. I've considered this approach in the past. I do
> think that it adds complexity, but is probably the best way to reuse
> existing LSR. I can see a few alternatives to solving your problem:
>
> (1) Use poison value analysis to inform SCEV. SCEV now sees nsw flags on
> your recurrence and reduces the expression for you. LSR does the
> transformation you want.
>
> I'm leaning towards going with this as it should help LSR in other cases
too and LSR already has all the machinery, it just needs a bit more
information.

(2) Add nsw flags to the SCEV key so we don't need poison value analysis. I
> think this could be problematic, but if Sanjoy really wants to go this
> route and support the work I won't get in the way.
>
> It seems that no one is significantly preferring this approach.


> (3) Write a *simple* IR-level analysis that refactors address expressions
> to hoist the loop invariant component, informed by the target's addressing
> mode. This could be a first step in replacing the LSR pass with something
> more efficient and predictable. This is the approach I would take if I were
> doing the work. But I can understand not wanting to design a new pass just
> to handle your case.
>
> I see how that would work for ptr[i+offset], reassociating it to
(&ptr[offset])[i] and then hoisting &ptr[offset]. Here's another simple
case that should introduce a 64 bit pointer induction variable for &p[2*i],
while keeping i in 32 bits, but doesn't currently:

  for (int i = 0; i < N; ++i)
    p[2*i] = ...;

It's the same issue, just with nsw on 2*i instead of on an addition. There
may be some hoisting approach that works for this, and that also works if
it is x*i instead of 2*i for some loop-invariant x, though I don't see it
at the moment.

Bjarke
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20150701/e5b3c916/attachment.html>