Answers are grounded in this paper and cite their sources.
The problem of determining the points in a program at which variables are “live” (will be used again) is introduced and discussed. Two solutions, one which uses a simple iterative algorithm and one which uses an algorithm based on “Cocke–Allen interval” analysis, are presented and analyzed. These algorithms are compared on “self replicating“ families of reducible program flow graphs. The results are inconclusive in that the interval method requires fewer bit-vector steps on some graphs and more on others. If n is the number of nodes in a program flow graph and the number of edges is linearly proportional to n, then both algorithms require O(n² ) steps in the worst case.
No takes yet. Share an insight, caveat, or question.
Ken Kennedy (1976) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: