Lzh's blog

编译原理复习-5

  • 2023年 06月16日

纯纯傻逼课

Chapter-7: 运行时环境

运行时环境主要是指程序运行时的存储调用等行为的分析和刻画.

比较核心的定义是:

  • 过程定义：是一个声明，最简单形式是把一个标识符和一个语句联系起来
    • 该标识符称为过程名
    • 语句是过程体
    • 函数：返回值的过程
  • 过程调用
    • 过程名出现在可执行语句中时，则称这个过程在这点被调用
    • 调用者、被调用者和调用点

存储

存储主要分为栈分配和堆分配, 从操作系统层次讲会清晰一点.

我们首先关注调用:

活动记录

  • 定义：过程的一次执行所需要的信息用一块连续的存储区来管理，这块存储区叫做活动记录或帧

一般来说从高地址到低地址为:

Actual Parameters   // 实际传入的参数, 现在一般放寄存器
Returened values    // 返回值, 现在一般放寄存器
Control link        // 主要是栈顶
Access link         // 主要是栈底
Saved machine status// 不懂
Local data          // 开始跑自己的东西
Temporaries

我们看 x86 的相关操作, 这个体系结构和栈比较紧密:

int func(int a, int b){
        return a+b;
}

int main(){
        int c = func(3,9);
        c++;
        return 0;
}

-c得到汇编文件, 删去无关紧要的可以得到:

main:
.LFB1:
    pushq   %rbp
    // 保存栈底
    movq    %rsp, %rbp
    // 更新栈底
    subq    $16, %rsp
    movl    $9, %esi
    movl    $3, %edi
    // call    func
        pushq   %rbp
        movq    %rsp, %rbp
        movl    %edi, -4(%rbp)
        movl    %esi, -8(%rbp)
        movl    -4(%rbp), %edx
        movl    -8(%rbp), %eax
        addl    %edx, %eax
        popq    %rbp
        ret
    // 取回参数
    movl    %eax, -4(%rbp)
    addl    $1, -4(%rbp)
    movl    $0, %eax
    leave
    ret

可以看到实际和概念差距还是很大的.

活动记录的各个域的作用

  • 临时数据域：临时变量的存储等
  • 局部数据域：局部于过程执行的数据
  • 机器状态：保存过程调用前的机器状态信息
  • 返回地址和一些寄存器的内容等
  • 访问链：用于非局部数据的访问
  • 控制链：指向调用者的活动记录
  • 实在参数域：参数个数较少时，可以考虑用寄存器传递，效率高；参数多时用用这个域传递
  • 返回值域：用于存放被调用过程返回给调用过程的值，也可以用寄存器返回（效率高，但形式受限制）

Call

分配

然后关注分配给数据的情况

过程调用的实现：通过过程调用代码序列（calling sequences）实现，包括调用序列和返回序列

  • 调用序列：分配活动记录，信息的保存和填充
  • 参数、返回地址、老的控制栈top、寄存器的保存、局部对象的初始化等
  • 返回序列：恢复机器状态，使调用者继续执行
  • 返回值、寄存器的恢复、重置控制栈top、跳转到返回地址

调用序列（call sequences），过程p调用过程q

  • p计算实参，依次放入q的活动记录中（也可以利用寄存器传递参数）
  • p把返回地址和原来的top_sp的值存入q的活动记录中，建立q的访问链，增加- top_sp的值，使之指向Callee的栈顶
  • q保存寄存器的值和其它机器状态信息
  • q初始化它的局部数据，并开始执行

返回序列（return sequences），过程p调用过程q

  • q把返回值放到q的活动记录中与参数相邻的地方（也可以利用特定的寄存器传递返回值）
  • q机器状态字段的信息恢复top_sp和其它机器状态信息
  • q根据返回地址将控制返回p
  • p根据参数个数调整top_sp的值，把返回值放入自己的活动记录中，p知道返回值相对于当前top_sp值的位置

访问链

访问链的建立：

  • 假定过程q的嵌套深度为nq，它调用一个嵌套深度为np的过程p：
  • 如果np > nq
    • 过程p比过程q嵌得更深，p必定在q中定义，因此np = nq+1
    • p的访问链一定指向q，即栈中刚好在它下面的调用过程的活动记录
    • 如排序如例子中的sort调用quicksort，产生了图7-11a；以及quicksort对partition的调用，产生了图7-11c
  • 如果np = nq
    • 新的活动记录的访问链和它下面的活动记录的访问链相同，如例子中的quicksort(1,9)调用quicksort(1,3)，形成了图7-11b
    • 此时，或者是过程的递归调用，或者如同上页中的D调用C
  • 如果np < nq
    • 过程q和p的嵌套深度为1，2，…，np –1的外围过程必定相同
    • 从调用过程追踪访问链 nq - np + 1次，即到达静态包围q和p的最内过程r的最新活动记录，这个访问链就是p必须指向的访问链
    • nq - np + 1可以在编译时计算
    • 此时，如图7-11c转变为7-11d的过程，exchange的嵌套深度为2，partition的嵌套深度为3，因此要经过两次访问链的转换

通过数组存放访问链，提高对非局部名字的访问效率 如果当前的活动记录对应的过程p的嵌套深度为j，则Display表有j项，前j-1项指向依次嵌套在过程p外面的过程的最新活动记录，第j项指向过程p的这次活动记录

搜索