本章会围绕以下程序进行演示:
#include <stdio.h>
void f_signed (int a, int b)
{
if (a>b)
printf ("a>b\n");
if (a==b)
printf ("a==b\n");
if (a<b)
printf ("a<b\n");
};
void f_unsigned (unsigned int a, unsigned int b)
{
if (a>b)
printf ("a>b\n");
if (a==b)
printf ("a==b\n");
if (a<b)
printf ("a<b\n");
};
int main()
{
f_signed(1, 2);
f_unsigned(1, 2);
return 0;
};
x86 + MSVC
在关闭优化选项时,使用MSVC编译上述源程序,可得到f_signed()函数。
指令清单12.1 Non-optimizing MSVC 2010
_a$ = 8
_b$ = 12
_f_signed PROC
push ebp
mov ebp, esp
mov eax, DWORD PTR _a$[ebp]
cmp eax, DWORD PTR _b$[ebp]
jle SHORT $LN3@f_signed
push OFFSET $SG737 ; 'a>b'
call _printf
add esp, 4
$LN3@f_signed:
mov ecx, DWORD PTR _a$[ebp]
cmp ecx, DWORD PTR _b$[ebp]
jne SHORT $LN2@f_signed
push OFFSET $SG739 ; 'a==b'
call _printf
add esp, 4
$LN2@f_signed:
mov edx, DWORD PTR _a$[ebp]
cmp edx, DWORD PTR _b$[ebp]
jge SHORT $LN4@f_signed
push OFFSET $SG741 ; 'a<b'
call _printf
add esp, 4
$LN4@f_signed:
pop ebp
ret 0
_f_signed ENDP
第一个条件转移指令是JLE,即“Jump if Less or Equal”。如果上一条CMP指令的第一个操作表达式小于或等于(不大于)第二个表达式,JLE将跳转到指令所标明的地址;如果不满足上述条件,则运行下一条指令,就本例而言程序将会调用printf()函数。第二个条件转移指令是JNE,“Jump if Not Equal”,如果上一条CMP的两个操作符不相等,则进行相应跳转。
第三个条件转移指令是JGE,即“Jump if Greater or Equal”。如果CMP的第一个表达式大于或等于第二个表达式(不小于),则进行跳转。这段程序里,如果三个跳转的判断条件都不满足,将不会调用printf()函数;不过,除非进行特殊干预,否则这种情况应该不会发生。
现在我们观察f_unsigned()函数的汇编指令。f_unsigned()函数和f_signed()函数大体相同。它们的区别集中体现在条件转移指令上:f_unsinged()函数的使用的条件转移指令是JBE和JAE,而f_signed()函数使用的条件转移指令则是JLE和JGE。
使用GCC编译上述程序,可得到f_unsigned()的汇编指令如下。
指令清单12.2 GCC
_a$ = 8 ; size = 4
_b$ = 12 ; size = 4
_f_unsigned PROC
push ebp
mov ebp, esp
mov eax, DWORD PTR _a$[ebp]
cmp eax, DWORD PTR _b$[ebp]
jbe SHORT $LN3@f_unsigned
push OFFSET $SG2761 ; 'a>b'
call _printf
add esp, 4
$LN3@f_unsigned:
mov ecx, DWORD PTR _a$[ebp]
cmp ecx, DWORD PTR _b$[ebp]
jne SHORT $LN2@f_unsigned
push OFFSET $SG2763 ; 'a==b'
call _printf
add esp, 4
$LN2@f_unsigned:
mov edx, DWORD PTR _a$[ebp]
cmp edx, DWORD PTR _b$[ebp]
jae SHORT $LN4@f_unsigned
push OFFSET $SG2765 ; 'a<b'
call _printf
add esp, 4
LN4@f_unsigned:
Pop ebp
Ret 0
_f_unsigned ENDP
GCC编译的结果与MSVC编译的结果基本相同。
经GCC编译后,f_unsigned()函数使用的条件转移指令是JBE(Jump if Below or Equal,相当于JLE)和JAE(Jump if Above or Equal,相当于JGE)。JA/JAE/JB/JBE与JG/JGE/JL/JLE的区别,在于它们检查的标志位不同:前者检查借/进位标志位CF(1意味着小于)和零标志位ZF(1意味着相等),后者检查“SF XOR OF”(1意味着异号)和ZF。从指令参数的角度看,前者适用于unsigned(无符号)类型数据的(CMP)运算,而后者的适用于signed(有符号)类型数据的运算。
本书第30章会介绍signed类型数据。可见,根据条件转移的指令,我们可以直接判断CMP所比较的变量的数据类型。
接下来,我们一起研究main()函数的汇编代码。
指令清单12.3 main()
_main PROC
push ebp
mov ebp, esp
push 2
push 1
call _f_signed
add esp, 8
push 2
push 1
call _f_unsigned
add esp, 8
xor eax, eax
pop ebp
ret 0
_main ENDP
x86 + MSVC + OllyDbg
我们可以通过OllyDbg直观地观察到指令对标志寄存器的影响。我们先用OllyDbg观察f_unsigned()函数比较无符号数的过程。f_unsigned()函数使用了CMP指令,分三次比较了两个相同的unsigned类型数据。因为参数相同,所以CMP设置的标志位必定相同。
如图12.1所示,在运行到第一个条件转移指令时,C=1, P=1, A=1, Z=0, S=1, T=0, D=0, O=0。OllyDbg会使用标志位的首字母作为该标志位的简称。
图12.1 使用OllyDbg:观察f_unsigned()的第一个条件转移指令
OllyDbg在左下窗口进行提示,JBE条件跳转指令的条件已经达成,下一步会进行相应跳转。这种预测准确无误,JBE的触发条件是(CF=1或ZF=1)。条件表达式为真时,JBE确实会进行跳转。
如图12.2所示,在运行到第二个条件转移指令——JNZ指令时,ZF=0。所以OllyDbg能够判断程序会进行相应跳转。
图12.2 使用OllyDbg观察f_unsigned()函数的第二个条件转移指令
如图12.3所示,运行到第三个条件转移指令——JNB指令的时候,借/进位标志CF=0,条件表达式会为假,所以不会发生跳转,程序将执行第三个printf()指令。
图12.3 使用OllyDbg观察f_unsigned()函数的第三个条件转移指令
现在来调试下示例程序里的f_signed()函数,它的参数为signed型数据。
在运行f_signed()函数时,标志位的状态和刚才一样。即,运行CMP指令之后,C=1, P=1, A=1, Z=0, S=1, T=0, D=0, O=0。
第一个条件转移指令——JLE指令将会被触发,如图12.4所示。
图12.4 使用OllyDbg观察f_signed()函数的第一个条件转移指令
参照[Int13],触发JLE的条件是ZF=1或SF≠OF。本例满足SF≠OF的条件。
由于ZF=0,第二个条件转移指令——JNZ指令会被触发,如图12.5所示。
图12.5 使用OllyDbg观察f_signed()函数的第二个条件转移指令
而第三个条件转移指令——JGE指令不会被触发。触发JGE的条件是SF=OF,而当前情形不满足这个条件,如图12.6所示。
图12.6 使用OllyDbg观察f_signed()函数的第三个条件转移指令
x86 + MSVC +Hiew
我们还可以用Hiew给可执行文件打补丁,强制f_unsigned()函数永远打印“a==b”、忽略它的输入参数,如图2.7所示。
图12.7 使用Hiew打开f_unsigned()函数
本文将分3次修改上述可执行程序,分别完成下述三个任务:
强制触发第一个条件转移指令。
强制屏蔽第二个条件转移指令。
强制触发第三个条件转移指令。
我们可以直接修改程序,令程序流永远转向第二个printf()函数并打印“a==b”。
故而需要修改三条指令(3个字节):
把第一个条件转移指令改为JMP,并保留原始的转移偏移量(jump offset)。
第二个条件转移指令的触发条件不一定成立。无论触发条件是否成立,我们都要它跳转到下一条指令。所以,我们把转移偏移量设置为零。对于条件转移语句来说,跳转的目标地址是下一条地址与转移偏移量的和。把转移偏移量设置为零之后,程序会继续执行下一条指令。
第三个条件转移指令的修改方法和第一个条件转移指令的修改方法相同。我们只需把将条件转移指令换成JMP(无条件转移指令)即可。
修改之后的f_unsigned()函数如图12.8所示。
图12.8 经过修改之后的f_unsigned()函数
三个条件转移指令全部都要修改。如果少修改了一个指令,它就可能会多次调用printf()函数,与我们的预期——只调用一次printf()函数的任务目标相悖。
Non-optimizing GCC
如果关闭了GCC的优化选项,那么它编译出来的程序和MSVC编译出来的程序没什么区别,只不过就是把printf()函数替换为了puts()函数[1]。
Optimizing GCC
聪明的您一定会问,既然CMP比较的是相同的值,比较之后的标志位的状态也相同,那么何必要对同样的参数进行多次比较呢?或许MSVC真的不能再智能一些了;但是启用优化选项后,GCC 4.8.1确实能够进行这种深度优化。
指令清单12.4 GCC 4.8.1 f_signed()
f_signed:
mov eax, DWORD PTR [esp+8]
cmp DWORD PTR [esp+4], eax
jg .L6
je .L7
jge .L1
mov DWORD PTR [esp+4], OFFSET FLAT:.LC2 ; "a<b"
jmp puts
.L6:
mov DWORD PTR [esp+4], OFFSET FLAT:.LC0 ; "a>b"
jmp puts
.L1:
rep ret
.L7:
mov DWORD PTR [esp+4], OFFSET FLAT:.LC1 ; "a==b"
jmp puts
很明显,它使用jmp指令替代了臃肿的“CALL ……puts …… RETN”指令。本书将在13.1.1节里详细解说这种编译技术。
我们不得不说在x86的系统中,这种程序比较少见。MSVC 2012做不到GCC那种程度的深度优化。另一方面,汇编语言的编程人员确实可能学会Jcc指令的连用技巧。所以,如果您遇到了这样精简的程序,而且还能够判断出它不是GCC编译出来的程序,那么您基本上可以判断它是手写出来的汇编程序。
即使开启了同样的优化选项,f_unsigned()函数对应的指令也没有那么精致。
指令清单12.5 GCC 4.8.1 f_unsigned()
f_unsigned:
push esi
push ebx
sub esp, 20
mov esi, DWORD PTR [esp+32]
mov ebx, DWORD PTR [esp+36]
cmp esi, ebx
ja .L13
cmp esi, ebx ; instruction may be removed
je .L14
.L10:
jb .L15
add esp, 20
pop ebx
pop esi
ret
.L15:
mov DWORD PTR [esp+32], OFFSET FLAT:.LC2 ; "a<b"
add esp, 20
pop ebx
pop esi
jmp puts
.L13:
mov DWORD PTR [esp], OFFSET FLAT:.LC0 ; "a>b"
call puts
cmp esi, ebx
jne .L10
.L14:
mov DWORD PTR [esp+32], OFFSET FLAT:.LC1 ; "a==b"
add esp, 20
pop ebx
pop esi
jmp puts
程序中只有两条CMP指令,至少它优化去了一个CMP指令。可见,GCC 4.8.1的优化算法还有改进的空间。
32位ARM程序
Optimizing Keil 6/2013 (ARM mode)
指令清单12.6 Optimizing Keil 6/2013 (ARM mode)
.text:000000B8 EXPORT f_signed
.text:000000B8 f_signed ; CODE XREF: main+C
.text:000000B8 70 40 2D E9 STMFD SP!, {R4-R6,LR}
.text:000000BC 01 40 A0 E1 MOV R4, R1
.text:000000C0 04 00 50 E1 CMP R0, R4
.text:000000C4 00 50 A0 E1 MOV R5, R0
.text:000000C8 1A 0E 8F C2 ADRGT R0, aAB ; "a>b\n"
.text:000000CC A1 18 00 CB BLGT __2printf
.text:000000D0 04 00 55 E1 CMP R5, R4
.text:000000D4 67 0F 8F 02 ADREQ R0, aAB_0; "a==b\n"
.text:000000D8 9E 18 00 0B BLEQ __2printf
.text:000000DC 04 00 55 E1 CMP R5, R4
.text:000000E0 70 80 BD A8 LDMGEFD SP!, {R4-R6,PC}
.text:000000E4 70 40 BD E8 LDMFD SP!, {R4-R6,LR}
.text:000000E8 19 0E 8F E2 ADR R0, aAB_1 ; "a<b\n"
.text:000000EC 99 18 00 EA B __2printf
.text:000000EC ; End of function f_signed
ARM模式的多数指令都存在着相应的条件执行指令。这些派生出来的条件执行指令仅会在特定标志位为1的情况下执行。换句话说,只有当前面存在比较数值的指令时,后面才可能会出现这种派生出来的条件执行指令。
举例来讲,加法指令ADD指令实际上是ADDAL指令。“AL”就是always的缩写,即ADDAL总会被无条件执行。在32位的ARM指令中,条件判断表达式被封装在条件执行指令的前(最高)4位——条件字段(condition field)里。即使是无条件转移指令B指令,其前4位还是条件字段。从指令构成上说,B指令仍然属于条件转移指令,只不过它的条件字段是AL而已。顾名思义,AL的作用就是忽略标志寄存器、永远执行这条指令。
ADRGT指令中的GT代表greater than(大于)。该指令依据先前CMP指令的比较结果,而判断是否执行寻址指令。当且仅当CMP比较的第一个值大于第二个值的时候,ADRGT指令才会执行寻址(ADR)指令。
后面的BLGT指令有异曲同工之妙。仅在相同条件下,即当且仅当CMP比较的第一个值大于第二个值的时候,BLGT指令才会执行BL指令。在这个条件成立的时候,前面的ADRGT指令已经把字符串“a>b /n”的地址赋值给R0寄存器,成为了printf()的参数,而BLGT负责调用printf()。可见,当且仅当在R0的值(变量a)大于R4的值(变量b)的情况下,计算机才会运行后面那组带有-GT后缀的指令。很显然,这是一组相互关联的指令。
后面的ADREQ和BLEQ指令,都在最近一个CMP的操作数相等的情况下才会讲行ADR和BL指令的操作。程序之中连续两次出现“CMP R5, R4”指令,这是因为夹在其间的printf()函数可能会影响标志位。
LDMGEFD是“Great or Equal(大于或等于)”的情况下进行LDMFD (Load Multiple Full Descending) 操作的指令。
依此类推,“LDMGEFD SP!, {R4-R6,PC}”指令起到函数尾声的作用,不过它只会在“a>=b”的时候才会结束本函数。
如果上述条件不成立,即“a<b”的时候,会执行下一条指令“LDMFD SP!, {R4-R6,LR}”。这同样起到函数尾声的作用。该指令将恢复R4~R6寄存器、LR寄存器的值,而不恢复PC寄存器的值,且不会退出当前函数。
函数最后的两条指令,分别向printf()函数传递参数(字符串“a<b\n”),并且调用printf()函数。本书的6.2.1节已经介绍过:当调用方函数调用(跳转到)printf()函数之后,调用方函数可以伴随printf()函数退出而退出。所以本节不再进行有关解释。
f_unsigned()函数与f_signed()函数的功能十分类似。不同之处是它用到了ADRHI、BLHI和LDMSFD指令。指令尾部的-HI代表Unsigned Higher,CS代表Carry Set (greater than or equal)。因为参数的数据类型有所变化,所以这两个函数的具体指令有所区别。
这个程序的main()函数的汇编指令如下。
指令清单12.7 main()函数
.text:00000128 EXPORT main
.text:00000128 main
.text:00000128 10 40 2D E9 STMFD SP!, {R4,LR}
.text:0000012C 02 10 A0 E3 MOV R1, #2
.text:00000130 01 00 A0 E3 MOV R0, #1
.text:00000134 DF FF FF EB BL f_signed
.text:00000138 02 10 A0 E3 MOV R1, #2
.text:0000013C 01 00 A0 E3 MOV R0, #1
.text:00000140 EA FF FF EB BL f_unsigned
.text:00000144 00 00 A0 E3 MOV R0, #0
.text:00000148 10 80 BD E8 LDMFD SP!, {R4,PC}
.text:00000148 ; End of function main
可见,ARM模式的程序可以完全不依赖条件转移指令。
这样做有什么优点呢?依赖精简指令集(RISC)的ARM处理器采用流水线技术(pipeline)。简单地说,这种处理器在跳转指令方面的性能不怎么优越,所以它们的分支预测处理器(branch predictor unites)决定了整体的性能。对于采用流水线技术的处理器来说,运行其上的程序跳转次数越少(无论是条件转移还是无条件转移),程序的性能就越高。条件执行指令[2],会受益于其跳跃次数最少的优点,体现出最高的效率。详细介绍请参阅本书的33.1节
x86指令集里只有CMOVcc指令,没有其他的条件执行指令了。CMOVcc指令是仅在特定标志位为1(通常由CMP指令设置)的情况下才会执行MOV操作的条件执行指令。
Optimizing Keil 6/2013 (Thumb mode)
指令清单12.8 Optimizing Keil 6/2013 (Thumb mode)
.text:00000072 f_signed ; CODE XREF: main+6
.text:00000072 70 B5 PUSH {R4-R6,LR}
.text:00000074 0C 00 MOVS R4, R1
.text:00000076 05 00 MOVS R5, R0
.text:00000078 A0 42 CMP R0, R4
.text:0000007A 02 DD BLE loc_82
.text:0000007C A4 A0 ADR R0, aAB ; "a>b\n"
.text:0000007E 06 F0 B7 F8 BL __2printf
.text:00000082
.text:00000082 loc_82 ; CODE XREF: f_signed+8
.text:00000082 A5 42 CMP R5, R4
.text:00000084 02 D1 BNE loc_8C
.text:00000086 A4 A0 ADR R0, aAB_0 ; "a==b\n"
.text:00000088 06 F0 B2 F8 BL __2printf
.text:0000008C
.text:0000008C loc_8C ; CODE XREF: f_signed+12
.text:0000008C A5 42 CMP R5, R4
.text:0000008E 02 DA BGE locret_96
.text:00000090 A3 A0 ADR R0, aAB_1 ; "a<b\n"
.text:00000092 06 F0 AD F8 BL __2printf
.text:00000096
.text:00000096 locret_96 ; CODE XREF: f_signed+1C
.text:00000096 70 BD POP {R4-R6,PC}
.text:00000096 ; End of function f_signed
在ARM系统的Thumb模式指令集里,只有B指令才有派生出来的条件执行指令。所以Thumb模式下的汇编指令看上去更为贴近x86指令。
上述指令里,条件转移指令有BLE(Less than or Equal)、BNE(Not Equal)、BGE(Greater than or Equal)。这些指令都可以望文生义。
f_unsigned函数十分雷同,只是里面出现了新的条件转移指令BLS(Unsigned Lower or Same)和BCS(Carry Set(Greater than or equal))。
64位ARM程序
Optimizing GCC(Linaro)4.9
指令清单12.9 f_signed()
f_signed:
; W0=a, W1=b
cmp w0, w1
bgt .L19 ; Branch if Greater Than (a>b)
beq .L20 ; Branch if Equal (a==b)
bge .L15 ; Branch if Greater than or Equal (a>=b) (impossible here)
; a<b
adrp x0, .LC11 ; "a<b"
add x0, x0, :lo12:.LC11
b puts
.L19:
adrp x0, .LC9 ; "a>b"
add x0, x0, :lo12:.LC9
b puts
.L15: ; impossible here
ret
.L20:
adrp x0, .LC10 ; "a==b"
add x0, x0, :lo12:.LC10
b puts
指令清单12.10 f_unsigned()
f_unsigned:
stp x29, x30, [sp, -48]!
; W0=a, W1=b
cmp w0, w1
add x29, sp, 0
str x19, [sp,16]
mov w19, w0
bhi .L25 ; Branch if HIgher (a>b)
cmp w19, w1
beq .L26 ; Branch if Equal (a==b)
.L23:
bcc .L27 ; Branch if Carry Clear (if less than) (a<b)
; function epilogue, impossible to be here
ldr x19, [sp,16]
ldp x29, x30, [sp], 48
ret
.L27:
ldr x19, [sp,16]
adrp x0, .LC11 ; "a<b"
ldp x29, x30, [sp], 48
add x0, x0, :lo12:.LC11
b puts
.L25:
adrp x0, .LC9 ; "a>b"
str x1, [x29,40]
add x0, x0, :lo12:.LC9
bl puts
ldr x1, [x29,40]
cmp w19, w1
bne .L23 ; Branch if Not Equal
.L26:
ldr x19, [sp,16]
adrp x0, .LC10 ; "a==b"
ldp x29, x30, [sp], 48
add x0, x0, :lo12:.LC10
b puts
我在程序之中添加了注释。很明显,虽然有些条件表达式不可能成立,但是编译器不能自行判断出这种问题。所以程序留有一些永远不会执行的无效代码。
练习题
上述代码中存在无效代码。请在不添加新指令的情况下删除多余多指令。
MIPS处理器没有标志位寄存器,这是它最显著的特征之一。这种设计旨在降低数据相关性的分析难度。
x86的指令集中有SETcc指令,MIPS平台也有类似的指令:SLT(Set on Less Than/操作对象为有符号数)和SLTU(无符号数)。这两个指令会在条件表达式为真的时候设置目的寄存器为1,否则设置其为零。
随即可用BEQ(Branch on Equal)或BEN(Branch on Not Equal)指令检查上述寄存器的值,判断是否进行跳转。总之,在MIPS平台上组合使用这两种指令,可完成条件转移指令的比较和转移操作。
我们来看范本程序里处理有符号数的相应函数。
指令清单12.11 Non-optimizing GCC 4.4.5 (IDA)
.text:00000000 f_signed: # CODE XREF: main+18
.text:00000000
.text:00000000 var_10 = -0x10
.text:00000000 var_8 = -8
.text:00000000 var_4 = -4
.text:00000000 arg_0 = 0
.text:00000000 arg_4 = 4
.text:00000000
.text:00000000 addiu $sp, -0x20
.text:00000004 sw $ra, 0x20+var_4($sp)
.text:00000008 sw $fp, 0x20+var_8($sp)
.text:0000000C move $fp, $sp
.text:00000010 la $gp, __gnu_local_gp
.text:00000018 sw $gp, 0x20+var_10($sp)
; store input values into local stack:
.text:0000001C sw $a0, 0x20+arg_0($fp)
.text:00000020 sw $a1, 0x20+arg_4($fp)
; reload them.
.text:00000024 lw $v1, 0x20+arg_0($fp)
.text:00000028 lw $v0, 0x20+arg_4($fp)
; $v0=b
; $v1=a
.text:0000002C or $at, $zero ; NOP
; this is pseudoinstruction. in fact, "slt $v0,$v0,$v1" is there.
; so $v0 will be set to 1 if $v0<$v1 (b<a) or to 0 if otherwise:
.text:00000030 slt $v0, $v1
; jump to loc_5c, if condition is not true.
; this is pseudoinstruction. in fact, "beq $v0,$zero,loc_5c" is there:
.text:00000034 beqz $v0, loc_5C
; print "a>b" and finish
.text:00000038 or $at, $zero ; branch delay slot, NOP
.text:0000003C lui $v0, (unk_230 >> 16) # "a>b"
.text:00000040 addiu $a0, $v0, (unk_230 & 0xFFFF) # "a>b"
.text:00000044 lw $v0, (puts & 0xFFFF)($gp)
.text:00000048 or $at, $zero ; NOP
.text:0000004C move $t9, $v0
.text:00000050 jalr $t9
.text:00000054 or $at, $zero ; branch delay slot, NOP
.text:00000058 lw $gp, 0x20+var_10($fp)
.text:0000005C
.text:0000005C loc_5C: # CODE XREF: f_signed+34
.text:0000005C lw $v1, 0x20+arg_0($fp)
.text:00000060 lw $v0, 0x20+arg_4($fp)
.text:00000064 or $at, $zero ; NOP
; check if a==b, jump to loc_90 if its not true':
.text:00000068 bne $v1, $v0, loc_90
.text:0000006C or $at, $zero ; branch delay slot, NOP
; condition is true, so print "a==b" and finish:
.text:00000070 lui $v0, (aAB >> 16) # "a==b"
.text:00000074 addiu $a0, $v0, (aAB & 0xFFFF) # "a==b"
.text:00000078 lw $v0, (puts & 0xFFFF)($gp)
.text:0000007C or $at, $zero ; NOP
.text:00000080 move $t9, $v0
.text:00000084 jalr $t9
.text:00000088 or $at, $zero ; branch delay slot, NOP
.text:0000008C lw $gp, 0x20+var_10($fp)
.text:00000090
.text:00000090 loc_90: # CODE XREF: f_signed+68
.text:00000090 lw $v1, 0x20+arg_0($fp)
.text:00000094 lw $v0, 0x20+arg_4($fp)
.text:00000098 or $at, $zero ; NOP
; check if $v1<$v0 (a<b), set $v0 to 1 if condition is true:
.text:0000009C slt $v0, $v1, $v0
; if condition is not true (i.e., $v0==0), jump to loc_c8:
.text:000000A0 beqz $v0, loc_C8
.text:000000A4 or $at, $zero ; branch delay slot, NOP
; condition is true, print "a<b" and finish
.text:000000A8 lui $v0, (aAB_0 >> 16) # "a<b"
.text:000000AC addiu $a0, $v0, (aAB_0 & 0xFFFF) # "a<b"
.text:000000B0 lw $v0, (puts & 0xFFFF)($gp)
.text:000000B4 or $at, $zero ; NOP
.text:000000B8 move $t9, $v0
.text:000000BC jalr $t9
.text:000000C0 or $at, $zero ; branch delay slot, NOP
.text:000000C4 lw $gp, 0x20+var_10($fp)
.text:000000C8
; all 3 conditions were false, so just finish:
.text:000000C8 loc_C8: # CODE XREF: f_signed+A0
.text:000000C8 move $sp, $fp
.text:000000CC lw $ra, 0x20+var_4($sp)
.text:000000D0 lw $fp, 0x20+var_8($sp)
.text:000000D4 addiu $sp, 0x20
.text:000000D8 jr $ra
.text:000000DC or $at, $zero ; branch delay slot, NOP
.text:000000DC # End of function f_signed
此处有两条指令是IDA的伪指令。“SLT REG0, REG1”的实际指令是“SLT REG0, REG0, REG1”,而BEQZ的实际指令是“BEQ REG, $ZERO, LABEL”。
f_unsigned()函数的汇编指令,只是把f_signed()函数中的SLT指令替换为SLTU(U是unsigned的缩写)。除此之外,处理有符号数和无符号数的两个函数完全相同。
指令清单12.12 Non-optimizing GCC 4.4.5 (IDA)
.text:000000E0 f_unsigned: # CODE XREF: main+28
.text:000000E0
.text:000000E0 var_10 = -0x10
.text:000000E0 var_8 = -8
.text:000000E0 var_4 = -4
.text:000000E0 arg_0 = 0
.text:000000E0 arg_4 = 4
.text:000000E0
.text:000000E0 addiu $sp, -0x20
.text:000000E4 sw $ra, 0x20+var_4($sp)
.text:000000E8 sw $fp, 0x20+var_8($sp)
.text:000000EC move $fp, $sp
.text:000000F0 la $gp, __gnu_local_gp
.text:000000F8 sw $gp, 0x20+var_10($sp)
.text:000000FC sw $a0, 0x20+arg_0($fp)
.text:00000100 sw $a1, 0x20+arg_4($fp)
.text:00000104 lw $v1, 0x20+arg_0($fp)
.text:00000108 lw $v0, 0x20+arg_4($fp)
.text:0000010C or $at, $zero
.text:00000110 sltu $v0, $v1
.text:00000114 beqz $v0, loc_13C
.text:00000118 or $at, $zero
.text:0000011C lui $v0, (unk_230 >> 16)
.text:00000120 addiu $a0, $v0, (unk_230 & 0xFFFF)
.text:00000124 lw $v0, (puts & 0xFFFF)($gp)
.text:00000128 or $at, $zero
.text:0000012C move $t9, $v0
.text:00000130 jalr $t9
.text:00000134 or $at, $zero
.text:00000138 lw $gp, 0x20+var_10($fp)
.text:0000013C
.text:0000013C loc_13C: # CODE XREF: f_unsigned+34
.text:0000013C lw $v1, 0x20+arg_0($fp)
.text:00000140 lw $v0, 0x20+arg_4($fp)
.text:00000144 or $at, $zero
.text:00000148 bne $v1, $v0, loc_170
.text:0000014C or $at, $zero
.text:00000150 lui $v0, (aAB >> 16) # "a==b"
.text:00000154 addiu $a0, $v0, (aAB & 0xFFFF) # "a==b"
.text:00000158 lw $v0, (puts & 0xFFFF)($gp)
.text:0000015C or $at, $zero
.text:00000160 move $t9, $v0
.text:00000164 jalr $t9
.text:00000168 or $at, $zero
.text:0000016C lw $gp, 0x20+var_10($fp)
.text:00000170
.text:00000170 loc_170: # CODE XREF: f_unsigned+68
.text:00000170 lw $v1, 0x20+arg_0($fp)
.text:00000174 lw $v0, 0x20+arg_4($fp)
.text:00000178 or $at, $zero
.text:0000017C sltu $v0, $v1, $v0
.text:00000180 beqz $v0, loc_1A8
.text:00000184 or $at, $zero
.text:00000188 lui $v0, (aAB_0 >> 16) # "a<b"
.text:0000018C addiu $a0, $v0, (aAB_0 & 0xFFFF) # "a<b"
.text:00000190 lw $v0, (puts & 0xFFFF)($gp)
.text:00000194 or $at, $zero
.text:00000198 move $t9, $v0
.text:0000019C jalr $t9
.text:000001A0 or $at, $zero
.text:000001A4 lw $gp, 0x20+var_10($fp)
.text:000001A8
.text:000001A8 loc_1A8: # CODE XREF: f_unsigned+A0
.text:000001A8 move $sp, $fp
.text:000001AC lw $ra, 0x20+var_4($sp)
.text:000001B0 lw $fp, 0x20+var_8($sp)
.text:000001B4 addiu $sp, 0x20
.text:000001B8 jr $ra
.text:000001BC or $at, $zero
.text:000001BC # End of function f_unsigned
本节将围绕以下程序进行演示:
int my_abs (int i)
{
if (i<0)
return -i;
else
return i;
};
上述程序的编译结果如下。
指令清单12.13 Optimizing MSVC 2012 x64
i$ = 8
my_abs PROC
; ECX = input
test ecx, ecx
; check for sign of input value
; skip NEG instruction if sign is positive
jns SHORT $LN2@my_abs
; negate value
neg ecx
$LN2@my_abs:
; prepare result in EAX:
mov eax, ecx
ret 0
my_abs ENDP
GCC 4.9的编译结果几乎相同。
指令清单12.14 Optimizing Keil 6/2013:Thumb mode
my_abs PROC
CMP r0,#0
; is input value equal to zero or greater than zero?
; skip RSBS instruction then
BGE |L0.6|
; subtract input value from 0:
RSBS r0,r0,#0
|L0.6|
BX lr
ENDP
ARM平台没有负数运算指令,所以Keil编译器使用了“零减去数值”的减法运算指令“Reverse Subtract”(减数和被减数位置对调的减法运算),同样达到了替换符号的效果。
因为ARM模式的指令集存在条件执行指令,所以开启优化选项后可得到如下指令。
指令清单12.15 Optimizing Keil 6/2013:ARM mode
my_abs PROC
CMP r0,#0
; execute "Reverse Subtract" instruction only if input value is less than 0:
RSBLT r0,r0,#0
BX lr
ENDP
即使没有使用条件转移指令(请参见33.1节),它也实现相同的功能。
ARM64的指令集存在求负运算的NEG指令。
指令清单12.16 Optimizing GCC 4.9 (ARM64)
my_abs:
sub sp, sp, #16
str w0, [sp,12]
ldr w0, [sp,12]
; compare input value with contents of WZR register
; (which always holds zero)
cmp w0, wzr
bge .L2
ldr w0, [sp,12]
neg w0, w0
b .L3
.L2:
ldr w0, [sp,12]
.L3:
add sp, sp, 16
ret
指令清单12.17 Optimizing GCC 4.4.5 (IDA)
my_abs:
; jump if $a0<0:
bltz $a0, locret_10
; just return input value ($a0) in $v0:
move $v0, $a0
jr $ra
or $at, $zero ; branch delay slot, NOP
locret_10:
; negate input value and store it in $v0:
jr $ra
; this is pseudoinstruction. in fact, this is "subu $v0,$zero,$a0" ($v0=0-$a0)
negu $v0, $a0
这里出现了新指令BLTZ(Branch if Less Than Zero),以及伪指令NEGU。NEGU指令计算零减去操作数的差。SUBU和NEGU指令中的后缀U代表它的操作数是无符号型数据,并且在整数溢出的情况下不会触发异常处理机制。
不使用转移指令同样可以计算绝对值。本书的第45章有详细说明。
C/C++都支持条件运算符:
表达式? 表达式: 表达式
例如:
const char* f (int a)
{
return a==10 ? "it is ten" : "it is not ten";
};
在编译含有条件运算符的语句时,早期无优化功能的编译器会以编译“if/else”语句的方法进行处理。
指令清单12.18 Non-optimizing MSVC 2008
$SG746 DB 'it is ten', 00H
$SG747 DB 'it is not ten', 00H
tv65 = -4 ; this will be used as a temporary variable
_a$ = 8
_f PROC
push ebp
mov ebp, esp
push ecx
; compare input value with 10
cmp DWORD PTR _a$[ebp], 10
; jump to $LN3@f if not equal
jne SHORT $LN3@f
; store pointer to the string into temporary variable:
mov DWORD PTR tv65[ebp], OFFSET $SG746 ; 'it is ten'
; jump to exit
jmp SHORT $LN4@f
$LN3@f:
; store pointer to the string into temporary variable:
mov DWORD PTR tv65[ebp], OFFSET $SG747 ; 'it is not ten'
$LN4@f:
; this is exit. copy pointer to the string from temporary variable to EAX.
mov eax, DWORD PTR tv65[ebp]
mov esp, ebp
pop ebp
ret 0
_f ENDP
指令清单12.19 Optimizing MSVC 2008
$SG792 DB 'it is ten', 00H
$SG793 DB 'it is not ten', 00H
_a$ = 8 ; size = 4
_f PROC
; compare input value with 10
cmp DWORD PTR _a$[esp-4], 10
mov eax, OFFSET $SG792 ; 'it is ten'
; jump to $LN4@f if equal
je SHORT $LN4@f
mov eax, OFFSET $SG793 ; 'it is not ten'
$LN4@f:
ret 0
_f ENDP
新编译器生成的程序更为简洁。
指令清单12.20 Optimizing MSVC 2012 x64
$SG1355 DB 'it is ten', 00H
$SG1356 DB 'it is not ten', 00H
a$ = 8
f PROC
; load pointers to the both strings
lea rdx, OFFSET FLAT:$SG1355 ; 'it is ten'
lea rax, OFFSET FLAT:$SG1356 ; 'it is not ten'
; compare input value with 10
cmp ecx, 10
; if equal, copy value from RDX ("it is ten")
; if not, do nothing. pointer to the string "it is not ten" is still in RAX as for now.
cmove rax, rdx
ret 0
f ENDP
启用优化选项后,GCC 4.8生成的x86指令同样使用了CMOVcc指令。相比之下,在关闭优化功能的情况下,GCC 4.8用条件转移指令编译条件操作符。
启用优化功能之后,Keil生成的ARM代码会应用条件运行指令ADRcc。
指令清单12.21 Optimizing Keil 6/2013 (ARM mode)
f PROC
; compare input value with 10
CMP r0, #0xa
; if comparison result is EQual, copy pointer to the "it is ten" string into R0
ADREQ r0,|L0.16| ; "it is ten"
; if comparison result is Not Equal, copy pointer to the "it is not ten" string into R0
ADRNE r0,|L0.28| ; "it is not ten"
BX lr
ENDP
|L0.16|
DCB "it is ten",0
|L0.28|
DCB "it is not ten",0
除非存在人为干预,否则ADREQ和ADRNE指令不可能在同一次调用期间都被执行。
在启用优化功能之后,Keil会给编译出的Thumb模式代码分配条件转移指令。毕竟在Thumb模式的指令之中,没有支持标志位判断的赋值指令。
指令清单12.22 Optimizing Keil 6/2013 (Thumb mode)
f PROC
; compare input value with 10
CMP r0,#0xa
; jump to |L0.8| if EQual
BEQ |L0.8|
ADR r0,|L0.12| ; "it is not ten"
BX lr
|L0.8|
ADR r0,|L0.28| ; "it is ten"
BX lr
ENDP
|L0.12|
DCB "it is not ten",0
|L0.28|
DCB "it is ten",0
启用优化功能之后,GCC(Linaro)4.9编译出来的ARM64程序同样用条件转移指令实现条件运算符。
指令清单12.23 Optimizing GCC (Linaro) 4.9
f:
cmp x0, 10
beq .L3 ; branch if equal
adrp x0, .LC1 ; "it is ten"
add x0, x0, :lo12:.LC1
ret
.L3:
adrp x0, .LC0 ; "it is not ten"
add x0, x0, :lo12:.LC0
ret
.LC0:
.string "it is ten"
.LC1:
.string "it is not ten"
ARM64同样没有能够判断标志位的条件赋值指令。而32位的ARM指令集[3],以及x86的CMOVcc指令都可以根据相应标志位进行条件赋值。虽然ARM64存在“条件选择”指令CSEL(Conditional SELect),但是GCC 4.9似乎无法给这种程序分配上这条指令。
不幸的是,GCC 4.45在编译MIPS程序方面的智能程度也有待完善。
指令清单12.24 Optimizing GCC 4.4.5 (assembly output)
$LC0:
.ascii "it is not ten\000"
$LC1:
.ascii "it is ten\000"
f:
li $2,10 # 0xa
; compare $a0 and 10, jump if equal:
beq $4,$2,$L2
nop ; branch delay slot
; leave address of "it is not ten" string in $v0 and return:
lui $2,%hi($LC0)
j $31
addiu $2,$2,%lo($LC0)
$L2:
; leave address of "it is ten" string in $v0 and return:
lui $2,%hi($LC1)
j $31
addiu $2,$2,%lo($LC1)
const char* f (int a)
{
if (a==10)
return "it is ten";
else
return "it is not ten";
};
启用优化功能之后,GCC 4.8在编译x86程序时能够应用CMOVcc指令。
指令清单12.25 Optimizing GCC 4.8
.LC0:
.string "it is ten"
.LC1:
.string "it is not ten"
f:
.LFB0:
; compare input value with 10
cmp DWORD PTR [esp+4], 10
mov edx, OFFSET FLAT:.LC1 ; "it is not ten"
mov eax, OFFSET FLAT:.LC0 ; "it is ten"
; if comparison result is Not Equal, copy EDX value to EAX
; if not, do nothing
Cmovne eax, edx
ret
Optimizing Keil编译的ARM程序,与指令清单12.21相同。
但是启用优化功能的MSVC 2012仍然没有什么起色。
启用优化功能之后,编译器会尽可能地避免使用条件转移指令。本书的33.1节将详细讲解这个问题。
int my_max(int a, int b)
{
if (a>b)
return a;
else
return b;
};
int my_min(int a, int b)
{
if (a<b)
return a;
else
return b;
};
指令清单12.26 Non-optimizing MSVC 2013
_a$ = 8
_b$ = 12
_my_min PROC
push ebp
mov ebp, esp
mov eax, DWORD PTR _a$[ebp]
; compare A and B:
cmp eax, DWORD PTR _b$[ebp]
; jump, if A is greater or equal to B:
jge SHORT $LN2@my_min
; reload A to EAX if otherwise and jump to exit
mov eax, DWORD PTR _a$[ebp]
jmp SHORT $LN3@my_min
jmp SHORT $LN3@my_min ; this is redundant JMP
$LN2@my_min:
; return B
mov eax, DWORD PTR _b$[ebp]
$LN3@my_min:
pop ebp
ret 0
_my_min ENDP
_a$ = 8
_b$ = 12
_my_max PROC
push ebp
mov ebp, esp
mov eax, DWORD PTR _a$[ebp]
; compare A and B:
cmp eax, DWORD PTR _b$[ebp]
; jump if A is less or equal to B:
jle SHORT $LN2@my_max
; reload A to EAX if otherwise and jump to exit
mov eax, DWORD PTR _a$[ebp]
jmp SHORT $LN3@my_max
jmp SHORT $LN3@my_max ; this is redundant JMP
$LN2@my_max:
; return B
mov eax, DWORD PTR _b$[ebp]
$LN3@my_max:
pop ebp
ret 0
_my_max ENDP
两个函数的唯一区别就是条件转移指令:第一个函数使用的是JGE(Jump if Greater or Equal),而第二个函数使用的是JLE(Jump if Less or Equal)。
上述每个函数里都存在一个多余的JMP指令。这可能是MSVC的问题。
无分支指令的编译方法
Keil编译的Thumb模式程序与x86程序有几分相似。
指令清单12.27 Optimizing Keil 6/2013 (Thumb mode)
my_max PROC
; R0=A
; R1=B
; compare A and B:
CMP r0,r1
; branch if A is greater then B:
BGT |L0.6|
; otherwise (A<=B) return R1 (B):
MOVS r0,r1
|L0.6|
; return
BX lr
ENDP
my_min PROC
; R0=A
; R1=B
; compare A and B:
CMP r0,r1
; branch if A is less then B:
BLT |L0.14|
; otherwise (A>=B) return R1 (B):
MOVS r0,r1
|L0.14|
; return
BX lr
ENDP
两个函数所用的转移指令不同:一个是BGT,而另一个是BLT。
在编译ARM模式程序时,编译器可能会使用条件执行指令(即“有分支”指令)。这种程序会显得更为短小。在编译条件表达式时,Keil编译器使用了MOVcc指令。
指令清单12.28 Optimizing Keil 6/2013 (ARM mode)
my_max PROC
; R0=A
; R1=B
; compare A and B:
CMP r0,r1
; return B instead of A by placing B in R0
; this instruction will trigger only if A<=B (hence, LE - Less or Equal)
; if instruction is not triggered (in case of A>B), A is still in R0 register
MOVLE r0,r1
BX lr
ENDP
my_min PROC
; R0=A
; R1=B
; compare A and B:
CMP r0,r1
; return B instead of A by placing B in R0
; this instruction will trigger only if A>=B (hence, GE - Greater or Equal)
; if instruction is not triggered (in case of A<B), A value is still in R0 register
MOVGE r0,r1
BX lr
ENDP
在启用优化功能的情况下,GCC 4.8.1和MSVC 2013都能使用CMOVcc指令。这个指令相当于ARM程序里的MOVcc指令。
指令清单12.29 Optimizing MSVC 2013
my_max:
mov edx, DWORD PTR [esp+4]
mov eax, DWORD PTR [esp+8]
; EDX=A
; EAX=B
; compare A and B:
cmp edx, eax
; if A>=B, load A value into EAX
; the instruction idle if otherwise (if A<B)
cmovge eax, edx
ret
my_min:
mov edx, DWORD PTR [esp+4]
mov eax, DWORD PTR [esp+8]
; EDX=A
; EAX=B
; compare A and B:
cmp edx, eax
; if A<=B, load A value into EAX
; the instruction idle if otherwise (if A>B)
cmovle eax, edx
ret
#include <stdint.h>
int64_t my_max(int64_t a, int64_t b)
{
if (a>b)
return a;
else
return b;
};
int64_t my_min(int64_t a, int64_t b)
{
if (a<b)
return a;
else
return b;
};
虽然编译出来的程序里存在不必要的数据交换,但是代码功能一目了然。
指令清单12.30 Non-optimizing GCC 4.9.1 ARM64
my_max:
sub sp, sp, #16
str x0, [sp,8]
str x1, [sp]
ldr x1, [sp,8]
ldr x0, [sp]
cmp x1, x0
ble .L2
ldr x0, [sp,8]
b .L3
.L2:
ldr x0, [sp]
.L3:
add sp, sp, 16
ret
my_min:
sub sp, sp, #16
str x0, [sp,8]
str x1, [sp]
ldr x1, [sp,8]
ldr x0, [sp]
cmp x1, x0
bge .L5
ldr x0, [sp,8]
b .L6
.L5:
ldr x0, [sp]
.L6:
add sp, sp, 16
ret
无分支指令的编译方法
既然函数参数就在寄存器里,那么就不必通过栈访问它们。
指令清单12.31 Optimizing GCC 4.9.1 x64
my_max:
; RDI=A
; RSI=B
; compare A and B:
cmp rdi, rsi
; prepare B in RAX for return:
mov rax, rsi
; if A>=B, put A (RDI) in RAX for return.
; this instruction is idle if otherwise (if A<B)
cmovge rax, rdi
ret
my_min:
; RDI=A
; RSI=B
; compare A and B:
cmp rdi, rsi
; prepare B in RAX for return:
mov rax, rsi
; if A<=B, put A (RDI) in RAX for return.
; this instruction is idle if otherwise (if A>B)
cmovle rax, rdi
ret
MSVC 2013的编译方法几乎一样。
ARM64指令集里有CSEL指令。它相当于ARM指令集中的MOVcc指令,以及x86平台的CMOVcc指令。它只是名字不同:“Conditional SELect”。
指令清单12.32 Optimizing GCC 4.9.1 ARM64
my_max:
; X0=A
; X1=B
; compare A and B:
cmp x0, x1
; select X0 (A) to X0 if X0>=X1 or A>=B (Greater or Equal)
; select X1 (B) to X0 if A<B
csel x0, x0, x1, ge
ret
my_min:
; X0=A
; X1=B
; compare A and B:
cmp x0, x1
; select X0 (A) to X0 if X0<=X1 or A<=B (Less or Equal)
; select X1 (B) to X0 if A>B
csel x0, x0, x1, le
ret
不幸的是,GCC 4.4.5在编译MIPS程序方面的智能化程度有限。
指令清单12.33 Optimizing GCC 4.4.5 (IDA)
my_max:
; set $v1 $a1<$a0,or clear otherwise (if $01>$a0):
slt $v1, $a1, $a0
; jump, if $v1 iso (or $a1>$a9):
beqz $v1, locret_10
; this is branch delay slot
; prepare $a1 in $v0 in case of branch triggered:
move $v0, $a1
; no branch triggered, prepare $a0 in $v0:
move $v0, $a0
locret_10:
jr $ra
or $at, $zero ; branch delay slot, NOP
; the min() function is same, but input operands in SLT instruction are swapped:
my_min
slt $v1, $a0, $a1
beqz $v1, locret_28
move $v0, $a1
move $v0, $a0
locret_28:
jr $ra
or $at, $zero ; branch delay slot, NOP
请注意分支延时槽现象:第一个MOVE指令“先于”BEQZ指令运行,而第二个MOVE指令仅在不发生跳转的情况下才会被执行。
条件转移指令的构造大体如下。
指令清单12.34 x86
CMP register, register/value
Jcc true ; cc=condition code
false:
... some code to be executed if comparison result is false ...
JMP exit
true:
... some code to be executed if comparison result is true ...
exit:
指令清单12.35 ARM
CMP register, register/value
Bcc true ; cc=condition code
false:
... some code to be executed if comparison result is false ...
JMP exit
true:
... some code to be executed if comparison result is true ...
exit:
指令清单12.36 遇零跳转
BEQZ REG, label
...
指令清单12.37 遇负数跳转
BLTZ REG, label
...
指令清单12.38 值相等的情况下跳转
BEQ REG1, REG2, label
...
指令清单12.39 值不等的情况下跳转
BNE REG1, REG2, label
...
指令清单12.40 第一个值小于第二个值的情况下跳转(signed)
SLT REG1, REG2, REG3
BEQ REG1, label
...
指令清单12.41 第一个值小于第二个值的情况下跳转(unsigned)
SLTU REG1, REG2, REG3
BEQ REG1, label
...
如果条件语句十分短,那么编译器可能会分配条件执行指令:
编译ARM模式的程序时应用MOVcc指令。
编译ARM64程序时应用CSEL指令。
编译x86程序时应用CMOVcc指令。
ARM
在编译ARM模式的程序时,编译器可能用条件执行指令替代条件转移指令。
指令清单12.42 ARM (ARM mode)
CMP register, register/value
instr1_cc ; some instruction will be executed if condition code is true
instr2_cc ; some other instruction will be executed if other condition code is true
... etc ...
在被执行指令不修改任何标志位的情况下,程序可有任意多条的条件执行指令。
Thumb模式的指令集里有IT指令。它可以把后续四条指令构成一个指令组,并且在条件表达式为真的时候运行这组指令。详细介绍请参见本书的17.7.2节。
指令清单12.43 ARM (Thumb mode)
CMP register, register/value
ITEEE EQ ; set these suffixes: if-then-else-else-else
instr1 ; instruction will be executed if condition is true
instr2 ; instruction will be executed if condition is false
instr3 ; instruction will be executed if condition is false
instr4 ; instruction will be executed if condition is false
请使用CSFL指令替代指令清单12.23中所有的条件转移语句。
[1] 请参见本书3.4.3节的解释。
[2] 即predicated instructions,泛指BLGT/ADREQ这类混合条件判定功能的操作指令。
[3] 请参阅ARM13a,p390,C5.5。