很多C 的初學者都會有這麼一個疑問, .Net程式代碼是如何被機器載入執行的? 最簡單的解答是, C 會通過編譯器(CodeDom, Roslyn)編譯成IL代碼, 然後CLR(.Net Framework, .Net Core, Mono)會把這些IL代碼編譯成目標機器的機器代碼並執行. 相信大多 ...

很多C#的初學者都會有這麼一個疑問, .Net程式代碼是如何被機器載入執行的?
最簡單的解答是, C#會通過編譯器(CodeDom, Roslyn)編譯成IL代碼,
然後CLR(.Net Framework, .Net Core, Mono)會把這些IL代碼編譯成目標機器的機器代碼並執行.
相信大多數的C#的書籍都是這樣一筆帶過的.
這篇和下篇文章會深入講解JIT的具體工作流程,
和前面的GC篇一樣, 實現中的很多細節都是無標準文檔的, 用搜索引擎不會找到它們相關的資料.

因為內容相當多, 講解JIT的文章將會分為兩篇.
第一篇是入門篇, 看過這個系列之前的文章和CLR via C#, 瞭解一些編譯原理的都可以看的明白.
第二篇是詳解篇, 會分析JIT的具體實現流程, 演算法和數據結構.

這篇的內容是基於CoreCLR 1.1.0分析的, 其他CLR中的實現不一定和這篇分析的實現完全一樣.
微軟最近提供了一篇JIT入門文檔,
儘管裡面寫的相當潦草但是仍有很大的參考價值, 推薦同時參考這個文檔.

JIT的作用介紹

相信很多C#程式員都知道, 我們編寫的C#代碼在經過編譯後得出的exe或dll裡面包含的並不是機器代碼,
而是一種中間代碼, 也稱為MSIL(簡稱IL).
MSIL可以在不同的系統或者平臺上執行, CLR中執行它們的模塊就是這篇要講的JIT.

如圖所示

CoreCLR中的JIT代號是RyuJIT, RyuJIT可以把MSIL翻譯為X86, X64或者ARM的機器代碼.

使用JIT的好處有

同一個程式集可以在不同平臺上運行
減少編譯時間(編譯到MSIL的時間比編譯到機器代碼的時間要短很多)
可以根據目標平臺選擇最優的代碼(例如只在支持AVX指令的CPU使用AVX指令)

使用JIT的壞處有

增加運行負擔
不能執行過多的優化(否則將會增加更多的運行負擔)
部分平臺上無法使用(例如iOS)

為瞭解決這些壞處而出現的技術有NGEN, AOT, CoreRT等, 但是使用它們以後同時也就失去了使用JIT的好處.

JIT的流程總覽

以下的圖片來源於微軟提供的JIT入門文檔:

總體上來說RyuJIT可以分為兩個部分.
前端: 也就是圖上的第一行, 負責把MSIL轉換為JIT中的內部表現(IR)並且執行優化.
後端: 也就是圖上的第二行, 負責準備生產機器代碼, 分配寄存器等與平臺相關的處理.

具體的步驟可以分為:

前端的步驟有(導入MSIL和優化):

後端的步驟有(平臺相關的處理):

JIT的流程實例

只看上面的圖你可能會一頭霧水, 我們來看看實際的流程.
為了更容易理解這裡我使用的是Debug模式.
以下的內容來源於CoreCLR的輸出, 設置環境變數"COMPlus_JitDump=Main"並且使用Debug版的CoreCLR即可得到.

首先是C#代碼, 非常簡單的迴圈3次並且輸出到控制台.

using System;
using System.Runtime.InteropServices;

namespace ConsoleApplication
{
    public class Program
    {
        public static void Main(string[] args)
        {
            for (int x = 0; x < 3; ++x)
            {
                Console.WriteLine(x);
            }
        }
    }
}

經過編譯後會生成以下的IL, 下麵我標記了運行堆棧的狀態和簡單的註釋.

IL to import:
IL_0000  00                nop
IL_0001  16                ldc.i4.0                  ; 運行堆棧 [ 0 ]
IL_0002  0a                stloc.0                   ; 運行堆棧 [ ], 保存到本地變數0 (x = 0)
IL_0003  2b 0d             br.s         13 (IL_0012) ; 跳轉到IL_0012
IL_0005  00                nop
IL_0006  06                ldloc.0                   ; 運行堆棧 [ x ]
IL_0007  28 0c 00 00 0a    call         0xA00000C    ; 運行堆棧 [ ], 調用Console.WriteLine, 這裡的0xA00000C是token
IL_000c  00                nop
IL_000d  00                nop         
IL_000e  06                ldloc.0                   ; 運行堆棧 [ x ]
IL_000f  17                ldc.i4.1                  ; 運行堆棧 [ x, 1 ]
IL_0010  58                add                       ; 運行堆棧 [ x+1 ]
IL_0011  0a                stloc.0                   ; 運行堆棧 [ ], 保存到本地變數0 (x = x + 1)
IL_0012  06                ldloc.0                   ; 運行堆棧 [ x ]
IL_0013  19                ldc.i4.3                  ; 運行堆棧 [ x, 3 ]
IL_0014  fe 04             clt                       ; 運行堆棧 [ x<3 ]
IL_0016  0b                stloc.1                   ; 運行堆棧 [ ], 保存到本地變數1 (tmp = x < 3)
IL_0017  07                ldloc.1                   ; 運行堆棧 [ tmp ]
IL_0018  2d eb             brtrue.s     -21 (IL_0005); 運行堆棧 [ ], 如果tmp為true則跳轉到IL_0005
IL_001a  2a                ret                       ; 從函數返回

