On 5 November 2014 12:48, Hal Finkel <hfinkel at anl.gov> wrote:> ----- Original Message ----- > > From: "Nick Lewycky" <nlewycky at google.com> > > To: "Hal Finkel" <hfinkel at anl.gov> > > Cc: "Reid Kleckner" <rnk at google.com>, "LLVM Developers Mailing List" < > llvmdev at cs.uiuc.edu> > > Sent: Wednesday, November 5, 2014 2:39:38 PM > > Subject: Re: [LLVMdev] lifetime.start/end clarification > > > > On 5 November 2014 11:51, Hal Finkel < hfinkel at anl.gov > wrote: > > > > > > ----- Original Message ----- > > > From: "Reid Kleckner" < rnk at google.com > > > > To: "Philip Reames" < listmail at philipreames.com > > > > Cc: "LLVM Developers Mailing List" < llvmdev at cs.uiuc.edu > > > > Sent: Wednesday, November 5, 2014 12:54:30 PM > > > Subject: Re: [LLVMdev] lifetime.start/end clarification > > > > > > This seems fine to me. The optimizer can (soundly) conclude that %p > > > is dead after the "lifetime.end" (for the two instructions), and > > > dead before the "lifetime.start" (for the *single* instruction in > > > that basic block, *not* for the previous BB). This seems like the > > > proper result for this example, am I missing something? > > > > > > > > > What if I put that in a loop, unroll it once, and prove that the > > > lifetime.start is unreachable? We would end up with IR like: > > > > > > > > > loop: > > > ... use %p > > > call void @lifetime.end( %p ) > > > > > > ... use %p > > > call void @lifetime.end( %p ) > > > br i1 %c, label %loop, label %exit > > > > > > > > > Are the second uses of %p uses of dead memory? > > > > > > > > > We have similar issues if the optimizer somehow removes the > > > lifetime > > > end and keeps the start: > > > > > > > > > > > > loop: > > > call void @lifetime.start( %p ) > > > > > > ... use %p > > > call void @lifetime.start( %p ) > > > > > > > > > ... use %p > > > br i1 %c, label %loop, label %exit > > > > > > > > > For this reason, it has been suggested that these intrinsics are > > > horribly broken, > > > > I disagree, these just seem like bugs. lifetime_start are marked as > > IntrReadWriteArgMem, but this is not really sufficient to prevent > > their removal should the memory be subsequently unused. Plus there > > are other places that just delete the lifetime intrinsics, like this > > in lib/Transforms/Scalar/SROA.cpp: > > > > // FIXME: Currently the SSAUpdater infrastructure doesn't reason > > about > > // lifetime intrinsics and so we strip them (and the bitcasts+GEPs > > // leading to them) here. Eventually it should use them to optimize > > the > > // scalar values produced. > > if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) { > > assert(II->getIntrinsicID() == Intrinsic::lifetime_start || > > II->getIntrinsicID() == Intrinsic::lifetime_end); > > II->eraseFromParent(); > > continue; > > } > > > > we need to go through the various places that might delete these > > intrinsics and fix them. The same will be true with any other > > mechanism. > > > > > > > > It removes them because it does (or will) remove the associated > > alloca anyways as part of turning loads and stores into SSA. There's > > no need for lifetime intrinsic equivalents on SSA given that we have > > use-lists and tools like the dominator tree. > > Good point, I did not think too carefully about what the code was doing, > but rather pointing out that there is special-case code dealing with > lifetime intrinsics that needs to be looked at, and code that does not deal > specifically with lifetime intrinsics that may have to do so. I certainly > agree that we don't need them for SSA values. > > For the code in question, I don't see why you wouldn't just RAUW the > alloca with undef and then let DCE remove the intrinsics (this is, however, > somewhat off-topic for this thread). > > > > > > > > > > > > and both should be remodeled to just mean "store of > > > undef bytes to this memory". > > > > This is a bad idea. Stores of undef bytes can be removed if we can > > prove that the address is dereferenceable. And if they can't be > > removed, then they have side effects that can't ever be removed. > > Please don't do that. > > > > I think the idea is to define them with the semantics of storing > > undef bytes, but keep them implemented as intrinsic function calls, > > so that the optimizer does not simply delete them. It's a way of > > communicating that these are deliberate and valuable stores to > > undef, as opposed to stores of SSA values that were later found to > > be undef. > > I did not get that impression, and if that is what was proposed, I don't > see how that differs, in practice, from what we have now. >The LangRef definition looks like that plus some special rules about how *all* uses before the start are dead. *The* start? What about multiple starts? What does it mean to have start/end/start/end? Can you use an alloca normally, then lifetime.start it? According to langref, no, *all* uses before the start may be nuked. It's a weird rule, but it's intended to support the use case of stack slot colouring, where your starts and ends are paired and tightly wrap the point where the variable is live. If you remove that oddity, lifetime.start and lifetime.end become semantically equivalent and both just mean "store undef there" and become straight-forward to reason about, though harder to use for stack slot colouring (it becomes a bidirectional data flow problem, which is hard on compile time). At this stage, I think the tradeoff is worthwhile. Thanks again,> Hal > > > > > > > > > -Hal > > > > > If "use %p" is a load, for example, in > > > both cases we can safely say it returns undef, because it's a > > > use-after-scope. > > > > > > > > > I think coming up with a new representation with simpler semantics > > > is > > > the way to go. One allocation or lifetime start, and one > > > deallocation and end. > > > > > > > > > Implementing this in Clang will be tricky, though. Clang's IRGen is > > > supposed to be a dumb AST walk, but it has already strayed from > > > that > > > path. Needs more thought... > > > _______________________________________________ > > > 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 > > > > > > _______________________________________________ > > 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 >-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20141105/ff383557/attachment.html>
----- Original Message -----> From: "Nick Lewycky" <nlewycky at google.com> > To: "Hal Finkel" <hfinkel at anl.gov> > Cc: "Reid Kleckner" <rnk at google.com>, "LLVM Developers Mailing List" <llvmdev at cs.uiuc.edu> > Sent: Wednesday, November 5, 2014 2:59:54 PM > Subject: Re: [LLVMdev] lifetime.start/end clarification > > On 5 November 2014 12:48, Hal Finkel < hfinkel at anl.gov > wrote: > > > ----- Original Message ----- > > From: "Nick Lewycky" < nlewycky at google.com > > > To: "Hal Finkel" < hfinkel at anl.gov > > > > > Cc: "Reid Kleckner" < rnk at google.com >, "LLVM Developers Mailing > > List" < llvmdev at cs.uiuc.edu > > > Sent: Wednesday, November 5, 2014 2:39:38 PM > > Subject: Re: [LLVMdev] lifetime.start/end clarification > > > > On 5 November 2014 11:51, Hal Finkel < hfinkel at anl.gov > wrote: > > > > > > ----- Original Message ----- > > > From: "Reid Kleckner" < rnk at google.com > > > > To: "Philip Reames" < listmail at philipreames.com > > > > Cc: "LLVM Developers Mailing List" < llvmdev at cs.uiuc.edu > > > > Sent: Wednesday, November 5, 2014 12:54:30 PM > > > Subject: Re: [LLVMdev] lifetime.start/end clarification > > > > > > This seems fine to me. The optimizer can (soundly) conclude that > > > %p > > > is dead after the "lifetime.end" (for the two instructions), and > > > dead before the "lifetime.start" (for the *single* instruction in > > > that basic block, *not* for the previous BB). This seems like the > > > proper result for this example, am I missing something? > > > > > > > > > What if I put that in a loop, unroll it once, and prove that the > > > lifetime.start is unreachable? We would end up with IR like: > > > > > > > > > loop: > > > ... use %p > > > call void @lifetime.end( %p ) > > > > > > ... use %p > > > call void @lifetime.end( %p ) > > > br i1 %c, label %loop, label %exit > > > > > > > > > Are the second uses of %p uses of dead memory? > > > > > > > > > We have similar issues if the optimizer somehow removes the > > > lifetime > > > end and keeps the start: > > > > > > > > > > > > loop: > > > call void @lifetime.start( %p ) > > > > > > ... use %p > > > call void @lifetime.start( %p ) > > > > > > > > > ... use %p > > > br i1 %c, label %loop, label %exit > > > > > > > > > For this reason, it has been suggested that these intrinsics are > > > horribly broken, > > > > I disagree, these just seem like bugs. lifetime_start are marked as > > IntrReadWriteArgMem, but this is not really sufficient to prevent > > their removal should the memory be subsequently unused. Plus there > > are other places that just delete the lifetime intrinsics, like > > this > > in lib/Transforms/Scalar/SROA.cpp: > > > > // FIXME: Currently the SSAUpdater infrastructure doesn't reason > > about > > // lifetime intrinsics and so we strip them (and the bitcasts+GEPs > > // leading to them) here. Eventually it should use them to optimize > > the > > // scalar values produced. > > if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) { > > assert(II->getIntrinsicID() == Intrinsic::lifetime_start || > > II->getIntrinsicID() == Intrinsic::lifetime_end); > > II->eraseFromParent(); > > continue; > > } > > > > we need to go through the various places that might delete these > > intrinsics and fix them. The same will be true with any other > > mechanism. > > > > > > > > It removes them because it does (or will) remove the associated > > alloca anyways as part of turning loads and stores into SSA. > > There's > > no need for lifetime intrinsic equivalents on SSA given that we > > have > > use-lists and tools like the dominator tree. > > Good point, I did not think too carefully about what the code was > doing, but rather pointing out that there is special-case code > dealing with lifetime intrinsics that needs to be looked at, and > code that does not deal specifically with lifetime intrinsics that > may have to do so. I certainly agree that we don't need them for SSA > values. > > For the code in question, I don't see why you wouldn't just RAUW the > alloca with undef and then let DCE remove the intrinsics (this is, > however, somewhat off-topic for this thread). > > > > > > > > > > > > and both should be remodeled to just mean "store of > > > undef bytes to this memory". > > > > This is a bad idea. Stores of undef bytes can be removed if we can > > prove that the address is dereferenceable. And if they can't be > > removed, then they have side effects that can't ever be removed. > > Please don't do that. > > > > I think the idea is to define them with the semantics of storing > > undef bytes, but keep them implemented as intrinsic function calls, > > so that the optimizer does not simply delete them. It's a way of > > communicating that these are deliberate and valuable stores to > > undef, as opposed to stores of SSA values that were later found to > > be undef. > > I did not get that impression, and if that is what was proposed, I > don't see how that differs, in practice, from what we have now. > > > > The LangRef definition looks like that plus some special rules about > how *all* uses before the start are dead. *The* start? What about > multiple starts? What does it mean to have start/end/start/end? Can > you use an alloca normally, then lifetime.start it? According to > langref, no, *all* uses before the start may be nuked.Ah, yes, good point.> It's a weird > rule, but it's intended to support the use case of stack slot > colouring, where your starts and ends are paired and tightly wrap > the point where the variable is live.Yes.> > If you remove that oddity, lifetime.start and lifetime.end become > semantically equivalent and both just mean "store undef there" and > become straight-forward to reason about, though harder to use for > stack slot colouring (it becomes a bidirectional data flow problem, > which is hard on compile time). At this stage, I think the tradeoff > is worthwhile.I'm unsure, but could easily agree. -Hal> > > > Thanks again, > Hal > > > > > > > > > > > -Hal > > > > > If "use %p" is a load, for example, in > > > both cases we can safely say it returns undef, because it's a > > > use-after-scope. > > > > > > > > > I think coming up with a new representation with simpler > > > semantics > > > is > > > the way to go. One allocation or lifetime start, and one > > > deallocation and end. > > > > > > > > > Implementing this in Clang will be tricky, though. Clang's IRGen > > > is > > > supposed to be a dumb AST walk, but it has already strayed from > > > that > > > path. Needs more thought... > > > _______________________________________________ > > > 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 > > > > > > _______________________________________________ > > 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 > >-- Hal Finkel Assistant Computational Scientist Leadership Computing Facility Argonne National Laboratory
On 11/05/2014 12:59 PM, Nick Lewycky wrote:> On 5 November 2014 12:48, Hal Finkel <hfinkel at anl.gov > <mailto:hfinkel at anl.gov>> wrote: > > ----- Original Message ----- > > From: "Nick Lewycky" <nlewycky at google.com > <mailto:nlewycky at google.com>> > > To: "Hal Finkel" <hfinkel at anl.gov <mailto:hfinkel at anl.gov>> > > Cc: "Reid Kleckner" <rnk at google.com <mailto:rnk at google.com>>, > "LLVM Developers Mailing List" <llvmdev at cs.uiuc.edu > <mailto:llvmdev at cs.uiuc.edu>> > > Sent: Wednesday, November 5, 2014 2:39:38 PM > > Subject: Re: [LLVMdev] lifetime.start/end clarification > > > > On 5 November 2014 11:51, Hal Finkel < hfinkel at anl.gov > <mailto:hfinkel at anl.gov> > wrote: > > > and both should be remodeled to just mean "store of > > > undef bytes to this memory". > > > > This is a bad idea. Stores of undef bytes can be removed if we can > > prove that the address is dereferenceable. And if they can't be > > removed, then they have side effects that can't ever be removed. > > Please don't do that. > > > > I think the idea is to define them with the semantics of storing > > undef bytes, but keep them implemented as intrinsic function calls, > > so that the optimizer does not simply delete them. It's a way of > > communicating that these are deliberate and valuable stores to > > undef, as opposed to stores of SSA values that were later found to > > be undef. > > I did not get that impression, and if that is what was proposed, I > don't see how that differs, in practice, from what we have now. > > > The LangRef definition looks like that plus some special rules about > how *all* uses before the start are dead. *The* start? What about > multiple starts? What does it mean to have start/end/start/end? Can > you use an alloca normally, then lifetime.start it? According to > langref, no, *all* uses before the start may be nuked. It's a weird > rule, but it's intended to support the use case of stack slot > colouring, where your starts and ends are paired and tightly wrap the > point where the variable is live.Er, what text are you referring to? I don't see anything like this in the intrinsics definition section. Could you quote exactly what you're referencing? This is the text I see for lifetime.start: "This intrinsic indicates that before this point in the code, the value of the memory pointed to by ptr is dead. This means that it is known to never be used and has an undefined value. A load from the pointer that precedes this intrinsic can be replaced with 'undef'."> > If you remove that oddity, lifetime.start and lifetime.end become > semantically equivalent and both just mean "store undef there" and > become straight-forward to reason about, though harder to use for > stack slot colouring (it becomes a bidirectional data flow problem, > which is hard on compile time). At this stage, I think the tradeoff is > worthwhile.Specifically what are you proposing? I have yet to see a clearly worded proposal here and it seems like different folks have different mental models. Could you spell out your desired semantics? Philip -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20141105/8b2c71d9/attachment.html>
On 11/05/2014 12:59 PM, Nick Lewycky wrote:> The LangRef definition looks like that plus some special rules about > how *all* uses before the start are dead. *The* start? What about > multiple starts? What does it mean to have start/end/start/end? Can > you use an alloca normally, then lifetime.start it? According to > langref, no, *all* uses before the start may be nuked. It's a weird > rule, but it's intended to support the use case of stack slot > colouring, where your starts and ends are paired and tightly wrap the > point where the variable is live.In my previous response, I'd missed this bit of text: "What does it mean to have start/end/start/end?" You're right, this is ill defined. This is an area which needs clarified. I'm still confused by the rest of your response. In particular, I don't see the text which inspires: "Can you use an alloca normally, then lifetime.start it?" The text doesn't talk about uses. It talks about values of *memory locations*. Philip
On 5 November 2014 13:37, Philip Reames <listmail at philipreames.com> wrote:> > On 11/05/2014 12:59 PM, Nick Lewycky wrote: > >> The LangRef definition looks like that plus some special rules about how >> *all* uses before the start are dead. *The* start? What about multiple >> starts? What does it mean to have start/end/start/end? Can you use an >> alloca normally, then lifetime.start it? According to langref, no, *all* >> uses before the start may be nuked. It's a weird rule, but it's intended to >> support the use case of stack slot colouring, where your starts and ends >> are paired and tightly wrap the point where the variable is live. >> > In my previous response, I'd missed this bit of text: > "What does it mean to have start/end/start/end?" > > You're right, this is ill defined. This is an area which needs clarified. > > I'm still confused by the rest of your response. In particular, I don't > see the text which inspires: > "Can you use an alloca normally, then lifetime.start it?" > > The text doesn't talk about uses. It talks about values of *memory > locations*.Sorry, I was unclear. I meant, suppose you alloca, then store to it, then load it, then call lifetime.start. The use of lifetime.start goes *back in time* and states that the memory has been undef up until that point. The load can be optimized away into undef. The store value can be optimized away into undef? What is going on? A simple fix is to define that all alloca's perform lifetime.start implicitly, but if that's so, then what does alloca+store+lifetime.start do? The intention of lifetime.start was to provide a way to eliminate a dead store before the lifetime.start, but now you can't because the memory was live at the time due to the implicit lifetime.start in the alloca. -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20141105/2518ad88/attachment.html>
On Wed, Nov 5, 2014 at 3:06 PM, Hal Finkel <hfinkel at anl.gov> wrote:> > It's a weird > > rule, but it's intended to support the use case of stack slot > > colouring, where your starts and ends are paired and tightly wrap > > the point where the variable is live. > > Yes. > > > > > If you remove that oddity, lifetime.start and lifetime.end become > > semantically equivalent and both just mean "store undef there" and > > become straight-forward to reason about, though harder to use for > > stack slot colouring (it becomes a bidirectional data flow problem, > > which is hard on compile time). At this stage, I think the tradeoff > > is worthwhile. > > I'm unsure, but could easily agree.I also think I agree that this is the right semantic model. I really do not want to make how we handle lifetime-based optimizations have anything to do with where the memory comes from. That is a Really Bad Idea IMO because it couples things that shouldn't be coupled. We could reasonably want to do stack-to-heap or heap-to-stack changes to allocation patterns, and those should be totally orthogonal to managing lifetimes. Also, when we do end up with obviously bracketed regions as expected for many cases, it should be no harder to detect. We just need to use a conservatively correct algorithm for matching them up during stack coloring. -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20141105/17f413f5/attachment.html>