編譯器如何對(duì)代碼進(jìn)行優(yōu)化（下）

變量乘常量

• 常量為2的冪

乘法將會(huì)被替換為執(zhí)行周期更短的移位指令。

int fun(int n) {
    return n * 16;
}
// mov eax, n
// shl eax, 4

• 常量為非2的冪

因?yàn)?thumb 和 x86 指令集的差異，安卓平臺(tái)上處理的更好一些。

我并不推薦你把自己當(dāng)成編譯器，看到算式想著怎么轉(zhuǎn)成匯編，而是推薦記下這種算法，看到計(jì)算過(guò)程知道怎么轉(zhuǎn)成原式，當(dāng)然也不追求100%還原，邏輯一致即可。

編譯器會(huì)對(duì)非2的冪進(jìn)行拆解，例如：

• n * 15 = n * 16 - n = n << 4 - n
• n * 12 = n * 3 * 4 = (n << 1 + n) << 2

int value = n * 15;
// rsb.w r0, r1, r1, lsl #4

int value = n * 12;
// add.w r0, r1, r1, lsl #1

當(dāng)然 windows 平臺(tái)也不是一無(wú)是處，某些乘法會(huì)通過(guò) lea 將兩條指令合并成一條。

• n * 4 + 5 = lea edx, [ecx * 4 + 5]

printf("%d", n * 4 + 5);
// mov ecx, n
// lea edx, [ecx * 4 + 5]
// push edx

至于值為不可拆分的素?cái)?shù)，就改用 mul 指令。

變量乘變量

這一步?jīng)]有什么優(yōu)化空間，因?yàn)槎际俏粗?，只能老老?shí)實(shí)用 mul 指令。

int fun(int n, int m) {
    return n * m;
}
// mov eax, n
// mov ecx, m
// imul ecx

除法

在看下面內(nèi)容之前，不妨再問(wèn)問(wèn)自己，真的了解除法嗎？除法的本質(zhì)是什么？

ok，現(xiàn)在是復(fù)習(xí)時(shí)間，簡(jiǎn)單總結(jié)一下以下兩個(gè)問(wèn)題。

• 符號(hào)問(wèn)題
  1. 兩個(gè)無(wú)符號(hào)整數(shù)相除，結(jié)果依然是無(wú)符號(hào)
  2. 兩個(gè)有符號(hào)整數(shù)相除，結(jié)果依然是有符號(hào)
  3. 混除，參數(shù)全被當(dāng)成無(wú)符號(hào)計(jì)算，結(jié)果是無(wú)符號(hào)
• 取整問(wèn)題
  1. 向下取整 —— floor 函數(shù) 存在誤差 => ( - a / b ) + ( a / b ) != - ( a / b ) - ( a / b )
  2. 向上取整 —— ceil 函數(shù) 存在誤差 => ( - a / b ) != - ( a / b )
  3. 向零取整 —— 截?cái)喑?Truncate)，可以理解為放棄小數(shù)部分，只取整數(shù)部分，可以在任何情況保持恒等，大部分語(yǔ)言用的都是截?cái)喑?/li>

除數(shù)為無(wú)符號(hào)數(shù)

• 大數(shù)（負(fù)數(shù)）

在無(wú)符號(hào)中，負(fù)數(shù)的值是很大的，例如 -8 = 0xFFFFFFF8。

而除以這種大數(shù)，只能出現(xiàn)兩種情況，1或 0，換個(gè)思路來(lái)想就可以寫(xiě)成這樣：[被除數(shù)] >= [除數(shù)] ? 1 : 0

我們來(lái)看看 thumb 下是怎么優(yōu)化的？

UINT value = (UINT)n / -8;
// cmn.w r0, #9    ; cmp r0, -9
// it hi
// movhi r1, #1    ; n > -9 ? 1 : 0

他這里做了一個(gè)小小的變形：[被除數(shù)] > [除數(shù) - 1] ? 1 : 0，邏輯上仍然成立。

• 2的冪

簡(jiǎn)單的移位

UINT value = (UINT)n / 4;
// lsrs r1, r0, #2

• 非2的冪

接下來(lái)就要引入一個(gè)非常魔幻的設(shè)定，magic number。說(shuō)來(lái)這個(gè)魔數(shù)，依稀記得早在幾年前的知乎上看到過(guò)一篇文章，講的是雷神之錘游戲引擎就使用了這么一個(gè)魔數(shù)，那時(shí)的cpu是非常低效的，而為了避免使用除法這種 cpu 周期偏長(zhǎng)的指令，天才的程序員們想出了各種奇技淫巧，其中最為后人津津樂(lè)道的就是游戲中對(duì)平方根倒數(shù)的優(yōu)化，將計(jì)算過(guò)程等價(jià)替換為加法和移位操作，損失少量的精度來(lái)?yè)Q取絕對(duì)的性能。

我們這里的魔數(shù)稍有不同，它是用來(lái)優(yōu)化除法的，而且邏輯上也相對(duì)容易理解一些，廢話(huà)不多說(shuō)，進(jìn)入正題。

對(duì)于普通除法，我們可以得到以下的換算：（x => 被除數(shù)變量，c => 除數(shù)常量，M => 魔數(shù)）

假設(shè)用 M 代替 2^n / c 這個(gè) Magic 變量，于是有：

也就是說(shuō)，除法將會(huì)被轉(zhuǎn)會(huì)成 (x * M) >> n 的邏輯進(jìn)行運(yùn)算，至于 M 和 n 值怎么來(lái)的，我們不關(guān)心，這是編譯器根據(jù)除數(shù)算出來(lái)的最優(yōu)值，會(huì)盡力保證偏差達(dá)到最小，我們要做的是認(rèn)出魔數(shù)和移了多少位，然后根據(jù) m = 2^n/c 公式求得原本的除數(shù) c = 2^n/m

公式來(lái)源于《C++反匯編與逆向分析技術(shù)揭秘》，真的是非常非常的細(xì)，書(shū)中整個(gè)推導(dǎo)過(guò)程很完整，很建議各位去仔細(xì)研讀一遍

以下代碼為例：

printf("%u", (unsigned)argc / 3);
// mov eax, 0xAAAAAAAB   ; M
// mul [argc]            ; edx:eax = argc * M
// shr edx, 1            ; edx = argc * M >> 32 >> 1
// push edx