LLVM編譯過(guò)程

image.png

LLVM編譯過(guò)程的前端(Clang)處理流程

使用一個(gè)簡(jiǎn)單的程序來(lái)簡(jiǎn)要說(shuō)明編譯過(guò)程

helloworld.c

#include <stdio.h>

int main(int argc, char const *argv[])
{
    printf("hello world!\n");
    return 0;
}

編譯過(guò)程

source code -> clang or GCC with GrogenEgg -> LLVM IR Linker -> LLVM IR optimizer -> LLVM backend(生成匯編代碼) -> assembler(生成匯編文件) -> GCC Linker(鏈接：鏈接需要的動(dòng)態(tài)庫(kù)和靜態(tài)庫(kù)，生成可執(zhí)行文件) -> program bind(綁定：通過(guò)不同的架構(gòu)，生成對(duì)應(yīng)的可執(zhí)行文件)

前端過(guò)程

C, C++, Objective-C 源碼 -> 詞法分析 -> 語(yǔ)法分析 -> 語(yǔ)義分析 -> LLVM IR 生成器

詞法分析

將源碼去掉注釋,空格,縮進(jìn)等, 剩下的文本進(jìn)行拆分成詞語(yǔ)和符號(hào)(token)

保留關(guān)鍵字和符號(hào)都會(huì)定義在一個(gè)文件中 點(diǎn)這里查看

PUNCTUATOR(l_square,            "[")
PUNCTUATOR(r_square,            "]")
PUNCTUATOR(l_paren,             "(")
PUNCTUATOR(r_paren,             ")")
KEYWORD(auto                        , KEYALL)
KEYWORD(break                       , KEYALL)
KEYWORD(case                        , KEYALL)
KEYWORD(char                        , KEYALL)

$ clang -cc1 -dump-tokens helloworld.c

命令可以將源碼拆分成對(duì)應(yīng)的語(yǔ)言的關(guān)鍵字和符號(hào),以及每個(gè)關(guān)鍵字和符號(hào)對(duì)應(yīng)的定義所在文件的起始位置

if 'if'  [StartOfLine] [LeadingSpace] Loc=<min.c:2:3>
l_paren '('  [LeadingSpace] Loc=<min.c:2:6>
identifier 'a'  Loc=<min.c:2:7>
less '<'  [LeadingSpace] Loc=<min.c:2:9>
identifier 'b'  [LeadingSpace] Loc=<min.c:2:11>

錯(cuò)誤分析 檢查代碼中的拼寫(xiě)錯(cuò)誤

預(yù)處理 在語(yǔ)義分析提取代碼的意義之前,會(huì)進(jìn)行預(yù)編譯處理,它負(fù)責(zé)將宏展開(kāi),引入包含的文件,跳過(guò)以#開(kāi)頭的代碼

語(yǔ)法分析

將語(yǔ)義分析完成的tokens(拆分成了一個(gè)個(gè)詞和符號(hào))組合在一起，形成表達(dá)式、語(yǔ)句和函數(shù)體等等.檢查組合在一起的tokens是否符合他們排版在一起的意義.但是代碼的意思還沒(méi)有進(jìn)行分析,這個(gè)需要下一步語(yǔ)義分析, 語(yǔ)法分析只要做到像語(yǔ)言分析那樣tokens對(duì)不對(duì),不需要關(guān)心具體的tokens是什么意思.語(yǔ)法分析的結(jié)果會(huì)輸出一個(gè)抽象語(yǔ)法樹(shù)(AST)

clang -fsyntax-only -Xclang -ast-dump helloworld.c

命令查看抽象語(yǔ)法樹(shù)

TranslationUnitDecl 0x7faef88166d0 <<invalid sloc>> <invalid sloc>
|-TypedefDecl 0x7faef8816c18 <<invalid sloc>> <invalid sloc> implicit __int128_t '__int128'
| `-BuiltinType 0x7faef8816940 '__int128'
|-TypedefDecl 0x7faef8816c78 <<invalid sloc>> <invalid sloc> implicit __uint128_t 'unsigned __int128'
| `-BuiltinType 0x7faef8816960 'unsigned __int128'
...

生成語(yǔ)法書(shū)的過(guò)程是根據(jù)詞法分析的結(jié)果, 查找其中的token進(jìn)行對(duì)應(yīng)的Parse方法調(diào)用, parse方法在這里, 例如找到了一個(gè)token是kw_if,就是我們代碼中寫(xiě)的if,那么會(huì)調(diào)用Parse/ParseStmt.cpp下的ParseIfStatement方法,這里面會(huì)對(duì)后面的token進(jìn)行判斷,直到查找到所有if條件判斷的代碼之后,生成一個(gè)if的節(jié)點(diǎn),作為這個(gè)if判斷的根節(jié)點(diǎn),這樣循環(huán)調(diào)用就會(huì)生成一個(gè)語(yǔ)法樹(shù),為后續(xù)語(yǔ)義分析做準(zhǔn)備.

