A Static-Dynamic Collaborative Framework for Nested Loops Instrumentation and Profiling

Runtime information extraction is usually achieved using some code instrumentations, where additional instructions are inserted in order to collect relevant values as accessed memory locations, reached variable values or taken branches. In order to minimize the time overhead, a usual strategy is to run instrumented code exclusively during some execution time samples. Hence an intended dynamic mechanism has to provide a way to alternate quickly between instrumented and non-instrumented code, without altering the code semantics. Since loop nests usually represent a major part of the whole execution time of programs, they are important optimization targets. Obviously, since their statements are run many times, the time overhead induced from instrumentation is even more difficult to minimize. In this paper, we present a static-dynamic collaborative framework dedicated to nested loops. Its goal is to catch some linearity of the performed memory accesses and of the loop trip counts, serving as a launching point for further optimizations as data prefetching or speculative parallelization. Interesting cases in instrumentation are revealed by indirect memory accesses or pointer arithmetic based accesses, as they cannot be determined statically. Our framework introduces a new pragma inserted in the higher level source code and delimiting the regions for instrumentation. Next, it extends the LLVM compiler to process the marked regions and statically create an instrumented version of the code. For a minimal time overhead, we use a sampling strategy where we instrument the first iterations of each loop of the considered nest. At runtime, the executions of instrumented and non-instrumented versions alternate, thanks to a runtime system which guides the execution flow by patching the binary code. Based on the acquired information related to accessed memory addresses and loop trip counts, the runtime system interpolates on the loop indices to identify linear functions