llvm dev - Jul 2015 - [LLVMdev] extractelement causes memory access violation - what to do?

On Tue, Jun 30, 2015 at 11:03 PM Hal Finkel <hfinkel at anl.gov> wrote:
> ----- Original Message -----
> > From: "Paweł Bylica" <chfast at gmail.com>
> > To: "David Majnemer" <david.majnemer at gmail.com>
> > Cc: "LLVMdev" <llvmdev at cs.uiuc.edu>
> > Sent: Tuesday, June 30, 2015 5:42:24 AM
> > Subject: Re: [LLVMdev] extractelement causes memory access violation -
> what   to do?
> >
> >
> >
> >
> >
> > On Fri, Jun 26, 2015 at 5:42 PM David Majnemer <
> > david.majnemer at gmail.com > wrote:
> >
> >
> >
> >
> >
> > On Fri, Jun 26, 2015 at 7:00 AM, Paweł Bylica < chfast at gmail.com
>
> > wrote:
> >
> >
> >
> > Hi,
> >
> >
> > Let's have a simple program:
> >
> > define i32 @main(i32 %n, i64 %idx) {
> > %idxSafe = trunc i64 %idx to i5
> > %r = extractelement <4 x i32> <i32 -1, i32 -1, i32 -1, i32
-1>, i64
> > %idx
> > ret i32 %r
> > }
> >
> >
> > The assembly of that would be:
> >
> > pcmpeqd %xmm0, %xmm0
> > movdqa %xmm0, -24(%rsp)
> > movl -24(%rsp,%rsi,4), %eax
> > retq
> >
> >
> > The language reference states that the extractelement instruction
> > produces undefined value in case the index argument is invalid (our
> > case). But the implementation simply dumps the vector to the stack
> > memory, calculates the memory offset out of the index value and
> > tries to access the memory. That causes the crash.
> >
> >
> > The workaround is to trunc the index value before extractelement (see
> > %idxSafe). But what should be the ultimate solution?
> >
> >
> >
> >
> >
> > We could fix this by specifying that out of bounds access on an
> > extractelement leads to full-on undefined behavior, no need to force
> > everyone to eat the cost of a mask.
> >
> >
> > I don't have preference for any of the solutions.
> >
> >
> > I have a side question. It is not stated explicitly in the reference
> > but I would assume the index of extractelement is processed as an
> > unsigned value. However, the DAG Builder extends the index with
> > sext. Is it correct?
>
> Hrmm. Given that only (small) positive numbers are valid, it shouldn't
> matter. Unless we can find a reason that it works better to be sext, it
> seems conceptually cleaner to make it zext.
>
I have tried to change it to zext. 2 Mips test have failed. I haven't
checked the details though.
sext looks pretty wrong to me because i5 -1 does not mean 31 any more.

- PB

>
>  -Hal
>
> >
> >
> > - PB
> > _______________________________________________
> > LLVM Developers mailing list
> > LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
> >
>
> --
> Hal Finkel
> Assistant Computational Scientist
> Leadership Computing Facility
> Argonne National Laboratory
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150630/e93e7658/attachment.html>

Sorry for chiming in so late in this.

So I agree that negative indices are UB, I don’t think thats contentious.

However, I think the issue here is the DAG expansion.  That is the point at
which we go from UB which would just be hidden in the instruction to something
which can crash.  I think its at that point where we should mask to ensure that
the in memory expansion doesn’t read out of bounds.  On architectures which do
the variable extract in an instruction, they won’t be penalized by a mask, only
the memory expansion will be which should be rarer,

The point about speculation at the IR level is interesting.  Personally i’m ok
with constant indices being speculated and variable not.  If we later want to
find a good way to ask TTI whether a variable extract is cheap then we can find
a way to do so.

Anyway, just my 2c.