RyuJIT的前端會把IL導入為中間表現(IR), 如下

Importing BB02 (PC=000) of 'ConsoleApplication.Program:Main(ref)'
    [ 0]   0 (0x000) nop

               [000004] ------------             *  stmtExpr  void  (IL 0x000...  ???)
               [000003] ------------             \--*  no_op     void  

    [ 0]   1 (0x001) ldc.i4.0 0
    [ 1]   2 (0x002) stloc.0

               [000008] ------------             *  stmtExpr  void  (IL 0x001...  ???)
               [000005] ------------             |  /--*  const     int    0
               [000007] -A----------             \--*  =         int   
               [000006] D------N----                \--*  lclVar    int    V01 loc0         

    [ 0]   3 (0x003) br.s

               [000010] ------------             *  stmtExpr  void  (IL 0x003...  ???)
               [000009] ------------             \--*  nop       void  

Importing BB03 (PC=005) of 'ConsoleApplication.Program:Main(ref)'
    [ 0]   5 (0x005) nop

               [000025] ------------             *  stmtExpr  void  (IL 0x005...  ???)
               [000024] ------------             \--*  no_op     void  

    [ 0]   6 (0x006) ldloc.0
    [ 1]   7 (0x007) call 0A00000C

               [000029] ------------             *  stmtExpr  void  (IL 0x006...  ???)
               [000027] --C-G-------             \--*  call      void   System.Console.WriteLine
               [000026] ------------ arg0           \--*  lclVar    int    V01 loc0         

    [ 0]  12 (0x00c) nop

               [000031] ------------             *  stmtExpr  void  (IL 0x00C...  ???)
               [000030] ------------             \--*  no_op     void  

    [ 0]  13 (0x00d) nop

               [000033] ------------             *  stmtExpr  void  (IL 0x00D...  ???)
               [000032] ------------             \--*  no_op     void  

    [ 0]  14 (0x00e) ldloc.0
    [ 1]  15 (0x00f) ldc.i4.1 1
    [ 2]  16 (0x010) add
    [ 1]  17 (0x011) stloc.0

               [000039] ------------             *  stmtExpr  void  (IL 0x00E...  ???)
               [000035] ------------             |     /--*  const     int    1
               [000036] ------------             |  /--*  +         int   
               [000034] ------------             |  |  \--*  lclVar    int    V01 loc0         
               [000038] -A----------             \--*  =         int   
               [000037] D------N----                \--*  lclVar    int    V01 loc0         

Importing BB04 (PC=018) of 'ConsoleApplication.Program:Main(ref)'
    [ 0]  18 (0x012) ldloc.0
    [ 1]  19 (0x013) ldc.i4.3 3
    [ 2]  20 (0x014) clt
    [ 1]  22 (0x016) stloc.1

               [000017] ------------             *  stmtExpr  void  (IL 0x012...  ???)
               [000013] ------------             |     /--*  const     int    3
               [000014] ------------             |  /--*  <         int   
               [000012] ------------             |  |  \--*  lclVar    int    V01 loc0         
               [000016] -A----------             \--*  =         int   
               [000015] D------N----                \--*  lclVar    int    V02 loc1         

    [ 0]  23 (0x017) ldloc.1
    [ 1]  24 (0x018) brtrue.s

               [000022] ------------             *  stmtExpr  void  (IL 0x017...  ???)
               [000021] ------------             \--*  jmpTrue   void  
               [000019] ------------                |  /--*  const     int    0
               [000020] ------------                \--*  !=        int   
               [000018] ------------                   \--*  lclVar    int    V02 loc1         

Importing BB05 (PC=026) of 'ConsoleApplication.Program:Main(ref)'
    [ 0]  26 (0x01a) ret

               [000042] ------------             *  stmtExpr  void  (IL 0x01A...  ???)
               [000041] ------------             \--*  return    void

我們可以看到IL被分成了好幾組(BB02~BB05), 這裡的BB是BasicBlock的縮寫,
一個BasicBlock中有多個語句(Statement), 一個語句就是一棵樹(GenTree).

上面的文本對應了以下的結構(又稱HIR結構):

BasicBlock: 保存了一組語句, BasicBlock內原則上跳轉指令只會出現在最後一個語句
Statement: 一個語句就是一棵樹, 在內部Statement也是一個GenTree的子類(GenTreeStmt)
GenTree: 組成樹的節點, 有很多不同的類型例如GenTreeUnOp(unary op), GenTreeIntCon(int constant)

有人可能會好奇為什麼上面的BasicBlock從02開始, 這是因為01是內部用的block, 裡面會保存函數開始時運行的內部處理.

接下來RyuJIT的前端會不斷的修改HIR結構, 做出各種變形和優化:

Trees before IR Rationalize

-------------------------------------------------------------------------------------------------------------------------------------
BBnum         descAddr ref try hnd preds           weight   [IL range]      [jump]      [EH region]         [flags]
-------------------------------------------------------------------------------------------------------------------------------------
BB01 [00000000024701F8]  1                              1   [???..???)                                     i internal label target 
BB02 [0000000002473350]  1       BB01                   1   [???..???)-> BB04 ( cond )                     internal 
BB03 [0000000002473460]  1       BB02                   0.5 [???..???)                                     internal 
BB04 [0000000002473240]  2       BB02,BB03              1   [???..???)                                     i internal label target 
BB05 [0000000002470470]  1       BB04                   1   [000..005)-> BB07 (always)                     i 
BB06 [0000000002470580]  1       BB07                   1   [005..012)                                     i label target gcsafe bwd 
BB07 [0000000002470690]  2       BB05,BB06              1   [012..01A)-> BB06 ( cond )                     i label target bwd 
BB08 [00000000024707A0]  1       BB07                   1   [01A..01B)        (return)                     i 
-------------------------------------------------------------------------------------------------------------------------------------

