Optimal register allocation by augmented left-edge algorithm on arbitrary control-flow structures

A new algorithm for optimal register allocation in context of high-level synthesis is presented. In this paper we show how the greedy left-edge algorithm can be leveraged to obtain a globally optimal allocation, that is computed in polynomial time. By splitting variables at block boundaries, allows for allocation to be done using only quasi-local and local allocation - avoiding the complexity of true global allocation. As local allocation is much simpler than global allocation, this approach emphasizes efficiency and ease of implementation - at a cost of an increased number of register transfers compared to other allocators. Experiments show that runtime is linear for all practical purposes.