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

Recently, approaches based on tree-decompositions (a concept from graph-structure theory) of control-flow graphs have been introduced for classical problems in compiler construction, some of which have proven their practical usefulness in implementations in SDCC, a free mainstream C compiler for embedded systems.Optimizing compilers contain optimization, which attempt to improve the generated code, to make the resulting program faster, smaller or less energy-consuming. Since all it takes for a program to benefit from optimizations is being compiled with an optimizing compiler, compiler optimizations have a huge, immediate effect on resource usage in the real world.The goal of the project is further research into applications of graph-structure theory in compiler construction.Further research on known applications of tree-decompositions of control-flow graphs:All currently known applications of graph-structure theory use tree-decompositions of control-flow graphs. It should be investigated if and how these can be improved in particular with respect to runtime and generality. The limits of improvements should be clarified by hardness results (NP-hardness, hardness in the W-hierarchy).Further applications of tree-decompositions:The successes already achieved using tree-decompositions suggest applying tree-decompositions to further problems in compiler construction. The problems to be considered are in particular redundancy elimination, placement of local variables on the stack, procedural abstraction, and the influence of programming languages on the tree-width of control-flow graphs as well as efficient methods of obtaining tree-decompositions. Besides graph problems in classical compilers, also applications in hardware synthesis should be considered.Other graph-structure parameters and graphs:Besides tree-width, which is based on tree-decompositions, graph-structure theory knows many other graph-structure parameters. It should be investigated if these yield useful applications in compiler construction also considering graphs other than control-flow graphs.

• DFG Programme: Research Grants