编译原理

引论

语言处理器

语言处理器是将一种语言编写的程序转换为另一种形式的工具，主要包括：

• 编译器：将高级语言源程序一次性翻译为目标代码（如机器码、汇编代码），常见于 C/C++等静态语言。
• 解释器：逐条读取、分析并执行源程序，不生成独立目标代码，常见于 Python、JavaScript 等动态语言。
• 汇编器：将汇编语言翻译为机器指令。
• 其他相关工具：如虚拟机、链接器、装载器等。

补充说明与例子：

• 编译器常见工作流：源代码 -> 预处理 -> 编译为汇编 -> 汇编为目标文件 -> 链接为可执行文件/库。
• 交叉编译：在平台 A 为平台 B 生成可执行文件，如在 x86_64 上为 ARM 生成二进制（Clang/LLVM 的 --target）。
• JVM/CLR 等虚拟机体系：源代码 -> 字节码（IR）-> 解释执行/即时编译（JIT）-> 机器码。典型的热点探测与内联缓存优化策略。

常见混合实现：

• Python：解释器 + JIT（PyPy）、C 扩展模块。
• JavaScript 引擎（V8）：解释器（Ignition）+ JIT（TurboFan）+ 隐式类（Hidden Class）与内联缓存（IC）。
• Java：CLASS 字节码 + C1/C2 分层 JIT + AOT（GraalVM Native Image）。

编译器结构与主要阶段

编译器通常分为前端和后端：

• 前端：负责源代码的分析，包括词法分析、语法分析、语义分析，生成中间表示。
• 后端：对中间表示进行优化，生成目标代码。

主要阶段如下：

• 词法分析：将字符流分割成有意义的单元（记号/Token），如关键字、标识符、常量、运算符。常用自动机理论实现，典型工具有 lex/flex。
• 语法分析：根据上下文无关文法将记号序列构造成语法树或抽象语法树，检查结构合法性。常用自顶向下（递归下降、LL）和自底向上（LR、LALR）分析方法。
• 语义分析：在语法树基础上进行类型检查、作用域检查、名称绑定等，保证程序语义正确。常用符号表管理变量、函数等信息。
• 中间代码生成：将语法树转换为中间表示，如三地址码、四元式、静态单赋值等，便于后续优化和跨平台。
• 代码优化：对中间代码进行等价变换，提高效率或减少资源消耗。包括局部优化（如常量合并、死代码消除）、全局优化（如循环优化、内联展开）等。
• 代码生成：将优化后的中间代码翻译为目标机器代码或汇编代码，涉及寄存器分配、指令选择、指令调度等。
• 符号表管理：符号表用于记录变量、函数、类型等符号的属性信息，支持作用域嵌套、类型检查、重定义检测等。
• 多趟编译：复杂编译器常将编译过程分为多趟，每一趟处理特定任务，如先分析结构再优化代码，便于分阶段处理和调试。
• 编译器构造工具：如 lex/flex、yacc/bison 等自动生成分析器代码，提高开发效率。

典型例题方向与示范：

• 给定正则表达式，构造 NFA、DFA 并最小化；据此识别词法单元。
• 给定文法，计算 FIRST/FOLLOW 集；判断 LL(1) 条件；构建预测分析表。
• 构造 LR(0)/SLR(1)/LR(1)/LALR(1) 项目集族、ACTION/GOTO 表；模拟移进-归约。
• 编写 SDD/SDT 生成后缀式或三地址码；布尔表达式短路求值与回填。
• 控制流图、基本块划分、活跃变量分析、可达定义、CSE、循环不变外提与强度削弱。
• 寄存器分配：干涉图构造、图着色、溢出处理。
• 指令选择/调度：树匹配、依赖图、列表调度、循环展开与向量化可行性。

相关背景与应用

• 程序设计语言的发展历程：早期为机器语言，后有汇编语言，再到 FORTRAN、COBOL 等高级语言。高级语言更接近人类思维，支持抽象、结构化、模块化、面向对象等特性，极大提升了开发效率和程序可维护性。语言特性的丰富推动了编译技术的不断进步。
• 编译器相关科学：涉及形式语言与自动机、算法与数据结构、计算机体系结构、程序分析与优化理论等。
• 编译技术的应用：不仅用于高级语言实现，还广泛应用于不同硬件平台优化、新体系结构设计、源到源翻译、跨平台移植、静态分析、自动化重构、代码生成等。

补充：

• 源到源翻译（Transpiler）：如 TypeScript->JS，Babel，Clang-Tidy/Clang-Format 的重写。
• 静态分析：类型推断、空指针、越界、未初始化、内存泄漏（如 Clang Static Analyzer）。
• 领域特定语言（DSL）：SQL、正则、着色器语言（GLSL/HLSL），常借助编译技术实现解释与优化。

