DE60000433T2

DE60000433T2 - Bestimmung der ziele einer dynamischen verzweigung

Info

Publication number: DE60000433T2
Application number: DE60000433T
Authority: DE
Inventors: N. Fender; T. Jennings; Lawrence Krablin; William Stratton
Original assignee: Unisys Corp
Current assignee: Unisys Corp
Priority date: 1999-01-29
Filing date: 2000-01-27
Publication date: 2003-04-30
Anticipated expiration: 2020-01-28
Also published as: EP1145105A2; DE60000433D1; JP2002536711A; US6662354B1; JP3685717B2; WO2000045255A3; EP1145105B1; US20080288915A1; WO2000045255A2

Description

BESTIMMUNG DER ZIELE EINER DYNAMISCHEN VERZWEIGUNG

Gebiet der Erfindung

Die vorliegende Erfindung betrifft die Bestimmung von Zielen einer dynamischen Verzweigung in kompiliertem Computer- Code (d. h. Maschinencode). Spezieller betrifft die vorliegende Erfindung die Bestimmung von jedem möglichen Ziel einer derartigen dynamischen Verzweigung, sodass der Steuerfluss eines solchen Computer-Codes bezüglich dieser dynamischen Verzweigung genau bestimmt werden kann.

Hintergrund der Erfindung

Unter bestimmten Umständen ist es nützlich, kompilierten Maschinencode von einem ersten Zustand, der einem ersten Anweisungssatz entspricht, in einen zweiten Zustand, der einem zweiten Anweisungssatz entspricht, zu übersetzen. Wie bekannt ist, ist eine solche Übersetzung gegenüber der Alternative vorzuziehen: Den Quellcode ausfindig zu machen, von dem der Maschinencode in dem ersten Codezustand abgeleitet wurde; und Schreiben und Austesten eines Compilers, um diesen ausfindig gemachten Quellcode direkt in den Maschinencode in dem zweiten Codezustand zu kompilieren.
Wie außerdem bekannt ist, wird eine solche Übersetzung von dem ersten Codezustand in den zweiten. Codezustand von einem geeigneten Wieder-Compiler oder Übersetzer auf einem geeigneten Prozessor mit angehängtem Speicher ausgeführt. Jedoch tritt ein Problem in der Situation auf, wo der Maschinencode in dem ersten Zustand Verzweigungs- oder Zieladressinformationen einschließt, wo derartige Verzweigungsadressinformationen für den Maschinencode in dem zweiten Zustand unterschiedlich wären, und wo explizite Adressinformationen von dem ursprünglichen Compiler fehlen. Das Problem verschlimmert sich, wenn sich Verzweigungsadressinformationen nicht auf eine völlig direkte Art und Weise übersetzen lassen.
Wie bei der Computerprogrammerstellung allgemein bekannt ist, ist eine dynamische Verzweigung eine Übergabe von einem Teil des Computer-Codes an einen von mehreren anderen Teilen des Computer-Codes, beruhend auf einer möglicherweise komplexen Berechnung einer Verzweigungs- oder Zieladresse. Ein Übersetzer muss alle möglichen potentiellen Ziele einer dynamischen Verzweigung in Abwesenheit expliziter Informationen von dem ursprünglichen Compiler genau bestimmen, sodass der Steuerfluss bezüglich einer solchen dynamischen Verzweigung genau übersetzt wird.
Um Code von einem Anweisungssatz in einen anderen zu übersetzen, ist es notwendig, das Ziel von jeder Verzweigung zu identifizieren. Das ist eine Voraussetzung für die Erzeugung eines vollständigen Steuerflussdiagramms (CFG) für den Code. Wie verstanden werden sollte, wird ein derartiges CFG für die vollständige semantische Analyse des Codes benötigt, und eingeschränkter, um die Anpassung der Verzweigungen oder ihrer Argumente an geänderte Adressen oder neue Adressformen in dem Zielanweisungssatz (d. h. dem zweiten Anweisungssatz) zu ermöglichen. Für eine statische Verzweigung (d. h. eine Verzweigung zu nur einem Ziel), egal ob Codesegment-basierend oder selbstbezüglich, ist das eine unkomplizierte Aufgabe, da die Adresse des Ziels in der Verzweigungsanweisung selbst codiert ist. Für eine dynamische Verzweigung jedoch wird die Aufgabe komplexer.
Dynamische Verzweigungen beruhen ganz oder teilweise auf Ergebnissen von Berechnungen, die vor der Verzweigung gemacht wurden, und stellen deshalb ein schwierigeres Problem für die Übersetzung dar. Eine dynamische Verzweigung impliziert selbstverständlich eher einen Satz von potentiellen Zieladressen als ein einzelnes Ziel. Es besteht folglich ein Bedarf an einem Übersetzer, der die Berechnungen bewertet, die die Verzweigung einleiten, um sich auf verlegte potentielle Ziele oder eine unterschiedliche Adressierstruktur in dem Zielanweisungssatz anzupassen.

Zusammenfassung der Erfindung

Die vorliegende Erfindung befriedigt die zuvor genannten Bedürfnisse, indem sie ein Verfahren, einen Übersetzer und ein Computer-lesbares Medium zum Übersetzen von kompilierten Programmiercode von einem ersten Codezustand in einen zweiten Codezustand bereitstellt. Der Programmiercode in dem ersten Codezustand hat eine Vielzahl von Basisblöcken, wobei jeder Basisblock einen Satz von Anweisungen besitzt. Mindestens ein Basisblock endet in einer dynamischen Verzweigung, wobei die dynamische Verzweigung eine Übergabe ist an ein Ziel von einem Satz von Zielen, beruhend auf einer Berechnung einer Zieladresse.
Die Vielzahl von Basisblöcken in dem ersten Codezustand des Programmiercodes werden identifiziert, ebenso wie Verbindungen zwischen den identifizierten Basisblöcken identifiziert werden. Ein Steuerflussdiagramm/Darstellung (CFG) des Programmiercodes wird dann beruhend auf den identifizierten Basisblöcken und identifizierten Verbindungen konstruiert, wobei das CFG von einer vorläufigen Form ist. Mindestens ein Basisblock, der in einer dynamischen Verzweigung endet, wird identifiziert, und alle identifizierten Basisblöcke, die zu der dynamischen Verzweigung führen, werden beruhend auf dem CFG so weit zurück untersucht, wie notwendig ist, um einen Satz von Zieladressen für die dynamische Verzweigung vollständig zu bestimmen.
Der Satz von Zieladressen definiert den Satz von Zielen von der dynamischen Verzweigung. Ein solcher Satz von Zielen wird geprüft, um eine Verzweigungstabelle zu identifizieren, und das CFG wird aktualisiert, um den Satz von Zielen und die identifizierte Verzweigungstabelle widerzuspiegeln. Der Programmiercode wird dann von dem ersten Codezustand in den zweiten Codezustand übersetzt, mindestens teilweise beruhend auf dem aktualisierten CFG.

Kurze Beschreibung der Zeichnungen

Die vorhergehende Zusammenfassung sowie die folgende ausführliche Beschreibung der bevorzugten Ausführungsformen der vorliegenden Erfindung werden besser verstanden werden, wenn sie in Verbindung mit den angehängten Zeichnungen gelesen werden. Zum Zwecke der Veranschaulichung der Erfindung werden in den Zeichnungen Ausführungsformen gezeigt, die gegenwärtig bevorzugt werden. Es sollte verstanden werden, dass die Erfindung jedoch nicht beschränkt ist auf die genauen Anordnungen und Mittel, die gezeigt werden. In den Zeichnungen:
ist Fig. 1 ein Blockdiagramm, das einen Übersetzer gemäß der vorliegenden Erfindung zeigt, der auf einem Prozessor arbeitet und ein Programm von einen ersten Zustand in einen zweiten Zustand übersetzt;
Fig. 2 ist ein Blockdiagramm, das die Struktur eines typischen Programms zeigt, wie es in dem ersten Zustand von Fig. 1 erscheinen kann;
Fig. 3 ist ein Flussdiagramm, das die einleitenden Schritte zeigt, die von dem Übersetzer von Fig. 1 ausgeführt werden;
Fig. 4 ist ein Diagramm, das ein Steuerflussdiagramm (CFG) zeigt, das von dem Übersetzer von Fig. 1 für ein bestimmtes Codesegment konstruiert wird.
Fig. 5-Fig. 9 sind Diagramme, die Beispiele für Codediagramme zeigen, die von dem Übersetzer von Fig. 1 für einzelne Basisblöcke von Code konstruiert werden;
Fig. 10 ist ein Flussdiagramm, das die Schritte zeigt, die von dem Übersetzer von Fig. 1 beim Analysieren einer dynamischen Verzweigung ausgeführt werden;
Fig. 11A-Fig. 11C sind Diagramme, die Codediagramme zeigen, die von dem Übersetzer von Fig. 1 für drei verwandte Blöcke von Code, die analysiert werden sollen, konstruiert werden;
Fig. 12 und Fig. 13 sind Diagramme, die neue, kombinierte Codediagramme zeigen, die von dem Übersetzer von Fig. 1 aus den Codediagrammen von Fig. 11A-Fig. 11C konstruiert werden; und
Fig. 14-Fig. 16 sind weitere Flussdiagramme, die Schritte zeigen, die von dem Übersetzer von Fig. 1 beim Analysieren einer dynamischen Verzweigung ausgeführt werden.

Ausführliche Beschreibung von bevorzugten Ausführungsformen

Eine bestimmte Terminologie kann in der folgenden Beschreibung nur der Bequemlichkeit halber verwendet werden und wird nicht in Betracht gezogen, beschränkend zu sein. Die Wörter "links davon", "rechts davon", "darüber" und "darunter" bezeichnen Richtungen in den Zeichnungen, auf welche Bezug genommen wird. Die Wörter "nach innen" und "nach außen" sind weitere Richtungen hin bzw. weg von der geometrischen Mitte des verwiesenen Objektes. Die Terminologie schließt die Wörter ein, die oben speziell erwähnt wurden, Ableitungen davon und Wörter von ähnlicher Bedeutung.
In der vorliegenden Offenbarung wird besonders Bezug genommen auf den Maschinencodeanweisungssatz E-Mode, der von Compilern für die Verwendung in Verbindung mit bestimmten Computern erzeugt wird, die durch die UNISYS Corporation von Blue Beil, Pennsylvania, hergestellt und verkauft werden. Die vorliegende Erfindung ist jedoch nicht auf einen solchen E-Mode- Anweisungssatz beschränkt und kann tatsächlich mit jedem geeigneten Anweisungssatz (mit entsprechenden Modifikationen) eingesetzt werden.

Dynamisches Verzweigen

E-Mode hat drei dynamische Verzweigungsanweisungen, eine unbedingte (DBUN), die anderen zwei sind bedingte Anweisungen (DBFL & DBTR). Alle Verzweigungsanweisungen nehmen ein oberstes Stapelargument als das Ziel. Die bedingten Abweisungen nehmen ein weiteres Stapelargument als einen Booleschen Hinweis, ob die Verzweigung zu nehmen ist oder durchfallen werden soll. Außer dort, wo es speziell relevant ist für die Verfahren, die beschrieben werden, wird keine weitere Unterscheidung zwischen bedingten und unbedingten Formen vorgenommen werden. Das Zielargument für eine dynamische Verzweigung kann eine von zwei Formen annehmen: ein Programmsteuerwort (Program Control Word, PCW) oder ein Verweis zu einem PCW, oder ein Operand. Ein PCW enthält eine Codeadresse einschließlich einer Segmentidentifikation. Ein Operand wird interpretiert als eine Adresse bezüglich des gleichen Codesegments wie die Verzweigungsanweisung selbst.
Eine gewöhnliche Nutzung der Operandenform ist, in eine Verzweigungstabelle zu verzweigen. Wie bekannt ist, wird eine Verzweigungstabelle während des Kompilierens von Quellcode in ein E-Mode-Programm erzeugt, um eine SWITCH- oder CASE-Anweisung zu implementieren. Zum Beispiel kann beruhend auf dem folgenden Quellcode:
In dem Code wird der Index x auf Begrenzungen geprüft, an die Position der Verzweigungstabelle angepasst und als das Adressargument für eine dynamische Verzweigung DBUN verwendet. Zusätzlich zu diesem Code kann die folgende Verzweigungstabelle erzeugt werden, wobei jeder ihrer Eihträge eine unbedingte statische Verzweigung ist zu einem Ziel, das einem speziellen Fall entspricht:
BRUN - Fall 0
BRUN - Fall 1
BRUN - Fall 2
BRUN - Fall 3
BRUN - Fall n
Wie jetzt verstanden sein sollte, verzweigt die DBUN- Anweisung dynamisch zu der Adresse einer speziellen BRUN- Anweisung in der Verzweigungstabelle, entsprechend der Aktion, die beruhend auf dem Wert x auszuführen ist, und die BRUN- Anweisung verzweigt statisch weiter zu Code entsprechend der Aktion, die beruhend auf dem Wert x ausgeführt werden soll.
Es wird erkannt werden, dass viele Variationen in einer Verzweigungstabelle eingesetzt werden können. Zum Beispiel müssen die einzelnen Tabelleneinträge keine statischen Verzweigungen sein. Jedoch ist Compiler-Konvention, dass ein solcher Eintrag entweder unbedingt woanders hin verzweigen, die Prozedur verlassen oder bedingungsweise fehlschlagen muss. Die einzige Ausnahme für eine derartige Konvention ist, dass der letzte Eintrag in einer Verzweigungstabelle keine Beschränkungen hat und häufig die Codesequenz ist, auf die durch diesen Eintrag hätte verzweigt werden sollen. Es ist außerdem eine Compiler- Konvention, dass in eine Verzweigungstabelle stets durch eine Operand-dynamische Verzweigung eingesprungen wird, niemals über eine vorhergehende Anweisung eingefallen wird.
Die PCW-Form der dynamischen Verzweigung nimmt als ihr Zielargument entweder das PCW selbst oder einen indirekten Verweis auf das PCW. Diese Form muss immer verwendet werden, wenn das Ziel der Verzweigung in einem anderen Codesegment liegt, selbst wenn die Adresse des Ziels fest ist. Das PCW kann an einer adressierbaren Aktivierungsdatensatzposition gespeichert und darauf indirekt verweisen, direkt auf dem Stapel konstruiert (MPCW-Anweisung) oder durch andere Mittel ganz oben auf den Stapel gebracht werden. Ein PCW wird häufig in dem Stapel als der Rücksprungpunkt für einen "billigen" Prozeduraufruf hinterlassen, wo die 'Ausstiegs'-Anweisung lediglich DBUN ist.
Unter bestimmten Umständen wird dynamische Verzweigung durch eine einfache literale Codeadresse erreicht. In einer solchen Situation wird die Adresse entweder in dem Stapel gelassen oder in einer lokalen Aktivierungsdatensatzzelle gespeichert, und wird verwendet, um den Zustand einer Schleife mit vielfachen Teilen anzuzeigen. Die DBUN-Anweisung wird dann verwendet, um zu dem nächsten Element der Schleife zu iterieren. Jedes Element aktualisiert dann den Zustand geeignet für die nächste Iteration. Diese Form kann von einem Compiler verwendet werden, um jedes beliebige "Zustandsautomaten"-Konstrukt zu implementieren.

