Fast computation of strong control dependencies

DOI10.1007/978-3-030-81688-9_41zbMATH Open1493.68102arXiv2011.01564OpenAlexW3096908876MaRDI QIDQ832318FDOQ832318

Authors: Marek Chalupa, David Klaška, Jan Strejček, Lukáš Tomovič 

Publication date: 25 March 2022

Abstract: We introduce new algorithms for computing non-termination sensitive control dependence (NTSCD) and decisive order dependence (DOD). These relations on control flow graph vertices 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 and we experimentally compare their performance and outcome. Our algorithms dramatically outperform the original ones.

Full work available at URL: https://arxiv.org/abs/2011.01564

Recommendations

• Simple and efficient computation of minimal weak control closure
• A unifying theory of control dependence and its application to arbitrary program structures
• Parametric and Termination-Sensitive Control Dependence
• scientific article; zbMATH DE number 841576
• An optimal algorithm for the construction of the system dependence graph

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30)

Cites Work

• Characterizations of Reducible Flow Graphs
• Program Slicing
• The program dependence graph and its use in optimization
• Programming Languages and Systems
• Certification of programs for secure information flow
• A unifying theory of control dependence and its application to arbitrary program structures
• Slicing for modern program structures: a theory for eliminating irrelevant loops
• Cut branches before looking for bugs: certifiably sound verification on relaxed slices
• Slicing communicating automata specifications: Polynomial algorithms for model reduction
• Parametric and Termination-Sensitive Control Dependence

Cited In (6)

• Simple and efficient computation of minimal weak control closure
• Efficient computation of arbitrary control dependencies
• Title not available (Why is that?)
• An alternative characterization of weak order dependence
• Parametric and Termination-Sensitive Control Dependence
• A unifying theory of control dependence and its application to arbitrary program structures

Uses Software

• LLVM

This page was built for publication: Fast computation of strong control dependencies

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q832318)