Philip Reames
2015-Jun-17 23:33 UTC
[LLVMdev] design question on inlining through statepoints and patchpoints
The long term plan is a) evolving, and b) dependent on the specific use case. :) It would definitely be nice if we could support both early and late safepoint insertion. I see no reason that LLVM as a project should pick one or the other since the infrastructure required is largely overlapping. (Obviously, I'm going to be mostly working on the parts that I need, but others are always welcome to extend in other directions.) One of the challenges we've run into is that supporting deoptimization points (which in practice are safepoints) require a lot of the same infrastructure as early safepoint insertion. It's likely that we'll end with a scheme which inserts safepoint polls quite early (but with restricted semantics and optimization impact) and then converts them to explicit GC safepoints (with full invalidation semantics) quite late. We already have this distinction in tree in the form of PlaceSafepoints and RewriteStatepointsForGC. I suspect we'll move further in this direction. I suspect that for languages without deoptimization, you'll want to insert safepoint polls quite late. Whether you do the same for safepoints-at-calls is debatable. I used to think that you should do that quite late, but I'm no longer sure that's always the right answer. Philip On 06/17/2015 04:13 PM, Swaroop Sridhar wrote:> With respect to phase ordering, is the long term plan to run the statepoint placement/transformation phases late (after all optimizations)? > If so, will we need to support inlining post statepoint transformation? > > Thanks, > Swaroop. > > -----Original Message----- > From: Sanjoy Das [mailto:sanjoy at playingwithpointers.com] > Sent: Tuesday, June 16, 2015 7:20 PM > To: LLVM Developers Mailing List; Andrew Trick; Swaroop Sridhar; Chandler Carruth; Nick Lewycky > Subject: design question on inlining through statepoints and patchpoints > > I've been looking at inlining invokes / calls done through statepoints and I want to have a design discussion before I sink too much time into something I'll have to throw away. I'm not actively working on adding inlining support to patchpoints, but I suspect these issues are applicable towards teaching LLVM to inline through patchpoints as well. > > > There are two distinct problems to solve before LLVM can inline through statepoints: > > # Managing data flow for the extra metadata args. > > LLVM needs some logic to "transfer" the extra live values attached to a statepoint/patchpoint into the body of the inlinee somehow. How this is handled depends on the semantics of the live values (something the frontend knows). There needs to be a clean way for the frontend to communicate this information to LLVM, or we need to devise a convention that is sensible for the kinds of frontends we wish to support. Initially I plan to sidestep this problem by only inlining through statepoints have *no* extra live values / gc pointers. > > > # Managing the call graph > > This is the problem we need to solve first. Currently LLVM views the a statepoint or patchpoint call as > > 1. A call to an intrisic. This does not add an edge to the call > graph (not even to the dedicated external node). > > 2. An escaping use of the callee. > > IIUC, (2) is (conservatively) imprecise and (1) is incorrect. (1) makes LLVM believe that a function that calls @f via a statepoint does not call @f at all. (2) makes LLVM believe that @f is visible externally, even if it has internal linkage. > > Given this starting point, I can think of three ways to model statepoint's (and patchpoint's) control flow semantics within a call > graph: > > 1. Model calls to statepoint, patchpoint and stackmap intrinsics as > calling the external node. Teach the inliner pass to > "devirtualize" calls through statepoints when posssible, except > that the "devirtualization" is only a facade (i.e. we don't > mutate the IR to change the statepoint to a direct call). We add > some abstraction to the inlining utility functions to inline > through something more general than a CallSite. > > 2. Introduce a new abstraction InlineSite (bikeshedding on the name > is welcome). InlineSite sits on top of a CallSite and knows how > to extract the semantic call out of a statepoint or a patchpoint > (similar to the llvm::Statepoint class). The inliner and the > call graph analysis works on top of this InlineSite abstraction > instead of the CallSite abstraction. > > 3. Change all the places that matter (CallGraph, CallGraphSCCPass > etc.) from > > if (CallSite CS = ...) > > to > > if (Statepoint SP = ...) > ... > else if (CallSite CS = ...) > > or something equivalent to this. > > Personally, I'd prefer going with (1) if it is viable, and (2) if not. > > What do you think? > > -- Sanjoy > > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Sanjoy Das
2015-Jun-23 21:18 UTC
[LLVMdev] design question on inlining through statepoints and patchpoints
patches here (reverse chronological order): http://reviews.llvm.org/D10633 http://reviews.llvm.org/D10632 http://reviews.llvm.org/D10631 On Wed, Jun 17, 2015 at 4:33 PM, Philip Reames <listmail at philipreames.com> wrote:> The long term plan is a) evolving, and b) dependent on the specific use > case. :) > > It would definitely be nice if we could support both early and late > safepoint insertion. I see no reason that LLVM as a project should pick one > or the other since the infrastructure required is largely overlapping. > (Obviously, I'm going to be mostly working on the parts that I need, but > others are always welcome to extend in other directions.) > > One of the challenges we've run into is that supporting deoptimization > points (which in practice are safepoints) require a lot of the same > infrastructure as early safepoint insertion. It's likely that we'll end > with a scheme which inserts safepoint polls quite early (but with restricted > semantics and optimization impact) and then converts them to explicit GC > safepoints (with full invalidation semantics) quite late. We already have > this distinction in tree in the form of PlaceSafepoints and > RewriteStatepointsForGC. I suspect we'll move further in this direction. > > I suspect that for languages without deoptimization, you'll want to insert > safepoint polls quite late. Whether you do the same for safepoints-at-calls > is debatable. I used to think that you should do that quite late, but I'm > no longer sure that's always the right answer. > > Philip > > > > On 06/17/2015 04:13 PM, Swaroop Sridhar wrote: >> >> With respect to phase ordering, is the long term plan to run the >> statepoint placement/transformation phases late (after all optimizations)? >> If so, will we need to support inlining post statepoint transformation? >> >> Thanks, >> Swaroop. >> >> -----Original Message----- >> From: Sanjoy Das [mailto:sanjoy at playingwithpointers.com] >> Sent: Tuesday, June 16, 2015 7:20 PM >> To: LLVM Developers Mailing List; Andrew Trick; Swaroop Sridhar; Chandler >> Carruth; Nick Lewycky >> Subject: design question on inlining through statepoints and patchpoints >> >> I've been looking at inlining invokes / calls done through statepoints and >> I want to have a design discussion before I sink too much time into >> something I'll have to throw away. I'm not actively working on adding >> inlining support to patchpoints, but I suspect these issues are applicable >> towards teaching LLVM to inline through patchpoints as well. >> >> >> There are two distinct problems to solve before LLVM can inline through >> statepoints: >> >> # Managing data flow for the extra metadata args. >> >> LLVM needs some logic to "transfer" the extra live values attached to a >> statepoint/patchpoint into the body of the inlinee somehow. How this is >> handled depends on the semantics of the live values (something the frontend >> knows). There needs to be a clean way for the frontend to communicate this >> information to LLVM, or we need to devise a convention that is sensible for >> the kinds of frontends we wish to support. Initially I plan to sidestep >> this problem by only inlining through statepoints have *no* extra live >> values / gc pointers. >> >> >> # Managing the call graph >> >> This is the problem we need to solve first. Currently LLVM views the a >> statepoint or patchpoint call as >> >> 1. A call to an intrisic. This does not add an edge to the call >> graph (not even to the dedicated external node). >> >> 2. An escaping use of the callee. >> >> IIUC, (2) is (conservatively) imprecise and (1) is incorrect. (1) makes >> LLVM believe that a function that calls @f via a statepoint does not call @f >> at all. (2) makes LLVM believe that @f is visible externally, even if it >> has internal linkage. >> >> Given this starting point, I can think of three ways to model statepoint's >> (and patchpoint's) control flow semantics within a call >> graph: >> >> 1. Model calls to statepoint, patchpoint and stackmap intrinsics as >> calling the external node. Teach the inliner pass to >> "devirtualize" calls through statepoints when posssible, except >> that the "devirtualization" is only a facade (i.e. we don't >> mutate the IR to change the statepoint to a direct call). We add >> some abstraction to the inlining utility functions to inline >> through something more general than a CallSite. >> >> 2. Introduce a new abstraction InlineSite (bikeshedding on the name >> is welcome). InlineSite sits on top of a CallSite and knows how >> to extract the semantic call out of a statepoint or a patchpoint >> (similar to the llvm::Statepoint class). The inliner and the >> call graph analysis works on top of this InlineSite abstraction >> instead of the CallSite abstraction. >> >> 3. Change all the places that matter (CallGraph, CallGraphSCCPass >> etc.) from >> >> if (CallSite CS = ...) >> >> to >> >> if (Statepoint SP = ...) >> ... >> else if (CallSite CS = ...) >> >> or something equivalent to this. >> >> Personally, I'd prefer going with (1) if it is viable, and (2) if not. >> >> What do you think? >> >> -- Sanjoy >> >> _______________________________________________ >> LLVM Developers mailing list >> LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu >> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev > >
Chandler Carruth
2015-Jun-26 07:59 UTC
[LLVMdev] design question on inlining through statepoints and patchpoints
I'm digging into the patches, and it has at least raised one high-level question for me that I wanted to ask here so that the response would be reasonably widely seen. Essentially, what are the particular motivations for inlining through statepoints? How important are they for the actual users we're building of the GC infrastructure? (Philip's email starts to give some hints here, but I'm not really clear exactly how important this is... for example, I don't understand what the deoptimization thing is all about. This is likely just my ignorance of common parlance and problems in GC land, but I think it would be useful to break it down so that we have a reference for what all is being discussed.) I'm not really doubting the importance mind you, I'd just like to *understand* it better (and confirm my suspicion that this is really a "must have" feature rather than a "nice to have" feature). On Tue, Jun 23, 2015 at 2:24 PM Sanjoy Das <sanjoy at playingwithpointers.com> wrote:> patches here (reverse chronological order): > > http://reviews.llvm.org/D10633 > http://reviews.llvm.org/D10632 > http://reviews.llvm.org/D10631 > > > On Wed, Jun 17, 2015 at 4:33 PM, Philip Reames > <listmail at philipreames.com> wrote: > > The long term plan is a) evolving, and b) dependent on the specific use > > case. :) > > > > It would definitely be nice if we could support both early and late > > safepoint insertion. I see no reason that LLVM as a project should pick > one > > or the other since the infrastructure required is largely overlapping. > > (Obviously, I'm going to be mostly working on the parts that I need, but > > others are always welcome to extend in other directions.) > > > > One of the challenges we've run into is that supporting deoptimization > > points (which in practice are safepoints) require a lot of the same > > infrastructure as early safepoint insertion. It's likely that we'll end > > with a scheme which inserts safepoint polls quite early (but with > restricted > > semantics and optimization impact) and then converts them to explicit GC > > safepoints (with full invalidation semantics) quite late. We already > have > > this distinction in tree in the form of PlaceSafepoints and > > RewriteStatepointsForGC. I suspect we'll move further in this direction. > > > > I suspect that for languages without deoptimization, you'll want to > insert > > safepoint polls quite late. Whether you do the same for > safepoints-at-calls > > is debatable. I used to think that you should do that quite late, but > I'm > > no longer sure that's always the right answer. > > > > Philip > > > > > > > > On 06/17/2015 04:13 PM, Swaroop Sridhar wrote: > >> > >> With respect to phase ordering, is the long term plan to run the > >> statepoint placement/transformation phases late (after all > optimizations)? > >> If so, will we need to support inlining post statepoint transformation? > >> > >> Thanks, > >> Swaroop. > >> > >> -----Original Message----- > >> From: Sanjoy Das [mailto:sanjoy at playingwithpointers.com] > >> Sent: Tuesday, June 16, 2015 7:20 PM > >> To: LLVM Developers Mailing List; Andrew Trick; Swaroop Sridhar; > Chandler > >> Carruth; Nick Lewycky > >> Subject: design question on inlining through statepoints and patchpoints > >> > >> I've been looking at inlining invokes / calls done through statepoints > and > >> I want to have a design discussion before I sink too much time into > >> something I'll have to throw away. I'm not actively working on adding > >> inlining support to patchpoints, but I suspect these issues are > applicable > >> towards teaching LLVM to inline through patchpoints as well. > >> > >> > >> There are two distinct problems to solve before LLVM can inline through > >> statepoints: > >> > >> # Managing data flow for the extra metadata args. > >> > >> LLVM needs some logic to "transfer" the extra live values attached to a > >> statepoint/patchpoint into the body of the inlinee somehow. How this is > >> handled depends on the semantics of the live values (something the > frontend > >> knows). There needs to be a clean way for the frontend to communicate > this > >> information to LLVM, or we need to devise a convention that is sensible > for > >> the kinds of frontends we wish to support. Initially I plan to sidestep > >> this problem by only inlining through statepoints have *no* extra live > >> values / gc pointers. > >> > >> > >> # Managing the call graph > >> > >> This is the problem we need to solve first. Currently LLVM views the a > >> statepoint or patchpoint call as > >> > >> 1. A call to an intrisic. This does not add an edge to the call > >> graph (not even to the dedicated external node). > >> > >> 2. An escaping use of the callee. > >> > >> IIUC, (2) is (conservatively) imprecise and (1) is incorrect. (1) makes > >> LLVM believe that a function that calls @f via a statepoint does not > call @f > >> at all. (2) makes LLVM believe that @f is visible externally, even if > it > >> has internal linkage. > >> > >> Given this starting point, I can think of three ways to model > statepoint's > >> (and patchpoint's) control flow semantics within a call > >> graph: > >> > >> 1. Model calls to statepoint, patchpoint and stackmap intrinsics as > >> calling the external node. Teach the inliner pass to > >> "devirtualize" calls through statepoints when posssible, except > >> that the "devirtualization" is only a facade (i.e. we don't > >> mutate the IR to change the statepoint to a direct call). We add > >> some abstraction to the inlining utility functions to inline > >> through something more general than a CallSite. > >> > >> 2. Introduce a new abstraction InlineSite (bikeshedding on the name > >> is welcome). InlineSite sits on top of a CallSite and knows how > >> to extract the semantic call out of a statepoint or a patchpoint > >> (similar to the llvm::Statepoint class). The inliner and the > >> call graph analysis works on top of this InlineSite abstraction > >> instead of the CallSite abstraction. > >> > >> 3. Change all the places that matter (CallGraph, CallGraphSCCPass > >> etc.) from > >> > >> if (CallSite CS = ...) > >> > >> to > >> > >> if (Statepoint SP = ...) > >> ... > >> else if (CallSite CS = ...) > >> > >> or something equivalent to this. > >> > >> Personally, I'd prefer going with (1) if it is viable, and (2) if not. > >> > >> What do you think? > >> > >> -- Sanjoy > >> > >> _______________________________________________ > >> LLVM Developers mailing list > >> LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > >> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev > > > > > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev >-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20150626/dbb10f90/attachment.html>