Diseño del compilador: generación de código

La generación de código puede considerarse como la fase final de la compilación. A través de la generación de código posterior, el proceso de optimización se puede aplicar en el código, pero eso puede verse como parte de la propia fase de generación de código. El código generado por el compilador es un código objeto de algún lenguaje de programación de nivel inferior, por ejemplo, lenguaje ensamblador. Hemos visto que el código fuente escrito en un lenguaje de nivel superior se transforma en un lenguaje de nivel inferior que da como resultado un código objeto de nivel inferior, que debe tener las siguientes propiedades mínimas:

  • Debe tener el significado exacto del código fuente.
  • Debería ser eficiente en términos de uso de CPU y administración de memoria.

Ahora veremos cómo el código intermedio se transforma en código objeto de destino (código ensamblador, en este caso).

Gráfico Acíclico Dirigido

El gráfico acíclico dirigido (DAG) es una herramienta que describe la estructura de los bloques básicos, ayuda a ver el flujo de valores que fluyen entre los bloques básicos y también ofrece optimización. DAG proporciona una fácil transformación en bloques básicos. DAG se puede entender aquí:

  • Los nodos hoja representan identificadores, nombres o constantes.

  • Los nodos interiores representan operadores.

  • Los nodos interiores también representan los resultados de las expresiones o los identificadores / nombre donde se almacenarán o asignarán los valores.

Example:

t0 = a + b
t1 = t0 + c
d = t0 + t1

[t 0 = a + b]

[t 1 = t 0 + c]

[d = t 0 + t 1 ]

Optimización de mirilla

Esta técnica de optimización trabaja localmente en el código fuente para transformarlo en un código optimizado. Por local, nos referimos a una pequeña parte del bloque de código en cuestión. Estos métodos se pueden aplicar tanto en códigos intermedios como en códigos objetivo. Se analizan un montón de declaraciones y se comprueban para la siguiente optimización posible:

Eliminación de instrucciones redundantes

A nivel de código fuente, el usuario puede hacer lo siguiente:

int add_ten(int x)
   {
   int y, z;
   y = 10;
   z = x + y;
   return z;
   }
 
int add_ten(int x)
   {
   int y;
   y = 10;
   y = x + y;
   return y;
   }
 
int add_ten(int x)
   {
   int y = 10;
   return x + y;
   }
 
int add_ten(int x)
   {
   return x + 10;
   }

A nivel de compilación, el compilador busca instrucciones de naturaleza redundante. La carga y el almacenamiento múltiples de instrucciones pueden tener el mismo significado incluso si se eliminan algunas de ellas. Por ejemplo:

  • MOV x, R0
  • MOV R0, R1

Podemos eliminar la primera instrucción y reescribir la oración como:

MOV x, R1

Código inalcanzable

El código inalcanzable es una parte del código del programa al que nunca se accede debido a las construcciones de programación. Los programadores pueden haber escrito accidentalmente un fragmento de código al que nunca se podrá acceder.

Example:

void add_ten(int x)
{
   return x + 10;
   printf(“value of x is %d”, x);
}

En este segmento de código, el printf La declaración nunca se ejecutará ya que el control del programa regresa antes de que pueda ejecutarse, por lo tanto printf se puede quitar.

Optimización del flujo de control

Hay casos en un código donde el control del programa salta hacia adelante y hacia atrás sin realizar ninguna tarea significativa. Estos saltos se pueden eliminar. Considere el siguiente fragmento de código:

...		
MOV R1, R2
GOTO L1
...
L1 :   GOTO L2
L2 :   INC R1

En este código, la etiqueta L1 se puede quitar cuando pasa el control a L2. Entonces, en lugar de saltar a L1 y luego a L2, el control puede llegar directamente a L2, como se muestra a continuación:

...		
MOV R1, R2
GOTO L2
...
L2 :   INC R1

Simplificación de expresiones algebraicas

Hay ocasiones en las que las expresiones algebraicas se pueden simplificar. Por ejemplo, la expresióna = a + 0 puede ser reemplazado por a sí mismo y la expresión a = a + 1 simplemente se puede reemplazar por INC a.

Reducción de fuerza

Hay operaciones que consumen más tiempo y espacio. Su 'fuerza' se puede reducir reemplazándolos con otras operaciones que consumen menos tiempo y espacio, pero producen el mismo resultado.

Por ejemplo, x * 2 puede ser reemplazado por x << 1, que implica solo un desplazamiento a la izquierda. Aunque la salida de a * ay a 2 es la misma, a 2 es mucho más eficiente de implementar.

Acceso a las instrucciones de la máquina

La máquina de destino puede implementar instrucciones más sofisticadas, que pueden tener la capacidad de realizar operaciones específicas de manera muy eficiente. Si el código de destino puede acomodar esas instrucciones directamente, eso no solo mejorará la calidad del código, sino que también producirá resultados más eficientes.

