The Wisconsin Program-Slicing Tool, Version 1.1

Last updated: Tue Nov 14 03:10:28 CST 2000

• Introduction
• System Capabilities
• Versions of the Slicing Tool
• Assumptions and Limitations
• Components of the Slicing Tool
• Platforms Supported
• Licensing Requirements
• References

The remainder of this document gives an overview of the system and describes some of its capabilities. For your convenience, the system's reference manual can be obtained by clicking here. Some of the technical papers that describe the system's theoretical underpinnings include [FOW87, HR92, HRB90, RHSR94, B93]. The home page of the Wisconsin Program-Slicing Project is a source of additional information about program slicing and other related research that has been carried out at Wisconsin. For surveys of research on program slicing and its applications, see [T95] and [BG96]. The original paper on program slicing is [W84].

System Capabilities

From the user's perspective, the Slicing Tool's main capabilities are:

• It can perform forward and backward slicing with respect to a given set of program components.
• It can perform chopping of a program with respect to given sets of source and target components.
• It can show control and/or flow dependences between program components.

We will illustrate backward slicing using the following program as an example:

When a backward slice of this program is performed with respect to variable i in the printf statement in function demo (i.e., with respect to the position of the caret six lines from the bottom), the results are displayed as follows:

This example illustrates the application of the Slicing Tool to a program that contains C-preprocessor directives (i.e., ``#include'', ``#ifdef'', ``#else'', etc.). In general, a ``.c'' file does not contain a C program; rather, it contains text that can be preprocessed to produce a C program. For this reason, when the SDG for a program is constructed, the user is presented with a dialog box in which to provide the appropriate C-preprocessor flags (``-I'', ``-D'', etc.) and their arguments (e.g., ``-I.'', ``-DEVEN'', etc.). The SDG constructed is specific to the C program that results from preprocessing the source files with respect to these flags. In the example above, we supplied the flag ``-DEVEN'', which is why the line

i = add(i,2); /* Next even integer */

i = add(i,1); /* Next integer */

The Slicing Tool can operate on complete or partial C programs; assumptions made about incomplete programs are discussed below.

Versions of the Slicing Tool

In the interactive version of the Slicing Tool, there is a a language-specific browser created using the Synthesizer Generator, a meta-system for creating interactive, language-based program-development systems [RT88a, RT88b]. Commands are provided to build or use an SDG to perform various actions. The Synthesizer Generator's facility for displaying program components in different display styles is used to report information back to the user of the Slicing Tool. The various commands use different colors and/or different typefaces (depending on how the display styles are defined in the X resources file for the editor) to indicate various collections of program components. For example, as above, the components in a slice of a program are ordinarily highlighted by displaying them in a contrasting display style.

For both the interactive and batch versions of the Slicing Tool, there are three possible configurations. The different configurations are distinguished by the following features:

• The representation of dependence graphs in a compressed format: In each PDG, each strongly connected component is condensed to a single node, and certain internal information that distinguishes between various types of edges is discarded.
• The use of external storage for storing dependence graphs: Dependence graphs are written to intermediate files, and read in on demand to compute summary edges and slices.

• The regular configuration. No compression is performed, and the entire SDG is kept in main memory.
• The compressed configuration. The entire SDG is kept in main memory, but each PDG is compressed.
• The io configuration. In addition to the use of compression (as in the compressed configuration), the operations for building and slicing SDGs make use of secondary storage.

The decision as to which configuration to use should be made according to the size of the program that will be operated on, as well as the operations that will be performed on the program: The different configurations differ in terms of how large a program they can handle and how quickly the various operations are performed. The best performance in terms of run time is obtained with the compressed version. The io version is slower due to the I/O operations it performs, but it does not require as much main memory as the other two configurations.

The Slicing Tool has been used successfully to slice systems as large as 51,000 lines. Some statistics on the performance of the Slicing Tool for programs ranging in size from approximately 1,000-30,000 lines can be found in the Wisconsin Program-Slicing Tool Reference Manual.

Assumptions and Limitations

It is an error to have more than one non-static function with a given name. Functions not found in the program or libraries are handled as follows: We make the optimistic (non-conservative) assumption that they do not use or modify global variables and do not dereference pointer variables; we then make the conservative assumption that at all calls to such functions all possible dependences exist, and thus insert all possible summary edges (i.e., edges between parameter-in and parameter-out vertices) into the SDG.

Pointers are handled as follows:

• Every indirect call (call via a pointer) is considered to be a possible call to every function used as an rvalue somewhere in the program.
• Every pointer dereference is considered to be a possible access of every piece of heap-allocated storage, as well as a possible access of every variable to which the address-of operator (&) is applied somewhere in the program.

In the current version of the Slicing Tool, a few limitations on programs are imposed by the C front end. Some of the features that it does not currently handle are

• line continuations
• the use of an identifier that is a type name as the name of a field in a struct, for example:

  typedef int foo;
  struct { int foo; };
  

• an initialization of a global variable with a conditional value, such as:

  int x = sizeof(int) == 4 ? 0 : 1;
  

• variable-length parameter lists
• setjmp/longjmp
• signals
• system calls such as system, exec, abort, etc.

The Wisconsin Program-Slicing Tool consists of the following components:

• A C front end, which produces intermediate files.
• An interface to read intermediate files and build control flow graphs.
• A system-dependence-graph module that implements operations on SDGs.
• A browser with commands for building SDGs, invoking operations such as slicing and chopping, examining the results of such operations, etc.
• A driver for running the Slicing Tool in batch mode.

The C front end itself consists of two components:

• A customized C preprocessor that processes files and establishes a concordance between the original text and the preprocessed one.
• A tool that scans the program files, one at a time, to produce intermediate files. These files contain two kinds of information:
  • The concordance between source text and program components (i.e., vertices in the SDG), which allows interaction between the user and the Slicing Tool, for example, to define the slice criteria and to display the result of a slice.
  • The information needed to build control-flow graphs and perform data-flow analysis.

Because the C front end operates on a single file at a time, there is essentially no limitation on the size of programs that it can process (as long as each individual file is of reasonable size).

A first pass through the intermediate files produced by the front end builds the call graph and gathers information about global variables and indirect calls (calls via pointers) in the program. A second pass builds a control flow graph for each procedure.

The program's procedure dependence graphs are constructed from their corresponding control flow graphs. The SDG proper is then constructed by linking together all of the program's procedure dependence graphs with call-graph information and introducing some additional information that summarizes transitive dependences due to procedure calls [HRB90, RHSR94].

The SDG of a given program can be written to a file for later use.

Platforms Supported

We have not compiled or tested the system on versions of UNIX other than SunOS 5.5.1. The Synthesizer Generator runs on SPARC Solaris 2.x, SunOS 4.1.x, AIX 4.x, HP-UX 10, Intel Solaris 2.5, Digital UNIX, IRIX 6.2, and porting the Slicing Tool to these platforms should be relatively straightforward.

Licensing Requirements

CodeSurfer builds a dependence-graph program representation and provides a GUI for exploring this web. The dependence graph includes forward and backward links between each assignment statement and possible uses of the values stored by that assignment. Pointer analysis is used so that indirect loads and stores through pointers are taken into account, as well as indirect function calls. Dataflow analysis is used so that links between unrelated assignments and uses are excluded. Operations that highlight forward and backward slices show the impact of a given statement on the rest of the program (forward slicing), and the impact of the rest of a program on a given statement (backward slicing) [TOPLAS90, FSE94]. Operations that highlight paths between nodes in the dependence graph (chops) show ways in which the program points are interdependent (or independent) [FSE95b]. CodeSurfer's scripting language, which provides access to the dependence-graph program representation and the Tk widget set, is used for extensibility and for batch applications.

Full information about CodeSurfer is available here, where you can find

• full documentation,
• whitepapers,
• pricing information,
• information about use by academic researchers,
• the site for downloading an evaluation copy.

• Language: ANSI C
• Program length: < 100K SLOC

B93

Binkley, D., Precise executable interprocedural slices. ACM Letters on Programming Languages and Systems 2, 1-4 (1993), 31-45.

BG96

Binkley, D., and Gallagher, K., Program slicing. Advances in Computers, Vol. 43, M. Zelkowitz (ed.), Academic Press, San Diego, CA, 1996.

FOW87

Ferrante, J., Ottenstein, K., and Warren, J., The program dependence graph and its use in optimization. ACM Transactions on Programming Languages and Systems 8, 3 (July 1987), 319-349.

HPR89

Horwitz, S., Prins, J., and Reps, T., Integrating non-interfering versions of programs. ACM Transactions on Programming Languages and Systems 11, 3 (July 1989), 345-387.

HR92

Horwitz, S. and Reps, T., The use of program dependence graphs in software engineering. In Proceedings of the Fourteenth International Conference on Software Engineering, (May 11-15, 1992, Melbourne, Australia), ACM, New York, NY, 1992, pp. 392-411.

HRB90

Horwitz, S., Reps, T., and Binkley, D., Interprocedural slicing using dependence graphs. ACM Transactions on Programming Languages and Systems 12, 1 (January 1990), 26-60.

KKLPW81

Kuck, D.J., Kuhn, R.H., Leasure, B., Padua, D.A., and Wolfe, M., Dependence graphs and compiler optimizations. In Conference Record of the Ninth ACM Symposium on Principles of Programming Languages, (Albuquerque, NM, January 25-27, 1982), ACM, New York, NY, 1982, pp. 207-218.

RHSR94

Reps, T., Horwitz, S., Sagiv, M., and Rosay, G., Speeding up slicing. In SIGSOFT '94: Proceedings of the Second ACM SIGSOFT Symposium on the Foundations of Software Engineering, (New Orleans, LA, December 7-9, 1994), ACM SIGSOFT Software Engineering Notes 19, 5 (December 1994), pp. 11-20.

RR95

Reps, T. and Rosay, G., Precise interprocedural chopping. In SIGSOFT '95: Proceedings of the Third ACM SIGSOFT Symposium on the Foundations of Software Engineering, (Washington, DC, October 10-13, 1995), ACM SIGSOFT Software Engineering Notes 20, 4 (1995), pp. 41-52.

RT88a

Reps, T. and Teitelbaum, T., The Synthesizer Generator: A System for Constructing Language-Based Editors. Springer-Verlag, New York, NY, 1988.

RT88b

Reps, T. and Teitelbaum, T., The Synthesizer Generator Reference Manual: Third Edition. Springer-Verlag, New York, NY, 1988.

T95

Tip, F., A survey of program slicing techniques. J. Program. Lang. 3, 1995, 121-181.

W84

Weiser, M., Program slicing. IEEE Trans. on Softw. Eng. SE-10, 4 (July 1984), 352-357.