5.8 编译器对循环结构的优化
5.7 节介绍了3种循环结构,在执行效率上,do循环结构是最高的。由于do循环在结构上非常精简,利用了程序执行时由低地址到高地址的特点,只使用一个条件跳转指令就完成了循环,因此已经无需在结构上进行优化处理。
由于循环结构中也有分支功能,所以4.4.2节介绍的分支优化同样适用于循环结构。分支优化会使用目标分支缓冲器,预读指令。由于do循环是先执行后比较,因此执行代码都在比较之前,如下所示。
int i=0;
00401248 mov dword ptr[ebp-4],0
do
{
i++;
0040124F mov eax, dword ptr[ebp-4]
00401252 add eax,1
00401255 mov dword ptr[ebp-4],eax
printf("%d",i);
;printf讲解略
}while(i<1000);
;此处的汇编代码在退出循环时才预测失败
00401269 cmp dword ptr[ebp-4],3E8h
00401270 jl main+1Fh(0040124f)
do循环结构中只使用了一次跳转就完成了循环功能,大大提升了程序的执行效率。因此,在三种循环结构中,它的执行效率最高。
while循环结构的效率要比do循环结构低。while循环结构先比较再循环,因此无法利用程序执行顺序来完成循环。同时,while循环结构使用了2个跳转指令,在程序流程上就弱于do循环结构。为了提升while循环结构的效率,可以将其转成效率较高的do循环结构。在不能直接转换成do循环结构的情况下,可以使用if单分支结构,将do循环结构嵌套在if语句块内,由if语句判定是否能执行循环体。因此,所有的while循环都可以转换成do循环结构,如图5-13所示。
图 5-13 while循环结构的优化图
图5-13为代码清单5-23使用O2选项后编译的Release版结构流程图,该图截取自IDA。图5-13划分了程序的流程,箭头方向显示,反汇编代码中有一个单分支结构与循环结构。首先由条件跳转指令jl比较参数,小于等于0则跳转。可见这是一个if语句。
如果jl跳转失败,则顺序向下执行,进入标号loc_40100C处。这是一个循环语句块。此语句块内使用条件跳转指令jle,当ecx小于等于edx时,跳转到地址标号loc_40100C处。edx中保存参数数据,ecx每次加1,使eax每次对ecx累加。先执行,后判断,有了这个特性便可将图5-13所对应的代码还原成由单分支结构中嵌套do循环结构的高级代码。转换成对应的C++代码如下:
int LoopWhile(int nCount){
int nSum=0;
int nIndex=0;
if(nCount>=0){
do{
nSum+=nIndex;
nIndex++;
}while(nIndex<=nCount)
}
return nSum;
}
经过转换后,代码的功能没有任何改变,只是在结构上有了调整,变成了单分支结构加do循环结构。
以上讨论了while循环结构的优化,可以将其转换为do循环结构来提升效率。
从结构特征上可知,for循环是执行速度最慢的,它需要三个跳转指令才能够完成循环,因此也需要对其进行优化。for循环可以这么转换吗?从循环结构上看,其结构特征和while循环结构类似。由于赋初值部分不属于循环体,可以忽略。只要将比较部分放到循环体内,即是一个while循环结构。既然可以转换while循环结构,那么自然可以转换为do循环结构进行优化以提升效率。
有了for循环结构的优化方案,那么在对其优化过程中,VC++6.0能否按照此方案进行优化呢?将代码清单5-24使用O2选项进行重新编译,优化后的for循环反汇编代码如代码清单5-25所示。
代码清单5-25 for循环结构—Release版
.text:00401000 sub_401000 proc near
;函数参数标号定义arg_0
.text:00401000 arg_0=dword ptr 4
;使用edx保存参数arg_0
.text:00401000 mov edx,[esp+arg_0]
;清空eax, ecx
.text:00401004 xor eax, eax
.text:00401006 xor ecx, ecx
.text:00401008 test edx, edx
;检查edx,小于0则跳转到标号short locret_401013处,该函数结束
.text:0040100A jl short locret_401013
;说明此处标号在地址sub_401000+0x11处被调用
.text:0040100C loc_40100C:
;执行eax加等于ecx操作
.text:0040100C add eax, ecx
;执行ecx自加1操作
.text:0040100E inc ecx
.text:0040100F cmp ecx, edx
;比较ecx与edx,小于等于则跳转到标号short loc_40100C处,这是一个向上跳
.text:00401011 jle short loc_40100C
;函数返回地址标号locret_401013处,被地址标号sub_401000+0x0A处调用
.text:00401013 locret_401013:
.text:00401013 retn
分析代码清单5-25发现,它与图5-13的思路竟然完全一致。编译器通过检查,将for循环结构最终转换成了do循环结构。使用if单分支结构进行第一次执行循环体的判断,再将转换后的do循环嵌套在if语句中,就形成了“先执行,后判断”的do循环结构。由于在O2选项下,while循环及for循环都可以使用do循环进行优化,所以在分析经过O2选项优化的反汇编代码时,很难转换回相同源码,只能尽量还原等价源码。读者可根据个人习惯转换对应的循环结构。
从结构上优化循环后,还需从细节上再次优化,以进一步提高循环的效率。4.4节介绍了编译器的各种优化技巧,循环结构的优化也使用这些技巧,其中常见的优化方式是“代码外提”。例如,循环结构中经常有重复的操作,在对循环结构中语句块的执行结果没有任何影响的情况下,可选择相同代码外提,以减少循环语句块中的执行代码,提升循环执行效率,如代码清单5-26所示。
代码清单5-26 循环结构优化—代码外提
//C++源码说明:for循环完成整数累加和
int CodePick(int nCount){
int nSum=0;
int nIndex=0;
do{
nSum+=nIndex;
nIndex++;
//此处代码每次都要判断nCount-1,nCount并没有自减,仍然为一个固定值
//可在循环体外先对nCount进行减等于1操作,再进入循环体
}while(nIndex<nCount-1);
return nSum;
}
//经过优化后的反汇编代码
.text:00401000 sub_401000 proc near;CODE XREF:_main+21-p
.text:00401000 arg_0=dword ptr 4
;获取参数到edx中
.text:00401000 mov edx,[esp+arg_0]
.text:00401004 xor eax, eax
.text:00401006 xor ecx, ecx
;代码外提,对edx执行自减1操作
.text:00401008 dec edx
;进入循环体,在循环体内直接对保存参数的edx进行比较,没有任何减1操作
.text:00401009 loc_401009:;CODE XREF:sub_401000+E j
.text:00401009 add eax, ecx
.text:0040100B inc ecx
.text:0040100C cmp ecx, edx
.text:0040100E jl short loc_401009
.text:00401010 retn
.text:00401010 sub_401000 endp
分析代码清单5-26可知,编译器将循环比较“nIndex<nCount-1”中的“nCount-1”进行了外提。由于“nCount-1”中nCount在循环体中没有被修改,因此对它的操作是可以被拿到循环体外。被外提后的代码如下:
int CodePick(int nCount){
int nSum=0;
int nIndex=0;
nCount-=1;//外提代码
do{
nSum+=nIndex;
nIndex++;
}while(nIndex<nCount);//原来的nCount-1被外提了
return nSum;
}
这种外提是有选择性的—只有在不影响循环结果的情况下,才可以外提。
除了代码外提,还可以通过一些方法进一步提升循环结构的执行效率—强度削弱,即用等价的低强度运算替换原来代码中的高强度运算,例如,用加法代替乘法,如代码清单5-27所示。
代码清单5-27 循环强度降低优化—Release版
//C++源码说明:强度削弱
int main(int argc){
int t=0;
int i=0;
while(t<argc){
t=i*99;//强度削弱后,这里将不会使用乘法运算
i++;//此处转换后将为t=i;i+=99;
}
//利用加法运算替换掉了指令周期长的乘法运算
printf("%d",t);
return 0;
}
;优化后的反汇编代码
.text:00401020 arg_0=dword ptr 4
;将参数信息保存到edx中
.text:00401020 mov edx,[esp+arg_0]
.text:00401024 xor eax, eax;清空eax
.text:00401026 test edx, edx
.text:00401028 jle short loc_401035
.text:0040102A xor ecx, ecx;清空ecx
.text:0040102C
;循环语句块首地址
.text:0040102C loc_40102C:;CODE XREF:sub_401020+13 j
.text:0040102C mov eax, ecx;将ecx传入eax中
;ecx自加63h,即十进制99,等价于ecx每次加1乘以99
.text:0040102E add ecx,63h
.text:00401031 cmp eax, edx
.text:00401033 jl short loc_40102C;eax小于edx则执行跳转
.text:00401035
.text:00401035 loc_401035:;CODE XREF:sub_401020+8 j
;printf函数调用处略
.text:00401043 retn
.text:00401043 sub_401020 endp