| Abstract |
Pointer analysis is a major component of most static program analyses. Static pointer analysis has many uses like increasing the precision and efficiency of compiler optimizations, driving auto-parallelization, and bug-finding tools. Usually pointer analysis implementations target one given source language and take advantage of specific features of that language to increase precision, e.g., the type system, package system, or object inheritance mechanism. This, however, makes each implementation give different results with respect to precision and performance, and often requires a new implementation for each front-end of a multi-language compiler system. Conversely, implementing a pointer analysis for a compiler intermediate representation makes it more generic, while sacrificing precision that could have been achieved by working on the source-language abstraction level. This creates an interesting trade-off, where the optimal point would achieve maximum precision for the lowest-level language that is possible. This thesis presents the design and implementation of a static pointer analysis for the LLVM intermediate representation language. We implemented an extension of Andersen’s pointer analysis algorithm, broadly used to compute such information due to its scalability. The analysis is computed directly from the intermediate representation of LLVM, making it applicable to all languages that compile to the LLVM intermediate representation. The analysis is typebased, inter-procedural, flow-insensitive, and context-insensitive, following most applications of Andersen’s algorithm, with the extension of field-sensitivity for increased precision on struct types. Our algorithm is capable of responding to a full variety of alias analysis queries and can provide substantially more precision than the standard algorithm due to its field-sensitivity. Evaluated using three different suites of 20 open-source C programs ranging from 1K to 230K lines of source code, we demonstrate our technique and provide a qualitative evaluation towards other algorithmic approaches.
|
Static pointer analysis on intermediate representation for compilation optimizations
