How to talk to your kids about SIL type use

In the previous installment, I gave an overview of Swift’s formal type system, describing how types are represented in the AST. Now, let’s peel back a layer and dive into the type system of SIL, the Swift Intermediate Language. SIL adds a layer of detail missing from formal types, drawing a distinction between values and addresses, and making function types more explicit by introducing explicit annotations for argument and return value conventions.

A quick introduction to SIL

SIL is an intermediate language used by the Swift compiler, filling the gap between the AST and the LLVM IR. I cannot hope to give a complete description of SIL here; if you’re interested in learning more details, I suggesting starting with the following material:

For our purposes here, the following description suffices. A SIL program is a collection of named functions, with each function consisting of one or more basic blocks. A basic block is a linear sequence of instructions, with the last instruction in each block transferring control to another basic block, or returning from the function.

A SIL instruction may have a side-effect, and optionally produce a value. SIL programs are written in Static Single Assignment form, so values can never be re-defined; when an instruction references a value, the value is either an input argument to the current basic block, or was defined by a single unique instruction in that block. Note that unlike a “real” programming language, SIL is “flat”, in the sense that there’s no nested structure in the syntax; each instruction references values produced by other instructions, and performs one logical operation on them to produce a new value.

You can pass the -emit-silgen flag to the Swift compiler to see what the SIL for a Swift program looks like; here you will see the key elements of SIL, such as function definitions, instructions, and values.

SIL object and address types

Every SIL value has a SIL type; we can finally look at these types now.

SIL types are represented by the SILType class. There are two sorts of types in SIL; object types, and addresses. An object type here is not really an object in the “object-oriented programming” sense; object types include integers, a reference to a class instance, struct values, or functions. An address is a value storing a pointer to an object type. A SILType is basically a CanType together with a flag indicating if it is an object or address.

In SIL code, SIL object types are parsed and printed with a ‘$’ prefix, followed by a canonical formal type (see the definition of a canonical type from the previous article if you forgot what this means). SIL address types instead have a ‘$*’ prefix. Here are some simple examples:

$Int  // A Swift Int value
$*String // The address of a Swift String value
$(Int, Optional<(Int) -> ()>) // A tuple containing an integer and an optional value wrapping a function

Address types arise in SIL code generated from Swift expressions that load and store lvalues (assignable locations), as well as inout parameters. There are also some formal types that cannot be represented as a value in SIL, and must be manipulated indirectly via addresses; these are known as address-only types.

Note that not all formal types are legal SIL types; in particular, function types and metatypes are special. More on why later.

SIL type lowering

The operation of constructing a SIL type from a formal type is known as “type lowering”. For this reason, SIL types are sometimes referred to as “lowered types”.

Since SIL is an intermediate language, SIL values roughly correspond to an infinite register file for an abstract machine. Address-only types are essentially those types which are “too complex” to be stored in registers. Types which are not address-only are known as loadable types, meaning they can be loaded into registers.

It is legal to have an address type pointing to a type that is not address-only, but it is not legal to have an object type containing an address-only type.

You can find the bulk of the type lowering logic in lib/SIL/TypeLowering.cpp. The main entry points are ‘TypeLowering::getLoweredType()’, which returns a SIL type from a formal type, and ‘TypeLowering::getTypeLowering()’, which returns an object with some additional information describing the SIL type.

Sometimes, you already have a SIL type, and you need to check if it is a trivial, loadable or address-only type. For this purpose, the SILType class defines various methods: ‘SILType::isTrivial()’, ‘SILType::isLoadable()’, and ‘SILType::isAddressOnly()’.

Now, let’s look at how these operations are implemented.

Trivial, loadable, and address-only types

There are two key properties which force a type to be address-only:

  • Values of the type have to always exist in memory, because values of those types must have their addresses registered in some kind of global list. Passing such a value in a register does not make sense, because registers do not have global addresses.
  • Values of the type might not have a size known at compile-time; while SIL values can be larger than what fits in a single machine register, we have to know their size at compile-time, because IRGen will split up SIL values into zero or more “scalar” LLVM values, such as floats and integers.

The quintessential example of the first kind of type is a weak reference to a class instance. In Swift, weak references are used to break reference cycles in a memory-safe way. Weak references are implemented by registering all weak references in a global structure in the Swift runtime (if you’re curious, the code can be found in stdlib/public/runtime/SwiftObject.mm). When the last strong reference to a class instance is destroyed, the runtime checks to see if there are any outstanding weak references to the instance, and sets them to nil. Certainly, this would not work if weak references could appear in registers.

The canonical example of the second kind is a value whose type is a generic parameter. Recall that unlike C++ or Clay, Swift does not fully instantiate generic functions and types. It is possible to compile code that uses generics without knowing all the concrete types that may be bound to those generic parameters at compile-time; this is implemented by passing around generic values indirectly, together with metadata which tells the runtime the size and alignment of that type, as well as how to manipulate those values.

