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.