[prev in list] [next in list] [prev in thread] [next in thread]
List: cfe-dev
Subject: Re: [cfe-dev] [LLVMdev] Clang devirtualization proposal
From: Chandler Carruth <chandlerc () google ! com>
Date: 2015-08-07 22:55:47
Message-ID: CAGCO0KiKLnrnYsBg-CbBgQQijNgmVzbVmNaVLYuW65ifVH62tA () mail ! gmail ! com
[Download RAW message or body]
[Attachment #2 (multipart/alternative)]
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.
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
[Attachment #5 (text/html)]
<div dir="ltr"><div class="gmail_quote"><div dir="ltr">On Sat, Aug 1, 2015 at 6:39 AM \
Hal Finkel <<a href="mailto:hfinkel@anl.gov">hfinkel@anl.gov</a>> \
wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 \
.8ex;border-left:1px #ccc solid;padding-left:1ex">----- 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> \
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 to<br>
> `%a` at runtime, it is "type incompatible" to replace `%a` with \
`%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 if<br>
> you can prove `ptrtoint %a` == `ptrtoint %b` -- the nature of `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` 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 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).<br> <br>
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.<br></blockquote><div><br></div><div \
style="font-size:13.1999998092651px;line-height:19.7999992370605px">What follows is \
an off-the-cuff response. I'm still thinking through it, but wanted to let others \
do so as well.</div><div \
style="font-size:13.1999998092651px;line-height:19.7999992370605px"><br></div><div \
style="font-size:13.1999998092651px;line-height:19.7999992370605px">There is yet \
another interpretation that we might use: the final transformation Reid proposed is \
actually correct and allowed according to the IR.</div><div \
style="font-size:13.1999998092651px;line-height:19.7999992370605px"><br></div><div \
style="font-size:13.1999998092651px;line-height:19.7999992370605px">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.</div><div style="font-size:13.1999998092651px;line-height:19.7999992370605px"><br></div><div><span \
style="font-size:13.1999998092651px;line-height:19.7999992370605px">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.</span></div><div><br></div><div>-Chandler</div></div></div>
[Attachment #6 (text/plain)]
_______________________________________________
cfe-dev mailing list
cfe-dev@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev
[prev in list] [next in list] [prev in thread] [next in thread]
Configure |
About |
News |
Add a list |
Sponsored by KoreLogic