Technical Report of Osaka University, Department of Information and Computer Scineces, IIP Lab, IIP-06-05-00, June 5 2000.

Lightweight Semi-Dynamic Methods forEÆcient and E ective Program Slicing
yyyKatsuro Inoue , Fumiaki Ohata , Yoshiyuki AshidayOsaka University
June 5, 2000

Abstract
When we try to debug a large program e ectively, it is very important toseparate a suspicious program portion from the overall source program. Program slicing is a promising technique to extract a program portion; however,it remains diÆcult issues. Static slicing sometimes produces a large portionof the source program, especially for a program with arrays and pointers.
Dynamic slicing requires unacceptably huge run-time overhead. In this paper, we discuss intermediate semi-dynamic methods between static and dynamic slicing. We propose two slicing methods named call-mark slicing anddependence-cache slicing. These algorithms have been implemented in our
experimental slicing system, and execution data for several sample programs
have been collected. The result shows that call-mark slicing reduces the slice
size by about 10{20% from the static slice size, with very little overhead
increase. Also, dependence-cache slice reduces by about 30{90%, even forprograms using arrays, with a ordable run-time overhead increase. Theseslicing methods will be important features for e ective debugging environments.
Author address: Katsuro Inoue
Department of Informatics, Graduate School of Engineering Science,
Osaka University, 1-3 Machikaneyama, Toyonaka, Osaka 560-8531, Japan
Ph. +81-6-6850-6570 Fax +81-6-6850-6574 E-mail inoue@ics.es.osaka-u.ac.jp
 This work is partly supported by Ministry of Education, Science, Sports, and Culture,
grant-in-aid for priority areas \Principles for Constructing Evolutionary Software".

1

1 Introduction
Finding faults in source programs is a very time-consuming activity in software testing and maintenance phases. Looking over all of the source programs
to nd a fault is ineÆcient. We would like to focus our attention to a speci c
portion of the source programs to improve eÆciency.
As a candidate of the focusing aids, program slicing techniques[27, 28]
have been studied. A program slice is intuitively a collection of program
statements which a ect the value of a variable in a statement we are interested in. We can concentrate our attention only on the statements in theslice so that we would be able to e ectively debug the source program.
We have investigated the e ectiveness of program slicing for program debugging and maintenance processes using a controlled method[22]. The bugnding time was measured and compared between two independent groups ofprogrammers, where one group of subjects used an ordinary debugging tooland the other used the debugging tool with static slicing features. Each subject was given a fault-injected program and an associated test data set thate ectively detected the faults. The average bug- nding times were 165 minutes without the slicing, and 122 minutes with the slicing. The e ectivenessof the slicing was con rmed statistically.
A lot of researches and applications for program slicing have emerged[5,6, 7, 10, 14] from the original work of Mark Weiser[27, 28]. These slicing
techniques are roughly categorized into two classes, static slicing and dynamic
slicing.
Static slicing was rst proposed by Weiser[27]. A static slice is a collectionof program statements possibly a ecting a variable's value at a particular
program point. The variable of interest and the program point of interest are
called the slicing criterion. Static slicing extracts portions from an original
program; however, the resulting portions are still large in many cases. In
extreme cases, there is no reduction after taking a static slice. This is due toits analysis nature such that it must consider all possible input data and all
possible control ows.
Also, they remain many diÆcult issues on the analysis, i.e., aliasing ofvariable names, separation of array and structure data elements, and trackingof pointer variables. In addition, object oriented programs, recently prevalentwidely, cause the static analysis much harder, since those programs tend tocontain a lot of small methods (procedures or functions) with dynamically2bind names.
Dynamic slicing was proposed by Agrawal et. al.[1, 2, 16, 17]. A dynamic
slice is a collection of executed program statements actually a ecting a variable's value at a particular program point. Since the dynamic slicing is basedon an execution instance for the source program with a speci c input data,non-executed parts of the source program are automatically excluded, resulting in a slice that is generally smaller than a static one. However, computing
a dynamic slice is costly, requiring signi cant memory and time resources
because of dynamic variable dependences that must be tracked.
For the purpose of bug nding, we would prefer the dynamic slicing, since
the dynamic slicing gives us a narrower focus on the source program.
There have been a few proposal of reducing overhead of dynamic slicing[1].
However, we do not know how e ective those methods are in comparison withdynamic and static methods.
There are various design space for choosing lightweight semi-dynamic
methods which use static analysis information with lightweight dynamic information. In this paper, we propose two methods in such design space.
One method focuses on collecting execution path information, and anotherfocuses on collecting data dependences.
The contributions of this paper are summarized as follows.

 Classi cation and categorization of various algorithms between staticand dynamic slicing methods are presented.

 Two intermediate slicing algorithms, call-mark slicing[23] and dependencecache slicing are proposed, which are lightweight and semi-dynamic
methods. These algorithms require only limited size memory for recording execution information.

 Various empirical data for slicing sizes, and analysis and execution
times are collected using our Osaka Slicing System. Through this experiment, execution overhead and analysis cost are discussed.

The experiment result shows that the lightweight semi-dynamic methods
reduce the sizes of slices, compared to the static ones. Especially dependencecache slicing reduces the slice size greatly. The runtime overhead of thesemethods are small one acceptable to practical use. Although these results are
based on our experimental slicing system, which limits the target language
3

and the source programs, we would think that the lightweight semi-dynamic
slicing methods will be very useful to practical debugging environment.
In Section 2, we will brie y overview static and dynamic slicing, andwill classify various analysis techniques between static and dynamic methods. Section 3 will present call-mark slicing, and Section 4 will propose
dependence-cache slicing. We will show our experiment using Osaka Slicing
System in Section 5. In Section 6, our ndings will be discussed associatedwith related works. We will conclude this paper with some remarks in Section
7.

2 Classi cation of Slicing Methods
2.1 Overview of Static and Dynamic Slicing
In this section, we will brie y show static slicing and dynamic slicing for
further discussions.
2.1.1

Static Slicing

Consider statements s1 and s2 in a source program p. When all of thefollowing conditions are satis ed, we say that a control dependence, CD ,from statement s1 to statement s2 exists:

 s1 is a conditional predicate, and the result of s1 determines whether s2 is executed or not.

This relation is written by s1 - s2.
When the following conditions are all satis ed, we say that a data dependence, DD , from statement s1 to statement s2 by a variable v exists:

 s1 de nes v, and s2 refers to v, and at least one execution path from s1 to s2 without re-de ning v exists.

4This relation is denoted by s1 v- s2 .
A Program Dependence Graph (PDG) is a directed graph whose edges
denote dependences between statements, and whose nodes denote statements
in a program such as conditional predicates, assignment statements, and soon. For a Pascal source program shown in Figure 1 (which computes anabsolute value of the squared or cubed value selected by an input), we have a
PDG presented in Figure 2. To handle function/procedure calls, we employedadditional nodes for input and output parameters.
A Static Slice with respect to a variable v on a statement s (this pair (v ,s) is called a slice criterion) in a program is a collection of statements corresponding to the nodes which possibly reach s using v and other transitively
traversal CD and DD relations. The static slice of variable d at line 24 as
the slice criterion for the program shown in Figure 1 is all statements except
for the message output statements (lines 12, 14, 16) as shown in Figure 3.
2.1.2

Dynamic Slicing

Consider an execution trace e of a source program p for an input data d. si
is a program statement appearing in e, and it indicates a point during an
execution of p with d.
A dynamic slice p0 with respect to si , d, and a variable v is a syntactic
correct subset of p, which computes the same value of v for d at execution
point s0i that corresponds to si . A triple (d, s0i , v ) is also called a slice criterionof a dynamic slice.
A dynamic slice is computed rst by analyzing and storing the actual
data and control dependences of variables in association with the program
execution. Using this dependence chain, all statements in e, which a ect thevalue of v at si , are extracted. Then p0 , which generates the same execution
trace as this extracted trace, is reconstructed.
Figure 4 shows a dynamic slice of the program shown in Figure 1. The
slice criterion is input data (a = 2; b = 3; c = 0), line 24 (of the last instance),and variable d.
Dynamic slicing is based on a single execution path, and it gives narrower
slices than static slices. This nature is preferable in the debugging situation,
since we could concentrate on our attention to the smaller slices.

5

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

program Square_Cube(input,output);var a,b,c,d : integer;function Square(x : integer):integer;
begin
Square := x*xend;function Cube(x : integer):integer;
begin
Cube := x*x*x
end;
begin
writeln(``Squared Value ?'');
readln(a);writeln(``Cubed Value ?'');
readln(b);writeln(``Select Feature! Square:0 Cube: 1'');
readln(c);if(c = 0) thend := Square(a)else
d := Cube(b);if (d < 0) thend := -1 * d;writeln(d)end.

Figure 1: A Sample Source Program

6

Main
writeln("Sq...

Squarereadln(a)x-paraxawriteln("Cu...

readln(b)Square:=x*xawriteln("Sel...

readln(c)Squarec

Square-exit

if c=0

Squarebd:=Square(a)Cubed:=Cube(b)dx-paraxbd

if d<0
d:=-1*dCube:=x*x*x

Cube

Cube

writeln(d)dCube=exit

Data DependenceControl Dependence

Figure 2: Program Dependence Graph (PDG) of Program Shown in Figure
1

7

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

program Square_Cube(input,output);var a,b,c,d : integer;function Square(x : integer):integer;
begin
Square := x*xend;function Cube(x : integer):integer;
begin
Cube := x*x*x
end;
begin
readln(a);readln(b);readln(c);if(c = 0) thend := Square(a)else
d := Cube(b);if (d < 0) thend := -1 * d;writeln(d)end.

Figure 3: Static Slicing Result by d at Line 24

8

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

program Square_Cube(input,output);var a,b,c,d : integer;function Square(x : integer):integer;
begin
Square := x*x
end;

begin
readln(a);readln(c);if(c = 0) thend := Square(a)writeln(d)end.

Figure 4: Dynamic Slicing Result by d at Line 24 with input (a = 2; b =3; c = 0)92.2 Classi cation of Slicing Methods
As mentioned in Section 1, various kinds of slicing method have been proposed and studied. However, there are little e orts to categorize them. In
this section, we would try to sort out them from a view point of analysis
eÆciency and e ectiveness under bug- nding phase. In this viewpoint, weare interested in narrower focus on the source program with smaller analysis
time.
2.2.1

Analysis Based on Statical Flow Prediction

At rst, we explore static slicing methods. The diÆculties of the static
methods lie on nding precise data dependencies, rather than control dependencies. Control dependencies are relatively easily determined by simple
syntactic analyses of the source programs. On the other hand, data dependencies are not easily determined since we cannot determine a single program
execution path statically (i.e., without input data).
If we are able to know the execution order of statements, we would predict which statement assigns the value of a variable and which statement
refers to that value, and thus we can determine data dependencies (Def-Use
relation[3]). There are roughly two issues of execution path prediction in thestatic approach[9].

 Flow SensitivenessIn most static slicing algorithms, the control ow is rst analyzed, andthe results are used by the following data ow analysis, as various
compiler optimization techniques[3]. This type of slicing algorithm iscalled ow sensitive method, and it is commonly used.
An extreme method of reducing the overhead of this control ow analysis, is proposed, in which we do not analyse the control ow at all.
We assume all possible data dependencies between the de nition statements of a variable and its reference statements. This method, called
ow insensitive method, simpli es the analysis process, although theresulting slice size would be increased due to the increase of spurious
data dependencies.

 Context Sensitiveness10For the analysis of multiple procedures and functions in target source
programs, there are two di erent methods proposed and implemented.
For each instance of procedure/function activation statement, the bodyof the procedure/function is analyzed along with its actual parametersand global variable information at caller statements. This method iscalled, context sensitive analysis[14]. In this method, we might have torepeat the analysis of a procedure/function with multiple caller statements.
Another method, in which procedures and functions are analyzed independently from actual call statements, is called context insensitive
analysis. This method would be much simpler than the context sensitive method; however, the precision of analysis results is limited andwe would get generally larger slice results than the context sensitive
method.
As a basis of our discussion, we assume here static slicing algorithmwith ow sensitive and context insensitive ones, without explicit note. Thismethod is fairly straightforward and practically eÆcient one[25].
In this method, control ow of the program is computed through thesyntax analysis of the source program. However, since the analysis is staticone, we cannot generally determine which one of branches of an if statement
statement is selected at execution time. Therefore, we have to assume all
possible control ows, and this would increase the number of data dependencies, and then the resulting slice will be enlarged. This is a fundamental
limitation of static slicing method.
2.2.2

Dynamic Execution Path and Data Dependence Analyses

In debugging environment we assume, program slicing techniques are used
to identify faulty statements. In such cases, there are test cases and theyspecify execution paths of the program for speci c input data. Thus, we areable to use information of the program execution for getting more narrower
slices more eÆciently.
As examples of this approach, dynamic slicing methods have been proposed[1,2, 16, 17], although its overhead at program execution is fairly large. This
type of dynamic slicing algorithm basically requires all history of program
execution including its execution path and status of variables. To do this, we
11

would have to prepare history space proportional to the program execution
length.
The following is a list of intermediate semi-dynamic methods which add
some dynamic information to static one for improving slicing precision andeÆciency.

 Collecting Execution Path
We collect information of the program execution path ( ow). The pointis that we would e ectively get information of the execution path withvery lightweight run-time overhead.
Pro ling Method
This approach is proposed as a simpli ed method of dynamic slicing by Agrawal and et. al[1]. We delete nodes in PDG (which ismade statically), when those statements (nodes) are not executed.
This method can be implemented by checking whether each program statement is executed or not, and it does not require long
history of program execution.
{ Call Mark Slicing Method
We propose this method which will be described in Section 3 indetail. This method is intended to reduce the runtime overhead
compared to the pro ling method. Call-mark method only checks
if each procedure/function call statement is executed or not. Using this information, portions of a source program which are notexecuted are determined and deleted from the slices. Candidate
statements for the possible deletion with respect to each procedure/function call statements are statically analyzed.
{ Hybrid Slicing Method (Partial Trace by break point and call history)
This method record execution history of break points which users
have set or call history of each procedure/function activations[12].
Using this history, an execution path is predicted. To get e ective
execution path information, the users have to set break points
at e ective points in the program. Or we would have to record
activation history of procedure and function activations.
{12 Collecting Data Flow Information
If we could statically predict an execution path of a program, data
dependencies of scalar type variables are easily determined. However,those of array and pointer type variables are not determined by simple
knowing it.
Consider the following a program portion. In this program, it is easy toknow that the execution path is straightforward. However, we cannot
determine that statement 4 depends on 1 or 2.
1: a[0]=0
2: a[1]=1
3: input(i) % Assume integer 0 or 1 as an input
4: c=a[i]In order to resolve this, we need full execution history by which thearray indices are restored and data dependencies are determined. In
usual, DDG (Dynamic Dependence Graph) is used for it. This DDG
keeps all of variable dependencies in its structure[1]. This method iseasily established, although the overhead of constructing full DDG isextremely expensive.
There are a few proposal to compromise between data dependence precision and run-time overhead.
Reduced DDG Method
As an optimization method for constructing DDG, a reduced DDG
has been proposed also in [1]. In this method, the same substructure of DDG has been identi ed and shared with one structure, so that the overall size of the reduced DDG is bounded not by
the program execution length, but by the program size. However,
the execution overhead for the construction would be increased
due to checking the structure similarity, and thus, the practicability of this method is unknown. Also the size of the reduced DDG
is bounded but still large.
{ Dependence-Cache Method{13

We propose this method in Section 4. This method uses a simple memorization technique to determine each Def-Use relation atexecution time. Each data dependence found is added to partial
PDG which is statically constructed with nodes and their control
dependence relations. This method is easily applicable, and it ise ective for non-scalar variables such as array and pointer variables. Only we need is a cache for recording last de nition of eachvariable, and the cache size is bounded by the number of variables
used by the program.
As candidates of promising approaches of practical slicing methods using
both static and dynamic information, we propose, in this paper, call-markslicing and dependence-cache slicing.

3 Call-Mark Slice
3.1 Execution Dependence and CEDHere, we introduce an execution dependence of two statements s1 and s2 .
Consider a case where s1 cannot be executed if s2 is not executed. We
say that s1 is executionally dependent on s2.
Finding all of the execution dependences in a program would require
dynamic information of the program behavior which is known to be very
expensive to compute. Thus, we choose a practical and safe approximation;
namely, we use a subset obtained by static analysis of the program(withassumption of program termination).
If both s1 and s2 are contained in the same basic block of the control
ow graph[3], i.e., there is no outgoing or incoming path on the control ow
between the two statements, s1 is executionally dependent on s2 and viceversa. Also, if s2 is contained in a dominant basic block of s1's block, s1 is
executionally dependent on s2. The control ow associated with the basic
block structure and the domination relation of the basic blocks are easily
obtained by static analysis[3].
Now we de ne a set of caller statements with execution dependence,
CED(s), as follow.

CED(s)

 ft j t is a function/procedure call14

statement and s is executionallydependent on tg
The execution of s is dominated by the call statements in CED(s). If
CED(s) contains at least a non-executed call statement at the end of theexecution, we can conclude that s was never executed.
Consider a small portion of a program such that,...
s1: callA ;s2: if a=1 then begins3:
b:= c ;
s4:
callB ;...

In this program, s1 is executionally dependent on s2, and vice versa, andalso s3 and s4 are executionally dependent on each other. In addition, s3 ands4 are executionally dependent on s1 and also on s2. Thus CED(s2) = fs1g
and CED(s3) = fs1; s4g.

3.2 Computation of Call-Mark Slice
A call-mark slice is de ned as a subset of a static slice of the original programwith respect to an execution e of the program and a slice criterion (sc , v )where sc is a statement and v is a variable. Each statement s in the callmark slice is such that all of the call statements in CED(s) are executedat least once in the execution e. This means that statements appearing inthe static slice but not in the call-mark slice are not executed in e. The
execution of each statement is determined by the record of activation of eachcall statement in the program.
In the following, a process of computing the call-mark slice is described.
Pre-Execution Analysis
Similar to the computing a static slice, we construct the PDG (Program
Dependence Graph) by analyzing the data dependences and control
dependences among the statements. Also, the execution dependences
and CED(s) for each statement s are computed at the same time.

Step 115

Execution-Time Marking
The target program is executed with an input data set. Each timea call statement of a function/procedure is executed, that statement
name (i.e., a pointer to the node in PDG) is marked as \executed".
We refer to the set of marked call statements as CM .

Step 2

Post-Execution Slice Construction
By performing the algorithm shown in Figure 5, the call-mark slice iscollected.

Step 3For the program shown in Figure 1, we have a static slice for the slicing
criterion of (line 24, d) as shown in Figure 3. Consider an execution of thisprogram with input data (a = 2; b = 3; c = 0). In this case, CM = f19g. Forline 19 of this program, CED(19) = f19g; thus CED(19)  CM and line
19 is not deleted. For line 21, CED(21) = f21g; therefore CED(21) 6 CM
and line 21 (and associated line 20) is deleted. Since line 21 is deleted, thestatement de ning b at line 15 is also deleted. The resulting call-mark slice
for that execution and the same criterion, (line 24, d) is as shown in Figure
6.

4 Dependence-Cache Slice
4.1 Overview
As we have discussed in Section 2.2.2, getting precise data dependences ofvariables with static methods are diÆcult in general, although the control
dependences are fairly easily collected statically. Furthermore, data dependencies of pointer variables and array elements are more diÆcult to obtainstatically than scalar variables, since analyses of those non-scalar variables
require complicated prediction of the content values of pointer variables andarray indices[13, 15, 18]. If we would fail to predict possible contents of apointer variable v , we have to use a safe assumption such that a statement s
which indirectly refers to a variable u via v depends on all statements which
possibly de ne u directly or indirectly. (Similar cases could happen for array variables.) Thus, precision of resulting slice would be low, i.e., a lot of
spurious statements which do not a ect the slice criteria are included.
16

Input
PDG: Program Dependence Graph (statically constructed)
CM : Set of nodes which are call statements executed(sc , v ): Slice criterion where sc is a node (a statement) and v is avariable nameTemporary

M; N : Sets of nodes
m; n: nodes
OutputM : Set of nodes of call-mark slice
Algorithm Body
1. M := sc
2. N := fn j n v- sc g [fm j m - sc g
3. While N 6=  then execute the following steps(a) choose a node n 2 N(b) N := N n(c) if CED(n) 6 CM then goto (a)(d) M := M [ n(e) N := N [ fm j m 62 M ^ (m w- n _ m - n)g
where w is any variable name.

Figure 5: Algorithm of Post-Execution Collection for Call-Mark Slicing

17

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

program Square_Cube(input,output);var a,b,c,d : integer;function Square(x : integer):integer;
begin
Square := x*x
end;

begin
readln(a);readln(c);if(c = 0) thend := Square(a)if (d < 0) thend := -1 * d;writeln(d)end.

Figure 6: Call-Mark Slicing Result by d at Line 24 with input (a = 2; b =3; c = 0)18

Once we execute the program with an input data, we are able to collectactual dependence relations between statements, although the penalty ofcollecting precise dependences is fairly large overhead for program execution.
Here, we introduce Dependence-Cache Slicing method, for a good compromise between slice precision and execution overhead. The following are
major steps of computing dependence-cache slices.
Step 1 Pre-Execution Analysis
We statically construct a part of program dependence graph, named
P DGDS for dependence-cache slicing. We prepare at rst nodes foreach statement or predicate statement, and draw control dependenceedges between nodes, as we do for constructing a program dependence
graph PDG for static slicing. No data dependence relations are added
to the graph.
Step 2 Execution-Time Data Dependence Collection
The target program is executed with an input data. Along the execution, dynamic data dependence relation is collected by using data
dependency collection algorithm shown in the next section, and data
dependence relation edges are added to the graph. When the program
execution terminates, P DGDS has been completed.
Step 3 Post-Execution Slice Construction
The completed P DGDS is traversed backwardly, as we do for static
slicing, from a slice criterion (sc , v ) where sc is a statement and v is avariable. A dependence-cache slice is a collection of all reachable nodes
by this traversal.
Since data dependences are analyzed dynamically, we would expect smallerslice size, close to that of the dynamic slice.

4.2 Data Dependence Collection Algorithm
Figure 7 shows the data dependence collection algorithm used at Step 2 inSection 4.1. For each variable v used in a program, we prepare a cache,denoted by C (v ), which contains the line number of a program statement(i.e., a node in P DGDS ). For each point of program execution, C (v ) always
19

InputP DGDS : Partially constructed Program Dependence Graph for dependence cache slicing
P : Target Program
I : Inputs for P
Temporary
Data Dependence Caches C (v ) for each variable v in P
OutputOUT : Output of execution of P for I
P DGDS : Completely constructed Program Dependence Graph for dependence cache slicing
Algorithm Body
1. For each variable v in P , C (v ) := ?
f Initialize with not assigned marks. Note that if we use a dynamically allocated variable, we prepare also a cache initialized with
the not-assigned mark g
2. Repeat following untile execution of P terminates
f Execute P with I from the beginning to the termination, statement by statement g(a) Execute a next single statement s of P associated with I(b) For each variable u used (referred) at s, if C (u) 6= ?, thenadd a data dependence edge C (u) u- s to P DGDS unless theedge exists(c) For each variable w de ned at s, C (w) := sFigure 7: Data Dependence Collection Algorithm
20keeps the line number of a statement which most recently de ned v . Whenv is used (referred) by execution of a statement s, a data dependence edge isdrawn from a node for C (v ) to a node for s, if it does not exist yet. When v
is de ned at s, C (v ) is updated with the line number of s.
We do this for all types of variables, including arrays, dynamically allocated variables, pointer variables, and so on.
We prepare caches for each element of an array. For example, for array
A of ten elements A[1], A[2], . . . , A[10], we have caches C (A[1]), C (A[2]),. . . , C (A[10]). For dynamic allocated variables, we prepare caches for eachvariable also dynamically. When a pointer variable p is used at statements, we have to know that not only p itself is used, but an indirectly accessedvariable p " is also treated as a variable to be used. Thus, we have toinclude the edges of both direct and indirect references ; i.e., C (p) p- s and- s. Also, in the case of indirect assignment with a pointer variable
C (p ") p"q such as q ":= : : : at statement t, we have to know that cache C (q ") is
updated with t, and also that q is used at t.
This algorithm requires cache space proportional to variable usage of the
program execution, and runtime overhead corresponding to variable accessby the program execution.
The result of dependence-cache slicing for program shown in Figure 1 isthe same as the dynamic slice shown in Figure 4 for the same input data(a = 2; b = 3; c = 0).

5 Experiments
5.1 Overview of Osaka Slicing System
In order to validate various slicing algorithms, we have developed a softwaredevelopment and debugging environment called Osaka Slicing System[24].
Figure 8 shows the architecture, and the target language is Pascal.
The system contains slicers, as well as a program executor and debugger.
The slicing algorithms used by the system are interprocedural ow-sensitive
context-insensitive static slicing and fully traced dynamic slicing. These algorithms are sometimes replaced with call-mark slicing and dependence-cacheslicing for experimental data collection.
In the system, the source program in Pascal is parsed into an abstract
21

syntax tree that is stored in the system. The user can view and modify thesource program interactively using a visual editor.
Figure 9 shows the user interface of the system. The left window displays
the target source program. The statement of the slice criteria is shaded
darkly, and the statements in the slice result are shaded lightly. We canalso edit the source program on this window. The right upper window gives
system status such as loaded le name, program size, slice size and so on.
The right lower window works for the standard input and output during theexecution of the target program.
The source program is analyzed and transformed into a PDG by a user
request. A static slice may be computed from the PDG by specifying a slice
criterion.
Both the whole source program and a computed static slice can be executed by the executor. The debugger associated with the executor contains
features of ordinary runtime debuggers such as tracing, setting breakpoints,
viewing and modifying variable values, and so on. Various levels of the dynamic information are recorded during execution based on the selection ofslicing algorithms; dynamic slice, call-mark slice, or dependence-cache slice
can be computed using this information. The total size of the system is about
19,000 lines of C code.
To handle inter-procedural dependences including recursive functions/procedures, we have introduced auxiliary types of nodes in PDG for passing
parameters and global variables. Using these nodes, the data dependences are
examined inter-procedurally. In the case of self or mutual recursive structuresof function/ procedure calls, the dependences become cyclic. This cyclic
dependence is eÆciently solved by analyzing the structure of the dependences,
and a suitable solution is found[25].
The implementation of the call-mark slicing is based on the method presented in previous section. For Step 2, we need only one bit of informationfor each function/ procedure call statement in the program. This bit is notnecessarily marked at the caller context, but rather at the callee context.
At the entry of each function/ procedure, the pointer to the return context
is collected as CM . By doing so, we do not need to nd out all function/
procedure calls in the program, but we simply modify the entry part of eachfunction/procedure slightly.

22

Dynamic
Dependence
Graph

Executor/
Debugger

Dynamic
Slicer

Programmer
Abstract
SyntaxTreeInteractive
Viewer/Editor
StaticDependence
Analyzer

StaticSlicer

Program
Dependence
Graph

Figure 8: Architecture of Osaka Slicing System

23

Figure 9: Snapshot of Osaka Slicing System24

5.2 Execution of Sample Programs
Using this experimental system, we have executed various programs and obtained several metrics values. Program P 1 is a calender calculation program.
P 2 is an inventory management program for a whole seller. P 3 is also an
extended version of the inventory management program of P 2.
Table 1 shows the slice sizes of three sample programs. These values
can vary with di erent slice criteria and input data. Here, we show averagevalues for several criteria and inputs for a typical debugging situation. (Thecriteria are mostly program output variables, and the output statements areplaced almost at the end part of program execution.)
Table 2 shows the time needed for the analysis before the execution. In
the case of static slicing, the value is the time to construct a PDG. The time
for computing both the PDG and the CED is counted for in the call-markslicing. For the dependence-cache slicing, it is time for constructing an initial
P DGDS . In the case of dynamic slicing, the analysis is not necessary.
In Table 3, the execution time is shown. In the case of static slicing, theoriginal program is executed without any extra runtime overhead; thus thisvalue means the execution time of the original program. The execution forthe dynamic slicing is performed in association with the construction of the
dynamic dependence graph. Therefore, the execution time contains the time
for this construction. The time for the dependence-cache slicing includes
the time for caching dependencies and constructing P DGDS . In the case ofcall-mark slicing, the time to mark callers is included.
Table 4 shows the time needed for collecting statements to be includedin the resulting slices. In the case of static slicing, this could be done before
execution. For dynamic slicing, the time for traversing the dynamic dependences is counted. For call-mark slicing and dependence-cache slicing, these
are the time for Step 3, respectively.
We discuss these tables in detail in the next section.

6 Discussion
6.1 Interpretation of Experiment Data Slice Size25

Table 1: Size of Slice (lines)
programP1(85 lines)
P2(387 lines)
P3(871 lines)

static21
182
187

call-mark

17
162
166

dependence-cache

15
16
61

dynamic

5
5
8

Table 2: Pre-execution Analysis Time (ms)program

P1
P2
P3

static11
213710

call-mark

14
215
698

dependence-cache

5
19
48

dynamic(Celeron-450MHz CPU with 128MB Memory)

N/A
N/A
N/A

Table 1 shows the sizes of slices. Those of the call-mark slicing are
80{89% of static slicing. Also, those of dependence-cache slicing are
9{71% of static slicing.
The slice sizes of the call-mark and dependence-cache slices are between
the static and dynamic slices. It is always smaller and better than thestatic slice and bigger and worse than the dynamic slice. Also, we cansay that the dependence-cache slices are much better (smaller) than thecall-mark slices. This is because dependence-cache slicing re ects data
dependences on a particular execution path, while call-mark slicing
only cuts out unexecuted parts of the statically detected data dependences based on a calling sequence. Reduction of the slice size with thedependence-cache slicing is large for programs P 2 and P 3, comparedwith P 1. This is because P 1 uses only scalar variables and P 2 and P 3
employ array variables whose element-wise data dependencies are only
analyzed by dependence-cache slicing or dynamic slicing.

 Pre-Execution Analysis:

As shown in Table 2, call-mark slicing needs a little extra time compared to the static slicing. This is natural since we have to construct a26

Table 3: Execution Time (ms)program

P1
P2
P3

static

47
43
4,700

call-markdependence-cache

47
43
4,731

dynamic

51
174
45
4,540
4,834 206,464(Celeron-450MHz CPU with 128MB Memory)

Table 4: Slice Construction Time (ms)program

P1
P2
P3

static

0.4
1.9
3.0

call-mark

0.6
1.8
3.0

dependence-cache

dynamic

0.3
76.0
0.7
101.0
1.2 24,969.3(Celeron-450MHz CPU with 128MB Memory)

PDG as in static slicing, and additionally we have to analyze the execution dependences. For dependence-cache slicing, we need a lightweight
pre-execution analysis only for control dependences, which is fairly
smaller overhead than the data dependence analysis for static and callmark slicing.

 Execution TimeThe execution time shown in Table 3 indicates that the overhead ofthe dynamic slicing is extremely big. If the program execution becomes longer by say, repeated execution of loops, this overhead would
cause serious decline of performance so that the programmer can hardly
use this facility. On the other hand, the call-mark slicing can be executed with very little overhead increase compared to the execution of
the static slicing (i.e., the execution of the original source program).
It shows that the marking of the caller names during execution is alightweight task, requiring little execution time.
For dependence-cache slicing, it requires extra execution time to callmark slicing; however, the values are much smaller than those of dy27

namic slicing. The execution time presented here is based on our interpretive system; therefore, the run-time overhead for these slicing might
be masked by the overhead of the interpretive execution. This issue
will be discussed in Section 6.3.

 Slice Construction TimeAs shown in Table 4, dynamic slicing requires a long time to collectthe slice result. The time for collecting a call-mark slice is almost
the same as the time to collect a static slice. For a dependence-cacheslice, it is better than the static one. This is because dependence-cacheslicing construct P DGDS smaller than P DG, so that the searching
space within the P DGDS is smaller than that for static slicing. For
dependence-cache slicing, it is evident that traversing a large dynamic
dependence graph (DDG) is very costly.

6.2 Application Domain and Limitation of Call-MarkSlice
The pre-execution analysis, execution, and slice construction times are almost
the same as those for static slicing, and the sizes of slices are about 12-20%
smaller than static slices.
The reduction rate might not be so signi cant. However, call-mark slicing method can be easily implemented if we have already a static slicing tool
and a program execution environment in which we can steal return addresses
in the activation records of a system stack. Also, there is very little overhead increase. Thus we consider that this method would be a very handy
improvement method of static slicing.
One of main targets of call-mark slicing method is a debugging environment. Dynamic information is considered to be essential for eÆcient fault
detection. A call-mark slice can be directly associated with a speci c test
data which exposes faults in the source program, although static slice would
generally include various portions which do not relate to the execution withthe test data.
Programs which consist of independent function/procedure components
may also be eÆciently debugged with our approach. In such cases, there
would be many function/procedure invocation statements, and also many28

function/procedure de nitions. Activation of selected functions/procedures
using a speci c input data will clearly reduce the slice size.
On the other hand, if the target programs contain a small number of function/procedure invocation statements or the function/procedures are tightlyinterleaved, the e ect of our approach will be limited.

6.3 Application Domain and Limitation of DependenceCache Slicing
As we can see in Table 1, the size of dependence-cache slicing is much smaller
than that of static and call-mark slicing, although it is bigger than that ofdynamic slicing. It is worth noticing that programs using arrays, such as P 2
and P 3, are well analyzed with dependence-cache slicing, producing smallerslices. Thus, we can say that this approach is very e ective to computeslices for programs using arrays and pointers, whose statical analysis would
be complicated and impractical.
To implement dependence-cache slicing under a practical compiler-based
environment, we have to consider the following.
 Control dependences has to be analyzed statically, and PDG with only
control dependence edges is to be built. This might be performed by acompiler and its optimizer.

 Execution environments has to be changed to include the dependence

caches for each variable. The size of the caches is proportional to thenumber of variables used in the program. If the program uses dynamic
variables, we have to prepare their caches dynamically also. Run-time
memory requirement will be increased, say, doubled by this. However,the cost of memory would not be a critical issue at program debugging
phase.

 Compiler-generated codes must contain instructions for updating thedependence caches and adding dependence edges to PDG.
The experiment shown in Section 5 has been made under our interpretive execution system. We would think that the characteristics of analyses
and execution times for various slicing will hold for compiler-based execution environment, although the run-time overhead needed for semi-dynamic
methods would become clearer.
29

For example, we have written a merge sort program in C. This program
has been modi ed to collect data dependences with the dependence caches
during execution of the merge sort. The execution speed of its compiled code
was 8.6 times slower than the original code. This would indicate that the
run-time overhead of the dependence-cache slicing is large under a compilerbased environment. However, this speed down can be minimized if we collect the data dependence information only for array and pointer variables.
Data dependences through scalar variables are fairly easily determined statically. Thus, statically diÆcult analysis is only performed at execution time.
Based on this idea, we have modi ed the C merge sort program again, sothat the data dependences only for array elements were collected dynamically. The execution-time ratio between the original program and the partial
dependence-cache program became 1 to 3.4, and we would think that this ispractically acceptable.
As we can see with Table 1, the dependence slices are always larger thanthe dynamic slices. This di erence is based on the rationale such that thedependence slicing does not distinguish repeated occurrences of a single statement and that it only holds the latest Def-Use relations in caches. Consider
the following simple example.
1: a[0]:=10 ;2: a[1]:=20 ;3: for i:=0 to 1
4:b[i]:= a[i] ;5: writeln(b[0]) ;Execution of this program will create a DDG (Dynamic Dependence
Graph) as shown in Figure 10. Nodes 3 and 4 appear twice and lower nodes
mean the second occurrences of statement 3 and 4. If we compute a slicewith a criterion (statement 5, b[0]), the result of the dynamic slicing is a setof statements 1, 3, 4 and 5.
On the other hand, the dependence caches contain the last de nition
statements as shown in Table 5. P DGDS created by this execution is shownin Figure 11, and resulting slice with the same criterion (statement 5, b[0])is a set of statements 1, 2, 3, 4, and 5.
 Also, this result suggests that the execution overhead for dynamic slicing would be

unacceptably huge.

30

Table 5: Change of Cache Contents for Simple Sample Program
statement
Cache Contents
executed

1
2
3
4
3
4
5

a[0]

1
1
1
1
1
1
1

a[1]

2
2
2
2
2
2

b[0]

4
4
4
4

b[1]

4
4

i

3
3
3
3
3

Underlines show that the variable is used and the cache is referred to

Dependence-cache slicing includes statement 2 as its result. This is because the dependence-cache slicing method cannot distinguish the rst andsecond occurrences of statement 4 execution, and dependences both fromstatement 1 and 2 are targeted to a single node for statement 4.
This limitation increases the slice size for dependence-cache slicing, compared to dynamic slicing; however, it is fairly smaller than the static slice,
and we think that this approach is a practical and promising method compromising between e ectiveness and overhead.

6.4 Relation to Other Methods
Others have worked on combining static and dynamic information for slicing.
Hybrid slicing[12] targets a similar goal as call-mark slicing. It reduces thestatic slice by using two types of dynamic information: breakpoint information and call history information. The former is supplied by the programmer
and that information is used to infer the executed control ow. The latter
is used to compute portions of dynamic slices for the periods between every
function/procedure call and return. The result is closer to the dynamic slice
than our approach since it gathers more dynamic information. The weaknessof the hybrid slicing would be that we have to specify appropriate breakpoints
to get a better slice. On the other hand, our approach performs everything
automatically except for giving the input data and slice criterion. Also, the
31

1

2

a[0]

3
CD

i
4

a[1]
i
3
CD

i
4

b[0]
5

Figure 10: Dynamic Dependence Graph for Simple Sample Program

1
a[0]
2
a[1]
i
3
CD

i

4
b[0]
5

Figure 11: P DGDS for Simple Sample Program32

hybrid slicing requires a fairly large amount of memory space for recording
the call history. The space required is roughly proportional to the program
execution length. Our call-mark slicing, however, needs only the memory
for the call marks, which is of a pre-determined size and is roughly proportional to the program text size. The di erence is signi cant if the program
execution becomes long. The execution method of the hybrid slicing mainly
contributes to determine an execution path of the program. However, thisexecution path information does not always help to determine data dependences of pointer and array variables, as our dependence-cache slicing.
Our approach, call-mark slicing, uses information of whether or not eachfunction/procedure call statement in the program is executed. The precisionof slices can be improved if we take such information of all statements in the
program. This approach, mentioned in [1] as type 1 method, can be implemented using a similar method to computing pro ling and program coverage
information. For each statement, we employ one bit ag of whether it isexecuted or not. The mechanism would be simple; however, it requires more
run-time overhead and signi cant modi cation of the executable program.
The call-mark slicing information can be obtained by minor modi cation of
the function/procedure entry routine to collect caller statements.
We could also take a simpler context-insensitive approach than the callmark slice, where each context of function/ procedure activation is recorded.
We could only gather information about whether or not each function/procedureis activated without recording which call statement actually activated it. Thisapproach reduces run-time overhead for collecting caller statements; however
it would increase the resulting slice size.
There are little researches which collect dynamical data dependencies eÆciently. In [1], an optimization method of constructing a dynamic dependence
graph for dynamic slicing, where same substructures of the graph are reduced
into a single one. This approach keeps the precision of dynamic slices andreduces the space for the graph; however, its execution overhead would not
be reduced or might be increased by checking the duplicates.
There are researches in which pointer and array variables are staticallyanalyzed[13, 15]. Many of these try to statically determine possible aliases
of pointer variables and array elements, and they still remain uncertain
cases[29]. Since our dependence-cache slicing is dynamic one and there isno complicated static analyses. It is easily applicable to any type of variables, and we can get reasonable slice precision with a ordable execution
33

overhead.
In [8], a method to extract various slice algorithms from semantic speci cations is presented. They propose a constrained slice, which is a generalization of static and dynamic slices, and which takes a subset of the inputs ofthe program as symbolic program execution. Using this input constraint, theprogram is rewritten and dependences are computed. Their approach contains very important notions of generalization of static and dynamic slicing,
and also it covers the partial evaluation and program simpli cation methods. However, it is not known whether such a generalized approach may be
implemented eÆciently and whether it is useful practically.
In terms of building analysis systems, several interesting approaches havebeen proposed. Various ways of analyzing large programs and extracting
abstracted information of the target software have been studied[4, 11, 19].
A generalized environment for developing analysis algorithm is proposed in[26]. It uses denotational frameworks to specify analysis algorithms; however,practicability of the generated algorithms for analysis tools is not known.
In [20], a more practical environment for understanding Cobol programs ispresented, where various slicing and program localization features are uni ed.
Our aim is to construct an eÆcient and e ective environment for structured
languages with functions and procedures calls.

7 Conclusions
Localizing a programmer's attention to a small portion of software is very important for improving the eÆciency of program debugging and maintenance.
Traditional program slicing methods do not provide adequate trade-o s ofe ectiveness and eÆciency.
We have proposed two lightweight semi-dynamic slicing methods, callmark slicing and dependence-cache slicing. These methods use lightweight
run-time execution, and have a similar or smaller analysis overhead withrespect to static analysis as static slicing. The resulting slices are smaller
than corresponding static ones, but larger than corresponding dynamic ones.
We have implemented these slice algorithms on our experimental interpreter
system. Also we have executed various sample programs, and con rmed ourapproach.
We are planning to design a debugging environment based on compiler34

based system, rather than the current interpreter-based system. The system
will be able to compute dependence-cache slices, associated with various
debugging features. This compiler generates a run-time environment withdependence caches, and the generated codes automatically collect dynamic
data dependences. This information is displayed as a slice or other debugging
aids when requested by users, and it gives more fruitful suggesting for fault
localization.

Acknowledgments
The authors are very grateful to Akira Nishimatsu, Minoru Jihira, and Shinji
Kusumoto of Osaka University who have contributed to designing and implementing the call-mark slicing system.

References[1] Agrawal, H. and Horgan, J. : \Dynamic Program Slicing", SIGPLAN
Notices, Vol.25, No.6, pp. 246{256, 1990.
[2] Agrawal, H., Demillo, R. A., and Spa ord, E. H. : \Debugging with
Dynamic Slicing and Backtracking", Software Practice and Experience,Vol. 23, No. 6, pp. 589{616 (1993).
[3] Aho, A. V., Sethi, R., and Ullman, J. D.: \Compilers: Principles, Techniques, and Tools", Addison Wesley, Massachusetts, 1986.
[4] Atkinson, D.C. and Griswold, W.G. : \The Design of Whole-Program
Analysis Tools", Proceedings of the 18th International Conference on
Software Engineering, Berlin, Germany, pp. 16{27, 1996.
[5] Bates, S. and Horwitz, S. : \Incremental Program Testing Using Program Dependence Graphs", Conference Record of the Twentieth ACM
Symposium on Principles of Programming Languages, 1993.
[6] Beck, J. and Eichmann, D. : \Program and Interface Slicing for Reverse Engineering", Proceedings of the 15th International Conference on
Software Engineering, pp. 509{518, 1993.
35

[7] Binkley, D.W. and Gallagher, K.B. : \Program Slicing", Advances in
Computers, Volume 43, Marvin Zelkowitz, Editor, Academic Press San
Diego, CA, 1996.
[8] Field, J., and Ramalingam, G.: \Parametric Program Slicing", Proc. of
22nd ACM Symposium on Principles of Programming Languages, pp.
379{392, San Francisco, USA, January (1995).
[9] Fiutem, R. , Tonella, P. , Antoniol, G. and Merlo, E.: \Variable Precision Reaching De nitions Analysis for Software Maintenance", In Proc.
of the Euromicro Working Conf. on Soft. Maintenance and Reengineering, pp. 60{67(1997).
[10] Gallagher, K.B. and Lyle, J.R. : \Using Program Slicing in Software
Maintenance", IEEE Transactions on Software Engineering, 17(8), pp.
751{761, 1991.
[11] Griswold, W. G. and Notkin, D.: \Architectural Tradeo s for a
Meaning-Preserving Program Restructuring Tool", IEEE Transactions
on Software Engineering, 21(4):275{287(1995).
[12] Gupta, R., So a, M.L., and Howard, J. : \Hybrid Slicing: Integrating
Dynamic Information with Static Analysis", ACM Transaction on Software Engineering and Methodology, Vol. 6, No. 4, pp. 370{397, 1997.
[13] Hind, M., Burke, M., Carini, P., and Choi, J.:\Interprocedural PointerAlias Analysis", ACM Trans. on Programming Languages and Systems,
Vol.21, No. 4, pp. 848{894 (1999).
[14] Horwitz, S. and Reps, T.:\The Use of Program Dependence Graphs in
Software Engineering", Proceedings of the 14th International Conference
on Software Engineering, pp. 392{411(1992).
[15] Horwitz, S. Pfei er, P., and Reps, T.:\Dependence Analysis for Pointervariables", Proceedings of SIGPLAN '89 Conference on Programming
Language Design and Implementation, pp.28{40, SIGPLAN Notices Vol.
24, No. 6 (1989).
[16] Korel, B., and Laski, J. : \Dynamic Program Slicing", Information
Processing Letters, Vol.29, No,10, pp. 155{163 (1988).
36

[17] Korel, B., and Laski, J. : \Dynamic Slicing of Computer Programs",
Journal of Systems Software, Vol.13, pp. 187{195 (1990).
[18] Liang, D., and Harrold, M. J., : \EÆcient Points-To Analysis for WholeProgram Analysis", Proc. of 7th European Software Engineering Conference and 7th ACM SIGSOFT Symposium on Foundations of Software
Engineering, pp.199{215, Toulouse, France (1999).
[19] Murphy, G. C., and Notkin, D.: \Lightweight Lexical Source Model Extraction", ACM Transactions on Software Engineering and Methodology,
Vol. 5, No. 3, pp. 262{292, July (1996).
[20] Ning, J. Q., Engberts, A., Kozaczynski, W. V. : \Automated Support
for Legacy Code Understanding", Communications of the ACM, Vol. 37,
No. 5, pp.50{57, May (1994).
[21] Nishie, K., Kamiya, T., Kusumoto, S. and Inoue, K. : \Experimental Evaluation of Usefulness of Debugging Support System Based on
Program Slicing", Proceedings of Software Symposium '97, pp. 142{147,Japan, 1997(in Japanese).
[22] Nishimatsu, A., Kusumoto, S., Inoue, K. : \An Experimental Evaluationof Program Slicing on Fault Localization Process", Technical Report of
IEICE Japan, SS98{3, pp. 17{24, (1998)(in Japanese).
[23] Nishimatsu, A., Jihira, M., Kusumoto, S. and Inoue, K. : \Call-Mark
Slicing: An EÆcient and Economical Way of Reducing Slice", Proceedings of The 21st International Conference on Software Engineering,pp.422-431, Los Angeles, CA, USA, 1999.
[24] Sato, S., Iida, H., and Inoue, K. : \Software Debug Supporting Tool
Based on Program Dependence Analysis", Transaction on IPSJ, Vol. 37,
No. 4, pp. 536{545 (1996) (in Japanese).
[25] Ueda, R., Inoue, K., and Iida, H. : \A Practical Slice Algorithm for Recursive Programs", Proceedings of the International Symposium on Software Engineering for the Next Generation, pp. 96{106, Nagoya, Japan,
February (1996).

37

[26] Vengatesh, G. A., and Fischer, C. N. : \SPARE: A Development Environment for Program Analysis Algorithms", IEEE Trans. on Software
Engineering, Vol. 18, No. 4, pp.304{315, April (1992).
[27] Weiser, M.: \Program Slicing", Proceedings of the Fifth International
Conference on Software Engineering, pp. 439{449 (1981).
[28] Weiser, M.:\Program Slicing", IEEE Transactions on Software Engineering, 10, pp.352-357, July (1984).
[29] Ramalingam, G.: The Undecidability of Aliasing, ACM Transactions
on Programming Languages and Systems , Vol. 16, No. 5, pp. 1467{1471(1994).

38