[swift-dev] Reducing array abstraction

[Chris Lattner]

On Oct 8, 2017, at 3:30 PM, Erik Eckstein <eeckstein at apple.com> wrote:
>>> We definitely already have a heap->stack for classes in the guise of the StackPromotion optimization is that what you are talking about with the "array outlining" optimization? (outlining to me is referring to specifically code outlining). IIRC Erik (+CC) do special work to make it work for fixed size array. I would ask why that optimization is not kicking in for varargs. Perhaps, we could add a special recognition that the given array will not escape through a varargs? Or provide some way of saying, trust me this doesn't escape.
> 
> We already do heap->stack promotion for array buffers. This is done in the StackPromotion pass. It uses interprocedural escape analysis to check if it can be done. So if the callee is known it should work with the varargs array. BTW it also works in your example, in testAPI():
> 
> %1 = alloc_ref [stack] [tail_elems $Int * %0 : $Builtin.Word] $_ContiguousArrayStorage<Int>
> 
> But it’s not zero cost, because we initialize the metadata pointer + refcount in a runtime function. Also we do ref-count operations on the array in the callee (this will improve as soon as we have a ref count representation for immortal objects).

This is fantastic, I didn’t notice the [stack] marker there!  I’m thrilled you’re on top of this.  It looks like you have a well-developed framework here, which I haven’t fully ingested.  As such, I have a few questions for you:

1) With a debug build of the stdlib, the “isNative” and other sanity checks in the stdlib create a lot of bridge_object_to_word -> zext to i64 -> and-with-magic-arch-specific-constant checks to validate that the array is properly in a native state.  Have you considered introducing a “bridge_object_classify” SIL instruction which translates a bridge object value into a tuple of bits (isNative, isObjC, etc)  + unbitmangled value?  It seems super weird to me that there are a bunch of architecture-specific magic constants in stdlib/public/core/Builtin.swift.  It seems that these should be encapsulated into a SIL instruction, which would then allow the SIL optimizer to eliminate these checks.  

Particularly with a debug stdlib, it is super common to see an “array.uninitialized” call which then gets bitwise queried through a super-verbose series of SIL instructions that are opaque to the SIL optimizer (because they are arch specific).  Encapsulating this into SIL seems like a good call both from putting the arch-specific bits into the SIL layer which can expand it in IRGen (if it survives that long) and also optimize it away in the common case when it is knowable if these bits are 0 or 1 (as when coming from an array literal or other common known-native construct). 


2) You have an apparently great infra for escape analysis of arrays.  Have you considered adding one more check?  If the only uses of the reference counted object is a single release in the current function (common when passing array literals to C functions) then you can eliminating the heap allocation AND all the refcounting instructions and use a simple alloc_stack (of an array of tuples?) and put the dealloc stack where the single release is.  This seems like it would be a particularly bit win for the simple case of things like:

	memcpy(dest, [1,2,3,4], sizeof(Int)*4) 

among others.  Because the array literal would turn into the C-equivalent construct with zero overhead.


3) There are other optimizations like ArrayElementValuePropagation, which don’t handle the BridgeObjectToWordInst or AddressToPointer or UncheckedRefCastInst, and thus give up.  This causes a number of limitations (though I have no idea if they are important in practice or not): since conversions to UnsafePointer cannot mutate the array, they should not prevent element optimizations, count propagation optimizations, etc.

In any case, I’m super-thrilled you and your team have been pushing this forward, since arrays are really fundamental to all swift programs.   I’m very much looking forward to the time when we can pass borrowed array slices down the stack with zero overhead.

-Chris


-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-dev/attachments/20171009/f65b5d6c/attachment.html>