------------ BB01 [???..???), preds={} succs={BB02}

***** BB01, stmt 1
     (  0,  0) [000001] ------------             *  stmtExpr  void  (IL   ???...  ???)
N001 (  0,  0) [000000] ------------             \--*  nop       void  

------------ BB02 [???..???) -> BB04 (cond), preds={BB01} succs={BB03,BB04}

***** BB02, stmt 2
     (  9, 16) [000055] ------------             *  stmtExpr  void  (IL   ???...  ???)
N005 (  9, 16) [000054] ------------             \--*  jmpTrue   void  
N003 (  1,  1) [000045] ------------                |  /--*  const     int    0
N004 (  7, 14) [000046] J------N----                \--*  ==        int   
N002 (  5, 12) [000044] ------------                   \--*  indir     int   
N001 (  3, 10) [000043] ------------                      \--*  const(h)  long   0x7f95ea870610 token

------------ BB03 [???..???), preds={BB02} succs={BB04}

***** BB03, stmt 3
     ( 14,  5) [000056] ------------             *  stmtExpr  void  (IL   ???...  ???)
N001 ( 14,  5) [000047] --C-G-?-----             \--*  call help void   HELPER.CORINFO_HELP_DBG_IS_JUST_MY_CODE

------------ BB04 [???..???), preds={BB02,BB03} succs={BB05}

------------ BB05 [000..005) -> BB07 (always), preds={BB04} succs={BB07}

***** BB05, stmt 4
     (  1,  1) [000004] ------------             *  stmtExpr  void  (IL 0x000...0x000)
N001 (  1,  1) [000003] ------------             \--*  no_op     void  

***** BB05, stmt 5
     (  1,  3) [000008] ------------             *  stmtExpr  void  (IL 0x001...0x002)
N001 (  1,  1) [000005] ------------             |  /--*  const     int    0
N003 (  1,  3) [000007] -A------R---             \--*  =         int   
N002 (  1,  1) [000006] D------N----                \--*  lclVar    int    V01 loc0         

***** BB05, stmt 6
     (  0,  0) [000010] ------------             *  stmtExpr  void  (IL 0x003...0x003)
N001 (  0,  0) [000009] ------------             \--*  nop       void  

------------ BB06 [005..012), preds={BB07} succs={BB07}

***** BB06, stmt 7
     (  1,  1) [000025] ------------             *  stmtExpr  void  (IL 0x005...0x005)
N001 (  1,  1) [000024] ------------             \--*  no_op     void  

***** BB06, stmt 8
     ( 15,  7) [000029] ------------             *  stmtExpr  void  (IL 0x006...0x00C)
N005 ( 15,  7) [000027] --C-G-------             \--*  call      void   System.Console.WriteLine
N003 (  1,  1) [000026] ------------ arg0 in rdi    \--*  lclVar    int    V01 loc0         

***** BB06, stmt 9
     (  1,  1) [000031] ------------             *  stmtExpr  void  (IL 0x00C...  ???)
N001 (  1,  1) [000030] ------------             \--*  no_op     void  

***** BB06, stmt 10
     (  1,  1) [000033] ------------             *  stmtExpr  void  (IL 0x00D...0x00D)
N001 (  1,  1) [000032] ------------             \--*  no_op     void  

***** BB06, stmt 11
     (  3,  3) [000039] ------------             *  stmtExpr  void  (IL 0x00E...0x011)
N002 (  1,  1) [000035] ------------             |     /--*  const     int    1
N003 (  3,  3) [000036] ------------             |  /--*  +         int   
N001 (  1,  1) [000034] ------------             |  |  \--*  lclVar    int    V01 loc0         
N005 (  3,  3) [000038] -A------R---             \--*  =         int   
N004 (  1,  1) [000037] D------N----                \--*  lclVar    int    V01 loc0         

------------ BB07 [012..01A) -> BB06 (cond), preds={BB05,BB06} succs={BB08,BB06}

***** BB07, stmt 12
     ( 10,  6) [000017] ------------             *  stmtExpr  void  (IL 0x012...0x016)
N002 (  1,  1) [000013] ------------             |     /--*  const     int    3
N003 (  6,  3) [000014] ------------             |  /--*  <         int   
N001 (  1,  1) [000012] ------------             |  |  \--*  lclVar    int    V01 loc0         
N005 ( 10,  6) [000016] -A------R---             \--*  =         int   
N004 (  3,  2) [000015] D------N----                \--*  lclVar    int    V02 loc1         

***** BB07, stmt 13
     (  7,  6) [000022] ------------             *  stmtExpr  void  (IL 0x017...0x018)
N004 (  7,  6) [000021] ------------             \--*  jmpTrue   void  
N002 (  1,  1) [000019] ------------                |  /--*  const     int    0
N003 (  5,  4) [000020] J------N----                \--*  !=        int   
N001 (  3,  2) [000018] ------------                   \--*  lclVar    int    V02 loc1         

------------ BB08 [01A..01B) (return), preds={BB07} succs={}

***** BB08, stmt 14
     (  0,  0) [000042] ------------             *  stmtExpr  void  (IL 0x01A...0x01A)
