2、编译原理基础回顾：词法分析、语法分析、语义分析、中间表示、优化与代码生成的基本流程

编译器的本质是一个“翻译器”，它将高级语言（如 C/C++、Rust、Swift）翻译为低级语言（如汇编或机器码）。无论目标平台是 x86、ARM 还是 RISC-V，这一翻译过程都遵循一套经典的分阶段架构。理解这套架构不仅是学习 LLVM 的前提，更是后续深入 IR（中间表示）、Pass 管线和后端代码生成的基础。本章将系统回顾编译器的六大核心阶段——词法分析、语法分析、语义分析、中间表示、优化与代码生成，并结合 LLVM 的实际工程实现，帮助读者建立从源码到机器码的完整认知链路。

编译器前端到后端整体流程 词法分析 源码 → 流 Lexer / Scanner 语法分析 → AST Parser / Bison 语义分析 AST → 类型检查 Sema / Type Check 中间表示 AST → LLVM IR CodeGen (IR) 优化 IR Pass Opt Pipeline 代码生成 IR → 汇编 Backend 指令选择 SelectionDAG ISel 指令调度 Scheduling PreRA / PostRA 寄存器分配 RegAlloc Greedy / PBQP 指令输出 Emit MC / AsmPrinter 前端（Frontend） 后端（Backend） 目标机器码 / 汇编 注：LLVM 前端（Clang）负责前三阶段，中端（Opt）负责优化，后端（LLVM Backend）负责代码生成。

上图展示了编译器从源码到机器码的完整流水线。在 LLVM 架构中，这条流水线被清晰地划分为三个部分：前端（Clang）、中端（优化器）和后端（代码生成器）。前端负责将源代码转换为 LLVM IR，中端对 IR 进行平台无关的优化，后端则将优化后的 IR 转换为目标平台的机器码。下面我们逐一深入每个阶段的原理与实现。

2.1 词法分析：从字符流到 流

核心原理

词法分析（Lexical Analysis）是编译器的第一个阶段，其输入是原始源代码字符流，输出是 序列。 是源代码的最小语法单元，通常包含关键字（如 if、while）、标识符（变量名、函数名）、字面量（整数、浮点数、字符串）、运算符（+、-、*）和分隔符（括号、分号）。词法分析器（Lexer）通过有限状态自动机（DFA）识别这些模式，并丢弃注释和空白字符。

在 LLVM 中，Clang 的 Lexer 实现于 clang/lib/Lex 目录，核心类是 clang::Lexer 和 clang::。Clang 的 Lexer 不仅处理常规 ，还处理预处理器指令（如 #include、#define），这是 C/C++ 词法分析的特殊之处。

判断方法与操作流程

词法分析器的实现通常遵循以下步骤：

  1. 输入缓冲：将源码读入内存缓冲区，维护当前字符指针。
  2. 状态转移：根据当前字符和状态，决定下一个状态。例如，遇到 / 时，需要判断是除法运算符还是注释的开始。
  3. 生成：当识别出一个完整的词素（Lexeme）时，生成对应的 ，记录其类型、位置（行号、列号）和文本值。
  4. 错误处理：遇到无法识别的字符时，报告词法错误（如非法字符 @）。
类型示例LLVM 中的表示
关键字if, returntok::kw_if
标识符foo, _counttok::identifier
整数字面量42, 0xFFtok::numeric_constant
字符串字面量"hello"tok::string_literal
运算符+, ->tok::plus, tok::arrow

案例拆解：Clang 处理 int x = 42;

假设输入源码为 int x = 42;，Clang 的 Lexer 会依次生成以下 流：

tok::kw_int      // 关键字 int
tok::identifier  // x
tok::equal       // =
tok::numeric_constant  // 42
tok::semi        // ;

每个 还携带 SourceLocation 信息，用于后续诊断和调试。例如，42 的 SourceLocation 指向第 1 行第 12 列。

