高效的C編程之C循環(huán)結(jié)構(gòu)

14.5 C循環(huán)結(jié)構(gòu)
　　循環(huán)體是程序設(shè)計(jì)與優(yōu)化的重點(diǎn)考慮對(duì)象。本節(jié)將著重講解在ARM上處理for和while循環(huán)最有效的方法。
　　14.5.1 循環(huán)中止
　　首先來(lái)看下面的例子，兩個(gè)不同的循環(huán)退出條件，產(chǎn)生的不同匯編代碼。
　　C源程序如下所示。
　　int fact1 （int n）
　　{
　　int i， fact = 1;
　　for （i = 1; i 《= n; i++）
　　fact *= i;
　　return （fact）;
　　}
　　int fact2 （int n）
　　{
　　int i， fact = 1;
　　for （i = n; i ！= 0; i--）
　　fact *= i;
　　return （fact）;
　　}
　　產(chǎn)生的匯編代碼如下所示。
　　fact1
　　MOV a3，#1
　　MOV a2，#1
　　CMP a1，#1
　　BLT |L000020.J5.fact1|
　　|L000010.J4.fact1|
　　MUL a3，a2，a3
　　ADD a2，a2，#1
　　CMP a2，a1
　　BLE |L000010.J4.fact1|
　　|L000020.J5.fact1|
　　MOV a1，a3
　　MOV pc，lr
　　fact2
　　MOVS a2，a1
　　MOV a1，#1
　　MOVEQ pc，lr
　　|L000034.J4.fact2|
　　MUL a1，a2，a1
　　SUBS a2，a2，#1
　　BNE |L000034.J4.fact2|
　　MOV pc，lr
　　從產(chǎn)生的匯編代碼中，可以看出兩個(gè)函數(shù)雖然實(shí)現(xiàn)的功能相同，但產(chǎn)生的代碼效率卻不盡相同。這里的關(guān)鍵是，循環(huán)的中止條件應(yīng)為計(jì)數(shù)減到零（count down to zero），而不是計(jì)數(shù)增加到某個(gè)值。由于減計(jì)數(shù)結(jié)果已存儲(chǔ)在條件標(biāo)志里，與零比較的指令就可以省略。同時(shí)也可以少用一個(gè)寄存器來(lái)存儲(chǔ)循環(huán)中止值。
　　注意上面的例子使用了-O2 –Otime的編譯選項(xiàng)，如果使用-Ospace選項(xiàng)，編譯結(jié)果會(huì)有不同。
　　對(duì)循環(huán)計(jì)數(shù)值i來(lái)說(shuō)，如果i是無(wú)符號(hào)的，則循環(huán)繼續(xù)的條件既可以是i！=0，也可以是i 》 0。由于i不可能是負(fù)數(shù)，所以這兩個(gè)條件是等價(jià)的。而對(duì)一個(gè)有符號(hào)的循環(huán)計(jì)數(shù)值來(lái)說(shuō)，最好不要用條件i 》 0作為循環(huán)繼續(xù)執(zhí)行的條件。如果使用i 》 0作為循環(huán)繼續(xù)執(zhí)行的條件，編譯器將生成下面的代碼。
　　SUB a2，a2，#1
　　CMP r1，＃0
　　BGT |L000034.J4.fact2|
　　這時(shí)，編譯器多增加了一條CMP指令，主要是為了防止有符號(hào)數(shù)i= ?0x8000000。總之，無(wú)論對(duì)于有符號(hào)還是無(wú)符號(hào)的循環(huán)計(jì)數(shù)值，都應(yīng)該使用i ！= 0作為循環(huán)的結(jié)束條件。對(duì)于有符號(hào)數(shù)i，這比使用i 》 0少了一條指令。
　　14.5.2 循環(huán)展開(kāi)
　　在14.5.1節(jié)中可以發(fā)現(xiàn)，每次循環(huán)需要在循環(huán)體外加兩條指令：一條減法指令來(lái)減少循環(huán)計(jì)數(shù)值和一條條件分支指令。通常這些指令稱為循環(huán)開(kāi)銷（Loop Overhead）。在ARM7或ARM9處理器上，加法指令需要1個(gè)周期，條件分支指令需要3個(gè)周期，這樣每個(gè)循環(huán)就需要4個(gè)周期的開(kāi)銷。
　　可以通過(guò)展開(kāi)循環(huán)體（Loop Unrolling），即重復(fù)循環(huán)主體多次，同時(shí)按同樣的比例減少循環(huán)次數(shù)來(lái)降低循環(huán)開(kāi)銷。
　　下面的例子通過(guò)將循環(huán)體展開(kāi)4次，來(lái)達(dá)到減少循環(huán)開(kāi)銷的目的。
　　int countbit1（uint n）
　　{ int bits = 0;
　　while （n ！= 0）
　　{
　　if （n & 1） bits++;
　　n 》》= 1;
　　}
　　return bits;
　　}
　　將循環(huán)主體展開(kāi)。
　　int countbit2（uint n）
　　{ int bits = 0;
　　while （n ！= 0）
　　{
　　if （n & 1） bits++;
　　if （n & 2） bits++;
　　if （n & 4） bits++;
　　if （n & 8） bits++;
　　n 》》= 4;
　　}
　　return bits;
　　}
　　這里減少了4N的循環(huán)開(kāi)銷（N=4，即循環(huán)體執(zhí)行的次數(shù)）。如果循環(huán)體中存在耗時(shí)的Store/Load指令，則代碼執(zhí)行效率的提高將更明顯。
　　ARM編譯器不會(huì)自動(dòng)將循環(huán)體展開(kāi)，只有用戶自己判斷何時(shí)將循環(huán)體展開(kāi)，到底應(yīng)該展開(kāi)多少次，如果循環(huán)的次數(shù)不是循環(huán)展開(kāi)的倍數(shù)該怎么辦？下面就將詳細(xì)討論，用戶編寫(xiě)自己的循環(huán)展開(kāi)程序時(shí)，需要注意的問(wèn)題。
　　① 只有當(dāng)循環(huán)展開(kāi)對(duì)提高應(yīng)用程序的整體性能非常重要時(shí)，才進(jìn)行循環(huán)展開(kāi)；否則反而會(huì)增加代碼尺寸。
　　② 應(yīng)設(shè)法使循環(huán)的次數(shù)是循環(huán)展開(kāi)的倍數(shù)。如果難以實(shí)現(xiàn)，那么就要增加額外的代碼來(lái)處理數(shù)組的剩余元素。這將增加少許代碼量，但可以保持較好的性能。
?