[Translation] How Graal Works - JIT JVM Compiler in Java

Hi, Habr! I present to your attention the translation of the article " Understanding How Graal Works - a Java JIT Compiler Written in Java ".

Introduction

One of the reasons why I became a researcher of programming languages is that, in a large community of people connected with computer technologies, almost all use programming languages, and many are interested in how they work. When I first encountered programming as a child and became acquainted with a programming language, the first thing I wanted to know was how it works, and the very first thing I wanted to do was create my own language.

In this presentation, I will show some of the mechanisms of the language used by all of you - Java. A special feature is that I will use a project called Graal , which implements the concept of Java in Java .

Graal is only one of the components in the work of Java - it is just-in-time compiler. This is the part of the JVM that converts Java bytecode to machine code during program operation, and is one of the factors ensuring high platform performance. It also seems to me that most people consider one of the most complex and hazy parts of the JVM, which is beyond their comprehension. To change this opinion is the purpose of this talk.

If you know what a JVM is; in general, you understand what the terms bytecode and machine code mean; and are able to read code written in Java, then I hope this will be enough to understand the stated material.

I will begin by discussing why we might want a new JIT compiler for JVM written in Java, and then I’ll show that there is nothing extraordinary in this, as you might think by breaking the task down into compiler build, use, and demonstration that its code is the same as in any other application.

I’ll touch on the theory quite a bit, and then show how it is applied during the whole compilation process from bytecode to machine code. I will also show some details, and in the end we will talk about the benefits of this feature besides implementing Java in Java for its own sake.

I will use screenshots of the code in Eclipse, instead of running them during the presentation, to avoid the inevitable problems of live coding.

What is a JIT compiler?

I am sure that many of you know what a JIT compiler is, but nevertheless I will touch upon the basics so that no one is sitting here afraid to ask this main question.

When you run the javac or compile-on-save command in the IDE, your Java program is compiled from Java code into JVM bytecode, which is a binary representation of the program. It is more compact and simple than Java source code. However, the usual processor of your laptop or server cannot simply execute JVM bytecode.

The JVM interprets this bytecode for your program to work. Interpreters are usually much slower than machine code run on a processor. For this reason, while the program is running, the JVM can start another compiler that converts your bytecode to machine code, which the processor is already able to execute.

This compiler, usually much more sophisticated than javac , performs complex optimizations to produce high-quality machine code as a result.

Why write a JIT compiler in Java?

Today, a JVM implementation called OpenJDK includes two main JIT compilers. The client compiler, known as C1 , is designed to run faster, but it also produces less optimized code. The server compiler, known as opto or C2 , takes a little more time to work, but produces more optimized code.

The idea was that the client compiler was better suited for desktop applications, where long pauses of the JIT compiler are undesirable, and the server compiler for long-running server applications in which it is possible to spend more time on compilation.

Today, they can be combined so that the code is first compiled with C1, and then, if it continues to be intensively executed and it makes sense to spend additional time, - C2. This is called tiered compilation .

Let's look at the C2 server compiler, which performs more optimizations.

We can clone OpenJDK from a mirror on GitHub , or just open a project tree on the site.

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

The C2 code is in openjdk / hotspot / src / share / vm / opto .

C2 source code

First of all, it is worth noting that C2 is written in C ++ . Of course, this is not something bad, but there are certain disadvantages. C ++ is an insecure language. This means that errors in C ++ can crash the VM. It is possible that the reason for this is the age of the code, but C2 code in C ++ has become very difficult to maintain and develop.

One of the key figures behind the C2 compiler, Cliff Click, said that he would never write VM again in C ++, and we heard the Twitter JVM team express the opinion that C2 had become stagnant and needed to be replaced due to difficulties of further development.

Cliff Click Presentation

What doesn’t Cliff Click

https://www.youtube.com/watch?v=Hqw57GJSrac

So, going back to the question, what is there in Java that can help solve these problems? The same thing that gives writing a program in Java instead of C ++. This is probably security (exceptions instead of crashes, no real memory leaks or dangling pointers), good tools (debuggers, profilers, and tools like VisualVM ), good support for IDE, etc.

