18. Registri salvati

La parte finale dell’analisi dello stack frame prevede il rilevamento dei registri salvati.

I registri salvati sono quei registri che sono obbligati da una certa convenzione di chiamata a essere preservati attraverso le chiamate di funzione. Questo concetto è molto importante per un compilatore (e quindi per un decompilatore) per poter allocare variabili ai registri ed evitare di dover salvare in memoria quei registri ogni volta che c’è una chiamata ad una funzione che potrebbe essere stata generata da un altro compilatore.

Vale la pena notare che diverse convenzioni di chiamata definiscono diversi insiemi di registri da conservare tra le chiamate di funzione. Questo perché finché entrambi i lati, il lato chiamante e il lato della funzione chiamata, concordano su quali informazioni devono essere conservate, il compilatore può generare il codice più efficiente per quella particolare chiamata.

Nel contesto di un decompilatore, dobbiamo rilevare quali registri sono conservati da ciascuna funzione, in modo da poter calcolare esattamente le informazioni di attività per ciascun registro.

Il codice di base per salvare i registri viene generato dai compilatori come parte del prologo della funzione dopo aver impostato lo stack frame. Corrispondentemente, ogni registro viene ripristinato nell’epilogo della funzione, prima della deallocazione dello stack frame. Per esempio:

Framed functions              Frame-less functions

   PUSH FP
   FP = SP
   SP -= #local_size            SP -= #local_size
   PUSH R1                      PUSH R1
   PUSH R2                      PUSH R2
   ...                          ...
   POP  R2                      POP R2
   POP  R1                      POP R1
   SP = FP                      SP += #local_size
   RET                          RET

In che modo le informazioni sui registri salvate influiscono sulla compressione delle espressioni? Considera la seguente sequenza di codice:

   R1 = 1
   R2 = 2            R2 = 2
   PUSH R1
   CALL FUNC         FUNC(R1)           FUNC(1)
   ADD SP, #4
   M1400 = R2        M1400 = R2         M1400 = 2?

Come possiamo essere sicuri che il valore 2 sia ancora nel registro R2 dopo la chiamata alla funzione? Solo se sappiamo che FUNC() non utilizza né modifica R2, possiamo comprimere R2 = 2 e M1400 = R2 in un’unica istruzione. Se FUNC() utilizza R2 come uno dei suoi valori di input, non possiamo rimuovere l’assegnazione R2 = 2. Se FUNC() modifica R2, è possibile che R2 sia in realtà un output della funzione e potremmo effettivamente dover tradurre la chiamata in M1400 = FUNC(R1).

La compressione di R2 = 2 e M1400 = R2 può essere eseguita utilizzando le informazioni sull’attività, ma solo se le informazioni sull’attività sono accurate per FUNC(). Ciò significa che dobbiamo tradurre FUNC() prima di tradurre la funzione che chiama FUNC(). Come decidiamo l’ordine di analisi delle funzioni? Possiamo utilizzare una tecnica collaudata, ovvero calcolare il depth-first order (DFO) per ciascuna funzione e quindi visitare prima le funzioni con l’ID DFO più alto.

Il seguente algoritmo calcola l’ID DFO per ogni funzione:

   id = procList.length
   computeDFO(entryFunction)
   qsort(procList, by_DFO_id)
   for each function in procList in reverse order
      computeInputOutputRegisters(function)

computeDFO(function){
    int succ;

    function.visited = true
    for each destFunc in function.callsTo
        if destFunc.visited
            continue
        computeDFO(destFunc)
    }
    function.dfoID = id
    --id
} 

Dopo questo algoritmo, ogni funzione avrà un ID DFO, con funzioni foglia (funzioni che non chiamano nessun’altra funzione) con ID più alti, mentre le funzioni più vicine al punto di ingresso avranno ID più bassi.

Possiamo quindi analizzare le funzioni con l’id DFO più alto. Quelle saranno inizialmente funzioni foglia. Poiché non avranno alcuna chiamata di funzione, possiamo calcolare con precisione l’insieme di registri di input, registri di output e registri salvati. Mentre continuiamo ad analizzare le funzioni con ID DFO inferiori, possiamo essere sicuri che tutte le funzioni che chiamano saranno già state analizzate, quindi possiamo essere sicuri di quali registri sono attivi in ​​un dato punto del programma.