Storage assignment optimizations through variable coalescence for embedded processors
Modem embedded. processors with dedicated address generation unit support memory access with indirect addressing mode with auto-increment and decrement. The auto-increment/decrement mode saves address arithmetic instructions. Liao et al [2][3] categorized this problem as simple offset assignment (SOA) problem and general offset assignment (GOA) problem, which involve storage layout of variables and assignment of address registers respectively proposing heuristic solutions. Later work [6][7] proposed improvements in the performance of Liao's solution by undertaking program and storage transformations that affect access sequence. In this paper, we propose a new approach of variable coalescence, which can reduce both instruction segment and data segment size and improve the utilization of automatic address register modification. Variable coalescence combines been observed in terms of code. and data size reduction, SOA and GOA cost reduction and dynamic cycle reduction. Variables not interfering with other (not simultaneously live at any program point) into the same memory location. Coalescing allows simplifications of the access graph yielding better SOA solutions or can perhaps lead to such a few uncoalesceable memory locations that GOA solutions for them are optimal. Moreover, it can reduce the program footprint both statically and at runtime (for stack variables) in terms of data segments. Variable coalescence is orthogonal to other solutions proposed; performing variable coalescence first and then solving the SOA or GOA problem with other techniques leads to excellent solutions. In this work, we have successfully applied it to both SOA and GOA problem. The algorithms are incorporated into and evaluated on the commercial compiler provided by Motorola to boost code generation performance on the DSP 56k chip. Compared to previous approaches, variable coalescence with program reordering reduces SOA costs by 48% and GOA (2AR) costs by 66% for Mediabench and SPEC benchmarks. Moreover, we show that our approach obtains theoretically optimal solution (zero cost) for the GOA problem in 87% of the cases with just 2 address registers and in 94% of the cases with 3 address registers.
storage assignment variable coalescence soa goa performance design