Clang devirtualization proposal

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
36 messages Options
12
Reply | Threaded
Open this post in threaded view
|

Re: Clang devirtualization proposal

Piotr Padlewski
oh I see. Yep, my mistake.

On Fri, Jul 31, 2015 at 5:03 PM, Philip Reames <[hidden email]> wrote:


On 07/31/2015 04:05 PM, Piotr Padlewski wrote:


On Fri, Jul 31, 2015 at 3:53 PM, Philip Reames <[hidden email]> wrote:
Quoting from the google doc: "If we don’t know definition of some function, we assume that it will not call @llvm.invariant.group.barrier()."
This part really really bugs me.  We generally try to assume minimal knowledge of external functions (i.e. they can do anything) and this assumption would invert that.  Is there a way we can rephrase the proposal which avoids the need for this?  I'm not quite clear what this assumption buys us.

This is because without it the optimization will be useless. For example:
A* a = new A;
a->foo(); //outline virtual
a->foo();

If we will assume that foo calls @llvm.invariant.barrier, then we will not be able to optimize the second call.
Why not?  If foo calls @llvm.invariant.group.barrier, then it would have to produce a new SSA value to accomplish anything which might effect the second call.  Given the call is on "a", not some return value from foo or a global variable, we know that any SSA value created inside foo isn't relevant.  We should end up a with two loads of the vtable using the same SSA value and the same invariant.group metadata.  The later can be forwarded from the former without issue right?

%a = ...;
%vtable1 = load %a + Y !invariant.group !0
%foo1 = load %vtable1 + X, !invariant.group !1
call %foo1(%a)
%vtable2 = load %a + Y !invariant.group !0 <-- Per state rules, this value forwards from previous vtable load
%foo2 = load %vtable2 + X, !invariant.group !1
call %foo2(%a)

Philip




_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: [cfe-dev] Clang devirtualization proposal

Sanjoy Das
In reply to this post by Hal Finkel
On Sat, Aug 1, 2015 at 6:33 AM, Hal Finkel <[hidden email]> wrote:

> ----- Original Message -----
>> From: "Sanjoy Das" <[hidden email]>
>> To: "Reid Kleckner" <[hidden email]>
>> Cc: "Piotr Padlewski" <[hidden email]>, "[hidden email] Developers" <[hidden email]>, "LLVM Developers
>> Mailing List" <[hidden email]>
>> 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 <[hidden email]>
>> 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.

I don't think the problem has to do with llvm.assume specifically.
This is a problematic example too:

void f(i32* readonly %a, i32* %b) {
   if (%a != %b) then unreachable;

   store i32 42, i32* %b
}

-- Sanjoy

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: [cfe-dev] Clang devirtualization proposal

Nick Lewycky
In reply to this post by Sanjoy Das
Sanjoy Das wrote:

> On Fri, Jul 31, 2015 at 6:18 PM, Reid Kleckner<[hidden email]>  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"

The trouble is that we want to express ideas like "at this call site,
but not others, I know that this call will not mutate state through this
pointer". We can't express that with the llvm type system we have today.

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

Right, but the "type merge" as you call it has to happen essentially
everywhere. We'd need something akin to C's qualification conversion.

>
> -- Sanjoy
> _______________________________________________
> LLVM Developers mailing list
> [hidden email]         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: [cfe-dev] Clang devirtualization proposal

Sanjoy Das
> The trouble is that we want to express ideas like "at this call site, but
> not others, I know that this call will not mutate state through this
> pointer". We can't express that with the llvm type system we have today.

Yes; to do that we'll effectively have to introduce some form of
quantification.

IOW: we'd have to have 4x the number of pointer types we have today --
each pointer type should be quantifiable with `noaccess`, `read`,
`write` and `readwrite` (the second one may not be very useful if we
do not want to support memory with only `PROT_WRITE`).

Functions and other consumers types would then have to be modified to
allow universal (and other forms of?) quantification.  I should be able to
write a function `@calc` of the type:

"forall $domain in { noaccess, read, write, readwrite }: i8* $domain -> i32"

