Colloquium - Ryder

Traditional data-flow analysis is performed on whole programs; however, such whole-program analysis is not feasible for large or incomplete programs. We propose fragment data-flow analysis as an alternative approach which computes data-flow information for a specific program fragment. The analysis is parameterized by the additional information available about the rest of the program.

We have developed a model of how to design a fragment analysis for an existing whole-program data-flow analysis, and have explored two specific uses of our model. The first refines the results of an inexpensive whole-program pointer alias analysis for a module of a C program, obtaining more fine-grained information for this fragment (i.e., module). The second performs separable points-to and side effect analyses of a C client program which uses a library. In this second application, we show how to analyze the library separate from the client code, summarize the possible effects the library code can have on client code, and then separately analyze the client code using this summary. In this case, the analysis of the client code is a fragment analysis. Both uses of fragment analysis have been empirically evaluated. Initial results on the cost and precision indicate possible applicability to real-world software.

This work was presented, in part, at the Conference on the Foundations of Software Engineering (1999), the International Conference on Compiler Construction (2001), and in technical report DCS-TR-423 October 2000, available from the PROLANGS website.

This research was funded, in part, by NSF grants CCR-980465 and CCR-9900989, Siemens Corporate Research, and Edison Design Group.

Special talk hosted by Alexander Wolf.