Einleitende Übersetzeroperation

In der vorliegenden Erfindung, und bezugnehmend jetzt auf Fig. 1, übersetzt ein Wieder-Compiler oder Übersetzer 10 kompilierten Maschinencode von einem ersten Zustand 12 entsprechend eines ersten Anweisungssatzes in einen zweiten Zustand 14 entsprechend eines zweiten Anweisungssatzes. Typischerweise wird der Übersetzer auf einem Prozessor 16 mit angehängtem Speicher 18 betrieben, und der Übersetzer 10 wird durch den Prozessor 16 von einem Computerlesbaren Medium 17, das Computer-ausführbare Anweisungen aufweist, konstruiert. Jeder geeignete Prozessor 16 und jeder geeignete Speicher 18 können eingesetzt werden.
In der vorliegenden Offenbarung wird der Maschinencodeanweisungssatz E-Mode als ein Beispiel für den ersten Anweisungssatz eingesetzt. Jedoch kann der erste Anweisungssatz jeder geeignete Anweisungssatz sein. Ähnlich kann der zweite Anweisungssatz jeder geeignete Anweisungssatz sein.
Bezugnehmend jetzt auf die Fig. 2 besteht ein E-Mode- Programm 20 aus einem Satz von Codesegmenten 22. Beschreiber für die Codesegmente sind in einem Segmentverzeichnis enthalten. In der vorliegenden Erfindung wird eine Codeanalyse von dem Übersetzer 10 für immer nur ein Codesegment 22 ausgeführt, wenn auch die Generalisierung auf ein vollständiges Programms 20 unkompliziert ist.
Ein einzelnes Codesegment 22 kann allgemein in einen Satz von Basisblöcken 24 unterteilt werden, wobei jeder Basisblock 24 eine Sequenz ist, in die nur an ihrem Anfang eingesprungen wird, sei es durch eine Verzweigung, einen Prozeduraufruf oder Durchfallen von einem vorhergehenden Block, und die nur durch die letzte Anweisung in einem solchen Basisblock 24 verlassen wird. Folglich muss jede Verzweigung notwendigerweise die letzte Anweisung in einem Basisblock 24 sein. Oft, aber nicht immer, ist ein Basisblock 24 definiert als eine maximale Sequenz, aber das ist zum Zweck der vorliegenden Erfindung nicht notwendig.
Vorzugsweise wird in der vorliegenden Erfindung die Endanweisung in einer Prozeduraufrufsequenz (ENTR) wie eine Verzweigung behandelt, wie es bestimmte, eine Unterbrechung verursachende Anweisungen sind. Dies hilft bei der Aktivheitsbestimmung (d. h. ob ein einzelner Basisblock 24 von irgendeinem anderen Basisblock 24 erreichbar ist, oder ob ein solcher einzelner Basisblock 24 'Abfall' ist, herrührend aus der ursprünglichen Kompilierung des E-Mode-Programms 20, und deshalb ignoriert werden kann) und markiert deutlich Rücksprungpunkte. Da ein PCW nur mit einer MPCW-Anweisung konstruiert werden kann, wird eine Abtastung eines E-Mode-Programms 20 in alle Codesegmente 22 Basisblöcke 24 identifizieren, in die über einen Prozeduraufruf oder eine dynamische PCW-Verzweigung eingesprungen werden kann. Zusätzlich ist eine Abtastung eines solchen Programms 20 in alle Segmenten 22 notwendig, um alle Verzweigungen und andere Strukturen zu identifizieren, die einen Basisblock 24 beenden oder beginnen würden.
In der vorliegenden Erfindung, und bezugnehmend jetzt auf die Fig. 3, überprüft dann der Übersetzer 10 als eine vorläufige Angelegenheit das ganze Programm 20, um solche PCWs, Verzweigungen und andere Strukturen ausfindig zu machen, und dadurch alle Basisblöcke 24 in dem Programm 20 vorläufig zu identifizieren (Schritt 301). Der Übersetzer 10 kann dann eine entsprechende Tabelle oder dergleichen konstruieren, um für jeden identifizierten Basisblock 24 und damit verwandte Informationen die Übersicht zu behalten. Solche Informationen können einschließen, sind aber nicht beschränkt auf: Aktivheit/Erreichbarkeit, Codeadresse, Einsprung- und Ausstiegmodus, und eine Datstellung der Anweisungen in dem Basisblock 24. Es sollte verstanden werden, dass die Identifikation von Basisblöcken 24 auf dieser Stufe vorläufig ist insofern, als dass einige Verzweigungen und andere Endstrukturen möglicherweise noch nicht nachgewiesen worden sind. Zum Beispiel kann eine dynamische Verzweigung ein Ziel in der Mitte dessen haben, was ein einzelner Basisblock 24 zu sein scheint, was darauf hinweist, dass dieser scheinbär einzelne Basisblock 24 tatsächlich ein Paar (mindestens) Basisblöcke ist, wobei der zweite Basisblock des Paars an dem vorher genannten Ziel beginnt, und der erste Basisblock unmittelbar davor endet. Wenn jedoch weitere Basisblöcke 24 später nachgewiesen werden, kann die zuvor genannte Tabelle geeignet angepasst/aktualisiert werden.
Sobald die Basisblöcke 24 identifiziert sind, beginnt der Übersetzer 10 dann damit, Verbindungen zwischen den identifizierten Basisblöcken 24 in einem einzelnen Segment 22 zu identifizieren (Schritt 303) und konstruiert ein vorläufiges Steuerflussdiagramm oder eine vorläufige Darstellung. (CFG) 26 von dem Segment 22, beruhend auf den identifizierten Basisblöcken 24 (Schritt 305). Ein solches CFG 26 ist in Form eines Diagramms in Fig. 4 veranschaulicht, auch wenn verstanden werden sollte, dass der Übersetzer 10 das CFG 26 in einer Datei oder einem Tabellenformat oder dergleichen pflegt. Zusätzlich werden, wenn Verzweigungsziele bestimmt sind, auch Verbindungen eingerichtet von einem Basisblock zu Verzweigungszielen von diesem Basisblock. Die eingerichteten Verbindungen sind die Basis für das CFG 26. Wie verstanden werden sollte, ist das CFG 26 vorläufig insofern, als dass einige Basisblöcke 24 möglicherweise vorläufig nicht identifiziert worden sind, und als dass dynamische Verzweigungsziele bis jetzt nicht identifiziert sind. Jedoch kann das CFG 26 geeignet angepasst/aktualisiert werden, nachdem geeignete zusätzliche Informationen erhalten worden sind.
Bezugnehmend jetzt auf die Fig. 4 wird ein CFG 26 für ein Segment 22 gezeigt, das sechzehn identifizierte Blöcke 24 besitzt. Wie gesehen werden kann, wird in das Segment 22 bei Block A eingesprungen, welcher entweder zu Block B oder Block C verzweigt. Die Blöcke C und D bilden einen kreisförmigen Pfad, auch wenn Block D auch zu Block E führt, welcher zu Block F führt, welcher zu Block G führt. Die Blöcke E und F verzweigen auch zu Block N. Block G endet mit einer dynamischen Verzweigung und wird deshalb von dem Übersetzer 10 analysiert werden. Vorzugsweise kompiliert der Übersetzer 10 eine Liste aller aktiven Blöcke 24 mit dynamischen Verzweigungen. Es ist keine Verbindung von Block G zu irgendeinem anderen Block gegenwärtig bekannt, auch wenn herausgefunden werden wird, dass Block G zu Block H, I und J führt, wie durch die gestrichelten Verbindungslinien angezeigt wird.
Die Blöcke H, I bzw. J führen zu den Blöcken K, L und M, welche alle zu Block N führen. Block K führt außerdem zu Block O, welcher zu Block P führt, welcher wiederum zu Block B führt. Die Blöcke H-M, O und P sind als nicht aktiv markiert, da für keinen anderen Block 24 gegenwärtig bekannt ist, dass er auf die Blöcke H-J verzweigt, und für die Blöcke K-M, O und P ist gegenwärtig bekannt, dass sie nur von Block F aus erreichbar sind. Block Q ist als nicht aktiv markiert, da er gegenwärtig von keinem anderen Block aus erreichbar ist. Darüber hinaus verzweigt Block Q (zumindest gegenwärtig) zu keinem anderen Block 24 in dem Segment 22.

Grafische Codedarstellung

