Graph Structure Theory in Compiler Construction
Mathematics
Computer Architecture, Embedded and Massively Parallel Systems
Software Engineering and Programming Languages
Final Report Abstract
In den letzten Jahren wurden einige Anwendungen der Graphstrukturtheorie bei Compileroptimierungen gefunden. 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. Der wichtigste Ansatz ist, für eine Programmiersprache zu zeigen, dass die Kontrollflussgraphen beschränkte Baumweite haben, und sich somit Baumzerlegungen kleiner Weite finden lassen. Diese Baumzerlegungen werden dann in effizienten Algorithmen für Compileroptimierungen genutzt. Wir haben für die weit verbreitete Programmiersprache C gezeigt, dass Funktionen, in denen höchstens g Sprungmarken für goto vorkommen, Kontrollflussgraphen von Baumweite höchstens 7 + g haben, und dass diese Schranke scharf ist. Wir zeigten wie sich Baumzerlegungen minimaler Weite für die Kontrollflussgraphen effizient berechnen lassen. Eine wichtige Compileroptimierung ist die Redundanzelimination, ein fortgeschrittener Ansatz ist dabei Lifetime-Optimale Spekulative Redundanzelimination (lospre). Für deterministische Implementierungen der beiden bisher hierzu verwendeten Algorithmen MC-PRE und MC-SSAPRE waren zuvor nur kubische Laufzeitschranken bekannt. Mittels Graphstrukturtheorie zeigten wir für C-Programme, die nur eine beschränke Anzahl an Sprungmarken für goto enthalten, eine quadratische Laufzeitschranke für MC-PRE und MC-SSAPRE. Für solche Programme entwickelten wir auch einen neuen Algorithmus für lospre, der lineare Laufzeit hat. Wir implementierten unsere Ansätze im Small Device C Compiler (SDCC), wo sie dazu beitragen, dass dieser freie Compiler für viele Zielarchitekturen oft besseren Code generiert als andere proprietäre Compiler. Daneben kam es zu zahlreichen kleineren Verbesserungen an und Beiträgen zu SDCC. Um unsere Ansätze mit bisherigen vergleichen zu können, entwickelten wir einen für die Zielarchitekturen von SDCC geeigneten Benchmark. Wir zeigten, dass die Anwendung des graphstrukturtheoretische „Irrelevant-Vertex“-Ansatz zum Disjunkte-Pfade-Problem beim Routing nicht erfolgversprechend ist. Daneben ergaben sich Erkenntnisse zu schnellen randomisierten Algorithmen zu Graphzusammenhangsproblemen.
Publications
- stdcbench - A Benchmark for Small Systems. In Proceedings of the 21st International Workshop on Software and Compilers for Embedded Systems, SCOPES ’18, page 43–46, New York, NY, USA, 2018. Association for Computing Machinery
Philipp K. Krause
(See online at https://doi.org/10.1145/3207719.3207726) - A lower bound on the tree-width of graphs with irrelevant vertices. Journal of Combinatorial Theory, Series B, 137(C):126–136, jul 2019
Isolde Adler and Philipp K. Krause
(See online at https://doi.org/10.1016/j.jctb.2018.12.008) - C for a tiny system, 2020
Philipp K. Krause and Nicolas Lesser
(See online at https://doi.org/10.48550/arXiv.2010.04633) - Constant-time connectivity tests, 2020
Philipp K. Krause
(See online at https://doi.org/10.48550/arXiv.2010.04527) - The tree-width of C. Discrete Applied Mathematics, 278:136–152, 2020. Eighth Workshop on Graph Classes, Optimization, and Width Parameters
Philipp K. Krause, Lukas Larisch, and Felix Salfelder
(See online at https://doi.org/10.1016/j.dam.2019.01.027) - Efficient Calling Conventions for Irregular Architectures, 2021
Philipp K. Krause
(See online at https://doi.org/10.48550/arXiv.2112.01397) - lospre in linear time. In Proceedings of the 24th International Workshop on Software and Compilers for Embedded Systems, page 35–41, New York, NY, USA, 2021. Association for Computing Machinery
Philipp K. Krause
(See online at https://doi.org/10.1145/3493229.3493304)
