<html>
<head>
<meta content="text/html; charset=utf-8" http-equiv="Content-Type">
</head>
<body bgcolor="#FFFFFF" text="#000000">
Chandler,<br>
<br>
Thanks for asking about the bigger picture. It's definitely good to
summarize that somewhere more visible than a patch review.<br>
<br>
In my mind, there are two intersecting but mostly orthogonal reasons
why we want to support the ability to inline through statepoints
(and someday possibly patchpoints). They are: a) supporting early
safepoint insertion and b) implementation flexibility. I'll go into
each below.<br>
<br>
<br>
Today, we really only support the insertion of safepoints (both
polls and call safepoints) after inlining has been done. This is
the model that PlaceSafepoints and RewriteStatepointsForGC support
in tree and that we've been using with some success. I believe
that's also the model that WebKit has used with patchpoints, though
in a different form. Their high level optimization is done in an
entirely different IR; whereas ours is done over LLVM IR. <br>
<br>
There have been a couple of things that have come up which make me
think it's valuable to support the insertion of at least call
safepoints earlier in the optimizer. For one, it makes thinking
about escaped stack allocated objects (which must be updated in
place) more obvious for the frontend. Second, talking to other
frontend authors most people expect to use an early insertion
model. Supporting both from a functional standpoint and having late
insertion be an "optimization" seems to provide a more gentle
introduction path. Third, it makes reasoning about deoptimization a
lot cleaner.<br>
<br>
I don't want to get into the weeds of deoptimization right now - it
would utterly derail the conversation and we're not making any
proposals for upstream in this area at the moment - but let me
summarize the problem for context. Essentially, we need to be able
to track a chain of abstract frame states through inlining and
serialize them into the stackmap via a statepoint. Today, we handle
tracking those abstract frames using an independent mechanism I'm
going to skip over. This has worked, but has frankly been a major
pain point. Having the ability to inline through statepoints opens
up some possible designs in this space, but we're not proposing
anything concrete at this moment. <br>
<br>
<br>
The more immediate benefit from adding support for inlining through
statepoints is that it gives a lot more implementation flexibility.
Today, we have a hard requirement that *all* inlining be done before
statepoints are inserted. This influences design choices in
sometimes odd ways. <br>
<br>
As one in tree example, consider the insertion of safepoint polls
done by PlaceSafepoints. We currently need to force inline newly
inserted calls rather than just inserting them and worrying about
the profitability later. In the future, we might want to support
not inlining some of these poll sites. (Consider a really cold loop
- you might prefer the cost of the extra call over the code size
increase for the test and slow path.) Today, we'd *have* to make
that choice within PlaceSafepoints. With support for inlining
through statepoints, we could defer that to a distinct pass and thus
factor the code more cleanly. In fact, we could even separate some
of the existing optimizations for placement into a separate pass
which removes provably redundant safepoints rather than combining
that into the insertion logic itself. I'm not necessarily saying we
will, but the ability to inline through statepoints gives us the
option of considering choices like these which we can't otherwise
do. <br>
<br>
Another (out of tree) example comes from our optimization pipeline.
We use a set of known functions to represent high level concepts.
Today, we have a hard requirement about inlining all of these known
functions (well, all that can contain safepoints), before safepoint
insertion. Part of our work (out of tree) at safepoint insertion is
pruning deoptimization state which turn out not to be required.
This often opens up optimization possibilities that would be visible
if we could identify high level semantic constructs. Being able to
swap the safepoint insertion and lowering phases (which does
inlining internally) would be very helpful from an optimization
perspective. <br>
<br>
<br>
Philip<br>
<br>
p.s. Just to be clear, the flexibility parts really only require the
InlineFunction changes; not full support from the inliner. That's
only required for early call safepoint insertion. <br>
<br>
p.p.s. Longer term, it really feels to me that
statepoints/patchpoints are moving in the direction of being an
arbitrary wrapped call. There's some underlying call (or invoke)
with additional layers of semantics wrapped around that. We seem to
be settling on a relatively fixed set of composable semantics, so
long term these may be IR extensions. No concrete proposals here
yet though.<br>
<br>
<br>
<br>
<div class="moz-cite-prefix">On 06/26/2015 12:59 AM, Chandler
Carruth wrote:<br>
</div>
<blockquote
cite="mid:CAGCO0Kg0xj60jqxaQHXUm5n5b+yAcB7wbvmr4gR27usov3UW5g@mail.gmail.com"
type="cite">
<div dir="ltr">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.
<div><br>
</div>
<div>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.)</div>
<div><br>
</div>
<div>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).</div>
</div>
<br>
<div class="gmail_quote">
<div dir="ltr">On Tue, Jun 23, 2015 at 2:24 PM Sanjoy Das <<a moz-do-not-send="true" href="mailto:sanjoy@playingwithpointers.com">sanjoy@playingwithpointers.com</a>>
wrote:<br>
</div>
<blockquote class="gmail_quote" style="margin:0 0 0
.8ex;border-left:1px #ccc solid;padding-left:1ex">patches here
(reverse chronological order):<br>
<br>
<a moz-do-not-send="true" href="https://urldefense.proofpoint.com/v2/url?u=http-3A__reviews.llvm.org_D10633&d=AwMDaQ&c=8hUWFZcy2Z-Za5rBPlktOQ&r=Mfk2qtn1LTDThVkh6-oGglNfMADXfJdty4_bhmuhMHA&m=GVdMR4jwuFtORFf5ivDLddK_INrJWbPv3ECuEmyfZPM&s=c4cR2E4sbljkE-Hb2soJEqkHO_8af3F7VakSutCElJU&e=" rel="noreferrer" target="_blank">http://reviews.llvm.org/D10633</a><br>
<a moz-do-not-send="true" href="https://urldefense.proofpoint.com/v2/url?u=http-3A__reviews.llvm.org_D10632&d=AwMDaQ&c=8hUWFZcy2Z-Za5rBPlktOQ&r=Mfk2qtn1LTDThVkh6-oGglNfMADXfJdty4_bhmuhMHA&m=GVdMR4jwuFtORFf5ivDLddK_INrJWbPv3ECuEmyfZPM&s=G5Y5xvvxctSQ_RTFBI5oBi_qcMADaPZGffe0nfL62ic&e=" rel="noreferrer" target="_blank">http://reviews.llvm.org/D10632</a><br>
<a moz-do-not-send="true" href="https://urldefense.proofpoint.com/v2/url?u=http-3A__reviews.llvm.org_D10631&d=AwMDaQ&c=8hUWFZcy2Z-Za5rBPlktOQ&r=Mfk2qtn1LTDThVkh6-oGglNfMADXfJdty4_bhmuhMHA&m=GVdMR4jwuFtORFf5ivDLddK_INrJWbPv3ECuEmyfZPM&s=9g83lSxD5Lvhs6uQTrxg_PY0MchJdBziCxS56WhJNYg&e=" rel="noreferrer" target="_blank">http://reviews.llvm.org/D10631</a><br>
<br>
<br>
On Wed, Jun 17, 2015 at 4:33 PM, Philip Reames<br>
<<a moz-do-not-send="true" href="mailto:listmail@philipreames.com" target="_blank">listmail@philipreames.com</a>>
wrote:<br>
> The long term plan is a) evolving, and b) dependent on
the specific use<br>
> case. :)<br>
><br>
> It would definitely be nice if we could support both
early and late<br>
> safepoint insertion. I see no reason that LLVM as a
project should pick one<br>
> or the other since the infrastructure required is largely
overlapping.<br>
> (Obviously, I'm going to be mostly working on the parts
that I need, but<br>
> others are always welcome to extend in other directions.)<br>
><br>
> One of the challenges we've run into is that supporting
deoptimization<br>
> points (which in practice are safepoints) require a lot
of the same<br>
> infrastructure as early safepoint insertion. It's likely
that we'll end<br>
> with a scheme which inserts safepoint polls quite early
(but with restricted<br>
> semantics and optimization impact) and then converts them
to explicit GC<br>
> safepoints (with full invalidation semantics) quite
late. We already have<br>
> this distinction in tree in the form of PlaceSafepoints
and<br>
> RewriteStatepointsForGC. I suspect we'll move further in
this direction.<br>
><br>
> I suspect that for languages without deoptimization,
you'll want to insert<br>
> safepoint polls quite late. Whether you do the same for
safepoints-at-calls<br>
> is debatable. I used to think that you should do that
quite late, but I'm<br>
> no longer sure that's always the right answer.<br>
><br>
> Philip<br>
><br>
><br>
><br>
> On 06/17/2015 04:13 PM, Swaroop Sridhar wrote:<br>
>><br>
>> With respect to phase ordering, is the long term plan
to run the<br>
>> statepoint placement/transformation phases late
(after all optimizations)?<br>
>> If so, will we need to support inlining post
statepoint transformation?<br>
>><br>
>> Thanks,<br>
>> Swaroop.<br>
>><br>
>> -----Original Message-----<br>
>> From: Sanjoy Das [mailto:<a moz-do-not-send="true" href="mailto:sanjoy@playingwithpointers.com" target="_blank">sanjoy@playingwithpointers.com</a>]<br>
>> Sent: Tuesday, June 16, 2015 7:20 PM<br>
>> To: LLVM Developers Mailing List; Andrew Trick;
Swaroop Sridhar; Chandler<br>
>> Carruth; Nick Lewycky<br>
>> Subject: design question on inlining through
statepoints and patchpoints<br>
>><br>
>> I've been looking at inlining invokes / calls done
through statepoints and<br>
>> I want to have a design discussion before I sink too
much time into<br>
>> something I'll have to throw away. I'm not actively
working on adding<br>
>> inlining support to patchpoints, but I suspect these
issues are applicable<br>
>> towards teaching LLVM to inline through patchpoints
as well.<br>
>><br>
>><br>
>> There are two distinct problems to solve before LLVM
can inline through<br>
>> statepoints:<br>
>><br>
>> # Managing data flow for the extra metadata args.<br>
>><br>
>> LLVM needs some logic to "transfer" the extra live
values attached to a<br>
>> statepoint/patchpoint into the body of the inlinee
somehow. How this is<br>
>> handled depends on the semantics of the live values
(something the frontend<br>
>> knows). There needs to be a clean way for the
frontend to communicate this<br>
>> information to LLVM, or we need to devise a
convention that is sensible for<br>
>> the kinds of frontends we wish to support. Initially
I plan to sidestep<br>
>> this problem by only inlining through statepoints
have *no* extra live<br>
>> values / gc pointers.<br>
>><br>
>><br>
>> # Managing the call graph<br>
>><br>
>> This is the problem we need to solve first.
Currently LLVM views the a<br>
>> statepoint or patchpoint call as<br>
>><br>
>> 1. A call to an intrisic. This does not add an
edge to the call<br>
>> graph (not even to the dedicated external
node).<br>
>><br>
>> 2. An escaping use of the callee.<br>
>><br>
>> IIUC, (2) is (conservatively) imprecise and (1) is
incorrect. (1) makes<br>
>> LLVM believe that a function that calls @f via a
statepoint does not call @f<br>
>> at all. (2) makes LLVM believe that @f is visible
externally, even if it<br>
>> has internal linkage.<br>
>><br>
>> Given this starting point, I can think of three ways
to model statepoint's<br>
>> (and patchpoint's) control flow semantics within a
call<br>
>> graph:<br>
>><br>
>> 1. Model calls to statepoint, patchpoint and
stackmap intrinsics as<br>
>> calling the external node. Teach the inliner
pass to<br>
>> "devirtualize" calls through statepoints when
posssible, except<br>
>> that the "devirtualization" is only a facade
(i.e. we don't<br>
>> mutate the IR to change the statepoint to a
direct call). We add<br>
>> some abstraction to the inlining utility
functions to inline<br>
>> through something more general than a CallSite.<br>
>><br>
>> 2. Introduce a new abstraction InlineSite
(bikeshedding on the name<br>
>> is welcome). InlineSite sits on top of a
CallSite and knows how<br>
>> to extract the semantic call out of a
statepoint or a patchpoint<br>
>> (similar to the llvm::Statepoint class). The
inliner and the<br>
>> call graph analysis works on top of this
InlineSite abstraction<br>
>> instead of the CallSite abstraction.<br>
>><br>
>> 3. Change all the places that matter (CallGraph,
CallGraphSCCPass<br>
>> etc.) from<br>
>><br>
>> if (CallSite CS = ...)<br>
>><br>
>> to<br>
>><br>
>> if (Statepoint SP = ...)<br>
>> ...<br>
>> else if (CallSite CS = ...)<br>
>><br>
>> or something equivalent to this.<br>
>><br>
>> Personally, I'd prefer going with (1) if it is
viable, and (2) if not.<br>
>><br>
>> What do you think?<br>
>><br>
>> -- Sanjoy<br>
>><br>
>> _______________________________________________<br>
>> LLVM Developers mailing list<br>
>> <a moz-do-not-send="true" href="mailto:LLVMdev@cs.uiuc.edu" target="_blank">LLVMdev@cs.uiuc.edu</a>
<a moz-do-not-send="true" href="http://llvm.cs.uiuc.edu" rel="noreferrer" target="_blank">http://llvm.cs.uiuc.edu</a><br>
>> <a moz-do-not-send="true" href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev" rel="noreferrer" target="_blank">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a><br>
><br>
><br>
_______________________________________________<br>
LLVM Developers mailing list<br>
<a moz-do-not-send="true" href="mailto:LLVMdev@cs.uiuc.edu" target="_blank">LLVMdev@cs.uiuc.edu</a> <a moz-do-not-send="true" href="http://llvm.cs.uiuc.edu" rel="noreferrer" target="_blank">http://llvm.cs.uiuc.edu</a><br>
<a moz-do-not-send="true" href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev" rel="noreferrer" target="_blank">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a><br>
</blockquote>
</div>
</blockquote>
<br>
</body>
</html>