程序设计语言基础

• 静态与动态属性：静态属性在编译时确定，如类型、作用域、变量声明等；动态属性在运行时确定，如动态类型绑定、动态作用域等。
• 环境与状态：环境是变量名到存储位置的映射，状态是存储位置到实际值的映射。
• 静态作用域和块结构：静态作用域在编译时确定，支持嵌套作用域和块结构，便于局部变量管理。
• 显式访问控制：通过 public、private 等关键字控制变量/函数的可见性。
• 动态作用域：作用域在运行时根据调用链动态确定，部分脚本语言支持。
• 参数传递机制：包括值传递、引用传递、名称传递等，不同机制影响函数调用时变量的行为。
• 别名：多个名字引用同一存储位置，可能导致副作用和优化困难。

例子与推演：

• 静态作用域示例（C 风格）：

  int x = 1;
  void f() { int x = 2; void g(); g(); } // g 看到全局 x=1（静态作用域）
  void g() { printf("%d\n", x); }

• 动态作用域示例（伪代码）：

  x = 1
  def f():
    x = 2
    g()
  def g():
    print(x) # 动态作用域下输出 2；静态作用域输出 1
  f()

• 名称传递（call-by-name，Algol68 风格）可模拟为使用 thunk：

  // 传递 i++ 作为参数时，每次取值都会递增

对优化的影响：

• 别名阻碍优化：指针可能指向相同存储，编译器保守处理，限制寄存器缓存与重排序。
• 纯函数与无副作用便于 CSE、代码移动、并行化。

一个简单的语法制导翻译器

语法定义

**文法（Grammar）**用产生式规则描述语言结构。形式为 $A \to \alpha$，$A$ 为非终结符，$\alpha$ 为终结符和非终结符串。

**推导（Derivation）**是从开始符号出发，反复应用产生式，直到得到只含终结符的符号串。

**语法分析树（Parse Tree）**反映推导过程的树形结构，根为开始符号，叶为终结符。

**二义性（Ambiguity）**指同一符号串有多棵语法树。二义性会导致语义不确定，需通过调整文法、结合性和优先级消除。

运算符结合性与优先级：结合性决定运算符的结合方向（如加法左结合），优先级决定运算符的运算顺序。

典型例子：

• 经典表达式二义文法：

  E -> E + E | E * E | ( E ) | id

  对 id + id * id 既可解析为 (id + id) * id 也可解析为 id + (id * id)。

• 通过引入层级与结合性消解：

  E  -> E + T | T
  T  -> T * F | F
  F  -> ( E ) | id

  加法低于乘法，两个产生式左递归表达左结合。

• 替代方法：运算符优先级表与结合性声明（yacc/bison）：

  %left '+' '-'
  %left '*' '/'
  %right '^'

语法制导翻译（SDT/SDD）

在文法规则中嵌入语义动作，通过属性值传递实现语法制导翻译。

• 综合属性（Synthesized Attribute）：属性值由子节点综合而来，常用于自底向上的分析。
• 继承属性（Inherited Attribute）：属性值由父节点或兄弟节点传递，常用于自顶向下的分析。

后缀表示（逆波兰表示法）：将中缀表达式转换为后缀表达式，便于无括号计算。

树的遍历：属性计算顺序依赖于语法树的遍历方式（如自底向上、深度优先等）。

例：生成后缀式的 S 属性定义（仅综合属性）

E -> E + T   { E.out = E1.out || T.out || '+' }
E -> T       { E.out = T.out }
T -> T * F   { T.out = T1.out || F.out || '*' }
T -> F       { T.out = F.out }
F -> ( E )   { F.out = E.out }
F -> id      { F.out = id.lexeme }

若采用 LR 分析，可将语义动作放在产生式尾部；LL 分析可返回字符串。

例：带继承属性的宽度控制（如生成对齐空间）：

L -> L S     { S.indent = L.indent }
L -> S       { S.indent = L.indent }
S -> if (E) S1 else S2 { ... } // 子句继承缩进层级

短路求值 SDT（回填见后）：

E -> E1 || M E2
   { E1.true + E2.true -> E.true; E1.false -> M.next; E.false = E2.false }
E -> E1 && M E2
   { E1.false + E2.false -> E.false; E1.true -> M.next; E.true = E2.true }
E -> !E1 { swap(E1.true, E1.false) }
E -> id relop id
   { emit('if a relop b goto _'); E.true = [instr]; emit('goto _'); E.false=[instr] }
