Katyusha's blog

数据格式#

最初的架构为16位，所以Intel用 字(word) 表示16位，32位为双字(double words/long word)，64位为四字(quad words)

GCC生成的部分汇编代码指令都带有一个字符后缀表示操作的大小，如movl表示传送双字

信息访问#

x86-64 CPU 中含有16个通用寄存器

8086中含有%ax到%sp8个通用寄存器 IA32将这8个寄存器扩展为32位 (%eax中的”e”) x86-64将寄存器扩展到64位(%rax中的”r”)，并采用新的命名方式增加8个寄存器(%r8～%r15，%r8d中的”d” words，%r8w中的”w”) 指令通过不同的后缀大小(b,w,l,q)，得以访问寄存器的不同最低字节(1,2,4,8) 小于8字节的数据传送到寄存器中时，若传送字节为1或2，则更高的字节不变；若传送字节为4，则更高的4个字节全置为0(IA32到x86-64扩展导致的)

操作数指示符#

将寄存器看做数组$R[]$，内存看做数组$M[]$

1. 立即数(immediate):$后面接常数 eg. $114514
2. 寄存器(register)<以指定寄存器的低位1>,2,4,8字节为操作数，返回寄存器中的值即$R[r_a]$ eg. %eax返回第一个寄存器的低32位
3. 内存引用：将内存看做很大的字节数组，根据计算的有效地址访问内存位置

内存引用的寻址模式：$Imm(r_b,r_i,s)$，其中$Imm$为立即数偏移，$r_b$和$r_i$为64位寄存器，$s$取1,2,4,8(默认为1) 有效地址被计算为$addr=Imm+R[r_b]+R[r_i]*s$，返回$M[addr]$

数据传送指令#

将数据从一个位置传送到另一个位置的指令

算术和逻辑操作#

四类操作：加载有效地址，一元操作，二元操作，移位 这里主要讨论leaq的64位形式；其他算术逻辑指令通常能用不同后缀(b,w,l,q)指示操作大小

条件码#

部分指令(如计算，比较和测试，移位等)会设置条件码 注：leaq计算地址，不会设置条件码

CMP，TEST进行类似于SUB和AND的计算，不同之处在于不会将结果写入目的位置，而只会设置条件码

通过CMP a, b可以得到$b-a$对应的条件码，从而判断$a$和$b$的相对大小；通过TEST a, a可以将$a$的零值和符号等特征反映到条件码中

访问条件码#

SET通过条件码的组合，将是否满足后缀条件(0/1布尔值)传送到一个低位字节中

如假设$a$存储在%rsi中，$b$存储在%rdi中，执行cmpq %rdi, %rsi后 setl %al表示将%rax的最低字节设置为$(bool) (a < b)$，结果字节为0或1

跳转指令#

将指令执行的顺序改变，跳转到一个指定的位置

格式类似C中的goto-label：

jmp被称为无条件跳转，其余被称为条件跳转 只有无条件跳转能执行间接跳转，如jmp *%rax跳转到%rax的值对应地址的指令，jmp *(%rax)跳转到%rax指向内存的值对应地址的指令

1
if (condition){
2
  a = if_expr;
3
}
4
else {
5
  a = else_expr;
6
}

1
int x = if_expr;
2
int y = else_expr;
3
a = condition? x:y;

循环#

将条件测试和跳转组合起来即可得到循环

do-while

while有两种形式

1. jump to middle(先进入循环，在循环中途再检查条件)

2.guarded-do(先检查条件，再进入循环)

for

注意：当在$body-statement$中存在$continue$语句时，$continue$应当跳转到$update-expr$部分，否则可能导致死循环等问题 现代编译器会根据循环特征自动选择最优的实现方式，并进行循环展开等优化

运行时栈#

在过程$Q$被执行时，其调用链上的所有信息的挂起在栈上，栈中存放着传递控制，传递数据，内存分配释放的信息 栈帧：过程在寄存器中存放不下，存放在栈中的空间 局部变量都可以存储在寄存器中并且为叶子过程(未调用其他过程的过程)，则不需要栈帧 注:%rsp为栈指针，％rip为PC

传递控制#

从过程$P$到过程$Q$ call Q将PC跳转到$Q$起始指令的地址，并将call指令的下一条地址(返回地址)压入栈中 ret从栈中弹出返回地址，并将PC设置为返回地址

