CSAPP 第三章 汇编指令 – 条件分支

控制语句就是分支,和循环. 今天先来看看分支的相关指令.

1. 条件判断: 条件码
2. 条件判断: 跳转指令
3. 条件判断: 条件传送

条件码

条件码是一些特殊的寄存器, 在每次算术或者逻辑运算之后更新, 也有特殊的指令可以操作这些寄存器. 很多条件分支指令, 就是通过检测这些寄存器的值来实现的.

常用的条件码有:

1. CF 进位标志, 最近的操作使最高位产生进位
2. ZF 零标志, 最近的操作的结果得到0
3. SF 符号标志, 最近的操作结果是负数
4. OF 溢出标志, 最近的操作导致补码溢出,正负溢出都算

在上一节里的所有算术操作的指令, 除了 leaq之外, 其结果都会自动更新这几个寄存器的值.

除了这些算术操作,还有两个特殊的指令CMP和TEST, 这两个指令不会更改任意一个操作数对应的寄存器或者内存值, 只会根据操作结果更新条件码.

1. CMP S1, S2, 计算S2-S1的结果, 根据结果更新条件码. 即如果S1=S2, 零标志会被设置为1, 如果不相同, 则可以利用其它标志判断两数大小关系.
2. TEST S1, S2, 计算S2&S1的结果, 根据结果更新条件码. 常用的套路是两个操作数一样, 这样就可以通过条件码得到这个数是正数,零还是负数.

条件码寄存器通常不会直接读取, 而是依靠一个指令SET. 该指令根据当前条件码寄存器的各种组合方式, 将一个字节设置为0或者1. 注意这个指令的操作数只能是一个字节或者寄存器的单字节版本. 如果要得到32或者64位结果,
要先把其他位置清零.

SET类指令的后缀的意思不再是长度,而是某些条件. 条件比较多, 用到的时候可以查询.

指令	同作用的其他指令	效果
sete D	setz	相等, ZF = 0的时候, 设置D为1. 以下都是当条件成立的时候设置为1, 否则设置为0
setne	setnz	不相等, ZF不等于0
sets		SF表示结果为负数
setns		SF结果为非负数
setg	setnle	有符号的大于
setge	setnl	有符号的大于等于
setl	setnge	有符号的小于
setle	setng	有符号的小于等于
seta	setnbe	无符号大于
setae	setnb	无符号大于等于
setb	setnae	无符号小于
setbe	setna	无符号小于等于

一个简单的比较第一个参数是否小于第二个参数的程序:

int comp(long a, long b){
    return a < b;
}
// a in %rdi, b in %rsi

写成汇编如下:

comp:
    cmpq %rsi %rdi  被减数最后, 减数在前, 这条执行的是 a - b. 其实也可以认为 compq s1 s2 等于比较s2和s1,后边的条件大于就是指的s2>s1,以此类推
    setl %al        上一条指令执行完之后条件码更新, 如果a-b<0, 根据条件码设置%rax寄存器的最低字节为1. 如果不满足条件, 就设置0.
    movbl %al %eax  将%al零扩展更新到32位寄存器, 同时把高位清0. 这里返回的是int, 32位字节足够. 但是也一样会高位清0.
    ret

练习3.13 找出汇编代码对应的原来的数据类型

1.     cmpl  %esi, %edi
       setl  %al
   

   首先这是一个比较32位的指令, 然后调用的是有符号的小于比较, 所以应该是两个有符号数进行比较. 由于一方有无符号就是无符号比较, 因此不能是无符号的32位. 由于两个数据类型相同, 应该是int 与 int

2.     cmpw  %si, %di
       setge %al
   

   这是一个比较字的大小, 就是16位长度, 然后是有符号大于等于.因此也不是无符号数字. 所以是 short 类型

3.     cmpb  %sil, %dil
       setbe %al
   

   这个指令比较字节大小, 然后是无符号比较. 由于无符号数参与比较会转换另外一个为无符号数, 所以是 unsigned char

4.     cmpq  %rsi, %rdi
       setne %al
   

   比较64位长度, 然后判断是否不相等. 由于无符号比较会互相转换, 因此数据类型可能为 char*, long, unsigned long

练习3.14 找出汇编代码对应的数据类型

int test(data_t a){
    return a TEST 0;
}

针对这个伪代码, 判断下列汇编语句对应的data_t的数据类型:

1.     testq  %rdi, %rdi
       setge  %al
   

   这个例子就是自己和自己与, 然后调用有符号, 那应该就是 long 类型

2.     testw  %di, %di
       sete   %al
   

   16位长, 是否等于0, 这个和符号无关, 因此可以是 short 或者 unsigned short

3.     testb  %dil, %dil
       seta   %al
   

   一个字节长度, 使用无符号比较, 则应该是 unsigned char

4.     testl  %edi, %edi
       setle  %al
   

   双字长度, 32位. setle是带符号的小于, 所以是 int

跳转指令

