Fast computation of strong control dependencies

DOI10.1007/978-3-030-81688-9_41MaRDI QIDQ832318zbMATH OpenOpenAlexFDO

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

Publication date 25 March 2022

Copyright license Creative Commons Attribution 4.0 International

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

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)

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.

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

Cites work

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

Cited in

(7)

• Fast and incremental computation of weak control closure
• Efficient computation of arbitrary control dependencies
• Simple and efficient computation of minimal weak control closure
• Parametric and Termination-Sensitive Control Dependence
• An alternative characterization of weak order dependence
• scientific article; zbMATH DE number 841576 (Why is no real title available?)
• A unifying theory of control dependence and its application to arbitrary program structures

Describes a project that uses

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)