面向多面體模型的靜態控制塊識別擴展方法

夏文博 胡偉方 郭浩然

1(鄭州大學信息工程學院 河南 鄭州 450000)2(北京空間信息中繼傳輸技術研究中心 北京 100094)

0 引 言

近年來，隨著以深度學習算法為代表的人工智能技術不斷應用于各個領域，大量計算密集型程序對計算性能的要求逐步增高。為了利用程序中存在的并行性與數據局部性，確保程序快速執行，降低設備功耗，通用CPU提供了多級緩存、多核、SIMD部件，甚至GPU等專用的計算加速器也用于提升程序的執行效率[1]。更加復雜的并行層次及存儲器層次結構給編譯優化帶來了新的挑戰。

計算密集型程序中往往存在著大量的循環，例如在圖像處理程序中，計算核心耗時一般在圖像矩陣的運算，對這些運算進行處理時，需要多層循環來表示運算操作。將循環進行適當的變換，并且映射到不同目標平臺以充分發掘程序中的并行性和數據局部性則需要編譯優化的支持[2]。目前，大多數工業級編譯器雖然支持基本循環變換、向量化、自動并行代碼生成等功能，但是一旦涉及需要多種復雜轉換才能確保優化所需的數據局部性及并行性的情況，常規編譯優化過程是難以分析并進行處理的，這嚴重限制了編譯器對程序性能的優化能力。

多面體模型[3]是一種集成了靜態控制塊分析、依賴分析、循環調度變換于一體的數學表示方法。多面體模型比傳統抽象語法樹(Abstract Syntax Tree，AST)表示更準確地描述了程序靜態信息與動態特性。作為一種數學模型，多面體模型可以更抽象地描述循環嵌套，更加精確地計算語句實例之間的依賴關系。同時，多面體模型表示可以自然地表示多種循環變換方法，例如循環交換、循環傾斜等。利用多種循環變換方法，有利于發掘程序中的向量化機會，生成SIMD[4]代碼，也可以利用循環分塊等變換，幫助生成面向GPU體系結構的SIMT(單指令多線程)代碼[5]。隨著GPU、AI芯片等多種全新體系結構的出現，多面體編譯優化已成為一種越來越流行的技術。

對程序應用多面體優化時，首先需要找到可以被轉換成多面體表示的相關代碼段，稱為靜態控制塊(Static Control Parts，SCoP)，并為它們創建一個多面體模型描述。然而，SCoP的構成必須非常規范，實際程序中往往具有許多限制循環嵌套被識別為SCoP的非規則因素。在通過對SPEC2006[6]測試基準的測試中發現許多測試用例程序中的相關循環代碼段存在諸多限制SCoP識別的問題。例如圖1中的代碼，在進行SCoP檢測的過程中，由于大多數編譯器的別名分析相對保守，編譯器無法證明循環嵌套中所有數組訪問不會造成重疊，會將其識別為存在別名問題，多面體識別算法會判定該循環為非SCoP。

圖1 帶有可能別名的循環結構

為了擴展多面體編譯的實用性，目前已經有一些學者對限制靜態控制塊識別的若干非規則因素進行了研究。Benabderrahmane等[7]利用任意邊界建模循環結構，解決了while循環的多面體建模處理。Strout等[8]研究了稀疏矩陣的多面體編譯優化技術，并基于運行時重排序轉換技術，擴展了非仿射數組下標在多面體模型中的應用。另外也有開發人員選擇使用一些工具來緩解多面體建模不充分的問題，例如：SCoP的解析器Clan[9]，要求開發人員手工標記每個SCoP來手動幫助編譯器識別更多的SCoP，但是這種做法也給程序開發人員帶來了許多額外的負擔，需要進行大量的人工分析來確定SCoP的位置及范圍。

本文首先使用SPEC2006測試集進行多面體建模測試，分析并總結出實際應用程序中阻礙SCoP識別的主要因素。針對多面體建模的多種主要限制因素，基于LLVM編譯框架提出了兩種提升多面體建模能力的解決方案：(1) 針對多面體模型的SCoP識別限制中的復雜循環格式問題，在編譯流程中添加循環規范化遍歷，對待分析的循環進行規范化處理，消除部分不規范因素的影響。(2) 針對造成多面體建模失敗最多的非仿射數組訪問模式與循環邊界的問題，利用LLVM的靜態程序分析信息，提出了一種定值替換的方法來解決該問題。

1 SCoP識別限制分析

為了分析程序中限制SCoP識別的因素，對SPEC2006基準測試中的C語言程序進行了SCoP檢測測試與評估。在LLVM的多面體建模模塊中的SCoP識別功能函數中加入診斷信息輸出語句，統計導致SCoP識別失敗的原因，分析得出的主要原因如下：

