「譯」Graal JIT編譯器是如何工作的

2020 年 5 月 4 日
筆記
compiler, graal

原文Understanding How Graal Works – a Java JIT Compiler Written in Java，講了jvmci和ideal graph的基本概念以及一些優化技術，很不錯的一篇文章，開頭結尾不太重要的部分已經省略，請見諒。

JIT編譯器是什麼

我敢說很多讀者都知道JIT編譯器是什麼，但是我還是會覆蓋基本概念，讓在場各位都沒有基礎上的疑問。

當你運行javac命令，或者用IDE保存的時候就做編譯，你的java程式會從java程式碼編譯成JVM位元組碼。JVM位元組碼是Java程式碼的二進位形式的表示。它比起源碼來說更緊湊，更簡單。但是絕大多數CPU是不能直接執行JVM位元組碼的。

要運行java程式需要jvm解釋位元組碼。解釋位元組碼通常都會比運行在真正CPU上的機器程式碼要慢，所以JVM可以在運行時使用其他編譯器，將位元組碼編譯成你的CPU可以直接跑的機器程式碼。

這個編譯器通常會比javac更複雜，會做很多優化來產出高品質的機器程式碼。

為什麼JIT編譯器要用Java來寫

OpenJDK是JVM的一個實現，現在它包含兩個JIT編譯器。客戶端編譯器，也叫C1，設計目的是編譯速度要快，所以產出的程式碼會包含較少優化。伺服器編譯器，也叫opto或者C2，設計初衷是花更多的時間產出高效優化的程式碼。

兩者的設計動機是C1適合桌面應用程式，它們不能容忍因為JIT編譯導致長時間的停頓，C2適合長時間運行的伺服器程式，它們可以花更多時間在編譯上面。

現在的JVM將它們組合在了一起，程式碼首先使用C1編譯，如果後面還在運行而且值得為它花費額外時間就使用C2再做編譯。這個機制叫做分層編譯。

讓我們把目光轉向C2——花更多時間在優化上面

我們可以從github克隆openjdk鏡像，或者可以直接瀏覽它的網站下載。

$ git clone //github.com/dmlloyd/openjdk.git

C2程式碼位於openjdk/hotspot/src/share/vm/opto.

首先，C2使用C++寫的。當然C++沒什麼本質上的錯誤，但卻有一些麻煩。C++是一門不安全的語言——這意味這C++的錯誤可以造成虛擬機crash。也由於程式碼年代久遠，用C++寫的C2變得很難維護，很難擴展。

C2背後的關鍵人物Cliff Click說他再也不會用C++寫虛擬機，我們也聽Twitter JVM團隊說C2目前是一灘死水，亟待一個替代品，因為在它上面開發太困難了。

所以回到問題，為什麼Java可以幫我們解決這些問題？呃因為上述所有需求都暗示我們用Java而不是C++。Java異常比C++ cash更安全，沒有記憶體泄漏，沒有懸空指針，也有很多工具比如調試器，profiler，visualvm，還有很多ide支援，等等。

你可能會想用Java寫一個JIT編譯器這怎麼可能？你可能認為只有使用低級系統語言比如C++才能做到，但是在這個talk中我想說不是的，完全不是！事實上JIT編譯器要做的只是接受JVM位元組碼然後產出機器程式碼——你收到一個byte[]數組然後返還一個byte[]即可。它可能背後做很多複雜的工作，但是這完全不涉及一個真的「系統」，你也不需要一個「系統」語言——一些定義認為系統語言是指類似C或者C++的語言，但不是Java。

配置graal

我們要做的第一件事是java9。graal使用的介面叫做jvmci，由JEP 243Java-Level JVM Compiler Interface提案加入到Java中。第一個實現提案的版本是java9。我使用9+181。如果有特殊需求也可以使用backport jvmci的java8。

$ export JAVA_HOME=`pwd`/jdk9
$ export PATH=$JAVA_HOME/bin:$PATH
$ java -version
java version "9"
Java(TM) SE Runtime Environment (build 9+181)
Java HotSpot(TM) 64-Bit Server VM (build 9+181, mixed mode)

