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

Question

Из любопытства я пытался сгенерировать код операции хвоста с помощью 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>, навигации по списку окна сборками, чтобы получить его) и загрузить его обратно в 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 для метода выдумки выглядит следующим образом:

.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 (языки Roslyn), оптимизация хвостовых вызовов - это работа, выполняемая дрожанием, а не компилятором. Философия заключается в том, что работа над дрожанием полезна, поскольку любой язык будет полезен, и обычно сложная работа по написанию и отладке оптимизатора кода должна выполняться только один раз для каждой архитектуры.

Вы должны посмотреть на сгенерированный машинный код, чтобы убедиться, что это делается, Debug + Windows + Disassembly. С дополнительным требованием, которое вы делаете, просмотрев код сборки Release, который генерируется с помощью опций Tools + Options, Debugging, General, Suppress 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. Вы найдете другие оптимизации, выполненные джиттером, зарегистрированными в this answer.

Answer 3

Ситуация с оптимизацией вызова хвоста в .Net довольно сложна. Насколько я знаю, это так:

• C# компилятор никогда не будет излучать tail. опкод и также никогда не делать хвостовую оптимизацию самого по себе.
• Компилятор F # иногда испускает код операции tail., а иногда и оптимизацию хвостового вызова сам по себе, испуская ИЛ, который не является рекурсивным.
• CLR будет выполнять код операции tail., если он присутствует, и 64-разрядная среда CLR иногда может оптимизировать хвостовой вызов, даже если код операции отсутствует.

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

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