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

[Bjarke Roune]

On Tue, Jun 30, 2015 at 10:54 PM, Adam Nemet <anemet at apple.com> wrote:

> Hi Bjarke,
>
> On Jun 30, 2015, at 6:16 PM, Bjarke Roune <broune at google.com> wrote:
>
> Hi Adam,
>
> Jingyue is right. We need to keep things in 32 bits because 64 bit
> arithmetic is more expensive and because one 64 bit register consumes two
> 32 bit registers.
>
> To add a bit more background: we would often emit worse code if we widened
> in indvars and then narrowed in the NVPTX backend later because we often
> would not be able to narrow AFAICT. Consider this general pattern where
> everything is 32 bit:
>
>   for (int i = a; i < b; i += s) {
>     // ...
>   }
>
> Suppose we widen i to be 64 bit:
>
>   for (int64 i = a; i < b; i += s) {
>     // ...
>   }
>
> As an example, suppose a = 0, b = INT_MAX, s = 2. The final value of i
> that makes the loop terminate would then be INT_MAX+1, so we cannot narrow
> i to 32 bits.
>
>
> Is the original program defined for s = 2 and b = INT_MAX?  Seems to me
> that last increment (INT_MAX - 1 + 2) before the exit condition should
> generate a poison?  (From the original post, it seemed you were assuming
> C/C++ overflow rules.)
>
> That's true, though that doesn't let us narrow because the narrowing pass
does not have information about the original program (though with an assume
intrinsic perhaps it could, but that again would require proving that
poison would lead to UB, since violating an assume is UB).

I'm assuming that we're translating from C into LLVM IR with the nsw flag
and then using LLVM's less strict rules for overflow. In the original loop,
it could be the case that s=2, b=INT_MAX, a=0, but then we could assume
that the effect of the poison/overflow that this creates is not externally
observable due to the 32 bit nsw on i += s. That makes it sound to widen.

Once we have widened, we lose some information. In particular, the nsw flag
on i += s is now a 64 bit nsw. So when we want to narrow back to 32 bit,
there is nothing that guarantees that the overflow that would be produced
by s=2, b=INT_MAX, a=0 could not be observed so narrowing is then unsound
from the perspective of the narrowing pass.

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