基于鏈接器的RISC-V字加載指令優化①

烏鑫龍, 廖春玉

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

2(北京師范大學珠海分校 計算機學院, 珠海 519087)

1 引言

由于RISC-V指令集架構具有開源、芯片設計友好、開發成本低等特點[1,2], 近年來被越來越多地運用于嵌入式設備中. 同時RISC-V指令集作為RISC的一員, 也會不可避免的存在一些精簡指令集的弊端,RISC二進制程序體積偏大的問題就是其中之一. 因為RISC指令集只要求實現計算機硬件中最常用且數量有限的基礎指令, 所以其中較復雜的操作只能通過基礎指令的組合來實現. 因此在完成相同操作的情況下,相較于直接包含復雜操作指令的CISC來說, RISC程序往往需要執行更多條指令. 尤其是在內存大小受限的嵌入式設備中[3], 二進制程序體積偏大的問題更加突出[1].

本文第2節簡要介紹了相關減小程序體積的部分方法以及研究, 并且簡要介紹Zce子擴展對于指令優化的效果. 第3節介紹RISC-V架構以Zce子擴展的優化思路. 第4節詳細解釋了LSGP指令優化程序體積的方法. 最后基于LLD鏈接器實現了LSGP指令的優化并對優化效率進行分析.

2 相關研究

針對RISC程序體積偏大的問題, 目前主流方法之一就是在基礎指令集以外額外支持一個“短指令集”.該指令集用更短的指令寬度編碼基礎指令集中最常用的指令從而二進制程序體積. 在ARM架構中就使用Thumb指令集縮減程序體積, MIPS架構則有MISP16指令集承擔縮小程序體積的任務[3]. 得益于RISC-V指令集可擴展性高的特點, RISC-V當前也有C指令集子擴展被用于同樣的目的.

除此之外, Halambi等人[3]還通過對MIPS指令建模, 使用啟發式的方法來估算因為寄存器數量有限導致被分配的堆棧, 計算分析從而更細粒度地選擇壓縮指令. 在MISP 16壓縮指令集的基礎上更進一步的壓縮了MIPS二進制程序的體積.

在嵌入式領域的基準測試中, RISC-V架構的二進制體積相較ARM架構增大了約11%, 即使在使用了C子擴展的情況下仍有較大差距[4]. 本文研究的RISC-V的Zce子擴展[4]與C子擴展同樣被用來解決二進制程序體積偏大的問題. 但與C子擴展不相同的是, 該擴展除了通過縮減常用指令的長度以外, 還嘗試替換頻繁使用的固定指令組合從而縮減程序體積, 進一步增加了代碼密度. 具體而言, 在C子擴展的基礎上, Zce子擴展使得二進制體積比ARM架構小約1.75%. 本文對于Zce擴展中以LWGP為代表的指令進行研究, 基于LLD鏈接器實現該優化并且評估其優化效率.

3 RISC-V指令集擴展

RISC-V指令集由基礎指令集和眾多擴展指令集組成. 其中基礎指令集包含了如整數加減和位運算以及分支跳轉指令等, 如表1所示. 這些指令足以支撐一個簡單的裸機程序或者操作系統的運行.

表1 基礎指令集中常用的主要指令

除此之外, 基礎指令集還為RISC-V指令集定義了x0-x31共32個通用寄存器. 每個寄存器都有其對應的用途. 如表2所示.

表2 通用寄存器使用規范

表2中, gp和tp寄存器則較為特殊, 它在程序執行的過程中被當作常量值使用.

3.1 Zce指令集擴展

與基礎指令集不同, Zce擴展更多的是針對當前已有指令的壓縮和優化問題. 它通過減少指令中某些情況下冗余操作數或者替換常用的固定指令組合來縮減單個指令的長度和指令條數.

以基礎指令集中邏輯運算指令為例, 邏輯運算中只有與, 或和異或, 非運算則通過將源寄存器異或-1實現. 圖1是XORI的指令格式

圖1 XORI 指令格式

