llvm dev - Jul 2016 - RFC: Strong GC References in LLVM

On Thu, Jul 21, 2016 at 9:39 AM, Daniel Berlin <dberlin at dberlin.org>
wrote:
>
>
> On Thu, Jul 21, 2016 at 9:26 AM, Andrew Trick <atrick at apple.com>
wrote:
>
>>
>> On Jul 21, 2016, at 7:45 AM, Philip Reames <listmail at
philipreames.com>
>> wrote:
>>
>> Joining in very late, but the tangent here has been interesting (if
>> rather OT for the original thread).
>>
>> I agree with Danny that we might want to take a close look at how we
>> model things like maythrow calls, no return, and other implicit control
>> flow.  I'm not convinced that moving to a pure explicit model is
the right
>> idea because we get a lot of gain in practice from being able to reason
>> about what are essentially a limited form of extended basic blocks.  I
>> would welcome a design discussion about this, preferably in person, but
>> also don't want to block any current (or future honestly) work on
this
>> until we have a reasonable firm plan of action.
>>
>> One idea would be to explicitly acknowledge that our "basic
blocks" are
>> actually "extended basic blocks" with internal exits due to
exception
>> propagation, noreturn, and (recently) guards.  I could see a couple of
>> implementation strategies here:
>> 1) Extend BasicBlock to explicitly track potential early exiting
>> instructions.  This would probably have to be conservative so that
things
>> like nothrow inference aren't required to update all callers in one
go.
>> 2) Conservative assume that BasicBlock has an unknown number of early
>> exiting instructions and write an analysis pass which answers questions
>> about where those early exits are.  Any pass which does code motion
would
>> require this analysis.  (This is essentially the principled version of
our
>> current hacks.)
>>
>>
>> This analysis can be lazy/incremental. Most passes only do “safe”
>> speculation and code sinking without side effects.
>>
>
> While I agree it can be lazy, and should be an analysis, i'm, again,
> really not sure which passes you are thinking about here that do code
> sinking/speculation that won't need it.
>
> Here's the list definitely needing it right now:
> GVN
> GVNHoist
> LICM
> LoadCombine
> LoopReroll
> LoopUnswitch
> LoopVersioningLICM
> MemCpyOptimizer
> MergedLoadStoreMotion
> Sink
>
> The list is almost certainly larger than this, this was a pretty trivial
> grep and examination.
> (and doesn't take into account bugs, etc)
>
>
(Note, this list is stuff in the Scalar directory only. Everything in
Vectorize would n eed it, etc)

And in case folks want more evidence that reasonable llvm developers need
something that just gives easy and right answers, see
https://reviews.llvm.org/D22547 from just yesterday :)

To move this along, i will go build the analysis (I already have it mostly
done, actually).  If someone updates our docs to make this stuff clear and
obvious, that would be wonderful :)

The analysis currently computes, internally, for a given BB:

EarliestLoadHoistBarrier (used to see if you can move something out of a
block)
LatestLoadHoistBarrier (used to find the latest safe insertion point in a
block, if any)
EarliestStoreSinkBarrier (insertion)
LatestStoreSinkBarrier (movement)


(stores are maythrow dependent, loads are
isGuaranteedToTransferExecutionToSuccessor dependent)

I'm still coming up with the external API, the users all want to know
either:

1. Can i move a load up out of this block to a direct predecessor
2. Can i move a store down out of this block to a direct successor

GVN's current load PRE is complex to get "right" from it's
current
standpoint, the APi that will provide the easiest way to fix it will be:

3. What is the latest insertion point in a block for a load, if it is safe
(IE the block does not end in an instruction you cannot move the load
before).

Nothing is doing global store sinking right now that i see, so nothing
needs the analogous store api.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160721/26fa7850/attachment.html>

