Home 计算机科学 编译原理

# Activation Record/Stack Frame

函数的栈帧是栈上用来放函数的局部变量、参数、返回地址以及其他临时变量的区域
stack 一般从高地址向低地址，heap 从低地址向高地址
layout:

  • incoming arguments: 存储 caller 传递给 callee 的参数
  • frame pointer: 帧指针，用来访问 incoming arguments，从低向高是 argument 1, argument 2, …
  • local variables: 存储函数的局部变量（还有一些保存在寄存器里）
  • return address: 存储需要返回 caller 的哪里；non-leaf 过程会把 return address 写入栈帧里面
  • temporaries: 存储临时变量，复杂表达式拆出来的中间变量放的地方
  • saved registers
  • outgoing arguments: 存储当前函数要传递给别的函数的参数
  • stack pointer: 栈指针，从低向高

# 函数调用流程：

  • g 调用 f 的时候
  1. 进入 f 的时候，保存旧的 FP (g 的 FP)
  2. 把 FP 设置为原来的 SP，把 SP = SP - frame size
  • f 返回的时候
  1. 让 SP = FP (恢复 g 的 SP)
  2. 从内存中读出 g 的 FP 恢复回去

如果栈帧大小固定就只需要 FP 不需要 SP 了，因为 FP = SP + frame size

# saved register

函数 g 调用 f 的时候，用到了寄存器 r，调用 f 的时候要把 r 保存在 saved register 中，等调用结束再恢复回去

  • caller-saved register: 函数调用的时候用到的寄存器，调用结束后可以恢复
  • callee-saved register: 函数调用的时候用不到的寄存器，调用结束后不能恢复
    FP 是由 callee 保存和恢复的

# 参数传递

一般约定把前 k (4 or 6) 个参数放在寄存器传递，剩下的参数放在栈中传递
四种传参方法：

  1. 不给叶过程 (leaf procedure) 分配栈帧
    叶过程是指不调用其他过程的过程。在这种情况下，可以不为叶过程分配栈帧
  2. 过程间寄存器分配 (interprocedural register allocation)
    这种方法需要先分析代码中全部的函数，然后再根据分析结果来分配寄存器。
    假设有一个程序包含多个函数，通过全局分析发现某些变量在多个函数之间频繁使用，可以为其分配固定的寄存器，避免频繁的内存读写
  3. 若变量 x 不再被使用，可以直接写其寄存器，不需要再保存 x 到栈帧中
    当一个变量在当前作用域内不再被使用时，可以直接将其值写入寄存器，而无需保存到栈帧中
example
1
2
3
4
5
6
void exampleFunction() {
    int x = 5;
    int y = x * 2;  // 使用x后，x不再被使用
    // 直接将y的值写入寄存器，无需保存x到栈帧中
    printf("Result: %d\n", y);
}
  1. 寄存器窗口技术 (register windows)
    在每次函数调用时，系统会自动切换到一组新的寄存器，称为寄存器窗口。这样，每个函数都可以独立地使用自己的寄存器，而不会影响其他函数的寄存器状态。
example
1
2
3
4
5
6
7
8
void functionA() {
    // 使用寄存器窗口A
}

void functionB() {
    // 使用寄存器窗口B
    functionA();  // 调用functionA时，自动切换到寄存器窗口A
}

# Frame-Resident Variables

什么情况下要把变量写入栈帧里面？、

  1. the varibles will be passed by reference 变量传地址 / 引用
  2. 变量被嵌套在函数内部的函数访问（不绝对）
  3. 变量太大了没法直接放寄存器
  4. 变量是一个数组
  5. 传递参数
  6. 有太多局部变量和临时变量放不下了
  • escape 逃逸：如果一个变量需要传地址 / 取地址 / 被过程内部嵌套的函数访问，那么这个变量就会逃逸。

在嵌套的函数声明中，内层函数是有可能用到外层函数的局部变量的。

  • static links 是指向上一层嵌套层级的栈帧的指针。内层嵌套函数调用外层定义的变量的时候需要用到 static links，否则无法寻址。


    只有调用自身的时候才传递自己的 static link 作为 static link，其他的都是把外层函数的 fp 作为 static link
    如果要访问外层变量，就顺着 static 一层一层查上去直到找到了为止。
    其他访问方法：
  • 嵌套层次显示表 (display)
    建立一个全局数组，位置 i 包含一个指针，指向最近一次进入的，其静态嵌套深度是 i 的过程的栈帧

    先给它们标上嵌套深度
    直接把链表变成数组了，需要用到一个变量，就查看当前变量的嵌套深度 i 然后直接找那个数组 i 位置的座位 fp 地址来找
  • lambda lifting
    g 调用 f 时，g 中每一个实际（或被嵌套在 f 内的任意函数）访问了的变量，都将作为额外的参数传递给 f
    把内部的函数，从内往外进行改写，改写函数的参数实现 lambda lifting

# tiger 编译器的栈帧

tiger 不支持高阶函数
看不完了。。再说吧