基于CK810處理器的匯編鏈接時優化

胡 敏,盧永江,劉 兵

(浙江大學超大規模集成電路設計研究所,杭州310027)

基于CK810處理器的匯編鏈接時優化

胡 敏,盧永江,劉 兵

(浙江大學超大規模集成電路設計研究所,杭州310027)

提出基于CK810處理器的16/32位混編指令集匯編鏈接時優化技術。利用匯編輸出二進制文件,根據CK810處理器的16/32位混編指令集中指令及操作數的特征,動態選擇指令的編碼方式,實現對指令relax,最大程度地提高了程序的代碼密度。對于在匯編時不能確定編碼方式的指令,通過留出重定位的方式,由鏈接時完成優化。在鏈接時,利用信息的確定性,實現對整個程序的壓縮和指令的替換,使得程序執行效率更高,代碼占用空間更小。匯編鏈接時優化技術克服了傳統編譯器只限于一個模塊優化的缺點,把優化范圍擴展到整個程序,實現了跨模塊的優化,使得基于CK810處理器的程序代碼密度平均提高7.52%,性能平均提升7.91%。

匯編優化;鏈接優化;動態編碼;重定位;壓縮;替換

1 概述

在計算機系統中,現今16/32位混編指令集架構已經成為主流。通常在 16/32位混合編碼集中［1-2］,32位指令用于提升指令集的運算性能,采用3操作數尋址模式,可以訪問所有寄存器資源,具有尋址范圍大的特點;16位指令是32位指令中出現頻率最高的指令子集,用于提升指令代碼密度,16位指令多采用兩操作數尋址模式,只能訪問部分寄存器資源,立即數尋址范圍較小。為獲得代碼密度和性能提升的有機結合,對16/32位混編指令集的優化必不可少。目前,大部分對代碼的優化主要集中在編譯階段［3-4］,雖然文獻［5-6］有對程序在鏈接時做過優化,但也是在對可執行程序重新反匯編和鏈接來達到優化,屬于鏈接后的優化,不是本文所論述的匯編鏈接時優化,所以當前在匯編與鏈接時對代碼優化幾乎為空白。傳統編譯器是指通過詞法分析、語法分析、語義分析、中間代碼生成、代碼優化和目標代碼生成的編譯翻譯過程。這個過程通常的優化是對單個函數而言,并且是生成一個個獨立不相關的匯編文件［7］,即不能對整個程序進行優化,故傳統編譯器對16/32位混編指令集的編譯優化存在3個不足:

(1)從文獻［8］可知,傳統編譯器對程序的分析和優化一般都是限于單個函數和過程,損失了過程間的優化機會;

(2)從文獻［9］可概括出,傳統編譯器無法獲得整個程序的所有信息,在編譯時無法獲得指令和數據的地址信息;

(3)傳統編譯器不能決定指令是以16位編碼還是以32位編碼,而指令以何種形式編碼是程序代碼密度和性能優劣的關鍵因素,若指令本可以以16位形式編碼卻被編碼成了32位的指令,無疑是浪費了代碼空間;反之,若本該編碼成32位的指令,卻被編碼成多條16位指令,性能則會受到影響。

針對傳統編譯器在16/32位混編指令集編譯時存在的局限性,本文提出匯編鏈接時的指令編碼優化方法。匯編時,運用relax優化機制,實現對指令動態選擇的編碼方式,以達到代碼密度和性能的最優化;鏈接時,根據地址信息的確定性,提出鏈接時指令替換、空間壓縮、地址索引優化和靜態地址優化等優化策略。

2 16/32位指令混合編碼的優化

2.1 匯編時relax優化

在針對16/32位混編指令集的匯編階段,當指令在操作數確定的情況下,根據操作數個數和操作數是否超出16位指令編碼范圍來選擇采用16位或32位指令。