You might think: How can I write something like a JIT compiler in Java? and that this is only possible in a low-level system programming language, such as C ++. In this talk, I hope to convince you that this is not the case at all! Essentially, the JIT compiler should simply accept the JVM bytecode and output the machine code — you give it a byte[] at the input, and you also want to get back the byte[] . It takes a lot of complicated work to do this, but it doesn’t affect the system level, and therefore does not require a system language such as C or C ++.

Setting Graal

The first thing we need is Java 9. The Graal interface used called JVMCI was added to Java as part of the JEP 243 Java-Level JVM Compiler Interface and the first version that includes it is Java 9. I use 9 + 181 . In case of any particular requirements there are ports (backports) for Java 8.

 $ 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)

The next thing we need is an assembly system called mx . It is a bit like Maven or Gradle , but, most likely, you would not choose it for your application. It implements some functionality to support some complex use cases, but we will only use it for simple builds.

You can clone mx with github. I am using commit #7353064 . Now just add the executable file to the path.

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

Now we need to slope Graal himself. I am using a distribution called GraalVM version 0.28.2 .

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

This repository contains other projects that are not interesting to us now, so we simply move to the compiler subproject, which is the Graal JIT compiler, and build it using mx .

 $ cd graal/compiler $ mx build

I’ll use the Eclipse IDE to work with Graal code. I am using Eclipse 4.7.1. mx can generate Eclipse project files for us.

 $ mx eclipseinit

To open the graal directory as a workspace, you need to run File, Import ..., General, Existing projects and select the graal directory again . If you didn't run Eclipse in Java 9, then you might also need to attach the JDK sources.

Graal in eclipse

Good. Now that everything is ready, let's see how it works. We will use this very simple code.

 class Demo { public static void main(String[] args) { while (true) { workload(14, 2); } } private static int workload(int a, int b) { return a + b; } }

First we compile this javac code, and then run the JVM. First, I will show the work of the standard C2 JIT compiler. To do this, we specify several flags: -XX:+PrintCompilation , which is necessary for the JVM to write the log when compiling the method, and -XX:CompileOnly=Demo::workload , so that only this method is compiled. If we do not do this, too much information will be displayed, and the JVM will be smarter than we need and optimize the code we want to see.

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

I will not explain it in detail, but I will say only that this is a log output, which shows that the workload method workload been compiled.

Now, as a JIT compiler for our Java 9 JVM, we use the newly compiled Graal. For this you need to add a few more flags.

--module-path=... and --upgrade-module-path=... add Graal to the module path . Recall that the module path appeared in Java 9 as part of the Jigsaw module system, and for our purposes we can consider it by analogy with the classpath .

We need the -XX:+UnlockExperimentalVMOptions because the JVMCI (interface used by Graal) in this version is an experimental feature.

The -XX:+EnableJVMCI needed to say that we want to use JVMCI, and -XX:+UseJVMCICompiler - to enable and install a new JIT compiler.

In order not to complicate the example, and instead of using C1 in conjunction with JVMCI, to have only the JVMCI compiler, we specify the -XX:-TieredCompilation , which disables stepwise compilation.

As before, we specify the -XX:+PrintCompilation and -XX:CompileOnly=Demo::workload .

As in the previous example, we see that one method was compiled. But, this time, for compilation, we used the newly compiled Graal. For now, just take my word for it.

 $ 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) ...

JVM compiler interface

Do not you think that we have done something quite unusual? We have an installed JVM, and we replaced the JIT compiler with the newly compiled new one without changing anything in the JVM itself. This feature is provided by a new JVM interface called JVMCI, the JVM compiler interface , which I mentioned above was JEP 243 and was included in Java 9.

The idea is similar to some other existing JVM technologies.

Perhaps you have already come across additional processing of source code in javac using the Java annotation processing API . This mechanism makes it possible to identify the annotations and the model of the source code in which they are used, and to create new files based on them.

Also, you may have used additional bytecode processing in the JVM using Java agents . This mechanism allows you to modify Java bytecode by intercepting it when loading.

The idea of JVMCI is similar. It allows you to connect your own Java JIT compiler written in Java.

Now I want to say a few words about how I will show the code during this presentation. First, to understand the idea, I will show some simplified identifiers and logic in the form of text on slides, and then I will switch to Eclipse screenshots and show real code, which may be a little more complicated, but the main idea will remain the same. The main part of this speech is intended to show that you can really work with a real project code, and therefore I don’t want to hide it, although it may be somewhat complicated.

