Optimizing stack frame accesses for processors with restricted addressing modes

Abstract Random access to local variables stored in a stack frame is more difficult for compiled functions when the target processor lacks register‐plus‐offset addressing. One alternative technique employs a roving pointer which the program increments or decrements as needed between stack accesses. Processors which support auto‐increment and auto‐decrement addressing modes are often capable of performing these increments for free when consecutive accesses are to adjacent stack locations. For these processors, the compiler's chosen ordering for the local variables in the stack frame can substantially affect the execution speed of the compiled program. This paper is concerned with finding an ordering for the local variables in the frame that maximizes the likelihood that two consecutive references at run‐time will be to the same or to adjacent stack locations. We have formulated a solution to this problem in terms of finding a Hamiltonian path in a graph. Although this problem is NP‐complete in general, we have developed a heuristic algorithm that delivers good results with acceptable performance.