Optimierung in Übersetzern (PS-OiÜ)7.5 ECTS
(englische Bezeichnung: Optimizations in Compilers)
(Prüfungsordnungsmodul: Optimierung in Übersetzern)

Lehrveranstaltungen:

• • Optimierungen in Übersetzern
    (Vorlesung, 2 SWS, Michael Philippsen, Mi, 8:15 - 9:45, H4)
  • Übungen zu Optimierungen in Übersetzern
    (Übung, 2 SWS, Patrick Kreutzer)

Inhalt:

In der Vorlesung werden ausgewählte Kapitel aus dem Übersetzerbau besprochen.
Schwerpunktmäßig werden Optimierungstechniken für die Übersetzung imperativer Programmiersprachen diskutiert, insbesondere solche, die für Hochleistungsrechner und Parallelrechner von Bedeutung sind. Begleitend dazu werden einige oft verwendete Techniken und Repräsetationsformen vorgestellt, die erforderlich sind, um die zur Optimierung benötigten Informationen geeignet zu berechnen bzw. zu verwalten.

Themen der Vorlesung:

• Abhängigkeitsanalyse (Kontrollflussgraph, Dominatoren)

• Schleifentransformationen

• Schleifenumordnungen

• Schleifenrestrukturierung

• Speicherzugriffstransformationen

• Partielle Auswertung

• Redundanzentfernung

• Prozeduraufruftransformationen

• Optimierungen für Parallelrechner

• Pointer- und Aliasanalyse
  

Themen der Übung:

• In den Tafelübungen werden die in der Vorlesung vorgestellten Themen anhand von Übungsaufgaben angewendet und vertieft.

• Zusätzlich erweitern die Studierenden in Zweiergruppen einen Übersetzer für eine Beispielprogrammiersprache um einige der in der Vorlesung vorgestellten Optimierungstechniken. Ziel ist es, am Ende des Semesters einen optimierenden Übersetzer zu haben, der effizienten Code erzeugen kann.

Lernziele und Kompetenzen:

Die Studierenden

• entfernen unnötige Anweisungen mittels lokal wirkender Optimierungen

• konstruieren den Kontrollflussgraphen für gegebenen Code

• wenden den Fixpunktalgorithmus zur Berechnung der Dominanz in Kontrollflussgraphen an

• wenden den Lengauer-Tarjan-Algorithmus zur Berechnung der Dominanz in Kontrollflussgraphen an

• konstruieren den Dominatorbaum für einen Kontrollflussgraphen

• berechnen die Dominanzgrenzen für die Knoten eines Kontrollflussgraphen

• bestimmen die Kontrollflussabhängigkeiten der Knoten eines Kontrollflussgraphen

• wenden einen Fixpunktalgorithmus zur Bestimmung von Datenflusswissen an

• adaptieren den Fixpunktalgorithmus für neue Datenflussprobleme

• weisen die Korrektheit des Fixpunktalgorithmus zur Datenflussberechnung nach

• bestimmen lebendige Variablen und verfügbare Ausdrücke in einem Kontrollflussgraphen

• begründen die Legalität durchgeführter Optimierungstechniken

• überführen ein gegebenes Programm mit Hilfe des Dominanzgrenzenverfahrens in seine SSA-Form

• überführen ein gegebenes Programm mit Hilfe des Wertnummerierungsverfahrens in seine SSA-Form

• wenden SSA-basierte Optimierungstechniken an

• optimieren ein gegebenes Programm mittels Kopienfortschreibung und Konstantenweitergabe

• entfernen redundante Berechnungen aus Programmen

• entfernen toten oder unerreichbaren Code aus Programmen

• transformieren Programme in SSA-Form wieder aus dieser heraus

• erläutern die Notwendigkeit von Alias-Analysen in optimierenden Übersetzern

• kennen verschiedene Arten von Alias-Analysen

• bestimmen Aliase mit Hilfe eines Fixpunktalgorithmus

• bestimmen Aliase mit Hilfe des Steensgaard-Algorithmus

• unterscheiden natürliche von unnatürlichen Schleifen

• analysieren, ob ein Programm unnatürliche Schleifen beinhaltet

• erkennen natürliche Schleifen in einem Kontrollflussgraphen

• bestimmen Induktionsvariablen von Schleifen

• eliminieren Induktionsvariablen durch eine Reduktion der Ausdrucksstärke

• bestimmen schleifeninvarianten Code und ziehen diesen, falls möglich, vor die jeweilige Schleife

• erkennen schleifenunabhängige und schleifenabhängige Abhängigkeiten

• bestimmen Abhängigkeitsdistanzen

• wenden die Fourier-Motzkin-Elimination zur Index-Analyse an

• analysieren, ob eine Schleife parallelisierbar ist

• weisen die Legalität von Schleifentransformationen nach und wenden diese, falls möglich, an

• weisen die Legalität von Schleifenrestrukturierungen nach und wenden diese, falls möglich, an

• wenden Unimodulare Transformationen von Schleifen an

• wandeln mittels Schleifenneuausrichtung und Skalarvervielfachung schleifengetragene Abhängigkeiten in schleifenunabhängige Abhängigkeiten um

• verbessern ihre Fähigkeit, effizienten Code zu schreiben

• erläutern die Möglichkeiten und Grenzen unterschiedlicher Optimierungstechniken

Literatur:

• Aho, Lam, Sethi, Ullman: Compiler- Principles, Techniques, Tools

• S. Muchnick: Advanced Compiler Design&Implementation

• M. Wolfe: High Performance Compilers for Parallel Computing
  

Verwendbarkeit des Moduls / Einpassung in den Musterstudienplan:

1. Computational Engineering (Rechnergestütztes Ingenieurwesen) (Master of Science)
   (Po-Vers. 2013 | TechFak | Computational Engineering (Rechnergestütztes Ingenieurwesen) (Master of Science) | Gesamtkonto | Wahlpflichtbereich Informatik | Wahlpflichtbereich Informatik | Optimierung in Übersetzern)

Studien-/Prüfungsleistungen:

Optimierungen in Übersetzern (Prüfungsnummer: 42311)

(englischer Titel: Optimizations in Compilers)

Prüfungsleistung, mündliche Prüfung, Dauer (in Minuten): 30, benotet

Anteil an der Berechnung der Modulnote: 100.0 %

weitere Erläuterungen:
ACHTUNG: Falls erforderlich, findet die Prüfung gemäß Corona-Satzung der FAU in elektronischer/digitaler Form als Videokonferenz statt! Voraussetzung zur Teilnahme an dieser Prüfung ist die erfolgreiche Bearbeitung der Übungsaufgaben.

Prüfungssprache: Deutsch

Erstablegung: SS 2021, 1. Wdh.: WS 2021/2022

1. Prüfer:

Michael Philippsen

Ort: 26.7.: Martensstr. 3, Raum 00.152-113; 12.10.+14.10.: Martensstr. 1, Raum 0.031-113