M -> { M.next = nextinstr }

语法分析

自顶向下分析：从文法开始符号出发，递归分析输入串。常见方法有递归下降分析、预测分析（LL 分析）。

预测分析法：利用 lookahead 符号预测产生式，构建预测分析表（如 LL(1)分析表），实现自动分析。

左递归：文法左递归会导致自顶向下分析无限递归，需通过改写文法消除。

系统步骤与例子：

1. 消除直接左递归：
   • A -> A α | β 变换为 A -> β A’，A’ -> α A’ | ε
2. 消除间接左递归：按非终结符顺序替换前驱产生式后再消除直接左递归。
3. 左因子提取：A -> αβ1 | αβ2 | … => A -> α A’，A’ -> β1 | β2 | …

FIRST/FOLLOW 计算例：

E -> T E'
E'-> + T E' | ε
T -> F T'
T'-> * F T' | ε
F -> ( E ) | id

• FIRST(F) = {(, id}
• FIRST(T) = {(, id}
• FIRST(E) = {(, id}
• FIRST(T’) = {*, ε}
• FIRST(E’) = {+, ε}
• FOLLOW(E) = {), $}
• FOLLOW(E’) = {), $}
• FOLLOW(T) = {+, ), $}
• FOLLOW(T’) = {+, ), $} 构造 LL(1) 表据此填入 M[A,a]。

递归下降过程示意：

• 对于 E -> T E’：调用 T() 后调用 E’()，E’ 依据 lookahead 选择 + T E’ 或 ε。

LL(1) 判定条件：

• 对任意 A -> αi, αj，FIRST(αi) ∩ FIRST(αj) = ∅
• 若 ε ∈ FIRST(αi)，则 FIRST(αj) ∩ FOLLOW(A) = ∅

简单表达式的翻译器

抽象语法（AST）：忽略具体语法细节，仅保留表达式结构，便于后续处理。

具体语法：包括所有语法细节，如括号、分号等。

翻译方案调整：通过调整语法制导定义，优化属性传递和语义动作，简化实现。

非终结符过程：每个非终结符对应一个分析过程，递归调用实现语法分析和翻译。

简化实现：通过合并规则、消除冗余，简化语法和语义动作，便于实现完整表达式翻译器。

示例：表达式到三地址码（引入新临时变量 newtemp）

E -> E1 + T   { t = newtemp(); emit(t = E1.place + T.place); E.place = t; }
E -> T        { E.place = T.place }
T -> T1 * F   { t = newtemp(); emit(t = T1.place * F.place); T.place = t; }
T -> F        { T.place = F.place }
F -> (E)      { F.place = E.place }
F -> id       { F.place = id.lexeme }
F -> num      { F.place = num.value }

对输入 id + id * num，输出：

t1 = id2 * 3
t2 = id1 + t1

词法分析

剔除空白和注释：词法分析器需忽略空白字符和注释，保证分析准确。

预读（Lookahead）：通过预读字符判断记号类型，支持多字符记号识别。

常量识别：支持整数、浮点数、字符串等常量的识别。

关键字与标识符识别：区分保留字和用户自定义标识符，通常通过查表实现。

词法分析器实现：可手写有限自动机，也可用工具（如 lex）自动生成。

正则与自动机构造关键步骤：

• 正则 -> NFA（Thompson 构造）
• NFA -> DFA（子集构造）
• DFA 最小化（Hopcroft 算法）

示例：整数与标识符

• 正则：digit = [0-9], letter = [A-Za-z_]
  • int: digit digit*
  • id: letter (letter|digit)*
• 关键字处理：将关键字插入保留字表；匹配 id 后查保留字表决定记号种类。

flex 简例：

%{
#include "y.tab.h"
%}
%%
[ \t\r\n]+          ;
"//".*              ;
"/*"([^*]|\*+[^*/])*\*+"/"   ;
"if"                return IF;
"else"              return ELSE;
[0-9]+              { yylval.ival = atoi(yytext); return NUM; }
[A-Za-z_][A-Za-z0-9_]* { yylval.sval = strdup(yytext); return ID; }
"=="| "!="| "<="| ">="| "<"| ">"  { yylval.op = yytext[0]; return RELOP; }
"+"|"-"|"*"|"/"     return yytext[0];
"(" | ")" | ";"     return yytext[0];
.                   /* error token */
%%

常见细节：

• 最长匹配原则：DFA 会自然实现最长前缀匹配。
• 回退处理：若模式共享前缀，DFA 可避免回退；NFA 直扫需支持回退。
• 多行字符串/注释：注意贪婪匹配与转义处理。
• UTF-8 标识符：按字节还是代码点识别需明确。