N001 (  0,  0) [000041] ------------             \--*  return    void

上面的內容目前可以不用理解, 我貼出來只是為了說明HIR結構經過了轉換和變形.

接下來就會進入RyuJIT的後端, RyuJIT的後端會根據HIR結構生成LIR結構:

Trees after IR Rationalize

-------------------------------------------------------------------------------------------------------------------------------------
BBnum         descAddr ref try hnd preds           weight   [IL range]      [jump]      [EH region]         [flags]
-------------------------------------------------------------------------------------------------------------------------------------
BB01 [00000000024701F8]  1                              1   [???..???)                                     i internal label target LIR 
BB02 [0000000002473350]  1       BB01                   1   [???..???)-> BB04 ( cond )                     internal LIR 
BB03 [0000000002473460]  1       BB02                   0.5 [???..???)                                     internal LIR 
BB04 [0000000002473240]  2       BB02,BB03              1   [???..???)                                     i internal label target LIR 
BB05 [0000000002470470]  1       BB04                   1   [000..005)-> BB07 (always)                     i LIR 
BB06 [0000000002470580]  1       BB07                   1   [005..012)                                     i label target gcsafe bwd LIR 
BB07 [0000000002470690]  2       BB05,BB06              1   [012..01A)-> BB06 ( cond )                     i label target bwd LIR 
BB08 [00000000024707A0]  1       BB07                   1   [01A..01B)        (return)                     i LIR 
-------------------------------------------------------------------------------------------------------------------------------------

------------ BB01 [???..???), preds={} succs={BB02}
N001 (  0,  0) [000000] ------------                nop       void  


------------ BB02 [???..???) -> BB04 (cond), preds={BB01} succs={BB03,BB04}
N001 (  3, 10) [000043] ------------       t43 =    const(h)  long   0x7f95ea870610 token

                                                 /--*  t43    long   
N002 (  5, 12) [000044] ------------       t44 = *  indir     int   

N003 (  1,  1) [000045] ------------       t45 =    const     int    0

                                                 /--*  t44    int    
                                                 +--*  t45    int    
N004 (  7, 14) [000046] J------N----       t46 = *  ==        int   

                                                 /--*  t46    int    
N005 (  9, 16) [000054] ------------             *  jmpTrue   void  


------------ BB03 [???..???), preds={BB02} succs={BB04}
N001 ( 14,  5) [000047] --C-G-?-----                call help void   HELPER.CORINFO_HELP_DBG_IS_JUST_MY_CODE


------------ BB04 [???..???), preds={BB02,BB03} succs={BB05}

------------ BB05 [000..005) -> BB07 (always), preds={BB04} succs={BB07}
     (  1,  1) [000004] ------------                il_offset void   IL offset: 0

N001 (  1,  1) [000003] ------------                no_op     void  

     (  1,  3) [000008] ------------                il_offset void   IL offset: 1

N001 (  1,  1) [000005] ------------        t5 =    const     int    0

                                                 /--*  t5     int    
N003 (  1,  3) [000007] DA----------             *  st.lclVar int    V01 loc0         

     (  0,  0) [000010] ------------                il_offset void   IL offset: 3

N001 (  0,  0) [000009] ------------                nop       void  


------------ BB06 [005..012), preds={BB07} succs={BB07}
     (  1,  1) [000025] ------------                il_offset void   IL offset: 5

N001 (  1,  1) [000024] ------------                no_op     void  

     ( 15,  7) [000029] ------------                il_offset void   IL offset: 6

N003 (  1,  1) [000026] ------------       t26 =    lclVar    int    V01 loc0         

                                                 /--*  t26    int    arg0 in rdi
N005 ( 15,  7) [000027] --C-G-------             *  call      void   System.Console.WriteLine

     (  1,  1) [000031] ------------                il_offset void   IL offset: 12

N001 (  1,  1) [000030] ------------                no_op     void  

     (  1,  1) [000033] ------------                il_offset void   IL offset: 13

N001 (  1,  1) [000032] ------------                no_op     void  

     (  3,  3) [000039] ------------                il_offset void   IL offset: 14

N001 (  1,  1) [000034] ------------       t34 =    lclVar    int    V01 loc0         

N002 (  1,  1) [000035] ------------       t35 =    const     int    1

                                                 /--*  t34    int    
                                                 +--*  t35    int    
N003 (  3,  3) [000036] ------------       t36 = *  +         int   

                                                 /--*  t36    int    
N005 (  3,  3) [000038] DA----------             *  st.lclVar int    V01 loc0         


------------ BB07 [012..01A) -> BB06 (cond), preds={BB05,BB06} succs={BB08,BB06}
     ( 10,  6) [000017] ------------                il_offset void   IL offset: 18

N001 (  1,  1) [000012] ------------       t12 =    lclVar    int    V01 loc0         

N002 (  1,  1) [000013] ------------       t13 =    const     int    3

                                                 /--*  t12    int    
                                                 +--*  t13    int    
N003 (  6,  3) [000014] ------------       t14 = *  <         int   

                                                 /--*  t14    int    
N005 ( 10,  6) [000016] DA----------             *  st.lclVar int    V02 loc1         

     (  7,  6) [000022] ------------                il_offset void   IL offset: 23

N001 (  3,  2) [000018] ------------       t18 =    lclVar    int    V02 loc1         

N002 (  1,  1) [000019] ------------       t19 =    const     int    0

                                                 /--*  t18    int    
                                                 +--*  t19    int    
