Kontrol -flow -graf - Control-flow graph

Image
Nogle CFG-eksempler:
(a) en if-then-else
(b) en while-loop
(c) en naturlig loop med to udgange, f.eks. Mens med et if ... break i midten; ikke-struktureret, men reducerbar
(d) en ureducerbar CFG: en sløjfe med to indgangspunkter, f.eks. gå ind i et stykke tid eller for sløjfe
Image
En kontrolflowdiagram, der bruges af Rust -kompilatoren til at udføre kodegen.

I datalogi , en kontrol-rutediagram ( CFG ) er en repræsentation , anvendelse graf notation, af alle veje, der kan være gennemkøres gennem et program under dens udførelse . Kontrol-flow-grafen blev opdaget af Frances E. Allen , der bemærkede, at Reese T. Prosser brugte boolske tilslutningsmatricer til flowanalyse før.

CFG er afgørende for mange kompilatoroptimeringer og statiske analyseværktøjer .

Definition

I en kontrol-flow-graf repræsenterer hver node i grafen en grundlæggende blok , dvs. et lige stykke kode uden spring eller springmål ; springmål starter en blok, og spring ender en blok. Retede kanter bruges til at repræsentere spring i kontrolstrømmen . Der er i de fleste præsentationer to særligt udpegede blokke: indgangsblokken , gennem hvilken kontrol kommer ind i flowgrafen, og udgangsblokken , hvorigennem alle kontrolflow forlader.

På grund af dens konstruktionsprocedure i en CFG har hver kant A → B den egenskab, at:

grad (A)> 1 eller indegree (B)> 1 (eller begge dele).

CFG kan således opnås, i det mindste konceptuelt, ved at starte fra programmets (fulde) flowdiagram - dvs. grafen, hvor hver knude repræsenterer en individuel instruktion - og udføre en kantkontraktion for hver kant, der forfalsker prædikatet ovenfor, dvs. hver kant, hvis kilde har en enkelt exit, og hvis destination har en enkelt post. Denne sammentrækningsbaserede algoritme har ingen praktisk betydning, undtagen som et visualiseringshjælpemiddel til forståelse af CFG-konstruktionen, fordi CFG'en mere effektivt kan konstrueres direkte fra programmet ved at scanne den efter grundlæggende blokke .

Eksempel

Overvej følgende kodefragment: 

0: (A) t0 = read_num
1: (A) if t0 mod 2 == 0
2: (B)   print t0 + " is even."
3: (B)   goto 5
4: (C) print t0 + " is odd."
5: (D) end program

I ovenstående har vi 4 grundlæggende blokke: A fra 0 til 1, B fra 2 til 3, C ved 4 og D ved 5. Især i dette tilfælde er A "indgangsblokken", D "udgangsblokken "og linje 4 og 5 er springmål. En graf for dette fragment har kanter fra A til B, A til C, B til D og C til D.

Nåbarhed

Hovedartikel: Nåbarhed

Nåbarhed er en grafegenskab, der er nyttig til optimering.

Hvis en undergraf ikke er forbundet fra subgrafen, der indeholder indgangsblokken, er denne undergraf ikke tilgængelig under enhver udførelse, og det samme er utilgængelig kode ; under normale forhold kan den sikkert fjernes.

Hvis exitblokken ikke kan nås fra indgangsblokken, kan der findes en uendelig loop . Ikke alle uendelige sløjfer kan påvises, se Stop problem . Der kan også være en standseringsordre der.

Uopnåelig kode og uendelige sløjfer er mulige, selvom programmereren ikke eksplicit koder dem: optimeringer som konstant udbredelse og konstant foldning efterfulgt af springtråd kan kollapse flere grundlæggende blokke til en, få kanter til at blive fjernet fra en CFG osv., Og dermed evt. afbryde dele af grafen.

Dominansforhold

Hovedartikel: Dominator (grafteori)

En blok M dominerer en blok N, hvis hver vej fra posten, der når blok N, skal passere gennem blok M. Indgangsblokken dominerer alle blokke.

I modsat retning blokerer blok M postdominering blok N, hvis hver vej fra N til afkørslen skal passere gennem blok M. Udgangsblokken postdominerer alle blokke.

