Сгенерировать код операции хвостового вызова

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 сборки (используя 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)

И сгенерированный IL для метода fib выглядит так:

.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, который не является рекурсивным.
• ЦПР будет соблюдать tail. код операции, если он присутствует, и 64-битный CLR иногда выполняет оптимизацию хвостового вызова, даже если код операции отсутствует.

Итак, в вашем случае вы не видели tail. код операции в IL, сгенерированный компилятором C#, потому что он этого не делает. Но метод был оптимизирован с помощью хвостового вызова, потому что CLR иногда делает это даже без кода операции.

А в случае F# вы заметили, что компилятор F# выполнил оптимизацию сам по себе.

Answer 3

Как и все оптимизации, выполняемые в.NET (языки Roslyn), оптимизация хвостовых вызовов - это работа, выполняемая джиттером, а не компилятором. Философия заключается в том, что наложение работы на джиттер полезно, поскольку любой язык извлечет из этого пользу, и обычно сложная работа по написанию и отладке оптимизатора кода должна выполняться только один раз для каждой архитектуры.

Вы должны посмотреть на сгенерированный машинный код, чтобы увидеть, как это делается, Debug + Windows + Disassembly. С дополнительным требованием, которое вы выполняете, взглянув на код сборки Release, который генерируется без снятого флажка "Инструменты + параметры", "Отладка", "Общее", "Подавить оптимизацию 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. Вы найдете другие оптимизации, выполненные джиттером, которые описаны в этом ответе.