本次笔记内容：
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：
- cmove先进行了地址计算；
- 再决定最后选择谁。
- 在这道题中，如果xp不等于0的话，就把(%edx)取出来，挪到%eax里面去，替换掉预先填在%eax中的0值；
- 如果xp是空指针的话，虽然没有将(%edx)移动到%eax中，但是xp已经访问了一个0的地址，这是不对的。
下面是一种正确的操作：
先从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时，则无需访问它。
如何实现循环（Loops）
- 所有的循环模式（while, do-while, for）都转换为“do-while”形式，再转换为汇编形式；
- 历史上gcc采用过多种转换模式，经历了“否定之否定”的过程：do-while -> Jump-to-middle -> do-while。
“Do-While”循环实例
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
“While”循环版本
“While”循环版本1
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;
}
“While”循环版本2
目前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” -> “While” -> “Do-While”
对于for循环，也要转换为Goto Version，历程如下：
For Version -> While Version -> Do-While Version -> Goto Version
为什么gcc历史上经历了多种转换模式？
历史上gcc采用过多种转换模式，经历了“否定之否定”的过程：do-while -> Jump-to-middle -> do-while。
以“While”转换成“jump-to-middle”为例
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进行专门的预测，即对于“循环入口”的预测基本为真。
Switch语句
- 多个case对应同一段处理语句；
- “Fall through”；
- case值并不连续。
在内存中设置Jump Table跳转表：
| Jump Table | Jump Targets |
|---|---|
| Targ0 | Code Block 0 |
| …1 | …1 |
| … | … |
Swith语句示例（x86-32）
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]
表结构：
- 每个表项（及跳转地址）占4字节；
- 基地址是 .L62。
无条件跳转指令：
- jmp .L61
-
- Jump target is denoted by label .L61
- jmp *.L62(, %edx, 4)
-
- Start of jump table denoted by label .L62
-
- Register %edx holds x
-
- Must scale by factor of 4 to get offset into table
-
- Fetch target from effective Address .L61 + x * 4, Only for 0 ≤ x ≤ 6 0 \le x \le 6 0≤x≤6
-
- 这表明是一个间接跳转，即目标地址存于内存地址中
本例中表项内容如下图：
对于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
x86-64下的Switch语句
基本与32位版本一样，地址长度64位。
Switch语句实例（case很稀疏）
使用跳转表性能差，不现实，编译器编译成二叉树形式。