下一步需要一個構建工具mx。他有點像maven或gradle，但是可能你從沒在你的程式上用過它。它支援一些複雜的使用樣例，但是我們只使用它做簡單的構建工作。

$ git clone //github.com/graalvm/mx.git
$ cd mx; git checkout 7353064
$ export PATH=`pwd`/mx:$PATH

接著我們克隆graal本身。。我是用graalvm的一個版本，版本號是0.28.2

$ git clone //github.com/graalvm/graal.git --branch vm-enterprise-0.28.2

該倉庫包含了一些項目，目前我們不關心。我們可以切換到compiler子目錄，那就是graal jit本身。然後使用mx構建它。

$ cd graal/compiler
$ mx build

現在我要使用eclipse ide打開graal源碼。我是用eclipse 4.7.1。 mx支援生成eclipse項目文件。

$ mx eclipseinit

如果你想使用graal作為workspace，點File，Import…,General,Existing projects然後選擇graal目錄即可。如果你沒用Java9運行eclipse本身，那你可能需要attach一個jdk。

ok，現在萬事俱備，以一個簡單的代為例我會展示它是如何工作的。

class Demo {
  public static void main(String[] args) {
    while (true) {
      workload(14, 2);
    }
  }

  private static int workload(int a, int b) {
    return a + b;
  }
}

我們將用javac編譯，然後使用jvm運行。首先使用傳統的C2 JIT。在這之前我們加上一些參數，用-XX:+PrintCompilation jvm記錄哪些方法便已過，用-XX:CompileOnly=Demo::workload讓編譯器只編譯某個方法，免得輸出太多了。

$ javac Demo.java
$ java \
  -XX:+PrintCompilation \
  -XX:CompileOnly=Demo::workload \
  Demo
...
    113    1       3       Demo::workload (4 bytes)
...

上面的log表示workload方法被編譯了，其他細節資訊我不做解釋。

現在讓我們使用剛剛構建的Graal作為Java9 JVM的JIT編譯器。我們需要再加一些比較複雜的flags。

·–module-path=…和–upgrade-module-path=…把graal加入模組路徑。注意模組是Jigsaw模組系統的東西，現在已經加入Java9，目前來說你可以將模組路徑看成是classpath。

我們需要-XX:+UnlockExperimentalVMOptions因為JVMCI（graal使用的）現目前還是實驗性質的。

然後加上-XX:+EnableJVMCI告訴JVM我們要使用JVMCI，然後加上-XX：+UseJVMCICompiler告訴jvm我們想配置一個新的JIT編譯器。

接著簡單起見，加上-XX:-TieredCompilation關閉分層編譯讓JVM只有一個JVMCI編譯器而不是C1和JVMCI混合分層。

當然，前面的-XX:+PrintCompilation 和-XX:CompileOnly=Demo::workload還是保持不變。和之前一樣，我們會看到有一個方法被編譯了雖然是使用graal編譯的。現在請只管跟著我做。

$ java \
  --module-path=graal/sdk/mxbuild/modules/org.graalvm.graal_sdk.jar:graal/truffle/mxbuild/modules/com.oracle.truffle.truffle_api.jar \
  --upgrade-module-path=graal/compiler/mxbuild/modules/jdk.internal.vm.compiler.jar \
  -XX:+UnlockExperimentalVMOptions \
  -XX:+EnableJVMCI \
  -XX:+UseJVMCICompiler \
  -XX:-TieredCompilation \
  -XX:+PrintCompilation \
  -XX:CompileOnly=Demo::workload \
  Demo
...
    583   25             Demo::workload (4 bytes)
...

JVMCI編譯器介面

我們現在做的很牛逼了不是嗎？我們有個JVM，然後用新的JIT替換了之前的那個，還用它編譯了程式碼，且沒有改變JVM的任何程式碼。讓這一切變得可能的正是JVMCI——JVM編譯器介面——之前提到過JEP243提出它現在已經併入java9。

這個idea和jvm現有的一些技術其實差不多。

以前你可能用Java註解處理API添加過一些註解到javac，它們可以處理源程式碼。不難看出java註解就是個獲取它們附著於的源程式碼，然後產出新源程式碼的工具。

你可能使用過java agent做自定義的java位元組碼處理。它可以攔截java位元組碼然後修改它。