In der vorliegenden Erfindung konstruiert der Übersetzer 10, sobald er das Programm 20 vollständig syntaktisch analysiert hat, um die Basisblöcke 24 und das CFG 26 einzurichten, und sobald er eine Liste von allen aktiven Blöcken 24 mit dynamischen Verzweigungen kompiliert hat, dann ein Codediagramm oder eine Darstellung 28 (wie z. B. in Fig. 5-Fig. 9 zu sehen ist) der Anweisungen in jedem Block 24 (Schritt 307). Alternativ kann der Übersetzer 10 ein Codediagramm 28 für einen Block 24 auf einer Bedarfsbasis konstruieren, da es der Fall sein kann, dass nicht alle Blöcke 24 grafisch vom Code her dargestellt werden müssen. Wie beim CFG 26 werden die Codediagramme 28 in den Zeichnungen in Form von grafischen Darstellungen gezeigt, auch wenn verstanden werden sollte, dass der Übersetzer 10 die Codediagramme 28 in einer Datei oder einem Tabellenformat oder dergleichen pflegt. Vorzugsweise ist jedes Codediagramm 28 ein gerootetes gerichtetes azyklisches Diagramm mit miteinander verbundenen Knoten, wobei diese Knoten in drei Kategorien fallen: Anweisungsknoten, Innenknoten und Spezialknoten. Alle Knoten tragen einige Grundinformationen, wie z. B. wie viele Stapeleingaben von dem Knoten benötigt werden, und wie viele Stapelelemente von dem Knoten zurückgelassen werden.
Bezugnehmend jetzt auf die Fig. 5-Fig. 9 sind Anweisungsknoten Astknoten, die keine abgehenden Kanten haben. Jeder Anweisungsknoten stellt eine Anweisung in dem ursprünglichen Strom von Anweisungen in dem Block 24 dar. Wenn eine Anweisung ein oder mehrere Argumente von dem Stapel verbraucht, wird sie mit diesen Argumenten durch einen Anwendungs-Innenknoten 'apply' verbunden. Der Anwendungsknoten hat zwei ausgehende Kanten, eine (auf der linken Seite) zu der Anweisung, die angewendet wird, und die andere (auf der rechten Seite) zu dem/den Argument(en), die angewendet werden sollen. Die meisten Anweisungen hinterlassen Null oder ein Ergebnis auf dem Stapel. Der Anwendungsknoten stellt dann die Anwendung der Anweisung auf die Argumente dar. Wo das Ergebnis einer derartigen Anwendung dann ein Argument für eine nachfolgende Anweisung ist, kann durch die rechte Kante des Anwendungsknotens auf den Anwendungsknoten für die folgende Anweisung verwiesen werden. Es wird kein Anwendungsknoten für Anweisungen benötigt, welche kein Argument von dem Kopf des Stapels nehmen.
Viele E-Mode-Anweisungen nehmen mehr als ein Argument von dem Stapel. Diese Argumente werden in dem Diagramm unter Verwendung eines Stapel-Innenknotens 'stack' dargestellt. Ein Stapelknoten hat ebenfalls zwei ausgehende Kanten. Die Linke zeigt die jüngsten (obersten) Elemente an, die zu dem Stapel hinzugefügt wurden, und die Rechte zeigt die übrigen Elemente an. Der linke Teilbaum eines Stapelknotens ist niemals selbst ein Stapel-Teilbaum, während der rechte Teilbaum oftmals einer ist. Der Ausdruck 'Element auf dem Stapel' wird hier locker verwendet, da ein Stapel-Teilbaum einen Ausdruck darstellen kann, der nichts auf dem Stapel hinterlässt.
Es ist häufig der Fall, dass ein Basisblock 24 eine Anweisung enthält, für die einige oder alle Argumente von einem anderen Basisblock geliefert (d. h. durch diesen auf den Stapel gesetzt) werden. Der Spezialknoten 'missing' (fehlend) wird als ein Platzhalter in dem Diagramm für das fehlende Argument verwendet. Ein Knoten für ein fehlendes Argument ist ein Ast und zeigt immer ein Einzelelement auf dem Stapel an. Jeder Knoten in einem Diagramm enthält einen Zählwert für die Zahl der Knoten für ein fehlendes Argument in dem Teilbaum, den er anführt.
Einige E-Mode-Anweisungen geben mehrere Elemente an den Stapel zurück. Um zu ermöglichen, dass diese Ergebnisse einzeln als Eingabeargumente für spätere Anweisungen dargestellt werden, agiert der Innenknoten 'alias' als ein Platzhalter und indirekter Verweis auf ein (allgemein nicht das oberste) Ergebniselement von einer solchen Anweisung. Er ist ein Innenknoten, an den ein Stapelknoten oder Anwendungsknoten grenzt, und er hat eine einzige ausgehende Kante, die normalerweise zu der Anwendung von der Anweisung führt, die das Element hervorruft, auf das er verweist, oder manchmal (siehe unten) direkt zu einem der Argumente einer solchen Anwendung führt. Ein Aliasknoten zeigt immer auf einen anderen Knoten in dem gleichen Codediagramm 28, und er zeigt niemals auf einen anderen Aliasknoten oder einen Stapelknoten. Ein solcher Aliasknoten trägt auch einen Index, der anzeigt, auf welches der Ergebnisse dieser Anweisung gerade verwiesen wird.
Wo ein Aliasknoten verwendet wird, um einen Ausdruck darzustellen, der eine Anweisung mit mehreren Ergebnissen einschließt, wird der Anwendungsknoten für diese Anweisung markiert, dass er nur ein Ergebnis zurückgibt. In der Praxis wird ein Anwendungsknoten niemals mit einem Ergebniszählwert größer als eins erscheinen. Stapelknoten jedoch werden so erscheinen, da der Ausgabezählwert, der einem Stapelknoten zugeordnet ist, die Summe für den Teilbaum ist, den er anführt.
Der E-Mode-Anweisungssatz umfasst einen Satz von Anweisungen, welche Elemente oben auf dem Stapel permutieren. Diese umfassen DUPL: duplicate top of stack (Kopf von Stapel duplizieren), EXCH: exchange two top of stack items (zwei obere Stapelelemente austauschen), RSDN: rotate top three items down (obere drei Eemente nach unten rotieren), und RSUP: rotate top three items up (obere drei Elemente nach oben rotieren). Die Aliasknoten für diese Anweisungen zeigen eher direkt auf das ursprüngliche Element, mit einem Index von eins, als auf den Anweisungsknoten.
In der Fig. 5 stellt das gezeigte Codediagramm 28 die Berechnung eines Wertes und die Zuordnung dieses Wertes zu einer Variablen dar. Das Diagramm 28 zeigt die Verhältnisse zwischen Anweisungen und Argumenten sowie, wie der Stapelknoten verwendet wird, um vielfache Argumente zu gruppieren. Insbesondere stellt das Codediagramm 28 die Quellcodeanweisung dar:
A := (B* -C) + D
die in dem E-Mode-Anweisungssatz dargestellt werden kann als:
VALC B (Wert B auf Stapel setzen)
VALC C (Wert C auf Stapel setzen)
CHSN (das Vorzeichen des obersten Elementes auf Stapel wechseln)
MULT (die oberen beiden Elemente auf Stapel verwenden und multiplizieren, Ergebnis auf Stapel zurücklassen)
VALC D (D auf Stapel setzen)
ADD (die oberen beiden Elemente auf Stapel verwenden und addieren, Ergebnis auf Stapel zurücklassen)
NAMC A (einen Verweis für Position A auf Stapel setzen)
STOD (die oberen beiden Elemente auf Stapel verwenden und Ergebnis an angezeigtem Ort speichern)
Wie aus der Betrachtung von Fig. 5 erkannt werden kann, ereignet sich in jedem Codediagramm 28 die chronologische Aktion allgemein von unten nach oben in einer Querrichtung des umspannenden Baums (d. h. des Baums ohne irgendwelche Aliasknoten und Verbindungen) von unten rechts nach oben links. Jedoch ereignet sich eine Zurückverfolgungsanalyse, die von dem Übersetzer 10 ausgeführt wird, wie unten besprochen werden wird, allgemein von oben nach unten (d. h. in umgekehrter chronologischer Reihenfolge).
Fig. 6 zeigt ein Diagramm 28 für einen Block 24, wobei das Diagramm 28 einen Aliasknoten einschließt, um die Wirkung einer DUPL-Anweisung (duplicate top of Stack = Kopf von Stapel duplizieren) darzustellen. Da DUPL keine Modifikation von seinen Argumenten hervorruft, verweist der Alias direkt auf den VALC- Knoten. Die Anwendung von DUPL selbst produziert ein Argument für ADD, während der Alias verwendet wird, um das andere Argument darzustellen.
Wie in der Fig. 7 gezeigt ist, werden zwei Aliasknoten benötigt, um die Wirkung von RSDN (rotate stack down = Stapel nach unten rotieren) darzustellen, wodurch das oberste Element des Stapels zum dritten Element in dem Stapel gemacht und das zweite und dritte Element nach oben zur ersten bzw. zweiten Position verschoben werden.
Wie in der Fig. 8 gezeigt ist, verwendet die grafische Darstellung 28 'missing'-Knoten, um die fehlenden Argumente darzustellen, wenn ein Block 24 Anweisungen enthält, für die einige Argumente von diesem Block 24 nicht geliefert werden (d. h. durch einen anderen Block 24 auf den Stapel gesetzt werden). Ein Knoten für ein fehlendes Argument hat immer einen Stapelelementausgabezählwert von eins.
Wie in der Fig. 9 gezeigt ist, verursacht die TEQU- Anweisung (transfer while equal update) selbst eine irgendwie extreme Kombination aus 'missing'-Knoten und Aliasknoten. Wie verstanden werden sollte, verbraucht eine solche TEQU-Anweisung vier Stapelargumente und hinterlässt drei Ergebniselemente auf dem Stapel. Die zurückgegebenen Elemente sind nicht einfache Kopien von irgendeinem der ursprünglichen Argumente, so dass die Aliasknoten auf die Anwendung von TEQU verweisen und Indizes enthalten, die das zweite und dritte zurückgegebene Element anzeigen.
Im Allgemeinen kann der Übersetzer 10, wie durch die zahlreichen Beispiele gesehen werden kann, die in der Fig. 5- Fig. 9 dargestellt sind, beruhend auf jeder Anweisung in einem Baustein 24 und die Wirkung, die eine solche Anweisung auf den Stapel hat ein Codediagramm 28 konstruieren, um einen solchen Block 24 in einer relativ direkten Art und Weise darzustellen. Spezialknoten werden allgemein von dem Übersetzer 10 eingesetzt, nachdem ein solcher Übersetzer 10 das Codediagramm 28 konstruiert hat, und schließen die 'Test'-Knoten ein. Drei Typen von Testknoten werden verwendet, um Verzweigungen darzustellen, wenn Codediagramme 28 aus vielfachen Basisblöcken 24 kombiniert werden, um die Anweisungssequenz entlang eines Pfads darzustellen. Solche Testknoten agieren als Anweisungen, die auf ein einzelnes Argument angewendet werden, und sind Astknoten. Knoten für Test wahr und Test falsch zeigen jeweils an, dass der Pfad annimmt, dass das Argument wahr oder falsch ergibt. Der Testindex-Knoten zeigt an, dass das Argument einen ganzzahligen Wert ergibt, der dem Index entspricht, den die Anweisung mit sich führt. Die Testknoten werden bei der Begrenzungsevaluierung verwendet, wie ausführlicher unten erklärt werden wird.

Bestimmung des Ziels einer dynamischen Verzweigung

Falls in der vorliegenden Erfindung der Übersetzer 10 ein Programm 20 übersetzt, das in den E-Mode-Anweisungssatz kompiliert wurde, kann dieser Übersetzer 10 alle Analysen an einem Segment 22 auf Basis von Segment 22 ausführen, anstatt von allen Segmente 22 gleichzeitig. Das ist möglich mit Bezug auf E- Mode, da alle Ziele einer statischen Verzweigung oder Operand- dynamischen Verzweigung von E-Mode in dem gleichen Codesegment 22 wie diese Verzweigung liegen.
Wie oben besprochen wurde, richtet der Übersetzer 10 zuerst die Begrenzungen der Basisblöcke 24 ein (mit einer Ausnahme, die unten erklärt wird) (Schritt 301). Der Übersetzer 10 richtet dann das unvollständige Steuerflussdiagramm (CFG) 26 ein, das die Wirkung von statischen Verzweigungen darstellt (Schritt 305), und transformiert die Codesequenzen in jedem Basisblock 24 in grafische Darstellungen 28 für die weitere Analyse (Schritt 307). Für Steuerflusszwecke werden Prozeduraufrufe modelliert, als ob sie einen Basisblock beenden, aber zu dem nächsten durchfallen. Die einzige Ausnahme dazu ist, dass sogenanntes "bad goto" ('longjmp' in C) implementiert wird als ein Prozeduraufruf an eine Betriebssystemroutine, die nicht zu dem Aufrufpunkt zurückkehrt. Das muss speziell erkannt werden und als eine unbedingte Verzweigung behandelt werden, da der Compiler, der ursprünglich das Programm 20 erzeugte, wissend, dass der Stapel zurückgeschnitten werden wird, manchmal diesen Stapel in einem Zustand lässt, welcher nicht den Anforderungen des folgenden Blockes 24 genügt. Das CFG 26, das von dem Übersetzer 10 gebildet wird, bildet nicht die Verhältnisse zwischen Blöcken 24 ab, die durch Prozeduraufrufe verursacht werden. Das heißt, es gibt weder eine Kante von einem aufrufenden Block 24 zu seinem Ziel, noch von dem Ziel zurück zu dem Rücksprungpunkt. Eine solche Modellierung ist nicht erforderlich, da in der Praxis solche Verhältnisse bei der Bestimmung dynamischer Verzweigungsziele keine Rolle spielen.
Wie in der Fig. 4 gesehen werden kann, ist das CFG 26 von Natur aus gerichtet, da es das dynamische "Folge"-Verhältnis zwischen Basisblöcken 24 darstellt. Jeder Block 24, für den es ein PCW gibt, wird als ein Root behandelt. Einige Basisblöcke 24 in dem unvollständigen CFG 26 können von einigen Roots oder von allen Roots nicht erreichbar sein. Das ereignet sich wegen fehlender Verbindungen aufgrund dynamischer Verzweigungen, da vielfache Prozeduren in einem einzelnen Codesegment 22 vorhanden sein können, und da der Compiler, der ursprünglich das Programm 20 erzeugte, möglicherweise beim Beseitigen nicht erreichbarer Codes nachlässig gewesen ist.
Innerhalb des unvollständigen CFG 26 sind die Blöcke 24, die von einem PCW erreicht werden können, als aktiv markiert. Einige aktive Blöcke 24 können von noch nicht aktiven (möglicherweise niemals aktiven) Blöcken 24 erreichbar sein. Es ist möglich, dass die anfängliche Übersetzeranalyse (Schritt 301) eine Codesequenz, die tatsächlich aus mehreren Blöcken 24 besteht, als einen einzigen Basisblock 24 identifiziert. Das wird schließlich entdeckt, wenn eine (Nicht-Verzweigungstabellen-) dynamische Verzweigung ein Ziel in der Mitte eines angeblichen Blocks 24 hat. Ein solcher Block 24 muss in zwei geteilt werden, und das CFG 26 und andere Strukturen müssen entsprechend angepasst werden.
Vorzugsweise analysiert der Übersetzer 10 jede dynamische Verzweigung, aber nur, wenn sie aktiv wird. Dies minimiert die Notwendigkeit, alle dynamischen Verzweigungen, auf neu entdeckten Verbindungen beruhen, in dem CFG 26 zu analysieren.
Vorzugsweise, und bezugnehmend jetzt auf die Fig. 10, ist, sobald eine dynamische Verzweigung identifiziert ist (Schritt 1001), das allgemeine Verfahren der Analyse, das von dem Übersetzer 10 eingesetzt wird, alle Anweisungssequenzen, die zu einer dynamischen Verzweigung führen, so weit zurück zu untersuchen, wie notwendig ist, um den Typ des Argumentes vollständig zu bestimmen, und, falls es ein Operand ist, den Bereich oder Satz von Werten, den dieser Operand annehmen kann, zu untersuchen (Schritt 1003). Sobald alle möglichen Ziele von der dynamischen Verzweigung definiert sind, untersucht der Übersetzer dann diese Ziele auf Gültigkeit und um eine mögliche Verzweigungstabelle zu identifizieren (Schritt 1005). Zuletzt wird die dynamische Verzweigung in dem Codediagramm 28 ersetzt durch eine genauere Darstellung der beabsichtigten Wirkung, und das CFG 26 wird aktualisiert, um den tatsächlichen Satz von Zielen anzuzeigen, wobei Aktivheit bei Bedarf fortgepflanzt wird (Schritt 1007). Entsprechend entdeckt der Übersetzer 10 schließlich alle Ziele, die mit der dynamischen Verzweigung verbunden sind, wenn er den Programmiercode von dem ersten Codezustand 12 in den zweiten Codezustand 14 übersetzt (Schritt 1009).

Argumente bestimmen

