10. Grafico del flusso di controllo

Ora che abbiamo una serie di blocchi di base con cui lavorare, è molto più facile implementare qualche analisi in più e scoprire di più sulla struttura del programma.

Poiché abbiamo limitato la costruzione di blocchi di base a una singola procedura, ci occuperemo principalmente di recupero di istruzioni a livello di procedura. L’analisi dell’interazione tra diverse procedure sarà trattata nella sezione avanzata.

Potresti aver notato che nell’algoritmo di costruzione del blocco di base abbiamo salvato il blocco di ingresso nella struttura dati della procedura. Ecco il pezzo di codice pertinente:

Perché non siamo semplicemente entrati nel ciclo while e abbiamo usato solo il primo blocco nel set blockList?

Questo perché l’insieme blockList verrà ordinato in base all’indirizzo iniziale di ciascun blocco e, sebbene la maggior parte dei punti di ingresso delle procedure sarà l’indirizzo più basso della procedura, è possibile che il punto di ingresso sia effettivamente generato dal compilatore nel mezzo o alla fine di la procedura (ad esempio in presenza di ottimizzazioni call-tail), quindi dopo l’ordinamento, la prima entry in blockList non sarebbe più il nostro entry block.

Si noti che mentre esiste un solo blocco di ingresso per ogni procedura (non consideriamo i linguaggi di programmazione con più punti di ingresso, come Fortran), possono esserci più blocchi che escono dalla procedura, poiché possono esserci molte sequenze di istruzioni che terminano con un’istruzione RET.

Sapere che entriamo sempre nella procedura da un blocco specifico ci dà un punto da cui iniziare a ispezionare il codice. Dal blocco di ingresso, possiamo visitare tutti gli altri blocchi seguendo l’ elenco dei successi. Questa è chiamata analisi in avanti , perché segue il flusso di esecuzione.

Alcune analisi richiedono di visitare i blocchi nella direzione opposta, cioè dal punto di uscita al punto di ingresso. Ma come possiamo farlo quando ci sono più blocchi di uscita? La soluzione è creare un blocco falso e rendere tutti i blocchi che terminano con un’istruzione di ritorno i predecessori del blocco di uscita falsa (e automaticamente il blocco di uscita falsa diventerà il loro unico successore).

Con questo trucco possiamo implementare gli algoritmi che richiedono l’analisi all’indietro , cioè che guardano il codice nella direzione opposta all’esecuzione del codice.

Se la procedura ha alcuni cicli, ci sarà un collegamento tra il blocco in fondo al ciclo e il blocco all’inizio del ciclo. Quando visitiamo i diversi blocchi dobbiamo assicurarci di non analizzare all’infinito i blocchi nel ciclo più e più volte. Per fare ciò, aggiungiamo un campo visitato a ciascun blocco di base e controlliamo quel campo mentre visitiamo i blocchi.

Esistono molti ordini possibili in cui visitare ciascun blocco e alcuni algoritmi dipendono dall’ordine di visita. Ecco un esempio di un algoritmo di visita in avanti che visiterà ogni blocco il prima possibile (ecco perché si chiama algoritmo di “attraversamento in profondità”):

Possiamo aggiungere il codice per eseguire un algoritmo in uno dei due posti seguenti: prima di visitare i blocchi successori o dopo averli visitati. In C++ probabilmente implementeremmo un modello “visitatore” e forniremmo un puntatore a un oggetto che implementa un’analisi specifica come argomento per il visitatore.

Potresti aver notato dall’immagine sopra che possiamo riconoscere le sequenze “if-then-else” controllando se i predecessori e i successori di due blocchi sono gli stessi. Esistono diverse configurazioni simili di blocchi di base che possono essere utilizzate per convertire il codice pieno di goto in codice strutturato.

Tuttavia, alcune di queste strutture richiedono una gestione speciale: i loop.

Trovare Loop

Un grafico del flusso di controllo ci consente di trovare loop. L’algoritmo per identificare quale blocco appartiene a un ciclo dipende dalla conoscenza del blocco dominatore per ogni ciclo, quindi prima dobbiamo calcolare l’insieme dei dominatori per ogni blocco.

Biografia

Sono uno specialista in materia di sicurezza informatica, scrittore, contributore per il progetto Monero, una criptovaluta che è focalizzata nel proteggere le informazioni sulle transazioni. Il libro che ho pubblicato Mastering Monero è diventato una delle migliori risorse per padroneggiare Monero. Più informazioni su di me

Seguimi su Twitter o scrivimi una e-mail. Le donazioni sono molto apprezzate, mi permettono di continuare a lavorare e a scrivere.

Mastering Monero Book