JVMCI和它們一樣。它讓你可以插入一個java寫的jit編譯器到jvm上。

等下我會介紹ppt上展示的程式碼的一些方法，然後我會簡化標識符和邏輯幫助你理解這個idea，接著我會切換到eclpse的一些螢幕截圖向你展示真的程式碼，雖然可能有點複雜，但是大體上是一樣的。這個talk的重要內容就是幫助你深入源碼本身，所以我不想隱藏它，儘管它很複雜。

首先我想消除你覺得jit編譯器極其複雜的想法。JIT編譯器的輸入什麼？它獲取要編譯的方法的位元組碼，位元組碼，看名字就知道是「一個位元組數組的程式碼」。JIT編譯器輸出什麼？它輸出方法對應的機器程式碼。機器程式碼也是「一個位元組數組的程式碼「
所以當你寫一個新jit插入到jvm的時候你要實現的介面看起來類似下面：

interface JVMCICompiler {
    byte[] compileMethod(byte[] bytecode);
}

所以你大可不必認為java怎麼能做jit編譯產出機器碼這麼底層的事情，他就是個byte[]到byte[]的函數而已。

不過實際上的比這要複雜一些。只是一個位元組數組的程式碼還不夠，我們還想要一些資訊比如局部變數的個數，棧的大小，解釋器收集到的profiling資訊等，這讓我們可以了解實際程式碼運行的情況。因此輸入不是位元組數組而是一個CompilationRequest，它可以告訴我們哪一個JavaMethod要編譯，然後給我們需要的所有資訊。

interface JVMCICompiler {
  void compileMethod(CompilationRequest request);
}

interface CompilationRequest {
    JavaMethod getMethod();
}

interface JavaMethod {
    byte[] getCode();
    int getMaxLocals();
    int getMaxStackSize();
    ProfilingInfo getProfilingInfo();
    ...
}

同樣，介面不返回編譯好的機器程式碼。取而代之是你調用其他API告訴虛擬機你想裝配上機器程式碼。

HotSpot.installCode(targetCode);

現在為jvm寫一個jit編譯器我們只需要實現這個介面就好了。我們得到了想要編譯的方法的資訊，然後編譯成機器程式碼，最後調用installCode

class GraalCompiler implements JVMCICompiler {
  void compileMethod(CompilationRequest request) {
    HotSpot.installCode(...);
  }
}

讓我們切換到eclipse ide，看看這些介面到底長什麼樣。和我前面說的一樣，他有點複雜但不是很複雜

現在我想像你展示的就是我們可以馬上改graal的程式碼然後在java9中使用它。我會在graal編譯方法的地方加一些log程式碼

class HotSpotGraalCompiler implements JVMCICompiler {
  CompilationRequestResult compileMethod(CompilationRequest request) {
    System.err.println("Going to compile " + request.getMethod().getName());
    ...
  }
}

現在關閉HotSpot的編譯記錄，然後用我們修改的版本

$ java \
  --module-path=graal/sdk/mxbuild/modules/org.graalvm.graal_sdk.jar:graal/truffle/mxbuild/modules/com.oracle.truffle.truffle_api.jar \
  --upgrade-module-path=graal/compiler/mxbuild/modules/jdk.internal.vm.compiler.jar \
  -XX:+UnlockExperimentalVMOptions \
  -XX:+EnableJVMCI \
  -XX:+UseJVMCICompiler \
  -XX:-TieredCompilation \
  -XX:CompileOnly=Demo::workload \
  Demo

如果你在elipse中編輯，你會注意到我們甚至沒有運行mx build。正常的eclipse編譯即可。我們完全不需要編譯jvm本身。我們可以看可以立刻把修改好的編譯器插入到現有的jvm。

Graal graph

ok，現在我們知道graal是把byte[]轉成另一個byte[]。讓我們說說這個轉化背後的理論和數據結構。因為它有點不尋常，即使是對於編譯器來說。

本質來說編譯器做的事情是操縱程式。要操縱程式需要一些用來表示程式本身的數據結構。位元組碼和類似的指令序列都行，但是表達力不強。

相反，graal使用圖結構來表示你的程式。如果你對兩個局部變數做加飯，圖將為每個局部變數創建一個node，還有一個表示加法的node，兩條邊指示局部變數node流入加法node。

