12. Creazione di dichiarazioni

Con le informazioni che abbiamo raccolto nei due passaggi precedenti (blocchi e cicli di base) ora abbiamo tutto ciò che serve per convertire le istruzioni del flusso di controllo in istruzioni di alto livello.

Questo processo è chiamato " strutturazione " in letteratura, perché ricreiamo la struttura originale del programma da una sequenza non strutturata di istruzioni. Sappiamo infatti che assembly non esprime i diversi rami nel codice sorgente, ma utilizza un approccio chiamata goto che consente alla cpu di saltare di eseguire. Durante l’assemblaggio infatti si perde questa visione ad alto livello dei diversi rami

Le istruzioni del flusso di controllo (rami, goto, etichette) vengono convertite nel seguente insieme di istruzioni C:

do { break; continue; } while;
while() { break; continue; }
for() { break; continue; }
if() { }       if() { } else { }
return
goto label

L’obiettivo finale è rimuovere tutti i goto e tutte le etichette.

Usiamo una tecnica collaudata chiamata " analisi dell’intervallo “. L’approccio generale consiste nel sostituire un numero di blocchi di base identificati per avere uno schema noto in un singolo blocco di base, ovvero in un’istruzione che ha solo un’entrata e una sola uscita. Lo faremo spostando le istruzioni dall’ambito contenitore (inizialmente c’è un solo ambito, l’intera procedura), nell’ambito/i dell’istruzione di controllo, creando di fatto un albero di blocchi di base.

Anelli di strutturazione

Iniziamo strutturando le istruzioni del ciclo. Il motivo è che vogliamo convertire le istruzioni goto in istruzioni break e continue prima di tentare di convertire rami condizionali in istruzioni if-else.

Avendo l’elenco dei loop in una procedura, per prima cosa identifichiamo il loop più nidificato (un loop che non ha altri loop al suo interno). Quindi sostituiamo il blocco di intestazione di ogni ciclo con un’istruzione do-while e spostiamo tutti i blocchi appartenenti al ciclo nell’istruzione do-while.

sort loopSet from innermost loop to outermost loop
for each loop in loopSet {
    doWhile = new Statement(DoWhile)
    doWhile->expr = new Expr(loop->blocks.last->lastCompareInstr)
    doWhile->blocks = loop->blocks
    doWhile->breakBlock = loop->blocks->postDominator
    doWhile->continueBlock = loop->blocks.last

    if doWhile->continueBlock->onlyStatement != If or
       doWhile->continueBlock->onlyStatement.destination != header
        doWhile->continueBlock = NULL

    loop->header->lastStatement = doWhile
    StructureBreakContinue(doWhile, doWhile->continueBlock, doWhile->breakBlock)
}

StructureBreakContinue(Statement stmt, Block contBlock, Block breakBlock)
{
    switch stmt.type {

    case Goto:
        if stmt.destination == contBlock
            stmt.type = Continue
        else if stmt.destination == breakBlock
            stmt.type = Break
        break

    case If:
        if stmt.elseBlocks
            for each statement in stmt.elseBlocks
                StructureBreakContinue(statement, contBlock, breakBlock)
       
        if stmt.trueBlocks
            for each statement in stmt.trueBlocks
                StructureBreakContinue(statement, contBlock, breakBlock)
    }
}

....                            ....
Lheader:
                                    do {
   ....                                 .... 
   if(expr)                             if(expr)
      goto Lcontinue                        continue;
   ....                                 ....
   if(expr)                             if(expr)
      goto Lbreak                           break;
   ...                                  ....
Lcontinue:
   if(expr)                         } while(expr);
      goto Lheader
Lbreak:
   ...

Come puoi vedere, 2 istruzioni goto e 2 etichette sono state rimosse. Nota come dobbiamo prima visitare i cicli più interni e come scendiamo solo le istruzioni if-else ma non le istruzioni do-while che abbiamo già scoperto. Questo perché un’istruzione break o continue si applica solo al ciclo più vicino, non a qualsiasi ciclo esterno che potrebbe essere attivo in quell’istruzione. Le istruzioni goto che saltano fuori dal ciclo più interno rimarranno come goto s nell’output finale.

Strutturazione ad anello avanzata

Ora che abbiamo identificato le istruzioni di base del ciclo, possiamo migliorare l’output cercando di eliminare ancora più goto ed etichette, e anche creando costrutti di ciclo più familiari. Dopotutto, il ciclo do-while non viene utilizzato così spesso come i più comuni cicli while e for. Questi possono ora essere creati controllando alcune condizioni e riscrivendo i cicli do-while che abbiamo appena generato.

Si noti che i punti break e continue sono rimasti gli stessi durante la conversione da do-while a while.

if(expr)                           while(expr) {
      goto Lbreak;
   do {
      ....                              ....
   } while(expr);                  }
Lbreak:
   ....                            ....

Ora possiamo andare oltre e convertire i cicli while in cicli for controllando se esiste un’inizializzazione e un’istruzione di incremento per la stessa variabile:

Si noti che i cicli for hanno un punto di continuazione diverso rispetto ai cicli do-while e while , pertanto la conversione iniziale delle istruzioni if-goto in if-continue sarebbe fallita. Ma ora che conosciamo il punto di continuazione del ciclo, possiamo chiamare StructureBreakContinue per le istruzioni all’interno del ciclo for , in modo che goto s al punto di continuazione vengano convertite in istruzioni continue.

Strutturazione degli if

Ora che abbiamo convertito le istruzioni del ciclo, possiamo provare a eliminare le restanti istruzioni goto. Questi dovrebbero far parte delle istruzioni if o if-else , quindi cercheremo di identificare le configurazioni di blocco di base che ci consentono di convertire le sequenze if-goto in sequenze if o if-else.

StructureIfElse(Block block){
   if block.succ.size != 2
       return false
   trueBlock = block.succ[0]
   falseBlock = block.succ[1]
   if trueBlock.succ.size != 1 or falseBlock.succ.size != 1
       return false
   if falseBlock.succ[0] != trueBlock.succ[0]
       return false

   ifStmt = new Statement(If)
   ifStmt.expr = NegateCondition(block.lastStmt)
   ifStmt.trueBlocks = trueBlock
   ifStmt.falseBlocks = falseBlock
   removeLastGoto(trueBlock, trueBlock.succ[0])
   removeLastGoto(falseBlock, falseBlock.succ[0])

   return true 
}

L’idea di base è la stessa che abbiamo usato nella strutturazione dei cicli: rimuoviamo tutti i blocchi che appartengono alla sequenza if-goto e li rendiamo figli dell’istruzione if-else contenente.

Nota che dobbiamo negare la condizione per entrare nel blocco true (in alternativa possiamo scambiare i blocchi true e false e mantenere la stessa condizione). Questo modello eliminerà 2 goto se possibilmente 2 etichette.

Una variante dell’algoritmo precedente non ha parti else. Questo è:

StructureIfs(Block block){

   if block.succ.size != 2
       return false
   trueBlock = block.succ[0]
   falseBlock = block.succ[1]
   if trueBlock.succ.size == 1 and trueBlock.succ[0] == falseBlock
       ifStmt = new Statement(If)
       ifStmt.expr = NegateCondition(block.lastStmt)
       ifStmt.trueBlocks = trueBlock
       ifStmt.falseBlocks = NULL
       removeLastGoto(trueBlock, falseBlock)
}

Questa variante considera il caso:

if(expr)                     if(!expr) {
      goto Lfalse
   ....                             ....
Lfalse:                      }

Strutturazione degli if avanzata

Non tutte le coppie if-goto verranno convertite dagli algoritmi di cui sopra. Considera il seguente schema:

La sequenza precedente è indicativa di una singola istruzione if con due condizioni. Che deve essere convertito in un’unica espressione concatenando le 2 condizioni con un operatore && :

Non c’è limite al numero di espressioni che possono essere compresse nella stessa istruzione if , quindi il riconoscimento del modello precedente dovrebbe essere ripetuto finché possiamo comprimere sempre più espressioni. Allo stesso modo, possiamo riconoscere sequenze di espressioni che saltano al vero blocco e concatenarle usando || operatore:

Limitazioni

Gli algoritmi e i modelli di cui sopra funzionano abbastanza bene per sequenze di istruzioni specifiche. Tuttavia il loro approccio abbastanza semplicistico fallisce miseramente in presenza anche del minimo disturbo nella sequenza delle istruzioni. In particolare la presenza di espressioni complesse impedisce il collasso delle sequenze if . Considera la seguente sequenza:

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

La sequenza si adatta perfettamente al modello if-or . Tuttavia, avere una sequenza di espressioni più complessa interromperà la mappatura:

    MOV R1, var_1 R1 = var_1; // blocco base 1
    CMP R1,#10 if(R1 == 10)
    JEQ L1 goto L1;
    MOV R1, var_2 R1 = var_2; // blocco base 2
    CMP R1,#20 if(R1 != 20)
    JNE L2 goto L2;
L1: .... L1: ...
L2: L2:

Questo perché il secondo blocco di base ha più istruzioni invece di una singola istruzione if . Poiché un’espressione non può contenere istruzioni, non è possibile comprimere le due istruzioni di confronto in un’unica espressione if .

Per poter ridurre il numero di proposizioni, aprendo così la porta a un’ulteriore strutturazione delle proposizioni, abbiamo bisogno di comprimere espressioni semplici in espressioni più complesse.

L’analisi del flusso di dati aiuta a ridurre le dichiarazioni di flusso non di controllo e apre la porta a una migliore strutturazione delle dichiarazioni.

Questo perché il secondo blocco di base ha più istruzioni invece di una singola istruzione if . Poiché un’espressione non può contenere istruzioni, non è possibile comprimere le due istruzioni di confronto in un’unica espressione if .

Per poter ridurre il numero di proposizioni, aprendo così la porta a un’ulteriore strutturazione delle proposizioni, abbiamo bisogno di comprimere espressioni semplici in espressioni più complesse.

L’analisi del flusso di dati aiuta a ridurre le dichiarazioni di flusso non di controllo e apre la porta a una migliore strutturazione delle dichiarazioni.