Download - Optimizaciones Tradicionales
![Page 1: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/1.jpg)
Compiladores
Optimizaciones Tradicionales
Simplificación Algebraica,Copy Propagation,
y Constant Propagation
![Page 2: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/2.jpg)
2
Resumen• Overview de análisis de control de flujo• Simplificación algebraica• Copy Propagation• Constant Propagation
40
![Page 3: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/3.jpg)
3
Expresiones Disponibles• Dominio
– conjunto de expresiones• Dirección de flujo de datos Hacia adelante• Función de flujo de datos
– OUT = gen (IN - kill)– gen = { a | a se calcula en el bloque básico }– kill = { a | una variable va que es definida en el b.b. }
• Operación Meet– IN = OUT
• Valores iniciales conjunto entero (Top)
![Page 4: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/4.jpg)
4
Cadena DU (Reaching Definitions)
• Dominio– conjunto de definiciones
• Dirección de flujo de datos Hacia adelante• Función de flujo de datos
– OUT = gen (IN - kill)– gen = { x | x es definida en el statement}– kill = { x | LHS var. de x es redefinido en el statement. }
• Operación Meet– IN = OUT
• Valores iniciales Conjunto vacío (Bottom)
![Page 5: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/5.jpg)
5
Framework para análisis• Análisis de control de flujo
– Identificar la estructura del programa– Ayuda a construir el análisis de flujo de datos
• Análisis de flujo de datos– Framework para encontrar la información necesaria para
optimizar– Hasta ahora hemos encontrado
• expresiones disponibles• cadenas UD y DU
– ¡Ahora usemos esta información para hacer algo interesante!
![Page 6: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/6.jpg)
6
Optimizaciones
• Cada optimización es muy simple– Reduce la complejidad
• Se necesitan múltiples optimizaciones
• Es posible que haya que aplicar la misma optimización múltiples veces
![Page 7: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/7.jpg)
7
Resumen• Overview de análisis de control de flujo• Simplificación algebraica• Copy Propagation• Constant Propagation
40
![Page 8: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/8.jpg)
8
Simplificación algebraica
• Aplicar nuestro conocimiento de algebra, teoría de números, etc para simplificar expresiones
![Page 9: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/9.jpg)
9
Simplificación algebraica• Aplicar nuestro conocimiento de algebra, teoría de
números, etc para simplificar expresiones• Ejemplo
– a + 0 a– a * 1 a– a / 1 a– a * 0 0– 0 - a -a– a + (-b) a - b– -(-a) a
![Page 10: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/10.jpg)
10
Simplificación algebraica
• Aplicar nuestro conocimiento de algebra, teoría de números, etc para simplificar expresiones
• Ejemplo– a true a– a false false– a true true– a false a
![Page 11: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/11.jpg)
11
Simplificación algebraica
• Aplicar nuestro conocimiento de algebra, teoría de números, etc para simplificar expresiones
• Ejemplo– a ^ 2 a*a– a * 2 a + a– a * 8 a << 3
![Page 12: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/12.jpg)
12
Oportunidades para Simplificación Algebraica
• En el código– Los programadores no simplifican expresiones– Los programas son más legibles con exresiones
completas• Luego de la expansión del compilador
– Ejemplo: Lectura de array A[8][12] va a ser expandida a:
– *(Abase + 4*(12 + 8*256)) que puede ser simplificada después de otras optimizaciones
![Page 13: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/13.jpg)
13
Utilidad de Simplificación Algebraica
• Reduce el número de instrucciones• Usa expresiones menos “caras”• Habilita otras optimizaciones
![Page 14: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/14.jpg)
14
Implementación
• ¡No es una optimización de flujo de datos!• Encontrar candidatos que hagan match con las
reglas de simplificación y simplificar los árboles de expresión
• Los candidatos pueden no ser obvios
![Page 15: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/15.jpg)
15
Implementación
• ¡No es una optimización de flujo de datos!• Encontrar candidatos que hagan match con las
reglas de simplificación y simplificar los árboles de expresión
• Los candidatos pueden no ser obvios– Ejemplo
a + b - aa -
b a
+
![Page 16: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/16.jpg)
16
Usar nuestro conocimiento de los operadores
• Operadores conmutativos a op b = b op a
• Operadores asociativos (a op b) op c = b op (a op c)
![Page 17: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/17.jpg)
17
Forma Canónica
• Poner los árboles de expresiones en forma canónica– Suma de multiplicandos– Ejemplo
• (a + 3) * (a + 8) * 4 4*a*a + 44*a + 96
– La Sección 12.3.1 de la ballena habla de esto
![Page 18: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/18.jpg)
18
Efectos en la estabilidad numérica
• Algunas simplificaciones algebraicas pueden producir resultados incorrectos
![Page 19: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/19.jpg)
19
Efectos en la estabilidad numérica
• Algunas simplificaciones algebraicas pueden producir resultados incorrectos
• Ejemplo– (a / b)*0 + c
![Page 20: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/20.jpg)
20
Efectos en la estabilidad numérica
• Algunas simplificaciones algebraicas pueden producir resultados incorrectos
• Ejemplo– (a / b)*0 + c– Podemos simplificar esto a c
![Page 21: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/21.jpg)
21
Efectos en la estabilidad numérica
• Algunas simplificaciones algebraicas pueden producir resultados incorrectos
• Ejemplo– (a / b)*0 + c– Podemos simplificar esto a c– Pero qué pasa cuándo b = 0
debería ser una excepción, pero vamos a obtener un resultado
![Page 22: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/22.jpg)
22
Resumen• Overview de análisis de control de flujo• Simplificación algebraica• Copy Propagation• Constant Propagation
40
![Page 23: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/23.jpg)
23
Copy Propagation
• Eliminar copias múltiples– propagar el valor directamente a su uso
• Ejemploa = b + cd = ae = df = d + 2*e + c
![Page 24: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/24.jpg)
24
Copy Propagation
• Eliminar copias múltiples– propagar el valor directamente a su uso
• Ejemploa = b + cd = ae = df = d + 2*e + c
![Page 25: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/25.jpg)
25
Copy Propagation
• Eliminar copias múltiples– propagar el valor directamente a su uso
• Ejemploa = b + cd = ae = af = d + 2*e + c
![Page 26: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/26.jpg)
26
Copy Propagation
• Eliminar copias múltiples– propagar el valor directamente a su uso
• Ejemploa = b + cd = ae = af = d + 2*e + c
![Page 27: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/27.jpg)
27
Copy Propagation
• Eliminar copias múltiples– propagar el valor directamente a su uso
• Ejemploa = b + cd = ae = af = a + 2*e + c
![Page 28: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/28.jpg)
28
Copy Propagation
• Eliminar copias múltiples– propagar el valor directamente a su uso
• Ejemploa = b + cd = ae = af = a + 2*e + c
![Page 29: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/29.jpg)
29
Copy Propagation
• Eliminar copias múltiples– propagar el valor directamente a su uso
• Ejemploa = b + cd = ae = af = a + 2*a + c
![Page 30: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/30.jpg)
30
Copy Propagation
• Eliminar copias múltiples– propagar el valor directamente a su uso
• Ejemploa = b + cd = ae = af = a + 2*a + c
![Page 31: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/31.jpg)
31
Oportunidades para Copy Propagation
• En código del usuario• Después de otras optimizaciones
– Ejemplo: Simplificación algebraica
![Page 32: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/32.jpg)
32
Ventajas de Copy Propagation
• Lleva a más simplificaciones algebraicas
![Page 33: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/33.jpg)
33
Ventajas de Copy Propagation
• Lleva a más simplificaciones algebraicas
• Ejemploa = b + cd = ae = af = a + 2*a + c
![Page 34: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/34.jpg)
34
Ventajas de Copy Propagation
• Lleva a más simplificaciones algebraicas
• Ejemploa = b + cd = ae = af = a + 2*a + c
![Page 35: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/35.jpg)
35
Ventajas de Copy Propagation
• Lleva a más simplificaciones algebraicas
• Ejemploa = b + cd = ae = af = 3*a + c
![Page 36: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/36.jpg)
36
Ventajas de Copy Propagation
• Reduce instrucciones al eliminar ops de copia– Crea código muerto que puede ser eliminado
![Page 37: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/37.jpg)
37
Ventajas de Copy Propagation
• Reduce instrucciones al eliminar ops de copia– Crea código muerto que puede ser eliminado
• Ejemploa = b + cd = ae = af = 3*a + c
![Page 38: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/38.jpg)
38
Ventajas de Copy Propagation
• Reduce instrucciones al eliminar ops de copia– Crea código muerto que puede ser eliminado
• Ejemploa = b + c f = 3*a + c
![Page 39: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/39.jpg)
39
Cómo hacer copy propagation
• Para cada expresión RHS Para cada variable v usada en expresión RHS– si la variable v es definida por un statement v = u– reemplazar la variable v por u
• En cada punto del programa hay que saber– qué variables son iguales– un elemento <u,v> está en el conjunto ssi v = u
(u, v son variables)
![Page 40: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/40.jpg)
40
Cómo hacer copy propagation• Una asignación v = u todavía es válida en un
punto dado de ejecución ssi– Un statement v = u occurre en cada camino de
ejecución que llega al punto actual– La variable v no es redefinida en ninguno de estos
caminos de ejecución entre el statement y el punto actual
– La variable u no es redefinida en ninguno de caminos de ejecución entre el statement y el punto actual
• ¡un problema de flujo de datos!
![Page 41: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/41.jpg)
41
Problema de Data-Flow paraCopy Propagation
• Dominio– Conjunto de tuplas <v,u> representando un statement v = u
• Dirección de flujo de datos Hacia adelante• Función de flujo de datos
– OUT = gen (IN - kill)– gen = { <v,u> | v = u es el statement }– kill = { <v,u> | LHS var. del stmt. es v ó u }
• Operación Meet– IN = OUT
• Valores Iniciales Conjunto vacio (Bottom)
![Page 42: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/42.jpg)
42
Ejemplo
b = a
c = b + 1
d = b
b = d + c
b = d
![Page 43: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/43.jpg)
43
b = a
c = b + 1
d = b
b = d + c
b = d
gen = { <v,u> | v = u es el statement }kill = { <v,u> | LHS var. del stmt. es v ó u }
![Page 44: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/44.jpg)
44
b = a
c = b + 1
d = b
b = d + c
b = d
gen = { <b,a> }
gen = { }
gen = { <d,b> }
gen = { }
gen = { <b,d> }
gen = { <v,u> | v = u es el statement }kill = { <v,u> | LHS var. del stmt. es v ó u }
![Page 45: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/45.jpg)
45
b = a
c = b + 1
d = b
b = d + c
b = d
gen = { <b,a> }kill = { <d,b>, <b,d> }
gen = { }kill = { }
gen = { <d,b> }kill = { <b,d> }
gen = { }kill = { <b,a> <d,b>, <b,d> }
gen = { <b,d> }kill = { <b,a>, <d,b> }
gen = { <v,u> | v = u es el statement }kill = { <v,u> | LHS var. del stmt. es v ó u }
![Page 46: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/46.jpg)
46
b = a
c = b + 1
d = b
b = d + c
b = d
gen = { <b,a> }kill = { <d,b>, <b,d> }
gen = { }kill = { }
gen = { <d,b> }kill = { <b,d> }
gen = { }kill = { <b,a> <d,b>, <b,d> }
gen = { <b,d> }kill = { <b,a>, <d,b> }
OUT = gen (IN - kill)
![Page 47: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/47.jpg)
47
b = a
c = b + 1
d = b
b = d + c
b = d
gen = { <b,a> }kill = { <d,b>, <b,d> }
gen = { }kill = { }
gen = { <d,b> }kill = { <b,d> }
gen = { }kill = { <b,a> <d,b>, <b,d> }
gen = { <b,d> }kill = { <b,a>, <d,b> }
OUT = { <b,a> }
IN = { }
OUT = gen (IN - kill)
![Page 48: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/48.jpg)
48
b = a
c = b + 1
d = b
b = d + c
b = d
gen = { <b,a> }kill = { <d,b>, <b,d> }
gen = { }kill = { }
gen = { <d,b> }kill = { <b,d> }
gen = { }kill = { <b,a> <d,b>, <b,d> }
gen = { <b,d> }kill = { <b,a>, <d,b> }
OUT = { <b,a> }
IN = { <b,a> }
IN = { }
OUT = gen (IN - kill)
![Page 49: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/49.jpg)
49
b = a
c = b + 1
d = b
b = d + c
b = d
gen = { <b,a> }kill = { <d,b>, <b,d> }
gen = { }kill = { }
gen = { <d,b> }kill = { <b,d> }
gen = { }kill = { <b,a> <d,b>, <b,d> }
gen = { <b,d> }kill = { <b,a>, <d,b> }
IN = { <b,a> }
IN = { <b,a> }
IN = { }
OUT = { <b,a>, <d,b> }
OUT = gen (IN - kill)
![Page 50: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/50.jpg)
50
b = a
c = b + 1
d = b
b = d + c
b = d
gen = { <b,a> }kill = { <d,b>, <b,d> }
gen = { }kill = { }
gen = { <d,b> }kill = { <b,d> }
gen = { }kill = { <b,a> <d,b>, <b,d> }
gen = { <b,d> }kill = { <b,a>, <d,b> }
IN = { <b,a> }
IN = { <b,a> }
IN = { }
IN = { <b,a>, <d,b> }
OUT = { }
OUT = gen (IN - kill)
![Page 51: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/51.jpg)
51
b = a
c = b + 1
d = b
b = d + c
b = d
gen = { <b,a> }kill = { <d,b>, <b,d> }
gen = { }kill = { }
gen = { <d,b> }kill = { <b,d> }
gen = { }kill = { <b,a> <d,b>, <b,d> }
gen = { <b,d> }kill = { <b,a>, <d,b> }
IN = { <b,a> }
IN = { <b,a> }
IN = { }
IN = { <b,a>, <d,b> }
IN = { }
OUT = { <b,d> }
OUT = gen (IN - kill)
![Page 52: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/52.jpg)
52
b = a
c = b + 1
d = b
b = d + c
b = d
gen = { <b,a> }kill = { <d,b>, <b,d> }
gen = { }kill = { }
gen = { <d,b> }kill = { <b,d> }
gen = { }kill = { <b,a> <d,b>, <b,d> }
gen = { <b,d> }kill = { <b,a>, <d,b> }
{ <b,a> }
{ <b,a> }
{ }
{ <b,a>, <d,b> }
{ }
{ <b,d> }
OUT = gen (IN - kill)
![Page 53: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/53.jpg)
53
Ejemplo
b = a
c = b + 1
d = b
b = d + c
b = d
gen = { <b,a> }kill = { <d,b>, <b,d> }
gen = { }kill = { }
gen = { <d,b> }kill = { <b,d> }
gen = { }kill = { <b,a> <d,b>, <b,d> }
gen = { <b,d> }kill = { <b,a>, <d,b> }
{ <b,a> }
{ <b,a> }
{ }
{ <b,a>, <d,b> }
{ }
{ <b,d> }
![Page 54: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/54.jpg)
54
Ejemplo
b = a
c = b + 1
d = a
b = d + c
b = d
gen = { <b,a> }kill = { <d,b>, <b,d> }
gen = { }kill = { }
gen = { <d,b> }kill = { <b,d> }
gen = { }kill = { <b,a> <d,b>, <b,d> }
gen = { <b,d> }kill = { <b,a>, <d,b> }
{ <b,a> }
{ <b,a> }
{ }
{ <b,a>, <d,b> }
{ }
{ <b,d> }
![Page 55: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/55.jpg)
55
Ejemplo
b = a
c = b + 1
d = a
b = d + c
b = d
gen = { <b,a> }kill = { <d,b>, <b,d> }
gen = { }kill = { }
gen = { <d,b> }kill = { <b,d> }
gen = { }kill = { <b,a> <d,b>, <b,d> }
gen = { <b,d> }kill = { <b,a>, <d,b> }
{ <b,a> }
{ <b,a> }
{ }
{ <b,a>, <d,b> }
{ }
{ <b,d> }
![Page 56: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/56.jpg)
56
Ejemplo
b = a
c = b + 1
d = a
b = b + c
b = d
gen = { <b,a> }kill = { <d,b>, <b,d> }
gen = { }kill = { }
gen = { <d,b> }kill = { <b,d> }
gen = { }kill = { <b,a> <d,b>, <b,d> }
gen = { <b,d> }kill = { <b,a>, <d,b> }
{ <b,a> }
{ <b,a> }
{ }
{ <b,a>, <d,b> }
{ }
{ <b,d> }
![Page 57: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/57.jpg)
57
Ejemplo
b = a
c = b + 1
d = a
b = b + c
b = d
gen = { <b,a> }kill = { <d,b>, <b,d> }
gen = { }kill = { }
gen = { <d,b> }kill = { <b,d> }
gen = { }kill = { <b,a> <d,b>, <b,d> }
gen = { <b,d> }kill = { <b,a>, <d,b> }
{ <b,a> }
{ <b,a> }
{ }
{ <b,a>, <d,b> }
{ }
{ <b,d> }
![Page 58: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/58.jpg)
58
Ejemplo
b = a
c = b + 1
d = a
b = b + c
b = d
¿Terminamos?
¡No!
![Page 59: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/59.jpg)
59
b = a
c = b + 1
d = a
b = b + c
b = d
gen = { <b,a> }
gen = { }
gen = { <d,a> }
gen = { }
gen = { <b,d> }
gen = { <v,u> | v = u es el statement }kill = { <v,u> | LHS var. del stmt. es v ó u }
![Page 60: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/60.jpg)
60
b = a
c = b + 1
d = a
b = b + c
b = d
gen = { <b,a> }kill = { <d,a>, <b,d> }
gen = { }kill = { }
gen = { <d,a> }kill = { <b,d> }
gen = { }kill = { <b,a>, <b,d> }
gen = { <b,d> }kill = { <b,a> }
gen = { <v,u> | v = u es el statement }kill = { <v,u> | LHS var. del stmt. es v ó u }
![Page 61: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/61.jpg)
61
b = a
c = b + 1
d = a
b = b + c
b = d
gen = { <b,a> }kill = { <d,a>, <b,d> }
gen = { }kill = { }
gen = { <d,a> }kill = { <b,d> }
gen = { }kill = { <b,a>, <b,d> }
gen = { <b,d> }kill = { <b,a> }
OUT = { <b,a> }
IN = { }
OUT = gen (IN - kill)
![Page 62: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/62.jpg)
62
b = a
c = b + 1
d = a
b = b + c
b = d
gen = { <b,a> }kill = { <d,a>, <b,d> }
gen = { }kill = { }
gen = { <d,a> }kill = { <b,d> }
gen = { }kill = { <b,a>, <b,d> }
gen = { <b,d> }kill = { <b,a> }
OUT = { <b,a> }
IN = { <b,a> }
IN = { }
OUT = gen (IN - kill)
![Page 63: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/63.jpg)
63
b = a
c = b + 1
d = a
b = b + c
b = d
gen = { <b,a> }kill = { <d,a>, <b,d> }
gen = { }kill = { }
gen = { <d,a> }kill = { <b,d> }
gen = { }kill = { <b,a>, <b,d> }
gen = { <b,d> }kill = { <b,a> }
IN = { <b,a> }
IN = { <b,a> }
IN = { }
OUT = { <b,a>, <d,a> }
OUT = gen (IN - kill)
![Page 64: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/64.jpg)
64
b = a
c = b + 1
d = a
b = b + c
b = d
gen = { <b,a> }kill = { <d,a>, <b,d> }
gen = { }kill = { }
gen = { <d,a> }kill = { <b,d> }
gen = { }kill = { <b,a>, <b,d> }
gen = { <b,d> }kill = { <b,a> }
IN = { <b,a> }
IN = { <b,a> }
IN = { }
IN = { <b,a>, <d,a> }
OUT = { <d,a> }
OUT = gen (IN - kill)
![Page 65: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/65.jpg)
65
b = a
c = b + 1
d = a
b = b + c
b = d
gen = { <b,a> }kill = { <d,a>, <b,d> }
gen = { }kill = { }
gen = { <d,a> }kill = { <b,d> }
gen = { }kill = { <b,a>, <b,d> }
gen = { <b,d> }kill = { <b,a> }
IN = { <b,a> }
IN = { <b,a> }
IN = { }
IN = { <b,a>, <d,a> }
IN = { <d,a> }
OUT = {<d,a> ,<b,d> }
OUT = gen (IN - kill)
![Page 66: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/66.jpg)
66
Ejemplo
b = a
c = b + 1
d = a
b = b + c
b = d
gen = { <b,a> }kill = { <d,a>, <b,d> }
gen = { }kill = { }
gen = { <d,a> }kill = { <b,d> }
gen = { }kill = { <b,a>, <b,d> }
gen = { <b,d> }kill = { <b,a> }
{ <b,a> }
{ <b,a> }
{ }
{ <b,a>, <d,a> }
{ <d,a> }
{<d,a> ,<b,d> }
![Page 67: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/67.jpg)
67
Ejemplo
b = a
c = b + 1
d = a
b = b + c
b = d
gen = { <b,a> }kill = { <d,a>, <b,d> }
gen = { }kill = { }
gen = { <d,a> }kill = { <b,d> }
gen = { }kill = { <b,a>, <b,d> }
gen = { <b,d> }kill = { <b,a> }
{ <b,a> }
{ <b,a> }
{ }
{ <b,a>, <d,a> }
{ <d,a> }
{<d,a> ,<b,d> }
![Page 68: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/68.jpg)
68
Ejemplo
b = a
c = b + 1
d = a
b = a + c
b = d
gen = { <b,a> }kill = { <d,a>, <b,d> }
gen = { }kill = { }
gen = { <d,a> }kill = { <b,d> }
gen = { }kill = { <b,a>, <b,d> }
gen = { <b,d> }kill = { <b,a> }
{ <b,a> }
{ <b,a> }
{ }
{ <b,a>, <d,a> }
{ <d,a> }
{<d,a> ,<b,d> }
![Page 69: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/69.jpg)
69
Ejemplo
b = a
c = b + 1
d = a
b = a + c
b = d
gen = { <b,a> }kill = { <d,a>, <b,d> }
gen = { }kill = { }
gen = { <d,a> }kill = { <b,d> }
gen = { }kill = { <b,a>, <b,d> }
gen = { <b,d> }kill = { <b,a> }
{ <b,a> }
{ <b,a> }
{ }
{ <b,a>, <d,a> }
{ <d,a> }
{<d,a> ,<b,d> }
![Page 70: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/70.jpg)
70
Ejemplo
b = a
c = b + 1
d = a
b = a + c
b = a
gen = { <b,a> }kill = { <d,a>, <b,d> }
gen = { }kill = { }
gen = { <d,a> }kill = { <b,d> }
gen = { }kill = { <b,a>, <b,d> }
gen = { <b,d> }kill = { <b,a> }
{ <b,a> }
{ <b,a> }
{ }
{ <b,a>, <d,a> }
{ <d,a> }
{<d,a> ,<b,d> }
![Page 71: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/71.jpg)
71
Ejemplo
b = a
c = b + 1
d = a
b = a + c
b = a
gen = { <b,a> }kill = { <d,a>, <b,d> }
gen = { }kill = { }
gen = { <d,a> }kill = { <b,d> }
gen = { }kill = { <b,a>, <b,d> }
gen = { <b,d> }kill = { <b,a> }
{ <b,a> }
{ <b,a> }
{ }
{ <b,a>, <d,a> }
{ <d,a> }
{<d,a> ,<b,d> }
![Page 72: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/72.jpg)
72
Ejemplo
b = a
c = b + 1
d = a
b = a + c
b = a
¿Terminamos?
¡Sí!
![Page 73: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/73.jpg)
73
Otro Ejemplo
a = b + cp = q + r
d = as = p
a = d + p
d = a
![Page 74: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/74.jpg)
74
Otro Ejemplo
a = b + cp = q + r
d = as = p
a = d + p
d = a
Gen = { }
Gen = {<d,a>, <s,p> } Gen = {<d,a> }
Gen = { }
gen = { <v,u> | v = u es el statement }kill = { <v,u> | LHS var. del stmt. es v ó u }
![Page 75: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/75.jpg)
75
Otro Ejemplo
a = b + cp = q + r
d = as = p
a = d + p
d = a
Gen = { }Kill = {<d,a>, <s,p> }
Gen = {<d,a>, <s,p> }Kill = { }
Gen = {<d,a> }Kill = { }
Gen = { }Kill = {{<d,a> }
gen = { <v,u> | v = u es el statement }kill = { <v,u> | LHS var. del stmt. es v ó u }
![Page 76: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/76.jpg)
76
Otro Ejemplo
a = b + cp = q + r
d = as = p
a = d + p
d = a
Gen = { }Kill = {<d,a>, <s,p> }
Gen = {<d,a>, <s,p> }Kill = { }
Gen = {<d,a> }Kill = { }
Gen = { }Kill = {{<d,a> }
OUT = gen (IN - kill)IN = OUT
![Page 77: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/77.jpg)
77
Otro Ejemplo
a = b + cp = q + r
d = as = p
a = d + p
d = a
Gen = { }Kill = {<d,a>, <s,p> }
Gen = {<d,a>, <s,p> }Kill = { }
Gen = {<d,a> }Kill = { }
Gen = { }Kill = {{<d,a> }
IN = { }OUT = gen (IN - kill)IN = OUT
![Page 78: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/78.jpg)
78
Otro Ejemplo
a = b + cp = q + r
d = as = p
a = d + p
d = a
Gen = { }Kill = {<d,a>, <s,p> }
Gen = {<d,a>, <s,p> }Kill = { }
Gen = {<d,a> }Kill = { }
Gen = { }Kill = {{<d,a> }
IN = { }OUT = gen (IN - kill)IN = OUT
![Page 79: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/79.jpg)
79
Otro Ejemplo
a = b + cp = q + r
d = as = p
a = d + p
d = a
Gen = { }Kill = {<d,a>, <s,p> }
Gen = {<d,a>, <s,p> }Kill = { }
Gen = {<d,a> }Kill = { }
Gen = { }Kill = {{<d,a> }
IN = { }OUT = gen (IN - kill)IN = OUT
OUT = { }
![Page 80: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/80.jpg)
80
Otro Ejemplo
a = b + cp = q + r
d = as = p
a = d + p
d = a
Gen = { }Kill = {<d,a>, <s,p> }
Gen = {<d,a>, <s,p> }Kill = { }
Gen = {<d,a> }Kill = { }
Gen = { }Kill = {{<d,a> }
IN = { }OUT = gen (IN - kill)IN = OUT
OUT = { }
IN = { }
![Page 81: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/81.jpg)
81
Otro Ejemplo
a = b + cp = q + r
d = as = p
a = d + p
d = a
Gen = { }Kill = {<d,a>, <s,p> }
Gen = {<d,a>, <s,p> }Kill = { }
Gen = {<d,a> }Kill = { }
Gen = { }Kill = {{<d,a> }
IN = { }OUT = gen (IN - kill)IN = OUT
OUT = { }
IN = { }
![Page 82: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/82.jpg)
82
Otro Ejemplo
a = b + cp = q + r
d = as = p
a = d + p
d = a
Gen = { }Kill = {<d,a>, <s,p> }
Gen = {<d,a>, <s,p> }Kill = { }
Gen = {<d,a> }Kill = { }
Gen = { }Kill = {{<d,a> }
IN = { }OUT = gen (IN - kill)IN = OUT
OUT = { }
IN = { }
OUT = { <d,a>, <s,p> }
![Page 83: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/83.jpg)
83
Otro Ejemplo
a = b + cp = q + r
d = as = p
a = d + p
d = a
Gen = { }Kill = {<d,a>, <s,p> }
Gen = {<d,a>, <s,p> }Kill = { }
Gen = {<d,a> }Kill = { }
Gen = { }Kill = {{<d,a> }
IN = { }OUT = gen (IN - kill)IN = OUT
OUT = { }
IN = { } IN = { }
OUT = { <d,a>, <s,p> }
![Page 84: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/84.jpg)
84
Otro Ejemplo
a = b + cp = q + r
d = as = p
a = d + p
d = a
Gen = { }Kill = {<d,a>, <s,p> }
Gen = {<d,a>, <s,p> }Kill = { }
Gen = {<d,a> }Kill = { }
Gen = { }Kill = {{<d,a> }
IN = { }OUT = gen (IN - kill)IN = OUT
OUT = { }
IN = { } IN = { }
OUT = { <d,a>, <s,p> }
![Page 85: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/85.jpg)
85
Otro Ejemplo
a = b + cp = q + r
d = as = p
a = d + p
d = a
Gen = { }Kill = {<d,a>, <s,p> }
Gen = {<d,a>, <s,p> }Kill = { }
Gen = {<d,a> }Kill = { }
Gen = { }Kill = {{<d,a> }
IN = { }OUT = gen (IN - kill)IN = OUT
OUT = { }
IN = { } IN = { }
OUT = { <d,a>, <s,p> } OUT = { <d,a> }
![Page 86: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/86.jpg)
86
Otro Ejemplo
a = b + cp = q + r
d = as = p
a = d + p
d = a
Gen = { }Kill = {<d,a>, <s,p> }
Gen = {<d,a>, <s,p> }Kill = { }
Gen = {<d,a> }Kill = { }
Gen = { }Kill = {{<d,a> }
IN = { }OUT = gen (IN - kill)IN = OUT
OUT = { }
IN = { } IN = { }
OUT = { <d,a>, <s,p> } OUT = { <d,a> }
IN = { <d,a> }
![Page 87: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/87.jpg)
87
Otro Ejemplo
a = b + cp = q + r
d = as = p
a = d + p
d = a
Gen = { }Kill = {<d,a>, <s,p> }
Gen = {<d,a>, <s,p> }Kill = { }
Gen = {<d,a> }Kill = { }
Gen = { }Kill = {{<d,a> }
IN = { }OUT = gen (IN - kill)IN = OUT
OUT = { }
IN = { } IN = { }
OUT = { <d,a>, <s,p> } OUT = { <d,a> }
IN = { <d,a> }
![Page 88: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/88.jpg)
88
Otro Ejemplo
a = b + cp = q + r
d = as = p
a = d + p
d = a
Gen = { }Kill = {<d,a>, <s,p> }
Gen = {<d,a>, <s,p> }Kill = { }
Gen = {<d,a> }Kill = { }
Gen = { }Kill = {{<d,a> }
IN = { }OUT = gen (IN - kill)IN = OUT
OUT = { }
IN = { } IN = { }
OUT = { <d,a>, <s,p> } OUT = { <d,a> }
OUT = { }
IN = { <d,a> }
![Page 89: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/89.jpg)
89
Otro Ejemplo
a = b + cp = q + r
d = as = p
a = d + p
d = a
IN = { }
OUT = { }
IN = { } IN = { }
OUT = { <d,a>, <s,p> } OUT = { <d,a> }
OUT = { }
IN = { <d,a> }
![Page 90: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/90.jpg)
90
Otro Ejemplo
a = b + cp = q + r
d = as = p
a = d + p
d = a
IN = { }
OUT = { }
IN = { } IN = { }
OUT = { <d,a>, <s,p> } OUT = { <d,a> }
OUT = { }
IN = { <d,a> }
![Page 91: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/91.jpg)
91
Otro Ejemplo
a = b + cp = q + r
d = as = p
a = a + p
d = a
IN = { }
OUT = { }
IN = { } IN = { }
OUT = { <d,a>, <s,p> } OUT = { <d,a> }
OUT = { }
IN = { <d,a> }
![Page 92: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/92.jpg)
92
Otro Ejemplo
a = b + cp = q + r
d = as = p
a = a + p
d = a
IN = { }
OUT = { }
IN = { } IN = { }
OUT = { <d,a>, <s,p> } OUT = { <d,a> }
OUT = { }
IN = { <d,a> }
![Page 93: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/93.jpg)
93
Otro Ejemplo
a = b + cp = q + r
d = as = p
a = a + p
d = a
![Page 94: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/94.jpg)
94
Resumen• Overview de análisis de control de flujo• Simplificación algebraica• Copy Propagation• Constant Propagation
40
![Page 95: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/95.jpg)
95
Constant Propagation
• Usar valores constantes– Usar la constante conocida para una variable
![Page 96: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/96.jpg)
96
Constant Propagation
• Usar valores constantes– Usar la constante conocida para una variable
• Ejemploa = 43b = 4d = a + 2*b + c
![Page 97: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/97.jpg)
97
Constant Propagation
• Usar valores constantes– Usar la constante conocida para una variable
• Ejemploa = 43b = 4d = a + 2*b + c
![Page 98: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/98.jpg)
98
Constant Propagation
• Usar valores constantes– Usar la constante conocida para una variable
• Ejemploa = 43b = 4d = 43 + 2*b + c
![Page 99: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/99.jpg)
99
Constant Propagation
• Usar valores constantes– Usar la constante conocida para una variable
• Ejemploa = 43b = 4d = a + 2*b + c
![Page 100: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/100.jpg)
100
Constant Propagation
• Usar valores constantes– Usar la constante conocida para una variable
• Ejemploa = 43b = 4d = 43 + 2*4 + c
![Page 101: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/101.jpg)
101
Oportunidades paraConstant Propagation
• Constantes definidas por el usuario– Las mismas constantes se propagan por muchos
caminos– Constantes simbólicas definidas como variables
• Constantes conocidas al compilador– data sizes, stack offsets
• Constantes disponibles después de otras optimizaciones– Simplificación algebraica– Copy propagation
![Page 102: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/102.jpg)
102
Ventajas de Constant Propagation
• Simplificación del programa
![Page 103: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/103.jpg)
103
Ventajas de Constant Propagation
• Simplificación del programa
• Ejemploa = 43b = 4d = 43 + 2*4 + c
![Page 104: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/104.jpg)
104
Ventajas de Constant Propagation
• Simplificación del programa
• Ejemploa = 43b = 4d = 43 + 2*4 + c
![Page 105: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/105.jpg)
105
Ventajas de Constant Propagation
• Simplificación del programa
• Ejemploa = 43b = 4d = 51 + c
![Page 106: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/106.jpg)
106
Ventajas de Constant Propagation
• Habilita otras optimizaciones
![Page 107: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/107.jpg)
107
Ventajas de Constant Propagation
• Habilita otras optimizaciones
• Ejemploa = 4b = 8d = 2*a - b + ce = c + d
![Page 108: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/108.jpg)
108
Ventajas de Constant Propagation
• Habilita otras optimizaciones
• Ejemploa = 4b = 8d = 2*a - b + ce = c + d
![Page 109: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/109.jpg)
109
Ventajas de Constant Propagation
• Habilita otras optimizaciones
• Ejemploa = 4b = 8d = 2*4 - b + ce = c + d
![Page 110: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/110.jpg)
110
Ventajas de Constant Propagation
• Habilita otras optimizaciones
• Ejemploa = 4b = 8d = 2*4 - b + ce = c + d
![Page 111: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/111.jpg)
111
Ventajas de Constant Propagation
• Habilita otras optimizaciones
• Ejemploa = 4b = 8d = 2*4 - 8 + ce = c + d
![Page 112: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/112.jpg)
112
Ventajas de Constant Propagation
• Habilita otras optimizaciones
• Ejemploa = 4b = 8d = 2*4 - 8 + ce = c + d
![Page 113: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/113.jpg)
113
Ventajas de Constant Propagation
• Habilita otras optimizaciones
• Ejemploa = 4b = 8d = 8 - 8 + ce = c + d
![Page 114: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/114.jpg)
114
Ventajas de Constant Propagation
• Habilita otras optimizaciones
• Ejemploa = 4b = 8d = 8 - 8 + ce = c + d
![Page 115: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/115.jpg)
115
Ventajas de Constant Propagation
• Habilita otras optimizaciones
• Ejemploa = 4b = 8d = 0 + ce = c + d
![Page 116: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/116.jpg)
116
Ventajas de Constant Propagation
• Habilita otras optimizaciones
• Ejemploa = 4b = 8d = 0 + ce = c + d
![Page 117: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/117.jpg)
117
Ventajas de Constant Propagation
• Habilita otras optimizaciones
• Ejemploa = 4b = 8d = ce = c + d
![Page 118: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/118.jpg)
118
Ventajas de Constant Propagation
• Habilita otras optimizaciones
• Ejemploa = 4b = 8d = ce = c + d
![Page 119: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/119.jpg)
119
Ventajas de Constant Propagation
• Habilita otras optimizaciones
• Ejemploa = 4b = 8d = ce = c + d
![Page 120: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/120.jpg)
120
Ventajas de Constant Propagation
• Habilita otras optimizaciones
• Ejemploa = 4b = 8d = ce = c + c
![Page 121: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/121.jpg)
121
Ventajas de Constant Propagation
• Habilita otras optimizaciones
• Ejemploa = 4b = 8d = ce = c + c
![Page 122: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/122.jpg)
122
Ventajas de Constant Propagation
• Habilita otras optimizaciones
• Ejemploa = 4b = 8d = ce = c + c
![Page 123: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/123.jpg)
123
Ventajas de Constant Propagation
• Habilita otras optimizaciones
• Ejemploa = 4b = 8d = ce = 2*c
![Page 124: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/124.jpg)
124
Ventajas de Constant Propagation
• Habilita otras optimizaciones
• Ejemploa = 4b = 8d = ce = 2*c
![Page 125: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/125.jpg)
125
Ventajas de Constant Propagation
• Habilita otras optimizaciones
• Ejemploa = 4b = 8
e = 2*c
![Page 126: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/126.jpg)
126
Cómo hacer Constant Propagation
• En cada expresión RHS Para cada variable v usada en expresión RHS– si la variable v es una constante conocida k– reemplazar la variable v por k
• En cada punto del programa hay que saber– Para cada variable v, si v es una constante, y si lo
es, el valor constante
![Page 127: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/127.jpg)
127
Cómo hacer Constant Propagation
• Una variable v es la constante k en un punto de ejecución ssi– el statement actual es v = k
o– todo camino que llega al punto actual tiene la
constante k asignada a v• ¡Un problema de flujo de datos!
![Page 128: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/128.jpg)
128
Valores de dos caminos
a = 5
b = a + 10
a = 5
a = 5
![Page 129: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/129.jpg)
129
Valores de dos caminos
a = 5
b = a + 10
a = k + 2
a no es constante
![Page 130: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/130.jpg)
130
Valores de dos caminos
a = 5
b = a + 10
a = 7
a no es constante
![Page 131: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/131.jpg)
131
Valores de dos caminos
a = 5
b = a + 10
a no definida
a = 5
![Page 132: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/132.jpg)
132
Valores de dos caminos
a = 5
b = a + 10
a no definida
a = 5
• programa tonto, usa un valor no inicializado
![Page 133: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/133.jpg)
133
Valores de dos caminos
a = 5
b = a + 10
a no definida
a = 5
• programa tonto, usa un valor no inicializado• semántica de alto nivel que el compilador no entiende hace que este sea un programa correcto
![Page 134: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/134.jpg)
134
Lattice para Constant Propagation
= not a constant
T = undefined
false true …. -2 -1 0 1 2 3 4 ….
![Page 135: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/135.jpg)
135
Lattice (repaso)
• Un lattice L consiste de– un conjunto de valores – dos operaciones meet( ) y join ( )– un valor top (T) y un valor bottom ()
![Page 136: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/136.jpg)
136
Lattice (repaso)
• Ejemplo: el lattice para el problema de reaching definitions cuándo sólo hay 3 definiciones
{ d1, d2 }
{ d2, d3 }
{ d1 }
{ d3 }
= { }
T = { d1, d2, d3 }
{ d1, d3 }{ d2 }
![Page 137: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/137.jpg)
137
Operaciones Meet y Join
{ d1, d2 }
{ d2, d3 }
{ d1 }
{ d3 }
= { }
T = { d1, d2, d3 }
{ d1, d3 }{ d2 }
{ d1, d2 } { d2, d3 } = ???
![Page 138: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/138.jpg)
138
Operaciones Meet y Join
{ d1, d2 }
{ d2, d3 }
{ d1 }
{ d3 }
= { }
T = { d1, d2, d3 }
{ d1, d3 }{ d2 }
{ d1, d2 } { d2, d3 } = ???
![Page 139: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/139.jpg)
139
Operaciones Meet y Join
{ d1, d2 }
{ d2, d3 }
{ d1 }
{ d3 }
= { }
T = { d1, d2, d3 }
{ d1, d3 }{ d2 }
{ d1, d2 } { d2, d3 } = ???
![Page 140: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/140.jpg)
140
Operaciones Meet y Join
{ d1, d2 }
{ d2, d3 }
{ d1 }
{ d3 }
= { }
T = { d1, d2, d3 }
{ d1, d3 }{ d2 }
{ d1, d2 } { d2, d3 } = { d2 }
![Page 141: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/141.jpg)
141
Operaciones Meet y Join
{ d1, d2 }
{ d2, d3 }
{ d1 }
{ d3 }
= { }
T = { d1, d2, d3 }
{ d1, d3 }{ d2 }
{ d1, d2 } { d3 } = ???
![Page 142: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/142.jpg)
142
Operaciones Meet y Join
{ d1, d2 }
{ d2, d3 }
{ d1 }
{ d3 }
= { }
T = { d1, d2, d3 }
{ d1, d3 }{ d2 }
{ d1, d2 } { d3 } = ???
![Page 143: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/143.jpg)
143
Operaciones Meet y Join
{ d1, d2 }
{ d2, d3 }
{ d1 }
{ d3 }
= { }
T = { d1, d2, d3 }
{ d1, d3 }{ d2 }
{ d1, d2 } { d3 } = ???
![Page 144: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/144.jpg)
144
Operaciones Meet y Join
{ d1, d2 }
{ d2, d3 }
{ d1 }
{ d3 }
= { }
T = { d1, d2, d3 }
{ d1, d3 }{ d2 }
{ d1, d2 } { d3 } = ???
![Page 145: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/145.jpg)
145
Operaciones Meet y Join
{ d1, d2 }
{ d2, d3 }
{ d1 }
{ d3 }
= { }
T = { d1, d2, d3 }
{ d1, d3 }{ d2 }
{ d1, d2 } { d3 } = { d1, d2, d3 }
![Page 146: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/146.jpg)
146
Lattice para Constant Propagation
= not a constant
T = undefined
false true …. -2 -1 0 1 2 3 4 ….
![Page 147: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/147.jpg)
147
Operación Meet en el lattice
= not a constant
T = undefined
false true …. -2 -1 0 1 2 3 4 ….
a = 2 a = 2
= a
2 2 =
![Page 148: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/148.jpg)
148
Operación Meet en el lattice
= not a constant
T = undefined
false true …. -2 -1 0 1 2 3 4 ….
a = 2 a = 2
= a
2 2 =
![Page 149: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/149.jpg)
149
Operación Meet en el lattice
= not a constant
T = undefined
false true …. -2 -1 0 1 2 3 4 ….
a = 2 a = 2
= a
2 2 = 2
![Page 150: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/150.jpg)
150
Operación Meet en el lattice
= not a constant
T = undefined
false true …. -2 -1 0 1 2 3 4 ….
a = 2 a = 0
= a
2 0 =
![Page 151: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/151.jpg)
151
Operación Meet en el lattice
= not a constant
T = undefined
false true …. -2 -1 0 1 2 3 4 ….
a = 2 a = 0
= a
2 0 =
![Page 152: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/152.jpg)
152
Operación Meet en el lattice
= not a constant
T = undefined
false true …. -2 -1 0 1 2 3 4 ….
a = 2 a = 0
= a
2 0 =
![Page 153: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/153.jpg)
153
Operación Meet en el lattice
= not a constant
T = undefined
false true …. -2 -1 0 1 2 3 4 ….
a = 2 a = 0
= a
2 0 = not a constant
![Page 154: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/154.jpg)
154
Operación Meet en el lattice
= not a constant
T = undefined
false true …. -2 -1 0 1 2 3 4 ….
a = 2 undefined
= a
2 undefined =
![Page 155: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/155.jpg)
155
Operación Meet en el lattice
= not a constant
T = undefined
false true …. -2 -1 0 1 2 3 4 ….
a = 2 undefined
= a
2 undefined =
![Page 156: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/156.jpg)
156
Operación Meet en el lattice
= not a constant
T = undefined
false true …. -2 -1 0 1 2 3 4 ….
a = 2 undefined
= a
2 undefined =
![Page 157: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/157.jpg)
157
Operación Meet en el lattice
= not a constant
T = undefined
false true …. -2 -1 0 1 2 3 4 ….
a = 2 undefined
= a
2 undefined = 2
![Page 158: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/158.jpg)
158
Problema de Data-Flow paraConstant Propagation
• Dominio– Para cada variable un lattice Lv
• Dirección de flujo de datos Hacia adelante• Función de flujo de datos
– OUT = gen (IN resv)
![Page 159: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/159.jpg)
159
Problema de Data-Flow paraConstant Propagation
• Dominio– Para cada variable un lattice Lv
• Dirección de flujo de datos Hacia adelante• Función de flujo de datos
– OUT = gen (IN resv) T si v no es LHS
– gen = xv xv = valor si v es LHS & RHS es constante de otra forma
![Page 160: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/160.jpg)
160
Problema de Data-Flow paraConstant Propagation
• Dominio– Para cada variable un lattice Lv
• Dirección de flujo de datos Hacia adelante• Función de flujo de datos
– OUT = gen (IN resv) T si v no es LHS
– gen = xv xv = valor si v es LHS & RHS es constante de otra forma
– prsv = xv xv = T si v es el LHS si v no es el LHS
![Page 161: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/161.jpg)
161
Problema de Data-Flow paraConstant Propagation
• Dominio– Para cada variable un lattice Lv
• Dirección de flujo de datos Hacia adelante• Función de flujo de datos
– OUT = gen (IN resv) T si v no es LHS
– gen = xv xv = valor si v es LHS & RHS es constante de otra forma
– prsv = xv xv =
• Valores Iniciales T (= undefined)
T si v es el LHS si v no es el LHS
![Page 162: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/162.jpg)
162
i = 1 j = 2k = false
i = 3 j = 2
print j j = j + 1
k
exit
i < n
![Page 163: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/163.jpg)
163
i = 1
j = 2
k = false
![Page 164: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/164.jpg)
164
•
T si v no es LHS– gen = xv xv = valor si v es LHS & RHS es constante.
de otra forma
– prsv = xv xv = T si v es el LHS si v no es el LHS
![Page 165: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/165.jpg)
165
gen ={ i:T, j:T, k:T, n:T }
•
T si v no es LHS– gen = xv xv = valor si v es LHS & RHS es constante.
de otra forma
– prsv = xv xv = T si v es el LHS si v no es el LHS
![Page 166: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/166.jpg)
166
gen ={ i:T, j:T, k:T, n:T }
prsv = { i:, j:, k:, n: }•
T si v no es LHS– gen = xv xv = valor si v es LHS & RHS es constante.
de otra forma
– prsv = xv xv = T si v es el LHS si v no es el LHS
![Page 167: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/167.jpg)
167
i = 1
gen ={ i:1, j:T, k:T, n:T }
prsv = { i:T, j:, k:, n: }•
T si v no es LHS– gen = xv xv = valor si v es LHS & RHS es constante.
de otra forma
– prsv = xv xv = T si v es el LHS si v no es el LHS
![Page 168: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/168.jpg)
168
i = 1
j = 2
gen ={ i:1, j:2, k:T, n:T }
prsv = { i:T, j:T, k:, n: }•
T si v no es LHS– gen = xv xv = valor si v es LHS & RHS es constante.
de otra forma
– prsv = xv xv = T si v es el LHS si v no es el LHS
![Page 169: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/169.jpg)
169
i = 1
j = 2
k = false
gen ={ i:1, j:2, k:false, n:T }
prsv = { i:T, j:T, k:T, n: }•
T si v no es LHS– gen = xv xv = valor si v es LHS & RHS es constante.
de otra forma
– prsv = xv xv = T si v es el LHS si v no es el LHS
![Page 170: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/170.jpg)
170
i = 1 j = 2k = false
i = 3 j = 2
print j j = j + 1
k
exit
i < n
gen ={ i:1, j:2, k:false, n:T } prsv = { i:T, j:T, k:T, n: }
gen ={ i:T, j:T, k:T, n:T } prsv = { i:, j:, k:, n: }
gen ={ i:3, j:2, k:T, n:T } prsv = { i:T, j:T, k:, n: }
gen ={ i:T, j:T, k:T, n:T } prsv = { i:, j:, k:, n: }
gen ={ i:T, j:T, k:T, n:T } prsv = { i:, j:, k:, n: }
gen ={ i:T, j:, k:T, n:T } prsv ={ i:, j:T, k:, n:}
gen ={ i:T, j:T, k:T, n:T } prsv = { i:, j:, k:, n: }
![Page 171: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/171.jpg)
171
i = 1 j = 2k = false
i = 3 j = 2
print j j = j + 1
k
exit
i < n
gen ={ i:1, j:2, k:false, n:T } prsv = { i:T, j:T, k:T, n: }
gen ={ i:T, j:T, k:T, n:T } prsv = { i:, j:, k:, n: }
gen ={ i:3, j:2, k:T, n:T } prsv = { i:T, j:T, k:, n: }
gen ={ i:T, j:T, k:T, n:T } prsv = { i:, j:, k:, n: }
gen ={ i:T, j:T, k:T, n:T } prsv = { i:, j:, k:, n: }
gen ={ i:T, j:, k:T, n:T } prsv ={ i:, j:T, k:, n:}
gen ={ i:T, j:T, k:T, n:T } prsv = { i:, j:, k:, n: }
![Page 172: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/172.jpg)
172
i = 1 j = 2k = false
i = 3 j = 2
print j j = j + 1
k
exit
i < n
gen ={ i:1, j:2, k:false, n:T } prsv = { i:T, j:T, k:T, n: }
gen ={ i:T, j:T, k:T, n:T } prsv = { i:, j:, k:, n: }
gen ={ i:3, j:2, k:T, n:T } prsv = { i:T, j:T, k:, n: }
gen ={ i:T, j:T, k:T, n:T } prsv = { i:, j:, k:, n: }
gen ={ i:T, j:T, k:T, n:T } prsv = { i:, j:, k:, n: }
gen ={ i:T, j:, k:T, n:T } prsv ={ i:, j:T, k:, n:}
gen ={ i:T, j:T, k:T, n:T } prsv = { i:, j:, k:, n: }
IN ={ i:T, j:T, k:T, n:T }
![Page 173: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/173.jpg)
173
i = 1
j = 2
k = false
gen = { i:1, j:2, k:false, n:T }
prsv = { i:T, j:T, k:T, n: }IN = { i:T, j:T, k:T, n:T }
![Page 174: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/174.jpg)
174
i = 1
j = 2
k = false
gen = { i:1, j:2, k:false, n:T }
prsv = { i:T, j:T, k:T, n: }IN = { i:T, j:T, k:T, n:T }
OUT = gen (IN resv)
= not a constant
T = undefined
false true …. -2 -1 0 1 2 3 4 ….
![Page 175: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/175.jpg)
175
i = 1
j = 2
k = false
gen = { i:1, j:2, k:false, n:T }
prsv = { i:T, j:T, k:T, n: }IN = { i:T, j:T, k:T, n:T }
OUT = gen (IN resv)IN = { i:1, j:2, k:false, n:T }
= not a constant
T = undefined
false true …. -2 -1 0 1 2 3 4 ….
![Page 176: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/176.jpg)
176
i = 1 j = 2k = false
i = 3 j = 2
print j j = j + 1
k
exit
i < n
gen ={ i:1, j:2, k:false, n:T } prsv = { i:T, j:T, k:T, n: }
gen ={ i:T, j:T, k:T, n:T } prsv = { i:, j:, k:, n: }
gen ={ i:3, j:2, k:T, n:T } prsv = { i:T, j:T, k:, n: }
gen ={ i:T, j:T, k:T, n:T } prsv = { i:, j:, k:, n: }
gen ={ i:T, j:T, k:T, n:T } prsv = { i:, j:, k:, n: }
gen ={ i:T, j:, k:T, n:T } prsv ={ i:, j:T, k:, n:}
gen ={ i:T, j:T, k:T, n:T } prsv = { i:, j:, k:, n: }
IN ={ i:T, j:T, k:T, n:T }
OUT ={ i:T, j:T, k:T, n:T }
OUT ={i:1, j:2, k:false, n:T }
![Page 177: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/177.jpg)
177
i = 1 j = 2k = false
i = 3 j = 2
print j j = j + 1
k
exit
i < n
gen ={ i:1, j:2, k:false, n:T } prsv = { i:T, j:T, k:T, n: }
gen ={ i:T, j:T, k:T, n:T } prsv = { i:, j:, k:, n: }
gen ={ i:3, j:2, k:T, n:T } prsv = { i:T, j:T, k:, n: }
gen ={ i:T, j:T, k:T, n:T } prsv = { i:, j:, k:, n: }
gen ={ i:T, j:T, k:T, n:T } prsv = { i:, j:, k:, n: }
gen ={ i:T, j:, k:T, n:T } prsv ={ i:, j:T, k:, n:}
gen ={ i:T, j:T, k:T, n:T } prsv = { i:, j:, k:, n: }
IN ={ i:T, j:T, k:T, n:T }
OUT ={ i:T, j:T, k:T, n:T }
OUT ={i:1, j:2, k:false, n:T }
![Page 178: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/178.jpg)
178
i < n
out1 = { i:T, j:T, k:T, n:T }out2 = { i:1, j:2, k:false, n:T } IN = out1 out2
= not a constant
T = undefined
false true …. -2 -1 0 1 2 3 4 ….
![Page 179: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/179.jpg)
179
i < n
out1 = { i:T, j:T, k:T, n:T }out2 = { i:1, j:2, k:false, n:T } IN = out1 out2IN = { i:1, j:2, k:false, n:T }
= not a constant
T = undefined
false true …. -2 -1 0 1 2 3 4 ….
![Page 180: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/180.jpg)
180
i = 1 j = 2k = false
i = 3 j = 2
print j j = j + 1
k
exit
i < n
gen ={ i:1, j:2, k:false, n:T } prsv = { i:T, j:T, k:T, n: }
gen ={ i:T, j:T, k:T, n:T } prsv = { i:, j:, k:, n: }
gen ={ i:3, j:2, k:T, n:T } prsv = { i:T, j:T, k:, n: }
gen ={ i:T, j:T, k:T, n:T } prsv = { i:, j:, k:, n: }
gen ={ i:T, j:T, k:T, n:T } prsv = { i:, j:, k:, n: }
gen ={ i:T, j:, k:T, n:T } prsv ={ i:, j:T, k:, n:}
gen ={ i:T, j:T, k:T, n:T } prsv = { i:, j:, k:, n: }
IN ={ i:T, j:T, k:T, n:T }
OUT ={ i:T, j:T, k:T, n:T }
OUT ={i:1, j:2, k:false, n:T } IN ={i:1, j:2, k:false, n:T }
![Page 181: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/181.jpg)
181
i = 1 j = 2k = false
i = 3 j = 2
print j j = j + 1
k
exit
i < n
gen ={ i:1, j:2, k:false, n:T } prsv = { i:T, j:T, k:T, n: }
gen ={ i:T, j:T, k:T, n:T } prsv = { i:, j:, k:, n: }
gen ={ i:3, j:2, k:T, n:T } prsv = { i:T, j:T, k:, n: }
gen ={ i:T, j:T, k:T, n:T } prsv = { i:, j:, k:, n: }
gen ={ i:T, j:T, k:T, n:T } prsv = { i:, j:, k:, n: }
gen ={ i:T, j:, k:T, n:T } prsv ={ i:, j:T, k:, n:}
gen ={ i:T, j:T, k:T, n:T } prsv = { i:, j:, k:, n: }
IN ={ i:T, j:T, k:T, n:T }
OUT ={ i:T, j:T, k:T, n:T }
OUT ={i:1, j:2, k:false, n:T } IN ={i:1, j:2, k:false, n:T }
OUT ={i:1, j:2, k:false, n:T }
![Page 182: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/182.jpg)
182
i = 1 j = 2k = false
i = 3 j = 2
print j j = j + 1
k
exit
i < n
gen ={ i:1, j:2, k:false, n:T } prsv = { i:T, j:T, k:T, n: }
gen ={ i:T, j:T, k:T, n:T } prsv = { i:, j:, k:, n: }
gen ={ i:3, j:2, k:T, n:T } prsv = { i:T, j:T, k:, n: }
gen ={ i:T, j:T, k:T, n:T } prsv = { i:, j:, k:, n: }
gen ={ i:T, j:T, k:T, n:T } prsv = { i:, j:, k:, n: }
gen ={ i:T, j:, k:T, n:T } prsv ={ i:, j:T, k:, n:}
gen ={ i:T, j:T, k:T, n:T } prsv = { i:, j:, k:, n: }
IN ={ i:T, j:T, k:T, n:T }
OUT ={ i:T, j:T, k:T, n:T }
OUT ={i:1, j:2, k:false, n:T } IN ={i:1, j:2, k:false, n:T }
OUT ={i:1, j:2, k:false, n:T }
![Page 183: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/183.jpg)
183
i = 1 j = 2k = false
i = 3 j = 2
print j j = j + 1
k
exit
i < n
gen ={ i:1, j:2, k:false, n:T } prsv = { i:T, j:T, k:T, n: }
gen ={ i:T, j:T, k:T, n:T } prsv = { i:, j:, k:, n: }
gen ={ i:3, j:2, k:T, n:T } prsv = { i:T, j:T, k:, n: }
gen ={ i:T, j:T, k:T, n:T } prsv = { i:, j:, k:, n: }
gen ={ i:T, j:T, k:T, n:T } prsv = { i:, j:, k:, n: }
gen ={ i:T, j:, k:T, n:T } prsv ={ i:, j:T, k:, n:}
gen ={ i:T, j:T, k:T, n:T } prsv = { i:, j:, k:, n: }
IN ={ i:T, j:T, k:T, n:T }
OUT ={ i:T, j:T, k:T, n:T }
OUT ={i:1, j:2, k:false, n:T } IN ={i:1, j:2, k:false, n:T }
IN ={i:1, j:2, k:false, n:T }
OUT ={i:1, j:2, k:false, n:T }
![Page 184: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/184.jpg)
184
i = 3
j = 2
gen = { i:3, j:2, k:T, n:T }
prsv = { i:T, j:T, k:, n: }IN = { i:1, j:2, k:false, n:T }
OUT = gen (IN resv)
= not a constant
T = undefined
false true …. -2 -1 0 1 2 3 4 ….
![Page 185: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/185.jpg)
185
i = 3
j = 2
gen = { i:3, j:2, k:T, n:T }
prsv = { i:T, j:T, k:, n: }IN = { i:1, j:2, k:false, n:T }
OUT = gen (IN resv)IN = { i:3, j:2, k:false, n:T }
= not a constant
T = undefined
false true …. -2 -1 0 1 2 3 4 ….
![Page 186: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/186.jpg)
186
i = 1 j = 2k = false
i = 3 j = 2
print j j = j + 1
k
exit
i < n
gen ={ i:1, j:2, k:false, n:T } prsv = { i:T, j:T, k:T, n: }
gen ={ i:T, j:T, k:T, n:T } prsv = { i:, j:, k:, n: }
gen ={ i:3, j:2, k:T, n:T } prsv = { i:T, j:T, k:, n: }
gen ={ i:T, j:T, k:T, n:T } prsv = { i:, j:, k:, n: }
gen ={ i:T, j:T, k:T, n:T } prsv = { i:, j:, k:, n: }
gen ={ i:T, j:, k:T, n:T } prsv ={ i:, j:T, k:, n:}
gen ={ i:T, j:T, k:T, n:T } prsv = { i:, j:, k:, n: }
IN ={ i:T, j:T, k:T, n:T }
OUT ={i:3, j:2, k:false, n:T }
OUT ={i:1, j:2, k:false, n:T } IN ={i:1, j:2, k:false, n:T }
IN ={i:1, j:2, k:false, n:T }
OUT ={i:1, j:2, k:false, n:T }
![Page 187: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/187.jpg)
187
i = 1 j = 2k = false
i = 3 j = 2
print j j = j + 1
k
exit
i < n
gen ={ i:1, j:2, k:false, n:T } prsv = { i:T, j:T, k:T, n: }
gen ={ i:T, j:T, k:T, n:T } prsv = { i:, j:, k:, n: }
gen ={ i:3, j:2, k:T, n:T } prsv = { i:T, j:T, k:, n: }
gen ={ i:T, j:T, k:T, n:T } prsv = { i:, j:, k:, n: }
gen ={ i:T, j:T, k:T, n:T } prsv = { i:, j:, k:, n: }
gen ={ i:T, j:, k:T, n:T } prsv ={ i:, j:T, k:, n:}
gen ={ i:T, j:T, k:T, n:T } prsv = { i:, j:, k:, n: }
IN ={ i:T, j:T, k:T, n:T }
OUT ={i:3, j:2, k:false, n:T }
OUT ={i:1, j:2, k:false, n:T } IN ={i:1, j:2, k:false, n:T }
IN ={i:1, j:2, k:false, n:T }
OUT ={i:1, j:2, k:false, n:T }
![Page 188: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/188.jpg)
188
i < n
out1 = { i:1, j:2, k:false, n:T }out2 = { i:3, j:2, k:false, n:T } IN = out1 out2
= not a constant
T = undefined
false true …. -2 -1 0 1 2 3 4 ….
![Page 189: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/189.jpg)
189
i < n
out1 = { i:1, j:2, k:false, n:T }out2 = { i:3, j:2, k:false, n:T } IN = out1 out2IN = { i:, j:2, k:false, n:T }
= not a constant
T = undefined
false true …. -2 -1 0 1 2 3 4 ….
![Page 190: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/190.jpg)
190
i = 1 j = 2k = false
i = 3 j = 2
print j j = j + 1
k
exit
i < n
gen ={ i:1, j:2, k:false, n:T } prsv = { i:T, j:T, k:T, n: }
gen ={ i:T, j:T, k:T, n:T } prsv = { i:, j:, k:, n: }
gen ={ i:3, j:2, k:T, n:T } prsv = { i:T, j:T, k:, n: }
gen ={ i:T, j:T, k:T, n:T } prsv = { i:, j:, k:, n: }
gen ={ i:T, j:T, k:T, n:T } prsv = { i:, j:, k:, n: }
gen ={ i:T, j:, k:T, n:T } prsv ={ i:, j:T, k:, n:}
gen ={ i:T, j:T, k:T, n:T } prsv = { i:, j:, k:, n: }
IN ={ i:T, j:T, k:T, n:T }
OUT ={i:3, j:2, k:false, n:T }
OUT ={i:1, j:2, k:false, n:T } IN ={i:, j:2, k:false, n:T }
IN ={i:1, j:2, k:false, n:T }
OUT ={i:, j:2, k:false, n:T }
![Page 191: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/191.jpg)
191
i = 1 j = 2k = false
i = 3 j = 2
print j j = j + 1
k
exit
i < n
gen ={ i:1, j:2, k:false, n:T } prsv = { i:T, j:T, k:T, n: }
gen ={ i:T, j:T, k:T, n:T } prsv = { i:, j:, k:, n: }
gen ={ i:3, j:2, k:T, n:T } prsv = { i:T, j:T, k:, n: }
gen ={ i:T, j:T, k:T, n:T } prsv = { i:, j:, k:, n: }
gen ={ i:T, j:T, k:T, n:T } prsv = { i:, j:, k:, n: }
gen ={ i:T, j:, k:T, n:T } prsv ={ i:, j:T, k:, n:}
gen ={ i:T, j:T, k:T, n:T } prsv = { i:, j:, k:, n: }
IN ={ i:T, j:T, k:T, n:T }
OUT ={i:3, j:2, k:false, n:T }
OUT ={i:1, j:2, k:false, n:T }
IN ={i:1, j:2, k:false, n:T }
OUT ={i:, j:2, k:false, n:T } IN ={i:, j:2, k:false, n:T }
IN ={i:, j:2, k:false, n:T }
![Page 192: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/192.jpg)
192
i = 1 j = 2k = false
i = 3 j = 2
print j j = j + 1
k
exit
i < n
gen ={ i:1, j:2, k:false, n:T } prsv = { i:T, j:T, k:T, n: }
gen ={ i:T, j:T, k:T, n:T } prsv = { i:, j:, k:, n: }
gen ={ i:3, j:2, k:T, n:T } prsv = { i:T, j:T, k:, n: }
gen ={ i:T, j:T, k:T, n:T } prsv = { i:, j:, k:, n: }
gen ={ i:T, j:T, k:T, n:T } prsv = { i:, j:, k:, n: }
gen ={ i:T, j:, k:T, n:T } prsv ={ i:, j:T, k:, n:}
gen ={ i:T, j:T, k:T, n:T } prsv = { i:, j:, k:, n: }
IN ={ i:T, j:T, k:T, n:T }
OUT ={i:3, j:2, k:false, n:T }
OUT ={i:1, j:2, k:false, n:T }
IN ={i:1, j:2, k:false, n:T }
OUT ={i:, j:2, k:false, n:T } IN ={i:, j:2, k:false, n:T }
OUT ={i:, j:2, k:false, n:T }
IN ={i:, j:2, k:false, n:T }
![Page 193: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/193.jpg)
193
i = 1 j = 2k = false
i = 3 j = 2
print j j = j + 1
k
exit
i < n
gen ={ i:1, j:2, k:false, n:T } prsv = { i:T, j:T, k:T, n: }
gen ={ i:T, j:T, k:T, n:T } prsv = { i:, j:, k:, n: }
gen ={ i:3, j:2, k:T, n:T } prsv = { i:T, j:T, k:, n: }
gen ={ i:T, j:T, k:T, n:T } prsv = { i:, j:, k:, n: }
gen ={ i:T, j:T, k:T, n:T } prsv = { i:, j:, k:, n: }
gen ={ i:T, j:, k:T, n:T } prsv ={ i:, j:T, k:, n:}
gen ={ i:T, j:T, k:T, n:T } prsv = { i:, j:, k:, n: }
IN ={ i:T, j:T, k:T, n:T }
OUT ={i:3, j:2, k:false, n:T }
OUT ={i:1, j:2, k:false, n:T }
IN ={i:1, j:2, k:false, n:T }
OUT ={i:, j:2, k:false, n:T } IN ={i:, j:2, k:false, n:T }
OUT ={i:, j:2, k:false, n:T }
IN ={i:, j:2, k:false, n:T }
![Page 194: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/194.jpg)
194
i = 1 j = 2k = false
i = 3 j = 2
print j j = j + 1
k
exit
i < n
gen ={ i:1, j:2, k:false, n:T } prsv = { i:T, j:T, k:T, n: }
gen ={ i:T, j:T, k:T, n:T } prsv = { i:, j:, k:, n: }
gen ={ i:3, j:2, k:T, n:T } prsv = { i:T, j:T, k:, n: }
gen ={ i:T, j:T, k:T, n:T } prsv = { i:, j:, k:, n: }
gen ={ i:T, j:T, k:T, n:T } prsv = { i:, j:, k:, n: }
gen ={ i:T, j:, k:T, n:T } prsv ={ i:, j:T, k:, n:}
gen ={ i:T, j:T, k:T, n:T } prsv = { i:, j:, k:, n: }
IN ={ i:T, j:T, k:T, n:T }
OUT ={i:3, j:2, k:false, n:T }
OUT ={i:1, j:2, k:false, n:T }
IN ={i:1, j:2, k:false, n:T }
OUT ={i:, j:2, k:false, n:T } IN ={i:, j:2, k:false, n:T }
OUT ={i:, j:2, k:false, n:T }
IN ={i:, j:2, k:false, n:T }
IN ={i:, j:2, k:false, n:T }
![Page 195: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/195.jpg)
195
i = 1 j = 2k = false
i = 3 j = 2
print j j = j + 1
k
exit
i < n
gen ={ i:1, j:2, k:false, n:T } prsv = { i:T, j:T, k:T, n: }
gen ={ i:T, j:T, k:T, n:T } prsv = { i:, j:, k:, n: }
gen ={ i:3, j:2, k:T, n:T } prsv = { i:T, j:T, k:, n: }
gen ={ i:T, j:T, k:T, n:T } prsv = { i:, j:, k:, n: }
gen ={ i:T, j:T, k:T, n:T } prsv = { i:, j:, k:, n: }
gen ={ i:T, j:, k:T, n:T } prsv ={ i:, j:T, k:, n:}
gen ={ i:T, j:T, k:T, n:T } prsv = { i:, j:, k:, n: }
IN ={ i:T, j:T, k:T, n:T }
OUT ={i:3, j:2, k:false, n:T }
OUT ={i:1, j:2, k:false, n:T }
IN ={i:1, j:2, k:false, n:T }
OUT ={i:, j:2, k:false, n:T } IN ={i:, j:2, k:false, n:T }
OUT ={i:, j:2, k:false, n:T }
IN ={i:, j:2, k:false, n:T }
OUT ={i:, j:2, k:false, n:T }
IN ={i:, j:2, k:false, n:T }
![Page 196: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/196.jpg)
196
i = 1 j = 2k = false
i = 3 j = 2
print j j = j + 1
k
exit
i < n
gen ={ i:1, j:2, k:false, n:T } prsv = { i:T, j:T, k:T, n: }
gen ={ i:T, j:T, k:T, n:T } prsv = { i:, j:, k:, n: }
gen ={ i:3, j:2, k:T, n:T } prsv = { i:T, j:T, k:, n: }
gen ={ i:T, j:T, k:T, n:T } prsv = { i:, j:, k:, n: }
gen ={ i:T, j:T, k:T, n:T } prsv = { i:, j:, k:, n: }
gen ={ i:T, j:, k:T, n:T } prsv ={ i:, j:T, k:, n:}
gen ={ i:T, j:T, k:T, n:T } prsv = { i:, j:, k:, n: }
IN ={ i:T, j:T, k:T, n:T }
OUT ={i:3, j:2, k:false, n:T }
OUT ={i:1, j:2, k:false, n:T }
IN ={i:1, j:2, k:false, n:T }
OUT ={i:, j:2, k:false, n:T } IN ={i:, j:2, k:false, n:T }
OUT ={i:, j:2, k:false, n:T }
IN ={i:, j:2, k:false, n:T }
OUT ={i:, j:2, k:false, n:T }
IN ={i:, j:2, k:false, n:T }
![Page 197: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/197.jpg)
197
i = 1 j = 2k = false
i = 3 j = 2
print j j = j + 1
k
exit
i < n
gen ={ i:1, j:2, k:false, n:T } prsv = { i:T, j:T, k:T, n: }
gen ={ i:T, j:T, k:T, n:T } prsv = { i:, j:, k:, n: }
gen ={ i:3, j:2, k:T, n:T } prsv = { i:T, j:T, k:, n: }
gen ={ i:T, j:T, k:T, n:T } prsv = { i:, j:, k:, n: }
gen ={ i:T, j:T, k:T, n:T } prsv = { i:, j:, k:, n: }
gen ={ i:T, j:, k:T, n:T } prsv ={ i:, j:T, k:, n:}
gen ={ i:T, j:T, k:T, n:T } prsv = { i:, j:, k:, n: }
IN ={ i:T, j:T, k:T, n:T }
OUT ={i:3, j:2, k:false, n:T }
OUT ={i:1, j:2, k:false, n:T }
IN ={i:1, j:2, k:false, n:T }
OUT ={i:, j:2, k:false, n:T } IN ={i:, j:2, k:false, n:T }
OUT ={i:, j:2, k:false, n:T }
IN ={i:, j:2, k:false, n:T }
OUT ={i:, j:2, k:false, n:T }
IN ={i:, j:2, k:false, n:T }
IN ={i:, j:2, k:false, n:T }
![Page 198: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/198.jpg)
198
j = j + 1
gen = { i:T, j:, k:T, n:T }
prsv = { i:, j:T, k:, n: }IN = { i:, j:2, k:false, n:T }
OUT = gen (IN resv)
= not a constant
T = undefined
false true …. -2 -1 0 1 2 3 4 ….
![Page 199: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/199.jpg)
199
j = j + 1
gen = { i:T, j:, k:T, n:T }
prsv = { i:, j:T, k:, n: }IN = { i:, j:2, k:false, n:T }
OUT = gen (IN resv)IN = { i:, j:, k:false, n:T }
= not a constant
T = undefined
false true …. -2 -1 0 1 2 3 4 ….
![Page 200: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/200.jpg)
200
i = 1 j = 2k = false
i = 3 j = 2
print j j = j + 1
k
exit
i < n
gen ={ i:1, j:2, k:false, n:T } prsv = { i:T, j:T, k:T, n: }
gen ={ i:T, j:T, k:T, n:T } prsv = { i:, j:, k:, n: }
gen ={ i:3, j:2, k:T, n:T } prsv = { i:T, j:T, k:, n: }
gen ={ i:T, j:T, k:T, n:T } prsv = { i:, j:, k:, n: }
gen ={ i:T, j:T, k:T, n:T } prsv = { i:, j:, k:, n: }
gen ={ i:T, j:, k:T, n:T } prsv ={ i:, j:T, k:, n:}
gen ={ i:T, j:T, k:T, n:T } prsv = { i:, j:, k:, n: }
IN ={ i:T, j:T, k:T, n:T }
OUT ={i:3, j:2, k:false, n:T }
OUT ={i:1, j:2, k:false, n:T }
IN ={i:1, j:2, k:false, n:T }
OUT ={i:, j:2, k:false, n:T } IN ={i:, j:2, k:false, n:T }
OUT ={i:, j:2, k:false, n:T }
IN ={i:, j:2, k:false, n:T }
OUT ={i:, j:2, k:false, n:T }
IN ={i:, j:2, k:false, n:T }
OUT ={i:, j:, k:false, n:T }
IN ={i:, j:2, k:false, n:T }
![Page 201: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/201.jpg)
201
i = 1 j = 2k = false
i = 3 j = 2
print j j = j + 1
k
exit
i < n
gen ={ i:1, j:2, k:false, n:T } prsv = { i:T, j:T, k:T, n: }
gen ={ i:T, j:T, k:T, n:T } prsv = { i:, j:, k:, n: }
gen ={ i:3, j:2, k:T, n:T } prsv = { i:T, j:T, k:, n: }
gen ={ i:T, j:T, k:T, n:T } prsv = { i:, j:, k:, n: }
gen ={ i:T, j:T, k:T, n:T } prsv = { i:, j:, k:, n: }
gen ={ i:T, j:, k:T, n:T } prsv ={ i:, j:T, k:, n:}
gen ={ i:T, j:T, k:T, n:T } prsv = { i:, j:, k:, n: }
IN ={ i:T, j:T, k:T, n:T }
OUT ={i:3, j:2, k:false, n:T }
OUT ={i:1, j:2, k:false, n:T }
IN ={i:1, j:2, k:false, n:T }
OUT ={i:, j:2, k:false, n:T } IN ={i:, j:2, k:false, n:T }
OUT ={i:, j:2, k:false, n:T }
IN ={i:, j:2, k:false, n:T }
OUT ={i:, j:2, k:false, n:T }
IN ={i:, j:2, k:false, n:T }
OUT ={i:, j:, k:false, n:T }
IN ={i:, j:2, k:false, n:T }
![Page 202: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/202.jpg)
202
exit
out1 = { i:, j:2, k:false, n:T }out2 = { i:, j:, k:false, n:T } IN = out1 out2IN = { i:, j:, k:false, n:T }
= not a constant
T = undefined
false true …. -2 -1 0 1 2 3 4 ….
![Page 203: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/203.jpg)
203
i = 1 j = 2k = false
i = 3 j = 2
print j j = j + 1
k
exit
i < n
gen ={ i:1, j:2, k:false, n:T } prsv = { i:T, j:T, k:T, n: }
gen ={ i:T, j:T, k:T, n:T } prsv = { i:, j:, k:, n: }
gen ={ i:3, j:2, k:T, n:T } prsv = { i:T, j:T, k:, n: }
gen ={ i:T, j:T, k:T, n:T } prsv = { i:, j:, k:, n: }
gen ={ i:T, j:T, k:T, n:T } prsv = { i:, j:, k:, n: }
gen ={ i:T, j:, k:T, n:T } prsv ={ i:, j:T, k:, n:}
gen ={ i:T, j:T, k:T, n:T } prsv = { i:, j:, k:, n: }
IN ={ i:T, j:T, k:T, n:T }
OUT ={i:3, j:2, k:false, n:T }
OUT ={i:1, j:2, k:false, n:T }
IN ={i:1, j:2, k:false, n:T }
OUT ={i:, j:2, k:false, n:T } IN ={i:, j:2, k:false, n:T }
OUT ={i:, j:2, k:false, n:T }
IN ={i:, j:2, k:false, n:T }
OUT ={i:, j:2, k:false, n:T }
IN ={i:, j:2, k:false, n:T }
OUT ={i:, j:, k:false, n:T }
OUT ={i:, j:, k:false, n:T }
IN ={i:, j:2, k:false, n:T }
![Page 204: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/204.jpg)
204
i = 1 j = 2k = false
i = 3 j = 2
print j j = j + 1
k
exit
i < n
gen ={ i:1, j:2, k:false, n:T } prsv = { i:T, j:T, k:T, n: }
gen ={ i:T, j:T, k:T, n:T } prsv = { i:, j:, k:, n: }
gen ={ i:3, j:2, k:T, n:T } prsv = { i:T, j:T, k:, n: }
gen ={ i:T, j:T, k:T, n:T } prsv = { i:, j:, k:, n: }
gen ={ i:T, j:T, k:T, n:T } prsv = { i:, j:, k:, n: }
gen ={ i:T, j:, k:T, n:T } prsv ={ i:, j:T, k:, n:}
gen ={ i:T, j:T, k:T, n:T } prsv = { i:, j:, k:, n: }
IN ={ i:T, j:T, k:T, n:T }
OUT ={i:3, j:2, k:false, n:T }
OUT ={i:1, j:2, k:false, n:T }
IN ={i:1, j:2, k:false, n:T }
OUT ={i:, j:2, k:false, n:T } IN ={i:, j:2, k:false, n:T }
OUT ={i:, j:2, k:false, n:T }
IN ={i:, j:2, k:false, n:T }
OUT ={i:, j:2, k:false, n:T }
IN ={i:, j:2, k:false, n:T }
OUT ={i:, j:, k:false, n:T }
OUT ={i:, j:, k:false, n:T }
IN ={i:, j:2, k:false, n:T }
![Page 205: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/205.jpg)
205
i = 1 j = 2k = false
i = 3 j = 2
print j j = j + 1
k
exit
i < n
IN ={ i:T, j:T, k:T, n:T }
IN ={i:, j:2, k:false, n:T }
IN ={i:1, j:2, k:false, n:T }
IN ={i:, j:2, k:false, n:T }
IN ={i:, j:2, k:false, n:T } IN ={i:, j:2, k:false, n:T }
OUT ={i:, j:, k:false, n:T }
![Page 206: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/206.jpg)
206
i = 1 j = 2k = false
i = 3 j = 2
print j j = j + 1
k
exit
i < n
IN ={ i:T, j:T, k:T, n:T }
IN ={i:1, j:2, k:false, n:T }
IN ={i:1, j:2, k:false, n:T }
IN ={i:, j:2, k:false, n:T }
IN ={i:, j:2, k:false, n:T } IN ={i:, j:2, k:false, n:T }
OUT ={i:, j:, k:false, n:T }
![Page 207: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/207.jpg)
207
i = 1 j = 2k = false
i = 3 j = 2
print j j = j + 1
false
exit
i < n
IN ={ i:T, j:T, k:T, n:T }
IN ={i:1, j:2, k:false, n:T }
IN ={i:1, j:2, k:false, n:T }
IN ={i:, j:2, k:false, n:T }
IN ={i:, j:2, k:false, n:T } IN ={i:, j:2, k:false, n:T }
OUT ={i:, j:, k:false, n:T }
![Page 208: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/208.jpg)
208
i = 1 j = 2k = false
i = 3 j = 2
print j j = j + 1
false
exit
i < n
IN ={ i:T, j:T, k:T, n:T }
IN ={i:1, j:2, k:false, n:T }
IN ={i:1, j:2, k:false, n:T }
IN ={i:, j:2, k:false, n:T }
IN ={i:, j:2, k:false, n:T } IN ={i:, j:2, k:false, n:T }
OUT ={i:, j:, k:false, n:T }
![Page 209: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/209.jpg)
209
i = 1 j = 2k = false
i = 3 j = 2
print 2 j = j + 1
false
exit
i < n
IN ={ i:T, j:T, k:T, n:T }
IN ={i:1, j:2, k:false, n:T }
IN ={i:1, j:2, k:false, n:T }
IN ={i:, j:2, k:false, n:T }
IN ={i:, j:2, k:false, n:T } IN ={i:, j:2, k:false, n:T }
OUT ={i:, j:, k:false, n:T }
![Page 210: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/210.jpg)
210
i = 1 j = 2k = false
i = 3 j = 2
print 2 j = j + 1
false
exit
i < n
IN ={ i:T, j:T, k:T, n:T }
IN ={i:1, j:2, k:false, n:T }
IN ={i:1, j:2, k:false, n:T }
IN ={i:, j:2, k:false, n:T }
IN ={i:, j:2, k:false, n:T } IN ={i:, j:2, k:false, n:T }
OUT ={i:, j:, k:false, n:T }
![Page 211: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/211.jpg)
211
i = 1 j = 2k = false
i = 3 j = 2
print 2 j = j + 1
false
exit
i < n
IN ={ i:T, j:T, k:T, n:T }
IN ={i:1, j:2, k:false, n:T }
IN ={i:1, j:2, k:false, n:T }
IN ={i:, j:2, k:false, n:T }
IN ={i:, j:2, k:false, n:T } IN ={i:, j:2, k:false, n:T }
OUT ={i:, j:, k:false, n:T }
![Page 212: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/212.jpg)
212
i = 1 j = 2k = false
i = 3 j = 2
print 2 j = 2 + 1
false
exit
i < n
IN ={ i:T, j:T, k:T, n:T }
IN ={i:1, j:2, k:false, n:T }
IN ={i:1, j:2, k:false, n:T }
IN ={i:, j:2, k:false, n:T }
IN ={i:, j:2, k:false, n:T } IN ={i:, j:2, k:false, n:T }
OUT ={i:, j:, k:false, n:T }
![Page 213: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/213.jpg)
213
i = 1 j = 2k = false
i = 3 j = 2
print 2 j = 2 + 1
false
exit
i < n
IN ={ i:T, j:T, k:T, n:T }
IN ={i:1, j:2, k:false, n:T }
IN ={i:1, j:2, k:false, n:T }
IN ={i:, j:2, k:false, n:T }
IN ={i:, j:2, k:false, n:T } IN ={i:, j:2, k:false, n:T }
OUT ={i:, j:, k:false, n:T }
![Page 214: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/214.jpg)
214
i = 1 j = 2k = false
i = 3 j = 2
j = 2 + 1
exit
i < n
IN ={ i:T, j:T, k:T, n:T }
IN ={i:1, j:2, k:false, n:T }
IN ={i:1, j:2, k:false, n:T }
IN ={i:, j:2, k:false, n:T }
IN ={i:, j:2, k:false, n:T }
OUT ={i:, j:, k:false, n:T }
![Page 215: Optimizaciones Tradicionales](https://reader034.vdocumento.com/reader034/viewer/2022051402/56815df9550346895dcc32c0/html5/thumbnails/215.jpg)
215
Lecturas
• Ballena– Capítulo 13