经验提醒：在 LLVM 开发中，如果你需要编写自定义语言的词法分析器，可以直接复用 Clang 的 Lexer 基础设施，或者使用 llvm::StringRef 和正则表达式库自行实现。但要注意，C/C++ 的预处理与词法分析是交织的，Clang 通过 Preprocessor 类统一管理。

常见误区

  • 混淆词法分析与语法分析：词法分析只负责识别 ，不负责检查语法结构。例如，int int 在词法上合法（两个关键字 ），但在语法上非法。
  • 忽略 Unicode 支持：现代语言（如 Swift）支持 Unicode 标识符，词法分析器需要处理多字节字符编码。
  • 错误恢复策略：生产级编译器在遇到词法错误时不应立即停止，而应跳过错误字符并继续扫描，以便报告更多错误。

2.2 语法分析：从 流到抽象语法树

核心原理

语法分析（Syntax Analysis / Parsing）接收 流，根据语言的上下文无关文法（CFG）构建抽象语法树（AST）。AST 是源代码的树状结构表示，去除了括号、分号等冗余信息，保留了表达式的嵌套关系和语句的执行顺序。语法分析器（Parser）通常采用两种策略：自顶向下（递归下降）或自底向上（LR 系列）。

Clang 使用递归下降解析器，手写实现于 clang/lib/Parse。每个语法规则对应一个解析函数，例如 ParseIfStmt()、ParseExpr()。手写解析器的优势是错误信息更友好、支持增量解析（用于 IDE 代码补全）。

判断方法与操作流程

递归下降解析的基本流程：

  1. 预测：根据当前 类型，决定调用哪个解析函数。例如，看到 if 关键字，调用 ParseIfStmt()。
  2. 匹配：解析函数内部按文法规则依次消费 ，并递归调用子解析函数。
  3. 构建 AST 节点：每解析完一个语法单元，创建对应的 AST 节点（如 IfStmt、BinaryOperator）。
  4. 错误恢复：当 不匹配时，尝试同步（Synchronization）——跳过 直到找到安全的恢复点（如分号或右花括号）。

案例拆解：解析 if (x > 0) return x;

Clang 的解析过程如下：

ParseIfStmt():
  Expect tok::kw_if
  Expect tok::l_paren
  ParseExpr() → 解析 x > 0，生成 BinaryOperator 节点（Opcode=GT）
  Expect tok::r_paren
  ParseStmt() → 解析 return x;，生成 ReturnStmt 节点
  构建 IfStmt 节点，包含条件表达式和 then 分支

最终生成的 AST 结构（简化）：

IfStmt
├── Condition: BinaryOperator '>'
│   ├── LHS: DeclRefExpr 'x'
│   └── RHS: IntegerLiteral 0
└── Then: ReturnStmt
    └── RetValue: DeclRefExpr 'x'
LLVM 视角：Clang 的 AST 节点定义在 clang/include/clang/AST 中，所有节点继承自 Stmt 或 Decl。AST 不仅用于语义分析，还驱动 IDE 的代码高亮、重构和静态分析。LLVM 的 IR 生成（CodeGen）也是通过遍历 AST 完成的。

常见误区

  • 文法歧义：如悬空 else（dangling else）问题，需要优先级和结合性规则解决。
  • 左递归：递归下降解析器无法直接处理左递归文法，需要改写为右递归或使用循环。
  • 性能陷阱：回溯（Backtracking）会显著降低解析速度，应通过预测（Lookahead）避免。

2.3 语义分析：类型检查与作用域解析

核心原理

语义分析（Semantic Analysis）确保程序在语义上合法，而不仅仅是语法上正确。主要任务包括：类型检查（如 int + float 是否允许）、作用域解析（变量是否已声明）、函数重载决议、隐式类型转换等。语义分析通常基于 AST 进行，维护一个符号表（Symbol Table）记录变量、函数、类型的属性和作用域。

在 Clang 中，语义分析由 Sema 类完成（clang/lib/Sema）。Sema 在 Parser 构建 AST 节点时被回调，例如解析完一个表达式后，Sema 会检查其类型是否匹配上下文。

判断方法与操作流程

