Generación de código intermedio.

2.1 Notaciones 

• Las notaciones sirven de base para expresar sentencias bien definidas. 

• El uso más extendido de las notaciones sirve para expresar operaciones aritméticas. 

• Las expresiones aritméticas se pueden expresar de tres formas distintas: infija, prefija y postfija. Notaciones 

• La diversidad de notaciones corresponde en que para algunos casos es más sencillo un tipo de notación. 

• Las notaciones también dependen de cómo se recorrerá el árbol sintáctico, el cual puede ser en inorden, preorden o postorden; teniendo una relación de uno a uno con la notación de los operadores. 

2.1.1 Prefija 

• La notación prefija pone el operador primero que los dos operando, por lo que la expresión anterior queda: +ab-5. Esto se representa con una estructura del tipo FIFO (First In First Out) o cola. 

• Las estructuras FIFO son ampliamente utilizadas, pero tienen problemas con el anidamiento aritmético. 

2.1.2 Infija 

• La notación infija es la más utilizada por los humanos porque es la más comprensible ya que ponen el operador entre los dos operando. Por ejemplo, a+b-5. 

• No existe una estructura simple para representar este tipo de notación en la computadora por esta razón se utilizan otras notaciones. Venustiano Carranza, Chiapas, México. 19 de octubre de 2021 

2.2.3 Postfija 

• La notación postfija pone el operador al final de los dos operando, por lo que la expresión queda: ab+5- 

• La notación posftfija utiliza una estructura del tipo LIFO (Last In First Out) pila, la cual es la más utilizada para la implementación.

2.2 Representaciones de código Intermedio. 

El código intermedio se genera para una máquina virtual. Estas máquinas se definen con dos objetivos: Ser lo suficientemente simples como para poder generar código para ellas de manera sencilla, pero con la suficiente riqueza para poder expresar las construcciones del lenguaje fuente.

2.2.1 Notación Polaca. 

La notación polaca, también conocida como notación de prefijo o notación prefija, es una forma de notación para la lógica, la aritmética, el álgebra y la computación. Su característica distintiva es que coloca los operadores a la izquierda de sus operandos. Si la aridad de los operadores es fija, el resultado es una sintaxis que carece de paréntesis u otros signos de agrupación, y todavía puede ser analizada sin ambigüedad. El lógico polaco Jan Łukasiewicz inventó esta notación alrededor de 1920 para simplificar la lógica proposicional.

2.2.2 Código P. 

El código P hace referencia a máquinas que utilizan o se auxilian de pilas para generar código objeto.

En muchos caso la P se asociado a código portable el cual garantiza que el código compilado en una máquina se pueda ejecutar en otras.

Para garantizar la portabilidad del código se necesita que el lenguaje este estandarizado por algún instituto y que dicho código no tenga extensiones particulares. También se recomienda la no utilización de características especiales exclusivas de alguna arquitectura de computadoras en particular.

2.2.3 Triplos. 

Las proposiciones de tres direcciones se parecen mucho al ensamblador, el cual es un lenguaje intermedio más entendible para la máquina.

• Las estructuras de control (if, switch, while, do-while, for) son realmente etiquetas goto disfrazadas.

2.2.4 Cuádruplos. 

Es una estructura tipo registro con cuatros campos que se llaman: op, arg1, arg2 y resultado. OP tiene un código intermedio.

Los operadores unarios como x:=-y no utilizan arg2. Generalmente arg1, arg2 y resultado son valores de tipo puntero y apuntan a una entrada en la tabla de símbolos.

Constituida por 4 elementos: un código de operación, dos operando de entrada y otro de salida para almacenar el resultado.

2.3 Esquema de generación. 

Los esquemas de generación son las estrategias o acciones que se deberán realizarse y tomarse en cuenta en el momento de generar código intermedio. Los esquemas de generación dependen de cada lenguaje. Tomaremos algunos esquemas de generación del lenguaje C.

