课程主页:

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

课程视频:

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

备注:

图片均来自于课件。

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

代码生成的例子

回顾之前讨论的语言

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

例子

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)}$满足如下性质:

例子

依然考虑之前的代码

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$。