Générer l’opcode d’appel de queue

Par curiosité, j’essayais de générer un opcode d’appel de queue en utilisant C #. Fibinacci est facile, donc mon exemple c # ressemble à ceci:

private static void Main(ssortingng[] 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 construis dans la version et l’exécute sans déboguer, je ne reçois pas de débordement de stack. Le déboguer ou l’exécuter sans optimisations et j’obtiens un débordement de stack, ce qui implique que l’appel de queue fonctionne lorsqu’il est en version avec des optimisations (ce que j’attendais).

Le MSIL pour cela 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 m’attendais à voir un opcode tail, selon le msdn , mais ce n’est pas là. Cela m’a fait me demander si le compilateur JIT était responsable de le mettre là-dedans? J’ai essayé de construire l’assemblage (en utilisant ngen install , en naviguant dans la liste des assemblys windows pour l’obtenir) et en le chargeant dans ILSpy, mais cela me semble identique:

 .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 ne le vois toujours pas.

Je sais que F # gère bien les appels de queue, donc je voulais comparer ce que F # faisait avec ce que C # faisait. Mon exemple F # 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’IL généré pour la méthode fib 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.CompilationArgumentCountsAtsortingbute::.ctor(int32[]) = { int32[](Mono.Cecil.CustomAtsortingbuteArgument[]) } .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.si L_0010: br.s L_0000 } 

Ce qui, selon ILSpy, équivaut à ceci:

 [Microsoft.FSharp.Core.CompilationArgumentCounts(Mono.Cecil.CustomAtsortingbuteArgument[])] 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é appel de queue en utilisant des instructions goto? Ce n’est pas ce à quoi je m’attendais.

Je n’essaie pas de compter sur l’appel de la queue, mais je suis juste curieux de savoir exactement où cet opcode est défini? Comment C # fait-il cela?

Le compilateur C # ne vous donne aucune garantie quant à l’optimisation des appels de fin, car les programmes C # utilisent généralement des boucles et ne dépendent donc pas des optimisations d’appel. Donc, en C #, il s’agit simplement d’une optimisation JIT qui peut ou non se produire (et vous ne pouvez pas vous y fier).

Le compilateur F # est conçu pour gérer le code fonctionnel qui utilise la récursivité et vous donne donc certaines garanties sur les appels de fin. Cela se fait de deux manières:

  • Si vous écrivez une fonction récursive qui s’appelle elle-même (comme votre fib ), le compilateur le transforme en une fonction qui utilise une boucle dans le corps (il s’agit d’une optimisation simple et le code produit est plus rapide que d’utiliser un appel de fin)

  • Si vous utilisez un appel récursif dans une position plus complexe (lorsque vous utilisez le style de passe de continuation où la fonction est passée en argument), le compilateur génère une instruction de fin d’appel qui indique au JIT qu’il doit utiliser un appel de fin.

Comme exemple du deuxième cas, comstackz la fonction F # simple suivante (F # ne le fait pas en mode Debug pour simplifier le débogage, vous pouvez donc avoir besoin du mode Release ou append --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 style de passage continu, vous avez une longue séquence d’appels, donc l’optimisation est cruciale (vous ne pouvez simplement pas utiliser ce style sans avoir à gérer les appels de fin). Le code IL génère 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::Invoke(!0) IL_000b: ret 

La situation avec l’optimisation des appels de queue dans .Net est assez compliquée. Pour autant que je sache, c’est comme ça:

  • Le compilateur C # n’émettra jamais la tail. opcode et il ne fera jamais l’optimisation de l’appel de queue par lui-même.
  • Le compilateur F # émet parfois la tail. opcode et fait parfois la queue appel optimisation par lui-même en émettant IL qui n’est pas récursif.
  • Le CLR va honorer la tail. opcode s’il est présent et le CLR 64 bits fera parfois l’optimisation de l’appel de queue même lorsque l’opcode n’est pas présent.

Donc, dans votre cas, vous n’avez pas vu la tail. opcode dans l’IL généré par le compilateur C #, car il ne fait pas cela. Mais la méthode était optimisée pour les appels de fin, car le CLR le fait parfois même sans l’opcode.

Et dans le cas de F #, vous avez observé que le compilateur f # effectuait lui-même l’optimisation.

Comme toutes les optimisations effectuées en .NET (langages Roslyn), l’optimisation des appels de fin est un travail effectué par la gigue, et non par le compilateur. La philosophie est que mettre le travail sur la gigue est utile car tout langage en bénéficiera et le travail normalement difficile d’écriture et de débogage d’un optimiseur de code ne doit être effectué qu’une fois par architecture.

Vous devez regarder le code machine généré pour le voir en cours, Debug + Windows + Déassembly. En outre, vous devez le faire en consultant le code de version Release généré à l’aide de l’optimisation Tools + Options, Debugging, General et Suppress JIT.

Le code x64 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 

Notez l'instruction marquée, un saut au lieu d'un appel. C'est l'optimisation des appels de queue au travail. Une bizarrerie dans .NET est que la gigue x86 32 bits n'effectue pas cette optimisation. Simplement une tâche à faire à laquelle ils ne se rendront probablement jamais. Ce qui obligeait les auteurs du compilateur F # à ne pas ignorer le problème et à émettre des Opcodes.Tailcall. Vous trouverez d'autres optimisations effectuées par la gigue documentée dans cette réponse .