Cos'è un nodo del dominatore e un albero dominante?

Question

Ho provato a leggere il wikipedia su dominator (teoria grafico) , che dà La seguente definizione di un nodo Dominator:

.

Un nodo D domina un nodo n se ogni percorso dal nodo di ingresso a n deve passare attraverso d.

Devo capire il concetto di un nodo del dominatore ma non ho bisogno di andare in profondità nei grafici, quindi sto cercando di dare un senso a queste definizioni. Sto cercando di guardare nelle immagini sull'articolo:

Questo è un grafico:

Questo dovrebbe essere un albero di dominatore per il grafico sopra:

Basato sulla definizione sopra, penso

Il nodo 2 domina il nodo 3 perché ogni percorso da 3 deve passare attraverso 2. Perché? Per andare da 3 a se stesso, devo passare a 2. Ecco perché 2 va a 3 nel Dominator Tree.

Sto pensando giusto?

Posso sapere anche perché questo è utile nei compilatori?

Answer 1

La ragione per cui fai non è esattamente giusto; La definizione di un nodo Dominator funziona da un nodo di partenza ( $ 1 $ Nell'esempio). L'unico modo per raggiungere $ 3 $ da $ 1 $ è per passare attraverso $ 2 $ Poiché è il nodo del successori di $ 1 $ nel grafico indicato. Quindi $ 2 $ Dominates $ 3 $ . Per lo stesso motivo, i nodi $ 4 $ attraverso $ 6 $ sono anche dominati da $ 2 $ e ulteriormente, $ 2 $ è il dominatore immediato di questi nodi (come $ 1 $ Dominate $ 2 $ ) E questi nodi non sono dominati da altri nodi di $ 1 $ e $ 2 $ :

.
• $ 3, 4 $ e $ 6 $ può essere immediatamente raggiunto da $ 1 $ tramite $ 2 $ .
• $ 5 $ può essere raggiunto da $ 2 $ tramite $ 3 $ o $ 4 $ e quindi gli unici nodi comuni in questi percorsi a $ 5 $ sono $ 1 $ e $ 2 $ .

Per quanto riguarda l'applicazione di questi concetti ai compilatori, considerare un grafico di flusso di controllo a livello di blocco (o CFG per Brevity) di un programma. Se alcuni blocchi $ B $ domina un blocco $ B '$ nel cfg, quindi $ B $ Deve essere stato eseguito dal momento in cui il programma raggiunge $ B '$ . Questa conoscenza può essere utilizzata per rimuovere i pezzi di codice ridondanti: Considera il programma

a = (something)
b = True

if a == True:
   b = True
else:
   b = False
   

.

Qui, il blocco composto dalle prime due righe domina il blocco IF e il blocco di else. Quindi sappiamo che quando saliamo al blocco IF dove avremmo impostato B per true, è già impostato su TRUE dal blocco del pugno e quindi il compilatore potrebbe ottimizzare il codice eliminando l'assegnazione nel blocco IF.

È inoltre possibile rilevare i loop nel codice analizzando se il CFG ha bordi del modulo $ B '\ a B $ dove di nuovo $ B $ Dominates $ B '$ . Tale percorso indica l'esistenza di un loop dove $ B $ rappresenterebbe quindi l'intestazione del ciclo mentre $ B '$ è (l'ultima) parte del corpo del loop.