Stanford Compiler Week 6 Code Generation Part 2

课程主页：

https://www.edx.org/course/compilers

课程视频：

https://www.bilibili.com/video/BV1NE411376V?p=20&t=6

备注：

图片均来自于课件。

这次回顾代码生成第二部分。

代码生成的例子

回顾之前讨论的语言

$$\begin{aligned} \mathrm{P} \rightarrow &\mathrm{D ; P | D}\\ \mathrm{D} \rightarrow &\text {def } \operatorname{id}(\mathrm{ARGS})=\mathrm{E} \\ \text { ARGS} \rightarrow &\text {id, ARGS | id }\\ \mathrm{E} \rightarrow& \text {int} \text { id } | \text { if } \mathrm{E}_{1}=\mathrm{E}_{2} \text { then } \mathrm{E}_{3} \text { else } \mathrm{E}_{4} \\ & \mathrm{E}_{1}+\mathrm{E}_{2}|\mathrm{E}_{1}-\mathrm{E}_{2}| \mathrm{id}\left(\mathrm{E}_{1}, \ldots, \mathrm{E}_{\mathrm{n}}\right) \end{aligned}$$

下面来看一个复杂的例子。

例子

def sumto(x) = if x = 0 then 0 else x + sumto(x – 1)

代码生成：

#x in ra
sumto_entry:
	move	$fp		$sp				#fp=sp
	sw		$ra		0($sp)			#*sp=ra
	addiu	$sp		$sp		-4		#sp-=4
	lw		$a0		4($fp)			#a0=*(sp+4)(a0=x)
	sw		$a0		0($sp)			#*sp=a0
	addiu	$sp		$sp		-4		#sp-=4	
	li		$a0		0				#a0=0		
	lw		$t1		4($sp)			#t1=*(sp+4)(t1=a0=x)
	addiu	$sp		$sp		+4		#sp+=4
	beq		$a0		$t1		true1	#if a0=t1, goto true1
false1:								#x in sp - 4
	lw		$a0		4($fp)			#a0=*(4+fp)	
	sw		$a0		0($sp)			#*sp=a0
	addiu	$sp		$sp		-4		#sp-=4
	sw		$fp		0($sp)			#*sp=fp
	addiu	$sp		$sp		-4		#sp-=4
	lw		$a0		4($fp)			#a0=*(4+fp)
	sw		$a0		0($sp)			#*sp=a0
	addiu	$sp		$sp		-4		#sp-=4
	li		$a0		1				#a0=1
	lw		$t1		4($sp)			#t1=*(4+sp)
	sub		$a0		$t1		$a0		#a0=t1-a0(a0=x-1)
	addiu	$sp		$sp		4		#sp+=4
	sw		$a0		0($sp)			#*sp=a0
	addiu	$sp		$sp		-4		#sp-=4
	jal		sumto_entry				#goto sumto_entry
	lw		$t1		4($sp)			#t1=*(4+sp)
	add		$a0		$t1		$a0		#a0=t1+a0
	addiu	$sp		$sp		4		#sp+=4
	jal		endif1
true1:
	li		$a0		0				#a0=0
endif1:								#恢复调用前的状态
	lw		$ra		4($sp)			#ra=*(4+sp)
	addiu	$sp		$sp		12		#sp+=12
	lw		$fp		0($sp)			#fp=*sp
	jr		$ra						#goto address in ra

临时变量（Temporaries）

这部分讨论对临时变量的处理。

• 想法：将临时变量留在AR中。
• 代码生成器必须在AR中为每个临时对象分配一个位置。
• 回顾：AR为激活记录，为管理一个过程激活所需的信息。

例子

def fib(x) = if x = 1 then 0 else
    if x = 2 then 1 else
    	fib(x - 1) + fib(x – 2)

这里

x = 1
x = 2

为临时变量。

讨论

• 令$\text{NT(e)}=$评估$\mathrm{e}$所需的临时变量。
• $\mathrm{NT(e_1 + e_2)}$
  • 至少需要与$\mathrm{NT(e_1)}$一样多的临时变量。
  • 至少需要与$\mathrm{NT(e_2)}+1$一样多的临时变量。
    • 加$1$是因为需要存储$\mathrm{e_1}$。
• $\mathrm{e_1}$中用于临时变量的空间可以在$\mathrm{e_2}$中重复使用。

性质

$\text{NT(e)}$满足如下性质：

