<div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote">On Fri, Aug 7, 2015 at 5:21 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:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><span class="">----- Original Message -----<br>
> From: "Chandler Carruth" <<a href="mailto:chandlerc@google.com">chandlerc@google.com</a>><br>
> To: "Hal Finkel" <<a href="mailto:hfinkel@anl.gov">hfinkel@anl.gov</a>>, "Sanjoy Das" <<a href="mailto:sanjoy@playingwithpointers.com">sanjoy@playingwithpointers.com</a>><br>
> Cc: "<a href="mailto:cfe-dev@cs.uiuc.edu">cfe-dev@cs.uiuc.edu</a> Developers" <<a href="mailto:cfe-dev@cs.uiuc.edu">cfe-dev@cs.uiuc.edu</a>>, "LLVM Developers Mailing List" <<a href="mailto:llvmdev@cs.uiuc.edu">llvmdev@cs.uiuc.edu</a>><br>
> Sent: Friday, August 7, 2015 5:52:04 PM<br>
> Subject: Re: [cfe-dev] [LLVMdev] Clang devirtualization proposal<br>
><br>
</span><div><div class="h5">> On Sat, Aug 1, 2015 at 6:39 AM Hal Finkel < <a href="mailto:hfinkel@anl.gov">hfinkel@anl.gov</a> > wrote:<br>
><br>
> ----- Original Message -----<br>
> > From: "Sanjoy Das" < <a href="mailto:sanjoy@playingwithpointers.com">sanjoy@playingwithpointers.com</a> ><br>
> > To: "Reid Kleckner" < <a href="mailto:rnk@google.com">rnk@google.com</a> ><br>
> > Cc: "Piotr Padlewski" < <a href="mailto:prazek@google.com">prazek@google.com</a> >, " <a href="mailto:cfe-dev@cs.uiuc.edu">cfe-dev@cs.uiuc.edu</a><br>
> > Developers" < <a href="mailto:cfe-dev@cs.uiuc.edu">cfe-dev@cs.uiuc.edu</a> >, "LLVM Developers<br>
> > Mailing List" < <a href="mailto:llvmdev@cs.uiuc.edu">llvmdev@cs.uiuc.edu</a> ><br>
> > Sent: Saturday, August 1, 2015 1:22:50 AM<br>
> > Subject: Re: [LLVMdev] [cfe-dev] Clang devirtualization proposal<br>
> ><br>
> > On Fri, Jul 31, 2015 at 6:18 PM, Reid Kleckner < <a href="mailto:rnk@google.com">rnk@google.com</a> ><br>
> > wrote:<br>
> > > Consider this pseudo-IR and some possible transforms that I would<br>
> > > expect to<br>
> > > be semantics preserving:<br>
> > ><br>
> > > void f(i32* readonly %a, i32* %b) {<br>
> > > llvm.assume(%a == %b)<br>
> > > store i32 42, i32* %b<br>
> > > }<br>
> > > ...<br>
> > > %p = alloca i32<br>
> > > store i32 13, i32* %p<br>
> > > call f(i32* readonly %p, i32* %p)<br>
> > > %r = load i32, i32* %p<br>
> > ><br>
> > > ; Propagate llvm.assume info<br>
> > > void f(i32* readonly %a, i32* %b) {<br>
> > > store i32 42, i32* %a<br>
> > > }<br>
> > > ...<br>
> > > %p = alloca i32<br>
> > > store i32 13, i32* %p<br>
> > > call f(i32* readonly %p, i32* %p)<br>
> > > %r = load i32, i32* %p<br>
> ><br>
> > I'd say this first transformation is incorrect. `readonly` is<br>
> > effectively part of `%a`'s "type" as it constrains and affects the<br>
> > operations you can do on `%a`. Even if `%b` is bitwise equivalent<br>
> > to<br>
> > `%a` at runtime, it is "type incompatible" to replace `%a` with<br>
> > `%b`.<br>
> ><br>
> > This is similar to how you cannot replace `store i32 42, i32<br>
> > addrspace(1)* %a` with `store i32 42, i32 addrspace(2)* %b`, even<br>
> > if<br>
> > you can prove `ptrtoint %a` == `ptrtoint %b` -- the nature of<br>
> > `store`<br>
> > is dependent on the type of the pointer you store through.<br>
> ><br>
> > The glitch in LLVM IR right now is that the `readonly`ness of `%a`<br>
> > is<br>
> > not modeled in the type system, when I think it should be. An `i32<br>
> > readonly*` should be a different type from `i32*`. In practice this<br>
> > may be non-trivial to get right (for instance `phi`s and `selects`<br>
> > will either have to do a type merge, or we'd have to have explicit<br>
> > type operators at the IR level).<br>
><br>
> We could do this, but then we'd need to promote these things to<br>
> first-class parts of the type system (and I'd need to put further<br>
> thought about how this interacts with dynamically-true properties at<br>
> callsites and inlining).<br>
><br>
> The alternative way of looking at it, which is true today, is that<br>
> @llvm.assume is not removed even when its information is 'used'. It<br>
> appears, given this example, that this is actually required for<br>
> correctness, and that dead-argument elimination needs to<br>
> specifically not ignore effectively-ephemeral values/arguments.<br>
><br>
> What follows is an off-the-cuff response. I'm still thinking through<br>
> it, but wanted to let others do so as well.<br>
><br>
><br>
> There is yet another interpretation that we might use: the final<br>
> transformation Reid proposed is actually correct and allowed<br>
> according to the IR.<br>
><br>
><br>
> Specifically, we could make 'readonly' a property of the memory much<br>
> like aliasing is. That would mean that the function promises not to<br>
> modify the memory pointed to by %a in this example. The optimizer<br>
> gets to ignore any such modifications while remaining correct.<br>
<br>
</div></div>We could certainly do this, but it will obviously make inference harder. That might not be a good thing.<br>
<br>
As I said earlier, the original problem highlighted by Reid's example cannot currently occur: that could only happen if you remove the @llvm.assume call (thus making the other argument unused). We already don't do this (because the assumes could be useful if later inlined), and now we have a second reason. Regardless, because we don't actively remove @llvm.assume, I'm not convinced the current state of things is currently broken.<br></blockquote><div><br></div><div>Aren't analogs of his problem still possible? I'm picturing something along the lines of an icmp-br pair which allows a transform to RAUW in the BranchInst's 'true' successor.</div><div><br></div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<br>
 -Hal<br>
