本次笔记内容:
09.控制流-2
int cread(int *xp) { return (xp ? *xp : 0); }
空指针返回0,否则返回指针所指。
是否可以用如下汇编代码段完成?
# xp in register %edx movl $0, %eax # Set 0 as return value testl %edx, %edx # Test xp cmovne (%edx), %eax # if !0, dereference xp to get return value
答:不可以,因为cmovne:
下面是一种正确的操作:
先从c的思考方式入手:
int cread_alt(int *xp) { int t = 0; return *(xp ? xp : &t); }
则对应的汇编代码如下:
movl $0 -4(%ebp) # t = 0 movl 8(%ebp) %eax # %eax = xp leal -4(%ebp) %edx testl %eax %eax cmove %edx %eax movl (%eax) %eax
如此,xp等于0时,则无需访问它。
int fact_do(int x) { int result = ; do { result *= x; x = x - 1; } while (x > 1); return result; }
编译器首先将代码转换为Goto Version,方便转换成机器语言:
int fact_goto(int x) { int result = 1; loop: result *= x; x = x - 1; if (x > 1) goto loop; return result; }
与汇编相对照:
Registers:
%edx x;
%eax result
fact_goto: pushl %ebp # Setup movl %esp, %ebp # Setup movl $1, %eax # eax = 1 movl 8(%ebp), %edx # edx = x L11: imull %edx, %eax # result *= x decl %edx # x-- cmpl $1, %edx # Compare X : 1 jg L11 #if > goto loop movl %ebp, %esp # Finish popl %ebp # Finish ret # Finish
int fact_while(int x) { int result = 1; while (x > 1) { result *= x; x = x - 1; }; return result; }
Goto Version - 1
int fact_while_goto(int x) { int result = 1; loop: if (! (x > 1)) goto done; result *= x; x = x - 1; goto loop; done: return result; }
目前gcc模式(4.0以后(不确定),以及早期gcc模式)如下:
Goto Version - 2
int fact_while_goto2(int x) { int result = 1; if (! (x > 1)) goto done; loop: result *= x; x = x - 1; if (x > 1) goto loop; done: return result; }
编译器转换成了do-while模式。
对于for循环,也要转换为Goto Version,历程如下:
For Version -> While Version -> Do-While Version -> Goto Version
历史上gcc采用过多种转换模式,经历了“否定之否定”的过程:do-while -> Jump-to-middle -> do-while。
int fact_while(int x) { int result = 1; while (x > 1) { result *= x; x = x - 1; }; return result; }
转换成Goto Version:
int fact_while_goto3(int x) { int result = 1; goto middle; loop: result *= x; x = x - 1; middle: if (x > 1) goto loop; return result; }
Jump-to-Middle转换成汇编效率更高。
使用gcc 3.4.4 -O2对c代码进行编译:
# x in %edx, result in $eax jmp L34 # goto Middle L35: # Loop: imull %edx, %eax # result *= x decl %edx # x-- L34: # Middle: cmp $1, %edx # x : 1 jg L35 # if >, goto Loop
这么做的好处:
但是问题是:
调转指令往往会引起一定的性能损失,Branch Prediction技术被引入进行优化。
在硬件中做了一张表,如果发现有跳转指令,使用PC记录其调转结果,之后可以根据表、PC来预测跳转指令是否为跳转。
Branch Prediction的表项数有限,且其依据跳转与否的历史信息来做预测。因此条件跳转指令越多(一般以指令地址来识别),跳转历史信息越碎片化,就越不利于提升预测精确度。
Branch Prediction继续发展,采用了循环预测器技术(US Patent 5909573),能够对loop进行专门的预测,即对于“循环入口”的预测基本为真。
在内存中设置Jump Table跳转表:
Jump Table | Jump Targets |
---|---|
Targ0 | Code Block 0 |
…1 | …1 |
… | … |
long switch_eg(long x, long y, long z) { long w = 1; switch(x) { case 1: w = y * z; break; case 2: w = y / z; /* Fall Through */ case 3: w += z; break; case 5: case 6: w -= z; break; default: w = 2; } return w; }
Setup:
switch_eg: pushl %ebp # Setup movl %esp, %ebp # Setup pushl %ebx # Setup movl $1, %ebx # w = 1 movl 8(%ebp), %edx # edx = x movl 16(%ebp), %ecx # ecx = z cmpl $6, %edx # x : 6 ja .L61 # if > goto default jmp *.L62(, %edx, 4) # goto Jtab[x]
表结构:
无条件跳转指令:
本例中表项内容如下图:
对于switch结构的汇编如下:
switch(x) { ... case 2: // .L57 w = y/z; /* Fall Through */ case 3: // .L58 w += z; break; default: // .L61 w = 2; }
其汇编为:
.L61: // Default case movl $2, %ebx # w = 2 movl %ebx, %eax # Return w popl %ebx leave ret .L57: // Case 2: movl 12(%ebp), %eax # y cltd # Div prep idivl %ecx # y/z movl %eax, %ebx # w = y/z # Fall through .L58: // Case 3: addl %ecx, %ebx # w += z movl %ebx, %eax # Return w popl %ebx leave ret
switch(x) { ... case 1: // .L56 w = y*z; break; ... case 5: case 6: // .L60 w -= z; break; ... }
对于汇编指令:
.L60: // Case 5&6: subl %ecx, %ebx # w -= z movl %ebx, %eax # Return w popl %ebx leave ret .L56: // Case 1: movl 12(%ebp), %ebx # w = y imull %ecx, %ebx # w *= z movl %ebx, %eax # Return w leave ret
基本与32位版本一样,地址长度64位。
使用跳转表性能差,不现实,编译器编译成二叉树形式。