새 컴파일러가 AST, HIR 및 TIR로 분할되는 이유 (및 콘텐츠별 캐시)

Compiler beginners easily imagine compilation as a straight line: read source, parse, generate machine code. In real engineering, that line is split into several intermediate representations (IRs), where each layer does one set of jobs and layers are joined by lowering. Why go through all this trouble? Because a single representation always hits a conflict between expressiveness and information at some stage: too close to source and it is hard to optimize, too close to machine code and it is hard to analyze. This post uses YQ, an unreleased LLVM-based systems language we are developing, to explain what the AST, HIR, and TIR layers each do, why their order cannot be shuffled, and how a content-addressed cache keeps a multi-layer pipeline from becoming too slow to use.

Three kinds of questions one compilation answers

Splitting “turn YQ source into an executable” apart, a compiler is really answering three different kinds of questions in sequence:

1. What does this text mean (syntax layer): what does the tree of a + b * c look like?
2. Are these names and types right (semantic layer): is b an f32 or a user-defined type? Does + have a matching implementation?
3. How does this logic land on the machine (code generation layer): is addition an add instruction or a function call? How is a struct laid out in memory?

If one AST alone ran the whole way, the first kind of question would be easy to answer and the third would be very hard, because the AST is full of syntactic sugar (if, pattern matching, operators, indentation blocks) and the optimizer would have to guess semantics every time. The industry-standard approach is therefore to let representations “desugar” layer by layer: the AST keeps the full syntactic shape of the source, and the further down the IR you go, the closer you get to a plain instruction-level form, until you reach LLVM IR, a representation that is optimizable and can generate code for many backends.

YQ’s pipeline is designed as:

YQ source
  |  lexing/parsing (Unicode identifiers, indentation-aware, error recovery)
  v
Token -> AST (carries Spans: every node remembers its start/end location in source)
  |  semantic analysis: scope resolution, desugaring
  v
HIR (high-level IR: explicit control flow and calls, syntactic sugar flattened)
  |  type checking (HM inference + trait solving) + ownership/borrow checking
  v
TIR (typed IR: every node carries a concrete type)
  |  generic specialization (monomorphization) + lowering to LLVM IR
  v
LLVM IR -> object files

Enter fullscreen mode Exit fullscreen mode

AST: faithfully preserving syntax, Span is its soul

The AST’s job is not to be “convenient”, but to be “complete”. The parser (ours is a hand-written recursive descent one) turns source into a tree where every node hangs on a Span, the start/end line and column range of that node in the source file. A Span looks like a tiny structure, but it is the foundation of all diagnostics quality downstream:

• when types mismatch, the error can point precisely at the offending subexpression instead of the whole function;

• editor features like hover, go-to-definition, and completion are, at bottom, “map a cursor position onto an AST node”;

• if an error message wants to show a source snippet with terminal coloring, the only reliable source of that is the correspondence between Spans and source text.

This is also why even adding one field at the AST stage deserves caution: its structure flows through HIR and TIR and affects diagnostics and tooling all the way down. Many new language projects rush with a minimal AST to get something running, and later find that retrofitting the diagnostics experience means almost rewriting the front end. That bill is not worth it.

HIR: flattening “code written by humans” into “code a compiler can handle”

HIR exists to remove syntactic sugar and implicit behavior. Code written by humans is full of conveniences: if is an expression, operators call trait methods, pattern matching hides a chain of branch decisions, and indentation blocks must become explicit scopes. These are friendly to readers, but not to analyzers. The HIR stage does a few typical things:

• scope and name resolution: resolve names like x and foo to definite definitions, producing binding relations for every symbol, preparing for type checking;

• explicitness: expand syntactic sugar into plainer structures so later stages only face a few node shapes;

• keeping what type checking needs: HIR nodes still have no types, but the call structure they record must be clean enough for the type checker to walk smoothly.

A common design question is whether HIR should keep Spans. The answer is almost always yes. Diagnostics at ever later stages need to point back at source, and since HIR has already flattened syntactic sugar, dropping position information here means errors would point at “desugared intermediate nodes” that users cannot understand at all.

TIR: the “final draft” after type and ownership checking

