JVM（HotSpot VM）におけるIntrinsics（C2/Graal）

Project Loomのソースを読んでいると、また遭遇しました。

public class Continuation {
...
    @HotSpotIntrinsicCandidate
    private static int doYield(int scopes) { throw new Error("Intrinsic not installed"); };
...
}

@HotSpotIntrinsicCandidateアノテーションです。継続の停止処理であるdoYield()メソッドは、エラーをスローする実装になっています。もちろん実際はエラーとならず、停止処理が実行されるわけですが、どうなっているのでしょうか？

僕は、@HotSpotIntrinsicCandidate、あーCPUアーキテクチャごとの処理があって実行されてるんだよね、くらいの認識でそれ以上深めてことはありませんでした。

Twitterで聞いてみました。

@HotSpotIntrinsicCandidateがついているメソッドの、HotSpot側の実際の実装部分はlibrary_call.cppにあるものでしょうか？？

— じゅくちょー Koichi Sakata (@jyukutyo) 2018年8月23日

OpenJDKレビュワーである@YaSuenagさんから教えていただけました！

まずは普通のIntrinsics。例えばString#indexOfなんかはOpenJDKビルド時にADファイルからNodeが自動生成されます https://t.co/hXTGSiexqe それがLibraryCallで組み込まれます https://t.co/LtyHsJNA9e AD定義が複数あるのは使うレジスタや使用条件が違うからだと思いますが、詳しくはわかりません。

— Yasumasa Suenaga (@YaSuenag) 2018年8月23日

ADファイル

ADとは"Architecture Description"のことです。HotSpotにはCPUアーキテクチャごとにADファイルがあります。OpenJDKのsrc/hotspot/cpu以下に各CPUのディレクトリがあります。その中にADファイルがあります。

たとえばx86のディレクトリにはx86.ad、x86_32.ad、x86_64.adがあります。ビルド時にADファイルからIRのノードを生成します。

例: String#indexOf()メソッド

String#indexOf()メソッドを例に調べます。

    static int indexOf(byte[] src, byte srcCoder, int srcCount,
                       String tgtStr, int fromIndex) {
...
        return StringUTF16.indexOf(src, srcCount, tgt, tgtCount, fromIndex);
...
    }

分岐がありますが、indexOfの実際の処理はStringUTF16.indexOf()メソッドなどです。

    @HotSpotIntrinsicCandidate
    public static int indexOf(byte[] value, int valueCount, byte[] str, int strCount, int fromIndex) {
        checkBoundsBeginEnd(fromIndex, valueCount, value);
        checkBoundsBeginEnd(0, strCount, str);
        return indexOfUnsafe(value, valueCount, str, strCount, fromIndex);
    }

@HotSpotIntrinsicCandidateが出てきました。今CPUがx86_64として、x86_64.adを見ます。

instruct string_indexofU(rdi_RegP str1, rdx_RegI cnt1, rsi_RegP str2, rax_RegI cnt2,
                         rbx_RegI result, regD vec, rcx_RegI tmp, rFlagsReg cr)
%{
  predicate(UseSSE42Intrinsics && (((StrIndexOfNode*)n)->encoding() == StrIntrinsicNode::UU));
  match(Set result (StrIndexOf (Binary str1 cnt1) (Binary str2 cnt2)));
  effect(TEMP vec, USE_KILL str1, USE_KILL str2, USE_KILL cnt1, USE_KILL cnt2, KILL tmp, KILL cr);

  format %{ "String IndexOf char[] $str1,$cnt1,$str2,$cnt2 -> $result   // KILL all" %}
  ins_encode %{
    __ string_indexof($str1$$Register, $str2$$Register,
                      $cnt1$$Register, $cnt2$$Register,
                      (-1), $result$$Register,
                      $vec$$XMMRegister, $tmp$$Register, StrIntrinsicNode::UU);
  %}
  ins_pipe( pipe_slow );
%}

string_indexof関数にはUやLの組み合わせが末尾に付きます。UはUTF-16、LはLatin1のようです。中身はほぼ読めませんが、string_indexof()を呼ぶようです。macroAssembler_x86.cppにありました。仕組みがわかっていないので推測でしかないですが、引数の数は合っています。

// Small strings are loaded through stack if they cross page boundary.
void MacroAssembler::string_indexof(Register str1, Register str2,
                                    Register cnt1, Register cnt2,
                                    int int_cnt2,  Register result,
                                    XMMRegister vec, Register tmp,
                                    int ae) {
...
  // Note, inline_string_indexOf() generates checks:
  // if (substr.count > string.count) return -1;
  // if (substr.count == 0) return 0;
...
}

とても長い関数です。もう無理です。視点を変えて、コメントにinline_string_indexOf()がチェックを生成するとあります。この関数はlibrary_call.cppにあります。

