程序的机器级表示

有关CSAPP第三章一些我关注到的重点的记录

操作指令

.c->.exe的流程

1.选项 -E : 预编译过程,处理宏定义和include，并作语法检查

gcc -E hello.c -o hello.i              #将hello.c预处理输出为hello.i文件

2.选项 -S : 编译过程,生成通用的汇编代码

gcc -S hello.c                         #生成汇编代码hello.s

生成的汇编文件以“.”开头的行都是指导汇编器和链接器工作的伪指令

3.选项 -c : 汇编过程,生成ELF格式的可重定位目标文件，目标文件(机器代码)，用文本编辑器打开是乱码

gcc -c hello.c                         #生成目标代码hello.o(中间文件)，不能执行，在Makefile中应用广泛

4.选项 -L : 链接过程,将.o文件与所需库文件链接合并成ELF格式的可执行目标文件，分静态链接和动态链接

gcc hello.o -L dir(如./lib)            #指定库搜索路径，有多个则从前往后搜索

5.选项 -l : 链接过程,指定链接库，库命名规则是libxxx.a,指定库名时使用的格式是-lxxx

gcc hello.c -o hello -lm              #链接数学库
ld -o hello hello.o -lxxx             #链接xxx库

6.选项 -o : 将源文件预处理、编译、汇编并链接形成可执行目标文件，-o选项指定可执行文件的文件名，加载到内存中即可执行

gcc hello.c -o hello                  #生成可执行文件hello

7.部分选项：
选项 -Wall : 编译时打开警告信息开关
选项 -D : 在文件中定义宏INFO，编译时加上-D INFO使其生效
选项 -O : 后指定数字，使用编译优化级别1~3优化程序
选项 -g : 产生调试信息

8.选项 -static : 使用静态链接库，将使用的静态库对象嵌入至可执行映像文件中，加载时无需进一步的链接

gcc -c -Wall x1.c x2.c       #生成目标文件
ar -cru libxxx.a x1.o x2.o   #创建静态库
#定义静态库的应用接口xxx.h，里面显式引用上面的源文件函数和对象
gcc -O2 -c main.c            #测试用例调用静态库的函数
gcc -static -o p main.o ./libxxx.a  #链接静态库和目标文件生成可执行文件p

9.选项 -share : 使用共享库，在运行时动态加载目标程序所需要的信息
选项 -fPIC : 指示编译器生成与地址无关的目标文件(position-independent code)

gcc -shared -fPIC -o libxxx.so x1.c x2.c  #生成共享库libvector.so
gcc -o p1 main.c ./libvector.so           #共享库中的目标对象并未嵌入可执行文件中，执行时完成链接过程

.c->.exe

linux> gcc -Og -o p -g p.c

-Og优化等级比较符合原始C代码整体结构，方便学习(为了更高的性能可以使用-O1或-O2甚至更高的编译优化选项)
-o转化成可执行文件
-g生成调试信息
p为转化成可执行文件的文件名
p.c为源文件名

.c->.s 编译生成汇编文件

linux> gcc -Og -S p.c

.c->.o 汇编生成目标文件

linux> gcc -Og -c p.c

.o/.exe->.s 反汇编

linux> objdump -d p.o

C语言嵌套汇编语言

C编译器在把程序中表达的计算转换到机器代码中表现很出色，但仍然有一些及其特性是C语言访问不到的。例如x86-64处理器执行算术或逻辑运算时，修改奇偶标志位寄存器PF的值时，用汇编语言的效率远高于C语言，故如果能在C语言中嵌套C语言，会提供大大的方便。

第一种方法：源代码中插入汇编代码

#include <stdio.h>
#include <stdlib.h>

int main(void)
{
	/* basic command demo */
	__asm__("movl %eax, %ecx");

	/* set b = 10 */
	int a = 10, b = 0;
	__asm__("movl %1, %%eax;"
	     "movl %%eax, %0;"
	     :"=r" (b)	/* output */
	     :"r" (a)	/* input */
	     :"%eax"	/* clobbered register */
	     );

	printf("%s: b = %d\n", __func__, b);
	return 0;
}

第二种方法：写好汇编文件和C文件，用汇编器和链接器把它们合并起来

保存寄存器

