生成尾部调用操作码 [英] Generate tail call opcode

问题描述

出于好奇，我试图使用C＃生成尾部调用操作码。 Fibinacci很简单，所以我的c＃示例如下：

Out of curiosity I was trying to generate a tail call opcode using C#. Fibinacci is an easy one, so my c# example looks like this:

    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);
    }

如果我在发行版中进行构建并在未调试的情况下运行它，则不会获得堆栈溢出。在没有优化的情况下调试或运行它，但确实出现了堆栈溢出，这意味着在发布具有优化功能的尾部调用时，该调用是有效的（这是我所期望的）。

If I build it in release and run it without debugging I do not get a stack overflow. Debugging or running it without optimizations and I do get a stack overflow, implying that tail call is working when in release with optimizations on (which is what I expected).

MSIL看起来像这样：

The MSIL for this looks like this:

.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中，但外观相同给我：

I would've expected to see a tail opcode, per the msdn, but it's not there. This got me wondering if the JIT compiler was responsible for putting it in there? I tried to ngen the assembly (using ngen install <exe>, navigating to the windows assemblies list to get it) and load it back up in ILSpy but it looks the same to me:

.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＃示例如下所示：

I know F# handles tail call well, so I wanted to compare what F# did with what C# did. My F# example looks like this:

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


Console.WriteLine (fibb 3 0)

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

And the generated IL for the fib method looks like this:

.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，这是等效的对此：

Which, according to ILSpy, is equivalent to this:

[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语句生成了尾调用？这不是我所期望的。

So F# generated tail call using goto statements? This isn't what I was expecting.

我不是想在任何地方依赖尾调用，但是我很好奇这个操作码在哪里设置？ C＃如何做到这一点？

I'm not trying to rely on tail call anywhere, but I am just curious where exactly does that opcode get set? How is C# doing this?

推荐答案

C＃编译器无法为您提供有关尾调用的任何保证优化，因为C＃程序通常使用循环，因此它们不依赖于尾调用优化。因此，在C＃中，这只是一个JIT优化，可能会发生也可能不会发生（并且您不能依靠它）。

C# compiler does not give you any guarantees about tail-call optimizations because C# programs usually use loops and so they do not rely on the tail-call optimizations. So, in C#, this is simply a JIT optimization that may or may not happen (and you cannot rely on it).

F＃编译器设计用于处理使用递归的功能代码，因此确实为您提供了有关尾部调用的保证。这可以通过两种方式完成：

F# compiler is designed to handle functional code that uses recursion and so it does give you certain guarantees about tail-calls. This is done in two ways:

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

• if you write a recursive function that calls itself (like your fib) the compiler turns it into a function that uses loop in the body (this is a simple optimization and the produced code is faster than using a tail-call)

如果您在较复杂的位置使用递归调用（使用使用函数作为参数传递的连续传递样式时），则编译器将生成一条尾部调用指令，该指令将通知JIT 必须使用尾部调用。

if you use a recursive call in a more complex position (when using continuation passing style where function is passed as an argument), then the compiler generates a tail-call instruction that tells the JIT that it must use a tail call.

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

As an example of the second case, compile the following simple F# function (F# does not do this in Debug mode to simplify debugging, so you may need Release mode or add --tailcalls+):

let foo a cont = cont (a + 1)

该函数只调用函数 cont ，第一个参数加1。在连续传递样式中，此类调用的序列很长，因此优化至关重要（如果不对尾部调用进行某些处理，就无法使用此样式）。生成的IL代码如下所示：

The function simply calls the function cont with the first argument incremented by one. In continuation passing style, you have a long sequence of such calls, so the optimization is crucial (you simply cannot use this style without some handling of tail calls). The generates IL code looks like this:

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

这篇关于生成尾部调用操作码的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！