Das erste Ziel ist, die Art des Argumentes für die dynamische Verzweigung zu bestimmen, d. h. Operand oder PCW. Der Übersetzer 10 erkennt einen Operanden als durch arithmetische Anweisungen oder Ausdrücke wie VALC (Wert auf Stapel setzen) gebildet, als durch eine 'Literal'-Anweisung (welche ihren Zwischenparameter oben auf dem Stapel als einen Operanden hinterlässt) gebildet, oder ADD, oder als explizit begrenzungsgeprüft mit arithmetischen Vergleichen. Ein dynamisches Verzweigungsargument, das durch ein NAMC erzeugt wird (welches einen indirekten Verweis erzeugt), wird immer ein PCW sein, und für jedes Argument, für das nicht bestimmt werden kann, dass es ein Operand ist, wird angenommen, dass es ein PCW ist.
Es gibt eine Zahl von Idiomen, die von Compilern verwendet werden, welche irgendwie den Analysenprozess des Übersetzers 10 vereinfachen, da die Betrachtung der vollständigen potentiellen Semantik von jeder möglichen Kombination von Anweisungen vermieden werden kann. Zum Beispiel begrenzt der einleitende Code zu einer Verzweigung in einer Verzweigungstabelle immer das Verzweigungsargument, entweder explizit oder implizit. Diese Notwendigkeit entspringt der fundamentalen Multiprocessing-, Shared-Memory-Natur von E-Mode und anderen modernen Anweisungssätzen. Wo expliziter begrenzender Code für eine Verzweigungstabelle in einem Block 24 erscheint, geht er immer unmittelbar der dynamischen Verzweigung voran, was es leicht macht, sie ausfindig zu machen und zu analysieren.
Es gibt eine Zahl von Modellen zum expliziten Begrenzen unter Verwendung verschiedener Kombinationen von Vergleichen und bedingten Verzweigungen, möglicherweise mit logischen Operationen, um den oberen und unteren Begrenzungstest zu kombinieren. Ein anderer Ansatz ist, Minimum- und Maximumfunktionen auf das Argument anzuwenden, um es in einen Bereich zu setzen, der über die nominelle Verzweigungstabellenausdehnung um einen Platz an beiden Enden hinausgeht. Die Verzweigungstabelle wird erweitert, um passend zu sein, und die zusätzlichen Elemente verzweigen beide zu dem 'else'-Code.
Eine oder beide der Begrenzungen können durch die Anweisungen beeinträchtigt werden, die zum Konstruieren des Argumentes verwendet werden. Von besonderem Nutzen sind Bitfeldisolieranweisungen, die ihre Ergebnisse auf einen engen, ganzzahligen Arithmetikbereich beschränken. Andere Anweisungen können erzwingen, dass das Argument positiv ist (untere Begrenzung von 0) usw. Solche Kenntnis kann eingesetzt werden, um das explizite Begrenzungsprüfen gänzlich überflüssig zu machen. Statt dessen kann die Verzweigungstabelle bei Bedarf erweitert werden, um mit dem aktuellen Bereich des Argumentes zusammenzupassen, oder um nur die obere oder untere Begrenzung zu prüfen.
Ein anderes Idiom-Beispiel betrifft das Verb COBOL PERFORM. Ein solches Verb wird implementiert, indem in den Kopf des Stapels ein PCW gedrückt wird, das den Rücksprungpunkt anzeigt, und eine ganze Zahl, welche den Absatz identifiziert, der den PERFORM-Bereich beendet. Auf den ersten Absatz des PERFORM- Bereichs wird dann verzweigt, entweder mit einer statischen Verzweigung (falls das Ziel in dem gleichen Codesegment liegt) oder der Kombination von MPCW (Make PCW) und einer dynamischen Verzweigung. Für Zwecke des Steuerflussdiagramms für das Codesegment ist es wichtig, zu erkennen, dass dieses Konstrukt sich wie ein Prozeduraufruf verhält, und die Ausführung wird schließlich wieder aufgenommen bei der Anweisung, die der Verzweigung folgt. Der Ausstieg aus einer COBOL PERFORM-Sequenz ist immer ein Test des obersten Stapelelementes, um zu bestimmen, ob es ein PERFORM repräsentiert, welches bei dem aktuellen Absatz endet. Ist dies der Fall, dann wird dieses Element gelöscht, und eine dynamische Verzweigung folgt, welche immer erwartet, ein PCW zu finden.
Ein anderes Idiom-Beispiel betrifft Quersegmentaufrufe. Spezieller können einige Compiler für blockstrukturierte Sprachen (ALGOL, NEWP) den Code für einen Innenblock in ein separates Codesegment 22 setzen, wobei eine PCW-dynamische Verzweigung für Einsprung sowie Rücksprung erforderlich ist. Der Einsprungcode sind zwei aufeinanderfolgende MPCWs, wobei das erste den Rücksprungpunkt anzeigt und das zweite den Beginn des Innenblocks anzeigt, und ein DBUN (dynamic branch unconditional = unbedingte dynamische Verzweigung). Der Rücksprungpunkt ist immer die Anweisung, die unmittelbar dem DBUN folgt. Wie bei COBOL PERFORM ist es wichtig zu erkennen, dass die Ausführung schließlich bei der nächsten Anweisung wieder aufgenommen wird. Der Ausstieg aus einem Innenblock in einem separaten Codesegment ist einfach ein DBUN, dessen Argument nicht bereitgestellt wird durch einen Code, der DBUN in dem gleichen Codesegment 22 vorangestellt ist. Ein solches DBUN erwartet, das Rücksprung-PCW zu finden, das von der Einsprungsequenz zurückgelassen wurde. Der Übersetzer 10 muss aufdecken, dass das Argument für DBUN nicht durch einen Basisblock in diesem Codesegment 22 bereitgestellt wird, und muss deshalb folgern, dass der gegenwärtige Fall eingetreten ist.
Ein anderes Idiom betrifft PCW-Gotos. Für Fälle von entweder expliziten programmierspezifischen Verzweigungen zu einem anderen Codesegment oder einer Compilergenerierten Instanz davon wird der Code eine von zwei Formen annehmen: entweder NAMC; DBUN oder MPCW; DBUN. Beide Formen sind unmittelbar als PCW-Fälle erkennbar und erfordern keine weitere Analyse.

Pfadanalyse

Bei der Durchführung einer Pfadanalyse behandelt der Übersetzer der vorliegenden Erfindung das unvollständige CFG 26 als eine gerichtete grafische Darstellung, gerootet in den Block 24, der die interessierende dynamische Verzweigung enthält, und mit Kanten, die den Kanten in dem umgekehrten CFG 26 entsprechen. Die Suche erfolgt zuerst in der Tiefe, so tief wie notwendig, um alle möglichen Quellen des Argumentes für die interessierende dynamische Verzweigung zu finden. Falls eine Rückkante angetroffen wird, wird dieser Pfad als eine Schleife deklariert und ignoriert.
Falls der Pfad ohne Lieferung einer Quelle endet, kann es sich um eine von zwei Situationen handeln. Der Übersetzer 10 kann auf einen Block 24 gestoßen sein, der nur durch eine dynamische Verzweigung erreichbar ist, die bisher noch nicht evaluiert worden ist, oder er kann zu einem Punkt gekommen sein, wo in das Codesegment durch eine PCW-dynamische Verzweigung von woanders her eingesprungen wurde. Der letztere Fall kann ignoriert werden, da er anzeigt, dass die gegenwärtige dynamische Verzweigung ein Segmentausstieg (PCW) ist, und das wird die Vorgabe sein. Für den vorhergehenden Fall kann es notwendig sein, die Analyse iterativ durchzuführen, um die Interaktion zwischen vielfachen dynamischen Verzweigungen aufzudecken.
Sobald der Übersetzer 10 alle Pfade zu einer interessierenden dynamischen Verzweigung untersucht hat, wird es null oder mehr Pfade geben, an die jeweils Typ- und möglicherweise Begrenzungsinformationen angehängt sind. Falls es keine gibt, nimmt der Übersetzer 10 einen Segmentausstieg an (ein PCW wurde auf dem Stapel zurückgelassen, als in das Codesegment 22 eingesprungen wurde), und der Verzweigungstyp ist PCW. In diesem Fall braucht sonst nichts weiter getan zu werden, da die PCWs übersetzt werden, und das CFG 26 erstreckt sich nicht quer über Codesegmente 22 und braucht somit nicht aktualisiert zu werden. Explizite Fälle einer dynamischen Verzweigung, die entweder durch NAMC oder MPCW eingeleitet werden, sind selbstverständlich eine PCW-Form einer dynamischen Verzweigung.
Falls alle Pfade zurück von einer interessierenden dynamischen Verzweigung ganzzahlige Begrenzungen anzeigen, wobei die oberen und unteren Begrenzungen innerhalb jedes Pfades gleich sind (aber unterschiedlich zwischen den verschiedenen Pfaden sind), ist die Quelle ein Literal, und der Fall ist ein endlicher Zustandsautomat, wobei die Zustandsanzeige oben auf dem Stapel zurückgelassen wird. Der Übersetzer 10 wird dann die Anweisungen identifizieren, die die Literale bereitstellen, so dass die Literalwerte während der Codeübersetzung und -erzeugung aktualisiert werden können, um geänderte Codeadressen widerzuspiegeln.
Falls es nur einen Pfad gibt, und dessen Quelle ein VALC (Holen eines Operanden von einer lokalen Variablen) mit einer unteren Begrenzungsprüfung ist, ist es die Form eines endlichen Zustandsautomaten, wobei der Zustandsanzeiger in einem lokalen temporären Speicher gespeichert ist. Das ist ein ALGOL-Idiom. Alle gespeicherten Werte in dieser temporären Zelle in Blöcken 24, die die dynamische Verzweigung erreichen, müssen von dem Übersetzer 10 untersucht werden, und die Literale, die gespeichert sind, müssen identifiziert werden wie oben, um aktualisiert zu werden. Beachten Sie, dass dies funktioniert, da der ALGOL-Compiler diese Stapelzelle einem bestimmten Fall von diesem Konstrukt speziell zueignet und sie für nichts weiteres verwendet.
Falls es einen einzigen Pfad gibt und er vollständig begrenzt ist, wird eine Verzweigungstabelle angezeigt.
Wegen der Unsicherheit bezüglich dessen, was von einem Prozeduraufruf zurückgegeben werden kann (ein Ergebnis oder kein Ergebnis auf den Stapel), ist es möglich, scheinbare Pfade zu haben, die sowohl auf PCW- als auch auf Operandenformen hinweisen. Da Prozeduraufrufe nicht zwischen der Quelle und der dynamischen Verzweigung für entweder Verzweigungstabellen oder lokale variable endliche Zustandsautomaten vermitteln, wird die Wahl nur zwischen explizitem PCW und endlichem Top-ofstack- Zustandsautomaten sein. Vorzugsweise, und etwas heuristisch, nimmt der Übersetzer 10 an, dass die Liste der Konstanten die richtige Antwort ist, so dass dieser Fall als endlicher Top-of- stack-Zustandsautomat genommen wird.

Codediagrammgenerierung

Ein Codediagramm 28 wird für einen Basisblock 24 erzeugt, indem jede der Anweisungen des Blocks 24 wiederum angewendet wird auf das Codediagramm 28 (als das Argument für die Anweisung dienend), das von den vorhergehenden Anweisungen resultiert. Der Prozess beginnt mit der ersten Anweisung in dem Basisblock 24 und einem leeren Codediagramm 28, und schreitet durch die Anweisungen des Basisblocks 24 in der Reihenfolge der Ausführung voran.
Jede Anweisung wird untersucht, um zu bestimmen, wie viele Stapeleingaben sie erfordert. Das Argumentcodediagramm 28 wird dann in separate Teildiagramme zerlegt, die den verschiedenen Elementen auf dem Stapel entsprechen (erzeugt durch die vorhergehenden Anweisungen). Falls es exakt genug Elemente gibt, die durch das Argumentcodediagramm 28 dargestellt werden, wird es direkt als das Argument verwendet. Falls es mehr Elemente gibt, die durch das Argumentcodediagramm 28 dargestellt werden, als von der Anweisung benötigt werden, wird die erforderliche Zahl verwendet (d. h. von oben von dem Stapel), und der Rest wird beiseite gehalten. Falls es weniger Elemente gibt, die durch das Argument dargestellt werden, als von der Anweisung benötigt werden, als ein Hinweis darauf, dass die Argumente durch Abweisungen in einem Vorgänger-Basisblock 24 geliefert werden, werden genügend Knoten für fehlende Argumente ('missing'-Knoten) bereitgestellt, um das Defizit zu adressieren.
Es ist wichtig zu beachten, dass einige Teildiagramme von dem Argumentcodediagramm 28 Null-Elemente an den Stapel zurückgeben können. Diese werden (verbunden mit Stapelknoten) über dem nächsten Teildiagramm gestapelt, das tatsächlich ein Element an den Stapel zurückgibt, um das entsprechende Argument für die zur Debatte stehende Anweisung zu bilden.
Falls vielfache Argumente für die zur Debatte stehende Anweisung erforderlich sind, werden sie in der richtigen Reihenfolge gestapelt, um das Endargument zu bilden. Falls nur ein Stapelargument erforderlich ist, ist das Teildiagramm, das ein derartiges Stapelargument darstellt, das endgültige Argument. In jedem Fall wird das Anwendungscodediagramm 28 gebildet, indem ein Anwendungsknoten mit der Anweisung auf der linken Seite und dem Argument auf der rechten Seite konstruiert wird. Falls keine Stapelargumente erforderlich sind, ist die zur Debatte stehende Anweisung selbst das Ergebnis.
Falls die zur Debatte stehende Anweisung mehr als ein Element an den Stapel zurückgibt, werden Aliasknoten über dem Anwendungsknoten nach Bedarf gestapelt.
Zuletzt wird der Rest von dem ursprünglichen Codediagramm 28 (nachdem die erforderlichen Argumente extrahiert worden sind), falls vorhanden, unter dem Anwendungsergebnis gestapelt, um das Codediagramm 28 für die Anweisungen zu bilden, die bisher von Beginn des Basisblocks 24 an verarbeitet wurden.
Wenn die Codediagramme 28 für vielfache Basisblöcke 24 entlang eines Pfades kombiniert werden, um ein einziges Codediagramm 28 zu bilden, wird der Prozess als Anwendung des Codediagramms 28 beschrieben, die den Nachfolger-Basisblock 24 für das Codediagramm 28 darstellt, welches den Vorgänger-Basisblock 24 darstellt. Der Prozess beginnt wie oben mit einem leeren Argumentdiagramm. Dann wird das Codediagramm 28 von jedem Basisblock 24 in Folge angewendet, Vorgänger zu Nachfolger, wie hier beschrieben. Der Prozess ist ähnlich wie der oben beschriebene. Jedes Codediagramm 28 wird von rechts nach links durchgesehen, entsprechend der Reihenfolge des Erscheinens der Anweisungen in dem Basisblock 24, aus welchem das Codediagramm 28 generiert wurde. Jede Anweisung, auf die bei der Durchsicht gestoßen wird, wird mit einigen Änderungen auf das Argumentdiagramm wie oben angewendet.
Wenn eine unbedingte Verzweigung angetroffen wird, wird sie einfach fallen gelassen, da die Wirkung der Ausführung entlang des Pfads, dargestellt durch die Folge der zwei involvierten Basisblöcke 24, so ist, als ob die Basisblöcke 24 benachbart wären, wobei einer in den nächsten hineinfällt ohne eine Verzweigung. Falls eine bedingte Verzweigung oder dynamische Verzweigung angetroffen wird, wird sie durch den geeigneten Testknoten ersetzt, darauf beruhend, wie die Ausführung durch die Verzweigung von dem Vorgänger-Basisblock 24 zu dem Nachfolger-Basisblock 24 fortschreiten würde. Spezieller, falls für ein Programm angenommen wird, dass es von einem BRTR (branch on true = Verzweigung bei wahr) verzweigt, ist der ersetzende Testknoten TT (test true = Test wahr). Entsprechend, falls für das Programm angenommen wird, dass es von einem solchen BRTR durchfallen wird, ist der ersetzende Testknoten TF (test false = Test falsch). Selbstverständlich gilt das Gegenteil für ein BRFL (branch on false = Verzweigung bei falsch).

