TY - JOUR
T1 - Validating register allocations for straight line programs
AU - Sethi, Ravi
N1 - Funding Information:
#This research was partially NSF Grant GJ-1052
Publisher Copyright:
© 1972 Association for Computing Machinery. All rights reserved.
PY - 1972/5/1
Y1 - 1972/5/1
N2 - Straight line programs are essentially sequences of assignment statements. A general program consists of straight line segments with flow of control between these segments. The interfaces between a straight line segment and the rest of the program place constraints on register allocations for the segment. These constraints may render a register allocation for a straight line program unrealizable. An algorithm is given to determine if a register allocation for a straight line program is realizable. It is shown that the algorithm takes O(n 3 ) steps, where n is the number of statements in the program. An unrealizable assignment may be made realizable by introducing stores into memory at appropriate points. It is shown how the minimum number of such stores may be found.
AB - Straight line programs are essentially sequences of assignment statements. A general program consists of straight line segments with flow of control between these segments. The interfaces between a straight line segment and the rest of the program place constraints on register allocations for the segment. These constraints may render a register allocation for a straight line program unrealizable. An algorithm is given to determine if a register allocation for a straight line program is realizable. It is shown that the algorithm takes O(n 3 ) steps, where n is the number of statements in the program. An unrealizable assignment may be made realizable by introducing stores into memory at appropriate points. It is shown how the minimum number of such stores may be found.
UR - http://www.scopus.com/inward/record.url?scp=85059439315&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85059439315&partnerID=8YFLogxK
U2 - 10.1145/800152.804918
DO - 10.1145/800152.804918
M3 - Conference article
AN - SCOPUS:85059439315
SP - 222
EP - 237
JO - Proceedings of the Annual ACM Symposium on Theory of Computing
JF - Proceedings of the Annual ACM Symposium on Theory of Computing
SN - 0737-8017
T2 - 4th Annual ACM Symposium on Theory of Computing, STOC 1972
Y2 - 1 May 1972 through 3 May 1972
ER -