Fast and incremental computation of weak control closure

Control dependence is a fundamental concept used in many program analysis techniques such as program slicing, program debug- ging, program parallelization, and detecting security leaks. Since the introduction of this concept in the late eighties, numerous definitions of control dependencies and their computation methods have been de- veloped. The later definitions are progressively more generalized cover- ing a wide spectrum of modern programming language constructs. The most generalized concepts are the weak and strong control closure (WCC and SCC) that capture the nontermination (in)sensitive control depen- dencies of a given program. In this paper, we have developed a novel method to compute WCC incrementally. Any client application of WCC such as program slicing requires computing the WCC repeatedly in a fixpoint computation. An incremental algorithm to compute WCC will improve the performance of the client application significantly. We have provided the proof of correctness and the theoretical worst-case com- plexity of our algorithm. We have performed an experimental evaluation on well-known benchmarks, and our experiments reveal that we have significantly improved the practical efficiency in computing WCC incre- mentally. We have obtained an average speedup of 31.03 in all bench- marks and a maximum speedup of 35.29 than the best state-of-the-art algorithm computing WCC.