N003 (  5,  4) [000020] J------N----       t20 = *  !=        int   

                                                 /--*  t20    int    
N004 (  7,  6) [000021] ------------             *  jmpTrue   void  


------------ BB08 [01A..01B) (return), preds={BB07} succs={}
     (  0,  0) [000042] ------------                il_offset void   IL offset: 26

N001 (  0,  0) [000041] ------------                return    void

我們可以看到在LIR結構里, BasicBlock包含的是GenTree節點的有序列表, 原來是樹結構的節點現在都連成了一串.
LIR結構跟最終生成的機器代碼結構非常的相似.

接下來RyuJIT的後端會給LIR結構中的GenTree節點分配寄存器, 並且根據LIR結構生成彙編指令列表:

Instructions as they come out of the scheduler

G_M21556_IG01:        ; func=00, offs=000000H, size=0016H, gcrefRegs=00000000 {}, byrefRegs=00000000 {}, byref, nogc <-- Prolog IG
IN001b: 000000 55                   push     rbp
IN001c: 000001 4883EC10             sub      rsp, 16
IN001d: 000005 488D6C2410           lea      rbp, [rsp+10H]
IN001e: 00000A 33C0                 xor      rax, rax
IN001f: 00000C 8945F4               mov      dword ptr [rbp-0CH], eax
IN0020: 00000F 8945F0               mov      dword ptr [rbp-10H], eax
IN0021: 000012 48897DF8             mov      gword ptr [rbp-08H], rdi

G_M21556_IG02:        ; func=00, offs=000016H, size=0014H, gcrefRegs=00000000 {}, byrefRegs=00000000 {}, byref, isz
IN0001: 000016 48B8100687EA957F0000 mov      rax, 0x7F95EA870610
IN0002: 000020 833800               cmp      dword ptr [rax], 0
IN0003: 000023 7405                 je       SHORT G_M21556_IG03
[02479BA8] ptr arg pop  0
IN0004: 000025 E8D6E0B578           call     CORINFO_HELP_DBG_IS_JUST_MY_CODE

G_M21556_IG03:        ; func=00, offs=00002AH, size=0009H, gcrefRegs=00000000 {}, byrefRegs=00000000 {}, byref, isz
IN0005: 00002A 90                   nop      
IN0006: 00002B 33FF                 xor      edi, edi
IN0007: 00002D 897DF4               mov      dword ptr [rbp-0CH], edi
IN0008: 000030 90                   nop      
IN0009: 000031 EB13                 jmp      SHORT G_M21556_IG05

G_M21556_IG04:        ; func=00, offs=000033H, size=0013H, gcrefRegs=00000000 {}, byrefRegs=00000000 {}, byref
IN000a: 000033 90                   nop      
IN000b: 000034 8B7DF4               mov      edi, dword ptr [rbp-0CH]
[02479BC0] ptr arg pop  0
IN000c: 000037 E864F7FFFF           call     System.Console:WriteLine(int)
IN000d: 00003C 90                   nop      
IN000e: 00003D 90                   nop      
IN000f: 00003E 8B45F4               mov      eax, dword ptr [rbp-0CH]
IN0010: 000041 FFC0                 inc      eax
IN0011: 000043 8945F4               mov      dword ptr [rbp-0CH], eax

G_M21556_IG05:        ; func=00, offs=000046H, size=0019H, gcrefRegs=00000000 {}, byrefRegs=00000000 {}, byref, isz
IN0012: 000046 8B7DF4               mov      edi, dword ptr [rbp-0CH]
IN0013: 000049 83FF03               cmp      edi, 3
IN0014: 00004C 400F9CC7             setl     dil
IN0015: 000050 400FB6FF             movzx    rdi, dil
IN0016: 000054 897DF0               mov      dword ptr [rbp-10H], edi
IN0017: 000057 8B7DF0               mov      edi, dword ptr [rbp-10H]
IN0018: 00005A 85FF                 test     edi, edi
IN0019: 00005C 75D5                 jne      SHORT G_M21556_IG04
IN001a: 00005E 90                   nop      

G_M21556_IG06:        ; func=00, offs=00005FH, size=0006H, epilog, nogc, emitadd
IN0022: 00005F 488D6500             lea      rsp, [rbp]
IN0023: 000063 5D                   pop      rbp
IN0024: 000064 C3                   ret

最後Emitter把這些指令編碼成機器代碼就完成了JIT的編譯工作.

JIT的數據結構

以下的圖片來源於微軟提供的JIT入門文檔:

第一張是HIR的數據結構

第二張是LIR的數據結構

第三張是CoreCLR中實際的數據結構(HIR和LIR會共用GenTree節點).

JIT的觸發

在相當多的.NET書籍中都提到過, CLR中的JIT是懶編譯的, 那麼具體是如何實現的?
JIT針對每個函數都會提供一個"樁"(Stub), 第一次調用時會觸發JIT編譯, 第二次調用時會跳轉到第一次的編譯結果.
流程參考下圖:

JIT之前的樁(例子)

0x7fff7c21f5a8: e8 2b 6c fe ff     callq  0x7fff7c2061d8

JIT之後的樁(例子)

0x7fff7c21f5a8: e9 a3 87 3a 00     jmp    0x7fff7c5c7d50

具體的彙編代碼分析我會在下一篇中給出, 目前你只需要理解"樁"起到的是一個路由的作用.

目前的CoreCLR觸發了JIT編譯後, 會在當前線程中執行JIT編譯.
如果多個線程同時調用了一個未JIT的函數, 其中一個線程會執行編譯, 其他線程會等待編譯完成.
CoreCLR會對正在JIT編譯的函數分配一個線程鎖(ListLockEntry)來實現這一點.

