Générer l'opcode d'appel final

Question

Par curiosité j'ai essayé de générer un appel tail opcode à l'aide de C#. Fibinacci est facile, donc mon exemple en c# ressemble à ceci:

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

Si je le construire dans la libération et de l'exécuter sans débogage je ne suis pas un débordement de pile. Le débogage ou le courant sans optimisations et je dois obtenir un débordement de la pile, ce qui implique que la queue d'appel est de travailler quand dans la version avec des optimisations (qui est ce que j'attendais).

Le MSIL pour cette ressemble à ceci:

.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 
}

Je l'ai attendu de voir une queue opcode, par la msdn, mais il n'est pas là. Cela m'a demande si le compilateur JIT a été chargé de mettre là? J'ai essayé de ngen l'assemblée (à l'aide d' ngen install <exe>, dans la windows assemblées liste pour l'obtenir) et la charge en ILSpy mais c'est la même chose pour moi:

.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 
}

Je n'ai toujours pas le voir.

Je sais que F# poignées d'appel tail bien, j'ai donc voulu comparer ce F# a fait avec ce que le C# n'. Mon F# exemple ressemble à ceci:

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


Console.WriteLine (fibb 3 0)

Et l'généré IL pour le fib méthode ressemble à ceci:

.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
}

Qui, selon ILSpy, est équivalent à ceci:

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

Donc F# générés queue appel à l'aide des instructions goto? Ce n'est pas ce à quoi je m'attendais.

Je n'essaie pas de s'appuyer sur la queue appeler de n'importe où, mais je suis juste curieux de savoir où est-ce que opcode préparez-vous? Comment est C# fait-il cela?

Answer 1

Compilateur C# ne vous donne pas toutes les garanties quant à la queue-appel optimisations parce que le C# programmes utilisent généralement des boucles et donc ils ne comptent pas sur la queue appel à des optimisations. Donc, en C#, c'est tout simplement un JIT optimisation qui peut ou peut ne pas arriver (et vous ne pouvez pas compter sur elle).

Compilateur F# est conçu pour gérer le code fonctionnel qui utilise la récursivité et ainsi il vous donne certaines garanties quant à la queue-les appels. Cela se fait de deux façons:

• si vous écrivez une fonction récursive qui s'appelle elle-même (comme votre fib) le compilateur transforme en une fonction qui utilise la boucle dans le corps (c'est une simple optimisation et le code produit est plus rapide que d'utiliser une queue-appel)

• si vous utilisez un appel récursif dans un complexe de position (lors de l'utilisation de continuation passing style où la fonction est passée comme argument), alors le compilateur génère une queue-appel d'instruction qui l'a dit à l'équipe qu'il doit utiliser une queue d'appel.

Comme exemple du second cas, compiler les suivantes simple fonction F# F# ne pas le faire dans le mode de Débogage pour simplifier le débogage, vous devrez le mode de Libération ou d'ajouter --tailcalls+):

let foo a cont = cont (a + 1)

La fonction appelle simplement la fonction cont avec le premier argument incrémenté de un. Dans le prolongement, passant du style, vous avez une longue séquence de tels appels, de sorte que l'optimisation est indispensable (vous ne pouvez pas utiliser ce style sans une certaine manipulation de la queue d'appels). L'génère du code IL ressemble à ceci:

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

La situation avec la queue d'appel d'optimisation de l' .Net est assez compliqué. Pour autant que je sais, c'est comme ça:

• Le compilateur C# sera jamais émettre l' tail. opcode et il permettra également de ne jamais faire la queue appeler l'optimisation par lui-même.
• Le compilateur F# parfois émet l' tail. opcode et fait parfois la queue d'appel d'optimisation par elle-même en émettant des IL qui n'est pas récursive.
• Le CLR mettra à l'honneur l' tail. opcode si il est présent et 64 bits CLR parfois faire la queue appel d'optimisation, même lorsque l'opcode n'est pas présent.

Donc, dans votre cas, vous ne voyez pas l' tail. opcode dans le IL générés par le compilateur C#, car elle ne fait pas ça. Mais la méthode était la queue-appel optimisé, car le CLR n'est parfois que, même sans l'opcode.

Et dans le F# cas, vous avez observé que le compilateur f# fait l'optimisation par lui-même.

Answer 3

Comme tous les optimisations dans .NET, la queue d'appel d'optimisation est un travail effectué par le scintillement, pas le compilateur. La philosophie est que le fait de mettre le travail sur le jitter est utile depuis n'importe quelle langue en bénéficieront et la normalement difficile tâche d'écriture et le débogage de code optimiseur doit être fait qu'une seule fois par l'architecture.

Vous avez à regarder le code machine généré pour voir qu'il fait, Debug + Windows + Démontage. À l'autre exigence que vous le faire en regardant la Version de publication code qui est généré avec les Outils + Options, le Débogage, le Général, de Supprimer JIT optimisation blanc.

Le x64 code ressemble à ceci:

        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  

Note l'importance de l'instruction, un saut au lieu d'un appel. Que la queue d'appeler l'optimisation au travail. Un caprice dans .NET est que le 32 bits x86 gigue ne pas effectuer cette optimisation. Tout simplement un objet à faire qu'ils vont probablement jamais obtenir autour de. Qui n'a besoin le compilateur F# écrivains de ne pas ignorer le problème et émettre des Opcodes.Tailcall. Vous trouverez d'autres optimisations de la gigue documenté dans cette réponse.