Leaving a placeholder here. When I have time, I will organize what I learned while completing RCompiler and studying compiler principles. Since I also selected Advanced Compiler next semester, I can add backend and optimization content later.

Parser & Semantic Check

Since this seems to be the first year we hand-wrote the parser, I should write a bit more. The parser itself is not hard. What really causes rework is this: at first you think “as long as I can parse an AST, it is fine.” Later, when doing semantic check and IR generation, you discover that the AST does not carry enough information, so you go back and add types, lvalue/rvalue information, spans, and various semantic markers to the nodes.

Expression

The main parser problem is building the AST for expression. I recommend reading Pratt Parser, whose pseudocode and principles are very clear. The biggest difficulty in expression parsing is precedence and associativity. If you write it layer by layer according to the grammar, the code becomes a long chain like parseLogicalOr -> parseLogicalAnd -> parseEquality -> .... It works, but it is verbose.

The idea of Pratt Parser is to bind different precedence levels to different operators, then use a unified parseExpr(minBp) to handle everything. The rough flow is:

  • First parse a prefix expression, such as a literal, variable, parenthesized expression, unary operation, array or struct literal, and so on.
  • Then loop and check whether an infix or postfix operator follows.
  • If the following operator has lower precedence than the current minBp, the current expression should end.
  • Otherwise, consume the operator, recursively parse the right operand, and combine the left and right sides into a new AST node.

I also recommend handling postfix expressions here in a unified way, such as function calls f(x), array indexing a[i], field access x.y, and method calls x.f(). They usually have the highest precedence and can appear continuously:

1
a.b(c)[i].d

If this kind of expression is not handled uniformly, the AST hierarchy is easy to assemble incorrectly. I recommend treating “primary + postfix chain” as part of prefix parsing: first obtain the leftmost primary, then keep consuming postfix operators until the next token is no longer postfix.

Semantic Check

Through mysterious operations, I successfully implemented semantic check in two passes. As a result, I finished semantic check much faster than others. This gave me a happy break, and I went straight to Hong Kong for four days, thinking my compiler was safe. This also planted the seeds for a series of later dangerous situations caused by starting IR too late.

The dangerous situation:

When writing IR, I discovered that I had completely forgotten to maintain lvalue/rvalue information, so I had to rebuild part of the logic. Therefore, do not blindly pursue fewer passes. Honestly scanning four or five passes according to requirements is often more stable. First collect global symbols, then handle types and function signatures, then check statements and expressions, and finally add constant evaluation and extra constraints. Each pass becomes clearer.

Another semantic-check lesson is that the scope stack must be clean. Entering a block pushes a scope, leaving a block pops a scope. Function parameters and local variables are inserted at different levels. break/continue need to know whether the current context is inside a loop. return needs to know the current function’s return type. Putting all this context into a SemanticContext is much more comfortable than passing scattered parameters everywhere.

IR Generation

IR generation is almost the same as building the AST in the parser: write it recursively. It is relatively easy, and there are many debugging tricks. I finished debugging it in 24 hours. But because my initial design had problems, I went through a major code refactor. On top of that, I got sick at the end of last year, which made writing code very painful and left quite a psychological shadow. Still, I have to say that my IR builder design is clean and beautiful, and I am quite proud of it.

Codegen

Implementation: do no register allocation. Spill everything to the stack. Whenever an operation needs a variable, load it from the stack into a register, operate on it, then store it back. This creates a large number of load and store instructions, and performance is poor.

Some possible pitfalls: the number of registers that can hold function arguments is limited, only eight registers a0-a7; when there are more than eight parameters, they need to be spilled to the stack. Pay attention to sign extension for m-extension instructions. Pay attention to load/store operations when dereferencing pointers. The reimu simulator’s default stack memory is 32K, and many tests require manually increasing the stack size. I tested that 4096K is about enough. When the function return value is an array or struct, the final return value needs to be written into register a0. Phi instructions do not exist in ASM and must be manually lowered. A simple idea is: every time an IR Br instruction is processed, look ahead to see whether the target block contains phi instructions. If so, first spill the phi result to the stack, because ASM cannot record which block you jumped from.

Register Allocation

I first wrote, with some borrowed mysterious power, a linear-scan register allocation algorithm. But the day after finishing and debugging it, I learned at the Advanced Compiler meeting that we needed to write graph coloring, so I was forced to write graph-coloring register allocation again.

Linear Scan

