过程调用和数组的分配访问

系列文章

: 深入理解计算机系统笔记

3.7 过程

• 过程是软件中一种很重要的抽象。用一组指定的参数和一个可选的返回值实现某种功能，可以在程序的不同的地方调用这个函数。隐藏某个行为的具体实现。过程的形式：函数（function）、方法（method）、子例程（subroutine）、处理函数（handler）等。
• 对过程的机器级支持，假设过程 P 调用过程 Q，Q 执行后返回 P。这些动作包括下面一个或多个机制：
  1. 传递控制。进入过程 Q 时，程序计数器被设为 Q 代码的起始地址，在返回时，要将程序计数器设置为 P 中调用 Q 的后面那条指令的地址。
  2. 传递数据。P 必须能够向 Q 提供一个参数，Q 必须能够向 P 返回一个值。
  3. 分配和释放内存。开始时，Q 可能需要为局部变量分配空间，而在返回前，又必须释放这些存储空间。（栈）
• 遵循最低要求策略：只实现上述机制每个过程所必须的那些

3.7.1 运行时栈

• 当Q执行时，P及其上的调用链是被挂起的，需要为Q的局部变量分配存储空间，或设置Q到另一个的过程调用。Q返回时，释放。
• 程序用栈管理过程所需的空间，栈和寄存器存放传递控制，数据和分配内存的信息（被放在栈尾）
• P调用Q时，参数设定后将返回地址压入栈，Q扩展栈的边界，大多数的栈帧是定长的，有些过程需要变长的栈帧
• 过程的栈帧是过程需要的存储空间超过寄存器存放的大小时，才在栈上分配，如果小于等于6个参数，且不调用其他函数（叶子过程）的函数通常不需要栈帧

3.7.2 转移控制

• 将P转移到Q函数只需要将PC设置为Q代码的起始地址。而返回时，处理器需要记录它需要继续P的继续执行的位置。
• call命令：将地址A（紧跟着call的下一条指令）压入栈中，将PC设置为Q代码的起始地址。可以是直接的，也可以是间接的（*）。
• ret命令：从栈中弹出地址A，并将PC设置为A

3.7.3 数据传送

-** 调用一个过程时**，也要将数据作为参数传递，从过程返回可能包含一个返回值，大部分过程间的数据传送是通过寄存器传递的。
六个寄存器传递di，si，dx，cx，8，9，一个寄存器返回ax

• 如果函数传递的参数大于六个整形参数，就需要栈来传递，所有的数据大小向8（字节）的倍数对齐
  第七个参数位于栈顶

3.7.4 栈上的局部存储

• 当寄存器不够存放所有的本地数据，或者对一个局部变量使用地址运算符，或者局部变量是数组或者结构时，在栈帧上存放局部变量

3.7.5 寄存器中的局部存储空间

• 寄存器组是唯一被所有过程共享的资源，在给定时刻只有一个过程是活动的，必须确保当一个过程调用另一个过程时，被调用者不会覆盖调用者稍后会使用的寄存器值。
• 被调用者保存寄存器（Callee-saved registers）：是指在函数调用过程中，如果被调用的函数需要使用这些寄存器，那么它必须在使用这些寄存器之前将它们的原始值保存起来（通常保存在栈上），在函数返回之前再恢复这些寄存器的值。这样就保证了调用者在调用函数前后，这些寄存器的值保持不变。

3.7.6 递归过程

• 递归调用是函数调用自身的情况，每次递归调用都会创建一个新的栈帧。即使是递归调用，栈帧的分配和释放规则依然适用，确保每次调用都有独立的状态信息。
• 函数调用过程
  调用者（caller）保存自身需要保存的寄存器值（调用者保存寄存器）。
  调用者将参数传递给被调用者（callee）。
  调用者执行 call 指令，将返回地址压入栈。
  被调用者创建新的栈帧，保存被调用者保存寄存器的值。
  被调用者执行函数体。
• 函数返回过程
  被调用者恢复被调用者保存寄存器的值。
  被调用者销毁栈帧。
  被调用者执行ret 指令，跳转到返回地址。
  调用者恢复调用者保存寄存器的值。（第一次是被调用者）
  调用者继续执行。

3.8 数组分配和访问

3.8.1 基本原则

• C语言对于数据类型 T 和整型常数 N，声明如下：
  T A[N];
  起始位置表示为xA（地址）
  ​首先，它在内存中分配一个
  L⋅N 字节的连续区域，L 是数据类型 T 的大小（单位为字节）。其次，标识符 A作为指向数组开头的指针，这个指针的值就是 x A。可以用0～N-1 的整数索引来访问该数组元素。第i个数组元素会被存放在地址为 x A+L⋅i 的地方。
• 假设 E 是一个 int 型的数组，而我们想计算 E[i]，在此，E 的地址存放在寄存器 %rdx 中，而 i 存放在寄存器 %rcx 中

movl (%rdx,%rcx,4),%eax

3.8.2 指针运算

• C 语言允许对指针进行运算， p 是一个指向类型为 T 的数据的指针，p + i 的值为 xp +L⋅i，这里 L 是数据类型 T 的大小。
• &Expr 是给出该对象地址的一个指针。对于一个表示某个对象地址的表达式 AExpr，*AExpr 给出该地址处的值。因此，表达式 A[i] 等同于表达式 *(A + i)，它计算第 i 个数组元素的地址，然后访问这个内存位置。
  假设整型数组 E 的起始地址和整数索引 i 分别存放在寄存器 %rdx 和 %rcx 中
  

3.8.3 嵌套的数组

int A[5][3];
//等价于
typedef int row3_t[3];
row3_t A[5];

• 嵌套的数组在内存中也是连续的
• xA，i，j分别存在%rdi，%rsi，%rdx中。
  将A [i] [j] 复制到%eax

leaq    (%rsi,%rsi,2), %rax       # 计算 3i
leaq    (%rdi,%rax,4), %rax       # 计算 x_A + 12i
movl    (%rax,%rdx,4), %eax       # 从 M[x_A + 12i + 4j] 读取数据

3.8.4 定长数组

• C语言编译器能优化定长多维数组，O1时的一些优化

1. 去掉整数索引：它将所有的数组引用都转换成了指针间接引用
2. 生成指针Aptr：指向数组A的行i中连续的元素
3. 生成指针Bptr：指向数组B的列k中连续的元素
4. 生成指针Bend：当需要终止循环时，它会等于Bptr的值。Bend的值是假想中B的列k的第(n+1)个元素的地址，由C表达式&B[N][k]给出。

• 例子：

/* Compute i,k of fixed matrix product */
int fix_prod_ele (fix_matrix A, fix_matrix B, long i, long k) {long j;int result = 0;for (j = 0; j < N; j++)result += A[i][j] * B[j][k];return result;
}
//优化后
/* Compute i,k of fixed matrix product */
int fix_prod_ele_opt(fix_matrix A, fix_matrix B, long i, long k) {int *Aptr = &A[i][0];   /* Points to elements in row i of A */int *Bptr = &B[0][k];   /* Points to elements in column k of B */int *Bend = &B[N][k];   /* Marks stopping point for Bptr */int result = 0;do {result += *Aptr * *Bptr;  /* Add next product to sum */Aptr++;                   /* Move Aptr to next column */Bptr += N;                /* Move Bptr to next row */} while (Bptr != Bend);       /* Test for stopping point */return result;
}

3.8.5 变长数组

• C99的变长数组允许数组的维度是一个表达式，分配时才计算。由于分配时才计算，所以在leap指令前需要需要一次乘法指令（imul），影响性能。循环访问时编译器可以优化，识别步长，避免直接应用乘法。