2020/11/03 by Marek Chalupa, David Klas̆ka, David Klaška +2
Computer Science · Engineering · #Algorithm #Compiler #Computation #Computer science #Control flow #Control flow graph #Graph #Optimizing compiler #Parallel Computing and Optimization Techniques #Parallel computing #Programming language #Radiation Effects in Electronics #Slicing #Software Testing and Debugging Techniques #Theoretical computer science #cs.DS
paper · pdf · doi:10.1007/978-3-030-81688-9_41
arxiv created 2020/11/03 · openalex publication_date 2021/01/01 · arxiv updated 2021/09/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
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.