Fast Computation of Strong Control Dependencies

Warning

This publication doesn't include Faculty of Education. It includes Faculty of Informatics. Official publication website can be found on muni.cz.

Authors	CHALUPA Marek KLAŠKA David STREJČEK Jan TOMOVIČ Lukáš
Year of publication	2021
Type	Article in Proceedings
Conference	Computer Aided Verification - 33rd International Conference, CAV 2021, Virtual Event, July 20-23, 2021, Proceedings, Part II
MU Faculty or unit	Faculty of Informatics
Citation
Web	https://link.springer.com/chapter/10.1007%2F978-3-030-81688-9_41
Doi	http://dx.doi.org/10.1007/978-3-030-81688-9_41
Keywords	control dependence;non-termination sensitive control dependence;decisive order dependence;control closure;ntscd;dod;graph theory
Description	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.
Related projects:	Rozsáhlé výpočetní systémy: modely, aplikace a verifikace X. Zapojení studentů Fakulty informatiky do mezinárodní vědecké komunity 21