Comment mettre en œuvre des appels de queue dans une machine virtuelle personnalisée

Question

Comment puis-je mettre en œuvre des appels de queue dans une machine virtuelle personnalisée?

Je sais que je dois faire sauter la pile locale de la fonction d'origine, il est des arguments, puis pousser sur les nouveaux arguments. Mais, si je pop hors pile locale de la fonction, comment suis-je censé pousser les nouveaux arguments? Ils viennent d'être extraites de la pile.

Answer 1

Je prends pour acquis que nous discutons d'une machine virtuelle traditionnelle « stack » ici.

Vous pop la pile locale de la fonction actuelle en conservant les parties encore pertinentes non-pile « registres » (où les « parties concernées » sont, clairement, l'argument de l'appel de la queue récursive à venir ), puis (une fois sont nettoyés) tous pile et arguments de la fonction locale vous appuyez sur les arguments de l'appel récursif. Par exemple, supposons que la fonction que vous optimisez est quelque chose comme:

def aux(n, tot):
  if n <= 1: return tot
  return aux(n-1, tot * n)

qui, sans optimisation pourrait produire byte-code symbolique comme:

AUX:   LOAD_VAR   N
       LOAD_CONST 1
       COMPARE
       JUMPIF_GT  LAB
       LOAD_VAR   TOT
       RETURN_VAL
LAB:   LOAD_VAR   N
       LOAD_CONST 1
       SUBTRACT
       LOAD_VAR   TOT
       LOAD_VAR   N
       MULTIPLY
       CALL_FUN2  AUX
       RETURN_VAL

les moyens de CALL_FUN2 « appeler une fonction avec deux arguments ». Avec l'optimisation, il pourrait devenir quelque temps comme:

   POP_KEEP     2
   POP_DISCARD  2
   PUSH_KEPT    2
   JUMP         AUX

Bien sûr, je fais mes bytecode symboliques comme je vais le long, mais j'espère que l'intention est claire: POP_DISCARD n est la pop normale qui vient d'annuler les entrées de n haut de la pile, mais POP_KEEP n est une variante qui les maintient « quelque part » (par exemple dans une pile auxiliaire ne sont pas directement accessibles à l'application mais seulement propres machines de la machine virtuelle - stockage avec caractère un tel est parfois appelé « un registre » lors de la discussion mise en œuvre VM) et un PUSH_KEPT n correspondant qui se jette les « registres "retour dans une pile normale de la machine virtuelle.

Answer 2

Je pense que vous regardez ce dans le mauvais sens. Au lieu de sauter les anciennes variables de la pile, puis en poussant les nouveaux, modifiez l'affectation ceux déjà là (attentivement). Ceci est à peu près la même optimisation qui se passerait-il si vous réécrit le code à l'algorithme itératif équivalent.

Pour ce code:

 int fact(int x, int total=1) {
     if (x == 1)
         return total;
     return fact(x-1, total*x);
 }

serait

 fact:
   jmpne x, 1, fact_cont  # if x!=1 jump to multiply
   retrn total            # return total
 fact_cont:               # update variables for "recursion
   mul total,x,total      # total=total*x
   sub x,1,x              # x=x-1
   jmp fact               #"recurse"

Il n'y a pas besoin de pop ou de quoi que ce soit poussée sur la pile, seulement Réattribuer.
De toute évidence, cela peut encore être optimisé, en mettant la condition de sortie seconde, ce qui nous permet de sauter un saut, ce qui entraîne moins d'opérations.

 fact_cont:               # update variables for "recursion
   mul total,x,total      # total=total*x
   sub x,1,x              # x=x-1
 fact:
   jmpne x, 1, fact_cont  # if x!=1 jump to multiply
   retrn total            # return total

Recherche de nouveau, cette « assemblée » reflète mieux cette C ++, qui a clairement évité les appels récursifs

int fact(int x, int total=1)
    for( ; x>1; --x)
        total*=x;
    return total;
}