This document provides information for developers working on the implementation of SIL. The formal specification of the Swift Intermediate Language is in SIL.rst. This is a guide to the internal implementation. Source comments normally provide this level of information as much as possible. However, some features of the implementation are spread out across the source base. This documentation is meant to offer a central point for approaching the source base with links to the code for more detailed comments.
TBD: Define the different levels of types. Explain type lowering with examples.
TBD: Explain how the various types fit together with pointers to the source: SILValue, SILInstruction, SingleValueInstruction, MultipleValueInstructionResult. And why it was done this way.
Throughout the compiler, integer indices are used to identify argument positions in several different contexts:
-
A
SILFunctionTypehas a tuple of parameters. -
The SIL function definition has a list of
SILFunctionArgument. This is the callee-side argument list. It includes indirect results. -
apply,try_apply, andbegin_applyhave "applied arguments": the subset of instruction operands representing the callee'sSILFunctionArgumentlist. -
partial_applyhas "applied arguments": the subset of instruction operands representing closure captures. Closure captures in turn map to a subset of the callee'sSILFunctionArgumentlist. -
In the above three contexts,
SILFunctionArgument,apply, andpartial_apply, the argument indices also depend on the SIL stage: Canonical vs. Lowered.
Consider the example:
func example<T>(i: Int, t: T) -> (Int, T) {
let foo = { return ($0, t) }
return foo(i)
}The closure foo has the indices as numbered below in each
context, ignoring the calling convention and boxing/unboxing of
captures for brevity:
The closure's SILFunctionType has two direct formal parameters at
indices (#0, #1) and one direct formal result of tuple type:
SILFunctionType(foo): (#0: Int, #1: T) -> @out (Int, T)
Canonical SIL with opaque values matches SILFunctionType. The
definition of foo has two direct SILFunctionArguments at (#0,
#1):
SILFunctionArguments: (#0: Int, #1: T) -> (Int, T)
The Lowered SIL for foos definition has an indirect "result
argument" at index #0. The function parameter indices are now (#1,
#2):
SILFunctionArguments: (#0: *T, #1: Int, #2: T) -> Int
Creation of the closure has one applied argument at index #0. Note
that the first applied argument is actually the second operand (the
first is the callee), and in lowered SIL, it is actually the third
SILFunctionArgument (after the indirect result and first parameter):
%closure = partial_apply @foo(#0: t)
Application of the closure with opaque values has one applied argument:
%resultTuple = apply %closure(#0: i)
Lowered application of the closure has two applied arguments:
%directResult = apply %closure(#0: %indirectResult: *T, #1: i)
The mapping between SILFunctionType and SILFunctionArgument, which depends
on the SIL stage, is managed by the
SILFunctionConventions
abstraction. This API follows naming conventions to communicate the meaning of the integer indices:
-
"Parameters" refer to the function signature's tuple of arguments.
-
"SILArguments" refer to the set of
SILFunctionArgumentin the callee's entry block, including any indirect results required by the current SIL stage.
These argument indices and their relative offsets should never be hardcoded. Although this is common practice in LLVM, it should be avoided in SIL: (a) the structure of SIL instructions, particularly applies, is much more nuanced than LLVM IR, (b) assumptions that may be valid at the initial point of use are often copied into parts of the code where they are no longer valid; and (c) unlike LLVM IR, SIL is not stable and will continue evolving.
Translation between SILArgument and parameter indices should use:
SILFunctionConventions::getSILArgIndexOfFirstParam().
Translation between SILArgument and result indices should use:
SILFunctionConventions::getSILArgIndexOfFirstIndirectResult().
Convenience methods exist for the most common uses, so there is
typically no need to use the above "IndexOfFirst" methods to translate
one integer index into another. The naming convention of the
convenience method should clearly indicate which form of index it
expects. For example, information about a parameter's type can be retrieved directly from a SILArgument index: getParamInfoForSILArg(index), getSILArgumentConvention(index), and getSILArgumentType(index).
Another abstraction,
ApplySite,
abstracts over the various kinds of apply instructions, including
try_apply, begin_apply, and partial_apply.
ApplySite::getSubstCalleeConv() is commonly used to query the
callee's SILFunctionConventions which provides information about the
function's type and its definition as explained above. Information about the applied arguments can be queried directly from the ApplySite API.
For example, ApplySite::getAppliedArgumentConvention(index) takes an
applied argument index, while
SILFunctionArguments::getSILArgumentConvention(index) takes a
SILFunctionArgument index. They both return the same information,
but from a different viewpoint.
A common mistake is to directly map the ApplySite's caller-side
arguments onto callee-side SILFunctionArguments. This happens to work
until the same code is exposed to a partial_apply. Instead, use the ApplySite API for applied argument indices, or use
ApplySite::getCalleeArgIndexOfFirstAppliedArg() to translate the
apply's arguments into function convention arguments.
Consistent use of common idioms for accessing arguments should be adopted throughout the compiler. Plenty of bugs have resulted from assumptions about the form of SIL made in one area of the compiler that have been copied into other parts of the compiler. For example, knowing that a block of code is guarded by a dynamic condition that rules out PartialApplies is no excuse to conflate applied arguments with function arguments. Also, without consistent use of common idioms, it becomes overly burdensome to evolve these APIs over time.
The AccessedStorage and AccessPath types formalize memory access
in SIL. Given an address-typed SIL value, it is possible to
reliably identify the storage location of the accessed
memory. AccessedStorage identifies an accessed storage
location. AccessPath contains both a storage location and the
"access path" within that memory object. The relevant API details are
documented in MemAccessUtils.h
SIL preserves the language semantics of formal variable access in the
form of access markers. begin_access identifies the address of the
formal access and end_access delimits the scope of the access. At
the language level, a formal access is an access to a local variable
or class property. For details, see
SE-0176: Enforce Exclusive Access to Memory
Access markers are preserved in SIL to:
-
verify exclusivity enforcement
-
optimize exclusivity checks following other transforms, such as converting dynamic checks into static checks
-
simplify and strengthen general analyses of memory access. For example,
begin_access [read] %addressindicates that the accessed address is immutable for the duration of its access scope
Computing AccessedStorage and AccessPath for any given SIL address
involves a use-def traversal to determine the origin of the
address. It may traverse operations on address, pointer, box, and
reference types. The logic that formalizes which SIL operations may be
involved in the def-use chain is encapsulated with the
AccessUseDefChainVisitor. The traversal can be customized by
implementing this visitor. Customization is not expected to change the
meaning of AccessedStorage or AccessPath. Rather, it is intended for
additional pass-specific book-keeping or for higher-level convenience
APIs that operate on the use-def chain bypassing AccessedStorage
completely.
Access def-use chains are divided by four points: the "root", the access "base", the outer-most "access" scope, and the "address" of a memory operation. For example:
struct S {
var field: Int64
}
class C {
var prop: S
}
%root = alloc_ref $C
%base = ref_element_addr %root : $C, #C.prop
%access = begin_access [read] [static] %base : $*S
%address = struct_element_addr %access : $*S, #.field
%value = load [trivial] %address : $*Int64
end_access %access : $*S
The first part of the def-use chain computes the formal access base
from the root of the object (e.g. alloc_ref -> ref_element_addr). The reference root might be a locally allocated
object, a function argument, a function result, or a reference loaded
from storage. There is no enforcement on the type of operation that
can produce a reference; however, only reference types or
Builtin.BridgeObject types are only allowed in this part of the
def-use chain. The reference root is the greatest common ancestor in
the def-use graph that can identify an object by a single SILValue. If
the root as an alloc_ref, then it is uniquely identified. The
def-use chain from the root to the base may contain reference casts
(isRCIdentityPreservingCast) and phis.
This example has an identifiable def-use chain from %root to %base:
class A {
var prop0: Int64
}
class B : A {
}
bb0:
%root = alloc_ref $B
cond_br _, bb1, bb2
bb1:
%a1 = upcast %root : $B to $A
br bb3(%a1 : $A)
bb2:
%a2 = upcast %root : $B to $A
br bb3(%a2 : $A)
bb3(%a : $A):
%bridge = ref_to_bridge_object %a : $A, %bits : $Builtin.Word
%ref = bridge_object_to_ref %bridge : $Builtin.BridgeObject to $A
%base = ref_element_addr %ref : $A, #A.prop0
Each object property and its tail storage is considered a separate
formal access base. The reference root is only one component of an
AccessedStorage location. AccessedStorage also identifies the class
property being accessed within that object.
The access base is the SILValue produced by an instruction that
directly identifies the kind of storage being accessed without further
use-def traversal. Common access bases are alloc_box, alloc_stack,
global_addr, ref_element_addr, and function arguments (see
AccessedStorage::Kind).
The access base is the same as the "root" SILValue for all storage kinds except global and class storage. Global storage has no root. For class storage the root is the SILValue that identifies object, described as the "reference root" above.
"Box" storage is uniquely identified by an alloc_box
instruction. Therefore, we consider the alloc_box to be the base of
the access. Box storage does not apply to all box types or box
projections, which may instead originate from arguments or indirect
enums for example.
Typically, the base is the address-type source operand of a
begin_access. However, the path from the access base to the
begin_access may include storage casts (see
isAccessedStorageCast). It may involve address, pointer, and box
types, and may traverse phis. For some kinds of storage, the base may
itself even be a non-address pointer. For phis that cannot be uniquely
resolved, the base may even be a box type.
This example has an identifiable def-use chain from %base to %access:
bb0:
%base = alloc_box $Int { var Int }
%boxadr = project_box %base : ${ var Int }
%p0 = address_to_pointer %boxadr : $*Int to $Builtin.RawPointer
cond_br _, bb1, bb2
bb1:
%p1 = copy_value %p0 : $Builtin.RawPointer
br bb3(%p1 : $Builtin.RawPointer)
bb2:
br bb3(%p0 : $Builtin.RawPointer)
bb3(%ptr : $Builtin.RawPointer):
%adr = pointer_to_address %ptr : $Builtin.RawPointer to $*Int
%access = begin_access [read] [static] %adr : $*Int
Note that address-type phis are illegal (full enforcement
pending). This is important for simplicity and efficiency, but also
allows for a class of storage optimizations, such as bitfields, in
which address storage is always uniquely determined. Currently, if a
(non-address) phi on the access path from base to access does not
have a common base, then it is considered an invalid access (the
AccessedStorage object is not valid). SIL verification ensures that a
formal access always has valid AccessedStorage (WIP). In other words, the
source of a begin_access marker must be a single, non-phi base. In
the future, for further simplicity, we may generally disallow box and
pointer phis unless they have a common base.
Not all SIL memory access is part of a formal access, but the
AccessedStorage and AccessPath abstractions are universally
applicable. Non-formal access still has an access base, even though
the use-def search does not begin at a begin_access marker. For
non-formal access, SIL verification is not as strict. An invalid
access is allowed, but handled conservatively. This is safe as long as
those non-formal accesses can never alias with class and global
storage. Class and global access is always guarded by formal access
markers--at least until static markers are stripped from SIL.
Nested access occurs when an access base is a function argument. The
caller always checks @inout arguments for exclusivity (an access
marker must exist in the caller). However, the argument itself is a
variable with its own formal access. Conflicts may occur in the callee
which were not evident in the caller. In this example, a conflict
occurs in hasNestedAccess but not in its caller:
func takesTwoInouts(_ : inout Int, _ : inout Int) -> () {}
func hasNestedAccess(_ x : inout Int) -> () {
takesTwoInouts(&x, &x)
}
var x = 0
hasNestedAccess(&x)
Produces these access markers:
sil @takesTwoInouts : $@convention(thin) (@inout Int, @inout Int) -> ()
sil @hasNestedAccess : $@convention(thin) (@inout Int) -> () {
bb0(%0 : $*Int):
%innerAccess = begin_access [modify] %0 : $*Int
%conflicting = begin_access [modify] %0 : $*Int
%f = function_ref @takesTwoInouts
apply %f(%innerAccess, %conflicting)
: $@convention(thin) (@inout Int, @inout Int) -> ()
end_access %conflicting : $*Int
end_access %innerAccess : $*Int
//...
}
%var = alloc_stack $Int
%outerAccess = begin_access [modify] %var : $*Int
%f = function_ref @hasNestedAccess
apply %f(%outerAccess) : $@convention(thin) (@inout Int) -> () {
end_access %outerAccess : $*Int
Nested accesses become part if the def-use chain after inlining. Here,
both %innerAccess and %conflicting are nested within
%outerAccess:
%var = alloc_stack $Int
%outerAccess = begin_access [modify] %var : $*Int
%innerAccess = begin_access [modify] %outerAccess : $*Int
%conflicting = begin_access [modify] %outerAccess : $*Int
%f = function_ref @takesTwoInouts
apply %f(%innerAccess, %conflicting)
: $@convention(thin) (@inout Int, @inout Int) -> ()
end_access %conflicting : $*Int
end_access %innerAccess : $*Int
end_access %outerAccess : $*Int
For most purposes, the inner access scopes are irrelevant. When we ask
for the "accessed storage" for %innerAccess, we get an
AccessedStorage value of "Stack" kind with base %var = alloc_stack. If instead of finding the original accessed storage, we
want to identify the enclosing formal access scope, we need to use a
different API that supports the special Nested storage kind. This is
typically only used for exclusivity diagnostics though.
TODO: Nested static accesses that result from inlining could potentially be removed, as long as DiagnoseStaticExclusivity has already run.
On the def-use chain between the outermost formal access scope within the current function and a memory operation, access projections identify subobjects laid out within the formally accessed variable. The sequence of access projections between the base and the memory address correspond to an access path.
For example, there is no formal access for struct fields. Instead,
they are addressed using a struct_element_addr within the access
scope:
%access = begin_access [read] [static] %base : $*S
%memaddr = struct_element_addr %access : $*S, #.field
%value = load [trivial] %memaddr : $*Int64
end_access %access : $*S
Note that is is possible to have a nested access scope on the address of a struct field, which may show up as an access of struct_element_addr after inlining. The rule is that access projections cannot occur outside of the outermost access scope within the function.
Access projections are address projections--they take an address at
operand zero and produce a single address result. Other
straightforward access projections include tuple_element_addr,
index_addr, and tail_addr (an aligned form of index_addr).
Enum payload extraction (unchecked_take_enum_data_addr) is also an
access projection, but it has no effect on the access path.
Indirect enum payload extraction is a special two-instruction form of
address projection (load : ${ var } -> project_box). For simplicity,
and to avoid the appearance of box types on the access path, this
should eventually be encapsulated in a single SIL instruction.
For example, the following complex def-use chain from %base to
%load actually has an empty access path:
%boxadr = unchecked_take_enum_data_addr %base : $*Enum<T>, #Enum.int!enumelt
%box = load [take] %boxadr : $*<τ_0_0> { var Int } <T>
%valadr = project_box %box : $<τ_0_0> { var Int } <T>, 0
%load = load [trivial] %valadr : $*Int
Storage casts may also occur within an access. This typically results
from accessors, which perform address-to-pointer
conversion. Pointer-to-address conversion performs a type cast, and
could lead to different subobject types corresponding to the same base
and access path. Access paths still uniquely identify a memory
location because it is illegal to cast memory to non-layout-compatible
types on same execution path (without an intervening bind_memory).
Address-type phis are prohibited, but because pointer and box types may be on the def-use chain, phis may also occur on an access path. A phi is only a valid part of an access path if it has no affect on the path components. This means that pointer casting and unboxing may occur on distinct phi paths, but index offsets and subobject projections may not. These rules are currently enforced to a limited extent, so it's possible for invalid access path to occur under certain conditions.
For example, the following is a valid def-use access chain, with an
access base defined in bb0, a memory operation in bb3 and an
index_addr and struct_element_addr on the access path:
class A {}
struct S {
var field0: Int64
var field1: Int64
}
bb0:
%base = ref_tail_addr %ref : $A, $S
%idxproj = index_addr %tail : $*S, %idx : $Builtin.Word
%p0 = address_to_pointer %idxproj : $*S to $Builtin.RawPointer
cond_br _, bb1, bb2
bb1:
%pcopy = copy_value %p0 : $Builtin.RawPointer
%adr1 = pointer_to_address [strict] %pcopy : $Builtin.RawPointer to $*S
%p1 = address_to_pointer %adr1 : $*S to $Builtin.RawPointer
br bb3(%p1 : $Builtin.RawPointer)
bb2:
br bb3(%p0 : $Builtin.RawPointer)
bb3(%p3 : $Builtin.RawPointer):
%adr3 = pointer_to_address [strict] %p3 : $Builtin.RawPointer to $*S
%field = struct_element_addr %adr3 : $*S, $S.field0
load %field : $*Int64
AccessedStorage identifies an accessed storage location, be it a
box, stack location, class property, global variable, or argument. It
is implemented as a value object that requires no compile-time memory
allocation and can be used as the hash key for that location. Extra
bits are also available for information specific to a particular
optimization pass. Its API provides the kind of location being
accessed and information about the location's uniqueness or whether it
is distinct from other storage.
Two uniquely identified storage locations may only alias if their AccessedStorage objects are identical.
AccessedStorage records the "root" SILValue of the access. The root is
the same as the access base for all storage kinds except global and
class storage. For class properties, the storage root is the reference
root of the object, not the base of the property. Multiple
ref_element_addr projections may exist for the same property. Global
variable storage is always uniquely identified, but it is impossible
to find all uses from the def-use chain alone. Multiple global_addr
instructions may reference the same variable. To find all global uses,
the client must independently find all global variable references
within the function. Clients that need to know which SILValue base was
discovered during use-def traversal in all cases can make use of
AccessedStorageWithBase or AccessPathWithBase.
AccessPath extends AccessedStorage to include the path components
that determine the address of a subobject within the access base. The
access path is a string of index offsets and subobject projection
indices.
struct S {
var field0: Int64
var field1: Int64
}
%eltadr = struct_element_addr %access : $*S, #.field1
Path: (#1)
class A {}
%tail = ref_tail_addr %ref : $A, $S
%one = integer_literal $Builtin.Word, 1
%elt = index_addr %tail : $*S, %one : $Builtin.Word
%field = struct_element_addr %elt : $*S, $S.field0
Path: (@1, #0)
Note that a projection from a reference type to the object's property or tail storage is not part of the access path because it is already identified by the storage location.
Offset indices are all folded into a single index at the head of the path (a missing offset implies offset zero). Offsets that are not static constants are still valid but are labeled "@Unknown". Indexing within a subobject is an ill-formed access, but is handled conservatively since this rule cannot be fully enforced.
For example, the following is an invalid access path, which just happens to point to field1:
%field0 = struct_element_addr %base : $*S, #field0
%field1 = index_addr %elt : $*Int64, %one : $Builtin.Word
Path: (INVALID)
The following APIs determine whether an access path contains another or may overlap with another.
AccessPath::contains(AccessPath subPath)
AccessPath::mayOverlap(AccessPath otherPath)
These are extremely light-weight APIs that, in the worst case, require a trivial linked list traversal with single pointer comparison for the length of subPath or otherPath.
Subobjects are both contained with and overlap with their parent storage. An unknown offset does not contain any known offsets but overlaps with all offsets.
For any accessed storage location and base, it must also be possible to reliably identify all uses of that storage location within the function for a particular access base. If the storage is uniquely identified, then that also implies that all uses of that storage within the function have been discovered. In other words, there are no aliases to the same storage that aren't covered by this use set.
The AccessPath::collectUses() API does this. It is possible to ask
for only the uses contained by the current path, or for all
potentially overlapping uses. It is guaranteed to return a complete
use set unless the client specifies a limit on the number of uses.
As passes begin to adopt AccessPath::collectUses(), I expect it to become a visitor pattern that allows the pass to perform custom book-keeping for certain types of uses.
The AccessPathVerification pass runs at key points in the pipeline
to ensure that all address uses are identified and have consistent
access paths. This pass ensures that the implementations of AccessPath
is internally consistent for all SIL patterns. Enforcing the validity
of the SIL itself, such as which operations are allowed on an access
def-use chain, is handled within the SIL verifier instead.
TBD: Possibly link to a separate document explaining the architecture of SILGen.
Some information from SIL.rst could be moved here.
TBD: Possibly link to a separate document explaining the architecture of IRGen.
TBD: describe the mechanism by which passes invalidate and update the PassManager and its available analyses.
HighLevelSILOptimizations.rst discusses how the optimizer imbues certain special SIL types and SIL functions with higher level semantics.