University of Illinois Urbana-Champaign

Automatic Generation and Management of Program Analyses

Yi, Kwangkeun

This item is only available for download by members of the University of Illinois community. Students, faculty, and staff at the U of I may log in with your NetID and password to view the item. If you are trying to access an Illinois-restricted dissertation or thesis, you can request a copy through your library's Inter-Library Loan office or purchase a copy directly from ProQuest.

Permalink

https://hdl.handle.net/2142/72099

Description

Title
Automatic Generation and Management of Program Analyses
Author(s)
Yi, Kwangkeun
Issue Date
1993
Doctoral Committee Chair(s)
Harrison, Williams Ludwell, III,
Department of Study
Computer Science
Discipline
Computer Science
Degree Granting Institution
University of Illinois at Urbana-Champaign
Degree Name
Ph.D.
Degree Level
Dissertation
Keyword(s)
Computer Science
Abstract
  • 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.
Graduation Semester
1993
Type of Resource
text
Permalink
http://hdl.handle.net/2142/72099

Owning Collections

Graduate Dissertations and Theses at Illinois PRIMARY
Graduate Theses and Dissertations at Illinois
Dissertations and Theses - Computer Science
Dissertations and Theses from the Dept. of Computer Science