本次笔记内容：
10.栈与过程调用的机器表示-1
11.栈与过程调用的机器表示-2
12.实验

文章目录

• • • 前言
    • x86-32的程序栈
    • • 压栈操作
      • 出栈操作
    • 过程调用
    • • 基于栈的编程语言
      • 栈帧
      • x86-32/Linux下的栈帧
      • 以swap过程为例
    • 寄存器使用惯例
    • • 为什么设置“使用惯例”
      • x86-32/Linux下的使用惯例
      • 递归调用例子
      • 带指针的“阶乘”过程
    • x86-32过程调用小结
    • x86-64通用寄存器与过程调用
    • • x86-64寄存器
      • 例：x86-64下的swap过程 - 1
      • 例：x86-64下的swap过程 - 2
      • 例：x86-64下的swap过程 - 3
      • 例：x86-64下的swap过程 - 4
      • x86-64的栈帧使用实例
    • 实验作业

前言

首先复习了上节课内容。

消除部分数据相关是有必要的，为了提高效率，可以使用 Partial Register Stall 等技术。

条件跳转指令可能对流水线效率造成伤害。

x86-32的程序栈

• 符合“栈（stack）”工作原理的一块内存区域，从高地址向低地址“增长”。
• %esp存储栈顶位置（尽量使esp指向当前栈的栈顶）。

压栈操作

pushl Src

• 从Src取得操作数
• %esp = %esp - 4
• 写入栈顶地址

出栈操作

popl Dest

• 读取栈顶数据（%esp）
• %esp = %esp + 4
• 写入Dest

过程调用

• 利用栈支持过程调用与返回

过程调用指令：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.

以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通用寄存器与过程调用

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。