Profitability computations on program flow graphs

The "profitability" of code optimizations is defined in terms of a Markov model of program flow. A system of linear equations for the expected frequency of execution of blocks of a program is derived. A solution method which uses "Cocke-Allen interval" analysis is presented and extensions of this method to other global flow analysis problems are described. © 1976.