Compilador Diseño - Generación de Código

Gráfico dirigidos acíclicos

Directed Acyclic Graph (DAG) es una herramienta que representa la estructura de bloques de base, ayuda a que el flujo de valores que fluye entre los bloques básicos, optimización y ofrece también. DAG proporciona fácil transformación en bloques básicos. DAG se puede entender aquí:

Nodos Hoja representar identificadores, nombres o constantes.
Los nodos interiores representan los operadores.
También los nodos interiores representan los resultados de las expresiones o los identificadores/nombre donde los valores se va a almacenar o asignado.

Ejemplo:

t₀ = a + b
t₁ = t₀ + c
d = t₀ + t₁

[t₀ = a + b]

[t₁ = t₀ + c]

[d = t₀ + t₁]

Optimización Mirilla

Esta optimización técnica funciona localmente en el código fuente para transformarlo en un código optimizado. A nivel local, es decir una pequeña porción del bloque de código a mano. Estos métodos se pueden aplicar en los códigos intermedios, así como de los códigos. Una serie de declaraciones se analiza y se verifica si las siguientes posibles para la optimización:

Eliminación instrucciones redundantes

A nivel de código fuente, el siguiente puede ser hecho por el usuario:

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;
   }

En la compilación, el compilador busca instrucciones redundantes en la naturaleza. Cargar y almacenar múltiples de instrucciones puede llevar el mismo significado aun cuando algunos de ellos se quitan. Por ejemplo:

MOV x, R0
MOV R0, R1

Podemos eliminar la primera instrucción y re-escribir la frase como:

MOV x, R1

Código inalcanzable

Código inalcanzable es una parte del código del programa que nunca se accede por construcciones de programación. Los programadores pueden tener escrito por accidente un trozo de código que nunca puede ser alcanzado.

Ejemplo:

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

En este segmento de código, la instrucción printf nunca se ejecutará el programa de control regresa antes de que pueda ejecutar, por lo tanto, printf puede ser eliminado.

Optimización de control de flujo

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

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

En el presente código, etiqueta L1 se puede retirar en el momento que pasa el control a L2. Por lo tanto, en lugar de saltar a L1 y, a continuación, en L2, el control puede llegar directamente L2, como se muestra a continuación:

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

Expresión algebraica simplificación

Hay ocasiones en que las expresiones algebraicas se puede hacer simple. Por ejemplo, la expresión a = a + 0 puede ser sustituido por una misma y la expresión a = a + 1 simplemente debe sustituirse por el INC.

Reducción Fuerza

Hay operaciones que consumen más tiempo y espacio. Su "fuerza" puede reducirse mediante su sustitución por otras operaciones que consumen menos tiempo y espacio, pero producen el mismo resultado.

Por ejemplo, x * 2 puede ser sustituido por x << 1,, en el que involucra sólo un desplazamiento a la izquierda. Aunque la salida de un * a y a ² es la misma, a²es mucho más eficaz para su aplicación.

Acceso a las instrucciones de máquina

El equipo de destino puede implementar las instrucciones más sofisticados, que pueden tener la capacidad de realizar operaciones específicas mucho más eficiente. Si el código de destino puede dar cabida a esas instrucciones directamente, que no sólo va a mejorar la calidad del código, sino que también produzcan resultados más eficientes.

Generador de código

Un generador de código se espera que tenga una comprensión de la máquina de destino entorno de ejecución y su conjunto de instrucciones. El generador de código debe tomar las siguientes cosas en cuenta para generar el código:

