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

原文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編譯器??蛻舳司幾g器,也叫C1,設計目的是編譯速度要快,所以產出的代碼會包含較少優化。服務器編譯器,也叫opto或者C2,設計初衷是花更多的時間產出高效優化的代碼。

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

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

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

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

$ git clone https://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++ crash更安全,沒有內存泄漏,沒有懸空指針,也有很多工具比如調試器,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 https://github.com/graalvm/mx.git
$ cd mx; git checkout 7353064
$ export PATH=`pwd`/mx:$PATH

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

$ git clone https://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編譯的?,F在請只管跟著我做。

$ 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結果到棧上?,F在從棧上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 http://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::[email protected] (line 10)

0x000000010f71cda7: mov    %esi,%eax          ;*ireturn {reexecute=0 rethrow=0 return_oop=0}
                                              ; - Demo::[email protected] (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::[email protected] (line 10)

0x0000000107f451a7: mov    %esi,%eax          ;*ireturn {reexecute=0 rethrow=0 return_oop=0}
                                              ; - Demo::[email protected] (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看看??梢钥吹皆瓐D有兩對monitoer enter/exit,然后變成了一對,當優化phase運行之后,兩個遞增變成了一個加法。

posted @ 2020-05-04 12:02  kelthuzadx  閱讀(...)  評論(...編輯  收藏
全民捕鱼游戏怎么玩 四维图新股票行情走势002249 扑克3 北京十一选5预测 山西11选5五码遗漏 湖北快3走势图今天 那个时时彩平台好可靠 601228股票行情 四川金7乐跨度走势图 内蒙古 11 选 5 走势图 江西快三走势分布图