Generador de códigos

Se espera que un generador de código comprenda el entorno de ejecución de la máquina de destino y su conjunto de instrucciones. El generador de código debe tener en cuenta lo siguiente para generar el código:

  • Target language: El generador de código debe conocer la naturaleza del idioma de destino para el que se va a transformar el código. Ese lenguaje puede facilitar algunas instrucciones específicas de la máquina para ayudar al compilador a generar el código de una manera más conveniente. La máquina de destino puede tener arquitectura de procesador CISC o RISC.

  • IR Type: La representación intermedia tiene varias formas. Puede estar en estructura de árbol de sintaxis abstracta (AST), notación polaca inversa o código de 3 direcciones.

  • Selection of instruction: El generador de código toma la Representación intermedia como entrada y la convierte (mapea) en el conjunto de instrucciones de la máquina de destino. Una representación puede tener muchas formas (instrucciones) para convertirla, por lo que es responsabilidad del generador de código elegir sabiamente las instrucciones adecuadas.

  • Register allocation: Un programa tiene una serie de valores que deben mantenerse durante la ejecución. Es posible que la arquitectura de la máquina de destino no permita que todos los valores se mantengan en la memoria o los registros de la CPU. El generador de código decide qué valores mantener en los registros. Además, decide los registros que se utilizarán para mantener estos valores.

  • Ordering of instructions: Por fin, el generador de código decide el orden en el que se ejecutará la instrucción. Crea horarios para instrucciones para ejecutarlos.

Descriptores

El generador de código tiene que rastrear tanto los registros (para disponibilidad) como las direcciones (ubicación de valores) mientras genera el código. Para ambos, se utilizan los siguientes dos descriptores:

  • Register descriptor: El descriptor de registro se utiliza para informar al generador de código sobre la disponibilidad de registros. El descriptor de registro realiza un seguimiento de los valores almacenados en cada registro. Siempre que se requiera un nuevo registro durante la generación del código, se consulta este descriptor para conocer la disponibilidad del registro.

  • Address descriptor: Los valores de los nombres (identificadores) utilizados en el programa pueden almacenarse en diferentes ubicaciones durante la ejecución. Los descriptores de dirección se utilizan para realizar un seguimiento de las ubicaciones de la memoria donde se almacenan los valores de los identificadores. Estas ubicaciones pueden incluir registros de CPU, montones, pilas, memoria o una combinación de las ubicaciones mencionadas.

El generador de código mantiene ambos descriptores actualizados en tiempo real. Para una declaración de carga, LD R1, x, el generador de código:

  • actualiza el descriptor de registro R1 que tiene un valor de xy
  • actualiza el descriptor de direcciones (x) para mostrar que una instancia de x está en R1.

Codigo de GENERACION

Los bloques básicos se componen de una secuencia de instrucciones de tres direcciones. El generador de código toma esta secuencia de instrucciones como entrada.

Note: Si el valor de un nombre se encuentra en más de un lugar (registro, caché o memoria), se preferirá el valor del registro sobre el caché y la memoria principal. Asimismo, se preferirá el valor de la caché sobre la memoria principal. A la memoria principal apenas se le da preferencia.

getReg: El generador de código utiliza la función getReg para determinar el estado de los registros disponibles y la ubicación de los valores de los nombres. getReg funciona de la siguiente manera:

  • Si la variable Y ya está en el registro R, usa ese registro.

  • De lo contrario, si algún registro R está disponible, usa ese registro.

  • De lo contrario, si ambas opciones anteriores no son posibles, elige un registro que requiere un número mínimo de instrucciones de carga y almacenamiento.

Para una instrucción x = y OP z, el generador de código puede realizar las siguientes acciones. Supongamos que L es la ubicación (preferiblemente el registro) donde se guardará la salida de y OP z:

  • Llame a la función getReg, para decidir la ubicación de L.

  • Determine la ubicación actual (registro o memoria) de y consultando el Descriptor de dirección de y. Siy actualmente no está registrado L, luego genere la siguiente instrucción para copiar el valor de y a L:

    MOV y ', L

    dónde y’ representa el valor copiado de y.

  • Determine la ubicación actual de z utilizando el mismo método utilizado en el paso 2 para y y genera la siguiente instrucción:

    OP z ', L

    dónde z’ representa el valor copiado de z.

  • Ahora L contiene el valor de y OP z, que está destinado a ser asignado a x. Entonces, si L es un registro, actualice su descriptor para indicar que contiene el valor dex. Actualiza el descriptor dex para indicar que está almacenado en la ubicación L.

  • Si yyz no tienen más uso, se pueden devolver al sistema.

Otras construcciones de código como bucles y declaraciones condicionales se transforman en lenguaje ensamblador en forma de ensamblaje general.