On 07/21/2016 10:30 AM, Daniel Berlin wrote:
>
>
> On Thu, Jul 21, 2016 at 9:39 AM, Daniel Berlin <dberlin at dberlin.org 
> <mailto:dberlin at dberlin.org>> wrote:
>
>
>
>     On Thu, Jul 21, 2016 at 9:26 AM, Andrew Trick <atrick at apple.com
>     <mailto:atrick at apple.com>> wrote:
>
>
>>         On Jul 21, 2016, at 7:45 AM, Philip Reames
>>         <listmail at philipreames.com
>>         <mailto:listmail at philipreames.com>> wrote:
>>
>>         Joining in very late, but the tangent here has been
>>         interesting (if rather OT for the original thread).
>>
>>         I agree with Danny that we might want to take a close look at
>>         how we model things like maythrow calls, no return, and other
>>         implicit control flow.  I'm not convinced that moving to a
>>         pure explicit model is the right idea because we get a lot of
>>         gain in practice from being able to reason about what are
>>         essentially a limited form of extended basic blocks.  I would
>>         welcome a design discussion about this, preferably in person,
>>         but also don't want to block any current (or future
honestly)
>>         work on this until we have a reasonable firm plan of action.
>>
>>         One idea would be to explicitly acknowledge that our
"basic
>>         blocks" are actually "extended basic blocks"
with internal
>>         exits due to exception propagation, noreturn, and (recently)
>>         guards.  I could see a couple of implementation strategies
here:
>>         1) Extend BasicBlock to explicitly track potential early
>>         exiting instructions.  This would probably have to be
>>         conservative so that things like nothrow inference aren't
>>         required to update all callers in one go.
>>         2) Conservative assume that BasicBlock has an unknown number
>>         of early exiting instructions and write an analysis pass
>>         which answers questions about where those early exits are. 
>>         Any pass which does code motion would require this analysis.
>>         (This is essentially the principled version of our current
>>         hacks.)
>
>         This analysis can be lazy/incremental. Most passes only do
>         “safe” speculation and code sinking without side effects.
>
>
>     While I agree it can be lazy, and should be an analysis, i'm,
>     again, really not sure which passes you are thinking about here
>     that do code sinking/speculation that won't need it.
>
>     Here's the list definitely needing it right now:
>     GVN
>     GVNHoist
>     LICM
>     LoadCombine
>     LoopReroll
>     LoopUnswitch
>     LoopVersioningLICM
>     MemCpyOptimizer
>     MergedLoadStoreMotion
>     Sink
>
>     The list is almost certainly larger than this, this was a pretty
>     trivial grep and examination.
>     (and doesn't take into account bugs, etc)
>
>
>
> (Note, this list is stuff in the Scalar directory only. Everything in 
> Vectorize would n eed it, etc)
>
> And in case folks want more evidence that reasonable llvm developers 
> need something that just gives easy and right answers, see 
> https://reviews.llvm.org/D22547 from just yesterday :)
>
> To move this along, i will go build the analysis (I already have it 
> mostly done, actually).  If someone updates our docs to make this 
> stuff clear and obvious, that would be wonderful :)
>
> The analysis currently computes, internally, for a given BB:
>
> EarliestLoadHoistBarrier (used to see if you can move something out of 
> a block)
> LatestLoadHoistBarrier (used to find the latest safe insertion point 
> in a block, if any)
> EarliestStoreSinkBarrier (insertion)
> LatestStoreSinkBarrier (movement)
>
>
> (stores are maythrow dependent, loads are 
> isGuaranteedToTransferExecutionToSuccessor dependent)
>
> I'm still coming up with the external API, the users all want to know 
> either:
>
> 1. Can i move a load up out of this block to a direct predecessor
> 2. Can i move a store down out of this block to a direct successor
I would argue that we should have this analysis *only* report the EBB 
information.  Doing this in the form of the information you've mentioned 
is fine, but I would not want to see this become our deref analysis for 
instance.  I think that needs to be a separate analysis which is well 
layered on top of this one.  (i.e. once I encounter a hoist barrier, I 
need to then ask if a load is safe to speculate beyond that point as a 
separate question.)
>
> GVN's current load PRE is complex to get "right" from
it's current
> standpoint, the APi that will provide the easiest way to fix it will be:
>
> 3. What is the latest insertion point in a block for a load, if it is 
> safe (IE the block does not end in an instruction you cannot move the 
> load before).
>
> Nothing is doing global store sinking right now that i see, so nothing 
> needs the analogous store api.
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160721/6be95187/attachment.html>

Okay, so it sounds like it might actually be better to be even more low
level, call it "ExtendedBBInfo" or something, and rename what it
provides
to be more clearly structural:

A. Inst * FirstIsGuaranteedToTransferExecutionToSuccessor(BB) (naming
bikeshed open on this one :P)
B. Inst * LastIsGuaranteedToTransferExecutionToSuccessor(BB)
C. Inst *FirstMayThrow(BB)
D. Inst *LastMayThrow(BB)


Most things want to know if a given inst is before or after these.

Since we have to touch the entire set of instructions for a bb anyway, we
could also provide dominates (like orderedbasicblock) to give you the
answer to that question for free (otherwise everything has to rewalk the
entire inst list again)

Rather than make it part of the API for this class, this would basically be
making OrderedBasicBlock an interface, and this class happens to be able to
provide a pointer to something satisfying that interface as well.

(IE getOrderedBasicBlock() on EBBInfo will return you something that  has
locallyDominates())