...
  case vmIntrinsics::_indexOfL:                 return inline_string_indexOf(StrIntrinsicNode::LL);
  case vmIntrinsics::_indexOfU:                 return inline_string_indexOf(StrIntrinsicNode::UU);
  case vmIntrinsics::_indexOfUL:                return inline_string_indexOf(StrIntrinsicNode::UL);
  case vmIntrinsics::_indexOfIL:                return inline_string_indexOfI(StrIntrinsicNode::LL);
  case vmIntrinsics::_indexOfIU:                return inline_string_indexOfI(StrIntrinsicNode::UU);
  case vmIntrinsics::_indexOfIUL:               return inline_string_indexOfI(StrIntrinsicNode::UL);
  case vmIntrinsics::_indexOfU_char:            return inline_string_indexOfChar();
...
//------------------------------inline_string_indexOf------------------------
bool LibraryCallKit::inline_string_indexOf(StrIntrinsicNode::ArgEnc ae) {
  if (!Matcher::match_rule_supported(Op_StrIndexOf)) {
    return false;
  }
  Node* src = argument(0);
  Node* tgt = argument(1);

  // Make the merge point
  RegionNode* result_rgn = new RegionNode(4);
  Node*       result_phi = new PhiNode(result_rgn, TypeInt::INT);

  // Get start addr and length of source string
  Node* src_start = array_element_address(src, intcon(0), T_BYTE);
  Node* src_count = load_array_length(src);

  // Get start addr and length of substring
  Node* tgt_start = array_element_address(tgt, intcon(0), T_BYTE);
  Node* tgt_count = load_array_length(tgt);

  if (ae == StrIntrinsicNode::UU || ae == StrIntrinsicNode::UL) {
    // Divide src size by 2 if String is UTF16 encoded
    src_count = _gvn.transform(new RShiftINode(src_count, intcon(1)));
  }
  if (ae == StrIntrinsicNode::UU) {
    // Divide substring size by 2 if String is UTF16 encoded
    tgt_count = _gvn.transform(new RShiftINode(tgt_count, intcon(1)));
  }

  Node* result = make_indexOf_node(src_start, src_count, tgt_start, tgt_count, result_rgn, result_phi, ae);
  if (result != NULL) {
    result_phi->init_req(3, result);
    result_rgn->init_req(3, control());
  }
  set_control(_gvn.transform(result_rgn));
  record_for_igvn(result_rgn);
  set_result(_gvn.transform(result_phi));

  return true;
}
...

JITのグラフ、Nodeの世界になりました。Nodeの生成と考えると、make_indexOf_node関数が呼び出されています。

// Create StrIndexOfNode with fast path checks
Node* LibraryCallKit::make_indexOf_node(Node* src_start, Node* src_count, Node* tgt_start, Node* tgt_count,
                                        RegionNode* region, Node* phi, StrIntrinsicNode::ArgEnc ae) {
...
    return make_string_method_node(Op_StrIndexOf, src_start, src_count, tgt_start, tgt_count, ae);
...
}

//------------------------------make_string_method_node------------------------
// Helper method for String intrinsic functions. This version is called with
// str1 and str2 pointing to byte[] nodes containing Latin1 or UTF16 encoded
// characters (depending on 'is_byte'). cnt1 and cnt2 are pointing to Int nodes
// containing the lengths of str1 and str2.
Node* LibraryCallKit::make_string_method_node(int opcode, Node* str1_start, Node* cnt1, Node* str2_start, Node* cnt2, StrIntrinsicNode::ArgEnc ae) {
  Node* result = NULL;
  switch (opcode) {
  case Op_StrIndexOf:
    result = new StrIndexOfNode(control(), memory(TypeAryPtr::BYTES),
                                str1_start, cnt1, str2_start, cnt2, ae);
    break;
...
  }
...
  return _gvn.transform(result);
}

StrIndexOfNodeが作られます。StrIndexOfNodeはintrinsicnode.hppに定義があります。

//------------------------------StrIndexOf-------------------------------------
class StrIndexOfNode: public StrIntrinsicNode {
 public:
  StrIndexOfNode(Node* control, Node* char_array_mem,
                 Node* s1, Node* c1, Node* s2, Node* c2, ArgEncoding encoding):
  StrIntrinsicNode(control, char_array_mem, s1, c1, s2, c2, encoding) {};
  virtual int Opcode() const;
  virtual const Type* bottom_type() const { return TypeInt::INT; }
};

さて、ここまでHotSpot VM、C2コンパイラで見てきました。Graalも見てみます。

Graal

ここのでGraalはJITコンパイラのGraalです。GraalVMのことではありませんのでご注意ください。私はGraalのことを学んでいます。

www.sakatakoichi.com

GraalにおけるIntrinsicsはこちらの論文に詳しいです。私も読みました。

Snippets: Taking the High Road to a Low Level

GraalはJavaで書かれていますので、少なくとも私にとってはC2よりコードは読みやすいです。

さて、String#indexOf()です。今度は逆にグラフのNodeから読みます。GraalはグラフやNodeがとても整理されている印象です。

