基于LLVM的RISC-V向量擴展棧幀布局優化①

陸旭凡, 胡海根, 邢明杰

1(中國科學院 軟件研究所, 北京 100190)

2(浙江工業大學 計算機科學與技術學院, 杭州 310012)

1 引言

LLVM[1,2]是一種開源的編譯基礎設施, 采用模塊化的方式進行設計, 具有清晰的架構層次和詳細的文檔資料, 并且提供了豐富的工具集, 因此基于LLVM來開發支持特定體系結構的編譯器, 可以縮短開發時間, 并生成高效的代碼.

RISC-V[3]是一種新興的開源RISC指令集架構.它的標準由非營利性的RISC-V基金會維護.由于具有開放、標準的擴展方式, 使得幾乎所有的計算機系統,從小型的微控制器到超級計算機都可以使用它.例如,為了滿足高性能計算、機器學習、密碼學領域的計算需求而提出的向量擴展.RISC-V向量擴展[4,5]具有可伸縮性, 向量寄存器的長度由具體的硬件實現來定義,可以在運行時動態設置向量寄存器組, 以及要處理的向量長度.這些特性對編譯器的實現提出了許多挑戰.其中之一就是程序的棧幀布局.

本文介紹了LLVM原有的棧幀布局方式, 并對該棧幀布局的缺點進行了分析, 隨后提出了新的優化方案, 并基于巴塞羅那超算中心開發的測試集進行驗證.通過對比分析優化前后生成的機器指令, 可以看到優化后的棧幀布局能夠有效減少訪存指令數量以及棧空間大小.除此之外, 新方案還可以減少預留寄存器的數量, 有助于緩解寄存器壓力.

2 RISC-V向量擴展對棧幀布局的挑戰

2.1 RISC-V向量擴展寄存器

RISC-V向量擴展架構具有32個向量數據寄存器,分別為V0-V31.向量寄存器的位長VLEN由具體的硬件實現來定義.多個連續的向量寄存器可以組合一起使用, 從而能夠處理更長的數據.控制狀態寄存器vlenb用來保存向量寄存器的字節長度(等于VLEN/8),控制狀態寄存器vtype用來保存向量寄存器的元素寬度SEW, 向量寄存器組乘數LMUL等信息.LMUL的值可以為1、2、4、8.圖1展示了不同的LMUL值所對應的向量寄存器組織結構.

圖1 不同LMUL下的向量寄存器組織結構

用戶可以通過指令csrr來讀取控制狀態寄存器vlenb中的內容, 從而獲得向量寄存器的長度信息; 可以通過指令vsetvli或者vsetvl在運行時動態設置LMUL的值, 從而使用不同大小的向量寄存器組.

2.2 長度未知的向量類型

由此可見, 對于應用程序中實際處理的向量對象,以及編譯器中的虛擬向量寄存器, 其長度有兩個因素來決定: 一個是具體處理器實現時所定義的單個向量寄存器長度VLEN, 該值必須大于或等于128, 并且為2的冪次方; 另一個是向量寄存器組中的寄存器個數, 即LMUL值.為了簡化編譯器實現, 方便用戶編程,向量擴展intrinsic編程接口針對不同的元素類型和LMUL值分別提供了相應的向量數據類型.例如元素類型為int8,LMUL分別為1、2、4、8的向量類型:vint8m1_t、vint8m2_t、vint8m4_t、vint8m8_t.這些類型的LMUL值在編譯時是已知的.但是由于VLEN的值在編譯時期無法靜態獲得, 因此向量對象的實際大小在編譯時期也是未知的.LLVM編譯器在內部實現中定義了一種可伸縮向量類型, 用來表示這種長度未知的向量.

2.3 可伸縮向量對棧幀布局造成的困難

對于不使用向量類型變量的函數, 編譯器一般可以通過計算每一個棧對象的大小來確定它相對于棧幀尋址指針的偏移量, 以及函數使用的棧空間大小, 從而完成棧幀布局并且在編譯時期確定棧對象的地址.而對于使用向量類型變量的函數, 由于向量類型的大小在編譯時期未知, 因此無法在編譯時期確定棧對象與棧幀尋址指針的偏移量.這就導致靜態分配棧對象, 編譯時期確定棧對象地址的方式無法適用.

