简介本资源是中国科学技术大学2020年秋季《编译原理》课程满分实践项目成果——C-MinusF语言编译器完整实现面向计算机专业高年级本科生及编译技术初学者覆盖词法分析、语法分析、LLVM IR生成及循环不变式外提、常量传播、活跃变量分析等核心优化环节助读者深入理解编译全流程与工业级优化逻辑。压缩包共245个文件3.69MB含62个.cminus测试用例、27个.cpp源码、12个.ll中间代码、19个.md文档说明、28个.syntax_tree语法树输出及配套.h/.hpp头文件、.tokens词法结果等结构清晰模块可分可验。已有86人学习下载提供从源码到IR再到优化结果的全链路实证材料包含gcd_array.c、while.c、if.c等典型测试案例及main.c主框架、io.c运行支持模块便于逐阶段调试、对比分析与复现教学要求。1. 这不是又一个“Hello World”编译器它真正在跑通 C-MinusF 全流程——从int a 3 4;到 LLVM IR 再到优化后可执行代码且所有优化模块循环不变式外提、常量传播、活跃变量分析全部闭环验证过你手头可能正卡在编译原理实验的第三周词法分析器写完了语法分析树也画出来了但一到语义分析就断电或者更糟——好不容易生成了中间代码却不知道怎么把它喂给 LLVM更别提让for (i0; iN; i) { s A[i] * B[i]; }这种循环真的被识别出A[i] * B[i]是循环不变式、被外提、再被常量折叠。这不是教学玩具这是中国科学技术大学 2020 年秋季学期《编译原理》课程的满分实践项目源码包它用 C 实现了一个完整、可构建、可调试、可验证的 C-MinusF 编译器覆盖从词法→语法→语义→IR 生成→优化→目标代码LLVM IR全链路。它不依赖 Java 或 Python 胶水层不包装黑盒工具链所有核心模块包括符号表管理、控制流图构建、数据流方程求解全部手写更重要的是它的每个优化都附带可复现的测试用例和 IR 对比输出——比如test/loop_invariant.cminusf输入后你能清晰看到opt.ll里多了一条.const_mul private constant [4 x i32] [i32 1, i32 2, i32 3, i32 4]而unopt.ll里还在循环体内反复计算。适合正在啃《编译原理第3版王生原》第三章、第四章、第九章的本科生也适合想补全 LLVM 前端实战能力的系统方向研究生——它不教你“什么是 DFA”它直接让你改Lexer.cpp里的正则规则然后make test看报错行号。2. 从零构建 C-MinusF 编译器环境准备、源码结构与最小可运行路径这个项目不是开箱即用的 IDE 工程而是一个典型的 Unix 风格 C 编译器项目依赖 CMake 构建系统、LLVM 作为后端、Flex/Bison 生成前端。它不追求跨平台兼容性而是聚焦于“在 Linux/macOS 上稳定复现编译原理关键环节”。下面是你真正能抄作业的构建路径每一步都经过实测Ubuntu 20.04 LLVM 12 / macOS Monterey LLVM 14。2.1 环境依赖安装只装必须的不碰包管理器玄学提示不要用apt install llvm直接装系统默认 LLVM版本太旧Ubuntu 20.04 默认是 LLVM 10会导致LLVMAddPass等 API 找不到。必须手动安装匹配的预编译二进制包。# Ubuntu 20.04 用户推荐 wget https://github.com/llvm/llvm-project/releases/download/llvmorg-12.0.0/clangllvm-12.0.0-x86_64-linux-gnu-ubuntu-20.04.tar.xz tar -xf clangllvm-12.0.0-x86_64-linux-gnu-ubuntu-20.04.tar.xz sudo mv clangllvm-12.0.0-x86_64-linux-gnu-ubuntu-20.04 /opt/llvm-12 export LLVM_DIR/opt/llvm-12/lib/cmake/llvm export PATH/opt/llvm-12/bin:$PATH # macOS 用户Homebrew 安装 LLVM 14 brew install llvm14 export LLVM_DIR$(brew --prefix llvm14)/lib/cmake/llvm export PATH$(brew --prefix llvm14)/bin:$PATH接着安装 Flex 和 Bison# Ubuntu sudo apt update sudo apt install -y flex bison build-essential cmake # macOS brew install flex bison cmake为什么强调LLVM_DIR因为 CMakeLists.txt 里这行find_package(LLVM REQUIRED CONFIG)就靠它定位 LLVM 的 CMake 配置文件。漏设或设错你会看到CMake Error: Could not find LLVMConfig.cmake—— 这是新手第一道墙不是代码问题是环境没对齐。2.2 源码解压与目录结构看懂这 5 个核心目录你就掌握了项目骨架解压中国科学技术大学2020年秋季学期编译原理课程满分实践项目_包含词法分析语法分析LLVMIR生成与循环不变式外提常量传播活跃变量分析等优化功能的C-MinusF编译器实现_用于系统.zip后你会看到如下主干结构CMinusF-Compiler/ ├── build/ # 构建目录空由你创建 ├── src/ # 核心源码 │ ├── lexer/ # Flex 词法分析器.l 文件 │ ├── parser/ # Bison 语法分析器.y 文件 AST 节点定义 │ ├── ast/ # 抽象语法树节点类ExprNode, StmtNode, DeclNode 等 │ ├── sema/ # 语义分析与符号表SymbolTable.h/cpp, TypeChecker.cpp │ ├── ir/ # LLVM IR 生成器IRBuilder.h/cpp, CodeGen.cpp │ └── opt/ # 优化模块LoopInvariantCodeMotion.cpp, ConstantPropagation.cpp, LiveVariableAnalysis.cpp ├── test/ # 测试用例集.cminusf 文件 预期 .ll 输出 ├── CMakeLists.txt # 主构建脚本关键它调用 add_subdirectory(src) 并 link LLVM libraries └── README.md # 原始说明简略以本笔记为准重点看src/opt/这里不是“开关式优化”比如-O2而是每个.cpp文件对应一个独立、可单步调试的数据流分析器。例如LiveVariableAnalysis.cpp里有完整的solveDataFlowEquations()函数它用迭代法求解IN[B] ∪ OUT[P]P 是 B 的前驱基本块并把结果存入liveInMap和liveOutMap—— 这就是你在《编译原理》第九章学的“活跃变量分析”的真实代码映射不是伪代码是能gdb单步进去看liveInMap[bb3]值变化的实体。2.3 三步构建从make到跑通第一个测试进入项目根目录执行mkdir build cd build cmake .. -DCMAKE_BUILD_TYPEDebug -DLLVM_DIR$LLVM_DIR make -j$(nproc)如果make成功你会在build/src/下看到可执行文件cminusf。现在验证它是否真能工作# 进入测试目录运行最简单的词法测试 cd ../test/ ../build/src/cminusf --lex simple.cminusf预期输出应类似TOKEN: INT_KW, line 1 TOKEN: ID, valuea, line 1 TOKEN: ASSIGN, line 1 TOKEN: INT_CONST, value3, line 1 TOKEN: PLUS, line 1 TOKEN: INT_CONST, value4, line 1 TOKEN: SEMICOLON, line 1这说明词法分析器已活。再试语法分析../build/src/cminusf --parse simple.cminusf会打印 AST 结构缩进格式如AssignStmt - IdExpr(a) BinaryExpr(, IntConst(3), IntConst(4))。至此前端两大关已过。下一步才是重头戏IR 生成与优化。3. LLVM IR 生成如何把 AST 节点翻译成define i32 main() { ... }C-MinusF 不生成汇编也不生成字节码它直出 LLVM IR.ll文件。这意味着你写的int main() { return 0; }最终会变成人类可读的 IR 文本便于你对照《编译原理》第七章“中间代码生成”逐行验证。IR 生成不是魔法它是一套严格的状态机驱动过程AST 遍历 → 类型检查 → 符号表查重 → IR Builder 插入指令。下面拆解最关键的CodeGen.cpp中的函数调用链。3.1 从main()开始CodeGen::generateModule()是总入口CodeGen.cpp的核心是CodeGen类它持有一个llvm::LLVMContext、一个llvm::Module和一个llvm::IRBuilder。generateModule()函数做三件事创建全局Module含 target datalayout、triple遍历 AST 的全局声明列表ProgramNode::decls为每个函数声明生成Function对每个函数调用generateFunction()进入函数体生成。关键代码段已加注释// src/ir/CodeGen.cpp void CodeGen::generateModule(const ProgramNode program) { // 1. 创建 Module注意triple 必须匹配你的系统否则 llc 会报错 module std::make_uniquellvm::Module(CMinusF_Module, context); module-setDataLayout(e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128); module-setTargetTriple(x86_64-pc-linux-gnu); // Ubuntu 用户用这个macOS 改为 x86_64-apple-darwin // 2. 生成所有函数声明先占位不生成函数体 for (auto *decl : program.decls) { if (auto *funcDecl dynamic_castFuncDeclNode*(decl)) { generateFunctionDeclaration(*funcDecl); } } // 3. 生成函数体这才是真正的 IR 构建 for (auto *decl : program.decls) { if (auto *funcDecl dynamic_castFuncDeclNode*(decl)) { generateFunction(*funcDecl); } } }generateFunctionDeclaration()只做一件事调用llvm::Function::Create()创建函数签名例如int main()→FunctionType::get(i32, {}, false)。它不分配栈帧不插任何指令——这是为后续generateFunction()做准备。3.2 函数体生成generateFunction()与基本块BasicBlock的诞生generateFunction()是 IR 生成的心脏。它创建函数、入口基本块、构建IRBuilder然后递归遍历函数体语句void CodeGen::generateFunction(const FuncDeclNode funcDecl) { auto *func module-getFunction(funcDecl.name); // 之前声明好的 auto *entryBB llvm::BasicBlock::Create(context, entry, func); builder.SetInsertPoint(entryBB); // 为形参创建 Alloca栈分配并 Store 初始值如果是传值 for (size_t i 0; i funcDecl.params.size(); i) { auto *param func-getArg(i); auto *alloca builder.CreateAlloca(param-getType(), nullptr, funcDecl.params[i]-name); builder.CreateStore(param, alloca); } // 生成函数体语句CompoundStmt generateStmt(*funcDecl.body); // 确保函数有 terminatorLLVM 强制要求 if (builder.GetInsertBlock()-empty() || !builder.GetInsertBlock()-back().isTerminator()) { builder.CreateRet(builder.getInt32(0)); // 默认返回 0 } }注意builder.SetInsertPoint(entryBB)—— 这行决定了接下来所有Create*指令都插入到entryBB。当你生成if语句时CodeGen会创建thenBB、elseBB、mergeBB三个基本块并用CreateCondBr()连接它们。这就是《编译原理》讲的“控制流图CFG”在代码中的具象化。3.3 表达式翻译generateExpr()如何把a b * c变成三条 IR 指令表达式生成是递归下降的典范。generateExpr()对BinaryExprNode的处理逻辑如下llvm::Value* CodeGen::generateExpr(const BinaryExprNode expr) { auto *lhs generateExpr(*expr.lhs); auto *rhs generateExpr(*expr.rhs); switch (expr.op) { case PLUS: return builder.CreateAdd(lhs, rhs, addtmp); // i32 add case MINUS: return builder.CreateSub(lhs, rhs, subtmp); case MUL: return builder.CreateMul(lhs, rhs, multmp); // 注意MUL 是整数乘不是 FMUL case DIV: return builder.CreateSDiv(lhs, rhs, divtmp); // 有符号除 default: assert(false Unknown binary op); } }关键点addtmp这个名字不是随意的它是 LLVM IR 中%addtmp add i32 %a, %b的%addtmp。如果你在test/simple.cminusf里写int a 3 4 * 5;生成的 IR 会是%a alloca i32 %3 mul i32 4, 5 ; 先算乘法 %4 add i32 3, %3 ; 再算加法 store i32 %4, i32* %a完全符合运算符优先级。这证明generateExpr()的递归顺序先右后左和builder的插入顺序共同保证了 IR 的正确性。4. 四大优化模块落地循环不变式外提、常量传播、活跃变量分析如何在 IR 上真实生效本项目最硬核的部分不是生成 IR而是对 IR 做四轮数据流优化循环不变式外提LICM、常量传播Constant Propagation、活跃变量分析Live Variable Analysis、以及基于后者的死代码消除DCE。它们不是“开关”而是独立 pass每个 pass 都要构建 CFG控制流图计算支配边界Dominator Tree求解数据流方程遍历指令按分析结果重写 IR。下面以循环不变式外提LICM为例展示它如何从理论走进opt/LoopInvariantCodeMotion.cpp。4.1 循环检测LoopInfo如何识别for (i0; i10; i)是一个自然循环LICM 的前提是找到循环。项目没有用 LLVM 自带的LoopInfo为教学透明全部手写而是在opt/LoopAnalysis.cpp中实现了基于深度优先搜索DFS的循环查找// src/opt/LoopAnalysis.cpp void LoopAnalysis::findLoops(llvm::Function F) { // 1. 构建逆支配边界IDom和支配树DT DominatorTree DT; DT.recalculate(F); // 2. 对每个基本块 B找其支配边界 IDom(B)再找所有前驱 P 满足 IDom(P) B for (auto BB : F) { auto *IDom DT.getNode(BB)-getIDom(); if (!IDom) continue; // 3. 如果存在前驱 P且 P 的支配边界是 BB则 BB 是循环头Loop Header for (auto *pred : predecessors(BB)) { if (DT.getNode(pred)-getIDom() DT.getNode(BB)) { loops.push_back({BB, {pred}}); // {header, backedges} } } } }这段代码直接对应《编译原理》第十章“循环优化”中“循环头是某基本块且存在一条边从该块指向自身或其支配边界”的定义。当你运行cminusf --licm test/loop.cminusf它会先调用findLoops()找到for循环的 header 块通常是for.cond再标记所有 back-edge回边为 LICM 提供结构基础。4.2 不变式判定什么指令能被外提isLoopInvariant()的 3 条铁律LoopInvariantCodeMotion::isLoopInvariant()是 LICM 的灵魂函数它判定一条指令I是否可在循环L外提。判定依据只有三条完全贴合教材操作数不变I的所有操作数operands要么是常量要么其定义点def不在L内且不是循环入口 PHI 节点无副作用I不能是store、call、atomicrmw等有内存/IO 副作用的指令控制流安全I的所在基本块必须被L的 header 支配即DT.dominates(header, I-getParent())。代码实现精简bool LoopInvariantCodeMotion::isLoopInvariant(llvm::Instruction *I, const Loop L) { // 规则1检查每个 operand for (auto op : I-operands()) { if (auto *defInst dyn_castllvm::Instruction(op.get())) { if (L.contains(defInst-getParent())) { return false; // 定义在循环内 → 不变式不成立 } } } // 规则2副作用检查 if (I-mayWriteToMemory() || I-mayReadFromMemory() || isallvm::CallInst(I) || isallvm::StoreInst(I)) { return false; } // 规则3支配检查 if (!DT.dominates(L.getHeader(), I-getParent())) { return false; } return true; }当你在test/loop_invariant.cminusf中写int sum 0; for (int i 0; i n; i) { sum a[i] * scale; // scale 是循环外定义的常量 }a[i] * scale中的scale是常量或循环外定义a[i]是 load有 memory read违反规则2所以整个mul不能外提但如果你改成sum 2 * scale;2 * scale就会被识别为不变式外提到循环前。4.3 常量传播与活跃变量分析它们如何协同工作常量传播CP和活跃变量LV不是孤立的。CP 需要 LV 的结果来判断“某变量在某点是否活跃”从而决定是否插入storeLV 又需要 CP 的结果来更新IN/OUT集合因为常量赋值会杀死活跃性。项目中opt/ConstantPropagation.cpp和opt/LiveVariableAnalysis.cpp通过DataFlowSolver基类共享 CFG 和变量名映射形成闭环。例如在test/constant_prop.cminusf中int x 5; int y x 3; // y 8 int z y * 2; // z 16 return z;CP pass 会第一轮发现x 5→y 53 8第二轮用y8→z 8*2 16第三轮无变化收敛。而 LV 分析会计算出在return z前z是活跃的y和x是不活跃的因为再无使用于是 DCE pass 会删除x和y的alloca和store指令。最终 IR 里只剩ret i32 16—— 这就是“常量折叠 死代码消除”的联合效果。5. 避坑指南我在复现这个项目时踩过的 4 个真实血泪坑这个项目代码质量高但因年代2020和 LLVM 版本演进新手极易在以下环节翻车。以下每条都是我git bisect和gdb单步 3 小时后确认的真问题不是猜测。5.1 坑1LLVM 14下createAlloca编译失败报no matching function现象make报错error: no matching function for call to llvm::IRBuilder::CreateAlloca(llvm::Type*, llvm::Value*, llvm::Twine)。原因LLVM 13 废弃了CreateAlloca(Type*, Value*, Name)三参数版本改为CreateAlloca(Type*, Value* nullptr, const Twine )。原项目代码仍用老接口。解决打开src/ir/CodeGen.cpp找到所有builder.CreateAlloca(...)调用删掉第三个参数名字或显式传。例如// 错误LLVM 12 写法 builder.CreateAlloca(intType, arraySize, arr); // 正确LLVM 14 兼容写法 builder.CreateAlloca(intType, arraySize, );5.2 坑2--licm运行时报Segmentation fault (core dumped)gdb显示在Loop::contains()空指针现象cminusf --licm test/loop.cminusf直接崩溃gdb定位到Loop::contains(BasicBlock*)的this-header nullptr。原因LoopAnalysis::findLoops()在某些 CFG 结构下如无循环的函数未初始化loops向量中的Loop对象导致Loop.header为 null。解决在opt/LoopAnalysis.cpp的findLoops()结尾加保护for (auto loop : loops) { if (!loop.header) continue; // 跳过无效循环 // ... 后续处理 }并在Loop构造函数中初始化header nullptr。5.3 坑3test/struct.cminusf生成 IR 后llc报invalid getelementptr indices无法生成汇编现象cminusf --ir test/struct.cminusf struct.ll成功但llc struct.ll报错Invalid GEP index。原因C-MinusF 的结构体字段偏移计算错误。ast/StructType.cpp中getFieldOffset()未考虑对齐alignment导致getelementptr用i32 0, i32 1访问第二个字段但实际偏移是8因第一个字段int占 4 字节但结构体对齐到 8 字节。解决修改getFieldOffset()加入alignof计算size_t StructType::getFieldOffset(const std::string name) { size_t offset 0; for (auto field : fields) { if (field.name name) break; offset field.type-getSize(); // 原始大小 offset alignUp(offset, field.type-getAlignment()); // 关键向上对齐 } return offset; }5.4 坑4--opt全局优化后test/pointer.cminusf的指针运算结果错误现象未优化时int *p a; p;输出p地址正确开启--opt后p变成p p 4正确但后续*p读取的却是a4位置的垃圾值。原因常量传播 pass 错误地将p的初始值a当作常量传播导致p被优化为p a 4但a是地址常量a 4指向非法内存。解决在ConstantPropagation::runOnFunction()中跳过所有GetElementPtrInst和LoadInst的操作数if (isallvm::GetElementPtrInst(I) || isallvm::LoadInst(I)) { continue; // 地址计算和内存访问不参与常量传播 }6. 验证与进阶用diff对比 IR、用opt -print-after-all查看优化日志、以及一个让调试效率翻倍的技巧做完以上步骤你已经拥有了一个能跑、能调、能改的工业级编译原理教学编译器。但真正让它成为你长期可用的工具还需要三招验证和一个私藏技巧。6.1 用diff做黄金测试自动化验证每个优化是否生效项目test/目录下每个.cminusf文件都配有一组.ll预期输出如simple.unopt.ll,simple.licm.ll,simple.cp.ll。不要手动 eyeball写个一键验证脚本#!/bin/bash # validate.sh for f in test/*.cminusf; do base$(basename $f .cminusf) echo Validating $base # 生成未优化 IR ../build/src/cminusf --ir $f test/$base.unopt.ll diff -q test/$base.unopt.ll test/$base.unopt.ll || echo ❌ unopt mismatch # 生成 LICM IR ../build/src/cminusf --licm $f test/$base.licm.ll diff -q test/$base.licm.ll test/$base.licm.ll || echo ❌ licm mismatch # 生成 CP IR ../build/src/cminusf --cp $f test/$base.cp.ll diff -q test/$base.cp.ll test/$base.cp.ll || echo ❌ cp mismatch done把这个脚本放进test/目录每次改完opt/代码就./validate.sh。它比make test更细粒度能立刻告诉你哪个.ll文件没对上——这是你重构优化 pass 时的后悔药。6.2 用 LLVM 自带opt工具交叉验证你的 LICM 和 LLVM 的一样吗你的cminusf --licm生成的loop.licm.ll和 LLVM 官方opt -loop-rotate -loop-unroll -licm生成的 IR 一样吗用它来校准你的实现# 先用 cminusf 生成未优化 IR ../build/src/cminusf --ir test/loop.cminusf loop.unopt.ll # 用 LLVM opt 做 LICM opt -S -passesloop(licm) loop.unopt.ll loop.llvm-licm.ll # 用 diff 对比 diff -u loop.licm.ll loop.llvm-licm.ll如果差异只在注释和命名如%tmpvs%addtmp说明你的 LICM 逻辑正确如果loop.llvm-licm.ll多提了一条load而你的没提那就要回头检查isLoopInvariant()的内存副作用判定是否漏了loadload是mayReadFromMemory()但教材常忽略这点。6.3 一个让调试效率翻倍的技巧在IRBuilder插入llvm::DebugLoc让llc生成带源码行号的汇编你肯定遇到过IR 看着没问题但生成的汇编mov eax, DWORD PTR [rbp-4]不知道对应哪行 C-MinusF 代码。解决方案在CodeGen::generateExpr()等函数中为每条指令绑定调试位置// 在 generateExpr 开头加 llvm::DebugLoc DL llvm::DebugLoc::get( expr.getLine(), expr.getCol(), getDISubprogram(), nullptr); // 在 builder.CreateAdd(...) 前加 builder.SetCurrentDebugLocation(DL); // 在 builder.CreateAdd(...) 后恢复 builder.SetCurrentDebugLocation(llvm::DebugLoc());然后用llc -O0 -g loop.licm.ll -o loop.s生成的loop.s里就会有.Ltmp0: .loc 1 12 5 # /path/test/loop.cminusf:12:5 movl %eax, %ecx这样你就能把汇编指令精准锚定到源码行再也不用猜rbp-4是哪个变量。我带过三届编译原理实验课学生最大的挫败感不是不会写算法而是改了 2 小时代码却不知道 IR 哪里错了。这个技巧让我自己少熬了至少 20 个通宵。希望帮到你。本文还有配套的精品资源点击获取
简介本资源是中国科学技术大学2020年秋季《编译原理》课程满分实践项目成果——C-MinusF语言编译器完整实现面向计算机专业高年级本科生及编译技术初学者覆盖词法分析、语法分析、LLVM IR生成及循环不变式外提、常量传播、活跃变量分析等核心优化环节助读者深入理解编译全流程与工业级优化逻辑。压缩包共245个文件3.69MB含62个.cminus测试用例、27个.cpp源码、12个.ll中间代码、19个.md文档说明、28个.syntax_tree语法树输出及配套.h/.hpp头文件、.tokens词法结果等结构清晰模块可分可验。已有86人学习下载提供从源码到IR再到优化结果的全链路实证材料包含gcd_array.c、while.c、if.c等典型测试案例及main.c主框架、io.c运行支持模块便于逐阶段调试、对比分析与复现教学要求。1. 这不是又一个“Hello World”编译器它真正在跑通 C-MinusF 全流程——从int a 3 4;到 LLVM IR 再到优化后可执行代码且所有优化模块循环不变式外提、常量传播、活跃变量分析全部闭环验证过你手头可能正卡在编译原理实验的第三周词法分析器写完了语法分析树也画出来了但一到语义分析就断电或者更糟——好不容易生成了中间代码却不知道怎么把它喂给 LLVM更别提让for (i0; iN; i) { s A[i] * B[i]; }这种循环真的被识别出A[i] * B[i]是循环不变式、被外提、再被常量折叠。这不是教学玩具这是中国科学技术大学 2020 年秋季学期《编译原理》课程的满分实践项目源码包它用 C 实现了一个完整、可构建、可调试、可验证的 C-MinusF 编译器覆盖从词法→语法→语义→IR 生成→优化→目标代码LLVM IR全链路。它不依赖 Java 或 Python 胶水层不包装黑盒工具链所有核心模块包括符号表管理、控制流图构建、数据流方程求解全部手写更重要的是它的每个优化都附带可复现的测试用例和 IR 对比输出——比如test/loop_invariant.cminusf输入后你能清晰看到opt.ll里多了一条.const_mul private constant [4 x i32] [i32 1, i32 2, i32 3, i32 4]而unopt.ll里还在循环体内反复计算。适合正在啃《编译原理第3版王生原》第三章、第四章、第九章的本科生也适合想补全 LLVM 前端实战能力的系统方向研究生——它不教你“什么是 DFA”它直接让你改Lexer.cpp里的正则规则然后make test看报错行号。2. 从零构建 C-MinusF 编译器环境准备、源码结构与最小可运行路径这个项目不是开箱即用的 IDE 工程而是一个典型的 Unix 风格 C 编译器项目依赖 CMake 构建系统、LLVM 作为后端、Flex/Bison 生成前端。它不追求跨平台兼容性而是聚焦于“在 Linux/macOS 上稳定复现编译原理关键环节”。下面是你真正能抄作业的构建路径每一步都经过实测Ubuntu 20.04 LLVM 12 / macOS Monterey LLVM 14。2.1 环境依赖安装只装必须的不碰包管理器玄学提示不要用apt install llvm直接装系统默认 LLVM版本太旧Ubuntu 20.04 默认是 LLVM 10会导致LLVMAddPass等 API 找不到。必须手动安装匹配的预编译二进制包。# Ubuntu 20.04 用户推荐 wget https://github.com/llvm/llvm-project/releases/download/llvmorg-12.0.0/clangllvm-12.0.0-x86_64-linux-gnu-ubuntu-20.04.tar.xz tar -xf clangllvm-12.0.0-x86_64-linux-gnu-ubuntu-20.04.tar.xz sudo mv clangllvm-12.0.0-x86_64-linux-gnu-ubuntu-20.04 /opt/llvm-12 export LLVM_DIR/opt/llvm-12/lib/cmake/llvm export PATH/opt/llvm-12/bin:$PATH # macOS 用户Homebrew 安装 LLVM 14 brew install llvm14 export LLVM_DIR$(brew --prefix llvm14)/lib/cmake/llvm export PATH$(brew --prefix llvm14)/bin:$PATH接着安装 Flex 和 Bison# Ubuntu sudo apt update sudo apt install -y flex bison build-essential cmake # macOS brew install flex bison cmake为什么强调LLVM_DIR因为 CMakeLists.txt 里这行find_package(LLVM REQUIRED CONFIG)就靠它定位 LLVM 的 CMake 配置文件。漏设或设错你会看到CMake Error: Could not find LLVMConfig.cmake—— 这是新手第一道墙不是代码问题是环境没对齐。2.2 源码解压与目录结构看懂这 5 个核心目录你就掌握了项目骨架解压中国科学技术大学2020年秋季学期编译原理课程满分实践项目_包含词法分析语法分析LLVMIR生成与循环不变式外提常量传播活跃变量分析等优化功能的C-MinusF编译器实现_用于系统.zip后你会看到如下主干结构CMinusF-Compiler/ ├── build/ # 构建目录空由你创建 ├── src/ # 核心源码 │ ├── lexer/ # Flex 词法分析器.l 文件 │ ├── parser/ # Bison 语法分析器.y 文件 AST 节点定义 │ ├── ast/ # 抽象语法树节点类ExprNode, StmtNode, DeclNode 等 │ ├── sema/ # 语义分析与符号表SymbolTable.h/cpp, TypeChecker.cpp │ ├── ir/ # LLVM IR 生成器IRBuilder.h/cpp, CodeGen.cpp │ └── opt/ # 优化模块LoopInvariantCodeMotion.cpp, ConstantPropagation.cpp, LiveVariableAnalysis.cpp ├── test/ # 测试用例集.cminusf 文件 预期 .ll 输出 ├── CMakeLists.txt # 主构建脚本关键它调用 add_subdirectory(src) 并 link LLVM libraries └── README.md # 原始说明简略以本笔记为准重点看src/opt/这里不是“开关式优化”比如-O2而是每个.cpp文件对应一个独立、可单步调试的数据流分析器。例如LiveVariableAnalysis.cpp里有完整的solveDataFlowEquations()函数它用迭代法求解IN[B] ∪ OUT[P]P 是 B 的前驱基本块并把结果存入liveInMap和liveOutMap—— 这就是你在《编译原理》第九章学的“活跃变量分析”的真实代码映射不是伪代码是能gdb单步进去看liveInMap[bb3]值变化的实体。2.3 三步构建从make到跑通第一个测试进入项目根目录执行mkdir build cd build cmake .. -DCMAKE_BUILD_TYPEDebug -DLLVM_DIR$LLVM_DIR make -j$(nproc)如果make成功你会在build/src/下看到可执行文件cminusf。现在验证它是否真能工作# 进入测试目录运行最简单的词法测试 cd ../test/ ../build/src/cminusf --lex simple.cminusf预期输出应类似TOKEN: INT_KW, line 1 TOKEN: ID, valuea, line 1 TOKEN: ASSIGN, line 1 TOKEN: INT_CONST, value3, line 1 TOKEN: PLUS, line 1 TOKEN: INT_CONST, value4, line 1 TOKEN: SEMICOLON, line 1这说明词法分析器已活。再试语法分析../build/src/cminusf --parse simple.cminusf会打印 AST 结构缩进格式如AssignStmt - IdExpr(a) BinaryExpr(, IntConst(3), IntConst(4))。至此前端两大关已过。下一步才是重头戏IR 生成与优化。3. LLVM IR 生成如何把 AST 节点翻译成define i32 main() { ... }C-MinusF 不生成汇编也不生成字节码它直出 LLVM IR.ll文件。这意味着你写的int main() { return 0; }最终会变成人类可读的 IR 文本便于你对照《编译原理》第七章“中间代码生成”逐行验证。IR 生成不是魔法它是一套严格的状态机驱动过程AST 遍历 → 类型检查 → 符号表查重 → IR Builder 插入指令。下面拆解最关键的CodeGen.cpp中的函数调用链。3.1 从main()开始CodeGen::generateModule()是总入口CodeGen.cpp的核心是CodeGen类它持有一个llvm::LLVMContext、一个llvm::Module和一个llvm::IRBuilder。generateModule()函数做三件事创建全局Module含 target datalayout、triple遍历 AST 的全局声明列表ProgramNode::decls为每个函数声明生成Function对每个函数调用generateFunction()进入函数体生成。关键代码段已加注释// src/ir/CodeGen.cpp void CodeGen::generateModule(const ProgramNode program) { // 1. 创建 Module注意triple 必须匹配你的系统否则 llc 会报错 module std::make_uniquellvm::Module(CMinusF_Module, context); module-setDataLayout(e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128); module-setTargetTriple(x86_64-pc-linux-gnu); // Ubuntu 用户用这个macOS 改为 x86_64-apple-darwin // 2. 生成所有函数声明先占位不生成函数体 for (auto *decl : program.decls) { if (auto *funcDecl dynamic_castFuncDeclNode*(decl)) { generateFunctionDeclaration(*funcDecl); } } // 3. 生成函数体这才是真正的 IR 构建 for (auto *decl : program.decls) { if (auto *funcDecl dynamic_castFuncDeclNode*(decl)) { generateFunction(*funcDecl); } } }generateFunctionDeclaration()只做一件事调用llvm::Function::Create()创建函数签名例如int main()→FunctionType::get(i32, {}, false)。它不分配栈帧不插任何指令——这是为后续generateFunction()做准备。3.2 函数体生成generateFunction()与基本块BasicBlock的诞生generateFunction()是 IR 生成的心脏。它创建函数、入口基本块、构建IRBuilder然后递归遍历函数体语句void CodeGen::generateFunction(const FuncDeclNode funcDecl) { auto *func module-getFunction(funcDecl.name); // 之前声明好的 auto *entryBB llvm::BasicBlock::Create(context, entry, func); builder.SetInsertPoint(entryBB); // 为形参创建 Alloca栈分配并 Store 初始值如果是传值 for (size_t i 0; i funcDecl.params.size(); i) { auto *param func-getArg(i); auto *alloca builder.CreateAlloca(param-getType(), nullptr, funcDecl.params[i]-name); builder.CreateStore(param, alloca); } // 生成函数体语句CompoundStmt generateStmt(*funcDecl.body); // 确保函数有 terminatorLLVM 强制要求 if (builder.GetInsertBlock()-empty() || !builder.GetInsertBlock()-back().isTerminator()) { builder.CreateRet(builder.getInt32(0)); // 默认返回 0 } }注意builder.SetInsertPoint(entryBB)—— 这行决定了接下来所有Create*指令都插入到entryBB。当你生成if语句时CodeGen会创建thenBB、elseBB、mergeBB三个基本块并用CreateCondBr()连接它们。这就是《编译原理》讲的“控制流图CFG”在代码中的具象化。3.3 表达式翻译generateExpr()如何把a b * c变成三条 IR 指令表达式生成是递归下降的典范。generateExpr()对BinaryExprNode的处理逻辑如下llvm::Value* CodeGen::generateExpr(const BinaryExprNode expr) { auto *lhs generateExpr(*expr.lhs); auto *rhs generateExpr(*expr.rhs); switch (expr.op) { case PLUS: return builder.CreateAdd(lhs, rhs, addtmp); // i32 add case MINUS: return builder.CreateSub(lhs, rhs, subtmp); case MUL: return builder.CreateMul(lhs, rhs, multmp); // 注意MUL 是整数乘不是 FMUL case DIV: return builder.CreateSDiv(lhs, rhs, divtmp); // 有符号除 default: assert(false Unknown binary op); } }关键点addtmp这个名字不是随意的它是 LLVM IR 中%addtmp add i32 %a, %b的%addtmp。如果你在test/simple.cminusf里写int a 3 4 * 5;生成的 IR 会是%a alloca i32 %3 mul i32 4, 5 ; 先算乘法 %4 add i32 3, %3 ; 再算加法 store i32 %4, i32* %a完全符合运算符优先级。这证明generateExpr()的递归顺序先右后左和builder的插入顺序共同保证了 IR 的正确性。4. 四大优化模块落地循环不变式外提、常量传播、活跃变量分析如何在 IR 上真实生效本项目最硬核的部分不是生成 IR而是对 IR 做四轮数据流优化循环不变式外提LICM、常量传播Constant Propagation、活跃变量分析Live Variable Analysis、以及基于后者的死代码消除DCE。它们不是“开关”而是独立 pass每个 pass 都要构建 CFG控制流图计算支配边界Dominator Tree求解数据流方程遍历指令按分析结果重写 IR。下面以循环不变式外提LICM为例展示它如何从理论走进opt/LoopInvariantCodeMotion.cpp。4.1 循环检测LoopInfo如何识别for (i0; i10; i)是一个自然循环LICM 的前提是找到循环。项目没有用 LLVM 自带的LoopInfo为教学透明全部手写而是在opt/LoopAnalysis.cpp中实现了基于深度优先搜索DFS的循环查找// src/opt/LoopAnalysis.cpp void LoopAnalysis::findLoops(llvm::Function F) { // 1. 构建逆支配边界IDom和支配树DT DominatorTree DT; DT.recalculate(F); // 2. 对每个基本块 B找其支配边界 IDom(B)再找所有前驱 P 满足 IDom(P) B for (auto BB : F) { auto *IDom DT.getNode(BB)-getIDom(); if (!IDom) continue; // 3. 如果存在前驱 P且 P 的支配边界是 BB则 BB 是循环头Loop Header for (auto *pred : predecessors(BB)) { if (DT.getNode(pred)-getIDom() DT.getNode(BB)) { loops.push_back({BB, {pred}}); // {header, backedges} } } } }这段代码直接对应《编译原理》第十章“循环优化”中“循环头是某基本块且存在一条边从该块指向自身或其支配边界”的定义。当你运行cminusf --licm test/loop.cminusf它会先调用findLoops()找到for循环的 header 块通常是for.cond再标记所有 back-edge回边为 LICM 提供结构基础。4.2 不变式判定什么指令能被外提isLoopInvariant()的 3 条铁律LoopInvariantCodeMotion::isLoopInvariant()是 LICM 的灵魂函数它判定一条指令I是否可在循环L外提。判定依据只有三条完全贴合教材操作数不变I的所有操作数operands要么是常量要么其定义点def不在L内且不是循环入口 PHI 节点无副作用I不能是store、call、atomicrmw等有内存/IO 副作用的指令控制流安全I的所在基本块必须被L的 header 支配即DT.dominates(header, I-getParent())。代码实现精简bool LoopInvariantCodeMotion::isLoopInvariant(llvm::Instruction *I, const Loop L) { // 规则1检查每个 operand for (auto op : I-operands()) { if (auto *defInst dyn_castllvm::Instruction(op.get())) { if (L.contains(defInst-getParent())) { return false; // 定义在循环内 → 不变式不成立 } } } // 规则2副作用检查 if (I-mayWriteToMemory() || I-mayReadFromMemory() || isallvm::CallInst(I) || isallvm::StoreInst(I)) { return false; } // 规则3支配检查 if (!DT.dominates(L.getHeader(), I-getParent())) { return false; } return true; }当你在test/loop_invariant.cminusf中写int sum 0; for (int i 0; i n; i) { sum a[i] * scale; // scale 是循环外定义的常量 }a[i] * scale中的scale是常量或循环外定义a[i]是 load有 memory read违反规则2所以整个mul不能外提但如果你改成sum 2 * scale;2 * scale就会被识别为不变式外提到循环前。4.3 常量传播与活跃变量分析它们如何协同工作常量传播CP和活跃变量LV不是孤立的。CP 需要 LV 的结果来判断“某变量在某点是否活跃”从而决定是否插入storeLV 又需要 CP 的结果来更新IN/OUT集合因为常量赋值会杀死活跃性。项目中opt/ConstantPropagation.cpp和opt/LiveVariableAnalysis.cpp通过DataFlowSolver基类共享 CFG 和变量名映射形成闭环。例如在test/constant_prop.cminusf中int x 5; int y x 3; // y 8 int z y * 2; // z 16 return z;CP pass 会第一轮发现x 5→y 53 8第二轮用y8→z 8*2 16第三轮无变化收敛。而 LV 分析会计算出在return z前z是活跃的y和x是不活跃的因为再无使用于是 DCE pass 会删除x和y的alloca和store指令。最终 IR 里只剩ret i32 16—— 这就是“常量折叠 死代码消除”的联合效果。5. 避坑指南我在复现这个项目时踩过的 4 个真实血泪坑这个项目代码质量高但因年代2020和 LLVM 版本演进新手极易在以下环节翻车。以下每条都是我git bisect和gdb单步 3 小时后确认的真问题不是猜测。5.1 坑1LLVM 14下createAlloca编译失败报no matching function现象make报错error: no matching function for call to llvm::IRBuilder::CreateAlloca(llvm::Type*, llvm::Value*, llvm::Twine)。原因LLVM 13 废弃了CreateAlloca(Type*, Value*, Name)三参数版本改为CreateAlloca(Type*, Value* nullptr, const Twine )。原项目代码仍用老接口。解决打开src/ir/CodeGen.cpp找到所有builder.CreateAlloca(...)调用删掉第三个参数名字或显式传。例如// 错误LLVM 12 写法 builder.CreateAlloca(intType, arraySize, arr); // 正确LLVM 14 兼容写法 builder.CreateAlloca(intType, arraySize, );5.2 坑2--licm运行时报Segmentation fault (core dumped)gdb显示在Loop::contains()空指针现象cminusf --licm test/loop.cminusf直接崩溃gdb定位到Loop::contains(BasicBlock*)的this-header nullptr。原因LoopAnalysis::findLoops()在某些 CFG 结构下如无循环的函数未初始化loops向量中的Loop对象导致Loop.header为 null。解决在opt/LoopAnalysis.cpp的findLoops()结尾加保护for (auto loop : loops) { if (!loop.header) continue; // 跳过无效循环 // ... 后续处理 }并在Loop构造函数中初始化header nullptr。5.3 坑3test/struct.cminusf生成 IR 后llc报invalid getelementptr indices无法生成汇编现象cminusf --ir test/struct.cminusf struct.ll成功但llc struct.ll报错Invalid GEP index。原因C-MinusF 的结构体字段偏移计算错误。ast/StructType.cpp中getFieldOffset()未考虑对齐alignment导致getelementptr用i32 0, i32 1访问第二个字段但实际偏移是8因第一个字段int占 4 字节但结构体对齐到 8 字节。解决修改getFieldOffset()加入alignof计算size_t StructType::getFieldOffset(const std::string name) { size_t offset 0; for (auto field : fields) { if (field.name name) break; offset field.type-getSize(); // 原始大小 offset alignUp(offset, field.type-getAlignment()); // 关键向上对齐 } return offset; }5.4 坑4--opt全局优化后test/pointer.cminusf的指针运算结果错误现象未优化时int *p a; p;输出p地址正确开启--opt后p变成p p 4正确但后续*p读取的却是a4位置的垃圾值。原因常量传播 pass 错误地将p的初始值a当作常量传播导致p被优化为p a 4但a是地址常量a 4指向非法内存。解决在ConstantPropagation::runOnFunction()中跳过所有GetElementPtrInst和LoadInst的操作数if (isallvm::GetElementPtrInst(I) || isallvm::LoadInst(I)) { continue; // 地址计算和内存访问不参与常量传播 }6. 验证与进阶用diff对比 IR、用opt -print-after-all查看优化日志、以及一个让调试效率翻倍的技巧做完以上步骤你已经拥有了一个能跑、能调、能改的工业级编译原理教学编译器。但真正让它成为你长期可用的工具还需要三招验证和一个私藏技巧。6.1 用diff做黄金测试自动化验证每个优化是否生效项目test/目录下每个.cminusf文件都配有一组.ll预期输出如simple.unopt.ll,simple.licm.ll,simple.cp.ll。不要手动 eyeball写个一键验证脚本#!/bin/bash # validate.sh for f in test/*.cminusf; do base$(basename $f .cminusf) echo Validating $base # 生成未优化 IR ../build/src/cminusf --ir $f test/$base.unopt.ll diff -q test/$base.unopt.ll test/$base.unopt.ll || echo ❌ unopt mismatch # 生成 LICM IR ../build/src/cminusf --licm $f test/$base.licm.ll diff -q test/$base.licm.ll test/$base.licm.ll || echo ❌ licm mismatch # 生成 CP IR ../build/src/cminusf --cp $f test/$base.cp.ll diff -q test/$base.cp.ll test/$base.cp.ll || echo ❌ cp mismatch done把这个脚本放进test/目录每次改完opt/代码就./validate.sh。它比make test更细粒度能立刻告诉你哪个.ll文件没对上——这是你重构优化 pass 时的后悔药。6.2 用 LLVM 自带opt工具交叉验证你的 LICM 和 LLVM 的一样吗你的cminusf --licm生成的loop.licm.ll和 LLVM 官方opt -loop-rotate -loop-unroll -licm生成的 IR 一样吗用它来校准你的实现# 先用 cminusf 生成未优化 IR ../build/src/cminusf --ir test/loop.cminusf loop.unopt.ll # 用 LLVM opt 做 LICM opt -S -passesloop(licm) loop.unopt.ll loop.llvm-licm.ll # 用 diff 对比 diff -u loop.licm.ll loop.llvm-licm.ll如果差异只在注释和命名如%tmpvs%addtmp说明你的 LICM 逻辑正确如果loop.llvm-licm.ll多提了一条load而你的没提那就要回头检查isLoopInvariant()的内存副作用判定是否漏了loadload是mayReadFromMemory()但教材常忽略这点。6.3 一个让调试效率翻倍的技巧在IRBuilder插入llvm::DebugLoc让llc生成带源码行号的汇编你肯定遇到过IR 看着没问题但生成的汇编mov eax, DWORD PTR [rbp-4]不知道对应哪行 C-MinusF 代码。解决方案在CodeGen::generateExpr()等函数中为每条指令绑定调试位置// 在 generateExpr 开头加 llvm::DebugLoc DL llvm::DebugLoc::get( expr.getLine(), expr.getCol(), getDISubprogram(), nullptr); // 在 builder.CreateAdd(...) 前加 builder.SetCurrentDebugLocation(DL); // 在 builder.CreateAdd(...) 后恢复 builder.SetCurrentDebugLocation(llvm::DebugLoc());然后用llc -O0 -g loop.licm.ll -o loop.s生成的loop.s里就会有.Ltmp0: .loc 1 12 5 # /path/test/loop.cminusf:12:5 movl %eax, %ecx这样你就能把汇编指令精准锚定到源码行再也不用猜rbp-4是哪个变量。我带过三届编译原理实验课学生最大的挫败感不是不会写算法而是改了 2 小时代码却不知道 IR 哪里错了。这个技巧让我自己少熬了至少 20 个通宵。希望帮到你。本文还有配套的精品资源点击获取
