Ein einfacher Algorithmus für Probleme der globalen Datenflussanalyse

Ein einfacher, iterativer Bit-Propagation-Algorithmus zur Lösung von Problemen der globalen Datenflussanalyse wie "verfügbare Ausdrücke" und "lebende Variablen" wird vorgestellt und zeigt sich in Bezug auf die Geschwindigkeit als ziemlich vergleichbar mit dem entsprechenden Intervallanalyse-Algorithmus. Dieser Vergleich wird durch ein Ergebnis erleichtert, das zwei Parameter eines reduzierbaren Flussgraphen (rfg) in Beziehung setzt. Nämlich, wenn G ein rfg ist, d die größte Anzahl von Rückkanten ist, die in einem zyklenfreien Weg in G gefunden werden, und k die Länge der aus G abgeleiteten Intervalsequenz ist, dann gilt k d. (Intuitiv ist k die maximale Verschachtelungstiefe von Schleifen in einem Computerprogramm, während d ein Maß für die maximale Schleifenvernetzung ist.) Die Knotenreihenfolge, die vom einfachen Algorithmus verwendet wird, ist das Gegenteil der Reihenfolge, in der ein Knoten zuletzt besucht wird, während ein beliebigen Tiefensuche-Baum des Flussgraphen wächst. Darüber hinaus wird ein Dominator-Algorithmus für ein rfg vorgestellt, der O (Kanten) Bit-Vektor-Schritte benötigt.