In addition to the distinction between loadable and address-only types, a further refinement exists among loadable types. We say a loadable type is trivial if values of the type can be freely copied and destroyed without executing additional logic. Examples of trivial types include integers, floating point values, and pointers to “permanent” structures such as metatypes.

The canonical example of a type which is loadable but not trivial is a strong reference to a class instance. We can load a class reference into a register as long as we “own” the value; single-assignment semantics ensure that reference counting semantics are preserved. There’s no need to register all strong references globally or store them in memory for any other reason, either. However, if we wish to copy a strong reference, we have to increment its reference count; and if we destroy a value containing a strong reference, we have to decrement the reference count.

When we ask SIL to lower an aggregate type such as a struct, enum or tuple type, the code first looks at the lowering of each member of the aggregate. If all members are trivial, the result is trivial; if all members are loadable, the result is loadable; and if at least one member is address-only, the entire result has to be address-only.

Note that lowering a class type never requires looking at the fields of the class; a class instance is always a single reference-counted pointer, which is loadable.

Furthermore, values of non-class bound protocol type — so-called “opaque existentials” — must be address-only, because they can contain any concrete type conforming to the protocol. Since we do not know the full set of conforming types at compile time, we must assume at least one of them may contain a weak reference (or some other opaque existential).

Recall the material from the previous section on the types of member references. This comes into play here, because we have to apply substitutions when lowering aggregate types with generic parameters. For example, consider this code:

struct Box<T> {
var value: T
}
$*Box<Any>  // address-only -- the aggregate contains an existential
$Box<Int> // trivial -- the aggregate only contains a trivial field
$Box<NSObject> // loadable -- contains a strong reference
struct Transform<T> {
var fn: (T) -> T
}
$Transform<Any>  // a function is always loadable
struct Phantom<T> {
var counter: Int
}
$Phantom<Any>  // trivial
$Phantom<() -> ()> // also trivial
$Phantom<NSObject> // ... also trivial

The first two types show that the lowering of a generic struct depends on the generic parameters; it does not make sense to talk about ‘Box’ being loadable or address-only, only ‘Box<Foo>’ for some type ‘Foo’.

Also, I’m including the ‘Transform’ example to show that merely the presence of generic parameters with an address-only lowering does not force the aggregate to be address-only, because here the generic parameter does not appear directly as the type of a field. Another case is the ‘Phantom’ type above, whose type parameter does not appear in the type of any of its fields at all.

Aside for C++ programmers

If you’ve ever worked with C++, you might recognize that a trivial type in SIL is the same as a POD (or Plain Old Data) type in C++. Indeed, if they were written in C++, trivial types would not need custom copy constructors, move constructors, or destructors.

Loadable types which are not trivial, on the other hand, do not have an analogue in C++ (or maybe they do now; I haven’t been paying much attention to C++ since ‘11). If you define a C++ class describing a smart pointer to a reference-counted object, the presence of a custom copy constructor and destructor force the value to be materialized in memory all of the time, because the compiler doesn’t know what the hell you’re doing inside the custom constructor; maybe you’re taking the address of ‘this’ and storing it somewhere.

If C++ had loadable types, they would involve some kind of special annotation that told the compiler that the move constructor can just trivially do a memcpy() of the value, even if there is a custom copy constructor or destructor. At this point, your smart pointer could be loaded into a register and passed around without issues. Sounds error-prone, which is why we think Swift is a better language than C++.

SIL function types

Consider the following Swift code:

struct Transform<T> {
let fn: (T) -> T
}
func double(x: Int) -> Int {
return x + x
}
let myTransform = Transform(fn: identity)

Here, we have a generic type ‘Transform’ storing a single function value. The function’s input and output are generic parameters. Generic parameters are address-only types, so they must be passed indirectly. You can imagine at the machine level, ‘Transform.fn’ takes an out-parameter pointer for the return value, and an in-parameter pointer for the argument.

On the other hand, the ‘double’ function manipulates integers, which are trivial; certainly we expect the input value ‘x’ to arrive in a register, with the return value stored in another register upon return from the function. Swift’s formal type system allows ‘identity’ to be stored in ‘myTransform.fn’, because after the substitution ‘T := Int’, the formal type of ‘myTransform.fn’ matches exactly the formal type of ‘double’. But if this were to be compiled naively as we’ve described so far, the code would do the wrong thing at runtime, because anyone calling ‘myTransform.fn’ with an integer would be passing the address of an integer value, and not the integer value itself as the function expects.

