liujiyu
Liujiyu's blog
learn & record

CSAPP-2-2:程序的机器级运行控制

程序的机器级表示

控制

C语言程序中存在有条件的执行语句，例如条件语句、循环语句和分支语句，机器代码提供两种基本的低级机制来实现有条件的行为：测试数据值，然后根据测试的结果来改变控制流或者数据流，

条件码

除了整数寄存器，CPU还维护着一组单个位的条件码(condition code)寄存器，它们描述了最近的算术或者逻辑操作的属性，最常用的条件码有：

  1. CF：进位标志。最近的操作使最高位产生了进位，可用来检查无符号操作的溢出。
  2. ZF：零标志。最近的操作得出的结果为0。
  3. SF：符号标志。最近的操作得到的结果为负数。
  4. OF：溢出标志。最近的操作导致一个补码溢出—-正溢出或负溢出。

例如，假设我们用一条ADD指令完成t=a+b的功能，则会根据下面的C表达式来设置条件码：

注意有几个特殊情况：

  1. leaq指令不会改变任何条件码，除此之外，所有一元二元指令都会设置条件码。
  2. 对于逻辑操作，例如XOR，进位标志和溢出标志会设置为0。
  3. 对于移位操作，进位标志将设置为最后一个被移除的位，而溢出标志设置为0。
  4. INC和DEC会设置溢出和零标志，但不会改变进位标志。

除了算术和逻辑操作，还有两类指令会设置条件码，它们只设置条件码而不改变任何其他寄存器：

  1. CMP指令根据两个操作数之差来设置条件码。除了不更新目的寄存器之外，行为与SUB指令一致，常用来比较大小。
  2. TEST指令与AND指令的行为一样，除了不改变目的寄存器的值。典型的用法是两个操作数是一样的，或者其中操作数是一个掩码用来指示哪些位应该被测试（例如，testq %rax,%rax用来检查%rax是负数、零还是正数）。

访问条件码

条件码通常不会直接读取，常见的使用方法有三种：

  1. 可以根据条件码的某种组合，将一个字节设置为0或1。
  2. 可以条件跳转到程序的某个其他的部分。
  3. 可以有条件的传送数据。

针对第一种情况，我们将这一整类指令称为SET指令，它们的区别就在于他们考虑的条件码组合是什么，此时后缀表示不同的条件而不是操作数大小。

一个SET指令的目的操作数是低位单字节寄存器之一，或者是一个字节的内存为止，指针会将这个字节设置成0或1。为了得到一个32位或64位结果，必须对高位清零，例如a<b的指令序列如下：

虽然所有的算术和逻辑操作都会设置条件码，但是所有SET指令的描述都适用的情况是：执行比较命令，根据计算t=a-b设置条件码。

考虑setl指令测试一个有符号比较，当没有发生溢出时（OF设置为0的时候表示无溢出），我们有当 $ a-_w^tb<0 $时有 $a<b$，将SF设置为1可以表明这一点，而当$ a-_w^tb\geq 0 $时有 $a<geq b$，此时SF将置为0，因此有上表setl的效果，并且由setl可以推导出其他三个。

对于无符号比较的测试，当 $a<b$时，CMP指令会设置进位标志，因而无符号比较使用的是进位标志和零标志的结合。

跳转指令

正常执行的情况下，指令会一条一条按顺序执行下去，跳转指令会导致执行切换到另一个全新的位置。在汇编代码中，这些跳转的目的地通常用一个标号(label)指明，例如：

在产生目标代码文件时，汇编器会确定所有带标号指令的地址，并将跳转目标（目的指令的地址）编码为跳转指令的一部分。

下图列举了不同的跳转指令，jmp为无条件跳转，他可以是直接跳转，即跳转目标是作为指令的一部分编码的，也可以是间接跳转，即跳转目标是从寄存器或内存位置中读出的，例如 jmp *&rax是用寄存器中的值作为跳转目标，jmp *(%rax)以%rax中的值作为读地址，再从内存中读出跳转目标。

跳转指令的编码

在汇编代码中，跳转指令用符号标号书写，汇编器及后来的链接器会产生跳转目标的适当编码。跳转指令有几种不同的编码，但最常用的都是 PC相对的(PC-relative)。 也就是，它们会将 目标指令的地址与紧跟在跳转指令后面那条指令的地址之间的差作为编码。 这些地址偏移量可以编码为1,2,4个字节。第二种编码方法就是给出“绝对”地址，用4个字节直接指定目标，汇编器和链接器会选择会选择适当的跳转目的编码。

下面是一个PC相对寻址的例子，第2行的jmp指令向前跳转到更高的地址，第7行的jg指令向后跳转到更低的地址：

每个16进制两位数都是1个字节，第二行中跳转目标指明为 loop+0x5+0x3，第五行中为loop+0xd-0x8，都是下一条指令的地址的相对位置。

用条件控制实现条件分支

C语言中的if-else语句的通用形式模板如下：

if (test-expr)
    then-statement
else
    else-statement

汇编实现如下：

我们可以使用goto风格代码来更好地理解，这里注意汇编中条件跳转的参数与C语言中是相反的：

还有一个例子：

void cond(long a, long *p){
    if(p && a>*p)
        *p=a;
}

汇编语言为

cond:
    testq %rdi, %rdi
    jz .L2
    cmpq %rsi, (%rdi)
    jle .L2
    movq %rsi, (%rdi)
.L2:
    ret

由于&&有短路性质，所以一个if语句在汇编中却有两个条件分支。

用条件传送来实现条件分支

实现条件操作的传统方法是 通过使用控制的条件转移，当条件满足时程序沿着一条执行路径执行，否则走另一条路径。这种机制简单通用但是可能会低效。

