生成尾调用操作码 [英] 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
,第一个参数加一.在延续传递风格中,您有很长的此类调用序列,因此优化至关重要(如果不处理尾调用,您根本无法使用这种风格).生成的 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屋!