Grafico del flusso di controllo - Control-flow graph

Alcuni esempi di CFG:
(a) un if-then-else
(b) un ciclo while
(c) un ciclo naturale con due uscite, ad esempio while con un if...break nel mezzo; non strutturato ma riducibile
(d) un CFG irriducibile: un ciclo con due punti di ingresso, ad esempio goto into a while o for loop
Un grafico del flusso di controllo utilizzato dal compilatore Rust per eseguire la generazione del codice.

In informatica , un grafico a flusso di controllo ( CFG ) è una rappresentazione , utilizzando la notazione grafica , di tutti i percorsi che potrebbero essere attraversati da un programma durante la sua esecuzione . Il grafico del flusso di controllo è stato scoperto da Frances E. Allen , che ha notato che Reese T. Prosser utilizzava in precedenza matrici di connettività booleane per l'analisi del flusso.

Il CFG è essenziale per molte ottimizzazioni del compilatore e strumenti di analisi statica .

Definizione

In un grafo di flusso di controllo ogni nodo nel grafo rappresenta un blocco di base , cioè un pezzo di codice in linea retta senza salti o obiettivi di salto ; i bersagli di salto iniziano un blocco e i salti terminano un blocco. I bordi orientati vengono utilizzati per rappresentare i salti nel flusso di controllo . Ci sono, nella maggior parte delle presentazioni, due blocchi appositamente designati: il blocco di ingresso , attraverso il quale il controllo entra nel grafico di flusso, e il blocco di uscita , attraverso il quale esce tutto il flusso di controllo.

A causa della sua procedura di costruzione, in un CFG, ogni arco A→B ha la proprietà che:

outdegree (A) > 1 o indegree (B) > 1 (o entrambi).

Il CFG può quindi essere ottenuto, almeno concettualmente, partendo dal grafo di flusso (completo) del programma – cioè il grafo in cui ogni nodo rappresenta una singola istruzione – ed eseguendo una contrazione degli archi per ogni arco che falsifica il predicato sopra, cioè contraendo ogni spigolo la cui sorgente ha un'unica uscita e la cui destinazione ha un'unica entrata. Questo algoritmo basato sulla contrazione non ha alcuna importanza pratica, tranne che come aiuto di visualizzazione per comprendere la costruzione CFG, perché il CFG può essere costruito in modo più efficiente direttamente dal programma scansionandolo per i blocchi di base .

Esempio

Considera il seguente frammento di codice: 

0: (A) t0 = read_num
1: (A) if t0 mod 2 == 0
2: (B)   print t0 + " is even."
3: (B)   goto 5
4: (C) print t0 + " is odd."
5: (D) end program

In quanto sopra abbiamo 4 blocchi base: A da 0 a 1, B da 2 a 3, C a 4 e D a 5. In particolare, in questo caso, A è il "blocco di entrata", D il "blocco di uscita " e le righe 4 e 5 sono bersagli di salto. Un grafo per questo frammento ha bordi da A a B, da A a C, da B a D e da C a D.

Raggiungibilità

Articolo principale: Raggiungibilità

La raggiungibilità è una proprietà del grafico utile nell'ottimizzazione.

Se un sottografo non è connesso dal sottografo contenente il blocco di ingresso, quel sottografo è irraggiungibile durante qualsiasi esecuzione, e quindi è irraggiungibile codice ; in condizioni normali può essere rimosso in sicurezza.

Se il blocco di uscita non è raggiungibile dal blocco di ingresso, potrebbe esistere un ciclo infinito . Non tutti i loop infiniti sono rilevabili, vedere Problema di interruzione . Lì può anche esistere un ordine di arresto.

Codice irraggiungibile e loop infiniti sono possibili anche se il programmatore non li codifica esplicitamente: ottimizzazioni come la propagazione costante e il ripiegamento costante seguiti da jump threading possono comprimere più blocchi di base in uno, causare la rimozione di bordi da un CFG, ecc., quindi possibilmente scollegare parti del grafico.

relazione di dominio

Articolo principale: Dominator (teoria dei grafi)

Un blocco M domina un blocco N se ogni percorso dall'ingresso che raggiunge il blocco N deve passare attraverso il blocco M. Il blocco di ingresso domina tutti i blocchi.

Nella direzione inversa, il blocco M postdomina il blocco N se ogni percorso da N all'uscita deve passare attraverso il blocco M. Il blocco di uscita postdomina tutti i blocchi.

