Abstract
Digital Signal Processors (DSPs) are a family of embedded processors designed under tight memory, area, and cost constraints. Many DSPs use irregular addressing modes where base-plus-offset mode is not supported. However, they often have Address Generation Units (AGUs) that can perform auto-increment/decrement address arithmetic instructions in parallel with Load/Store instructions. This feature can be utilized to reduce the number of explicit address arithmetic instructions and thus reduce the embedded application code size. This code size reduction is essential for this family of DSP as the code usually resides in the ROM and hence the code size directly translates into silicon area. An effective technique for optimized code generation is offset assignment. This is a well-used technique in the literature to decrease the code size by finding an offset assignment that can effectively utilize auto-increment/decrement. This problem is known as simple offset assignment when there is only one address register and as General Offset Assignment (GOA) for multiple available address registers. In this article, we present an optimal Integer Linear Programming (ILP) solution to the offset assignment problem with variable coalescing where more than one variable can share the same memory location. Variable permutation is also formulated to find the best access sequence to achieve the best offset assignment that decreases the code size the most. Experimental results on several benchmarks show the effectiveness of our variable permutation technique as well as the large improvement from the ILP-based solutions compared to heuristics.