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

[Sanjoy Das via llvm-dev]

On Thu, Jul 21, 2016 at 12:57 PM, Sanjoy Das
<sanjoy at playingwithpointers.com> wrote:
> 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)?

Ah, never mind, we can DSE across non-terminating calls but can't do
that across maythrow:

*x = 40;
while(1);  // behind a nounwind call
*x = 50;

==>

// *x = 40;
while(1);  // behind a nounwind call
*x = 50;

is okay (though mildly questionable), but

*x = 40;
may_throw();
*x = 50;

==>

// *x = 40;
may_throw();  // the frame that catches the exception can inspect *x
*x = 50;

is not okay, so maythrow is not "just another form of non-terminating
action" as I just said.

I wonder if there are optimizations that are legal across maythrow
calls that don't work across may_never_terminate calls.

-- Sanjoy




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



-- 
Sanjoy Das
http://playingwithpointers.com