FPGA開発日記

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

オリジナルLLVMバックエンド実装をまとめる(21. ByVal属性のついた引数を扱うための処理2)

前回の続き。

ByVal属性の引数における呼び出し側の処理

それでは、次に呼び出し側はどのようになっているのだろうか。 呼び出し側でも、ByVal属性のついた引数を一つ一つコピーして関数呼び出され側に渡す必要がある。 関数呼び出し側は、MYRISCVXTargetLowering::LowerCall()を改造するのだった。

  • llvm-myriscvx80/lib/Target/MYRISCVX/MYRISCVXISelLowering.cpp
SDValue
MYRISCVXTargetLowering::LowerCall(TargetLowering::CallLoweringInfo &CLI,
                                  SmallVectorImpl<SDValue> &InVals) const {
  // Check if it's really possible to do a tail call.
  if (IsTailCall)
    IsTailCall = isEligibleForTailCallOptimization(CCInfo, CLI, MF, ArgLocs);
...
  CCInfo.rewindByValRegsInfo();
...
  for (unsigned i = 0, e = ArgLocs.size(); i != e; ++i) {
...
    if (Flags.isByVal()) {
      unsigned FirstByValReg, LastByValReg;
      unsigned ByValIdx = CCInfo.getInRegsParamsProcessed();

      CCInfo.getInRegsParamInfo(ByValIdx, FirstByValReg, LastByValReg);

      assert(Flags.getByValSize() &&
             "ByVal args of size 0 should have been ignored by front-end.");
      assert(ByValIdx < CCInfo.getInRegsParamsCount());
      assert(!IsTailCall &&
             "Do not tail-call optimize if there is a byval argument.");
      passByValArg(Chain, DL, RegsToPass, MemOpChains, StackPtr, MFI, DAG, Arg,
                   CCInfo, FirstByValReg, LastByValReg, Flags, Subtarget.isLittle(), VA);
      CCInfo.nextInRegsParam();
      continue;
    }
...
    

LowerFormalArgumetsと内容は似ている。isByVal()フラグが立っているとByVal属性の処理が開始され、FirstByValRegsLastByValRegsに引数渡しに使用されるレジスタが設定される。これはHandleByValで処理したものと同様である。

f:id:msyksphinz:20191012021248p:plain
ByVal属性の引数を関数呼び出され側での取り扱い。CallOperands()で解析し、HandleByVal()を呼ぶ。

LowerCall()では、copyByValRegsとは逆に、passByValArgsを呼び出して、引数をコピーしていきます。

  • llvm-myriscvx80/lib/Target/MYRISCVX/MYRISCVXISelLowering.cpp
void MYRISCVXTargetLowering::
passByValArg(SDValue Chain, const SDLoc &DL,
             std::deque< std::pair<unsigned, SDValue> > &RegsToPass,
             SmallVectorImpl<SDValue> &MemOpChains, SDValue StackPtr,
             MachineFrameInfo &MFI, SelectionDAG &DAG, SDValue Arg,
             const CCState &CC, unsigned FirstReg, unsigned LastReg,
             const ISD::ArgFlagsTy &Flags, bool isLittle,
             const CCValAssign &VA) const {
...
      if (NumRegs) {
    const ArrayRef<MCPhysReg> ArgRegs = ABI.GetByValArgRegs();
    bool LeftoverBytes = (NumRegs * RegSizeInBytes > ByValSizeInBytes);
    unsigned I = 0;

    // レジスタに引数の値をコピーしていく。
    for (; I < NumRegs - LeftoverBytes;
         ++I, OffsetInBytes += RegSizeInBytes) {
      // オフセットの計算
      SDValue LoadPtr = DAG.getNode(ISD::ADD, DL, PtrTy, Arg,
                                    DAG.getConstant(OffsetInBytes, DL, PtrTy));
      // 引数レジスタに値をコピーしていく。
      SDValue LoadVal = DAG.getLoad(RegTy, DL, Chain, LoadPtr,
                                    MachinePointerInfo());
      MemOpChains.push_back(LoadVal.getValue(1));
      unsigned ArgReg = ArgRegs[FirstReg + I];
      RegsToPass.push_back(std::make_pair(ArgReg, LoadVal));
    }
...
  // byval属性にもかかわらず引数レジスタに入りきらなかったものについては、memcpyでスタックにコピーしていく。
  unsigned MemCpySize = ByValSizeInBytes - OffsetInBytes;
  SDValue Src = DAG.getNode(ISD::ADD, DL, PtrTy, Arg,
                            DAG.getConstant(OffsetInBytes, DL, PtrTy));
  SDValue Dst = DAG.getNode(ISD::ADD, DL, PtrTy, StackPtr,
                            DAG.getIntPtrConstant(VA.getLocMemOffset(), DL));
  Chain = DAG.getMemcpy(Chain, DL, Dst, Src,
                        DAG.getConstant(MemCpySize, DL, PtrTy),
                        Alignment, /*isVolatile=*/false, /*AlwaysInline=*/false,
                        /*isTailCall=*/false,
                        MachinePointerInfo(), MachinePointerInfo());
  MemOpChains.push_back(Chain);

レジスタに入りきらかなった引数は、なんとmemcpyを呼び出して一気にスタックにコピーする。これで、ByValに対する処理は完了である。

f:id:msyksphinz:20191012021318p:plain
LowerCall()において、ByVal属性の引数を見つけるとpassByValRegs()が呼び出される。

ByVal属性生成の特殊条件の追加

後で説明しますが、ByVal属性の引数が存在しているときは最適化の一つであるTail Call Optimizationが使用できない。このための条件判断のために、MYRISCVXTargetLowering::isEligibleForTailCallOptimization()を追加して、条件判断を行う。

  • llvm-myriscvx80/lib/Target/MYRISCVX/MYRISCVXISelLowering.cpp
/// isEligibleForTailCallOptimization - Check whether the call is eligible
/// for tail call optimization.
bool MYRISCVXTargetLowering::isEligibleForTailCallOptimization(
    CCState &CCInfo, CallLoweringInfo &CLI, MachineFunction &MF,
    const SmallVector<CCValAssign, 16> &ArgLocs) const {
  auto &Outs = CLI.Outs;

  // Byval parameters hand the function a pointer directly into the stack area
  // we want to reuse during a tail call. Working around this *is* possible
  // but less efficient and uglier in LowerCall.
  for (auto &Arg : Outs)
    if (Arg.Flags.isByVal())
      return false;

  return true;
}

実行結果の確認

それでは、上記のコードをコンパイルしてアセンブリを生成してみる。

./bin/llc -stats -debug -march=myriscvx32 -filetype=asm func_struct_simple.bc -o -
  • func() (関数呼び出され側)
_Z4func1S:
...
# %bb.0:                                # %entry
        addi    x2, x2, -32
        .cfi_def_cfa_offset 32
        addi    x5, x2, 0
        # レジスタ渡しした値をすべてスタックにコピーする。
        addi    x6, x5, 28
        sw      x17, 0(x6)
        addi    x17, x5, 24
        sw      x16, 0(x17)
        addi    x16, x5, 20
        sw      x15, 0(x16)
        addi    x15, x5, 16
        sw      x14, 0(x15)
        addi    x14, x5, 12
        sw      x13, 0(x14)
        addi    x13, x5, 8
        sw      x12, 0(x13)
        ori     x12, x5, 4
        sw      x11, 0(x12)
        addi    x11, zero, 0
        sw      x10, 0(x2)
        addi    x10, x11, 0
...
  • call_func() (関数呼び出し側)
...
        jal     memcpy         # レジスタ渡しができない値をすべてmemcpyでスタックにコピーする。
        addi    x10, x9, 28
        lw      x17, 0(x10)    # レジスタ渡しする値をレジスタにコピー x[7]
        addi    x10, x9, 24
        lw      x16, 0(x10)    # レジスタ渡しする値をレジスタにコピー x[6]
        addi    x10, x9, 20
        lw      x15, 0(x10)    # レジスタ渡しする値をレジスタにコピー x[5]
        addi    x10, x9, 16
        lw      x14, 0(x10)    # レジスタ渡しする値をレジスタにコピー x[4]
        addi    x10, x9, 12
        lw      x13, 0(x10)    # レジスタ渡しする値をレジスタにコピー x[3]
        addi    x10, x9, 8
        lw      x12, 0(x10)    # レジスタ渡しする値をレジスタにコピー x[2]
        ori     x10, x9, 4
        lw      x11, 0(x10)    # レジスタ渡しする値をレジスタにコピー x[1]
        lw      x10, 40(x2)    # レジスタ渡しする値をレジスタにコピー x[0]
        jal     _Z4func1S   # 関数呼び出し
...

オリジナルLLVMバックエンド実装をまとめる(20. ByVal属性のついた引数を扱うための処理)

今までの関数処理の中で、引数は基本的にポインタか値渡し、そして値も何らかの型の値を1つずつ渡していくという形式だった。 しかし、C言語では構造体などの複数の要素をまとめた型を渡すことができる。また、C言語では構造体の値をそのまま値渡しで引数として渡すことができる。

  • func_struct_simple.cpp
struct S
{
  int x[17];
};

void func (struct S elem) {
  for(int i = 0; i < 17; i++) {
    elem.x[i] ++;
  }
}

void call_func () {
  struct S elem;
  for (int i = 0; i < 17; i++) {
    elem.x[i] = i;
  }
  func (elem);
}

上記のプログラムでは、funcに構造体struct S elemを値渡ししている。 つまり、func内でstruct S elemの変更を行っても、その変更の結果は関数の呼び出し側にの値に影響を与えない。 ポインタではないのでアセンブリ的には、引数の要素を一つ一つコピーして、関数呼び出され側に値を渡してやる必要がある。

上記の例では、実際に渡さなければならない値はx[17]の17個である。 しかしMYRISCVXのABIでは引数渡しで使用できるレジスタの数はA0-A7の8個までである。この場合、どのようにして構造体の値を渡していけば良いだろうか。

まず、clangでbyval属性の引数が生成されることを確認すう。上記のfunc_struct_simple.cppをclangでLLVM IRを生成する。

./bin/clang -O1 func_struct_simple.cpp -c -emit-llvm # -target=riscv32-unknown-elfではbyval属性が出ないので、何もオプションを付けない。
./bin/llvm-dis func_struct_simple.bc -o -
%struct.S = type { [17 x i32] }
; byval属性が引数に付加された。
define dso_local void @_Z4func1S(%struct.S* byval nocapture align 8 %elem) #0 {
entry:
  br label %for.body
...

define dso_local void @_Z9call_funcv() #0 {
...
  ; 呼び出し側の引数にbyval属性が追加された
  call void @_Z4func1S(%struct.S* byval align 8 %agg.tmp)

引数にbyval属性が付加されていることが分かる。byval属性が付加されている引数には、特別な処理を付け加える。

  1. CallingConvの定義を修正して、ByVal属性の引数が入ってきたときの挙動を変える。
  2. MYRISCVXTargetLowering::HandleByVal()を実装して、ByVal属性の挙動を実装する。
  3. MYRISCVXTargetLowering::LowerFormalArguments()の実装を追加して、ByVal属性の引数を受け取った場合の挙動を追加する。
f:id:msyksphinz:20191012020813p:plain
構造体を値渡しで呼んだ場合の引数の処理。ByVal属性が付属される。一部はレジスタ渡し、残りはスタック渡しされる。

呼び出され側の処理

CallingConvの修正

まず、呼び出し規約の定義を修正して、ByVal属性の引数が入ってきたときは特殊な処理を行うように変更する。 MYRISCVXCallingConv.tdを修正するわけだが、ByVal属性の時に動きを変える特殊な命令を記述する。

  • llvm-myriscvx80/lib/Target/MYRISCVX/MYRISCVXCallingConv.td
def CC_LP32 : CallingConv<[
  // Promote i8/i16 arguments to i32.
  CCIfType<[i1, i8, i16], CCPromoteToType<i32>>,

  // Put ByVal arguments directly on the stack. Minimum size and alignment of a
  // slot is 32-bit.
  CCIfByVal<CCPassByVal<4, 4>>,
...

def CC_STACK32 : CallingConv<[
  // Promote i8/i16 arguments to i32.
  CCIfType<[i1, i8, i16], CCPromoteToType<i32>>,

  // Put ByVal arguments directly on the stack. Minimum size and alignment of a
  // slot is 32-bit.
  CCIfByVal<CCPassByVal<4, 4>>,
...

上記ではCC_LP32CC_STACK32のみを示したが、CC_LP64およびCC_STACK64にも同様の記述を行う。 CCIfByValという記述を追加した。 これにより、ByVal属性の引数が与えられたときはCCPassByValが呼び出される。 具体的にいうと、生成されたMYRISCVXGenCallingConv.incに以下のような条件文が追加されている。

  • build-myriscvx80/lib/Target/MYRISCVX/MYRISCVXGenCallingConv.inc
static bool CC_LP32(unsigned ValNo, MVT ValVT,
                    MVT LocVT, CCValAssign::LocInfo LocInfo,
                    ISD::ArgFlagsTy ArgFlags, CCState &State) {
...
  if (ArgFlags.isByVal()) {
    State.HandleByVal(ValNo, ValVT, LocVT, LocInfo, 4, 4, ArgFlags);
    return false;
  }
...

CCpasByValにより、State.HandleByValが呼び出される。 これはMYRISCVXTargetLoweringに記述する。

  • llvm-myriscvx80/lib/Target/MYRISCVX/MYRISCVXISelLowering.cpp
void MYRISCVXTargetLowering::HandleByVal(CCState *State, unsigned &Size,
                                         unsigned Align) const
{
...
  if (State->getCallingConv() != CallingConv::Fast) {
    unsigned RegSizeInBytes = Subtarget.getGPRSizeInBytes();
    ArrayRef<MCPhysReg> IntArgRegs = ABI.GetByValArgRegs();
...
    // 割り当てられていない引数渡しレジスタを取得する。
    FirstReg = State->getFirstUnallocated(IntArgRegs);
...
    // 引数の数だけ引数渡しレジスタを割り当てる。
    Size = alignTo(Size, RegSizeInBytes);
    for (unsigned I = FirstReg; Size > 0 && (I < IntArgRegs.size());
         Size -= RegSizeInBytes, ++I, ++NumRegs) {
      State->AllocateReg(IntArgRegs[I], ShadowRegs[I]);
    }
  }
  // CallingConvの情報に、ByValRegsの情報を登録。
  State->addInRegsParamInfo(FirstReg, FirstReg + NumRegs);
}
f:id:msyksphinz:20191012020954p:plain
ByVal属性の引数を関数呼び出され側での取り扱い。AnalyzeFormalArguments()で解析し、HandleByVal()を呼ぶ。

LowerFormalArguments()の修正

次に、関数呼び出され側の引数を解析するためのLowerFormalArgumets()を編集する。引数の解析にByvalの条件を追加する。

  • llvm-myriscvx80/lib/Target/MYRISCVX/MYRISCVXISelLowering.cpp
SDValue
MYRISCVXTargetLowering::LowerFormalArguments (SDValue Chain,
                                              CallingConv::ID CallConv,
                                              bool IsVarArg,
                                              const SmallVectorImpl<ISD::InputArg> &Ins,
                                              const SDLoc &DL, SelectionDAG &DAG,
                                              SmallVectorImpl<SDValue> &InVals) const {

...
  CCInfo.rewindByValRegsInfo();
...
  // 引数毎に処理を行うループ
  for (unsigned i = 0, e = ArgLocs.size(); i != e; ++i) {
    ...
    ISD::ArgFlagsTy Flags = Ins[i].Flags;
    ...
    // ByVal属性がついているかチェックする
    if (Flags.isByVal()) {
      assert(Ins[i].isOrigArg() && "Byval arguments cannot be implicit");
      CCInfo.getInRegsParamInfo(ByValIdx, FirstByValReg, LastByValReg);

      assert(Flags.getByValSize() &&
             "ByVal args of size 0 should have been ignored by front-end.");
      assert(ByValIdx < CCInfo.getInRegsParamsCount());
      copyByValRegs(Chain, DL, OutChains, DAG, Flags, InVals, &*FuncArg,
                    FirstByValReg, LastByValReg, VA, CCInfo);
      CCInfo.nextInRegsParam();
      continue;
    }
...

ByVal属性が付加されている場合の処理を追加した。 まず、ByVal属性が付加されている引数を見つけると、先ほどHandleByValで解析した情報に基づいて命令の生成に入る。 まず、CCInfo.getInRegsParamInfo()により、当該引数により引数わたしのレジスタの何番から何番までが使用されるかを取得する。 そして、この情報に基づいてcopyByValRegs()を呼び出す。

void MYRISCVXTargetLowering::copyByValRegs(
    SDValue Chain, const SDLoc &DL, std::vector<SDValue> &OutChains,
    SelectionDAG &DAG, const ISD::ArgFlagsTy &Flags,
    SmallVectorImpl<SDValue> &InVals, const Argument *FuncArg,
    unsigned FirstReg, unsigned LastReg, const CCValAssign &VA,
    MipsCCState &State) const {
...
  unsigned NumRegs = LastReg - FirstReg;  // 引数渡しに使用できるレジスタの数
  unsigned RegAreaSize = NumRegs * GPRSizeInBytes;
...
  for (unsigned I = 0; I < NumRegs; ++I) {
    unsigned ArgReg = ByValArgRegs[FirstReg + I];
    unsigned VReg = addLiveIn(MF, ArgReg, RC);
    unsigned Offset = I * GPRSizeInBytes;
    // オフセットの計算
    SDValue StorePtr = DAG.getNode(ISD::ADD, DL, PtrTy, FIN,
                                   DAG.getConstant(Offset, DL, PtrTy));
    // 引数をスタックに戻している。
    SDValue Store = DAG.getStore(Chain, DL, DAG.getRegister(VReg, RegTy),
                                 StorePtr, MachinePointerInfo(FuncArg, Offset));
    OutChains.push_back(Store);
  }

copyByValRegsで行っている処理だが、これはレジスタ経由で受け取った引数をスタックに戻す処理を行っている。 スタックポインタをベースにして、ストア命令を生成していることが分かる。 関数の呼びされ側(Callee)では、レジスタ渡しで引数を受け取っても、受け取った値をいったんスタックに戻しているのである。

f:id:msyksphinz:20191012021030p:plain
LowerFormalArguments()において、ByVal属性の引数を見つけると、copyByValRegs()が呼び出される。

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

前回の続き。

Legalizeでは、ターゲット固有のノードへの変換を行う。LLVM IRでは様々な演算ノードを定義しているが、ターゲットアーキテクチャによってはサポートしていない演算もある。

このような演算に関しては、ターゲットが生成できるノードに変換するなどの指示を出す必要がある。

これらについては、後述するMYRSCVXTargetLoweringで指示を出すが、例えば、ローテート命令はRISC-Vではそのまま生成できない。したがって、以下のように記述することでローテート演算の生成を抑制する。

  • llvm-myriscvx80/lib/Target/MYRISCVX/MYRISCVXISelLowering.cpp
  setOperationAction(ISD::ROTL, XLenVT, Expand);
  setOperationAction(ISD::ROTR, XLenVT, Expand);

setOperationActionにより、当該ノードの動作を決定する。上記の例だと、ISD::ROTL演算の`XLenVT‘サイズの演算について、Expandのアクションを設定する。

  • llvm-myriscvx80/include/llvm/CodeGen/TargetLowering.h
  /// Indicate that the specified operation does not work with the specified
  /// type and indicate what to do about it. Note that VT may refer to either
  /// the type of a result or that of an operand of Op.
  void setOperationAction(unsigned Op, MVT VT,
                          LegalizeAction Action) {
    assert(Op < array_lengthof(OpActions[0]) && "Table isn't big enough!");
    OpActions[(unsigned)VT.SimpleTy][Op] = Action;
  }

上記の場合だとノードのアクションがExpandに設定されるのだが、Legalizeの実行時にSelectionDAGLegalize::LegalizeOpが呼ばれ判断が行われる。 Expandの場合は、ExpandNode()が呼び出され、さらにExpandROTにより、より単純なノードへの置き換えが行われる。

  • llvm-myriscvx80/lib/CodeGen/SelectionDAG/LegalizeDAG.cpp
/// Return a legal replacement for the given operation, with all legal operands.
void SelectionDAGLegalize::LegalizeOp(SDNode *Node) {
  LLVM_DEBUG(dbgs() << "\nLegalizing: "; Node->dump(&DAG));
...
    switch (Action) {
    case TargetLowering::Legal:
      LLVM_DEBUG(dbgs() << "Legal node: nothing to do\n");
...
    case TargetLowering::Expand:
      if (ExpandNode(Node))
        return;
      LLVM_FALLTHROUGH;
...
  • llvm-myriscvx80/lib/CodeGen/SelectionDAG/LegalizeDAG.cpp
bool SelectionDAGLegalize::ExpandNode(SDNode *Node) {
  LLVM_DEBUG(dbgs() << "Trying to expand node\n");
  SmallVector<SDValue, 8> Results;
...
  case ISD::ROTL:
  case ISD::ROTR:
    if (TLI.expandROT(Node, Tmp1, DAG))
      Results.push_back(Tmp1);
    break;
...

最終的に、シフト演算と論理演算命令に置き換わる。

  • llvm-myriscvx80/lib/CodeGen/SelectionDAG/TargetLowering.cpp
// TODO: Merge with expandFunnelShift.
bool TargetLowering::expandROT(SDNode *Node, SDValue &Result,
                               SelectionDAG &DAG) const {
  EVT VT = Node->getValueType(0);
  unsigned EltSizeInBits = VT.getScalarSizeInBits();
...
  // Otherwise,
  //   (rotl x, c) -> (or (shl x, (and c, w-1)), (srl x, (and w-c, w-1)))
  //   (rotr x, c) -> (or (srl x, (and c, w-1)), (shl x, (and w-c, w-1)))
  //
  assert(isPowerOf2_32(EltSizeInBits) && EltSizeInBits > 1 &&
         "Expecting the type bitwidth to be a power of 2");
  unsigned ShOpc = IsLeft ? ISD::SHL : ISD::SRL;
  unsigned HsOpc = IsLeft ? ISD::SRL : ISD::SHL;
  SDValue BitWidthMinusOneC = DAG.getConstant(EltSizeInBits - 1, DL, ShVT);
  SDValue NegOp1 = DAG.getNode(ISD::SUB, DL, ShVT, BitWidthC, Op1);
  SDValue And0 = DAG.getNode(ISD::AND, DL, ShVT, Op1, BitWidthMinusOneC);
  SDValue And1 = DAG.getNode(ISD::AND, DL, ShVT, NegOp1, BitWidthMinusOneC);
  Result = DAG.getNode(ISD::OR, DL, VT, DAG.getNode(ShOpc, DL, VT, Op0, And0),
                       DAG.getNode(HsOpc, DL, VT, Op0, And1));
  return true;
} 

命令のSelection

ここまで来るとほぼ一対一でSelectionDAGのノードを命令に変換することができる。 次は、SelectionDAGのノードを命令に相当するノードMI(Machine Instruction)に変換する。 これには、DAGToDAGISelによって処理される。 今回作成するMYRISCVXアーキテクチャではMYRISCVXDAGToDAGISelによって行われる。 MYRISCVXDAGToDAGISel::Select()によって行われる。

//@Select {
/// Select instructions not customized! Used for
/// expanded, promoted and normal instructions
void MYRISCVXDAGToDAGISel::Select(SDNode *Node) {
  //@Select }
...
  // Select the default instruction
  SelectCode(Node);
}

SelectCodeMYRISCVXGenDAGISel.incに定義されており、TableGenにより生成されたノードから命令ノードへの変換が行われる。

  • build-myriscvx80/lib/Target/MYRISCVX/MYRISCVXGenDAGISel.inc
#if defined(GET_DAGISEL_BODY) || DAGISEL_INLINE
void DAGISEL_CLASS_COLONCOLON SelectCode(SDNode *N)
{
  // Some target values are emitted as 2 bytes, TARGET_VAL handles
...

これにより、以下のようなDAGが生成される。MYRISCVXISD::RetRetRAに変換されている。

f:id:msyksphinz:20191011015229p:plain:w300
Instruction Selectionにより生成されたDAG

オリジナル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

オリジナルLLVMバックエンド実装をまとめる(17. 関数からも戻るときのCalling Convention)

次に、戻り値に関するCalling Conventionの実装から始める。

以下の記述では、関数の戻り値が渡される場合に、CCAssignToRegで示されるレジスタのどれかに引数が格納されるルールが追加されている。 そしてCalling ConventionであるRetCC_MYRISCVXを定義する。

commit:84bc7aa2b1b Add MYRISCVX Calling Convention LP32/STACK32/LP64/STACK64

  • llvm-myriscvx80/lib/Target/MYRISCVX/MYRISCVXCallingConv.td
//===----------------------------------------------------------------------===//
// MYRISCVX LP32/STACK32 Return Convention
//===----------------------------------------------------------------------===//

def RetCC_LP32 : CallingConv<[
  CCIfType<[i32], CCAssignToReg<[A0, A1]>>
]>;

def RetCC_STACK32 : CallingConv<[
  CCIfType<[i32], CCAssignToStack<4, 4>>
]>;


//===----------------------------------------------------------------------===//
// MYRISCVX LP64/STACK64 Return Convention
//===----------------------------------------------------------------------===//

def RetCC_LP64 : CallingConv<[
  CCIfType<[i64], CCAssignToReg<[A0, A1]>>
]>;

def RetCC_STACK64 : CallingConv<[
  CCIfType<[i64], CCAssignToStack<8, 8>>
]>;

def RetCC_MYRISCVX : CallingConv<[
  CCIfSubtarget<"isABI_STACK64()", CCDelegateTo<RetCC_STACK64>>,
  CCIfSubtarget<"isABI_LP64   ()", CCDelegateTo<RetCC_LP64>>,
  CCIfSubtarget<"isABI_STACK32()", CCDelegateTo<RetCC_STACK32>>,
  CCDelegateTo<RetCC_LP32>
]>;

このRetCC_MYRISCVXはInstruction Selection時のAnalyzeReturnで使用される。AnalyzeReturnLowerReturnから呼び出される。

それぞれの中身は、見てみると簡単です。LP32/LP64のCalling Conventionの場合は戻り値をレジスタA0, A1に割り当てる。 これをCCAssignToRegという命令によって表現している。 また、STACK32/STACK64のCalling Conventionの場合は、CCAssignToStackという命令を使用してスタックに割り当てる。 文法はCCAssignToStack<Size, Align>となっており、最初の数字はデータサイズ、次の数字はアドレスアラインを示している。

f:id:msyksphinz:20191007022122p:plain
関数戻り時の戻り値を特定のレジスタ経由で行う仕組み。

そして、LP64/STACK64, LP32/STACK32をそれぞれオプションで切り替えるための、大元となるRetCC_MYRISCVXを定義している。

ちなみに、生成されたMYRISCVXGenCallingConv.incの一部を切り取る。 このように、CCIfSubTargetによりサブターゲットの条件分岐が行われ、さらにCC_LP{32,64}, CC_STACK{32, 64}の中で引数のチェックが行われている。

  • build-myriscvx80/lib/Target/MYRISCVX/MYRISCVXGenCallingConv.inc
// おおもとのCalling Convention。内部でCC_STACK32, CC_LP32, CC_STACK64, CC_LP64を条件分岐で使い分ける。
static bool RetCC_MYRISCVX(unsigned ValNo, MVT ValVT,
                           MVT LocVT, CCValAssign::LocInfo LocInfo,
                           ISD::ArgFlagsTy ArgFlags, CCState &State) {

  if (static_cast<const MYRISCVXSubtarget&>(State.getMachineFunction().getSubtarget()).isABI_STACK64()) {
    if (!RetCC_STACK64(ValNo, ValVT, LocVT, LocInfo, ArgFlags, State))
      return false;
  }

  if (static_cast<const MYRISCVXSubtarget&>(State.getMachineFunction().getSubtarget()).isABI_LP64   ()) {
    if (!RetCC_LP64(ValNo, ValVT, LocVT, LocInfo, ArgFlags, State))
      return false;
  }

  if (static_cast<const MYRISCVXSubtarget&>(State.getMachineFunction().getSubtarget()).isABI_STACK32()) {
    if (!RetCC_STACK32(ValNo, ValVT, LocVT, LocInfo, ArgFlags, State))
      return false;
  }

  if (!RetCC_LP32(ValNo, ValVT, LocVT, LocInfo, ArgFlags, State))
    return false;

  return true;  // CC didn't match.
}


// RetCC_STACK32の実装。
// スタックのアロケーションを行っている。
static bool RetCC_STACK32(unsigned ValNo, MVT ValVT,
                          MVT LocVT, CCValAssign::LocInfo LocInfo,
                          ISD::ArgFlagsTy ArgFlags, CCState &State) {

  if (LocVT == MVT::i32) {
    unsigned Offset1 = State.AllocateStack(4, 4);
    State.addLoc(CCValAssign::getMem(ValNo, ValVT, Offset1, LocVT, LocInfo));
    return false;
  }

  return true;  // CC didn't match.
}


// RetCC_LP32の実装
static bool RetCC_LP32(unsigned ValNo, MVT ValVT,
                       MVT LocVT, CCValAssign::LocInfo LocInfo,
                       ISD::ArgFlagsTy ArgFlags, CCState &State) {

  if (LocVT == MVT::i32) {
    static const MCPhysReg RegList1[] = {
      MYRISCVX::A0, MYRISCVX::A1
    };
    if (unsigned Reg = State.AllocateReg(RegList1)) {
      State.addLoc(CCValAssign::getReg(ValNo, ValVT, Reg, LocVT, LocInfo));
      return false;
    }
  }

  return true;  // CC didn't match.
}
  • llvm-myriscvx80/lib/Target/MYRISCVX/MYRISCVXISelLowering.cpp
template<typename Ty>
void MYRISCVXTargetLowering::MYRISCVXCC::
analyzeReturn(const SmallVectorImpl<Ty> &RetVals, bool IsSoftFloat,
              const SDNode *CallNode, const Type *RetTy) const {
  CCAssignFn *Fn;

  Fn = RetCC_MYRISCVX;

...
    if (Fn(I, VT, RegVT, CCValAssign::Full, Flags, this->CCInfo)) {
      LLVM_DEBUG(dbgs() << "Call result #" << I << " has unhandled type "
                 << EVT(VT).getEVTString() << '\n');
      llvm_unreachable(nullptr);
    }
...

オリジナルLLVMバックエンド実装をまとめる(16. 関数コールをサポートする)

今までのバックエンドの実装では、関数の取り扱いについていろいろとさぼっている部分があった。今回は、関数の定義と関数コールをきちんとサポートしようと思う。このためには、

  • スタックフレームの定義
  • 引数の処理

などを実装していく。

現状では、引数のある関数を定義してllcに入力すると以下のようなエラーが発生する。

  • func_args.cpp
int sum_global;
int sum_i(int x1, int x2, int x3, int x4, int x5, int x6)
{
  sum_global = x1 + x2 + x3 + x4 + x5 + x6;

  return 0;
}
./bin/clang -target riscv32-unknown-linux-gnu -c func_args.cpp -emit-llvm
./bin/llc -march=myriscvx32 -filetype=asm func_args.bc -o -
    llc: /home/msyksphinz/work/llvm/llvm-myriscvx80/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp:9135: void llvm::SelectionDAGISel::LowerArguments(const llvm::Function&): Assertion `InVals.size() == Ins.size() && "LowerFormalArguments didn't emit the correct number of values!"' failed.

最終的に関数をコンパイルして命令を出力するためには、これらの引数を処理し、適切なレジスタ・スタックに収め、命令をデータの流れをコントロールする必要がある。これらの処理について説明する。

f:id:msyksphinz:20191007021543p:plain

MYRISCVXのCalling Conventionについて

命令セットアーキテクチャには、命令の定義ともに、関数呼び出しのルールを規定するCalling Conventionが定義されている。 MYRISCVXにもCalling Conventionが存在し、基本的にRISC-VのCalling Conventionに基づいている。 このルールに基づき、引数を渡す際にも特定のレジスタを使用する必要がある。

呼び出し規約では、関数呼び出しの規約、つまり関数コールの際の引数をどのような形で渡すのか、戻り値はどのような形式で返すのかと言う事を規定している。 呼び出し規約はISAと直接関係ある訳ではなく、ソフトウェアによって独自に決めることができる。 しかし、呼び出し規約が異なるバイナリどうしは互いに呼び出すことができないため、ISA毎に標準的な呼び出し規約が決められているのが一般的だ。 RISC-Vでは複数の呼び出し規約が決められている。その中で、整数レジスタの動作について定義しているのはILP32だ。これは、

  • 整数値の引数渡しはA0-A7レジスタを経由して渡す。それよりも多い引数はスタックを経由して渡す。
  • 戻り値はA0-A1レジスタを経由して呼び出し元に戻す。

というルールだ。これをMYRISCVXの呼び出し規約としてそのまま採用する。

もう一つ、LLVMの動作を理解するために、独自の呼び出し規約を定義する。

  • 全ての引数はスタックを経由して渡す。
  • 戻り値はA0-A1レジスタを経由して呼び出し元に戻す。

というものだ。この呼び出し規約をSTACK32と呼ぶことにする。MYRISCVXでは、この2つの呼び出し規約を実装することにする。

MYRISCVXの場合はRISC-Vと同様に整数の引数は汎用レジスタA0-A7に格納して渡すモードもあるのだが、解説のためにもう一つ、すべての引数をスタック経由で渡すモードも用意している。

それぞれのこの関数呼び出しの規約をLP32, STACK32(32-bit版), LP64, STACK64(64-bit版)と呼びる。

Calling Convention名 説明
LP32 / LP64 最初の8個の引数は、A0-A7に格納し、それ以降はスタック経由で引数を渡す。
STACK32 / STACK64 すべての引数をスタック経由で渡す。

このCalling Conventionを実現するのがMYRISCVXCallingConv.tdに記述していく。 これらを制御するために、CCIfTypeおよびCCAssignToRegを使って制御する。

f:id:msyksphinz:20191007021625p:plain
CC_LP{32,64} 関数呼び出し規約
f:id:msyksphinz:20191007021647p:plain
CC_STACK{32,64} 関数呼び出し規約

関数に入るときのCalling Convention

まず、呼び出された関数が実行されるときのCalling Conventionから考えていく(関数を呼ぶ側、つまりCaller側の処理は以降の章で考えていく)。

関数が呼び出されると、まずはCallee Savedレジスタを退避する。つまり、関数側が管理すべきレジスタをスタックに退避し、関数から戻るときにレジスタを汚してしまうことを防止する。

そして、関数内で使用する変数の分だけスタックを移動し、関数本体に入っていく。

MYRISCVXでは2種類のCalling Conventionを用意すると説明した。 LP{32,64}とSTACK{32,64}だ。LPはA0-A7までのレジスタに引数の最初の8つまでを格納し、それ以降はスタックに格納する。一方で、STACKはすべての引数をスタックに格納する。

以下の記述では、関数の引数を渡す際のルールを決めている。Calling ConventionであるCC_MYRISCVXを定義している。

  • llvm-myriscvx80/lib/Target/MYRISCVX/MYRISCVXCallingConv.td
//===----------------------------------------------------------------------===//
// MYRISCVX LP32/STACK32 Calling Convention
//===----------------------------------------------------------------------===//

def CC_LP32 : CallingConv<[
  // Promote i8/i16 arguments to i32.
  CCIfType<[i1, i8, i16], CCPromoteToType<i32>>,

  // Integer arguments are passed in integer registers.
  CCIfType<[i32], CCAssignToReg<[A0, A1, A2, A3, A4, A5, A6, A7]>>,

  // Integer values get stored in stack slots that are 4 bytes in
  // size and 4-byte aligned.
  CCIfType<[i32], CCAssignToStack<4, 4>>
]>;

def CC_STACK32 : CallingConv<[
  // Promote i8/i16 arguments to i32.
  CCIfType<[i1, i8, i16], CCPromoteToType<i32>>,

  // Integer values get stored in stack slots that are 4 bytes in
  // size and 4-byte aligned.
  CCIfType<[i32], CCAssignToStack<4, 4>>
]>;

//===----------------------------------------------------------------------===//
// MYRISCVX LP64/STACK64 Calling Convention
//===----------------------------------------------------------------------===//

def CC_LP64 : CallingConv<[
  // Promote i8/i16/i32 arguments to i64.
  CCIfType<[i1, i8, i16, i32], CCPromoteToType<i64>>,

  // Integer arguments are passed in integer registers.
  CCIfType<[i64], CCAssignToReg<[A0, A1, A2, A3, A4, A5, A6, A7]>>,

  // Integer values get stored in stack slots that are 4 bytes in
  // size and 4-byte aligned.
  CCIfType<[i64], CCAssignToStack<8, 8>>
]>;

def CC_STACK64 : CallingConv<[
  // Promote i8/i16/i32 arguments to i64.
  CCIfType<[i1, i8, i16, i32], CCPromoteToType<i64>>,

  // Integer values get stored in stack slots that are 8 bytes in
  // size and 8-byte aligned.
  CCIfType<[i64], CCAssignToStack<8, 8>>
]>;

def CC_MYRISCVX : CallingConv<[
  CCIfSubtarget<"isABI_STACK64()", CCDelegateTo<CC_STACK64>>,
  CCIfSubtarget<"isABI_LP64   ()", CCDelegateTo<CC_LP64>>,
  CCIfSubtarget<"isABI_STACK32()", CCDelegateTo<CC_STACK32>>,
  CCDelegateTo<CC_LP32>
]>;

まず、4種類のCalling Convention、

  • CC_LP32
  • CCL_STACK32
  • CC_LP64
  • CC_STACK64

を定義していることが分かりる。CCIfTypeCCPromoteToTypeを使って、XLENよりも小さな値はすべてXLENのサイズまでビット幅を拡張するように設定している。 CC_LP{32,64}は、CCAssignToRegによってA0-A7までのレジスタを引数わたしに使用できる。 それ以降の引数はCCAssignToStackによりスタックに割り当てる。

CC_STACK{32,64}では、CCAssignToRegを使用せず、すべてCCAssignToStackによって引数をスタックに割り当てている。

さて、この4種類のCalling Conventionからどれを選ぶのか、ですがこれをひとまとめにしたCC_MYRISCVXというCalling Conventionを定義している。 CCIfSubTargetという命令を独自に追加し、サブターゲット内の条件によってCalling Conventionを切り替えるようにしている。

/// CCIfSubtarget - Match if the current subtarget has a feature F.
class CCIfSubtarget<string F, CCAction A, string Invert = "">
    : CCIf<!strconcat(Invert,
                      "static_cast<const MYRISCVXSubtarget&>"
            "(State.getMachineFunction().getSubtarget()).",
                      F),
           A>;

Calling Conventionの4種類の中から1種類を選択する。isABI_STACK64(), isABI_LP64(), isABI_STACK32()は、それぞれMYRISCVXSubTarget.hで定義されている。

  • llvm-myriscvx80/lib/Target/MYRISCVX/MYRISCVXSubtarget.h
  class MYRISCVXSubtarget : public MYRISCVXGenSubtargetInfo {
    virtual void anchor();
...
    bool isABI_LP32()    const { return getXLenVT() == MVT::i32 && getABI().IsLP();    }
    bool isABI_STACK32() const { return getXLenVT() == MVT::i32 && getABI().IsSTACK(); }
    bool isABI_LP64()    const { return getXLenVT() == MVT::i64 && getABI().IsLP();    }
    bool isABI_STACK64() const { return getXLenVT() == MVT::i64 && getABI().IsSTACK(); }
...

それぞれ、現在のABIと現在のレジスタサイズgetXLenVT()によりどのモードを使うのかを判定している。これにより、現在のサブターゲットの設定によりどのCalling Conventionを使うのかを1つに決定している。

オリジナルLLVMバックエンド実装をまとめる(14. 分岐の際に発生する不要なジャンプを削除するPassの追加)

前回の制御構文を追加した際に、不要なジャンプ命令が発生しているのが気になった。例えば、LLVM IRをダンプし時に以下のようなIRが出力されたはずだ。 この時、br label %if.endはすぐ後ろのif.endにジャンプするため、このジャンプ文は不要なはずだ。ここでは、このような不要なジャンプ命令を削除して、コードの最適化を図ってみる。

if.then:                                          ; preds = %entry
  %1 = load i32, i32* %a, align 4
  %inc = add i32 %1, 1
  store i32 %inc, i32* %a, align 4
  br label %if.end

if.end:                                           ; preds = %if.then, %entry
  %2 = load i32, i32* %a, align 4
  ret i32 %2
}
f:id:msyksphinz:20191004000339p:plain
DelJmp Passにより削除する命令のパタン

最適化のPassを追加する

ここで最適化のPassを追加するのだが、マシンコードが生成される前に最適化のPassを追加する。この場合、TargetPassConfig::addPreEmitPass()を通じてPassを追加する。

  • llvm-myriscvx80/lib/Target/MYRISCVX/MYRISCVXTargetMachine.cpp
//@MYRISCVXPassConfig {
/// MYRISCVX Code Generator Pass Configuration Options.
class MYRISCVXPassConfig : public TargetPassConfig {
 public:
...
   void addPreEmitPass() override;
...
void MYRISCVXPassConfig::addPreEmitPass() {
  MYRISCVXTargetMachine &TM = getMYRISCVXTargetMachine();
  addPass (createMYRISCVXDelJmpPass(TM));
  return;
}

createMYRISCVXDelJmpPassというPassを追加した。このPassはMYRISCVXDelUselessJMP.cppで追加する。

  • llvm-myriscvx80/lib/Target/MYRISCVX/MYRISCVXDelUselessJMP.cpp
#define DEBUG_TYPE "del-jmp"

STATISTIC(NumDelJmp, "Number of useless jmp deleted");

static cl::opt<bool> EnableDelJmp(
    "enable-MYRISCVX-del-useless-jmp",
    cl::init(true),
    cl::desc("Delete useless jmp instructions: jmp 0."),
    cl::Hidden);

Passの定義を行う。このPassはDelJmpというもので、デフォルトで有効だ。-enable-MYRISCVX-del-useless-jmpオプションで有効無効を制御することができる。 例えば、-enable-MYRISCVX-del-useless-jmp=falseとすることでこのPassを無効化することができる。

DelJmpクラスを定義する。このクラスは、MachineFunctionPassクラスから派生している。MachineFunctionPassクラスに記述したPassは、runOnMachineFunction()関数を呼び出すことにより実行される。

virtual bool runOnMachineFunction(MachineFunction &MF) = 0;

では、DelJmpクラスのrunOnMachineFunction()関数を実装してみる。

  bool runOnMachineFunction(MachineFunction &F) {
    bool Changed = false;
    if (EnableDelJmp) {
      MachineFunction::iterator FJ = F.begin();
      if (FJ != F.end())
        FJ++;
      if (FJ == F.end())
        return Changed;
      for (MachineFunction::iterator FI = F.begin(), FE = F.end();
           FJ != FE; ++FI, ++FJ)
        // In STL style, F.end() is the dummy BasicBlock() like '\0' in
        //  C string.
        // FJ is the next BasicBlock of FI; When FI range from F.begin() to
        //  the PreviousBasicBlock of F.end() call runOnMachineBasicBlock().
        Changed |= runOnMachineBasicBlock(*FI, *FJ);
    }
    return Changed;
  }

このコードでは、マシンコードからBasicBlockをひとつづつ取り出してPassを適用するという形をとっている。 FIイテレータがターゲットとなるBasic Blockを示しており、一つずらしたFJイテレータFIの次のブロックを示している。つまり、

  • FIイテレータの一番最後のコードがジャンプ命令であり、
  • ジャンプ先がFJの先頭であれば、FIの最後のジャンプ命令を削除しても良い

ということになり、この処理をrunOnMachineBasicBlock()に記述している。最終的にコードの変更を行った場合は、Changed変数をTrueに設定して戻る。

bool DelJmp::
runOnMachineBasicBlock(MachineBasicBlock &MBB, MachineBasicBlock &MBBN) {
  bool Changed = false;

  MachineBasicBlock::iterator I = MBB.end();
  if (I != MBB.begin())
    I--;    // set I to the last instruction
  else
    return Changed;

  if (I->getOpcode() == MYRISCVX::PseudoBR &&
      I->getOperand(0).getType() == MachineOperand::MO_MachineBasicBlock &&
      I->getOperand(0).getMBB() == &MBBN) {
    // I is the instruction of "jmp #offset=0", as follows,
    //     jal     zero, $BB0_3
    // $BB0_3:
    //     ld  $4, 28($sp)
    ++NumDelJmp;
    MBB.erase(I);   // delete the "JMP 0" instruction
    Changed = true;    // Notify LLVM kernel Changed
  }

  return Changed;
}

runOnMachineBasicBasicBlockでは、BasicBlockMBBと次のBasicBlockMBBNを使って最適化処理を行っている。 MBBの最後の命令が対象となる命令で、イテレータIで示されている。IRISC-VのPseudoBR、つまりJAL ZERO命令であり、さらに第1オペランドが示している先がMBBN(次のBasic Blockの先頭)であれば、削除可能だ。MBB.erase(I)により命令の削除を行い、ChangeをTrueに設定、そして最適化を行った回数を示すNumDelJmpをインクリメントする。

このNumDelJmp変数は、llcの-statsオプションにより参照することができる。

では、ここまでの変更を施したコードでLLVMをビルドしてみる。

# DelJmpPassを有効にした場合
# -enable-MYRISCVX-del-useless-jmp=true と同等
./bin/llc -debug -march=myriscvx32 -filetype=asm if_ctrl.rv32.bc -stats -o -
# DelJmpPassを無効にした場合
./bin/llc -debug -march=myriscvx32 -enable-MYRISCVX-del-useless-jmp=false -filetype=asm if_ctrl.rv32.bc -o -

それぞれ生成されたコードは以下のようになった。

  • DelJmpPassを無効にした場合
_Z11test_ifctrlv:                       # @_Z11test_ifctrlv

# %bb.0:                                # %entry
        addi    x2, x2, -4
        addi    x10, zero, 0
        sw      x10, 0(x2)
        lw      x10, 0(x2)
        bne     x10, zero, $BB0_2
        j       $BB0_1
$BB0_1:                                 # %if.then
        lw      x10, 0(x2)
        addi    x10, x10, 1
        sw      x10, 0(x2)
        j       $BB0_2
$BB0_2:                                 # %if.end
        addi    x2, x2, 4
        ret
  • DelJmpPassを有効にした場合
_Z11test_ifctrlv:                       # @_Z11test_ifctrlv

# %bb.0:                                # %entry
        addi    x2, x2, -4
        addi    x10, zero, 0
        sw      x10, 0(x2)
        lw      x10, 0(x2)
        bne     x10, zero, $BB0_2
# %bb.1:                                # %if.then
        lw      x10, 0(x2)
        addi    x10, x10, 1
        sw      x10, 0(x2)
$BB0_2:                                 # %if.end
        addi    x2, x2, 4
        ret

不要なJ命令が削除されているのが分かる。不要なJ命令がどれだけ削除されたのか-statsオプションを付けて確認してみようと思う。

./bin/llc -march=myriscvx32 -stats -filetype=asm if_ctrl.rv32.bc -o -
===-------------------------------------------------------------------------===
                          ... Statistics Collected ...
===-------------------------------------------------------------------------===

10 asm-printer    - Number of machine instrs printed
35 bitcode-reader - Number of Metadata records loaded
 2 bitcode-reader - Number of MDStrings loaded
 1 dagcombine     - Number of dag nodes combined
 2 del-jmp        - Number of useless jmp deleted
 3 isel           - Number of blocks selected using DAG
30 isel           - Number of times dag isel has to try another path
 1 isel           - Number of entry blocks encountered
 4 prologepilog   - Number of bytes used for stack in all functions
 1 prologepilog   - Number of functions seen in PEI
 4 regalloc       - Number of registers assigned
 1 stackmaps      - Number of functions skipped
 1 stackmaps      - Number of functions visited

del-jmp Passにより、2つの命令が削除されていることが分かった。