Graph Structure Theory in Compiler Construction

最近，基于树分解的方法控制流图（图结构理论中的一个概念）已被引入到编译器构造中的经典问题中，其中一些已在SDCC（一个用于嵌入式系统的免费主流C编译器）的实现中被证明是实用的。优化编译器包含优化，它试图改进生成的代码，使生成的程序更快，更小或更少的能量消耗。由于程序要从优化中受益，只需要使用优化编译器进行编译，因此编译器优化对真实的世界中的资源使用有着巨大而直接的影响。该项目的目标是进一步研究图结构理论在编译器构造中的应用。进一步研究控制流图的树分解的已知应用：图结构理论的所有当前已知应用都使用控制流图的树分解。应研究这些措施是否以及如何改进，特别是在运行时间和通用性方面。改进的限制应该通过硬度结果（NP-硬度，W-层次结构中的硬度）来澄清。树分解的进一步应用：使用树分解已经取得的成功建议将树分解应用于编译器构造中的进一步问题。要考虑的问题是，特别是冗余消除，放置在堆栈上的局部变量，过程抽象，和编程语言的影响，控制流图的树的宽度，以及获得树分解的有效方法。除了经典编译器中的图问题外，还应考虑在硬件综合中的应用。其他图结构参数和图：除了基于树分解的树宽之外，图结构理论还知道许多其他的图结构参数。应该调查，如果这些产生有用的应用程序在编译器建设也考虑图形以外的控制流图。

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.