2.3.1 Variables y constantes. 

Las declaraciones de variables y constantes deben separarse de tal manera que queden las expresiones una por una de manera simple. Por ejemplo int a,b,c; se descompone a int a; int b; intc; respectivamente.

2.3.2 Expresiones. 

Para generar expresiones estas deben representarse de manera más simple y más literal para que su conversión sea más rápida. Por ejemplo la traducción de operaciones aritméticas debe especificarse una por una, de tal forma que una expresión sea lo más mínimo posible.

2.3.3 Instrucción de asignación. 

Las operaciones de asignación deben quedar expresadas por una expresión sencilla, si está es compleja se debe reducir hasta quedar un operador sencillo. Por ejemplo: x = a+b/5; debe quedar de la forma y = b/5; z = a+y; x=z. Deben quedar Expresadas por una expresión sencilla.

2.3.4 Instrucciones de control. 

Permiten variar o alterar la secuencia normal de ejecución de un programa.

Tipos:

·         Instrucciones condicionales o alternativas-

·         Instrucciones de salto.

·         Instrucciones repetitivas.

2.3.5 Funciones. 

Las funciones pueden reducir a en línea, lo que se hace que expandir el código original de la función.

Las funciones se descomponen simplificando los parámetros de manera individual al igual que el valor de retorno. 

Entendemos que es el uso de la lengua que hace un hablante. En simples palabras, las funciones del lenguaje son los diferentes objetivos, propósitos y servicio que se le da al lenguaje al comunicarse, dándose una función del lenguaje por cada factor que tiene éste, en donde la función que prevalece es el factor en donde más se pone énfasis al comunicarse.

2.3.6 Estructuras.

Estructura y fases de un compilador (2) Análisis lineal También conocido como: análisis léxico o exploración. En la proposición de asignación: posicion = inicial + velocidad * 60 Se identifican los siguientes componentes léxicos Identificador Símbolo de asignación (=) Identificador (inicial) Signo de suma (+) Identificador Signo de multiplicación (*) Número (60)

Estructura y fases de un compilador (3) Análisis jerárquico También llamado análisis sintáctico. Implica agrupar los componentes léxicos en frases gramaticales que el compilador utiliza para sintetizar la salida. Por lo general, las frases gramaticales se representan mediante un árbol de análisis sintáctico.

UNIDAD 3 Optimizacion

3.1 Tipos de Optimización

 La optimización es un proceso que tiene a minimizar o maximizar alguna variable de rendimiento, generalmente tiempo, espacio, procesador, etc.

La optimización se realiza reestructurando el código de tal forma que el nuevo código generado tenga mayores beneficios.

 La optimización va a depender del lenguaje de programación y es directamente proporcional al tiempo de compilación; es decir, entre más optimización mayor tiempo de compilación.

•Las optimizaciones pueden realizarse de diferentes formas. Las optimizaciones se realizan en base al alcance ofrecido por el compilador de programación y es directamente proporcional al tiempo de compilación; es decir, entre más optimización mayor tiempo de compilación.

•Como el tiempo de optimización es gran consumidor de tiempo (dado que tiene que recorrer todo el árbol de posibles soluciones para el proceso de optimización) la optimización se deja hasta la fase de prueba final.

•Algunos editores ofrecen una versión de depuración y otra de entrega o final.

•La optimización es un proceso que tiene a minimizar o maximizar alguna variable de rendimiento, generalmente tiempo, espacio, procesador, etc.

•Desafortunamente no existen optimizador que hagan un programa más rápido y que ocupe menor espacio.

•La optimización se realiza reestructurando el código de tal forma que el nuevo código generado tenga mayores beneficios. La mayoría de los compiladores tienen una optimización baja, se necesita de compiladores especiales para realmente optimizar el código.

 3.1.1  Optimización Local

