Premium
Optimizing stack frame accesses for processors with restricted addressing modes
Author(s) -
Hartley David H.
Publication year - 1992
Publication title -
software: practice and experience
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.437
H-Index - 70
eISSN - 1097-024X
pISSN - 0038-0644
DOI - 10.1002/spe.4380220202
Subject(s) - call stack , computer science , stack (abstract data type) , pointer (user interface) , parallel computing , offset (computer science) , frame (networking) , compiler , algorithm , computer hardware , programming language , telecommunications
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.