Begrenzungsevaluierung

Vorzugsweise, und jetzt bezugnehmend auf die Fig. 15, führt der Übersetzer Begrenzungsevaluierung gemäß einer Liste von 'Stützen' durch (Schritt 1501). Jede Stütze kennzeichnet einen Knoten (das 'Ziel') in der grafischen Darstellung, für welche sie gilt, und einen Satz von Begrenzungen, die auf diesen Knoten angewendet werden sollen. Die Begrenzungen können eine obere Begrenzung oder eine untere Begrenzung oder beide einschließen. Für jede Stütze auf der Liste wird jeder Knoten in dem Codediagramm 28 durchgesehen (Schritt 1505). Eine Aktion wird aufgenommen, je nach der Art des Knotens und ob es der Zielknoten ist, der durch die Stütze angezeigt wird. Das Codediagramm 28 wird als eine Durchquerung eines umspannenden Baums vbn rechts nach links durchgesehen, definiert auf der grafischen Darstellung 28 unter Ignorieren von Aliasknoten und Verbindungen. Beachten Sie, dass Stapelknoten und direkte (Selektor 1) Aliasknoten niemals Ziele einer Stütze sind.
Falls der Knoten, der gerade untersucht wird, das Ziel der Stütze ist, dann muss es entweder ein Anwendungsknoten (Anwendung einer Anweisung auf Argumente) oder einfach eine Anweisung sein, welche keine Argumente aufgreift. Letzterer Fall ist uninteressant und erfordert keine weitere Aktion, außer dass die Begrenzungen aktualisiert werden, wie unten beschrieben. Für einen Anwendungsknoten werden die angrenzende Anweisung und seine Argumente untersucht, um zu bestimmen, ob Begrenzungsinformationen (in der Stütze), die auf den Anwendungsknoten aufzuerlegen sind, kombiniert werden können mit welchen Begrenzungsinformationen auch immer, die bereits für die Argumente verfügbar sein können. Vielversprechend können solche Kombinationen verwendet werden, um bessere Begrenzungsinformationen für ein oder mehrere der Argumente bereitzustellen (Schritt 1507).
Zum Beispiel kann eine Anwendung von einem Paar von Argumenten, von denen eines einige Begrenzungsinformationen besitzt, auf eine ADD-Anweisung (mit einigen Begrenzungen, die dem Ergebnis auferlegt sind) ermöglichen, dass einige Begrenzungsinformationen über das andere Argument abgeleitet werden. Ähnlich können für eine arithmetische Vergleich-Anweisung, falls für das Ergebnis des Vergleichs bekannt ist, dass es wahr ist (obere und untere Begrenzung = 1) und eines der Argumente ein Literal oder selbst ein teilweise begrenzter Ausdruck ist, einige Begrenzungsinformationen für das andere Argument abgeleitet werden. Falls irgendeine neue Begrenzungsinformation abgeleitet werden kann, werden Stützen, die solche Begrenzungsinformationen enthalten, für die Argumentknoten nach Bedarf generiert und zu der Liste für eine schließliche Verarbeitung hinzugefügt (Schritt 1511). Die Begrenzungsinformationen für den Zielknoten werden von der Stütze geändert/aktualisiert (Schritt 1509), und die Durchsicht zieht sich zurück auf den Anwendungsknoten oder Stapelknoten, der auf das Ziel verweist.
Falls der Knoten, der gerade untersucht wird, nicht das Ziel ist, hängt die aufgenommene Aktion von dem Knoten-Typ ab. Für einen Stapelknoten wird die Durchsicht durch Untersuchen der linken Seite des Stapelknotens und dann der rechten Seite ausgeführt. Falls der Knoten, der gerade untersucht wird, ein direkter (Selektor 1) Knoten ist, und der Knoten, der durch eine Aliasverbindung angezeigt wird, das Ziel ist, werden Begrenzungsinformationen auf den Alias selbst von der Stütze aktualisiert.
Falls der Knoten, der gerade untersucht wird, kein Ziel ist und es ein Anwendungsknoten ist, wird die aufgenommene Aktion von der linken Seite des Anwendungsknotens abhängen. Falls die linke Seite ein Testknoten ist und es sich um die anfängliche Durchsicht handelt (es gibt keine Stütze), wird eine Stütze für sein Argument mit Begrenzungen abhängig von dem Testknoten generiert (wobei untere und obere Begrenzung die gleichen sind) Ein Test wahr wird Begrenzungen von 1 verursachen, ein Test falsch wird Begrenzungen von 0 verursachen, und ein Testindex wird Begrenzungen gleich dem Index verursachen, der in dem Testknoten angezeigt wird. Für einen Anwendungsknoten, der nicht das Ziel ist und nicht einen Testknoten anwendet, wird die Durchsicht bei dem Argument für den Anwendungsknoten fortgesetzt.
In allen Fällen werden Begrenzungsänderungen nach oben durch das Diagramm verfolgt, so wie die Durchsicht sich zurückzieht. Das heißt, falls sich Begrenzungsinformationen in dem Argument für einen Anwendungsknoten ändern, werden diese Informationen in Verbindung mit der Definition der Anweisung verwendet, die gerade angewendet wird, um das Ergebnis (den Anwendungsknoten selbst) der Anwendung zu aktualisieren. Falls der Anwendungsknoten außerdem das Ziel einer Aliasverbindung ist, wird eine Stütze für den Anwendungsknoten generiert, so dass der Alias selbst schließlich aktualisiert werden wird.
Begrenzungsänderung/-aktualisierung für einen Knoten ist nur zulässig, um den Bereich einzuengen (die obere Begrenzung abzusenken oder die untere Begrenzung anzuheben). Falls die obere und untere Begrenzung als Ergebnis zueinander im Widerspruch stehen (untere Begrenzung > obere Begrenzung), werden alle Begrenzungsinformationen für den Knoten verworfen. Es wird dann angenommen, dass dieser widersprüchliche Knoten nicht zur umfassenden Bestimmung der Ziele der dynamischen Verzweigung beitragen wird.
Vorzugsweise findet die erste Durchsicht des Diagramms 28 mit einer leeren Stütze statt, nur für die Zwecke, Stützen für Testknoten zu akkumulieren (Schritt 1503). Beachten Sie, dass eine normale Diagrammkonstruktion alle Begrenzungsinformationen verwenden wird, die von Argumenten verfügbar sind, um die anfänglichen Begrenzungen für eine Anweisungsanwendung zu bestimmen. Falls ein Diagramm keine Testknoten enthält, wird seine Konstruktion bereits alle Begrenzungsinformationen geliefert haben.
Da der Begrenzungsevaluierungsprozess nur zum Zwecke der Bestimmung der möglichen Ziele einer dynamischen Verzweigung ist, ist es vorzuziehen, jede Anweisung zu ignorieren, die nicht zu dieser Bestimmung beiträgt. Wie erkannt werden sollte, gibt es einen Satz von Anweisungen, welche Compiler zum Begrenzen (Vergleiche, bedingte Verzweigungen usw.) und Normalisieren (Addition und Subtraktion von Literalen) verwenden, oder für die Compiler erkennen, dass sie inhärent begrenzte Ergebnisse haben. Alle anderen Anweisungen können ignoriert werden.
Die Anweisungen mit inhärent begrenzten Ergebnissen umfassen die Literale, Vergleiche (entweder null oder eins ergebend) und alle anderen Anweisungen, deren Ergebnis als eine begrenzte Zahl von Bits ausgedrückt wird. Die Begrenzungsinformationen werden während der normalen Diagrammkonstruktion angehängt.
Sowohl die normale Diagrammkonstruktion als auch die Verfolgung von Begrenzungsinformationen nach oben, wenn sich die Diagrammdurchsicht zurückzieht, versuchen, nützliche Begrenzungen durch Untersuchen von Knotenargumenten herzuleiten, wobei solche Begrenzungen für eine Anwendung einer Anweisung auf ihre Argumente sind. Dieser Prozess umfasst als einen degenerierten Fall die Anwendung einer Anweisung auf Literalargumente, aber Anwendungen dieser Natur werden allgemein auch umgebogen zu Konstanten. Der nützliche Satz von Anweisungen umfasst ADD/SUBT, MULT, arithmetische Vergleiche, AMIN/AMAX, bestimmte Bitanpassungsanweisungen und die logischen Anweisungen.
Für jeden vorhandenen Knoten muss der Prozess enden, wenn die Begrenzungen konvergieren, da der Bereich niemals erweitert wird. An diesem Punkt wird die Analyse dieses Knotens keine weiteren Stützen generieren. Das Codediagramm 28 ist endlich und fest, so dass der Gesamtprozess enden wird.

Bestimmung des Verzweigungstyps

Wenn alle möglichen Quellen für eine bestimmte dynamische Verzweigung untersucht worden sind, ist das Ergebnis eine Sammlung von Pfaden, jeder mit irgendeinem Hinweis, welche Art von Quelle gefunden wurde. Dabei kann es sich um folgendes handeln:
eine arithmetische Quelle, vollständig begrenzt, als der alleinige Pfad, was auf eine Verzweigungstabelle hinweist;
ein VALC, vollständig oder teilweise begrenzt, als der alleinige Pfad, was auf einen lokalen variablen endlichen Zustandsautomaten hinweist;
ein konstanter ganzzahliger Wert, einer von mehreren, was auf einen endlichen Top-on-stack-Zustandsautomaten hinweist;
ein explizierter PCW-Verweis, entweder NAMC oder MPCW, als der alleinige Pfad; oder
unbekannt - der Pfad endet ohne eine erkennbare Quelle, was auf eine Quersegmentrückkehr hinweist, wobei das PCW auf dem Stapel zurückgelassen wurde, bevor in das Segment 22 verzweigt wurde.
Wegen Prozeduraufrufen ist es möglich, eine Mischung von konstantem ganzzahligen Wert, explizitem PCW und unbekannten Fällen zu erhalten. Wo dies vorkommt, werden die unbekannten Fälle verworfen. Falls es konstante ganzzahlige Fälle gibt, werden die PCW-Hinweise verworfen.

BEISPIEL

Es wird angenommen, dass die folgenden drei Blöcke 24 nacheinander in einem Programm 20 ablaufen, wobei der letzte Block 24 in einer dynamischen Verzweigung endet:

Block 1:

VALC A (Wert einer Variablen A holen und auf Stapel setzen)
DUPL (oberen Wert von Stapel duplizieren und auf Stapel setzen)
LT 0 (Wert 0 auf Stapel setzen)
LESS (die oberen zwei Werte von Stapel verbrauchen und vergleichen, um zu bestimmen (tatsächlich, ob A kleiner als null ist), Vergleichsergebnis auf Stapel setzen)
BRTR (oberen Wert von Stapel und darauf beruhende Verzweigung verbrauchen, oder sonst durchfallen)

Block 2:

DUPL
LT 10
GTRT (obere zwei Werte von Stapel verbrauchen und vergleichen, um zu bestimmen (tatsächlich, ob A größer als 10 ist), Vergleichsergebnis auf Stapel setzen)
BRTR

Block 3:

