本次笔记内容：
10.栈与过程调用的机器表示-1
11.栈与过程调用的机器表示-2
12.实验
文章目录
前言
首先复习了上节课内容。
消除部分数据相关是有必要的，为了提高效率，可以使用 Partial Register Stall 等技术。
条件跳转指令可能对流水线效率造成伤害。
x86-32的程序栈
- 符合“栈（stack）”工作原理的一块内存区域，从高地址向低地址“增长”。
- %esp存储栈顶位置（尽量使esp指向当前栈的栈顶）。
| 栈底 |
|---|
| ↑ Increasing Addresses |
| ↓ Stack Grows Down |
| 栈顶指针 %esp 栈顶 |
压栈操作
pushl Src
- 从Src取得操作数
- %esp = %esp - 4
- 写入栈顶地址
| 栈底 |
|---|
| ↑ Increasing Addresses |
| ↓ Stack Grows Down |
| %esp 本来指向这里，压栈后-4，指向下面 |
| 栈顶指针 %esp 栈顶 |
出栈操作
popl Dest
- 读取栈顶数据（%esp）
- %esp = %esp + 4
- 写入Dest
| 栈底 |
|---|
| ↑ Increasing Addresses |
| ↓ Stack Grows Down |
| 栈顶指针 %esp 栈顶 |
| %esp 本来指向这里，出栈后+4，指向上面 |
过程调用
- 利用栈支持过程调用与返回
过程调用指令：call label，将返回地址压入栈，跳转至label。
返回地址：call指令的下一条地址。汇编实例如下。
804854e: e8 3d 06 00 00 call 8048b90 <main>
8048553: 50 pushl %eax
Return address = 0x8048553
过程返回指令：ret，跳转至栈顶的返回地址。
我理解，其作用为，执行 call 后面的函数，执行结束后，在回到本线程来。call即，我在执行前，先把当前线程执行到哪里了，做个标记，压栈。
基于栈的编程语言
支持递归：
- e.g. C, Pascal, Java
- 代码时可重入的（Reentrant），同时有同一个过程的多个实例在运行；
- 因此需要有一块区域来存储每个过程实例的数据，包括参数、局部变量、返回地址。
栈的工作规律：
- 每个过程实例的运行时间是有限的，即栈的有效时间有限：From when called to when return；
- 被调用者先于调用者返回（一般情况下，如果遇到异常处理情况，则不是这个样子）。
每个过程实例在栈中维护一个栈帧（stack frame）。
栈帧
栈帧（stack frame）存储内容：
- 局部变量；
- 返回地址；
- 临时空间
栈帧的分配与释放：
- 进入过程后先“分配”栈帧空间，“Set-up” code；
- 过程返回时“释放”，“Finish” code。
- 寄存器%esp指向当前栈帧的起始地址。
过程调用时栈的变化：
x86-32/Linux下的栈帧
当前栈真的内容（自“顶”向下）
- 子过程参数：“Argument build”；
- 局部变量，因为通用寄存器个数有限；
- 被保存的寄存器值；
- 父过程的栈帧起始地址（old %ebp）
父过程的栈帧中与当前过程相关的内容：
- 返回地址，由call指令存入
- 当前过程的输入参数；
- etc.
| Caller Frame | … |
|---|---|
| Caller Frame | Arguments |
| Caller Frame | Return Addr |
| 栈帧指针（%esp） | Old %ebp |
| Saved Registers + Local Variables | |
| 栈顶指针（%esp） | Argument Build |
以swap过程为例
如上图，当前%ebp还是父过程%ebp，因此Setup现将其存储，留着以后恢复。
之后将当前（新的）%ebp指向旧的%ebp，即设好之后工作的基址。
之后push %ebx，因为尽管父过程可能用%ebx，为了安全，要保存一下。
当然，也不是所有的实例的寄存器都要存。以后讲。
抽象的堆栈和实际的栈的对应关系如上图。
Finish在调用结束后，将父过程恢复。
寄存器使用惯例
为什么设置“使用惯例”
过程yoo调用who：
- yoo：caller
- who：callee
做一个软件层面的约定：哪些寄存器由调用者保存，哪些由被调用者保存。
如何使用寄存器作为程序的临时存储？
yoo:
...
movl $15213, %edx
call who
addl %edx, %eax
...
ret
who:
...
movl 8(%ebp), %edx
addl $91125, %edx
...
ret
如上例，%edx可能被yoo和who同时重复保存恢复，因此作出约定：
使用惯例：
- 调用者负责保存：caller在调用子过程之前将这些寄存器内容存储在它的栈帧内；
- 被调用者负责保存：callee在使用这些寄存器之前将其原有内容存储在它的栈帧内。
x86-32/Linux下的使用惯例
8个Registers：
- 两个特殊寄存器%ebp，%esp
- 三个由调用者负责保存：%ebx，%esi，%edi
- 三个由被调用者负责保存：%eax，%edx，%ecx
- %eax用于保存过程返回值
递归调用例子
int rfact(int x) {
int rval;
if (x <= 1)
return 1;
rval = rfact(x - 1);
return reval * x;
}
寄存器使用情况：
- %eax直接使用；
- %ebx使用前保存旧值，退出前恢复。
.globl rfact
.type
rfact, @function
rfact:
pushl %ebp
movl %esp, %ebp
pushl %ebx # Set up
movl 8(%ebp), %ebx
cmpl $1, %ebx
jle .L78
leal -1(%ebx), %eax
pushl %eax
call rfact
imull %ebx
jmp .L79
.align 4
.L78:
movl $1, %eax
.L79:
movl -4(%ebp), %ebx
movl %ebp, %esp
popl %ebp
ret
带指针的“阶乘”过程
// Recursive Procedure
void s_helper(int x, int *accum) {
if (x <= 1)
return;
else {
int z = *accum * x;
*accum = z;
s_helper(x - 1, accum);
}
}
// Top-Level Call
int sfact(int x) {
int val = 1;
s_helper(x, &val);
return val;
}
首先，创建指针，如下图。
如上图，可以认识到，在编程中不能把临时变量的地址return。
之所以将%esp增加16 bytes，是因为很多机器（x86-32）中要求栈16 bytes对齐。
接下来，传递指针。
因此，如上图，在使用指针时，就如上图：
- %ecx存储变量x；
- %edx存储变量accum。
x86-32过程调用小结
程序栈：
- 各个过程运行实例的私有空间：不同实例间避免相互干扰，过程本地变量与参数存于栈内(采用相对于栈基址%ebp的寻址)
- 符合栈的基本工作规律：过程返回顺序与过程调用的顺序相反
相关指令与寄存器使用惯例：
- Call / Ret指令
- 寄存器使用惯例：调用者/被调用者保存，%ebp/%esp两个特殊奇存器
- 栈帧的存储内容
x86-64通用寄存器与过程调用
| 寄存器 | 惯例 | 寄存器 | 惯例 |
|---|---|---|---|
| %rax | Return Value | %r8 | Argument #5 |
| %rbx | Callee Saved | %r9 | Argument #6 |
| %rcx | Argument #4 | %r10 | Callee Saved |
| %rdx | Argument #3 | %r11 | Used for linking |
| %rsi | Argument #2 | %r12 | C: Callee Saved |
| %rdi | Argument #1 | %r13 | Callee Saved |
| %rsp | Stack Pointer | %r14 | Callee Saved |
| %rbp | Callee Saved | %r15 | Callee Saved |
x86-64寄存器
过程参数(不超过6个)通过寄存器传递：
- 大于6个的仍使用栈传递；
- 这些传递参数的寄存器可以看成是“调用者保存”寄存器。
所有对于栈帧内容的访问都是基于%esp完成的：
- %ebp完全用作通用寄存器。
例：x86-64下的swap过程 - 1
void swap(long *xp, long *yp) {
long t0 = *xp;
long t1 = *yp;
*xp = t1;
*yp = t0;
}
swap:
movq (%rdi), %rdx
movq (%rsi), %rax
movq %rax, (%rdi)
movq %rdx, (%rsi)
ret
参数由寄存器传递：
- First (xp) in %rdi, second (yp) in %rsi
- 64位指针
无需任何栈操作：
- 局部变量也存储于寄存器中。
例：x86-64下的swap过程 - 2
/* Swap, using local array */
void swap_a(long *xp, long *yp) {
volatile long loc[2];
loc[0] = *xp;
loc[1] = *yp;
*xp = loc[1];
*yp = loc[0];
}
其中，使用 volatile关键字 强制使用栈空间，但在实际使用中没有修改栈顶寄存器（%rsp）。
swap_a:
movq (%rdi), %rax
movq %rax, -24(%rsp)
movq (%rsi), %rax
movq %rax, -16(%rsp)
movq -16(%rsp), %rax
movq %rax, (%rdi)
movq -24(%rsp), %rax
movq %rax, (%rsi)
ret
例：x86-64下的swap过程 - 3
long scount = 0;
/* Swap a[i] & a[i+1] */
void swap_ele_se(long a[], int i) {
swap(&a[i], &a[i+1]);
scount++;
}
swap_ele_se:
movslq %esi, %rsi # Sign extend i
leaq (%rdi, %rsi, 8), %rdi # &a[i]
leaq 8(%rdi), %rsi # &a[i+1]
call swap # swap()
incq scount(%rip) # scount++;
ret
incq scont(%rip) 是把变量加1。
在x86下引入新寻址方式：
- 相对于当前指令（%rip）的寻址；
- 因为程序可能有动态链接库dll，而在dll中我们无法确定绝对位置，但是知道相对位置。
为什么swap_ele_se没有分配栈帧？
因为（除返回值外）没有私有数据来保留，用不着。
例：x86-64下的swap过程 - 4
long scount = 0;
/* Swap a[i] & a[i+1] */
void swap_ele(long a[], int i) {
swap(&a[i], &a[i+1]);
}
swap_ele:
movslq %esi, %rsi # Sign extend i
leaq (%rdi, %rsi, 8), %rdi # &a[i]
leaq 8(%rdi), %rsi # &a[i+1]
jmp swap # swap
使用jmp指令调用过程，可以是因为对栈没有什么变化。
x86-64的栈帧使用实例
long sum = 0;
/* Swap a[i] & a[i+1] */
void swap_ele_su(long a[], int i) {
swap(&a[i], &a[i+1];
sum += a[i];
}
swap_ele_su:
movq %rbx, -16(%rsp)
movslq %esi, %rbx
movq %r12, -8(%rsp)
movq %rdi, %r12
leaq (%rdi, %rbx, 8), %rdi
subq $16, %rsp
leaq 8(%rdi), %rsi
call swap
movq (%r12, %rbx, 8), %rax
addq %rax, sum(%rip)
movq (%rsp), %rbx
movq 8(%rsp), %r12
addq $16, %rsp
ret
- 变量a与i的值存于“被调用者保存”的寄存器中；
- 因此必须分配栈帧来保存这些寄存器。
实验作业
两个，BombLab与BufLab。