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