関数呼び出しには様々な最適化の形があるが、その中の一つである末尾関数呼び出しでの最適化を実行してみる。末尾関数呼び出しとは、ある関数f1()が関数f2()の最後の処理として呼び出されるケースを言う。
int f1(a, b) { a + b; } int f2(c, d, e, f) { /* 様々な処理*/ return f1(10, 20); }
この場合、関数f1()を呼び出すためには引数渡しの処理、スタックの処理、そして呼び出しから戻ってきた場合には戻り値の処理やスタックの後片付けを行う必要がある。
しかし、場合によってはこれが不要なことがある。つまり、どっちにしろf1から戻った後はf2からも戻ってしまうのだから、せっかくなのでf2のスタック領域などもf1で使わせてもらって、関数呼び出し時のスタックの掘り下げを省略してしまいます。つまり、末尾呼び出しではスタックフレームを追加することなくf1を呼び出すことができる。
しかし、この末尾呼び出しはすべての条件下で実現可能なわけではない。上記で説明した通り、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=mips-unknown-elf tailcall.cpp -c -emit-llvm -o tailcall.o1.bc ./bin/clang -O0 --target=mips-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-myriscvx/lib/Target/MYRISCVX/MYRISCVXISelLowering.cpp
//@LowerCall { /// LowerCall - functions arguments are copied from virtual regs to /// (physical regs)/(stack frame), CALLSEQ_START and CALLSEQ_END are emitted. SDValue MYRISCVXTargetLowering::LowerCall(TargetLowering::CallLoweringInfo &CLI, SmallVectorImpl<SDValue> &InVals) const { ... bool &IsTailCall = CLI.IsTailCall; ... // Check if it's really possible to do a tail call. if (IsTailCall) IsTailCall = isEligibleForTailCallOptimization(CCInfo, NextStackOffset, *MF.getInfo<MYRISCVXFunctionInfo>()); if (!IsTailCall && CLI.CS && CLI.CS.isMustTailCall()) report_fatal_error("failed to perform tail call elimination on a call " "site marked musttail"); ...
IsTailCall変数は関数呼び出しが末尾関数呼び出しになっている場合にまずはTrueとなる。次に、本当に末尾関数呼び出し最適化が適用可能かチェックする。これを行っているのがisEligibleForTailCallOptimizationだ。
llvm-myriscvx/lib/Target/MYRISCVX/MYRISCVXSEISelLowering.cpp
bool MYRISCVXSETargetLowering:: isEligibleForTailCallOptimization(const CCState &CCInfo, unsigned NextStackOffset, const MYRISCVXFunctionInfo& FI) const { if (!EnableMYRISCVXTailCalls) return false; // 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(); }
末尾関数呼び出し最適化が適用できる条件としては、
EnableMYRISCVXTailCallsがTrue、つまりllcのオプションで-enable-MYRISCVX-tail-callsがTrueになっていないとダメだ。- 呼び出し先もしくは呼び出し元が
byvalの引数を持っている場合はダメだ。 - 呼び出し先が使用する予定のスタックサイズ(
NextStackOffset)よりも呼び出し元が持っているスタックのサイズFI.getIncomingArgSize()が大きい場合はダメだ。
上記をすべてクリアできれば末尾関数呼び出し最適化が適用できる。
では、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で新たなノードとして定義する。MYRISCVXCallSeqStartやMYRISCVXCallSeqEndのように、TailCallノードもノードとして定義しておく(後で除去するため)。
llvm-myriscvx/lib/Target/MYRISCVX/MYRISCVXInstrInfo.td
// Tail call def MYRISCVXTailCall : SDNode<"MYRISCVXISD::TailCall", SDT_MYRISCVXCall, [SDNPHasChain, SDNPOptInGlue, SDNPVariadic]>; ... let isCall = 1, isTerminator = 1, isReturn = 1, isBarrier = 1, hasDelaySlot = 0, hasExtraSrcRegAllocReq = 1 in { class TailCall<Instruction JumpInst> : MYRISCVXPseudo<(outs), (ins calltarget:$target), "", []>, PseudoInstExpansion<(JumpInst calltarget:$target)>; class TailCallReg<RegisterClass RO, Instruction JRInst, RegisterClass ResRO = RO> : MYRISCVXPseudo<(outs), (ins RO:$rs), "", [(MYRISCVXTailCall RO:$rs)]>, PseudoInstExpansion<(JRInst ResRO:$rs)>; }
TailCallとTailCallRegを定義しました。通常はTailCallのみで良いはずだが、PIC時にレジスタ経由でのジャンプすることも想定して、TailCallRegを作っておく。どちらも実際は疑似命令で、最終的にはJAL命令もしくはJALRに置き換えられる。
def TAILCALL : TailCall<JAL>; def TAILCALL_R : TailCallReg<GPR, JALR>;
TAILCALL側にはDAG生成パタンを登録していないので、パタンを登録しておく。
def : Pat<(MYRISCVXTailCall (iPTR tglobaladdr:$dst)),
(TAILCALL tglobaladdr:$dst)>;
def : Pat<(MYRISCVXTailCall (iPTR texternalsym:$dst)),
(TAILCALL texternalsym:$dst)>;
