首页> 外文会议>Modular Programming Languages >Graph Coloring vs. Optimal Register Allocation for Optimizing Compilers
【24h】

Graph Coloring vs. Optimal Register Allocation for Optimizing Compilers

机译:图形着色与优化寄存器分配以优化编译器

获取原文
获取原文并翻译 | 示例

摘要

Optimizing compilers play an important role for the efficient execution of programs written in high level programming languages. Current microprocessors impose the problem that the gap between processor cycle time and memory latency increases. In order to fully exploit the potential of processors, nearly optimal register allocation is of paramount importance. In the predominance of the x86 architecture and in the increased usage of high-level programming languages for embedded systems peculiarities and irregularities in their register sets have to be handled. These irregularities makes the task of register allocation for optimizing compilers more difficult than for regular architectures and register files. In this article we show how optimistic graph coloring register allocation can be extended to handle these irregularities. Additionally we present an exponential algorithm which in most cases can compute an optimal solution for register allocation and copy elimination. These algorithms are evaluated on a virtual processor architecture modeling two and three operand architectures with different register file sizes. The evaluation demonstrates that the heuristic graph coloring register allocator comes clos'e to the optimal solution for large register files, but performs badly on small register files. For small register files the optimal algorithm is fast enough to replace a heuristic algorithm.
机译:优化编译器对于高效执行以高级编程语言编写的程序起着重要作用。当前的微处理器提出了处理器周期时间和存储器等待时间之间的间隙增大的问题。为了充分利用处理器的潜力,几乎最佳的寄存器分配至关重要。在x86架构中占主导地位,以及在嵌入式系统中高级编程语言的日益使用中,必须处理其寄存器集中的特殊性和不规则性。这些不规则性使优化编译器的寄存器分配任务比常规体系结构和寄存器文件更加困难。在本文中,我们展示了如何扩展乐观图着色寄存器分配以处理这些不规则性。另外,我们提出了一种指数算法,该算法在大多数情况下可以计算出寄存器分配和复制消除的最佳解决方案。这些算法在虚拟处理器体系结构上进行评估,该体系结构对具有不同寄存器文件大小的两个和三个操作数体系结构进行建模。评估表明,启发式图形着色寄存器分配器接近了大型寄存器文件的最佳解决方案,但在小型寄存器文件上的性能很差。对于较小的寄存器文件,最佳算法足够快,足以取代启发式算法。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱:kefu@zhangqiaokeyan.com

京公网安备:11010802029741号 ICP备案号:京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有
  • 客服微信

  • 服务号