FPGA開発日記

カテゴリ別記事インデックス https://msyksphinz.github.io/github_pages , English Version https://fpgadevdiary.hatenadiary.com/

オリジナルLLVMバックエンド実装をまとめる(18. LLVM IRからInstruction Selectionまでの流れ)

Instruction Selectionでは、LLVM IRを受け取り、それをSelection DAGに変換する。このフェーズは、さらに以下の細かなフェーズに分けることができる。

  • LLVM IRをSelection DAGへ変換
  • Selection DAGのCombine
  • Selection DAGのLegalize
  • Selection DAGをMachine Instruction用のDAGに変換
f:id:msyksphinz:20191011014733p:plain
LLVM IRからMachine Instructionが生成されるまでの流れ

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が作られる。

f:id:msyksphinz:20191011014835p:plain:w200
SelectionDAGBuilderが生成したDAGノード
  • 黒の線はデータフローの依存関係を示している。
  • 赤の線は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をグラフ化すると、以下のようになっている。

f:id:msyksphinz:20191011014913p:plain:w200
Combineにより生成されたDAG