3 LLVM原有向量擴展棧幀布局

圖2展示了LLVM原有的RISC-V向量擴展棧幀布局.圖中有3種類型的指針[6], 分別用于指向棧幀中的不同位置, 幀指針指向棧幀的頂部, 棧指針指向棧幀的底部, 而基指針只在函數有可變大小的變量(例如變長數組)并且需要棧地址對齊的情況下存在, 指向棧幀中最后一個固定大小的對象.

圖2 LLVM原有的向量擴展棧幀布局

在這種布局方式下, 對于每一個向量類型對象, 在棧幀中會首先分配一個對象, 用于存儲棧中向量類型對象的地址.由于是用來存儲地址, 因此它的大小是固定的.接著通過控制狀態寄存器讀寫指令獲取vlenb的值, 在棧上動態分配VLEN×LMUL大小的空間.最后將向量對象的地址存儲到之前分配的固定大小對象中.

如果要讀取或者寫入一個棧向量對象, 編譯器首先要獲得向量對象的地址.在這種棧幀布局下, 由于在分配過程中已經對每一個向量對象的地址進行保存,因此要獲得向量對象的地址, 可以直接通過load指令將固定大小對象中的內容讀取到通用寄存器中.然后,就可以通過寄存器間接尋址方式對棧向量對象進行訪問.

3.1 存在的問題

3.1.1 需要較多的訪存指令

原有棧幀布局下, 在訪問棧向量對象時需要先讀取該向量對象的地址, 因此需要大量的load/store指令來完成對棧向量對象的分配與讀寫.在現代計算機存儲體系結構下, 內存讀寫操作通常要比算術運算操作花費更多的時鐘周期[7], 且能耗更高[8], 因此較多的訪存指令將會導致程序性能下降.

3.1.2 需要較大的棧空間

原有棧幀布局下, 在分配每一個棧向量對象時, 需要額外分配一個保存其地址的空間, 在RV64架構下,保存地址的空間大小是8個字節.因此每分配一個棧向量對象, 都需要多分配8個字節, 且可能由于對齊的要求, 每個棧向量對象會分攤到更多的字節.

3.1.3 需要較多的預留寄存器

在LLVM代碼生成階段, 如果是在寄存器分配過程之后創建新的虛擬寄存器, 則需要在棧幀的溢出變量區域中首先分配一個緊急溢出槽.在之后的寄存器清掃過程中, 如果該虛擬寄存器的活躍區間內有可用的物理寄存器, 則使用該物理寄存器來替換, 如果沒有可用的物理寄存器, 則需要溢出一個活躍的物理寄存器到緊急溢出槽.在對緊急溢出槽進行尋址時, 如果再引入新的虛擬寄存器, 則會陷入遞歸而導致編譯器崩潰.因此, 用于尋址的指針(棧指針、幀指針或基指針)與棧幀中對象之間不能存在編譯時期大小未知的區域.

原有棧幀布局下, 由于棧指針與分配固定大小對象(包括局部變量和向量地址)區域之間存在編譯時期大小未知的可伸縮向量, 因此棧指針不能用于棧幀對象尋址.在不需要棧地址對齊的時候, 可以用幀指針來尋址.在需要對齊的時候, LLVM會使用基指針來指向最后一個固定大小的對象, 通過基指針來尋址.因此,原有棧幀布局最少需要預留2個寄存器來保存棧指針和幀指針, 最多要預留3個寄存器來保存棧指針、幀指針和基指針.盡管RISC-V有32個通用寄存器, 但對于寄存器壓力較大的情況, 例如編譯器內聯優化時引入大量函數體代碼的時候, 預留過多的寄存器容易導致寄存器溢出, 從而影響程序性能.

4 新的棧幀布局方案

為了減少讀寫棧向量對象使用的訪存指令數, 并且減小函數使用的棧空間大小, 就需要摒棄保存每一個棧向量對象地址的棧幀布局方式.由于RISC-V向量擴展架構支持在運行時獲得向量寄存器的長度信息, 因此可以通過編譯時插入算術指令來動態計算棧向量對象的地址.按照這個思路, 我們提出了新的棧幀布局方案.

