Grundblock

I kompilatorkonstruktion är ett grundläggande block en rät linje kodsekvens utan förgreningar utom till ingången och inga förgreningar utom vid utgången. Denna begränsade form gör ett grundläggande block mycket mottagligt för analys. Kompilatorer brukar dekompilera program i sina grundläggande block som ett första steg i analysprocessen. Grundläggande block bildar hörn eller noder i ett kontrollflödesdiagram .

Definition

Koden i ett grundblock har:

En ingångspunkt , vilket betyder att ingen kod i den är destinationen för en hoppinstruktion någonstans i programmet.
En utgångspunkt, vilket betyder att endast den sista instruktionen kan få programmet att börja exekvera kod i ett annat grundblock.

Under dessa omständigheter, närhelst den första instruktionen i ett grundläggande block exekveras, exekveras resten av instruktionerna nödvändigtvis exakt en gång och i ordning.

Koden kan vara källkod , monteringskod eller någon annan sekvens av instruktioner.

Mer formellt utgör en sekvens av instruktioner ett grundläggande block om:

Instruktionen i varje position dominerar , eller utförs alltid före, alla de i senare positioner.
Ingen annan instruktion körs mellan två instruktioner i sekvensen.

Denna definition är mer generell än den intuitiva på vissa sätt. Till exempel tillåter det ovillkorliga hopp till etiketter som inte är inriktade på andra hopp. Denna definition förkroppsligar egenskaperna som gör grundläggande block lätta att arbeta med när man konstruerar en algoritm.

Blocken till vilka kontroll kan överföras efter att ha nått slutet av ett block kallas det blockets efterföljare , medan blocken från vilka kontroll kan ha kommit när man går in i ett block kallas det blockets föregångare . Starten av ett grundblock kan hoppas till från mer än en plats.

Skapande algoritm

Algoritmen för att generera grundläggande block från en kodlista är enkel: analysatorn skannar över koden, markerar blockgränser , som är instruktioner som antingen kan börja eller avsluta ett block eftersom de antingen överför kontroll eller accepterar kontroll från en annan punkt . Sedan "klipps" listningen helt enkelt vid var och en av dessa punkter, och grundläggande block kvarstår.

Observera att denna metod inte alltid genererar maximala basblock, enligt den formella definitionen, men de är vanligtvis tillräckliga (maximala basblock är basblock som inte kan utökas genom att inkludera angränsande block utan att bryta mot definitionen av ett basblock).

Inmatning : En sekvens av instruktioner (mest tre-adresskod ). Utdata : En lista över grundläggande block med varje tre-adresssats i exakt ett block.

Identifiera ledarna i koden. Ledare är instruktioner som hör till någon av följande tre kategorier:
1. Det är den första instruktionen. Den första instruktionen är en ledare.
2. Målet för en villkorlig eller ovillkorlig goto/jump-instruktion är en ledare.
3. Instruktionen som omedelbart följer en villkorlig eller en ovillkorlig goto/hoppinstruktion är en ledare.
Med utgångspunkt från en ledare, är uppsättningen av alla följande instruktioner till och inte inklusive nästa ledare grundblocket som motsvarar startledaren. Således har varje grundblock en ledare.

Instruktioner som avslutar ett grundläggande block inkluderar följande:

ovillkorliga och villkorade grenar , både direkta och indirekta;
återgår till ett anropsförfarande;
instruktioner som kan orsaka ett undantag ;
funktionsanrop kan vara i slutet av ett grundläggande block om de inte kan returnera, såsom funktioner som ger undantag eller specialanrop som C :s longjmp och exit ;
själva returinstruktionen.

Instruktioner som börjar ett nytt grundläggande block inkluderar följande:

ingångspunkter för procedur och funktion;
mål för hopp eller grenar;
"fall-through" instruktioner efter några villkorade grenar;
instruktioner efter sådana som ger undantag;
undantagshanterare.

Observera att eftersom kontroll aldrig kan passera genom slutet av ett grundblock, kan vissa blockgränser behöva modifieras efter att man hittat grundblocken. I synnerhet måste villkorliga fall-through-grenar ändras till tvåvägsgrenar, och funktionsanrop som kastar undantag måste ha ovillkorliga hopp tillagda efter sig. Att göra dessa kan kräva att du lägger till etiketter i början av andra block.

Se även

externa länkar