Re: Intraprocedural points-to analysis

Lots of pointer analysis work in the literature; two basic approaches
that I've found: (1) points-to analysis, and (2) data structure
reconstruction, which tries to discover the shape of the the dynamic
data structure that pointers are actually implementing (tree, linked
list, etc.). Most of the work (that I've seen) is in the latter
category.


The points-to analysis that I like best (not that what I like is very
important) is Emami et al, Sigplan PLDI'94, pp242-256; if you just
want the intraprocedural part, the rules in Figure 1 probably suffice.


A longish latex summary of pointer analysis (a couple years old now)
and the bibtex references follows.
-Michael Wolfe


---------
Pointer analysis is the subject of a great deal of research.
\citen{jones.muchnick.81} present some of the first work to try
to automatically determine the structure of the dynamic data structure
from program analysis.
\citen{landi.popl.91} give a classification of the general problem.
\citen{chase.pldi.90} add a heap reference count to the storage shape
graph, which counts the number of unnamed (nonvariable) pointers to
each object; if the heap reference count is one, then the data structure
must be a simple cycle, list, or tree.
\citen{larus.pldi.88} use an alias graph instead of a storage shape graph
to represent pointer aliases.
The points-to analysis presented here is shown in more detail by
\citen{emami.pldi.94}.


\citen{hendren.ics.89,hendren.tpds.90} discuss a path matrix
representation of pointer paths to determine aliasing or dependence
for programs that construct and traverse dynamic data structures.
\citen{horwitz.pldi.89} build on the work of \citen{jones.muchnick.81}.
\citen{loeliger.super.91} show some results of an
implementation of interprocedural pointer tracking in a commercial C compiler.
\citen{smith.super.91} shows the importance of pointer analysis
and pointer arithmetic
when compiling C for vector machines (and by extension, for parallel machines).
\citen{guarna.icpp.88} also looks at pointers as they are used in loops.
\citen{landi.pldi.92}, \citen{landi.pldi.93}, and \citen{choi.popl.93}
discuss interprocedural pointer alias and side effect analysis.
See the short article by \citen{marlowe.sigplan.93} for a discussion
of two general pointer-aliasing approaches.
Realizing that pointers are used to implement complex data structures
that may have regular characteristics,
\citen{hendren.pldi.92} have developed a language for annotating programs
to describe characteristics of the actual data structure that is
being constructed and/or traversed with the pointers.
\citen{hummel.loplas.92} show how these annotations can be used to
improve analysis;
\citen{hummel.ipps.94} describe a simple language for expressing
alias properties;
and \citen{hummel.pldi.94}
show a scheme to find data dependence by a theorem-proving technique,
given a set of simple axioms defined by the annotations.


@INCOLLECTION{jones.muchnick.81,
      author = "Neil D. Jones and Steven S. Muchnick",
      title = "Flow Analysis and Optimization of {L}isp-like Structures",
      pages = "102--131",
      editor = "Steven S. Muchnick and Neil D. Jones",
      booktitle = "Program Flow Analysis: Theory and Applications",
      publisher = prentice,
      year = 1981,
  }


@INPROCEEDINGS{landi.popl.91,
      author = "William Landi and Barbara G. Ryder",
      title = "Pointer-Induced Aliasing: A Problem Classification",
      pages = "93--103",
      booktitle = popl91,
      address = "Orlando, Fla.",
      month = jan,
      year = 1991,
  }


@INPROCEEDINGS{chase.pldi.90,
      author = "David R. Chase and Mark Wegman and F. Kenneth Zadeck",
      title = "Analysis of Pointers and Structures",
      pages = "296--310",
      booktitle = pldi90,
      address = "White Plains, N.Y.",
      month = jun,
      year = 1990,
  }


@INPROCEEDINGS{larus.pldi.88,
      author = "James R. Larus and Paul N. Hilfinger",
      title = "Detecting Conflicts Between Structure Accesses",
      pages = "21--34",
      booktitle = pldi88,
      address = "White Plains, N.Y.",
      month = jun,
      year = 1988,
  }


@INPROCEEDINGS{emami.pldi.94,
      author = "Maryam Emami and Rakesh Ghiya and Laurie J. Hendren",
      title = "Context-Sensitive Interprocedural Points-to Analysis in the Presence of Function Pointers",
      pages = "242--256",
      booktitle = pldi94,
      address = "Orlando, Fla.",
      month = jun,
      year = 1994,
  }


@INPROCEEDINGS{hendren.ics.89,
      author = "Laurie J. Hendren and Alexandru Nicolau",
      title = "Interference Analysis Tools for Parallelizing Programs with Recursive Data Structures",
      pages = "205--214",
      booktitle = ics89,
      address = "Crete, Greece",
      month = jun,
      year = 1989,
  }


@ARTICLE{hendren.tpds.90,
      author = "Laurie J. Hendren and Alexandru Nicolau",
      title = "Parallelizing Programs with Recursive Data Structures",
      pages = "35--47",
      journal = tpds,
      year = 1990,
      volume = 1,
      number = 1,
      month = jan,
  }


@inproceedings{horwitz.pldi.89,
      author = "Susan Horwitz and Phil Pfeiffer and Thomas Reps",
      title = "Dependence Analysis for Pointer Variables",
      booktitle = pldi89,
      pages = "28--40",
      address = "Portland, Ore.",
      month = jun,
      year = 1989,
  }


@INPROCEEDINGS{loeliger.super.91,
      author = "Jon Loeliger and Robert Metzger and Mark Seligman and Sean Stroud",
      title = "Pointer Target Tracking: An Empirical Study",
      pages = "14--23",
      booktitle = super91,
      address = "Albuquerque, N.M.",
      month = nov,
      year = 1991,
  }


@INPROCEEDINGS{smith.super.91,
      author = "Lauren L. Smith",
      title = "Vectorizing {C} Compilers: How Good Are They?",
      pages = "544--553",
      booktitle = super91,
      address = "Albuquerque, N.M.",
      month = nov,
      year = 1991,
  }


@INPROCEEDINGS{guarna.icpp.88,
      author = "Guarna, Jr., Vincent A.",
      title = "A Technique for Analyzing Pointer and Structure References in Parallel Restructuring Compilers",
      pages = "212--220",
      booktitle = icpp88,
      volume = "II",
      month = aug,
      year = 1988,
      address = "St.\ Charles, Ill.",
  }


@INPROCEEDINGS{landi.pldi.92,
      author = "William Landi and Barbara G. Ryder",
      title = "A Safe Approximate Algorithm for Interprocedural Pointer Aliasing",
      pages = "235--248",
      booktitle = pldi92,
      address = "San Francisco, Calif.",
      month = jun,
      year = 1992,
  }


@INPROCEEDINGS{landi.pldi.93,
      author = "William Landi and Barbara G. Ryder and Sean Zhang",
      title = "Interprocedural Modification Side Effect Analysis with Pointer Aliasing",
      pages = "56--67",
      booktitle = pldi93,
      address = "Albuquerque, N.M.",
      month = jun,
      year = 1993,
  }


@INPROCEEDINGS{choi.popl.93,
      author = "Jong-Deok Choi and Michael Burke and Paul Carini",
      title = "Efficient Flow-Sensitive Interprocedural Computation of Pointer-Induced Aliases and Side Effects",
      pages = "232--245",
      booktitle = popl93,
      address = "Charleston, S.C.",
      year = 1993,
      month = jan,
  }


@ARTICLE{marlowe.sigplan.93,
      author = "Thomas J. Marlowe and William G. Landi and Barbara G. Ryder and Jong-Deok Choi and Michael G. Burke and Paul Carini",
      title = "Pointer-Induced Aliasing: A Clarification",
      journal = "Sigplan Notices",
      year = 1993,
      volume = 28,
      number = 9,
      pages = "67--70",
      month = sep,
  }


@INPROCEEDINGS{hendren.pldi.92,
      author = "Laurie J. Hendren and Joseph Hummel and Alexandru Nicolau",
      title = "Abstractions for Recursive Pointer Data Structures: Improving the Analysis and Transformation of Imperative Programs",
      pages = "249--260",
      booktitle = pldi92,
      address = "San Francisco, Calif.",
      month = jun,
      year = 1992,
  }


@ARTICLE{hummel.loplas.92,
      author = "Joseph Hummel and Laurie J. Hendren and Alexandru Nicolau",
      title = "Abstract Description of Pointer Data Structures: An Approach for Improving the Analysis and Optimization of Imperative Programs",
      pages = "243--260",
      journal = loplas,
      year = 1992,
      volume = 1,
      number = 3,
      month = sep,
  }


@INPROCEEDINGS{hummel.ipps.94,
      author = "Joseph Hummel and Laurie J. Hendren and Alexandru Nicolau",
      title = "A Language for Conveying the Aliasing Properties of Dynamic, Pointer-Based Data Structures",
      pages = "208--216",
      booktitle = ipps94,
      address = "Cancun, Mexico",
      month = apr,
      year = 1994,
  }


@INPROCEEDINGS{hummel.pldi.94,
      author = "Joseph Hummel and Laurie J. Hendren and Alexandru Nicolau",
      title = "A General Data Dependence Test for Dynamic, Pointer-Based Data Structures",
      pages = "218--229",
      booktitle = pldi94,
      address = "Orlando, Fla.",
      month = jun,
      year = 1994,
  }

Return to the comp.compilers page.
Search the comp.compilers archives again.