[llvm-dev] RFC: Strong GC References in LLVM

[Sanjoy Das via llvm-dev]

Hi Daniel,

On Thu, Jul 21, 2016 at 12:17 PM, Daniel Berlin <dberlin at dberlin.org> wrote:
> 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)

Why would something be separately interested in C over A or D over B?
IOW, if you're looking for a "side exit" then isn't a may-throw call
is just one form of NOT(IsGuaranteedToTransferExecutionToSuccessor)?

Btw, I think todays implementation of
IsGuaranteedToTransferExecutionToSuccessor is fairly conservative
(IIRC it also considers volatile loads / stores as potentially
non-terminating).

-- Sanjoy

>
>
> 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> 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.
>>
>>
>



-- 
Sanjoy Das
http://playingwithpointers.com