Instruction Selectionでは、LLVM IRを受け取り、それをSelection DAGに変換する。このフェーズは、さらに以下の細かなフェーズに分けることができる。
- LLVM IRをSelection DAGへ変換
- Selection DAGのCombine
- Selection DAGのLegalize
- Selection DAGをMachine Instruction用のDAGに変換
LLVM IRをSelection DAGに変換する
まずは入力されたLLVM IRをSelection DAGのデータフローグラフに変換しなければならない。これを実行するのはSelectionDAGBuilder
というクラスにまとめられており、visit
関数を渡り歩くことによってDAGが生成される。
例えば、以下のようなLLVM IRを入力したものとする。
define i32 @test(i32 %a, i32 %b, i32 %c) { %node1 = add nsw i32 %a, %b %node2 = mul i32 %node1, 1 ret i32 %node2 }
引数としてa, b, c
を受け取り、2つの演算add
, mul
を実行している。これをSelection DAGに変換するためにSelectionDAGBuilder::visit()
を通過していく。
llvm-myriscvx80/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp
void SelectionDAGBuilder::visit(const Instruction &I) { // Set up outgoing PHI node register values before emitting the terminator. ... visit(I.getOpcode(), I); ...
void SelectionDAGBuilder::visit(unsigned Opcode, const User &I) { // Note: this doesn't use InstVisitor, because it has to work with // ConstantExpr's in addition to instructions. switch (Opcode) { default: llvm_unreachable("Unknown instruction type encountered!"); // Build the switch statement using the Instruction.def file. #define HANDLE_INST(NUM, OPCODE, CLASS) \ case Instruction::OPCODE: visit##OPCODE((const CLASS&)I); break; #include "llvm/IR/Instruction.def" } }
上記のコードを見ればわかる通り、visit(unsigned Opcode, const User &I)
ではオペコードによってcase文により訪れるvisit
関数が変わる。最初のadd
演算を変換する場合、visitAdd()
関数が使用される。
llvm-myriscvx80/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.h
//===----------------------------------------------------------------------===// /// SelectionDAGBuilder - This is the common target-independent lowering /// implementation that is parameterized by a TargetLowering object. /// class SelectionDAGBuilder { ... void visitAdd(const User &I) { visitBinary(I, ISD::ADD); } ...
さらにvisitAdd()
はvisitBinary()
を呼び出する。
llvm-myriscvx80/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp
void SelectionDAGBuilder::visitBinary(const User &I, unsigned Opcode) { SDNodeFlags Flags; if (auto *OFBinOp = dyn_cast<OverflowingBinaryOperator>(&I)) { Flags.setNoSignedWrap(OFBinOp->hasNoSignedWrap()); Flags.setNoUnsignedWrap(OFBinOp->hasNoUnsignedWrap()); } if (auto *ExactOp = dyn_cast<PossiblyExactOperator>(&I)) { Flags.setExact(ExactOp->isExact()); } if (isVectorReductionOp(&I)) { Flags.setVectorReduction(true); LLVM_DEBUG(dbgs() << "Detected a reduction operation:" << I << "\n"); } SDValue Op1 = getValue(I.getOperand(0)); SDValue Op2 = getValue(I.getOperand(1)); SDValue BinNodeValue = DAG.getNode(Opcode, getCurSDLoc(), Op1.getValueType(), Op1, Op2, Flags); setValue(&I, BinNodeValue); }
これによりSelectionDAGが作られる。add演算とmul演算を接続した結果、以下のようなSelectionDAGが作られる。
- 黒の線はデータフローの依存関係を示している。
- 赤の線はGlue依存関係、つまりスケジューリングにおいて壊されることを防ぐための順序関係を示している。
- 青の点線は、チェーン依存関係をしめする。ノードを副作用から守るための依存関係である。
Selection DAGのCombine
データフローの最適化に相当する。ここでは、いくつかのノードにおいて複数のノードをまとめる。この処理では、以下のコードに基づいて処理が行われる。
llvm-myriscvx80/lib/CodeGen/SelectionDAG/DAGCombiner.cpp
DAGCombiner::visit()
に、ノードをまとめるための処理が記述されている。
SDValue DAGCombiner::visit(SDNode *N) { switch (N->getOpcode()) { default: break; case ISD::TokenFactor: return visitTokenFactor(N); case ISD::MERGE_VALUES: return visitMERGE_VALUES(N); case ISD::ADD: return visitADD(N); case ISD::SUB: return visitSUB(N); ...
例えば、MULノードのCombine処理のために、visitMUL(N)
が定義されている。
SDValue DAGCombiner::visitMUL(SDNode *N) { SDValue N0 = N->getOperand(0); SDValue N1 = N->getOperand(1); EVT VT = N0.getValueType(); // fold (mul x, undef) -> 0 if (N0.isUndef() || N1.isUndef()) ...
例えば、N0×1の場合は、乗算を行わずにそのままN0を出力する。
// fold (mul x, 1) -> x if (N1IsConst && ConstValue1.isOneValue()) return N0;
上記のsample.llを少し改造して、以下のようにしてみる。
define i32 @test(i32 %a, i32 %b, i32 %c) { %node1 = add nsw i32 %a, %b %node2 = mul i32 %node1, 1 ret i32 %node2 }
mul
演算では、オペランド2を定数の1としたので、この演算は省略できるはずだ。llcの解析結果を見てみると、以下のようなログがあり、ノードが省略されたことが分かる。
Combining: t9: i32 = mul t7, Constant:i32<1> ... into: t7: i32 = add nsw t2, t4
つまり、1つ前のadd
演算とマージされた。DAGをグラフ化すると、以下のようになっている。