产生尾调用操作码(Generate tail call opcode)

出于好奇，我试图生成使用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的组件（使用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用加一的第一个参数。 在延续传递风格，你有这样的呼叫的长序列，所以优化是至关重要的（你根本无法使用这种风格没有一些处理尾调用的）。 该产生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这不是递归本身并不尾部调用优化。
• CLR将兑现tail. 如果目前的操作码和64位CLR有时会令尾部调用优化，即使操作码不存在。

所以，你的情况，你没有看到tail. 由C＃编译器生成的操作码的IL，因为它没有做到这一点。 但是，该方法是尾调用优化，因为CLR有时做，即使没有操作码。

而在F＃的情况下，您观察到，F＃编译器本身做了优化。

Answer 3:

像.NET（罗斯林语言）执行的所有优化，尾部调用优化是通过抖动，没有编译器执行的工作。 理念是把工作的抖动是有用的，因为任何语言将它和写作的一般困难的工作中受益，并调试代码优化，必须每建筑只需进行一次。

你必须查看生成的机器代码，看它正在做，调试+的Windows +拆卸。 与您查看的是与工具+选项生成的发布版本代码，这样做进一步的要求，调试，通用，禁止JIT优化取消选中。

该64位代码如下所示：

        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。 你会发现在记录的抖动进行其他优化这个答案 。

文章来源: Generate tail call opcode