# Introduction

SIL is an SSA-form IR with high-level semantic information designed to
implement the Swift programming language.

In contrast to LLVM IR, SIL is a generally target-independent format
representation that can be used for code distribution, but it can also
express target-specific concepts as well as LLVM can.

SIL has three representations:

- In memory: SIL is represented by data structures which are implemented in the
  compiler sources. Optimization passes use the in-memory representation of SIL.

- Textual: The compiler and related utilities can print and parse textual SIL
  files. Textual SIL files have the file extension `.sil`.

- Binary: SIL can be stored and read from binary files. Binary SIL files are
  called "swift-module" files and have the extension `.swiftmodule`.
  Note that the binary format is not stable. Swift-module files are _not_
  compatible between compiler versions.

In this document SIL is explained by describing and using the syntax of the textual representation.

SIL is reliant on Swift's type system and declarations, so textual SIL syntax
is an extension of Swift's. A `.sil` file is a Swift source file with
added SIL definitions. The Swift source is parsed only for its
declarations; Swift `func` bodies (except for nested declarations) and
top-level code are ignored by the SIL parser. In a `.sil` file, there
are no implicit imports; the `Swift` and/or `Builtin` standard modules
must be imported explicitly if used.

## SIL in the Swift Compiler

At a high level, the Swift compiler follows a strict pipeline
architecture:

-   The _parser_ constructs an AST from Swift source code.
-   The _type checker_ (SEMA) type-checks the AST and annotates it with type
    information.
-   _SILGen_ generates *raw SIL* from an AST. In raw SIL dataflow requirements,
    such as definitive assignment, function returns, etc. are not yet been
    enforced.
-   A series of _mandatory optimization passes_ are run over the raw SIL both
    to perform required optimizations and to emit language-specific diagnostics.
    These are always run, regardless of the selected optimization mode,
    and produce *canonical SIL*.
-   General *optimization passes* run over the canonical
    SIL to improve performance of the resulting executable. These are
    enabled and controlled by the optimization level.
-   *IRGen* lowers canonical SIL to LLVM IR.
-   The LLVM backend applies LLVM optimizations, runs the
    LLVM code generator and emits binary code.

## Ownership SSA

Ownership SSA - or OSSA - is an augmented version of SSA that enforces
ownership invariants for SSA values in SIL functions. OSSA allows to verify
ownership. 

By using these ownership invariants, SIL in OSSA form can be validated
statically as not containing use after free errors or leaked memory. This
allows the compiler at compile time to detect bugs in SILGen and optimization
passes.

SILGen generates OSSA and OSSA is maintained throughout mandatory optimizations
and for part of optimization passes. At some point in the SIL pass pipeline
OSSA is "lowered" to plain SSA. From this point on no ownership verification
can be done anymore.

# SIL Stages

SIL files declare the processing stage of the included SIL with one of
the declarations `sil_stage raw` or `sil_stage canonical` at top level.
Only one such declaration may appear in a file.

```
decl ::= sil-stage-decl
sil-stage-decl ::= 'sil_stage' sil-stage

sil-stage ::= 'raw'
sil-stage ::= 'canonical'
```

There are different invariants on SIL depending on what stage of
processing has been applied to it.

-   **Raw SIL** is the form produced by SILGen that has not been run
    through mandatory optimizations or diagnostic passes. Raw SIL may
    not have a fully-constructed SSA graph. It may contain dataflow
    errors, like not all variables are initialized.
    Some instructions may be represented in non-canonical forms,
    such as `assign`. Raw SIL cannot be used for native code generation or
    distribution.
-   **Canonical SIL** is SIL as it exists after mandatory optimizations
    and diagnostics. Dataflow errors must be eliminated, and certain
    instructions must be canonicalized to simpler forms. Performance
    optimization and native code generation are derived from this form,
    and a module can be distributed containing SIL in this forms.

# SIL Types

SIL types are introduced with the `$` sigil. SIL's type system is
closely related to Swift's, and so the type after the `$` is parsed
largely according to Swift's type grammar.

```
sil-type ::= '$' '*'? generic-parameter-list? type
```

## Formal vs. Lowered Types

A formal type corresponds to a Swift type as it is defined in the source code.
The AST and the type checker work with formal types. Formal types can be
canonicalized which resolves type aliases and removes sugar. Later stages of
the compiler, like the SIL optimizer, only deal with canonical formal types.
Therefore, if we speak about formal types in the following sections, we always
refer to _canonical_ formal types.

Each formal type has a corresponding lowered type. However, most lowered types
are identical to their original formal type, for example all nominal types,
like classes, structs or enums (except `Optional`). Only a few kind of types
are lowered to a different lowered type. The most prominent example is function
types: a lowered function type adds information about the calling convention and 
it lowers tuple arguments to individual arguments.

For example, the formal type of

```
  func foo(a: (Int, String), b: any P) { }
```

is `((Int, String), any P) -> ()` whereas its lowered type is
`(Int, @guaranteed String, @in_guaranteed any P) -> ()`.

