Slide Index

NIST CSL

UNIT 1 Program Slicing in the Presence of Pointers { SERF 93 ::::::::::::::::::::::: 1.0

Program Slicing in the Presence of Pointers :::::::::::::::::::::::::::::::::::::::::: 1.1Overview :::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: 1.2

Slicing Research Goals ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: 1.3Denitions ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: 1.4

An Ambiguity? ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: 1.5

Another Ambiguity? :::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: 1.6

Pointer State ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: 1.7

Keeping Slices Executable ::::::::::::::::::::::::::::::::::::::::::::::::::::::::: 1.8Weiser's Algorithm Recast ::::::::::::::::::::::::::::::::::::::::::::::::::::::::: 1.9Compound Control :::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: 1.10Indirect References ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: 1.11

Slicing Indirect References :::::::::::::::::::::::::::::::::::::::::::::::::::::::: 1.12Pointer State Function ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: 1.13

Indirect Assignments ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: 1.14

Observations About Pointer Usage ::::::::::::::::::::::::::::::::::::::::::::::::: 1.15Pointer State Subgraph ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: 1.16Capturing Pointer State :::::::::::::::::::::::::::::::::::::::::::::::::::::::::: 1.17Summary ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: 1.18

19 slides

1
May 12, 1997

2

UNIT 1

Program Slicing in the Presence of Pointers { SERF 93

NIST CSL Program Slicing in the Presence of Pointers { SERF 93 May 12, 1997 1.0
Program Slicing in the Presence of Pointers

James R. LyleDavid Binkley

U. S. Department of Commerce

Technology Administration

National Institute of Standards and Technology

Gaithersburg, Maryland

NIST CSL Program Slicing in the Presence of Pointers { SERF 93 May 12, 1997 1.1
Overview

 Slicing Research Goals

 Denitions An Ambiguity?

 Weiser's Algorithm Recast Slicing Indirect References Slicing Indirect Assignments

 Observations About Pointer Usage

 Pointer State Function

 Summary

NIST CSL Program Slicing in the Presence of Pointers { SERF 93 May 12, 1997 1.2
Slicing Research Goals

 To compute slices faster To compute smaller slices To develop new applications To handle more language constructs

NIST CSL Program Slicing in the Presence of Pointers { SERF 93 May 12, 1997 1.3
Denitions

Slicing Criterion < v; n > : Species a slice as a variable and a

location

Program Slice: All program statements relevant to a computation specied by a slicing criterion.

For a program, P, and a slicing criterion:

A program slice is obtained by deleting zero or more statementsfrom P, such that P and the slice both compute the same valuefor v at statement n.

NIST CSL Program Slicing in the Presence of Pointers { SERF 93 May 12, 1997 1.4
1 typedef struct List_struct List;

2 struct List_struct {3 int value;4 List *next;5 };7 main()8 {9 List *at,*head = NULL,*node;

10 int n;12 n = 0;13 while (n < 10){

14 node = (List *) malloc (sizeof(List));

15 node -> value = n++;

16 node -> next = head;

17 head = node;18 }19 at = head;20 at -> value = 47;21 at = at -> next;22 at -> value = 8;23 printf ("%d\n",at -> value);

24 }
An Ambiguity?

NIST CSL Program Slicing in the Presence of Pointers { SERF 93 May 12, 1997 1.5
1 main()

2 {3 int a,b,u,s,x;4 int *w,*y,**z;56 s = 1;7 a = 2;8 b = 3;9 scanf ("%d %d",&x,&u);

1011 if (x) y = &a;

12 else y = &b;1314 if (u) z = &y;15 else z = &w;1617 w = &s;18 **z = 4;1920 printf ("a %d b %d s %d\n",a,b,s);

21 }
Another Ambiguity?

NIST CSL Program Slicing in the Presence of Pointers { SERF 93 May 12, 1997 1.6
Pointer State

NIST CSL Program Slicing in the Presence of Pointers { SERF 93 May 12, 1997 1.7
Keeping Slices Executable

 Lines 11 and 12 are not relevant to the computation of s

 Since w contains the address of s, line 18 is relevant to the slice

only when the condition z = &w is true.

 Two possible solutions for producing executable slices:

1. Add statements to the slice that are irrelevant to the slicing

criterion but are required to keep the slice executable.

2. Add conditions to guard against executing statements that

would cause a run-time error when the slice is executed.

NIST CSL Program Slicing in the Presence of Pointers { SERF 93 May 12, 1997 1.8
Weiser's Algorithm Recast

To locate the statements that in
uence variable v just before execution reaches statement m we would compute a program slice for

the criterion < m; v >.

1. Start with program 
ow-graph2. Annotate with variables referenced and assigned to3. the defs(n) set and the slicing criterion determine inclusion4. the refs(n) set gives new criterion

5. 8n 3 m 2 succ(n)

S<m;v> =

8>><>>: S<n;v> if v 62 defs(n) fng [ S<n;x>8x 2 refs(n) otherwise

NIST CSL Program Slicing in the Presence of Pointers { SERF 93 May 12, 1997 1.9
Compound Control

 A compound control statement has a condition controlling the

execution of another statement

 if, switch, while, for and do ::: while should be included in a

program slice whenever any statement governed by the controlstatement is included in a slice.

 For each statement, n, associate a set, requires(n), of statements

that must be included in a slice containing statement n.

 The slicing rule for v 2 defs(n) becomes:

S<m;v> = fng [ S<n;x>8x 2 refs(n) [ S<k;y>

8y 2 refs(k)8k 2 requires(n)

NIST CSL Program Slicing in the Presence of Pointers { SERF 93 May 12, 1997 1.10
Indirect References

 Consider statement n: A = B + *C + **D

 defs(n) = fAg and refs(n) = fB, C, Dg

 Dene iref(n): set of ordered pairs (var,level) indicating variable and level of indirection.

 irefs(n) = f (C,1), (D,2) g

 Dene idefs similarly

NIST CSL Program Slicing in the Presence of Pointers { SERF 93 May 12, 1997 1.11
Slicing Indirect References

Consider statement n: A = *B + C

Where m is a successor of nWhat is S<m;A>:

 Statement n

 S<n;v>8v 2 refs(n) S<n;v>8v that B might point at

NIST CSL Program Slicing in the Presence of Pointers { SERF 93 May 12, 1997 1.12
Pointer State Function

 P1(n; x) is the set of variables that x might point to at statement

n

 Note that P0(n; x) = fxg

 Pi(n; v) = fxjx 2 P1(n; y)8y 2 Pi1(n; v)g

 For slicing arbitrary indirect references:

S<n;v>8v 2 Pi(n; b)8i; 1  i  k; for(b; k) 2 irefs(n)

NIST CSL Program Slicing in the Presence of Pointers { SERF 93 May 12, 1997 1.13
Indirect Assignments

Consider n: *B = A;

Criterion S<m;v>Include statement n if v 2 P1(n; B)

 S<n;v>8v 2 refs(n) S<n;B> if size of P1(n; B) > 1 then S<n;v>

NIST CSL Program Slicing in the Presence of Pointers { SERF 93 May 12, 1997 1.14
Observations About Pointer Usage

 A pointer dynamically created instances of a structure usually

does not point to other structure types

 Statements change the pointer state by:

1. allocating dynamic storage2. taking an address3. assigning one pointer variable to another

 Pointer state changes are sparsely distributed Pointer variables usually point to a small set of possible addresses.

NIST CSL Program Slicing in the Presence of Pointers { SERF 93 May 12, 1997 1.15
Pointer State Subgraph

 A subgraph of pointer operation is embedded within a program


ow-graph

 To capture the pointer state (Pi(n; v)) only address creation

and assignment need to be tracked.

 Irrelevant control 
ow can be discarded Result is smaller 
ow-graph for analysis of pointer state.

NIST CSL Program Slicing in the Presence of Pointers { SERF 93 May 12, 1997 1.16
Capturing Pointer State

1. Construct PSS2. Scan PSS for address creation3. Propagate created addresses4. Repeat until no more changes

NIST CSL Program Slicing in the Presence of Pointers { SERF 93 May 12, 1997 1.17
Summary

 An approach to slicing programs with pointers Pointer state can

be used for slicing code with indirect references and assignments(more language constructs)

 PSS is signicantly smaller than a program 
ow-graph (can

compute faster with smaller graph)

 Pointers introduce some ambiguities that need examination

(has size implications)

NIST CSL Program Slicing in the Presence of Pointers { SERF 93 May 12, 1997 1.18