传递数据#

$x86-64$架构中最多可以用6个寄存器来传送参数

当传递的参数大于6时，需要通过栈来进行传送(参数构造区)

eg.

注：通过栈传送数据时，第7个及以后的参数按从右到左的顺序压入栈中，第7个参数在栈顶（低地址），后续参数依次向高地址排列

内存的分配与释放#

当寄存器不足以存放局部数据，或者局部数据被取地址(&)需要被分配地址时，会在栈上为这个数据分配空间，形成局部变量

eg.

其中：

1. x1 x2 x3被取地址，作为局部变量在栈上分配空间，同时也属于前6个参数，传入寄存器
2. &x1 &x2 &x3属于前6个参数，传入寄存器，又未在该过程后续被直接使用，不是局部变量
3. x4被取地址，作为局部变量在栈上分配空间，同时也在栈上再次分配一个不同的空间，传送这个参数
4. &x4通过在栈上分配空间作为参数传送，但不是局部变量

在执行call proc时，会在栈中压入长8个字节的返回地址，使得$x4$和&x4相对栈的地址偏移量变为8和16个字节，proc过程得以正确执行 注意： 栈帧内存的释放只是改变了栈指针，没有改变曾经的参数和局部变量的值，意外访问这些位置可能读到旧数据

递归过程#

每个过程相关信息在栈上都有私有空间，互不干扰，使得递归能够高效而正确地实现

eg.

当递归调用是函数体中最后执行的操作时，编译器可能进行尾递归优化，将其转换为循环

定长数组与变长数组#

编译器对定长数组(数组大小为常量)的优化： 通过指针加减移动进行寻址，而非用乘法进行寻址，提高寻址的效率

对于变长数组(数组大小为表达式)：

由于数组的大小不确定，无法使用leaq，需要使用imul，时间开销更大，但编译器仍然尽量使用指针提高效率

struct 结构#

同一结构内的变量都分配在连续的内存中 eg.

1
struct str{
2
  int l, r;
3
  long long val;
4
}s;

其中s是一个结构体对象；若%rdx中存放的是指向s的指针，则通过8(%rdx)即可以访问s.val

联合 union#

eg.

1
struct node_t {
2
  nodetype_t type;
3
  union {
4
    struct {
5
      node_t *left;
6
      node_t *right;
7
    } internal;
8
    double data[2];
9
  } info;
10
};

其中，internal与data[2]互斥 (若为叶子节点则只有两个值，没有儿子指针；若不是叶子节点，则有两个儿子指针，无权值) union的大小为其中最大变量的大小，如以上的union中所占大小为16，通过union节省了空间

同时，union也可以实现保持位模式相同的类型转换

1
double x = 114514.1919810;
2
unsigned val = (unsigned)x;

这是普通数值转换：浮点数会向零舍入；如果超出unsigned可表示范围，行为不由C标准保证

1
union{
2
  double x;
3
  uint64_t val;
4
}u;
5
u.x = 114514.1919810;
6
uint64_t val = u.val;

通过union，可以观察同一段存储的位模式；这里用64位整数保存double的完整二进制串，数值含义会发生改变

数据对齐#

对于结构体中的变量，编译器通过数据对齐保证其地址为$K$的倍数($K=1,2,4,8$)，进而提高访问的效率 例如假设处理器每次操作从内存中取8个字节，对$double$进行字节对齐，使其不会落在两个不同的内存块中，保证了读写时处理器只会访问一个内存块，进而保证了操作的高效

字节对齐按以下步骤进行：

1. 对于结构内的某个变量，在其后面的地址连续填充空隙，直到下一个地址满足下一个变量所需的对齐约束，再将下一个变量放入这个地址中
2. 设$M$为结构内所有变量的最大对齐要求，在最后一个变量之后连续填充空隙，直到结构体总大小为$M$的倍数

eg.

1
struct str{
2
  int a;
3
  char b;
4
  int c;
5
  char d;
6
};

其对齐后的结果为： a: 0～3 b<4>～4 空隙<5>～7 c<8>～11 d<12>～12 空隙<13>～15

杂项#

浮点代码 (AVX2)#

“我们不太清楚GCC为什么会生成这样的代码，这样做既没有好处，也没有必要在XMM寄存器中把这个值复制一遍” 看破防了，感觉CSAPP也是讲得稀里糊涂的，以后再补