第三章：程序的机器级表示（2）

Posted on

《CSAPP》第三章小结（续）

《深入理解计算机系统》

算术和逻辑操作

下图是常见的指令

加载有效地址leaq

该指令实际是movq的变形，但它实际上根本没有引用内存，并不是从第一个操作数指定的位置读入数据，而是将有效地址写入目的操作数,例如%rax的值为x，那么指令leaq 7(%rdx,%rdx,4),%rax将设置寄存器%rax的值为5*x+7

1
2
3
4
5
long scale(long x,long y,long z)
{
	long t = x+4*y+12*z;
	return t;
}

1
2
3
4
5
6
7
8
9
scale:
.LFB0:
	.cfi_startproc
	leaq	(%rdi,%rsi,4), %rcx  //x+4*y
	leaq	(%rdx,%rdx,2), %rax  //z+2*z
	salq	$2, %rax      //3*z左移两位为12*z 
	addq	%rcx, %rax    //x+4*y+12*z
	ret
	.cfi_endproc

一元和二元操作

一元操作的操作数既是源又是目的，可以是内存也可以是寄存器。例如incp(%rsp)将是栈顶的八字节加一，类似于c语言中的++和–运算符
二元操作的第二个操作数既是源又是目的，类似于x-=y。不过源操作数是第一个，目的操作数第二个，例如指令subq %rax,%rdx是从%rdx中减去%rax，第二个操作数不能是立即数，并且如果是内存地址时，必须先读出值，执行操作，再写入内存

移位操作

先是移位量，再是要移位的数，移位量可以是立即数，或者放在%cl寄存器中，特别规定只能以该寄存器作为操作数。
移位操作对w位长的数据值进行操作，移位量是由寄存器的低m位决定的，并且$2^m=w$,高位自动忽略。例如%cl的值为OxFF时，指令salb左移7位，salw左移15位，sall左移31位，salq左移63位，这块地方依旧有些不明白。
左移指令有SAL和SHL，效果相同，都是右边补0
右移指令有SAP和SHR，SAR执行算术移位（填上符号位），SHR执行逻辑移位（填上0）

1
2
3
4
5
6
long shift(long x,long n)
{
	x<<=4;
	x>>=n;
	return x;
}

1
2
3
4
5
6
7
8
9
shift:
.LFB0:
	.cfi_startproc
	movq	%rdi, %rax
	salq	$4, %rax
	movl	%esi, %ecx
	sarq	%cl, %rax
	ret
	.cfi_endproc

另一个例子,寄存器%rax分别存储了不同的程序值，并在寄存器之间传送程序值

1
2
3
4
5
6
7
8
long arith(long x,long y,long z)
{
	long t1 = x^y;
	long t2 = z*48;
	long t3 = t1 & 252645135;
	long t4 = t2 -t3;
	return t4;
}

1
2
3
4
5
6
7
8
9
10
11
//x,y,z分别放在%rdi，%rsi，%rdx
arith:
.LFB0:
	.cfi_startproc
	xorq	%rsi, %rdi          //x^y异或
	leaq	(%rdx,%rdx,2), %rax //3*z
	salq	$4, %rax            //16*(3*z)
	andl	$252645135, %edi    //t1 & Ox252645135
	subq	%rdi, %rax          //t2-t3
	ret
	.cfi_endproc

一个小技巧

1
2
3
4
xorq %rdx,%rdx 
根据异或的特性，相同取0，不同取1，对自己异或就是清零
也可以用movq $0,%rax 来实现
两种操作的字节长度不同，这里有点不明白

特殊的算术操作

两个64位有符号或无符号整数相乘得到的乘机需要128位来表示，下图描述的就是产生两个64位数字的全128位乘机以及整数除法的指令
imulq指令有两种形式

  • 一种是IMUL类中双操作数的一种，他将从两个64位操作数产生一个64位乘积
  • 另一种则是单操作数指令，计算两个64位值的全128位乘机，一个是无符号乘积mulq，另一是补码乘法imulq。这两条指令都要求一个参数必须在寄存器%rax中，另一个作为指令的源操作数给出，然后将乘积放在%rdx（高64位）和%rax（低64位）中
    汇编器会自动分辨该使用上述那条指令

