Bitwidth aware global register allocation

Abstract

Multimedia and network processing applications make extensive use of subword data. Since registers are capable of holding a full data word, when a subword variable is assigned a register, only part of the register is used. New embedded processors have started sup-porting instruction sets that allow direct referencing of bit sections within registers and therefore multiple subword variables can be made to simultaneously reside in the same register without hinder-ing accesses to these variables. However, a new register allocation algorithm is needed that is aware of the bitwidths of program vari-ables and is capable of packing multiple subword variables into a single register. This paper presents one such algorithm. The algorithm we propose has two key steps. First, a combina-tion of forward and backward data flow analyses are developed to determine the bitwidths of program variables throughout the pro-gram. This analysis is required because the declared bitwidths of variables are often larger than their true bitwidths and moreover the minimal bitwidths of a program variable can vary from one pro-gram point to another. Second, a novel interference graph represen-tation is designed to enable support for a fast and highly accurate algorithm for packing of subword variables into a single register. Packing is carried out by a node coalescing phase that precedes the conventional graph coloring phase of register allocation. In contrast to traditional node coalescing, packing coalesces a set of interfering nodes. Our experiments show that our bitwidth aware register allo-cation algorithm reduces the register requirements by 10 % to 50% over a traditional register allocation algorithm that assigns separate registers to simultaneously live subword variables.