Graph Structure Theory in Compiler Construction

编译器构建中的图结构理论

• 批准号: 389550275
• 负责人: Dr. Philipp Klaus Krause
• 金额: --
• 依托单位: Institut für Informatik (IIF)
• 依托单位国家: 德国
• 项目类别: Research Grants
• 财政年份: 2017
• 资助国家: 德国
• 起止时间: 2016-12-31 至 2021-12-31
• 项目状态: 已结题
• 来源: https://gepris.dfg.de/gepris/projekt/389550275?language=en
• 关键词: Graph; Structure; Theory; Compiler; Construction

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.

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

项目成果

A lower bound on the tree-width of graphs with irrelevant vertices

• DOI: 10.1016/j.jctb.2018.12.008
• 发表时间: 2019-01
• 期刊: J. Comb. Theory B
• 作者: Isolde Adler;P. K. Krause

stdcbench: A Benchmark for Small Systems

stdcbench：小型系统的基准

• DOI: 10.1145/3207719.3207726
• 发表时间: 2018
• 期刊: Proceedings of the 21st International Workshop on Software and Compilers for Embedded Systems
• 作者: Philipp K. Krause

lospre in linear time

以线性时间开始

• DOI: 10.1145/3493229.3493304
• 发表时间: 2021
• 期刊: Proceedings of the 24th International Workshop on Software and Compilers for Embedded Systems
• 作者: Philipp K. Krause