Clearly, the lowering of a function type is not just the lowering of its argument and result types; we need a more flexible representation, to express the case where the argument type might be trivial but still has to be passed indirectly. Furthermore, we realize that the lowering of a formal type must somehow take substitution into account. Indeed, to pass in a fully substituted formal type to ‘TypeLowering::getLoweredType()’. When lowering function types, metatypes and tuples, you must use the longer form of this function which takes two parameters; the substituted formal type, and an abstraction pattern.

An abstraction pattern is essentially the original, unsubstituted type from which the substituted type was derived. When lowering a function type, the argument passing conventions are derived from the abstraction pattern, and not the substituted formal type. The result of lowering a function type is an instance of the SILFunctionType class, which adds some more detail missing from FunctionType, namely “conventions” for how arguments and results are passed in; whether they are passed or returned by value, or passed or returned by address, and if there is an ownership transfer for loadable types (trivial types do not require ownership transfer).

One last complication is the function itself has a “convention” describing how it is invoked. In our previous example, ‘double’ is a global function which does not capture any values from lexical context, so we can pass it as a single function pointer; this is called a “thin” function. On the other hand, if we take a closure value and store it into ‘myTransform.fn’, we have to keep a context around to reference captured values; this is called a “thick” function. A thick function is represented as two values, a function pointer followed by a strong reference to a context object.

Here are some examples:

// Original type:    (Any, Int) -> ()
// Substituted type: (Any, Int) -> ()
$@convention(thick) (@in Any, Int) -> ()
// Original type:    (T) -> T
// Substituted type: (T) -> T
$@convention(thick) (@in T) -> @out T
// Original type:    (Int) -> Int
// Substituted type: (Int) -> Int
$@convention(thick) (Int) -> Int
// Original type:    (NSObject) -> NSObject
// Substituted type: (NSObject) -> NSObject
$@convention(thick) (@owned NSObject) -> @owned NSObject
// Original type:    (T) -> T
// Substituted type: (Int) -> Int
$@convention(thick) (@in Int) -> @out Int

Let’s revisit the example at the top of this section. The lowered type of ‘myTransform.fn’ is:

$@convention(thick) (@in T) -> @out T

We must use a thick function convention, because the user can store any function value in there, including a closure. Furthermore, we must pass and return T indirectly, because a generic parameter is an address-only type.

On the other hand, we have the lowered type of ‘double’:

$@convention(thin) (Int) -> Int

At this point, we still cannot compile our code, but at least we can detect a type mismatch at the level of SILFunctionTypes, instead of just mis-compiling incorrect code. A situation where the formal types of the expressions match, but the lowered types do not is called an “abstraction difference”. Abstraction differences are handled by SILGen wrapping the substituted function value inside a re-abstraction thunk.

The re-abstraction thunk forwards arguments, calls the function, and forwards the result, taking care to handle any abstraction differences in the arguments and results. If the substituted argument is trivial but the original argument is passed indirectly, the thunk will load the value from its address and pass it to the substituted function. Similarly, if the substituted result is trivial but the original result is returned indirectly, the thunk takes the substituted result value, and stores it into the indirect return address given to the thunk.

If you’ve ever seen re-abstraction thunks appear in debugger backtraces, you know what they are; mostly you can ignore them, it just means you’re doing stuff with generics, and Swift is doing some magic behind the scenes to make this work.

The code implementing re-abstraction thunks is found in lib/SILGen/SILGenPoly.cpp. The main entry points are the ‘SILGenFunction::emitOrigToSubstValue()’ and ‘SILGenFunction::emitSubstToOrigValue()’. Conceptually, these operations take a substituted type S, and an original type O:

  • ‘emitOrigToSubstValue()’ converts a value of type S at the abstraction level of O to a value of type S with the abstraction level of S
  • ‘emitSubstToOrigValue()’ converts a value of type S at the abstraction level of S to a value of type S with the abstraction level of O

In practice, these functions actually take a pair of types and abstraction patterns, because the same machinery is also used to emit thunks for performing various types of function conversions. For example, ‘Int’ is a formal sub-type of ‘Any’, and so ‘() -> Int’ is a formal sub-type of ‘() -> Any’; passing an ‘() -> Int’ as a value of type ‘() -> Any’ requires wrapping the substituted function in a thunk. The thunk which calls the function, then wraps the result in an existential before returning to the caller.

Lowered metatypes

If the above doesn’t make sense, don’t sweat it; it took me a while to grasp function type lowering and why re-abstraction thunks are necessary, and I probably did a poor job explaining it. Something similar comes up with metatypes, but here the problem is much easier to describe.

A value of metatype type must uniquely identify a formal type at runtime. So a value of type ‘NSObject.Type’ can contain any subclass of NSObject, of which there are thousands. Class metatypes are lowered as a pointer to a runtime type metadata object.

