2016-02-14 13 views
13

Uno dei miei progetti laterali è un decompiler che trasforma il codice nativo in IR LMVM, lo semplifica e genera pseudo-C. Una fase essenziale del processo del programma è pattern-independent control flow structuring, che trova le regioni in un programma e le trasforma in istruzioni di flusso di controllo strutturate (ad esempio, non gotos).Come posso costruire l'albero post-dominatore di una funzione con un ciclo infinito?

Ho dovuto distribuire il mio codice per trovare le regioni perché le regioni di LLVM non sembrano esattamente come la carta si aspetta. Tuttavia, trovare le regioni richiede di avere un albero post-dominatore, e si scopre che l'algoritmo di compilazione degli alberi post-dominio di LLVM non può farne uno per le funzioni che non hanno un blocco finale, come le funzioni che "finiscono" con un ciclo infinito.

Questo sembra essere perché l'algoritmo di costruzione degli alberi ha bisogno di un punto di partenza. Normalmente, il punto di partenza è il blocco di ritorno della funzione, poiché post-domina ogni altro blocco; ma non c'è nessuna funzione che giri in un ciclo infinito, dal momento che non hanno alcun terminatore return o unreachable. (A questo punto, potrebbe valere la pena notare che il codice regionale di LLVM si basa anche su un albero post-dominatore ed è anche inutile per funzioni per cui non può essere costruito.)

Mi sembra che anche se questo l'algoritmo fallisce, il fatto che una funzione non ritorni non significa che non puoi creare un albero post-dominatore per esso. Infatti, se quel loop infinito ha un singolo back-edge (che è qualcosa che posso assicurare), il nodo con quel back edge necessariamente post-domina ogni altro nodo nel grafico, quindi dovrebbe essere possibile fare un albero post-dominatore.

Se potessi trovare quel nodo, potrei probabilmente fornirlo all'infrastruttura post-dom di LLVM e ricavarne un albero post-dominatore ragionevole. Sfortunatamente, non sono molto fantasioso e l'unico modo semplice in cui posso pensare di identificare quel nodo cruciale è che "è quello che post-domina tutto", che certamente non mi aiuterà a fare il boot di un albero post-dominatore.

Trovare i bordi posteriori non è particolarmente difficile. Come dice Doug Currie, puoi farlo con un semplice DFS e, in effetti, un'altra parte del mio progetto does exactly that. Tuttavia, nel caso di una funzione con un ciclo infinito e cicli di terminazione annidati, non so come direi il bordo posteriore interno dal bordo posteriore esterno senza informazioni sulla dominazione. (Se può aiutare, in questa fase del processo, ogni loop è garantito per avere un singolo nodo di entrata e al massimo un nodo di uscita.)

Quindi, come posso costruire l'albero post-dominatore di una funzione che non non ci sono blocchi base di ritorno?

1. Il mio compilatore e lo sfondo della teoria dei grafi sono interamente autodidatti. Questo potrebbe non essere accurato.

+0

Come trucco, per fare in modo che l'analisi abbia esito positivo, potresti forse inserire una finta condizione finale nel ciclo, che in realtà non diventa mai vera, ad es. in pseudo-codice: 'if (5 == 7) break;'? –

+0

@ 500-InternalServerError, ho ancora bisogno di scoprire dove metterlo esattamente, e che sarebbe al nodo con il bordo posteriore, che non so come trovare. – zneak

+0

Puoi trovare i bordi posteriori con DFS; per esempio, http://www.cs.yale.edu/homes/aspnes/pinewiki/DepthFirstSearch.html –

risposta

6

in senso stretto, quando c'è un ciclo infinito (non solo un loop senza limiti - uno strettamente infinita senza uscita), non v'è alcun post-Dominator, come per ogni nodo del ciclo, il nodo successivo il ciclo verrà eseguito dopo di esso, quindi non vi è alcun nodo "ultimo" al ciclo.

Un modo per gestirlo è quello di eseguire la normale ricerca post-dominio, tranne che dopo aver eseguito l'attraversamento iniziale di profondità dall'uscita, si controllano i nodi non visitati. Se ce ne sono, l'uscita non è raggiungibile da loro (nessun percorso dai nodi all'uscita), quindi ne scegli uno a caso e aggiungilo come uscita psuedo (come se il nodo contenesse un ramo condizionale all'uscita, solo la condizione è sempre falsa) e ricomincia.Questo ti dà un albero post-dominatore, ma non necessariamente un unico (dato che potresti scegliere diversi nodi a caso per aggiungere il ramo di uscita), ma generalmente non importa.

+0

Questo è in realtà quello che stavo cercando di ottenere con il mio commento, anche se non ero in grado di esprimere le mie parole. –

+0

Funziona anche quando non tutti i nodi irraggiungibili fanno parte di un ciclo infinito? – zneak

+0

Per definizione, tutti i nodi non raggiungibili devono essere parte di un ciclo infinito, poiché ogni nodo deve avere almeno un successore (se solo se stesso). –

Problemi correlati