[cfe-dev] [LLVMdev] Clang devirtualization proposal
Hal Finkel
hfinkel at anl.gov
Fri Aug 7 18:03:46 PDT 2015
----- 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/cfe-dev/attachments/20150807/73ca64ed/attachment.html>
More information about the cfe-dev
mailing list