Graphstrukturtheorie im Übersetzerbau

• Antragsteller: Dr. Philipp Klaus Krause
• Fachliche Zuordnung: Theoretische Informatik ; Mathematik ; Rechnerarchitektur, eingebettete und massiv parallele Systeme ; Softwaretechnik und Programmiersprachen
• Förderung: Förderung von 2017 bis 2022
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 389550275

In letzter Zeit wurden für einige klassische Probleme im Übersetzerbau Ansätze, die auf den aus der Graphstrukturtheorie stammenden Baumzerlegungen aufbauen, gefunden. Die Ansätze verwenden Baumzerlegungen der Kontrollflussgraphen und zeigten teils ihre praktische Tauglichkeit in Implementierungen in SDCC, einem freien C-Compiler für Eingebettete Systeme.Optimierende Compiler enthalten Optimierungen, die den erzeugten Code schneller, kürzer oder energieeffizienter machen. Da Programme aller Art durch einfaches Übersetzen mit einem optimierenden Compiler von Optimierungen profitieren, und dadurch auf gegebener Hardware weniger Zeit, Energie und Speicher benötigen, beziehungsweise es ermöglichen, gegebene Aufgaben auf einfacherer Hardware zu erledigen, leisten diese einen bedeutenden Beitrag zur Reduzierung des Ressourcenverbrauchs.Ziel des Projekts ist die weitere Untersuchung von Anwendungen der Graphstrukturtheorie im Übersetzerbau.Weitere Untersuchung der bereits gefundenen Anwendungen der Baumzerlegungen der Kontrollflussgraphen:Alle bisher bekannten Anwendungen der Graphstrukturtheorie im Übersetzerbau verwenden Baumzerlegungen von Kontrollflussgraphen. Es soll untersucht werden, inwieweit sich diese verbessern lassen, in Hinsicht auf Laufzeit und Allgemeinheit. Die Grenzen an mögliche Verbesserungen sollen durch Schwereresultate (NP-Schwere, parametrisierte Schwere in der W-Hierarchie) genauer erkannt werden.Weitere Anwendungen der Baumzerlegungen:Die bisher mit Hilfe der Baumweite erzielten Erfolge legen nahe, Baumzerlegungen bei weiteren im Übersetzerbau auftretenden Problemen anzuwenden. Es sollen Baumzerlegungen verwendende Algorithmen für solche Probleme gefunden und implementiert werden. Die Grenzen an das dabei Mögliche sollen durch Schwereresultate genauer erkannt werden. Zu untersuchende Probleme sind insbesondere die Redundanzelimination, die Allokation von Variablen auf dem Stack, prozedurale Abstraktion, die bei verschiedenen Programmiersprachen auftretenden Baumweiten der Kontrollflussgraphen und effiziente Möglichkeiten, die Baumzerlegungen zu berechnen. Neben den in klassischen Compilern auftretenden Problemen sollen auch bei der Hardwaresynthese auftretende Probleme betrachtet werden.Andere Graphstrukturparameter und Graphen:Neben der über Baumzerlegungen definierten Baumweite gibt es in der Graphstrukturtheorie weitere Graphstrukturparameter, die sich aus anderen Aspekten von Graphen ergeben. Es soll untersucht werden, inwiefern sich diese für Anwendungen im Übersetzerbau eignen. Dabei sollen verschiedene im Übersetzerbau auftretenden Graphen (also nicht nur Kontrollflussgraphen) betrachtet werden.

• DFG-Verfahren: Sachbeihilfen