(1) 非仿射的數組訪問表達式。在多面體模型中，要求所有的數組訪問表達式或條件表達式都必須是輸入參數或歸納變量的仿射表達式，否則SCoP的識別算法不會將該代碼所在的區域視為SCoP，從而阻礙了多面體模型對其進行優化。舉例如圖2所示。

圖2 非仿射表達式

此外，SCoP中所有循環迭代的上下限也必須是輸入參數或歸納變量的仿射表達式。

(2) 別名。當編譯器對循環的分析結果無法證明兩個內存訪問的基地址是否不相交時，特別是當指針與參數值相關而不是全局變量或堆棧分配的內存空間地址時，編譯器的別名分析就會保守地將其識別為指針別名，導致對該內存訪問所在的程序段的多面體建模失敗。

(3) 函數調用。在多面體模型中，調度變換需要首先分析并嘗試消除程序中存在的依賴關系。然而，在具有外部函數調用或間接函數調用的循環中，依賴關系將變得非常復雜。基于多面體模型的依賴關系分析方法也不能給出程序中精確的數據依賴關系。所以，在SCoP的檢測過程中，往往會排除包含函數調用的相關代碼段。

(4) 非規范化的歸納變量。在多面體模型對循環嵌套的抽象表示中，循環嵌套中某個語句的迭代域會被表示成多維仿射空間中的有界凸多面體，該多面體中每個整數點都代表該語句的一個執行實例。這使得在多面體建模過程中，對循環中的歸納變量具有一定的限制：在循環每次迭代中，迭代變量遞增或遞減幅度要求為1。編譯器在多面體模型建模之前，應盡量將循環中的歸納變量等進行規范化處理。

(5) 復雜的控制流。在多面體模型中，優化需要得到代碼段中的循環的各個信息，如果程序代碼段中出現了比較復雜的終止符(例如：switch、goto等)或者具有復雜形式的控制流(通過while和for或者if結構無法表示)，多面體模型將難以對程序的靜態信息與動態特性進行建模，不能識別為SCoP。

2 基于LLVM靜態分析的識別優化

LLVM[10]是一組用于構建編譯器的工具和庫。它圍繞一種和語言以及平臺無關的中間表示(LLVM-IR)構建，提供了先進的程序分析、優化和目標代碼生成等模塊功能。除了支持x86-32、x86-64和ARM等后端，還有針對大多數GPU加速器甚至硬件描述的目標代碼生成。LLVM支持目前大部分常用的編程語言的靜態和即時編譯。LLVM模塊化的結構、有良好可讀性的IR和一系列有用的工具，便于開發人員進行基于LLVM的編譯模塊開發。基于LLVM的多面體工具的靜態控制塊檢測實現流程如圖3所示。

圖3 SCoP識別流程

2.1 復雜循環格式的優化

LLVM-IR是LLVM編譯器的中間表示語言[11]。將源程序降級到LLVM-IR之后，源程序的復雜性就會顯著降低，并且生成的LLVM-IR沒有高級語言中的循環表示，只有跳轉語句和goto語句。源程序中的數組或仿射表達式也轉換為指針運算和三地址格式的操作。在這種表示中，源程序中的所有必要信息都會通過LLVM提供的內部分析Pass重新計算。所以，在LLVM-IR中，可以使用循環檢測或支配樹信息等簡單分析來驗證待分析程序段是否只包含結構化控制流，也可以使用更復雜的分析來檢查別名或提供關于函數調用副作用的信息。這里本文選擇運行一組LLVM規范化Pass，進一步規范化代碼，解決程序中不規范的循環格式。具體實現如圖4所示。

圖4 不規范循環格式處理流程

LLVM編譯框架具有非常完備的程序變換和規范化Pass集。其中包括基本別名分析、內存到寄存器的提升、庫調用的簡化、指令簡化、尾部調用消除、循環簡化、閉環SSA表單計算和歸納變量規范化。表1中給出了一些限制SCoP識別的非規范因素相應的解決方案，將這些方案加入到規范化Pass中，用以解決多面體的建模的一些限制。

表1 不同限制因素解決方案

2.2 非仿射問題的優化

如圖5所示，多面體模型不支持維數是未知的數組。一種常用的做法是對數組進行降維。使用一維數組并“手動”執行索引算法來實現n維數組。這樣就可以在一維數組上創建仿射下標，使用靜態分析可以推斷出該一維數組是二維數組的映射訪問。但是，目前LLVM編譯器中并沒有相關的轉換實現。另外，這樣的轉換也會導致代碼的復雜度增加，可能會導致靜態分析失敗，對后續的分析造成影響。所以，非仿射表達式的主要問題是：雖然表達式的值是固定不變的，但是其表達式是非仿射的，并將其判定為不滿足多面體模型建模條件。

