Optimierung Objektorientierter Programme: Übersetzungstechniken, Analysen Und Transformationen

ISBN-13: 9783642639999 / Niemiecki / Miękka / 2011 / 198 str.

Martin Trapp

Opis

Objektorientierung ist eine der wesentlichen Techniken zur Realisierung von Softwaresystemen. Die unbestrittenen Vorteile dieses Ansatzes bei der Modellierung und Implementierung mussen jedoch haufig durch eine geringere Effizienz der so erstellten Programme erkauft werden. Dieses Buch vermittelt moderne Optimierungstechniken, die es Ubersetzern fur objektorientierte Programmiersprachen wie Sather, Java oder C# ermoglichen, automatisch effizientere ausfuhrbare Programme zu erzeugen. Ausgehend von den speziellen Anforderungen an die Optimierung objektorientierter Programme werden in einem ganzheitlichen Ansatz geeignete ubersetzerinterne Programmreprasentationen, Algorithmen fur deren globale Analyse und zielgerichtete Programmtransformationen zur Effizienzsteigerung vermittelt.

Spis treści

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.

Blurb

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.