From this point on, I will begin to dispel the opinion that you might have, that the JIT compiler is very difficult.

What does the JIT compiler take as input? It accepts the bytecode of the method to be compiled. A baytkod, as the name suggests, is just an array of bytes.

What does the JIT compiler produce as a result? It gives the machine code of the method. Machine code is also just an array of bytes.

As a result, the interface that needs to be implemented when writing a new JIT compiler to embed it in the JVM will look something like this.

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

Therefore, if you could not imagine how Java can do something as low-level as JIT compilation into machine code, now it is clear that this is not such a low-level work. True? This is just a function from byte[] to byte[] .

In fact, everything is somewhat more complicated. Only bytecode is not enough - we also need some more information, such as the number of local variables, the required stack size, and the information collected by the interpreter profiler to understand how the code is executed after the fact. Therefore, we present the input in the form of a CompilationRequest , which tells us about the JavaMethod that needs to be compiled and provides all the necessary information.

 interface JVMCICompiler { void compileMethod(CompilationRequest request); } interface CompilationRequest { JavaMethod getMethod(); } interface JavaMethod { byte[] getCode(); int getMaxLocals(); int getMaxStackSize(); ProfilingInfo getProfilingInfo(); ... }

Also, the interface does not require the return of the compiled code. Instead, to install the machine code in the JVM, another API is used.

 HotSpot.installCode(targetCode);

Now, to write a new JIT compiler for the JVM, you just need to implement this interface. We get information about the method that needs to be compiled, and must compile it into machine code and call installCode .

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

Let's switch to Eclipse IDE with Graal and look at some real interfaces and classes. As mentioned earlier, they will be somewhat more complicated, but not by much.

JVMCICompiler

HotSpotGraalCompiler

compileMethod

Now I want to show that we can make changes to Graal, and immediately use them in Java 9. I will add a new log message, which will be displayed when the method is compiled using Graal. Add it to the implemented interface method, which is called by the JVMCI.

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

Compilation

For now, disable the compilation logging that exists in HotSpot. Now we can see our message from a modified version of the compiler.

 $ 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 Going to compile workload

If you try to do it yourself, you will notice that it does not even need to run our build system - mx build . Enough for Eclipse, compile on save . And certainly we don’t need to rebuild the JVM itself. We simply embed the modified compiler into the existing JVM.

Graph graal

Well, we know that Graal converts one byte[] into another byte[] . Now let's talk about the theory and data structures that it uses, because they are a bit unusual even for a compiler.

In essence, the compiler handles the processing of your program. To do this, the program must be represented in the form of a data structure. One option is bytecode and similar instruction lists, but they are not very expressive.

Instead, Graal uses a graph to represent your program. If we take a simple addition operator that adds two local variables, then the graph will include one node to load each variable, one node for the sum, and two edges, which show that the result of loading local variables is input to the addition operator.

This is sometimes called the program dependency graph .

Having an expression of the form x + y we get the nodes for the local variables x and y , and the node of their sums.

Data flow graph

The blue edges on this graph indicate the direction of data flow from reading local variables to summation.

Also, we can use edges to reflect the order of program execution. If, instead of reading local variables, we call methods, then we need to remember the order of the call, and we cannot rearrange them in places (without knowing the code inside). For this there are additional edges that define this order. They are shown in red.

Control flow graph

So, the Graal graph, in fact, is two graphs combined in one. Nodes are the same, but some edges show the direction of data flow, while others show the transfer of control between them.

To see the Graal graph, you can use a tool called IdealGraphVisualiser or IGV . The launch is performed using the mx igv .

IdealGraphVisualiser

After that, run the JVM with the -Dgraal.Dump flag.

A simple data stream can be seen by writing an uncomplicated expression.

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

IGV arithmetic mean

You can see how the parameters 0 ( P(0 ) and 1 ( P(1) ) are fed to the input of the addition operation, which, together with the constant 2 ( C(2) ) is fed to the input of the division operation. After this value is returned.

In order to look at a more complex data flow and control, we introduce a loop.

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

IGV arithmetic mean with a cycle

Detailed IGV arithmetic mean with a cycle

In this case, we have nodes at the beginning and end of the loop, reading the elements of the array, and reading the length of the array. As before, the blue lines show the direction of data flow, and the red lines indicate the flow of control.

Now you can see why this data structure is sometimes called a sea of nodes or a soup of nodes .

I want to say that C2 uses a very similar data structure, and, in fact, it was C2 that popularized the idea of the compiler of the sea of nodes , so this is not an innovation of Graal.

I will not show the process of building this graph until the next part of the speech, but when Graal gets the program in this format, optimization and compilation is performed by modifying this data structure. And this is one of the reasons why writing a JIT compiler in Java makes sense. Java — - , — , .

, .

. .

 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]