Si dice che un blocco M domina immediatamente il blocco N se M domina N, e non c'è un blocco intermedio P tale che M domini P e P domini N. In altre parole, M è l'ultimo dominatore su tutti i percorsi dall'ingresso a N. Ogni blocco ha un unico dominatore immediato.

Allo stesso modo, esiste una nozione di immediato postdominatore , analogo a quello di immediato dominatore .

L' albero del dominatore è una struttura di dati ausiliaria che descrive le relazioni del dominatore. C'è un arco dal Blocco M al Blocco N se M è un dominatore immediato di N. Questo grafico è un albero, poiché ogni blocco ha un unico dominatore immediato. Questo albero è radicato nel blocco di ingresso. L'albero del dominatore può essere calcolato in modo efficiente utilizzando l'algoritmo di Lengauer-Tarjan .

Un albero postdominatore è analogo all'albero dominatore . Questo albero è radicato nel blocco di uscita.

Bordi speciali

Un bordo posteriore è un bordo che punta a un blocco che è già stato raggiunto durante un attraversamento del grafico in profondità ( DFS ). I bordi posteriori sono tipici dei loop.

Un arco critico è un arco che non è né l'unico arco che lascia il suo blocco di origine, né l'unico arco che entra nel suo blocco di destinazione. Questi spigoli devono essere divisi : si deve creare un nuovo blocco al centro dello spigolo, per poter inserire calcoli sullo spigolo senza intaccare gli altri spigoli.

Un bordo anomalo è un bordo la cui destinazione è sconosciuta. I costrutti di gestione delle eccezioni possono produrli. Questi bordi tendono a inibire l'ottimizzazione.

Un bordo impossibile (noto anche come un bordo falso ) è un bordo che è stato aggiunto al grafico esclusivamente per preservare la proprietà che il blocco di uscita postdomina tutti i blocchi. Non può mai essere attraversato.

Gestione del ciclo

Un'intestazione ciclo (talvolta chiamato il punto di ingresso del loop) è un dominatore che è la destinazione di un bordo posteriore formatore d'ansa. L'intestazione del ciclo domina tutti i blocchi nel corpo del ciclo. Un blocco può essere un'intestazione di loop per più di un loop. Un ciclo può avere più punti di ingresso, nel qual caso non ha "intestazione del ciclo".

Supponiamo che il blocco M sia un dominatore con diversi archi in entrata, alcuni dei quali sono archi posteriori (quindi M è un'intestazione di loop). È vantaggioso per diversi passaggi di ottimizzazione spezzare M in due blocchi M pre e M loop . Il contenuto di M e degli archi posteriori viene spostato in M loop , il resto degli archi viene spostato in modo che punti in M pre e viene inserito un nuovo arco da M pre a M loop (in modo che M pre sia il dominatore immediato di M loop ). All'inizio, M pre sarebbe vuoto, ma i passaggi come il movimento del codice invariante del ciclo potrebbero popolarlo. M pre è chiamato loop pre-header e M loop sarebbe l'intestazione del loop.

Riducibilità

Un CFG riducibile è uno con archi che possono essere partizionati in due insiemi disgiunti: archi avanti e archi posteriori, in modo tale che:

I linguaggi di programmazione strutturati sono spesso progettati in modo tale che tutti i CFG che producono siano riducibili e le istruzioni di programmazione strutturata comuni come IF, FOR, WHILE, BREAK e CONTINUE producono grafici riducibili. Per produrre grafici irriducibili, sono necessarie affermazioni come GOTO . Grafici irriducibili possono anche essere prodotti da alcune ottimizzazioni del compilatore.

Connessione ad anello

La connessione ad anello di un CFG è definita rispetto a un dato albero di ricerca in profondità (DFST) del CFG. Questo DFST dovrebbe essere radicato nel nodo iniziale e coprire ogni nodo del CFG.

Gli archi nel CFG che vanno da un nodo a uno dei suoi antenati DFST (incluso se stesso) sono chiamati archi posteriori.

La connessione ad anello è il maggior numero di back edge trovati in qualsiasi percorso senza ciclo del CFG. In un CFG riducibile, la connessione del ciclo è indipendente dal DFST scelto.

La connessione ad anello è stata utilizzata per ragionare sulla complessità temporale dell'analisi del flusso di dati .

Grafico del flusso di controllo interprocedurale

Mentre i grafici di flusso di controllo rappresentano il flusso di controllo di una singola procedura, i grafici di flusso di controllo interprocedurali rappresentano il flusso di controllo di interi programmi.


Guarda anche

Riferimenti

link esterno

Esempi