程式分析與優化 – 6 循環優化

• 2022 年 6 月 12 日
• 筆記
• 人工智慧, 技術, 編譯器

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

本文中的所有內容來自學習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)引入控制流圖的化簡，並因此獲得圖靈獎