Tema Optimización de Código



Descargar 40,51 Kb.
Fecha de conversión10.01.2017
Tamaño40,51 Kb.

Tema 3. Optimización de Código

  • Lecciones 5,6,7,8 y 9

Generación de Código y Optimización

  • Generación de código
  • Optimización
    • Se realiza después de la generación de código de todo el programa o de un elemento ejecutable del programa (función, procedimiento, etc).
    • “Dependiente del contexto”
  • Programa fuente
  • Analizador
  • lexicográfico,
  • sintáctico y
  • semántico
  • Generador de
  • Código
  • Optimizador
  • Programa objeto
  • Se ejecuta todo junto. Mientras se analiza se genera código

Optimización

  • Objetivo
    • Obtener código que se ejecuta más eficientemente según los criterios
      • Tiempo de ejecución (optimización temporal)
      • Espacio de memoria utilizado (optimización espacial)
  • Funcionamiento
    • Revisa el código generado a varios niveles de abstracción y realiza las optimizaciones aplicables al nivel de abstracción
      • Representaciones de código intermedio de más a menos abstractas
        • Árbol sintáctico abstracto
          • Optimizar subexpresiones redundantes, reducción de frecuencia, etc.
        • Tuplas o cuadruplas
          • Optimizar en uso de los registros o de las variables temporales
        • Ensamblador/Código máquina

Optimización

  • Funcionamiento (continuación)
    • Representaciones de código para extraer información
      • Grafos.
  • Condiciones que se han de cumplir
    • El código optimizado se ha de comportar igual que el código de partida excepto por ser más rápido o ocupar menos espacio.
    • Hay que buscar transformaciones que no modifiquen el comportamiento del código según el comportamiento definido para el lenguaje de programación. Ejemplo
      • Si no se ha definido el orden de evaluación de los operandos la siguiente optimización es válida
          • B=2*A+(A=c*d);
        • Pasar a
          • A=c*d;
          • B=A*3;

Tipos de Optimización

  • Optimización independiente de máquina
  • Optimización dependiente de máquina
    • Asignación de registros
    • Reordenación de las instrucciones
  • Optimización local
    • Reducción de potencia
    • Folding
    • Propagación de constantes
  • Optimización global
    • análisis del grafo del flujo de ejecución
  • Optimización de bucles
    • Loop unrolling
    • Reducción de frecuencia
    • Reducción de potencia

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.

Bloque Básico (ejemplos)

  • Ejemplos (separación errónea):
    • for (i=1;i<10;++i) {
    • b=b+a[i];
    • c=b*i;
    • }
    • a=3;
    • b=4;
    • goto l1;
    • c=10;
    • l1: d=3;
    • e=4;
  • Separación correcta
    • for (i=1;i<10;++i) {
    • b=b+a[i];
    • c=b*i;
    • }
    • a=3;
    • b=4;
    • goto l1;
    • c=10;
    • l1: d=3;
    • e=4;
  • BB1:
    • i=1;
  • BB2:
    • i<10;
  • BB3:
    • b=b+a[i];
    • c=b*i;
    • ++i
  • BB4:
    • a=3;
    • b=4;
    • goto l1;
  • BB5:
    • c=10;
  • BB6:
    • l1: d=3;
    • e=4;

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
  • 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 nombres para las constantes sin introducir ineficiencias.

Extensiones

  • Variables indexadas
    • Se asocian constantes a expresiones de acceso a variables indexadas. Ejemplo
      • A[i]=10
      • Se asocia 10 a A[i] aun no sabiendo el valor de i.
      • En el caso de hacer una asignación a cualquier elemento de A se deshace la asociación.
  • Usar las propiedades conmutativa y asociativa.
    • Ejemplo: aplicando la propiedad conmutativa se reduce
      • A=B+2+C+3
      • A=B+C+5

Extensiones

  • Extender la aplicación fuera del bloques básicos
    • Hay que realizar un análisis del flujo de ejecución y es complejo. Ejemplo:
      • i=0;
      • loop:
      • i=i+1
      • if (i<10) goto loop;
      • Se transforma erróneamente en
      • i=0;
      • loop:
      • i=1
      • if (1<10) goto loop;