Deriving a lowered type from a formal type is called _type lowering_ which is
described in detail in the [Types](Types.md#Type-Lowering) document.

SIL types are always lowered types. The soundness of the SIL type system
depends on lowered types and the SIL optimizer needs lowered types to perform
correct optimizations.

However, there are a few places where SIL needs to refer to formal types. These
are operations on types which are "user visible", for example cast
instructions.

For example, a cast from `((Int, Bool)) -> ()` to `(Int, Bool) -> ()` fails
because the two formal function types differ. If a SIL cast instruction would
operate on SIL types, the cast would incorrectly succeed because the formal
types of those functions types are equivalent.

To summarize:

|                    | Definition                                   | Example                             |
| ------------------ | -------------------------------------------- | ----------------------------------- |
| **Formal type**    | original type from the source code           | `typealias C = ((Int, Bool)) -> ()` |
| **Canonical type** | formal type minus sugar, aliases resolved    | `((Int, Bool)) -> ()`               |
| **SIL type**       | lowered canonical type, plus is-address flag | `$*(Int, Bool) -> ()`               |


## Loadable vs. Address-only Types

Most SIL types are _loadable_. That means that a value of such a type can be
represented as an SSA value.  If a type is not loadable, it is address-only.
For example, if the compiler does not know the layout size of a type, the type
is address-only.

Values of address-only types can only live in memory and can only be accessed
via the address to the memory location.

> **_Note:_** that in future, SIL might represent address-only types as SSA values.

## Address vs. Object Types

The type of a value in SIL is either:
-   an *object type* `$T`, where `T` is a loadable type, or
-   an *address type* `$*T`, where `T` is a loadable or address-only type.

The *address of T* `$*T` is a pointer to memory containing a value of type
`$T`. This can be the address of a stack location
([`alloc_stack`](Instructions.md#alloc_stack), an internal pointer into a class
instance or reference-counted box, the address of a global variable, an
indirect function argument or an address produced from an unsafe pointer.
Addresses of loadable types can be loaded and stored to access values of those
types.

Addresses of address-only types can only be used with
instructions that manipulate their operands indirectly by address, such
as `copy_addr` or `destroy_addr`, or as arguments to functions. It is
illegal to have a value of type `$T` if `T` is address-only.

Addresses are not reference-counted pointers like class values are. They
cannot be retained or released.

Address types are not *first-class*: they cannot appear in recursive positions
in type expressions, e.g. the address of an address cannot be directly taken.
For example, the type `$**T` is not a legal type.

Addresses can be passed as arguments to functions if the corresponding
parameter is indirect. They cannot be returned, except by a `begin_apply`.

## Trivial vs. Non-Trivial Types

A *trivial type* is a loadable type with trivial value semantics.  Values of
trivial type can be copied or destroyed without any "extra effort" like retain
or release operations. For example, `Int` or `Bool` are trivial types.

In contrast, a non-trivial type requires extra code to be emitted to perform
copies and destroys. Some common reasons why a type is non-trivial are:

- The type (or a sub-type contained within it) contains a class reference which
  requiring retain/release operations.

- The type is not known at compile time, for example, a generic type or a
  resilient type.

- The type is a non-copyable type with a custom `deinit` that must be run when
  a value of such a type is destroyed.

> For more information on types in SIL see the [Types](Types.md) document.

# Functions

SIL functions are defined with the `sil` keyword. SIL function names are
introduced with the `@` sigil.
A SIL function name will become the LLVM IR name for the function, and is usually
the mangled name of the originating Swift declaration. The `sil` syntax
declares the function's name and SIL type, and defines the body of the
function inside braces. The declared type must be a function type, which
may be generic.

```
decl ::= sil-function
sil-function ::= 'sil' sil-linkage? sil-function-attribute+
                   sil-function-name ':' sil-type
                   '{' effects* sil-basic-block* '}'
sil-function-name ::= '@' [A-Za-z_0-9]+
```

If a function body does not contain at least one `sil-basic-block`, the
function is an external declaration.

For the list of function attributes see [FunctionAttributes](FunctionAttributes.md).

## Effects

Optionally a function can define a list of effects, which describe effects,
like memory effects or escaping effects for arguments. For details
see the documentation in
[Effects.swift](`SwiftCompilerSources/Sources/SIL/Effects.swift`).

```
effects ::= '[' argument-name ':' argument-effect (',' argument-effect)*]'
effects ::= '[' 'global' ':' global-effect (',' global-effect)*]'
argument-name ::= '%' [0-9]+

argument-effect ::= 'noescape' defined-effect? projection-path?
argument-effect ::= 'escape' defined-effect? projection-path? '=>' arg-or-return  // exclusive escape
argument-effect ::= 'escape' defined-effect? projection-path? '->' arg-or-return  // not-exclusive escape
argument-effect ::= side-effect

global-effect ::= 'traps'
global-effect ::= 'allocate'
global-effect ::= 'deinit_barrier'
global-effect ::= side-effect

side-effect ::= 'read' projection-path?
side-effect ::= 'write' projection-path?
side-effect ::= 'copy' projection-path?
side-effect ::= 'destroy' projection-path?

arg-or-return ::= argument-name ('.' projection-path)?
arg-or-return ::= '%r' ('.' projection-path)?
defined-effect ::= '!'    // the effect is defined in the source code and not
                          // derived by the optimizer

projection-path ::= path-component ('.' path-component)* 
path-component ::= 's' [0-9]+        // struct field
path-component ::= 'c' [0-9]+        // class field
path-component ::= 'ct'              // class tail element
path-component ::= 'e' [0-9]+        // enum case
path-component ::= [0-9]+            // tuple element
path-component ::= 'v**'             // any value fields
path-component ::= 'c*'              // any class field
path-component ::= '**'              // anything
```

Note that even function _declarations_, i.e. functions without basic blocks,
can defined effects. For example:

```
sil @foo : $@convention(thin) (@guaranteed String) -> String {
[%0: escape v** => %r.v**]
[global: read,copy]
}
```

# Basic Blocks

A function body consists of one or more basic blocks. Each basic block contains
one or more instructions and can have arguments. The last instruction of a
block is a "terminator" instruction.  The function's entry point is always the
first basic block in its body.

```
sil-basic-block ::= sil-label sil-instruction-def* sil-terminator
sil-label ::= sil-identifier ('(' sil-argument (',' sil-argument)* ')')? ':'
sil-argument-ownership-kind ::= @owned
sil-argument-ownership-kind ::= @guaranteed
sil-argument-ownership-kind ::= @reborrow
sil-argument ::= sil-value-name ':' sil-argument-ownership-kind? sil-type

sil-instruction-result ::= sil-value-name
sil-instruction-result ::= '(' (sil-value-name (',' sil-value-name)*)? ')'
sil-instruction-source-info ::= (',' sil-scope-ref)? (',' sil-loc)?
sil-instruction-def ::=
  (sil-instruction-result '=')? sil-instruction sil-instruction-source-info
```

For a detailed description of all instructions, see the [Instruction
Reference](Instructions.md).

## Basic Block Arguments

A block argument is a [value](#values-and-operands) and can have an ownership
kind specified before its type annotation.  
There are three kind of arguments:

- Function arguments: Per definition, the arguments of the first basic block in
  the function (the entry block) are the function's arguments. The types of the
  function arguments must match the parameters of the function type. Function
  arguments are bound by the function's caller:

```
    sil @foo : $@convention(thin) (Int, @guaranteed String) -> () {
    bb0(%0 : $Int, %1 : @guaranteed $String):
      ...
```

- Terminator results: Some terminator instructions forward their result to the
  successor block's arguments. For example a
  [`switch_enum`](Instructions.md#switch_enum) forwards the payload of an enum
  case to the corresponding successor block's argument.

```
      ...
      switch_enum %1, case #Optional.some!enumelt: bb1, default: bb2
    bb1(%term_result : $Int):
      ...
```

- Phi arguments: If a block has multiple predecessor blocks, the terminators of
  the predecessor blocks must be `br` or `cond_br` instructions and the
  operand values of those branch instructions are passed to the block's
  arguments. This corresponds to LLVM's phi nodes. Basic block arguments are
  bound by the branch from the predecessor block:

```
      cond_br %cond, bb1, bb2
    bb1:
      br bb3(%1)
    bb2:
      br bb3(%2)
    bb3(%phi : $Builtin.Int):
      return %phi
```

When a function is in Ownership SSA, arguments additionally have an
explicit annotated convention that describe the ownership semantics of
the argument value:

```
sil [ossa] @baz : $@convention(thin) (@owned String, @guaranteed String) -> () {
bb0(%0 : @owned $String, %1 : @guaranteed $String):
  ...
```

## The Control Flow Graph

The basic blocks of a function form a control flow graph (CFG). The nodes of
the CFG are the blocks. Edges are defined by the set of target blocks to which
the terminator instruction of a block may jump to. In the following example,
block `bb1` has two successor blocks `bb2` and `bb3` because the `cond_br`
might branch to `bb2` or `bb3`.
```
    bb1:
      cond_br %cond, bb2, bb3
```

## Control Flow Graph Invariants

In OSSA following rules apply to the CFG of a function:

- No critical edges: every edge in the CFG must have either a single
  predecessor or a single successor block.

- No unreachable blocks: All blocks must be reachable from the entry block
  of the function.

- No infinite loops: all cyclic strongly connected components (SCC) in the
  CFG must have at least one edge which is exiting the cyclic SCC.

Optimization passes must make sure to leave the CFG of an OSSA function in a
valid state by:

- inserting blocks at critical edges

- removing unreachable blocks

- creating artificial exit edges from infinite loops to dead-end blocks
  (= blocks which end in an `unreachable` instruction)

# Values and Operands

SIL values are introduced with the `%` sigil and named by an
alphanumeric identifier, which references the instruction result or basic block
argument that produces the value. SIL values may also refer to the
keyword 'undef', which is a value of undefined contents.

```
sil-identifier ::= [A-Za-z_0-9]+
sil-value-name ::= '%' sil-identifier
sil-value ::= sil-value-name
sil-value ::= 'undef'
sil-operand ::= sil-value
sil-operand ::= sil-value ':' sil-type
```

Values are used in instruction operands. Unlike LLVM IR, SIL instructions that
take value operands *only* accept value operands. 
References to literal constants, functions, global variables, or other entities
are introduced as the results of dedicated instructions such as
`integer_literal`, `function_ref`, and `global_addr`.

There are several kind of values in SIL:
- Basic block arguments
- Instruction results: most instructions have a single result. A few
  instructions have multiple results.
- `undef`

## Ownership

> **_Note:_** Many more details of OSSA are described in the [Ownership](Ownership.md) document.

In OSSA each non-trivial SIL value is statically mapped to an _ownership kind_:

- `@owned`: A value that exists independently of any other value and is
  consumed exactly once along all control flow paths through a function.
  "Consuming" the value means that it is either destroyed (via `destroy_value`)
  or consumed by a consuming instruction (e.g. stored to memory with `store`).

```
    sil [ossa] @foo : $@convention(thin) (@owned String, @inout String) -> () {
    bb0(%0 : @owned $String, %1 : $*String):
      cond_br %cond, bb1, bb2
    bb1:
      destroy_value %0        // "consumed" by destroying
      ...
    bb2:
      store %0 to [assign] %1 // consumed by storing to memory
```

- `@guaranteed`: A value with a scoped lifetime whose liveness is dependent on
  the lifetime of some other "enclosing" value. Due to this lifetime
  dependence, the enclosing value is required to be statically live over the
  entire scope where the guaranteed value is valid.

```
    bb0(%0 : @owned $String):
      %1 = begin_borrow %0   // %1 is borrowed from the enclosing value %0
      ...
      end_borrow %1          // %0 must be kept alive until here
      destroy_value %0
```

-  `@unowned`: A value that is only guaranteed to be instantaneously
    valid and must be copied before the value is used in an `@owned` or
    `@guaranteed` context. This is needed both to model argument values
    with the ObjC unsafe unowned argument convention and also to model
    the ownership resulting from bit-casting a trivial type to a
    non-trivial type. An unowned value should never be consumed.

Trivial values (like `Int`) values of address types don't have an ownership
kind associated.

The ownership kind of a value is statically determined:

- Basic block arguments have their ownership explicitly specified: 

```
    bb1(%0 : @owned $String, %1 : @guaranteed $String, %2 : $Int):
      ...
```

- The ownership of most instruction results can be statically determined from
  the instruction's kind and the offset of the value in the result tuple. For
  example `copy_value` has only one result and that result is always an owned
  value, whereas `begin_borrow` always produces a guaranteed value.

- Forwarding instructions: some instructions work with both, owned and
  guaranteed ownership, and "forward" the ownership from their operand(s) to
  their result(s), for example cast instructions.  
  If a forwarding instruction has multiple operands (like `struct` or `tuple`),
  the ownership of all operand values must be consistent. The operands values
  cannot have both guaranteed and owned ownership. However, it's possible to
  mix operands with ownership with trivial operands.

  ```
      bb1(%1 : @owned $A, %2 : @guaranteed $A, %3 : $Int):
        %4 = struct $S1 (%1, %3)   // owned
        %5 = struct $S1 (%2, %3)   // guaranteed
        %6 = struct $S2 (%1, %2)   // ERROR!
  ```

### Lifetimes

Lifetimes have following properties:

- A lifetime begins with a single definition - the "producer" of the value.

- There are many possibilities how an _owned_ value can be produced; either by
  an _owned_ block argument or by one of the many kind of instructions which have
  an _owned_ result value.

```
    bb0(%0: @owned $C):
      %1 = apply %f() : @convention(thin) () -> @owned D
      %2 = copy_value %x
      %3 = load [copy] %a
      ...
```

- Lifetimes of guaranteed values are called _borrow scopes_. A borrow scope
  starts with a single definition - the borrow-introducer. There are only a few
  different kinds of borrow-introducers:
    - guaranteed function argument: the lifetime spans over the whole function
      and doesn't need a scope-ending use.
    - `borrowed-from` instruction: it produces a borrow scope from a [reborrow
      phi argument](#Phi-arguments)
    - `begin_borrow` instruction
    - `load_borrow` instruction
    - `begin_apply` instruction

- A lifetime of a value must end exactly once along all control flow paths
  starting from its definition to function exits. It is illegal to end the
  lifetime more than once on a control flow path ("over-consume") or to _not_ end
  the lifetime on a control flow path ("leak").

- There are many kinds of instructions which end the lifetime of an _owned_
  value, which is called a _consume_. For example, `destroy_value` destroys the
  value (a _destroying consume_); a function call consumes a value if it is
  passed to a consuming argument, etc.

- A lifetime of a _guaranteed_ value  - a borrow scope - can only end at
  following instructions:
    - `end_borrow`
    - `end_apply` - in case the borrow introducer is a `begin_apply`
    - `br` instruction, which is the incoming value of a [reborrow phi
      argument] (#Phi-arguments).
    - guaranteed function arguments don't have a lifetime-ending instruction.

- Uses within a lifetime are called _non-consuming_ or _interior_ uses and must
  not appear _after_ the lifetime-ending consuming use ("use-after-consume") on
  all control flow paths. It depends on the kind of instruction if its operands
  are consuming or interior uses.

```
      %1 = load [copy] %0   // producer
      %2 = copy_value %1    // interior use of %1
      %3 = move_value %1    // consuming use of %1
      %4 = copy_value %1    // ERROR: use of %1 outside %1's lifetime
```

- Forwarding instructions end owned lifetimes and immediately produce a new
  owned value, which introduces a separate lifetime. The combined lifetimes over
  all forwarding instructions is called a _forward-extended_ lifetime.

```
      %1 = copy_value %0        -+               -+
      ...                        | lifetime       |
      // forwarding instruction  |                |
      %2 = struct $S (%1)       -+  -+            | forward-extended lifetime
                                     | lifetime   |
      // consuming instruction       |            |
      destroy_value %2              -+           -+
```

- Forwarding instructions do _not_ end the lifetime of guaranteed values.

```
      // borrow introducer
      %1 = begin_borrow                          -+
      ...                                         |
      // forwarding instruction                   | lifetime = borrow scope
      %2 = struct $S (%1)  // forwarded use =     |   
      ...                  //   interior use      |
      end_borrow %1                              -+
```

Note that forward-extended lifetimes don't necessarily have a single
definition. If a forwarding-lifetime contains forwarding aggregate instructions
or [phi arguments](#Phi-arguments) the forwarding-lifetime can have multiple
producers. For example:

```
  %1 = load [copy] %a1     // producer           -+
  %2 = load [copy] %a2     // producer            |  forward-extended lifetime
  %3 = struct $S (%1, %2)                         |
  %4 = destroy_value %3                          -+
```

Trivial values are never consumed and therefore don't have any restrictions on
where they are used on any control flow paths.

### Borrow Scopes

A borrow scope is a liverange of a guaranteed value which keeps its
[enclosing value](#Borrow-Introducers-and-Enclosing-Values)(s) alive.
It prevents optimizations from destroying an enclosing value before the borrow
scope has ended.
The most common borrow scope is a `begin_borrow`-`end_borrow` pair. But there
are other instructions which introduce borrow scopes:

#### `begin_borrow`

A [`begin_borrow`](Instructions.md#begin_borrow) defines a borrow scope for its
operand. The borrow scope ends at an `end_borrow`.

```
  %2 = begin_borrow %1          -+ borrow scope for %1
  // ...                         |
  end_borrow %2                 -+ %1 must be alive until here
```

Such a borrow scope can also "go through" a phi-argument. In this case the
overall borrow scope is the combination of multiple borrow lifetimes which are
"connected" by reborrow phi-arguments (see [Phi arguments](#phi-arguments)).

#### `load_borrow`

A [`load_borrow`](Instructions.md#load_borrow) is similar to `begin_borrow`,
except that its enclosing value is not an SSA value but a memory location.
During the scope of a `load_borrow`-`end_borrow` the memory location must not be mutated.

```
  %2 = load_borrow %addr    -+ borrow scope for memory value at %addr
  // ...                     |
  end_borrow %2             -+ memory at %addr must not be mutated until here
```

#### `store_borrow`

A [`store_borrow`](Instructions.md#store_borrow) is similar to `begin_borrow`,
except that beside defining a borrow scope it also stores the borrowed value
to a stack location. During the borrow scope (which ends at an `end_borrow`), the
borrowed value lives at the stack location.

```
  %s = alloc_stack $T
  %2 = store_borrow %1 to %s   -+ borrow scope for %1
  // ...                        |
  end_borrow %2                -+ %1 must be alive until here
  dealloc_stack %s
```

#### `partial_apply`

A [`partial_apply [on_stack]`](Instructions.md#partial_apply) defines borrow
scopes for its non-trivial arguments. The scope begins at the `partial_apply`
and ends at the end of the forward-extended lifetime of the `partial_apply`'s
result - the non-escaping closure.

```
  %3 = partial_apply [on_stack] %f(%1, %2)    -+ borrow scope for %1 and %2
  %4 = convert_function %3 to $SomeFuncType    |
  destroy_value %4                            -+ %1 and %2 must be alive until here
```
 
#### `mark_dependence`

A [`mark_dependence [nonescaping]`](Instructions.md#mark_dependence) defines a
borrow scope for its base operand. The scope begins at the `mark_dependence`
and ends at the forward-extended lifetime of the `mark_dependence`'s result.

```
  %3 = mark_dependence %2 on %1   -+ borrow scope for %1
  %4 = upcast %3 to $C             |
  destroy_value %4                -+ %1 must be alive until here
```

### Borrow Introducers and Enclosing Values

Every guaranteed value has a set of borrow-introducers (usually one), each of
which dominates the value and introduces a borrow scope that encloses all
forwarded uses of the guaranteed value.

```
  %1 = begin_borrow %0                // borrow introducer for %2, %3, %4
  %2 = begin_borrow %1                // borrow introducer for %3, %4
  %3 = tuple (%1, %2)                 // forwarded guaranteed value
  %4 = struct $S (%3)                 // forwarded guaranteed value
  end_borrow %2                       // end of borrow scope %2
  end_borrow %1                       // end of borrow scope %1
```

This example also shows that inner borrow scopes may be nested in outer borrow
scopes.

The _enclosing values_ of a forwarded guaranteed value are simply its
borrow-introducers.  Whereas the _enclosing values_ of a borrow-introducer
itself are the (owned or guaranteed) values from which the borrow scope is
derived, for example the operand of a `begin_borrow`.

```
                               Borrow Introducer    Enclosing Value
                               ~~~~~~~~~~~~~~~~~    ~~~~~~~~~~~~~~~
  %1 = load [copy] %0          -                    none
  %2 = begin_borrow %1         %2                   %1
  %3 = begin_borrow %2         %3                   %2
  %4 = struct $S (%3)          %3                   %3
```

Only the borrow-introducers `begin_borrow` and `borrowed-from` have enclosing
values. The set of enclosing values is empty for guaranteed function arguments,
`load_borrow` and `begin_apply`.

### Phi arguments

The lifetimes of owned and guaranteed values can end at branch (`br`)
instructions. Branch instructions define the incoming values for phi-arguments
in their target block. We distinguish between three kinds of ownership of
non-trivial phi arguments:

- `@owned`: The lifetimes of the incoming values end at the predecessor's `br`
  instructions. The phi-argument produces an owned value which starts a new
  lifetime. The combination of all those lifetimes is a _forward-extended_
  lifetime:

```
      cond_br %cond, bb1, bb2
    bb1:
      %1 = copy_value %0       -+ lifetime of %1     -+ forward-extended
      br bb3(%1)               -/                     |   lifetime
    bb2:                                              |
      %3 = load [copy] %addr   -+ lifetime of %3      |
      br bb3(%2)               -/                     |
    bb3(%phi : @owned $C):     -+ lifetime of %phi    |
      return %phi              -/                    -+
```

- `@reborrow`: The incoming values must be borrow-introducers and their borrow
  scopes end at the predecessor's `br` instructions. The phi-argument produces
  a guaranteed value which is borrow-introducing as well. The overall
  forward-extended borrow scope is a combination of all the individual borrow
  scopes.  A _reborrow_ argument must be directly forwarded to a
  [`borrowed-from`](Instructions.md#borrowed-from) instruction in the same
  basic block. The `borrowed-from` instruction specifies the enclosing values
  of the argument value.

```
      %1 = copy_addr %0
      cond_br %cond, bb1, bb2
    bb1:
      %2 = begin_borrow %1     -+ lifetime of %2     -+ forward-extended
      br bb3(%x, %2)           -/                     |   borrow scope
    bb2:                                              |
      %3 = load [copy] %addr                          |
      %4 = begin_borrow %1     -+ lifetime of %4      |
      br bb3(%3, %4)           -/                     |
    bb3(%p1 : @owned $C, %p2 : @reborrow $C): -+------|-- lifetime of %p2
      %6 = borrowed %p2 from (%p1, %1)         |      |
      end_borrow %6                           -+     -+
```

- `@guaranteed`: The incoming values can be either borrow introducers or
  forwarded guaranteed values. The phi argument does _not_ produce a new
  lifetime. Instead the argument can be viewed as interior use of another
  enclosing borrow scope. Such guaranteed phi-arguments are called "forwarded
  guaranteed phis".  
  Like reborrow arguments, the argument's enclosing values (= its borrow
  introducers) must be specified with a
  [`borrowed-from`](Instructions.md#borrowed-from) instruction.

```
      cond_br %cond, bb1, bb2
    bb1:
      %2 = begin_borrow %0                                  -+ forward-extended
      %3 = struct_extract %2, #S.a     // interior use       |   borrow scope
      br bb3(%2, %3)                                         |
    bb2:                                                     |
      %4 = begin_borrow %0                                   |
      %5 = struct_extract %2, #S.b     // interior use       |
      br bb3(%4, %5)                                         |
    bb3(%p1 : @reborrow $C, %p2 : @guaranteed $D):           |
      %6 = borrowed %p1 from (%0)                            |
      %7 = borrowed %p2 from (%p1)     // interior use       |
      %8 = ref_element_addr %7, #D.f   // interior use       |
      end_borrow %6                                         -+
```

### Lexical Lifetimes and Deinit Barriers

The optimizer is free to shrink lifetimes (e.g. by hoisting `destroy_value`
instructions) as long as all interior uses and inner borrow scopes stay
within the lifetime.

A forward-extended lifetimes can be marked as _lexical_ by either a `move_value
[lexical]` or `begin_borrow [lexical]` instruction. For such lifetimes further
restrictions apply. A destroy of such a value must not be hoisted above an
instruction which is or can be a _deinit barrier_.

Only the initial producer of a forward-extended lifetime needs to be marked as
_lexical_ in order to specify this property for all contributing lifetimes.

For details see [Variable Lifetimes](Ownership.md#variable-lifetimes) in the
Ownership document.

# Dominance

## Value and instruction dominance

Whenever an instruction uses a [value](#values-and-operands) as an
operand, the definition of the value must dominate the instruction.
This is a common concept across all SSA-like representations. SIL
uses a standard definition of dominance, modified slightly to account
for SIL's use of basic block arguments rather than phi instructions:

- The value `undef` always dominates an instruction.

- An instruction result `R` dominates an instruction `I` if the
  instruction that defines `R` dominates `I`.

- An argument of a basic block `B` dominates an instruction `I` if all
  initial paths passing through `I` must also pass through the start
  of `B`.

An instruction `D` dominates another instruction `I` if they are
different instructions and all initial paths passing through `I`
must also pass through `D`.

See [below](#definition-of-a-path) for the formal definition of an
initial path.

## Basic block dominance

A basic block `B1` dominates a basic block `B2` if they are different
blocks and if all initial paths passing through the start of `B2` must
also pass through through the start of `B1`.

This relationship between blocks can be thought of as creating a
directed acyclic graph of basic blocks, called the *dominance tree*.
The dominance tree is not directly represented in SIL; it is just
an emergent property of the dominance requirement on SIL functions.

## Joint post-dominance

Certain instructions are required to have a *joint post-dominance*
relationship with certain other instructions. Informally, this means
that all terminating paths through the first instruction must
eventually pass through one of the others. This is common for
instructions that define a scope in the SIL function, such as
`alloc_stack` and `begin_access`.

The dominating instruction is called the *scope instruction*,
and the post-dominating instructions are called the *scope-ending
instructions*. The specific joint post-dominance requirement
defines the set of instructions that count as scope-ending
instructions for the begin instruction.

For example, an `alloc_stack` instruction must be jointly
post-dominated by the set of `dealloc_stack` instructions
whose operand is the result of the `alloc_stack`. The
`alloc_stack` is the scope instruction, and the `dealloc_stack`s
are the scope-ending instructions.

The *scope* of a joint post-dominance relationship is the set
of all points in the function following the scope instruction
but prior to a scope-ending instruction. Making this precisely
defined is part of the point of the joint post-dominance rules.
A formal definition is given later.

In SIL, if an instruction acts as a scope instruction, it always
has exactly one set of scope-ending instructions associated
with it, and so it forms exactly one scope. People will therefore
often talk about, e.g., the scope of an `alloc_stack`, meaning
the scope between it and its `dealloc_stack`s. Furthermore,
there are no instructions in SIL which act as scope-ending
instructions for multiple scopes.

A scope instruction `I` is jointly post-dominated by its
scope-ending instructions if:

- All initial paths that pass through a scope-ending instruction
  of `I` must also pass through `I`. (This is just the normal
  dominance rule, and it is typically already required by the
  definition of the joint post-dominance relationship. For example,
  a `dealloc_stack` must be dominated by its associated
  `alloc_stack` because it uses its result as an operand.)

- All initial paths that pass through `I` twice must also pass
  through a scope-ending instruction of `I` in between.

- All initial paths that pass through a scope-ending instruction
  of `I` twice (not necessarily the same instruction) must also
  pass through `I` in between.

- All terminating initial paths that pass through `I` must also
  pass through a scope-ending instruction of `I`.

In other words, all paths must strictly alternate between `I`
and its scope-ending instructions, starting with `I` and (if
the path exits) ending with a scope-ending instruction.

Note that a scope-ending instruction does not need to appear on
a path following a scope instruction if the path doesn't exit
the function. In fact, a function needn't include any scope-ending
instructions for a particular scope instruction if all paths from
that point are non-terminating, such as by ending in `unreachable`
or containing an infinite loop.

A scope instruction `I` is *coherently* jointly post-dominated
by its scope-ending instructions if there is no point in the
function for which it is possible to construct two paths, both
ending in that point, which differ by whether they most recently
passed through `I` or one of its scope-ending instructions.
This is always true for points from which it is possible to
construct a terminating path, but it can be false for dead-end
points.

Several important joint post-dominance requirements in SIL
do not require coherence, including the stack-allocation rule.
Non-coherence allows optimizations to be more aggressive
across control flow that enters dead-end regions. Note that
control flow internal to a dead-end region is not special
in this way, so SIL analyses must not not simply check
whether a destination block is dead-end.

The *scope* defined by a joint post-dominance relationship for a
scope instruction `I` is the set of points in the function for
which:

- there exists an initial path that ends at that point and
  passes through `I`, but

- there does not an exist a simple initial path that ends at
  that point and passes through a scope-ending instruction
  of `I`.

In the absence of coherence, this second rule conservatively
shrinks the scope to the set of points that cannot possibly
have passed through a scope-ending instruction.

For a coherent joint post-dominance relationship, this
definition simplifies to the set of points for which there
exists an initial path that ends at that point and passes
through `I`, but which does not pass through a scope-ending
instruction of `I`.

Note that the point before a scope-ending instruction is always
within the scope.

## Definition of a path

A *point* in a SIL function is the moment before an instruction.
Every basic block has an entry point, which is the point before
its first instruction. The entry point of the entry block is also
called the entry point of the function.

A path through a SIL function is a path (in the usual graph-theory
sense) in the underlying directed graph of points, in which:

- every point in the SIL function is a vertex in the graph,

- each non-terminator instruction creates an edge from the point
  before it to the point after it, and

- each terminator instruction creates edges from the point before
  the terminator to the initial point of each its successor blocks.

A path is said to pass through an instruction if it includes
any of the edges created by that instruction. A path is said to
pass through the start of a basic block if it visits the entry
point of that block.

An *initial path* is a path which begins at the entry point of the
function. A *terminating path* is a path which ends at the point
before an exiting instruction, such as `return` or `throw`.

Note that the dominance rules generally require only an initial path,
not a terminating path. A path that simply stops in the middle of a
block still counts for dominance. Among other things, this ensures that
dominance holds in blocks that are part of an infinite loop.

A *dead-end point* is a point which cannot be included on any
terminating path. A *dead-end block* is a block for which the
entry point is a dead-end point. A *dead-end region* is a
strongly-connected component of the CFG containing only dead-end
blocks.

Note also that paths consider successors without regard to the
nature of the terminator. Paths that are provably impossible because
of value relationships still count for dominance. For example,
consider the following function:

```
    bb0(%cond : $Builtin.Int1):
      cond_br %cond, bb1, b22
    bb1:
      %value = integer_literal $Builtin.Int32, 0
      br bb3
    bb2:
      br bb3
    bb3:
      cond_br %cond, bb4, bb5
    bb4:
      %twice_value = builtin "add_Int32"(%value, %value) : $Builtin.Int32
      br bb6
    bb5:
      br bb6
    bb6:
      ret %cond
```

Dynamically, it is impossible to reach the `builtin` instruction
without passing through the definition of `%value`: to reach
the `builtin`, `%cond` must be `true`, and so the first `cond_br`
must have branched to `bb1`. This is not taken into consideration
by dominance, and so this function is ill-formed.

# Debug Information

Each instruction may have a debug location and a SIL scope reference at
the end.

```
sil-scope-ref ::= 'scope' [0-9]+
sil-scope ::= 'sil_scope' [0-9]+ '{'
                 sil-loc
                 'parent' scope-parent
                 ('inlined_at' sil-scope-ref)?
              '}'
scope-parent ::= sil-function-name ':' sil-type
scope-parent ::= sil-scope-ref
sil-loc ::= 'loc' string-literal ':' [0-9]+ ':' [0-9]+
```

Debug locations consist of a filename, a line number, and a
column number. If the debug location is omitted, it defaults to the
location in the SIL source file. SIL scopes describe the position inside
the lexical scope structure that the Swift expression a SIL instruction
was generated from had originally. SIL scopes also hold inlining
information.

# Declaration References

Some SIL instructions need to reference Swift declarations directly.
These references are introduced with the `#` sigil followed by the fully
qualified name of the Swift declaration. 

```
sil-decl-ref ::= '#' sil-identifier ('.' sil-identifier)* sil-decl-subref?
sil-decl-subref ::= '!' sil-decl-subref-part ('.' sil-decl-lang)? ('.' sil-decl-autodiff)?
sil-decl-subref ::= '!' sil-decl-lang
sil-decl-subref ::= '!' sil-decl-autodiff
sil-decl-subref-part ::= 'getter'
sil-decl-subref-part ::= 'setter'
sil-decl-subref-part ::= 'allocator'
sil-decl-subref-part ::= 'initializer'
sil-decl-subref-part ::= 'enumelt'
sil-decl-subref-part ::= 'destroyer'
sil-decl-subref-part ::= 'deallocator'
sil-decl-subref-part ::= 'globalaccessor'
sil-decl-subref-part ::= 'ivardestroyer'
sil-decl-subref-part ::= 'ivarinitializer'
sil-decl-subref-part ::= 'defaultarg' '.' [0-9]+
sil-decl-lang ::= 'foreign'
sil-decl-autodiff ::= sil-decl-autodiff-kind '.' sil-decl-autodiff-indices
sil-decl-autodiff-kind ::= 'jvp'
sil-decl-autodiff-kind ::= 'vjp'
sil-decl-autodiff-indices ::= [SU]+
```

Some Swift declarations are
decomposed into multiple entities at the SIL level. These are
distinguished by following the qualified name with `!` and one or more
`.`-separated component entity discriminators:

-   `getter`: the getter function for a `var` declaration
-   `setter`: the setter function for a `var` declaration
-   `allocator`: a `struct` or `enum` constructor, or a `class`'s
    *allocating constructor*
-   `initializer`: a `class`'s *initializing constructor*
-   `enumelt`: a member of a `enum` type.
-   `destroyer`: a class's destroying destructor
-   `deallocator`: a class's deallocating destructor
-   `globalaccessor`: the addressor function for a global variable
-   `ivardestroyer`: a class's ivar destroyer
-   `ivarinitializer`: a class's ivar initializer
-   `defaultarg.`*n*: the default argument-generating function for the
    *n*-th argument of a Swift `func`
-   `foreign`: a specific entry point for C/Objective-C interoperability

# Linkage

A linkage specifier controls the situations in which two objects in
different SIL modules are *linked*, i.e. treated as the same object.

```
sil-linkage ::= 'public'
sil-linkage ::= 'non_abi'
sil-linkage ::= 'package'
sil-linkage ::= 'package_non_abi'
sil-linkage ::= 'hidden'
sil-linkage ::= 'shared'
sil-linkage ::= 'private'
sil-linkage ::= 'public_external'
sil-linkage ::= 'package_external'
sil-linkage ::= 'hidden_external'
```

A linkage is *external* if it ends with the suffix `external`. An object
must be a definition if its linkage is not external.

All functions, global variables, and witness tables have linkage. The
default linkage of a definition is `public`. The default linkage of a
declaration is `public_external`.

On a global variable, an external linkage is what indicates that the
variable is not a definition. A variable lacking an explicit linkage
specifier is presumed a definition (and thus gets the default linkage
for definitions, `public`.)

## Definition of the *linked* relation

Two objects are linked if they have the same name and are mutually
visible:

-   An object with `public` or `public_external` linkage is always
    visible.
-   An object with `package` or `package_external` linkage is visible
    only to objects in the same Swift package.
-   An object with `hidden`, `hidden_external`, or `shared` linkage is
    visible only to objects in the same Swift module.
-   An object with `private` linkage is visible only to objects in the
    same SIL module.

Note that the *linked* relationship is an equivalence relation: it is
reflexive, symmetric, and transitive.

## Requirements on linked objects

If two objects are linked, they must have the same type.

If two objects are linked, they must have the same linkage, except:

-   A `public` object may be linked to a `public_external` object.
-   A `package` object may be linked to a `package_external` object.
-   A `hidden` object may be linked to a `hidden_external` object.

If two objects are linked, at most one may be a definition, unless:

-   both objects have `shared` linkage or
-   at least one of the objects has an external linkage.

If two objects are linked, and both are definitions, then the
definitions must be semantically equivalent. This equivalence may exist
only on the level of user-visible semantics of well-defined code; it
should not be taken to guarantee that the linked definitions are exactly
operationally equivalent. For example, one definition of a function
might copy a value out of an address parameter, while another may have
had an analysis applied to prove that said value is not needed.

## Non-ABI linkage

The `non_abi` and `package_non_abi` linkages are special linkages used for
definitions which only exist in serialized SIL, and do not define
visible symbols in the object file.

A definition with `non_abi` or `package_non_abi`  linkage behaves like it has
`shared` linkage, except that it must be serialized in the
SIL module even if not referenced from anywhere else in the module. For
example, this means it is considered a root for dead function
elimination.

When a `non_abi` definition is deserialized, it will have `shared` linkage.

There is no `non_abi_external` linkage. Instead,
referencing a `public_non_abi` or `package_non_abi` declaration is done with
- `hidden_external` if it is in a different source file but in the same module,
- `public_external` if it is in a different module.

# VTables

The potential destinations for [class_method](Instructions.md#class_method) and
[super_method](Instructions.md#super_method) are tracked in `sil_vtable` declarations
for every class type. The declaration contains a mapping from every
method of the class (including those inherited from its base class) to
the SIL function that implements the method for that class:

```
decl ::= sil-vtable
sil-vtable ::= 'sil_vtable' identifier '{' sil-vtable-entry* '}'
sil-vtable ::= 'sil_vtable' sil-type '{' sil-vtable-entry* '}'

sil-vtable-entry ::= sil-decl-ref ':' sil-linkage? sil-function-name
sil-vtable-entry ::= 'conformance' protocol-conformance
sil-vtable-entry ::= 'no_conformance' protocol-decl
```

SIL represents dynamic dispatch for class methods using the
[class_method](Instructions.md#class_method),
[super_method](Instructions.md#super_method),
[objc_method](Instructions.md#objc_method),
and [objc_super_method](Instructions.md#objc_super_method) instructions.

```
class A {
  func foo()
  func bar()
  func bas()
}

sil @A_foo : $@convention(thin) (@owned A) -> ()
sil @A_bar : $@convention(thin) (@owned A) -> ()
sil @A_bas : $@convention(thin) (@owned A) -> ()

sil_vtable A {
  #A.foo: @A_foo
  #A.bar: @A_bar
  #A.bas: @A_bas
}

class B : A {
  func bar()
}

sil @B_bar : $@convention(thin) (@owned B) -> ()

sil_vtable B {
  #A.foo: @A_foo
  #A.bar: @B_bar
  #A.bas: @A_bas
}

class C : B {
  func bas()
}

sil @C_bas : $@convention(thin) (@owned C) -> ()

sil_vtable C {
  #A.foo: @A_foo
  #A.bar: @B_bar
  #A.bas: @C_bas
}
```

Note that the declaration reference in the vtable is to the
least-derived method visible through that class (in the example above,
`B`'s vtable references `A.bar` and not `B.bar`, and `C`'s vtable
references `A.bas` and not `C.bas`). The Swift AST maintains override
relationships between declarations that can be used to look up
overridden methods in the SIL vtable for a derived class (such as
`C.bas` in `C`'s vtable).

In case the SIL function is a thunk, the function name is preceded with
the linkage of the original implementing function.

In addition to method entries, a vtable can also contain conformance entries.
Conformance entries are used for fast conformance lookup, which doesn't
need to query the runtime's conformance lookup table.
A conformance entry specifies if the class conforms or does not conform to a
protocol. At runtime, a type cast instruction to an existential can directly
load the witness table pointer from the vtable. If null, the class does not
conform to the protocol.

```
sil_vtable $C {
  conformance C : P   // C conforms to protocol P
  no_conformance Q    // C does not conform to protocol Q
  // ...
}
```

If the vtable refers to a specialized class, a SIL type specifies the
bound generic class type:

```
sil_vtable $G<Int> {
  // ...
}
```

# Witness Tables

```
decl ::= sil-witness-table
sil-witness-table ::= 'sil_witness_table' sil-linkage?
                      normal-protocol-conformance '{' sil-witness-entry* '}'
```

SIL encodes the information needed for dynamic dispatch of generic types
into witness tables. This information is used to produce runtime
dispatch tables when generating binary code. A witness table is
emitted for every declared explicit conformance. Generic types share one
generic witness table for all of their instances. Derived classes
inherit the witness tables of their base class.

```
protocol-conformance ::= normal-protocol-conformance
protocol-conformance ::= 'inherit' '(' protocol-conformance ')'
protocol-conformance ::= 'specialize' '<' substitution* '>'
                         '(' protocol-conformance ')'
protocol-conformance ::= 'dependent'
normal-protocol-conformance ::= identifier ':' identifier 'module' identifier
```

Witness tables are keyed by *protocol conformance*, which is a unique
identifier for a concrete type's conformance to a protocol.

-   A *normal protocol conformance* names a (potentially unbound
    generic) type, the protocol it conforms to, and the module in which
    the type or extension declaration that provides the conformance
    appears. These correspond 1:1 to protocol conformance declarations
    in the source code.
-   If a derived class conforms to a protocol through inheritance from
    its base class, this is represented by an *inherited protocol
    conformance*, which simply references the protocol conformance for
    the base class.
-   If an instance of a generic type conforms to a protocol, it does so
    with a *specialized conformance*, which provides the generic
    parameter bindings to the normal conformance, which should be for a
    generic type.

Witness tables are only directly associated with normal conformances.
Inherited and specialized conformances indirectly reference the witness
table of the underlying normal conformance.

```
sil-witness-entry ::= 'base_protocol' identifier ':' protocol-conformance
sil-witness-entry ::= 'method' sil-decl-ref ':' sil-function-name
sil-witness-entry ::= 'associated_type' identifier
sil-witness-entry ::= 'associated_conformance'
                      '(' identifier ':' identifier ')' ':' protocol-conformance
```

Witness tables consist of the following entries:

-   *Base protocol entries* provide references to the protocol
    conformances that satisfy the witnessed protocols' inherited
    protocols.
-   *Method entries* map a method requirement of the protocol to a SIL
    function that implements that method for the witness type. One
    method entry must exist for every required method of the witnessed
    protocol.
-   *Associated type entries* map an associated type requirement of the
    protocol to the type that satisfies that requirement for the witness
    type. Note that the witness type is a source-level Swift type and
    not a SIL type. One associated type entry must exist for every
    required associated type of the witnessed protocol.
-   *Associated type protocol entries* map a protocol requirement on an
    associated type to the protocol conformance that satisfies that
    requirement for the associated type.

# Default Witness Tables

```
decl ::= sil-default-witness-table
sil-default-witness-table ::= 'sil_default_witness_table'
                              identifier minimum-witness-table-size
                              '{' sil-default-witness-entry* '}'
minimum-witness-table-size ::= integer
```

SIL encodes requirements with resilient default implementations in a
default witness table. We say a requirement has a resilient default
implementation if the following conditions hold:

-   The requirement has a default implementation
-   The requirement is either the last requirement in the protocol, or
    all subsequent requirements also have resilient default
    implementations

The set of requirements with resilient default implementations is stored
in protocol metadata.

The minimum witness table size is the size of the witness table, in
words, not including any requirements with resilient default
implementations.

Any conforming witness table must have a size between the minimum size,
and the maximum size, which is equal to the minimum size plus the number
of default requirements.

At load time, if the runtime encounters a witness table with fewer than
the maximum number of witnesses, the witness table is copied, with
default witnesses copied in. This ensures that callers can always expect
to find the correct number of requirements in each witness table, and
new requirements can be added by the framework author, without breaking
client code, as long as the new requirements have resilient default
implementations.

Default witness tables are keyed by the protocol itself. Only protocols
with public visibility need a default witness table; private and
internal protocols are never seen outside the module, therefore there
are no resilience issues with adding new requirements.

```
sil-default-witness-entry ::= 'method' sil-decl-ref ':' sil-function-name
```

Default witness tables currently contain only one type of entry:

-   *Method entries* map a method requirement of the protocol to a SIL
    function that implements that method in a manner suitable for all
    witness types.

# Global Variables

The SIL representation of a global variable:

```
decl ::= sil-global-variable
static-initializer ::= '=' '{' sil-instruction-def* '}'
sil-global-variable ::= 'sil_global' sil-linkage identifier ':' sil-type
                           (static-initializer)?
```

Global variable access is performed by the `alloc_global`, `global_addr`
and `global_value` instructions.

A global can have a static initializer if its 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 @$S4test3varSiv : $Int {
  %0 = integer_literal $Builtin.Int64, 27
  %initval = struct $Int (%0 : $Builtin.Int64)
}
```

If a global variable does not have a static initializer, the `alloc_global`
instruction must be performed prior an access to initialize the storage.
Once a global's storage has been initialized, `global_addr` is used to
project the value.

If the last instruction in the static initializer is an `object`
instruction the global variable is a statically initialized object. In
this case the variable cannot be used as l-value, i.e. the reference to
the object cannot be modified. As a consequence the variable cannot be
accessed with `global_addr` but only with `global_value`.

# Differentiability Witnesses

```
decl ::= sil-differentiability-witness
sil-differentiability-witness ::=
    'sil_differentiability_witness'
    sil-linkage?
    '[' differentiability-kind ']'
    '[' 'parameters' sil-differentiability-witness-function-index-list ']'
    '[' 'results' sil-differentiability-witness-function-index-list ']'
    generic-parameter-clause?
    sil-function-name ':' sil-type
    sil-differentiability-witness-body?

differentiability-kind ::= 'forward' | 'reverse' | 'normal' | 'linear'

sil-differentiability-witness-body ::=
    '{' sil-differentiability-witness-entry?
        sil-differentiability-witness-entry? '}'

sil-differentiability-witness-entry ::=
    sil-differentiability-witness-entry-kind ':'
    sil-entry-name ':' sil-type

sil-differentiability-witness-entry-kind ::= 'jvp' | 'vjp'
```

SIL encodes function differentiability via differentiability witnesses.

Differentiability witnesses map a "key" (including an "original" SIL
function) to derivative SIL functions.

Differentiability witnesses are keyed by the following:

-   An "original" SIL function name.
-   Differentiability parameter indices.
-   Differentiability result indices.
-   A generic parameter clause, representing differentiability generic
    requirements.

Differentiability witnesses may have a body, specifying derivative
functions for the key. Verification checks that derivative functions
have the expected type based on the key.

```
sil_differentiability_witness hidden [normal] [parameters 0] [results 0] <T where T : Differentiable> @id : $@convention(thin) (T) -> T {
  jvp: @id_jvp : $@convention(thin) (T) -> (T, @owned @callee_guaranteed (T.TangentVector) -> T.TangentVector)
  vjp: @id_vjp : $@convention(thin) (T) -> (T, @owned @callee_guaranteed (T.TangentVector) -> T.TangentVector)
}
```

During SILGen, differentiability witnesses are emitted for the
following:

-   `@differentiable` declaration attributes.
-   `@derivative` declaration attributes. Registered
    derivative functions become differentiability witness entries.

The SIL differentiation transform canonicalizes differentiability
witnesses, filling in missing entries.

Differentiability witness entries are accessed via the
`differentiability_witness_function` instruction.

# Copy-on-Write Representation

Copy-on-Write (COW) data structures are implemented by a reference to an
object which is copied on mutation in case it's not uniquely
referenced.

A COW mutation sequence in SIL typically looks like:

```
  (%uniq, %buffer) = begin_cow_mutation %immutable_buffer : $BufferClass
  cond_br %uniq, bb_uniq, bb_not_unique
bb_uniq:
  br bb_mutate(%buffer : $BufferClass)
bb_not_unique:
  %copied_buffer = apply %copy_buffer_function(%buffer) : ...
  br bb_mutate(%copied_buffer : $BufferClass)
bb_mutate(%mutable_buffer : $BufferClass):
  %field = ref_element_addr %mutable_buffer : $BufferClass, #BufferClass.Field
  store %value to %field : $ValueType
  %new_immutable_buffer = end_cow_mutation %buffer : $BufferClass
```

Loading from a COW data structure looks like:

```
  %field1 = ref_element_addr [immutable] %immutable_buffer : $BufferClass, #BufferClass.Field
  %value1 = load %field1 : $*FieldType
...
  %field2 = ref_element_addr [immutable] %immutable_buffer : $BufferClass, #BufferClass.Field
  %value2 = load %field2 : $*FieldType
```

The `immutable` attribute means that loading values from
`ref_element_addr` and `ref_tail_addr` instructions, which have the
*same* operand, are equivalent. In other words, it's guaranteed that a
buffer's properties are not mutated between two
`ref_element/tail_addr [immutable]` as long as they have the same buffer
reference as operand. This is even true if e.g. the buffer 'escapes'
to an unknown function.

In the example above, `%value2` is equal to `%value1` because the
operand of both `ref_element_addr` instructions is the same
`%immutable_buffer`. Conceptually, the content of a COW buffer object
can be seen as part of the same *static* (immutable) SSA value as the
buffer reference.

The lifetime of a COW value is strictly separated into *mutable* and
*immutable* regions by `begin_cow_mutation` and `end_cow_mutation`
instructions:

```
  %b1 = alloc_ref $BufferClass
  // The buffer %b1 is mutable
  %b2 = end_cow_mutation %b1 : $BufferClass
  // The buffer %b2 is immutable
  (%u1, %b3) = begin_cow_mutation %b1 : $BufferClass
  // The buffer %b3 is mutable
  %b4 = end_cow_mutation %b3 : $BufferClass
  // The buffer %b4 is immutable
...
```

Both, `begin_cow_mutation` and `end_cow_mutation`, consume their operand
and return the new buffer as an *owned* value. The `begin_cow_mutation`
will compile down to a uniqueness check and `end_cow_mutation` will
compile to a no-op.

Although the physical pointer value of the returned buffer reference is
the same as the operand, it's important to generate a *new* buffer
reference in SIL. It prevents the optimizer from moving buffer accesses
from a *mutable* into a *immutable* region and vice versa.

Because the buffer *content* is conceptually part of the buffer
*reference* SSA value, there must be a new buffer reference every time
the buffer content is mutated.

To illustrate this, let's look at an example, where a COW value is
mutated in a loop. As with a scalar SSA value, also mutating a COW
buffer will enforce a phi-argument in the loop header block (for
simplicity the code for copying a non-unique buffer is not shown):

```
header_block(%b_phi : $BufferClass):
  (%u, %b_mutate) = begin_cow_mutation %b_phi : $BufferClass
  // Store something to %b_mutate
  %b_immutable = end_cow_mutation %b_mutate : $BufferClass
  cond_br %loop_cond, exit_block, backedge_block
backedge_block:
  br header_block(b_immutable : $BufferClass)
exit_block:
```

Two adjacent `begin_cow_mutation` and `end_cow_mutation` instructions
don't need to be in the same function.

# Stack discipline

Certain instructions in the SIL instruction set are identified as *stack
allocation instructions* or *stack deallocation instructions*. These
instructions jointly participate in a set of rules called the *stack
allocation discipline*, designed to allow SIL functions to easily and
safely dynamically allocate and deallocate memory in a scoped fashion on
the stack.

All stack deallocation instructions have an operand which identifies
their *paired* stack allocation instruction. This operand must always be
exactly the result of a stack allocation instruction, with no
intervening conversions, basic block arguments, or other abstractions. A
single stack allocation instruction may be paired with any number of
stack deallocation instructions. It can even be paired with no
instructions at all; by the rules below, this can only happen in
non-terminating functions.

- All stack allocation instructions must be jointly post-dominated
  by stack deallocation instructions paired with them.

- No path through the function that passes through a stack allocation
  instruction `B`, having already passed a stack allocation
  instruction `A`, may subsequently pass through a stack deallocation
  instruction paired with `A` without first passing through a stack
  deallocation instruction paired with `B`.

These two rules statically enforce that all stack allocations are
properly nested. In simpler terms:

- At every point in a SIL function, there is an ordered list of stack
  allocation instructions called the *active allocations list*.

- The active allocations list is empty at the start of the entry block
  of the function, and it must be empty again whenever an instruction
  that exits the function is reached, like `return` or `throw`.

- Whenever a stack allocation instruction is reached, it is added to
  the end of the list.

- Whenever a stack deallocation instruction is reached, its paired
  stack allocation instruction must be at the end of the list, which it
  is then removed from.

- The active allocations list always be the same on both sides of a
  control flow edge. This implies both that all successors of a block
  must start with the same list and that all predecessors of a block
  must end with the same list.

Note that these rules implicitly prevent stack allocations from leaking
or being double-freed.

The control-flow rule forbids certain patterns that would theoretically
be useful, such as conditionally performing an allocation around an
operation. SIL generally makes this sort of pattern somewhat difficult
to use, however, as it is illegal to locally abstract over addresses,
and therefore a conditional allocation cannot be used in the
intermediate operation anyway.

The stack discipline rules do not require coherent joint post-dominance.
This means that different control-flow paths entering a dead-end region
may disagree about the state of the stack. In such a region, the stack
discipline rules permit further allocation, but nothing that was not
allocated within the region can be deallocated.

# Structural type matching for pack indices

In order to catch type errors in applying pack indices, SIL requires the
projected element types of pack-indexing operations to be *structurally
well-typed* for the given pack type and index.

First, the projected element type must match the direct-ness of the
indexed pack type: if the pack is indirect, the project element type
must be an address type, and otherwise it must be an object type.

Second, the pack index must be a *pack indexing instruction* (one of
`scalar_pack_index`, `pack_pack_index`, or `dynamic_pack_index`), and it
must index into a pack type with the same shape as the indexed pack
type.

Third, additional restrictions must be satisfied depending on which pack
indexing instruction the pack index is:

-   For `scalar_pack_index`, the projected element type must be the same
    type as the scalar type at the given index in the pack type. (It
    must be a scalar type because of the shape restriction above.)

-   For `pack_pack_index`, the projected element type must be
    structurally well-typed for a slice of the pack type (as specified
    by the instruction) at the pack sub-index operand.

-   For `dynamic_pack_index`, consider each opened pack element
    archetype in the projected element type that is opened by an
    `open_pack_element` instruction whose pack index operand is the same
    `dynamic_pack_index` instruction. Because the pack substitutions in
    `open_pack_element` must have the same shape as the indexed pack
    type of its pack index operand, by transitivity they must have the
    same shape as the indexed pack type of the pack-indexing operation.
    Then for each component of this shape, the corresponding element
    component (or the pattern type for a projection component) of the
    indexed pack type must equal the result of applying a substitution
    to the projected element type which replaces any opened pack element
    archetype with the corresponding element component (pattern type for
    a projection component) of the pack substitution for that archetype
    in the `open_pack_element` which introduced it.

    For example, if the indexed pack type is
    `Pack{Optional<Int>, Optional<Float>, repeat Optional<each T>}`, a
    projected element type is `$*Optional<@pack_element("1234") U>` is
    structurally well-typed for a `dynamic_pack_index` pack index if
    `1234` is the UUID of an `open_pack_element` indexed by the same
    `dynamic_pack_index` instruction and the pack substitution
    corresponding to `U` in that `open_pack_element` is
    `Pack{Int, Float, repeat each T}`.

# Memory Lifetime

This section describes lifetime rules for values in
memory. With "memory" we refer to memory which is addressed by SIL
instruction with address-type operands, like `load`, `store`,
`switch_enum_addr`, etc.

Each memory location which holds a non-trivial value is either
uninitialized or initialized. A memory location gets initialized by
storing values into it (except assignment, which expects a location to
be already initialized). A memory location gets de-initialized by
"taking" from it or destroying it, e.g. with `destroy_addr`. It is
illegal to re-initialize a memory location or to use a location after it
was de-initialized.

If a memory location holds a trivial value (e.g. an `Int`), it is not
required to de-initialize the location.

The SIL verifier checks this rule for memory locations which can be
uniquely identified, for example and `alloc_stack` or an indirect
parameter. The verifier cannot check memory locations which are
potentially aliased, e.g. a `ref_element_addr` (a stored class
property).

## Lifetime of Enums in Memory

The situation is a bit more complicated with enums, because an enum can
have both, cases with non-trivial payloads and cases with no payload or
trivial payloads.

Even if an enum itself is not trivial (because it has at least on case
with a non-trivial payload), it is not required to de-initialize such an
enum memory location on paths where it's statically provable that the
enum contains a trivial or non-payload case.

That's the case if the destroy point is jointly dominated by:

-   a `store [trivial]` to the enum memory location.

or

-   an `inject_enum_addr` to the enum memory location with a trivial or
    non-payload case.

or

-   a successor of a `switch_enum` or `switch_enum_addr` for a trivial
    or non-payload case.

# Type Based Alias Analysis

SIL supports two types of Type Based Alias Analysis (TBAA): Class TBAA
and Typed Access TBAA.

## Class TBAA

Class instances and other *heap object references* are pointers at the
implementation level, but unlike SIL addresses, they are first class
values and can be `capture`-d and aliased. Swift, however, is
memory-safe and statically typed, so aliasing of classes is constrained
by the type system as follows:

-   A `Builtin.NativeObject` may alias any native Swift heap object,
    including a Swift class instance, a box allocated by `alloc_box`, or
    a thick function's closure context. It may not alias natively
    Objective-C class instances.
-   An `AnyObject` or `Builtin.BridgeObject` may alias any class
    instance, whether Swift or Objective-C, but may not alias
    non-class-instance heap objects.
-   Two values of the same class type `$C` may alias. Two values of
    related class type `$B` and `$D`, where there is a subclass
    relationship between `$B` and `$D`, may alias. Two values of
    unrelated class types may not alias. This includes different
    instantiations of a generic class type, such as `$C<Int>` and
    `$C<Float>`, which currently may never alias.
-   Without whole-program visibility, values of archetype or protocol
    type must be assumed to potentially alias any class instance. Even
    if it is locally apparent that a class does not conform to that
    protocol, another component may introduce a conformance by an
    extension. Similarly, a generic class instance, such as `$C<T>` for
    archetype `T`, must be assumed to potentially alias concrete
    instances of the generic type, such as `$C<Int>`, because `Int` is a
    potential substitution for `T`.

A violation of the above aliasing rules only results in undefined
behavior if the aliasing references are dereferenced within Swift code.
For example, `__SwiftNativeNS[Array|Dictionary|String]` classes alias
with `NS[Array|Dictionary|String]` classes even though they are not
statically related. Since Swift never directly accesses stored
properties on the Foundation classes, this aliasing does not pose a
danger.

## Typed Access TBAA

Define a *typed access* of an address or reference as one of the
following:

-   Any instruction that performs a typed read or write operation upon
    the memory at the given location (e.x. `load`, `store`).
-   Any instruction that yields a typed offset of the pointer by
    performing a typed projection operation (e.x. `ref_element_addr`,
    `tuple_element_addr`).

With limited exceptions, it is undefined behavior to perform a typed
access to an address or reference addressed memory is not bound to the
relevant type.

This allows the optimizer to assume that two addresses cannot alias if
there does not exist a substitution of archetypes that could cause one
of the types to be the type of a subobject of the other. Additionally,
this applies to the types of the values from which the addresses were
derived via a typed projection.

Consider the following SIL:

```
struct Element {
  var i: Int
}
struct S1 {
  var elt: Element
}
struct S2 {
  var elt: Element
}
%adr1 = struct_element_addr %ptr1 : $*S1, #S.elt
%adr2 = struct_element_addr %ptr2 : $*S2, #S.elt
```

The optimizer may assume that `%adr1` does not alias with `%adr2`
because the values that the addresses are derived from (`%ptr1` and
`%ptr2`) have unrelated types. However, in the following example, the
optimizer cannot assume that `%adr1` does not alias with `%adr2` because
`%adr2` is derived from a cast, and any subsequent typed operations on
the address will refer to the common `Element` type:

```
%adr1 = struct_element_addr %ptr1 : $*S1, #S.elt
%adr2 = pointer_to_address %ptr2 : $Builtin.RawPointer to $*Element
```

Exceptions to typed access TBAA rules are only allowed for blessed
alias-introducing operations. This permits limited type-punning. The
only current exception is the non-struct `pointer_to_address` variant.
The optimizer must be able to defensively determine that none of the
*roots* of an address are alias-introducing operations. An address root
is the operation that produces the address prior to applying any typed
projections, indexing, or casts. The following are valid address roots:

-   Object allocation that generates an address, such as `alloc_stack`
    and `alloc_box`.
-   Address-type function arguments. These are crucially *not*
    considered alias-introducing operations. It is illegal for the SIL
    optimizer to form a new function argument from an arbitrary
    address-type value. Doing so would require the optimizer to
    guarantee that the new argument is both has a non-alias-introducing
    address root and can be properly represented by the calling
    convention (address types do not have a fixed representation).
-   A strict cast from an untyped pointer,
    `pointer_to_address [strict]`. It is illegal for
    `pointer_to_address [strict]` to derive its address from an
    alias-introducing operation's value. A type punned address may only
    be produced from an opaque pointer via a non-strict
    `pointer_to_address` at the point of conversion.

Address-to-address casts, via `unchecked_addr_cast`, transparently
forward their source's address root, just like typed projections.

Address-type basic block arguments can be conservatively considered
aliasing-introducing operations; they are uncommon enough not to matter
and may eventually be prohibited altogether.

Although some pointer producing intrinsics exist, they do not need to be
considered alias-introducing exceptions to TBAA rules.
`Builtin.inttoptr` produces a `Builtin.RawPointer` which is not
interesting because by definition it may alias with everything.
Similarly, the LLVM builtins `Builtin.bitcast` and
`Builtin.trunc|sext|zextBitCast` cannot produce typed pointers. These
pointer values must be converted to an address via `pointer_to_address`
before typed access can occur. Whether the `pointer_to_address` is
strict determines whether aliasing may occur.

Memory may be rebound to an unrelated type. Addresses to unrelated types
may alias as long as typed access only occurs while memory is bound to
the relevant type. Consequently, the optimizer cannot outright assume
that addresses accessed as unrelated types are nonaliasing. For example,
pointer comparison cannot be eliminated simply because the two addresses
derived from those pointers are accessed as unrelated types at different
program points.

# Runtime Failure

Some operations, such as failed unconditional checked conversions or the
`cond_fail` instruction, cause a *runtime failure*, which terminates the
program. A runtime failure may be reordered freely as long as:

- it does not expose undefined behavior which is protected by the runtime
  failure; for example, it's illegal to move bounds checking past a potential
  buffer overflow.

- it only triggers in control flow paths where it would have been triggered
  originally; for example it's illegal to hoist a runtime failure out of a loop
  which may have a trip count of zero.

It is explicitly allowed to reorder runtime failures with externally visible
program behavior. For example, it's allowed to hoist a runtime failure above a
print statement.

# Undefined Behavior

Incorrect use of some operations is *undefined behavior*, such as
invalid unchecked casts involving `Builtin.RawPointer` types, or use of
compiler builtins that lower to LLVM instructions with undefined
behavior at the LLVM level. A SIL program with undefined behavior is
meaningless, much like undefined behavior in C, and has no predictable
semantics. Undefined behavior should not be triggered by valid SIL
emitted by a correct Swift program using a correct standard library, but
cannot in all cases be diagnosed or verified at the SIL level.

