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

> 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. They don’t need to run the analysis.

Thanks Philip. I forgot to mention that LLVM passes historically have taken
advantage of implicit extended basic blocks (ISel) and were never improved to
handle general EBBs. It took years for loop opts to finally handle early exits
well.
-Andy
> 
> Philip
> 
> On 07/15/2016 06:57 PM, Daniel Berlin wrote:
>> 
>> 
>> On Fri, Jul 15, 2016 at 5:25 PM, Andrew Trick <atrick at apple.com
<mailto:atrick at apple.com>> wrote:
>> 
>>> On Jul 15, 2016, at 4:48 PM, Hal Finkel < <mailto:hfinkel at
anl.gov>hfinkel at anl.gov <mailto:hfinkel at anl.gov>> wrote:
>>> 
>>> Why? A decision was made to give pointers types, and we've
decided to change that. It is not clear to me that the decision to allow
implicit early exits was, in retrospect, optimal. I think it is completely
healthy for the project to reevaluate these kinds of decisions. We now have many
years of experience, bug reports, and we should have a good ability to evaluate
the compile-time impact of a potential change.
>> 
>> 
>> Let me rephrase: It didn’t seem to me like the fundamental problem we
were up against in this discussion, and it’s definitely very difficult to change
given the burden it would place on intrinsics.
>> 
>> 
>> Yes, this discussion has gone a bit off track, which i will apologize
for.
>>  
>> FWIW, for a long time I was a very strong proponent of explicit control
flow because I like making it easy to reason about CFG transforms and code
motion. But I gradually came around to realize it’s a legitimate design either
way. In some ways it works well not to have a CFG edge for exits where it’s
illegal to insert code.
>>  
>> I think LLVM passes have also been biased toward algorithms that scale
in the number of blocks.
>> If this scaling is a design goal that's really interesting. Most of
the memory opt and code motion algorithms i've worked on in LLVM are
block/instruction-capped in the same way (and most have lower caps than GCC due
to compile time impact on llvm).
>> There certainly was a time when that wasn't true (i remember back
in the day :P), but it's no longer true.
>> 
>> Of course, I don't actually think either design necessarily makes
scaling easier or harder, that's just "the state of the world".
>> 
>> 
> 
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160721/7acc95db/attachment.html>

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)


It would be nice to know which passes, specifically, you are thinking of
when you say "most" :)


> They don’t need to run the analysis.
>
> Thanks Philip. I forgot to mention that LLVM passes historically have
> taken advantage of implicit extended basic blocks (ISel) and were never
> improved to handle general EBBs. It took years for loop opts to finally
> handle early exits well.
> -Andy
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160721/37120af8/attachment.html>

> On 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
<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)
> 
> 
> It would be nice to know which passes, specifically, you are thinking of
when you say "most" :)
I don’t have a point to argue, just clarifying Philip's language. But if you
want to know what I was thinking it’s that there are a couple of passes doing
deliberate code motion: GVN and LICM (I didn’t think of the others) and a bunch
of passes doing incidental code motion like InstCombine, CodeGenPrepare, a
handful of passes calling SCEVExpander, etc.

I should have said “most passes at most do safe speculation…” so you don’t ask
me to grep through the code looking for incidental code motion :)

-Andy
>  
> They don’t need to run the analysis.
> 
> 
> Thanks Philip. I forgot to mention that LLVM passes historically have taken
advantage of implicit extended basic blocks (ISel) and were never improved to
handle general EBBs. It took years for loop opts to finally handle early exits
well.
> -Andy
> 
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160721/9b855d0a/attachment.html>

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>