程式分析與優化 - 6 迴圈優化

本章是系列文章的第六章，介紹了迴圈的分析方法。迴圈優化的邏輯相對簡單，但對性能提升的效果卻非常明顯。迴圈優化的分析還產生了一個圖靈獎。

本文中的所有內容來自學習DCC888的學習筆記或者自己理解的整理，如需轉載請註明出處。周榮華@燧原科技

6.1 迴圈的重要性

• 90/10定律，90%的算力消耗在10%的代碼上，這些代碼絕大多數都是各種迴圈
• 迴圈的優化對獲得更高的性能非常重要
• 基於迴圈的迭代空間轉換的優化（本章不涉及）
• 維持迴圈的迭代空間不變進行的優化（本章重點）：
  • 代碼提升（code hoisting）
  • 強度削減（strength reduction）
  • 迴圈展開（loop unrolling）
  • 等等

6.2 分解控制流圖

對於下麵的C代碼，分析一下有幾重迴圈？怎麼從控制流圖中定義迴圈？

 1 #include <stdio.h>
 2 int main(int argc, char **argv) {
 3   int sum = 0;
 4   int i = 1;
 5   while (i < argc) {
 6     char *c = argv[i++];
 7     while (*c != '\0') {
 8       c++;
 9       sum++;
10     }
11   }
12   printf("sum = %d\n", sum);
13 }

控制流圖的生成方法就不多說了，忘記的同學可以回過頭去看看第二章（2.1.3 LLVM），生成的svg圖如下：

控制流圖中的自然迴圈是具有下列屬性的節點的集合S：

• 存在一個頭結點h
• S中的任意一個元素都存在路徑到頭結點h
• S外不存在任何節點有邊指向S中除h意外的其他節點

編譯器中說的迴圈（loop）和拓撲意義上的環（cycle）是不同的。編譯器領域中的環只能有一個入口，多個入口的環在編譯器領域不叫做迴圈，因為絕大多數對迴圈的優化在多入口的環中都不適用。

多個入口的環在編碼過程中也非常罕見，所以也不是編譯器需要關心的場景。

6.2.1 控制流圖的簡化過程

如果對於邊(n₁, n₂)，n₁是n₂的唯一前驅，或者n₁和n₂是強連通圖的一部分，可以用下麵的方法簡化：

• 刪除邊(n₁, n₂)
• 新建節點n₁₂
• 將所有n₁的前驅改成n₁₂的前驅
• 將所有n₂的後繼改成n₁₂的後繼
• 刪除節點n₁和n₂

重覆上述操作，直到控制流圖保持不變。

例如下麵的控制流圖：

簡化流程是這樣的：

為什麼要簡化控制流圖：

• 入口單一，可以在優化過程中在頭結點處增加 冗餘代碼
• 簡化後的圖數據流分析速度更快
• 常規的迴圈語法，例如for，while，repeat，continue和break都會產生可簡化的控制流圖
• goto會產生不可簡化的流圖

6.3 自然迴圈

6.3.1 支配節點（Dominators）

節點d是節點n的支配節點，當且僅當所有從控制流圖入口到n的所有路徑都經過d。

D[s₀] = {s₀} D[n] = {n} ∪ (∩ _{p∈ pred[n]}D[p]), for n ≠ s₀
支配節點的計算：

6.3.2 直接支配節點（Immediate Dominators）

每個階段n都 只有唯一一個直接支配節點idom(n)，定義如下：

• idom(n) 不是n
• idom(n)是n的支配節點
• idom(n)不是n的其他支配節點的支配節點

6.3.3 支配節點樹（Dominator Tree）

把每個節點的直接支配節點畫一條邊到該節點，就形成了圖的支配節點樹：

嵌套迴圈中優先優化記憶體迴圈。

迴圈的頭節點h：在迴圈的節點集中，存在一個節點n，h是它的支配節點，並且存在邊(n, h)。

如果兩個迴圈的頭結點存在支配關係，則被支配的頭節點所在的迴圈稱為內迴圈，支配的頭節點所在的迴圈稱為外迴圈。

6.4 安全的不變代碼提升（SAFE INVARIANT CODE HOISTING）

6.4.1 迴圈不變性

如果某個計算在迴圈的每次迭代中都產生同樣的值，則該計算時迴圈不變的。

迴圈不變表達式的通常優化方法是將該表達式提升到迴圈外。

滿足下麵任意一條要求的表達式是迴圈不變表達式：

• 表達式的參數是常量
• 表達式的參數定義在迴圈外
• 表達式的參數是迴圈不變表達式，並且在該表達式之前沒有其他定義

將迴圈不變表達式提升到迴圈外的做法稱為代碼提升。

6.4.2 安全的不變代碼提升

在程式點d，如果滿足下麵3個條件，可以對錶達式t = a + b 安全的進行代碼提升：

• d是所有t生效區域內節點的支配節點
• t在迴圈內只有一個定義
• t在迴圈的頭結點外沒有使用

6.4.3 迴圈倒置（Loop Inversion）

將常規的while迴圈轉換成repeat-util迴圈的做法稱為迴圈倒置。倒置後的迴圈可以安全的進行不變代碼提升。

repeat-utill迴圈在迴圈過程中每次迭代只需要進行一次跳轉，所以性能也比常規的while迴圈要好。

6.5 因變數（INDUCTION VARIABLES）

6.5.1 基本概念

基本因變數（Basic induction variable）：如果一個變數i在迴圈內部僅定義一次，並且每次定義都是在原有值基礎上增加或者減少迴圈不變數的值。

派生因變數（Derived induction variables）：如果一個變數k在迴圈內部僅定義一次，並且k是一個因變數與迴圈不變數的乘積或者和。

i系列的派生因變數（a derived induction variable in the family of i）：如果一個變數k定義中使用的因變數j僅定義一次，並且定義在迴圈內部，在j和k之間沒有i的定義。

6.5.2 強度削減

將乘法運算換算成加法運算。例如下麵的優化：

強度削減的演算法基本上就是將派生因變數轉換成基本因變數。演算法過程一般如下：

• 對所有j = i * c, 假定變數i每個迭代增加b，i 初始化為a，那j每個迭代就要增加 b*c。
• 在迴圈外新增一個變數j'為第一次迭代時的j的值， j' = a*c
• 在迴圈外新增一個變數k，用來保存每個迭代j需要增加的值b*c
• 這樣迴圈內部就可以優化成
• j = j'
• j' += k

6.5.3 無用代碼刪除（Dead Code Elimination）

首先刪除的是j'，因為k'已經完成了類似的功能：

由於i除了定義就只有和迴圈不變數的比較，所以實際上i也是可以刪除的：

刪除冗餘拷貝：

迴圈倒置：

初始版本和最終優化版本的對比：

6.5.4 迴圈展開

迴圈展開是通過減少迴圈次數並增加迴圈內部的計算來優化的一種方式。例如對下麵的代碼：

以2為因數進行迴圈展開之後的結果是這樣的：

6.5.5 指針分析簡史

• Lowry, E. S. and Medlock, C. W. "Object Code Optimization". CACM 12(1), 13-22 (1969) 引入因變數優化和支配節點的概念
• Allen, F. E. "Control Flow Analysis". SIGPLAN Notices 23(7) 308-317 (1970)引入控制流圖的化簡，並因此獲得圖靈獎