llvm dev - Aug 2015 - [cfe-dev] [LLVMdev] Clang devirtualization proposal

----- Original Message -----
> From: "Chandler Carruth" <chandlerc at google.com>
> To: "Hal Finkel" <hfinkel at anl.gov>, "Sanjoy
Das" <sanjoy at playingwithpointers.com>
> Cc: "cfe-dev at cs.uiuc.edu Developers" <cfe-dev at
cs.uiuc.edu>, "LLVM Developers Mailing List" <llvmdev at
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 at anl.gov >
wrote:
>  
> ----- Original Message -----
> > From: "Sanjoy Das" < sanjoy at playingwithpointers.com
>
> > To: "Reid Kleckner" < rnk at google.com >
> > Cc: "Piotr Padlewski" < prazek at google.com >, "
cfe-dev at cs.uiuc.edu
> > Developers" < cfe-dev at cs.uiuc.edu >, "LLVM
Developers
> > Mailing List" < llvmdev at 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 at 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.

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.

 -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 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
> _______________________________________________
> cfe-dev mailing list
> cfe-dev at cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/cfe-dev
> 
-- 
Hal Finkel
Assistant Computational Scientist
Leadership Computing Facility
Argonne National Laboratory

On Fri, Aug 7, 2015 at 5:21 PM, Hal Finkel <hfinkel at anl.gov> wrote:
> ----- Original Message -----
> > From: "Chandler Carruth" <chandlerc at google.com>
> > To: "Hal Finkel" <hfinkel at anl.gov>, "Sanjoy
Das" <
> sanjoy at playingwithpointers.com>
> > Cc: "cfe-dev at cs.uiuc.edu Developers" <cfe-dev at
cs.uiuc.edu>, "LLVM
> Developers Mailing List" <llvmdev at 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 at anl.gov >
wrote:
> >
> > ----- Original Message -----
> > > From: "Sanjoy Das" < sanjoy at
playingwithpointers.com >
> > > To: "Reid Kleckner" < rnk at google.com >
> > > Cc: "Piotr Padlewski" < prazek at google.com >,
" cfe-dev at cs.uiuc.edu
> > > Developers" < cfe-dev at cs.uiuc.edu >, "LLVM
Developers
> > > Mailing List" < llvmdev at 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 at
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.
>
> 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.
>
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.


>
>  -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 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
> > _______________________________________________
> > cfe-dev mailing list
> > cfe-dev at cs.uiuc.edu
> > http://lists.cs.uiuc.edu/mailman/listinfo/cfe-dev
> >
>
> --
> Hal Finkel
> Assistant Computational Scientist
> Leadership Computing Facility
> Argonne National Laboratory
> _______________________________________________
> cfe-dev mailing list
> cfe-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150807/d2df0403/attachment.html>

On Fri, Aug 7, 2015 at 5:21 PM Hal Finkel <hfinkel at anl.gov> wrote:
> ----- Original Message -----
> > From: "Chandler Carruth" <chandlerc at google.com>
> > To: "Hal Finkel" <hfinkel at anl.gov>, "Sanjoy
Das" <
> sanjoy at playingwithpointers.com>
> > Cc: "cfe-dev at cs.uiuc.edu Developers" <cfe-dev at
cs.uiuc.edu>, "LLVM
> Developers Mailing List" <llvmdev at 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 at anl.gov >
wrote:
> >
> > ----- Original Message -----
> > > From: "Sanjoy Das" < sanjoy at
playingwithpointers.com >
> > > To: "Reid Kleckner" < rnk at google.com >
> > > Cc: "Piotr Padlewski" < prazek at google.com >,
" cfe-dev at cs.uiuc.edu
> > > Developers" < cfe-dev at cs.uiuc.edu >, "LLVM
Developers
> > > Mailing List" < llvmdev at 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 at
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.

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.

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).

> 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.

>
>  -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 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
> > _______________________________________________
> > cfe-dev mailing list
> > cfe-dev at cs.uiuc.edu
> > http://lists.cs.uiuc.edu/mailman/listinfo/cfe-dev
> >
>
> --
> 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/20150808/1cb48996/attachment.html>

