课程主页：http://www.cs.cmu.edu/afs/cs/academic/class/15213-f15/www/schedule.html

课程资料：https://github.com/EugeneLiu/translationCSAPP

课程视频：https://www.bilibili.com/video/av31289365/

这一讲介绍了机器级编程4：数据。

数组

  • 基本原则
    • T A [L];
    • 上述声明表示数据类型为T，长度为L的数组
    • 内存中是L*sizeof(T)个字节的连续分配区域

数组读取的例子

#define ZLEN 5
typedef int zip_dig[ZLEN];
zip_dig cmu = { 1, 5, 2, 1, 3 };
zip_dig mit = { 0, 2, 1, 3, 9 };
zip_dig ucb = { 9, 4, 7, 2, 0 };

int get_digit(zip_dig z, int digit)
{
	return z[digit];
}

IA32

# %rdi = z
# %rsi = digit
movl (%rdi,%rsi,4), %eax # z[digit]
  • 寄存器％rdi包含数组的起始地址
  • 寄存器％rsi包含数组索引
  • 所需数字位于％rdi + 4*％rsi
  • 使用内存引用(％rdi，％rsi，4)

数组循环例子

void zincr(zip_dig z) {
  size_t i;
  for (i = 0; i < ZLEN; i++)
    z[i]++;
}

反汇编的结果为

  # %rdi = z
  movl    $0, %eax          #   i = 0
  jmp     .L3               #   goto middle
.L4:                        # loop:
  addl    $1, (%rdi,%rax,4) #   z[i]++
  addq    $1, %rax          #   i++
.L3:                        # middle
  cmpq    $4, %rax          #   i:4
  jbe     .L4               #   if <=, goto loop
  rep; ret

多维（嵌套）数组

  • 声明
    • T A [R] [C];
    • 数据类型为T的2D数组
    • R行，C列
    • 类型T元素需要K个字节
  • 数组大小
    • $\text{R} \times \text{C} \times \text{K}$字节
  • 内存安排
    • 按行排列

嵌套数组例子

#define PCOUNT 4
zip_dig pgh[PCOUNT] = 
  {{1, 5, 2, 0, 6},
   {1, 5, 2, 1, 3 },
   {1, 5, 2, 1, 7 },
   {1, 5, 2, 2, 1 }};

内存中的结果

  • “zip_dig pgh [4]”等价于“int pgh [4] [5]”
    • 变量pgh：4个元素的数组，内存中连续分配
    • 每个元素都是5个int的数组，内存中连续分配
  • 内存中所有元素都是按行排列

嵌套数组读取

嵌套数组行的读取
  • 行向量
    • A[i]是C个元素的数组
    • 类型T的每个元素需要K个字节
    • 起始地址为$\text{A} + \text{i} \times(\text{C} \times \text{K})$

例如$\text{int A[R][C]}$

考虑如下代码

int *get_pgh_zip(int index)
{
  return pgh[index];
}
# %rdi = index
leaq (%rdi,%rdi,4),%rax	# 5 * index
leaq pgh(,%rax,4),%rax	# pgh + (20 * index)
  • 行向量
    • pgh[index]是5个整数的数组
    • 起始地址$\text{pgh + 20} \times \text{index}$
  • 机器码
    • 计算并返回地址
    • 计算方式为$\text{pgh} + 4 \times (\text{index} + 4 \times \text{index})$

嵌套数组元素访问

  • 数组元素
    • A[i][j]是类型T的元素，需要K个字节
    • 地址为$\text{A + i} \times \text{(C} \times \text{K)} + \text{j} \times \text{K} = \text{A} + (\text{i} \times \text{C} + \text{j})\times \text{K}$

例如$\text{int A[R][C]}$

考虑如下代码

int get_pgh_digit
  (int index, int dig)
{
  return pgh[index][dig];
}
leaq	(%rdi,%rdi,4), %rax	# 5*index
addl	%rax, %rsi	# 5*index+dig
movl	pgh(,%rsi,4), %eax	# M[pgh + 4*(5*index+dig)]
  • 数组元素
    • pgh[index] [dig]是int
    • 地址：$\text{pgh + 20} \times \text{index + 4} \times \text{dig = pgh + 4} \times \text{(5} \times\text{index + dig)}$

多级数组例子

zip_dig cmu = { 1, 5, 2, 1, 3 };
zip_dig mit = { 0, 2, 1, 3, 9 };
zip_dig ucb = { 9, 4, 7, 2, 0 };