Linear-scan register allocation is relatively easy to understand. First, I reused part of the codegen code. The modification was that in codegen, all temporaries were stored on the stack and accessed through load/store, while in reg alloc, I first assigned all these temporaries virtual registers so that later register allocation could be performed. The core of linear-scan allocation is constructing the CFG and computing live intervals. Every ASM block obtained from codegen corresponds to a CFG block, which stores the first and last instruction numbers of the block, def/use variable sets, liveIn/liveOut sets, and related information. First we construct a CFG by finding successor blocks through intra-block jump instructions. After obtaining the CFG, we can compute liveIn/liveOut for each block. This is a mapping from virtual registers to live intervals, and we have:

1
2
liveIn[B] = use[B] U (liveOut[B] - def[B])
liveOut[B] = U liveIn[S] for all S in succ[B]

Perform backward iteration until liveIn/liveOut no longer changes.

Next we compute the live interval for each virtual register. A live interval is a range indicating where a register is defined and where it is last used in the program. The method is to traverse every block in the CFG and every instruction in each block, updating the corresponding register’s live interval. Finally, we obtain the live interval for each virtual register and can use it for linear-scan allocation. The core idea is to sort virtual registers by the start position of their live intervals, then scan these intervals from left to right and try to assign them to physical registers. If the current live interval overlaps with an already assigned interval, then one of them needs to be spilled to memory.

It is worth noting that we need to consider cross-call situations. In the RISC-V architecture, registers are divided into caller-saved and callee-saved. Caller-saved registers need to be saved and restored around function calls, while callee-saved registers are preserved by the callee. Therefore, during register allocation, we must ensure that live intervals crossing calls are not assigned to caller-saved registers, otherwise they need to be spilled to memory. Before entering each function, we need to save the values of callee-saved registers on the stack and restore them when the function returns.

Graph Coloring

TBD. Honestly, I think the graph-coloring explanation in the Mx Tutorial is already very clear, and I am not even sure I want to write it. Anyway, later.

IR Generation Optimization

Mem2Reg

The essence of mem2reg is an alloca removal optimization. The idea is to move objects originally allocated on the stack into virtual registers. I first spent one evening quickly writing three most basic mem2reg optimizations:

  • If an alloca is never used, do not allocate it. This had no effect.
  • If it is defined only once, all values can be replaced by the defined value. This had a clear effect.
  • If an alloca is only used in the current block, all uses can be replaced by the nearest preceding def. The effect was weak, probably because few variables appear only within one block.

Next I mainly analyze the fourth mem2reg optimization: if an alloca is only loaded and stored, we can insert phi instructions at dominance frontiers and replace all uses with corresponding phi results. In fact, when thinking about the third mem2reg optimization, I had already vaguely thought about generalizing def/use handling across blocks. Using phi is indeed one way.

Building the Dominator Tree and Dominance Frontier

A dominator set can be understood like this: to reach a certain block, there are blocks that must be passed through. These blocks form a chain, and then the dominator tree can be constructed. The construction method is to first build the CFG and obtain predecessor/successor relations, then find the LCA for all predecessor blocks. Next we need to find dominance frontiers. First clarify the definition of dominance frontier: a node X is in the dominance frontier of node Y if and only if Y is in the dominator set of one predecessor of X, but Y is not in the dominator set of X. The calculation method is to traverse predecessor blocks. If a predecessor block naturally has the current block as its dominance frontier, usually when there are more than two predecessors, then go upward to the previous dominator block of the predecessor and recurse until it is also in the current block’s dominator set.

Phi Insertion and Instruction Deletion

The phi insertion method is: for each alloca, find all def blocks, traverse the dominance frontiers of those def blocks, insert a phi instruction at the beginning of each dominance-frontier block, rename the value defined by the phi instruction at the entry top to the value defined by the alloca, and then recursively add phi instructions to the dominance frontier of the dominance frontier. Then maintain a stack for each allocated value. Whenever a store instruction or newly inserted phi instruction is encountered, push the corresponding value onto the stack. Whenever a load instruction is encountered, replace the load result with the stack top, similar to the first three optimizations through a replaceMap. At the same time, update the parameters of phi instructions using the current stack top. Finally, recursively process the child nodes of the current basic block in the dominator tree.

Eliminating Phi Instructions in Codegen

