Fight the Future

Java言語とJVM、そしてJavaエコシステム全般にまつわること

プレゼン、ボランティアコーチします!

勉強会で話したいけど、プレゼンが初めて、苦手という方に無償でコーチします!

  • スライドのレビュー
  • 録画リハへのアドバイス

Twitter@jyukutyoまでメンションでもDMでも。 デブサミやJJUG CCCなど200人規模で登壇しました。海外での登壇も短いながらあり。デブサミ2017では公募スピーカー1位でした!

GraalのJavaバイトコードからグラフ生成の実装

今回はGraalのJavaバイトコードからグラフ生成の処理を、JVMCIコンパイラの実装クラスであるorg.graalvm.compiler.hotspot.HotSpotGraalCompilerから見ていきます。

    /**
     * Gets a graph produced from the intrinsic for a given method that can be compiled and
     * installed for the method.
...
     */
    public StructuredGraph getIntrinsicGraph(ResolvedJavaMethod method, HotSpotProviders providers, CompilationIdentifier compilationId, OptionValues options, DebugContext debug) {
        Replacements replacements = providers.getReplacements();
        Bytecode subst = replacements.getSubstitutionBytecode(method);
        if (subst != null) {
            ResolvedJavaMethod substMethod = subst.getMethod();
            assert !substMethod.equals(method);
            StructuredGraph graph = new StructuredGraph.Builder(options, debug, AllowAssumptions.YES).method(substMethod).compilationId(compilationId).build();
...

org.graalvm.compiler.nodes.StructuredGraph.Builder#build()メソッドです。ビルダーパターンです。

        public StructuredGraph build() {
            return new StructuredGraph(name, rootMethod, entryBCI, assumptions, speculationLog, useProfilingInfo, compilationId, options, debug, cancellable);
        }

単純にコンストラクタ呼び出しですね。

    private StructuredGraph(String name,
                    ResolvedJavaMethod method,
                    int entryBCI,
                    Assumptions assumptions,
                    SpeculationLog speculationLog,
                    boolean useProfilingInfo,
                    CompilationIdentifier compilationId,
                    OptionValues options,
                    DebugContext debug,
                    Cancellable cancellable) {
        super(name, options, debug);
        this.setStart(add(new StartNode()));
        this.rootMethod = method;
        this.graphId = uniqueGraphIds.incrementAndGet();
        this.compilationId = compilationId;
        this.entryBCI = entryBCI;
        this.assumptions = assumptions;
        this.speculationLog = speculationLog;
        this.useProfilingInfo = useProfilingInfo;
        this.cancellable = cancellable;
    }

this.setStart(add(new StartNode()));で開始ノードを作っていることはわかります。スーパークラスorg.graalvm.compiler.graph.Graphのコンストラクタも見ます。

    /**
     * Creates an empty Graph with a given name.
     *
     * @param name the name of the graph, used for debugging purposes
     */
    public Graph(String name, OptionValues options, DebugContext debug) {
        nodes = new Node[INITIAL_NODES_SIZE];
        iterableNodesFirst = new ArrayList<>(NodeClass.allocatedNodeIterabledIds());
        iterableNodesLast = new ArrayList<>(NodeClass.allocatedNodeIterabledIds());
        this.name = name;
        this.options = options;
        assert debug != null;
        this.debug = debug;

        if (isModificationCountsEnabled()) {
            nodeModCounts = new int[INITIAL_NODES_SIZE];
            nodeUsageModCounts = new int[INITIAL_NODES_SIZE];
        }
    }

とくにグラフノードを作っている様子もありません。

このグラフオブジェクトに、バイトコードのパース結果を追加するのは別のコードです。org.graalvm.compiler.hotspot.HotSpotGraalCompilerに戻ります。

    public CompilationResult compile(ResolvedJavaMethod method, int entryBCI, boolean useProfilingInfo, CompilationIdentifier compilationId, OptionValues options, DebugContext debug) {
        StructuredGraph graph = createGraph(method, entryBCI, useProfilingInfo, compilationId, options, debug);
        CompilationResult result = new CompilationResult(compilationId);
        return compileHelper(CompilationResultBuilderFactory.Default, result, graph, method, entryBCI, useProfilingInfo, options);
    }

グラフオブジェクトを作ったあと、compileHelper()を呼び出します。

    public CompilationResult compileHelper(CompilationResultBuilderFactory crbf, CompilationResult result, StructuredGraph graph, ResolvedJavaMethod method, int entryBCI, boolean useProfilingInfo,
                    OptionValues options) {

        HotSpotBackend backend = graalRuntime.getHostBackend();
        HotSpotProviders providers = backend.getProviders();
...
        Suites suites = getSuites(providers, options);
        LIRSuites lirSuites = getLIRSuites(providers, options);
        ProfilingInfo profilingInfo = useProfilingInfo ? method.getProfilingInfo(!isOSR, isOSR) : DefaultProfilingInfo.get(TriState.FALSE);
        OptimisticOptimizations optimisticOpts = getOptimisticOpts(profilingInfo, options);
...
        result.setEntryBCI(entryBCI);
        boolean shouldDebugNonSafepoints = providers.getCodeCache().shouldDebugNonSafepoints();
        PhaseSuite<HighTierContext> graphBuilderSuite = configGraphBuilderSuite(providers.getSuites().getDefaultGraphBuilderSuite(), shouldDebugNonSafepoints, isOSR);
        GraalCompiler.compileGraph(graph, method, providers, backend, graphBuilderSuite, optimisticOpts, profilingInfo, suites, lirSuites, result, crbf);
...

GraalCompiler.compileGraph()の呼び出しがあります。その前にconfigGraphBuilderSuite()PhaseSuiteを作っています。PhaseSuiteは独立した処理(Phase)をまとめるスイートです。JUnitでのテストスイートみたいな感じです。そのPhaseの1つに、org.graalvm.compiler.java.GraphBuilderPhaseがあります。GraphBuilderPhaseJavaバイトコードをIRグラフにパースします。PhaseSuiteは保持しているPhaseを順番に呼び出していきます。

    private List<BasePhase<? super C>> phases;
...
    protected void run(StructuredGraph graph, C context) {
        for (BasePhase<? super C> phase : phases) {
            phase.apply(graph, context);
        }
    }

さてGraphBuilderPhaseを見ます。

/**
 * Parses the bytecodes of a method and builds the IR graph.
 */
public class GraphBuilderPhase extends BasePhase<HighTierContext> {
...
    @Override
    protected void run(StructuredGraph graph, HighTierContext context) {
        new Instance(context.getMetaAccess(), context.getStampProvider(), context.getConstantReflection(), context.getConstantFieldProvider(), graphBuilderConfig, context.getOptimisticOptimizations(),
                        null).run(graph);
    }

このInstanceGraphBuilderPhaseのstaticネストクラスです。

    // Fully qualified name is a workaround for JDK-8056066
    public static class Instance extends org.graalvm.compiler.phases.Phase {
...
        @Override
        protected void run(StructuredGraph graph) {
            createBytecodeParser(graph, null, graph.method(), graph.getEntryBCI(), initialIntrinsicContext).buildRootMethod();
        }

        /* Hook for subclasses of Instance to provide a subclass of BytecodeParser. */
        protected BytecodeParser createBytecodeParser(StructuredGraph graph, BytecodeParser parent, ResolvedJavaMethod method, int entryBCI, IntrinsicContext intrinsicContext) {
            return new BytecodeParser(this, graph, parent, method, entryBCI, intrinsicContext);
        }

ちなみに、GraalのコードにはこのInstancestaticネストクラスが頻発します。org.graalvm.compiler.java.BytecodeParserを見ましょう。

    protected BytecodeParser(GraphBuilderPhase.Instance graphBuilderInstance, StructuredGraph graph, BytecodeParser parent, ResolvedJavaMethod method,
                    int entryBCI, IntrinsicContext intrinsicContext) {
        this.bytecodeProvider = intrinsicContext == null ? new ResolvedJavaMethodBytecodeProvider() : intrinsicContext.getBytecodeProvider();
        this.code = bytecodeProvider.getBytecode(method);
        this.method = code.getMethod();
...
        this.stream = new BytecodeStream(code.getCode());
...
    }

this.codeはJVMCIのResolvedJavaMethodをラップするorg.graalvm.compiler.bytecode.ResolvedJavaMethodBytecodeオブジェクトです。ResolvedJavaMethodBytecodeからgetCode()すると、Javaバイトコードのバイト配列が取得できます。このバイト配列をorg.graalvm.compiler.bytecode.BytecodeStreamのコンストラクタに渡します。

/**
 * A utility class that makes iterating over bytecodes and reading operands simpler and less error
 * prone. For example, it handles the {@link Bytecodes#WIDE} instruction and wide variants of
 * instructions internally.
 */
public final class BytecodeStream {

    private final byte[] code;
    private int opcode;
    private int curBCI;
    private int nextBCI;

    /**
     * Creates a new {@code BytecodeStream} for the specified bytecode.
     *
     * @param code the array of bytes that contains the bytecode
     */
    public BytecodeStream(byte[] code) {
        assert code != null;
        this.code = code;
        setBCI(0);
    }

BCIはByteCode Index(バイトコードインデックス)です。BytecodeStreamからJavaバイトコード命令を1つずつ取り出せます。

    /**
     * Advances to the next bytecode.
     */
    public void next() {
        setBCI(nextBCI);
    }
...
   /**
     * Sets the bytecode index to the specified value. If {@code bci} is beyond the end of the
     * array, {@link #currentBC} will return {@link Bytecodes#END} and other methods may throw
     * {@link ArrayIndexOutOfBoundsException}.
     *
     * @param bci the new bytecode index
     */
    public void setBCI(int bci) {
        curBCI = bci;
        if (curBCI < code.length) {
            opcode = Bytes.beU1(code, bci);
            assert opcode < Bytecodes.BREAKPOINT : "illegal bytecode";
            nextBCI = bci + lengthOf();
        } else {
            opcode = Bytecodes.END;
            nextBCI = curBCI;
        }
    }
...
    /**
     * Gets the current opcode. This method will never return the {@link Bytecodes#WIDE WIDE}
     * opcode, but will instead return the opcode that is modified by the {@code WIDE} opcode.
     *
     * @return the current opcode; {@link Bytecodes#END} if at or beyond the end of the code
     */
    public int currentBC() {
        if (opcode == Bytecodes.WIDE) {
            return Bytes.beU1(code, curBCI + 1);
        } else {
            return opcode;
        }
    }

next()しつつcurrentBC()バイトコードを取り出し、Bytecodes.ENDで終了です。BytecodesJVM仕様にあるバイトコードをすべて定数として持っています。

/**
 * Definitions of the standard Java bytecodes defined by
 * <a href= "http://java.sun.com/docs/books/jvms/second_edition/html/VMSpecTOC.doc.html"> Java
 * Virtual Machine Specification</a>.
 */
public class Bytecodes {

    public static final int NOP                  =   0; // 0x00
    public static final int ACONST_NULL          =   1; // 0x01
    public static final int ICONST_M1            =   2; // 0x02
...

org.graalvm.compiler.java.BytecodeParserに戻ります。buildRootMethod()を通じて、Javaバイトコードをパースしてグラフに追加していきます。

    protected void buildRootMethod() {
        FrameStateBuilder startFrameState = new FrameStateBuilder(this, code, graph);
        startFrameState.initializeForMethodStart(graph.getAssumptions(), graphBuilderConfig.eagerResolving() || intrinsicContext != null, graphBuilderConfig.getPlugins());

        try (IntrinsicScope s = intrinsicContext != null ? new IntrinsicScope(this) : null) {
            build(graph.start(), startFrameState);
        }
...
    }

    protected void build(FixedWithNextNode startInstruction, FrameStateBuilder startFrameState) {
...
            // compute the block map, setup exception handlers and get the entrypoint(s)
            BciBlockMapping newMapping = BciBlockMapping.create(stream, code, options, graph.getDebug());
...
    }

buildRootMethod()build()を呼び出します。そこでまずBciBlockMappingオブジェクトを作ります。単純に言うとBciBlockMappingBciBlockのコンテナです。BciBlockは、Javaバイトコード1つにつき1つ作成します。バイトコードのインデックスと、対応するバイトコード命令を持っているイメージです。

    protected void build(FixedWithNextNode startInstruction, FrameStateBuilder startFrameState) {
...
            // compute the block map, setup exception handlers and get the entrypoint(s)
            BciBlockMapping newMapping = BciBlockMapping.create(stream, code, options, graph.getDebug());
...
            BciBlock[] blocks = blockMap.getBlocks();
            for (BciBlock block : blocks) {
                processBlock(block);
            }
    }

大部分のコードを省略すると、上記のようになります。各BciBlock対してprocessBlock()を呼び出します。

    protected void processBlock(BciBlock block) {
...
        iterateBytecodesForBlock(block);
    }

    protected void iterateBytecodesForBlock(BciBlock block) {
...
        int bci = block.startBci;
...
        stream.setBCI(block.startBci);
...
        int opcode = stream.currentBC();
...
         processBytecode(bci, opcode);
    }

BytecodeStreamも使いつつ、このブロックからbciとオペコードを取り出し、いくつもメソッドを経由して、processBytecode()を呼び出します。

    public final void processBytecode(int bci, int opcode) {
        int cpi;
        switch (opcode) {
            case NOP            : /* nothing to do */ break;
            case ACONST_NULL    : frameState.push(JavaKind.Object, appendConstant(JavaConstant.NULL_POINTER)); break;
            case ICONST_M1      : // fall through
            case ICONST_0       : // fall through
...
            case INVOKEVIRTUAL  : cpi = stream.readCPI(); genInvokeVirtual(cpi, opcode); break;
            case INVOKESPECIAL  : cpi = stream.readCPI(); genInvokeSpecial(cpi, opcode); break;
            case INVOKESTATIC   : cpi = stream.readCPI(); genInvokeStatic(cpi, opcode); break;
            case INVOKEINTERFACE: cpi = stream.readCPI(); genInvokeInterface(cpi, opcode); break;
            case INVOKEDYNAMIC  : cpi = stream.readCPI4(); genInvokeDynamic(cpi, opcode); break;
...
    }

cpiはコンスタントプールのインデックスです(Constant Pool Index)。オペコードでの単純なswitch文です。各ケースでのgenInvoke...()内は難しいコードで何のために何をやっているのか読めませんでしたが、こんな感じでグラフにノードを追加している部分はありました。

    protected Invoke createNonInlinedInvoke(ExceptionEdgeAction exceptionEdge, int invokeBci, ValueNode[] invokeArgs, ResolvedJavaMethod targetMethod,
                    InvokeKind invokeKind, JavaKind resultType, JavaType returnType, JavaTypeProfile profile) {
...
        MethodCallTargetNode callTarget = graph.add(createMethodCallTarget(invokeKind, targetMethod, invokeArgs, returnStamp, profile));
 ...
    }

ひとまず、Javaバイトコードからグラフ生成の実装は超おおまかにつかめました。

GraalでAOTする

GraalでAOT(Ahead Of Time)コンパイルしました。GraalはJava 9でのAOT実装としても使われています。Java 9ではLinuxのみjaotcコマンドがありAOTコンパイルできますが、GraalではMacでもできました。バイトコードをマシンコードにするのがJITコンパイルである以上、これをAOTの実装としても利用できるというのはイメージしやすいです。

実行時間も計測してみるため、サンプルとして以下のコードを使います。

import java.math.BigInteger;

public class Factorial {

    public static BigInteger factorial(int n) {
        BigInteger p = BigInteger.valueOf(1);
        while (n > 0) {
            p = p.multiply(BigInteger.valueOf(n));
            n = n - 1;
        }
        return p;
    }

    public static void main(String[] args) {
        System.out.println(factorial(Integer.parseInt(args[0])));
    }
}

javaコマンドで実行してみます。

$ time java Factorial 100
93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000
java Factorial 100  0.08s user 0.03s system 88% cpu 0.118 total

さて、AOTコンパイルしてネイティブイメージを作ります。

$ export PATH=[graalvm-0.28.2]/bin:$PATH

$ native-image -H:Name=fac -H:Class=Factorial
   classlist:   1,967.73 ms
       (cap):   1,656.13 ms
       setup:   2,947.44 ms
  (typeflow):   3,652.14 ms
   (objects):   1,199.91 ms
  (features):      11.76 ms
    analysis:   5,002.74 ms
    universe:     397.06 ms
     (parse):   1,028.24 ms
    (inline):   1,949.47 ms
   (compile):  12,080.05 ms
     compile:  15,468.37 ms
       image:   2,879.35 ms
   debuginfo:   1,001.58 ms
       write:   5,711.16 ms
     [total]:  34,449.74 ms

native-imageコマンドで作れます。Nameに指定した値がファイル名となります。Classは対象のクラスです。

$ ls -lat
...
-rwxr-xr-x   1 jyukutyo  jyukutyo  6844468 12 19 19:36 fac

$ time ./fac 100
93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000
./fac 100  0.00s user 0.01s system 66% cpu 0.014 total

こういった短時間で終わる処理は早くなります。サーバレスと相性がよさそうです!