符号表

作用域管理：为每个作用域设置独立符号表，支持嵌套作用域和作用域链。

符号表操作：包括插入新符号、查找已有符号、删除符号等，常用哈希表或链表实现。

层次结构：

• 使用栈维护作用域：进入块 push 新表，退出块 pop。
• 查找（静态作用域）：从栈顶向下查找第一个命中表。

记录内容：

• 名称、种类（变量、函数、类型、标签）、类型（含数组/指针/函数签名）、存储类（static、extern）、偏移、是否常量、可见性、生命周期信息。

示意代码：

typedef struct Symbol { char* name; Type* type; int offset; ... } Symbol;
typedef struct Scope  { HashMap* table; struct Scope* parent; } Scope;

Symbol* lookup(Scope* s, const char* name) {
  for (; s; s = s->parent) {
    Symbol* x = map_get(s->table, name);
    if (x) return x;
  }
  return NULL;
}
void insert(Scope* s, Symbol* sym) { map_put(s->table, sym->name, sym); }

重定义与屏蔽：

• 同一作用域重定义需报错；内层允许屏蔽外层同名标识符。

语法制导的翻译

语法制导定义

语法制导定义（SDD）在文法产生式基础上附加属性和语义规则，实现语法与语义的结合。属性分为综合属性和继承属性，语义规则描述属性如何计算。

• 综合属性：由子节点计算结果综合而来，适合自底向上分析。
• 继承属性：由父节点或兄弟节点传递，适合自顶向下分析。
• 属性值可为类型、值、代码片段、符号表信息等。

类型检查 SDD 示例（算术表达式）：

E -> E + T   { if (E.type == T.type == int) E.type=int; else error; }
E -> T       { E.type = T.type }
T -> F       { T.type = F.type }
F -> (E)     { F.type = E.type }
F -> id      { F.type = id.type } // 查符号表
F -> num     { F.type = int }

属性求值顺序

属性之间可能存在依赖关系。依赖图用于描述属性之间的依赖，求值顺序需满足依赖关系。

• S-属性定义：仅含综合属性，属性值可自底向上递归计算。
• L-属性定义：继承属性的依赖仅限于左侧兄弟和父节点，适合自顶向下递归分析。
• 属性求值顺序可通过拓扑排序确定。

依赖图构造：

• 节点：每个属性（如 E1.type）
• 边：从被依赖属性指向依赖该属性的属性
• 无环则存在合法求值顺序；有环说明定义不良（如循环依赖）。

例：列表打印缩进（L-属性）

S -> L      { L.indent = 0 }
L -> L Item { Item.indent = L.indent }
L -> Item   { Item.indent = L.indent }
Item -> stmt { print_with_indent(stmt, Item.indent) }

语法制导翻译的应用

• 抽象语法树构造：通过属性和语义动作生成 AST，便于后续优化和代码生成。
• 类型检查：属性记录类型信息，语义规则实现类型推断和检查。
• 中间代码生成：在语法分析过程中嵌入代码生成动作，直接输出中间代码。

AST 构造例（C 风格表达式）：

E -> E + T { E.node = mkBin('+', E1.node, T.node) }
E -> T     { E.node = T.node }
T -> F     { T.node = F.node }
F -> id    { F.node = mkId(id.lexeme) }
F -> num   { F.node = mkNum(num.value) }

语法制导翻译方案

• 后缀翻译方案：将语义动作放在产生式右部末尾，适合自底向上分析。
• 前缀/中缀方案：语义动作可插入产生式任意位置，灵活实现属性传递。
• 消除左递归：左递归文法不利于自顶向下分析，需改写为右递归或使用特殊处理。

布尔表达式与控制流的回填（回跳链表 backpatch）：

• 结构：
  • 表达式属性：trueList, falseList（待回填的跳转目标）
  • 语句属性：nextList（语句后继待回填）
• 基本动作：
  • makelist(i)：创建包含 i 的列表
  • merge(p, q)：连接两个列表
  • backpatch(p, i)：将列表 p 中每条跳转的目标回填为 i

例：if (E) S1 else S2

E.true -> backpatch to S1.start
E.false -> backpatch to S2.start
S1.next + S2.next -> S.next

实现 L-属性 SDD

• 在递归下降分析过程中传递继承属性，边分析边生成代码。
• LL 分析器适合实现 L-属性定义，LR 分析器适合 S-属性定义。
• 属性值可通过参数、返回值或全局结构传递.

伪代码例：递归下降 + 继承属性