Phi instructions are not part of the RISC-V instruction set, so they need to be eliminated during codegen. In fact, before writing mem2reg, I had already implemented one version of phi elimination: insert a copy, a new virtual register, in each predecessor block, and add mv dst tmp at the end. This is a very simple idea. Since virtual registers are used for storage, there are no data-conflict problems, and it passed the tests smoothly. Looking back afterward, this implementation has performance drawbacks:

  • It increases the number of virtual registers and puts pressure on regalloc.
  • It creates more dead code.

The more standard solution should be critical-edge splitting. The idea is to add a block on the critical edge and first copy the value that should be passed to the downstream block into that block. But here comes the twist: after implementing it, I tested and found no difference from my original implementation. Yes, not a single test case showed any performance difference. After thinking about it carefully, I found that the two implementations seem essentially equivalent. There is not much more to say. I recommend using my first implementation because it is much easier to implement and understand.

Dead Code Elimination

Starting from dead code elimination, we enter parts not covered by the ancient Mx Tutorial.

The purpose of DCE is to delete instructions that compute a value which will not affect the observable result of the program. For example:

1
2
b = 114514
c = b + 1

If the value of c is never used later in the program, then c = b + 1 is dead code and can be removed.

If you have already implemented linear-scan regalloc, congratulations: the remaining code for DCE is no more than 30 lines. In each block, maintain a liveSet, initialized as the liveOut set. Traverse instructions in reverse order. If an instruction’s def variable is not in liveSet, the instruction is dead code and can be deleted. If the instruction is not dead, add its used variables into liveSet and remove its defined variable from liveSet. Repeat multiple passes until no code is deleted.

Constant Propagation

Constant propagation is one of the easiest optimizations to think of and one of the easiest to write a first version for. The simplest version maintains a valueMap. If a variable is known to be a constant, then later uses of that variable are directly replaced by the constant. For example:

1
2
a = 1
b = a + 2

This can directly become b = 3. But this version is only suitable for local optimization inside one basic block. Once branches, loops, and phi nodes appear, things become complicated.

A more complete method is SCCP (Sparse Conditional Constant Propagation), which performs both constant propagation and unreachable-branch removal. The core idea is to maintain a three-state lattice for every SSA value:

  • Unknown: we do not know what the value is yet.
  • Constant: the value is known to be a certain constant.
  • Overdefined: the value is not a constant, or cannot be safely determined.

The biggest difference between SCCP and ordinary constant propagation is that it propagates only along executable edges. That is, if a branch condition can already be folded into a constant, the other edge that will never be taken should not continue participating in later phi computation. This detail is very important. Otherwise, values from unreachable blocks will pollute phi nodes and turn values that could have been folded into Overdefined.

For example:

1
2
3
4
5
if (x == 0) {
    y = 1
} else {
    y = 2
}

If we already know x = 0, then only the true edge is executable. The phi only needs to consider the y = 1 side, and finally y can continue to propagate as a constant. This optimization usually needs to run together with CFGClean and DCE: SCCP folds branches, CFGClean removes unreachable blocks and cleans phi nodes, and DCE deletes the remaining useless computations.

Besides SCCP, we can also implement a more local ConstantFold, specifically folding binary operations, casts, constant getptr, and constant branches. This kind of pass has low implementation cost but stable benefits. Especially after inline or memory forwarding, many new constant expressions often suddenly appear, so the pipeline usually runs several rounds repeatedly.

SROA

SROA (Scalar Replacement of Aggregates) can be understood as “splitting small aggregate objects into scalars.” For example, if a local struct has only a few fields and all accesses are constant field accesses, then instead of maintaining the entire struct in memory, we can split it into several independent allocas:

1
2
3
struct Pair { x, y }
p.x = a
p.y = b

This can be approximately viewed as:

1
2
p_x = a
p_y = b

After splitting, each field can continue to be promoted into SSA values by mem2reg, and later SCCP, CSE, and DCE can also work more effectively. This optimization is useful for small structs, fixed-length small arrays, and temporary aggregate objects inside helper functions.

However, SROA boundaries must be conservative. My understanding is that the first version should only handle local alloca, with a small number of fields or elements, field types limited to integers or pointers, no address escape, and all access paths being constant fields or constant indices. If there is dynamic indexing, passing the aggregate object’s address to a function, or complex memcpy/memset, it is better to skip it first. The biggest danger in optimization is something that “looks splittable” but accidentally breaks aliasing and causes WA.

Function Inline

