Scalable and precise range analysis on the interval lattice

Abstract

A Range Analysis (RA) is an algorithm that estimates the lowest and highest values that each variable in a computer program may assume during an execution of the program. This kind of analysis provides information that helps the compiler to better understand and optimize programs. However, previous works rely on approaches that are either expensive or imprecise, limiting their application. In this work we present an implementation of a new range analysis that is currently among the best tools of its kind publicly available. Our implementation provides the best balance between speed and precision. By relying on an idea that we deem future values - a key insight of our algorithm - we produce fast results that are comparable to the precision of more expensive solutions.We also present the advantages of the application of our range analysis in different scenarios: 1. In computing security, to provide efficient protection against undefined behavior caused, for instance, by integer overflows or access beyond the bounds of an array. Integer overflow occurs when a variable assumes a value that does not fit in the precision of the data type used for the variable while array-bound errors occur when accesses to an array continue beyond the end of the array. Our RA was applied successfully to remove unnecessary safety verifications in programs, enhancing the performance of safe programs.2. In hardware design, to reduce the storage space and the wiring necessary to store a variable. RA can be used to prove that a given variable will not use the entire width of the data type assigned to it in the program. Therefore that variable can be stored into smaller registers and can use fewer lines to be transmitted between different areas of the processing element. The bitwidth reduction enabled by the RA produces faster programs that make a better use of the hardware and save energy.3. In static program analysis, to expand the scope and improve the precision of static analysis routinely applied to code by optimizing compilers. A more precise RA can be used to infer the outcome of conditional tests in a program. For instance, with proven range bounds for the value of variables, a dead-code elimination may be able to prove more code to be dead, a constant-propagation may be able to propagate constants further, and an alias analysis may be able to reduce the size of alias sets. More precise alias sets may enable further data restructuring and automatic parallelization transformations that make better use of the memory hierarchy and of multi-core processor architectures. Thus, this work pushes the state of the art of the range analysis into a new level and demonstrates that it can be successfully used by program optimizations to produce smaller and faster machine code.