• Las optimizaciones locales se realizan sobre el bloque básico
• Optimizaciones locales
– Folding
– Propagación de constantes
– Reducción de potencia
– Reducción de subexpresiones comunes
Bloque Básico
• Un bloque básico es un fragmento de código que tiene una única entrada y salida, y cuyas instrucciones se ejecutan secuencialmente. Implicaciones:
– Si se ejecuta una instrucción del bloque se ejecutan todas en un orden conocido en tiempo de compilación.
• La idea del bloque básico es encontrar partes del programa cuyo análisis necesario para la optimización sea lo más simple posible.


Ensamblamiento (Folding)
• El ensamblamiento es remplazar las expresiones por su resultado cuando se pueden evaluar en tiempo de compilación (resultado constante).
– Ejemplo: A=2+3+A+C -> A=5+A+C
• Estas optimizaciones permiten que el programador utilice cálculos entre constantes representados explícitamente sin introducir ineficiencias.
Implementación del Folding
• Implementación del floding durante la generación de código realizada conjuntamente con el análisis sintáctico.
– Se añade el atributo de constante temporal a los símbolos no terminales y a las variables de la tabla de símbolos.
– Se añade el procesamiento de las constantes a las reglas de análisis de expresiones.
– Optimiza: 2+3+b -> 5+b
• Hay una suma de constantes (2+3)+b
– No optimiza: 2+b+3 -> 2+b+3
• No hay una suma de constantes (2+b)+3
Implementación del Folding
• Implementación posterior a la generación de código
– Buscar partes del árbol donde se puede aplicar la propiedad conmutativa:
• Sumas/restas: como la resta no es conmutativa se transforma en sumas: a+b-c+d -> a+b+(-c)+d
• Productos/divisiones: como la división no es conmutativa se transforma en productos: a*b/c*e -> a*b*(1/c)*e
– Buscar las constantes y operarlas
– Reconstruir el árbol.

Propagación de constantes
• Desde que se asigna a una variable un valor constante hasta la siguiente asignación, se considera a la variable equivalente a la constante.
• Ejemplo: Propagación Ensamblamiento
PI=3.14 -> PI=3.14 -> PI=3.14
G2R=PI/180 -> G2R=3.14/180 -> G2R=0.017
PI y G2R se consideran constantes hasta la próxima asignación.
• Estas optimizaciones permiten que el programador utilice variables como constantes sin introducir ineficiencias. Por ejemplo en C no hay constantes y será lo mismo utilizar
– Int a=10;
– #define a 10
Con la ventaja que la variable puede ser local.
• Actualmente en C se puede definir const int a=10;
implementación de la Propagación de Constantes
• Separar el árbol en bloques básicos
– Cada bloque básico será una lista de expresiones y asignaciones
• Para cada bloque básico
– Inicializar el conjunto de definiciones a conjunto vacío.
• Definición: (variable,constante)
– Procesar secuencialmente la lista de expresiones y asignaciones
– Para expresión y asignación
• Sustituir las apariciones de las variables que se encuentran en el conjunto de definiciones por sus constantes asociadas.
– Para asignaciones
• Eliminar del conjunto de definiciones la definición de la variable asignada
• Añadir la definición de la variable asignada si se le asigna una constante.

Ejecuci on en tiempo de compilaci on
Precalcular expresiones constantes (con constantes o variables cuyo valor no cambia)
i = 2 + 3 ! i = 5
j = 4
f = j + 2.5
!
j = 4
f = 6.5
2. Reutilizaci on de expresiones comunes
a = b + c
d = a - d
e = b + c
f = a - d
!
a = b + c
d = a - d
e = a
f = a - d
3. Propagaci on de copias
Ante instrucciones f = a, sustituir todos los usos de f por a
a = 3 + i
f = a
b = f + c
d = a + m
m = f + d
!
a = 3 + i
b = a + c
d = a + m
m = a + d

Reducci on de potencia

Reemplazar una operaci on por otra equivalente menos costosa

x2 ! x * x

