Vezérlésfolyamgráf
Megjelenés
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
[szerkesztés]- 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
[szerkesztés]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
[szerkesztés]- 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
[szerkesztés]Példák
[szerkesztés]- 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 Archiválva 2011. augusztus 25-i dátummal a Wayback Machine-ben