Minimizing address arithmetic instructions in embedded applications on DSPs

Address arithmetic instructions constitute a big part of the generated code for digital signal processors (DSPs). Most modern digital signal processors (DSPs) provide multiple address registers and a dedicated address generation unit (AGU) which performs address generation in parallel to instruction execution. There is no address computation overhead if the next address is within the auto-modify range. A careful placement of variables in memory is utilized to reduce the number of address arithmetic instructions and thus generate compact and efficient code. The simple offset assignment (SOA) problem concerns the layout of variables for machines with one address register and the general offset assignment (GOA) deals with multiple address registers. Both these problems assume that each variable needs to be allocated for the entire duration of a program. Both SOA and GOA are NP-complete. In this article, we present effective solutions using simulated annealing (SA) for the simple and the general offset assignment problems with variable coalescing where two or more non-interfering variables can be mapped into the same memory location. Results on several benchmarks show the significant improvement from our proposed techniques compared to other heuristics in the literature.

Figure optionsDownload as PowerPoint slideHighlights
► We presented effective solutions to the offset assignment problem.
► We utilized variable coalescing to improve the quality of the final solution.
► We presented a new nontraditional approach to the general offset assignment with variable coalescing.
► A near optimal simulated annealing approach to this problem is presented which reduced the code size and the stack size.