圖5 非仿射表達式

本文基于LLVM分析Pass得到的循環分析結果，對非仿射的表達式進行結果判斷，通過保持恒定的參數值來消除上述形式的非仿射表達式對多面體建模的影響。具體所用的分析如下：

(1) 靜態單一賦值(SSA)：SSA表示的抽象視圖是一種聲明性語言[12]，通過插入額外的標量變量，使每個定義都是唯一的。標量變量的賦值可以是表達式的結果，也可以是位于目標基本塊中控制流節點的phi節點的結果。例如，圖6中所示的程序代碼通過添加新的變量名和在控制流節點處合并值的phi節點，將其轉換為SSA。

圖6 SSA轉換

循環phi節點定義遞歸表達式：循環phi節點的第一個參數定義初始值，第二個參數使用自引用定義遞歸。例如：

a=loop_1-phi(0,a+1)

b=loop_1-phi(0,2×a)

a在第一次迭代時定義為0，并且對所有其他迭代使用自引用表達式a+1;b在第一次迭代中定義初始值0，接著是對于所有后續迭代引用另一個loop-phi節點2×a的表達式。

循環close-phi節點用來計算loop-phi節點在循環中定義的最后一個值：它們對應于部分遞歸函數的min運算符。例如：

c=loop_1-cloase-phi(b,a>10)

c被定義為當a變為大于10時第一次迭代的b的值：在示例中，c的值可以被靜態地計算為22。

(2) 標量演化分析(SCEV)：從上述SSA表示的抽象開始，通過識別循環phi節點、循環閉合phi節點和派生的標量聲明來分析標量變量演化函數。循環phi節點由初始值和包含自引用的表達式來聲明，當自引用與當前循環中的標量值或不變表達式一起出現在加法表達式中時，SCEV表示具有線性或仿射演化的遞歸函數。循環close-phi節點被聲明為一個由表達式計算的最后一個值，該表達式可能在循環中發生變化，然后SCEV表示一個部分遞歸函數。所有其他標量聲明都可以表示為從其他遞歸和部分遞歸函數的聲明派生的SCEV。SCEV分析將為上述運行示例提供以下表達式：

a={0,+,1}_1

b={0,+,2}_1

c=22

a的SCEV分析其初值為0，每次迭代值線性遞增加1。類似地，b的初值為0，每次迭代遞增加2。由于c的計算是在循環外，它的值并不隨循環的迭代而變化，所以，在這里可以通過SCEV的靜態分析得到表達式c的值為常量22。

(3) 迭代次數的分析：提供一個表示循環執行的次數的SCEV分析。迭代的次數被計算為閉合phi節點(close-phi)的SCEV，或者SCEV的最后一個值，從0開始，在循環的每次迭代中增加1。在運行的示例中，迭代數可以在退出循環時計算為a的值，并可以靜態地計算為11。

通過上述的分析可知，可以通過LLVM編譯器中的循環分析Pass得到程序中循環嵌套的中表達式的靜態分析值，再從中篩選出循環中重復出現的，可被定值為常量的參數值。然后，將其插入到非仿射參數或者表達式中，通過替換定值讓表達式保持恒定，并創建一個新的定值循環版本。最后將調度代碼插入到相應的循環檢查基本塊中，以在運行時確定實際參數值是否存在符合要求的版本。如果不符合，則使用原始版本。這樣可以將一些原本不能看成仿射的，但是循環上下界都是常數值的非仿射表達式表示成為仿射的，從而對更多的循環進行多面體優化。其具體實現如圖7所示。

圖7 定值版本循環生成流程

多面體模型代碼檢測階段，對循環代碼進行分析時，如果發現循環中存在非仿射表達式，調整其判斷策略：將其進行標識為待分析的仿射表達式；再判斷是否存在專用的循環版本，如果存在則識別為SCoP，進行多面體優化，如果不存在，則判定為非SCoP，讓其按照原來的方案進行處理。實現流程如圖8所示。

圖8 基于靜態分析的非仿射表達式處理流程

3 實驗與分析

3.1 測試指標與實驗平臺

在多面體優化過程中，SCoP的識別是優化的基礎。本文進行了如下兩個方面的測試：SCoP識別數目的優化測試和優化后的程序運行加速比測試。

(1) SCoP識別數量測試：測試優化前和優化后，識別出來的符合多面體建模條件的靜態控制塊的平均數目，通過對比得出優化的效果，驗證本文提出的非規范因素消除方法的有效性。