Implementación del Folding

  • Implementación durante el análisis sintáctico/semántico o creación del árbol 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.
  • Implementación posterior
    • Buscar partes del árbol donde se puede aplicar la propiedad conmutativa
    • Buscar las constantes y operarlas
    • Reconstruir el árbol

Ejemplo de Folding

  • Expresión: 3-(5+6)+4-A*10
  • Árbol:
    • -
    • +- +
    • | +- -
    • | | +- 3
    • | | +- +
    • | | +- 5
    • | | +- 6
    • | +- 4
    • +- *
    • +- A
    • +- 10
  • Términos:
    • 3
    • -5
    • -6
    • 4
    • -(A*10)
  • Resultado: -4-(A*10)

Implementación de la Propagación de Constantes

  • Implementación posterior
    • Separar el árbol en bloques básicos
    • 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

Ejemplo de Separación en Bloques Básicos

  • Fun
  • +- []
  • +- =>
  • +- f
  • | +- x
  • | +- y
  • +- InstrComp
  • +- ;
  • +- =
  • | +- i
  • | +- 0
  • +- ;
  • +- =
  • | +- b
  • | +- 5
  • +- ;
  • +- while
  • | +- <
  • | | +- i
  • | | +- x
  • | +- InstrComp
  • | +- ;
  • | +- Print
  • | | +- *
  • | | +- i
  • | | +- b
  • | +- =
  • | +- i
  • | +- +
  • | +- i
  • | +- 1
  • +- *
  • +- x
  • +- b
  • Fun f(x,y)=>
  • {
  • i=0;
  • b=5;
  • while (i
  • print(i*b);
  • i=i+1;
  • }
  • x*b
  • }
  • print(i*b);
  • i=i+1;
  • i
  • i=0;
  • b=5;

Eliminación de subexpresiones redundantes.

  • Las subexpresiones que aparecen más de una vez se calculan una sola vez y se reutiliza el resultado.
  • Idea: Detectar las subexpresiones iguales y que las compartan diversas ramas del árbol. Problema: Hay que trabajar con un grafo acíclico.
  • Dos expresiones pueden ser equivalentes y no escribirse de la misma forma A+B es equivalente a B+A. Para comparar dos expresiones se utiliza la forma normal
      • Se ordenan los operandos: Primero las constantes, después variables ordenadas alfabéticamente, las variables indexadas y las subexpresiones. Ejemplo
        • X=C+3+A+5 -> X= 3+5+A+C
        • Y=2+A+4+C -> Y=2+4+A+C
      • divisiones y restas se ponen como sumas y productos para poder conmutar
        • A-B -> A+ (-B)
        • A/B -> A * (1/B)

Implementación

  • Primero se aplica el ensamblamiento y la propagación de constantes.
  • Después se reordena el árbol sintáctico hasta obtener la forma normal.
  • Se inicia la eliminación de las subexpresiones redundantes.
  • Hay que considerar las asignaciones que pueden convertir una subexpresion redundante en no redundante. Ejemplo:
    • Q=A+B
    • A=Q^2+2
    • C[1]=A+B+P
  • Ejemplo de eliminación de subexpresiones
      • J=2*D+3
      • D=D*2
      • J=J+D
  • A+B no es redundante por la asignación

Optimizaciones Dentro de Bucles

  • La optimización de bucles es muy importante por las mejoras en tiempo de ejecución que se obtienen
  • Estrategias de optimización dentro de bucles
    • Expansión de bucles (loop unrolling)
    • Reducción de frecuencia (frequency reduction)
    • Reducción de potencia (strength reduction)

Expansión de bucles(loop unrolling)

  • La expansión de bucles solo se puede aplicar a los bucles cuyo número de iteraciones se conoce en tiempo de compilación. Ejemplo:
    • Se puede aplicar a los bucles
      • for i=1 to 10 do …
    • No se puede aplicar a los bucles
      • for i=a to b do …
  • La expansión de un bucle puede ser muy costosa en espacio. Hay que poner un criterio heurístico para decidir si se aplica la expansión.
    • Se puede aplicar una expansión parcial en la que sigue existiendo el bucle, pero cada iteración del nuevo bucle corresponde a varias iteraciones del bucle original.
  • En un bucle expandido se ha de sustituir el índice del bucle por el valor constante correspondiente

