Refining data flow information using infeasible paths
Rastislav Bodík, Rajiv Gupta, Mary Lou Soffa · ACM SIGSOFT Software Engineering Notes · 1997
Abstract. Experimental evidence indicates that large programs exhibit significant amount of branch correlation amenable to compile-time de-tection. Branch correlation gives rise to infeasible paths, which in turn make data flow information overly conservative. For example, def-use pairs that always span infeasible paths cannot be tested by any program input, preventing 100 % defuse, testing coverage. We present an algo-rithm for identifying infeasible program paths and a data flow analysis technique that improves the precision of traditional def-use pair analysis by incorporating the information about infeasible paths into the analysis. Infeasible paths are computed using branch correlation analysis, which can be performed either intra- or inter-procedurally. The efficiency of our technique is achieved through demand-driven formulation of both the infeasible paths detection and the defuse pair analysis. Our experi-ments indicate that even when a simple form of intraprocedural branch correlation is considered, more than 2 % of defuse pairs in the SPEC95 benchmark programs can be found infeasible. 1