void E(out Place p) {
  Place t; T(t); E_(t, p);
}
void E_(in Place inh, out Place syn) {
  if (lookahead == '+') {
    match('+'); Place t; T(t);
    Place r = newtemp(); emit(r = inh + t);
    E_(r, syn);
  } else { syn = inh; }
}

中间代码生成

中间代码的作用

中间代码（IR）是源代码与目标代码之间的桥梁，便于优化和跨平台。常见形式有三地址码、四元式、静态单赋值（SSA）等。

• 三地址码：每条指令最多包含三个操作数，结构简单，便于分析和优化。
• 四元式：用四元组表示操作、两个操作数和结果。
• 静态单赋值：每个变量只赋值一次，便于数据流分析。

三地址码表示形式：

• 赋值：x = y op z
• 一元：x = op y
• 赋值拷贝：x = y
• 数组访问：x = y[i], a[i] = x
• 取址/间接：x = *y, *x = y
• 条件跳转：if x relop y goto L
• 无条件跳转：goto L
• 函数：param x; call f, n; t = call f; return x

四元式与三元式：

• 四元式：(op, arg1, arg2, result)
• 三元式：使用指令编号作为临时值引用，减少 result 字段。

语法树与中间代码

• 语法树：表达式和语句结构的树形表示，节点类型包括操作符、常量、变量等。
• 从语法树生成中间代码：遍历语法树，递归生成三地址码或四元式。

例：((a + b) * (c - d)) + e

• 后缀：a b + c d - * e +
• 三地址码：

  t1 = a + b
  t2 = c - d
  t3 = t1 * t2
  t4 = t3 + e

表达式求值顺序与临时变量最少策略：

• 自底向上生成，使用 Sethi-Ullman 编号估计寄存器需求，决定左右子树顺序。
• 编号规则：叶子编号 1；节点编号 = max(左, 右)+[左==右]。大编号子树先生成。

控制流结构的中间代码

• 条件语句：生成条件跳转指令，使用标签表示分支目标。
• 循环结构：生成循环入口、条件判断、循环体和跳转指令。
• 函数调用：处理中间代码中的参数传递、返回值、调用和返回。

if-else 模板（短路求值 + 回填）：

E.true -> L1; E.false -> L2
L1: S1
    goto L3
L2: S2
L3:

while 模板：

Lbegin:
  // 布尔表达式 E 短路，E.true -> Lbody, E.false -> Lafter
Lbody:
  S
  goto Lbegin
Lafter:

for (init; cond; step) S 转换为：

init
Ltest: // cond 短路
  if cond goto Lbody
  goto Lafter
Lbody:
  S
  step
  goto Ltest
Lafter:

短路布尔表达式：

• 生成条件跳转而不是显式布尔值，避免额外临时。

临时变量与寄存器分配

• 中间代码生成过程中引入临时变量，便于表达复杂计算。
• 后续阶段需将临时变量映射到实际寄存器或内存位置。

基本策略：

• 局部寄存器分配（基本块内）：自顶向下扫描活跃性，使用栈式寄存器分配。
• 全局寄存器分配：构建干涉图，图着色；溢出则插入 spill/load 指令，迭代直到可着色。

示例（干涉图构造）：

语句顺序及liveOut集：
1: t1 = a + b     liveOut={c,d,e}
2: t2 = c - d     liveOut={t1,e}
3: t3 = t1 * t2   liveOut={e}
4: t4 = t3 + e    liveOut={}

干涉：变量在同一 live 区间互相干涉。构图后尝试 K-着色（K=寄存器数量）。

中间代码优化

• 局部优化：如常量合并、公共子表达式消除、死代码删除。
• 全局优化：如循环不变代码外提、内联展开、数据流分析。

局部优化示例（基本块内）：

• 常量折叠：t = 2*3 -> t = 6
• 强度削弱：x = y * 2^k -> x = y << k
• 消除冗余：x = y; z = x -> z = y；若 x 后不再使用可删除赋值
• 代价模型：多用寄存器少用内存，合并相邻加载/存储。

循环优化示例：

• 循环不变外提：

  for i: t = a*b; x[i] = t + i
  => preheader: t = a*b
     loop: x[i] = t + i

• 强度削弱（指数、乘法 -> 加法、移位）：

  for i: x = i*8 => x = i << 3

• 归纳变量简化：i = i + c；可用计数器替换复杂表达式。
• 循环展开：增加每次迭代的工作以降低分支开销并暴露 ILP。

运行时刻环境

运行时环境的组成

运行时环境为程序执行提供必要的支持，包括内存分配、函数调用、变量存储等。

• 存储管理：管理全局变量、局部变量、堆和栈空间。
• 栈帧结构：每次函数调用分配新的栈帧，保存参数、返回地址、局部变量等。
• 作用域与可见性：支持静态作用域和动态作用域的变量查找。