假设现在有两个函数funcA和funcB，函数A称为调用者，函数B称为被调用者，由于调用了函数B，寄存器rbx在函数B中被修改了，而逻辑上rbx寄存器的内容在调用函数B的前后应该保持一致，解决这个问题有两个策略，调用者保存和被调用者保存。

func_A:
	...
	movq $123, %rbx
	call func_B
	add %rbx, %rax
	...
	ret

func_B:
	...
	addq $456, %rbx
	...
	rer

调用者保存

func_A:
	...
	movq $123, %rbx
	保存rbx
	call func_B
	恢复rbx
	add %rbx, %rax
	...
	ret

func_B:
	...
	addq $456, %rbx
	...
	rer

被调用者保存

func_A:
	...
	movq $123, %rbx
	call func_B
	add %rbx, %rax
	...
	ret

func_B:
	...
	保存rbx
	addq $456, %rbx
	恢复rbx
	...
	rer

具体使用哪种策略取决于寄存器被定义为那种类型，下图是寄存器类型

c语言基本类型对应汇编后缀表示

访问信息

各存储部件的性价比

通用寄存器

寄存器	用途
%eax	操作数运算
%ebx	指向DS段中数据的指针
%ecx	字符串操作和循环计数器
%edx	输入输出指针
%esi	指向DS段中数据的指针或字符串操作中字符串的复制源
%edi	指向ES段中数据的指针或字符串操作中字符串的复制地
%esp	栈指针(SS段)
%ebp	指向SS段上数据的指针

段寄存器

寄存器	用途
CS	代码段
DS	数据段
SS	堆栈段
ES	数据段
FS	数据段
GS	数据段

C类型长度

C声明	Intel数据类型	汇编代码后缀	大小（字节）
char	字节	b	1
short	字	w	2
int	双字	l	4
long	四字	q	8
char*	四字	q	8
float	单精度	s	4
double	双精度	l	8

指令

指令包含操作码和操作数。

	操作码		操作数
	movq	 (%rdi), %rax
	addq	 $8,	%rsx
	subq	 %rdi,	%rax
	xorq	 %rsi,	%rdi
	ret

操作码决定CPU执行操作的类型

指令可以有一个、多个或没有操作数

操作数分为3类，分别为立即数、寄存器以及内存引用

数据寻址模式

这里的比例因子s会根据数据类型取

数据传送命令

以上命令中没有movzlq，是因为一个结论：当复制和生成字节以寄存器为目标时，对于生成4字节的指令，会把高位4个字节置为0，所以用movl就能代替命令movzlq，例如

movl %eax,%edx

实际上除了将低32位数据由eax传递给rdx的低32位之外，还把高32位设置为0

这里注意到练习题3.3的一题，找以下代码的错误

movl %eax,%rdx

在这里错误是源操作数和目标操作数类型不匹配，虽然eax传值后会扩展为64位，但在写代码时依然需要保持操作数类型的统一

movq指令的限制：

当movq指令的源操作数是立即数时，只能是32位的立即数，此时会对该立即数进行符号扩展到64位，再将得到的64位立即数传送到目的位置。

那么当源操作数是64位立即数时就引入了一个新的指令movabsq，此时就能将64位立即数作为源操作数，但目的操作数只能是寄存器

cltq指令

cltq = movslq %eax，%rax

算术和逻辑操作

操作指令

具体操作如下图，之所以z被分为两步操作，是因为比例因子只能取1、2、4、8这四个数中的一个

移位操作

移位量可以是一个立即数，或者放在单字节寄存器%cl中。

移位操作对w位长的数据值进行操作，移位量是由**%cl寄存器**的低m位决定的，这里2^m=w，高位被忽略。所以，例如寄存器%cl的十六进制值为0xFF时，指令salb会移7位，salw会移15位，sall会移31位，而salq会移63位。

SAR算术右移，高位补符号位；SHR逻辑右移，高位补0；

以下操作使用移位操作而不使用乘法操作的原因是因为乘法指令执行需要更长时间，因此编译器在生成汇编指令时，会优先考虑更高效的方式。

特殊的算术操作

控制

条件码

CPU除了提供上面的几个整数寄存器外，还维护着一组单个比特位的条件码，描述最近的算术或逻辑操作特性，用于执行条件分支指令。

