Register allocation is a major step for all compilers. Various register allocation algorithms have been developed over the dec- ades. This work describes a new class of rapid register allocation algorithms and present...Register allocation is a major step for all compilers. Various register allocation algorithms have been developed over the dec- ades. This work describes a new class of rapid register allocation algorithms and presents experimental data on their behavior. Our re- search encourages the avoidance of graphing and graph-coloring based on the fact that precise graph-coloring is nondeterministic poly- nomial time-complete （NP-complete）, which is not suitable for real-time tasks. In addition, practical graph-coloring algorithms tend to use polynomial-time heuristics. In dynamic compilation environments, their super linear complexity makes them unsuitable for register allocation and code generation. Existing tools for code generation and register allocation do not completely fulfill the requirements of fast compilation. Existing approaches either do not allow for the optimization of register allocation to be achieved comprehensively with a sufficient degree of performance or they require an unjustifiable amount of time and/or resources. Therefore, we propose a new class of register allocation and code generation algorithms that can be performed in linear time. These algorithms are based on the mathematic- al foundations of abstract interpretation and the computation of the level of abstraction. They have been implemented in a specialized library for just-in-time compilation. The specialization of this library involves the execution of common intermediate language （CIL） and low level virtual machine （LLVM） with a focus on embedded systems.展开更多
文摘Register allocation is a major step for all compilers. Various register allocation algorithms have been developed over the dec- ades. This work describes a new class of rapid register allocation algorithms and presents experimental data on their behavior. Our re- search encourages the avoidance of graphing and graph-coloring based on the fact that precise graph-coloring is nondeterministic poly- nomial time-complete （NP-complete）, which is not suitable for real-time tasks. In addition, practical graph-coloring algorithms tend to use polynomial-time heuristics. In dynamic compilation environments, their super linear complexity makes them unsuitable for register allocation and code generation. Existing tools for code generation and register allocation do not completely fulfill the requirements of fast compilation. Existing approaches either do not allow for the optimization of register allocation to be achieved comprehensively with a sufficient degree of performance or they require an unjustifiable amount of time and/or resources. Therefore, we propose a new class of register allocation and code generation algorithms that can be performed in linear time. These algorithms are based on the mathematic- al foundations of abstract interpretation and the computation of the level of abstraction. They have been implemented in a specialized library for just-in-time compilation. The specialization of this library involves the execution of common intermediate language （CIL） and low level virtual machine （LLVM） with a focus on embedded systems.