Once we can quantify function types this way, we should be able to
call a function of the above type (say) with a `i8* read`.  The
compiler can then specialize / inline / otherwise optimize that
specific call to `@calc` with the assumption that all stores through a
pointer (in the context of this specific call) of type `i8* read` are
`unreachable`.

I agree that this is fairly complex, especially for a low level IR.
But the key problem with `readonly` is that there is no run-time
mirror of the `readonly`ness of an SSA value (we cannot implement a
`is_readonly` predicate to call at runtime), so we have to have it present in
the type system all the way.  `nonnull` or `dereferenceable` do not
have the same problem because they are run-time properties (though
implementing `is_dereferenceable` may be difficult in practice).

-- Sanjoy
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: [cfe-dev] Clang devirtualization proposal

Sanjoy Das
On Sat, Aug 1, 2015 at 2:05 PM, Sanjoy Das
<[hidden email]> wrote:

>> The trouble is that we want to express ideas like "at this call site, but
>> not others, I know that this call will not mutate state through this
>> pointer". We can't express that with the llvm type system we have today.
>
> Yes; to do that we'll effectively have to introduce some form of
> quantification.
>
> IOW: we'd have to have 4x the number of pointer types we have today --
> each pointer type should be quantifiable with `noaccess`, `read`,
> `write` and `readwrite` (the second one may not be very useful if we
> do not want to support memory with only `PROT_WRITE`).
>
> Functions and other consumers types would then have to be modified to
> allow universal (and other forms of?) quantification.  I should be able to
> write a function `@calc` of the type:

I'm not going to derail this thread further, except this one last mail
** (we can talk off list or on another thread if this looks
interesting to you): what I said about quantification won't work
directly -- we'll have problems with pointer comparison for starters.
For instance, if we have a function of type

forall $domain in { noaccess, read, write, readwrite }, forall
$domain2 in { noaccess, read, write, readwrite }: (i8* $domain, i8*
$domain2) -> i32

that wants to compare its first two arguments, then such a comparison
will be well typed only if both $domain and $domain2 are same.  In
other words, only 4 out of the sixteen possible instantiations will be
well typed, so the quantification is not really forall but something
else.

But I don't see any direct, incremental way to make the current
function argument "readonly" consistent.  Semantically, we'd like to
say that programs that store through readonly *SSA values* are
undefined, but unless we track some extra information at runtime,
there is no way to tell if a store to a location happened through
readonly SSA value, or through a normal, read-write SSA value that
happened to evaluate to something that a readonly SSA value also
evaluates to.

For instance, here is another example that's problematic:

define void @f(i8* readonly %ro) {
 i8* %rw = some_computation()
 %ptr = select condition, %ro, %rw;

  ;; work

  *(%ptr) = 42
}

There is no way to know if the store has UB or not without keeping
track of condition till the store.  If the select was instead was
br-phi then we'd have to manufacture a value to keep track what %ptr
is.  Note that %rw can be == %ro, so you cannot just inspecting the
value of %ptr is not enough.

In fact, with readonly, I think mem2reg is also problematic:

define void @f(i8* readonly %ro) {
 %t = alloca
 store %ro to %t

 %ptr = load %t
  store 24 to %ptr
}

The store does not happen through the pointer argument, so the above
program is well defined.  But it becomes undefined after mem2reg
(unless it has special handling for this situation).

** it always is "one last mail" :)

-- Sanjoy
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: [llvm-dev] [cfe-dev] [LLVMdev] Clang devirtualization proposal

David Blaikie via llvm-dev
In reply to this post by Hal Finkel
On Sat, Aug 1, 2015 at 6:39 AM Hal Finkel <[hidden email]> wrote:
----- Original Message -----
> From: "Sanjoy Das" <[hidden email]>
> To: "Reid Kleckner" <[hidden email]>
> Cc: "Piotr Padlewski" <[hidden email]>, "[hidden email] Developers" <[hidden email]>, "LLVM Developers
> Mailing List" <[hidden email]>
> 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 <[hidden email]>
> 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

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|