On Thu, Jul 21, 2016 at 11:59 AM, Philip Reames <listmail at
philipreames.com>
wrote:
>
>
> On 07/21/2016 10:30 AM, Daniel Berlin wrote:
>
>
>
> On Thu, Jul 21, 2016 at 9:39 AM, Daniel Berlin <dberlin at
dberlin.org>
> wrote:
>
>>
>>
>> On Thu, Jul 21, 2016 at 9:26 AM, Andrew Trick < <atrick at
apple.com>
>> atrick at apple.com> wrote:
>>
>>>
>>> On Jul 21, 2016, at 7:45 AM, Philip Reames <listmail at
philipreames.com>
>>> wrote:
>>>
>>> Joining in very late, but the tangent here has been interesting (if
>>> rather OT for the original thread).
>>>
>>> I agree with Danny that we might want to take a close look at how
we
>>> model things like maythrow calls, no return, and other implicit
control
>>> flow.  I'm not convinced that moving to a pure explicit model
is the right
>>> idea because we get a lot of gain in practice from being able to
reason
>>> about what are essentially a limited form of extended basic blocks.
I
>>> would welcome a design discussion about this, preferably in person,
but
>>> also don't want to block any current (or future honestly) work
on this
>>> until we have a reasonable firm plan of action.
>>>
>>> One idea would be to explicitly acknowledge that our "basic
blocks" are
>>> actually "extended basic blocks" with internal exits due
to exception
>>> propagation, noreturn, and (recently) guards.  I could see a couple
of
>>> implementation strategies here:
>>> 1) Extend BasicBlock to explicitly track potential early exiting
>>> instructions.  This would probably have to be conservative so that
things
>>> like nothrow inference aren't required to update all callers in
one go.
>>> 2) Conservative assume that BasicBlock has an unknown number of
early
>>> exiting instructions and write an analysis pass which answers
questions
>>> about where those early exits are.  Any pass which does code motion
would
>>> require this analysis.  (This is essentially the principled version
of our
>>> current hacks.)
>>>
>>>
>>> This analysis can be lazy/incremental. Most passes only do “safe”
>>> speculation and code sinking without side effects.
>>>
>>
>> While I agree it can be lazy, and should be an analysis, i'm,
again,
>> really not sure which passes you are thinking about here that do code
>> sinking/speculation that won't need it.
>>
>> Here's the list definitely needing it right now:
>> GVN
>> GVNHoist
>> LICM
>> LoadCombine
>> LoopReroll
>> LoopUnswitch
>> LoopVersioningLICM
>> MemCpyOptimizer
>> MergedLoadStoreMotion
>> Sink
>>
>> The list is almost certainly larger than this, this was a pretty
trivial
>> grep and examination.
>> (and doesn't take into account bugs, etc)
>>
>>
>
> (Note, this list is stuff in the Scalar directory only. Everything in
> Vectorize would n eed it, etc)
>
> And in case folks want more evidence that reasonable llvm developers need
> something that just gives easy and right answers, see
> https://reviews.llvm.org/D22547 from just yesterday :)
>
> To move this along, i will go build the analysis (I already have it mostly
> done, actually).  If someone updates our docs to make this stuff clear and
> obvious, that would be wonderful :)
>
> The analysis currently computes, internally, for a given BB:
>
> EarliestLoadHoistBarrier (used to see if you can move something out of a
> block)
> LatestLoadHoistBarrier (used to find the latest safe insertion point in a
> block, if any)
> EarliestStoreSinkBarrier (insertion)
> LatestStoreSinkBarrier (movement)
>
>
> (stores are maythrow dependent, loads are
> isGuaranteedToTransferExecutionToSuccessor dependent)
>
> I'm still coming up with the external API, the users all want to know
> either:
>
> 1. Can i move a load up out of this block to a direct predecessor
> 2. Can i move a store down out of this block to a direct successor
>
> I would argue that we should have this analysis *only* report the EBB
> information.  Doing this in the form of the information you've
mentioned is
> fine, but I would not want to see this become our deref analysis for
> instance.  I think that needs to be a separate analysis which is well
> layered on top of this one.  (i.e. once I encounter a hoist barrier, I need
> to then ask if a load is safe to speculate beyond that point as a separate
> question.)
>
>
> GVN's current load PRE is complex to get "right" from
it's current
> standpoint, the APi that will provide the easiest way to fix it will be:
>
> 3. What is the latest insertion point in a block for a load, if it is safe
> (IE the block does not end in an instruction you cannot move the load
> before).
>
> Nothing is doing global store sinking right now that i see, so nothing
> needs the analogous store api.
>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160721/972f67bf/attachment.html>