A comparison of some algorithms for live variable analysis

Abstract

A complete algorithm for computing acceptable assignments for the live variable problem in global program optimization is given which is a modification of an earlier algorithm due to Graham and Wegman. The complexity of the algorithm has been analysed on some self-replicating families of reducible flow graphs. It has been observed that there exists class of graphs for which algorithms of 0(nlog n) require more bit vector operations than algorithms of 0(n ²). A characterization of the flow graphs for which the procedure of Graham and Wegman is applicable for backward data flow propagation problems is also presented

Keywords:

• Compiler
• interval analysis
• live variables
• information propagation problem
• algorithmic complexity

C.R. Categories:

• 4.20
• 5.24
• 5.25
• 5.32