Fast Computation of Strong Control Dependencies
Open Access
- 15 July 2021
- book chapter
- Published by Springer Nature
- p. 887-910
Abstract
We introduce new algorithms for computing non-termination sensitive control dependence (NTSCD) and decisive order dependence (DOD). These relations on vertices of a control flow graph have many applications including program slicing and compiler optimizations. Our algorithms are asymptotically faster than the current algorithms. We also show that the original algorithms for computing NTSCD and DOD may produce incorrect results. We implemented the new as well as fixed versions of the original algorithms for the computation of NTSCD and DOD. Experimental evaluation shows that our algorithms dramatically outperform the original ones.Keywords
All Related Versions
This publication has 34 references indexed in Scilit:
- Symbiotic 8: Beyond Symbolic Execution2021
- DG: Analysis and Slicing of LLVM Bitcode2020
- Evaluation of Program Slicing in Software Verification2019
- Reliable benchmarking: requirements and solutionsInternational Journal on Software Tools for Technology Transfer, 2017
- State-based model slicingACM Computing Surveys, 2013
- Control Dependence for Extended Finite State Machines2009
- Slicing for modern program structures: a theory for eliminating irrelevant loopsInformation Processing Letters, 2008
- Parametric and Termination-Sensitive Control Dependence2006
- A framework for generalized control dependence1996
- Efficiently computing static single assignment form and the control dependence graphACM Transactions on Programming Languages and Systems, 1991