如編碼無符號加法指令addurz,rx(CK810指令,下同),當z和x的值落入16位指令的操作數范圍時,采用16位指令編碼,否則以32位指令編碼。當指令的操作數不確定時,指令只能無條件編碼成為32位的指令,這就可能導致代碼密度的損失。為最大可能性對指令選擇合適的編碼方式,本文提出一種relax優化機制。relax機制是指,在編碼階段,把指令存放在一個個稱為frag的緩沖區,在匯編某條指令時,當指令操作數不能確定時,把指令暫且編碼成16位的指令,把這條指令作為當前frag的最后一條指令并預留出32指令的空間,之后開辟新的frag來存放接下來的指令,當再次遇到操作數不能確定的情況,重復上述過程。圖1是CK810的匯編代碼片段的匯編示意圖。

在圖1中,根據relax機制,在匯編bsr指令時,操作數label不能確定,把bsr指令編碼成16位指令,結束當前frag1。在最后匯編輸出的階段,bsr指令與lable的距離為0x1f,滿足16位指令的操作數范圍,bsr編碼成16位指令。

在引入relax機制時,在匯編輸出階段,若操作數的范圍仍不能確定,則把指令編碼為32位的指令,并留出重定位信息給連接器,在鏈接器中對指令再做優化。

圖1 匯編代碼的過程示意圖

圖2是在IA64linux主機平臺上,匯編目標處理器為CK810的測試結果(以下各個優化的環境相同)。測試實驗采用標準的benchmark CSiBE,對其在沒有引入relax和引入relax優化的一個代碼密度進行對比。從圖2可以看出,所有程序的代碼密度都有提到,代碼密度最低提高了 3%,最高提升6.38%,平均提升4.5%。

圖2 relax優化代碼密度對比

2.2 鏈接時壓縮替換優化

利用鏈接時代碼信息都確定的優勢［10-11］,可以對指令進一步壓縮與替換。本文針對嵌入式CPU指令集的特征,引入下面3種壓縮優化策略:

(1)把32位指令壓縮成16位指令;

(2)把帶常量池的指令替換成不需要常量池的指令;

(3)由上面2個壓縮,引起新的壓縮,即曾經PC偏移量超出指令編碼的,由于遞歸壓縮PC偏移量變小而可以在指令編碼中編碼。如絕對地址函數調用jsri指令,隨著程序的不斷遞歸壓縮,使得可以用相對地址偏移函數調用bsr指令來替代,從而刪除常量池,進一步提高代碼密度和性能。

圖3是鏈接時壓縮替換的示意圖。

圖3 鏈接時壓縮替換的示意圖

根據上述鏈接壓縮示意圖,通過對上述3種類型不斷的遞歸壓縮,使得程序代碼密度都處于最優狀態。圖4是CSiBEbenchmark使用鏈接時壓縮優化策略的代碼密度對比圖。從圖中可以看出,利用鏈接時壓縮優化,代碼密度最高提升6.1%,平均提升4.6%。

圖4 壓縮前后代碼密度對比

2.3 地址索引優化

在load/store架構嵌入式CPU中,獲取全局變量地址、函數地址或大立即數時,無法將立即數直接在指令中編碼,需將立即數存放在相對當前PC偏移一段距離處(即常量池),再通過相對PC偏移內存尋址指令讀取立即數(本文稱其為“地址立即數裝載指令”,如CK810的lrw指令)。在C語言的程序中,獲得某個全局變量的值,或絕對地址函數調用隨處可見,也就是說匯編代碼會包含大量的“地址立即數裝載指令”,通常在所有指令中占比為8%左右。大量的“地址立即數裝載指令”勢必會引起常量池的訪問而導致性能和代碼密度下降,一方面,“地址立即數裝載指令”從常量池內存讀取數據,頻繁的內存讀取增加了CPU和數據總線的開銷,導致性能的下降;另一方面,“地址立即數裝載指令”借助常量池來獲得數據,大量常量池的存在,必定使得代碼密度下降。