$$\begin{aligned} \mathrm{NT}\left(\mathrm{e}_{1}+\mathrm{e}_{2}\right)&= \max \left(\mathrm{NT}\left(\mathrm{e}_{1}\right), 1+\mathrm{NT}\left(\mathrm{e}_{2}\right)\right) \\ \mathrm{NT}\left(\mathrm{e}_{1}-\mathrm{e}_{2}\right)&= \max \left(\mathrm{NT}\left(\mathrm{e}_{1}\right), 1+\mathrm{NT}\left(\mathrm{e}_{2}\right)\right) \\ \mathrm{NT}\left(\text {if } \mathrm{e}_{1}=\mathrm{e}_{2} \text { then } \mathrm{e}_{3} \text { else } \mathrm{e}_{4}\right)&=\max \left(\mathrm{NT}\left(\mathrm{e}_{1}\right), 1+\mathrm{NT}\left(\mathrm{e}_{2}\right), \mathrm{NT}\left(\mathrm{e}_{3}\right), \mathrm{NT}\left(\mathrm{e}_{4}\right)\right) \\ \mathrm{NT}(\mathrm{id}\left(\mathrm{e}_{1}, \ldots, \mathrm{e}_{\mathrm{n}}\right) &=\max \left(\mathrm{NT}\left(\mathrm{e}_{1}\right), \ldots, \mathrm{NT}\left(\mathrm{e}_{\mathrm{n}}\right))\right.\\ \mathrm{NT}(\mathrm{int})&=0 \\ \mathrm{NT}(\mathrm{id})&=0 \end{aligned}$$

例子

依然考虑之前的代码

def fib(x) = if x = 1 then 0 else
	if x = 2 then 1 else
		fib(x - 1) + fib(x – 2)

那么需要的临时变量数量为$2$：

后续会利用$\mathrm{NT}$进行分析。

函数

对于函数定义$\mathrm{f\left(x_{1}, \ldots, x_{n}\right)=e}$，AR具有$\mathrm{2 + n + NT(e)}$个元素：

• 返回地址；
• 栈帧指针；
• $\mathrm{n}$个参数；
• 用于中间结果的$\mathrm{NT(e)}$个位置。

图示：

补充

• 代码生成必须知道每个点使用了多少个临时对象；
• 所以在代码生成中添加新的参数：
  • 下一个可用临时位置。
• 临时区域的使用类似于固定大小的小型堆栈

增加参数前的代码：

增加参数后的代码：

习题

选择第二项。

对象布局

引子

• OO实现 = 基本代码生成 + 更多内容；
• OO标语：如果B是A的子类，则可以在需要A类对象的任何地方使用B类对象；
• 这意味着对于类B的对象，类A中的代码可以不修改地工作；
• 那么
  • 对象如何表示在内存中？
  • 如何执行动态分派？

例子

代码：

Class A {
    a: Int <- 0;
    d: Int <- 1;
    f(): Int { a <- a + d };
}; 

Class B inherits A { 
    b: Int <- 2;
    f(): Int { a };
    g(): Int { a <- a - b };
};

Class C inherits A {
    c: Int <- 3;
    h(): Int { a <- a * c };
};

• 属性a和d由类B和C继承；
• 所有类中的所有方法均指向a；
• 为了使A方法在A，B和C对象中正常工作，属性a必须在每个对象中的相同“位置”中。

布局

从之前的例子中不难看出：

• 对象在连续的内存中布局；

• 每个属性以固定的偏移量存储在对象中；

  • 固定的属性在该类中的每个对象中都位于同一位置。

• 调用方法时，对象是self，而字段是对象的属性；

• Cool对象的前3个字包含header信息：

  • 

  • 类标签是一个整数

  • 标识对象的类别。
  • 对象大小是整数
    • 以字为单位的对象大小。
  • Dispatch ptr是指向方法表的指针
    • 后续介绍。
  • 后续位置中存储属性
  • 布局在内存中连续。

属性的布局

• 观察：给定A类的布局，子类B的布局可以通过将增加的属性添加到A的属性后得到；
  • 这保持A的布局不变；
  • 即B是扩展。

来看一个具体例子：

• 属性的偏移量在一个类及其所有子类中均相同；
  • $\mathrm{A_1}$的任何方法都可以在子类$\mathrm{A_2}$上使用。
• 考虑$\mathrm{A_n <\ldots <A_3 <A_2 <A_1}$的布局

习题

选择第三项。

例子

依然考虑之前的代码

Class A {
    a: Int <- 0;
    d: Int <- 1;
    f(): Int { a <- a + d };
}; 

Class B inherits A { 
    b: Int <- 2;
    f(): Int { a };
    g(): Int { a <- a - b };
};

Class C inherits A {
    c: Int <- 3;
    h(): Int { a <- a * c };
};

• 考虑分派e.g，只有类B包含该方法，所以该方法对应B的g方法。
• 考虑分派e.f，注意类A，B都包含该方法，所以分派的方法和e的类型有关。

方法的布局

• 每个类都有一组固定的方法；
  • 包括继承的方法。
• 分派表将索引这些方法；
  • 方法入口数组；
  • 方法f位于类及其所有子类分派表中的固定偏移量处。

分派表

回顾的例子：

Class A {
    a: Int <- 0;
    d: Int <- 1;
    f(): Int { a <- a + d };
}; 

Class B inherits A { 
    b: Int <- 2;
    f(): Int { a };
    g(): Int { a <- a - b };
};

Class C inherits A {
    c: Int <- 3;
    h(): Int { a <- a * c };
};

• A类的分派表只有一种方法；
• B和C的表将A的表向右扩展；
• 因为方法可以被覆盖，所以f的方法在每个类中都不相同，但始终位于相同的偏移量处。

图示如下：

分派指针

• $\mathrm{X}$类的对象中分派指针指向$\mathrm{X}$类的分派表；
• 在编译时，在分派表中为类$\mathrm{X}$的每个方法$\mathrm f$分配了偏移量$\mathrm{O_f}$；
• 为了实现动态分派$\text { e.f() }$，
  • 对于给定对象$\mathrm{x}$，评估$\mathrm{e}$；
  • 我们调用$\mathrm{D}\left[\mathrm{O}_{\mathrm{f}}\right]$；
    • 其中$\mathrm{D}$是$\mathrm x$的分派表。
    • 在调用中，$\mathrm {self}$绑定到$\mathrm x$。