XORI指令將rs1寄存器中的數和立即數imm按位異或運算, 結果寫入rd寄存器. 在非運算過程中較頻繁的會出現rs1和rd使用同一個寄存器的情況, 因此Zce擴展嘗試將這種情況下rs1和rd寄存器合并以節約編碼點. Zce中將非運算(c.not)定義為如圖2格式.

圖2 c.not指令格式

c.not 指令合并rs1和rd寄存器為rsd, 同時因為約定立即數為-1所以刪除了立即數. 將基礎指令集實現的32位非運算指令XORI rd, rs1, -1縮減為16位的c.not指令.

Zce擴展中還有一部分指令用于壓縮固定的指令組合. 例如push/pop指令. 在RISC-V匯編中, 函數的開始和末尾都需要保存和恢復堆棧指針和參數或返回值. Zce以使用push/pop指令一次性代替多條SW/LW指令的方式縮減指令條數.

LSGP指令縮減程序體積的方式也與之類似,LSGP指令仍為32 bit指令, 它通過提高硬件的復雜度,將兩條指令合并為一條指令從而減小程序二進制體積.Zce中使用GP寄存器進行優化的指令共4條, 分別是LWGP、SWGP、LDGP、SDGP (下用LSGP指代全部4條指令). 其與基礎指令集的Load/Store指令對應.其中, LDGP和SDGP僅被用于RISC-V 64位機器中加載雙字長的數據.

4 LWGP指令優化原理

4.1 LW指令介紹

前面提到的RISC-V基礎指令中還定義了字加載/存儲指令, 分別是LW、SW、LD、SD (下多以LW指令為例), 它們被用來從給定地址加載字節數據. 其指令格式如圖3所示. LW指令使用rs1的值為基地址,將rs1+offset處4個字節的數據加載到rd寄存器中.這就意味著在程序執行LW指令之前仍需使用額外指令將基地址加載到rs1寄存器中. 適用于這種情況的有兩條指令, 分別是ADDI和LUI. 本文主要研究使用LUI指令加載基地址的情況.

圖3 Load/Store指令格式

代碼示例 1. LW指令的使用lui a0, 512 lw a1, 256(a0)

在代碼示例1中, 兩條指令一起被用來加載位于0x200100的數據. 由LUI現將該數據的高二十位地址加載進a0寄存器, 再由LW指令將位于此處的數據加載到a1中.

為了對這種情況進行優化, RISC-V引入了一個全局指針寄存器GP. 這個寄存器的值在鏈接過程中被確定并且在程序執行過程中保持不變. GP寄存器主要被用來優化程序中全局變量的訪問, 所以在一般情況下,鏈接器會將GP指針指向ELF文件中.sdata小數據段+0X800的位置. 當某一個全局變量可以被以GP為基地址訪問時. 鏈接器就會刪除LW指令之前的LUI指令以縮減代碼體積. 示意如圖4.

圖4 GP指針位置示意

但是由于LW指令中的偏移量的長度僅有12 bit,因此僅能訪問到GP±2 KB范圍內的全局變量. 對于超出該范圍的全局變量, 就仍需要LUI指令通過其他寄存器傳遞基地址.

4.2 通過LWGP提高LW指令的訪存能力

LW指令的主要問題是偏移量位寬不足以當前情況. 它只能訪問基地址±2 KB范圍內的變量. 所以需要較為頻繁的使用LUI指令以重新加載新的基地址. 而LWGP正是通過增加長偏移量的位寬提高了其訪存能力. LWGP指令格式如圖5.

圖5 LWGP指令格式

LWGP指令事先約定了使用GP寄存器作為基址寄存器, 如此可以將LW中基地址寄存器rs1對應的編碼點分享給偏移量offset使用. 這樣就可以使得偏移量的寬度從LW的12 bit擴展到了LWGP的16 bit, 從而使LWGP指令可以訪問GP±32 KB范圍內的全局變量. 基于同樣的原理, LDGP和SDGP的訪存能力更是擴大到了GP±64 KB的范圍.

5 基于LLD的LSGP指令優化

