Bloque básico
Secuencia de código sin ramificaciones excepto en la entrada y la salida

En la construcción de compiladores , un bloque básico es una secuencia de código en línea recta sin ramificaciones de entrada excepto en la entrada y sin ramificaciones 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 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 ningún código dentro de él es el destino de una instrucción de salto en ninguna parte del programa.
  • Un punto de salida, lo que significa que sólo 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 exactamente una vez y en orden. [4] [5]

El código puede ser código fuente , código ensamblador 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 (siempre se ejecuta antes) que todas las de 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 son el objetivo de otros saltos. Esta definición incorpora las propiedades que hacen que sea fácil trabajar con bloques básicos 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 venido el 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 una lista de código es simple: el analizador recorre el código y marca los límites de los bloques , que son instrucciones que pueden comenzar o finalizar un bloque porque transfieren el control o lo aceptan desde otro punto. Luego, la lista simplemente se "corta" en cada uno de estos puntos y los bloques básicos permanecen.

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 se pueden extender mediante la inclusión de bloques adyacentes sin violar la definición de un bloque básico [6] ).

Entrada : Una secuencia de instrucciones (principalmente códigos de tres direcciones ). [7]
Salida : Una lista de bloques básicos con cada instrucción de tres direcciones en exactamente un bloque.

  1. Identifique a 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 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.
  2. Partiendo de un líder, el conjunto de todas las instrucciones siguientes hasta el líder siguiente (sin incluirlo) 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 las siguientes:

  • ramas incondicionales y condicionales , tanto directas como indirectas;
  • vuelve a un procedimiento de llamada;
  • instrucciones que pueden generar una excepción ;
  • Las llamadas de función pueden estar al final de un bloque básico si no pueden regresar, como funciones que lanzan excepciones o llamadas especiales como C y .longjmpexit

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

  • puntos de entrada de procedimientos y funciones;
  • objetivos de saltos o ramas;
  • instrucciones de "fall-through" que siguen a algunas ramas condicionales;
  • instrucciones que siguen a las que lanzan excepciones;
  • manejadores de excepciones

Tenga en cuenta que, debido a que el control nunca puede pasar por el final de un bloque básico, es posible que sea necesario modificar algunas instrucciones para encontrar los bloques básicos. En particular, las bifurcaciones condicionales de paso deben cambiarse a bifurcaciones de dos vías, y las llamadas a funciones que lanzan excepciones deben tener saltos incondicionales agregados después de ellas. Para hacer esto, es posible que sea necesario agregar etiquetas al comienzo de otros bloques.

Véase también

Referencias

  1. ^ Hennessy, John L.; David A. Patterson. Arquitectura informática: 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-0120884780.OCLC 714113472  .
  3. ^ "Análisis del flujo de control" por Frances E. Allen.
  4. ^ Yousefi, Javad (2015). "Enmascaramiento de errores de flujo de control de sucesores erróneos empleando redundancia de datos". 2015 5.ª Conferencia internacional sobre ingeniería informática y del conocimiento (ICCKE) . IEEE. págs. 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 del compilador, Aho Sethi Ullman.
  • Bloques básicos - Colección de compiladores GNU
  • Bloque básico extendido - Wikcionario
Obtenido de "https://es.wikipedia.org/w/index.php?title=Bloque_básico&oldid=1238067209"