Re: [llvm-dev] [cfe-dev] [LLVMdev] Clang devirtualization proposal

David Blaikie via llvm-dev
In reply to this post by Piotr Padlewski
----- Original Message -----

> From: "Chandler Carruth" <[hidden email]>
> To: "Hal Finkel" <[hidden email]>, "Sanjoy Das" <[hidden email]>
> Cc: "[hidden email] Developers" <[hidden email]>, "LLVM Developers Mailing List" <[hidden email]>
> 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 < [hidden email] > wrote:
>  
> ----- Original Message -----
> > From: "Sanjoy Das" < [hidden email] >
> > To: "Reid Kleckner" < [hidden email] >
> > Cc: "Piotr Padlewski" < [hidden email] >, " [hidden email]
> > Developers" < [hidden email] >, "LLVM Developers
> > Mailing List" < [hidden email] >
> > 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 < [hidden email] >
> > 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
> > [hidden email] 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
> [hidden email]
> http://lists.cs.uiuc.edu/mailman/listinfo/cfe-dev
>

--
Hal Finkel
Assistant Computational Scientist
Leadership Computing Facility
Argonne National Laboratory
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|

Re: [llvm-dev] [cfe-dev] [LLVMdev] Clang devirtualization proposal

David Blaikie via llvm-dev


On Fri, Aug 7, 2015 at 5:21 PM, Hal Finkel <[hidden email]> wrote:
----- Original Message -----
> From: "Chandler Carruth" <[hidden email]>
> To: "Hal Finkel" <[hidden email]>, "Sanjoy Das" <[hidden email]>
> Cc: "[hidden email] Developers" <[hidden email]>, "LLVM Developers Mailing List" <[hidden email]>
> 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 < [hidden email] > wrote:
>
> ----- Original Message -----
> > From: "Sanjoy Das" < [hidden email] >
> > To: "Reid Kleckner" < [hidden email] >
> > Cc: "Piotr Padlewski" < [hidden email] >, " [hidden email]
> > Developers" < [hidden email] >, "LLVM Developers
> > Mailing List" < [hidden email] >
> > 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 < [hidden email] >
> > 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
> > [hidden email] 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
> [hidden email]
> http://lists.cs.uiuc.edu/mailman/listinfo/cfe-dev
>

--
Hal Finkel
Assistant Computational Scientist
Leadership Computing Facility
Argonne National Laboratory
_______________________________________________
cfe-dev mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev


_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|

Re: [llvm-dev] [cfe-dev] [LLVMdev] Clang devirtualization proposal

David Blaikie via llvm-dev
In reply to this post by David Blaikie via llvm-dev
On Fri, Aug 7, 2015 at 5:21 PM Hal Finkel <[hidden email]> wrote:
----- Original Message -----
> From: "Chandler Carruth" <[hidden email]>
> To: "Hal Finkel" <[hidden email]>, "Sanjoy Das" <[hidden email]>
> Cc: "[hidden email] Developers" <[hidden email]>, "LLVM Developers Mailing List" <[hidden email]>
> 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 < [hidden email] > wrote:
>
> ----- Original Message -----
> > From: "Sanjoy Das" < [hidden email] >
> > To: "Reid Kleckner" < [hidden email] >
> > Cc: "Piotr Padlewski" < [hidden email] >, " [hidden email]
> > Developers" < [hidden email] >, "LLVM Developers
> > Mailing List" < [hidden email] >
> > 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 < [hidden email] >
> > 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
> > [hidden email] 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
> [hidden email]
> http://lists.cs.uiuc.edu/mailman/listinfo/cfe-dev
>

--
Hal Finkel
Assistant Computational Scientist
Leadership Computing Facility
Argonne National Laboratory

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|

Re: [llvm-dev] [cfe-dev] [LLVMdev] Clang devirtualization proposal

David Blaikie via llvm-dev
In reply to this post by David Blaikie via llvm-dev


----- Original Message -----

