Optimierung objektorientierter Programme

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.