We present m interprocedural flow-lnsensltlve points-to rmalysls based on type ]nference methods with an almost hneart ime cost complexity To our knowled~e, this is the asymptotically fastest non-trlwzd lnterprocedural points-to analysis algorlthm yet described The al,gotnthm IS bmedona non-standard type system. The type Inferred for any wmable l-epl-esents a set of locations and includes a type which in turn represents a set ot' locations possibly pointed to by the variable. Thetype inferred for a function variable l-epresents a set of functions It may point to and Includes a type signature for these functions Theresults ztre equivalent tothoseof a flowinsensitive alias analysis (and control flow analysls) that assumes alias relations arereflexlve andtransltive. This work makes three contributions The first isatype system for describing a umversally valid storage shape graph for a program in linear space. The second is a constraint system which often leads to bettel-l-esults than the''obvious" constraint system for the gyven type system The third is an almost llneal-time algolnthm for points-to analysls by solwng a constraint system Most current compilel-s and programming tools use only intraprocedural analyses, asthepolynomlal tlmeand space complexIty of the common data-flow based analyses pi-events the use of interprocedural analyses for large programs. Intel-procedural analyslslsbecoming increasingly important, asitlsnecessary to support whole-program optimization and various program understanding tools. Previously published Interprocedural analysis algorithms have not been reported to have been successfully applied to programs around 100,000 lines of C code (the published results are practically all forless than 10,0001 inesof Ccode). Permission to make digital/hard copies of all or part of this mriterial for personal or claasroom use ia granted witbout fee provided that the copies arenotmade or distributed forprofit orcommercial advrmtage, the copyright notice, the title of the publication and its date appear, and notice is given that copyright is byperrnission of the ACM, Inc. We present a flow-insensitive interprocedural points-to analysis algol-ithm that has a desirable linear space and almost linear time complexity and is also very fast in practice. The algorithm is easily apphcable to programs with many hundreds of thousands of Ilnes of code. The analysis results are often not as accurate as those obtained by flow-sensitive analyses However, the results are roughly comparable to those of, e g , the cubic time complexity flow insensitive analysls of [Wei80] The algorithm, which is inspired by Henglein's blndlng time analysis by type infel-ence [Hen9 1]. uses anon-standard type system to describe the store usage at runtime by using types to construct a storage shape graph [CWZ90]. While we describe the principles behind the algorithm in terms of types and typing rules, we also provide a detailed description of the algorlthm which can be used almost directly to implement the olgorithm in a compiler In Section 2 we state the source language for which we describe the algorithm The language captures the essential parts of a language like C. In Section 3 we define the non-standard set of types we use to model the storage use, and in Section 4 we state a set of typing rules for programs The typing rules impose constraints on the relationships of types of program variables. Finding a typing of the program that obeys these constraints amounts to performing a points-to analysis In Section 5 we show how to efficiently infer the minimal typing that obeys the constraints In Section 6 we report on practical experience with the algorithm in a C programming envil-onment. In Section 7 we describe related work, and m SectIon 8 we present our conclusions and point out dmections for future wol-k 2 The source Iang,uage We describe the points-to analysis for a small Imperative pointer language which captures the impel-tant properties of languages like C [KR88] The language Includes pointers to locations, pointers to functions, dynamic allocahon, and computing addresses of variables Since the analysis is flow insensitive, the control struckues of the language are irrelevant The abstract syntax of the relevant statements of the language is shown in Figure 1 . The syntax for computing the addresses of variables and for pointer indirection is borrowed from the C progl-amming language
Steensgaard REF proposed an almost linear time algorithm that has been shown to scale to millions of lines of programs.