Reducción de frecuencia. (frequency reduction)

  • La reducción de frecuencia detecta las operaciones invariantes de bucle y las calcula una única vez delante del bucle. Ejemplo:
    • for i=1 to n do c=i*sin(a);
    • sin(a) es una operación invariante del bucle que puede pasar de calcularse n veces a una con la siguiente transformación
    • tmp=sin(a);
    • for i=1 to n do c=i*tmp;
  • Sólo las operaciones que cumplen
    • Su único efecto es el cálculo del resultado
    • El resultado solo depende de los operandos.
  • se pueden considerar como operaciones invariantes de bucle.
  • Ejemplo:
    • Invariantes: +. -, *, / , sin, ln
    • No invariantes: printf, getchar, ++, random

Implementación de la Reducción de Frecuencia

  • Pasos
    • Detectar todas las variables que se modifican en el bucle.
    • Marcar todas las operaciones no invariantes
    • Aplicar la siguiente regla recursiva para detectar las operaciones invariantes
      • Una operación es invariante si sus operandos son invariantes.
    • Asociar a cada expresión invariante una variable temporal.
    • Sustituir en el bucle las operaciones invariantes por las correspondientes variables.
    • Añadir delante del bucle la asignación de la expresión invariante a su variable temporal.
  • Problema del método anterior
    • Cuando no se entra en el bucle se calculan sus operaciones invariantes. La solución es evaluar antes la condición de salida del bucle.

Reducción de potencia(strength reduction)

  • Se busca sustituir operaciones costosas por otras mas simples. Ejemplo:
    • sustituir productos por sumas.
      • a=2*a
      • a=a+a
    • Evitar la operación append (++)
      • A=length(s1 ++ s2)
      • convertirlo en
      • A=length(s1)+length(s2)
    • Sustituir productos entre variables inductivas e invariantes de bucle por sumas
      • for(i=1; i<10;++i) a[i]=3*i;
      • convertir en
      • for(i=1,j=3;i<10;++i,j+=3) a[i]=j;
  • Problemas ha resolver

Variables Inductivas

  • Una variable V es inductiva cuando la única forma en que se modifica su código es V=V+K, donde K es una invariante de bucle.
  • Se considerará la necesidad de generar una variable inductiva temporal T a partir de encontrar expresiones de la forma V*C, donde C es una invariante de bucle.
    • Se sustituirá V*C por T
    • Se inicializa T después de la inicialización de V como T=V*C (solo se ejecuta al entrar en el bucle)
    • Al final de cada iteración se añade T=T+C*K

Optimización Global

  • Grafo del flujo de ejecución
    • Antes de realizar una optimización global es necesario crear el grafo de flujo de ejecución.
    • El grafo de flujo de ejecución representa todos los caminos posibles de ejecución del programa.
    • La información contenida en el grafo es útil para
      • el programador y
      • el optimizador
  • La optimización global a partir del análisis del grafo del flujo de ejecución permite
    • Una propagación de constantes fuera del bloque básico.
    • Eliminación del código no utilizado
    • Una mejor asignación de los registros.
  • Problema: la optimización global es muy costosa en tiempo de compilación

Construcción del Grafo del Flujo de Ejecución

  • Tipos de grafo
    • Orientado a procedimiento/función
    • Grafo de llamadas
  • Ejemplo
    • int fact(int n) {
    • int r;
    • r=1;
    • i=1;
    • while (i<=n) {
    • r=r*i;
    • ++i;
    • }
    • return r;
    • }
  • r=1
  • i=1
  • while (i<=n)
  • r=r*i;
  • ++i;
  • return r;
  • bloque
  • básico
  • bloque
  • básico
  • bloque
  • básico
  • bloque
  • básico

Construcción del Grafo del Flujo de Ejecución

  • Pasos
    • Dividir el programa en bloques básicos
      • Se representa el programa en un código intermedio donde queden explícitamente representados los saltos condicionales e incondicionales.
      • Un bloque básico será cualquier trozo de código que no contenga saltos ni etiquetas en su interior (es posible tener etiquetas al inicio del bloque y saltos al final).
    • En el grafo, los vértices representan los bloques básicos y las aristas representan los saltos de un bloque básico a otro.
  • Detección de código no utilizado
    • El código no utilizado son los bloques básicos donde no llega ninguna arista.

