Review on Cost Effective Dynamic Program Slicing
Original paper at http://dl.acm.org/citation.cfm?id=996855
This paper talks about a set of optimizations that can be applied while constructing dynamic dependence graphs for programs, thereby reducing the size and the traversal times of these graphs. Since these aspects of a dynamic dependence graph incur costs on computing slices, reducing them makes the process faster. The paper makes a very basic assumption about the basic blocks of a program and their associated 'time stamps' in the context of computing the complete dynamic dependence graph. The assumption is that each basic block will be given a time stamp which will then be associated to all local dependencies occurring in that block. My first doubt at this stage is on the definition of a basic block: is it a function, the body of a loop or individual bodies of a conditional statement? The paper does not clarify this. Assuming that it is the standard definition1, such a time stamp scheme might not be right in the context of concurrent programs, where variables are shared between basic blocks.
On a different note, the paper notes that simply drawing edges between statements of code is not enough, but accurate information should be shown in the form of labels, about all the execution instances which are associated with that dependence being formed. This will also lead to an understanding of the context of the program run. However, it is noted further that the amounts of such labels for each edge will depend on the extent of the program's execution itself. Thus, long running programs are likely to have high amounts of such labels. The optimizations proposed in this paper look at reducing the needs to capture all those labels, and on particular occasions even reducing the edges themselves. The reduction is achieved by a basic principle of edge sharing. Or in other words, if you have a set of edges/labels which will occur together in all or a given set of execution instances then a common edge or a common edge without labels can be drawn which will represent all of those dependencies or execution instances. Here comes the question of loss of information. It is to be noted here that the information being provided by such optimizations are still accurate, but they are abstracted. Given a situation where you want to tag individual execution instances with specific information such as being associated to pass/fail test runs, then you have lost some information with the kind of abstraction that these optimizations introduce. Of course this is a very specific situation, and the paper I assume is looking at more general situations where dynamic slices are required. It would have been better for the paper had certain concrete examples been provided where such an optimized slice might be useful. However, I do understand that the paper is grounded in theory and perhaps such a discussion is out of scope for the paper.
On the subject of the optimizations themselves, in my opinion they are an efficient use of the statically derived information about the program's statement dependencies. The simplest category of optimizations come from statically inferring dependencies which are definite to occur. Edges between statements and unambiguous and sole definitions or control ancestors are instances of such dependencies. These edges need not store label information. The time stamp information is also a compile time constant for these edges as shown in the paper. The next set of optimizations involve transformations of the nodes themselves. When a node has two distinct definition-parents or control-ancestors, then the node is duplicated to serve each parent or ancestor separately. This allows us to statically infer the edges in these transformed nodes. At times, when two uses or control dependent nodes have the same definition-parent or the control-ancestor, then those two nodes are linked together and the dependence edge is drawn only between one of them to the parent or ancestor, thus reducing the number of edges themselves. Furthermore, such transformations can also depend on the path taken between the statements with dependencies. That is different (specialized) nodes can be created for specific paths based on how the dependencies can be identified along that path. The third and final set of transformations are to reduce redundant edges. This is done by merging common common def-use edges between two different variables/objects or common data and control dependent edges into one. This reduces the redundancy as it eliminated the edges. Again, here, a question of information loss comes up. You cannot now, for instance distinguish between control and data dependencies in certain places. And if a situation arises where such a distinction is necessary, then these optimizations won't be helpful.
The evaluations of the optimizations showed the margin by which they reduced the size of the dependence graph and time taken to compute the slices from such an optimized graphs. Furthermore, it showed how each optimization technique contributed to the size reduction. This I felt was the most insightful. It especially shows that OPT1 (optimization 1) which involved inferring local (to a block), data dependences was the most effective at reducing the sizes of the graphs. This is to me is an important result. OPT1 was the most fail safe optimization of all, in that it rejected labels for those edges which are sure to happen no matter what. The other optimizations while valid only if a set of preconditions were met or certain transformations were applied. Also, OPT1 did not go for blatant abstraction which could result in information loss. On the whole, all the optimizations together reduced the graph size by significant margin. And thus the time taken to calculate the slices was obviously far lesser. We should however question the information presented in these slices and their effectiveness. Also, might it be possible to just apply OPT1 even though it would not achieve complete optimization but reduces the graph enough for a fast computation of the slice? It would have been interesting to note the separate times taken for slice computation for each individual optimization.
1 Frances E. Allen. 1970. Control flow analysis. SIGPLAN Not. 5, 7 (July 1970), 1-19. DOI=10.1145/390013.808479 http://doi.acm.org/10.1145/390013.808479