  When a program is loaded into memory for execution, the relative position of
its basic blocks is crucial, since loading basic blocks that are unlikely to be
executed first places them high in the instruction-memory hierarchy only to be
dislodged as the execution goes on. In this paper we study the use of Bayesian
networks as models of the input history of a program. The main point is the
creation of a probabilistic model that persists as the program is run on
different inputs and at each new input refines its own parameters in order to
reflect the program's input history more accurately. As the model is thus
tuned, it causes basic blocks to be reordered so that, upon arrival of the next
input for execution, loading the basic blocks into memory automatically takes
into account the input history of the program. We report on extensive
experiments, whose results demonstrate the efficacy of the overall approach in
progressively lowering the execution times of a program on identical inputs
placed randomly in a sequence of varied inputs. We provide results on selected
SPEC CINT2000 programs and also evaluate our approach as compared to the gcc
level-3 optimization and to Pettis-Hansen reordering.
