[swift-dev] statically initialized arrays

[Joe Groff]

> On Jun 19, 2017, at 1:45 PM, Erik Eckstein <eeckstein at apple.com> wrote:
> 
>> 
>> On Jun 19, 2017, at 8:53 AM, Joe Groff <jgroff at apple.com> wrote:
>> 
>>> 
>>> On Jun 14, 2017, at 11:24 AM, Erik Eckstein via swift-dev <swift-dev at swift.org> wrote:
>>> 
>>> Hi,
>>> 
>>> I’m about implementing statically initialized arrays. It’s about allocating storage for arrays in the data section rather than on the heap.
>>> 
>>> Info: the array storage is a heap object. So in the following I’m using the general term “object” but the optimization will (probably) only handle array buffers.
>>> 
>>> This optimization can be done for array literals containing only other literals as elements.
>>> Example:
>>> 
>>> func createArray() -> [Int] {
>>>  return [1, 2, 3]
>>> }
>>> 
>>> The compiler can allocate the whole array buffer as a statically initialized global llvm-variable with a reference count of 2 to make it immortal.
>>> It avoids heap allocations for array literals in cases stack-promotion can’t kick in. It also saves code size.
>>> 
>>> What’s needed for this optimization?
>>> 
>>> 1) An optimization pass (GlobalOpt) which detects such array literal initialization patterns and “outlines” those into a statically initialized global variable
>>> 2) A representation of statically initialized global variables in SIL
>>> 3) IRGen to create statically initialized objects as global llvm-variables
>>> 
>>> ad 2) Changes in SIL:
>>> 
>>> Currently a static initialized sil_global is represented by having a reference to a globalinit function which has to match a very specific pattern (e.g. must contain a single store to the global).
>>> This is somehow quirky and would get even more complicated for statically initialized objects.
>>> 
>>> I’d like to change that so that the sil_global itself contains the initialization value.
>>> This part is not yet related to statically initialized objects. It just improves the representation of statically initialized global in general.
>>> 
>>> @@ -1210,7 +1210,9 @@ Global Variables
>>> ::
>>> 
>>>   decl ::= sil-global-variable
>>> +  static-initializer ::= '{' sil-instruction-def* '}'
>>>   sil-global-variable ::= 'sil_global' sil-linkage identifier ':' sil-type
>>> +                             (static-initializer)?
>>> 
>>> SIL representation of a global variable.
>>> 
>>> @@ -1221,6 +1223,19 @@ SIL instructions. Prior to performing any access on the global, the
>>> Once a global's storage has been initialized, ``global_addr`` is used to
>>> project the value.
>>> 
>>> +A global can also have a static initializer if it's initial value can be
>>> +composed of literals. The static initializer is represented as a list of
>>> +literal and aggregate instructions where the last instruction is the top-level
>>> +value of the static initializer::
>>> +
>>> +  sil_global hidden @_T04test3varSiv : $Int {
>>> +    %0 = integer_literal $Builtin.Int64, 27
>>> +    %1 = struct $Int (%0 : $Builtin.Int64)
>>> +  }
>>> +
>>> +In case a global has a static initializer, no ``alloc_global`` is needed before
>>> +it can be accessed.
>>> +
>>> 
>>> Now to represent a statically initialized object, we need a new instruction. Note that this “instruction" can only appear in the initializer of a sil_global.
>>> 
>>> +object
>>> +``````
>>> +::
>>> +
>>> +  sil-instruction ::= 'object' sil-type '(' (sil-operand (',' sil-operand)*)? ')'
>>> +
>>> +  object $T (%a : $A, %b : $B, ...)
>>> +  // $T must be a non-generic or bound generic reference type
>>> +  // The first operands must match the stored properties of T
>>> +  // Optionally there may be more elements, which are tail-allocated to T
>>> +
>>> +Constructs a statically initialized object. This instruction can only appear
>>> +as final instruction in a global variable static initializer list.
>>> 
>>> Finally we need an instruction to use such a statically initialized global object.
>>> 
>>> +global_object
>>> +`````````````
>>> +::
>>> +
>>> +  sil-instruction ::= 'global_object' sil-global-name ':' sil-type
>>> +
>>> +  %1 = global_object @v : $T
>>> +  // @v must be a global variable with a static initialized object
>>> +  // $T must be a reference type
>>> +
>>> +Creates a reference to the address of a global variable which has a static
>>> +initializer which is an object, i.e. the last instruction of the global's
>>> +static initializer list is an ``object`` instruction.
>>> 
>>> 
>>> ad 3) IRGen support
>>> 
>>> Generating statically initialized globals is already done today for structs and tuples.
>>> What’s needed is the handling of objects.
>>> In addition to creating the global itself, we also need a runtime call to initialize the object header. In other words: the object is statically initialized, except the header.
>>> 
>>> HeapObject *swift::swift_initImmortalObject(HeapMetadata const *metadata, HeapObject *object)
>>> 
>>> There are 2 reasons for that: first, the object header format is not part of the ABI. And second, in case of a bound generic type (e.g. array buffers) the metadata is not statically available.
>> 
>> I did some work along these lines already so that KeyPaths could be immortal heap objects. I added an entry point _swift_instantiateInertHeapObject that does exactly this. We could un-underscore it and promote it to a SWIFT_RUNTIME_EXPORT.
> 
> sounds good. If I understood it correctly, _swift_instantiateInertHeapObject currently initializes the object with a reference count of 1. For array buffers we would need 2. But I think for KeyPaths you are fine with 2 as well.

Yeah, 2 is probably a more semantically-correct value for global objects anyway to ward off uniqueness checks, at least till we get a real "inert" bit pattern.

-Joe