Building Approximate Calling Context from Partial Call Traces

We present an approach for building calling context information useful for program understanding, performance analysis and optimizations. Our approach exploits a lightweight profiling mechanism providing partial call traces. The goal is to reconstruct calling context information as accurately as possible, and to help the user navigate through it. We propose three steps to merge partial call traces into a smaller number of partial calling context trees. We intend to minimize errors such that the final partial contexts represent actual components of the real calling context tree with a very high probability. The first step concatenates call traces based on their common sequences. The second step converts call traces into partial calling context trees, and the last step merges partial context trees through maximal matching. To gauge how well the merged trees represent the full calling context tree, several criteria are presented. Our results indicate that call traces are successfully merged into a small number of large calling context trees. The merged trees are highly accurate.We have also developed a semi-automatic tool to navigate across partial calling context trees for program understanding and performance analysis purposes. Our results for several Java benchmarks show that our merging strategies exhibit a maximum 1% inaccuracy when compared to the exact solution.