Once type checking (HM-style inference plus trait constraint solving) and ownership checking finish, the compiler has enough information to pin every expression to a concrete type. That representation is TIR. Compared with HIR, the key increment of TIR is that every node carries a definite type, which makes it safe to do:

• generic specialization: add 1 2 and add 1.5 2.5 are the same function node in HIR; in TIR the instantiation information is clear, so a dedicated copy can be cloned for (i32, i32) and for (f32, f32) and handed to LLVM for optimization;

• memory layout decisions: struct field offsets and enum discriminant layouts can only really be computed once types are known;

• ownership-related move/borrow decisions: where a value moves and where it drops needs type information combined with region inference.

Doing specialization at the TIR level instead of the LLVM level is so that “clone code by type” happens on our own IR. On our own IR we can freely copy, rename, and instrument nodes, while the LLVM layer is better at scalar optimization and instruction selection. The two jobs do not overlap.

Why hook up to LLVM instead of writing a whole back end

Everything up to TIR is language-specific. The work after that, instruction selection, register allocation, optimization, and object file generation, is highly generic and an enormous amount of engineering. Calling into LLVM is what most new languages choose, and YQ does too: at the code generation layer, TIR is lowered to LLVM IR through LLVM’s C API bindings, and LLVM produces object files. The benefit is getting an industrial-grade optimizer and multi-backend support for free (x86_64, WASM, and even GPU/TPU directions all build on the LLVM ecosystem). The cost is that you have to describe your language in LLVM’s world view: you are responsible for struct layout decisions, calling conventions, and translating YQ’s error handling model into control flow that LLVM can express.

The cost of a multi-layer pipeline: slowness, and how a cache covers it

The most direct cost of multiple IR layers is slower compilation: every layer walks the whole tree once, and every lowering allocates again. Early new-language projects usually do not care, but once the compiler starts compiling itself (bootstrapping) and the test suite grows into the hundreds, slowness becomes a development-efficiency problem. Our approach is a content-addressed compilation cache: cache intermediate artifacts per file rather than per whole project.

In the compile cache directory, each compilation unit leaves a group of files like this:

1423ba0b-e3b0c442.meta     # metadata
1423ba0b-e3b0c442.bin      # intermediate artifact
1423ba0b-e3b0c442.o        # object file

Enter fullscreen mode Exit fullscreen mode

The .meta content is roughly:

v=1
source_hash=<SHA256 of the source>
flags_hash=<SHA256 of the compile options>
deps=<list of source files this unit depends on>
obj=<corresponding .o file name>
bin=<corresponding .bin file name>

Enter fullscreen mode Exit fullscreen mode

The keyword of this design is “content addressing”: the cache key is not a file name or timestamp but a hash of the input content. Change one byte of source and source_hash changes, so that unit is automatically invalidated and rebuilt; units that did not change are reused directly from .o/.bin. The deps field records dependency relations, which makes “only recompile affected modules” possible. That is the skeleton of incremental compilation, and it lays the groundwork for toolchain goals such as “a full rebuild after changing one line stays under 500 ms”. Note that what is hashed is the recomputable input, not the artifact path; otherwise the cache would silently hand you stale results.

It is worth stressing: cache correctness matters far more than cache hit rate. Better to invalidate too much and rebuild than to let an old artifact slip into a new build. That is why compile options are folded into the hash as well (flags_hash), ruling out the classic bug of “switching optimization levels yet eating the old cache”.

Looking back over the pipeline: the AST is responsible for faithfully preserving syntax and carrying Spans, HIR for flattening syntactic sugar so it can be analyzed, TIR for finalizing after type and ownership checking and performing specialization, and LLVM for the last mile of optimization and code generation. Each layer boundary corresponds to a clear analysis phase in the compiler, and once the order is reversed you are forced to do work on a representation that it was never meant for. The content-addressed cache then pays off the “performance debt” of the multi-layer pipeline, keeping iteration speed usable after bootstrapping and test growth. For new language projects, planning this “layering plus content addressing” combination early is more valuable than jumping straight to a toy compiler, because once the front-end structure is fixed, later changes mean rewriting layer by layer.
**