典型栈帧布局（x86-64 System V，可能因编译器不同略有差异）：

• 高地址向低地址增长：
  • 参数入栈（寄存器溢出部分）
  • 返回地址
  • 旧帧指针（RBP）
  • 保存的被调用者保存寄存器（rbx, r12-r15）
  • 局部变量区（对齐）
  • 临时溢出区（spill slots）
• 调用约定：前六整型参数用寄存器（rdi, rsi, rdx, rcx, r8, r9），返回值 rax；浮点使用 xmm0-7。

RISC-V LP64 约定简述：

• 参数 a0-a7，返回 a0-a1；被调用者保存 s0-s11；调用者保存 t0-t6。

参数传递与返回值

• 值传递：将实参值复制到形参。
• 引用传递：传递变量地址，实现共享。
• 名称传递：传递表达式或变量名，按需求值。

调用序列：

• 调用者：实参准备 -> 调用保存 -> call -> 调用后清理（按约定）
• 被调用者：保存旧帧指针 -> 建立新帧 -> 保存被调保存寄存器 -> 分配局部 -> 返回前恢复。

变长参数（C 的 stdarg）：

• 固定参数通过寄存器/栈传递，额外参数通过栈；va_list 记录参数区指针与剩余计数。

动态内存分配

• 堆管理：动态分配和释放内存，常用 malloc/free、new/delete 等机制。
• 垃圾回收：自动回收不再使用的内存，常见于高级语言运行时。

GC 基础：

• 标记-清扫（Mark-Sweep）：从根集可达对象标记，未标记对象回收；碎片化问题。
• 复制回收（Copying）：两半区复制存活对象，紧凑无碎片；适合新生代。
• 分代收集（Generational）：新生代复制 + 老年代标记整理；跨代记忆集与写屏障。
• 引用计数：实时回收不可达对象，但环无法处理，需配弱引用/周期检测。

异常处理与控制流

• 支持异常捕获、抛出和处理，维护异常表和控制流跳转。
• 支持协程、生成器等高级控制流结构。

异常实现：

• 栈展开（stack unwinding）：查找匹配的 catch 块，沿调用栈回退，调用析构/清理。
• 映射表法（零开销异常）：正常路径无开销，抛出时依据 PC 查表展开。

协程/生成器：

• 将函数状态（PC、局部变量）封装为帧对象；yield/suspend 恢复点；
• CPS（Continuation-Passing Style）或状态机转换实现。

运行时类型信息

• 记录类型信息，支持动态类型检查、反射等特性。

实现手段：

• 每对象隐藏头部：指向类元数据（方法表、字段表、RTTI）、GC 标志。
• vtable：虚方法调用通过 vptr 间接跳转。
• 动态语言字典：对象属性表、形状（Hidden Class）优化。

代码生成

目标代码生成的任务

代码生成器将中间代码翻译为目标机器代码或汇编代码，需考虑指令集、寄存器分配、内存布局等。

• 指令选择：将中间代码映射为具体机器指令，选择高效指令序列。
• 寄存器分配：将变量和临时量分配到有限的物理寄存器，溢出时使用内存。
• 指令调度：调整指令顺序，减少流水线冲突，提高并行度。

树覆盖（Pattern Matching）：

• 使用目标机指令模式（树）覆盖 IR 表达式树，选择最小代价覆盖（如 IBURG）。
• 例：x = y + 1 在 x86 可选择 lea 指令代替 add 以减少依赖。

延迟槽（某些 RISC）：分支延迟槽可填入对其安全的指令（或 NOP）。

地址与内存管理

• 变量分配：全局变量、局部变量、静态变量分配到不同内存区域。
• 数组与结构体访问：计算偏移量，生成相应的加载和存储指令。
• 函数调用约定：参数传递、返回值、调用保存、栈帧管理等。

数组寻址：

• a[i] 的地址 = base(a) + i * sizeof(elem)
• 多维数组（行主序）：a[i][j] = base + ((i*col) + j)*elem_size

结构体：

• 字段偏移由对齐规则决定；通过 base + offset 访问。

示例（x86-64）：

mov rax, [rbp-8]     ; load i
lea rcx, [rax*8]     ; i * 8
add rcx, [rbp-32]    ; base + i*8
mov rdx, [rcx]       ; load a[i]

目标代码优化

• 消除冗余指令、合并相邻操作、利用特殊指令提升性能。
• 针对特定硬件特性进行优化，如 SIMD、流水线、缓存友好等。

常见例：