语义分析的核心流程：

  1. 符号表管理：进入新作用域时压栈，退出时弹栈。查找变量时从当前作用域向外层逐级搜索。
  2. 类型推导：对表达式节点，根据子节点的类型推导出父节点的类型。例如，a + b 的类型取决于 a 和 b 的类型及运算符重载规则。
  3. 类型检查：验证操作数类型是否满足运算符要求。例如，取地址运算符 & 要求操作数是左值。
  4. 隐式转换：当类型不匹配但可转换时，插入转换节点（如 int 提升为 long）。

案例拆解：类型不匹配的检测

考虑以下代码：

int foo() { return "hello"; }

Clang 的 Sema 在解析 return "hello"; 时，会检查返回表达式类型（const char[6]）与函数返回类型（int）是否兼容。由于不存在从字符串字面量到 int 的隐式转换，Sema 会报告错误：

error: cannot initialize return object of type 'int' with an lvalue of type 'const char[6]'
风险提示：语义分析是编译器中最容易产生“误报”和“漏报”的阶段。例如，C++ 的模板实例化、重载决议和 ADL（参数依赖查找）极其复杂，Sema 的实现需要处理大量边界情况。LLVM 社区持续在改进 Sema 的准确性和诊断质量。

常见误区

  • 作用域泄漏：忘记在退出作用域时清理符号表，导致变量被错误地访问。
  • 类型等价性：结构体类型是“结构等价”还是“名称等价”？C 语言使用名称等价，而某些语言使用结构等价。
  • 延迟检查：某些语义检查（如模板实例化）需要延迟到实例化时进行，不能在前端立即完成。

2.4 中间表示：LLVM IR 的设计与生成

核心原理

中间表示（Intermediate Representation, IR）是编译器前端和后端之间的桥梁。LLVM IR 是一种静态单赋值（SSA）形式的低级别语言，具有以下特点：

  • 三地址码：每条指令最多有一个运算符和三个操作数（两个源、一个目标）。
  • 无限寄存器：SSA 形式下，每个变量只被赋值一次，因此不需要考虑寄存器数量限制。
  • 显式类型：每个值都有明确的类型（如 i32、float、ptr）。
  • 内存操作显式化：加载（load）和存储（store）指令明确区分内存访问和寄存器操作。

LLVM IR 有三种表示形式：内存中的数据结构（llvm::Module、llvm::Function、llvm::BasicBlock）、文本形式（.ll 文件）和二进制位码（.bc 文件）。三种形式可以互相转换。

判断方法与操作流程

从 AST 生成 LLVM IR 的过程称为 IR CodeGen，在 Clang 中由 CodeGen 模块完成（clang/lib/CodeGen）。核心流程：

  1. 类型映射：将 Clang 类型（如 int）映射为 LLVM 类型（i32）。
  2. 函数生成：为每个函数创建 llvm::Function，并生成入口基本块。
  3. 语句翻译：遍历 AST 语句，生成对应的 IR 指令。例如，return x + 1; 会生成 add 指令和 ret 指令。
  4. SSA 构建：通过 llvm::IRBuilder 自动处理 SSA 形式，插入 phi 节点（如有必要）。

案例拆解：C 代码到 LLVM IR

考虑以下 C 函数：

int add(int a, int b) {
  return a + b;
}

生成的 LLVM IR（文本形式）为：

define i32 @add(i32 %a, i32 %b) {
entry:
  %add = add i32 %a, %b
  ret i32 %add
}

可以看到，a + b 被翻译为 add i32 %a, %b，结果存储在虚拟寄存器 %add 中，然后通过 ret 返回。

LLVM 优势：IR 是平台无关的，因此同一份 IR 可以用于 x86、ARM、RISC-V 等多个后端。此外，IR 上的优化（Pass）可以复用，无需为每种语言单独编写优化器。

