COW2LLVM: The isKnownUniquelyReferenced Deep-Dive

Demystify the Swift Compiler, the engine behind copy-on-write

The copy-on-write (a.k.a. CoW or 🐮) optimisation is the quintessential under-the-hood interview question for iOS engineers.

Today, we’re going on a quest to discover how this optimisation really works. I’m taking you on a journey deep into the enigmatic source code of the Swift compiler.

And, of course, I’m going to be referring to copy-on-write as 🐮 throughout.

Roadmap

• What is 🐮?

• Implementing 🐮

• The Swift Standard Library

• Builtins

• (Interlude) The Swift Compiler

• The Abstract Syntax Tree

• Swift Intermediate Language

• LLVM Intermediate Representation

• The Swift Runtime

• SwiftShims

• The isKnownUniquelyReferenced Meme

• Conclusion

What is 🐮?

For those not in the know, 🐮 optimises the performance of our Swift structs to get the best of both worlds: easy-to-reason-about value semantics with the low memory overhead of reference semantics.

Reference and value semantics

structs which utilise 🐮 store their data in a memory buffer on the heap. When the struct is copied, the lightweight pointer to this data in memory is the only thing that’s copied. The underlying memory is shared — this is reference semantics.

When the value of the data changes, value semantics kick in — the struct allocates a new buffer of memory on the heap, copies the updated data there, then points at the new buffer— leaving the original memory block, and other instances of the struct pointing to it, unchanged.

🐮 In the Swift Standard Library

Many fundamental types in the Swift Standard Library utilise this optimisation, such as:

• Array

• Set

• Dictionary

• String

• Data

When using these data structures, or types containing them, you reap the benefits of the underlying 🐮 optimisation for free. But it’s possible to implement 🐮 in your own types, too!

Implementing 🐮

Very senior iOS engineers will tell you how you can implement your own types that utilise 🐮 — check out this sample robbed straight from Apple’s Swift Optimisation Tips:

final class Ref<T> {
    var val: T
    init(_ v: T) { val = v }
}

struct Box<T> {
    var ref: Ref<T>
    init(_ x: T) { ref = Ref(x) }

    var value: T {
        get { return ref.val }
        set {
            if !isKnownUniquelyReferenced(&ref) {
                ref = Ref(newValue)
                return
            }
            ref.val = newValue
        }
    }
}

In short, you place your struct type, T, in Box, which acts as a wrapper over T. Box instantiates a class — an instance of Ref. This class, like all reference types, points to a memory buffer on the heap containing the data contained by T.

Getter

When we get the struct data wrapped in Box, we simply return the data from the Ref class — from the block of heap memory at which ref points.

Setter

But when we set this data, the outcome depends on whether our instance of Box<T> has been copied —that is, if it exists in more than one place:

• If there is only one instance of the Box struct, ref only has one reference to it, and we mutate the data as normal.

• But, if our entity has been passed around in multiple places, then the Box wrapper itself is copied due to its struct value semantics.

• This means there are multiple identical ref pointers to the same instance of the Ref class — multiple pointers to the heap memory where our data is stored.

• We, therefore, instantiate a new instance of Ref with ref = Ref(newValue), the updated data is written to a new memory buffer on the heap, and a new ref pointer is returned to that new instance, leaving the other refs in other copies of Box intact.

isKnownUniquelyReferenced

A mysterious function called isKnownUniquelyReferenced is the secret sauce that makes this optimisation possible.

I’m pulling back the curtain and searching for the wizard.

I’m going to figure out what the hell it does.

The Swift Standard Library

First things first.

Let’s download the Swift source code, search for isKnownUniquelyReferenced, and take a gander at the implementation.

Target acquired.

It’s holed up in ManagedBuffer.swift, underneath the definition of ManagedBufferPointer. I’m not the biggest fan of putting global functions underneath unrelated data structures, but who am I to question the wisdom of our Cupertinoverlords.

Here’s the implementation of isKnownUniquelyReferenced I’ve been searching for in all its glory:

@inlinable
public func isKnownUniquelyReferenced<T: AnyObject>(_ object: inout T) -> Bool {
    return _isUnique(&object)
}

Brilliant!

Another fine day’s work.

I can go home and have a beer now.

Builtins

Selfie from my iPhone (front camera)

I’ve got my beer!

I suppose I don’t have much on.

Maybe we can dive a little bit deeper and find out what _isUnique is doing.

We find it defined pretty close by — in the same folder — Builtin.swift:

//   When it is not an inout function, self is passed by
//   value... thus bumping the reference count and disturbing the
//   result we are trying to observe, Dr. Heisenberg!
@usableFromInline @_transparent
internal func _isUnique<T>(_ object: inout T) -> Bool {
    return Bool(Builtin.isUnique(&object))
} 

Loving the doc comments from Apple; let’s as an industry strive for more quantum physics references in our source code!

We need to find out what this Builtin.isUnique(&object) character is trying to do.

This is where it gets interesting.

We find this Builtin function defined somewhere totally different — Builtins.def.

BUILTIN_SIL_OPERATION(IsUnique, "isUnique", Special)

Why is this located in include/AST? What’s going on here?

Before we can progress any further, we need to understand a bit of theory about the Swift Compiler and LLVM.

(Interlude) The Swift Compiler

The Swift Compiler processes Swift source code files into efficient machine code. It’s a pipeline with several Swift-specific optimisation stages.

Swift compilation process — Image from Jesse Squires on Realm Academy

Let’s get our heads around each step in some detail:

1. .swift files are parsed and turned into a data structure known as an Abstract Syntax Tree (AST). This is vital for any compiler — it transforms code text files into a tree data structure containing all tokens, such as keywords, operators, and functions. This data structure is easy for algorithms to traverse systematically, making it easy for the next compilation stages to transform and optimise the code.

2. Semantic analysis is performed on the AST, performing tasks such as type-checking, evaluating protocol conformance, and checking variable scopes. Compiler warnings and errors can be emitted at this stage. Xcode maintains an AST as you code and performs this analysis as you type to help catch issues early.

3. Next comes a step that makes Swift a bit special — the compiler generates Swift Intermediate Language (SIL) from the AST. This is a halfway point between raw Swift code and the low-level LLVM IR produced at the end of the Swift-specific compilation process. Clean builds clear the cached AST, SIL, and LLVM IR, re-compiling from step 1, which is why they take longer than incremental builds.

4. This SIL is optimised through various passes. Automatic reference counting is optimised, specialised generic functions are generated, code is inlined, and devirtualization tries to replace dynamic method dispatches via witness table with more direct static dispatch. SIL also undergoes dataflow analysis, which emits errors to enforce Swift language requirements — e.g., when failing to return or throw from all function branches, or if you miss cases in a switch statement.

5. Optimised SIL is transformed into LLVM IR — LLVM Intermediate Representation. This is a high-level, language-independent flavour of assembly language around which LLVM is designed. LLVM IR bridges high-level languages with machine code for any CPU instruction set architecture.

6. LLVM is an open-source compiler toolchain that allows engineers to build a frontend that processes any programming language into LLVM IR and a backend that translates this IR into instructions for a given CPU. Once IR is generated, LLVM runs multiple optimisation passes in the middle, enhancing performance on the target CPU.

7. The LLVM backend transforms the LLVM IR into actual machine code and produces object .o files. These files contain these assembly instructions and metadata, strings, and debug information.

8. In the final compilation step, the Linker combines various object files with libraries into a single executable, which the OS can load to run a Swift application.

Our isKnownUniquelyReferenced Compass

With that substantial segue completed, let’s return to our isKnownUniquelyReferenced deep-dive.

Now that we understand how the Swift Compiler works, we have a compass with which to orient ourselves while we dredge the depths of the Swift source code.

Instead of inspecting the 859 individual instances of isUnique we find when we CMF+F the Swift codebase, we can:

1. Find out how the isUnique Builtin function is applied to the Abstract Syntax Tree.

2. Work out how isUnique looks when it is transformed into Swift Intermediate Language.

3. Determine how isUnique behaves when converted to LLVM Intermediate Representation.