#define UCOUNT 3
int *univ[UCOUNT] = {mit, cmu, ucb};
  • 变量univ表示由3个元素组成的数组
  • 每个元素都是一个指针
    • 8字节
  • 每个指针都指向int数组

多级数组读取

int get_univ_digit
  (size_t index, size_t digit)
{
  return univ[index][digit];
}
salq    $2, %rsi            # 4*digit
addq    univ(,%rdi,8), %rsi # p = univ[index] + 4*digit
movl    (%rsi), %eax        # return *p
ret
  • 计算方式
    • 元素访问$\text{Mem[Mem[univ + 8} \times \text{index] + 4} \times \text{digit]}$
    • 必须做两次内存读取
      • 首先获取指向行数组的指针
      • 然后访问数组中的元素

还有一些例子这里从略。

结构

结构表示

struct rec {
    int a[4];
    size_t i;
    struct rec *next;
};

  • 结构表示为内存块
    • 足够容纳所有的字段
  • 根据声明的顺序安排字段
    • 即使另一个排序可以产生更紧凑的表示
  • 编译器确定整体大小+字段位置
    • 机器级程序不了解源代码中的结构

结构和对齐

struct S1 {
  char c;
  int i[2];
  double v;
} *p;
  • 没有对齐的数据

  • 对齐的数据
    • 原始数据类型需要K个字节
    • 地址必须是K的倍数

对齐原则

  • 对齐数据
    • 原始数据类型需要K个字节
    • 地址必须是K的倍数
    • 在某些机器上是必需的； x86-64上被建议使用
  • 对齐数据的动机
    • 通过（对齐的）4或8个字节的块访问内存（取决于系统）
    • 加载或存储跨越四字边界的数据效率低下
    • 当数据跨越2页时，虚拟内存会更复杂
  • 编译器
    • 在结构中插入间隙以确保正确对齐字段

对齐的特定情况（x86-64）

  • 1个字节：char，…
    • 地址无限制
  • 2个字节：short，…
    • 地址的最低1位必须为$0_2$
  • 4个字节：int，float等
    • 地址的最低2位必须为$00_2$
  • 8个字节：double，long，char *，…
    • 地址的最低3位必须为$000_2$
  • 16个字节：long double（Linux上的GCC）
    • 地址的最低4位必须为$0000_2$

节省空间

  • 将较大的数据放在前面

    struct S4 {
  char c;
  int i;
  char d;
} *p;
    struct S5 {
  int i;
  char c;
  char d;
} *p;

  • 有效位数($K=4$)

浮点数

背景

  • 历史
    • x87 FP
      • 旧版，非常难看
    • SEE FP
      • Shark machines（CMU的虚拟机）支持
      • 特殊情况使用矢量指令
    • AVX FP
      • 最新版本
      • 类似于SEE FP

SSE3

XMM寄存器

  • 总共16个，每个16个字节

基本操作

FP基础

  • 参数传入％xmm0，％xmm1 …
  • 结果以％xmm0返回
  • 所有XMM寄存器均已保存caller

例子

float fadd(float x, float y)
{
    return x + y;
}
# x in %xmm0, y in %xmm1
addss   %xmm1, %xmm0
ret
double dadd(double x, double y)
{
    return x + y;
}
# x in %xmm0, y in %xmm1   
addsd   %xmm1, %xmm0
ret

FP内存引用

  • 在常规寄存器中传递的整数（和指针）参数
  • XMM寄存器中传递的FP值
  • 在XMM寄存器之间以及在存储器和XMM寄存器之间使用不同的mov指令
double dincr(double *p, double v)
{
    double x = *p;
    *p = x + v;
    return x;
}
# p in %rdi, v in %xmm0
movapd  %xmm0, %xmm1   # Copy v
movsd   (%rdi), %xmm0  # x = *p
addsd   %xmm0, %xmm1   # t = x + v
movsd   %xmm1, (%rdi)  # *p = t
ret

总结

  • 数组
    • 元素打包到内存的连续区域
    • 使用索引计算来定位单个元素
  • 结构体
    • 元素打包到单个内存区域
    • 使用编译器确定的偏移量进行访问
    • 可能需要内部和外部填充以确保对齐
  • 组合方式
    • 可以任意嵌套结构和数组代码
  • 浮点
    • 在XMM寄存器中保存和操作的数据