Ein Kontrollfluss-Graph (CFG) in der Informatik ist eine Darstellung mit der Graph-Notation von allen Pfaden, die durch ein Programm während seiner Ausführung überquert werden könnten.

Übersicht

In einem Kontrollfluss-Graphen vertritt jeder Knoten im Graphen einen grundlegenden Block, d. h. ein lineares Stück des Codes ohne irgendwelche Sprünge oder Sprung-Ziele; springen Sie Ziele fangen einen Block an, und Sprünge beenden einen Block. Geleitete Ränder werden verwendet, um Sprünge im Kontrollfluss zu vertreten. Es, gibt in den meisten Präsentationen, zwei besonders benannten Blöcken: Der Zugang-Block, durch den Kontrolle in den Fluss-Graphen und den Ausgangsblock eintritt, durch den der ganze Kontrollfluss abreist.

Der CFG ist für viele Bearbeiter-Optimierungen und statische Analyse-Werkzeuge notwendig.

Beispiel

Denken Sie das folgende Bruchstück des Codes:

0: (A) t0 = read_num

1: (A) wenn t0 mod 2 == 0

2: (B) drucken t0 + "ist gleich."

3: (B) goto 5

4: (C) drucken t0 + "ist seltsam."

5: (D) beenden Programm

</pre>

Im obengenannten haben wir 4 grundlegende Blöcke: Von 0 bis 1, B von 2 bis 3, C an 4 und D an 5. Insbesondere in diesem Fall ist A der "Zugang-Block", D der "Ausgangsblock", und Linien 4 und 5 sind Sprung-Ziele. Ein Graph für dieses Bruchstück hat Ränder von bis B, zu C, B zu D und C zu D.

Reachability

Reachability ist ein anderes in der Optimierung nützliches Graph-Eigentum.

Wenn ein Block/Subgraph vom Subgraphen nicht verbunden wird, der den Zugang-Block enthält, ist dieser Block während jeder Ausführung unerreichbar, und ist so unerreichbarer Code; es kann sicher entfernt werden.

Wenn der Ausgangsblock vom Zugang-Block unerreichbar ist, zeigt er eine unendliche Schleife an. Nicht alle unendlichen Schleifen sind natürlich feststellbar; sieh Stockendes Problem.

Toter Code und einige unendliche Schleifen sind möglich, selbst wenn der Programmierer diesen Weg nicht ausführlich codiert hat: Optimierungen wie unveränderliche Fortpflanzung und unveränderliche Falte, die vom einfädelnden Sprung gefolgt ist, konnten vielfache grundlegende Blöcke in einen, Ursache-Ränder zusammenbrechen, die von einem CFG zu entfernen sind, usw. so vielleicht Teile des Graphen trennend.

Überlegenheitsbeziehung

Eine Block-M beherrscht einen Block N, wenn jeder Pfad vom Zugang, der Block N erreicht, Block M durchführen muss. Der Zugang-Block beherrscht alle Blöcke.

In der Rückwartsrichtung, blockieren Sie M postbeherrscht Block N, wenn jeder Pfad von N bis den Ausgang Block M durchführen muss. Der Ausgangsblock postbeherrscht alle Blöcke.

Es wird gesagt, dass ein Block M beherrscht sofort Block N, wenn M N beherrscht, und es keinen vorläufigen solchen Block P gibt, dass M P beherrscht und P N beherrscht. Mit anderen Worten ist M der letzte dominator auf allen Pfaden vom Zugang bis N. Jeder Block hat einen einzigartigen unmittelbaren dominator.

Ähnlich gibt es einen Begriff von unmittelbarem postdominator: Analog unmittelbarem dominator.

Der dominator Baum ist eine Hilfsdatenstruktur, die die dominator Beziehungen zeichnet. Es gibt einen Kreisbogen vom Block M zum Block N, wenn M ein unmittelbarer dominator von N ist. Dieser Graph ist ein Baum, da jeder Block einen einzigartigen unmittelbaren dominator hat. Dieser Baum wird am Zugang-Block eingewurzelt. Kann effizient mit dem Algorithmus von Lengauer-Tarjan berechnet werden.

Ein postdominator Baum ist dem dominator Baum analog. Dieser Baum wird am Ausgangsblock eingewurzelt.

Spezielle Ränder

Aus praktischen Gründen ist es notwendig, einige künstliche Arten von Rändern einzuführen oder verschieden einige Arten von Rändern zu bearbeiten.

Ein Zurückrand ist ein Rand, der zu einem Block hinweist, der bereits während einer Tiefe das erste (DFS) Traversal des Graphen entsprochen worden ist. Zurückränder sind für Schleifen typisch.

Ein kritischer Rand ist ein Rand, der weder der einzige Rand ist, seinen Quellblock, noch der einzige Rand verlassend, der in seinen Bestimmungsort-Block eingeht. Diese Ränder müssen gespalten werden: Ein neuer Block muss in der Mitte des Randes geschaffen werden, um Berechnung am Rand einzufügen, ohne irgendwelche anderen Ränder zu betreffen.

Ein anomaler Rand ist ein Rand, dessen Bestimmungsort unbekannt ist. Ausnahme-Berühren-Konstruktionen können sie erzeugen. Diese Ränder neigen dazu, Optimierung zu hemmen.

Ein unmöglicher Rand (auch bekannt als ein unechter Rand) sind ein Rand, der zum Graphen hinzugefügt worden ist, um allein das Eigentum zu bewahren, dass der Ausgangsblock alle Blöcke postbeherrscht. Es kann nicht jemals überquert werden.

Schleife-Management

Ein Schleife-Kopfball (hat manchmal den Zugang-Punkt der Schleife genannt), ist ein dominator, der das Ziel eines Schleife-Formens zurück Rand ist. Der Schleife-Kopfball beherrscht alle Blöcke im Schleife-Körper.

Nehmen Sie Block an M ist ein dominator mit mehreren eingehenden Rändern, einige von ihnen, zurück Ränder seiend (so ist M ein Schleife-Kopfball). Es ist für mehrere Optimierungspässe vorteilhaft, M in zwei Blöcke M und M zu zerbrechen. Der Inhalt der M und Zurückränder wird zur M bewegt, der Rest der Ränder werden bewegt, um in die M hinzuweisen, und ein neuer Rand von der M bis M wird eingefügt (so dass M der unmittelbare dominator von M ist). Am Anfang würde M leer sein, aber Pässe wie Codebewegung der Schleife-invariant konnten es bevölkern. M wird den Schleife-Vorkopfball genannt, und M würde der Schleife-Kopfball sein.

Siehe auch

• Flussschema
• Kontrollfluss-Analyse
• Kontrollflussschema
• Programm-Abhängigkeitsgraph

Zeichen

Links

• Die Maschinen-SUIF Kontrollfluss-Graph-Bibliothek
• GNU-Bearbeiter-Sammlung Internals
• Papier "Infrastruktur für das Profil Gesteuerte Optimierungen im GCC Bearbeiter" durch Zdeněk Dvořák und al.

Beispiele

• http://www.aisee.com/graph_of_the_month/cfg.htm
• http://www.absint.com/aicall/gallery.htm
• http://www.icd.de/es/icd-c/example.html
• http://compilers.cs.ucla.edu/avrora/cfg.html