• 强化寻址模式：x86 的 lea 合并加法与乘法
• 条件移动（cmov）减少分支预测失败
• 位操作代替乘除以常数：乘以 10 => (x<<3) + (x<<1)
• 矢量化：将标量循环用 SSE/AVX/RVV 指令成组处理

目标文件生成

• 生成可重定位目标文件，包含代码段、数据段、符号表等。
• 支持链接器和装载器进行后续处理，生成可执行文件。

概念：

• 段：.text, .data, .bss, .rodata
• 符号：全局符号、弱符号、重定位项
• 重定位：链接时修正地址（R_X86_64_PC32 等）

机器无关优化

优化目标与原则

机器无关优化关注于提升中间代码的执行效率，不依赖具体硬件结构。优化目标包括减少指令数、降低内存访问、提升并行度、减少分支等。

• 等价变换：保证优化前后程序语义一致。
• 局部与全局优化：局部优化作用于基本块内，全局优化跨越多个基本块或整个函数。

基本块与流图：

• 基本块：无分支进入点（除首条），无分支中断（除末条）；入口只有第一条，出口只有最后一条。
• 划分：以 leaders 开始（第一条、跳转目标、跳转后继），直到下一个 leader 前的连续序列。
• CFG：结点为基本块，边为控制流可能性（分支/顺序）。

常见优化技术

• 公共子表达式消除（CSE）：识别并消除重复计算的表达式。
• 常量传播与折叠：将常量值在程序中传播，提前计算常量表达式。
• 死代码消除：移除不会影响程序结果的代码。
• 复制传播：用变量的实际值替换对其的引用，简化表达式。
• 循环优化：包括循环不变代码外提、强度削弱、循环展开等。
• 内联展开：将小函数体直接插入调用点，减少函数调用开销。
• 代码移动：将无副作用的代码移动到执行频率更低的位置。

示例：可用表达式分析 + CSE

• 可用表达式：到达某点的所有路径上表达式 e 都已计算且自上次计算后其操作数未被修改
• 数据流方程（前向、交汇为交集）：

  IN[B]  = ∩_{P∈pred(B)} OUT[P]
  OUT[B] = gen[B] ∪ (IN[B] - kill[B])

• gen/kill：由块内赋值决定；赋值给 x 杀死所有含 x 的表达式。

数据流分析

• 活跃变量分析：确定变量在何处被使用，指导寄存器分配和死代码消除。
• 可达定义分析：追踪变量定义的传播路径。
• 定值传播：分析变量是否为常量，便于常量折叠。

活跃变量（后向问题，交汇为并集）：

OUT[B] = ∪_{S∈succ(B)} IN[S]
IN[B]  = use[B] ∪ (OUT[B] - def[B])

• use：在定义前使用的变量集合
• def：在块内被定义的变量集合

可达定义（前向，交汇为并集）：

• 定义 d 到达 B 的入口若存在某前驱路径未被重定义杀死。
• IN/OUT 类似可用表达式，但对定义流对象集合进行运算。

常量传播（稀疏解法）：

• 基于 SSA，通过“格”传播（常量、非常量、未定义）；Phi 函数合并格值。

SSA 形式与优化

• 静态单赋值（SSA）：每个变量只赋值一次，便于数据流分析和优化。
• Phi 函数：在控制流汇合处合并不同路径的变量值。

构造步骤：

1. 插入 Φ：在支配边界（dominance frontier）位置为变量插入 φ
2. 重命名：沿支配树深度优先遍历，用栈记录每个变量当前版本 v_i

例：

x = 0
if (c) x = 1
y = x

转换：

x0 = 0
if (c) x1 = 1
x2 = phi(x0, x1)
y0 = x2

SSA 上的优化：

• 常量传播：phi(k, k) -> k；phi(k, ⊥) -> k；死 φ 删除
• 冗余消除：GVN（全局值编号）、PRE（部分冗余消除）
• 跨基本块复制传播与死代码消除更简单

从 SSA 恢复：

• 插入并行赋值的拷贝以实现 φ；然后寄存器/内存映射。

指令级并行

并行性基础

指令级并行（ILP）通过同时执行多条指令提升处理器利用率。现代处理器支持流水线、乱序执行、超标量等机制。

• 流水线：将指令分解为多个阶段，多个指令可在不同阶段并行处理。
• 乱序执行：允许指令不按程序顺序执行，只要数据依赖得到满足。
• 超标量：每周期可发射多条指令到不同执行单元。

并行性分析

• 数据相关性：包括数据依赖（RAW）、反相关（WAR）、输出相关（WAW），影响指令能否并行。
• 调度与重排序：编译器可调整指令顺序，减少依赖冲突和流水线停顿。
• 寄存器重命名：消除伪相关（WAR/WAW），提升并行度。