LT 50 (vorher definierten Offsetwert 50 auf den Stapel setzen)
ADD (die oberen zwei Werte von Stapel verbrauchen und addieren, Ergebnis auf Stapel setzen)
DBUN (oberen Wert von Stapel verbrauchen und als Adresse für dynamische Verzweigung verwenden)
Entsprechend wird in Block 1 der Wert A geprüft, um zu sehen, ob er außerhalb der Begrenzungen am unteren Ende liegt (d. h. kleiner null ist), und in Block 2 wird der Wert A geprüft, um zu sehen, ob er außerhalb der Begrenzungen am oberen Ende liegt (d. h. größer zehn ist). Falls er außerhalb der Begrenzungen auf beiden Enden liegt, verzweigt das Programm 20 anderswohin; ansonsten fällt das Programm durch zu Block 3, wo der Wert A durch einen vorher definierten Offsetwert verschoben wird, und das Ergebnis wird als die Adresse einer dynamischen Verzweigung zu einer Verzweigungstabelle verwendet, die hier nicht angegeben ist. Wie verstanden werden sollte, entsprechen die Blöcke 1-3 grob den Blöcken E, F und G in der Fig. 4.
Vermutlich wird der Übersetzer 10 beim Analysieren des Programms 20 mit den oben angegebenen Blöcken die dynamische Verzweigung in Block 3 ausfindig machen, und wird schließlich diese dynamische Verzweigung untersuchen, um das CFG 26 vollständiger zu definieren, wie oben besprochen wurde. Dabei wird der Übersetzer 10 Codediagramme 28 für jeden der Blöcke 1-3 konstruieren (unter anderem), wie in der Fig. 11A-Fig. 11C jeweils gezeigt wird. Der Übersetzer 10 wird dann alle entsprechenden Codediagramme 28 analysieren, in einem Versuch alle möglichen Werte zu definieren, die für die DBUN-Anweisung bereitgestellt werden können.
Es kann sehr gut der Fall sein, dass andere Blöcke 24 ebenfalls zu der in dem vorliegenden Beispiel zur Debatte stehenden dynamischen Verzweigung fließen. In diesem Fall wird der Übersetzer diese anderen Blöcke 24 bei Bedarf analysieren. Jedoch wird das vorliegende Beispiel der Einfachheit halber den Schwerpunkt nur auf die Blöcke 1-3 legen.
Hier, und bezugnehmend jetzt auf die Fig. 14, beginnt die Analyse durch den Übersetzer 10 damit, dass er bemerkt, dass in dem Block mit der dynamischen Verzweigung (Block 3) Informationen über einen benötigten Wert zur Berechnung der Verzweigungsadresse von woanders her geliefert wird (d. h. von einem vorhergehenden Block in dem Ablauf des Programms 20) oder ansonsten unzureichend definiert ist (Schritt 1401). Solche Informationen über den benötigten Wert werden durch den 'missing'- Knoten am unteren Rand von Fig. 11C dargestellt.
Um Informationen für diesen Knoten für ein fehlendes Argument zu erhalten, schaut der Übersetzer 10 auf den unmittelbar vorhergehenden Block 24, welcher Block 2 ist, wie in der Fig. 11B gezeigt, wie bestimmt werden kann durch Überprüfen des CFG 26, das Block 3 einschließt (Schritt 1403). Insbesondere konstruiert der Übersetzer 10 ein neues Codediagramm 28, das die Codediagramme 28 für beide Blöcke 3 und 2 (Fig. 11C und Fig. 11B) aufweist (Schritt 1405). Wie in der Fig. 12 gezeigt ist, ersetzt der Übersetzer 10 den 'missing'-Knoten am unteren Rand des Codediagramms 28 für Block 3 (Fig. 11C) mit dem Stapelknoten am oberen Rand des Codediagramms 28 für Block 2 (Fig. 11B) und alle anderen Knoten, die von diesem Stapelknoten abgehen. Zusätzlich macht der Übersetzer 10 den BRTR-Knoten in dem Codediagramm 28 für Block 2 (Fig. 11B) ausfindig und ersetzt ihn durch einen Test falsch(TF)-Knoten in der Annahme, dass GRTR in dem gleichen Codediagramm 28 falsch ist, wodurch es dem Programm 20 ermöglicht wird, bei BRTR in Block 2 durchzufallen (Schritt 1407, 1409). Wäre die Annahme gemacht worden, dass das Programm 20 bei BRTR verzweigt anstatt durchzufallen, wäre ein Testwahr(TT)-Knoten statt dessen benutzt worden. Wie verstanden werden sollte, würde, falls die Anweisung BRFL (branch on false = Verzweigung bei falsch) wäre, das Gegenteil wahr sein. Wie ebenfalls gesehen wird, werden der DBUN-Knoten und der Anwendungsknoten, der an den DBUN-Knoten grenzt, als unnütz in der vorliegenden Analyse ausgelassen: Das ultimative Ziel der Analyse ist, Begrenzungsinformationen bezüglich des (jetzt obersten) Anwendungsknotens zu finden, welcher das Argument darstellt, das auf die DBUN-Anweisung angewendet wird. Der Übersetzer 10 schreitet dann voran, um das neue Codediagramm 28 durchzusehen (Schritt 1411).
Der Übersetzer 10 wird jetzt zur Kenntnis nehmen, dass in Block 2 Information über einen benötigten Wert zum Berechnen der Verzweigungsadresse immer noch von woanders her geliefert wird (d. h. von einem vorhergehenden Block in dem Ablauf des Programms 20). Solche Informationen über den benötigten Wert werden noch einmal durch den 'missing'-Knoten am unteren Rand von Fig. 11B dargestellt, und jetzt auch am unteren Rand von Fig. 12. Wichtig ist, dass jetzt, obwohl der Übersetzer 10 bis jetzt den fehlenden Wert noch nicht definiert hat, Informationen erhältlich sind, die wenigstens den Bereich eines solchen fehlenden Wertes einengen: Der fehlende Wert hat kleiner als 10 zu sein. Ansonsten könnte das Programm 20 nicht durch die Anweisung GRTR in Block 2 fallen.
Da ein 'missing'-Knoten immer noch am unteren Rand des Codediagramms 28 für die Blöcke 3 und 2 (Fig. 12) vorhanden ist, schaut der Übersetzer 10 noch einmal auf den unmittelbar vorhergehenden Block 24, welcher Block 1 ist, wie in der Fig. 11A gezeigt, wie wieder einmal durch Überprüfen des CFG 26 (das die Blöcke 3 und 2 umfasst) bestimmt werden kann. Insbesondere konstruiert der Übersetzer 10 noch einmal ein neues Codediagramm 28, das die Codediagramme 28 für die Blöcke 3, 2 und 1 (Fig. 11C -Fig. 11A) aufweist. Insbesondere, und wie in der Fig. 13 gezeigt, ersetzt der Übersetzer 10 den Knoten für ein fehlendes Argument am unteren Rand des Codediagramms 28 für die Blöcke 3 und 2 (Fig. 12) mit einem Stapelknoten am Kopf des Codediagramms 28 für Block 1 (Fig. 11A) und alle anderen Knoten, die von diesem Stapelknoten abgehen. Zusätzlich ersetzt der Übersetzer 10 noch einmal den Knoten BRTR in dem Codediagramm 28 für Block 2 (Fig. 11B) mit einem Test falsch (TF)-Knoten in der Annahme, dass LESS in dem gleichen Codediagramm 28 falsch ist, wodurch es dem Programm 20 ermöglicht wird, bei BRTR in Block 1 durchzufallen. Wie außerdem gesehen werden kann, ist der Aliasknoten von der Fig. 11B und Fig. 12 angepasst worden, an den Knoten VALC von der Fig. 11A zu grenzen, da der Wert, der letztlich stellvertretend dargestellt wird, sich von diesem VALC-Knoten ableitet. Weiter ist jeder Aliasknoten und jeder Stapelknoten zum Zwecke der Beschreibung unten einzeln identifiziert worden.
Wieder wird der Übersetzer 10 zur Kenntnis nehmen, dass in Block 1 ein benötigter Wert zum Berechnen der Verzweigungsadresse immer noch von woanders her geliefert wird (d. h. von einem vorhergehenden Block in dem Ablauf des Programms 20). Jedoch wird in diesem Fall dieser benötigte Wert durch den VALC- Knoten am unteren Rand von der Fig. 11C dargestellt, und jetzt außerdem am unteren Rand von der Fig. 13. Wichtig ist, dass jetzt, obwohl der Übersetzer 10 bis jetzt den benötigten Wert noch nicht definiert hat, zusätzliche Informationen verfügbar sind, die wenigstens den Bereich dieses benötigten Wertes einengen: Dieser benötigte Wert hat größer als 0 zu sein. Ansonsten könnte das Programm 20 nicht durch die Anweisung GRTR in Block 1 fallen.
Darüber hinaus braucht sich der Übersetzer 10 jetzt, da er weiß, dass der benötigte Wert größer als 0 und kleiner als 10 ist, selbst nicht weiter mit dem exakten Wert des benötigten Werts zu beschäftigen. Daher die Unterscheidung zwischen 'benötigtem Wert' und 'Informationen über einen benötigten Wert'. Aber es ist einfach genug zu wissen, dass der benötigte Wert eine gesetzte obere Begrenzung und eine gesetzte untere Begrenzung hat, wenigstens gemäß dem Pfad, der durch die Blöcke 1-3 dargestellt wird. Signifikanter Weise wäre dies wahr, selbst wenn der zuvor genannte VALC-Knoten statt dessen ein weiterer Knoten für ein fehlendes Argument wäre. Natürlich müssten, falls andere Pfade existierten, solch andere Pfade von dem Übersetzer 10 mit der Möglichkeit durchgesehen werden, dass diese anderen Pfade breitere Begrenzungen hervorrufen würden.
Sobald die breitesten Begrenzungen des Knotens für ein fehlendes Argument am unteren Ende des Codediagramms 28 von Block 3 definiert worden sind, kann der Übersetzer 10 den Bereich von Adressen berechnen, die für die dynamische Verzweigung (DBUN) in diesem Block 3 präsentiert werden können. Falls dieser Knoten für ein fehlendes Argument Werte zwischen 0 und 10 annehmen kann, und da der Literalwert, der auf dem Stapel abgelegt ist, 50 ist, wird insbesondere dann die Anweisung ADD einen Wert zwischen 50 und 60 auf den Stapel zurückgeben. Ein solcher Wert zwischen 50 und 60 ist dann der Bereich von Adressen, die für die dynamische Verzweigung präsentiert werden, und beruhend auf diesen Informationen kann der Übersetzer 10 eine zugeordnete Verzweigungstabelle ausfindig machen, und kann dadurch das CFG 26 entsprechend aktualisieren.
Dabei kann es sehr gut der Fall sein, dass zuvor unerreichbare Blöcke 24 jetzt erreichbar sind. Solche neu erreichbaren Blöcke 24 werden dann selbstverständlich als aktiv markiert. Es könnte außerdem der Fall sein, dass solche neuen aktiven Blöcke 28 eine oder mehrere dynamische Verzweigungen enthalten, welche durch den Übersetzer 10 analysiert werden müssten.
Während das vorliegende Beispiel in narrativer Form so weit analysiert worden ist, versteht es sich, dass der Übersetzer 10 einen Algorithmus einsetzt, um die Analyse zu bewerkstelligen, wobei der Übersetzer 10 (über die zuvor genannten Stützen) versucht, Begrenzungsinformationen unter ein Codediagramm 28 zu drücken und außerdem, Änderungen in diesem Codediagramm 28 nach oben fortzupflanzen. Einleitend sollte verstanden werden, dass ein solcher Algorithmus auf dem Codediagramm 28 für den Block ausgeführt wird, der die dynamische Verzweigung aufweist (Block 3 in diesem Beispiel). Falls die Ergebnisse nicht schlüssig sind, greift der Übersetzer 10 zurück in dem CFG 26 und analysiert kombinierte Codediagramme 28 (wie solche in der Fig. 12 und Fig. 13), bis schlüssige Ergebnisse erhalten werden. Der Klarheit wegen wird deshalb die vorliegende Analyse den Schwerpunkt jetzt auf das Codediagramm legen, das in Fig. 13 gezeigt wird.
Einleitend durchquert der Übersetzer 10 das Diagramm in Richtung des unteren Randes des Codediagramms 28, um Anwendungsknoten zu suchen, deren Anweisungen (d. h. darunter und links davon) 'interessant' sind. Hier werden nur Testknoten als interessant betrachtet. Dabei nimmt der Übersetzer 10 die Existenz des oberen TF-Knotens und des unteren TF-Knotens zur Kenntnis. Der Übersetzer 10 wählt dann einen der interessanten Knoten für eine Untersuchung aus. Angenommen, der untere TF- Knoten wird als erstes ausgewählt, dann beginnt der Übersetzer 10 die Untersuchung von diesem unteren TF-Knoten, indem er erkennt, dass der Anwendungsknoten (a6), welcher das Argument für den TF-Knoten ist (d. h. rechts davon), falsch (0) sein muss, um einen solchen TF-Knoten zu erfüllen. Der Übersetzer hängt deshalb Begrenzungsinformationen an a6 an, mit der Wirkung, dass a6 eine obere und untere Begrenzung von 0 hat.
Der Übersetzer 10 erkennt dann, dass er die Anweisung (das LESS darunter und links davon) und das Argument (der 0-Knoten und der a7-Knoten, abhängig vom Stapelknoten s5 darunter und rechts davon) von a6 untersuchen muss. Dabei erkennt der Übersetzer 10, dass a7 größer als 0 sein muss, um den LESS- Knoten zu erfüllen. Der Übersetzer 10 hängt deshalb Begrenzungsinformationen an a7 an, mit der Wirkung, dass a7 eine untere Begrenzung von 0 und eine unbekannte obere Begrenzung hat.
Jetzt, da der Übersetzer 10 erkennt, dass a7 die Anwendung der Anweisung DUPL (Duplikation) auf das Argument VALC (ein undefinierter Wert) ist, erkennt der Übersetzer 10 weiter, dass VALC die gleichen Knoteninformationen haben muss wie a7. Der Übersetzer 10 hängt deshalb Begrenzungsinformationen an VALC an, mit der Wirkung, dass VALC eine untere Begrenzung von 0 und eine unbekannte obere Begrenzung hat.
Als nächstes erkennt der Übersetzer 10, dass auf VALC durch den unteren Aliasknoten verwiesen wird, welcher von Stapelknoten s4 wegführt (sowie durch den oberen Aliasknoten, welcher von einem Stapelknoten s2 wegführt). Da der Stapelknoten s4 zu einem Anwendungsknoten a5 führt, der das Ergebnis einer TF-Anweisung ist, erkennt der Übersetzer, dass er a5 ignorieren kann, und dass s4 die gleichen Knoteninformationen haben muss wie VALC. Der Übersetzer hängt deshalb Begrenzungsinformationen an s4 an, mit der Wirkung, dass s4 eine untere Begrenzung von 0 und eine unbekannte obere Begrenzung hat. Aus den gleichen Gründen hängt der Übersetzer 10 ähnlich Begrenzungsinformationen an s2 an, mit der Wirkung, dass s2 eine untere Begrenzung von 0 und eine unbekannte obere Begrenzung hat.
Der Übersetzer 10 beginnt dann die Untersuchung des oberen TF-Knotens, indem er erkennt, dass der Anwendungsknoten (a3), welcher das Argument für den TF-Knoten ist (d. h. rechts davon), falsch (0) sein muss, um diesen TF-Knoten zu erfüllen. Der Übersetzer hängt deshalb Begrenzungsinformationen an a3 an, mit der Wirkung, dass a3 eine untere und eine obere Begrenzung von 0 hat.
Der Übersetzer 10 erkennt dann, dass er die Anweisung (das GRTR darunter und links davon) und das Argument (den 10-Knoten und den a4-Knoten, abhängig von dem Stapelknoten s3 darunter und rechts davon) von a3 untersuchen muss. Dabei erkennt der Übersetzer 10, dass a4 kleiner als 10 sein muss, um den GRTR-Knoten zu erfüllen. Der Übersetzer 10 hängt deshalb Begrenzungsinformationen an a4 an, mit der Wirkung, dass a4 eine obere Begrenzung von 10 und eine unbekannte untere Begrenzung hat.
Jetzt, da der Übersetzer 10 erkennt, dass a4 die Anwendung der Anweisung DUPL (Duplikation) auf den Stapelknoten s4 ist, erkennt der Übersetzer 10 weiter, dass s4 die gleichen Knoteninformationen haben muss wie a7. Da s4 bereits Begrenzungsinformationen hat (untere Begrenzung unbekannt, obere Begrenzung 10), aktualisiert der Übersetzer darüber hinaus deshalb die Begrenzungsinformationen von s4, mit der Wirkung, dass s4 eine untere Begrenzung von 0 und eine obere Begrenzung von 10 hat.
Als nächstes erkennt der Übersetzer 10 wieder, dass auf VALC durch den unteren Aliasknoten verwiesen wird, welcher von s4 wegführt, und das der obere Aliasknoten, welcher von Stapel s2 wegführt, ebenfalls auf VALC zeigt. Der Übersetzer 10 erkennt dann, dass VALC, s2 und s4 alle die gleichen Begrenzungsinformationen haben müssen, und aktualisiert deshalb die Begrenzungsinformationen von s2, mit der Wirkung, dass s2 eine untere Begrenzung von 0 und eine obere Begrenzung von 10 hat.
Der Übersetzer 10 erkennt dann, dass er die Anweisung (das ADD darunter und links davon) und das Argument (den 50-Knoten und den s2-Knoten, abhängig von dem Stapelknoten s3 darunter und rechts davon) von al untersuchen muss. Dabei erkennt der Übersetzer 10, dass das Ergebnis der ADD-Anweisung sein wird, was auch immer durch Stapelknoten s2 dargestellt wird, plus 50. Da s2 eine untere Begrenzung von 0 und eine obere Begrenzung von 10 hat, hängt dann der Übersetzer 10 deshalb Begrenzungsinformationen an a1 an, mit der Wirkung, dass a4 eine untere Begrenzung von 50 und eine obere Begrenzung von 60 hat.
Diese Begrenzungen für a1 von 50 und 60 sind dann der Bereich von Adressen, die der dynamischen Verzweigung präsentiert werden, und beruhend auf diesen Informationen kann der Übersetzer 10 eine zugeordnete Verzweigungstabelle ausfindig machen und kann dadurch das CFG 26 entsprechend aktualisieren.
Beachten Sie aus dem vorliegenden Beispiel, dass, falls der Übersetzer 10 die Begrenzungen von einer dynamischen Verzweigung zu eng definiert, Verzweigungstabellen-Informationen fehlen werden und das CFG 26 unvollständig sein wird. Falls jedoch der Übersetzer 10 die Begrenzungen von einer dynamischen Verzweigung zu breit definiert, werden keine Verzweigungstabellen-Informationen fehlen und das CFG 26 wird nicht unvollständig sein. Stattdessen können Informationen in der Nähe einer Verzweigungstabelle falsch interpretiert werden als Verzweigungstabellen- Informationen, und das CFG 26 wird möglicherweise mit harmlosem Abfall aktualisiert. Vorzugsweise wird daher der Übersetzer 10 erkennen, dass solche angrenzenden Informationen nicht wie ein Teil einer Verzweigungstabelle aussehen, und wird solche angrenzenden Informationen ignorieren.
Selbstverständlich gibt es viele Variationen und Abkürzungen. Zum Beispiel, falls der Pfad zurück von einer ersten dynamischen Verzweigung zu einer zweiten dynamischen Verzweigung führt, wird diese zweite dynamische Verzweigung in einem neuen Codediagramm (nach Fig. 12 oder Fig. 13) durch den Übersetzer 10 vorzugsweise mit einem Testindex-Knoten ersetzt, der den notwendigen Wert hat, um in Richtung der ersten dynamischen Verzweigung durchzufallen.
Falls der Übersetzer 10 auf einen benötigten Wert trifft und weiß, dass der benötigte Wert zum Beispiel vier Bit breit ist (0-15), kann der Übersetzer 10 auf eine Codediagrammanalyse verzichten und statt dessen annehmen, dass der benötigte Wert zwischen 0 und 15 ist.
Falls der Übersetzer 10 beim Durchsehen eines Codediagramms 28 auf einen Prozeduraufruf trifft, taucht Unbestimmtheit auf, da ein derartiger Prozeduraufruf entweder ein Ergebnis oder keines auf den Stapel zurückgeben kann. Der Prozeduraufruf kann nicht verfolgt werden, da sein Ort bis zur Laufzeit nicht bestimmt werden kann. In diesem Fall, falls nichts weiteres bekannt ist darüber, was der Prozeduraufruf zurückgibt, untersucht der Übersetzer 10 vorzugsweise die Wirkung beider Fälle (null oder ein Ergebnis auf dem Stapel), vergleicht die Wirkungen und wählt, was auch immer konsistent mit dem Kontext ist. Oftmals wird die Wahl klar sein.
Gelegentlich wird der Übersetzer 10 auf eine dynamische Verzweigung ohne irgendwelchen zugeordneten begrenzenden oder verschiebenden Code treffen. Statt dessen wird auf die dynamische Verzweigung von mehreren unterschiedlichen Blöcken 24 zugelaufen, die jeweils lediglich einen vorher definierten Adresswert auf dem Stapel für die dynamische Verzweigung speichern, um darauf hinzuwirken. In solch einem Fall ist sich der Übersetzer vorzugsweise bewusst, dass er wahrscheinlich auf einen endlichen Zustandsautomaten gestoßen ist. In diesem Automaten geht die dynamische Verzweigung nicht zu einer Verzweigungstabelle, sondern direkt zu mehreren anderen Blöcken 24, die jeweils wahrscheinlich Teil eines solchen Automaten sind. Der Übersetzer 10 braucht dann nur die Codediagramme 28 von allen Pfaden durchzusehen, die zu der dynamischen Verzweigung führen, in dem Ausmaß, der notwendig ist, um die Welt spezifischer Adressen zu erhalten, auf die durch diese dynamische Verzweigung hingewirkt werden kann.
In der vorhergehenden Beschreibung kann gesehen werden, dass die vorliegende Erfindung ein neues und nützliches Verfahren und einen Übersetzer zum Übersetzen kompilierter Programmiercodes von einem ersten Codezustand in einen zweiten Codezustand umfasst. Es sollte richtig eingeschätzt werden, dass Änderungen an den oben beschriebenen Ausführungsformen gemacht werden könnten, ohne von deren erfinderischen Konzepten abzuweichen. Es versteht sich deshalb, dass diese Erfindung nicht auf die einzelnen offenbarten Ausführungsformen begrenzt ist, sondern es ist beabsichtigt, Modifikationen innerhalb des Schutzumfangs der vorliegenden Erfindung abzudecken, wie durch die anliegenden Ansprüche definiert wird.

