Enabling code optimizations through hybrid analysis of memory access ranges

Abstract

Compilers implement a number of code optimizations that rely on precise memory-related information to generate efficient code. The effectiveness of such transformations is bound by the inherent imprecision of static methods designed to extract useful memory insights. We present a symbolic analysis that combines static and dynamic information to infer access bounds for memory operations. Our method is able to derive symbolic bounds for 98% of the memory accesses. We present two distinct clients. The first, a hybrid pointer disambiguation technique, uses our access range analysis to provide the compiler with more precise alias information, generating binaries that are 10% faster. The second, a framework that automatically annotates code for GPU execution, uses our memory range inference to generate directives capable of transferring data to the external device, allowing speedups of over 100x in an Nvidia architecture, and over 50x in an ARM architecture.