依赖图构造：

• 节点为指令，边表示依赖类型与延迟（latency）
• 列表调度：依据就绪集合与启发式（关键路径长度、资源可用性）选择发射顺序

小例（假设 mul 延迟 3，add 延迟 1）：

1: t1 = a * b
2: t2 = c * d
3: t3 = t1 + t2
4: e  = t3 + f

• 1、2 可并行；3 依赖 1、2；4 依赖 3。
• 调度：周期 0 发 1、2；周期 3 发 3；周期 4 发 4。

编译器支持

• 循环展开：增加循环体内指令数，提升并行度。
• 指令调度：重新排列指令，减少流水线气泡。
• 自动向量化：将标量操作转化为向量操作，利用 SIMD 指令集。

向量化前提：

• 无迭代间真实依赖（RAW）；可通过依赖测试（GCD、Banerjee）判断。
• 内存对齐与步长一致；处理边界余数（remainder loop）。

GCD 测试简例：

• 访问 a[i] 与 a[i+3] 是否可能别名？差为 3，与步长 1 的 GCD 为 1，可能冲突；跨迭代依赖预防向量化。

并行性和局部性的优化

并行性优化

• 任务划分：将程序划分为可独立执行的任务或线程。
• 数据分区：将数据划分为独立块，减少线程间依赖。
• 同步与通信优化：减少锁和同步操作，降低并发开销。

OpenMP 示例：

#pragma omp parallel for schedule(static)
for (int i=0;i<n;i++) C[i] = A[i] + B[i];

注意避免伪共享：相邻线程写入同一缓存线不同元素引发竞争，解决：对齐/填充或按块划分。

局部性优化

• 时间局部性：同一数据多次访问，适合缓存。
• 空间局部性：相邻数据被连续访问，适合预取和缓存行优化。
• 循环交换：调整循环顺序，提升数据访问的局部性。
• 数据布局优化：调整数据结构布局，减少缓存未命中。

循环变换例：

• 交换（loop interchange）：

  for i
    for j
      A[j][i]   // 行主序下差
  =>
  for j
    for i
      A[j][i]   // 连续访问

• 分块/tiling：

  for ii in 0..n step B
    for jj in 0..n step B
      for i in ii..ii+B
        for j in jj..jj+B
          C[i][j] += ...

并行编译技术

• 自动并行化：编译器自动识别可并行代码，插入并行指令或线程。
• OpenMP、CUDA 等支持：为多核和 GPU 编程提供编译器级优化。

CUDA 简要示例：

__global__ void saxpy(float a, float* x, float* y, float* out, int n) {
  int i = blockIdx.x*blockDim.x + threadIdx.x;
  if (i < n) out[i] = a*x[i] + y[i];
}

注意事项：

• 全局内存合并访问（coalescing）
• 共享内存用于块内数据重用
• 避免分支发散

过程间分析

过程间优化的意义

过程间分析（IPA）跨越单个函数或模块，分析和优化整个程序，提高全局性能。

• 跨过程常量传播：在多个函数间传播常量信息。
• 跨过程死代码消除：移除未被调用的函数和无用代码。
• 跨过程内联：将被频繁调用的小函数内联到调用点。

示例：

inline int add1(int x){ return x+1; }
int f(){ return add1(4); } => 5 // 内联 + 常量折叠

依赖分析与调用图

• 调用图：描述函数间调用关系，指导内联和优化顺序。
• 别名分析：分析指针和引用的别名关系，避免错误优化。
• 全局变量分析：追踪全局变量的定义和使用，优化其访问。

调用图构造：

• 节点为函数，边为调用
• 虚调用（C++/Java）需要去虚拟化：类层次分析（CHA）、快速类型分析（RTA）得到可能目标集

别名分析层级：

• 局部别名（栈对象）、全局别名（堆/全局）、场敏感/不敏感、上下文敏感/不敏感
• Andersen（包含式）与 Steensgaard（统一式）近似

链接时优化

• 链接时优化（LTO）：编译器在链接阶段进行全程序优化，消除模块间边界。
• 跨模块内联与优化：提升最终可执行文件的性能。

实现：

• 以 IR（如 LLVM bitcode）为链接单元；链接器驱动优化管线（内联、DCE、CSE、GVN、CFG 简化）。

安全与可维护性

• 安全检查插桩：在过程间插入安全检查代码，防止越界、空指针等错误。
• 可维护性分析：辅助重构、代码分割和模块化。

示例：

• 边界检查插桩与消除：证明索引安全后移除检查。
• 空指针检查移动：将频繁异常路径外提，减少重复检查。