這種圖也被叫做程式依賴圖。

如果有一個表達式比如x+y，我們會看到兩個表示x，y的node，一個對兩者做加法的node。

圖中藍色的邊表示數據流，它們讀取局部變數的值，流入加法node。我們也可以使用邊表示程式運行的順序。如果我們調用兩個方法而不是讀取兩個局部變數，比如getX(),getY()，然後我們需要記住調用順序。這個也可以通過一條邊來表示，即下面的紅邊。

graal圖可以說是將兩種圖以某種方式結合到了一起。節點相同，但是一個邊集（edge set）表示數據流，另一個邊集表示控制流。

你可以用IdealGraphVisualiser這個工具可視化graal圖。運行mx igv即可。

然後jvm加上參數-Dgraal.Dump

我們可以寫個簡單的表達式看看數據流

int average(int a, int b) {
  return (a + b) / 2;
}

你可以看到參數0（寫作P(0)）和參數1（寫作P(1)）是如何送入加法操作的，然後結果是如何和常量2（寫作C(2)）送入除法操作的。計算最後結果返回。

如果我們引入一個循環可以看到更複雜的數據流和控制流

int average(int[] values) {
  int sum = 0;
  for (int n = 0; n < values.length; n++) {
    sum += values[n];
  }
  return sum / values.length;
}

現在圖中有節點表示循環起始，有節點表讀取數組元素，有節點讀取數組長度。和之前一樣，藍線表示數據流，紅線表示控制流。

從上面不難看出為什麼這個數據結構有時候又叫做節點海（sea of nodes），或者節點湯（soup of nodes）。

我想說c2使用非常類似的數據結構，也正是因為c2使得這種節點海編譯器變得留下，它不是graal的創新。

關於圖是怎麼構建的這裡我先不展示，當你的程式使用graal graph這種格式，編譯和優化都修改這個數據結構而已。這也是為什麼用java寫jit沒問題的原因。java是oop語言，graal graph是對象的集合，然後引用視作邊將他們鏈接起來。

從位元組碼到機器程式碼

讓我們從實際除法，看看編譯的流程。

1.位元組碼輸入

編譯始於位元組碼。我們回到之前的簡單加法示例。

int workload(int a, int b) {
  return a + b;
}

我們在編譯開始位置輸出要編譯的位元組碼

class HotSpotGraalCompiler implements JVMCICompiler {
  CompilationRequestResult compileMethod(CompilationRequest request) {
    System.err.println(request.getMethod().getName() + " bytecode: "
      + Arrays.toString(request.getMethod().getCode()));
    ...
  }
}

workload bytecode: [26, 27, 96, -84]

2.位元組碼解析器和圖構造器

位元組數組被解析為jvm位元組碼然後放入圖構造器。這是另一種形式的解釋器，只是比較抽象。它解釋執行位元組碼，只是不傳遞它們的值而是傳遞邊然後將他們連接起來。讓我們享受一下java寫graal的好處，用elipse navigation工具看看它怎麼工作的。我們知道示例有一個加法節點，現在看看它們是怎麼創建的。

可以看到位元組碼解析器解析到iadd的時候創建了它們。如果這是一個真的jvm解釋器，他會pop兩個棧上的值，然後做加法，然後push結果到棧上。現在從棧上pop兩個node表示計算的操作數，然後添加一個node表示加法操作，最後把它們push到棧上表示計算結果。如此操作我們得倒了graal graph。

3. 生成彙編

我們想要將graal graph轉化為機器程式碼，需要為圖中每個node生成機器程式碼。這一步在generate方法中完成。

void generate(Generator gen) {
    gen.emitAdd(a, b);
}

再一次的，我們在高層次抽象上面工作，又一個類生成類加法的彙編，但是不知道細節。emitAdd的細節有點複雜和抽象，因為算數操作會根據operand的不同很多組合，並且不同的操作符可以共享絕大部分程式碼，所以我們簡化一下程式

int workload(int a) {
  return a + 1;
}

它使用加法指令，然後我會向你展示類似的彙編

