Storage Assignment using Expression Tree Transformations to Generate Compact and Efficient DSP Code

DSP architectures typically provide dedicated memory address generation units and indirect addressing modes with auto-increment and decrement that subsume address arithmetic. The heavy use of auto-increment and autodecrement indirect addressing require DSP compilers to perform a careful placement of variables in storage to minimize address arithmetic instructions to generate compact and efficient DSP code. Liao et al. [7] have formulated the problem of storage assignment as a graph covering problem. The storage allocation of variables critically depends on the sequence of variable accesses. In this paper we present techniques to optimize the access sequence of variables by applying algebraic transformations (commutativity and associativity) on expression trees to minimize address arithmetic instructions. Based on these techniques, we propose heuristic algorithms that determine the optimized access sequence and its corresponding instruction schedule resulting in fewer address arithmetic..