程序的机器级表示2

程序的流程控制，包括条件循环和分支结构,如if，for，while，switch语句，本文从汇编的角度，来理解这些结构

条件码

例如有两个值运算，有可能会溢出，有可能会产生进位，有可能为负，运算后，这些信息都通过条件码的形式保存下来。

  • CF：进位标志位，针对无符号数。若产生进位或借位，CF会被置位为1（无符号数进位或借位表示无符号位溢出）
  • SF：符号标志位，针对有符号数。表示当前指令运算结果的符号，非负数置位为0，负数置位为1
  • ZF：0标志位。运算结果为0时，会被置位为1
  • OF：溢出标志位，针对有符号数。有符号数运算有可能出现溢出而非进位，若产生溢出，则置位为1

lead指令只进行地址运算，不会修改条件码

一元，二元，移位操作都会修改寄存器，并且设置条件码

有两类指令只设置条件码，不修改其他寄存器： CMP和 TEST指令

CMP对操作数之间运算比较，基于S2-S1

1
CMP S1,S2

TEST对操作数进行测试，基于S2&S1

1
TEST S1,S2

例如 testq %rax,%rax可以检查%rax是正数负数还是零

每条指令都对应四种类型 b,w,l,q对应 字节，字，双字，四字

上面是设置条件码的一些指令，下面是一种根据条件吗，设置的指令SET（读取条件码）

访问条件码

SET指令会根据条件码设置值，有三种使用方法

  • 根据条件码，设置字节
  • 跳转程序
  • 有条件传送数据
1
2
3
4
5
comp:
	cmpq %rsi,%rdi	//比较%rdi和%rsi
	setl %al
	movzbl %al,%eax
	ret

set指令

跳转指令

jump指令又可以分为直接跳转，间接跳转，有条件跳转

  • 直接跳转 jmp .L1
  • 间接跳转 jmp *(%rax)
  • 有条件跳转,一般和cmp或test组合使用,并且只能是直接跳转到代码段

跳转指令的编码方式常见的采用pc相对寻址(基址+偏移量)来编码，csapp中有个例子

1
2
3
4
5
6
7
8
1	movq %rdi, %rax
2	jmp .L2
3    .L3:
4	sarq %rax	//算术右移
5    .L2:
6	testq %rax，%rax
7	jg .L3
8	rep; ret	//写重复字符串

.o反汇编

1
2
3
4
5
6
0:48 89 f8	mov %rdi , %rax
3:eb 03		jmp 8 <loop+0x8>
5:48 d1 f8	sar %rax
8:48 85 c0	test %rax ,%rax
b:7f f8		jg 5 <loop+0x5>
d:f3 c3		repz retq

条件结构

条件结构可以用条件控制和条件跳转来实现

条件控制的条件结构

1
2
3
4
5
//C语言中的if-else
if (test)
	then-statementelse
else
	else-statementelse

翻译为goto版本

1
2
3
4
5
6
7
t = test;
if (!t)
	goto false;
then-statement
goto done;
false:
	else-statementdone;

&&在c中存在短路现象，即t1&&t2，若前面为假，第二个条件直接不检查，下面从汇编的角度理解下（csappT3.16）

源码

1
2
3
4
5
void cond(long a,long *p)
{
	if(p&&a>*p)
	*p=a;
}

gcc下汇编代码

a in %rdi ,p in %rsi

1
2
3
4
5
6
7
8
cond:
	testq %rsi,%rsi
	je .L1		//测试指针是否为0，为0跳转L1
	cmpq %rdi,(%rsi)
	jge .L1
	movq %rdi,(%rsi)
.L1:
	rep;ret

可以看到，若第一个为假，会直接跳转到 .L1段，跳过检查第二个条件的代码

条件跳转的条件结构

条件传送比起条件控制，更符合现代处理器的性能特性

  • 条件控制->判断，满足条件，执行，错误，重新导入指令
  • 条件传送->判断，传送or不执行

分支预测的处罚

假设预测错误的概率是 p，如果没有预测错误，执行代码的时间是 TOK，而预测错误的处罚是 TMP。 那么，作为 p 的一个函数，执行代码的平均时间是 Tavg(p)=(1-p) TOK+p(TOK+TMP)。 如果已知 TOK和 Tran(当 p=0.5 时的平均时间)，代入等式，我们有 Tran=Tavg(0.5)=TOK+0.5TMP， 所以有 TMP=2(Tran-TOK)。因此，已知 TOK=8 和 Tran=17.5，我们有 TMP=19。

条件传送指令

条件控制的代码

1
2
3
4
5
6
7
if (!test-expr)
	goto false;
v=then-expr;
goto done;
false:
	v=else-expr;
done:

条件传送的代码

1
2
3
4
v=then-expr;
ve=else-expr;
t=test-expr;
if(!t) v=ve;