正如上文所提到的, GP指針被用來優化全局變量的訪問. 然而在程序鏈接之前, 全局變量的地址還尚未被確定. 因此當前生成的一些匯編指令需要使用標志符預先占位, 如 %hi (symbol) 代表符號symbol的高20位地址, 這些標志并不能被直接編碼到二進制指令中, 所以編譯器會使用重定位類型(如R_RISCV_LO12_I)標記這條指令, 表示這條指令還需要鏈接器做后續處理. 而具體的相應數據會在鏈接過程中被寫入.

5.1 鏈接器松弛

在鏈接器松弛過程中, 鏈接器會從整個可執行程序的視角對于代碼進行優化. 鏈接器會讀取并解析文件中所有的重定位信息, 針對每一條重定位信息進行相應的優化處理, 鏈接器松弛的簡要流程如圖6所示.每條重定位信息的優化方式取決于該條信息的重定位類型, 不同的重定位類型對應著不同的函數方法. 本文的優化主要設涉及3種重定位類型, 分別是R_RISCV_HI20、R_RISCV_LO12_I和R_RISCV_LO12_S.

圖6 鏈接器松弛簡要流程

當LUI指令被用來加載一個全局變量的高20位地址時, 編譯器會將該指令用R_RISCV_HI20標記. 同時, 該指令通常會和使用全局變量低12位的LW指令一起使用. 以本文研究涉及到的LW和LUI的指令為例, 編譯器會給LW指令標記重定位類型R_RISCV_LO12_I.

在鏈接器的松弛階段中, 鏈接器會不斷重復掃描并嘗試優化程序中每一條重定位信息, 直到全部的重定位信息都不能夠再次被優化. 其中被用來加載全局變量的LUI和LW兩條指令會被嘗試優化成以GP寄存器為基地址寄存器的LW指令. 基于同樣的邏輯, 本文主要討論的LSGP也需要做相似的處理.

代碼示例 2. LW指令使用的重定位類型lui a0, %hi (symbol) # R_RISCV_HI20 (symbol)lw a0, %lo (symbol) (a0) # R_RISCV_LO12_I (symbol)

由于LSGP指令格式與其他指令都不相同, 因此并不能被目前已經存在的重定位標記正確處理. 于是在這一階段我們定義了新的重定位類型來指定LSGP指令的優化操作. 同時, 鏈接器中所有被用到的重定位類型都需要由psABI來定義. 但是由于Zce擴展仍處在實驗階段, psABI中沒有定義相關的重定位類型, 因此出于實驗測試目的, 作者針對LSGP臨時定義了重定位標記用于指令的優化.

鏈接器松弛結束后, 每一條被重定位類型標記的指令會被按照這個重定位類型的要求計算地址, 并且填充到對應占位標志的地方.

5.2 鏈接器上LSGP優化的實現

本節中使用LLD鏈接器為例子進行討論. 由于LLD主線針對于RISC-V鏈接器松弛的實現尚不完善,因此我們使用了一個上游正在review的補丁來完善相關功能. 在此基礎上進行LSGP等指令的生成、優化以及評估工作. 同時, 為了能夠單獨評估LSGP的優化效率, 我們定義了一個-mzce-lsgp開關, 用來更直觀地評估LSGP四條指令的優化效率.

編譯器會為LUI和LW指令分別標記重定位類型R_RISCV_HI20和R_RISCV_LO12_I. 在初始階段,鏈接器就會統一提取所有的重定位信息. 因此我們通過遍歷重定位標記就可以找到需要被優化的指令. 但值得注意的是, LUI指令并不僅會和LW被一起使用.也會和例如ADDI等其他指令一同被用來加載絕對地址. 因此我們在判斷LUI指令是否可以被優化的時候還需要提前讀取并判斷下一條指令是否屬于字加載指令.

在此之后還需針對R_RISCV_LO12_*進行優化.為了避免造成額外的影響, 首先需要判斷當前指令是否為LW/SW/LD/SD的其中之一, 之后計算當前指令使用的全局變量是否位于LSGP指令要求的地址范圍內. 過程中要注意保存rd寄存器的值來確保優化前后的功能不會改變. 整體實現邏輯偽代碼如示例代碼3所示. 鏈接器在將LW修改成LWGP的過程中并不會對偏移量offset參數進行賦值, 它的值將會在鏈接器優化階段結束后被統一調整.

