Vibing with Compilers: Part 2
It has been a while since I wrote about my C Compiler in Rust project. That initial blog post was mostly a non-technical heuristic for my vibe-coding methodology, which always has to adapt to new models. It was written out of satisfaction with having easily produced copious amounts of software that passed a rather strict test suite.
However, it turns out that actually understanding the internals of compilers is an incredibly useful skill. But acquiring the skill is quite difficult when I open the ultra-long LLVM Language Reference Manual and get dizzy scrolling between various sections. So this blog post will be an easy-to-process deep dive into my C compiler, with a focus on the optimizer.
High-Level Overview
The compiler contains a lexer, a parser, a semantic analyzer, an IR lowerer, an optimizer, and a code generator. It runs after the GCC preprocessor and before the GCC assembler & linker. The overall process turns C files into executable binaries.
The lexer turns the source code into a vector of tokens, where each token is an atomic element of the language, such as for or +.
The parser turns the token stream into an Abstract Syntax Tree (AST), verifying the syntactic correctness of the program and producing a hierarchy that is easier for later semantic analysis passes to process.
The semantic analyzer is a pass over the AST to verify semantic correctness, such as scoping and checking.
The IR lowerer transforms the AST into an Intermediate Representation, hence the name. LLVM IR is one of the most widely used compiler IRs in practice, and it combines both lower-level operations, data types, and higher-level control-flow semantics, making it a perfect platform for optimization before turning the program into assembly.
The optimizer rewrites the IR so that the downstream assembly uses the underlying processor hardware more efficiently, producing a higher-performance program.
The code generator turns the generic operations in the IR and turns them into instructions specific to the target backend, in my case, x86. It also has to allocate registers for variables, as registers are faster than RAM, which it does with a graph coloring algorithm.
IR Features
Since my compiler project had a custom IR designed from scratch, many of the fundamental backend support foundations came about from expanding the IR. Naturally, vibe-coding all of it made the LLM reach into its training corpus, which most likely just involved reimplementing a form of LLVM IR in Rust.
One of the most fundamental concepts of LLVM IR is that it uses Static Single Assignment (SSA) form, where each variable/register can be assigned exactly once. This pattern makes it easy to trace data dependencies and helps to simplify the optimizer. However, if the assignment is conditional, LLVM has an instruction called phi, named after the SSA -function, which merges values coming from different control-flow paths. The gist is that the instruction is a node in a control flow graph that branches out into separate execution contexts for the condition and converges back to the caller once complete.
What about pointers? One LLVM IR instruction that returns a pointer is alloca, which allocates memory on the stack. To retrieve the data stored at that address, one has to use the load instruction.
To index into subobjects from a pointer, the instruction commonly used is getelementptr, also known as GEP. Similar to alloca, the "dereferencing" occurs using the load instruction from the address.
Autovectorization Pipeline
Downstream from the IR lowering, there are many optimization passes to make the code more efficient on the backend, but the one which I find the most interesting is auto-vectorization.
In a nutshell, each CPU core has a vector execution hardware unit, which enables data parallelism, a.k.a. SIMD. Running on these units requires special assembly instructions. Since data parallelism can be a huge speed boost, it is very convenient and cool to have a compiler that is "smart enough" to take a program and generate data parallel SIMD assembly while the user writes generic code.
Pre-Vectorization Passes
The optimizer in my compiler first runs the mem2reg, LICM, loop interchange, and prefetch passes on the IR, which respectively promote eligible stack allocations into SSA registers, hoist loop invariant instructions out of the loop, and add prefetch hints to hide memory latency.
Loop Extraction and Analysis
The optimizer then searches the control flow graph for loops and extracts their induction variables, i.e., the variables that are incremented or decremented each iteration
From the loop attributes, the optimizer validates attributes required for SIMD compatibility, such as memory access patterns, loop trip count and bounds (which must be analyzable for vectorization), and result output safety.
Another type of check that is needed is memory dependence. Some examples of that include ensuring no inter-iteration memory dependence (requiring sequential execution), memory read/write hazards, or pointer aliasing (i.e. overlapping/interfering operations).
IR Transformation
At the end of various analysis passes, the optimizer transforms the IR for loops into vector instructions, restructuring the control flow while also navigating around numerous iteration and operation type edge cases.
As an example, for the simple loop below:
for (i = 0; i < 10; i++)
a[i] = b[i];
Here is what IR would pseudo-look like before applying vectorization.
preheader:
br loop_header
loop_header:
%i = phi [0, preheader], [%i_next, loop_latch]
%cmp = %i < 10
br %cmp, loop_body, exit
loop_latch:
%i_next = %i + 1
br loop_header
loop_body:
%gep_b = gep %b, %i
%gep_a = gep %a, %i
%vb = load %gep_b
store %vb, %gep_a
br loop_latch
And here is what it would look like after vectorization:
preheader:
br vec_header
vec_header:
%vi = phi [0, preheader], [%vi_next, vec_body]
br %vi < 8, vec_body, tail_block
vec_body:
%gep_b = gep %b, %vi
%gep_a = gep %a, %vi
%vb = simd.load %gep_b, width=4
simd.store %gep_a, %vb, width=4
%vi_next = %vi + 4
br vec_header
tail_block:
%mask = simd.lanemask %vi, 10
%gep_b = gep %b, %vi
%gep_a = gep %a, %vi
%vb = simd.load %gep_b, width=4
%vb_m = simd.and %vb, %mask // masked tail!
%old = simd.load %gep_a, width=4
%out = simd.blend %old, %vb_m, %mask
simd.store %gep_a, %out, width=4
br exit
The vectorizer also applies a related optimization pass called SLP vectorization. Same concept, but doesn't restrict to loops. For example, four independent add operations in a function can be bundled together for SIMD parallel computation.
After a cleanup of the IR control-flow graph, the codegen module of the compiler maps the SIMD instructions to the hardware backend. Some generations of x86 processors only have SSE vector units; newer ones have wider AVX/AVX2 as well, which have different instruction sets.
Polyedral Optimization
A theme that extends basic auto-vectorization is polyhedral optimization. It represents loop iterations and memory dependences as systems of linear constraints, then reorders instruction execution to optimize for locality, parallelism, vectorization, pipelining, or other performance objectives.
It is also an area where popular mathematical optimization algorithms can be applied, such as integer linear programming.
Conclusion
Unfortunately, about 2 months ago, Copilot pulled the plug on Sonnet and Opus models for the free student edition. While the demand for tokens to support further development of the project is growing exponentially, my financial means do not yet support an infinite token budget. So, while I will not be able to extend my C Compiler in Rust very much, I will definitely be extending my understanding of compilers.
At a high level, after diving into the parts of the auto-vectorization optimization passes, I now understand the integral role of compilers in the evolution of domain-specific chip architectures. In the future, I will continue to explore other related areas.