Idioma de destino: el generador de código ha de ser consciente de la naturaleza del idioma de destino para que el código se ha transformado. Que el lenguaje puede facilitar algunas de las instrucciones específicas para ayudar a el compilador genera el código en una forma más cómoda. El equipo de destino puede tener procesador RISC o CISC arquitectura.
Tipo de infrarrojos: representación intermedia tiene diversas formas. Puede ser en Abstract Syntax Tree (AST) estructura, Notación Polaca Inversa, o 3-código de dirección.
Selección de la instrucción: el generador de código tiene representación intermedia como entrada y convierte (mapas) en la máquina de destino. Una representación puede tener muchas formas (instrucciones) para convertir, por lo que se convierte en la responsabilidad del generador de código para elegir sabiamente las instrucciones adecuadas.
Asignación de registros: un programa tiene un número de valores que se mantiene durante la ejecución. La arquitectura de la máquina de destino no puede permitir que todos los valores que se guardan en la memoria de la CPU o de los registros. Generador de código decide qué valores para mantener en los registros. Asimismo, se decide los registros con el fin de ser utilizado para mantener estos valores.
Orden de las instrucciones: Por último, el generador de código determina el orden en que las instrucciones se ejecutan. Crea listas de instrucciones que se van a ejecutar.

Descriptores

El generador de código de seguimiento tanto de las registra (por disponibilidad) y direcciones (ubicación de valores) al mismo tiempo que genera el código. En ambos casos, los dos siguientes se utilizan descriptores:

Registro: registro descriptor descriptor se utiliza para informar al generador de código sobre la disponibilidad de registros. Descriptor Registro realiza un seguimiento de los valores almacenados en cada registro. Cada vez que un nuevo registro es necesario durante la generación de código, este descriptor es consultado para registrar disponibilidad.
Descriptor de las direcciones: Los valores de los nombres (identificadores) utilizados en el programa pueden estar almacenados en distintos lugares al mismo tiempo que en su ejecución. Descriptores Dirección se utilizan para mantener un registro de ubicaciones de memoria donde los valores de los identificadores se almacenan. Estas ubicaciones pueden incluir registros de la CPU, montones, pilas, memoria, o una combinación de los lugares antes mencionados.

Generador de código mantiene tanto el descriptor actualizado en tiempo real. Para una declaración de carga, LD R1, x, el generador de código:

updates the Register Descriptor R1 that has value of x and
updates the Address Descriptor (x) to show that one instance of x is in R1.

Generación de código

Bloques Básicos forman parte de una secuencia de tres direcciones de instrucciones. Generador de código tiene esta secuencia de instrucciones como entrada.

Nota: Si el valor de un nombre se encuentra en más de un lugar (registro, memoria caché, o la memoria), el valor del registro será preferible a la caché y la memoria principal. Del mismo modo la memoria caché se prefiere en lugar de la memoria principal. Memoria principal es apenas ninguna preferencia.

getreg: generador de código utiliza getreg función para determinar el estado de registros disponibles y la ubicación de nombre valores. getreg funciona de la siguiente manera:

Si la variable Y ya está en el registro R, se utiliza el registro.
Si algún registro R está disponible, se utiliza el registro.
Si tanto las opciones anteriores no son posibles, elige un registro que requiere un mínimo número de cargar y almacenar instrucciones.

Para una instrucción x = y OP z, el generador de código puede realizar las siguientes acciones. Supongamos que L es el lugar (preferiblemente registro) donde la producción de y OP z va a ser guardado:

Llamar a la función getreg, a decidir la ubicación de L.
Determinar la ubicación actual (registro o memoria) de y mediante la consulta de los Descriptor de Direcciones de y. SiY no está actualmente en registro L y, a continuación, generar las siguientes instrucciones para copiar el valor de y a L:

MOV y’, L

Donde y’ representa la copia valor de y.
Determinar la ubicación actual de z con el mismo método utilizado en el paso 2 para el año y generar la siguiente instrucción:

OP z’, L

Donde z' representa la copia valor de z.
Ahora L contiene el valor de y OP z, que se destina a ser asignado a x. Por lo tanto, si L es un registro, actualizar su descriptor para indicar que contiene el valor de x. Actualizar el descriptor de x para indicar que es almacenado en la localidad L.
Si y y z no tiene más uso, que puede ser dada al sistema.

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

Previous Page Print Page