為此,本文提出一種名為“錨地址優化”的指令替換策略,把“地址立即數裝載指令”替換成立即數加法指令,從而提高代碼密度的同時提高性能。匯編時代碼段或數據段基地址放在某個預留的寄存器rb中,通過加法指令計算“地址立即數裝載指令”中的地址立即數,如CK810中采用匯編指令“addirx, rb,#offset”實現。在鏈接時,“地址立即數裝載指令”中的地址立即數已經確定,#offset等于把目標地址減去代碼段或數據段基地址rb。當程序執行時rx等于代碼段或數據段基地址rb加上#offset,就是需要裝載的地址立即數。通過“錨地址優化”的指令替換策略,不僅可以提高運行效率,也提高了代碼密度。圖5是通過CSiBEbenchmark使用“錨地址優化”的指令替換策略前后的性能比較圖,從圖中可以看出,通過靜態地址優化策略,性能平均提升2.33%,最高提升3%。

圖5 指令替換策略前后性能對比

2.4 靜態鏈接地址優化

在RISC架構嵌入式CPU中,絕對地址函數調用的目標地址立即數無法在指令中直接編碼,需要借助常量池,使得函數的跳轉范圍在4 GB內。但是在嵌入式領域里,函數通常只需要在一個很小的范圍內跳轉,如果能把絕對地址函數調用指令替換成PC相對跳轉指令,不僅能提高程序運行性能,而且還可以刪除常量池,從而提高代碼密度?；谶@個思路,本文提出一種在靜態鏈接時的函數調用優化策略,即在靜態鏈接程序時［12］,根據鏈接地址信息確定的優勢,在重定位絕對地址函數調用指令的目標地址時,根據地址的范圍,計算要跳轉的地址與當前PC距離,若小于PC相對跳轉指令的偏移范圍(如CK810為前后64 MB偏移),則把絕對地址函數調用指令替換為PC相對跳轉指令。

圖6是CSiBEbenchmark使用靜態鏈接地址優化策略的性能對比圖。從圖中可以看出,通過靜態地址優化策略,性能平均提升 5.7%,最高提升6.5%。

圖6 靜態鏈接地址優化策略性能對比

3 實驗與結果分析

實驗平臺以GCC4.5.1為編譯器,實驗的Case采用標準的benchmark CSiBE,通過編譯器編譯出匯編目標文件,再通過匯編鏈接優化生成目標程序,使目標程序運行于小端的CK810處理器上,對CSiBE使用所有的優化手段和不使用任何優化策略,來比較整體的優化效果。

從圖7和圖8可以看出,對程序使用所有的優化策略,代碼密度最低提高也有6.12%,最高可達到11.06%,平均提升 7.52%;而性能最低提升有5.8%,最高有11%,平均提高7.91%。對程序使用所有的優化策略,并不是簡單的每個優化策略之和相加,這是因為一些優化策略,比如壓縮優化和地址索引優化,在地址索引優化中,有壓縮優化的功能。另外,在壓縮優化時,隨著指令的替換與壓縮,性能會所有提高。所以所有的優化放在一起,會比單個優化的效果更好,但不是每個優化的相加。

圖7 優化前后代碼密度對比

圖8 優化前后性能對比

4 結束語

根據嵌入式16/32位混編指令集特征,在兼顧性能和代碼密度的情況下,本文充分利用編碼特性和鏈接后信息的確定性,對基于16/32位混編指令集在匯編鏈接時做出優化,取得較好的效果。另外,在實驗過程中,還發現在匯編鏈接時,仍有其他優化空間。如寄存器編碼優化,對整個函數過程進行寄存器生命周期分析,對寄存器進行重分配,盡量采用低編碼寄存器,使得指令盡可能用16位進行編碼;再如,對常量池重新排序,使得存放同一個變量的常量池合并,把分散在程序中的常量池盡量集中在一起,達到共享常量池的作用,提高代碼密度。

［1］ Bunda J,Fussell D,Jenevein R,et al.16-bit vs.32-bit Instructions for Pipelined Micro-processors［C］//Proceedings of the 20th Annual International Symposium on Computer Architecture.［S.l.］:IEEE Press,1993:237-246.

