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

関数呼び出しには様々な最適化の形があるが、その中の一つである末尾関数呼び出しでの最適化を実行してみる。末尾関数呼び出しとは、ある関数f1()が関数f2()の最後の処理として呼び出されるケースを言う。

int f1(a, b) { a + b; }
int f2(c, d, e, f) {
    /* 様々な処理*/
    return f1(10, 20);
}

この場合、関数f1()を呼び出すためには引数渡しの処理、スタックの処理、そして呼び出しから戻ってきた場合には戻り値の処理やスタックの後片付けを行う必要がある。

f:id:msyksphinz:20191016013535p:plain — 通常のスタックフレームの作成手順。関数が呼び出されると新たなスタックフレームが作成される。

しかし、場合によってはこれが不要なことがある。つまり、どっちにしろf1から戻った後はf2からも戻ってしまうのだから、せっかくなのでf2のスタック領域などもf1で使わせてもらって、関数呼び出し時のスタックの掘り下げを省略してしまう。つまり、末尾呼び出しではスタックフレームを追加することなくf1を呼び出すことができる。

f:id:msyksphinz:20191016013631p:plain — Tail Callのスタックフレームの作成手順。スタックフレームは新たに作成されず、引数の調整だけを行って関数に飛ぶ。

しかし、この末尾呼び出しはすべての条件下で実現可能なわけではない。上記で説明した通り、f2のスタックフレームを使用してf1が実行される。つまり、f1が使う予定であるスタックフレームのサイズがf2のスタックフレームのサイズを超えていてはならない。また、f1のスタックフレームのサイズが最初から算出できない場合にも末尾関数呼び出し最適化は適用できない。 f1のスタックフレーム以外の場所まで破壊してしまう可能性があるからだ。

では、実際にLLVMで末尾関数呼び出しの最適化を実行してみる。clangでは-O1オプションを付加することで末尾関数呼び出し最適化を施したIRを生成することができる。以下のプログラムをclangでIRを生成してみる。

int tail_call_func(int a, int b) {
    return a + b;
}
int tail_call_main (int a, int b, int c, int d) {
    int e = a + b;
    int f = c + d;
    return tail_call_func(e, f);  /* 末尾関数呼び出し */
}

./bin/clang -O1 --target=riscv32-unknown-elf tailcall.cpp -c -emit-llvm -o tailcall.o1.bc
./bin/clang -O0 --target=riscv32-unknown-elf tailcall.cpp -c -emit-llvm -o tailcall.o0.bc

生成されたバイナリをダンプしてみると、tailcall.o1の方ではf1の呼び出しの部分がtail callとなっていることが分かる。

./bin/llvm-dis tailcall.o1.bc -o -

  %sub = sub nsw i32 %a, %b
  %mul = mul nsw i32 %d, %c
  /* Tail Call が使用されている */
  %call = tail call i32 @_Z14tail_call_funcii(i32 signext %sub, i32 signext %mul)
  ret i32 %call

./bin/llvm-dis tailcall.o0.bc -o -

  /* -O0なので最適化が施されていない */
  store i32 %sub, i32* %e, align 4
...
  %mul = mul nsw i32 %2, %3
...
  /* 普通のCallが使用されている */
  %call = call i32 @_Z14tail_call_funcii(i32 signext %4, i32 signext %5)
  ret i32 %call

では、このIRを処理して末尾関数呼び出し最適化を適用してみる。実装しなければならないのは、

末尾関数呼び出し最適化が適用可能かチェックする
スタックフレームの生成を実行しないように制御
引数渡しの処理を行う
関数ジャンプ
戻り値処理

と、とりあえずは関数呼び出しのシーケンスの部分に手を加えれば良さそうだ。これらはすべてIRからDAGへの変換時に適用できるので、MYRISCVXISelLowering.cppに記述されているMYRISCVXTargetloweringクラスに手を加える。関数呼び出しの部分なので、MYRISCVXTargetLowering:::LowerCallを改造すれば良さそうだ。

llvm-myriscvx80/lib/Target/MYRISCVX/MYRISCVXISelLowering.cpp

SDValue
MYRISCVXTargetLowering::LowerCall(TargetLowering::CallLoweringInfo &CLI,
                                  SmallVectorImpl<SDValue> &InVals) const {
...
  bool &IsTailCall                      = CLI.IsTailCall;
...
  // Get a count of how many bytes are to be pushed on the stack.
  unsigned NextStackOffset = CCInfo.getNextStackOffset();

  // Check if it's really possible to do a tail call.
  if (IsTailCall)
    IsTailCall = isEligibleForTailCallOptimization(CCInfo, NextStackOffset,
                                                   *MF.getInfo<MYRISCVXFunctionInfo>());
...

IsTailCall変数は関数呼び出しが末尾関数呼び出しになっている場合にまずはTrueとなる。次に、本当に末尾関数呼び出し最適化が適用可能かチェックする。これを行っているのがisEligibleForTailCallOptimizationである。

llvm-myriscvx80/lib/Target/MYRISCVX/MYRISCVXSEISelLowering.cpp

/// isEligibleForTailCallOptimization - Check whether the call is eligible
/// for tail call optimization.
/// Note: This is modelled after ARM's IsEligibleForTailCallOptimization.
bool MYRISCVXTargetLowering::
isEligibleForTailCallOptimization(
    CCState &CCInfo,
    unsigned NextStackOffset, const MYRISCVXFunctionInfo& FI) const {

  // Return false if either the callee or caller has a byval argument.
  if (CCInfo.getInRegsParamsCount() > 0 || FI.hasByvalArg())
    return false;

  // Return true if the callee's argument area is no larger than the
  // caller's.
  return NextStackOffset <= FI.getIncomingArgSize();
}