例子展示将两个无符号64位数字乘积生成128位数字,首先显式的定义两个64位数字x、y，并用typedef定义uint128_t，指明乘积放在指针dest指向的16字节处

1
2
3
4
5
6
7
8
#include<inttypes.h>

typedef unsigned __int128 uint128_t;

void store_uprod(uint128_t *dest,uint64_t x,uint64_t y)
{
	*dest=x*(uint128_t)y;
}

1
2
3
4
5
6
7
8
9
store_uprod:
.LFB4:
	.cfi_startproc
	movq	%rsi, %rax     //将x复制到%rax
	mulq	%rdx           //y*x
	movq	%rax, (%rdi)   //存储低8字节
	movq	%rdx, 8(%rdi)  //存储高8字节
	ret
	.cfi_endproc

有符号除法指令idivl将寄存器%rdx（高64位）和%rax（低64位）中的128位数作为被除数，而除数作为指令的操作数给出，商存储在%rax，余数存在%rdx
对于64位除法来说，被除数也是64位值，这个值如上所述，存在%rax中，而%rdx的位设置为全0（无符号运算）或者%rax的符号位（有符号运算），该设置的指令将有cpto完成，具体如下所示

1
2
3
4
5
6
7
void remdiv(long x,long y,long *pq,long *rq)
{
	long q=x/y;
	long r=x%y;
	*pq=q;
	*rq=r;
}

1
2
3
4
5
6
7
8
9
10
11
12
//x in %rdi,y in %rsi,pq in %rdx,rp in %rcx
remdiv:
.LFB0:
	.cfi_startproc
	movq	%rdx, %r8   //因为除法操作用到%rdx，所以copy pq to %r8
	movq	%rdi, %rax  //move x to %rax
	cqto                //扩展高8字节
	idivq	%rsi        //x/y   
	movq	%rax, (%r8) //存储商
	movq	%rdx, (%rcx)//存储余数
	ret
	.cfi_endproc

控制

条件码

CPU维护着一组单个位的条件码寄存器，描述最近的算术或者逻辑操作的属性，可以通过检测这些条件码寄存器来执行条件分支指令。

  • CF：进位标志，检查最高位是否产生进位，用来标志无符号溢出
  • ZF：标志操作结果是否为0
  • SF：操作结果是否为负数
  • OF：操作是否导致补码溢出–正溢出或负溢出

如本文一幅图所示，除了leap不改变条件码寄存器，其余操作均要设置条件码，还有两类操作也会设置条件码

  • CMP：根据两个操作数之差设置条件码，除了不更新目的寄存器以外，和SUB指令行为一样
  • TEST：和AND指令行为类似，例如testq %rax，%rax来检查%rax是负数还是0或者是整数

一般有三种使用条件码的方法，第一种根据条件码的组合，将一个字节设置为0或1，这类指令成为SET指令，这类指令的后缀不代表操作数的大小，而是指明条件码的组合，如下图所示

1
2
3
4
int cmp(int a,int b)
{
	return a > b;
}

1
2
3
4
5
6
7
8
cmp:
.LFB0:
	.cfi_startproc
	cmpl	%esi, %edi   //比较a，b
	setg	%al          //设置低位单字节寄存器为0或1
	movzbl	%al, %eax    //为了得到一个32位或64位结果，要进行零位扩展，将寄存器的高位清零
	ret
	.cfi_endproc

跳转指令

跳转的目的地一般用label表明，产生目标代码文件时，汇编器会确定所有带label指令的地址，并将目的指令的地址编码为跳转指令的一部分

  • 直接跳转：以label为目标直接跳转
  • 间接跳转：跳转目标从寄存器或者内存位置读出，一般带有*号

