Context-aware code optimization

A program segment such as a function or a basic block sequence may display different behaviors during the execution of the program. For example, a basic block sequence may consistently show few cache misses during the first 10 times it is executed, while the same basic block sequence may experience high number of cache misses when the sequence is invoked in the next 100 times. The divergence within the runtime behavior of program segment implies that different optimization choices should be made even for a single code segment if it shows different behaviors under different runtime contexts. However, traditional compilation technique rarely, if ever, takes advantage of that optimization opportunity. This concept is different from the finding of hot path, which has been done in both static compilation and dynamic optimization, whose purpose is to find the most frequently executed code segment and then to apply more aggressive and more expensive optimizations on that code segment. For the most part, behavior divergence other than execution frequency is not a factor in the determination of which optimizations to be applied to the segment. In this paper, we propose a novel feedback-driven program optimization technique that profiles and determines the runtime behaviors of code segments in a program to find the different patterns of behavior, correlates different runtime behaviors of a program segment with its program source code, and uses an empirical search method to customize the choice of optimization for same program segments under different runtime behaviors. We implement our optimization technique in LLVM and test our approach with SPEC2000 and SPEC2006 benchmarks. The preliminary results show promising performance improvement compared with the standard optimization settings used by the benchmarks.