Tipos de Optimización

Tarea 8_López

Tipos de optimización:

Optimizaciones Globales
Optimizaciones de Ciclo
Optimización de Mirilla
Optimizaciones Locales

•  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.

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.

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.)

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.

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.

Funciones y estructuas

Tarea 7__López

FUNCIONES Y ESTRUCTURAS

La generación de código para las funciones es la parte mas complicada porque depende de la maquina objeto y de la organización del entorno de ejecución. La traducción de funciones implica dos etapas:

·        La definición de la función. Una definición de función crea un nombre, parámetros y código del cuerpo de la función pero no se ejecuta la función en ese punto.

·        La llamada a la función desde una parte del programa (trataremos a los procedimientos como funciones que no de vuelven valores). Una llamada crea los valores actuales para los parámetros y realiza un salto al código de entrada de la función que se ejecuta y retorna al punto de la llamada.

Supongamos que el sub árbol sintáctico correspondiente a una función tiene como raíz un nodo de tipo n_ call, llamada a función, con una serie de hijos que corresponden a los argumentos, que en general, serán expresiones E1; : : : ;En a evaluar para obtener el valor actual de los n-argumentos.

A continuación se incluye una implantación para generar el código de 3-direcciones correspondiente a la llamada de la función en primer lugar. Posteriormente analizaremos el caso de la definición de la función. Supondremos que se han comprobado previamente las condiciones semánticas de la llamada (número y tipo de argumentos).

Ejemplo de llamada a la función

La llamada a una función de dos argumentos genera el siguiente código intermedio:

Se hace uso de una pila en donde se apilan los valores actuales de los parámetros de la función para después, como veremos en  Siguiente apartado, en la implantación del cuerpo de la función, 

Nota: Respecto a la dirección de la llamada a la función (índice de la instrucción del código de entrada a la función), se podrá conocer en el caso de que el código para la función ya se hubiera generado antes de la llamada (por ejemplo, se podrá haber almacenado en la entrada de la tabla de símbolos correspondiente a esa función en un campo definido para ese propósito).

En el caso de que aun no se haya generado el código para la dedición de la función tendremos que hacer un relleno de retroceso en todas las llamadas a esa función. Una forma será para cada función almacenar los índices de las instrucciones donde se hace una llamada dicha función (por ejemplo, en un vector de índices) y Una vez definida la función que ya se conoce la dirección de entrada recorremos el vector de índices y rellenamos con la dirección adecuada en todas las proposiciones de llamadas a esa función.

Notaciones

Tarea 6__López

Importancia de un compilador

Tarea 5__López

La importancia de los compiladores radica en que sin estos programas no existiría ninguna aplicación informática ya que son la base de la programación en cualquier plataforma.

FASES DE UN COMPILADOR

Retrospectiva al momento de programar

Tarea 4__López

Retrospectiva de mis errores al momento de programar

         Si he de sincerarme conmigo misma,… --¡si me dieran el código de un programa donde yo tuviera que identificar su estructura y cada una de sus partes o que me dijeran tal programa necesito?--- fallaría al momento de pretender hacerlo ya que para poder hacer “uno” necesito de estar consultando un manual, el hecho de haber analizado el programa par/impar de la tarea número 3 me ha ayudado a conocer bien como esta diseñada  la sintaxis de dicho programa, conociendo la mayoría de las palabras reservadas que usa java, las bibliotecas o paquetes que incluyen clases, las sentencias o instrucciones, las expresiones, los operandos y operadores, las variables, los bloques etc.

        La mayoría de las veces la  información que se necesita es bajada de internet; para el programa requerido solo  cambio la instrucción y algunos otros detalles que tiene de mas… o de menos el programa. Pero una estructura completa en si de un determinado programa necesito de un ejemplo que se le parezca  a lo que busco para poder guiarme y hacerlo.

      Al momento de estar utilizando el IDE (JCreator Pro) si se me pasan algunos detalles en lo que es la sintaxis por ejemplo la doble comilla, paréntesis, el punto, las variables etc. Una observación importante es cuando  --la clase que importo la tecleo completa-- no se compila tiene que ser seleccionada de la lista de clases que hay al desglosarse el paquete o biblioteca. Por muy sencillo que sea el programa si tengo muchas fallas y para lograr llegar al término del mismo si me tardo bastante tiempo. Pero si me gusta programar, mi falla esta en que casi no practico.

Programa sencillo (su tabla de símbolos y árbol sintáctico)

PROGRAMA ParImpar

Tarea 3__López

TABLA DE SÍMBOLOS