常见误区

  • 混淆 IR 与机器码：IR 不是机器码，它不包含寄存器分配、指令选择等后端信息。
  • 忽略 SSA 约束：手动构建 IR 时，必须遵守 SSA 规则——每个虚拟寄存器只能赋值一次。如果需要更新值，必须创建新的虚拟寄存器。
  • 内存操作过度：初学者倾向于将所有变量都放在内存中（通过 alloca），但优化器更擅长处理寄存器值。应尽量使用 SSA 值，减少内存访问。

2.5 优化：LLVM Pass 管线

核心原理

优化阶段对 IR 进行一系列等价变换，以提高程序运行效率或减小代码体积。LLVM 的优化器由多个 Pass 组成，每个 Pass 执行一种特定的优化。Pass 分为两类：函数内 Pass（如指令合并、死代码消除）和模块级 Pass（如内联、全局常量传播）。

LLVM 的优化管线通过 opt 工具或 PassBuilder 配置。常用的优化级别包括 -O0（无优化）、-O1（基本优化）、-O2（推荐优化）、-O3（激进优化）和 -Os（优化代码大小）。

判断方法与操作流程

一个典型的优化 Pass 执行流程：

  1. 收集分析结果：运行分析 Pass（如 DominatorTreeAnalysis、LoopInfo），获取程序的控制流和数据流信息。
  2. 识别优化机会：遍历 IR，寻找可优化的模式。例如，add i32 %x, 0 可以简化为 %x。
  3. 执行变换：修改 IR 结构，删除冗余指令、合并基本块、替换常量等。
  4. 验证正确性：LLVM 提供 verify 工具检查 IR 的一致性（如 SSA 约束、类型正确性）。

案例拆解：常量折叠与死代码消除

考虑以下 IR：

define i32 @test() {
  %1 = add i32 2, 3
  %2 = mul i32 %1, 4
  %3 = sub i32 %2, 1
  ret i32 %3
}

经过 -O2 优化后，所有指令都是常量表达式，优化器会直接计算出结果：

define i32 @test() {
  ret i32 19
}

如果 %3 的结果未被使用，死代码消除 Pass 会将其删除。

实战建议：在 LLVM 开发中，使用 opt -passes='print<domtree>' 可以查看支配树信息，帮助理解优化 Pass 的行为。调试自定义 Pass 时，建议先用 -print-after-all 查看每个 Pass 执行后的 IR 变化。

常见误区

  • 过度优化：-O3 并不总是比 -O2 快，因为激进的内联和向量化可能增加代码体积，导致指令缓存命中率下降。
  • 忽略浮点语义：浮点运算不满足结合律，(a+b)+c 不等于 a+(b+c)。优化器默认不进行浮点重关联，除非指定 -ffast-math。
  • Pass 顺序依赖：某些 Pass 需要先运行其他 Pass 才能生效。例如，GVN（全局值编号）依赖于支配树分析。

2.6 代码生成：从 IR 到机器码

核心原理

代码生成（CodeGen）是编译器的最后一个阶段，将优化后的 IR 转换为目标平台的汇编代码或机器码。LLVM 后端的主要子阶段包括：

  1. 指令选择（Instruction Selection）：将 IR 指令映射为目标机器的指令。LLVM 使用 SelectionDAG 或 GlobalISel 两种框架。
  2. 指令调度（Scheduling）：重排指令顺序，以利用 CPU 的流水线并行性。
  3. 寄存器分配（Register Allocation）：将无限虚拟寄存器映射到有限的物理寄存器，必要时插入溢出（Spill）代码。
  4. 指令输出（Emission）：生成汇编文本或二进制目标文件。

判断方法与操作流程

以 SelectionDAG 为例，指令选择流程：

  1. 构建 DAG：将基本块转换为有向无环图（DAG），节点表示操作，边表示数据依赖。
  2. 模式匹配：通过 TableGen 生成的匹配器，将 DAG 节点组合为目标指令。例如，add i32 在 x86 上可能匹配 ADD32rr 指令。
  3. 合法化（Legalization）：将不支持的类型或操作转换为目标支持的形式。例如，64 位加法在 32 位平台上需要拆分为多条指令。
  4. 优化 DAG：在 DAG 层面
    ← 上一章 📖 返回目录 下一章 →