Ohjausvirtauskaavio ( englanniksi c control flow graph , CFG) - käännösteoriassa - joukko kaikkia mahdollisia ohjelman suoritustapoja, esitetty kuvaajana .
Ohjausvuokaaviossa graafin jokainen solmu (vertex) vastaa peruslohkoa - koodin suoraviivaista osaa, joka ei sisällä ohjauksen siirtotoimintoja tai pisteitä, joihin ohjaus siirretään ohjelman muista osista. On vain kaksi poikkeusta:
Suunnattuja kaaria käytetään kuvaajassa esittämään hyppykäskyjä. Useimmissa toteutuksissa on myös lisätty kaksi erikoistunutta lohkoa:
CFG - rakenne on tärkeä monille kääntäjien optimoinnille ja staattisen koodin analysointiapuohjelmille .
Kaksi tapausta on mahdollista: lohko tai osakuvaaja puuttuu:
Lohkoa, jota ei ole liitetty syöttölohkoon, pidetään tavoittamattomana ("kuollut" koodi). Saavutettavuus on yksi optimoinnissa käytetyistä graafin ominaisuuksista. Saavutamaton lohko voidaan poistaa ohjelmasta.
Lohko, jota ei ole liitetty lähtölohkoon, sisältää äärettömän silmukan. Tähän lauseeseen luottaen ei ole mahdollista havaita kaikkia äärettömiä silmukoita pysäytysongelman vuoksi .
Optimoinnissa kääntäjä voi luoda sekä "kuollutta" koodia että äärettömiä silmukoita, vaikka ohjelmoija ei olisi koodannut sitä erikseen. Esimerkiksi jatkuvan taittamisen ja jatkuvan etenemisen jälkeen hyppyketjutuksen optimointi voi yhdistää useita lohkoja yhdeksi; seurauksena jotkin reunat voivat kadota ja joitain lohkoja ei välttämättä yhdistetä kuvaajaan.
Seuraavia termejä käytetään usein käytettäessä ohjausvuokaavioita.
reuna suunnattu reuna (tai kaari), joka yhdistää graafilohkoja. Syöttölohko , sisääntulolohko, aloituslohko lohko, josta mikä tahansa polku alkaa. Poistu lohkosta , poistu lohkosta lohko, joka päättää minkä tahansa polun. Takareuna reuna, joka osoittaa edelliseen lohkoon, eli lohkoon, joka olisi kuljetettu aikaisemmin graafin läpikulkuprosessin aikana . kriittinen reuna reuna, joka on peräisin lohkosta, jossa on useita lähteviä reunoja, ja tulee lohkoon, jossa on useita saapuvia reunoja. Epänormaali reuna reuna, joka lähtee yhdestä lohkosta ja ei mene toiseen lohkoon, koska jälkimmäistä ei voida laskea. Esiintyy esimerkiksi poikkeuksenkäsittelykonstruktin muuntamisen jälkeen . Tällaiset reunat häiritsevät optimointia. Mahdoton reuna graafiin lisätty reuna vain sen ominaisuuden säilyttämiseksi, että tuloslohko on jälkidominoiva muihin lohkoihin nähden. Tätä reunaa ei voi ylittää. Dominator , dominator, pakollinen edeltäjä Lohkon M sanotaan olevan hallitseva lohkon N suhteen, jos mikä tahansa polku tulolohkosta lohkoon N kulkee lohkon M läpi. Syöttölohko hallitsee kaikkia muita kaavion lohkoja. Postdominaattori , postdominaattori Lohkon M sanotaan olevan jälkidominantti lohkon N suhteen, jos mikä tahansa polku N:stä lähtölohkoon kulkee lohkon M läpi. Lähtösolmu jälkidominoi graafin kaikissa lohkoissa. Välitön hallitseja , välitön hallitseja Lohkon M sanotaan olevan suoraan hallitseva lohko N, jos lohko M hallitsee lohkoa N, eikä ole muuta välilohkoa P, jota hallitsee lohko M ja joka hallitsee lohkoa N. Toisin sanoen M on viimeinen dominatori kaikilla poluilla tulolohkosta lohkoon N Jokaisella lohkolla paitsi tuloa on yksi välitön dominatori. Välitön postdominaattori analogi termille välitön dominantti, mutta postdominaattorille. Dominator puu apupuutietorakenne , joka sisältää tietoa dominanssisuhteista . Haara lohkosta M lohkoon N luodaan, jos ja vain jos lohko M on N:n välitön dominatori. Tietorakenne on puu, koska jokaisella lohkolla on ainutlaatuinen välitön dominatori. Puun juuri on syöttösolmu. Rakentamiseen käytetään tehokasta Lengauer-Tarjanin algoritmia . Postdominator puu Dominator-puun analogi , mutta postdominaattoreille. Puun juuri on lähtölohko. Silmukan otsikko , silmukan otsikko, silmukan sisääntulokohta kappale, joka on yhdistetty reunoilla kaikkiin pyörän rungon lohkoihin. Lohko hallitsee kaikkia silmukan rungon solmuja. Silmukan esiotsikko lohko, joka on liitetty reunalla silmukan otsikkolohkoon ; välitön dominantti silmukan sisääntulopisteelle. Olkoon lohko M silmukan sisääntulokohta. Joissakin optimointivaiheissa on edullista, että M-lohko jaetaan kahteen lohkoon: M pre (silmukan otsikko) ja M loop (silmukan otsikko). Lohkon M jakamisen jälkeen sen sisältö ja takareunat siirretään M silmukkalohkoon ja loput reunat M esilohkoon ; sitten luodaan uusi reuna, joka yhdistää M - esilohkon M- silmukkalohkoon ; siten M - esilohkosta tulee M- silmukkalohkon suora dominatori . M - esilohko ei sisällä koodia ennen kuin jotkin optimoinnit, kuten silmukkainvarianttikoodiliike , täydentävät sen sisällön .Koodinpätkä:
0: (A)t0 = luku_num 1: (A) jos t0 mod 2 == 0 goto 4 2: (B) tulosta t0 + " on pariton." 3: (B) meni 5 4: (C) tulosta t0 + "on parillinen." 5: (D) lopeta ohjelmaOhjauksen vuokaavio koostuu 4 peruslohkosta: A rivit 0-1, B rivit 2-3, C rivit 4 ja D 5. riviä. Kaaviossa on kaaria A -> B, A -> C, B -> D, C -> D.