05-IR

• 使用语法制导翻译器生成 IR

  • 语法指导翻译器：在上下文无关文法中，向结果添加一系列动作

• IR 对分析和优化友好

  • 更好的结构、控制流图

  • 更丰富的源代码信息

  • 机器无关的分析

    • 类型推导

    • Bug 检测

    • 代码插桩：在代码中插入额外逻辑

      • 记录行为

      • 避免攻击：如判断数组越界

    • 机器无关优化

      • 死代码消除

      • 常量传播

      • 活动变量分析

      • 向量化

三地址码

• x = y op z

  • op 是操作符

  • x 是结果变量

  • y 和 z 是操作数

• 最多一个op，三个地址/变量

基本格式

计算/赋值指令

指令类型	指令形式	例子
算术运算	x = y op z x = op y	x = y + z x = -y
逻辑运算	x = y op z x = op y	x = y && z x = !y
关系运算	x = y op z	x = y < z
赋值	x = y

控制指令

指令类型	指令形式	其他形式
无条件跳转	goto L
条件跳转	if x goto L else goto L'	if x goto L，如果不满足就继续执行后续语句
条件跳转	if x op y goto L else goto L'	if x op y goto L，如果不满足就继续执行后续语句

• 注：严格来说带计算的条件跳转应该是z = x op y，if z goto L，但是可以写成上面的简化形式

内存操作

指令类型	指令形式	其他形式
取地址	x = &y
Load	x = *y
Store	*x = y
索引	x = y[z] y[z] = x	t = y + z，x = *t t = y + z，*t = x

• 三地址码中的索引无需考虑数据的大小，下一项直接将index加 1 即可

函数调用返回

指令类型	指令形式	其他形式
函数调用	param p1 param p2 ... param pn call func n
函数返回	return x return

使用四元组的形式表示三地址码

原代码	op	arg1	arg2	result
x = y + z	+	y	z	x
x = y	=	y		x
x = -y	-	y		x

使用三元组的形式表示三地址码

• 省略result，使用行号代表结果作为后续指令的arg1或arg2

• 三元组能和语法树自底向上地对应起来

行号	源代码	op	arg1	arg2
0	t0 = -c	-	c
1	t1 = t0 + b	+	(0)	b
2	t2 = -c	-	c
3	t3 = t2 + b	+	(2)	b
4	t4 = t1 + t3	+	(1)	(3)
5	a = t4	=	a	(4)

优化：Syndax DAG

• Direct Acyclic Graph 有向无环图

• 把冗余的节点合并，减少重复运算

语法指导翻译 Syntax-Directed Translation

• SDD = 上下文无关文法 + 属性 + 语义规则

• 属性：附加在语法树节点上，用以描述语法结构的语义信息，和符号相关

  • 例：$E \to E_1 + E_2$：E.val = E_1.val + E_2.val，E.val是E的属性

  • 综合属性 Synthesized Attribute：只依赖于子节点的属性，只需自底向上遍历一次语法树即可得出结果

  • 继承属性 Inherited Attribute：依赖于父节点的属性

• 语义规则：定义属性值的规则，和产生式相关

  • 例：E.val = E_1.val + E_2.val

• SDD 提供了语义规则来通过遍历 AST 解析字符串

在 ANTLR4 中实现 SDD

• 对于$E \to T$，语义规则为E.val = T.val

parser grammar arith;
l: e EOF;
e: e ADD t | t;
t: t MUL f | f;
f: '(' e ')' | INT;
ADD : '+';
MUL : '*';
INT : [0-9]+;

class ArithVisitor implements arithVisitor<Integer> {
  Map<Object, Integer> AttrMap = new Map<…>();

  @override
  public Integer visitE(arithParser.EContext ctx) {
    if (ctx.getChildCount() == 1) {
      Integer val = visitT(ctx.t());
      AttrMap.put(ctx, val);
      return val;
    } else {
      ...
    }
  }
}

生成语法树

• SDD 可将高阶语言转换为低阶语言

• 适用于 IR 生成

例：

推导规则	语义规则
$Asignment \to var = Exp$	node(=).addChild(node(var), node(Exp))
$Exp1 \to Exp2 + Exp3$	node(+).addChild(node(Exp2), node(Exp3))
$Exp1 \to Exp2 * Exp3$	node(*).addChild(node(Exp2), node(Exp3))
$Exp1 \to (-Exp2)$	node(minus).addChild(node(Exp2))
$Exp1 \to var$	node(var)

生成带有 DAG 的语法树

• 在node() addChild()中增加逻辑，若已有现成节点，则直接返回

• 实现：Hash consing

翻译变量声明

• 类型

  • 基本类型：int、char、float

  • 符合类型

    • 数组：int[3]、int[3][4]

    • 结构体：record{float x; int[3] y;}、record{float x; record{int a; int b;}y;}

• 内存分布

推导规则

$$D \to T \textbf{ id }; D | \epsilon \\ T \to B C | \textbf{ record } \{ D \} \\ B \to \textbf{ int } | \textbf{ float } \\ C \to [\textbf{ num }] C | \epsilon \\$$

对应的语义规则

