  Identifying the hottest paths in the control flow graph of a routine can
direct optimizations to portions of the code where most resources are consumed.
This powerful methodology, called path profiling, was introduced by Ball and
Larus in the mid 90s and has received considerable attention in the last 15
years for its practical relevance. A shortcoming of Ball-Larus path profiling
was the inability to profile cyclic paths, making it difficult to mine
interesting execution patterns that span multiple loop iterations. Previous
results, based on rather complex algorithms, have attempted to circumvent this
limitation at the price of significant performance losses already for a small
number of iterations. In this paper, we present a new approach to multiple
iterations path profiling, based on data structures built on top of the
original Ball-Larus numbering technique. Our approach allows it to profile all
executed paths obtained as a concatenation of up to k Ball-Larus acyclic paths,
where k is a user-defined parameter. An extensive experimental investigation on
a large variety of Java benchmarks on the Jikes RVM shows that, surprisingly,
our approach can be even faster than Ball-Larus due to fewer operations on
smaller hash tables, producing compact representations of cyclic paths even for
large values of k.