Claims

1. Ein Verfahren zum Übersetzen von kompiliertem Programmiercode (20) von einem ersten Codezustand (12) in einen zweiten Codezustand (14), wobei der Programmiercode in dem ersten Codezustand eine Vielzahl von. Basisblöcken (24) umfasst, wobei jeder Basisblock einen Satz von Anweisungen umfasst, wobei mindestens ein Basisblock in einer dynamischen Verzweigung endet, wobei die dynamische Verzweigung eine Übergabe ist an ein Ziel von einem Satz von Zielen, beruhend auf einer Berechnung einer Zieladresse, wobei das Verfahren die folgenden Schritte umfasst:

Identifizierung der Vielzahl von Basisblöcken in dem ersten Codezustand des Programmiercodes;

Identifizierung von Verbindungen zwischen den identifizierten Basisblöcken;

Konstruktion eines Steuerflussdiagramms/Darstellung (CFG) (26) des Programmiercodes beruhend auf den identifizierten Basisblöcken und den identifizierten Verbindungen, wobei das CFG von einer vorläufigen Form ist;

Identifizierung von mindestens einem Basisblock, der in einer dynamischen Verzweigung endet;

beruhend auf dem CFG Untersuchung aller identifizierter Basisblöcke, die zu der dynamischen Verzweigung führen, so weit zurück, wie notwendig ist, um einen Satz von Zieladressen für die dynamische Verzweigung vollständig zu bestimmen, wobei der Satz von Zieladressen den Satz von Zielen von der dynamischen Verzweigung definiert;

Prüfen des Satzes von Zielen, um eine Verzweigungstabelle zu identifizieren;

Aktualisieren des CFG, um den Satz von Zielen und die identifizierte Verzweigungstabelle widerzuspiegeln;

Übersetzen des Programmiercodes von dem ersten Codezustand in den zweiten Codezustand mindestens teilweise beruhend auf dem aktualisierten CFG.

2. Das Verfahren nach Anspruch 1, worin der Untersuchungsschritt die folgenden Schritte umfasst:

für jeden untersuchten Basisblock Konstruktion eines entsprechenden Codediagramms/Darstellung (Codediagramm) der Anweisungen in einem solchen Basisblock; und

Durchsehen jedes Codediagramms, um den Satz von Zieladressen von der dynamischen Verzweigung zu bestimmen.

3. Das Verfahren nach Anspruch 2, worin jedes Codediagramm ein gerootetes gerichtetes azyklisches Diagramm mit miteinander verbundenen Knoten ist, wobei jeder Knoten einer der folgenden ist:

ein Anweisungsknoten, der eine Anweisung in dem entsprechenden Basisblock darstellt;

ein Argumentknoten, der ein Argument in dem entsprechenden Basisblock darstellt;

ein Anwendungsknoten, der an einen Anweisungsknoten und an einen Argumentknoten grenzt und der die Anwendung eines solchen Argumentknotens auf diesen Anweisungsknoten darstellt, wobei der Anwendungsknoten in bestimmten Fällen auch ein Argumentknoten ist, an dem ein anderer Knoten grenzt;

ein Stapelknoten, der an ein Paar von Argumentknoten grenzt und der als ein Argumentknoten wirkt, der das Paar von Argumentknoten hat;

ein Knoten für ein fehlendes Argument, der ein fehlendes Argument darstellt, das von einem anderen Basisblock geliefert wird; und

ein Aliasknoten, an dem ein Stapelknoten oder ein Anwendungsknoten grenzt und der an ein Argument fern von diesem Stapelknoten grenzt, und der ein solches fernes Argument für diesen Stapelknoten darstellt.

4. Das Verfahren nach Anspruch 3, worin der Untersuchungsschritt die folgenden Schritte umfasst:

Feststellung, dass ein erstes Codediagramm, das einem ersten Basisblock entspricht, einen Knoten für ein fehlendes/unzureichend definiertes Argument enthält;

auf Basis des CFG Ausfindig machen eines zweiten Basisblocks, der dem ersten Basisblock unmittelbar vorausgeht, wobei ein zweites Codediagramm dem zweiten Basisblock entspricht;

Konstruktion eines neuen Codediagramms, das das erste Codediagramm und das zweite Codediagramm aufweist, indem der Knoten für das fehlende Argument in dem ersten Codediagramm mit dem zweiten Codediagramm ersetzt wird; und

Durchsehen des neuen Codediagramms in einem Versuch, den Satz von Zieladressen von der dynamischen Verzweigung zu bestimmen.

5. Das Verfahren nach Anspruch 4, worin der Untersuchungsschritt die folgenden Schritte umfasst:

in dem Abschnitt des neuen Codediagramms, der dem zweiten Codediagramm entspricht, Ausfindig machen eines Anweisungsknotens, der eine Bedingung darstellt, die erfüllt werden muss, um die Fortsetzung eines Programmflusses von dem zweiten Basisblock zu dem ersten Basisblock zu gestatten; und

Ersetzen des ausfindig gemachten Anweisungsknotens mit einem Testknoten, der die Bedingung anzeigt, die erfüllt werden muss.

6. Das Verfahren nach Anspruch 5, worin der ausfindig gemachte Anweisungsknoten repräsentativ für eine Verzweigungsanweisung ist, und die Bedingung, die erfüllt werden muss, ein logisches Wahr, ein logisches Falsch oder ein vorherbestimmter Indexwert ist.

7. Das Verfahren nach Anspruch 5, worin der Untersuchungsschritt den Schritt des Durchführens von Begrenzungsevaluierung entsprechend einer Liste von Stützen umfasst, wobei jede Stütze auf einen Zielknoten, für welchen eine solche Stütze zutrifft, und einen Satz von Begrenzungen anzeigt, die auf diesen Knoten angewendet werden sollen.

8. Das Verfahren nach Anspruch 7, worin der Schritt des Durchführens von Begrenzungsevaluierung den Schritt des Durchsehens jedes Knotens in dem Codediagramm für jede Stütze in der Liste umfasst.

