13. Analisi del flusso dei dati

Finora abbiamo considerato solo i percorsi di esecuzione del codice senza considerare ciò che fa ciascuna istruzione aritmetica. Ci siamo preoccupati solo dei rami e delle istruzioni di confronto. Tuttavia abbiamo visto nella pagina precedente che non possiamo comprimere più istruzioni if senza comprimere almeno alcune delle istruzioni tra le istruzioni di branch.

Poiché i registri non sono direttamente accessibili da un programma C, una buona linea guida è provare a rimuovere tutti i riferimenti ai registri dalle istruzioni. Ciò che resta dovrebbe essere abbastanza vicino al file sorgente originale.

Ma quando è sicuro comprimere più istruzioni senza modificare il comportamento del programma convertito?

La risposta è: quando siamo sicuri che non ci sia perdita di dati quando rimuoviamo un’istruzione.

Considera la seguente sequenza di istruzioni:

    MOV R1, var_1 R1 = var_1;
    CMP R1,#10 if(R1 == 10 ||
L0: JEQ L1
    CMP R1,#20 R1 == 20) {
    JNE L2
L1: ....
L2: }

In questa sequenza non possiamo semplicemente comprimere le prime 2 istruzioni in un’unica “CMP var_1, #10”, perché il valore in R1 viene utilizzato nuovamente nella seconda istruzione CMP. In questo caso è lecito ritenere che anche la seconda istruzione CMP controlli il valore di “var_1”, quindi è lecito convertirlo in “CMP var_1, #20”. Ciò porterebbe alla dichiarazione finale:

if(var_1 == 10 || var_1 == 20) {
} 

Se il valore del registro R1 viene utilizzato in corrispondenza o dopo l’istruzione L0, si dice che il registro è “vivo” in L0. Se invece il registro viene ricaricato con un altro valore in una successiva istruzione, si dice che il registro è “morto” in L0.

Pertanto, la “vivacità” di un registro è un attributo di ogni istruzione.

È facile calcolare la vivacità di un registro in un blocco base. È più difficile calcolare la durata di un registro attraverso i blocchi di base. Ad esempio nel seguente codice:

    MOV R2, var_2
    ...
    JEQ L3
    ...
L4:
    MOV R1, var_1              
    CMP R1,#10 if(var_1 == 10 ||
    JEQ L1
    CMP R2,#20 var_2 == 20) { // ?
    JNE L2
L1: ....
L2: }

Come sappiamo che R2 ha ancora il valore di var_2 nell’istruzione CMP R2,#20?

Potrebbe esserci un percorso di esecuzione da un’altra assegnazione R2 che entra nel blocco L4, nel qual caso non possiamo sapere quale sia il valore di R2. Oppure, può esserci un altro uso di R2 dopo l’istruzione di confronto.

Dobbiamo eseguire un’analisi di durata globale su tutti i blocchi di base della funzione, considerando come l’esecuzione scorre da un blocco all’altro e calcolando se ogni registro è “morto” o “vivo” a ogni istruzione.

Rappresentazione dei dati

Le informazioni sull’attività sono in genere rappresentate come un insieme di bit per ciascuna istruzione. Ogni bit nel set rappresenta una delle variabili che vogliamo tracciare. Nonostante l’importanza dell’analisi del flusso di dati, i libri sull’implementazione del compilatore utilizzano termini diversi per identificare le informazioni descritte nei liveness set. Alcuni calcolano gli insiemi di variabili eliminate e utilizzate; altri calcolano gli insiemi di variabili vive e morte, sebbene questa definizione non dica se le variabili sono vive quando entrano nell’istruzione o quando escono dall’istruzione.

Penso che un’identificazione più chiara delle informazioni di liveness implichi il calcolo dei set “livein” e “liveout”, ovvero l’insieme di variabili che sono vive prima di eseguire l’istruzione e quelle che sono vive dopo l’esecuzione dell’istruzione.

Dato che abbiamo a che fare con le istruzioni di assemblaggio e vogliamo tenere traccia delle informazioni di liveness di ogni registro, ha senso avere un set di bit in cui ogni bit rappresenta un registro della CPU. Ecco un esempio:

Uso informatico e def

