以前SSAそしてPHIとは何かについて学びました。
今回はGraalでのPHIについて調べます。
"static single assignment"で検索すると、org.graalvm.compiler.lir.ssa.SSAUtilクラスを見つけました。
ドキュメンテーションコメントはこうです。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()ではインターバル間の値の移動を管理しているようです。