The benefit of function inlining is intuitive: it saves call/return and parameter movement, while exposing computations inside the callee to the caller so later optimizations can continue. For example, many modular-arithmetic wrappers, getters/setters, and small arithmetic helpers look like a pile of function calls to the backend if not inlined. After inlining, SCCP, ConstantFold, and MemoryForward may further flatten the code inside.

But more inlining is not always better. Excessive inlining increases function-body size, lengthens live ranges, raises backend register pressure, and may ultimately be offset by many spills. A safer strategy is:

  • Do not inline main.
  • Do not inline recursive functions.
  • Prefer inlining single-call functions, small functions, and pure arithmetic helpers.
  • Penalize functions with many parameters, complex aggregate returns, or many basic blocks.
  • Control the caller’s code-growth budget.

After inlining, it is best to run SCCP and CFG cleanup again. The reason is simple: inlining often brings constants from actual parameters into the function body and exposes branches and store-load chains that were previously invisible across functions.

Memory Forwarding

The goal of Memory Forwarding is to reduce unnecessary loads and stores. The most typical case is:

1
2
store v, p
x = load p

If there is no operation in between that may modify the memory pointed to by p, then x can be directly replaced by v. Furthermore, if a load has already read the same exact address and there is no write in between, the previous load result can be reused.

The key to this pass is “exact address” and “conservative aliasing.” A relatively safe method is to maintain a memory state along the dominator tree and forward only when the same address is confirmed. For struct fields, the address can be normalized into a key like base + field path: the same root object with different constant fields can usually be considered non-aliasing. But when encountering dynamic array indices, function calls, unknown stores, or memcpy/memset, related state should be cleared or discarded.

Memory Forwarding also pairs well with ConstantFold. Many times, a load is replaced by a literal, and a constant branch can immediately be folded afterward. A store overwritten by a later store with no read in between can also be deleted. This optimization is useful for repeated reads and writes of struct fields, interpreter state variables, and repeated loads in arrays or object pools.

Local CSE / Dominator GVN

CSE (Common Subexpression Elimination) handles repeated expressions, for example:

1
2
t1 = a + b
t2 = a + b

The second a + b can directly reuse t1. If this is done only inside one basic block, it is Local CSE. If an expression table is maintained downward along the dominator tree, it becomes a simplified Dominator GVN.

During implementation, pure expressions can be assigned a key such as op + lhs + rhs + type + flags. For commutative operations such as addition and multiplication, operands can be normalized to avoid treating a + b and b + a as two different expressions. Besides binary operations, pure casts such as getptr, sext/zext/trunc are also suitable for CSE.

One easy pitfall is that the key must include semantic flags and type information, such as whether the operation is unsigned, whether it is i8, whether it preserves 64-bit semantics, and so on. Otherwise two expressions that look identical by operands may actually mean different things. Load CSE must also be very conservative, and it is usually better handled uniformly by MemoryForward.

CSE is helpful for array address computation. Many IRs repeatedly generate the same getptr chain. After CSE, not only are repeated computations reduced, but MemoryForward can more easily recognize “this is the same address.”

LICM

LICM (Loop Invariant Code Motion) moves loop invariants out of loops. For example:

1
2
3
4
while (...) {
    t = n * 8
    a[i] = base[t + i]
}

If n does not change inside the loop, then t = n * 8 does not need to be recomputed every iteration.

Implementation-wise, first identify natural loops through back edges, then find the loop preheader and move safe loop invariants into the preheader. To judge whether an instruction can be hoisted, roughly check two conditions:

  • The instruction itself has no side effects.
  • All its operands are defined outside the loop, or come from loop invariants that have already been hoisted.

Good candidates include expensive scalar binary operations such as mul/div/mod/shift, pure getptr, casts, and add/sub used in address chains. But do not hoist loads lightly unless you have sufficiently strong alias analysis proving that the memory will not be modified inside the loop.

LICM is also not something that should be as aggressive as possible. Moving cheap computations outside a loop may lengthen live ranges, increase register pressure, and cause more backend spills. This is especially true for interpreters and hash pipelines where many values are live. Excessive hoisting can become a negative optimization. A conservative strategy is: hoist expensive operations, hoist cheap add/sub related to address chains, and avoid moving other cheap binary operations casually.

Strength Reduction

Strength Reduction mainly replaces expensive operations with cheaper forms. The most common cases are:

1
2
3
x * 2^k  ->  x << k
x / 2^k  ->  x >> k
x % 2^k  ->  x & (2^k - 1)

