[cfe-dev] [LLVMdev] Clang devirtualization proposal

[Hal Finkel]

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