However, a value of type ‘Int.Type’ only needs to uniquely identify a subtype of ‘Int’, of which there is exactly one, ‘Int’ itself. So ‘Int.Type’ needs no storage at all, and indeed lowers as an empty value.

However, again, we have a situation where before and after substitution, the lowering is different; if I have a generic type parameter ‘T’, then ‘T.Type’ must lower as a pointer to a runtime value. If I’m operating on this value in a context with a substitution ‘T := Int’, then how do I store an ‘Int.Type’ there, when the ‘Int.Type’ value is empty?

As before, the answer is that metatypes must be lowered against an abstraction pattern, which tells SIL what the “most general” view of that value is going to be. The resulting metatype is annotated with a “convention”.

// Original type:    NSObject
// Substituted type: NSObject
$@convention(thick) NSObject
// Original type:    Int
// Substituted type: Int
$@convention(thin) Int
// Original type:    T
// Substituted type: T
$@convention(thick) Int

A “thick” metatype has a runtime representation, but a “thin” metatype does not. Note that class metatypes are always thick (although perhaps we could say that class metatypes for final classes are thin, we don’t do this right now). Only value types can have a thin metatype.

Instead of re-abstraction thunks, metatypes only require “thickness” conversions. When we go from thin to thick, we are loading the runtime value corresponding to a unique compile-time metatype. When we go from thick to thin, we’re simply discarding the runtime value, since we know it must be unique at compile-time.

One last thing: SIL box types

You might have seen SILBoxType appear in SIL code. They look like so in the printed representation of SIL:

$@box Int

A box type is a heap-allocated container for a value. Boxes arise as the types of mutable captured variables, as well as payloads of indirect enum cases. In the former case, the payload is shared and has mutable reference semantics; in the latter, it is immutable and behaves as a value. Unfortunately we do not distinguish between the two, which may or may not be a problem.

Substitutions with SIL types

Sometimes, it is necessary to perform a substitution on a SIL type containing dependent types to produce a fully-concrete SIL type.

Recall that a substitution maps GenericTypeParamTypes to formal types. Furthermore, when a SILType contains a BoundGenericType, the arguments of the BoundGenericType are formal types, not lowered SIL types.

On the other hand, components of tuple types are lowered SIL types. So we would expect SIL type substitution to behave as follows when we apply the substitution ‘T := Int.Type’:

// The generic type parameter appears in "unlowered position"
$Array<T> => $Array<Int.Type>
// The generic type parameter appears in "lowered position"
$(T, T) => $(@convention(thick) Int.Type, @convention(thick) Int.Type)

The logic for performing SIL type substitution is found in the ‘SILType::subst()’ method, and correctly handles lowering the right hand side of substitutions where appropriate, by calling back into type lowering using the original generic parameter as an abstraction pattern.

Optional payloads are maximally abstract

Now, you know enough to understand an interesting limitation of the current implementation. Recall the definition of the ‘Optional’ type in Swift:

enum Optional<T> {
case some(T)
case none
}

If I store a function value of type ‘(Int) -> Int’ in an optional payload, someone else might operate on it as if it were ‘(T) -> Int’, ‘(Int) -> T’, or ‘(T) -> T’. For this reason, functions stored inside optionals must be “maximally abstract”.

This is a tradeoff; while converting ‘Optional<(Int) -> Int>’ to ‘Optional<(T) -> T>’ can be done without any work at runtime, this comes at the expense of always storing both values as the latter.

It would be nice to change this at some point, so that optional payloads can be re-abstracted; this would require additional compiler support for optionals, but they already have special casing in semantic analysis anyway.

For now though, it is important to remember that when working with Optionals in SIL, the payload type is always unlowered. For example if you call ‘SILType::getAnyOptionalObjectType()’ on an Optional SILType, you have to subsequently lower the result, using the “maximally opaque” abstraction pattern, ‘AbstractionPattern::getOpaque()’. It is easy to make the mistake of forgetting to lower the payload type, or lower it using itself as an abstraction pattern, which will lead to SIL verifier failures or miscompiles.

Next steps

SIL types provide more detail to IRGen regarding function calling conventions and how values are stored in memory and passed around. At this point, we still don’t know the size and alignment of values, or how they are mapped to machine registers. This is IRGen’s job, which I’ll try to explain in my next post.

Conclusion

The SIL type system introduces the concept of addresses on top of the formal type system. SIL types are constructed from formal types by “type lowering”, which is tasked with classifying types into those which can be passed trivially, those that can be loaded into registers but require special copy and destroy behavior, and address-only types which must always be passed indirectly. This classification is also reflected in the arguments and results of lowered function types. It is possible for two expressions to have the same formal type but different SIL types, in which case SILGen knows to emit various conversions to bridge the abstraction difference. Lowered metatypes and SIL boxes round out the SIL type system.