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* %pI'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). -- Sanjoy
On Sat, Aug 1, 2015 at 6:33 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.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
> 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
Chandler Carruth via llvm-dev
2015-Aug-07 22:55 UTC
[llvm-dev] [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. 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 -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20150807/c2b94012/attachment.html>