条件传送相当于不进行预测了，把分支的表达式都算出来，最后当满足条件的时候再进行赋值操作，这种对简单的表达式才有效，而且有时候可能会失效，不能采用这种方法，例如如下代码，如采用条件传送的话，假设指针为空，会异常

1
2
3
long cread(long *xp){
	return (xp?*xp:0)
}

循环

c中的循环，包括while，do-while，for循环

do-while

1
2
3
do
	body-statement;
	while(test-expr)

直到型循环，至少执行一次，翻译为goto

1
2
3
4
5
loop:
	body-statement;
	t=test-expr;
	if(t)
	goto loop;

while

1
2
while(test-expr)
	body-statement;

跳转到中间, 它执行一个无条件跳转跳到循环结尾处的测试，以此来执行初始的测试

1
2
3
4
5
6
7
goto test;
loop:
	body-statement;
test:
	t=test-expr;
	if(t)
	goto loop;

guarded-do，首先用条件分支，如果初始条件不成立就跳过循环，把代码变换为 do-while 循环

1
2
3
4
5
6
7
t=test-expr;
	if(!t)
	goto done;
do:
	body-statement;
	while(test-expr);
done:

goto代码

1
2
3
4
5
6
7
8
9
t=test-expr;
	if(!t)
	goto done;
loop:
	body-statement;
	t=test-expr;
	if(t)
	goto loop;
done:

for

1
2
3
for(init-expr;test-expr;update-expr){
	body-statement;
}

for可以翻译成while代码

1
2
3
4
5
init-expr;
while(test-expr){
	body-statement;
	update-expr;
}

中间策略

1
2
3
4
5
6
7
8
9
init-expr;
goto test;
loop:
	body-statement;
	update-expr;
test:
	t=test-expr;
	if(t)
	goto loop;

guarded-do

1
2
3
4
5
6
7
8
9
10
11
init-expr;
t=test-expr;
	if(!t)
	goto done;
loop:
	body-statement;
	update-expr;
	t=test-expr;
	if(t)
	goto loop;
done:

switch语句

switch语句通过使用跳转表(jump table)这种数据结构，可以根据一个索引值进行多重分支

跳转表，是一个指针数组，数组元素都是指向代码段的指针，通过 &&符号声明

switch.c

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 #include<stdio.h>
int switch_eg (int index)
{

static void *jt[2] = {
    &&loc_A,
    &&loc_B};
goto *jt[index];
loc_A:
printf("1\n");
return 1;
loc_B:
printf("2\n");
return 2;
}

int main(int argc, char const *argv[])
{
   switch_eg (0);
   switch_eg (1);
    return 0;
}

gcc下运行结果

1
2
1
2

采用指针数组的方法对比

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<stdio.h>
//地址作为函数入口定义
//#define EnterPWDN(clkcon) ((void (*)(int))0x00000020)(clkcon)
void loc_A()
{
    printf("1\n");
}
void loc_B()
{
    printf("2\n");
}

int main(int argc, char const* argv[])
{
    void (*loc_a)() = &loc_A;
    void (*loc_b)() = &loc_B;
    void* jt[2] =
    {
        loc_a,
        loc_b
    };
    goto run;
    //printf((const char*)jt[0]);
    //printf((const char *)jt[1]);
run:
    ((void(*)(void))jt[0])();
    ((void(*)(void))jt[1])();
    return 0;
}

switch语句关键步骤是通过跳转表访问代码位置。

跳转表对重复的情况就是用同样的代码标号，对跳出程序的情况使用默认标号

csappT3.30

下面的 C 函数省略了 switch 语句的主体。在 C 代码中，情况标号是不连续的，而有些情况有多个标号。

1
2
3
4
5
6
7
8
9
void switch2(long x, long *dest) {
    long val = 0;
    switch (x) {
        .
        .  // Body of switch statement omitted
        .
    }
    *dest = val;
}

汇编

1
2
3
4
5
6
7
# void switch2(long x, long *dest)
# x in %rdi
switch2:
    addq    $1, %rdi    # x = x + 1 ，由于将索引控制在 0 开始，所以 x 的最小值是 -1  
    cmpq    $8, %rdi    # 比较 x - 8，其实就是 x + 1 - 8 > 0 ，则原始的 x 最大标号是 7   
    ja      .L2         # 超过 8 就跳转到 L2，L2 相当于 default   
    jmp     *.L4(, %rdi, 8)    # 没有超过 8 就进入跳转表

为跳转表生成以下代码：

1
2
3
4
5
6
7
8
9
10
.L4
    quad:   .L9    # -1
    quad:   .L5    # 0
    quad:   .L6    # 1
    quad:   .L7    # 2
    quad:   .L2    # default
    quad:   .L7    # 4
    quad:   .L8    # 5
    quad:   .L2    # default 
    quad:   .L5    # 7

A. switch 语句内情况标号的值分别是多少？

-1、0、1、2、4、5 和 7

B. C 代码中哪些情况有多个标号？

.L5 的情况为 0 和 7，.L7 的情况标号为 2 和 4。