一个替代的策略是使用数据的条件转移，这种方法计算一个条件操作的两种结果，然后再根据条件是否满足从中选取一个。下面是一个例子，注意也是求相反的结果：

首先了解一下现代处理器如何运行，处理器通过使用流水线来获得高性能，一条指令的处理要经过一系列的阶段，例如从内存读指令，确定指令，从内存读数据，执行运算，写数据，更新计数器等。这种方法通过重叠连续指令来获得高性能，例如在取一条指令的同时执行前一条命令的算术运算。那就要实现确定要执行的指令序列才能保持流水线充满待执行的指令。

当机器遇到条件跳转的时候，处理器会采用非常精密的分支预测逻辑来猜测每条跳转指令是否会执行，如果猜错了就要求处理器丢掉它为该跳转指令后所有指令已做的工作，再从正确的位置处填充流水线，这会导致性能严重下降。

下面是一些可用的条件传送指令，源和目的的值可以是16、32、64位，但不支持单字节的条件传送。无条件传送需要将操作数长度显式编码在指令名中，但条件传送中汇编器可以从目标寄存器的名字来推断操作数长度，因此可以使用同一个名字。

同条件跳转不同，处理器无需预测测试结果就可以执行条件传送，在下一章会讨论它的实现。

但是不是所有的条件表达式都可以用条件传送来编译：

  1. 如果这两个表达式中的任意一个可能产生错误条件或者副作用，就会导致非法的行为： 例如，考虑下面这个C函数 
     long cread(long *xp){
     return (xp ? *xp : 0);
 }

    对应的条件传送如下：

     xp in register %rdi.
 cread:
     movq (%rdi), %rax
     testq %rdi, %rdi
     movl $0, %edx
     cmove %rdx, %rax
     ret

    此时会出现间接引用空指针的错误。

  2. 如果两个操作都需要花费大量的运算，那就不会使用条件传送。
  3. 执行任意分支可能会改变程序其他部分的状态时不会使用条件传送，例如 
     val = x>0 ? x*=7 : x+=3;

下面是除以2的幂次的例子：

通过右移来实现，如果x小于0需要加$2^k-1$再进行右移。

循环

C语言三中循环： do-while, while 和 for：

  1. do-while循环： do-while循环的通用形式为： 
     do
     body-statement
     while(test-expr)

    汇编形式为：

     loop:
     body-statement
     t = test-expr
     if (t)
         goto loop

    下面是阶乘计算的例子：

  2. while循环： while语句有两种生成方法：

    1. 第一种称之为jump to middle，这个是GCC带优化命令选项-Og时采用的翻译方法，可以翻译为：

       goto test;
 loop:
     body-statement
 test:
     t = test-expr;
     if (t)
         goto loop;

    2. 第二种翻译方法称为guarded-do，首先用条件分支，如果初始条件不成立就跳过循环，把代码变换为do-while循环，这是采用较高优化等级-O1才会采用的策略：

       t = test-expr
 if (t)
     goto done;
 loop:
     body-statement;
     t = test-expr;
     if(t)
         goto loop;
 done:
     ret

  3. for循环： for循环的通用形式为

     for(init-expr; test-expr; update-expr)
     body-statement

    这样一个循环的行为与下面这段代码的行为一样：

     init-expr;
 while (test-expr) {
     body-statement
     update-expr;
 }

    再利用while循环翻译为汇编语言。

     long fun_b(unsigned long x){
     long val = 0;
     long i;
     for(i = 64; i!=0; i--){
         val = (val << 1) | (x & 1);
         x >>= 1;
     }
     return val;
 }

    汇编代码为：

     fun_b:
     movl $64, %edx
     movl $0. &eax
 .L10:
     movq %rdi, %rcx
     andl $1, %ecx
     addq %rax, %rax
     orq %rcx, %rax
     shrq $1, %rdi
     subq $1, %rdx
     jne .L10
     rep; ret

    因为64不为0，所有初始测试直接被忽略了。这个函数的行为是将x的位反过来，只需每次取x的最低位放进val低位，每次val左移，x右移。

switch语句

switch语句不仅提高了C代码的可读性，而且通过使用跳转表使得实现更加高效。跳转表是一个数组，表项i是一个代码段的地址，当开关索引值等于i时程序采用对应的动作。它的优点在于：执行开关语句的时间与开关情况的数量无关。当开关情况数量比较多并且值的跨度范围比较小时就会使用跳转表。

这个例子中包括case label跨过一个不连续区域（101，105没有标号）、有多个标号（104，106）、有些情况会落入其他情况之中（102），因为没有break语句结尾。

可以看到，编译器首先将n减去100，把取值范围移到0-6之间，创建一个新的程序变量index，注意它是无符号值，这样我们可以通过测试index是否大于6来判定index是否在0-6之间，如果小于0的话根据补码性质也还是大于6的。根据index值有五个不同的跳转位置，loc_A(.L3)，loc_B(.L5)，loc_C(.L6)，loc_D(.L7)，loc_def(.L8)，最后一个是默认的目的地址。

执行switch语句的关键步骤是通过跳转表来访问代码位置，在汇编第五行以及goto代码中的第16行，jmp指令的操作数有前缀*，表明这是一个间接跳转，操作数指定一个内存为止，索引由寄存器%rsi给出，这个寄存器保存着index的值。

C代码将跳转表声明为一个7个元素的数组，每个元素都是一个指向代码位置的指针，可以发现，对于重复情况的处理就是对4和6采用同样的代码标号，对于确实情况的处理就是对1和5采用默认情况的标号。对于fall through的情况就是对应的代码位置也是fall through的。

在汇编中表示如下：

其中.rodata为只读数据，其中包含一组7个四“字”（8个字节），每个字的值都是与指定的汇编代码标号相关联的指令地址。

Table of Contents