JIT會為準備的函數創建一個Compiler實例, Compiler實例儲存了BasicBlock列表等編譯時需要的信息.
一個正在編譯的函數對應一個Compiler實例, 函數編譯後Compiler實例會被銷毀.

接下來我會對JIT的各項步驟進行一個簡單的說明.

Frontend

Importer

Importer負責讀取和解析IL(byte array), 並根據IL生成JIT使用的內部表現IR(BasicBlock, Statement, GenTree).
BasicBlock會根據它們的跳轉類型連接成一個圖(graph).

第一個BasicBlock是內部使用的, 會添加一些函數進入的初始化處理(但不要和彙編中的prolog混淆).

下圖是Importer的實例:

Inliner

如果函數符合內聯的條件, 則Inliner會把函數的IR嵌入到它的調用端函數(callsite), 並且對本地變數和參數進行修整.
執行內聯後接下來的步驟將在調用端函數中完成.

內聯的條件有很多, 判斷邏輯也相當的複雜, 這裡我只列出一部分:

未開啟優化時不內聯
函數是尾調用則不內聯
函數是虛函數時不內斂
函數是helper call時不內聯
函數是indirect call時(編譯時無法確認地址)時不內聯
未設置COMPlus_AggressiveInlining環境變數且函數在catch或者filter中時不內聯
之前嘗試內聯失敗時不內聯
同步函數(CORINFO_FLG_SYNCH)不內聯
函數需要安全檢查(CORINFO_FLG_SECURITYCHECK)時不內聯
如果函數有例外處理器則不內聯
函數無內容(大小=0)則不內聯
函數參數是vararg時不內聯
函數中的本地變數數量大於MAX_INL_LCLS(32)時不內聯
函數中的參數數量大於MAX_INL_LCLS時不內聯
函數中的本地變數(包含內部變數)有512個以上, 則標記內聯失敗
如果出現迴圈inline, 例如A inline B, B inline A, 則標記內聯失敗
如果層數大於InlineStrategy::IMPLEMENTATION_MAX_INLINE_DEPTH(1000), 則標記內聯失敗
如果函數有返回類型但無返回表達式(包含throw), 則標記內聯失敗
如果初始化內聯函數所在的class失敗, 則標記內聯失敗
如果內聯函數估算體積 > 調用函數的指令體積 * 繫數(DetermineMultiplier), 則標記內聯失敗
等等

下圖是Inliner的實例:

Morph

Morph會對Importer導入的HIR進行變形, 這個步驟包含了很多處理, 這裡我只列出一部分:

在第一個BasicBlock插入內部使用的代碼
刪除無法到達的BasicBlock(死代碼)
如果有多個return block並且需要合併, 則生成一個新的return block並且讓原來的block指向它
對本地的struct變數進行promotion, 把各個欄位提取出來作為單獨的變數
對各個節點進行修改
- 標記節點是否需要檢查null
- 標記節點是否需要檢查邊界
- 根據節點添加斷言
  - 例如a = 5即可斷言a等於5, b = new X()即可斷言b != null
- 需要時添加cast
- 對於平臺不支持的操作轉換為helper call, 例如(1f+1f)轉換為float_add(1f, 1f)
- 進行簡單的優化, 例如(常量+常量)轉換為(常量)
- 轉換一些表達式, 例如(1 op 2 == 0)轉換為(1 (rev op) 2)
- 如果表達式帶有溢出檢查(checked), 則添加對應的throw block, 只添加一次
- 添加檢查數組邊界的代碼
- 尾調用(tail call)優化
- 等等

經過Morph變形後的HIR將會包含更多信息, 對IL中隱式的處理(例如邊界檢查和溢出檢查)也添加了顯式的代碼(GenTree).

下圖是Morph的實例:

圖中的comma表示的是逗號式, 例如(X(), 123)這個式會先評價X()然後結果使用123,
上圖中的comma會先把數組保存到一個臨時變數, 執行邊界檢查, 然後再訪問數組中的元素然後輸出到控制台.

Flowgraph Analysis

Flowgraph Analysis會對BasicBlock進行流程分析,
找出BasicBlock有哪些前任block(predecessor)和後繼block(successor), 並且標記BasicBlock的引用次數.

如果一個block是多個block的跳轉目標, 則這個block有多個preds,
如果一個block的跳轉類型是jtrue(條件成立時跳轉到目標block, 否則到下一個block), 則這個block有兩個succs.

並且計算DOM(dominator)樹,
例如出現 A -> B, A -> C, B -> D, C -> D, 則D的dominator不是B或C而是A, 表示執行D必須經過A,
參考Wikipedia和論文.

例如在這張圖中:

block 1的preds是[], succs是[2]
block 2的preds是[1, 5], succs是[3, 4, 6]
block 3的preds是[2], succs是[5]
block 4的preds是[2], succs是[5]
block 5的preds是[3, 4], succs是[2]
block 6的preds是[2], succs是[]

計算出來的DOM(dominator)樹為:

然後會根據流程分析的結果進行一些優化:

優化 while 到 do while:
優化前 jmp test; loop: ...; test: cond; jtrue loop;
優化後 cond; jfalse done; loop: ...; test: cond; jtrue loop; done: ...;

優化迴圈中數組的邊界檢查:
優化前 for (var x = 0; x < a.Length; ++x) { b[x] = a[x]; },
優化後

