Computing Slices for Interprocedural Programs

Abstract

Program slicing has been a hot topic for research nowadays because of its use in program debugging, code simplification and code analysis. As the maintenance of softwares take up to 60% of programming effort and cost, its reduction has become vital. Certain blocks of code can cause unnecessary complexity which doesn’t even contribute to the actual computations in the program. This project is concerned with construction of System Dependence Graph (SDG) for an input source code. SDG is an intermediate graphical representation to represent the dependencies among different programming constructs. The graph is constructed by converting the source code into tokens which are then analysed to form nodes. The nodes of the graph are connected by edges that represent different dependencies present in the program. A node is added to the graph when we encounter any variable or function. Edges are added to the graph on the basis of what relation the nodes have in between them. A control dependency edge is added between two nodes when one node follows the other in the execution sequence. A data dependency edge is added when the value of a certain variable is used at some other point of interest in the program. To compute the slices from the SDG, we have implemented the two phase algorithm as proposed by Horwitz. In this algorithm, for a given slicing criterion, we calculate the phase 1 slice without descending into the called procedures. We mark all the nodes which are reachable from the given slicing criterion except for the ones which are related by the parameter-out edges. The phase 2 slice is calculated by marking all the nodes in the graph except for those related by parameter-in edges and call edges. The slices from the two phases are then merged to give the final static backward slice for the entire source code.