Automatic Generation and Management of Program Analyses

296 p.Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1993.Designing a program analysis (for use in optimizing compilers) is a time-consuming, complicated process because it involves many parameters. In particular, one must carefully measure the accuracy of the analysis against its cost. To reach an acceptable cost-accuracy balance the designer must repeatedly implement the analysis, measure its behavior, and alter its design.In this thesis we present a software system called system Z1, by which one can quickly specify a program analysis, obtain automatically from this specification an executable version, measure its performance, and alter the design (adjust the cost-accuracy balance), and repeat the cycle until the desired behavior is seen. Specification language Z1 is designed in which the user can conveniently express various program analyses for a wide range of target languages. System Z1 is based on the abstract interpretation framework. The input to system Z1 is a high-level specification of an abstract interpreter. The output is a C code for the specified interprocedural program analyzer.What makes system Z1 especially useful is called a projection expression. The user writes down, at the outset, a straightforward specification of an analysis, essentially ignoring its cost (memory and cpu time) required to compute it. Afterwards, projection expressions are used to control the cost-accuracy tradeoff of the analysis. The user adds projection expressions for selected domains. System Z1 automatically generates a new analyzer which will conduct the program analysis over the simplified domain structure. Projection expressions permit accuracy to be traded against cost, without requiring that the specification of the analysis be altered.Using system Z1 we have designed constant propagation, alias analysis, def-use/use-def chain analysis, and memory object lifetime analysis. The target languages are C, FORTRAN, and SCHEME, without restriction upon the programs treated. We present a series of experiments results that demonstrate the uses of projection expressions for these analyses problems.U of I OnlyRestricted to the U of I community idenfinitely during batch ingest of legacy ETD