同時, 為了減少預留寄存器的個數, 新方案會根據是否存在可變大小局部變量, 是否需要棧地址對齊, 這些不同的場景對棧幀布局進行調整.表1展示了不同場景下棧對象的尋址方式, 以及兩種方案所需要預留的寄存器情況.可以看到, 在沒有可變大小局部變量的情況下, 新方案能夠使用棧指針來尋址, 需要預留的寄存器數量要比原有方案少.

表1 不同場景下的棧對象尋址方式及需要保存的指針

4.1 不存在可變大小局部變量且不需要棧地址對齊

圖3展示了不存在可變大小局部變量且不需要棧地址對齊時的棧幀布局.棧向量對象區域位于被調用者保存寄存器區域與局部變量及溢出變量區域之間.在這種場景下, 可以使用棧指針來尋址.在棧幀布局的時候, 通過計算棧向量類型對象的個數和LMUL值, 以及讀取控制狀態寄存器vlenb的值, 可以在運行時動態計算出棧向量對象區域的長度大小值.

圖3 不存在可變大小局部變量且不需要棧地址對齊時的棧幀布局

LLVM內部使用二維抽象數據類型來表示棧對象相對于尋址指針的偏移量.其中第一個維度表示固定大小的偏移量, 第二個維度表示可伸縮大小的偏移量.在RISC-V向量擴展中, 可伸縮偏移量表示的實際值是該偏移量值與控制狀態寄存器vlenb的值的乘積.因此, 在計算棧向量對象地址時, 其固定偏移量為局部變量及溢出變量區域的大小, 可伸縮偏移量則取決于該對象在棧向量對象區域中的位置.

4.2 不存在可變大小局部變量且需要棧地址對齊

圖4展示了不存在可變大小局部變量且需要棧地址對齊時的棧幀布局.由于需要棧地址對齊, 在被調用者保存寄存器區域和棧向量對象區域之間多出一塊編譯時未知的對齊區域, 因此, 需要預留寄存器來保存幀指針, 以便利用幀指針在函數退出時恢復棧幀.在這種場景下, 可以使用棧指針來尋址.棧向量對象相對于棧指針的固定偏移量為局部變量和溢出變量區域的大小,可伸縮偏移量取決于棧向量對象在棧向量對象區域中的位置.

圖4 不存在可變大小局部變量且需要棧地址對齊時的棧幀布局

4.3 存在可變大小局部變量且不需要棧地址對齊

圖5展示了存在可變大小局部變量且不需要棧地址對齊時的棧幀布局.與之前不同的地方是, 我們調換了局部變量及溢出變量區域和棧向量對象區域的分配順序, 將編譯時大小未知區域連在一起, 從而可以避免引入基指針.在這種場景下, 可以使用幀指針來尋址.棧向量對象的固定偏移量為局部變量及溢出變量區域與被調用者保存寄存器區域的大小之和, 可伸縮偏移量則取決于該對象在棧向量對象區域中的位置.

圖5 存在可變大小局部變量且不需要棧地址對齊時的棧幀布局

4.4 存在可變大小局部變量且需要棧地址對齊

圖6展示了存在可變大小局部變量且需要棧地址對齊時的棧幀布局.在這種場景下, 由于局部變量與棧指針和幀指針之間都存在編譯時大小未知區域, 為了避免在尋址緊急溢出槽時遞歸地引入虛擬寄存器而導致編譯器崩潰, 需要使用基指針來尋址.此時棧向量對象相對于基指針的固定偏移量為局部變量及溢出變量區域的大小, 可伸縮偏移量則取決于該棧向量對象在分配棧向量對象區域中的位置.

圖6 存在可變大小局部變量且需要棧地址對齊時的棧幀布局

4.5 通過指令動態計算棧向量對象地址

將LLVM中表示偏移量的抽象二維數據類型轉化到實際的偏移量時, 需要通過多條指令來實現.圖7展示了計算固定偏移量為32, 可伸縮偏移量為8時生成的3條指令.首先通過csrr指令讀取控制狀態寄存器vlenb的值, 隨后通過slli指令得到該值與可伸縮偏移量8的乘積, 最后通過addi指令與固定偏移量相加得到該棧向量對象相對于棧指針的實際偏移量.

圖7 計算二維數據(32, 8)時的指令

5 測試驗證