Det siges, at en blok M umiddelbart dominerer blok N, hvis M dominerer N, og der ikke er nogen mellemliggende blok P, således at M dominerer P og P dominerer N. Med andre ord er M den sidste dominator på alle stier fra indgang til N. Hver blok har en unik umiddelbar dominator.

På samme måde er der en forestilling om umiddelbar postdominator , analog med umiddelbar dominator .

Den Dominator træ er en accessorisk datastruktur skildrer Dominator relationer. Der er en bue fra blok M til blok N, hvis M er en umiddelbar dominator af N. Denne graf er et træ, da hver blok har en unik umiddelbar dominator. Dette træ er forankret i indgangsblokken. Dominator -træet kan beregnes effektivt ved hjælp af Lengauer -Tarjans algoritme .

Et postdominator træ er analogt med dominator træet . Dette træ er forankret ved udgangsblokken.

Særlige kanter

En bagkant er en kant, der peger på en blok, der allerede er blevet opfyldt under en dybde-først ( DFS ) traversal af grafen. Bagkanter er typiske for sløjfer.

En kritisk kant er en kant, der hverken er den eneste kant, der forlader sin kildeblok, eller den eneste kant, der kommer ind i sin destinationsblok. Disse kanter skal deles : en ny blok skal oprettes i midten af ​​kanten for at indsætte beregninger på kanten uden at påvirke andre kanter.

En unormal kant er en kant, hvis destination er ukendt. Undtagelseshåndteringskonstruktioner kan producere dem. Disse kanter har en tendens til at hæmme optimering.

En umulig kant (også kendt som en falsk kant ) er en kant, der er tilføjet til grafen udelukkende for at bevare den egenskab, at exitblokken postdominerer alle blokke. Det kan aldrig krydses.

Loop management

Et loop-header (undertiden kaldet loop- indgangens punkt ) er en dominator, der er målet for en loop-dannende bagkant. Loop -headeren dominerer alle blokke i loop -kroppen. En blok kan være en loop -header til mere end en loop. En loop kan have flere indgangspunkter, i hvilket tilfælde den ikke har et "loop header".

Antag, at blok M er en dominator med flere indgående kanter, hvoraf nogle er bagkanter (så M er et loop -header). Det er fordelagtigt ved flere optimeringspasninger at opdele M i to blokke M pre og M loop . Indholdet af M og bagkanter flyttes til M loop , resten af ​​kanterne flyttes til at pege i M pre , og en ny kant fra M pre til M loop indføres (så M pre er den umiddelbare dominator af M loop ). I begyndelsen ville M pre være tom, men passerer som loop-invariant kodebevægelse kan udfylde den. M pre kaldes loop-pre-header , og M loop vil være loop-header.

Reducerbarhed

En reducerbar CFG er en med kanter, der kan opdeles i to usammenhængende sæt: forreste kanter og bagkanter, således at:

  • Fremadkanter danner en rettet acyklisk graf med alle knudepunkter, der kan nås fra indgangsknudepunktet.
  • For alle bagkanter (A, B) dominerer knude B knude A.

Strukturerede programmeringssprog er ofte designet således, at alle CFG'er, de producerer, kan reduceres, og almindelige strukturerede programmeringsudsagn som IF, FOR, WHILE, BREAK og CONTINUE producerer reducerbare grafer. For at producere ureducerbare grafer er der brug for udsagn som f.eks. GOTO . Ureducerbare grafer kan også frembringes ved nogle kompilatoroptimeringer.

Sløjfeforbindelse

Loopforbindelsen for en CFG er defineret i forhold til et givet dybde-første søgetræ (DFST) for CFG. Denne DFST bør være forankret ved startnoden og dække hver knude i CFG.

Kanter i CFG, der løber fra en knude til en af ​​dens DFST -forfædre (inklusive sig selv) kaldes bagkanter.

Sløjfeforbindelsen er det største antal bagkanter, der findes i enhver cyklusfri sti for CFG. I en reducerbar CFG er sløjfeforbindelsen uafhængig af den valgte DFST.

Loop-forbindelse er blevet brugt til at ræsonnere om tidskompleksiteten i dataflowanalyser .

Mellemprocedurel kontrolflowdiagram

Mens kontrolstrømningsgrafer repræsenterer kontrolforløbet for en enkelt procedure, repræsenterer tværprocedurelle kontrolflowgrafer kontrolflowet for hele programmer.


See also

Referencer

eksterne links

Eksempler