2*x ! x + x (suma); x<<1 (despl. izq.)

4*x, 8*x,... ! x<<2, x<<3,...

x / 2 ! x>>2

Bucles

• Los ciclos son una de las partes más esenciales en el rendimiento de un programa dado que realizan acciones repetitivas, y si dichas acciones están mal realizadas, el problema se hace N veces más grandes.

3.1.2 Ciclos

• El problema de la optimización en ciclos y en general radica es que muy difícil saber el uso exacto de algunas instrucciones. Así que no todo código de proceso puede ser optimizado.

• Otros uso de la optimización pueden ser el mejoramiento de consultas en SQL o en aplicaciones remotas (sockets, E/S, etc.)

3.1.3 Globales 

• La optimización global se da con respecto a todo el código.

• Este tipo de optimización es más lenta pero mejora el desempeño general de todo programa.

• Las optimizaciones globales pueden depender de la arquitectura de la máquina.

Optimización global

• En algunos casos es mejor mantener variables globales para agilizar los procesos (el proceso de declarar variables y eliminarlas toma su tiempo) pero consume más memoria.

• Algunas optimizaciones incluyen utilizar como variables registros del CPU, utilizar         instrucción  es  enensamblador.

3.1.4 De mirilla

• La optimización de mirilla trata de estructurar de manera eficiente el flujo del programa, sobre todo en instrucciones de bifurcación como son las decisiones, ciclos y saltos de rutinas.

• La idea es tener los saltos lo más cerca de as llamadas, siendo el salto lo más pequeño posible.

3.2 Cotos

Los costos son el factor más importante a tomar en cuenta a la hora de optimizar ya que en ocasiones la mejora obtenida puede verse no reflejada en el programa final pero si ser perjudicial para el equipo de desarrollo. La optimización de una pequeña mejora tal vez tenga una pequeña ganancia en tiempo o en espacio pero sale muy costosa en tiempo en generarla. Pero en cambio si esa optimización se hace por ejemplo en un ciclo, la mejora obtenida puede ser N veces mayor por lo cual el costo se minimiza y es benéfico la mejora.

3.2.1 Costos de Ejecución. (memoria, registros, pilas)

Los costos de ejecución son aquellos que vienen implícitos al ejecutar el programa. En algunos programas se tiene un mínimo para ejecutar el programa, por lo que el espacio y la velocidad de los microprocesadores son elementos que se deben optimizar para tener un mercado potencial más amplio. Las aplicaciones multimedia como los videojuegos tienen un costo de ejecución alto por lo cual la optimización de su desempeño es crítico, la gran mayoría de las veces requieren de procesadores rápidos (e.g. tarjetas de video) o de mucha memoria. Otro tipo de aplicaciones que deben optimizarse son las aplicaciones para dispositivos móviles. Los dispositivos móviles tienen recursos más limitados que un dispositivo de cómputo convencional razón por la cual, el mejor uso de memoria y otros recursos de hardware tiene mayor rendimiento. En algunos casos es preferible tener la lógica del negocio más fuerte en otros dispositivos y hacer uso de arquitecturas descentralizadas como cliente/servidor o P2P.

3.2.2 Criterios para mejorar el código

 La mejor manera de optimizar el código es hacer ver a los programadores que optimicen su código desde el inicio, el problema radica en que el costo podría ser muy grande ya que tendría que codificar más y/o hacer su código más legible. Los criterios de optimización siempre están definidos por el compilador. Muchos de estos criterios pueden modificarse con directivas del compilador desde el código o de manera externa. Este proceso lo realizan algunas herramientas del sistema como los ofuscadores para código móvil y código para dispositivos móviles.

3.2.3 Herramientas para el análisis del flujo de datos

Existen algunas herramientas que permiten el análisis de los flujos de datos, entre ellas tenemos los depuradores y desambladores. La optimización al igual que la programación es un arte y no se ha podido sistematizar del todo.

Elaborado por Miguel Perez