This document describes the design of the Swift Optimizer. It is intended for developers who wish to debug, improve or simply understand what the Swift optimizer does. Basic familiarity with the Swift programming language and knowledge of compiler optimizations is required.
The Swift compiler translates textual Swift programs into LLVM-IR and uses multiple representations in between. The Swift frontend is responsible for translating textual Swift programs into well-formed and type-checked programs that are encoded in the SIL intermediate representation. The frontend emits SIL in a phase that's called SILGen (stands for SIL-generation). Next, the Swift compiler performs a sequence of transformations, such as inlining and constant propagation that allow the Swift compiler to emit diagnostic messages (such as warnings for uninitialized variables or arithmetic overflow). Next, the Swift optimizer transforms the code to make it faster. The optimizer removes redundant reference counting operations, devirtualizes function calls, and specializes generics and closures. This phase of the compiler is the focus of this document. Finally, the SIL intermediate representation is passed on to the IRGen phase (stands for intermediate representation generation phase) that lowers SIL into LLVM IR. The LLVM backend optimizes and emits binary code for the compiled program.
Please refer to the document "Swift Intermediate Language (SIL)" for more details about the SIL IR.
The compiler optimizer is responsible for optimizing the program using the high-level information that's available at the SIL level. When SIL is lowered to LLVM-IR the high-level information of the program is lost. It is important to understand that after IRGen, the LLVM optimizer can't perform high-level optimizations such as inlining of closures or CSE-ing of virtual method lookups. When a SIL virtual call or some code that deals with generics is lowered to LLVM-IR, to the optimizer this code looks like a bunch of loads, stores and opaque calls, and the LLVM-optimizer can't do anything about it.
The goal of the Swift optimizer is not to reimplement optimizations that already exist in the LLVM optimizer. The goal is to implement optimizations that can't be implemented in LLVM-IR because the high-level semantic information is lost. The Swift optimizer does have some optimizations that are similar to LLVM optimizations, like SSA-construction and function inlining. These optimizations are implemented at the SIL-level because they are required for exposing other higher-level optimizations. For example, the ARC optimizer and devirtualizer need SSA representation to analyze the program, and dead-code-elimination is a prerequisite to the array optimizations.
The Swift pass manager is the unit that executes optimization passes on the functions in the Swift module. Unlike the LLVM optimizer, the Swift pass manager does not schedule analysis or optimization passes. The pass manager simply runs optimization passes on the functions in the module. The order of the optimizations is statically defined in the file "Passes.cpp".
TODO: The design that's described in the paragraph below is still under development.
The pass manager scans the module and creates a list of functions that are organized at a bottom-up order. This means that the optimizer first optimizes callees, and later optimizes the callers. This means that when optimizing some caller function, the optimizer had already optimized all of its callees and the optimizer can inspect the callee for side effects and inline it into the caller.
The pass manager is also responsible for the registry and invalidation of analysis. We discuss this topic at length below. The pass manager provides debug and logging utilities, such as the ability to print the content of the module after specific optimizations and to measure how much time is spent in each pass.
There are two kind of optimization passes in Swift: Function passes, and Module passes. Function passes can inspect the entire module but can only modify a single function. Function passes can't control the order in which functions in the module are being processed - this is the job of the Pass Manager. Most optimizations are function passes. Optimizations such as LICM and CSE are function passes because they only modify a single function. Function passes are free to analyze other functions in the program.
Module passes can scan, view and transform the entire module. Optimizations that create new functions or that require a specific processing order needs to be module optimizations. The Generic Specializer pass is a module pass because it needs to perform a top-down scan of the module in order to propagate type information down the call graph.
This is the structure of a simple function pass:
class CSE : public SILFunctionTransform {
void run() override {
// .. do stuff ..
}
StringRef getName() override {
return "CSE";
}
};
Swift Analysis are very different from LLVM analysis. Swift analysis are simply a cache behind some utility that performs computation. For example, the dominators analysis is a cache that saves the result of the utility that computes the dominator tree of function.
Optimization passes can ask the pass manager for a specific analysis by name. The pass manager will return a pointer to the analysis, and optimization passes can query the analysis.
The code below requests access to the Dominance analysis.
DominanceAnalysis* DA = getAnalysis<DominanceAnalysis>();
Passes that transform the IR are required to invalidate the analysis. However, optimization passes are not required to know about all the existing analysis. The mechanism that swift uses to invalidate analysis is broadcast-invalidation. Passes ask the pass manager to invalidate specific traits. For example, a pass like simplify-cfg will ask the pass manager to announce that it modified some branches in the code. The pass manager will send a message to all of the available analysis that says "please invalidate yourself if you care about branches for function F". The dominator tree would then invalidate the dominator tree for function F because it knows that changes to branches can mean that the dominator tree was modified.
The code below invalidates sends a message to all of the analysis saying that some instructions (that are not branches or calls) were modified in the function that the current function pass is processing.
if (Changed) {
invalidateAnalysis(InvalidationKind::Instructions);
}
The code below is a part of an analysis that responds to invalidation messages. The analysis checks if any calls in the program were modified and invalidates the cache for the function that was modified.
virtual void invalidate(SILFunction *F,
InvalidationKind K) override {
if (K & InvalidationKind::Calls) {
Storage[F].clear();
}
}
The invalidation traits that passes can invalidate are:
- Instructions - some instructions were added, deleted or moved.
- Calls - some call sites were added or deleted.
- Branches - branches in the code were added, deleted or modified.
- Functions - Some functions were added or deleted.
The Swift optimizer has optimization passes that target specific data structures in the Swift standard library. For example, one optimization can remove the Array copy-on-write uniqueness checks and hoist them out of loops. Another optimization can remove array access bounds checks.
The Swift optimizer can detect code in the standard library if it is marked with special attributes @_semantics, that identifies the functions.
This is an example of the @_semantics attribute as used by Swift Array:
@public @_semantics("array.count")
func getCount() -> Int {
return _buffer.count
}
Notice that as soon as we inline functions that have the @_semantics attribute the attribute is lost and the optimizer can't analyze the content of the function. For example, the optimizer can identify the array 'count' method (that returns the size of the array) and can hoist this method out of loops. However, as soon as this method is inlined, the code looks to the optimizer like a memory read from an undetermined memory location, and the optimizer can't optimize the code anymore. In order to work around this problem we prevent the inlining of functions with the @_semantics attribute until after all of the data-structure specific optimizations are done. Unfortunately, this lengthens our optimization pipeline.
Please refer to the document "High-Level SIL Optimizations" for more details.
Swift Passes and Analysis often keep instruction pointers in internal data structures such as Map or Set. A good example of such data structure is a list of visited instructions, or a map between a SILValue and the memory aliasing effects of the value.
Passes and utilities delete instructions in many different places in the optimizer. When instructions are deleted pointers that are saved inside maps in the different data structures become invalid. These pointers point to deallocated memory locations. In some cases malloc allocates new instructions with the same address as the freed instruction. Instruction reallocation bugs are often difficult to detect because hash maps return values that are logically incorrect.
LLVM handles this problem by keeping ValueHandles, which are a kind of smart pointers that handle instruction deletion and replaceAllUsesWith events. ValueHandles are special uses of LLVM values. One problem with this approach is that value handles require additional memory per-value and require doing extra work when working with values.
The Swift optimizer approach is to let the Context (currently a part of the SILModule) handle the invalidation of instructions. When instructions are deleted the context notifies a list of listeners. The invalidation mechanism is relatively efficient and incurs a cost only when instructions are deleted. Every time an instruction is deleted the context notifies all of the listeners that requested to be notified. A typical notifications list is very short and is made of the registered Analysis and the currently executed Pass.
Passes and Analysis are registered by the PassManager to receive instruction deletion notifications. Passes and Analysis simply need to implement the following virtual method:
virtual void handleNotification(swift::ValueBase *Value) override {
llvm::errs()<<"SILCombine Deleting: " << Value<<"\n";
}
TODO.
TODO.
The updated list of passes is available in the file "Passes.def".