我們對新方案基于LLVM 11.0版本進行了代碼實現, 并測試通過了LLVM自帶的回歸測試集.

由于RISC-V向量擴展指令集標準尚處于草案階段, 目前還沒有適于做性能測試的硬件平臺.為了評估新方案對生成代碼的優化效果, 我們使用了巴塞羅那超算中心為RISC-V向量擴展所開發的測試集[9,10], 該測試集主要測試的內容是向量的數學計算(例如向量按元素乘加, 向量按元素取余弦值), 可以充分利用向量指令及寄存器.我們對該測試集分別在-O0優化級別(即不做優化)和-O2優化級別下編譯測試文件, 然后對生成代碼的訪存指令數量和棧空間大小進行靜態統計.

圖8展示了新方案下訪存指令數量相對于原有方案下的百分比.在-O0優化級別下, 所有測試文件的訪存指令數量均有減少, 其中使用向量類型變量較多的測試文件CumNormalInv.cpp, 優化后的訪存指令數量僅占原有方案下的39.5%.在-O2優化級別下, 由于測試文件axpy.c使用的向量類型變量較少, 經過優化后都已全部放在向量寄存器中, 因此訪存指令數沒有變化.其他測試文件的訪存指令數量均有減少, 其中測試文件CumNormalInv.cpp在優化后的訪存指令數量僅占原有方案下的1.6%.圖9展示了新方案下棧空間大小相對于原有方案下的百分比.在-O0優化級別下, 對于所有的測試文件, 相比原有方案, 優化方案下棧空間的使用量均有所減少, 其中使用向量類型變量較多的文件CumNormalInv.cpp, 優化后棧空間使用量為原有方案下的49.2%.在-O2優化級別下, 除了axpy.c測試文件在棧上沒有分配向量對象, 其他文件相比原有方案, 優化方案下棧空間的使用量均有減少, 其中測試文件CumNormalInv.cpp的棧空間使用量僅占原有方案下的13.3%.

圖8 訪存指令數對比

圖9 棧空間大小對比

圖10展示了新方案下總指令數量相對于原有方案下的百分比.在-O0優化級別下, 對于所有測試文件,新方案的總指令數量均有增加, 其中測試文件axpy.c新增指令最多, 占原有方案下的112.5%.在-O2優化級別下, 測試文件CumNormalInv.cpp新增指令最多, 占原有方案下的129.8%.測試文件Particlefilter.c的總指令數量反而會下降, 占原有方案下的90.0%.這是由于原有方案下函數使用的棧空間比較大, 導致尋址偏移量超過了12 bit的范圍, 需要生成額外的指令來處理,而優化后減小了棧空間, 因此不需要再生成這部分指令.

圖10 總指令數對比

表2展示了優化方案和原有方案下的預留寄存器數量對比, 由于-O0優化級別下, 編譯器不開啟與寄存器使用相關的幀指針消除優化, 因此表2僅統計了-O2優化級別下每個測試文件累計預留寄存器的數量.可以看到, 優化方案在-O2優化級別下能夠減少預留寄存器的數量.

表2 累計預留寄存器數量對比

總的來說, 優化后的棧幀布局由于采用動態計算棧向量對象地址的方式, 所以能夠減少保存和讀取地址時的load/store指令, 由于不需要分配棧對象來保存棧向量對象地址, 所以能夠減少棧空間的使用.除此之外, 由于通過區分不同場景來確保緊急溢出槽始終緊鄰用于尋址的指針, 所以相比原有棧幀布局方案, 能夠減少預留寄存器的數量.但是, 采用動態計算棧向量對象地址的方式會插入多條指令, 帶來額外的運行時計算開銷.因此, 新方案最終優化效果如何, 還需要在實際的硬件平臺上通過運行測試來評測.

6 結語

本文介紹了原有LLVM中RISC-V向量擴展的棧幀布局, 并針對原有棧幀布局中存在的問題, 提出了優化方案.通過巴塞羅那超算中心開發的測試集, 驗證了優化方案的正確性, 并通過靜態統計訪存指令數量以及棧空間大小, 證明了優化方案在不同優化級別下能有效減少訪存指令數量以及棧空間的使用量.目前,優化后的棧幀布局代碼實現已經提交到LLVM官方倉庫[11].