But pay attention to signed and unsigned semantics. Division and modulo especially cannot be casually replaced in signed cases. Unsigned power-of-two transformations are much safer. Also, in RV64GC, mul itself is one instruction, so expanding x * (2^k +/- 1) into slli + add/sub may not be faster and may even increase temporary registers and spills. Keeping only the most clearly safe power-of-two transformations is enough.

Backend Optimization

After IR-level optimization, a large part of the remaining performance gap is in the backend: register-allocation quality, spill/reload count, function-call overhead, stack-frame maintenance, and some assembly-level peephole optimizations.

Peephole

Peephole optimization is suitable for small local patterns whose correctness is clear. For example:

  • Delete mv x, x.
  • Delete addi x, x, 0.
  • Delete fallthrough j instructions that jump to the next block.
  • Fold seqz/snez/slt/slti + bnez into direct conditional branches.
  • Fold a one-time address temporary into load/store: addi addr, base, off; ld x, 0(addr) becomes ld x, off(base).

Each optimization looks tiny on its own, but they reduce short-lived temporaries and lower later register-allocation pressure. For modular-arithmetic hotspots, small helpers such as add_mod/sub_mod/norm can also be recognized and expanded directly at the call site, saving function-call and parameter-movement overhead.

Improving Linear Scan

The basic linear-scan method was described earlier. In the backend optimization stage, the main task is continuing to reduce spills. The biggest problem with naive linear scan is that it easily treats the lifetime of a virtual register as one large interval from first definition to last use, failing to exploit live holes in between. Although full live-range splitting is somewhat troublesome to implement, there are still several cost-effective improvements:

  • Use CFG-based liveIn/liveOut instead of only linear text order.
  • Weight loop blocks so uses inside loops have higher spill cost.
  • For intervals crossing calls, try callee-saved registers first.
  • For calls, count only the actually used a0-a7 argument registers as uses.
  • Collect copy hints from mv v1, v2 and try to assign non-conflicting copy endpoints to the same physical register.
  • Rematerialize single-definition li constants when needed instead of occupying a spill slot.

The core judgment is: many hidden performance points are not because the IR is still too large, but because too many ld/sd instructions are inserted into hot loops. Reducing spill traffic is usually more effective than continuing to stack IR passes.

Stack Frame and ABI

Stack-frame optimization is also very practical. For example, leaf functions do not need to save/restore ra. If a leaf function has no call, no alloca, no spill, and does not use callee-saved registers, frame setup can be omitted entirely. Callee-saved registers only need to save the ones actually used. Do not mechanically save a pile of registers in every function.

Also, RISC-V load/store immediate offsets are only 12-bit. With large frames, accessing stack slots becomes a longer sequence such as li + add + ld/sd, so in large-frame scenarios, repeated materialization of frame addresses needs special attention. If the same large-offset address appears repeatedly in a basic block, the already computed frame address can be reused.

Post-regalloc Spill Cleanup

After register allocation, another local cleanup pass can be run specifically to handle redundant stack accesses produced by spill/reload. For example:

  • After ld slot, another repeated ld slot appears with no write to that slot in between. Reuse the previous result directly.
  • Delete sd same-value slot.
  • If store a, slot; store b, slot appears with no load in between, delete the earlier store.
  • Under large frames, repeated li off; add addr, off, s0 can be replaced with mv from an existing address register.

This pass already has benefits even if it only works within a basic block. Cross-block cleanup is of course stronger, but correctness pressure increases significantly. Overall, the backend optimization principle remains conservative: first remove obvious redundant spill/reload, then consider more complex live-range splitting, copy coalescing, and block-layout adjustment.

Conclusion

From 2025.8 to 2026.7, RxCompiler went through a full year. It is hard to say whether my attitude toward it is good or bad, because it truly placed a huge burden on an already high-pressure first semester of sophomore year. At the same time, it may also have been the last time in my life that I felt the pleasure of such a large engineering project. From hand-writing the frontend plus codegen and register allocation, to handing optimization to coding agents, this year also let me witness the whole process of coding agents transforming from Copilot-like useless tools into Codex/CC-like agents with both powerful harnesses and powerful models. I do not like compilers or traditional systems themselves, but I am happy that through compilers, I indirectly found some other things I am interested in and am now working toward them.

You still have a long way to go, but I hope you can enjoy the process and keep learning.