<div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote">On Wed, Jul 1, 2015 at 4:48 PM, Hal Finkel <span dir="ltr"><<a href="mailto:hfinkel@anl.gov" target="_blank">hfinkel@anl.gov</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><span>----- Original Message -----<br>
> From: "Pete Cooper" <<a href="mailto:peter_cooper@apple.com" target="_blank">peter_cooper@apple.com</a>><br>
</span><div><div>> To: "Hal Finkel" <<a href="mailto:hfinkel@anl.gov" target="_blank">hfinkel@anl.gov</a>><br>
> Cc: "LLVMdev" <<a href="mailto:llvmdev@cs.uiuc.edu" target="_blank">llvmdev@cs.uiuc.edu</a>>, "Paweł Bylica" <<a href="mailto:chfast@gmail.com" target="_blank">chfast@gmail.com</a>><br>
> Sent: Wednesday, July 1, 2015 6:42:41 PM<br>
> Subject: Re: [LLVMdev] extractelement causes memory access violation - what   to do?<br>
><br>
><br>
> > On Jul 1, 2015, at 3:45 PM, Hal Finkel <<a href="mailto:hfinkel@anl.gov" target="_blank">hfinkel@anl.gov</a>> wrote:<br>
> ><br>
> > ----- Original Message -----<br>
> >> From: "Pete Cooper" <<a href="mailto:peter_cooper@apple.com" target="_blank">peter_cooper@apple.com</a>><br>
> >> To: "Paweł Bylica" <<a href="mailto:chfast@gmail.com" target="_blank">chfast@gmail.com</a>><br>
> >> Cc: "Hal Finkel" <<a href="mailto:hfinkel@anl.gov" target="_blank">hfinkel@anl.gov</a>>, "LLVMdev"<br>
> >> <<a href="mailto:llvmdev@cs.uiuc.edu" target="_blank">llvmdev@cs.uiuc.edu</a>><br>
> >> Sent: Wednesday, July 1, 2015 12:08:37 PM<br>
> >> Subject: Re: [LLVMdev] extractelement causes memory access<br>
> >> violation - what   to do?<br>
> >><br>
> >> Sorry for chiming in so late in this.<br>
> >><br>
> >> So I agree that negative indices are UB, I don’t think thats<br>
> >> contentious.<br>
> >><br>
> >> However, I think the issue here is the DAG expansion. That is the<br>
> >> point at which we go from UB which would just be hidden in the<br>
> >> instruction to something which can crash. I think its at that<br>
> >> point<br>
> >> where we should mask to ensure that the in memory expansion<br>
> >> doesn’t<br>
> >> read out of bounds. On architectures which do the variable extract<br>
> >> in an instruction, they won’t be penalized by a mask,<br>
> ><br>
> > Why do you feel that they won't be penalized by the mask? Or are<br>
> > you assuming will adjust the patterns to match the index plus the<br>
> > mask?<br>
> Ah, should have explained better.  What I meant was that if i can do<br>
> the variable extract in a register without going to memory at all<br>
> (so have suitable legal instructions to do so), then we won’t<br>
> generate a mask at all.  The mask would only be generated when the<br>
> legalizer moves the data to memory which we don’t do if its legal.<br>
<br>
</div></div>Ah, alright.<br>
<span><br>
> ><br>
> >> only the<br>
> >> memory expansion will be which should be rarer,<br>
> ><br>
> > On some architectures expansion in memory is not particularly<br>
> > expensive because they have very good store-to-load forwarding.<br>
> > Adding additional masking instructions into the critical path of<br>
> > correct code will not be a welcome change.<br>
> Thats true, so i guess it depends how many architectures need to do<br>
> variable extracts in memory.  I have no idea if any architectures we<br>
> support are able to do a variable extract in a register, or if all<br>
> use memory.<br>
<br>
</span>At least on PowerPC, when using QPX, we can do this using instructions.<br>
<span><br>
>  If most use a register, then penalizing the few who do<br>
> use memory by inserting a mask seems reasonable.<br>
> ><br>
> >><br>
> >> The point about speculation at the IR level is interesting.<br>
> >> Personally i’m ok with constant indices being speculated and<br>
> >> variable not. If we later want to find a good way to ask TTI<br>
> >> whether<br>
> >> a variable extract is cheap then we can find a way to do so.<br>
> ><br>
> > It is not about expense, it is about not introducing UB when<br>
> > speculating the instruction.<br>
> Yeah, I see what you mean here.  So the user could have written<br>
><br>
> if (i >= 0) x = extract v[i]<br>
><br>
> but if we speculate then we aren’t guarded and have UB.  Having the<br>
> backend insert the mask would fix this, but I agree that someone,<br>
> somewhere needs to put in the mask if we want to allow speculation<br>
> here, and the target can’t do the variable extract in a register.<br>
<br>
</span>I'd rather the frontend do this if the language wants it. We can use ComputeKnownBits when we do the speculation check, and so if there is a mask, we'll be fine.<br></blockquote><div><br></div><div>I don't think we can rely on ComputeKnownBits for this sort of thing.</div><div>Consider:</div><div>  %and = and i64 %x, 1</div><div>  %idx = lshr exact i64 %and, 1</div><div>  %z = extractelement<span style="font-size:12.8000001907349px"> </span><span style="font-size:12.8000001907349px"><4 x i32> <i32 -1, i32 -1, i32 -1, i32 -1>, i64 %idx</span></div><div> </div><div>ComputeKnownBits doesn't take 'exact' into account and will report that %idx must be all zeros.  However, %idx might turn into undef if %x has the bottom bit set.  In fact, it doesn't appear to be conservative at all in the face of flags.  If anything, it takes advantage of them: <a href="https://urldefense.proofpoint.com/v2/url?u=http-3A__llvm.org_docs_doxygen_html_ValueTracking-5F8cpp-5Fsource.html-23l00275&d=AwMFaQ&c=8hUWFZcy2Z-Za5rBPlktOQ&r=Mfk2qtn1LTDThVkh6-oGglNfMADXfJdty4_bhmuhMHA&m=PX6u2wV56vigXO8ANOwgZw9-5WrBrDQyQiLo8bX-X48&s=22q6lNl83Fzyo5rfXascBF2TlGC8hUnITEucsUptCdI&e=">http://llvm.org/docs/doxygen/html/ValueTracking_8cpp_source.html#l00275</a></div><div><br></div><div>This tells me that we have three options if we want the instruction to stay speculatable:</div><div>1. Make a variant of ComputeKnownBits (or something along those lines) which is explicitly pessimistic in the face of flags.<br></div><div>2. Kick the can to the backend.</div><div>3. Make ComputeKnowBits pessimistic in the face of flags.</div><div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
<div><div><br>
><br>
> Pete<br>
> ><br>
> > -Hal<br>
> ><br>
> >><br>
> >> Anyway, just my 2c.<br>
> >><br>
> >><br>
> >> Cheers,<br>
> >> Pete<br>
> >><br>
> >><br>
> >><br>
> >><br>
> >> On Jun 30, 2015, at 2:07 PM, Paweł Bylica < <a href="mailto:chfast@gmail.com" target="_blank">chfast@gmail.com</a> ><br>
> >> wrote:<br>
> >><br>
> >><br>
> >><br>
> >><br>
> >> On Tue, Jun 30, 2015 at 11:03 PM Hal Finkel < <a href="mailto:hfinkel@anl.gov" target="_blank">hfinkel@anl.gov</a> ><br>
> >> wrote:<br>
> >><br>
> >><br>
> >> ----- Original Message -----<br>
> >>> From: "Paweł Bylica" < <a href="mailto:chfast@gmail.com" target="_blank">chfast@gmail.com</a> ><br>
> >>> To: "David Majnemer" < <a href="mailto:david.majnemer@gmail.com" target="_blank">david.majnemer@gmail.com</a> ><br>
> >>> Cc: "LLVMdev" < <a href="mailto:llvmdev@cs.uiuc.edu" target="_blank">llvmdev@cs.uiuc.edu</a> ><br>
> >>> Sent: Tuesday, June 30, 2015 5:42:24 AM<br>
> >>> Subject: Re: [LLVMdev] extractelement causes memory access<br>
> >>> violation - what to do?<br>
> >>><br>
> >>><br>
> >>><br>
> >>><br>
> >>><br>
> >>> On Fri, Jun 26, 2015 at 5:42 PM David Majnemer <<br>
> >>> <a href="mailto:david.majnemer@gmail.com" target="_blank">david.majnemer@gmail.com</a> > wrote:<br>
> >>><br>
> >>><br>
> >>><br>
> >>><br>
> >>><br>
> >>> On Fri, Jun 26, 2015 at 7:00 AM, Paweł Bylica < <a href="mailto:chfast@gmail.com" target="_blank">chfast@gmail.com</a><br>
> >>> ><br>
> >>> wrote:<br>
> >>><br>
> >>><br>
> >>><br>
> >>> Hi,<br>
> >>><br>
> >>><br>
> >>> Let's have a simple program:<br>
> >>><br>
> >>> define i32 @main(i32 %n, i64 %idx) {<br>
> >>> %idxSafe = trunc i64 %idx to i5<br>
> >>> %r = extractelement <4 x i32> <i32 -1, i32 -1, i32 -1, i32 -1>,<br>
> >>> i64<br>
> >>> %idx<br>
> >>> ret i32 %r<br>
> >>> }<br>
> >>><br>
> >>><br>
> >>> The assembly of that would be:<br>
> >>><br>
> >>> pcmpeqd %xmm0, %xmm0<br>
> >>> movdqa %xmm0, -24(%rsp)<br>
> >>> movl -24(%rsp,%rsi,4), %eax<br>
> >>> retq<br>
> >>><br>
> >>><br>
> >>> The language reference states that the extractelement instruction<br>
> >>> produces undefined value in case the index argument is invalid<br>
> >>> (our<br>
> >>> case). But the implementation simply dumps the vector to the<br>
> >>> stack<br>
> >>> memory, calculates the memory offset out of the index value and<br>
> >>> tries to access the memory. That causes the crash.<br>
> >>><br>
> >>><br>
> >>> The workaround is to trunc the index value before extractelement<br>
> >>> (see<br>
> >>> %idxSafe). But what should be the ultimate solution?<br>
> >>><br>
> >>><br>
> >>><br>
> >>><br>
> >>><br>
> >>> We could fix this by specifying that out of bounds access on an<br>
> >>> extractelement leads to full-on undefined behavior, no need to<br>
> >>> force<br>
> >>> everyone to eat the cost of a mask.<br>
> >>><br>
> >>><br>
> >>> I don't have preference for any of the solutions.<br>
> >>><br>
> >>><br>
> >>> I have a side question. It is not stated explicitly in the<br>
> >>> reference<br>
> >>> but I would assume the index of extractelement is processed as an<br>
> >>> unsigned value. However, the DAG Builder extends the index with<br>
> >>> sext. Is it correct?<br>
> >><br>
> >> Hrmm. Given that only (small) positive numbers are valid, it<br>
> >> shouldn't matter. Unless we can find a reason that it works better<br>
> >> to be sext, it seems conceptually cleaner to make it zext.<br>
> >><br>
> >><br>
> >><br>
> >> I have tried to change it to zext. 2 Mips test have failed. I<br>
> >> haven't<br>
> >> checked the details though.<br>
> >> sext looks pretty wrong to me because i5 -1 does not mean 31 any<br>
> >> more.<br>
> >><br>
> >><br>
> >> - PB<br>
> >><br>
> >><br>
> >><br>
> >> -Hal<br>
> >><br>
> >>><br>
> >>><br>
> >>> - PB<br>
> >>> _______________________________________________<br>
> >>> LLVM Developers mailing list<br>
> >>> <a href="mailto:LLVMdev@cs.uiuc.edu" target="_blank">LLVMdev@cs.uiuc.edu</a> <a href="http://llvm.cs.uiuc.edu" rel="noreferrer" target="_blank">http://llvm.cs.uiuc.edu</a><br>
> >>> <a href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev" rel="noreferrer" target="_blank">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a><br>
> >>><br>
> >><br>
> >> --<br>
> >> Hal Finkel<br>
> >> Assistant Computational Scientist<br>
> >> Leadership Computing Facility<br>
> >> Argonne National Laboratory<br>
> >> _______________________________________________<br>
> >> LLVM Developers mailing list<br>
> >> <a href="mailto:LLVMdev@cs.uiuc.edu" target="_blank">LLVMdev@cs.uiuc.edu</a> <a href="http://llvm.cs.uiuc.edu" rel="noreferrer" target="_blank">http://llvm.cs.uiuc.edu</a><br>
> >> <a href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev" rel="noreferrer" target="_blank">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a><br>
> >><br>
> >><br>
> ><br>
> > --<br>
> > Hal Finkel<br>
> > Assistant Computational Scientist<br>
> > Leadership Computing Facility<br>
> > Argonne National Laboratory<br>
><br>
><br>
<br>
--<br>
Hal Finkel<br>
Assistant Computational Scientist<br>
Leadership Computing Facility<br>
Argonne National Laboratory<br>
<br>
_______________________________________________<br>
LLVM Developers mailing list<br>
<a href="mailto:LLVMdev@cs.uiuc.edu" target="_blank">LLVMdev@cs.uiuc.edu</a>         <a href="http://llvm.cs.uiuc.edu" rel="noreferrer" target="_blank">http://llvm.cs.uiuc.edu</a><br>
<a href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev" rel="noreferrer" target="_blank">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a><br>
</div></div></blockquote></div><br></div></div>