void incl(Register dst) {
    int encode = prefixAndEncode(dst.encoding);
    emitByte(0xFF);
    emitByte(0xC0 | encode);
}

void emitByte(int b) {
    data.put((byte) (b & 0xFF));
}

可以看到它生成位元組作為輸出，這些都放到一個標準的ByteBuffer裡面——它可以用來構建位元組數組

4. 彙編輸出

和前面提到的位元組碼輸入一樣，我們看看機器程式碼的輸出是什麼樣的。我們改一下源碼讓他log生成的機器碼

class HotSpotGraalCompiler implements JVMCICompiler {
  CompilationResult compileHelper(...) {
    ...
    System.err.println(method.getName() + " machine code: "
      + Arrays.toString(result.getTargetCode()));
    ...
  }
}

我們也可以使用一個工具反彙編生成的呃機器程式碼，它是hotspot的標準組件——不是graal的。我會展示怎麼構建這個工具——它在openjdk倉庫中但是默認沒有在jvm中，所以只得自己構建它

$ cd openjdk/hotspot/src/share/tools/hsdis
$ curl -O //ftp.heanet.ie/mirrors/gnu/binutils/binutils-2.24.tar.gz
$ tar -xzf binutils-2.24.tar.gz
$ make BINUTILS=binutils-2.24 ARCH=amd64 CFLAGS=-Wno-error
$ cp build/macosx-amd64/hsdis-amd64.dylib ../../../../../..

現在加上兩個flag -XX:+UnlockDiagnosticVMOptions -XX:+PrintAssembly

$ java \
  --module-path=graal/sdk/mxbuild/modules/org.graalvm.graal_sdk.jar:graal/truffle/mxbuild/modules/com.oracle.truffle.truffle_api.jar \
  --upgrade-module-path=graal/compiler/mxbuild/modules/jdk.internal.vm.compiler.jar \
  -XX:+UnlockExperimentalVMOptions \
  -XX:+EnableJVMCI \
  -XX:+UseJVMCICompiler \
  -XX:-TieredCompilation \
  -XX:+PrintCompilation \
  -XX:+UnlockDiagnosticVMOptions \
  -XX:+PrintAssembly \
  -XX:CompileOnly=Demo::workload \
  Demo

現在我們可以運行示例然後看看生成的加法指令

workload machine code: [15, 31, 68, 0, 0, 3, -14, -117, -58, -123, 5, ...]
...
0x000000010f71cda0: nopl   0x0(%rax,%rax,1)
0x000000010f71cda5: add    %edx,%esi          ;*iadd {reexecute=0 rethrow=0 return_oop=0}
                                              ; - Demo::workload@2 (line 10)

0x000000010f71cda7: mov    %esi,%eax          ;*ireturn {reexecute=0 rethrow=0 return_oop=0}
                                              ; - Demo::workload@3 (line 10)

0x000000010f71cda9: test   %eax,-0xcba8da9(%rip)        # 0x0000000102b74006
                                              ;   {poll_return}
0x000000010f71cdaf: vzeroupper
0x000000010f71cdb2: retq

ok，為了檢驗我們是不是真的掌握了，我們修改一下加法的實現，用減法代替。我會修改generate方法的加法節點，然後生成減法

class AddNode {
  void generate(...) {
    ... gen.emitSub(op1, op2, false) ...  // changed from emitAdd
  }
}

運行之後會看到生成的機器程式碼數組改變了，機器指令也改變了

workload mechine code: [15, 31, 68, 0, 0, 43, -14, -117, -58, -123, 5, ...]
0x0000000107f451a0: nopl   0x0(%rax,%rax,1)
0x0000000107f451a5: sub    %edx,%esi          ;*iadd {reexecute=0 rethrow=0 return_oop=0}
                                              ; - Demo::workload@2 (line 10)

0x0000000107f451a7: mov    %esi,%eax          ;*ireturn {reexecute=0 rethrow=0 return_oop=0}
                                              ; - Demo::workload@3 (line 10)

0x0000000107f451a9: test   %eax,-0x1db81a9(%rip)        # 0x000000010618d006
                                              ;   {poll_return}
0x0000000107f451af: vzeroupper
0x0000000107f451b2: retq