Cheers,
Pete
> On Jun 30, 2015, at 2:07 PM, Paweł Bylica <chfast at gmail.com>
wrote:
> 
> On Tue, Jun 30, 2015 at 11:03 PM Hal Finkel <hfinkel at anl.gov
<mailto:hfinkel at anl.gov>> wrote:
> ----- Original Message -----
> > From: "Paweł Bylica" <chfast at gmail.com
<mailto:chfast at gmail.com>>
> > To: "David Majnemer" <david.majnemer at gmail.com
<mailto:david.majnemer at gmail.com>>
> > Cc: "LLVMdev" <llvmdev at cs.uiuc.edu <mailto:llvmdev
at cs.uiuc.edu>>
> > Sent: Tuesday, June 30, 2015 5:42:24 AM
> > Subject: Re: [LLVMdev] extractelement causes memory access violation -
what   to do?
> >
> >
> >
> >
> >
> > On Fri, Jun 26, 2015 at 5:42 PM David Majnemer <
> > david.majnemer at gmail.com <mailto:david.majnemer at gmail.com>
> wrote:
> >
> >
> >
> >
> >
> > On Fri, Jun 26, 2015 at 7:00 AM, Paweł Bylica < chfast at gmail.com
<mailto:chfast at gmail.com> >
> > wrote:
> >
> >
> >
> > Hi,
> >
> >
> > Let's have a simple program:
> >
> > define i32 @main(i32 %n, i64 %idx) {
> > %idxSafe = trunc i64 %idx to i5
> > %r = extractelement <4 x i32> <i32 -1, i32 -1, i32 -1, i32
-1>, i64
> > %idx
> > ret i32 %r
> > }
> >
> >
> > The assembly of that would be:
> >
> > pcmpeqd %xmm0, %xmm0
> > movdqa %xmm0, -24(%rsp)
> > movl -24(%rsp,%rsi,4), %eax
> > retq
> >
> >
> > The language reference states that the extractelement instruction
> > produces undefined value in case the index argument is invalid (our
> > case). But the implementation simply dumps the vector to the stack
> > memory, calculates the memory offset out of the index value and
> > tries to access the memory. That causes the crash.
> >
> >
> > The workaround is to trunc the index value before extractelement (see
> > %idxSafe). But what should be the ultimate solution?
> >
> >
> >
> >
> >
> > We could fix this by specifying that out of bounds access on an
> > extractelement leads to full-on undefined behavior, no need to force
> > everyone to eat the cost of a mask.
> >
> >
> > I don't have preference for any of the solutions.
> >
> >
> > I have a side question. It is not stated explicitly in the reference
> > but I would assume the index of extractelement is processed as an
> > unsigned value. However, the DAG Builder extends the index with
> > sext. Is it correct?
> 
> Hrmm. Given that only (small) positive numbers are valid, it shouldn't
matter. Unless we can find a reason that it works better to be sext, it seems
conceptually cleaner to make it zext.
> 
> I have tried to change it to zext. 2 Mips test have failed. I haven't
checked the details though.
> sext looks pretty wrong to me because i5 -1 does not mean 31 any more.
> 
> - PB
>  
> 
>  -Hal
> 
> >
> >
> > - PB
> > _______________________________________________
> > LLVM Developers mailing list
> > LLVMdev at cs.uiuc.edu <mailto:LLVMdev at cs.uiuc.edu>        
http://llvm.cs.uiuc.edu <http://llvm.cs.uiuc.edu/>
> > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
<http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev>
> >
> 
> --
> Hal Finkel
> Assistant Computational Scientist
> Leadership Computing Facility
> Argonne National Laboratory
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150701/0da5432c/attachment.html>

----- Original Message -----
> From: "Pete Cooper" <peter_cooper at apple.com>
> To: "Paweł Bylica" <chfast at gmail.com>
> Cc: "Hal Finkel" <hfinkel at anl.gov>, "LLVMdev"
<llvmdev at cs.uiuc.edu>
> Sent: Wednesday, July 1, 2015 12:08:37 PM
> Subject: Re: [LLVMdev] extractelement causes memory access violation - what
to do?
> 
> Sorry for chiming in so late in this.
> 
> So I agree that negative indices are UB, I don’t think thats
> contentious.
> 
> However, I think the issue here is the DAG expansion. That is the
> point at which we go from UB which would just be hidden in the
> instruction to something which can crash. I think its at that point
> where we should mask to ensure that the in memory expansion doesn’t
> read out of bounds. On architectures which do the variable extract
> in an instruction, they won’t be penalized by a mask,
Why do you feel that they won't be penalized by the mask? Or are you
assuming will adjust the patterns to match the index plus the mask?
> only the
> memory expansion will be which should be rarer,
On some architectures expansion in memory is not particularly expensive because
they have very good store-to-load forwarding. Adding additional masking
instructions into the critical path of correct code will not be a welcome
change.
> 
> The point about speculation at the IR level is interesting.
> Personally i’m ok with constant indices being speculated and
> variable not. If we later want to find a good way to ask TTI whether
> a variable extract is cheap then we can find a way to do so.
It is not about expense, it is about not introducing UB when speculating the
instruction.

 -Hal