CF：进位标志，表示最近的操作使最高位产生了进位。用于检查无符号操作数的溢出，如下图
ZF：零标志，表示最近的操作得出的结果为0，如下图
SF：符号标志，表示最近的操作得出的结果为负数
OF：溢出标志，表示最近的操作使补码溢出-正溢出或负溢出

条件码寄存器的值是由ALU执行算术逻辑运算指令改变的

有几种设置条件码的情形

INC（加一）和DEC（减一）指令会设置OF（溢出）标志和ZF（零）标志，但不会改变CF（进位）标志。

因为指令系统设计人员考虑该指令主要用于对指针（即地址）进行增加，不存在进位问题，所以没有设计让INC影响进位标志CF。
INC,DEC指令不影响CF标志位,这个是Intel规定的！其原因是硬件设计造成的，总之，对软件人员来制说不重要！
INC,DEC指令不影响CF标志位,这表明执行INC/DEC指令之后，CF不能反映进位情况。

INC 0000000011111111

0000000011111111+1当然要进位，但不设置CF为1。
我们的问题就在于，将进位与CF等同
CF被称为进位标志位，在多数情况下，它确实反映进位情况，但不是绝对的，INC/DEC就是其中两例
INC/DEC指令不影响CF标志位，这句话就是明明白白地告诉你，此时，CF与进位无关

A. 比较和测试指令：它们只设置条件码而不改变任何其他寄存器

cmp S2,S1 通过S1-S2的结果，比较两者的大小
test S2,S1 通过S1&S2的结果(按位与)，比如testl %eax,%eax用来检查%eax是正数，负数还是0或者其中一个操作数是掩码，用来指示哪些位应该被测试

B. 根据条件码的组合，使用set指令，不同后缀名表示不同条件

set指令的目的操作数是8个单字节寄存器或者存储一个字节的存储器位置，把该字节位置设置成0或1。它的基本思路是执行比较或测试指令，根据set指令的类型决定计算结果t=a-b：操作数的大小，是有符号的还是无符号的，程序值的数据类型。如图所示为set指令的常见情形

跳转指令

关于跳转指令如何编码

可以看到第2行中跳转指令目标指明位0x8，第5行中跳转指令跳转目标是0x5，这里有一个规则，在指令的字节编码中，我们可以看到第二个字节中编码位0x3，再将其加上下一条指令的地址，即0x5，就可以得到跳转目标地址0x8，同样第5行0xf8(即十进制-8)，这个数加上0xd，即为地址0x5

条件分支

用条件控制来实现条件分支
实际上，C语言中有一种语句叫做goto，一般不推荐使用，但是它的控制和汇编代码的条件转移十分相似。

例如我们有这样一段正常的代码，实际上就是得到两数之差的绝对值：

long absdiff(long x, long y)
{
long result;
if (x > y)
result = x-y;
else
result = y-x;
return result;
}

然后我们使用goto语句改写一下：

long absdiff_j(long x, long y)
{
long result;
int ntest = x <= y;
if (ntest) goto Else;
result = x-y;
goto Done;
Else:
result = y-x;
Done:
return result;
}

从控制流的角度来看，这两个代码基本上是一样的。

用条件传送来实现条件分支
条件传送，和set指令有些相似，也就是根据条件码部分来判断是否要进行数据传送，使用的是cmov（conditional move），比如当相等的时候进行条件传送，也就是cmove。

现代处理器会使用一种特殊的技术，叫做流水线（pipeline），它的名字就是取自工厂流水线，在CPU中，也就是说当你执行一条指令的时候，下一条指令的一部分会被执行，下下一条指令的一部分也会被执行，这样就提高了并行的程序。

但是条件转移会破坏流水线的运作，于是我们会把两个条件的结果都计算一遍，然后再根据跳转选择其中的一条。这里也就用到了cmov。

比如还是之前的程序，我们汇编变成如下这个样子，也就是把x-y和y-x都计算了，然后再根据条件，选择其中一个结果返回：

absdiff:
movq %rdi, %rax # x
subq %rsi, %rax # result = x-y
movq %rsi, %rdx
subq %rdi, %rdx # eval = y-x
cmpq %rsi, %rdi # x:y
cmovle %rdx, %rax # if <=, result = eval
ret
但是，使用cmov也会有一些负面影响：