所以這裡我們學到了什麼？graal真的接受一個位元組碼數組，我們可以看到圖node是如何從那個數組上創建的，我們可以看到機器程式碼是如何基於node生成的，然後機器指令是如何編碼的。我們可以看到我們能改變graal工作機制。

[26, 27, 96, -84] → [15, 31, 68, 0, 0, 43, -14, -117, -58, -123, 5, ...]

優化

現在我們知道了怎麼得到圖表示，圖node怎麼生成機器程式碼，現在再讓我們看看graal是怎麼優化圖讓它高效的。

一個優化階段（phase）是一個方法，它有修改圖的機會。你要寫一個優化階段需要實現下面的介面。

interface Phase {
  void run(Graph graph);
}

1. 規範化（Canonicalisation）

規範化意味著重排node，形成一個統一的表示，規範化還有些其他目的，不過這次ppt我們要說的是規範化意味著常量摺疊和節點簡化。

節點可以簡化自身，它們本身有一個canonical方法

interface Node {
  Node canonical();
}

讓我們看看負節點（negate node），負節點即一元減法操作。如果一個一元減法作用於另一個一元減法，那麼減法本身就會消除，只留下原始值，，即–x == x

class NegateNode implements Node {
  Node canonical() {
    if (value instanceof NegateNode) {
      return ((NegateNode) value).getValue();
    } else {
      return this;
    }
  }
}

這是個理解graal絕佳的來自。程式碼邏輯已經不能在簡化了。

如果你有一個java操作要簡化，你可以修改canonical方法實現。

2. 全局值編號（global value numbering）

全局值編號是一種移除冗餘程式碼的技術。這個例子中，a+b可以只計算一次，然後使用兩次計算得倒的值。

int workload(int a, int b) {
  return (a + b) * (a + b);
}

graal可以比較兩個node看它們是否相等。如果相等則簡化。graal的全局值編號階段會迭代檢查每個節點是否和其他任何節點相等，，如果相等就會替換為另一個節點的拷貝。他把所有節點放入hash map，這樣可以高效完成。有點類似於node快取。

注意測試節點不是固定的，這意味著節點在某個確定的時間不能有副作用。如果我們使用方法調用代替，就變成了確定的

int workload() {
  return (getA() + getB()) * (getA() + getB());
}

3. 鎖粗化（lock coarsening）

來看一個更複雜的例子。有時候我們會在一個小範圍內對同一個對象多次使用synchonrized，雖然可能不會有意為之，但是編譯器內聯優化可能會導致那種程式碼產生。

void workload() {
  synchronized (monitor) {
    counter++;
  }
  synchronized (monitor) {
    counter++;
  }
}

我們可以對它進行去糖化，然後高效實現

void workload() {
  monitor.enter();
  counter++;
  monitor.exit();
  monitor.enter();
  counter++;
  monitor.exit();
}

我們可以優化這段程式碼，只進出一次monitor而不是多次進出，這就是鎖粗化

void workload() {
  monitor.enter();
  counter++;
  counter++;
  monitor.exit();
}

在graal中鎖粗化由 LockEliminationPhase這個階段實現。它的 run 方法查看所有monitor退出節點，然後看它們是否後面馬上跟一個monitor 進入節點。如果後面確認使用了使用了相同的monitor，會移除它們，只留下一個monitor進/出節點。

void run(StructuredGraph graph) {
  for (monitorExitNode monitorExitNode : graph.getNodes(MonitorExitNode.class)) {
    FixedNode next = monitorExitNode.next();
    if (next instanceof monitorEnterNode) {
      AccessmonitorNode monitorEnterNode = (AccessmonitorNode) next;
      if (monitorEnterNode.object() == monitorExitNode.object()) {
        monitorExitNode.remove();
        monitorEnterNode.remove();
      }
    }
  }
}

這樣做是值得的，因為少了額外monitor進/出意味著程式碼變少了，其實這裡還允許我們繼續優化，可以把兩個遞增組合起來變成+2

void workload() {
  monitor.enter();
  counter += 2;
  monitor.exit();
}

讓我們用IGV看看。可以看到原圖有兩對monitoer enter/exit，然後變成了一對，當優化phase運行之後，兩個遞增變成了一個加法。

Tags: compiler graal