CSAPP 第三章 程序的机器级表示（二）基本数据结构的机器级实现与浮点数指令

发表于 | 分类于

不要假设，要证明。

1. 数组

对于数组声明T A[N];会产生两个效果：

  • 内存中会分配一个L * N字节的连续区域，L为数据类型T的大小
  • 引入标识符A，A可用于作为指向数组第一个元素的指针

对于数组访问A[i]，若A的地址存放于%rdx，i存放于%rcx则指令movl (%rdx, %rcx, 4), %eax能访问int类型数组第i个元素。

指针运算

  • 设指针p1、p2为指向类型T的指针，的值分别为xp1、xp2
    • p + i结果为xp + i * L
    • p1 - p2结果为(xp1 - xp2) / L: 指针的差结果类型为long，值等于两个地址之差除以数据类型的大小

嵌套数组

对于嵌套数组，机器级的实现仍使用连续的内存区域。数组元素按照行优先的顺序进行排列。这种排列顺序说明嵌套数组和嵌套声明等价。即int A[5][3]和下面的语句等价。

1
2
typedef int row3_t[3];
row3_t A[5];

对于嵌套数组元素访问的实现，对于T D[R][C];，数组元素D[i][j]的内存地址为D + L * ( i * n + j)。例如对于A[5][3]

1
2
3
4
// A in %rdi, i in %rsi, j in %rdx
leaq (%rsi, %rsi, 2), %rax // 跨行的元素数
leaq (%rdi, %rax, 4), %rax // 第i行行首位置
leaq (%rax, %rdx, 4), %rax // 行首到目标位置的偏移

1.1. 定长/变长数组机器级实现的优化

  • 定长数组
    • 使用指针替代i, j作为循环变量，并用指针加法替代索引访问
    • 循环的结束点使用一个指针固定值
  • 变长数组：从ISO C99开始引入了变长数组的功能，即数组可以在运行期指定长度T A[expr1][expr2];。变长数组能够作为局部变量或是函数参数（传指针）。

2. 结构体和联合的机器级实现

2.1. 结构

  • 按照内存地址自低到高结构体内部的各个成员按序占据着单个内存块
  • 编译器维护结构每个成员的类型信息，这些类型信息指示着字段偏移。通过将偏移作为内存引用指令中的位移，从而可以产生对结构元素的引用。
1
2
3
4
5
6
struct rec {
  int i;
  int j;
  int a[2];
  int *p;
}

若%rdi中保存r的指针，%rsi中保存了i。访问a[1]的指令leaq 8(%rdi, %rsi, 4), %rax

而对于访问r->p = r->a[r->i + r->j]，则需要

1
2
3
4
5
movl 4(%rdi), %rax
addl (%rdi), %rax
cltq
leaq 8(%rdi, %rax, 4), %rax
mov %rax, 16(%rdi)

2.1.1. 对齐

对齐的目的

  • 避免低效的对跨cache行(64字节)的数据块的读写
  • 避免低效的跨内存页数据的访问

对齐原则

  • 结构体内部:
    • 满足每个元素的对齐要求
      • 任何K字节的基本对象的地址必须是K的倍数
    • 汇编代码可以使用命令指明全局数据的对齐.align 8，则该命令之后的数据均按照8字节对齐
  • 整个结构体:
    • 每个结构体对象都有对齐要求K
      • K = Largest alignment of any element
    • 初始地址和结构长度必须是K的倍数
1
2
3
4
5
6
7
8
9
// 若只是单个S1类型的数据，则9字节即可
struct S1 {
  int a;
  int b;
  char c;
}
// 但是如下面的结构体数组
// 编译器会分配12字节，即在结构体末尾填充3字节以满足对齐
struct S1 d[4];

例子：对于下面的结构体数组的访问

1
2
3
4
5
6
// i [2bytes] v j [2bytes]
struct S3 {
  short i;
  float v;
  short j;
} a[10];

则a[idx].j能被翻译为

1
2
3
# %rdi = idx
leaq (%rdi, %rdi, 2), %rax # 3 * idx
movzwl a+8(, %rax, 4), %eax

2.2. 联合

联合绕过了类型系统提供的安全措施，允许使用多种类型引用同一个内存块。

节省内存

例如: 对于一个表示二叉树节点的结构体。对于叶子节点，有double类型的数据；对于内部节点，有左右指针。则可以用下面方式表示以节省内存：

1
2
3
4
5
6
7
8
9
10
11
12
typedef enum { N_LEAF, N_INTERNAL } nodetype_t;

struct node_t {
  nodetype_t type;
  union {
    struct {
      struct node_t *left;
      struct node_t *right;
    } internal;
    double data[2];
  } info;
}

访问不同数据类型的位模式

试想，如果我们想用unsigned long类型的位模式解释一个double类型的数据。

强制类型转换无法达到目的：

1
unsigned long u = (unsigned long) d;

但是可以使用联合达到要求：

1
2
3
4
5
6
7
8
unsigned long double2bits(double d) {
  union {
    double d;
    unsigned long u;
  } tmp;
  tmp.d = d;
  return tmp.u;
}

注：当使用联合表示多种大小不同的数据时，字节顺序会影响到结果。

1
2
3
4
5
6
7
8
9
double unsigned2double(unsigned word0, unsigned word1) {
  union {
    double d;
    unsigned u[2];
  } temp;
  temp.u[0] = word1;
  temp.u[1] = word0;
  return temp.d;
}

对于大端法，高位字节位于u[0]。对于小端法，低位字节位于u[0]。

3. 浮点数指令

3.1. 历史

  • x87 FP
  • SSE FP (Stream SIMD Extension)
    • 寄存器为16字节
  • AVX FP (Advanced Vector Extension)
    • 最新版本
    • 寄存器为32字节

3.2. 浮点数指令基础

  • 寄存器被称为MM，XMM对应低16字节，YMM对应这个32字节。共16个。
  • 既可以当作标量使用，也可以作为表示数组的向量使用（SIMD）
  • 后缀
    • sd，single double
    • ss, single float
  • 过程调用
    • 所有XMM寄存器都是调用者保存
    • 参数通过%xmm0, %xmm1传递
    • 返回值通过%xmm0返回
  • 内存引用
    • 整数和指针通过通过寄存器传递
    • 浮点数通过XMM寄存器传递
    • 不同的mov指令在xmm寄存器间和xmm寄存器和内存间移动