if (x < a.Length) {
    if ((a != null && b != null) && (a.Length <= b.Length)) {
        do {
            var tmp = a[x]; // no bounds check
            b[x] = tmp; // no bounds check
            x = x + 1;
        } while (x < a.Length);
    } else {
        do {
            var tmp = a[x];
            b[x] = tmp;
            x = x + 1;
        } while (x < a.Length);
    }
}

優化次數是常量的迴圈:
優化前 for (var x = 0; x < 3; ++x) { DoSomething(); }
優化後 DoSomething(); DoSomething(); DoSomething();
註意迴圈次數過多或者迴圈中的代碼過長則不會執行這項優化.

LclVar sorting & Tree Ordering

這個步驟會標記函數中本地變數的引用計數, 並且按引用計數排序本地變數表.
然後會對tree的運行運行順序執行標記, 例如 a() + b(), 會標記a()先於b()執行.
(與C, C++不同, .Net中對操作參數的運行順序有很嚴格的規定, 例如a+b和f(a, b)的運行順序都是已規定的)

經過運行順序標記後其實就已經形成了LIR結構.
LIR結構中無語句(Statement)節點, 語句節點經過在後面的Rationalization後會變為IL_OFFSET節點, 用於對應的IL偏移值,
最終VisualStudio等IDE可以根據機器代碼地址=>IL偏移值=>C#代碼偏移值來下斷點和調試.

下圖是Tree Ordering的實例, 紅線表示連接下一個節點:

Optimize

SSA & VN

RyuJIT為了實現更好的優化, 會對GenTree節點分配SSA序號和VN.

要說明什麼是SSA, 可以拿Wikipedia上的代碼做例子:

這裡有4個BasicBlock和3個變數(x, y, w), 變數的值會隨著執行而改變,
我們很難確定兩個時點的y是否同一個y, 這為代碼優化帶來了障礙.

為瞭解決這個問題我們為每個變數都標記一個版本號, 修改一次它的值就會出現一個新的版本.
這就是SSA(Static single assignment form), 一個變數+版本只能有一個值, 這時我們可以很簡單的確定兩個時點的y是否同一個y.
但是上圖有一個問題, 最後一個BasicBlock使用的y在編譯時是無法確定來源於哪個版本的.

為瞭解決這個問題, SSA引入了Φ(Phi)函數, 最後一個BasicBlock的開頭添加一個新的版本y3 = Φ(y1, y2).

而VN(Value Number)則是基於SSA的標記, 會根據給GenTree分配一個唯一的ID, 例如x = 3和w = 3時, x和w的VN會相等.

下圖是標記SSA和VN的實例:

Loop Optimizations

上面的"Flowgraph Analysis"提到的針對迴圈的一些優化, 在生成了SSA和VN以後我們可以做出進一步的優化.

例如這樣的迴圈:

var a = SomeFunction();
for (var x = 0; x < 3; ++x) {
    Console.WriteLine(a * 3);
}

註意a * 3這個表達式, 它每次迴圈都是一樣的並且無副作用, 也就是我們可以提取(hoist)它到迴圈外面:

var a = SomeFunction();
var tmp = a * 3;
for (var x = 0; x < 3; ++x) {
    Console.WriteLine(tmp);
}

這樣a * 3我們就只需要計算一次了, 但需要註意的是這種優化會增加一個臨時變數, 所以實際不一定會執行.

Copy Propagation

這項優化會替換具有相同VN的本地變數,
例如var tmp = a; var b = tmp + 1;, 因為我們確定tmp和a的值(VN)是一致的, 可以優化為var b = a + 1.
在執行這項優化後, 多餘的臨時變數將不再需要, 例如上面的tmp變數如果引用計數為0即可刪除.

CSE

這項優化會替換具有相同VN的表達式, 比起Copy Propagation這項優化的效果更強大.
例如:

var a = SomeFunction();
var b = (a + 5) * a;
var c = (a + 5) + a;

註意a + 5這個表達式出現了兩次, 這兩次對應的GenTree的VN都是一樣的,
因為它們無副作用(不會修改到全局狀態), JIT可以把這段代碼優化為:

var a = SomeFunction();
var tmp = a + 5;
var b = tmp * a;
var c = tmp + a;

和上面的Loop Optimizations一樣, 這種優化會增加一個臨時變數, 所以實際不一定會執行.

Assertion Propagation

在上面的Morph中JIT根據語句添加了一些斷言, 在生成VN後JIT可以傳播這些斷言.
例如:

var x = 1; // x確定為1
var y = x + 2;

傳播斷言後:

var x = 1; // x確定為1
var y = x + 2; // y確定為3

Range Check Elimination

因為斷言已經傳播, 這項優化可以根據斷言和VN來判斷哪些數組的邊界檢查是多餘的.
例如:

var length = 100;
var index = 99;
var a = new int[length]; // a的長度確定為100
var b = a[index]; // 確定訪問不會越界, 所以這裡的邊界檢查可以去掉

Backend

Rationalization

這個步驟會正式把HIR轉換為LIR, 後面的步驟使用的都是LIR形式.
前面的HIR中存在著一些問題, 例如ASG(=)節點:

看出問題了嗎?lclVar在LIR中如果不訪問後面的節點, 無法確定是讀取變數還是寫入變數.
Rationalizer會修改這些有問題的GenTree, 讓後面的處理更加簡單.
上面的lclVar =會修改為st.lclVar, 與lclVar區別開來.

Lowering

這個步驟會修改LIR中的GenTree節點, 讓它更接近最終生成的機器代碼形式.

