Loading...
Please wait, while we are loading the content...
Similar Documents
ABSTRACT Bitwidth Aware Global Register Allocation
| Content Provider | CiteSeerX |
|---|---|
| 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 supporting 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 hindering accesses to these variables. However, a new register allocation algorithm is needed that is aware of the bitwidths of program variables 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 combination of forward and backward data flow analyses are developed to determine the bitwidths of program variables throughout the program. 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 program point to another. Second, a novel interference graph representation 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 allocation algorithm reduces the register requirements by 10 % to 50% over a traditional register allocation algorithm that assigns separate registers to simultaneously live subword variables. |
| File Format | |
| Access Restriction | Open |
| Subject Keyword | Program Variable Single Register Subword Variable Bitwidth Aware Register Allocation Algorithm Backward Data Flow Analysis Register Requirement Traditional Register Allocation Instruction Set Live Subword Variable Extensive Use Novel Interference Graph Representation Bit Section Register Allocation Full Data Word Traditional Node Coalescing Separate Register Accurate Algorithm True Bitwidths Subword Data Multiple Subword Variable Node Coalescing Phase New Register Allocation Algorithm Minimal Bitwidths Declared Bitwidths Key Step Direct Referencing Multiple Subword Conventional Graph Program Point Network Processing Application |
| Content Type | Text |
| Resource Type | Article |