語(yǔ)義分析

語(yǔ)義分析確保代碼不會(huì)通過(guò)符號(hào)表來(lái)違反編程語(yǔ)言的類型系統(tǒng), 符號(hào)表存儲(chǔ)著每個(gè)符號(hào)和它的類型,通過(guò)遍歷AST并從符號(hào)表中收集有關(guān)類型的信息，從而執(zhí)行解析.實(shí)際語(yǔ)義分析本身沒(méi)有遍歷整個(gè)AST, 而是在語(yǔ)法分析生成AST的時(shí)候進(jìn)行類型檢查,在DeclContext中保存了所有的Decl節(jié)點(diǎn)信息,

$ clang -fsyntax-only -Xclang -print-decl-contexts helloworld.c

命令可以打印出context

[translation unit] 0x7fe35b823cf0
        <typedef> __int128_t
        <typedef> __uint128_t
        <typedef> __NSConstantString
        <typedef> __builtin_ms_va_list
        ...

生成LLVM IR 代碼

在經(jīng)過(guò)了語(yǔ)法和語(yǔ)義分析的AST后,ParseAST方法會(huì)調(diào)用HandleTranslationUnit方法通知客戶端使用生成好的AST,如果編譯器使用了前端的CodeGenAction命令,客戶端就是BackendConsumer,它會(huì)遍歷AST按照對(duì)應(yīng)的行為生成LLVM IR代碼,遍歷行為從數(shù)頂開(kāi)始,也就是TranslationUnitDecl節(jié)點(diǎn).

生成LLVM IR代碼之后, 就完成了編譯器前端的工作,剩下的工作交給LLVM,例如優(yōu)化IR代碼,交給后端去生成目標(biāo)代碼.

IR有三種存儲(chǔ)形式:

  1. 在內(nèi)存中存儲(chǔ)(Instruction類等)
  2. 在磁盤(pán)中存儲(chǔ)的特殊編碼文件(bitcode文件)
  3. 在磁盤(pán)中存儲(chǔ)的可閱讀的文本(裝配文件)

LLVM IR

生成LLVM IR bitcode文件命令

$ clang helloworld.c -emit-llvm -c -o helloworld.bc

生成LLVM IR 可閱讀文本命令

clang helloworld.c -emit-llvm -S -c -o helloworld.ll

我們看一下可閱讀的文本

; ModuleID = 'helloworld.c'
source_filename = "helloworld.c"
target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
target triple = "x86_64-apple-macosx10.12.0"

@.str = private unnamed_addr constant [14 x i8] c"hello world!\0A\00", align 1

; Function Attrs: nounwind ssp uwtable
define i32 @main(i32, i8**) #0 {
  %3 = alloca i32, align 4
  %4 = alloca i32, align 4
  %5 = alloca i8**, align 8
  store i32 0, i32* %3, align 4
  store i32 %0, i32* %4, align 4
  store i8** %1, i8*** %5, align 8
  %6 = call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([14 x i8], [14 x i8]* @.str, i32 0, i32 0))
  ret i32 0
}

declare i32 @printf(i8*, ...) #1

attributes #0 = { nounwind ssp uwtable "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "less-precise-fpmad"="false" "no-frame-pointer-elim"="true" "no-frame-pointer-elim-non-leaf" "no-infs-fp-math"="false" "no-jump-tables"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="penryn" "target-features"="+cx16,+fxsr,+mmx,+sse,+sse2,+sse3,+sse4.1,+ssse3,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" }
attributes #1 = { "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "less-precise-fpmad"="false" "no-frame-pointer-elim"="true" "no-frame-pointer-elim-non-leaf" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="penryn" "target-features"="+cx16,+fxsr,+mmx,+sse,+sse2,+sse3,+sse4.1,+ssse3,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" }

!llvm.module.flags = !{!0}
!llvm.ident = !{!1}

!0 = !{i32 1, !"PIC Level", i32 2}
!1 = !{!"Apple LLVM version 8.1.0 (clang-802.0.42)"}

LLVM IR代碼遵循了SSA 靜態(tài)單賦值形式,所以所有的符號(hào)都只會(huì)被賦值一次,方便后續(xù)進(jìn)行查找和處理.