只有当计算较为简单时，才用cmov进行优化，如果两条分支都较为复杂，那么使用cmov反而不好
对于某个分支而言，计算它可能没有什么用，只是浪费时间。
两个分支可能会存在关联性，比如val = x > 0 ? x*=7 : x+=3;，如果两个都进行计算就会出现错误。

指令	同义名	传送条件	描述
cmove S,R	cmovz	ZF	相等/零
cmovne S,R	cmovnz	~ZF	不相等/非零
cmovs S,R		SF	负数
cmovns S,R		~SF	非负数
cmovg S,R	cmovnle	~(SF^OF) & ~ZF	大于（有符号>)
cmovge S,R	cmovnl	~(SF^OF)	大于或等于（有符号>=）
cmovl S,R	cmovnge	SF^OF	小于（有符号<）
cmovle S,R	cmovng	(SF^OF) \| ZF	小于或等于（有符号<=）
cmova S,R	cmovnbe	~CF & ~ZF	超过（无符号>）
cmovae S,R	cmovnb	~CF	超过或相等（无符号>=）
cmovb S,R	cmovnae	CF	低于（无符号<）
cmovbe S,R	cmovna	CF \| ZF	低于或相等（无符号<=）

练习题3.20

在这里发现一个规则，当负数做被除数时，需要将该数先加上2^k-1，k为要右移的位数。这是为了保证，正数向下舍入，负数向上舍入

循环

一、do-while

如果用C的goto来实现，则如下面的代码：

loop:
  Body
  if (Test)
    goto loop

实际上就是先循环体，然后进行测试，如果测试成功，那么跳回到loop再继续循环。

举个例子，比如我们有这样一个C程序的goto版本：

long pcount_goto (unsigned long x) {
  long result = 0;
 loop:
  result += x & 0x1;
  x >>= 1;
  if(x) goto loop;
  return result;
}

那么会发现，汇编的版本也类似：


 movl    $0, %eax		#  result = 0
.L2:			# loop:
   movq    %rdi, %rdx	
   andl    $1, %edx		#  t = x & 0x1
   addq    %rdx, %rax	#  result += t
   shrq    %rdi		#  x >>= 1
   jne     .L2		#  if (x) goto loop
   rep; ret

二、while

while和do-while的区别就在于do-while第一次不进行测试，所以总会执行一遍循环体，而while在开始就测试，如果不满足就跳出，不执行。

while的实现有2种方式，第一种方式就是先跳到了do-while的中间，然后进行测试。

C的goto版本如下：

goto test;
loop:
  Body
test:
  if (Test)
    goto loop;
done:

我们还是用pcount这个程序，那么while就是下面这种实现：

long pcount_goto_jtm(unsigned long x) {
  long result = 0;
  goto test;
 loop:
  result += x & 0x1;
  x >>= 1;
 test:
  if(x) goto loop;
  return result;
}

第二种实现方式比较传统，就是一开始进行判断，如果不满足直接goto跳出，满足那么进入到和do-while相同的语句块中。

 if (!Test)
    goto done;
loop:
  Body
  if (Test)
    goto loop;
done:

pcount的第二种while实现如下：

long pcount_goto_dw(unsigned long x) {
  long result = 0;
  if (!x) goto done;
 loop:
  result += x & 0x1;
  x >>= 1;
  if(x) goto loop;
 done:
  return result;
}

三、for

for循环实际上包含了4个部分，例如一个C语言的for循环for(int i = 0;i < 5;i++){body}，包括了初始化（int i = 0），测试（i < 5），更新（i++）和循环体。

如果用while循环来表示for循环，那么就是先进行初始化，然后是while循环，在while循环体的最后加上更新操作。

Init;
while (Test ) {
    Body
    Update;
}

还是之前的例子，我们使用for循环（用while实现for）实现：

long pcount_for_while(unsigned long x)
{
  size_t i;
  long result = 0;
  i = 0;
  while (i < WSIZE)
  {
    unsigned bit = 
      (x >> i) & 0x1;
    result += bit;
    i++;
  }
  return result;
}

然后我们用goto替代：

long pcount_for_goto_dw(unsigned long x) {
  size_t i;
  long result = 0;
  i = 0;
  if (!(i < WSIZE))
    goto done;
 loop:
  {
    unsigned bit = 
      (x >> i) & 0x1;
    result += bit;
  }
  i++;
  if (i < WSIZE)
    goto loop;
 done:
  return result;
}