Palabras reservadas	import:  ayuda al compilador a localizar una clase(JOptionPane) que se utiliza en el programa. public. string, int, doublé, if, else, static class:  introduce  una declaración de clase, que debe de ir seguida de inmediato por el nombre de la clase void: indica que este método no devolverá ningún tipo de información
Identificadores	Un identificador: es una serie de caracteres que pueden ser letras, dígitos, guiones bajos (_) y signos de modena($), que no comience con un digito ni tenga espacios. Un identificador es el nombre de una clase  el cual comienza con una letra mayúscula y la primera letra de cada palabra también Main: indica que éste es un bloque de construcción del programa, al cual se le llama método
Expresiones	Una expresión es todo aquello que se puede poner a la derecha del operador asignación = La expresión numx=(num%2]realiza una operación de división
Variables	El tipo de variable determina los valores que puede almacenar y las operaciones que se pueden hacer con ellas. Ejemplo: String op; variable de tipo String Int num; variable de tipo entero Doublé numx; variable de número parte entera y parte decimal
Literales de cadena (String)	Una cadena es una combinación de caracteres; permiten combinar, probar y modificar cadenas. Se representan por una serie de caracteres entre comillas dobles. Ejemplo: (“determina si un número  es par/impar”); (“digite un número”); “Hola bienvenido este “+num+” es par”); “Hola que tal este “+nume*” es impar);
System.out.println	Muestra o imprime una línea de texto en la ventana de comandos y lo que tiene adentro del paréntesis en al argumento pare el método.
Sentencias if-else If (condición)         Sentencia 1 Else          Sentencia 2	La sentencia if, permite en un programa tomar la decisión sobre la ejecución de una acción mediante la evaluación de una expresión lógica o booleana. Ofreciendo  dos alternativas basadas en la comprobación de la condición utilizando también la palabra reservada else  para separar las sentencias utilizadas para ejecutar cada alternativa.
Cuadros de dialogo de la clase JOptionPane	showInputDialog: cuadro de dialogo entrada de datos. showMessageDialog; cuadro de dialogo mensaje de salida.
Bibliotecas o paquetes	Javax.swing. Java.io.*;
public static void main(String[] args)	Es el punto de inicio de toda aplicación en java. Los paréntesis después del identificador main indican que este en bloque de construcción del programa, al cual se le llama método.

Árbol sintáctico

La operación del programa

num%2==0

operadores: %, ==

operandos: num, 2, 0

Las propiedades de un árbol de expresión son las sig.

         ·        Cada hoja es un operando

• 
  
•      El nodo raíz y los nodos internos son operadores
• 
  
• ·        Los subárboles son sub-expresiones en las que el nodo raíz es un operador

Creación de la tabla de simbolos

Tarea 2_López

Tabla de símbolos

Su creación, procedimiento, pasos e instrucciones.

CREACIÓN DE LA TABLA DE SIMBOLOS

            La tabla de símbolos es una estructura de datos muy importante en CASI todo el proceso de compilación. En ella se guarda durante las primeras fases de compilación los nombres de los identificadores (símbolos) usados en el programa fuente, además de los atributos de cada uno de estos identificadores. Estos identificadores y símbolos junto con sus atributos serán usados posteriormente para realizar funciones como el chequeo de tipos, la asignación de memoria, generación de código objeto etc.

        Un compilador necesita guardar y usar la información de los objetos que se va encontrando en el texto fuente, como variables, etiquetas, declaraciones de tipos, etc.

 Esta información se almacena en una estructura de datos interna conocida como tabla de símbolos.

TABLA DE SIMBOLOS

Contenido de la tabla de símbolos.

Identificadores

Tipos de datos

Palabras reservadas

Sentencias o instrucciones

Comentarios

Expresiones

Operaciones

Esencialmente la información que aparece en la tabla de símbolos es de dos tipos:

·          El propio símbolo, y

·         Los atributos necesarios para definir el símbolo a nivel semántico y de generación de código.

Operaciones sobre la tabla de símbolos.

·         INSERTAR

·         CONSULTAR

·         MODIFICAR (añadir atributos nuevos)

El CUANDO y el CÓMO se usan estas operaciones dependen del tipo de lenguaje:

Lenguajes con DECLARACIONES DE VARIABLES:

·         Explícitas:

ü  Declaraciones: sólo INSERTAR.

ü  Referencia: sólo CONSULTAR.

·         Implícitas:

ü  CONSULTAR si no está ya incluida.

ü  INSERTAR, en caso contrario.

ü  Lenguajes con estructura de BLOQUE: CREAR SUBTABLAS

•      Operadores relacionales: <, <=, >, >=, == y !=.

•      Operadores de operaciones con bits:

<<                   Corrimiento a la izquierda.

>>                   Corrimiento a la derecha.

&                                And

|                                 Or

^                                 Xor

•      Operadores Lógicos:

&&                               And

||                                Or

!                                  Not

OPERADORES DE ASIGNACIÓN

=                     Asignación.

*=        Asignación de producto.

/=        Asignación de cociente.

%=       Asignación de residuo.

+=        Asignación de suma.

-=        Asignación de diferencia.

<<=      Asignación de corrimiento a la izquierda.

>>=      Asignación de corrimiento a la derecha.

&=       Asignación de And de bits.

^=        Asignación de Xor de bits.

|=         Asignación de Or de bits.

OPERADORES DE PERTENENCIA A CLASES

::                     Resolución de área de visualización de clases.

. y *               Apuntadores de referencia de un apuntador a un miembro de una clase.

-> y *            Apuntadores de referencia a apuntadores de un miembro de una clase.

Etc. Etc. Etc.