如代碼所示,LLVM語(yǔ)言首先定義了一個(gè)模塊, 模塊下面會(huì)有一系列的方法, 其中以%開(kāi)頭的是本地符合, @開(kāi)頭的代表全局符合. 方法定義類似C函數(shù)define i32 @main(i32, i8**) #0 {}, 其中#0代表著方法的屬性,這些屬性定義在文件結(jié)尾.

另外其實(shí)函數(shù)內(nèi)部會(huì)被標(biāo)簽分成若干個(gè)代碼塊,上面的函數(shù)因?yàn)闆](méi)有跳轉(zhuǎn),循環(huán)等.下面來(lái)看下面的int sum(int a, int b)函數(shù)的IR碼.

define i32 @sum(i32, i32) #0 {
  %3 = alloca i32, align 4
  %4 = alloca i32, align 4
  store i32 %0, i32* %3, align 4
  store i32 %1, i32* %4, align 4
  %5 = load i32, i32* %3, align 4
  %6 = load i32, i32* %4, align 4
  %7 = icmp ne i32 %5, %6
  br i1 %7, label %8, label %10

; <label>:8:                                      ; preds = %2
  %9 = load i32, i32* %4, align 4
  store i32 %9, i32* %3, align 4
  br label %10

; <label>:10:                                     ; preds = %8, %2
  %11 = load i32, i32* %3, align 4
  %12 = load i32, i32* %4, align 4
  %13 = add nsw i32 %11, %12
  ret i32 %13
}

其中 ; <label>:8:和; <label>:10:就是分支代碼.

alloca說(shuō)明了會(huì)在當(dāng)前函數(shù)的棧幀上分配空間,空間大小由i32, i64, i128等大小控制.

使用LLVM匯編語(yǔ)言編寫(xiě)一些小例子來(lái)學(xué)習(xí)LLVM是很方便的,在這里可以找到LLVM匯編語(yǔ)言的語(yǔ)法.

從LLVM IR代碼到目標(biāo)代碼/匯編代碼過(guò)程

LLVM IR代碼 -> 編譯期和鏈接期優(yōu)化 -> Instruction Selection -> Instruction Scheduling -> Register Allocation -> Instruction Scheduling -> Code Emission

Instruction Selection: 將LLVM IR在內(nèi)存中的代碼轉(zhuǎn)換成將三地址結(jié)構(gòu)轉(zhuǎn)換成DAG(有向無(wú)環(huán)圖)節(jié)點(diǎn) ,最終轉(zhuǎn)換為目標(biāo)機(jī)器的節(jié)點(diǎn)

Instruction Scheduling: 將一組虛擬寄存器引用轉(zhuǎn)換成目標(biāo)的寄存器集合

Code Emission: 生成最終的目標(biāo)機(jī)器碼或匯編代碼

Clang 靜態(tài)分析器

Clang靜態(tài)分析會(huì)在開(kāi)發(fā)過(guò)程中發(fā)現(xiàn)問(wèn)題并報(bào)告出來(lái), 不會(huì)將可檢測(cè)的bug帶到runtime中,它會(huì)在編譯之前進(jìn)行.

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書(shū)系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

  • 前面一個(gè)章節(jié)已經(jīng)簡(jiǎn)單介紹了LLVM。該章節(jié)主要介紹LLVM的編譯過(guò)程。 1. OC源文件 2. 編譯過(guò)程 命令...
    Aliv丶Zz閱讀 582評(píng)論 0贊 0
  • # iOS的編譯、鏈接工具 — Clang/LLVM 官網(wǎng)定義：[https://llvm.org/] The L...
    Tenloy閱讀 4,613評(píng)論 1贊 13
  • 在 iOS 開(kāi)發(fā)的過(guò)程中，Xcode 為我們提供了非常完善的編譯能力，正常情況下，我們只需要 Command + ...
    CoderLF閱讀 13,275評(píng)論 0贊 17
  • 前言 語(yǔ)言類型 我們有很多維度可以將計(jì)算機(jī)語(yǔ)言進(jìn)行分類，其中以編譯/執(zhí)行方式為維度，可以將計(jì)算機(jī)語(yǔ)言分為： 編譯型...
    AiLearn閱讀 2,634評(píng)論 1贊 6
  • iOS app的編譯過(guò)程 在 iOS 開(kāi)發(fā)的過(guò)程中，Xcode 為我們提供了非常完善的編譯能力，正常情況下，我們只...
    帽子和五朵玫瑰閱讀 2,974評(píng)論 0贊 17

友情鏈接更多精彩內(nèi)容