生成尾调用指令

Question

出于好奇我试图使用C#生成一个尾调用操作码。 斐波那契数列是一个简单的例子，因此我的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>对程序集进行ngened（导出原生映像），并在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#是如何做到这一点的？

- devshorts

---

F#（就像IronScheme一样）使用尾调用消除将“昂贵”的尾调用更改为“廉价”的本地跳转。这是在编译器中完成的。 - leppie

@devshorts：这种优化被称为尾调用消除，因此您不会看到它（尾操作码或调用）。您需要一个更复杂的示例来防止这种优化。 - leppie

@devshorts：JIT 不会改变 MSIL。它会生成机器码。请参考 Hans 的答案，他查看了 JIT 的输出并发现尾调用已被转换为跳转。 - Ben Voigt

据我所知，tail.调用的生成也取决于您是为x86还是x64编译。上次我读到关于这个问题的时候，当针对x64时，尾调用优化无法工作。 - stakx - no longer contributing

请参阅 http://blogs.msdn.com/b/fsharpteam/archive/2011/07/08/tail-calls-in-fsharp.aspx 以获取有关 F# 如何处理尾调用的更多低级细节。 - kvb

Answer 1

C#编译器不保证尾递归优化，因为C#程序通常使用循环，所以它们不依赖于尾递归优化。因此，在C#中，这只是一种可能发生的JIT（Just-In-Time）优化，您不能依赖它。

F#编译器旨在处理使用递归的函数式代码，因此它确实对尾调用给出了某些保证。它通过两种方式实现：

• 如果您编写一个调用自身的递归函数（例如fib），则编译器将其转换为在函数体中使用循环的函数（这是一个简单的优化，生成的代码比使用尾递归更快）

• 如果您在更复杂的位置使用递归调用（在继续传递样式中使用函数作为参数时），则编译器会生成一个尾调用指令，告诉JIT必须使用尾调用。

以下是第二种情况的示例，请编译以下简单的F＃函数（F＃在调试模式下不会执行此操作，以简化调试，因此您可能需要Release模式或添加--tailcalls+）：

let foo a cont = cont (a + 1)

该函数仅仅是使用第一个参数加一作为参数调用cont函数。在继续传递样式中，你有一长串这样的调用序列，所以优化至关重要（如果没有一些尾部调用处理，你根本无法使用这种风格）。生成的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

- Tomas Petricek

---

我认为C#编译器不使用尾调用的主要原因是因为它会使堆栈跟踪看起来“不正确”。 - Timwi

这是F#调试模式下默认禁用尾调用的原因之一。 - Tomas Petricek

当然可以，但是堆栈跟踪不仅适用于调试模式。客户在发布模式下运行您的程序（并生成异常堆栈跟踪）。 - Timwi

@Timwi 堆栈跟踪仍将存在并且仍然很有用，我想这可能更适合在调试时步进（在发布模式下您可能不会这样做），而不是与最终跟踪的推理能力有所不同。 - Sprague

Answer 2

在.Net中，关于尾调用优化的情况非常复杂。据我所知，情况如下：

1. C# 编译器不会生成 tail. 操作码，也不会自己进行尾调用优化。

2. F# 编译器有时会生成 tail. 操作码，有时会通过生成非递归的 IL 自己进行尾调用优化。

3. 如果存在 tail. 操作码，CLR 会遵循它，即使未提供操作码，64位 CLR 也有时会进行尾调用优化。

因此，在您的情况下，您没有在 C# 编译器生成的 IL 中看到 tail. 操作码，因为它不会这样做。但是该方法已被尾调用优化，因为 CLR 偶尔会在没有操作码的情况下进行优化。

在 F# 的情况下，您观察到 F# 编译器自己进行了优化。

- svick

---

感谢您清晰简洁的回答，非常有帮助！ - devshorts

Answer 3

像 .NET (Roslyn 语言) 中执行的所有优化一样，尾调用优化是由即时编译器（JIT）而非编译器执行的工作。其哲学在于将该任务交给 JIT 执行很有用，因为任何语言都会从中受益，而编写和调试代码优化器通常很困难且只需要针对每个体系结构完成一次。

您必须查看生成的机器代码才能看到它的执行过程，通过选择“调试”、“窗口”、“反汇编”。此外，您还需通过选择“工具”、“选项”、“调试”、“常规”，取消选中“抑制 JIT 优化”来查看 Release 构建代码。

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。 您将在此答案中找到 JIT 编译器执行的其他优化。

- Hans Passant

---

我认为这个问题特别关注于tail.操作码，而你甚至没有提到它。 - svick

这怎么是一种合法的优化？它改变了程序的可观察行为（关于堆栈跟踪，这对代码访问安全和异常报告至关重要）。好吧，在这种情况下没有调用任何其他函数，因此可以证明CAS不是一个问题。 - Ben Voigt

@leppie：我并不是说在大多数情况下消除堆栈帧不可取；我是说它会改变可观察行为（除运行时外），因此不适合进行优化。对于CAS，它是否区分（我的调用者）和（我的调用者的调用者）？尾调用消除可能会改变后者。 - Ben Voigt

这是无稽之谈，方法内联也是一种标准优化。 - Hans Passant

“在“.NET”中进行的优化”在句子“就像在“.NET”中执行的所有优化一样（……）是由jitter执行的任务”中是什么意思呢？ “在“.NET”中”是指Jitter吗？如果是这样，那么这个句子是重言（而且只会让人感到困惑）。还是说你是指.NET语言总体上的优化？如果是这样，它就是错误的，因为F#做了其他的优化。（我知道C#和VB不这样做，但那是另外一个故事……） - Tomas Petricek