org.graalvm.compiler.replacements.amd64.AMD64StringIndexOfNodeというクラスがあります。なお、各CPUの実装は、パッケージで分けられているだけではなくモジュールで分けられています。AMD64StringIndexOfNodeクラスはorg.graalvm.compiler.replacements.amd64モジュールにあります。

@NodeInfo(size = SIZE_64, cycles = NodeCycles.CYCLES_UNKNOWN)
public class AMD64StringIndexOfNode extends FixedWithNextNode implements LIRLowerable, MemoryAccess {
...
    @NodeIntrinsic
    public static native int optimizedStringIndexPointer(Pointer sourcePointer, int sourceCount, Pointer targetPointer, int targetCount);
...
}

これがGraalのIRノードです。その中でもLIRとなります。そして、@NodeIntrinsicがIntrinsicsのマークです。

    /**
     * Annotates a method that can be replaced by a compiler intrinsic. A (resolved) call to the
     * annotated method will be processed by a generated {@code InvocationPlugin} that calls either
     * a factory method or a constructor corresponding with the annotated method.
...
     */
    @java.lang.annotation.Retention(RetentionPolicy.RUNTIME)
    @java.lang.annotation.Target(ElementType.METHOD)
    public static @interface NodeIntrinsic {
    }

ドキュメンテーションコメントには"コンパイラのintrinsicで置換できるメソッドをアノテートする。アノテートされたメソッドに対する（解決済みの）呼び出しは、生成されたInvocationPluginによって処理される。InvocationPluginはアノテートされたメソッドに対応するファクトリメソッドもしくはコンストラクタを呼び出す。"とあります。

InvocationPluginおよびそのファクトリは、アノテーションプロセッサでコード生成されます。AMD64StringIndexOfNodeのものは同じくorg.graalvm.compiler.replacements.amd64パッケージです。

public class PluginFactory_AMD64StringIndexOfNode implements NodeIntrinsicPluginFactory {

    private static final class AMD64StringIndexOfNode_optimizedStringIndexPointer extends GeneratedInvocationPlugin {

        @Override
        public boolean execute(GraphBuilderContext b, ResolvedJavaMethod targetMethod, InvocationPlugin.Receiver receiver, ValueNode[] args) {
            ValueNode arg0 = args[0];
            ValueNode arg1 = args[1];
            ValueNode arg2 = args[2];
            ValueNode arg3 = args[3];
            org.graalvm.compiler.replacements.amd64.AMD64StringIndexOfNode node = new org.graalvm.compiler.replacements.amd64.AMD64StringIndexOfNode(arg0, arg1, arg2, arg3);
            b.addPush(JavaKind.Int, node);
            return true;
        }
        @Override
        public Class<? extends Annotation> getSource() {
            return org.graalvm.compiler.graph.Node.NodeIntrinsic.class;
        }
    }

    @Override
    public void registerPlugins(InvocationPlugins plugins, InjectionProvider injection) {
        plugins.register(new AMD64StringIndexOfNode_optimizedStringIndexPointer(), org.graalvm.compiler.replacements.amd64.AMD64StringIndexOfNode.class, "optimizedStringIndexPointer", org.graalvm.word.Pointer.class, int.class, org.graalvm.word.Pointer.class, int.class);
    }
}

registerPlugins()メソッドはHotSpotBackendFactoryインタフェースの各CPUアーキテクチャ用実装クラスから呼び出されます。これはコンパイラオブジェクト生成時に呼び出される処理です。

結局どのように処理されるのかというと、以下のようになります。

1. AMD64StringIndexOfNode.optimizedStringIndexPointer()メソッドが呼び出される。
2. @NodeIntrinsicがあるメソッドのため、処理はインターセプトされInvocationPluginの実装であるAMD64StringIndexOfNode_optimizedStringIndexPointerオブジェクトが生成される。
3. AMD64StringIndexOfNode_optimizedStringIndexPointer#execute()メソッドが呼び出される。

もともとint optimizedStringIndexPointer()とintを返すメソッドですが、AMD64StringIndexOfNode_optimizedStringIndexPointerではboolean execute()とbooleanを返しています。これは、execute()メソッド内で元のメソッドの戻り値の型をNodeとともにGraphBuilderContextにpushするので大丈夫です。このbooleanは元のメソッドを自分が処理できるか、（処理内容をインライン化した場合など）処理できないかを返すものです。

最終的には、LIRのNodeをグラフにpushしたことで、emit時にCPU（今回ならAMD64）向けのマシンコードが生成されることになります。

感想

@YaSuenagさんから学ぶヒントをいただけて、少し知識が深まりました。ありがとうございます！

JVM開発に関わるさまざまな方々からC2はつらい旨を聞いていたのですが、その一端は理解できた気がします。これを拡張していくのは…

そしてGraalはやはりJavaで書かれていることと同時にグラフやNode、今回触れていないSnippetなどで設計やコードが整理されていて、読みやすいです。こうして読み進めて、自分もJVM開発に携わりたい！！