COW2LLVM: The isKnownUniquelyReferenced Deep-Dive

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

Nov 06, 2023

Subscribe to Jacob’s Tech Tavern for free to get ludicrously in-depth articles on iOS, Swift, tech, & indie projects in your inbox every two weeks.
Paid subscribers unlock Quick Hacks, my advanced tips series, and enjoy exclusive early access to my long-form articles.

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 🐮?

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

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:

.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.
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.
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.
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.
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.
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.
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.
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:

Find out how the isUnique Builtin function is applied to the Abstract Syntax Tree.
Work out how isUnique looks when it is transformed into Swift Intermediate Language.
Determine how isUnique behaves when converted to LLVM Intermediate Representation.
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:

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.
The generic inout parameter and Int1 result type of the signature are defined here — to synthesise the function signature of the FuncDecl.
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.

`The Builtin Module`

Swift’s Builtin module itself contains a set of low-level functions and operations that map directly to LLVM IR instructions in the Swift compiler, bypassing Swift’s ordinary safety mechanisms.

As we have seen, Builtins are used extensively to implement the Swift Standard Library for maximum performance, but Apple doesn’t trust us mere mortals to utilise them ourselves.

To be honest, I’m just one Tiger Beer deep, and I wouldn’t trust me either.

Tiger Beer, please sponsor my Substack 🙏🐯🍺.

AST Recap

Let’s recap on our progress so far:

isKnownUniquelyReferenced is based on an internal isUnique method, which uses a Builtin method, a special low-level function implemented deep in the Swift Compiler.

When Swift code compiles, the Builtin.isUnique method is added onto Swift’s Abstract Syntax Tree. This allows the LLVM IR operation to be called by the Swift Standard Library as if it were an ordinary Swift function.

What happens to this Builtin function next? How does the resulting low-level instruction check the reference count?

To truly find out, we need to go deeper.

Let’s check our compass.

Next stop?

SIL.

Swift Intermediate Language

After constructing an Abstract Syntax Tree and synthesising the Builtin function declarations, the Swift Compiler converts your code into Swift Intermediate Language. SIL is a precursor to LLVM IR, which itself undergoes multiple Swift-specific optimisation passes.

In our journey to find out how the isUnique Builtin is working, the obvious first port of call is the SIL Generation library — and specifically, SILGenBuiltin.cpp.

It isn’t trivial to find the right function calls. Naming isn’t fully consistent between compiler steps.

This function looks like it fits the bill:


static ManagedValue emitBuiltinIsUnique(SILGenFunction &SGF,
                                        SILLocation loc,
                                        SubstitutionMap subs,
                                        ArrayRef<ManagedValue> args,
                                        SGFContext C) {
  // ...

  return ManagedValue::forObjectRValueWithoutOwnership(
      SGF.B.createIsUnique(loc, args[0].getValue()));
}

As before, I’ve left out numerous lines of C++ assertions (mostly nullability checks) to make the code easier to follow.

This emitBuiltinIsUnique method, naturally, emits the SIL instructions for the Builtin function isUnique.

Following createIsUnique further, we find it defined in include/, with the public interface for SIL, SILBuilder.h:

IsUniqueInst *createIsUnique(SILLocation Loc, SILValue operand) {
  auto Int1Ty = SILType::getBuiltinIntegerType(1, getASTContext());
  return insert(new (getModule()) IsUniqueInst(getSILDebugLocation(Loc),
                                                 operand, Int1Ty));
}

C++ header files often inline method implementations. The createIsUnique method, in arcane C++ syntax, instantiates an instance of the type IsUniqueInst.

We locate the class declaration for IsUniqueInst at SILInstruction.h:

/// Given an object reference, return true iff it is non-nil and refers
/// to a native swift object with strong reference count of 1.
class IsUniqueInst
    : public UnaryInstructionBase<SILInstructionKind::IsUniqueInst,
                                  SingleValueInstruction> {
  friend SILBuilder;

  IsUniqueInst(SILDebugLocation DebugLoc, SILValue Operand, SILType BoolTy)
      : UnaryInstructionBase(DebugLoc, Operand, BoolTy) {}
};

IsUniqueInst ultimately defines the Swift Intermediate Language instruction, which checks whether an object on the heap is uniquely referenced. This SIL instruction is now ready for optimisation passes and eventual conversion into LLVM IR.

LLVM Intermediate Representation

Chris Lattner, creator of LLVM and Swift, apocryphally called Swift “syntactic sugar for LLVM.”

After parsing the Abstract Syntax Tree and Swift Intermediate Language generation, we arrive at the lowest level of the Swift frontend to LLVM: Synthesising LLVM Intermediate Representation. LLVM IR is a language-independent, high-level assembly language around which LLVM itself is designed. The LLVM toolchain optimises this IR for any CPU instruction set architecture you want to run your code on.