9. Das Verfahren nach Anspruch 8, worin der Schritt des Durchsehens jedes Knotens für jede Stütze den Schritt des Versuchs umfasst, Begrenzungsinformationen in den Argumentknoten, an dem ein Anwendungsknoten grenzt, zu schieben, falls ein solcher Anwendungsknoten durchgesehen wird und der Zielknoten der Stütze ist.

10. Das Verfahren nach Anspruch 9, worin jeder Knoten Begrenzungsinformationen einschließt, und worin der Versuchsschritt die folgenden Schritte umfasst:

Versuch, Begrenzungsinformationen für den Argumentknoten herzuleiten, an den der Ziel-Anwedungsknoten grenzt, auf Basis dieses Argumentknotens und des Anweisungsknotens, an dem dieser Ziel-Anwendungsknoten grenzt;

falls geeignet, Ändern der Begrenzungsinformationen des Argumentknotens, an dem der Ziel-Anwendungsknoten grenzt; und

Hinzufügen einer neuen Stütze zu der Liste, falls die Begrenzungsinformationen des Argumentknotens, an dem der Ziel- Anwendungsknoten grenzt, geändert werden.

11. Das Verfahren nach Anspruch 7, worin der Schritt des Durchsehens jedes Knotens das Erzeugen einer Stütze für das Argument von jedem Testknoten beim ersten Mal umfasst, wenn auf den Testknoten gestoßen wird.

12. Das Verfahren nach Anspruch 11, worin der Schritt des Durchsehens jedes Knotens das vorläufige Durchsehen des Codediagramms mit einer leeren Stütze umfasst, die zum Ziel hat, Stützen für Testknoten zu akkumulieren.

13. Das Verfahren nach Anspruch 12, worin jeder Knoten Begrenzungsinformationen einschließt, und worin der Schritt des Durchsehens jedes Knotens das Durchschreiten des Codediagramms in einer umspannenden Richtung umfasst, und dann das Zurückverfolgen durch das Codediagramm entgegen der umspannenden Richtung, wobei der zurückverfolgende Schritt den Schritt Wiederevaluierung der Begrenzungsinformationen von jedem zurückverfolgten Knoten einschließt, wann immer sich eine Änderung der Begrenzungen ergeben könnte.

14. Ein Übersetzer (10), der auf einen Prozessor (16) einwirkt zum Übersetzen von kompiliertem Programmiercode (20) von einem ersten Codezustand (12) in einem zweiten Codezustand (14), wobei der Programmiercode in dem ersten Codezustand eine Vielzahl von Basisblöcken (24) umfasst, wobei jeder Basisblock einen Satz von Anweisungen umfasst, wobei mindestens ein Basisblock in einer dynamischen Verzweigung endet, wobei die dynamische Verzweigung eine Übergabe ist an ein Ziel von einem Satz von Zielen, auf Basis einer Berechnung einer Zieladresse, wobei der Übersetzer:

die Vielzahl von Basisblöcken in dem ersten Codezustand des Programmiercodes identifiziert;

die Verbindungen zwischen den identifizierten Basisblöcken identifiziert;

ein Steuerflussdiagramm/Darstellung (CFG) (26) des Programmiercodes konstruiert auf Basis der identifizierten Basisblöcke und der identifizierten Verbindungen, wobei das CFG von einer vorläufigen Form ist;

mindestens einen Basisblock identifiziert, der in einer dynamischen Verzweigung endet;

auf Basis des CFG alle identifizierter Basisblöcke, die zu der dynamischen Verzweigung führen, so weit zurück untersucht, wie notwendig ist, um einen Satz von Zieladressen für die dynamische Verzweigung vollständig zu bestimmen, wobei der Satz von Zieladressen den Satz von Zielen von der dynamischen Verzweigung definiert;

den Satz von Zielen prüft, um eine Verzweigungstabelle zu identifizieren;

das CFG aktualisiert, um den Satz von Zielen und die identifizierte Verzweigungstabelle widerzuspiegeln;

den Programmiercode von dem ersten Codezustand in den zweiten Codezustand übersetzt mindestens teilweise beruhend auf dem aktualisierten CFG.

15. Der Übersetzer nach Anspruch 14, wobei der Übersetzer: für jeden untersuchten Basisblock ein entsprechendes Codediagramm/Darstellung (Codediagram) der Anweisungen in diesem Basisblock konstruiert; und jedes Codediagramm durchsieht, um den Satz von Zieladressen von der dynamischen Verzweigung zu bestimmen.

16. Der Übersetzer nach Anspruch 15, wobei jedes Codediagramm ein gerootetes gerichtetes azyklisches Diagramm mit miteinander verbundenen Knoten ist, wobei jeder Knoten einer der folgenden ist:

17. Der Übersetzer nach Ansprüch 16, wobei der Übersetzer feststellt, dass ein erstes Codediagramm, das einem ersten Basisblock entspricht, einen Knoten für ein fehlendes/unzureichend definiertes Argument enthält;

beruhend auf dem CFG einen zweiten Basisblock ausfindig macht, der dem ersten Basisblock unmittelbar vorausgeht, wobei ein zweites Codediagramm dem zweiten Basisblock entspricht;

ein neues Codediagramm konstruiert, das das erste Codediagramm und das zweite Codediagramm aufweist, indem der Knoten für das fehlende Argument in dem ersten Codediagramm mit dem zweiten Codediagramm ersetzt wird; und

das neue Codediagramm durchsieht in einem Versuch, den Satz von Zieladressen von der dynamischen Verzweigung zu bestimmen.

18. Der Übersetzer nach Ansprüch 17, wobei der Übersetzer:

in dem Abschnitt des neuen Codediagramms, der dem zweiten Codediagramm entspricht, einen Anweisungsknoten ausfindig macht, der eine Bedingung darstellt, die erfüllt werden muss, um die Fortsetzung eines Programmflusses von dem zweiten Basisblock zu dem ersten Basisblock zu gestatten; und

den ausfindig gemachten Anweisungsknoten mit einem Testknoten ersetzt, der die Bedingung anzeigt, die erfüllt werden muss.

19. Der Übersetzer nach Anspruch 18, wobei der ausfindig gemachte Anweisungsknoten repräsentativ für eine Verzweigungsanweisung ist, und die Bedingung, die erfüllt werden muss, ein logisches Wahr, ein logisches Falsch oder ein vorherbestimmter Indexwert ist.

20. Der Übersetzer nach Anspruch 18, wobei der Übersetzer Begrenzungsevaluierung entsprechend einer Liste von Stützen durchführt, wobei jede Stütze einen Zielknoten, für welchen eine solche Stütze zutrifft, und einen Satz von Begrenzungen anzeigt, die auf diesen Knoten angewendet werden sollen.

21. Der Übersetzer nach Anspruch 20, wobei der Übersetzer jeden Knoten in dem Codediagramm für jede Stütze in der Liste durchsieht.

22. Der Übersetzer nach Anspruch 21, wobei der Übersetzer für jede Stütze versucht, Begrenzungsinformationen in den Argumentknoten zu schieben, an dem ein Anwendungsknoten grenzt, falls ein solcher Anwendungsknoten durchgesehen wird und der Zielknoten der Stütze ist.

23. Der Übersetzer nach Anspruch 22, wobei jeder Knoten Begrenzungsinformationen einschließt, und wobei der Übersetzer:

versucht, Begrenzungsinformationen für den Argumentknoten herzuleiten, an dem der Ziel-Anwendungsknoten grenzt, beruhend auf diesem Argumentknoten und dem Anweisungsknoten, an dem dieser Ziel-Anwendungsknoten grenzt;

falls geeignet die Begrenzungsinformationen des Argumentknotens ändert, an dem der Ziel-Anwendungsknoten grenzt; und

eine neue Stütze zu der Liste hinzufügt, falls die Begrenzungsinformationen des Argumentknotens, am dem der Ziel-Anwendungsknoten grenzt, geändert werden.

24. Der Übersetzer nach Anspruch 20, wobei der Übersetzer eine Stütze erzeugt für das Argument von jedem Testknoten beim ersten Mal, wenn auf den Testknoten gestoßen wird.

25. Der Übersetzer nach Anspruch 24, wobei der Übersetzer vorläufig das Codediagramm mit einer leeren Stütze durchsieht, die zum Ziel hat, Stützen für Testknoten zu akkumulieren.

26. Der Übersetzer nach Anspruch 25, wobei jeder Knoten Begrenzungsinformationen einschließt, und wobei der Übersetzer das Codediagramm in einer umspannenden Richtung durchschreitet, und dann das Codediagramm entgegen der umspannenden Richtung zurückverfolgt, wobei das Zurückverfolgen Wiederevaluierung der Begrenzungsinformationen von jedem zurückverfolgten Knoten einschließt, wann immer sich eine Änderung der Begrenzungen ergeben könnte.

27. In Zusammenhang mit dem Übersetzen kompilierter Programmiercodes (20) von einem ersten Codezustand (12) in einen zweiten Codezustand (14), wobei der Programmiercode in dem ersten Codezustand eine Vielzahl von Basisblöcken (24) umfasst, wobei jeder Basisblock einen Satz von Anweisungen umfasst, wobei mindestens ein Basisblock in einer dynamischen Verzweigung endet, wobei die dynamische Verzweigung eine Übergabe ist an ein Ziel von einem Satz von Zielen, beruhend auf einer Berechnung einer Zieladresse, ein Computer-lesbares Medium (17) mit Computer ausführbaren Anweisungen zum Durchführen von Schritten, die folgendes umfassen:

Identifizierung der Verbindungen zwischen den identifizierten Basisblöcken;

Prüfen des Satzes von Zielen, um eine Verzweigungstabelle zu identifizieren;

28. Das Computer-lesbare Medium nach Anspruch 27, worin der Untersuchungsschritt die folgenden Schritte umfasst:

für jeden untersuchten Basisblock die Konstruktion eines entsprechenden Codediagramms/Darstellung (Codediagramm) der Anweisungen in einem solchen Basisblock; und

29. Das Computer-lesbare Medium nach Anspruch 28, worin jedes Codediagramm ein gerootetes gerichtetes azyklisches Diagramm mit miteinander verbundenen Knoten ist, wobei jeder Knoten einer der folgenden ist:

ein Stapelknoten, der an ein Paar von Argumentknoten grenzt und als ein Argumentknoten mit dem Paar von Argumentknoten wirkt;

30. Das Computer-lesbare Medium nach Anspruch 29, worin der Untersuchungsschritt die folgenden Schritte umfasst:

beruhend auf dem CFG Ausfindig machen eines zweiten Basisblocks, der dem ersten Basisblock unmittelbar vorausgeht, wobei ein zweites Codediagramm dem zweiten Basisblock entspricht;

31. Das Computer-lesbare Medium nach Anspruch 30, worin der Untersuchungsschritt die folgenden Schritte umfasst:

in dem Abschnitt des neuen Codediagramms, der dem zweiten Codediagramm entspricht, das Ausfindig machen eines Anweisungsknotens, der eine Bedingung darstellt, die erfüllt werden muss, um die Fortsetzung eines Programmflusses von dem zweiten Basisblock zu dem ersten Basisblock zu gestatten; und

32. Das Computer-lesbare Medium nach Anspruch 31, worin der ausfindig gemachte Anweisungsknoten repräsentativ für eine Verzweigungsanweisung ist, und die Bedingung, die erfüllt werden muss, ein logisches Wahr, ein logisches Falsch oder ein vorherbestimmter Indexwert ist.

33. Das Computer-lesbare Medium nach Anspruch 31, worin der Untersuchungsschritt den Schritt de Durchführens von Begrenzungsevaluierung entsprechend einer Liste von Stützen umfasst, wobei jede Stütze einen Zielknoten, für welchen eine solche Stütze zutrifft, und einen Satz von Begrenzungen anzeigt, die auf diesen Knoten angewendet werden sollen.

34. Das Computer-lesbare Medium nach Anspruch 33, worin der Schritt des Durchführens von Begrenzungsevaluierung den Schritt des Durchsehens jedes Knotens in dem Codediagramm für jede Stütze in der Liste umfasst.

35. Das Computer-lesbare Medium nach Anspruch 34, worin der Schritt des Durchsehens jedes Knotens für jede Stütze den Schritt des Versuchs, Begrenzungsinformationen in den Argumentknoten zu schieben, an dem ein Anwendungsknoten grenzt, umfasst, falls ein solcher Anwendungsknoten durchgesehen wird und der Zielknoten der Stütze ist.

36. Das Computer-lesbare Medium nach Anspruch 35, worin jeder Knoten Begrenzungsinformationen einschließt, und worin der Versuchsschritt die folgenden Schritte umfasst:

Versuch, Begrenzungsinformationen für den Argumentknoten herzuleiten, an dem der Ziel-Anwendungsknoten grenzt, beruhend auf diesem Argumentknoten und auf dem Anweisungsknoten, an dem dieser Ziel-Anwendungsknoten grenzt

37. Das Computer-lesbare Medium nach Anspruch 33, worin der Schritt des Durchsehens jedes Knotens das Erzeugen einer Stütze für das Argument von jedem Testknoten beim ersten Mal umfasst, wenn auf den Testknoten gestoßen wird.

38. Das Computer-lesbare Medium nach Anspruch 37, worin der Schritt des Durchsehens jedes Knotens das vorläufige Durchsehen des Codediagramms umfasst, die zum Ziel hat, Stützen für Testknoten zu akkumulieren.

39. Das Computer-lesbare Medium nach Anspruch 38, worin jeder Knoten Begrenzungsinformationen einschließt, und worin der Schritt des Durchsehens jedes Knotens das Durchschreiten des Codediagramms in einer umspannenden Richtung umfasst, und dann das Zurückverfolgen durch das Codediagramm entgegen der umspannenden Richtung, wobei der zurückverfolgende Schritt den Schritt Wiederevaluierung der Begrenzungsinformationen von jedem zurückverfolgten Knotens einschließt, wann immer sich eine Änderung der Begrenzungen ergeben könnte.