Fast Computation of Strong Control Dependencies

D 2021

Fast Computation of Strong Control Dependencies

CHALUPA, Marek, David KLAŠKA, Jan STREJČEK a Lukáš TOMOVIČ

Základní údaje

Originální název

Fast Computation of Strong Control Dependencies

Autoři

CHALUPA, Marek (203 Česká republika, domácí), David KLAŠKA (203 Česká republika, domácí), Jan STREJČEK (203 Česká republika, domácí) a Lukáš TOMOVIČ (703 Slovensko, domácí)

Vydání

Cham (Švýcarsko), Computer Aided Verification - 33rd International Conference, CAV 2021, Virtual Event, July 20-23, 2021, Proceedings, Part II, od s. 887-910, 24 s. 2021

Nakladatel

Springer, Cham

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Švýcarsko

Utajení

není předmětem státního či obchodního tajemství

Forma vydání

tištěná verze "print"

Odkazy

URL

Impakt faktor

Impact factor: 0.402 v roce 2005

Kód RIV

RIV/00216224:14330/21:00121991

Organizační jednotka

Fakulta informatiky

ISBN

978-3-030-81687-2

ISSN

DOI

http://dx.doi.org/10.1007/978-3-030-81688-9_41

UT WoS

000693429500041

Klíčová slova anglicky

control dependence;non-termination sensitive control dependence;decisive order dependence;control closure;ntscd;dod;graph theory

Štítky

core_A, firank_1, formela-ver, program analysis, program slicing

Příznaky

Mezinárodní význam, Recenzováno

Změněno: 23. 5. 2022 14:53, RNDr. Pavel Šmerk, Ph.D.

Anotace

V originále

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.

Návaznosti

MUNI/A/1108/2020, interní kód MU

Název: Rozsáhlé výpočetní systémy: modely, aplikace a verifikace X. (Akronym: SV-FI MAV X.)

Investor: Masarykova univerzita, Rozsáhlé výpočetní systémy: modely, aplikace a verifikace X.

MUNI/A/1549/2020, interní kód MU

Název: Zapojení studentů Fakulty informatiky do mezinárodní vědecké komunity 21 (Akronym: SKOMU)

Investor: Masarykova univerzita, Zapojení studentů Fakulty informatiky do mezinárodní vědecké komunity 21

Citovat

CHALUPA, Marek, David KLAŠKA, Jan STREJČEK a Lukáš TOMOVIČ. Fast Computation of Strong Control Dependencies. In Alexandra Silva, K. Rustan M. Leino. Computer Aided Verification - 33rd International Conference, CAV 2021, Virtual Event, July 20-23, 2021, Proceedings, Part II. Cham (Švýcarsko): Springer, Cham, 2021, s. 887-910. ISBN 978-3-030-81687-2. Dostupné z: https://dx.doi.org/10.1007/978-3-030-81688-9_41.

@inproceedings{1783922,
   author = {Chalupa, Marek and Klaška, David and Strejček, Jan and Tomovič, Lukáš},
   address = {Cham (Švýcarsko)},
   booktitle = {Computer Aided Verification - 33rd International Conference, CAV 2021, Virtual Event, July 20-23, 2021, Proceedings, Part II},
   doi = {http://dx.doi.org/10.1007/978-3-030-81688-9_41},
   editor = {Alexandra Silva, K. Rustan M. Leino},
   keywords = {control dependence;non-termination sensitive control dependence;decisive order dependence;control closure;ntscd;dod;graph theory},
   howpublished = {tištěná verze "print"},
   language = {eng},
   location = {Cham (Švýcarsko)},
   isbn = {978-3-030-81687-2},
   pages = {887-910},
   publisher = {Springer, Cham},
   title = {Fast Computation of Strong Control Dependencies},
   url = {https://link.springer.com/chapter/10.1007%2F978-3-030-81688-9_41},
   year = {2021}
}

TY  - JOUR
ID  - 1783922
AU  - Chalupa, Marek - Klaška, David - Strejček, Jan - Tomovič, Lukáš
PY  - 2021
TI  - Fast Computation of Strong Control Dependencies
PB  - Springer, Cham
CY  - Cham (Švýcarsko)
SN  - 9783030816872
KW  - control dependence;non-termination sensitive control dependence;decisive order dependence;control closure;ntscd;dod;graph theory
UR  - https://link.springer.com/chapter/10.1007%2F978-3-030-81688-9_41
N2  - 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.
ER  -

CHALUPA, Marek, David KLAŠKA, Jan STREJČEK a Lukáš TOMOVIČ. Fast Computation of Strong Control Dependencies. In Alexandra Silva, K. Rustan M. Leino. \textit{Computer Aided Verification - 33rd International Conference, CAV 2021, Virtual Event, July 20-23, 2021, Proceedings, Part II}. Cham (Švýcarsko): Springer, Cham, 2021, s.~887-910. ISBN~978-3-030-81687-2. Dostupné z: https://dx.doi.org/10.1007/978-3-030-81688-9\_{}41.

Podrobný výpis o publikaci