<span class=""><br>
><br>
> This would, in turn, mean that the store in Reid's "@f" function is<br>
> an unobservable in the case that %a == %b through some dynamic<br>
> property, whatever that may be. And as a consequence, the<br>
> store-forwarding is a correct transformation.<br>
><br>
><br>
> -Chandler<br>
><br>
><br>
><br>
><br>
><br>
</span>> -Hal<br>
<span class="">><br>
> ><br>
> > -- Sanjoy<br>
> > _______________________________________________<br>
> > LLVM Developers mailing list<br>
> > <a href="mailto:LLVMdev@cs.uiuc.edu">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>
</span><span class="">> --<br>
> Hal Finkel<br>
> Assistant Computational Scientist<br>
> Leadership Computing Facility<br>
> Argonne National Laboratory<br>
> _______________________________________________<br>
> cfe-dev mailing list<br>
> <a href="mailto:cfe-dev@cs.uiuc.edu">cfe-dev@cs.uiuc.edu</a><br>
> <a href="http://lists.cs.uiuc.edu/mailman/listinfo/cfe-dev" rel="noreferrer" target="_blank">http://lists.cs.uiuc.edu/mailman/listinfo/cfe-dev</a><br>
><br>
<br>
--<br>
Hal Finkel<br>
Assistant Computational Scientist<br>
Leadership Computing Facility<br>
Argonne National Laboratory<br>
_______________________________________________<br>
cfe-dev mailing list<br>
</span><a href="mailto:cfe-dev@lists.llvm.org">cfe-dev@lists.llvm.org</a><br>
<a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev" rel="noreferrer" target="_blank">http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev</a><br>
</blockquote></div><br></div></div>