Análisis del Grafo del Flujo de Ejecución

  • Hay que considerar como la información sobre las variables y expresiones se propaga a través del grafo.
  • Problemas resueltos durante el análisis del grafo
    • expresiones disponibles (al seguir la ejecución sigue siendo válido el resultado obtenido)
    • Alcance de las definiciones
    • variables vivas
    • expresiones muy utilizadas
  • Para la resolución de los problemas anteriores se utiliza la idea de punto entre instrucciones o bloques básicos.
  • r=1
  • i=1
  • while (i<=n)
  • Puntos

Expresiones Disponibles (Available expresions)

  • El problema de las expresiones disponibles consiste en determinar que expresiones están disponibles al inicio de cada bloque
  • Algoritmo
    • Para cada bloque básico se definen 4 conjuntos
      • AE_TOP(BB): la expresión está disponible en el punto que precede a BB
      • AE_KILL(BB): la expresión ya no será válida después de la ejecución de BB por que se ha modificado algún operando.
      • AE_GEN(BB): Se ha evaluado la expresión en BB sin que se modifiquen sus operándos.
      • AE_BOT(BB): La expresión está disponible justo después de la ejecución de BB
    • Ecuación para las expresiones disponibles
      • AE_BOT(BB)=(AE_TOP(BB)-AE_KILL(BB)) AE_GEN(BB)
      • AE_TOP(BB)= p precedente de BB AE_BOT(P)

Alcance de las Definiciones (reaching definitions)

  • El valor de una variable se define cuando se le asigna un valor.
  • Este valor definido se pierde cuando se realiza una nueva asignación.
  • El problema del alcance de las definiciones es el mismo que el problema de las expresiones disponibles, pero en el caso de las variables.
  • Ecuaciones:
    • RD_BOT(BB)=(RD_TOP(BB)-RD_KILL(BB)) 
    • RD_GEN(BB)
    • RD_TOP(BB)= p precedente de BB RD_BOT(P)

Variables Vivas (live variables)

  • Una variable esta viva en un punto p cuando su valor es requerido para un camino de ejecución que pasa por p.
  • Un camino requiere el valor de una variable cuando hay una asignación de la variable al principio y una lectura al final.
  • Uso delimitar exactamente en que partes del código es necesaria una variable.
  • Ecuaciones
    • LV_TOP(BB)=(LV_BOT(BB)-LV_DEF(BB)) 
    • LV_USE(BB)
    • LV_BOT(BB)= s sucesor de BB LV_TOP(S)

Expresiones muy Utilizadas (Very Busy Expression)

  • Una expresión es muy utiliza en un punto p cuando el valor de la expresión se requiere antes que el valor de cualquiera de sus términos a lo largo de cualquier camino que empieza en p.
  • Ecuaciones
    • VBE_TOP(BB)=(VBE_BOT(BB)-BVE_DEF(BB)) BVE_USE(BB)
    • VBE_BOT(BB)= s sucesor de BB VBE_TOP(S)

Algoritmos de Análisis del Flujo de Ejecución

  • Tipos
    • Algoritmos basados en la estructura de los bucles
      • Son rápidos
      • Hay que reducir el grafo a bucles sin saltos que entren en medio del bucle. Los programas estructurados son reducibles.
    • Algoritmos iterativos
      • Son lentos pero genéricos
      • Tipos:
        • lista de trabajos
        • round robin

Aplicaciones a la Optimización de Programas

  • expresiones disponibles (al seguir la ejecución sigue siendo válido el resultado obtenido)
    • Eliminar expresiones redundantes
  • Alcance de las definiciones
    • Reutilizar las copias en registro de los valores de las variables.
    • Propagación de constantes
    • Reducción de frecuencia
  • variables vivas
  • expresiones muy utilizadas
    • optimizar la asignación de registros

Ejemplo: Optimización Global

  • IF A(1)<0 & J>0 THEN L:=1 ELSE L:=2;
  • J:=2;
  • FOR K:=1 STEP 2 UNTIL J DO
  • BEGIN
  • A(K+1):=A(K)+A(K+1);
  • I:=J;
  • L:=K*I;
  • END
  • A(1)<0
  • J>0
  • L:=2
  • L:=1
  • J:=2
  • K:=1
  • A(K+1):=A(K)+A(K+1);
  • I:=J;
  • L:=K*I
  • K:=K+2
  • K

