DE69727453T2

DE69727453T2 - Kompilieren von prädikatiertem Code mit direkter Analyse desselben

Info

Publication number: DE69727453T2
Application number: DE1997627453
Authority: DE
Inventors: Richard C. No. E-14 Cupertino Johnson; Michael S. Schlansker
Original assignee: Hewlett Packard Co
Current assignee: Hewlett Packard Development Co LP
Priority date: 1996-11-26
Filing date: 1997-11-18
Publication date: 2005-01-13
Anticipated expiration: 2017-11-19
Also published as: DE69727453D1; US5920716A; EP0844557A1; JP4105264B2; EP0844557B1; JPH10187463A

Description

Die vorliegende Erfindung bezieht sich auf ein Programmieren von Sprachcompilern für Computersysteme. Insbesondere bezieht sich diese Erfindung auf einen Compiler zum Kompilieren eines prädizierten Codes mit einer direkten Analyse des prädizierten Codes.
Wie man weiß, umfaßt ein Computersystem in der Regel einen oder mehrere Prozessoren, die auch als Zentralverarbeitungseinheiten (CPUs) oder Mikroprozessoren bekannt sind. Der Prozessor umfaßt üblicherweise Anweisungen von Softwareprogrammen, eine Vielzahl von Aufgaben in dem Computersystem durchzuführen. Die Anweisungen der Softwareprogramme liegen in Form einer Maschinensprache (z.B. in binärer Form) vor, da der Prozessor nur Maschinensprache verstehen und interpretieren kann. Die Anweisungen in Maschinensprache werden nachfolgend als Maschinencode oder Objektcode bezeichnet.
Da die Maschinensprache sehr schwierig zu schreiben und zu verstehen ist, wurden Quellprogrammierungssprachen auf hoher Ebene (z.B. C und Fortran) entwickelt, um die Anweisungen eines Softwareprogramms in einer für Menschen lesbaren Weise zu codieren oder zu definieren. Ein derartiges Quellprogrammierungssprachsoftwareprogramm wird als Quellcode bezeichnet. Der Quellcode muß durch ein Compilerprogramm in den Maschinencode umgewandelt oder übersetzt werden, bevor er durch den Prozessor ausgeführt wird.
Die früheren Prozessoren des Standes der Technik sind in der Regel Skalarprozessoren (SISD-Prozessoren, SISD = single instruction single data). Ein SISD-Prozessor empfängt üblicherweise einen einzigen Anweisungsstrom und einen einzigen Datenstrom. Der SISD-Prozessor führt jede Anweisung nacheinander aus, wobei er Daten in einem einzigen Speicherbereich bearbeitet. Jedoch stellt diese SISD-Prozessor-Architektur ein Hindernis beim Erreichen eines hohen Verarbeitungsdurchsatzes dar.
Um den Verarbeitungsdurchsatz eines Prozessors zu erhöhen, wurden bereits viele Parallelverarbeitungsarchitekturen entwickelt. Ein Typ eines derartigen Parallelverarbeitungsmodells ist als ILP-Prozessor (ILP = instruction-level parallel, Anweisungsebene-parallel) bekannt. Bei einem ILP-Prozessor ist die grundlegende Recheneinheit (für die Zeitplanungs- und Synchronisierungsentscheidungen getroffen werden) eine Prozessoranweisung, z.B. eine einzelne Addieren-, Multiplizieren-, Laden- oder Speichern-Operation. Nicht voneinander abhängige Anweisungen werden parallel geladen und ausgeführt. Bei einer Verwendung von ILP-Prozessoren müssen während einer Programmausführung keine Anweisungszeitplanungs- oder -synchronisierungsentscheidungen getroffen werden. Manche Entscheidungen können während einer Programmkompilierunq getroffen werden. Falls der Compiler beispielsweise beweisen kann, daß zwei Operationen voneinander unabhängig sind (d.h. keine erfordert das Ergebnis der anderen als Eingabe), können die Operationen parallel ausgeführt werden.
Jedoch können häufige und unvorhersehbare Zweigoperationen in einem Programmcode eine Hauptbarriere beim Nutzen eines größeren Umfangs einer Anweisungsebene-Parallelität darstellen. Dies liegt daran, daß manche Zweigoperationen üblicherweise Zweiglatenzen oder Fehlvorhersagenachteile einbringen und somit bewirken, daß die Ausführung während der Laufzeit anhält. Ferner begrenzen Zweigoperationen üblicherweise den Zeitplanungsumfang des Codes bezüglich der Anweisungsebene-Parallelität. Die Zweigoperationen werden als Zweige bezeichnet.
Um Zweige zu eliminieren und die Anweisungsebene-Parallelität weiter zu verbessern, wurde ein neues archi tektonisches Modell vorgeschlagen, bei dem jede Prozessoroperation durch einen mit einem Booleschen Wert versehenen Quelloperand bewacht wird. Der Wert des Operanden bestimmt, ob die Operation ausgeführt oder aufgehoben wird. Dieses architektonische Modell wird als prädizierte Ausführung bezeichnet, und der mit einem Booleschen Wert versehene Quelloperand wird als Prädikat bezeichnet. Von dem Gesichtspunkt der Anweisungssatzarchitektur bestehen die Hauptmerkmale der prädizierten Ausführung darin, daß ein Prädikat jede Operation bewacht und darin, daß ein Satz von Vergleiche-Mit-Prädikat-Operationen verwendet wird, um Prädikaten zu berechnen. Die prädizierte Ausführung eliminiert üblicherweise viele Zweige vollständig und verallgemeinert die Regeln für ein Bewegen eines Codes zwischen grundlegenden Blöcken. Sehr häufig kann ein ganzer azyklischer Steuerflußteilgraph in einen einzelnen zweigfreien Codeblock umgewandelt werden.
Der Prozeß des Ersetzens von Zweigen durch entsprechende Prädikatenberechnungen und Wächter wird als Falls-Umwandlung oder Prädikatenumwandlung bezeichnet. Der sich aus der Falls-Umwandlung ergebende Code wird als prädizierter Code bezeichnet. 1A zeigt den herkömmlichen Code für ein in 1B dargestelltes Programm. 1C zeigt den von dem herkömmlichen Code der 1A umgewandelten prädizierten Code. Wie aus 1C zu sehen ist, werden explizite Zweige, die eine Ausführung steuern, bei Operationen durch wachende Prädikaten ersetzt, zusammen mit Vergleiche-Mit-Prädikat-Operationen, die die entsprechenden Prädikatenwerte berechnen. Alle Nicht-Zweig-Anweisungen werden während der Falls-Umwandlung mit den Prädikaten prädiziert. Das Ergebnis ist ein einziger zweigfreier Block eines prädizierten Codes.
Jedoch treten Probleme auf, wenn ein prädizierter Code durch einen herkömmlichen Compiler kompiliert wird. Dies liegt daran, daß die Datenflußanalysehilfsmittel von herkömmlichen Compilern beim Kompilieren des prädizierten Co des üblicherweise nicht Beziehungen zwischen Prädikaten ausnutzen. 2 zeigt einen herkömmlichen Compiler 50 zum Kompilieren des prädizierten Codes. Wie aus 2 zu sehen ist, umfaßt der Compiler 50 ein Falls-Umwandlungs-System 51, eine Zeitplaner- und Registerzuweisungseinrichtung 52 und ein Datenflußanalysesystem 53. Das Datenflußanalysesystem 53 analysiert jedoch lediglich die Datenabhängigkeit des ursprünglichen Codes und integriert in seine Datenflußanalyse keine Informationen über Beziehungen zwischen Prädikaten des prädizierten Codes. Üblicherweise veranlaßt dies das Datenflußanalysesystem 53, entweder falsche Annahmen über das Laufzeitverhalten des prädizierten Codes oder überhaupt keine Annahme zu machen, was dann in wesentlichen Bereichen wie z.B. der Zeitplanung und Registerzuweisung übermäßig konservative Ergebnisse ergibt. 3 zeigt einen konservativen Zeitplan des Codes in 1C, der durch den Compiler der 2 erzeugt wird. 3 veranschaulicht den Nachteil einer Verwendung des herkömmlichen Lösungsansatzes beim Kompilieren des prädizierten Codes.
Die Veröffentlichung „Register Allocation for Predicated Code", A.E. Eichenberger und U. Davidson, Verfahren des 28. jährlichen IEEE/ACM-Internationalen Symposiums über Mikroarchitektur, 29. November 1995 bis 1. Dezember 1995, Ann Arbor, MI, USA, Seiten 180–198, zielt darauf ab, die Registerzuweisung für einen prädizierten Code zu verbessern. Zu diesem Zweck wird ein prädizierter Code analysiert. Informationen über prädizierte Werte werden aus dem Code extrahiert, aktive Bereiche und ihre Prädikatenausdrücke werden entdeckt, und Aktivbereich-Interferenzen werden berechnet. Willkürliche-Prädiktton-Schemata und willkürliche Beziehungen zwischen Prädikaten, die Korrelationen zwischen ZFumgewandelten Zweigen umfassen, können verarbeitet werden. Die verbesserte Registerzuweisung kann entweder vor oder nach einer Zeitplanung angewandt werden.
Eine der Aufgaben der vorliegenden Erfindung besteht darin, eine Kompilierung eines prädizierten Codes zu optimieren, wie in Anspruch 13 dargelegt ist.
Eine weitere Aufgabe der vorliegenden Erfindung besteht darin, die Laufzeit-Leistungsfähigkeit eines prädizierten Codes zu verbessern, wie in den Ansprüchen 1 und 6 dargelegt ist.
Ein weiteres Merkmal der vorliegenden Erfindung besteht darin, einen Compiler zu liefern, der beim Kompilieren eines prädizierten Codes Prädikatenbeziehungen des prädizierten Codes ausnutzt, wie in Anspruch 12 dargelegt ist.
Ein weiteres Merkmal der vorliegenden Erfindung besteht darin, ein Prädikatenanfragesystem für einen Prädizierter-Code-Compiler zu liefern, das Prädikatenbeziehungen des prädizierten Codes speichert, so daß der Compiler die Prädikatenbeziehungen verwenden kann, um eine andere Datenflußanalyse an dem prädizierten Code vorzunehmen, wie sie z.B. von einer Zeitplanung, Zuweisung und Optimierung benötigt wird.
Nachfolgend wird ein Compiler für einen prädizierten Code beschrieben. Der Compiler umfaßt ein Datenflußanalysesystem, das Prädikatenausdrücke des prädizierten Codes manipuliert und anfragt, um Datenflußeigenschaften des prädizierten Codes zu analysieren.
Ferner ist auch ein prädikatenempfindlicher Analysierer für einen Compiler beschrieben, der einen prädizierten Code kompiliert. Der prädikatenempfindliche Analysierer umfaßt ein Prädikatenanfragesystem, um lokale und globale Prädikatenbeziehungen des prädizierten Codes zu speichern und um Anfragen bezüglich der lokalen und globalen Prädikatenbeziehungen zu beantworten.
Weitere Merkmale und Vorteile der vorliegenden Erfindung ergeben sich aus der folgenden ausführlichen Beschreibung, die in Verbindung mit den beigefügten Zeichnungen zu sehen ist, welche die Prinzipien der Erfindung beispielhaft veranschaulichen.
1 zeigt einen herkömmlichen Code für ein Programm;
1B zeigt den Steuerfluß des Programms;
1C zeigt den prädizierten Code (d.h. fallsumgewandelten Code) des herkömmlichen Codes der 1A;
2 zeigt einen bekannten Prädizierter-Code-Compiler;
3 zeigt den prädizierten Code der 1C, nachdem er durch den Compiler der 2 kompiliert wurde;
4A zeigt ein Computersystem, das einen Prozessor umfaßt, der eine prädizierte Ausführung unterstützt;
4B zeigt eine Tabelle eines Ausführungsverhaltens von Vergleichsoperationen des Prozessors der 4A;
5 zeigt ein Compilerprogramm für das Computersystem der 4, das einen Quellcode zu einem prädizierten Maschinencode kompiliert, gemäß einem Ausführungsbeispiel der vorliegenden Erfindung;
6 zeigt die Struktur des Prädizierter-Code-Compilers der 5, der ein Prädizierter-Code-Analysesystem und ein Falls-Umwandlungssystem umfaßt, um den Quellcode in einen prädizierten Code umzuwandeln;
7 zeigt die Struktur des Prädizierter-Code-Analysesystems der 6;
8 ist ein Flußdiagramm, das die Funktionsweise des Scanners des Prädizierter-Code-Analysesystems der 7 zeigt;
9 ist eine Tabelle, die eine sequentielle Einzelzielform für Vergleiche-Mit-Prädikat-Operationen des prädizierten Codes zeigt;
10 zeigt die Form einer sequentiellen statischen Einzelzuordnung des prädizierten Codes der 1C, der durch den Scanner der 7 übersetzt ist;
11A–11C zeigen verschiedene durch den Scanner der 7 betriebene Routinen zum Extrahieren lokaler Prädikatenbeziehungen aus dem prädizierten Code;
11D–11F zeigen die Hash-Tabelle in unterschiedlichen Stufen für den prädizierten Code der 10;
12 ist ein Flußdiagramm der Funktionsweise des Aufbauelements des Prädizierter-Code-Analysesystems der 7;
13 zeigt einen Relative-Ergänzung-Verteilungsteilgraphen;
14A und 14B zeigen den anfänglichen Verteilungsgraphen und den vervollständigten Verteilungsgraphen des prädizierten Codes der 10;
15A–15D zeigen verschiedene durch das Prädikatenanfragesystem der 7 betriebene Anfrageroutinen zum Nachfragen bezüglich Prädikatenbeziehungen des prädizierten Codes;
15E–15J zeigen verschiedene durch das Prädikatenanfragesystem der 7 betriebene Routinen zum Manipulieren von Prädikatenausdrücken des prädizierten Codes;
16 zeigt verschiedene Typen von Flußabhängigkeiten zwischen zwei Anweisungen;
17 zeigt den Prozeß des Bestimmens einer Flußabhängigkeit einer Variable x des prädizierten Codes der 10 durch das Datenflußanalyse-Teilsystem der 7;
18 zeigt teilweise den mit Anmerkungen versehenen Steuerflußgraphen für die Variable x des prädizierten Codes der 10;
19 zeigt den zeitlich geplanten Code des Codes der 10, nachdem er durch den Compiler der 5–18 kompiliert wurde.
Die folgende ausführliche Beschreibung mancher Ausführungsbeispiele der vorliegenden Erfindung verwendet der Deutlichkeit halber bestimmte Terminologien. Jedoch ist die Erfindung nicht auf diese spezifischen verwendeten Begriffe beschränkt, sondern umfaßt vielmehr alle technischen Äquivalente, die auf im wesentlichen ähnliche Weise arbeiten, um ein im wesentlichen ähnliches Ergebnis zu erzielen.
4A veranschaulicht ein Computersystem 100, das einen Prozessor 102 umfaßt, der eine prädizierte Ausführung unterstützt. Die Hauptmerkmale der prädizierten Ausführung sind ein zusätzlicher Boolescher Operand und ein Satz von Vergleiche-Mit-Prädikat-Operationen zum Berechnen von Prädikaten. Um die prädizierte Ausführung zu unterstützen, um faßt der Prozessor 102 einen Satz von Prädikatenregistern (in 4A nicht gezeigt), um die Prädikaten zu speichern. Die Prädikatenregisterdatei ist mit der ALU (Arithmetic and Logic Unit, Rechen- und Logikeinheit) (ebenfalls nicht in 4A gezeigt) des Prozessors 102 als Anweisungsformaterweiterung verbunden. Jedes Register der Prädikatenregisterdatei speichert eine Prädikateneingabe (d.h. einen Prädikaten), die verwendet wird, um die Ausführung einer Operation oder Anweisung zu bewachen. Eine derartige Operation wird als prädizierte Operation bezeichnet. Wenn der Prädikat für eine Operation einen Wert von Eins (d.h. wahr) aufweist, wird die Operation normal ausgeführt. Wenn der Prädikat einen Wert von Null (d.h. falsch) aufweist, wird die Ausführung der Operation aufgehoben. Dies bedeutet, daß keine Veränderung des Maschinenzustands stattfindet.
Ferner umfaßt der Anweisungssatz des Prozessors 102 Vergleiche-Mit-Prädikat-Operationen. Die Vergleiche-Mit-Prädikat-Operationen berechnen die Prädikaten und schreiben das Berechnungsergebnis in die Prädikatenregister der Prädikatenregisterdatei. Jede der Vergleiche-Mit-Prädikat-Operationen kann in zwei Prädikatenregister schreiben.
Bei einem Ausführungsbeispiel weist jede der durch den Prozessor 102 ausgeführten Vergleiche-Mit-Prädikat-Operationen die folgende Form auf. p1, p2=cmpp<d1><d2>(r1<Bed>r2) falls q wobei
– p1, p2 die Zielortprädikatenregisteroperanden (d.h. Prädikaten) sind.
– cmpp der generische Vergleichs-Op-Code ist.
– <d1> und <d2> aus zwei Buchstaben bestehende Deskriptoren sind, die eine Aktion und einen Modus für die Vergleichsoperation spezifizieren. Beispielsweise können die Aktionen bedingungslose (u), bedingte (c), Parallel-Oder-(o) und Parallel-Und-(a)-Aktionen, die durch den ersten Buchstaben des Diskriptors spezifiziert sind, umfassen. Jede Aktion weist sowohl einen normalen Modus (n) als auch einen Ergänzungsmodus (c), die durch den zweiten Buchstaben des Deskriptors spezifiziert sind, auf.
– „r1<Bed>r2" spezifiziert den tatsächlichen Vergleich. Beispielsweise kann die <Bed> folgende sein: „<" (kleiner als), „>" (größer als), „=" (gleich), „≤" (kleiner gleich) oder „≥" (größer gleich).
– q ist der Prädikatenregisteroperand für die Vergleichsoperation. Obwohl q als Wachprädikat erscheint, wird es lediglich als Dateneingabe in die Vergleichsoperation betrachtet.
Alternativ dazu kann der Prozessor 102 andere Ausführungsformen für Vergleiche-Mit-Prädikat-Operationen unterstützen.
Die prädizierte Ausführung erfordert, daß der auf dem Prozessor 102 betriebene herkömmliche Code in den prädizierten Code (z.B. den prädizierten Code der 1C) fallsumgewandelt wird. Dies bedeutet, daß jede Anweisung des Codes mit einem Prädikaten prädiziert wird und ein Satz von Vergleiche-Mit-Prädikat-Anweisungen hinzugefügt wird, um die Prädikaten zu berechnen. Da der Falls-Umwandlungsprozeß lediglich die bedingungslosen und Parallel-Oder-Aktionen benötigt, um die Prädikaten zu berechnen, befaßt sich die folgende Beschreibung hauptsächlich mit diesen zwei Aktionen. Die durch die bedingungslosen Aktionen berechneten Prädikaten sind für Anweisungen brauchbar, die auf der Basis einer einzelnen Bedingung ausgeführt werden. Die durch die Parallel-Oder-Aktionen berechneten Prädikaten sind nützlich, wenn eine Ausführung eines Blocks durch mehrere Bedingungen freigegeben werden kann. 4B ist eine Tabelle, die das Ausführungsverhalten der bedingungslosen und Parallel-Oder-Aktionen sowohl bei normalen als auch bei Ergänzungsmodi zeigt. Jeder Eintrag beschreibt das Ergebnis auf dem Zielortprädikat. Es ist zu beachten, daß dem Zielort ein Wert zugewiesen sein kann, oder daß derselbe unverändert belassen werden kann (als „–" bezeichnet). Wie aus der Tabelle in 4B zu sehen ist, schreibt eine bedingungslose Vergleichsoperation immer einen Wert in ihr Zielortregister. Obwohl der Eingangsprädikat als Wachprädikat für die Vergleichsoperation erscheint, sollte er somit als Eingangsoperand in die Vergleichsoperation betrachtet werden.
Unter Bezugnahme auf 4A kann das Computersystem 100 bei einem Ausführungsbeispiel ein Personal-Computer, ein Notebook-Computer, ein Palmtop-Computer, eine Arbeitsstation, ein Großrechner oder ein Superrechner sein. Bei alternativen Ausführungsbeispielen kann das Computersystem 100 eine andere Art von Computersystem sein. Beispielsweise kann das Computersystem 100 ein Netzwerkserver oder ein Videokonferenzsystem sein.
Der Prozessor 102 ist mit einem Bus 101 gekoppelt. In dem Computersystem 100 ist ferner ein Speicher 104 vorgesehen. Der Speicher 104 ist mit dem Bus 101 verbunden und speichert üblicherweise Informationen und Anweisungen, die durch den Prozessor 102 auszuführen sind. Der Speicher 104 kann durch verschiedene Typen von Speichern implementiert sein. Beispielsweise kann der Speicher 104 durch einen RAM (Direktzugriffsspeicher) und/oder einen nicht-flüchtigen Speicher implementiert sein. Ferner kann der Speicher 104 durch eine Kombination eines RAM, eines ROM (Nur-Lese-Speicher) und/oder eines elektrisch löschbaren und programmierbaren nicht-flüchtigen Speichers implementiert sein.
Das Computersystem 100 umfaßt ferner eine Massenspeichervorrichtung 107, die Programme, Daten und andere Informa tionen speichert. Die Programme werden durch den Prozessor 102 ausgeführt und müssen zu dem Speicher 104 heruntergeladen werden, bevor sie durch den Prozessor 102 ausgeführt werden.
Eine Anzeige 121 ist mit dem Bus 101 gekoppelt, um einem Benutzer des Computersystems 100 gegenüber Informationen anzuzeigen. Eine Tastatur oder eine Tastenfeldeingabevorrichtung 122 ist mit dem Bus 101 verbunden. Eine zusätzliche Eingabevorrichtung des Computersystems 100 ist eine Cursorsteuervorrichtung 123, z.B. eine Maus, eine Rollkugel, ein Trackpad oder eine Cursorrichtungstaste. Eine weitere Vorrichtung, die ebenfalls in dem Computersystem 100 enthalten sein kann, ist eine Druckkopievorrichtung 124. Die Druckkopievorrichtung 124 wird bei dem Computersystem 100 verwendet, um Text- und/oder Bildinformationen auf ein Medium, z.B. Papier, Folie oder ähnliche Medientypen, zu drucken.
Das Computersystem 100 umfaßt des weiteren andere Peripheriegeräte 126. Diese anderen Geräte 126 können ein Floppy-Disk-Laufwerk, einen digitalen Signalprozessor, einen Scanner, eine LAN (Lokales-Netzwerk-) oder WAN(Weitverkehrsnetz-)Steuerung, einen digitalen Signalprozessor, ein MODEM (Modulation/Demodulation) und/oder ein CD-ROM-Laufwerk umfassen. Ferner kann das Computersystem 100 ohne manche der oben beschriebenen Komponenten arbeiten. Obwohl 4A manche der grundlegenden Komponenten des Computersystems 100 zeigt, soll sie weder einschränkend sein noch andere Komponenten oder Kombinationen von Komponenten in dem Computersystem 100 ausschließen.
Das Computersystem 100 umfaßt ferner einen Programmierungssprache-Compiler 200 (in 5 gezeigt). Der Compiler 200 wird auf dem Prozessor 102 betrieben, um einen Quellcode 201 zu einem prädizierten Maschinencode 202 zu kompilieren. Der prädizierte Maschinencode 202 wird anschließend in der Massenspeichervorrichtung 107 gespeichert. Wenn der prädi zierte Maschinencode 202 durch den Prozessor 102 ausgeführt werden soll, wird der prädizierte Maschinencode 202 durch den Prozessor 102 in den Speicher 104 gebracht.
Der Compiler 200 kann eine beliebige Art von Compilerprogramm sein. Wenn der Quellcode 201 beispielsweise in der Programmiersprache Fortran geschrieben ist, ist der Compiler 200 ein Fortran-Compiler. Wenn der Quellcode 200 in der C-Programmiersprache geschrieben ist, ist der Compiler 200 ein C-Programmiersprache-Compiler.
Der Compiler 200 wandelt zuerst den Quellcode 201 (z.B. den Quellcode der 1A) in den prädizierten Code (z.B. den prädizierten Code der 1C) um. Um einen qualitativ hochwertigen prädizierten Maschinencode für den Prozessor 102 zu erzeugen, der eine prädizierte Ausführung unterstützt, muß der Compiler 200 Informationen über Beziehungen zwischen Prädikaten des prädizierten Codes vor einem Planen und einer Zuweisung des prädizierten Codes in seine Datenflußanalyse integrieren.
Gemäß einem Ausführungsbeispiel der vorliegenden Erfindung führt der Compiler 200 an dem kompilierten prädizierten Code eine Analyse des prädikatenempfindlichen Datenflusses durch. Die durch den Compiler 200 durchgeführte Analyse des prädikatenempfindlichen Datenflusses manipuliert und fragt Prädikatenausdrücke des prädizierten Codes an, um (1) Datenflußeigenschaften des prädizierten Codes zu analysieren und (2) Anmerkungen bezüglich der analysierten Datenflußeigenschaften in den prädizierten Code aufzunehmen. Die Prädikatenempfindlichkeitsanalyse wird direkt an dem prädizierten Code durchgeführt, so daß keine Entsprechung mit dem ursprünglichen Steuerfluß erforderlich ist (d.h. die Analyse stützt sich nicht auf den ursprünglichen Quellcode). Die Analyse wird gemäß einem Ausführungsbeispiel der vorliegenden Erfindung durch einen Analysator des Compilers 200 durchgeführt.
Die Datenflußeigenschaften sind Eigenschaften, die sich auf den Fluß von Werten zwischen Operationen beziehen. Gemäß einem Steuerfluß und einer prädizierten Ausführung werden Operationen bedingt ausgeführt. Ein Beispiel ist eine Flußabhängigkeitsanalyse, die bestimmt, ob ein durch eine Operation erzeugter Wert durch eine nachfolgende Operation verbraucht wird.
Alternativ dazu kann der prädizierte Code trotzdem Zweiganweisungen zwischen Prädizierter-Code-Blöcken umfassen. In diesem Fall kann die Analyse des prädikatenempfindlichen Datenflusses das Vorliegen von bedingten Ausführungen aufgrund eines Verzweigens berücksichtigen.
Insbesondere analysiert der Compiler 200 die Vergleiche-Mit-Prädikat-Operationen oder -Anweisungen in dem prädizierten Code, um Beziehungen zwischen den Prädikaten zu bestimmen. Wie oben beschrieben wurde, werden diese Operationen oder Anweisungen verwendet, um die Prädikaten zu berechnen. Die Beziehungen umfassen Konzepte wie z.B. die Getrenntheit von zwei Prädikaten oder die Beziehung, daß ein Prädikat p ein Teilsatz eines anderen Prädikaten q ist (d.h. q ist immer dann wahr, wenn p wahr ist). Diese Beziehungen werden dann in einer einzigartigen Datenstruktur (d.h. einem Verteilungsgraphen) festgehalten. Die einzigartige Datenstruktur wird dann verwendet, um Prädikatenausdrücke (d.h. symbolische Boolesche Ausdrücke), die Ausführungen repräsentieren, für die jede Datenflußeigenschaft hält, darzustellen und zu manipulieren. Die Struktur des Compilers 200 ist in den 6–19, die nachfolgend ausführlicher beschrieben werden, ausführlicher gezeigt.
6 ist ein Blockdiagramm, das den Compiler 200 der 5 ausführlicher zeigt. Wie am besten in 6 zu sehen ist, umfaßt der Compiler 200 ein mit einem Vorderende 209 des Compilers 200 gekoppeltes Falls-Umwandlungssystem 210. Der Compiler 200 umfaßt ferner ein Prädizierter-Code-Analysesystem 220, das mit dem Falls-Umwandlungssystem 210 gekoppelt ist, und eine Zeitplanungs- und Registerzuweisungseinrichtung 230, die mit dem Prädizierter-Code-Analysesystem 220 gekoppelt ist. Das Vorderende 209 führt bekannte Funktionen aus und kann durch ein beliebiges bekanntes Vorderende eines Compilers implementiert sein. Das Falls-Umwandlungssystem 210 kann ebenfalls durch ein beliebiges bekanntes Falls-Umwandlungssystem eines Compilers implementiert sein, das die Ausführungsform des Prozessors 102 der 4A unterstützt. Die Zeitplanungs- und Registerzuweisungseinrichtung 230 kann durch eine beliebige Die Zeitplanungs- und Registerzuweisungseinrichtung eines Compilers implementiert sein, die in der Lage ist, eine ILP-Zeitplanung durchzuführen.
Das Vorderende 209 empfängt den Quellcode 201 (5) und wandelt den Quellcode 201 in einen Zwischencode um, der anschließend auf das Falls-Umwandlungssystem 210 angewandt wird. Das Falls-Umwandlungssystem 210 wandelt den Zwischencode auf bekannte Weise in den prädizierten Zwischencode (d.h. den prädizierten Code) um. Der prädizierte Zwischencode wird anschließend durch das Prädizierter-Code-Analysesystem 220 verarbeitet. Das Prädizierter-Code-Analysesystem 220 verarbeitet den prädizierten Zwischencode, um die Prädikatenbeziehungen aus dem Code zu extrahieren. Dies liegt daran, daß das Falls-Umwandlungssystem 210 die Prädikatenbeziehungen einbringt, wenn es den Quellcode in den prädizierten Code umwandelt. Das Prädizierter-Code-Analysesystem 220 verwendet anschließend die extrahierten Prädikatenbeziehungen, um eine Datenabhängigkeit (d.h. Zeitplanungseinschränkungen oder Präzedenzeinschränkungen) des Codes zu analysieren und den Code mit Anmerkungen bezüglich der analysierten Datenabhängigkeit zu versehen. Mit anderen Worten nutzt das Prädizierter-Code-Analysesystem 220 Beziehungen zwischen Prädikaten, um Präzedenzkanten (d.h. Zeitplanungsbeschränkungen), die für eine ILP-Zeitplanung kritisch sind, genau zu erzeugen. Der Code wird dann zu einem mit Anmerkungen versehenen prädizierten Zwischencode, wobei der Code mit Anmerkungen bezüglich der Präzedenzkanten versehen ist. Der mit Anmerkungen versehene prädizierte Zwischencode wird anschließend für eine ILP-Zeitplanungs- und Registerzuweisung auf die Zeitplanungs- und Registerzuweisungseinrichtung 230 angewandt. Die Zeitplanungs- und Registerzuweisungseinrichtung 230 führt die ILP-Zeitplanungs- und Zuweisungsfunktion auf bekannte Weise durch.
Alternativ dazu kann das Prädizierter-Code-Analysesystem 220 über ein Rückübersetzungsprogramm bzw. einen Disassembler (nicht gezeigt) direkt mit einem prädizierten Maschinencode angewandt werden. Ein derartiges System kann beispielsweise verwendet werden, um einen prädizierten Maschinencode für ein anderes Computersystem, das einen anderen Prozessor aufweist, zeitlich umzuplanen. Dieser Prozeß ist als Objektcodeübersetzung bekannt.
Gemäß einem Ausführungsbeispiel der vorliegenden Erfindung ist das Prädizierter-Code-Analysesystem 220 direkt mit dem Falls-Umwandlungssystem 210 verbunden, um den prädizierten Zwischencode zu empfangen. Das Prädizierter-Code-Analysesystem 220 liefert anschließend eine direkte Analyse an den prädizierten Zwischencode, so daß keine Entsprechung mit dem ursprünglichen Steuerfluß erforderlich ist. Wie oben beschrieben wurde, ermöglicht dies, daß (1) die Zeitplanungsbeschränkungen (d.h. Datenabhängigkeit) des prädizierten Codes vor einer Zeitplanungs- und Registerzuweisung des Codes in dem Code vermerkt wird, und (2) die Analyse sich nicht auf den Steuerfluß des ursprünglichen Quellcodes stützt. Mit anderen Worten muß die Analyse nicht den ursprünglichen Quellcode kennen und wissen, wie der prädizierte Code erzeugt wird. 7 zeigt das Prädizierter-Code-Analysesystem 220 der 6 ausführlicher.
Bevor zu 7 übergegangen wird, seien manche Begriffe wie folgt definiert.
1. PRÄDIKATENBLOCK
Ein Prädikatenblock ist eine geradlinige Sequenz von prädizierten Operationen. Ein Prädikatenblock wird allgemein durch eine Falls-Umwandlung einer Einzeleintritt-Einzelaustritt-Steuerflußregion gebildet.
2. AUSFÜHRUNGSSATZ
Ein Ausführungssatz für einen Prädikaten p, mit P bezeichnet, ist der Satz von Spuren, in denen dem Prädikaten p wahr zugewiesen ist. Eine Ausführungsspur ist eine Aufzeichnung von Booleschen Werten, die während einer Ausführung eines Prädikatenblocks Prädikatenvariablen zugewiesen werden. Hier verwenden wir „1", um den Satz aller möglichen Ausführungsspuren zu bezeichnen. Im Falle des Prädikaten p ist P für jeglichen Prädikaten p ein Teilsatz von 1 (d.h. P⊆1).
3. VERTEILUNGSGRAPH
Ein Verteilungsgraph ist ein gerichteter azyklischer Graph, dessen Knoten Ausführungssätze darstellen und dessen markierte Kanten Verteilungsbeziehungen zwischen Knoten darstellen. Im einzelnen wird eine Verteilung U=M|N durch markierte Kanten U→^r M und U→^r N dargestellt, wobei die gemeinsame Markierung r angibt, daß all diese Kanten zu derselben Verteilung gehören. Ein Verteilungsgraph ist vollständig, wenn er einen eindeutigen Knoten enthält, der keine Vorgänger aufweist, von denen alle Knoten erreichbar sind. Um Ballast zu verringern, sind Kanten mit derselben Markierung (die eine einzelne Verteilung darstellt) bezeichnet, so daß sich ihre Enden berühren, wodurch Kantenmarkierungen weggelassen werden.
4. PRÄDIKATENAUSDRUCK
Ein Prädikatenausdruck ist ein symbolischer Ausdruck, der einen Ausführungssatz darstellt. Die Basissymbole von Prädikatenausdrücken sind die Namen von Ausführungssätzen für einzelne Prädikaten, z.B. P, Q, 1 usw. Basisausdrücke können unter Verwendung der Operatorensumme (+), -differenz (–) und des -produkts (·) kombiniert werden. Ein Prädikatenausdruck wird als der Anweisungssatz interpretiert, der durch ein Anwenden entsprechender Satzoperatoren auf die Basisausführungssätze gebildet wird.
Unter Bezugnahme auf 7 umfaßt das Prädizierter-Code-Analysesystem 220 einen Scanner 301, ein Aufbauelement 303, ein Prädikatenanfragesystem 304 und ein Datenflußanalyse-Teilsystem 302. Der Scanner 301 ist verbunden, um den prädizierten Zwischencode von dem Falls-Umwandlungssystem 210 (6) zu empfangen. Der Scanner 301 ist dann mit dem Datenflußanalysesystem 302 verbunden, das wiederum mit der Zeitplanungs- und Registerzuweisungseinrichtung 230 verbunden ist. Das Aufbauelement 303 ist ebenfalls mit dem Scanner 301 verbunden. Das Prädikatenanfragesystem 304 ist mit dem Aufbauelement 303 und mit dem Datenflußanalyse-Teilsystem 302 verbunden.
Bei einem Ausführungsbeispiel ist jedes der Elemente 301 bis 304 des Prädizierter-Code-Analysesystems 220 durch eine Softwareeinrichtung implementiert. Alternativ dazu können jedes oder manche der Elemente 301 bis 304 des Prädizierter-Code-Analysesystems 220 durch eine Hardware- oder Firmwareeinrichtung implementiert sein.
Der Scanner 301 wird verwendet, um lokale Beziehungen zwischen Prädikaten in dem Code zu extrahieren. Die Prädikatenbeziehungen eines prädizierten Codes umfassen die lokalen Beziehungen und die globalen Beziehungen. Die lokalen Beziehungen beziehen sich auf die Beziehungen zwischen Prädikaten, die durch eine einzelne Vergleiche-Mit-Prädikat- Operation gelesen oder geschrieben werden. Mit anderen Worten kommen die lokalen Beziehungen von den „cmpp"-Operationen. Die globalen Beziehungen beziehen sich auf alle anderen Beziehungen. Allgemein kann jede lokale Beziehung symbolisch als eine Verteilungsbeziehung zwischen den Ausführungssätzen von Prädikaten dargestellt werden. Wie beispielsweise aus 1C ersichtlich ist, wird die Beziehung zwischen Prädikaten p und q (z.B. ist p von q getrennt) als lokale Beziehung betrachtet. Desgleichen werden die Beziehungen zwischen Prädikaten q, r und s (z.B. ist r von s getrennt, r impliziert q, s impliziert q, q=r+s) als lokale Beziehung angesehen.
Um die lokalen Beziehungen zu extrahieren, übersetzt der Scanner 301 zunächst den prädizierten Code in eine Form einer sequentiellen statischen Einzelzuordnung, was ein anschließendes Verarbeiten vereinfacht. Anschließend verarbeitet der Scanner 301 diese Form, um lokale Beziehungen zwischen Prädikaten zu entdecken. 8 zeigt den Prozeß des Scanners 301, der nachfolgend ausführlicher beschrieben wird.
Wie aus 8 ersichtlich ist, beginnt der Prozeß bei Schritt 330. Bei Schritt 331 empfängt der Scanner 301 der 7 den prädizierten Zwischencode. Bei Schritt 332 wandelt der Scanner 301 den Code in eine sequentielle Einzelzielform um. Diese Übersetzung ersetzt bedingungslose und Parallel-Oder-Operationen in dem Code durch eine sequentielle Lesen-Modifizieren-Schreiben-Version. 9 zeigt eine Tabelle, die die sequentielle Einzelzielform veranschaulicht. Wie aus 9 hervorgeht, ist der Zielortprädikatenwert eine Boolesche Funktion des Prädikateneingangswerts und der Vergleichsbedingung. Der Scanner 301 kann diese Übersetzungsfunktion unter Verwendung der bekannten Technik durchführen.
Bei Schritt 333 wandelt der Scanner 301 den Code in eine Form einer statischen Einzelzuweisung (SSA-Form, SSA = sta tic single assignment, statische Einzelzuweisung) um. Bei diesem Schritt benennt der Scanner 301 die Variablen in dem Code um, so daß jede Variable in verschiedenen Phasen individuell identifiziert werden kann. Wenn beispielsweise eine Variable t mehrere Male in dem Code definiert ist, benennt der Scanner 301 die Variable t für jede Definition um (d.h. t1, t2, t3 usw.). Diese Technik wird als Wertnumerierung bezeichnet. Um eine einfache Wertnumerierung durchzuführen, wird jeder Variable ein Zähler zugeordnet. Der Zähler wird bei jeder Definition der Variablen inkrementiert und wird bei nachfolgenden Verwendungen der Variable als Tiefstellung verwendet. Bei Schritt 334 normiert der Scanner 301 die Vergleichsbedingungen des prädizierten Codes in der Form der sequentiellen SSA, wobei Eingangsoperanden lexikographisch geordnet werden. Beispielsweise bedeutet die normierte Vergleichsbedingung von (a≥b) !(a<b). Hier bedeutet „!" „nicht". Eine Normierung und Wertnumerierung ermöglichen, daß andere Beziehungen, z.B. Ergänzung, Gleichheit und Implikation, mit einer einzigen Hash-Funktion erfaßt werden. Der Scanner 301 sendet den normierten prädizierten Code in der Form der sequentiellen statischen Einzelzuordnung anschließend an das Datenflußanalyse-Teilsystem 302 (7). 10 zeigt die umgewandelte und normierte Form der sequentiellen SSA des prädizierten Codes der 1C. Wie aus 10 ersichtlich ist, sind t1 und p äquivalente Prädikaten. Während der anfänglichen Analyse des prädizierten Codes können derartige Äquivalenzen erfaßt und in einen einzelnen symbolischen Prädikaten abgebildet werden.
Wenn eine Sequenz von prädizierten Operationen des Codes in der Form der sequentiellen statischen Einzelzuordnung gegeben ist, scannt der Scanner 301 anschließend die Operationen in einer Reihenfolge. Während Vergleichsoperationen verarbeitet werden, werden Verteilungsbeziehungen, die den Prädikatensymbolen der Vergleichsoperanden zugeordnet sind, ausgegeben. Dies erfolgt bei Schritt 335 durch den Scanner 301.
Eine Hash-Tabelle zeichnet die Abbildung zwischen Prädikatennamen in den während dieser Phase zugewiesenen Quellen- und Prädikatensymbolen auf. Ganzzahlen, die ab 1 numeriert sind, werden als Knotennamen verwendet. Anfänglich enthält die Hash-Tabelle den auf 1 abgebildeten wahren Prädikaten. Vergleichsoperationen werden der Reihe nach verarbeitet, und die Hash-Tabelle wird aktualisiert, um die Abbildungen von Vergleichsausdrücken zu symbolischen Namen und von symbolischen Namen zu Prädikatenregistern nachzuverfolgen. Bei jeder Vergleichsoperation wird die rechte Seite durch ein Normieren der Vergleichsbedingung und durch ein Ersetzen von Prädikatenoperanden durch ihren symbolischen Namen verringert.
Der Scanner 301 scannt den Code in der SSA-Form, indem er eine lookup_AND_string-Routine, eine scan_ops-Routine und eine lookup_OR_string-Routine durchführt. Die 11A bis 11C zeigen diese Routinen für ein Scannen eines Prädikatenblocks, um lokale Beziehungen zu extrahieren. Alternativ dazu können diese Routinen in anderen Formen geschrieben sein.
Die Hauptroutine ist die scan_ops, die sich über Vergleiche-Mit-Prädikat-Operationen in dem Prädikatenblock wiederholt. Während jede Vergleichsoperation besucht wird, wird die rechtsseitige Vergleichsoperation und der Wachprädikat zu einer Zeichenfolge normiert, die als Hash-Taste dient. Die Routinen lookup_AND_string und lookup_OR_string verarbeiten Tasten von bedingungslosen bzw. Oder-Stil-Vergleiche-Mit-Prädikat-Operationen. Beide Routinen geben einen symbolischen Namen zurück, der der durch die Vergleichsoperation berechneten Prädikatenvariable entspricht. In beiden Fällen wird ein Eintrag erzeugt, falls in der Hash-Tabelle nicht bereits ein Name für die Berechnung existiert. Infolge eines Hinzufügens von Einträgen zu der Hash-Tabelle können neue Verteilungsbeziehungen erzeugt werden.
Unten ist ein Beispiel dafür gezeigt, wie lokale Beziehungen unter Verwendung der Routinen der 11A bis 11C aus dem in 10 gezeigten Code extrahiert werden. Der Code der 10 ist nachstehend erneut aufgeführt, wobei die Vergleichsoperationen normiert und Nicht-Vergleichsoperationen weggelassen sind. p=!(a<b)·wahr q=(a<b)·wahr· t1=!(a<b)·wahr t2=t1+!(c=d)·q s=(c=d)·q r=!(c=d)·q
Operationen werden der Reihe nach verarbeitet, was zu folgenden Effekten führt.

– Die anfängliche Hash-Tabelle bildet wahr auf 1 ab und erzeugt einen symbolischen Namen für den Ausführungssatz.
– p=!(a<b)·wahr. Dies kann auf p=!(a<b)·1 reduziert werden. Während des Nachschlagens werden die rechte Seite und ihre Ergänzung zu der anfänglichen Tabelle hinzugefügt (siehe 11D), und es wird eine Verteilungsbeziehung ausgegeben, die 1=2|3 lautet.
– q=(a<b)·wahr. Dies kann auf q=(a<b)·1 reduziert werden, was weiter auf q=3 reduziert wird. Aktion: füge q zu der Liste von Quellnamen für das Symbol 3 hinzu.
– t1=!(a<b)·wahr. Dies kann auf t1=2 reduziert werden. Aktion: füge t1 zu der Liste von Quellnamen für das Symbol 2 hinzu.
– t2=t1+!(c=d)·q. Dies kann auf t2=2+!(c=d)·3 reduziert werden. Während des Nachschlagens werden „!(c=d)·3" und seine Ergänzung zu der Hash-Tabelle hinzugefügt (siehe 11E), und es wird eine Verteilungsbeziehung ausgegeben, die 3=4|5 lautet. Der äußere Ausdruck wird ferner auf t2=2+4 reduziert, was zu der Hash-Tabelle hinzugefügt wird (11E), und es wird eine Verteilungsbeziehung ausgegeben, die 6=2|4 lautet.
– s=(c=d)·q. Dies kann auf s=5 reduziert werden. Aktion: füge s zu der Liste von Quellnamen für das Symbol 5 hinzu.
– r=!(c=d)·q. Dies kann auf r=4 reduziert werden. Aktion: füge r zu der Liste von Quellnamen für das Symbol 4 hinzu.
– Die endgültige Hash-Tabelle ist in 11F gezeigt, zusammen mit den endgültigen Verteilungsbeziehungen (lokalen Beziehungen), die ausgegeben werden. Diese Beziehungen lauten 1=2|3, 3=4|5 und 6=2|4.

Unter erneuter Bezugnahme auf 7 sendet der Scanner 301 die extrahierten lokalen Beziehungen an das Aufbauelement 303, nachdem der Scanner 301 die lokalen Beziehungen aus dem prädizierten Code extrahiert. Das Aufbauelement 303 bestimmt anschließend die globalen Beziehungen des Codes, indem es die lokalen Beziehungen kombiniert. Wenn wir beispielsweise die Beziehungen 1=P|Q und Q=R|S kennen, können wir ableiten, daß Prädikaten sowohl von R als auch von S getrennt ist. Das Aufbauelement 303 bestimmt die globalen Beziehungen, indem es einen Verteilungsgraphen aufbaut, bei dem die lokalen Beziehungen aus dem Code extrahiert sind, und anschließend den Verteilungsgraphen vervollständigt. 12 zeigt den Prozeß des Aufbauelements 303, den Verteilungsgraphen aufzubauen und zu vervollständigen.
Wie aus 12 erkennbar ist, beginnt der Prozeß bei Schritt 370. Bei Schritt 371 empfängt das Aufbauelement 303 die lokalen Beziehungen, die in Form einer Liste von Verteilungen vorliegen. Bei Schritt 372 baut das Aufbauelement 303 einen anfänglichen Verteilungsgraphen 400 auf, indem es die lokalen Beziehungen einfach als Knoten und Kanten darstellt. 14A zeigt den anfänglichen Verteilungsgraphen 400 des prädizierten Codes der 10, der durch das Aufbauelement 303 aufgebaut ist, mit den lokalen Beziehungen 1=P|Q, Q=R|S und T2=P+R. Wie aus 14A zu ersehen ist, ist der anfängliche Verteilungsgraph 400 kein vollständiger Graph, da nicht alle Knoten von der Wurzel erreichbar sind. Insbesondere ist der Knoten T2 nicht von der Wurzel erreichbar. Dies liegt daran, daß Knoten, die nichtaufgebauten Steuerregionen entsprechen, deren Verteilungen von Oder-Stil-Vergleichen kommen, anfänglich nicht erreichbar sind.
Bei Schritt 373 vervollständigt das Aufbauelement 303 den anfänglichen Verteilungsgraphen. Um den anfänglichen Verteilungsgraphen zu vervollständigen, müssen zusätzliche Verteilungen, die mit existierenden Verteilungen übereinstimmen, synthetisiert werden, so daß alle Knoten von der Wurzel erreichbar sind. Das Aufbauelement 303 vervollständigt den Verteilungsgraphen, indem es eine nachstehend gezeigte Routine durchführt.

1. L sei eine Liste von Verteilungen, die von dem Verteilungsgraph-Wurzelknoten nicht erreichbar sind. Ferner sollen die Verteilungen in der Liste L in der Reihenfolge auftreten, in der sie während des Scannens angetroffen wurden.
2. Für jede Verteilung in L gelte p=m/n tue – lca sei der niedrigste gemeinsame Vorfahre von m und n, so daß lca von der Wurzel erreichbar ist; – lca kann nun zu p und r verteilt werden, wobei r die relative Ergänzung von p bezüglich lca ist; – falls r nicht als Knoten in dem Verteilungsgraphen existiert (d.h. falls rel_comp einen Satz von Knoten mit mehr als einem Element zurückgibt), erzeuge einen Verteilungsunterbaum, der den Knoten r als Wurzel aufweist, um die relative Ergänzung darzustellen (siehe 13). Dieser Baum kann eine einfache Kette sein.

Alternativ dazu kann die Routine der 13 in anderen Formen geschrieben werden. Der vervollständigte Verteilungsgraph ist eine Datenstruktur, die die lokalen Beziehungen mit den globalen Beziehungen in einer Form kombiniert, die für ein Beantworten allgemeiner Anfragen bezüglich Prädikatenbeziehungen geeignet ist.
Durch ein Durchführen der oben beschriebenen Routine vervollständigt das Aufbauelement 303 den anfänglichen Verteilungsgraphen 400 der 14A zu dem vollständigen Verteilungsgraphen 410 der 14B. Hier kann das Aufbauelement 303 durch Untersuchen des anfänglichen Verteilungsgraphen 400 der 14A bestimmen, daß, obwohl der Knoten T2 nicht von dem Knoten 1 erreichbar ist, seine Nachfolger P und R (durch Q) von dem Knoten 1 erreichbar sind. Ferner kann das Aufbauelement 303 bestimmen, daß der Knoten 1 selbst der niedrigste gemeinsame Vorfahre von P und R ist. Somit kann die relative Ergänzung von T2 bezüglich 1 (d.h. 1–T2) als (1-R)-P berechnet werden. (Die relative Ergänzung eines Knotens N bezüglich eines Vorfahren M findet sich, indem die Vereinigung von Geschwistern von Knoten entlang eines beliebigen Pfades von M nach N gesammelt wird. Beispielsweise sind P und S die Geschwister von Knoten auf dem Pfad von 1 nach R, so daß 1–R=P+S). Somit gilt: 1–T2=(1–R)– P=(P+S)–P=(P–P)+S=S. Daher gilt 1=T2|S. Diese Verteilung (d.h. 1=T2|S) wird anschließend zu dem Graphen hinzugefügt, was den Verteilungsgraphen 410 (14B) vervollständigt. Der vervollständigte Verteilungsgraph wird anschließend bei Schritt 374 in dem Prädikatenanfragesystem 304 (7) gespeichert. Der Prozeß endet dann bei Schritt 375.
Wie aus dem Verteilungsgraphen 410 der 14B ersichtlich ist, sind die Prädikaten p und s voneinander getrennt.
Unter erneuter Bezugnahme auf 7 bildet das Prädikatenanfragesystem 304 eine Schnittstelle mit dem Datenflußanalyse-Teilsystem 302. Das Prädikatenanfragesystem 304 speichert den von dem Aufbauelement 303 empfangenen vervollständigten Verteilungsgraphen und verwendet den Verteilungsgraphen, um Anfragen von dem Datenflußanalyse-Teilsystem 302 zu beantworten. Das Datenflußanalyse-Teilsystem 302 analysiert den prädizierten Code in der SSA-Form, um Datenflußeigenschaften des Codes zu bestimmen. Mit anderen Worten berechnet das Datenflußanalyse-Teilsystem 302 (1) Datenabhängigkeiten des Codes, (2) nach oben und nach unten freiliegende Definitionen und Verwendungen und (3) Aktivbereich- und Interferenzinformationen während einer Registerzuweisung. Beim Analysieren des Datenflusses des Codes erzeugt das Datenflußanalyse-Teilsystem 302 Anfragen bezüglich der Prädikatenbeziehungen des Codes, indem es die entsprechenden Anfragebefehle an das Prädikatenanfragesystem 304 sendet. Das Prädikatenanfragesystem 304 betreibt dann die entsprechenden Anfrageroutinen, um zu bestimmen, ob jede der Prädikatenbeziehungsanfragen wahr oder falsch ist. 15A bis 15J zeigen verschiedene Anfrageroutinen für das Prädikatenanfragesystem 304. Alternativ können diese Anfrageroutinen in anderen Formen implementiert sein. Nach dem Betreiben der Anfrageroutinen informiert das Prädikatenanfragesystem 304 das Datenflußanalyse-Teilsystem 302, ob jede der Anfragen wahr oder falsch ist.
Wenn das Datenflußanalyse-Teilsystem 302 beispielsweise auf Prädikaten p und q in dem Code trifft, muß das Teilsystem 302 wissen, ob der Prädikat p von dem Prädikaten q getrennt oder ein Teilsatz desselben ist. In diesem Fall erzeugt das Teilsystem 302 die Anfragebefehle is_disjoint [ist_getrennt] (p, q) und is_subset [ist_Teilsatz] (p, q) an das Prädikatenanfragesystem 304. Das Prädikatenanfragesystem 304 betreibt anschließend die entsprechenden Anfrageroutinen, um zu bestimmen, ob jede der Anfragen wahr oder falsch ist.
Die Anfragebefehle von dem Datenflußanalyse-Teilsystem 302 umfassen folgende.

– true_expr [wahrer_Ausdr.] (); ein Prädikatenausdruck, der den universellen Satz von Ausführungen darstellt.
– false_expr [falscher_Ausdr.] (); der Null-Prädikatenausdruck, der den leeren Satz von Ausführungen darstellt. Diese zwei Befehle werden verwendet, um Prädikatenausdrücke in Datenflußvektoren (nachfolgend beschrieben) auf den entsprechenden Standardwert zu initialisieren. Beispielsweise wird bei einer Aktivitätsanalyse jeder Vektor auf die falschen Ausdrücke initialisiert, was keine Variablen aktiv darstellt.
– lub_sum (p, ∊); ein kleinstes ∊', so daß P∪∊⊆∊'.
– glb_sum (p, ∊) ; ein größtes ∊', so daß P∪∊⊇∊' . Diese zwei Befehle werden verwendet, um eine Eigenschaft an einem Punkt unter einem Wachprädikaten zu erzeugen. Die Wahl zwischen der kleinsten oberen Grenze und der größten unteren Grenze wird dadurch bestimmt, daß das Datenflußproblem gelöst wird. Wenn bei einer Aktivitätsanalyse z.B. eine Variable x bei Ausführungen, die durch einen Ausdruck ∊ dargestellt werden, direkt nach einer Operation aktiv ist, bei der x unter dem Wachprädikaten p verwendet wird, so ist x bei Ausführungen aktiv, die durch den Ausdruck ∊+P direkt vor der Operation dargestellt werden. Da die Aktivität ein Problem „eines beliebigen Pfades" ist, ist eine Überannäherung des Ausführungssatzes konservativ, und somit berechnen wir ∊+P unter Verwendung von lub_sum (p, ∊). Für ein Problem „jedes Pfades" muß der Ausfüh rungssatz einer Unterannäherung unterzogen werden. Somit kann ein Prädikatenausdruck unter Verwendung von glu_sum berechnet werden.
– lub_diff (p, ∊); ein kleinstes ∊', so daß ∊–P⊆∊';
– glb diff (p, ∊); ein größtes ∊', so daß ∊–P⊇∊'. Diese Befehle werden verwendet, um eine Eigenschaft an einem Punkt unter einem Wachprädikaten zu töten. Wenn bei einer Aktivitätsanalyse z.B. eine Variable x bei Ausführungen, die durch einen Ausdruck ∊ dargestellt werden, direkt nach einer Operation aktiv ist, bei der x unter dem Wachprädikaten p verwendet wird, so ist x bei Ausführungen aktiv, die durch den Ausdruck ∊–P direkt vor der Operation dargestellt werden. Da die Aktivität ein Problem „eines beliebigen Pfades" ist, ist eine Überannäherung des Ausführungssatzes konservativ, und somit berechnen wir ∊–P unter Verwendung von lub_diff (p, ∊).
– is_disjoint (p, ∊); wahr, falls P∩∊=0. Dieser Befehl wird verwendet, um zu testen, ob eine Eigenschaft bei irgendeiner Ausführung an einem Punkt unter einem Wachprädikaten hält. Beispielsweise stören zwei Variablen (d.h. sie müssen verschiedenen physischen Registern zugewiesen werden), falls eine an einem Definitionspunkt der anderen aktiv ist. Falls eine Variable y bei Ausführungen, die an einem Punkt, wo die Variable x unter dem Prädikaten p definiert ist, durch ∊ dargestellt werden, aktiv ist, so stören die Variablen, falls ∊ nicht von P getrennt ist. Dies wird unter Verwendung von is_disjoint (p, ∊) getestet.
– is_subset (p, ∊); wahr, falls P ein Teilsatz des durch ∊ dargestellten Ausführungssatzes ist. Dieser Befehl wird verwendet, um zu testen, ob eine Eigenschaft in allen Ausführungen an einem Punkt unter einem Wachprädikaten hält.

Die Variablen von Prädikatenausdrücken sind Symbole, die Ausführungssätze für individuelle Prädikaten benennen, und sie werden explizit durch Knoten in dem Verteilungsgraphen dargestellt. Um Anfragen bezüglich Prädikatenbeziehungen effizient und genau zu beantworten und um die Prädikatenausdrücke zu manipulieren, beschränken die Anfrageroutinen Prädikatenausdrücke auf Trennungen bzw. Disjunktionen von individuellen Symbolen, die als 1-disjunktive Normalform (1-dnf) bekannt sind. Derartige Ausdrücke können entweder als Liste von Symbolen oder als Bitvektor, der ein Bit pro Symbol (d.h. ein Bit pro Knoten in dem Verteilungsgraphen) aufweist, gespeichert sein.
15A zeigt die Anfrageroutine zum Testen einer Getrenntheit zwischen einem Paar von Symbolen, und 15B zeigt die Anfrageroutine zum Testen einer Getrenntheit zwischen einem Symbol und einem Prädikatenausdruck (in reduzierter 1-dnf-Form). Es ist anzumerken, daß der falsche Ausdruck ∊_falsch einfach eine leere Liste von Prädikatensymbolen ist. Der wahre Ausdruck ∊_wahr ist die Liste, die 1, die Wurzel des Verteilungsgraphen, enthält. Die Routinen versuchen, eine Getrenntheit zwischen zwei Symbolen P und Q zu zeigen, indem sie eine Verteilung finden, bei der P und Q in getrennten Teilen enthalten sind. Falls keine derartige Verteilung existiert, nimmt man an, daß P und Q sich schneiden.
15C und 15D zeigen die Anfrageroutinen zum Testen der Teilsatzbeziehungen. Der Ausführungssatz P ist ein Teilsatz von Q, falls in dem Verteilungsgraphen von dem Knoten P zum Knoten Q ein Umkehrpfad vorliegt. Die Teilsatzbeziehungen sind analog zu Dominanz und Post-Dominanz, sind jedoch unempfindlich bezüglich eines zeitlichen Ordnens der Prädikatenberechnungen.
15E und 15F zeigen die Routinen zum Summieren eines einzelnen Symbols zu einem Prädikatenausdruck. Die Routine sum_reduce wird durchgeführt, wenn das zu einem Ausdruck hinzuzufügende neue Symbol ein Teilsatz eines Symboles ist, das bereits in dem Ausdruck enthalten ist. In diesem Fall wird das neue Symbol hinzugefügt, und der sich ergebende Ausdruck wird auf rekursive Weise reduziert.
15G bis 15J zeigen die Routinen zum Subtrahieren eines Symbols P von einem Prädikatenausdruck. Hier ist eine Annäherung erforderlich. Wenn das Symbol P in dem Ausdruck ein Teilsatz des Symbols Q ist, kann Q-P berechnet werden, indem Q durch die relative Ergänzung von P bezüglich Q, die immer durch einen 1-dnf-Ausdruck dargestellt werden kann, ersetzt wird. Dies erfolgt durch die Routine approx_diff (15H). Falls P Q in dem Ausdruck schneidet, jedoch weder ein Teilsatz noch ein Supersatz ist, so muß die Annäherung die Satzdifferenz darstellen, was durch die Routine rel_cmpl (15I) erfolgt. Jeglicher Supersatz der Satzdifferenz ist eine gültige Annäherung. In diesem Fall kann die relative Ergänzung von P bezüglich des niedrigsten gemeinsamen Vorfahrens von P und Q durch die Routine find_lca der 15J angenähert werden.
Unter Bezugnahme auf 7 führt das Datenflußanalyse-Teilsystem 302 eine prädikatenempfindliche Bitvektoranalyse durch, um zu berechnen, ob eine Eigenschaft für einen Satz von Ausführungen an jedem Punkt in einem Steuerflußgraphen (d.h. an einem Punkt in einem Ausführungssatz) hält. Jede Variable wird auf eine bestimmte Position in allen Bitvektoren abgebildet. Jede Vektorposition wird erweitert, um einen Prädikatenausdruck statt eines einzelnen Bits zu halten. Wenn eine Operation eine Eigenschaft unter einem Prädikaten p erzeugt, so hält die Eigenschaft für alle Ausführungen bei P an diesem Punkt, und so wird der Satz P an diesem Punkt zu dem Ausführungssatz hinzugefügt. Falls eine Operation eine Eigenschaft unter dem Prädikaten q tötet, wird Q an diesem Punkt von dem Ausführungssatz subtrahiert. In diesem Fall wird das Konzept des Testens einer Eigenschaft an einem Punkt des Steuerflußgraphen auf ein Testen dessen erweitert, ob die Eigenschaft an einem Punkt in einem bestimmten Teilsatz von Ausführungen hält. Diese Ausdrucksmanipulationen werden unter Verwendung der oben erwähnten Anfragebefehle an das Prädikatenanfragesystem 304 durchgeführt.
Die prädikatenempfindliche Bitvektoranalyse umfaßt eine Flußanalyse und eine Aktivitätsanalyse. Die Flußanalyse wird zum zeitlichen Planen verwendet, und die Aktivitätsanalyse wird für eine Registerzuweisung verwendet. 16 zeigt verschiedene Arten von Flußabhängigkeiten zwischen zwei Anweisungen. Wie man weiß, ist eine Variable x an einem Punkt des Steuerflußgraphen aktiv, falls ein Pfad vorliegt, der keine Definition von x von diesem Punkt bis zu einer Verwendung von x enthält. Der Unterschied zwischen der Flußanalyse und der Aktivitätsanalyse besteht darin, daß die Flußanalyse durch den Steuerflußgraphen nach vorne ausgebreitet ist, während die Aktivitätsanalyse durch den Steuerflußgraphen nach hinten ausgebreitet ist.
Bei der prädikatenempfindlichen Aktivitätsanalyse wird ein Vektor von Prädikatenausdrücken verwendet, die eine Position für jede Variable in dem Code aufweisen. Jeder Prädikatenausdruck stellt den Satz von Ausführungen dar, in dem die entsprechende Variable an diesem Punkt aktiv ist. Die Prädikatenausdrücke werden aktualisiert, wenn jede Operation in umgekehrter Reihenfolge besucht wird.
Bei einer Operation wird E^– verwendet, um einen Ausdruck direkt vor der Operation zu bezeichnen, und E⁺ wird verwendet, um einen Ausdruck direkt nach der Operation zu bezeichnen. Man betrachte beispielsweise eine Verwendung der Variablen x, die durch einen Prädikaten p bewacht wird. Die Verwendung von x erzeugt eine Aktivität von x in allen Ausführungen in dem Satz P direkt vor der Operation, d.h. bei der Operation, E / x– = E / x+ + P (unter Verwendung der Routine lub_sum). Eine Definition von x, das durch einen Prädikaten q bewacht wird, tötet eine Aktivität von x in allen Ausfüh rungen in dem Satz Q, d.h. bei der Operation, E / x– =E / x+ – Q (unter Verwendung der Routine lub_diff). Bei einer Definition einer Variablen y, die durch einen Prädikaten r bewacht wird, stören sich y und x, falls x unter dem Prädikaten r aktiv ist, d.h. falls E / x+ ⋂ R ≠ 0. Eine Interferenz bzw. Störung wird unter Verwendung der Routine is_disjoint getestet. Das !disj stellt die Ergänzung der Routine is_disjoint dar.
17 ist ein Beispiel, das den Prozeß der prädikatenempfindlichen Bitvektoranalyse zeigt, der durch das Datenflußanalyse-Teilsystem 302 der 7 an einem Abschnitt des Codes der 10 durchgeführt wird. Der Einfachheit und Deutlichkeit halber zeigt 17 lediglich den Analyseprozeß für die Variable x des Codes der 10.
Es gibt die Funktionen GEN (ERZEUGEN), KILL (TÖTEN) und TEST (TESTEN), die jeder Operation entsprechen. Diese Funktionen manipulieren die Datenflußinformationen an diesem Punkt in dem Programm. Diese Funktionen stellen die Auswirkung der Operation auf die Datenflußwerte dar. Jede Operation weist ferner eine zugeordnete TEST-Funktion zum Abtasten der Datenflußwerte an diesem Punkt in dem Programm auf. Bei einer Abhängigkeitsanalyse wird eine Datenabhängigkeitskante erzeugt, wenn die TEST-Funktion als wahr wiedergegeben wird.
Wie in 17 zu sehen ist, werden ein Datenvektor und ein Verwendungsvektor für die Variable x geliefert. Die zwei Vektoren werden anfänglich auf falsch eingestellt, da die Analyse in der vorwärtsgerichteten Reihenfolge durchgeführt wird. Alternativ dazu können die Vektoren anfänglich auf wahr eingestellt werden. Anschließend werden die GEN-, KILL- und TEST-Verarbeitungsfunktionen auf die Operationen (d. h. die Operationen S₄, S₅, S₉ und S₁₁) für gewöhnliche Definitionen und Verwendungszwecke angewendet. Bei jeder Operation werden die Definitionen vor der Verwendung verarbeitet.
Bei der Operation S₄ werden die GEN-, KILL- und TEST-Funktionen angewendet. Hier wird die TEST-Verarbeitung übersprungen, da der Datenvektor für alle Definitionsvektorpositionen falsch ist (d.h. D[S₄, S₅, S₉]=falsch) . Die KILL-Verarbeitung bestimmt, daß alle Definitionsvektorpositionen in dem Datenvektor falsch bleiben. Zu diesem Zeitpunkt bestimmt die für die S₄-Vektorposition durchgeführte GEN-Verarbeitung, daß die Datenvektorposition für S₄ (d.h. D[S₄] gleich P ist. Das neue Ergebnis wird anschließend in die Datenvektorposition für S₄ geschrieben.
Bei der Operation S₅ werden die GEN-, KILL- und TEST-Regeln lediglich auf die jeweiligen Vektorpositionen des Datenvektors angewandt. Die KILL-Verarbeitung bestimmt, daß die Datenvektorposition für S₄ (d.h. D[S₄]) P ist und daß die Datenvektorposition für jedes von S₅ und S₉ falsch bleibt. Die GEN-Verarbeitung bestimmt, daß die Datenvektorposition für S₅ Q wird. Die TEST-Verarbeitung bestimmt, daß zwischen den S₄- und S_S-Operationen keine Abhängigkeit vorliegt. Die Daten- und Verwendungsvektoren werden anschließend aktualisiert.
Bei der Operation S₉ bestimmt die KILL-Verarbeitung, daß D[S₄] P ist, daß D[S₅] R ist und daß D[S₉] falsch bleibt. Die GEN-Verarbeitung bestimmt, daß die Datenvektorposition für S₉ S wird. Die TEST-Verarbeitung bestimmt, daß zwischen den S₄- und S₉-Operationen keine Abhängigkeit vorliegt. Die TEST-Verarbeitung bestimmt ferner, daß zwischen den S₅- und S₉-Operationen eine Ausgabeabhängigkeit vorliegt. Anschließend werden die Daten- und Verwendungsvektoren aktualisiert.
Da die Operation S₁₁ eine Verwendungsoperation für die Variable x ist, kommt es zu keiner KILL-Verarbeitung. Die GEN-Verarbeitung bestimmt, daß die Verwendungsvektorposition für S₁₁ T2 ist. Die TEST-Verarbeitung bestimmt, daß zwischen den S₄- und S₁₁-Operationen und zwischen den S₅ und S₁₁-Operationen eine Flußabhängigkeit vorliegt. Die TEST-Verarbeitung bestimmt ferner, daß zwischen den S₉- und S₁₁-Operationen keine Abhängigkeit vorliegt.
Anschließend wird der Code wieder mit Anmerkungen bezüglich der Datenabhängigkeiten versehen, wodurch ein mit Anmerkungen versehener Steuerflußgraph für die Variable x erhalten wird (siehe 18). Der mit Anmerkungen versehene Code kann anschließend durch den Zeitplaner 230 zeitlich geplant und registerzugewiesen werden (7), und 19 zeigt den zeitlich geplanten Code des Codes der 10.
Wie aus 18 und 19 ersichtlich ist, werden die S₄- und S₅-Operationen zusammen zeitlich in demselben Zyklus zeitlich eingeplant, da sie keine Abhängigkeit aufweisen. Desgleichen werden die S₉- und S₁₁-Operationen zusammen in demselben Zyklus zeitlich eingeplant, da sie keine Abhängigkeit aufweisen. Folglich kann der Code in lediglich drei Zyklen ausgeführt werden, im Vergleich zu fünf Zyklen (siehe 3) für denselben Code unter Verwendung des bekannten Compilers.

Claims

System (220) zum Analysieren eines prädizierten Codes, der Prädikatenbeziehungen aufweist, wobei das System folgende Merkmale aufweist: eine Einrichtung zum Verarbeiten des prädizierten Codes, um die Prädikatenbeziehungen aus dem prädizierten Code zu extrahieren; und eine Einrichtung (302, 303, 304) zum Verwenden der extrahierten Prädikatenbeziehungen, um Datenflußeigenschaften des prädizierten Codes zu analysieren, wobei die Datenflußeigenschaften Datenabhängigkeiten zwischen Operationen in dem prädizierten Code umfassen, wobei die Datenabhängigkeiten zwischen den Operationen zum Planen der Operationen verwendet werden sollen.
System gemäß Anspruch 1, bei dem die Einrichtung zum Verwenden folgende Merkmale aufweist: ein Prädikatenanfragesystem (304) zum Speichern der Prädikatenbeziehungen des prädizierten Codes; und ein Datenflußanalyse-Teilsystem (302) zum Anfragen des Prädikatenanfragesystems (304), um die Prädikatenausdrücke des prädizierten Codes zum Bestimmen der Datenflußeigenschaften zu manipulieren.
System gemäß Anspruch 1 oder 2, bei dem das Datenflußanalyse-Teilsystem (302) zum Annähern von Ergebnissen der Prädikatenausdrücke des prädizierten Codes wirksam ist, während es die Prädikatenausdrücke manipuliert, und den prädizierten Code mit Anmerkungen zu den analysierten Datenflußeigenschaften versieht, um einen mit Anmerkungen versehenen prädizierten Code zu erhalten.
System (220) gemäß Anspruch 1, bei dem die Prädikatenbeziehungen lokale und globale Prädikatenbeziehungen umfassen und bei dem die Einrichtung zum Verwenden folgende Merkmale aufweist: ein Prädikatenanfragesystem (304) zum Speichern der lokalen und globalen Prädikatenbeziehungen des prädizierten Codes und zum Beantworten von Anfragen bezüglich der lokalen und globalen Prädikatenbeziehungen.
System (220) gemäß Anspruch 4, bei dem die Einrichtung zum Verwenden ferner folgende Merkmale aufweist: einen Scanner (301), der die lokalen Prädikatenbeziehungen des prädizierten Codes bestimmt; ein Aufbauelement (303), das die globalen Prädikatenbeziehungen des prädizierten Codes bestimmt, wobei das Aufbauelement (303) die globalen Prädikatenbeziehungen des prädizierten Codes bestimmt, indem es aus den lokalen Prädikatenbeziehungen einen Verteilungsgraphen aufbaut und den Verteilungsgraphen vervollständigt, indem es einen einzigen gemeinsamen Vorfahren liefert, der einen einzigartigen Wurzelknoten für den Verteilungsgraphen bildet.
Verfahren zum Analysieren eines prädizierten Codes, der Prädikatenbeziehungen aufweist, wobei das Verfahren folgende Schritte aufweist: Verarbeiten des prädizierten Codes, um die Prädikatenbeziehungen aus dem prädizierten Code zu extrahieren; und Verwenden (302, 303, 304) der extrahierten Prädikatenbeziehungen, um Datenflußeigenschaften des prädizierten Codes zu analysieren, wobei die Datenflußeigenschaften Datenabhängigkeiten zwischen Operationen in dem prädizierten Code umfassen, wobei die Datenabhängigkeiten zwischen den Operationen zum Planen der Operationen verwendet werden sollen.
Verfahren gemäß Anspruch 6, bei dem der Schritt des Verwendens folgende Teilschritte umfaßt: Manipulieren von Prädikaten und Prädikatenausdrücken des prädizierten Codes, um die Datenflußeigenschaften des prädizierten Codes zu analysieren; Senden von Anfragen bezüglich der Prädikate und Prädikatenausdrücke des prädizierten Codes an ein Prädikatenanfragesystem (304), das Prädikatenbeziehungen des prädizierten Codes speichert, wenn es die Prädikaten und Prädikatenausdrücke manipuliert; und Empfangen von Ergebnissen der Anfragen von dem Prädikatenanfragesystem (304) bezüglich der Prädikate und der Prädikatenausdrücke.
Das Verfahren gemäß Anspruch 7, bei dem der Schritt des Manipulierens ferner den Schritt des Annäherns an Ergebnisse der Prädikatenausdrücke, die manipuliert werden, aufweist, wobei der Schritt des Empfangens ferner den Schritt des Versehens des prädizierten Codes mit Anmerkungen bezüglich der analysierten Datenflußeigenschaften aufweist.
Das Verfahren gemäß Anspruch 6, bei dem der Schritt des Verwendens folgende Schritte aufweist: Bestimmen lokaler Prädikatenbeziehungen des prädizierten Codes; Bestimmen globaler Prädikatenbeziehungen des prädizierten Codes; Speichern der lokalen und globalen Prädikatenbeziehungen des prädizierten Codes in einem Prädikatenanfragesystem (304), derart, daß die lokalen und globalen Prädikatenbeziehungen während einer Datenflußanalyse des prädizierten Codes angefragt werden können.
Das Verfahren gemäß Anspruch 9, bei dem der Schritt des Bestimmens lokaler Prädikatenbeziehungen ferner folgende Schritte aufweist: Übersetzen von Prädikaten des prädizierten Codes in eine Form einer sequentiellen statischen Einzelzuordnung; Normieren von Vergleichsbedingungen des prädizierten Codes und Abtasten des normierten prädizierten Codes, um die lokalen Prädikatenbeziehungen zu bestimmen; wobei der Schritt des Bestimmens von globalen Prädikatenbeziehungen des prädizierten Codes ferner folgende Schritte aufweist: (i) Aufbauen eines Verteilungsgraphen aus den lokalen Prädikatenbeziehungen; (ii) Vervollständigen des Verteilungsgraphen durch Bereitstellen eines einzigen gemeinsamen Vorfahren, der einen einzigartigen Wurzelknoten für den Verteilungsgraphen bildet.
Das Verfahren gemäß Anspruch 10, bei dem der Schritt des Speicherns der lokalen und globalen Prädikatenbeziehungen ferner folgende Schritte aufweist: Untersuchen des vervollständigten Verteilungsgraphen, um zu bestimmen, ob ein erstes Prädikat des prädizierten Codes von einem zweiten Prädikat des prädizierten Codes getrennt ist; Untersuchen des vervollständigten Verteilungsgraphen, um zu bestimmen, ob das erste Prädikat des prädizierten Codes ein Teilsatz des zweiten Prädikats des prädizierten Codes ist; Untersuchen des vervollständigten Verteilungsgraphen, um das erste Prädikat des prädizierten Codes zu einem Prädikatenausdruck des prädizierten Codes hinzuzufügen; Untersuchen des vervollständigten Verteilungsgraphen, um das erste Prädikat des prädizierten Codes von dem Prädikatenausdruck des prädizierten Codes zu subtrahieren.
Compiler (200), der folgende Merkmale aufweist: ein Prädikatenumwandlungssystem (210) zum Umwandeln eines Quellcodes in einen prädizierten Code; ein System (220) zum Analysieren des prädizierten Codes, um Datenabhängigkeiten zwischen Operationen gemäß einem der Ansprüche 1 bis 5 zu erhalten; und einen Zeitplaner (230) zum zeitlichen Planen der Operationen auf der Basis der Datenabhängigkeiten.
Verfahren zum Kompilieren (200), das folgende Schritte aufweist: Umwandeln (210) eines Quellcodes in einen prädizierten Code; Analysieren (220) des prädizierten Codes, um Datenabhängigkeiten zwischen Operationen gemäß einem der Ansprüche 6 bis 11 zu erhalten; und zeitliches Festlegen (230) der Operationen auf der Basis der Datenabhängigkeiten.
Computerprogramm zum Durchführen des Verfahrens gemäß Anspruch 6 oder Anspruch 13, wobei das Computerprogramm auf einem Computer betrieben wird.