In the general case, the exact number of times a certain part in a program is executed can be determined once the probability of taking each branch in the program is known [Knu73]. This observation has lead to the idea of applying the Markov analysis technique to the flow graph of a program ([Ram65], [Tri82], [Wag94]).

A program flow graph consists of a set of nodes called *basic blocks* that
are connected by arcs referred to as *branches* [Aho86].
When using Markov analysis, the flow graph of a program is mapped onto a
finite Markov chain. Each basic block in the flow graph corresponds to a
*state* of the Markov chain, and each branch corresponds to a *transition* of the
Markov chain. The probability of taking a branch is then equivalent to the
*transition probability* of the corresponding transition in the Markov chain.

Let be the number of basic blocks in the flow graph, and let be the probability that control passes from basic block to basic block . It can be shown [Tri82] that the number of times that each of the basic block is visited can be calculated by solving the following system of linear equations: where for i=j, and otherwise.

Wed Aug 9 15:22:05 MET DST 1995