4. Understand how these low-level instructions check whether an object is uniquely referenced.

The Abstract Syntax Tree

Last time we left off, we found the Builtin declaration for the isUnique method in the AST/ folder, Builtins.def:

/// isUnique only returns true for non-null, native swift object
/// references with a strong reference count of one.
BUILTIN_SIL_OPERATION(IsUnique, "isUnique", Special)

.def files contain exported C++ macro definitions — think of them as header files. The include/ folder defines a public interface to the Swift Compiler, which is made available to stdlib/, the Swift Standard Library.

Builtins on the AST

First, we need to work out how the Builtin isUnique function gets applied to the Abstract Syntax Tree.

We find the Builtin being synthesised here in Builtins.cpp:

case BuiltinValueKind::IsUnique:
case BuiltinValueKind::IsUnique_native:
case BuiltinValueKind::BeginCOWMutation:
case BuiltinValueKind::BeginCOWMutation_native:
    if (!Types.empty()) return nullptr;
    // BeginCOWMutation has the same signature as IsUnique.
    return getIsUniqueOperation(Context, Id);

static ValueDecl *getIsUniqueOperation(ASTContext &ctx, Identifier id) {
    // <T> (@inout T) -> Int1
    return getBuiltinFunction(ctx, id, _thin,
                              _generics(_unrestricted),
                              _parameters(_inout(_typeparam(0))),
                              _int(1));
}

Several methods are parsed out into the same operation here — IsUnique, IsUnique_native (which has some extra safety checks), and a couple of variants of BeginCOWMutation, which the Swift Standard Library uses to internally implement 🐮 optimisations for Array and its friends, ArraySlice and ContiguousArray.

These IsUnique variants all produce getIsUniqueOperation, to be inserted into the AST. This itself calls getBuiltinFunction to return a pointer to a ValueDecl, a special type in the Swift Compiler that represents a function signature on the Abstract Syntax Tree.

You’ll notice the function signature returns Int1 — a single-bit Integer — this is actually the underlying backing store used to implement the Swift Bool!

Synthesising a Builtin Function

getBuiltinFunction itself is implemented in this same file:

static FuncDecl *
getBuiltinFunction(ASTContext &ctx, Identifier id,
                   const ExtInfoS &extInfoS,
                   const GenericsS &genericsS,
                   const ParamsS &paramsS,
                   const ResultS &resultS) {

  // 1
  ModuleDecl *M = ctx.TheBuiltinModule;
  DeclContext *DC = &M->getMainFile(FileUnitKind::Builtin);
  SynthesisContext SC(ctx, DC);

  // ...

  return getBuiltinFunctionImpl(SC, id, genericParamList, genericSignature,
                                extInfoS, paramsS, resultS);
}

static FuncDecl *
getBuiltinFunctionImpl(SynthesisContext &SC, Identifier id,
                       GenericParamList *genericParams,
                       GenericSignature signature,
                       const ExtInfoS &extInfoS,
                       const ParamsS &paramsS,
                       const ResultS &resultS) {

  // 2 
  auto params = synthesizeParameterList(SC, paramsS);
  auto extInfo = synthesizeExtInfo(SC, extInfoS);
  auto resultType = synthesizeType(SC, resultS);

  // 3
  DeclName name(SC.Context, id, params);
  auto *FD = FuncDecl::createImplicit( /* ... */ )

  // ... 

  return FD;
}

With most code samples in this article, I’ve stripped out most of the code to make the key moving parts clearer, but feel free to look at the full source yourself.

Reading through carefully, we find three critical steps:

1. A reference to the Builtin module is retrieved from the AST context (ctx), a repository of shared information the compiler uses that includes the Builtin module.

2. The generic inout parameter and Int1 result type of the signature are defined here — to synthesise the function signature of the FuncDecl.

3. id, the Builtin function identifier, is used to synthesise the function declaration we want from the Builtin module — IsUnique in our case.

In summary, a FuncDecl, a function declaration, is synthesised. This implements the isUnique method on the Builtin module, and gets inserted into the Abstract Syntax Tree.

Ultimately, this allows Builtin functions to behave the same as regular Swift functions.