C++|Compiler|活动记录（栈帧）

活动记录（Activation Record），常称栈帧（stack frame）。需要注意的是，在支持闭包的语言中，活动记录未必在栈上，因为函数返回仍需访问其中的变量，因此活动记录应作为环境保存下来。

Activation Record

过程的调用是过程的一次活动，当过程语句（及其调用）结束后，活动生命周期结束。

变量的生命周期为其从被定义后有效存在的时间。（dynamic，和scope不同，比如每次调函数都会创建一个新的生命周期）

为了正确地管理一个过程的活动，我们需要活动记录存储相关信息。内存布局如下：

Prev Frame Pointer->——————————————

上一个栈帧传入的参数

返回地址(可能在寄存器里，如RISC）

Frame Pointer（%rbp-> —————————————

callee-save的寄存器（保护先前寄存器的值）

局部变量、临时变量（RISC将前六个局部变量放在寄存器）

返回值（多返回值的情况）

静态链（支持嵌套函数，内层持有外层栈帧的指针，以调用外部函数的变量）

Stack Pointer（%rsp）-> —————————————

这些活动记录应当尽可能放在寄存器里，以减少内存访问。

Call

l-value，左值，如x=y+1的x，我们关心x的地址

r-value，右值，如x=y+1的y+1，我们关心y+1的字面值

Call-by-Value

形参作为local name，活动记录中存储形参，caller只是计算实参的右值，并且将值传入形参的地址。

Call-by-Reference

如果实参（变量or表达式）为左值，传递左值本身。

如果实参（表达式）为右值，那么在一个地方求值后传递地址。

Call-by-Restore

传入的时候传入右值，返回时把结果的右值全部倒回之前的左值里（想起了辣鸡Matlab的语法）

Call-by-Name

如宏。意思是这个参数并不是开始就求值，而是在函数的每次实际调用再进行解析。

找了个Scala的博客http://blog.sina.com.cn/s/blog_521e9ecc0102xpcg.html ,by name每次调用时，表达式都会被重复执行一次（造成了多次side effect，98765递减5次，而4只减了1次）

def printByName(x: => Int): Unit = {
    for (i <- 0 until 5)
      println(x)
  }

  def printByValue(x: Int): Unit = {
    for (i <- 0 until 5)
      println(x)
  }
  printByName(count) //9 8 7 6 5 
  printByValue(count)// 4 4 4 4 4 

简单说来就是一个是将未计算的参数表达式直接应用到函数内部， 一个是计算参数表达式的值，传入函数计算。 This indicates that the argument is not evaluated at the point of function application, but instead is evaluated at each use within the function. That is, the argument is evaluated using call-by-name.

Callee-saved Register

Callee在占用寄存器前，先存入栈，执行完成后再恢复。尽管看起来到头来参数还是要入内存，但是在执行过程中，参数的使用是通过寄存器进行的。

In-register Parameter

以下情况参数必须进内存(variable escape)

• 需要取址
• 传引用
• 被嵌套的函数调用

以下情况参数在特定环境下必须进内存，并不能断定

• 参数大小大于寄存器大小
• register有特殊需求不能被占用（例如汇编要求占用寄存器）
• 局部变量数量多于可用寄存器数目

在C中，某些可变参数函数（printf）需要所有的参数都是连续分配的，那么不能使得某些参数在寄存器，某些在内存。很多现代标准中，caller会为寄存器变量仍然分配内存空间，只有callee需要时才会把值真正填进去。

嵌套过程

静态链（Static Link)

嵌套函数中，内部函数调用的栈帧可见外部函数调用的栈帧中的变量。

以frame pointer作为第一个参数（不一定是当前的栈帧，而是callee的上层）传递给callee作为static link，可以通过static link回溯上一层、上上层的栈帧，最终获得外部的变量。（隐式链表）

类似于对象第一个参数隐式传this指针，因此类的方法能够访问类的field，但是这个原理又大相径庭，这个其实是建立了一个栈帧链表。

当前过程和nonlocal变量的嵌套深度差，是所需link的次数。编译期已知。

如果儿子1调用儿子2，那么事实上儿子1是通过父亲访问到的儿子2，因此不能直接传儿子1的栈帧，而是先回溯到父亲的栈帧，再把父亲的栈帧指针作为第一个参数传递给儿子2.

嵌套层次显示表（Display）

嵌套层次显示表是帧指针组成的数组，下标为深度。元素Di指向最近被调用的嵌套深度为i的函数（听起来所有的函数公用一张表）

