The Wisconsin Program-Slicing Tool, Version 1.1

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



The Wisconsin Program-Slicing Tool is a software system that supports operations on C programs, including backward slicing, forward slicing, and chopping [HRB90, RHSR94, RR95], which can help the user gain an understanding of what a program does and how it works. The Slicing Tool consists of a package for building and manipulating control-flow graphs and program dependence graphs, as well as a front-end that parses C programs and translates them to the internal representations used for slicing.

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

The heart of the Wisconsin Program-Slicing Tool is a package for manipulating program dependence graphs (PDGs) [KKLPW81, FOW87, HPR89] and an extension of program dependence graphs, called system dependence graphs (SDGs), which are a variant of PDGs extended to handle multiple procedures [HRB90, RHSR94].

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

It can also report certain other kinds of information about the program; for instance, it can answer questions about the program, such as "What global variables might be modified by a given procedure call?".

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 */
appears in the slice, rather than the line
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

There are two versions of the Wisconsin Program-Slicing Tool: an interactive version, which allows a user to invoke various operations and view the results; and a batch version, which can be used to report statistics about a program, or to build and save the program's SDG, which can be used later by either the interactive or batch versions of the tool. Once a program's SDG has been created, subsequent operations of the Slicing Tool can be carried out much faster. (For your convenience, the man page for the batch version of the Slicing Tool can be obtained by clicking here.)

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:

Thus, there are three possible configurations: With all three configurations, the Slicing Tool's user interface is essentially the same, and slicing operations give the same results. (Chopping operations are currently not supported in the io configuration.)

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

Source files are assumed to contain syntactically correct C code. To allow different parts of SDGs to be built during different sessions (in a manner similar to separate compilation), no main procedure is required.

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:

(We are currently working on extending the Slicing Tool with improved pointer-analysis algorithms, and plan to make these improvements available in a future release.)

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

In addition, the following features can cause erroneous slices to be created:

Components of the Slicing Tool

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

Note that only the C front end is language dependent. In principle, it is possible to create a similar slicing tool for another language by using an appropriate front end to replace the C front end that is provided in the distribution.

The C front end itself consists of two components:

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

The Wisconsin Program-Slicing Tool has been developed and tested on Sun SPARCstations running SunOS 5.5.1 (also known as Solaris 2.5.1), compiled with gcc, version The Slicing Tool's browser uses X11R6.

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

Although the Wisconsin Program-Slicing Tool was distributed from 1996-2000 for not-for-profit research purposes under license from the University of Wisconsin, it is no longer being distributed. However, there is a commercial tool available, named Codsurfer, that is derived from the Wisconsin implementation and is available from GrammaTech, Inc. GrammaTech has improved on the Wisconsin implementation considerably (both in terms of speed and space efficiency). GrammaTech also provides CodeSurfer to academic researchers on very favorable terms.

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

You should be aware that the most important current limitations of CodeSurfer are as follows: CodeSurfer is currently available for Sun SPARC Solaris, as well as for Windows 95, 98, NT, and 2000.


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

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

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.

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.

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.

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.

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.

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.

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.

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

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

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

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