以下是部分會轉換的GenTree節點:

ARR_LENGTH(獲取數組長度), 會轉換為IND(arr + ArrLenOffset), IND相當於C中的deref(*ptr)
計算式, 可能時轉換為LEA, 例如((v07 << 2) + v01) + 16可以轉換為lea(v01 + v07*4 + 16)
LONG, 如果當前cpu是x86(32位)則需要分為兩個變數操作
SWITCH, 切割SWITCH到if else和jmp jumpTable[x-offset]
CALL, 對於參數添加putarg節點(指定需要放到哪個寄存器或者推入堆棧)
STMT, 轉換為IL_OFFSET, 讓機器代碼地址跟IL偏移值可以對應起來

在完成了對GenTree節點的修改後, Lowering會對每個節點確定來源(src)和目標(dst)的寄存器數量.
例如lclVar節點需要一個目標寄存器, lclVar + lclVar節點需要兩個來源寄存器和一個目標寄存器.

除了設置需要的寄存器數量外, Lowering還會標記哪些節點是contained,
標記為contained的節點代表它是上級節點的一部分, 生成指令時不需要針對contained節點單獨生成.
典型的contained節點是常量, 例如b = a + 1可以生成add rbx, 1; mov rdi, rbx;, 這裡的1並不需要一條單獨的指令.

下圖是Lowering的實例:

LSRA

在Lowering確認了寄存器需求以後, JIT還需要給這些節點實際的分配寄存器.
分配寄存器的演算法有Graph coloring和LSRA等, RyuJIT使用的是LSRA, 和論文中的演算法很相似.
使用LSRA演算法可以讓JIT中分配寄存器所需的計算量更少, 但是分配的結果(執行效率)會比Graph coloring差一些.

在LSRA中有以下概念:

RefPosition: 記錄定義或使用變數的位置, 如果是Def或者Use則有所屬的Interval
Interval: 同一個變數對應的使用期間, 包含多個RefPosition
LocationInfo: 代碼位置, 在構建時會對LIR中的GenTree分配位置, 位置總會+2

下圖是LSRA的實例:

在這張圖中, Interval 0~2 是本地變數, 這裡只有V01被使用, Interval 3~4是虛擬變數, 用於表示函數返回的結果或傳入的參數.

DEF表示Interval被寫入, USE表示Interval被讀取,
Kill無對應的Interval, 只用於表示指定的寄存器的值是否在某個位置後被破壞,
FixedReg也無對應的Interval, 只用於表示對應的位置使用了固定的寄存器.

在確認Interval和RefPosition後, LSRA會開始分配寄存器,
一個寄存器在同一時間只能被一個Interval使用, 圖上的寄存器都未出現Interval重疊的情況,
如果出現Interval重疊, 寄存器中的值會保存(spill)到堆棧上的變數.
如果一個變數從未被spill, 則該變數可以不使用堆棧保存, 如圖上的V01可以一直存在rbx中, 不需要保存在記憶體里,
這可以帶來很大幅度的性能提升.

LSRA會積極的使用Callee Saved Register(RBX, RBP, R12, R13, R14, R15)暫存變數,
這些寄存器在調用(call)其它函數後原來的值仍然會被保留, 不需要spill.

CodeGen

在以上步驟都完成後, JIT會根據cpu平臺(x86, x64, arm)生成不一樣的彙編指令.

在CodeGen中有以下概念:

instrDesc: 彙編指令的數據, 一個instrDesc實例對應一條彙編指令
insGroup: 彙編指令的組, 一個insGroup包含一個或多個instrDesc, 跳轉指令的目標只能是IG的第一條指令

下圖是CodeGen的實例:

如圖所示, CodeGen會按LIR中的節點和LSRA分配的寄存器信息生成彙編指令, 並且會對指令進行分組儲存在不同的IG中.
進入函數的prolog和離開函數的epilog指令也會在這裡添加.
CodeGen還會對彙編指令的大小進行估算, 確定最多需要分配多少記憶體才可以編碼這些指令.

Emiiter

在最後, Emiiter會從LoaderHeap中分配記憶體, 並且根據instrDesc編碼機器代碼.

下圖是Emitter的實例:

除了寫入機器代碼外, Emiiter還會寫入以下的信息:

phdrDebugInfo: 包含了機器代碼地址到IL偏移值的索引
phdrJitEHInfo: 包含了函數中的例外信息
phdrJitGCInfo: 包含了函數中需要GC掃描的變數的信息
unindInfos: 包含了函數的堆棧回滾信息(在什麼位置使用了多大的堆棧空間)

最終寫入的函數在記憶體中的結構如下:

機器代碼的前面是函數頭信息(CodeHeader), 函數頭信息指向真正的函數頭信息(RealCodeHeader), 真正的頭信息中包含了上面提到的信息.
我們可以實際在Visual Studio中確認這一點:

圖中的0x7ffa46d0d898就是CodeHeader的內容, 也是指向RealCodeHeader的指針.
後面的55 57 56 ...是機器代碼, 表示push rbp; push rdi; push rsi; ....

打開0x7ffa46d0d898可以看到RealCodeHeader的內容.

參考鏈接

這篇是JIT的入門+科普教程, 為了讓內容更加易懂我省略了大量的實現細節, 也沒有貼出CoreCLR中的代碼.
在下一篇我將結合CoreCLR中的代碼講解JIT的具體工作流程, 內容會比這一篇難很多, 絕大多數C#程式員只要理解這一篇就很足夠了.

CoreCLR源碼探索(七) JIT的工作原理(入門篇)