> From: "David Majnemer" <[hidden email]>
> To: "Hal Finkel" <[hidden email]>
> Cc: "Chandler Carruth" <[hidden email]>, "llvm-dev" <[hidden email]>, "Sanjoy Das"
> <[hidden email]>, [hidden email]
> 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 < [hidden email] > wrote:
>
>
> ----- Original Message -----
> > From: "Chandler Carruth" < [hidden email] >
> > To: "Hal Finkel" < [hidden email] >, "Sanjoy Das" <
> > [hidden email] >
> > Cc: " [hidden email] Developers" < [hidden email] >,
> > "LLVM Developers Mailing List" < [hidden email] >
> > 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 < [hidden email] >
> > wrote:
> >
> > ----- Original Message -----
> > > From: "Sanjoy Das" < [hidden email] >
> > > To: "Reid Kleckner" < [hidden email] >
> > > Cc: "Piotr Padlewski" < [hidden email] >, "
> > > [hidden email]
> > > Developers" < [hidden email] >, "LLVM Developers
> > > Mailing List" < [hidden email] >
> > > 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 < [hidden email] >
> > > 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
> > > [hidden email] 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
> > [hidden email]
> > http://lists.cs.uiuc.edu/mailman/listinfo/cfe-dev
> >
>
> --
> Hal Finkel
> Assistant Computational Scientist
> Leadership Computing Facility
> Argonne National Laboratory
> _______________________________________________
> cfe-dev mailing list
> [hidden email]
> http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev
>
>

--
Hal Finkel
Assistant Computational Scientist
Leadership Computing Facility
Argonne National Laboratory
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|

Re: [llvm-dev] [cfe-dev] [LLVMdev] Clang devirtualization proposal

David Blaikie via llvm-dev
In reply to this post by David Blaikie via llvm-dev


From: "Chandler Carruth" <[hidden email]>
To: "Hal Finkel" <[hidden email]>
Cc: "Sanjoy Das" <[hidden email]>, "llvm-dev" <[hidden email]>, [hidden email]
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 <[hidden email]> wrote:


> From: "Chandler Carruth" <[hidden email]>
> To: "Hal Finkel" <[hidden email]>, "Sanjoy Das" <[hidden email]>
> Cc: "[hidden email] Developers" <[hidden email]>, "LLVM Developers Mailing List" <[hidden email]>
> 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 < [hidden email] > wrote:
>
> ----- Original Message -----
> > From: "Sanjoy Das" < [hidden email] >
> > To: "Reid Kleckner" < [hidden email] >
> > Cc: "Piotr Padlewski" < [hidden email] >, " [hidden email]
> > Developers" < [hidden email] >, "LLVM Developers
> > Mailing List" < [hidden email] >
> > 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 < [hidden email] >
> > 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
> > [hidden email] 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
> [hidden email]
> 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

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|

Re: [llvm-dev] [cfe-dev] [LLVMdev] Clang devirtualization proposal

David Blaikie via llvm-dev
Summing up, it seems there are three choices here that are all reasonably defensible:

1) We can change how CSE works such that equality is not sufficient for substitutability.
2) We can change the requirements of 'readonly' (and related) parameter attribute to be that the *memory location* is not modified by the function.
3) We can change argument elimination to not eliminate dead arguments which might change the set of memory locations which can be read or written by the function.

The only one of these I see as completely infeasible is #1.

For #3, this is at odds with how I understand dereferencable works, and it seems like these should work the same way and dereferencable had particularly good reasons to need to work the way it does.

For #2, it really does make inference significantly more tricky. Here is an example of the new challenges: if the caller has already escaped a pointer to the memory location (which we must assume it has) then any function which might write to memory must be assumed to write to the memory aliased by the passed in pointer.

Also for #2, we should probably finish converging with dereferencable and have a size attached. This will become especially important with type-less pointers.

I suspect #2 is the right design, mostly because I suspect most of the interesting and important inference cases are going to be cases where we can easily infer the stronger guarantee, and once inferred we will have much more freedom to optimize based on this stronger guarantee... But I can't say I'm completely confident in this model yet.