Ejemplo de Optimización Global Variables Vivas

  • A(1)<0
  • J>0
  • L:=2
  • L:=1
  • J:=2
  • K:=1
  • A(K+1):=A(K)+A(K+1);
  • I:=J;
  • L:=K*I
  • K:=K+2
  • K
  • {J,K}
  • {J,K}
  • {J,K}
  • {A(1),J}
  • {J}

Ejemplo de Optimización Global Eliminación de Variables Innecesarias

  • A(1)<0
  • J>0
  • L:=2
  • L:=1
  • J:=2
  • K:=1
  • A(K+1):=A(K)+A(K+1);
  • I:=J;
  • L:=K*I
  • K:=K+2
  • K
  • {J,K}
  • {J,K}
  • {J,K}
  • {A(1),J}
  • {J}
  • Se puede eliminar L e I
  • Las A(K),A(K+1) no se eliminan pues no se han
  • podido considerar en el cálculo de variables vivas

Ejemplo de Optimización Global Propagación de Constantes

  • A(1)<0
  • J>0
  • J:=2
  • K:=1
  • A(K+1):=A(K)+A(K+1);
  • K:=K+2
  • K<2
  • {A(1),J}
  • {J:=2}
  • Eliminar J>0 por no
  • utilizarse y saltar
  • al mismo bloque básico
  • Eliminar A(1)<0 después
  • de eliminar J>0
  • Se puede expandir el bucle

Ejemplo de Optimización Global Expandir el Bucle

  • J:=2
  • K:=1
  • A(1+1):=A(1)+A(1+1);
  • A(2+1):=A(2)+A(2+1);
  • A(2):=A(1)+A(2);
  • A(3):=A(2)+A(3);
  • Eliminar J y k por que no se utilizan y
  • realizar los cálculos entre constantes

Optimización Dependiente de Máquina

  • La optimización dependiente de máquina pretende aprovechar las características específicas de la máquina para acelerar la ejecución del programa
    • Considerar los ciclos de reloj que gasta cada instrucción de código máquina.
      • Utilizar desplazamientos de bits para multiplicar y dividir.
      • Para poner un registro a cero utilizar la instrucción XOR reg,reg que accede menos a memoria
      • Utilizar saltos relativos de 8 o 16 bits para acceder menos a memoria.
    • Alinear instrucciones/Datos para que se acceda en un único ciclo de memoria.
    • Combinar operaciones en una misma instrucción.
      • Utilizar el direccionamiento con pre- y post-incremento.

Optimizaciones Dependientes de Máquina

    • Sacar provecho de todas las formas de direccionamiento del procesador.
      • Utilizar acceso indexado para los arrays.
    • Reordenar las instrucciones para paralelizar su ejecución.
      • Un Pentium es capaz de ejecutar en paralelo un cálculo con enteros con otro de flotantes.
      • Evitar que la siguiente instrucción dependa del resultado de la anterior para que no se produzca un fallo en la pipe-line. Incluso puede ser interesante añadir NOPs para evitar los fallos de pipe-line.
    • Optimizar el uso de los registros del procesador.
      • Es especialmente importante en los procesadores RISC.
    • Considerar el tamaño de la cache del procesador.

Asignación de Registros

  • Máquinas con un solo registro (acumulador)
    • Código máquina típico. Todas las operaciones trabajan sobre el acumulador
      • Cargar X
      • Guardar X
      • Operar X
    • Ejemplo: T=X+Y
      • Cargar X
      • Sumar Y
      • Guardar T
  • La optimización será reducir el número de operaciones del carga y descarga del acumulador.

Generar Código para Maquina con un Acumulador a partir de Notación Polaca

  • Ideas:
    • Utilizar una pila de variables temporales donde se guardan los operandos.
    • Mirar de eliminar las operaciones de carga/descarga innecesarias.
  • Ejemplo: X=A+(B*C+D)
    • Notación polaca inversa:
      • X A B C * D + + =
    • Código generado sin optimizar
      • Cargar B
      • Mult C
      • Guardar T1 ; B*C
      • Cargar T1
      • Sumar D
      • Guardar T2 ; B*C+D
      • Cargar A
      • Sumar T2
      • Guardar T3 ; A+(B*C+D)
      • Cargar T3
      • Guardar X

