A vezérlésfolyam-gráf a gráfok egyik alkalmazott formája, számítástechnikában használatos ábrázolási forma. Végrehajtási gráfként lehetne legpontosabban fordítani, hiszen az ábra egyes csomóponjaiban blokkok helyezkednek el, s az élek a blokkok végrehajtása után követendő irányt, irányokat jelölik ki. Két kitüntetett blokk van, a belépési blokk és a kilépési blokk.
A végrehajtási gráf segítségével nagyon jól detektálhatóak a kód egyes hibái. Például, ha a gráf egy részgráfjában a belépési blokkból nem érhető el a kilépési blokk, elérhetetlenségi tulajdonságról beszélünk. Ugyanakkor folyamatábra tanulmányozásával az - esetlegesen a programozó szándékától függetlenül létrejövő - végtelen ciklusok is könnyedén felfedezhetőek.
Terminológia belépési blokk (entry block) Az a blokk, amin keresztül beléphetünk a gráfba
Kilépési blokk (exit block) Az a blokk, amin keresztül kiléphetünk a gráfból
Visszamutató él (back edge) Egy blokk ősére mutató él mélységi keresésnél (DFS)
Kritikus él (critical edge) Minden olyan él, amely nem hagyja el a forrás blokkját vagy lép be a célblokkjába. Új blokkok illeszthetőek be hasítás (új blokk létrehozása az él közepén) segítségével.
Abnormális él (abnormal edge) Az ismeretlen célú élek elnevezése. Gátolhatják az optimalizálást
Lehetetlen él (impossible edge; fake edge)
Példa 0: (A) t0 = read_num 1: (A) if t0 mod 2 == 0 goto 4 2: (B) print t0 + " is odd." 3: (B) goto 5 4: (C) print t0 + " is even." 5: (D) end program
Külső hivatkozások The Machine-SUIF Control Flow Graph Library Compiler Collection Internals Paper "Infrastructure for Profile Driven Optimizations in GCC Compiler" by Zdeněk Dvořák, Jan Hubička, Pavel Nejedlý and Josef Zlomek
Kapcsolódó szócikkek Gráf Gráfelméleti fogalomtár Gráfelmélet Gráfok színezése
Példák https://web.archive.org/web/20080311004307/http://www.aisee.com/graph_of_the_month/cfg.htm http://www.absint.com/aicall/gallery.htm https://web.archive.org/web/20080427021215/http://www.icd.de/es/icd-c/example.html http://compilers.cs.ucla.edu/avrora/cfg.html
Kategória:Programozási alapfogalmak