Optimum register assignment for heterogeneous register-set architectures

This paper focuses on the register assignment problem for basic blocks assuming a given instruction schedule. This is equivalent to the well-known coloring of an interference graph which satisfies the interval graph properties if no other constraints are considered. For a set of equivalent colors (homogeneous registers), an interval graph is colorable with linear complexity. In contrast, however, we assume a heterogeneous register-set as often found in general purpose digital signal processors. In this case, register assignment corresponds to a list-coloring problem which is NP-complete even for interval graphs. Topically, heuristics have to be applied. However, we present a search space pruning technique based on a graph decomposition into maximum cliques that allows us to find proper colorings if there are any. Our optimum technique is applicable even to large graphs since the maximum number of colorings that have to be investigated just depend on the maximum clique size.