Address Register Allocation in Digital Signal Processors

It is important in signal processing to optimize a code inside loops. In most programs, addressing computation accounts for a large fraction of an execution time. From the fact that typical DSP programs access massive amounts of data, it is easy to conclude that handling addressing computation properly in DSP domain is a more important subject than in general purpose computing in order to achieve a compact code with real-time performance. In this paper, we develop an algorithm that can eliminate an explicit use of address register instructions in a loop and find a lower bound on the number of ARs by finding strongly connected components (SCCs) of an extended graph.