斯坦福cs231(编译原理)の 8 Cool Object Layout

本文是斯坦福cs143编译原理的笔记，内容大部分来自于课件和自己的理解，笔者能力和精力有限，如果有错误欢迎指出

Temporaries

之前介绍的汇编代码比如两个表达式相加：

lw $a0 (0)$sp
li $t0 ?
add $a0, $t0, $a0
sw $s0 $sp

这里把其中一个加数放在了stack里，然后取出来，再把计算的中间结果放在了stack里，这就是临时变量

最普通的堆栈机需要在函数栈帧暂存这些临时变量（虽然这并不高效，后面会讲解关于临时变量分配到寄存器的算法）

考虑下面代码使用了多少临时变量：

def fib(x) = 
if (x == 1) ==> 1
	then 0 ==> 0
else
	if (x == 2) ==> 1
		then 1 ==> 0
	else
		fib(x-1) + fib(x-2) ==> x-1是一个，x-2是一个，两式相加，会产生一个，所以共两个
	fi
fi

定义NT(e)为表达式e需要多少个临时变量

对于一个函数定义：f(x1, ..., fn) = e，the AR has 2 + NT(e) elements:

• Return
• Frame pointer
• n arguments
• NT(e)

以下是一些常见的规则：

NT(e1 + e2) = Max(NT(e1), NT(e2) + 1)
	Needs at least as many tempories as NT(e1)
	Needs at least as many tempories as NT(e2) + 1
Of course, space used for temporaies in e1 can be reused for temporaies in e2

NT(if e1 = e2 then e3 else e4) = Max(NT(e1), NT(e2) + 1, NT(e3), NT(e4))
NT(id(e1, ..., en) = Max(NT(e1), ..., NT(en))
NT(int) = 0
NT(id) = 0

在没有使用临时变量之前：

cgen(e1 + e2) = 
	cgen(e1)
	sw $a0 0($sp)
	addiu $sp $sp - 4
	cgen(e2)
	lw $t1 4($sp)
	add $a0 $t1 $a0
	addiu $a0 $sp 4

使用了临时变量之后：

cgen(e1 + e2, nt) = 
	cgen(e1, nt)
	sw $a0 nt($fp) // 在偏移量处做压入栈的动作
	// addiu $sp $sp - 4 这样就不用了频繁执行addiu了
	cgen(e2, nt + 4)
	lw $t1 nt($fp)
	add $a0 $t1 $a0
  // addiu $a0 $sp 4

Object Layout and dynamic dispatch

OO(Objetc Oriented) Implementation = Basic code generation + more stuff (面向对象的实现其实就是之前所介绍的基本代码生成+本次要讲的内容)

OO Slogan：如果B是A的子类，那么B类对象可以用于任何A类的地方：

eg:

class A {}

class B extends A {}

void f (A a) {

}

函数f的入参可以是A及其子类

这就意味着在代码生成的时候，在已经生成完了A类的代码，那么B类(A的子类)可以不用修改其父类(A)的代码，而只是在其基础上进行扩展。

再介绍对象的代码生成之前，需要考虑以下问题：

对象在内存里如何表示？

• Objects are laid out int contiguous memory;

• Each attribute stored at a fixed offset in the object;

• The attribute is in the same place in every object of that class;

• When a method is invoked, the object is self and the fields are the object's attributes;

为什么对象每个属性都是固定的偏移量呢？这要归结于同一个类可以new多个对象，但这些对象的数据内存是各自独有的，每个对象同一个属性在固定偏移量的内存处，方便获取；而方法是共享的，所以方法单独维护在了一张methods table中，每个对象都都持有指向这个methods table的指针dispatch pointer，不然不同的对象还要维护各自的方法，这样太费内存了。

如何实现动态分配?

answer: Method table and dispatch ptr

关于动态分配和静态分配的概念：https://lukasatkinson.de/2016/dynamic-vs-static-dispatch/

其实node里也有静态分配和动态分配的概念：

wip

首先介绍下对象布局

考虑如下🌰，以下内容均围绕该🌰展开：

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

class B {
 b: Int <- 2;
 f(): Int { a };
 g(): Int { a <- a - b };
}

class C {
	c: Int <- 3;
	h(): Int { a <- a * c };
}

cool objects layout: (下面内存是连续的)

Class tag(int) 类标识符
Object size(int)
Dispatch ptr
Attribute 1
Attribute 2
...

其中前3个称为header infomation

关于继承的子类的内存布局：考虑父类A，其子类B可以通过在A布局之上进行扩展得到，如下：

B is an extension， just leaves the layout of A unchanged

Class	0	4	8	12	16	20
A	Atag	5(word)	dispatch ptr1	a	d
B	Btag	6(word)	dispatch ptr2	a	d	b
C	Ctag	6(word)	dispatch ptr3	a	d	c

The offset for an attribute is the same in a class and all of its subclass

介绍下动态分配

考虑e.f(), 这个表达式e生成之后，该如何调用对象上的方法呢？

和属性布局一样，对象的方法同样在内存上有着固定的偏移量(包含继承的方法)，只不过这些方法是存在一张dispatch table里的(其实我个人喜欢称之为method table)，这张表提供了索引这些方法的能力，表里存储的是函数地址，如，方法f就是在其附属类的表里的固定偏移量处，当然在其子类也是同样的偏移量；

为什么同一方法在类和其子类中设计成固定的偏移量呢？wip

Class	0	4
A	fa
B	fb	g
C	fa	h

注：如果fa中海定义了其他方法，则可以

类的每个方法f都在编译期被分配在dispatch table的固定偏移量O_f 处，换句话说，编译器的工作就是找出类的所有方法然后给每个方法分派一个固定的位置。

综上，为了实现dynamic dispatch e.f()，编译器应该走以下两个步骤：

1. 评估表达式e，得到一个对象x；
2. call D[Of]
   • D is the disptatch table for x
   • in the call ,self is bound to x

总结

在学习完之后，我们考虑下如果是我们该如何为以下代码设计代码生成

class A {
	a: Int <- 1;
	f(): Int { Int(1) };
}

class B extends A {
	b: Int <- 10;
	g(): int { b;
}

class C extends A {
	m: Int <- 2;
	f(): int { Int(2)};
}

b: B <- new B();
b.g();

c: C <- new C();
c.f();

评估b: A <- new B();
初始化:
classTag: 2
size: 5
0f4888 => dispath table1
a: 1
b: 10

dispath table1:
f: rcsv__f
g: rcsv__g


评估c: A <- new C();
初始化c
classTag: 3
size: 5
0f4888 => dispath table2
a: 1
m: 2


dispath table2:
f: rcsv__f

b.g();
获取b对象的dispatch table1
拿到g方法
调用即可