llvm dev - Jun 2015 - [LLVMdev] 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

Look at the LazyCallGraph pass? This is going to be the basis of the new
pass manager, and I designed it specifically to help deal with these kinds
of issues. I'd be interested if it just directly addresses the call graph
issue without the need for any special handling. If not, I'd like to
understand why not.

I'll think some about the inliner side of this...

On Tue, Jun 16, 2015, 19:24 Sanjoy Das <sanjoy at playingwithpointers.com>
wrote:
> 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
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150617/ff193cd1/attachment.html>

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

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