代碼示例 3. 優化LUI和LSGP指令1. for each rel in relocations 2. if rel.type is R_RISCV_HI20 and rel.inst is LUI 3. if rel.nextInst is one of (LW ro LD or SW or SD)4. if rel.inst.offset is in range of Uint16 and aligned by 4 b 5. Call removeInst(rel)6. else if rel.type is R_RISCV_LO12_I or R_RISCV_LO12_S 7. if rel.inst is LW 8. if rel.inst.offset is in range of Uint16 and aligned by 4 b 9. Call repleaseInstByLWGP(rel)10. rel.type = R_RISCV_LWGP 11. else if rel.inst is SW 12. if rel.inst.offset is in range of Uint16 and aligned by 4 b 13. Call repleaseInstBySWGP(rel)14. rel.type = R_RISCV_SWGP 15. else if rel.inst is LD 16. if rel.inst.offset is in range of Uint17 and aligned by 8 b 17. Call repleaseInstByLDGP(rel)18. rel.type = R_RISCV_LDGP 19. else if rel.inst is SD 20. if rel.inst.offset is in range of Uint17 and aligned by 8 b 21. Call repleaseInstBySDGP(rel)22. rel.type = R_RISCV_SDGP 23. end

鏈接器優化結束后, 意味著各個段的地址已經被最終確定. 編譯器會分別為不同的重定位標記計算地址, 并按照相應的指令格式將偏移量寫入指令. 同樣因為LSGP四條指令的格式各不相同, 所以需要分別處理.

6 LSGP優化效率分析

為了分析LSGP指令對于程序的優化效果, 我們嘗試使用上文中修改的LLD和Clang對RISC-V測試(riscv-test)代碼的部分程序進行編譯鏈接. 并對比分析使用LSGP指令前后反匯編代碼數目.

6.1 LSGP縮減代碼體積的比例

由于LSGP指令針對于全局變量進行訪問, 我們從RISC-V test測試集合中選取了兩個使用全局變量較為頻繁的測試程序, 分別是用來測試整數加法的Dhrystone測試以及測試遞歸調用的towers測試, 此外還編譯了Linux常用軟件bash和vim進行測試. 測試過程中均以riscv32imac作為基準, 結果如圖7所示.

圖7 LSGP 縮減程序體積與數據段大小的關系

在Dhrystone測試程序中, 使用LSGP指令前后反匯編得出的指令條數分別為18 447和18 413條. .data和.sdata共計4 384字節. 有22個全局變量被訪問, 共計184字節的全局數據通過LDGP/SDGP被訪問. 優化前二進制大小286 216字節, 優化后二進制大小286 080字節. 二進制體積減少約0.047%. 對于towers測試程序, 由于相對使用全局變量較少且程序整體代碼量較少. .data與.sdata總計1 880字節, 共計36字節全局數據通過LSGP被訪問, 優化前二進制大小為10 152字節, 優化后為10 144字節. 二進制程序體積減少了0.07%.我們還嘗試編譯了目前常用的GNU軟件vim和bash作為日常軟件的代表. 與測試集合中刻意的測試代碼不同, bash和vim程序體積減小的幅度小于Dhrystone和towers. Bash中.data與.sdata總計35 548字節中的148字節數據被通過LSGP指令訪問. Vim中則共有782字節的數據被LSGP訪問. 相較于使用LSGP加載數據之前, bash和vim二進制程序體積的縮減效率分別是0.007 6%和0.009 8%. 總體而言, 程序體積的縮減效率與程序數據段占比呈正相關.

表3中展示的優化效率看似較為低下, 其主要由于Zce擴展的優化空間所導致. Zce指令集的目的是在C壓縮指令擴展的基礎上進一步縮減程序體積.C擴展指令已經將RISC-V程序體積大幅度縮小. 盡管如此, 相較于ARM Cortex M4架構下的二進制程序,仍然有不到10%的體積差距[5]. 于是Zce子擴展則致力于進一步縮小這不到10%的差距. 這也就導致了Zce擴展的優化空間普遍較小, 從而優化效率相較于C指令集較低. 同時考慮到Zce擴展中其他單條指令的優化效率也都在0.02%-0.24%之間, 所以從這個角度來分析LSGP作為單條指令的優化效率也算合格.

