Bloque básico

En la construcción del compilador, un bloque básico es una secuencia de código de línea recta sin ramificaciones, excepto en la entrada y sin ramificaciones, excepto en la salida.^[1]​^[2]​ Esta forma restringida hace que un bloque básico sea altamente susceptible de análisis.^[3]​ Los compiladores generalmente descomponen los programas en sus bloques básicos como primer paso en el proceso de análisis. Los bloques básicos forman los vértices o nodos en un gráfico de flujo de control.

Definición

El código en un bloque básico tiene:

• Un punto de entrada, lo que significa que no hay código dentro de él es el destino de una instrucción de salto en cualquier parte del programa.
• Un punto de salida, lo que significa que solo la última instrucción puede hacer que el programa comience a ejecutar código en un bloque básico diferente.

En estas circunstancias, cada vez que se ejecuta la primera instrucción en un bloque básico, el resto de las instrucciones se ejecutan necesariamente exactamente una vez, en orden.^[4]​^[5]​ El código puede ser código fuente , código de ensamblaje o alguna otra secuencia de instrucciones. Más formalmente, una secuencia de instrucciones forma un bloque básico si:

• La instrucción en cada posición domina , o siempre se ejecuta antes, a todos aquellos en posiciones posteriores.
• Ninguna otra instrucción se ejecuta entre dos instrucciones en la secuencia.

Esta definición es más general que la intuitiva en algunos aspectos. Por ejemplo, permite saltos incondicionales a etiquetas que no están dirigidas por otros saltos. Esta definición incorpora las propiedades que hacen que los bloques básicos sean fáciles de trabajar al construir un algoritmo. Los bloques a los que se puede transferir el control después de llegar al final de un bloque se denominan sucesores de ese bloque, mientras que los bloques de los que puede haber llegado el control al entrar en un bloque se denominan predecesores de ese bloque. El inicio de un bloque básico se puede saltar desde más de una ubicación.

Creación algoritmo

El algoritmo para generar bloques básicos a partir de una lista de código es simple: el analizador escanea el código, marca los límites del bloque, que son instrucciones que pueden comenzar o finalizar un bloque porque transfieren el control o aceptan el control desde otro punto. Luego, el listado simplemente se "corta" en cada uno de estos puntos, y quedan bloques básicos.

Tenga en cuenta que este método no siempre genera bloques básicos máximos, según la definición formal, pero generalmente son suficientes (los bloques básicos máximos son bloques básicos que no pueden ampliarse incluyendo bloques adyacentes sin violar la definición de un bloque básico^[6]​).

Entrada: una secuencia de instrucciones (principalmente código de tres direcciones ).^[7]​

Salida: una lista de bloques básicos con cada declaración de tres direcciones en exactamente un bloque.

Paso 1. Identifique los líderes en el código. Los líderes son instrucciones que se incluyen en cualquiera de las siguientes 3 categorías:

1. La primera instrucción es un líder.
2. El objetivo de una instrucción goto / jump condicional o incondicional es un líder.
3. La instrucción que sigue inmediatamente a una instrucción goto / jump condicional o incondicional es un líder.

Paso 2. A partir de un líder, el conjunto de todas las instrucciones siguientes hasta y sin incluir el siguiente líder es el bloque básico correspondiente al líder inicial. Por lo tanto, cada bloque básico tiene un líder. Las instrucciones que finalizan un bloque básico incluyen lo siguiente:

• ramas incondicionales y condicionales, tanto directas como indirectas
• vuelve a un procedimiento de llamada
• instrucciones que pueden arrojar una excepción
• las llamadas a funciones pueden estar al final de un bloque básico si no pueden regresar, como funciones que arrojan excepciones o llamadas especiales como longjmp y exit C
• la instrucción de devolución en sí.

Las instrucciones que comienzan un nuevo bloque básico incluyen lo siguiente:

• puntos de entrada de procedimiento y función
• objetivos de saltos o ramas
• instrucciones "fall-through" siguiendo algunas ramas condicionales
• instrucciones que siguen a las que arrojan excepciones
• manejadores de excepciones.

Tenga en cuenta que, dado que el control nunca puede pasar por el final de un bloque básico, algunos límites de bloque pueden tener que modificarse después de encontrar los bloques básicos. En particular, las ramas condicionales de caída deben cambiarse a ramas bidireccionales, y las llamadas de función que lanzan excepciones deben tener saltos incondicionales agregados después de ellas. Hacer esto puede requerir agregar etiquetas al comienzo de otros bloques.

Referencias

1. Hennessy, John L., and David A. Patterson. Computer architecture: a quantitative approach. Elsevier, 2011.
2. Daniel), Cooper, Keith D. (Keith (2012). Engineering a compiler. Torczon, Linda. (2nd edición). Amsterdam: Elsevier/Morgan Kaufmann. p. 231. ISBN 012088478X. OCLC 714113472. 
3. "Control Flow Analysis" by Frances E. Allen
4. Yousefi, Javad (2015). Masking wrong-successor Control Flow Errors employing data redundancy. IEEE. pp. 201-205. doi:10.1109/ICCKE.2015.7365827. 
5. "Global Common Subexpression Elimination" by John Cocke
6. Modern Compiler Design by Dick Grune, Henri E. Bal, Ceriel J.H. Jacobs, and Koen G. Langendoen p320
7. Compiler Principles, Techniques and Tools, Aho Sethi Ullman

Enlaces externos

• Basic Blocks - GNU Compiler Collection
• Extended Basic Block - Wiktionary

•   Datos: Q76761870