Fight the Future

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

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

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

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

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

GraalでのPHI

以前SSAそしてPHIとは何かについて学びました。

jyukutyo.hatenablog.com

今回はGraalでのPHIについて調べます。

"static single assignment"で検索すると、org.graalvm.compiler.lir.ssa.SSAUtilクラスを見つけました。

f:id:jyukutyo:20171219111040p:plain

ドキュメンテーションコメントはこうです。PHI(ファイ)のLIRInstructionクラスというのは個別にはない。代わりにPHIはコントロールフローのエッジをまたがる並行コピーとして実装される。特定のマージブロックのPHIにより導入される変数は、ブロックのStandardOp.LabelOpにアタッチされる。先行者からの出力値は先行者のStandardOp.BlockEndOpの入力となる。危機的なエッジはないので、先行者のStandardOp.BlockEndOpはStandardOp.JumpOpに違いないと我々は知っている。

B0 -> B1
   ...
   v0|i = ...
   JUMP ~[v0|i, int[0|0x0]] destination: B0 -> B1
 ________________________________________________
 
 B2 -> B1
   ...
   v1|i = ...
   v2|i = ...
   JUMP ~[v1|i, v2|i] destination: B2 -> B1
 ________________________________________________
 
 B1 <- B0,B2
   [v3|i, v4|i] = LABEL

B1の[v3|i, v4|i]がPHIですが、先行ブロックであるB0、B2とも最後はJUMPになっています。"StandardOp.BlockEndOpはStandardOp.JumpOpに違いない"というのはこうのことだと思います。

StandardOpクラスは"A collection of machine-independent LIR operations, as well as interfaces to be implemented for specific kinds or LIR operations."とあります。マシン依存のないLIR操作のコレクションで、特定の種類もしくはLIRの操作のために実装されるべきインタフェース群です。

BlockEndOpは、このOpがあるブロックのデリミタ、区切りです。適切に定義されたブロックはきっちり1つこの操作を含まなくてはならず、またそれはブロックの最後の操作でなければならない)"Every well formed block must contain exactly one such operation and it must be the last operation in the block.")。

LabelOpはラベルの一を定義するLIR操作、JumpOpは無条件ジャンプを表すLIR操作です。

ではPHIを処理するGraalの実際のコードを見ます。SSAUtilのメソッドです。

    /**
     * Visits each phi value pair of an edge, i.e. the outgoing value from the predecessor and the
     * incoming value to the merge block.
     */
    public static void forEachPhiValuePair(LIR lir, AbstractBlockBase<?> merge, AbstractBlockBase<?> pred, PhiValueVisitor visitor) {
        if (merge.getPredecessorCount() < 2) {
            return;
        }
...
        JumpOp jump = phiOut(lir, pred);
        LabelOp label = phiIn(lir, merge);
...
        for (int i = 0; i < label.getPhiSize(); i++) {
            visitor.visit(label.getIncomingValue(i), jump.getOutgoingValue(i));
        }
    }

実装は上述のドキュメンテーションコメント通りになっています。PHIは分岐などで複数のルートが先行ブロックとしてある場合に、状態をマージして後続ブロックで使えるようにします(つまりたどったブロックの値を使うようにします)。getPredecessorCount()が2未満は先行ブロックが複数なく、マージする必要はありません。phiOut()では先行ブロックの最後のLIR操作、上記の通りJumpOpを取り出します。phiIn()ではマージブロックのLabelOpを取り出します。visitor.visit(label.getIncomingValue(i), jump.getOutgoingValue(i))で、値を移すような何かをしているのでしょうか?

PhiValueVisitorの実装はorg.graalvm.compiler.lir.alloc.lsra.ssa.SSALinearScanResolveDataFlowPhaseにあります。

            PhiValueVisitor visitor = new PhiValueVisitor() {
                @Override
                public void visit(Value phiIn, Value phiOut) {
...
                    Interval toInterval = allocator.splitChildAtOpId(allocator.intervalFor(phiIn), toBlockFirstInstructionId, LIRInstruction.OperandMode.DEF);
                    DebugContext debug = allocator.getDebug();
                    if (isConstantValue(phiOut)) {
                        numPhiResolutionMoves.increment(debug);
                        moveResolver.addMapping(asConstant(phiOut), toInterval);
                    } else {
                        Interval fromInterval = allocator.splitChildAtOpId(allocator.intervalFor(phiOut), phiOutId, LIRInstruction.OperandMode.DEF);
                        if (fromInterval != toInterval && !fromInterval.location().equals(toInterval.location())) {
                            numPhiResolutionMoves.increment(debug);
                            if (!(isStackSlotValue(toInterval.location()) && isStackSlotValue(fromInterval.location()))) {
                                moveResolver.addMapping(fromInterval, toInterval);
                            } else {
                                numStackToStackMoves.increment(debug);
                                moveResolver.addMapping(fromInterval, toInterval);
                            }
                        }
                    }
                }
            };

純化すると、このコードはmoveResolver.addMapping(fromInterval, toInterval);しているだけです。あとはConstantか、fromとtoのインターバルが異なるか、fromかtoがスタックスロットにあるかという判定です。MoveResolver#addMapping()ではインターバル間の値の移動を管理しているようです。