Darstellung der Kerntechniken des modernen Übersetzerbaus
Vermittlung von modernen Techniken zur Realisierung optimierender Übersetzer für objektorientierte Programmiersprachen
Ganzheitliche Darstellung des Themas
Objektorientierung ist eine der wesentlichen Techniken zur Realisierung von Softwaresystemen. Die unbestrittenen Vorteile dieses Ansatzes bei der Modellierung und Implementierung müssen jedoch häufig durch eine geringere Effizienz der so erstellten Programme erkauft werden. Dieses Buch vermittelt moderne Optimierungstechniken, die es Übersetzern für objektorientierte Programmiersprachen wie Sather, Java oder C# ermöglichen, automatisch effizientere ausführbare Programme zu erzeugen. Ausgehend von den speziellen Anforderungen an die Optimierung objektorientierter Programme werden in einem ganzheitlichen Ansatz geeignete übersetzerinterne Programmrepräsentationen, Algorithmen für deren globale Analyse und zielgerichtete Programmtransformationen zur Effizienzsteigerung vermittelt.|Die unbestrittenen Vorteile des objektorientierten Ansatzes bei Modellierung und Implementierung müssen häufig durch geringere Effizienz der so erstellten Programme erkauft werden. Dieses Buch vermittelt moderne Optimierungstechniken, die es Übersetzern für objektorientierte Programmiersprachen wie Sather, Java oder C# ermöglichen, automatisch effizientere ausführbare Programme zu erzeugen. Dabei werden in einem ganzheitlichen Ansatz zielgerichtet geeignete übersetzerinterne Programmrepräsentationen, Algorithmen für deren globale Analyse und wirksame Mechanismen für effizienzsteigernde Programmtransformationen vermittelt.
1 Einleitung.- 2 Anforderungsanalyse.- 2.1 Ineffizienzen objektorientierter Programme.- 2.1.1 Ineffizienzen durch Abstraktion.- 2.1.2 Ineffizienzen durch anwendungsunabhängigen Entwurf.- 2.1.3 Ineffizienzen durch hohe Kontextabhängigkeit.- 2.2 Benötigte Optimierungen.- 2.2.1 Traditionelle Optimierungen.- 2.2.2 Elimination unnötiger Abstraktionen.- 2.2.3 Spezialisierung des anwendungsunabhängigen Entwurfs.- 2.2.4 Reduktion der Kontextabhängigkeit.- 2.3 Benötigte Programminformationen.- 2.3.1 Definitionen und Benutzungen.- 2.3.2 Partielle Ordnung und Abhängigkeiten.- 2.4 Approximation von Programminformationen.- 2.4.1 Numerische Werte.- 2.4.2 Variablen.- 2.4.3 Namensschemata.- 2.4.4 Aliasproblematik.- 2.4.5 Schwache Aktualisierung.- 2.4.6 Essentielle Abhängigkeiten.- 2.5 Beziehungen zwischen Programminformationen.- 2.6 Zusammenfassung.- 3 Stand von Forschung und Technik.- 3.1 Optimierungen.- 3.1.1 Optimierungsstrategien.- 3.1.2 Traditionelle Optimierungen.- 3.1.3 Elimination unnötiger Abstraktionen.- 3.1.4 Spezialisierung des anwendungsunabhängigen Entwurfs.- 3.1.5 Reduktion der Kontextabhängigkeit.- 3.2 Programmanalyse.- 3.2.1 Datenflußanalyse.- 3.2.2 Steuerflußanalyse, Typanalyse.- 3.2.3 Zeigeranalyse, Haldenanalyse.- 3.2.4 Genauigkeit und Aufwand.- 3.3 Programmrepräsentation.- 3.3.1 Grundblockgraph.- 3.3.2 Static Single Assignment Darstellungen.- 3.3.3 Ausgedünnte Repräsentationen.- 3.3.4 Ausnahmebehandlung.- 3.3.5 Abstraktionsniveau.- 3.4 Offene Probleme.- 4 Explizite Abhängigkeitsgraphen.- 4.1 Darzustellende Informationen.- 4.1.1 Operationen, Steuerfluß und Datenfluß.- 4.1.2 Speicherabbildung.- 4.1.3 Ausnahmen.- 4.1.4 Typinformationen und statisch initialisierte Daten.- 4.2 Syntax und Semantik expliziter Abhängigkeitsgraphen.- 4.2.1 Operationen und Abhängigkeiten.- 4.2.2 Speicherabhängigkeiten.- 4.2.3 Zugriffsfunktionen.- 4.2.4 Ausnahmen.- 4.2.5 Typinformationen.- 4.3 Aufbau aus der semantischen Analyse.- 4.3.1 Hilfsstrukturen.- 4.3.2 Bestimmung von Abhängigkeiten.- 4.3.3 Vermeidung unnötiger Phi-Operationen.- 4.3.4 Minimalität.- 4.3.5 Aufwand.- 4.4 Abbau der Darstellung.- 4.4.1 Transformation komplexer Operationen.- 4.4.2 Abbildung von Datenflußkanten.- 4.4.3 Auflösung von Phi-Operationen.- 4.5 Zusammenfassung.- 5 Programmanalyse über expliziten Abhängigkeitsgraphen.- 5.1 Analyse von Werten und Abhängigkeiten.- 5.1.1 Abstrakte Bereiche.- 5.1.2 Analyse von Variableninhalten und Ausdrücken.- 5.1.3 Bestimmung von Definitionen und Benutzungen.- 5.2 Beschleunigung der Konvergenz.- 5.2.1 Besuchsreihenfolge.- 5.2.2 Analyse über dem Schleifenbaum.- 5.3 Reduktion des Speicherbedarfs.- 5.3.1 Einsparungspotentiale.- 5.3.2 Bedarfsgesteuerte Analyse.- 5.3.3 Zusammenfassen von Operationen zu Gebieten.- 5.4 Modellierung kontextsensitiver Werte mit ?-Termen.- 5.4.1 Symbolische Darstellung kontextsensitiver Werte.- 5.4.2 ?-Terme als Entscheidungsdiagramme.- 5.4.3 Kontextsensitive Transferfunktionen über ?-Termen s.- 5.4.4 Erzwingen einer geeigneten Variablenordnung.- 5.5 Zusammenfassung.- 6 Optimierung expliziter Abhängigkeitsgraphen.- 6.1 Transformationen als Graphersetzung.- 6.1.1 Ersetzungsregeln.- 6.1.2 Gesteuerte Ersetzung.- 6.1.3 Effiziente Erhaltung von Identitäten.- 6.1.4 Normalisierung.- 6.2 Traditionelle Optimierungen.- 6.2.1 Konstantenfaltung und partielle Auswertung.- 6.2.2 Beseitigung von Kopien und totem Code.- 6.2.3 Globale Vermeidung redundanter Berechnungen.- 6.3 Beseitigung objektorientierter Ineffizienzen.- 6.3.1 Reduktion von Polymorphie und Prozeduraufrufen.- 6.3.2 Reduktion von Speicherzugriffen.- 6.3.3 Elimination dynamischer Objekterzeugungen.- 6.4 Reduktion nicht essentieller Abhängigkeiten.- 6.4.1 Verfeinerung des Namensschemas.- 6.4.2 Pfadverkürzung durch lokale Transformation.- 6.4.3 Globale Bestimmung essentieller Abhängigkeiten.- 6.5 Iterative optimierende Übersetzung.- 6.6 Zusammenfassung.- 7 Praktische Ergebnisse.- 7.1 Der Sather-K Übersetzer.- 7.2 Testprogramme.- 7.3 Messungen.- 7.4 Speichereffizienz von ?-Termen.- 7.5 Vergleich zu anderen Übersetzern.- 7.6 Diskussion.- 8 Zusammenfassung.- Literatur.- A Entscheidungsdiagramme.- A.1 Geordnete, binäre Entscheidungsdiagramme.- A.2 Größe von OBDDs.- A.3 Symbolisches Rechnen auf OBDDs.- A.4 Effiziente Implementierung.- A.5 Andere Typen von Entscheidungsdiagrammen.- B Beispielprogramme.
Objektorientierung ist eine der wesentlichen Techniken zur Realisierung von Softwaresystemen. Die unbestrittenen Vorteile dieses Ansatzes bei der Modellierung und Implementierung müssen jedoch häufig durch eine geringere Effizienz der so erstellten Programme erkauft werden. Dieses Buch vermittelt moderne Optimierungstechniken, die es Übersetzern für objektorientierte Programmiersprachen wie Sather, Java oder C sharp ermöglichen, automatisch effizientere ausführbare Programme zu erzeugen. Ausgehend von den speziellen Anforderungen an die Optimierung objektorientierter Programme werden in einem ganzheitlichen Ansatz geeignete übersetzerinterne Programmrepräsentationen, Algorithmen für deren globale Analyse und zielgerichtete Programmtransformationen zur Effizienzsteigerung vermittelt.
1 Einleitung.- 2 Anforderungsanalyse.- 2.1 Ineffizienzen objektorientierter Programme.- 2.2 Benötigte Optimierungen.- 2.3 Benötigte Programminformationen.- 2.4 Approximation von Programminformationen.- 2.5 Beziehungen zwischen Programminformationen.- 2.6 Zusammenfassung.- 3 Stand von Forschung und Technik.- 3.1 Optimierungen.- 3.2 Programmanalyse.- 3.3 Programmrepräsentation.- 3.4 Offene Probleme.- 4 Explizite Abhängigkeitsgraphen.- 4.1 Darzustellende Informationen.- 4.2 Syntax und Semantik expliziter Abhängigkeitsgraphen.- 4.3 Aufbau aus der semantischen Analyse.- 4.4 Abbau der Darstellung.- 4.5 Zusammenfassung.- 5 Programmanalyse über expliziten Abhängigkeitsgraphen.- 5.1 Analyse von Werten und Abhängigkeiten.- 5.2 Beschleunigung der Konvergenz.- 5.3 Reduktion des Speicherbedarfs.- 5.4 Modellierung kontextsensitiver Werte mit ?-Termen.- 5.5 Zusammenfassung.- 6 Optimierung expliziter Abhängigkeitsgraphen.- 6.1 Transformationen als Graphersetzung.- 6.2 Traditionelle Optimierungen.- 6.3 Beseitigung objektorientierter Ineffizienzen.- 6.4 Reduktion nicht essentieller Abhängigkeiten.- 6.5 Iterative optimierende Übersetzung.- 6.6 Zusammenfassung.- 7 Praktische Ergebnisse.- 7.1 Der Sather-K Übersetzer.- 7.2 Testprogramme.- 7.3 Messungen.- 7.4 Speichereffizienz von ?-Termen.- 7.5 Vergleich zu anderen Übersetzern.- 7.6 Diskussion.- 8 Zusammenfassung.- Literatur.- A Entscheidungsdiagramme.- A.1 Geordnete, binäre Entscheidungsdiagramme.- A.2 Größe von OBDDs.- A.3 Symbolisches Rechnen auf OBDDs.- A.4 Effiziente Implementierung.- A.5 Andere Typen von Entscheidungsdiagrammen.- B Beispielprogramme.
Inhaltsverzeichnis
1 Einleitung.- 2 Anforderungsanalyse.- 2.1 Ineffizienzen objektorientierter Programme.- 2.1.1 Ineffizienzen durch Abstraktion.- 2.1.2 Ineffizienzen durch anwendungsunabhängigen Entwurf.- 2.1.3 Ineffizienzen durch hohe Kontextabhängigkeit.- 2.2 Benötigte Optimierungen.- 2.2.1 Traditionelle Optimierungen.- 2.2.2 Elimination unnötiger Abstraktionen.- 2.2.3 Spezialisierung des anwendungsunabhängigen Entwurfs.- 2.2.4 Reduktion der Kontextabhängigkeit.- 2.3 Benötigte Programminformationen.- 2.3.1 Definitionen und Benutzungen.- 2.3.2 Partielle Ordnung und Abhängigkeiten.- 2.4 Approximation von Programminformationen.- 2.4.1 Numerische Werte.- 2.4.2 Variablen.- 2.4.3 Namensschemata.- 2.4.4 Aliasproblematik.- 2.4.5 Schwache Aktualisierung.- 2.4.6 Essentielle Abhängigkeiten.- 2.5 Beziehungen zwischen Programminformationen.- 2.6 Zusammenfassung.- 3 Stand von Forschung und Technik.- 3.1 Optimierungen.- 3.1.1 Optimierungsstrategien.- 3.1.2 Traditionelle Optimierungen.- 3.1.3 Elimination unnötiger Abstraktionen.- 3.1.4 Spezialisierung des anwendungsunabhängigen Entwurfs.- 3.1.5 Reduktion der Kontextabhängigkeit.- 3.2 Programmanalyse.- 3.2.1 Datenflußanalyse.- 3.2.2 Steuerflußanalyse, Typanalyse.- 3.2.3 Zeigeranalyse, Haldenanalyse.- 3.2.4 Genauigkeit und Aufwand.- 3.3 Programmrepräsentation.- 3.3.1 Grundblockgraph.- 3.3.2 Static Single Assignment Darstellungen.- 3.3.3 Ausgedünnte Repräsentationen.- 3.3.4 Ausnahmebehandlung.- 3.3.5 Abstraktionsniveau.- 3.4 Offene Probleme.- 4 Explizite Abhängigkeitsgraphen.- 4.1 Darzustellende Informationen.- 4.1.1 Operationen, Steuerfluß und Datenfluß.- 4.1.2 Speicherabbildung.- 4.1.3 Ausnahmen.- 4.1.4 Typinformationen und statisch initialisierte Daten.- 4.2 Syntax und Semantik expliziter Abhängigkeitsgraphen.- 4.2.1 Operationen und Abhängigkeiten.- 4.2.2 Speicherabhängigkeiten.- 4.2.3 Zugriffsfunktionen.- 4.2.4 Ausnahmen.- 4.2.5 Typinformationen.- 4.3 Aufbau aus der semantischen Analyse.- 4.3.1 Hilfsstrukturen.- 4.3.2 Bestimmung von Abhängigkeiten.- 4.3.3 Vermeidung unnötiger Phi-Operationen.- 4.3.4 Minimalität.- 4.3.5 Aufwand.- 4.4 Abbau der Darstellung.- 4.4.1 Transformation komplexer Operationen.- 4.4.2 Abbildung von Datenflußkanten.- 4.4.3 Auflösung von Phi-Operationen.- 4.5 Zusammenfassung.- 5 Programmanalyse über expliziten Abhängigkeitsgraphen.- 5.1 Analyse von Werten und Abhängigkeiten.- 5.1.1 Abstrakte Bereiche.- 5.1.2 Analyse von Variableninhalten und Ausdrücken.- 5.1.3 Bestimmung von Definitionen und Benutzungen.- 5.2 Beschleunigung der Konvergenz.- 5.2.1 Besuchsreihenfolge.- 5.2.2 Analyse über dem Schleifenbaum.- 5.3 Reduktion des Speicherbedarfs.- 5.3.1 Einsparungspotentiale.- 5.3.2 Bedarfsgesteuerte Analyse.- 5.3.3 Zusammenfassen von Operationen zu Gebieten.- 5.4 Modellierung kontextsensitiver Werte mit ?-Termen.- 5.4.1 Symbolische Darstellung kontextsensitiver Werte.- 5.4.2 ?-Terme als Entscheidungsdiagramme.- 5.4.3 Kontextsensitive Transferfunktionen über ?-Termen s.- 5.4.4 Erzwingen einer geeigneten Variablenordnung.- 5.5 Zusammenfassung.- 6 Optimierung expliziter Abhängigkeitsgraphen.- 6.1 Transformationen als Graphersetzung.- 6.1.1 Ersetzungsregeln.- 6.1.2 Gesteuerte Ersetzung.- 6.1.3 Effiziente Erhaltung von Identitäten.- 6.1.4 Normalisierung.- 6.2 Traditionelle Optimierungen.- 6.2.1 Konstantenfaltung und partielle Auswertung.- 6.2.2 Beseitigung von Kopien und totem Code.- 6.2.3 Globale Vermeidung redundanter Berechnungen.- 6.3 Beseitigung objektorientierter Ineffizienzen.- 6.3.1 Reduktion von Polymorphie und Prozeduraufrufen.- 6.3.2 Reduktion von Speicherzugriffen.- 6.3.3 Elimination dynamischer Objekterzeugungen.- 6.4 Reduktion nicht essentieller Abhängigkeiten.- 6.4.1 Verfeinerung des Namensschemas.- 6.4.2 Pfadverkürzung durch lokale Transformation.- 6.4.3 Globale Bestimmung essentieller Abhängigkeiten.- 6.5 Iterative optimierende Übersetzung.- 6.6 Zusammenfassung.- 7 Praktische Ergebnisse.- 7.1 Der Sather-K Übersetzer.- 7.2 Testprogramme.- 7.3 Messungen.- 7.4 Speichereffizienz von ?-Termen.- 7.5 Vergleich zu anderen Übersetzern.- 7.6 Diskussion.- 8 Zusammenfassung.- Literatur.- A Entscheidungsdiagramme.- A.1 Geordnete, binäre Entscheidungsdiagramme.- A.2 Größe von OBDDs.- A.3 Symbolisches Rechnen auf OBDDs.- A.4 Effiziente Implementierung.- A.5 Andere Typen von Entscheidungsdiagrammen.- B Beispielprogramme.
Klappentext
Objektorientierung ist eine der wesentlichen Techniken zur Realisierung von Softwaresystemen. Die unbestrittenen Vorteile dieses Ansatzes bei der Modellierung und Implementierung müssen jedoch häufig durch eine geringere Effizienz der so erstellten Programme erkauft werden. Dieses Buch vermittelt moderne Optimierungstechniken, die es Übersetzern für objektorientierte Programmiersprachen wie Sather, Java oder C# ermöglichen, automatisch effizientere ausführbare Programme zu erzeugen. Ausgehend von den speziellen Anforderungen an die Optimierung objektorientierter Programme werden in einem ganzheitlichen Ansatz geeignete übersetzerinterne Programmrepräsentationen, Algorithmen für deren globale Analyse und zielgerichtete Programmtransformationen zur Effizienzsteigerung vermittelt.
Die unbestrittenen Vorteile des objektorientierten Ansatzes bei Modellierung und Implementierung müssen häufig durch geringere Effizienz der so erstellten Programme erkauft werden. Dieses Buch vermittelt moderne Optimierungstechniken, die es Übersetzern für objektorientierte Programmiersprachen wie Sather, Java oder C# ermöglichen, automatisch effizientere ausführbare Programme zu erzeugen. Dabei werden in einem ganzheitlichen Ansatz zielgerichtet geeignete übersetzerinterne Programmrepräsentationen, Algorithmen für deren globale Analyse und wirksame Mechanismen für effizienzsteigernde Programmtransformationen vermittelt.