最常见的是PC相对编码，将目标指令的地址与紧跟在跳转指令后面那条指令的地址的差作为编码，另一种则是给出绝对地址，用四字节直接指定目标，汇编器和链接器会选择合适的跳转目的编码，所以跳转指令的地址=目标指令的地址-跳转指令后一条指令的地址，当执行PC相对寻址时，程序计数器的值是跳转指令后面的那条指令的的地址，而不是跳转指令本身的地址
通过PC相对的跳转目标编码，将很容易将目标代码迁移至内存中该图是链接后的反汇编版本，其中有两个跳转指令jmp、jg,其中jmp目的地址等于下一条指令地址0x4004d5加上相对编码03得到0x4004d8,同理jg的目的地址等于0xd+0xf8=0xd5,因为f8对应十进制-8

条件控制实现条件分支

刚学习的时候比较语句例如cmpq $-3, %rdi和jge .L2其实合起来相当于是else的条件而不是if的条件，当时理解的时候出现了偏差

1
2
3
4
5
6
7
8
9
10
11
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;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
test:
.LFB0:
	.cfi_startproc
	leaq	(%rdi,%rsi), %rax
	addq	%rdx, %rax
	cmpq	$-3, %rdi
	jge	.L2
	cmpq	%rdx, %rsi
	jge	.L3
	movq	%rdi, %rax
	imulq	%rsi, %rax
	ret
.L3:
	movq	%rsi, %rax
	imulq	%rdx, %rax
	ret
.L2:
	cmpq	$2, %rdi
	jle	.L4
	movq	%rdi, %rax
	imulq	%rdx, %rax
.L4:
	rep ret
	.cfi_endproc

条件传送来实现条件分支

基于条件数据传送的代码会比基于条件控制转移的代码性能更好，这种方法计算一个条件操作的两种结果，然后再根据条件是否满足从中选取一个。
为什么条件数据传送的代码性能好：

  • 处理器通过该使用流水线的重叠连续指令来获得高性能
  • 当机器遇到条件跳转时，一般是在分支条件求值完成后，决定分支往哪走，但是处理区采用非常精密的分支预测逻辑才猜测每条跳转指令是否执行
  • 但是如果预测错误，就要丢掉处理器为该跳转指令后所有指令做的工作然后回到正确位置重新计算，这一步的代价是很高的
  • 因此如果是采用条件控制转移猜测x>y时，猜对的概率也只有%50，而分支中的操作只需要很小消耗时，分支预测错误就主导了函数的性能，
  • 但是如果我们先计算出分支条件，就不存在预测错误的机会
  • 条件传送使用的限制很多，比如分支操作不能有副作用、求值计算不能太多
1
2
3
4
5
#define OP /

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

该程序创建一个临时值为x+7，预计x为负。当cmovns指令在x>=0成立时才把临时值修改为x，再算术右移3位

1
2
3
4
5
6
7
8
9
arith:
.LFB0:
	.cfi_startproc
	leaq	7(%rdi), %rax   temp=x+7
	testq	%rdi, %rdi      Test x
	cmovns	%rdi, %rax      if x>= 0 ,temp=x
	sarq	$3, %rax        return temp>>4=3
	ret
	.cfi_endproc

循环

汇编中没有相应的指令存在，可以用条件测试和跳转组合起来实现循环的效果

  • do-while循环
  • while循环：有两种翻译方式，跳转到中间(jumo to middle)和guarded-do，当较高级优化时，GCC会采取后者这种策略
1
2
3
4
5
6
7
8
//jumo to middle的goto代码模板
	goto test
loop:
	body-statement
test:
	t=test-expr;
	if(t)
		goto loop;
1
2
3
4
5
6
7
8
9
10
//guarded-do的goto代码模板
t=test-expr;
if(!t)
	goto done;
loop:
	body-statement
	t=test-expr;
	if(t)
		goto loop;
done:

这段代码使用jump to middle翻译方法产生以下汇编代码，该代码计算x的奇偶性，也就是如果x中有奇数个1，就返回1，如果有偶数个1，就返回0,这段代码还是不理解

1
2
3
4
5
6
7
8
long fun_a(unsigned long x){
	long val = 0;
	while(x != 0){
		val ^= x;
		x >>= 1;
	}
	return val & 0x1;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
fun_a:
.LFB0:
	.cfi_startproc
	movl	$0, %eax
	jmp	.L2
.L3:
	xorq	%rdi, %rax
	shrq	%rdi
.L2:
	testq	%rdi, %rdi
	jne	.L3
	andl	$1, %eax
	ret
	.cfi_endproc
  • for循环:可以转化成while循环
1
2
3
4
5
6
7
8
9
10
//jump to middle的goto模板
init-expr;
goto test;
loop:
	body-statement;
	update-expr;
test:
	t=test-expr;
	if(t)
		goto loop;
1
2
3
4
5
6
7
8
9
10
11
12
//guarder-to的goto模板
init=expr;
t=test-expr;
if(!t)
	goto done;
loop:
	body-statement;
	update-expr;
	t=test-expr;
	if(t)
		goto loop;
done:

这段代码是将x的位反转，产生镜像，

1
2
3
4
5
6
7
8
9
long fun_b(unsigned long x){
	long val = 0;
	int i ;
	for(i = 64; i != 0 ; i++){
		val = (val << 1) | (x & 0x1);
		x >>= 1;
	}
	return val;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
fun_b:
.LFB0:
	.cfi_startproc
	movl	$64, %edx
	movl	$0, %eax
	jmp	.L2
.L3:
	addq	%rax, %rax
	movq	%rdi, %rcx
	andl	$1, %ecx
	orq	%rcx, %rax
	shrq	%rdi
	addl	$1, %edx
.L2:
	testl	%edx, %edx
	jne	.L3
	rep ret
	.cfi_endproc

switch语句

通过使用跳转表，实现多重分支，这样switch即使有上百种情况，也能只用一次跳转表访问处理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void switch_eg(long x,long n,long *dest)
{
	long val = x;
	switch(n){
	case 100:
		val*=13;
		break;
	case 102:
		val+=10;
	case 103:
		val+=11;
		break;
	case 104:
	case 106:
		val*=val;
		break;
	default:
		val=0;
	}
	*dest=val;
}

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
30
31
32
33
34
35
36
37
switch_eg:
.LFB0:
	.cfi_startproc
	subq	$100, %rsi
	cmpq	$6, %rsi
	ja	.L8
	jmp	*.L4(,%rsi,8)   //间接跳转
	.section	.rodata //只读的目标代码文件的段中
	.align 8
	.align 4
.L4:                    //标记分配地址的开始，作为间接跳转的基地址 
	.quad	.L3
	.quad	.L8
	.quad	.L5
	.quad	.L6
	.quad	.L7
	.quad	.L8
	.quad	.L7
	.text
.L3:
	leaq	(%rdi,%rdi,2), %rax
	leaq	(%rdi,%rax,4), %rdi
	jmp	.L2
.L5:
	addq	$10, %rdi
.L6:
	addq	$11, %rdi
	jmp	.L2
.L7:
	imulq	%rdi, %rdi
	jmp	.L2
.L8:
	movl	$0, %edi
.L2:
	movq	%rdi, (%rdx)
	ret
	.cfi_endproc

过程

是一种很重要的抽象，提供一种封装代码的方式，来实现摸个特定的功能，但却隐藏行为的具体实现，又提供清晰间接的接口定义。过程调用主要有以下几个机制：

  • 传递控制
  • 传递数据
  • 分配和释放内存

运行时栈

该机制的关键在于使用了栈数据结构提供的先进先出的内存管理机制
例如在Q执行时，先前调用Q的P调用链处在挂起的状态，Q可以在属于自己的存储空间中分配，当Q返回时，所分配的局部存储空间都可以被释放。
可以通过减小栈指针来分配空间，通过增加栈指针来释放空间，如果寄存器不够拿来分配，就会在栈中分配空间，如下图所示

转移控制

通过call指令来实现函数调用，该指令call Q会将PC设置为Q的起始地址，并将紧跟在call指令后面的那条指令压入栈中，成为返回地址。对应ret指令会从栈中弹出返回地址,并将会PC设置为返回地址。这种简单的机制和多数程序语言的调用/返回机制吻合。

数据传送

数据传送大多通过寄存器实现，并最多传递6个整数，寄存器的使用也是有特殊顺序的，如下图所示超过6个的部分就要通过栈来传递

1
2
3
4
5
6
7
8
9
10
void proc(long a1,long *a1p,
	  int a2,int *a2p,
	  short a3,short *a3p,
	  char a4,char *a4p)
{
	*a1p+=a1;
	*a2p+=a2;
	*a3p+=a3;
	*a4p+=a4;
}

1
2
3
4
5
6
7
8
9
10
11
proc:
.LFB0:
	.cfi_startproc
	movq	16(%rsp), %rax
	addq	%rdi, (%rsi)
	addl	%edx, (%rcx)
	addw	%r8w, (%r9)
	movl	8(%rsp), %edx
	addb	%dl, (%rax)
	ret
	.cfi_endproc

这个实例说明第7和8个参数位于栈指针距离8和16的位置上，返回地址也被压入栈中

局部数据

有些时候需要将局部数据存放在内存中,例如

  • 寄存器不够存放本地数据
  • 需要地址运算符&，此时就必须为它产生一个地址
  • 数组或者结构时，需要通过数组或结构引用才能访问到

运行时栈提供了一种简单的、在需要时分配、函数完成时释放局部存储的机制

1
2
3
4
5
6
7
long call_proc()
{
	long x1 =1;int x2 = 2;
	short x3 = 3;char x4 = 4;
	proc(x1,&x1,x2,&x2,x3,&x3,x4,&x4);
	return (x1+x2)*(x3-x4);
}

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
30
31
call_proc:
.LFB0:
	.cfi_startproc
	subq	$40, %rsp
	.cfi_def_cfa_offset 48
	movq	$1, 24(%rsp)
	movl	$2, 20(%rsp)
	movw	$3, 18(%rsp)
	movb	$4, 17(%rsp)
	leaq	17(%rsp), %rax
	movq	%rax, 8(%rsp)
	movl	$4, (%rsp)
	leaq	18(%rsp), %r9
	movl	$3, %r8d
	leaq	20(%rsp), %rcx
	movl	$2, %edx
	leaq	24(%rsp), %rsi
	movl	$1, %edi
	movl	$0, %eax
	call	proc
	movslq	20(%rsp), %rdx
	addq	24(%rsp), %rdx
	movswl	18(%rsp), %eax
	movsbl	17(%rsp), %ecx
	subl	%ecx, %eax
	cltq
	imulq	%rdx, %rax
	addq	$40, %rsp
	.cfi_def_cfa_offset 8
	ret
	.cfi_endproc

大部分指令都在为调用proc做准备，其中包括为局部变量和函数参数建立栈帧，当调用其他函数时，就可以根据相对于%rsp位置来修改参数值，当程序返回调用函数时，就会取出这些局部变量，并执行最后的运算。程序结束时，将栈指针增加，释放栈帧。

由于寄存器是所有过程共享的资源，为了防止被调用者不会覆盖调用者的寄存器值，根据惯例规定，寄存器%rbx %rbp %r12~%r15都被划分为被调用者保存寄存器，当过程Q保存一个寄存器的值时，要么不去改变，要么把原始值先压入栈中，然后改变寄存器的值，然后再返回前从栈中弹出旧值，压入的值存在栈帧中“保存的寄存器”的特殊部分，这样调用者就能把值安全得保存在寄存器中

递归

递归调用一个函数本身与调用其他函数是一样的，每次函数调用都有它自己的私有状态信息存储空间