----- Original Message -----
> From: "David Majnemer" <david.majnemer at gmail.com>
> To: "Hal Finkel" <hfinkel at anl.gov>
> Cc: "Chandler Carruth" <chandlerc at google.com>,
"llvm-dev" <llvm-dev at lists.llvm.org>, "Sanjoy Das"
> <sanjoy at playingwithpointers.com>, cfe-dev at lists.llvm.org
> Sent: Friday, August 7, 2015 7:32:16 PM
> Subject: Re: [cfe-dev] [LLVMdev] Clang devirtualization proposal
> 
> 
> 
> 
> 
> 
> On Fri, Aug 7, 2015 at 5:21 PM, Hal Finkel < hfinkel at anl.gov >
wrote:
> 
> 
> ----- Original Message -----
> > From: "Chandler Carruth" < chandlerc at google.com >
> > To: "Hal Finkel" < hfinkel at anl.gov >, "Sanjoy
Das" <
> > sanjoy at playingwithpointers.com >
> > Cc: " cfe-dev at cs.uiuc.edu Developers" < cfe-dev at
cs.uiuc.edu >,
> > "LLVM Developers Mailing List" < llvmdev at 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 at anl.gov >
> > wrote:
> > 
> > ----- Original Message -----
> > > From: "Sanjoy Das" < sanjoy at
playingwithpointers.com >
> > > To: "Reid Kleckner" < rnk at google.com >
> > > Cc: "Piotr Padlewski" < prazek at google.com >,
"
> > > cfe-dev at cs.uiuc.edu
> > > Developers" < cfe-dev at cs.uiuc.edu >, "LLVM
Developers
> > > Mailing List" < llvmdev at 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 at
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.
> 
> 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.
> 
> 
> 
> 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.
> 
> 
You can certainly have this:

if (a == b) {
  *b = 5;
}

and transform this into:

if (a == b) {
  *a = 5;
}

but that does not completely remove b, and so the dead-argument removal could
not kick in.

 -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 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
> > _______________________________________________
> > cfe-dev mailing list
> > cfe-dev at cs.uiuc.edu
> > http://lists.cs.uiuc.edu/mailman/listinfo/cfe-dev
> > 
> 
> --
> Hal Finkel
> Assistant Computational Scientist
> Leadership Computing Facility
> Argonne National Laboratory
> _______________________________________________
> cfe-dev mailing list
> cfe-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev
> 
> 
-- 
Hal Finkel
Assistant Computational Scientist
Leadership Computing Facility
Argonne National Laboratory

----- Original Message -----
> From: "Chandler Carruth" <chandlerc at google.com>
> To: "Hal Finkel" <hfinkel at anl.gov>
> Cc: "Sanjoy Das" <sanjoy at playingwithpointers.com>,
"llvm-dev"
> <llvm-dev at lists.llvm.org>, cfe-dev at 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 at anl.gov >
wrote:
> > ----- Original Message -----
> 
> > > From: "Chandler Carruth" < chandlerc at google.com
>
> 
> > > To: "Hal Finkel" < hfinkel at anl.gov >,
"Sanjoy Das" <
> > > sanjoy at playingwithpointers.com >
> 
> > > Cc: " cfe-dev at cs.uiuc.edu Developers" < cfe-dev
at cs.uiuc.edu >,
> > > "LLVM Developers Mailing List" < llvmdev at
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 at anl.gov
>
> > > wrote:
> 
> > >
> 
> > > ----- Original Message -----
> 
> > > > From: "Sanjoy Das" < sanjoy at
playingwithpointers.com >
> 
> > > > To: "Reid Kleckner" < rnk at google.com >
> 
> > > > Cc: "Piotr Padlewski" < prazek at google.com
>, "
> > > > cfe-dev at cs.uiuc.edu
> 
> > > > Developers" < cfe-dev at cs.uiuc.edu >,
"LLVM Developers
> 
> > > > Mailing List" < llvmdev at 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 at
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 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
> 
> > > _______________________________________________
> 
> > > cfe-dev mailing list
> 
> > > cfe-dev at 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 
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150807/73ca64ed/attachment-0001.html>