On Fri, Jul 31, 2015 at 3:53 PM, Philip Reames <listmail at philipreames.com> wrote:> > I'm wondering if there's a problematic interaction with CSE here. > Consider this example is pseudo LLVM IR: > v1 = load i64, %p, !invariant.group !Type1 > ; I called destructor/placement new for the same type, but that optimized > entirely away > p2 = invariant.group.barrier(p1) > if (p1 != p2) return. > store i64 0, %p2, !invariant.group !Type1 > v2 = load i64, %p2, !invariant.group !Type1 > ret i64 v1 - v2 > > (Assume that !Type is used to describe a write once integer field within > some class. Not all instances have the same integer value.) > > Having CSE turn this into: > v1 = load i64, %p, !invariant.group !Type1 > p2 = invariant.group.barrier(p1) > if (p1 != p2) return. > store i64 0, %p1, !invariant.group !Type1 > v2 = load i64, %p1, !invariant.group !Type1 > ret i64 v1 - v2 > > And then GVN turn this into: > v1 = load i64, %p, !invariant.group !Type1 > p2 = invariant.group.barrier(p1) > if (p1 != p2) return. > ret i64 v1 - v1 (-> 0) > > This doesn't seem like the result I'd expect. Is there something about my > initial IR which is wrong/invalid in some way? Is the invariant.group > required to be specific to a single bitpattern across all usages within a > function/module/context? That would be reasonable, but I don't think is > explicit said right now. It also makes !invariant.group effectively > useless for describing constant fields which are constant per instance > rather than per-class. >Yes, this family of examples scares me. :) It seems we've discovered a new device testing IR soundness. We used it to build a test case that shows that 'readonly' on arguments without 'nocapture' doesn't let you forward stores across such a call. 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 ; Delete dead args void f(i32* readonly %a) { store i32 42 } ... %p = alloca i32 store i32 13, i32* %p call f(i32* readonly %p) %r = load i32, i32* %p ; Forward store %p to load %p, since the only use of %p is readonly void f(i32* readonly %a) { store i32 42 } ... %p = alloca i32 call f(i32* readonly %p) %r = i32 13 Today LLVM will not do the final transform because it requires readonly on the entire function, or nocapture on the argument. nocapture cannot be inferred due to the assume comparison. -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20150731/79a6f691/attachment.html>
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
----- 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. -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
Sanjoy Das wrote:> 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"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 > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev >