From: "Chandler Carruth" <chandlerc@google.com>
To: "Hal Finkel" <hfinkel@anl.gov>, "Sanjoy Das" <sanjoy@playingwithpointers.com>
Cc: "cfe-dev@cs.uiuc.edu Developers" <cfe-dev@cs.uiuc.edu>, "LLVM Developers Mailing List" <llvmdev@cs.uiuc.edu>
Sent: Friday, August 7, 2015 5:52:04 PM
Subject: Re: [cfe-dev] [LLVMdev] Clang devirtualization proposal> From: "Sanjoy Das" < sanjoy@playingwithpointers.com >
> To: "Reid Kleckner" < rnk@google.com >
> Cc: "Piotr Padlewski" < prazek@google.com >, " cfe-dev@cs.uiuc.edu
> Developers" < cfe-dev@cs.uiuc.edu >, "LLVM Developers
> Mailing List" < llvmdev@cs.uiuc.edu >
> Sent: Saturday, August 1, 2015 1:22:50 AM
> Subject: Re: [LLVMdev] [cfe-dev] Clang devirtualization proposal
>
> > 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