FPGA開発日記

FPGAというより、コンピュータアーキテクチャかもね! カテゴリ別記事インデックス https://msyksphinz.github.io/github_pages

オリジナルLLVMバックエンド実装をまとめる(24. 末尾再帰関数呼び出しの実装2.)

f:id:msyksphinz:20191016013631p:plain

前回の続き。末尾再帰の生成について。

LowerCallに戻る。IsTailCallがTrueとなり、末尾関数呼び出し最適化が有効として読み進める。

...
  if (!IsTailCall)
    Chain = DAG.getCALLSEQ_START(Chain, NextStackOffset, 0, DL);
...

末尾関数呼び出し最適化が有効の場合は、新たにスタックフレームを作らないのでCALLSEQ_STARTは生成しない。

  /* 引数渡しのDAG生成部 */
  for (unsigned i = 0, e = ArgLocs.size(); i != e; ++i) {
...
    MemOpChains.push_back(passArgOnStack(StackPtr, VA.getLocMemOffset(),
                                         Chain, Arg, DL, IsTailCall, DAG));
  }

スタック渡しの引数の場合は、少し細工をする。

SDValue
MYRISCVXTargetLowering::passArgOnStack(SDValue StackPtr, unsigned Offset,
                                       SDValue Chain, SDValue Arg, const SDLoc &DL,
                                       bool IsTailCall, SelectionDAG &DAG) const {
  if (!IsTailCall) {
...
  }

  MachineFrameInfo &MFI = DAG.getMachineFunction().getFrameInfo();
  int FI = MFI.CreateFixedObject(Arg.getValueSizeInBits() / 8, Offset, false);
  SDValue FIN = DAG.getFrameIndex(FI, getPointerTy(DAG.getDataLayout()));
  return DAG.getStore(Chain, DL, Arg, FIN, MachinePointerInfo(),
                      /* Alignment = */ 0, MachineMemOperand::MOVolatile);
}

LowerCallに戻る。TailCallノードを挿入する。

  if (IsTailCall)
    return DAG.getNode(MYRISCVXISD::TailCall, DL, MVT::Other, Ops);

上記で使用したMYRISCVXISD::TailCallノードも定義しておく必要がある。これはMYRISCVXInstrInfo.tdで新たなノードとして定義する。 MYRISCVXCallSeqStartMYRISCVXCallSeqEndのように、TailCallノードもノードとして定義しておく(後で除去するため)。

このMYRISCVXISD::TailCallMYRISCVXInstrInfo.tdの中でパタンとして変換される。つまり、

  1. LowerCall内でMYRISCVXISD::TailCallノードを生成する。
  2. MYRISCVXISD::TailCallノードはMYRISCVXInstrInfo.tdで定義した生成パタンに基づいて変換される。
  3. 変換されたパタンに基づいて命令が生成される。

という手順になる。では具体的にMYRISCVXInstrInfo.tdでどのような変換ノードを定義すれば良いのか見てみる。

  • llvm-myriscvx80/lib/Target/MYRISCVX/MYRISCVXInstrInfo.td
let isCall = 1, isTerminator = 1, isReturn = 1, isBarrier = 1, hasDelaySlot = 0,
    hasExtraSrcRegAllocReq = 1 in {
  class TailCall<Instruction JumpInst> :
    MYRISCVXPseudo<(outs), (ins brtarget20:$target), "", []>,
    PseudoInstExpansion<(JumpInst ZERO, brtarget20:$target)>;

  class TailCallReg<Instruction JRInst, RegisterClass RC> :
    MYRISCVXPseudo<(outs), (ins RC:$rs), "", [(MYRISCVXTailCall RC:$rs)]>,
    PseudoInstExpansion<(JRInst ZERO, RC:$rs, 0)>;
}

まず、テンプレートとなるTailCallTailCallRegクラスを定義した。TailCallは最終的にJAL命令(即値ジャンプ命令)、TailCallReg命令は最終的に命令(レジスタ間接ジャンプ命令)に変換されることを狙っている。見てわかる通り、それぞれPseudoInstExpansionにおいてジャンプ元を格納するリンクレジスタにZEROを指定している。これによりTailCallは単なるリンクをしない単なるジャンプ命令となり、リンクレジスタの内容は保持されるため、ジャンプ先でそのまま呼び出し元に戻ることができる、という仕組みだ。

さて、TailCallTailCallRegを定義した。最終的にはJAL命令もしくはJALRに置き換えられる。

def TAILCALL : TailCall<JAL>;
def TAILCALL_R : TailCallReg<JALR, GPR>;

そして、TAILCALL側にはDAG生成パタンを登録していないので、パタンを登録しておく。 TAILCALL_R側は、TailCallRegの定義ですでに生成パタンMYRISCVXTailCall RC:$rsを登録済みである。

