Blocco di base - Basic block

Nella costruzione del compilatore , un blocco di base è una sequenza di codice lineare senza diramazioni tranne che per l'entrata e senza diramazioni tranne che per l'uscita. Questa forma ristretta rende un blocco di base altamente suscettibile di analisi. I compilatori di solito scompongono i programmi nei loro blocchi di base come primo passo nel processo di analisi. I blocchi di base formano i vertici o nodi in un grafo di flusso di controllo .

Definizione

Il codice in un blocco di base ha:

  • Un punto di ingresso , il che significa che nessun codice al suo interno è la destinazione di un'istruzione di salto in qualsiasi punto del programma.
  • Un punto di uscita, ovvero solo l'ultima istruzione può far sì che il programma inizi l'esecuzione del codice in un blocco di base diverso.

In queste circostanze, ogni volta che viene eseguita la prima istruzione in un blocco di base, il resto delle istruzioni viene necessariamente eseguito esattamente una volta, in ordine.

Il codice può essere codice sorgente , codice assembly o qualche altra sequenza di istruzioni.

Più formalmente, una sequenza di istruzioni forma un blocco di base se:

  • L'istruzione in ciascuna posizione domina , o esegue sempre prima, tutte quelle nelle posizioni successive.
  • Nessun'altra istruzione viene eseguita tra due istruzioni nella sequenza.

Questa definizione è più generale di quella intuitiva per certi versi. Ad esempio, consente salti incondizionati a etichette non mirate da altri salti. Questa definizione incarna le proprietà che rendono i blocchi di base facili da lavorare quando si costruisce un algoritmo.

I blocchi a cui il controllo può essere trasferito dopo aver raggiunto la fine di un blocco sono chiamati successori di quel blocco , mentre i blocchi da cui può provenire il controllo quando si entra in un blocco sono chiamati predecessori di quel blocco . È possibile saltare l'inizio di un blocco di base da più di una posizione.

Algoritmo di creazione

L' algoritmo per la generazione di blocchi di base da un elenco di codice è semplice: l'analizzatore esegue la scansione del codice, contrassegnando i confini del blocco , che sono istruzioni che possono iniziare o terminare un blocco perché trasferiscono il controllo o accettano il controllo da un altro punto. Quindi, l'elenco viene semplicemente "tagliato" in ciascuno di questi punti e rimangono i blocchi di base.

Si noti che questo metodo non genera sempre blocchi di base massimi , secondo la definizione formale, ma di solito sono sufficienti (i blocchi di base massimi sono blocchi di base che non possono essere estesi includendo blocchi adiacenti senza violare la definizione di un blocco di base).

Input : una sequenza di istruzioni (principalmente codice a tre indirizzi ).
Output : un elenco di blocchi di base con ciascuna istruzione a tre indirizzi esattamente in un blocco.

  1. Identifica i leader nel codice. I leader sono istruzioni che rientrano in una delle seguenti 3 categorie:
    1. È la prima istruzione. La prima istruzione è un leader.
    2. L'obiettivo di un'istruzione goto / jump condizionale o incondizionata è un leader.
    3. L'istruzione che segue immediatamente un'istruzione goto / jump condizionale o incondizionata è una guida.
  2. Partendo da un leader, l'insieme di tutte le istruzioni successive fino a quando non includendo il leader successivo è il blocco di base corrispondente al leader iniziale. Quindi ogni blocco di base ha un leader.

Le istruzioni che terminano un blocco di base includono quanto segue:

  • rami incondizionati e condizionali , sia diretti che indiretti
  • ritorna a una procedura chiamante
  • istruzioni che possono generare un'eccezione
  • chiamate di funzione possono essere alla fine di un blocco di base se non possono tornare, come funzioni che producono eccezioni o chiamate speciali come C s' longjmp e exit
  • l'istruzione di ritorno stessa.

Le istruzioni che iniziano un nuovo blocco di base includono quanto segue:

  • punti di ingresso di procedure e funzioni
  • bersagli di salti o rami
  • istruzioni "fall-through" che seguono alcuni rami condizionali
  • istruzioni che seguono quelle che generano eccezioni
  • gestori di eccezioni.

Si noti che, poiché il controllo non può mai passare attraverso la fine di un blocco di base, potrebbe essere necessario modificare alcuni confini del blocco dopo aver trovato i blocchi di base. In particolare, i rami condizionali fallici devono essere modificati in rami a due vie e le chiamate di funzione che generano eccezioni devono avere salti incondizionati aggiunti dopo di essi. In questo modo potrebbe essere necessario aggiungere etichette all'inizio di altri blocchi.

Guarda anche

Riferimenti

link esterno