Ugrás a tartalomhoz

control-flow graph

A Wikiszótárból, a nyitott szótárból


Főnév

control-flow graph (tsz. control-flow graphs)

  1. (informatika) A Control-Flow Graph (CFG) egy gráfelméleti modell, amely egy program lehetséges vezérlésútvonalait írja le. Az ilyen gráf statikus elemzések (pl. data-flow analysis, optimizáció, hibadetektálás, biztonsági vizsgálatok) alapja, és központi szerepet játszik fordítóprogramokban, elemzőeszközökben, valamint a formális verifikációban.


🧠 Mi az a CFG?

A vezérlésáramlási gráf egy irányított gráf, amelyben:

  • Csomópontok (node): a program utasításai, basic blockjai, vagy utasításcsoportok.
  • Élek (edge): lehetséges vezérlésátmenetek (pl. egy utasítás után mi hajtódhat végre).

A CFG nem az értékekkel, hanem a végrehajtás sorrendjével foglalkozik.


🔁 Basic block

Egy basic block egy olyan utasítássorozat, amely:

  • egyetlen belépési ponttal rendelkezik (csak az elején lehet belépni),
  • egyetlen kilépési ponttal rendelkezik (csak a végén lehet kilépni),
  • nem tartalmaz elágazást a blokkon belül.

Ez a CFG építőköve.

Példa:

1: x = 0;
2: y = 1;
3: if (a > b)
4:     x = x + 1;
5: y = y + 1;

Itt a basic block-ok lehetnek:

  • B1: x = 0; y = 1;
  • B2: if (a > b)
  • B3: x = x + 1;
  • B4: y = y + 1;


📈 Példa: CFG vizualizáció

1: int x = 0;
2: if (a > 0)
3:     x = 1;
4: else
5:     x = -1;
6: return x;

CFG:

  [1]
   |
  [2]
  / \
[3] [5]
  \ /
  [6]
  • Az él azt mutatja, hogy milyen irányba léphet tovább a vezérlés.
  • A 2. sor egy elágazási pont (branch).


⚙️ Alkalmazások

1. Data-Flow Analysis

A data-flow információk (pl. elérhető definíciók, konstansok) IN/OUT halmazként tárolhatók minden csomópontnál.

2. Optimalizálás

Fordítók CFG-t használnak pl.:

  • halott kód eltávolításához,
  • loop unrolling,
  • inlineolás,
  • jump threading,
  • basic block átrendezéshez.

3. Hibadetektálás

Pl. unreachable kód, végtelen ciklusok, nem inicializált változók.

4. Biztonsági elemzés

  • Lehetséges futási útvonalak vizsgálata (taint analysis).
  • Statikus sebezhetőségvizsgálat.


🧮 Technikai részletek

1. Élek típusai

  • Folytonos (fall-through): nincs explicit goto, if, return.
  • Feltételes elágazás (conditional branch): if, switch.
  • Ugrás (jump/goto): pl. ciklus vagy goto.

2. Belépési / kilépési csomópont

  • A CFG-nek egy belépési pontja van (általában az első utasítás).
  • Lehet több kilépési pontja (pl. return, exit, throw).


🔄 Ciklusok a CFG-ben

Ciklusok felismerhetők, ha egy útvonal visszavezeti a vezérlést egy korábbi blokkhoz.

Példa:

while (x < 10) {
    x++;
}

A CFG-ben ez egy önmagába visszacsatolt él.


🛠️ Eszközök CFG generálásra

  • LLVM: opt -dot-cfg opcióval .dot fájlokat generálhat.
  • GCC: -fdump-tree-cfg opció.
  • Clang Static Analyzer
  • Soot: Java CFG + data-flow analízishez.
  • Frama-C: C programok CFG vizualizációja és verifikációja.


🧩 Haladó témák

1. Program Dependence Graph (PDG)

A CFG kibővített változata, amely adat- és vezérlésfüggéseket is tartalmaz.

2. Control Dominators

Egy blokk B dominál egy másikat, ha minden úton B-hez el kell haladni rajta. Ez hasznos strukturált ciklusok, if-else blokkok felismeréséhez.


⚠️ Kihívások

  • Goto utasítás: nehézzé teszi a CFG olvashatóságát.
  • Függvényhívások: interprocedurális CFG nehezebben kezelhető.
  • Kivételkezelés (try-catch): nem lineáris vezérlés-átmeneteket okozhat.


✅ TL;DR

A Control-Flow Graph (CFG) egy irányított gráf, amely megmutatja, hogyan haladhat a vezérlés egy programon belül. Csomópontjai utasításblokkok, élei pedig végrehajtási lehetőségek. A CFG kulcsfontosságú a fordítókban, statikus elemzőkben, és a verifikációban – alapul szolgál például az adatfolyam-analízishez, optimalizálásokhoz és biztonsági auditokhoz.

A lap eredeti címe: „https://hu.wiktionary.org/w/index.php?title=control-flow_graph&oldid=3504446”