Puoi vedere che i set LiveIn e LiveOut dipendono dalle informazioni fornite da 2 funzioni di ciascuna istruzione. La funzione Def(i) restituisce l’insieme dei registri che sono “definiti” (scritti) dall’istruzione ‘i’; la funzione Use(i) restituisce l’insieme dei registri “utilizzati” (letti) dall’istruzione ‘i’. Def(i) e Use(i) dipendono solo da ciascuna istruzione. Ecco del codice che calcola Def(i) e Use(i):

Instruction stream    LiveIn(i) Set   LiveOut(i) Set    Def(i) Set   Use(i) Set
R1 = var_2                            R1                R1
R2 = R1 + 1           R1              R1?  R2           R2           R1
var_2 = R2            R1? R2          R1?  R2?                       R2

Questo codice presuppone che ogni operando possa essere solo una locazione di memoria, una costante o un registro. Se un operando può essere qualcosa di più complesso, come una modalità di indirizzamento indicizzato, allora dobbiamo considerare ogni singolo pezzo a cui fa riferimento la modalità di indirizzamento e impostare tutti i bit rilevanti nei set Def(i) e Use(i).

Un algoritmo più robusto, che utilizza un albero per rappresentare sia gli operandi di origine che quelli di destinazione, è il seguente:

ComputeUseDefs(){
    for each instruction i in each block in CFG
        i.defs = 0
        i.use = 0
        if i.op == Assign && isRegister(i.result)
            i.defs = BitSet(i.result.regnum)
        else
            i.use |= getUses(i.result)
        i.use |= getUses(i.op1)
        i.use |= getUses(i.op2)
}

getUses(Node n){
    if n == null
       return 0
    use  = getUses(n.op1)
    use |= getUses(n.op2)
    if n.op == Register
       use |= BitSet(n.regnum)
    return use
}

Vedremo nella sezione avanzata che non è sempre possibile calcolare gli insiemi Defs(i) e Use(i), in particolare per le istruzioni di chiamata quando la destinazione della chiamata non è nota.

Analisi della vita globale

Armati della conoscenza di quale registro viene utilizzato e definito da ciascuna istruzione, ora possiamo calcolare le informazioni sulla vivacità.

L’algoritmo per calcolare LiveIn(i) e LiveOut(i) esegue diversi passaggi attraverso il grafo del flusso di controllo, calcolando e propagando le informazioni di liveness a tutti gli altri blocchi fino a quando non c’è qualche voce che viene modificata. Quando gli insiemi calcolati non vengono più modificati, significa che abbiamo calcolato tutte le informazioni necessarie e possiamo uscire dall’algoritmo.

L’algoritmo funziona in 3 fasi. La prima fase calcola le informazioni sull’attività per ogni blocco di base senza considerare come quel blocco di base è correlato agli altri blocchi di base:

for each b in CFG
      b.use = 0
      b.defs = 0
      b.input = 0
      b.output = 0
      i = b.lastInstr
      do
          i.liveout = i.use
          i.dead = i.defs & ~i.liveout

          b.use = i.liveout | (b.use & ~i.dead)
          b.defs = i.dead | (b.defs & ~i.liveout)

          i = i.prevInstr
      while i != null
   end for each b

La seconda fase lavora sulle informazioni in ciascun blocco propagando le informazioni di liveness da ciascun blocco a tutti gli altri blocchi nel CFG:

do
        changed = false
        for each block in CFG
            out = b.defs
            for each succ in block.succs
                out |= succ.input

            in = block.use | (out & ~block.defs)
            if in != block.input || out != block.output
                changed = true
                block.input = in
                block.output = out
        end for each block
    while changed

La terza fase aggiunge le informazioni raccolte dagli altri blocchi a ciascuna istruzione presente in ciascun blocco:

for each block in CFG
        live = 0
        for each succ in block.succs
            live |= succ.input

        i = block.lastInstr
        do
           newlive = i.liveout | (live & ~i.dead)
           i.liveout = live
           live = newlive
           i = i.prevInstr
        while i != null
    end for each block

Dopo l’algoritmo possiamo utilizzare le informazioni LiveIn(i) e LiveOut(i) nel nostro tentativo di eliminare i riferimenti di registro e di comprimere più istruzioni in espressioni complesse.