［2］ Gupta A R.Enhancing the Performance of 16-bit Code Using Augmenting Instructions［C］//Proceedings of ACM SIGPLAN Conference on Languages Compilers.［S.l.］:ACM Press,2003.

［3］ 劉 博,李蜀瑜,阮 園.一種面向CoSy編譯框架的編譯優化開發方法［J］.計算機技術與發展,2013,23(3): 61-64.

［4］ 張茉莉,楊海鋼,劉 峰,等.針對遞歸函數的高級綜合編譯優化算法［J］.計算機輔助設計與圖形學學報, 2013,25(10):1557-1565.

［5］ 陳 瑜,朱曉靜,鄒 瓊.龍芯鏈接后優化器設計與分析［J］.計算機研究與發展,2006,43(8):1450-1456.

［6］ 陳 瑜.龍芯2號鏈接后優化器的實現與分析［D］.北京:中國科學院計算技術研究所,2004.

［7］ Li D X,Ashok R,Hundt R.Lightweight Feedbackdirected Cross-module Optimization［C］//Proceedings of the 8th Annual IEEE/ACM International Symposium on Code Generation and Optimization.［S.l.］:ACM Press,2010:53-61.

［8］ Liu Xianhua,Zhang Jiyu,Cheng Xu.Efficient Code Size Reduction Without Performance Loss［C］//Proceedings of ACM Symposium on Applied Computing.［S.l.］: ACM Press,2007:666-672.

［9］ Bus B,Kaster D,Chanet D,et al.Post-pass Compaction Techniques 2003［J］.Communications of the ACM, 2003,46(8):41-46.

［10］ Phela R.Improving ARM Code Density and Performance［EB/OL］.(2003-05-07).http://www.cs.uiuc.edu/ class/fa05/cs433ug/PROCESSORS/Thumb2.pdf.

［11］ Sutter B.Link-time Binary Rewriting Techniques for Program Compaction［J］.ACM Transactions on Programming Languages and Systems,2005,27(5): 882-945.

［12］ Jones T M,BartoliniS,Maebe J,etal.Link-time Optimization for Power Efficiency in a Tagless Instruction Cache［C］//Proceedings of the 9th Annual IEEE/ACM InternationalSymposium on Code Generation and Optimization.［S.l.］:IEEE Press,2011:32-41.

編輯 顧逸斐

Assembly and Link Time Optimization Based on CK810 Processor

HU Min,LU Yongjiang,LIU Bing
(Institute of Very Large Scale Integrated Circuits Design,Zhejiang University,Hangzhou 310027,China)

According to feature of 16/32 bit mixed instruction set of CK810,assembly and link time optimization techniques based on the 16/32 mixed instruction set of CK810 make use of assembler output binary files to achieve instructions relax and coding instructions dynamically.The assembler gives relocations to linker for instructions that can' t decide how to code at assembly time,the techniques fully utilizes the information only available at link time to realize of the entire program for compression and replacement of instructions to make program more efficient and small.Assembly and link optimization techniques overcome the limitations of traditional compilers by enlarging the optimizing scope from a single function or a module to the whole program,making the code density on CK810 increase an average of 7.52%, the average performance improvement of 7.91%.

assembly optimization;link optimization;dynamic coding;relocation;compaction;replace

1000-3428(2014)11-0250-05

A

TP313

10.3969/j.issn.1000-3428.2014.11.050

國家“863”計劃基金資助項目(2009AA011706)。

胡 敏(1987-),男,碩士,主研方向:嵌入式系統;盧永江,副教授、博士;劉 兵,碩士研究生。

2013-10-25

2014-01-06E-mail:zju21110143@163.com

中文引用格式:胡 敏,盧永江,劉 兵.基于CK810處理器的匯編鏈接時優化［J］.計算機工程,2014,40(11):250-254.

英文引用格式:Hu Min,Lu Yongjiang,Liu Bing.Assembly and Link Time Optimization Based on CK810 Processor［J］.Computer Engineering,2014,40(11):250-254.