Optimización

  • Ideas
    • Retrasar en todo lo posible las instrucción Guardar
    • Reutilizar el contenido del acumulador
    • Sacar provecho de la conmutatividad de las operaciones
  • Ejemplo:
  • Eliminar
  • por reutilización
  • del acumulador
  • Cargar B
  • Mult C
  • Guardar T1 ; B*C
  • Cargar T1
  • Sumar D
  • Guardar T2 ; B*C+D
  • Cargar A
  • Sumar T2
  • Guardar T3 ; A+(B*C+D)
  • Cargar T3
  • Guardar X
  • Cargar B
  • Mult C ; B*C
  • Sumar D ; B*C+D
  • Guardar T2 ; B*C+D
  • Cargar A
  • Sumar T2 ; A+(B*C+D)
  • Guardar X
  • Cargar B
  • Mult C ; B*C
  • Sumar D ; B*C+D
  • Sumar A ; B*C+D+A
  • Guardar X
  • Eliminar
  • por reutilización
  • del acumulador
  • Aplicar la
  • propiedad
  • conmutativa
  • de la suma

Asignación de Registro en Máquinas Multi Registro

  • La asignación de registros tiene dos pasos
    • Register Allocation
    • Register Assignment
      • Es cuando se selecciona el registro para guardar una variable
  • Como optimizar la asignación de registros
    • Minimizar el número de variables temporales necesarias para evaluar una expresión
    • Asignar las variables temporales a registros
      • Si hay suficientes registros ya se ha acabado
      • Si no hay que decidir que variables se han de transferir a memoria y como minimizar el número de transferencias

Minimizar el Número de Variables Temporales

  • Idea:
    • Minimizar el número de registros necesarios para los operandos de una operación y luego considerar en que orden se han de calcular los operandos para minimizar el número de registros del cálculo completo
  • Operación
  • binaria
  • Operando 1
  • n registros
  • Operando 2
  • m registros
  • Max{n,m+1} registros
  • R=Calcular Op1
  • Calcular Op2
  • Operación R,Op2
  • Max{n+1,m} registros
  • R=Calcular Op2
  • Calcular Op1
  • Operación Op1,R

Carga/Descarga de Registros

  • Minimizar el número de operaciones de carga y descarga
    • ¿Que registro se ha de descargar a memoria?
      • No guardar en memoria los operandos izquierdos de operaciones no conmutativas (ej. / -) siempre que haya otra posibilidad. Sólo tiene sentido si el procesador no permite divisiones o restas con los operandos invertidos ( -A+B, A\B).
      • Guardar en memoria el valor que más se tardará en utilizar en el programa
  • Seleccionar el registro para una variable V
    • Si hay algún registro libre asignarlo a V
    • sino si hay un registro cuyo valor no se necesitara
    • asignarlo a V
    • sino seleccionar el registro que más tardará en
    • utilizarse
    • guardar el valor del registro si ha sido modificado
    • asignarlo a V

Cuando se utilizará una Variable

  • Para saber cuando se utilizará una variable se ha de aplicar el cálculo de las variables vivas.
  • Ejemplo:
    • c=c*b
    • a=a+b
    • d=d*c
    • b=d
    • e=c
  • a b c d e
  • Uso de los registros
  • R0 R1 R2
  • b c -
  • b c a
  • d c a
  • d c b
  • e c b

Optimizar Cargas y Descargas

  • Descargar una variable modificada es más costoso que una no modificada. Para considerar esta diferencia de coste se utiliza el siguiente grafo
    • Los vértices representan los estados de utilización de los registros y
    • Las aristas representan las cargas y descargar necesarias para pasar de un estado a otro.
  • Se busca el camino de menor coste que vaya del estado de los registros al inicio del bloque básico hasta el estado de estos al final del bloque básico

