An algorithm for tracing live variables based on a straightened program graph

Abstract

An algorithm is given for finding where the variables of a program are active or live. While the algorithm is modeled after that of Kennedy, it is based on the flow graph straightening procedure of Earnest, Balke, and Anderson, rather than on Cocke-Allen intervals. Thus it can be applied to any program, without appeal to any additional mechanism such as node splitting.

Keywords:

• control flow graphs
• compiler optimization
• data flow analysis
• program graphs
• global register allocation

C.R. Categories:

• 4.12
• 5.14
• 5.32
• 5.39