Graph Structure Theory in Compiler Construction

• Applicant: Dr. Philipp Klaus Krause
• Subject Area: Theoretical Computer Science ; Mathematics ; Computer Architecture, Embedded and Massively Parallel Systems ; Software Engineering and Programming Languages
• Term: from 2017 to 2022
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 389550275

• Final Report Year: 2022

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
  
• 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
  
• C for a tiny system, 2020
  Philipp K. Krause and Nicolas Lesser
  
• Constant-time connectivity tests, 2020
  Philipp K. Krause
  
• 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
  
• Efficient Calling Conventions for Irregular Architectures, 2021
  Philipp K. Krause
  
• 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