Bloques básicos en el diseño del compilador

El bloque básico es una secuencia de código de línea recta que no tiene bifurcaciones de entrada y salida, excepto en la entrada y al final, respectivamente. Basic Block es un conjunto de sentencias que siempre se ejecutan una detrás de otra, en una secuencia. 

La primera tarea es dividir una secuencia de código de tres direcciones en bloques básicos. Se inicia un nuevo bloque básico con la primera instrucción y se van añadiendo instrucciones hasta alcanzar un salto o una etiqueta. En ausencia de un salto, el control se mueve consecutivamente de una instrucción a otra. La idea está estandarizada en el siguiente algoritmo: 

Algoritmo: 
partición de código de tres direcciones en bloques básicos. 

Entrada: Una secuencia de tres instrucciones de dirección. 

Proceso: Se determinan las instrucciones del código intermedio que son líderes. Las siguientes son las reglas utilizadas para encontrar un líder: 
 

1. La primera instrucción de tres direcciones del código intermedio es un líder. 
    
2. Las instrucciones que son objetivos de sentencias de salto/goto incondicionales o condicionales son líderes. 
    
3. Las instrucciones que siguen inmediatamente a declaraciones de salto/ir a incondicionales o condicionales se consideran líderes. 
    

Para cada líder así determinado, su bloque básico se contiene a sí mismo y todas las instrucciones hasta excluir al siguiente líder. 

Ejemplo 1: 

La siguiente secuencia de declaraciones de tres direcciones forma un bloque básico:

t1 := a*a

t2 := a*b

t3 := 2*t2

t4 := t1+t3

t5 := b*b

t6 := t4 +t5

Se dice que una declaración de tres direcciones x:= y+z define x y usa y y z. Se dice que un nombre en un bloque básico está vivo en un punto dado si su valor se usa después de ese punto en el programa, quizás en otro bloque básico.

Ejemplo 2: 
código intermedio para establecer una array de 10*10 en una array de identidad: 

1)  i=1        //Leader 1 (First statement)
2)  j=1             //Leader 2 (Target of 11th statement)
3)  t1 = 10 * i     //Leader 3 (Target of 9th statement) 
4)  t2 = t1 + j
5)  t3 = 8 * t2
6)  t4 = t3 - 88
7)  a[t4] = 0.0
8)  j = j + 1
9)  if j <= goto (3)       
10) i = i + 1                    //Leader 4 (Immediately following Conditional goto statement)
11) if i <= 10 goto (2)
12) i = 1                        //Leader 5 (Immediately following Conditional goto statement)
13) t5 = i - 1                   //Leader 6 (Target of 17th statement) 
14) t6 = 88 * t5
15) a[t6] = 1.0
16) i = i + 1
17) if i <= 10 goto (13) 

El algoritmo dado se utiliza para convertir una array en array identidad, es decir, una array con todos los elementos diagonales 1 y todos los demás elementos como 0. 

Los pasos (3)-(6) se usan para hacer que los elementos sean 0, el paso (14) se usa para hacer que un elemento sea 1. Estos pasos se usan recursivamente por instrucciones goto. 

Hay 6 bloques básicos en el código anterior: 
B1) Declaración 1 
B2) Declaración 2 
B3) Declaración 3-9 
B4) Declaración 10-11 
B5) Declaración 12 
B6) Declaración 13-17