[prev in list] [next in list] [prev in thread] [next in thread]
List: llvm-dev
Subject: Re: [llvm-dev] [cfe-dev] [LLVMdev] Clang devirtualization proposal
From: Hal Finkel via llvm-dev <llvm-dev () lists ! llvm ! org>
Date: 2015-08-08 1:03:46
Message-ID: 10507812.153.1438995824786.JavaMail.javamailuser () localhost
[Download RAW message or body]
[Attachment #2 (multipart/alternative)]
----- Original Message -----
> From: "Chandler Carruth" <chandlerc@google.com>
> To: "Hal Finkel" <hfinkel@anl.gov>
> Cc: "Sanjoy Das" <sanjoy@playingwithpointers.com>, "llvm-dev"
> <llvm-dev@lists.llvm.org>, cfe-dev@lists.llvm.org
> Sent: Friday, August 7, 2015 7:35:57 PM
> Subject: Re: [cfe-dev] [LLVMdev] Clang devirtualization proposal
> On Fri, Aug 7, 2015 at 5:21 PM Hal Finkel < hfinkel@anl.gov > wrote:
> > ----- Original Message -----
>
> > > From: "Chandler Carruth" < chandlerc@google.com >
>
> > > To: "Hal Finkel" < hfinkel@anl.gov >, "Sanjoy Das" <
> > > sanjoy@playingwithpointers.com >
>
> > > Cc: " cfe-dev@cs.uiuc.edu Developers" < cfe-dev@cs.uiuc.edu >,
> > > "LLVM Developers Mailing List" < llvmdev@cs.uiuc.edu >
>
> > > Sent: Friday, August 7, 2015 5:52:04 PM
>
> > > Subject: Re: [cfe-dev] [LLVMdev] Clang devirtualization proposal
>
> > >
>
> > > On Sat, Aug 1, 2015 at 6:39 AM Hal Finkel < hfinkel@anl.gov >
> > > wrote:
>
> > >
>
> > > ----- Original Message -----
>
> > > > From: "Sanjoy Das" < sanjoy@playingwithpointers.com >
>
> > > > To: "Reid Kleckner" < rnk@google.com >
>
> > > > Cc: "Piotr Padlewski" < prazek@google.com >, "
> > > > cfe-dev@cs.uiuc.edu
>
> > > > Developers" < cfe-dev@cs.uiuc.edu >, "LLVM Developers
>
> > > > Mailing List" < llvmdev@cs.uiuc.edu >
>
> > > > Sent: Saturday, August 1, 2015 1:22:50 AM
>
> > > > Subject: Re: [LLVMdev] [cfe-dev] Clang devirtualization
> > > > proposal
>
> > > >
>
> > > > On Fri, Jul 31, 2015 at 6:18 PM, Reid Kleckner < rnk@google.com
> > > > >
>
> > > > wrote:
>
> > > > > Consider this pseudo-IR and some possible transforms that I
> > > > > would
>
> > > > > expect to
>
> > > > > be semantics preserving:
>
> > > > >
>
> > > > > void f(i32* readonly %a, i32* %b) {
>
> > > > > llvm.assume(%a == %b)
>
> > > > > store i32 42, i32* %b
>
> > > > > }
>
> > > > > ...
>
> > > > > %p = alloca i32
>
> > > > > store i32 13, i32* %p
>
> > > > > call f(i32* readonly %p, i32* %p)
>
> > > > > %r = load i32, i32* %p
>
> > > > >
>
> > > > > ; Propagate llvm.assume info
>
> > > > > void f(i32* readonly %a, i32* %b) {
>
> > > > > store i32 42, i32* %a
>
> > > > > }
>
> > > > > ...
>
> > > > > %p = alloca i32
>
> > > > > store i32 13, i32* %p
>
> > > > > call f(i32* readonly %p, i32* %p)
>
> > > > > %r = load i32, i32* %p
>
> > > >
>
> > > > I'd say this first transformation is incorrect. `readonly` is
>
> > > > effectively part of `%a`'s "type" as it constrains and affects
> > > > the
>
> > > > operations you can do on `%a`. Even if `%b` is bitwise
> > > > equivalent
>
> > > > to
>
> > > > `%a` at runtime, it is "type incompatible" to replace `%a` with
>
> > > > `%b`.
>
> > > >
>
> > > > This is similar to how you cannot replace `store i32 42, i32
>
> > > > addrspace(1)* %a` with `store i32 42, i32 addrspace(2)* %b`,
> > > > even
>
> > > > if
>
> > > > you can prove `ptrtoint %a` == `ptrtoint %b` -- the nature of
>
> > > > `store`
>
> > > > is dependent on the type of the pointer you store through.
>
> > > >
>
> > > > The glitch in LLVM IR right now is that the `readonly`ness of
> > > > `%a`
>
> > > > is
>
> > > > not modeled in the type system, when I think it should be. An
> > > > `i32
>
> > > > readonly*` should be a different type from `i32*`. In practice
> > > > this
>
> > > > may be non-trivial to get right (for instance `phi`s and
> > > > `selects`
>
> > > > will either have to do a type merge, or we'd have to have
> > > > explicit
>
> > > > type operators at the IR level).
>
> > >
>
> > > We could do this, but then we'd need to promote these things to
>
> > > first-class parts of the type system (and I'd need to put further
>
> > > thought about how this interacts with dynamically-true properties
> > > at
>
> > > callsites and inlining).
>
> > >
>
> > > The alternative way of looking at it, which is true today, is
> > > that
>
> > > @llvm.assume is not removed even when its information is 'used'.
> > > It
>
> > > appears, given this example, that this is actually required for
>
> > > correctness, and that dead-argument elimination needs to
>
> > > specifically not ignore effectively-ephemeral values/arguments.
>
> > >
>
> > > What follows is an off-the-cuff response. I'm still thinking
> > > through
>
> > > it, but wanted to let others do so as well.
>
> > >
>
> > >
>
> > > There is yet another interpretation that we might use: the final
>
> > > transformation Reid proposed is actually correct and allowed
>
> > > according to the IR.
>
> > >
>
> > >
>
> > > Specifically, we could make 'readonly' a property of the memory
> > > much
>
> > > like aliasing is. That would mean that the function promises not
> > > to
>
> > > modify the memory pointed to by %a in this example. The optimizer
>
> > > gets to ignore any such modifications while remaining correct.
>
> > We could certainly do this, but it will obviously make inference
> > harder. That might not be a good thing.
>
> The other approach that seems reasonable is to push this to the
> caller to make inference in the callee easier. In that scenario, you
> would say that the readonly tells the caller that the memory
> location represented by the argument is not written *through that
> argument* but might be written through some other argument. Since
> the caller passes two pointers which alias, it cannot forward the
> store.
Isn't that what happens today?
> The problem I see is that if the transformation in the body of the
> callee does CSE of any form, it allows dead argument elimination to
> remove this non-readonly potentially-aliasing argument.
Right, that seems to be the problem.
> So if we want to go this route, I think we need to at least block
> dead argument elimination from removing a potentially writable
> aliasing argument even if it is unused in the function body, because
> it might be modeling a writable way for a particular memory location
> to enter the function.
> All in all, I would prefer the stronger guarantee of the readonly
> attribute (that the memory location is unchanged, regardless of
> through which pointer it is accessed).
Perhaps this is indeed the only strategy that is completely self-consistent. I don't \
object to pursuring this.
> > 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.
>
> As others have said, *anything* which triggers CSE seems problematic
> here.
Fair enough. To record the example you provided to me on IRC here:
chandlerc: we start with 'if (a == b) { *b = 42; } else { x(); }'
chandlerc: then CSE to 'if (a == b) { *a = 42; } else { x(); }'
chandlerc: then inline to 'if (a == b) { *a = 42; } else { unreachable; }'
chandlerc: then fold to 'if (true) { *a = 42; }'
chandlerc: b is now dead
chandlerc: x was marked as 'readnone'
chandlerc: and contained unreachable
-Hal
> > -Hal
>
> > >
>
> > > This would, in turn, mean that the store in Reid's "@f" function
> > > is
>
> > > an unobservable in the case that %a == %b through some dynamic
>
> > > property, whatever that may be. And as a consequence, the
>
> > > store-forwarding is a correct transformation.
>
> > >
>
> > >
>
> > > -Chandler
>
> > >
>
> > >
>
> > >
>
> > >
>
> > >
>
> > > -Hal
>
> > >
>
> > > >
>
> > > > -- Sanjoy
>
> > > > _______________________________________________
>
> > > > LLVM Developers mailing list
>
> > > > LLVMdev@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
>
> > > _______________________________________________
>
> > > cfe-dev mailing list
>
> > > cfe-dev@cs.uiuc.edu
>
> > > http://lists.cs.uiuc.edu/mailman/listinfo/cfe-dev
>
> > >
>
> > --
>
> > Hal Finkel
>
> > Assistant Computational Scientist
>
> > Leadership Computing Facility
>
> > Argonne National Laboratory
>
--
Hal Finkel
Assistant Computational Scientist
Leadership Computing Facility
Argonne National Laboratory
[Attachment #5 (text/html)]
<html><head><style type='text/css'>p { margin: 0; }</style></head><body><div \
style='font-family: arial,helvetica,sans-serif; font-size: 10pt; color: \
#000000'><br><hr id="zwchr"><blockquote style="border-left: 2px solid rgb(16, 16, \
255); margin-left: 5px; padding-left: 5px; color: rgb(0, 0, 0); font-weight: normal; \
font-style: normal; text-decoration: none; font-family: Helvetica,Arial,sans-serif; \
font-size: 12pt;"><b>From: </b>"Chandler Carruth" \
<chandlerc@google.com><br><b>To: </b>"Hal Finkel" \
<hfinkel@anl.gov><br><b>Cc: </b>"Sanjoy Das" \
<sanjoy@playingwithpointers.com>, "llvm-dev" <llvm-dev@lists.llvm.org>, \
cfe-dev@lists.llvm.org<br><b>Sent: </b>Friday, August 7, 2015 7:35:57 \
PM<br><b>Subject: </b>Re: [cfe-dev] [LLVMdev] Clang devirtualization \
proposal<br><br><div dir="ltr"><div class="gmail_quote"><div dir="ltr">On Fri, Aug 7, \
2015 at 5:21 PM Hal Finkel <<a href="mailto:hfinkel@anl.gov" \
target="_blank">hfinkel@anl.gov</a>> wrote:<br></div><blockquote \
class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, \
204, 204); padding-left: 1ex;"><hr id="zwchr"><br> > From: "Chandler Carruth" \
<<a href="mailto:chandlerc@google.com" \
target="_blank">chandlerc@google.com</a>><br> > To: "Hal Finkel" <<a \
href="mailto:hfinkel@anl.gov" target="_blank">hfinkel@anl.gov</a>>, "Sanjoy Das" \
<<a href="mailto:sanjoy@playingwithpointers.com" \
target="_blank">sanjoy@playingwithpointers.com</a>><br> > Cc: "<a \
href="mailto:cfe-dev@cs.uiuc.edu" target="_blank">cfe-dev@cs.uiuc.edu</a> Developers" \
<<a href="mailto:cfe-dev@cs.uiuc.edu" target="_blank">cfe-dev@cs.uiuc.edu</a>>, \
"LLVM Developers Mailing List" <<a href="mailto:llvmdev@cs.uiuc.edu" \
target="_blank">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>
> On Sat, Aug 1, 2015 at 6:39 AM Hal Finkel < <a href="mailto:hfinkel@anl.gov" \
target="_blank">hfinkel@anl.gov</a> > wrote:<br> ><br>
> ----- Original Message -----<br>
> > From: "Sanjoy Das" < <a href="mailto:sanjoy@playingwithpointers.com" \
target="_blank">sanjoy@playingwithpointers.com</a> ><br> > > To: "Reid \
Kleckner" < <a href="mailto:rnk@google.com" target="_blank">rnk@google.com</a> \
><br> > > Cc: "Piotr Padlewski" < <a href="mailto:prazek@google.com" \
target="_blank">prazek@google.com</a> >, " <a href="mailto:cfe-dev@cs.uiuc.edu" \
target="_blank">cfe-dev@cs.uiuc.edu</a><br> > > Developers" < <a \
href="mailto:cfe-dev@cs.uiuc.edu" target="_blank">cfe-dev@cs.uiuc.edu</a> >, "LLVM \
Developers<br> > > Mailing List" < <a href="mailto:llvmdev@cs.uiuc.edu" \
target="_blank">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" target="_blank">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>
We could certainly do this, but it will obviously make inference harder. That might \
not be a good thing.<br></blockquote><div><br></div><div id="DWT1761">The other \
approach that seems reasonable is to push this to the caller to make inference in the \
callee easier. In that scenario, you would say that the readonly tells the caller \
that the memory location represented by the argument is not written *through that \
argument* but might be written through some other argument. Since the caller passes \
two pointers which alias, it cannot forward the \
store.<br></div></div></div></blockquote><br>Isn't that what happens \
today?<br><br><blockquote style="border-left: 2px solid rgb(16, 16, 255); \
margin-left: 5px; padding-left: 5px; color: rgb(0, 0, 0); font-weight: normal; \
font-style: normal; text-decoration: none; font-family: Helvetica,Arial,sans-serif; \
font-size: 12pt;"><div dir="ltr"><div \
class="gmail_quote"><div></div><div><br></div><div id="DWT1762">The problem I see is \
that if the transformation in the body of the callee does CSE of any form, it allows \
dead argument elimination to remove this non-readonly potentially-aliasing \
argument.</div></div></div></blockquote><br>Right, that seems to be the \
problem.<br><br><blockquote style="border-left: 2px solid rgb(16, 16, 255); \
margin-left: 5px; padding-left: 5px; color: rgb(0, 0, 0); font-weight: normal; \
font-style: normal; text-decoration: none; font-family: Helvetica,Arial,sans-serif; \
font-size: 12pt;"><div dir="ltr"><div \
class="gmail_quote"><div></div><div><br></div><div>So if we want to go this route, I \
think we need to at least block dead argument elimination from removing a potentially \
writable aliasing argument even if it is unused in the function body, because it \
might be modeling a writable way for a particular memory location to enter the \
function.</div><div><br></div><div id="DWT1763">All in all, I would prefer the \
stronger guarantee of the readonly attribute (that the memory location is unchanged, \
regardless of through which pointer it is \
accessed).</div></div></div></blockquote><br>Perhaps this is indeed the only strategy \
that is completely self-consistent. I don't object to pursuring \
this.<br><br><blockquote style="border-left: 2px solid rgb(16, 16, 255); margin-left: \
5px; padding-left: 5px; color: rgb(0, 0, 0); font-weight: normal; font-style: normal; \
text-decoration: none; font-family: Helvetica,Arial,sans-serif; font-size: \
12pt;"><div dir="ltr"><div class="gmail_quote"><div></div><div><br></div><blockquote \
class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, \
204, 204); padding-left: 1ex;"> <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 id="DWT1674">As \
others have said, *anything* which triggers CSE seems problematic \
here.</div></div></div></blockquote><br>Fair enough. To record the example you \
provided to me on IRC here:<br><br><span style="font-weight: normal;"></span><span \
style="font-weight: normal; color: rgb(118, 88, 87);">chandlerc: </span>we start with \
'if (a == b) { *b = 42; } else { x(); }'<br><span style="font-weight: \
normal;"></span><span style="font-weight: normal; color: rgb(118, 88, \
87);">chandlerc: </span>then CSE to 'if (a == b) { *a = 42; } else { x(); }'<br><span \
style="font-weight: normal;"></span><span style="font-weight: normal; color: rgb(118, \
88, 87);">chandlerc: </span>then inline to 'if (a == b) { *a = 42; } else { \
unreachable; }'<br><span style="font-weight: normal;"></span><span \
style="font-weight: normal; color: rgb(118, 88, 87);">chandlerc: </span>then fold to \
'if (true) { *a = 42; }'<br><span style="font-weight: normal;"></span><span \
style="font-weight: normal; color: rgb(118, 88, 87);">chandlerc: </span>b is now \
dead<br><span style="font-weight: normal;"></span><span style="font-weight: normal; \
color: rgb(118, 88, 87);">chandlerc: </span>x was marked as 'readnone'<br><span \
style="font-weight: normal;"></span><span style="font-weight: normal; color: rgb(118, \
88, 87);">chandlerc: </span>and contained \
unreachable<br><br> -Hal<br><blockquote style="border-left: 2px solid rgb(16, \
16, 255); margin-left: 5px; padding-left: 5px; color: rgb(0, 0, 0); font-weight: \
normal; font-style: normal; text-decoration: none; font-family: \
Helvetica,Arial,sans-serif; font-size: 12pt;"><div dir="ltr"><div \
class="gmail_quote"><div></div><div> </div><blockquote class="gmail_quote" \
style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); \
padding-left: 1ex;"> <br>
-Hal<br>
<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>
> -Hal<br>
><br>
> ><br>
> > -- Sanjoy<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>
> cfe-dev mailing list<br>
> <a href="mailto:cfe-dev@cs.uiuc.edu" target="_blank">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>
</blockquote></div></div>
</blockquote><br><br><br>-- <br><div><span name="x"></span>Hal Finkel<br>Assistant \
Computational Scientist<br>Leadership Computing Facility<br>Argonne National \
Laboratory<span name="x"></span><br></div></div></body></html>
[Attachment #6 (text/plain)]
_______________________________________________
LLVM Developers mailing list
llvm-dev@lists.llvm.org http://llvm.cs.uiuc.edu
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
[prev in list] [next in list] [prev in thread] [next in thread]
Configure |
About |
News |
Add a list |
Sponsored by KoreLogic