Points-to Analysis By Type Inference of Programs with Structures and Unions

We present an interprocedural flow-insensitive points-to analysis algorithm based on monomorphic type inference. The source language model the important features of C including pointers, pointer arithmetic, pointers to functions, structured objects, and unions. The algorithm is based on a non-standard type system where types represent nodes and edges in a storage shape graph. This work is an extension of previous work on performing points-to analysis of C programs in almost linear time. This work makes three new contributions. The first is an extension of a type system for describing storage shape graphs to include objects with internal structure. The second is a constraint system that can deal with arbitrary use of pointers and which incorporates a two-tier domain of pointer offsets to improve the results of the analysis. The third is an efficient inference algorithm for the constraint system, leading to an algorithm that has close to linear time and space performance in practice.