执行嵌套深度为i的函数时，对Di进行callee-save 并且更新Di。

入口出口由于callee-save需要的指令更多，但是由于采用数组而不是链表，在随机访问上则更占据优势。

[公式]

提升（Lambda Lifting）

将父函数中每一个被子函数（或者孙子、曾孙...）访问的变量作为额外的参数按引用传递给子函数。听起来就属于

[公式]

演算的术语，适合函数式编程，如果父函数中的变量都是unmutable，函数都是pure function就好办了，直接传值就行了。

难点在于语义分析时还得找出函数访问的上层变量，实现的时候未必简单。

Implementation

Frame

typedef struct F_frame_ *F_frame ;
F_frame F_newFrame(Temp_label name, U_boolList formals);

虎书上没有给出具体实现，而是给出了ADT，避免机器依赖。（emmm，好像lab要我们写实现）

newFrame第一个参数表示函数名，第二个是一个bool链表，T表示逃逸（在存储器中）。

struct F_access_ {
	enum {inFrame, inReg} kind;
	union {
		int offset;		/* InFrame */
		Temp_temp reg;		/* InReg */
	} u;
};
struct Temp_temp_ {int num;};
static F_access Inframe(int offset);   static F_access InReg(Temp_temp reg);

F_accessList F_formals(F_frame f);
F_access F_allocLocal(F_frame f, bool escape);

F_access则描述栈或者寄存器中的形参和局部变量，里面存了变量相对于栈帧指针的偏移量或者临时变量编号(间接层，由寄存器分配器处理，一方面方便优化使用尽可能少的寄存器，一方面寄存器不足时分配到内存里）。

F_allocLocal在栈帧上分配局部变量。

struct F_accessList_ { F_access head; F_accessList tail};
F_accessList F_formals(F_frame f);

F_formals 传回所有的参数，需要注意，这里的F_access是针对callee而言的（caller把static link 放进寄存器，callee把他放进内存，两者视角不同，称为View Shift）

因此newFrame需要进行额外的工作处理View Shift（machine dependent）

• 处理参数在函数内部的布局
• 实现指令（例如frame pointer + offset作为内存地址）
• 过程入口frame pointer <- stacck pointer

存储以下信息

• formal的位置
• 实现view shift的指令
• 局部变量数目
• 机器码开始处的标签

Formals
–InFrame(8)
–InFrame(12)
–InFrame(16)
View Shift
–pushl %ebp
–movl %esp, %ebp
–subl $K, %esp

Local

• 寄存器中的变量会优化，尽可能使用少的寄存器
• Frame中的变量会优化，两个变量可能先后共用同一个槽
• 由于嵌套block，可能某个变量多次声明在不同block中，可以为变量声明保留专门的槽，只在block结束后遗忘关联。

Escape

EscapeEntry(d, &(x->escape))

一开始所有的变量均设为 not escape，记录其嵌套深度，如果某个变量被嵌套的函数所访问（需要通过静态链去内存找），则成为escape

Tiger没有寻址，如果有寻址操作也escape

Label

struct Temp_temp_ {int num;};
typedef struct Temp_temp_ *Temp_temp;
Temp_temp Temp_newTemp(void);// from  set
typedef S_symbol Temp_label; 
Temp_label Temp_newlabel(void);// from  set
Temp_label Temp_namedlabel(string);
string Temp_labelstring(Temp_label);

由于要知道具体的地址或者寄存器可用情况很难，先用抽象指代其位置。new生成新的标号。

Temp 局部变量抽象名（以后映射到寄存器或内存）

Label 存储器地址抽象名（生成机器代码地址的标号）

环境

栈帧本身并不负责跟踪level，这个应该是语义分析阶段的事。

在环境中需要跟踪level信息

如果发现了函数声明，那么Tr_newLevel()更新level存入entry，并且在newlevel中调用newFrame，且将static link作为第一个参数。

如果发现了局部变量声明，那么Tr_allocLocal(lev, esc) 在lev层alloc变量，并且Tr_access保存分配入口。

struct Tr_level_ { F_frame f; int level; };
struct Tr_access_ { Tr_level level; F_access access; };

struct E_enventry_ {
 enum {E_varEntry, E_funEntry} kind;
 union {
 struct {Tr_access access; Ty_ty ty; } var ;
 struct {Tr_level level; Temp_label label;
  Ty_tyList formals; Ty_ty result; } fun ;
 } u ;
}