Arquitectura Máquina y Generación de Código Real.

  • Generar código por tabla
    • A cada instrucción de código intermedio le corresponde una o más instrucciones de código máquina que se han guardado en una tabla.
  • Los registros no siempre son genéricos
    • 68K registros de datos y direcciones separados
    • Pentium registros separados para enteros y flotantes
  • Una instrucción de código máquina puede ser varias instrucciones de código intermedio
    • En la misma instrucción se realiza el cálculo de la dirección de memoria del elemento de un array
  • push
  • pop
  • MOV (SP)+,R1
  • MOV R1,-(SP)

Ejemplo de Optimización dependiente de Máquina: Pentium y Pentium II (I)

  • Ayudar al compilador para que pueda optimizar el código
  • Tener en cuenta los algoritmos de predicción de saltos
  • Evitar paradas por uso parcial de registros (Avoid partial register stalls).
  • Alinear los datos
  • Ordenar el código para evitar fallos de la cache de prelectura de instrucciones
  • Reordenar las instrucciones para maximizar la ejecución paralela de instrucciones.

Ejemplo de Optimización dependiente de Máquina: Pentium y Pentium II (II)

  • Evitar los prefijos de instrucción
  • Evitar leer y escribir sobre la misma memoria con diferentes tipos de datos.
  • Emparejar CALL y RET
  • Evitar código automodificable
  • No poner datos en el segmento de código
  • Calcular las direcciones de destino cuanto antes

Como Escribir los Programas C

  • Ayudar al compilador para que pueda optimizar el código
    • Minimizar el uso de variables globales
    • Minimizar el uso de punteros
    • Minimizar el uso de estructuras de control complejas
    • No usar register
    • Usar const
    • No contradecir al sistema de tipos
  • Tener en cuenta los algoritmos de predicción de saltos. Suposiciones del predictor
    • No saltar en caso de un salto condicional hacia delante
    • Saltar en caso de salto condicional hacia atrás

Reducir el Número de Saltos

  • Reduce la posibilidad de predicciones erróneas
  • Reduce el número de entradas en la BTB (Branch Target Buffer)
  • Ejemplo: ebx = (A
      • cmp A, B ; condition
      • jge L30 ; conditional branch
      • mov ebx, CONST1
      • jmp L31 ; unconditional branch
      • L30:
      • mov ebx, CONST2
      • L31:
    • Pentium
      • xor ebx, ebx ;clear ebx
      • cmp A, B
      • setge bl ;When ebx = 0 or 1
      • ;OR the complement condition dec ebx ;ebx=00...00 or 11...11
      • and ebx, (CONST2-CONST1) ;ebx=0
      • or (CONST2-CONST1)
      • add ebx, min(CONST1,CONST2)
    • Pentium II
      • move ebx,CONST1
      • cmp A, B
      • cmovege ebx, CONST2

Evitar paradas por uso parcial de registros (Avoid partial register stalls).

  • Register Stall al acceder a EAX
    • MOV AX, 8
    • ADD ECX, EAX
  • En el caso de Pentium II se puede producir para instrucciones no contiguas
    • MOV AL, 8
    • MOV EDX, 0x40
    • MOV EDI, new_value
    • ADD EDX, EAX ;Partial stall

Alinear

  • Alinear datos
    • Align 8-bit data on any boundary.
    • Align 16-bit data to be contained within an aligned 4-byte word.
    • Align 32-bit data on any boundary which is a multiple of four.
    • Align 64-bit data on any boundary which is a multiple of eight.
    • Align 80-bit data on a 128-bit boundary (that is, any boundary which is a multiple of 16 bytes).
  • Alinear código
    • Loop entry labels should be 16-byte aligned when less than eight bytes away from a 16-byte boundary.
    • Labels that follow a conditional branch should not be aligned.
    • Labels that follow an unconditional branch or function call should be 16-byte aligned when less than eight bytes away from a 16-byte boundary.

Reordenar las instrucciones para maximizar la ejecución paralela

  • Pairing cannot be performed when the following conditions occur:
    • The next two instructions are not pairable instructions (see Appendix A for pairing characteristics of individual instructions). In general, most simple ALU instructions are pairable.
    • The next two instructions have some type of register contention (implicit or explicit). There are some special exceptions to this rule where register contention can occur with pairing. These are described later.
    • The instructions are not both in the instruction cache. An exception to this which permits pairing is if the first instruction is a one-byte instruction.


La base de datos está protegida por derechos de autor ©absta.info 2016
enviar mensaje

    Página principal