-Chandler

On Fri, Aug 7, 2015 at 6:03 PM Hal Finkel <[hidden email]> wrote:
From: "Chandler Carruth" <[hidden email]>
To: "Hal Finkel" <[hidden email]>
Cc: "Sanjoy Das" <[hidden email]>, "llvm-dev" <[hidden email]>, [hidden email]
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 <[hidden email]> wrote:

> From: "Chandler Carruth" <[hidden email]>
> To: "Hal Finkel" <[hidden email]>, "Sanjoy Das" <[hidden email]>
> Cc: "[hidden email] Developers" <[hidden email]>, "LLVM Developers Mailing List" <[hidden email]>
> 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 < [hidden email] > wrote:
>
> ----- Original Message -----
> > From: "Sanjoy Das" < [hidden email] >
> > To: "Reid Kleckner" < [hidden email] >
> > Cc: "Piotr Padlewski" < [hidden email] >, " [hidden email]
> > Developers" < [hidden email] >, "LLVM Developers
> > Mailing List" < [hidden email] >
> > 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 < [hidden email] >
> > 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
> > [hidden email] 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
> [hidden email]
> 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

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|

Re: [llvm-dev] [cfe-dev] [LLVMdev] Clang devirtualization proposal

David Blaikie via llvm-dev
> I suspect #2 is the right design, mostly because I suspect most of the interesting and important inference cases are going to be cases where we can easily infer the stronger guarantee, and once inferred we will have much more freedom to optimize based on this stronger guarantee...

Can't the stronger guarantee be represented in the existing system by either:

* Adding 'readonly' to all the aliasing pointer arguments.
* Adding 'noalias' to the pointer argument (if there aren't any
aliasing pointer arguments).

The proposal sounds interesting but it seems like it would prevent
languages with strong versions of 'const' (or similar) from marking
pointers as 'readonly', which might be a useful parameter attribute
for APIs (i.e. function declarations where inference isn't possible).

I may not have followed the discussion completely, but would it be
possible to simply strip the 'readonly' attributes when dead arguments
are eliminated?

On Sat, Aug 8, 2015 at 2:27 AM, Chandler Carruth <[hidden email]> wrote:

> Summing up, it seems there are three choices here that are all reasonably
> defensible:
>
> 1) We can change how CSE works such that equality is not sufficient for
> substitutability.
> 2) We can change the requirements of 'readonly' (and related) parameter
> attribute to be that the *memory location* is not modified by the function.
> 3) We can change argument elimination to not eliminate dead arguments which
> might change the set of memory locations which can be read or written by the
> function.
>
> The only one of these I see as completely infeasible is #1.
>
> For #3, this is at odds with how I understand dereferencable works, and it
> seems like these should work the same way and dereferencable had
> particularly good reasons to need to work the way it does.
>
> For #2, it really does make inference significantly more tricky. Here is an
> example of the new challenges: if the caller has already escaped a pointer
> to the memory location (which we must assume it has) then any function which
> might write to memory must be assumed to write to the memory aliased by the
> passed in pointer.
>
> Also for #2, we should probably finish converging with dereferencable and
> have a size attached. This will become especially important with type-less
> pointers.
>
> I suspect #2 is the right design, mostly because I suspect most of the
> interesting and important inference cases are going to be cases where we can
> easily infer the stronger guarantee, and once inferred we will have much
> more freedom to optimize based on this stronger guarantee... But I can't say
> I'm completely confident in this model yet.
>
> -Chandler
>
> On Fri, Aug 7, 2015 at 6:03 PM Hal Finkel <[hidden email]> wrote:
>>
>> From: "Chandler Carruth" <[hidden email]>
>> To: "Hal Finkel" <[hidden email]>
>>
>> Cc: "Sanjoy Das" <[hidden email]>, "llvm-dev"
>> <[hidden email]>, [hidden email]
>> 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 <[hidden email]> wrote:
>>>
>>>
>>> > From: "Chandler Carruth" <[hidden email]>
>>> > To: "Hal Finkel" <[hidden email]>, "Sanjoy Das"
>>> > <[hidden email]>
>>> > Cc: "[hidden email] Developers" <[hidden email]>, "LLVM
>>> > Developers Mailing List" <[hidden email]>
>>> > 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 < [hidden email] > wrote:
>>> >
>>> > ----- Original Message -----
>>> > > From: "Sanjoy Das" < [hidden email] >
>>> > > To: "Reid Kleckner" < [hidden email] >
>>> > > Cc: "Piotr Padlewski" < [hidden email] >, " [hidden email]
>>> > > Developers" < [hidden email] >, "LLVM Developers
>>> > > Mailing List" < [hidden email] >
>>> > > 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 < [hidden email] >
>>> > > 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
>>> > > [hidden email] 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
>>> > [hidden email]
>>> > 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
>
>
> _______________________________________________
> cfe-dev mailing list
> [hidden email]
> http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev
>
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|

