Memory allocation methods for a DSP with indirect addressing modes and their application to compilers

For a DSP with address registers (ARs), which point memory addresses to be accessed, memory allocation methods to reduce overhead codes in accesses are discussed. In the existing heuristic method, variables in a program and AR operations are modeled by a graph, and modification of the graph according to a cost function leads to an efficient address location. In this paper, this method is iteratively applied and the most efficient address locations in sense of a cost function (sub-optimal locations) are derived. This iterative method is applied to the compiler for μPD77230 (NEC), and computational time for deriving efficient memory locations is proved to be relatively shorter than that of the exhaustive search method for the global optimal address locations. Second, a new cost function for the graph linearization algorithm which considers locality of addresses in memory accesses is proposed. This cost function is utilized in the compiler and an efficient address location, which is comparable to the optimal/sub-optimal allocations, is derived in a very short computational period