After searching through lib/IRGen/, the library for generating LLVM IR, we spot a familiar-looking declaration in IRGenSIL.cpp — this time, taking in an SIL instruction as an argument and emitting LLVM IR for the isUnique Builtin function:

static llvm::Value *emitIsUnique(IRGenSILFunction &IGF, SILValue operand,
                                 SourceLoc loc) {
  // ...

  LoadedRef ref =
    operTI.loadRefcountedPtr(IGF, loc, IGF.getLoweredAddress(operand));
  return
    IGF.emitIsUniqueCall(ref.getValue(), ref.getStyle(), loc, ref.isNonNull());
}

This method loads in a reference-counted pointer (to the object we’re checking the uniqueness of) in loadRefcountedPtr and emits the isUnique function call as LLVM IR.

Following this emitIsUniqueCall function call along; we are led to GenHeap.cpp in the IRGen/ library.

The documentation at the top of the file reads:
“This file implements routines for arbitrary Swift-native heap objects, such as layout and reference-counting.”
Is that light I see at the end of the tunnel?

Let’s read through the implementation of emitIsUniqueCall:

llvm::Value *IRGenFunction::
emitIsUniqueCall(llvm::Value *value, ReferenceCounting style, SourceLoc loc, bool isNonNull) {

  FunctionPointer fn;

  // ...

  switch (style) {
  case ReferenceCounting::Native: {
    fn = IGM.getIsUniquelyReferenced_nonNull_nativeFunctionPointer();

  // ...

  llvm::CallInst *call = Builder.CreateCall(fn, value);
  call->setDoesNotThrow();
  return call;
}

I’ve omitted a lot of code from here, which primarily handles additional cases in the switch statement for nullable types (optionals), Objective-C classes, and ObjC-bridged Swift types.

The getIsUniquelyReferenced_nonNull_nativeFunctionPointer() function call generates LLVM IR, which, when compiled and linked, calls into the Swift runtime upon execution.

It looks like our understanding of Builtins was a little incomplete. As well as low-level compiler types like Builtin.Int64 and functions such as Builtin.sadd_with_overflow_Int64, Builtins also can call directly into the Swift Runtime.

This is possible due to the incestuously interlinked nature of Chris Lattner’s Targaryen harem: The Swift Standard Library, the Swift Compiler, and the Swift Runtime.

The Swift Runtime

The Swift Runtime provides core functionality for executing Swift programmes — dynamic dispatch, error handling, and memory management operations such as allocation and reference counting.

I think you can see where this is going, at last.

Checking the docs

Let’s investigate where the LLVM IR instruction for IGM.getIsUniquelyReferenced_nonNull_nativeFunctionPointer ends up. As before, there is an art to hunting these down — naming isn’t consistent between the different layers of Swift’s implementation.

Like all good engineers, we can save ourselves hours of flailing about with a few minutes of reading documentation.

The Swift Runtime ABI documentation defines the interface the compiled LLVM IR instructions can call into. It’s clear that the definition we’re looking for is _swift_isUniquelyReferenced_nonNull_native.

Swift Object

Now, we can investigate the Swift Runtime source code in /stdlib/public/runtime. Looking at SwiftObject.mm (an Objective C++ file!), we find the function defined in the ABI:

bool swift::swift_isUniquelyReferenced_nonNull_native(const HeapObject *object) {
  assert(object != nullptr);
  assert(!object->refCounts.isDeiniting());
  return object->refCounts.isUniquelyReferenced();
}

After some assertions to avoid undefined behaviour from null pointers (no type-safe nullability here!), we are looking at the HeapObject argument, inspecting its refCount property, and asking if it’s uniquely referenced.

In the Swift Runtime, HeapObject defines how memory is allocated and managed for reference types such as classes, actors, and closures. Taking a peek into its source, we find the implementations of manual memory management functions. These will be familiar to anyone from the pre-ARC era: _swift_retain and _swift_release to increment and decrement the reference count of an object.

The refCounts property is itself an object which, you guessed it — maintains the reference counts (strong, weak, and unowned) of the object it relates to.

Like SEAL Team 6, let’s target where this isUniquelyReferenced() function is implemented on the RefCount for a HeapObject. With extreme prejudice.

SwiftShims

SwiftShims is a lightweight compatibility layer between the Standard Library, the Runtime, the Compiler, and the OS. This collection of C and C++ header files helps bridge code to underlying system libraries.

Critically, RefCount.h implements the method we’re searching for:

bool isUniquelyReferenced() const {
  auto bits = refCounts.load(SWIFT_MEMORY_ORDER_CONSUME);
  if (bits.hasSideTable())
    return bits.getSideTable()->isUniquelyReferenced();
  
  assert(!bits.getIsDeiniting());
  return bits.isUniquelyReferenced();
}

Firstly, in the isUniquelyReferenced property, we safely load the memory into the bits property and asks if it’s uniquely referenced.

For the interested: A side table is an optional, separate, reference count store for an object. They are created to store weak references, or used if the strong reference count overflows past the bits available in the ordinary memory layout of RefCount.

Next, we see the underlying implementation of isUniquelyReferenced() on the RefCount object.

SWIFT_ALWAYS_INLINE
bool isUniquelyReferenced() {
  // ...
  return
    !getUseSlowRC() && !getIsDeiniting() && getStrongExtraRefCount() == 0;
}

getUseSlowRC checks there’s side table storing overflowed pointer counts; and getIsDeiniting is fairly self-explanatory: deinitialisation only happens when a strong reference count is already zero.

The most important part here is getStrongExtraRefCount() == 0;.

Scrolling up for the inlined documentation, we read:

The strong RC is stored as an extra count: when the physical field is 0 the logical value is 1.

We now know that if an object has only one strong reference, StrongExtraRefCount is equal to zero.

The getStrongExtraRefCount function finds us the strong reference count that we’re looking for:

SWIFT_ALWAYS_INLINE
uint32_t getStrongExtraRefCount() const {
  assert(!hasSideTable());
  return uint32_t(getField(StrongExtraRefCount));
}

Here, we call into a C++ macro that returns the StrongExtraRefCount field stored in RefCount:

# define getField(name) getFieldIn(bits, Offsets, name)

# define getFieldIn(bits, offsets, name) \
    ((bits & offsets::name##Mask) >> offsets::name##Shift)

These macros operate directly on the bits stored by RefCount to return the integer value of StrongExtraRefCount. These bitwise operations can be dense, so let’s take this step-by-step:

The number StrongExtraRefCount is stored in some bits in RefCount‘s memory layout, bit-packed with other metadata to save space.
Let’s say the memory layout for the RefCount looks like 00101010 (in reality, it’s probably something like 64 bits wide).
The bit-mask has 1s for the locations of the bits that represent the StrongExtraRefCount, e.g., 00001100.
We can run a bitwise & operation to isolate just those bits, 0-ing out the rest of the data: leaving us with 00001000.
The offset ##Shift contains the number of significant binary digits which the StrongExtraRefCount lives at, which in this example is two bits from the end (in this one-byte example, we don’t need to fret about endian-ness).
The right bit-shift operator >> shifts our bit-masked data to the right, returning 00000010.
This, in full binary glory, is the strong extra reference count we’re looking for: 10, or “2” if you’re a decimal normie.

Therefore, our object has three strong references, meaning it’s not uniquely referenced!

The `isKnownUniquelyReferenced` Meme

We’ve finally determined how isKnownUniquelyReferenced is working behind the scenes to power our 🐮 optimisations.

It’s all a bit obvious, really.

Each time a new pointer is created to reference an object stored on heap memory strongly, it increments the strong reference count of that object.

isKnownUniquelyReferenced simply takes a sneaky backdoor route to ask the Swift Runtime whether this strong reference count is equal to 1.

7-tier expanding brain meme, created with Memegenerator

(Accessible version of the meme)

isKnownUniquelyReferenced just checks the strong reference count = 1
isUnique in the Swift Standard Library calls a Builtin function
The Abstract Syntax Tree synthesises Builtin functions so they can be called like regular Swift functions
Swift Intermediary Language emits the IsUniqueInst instruction, which performs the uniqueness check
The LLVM IR instruction generates the emitIsUnique instruction, which calls into the Swift Runtime ABI
The Swift Runtime inspects the bits on a HeapObject which stores the strong reference count
isKnownUniquelyReferenced just checks the strong reference count = 1

Conclusion

I assumed I’d poke around the Swift Standard Library, find some arcane private API that tracked a reference count property somewhere, and call it a day.

Curiosity is a heavy burden.

Like Dante, I kept pressing forward.

Into the haunted woods of the Standard Library source code. Through the purgatorial hallways of Builtin definitions. Deeper and deeper through the infernal circles of the Swift Compiler: the Abstract Syntax Tree, Swift Intermediary Language, and LLVM IR. Until finally, paradise was found in the Swift Runtime and SwiftShims.

I hope you had fun, learned a lot, and, most importantly — I hope you get the chance to flex your unbeatable 🐮 knowledge the next time you get an iOS job interview.

Do you think I missed anything important in my deep dive? Perhaps there’s another piece of the Swift Standard Library you’d love to see analysed to an absolutely ridiculous degree? Let me know in the comments!

If you really enjoyed this post, please share to help me grow my Substack audience.

Jacob’s Tech Tavern