オリジナルLLVM Backendを追加しよう (24. Tail call optimizationの実装)

LLVMにはすでにRISC-Vのバックエンドサポートが追加されている。しかし、勉強のために独自のRISC-V実装をLLVMに追加している。

jonathan2251.github.io

関数コールの最適化の一つとして、Tail call optimization(末尾再帰呼び出し)を実装してみる。

ja.wikipedia.org

LLVMにはTail CallというIRが用意されており、これで末尾再帰呼び出しを表現して、最適化に使用することができるようだ。

サンプルプログラム :

int factorial(int x)
{
  if (x > 0)
    return x*factorial(x-1);
  else
    return 1;
}

int test_tailcall(int a)
{
  return factorial(a);
}

これをコンパイルする。まずは-O0オプションから。

./bin/clang -O0 -c -target mips-unknown-linux-gnu ../lbdex/input/ch9_2_tailcall.cpp -emit-llvm
./bin/llvm-dis ch9_2_tailcall.bc -o -

define dso_local i32 @_Z9factoriali(i32 signext %x) #0 {
entry:
  %retval = alloca i32, align 4
  %x.addr = alloca i32, align 4
  store i32 %x, i32* %x.addr, align 4
  %0 = load i32, i32* %x.addr, align 4
  %cmp = icmp sgt i32 %0, 0
  br i1 %cmp, label %if.then, label %if.else

if.then:                                          ; preds = %entry
  %1 = load i32, i32* %x.addr, align 4
  %2 = load i32, i32* %x.addr, align 4
  %sub = sub nsw i32 %2, 1
  %call = call i32 @_Z9factoriali(i32 signext %sub)
  %mul = mul nsw i32 %1, %call
  store i32 %mul, i32* %retval, align 4
  br label %return

if.else:                                          ; preds = %entry
  store i32 1, i32* %retval, align 4
  br label %return

return:                                           ; preds = %if.else, %if.then
  %3 = load i32, i32* %retval, align 4
  ret i32 %3
}

; Function Attrs: noinline optnone
define dso_local i32 @_Z13test_tailcalli(i32 signext %a) #0 {
entry:
  %a.addr = alloca i32, align 4
  store i32 %a, i32* %a.addr, align 4
  %0 = load i32, i32* %a.addr, align 4
  %call = call i32 @_Z9factoriali(i32 signext %0)
  ret i32 %call
}

普通の関数呼び出しが実行されている。これを、最適化していくとどうなるのか。

./bin/clang -O1 -c -target mips-unknown-linux-gnu ../lbdex/input/ch9_2_tailcall.cpp -emit-llvm
./bin/llvm-dis ch9_2_tailcall.bc -o -

; Function Attrs: nounwind readnone
define dso_local i32 @_Z9factoriali(i32 signext %x) local_unnamed_addr #0 {
entry:
  %cmp3 = icmp sgt i32 %x, 0
  br i1 %cmp3, label %if.then, label %return

if.then:                                          ; preds = %entry, %if.then
  %x.tr5 = phi i32 [ %sub, %if.then ], [ %x, %entry ]
  %accumulator.tr4 = phi i32 [ %mul, %if.then ], [ 1, %entry ]
  %sub = add nsw i32 %x.tr5, -1
  %mul = mul nsw i32 %x.tr5, %accumulator.tr4
  %cmp = icmp sgt i32 %x.tr5, 1
  br i1 %cmp, label %if.then, label %return

return:                                           ; preds = %if.then, %entry
  %accumulator.tr.lcssa = phi i32 [ 1, %entry ], [ %mul, %if.then ]
  ret i32 %accumulator.tr.lcssa
}

; Function Attrs: nounwind readnone
define dso_local i32 @_Z13test_tailcalli(i32 signext %a) local_unnamed_addr #0 {
entry:
  %call = tail call i32 @_Z9factoriali(i32 signext %a)
  ret i32 %call
}

おや、test_tailcallが末尾再帰として認識された。

これを-enable-myriscvx-tail-callsを付加してアセンブリを出力するとどうなるのか。

• O0でコンパイルしたもの

_Z13test_tailcalli:
# %bb.0:                                # %entry
    lui x10, %hi(_gp_disp)
    addi    x10, x10, %lo(_gp_disp)
    addi    x2, x2, -16
    .cfi_def_cfa_offset 16
    sw  x10, 12(x2)
    lw  x10, 12(x2)
    lw  x3, %call16(_Z9factoriali)(x3)
    jalr    x3
    addi    x2, x2, 16
    jalr    x1

• O1でコンパイルしたもの

_Z13test_tailcalli:
# %bb.0:                                # %entry
    lui x10, %hi(_gp_disp)
    addi    x10, x10, %lo(_gp_disp)
    lw  x3, %call16(_Z9factoriali)(x3)
    jalr    x3

確かに、スタックの操作がなくなってそのままfactorialを呼び出しているようだ。