On 10/21/2014 01:44 PM, Andrew Trick wrote:>> On Oct 21, 2014, at 11:46 AM, Sanjoy Das <sanjoy at playingwithpointers.com> wrote: >> >> Thank you for the explanation, I think I misunderstood your solution >> initially. Is it accurate to say: by making the definition of the >> source pointer of an !invariant load control (or data) dependent on >> some initialization event, you can effectively separate the >> initialization event (where the location is not invariant) and the >> rest of the execution (where the location is invariant). >> >> This approach looks similar to Ruby's "freeze" method: >> http://ruby-doc.org/core-2.1.3/Object.html#method-i-freeze >> >> What is the aliasing relationship between a non-invariant load from >> the result of a safe_cast and a load from (or store to) the argument >> we pass to it? Is it sensible to make them MustAlias? I'm trying to >> think if a frontend needs to be careful about using the return value >> of check_cast only for !invariant loads (or some other restriction), >> or is it legal (or desirable) to mix and match both kinds of loads >> from both kinds of pointers. > %p1 = ... > store %v0, %p1 > %p2 = llvm.safe_cast %p1 > store %v1, %p1 > store %v2, %p2 > %v3 = load %p2, !invariant > > The load can be moved above both stores (%v1 and %v2). AFAIK, the invariant metadata tag essentially tells alias analysis not to even try, just assume no aliasing. So the semantics effectively guarantee that %v0==%v1==%v3==%v3. The IR is still “legal” in that it is verifiable, but it is nonsense. > > Note that it is also totally valid for an alias analysis to return that they MustAlias. That would allow forwarding from store %v0 to the load. This would have to be implemented as a special case, since the invariant tag normally bypasses pointer analysis. I admit this is weird, but I’m don’t know of any problems it will cause. This can already happen with TBAA, and will be a problem with any metadata that can be abused by the frontend or language design. A difficultly with this approach is that the frontend has the burden for emitting guards anywhere the “invariant” data could be modified. > > How do you imagine mixing and matching invariant and non-invariant? I showed some examples of doing that safely, but I’m not sure how it’s relevant to you. > > -AndyOk, I'm catching up on this thread. Let me summarize a couple of things I noticed while reading. Sanjoy made a good point. We don't actually need a new variant of "invariant.start". Simply using an invariant.start with no uses gives us a notion of an invariant region with no end. (Since the result doesn't escape, there can be no end hidden inside a function call.) This seems like a simple notion to exploit and is strict step forward from where we are, without a new intrinsic. The notions of "invariant over some range" and "safe to speculate over some range" are related, but distinct. However, to get the most power out of the former, you often need the later. Andy seems to be arguing in favour of data flow mostly because it's easier for the optimizer. Unless I'm misreading, there's nothing preventing us from using control flow for the same patterns. For example: p1 = ... *p1 = 5 p2 = llvm.safe_cast p1 p3 = select is_constant p2, p1 load p3 Is isomorphic with: p1 = ... *p1 = 5 if is_constant: invariant.start(p1) load p1 Andy, is this correct? Or am I missing something? (p.s. You guys seem to be throwing around the terms "!invariant" and "invariant load" without clearly defining them. I'm unsure if you mean the same things.) I suspect this is going to be a topic we should discuss in person at the developers conference or over a beer at a social. It's a bit complicated to keep track of in email. My belief is that a path sensitive invariant indicator for a memory location is probably sufficient for most use cases. In particular, the initialization and use logic is usually not in the same compilation for the cases I care about. I care that such cases are *possible*, but I'm less concerned about them being *easy*. I'm also having real trouble find examples of cases where Andy's "conditionally invariant data" is useful. Given that we *have an existing* mechanism which only needs a slightly tweak for "endless" invariant regions, I'm tempted to stick with what we have. The only change (clarification?) I'd make to the current scheme is to specify that a location is both invariant *and dereferenceable* at the point it is listed in an invariant.start. This enables speculative loading up to that construct. I think this is actually what the current intrinsic is trying for from the documentation. (Hm.. it does make it hard to rearrange calls to invariant.start though... Thoughts?) I suspect that for the Array.length case, I'd probably do something like this: arr = function_that_returns_array(); invariant.start(arr.length) ... arbitrary control flow ... length = arr.length ... arbitrary control flow ... length2 = arr.length My reasoning here is that if something returns an array (in this compilation) I want the invariant fact to be visible. If that factory function gets inlined, I'd end up with: arr = new Array; arr.length = X; invariant.start(arr.length) ... arbitrary control flow ... length = arr.length ... arbitrary control flow ... length2 = arr.length Both cases seem nearly ideal here. I know I can lift the loads as far as the function which returns the base pointer. I know I can value forward loads (either with or without lifting). I know I can value forward the store to the load (as I normally would). In terms of aliasing, it seems like having invariant.start read from it's arguments memory is sufficient. That prevents reorderings of stores to that location before the address to after the invariant.start. Due to conservative aliasing, that might be somewhat harmful, but I don't really see a way to avoid this... (Or is this the point Andy's trying to solve with the data flow?) I don't have a sense for how painful this is. Try it and see? I could see a useful extension for a function attribute (type?, TBAA?) for describing the return value's invariant fields (*at the point of the return*), but that is more minor goodness for IR size then clearly necessary. Philip
> On Oct 21, 2014, at 4:03 PM, Philip Reames <listmail at philipreames.com> wrote: > > > On 10/21/2014 01:44 PM, Andrew Trick wrote: >>> On Oct 21, 2014, at 11:46 AM, Sanjoy Das <sanjoy at playingwithpointers.com> wrote: >>> >>> Thank you for the explanation, I think I misunderstood your solution >>> initially. Is it accurate to say: by making the definition of the >>> source pointer of an !invariant load control (or data) dependent on >>> some initialization event, you can effectively separate the >>> initialization event (where the location is not invariant) and the >>> rest of the execution (where the location is invariant). >>> >>> This approach looks similar to Ruby's "freeze" method: >>> http://ruby-doc.org/core-2.1.3/Object.html#method-i-freeze >>> >>> What is the aliasing relationship between a non-invariant load from >>> the result of a safe_cast and a load from (or store to) the argument >>> we pass to it? Is it sensible to make them MustAlias? I'm trying to >>> think if a frontend needs to be careful about using the return value >>> of check_cast only for !invariant loads (or some other restriction), >>> or is it legal (or desirable) to mix and match both kinds of loads >>> from both kinds of pointers. >> %p1 = ... >> store %v0, %p1 >> %p2 = llvm.safe_cast %p1 >> store %v1, %p1 >> store %v2, %p2 >> %v3 = load %p2, !invariant >> >> The load can be moved above both stores (%v1 and %v2). AFAIK, the invariant metadata tag essentially tells alias analysis not to even try, just assume no aliasing. So the semantics effectively guarantee that %v0==%v1==%v3==%v3. The IR is still “legal” in that it is verifiable, but it is nonsense. >> >> Note that it is also totally valid for an alias analysis to return that they MustAlias. That would allow forwarding from store %v0 to the load. This would have to be implemented as a special case, since the invariant tag normally bypasses pointer analysis. I admit this is weird, but I’m don’t know of any problems it will cause. This can already happen with TBAA, and will be a problem with any metadata that can be abused by the frontend or language design. A difficultly with this approach is that the frontend has the burden for emitting guards anywhere the “invariant” data could be modified. >> >> How do you imagine mixing and matching invariant and non-invariant? I showed some examples of doing that safely, but I’m not sure how it’s relevant to you. >> >> -Andy > Ok, I'm catching up on this thread. Let me summarize a couple of things I noticed while reading. > > Sanjoy made a good point. We don't actually need a new variant of "invariant.start". Simply using an invariant.start with no uses gives us a notion of an invariant region with no end. (Since the result doesn't escape, there can be no end hidden inside a function call.) This seems like a simple notion to exploit and is strict step forward from where we are, without a new intrinsic. > > The notions of "invariant over some range" and "safe to speculate over some range" are related, but distinct. However, to get the most power out of the former, you often need the later.Yes. Exactly.> Andy seems to be arguing in favour of data flow mostly because it's easier for the optimizer. Unless I'm misreading, there's nothing preventing us from using control flow for the same patterns. For example: > p1 = ... > *p1 = 5 > p2 = llvm.safe_cast p1 > p3 = select is_constant p2, p1 > load p3 > > Is isomorphic with: > p1 = ... > *p1 = 5 > if is_constant: > invariant.start(p1) > load p1 > > Andy, is this correct? Or am I missing something?Yes, you are missing my main point. In the first case, you can actually mark load p3 with the !invariant tag. The cast and load don’t need to be in the same scope.> (p.s. You guys seem to be throwing around the terms "!invariant" and "invariant load" without clearly defining them. I'm unsure if you mean the same things.)Were talking about two things - loads of data that is known to be immutable, path sensitive - load that are marked with !invariant metadata (I often say “invariant load” because !invariant looks like “not invariant”)> I suspect this is going to be a topic we should discuss in person at the developers conference or over a beer at a social. It's a bit complicated to keep track of in email.Definitely. I am not at all opposed to an assert_immutable intrinsic. I just don’t think it will be performant for the three reasons I stated in the previous email.> In terms of aliasing, it seems like having invariant.start read from it's arguments memory is sufficient. That prevents reorderings of stores to that location before the address to after the invariant.start. Due to conservative aliasing, that might be somewhat harmful, but I don't really see a way to avoid this... (Or is this the point Andy's trying to solve with the data flow?) I don't have a sense for how painful this is. Try it and see? > > I could see a useful extension for a function attribute (type?, TBAA?) for describing the return value's invariant fields (*at the point of the return*), but that is more minor goodness for IR size then clearly necessary.invariant.start/assert_immutable has to write to memory to get the semantics you want. “maythrow” is insufficient (see previous message). I proposed new semantics based on TBAA tags as a partial fix for this problem. -Andy> My belief is that a path sensitive invariant indicator for a memory location is probably sufficient for most use cases. In particular, the initialization and use logic is usually not in the same compilation for the cases I care about. I care that such cases are *possible*, but I'm less concerned about them being *easy*. I'm also having real trouble find examples of cases where Andy's "conditionally invariant data" is useful. Given that we *have an existing* mechanism which only needs a slightly tweak for "endless" invariant regions, I'm tempted to stick with what we have. > > The only change (clarification?) I'd make to the current scheme is to specify that a location is both invariant *and dereferenceable* at the point it is listed in an invariant.start. This enables speculative loading up to that construct. I think this is actually what the current intrinsic is trying for from the documentation. > > (Hm.. it does make it hard to rearrange calls to invariant.start though... Thoughts?) > > I suspect that for the Array.length case, I'd probably do something like this: > arr = function_that_returns_array(); > invariant.start(arr.length) > ... arbitrary control flow ... > length = arr.length > ... arbitrary control flow ... > length2 = arr.length > > My reasoning here is that if something returns an array (in this compilation) I want the invariant fact to be visible. If that factory function gets inlined, I'd end up with: > arr = new Array; > arr.length = X; > invariant.start(arr.length) > ... arbitrary control flow ... > length = arr.length > ... arbitrary control flow ... > length2 = arr.length > > Both cases seem nearly ideal here. I know I can lift the loads as far as the function which returns the base pointer. I know I can value forward loads (either with or without lifting). I know I can value forward the store to the load (as I normally would). > > > > Philip > > > > > > > >
> On Oct 21, 2014, at 4:03 PM, Philip Reames <listmail at philipreames.com> wrote: > > Sanjoy made a good point. We don't actually need a new variant of "invariant.start". Simply using an invariant.start with no uses gives us a notion of an invariant region with no end. (Since the result doesn't escape, there can be no end hidden inside a function call.) This seems like a simple notion to exploit and is strict step forward from where we are, without a new intrinsic.I'm coming back to this because it is a sticking point for me in all of the proposals that were floated informally on the commits list. I would really like this to work, but can't prove that it's safe. Given: %a = newArray() %pLen = gep(%a, <length offset>) invariant.start(<size>, %pLen) %len = load %pLen %o = foo() // may deallocate %a store %something load %o I want to claim that the LLVM optimizer cannot do the following (but don't have a complete line of reasoning yet): %a = newArray() %pLen = gep(%a, <length offset>) invariant.start(<size>, %pLen) %len = load %pLen %o = foo() // may deallocate %a if ptrtoint(%o) == ptrtoint(%pLen) load %pLen store %something // Oops... this might alias else store %something load %o Either we need to make a convincing argument, or bail on most of the tentative proposals for expressing invariance, and resort to generating IR like this: %a = newArray() %pLen = gep(%a, <length offset>) %t = invariant.start(<size>, %pLen) %len = load %pLen %o = foo() // may deallocate %a invariant.end(%t, <size>, %pLen) store %something load %o ...which is pretty painful to implement and may be very difficult to optimize. -Andy -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20141201/baf5fec6/attachment.html>
On 12/01/2014 11:14 AM, Andrew Trick wrote:> >> On Oct 21, 2014, at 4:03 PM, Philip Reames <listmail at philipreames.com >> <mailto:listmail at philipreames.com>> wrote: >> >> Sanjoy made a good point. We don't actually need a new variant of >> "invariant.start". Simply using an invariant.start with no uses >> gives us a notion of an invariant region with no end. (Since the >> result doesn't escape, there can be no end hidden inside a function >> call.) This seems like a simple notion to exploit and is strict >> step forward from where we are, without a new intrinsic. > > I'm coming back to this because it is a sticking point for me in all > of the proposals that were floated informally on the commits list. I > would really like this to work, but can't prove that it's safe.As I said in the other thread, !invariant.load and llvm.invariant.* are not the same. This thread is discussing the later, not the former. The other thread is discussing the former, but not the later.> > Given: > > %a = newArray() > %pLen = gep(%a, <length offset>) > invariant.start(<size>, %pLen) > %len = load %pLen > > %o = foo() // may deallocate %a > store %something > load %o > > I want to claim that the LLVM optimizer cannot do the following (but > don't have a complete line of reasoning yet): > > %a = newArray() > %pLen = gep(%a, <length offset>) > invariant.start(<size>, %pLen) > %len = load %pLen > > %o = foo() // may deallocate %a > if ptrtoint(%o) == ptrtoint(%pLen) > load %pLen > store %something // Oops... this might alias > else > store %something > load %oJust to make sure we're on the same page, it *would* be legal for the optimizer to construct: %a = newArray() %pLen = gep(%a, <length offset>) invariant.start(<size>, %pLen) %len = load %pLen %o = foo() // may deallocate %a if ptrtoint(%o) == ptrtoint(%pLen) store %something // Oops... this might alias load %pLen <--- This is now after the store else store %something load %o Are we in agreement here? What is the argument that you see leading from the second to your problematic example? I'm missing the reasoning by which you got there. I agree that the example is problematic, I'm just not sure how it would arise.> > Either we need to make a convincing argument, or bail on most of the > tentative proposals for expressing invariance, and resort to > generating IR like this: > > %a = newArray() > %pLen = gep(%a, <length offset>) > %t = invariant.start(<size>, %pLen) > %len = load %pLen > > %o = foo() // may deallocate %a > invariant.end(%t, <size>, %pLen) > store %something > load %o > > ...which is pretty painful to implement and may be very difficult to > optimize. > > -Andy-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20141201/b377bf16/attachment.html>