LLVM (Low Level Virtual Machine) 筆記
by loda
hlchou@mail2000.com.tw
很喜歡愛因斯坦所說的這段話,“ 在科學上,每一條道路都應該走一走. 發現一條走不通的道路,就是對於科學的一大貢獻.科學史只寫某人某人取得成功,在成功者之前探索道路，發現 ‘此路不通‘ 的失敗者統統不寫,這是很不公平的“ . 第一次看到LLVM技術時,當時會心想跨平台的技術,不是已經有了JAVA 虛擬機搭配JIT(Just In Time)技術,或是微軟所推的.Net 也基於支援IL Assembly可以在跨平台的方案上得到滿不錯的效能. 又一個新出的LLVM跨平台技術,真的能帶來跟以往不同的好處嗎?
在深入探究LLVM後,其實不論是在效能 (可以參考OpenBenchMark網站http://openbenchmarking.org/result/1204215-SU-LLVMCLANG23 ),支援語法的廣泛性(包括 C/C++ 都可以直接編譯為LLVM BitCode),並且也支援指標,函式指標,Inline Assembly,對於一般應用程式的轉換上,成本可以大幅度的降低,所產生的BitCode除了可以透過LLI（LLVM Interpreter)執行外,也可直接轉譯為所在平台的機械碼.對多數的開發者而言,光是可以讓C/C++開發的成果只要由開發者編譯一次後,就可以擁有跨平台的特性,對許多產品開發上就已經很有誘因了.
實際下載LLVM編譯安裝前,可以先透過http://llvm.org/demo/index.cgi 由LLVM所提供的線上測試網站,在這可以嘗試把不同的C/C++語言透過LLVM線上轉譯為對應的BitCode Assembly語法,而這樣的IR中間語法,就可以再透過LLC轉譯為不同平台上的原生Assembly Code.
LLVM是由Vikram Adve與Chris Lattne在2000年開始進行開發,透過編譯器的技術,可支援把C/C++,Object-C,Fortran,Java ByteCode,Python,ActionScript以及其他程式語言編譯為LLVM BitCode Assembly. 基於這跨平台的BitCode Assembly就可以再轉譯為目標平台的可執行機械碼. 並在2004年於 Code Generation and Optimization (CGO’04)上發表了’LLVM: A Compilation Framework for Lifelong Program Analysis & Transformation ‘ Paper (文章可在這取得http://llvm.org/pubs/2004-01-30-CGO-LLVM.pdf, 投影片網址http://llvm.org/pubs/2004-03-22-CGO-LLVM-Presentation.ppt),介紹當時LLVM LifeLong Optimization 概念,並在這Paper中提到LLVM幾個主要的特色
1, RISC Like的指令集.
2, 以SSA(Static Single-Assignment) 形式提供數目不設限的虛擬暫存器
3, 以Load/store 指令存取型態定義的指標(Typed-Pointer)
4, 基於SSA可明確資料在運作過程中的傳遞流程
5, 提供跟語言無關的形態資訊
6, 在exception的支援上提供 setjmp/longjmp實作的Exception機制,並提供 invoke指令可呼叫一個需要帶有Exception Handler的函式,與提供Unwind指令,能透過Stack Frame回推到上一個invoke指令位置.
在2005年時,Chris Lattner加入了Apple,也藉此讓LLVM成為Apple官方所支持的編譯器方案.在2005年以前,LLVM一直沒有在實際的商業化產品中導入,直到2005年後,才開始應用在相關商業產品中.有關LLVM 技術在Mac OS X 上的演進可以參考以下的連結 http://arstechnica.com/apple/reviews/2007/10/mac-os-x-10-5.ars/11#llvm 與 http://arstechnica.com/apple/reviews/2009/08/mac-os-x-10-6.ars/9 .
在支援C/C++的部份,LLVM的前端可以為llvm-gcc或是Clang.
以llvm-gcc來說,這是基於GCC修改而來支援 C/Object-C 的LLVM C Front End編譯器工具,並因此而擁有許多GCC故有的能力,llvm-gcc可用來產生最終的執行檔案,或是LLVM BitCode 二進位檔案,或是LLVM Assembly原始碼.llvm-gcc在不加入任何參數下的預設行為跟原本的gcc一樣,會產生最終的可執行檔案,如果是加上 -emit-llvm與-c則是會產生LLVM BitCode的二進位檔案,若加上-emit-llvm與-S則是會產生LLVM的Assembly原始碼.
既然已經有了llvm-gcc作為llvm的前端,又為何要有Clang呢? 可以參考這網頁上的訊息如下(http://linuxtoy.org/archives/llvm-and-clang.html )
| Apple 使用 LLVM 在不支援全部 OpenGL 特性的 GPU (Intel 低端顯卡) 上生成代碼 (JIT)，令程式仍然能夠正常運行。之後 LLVM 與 GCC 的集成過程引發了一些不快，GCC 系統龐大而笨重，而 Apple 大量使用的 Objective-C 在 GCC 中優先順序很低。此外 GCC 作為一個純粹的編譯系統，與 IDE 配合很差。加之許可證方面的要求，Apple 無法使用修改版的 GCC 而閉源。於是 Apple 決定從零開始寫 C family 的前端，也就是基於 LLVM 的 Clang 了。 |
由此可知Clang(官方網站為http://clang.llvm.org/)將會是未來LLVM所主要搭配配的前端C/C++編譯器工作.
LLVM本身主要是從處理器CPU的角度來進行虛擬化,也就是說讓各種語言所開發的應用程式都可以透過前端編譯器轉譯為LLVM虛擬處理器所能執行的BitCode,再將 BitCode轉譯為不同處理器平台的指令集(目前支援像是x86, ARM, MIPS,PowerPC,Sparc,XCore,Alpha…etc 處理器指令集).也因此LLVM Compiler只需要專注再LLVM對BitCode轉譯為不同處理器平台機械碼優化的任務上即可,而不需在前端去面對各種不同程式語言的編譯與優化工作.LLVM的前端包括像是llvm-lua(http://code.google.com/p/llvm-lua/)可以把lua編譯為LLVM BitCode,或是llvm-java支援的class2llvm要把Java ByteCode轉譯為LLVM BitCode.
LLVM 的跨平台支援演示.
如下筆者以同樣是ARM平台來看,對同一個 BitCode Assembly,選擇要對Cortex-A9優化與要對ARM9優化選項後,所產生的組語有哪些差異
[root@localhost reference_code]#
[root@localhost reference_code]# arm-none-linux-gnueabi-gcc -mcpu=arm9 sample_ar
m9.s -ldl -o sample_arm9
//把BitCode Assembly 針對ARM 架構下的Cortex-A9處理器進行優化,並產生檔案到sample_cortexa9.s
#llc -O2 -march=arm -mcpu=cortex-a9 sample.bc -o sample_cortexa9.s
//把BitCode Assembly 針對ARM 架構下的ARM9處理器進行優化,並產生檔案到sample_arm9.s
# llc -O2 -march=arm -mcpu=arm9 sample.bc -o sample_arm9.s
//可再透過 Diff 比較針對Cortex-A9與ARM9優化後,兩者的差異 (各位可以自行嘗試,筆者就不再此列舉內容).
# diff sample_corei7.s sample_atom.s
兩者最直接的差異就是在所產生的組語中,Cortex-A9會加入對 ‘.fpu neon’ 指令集的支援,而這是在不支援Neon指令集的ARM9處理器上所不會有的.
最後不免要把兩段BitCode實際編譯驗證,
# arm-none-linux-gnueabi-gcc -mcpu=cortex-a9 sample_cortexa9.s -ldl -o sample_cortexa9
# arm-none-linux-gnueabi-gcc -mcpu=arm9 sample_arm9.s -ldl -o sample_arm9
並且比較基於兩個不同處理器優化下,所產生最終執行檔的Size差異.
# ls -l sample_cortexa9
-rwxr-xr-x. 1 root root 6877 May 13 23:42 sample_cortexa9
# ls -l sample_arm9
-rwxr-xr-x. 1 root root 7201 May 13 23:42 sample_arm9
筆者把一段C Code (由於重點是在演示如何把C Code轉 BitCode,再透過BitCode轉成不同平台的Assembly,所以在此就不偏重C Code的內容了),先轉成BitCode,之後再編譯為跨不同處理器平台的Assembly原始碼與最終的執行檔案,藉此演示LLVM在支援不同平台優化技術上的能力.
//透過clang 把C程式碼編譯為 BitCode 二進位檔案.
[root@localhost reference_code]# clang -O2 -emit-llvm sample.c -c -o sample.bc
[root@localhost reference_code]# ls -l sample.bc
-rw-r–r–. 1 root root 1956 May 12 10:28 sample.bc
//把BitCode二進位檔案轉譯為x86-64 platform assembly code.
[root@localhost reference_code]# llc -O2 -mcpu=x86-64 sample.bc -o sample.s
//編譯轉譯後的assembly code 為 x86-64 native execution file.
[root@localhost reference_code]# gcc sample.s -o sample -ldl
[root@localhost reference_code]# ls -l sample
-rwxr-xr-x. 1 root root 8247 May 12 10:36 sample
//把BitCode二進位檔案轉譯為 ARM Cortext-A9 platform assembly code.
[root@localhost reference_code]# llc -O2 -march=arm -mcpu=cortex-a9 sample.bc -o
sample.s
//編譯轉譯後的 assembly code 為 ARM Cortext-A9 native execution file.
[root@localhost reference_code]# arm-none-linux-gnueabi-gcc -mcpu=cortex-a9 sample.s -ldl -o sample
[root@localhost reference_code]# ls -l sample
-rwxr-xr-x. 1 root root 6877 May 12 10:54 sample
藉由上述的演示,我們可以知道LLVM如何透過LLC(LLVM Compiler)把同一段BitCode轉譯為ARM或x86平台的組語,而所產生的Assembly Code可以再透過GCC編譯為所在平台的執行檔. 有關LLVM的編譯環境運作示意圖,可參考下圖的所示.
透過LLVM前端把程式語言C/C++/Java/Fortran轉譯為BitCode Assembly,再藉由LLVM Compiler轉譯為不同平台差異的Assembly實作.
Clang的靜態分析語句引擎(static analyzer)
Clang不只是LLVM前端的C/C++/Objective C/C++ 編譯器工具,還支援對軟體開發極有幫助的靜態程式碼分析工具,有關LLVM的Clang靜態語句分析(Clang Static Analyzer)工具的介紹可以參考網站http://clang-analyzer.llvm.org/ ,這工具可用以分析C與Objective-C所開發的應用程式(尚不支援 C++/Objective-C++).目前這工具是以Open Source的方式釋出,並成為Clang 計畫的一部分.
其實市場上原本已有一些靜態程式語言分析的商業化工具,像是Coverity 或是 Klocwork,可在開發階段針對所撰寫的C/C++,Java應用程式潛在的設計問題提供分析結果,讓開發者針對這些分析內容先行解決,如此可減少在RunTime QA 人員找出Bug後,還要再提交給研發人員覆現問題的往返時間成本.好的程式語言靜態分析工具可以提前找出可能是在哪一行發生記憶體拷貝的溢位,避免QA週期透過窮舉法去走過所有程式邏輯的路徑,涵蓋範圍的不足.
在Clang基於LLVM環境編譯後,可以在llvm-3.0.src/tools/clang/tools/scan-build與llvm-3.0.src/tools/clang/tools/scan-view 這兩個路徑下取得scan-build與scan-view兩個Clang靜態分析工具編譯後的執行檔, scan-view 可用以檢視scan-build分析後產生到指定目錄中的結果報告.
接下來,筆者以如下的程式碼來驗證scan-build靜態分析程式碼的能力,
| int main()
{
char *p,*xp;
char vBuffer[128];
int i;
p=malloc(128);
xp=(char *)malloc(222);
memset(p,256,0);
for(i=0;i<256;i++)
vBuffer[i]=0×00;
return 1;
} |
這段程式碼中,筆者把malloc回來的pointer不作NULL檢查就直接使用,並刻意memset超出所配置記憶體的空間,或是透過 for 迴圈故意寫出超過Array配置大小的範圍,如下所示為透過scan-build執行後,產生的錯誤訊息
[root@www LLVM]# ~/scan-build clang -O3 -emit-llvm test.c -c -I/usr/local/bin/../lib/clang/3.0/include/
test.c:9:2: warning: Value stored to ‘xp’ is never read
xp=(char *)malloc(222);
^ ~~~~~~~~~~~~~~~~~~~
1 warning generated.
scan-build: 1 bugs found.
scan-build: Run ‘scan-view /tmp/scan-build-2012-05-20-6′ to examine bug reports.
最後的報告是產生在 /tmp/scan-build-2012-05-20-6 目錄下,可以透過 scan-view工具進行檢視,如下指令.
[root@www LLVM]# ~/scan-view /tmp/scan-build-2012-05-20-7
檢視後的 Bug內容為
File: test.c
Location: line 11, column 2
Description: Value stored to ‘xp’ is never read
以scan-build對這案例的分析結果來看,只有找出 xp 變數有被配置但沒有被使用的問題,其他更嚴重的溢位問題,並沒有被偵測出來. 以目前scan-build的分析能力,對商業化產品的開發,選擇Coverity 或klocwork這類功能比較完整的靜態程式碼分析工具,應該會是對軟體品質確保上有比較好的幫助才是.當然,若在一般性的檢查上,scan-build還是可以帶來一些幫助的.
SSA(Static Single-Assignment)
LLVM IR (Intermediary Representation)會以 SSA (Static Single Assignment) 的形式表述,在往LLVM Assembly進一步的探究前,SSA應該是最值得介紹的項目,也是目前LLVM Assembly在設計實作上的基礎思維. 簡要來說,SSA的技術是由Wegman,Zadeck,Alpern,與Rosen在1988來開始發展,目前已經應用在GCC 4.0,IBM或Sun的Java JIT Compiler. SSA主要的概念為每個變數會被限制只能被給值一次的中間形式(IR),也就是說在轉成IR型態後,原本認為的變數,會在每次內容被改變時,就會重新把結果給值到一個新的變數中,例如變數X在運算過程中內容被改變了5次,就會因此而產生五個與最終給值有關的中間形式靜態單一分配形式.
每個描述式結果都會對應到一個全新的變數 (也就是說假設所在的環境中,全新變數宣告的總數也是沒有上限的.)
| 原本的描述式 |
轉成SSA後 |
| x=a + b
y=b + x
x=a + 21
x=c * x
y=x + b |
x1 = a + b
y1 = b + x1
x2 = a + 21
x3 = c * x2
y2 = x3 + b |
經過SSA 的Dead Code Elimination後,編譯器就可以識別出其實x1與y1是沒有必要存在而可以加以優化消除的,簡化後的結果如下所示
| x2 = a + 21
x3 = c * x2
y2 = x3 + b |
LLVM 跟Dalvik 執行環境的比較
從目前的趨勢上,LLVM很有機會在Android執行環境扮演一定程度的角色,相對於Dalvik Java 的執行環境,LLVM可以提供更貼近於平台Native應用程式的執行效能. 在跨平台的能力上,Dalvik可以選擇透過 Portable Interpreter (in C), Fast Interpreter (in Assembly)或基於Just-In Time Compiler編譯技術,在支援Neon指令集的平台上,JIT目前也能透過Neon指令產生優化後的結果.
而同樣的優勢,到了LLVM後又更進一步的改變,例如LLVM的IR(Intermediate Representation)是給LLVM直譯器/編譯器看的IR,相對於Java的ByteCode是一個被編譯後的結果,而JIT所做的優化則是根據每個Java ByteCode指令集操作改用原生指令實作所進行的優化(例如:把Dalvik move-wide指令用ARMv7 NEON指令實現,以進行加速),也就是說當從Java Code轉成ByteCode時,實際上有關應用程式流程的優化動作已經被進行過,所產生的ByteCode是適合直接上到Java處理器/虛擬機上執行的結果.
但,在LLVM透過Front-End所產生的結果則是一個還需要經過編譯的中間結果,並且是以SSA (Static Single Assignment) 編譯結果表述的內容,也就是說當BitCode要執行時,還需要透過LLI (LLVM Interpreter)或LLC (LLVM Compiler)來進行直譯或是編譯為目標平台原始碼的過程.
也因此,相較於Java JIT技術的結果,LLVM可以提供更接近於原生應用程式的效能,能根據基於LLVM IR所表述的SSA BitCode結果,重新優化編譯為目標平台的機械碼,相較於Java ByteCode的作法,是基於已經編譯好的ByteCode結果,把每個ByteCode指令改用以平台上的機械碼實現,LLVM能帶來的優化程度與結果是相對較佳的.
簡單來說,兩者最大的差異有
1, 從產生的執行碼來看: BitCode可以被LLVM編譯為原生碼,而且運作過程中直接呼叫Native函式庫,也可以直接被處理器執行.反觀Dalvik ByteCode,必須要基於Dalvik 虛擬機執行,就算是基於Dalvik JIT Compiler的技術,也只有部分的Dalvik ByteCode Trace-Run區塊可以被編譯為原生的機械碼,並不像是LLVM技術所產生的原生碼,是可以100%運作在原生碼執行的環境中.
2,從編譯後的原生碼重用性來看: LLVM可以把BitCode整個優化為原生碼,目前Dalvik ByteCode只支援執行時期階段的ByteCode JIT Compiler,一旦Dalvik應用程式結束,所有JIT編譯後的結果就消失了,必須要等下一次該Dalvik應用程式重新被載入執行,再根據每一個ByteCode Trace-Run區塊的Counter重新去決定哪些區塊要被編譯為Native Code.
3,從執行時期負荷來看 :LLVM Compiler後的結果,能以原生應用程式的方式執行,但Dalvik JIT會跟去Trace-Run Counter結果統計出熱區重新編譯,取得優化後的效能,對處理器的Run-Time負荷來說,LLVM顯然可以帶來更好的改善. 若Dalvik Application把主要的運算都放到JNI .so動態函式庫中,試圖改善Run-Time的效能問題,但卻會因為.so是有平台相依性的,而必須要針對所有的平台都提供一份專屬的.so.
4,從記憶體需求的角度來看:統計編譯後的結果,Clang把C/C++程式碼編譯為 LLVM IR之後透過LLVM Compiler轉譯為目標平台Assembly後所產生的執行檔大小,甚至可以比起直接透過GCC編譯的結果更佳,而Dalvik應用程式,在經過JIT後大小會膨脹 (一般來說為 4-8倍),並且相關的JAR Framework載入後,若也有相關的熱區,也會需要經由JIT技術來加以即時編譯優化,並儲存到JIT Cache中,相較於LLVM技術則無需有這段額外的記憶體成本在.
5,從儲存空間的需求來看: 一般的Dalvik Application APK需要有兩份儲存空間一個是DEX所在的.apk,一個是ODEX 儲存在dalvik-cache中.而LLVM Application並無這樣的必要.
6,從系統安全性的角度來看:LLVM支援指標/Inline Assembly,這是在Java世界中所不允許的,也因為支援指標,甚至是函式指標,可讓LLVM在效能的提升上得到很好的改善,但卻也隱藏了潛在的安全問題.
如下圖所示,為一個Dalvik應用程式在執行時相對於Dalvik 虛擬機與.so動態函式庫的示意圖,我們可以看到 Dalvik應用程式主要還是基於 ByteCode Based的JAR Framework,或是可直接透過JNI介面去呼叫外部的.so動態函式庫,以便得到接近原生碼的執行效能.
接下來,可以參考下圖為透過LLVM Interpreter 執行BitCode應用程式的示意圖,可以看到除了LLVM BitCode應用程式以外,其他外部函式的呼叫都會直接對應到原生的.so動態函式庫.
到這段落,各位以該對於Dalvik/LLVM應用程式在Run-Time上的差異有所了解了,接下來筆者將介紹另一個LLVM延伸的重要應用Native Client(Nacl) 與 Portable Native Client (PnaCl).
Native Client(Nacl) and Portable Native Client (PNaCl)
Google是在約2008開始進行Native Client的開發工作,並在2009年初舉辦Google Native Client Security/Hacking比賽 ,可參考網頁:http://www.zdnet.com/blog/google/hack-googles-native-client-and-get-8192/1295,比賽結果可以在這看到https://developers.google.com/native-client/community/security-contest/,並在Google 瀏覽器Chrome 10之後加入對Native Client的支援.
Native Client是類似微軟早期在Internet Explorer上支援的 ActiveX OCX元件的想法,讓網頁應用程式可以用處理器原生碼在支援這技術的瀏覽器直接執行. 參考Native Client網頁說明,簡單來說目標就是 "seamlessly execute native compiled code inside the browser",也就是可以 "在瀏覽器上無縫執行編譯後的機械碼 ". 目前Native Client編譯後的NaCl Executable (*.NEXE) 檔案格式,會根據目標平台編譯,例如筆者所使用的Windows 7 64bits電腦執行環境,所編譯出的NEXE檔案中的機械碼就會是是用於x86_64環境執行的程式碼,也就是說在開發Native Client時,所產生的NEXE檔案是沒有辦法直接跨到其它平台執行的.
基於Native Client SDK,一個Native Client技術的NEXE執行檔案可以透過如下i686-nacl-gcc 編譯指令編譯出來,如果透過i686-nacl-objdump 去觀察編譯後的結果,可以注意到每個函式的起點都必須是32bytes Alignment的記憶體位址.
i686-nacl-gcc -o hello_loda_x86_32.nexe hello_loda.c -m32 -O0 -g -pthread -O0 -g -Wno-long-long -Wall -lppapi -ldl
參考網頁https://developers.google.com/native-client/overview,Native Client,Native Client支援Software Fault Isolation (SFI),用以檢查所下載機械碼安全性的SandBox大約會讓帶來5%的Overhead.但由於Native Client是以機械碼的方式載入到使用者瀏覽器中執行,因此包括處理器的暫存器與支援inline assembly的寫法,都會比起透過Java Applet+Just-In-Time Compiler 或是透過Flash Action Script在瀏覽器中支援應用程式的方式來的更有安全性的疑慮. 舉個例子來說,這表示如果Native Client的Security SandBox如果沒有防守好的話,就有機會讓一個你在瀏覽網頁過程中所執行的Web Application讀取到你電腦上的檔案資料,或是有機會對將其他的惡意代碼寫入到你的電腦中,讓使用者電腦在不預期的狀況下,被第三方的應用程式給植入.
由於Native Client本身機制是產生出x86 32bits 與 64bits的機械碼,目前也不支援x86以外的平台,因此Google也在2010年時進行新的PNacl (發音為Pinnacle)技術開發,各位可以參考Google的’PNaCl Portable Native Client Executables’文件,如果要讓使用者根據不同平台的差異(X86-32/64 bits,Java,ARM,MIPS,PowerPC….etc)自行編譯出相關的執行檔案進行驗證無誤後發佈產品,這背後會有相當的難度,也因此,Google基於LLVM BitCode的特性開發了PNacl的技術,可參考筆者從文件’PNaCl Portable Native Client Executables’所截出的下圖,PNaCl的想法是開發者產出的是BitCode的檔案格式 (非原本Native Client的X86 32/64 bits ISA指令集),在網頁瀏覽的過程中,由使用者下載包含該BitCode內容的PNaCl檔案格式,透過LLC (LLVM Compiler)技術,動態的在目標平台上把BitCode轉譯為目標平台上的可執行機械碼,隨後成為一個NaCl執行檔案.
基於這樣的設計,等於可以延續Native Client計有的基礎,又可以讓產生機械碼的動作不是在開發者開發階段就要去面對不同平台差異而去產生,開發者所需面對的只有LLVM的BitCode,並且只要基於BitCode的環境驗證無誤下,就可以透過目前LLVM的優勢把BitCode重新編譯為目標平台上的機械碼,如此就可以延續目前Native Client的基礎,但又可以真正的達到跨所有處理器平台的目的.
下圖同樣為Google的’PNaCl Portable Native Client Executables’文件中的截圖,可以看到PNaCl的概念上,是透過LLVM BitCode達成跨平台的目的,在基於NaCl SandBox技術確保Native Client 執行環境的安全性.
Portable Native Client官方網頁為http://www.chromium.org/nativeclient/pnacl/building-and-testing-portable-native-client , 基於PNaCl所產生的執行檔為PEXE (原本的Native Client為NEXE),使用LLVM編譯器的好處是,開發者可以用C/C++語言開發,然後基於LLVM可以讓NACL應用程式在Browser上運作時,效率接近直接用C/C++語言針對該平台編譯的結果,而且最重要的是又可以用同一套LLVM產生中間碼(IL)的結果相容於所有的處理器平台.
Native Client定義跟Web Browser (例如目前Google的Chromium) 之間的介面為Pepper,可用以讓Native Client據此實作成為Browser Plug-in. Pepper介面是從Mozilla的NPAPI而來,新版的Native Client Pepper v2介面則重新在NPAPI基礎增加新的API介面.有關Pepper API的說明可以參考網頁http://code.google.com/p/ppapi/wiki/Concepts .
參考目前Native Client的文件,基於安全性的考量Native Client在施行上會有以下的限制存在
1,不支持Hardware Exception.
2, 不支持產生新的Process/Subprocess
3,不支持Raw TCP/UDP Sockets (會額外提供WebSockets 供TCP與UDP Peer-to-Perr Connection.)
4,不支持同步(Synchronous) Blocking I/O
5,不支持對可使用記憶體的查詢
6,可以使用Inline Assembly,但必需要通過Native Client Validator (ncval) 工具的查核
7,跟Native Client所 Plug-in進Browser介面的Pepper API呼叫必須從應用的Main Thread而來.
Google Native Client的相關資訊可以參考
| Google Code Project |
http://code.google.com/p/nativeclient/ |
| Native Client SDK |
https://developers.google.com/native-client/?hl=zh-TW |
| Download Native Client SDK |
https://developers.google.com/native-client/sdk/download?hl=zh-TW |
| Test Run |
https://developers.google.com/native-client/devguide/devcycle/running?hl=zh-TW |
| Distribute |
https://developers.google.com/native-client/devguide/distributing?hl=zh-TW |
| Getting Start |
https://developers.google.com/chrome/web-store/docs/get_started_simple?hl=zh-TW#step4 |
目前為止我們知道LLVM技術將有機會更廣泛的應用到瀏覽器技術上,與我們生活更緊密的結合,既然知道到LLVM本身的認識是可以把BitCode透過LLI (LLVM Interpreter)以直譯方式執行,或是透過LLC (LLVM Compiler)轉譯為不同平台上的機械碼,相對的把C/C++這些主要開發語言轉譯為BitCode的前端編譯器就變得很重要了,下一段落就讓我們實際操練Clang與LLVM的執行環境.
編譯第一個LLVM程式
接下來讓我們嘗試編譯一個基於BitCode檔案格式的LLVM程式,首先如下範例程式
| #include <stdio.h>
int main()
{
printf("LLVM Test\n");
return 0;
} |
透過clang -S -emit-llvm test.c -o test.llvm 進行編譯,可以產生 LLVM的Assembly Code,如下所示
| ; ModuleID = ‘test.c’
target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128″
target triple = "x86_64-unknown-linux-gnu"
@gCount = global i32 0, align 4
@.str = private unnamed_addr constant [11 x i8] c"LLVM Test\0A\00″, align 1
define i32 @main() nounwind uwtable {
%1 = alloca i32, align 4
%i = alloca i32, align 4
store i32 0, i32* %1
%2 = call i32 (i8*, …)* @printf(i8* getelementptr inbounds ([11 x i8]* @.str, i32 0, i32 0))
ret i32 0
}
declare i32 @printf(i8*, …) |
有關LLVM Assembly Code格式的介紹可以參考http://llvm.org/docs/LangRef.html .
可以透過 clang -c -emit-llvm test.c -o test.bc,產生LLVM BitCode格式的檔案,並且可以透過lli執行所產生的 BitCode檔案,如下所示
[root@localhost test]# lli test.bc
LLVM Test
再來可以透過llvm-dis 反組譯 test.bc為test.ll
[root@localhost test]# llvm-dis test.bc
如下為test.ll內容
| [root@localhost test]# more test.ll
; ModuleID = ‘test.bc’
target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128″
target triple = "x86_64-unknown-linux-gnu"
@gCount = global i32 0, align 4
@.str = private unnamed_addr constant [11 x i8] c"LLVM Test\0A\00″, align 1
define i32 @main() nounwind uwtable {
%1 = alloca i32, align 4
%i = alloca i32, align 4
store i32 0, i32* %1
%2 = call i32 (i8*, …)* @printf(i8* getelementptr inbounds ([11 x i8]* @.str, i32 0, i32 0))
ret i32 0
}
declare i32 @printf(i8*, …) |
並可透過llvm-as test.ll 重新把test.ll編譯為test.bc.
[root@localhost test]# llvm-as test.ll
[root@localhost test]# ls -l test.bc
-rw-r–r–. 1 root root 656 Apr 10 22:49 test.bc
[root@localhost test]# date
Tue Apr 10 22:49:22 CST 2012
[root@localhost test]#
接下來讓我們以LLVM 把兩個BitCode檔案進行Link,以驗證LLVM的運作行為
首先 testA.c如下所示
| #include <stdio.h>
long funcB();
int main()
{
int X=funcB();
printf("X:%xh\n",X);
return 0;
} |
而 testB.c如下所示
| #include <stdio.h>
long funcB()
{
return 0×9999999;
} |
先把 testA.c與testB個別編譯為 testA.bc與testB.bc 兩個BitCode檔案格式,再透過llvm-link把這兩個BitCode檔案Link成一個test.bc檔案,再透過lli 執行該BitCode test.bc檔案.
[root@localhost test]# clang -c -emit-llvm testA.c -o testA.bc
[root@localhost test]# clang -c -emit-llvm testB.c -o testB.bc
[root@localhost test]# llvm-link testA.bc testB.bc -o test.bc
[root@localhost test]# lli test.bc
X:9999999h
[root@localhost test]#
如下所示,也可以先把 testB.bc先Archive 成一個libTestB.a 的靜態連結函式庫,並透過llvm-nm檢視該函式數所提供的Symbol,最後再透過llvm-ld把 testA.nc跟靜態函式庫libTestB.a 進行連結成Native執行檔案的動作,最後就可以透過 ./test驗證最終執行結果是否符合預期.
[root@localhost test]# llvm-ar rucs libTestB.a testB.bc
[root@localhost test]# llvm-nm libTestB.a
T funcB
[root@localhost test]# llvm-ld testA.bc -o test -lTestB
[root@localhost test]# date
Tue Apr 10 22:57:42 CST 2012
[root@localhost test]# ls -l test
-rwxr-xr-x. 1 root root 66 Apr 10 22:57 test
[root@localhost test]# ./test
X:9999999h =>符合預期.
[root@localhost test]#
在實際操練LLVM有關的工具指令後,接下來就是介紹LLVM 反組譯與BitCode檔案格式.
LLVM Assembly Language 與 程式碼反組譯
有關LLVM Assembly Language的支援列表筆者另外整理在http://loda.hala01.com/llvm-assembly-language/ ,供參考.
LLVM的Identifiers可以區分為Global全域開頭為’@'的Identifiers(包括函式與全域變數)與Local區域開頭為’%'的Identifiers,如前面的例子,所有的變數會以其命名作為字串但加上@或%表示其為全域變數(例如:@gX)或是區域變數(例如:%Y).參考’ LLVM Language Reference Manual’文件可接受的字元包括 ‘ [%@][a-zA-Z$._][a-zA-Z$._0-9]*’,如果有遇到不在這範圍內的字元,就會透過16進位的方式儲存,同樣以前述的例子來說,函式main的字串會以 ‘ main:%d\0A\00′方式儲存,長度為9bytes,其中\0A代表0x0A的16進位字元,而\00則代表0×00的字串結尾字元.
沒有在程式設計階段被命名的變數,就會以上述像是%11, @22,%33或@44這類數字形式方式來命名.
常數Constants的部份,筆者說明列舉如下所示
| 常數型態 |
說明 |
| Boolean |
i1(a single-bit integer),
會以’true’ 與 ‘false’ 代表長度為1bit的整數值 |
| Integer |
通常為i32 (a 32-bit integer),可以用來表示負值,長度可為i1(1bit), i2(2bits), i3(3bits), … i8 (8bits), … i16 (16bits), … i32 (32bits), … i64 (64bits), … |
| Floating point |
通常為half(16-bit floating point value),float(32-bit floating point value)或double(64-bit floating point value),表示的方式可以為10或16進位浮點數(double 0x432ff973cafa8000),或指數符號（例如1.23456e+2） |
| Null pointer |
為Pointer Type,會以 ‘null’ 字串表示Null Pointer Constant |
| Structure |
結構常數的組成會以{}括號來定義前後範圍,並以逗號’,'分隔前後的組成變數,每個組成變數都會包括它的形態(i32,float,i32*,double…etc),例如像是"{ i32 4, float 17.0, i32* @G }",其中’i32* @G ‘表示這個變數儲存的是全域變數 ‘@G’ 的位址,可用於透過存取這個結構時,再藉由這個變數去存取全域變數’@G’. |
| Array |
Array的組成會以[]方括號來定義前後範圍,並以逗號’,'分隔前後的變數值,每個變數都會包括它的形態,例如像是 "[ i32 42, i32 11, i32 74 ]",Array中常數的型態與變數個數,都需要跟原本所宣告的形態一致,例如像是’[11 x i32]‘(Array of 11 32-bit integer values)或’[4 x i8]‘ (Array of 4 8-bit integer values). |
| Vector |
Vector的組成會以<>的小於/大於括號來定義前後範圍, 並以逗號’,'分隔前後的變數值,每個變數都會包括它的形態,例如像是 "< i32 42, i32 11, i32 74, i32 100 >",Vector中常數的型態與變數個數,都需要跟原本所宣告的形態一致 |
| Zero initialization |
字串“zeroinitializer’ 可用以進行初始化值為零的任何型態(Type),通常應用在像是大型的Array,可以讓相關的變數初始化為Zero. |
| Metadata node |
A metadata node is a structure-like constant with?metadata type. For example: "metadata !{ i32 0, metadata !"test" }". Unlike other constants that are meant to be interpreted as part of the instruction stream, metadata is a place to attach additional information such as debug info. |
而在變數的部分,當在程式設計階段,給定一個全域變數常數值時,這個全域變數所包含的常數內容,就可以在執行時期的任意時間點被參考與使用,可參考如下兩個全域32 bits Integer變數,與一個全域大小為2*32bits Array的宣告,初值的給予.
@X = global i32 17
@Y = global i32 42
@Z = global [2 x i32*] [ i32* @X, i32* @Y ]
在初值的部份,執行可以設定初值為’Undefined Values’,定義為Undefined Values的變數就表示應用程式並不在意該值的初始化內容,指定的方式可以為
i32 undef
store i32 undef, i32 *%1
筆者以如下程式碼作為例子,來進行編譯後的LLVM BitCode檔案格式解析與對反組譯BitCode Assembly的比對.
| #include <stdio.h>
unsigned long long gW=10;
long gX;
unsigned int gY=30;
short gZ;
unsigned char gC=50;
short FuncBC(int vA)
{
int Y;
Y=((gC+gW+gX)*vA)+40;
Y*=gX+20;
printf("FuncBC:%d\n",Y);
return Y;
}
static unsigned long FuncA(int vA,int vB)
{
int Y;
gX=vA+vB;
gZ=gC+vB;
Y=gC*(gX+gY+gZ)+10;
Y*=gX+30;
gZ=FuncBC(Y);
printf("FuncA:%d\n",gZ);
return Y;
}
int main()
{
int Y=99;
int i;
for(i=0;i<99999;i++)
{
Y++;
}
Y=FuncA(Y,30);
printf("main:%d\n",Y);
return 0;
} |
編譯這段範例程式
clang -c -emit-llvm test.c -o test.bc
進行反組譯
llvm-dis test.bc
進行BitCode檔案格式分析.
llvm-bcanalyzer -dump test.bc
首先從反組譯的程式碼來看,5個全域變數轉成BitCode後的內容如下所示
| C中的變數宣告 |
BitCode產生的變數宣告 |
| unsigned long long gW=10; |
@gW = global i64 10, align 8 |
| long gX; |
@gX = common global i64 0, align 8 |
| unsigned int gY=30; |
@gY = global i32 30, align 4 |
| short gZ; |
@gZ = common global i16 0, align 2 |
| unsigned char gC=50; |
@gC = global i8 50, align 1 |
可以知道,long長度為 64bits,int長度為32bits,short長度為16bits而char長度為8bits.預設的變數為unsigned,若屬於signed的變數則會加上common.沒有給予初值的全域變數預設值為0.
如下所示,定義為static function的話會加上internal,外部函式會以declare方式宣告原型,內部函式的定義會透過define,每個函式的函式參數會以型別跟參數名稱依序定義在函式參數中.
| C中的函式宣告 |
BitCode產生的函式宣告 |
| 使用到外部呼叫printf 函式 |
declare i32 @printf(i8*, …) |
| int main() |
define i32 @main() nounwind uwtable |
| static unsigned long FuncA(int vA,int vB) |
define internal i64 @FuncA(i32 %vA, i32 %vB) nounwind uwtable |
| short FuncBC(int vA) |
define signext i16 @FuncBC(i32 %vA) nounwind uwtable |
而以函式名稱的宣告來看,在這範例中筆者有宣告如下三個函式
short FuncBC(int vA)
static unsigned long FuncA(int vA,int vB)
int main()
在編譯為 BitCode後,會依據這三個函式名稱的長度,例如main為 ‘ main:%d\0A\00′,長度為9. (main:%d 長度為 7 bytes, 加上 0x0A 跟 0×00 各 1byte就為 9 bytes.)
@.str = private unnamed_addr constant [11 x i8] c"FuncBC:%d\0A\00″, align 1
@.str2 = private unnamed_addr constant [10 x i8] c"FuncA:%d\0A\00″, align 1
@.str1 = private unnamed_addr constant [9 x i8] c"main:%d\0A\00″, align 1
提到LLVM Assembly,最值得參閱的文件為’ LLVM Language Reference Manual’,可參考的網頁位置在http://llvm.org/docs/LangRef.html . LLVM Assembly目標在於成為一個 ‘Universal IR’,也就是可以滿足讓各種程式語言對應到的Assembly Code,不管開發者使用的是C/C++,Java,Python …等等,都可以透過LLVM的Front-End前端編譯器(例如 Clang)把這些開發的Source Code轉譯為IR Assembly,以便讓LLVM本身可以把所產生的IR程式碼重新編譯到最後所要執行的處理器平台上(像是 x86,ARM或MIPS..等).
如下所示,可以先從C與編譯後的BitCode反組譯內容來做為這段落的起點
| C Code |
BitCode反組譯的結果 |
| short FuncBC(int vA)
{
int Y;
Y=((gC+gW+gX)*vA)+40;
Y*=gX+20;
printf("FuncBC:%d\n",Y);
return Y;
} |
define signext i16 @FuncBC(i32 %vA) nounwind uwtable {
%1 = alloca i32, align 4
%Y = alloca i32, align 4
store i32 %vA, i32* %1, align 4
%2 = load i8* @gC, align 1
%3 = zext i8 %2 to i64
%4 = load i64* @gW, align 8
%5 = add i64 %3, %4
%6 = load i64* @gX, align 8
%7 = add i64 %5, %6
%8 = load i32* %1, align 4
%9 = sext i32 %8 to i64
%10 = mul i64 %7, %9
%11 = add i64 %10, 40
%12 = trunc i64 %11 to i32
store i32 %12, i32* %Y, align 4
%13 = load i64* @gX, align 8
%14 = add nsw i64 %13, 20
%15 = load i32* %Y, align 4
%16 = sext i32 %15 to i64
%17 = mul nsw i64 %16, %14
%18 = trunc i64 %17 to i32
store i32 %18, i32* %Y, align 4
%19 = load i32* %Y, align 4
%20 = call i32 (i8*, …)* @printf(i8* getelementptr inbounds ([11 x i8]* @.str, i32 0, i32 0), i32 %19)
%21 = load i32* %Y, align 4
%22 = trunc i32 %21 to i16
ret i16 %22
} |
基於SSA的概念,我們可以把C語言與BitCode程式碼對應如下所示
| C Code |
BitCode反組譯的結果 |
| short FuncBC(int vA) |
define signext i16 @FuncBC(i32 %vA) nounwind uwtable |
| int Y; |
%1 = alloca i32, align 4
//宣告 int Y
%Y = alloca i32, align 4 |
| Y=((gC+gW+gX)*vA)+40 |
//把 vA儲存到 %1
store i32 %vA, i32* %1, align 4
//把 gC 儲存到 %2,並Extend為i64到%3
%2 = load i8* @gC, align 1
%3 = zext i8 %2 to i64
//把gW儲存到%4,讓%3加%4等於%5
%4 = load i64* @gW, align 8
%5 = add i64 %3, %4
//把gX儲存到 %6
%6 = load i64* @gX, align 8
//讓%6加%5等於%7
%7 = add i64 %5, %6
//讓vA等於%1儲存到%8,並Extend為i64到%9
%8 = load i32* %1, align 4
%9 = sext i32 %8 to i64
//讓%7與%9相乘把結果儲存到%10
%10 = mul i64 %7, %9
//讓%10結果加上40,並儲存到%11
%11 = add i64 %10, 40
//Truncate %11到i32 bits,結果為%12
%12 = trunc i64 %11 to i32
//最後把結果((gC+gW+gX)*vA)+40儲存在 Y
store i32 %12, i32* %Y, align 4 |
| Y*=gX+20; |
//把 gX放到 %13
%13 = load i64* @gX, align 8
//對 %13 加上20 然後儲存到%14
%14 = add nsw i64 %13, 20
//把 Y值儲存到%15
%15 = load i32* %Y, align 4
//Extend %15到i64後 儲存到%16
%16 = sext i32 %15 to i64
//把%14跟%16相乘後 儲存到%17
%17 = mul nsw i64 %16, %14
//把%17的相乘結果Truncate 後除存在%18
%18 = trunc i64 %17 to i32
//把%18儲存在 Y值
store i32 %18, i32* %Y, align 4 |
| printf("FuncBC:%d\n",Y); |
//把Y值儲存在%19
%19 = load i32* %Y, align 4
//呼叫外部函式 printf,並把 %19 當做 %d 的參數
%20 = call i32 (i8*, …)* @printf(i8* getelementptr inbounds ([11 x i8]* @.str, i32 0, i32 0), i32 %19) |
| return Y; |
//把最後Y值結果Truncate 後除存在%22
%21 = load i32* %Y, align 4
%22 = trunc i32 %21 to i16
//以%22作為最後Y值的返回結果
ret i16 %22 |
原始資料編碼 (Encoding Primitive)
BitStream的封裝會以最少的Bit數來呈現每個有意義的Byte數值,BitStream會把這些原始資料數值以Unsigned Integer 數值的方式編碼,主要的編碼方式包括固定長度整數 (Fixed Width Integer),可變長度整數 (Variable Width Integer),字元編碼(6-bit characters)或32bits方式編碼(Word Alignment)
固定長度整數 (Fixed Width Integer): 例如假設一個8 bits整數,如果要呈現1這個數字,就會以0b00000001的方式來表示. 通常固定長度整數會用來處理習知的數值,最經典的例子就是Boolean 整數,就不會用 32bits來表示,而會以固定長度整數 1bit來代表一個Boolean.
可變長度整數 (Variable Width Integer):可變長度整數,以VBR4來說,就是會以4bits為一組的方式呈現一個VBR欄位,其中最高Bit為0表示該VBR4的4bits組合尚未到結尾,若VBR4最高Bit為1表示該VBR4的數值已經結束.例如: 6 這數字二進位編碼為 0b0110,若用VBR4編碼為0b1110.或像是以8這數字二進位編碼來說為0b1000,若用VBR4編碼則為0b10010000,以每4Bits的VBR4解碼回來看就是把0b1001 最高bit忽略後 << 3 + 0b0000 也就會等於 0b1000. 以’LLVM Bitcode File Format’文件中的例子來說,0x1B ( =27) 來說,原本的二進位呈現方式為0b00011011,以可變長度整數方式來編碼的話,會以每三個bits一組來呈現,以這個例子來說就是 0b011 跟 0b011, 低位址的0b011 由於後面還有0b011要接續在一起,所以他的最高bit 會為0,表示還有接續的3bits內容,而最後的0b011 的最高bit會為1,表示已經到了結尾. 更直接一點來看就是把0x1B=27=0b00011011分拆成 24 + 3 也就是以 0b10110011 的 可變長度整數來呈現,Decode回來的方式就是 0b0011 最高bit為0,表示其後還有數值,目前值為3,而0b1011最高bit為1,表示目前數值已經到結尾,目前值為24 (0b011 << 3),所以 0b10110011解碼後的結果為 0x1B=27.
字元編碼(6-bit characters):6-bit characters encode common characters into a fixed 6-bit field. They represent the following characters with the following 6-bit values:
‘a’ .. ‘z’ — 0 .. 25
‘A’ .. ‘Z’ — 26 .. 51
’0′ .. ’9′ — 52 .. 61
‘.’ — 62
‘_’ — 63
This encoding is only suitable for encoding characters and strings that consist only of the above characters. It is completely incapable of encoding characters not in the set.
32bits方式編碼(Word Alignment):Occasionally, it is useful to emit zero bits until the bitstream is a multiple of 32 bits. This ensures that the bit position in the stream can be represented as a multiple of 32-bit words.
LLVM Bitcode File Format/BitStream Nested Block
有關LLVM Bitcode格式的說明可以參考網頁http://llvm.org/docs/BitCodeFormat.html ,而LLVM也提供一個方便解析LLVM BitCode檔案格式的工具 llvm-bcanalyzer,可用以讓開發者檢視LLVM BitCode檔案格式與對應欄位在編碼後的狀況.
LLVM的BitCode就像是Sun JVM HotSpot或是Google Android Dalvik VM ByteCode的角色一樣,都是提供一個中介的程式編碼IR(Intermediary Representation),再透過可以把這些IR程式碼格式編譯成為優化後的Native機械碼的方式,提供就像是Java JIT一樣可以跨平台但又考慮到不同處理器差異,可藉此提供接近原生程式碼編譯器(例如:GCC)的編譯效能,藉此提供一個高效率的編譯器與編譯後的指令集組合方案.
BitCode總共包含兩個部分,一個是BitStream Container Format,一個是被編碼在Container中的LLVM IR指令集編碼. BitStream Container Format就像是XML的資料結構描述方式,其中包括 Tags與Nested Structures,主要差異在於BitStream Container 為binary方式的編碼儲存,並且支援在這檔案中透過縮寫(Abbreviations)的方式來儲存相關的資料項目名稱,藉此縮小檔案的儲存空間.LLVM IR檔案中會嵌入(embedded ) Wrapper Structure讓LLVM 檔案可以被嵌入額外的資料訊息.
一個標準的BitCode檔案格式,檔案開頭前兩個Bytes會是’ 0×42, 0×43′ (=BC),接下來的兩個Bytes為 Application-Specific Magic Number,以筆者自己所編譯的BitCode檔案來說這兩個值為 ’0xC0,0xDE’,一般的BitCode識別只需要判斷前面兩個Bytes,對特定的應用程式識別來說,則需要判斷完整的四個Bytes.
透過工具llvm-bcanalyzer Dump BitCode檔案時,如果該區塊內容為空,會看到如下的區塊名稱宣告與結尾
<BLOCKINFO_BLOCK/>
若該區塊中有包括相關描述內容,則可看到如下的區塊名稱宣告與結尾
<PARAMATTR_BLOCK NumWords=25 BlockCodeSize=3>
….
</PARAMATTR_BLOCK>
每個區塊的描述都會以 <…> 的括號來區隔,並且對該區塊而言,會以 ‘/’ 作為一個區塊的結束,BitStream中的Block可以包括Nested 巢狀的內容結構,每一個Block都會包括一個依據內容屬性而訂定的特定ID.如下為以 Nested方式呈現的LLVM Block資料內容
| <FUNCTION_BLOCK NumWords=5 BlockCodeSize=4> =>最一層的Block,其中包括其它第一層以後的內容
<DECLAREBLOCKS op0=1/> =>第二層的Block,直接以 ‘/’ 收尾
<CONSTANTS_BLOCK NumWords=1 BlockCodeSize=4> =>第二層的Block,其中包括其它第二層以後的內容
<SETTYPE abbrevid=4 op0=17/> =>第三層的Block,直接以 ‘/’ 收尾
<INTEGER abbrevid=5 op0=2/> =>第三層的Block,直接以 ‘/’ 收尾
</CONSTANTS_BLOCK>
<INST_RET abbrevid=9 op0=48/> =>第二層的Block,直接以 ‘/’ 收尾
</FUNCTION_BLOCK> |
由於這些Block的定義在未來是可以根據需求擴充的,也因此在BitCode Format中會把Block 0定義為 Block Information區塊 (BLOCKINFO),用以儲存描述目前BitCode檔案中其他Block相關背景資訊的MetaData.
BitCode檔案格式內的MODULE_BLOCK區塊,是LLVM BitCode檔案格式Nested Block區塊巢狀架構最外層的Block, 檢視BitCoe Block架構與內容最好的方式就是透過指令 ‘ llvm-bcanalyzer -dump ‘,就可以把BitCode檔案格式所包含的Block資訊秀出,如下例子
[root@localhost test]# llvm-bcanalyzer -dump test.bc
| <MODULE_BLOCK NumWords=167 BlockCodeSize=3>
<BLOCKINFO_BLOCK/>
<PARAMATTR_BLOCK NumWords=4 BlockCodeSize=3>
<ENTRY op0=4294967295 op1=2199023255584/>
</PARAMATTR_BLOCK>
<TYPE_BLOCK_ID NumWords=15 BlockCodeSize=4>
<NUMENTRY op0=14/>
<INTEGER op0=8/>
<ARRAY abbrevid=9 op0=7 op1=0/>
<POINTER abbrevid=4 op0=1 op1=0/>
<INTEGER op0=32/>
<FUNCTION abbrevid=5 op0=0 op1=0 op2=3/>
<POINTER abbrevid=4 op0=4 op1=0/>
<INTEGER op0=64/>
<FUNCTION abbrevid=5 op0=1 op1=0 op2=6/>
<POINTER abbrevid=4 op0=7 op1=0/>
<POINTER abbrevid=4 op0=0 op1=0/>
<FUNCTION abbrevid=5 op0=1 op1=0 op2=3 op3=9/>
<POINTER abbrevid=4 op0=10 op1=0/>
<POINTER abbrevid=4 op0=3 op1=0/>
<VOID/>
</TYPE_BLOCK_ID>
<TRIPLE op0=120 op1=56 op2=54 op3=95 op4=54 op5=52 op6=45 op7=117 op8=110 op9=107 op10=110 op11=111 op12=119 op13=110 op14=45 op15=108 op16=105 op17=110 op18=117 op19=120 op20=45 op21=103 op22=110 op23=117/>
<DATALAYOUT op0=101 op1=45 op2=112 op3=58 op4=54 op5=52 op6=58 op7=54 op8=52 op9=58 op10=54 op11=52 op12=45 op13=105 op14=49 op15=58 op16=56 op17=58 op18=56 op19=45 op20=105 op21=56 op22=58 op23=56 op24=58 op25=56 op26=45 op27=105 op28=49 op29=54 op30=58 op31=49 op32=54 op33=58 op34=49 op35=54 op36=45 op37=105 op38=51 op39=50 op40=58 op41=51 op42=50 op43=58 op44=51 op45=50 op46=45 op47=105 op48=54 op49=52 op50=58 op51=54 op52=52 op53=58 op54=54 op55=52 op56=45 op57=102 op58=51 op59=50 op60=58 op61=51 op62=50 op63=58 op64=51 op65=50 op66=45 op67=102 op68=54 op69=52 op70=58 op71=54 op72=52 op73=58 op74=54 op75=52 op76=45 op77=118 op78=54 op79=52 op80=58 op81=54 op82=52 op83=58 op84=54 op85=52 op86=45 op87=118 op88=49 op89=50 op90=56 op91=58 op92=49 op93=50 op94=56 op95=58 op96=49 op97=50 op98=56 op99=45 op100=97 op101=48 op102=58 op103=48 op104=58 op105=54 op106=52 op107=45 op108=115 op109=48 op110=58 op111=54 op112=52 op113=58 op114=54 op115=52 op116=45 op117=102 op118=56 op119=48 op120=58 op121=49 op122=50 op123=56 op124=58 op125=49 op126=50 op127=56 op128=45 op129=110 op130=56 op131=58 op132=49 op133=54 op134=58 op135=51 op136=50 op137=58 op138=54 op139=52 op140=45 op141=83 op142=49 op143=50 op144=56/>
<GLOBALVAR op0=2 op1=1 op2=5 op3=9 op4=1 op5=0 op6=0 op7=0 op8=1/>
<FUNCTION op0=5 op1=0 op2=0 op3=0 op4=1 op5=0 op6=0 op7=0 op8=0 op9=0/>
<FUNCTION op0=8 op1=0 op2=1 op3=0 op4=0 op5=0 op6=0 op7=0 op8=0 op9=0/>
<FUNCTION op0=11 op1=0 op2=1 op3=0 op4=0 op5=0 op6=0 op7=0 op8=0 op9=0/>
<CONSTANTS_BLOCK NumWords=6 BlockCodeSize=4>
<SETTYPE abbrevid=4 op0=1/>
<CSTRING abbrevid=10 op0=88 op1=58 op2=37 op3=120 op4=104 op5=10/>
</CONSTANTS_BLOCK>
<FUNCTION_BLOCK NumWords=20 BlockCodeSize=4>
<DECLAREBLOCKS op0=1/>
<CONSTANTS_BLOCK NumWords=4 BlockCodeSize=4>
<SETTYPE abbrevid=4 op0=3/>
<NULL/>
<INTEGER abbrevid=5 op0=2/>
<SETTYPE abbrevid=4 op0=9/>
<CE_INBOUNDS_GEP op0=2 op1=0 op2=3 op3=5 op4=3 op5=5/>
</CONSTANTS_BLOCK>
<INST_ALLOCA op0=12 op1=3 op2=6 op3=3/>
<INST_ALLOCA op0=12 op1=3 op2=6 op3=3/>
<INST_STORE op0=8 op1=5 op2=0 op3=0/>
<INST_CALL op0=0 op1=0 op2=2/>
<INST_CAST abbrevid=7 op0=10 op1=3 op2=0/>
<INST_STORE op0=9 op1=11 op2=3 op3=0/>
<INST_LOAD abbrevid=4 op0=9 op1=3 op2=0/>
<INST_CALL op0=0 op1=0 op2=3 op3=7 op4=12/>
<INST_RET abbrevid=9 op0=5/>
<VALUE_SYMTAB NumWords=1 BlockCodeSize=4>
<ENTRY abbrevid=6 op0=9 op1=88/>
</VALUE_SYMTAB>
</FUNCTION_BLOCK>
<METADATA_BLOCK NumWords=7 BlockCodeSize=3>
<METADATA_KIND op0=0 op1=100 op2=98 op3=103/>
<METADATA_KIND op0=1 op1=116 op2=98 op3=97 op4=97/>
<METADATA_KIND op0=2 op1=112 op2=114 op3=111 op4=102/>
</METADATA_BLOCK>
<VALUE_SYMTAB NumWords=6 BlockCodeSize=4>
<ENTRY abbrevid=6 op0=3 op1=112 op2=114 op3=105 op4=110 op5=116 op6=102/>
<ENTRY abbrevid=6 op0=1 op1=109 op2=97 op3=105 op4=110/>
<ENTRY abbrevid=6 op0=0 op1=46 op2=115 op3=116 op4=114/>
<ENTRY abbrevid=6 op0=2 op1=102 op2=117 op3=110 op4=99 op5=66/>
</VALUE_SYMTAB>
</MODULE_BLOCK> |
如下圖所示,為LLVM BitCode檔案格式中不同區塊描述時,Nested Block的示意圖,我們可以看到最外層為MODULE_BLOCK,其下依序包括FUNCTION_BLOCK,METADATA_BLOCK…etc,在Block之中還可以在包括其他的描述Block.
Block ID 0-7預設給BitCode所定義的標準Block區塊.Blokc ID 8 以後為應用程式所特定使用的ID,像是Block ID 12為用以呈現函式實作本體(Function Body)的LLVM IR(Intermediary Representation)內容.
LLVM IR is defined with the following blocks
| Block ID |
說明 |
| 0 |
BLOCKINFO主要用以儲存描述其它Block區塊資訊的MetaData,根據文件的定義主要包括,SETBID(Code 1,[SETBID (#1), blockid]),用來表示目前描述的資訊是哪個Block ID,在BLOCKINFO中根據所要描述的Block個數,就可以有多筆SETBID宣告. DEFINE_ABBREV([DEFINE_ABBREV, ...])在BLOCKINFO中主要用以表示目前所描述Block Id的縮寫定義.BLOCKNAME (Code 2,[BLOCKNAME, ...name...])是非必要的欄位,用以記錄Block的名稱字串.SETRECORDNAME (Code 3,[SETRECORDNAME, RecordID, ...name...])是非必要欄位,會以第一個參數作為Record ID,其它部分則為這筆Record的名稱字串.
如下為筆者所舉範例的 BLOCKINFO_BLOCK Summary內容,
Block ID #0 ( BLOCKINFO_BLOCK):
Num Instances: 1
Total Size: 637b/79.62B/19W
Percent of file: 11.7096%
Num SubBlocks: 0
Num Abbrevs: 0
Num Records: 0 |
| 1 — 7 |
Block IDs 1-7 保留,用以作為未來的擴充之用. |
| 8 |
MODULE_BLOCK (=FIRST_APPLICATION_BLOCKID )
這是BitCode檔案格式中最外層的Block,在這Block內會包括整個模組內其它Block的描述內容. 根據目前的定義,MODULE_BLOCK可以包括以下的Sub BLOCK區塊內容.
1,BLOCKINFO
2,PARAMATTR_BLOCK
3,TYPE_BLOCK
4,TYPE_SYMTAB_BLOCK
5,VALUE_SYMTAB_BLOCK
6,CONSTANTS_BLOCK
7,FUNCTION_BLOCK
8,METADATA_BLOCK
如下為筆者所舉範例的 MODULE_BLOCK Summary內容,
Block ID #8 (MODULE_BLOCK):
Num Instances: 1
Total Size: 2544b/318.00B/79W
Percent of file: 46.7647%
Num SubBlocks: 7
Num Abbrevs: 1
Num Records: 6
Percent Abbrevs: 0.0000%
Record Histogram:
Count # Bits % Abv Record Kind
3 225 FUNCTION
1 69 GLOBALVAR
1 1761 DATALAYOUT
1 303 TRIPLE
除了Sub Block外, MODULE_BLOCK主要包括以下資訊內容,
[VERSION, version#] : VERSION (Code 1) 用以表示目前所支援的格式版本
[TRIPLE, ...string...]: TRIPLE (Code 2) 用以儲存Target Triple Specification 字串字元.如下為筆者環境的例子
<TRIPLE op0=120 op1=56 op2=54 op3=95 op4=54 op5=52 op6=45 op7=117 op8=110 op9=107 op10=110 op11=111 op12=119 op13=110 op14=45 op15=108 op16=105 op17=110 op18=117 op19=120 op20=45 op21=103 op22=110 op23=117/>
[DATALAYOUT, ...string...]: DATALAYOUT (Code 3)用以儲存 target datalayout Specification 字串字元.如下為筆者環境的例子
<DATALAYOUT op0=101 op1=45 op2=112 op3=58 op4=54 op5=52 op6=58 op7=54 op8=52 op9=58 op10=54 op11=52 op12=45 op13=105 op14=49 op15=58 op16=56 op17=58 op18=56 op19=45 op20=105 op21=56 op22=58 op23=56 op24=58 op25=56 op26=45 op27=105 op28=49 op29=54 op30=58 op31=49 op32=54 op33=58 op34=49 op35=54 op36=45 op37=105 op38=51 op39=50 op40=58 op41=51 op42=50 op43=58 op44=51 op45=50 op46=45 op47=105 op48=54 op49=52 op50=58 op51=54 op52=52 op53=58 op54=54 op55=52 op56=45 op57=102 op58=51 op59=50 op60=58 op61=51 op62=50 op63=58 op64=51 op65=50 op66=45 op67=102 op68=54 op69=52 op70=58 op71=54 op72=52 op73=58 op74=54 op75=52 op76=45 op77=118 op78=54 op79=52 op80=58 op81=54 op82=52 op83=58 op84=54 op85=52 op86=45 op87=118 op88=49 op89=50 op90=56 op91=58 op92=49 op93=50 op94=56 op95=58 op96=49 op97=50 op98=56 op99=45 op100=97 op101=48 op102=58 op103=48 op104=58 op105=54 op106=52 op107=45 op108=115 op109=48 op110=58 op111=54 op112=52 op113=58 op114=54 op115=52 op116=45 op117=102 op118=56 op119=48 op120=58 op121=49 op122=50 op123=56 op124=58 op125=49 op126=50 op127=56 op128=45 op129=110 op130=56 op131=58 op132=49 op133=54 op134=58 op135=51 op136=50 op137=58 op138=54 op139=52 op140=45 op141=83 op142=49 op143=50 op144=56/>
[ASM, ...string...]: ASM (Code 4)用以儲存個別的BitCode Assembly區塊,不同的Assembly區塊會以0x0A NewLine來區隔開來.
[SECTIONNAME, ...string...]: SECTIONNAME (Code 5)用以儲存不同Section的名稱字串.每一個Section名稱都會對應到一筆 SECTIONNAME資料.
其它包括[DEPLIB, ...string...] (Code 6),[GLOBALVAR, pointer type, isconst, initid, linkage, alignment, section, visibility, threadlocal] (Code 7),[FUNCTION, type, callingconv, isproto, linkage, paramattr, alignment, section, visibility, gc] (Code 8),[ALIAS, alias type, aliasee val#, linkage, visibility] (Code 9),[PURGEVALS, numvals] (Code 10),[GCNAME, ...string...] (Code 11) 都是MODULE_BLOCK中所包括的資訊,筆者在此就不一一說明,有興趣的開發者可以自行參與技術文件. |
| 9 |
PARAMATTR_BLOCK (Id=9)包含一個用以描述每個Function 參數Parameters屬性的Table.在這表格中的Entry會被FUNCTION區塊的每個Parameters欄位所參考.或是被FUNCTION區塊中的INST_INVOKE與INST_CALL的ATTR欄位所參考.
每筆在PARAMATTR_BLOCK 欄位中的資料,都會是唯一的
PARAMATTR_BLOCK中的資料格式如下
[ENTRY, paramidx0, attr0, paramidx1, attr1...]
筆者舉手中BitCode的 PARAMATTR_BLOCK為例,內容如下所示
<PARAMATTR_BLOCK NumWords=25 BlockCodeSize=3>
<ENTRY op0=4294967295 op1=2199023256096/>
<ENTRY op0=4294967295 op1=2199023255584/>
<ENTRY op0=1 op1=4294967296 op2=4294967295 op3=32/>
<ENTRY op0=4294967295 op1=32/>
<ENTRY op0=1 op1=4294967296 op2=2 op3=4294967296 op4=4294967295 op5=32/>
<ENTRY op0=0 op1=64 op2=4294967295 op3=32/>
<ENTRY op0=2 op1=4294967296 op2=4294967295 op3=32/>
</PARAMATTR_BLOCK>
如下為筆者所舉範例的 PARAMATTR_BLOCK Summary內容,
Block ID #9 (PARAMATTR_BLOCK):
Num Instances: 1
Total Size: 189b/23.62B/5W
Percent of file: 3.4743%
Num SubBlocks: 0
Num Abbrevs: 0
Num Records: 1
Percent Abbrevs: 0.0000%
Record Histogram:
Count # Bits % Abv Record Kind
1 111 ENTRY |
| 10 |
TYPE_BLOCK (ID=10) 包括了一個在這模組中所使用的Type Table列表,用以表示在這BitCode模組中所參考到的形態.除了NUMENTRY外的資料會產生一個單一型態Type的Entry記錄,包括指令集,常數,MetaData,Type Symbol Table Entry,或其他Type操作單元資料. 每筆在TYPE_BLOCK中的資料都會確保是唯一的.
筆者舉手中BitCode的 TYPE_BLOCK為例,內容如下所示
<TYPE_BLOCK_ID NumWords=35 BlockCodeSize=4>
<NUMENTRY op0=51/>
<INTEGER op0=8/>
<ARRAY abbrevid=9 op0=13 op1=0/>
<POINTER abbrevid=4 op0=1 op1=0/>
……………..
<VOID/>
<INTEGER op0=1/>
<FUNCTION abbrevid=5 op0=0 op1=0 op2=46 op3=18 op4=18 op5=7 op6=17 op7=47/>
<POINTER abbrevid=4 op0=48 op1=0/>
<METADATA/>
</TYPE_BLOCK_ID> |
| 11 |
CONSTANTS_BLOCK 主要用以儲存在這模組內或所包含的函式所使用到的常數資料,
如下為筆者所舉範例的 CONSTANTS_BLOCK Summary內容,
Block ID #11 (CONSTANTS_BLOCK):
Num Instances: 2
Total Size: 454b/56.75B/14W
Percent of file: 8.3456%
Average Size: 227.00/28.38B/7W
Tot/Avg SubBlocks: 0/0.000000e+00
Tot/Avg Abbrevs: 4/2.000000e+00
Tot/Avg Records: 7/3.500000e+00
Percent Abbrevs: 71.4286%
Record Histogram:
Count # Bits % Abv Record Kind
3 24 100.00 SETTYPE
1 52 CE_INBOUNDS_GEP
1 52 100.00 CSTRING
1 12 100.00 INTEGER
1 16 NULL |
| 12 |
FUNCTION_BLOCK,主要用以描述Function的本體.
如下為筆者所舉範例的 FUNCTION_BLOCK Summary內容,
Block ID #12 (FUNCTION_BLOCK):
Num Instances: 1
Total Size: 418b/52.25B/13W
Percent of file: 7.6838%
Num SubBlocks: 2
Num Abbrevs: 0
Num Records: 10
Percent Abbrevs: 30.0000%
Record Histogram:
Count # Bits % Abv Record Kind
2 92 INST_CALL
2 80 INST_STORE
2 80 INST_ALLOCA
1 15 100.00 INST_LOAD
1 10 100.00 INST_RET
1 18 100.00 INST_CAST
1 22 DECLAREBLOCKS |
| 13 |
TYPE_SYMTAB_BLOCK,主要用以描述Type Symbol Table. |
| 14 |
VALUE_SYMTAB_BLOCK,主要用以描述數值的Symbol Table
如下為筆者所舉範例的 VALUE_SYMTAB_BLOCK Summary內容,
Block ID #14 (VALUE_SYMTAB):
Num Instances: 2
Total Size: 338b/42.25B/10W
Percent of file: 6.2132%
Average Size: 169.00/21.12B/5W
Tot/Avg SubBlocks: 0/0.000000e+00
Tot/Avg Abbrevs: 0/0.000000e+00
Tot/Avg Records: 5/2.500000e+00
Percent Abbrevs: 100.0000%
Record Histogram:
Count # Bits % Abv Record Kind
5 210 100.00 ENTRY |
| 15 |
METADATA_BLOCK,主要用以描述MetaData項目.
如下為筆者所舉範例的 METADATA_BLOCK Summary內容,
Block ID #15 (METADATA_BLOCK):
Num Instances: 1
Total Size: 285b/35.62B/8W
Percent of file: 5.2390%
Num SubBlocks: 0
Num Abbrevs: 0
Num Records: 3
Percent Abbrevs: 0.0000%
Record Histogram:
Count # Bits % Abv Record Kind
3 195 METADATA_KIND |
| 16 |
METADATA_ATTACHMENT,主要用以記錄跟函式指令數值有關的MetaData資料. |
| 17 |
TYPE_BLOCK_ID
如下為筆者所舉範例的 TYPE_BLOCK_ID Summary內容,
Block ID #17 (TYPE_BLOCK_ID):
Num Instances: 1
Total Size: 541b/67.62B/16W
Percent of file: 9.9449%
Num SubBlocks: 0
Num Abbrevs: 6
Num Records: 15
Percent Abbrevs: 66.6667%
Record Histogram:
Count # Bits % Abv Record Kind
6 48 100.00 POINTER
3 49 100.00 FUNCTION
3 78 INTEGER
1 16 100.00 ARRAY
1 16 VOID
1 22 NUMENTRY |
|
|
基於Nested Block的架構,可以支援有從屬繼承關係的資料屬性或內容,並且可以在Block結構分析時,可以先在其上的Block Id判斷這是否為應該要處理的資料內容,而節省檔案結構分析所需的時間,例如Block ID 3的Nested Block範圍內還有Block ID 13與8,若Block ID 3是目前檔案分析所不需要參考的內容,就可以直接往其後不在Block ID 3內的Block來做分析處理,對系統運作效率上可以得到改善.
LLVM Calling Convention
Calling Convention是每一個語言在處理函式呼叫時,暫存器要如何配置與返回值要如何處理的重要原則,而一個函式呼叫Caller/Callee雙方要能順利執行,也都必須要支持一致的Calling Convention行為,而LLVM基於一個要達成跨平台高執行效率的角色,自然在Call Convention的技術支援上,也該有值得我們深入關注的部份,目前筆者所理解的LLVM主要支援以下的Calling Convention機制,
1,C Calling Convention(CCC):當函式呼叫沒有指定Calling Convention時,預設就會支援這個C Calling Convention模式.會把函式參數由右而左推到Stack中,而被呼叫端則依序透過Stack把函式參數取出. This calling convention supports varargs function calls and tolerates some mismatch in the declared prototype and implemented declaration of the function (as does normal C).
2,Fast Calling Convention (FastCC):顧名思義,這是一個會盡可能讓呼叫很快速的Calling Convention機制,在函式呼叫過程中所傳遞的函式參數會以處理器暫存器來傳遞,並無需考慮特定的 specified ABI (Application Binary Interface)標準.This calling convention does not support varargs and requires the prototype of all callees to exactly match the prototype of the function definition.
3,Cold Calling Convention: 這是一個讓不是很常被執行的函式,可以在呼叫端有效率的執行呼叫.主要的差異在於在一個函式呼叫的熱區中,有關的參數與數值都會儲存在處理器的暫存器中,如果為了一個非熱區的函式還要把這些暫存器備份到相對速度比較慢的外部記憶體,如此則會對執行效率產生影響.This calling convention does not support varargs and requires the prototype of all callees to exactly match the prototype of the function definition.
4,GHC Convetion (cc10, Glasgow Haskell Compiler): 這是一個由Glasgow Haskell編譯器所支援的Calling Convention.函式參數的傳遞主要透過處理器暫存器進行,並會Disable被呼叫端對處理器暫存器的保存與回復動作,這種呼叫方式主要應用在對執行效能有較高要求的函式呼叫中.如同 Fast Calling Convention一樣, GHC Calling Convention也支持Tail Call的Calling Convention.
在函式呼叫效能的改善上,LLVM也支援Tail Call機制,例如在x86上可讓Caller與Callee在呼叫時共用同樣的Stack Frame,例如FuncA->FuncB->FuncC的呼叫,基於Tail Call機制,可以減少其中透過 call 與重新Push Stack的成本,讓FuncA->FuncB->FuncC可以透過 Jmp與共用 Stack方式,而在FuncC結束時,也可以直接返回到FuncA讓函式呼叫的效率提高,LLVM的Tail Call支援是有平台限制的,且必須Caller與Callee的函式宣告為Fast Calling Convention或是 GHC Convention型態.
結語
法拉第曾說,“ 人心是偏向於錯誤的,人會在自己強烈需要的事情上,欺騙自己.即使尋找印證，也要符合自己的欲望“ ,筆者在整理本文時雖盡可能確保資料的正確性,然若有所遺漏也歡迎各位指正.
LLVM要介紹與說明的細節非常多,在這篇文章中筆者只選擇自己感興趣的LLVM技術加以探究,限於篇幅也難以透過一篇文章就把這麼精采的技術項目說明完畢,對LLVM Dig-in越深,也越加覺得這技術在未來發展上的潛力無窮. 隨著Google在未來把PNaCl應用到瀏覽器中,Apple也會把LLVM技術紮根於Mac OS X上,可預見的未來LLVM技術將會更加普及,LLVM不但支援跨平台,還兼顧到執行效率與所耗資源不高的特性,對於現今手機或消費性電子的軟體執行效能改善,將會有相當的助益.
People who looked at this item also looked at…