(2) 程序運行加速比測試：首先進行不引入多面體優化的基準測試；之后分別測試初始多面體優化工具和經過本文優化后的多面體優化工具測試結果。通過對比兩次測試相對于基準測試的加速比，來分析SCoP識別數目對多面體優化的影響。

測試平臺采用處理器為Intel(R) Xeon(R) CPU E5- 2682 v4 @ 2.50 GHz，128 GB內存，操作系統為CentOS7；編譯器版本為LLVM- 8.0.0。

3.2 測試內容

為了對比測試優化方案在實際應用中對SCoP檢測能力的優化效果，實驗采用SPEC2006測試集來進行測試。分別在LLVM中的多面體工具和經過本文中設計的優化后的LLVM多面體工具上進行測試，得出識別到的SCoP數目的平均值。

LLVM編譯器可以使用OPT工具來手動實施對LLVM-IR的單獨優化，使用-polly-detect選項來直接測試識別出的SCoP，其中-polly選項代表引入多面體優化。針對優化后的版本，本文添加編譯選項-polly-canonicalize，利用LLVM標準化Pass來規范多面體檢測代碼，非仿射表達式的處理則使用-polly-opt-nonaff選項進行控制。

3.3 實驗結果及分析

3.3.1識別率分析

為了更確切地表示基于LLVM的靜態分析對消除多面體建模中SCoP識別的優化能力，實驗依然采用SPEC2006的C語言測試用例。實驗結果如圖9所示，其中黑色部分表示優化前識別出的SCoP數量，8個測試用例共識別出296個SCoP。白色表示經過本文方法優化后識別出的SCoP數目，8個測試用例共426個SCoP，平均識別數目增加了1.4倍。除mcf的識別出的循環個數沒有發生改變外，其余測試用例符合SCoP條件的循環個數都得到了提高。并且sjeng測試用例靜態控制塊數目提升最為明顯，提升了約4.3倍。實驗結果表明，基于LLVM的靜態分析優化以及規范化方法能夠有效提升SCoP的識別率。

圖9 動態優化前后靜態控制塊數量對比圖

3.3.2加速比分析

本文采用多面體模型編譯測試集PolyBench作為加速比測試的測試用例來測試SCoP識別數目對多面體優化效果的提升效果。PolyBench[13]是一個具有30個數值計算的基準測試套件，包含了線性代數計算、模板計算、圖像處理和數據挖掘的計算內核。在計算加速比時，先使用經過LLVM編譯器最優選項-O3優化后，獲取的程序運行時間作為基準時間，通過使用和不使用本文中的SCoP識別優化方法，分別測試程序運行的時間，通過與基準時間相比較計算出各自的加速比。

測試結果如圖10所示，其中黑色部分表示在沒有進行SCoP識別優化情況下取得的加速比，白色部分表示在對SCoP識別方法進行改進后的情況下所取得的加速比。經過優化后，測試用例中的3 mm運行速度最高相對于優化前提升了2.3倍。大部分情況下，加速比有了相應的提升，說明基于循環格式規范化和定值替換的方法可以避開多面體建模的一些限制，提升SCoP的識別率，發掘更多的多面體優化機會以獲得性能提升。然而，也有一些測試用例出現了加速效果降低的現象，例如：mvt、symm。這種情況的出現，主要是因為新增加的一些循環代碼區域本身存在一些依賴或者其他原因，造成并行化優化失敗。這樣就會出現優化帶來的收益，不能抵消多面體建模或者SCoP識別帶來的時間消耗的情況，從而導致程序運行速度變慢。也有另外一種原因是SCoP識別數目增加后，并行處理這些靜態控制單元，需要更加頻繁地進行線程開啟和同步，造成了線程開銷增加的問題，抵消了程序并行運行帶來的收益。要解決這個問題，需要后續對SCoP的處理算法進行改進。

圖10 多面體優化加速對比

4 結 語

本文針對多面體建模有諸多限制的問題，對阻礙程序代碼中實現多面體模型建立的因素進行了全面分析。對不規則的循環代碼，在規范化處理Pass中整合了解決方案，對進行多面體建模識別的區域進行了規范化處理，解決了復雜的循環結構的簡化和處理。針對限制多面體建模占比最多的非仿射表達式的問題，基于LLVM的靜態分析中的標量演化，進行了預分析優化，將循環中不確定的變量參數，進行了定值化處理，生成了定值版本的循環，從而對非仿射問題進行了擴展。最后經過實驗驗證，本文所做的方法優化，可以有效提升SCoP的識別數量，增強了多面體模型的優化效果。