生成尾调用操作码

Question

出于好奇,我试图使用C#生成尾调用操作码.Fibinacci是一个简单的,所以我的c#示例如下所示:

    private static void Main(string[] args)
    {
        Console.WriteLine(Fib(int.MaxValue, 0));
    }

    public static int Fib(int i, int acc)
    {
        if (i == 0)
        {
            return acc;
        }

        return Fib(i - 1, acc + i);
    }

如果我在发布中构建并在没有调试的情况下运行它,我就不会出现堆栈溢出.在没有优化的情况下调试或运行它,我确实得到了堆栈溢出,这意味着尾部调用在发布时具有优化功能(这是我的预期).

这个MSIL看起来像这样:

.method public hidebysig static int32 Fib(int32 i, int32 acc) cil managed
{
    // Method Start RVA 0x205e
    // Code Size 17 (0x11)
    .maxstack 8
    L_0000: ldarg.0 
    L_0001: brtrue.s L_0005
    L_0003: ldarg.1 
    L_0004: ret 
    L_0005: ldarg.0 
    L_0006: ldc.i4.1 
    L_0007: sub 
    L_0008: ldarg.1 
    L_0009: ldarg.0 
    L_000a: add 
    L_000b: call int32 [ConsoleApplication2]ConsoleApplication2.Program::Fib(int32,int32)
    L_0010: ret 
}

我希望看到一个尾部操作码,根据msdn,但它不存在.这让我想知道JIT编译器是否负责将它放在那里？我尝试使用程序集(使用ngen install <exe>,导航到Windows程序集列表来获取它)并将其加载到ILSpy中,但它看起来与我相同:

.method public hidebysig static int32 Fib(int32 i, int32 acc) cil managed
{
    // Method Start RVA 0x3bfe
    // Code Size 17 (0x11)
    .maxstack 8
    L_0000: ldarg.0 
    L_0001: brtrue.s L_0005
    L_0003: ldarg.1 
    L_0004: ret 
    L_0005: ldarg.0 
    L_0006: ldc.i4.1 
    L_0007: sub 
    L_0008: ldarg.1 
    L_0009: ldarg.0 
    L_000a: add 
    L_000b: call int32 [ConsoleApplication2]ConsoleApplication2.Program::Fib(int32,int32)
    L_0010: ret 
}

我仍然没有看到它.

我知道F#可以很好地处理尾调用,所以我想比较一下F#做了什么和C#做了什么.我的F#示例如下所示:

let rec fibb i acc =  
    if i = 0 then
        acc
    else 
        fibb (i-1) (acc + i)


Console.WriteLine (fibb 3 0)

并且为fib方法生成的IL看起来像这样:

.method public static int32 fibb(int32 i, int32 acc) cil managed
{
    // Method Start RVA 0x2068
    // Code Size 18 (0x12)
    .custom instance void [FSharp.Core]Microsoft.FSharp.Core.CompilationArgumentCountsAttribute::.ctor(int32[]) = { int32[](Mono.Cecil.CustomAttributeArgument[]) }
    .maxstack 5
    L_0000: nop 
    L_0001: ldarg.0 
    L_0002: brtrue.s L_0006
    L_0004: ldarg.1 
    L_0005: ret 
    L_0006: ldarg.0 
    L_0007: ldc.i4.1 
    L_0008: sub 
    L_0009: ldarg.1 
    L_000a: ldarg.0 
    L_000b: add 
    L_000c: starg.s acc
    L_000e: starg.s i
    L_0010: br.s L_0000
}

据ILSpy称,这相当于:

[Microsoft.FSharp.Core.CompilationArgumentCounts(Mono.Cecil.CustomAttributeArgument[])]
public static int32 fibb(int32 i, int32 acc)
{
    label1:
    if !(((i != 0))) 
    {
        return acc;
    }
    (i - 1);
    i = acc = (acc + i);;
    goto label1;
}

那么F#使用goto语句生成尾调用？这不是我所期待的.

我不是想在任何地方依赖尾调用,但我只是好奇那个操作码到底在哪里设置？C#是如何做到这一点的？

Answer 1

C#编译器没有为尾部调用优化提供任何保证,因为C#程序通常使用循环,因此它们不依赖于尾调用优化.因此,在C#中,这只是一个可能会或可能不会发生的JIT优化(并且您不能依赖它).

F#编译器旨在处理使用递归的函数代码,因此它确实为您提供了有关尾调用的一些保证.这有两种方式:

• 如果你编写一个自我调用的递归函数(比如你的fib),编译器将它变成一个在正文中使用循环的函数(这是一个简单的优化,生成的代码比使用尾调用更快)

• 如果你在一个更复杂的位置使用递归调用(当使用函数作为参数传递的连续传递样式时),编译器会生成一个尾调用指令,告诉JIT它必须使用尾调用.

作为第二种情况的示例,编译以下简单的F#函数(F#在调试模式下不执行此操作以简化调试,因此您可能需要发布模式或添加--tailcalls+):

let foo a cont = cont (a + 1)

该函数只是cont在第一个参数加1时调用该函数.在连续传递样式中,您有很长的此类调用序列,因此优化是至关重要的(如果没有一些尾调用处理,您根本无法使用此样式).生成IL代码如下所示:

IL_0000: ldarg.1
IL_0001: ldarg.0
IL_0002: ldc.i4.1
IL_0003: add
IL_0004: tail.                          // Here is the 'tail' opcode!
IL_0006: callvirt instance !1 
  class [FSharp.Core] Microsoft.FSharp.Core.FSharpFunc`2<int32, !!a>::Invoke(!0)
IL_000b: ret

Answer 2

.Net中尾调用优化的情况非常复杂.据我所知,它是这样的:

• C#编译器永远不会发出tail.操作码,它也不会自己进行尾调用优化.
• F#编译器有时会发出tail.操作码,有时通过发出不是递归的IL来自行调用尾部优化.
• tail.如果操作码存在,CLR将遵守操作码,即使操作码不存在,64位CLR有时也会进行尾调用优化.

因此,在您的情况下,您没有tail.在C#编译器生成的IL中看到操作码,因为它没有这样做.但该方法是尾调用优化的,因为即使没有操作码,CLR有时也会这样做.

在F#案例中,您观察到f#编译器自己进行了优化.

Answer 3

与在.NET(Roslyn语言)中执行的所有优化一样,尾调用优化是由抖动而不是编译器执行的工作.理念是将工作放在抖动上是有用的,因为任何语言都将从中受益,并且编写和调试代码优化器的通常困难的工作只需要在每个体系结构中完成一次.

您必须查看生成的机器代码才能看到它正在完成,Debug + Windows + Disassembly.进一步要求您通过查看使用工具+选项,调试,常规,抑制JIT优化未生成的版本构建代码来执行此操作.

x64代码如下所示:

        public static int Fib(int i, int acc) {
            if (i == 0) {
00000000  test        ecx,ecx 
00000002  jne         0000000000000008 
                return acc;
00000004  mov         eax,edx 
00000006  jmp         0000000000000011 
            }

            return Fib(i - 1, acc + i);
00000008  lea         eax,[rcx-1] 
0000000b  add         edx,ecx 
0000000d  mov         ecx,eax 
0000000f  jmp         0000000000000000              // <== here!!!
00000011  rep ret  

注意标记的指令,跳转而不是呼叫.这是尾部调用优化工作.在.NET甲怪癖是,32位x86抖动不会不执行该优化.只是一个他们可能永远无法解决的待办事项.这确实要求F#编译器编写者不要忽略该问题并发出Opcodes.Tailcall.您将找到本答案中记录的抖动执行的其他优化.