def : Pat<(MYRISCVXTailCall (iPTR tglobaladdr:$dst)), (TAILCALL tglobaladdr:$dst)>;
def : Pat<(MYRISCVXTailCall (iPTR texternalsym:$dst)), (TAILCALL texternalsym:$dst)>;

最後に、アセンブリの生成だ。TAILCALLTAILCALL_Rは疑似命令なのでそのままではアセンブリ命令を出力することができない。 これを置き換える処理は、tdファイルからすでに生成されている。MYRISCVXGenMCPseudoLowering.incを見てみる。

  • build-myriscvx80/lib/Target/MYRISCVX/MYRISCVXGenMCPseudoLowering.inc
bool MYRISCVXAsmPrinter::
emitPseudoExpansionLowering(MCStreamer &OutStreamer,
                            const MachineInstr *MI) {
  switch (MI->getOpcode()) {
    default: return false;
    case MYRISCVX::TAILCALL: {
      MCInst TmpInst;
      MCOperand MCOp;
      TmpInst.setOpcode(MYRISCVX::JAL);
      // Operand: target
      lowerOperand(MI->getOperand(0), MCOp);
      TmpInst.addOperand(MCOp);
      EmitToStreamer(OutStreamer, TmpInst);
      break;
    }
    case MYRISCVX::TAILCALL_R: {
      MCInst TmpInst;
      MCOperand MCOp;
      TmpInst.setOpcode(MYRISCVX::JALR);
      // Operand: rs1
      lowerOperand(MI->getOperand(0), MCOp);
      TmpInst.addOperand(MCOp);
      EmitToStreamer(OutStreamer, TmpInst);
      break;
    }
  }
  return true;
}

TAILCALLではJAL命令に置き換え、TAILCALL_RノードではJALR命令に置き換えるシーケンスが生成されていることが分かる。 なぜこれが生成されたかというと、これらのノードにはPseudoInstExpansionが追加されており、自動的に展開することができるようになっていたからだ。

  • llvm-myriscvx80/lib/Target/MYRISCVX/MYRISCVXAsmPrinter.cpp
//- EmitInstruction() must exists or will have run time error.
void MYRISCVXAsmPrinter::EmitInstruction(const MachineInstr *MI) {
...
  do {
    // Do any auto-generated pseudo lowerings.
    if (emitPseudoExpansionLowering(*OutStreamer, &*I))
      continue;
... 

ここまでで、末尾関数呼び出し最適化を適用した場合とそうでない場合についてアセンブリ命令を生成してみる。

# 末尾関数呼び出し最適化を適用した場合
./bin/llc -stats -debug -target-abi=lp64 -march=myriscvx32 -mcpu=simple32 -enable-MYRISCVX-tail-calls=true -relocation-model=static -filetype=asm result/tailcall_-O1_-march=myriscvx32_-mcpu=simple32_static_lp64_-enable-MYRISCVX-tail-calls=true/tailcall.bc -o -
# 末尾関数呼び出し最適化を適用しない場合
./bin/llc -stats -debug -target-abi=lp64 -march=myriscvx32 -mcpu=simple32 -enable-MYRISCVX-tail-calls=false -relocation-model=static -filetype=asm result/tailcall_-O1_-march=myriscvx32_-mcpu=simple32_static_lp64_-enable-MYRISCVX-tail-calls=false/tailcall.bc -o -

- 末尾関数呼び出し最適化を適用した場合の生成されたアセンブリ命令

​```asm
// 関数呼び出され側 (Callee)
_Z14tail_call_funcii:
...
# %bb.0:                                # %entry
    add x10, x11, x10
    ret x1

// 関数呼び出し側 (Caller)
_Z14tail_call_mainiiii:
...
# %bb.0:                                # %entry
    sub x10, x10, x11
    mul x11, x13, x12
    jal _Z14tail_call_funcii
...
  • 末尾関数呼び出し最適化を適用しない場合の生成されたアセンブリ命令
// 関数呼び出され側 (Callee)
_Z14tail_call_funcii:
...
# %bb.0:                                # %entry
    add x10, x11, x10
    ret x1

_Z14tail_call_mainiiii:
...
# %bb.0:                                # %entry
    addi    x2, x2, -8
    .cfi_def_cfa_offset 8
    sw  x2, 4(x2)               # 4-byte Folded Spill
    .cfi_offset 2, -4
    sub x10, x10, x11
    mul x11, x13, x12
    jal _Z14tail_call_funcii
    lw  x2, 4(x2)               # 4-byte Folded Reload
    addi    x2, x2, 8
    ret x1

末尾関数呼び出し最適化を適用しない場合場合は、_Z14tail_call_funcii呼び出し前にスタックの調整が行われていることが確認できる。一方で、末尾関数呼び出し最適化を適用した場合はスタックの調整コードが省略されている。これにより、関数呼び出しの場合のスタックフレームの消費を抑え、動作を高速化することができる。