<input id="ohw05"></input>
  • <table id="ohw05"><menu id="ohw05"></menu></table>
  • <var id="ohw05"></var>
  • <code id="ohw05"><cite id="ohw05"></cite></code>
    <label id="ohw05"></label>
    <var id="ohw05"></var>
  • 程序分析與優化 - 2 控制流圖

    本章是系列文章的第二章,介紹了基于控制流圖的一些優化方法。包括DAG、值標記、相同子表達式等方法。這章的后面介紹了llvm的一些基本概念,并引導大家寫了個簡單的pass。

     

    本文中的所有內容來自學習DCC888的學習筆記或者自己理解的整理,如需轉載請注明出處。周榮華@燧原科技

     

    2 控制流圖

    2.1 基本概念

    2.1.1 中間程序表達

    優化編譯器和人類檢視代碼的角度是不一樣的。

    人類更關注源代碼,但源代碼和機器碼相差太大,另外,從工程師的角度,最好能有一種通用的方法來表示不同編程語言,并且面向不同的target硬件架構,這種通用的表達我們通常稱為程序的中間表達(Intermediate Representations),簡稱IR。針對不同層,我們經常會看到不同的IR,高級的有HLIR,低級的有LLIR,還有多級的IR,叫MLIR(Multi-Level Intermediate  representation,有時MLIR也會當做中級IR,也就是Middle Level IR的簡稱)。

     

     

     

    2.1.2 控制流圖CFG

    控制流圖是編譯器表示程序的一種方式。

    控制流圖是BB(Basic Block,基本塊)為結點,根據程序在BB之間的流動方向作為有向邊的有向圖。

    2.1.3 LLVM

    LLVM是The Low Level Virtual Machine(低級虛擬機)的簡稱,是當前各種研究領域最常用的編譯器,也是很多大公司普遍使用的編譯器。和其他編譯器一樣,LLVM分為前端(clang),中端(opt)和后端(llc)。

     

     

    llvm可以幫我們生成dot格式的CFG,例如對identity.c,可以先用clang將c源文件轉換成bc文件,然后用opt轉換成dot文件,如果環境上有dot工具,并且環境也有窗口的話(純命令行的遠程不行,由于沒有窗口可以打開,只能用dot工具將dot文件轉換成windows認識的svg或者png文件,推薦svg,因為文本可以拷貝。)

    clang -c -emit-llvm identity.c -o identity.bc
    opt –view-cfg identity.bc
    '' is not a recognized processor for this target (ignoring processor)
    WARNING: You're attempting to print out a bitcode file.
    This is inadvisable as it may cause display problems. If
    you REALLY want to taste LLVM bitcode first-hand, you
    can force output with the `-f' option.
     
    Writing '/tmp/cfgfoo-f4b44d.dot'...  done.
    Trying 'xdg-open' program... Remember to erase graph file: /tmp/cfgfoo-f4b44d.dot
    root@cse-lab-003:/home/james/workspace/bc# Error: no "view" rule for type "application/msword" passed its test case
           (for more information, add "--debug=1" on the command line)
    /usr/bin/xdg-open: 851: /usr/bin/xdg-open: www-browser: not found
    /usr/bin/xdg-open: 851: /usr/bin/xdg-open: links2: not found
    /usr/bin/xdg-open: 851: /usr/bin/xdg-open: elinks: not found
    /usr/bin/xdg-open: 851: /usr/bin/xdg-open: links: not found
    /usr/bin/xdg-open: 851: /usr/bin/xdg-open: lynx: not found
    /usr/bin/xdg-open: 851: /usr/bin/xdg-open: w3m: not found
    xdg-open: no method available for opening '/tmp/cfgfoo-f4b44d.dot'
    dot -Tsvg '/tmp/cfgfoo-f4b44d.dot' > cfgfoo-f4b44d.svg

     

    將剛剛生成的cfgfoo-f4b44d.svg拷貝到windows,用瀏覽器可以打開對應c/c++或者bc文件的CFG:

     

     

    LLVM用一種指令的序列來表達程序,這些指令的序列稱為bytecodes,或者簡稱bc。LLVM的指令又稱為LLIR,LLIR和target機器沒有綁定關系,是一種類匯編的代碼,LLVM的匯編代碼的詳細說明參見New tab (llvm.org)

    2.1.4 基本塊Basic Blocks

    基本塊是滿足下面屬性的最大的連續指令序列:

    • 控制流只能從基本塊的第一行開始執行(不能有jump執行塊中間的某行代碼)
    • 除非是基本塊的最后一條指令,否則不允許包含離開基本塊的分支或者掛機指令

    2.1.5 基本塊的首領(leader)

    • 代碼的第一行是基本塊首領
    • 任何條件或者非條件跳轉指令的目標行是基本塊首領
    • 任意條件或者非條件跳轉指令的下一行是基本塊首領

    2.1.6 基本塊的界定方法

    • 基本塊的首領是基本塊的一部分
    • 基本塊首領到下一個基本塊的首領直接的代碼,屬于該基本塊

    下面是一個簡單的例子:

    1 int fact(int n) {
    2     int ans = 1;
    3     while (n > 1) {
    4         ans *= n;
    5         n--;
    6     }
    7     return ans;
    8 }

     

    這個函數用opt生成的CFG是這樣的,opt自動把while循環涉及的2個BB標了紅色(博客園不支持直接以html格式增加svg圖,只能貼個截圖):

     

      

    2.1.7 本地優化和全局優化

    作用于在一個BB內部的優化稱為本地優化。常見的有:

    • 基于DAG的優化
    • 窺孔優化
    • 本地寄存器分配

    基于整個程序的優化稱為全局優化。

    本課程介紹的大多數優化都是全局優化。

    2.2 基于程序DAG的優化

    2.2.1 程序的有向無環圖(Directed Acyclic Graph)

    • 每個輸入值對應DAG中的一個結點
    • BB中的每行指令生成一個結點
    • 如果指令S用到了指令S1, ..., Sn中的變量,畫一條從Si, i∈{1, ..., n}到S的邊
    • BB中定義但未在BB中使用的變量稱為輸出值

     例如下面的BB:

    1 a = b + c
    2 b = a – d
    3 c = b + c
    4 d = a – d

     

     

    生成的DAG是這樣的:

     

     

     

    llvm也支持自動生成DAG,不過LLVM生成的DAG是基于llvm ir,所以如果是用高級語言寫的代碼,轉換成llvm ir的時候會有很多寄存器相關的操作,這樣DAG顯得非常大,例如上面的代碼,如果要編譯成llvmir的話,還需要封裝一個函數,變成:

    1 int dag_test(int b, int c, int d) {
    2   int a = b + c;
    3   b = a - d;
    4   c = b + c;
    5   d = a - d;
    6   return c;
    7 }

     

    保存成bb2.cc,然后用clang生成對應的llvm ir:

    clang -c -emit-llvm bb2.cc

     

    生成的llvm ir自動取名bb2.ll,內容是這樣的:

     1 ; ModuleID = 'bb2.cc'
     2 source_filename = "bb2.cc"
     3 target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
     4 target triple = "x86_64-unknown-linux-gnu"
     5  
     6 ; Function Attrs: noinline nounwind optnone uwtable
     7 define dso_local i32 @_Z8dag_testiii(i32 %0, i32 %1, i32 %2) #0 {
     8   %4 = alloca i32, align 4
     9   %5 = alloca i32, align 4
    10   %6 = alloca i32, align 4
    11   %7 = alloca i32, align 4
    12   store i32 %0, i32* %4, align 4
    13   store i32 %1, i32* %5, align 4
    14   store i32 %2, i32* %6, align 4
    15   %8 = load i32, i32* %4, align 4
    16   %9 = load i32, i32* %5, align 4
    17   %10 = add nsw i32 %8, %9
    18   store i32 %10, i32* %7, align 4
    19   %11 = load i32, i32* %7, align 4
    20   %12 = load i32, i32* %6, align 4
    21   %13 = sub nsw i32 %11, %12
    22   store i32 %13, i32* %4, align 4
    23   %14 = load i32, i32* %4, align 4
    24   %15 = load i32, i32* %5, align 4
    25   %16 = add nsw i32 %14, %15
    26   store i32 %16, i32* %5, align 4
    27   %17 = load i32, i32* %7, align 4
    28   %18 = load i32, i32* %6, align 4
    29   %19 = sub nsw i32 %17, %18
    30   store i32 %19, i32* %6, align 4
    31   %20 = load i32, i32* %5, align 4
    32   ret i32 %20
    33 }
    34  
    35 ; attributes #0 = { noinline nounwind optnone uwtable "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "frame-pointer"="all" "less-precise-fpmad"="false" "min-legal-vector-width"="0" "no-infs-fp-math"="false" "no-jump-tables"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="true" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" }
    36 attributes #0 = { nounwind uwtable "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"="x86-64" "target-features"="+fxsr,+mmx,+sse,+sse2,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" }
    37  
    38  
    39  
    40 !llvm.module.flags = !{!0}
    41 !llvm.ident = !{!1}
    42  
    43 !0 = !{i32 1, !"wchar_size", i32 4}
    44 !1 = !{!"clang version 11.1.0"}

     

     

    我這里用的是llvm11的clang,生成出來的llvm ir的module的原始attributes是35行,但這個attributes無法生成DAG,需要改成36行的attributes。

    然后用llvm的llc(注意,llvm發布版本默認是release版本的,想要看到DAG,需要自己基于源代碼編譯debug版本的,內網有我編譯好的debug版本的llvm11,在/home/.devtools/efb/clang11/bin目錄,大家可以加到自己的默認PATH里面之后直接用)將llvm ir轉換成dot文件:

    llc -view-dag-combine1-dags bb2.ll

    如果是命令行連接的linux系統,由于沒有window可以展示,會提示生成了dot文件。然后大家可以選擇將dot文件轉換成svg或者png等圖片格式,我更喜歡svg,因為里面的字符串還是字符串形式的存在,不像png完全是圖片,不方便拷貝,生成svg的命令如下,假定提示生成的dot文件名為dag._Z8dag_testiii-3c598e.dot:

    dot -Tsvg dag._Z8dag_testiii-3c598e.dot > dag._Z8dag_testiii-3c598e.dot.svg

    生成出來的dag._Z8dag_testiii-3c598e.dot.svg是文本文件,可以拷貝到支持HTML的瀏覽器中打開,效果如下(轉換成llvm ir之后的代碼,增加了很多寄存器操作,所以雖然簡單的7行代碼,生成的DAG也非常夸張):

     

     

     

    2.2.2 基于相同子表達式的優化

    回到剛才畫的簡化版DAG,我們重復畫圖過程,增加利用相同子表達式優化的方法重新畫一次:

    • 對任意輸入vi:
      • 在DAG上畫結點vi
      • 并打上in標簽
    • 按BB中的順序對每條指令v=f(v1, ..., vn):
      • 如果DAG中存在一個標簽為f的結點v',按順序包含v的所有子結點,定義v'是v的一個別名
      • 如果不存在,
        • 畫一個結點v,
        • 對每個1≤i≤n,畫一條邊(vi, v),
        • 并給v打標簽f

    按上面的畫法,到第4行的d的時候,就能發現它和第2行的b,擁有相同的子結點{d, a}并且順序一樣,所以第4行的d和第2行的b是別名關系。

     

     

     

    實際應用過程中,我們使用值標記的方法來計算相同子表達式:

    • 對DAG的每個結點關聯一個簽名(lb, v1, ..., vn),其中lb是該結點的標簽,vi (1≤i≤n)是該結點的所有子結點。
      • 將簽名中的子結點序列作為hash函數的key,
      • hash函數的值就是該變量的值標記
    • 當有新結點加入到DAG時,
      • 先根據它的所有子結點計算出一個hash值,如果已經存在,我們直接返回該hash值對應對應的索引。
      • 如果找不到,則創建該結點。

    對上面的DAG,我們生成的值標記的hash表如下,最后一列很顯然是不必要的:

    表達式
    b
    c
    d
    a=b+c
    b=a-d
    c=b+c
    d=a-d
    hash key b c d (+, 1, 2) (-, 4, 3) (+, 5, 2) (-, 4, 3)
    value number 1 2 3 4 5 6 5

    2.2.3 CSE定理

    為了找到更多的CSE(Common SubExpressions),需要制定更多的定理:

    交換律:對+運算符,x+y和y+x等同。

    特性轉換:x<y一般轉換成t=x-y; t<0

    結合律: 對

    a=b+c; t=c+d; e=t+b;

    等同于:

    a=b+c; e=a+d;

    算術特性轉換:

    x+0=0+x=x; 

    x*1=1*x=x;

    x-0=x;

    x/1=x;

    計算強度降維轉換:

    x2=x*x;

    2*x=x+x;

    x/2=x*0.5;

    常量折疊:在編譯階段計算表達式的值,并將表達式替換成對應的值。

    2.2.4 死代碼刪除

    死代碼(Dead Code)是滿足下面2個條件的DAG結點:

    • 該結點沒有子結點;
    • 該結點不是輸出結點。
    • 上面的刪除過程可以通過多輪迭代實現。

    2.3 窺孔優化(Peephole Optimizations)

    • 優化器分析一個指令的集合
    • 每次只分析比較小的固定窗口內的指令
    • 這個固定窗口不斷往下滑動
    • 當窗口內發現某種可以優化的模式,則執行該優化

    窺孔優化的實例:

    • 冗余的load和store指令刪除
    • 冗余分支指令的刪除
    • 冗余調整指令的刪除
    • 計算強度降維:除法 > 乘法 > 減法 > 移位/加法
    • 機器特有屬性:addl > incl

    2.4 局部寄存器分配

    局部寄存器分配的偽代碼類似這樣:

     1 allocate(Block b) {
     2   for (Inst i : b.instructions()) {
     3     for (Operand o : i.operands()) {
     4       if (o is in memory m) {
     5         r = find_reg(i) assign r to o add "r = load m" before i
     6       }
     7     }
     8     for (Operand o : i.operands()) {
     9       if (i is the last use of o) {
    10         return the register bound to o to the list of free registers
    11       }
    12     }
    13     v = i.definition r = find_reg(i) assign r to v
    14   }
    15 }

     

     

    溢出(spilling):大多數情況下寄存器是有限的,需要在寄存器不夠用的情況下將之前保存在寄存器里面的內容映射回內存,這個操作叫做溢出。

    find_reg函數的偽代碼是這樣的:

     1 find_reg(i) {
     2   if there is free register r
     3       return r
     4   else
     5       let v be the latest variable to be used after i, that is in a register
     6   if v does not have a memory slot
     7       let m be a fresh memory slot
     8   else
     9       let m be the memory slot assigned to v
    10   add "store v m" right after the definition of v
    11   return r
    12 }

     

     

    可以看出局部寄存器的分配,主要依賴在變量使用前插入"r = load m"指令,并在變量使用完之后插入"store v m"來實現。

    但當寄存器不足的時候,要選擇將哪個變量從寄存器溢出到內存里面?

    伯克利算法策略:溢出時通常選擇離溢出點最遠的變量,也稱為LRU(Least Recently Used,最近最少使用算法)。該算法在各種緩存溢出過程中廣泛采用,包括頁面置換,cache miss等過程。

    對只有2個寄存器的機器,要實現下面的計算:

    1 a = load m0
    2 b = load m1
    3 c = a + b
    4 d = 4 * c
    5 e = b + 1
    6 f = e + a
    7 g = d / e
    8 h = f - g
    9 ret h

     

     

    實際完成局部寄存器分配之后的代碼和各變量在寄存器,內存里面的生命周期是這樣的:

     

     

     

    上面的算法在這次運算中其實不是最優解。如果在"c=a+b"計算之前不把b踢出寄存器,而是在"d=4*c"計算中讓d復用c的寄存器,就可以少store一次b并且少load一次b。

    但在1998年就有科學家證明了,找到每次分配寄存器的最優解是NP完全問題(NP-completeness,是"nondeterministic polynomial-time completeness"的簡稱,也就是不確定的多項式時間完全問題,其中不確定性指的是不確定圖靈機,是數學上形式化描述的暴力搜索算法。對確定性的算法,只需要進行一次迭代就能得出結果,對不確定的算法,需要遍歷整個空間。)。也就是說,如果遍歷所有分配選項,當然是能找出一個最優解的,但時間消耗非常大,所以各個類似領域都是用LRU作為較優解。

    2.5 LLVM簡介

    2.5.1 LLVM是一種編譯框架結構

    llvm有很多編譯工具:

     1 root@e6db4f256fba:/home/.devtools/efb/clang11/bin# cd /home/.devtools/efb/clang11/bin/
     2 root@e6db4f256fba:/home/.devtools/efb/clang11/bin# ls
     3 bugpoint                  ld64.lld         llvm-gsymutil                   llvm-rtdyld
     4 c-index-test              llc              llvm-ifs                        llvm-size
     5 clang                     lld              llvm-install-name-tool          llvm-special-case-list-fuzzer
     6 clang++                   lld-link         llvm-isel-fuzzer                llvm-split
     7 clang-11                  lldb             llvm-itanium-demangle-fuzzer    llvm-stress
     8 clang-apply-replacements  lldb-argdumper   llvm-jitlink                    llvm-strings
     9 clang-change-namespace    lldb-instr       llvm-lib                        llvm-strip
    10 clang-check               lldb-server      llvm-link                       llvm-symbolizer
    11 clang-cl                  lldb-vscode      llvm-lipo                       llvm-tblgen
    12 clang-cpp                 lli              llvm-lit                        llvm-undname
    13 clang-doc                 llvm-addr2line   llvm-locstats                   llvm-xray
    14 clang-extdef-mapping      llvm-ar          llvm-lto                        llvm-yaml-numeric-parser-fuzzer
    15 clang-format              llvm-as          llvm-lto2                       mlir-cpu-runner
    16 clang-include-fixer       llvm-bcanalyzer  llvm-mc                         mlir-edsc-builder-api-test
    17 clang-move                llvm-c-test      llvm-mca                        mlir-linalg-ods-gen
    18 clang-offload-bundler     llvm-cat         llvm-microsoft-demangle-fuzzer  mlir-opt
    19 clang-offload-wrapper     llvm-cfi-verify  llvm-ml                         mlir-reduce
    20 clang-query               llvm-config      llvm-modextract                 mlir-sdbm-api-test
    21 clang-refactor            llvm-cov         llvm-mt                         mlir-tblgen
    22 clang-rename              llvm-cvtres      llvm-nm                         mlir-translate
    23 clang-reorder-fields      llvm-cxxdump     llvm-objcopy                    modularize
    24 clang-scan-deps           llvm-cxxfilt     llvm-objdump                    obj2yaml
    25 clang-tblgen              llvm-cxxmap      llvm-opt-fuzzer                 opt
    26 clang-tidy                llvm-diff        llvm-opt-report                 pp-trace
    27 clangd                    llvm-dis         llvm-pdbutil                    sancov
    28 diagtool                  llvm-dlltool     llvm-profdata                   sanstats
    29 dsymutil                  llvm-dwarfdump   llvm-ranlib                     scan-build
    30 find-all-symbols          llvm-dwp         llvm-rc                         scan-view
    31 git-clang-format          llvm-elfabi      llvm-readelf                    verify-uselistorder
    32 hmaptool                  llvm-exegesis    llvm-readobj                    wasm-ld
    33 ld.lld                    llvm-extract     llvm-reduce                     yaml2obj

     

     

    2.5.2 使用opt進行機器無關優化,輸入輸出都是bc或者llvm ir

     1 root@e6db4f256fba:/home/.devtools/efb/clang11/bin# opt --help
     2 OVERVIEW: llvm .bc -> .bc modular optimizer and analysis printer
     3  
     4 USAGE: opt [options] <input bitcode file>
     5  
     6 OPTIONS:
     7  
     8 Color Options:
     9  
    10   --color                                            - Use colors in output (default=autodetect)
    11  
    12 General options:
    13  
    14   --Emit-dtu-info                                    - Enable DTU info section generation
    15   --O0                                               - Optimization level 0. Similar to clang -O0
    16   --O1                                               - Optimization level 1. Similar to clang -O1
    17   --O2                                               - Optimization level 2. Similar to clang -O2
    18   --O3                                               - Optimization level 3. Similar to clang -O3
    19   --Os                                               - Like -O2 with extra optimizations for size. Similar to clang -Os
    20   --Oz                                               - Like -Os but reduces code size further. Similar to clang -Oz
    21   -S                                                 - Write output as LLVM assembly
    22   --aarch64-neon-syntax=<value>                      - Choose style of NEON code to emit from AArch64 backend:
    23     =generic                                         -   Emit generic NEON assembly
    24     =apple                                           -   Emit Apple-style NEON assembly
    25   --addrsig                                          - Emit an address-significance table
    26   --analyze                                          - Only perform analysis, no optimization
    27   --asm-show-inst                                    - Emit internal instruction representation to assembly file
    28   --atomic-counter-update-promoted                   - Do counter update using atomic fetch add  for promoted counters only
    29   Optimizations available:
    30       --X86CondBrFolding                                - X86CondBrFolding
    31       --aa                                              - Function Alias Analysis Results
    32       --aa-eval                                         - Exhaustive Alias Analysis Precision Evaluator
    33       --aarch64-a57-fp-load-balancing                   - AArch64 A57 FP Load-Balancing
    34       --aarch64-branch-targets                          - AArch64 Branch Targets
    35       --aarch64-ccmp                                    - AArch64 CCMP Pass
    36       --aarch64-collect-loh                             - AArch64 Collect Linker Optimization Hint (LOH)
    37       --aarch64-condopt                                 - AArch64 CondOpt Pass
    38       --aarch64-copyelim                                - AArch64 redundant copy elimination pass
    39       --aarch64-dead-defs                               - AArch64 Dead register definitions
    40       --aarch64-expand-pseudo                           - AArch64 pseudo instruction expansion pass
    41       --aarch64-fix-cortex-a53-835769-pass              - AArch64 fix for A53 erratum 835769
    42       --aarch64-jump-tables                             - AArch64 compress jump tables pass
    43       --aarch64-ldst-opt                                - AArch64 load / store optimization pass
    44       --aarch64-local-dynamic-tls-cleanup               - AArch64 Local Dynamic TLS Access Clean-up
    45       --aarch64-prelegalizer-combiner                   - Combine AArch64 machine instrs before legalization
    46       --aarch64-promote-const                           - AArch64 Promote Constant Pass
    47       --aarch64-simd-scalar                             - AdvSIMD Scalar Operation Optimization
    48       --aarch64-simdinstr-opt                           - AArch64 SIMD instructions optimization pass
    49       --aarch64-speculation-hardening                   - AArch64 speculation hardening pass
    50       --aarch64-stack-tagging-pre-ra                    - AArch64 Stack Tagging PreRA Pass
    51       --aarch64-stp-suppress                            - AArch64 Store Pair Suppression
    52       --adce                                            - Aggressive Dead Code Elimination
    53 …………

     

     

    不同優化級別的優化使能的優化選項:

    1 root@e6db4f256fba:/home/.devtools/efb/clang11/bin# llvm-as < /dev/null | opt -O0 -disable-output -debug-pass=Arguments
    2 Pass Arguments:  -tti -verify -ee-instrument
    3 Pass Arguments:  -targetlibinfo -tti -assumption-cache-tracker -profile-summary-info -forceattrs -basiccg -always-inline -verify
    4 root@e6db4f256fba:/home/.devtools/efb/clang11/bin# llvm-as < /dev/null | opt -O3 -disable-output -debug-pass=Arguments
    5 Pass Arguments:  -tti -tbaa -scoped-noalias -assumption-cache-tracker -targetlibinfo -verify -ee-instrument -simplifycfg -domtree -sroa -early-cse -lower-expect
    6 Pass Arguments:  -targetlibinfo -tti -tbaa -scoped-noalias -assumption-cache-tracker -profile-summary-info -forceattrs -inferattrs -domtree -callsite-splitting -ipsccp -called-value-propagation -attributor -globalopt -domtree -mem2reg -deadargelim -domtree -basicaa -aa -loops -lazy-branch-prob -lazy-block-freq -opt-remark-emitter -instcombine -simplifycfg -basiccg -globals-aa -prune-eh -inline -functionattrs -argpromotion -domtree -sroa -basicaa -aa -memoryssa -early-cse-memssa -speculative-execution -basicaa -aa -lazy-value-info -jump-threading -correlated-propagation -simplifycfg -domtree -aggressive-instcombine -basicaa -aa -loops -lazy-branch-prob -lazy-block-freq -opt-remark-emitter -instcombine -libcalls-shrinkwrap -loops -branch-prob -block-freq -lazy-branch-prob -lazy-block-freq -opt-remark-emitter -pgo-memop-opt -basicaa -aa -loops -lazy-branch-prob -lazy-block-freq -opt-remark-emitter -tailcallelim -simplifycfg -reassociate -domtree -basicaa -aa -memoryssa -loops -loop-simplify -lcssa-verification -lcssa -scalar-evolution -loop-rotate -licm -loop-unswitch -simplifycfg -domtree -basicaa -aa -loops -lazy-branch-prob -lazy-block-freq -opt-remark-emitter -instcombine -loop-simplify -lcssa-verification -lcssa -scalar-evolution -indvars -loop-idiom -loop-deletion -loop-unroll -mldst-motion -phi-values -basicaa -aa -memdep -lazy-branch-prob -lazy-block-freq -opt-remark-emitter -gvn -phi-values -basicaa -aa -memdep -memcpyopt -sccp -demanded-bits -bdce -basicaa -aa -lazy-branch-prob -lazy-block-freq -opt-remark-emitter -instcombine -lazy-value-info -jump-threading -correlated-propagation -basicaa -aa -phi-values -memdep -dse -basicaa -aa -memoryssa -loops -loop-simplify -lcssa-verification -lcssa -scalar-evolution -licm -postdomtree -adce -simplifycfg -domtree -basicaa -aa -loops -lazy-branch-prob -lazy-block-freq -opt-remark-emitter -instcombine -barrier -elim-avail-extern -basiccg -rpo-functionattrs -globalopt -globaldce -basiccg -globals-aa -domtree -float2int -lower-constant-intrinsics -domtree -basicaa -aa -memoryssa -loops -loop-simplify -lcssa-verification -lcssa -scalar-evolution -loop-rotate -loop-accesses -lazy-branch-prob -lazy-block-freq -opt-remark-emitter -loop-distribute -branch-prob -block-freq -scalar-evolution -basicaa -aa -loop-accesses -demanded-bits -lazy-branch-prob -lazy-block-freq -opt-remark-emitter -inject-tli-mappings -loop-vectorize -loop-simplify -scalar-evolution -basicaa -aa -loop-accesses -lazy-branch-prob -lazy-block-freq -loop-load-elim -basicaa -aa -lazy-branch-prob -lazy-block-freq -opt-remark-emitter -instcombine -simplifycfg -domtree -loops -scalar-evolution -basicaa -aa -demanded-bits -lazy-branch-prob -lazy-block-freq -opt-remark-emitter -slp-vectorizer -opt-remark-emitter -instcombine -loop-simplify -lcssa-verification -lcssa -scalar-evolution -loop-unroll -lazy-branch-prob -lazy-block-freq -opt-remark-emitter -instcombine -memoryssa -loop-simplify -lcssa-verification -lcssa -scalar-evolution -licm -lazy-branch-prob -lazy-block-freq -opt-remark-emitter -transform-warning -alignment-from-assumptions -strip-dead-prototypes -globaldce -constmerge -domtree -loops -branch-prob -block-freq -loop-simplify -lcssa-verification -lcssa -basicaa -aa -scalar-evolution -block-freq -loop-sink -lazy-branch-prob -lazy-block-freq -opt-remark-emitter -instsimplify -div-rem-pairs -simplifycfg -verify
    7 Pass Arguments:  -domtree
    8 Pass Arguments:  -targetlibinfo -domtree -loops -branch-prob -block-freq
    9 Pass Arguments:  -targetlibinfo -domtree -loops -branch-prob -block-freq

     

     

    2.5.3 pass

    pass是llvm特有的概念。Llvm的paas框架是llvm系統中的重要部分,也是編譯器中最有趣的部分,llvm通過應用一連串的pass來達到優化效果。部分pass為編譯器提供轉換或者優化功能,而這些pass又依賴其他pass提供這些轉換和優化需要的分析結果。Pass是llvm提供的編譯代碼的一種結構化的技術。

    所有llvm的pass都是Pass類的子類,它們重載繼承自Pass類的虛擬函數,根據pass的功能需要,可以選擇繼承自ModulePassCallGraphSCCPassFunctionPassLoopPassRegionPass, 或者 BasicBlockPass 類,這些類相對于最上層的Pass類,提供了更多上下文信息。

    2.5.4 虛擬寄存器分配mem2reg

    例如下面這個函數:

    1 int main() {
    2   int c1 = 17;
    3   int c2 = 25;
    4   int c3 = c1 + c2;
    5   printf("Value = %d\n", c3);
    6 }

     

     

    編譯生成的llvm ir是這樣的(省略了一些屬性,只顯示了函數體):

     1 clang -S -emit-llvm mem2reg.cc
     2 llvm-dis mem2reg.bc
     3 cat mem2reg.ll
     4 ; ModuleID = 'mem2reg.bc'
     5 source_filename = "mem2reg.cc"
     6 target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
     7 target triple = "x86_64-unknown-linux-gnu"
     8  
     9 @.str = private unnamed_addr constant [12 x i8] c"Value = %d\0A\00", align 1
    10  
    11 ; Function Attrs: noinline norecurse optnone uwtable
    12 define dso_local i32 @main() #0 {
    13   %1 = alloca i32, align 4
    14   %2 = alloca i32, align 4
    15   %3 = alloca i32, align 4
    16   store i32 17, i32* %1, align 4
    17   store i32 25, i32* %2, align 4
    18   %4 = load i32, i32* %1, align 4
    19   %5 = load i32, i32* %2, align 4
    20   %6 = add nsw i32 %4, %5
    21   store i32 %6, i32* %3, align 4
    22   %7 = load i32, i32* %3, align 4
    23   %8 = call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([12 x i8], [12 x i8]* @.str, i64 0, i64 0), i32 %7)
    24   ret i32 0
    25 }
    26  
    27 declare dso_local i32 @printf(i8*, ...) #1
    28  
    29 attributes #0 = { noinline norecurse optnone uwtable "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "frame-pointer"="all" "less-precise-fpmad"="false" "min-legal-vector-width"="0" "no-infs-fp-math"="false" "no-jump-tables"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="true" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" }
    30 attributes #1 = { "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "frame-pointer"="all" "less-precise-fpmad"="false" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="true" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" }
    31  
    32 !llvm.module.flags = !{!0}
    33 !llvm.ident = !{!1}
    34  
    35 !0 = !{i32 1, !"wchar_size", i32 4}
    36 !1 = !{!"clang version 11.1.0"}

     

     

    直接對上面生成的bc文件跑opt,發現優化之后的llvm ir和優化前的llvm ir幾乎完全一樣,沒有達到預期的優化效果。問了一圈,有同事懷疑是屬性里面的optnone 再使壞,刪掉之后確實能正常優化了。

    下面是優化之后的llvm ir和優化過程中運行的命令,可以看出main函數從之前的8行指令優化成了2行。在寄存器足夠的情況下,僅僅mem2reg這個優化pass的效果也是非常可觀的。

    1 root@e6db4f256fba:~/DCC888# opt --mem2reg mem2reg.ll > mem2reg_after.bc
    2 root@e6db4f256fba:~/DCC888# llvm-dis mem2reg_after.bc
    3 root@e6db4f256fba:~/DCC888# cat mem2reg_after.ll
    4 ; Function Attrs: noinline norecurse uwtable
    5 define dso_local i32 @main() #0 {
    6   %1 = add nsw i32 17, 25
    7   %2 = call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([12 x i8], [12 x i8]* @.str, i64 0, i64 0), i32 %1)
    8   ret i32 0
    9 }

     

     

    2.5.5 常量折疊constprop

    經過一輪常量折疊后main函數代碼可以精簡到1行,下面是命令和優化后的llvm ir。

    1 root@e6db4f256fba:~/DCC888# opt --constprop mem2reg_after.ll > mem2reg_constprop.bc
    2 root@e6db4f256fba:~/DCC888# llvm-dis mem2reg_constprop.bc
    3 root@e6db4f256fba:~/DCC888# cat mem2reg_constprop.ll
    4 define dso_local i32 @main() #0 {
    5   %1 = call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([12 x i8], [12 x i8]* @.str, i64 0, i64 0), i32 42)
    6   ret i32 0
    7 }

     

     

    2.5.6 通用子表達式early-cse

    再來一個CSE的例子,源代碼如下:

     1 root@e6db4f256fba:~/DCC888# cat cse.cc
     2 #include<stdio.h>
     3 int main(int argc, char** argv) {
     4     char c1 = argc + 1;
     5     char c2 = argc - 1;
     6     char c3 = c1 + c2;
     7     char c4 = c1 + c2;
     8     char c5 = c4 * 4;
     9     if (argc % 2)
    10         printf("Value = %d\n", c3);
    11     else
    12         printf("Value = %d\n", c5);
    13 }

     

     

    先秀一下沒做CSE之前的llir(llvm ir可以簡寫成llir,省去不關心的各種attributes,但自己跑的時候注意把optnone的attribute刪除掉再跑):

    root@e6db4f256fba:~/DCC888# clang -S -emit-llvm cse.cc
    root@e6db4f256fba:~/DCC888# opt --mem2reg cse.ll > cse_mem2reg.bc
    root@e6db4f256fba:~/DCC888# llvm-dis cse_mem2reg.bc
    root@e6db4f256fba:~/DCC888# cat cse_mem2reg.ll
    define dso_local i32 @main(i32 %0, i8** %1) #0 {
      %3 = add nsw i32 %0, 1
      %4 = trunc i32 %3 to i8
      %5 = sub nsw i32 %0, 1
      %6 = trunc i32 %5 to i8
      %7 = sext i8 %4 to i32
      %8 = sext i8 %6 to i32
      %9 = add nsw i32 %7, %8
      %10 = trunc i32 %9 to i8
      %11 = sext i8 %4 to i32
      %12 = sext i8 %6 to i32
      %13 = add nsw i32 %11, %12
      %14 = trunc i32 %13 to i8
      %15 = sext i8 %14 to i32
      %16 = mul nsw i32 %15, 4
      %17 = trunc i32 %16 to i8
      %18 = srem i32 %0, 2
      %19 = icmp ne i32 %18, 0
      br i1 %19, label %20, label %23
     
    20:                                               ; preds = %2
      %21 = sext i8 %10 to i32
      %22 = call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([12 x i8], [12 x i8]* @.str, i64 0, i64 0), i32 %21)
      br label %26
     
    23:                                               ; preds = %2
      %24 = sext i8 %17 to i32
      %25 = call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([12 x i8], [12 x i8]* @.str, i64 0, i64 0), i32 %24)
      br label %26
     
    26:                                               ; preds = %23, %20
      ret i32 0
    }

     

     

    經過cse優化之后的結果,注意,優化前的7~10和11~14行的代碼一樣,被優化成一份了:

     1 root@e6db4f256fba:~/DCC888# opt --early-cse cse_mem2reg.ll | llvm-dis
     2 ; Function Attrs: noinline norecurse uwtable
     3 define dso_local i32 @main(i32 %0, i8** %1) #0 {
     4   %3 = add nsw i32 %0, 1
     5   %4 = trunc i32 %3 to i8
     6   %5 = sub nsw i32 %0, 1
     7   %6 = trunc i32 %5 to i8
     8   %7 = sext i8 %4 to i32
     9   %8 = sext i8 %6 to i32
    10   %9 = add nsw i32 %7, %8
    11   %10 = trunc i32 %9 to i8
    12   %11 = sext i8 %10 to i32
    13   %12 = mul nsw i32 %11, 4
    14   %13 = trunc i32 %12 to i8
    15   %14 = srem i32 %0, 2
    16   %15 = icmp ne i32 %14, 0
    17   br i1 %15, label %16, label %18
    18  
    19 16:                                               ; preds = %2
    20   %17 = call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([12 x i8], [12 x i8]* @.str, i64 0, i64 0), i32 %11)
    21   br label %21
    22  
    23 18:                                               ; preds = %2
    24   %19 = sext i8 %13 to i32
    25   %20 = call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([12 x i8], [12 x i8]* @.str, i64 0, i64 0), i32 %19)
    26   br label %21
    27  
    28 21:                                               ; preds = %18, %16
    29   ret i32 0
    30 }

     

     

    上面代碼里面的trunc指令負責把大的數據類型轉換成小的數據類型,因為函數入參是int,但計算時需要轉換成char,但計算時編譯器又會自動把它擴展成int32,這時又需要調用sext指令,加法運算完又要調用trunc指令轉回char。

    這就是為何經常有人建議,除非涉及協議對接,要不然不要用char當做整數處理,如果編譯器不做優化的話,性能比直接用int會差很多。

    2.5.7 自己動手寫一個llvm的pass

    寫pass之前需要先了解一下llvm對代碼的抽象。llvm代碼抽象的最上層是Module,每個Module由一個或者多個Function組成,再往下依次是BasicBlock,Instruction,每條Instruction由一個OpCode和一個或者多個個operand組成。

    我們的pass可以是針對下面任意一個層次的處理。

     

     

    原ppt里面的寫pass的流程是llvm2的,當前比較新的版本已經不可用,下面的例子是基于llvm11驗證通過,參考了官網的例子https://www.llvm.org/docs/WritingAnLLVMPass.html#quick-start-writing-hello-world

    例如要寫一個基于Function的Pass,需要繼承自FunctionPass類,重載基于該類的runOnFunction虛函數。下面是一個計算函數內操作符個數的Pass:

     1 #define DEBUG_TYPE "opCounter"
     2 #include "llvm/IR/Function.h"
     3 #include "llvm/Pass.h"
     4 #include "llvm/Support/raw_ostream.h"
     5 #include <map>
     6 using namespace llvm;
     7 namespace {
     8 struct CountOp : public FunctionPass {
     9   std::map<std::string, int> opCounter;
    10   static char ID;
    11   CountOp() : FunctionPass(ID) {}
    12   virtual bool runOnFunction(Function &F) {
    13     errs() << "Function " << F.getName() << '\n';
    14     for (Function::iterator bb = F.begin(), e = F.end(); bb != e; ++bb) {
    15       for (BasicBlock::iterator i = bb->begin(), e = bb->end(); i != e; ++i) {
    16         if (opCounter.find(i->getOpcodeName()) == opCounter.end()) {
    17           opCounter[i->getOpcodeName()] = 1;
    18         } else {
    19           opCounter[i->getOpcodeName()] += 1;
    20         }
    21       }
    22     }
    23     std::map<std::string, int>::iterator i = opCounter.begin();
    24     std::map<std::string, int>::iterator e = opCounter.end();
    25     while (i != e) {
    26       errs() << i->first << ": " << i->second << "\n";
    27       i++;
    28     }
    29     errs() << "\n";
    30     opCounter.clear();
    31     return false;
    32   }
    33 };
    34 } // namespace
    35 char CountOp::ID = 0;
    36 static RegisterPass<CountOp> X("opCounter", "Counts opcodes per functions");

     

     

    通過runOnFunction的入參就是Function,通過遍歷Function找到BasicBlock,通過遍歷BasicBlock找到Instruction,獲得Instruction的OpcodeName,并增加累加功能。函數遍歷完之后,使用errors()錯誤輸出流將計算的操作符的次數打印出來。

    每個Pass都會定義一個ID,看大家代碼都是統一賦值成0,看起來不可思議,實際上傳給FunctionPass的是一個引用,這個引用再作為引用傳遞給FunctionPass的父類Pass,Pass將ID的地址作傳給PassID,最終實現用每個類里面定義的ID的地址作為類的真實ID的效果。下面貼的代碼為了表達這個傳遞關系,省略了其他無關代碼:

    282 class FunctionPass : public Pass {
    283 public:
    384   explicit FunctionPass(char &pid) : Pass(PT_Function, pid) {}
    78 class Pass {
    79   AnalysisResolver *Resolver = nullptr;  // Used to resolve analysis
    80   const void *PassID;
    81   PassKind Kind;
    82  
    83  
    84 public:
    85   explicit Pass(PassKind K, char &pid) : PassID(&pid), Kind(K) {}

     

     

    將上面寫好的CountOp.cpp拷貝到llvm/lib/Transforms/CountOP目錄下面,并將llvm/lib/Transforms/Hello/CMakeLists.txt拷貝到本目錄下,將其中的Hello替換成我們新創建的CountOP:

     1 # If we don't need RTTI or EH, there's no reason to export anything
     2 # from the hello plugin.
     3 if( NOT LLVM_REQUIRES_RTTI )
     4   if( NOT LLVM_REQUIRES_EH )
     5     set(LLVM_EXPORTED_SYMBOL_FILE ${CMAKE_CURRENT_SOURCE_DIR}/CountOP.exports)
     6   endif()
     7 endif()
     8  
     9 if(WIN32 OR CYGWIN)
    10   set(LLVM_LINK_COMPONENTS Core Support)
    11 endif()
    12  
    13 add_llvm_library( LLVMCountOP MODULE BUILDTREE_ONLY
    14   CountOP.cpp
    15  
    16   DEPENDS
    17   intrinsics_gen
    18   PLUGIN_TOOL
    19   opt
    20   )

     

     

    修改llvm/lib/Transforms/CMakeLists.txt,增加一行“add_subdirectory(CountOP)”,然后啟動llvm的編譯。編譯完會在當前build目錄下面生成lib/LLVMCountOP.so庫,將這個庫拷貝到當前代碼目錄,執行下面命令就可以看到這個pass的執行結果:

    1 root@e6db4f256fba:~/DCC888# opt -load LLVMCountOP.so --opCounter mem2reg.bc -disable-output
    2 Function main
    3 add: 1
    4 alloca: 3
    5 call: 1
    6 load: 3
    7 ret: 1
    8 store: 3

     

    posted @ 2022-05-04 12:01  周榮華  閱讀(536)  評論(0編輯  收藏  舉報
    国产美女a做受大片观看