语法规则	语义规则	备注
（初始规则）	offset = 0;
$D \to T \textbf{ id}\\D_1$	top.put(id.lexeme,T.type,offset); offset += T.width; 暂时为空
$T \to B C$	t = B.type; w = B.width; T.type = C.type; T.width = C.width;
$T \to \textbf{ record } \{ \\ D \}$	Env.push(top); top = new Env(); Stack.push(offset); offset=0 T.type = record(top); T.width = offset; top = Env.pop(); offset = Stack.pop();	使用两个栈，Env栈存放符号信息，Stack栈存放偏移量
$B \to \textbf{int}$	B.type = int; B.width = 4;
$B \to \textbf{float}$	B.type = float; B.width = 8;	float 是64位的
$C \to \epsilon$	C.type = t; C.width = w;
$C \to [\textbf{num}] C1$	C.type = array(num.value, C1.type); C.width = num.value * C1.width;

翻译表达式

• E.code：E的三地址码，最后一条指令一定是 E.addr = xxx 的赋值语句

• E.addr：E的运算结果对应的变量（地址）

• 先执行 E.code，才有 E.addr 的值

语法规则	语义规则	备注
$S \to \textbf{id} = E$	S.code = E.code || gen(top.get(id.lexeme) '=' E.addr)	先执行 E.code，随后生成赋值语句，将 E 的结果即 E.addr赋值给 id
$E \to E_1 + E_2$	E.addr = new Temp() E.code = E1.code || E2.code || gen(E.addr '=' E1.addr '+' E2.addr)	任意二元运算符均适用
$E \to -E_1$	E.addr = new Temp() E.code = E1.code || gen(E.addr '=' 'minus' E1.addr)	任意一元运算符均适用
$E \to (E_1)$	E.addr = E1.addr E.code = E1.code
$E \to \textbf{ id }$	E.addr = top.get(id.lexeme) E.code = ''	无额外代码，使用id即可

Java 中的类型转换

• 对于 $E \to E_1 + E_2$:

$$E.type = \max(E_1.type, E_2.type); \\ a_1 = \text{widen}(E_1.addr, E_1.type, E.type); \\ a_2 = \text{widen}(E_2.addr, E_2.type, E.type); \\ E.addr = \textbf{new} \ \text{Temp}(); \\ \text{gen}(E.addr \ '=' \ a_1 \ '+' \ a_2);$$

• 类型检查

  • 赋值时检查类型：$S \to \textbf{id} = E$，检查id.type和E.type

  • 方法重载，检查参数类型

翻译控制流

• 可能的跳转点都要有 label，如果没有现成的标签，使用newlabel()生成

• S.next：S的下一条指令的标签

• S.code：S的三地址码

• B.true：B的真分支标签

• B.false：B的假分支标签

• 每一段 Statement 前都有标签，和跳转语句形成链表

语法规则	语义规则	备注
$P \to S$	S.next = newlabel() P.code = S.code || label(S.next)
$S \to \textbf{assign}$	S.code = assign.code
$S \to \textbf{if} \ ( B ) \ S_1$	B.true = newlabel() B.false = S.next = S_1.next S.code = B.code || label(B.true) || S_1.code
$S \to \textbf{if} \ ( B ) \ S_1 \ \textbf{else} \ S_2$	B.true = newlabel() B.false = newlabel() S_1.next = S_2.next = S.next S.code = B.code || label(B.true) || S_1.code || gen('goto' S.next) || label(B.false) || S_2.code
$S \to \textbf{while} \ ( B ) \ S_1$	begin = newlabel() B.true = newlabel() B.false = S.next S_1.next = begin S.code = label(begin) || B.code || label(B.true) || S_1.code || gen('goto' begin)
$S \to S_1 \ S_2$	S_1.next = newlabel() S_2.next = S.next S.code = S_1.code || label(S_1.next) || S_2.code

翻译布尔表达式

• rel：关系运算符 <、>、<=、>=、==、!=

• 逻辑短路在此实现

语法规则	语义规则	备注
$B \to B_1 \|\| B_2$	B_1.true = B.true B_1.false = newlabel() B_2.true = B.true B_2.false = B.false B.code = B_1.code || label(B_1.false) || B_2.code	若 B_1 为真，则 B 也为真，所以B_1.true = B.true，若 B_1 为假，则执行 B_2 继续判断，所以B_1.false = newlabel()
$B \to B_1 \&\& B_2$	B_1.true = newlabel() B_1.false = B.false B_2.true = B.true B_2.false = B.false B.code = B_1.code || label(B_1.true) || B_2.code
$B \to \ ! B_1$	B_1.true = B.false B_1.false = B.true B.code = B_1.code
$B \to E_1 \ rel \ E_2$	B.code = E_1.code || E_2.code || gen('if' E1.addr rel.op E2.addr 'goto' B.true) || gen('goto' B.false)
$B \to \textbf{true}$	B.code = gen('goto' B.true)
$B \to \textbf{false}$	B.code = gen('goto' B.false)

其他

• 优化

  • 避免不必要的 goto

  • Backpatching：在生成代码时，先生成跳转语句，后面再补充标签

• 针对以下语句的翻译

  • switch

  • 函数调用