A full front-to-back compiler for Cminus-f — lexer, parser, AST, LightIR (an LLVM-IR subset) generation, LoongArch code generation, and machine-independent optimization — an independent, from-skeleton implementation of USTC 编译原理和技术 (Compiler Principles and Technology) (University of Science and Technology of China), part of a csdiy.wiki full-catalog build.
Cminus-f is a small C-like language (integers, floats, arrays, functions, if/while,
recursion). This repo builds a complete compiler for it, structured as the four USTC labs:
- Front end — a Flex lexer and Bison LALR parser produce a concrete syntax tree, which is lowered to a typed AST.
- LightIR generation — an AST visitor emits LightIR, a hand-written subset of LLVM IR
(SSA values, typed pointers,
alloca/load/store,getelementptr,phi,br, integer/float arithmetic and comparisons,call,sitofp/fptosi/zext). The printed IR is textually compatible withclang, so generated.llcan be compiled by LLVM directly. - Back end — a stack-allocating code generator translates LightIR to LoongArch
(LoongArch64 / Loongson) assembly, which is assembled and run with the cross-toolchain +
qemu-loongarch64. - Optimization — machine-independent passes: Mem2Reg (promote stack slots to SSA registers using a dominance-frontier phi-insertion + renaming algorithm, on top of a dominator-tree analysis) and LICM (loop-invariant code motion, on top of natural-loop detection and a purity analysis).
Every lab was verified with the course's own grading scripts. Full logs are in
results/.
| Lab | What it does | Result (measured, course grader) |
|---|---|---|
| 1 — Lexer/Parser | Flex+Bison → syntax tree → AST | syntax_tree 40/40, AST 34/34 |
| 2 — LightIR gen | Cminus-f → LLVM-IR subset, run via clang | 100/100 (lv0_1 17, lv0_2 18, lv1 31, lv2 23, lv3 11 — incl. bonuses) |
| 3 — Code generation | LightIR → LoongArch asm, run via qemu | 14/14 testcases + 21/21 general + 6/6 warmup |
| 4 — Optimization | Mem2Reg + LICM, run via qemu | Mem2Reg 14/14 + 3/3; LICM 14/14 + 4/4 loops |
Source (Euclid's GCD by recursion) compiles cleanly through every stage and runs correctly
under qemu-loongarch64. The -mem2reg -licm passes promote all local scalars out of memory,
shrinking the gcd/main IR from 66 → 37 lines (all alloca/load/store for locals
eliminated). See results/demo/ for the emitted gcd.syntax_tree, gcd.ll,
gcd.opt.ll, and gcd.s.
; gcd(), unoptimized ; gcd(), after -mem2reg
define i32 @gcd(i32 %arg0, i32 %arg1) { define i32 @gcd(i32 %arg0, i32 %arg1) {
label_entry: label_entry:
%op2 = alloca i32 %op2 = icmp eq i32 %arg1, 0
store i32 %arg0, i32* %op2 %op3 = zext i1 %op2 to i32
%op3 = alloca i32 %op4 = icmp ne i32 %op3, 0
store i32 %arg1, i32* %op3 br i1 %op4, label %label5, label %label6
%op4 = load i32, i32* %op3 label5:
%op5 = icmp eq i32 %op4, 0 ret i32 %arg0 ; was load %op2
... ...- Lab 1 — Lexical & syntax analysis — Flex token rules for Cminus-f, Bison grammar
with the full production set, syntax-tree construction, and AST lowering
(
src/parser/lexical_analyzer.l,src/parser/syntax_analyzer.y,src/common/ast.cpp). - Lab 2 — LightIR generation — a
CminusfBuilderAST visitor generating SSA IR: scopes, global/local vars & arrays, arithmetic with int/float promotion, comparisons, boolean lowering, control flow, function calls, and array GEP with negative-index checks (src/cminusfc/cminusf_builder.cpp). - Lab 3 — LoongArch code generation — stack-frame layout, prologue/epilogue, register
loads/stores, integer & float binary ops,
icmp/fcmp,alloca/load/store,getelementptr,zext/sitofp/fptosi, and the calling convention (src/codegen/CodeGen.cpp). - Lab 4 — Machine-independent optimization — dominator tree, natural-loop detection,
function purity analysis, Mem2Reg (SSA construction), LICM, and dead-code elimination
(
src/passes/).
ustc-compilers/
├── include/ # public headers
│ ├── common/ # AST, logging, syntax_tree
│ ├── lightir/ # LightIR: Module/Function/BasicBlock/Instruction/Type/...
│ ├── cminusfc/ # AST-visitor IR builder
│ ├── codegen/ # LoongArch codegen + register/ASM helpers
│ └── passes/ # Dominators, LoopDetection, Mem2Reg, LICM, DeadCode, FuncInfo
├── src/ # implementations (mirrors include/) + parser/ (flex+bison) + io/
├── tests/ # the course's own graders + testcases
│ ├── 1-parser/ # eval_phase1.sh (syntax tree), eval_phase2.sh (AST)
│ ├── 2-ir-gen/ # autogen/eval_lab2.py
│ ├── 3-codegen/ # autogen/eval_lab3.sh + warmup/
│ └── 4-opt/ # eval_lab4.sh (mem2reg / licm)
├── results/ # captured verification logs + a full-pipeline demo/
└── CMakeLists.txt
Linux (or WSL2). Toolchain: cmake, flex, bison, LLVM dev headers, clang; for the
LoongArch back end also qemu-user and a LoongArch cross-gcc.
# Ubuntu 24.04
sudo apt-get install -y cmake flex bison llvm-18-dev clang \
qemu-user gcc-14-loongarch64-linux-gnu
# the lab scripts call `loongarch64-unknown-linux-gnu-gcc`:
sudo ln -sf /usr/bin/loongarch64-linux-gnu-gcc-14 \
/usr/local/bin/loongarch64-unknown-linux-gnu-gcc
# build
cmake -S . -B build -DCMAKE_BUILD_TYPE=Debug \
-DLLVM_DIR=/usr/lib/llvm-18/lib/cmake/llvm
cmake --build build -j
# compile a program through the whole pipeline
build/cminusfc -emit-llvm foo.cminus -o foo.ll # Cminus-f -> LightIR
build/cminusfc -S foo.cminus -o foo.s # Cminus-f -> LoongArch asm
build/cminusfc -S -mem2reg -licm foo.cminus -o foo.s # with optimization
loongarch64-unknown-linux-gnu-gcc -static foo.s src/io/io.c -o foo && qemu-loongarch64 ./fooReproduce every number in the results table:
# Lab 1 — parser (syntax tree) and AST
cd tests/1-parser && BUILD_DIR=$PWD/../../build bash eval_phase1.sh -all yes # 40/40
BUILD_DIR=$PWD/../../build bash eval_phase2.sh -all yes # 34/34
# Lab 2 — IR generation autograder
cd tests/2-ir-gen/autogen && python3 eval_lab2.py && cat eval_result # 100
# Lab 3 — LoongArch codegen
cd tests/3-codegen/autogen && bash eval_lab3.sh ./testcases test # 14 OK
bash eval_lab3.sh ../../testcases_general test # 21 OK
# Lab 4 — optimization (compiles with the pass, runs, diffs output)
cd tests/4-opt && bash eval_lab4.sh mem2reg ./testcases/functional-cases test
bash eval_lab4.sh licm ./testcases/loop testCaptured runs of all of the above are in results/lab{1,2,3,4}-*.txt, and the environment
they were measured on is in results/environment.txt.
C++17, Flex 2.6.4, Bison 3.8.2, LLVM 18 (headers / support+core, for the IR-printing path
and find_package(LLVM)), CMake. Back-end target: LoongArch64, run under qemu-loongarch64.
- SSA construction in practice — computing a dominator tree and dominance frontiers, then
Mem2Reg's phi-placement + variable-renaming to turn
alloca-heavy IR into clean SSA. - A minimal but faithful LLVM-IR — LightIR mirrors LLVM's value/user/use graph and type
system closely enough that its textual output compiles under real
clang. - Stack-machine code generation — laying out a frame, honoring a calling convention, and
materializing every IR instruction (including
getelementptraddress arithmetic and int/float conversions) into LoongArch instructions. - Loop optimization — natural-loop detection + purity analysis are what make LICM safe; hoisting is the easy part.
- Grading against real emulated hardware — the back-end labs are validated by actually
running the compiled program under
qemu-loongarch64and diffing its output, not by inspecting assembly.
Based on the labs of USTC 编译原理和技术 (Compiler Principles and Technology) by the University of Science and Technology of China (course site, csdiy.wiki entry). This repository is an independent educational reimplementation; the course skeleton, specifications, testcases, and grading scripts belong to their original authors. Original implementation code in this repo is released under the MIT License.