, .

, JVM, Graal. , , — Java, , , .

, Graal Java, Eclipse. , , .

Addnode

Call Search AddNode.create

Parser

, , IADD ( 96 , ).

 private void genArithmeticOp(JavaKind kind, int opcode) { ValueNode y = frameState.pop(kind); ValueNode x = frameState.pop(kind); ValueNode v; switch (opcode) { ... case LADD: v = genIntegerAdd(x, y); break; ... } frameState.push(kind, append(v)); }

, , .. . JVM, , , . , , , , , , , .

Graal.

Graal . generate .

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

, . , .

emitAdd , , , , . .

 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)); }

incl

, , ByteBuffer — .

— .

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

. HotSpot. . 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 ../../../../../..

: -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

. , . generate , .

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

AddNode

, , , .

 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 ; ; ; . , Graal.

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

, , . Graal , .

— . .

 interface Phase { void run(Graph graph); }

(canonicalisation)

. , , ( constant folding ) .

— canonical .

 interface Node { Node canonical(); }

, , , . — . -(-x) x .

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

findSynonym NegateNode

Graal . , .

Java, canonical .

Global value numbering

Global value numbering (GVN) — . a + b , — .

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

Graal . — . GVN . hash map , , .

Global value numbering

global value numbering

, — , , - . , , , , — .

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

, global value numbered

(lock coarsening)

. . , , , ( inlining ).

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

, , , , .

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

. .

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

Graal LockEliminationPhase . run , . , , .

 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(); } } } }

, , , , 2 .

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

IGV . , , \ , , , 2 .

Graal , , , . , , , .

Graal , , , , , , .

Graal , , . ? , ?

, , . . , , , , . , , , , , .

( register allocation ). Graal , JIT-, — ( linear scan algorithm ).

, , , - , .

, , , , (.. ), . , , .

( graph scheduling ). . , . , , , .

, .

Graal?

, , , Graal — , Oracle . , Graal?

(final-tier compiler)

C JVMCI Graal HotSpot — , . ( HotSpot) Graal , .

Twitter Graal , Java 9 . : -XX:+UseJVMCICompiler .

JVMCI , Graal JVM. (deploy) - JVM, Graal. Java-, Graal, JVM.

OpenJDK Metropolis JVM Java. Graal .

Metropolis

http://cr.openjdk.java.net/\~jrose/metropolis/Metropolis-Proposal.html

Graal . Graal JVM, Graal . , Graal . , - , , JNI.

Charles Nutter JRuby Graal Ruby. , - .

AOT (ahead-of-time)

Graal — Java. JVMCI , Graal, , , Graal . , Graal , JIT-.

JIT- AOT- , Graal . AOT Graal.

Java 9 JIT-, . JVM, .

AOT Java 9 Graal, Linux. , , .

. SubstrateVM — AOT-, Java- JVM . , - (statically linked) . JVM , . SubstrateVM Graal. ( just-in-time ) SubstrateVM, , Graal . Graal AOT- .

 $ javac Hello.java $ graalvm-0.28.2/bin/native-image Hello classlist: 966.44 ms (cap): 804.46 ms setup: 1,514.31 ms (typeflow): 2,580.70 ms (objects): 719.04 ms (features): 16.27 ms analysis: 3,422.58 ms universe: 262.09 ms (parse): 528.44 ms (inline): 1,259.94 ms (compile): 6,716.20 ms compile: 8,817.97 ms image: 1,070.29 ms debuginfo: 672.64 ms write: 1,797.45 ms [total]: 17,907.56 ms $ ls -lh hello -rwxr-xr-x 1 chrisseaton staff 6.6M 4 Oct 18:35 hello $ file ./hello ./hellojava: Mach-O 64-bit executable x86_64 $ time ./hello Hello! real 0m0.010s user 0m0.003s sys 0m0.003s