C#と諸々 [ .NET ] CLI

末尾最適化を検証

[ .NET ] CLI

2008/10/09 00:30

まず、末尾再帰を行う単純な C# コード。

NoOptimization.cs
using System;
using System.Diagnostics;

static class Program
{
    static void Main(string[] args)
    {
        TailCall(5);
        Console.ReadLine();
    }

    static int TailCall(int i)
    {
        int frameCount = new StackTrace().FrameCount;
        Console.WriteLine("FrameCount:{0}", frameCount);
        if (i == 0)
        {
            return i;
        }
        i--;
        return TailCall(i);
    }
}
これと等価な IL コード。

NoOptimization.il
.assembly extern mscorlib { }
.assembly NoOptimization { }

.class private abstract auto ansi sealed beforefieldinit Program
    extends [mscorlib]System.Object
{
    .method private hidebysig static void Main(string[] args) cil managed
    {
        .entrypoint
        .maxstack 8
        ldc.i4.5
        call int32 Program::TailCall(int32)
        pop
        call string [mscorlib]System.Console::ReadLine()
        pop
        ret
    }

    .method private hidebysig static int32 TailCall(int32 i) cil managed
    {
        .maxstack 2
        .locals init (
            [0] int32 frameCount)
        newobj instance void [mscorlib]System.Diagnostics.StackTrace::.ctor()
        callvirt instance int32 [mscorlib]System.Diagnostics.StackTrace::get_FrameCount()
        stloc.0
        ldstr "FrameCount:{0}"
        ldloc.0
        box int32
        call void [mscorlib]System.Console::WriteLine(string, object)
        ldarg.0
        brtrue.s Label1
        ldarg.0
        ret
Label1:
        ldarg.0
        ldc.i4.1
        sub
        starg.s i
        ldarg.0
        call int32 Program::TailCall(int32)
        ret
    }
}
実行結果はこちら。末尾最適化が行われていないことがわかる。

FrameCount:2
FrameCount:3
FrameCount:4
FrameCount:5
FrameCount:6
FrameCount:7

続いて、IL コードに tail. プレフィックスを追加してみる。
追加する場所は、TailCall メソッドの下から 3 行目。

Optimization.il
.assembly extern mscorlib { }
.assembly Optimization { }

.class private abstract auto ansi sealed beforefieldinit Program
    extends [mscorlib]System.Object
{
    .method private hidebysig static void Main(string[] args) cil managed
    {
        .entrypoint
        .maxstack 8
        ldc.i4.5
        call int32 Program::TailCall(int32)
        pop
        call string [mscorlib]System.Console::ReadLine()
        pop
        ret
    }

    .method private hidebysig static int32 TailCall(int32 i) cil managed
    {
        .maxstack 2
        .locals init (
            [0] int32 frameCount)
        newobj instance void [mscorlib]System.Diagnostics.StackTrace::.ctor()
        callvirt instance int32 [mscorlib]System.Diagnostics.StackTrace::get_FrameCount()
        stloc.0
        ldstr "FrameCount:{0}"
        ldloc.0
        box int32
        call void [mscorlib]System.Console::WriteLine(string, object)
        ldarg.0
        brtrue.s Label1
        ldarg.0
        ret
Label1:
        ldarg.0
        ldc.i4.1
        sub
        starg.s i
        ldarg.0
        tail.
        call int32 Program::TailCall(int32)
        ret
    }
}
実行結果はこちら。末尾最適化が行われていることがわかる。

FrameCount:2
FrameCount:2
FrameCount:2
FrameCount:2
FrameCount:2
FrameCount:2

さてここで、Optimization.il の TailCall メソッドに noinlining を付加して試してみる。

NoInlining.il
.assembly extern mscorlib { }
.assembly NoInlining { }

.class private abstract auto ansi sealed beforefieldinit Program
    extends [mscorlib]System.Object
{
    .method private hidebysig static void Main(string[] args) cil managed
    {
        .entrypoint
        .maxstack 8
        ldc.i4.5
        call int32 Program::TailCall(int32)
        pop
        call string [mscorlib]System.Console::ReadLine()
        pop
        ret
    }

    .method private hidebysig static int32 TailCall(int32 i) cil managed noinlining
    {
        .maxstack 2
        .locals init (
            [0] int32 frameCount)
        newobj instance void [mscorlib]System.Diagnostics.StackTrace::.ctor()
        callvirt instance int32 [mscorlib]System.Diagnostics.StackTrace::get_FrameCount()
        stloc.0
        ldstr "FrameCount:{0}"
        ldloc.0
        box int32
        call void [mscorlib]System.Console::WriteLine(string, object)
        ldarg.0
        brtrue.s Label1
        ldarg.0
        ret
Label1:
        ldarg.0
        ldc.i4.1
        sub
        starg.s i
        ldarg.0
        tail.
        call int32 Program::TailCall(int32)
        ret
    }
}
実行結果はこちら。noinlining を付加しても末尾最適化が行われていることが確認できる。

FrameCount:2
FrameCount:2
FrameCount:2
FrameCount:2
FrameCount:2
FrameCount:2

では、Optimization.il の TailCall メソッドに reqsecobj を付加して試してみる。

ReqSecObj.il
.assembly extern mscorlib { }
.assembly ReqSecObj { }

.class private abstract auto ansi sealed beforefieldinit Program
    extends [mscorlib]System.Object
{
    .method private hidebysig static void Main(string[] args) cil managed
    {
        .entrypoint
        .maxstack 8
        ldc.i4.5
        call int32 Program::TailCall(int32)
        pop
        call string [mscorlib]System.Console::ReadLine()
        pop
        ret
    }

    .method private hidebysig static reqsecobj int32 TailCall(int32 i) cil managed
    {
        .maxstack 2
        .locals init (
            [0] int32 frameCount)
        newobj instance void [mscorlib]System.Diagnostics.StackTrace::.ctor()
        callvirt instance int32 [mscorlib]System.Diagnostics.StackTrace::get_FrameCount()
        stloc.0
        ldstr "FrameCount:{0}"
        ldloc.0
        box int32
        call void [mscorlib]System.Console::WriteLine(string, object)
        ldarg.0
        brtrue.s Label1
        ldarg.0
        ret
Label1:
        ldarg.0
        ldc.i4.1
        sub
        starg.s i
        ldarg.0
        tail.
        call int32 Program::TailCall(int32)
        ret
    }
}
実行結果はこちら。noinlining とは異なり、reqsecobj を付加すると末尾最適化が行われなくなることが確認できる。

FrameCount:2
FrameCount:3
FrameCount:4
FrameCount:5
FrameCount:6
FrameCount:7

[関連記事]
JIT 最適化にも負けずに呼び出し元のメソッドを取得する方法

スポンサーサイト