On the Minimization of Loads/Stores in Local Register Allocation
Journal
IEEE Transactions on Software Engineering
Journal Volume
15
Journal Issue
10
Pages
1252-1260
Date Issued
1989
Author(s)
Fischer, C.N.
Abstract
This paper presents an algorithm to find the optimal register allocation of straight-line programs. The basic approach is to search for a shortest path in a weighted DAG. The machine model used here is a load/store architecture, common in RISC machines. Although the weighted DAG grows exponentially in the worst case with the number of variables in the input program and the number of available registers. we provide rules to restrict the worst case to a very small domain. With the provided pruning rules, the optimal algorithm is used to evaluate how well heuristic algorithms perform for large basic blacks. We also present a heuristic algorithm which generally outperforms other algorithms in large basic blocks. © 1989 IEEE
Type
journal article