> 
> Anyway, just my 2c.
> 
> 
> Cheers,
> Pete
> 
> 
> 
> 
> On Jun 30, 2015, at 2:07 PM, Paweł Bylica < chfast at gmail.com >
wrote:
> 
> 
> 
> 
> On Tue, Jun 30, 2015 at 11:03 PM Hal Finkel < hfinkel at anl.gov >
> wrote:
> 
> 
> ----- Original Message -----
> > From: "Paweł Bylica" < chfast at gmail.com >
> > To: "David Majnemer" < david.majnemer at gmail.com >
> > Cc: "LLVMdev" < llvmdev at cs.uiuc.edu >
> > Sent: Tuesday, June 30, 2015 5:42:24 AM
> > Subject: Re: [LLVMdev] extractelement causes memory access
> > violation - what to do?
> > 
> > 
> > 
> > 
> > 
> > On Fri, Jun 26, 2015 at 5:42 PM David Majnemer <
> > david.majnemer at gmail.com > wrote:
> > 
> > 
> > 
> > 
> > 
> > On Fri, Jun 26, 2015 at 7:00 AM, Paweł Bylica < chfast at gmail.com
>
> > wrote:
> > 
> > 
> > 
> > Hi,
> > 
> > 
> > Let's have a simple program:
> > 
> > define i32 @main(i32 %n, i64 %idx) {
> > %idxSafe = trunc i64 %idx to i5
> > %r = extractelement <4 x i32> <i32 -1, i32 -1, i32 -1, i32
-1>, i64
> > %idx
> > ret i32 %r
> > }
> > 
> > 
> > The assembly of that would be:
> > 
> > pcmpeqd %xmm0, %xmm0
> > movdqa %xmm0, -24(%rsp)
> > movl -24(%rsp,%rsi,4), %eax
> > retq
> > 
> > 
> > The language reference states that the extractelement instruction
> > produces undefined value in case the index argument is invalid (our
> > case). But the implementation simply dumps the vector to the stack
> > memory, calculates the memory offset out of the index value and
> > tries to access the memory. That causes the crash.
> > 
> > 
> > The workaround is to trunc the index value before extractelement
> > (see
> > %idxSafe). But what should be the ultimate solution?
> > 
> > 
> > 
> > 
> > 
> > We could fix this by specifying that out of bounds access on an
> > extractelement leads to full-on undefined behavior, no need to
> > force
> > everyone to eat the cost of a mask.
> > 
> > 
> > I don't have preference for any of the solutions.
> > 
> > 
> > I have a side question. It is not stated explicitly in the
> > reference
> > but I would assume the index of extractelement is processed as an
> > unsigned value. However, the DAG Builder extends the index with
> > sext. Is it correct?
> 
> Hrmm. Given that only (small) positive numbers are valid, it
> shouldn't matter. Unless we can find a reason that it works better
> to be sext, it seems conceptually cleaner to make it zext.
> 
> 
> 
> I have tried to change it to zext. 2 Mips test have failed. I haven't
> checked the details though.
> sext looks pretty wrong to me because i5 -1 does not mean 31 any
> more.
> 
> 
> - PB
> 
> 
> 
> -Hal
> 
> > 
> > 
> > - PB
> > _______________________________________________
> > LLVM Developers mailing list
> > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu
> > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
> > 
> 
> --
> Hal Finkel
> Assistant Computational Scientist
> Leadership Computing Facility
> Argonne National Laboratory
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
> 
> 
-- 
Hal Finkel
Assistant Computational Scientist
Leadership Computing Facility
Argonne National Laboratory