Demand-Driven Slicing

Status:

active

Static program slicing selects a part of the program that can possibly affect, or be affected by, the slicing criterion in question. The standard slicing algorithm is based on building the Program Dependency Graph (PDG). PDG is constructed upon Control Flow Graph (CFG) nodes connecting all the data and control dependency edges which can be quite an expensive operation.

The aim of this project is to improve and develop new slicing approaches that use alternative program representations than PDG and SDG.

Our current appraoch uses an Object Based Program Representation (OBPR) of a given well-structured single-procedure program and program slicing is done on-the-fly during the Strongly Live Variables (SLV) dataflow analysis.

The OBPR is an intermediate program representation proposed in this paper where a given program is represented by a set of objects and a set of interfaces. An object is structured into loops and/or conditionals that directly captures the control dependencies. An interface represents a direct data flow between objects. The SLV dataflow analysis uses one SLV set for each object that efficiently represent the data dependency information unlike the Reaching Definitions (RD) in PDG which uses on RD set for each statement. Moreover, the fixed-point iteration required by the SLV analysis is guided to ensure the quick convergence of the combined SLV analysis and slicing. The overall strategy gives us a static object-based slicing algorithm that is more time and memory efficient than PDG-based slicing. 

Codesurfer which is provided by GrammaTech is one of the main tools that are used in evaluating our algorithms. 

Björn Lisper, Professor

Email: bjorn.lisper@mdu.se
Room: U1-091
Phone: +46-21-151709