表3 LSGP縮減程序體積的效率

對于代碼體積的優化問題, 本研究中主要針對于對全局變量的優化, 因此正如表3和圖7所體現的, 一個程序中全局變量的數量或占比決定了LSGP優化的效率. 而程序中全局變量使用的數量一定程度上取決于程序的規模[6]和功能. 因此, 對于底層軟件, 例如操作系統, 單片機程序等也會使用到較多全局變量的程序來說, LSGP縮減代碼體積的效果同樣是樂觀的.

7 結論和展望

綜上所述, 與LW等常規字加載指令相比, LSGP指令能夠針對LW指令的部分使用場景進行優化, 通過約定基址寄存器的方式將寄存器的位寬分配給偏移量使用, 從而擴大指令的尋址范圍. 本文在LLD鏈接器上實現這部分的優化并進行了評估. 對于RISC-V的部分標準測試程序來說, LSGP達到了較高的優化效率. 同時在日常通用軟件中, LSGP對于程序體積的縮減也起到了一定的作用.

雖然前文描述了LWGP確實在一定程度上優化了代碼體積. 但是優化效率相較于標準測試程序中的理想條件仍有一定差距. 可以通過改進以下問題進一步減小這個差距.

(1) LSGP指針的編碼不合理.

(2) 部分LSGP的尋址能力被浪費.

(3) 局限于優化.sdata段而忽略了其他可以被優化的數據段.

psABI只考慮到LW指令的4K尋址能力. 因此將GP指針的值設置為.sdata+2K (0X800)的位置來確保盡可能大覆蓋到.sdata節的數據. 但是對于LSGP指令達到64 KB的尋址能力來說, GP指令仍位于.sdata+2K (0X800)位置的話就意味著LSGP指令的尋址范圍并不是從.sdata段開始. 所以最簡單的辦法本應是改變GP指針的位置, 但由于LSGP指令無法完全代替LW指令, 無法改變GP指針的位置. 基于此, 當前最好的解決辦法就是嘗試更改LSGP指令的格式, offset偏移量從帶符號數改為無符號數, 從GP±32 KB變成GP±64 KB, 這樣LW和LWGP搭配使用, 可以通過GP指針訪問更大范圍的全局變量.

又因為LSGP大部分的尋址范圍覆蓋到了除.sdata段以外的地址. 因此每個數據段之間的相對位置就變得相對重要. 如果相關的數據段排列在一起, 可以更大程度上避免LSGP尋址能力被浪費. 同時, .sdata段是小數據段, 其存儲了數據長度小于某一閾值(通常小于8字節)的變量, 其余的全局變量會被存儲到.data段. 這就導致程序中的.sdata段普遍較小, 甚至一部分程序根本不存在.sdata段. 目前鏈接器的實現(以LLD為例)僅基于.sdata段設置GP指針. 如果.sdata段不存在, 則GP指針就會被LLD忽略, 不只LSGP, 甚至對于LW的優化也會被無效化. 如果鏈接器在.sdata段不存在的情況下將GP指向.data段, 程序體積可以被進一步縮減.

8 結束語

本文通過介紹和分析LW指令的作用以及存在的問題, 闡述了LSGP指令的優勢和特點. 將之實現到LLD鏈接器上并粗略評估了LSGP指令優化效率. 相較于現有的字加載指令, LSGP通過擴大偏移量立即數的位寬增大尋址范圍的方式避免使用LUI指令加載高位地址, 從而縮減代碼條數和程序體積的方式, 針對于使用GP寄存器作為基址的情況進行優化. 證明了LSGP指令存在一定的優化價值. 同時在整個過程中作者也發現了目前LSGP作為實驗性指令存在的一些問題. 針對于這些問題提出了相應的解決方案. 我們已經將這些問題和建議反饋到RISC-V社區.