Hispanopedia Wiki
Articulo de referencia

Bloque básico

En la construcción de compiladores , un bloque básico es una secuencia de código lineal sin bifurcaciones de entrada excepto hacia la entrada y sin bifurcaciones de salida excep...

Hispanopedia WikiContenido en espanolLectura gratuita

En la construcción de compiladores , un bloque básico es una secuencia de código lineal sin bifurcaciones de entrada excepto hacia la entrada y sin bifurcaciones de salida excepto en la salida. [ 1 ] [ 2 ] Esta forma restringida hace que un bloque básico sea muy susceptible al análisis. [ 3 ] Los compiladores suelen descomponer 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 grafo de flujo de control .

Definición

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

  • Un único punto de entrada , lo que significa que ningún código dentro de él es el destino de una instrucción de salto en ninguna parte del programa.
  • Un único 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, siempre que se ejecuta la primera instrucción de un bloque básico, el resto de las instrucciones se ejecutan necesariamente una sola vez y en orden. [ 4 ] [ 5 ]

El código puede ser código fuente , código ensamblador o alguna otra secuencia de instrucciones.

De forma más formal, una secuencia de instrucciones forma un bloque básico si:

  • La instrucción en cada posición domina (siempre se ejecuta antes) a todas las que se encuentran en posiciones posteriores.
  • No se ejecuta ninguna otra instrucción entre dos instrucciones en la secuencia.

Esta definición es, en cierto modo, más general que la intuitiva. Por ejemplo, permite saltos incondicionales a etiquetas que no son el objetivo de otros saltos. Esta definición incorpora las propiedades que facilitan el trabajo con bloques básicos al construir un algoritmo.

Los bloques a los que se puede transferir el control tras llegar al final de un bloque se denominan sucesores de ese bloque , mientras que los bloques desde los que se puede haber accedido al control al entrar en un bloque se denominan predecesores de ese bloque . Se puede saltar al inicio de un bloque básico desde más de una ubicación.

Algoritmo de creación

El algoritmo para generar bloques básicos a partir de un listado de código es sencillo: el analizador recorre el código, marcando los límites de los bloques , que son instrucciones que pueden iniciar o finalizar un bloque, ya que transfieren o aceptan el control desde otro punto. A continuación, el listado se "corta" en cada uno de estos puntos, y quedan los 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 suelen ser suficientes (los bloques básicos máximos son bloques básicos que no se pueden extender 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 instrucción de tres direcciones en exactamente un bloque.

  1. Identifica los líderes en el código. Los líderes son instrucciones que se incluyen en cualquiera de las siguientes 3 categorías:
    1. Es la primera instrucción. La primera instrucción es un líder.
    2. El destinatario 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.
  2. Partiendo de un líder, el conjunto de todas las instrucciones subsiguientes, hasta llegar al siguiente líder (sin incluirlo), constituye el bloque básico correspondiente a dicho líder. Por lo tanto, cada bloque básico tiene un líder.

Las instrucciones que finalizan un bloque básico incluyen las siguientes:

  • ramas incondicionales y condicionales , tanto directas como indirectas;
  • regresa a un procedimiento de llamada;
  • instrucciones que pueden generar una excepción ;
  • Las llamadas a funciones pueden estar al final de un bloque básico si no pueden devolver ningún valor, como por ejemplo las funciones que lanzan excepciones o las llamadas especiales como las de C.longjmpexit

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

  • Puntos de entrada de procedimientos y funciones;
  • objetivos de saltos o ramificaciones;
  • Instrucciones "de ejecución secuencial" tras algunas bifurcaciones condicionales;
  • instrucciones que siguen a aquellas que generan excepciones;
  • manejadores de excepciones.

Tenga en cuenta que, dado que el control nunca puede pasar del final de un bloque básico, es posible que algunas instrucciones deban modificarse para encontrar los bloques básicos. En particular, las bifurcaciones condicionales de continuación deben cambiarse a bifurcaciones bidireccionales, y las llamadas a funciones que lanzan excepciones deben incluir saltos incondicionales después de ellas. Para ello, puede ser necesario añadir etiquetas al inicio de otros bloques.

Véase también

Referencias

  1. ↑ Hennessy, John L.; David A. Patterson. Arquitectura de computadoras: un enfoque cuantitativo . Elsevier, 2011.
  2. ↑ Cooper, Keith Daniel; Torczon, Linda (2012). Ingeniería de un compilador (2.ª  ed.). Ámsterdam : Elsevier/Morgan Kaufmann. pág.  231. ISBN 978-0120884780OCLC 714113472​​ 
  3. ↑ "Análisis del flujo de control" por Frances E. Allen.
  4. ↑ Yousefi, Javad (2015). "Enmascaramiento de errores de flujo de control de sucesor incorrecto mediante redundancia de datos". 5.ª Conferencia Internacional de Ingeniería Informática y del Conocimiento (ICCKE) de 2015. IEEE. pp. 201–205 . doi : 10.1109/ICCKE.2015.7365827 . ISBN  978-1-4673-9280-8.
  5. ↑ "Eliminación de subexpresiones comunes globales" por John Cocke.
  6. ^ Diseño de compilador moderno por Dick Grune, Henri E. Bal, Ceriel JH Jacobs y Koen G. Langendoen, p. 320.
  7. ↑ Principios, técnicas y herramientas de compilación, Aho Sethi Ullman.