Re: [llvm-dev] [cfe-dev] [LLVMdev] Clang devirtualization proposal

David Blaikie via llvm-dev
On Sat, Aug 8, 2015 at 8:03 AM, Stephen Cross <[hidden email]> wrote:
I may not have followed the discussion completely, but would it be
possible to simply strip the 'readonly' attributes when dead arguments
are eliminated?

I think this actually works. Think of it this way: the result of functionattrs is actually an analysis that we cache and maintain in the IR. DAE invalidates that analysis, so it must flush the cache or repopulate it. 

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|

Re: [llvm-dev] [cfe-dev] [LLVMdev] Clang devirtualization proposal

David Blaikie via llvm-dev
Hi all,
I am finishing my internship today and I want to make small report:

1. available_externally vtables are now generated for classes without inline / hidden virtual functions
2. Assumption loads are generated for the same case as above (temporary works only with -fstrict-vtable-pointers because of some performance lose in InstCombine)
3. Using invariant.group metadata, vtable loads and vfunction loads are now squashed to one load across one BB.

If someone would like to contact me, [hidden email] is my personal email (I won't have access to [hidden email])

Piotr Padlewski

On Tue, Aug 11, 2015 at 9:54 AM, Reid Kleckner <[hidden email]> wrote:
On Sat, Aug 8, 2015 at 8:03 AM, Stephen Cross <[hidden email]> wrote:
I may not have followed the discussion completely, but would it be
possible to simply strip the 'readonly' attributes when dead arguments
are eliminated?

I think this actually works. Think of it this way: the result of functionattrs is actually an analysis that we cache and maintain in the IR. DAE invalidates that analysis, so it must flush the cache or repopulate it. 

_______________________________________________
cfe-dev mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev



_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|

Re: [llvm-dev] [cfe-dev] [LLVMdev] Clang devirtualization proposal

David Blaikie via llvm-dev
Thanks for sharing your progress and all the work along the way.

On 10/02/2015 03:50 PM, Piotr Padlewski via llvm-dev wrote:
Hi all,
I am finishing my internship today and I want to make small report:

1. available_externally vtables are now generated for classes without inline / hidden virtual functions
2. Assumption loads are generated for the same case as above (temporary works only with -fstrict-vtable-pointers because of some performance lose in InstCombine)
Is there a bug filed for this?
3. Using invariant.group metadata, vtable loads and vfunction loads are now squashed to one load across one BB.

If someone would like to contact me, [hidden email] is my personal email (I won't have access to [hidden email])

Piotr Padlewski

On Tue, Aug 11, 2015 at 9:54 AM, Reid Kleckner <[hidden email]> wrote:
On Sat, Aug 8, 2015 at 8:03 AM, Stephen Cross <[hidden email]> wrote:
I may not have followed the discussion completely, but would it be
possible to simply strip the 'readonly' attributes when dead arguments
are eliminated?

I think this actually works. Think of it this way: the result of functionattrs is actually an analysis that we cache and maintain in the IR. DAE invalidates that analysis, so it must flush the cache or repopulate it. 

_______________________________________________
cfe-dev mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev




_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev


_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
12