Comment implémenter des appels d'attente dans une machine virtuelle personnalisée

Question

Comment puis-je implémenter des appels d'attente dans une machine virtuelle personnalisée?

Je sais que j'ai besoin de faire sauter la pile locale de la fonction d'origine, puis ses arguments, puis pousser sur les nouveaux arguments. Mais, si je saute la pile locale de la fonction, comment suis-je censé pousser les nouveaux arguments? Ils viennent d'être sortis de la pile.

Answer 1

Je suppose que nous discutons ici d'une machine virtuelle traditionnelle «basée sur une pile».

Vous pop au large de la fonction en cours de pile locale préservant 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 que tous les arguments et la pile locale de la fonction sont nettoyés, vous devez appuyer sur les arguments de l'appel récursif. Par exemple, supposons que la fonction que vous l'optimisation 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 

le CALL_FUN2 signifie « 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 le pop normal que juste défausse haut n entrées de la pile, mais POP_KEEP n est une variante qui les garde "quelque part" (par exemple dans une pile auxiliaire non directement accessible à l'application mais uniquement aux propres machines de la machine virtuelle - stockage avec un tel caractère parfois appelé "un registre" lors de la discussion sur l'implémentation de VM) et un PUSH_KEPT n correspondant qui vide les "registres" dans la pile normale de la machine virtuelle.

Answer 2

Je pense que vous regardez cela dans le mauvais sens. Au lieu de retirer les vieilles variables de la pile et de pousser les nouvelles, il suffit de réaffecter celles qui sont déjà là (attention). C'est à peu près la même optimisation qui se produirait si vous réécriviez le code comme étant 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 pousser quoi que ce soit sur la pile, réassigner simplement. De toute évidence, cela peut être encore optimisé, en mettant la condition de sortie en second lieu, 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 

regardant de nouveau, cette « assemblée » reflète mieux ce C++, qui a clairement évité la récursion appelle

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