跳转指令就是jmp指令, 其后的操作数有两种: 一是标号, 会被汇编器转成对应汇编指令的地址, 这是直接跳转; 还一种是间接跳转, 即寄存器或者内存的值, 表示跳转到该位置.

两种指令的写法是:

1. jmp .L1, 跳转到 L1 标号
2. jmp *%rax, 跳转到%rax的值代表的目标
3. jmp *(%rax), 跳转到%rax中的指针指向的内存地址中的的目标

这里的目标也是一个数字, 但不是用来解释成内存地址, 而是一个程序计数器的指向.

除了jmp指令之外, JUMP类的其他指令是根据条件码来跳转, 条件跳转只能是直接跳转, 不能是间接跳转.

JUMP类指令如下:

指令	同义名	跳转条件
jmp Label	直接跳转	无条件跳转
jmp *操作数	间接跳转	无条件跳转
je Label	jz	相等或者为0时跳转, 只能间接跳转, 下同, 都省略Label字样
jne	jnz	不相等, 非0的时候跳转
js		为负数的时候跳转
jns		非负数的时候跳转
jg	jnle	大于的时候跳转
jge	jnl	大于等于的时候跳转
jl	jnge	小于的时候跳转
jle	jng	小于等于的时候跳转
ja	jnbe	无符号大于的时候跳转
jae	jnb	无符号大于等于的时候跳转
jb	jnae	无符号小于的时候跳转
jbe	jna	无符号小于等于的时候跳转

跳转的目标究竟是什么, 非常重要. 在汇编代码中, 一般直接跳转的目标用符号书写, 会被最终转换成与程序计数器相对的编码, 可能是目标指令所在的地址与跳转指令后边那条指令地址的差, 也可能是绝对地址, 直接指定程序计数器的值.

所谓程序计数器相对的编码, 在执行跳转指令的时候, 程序计数器指向的是下一条的地址, 因此只需要给出要跳转到的地址与下一条地址之间的偏移量即可. 之后用下一条指令的地址 与 跳转值进行计算就可以得到要跳转的地方.

而jmp 指令之后接的大小数字, 要按照补码的形式去解释.

练习 3.15 跳转的目标

1.             400f3a: 74 02   je XXXX
               4003fc: ff d0   callq *%rax
   

   可以看到74指令之后接着02, 表示下一行指令的地址+2 , 即 0x4003fc+2 = 0x4003fe

2.             40042f: 74 f4   je XXXX
               400431: 5d      pop %rbp
   

   可以看到74指令之后接着f4, 表示下一行指令的地址为补码的-12 , 即 0x400431 – 12 = 400425

3.             XXXXXX: 77 02   ja 400547
               XXXXXX: 5d      pop %rbp
   

   先算出下一行指令的地址, 为400547-2 = 0x400545
   由于跳转指令是两字节, 所以跳转指令的地址是 0x400545-2 = 0x400543

4.             4005e8: e9 73 ff ff ff   jmpq XXXXXXXX
               4005ed: 90               nop
   

   73 ff ff ff 的小端法补码表示的是十进制-141, 然后用4005ed – 141 = 0x400560

C语言的条件分支加上Goto语句, 可以很方便的对应到汇编的条件分支上, 普遍用的套路是测试一个表达式, 然后根据表达式的结果进行跳转即可.

练习 3.16 写出汇编风格的C代码

//在 a 大于 p 指针指向的数值的时候, 将数值更新为 a
void cond(long a, long *p){
    if(p && a > *p){
        *p = a;
    }
}

对应的汇编是:

a in %rdi, p in %rsi
cond:
    testq  %rsi, %rsi  测试 p
    je     .L1         如果是0就跳转到L1标号

    compq  %rdi, (%rsi)  比较*p 和 a
    jge    .L1           如果*p >= a, 即不满足 a > *p,跳转到L1标号

    movq   %rdi, (%rsi)  *p = a
  .L1:
    rep; ret

这个按照汇编来可以写出相应的C代码, 由于条件本身还需要一次逻辑运算, 所以实际上会有两条比较语句, 一条用来测试指针是否为0, 另外一条用来比较 a 和 *p 的值:

void cond_assembly(long a, long *p){
    if(!p)
        goto ends;
    if(a <= *p)
        goto ends;
    *p = a;

  ends:
    return;
}

练习题 3.17 按照新套路重写函数

long absdiff_se(long x, long y) {

    long result;

    if (x < y)
        goto true;
    ge_cnt++;
    result = x - y;
    goto done;

    true:
    lt_cnt++;
    result = y - x;

    done:
    return result;
}

由于一开始的测试表达式是 x < y, 就直接使用这个表达式, 判断为true的时候到true标号, 接下来处理false的部分, 最后都跳转到 done标号来返回结果.

练习题 3.18 根据汇编编写C代码

汇编代码如下, 三个参数x, y, z按顺序依次放在 %rdi, %rsi, %rdx中:

test:
    leaq  (%rdi, %rsi), %rax   这行等于long temp1 = x + y
    addq  %rdx, %rax           这行等于temp1 = temp1 + z
    cmpq  $-3, %rdi            这行等于是比较 x 和 -3
    jge   .L2                  jge表示有符号大于等于, 然后跳转到 .L2标号, 结合上一条指令就表示  x >= 3 的时候跳转. 则往下的部分就是 x<3的情况对应的代码

    现在已知: .L2处理 大于等于3的情况. 以下处理x < 3的情况

    cmpq  %rdx, %rsi           比较y:z
    jge   .L3                  表示 y >= z , 跳转到 .L3标号 往下的部分就是 x<3 且 y<z的情况
    movq  %rdi, %rax           把%rdi的值也就是x 放到temp 中, 即 temp1 = x
    imulq %rsi, %rax           然后temp1 = temp1 * y
    ret                        返回%rax中的值, 此时等于 x * y

  .L3:
    movq  %rsi, %rax           此时x<3 ,y>z, 这条指令让 temp1 = y
    imulq %rdx, %rax           temp1 = temp1 * z
    ret                        此时返回值是 y*z

  .L2:
    cmpq  %2, %rdi             进到L2分支的条件是 x>=3, 此时再比较 x:2
    jle   .L4                  如果x<=2, 直接到L4
    movq  %rdi, %rax           temp1 = x
    imulq %rdx, %rax           temp1 = x * z
  .L4
    rep; ret

然后写出这个代码

long test(long x, long y, long z){
    long val = x + y + z;
    if(x<-3){
        if(y<z){
            val = x * y;
        } else {
            val = y * z;
        }
    } else if(x>2){
        val = x * z;
    }
    return val;
}

条件传送

所谓条件传送, 就是测试条件码满足情况的时候, 使用传送指令相同的效果来操作值. 采用条件码分支对于现代CPU效率比较低, 所以会提前计算出结果的值然后进行分支预测.

既然都计算出结果的值了, 那么使用条件传送就会简便一些. 不过条件传送在求值的时候可能引发副作用或者异常的时候, 就不能使用了, 此时就必须使用条件传送.

条件传送的指令有两个操作数, 第一个操作数是寄存器或者内存地址, 第二个操作数必须是寄存器. 而且源和目的值必须是16位, 32位或者64位, 不能传送字节. 这是和普通传送指令有区别的地方.

练习题 3.19 分支预测惩罚计算

分支行为可预测的执行时间是16个时钟周期, 模式随机的时候大概是31个时钟周期, 计算预测错误处罚的时钟周期, 和函数的执行周期

设预测错误的时钟周期是x, 则预测错误的时候, 实际执行时间是16+x, 模式随机的时候各有50%的概率执行, 则可以得到:

0.5 * 16 + 0.5 * (16 + x) = 31

可以得到 x = 30, 即预测错误处罚的时间是30个时钟周期. 函数分支预测错误的时候, 执行周期 = 16+30 = 46

练习题 3.20 补充宏定义

#define OP

long arith(long x){
    return x OP 8;
}

x在%rdi寄存器中. 对应的汇编代码如下:

arith:
    leaq    7(%rdi), %rax    long temp = x+7
    testq   %rdi, %rdi       测试 x
    cmovns  %rdi, %rax       x 非负数的情况下, 传送 x 到 %rax 中, 即temp = x
    sarq    $3, %rax         把 temp 算术右移3位
    ret

从分析来看可以知道, 这段代码的核心分支是 x 非负数就把x右移3位, 如果x是负数, 就把 x+7 的结果右移3位.

所以可以发现宏应该是 x >= 0? x+7:x /

练习 3.21 补充C代码

有一个函数: 两个long类型参数, x 在 %rdi 寄存器, y 在 %rsi 寄存器.

test:
    leaq    0(,%rdi,8), %rax    long temp = 8 * x
    testq   %rsi, %rsi          测试y
    jle     .L2                 y小于或等于0, 这个是什么意思. 之后跳转
    movq    %rsi, %rax          测试不通过的情况下的代码 , temp = y
    subq    %rdi, %rax          temp = temp - x
    movq    %rdi, %rdx          long temp2 = x
    andq    %rsi, %rdx          temp2 = temp2 & y
    cmpq    %rsi, %rdi          比较 x : y
    comvge  %rdx, %rax          x>=y 的情况下, %rax 的值是 %rdx的值, 也就是 x & y
    ret
  .L2:
    addq    %rsi, %rdi          x = x + y
    cmpq    %-2,  %rsi          比较 y 和 -2
    cmovle  %rdi, %rax          y <= -2 的时候, %rax 是 x + y
    ret                         L2标号分支返回x + y

然后可以根据条件分支来补全C程序:

long testmove(long x, long y){
    long val = 8 * x;

    if (y > 0) {
        if (x >= y) {
            val = x & y;
        } else {
            val = y - x;
        }

    } else if (y <= -2) {
        val = x + y;
    }

    return val;
}

注意单独测试 y 的时候的jle表示小于等于0.

顺利看完了条件, 感觉还可以, 都能理解. 下边是循环了.