An Effective Heuristic for Simple Offset Assignment with Variable Coalescing
Hassan Salamy and J. (Ram) Ramanujam
The 19th International Workshop on Languages and Compilers for Parallel Computing (LCPC 2006)
New Orleans, Louisiana, November 2-4, 2006
Abstract
In many Digital Signal Processors (DSP) with limited memory, programs are loaded in the ROM and thus the size of the program is extremely important. For this reason, it is very important to optimize the size of the code and thus optimize memory requirement. Many DSP processors include address generation units (AGUs) that can perform address arithmetic in parallel to instruction execution. This architecture supports address auto-increment and auto- decrement without the need of an extra instruction. A lot of research has been conducted to optimize the order of the variables in memory to get the most benefit from auto-increment and auto-decrement. Researchers studied this problem as simple offset assignment (SOA) where there is only one address register and as general offset assignment (GOA) where there are multiple address registers, both under the assumption that each variable needs to be allocated for the entire duration of a program. Both SOA and GOA are NP-complete. In this paper we present a heuristic for SOA that considers coalescing two or more variables into the same memory location. SOA with variable coalescing is intended to decrease the cost of address arithmetic instructions as well as to decrease the memory requirement for variables by maximizing the number of variables mapped to the same memory slot. Results on the several benchmarks show the significant improvement of our solution compared to other heuristics. In addition, we have adapted simulated annealing to further improve the solution from our heuristic.