Detection of unfeasible paths with a path‐dependence flow graph
Kuniaki Naoi, Naohisa Takahashi · Systems and Computers in Japan · 1994
Abstract The problem of finding unfeasible paths (UFP: computation paths that are never executed for any input) is important in test data generation and effect propagation analyses. In this paper a directed graph representation executable in parallel, called path dependence flow graph, is proposed which is suited to problems of finding properties of procedural programs along computation paths such as the UFP detection problem. Also, a method is given that symbolically computes logical expressions necessary for UFP detection by parallel abstract interpretation of this graph. Furthermore a method for detecting UFP is presented that converts an obtained logical expression into a Presburger sentence and that applies a truth value decision method for Presburger sentences to it. By using this method, the computation control is made simple and the removal of computations that are not necessary for UFP detection is made easy. In addition since partial results can be shared, UFPs are detected more efficiently.