Download , - Oscar Bonilla

Compiladores
Optimizaciones Tradicionales
Simplificación Algebraica,
Copy Propagation,
y Constant Propagation
40
Resumen
•
•
•
•
Overview de análisis de control de flujo
Simplificación algebraica
Copy Propagation
Constant Propagation
2
Expresiones Disponibles
• Dominio
– conjunto de expresiones
• Dirección de flujo de datos
• Función de flujo de datos
Hacia adelante
– OUT = gen  (IN - kill)
– gen = { a | a se calcula en el bloque básico }
– kill = { a |  una variable va que es definida en el b.b. }
• Operación Meet
– IN =  OUT
• Valores iniciales
conjunto entero (Top)
3
Cadena DU (Reaching Definitions)
• Dominio
– conjunto de definiciones
• Dirección de flujo de datos
• Función de flujo de datos
Hacia adelante
– 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)
4
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!
5
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
6
40
Resumen
•
•
•
•
Overview de análisis de control de flujo
Simplificación algebraica
Copy Propagation
Constant Propagation
7
Simplificación algebraica
• Aplicar nuestro conocimiento de algebra, teoría
de números, etc para simplificar expresiones
8
Simplificación algebraica
• Aplicar nuestro conocimiento de algebra, teoría de
números, etc para simplificar expresiones
• Ejemplo
–
–
–
–
–
–
–
a+0
a*1
a/1
a*0
0-a
a + (-b)
-(-a)







a
a
a
0
-a
a-b
a
9
Simplificación algebraica
• Aplicar nuestro conocimiento de algebra, teoría
de números, etc para simplificar expresiones
• Ejemplo
–
–
–
–
a
a
a
a
true
false
true
false




a
false
true
a
10
Simplificación algebraica
• Aplicar nuestro conocimiento de algebra, teoría
de números, etc para simplificar expresiones
• Ejemplo
–a^2
–a*2
–a*8
 a*a
 a+a
 a << 3
11
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
12
Utilidad de Simplificación Algebraica
• Reduce el número de instrucciones
• Usa expresiones menos “caras”
• Habilita otras optimizaciones
13
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
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
– Ejemplo
a+b-a
+
-
a
b
15
a
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)
16
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
17
Efectos en la estabilidad numérica
• Algunas simplificaciones algebraicas pueden
producir resultados incorrectos
18
Efectos en la estabilidad numérica
• Algunas simplificaciones algebraicas pueden
producir resultados incorrectos
• Ejemplo
– (a / b)*0 + c
19
Efectos en la estabilidad numérica
• Algunas simplificaciones algebraicas pueden
producir resultados incorrectos
• Ejemplo
– (a / b)*0 + c
– Podemos simplificar esto a c
20
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
21
40
Resumen
•
•
•
•
Overview de análisis de control de flujo
Simplificación algebraica
Copy Propagation
Constant Propagation
22
Copy Propagation
• Eliminar copias múltiples
– propagar el valor directamente a su uso
• Ejemplo
a
d
e
f
=
=
=
=
b + c
a
d
d + 2*e + c
23
Copy Propagation
• Eliminar copias múltiples
– propagar el valor directamente a su uso
• Ejemplo
a
d
e
f
=
=
=
=
b + c
a
d
d + 2*e + c
24
Copy Propagation
• Eliminar copias múltiples
– propagar el valor directamente a su uso
• Ejemplo
a
d
e
f
=
=
=
=
b + c
a
a
d + 2*e + c
25
Copy Propagation
• Eliminar copias múltiples
– propagar el valor directamente a su uso
• Ejemplo
a
d
e
f
=
=
=
=
b + c
a
a
d + 2*e + c
26
Copy Propagation
• Eliminar copias múltiples
– propagar el valor directamente a su uso
• Ejemplo
a
d
e
f
=
=
=
=
b + c
a
a
a + 2*e + c
27
Copy Propagation
• Eliminar copias múltiples
– propagar el valor directamente a su uso
• Ejemplo
a
d
e
f
=
=
=
=
b + c
a
a
a + 2*e + c
28
Copy Propagation
• Eliminar copias múltiples
– propagar el valor directamente a su uso
• Ejemplo
a
d
e
f
=
=
=
=
b + c
a
a
a + 2*a + c
29
Copy Propagation
• Eliminar copias múltiples
– propagar el valor directamente a su uso
• Ejemplo
a
d
e
f
=
=
=
=
b + c
a
a
a + 2*a + c
30
Oportunidades para Copy
Propagation
• En código del usuario
• Después de otras optimizaciones
– Ejemplo: Simplificación algebraica
31
Ventajas de Copy Propagation
• Lleva a más simplificaciones algebraicas
32
Ventajas de Copy Propagation
• Lleva a más simplificaciones algebraicas
• Ejemplo
a
d
e
f
=
=
=
=
b + c
a
a
a + 2*a + c
33
Ventajas de Copy Propagation
• Lleva a más simplificaciones algebraicas
• Ejemplo
a
d
e
f
=
=
=
=
b + c
a
a
a + 2*a + c
34
Ventajas de Copy Propagation
• Lleva a más simplificaciones algebraicas
• Ejemplo
a
d
e
f
=
=
=
=
b + c
a
a
3*a + c
35
Ventajas de Copy Propagation
• Reduce instrucciones al eliminar ops de copia
– Crea código muerto que puede ser eliminado
36
Ventajas de Copy Propagation
• Reduce instrucciones al eliminar ops de copia
– Crea código muerto que puede ser eliminado
• Ejemplo
a
d
e
f
=
=
=
=
b + c
a
a
3*a + c
37
Ventajas de Copy Propagation
• Reduce instrucciones al eliminar ops de copia
– Crea código muerto que puede ser eliminado
• Ejemplo
a = b + c
f = 3*a + c
38
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)
39
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!
40
Problema de Data-Flow para
Copy Propagation
• Dominio
– Conjunto de tuplas <v,u> representando un statement v = u
• Dirección de flujo de datos
• Función de flujo de datos
Hacia adelante
– 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)
41
Ejemplo
b=a
c=b+1
d=b
b=d+c
b=d
42
gen = { <v,u> | v = u es el statement }
kill = { <v,u> | LHS var. del stmt. es v ó u }
b=a
c=b+1
d=b
b=d+c
b=d
43
gen = { <v,u> | v = u es el statement }
kill = { <v,u> | LHS var. del stmt. es v ó u }
b=a
c=b+1
d=b
b=d+c
b=d
gen = { <b,a> }
gen = { }
gen = { <d,b> }
gen = { }
gen = { <b,d> }
44
gen = { <v,u> | v = u es el statement }
kill = { <v,u> | LHS var. del stmt. es v ó u }
b=a
gen = { <b,a> }
kill = { <d,b>, <b,d> }
gen = { }
c = b + 1 kill = { }
d=b
gen = { <d,b> }
kill = { <b,d> }
gen = { }
b = d + c kill = { <b,a> <d,b>, <b,d> }
b=d
gen = { <b,d> }
kill = { <b,a>, <d,b> }
45
OUT = gen  (IN - kill)
b=a
gen = { <b,a> }
kill = { <d,b>, <b,d> }
gen = { }
c = b + 1 kill = { }
d=b
gen = { <d,b> }
kill = { <b,d> }
gen = { }
b = d + c kill = { <b,a> <d,b>, <b,d> }
b=d
gen = { <b,d> }
kill = { <b,a>, <d,b> }
46
OUT = gen  (IN - kill)
b=a
gen = { <b,a> }
kill = { <d,b>, <b,d> }
IN = { }
OUT = { <b,a> }
gen = { }
c = b + 1 kill = { }
d=b
gen = { <d,b> }
kill = { <b,d> }
gen = { }
b = d + c kill = { <b,a> <d,b>, <b,d> }
b=d
gen = { <b,d> }
kill = { <b,a>, <d,b> }
47
OUT = gen  (IN - kill)
b=a
gen = { <b,a> }
kill = { <d,b>, <b,d> }
IN = { }
IN = { <b,a> }
gen = { }
c = b + 1 kill = { }
OUT = { <b,a> }
d=b
gen = { <d,b> }
kill = { <b,d> }
gen = { }
b = d + c kill = { <b,a> <d,b>, <b,d> }
b=d
gen = { <b,d> }
kill = { <b,a>, <d,b> }
48
OUT = gen  (IN - kill)
b=a
gen = { <b,a> }
kill = { <d,b>, <b,d> }
IN = { }
IN = { <b,a> }
gen = { }
c = b + 1 kill = { }
IN = { <b,a> }
d=b
gen = { <d,b> }
kill = { <b,d> }
OUT = { <b,a>, <d,b> }
gen = { }
b = d + c kill = { <b,a> <d,b>, <b,d> }
b=d
gen = { <b,d> }
kill = { <b,a>, <d,b> }
49
OUT = gen  (IN - kill)
b=a
gen = { <b,a> }
kill = { <d,b>, <b,d> }
IN = { }
IN = { <b,a> }
gen = { }
c = b + 1 kill = { }
IN = { <b,a> }
d=b
gen = { <d,b> }
kill = { <b,d> }
IN = { <b,a>, <d,b> }
gen = { }
b = d + c kill = { <b,a> <d,b>, <b,d> }
OUT = { }
b=d
gen = { <b,d> }
kill = { <b,a>, <d,b> }
50
OUT = gen  (IN - kill)
b=a
gen = { <b,a> }
kill = { <d,b>, <b,d> }
IN = { }
IN = { <b,a> }
gen = { }
c = b + 1 kill = { }
IN = { <b,a> }
d=b
gen = { <d,b> }
kill = { <b,d> }
IN = { <b,a>, <d,b> }
gen = { }
b = d + c kill = { <b,a> <d,b>, <b,d> }
IN = { }
b=d
gen = { <b,d> }
kill = { <b,a>, <d,b> }
51
OUT = { <b,d> }
OUT = gen  (IN - kill)
b=a
gen = { <b,a> }
kill = { <d,b>, <b,d> }
{ }
{ <b,a> }
gen = { }
c = b + 1 kill = { }
{ <b,a> }
d=b
gen = { <d,b> }
kill = { <b,d> }
{ <b,a>, <d,b> }
gen = { }
b = d + c kill = { <b,a> <d,b>, <b,d> }
{ }
b=d
gen = { <b,d> }
kill = { <b,a>, <d,b> }
52
{ <b,d> }
Ejemplo
b=a
gen = { <b,a> }
kill = { <d,b>, <b,d> }
{ }
{ <b,a> }
gen = { }
c = b + 1 kill = { }
{ <b,a> }
d=b
gen = { <d,b> }
kill = { <b,d> }
{ <b,a>, <d,b> }
gen = { }
b = d + c kill = { <b,a> <d,b>, <b,d> }
{ }
b=d
gen = { <b,d> }
kill = { <b,a>, <d,b> }
53
{ <b,d> }
Ejemplo
b=a
gen = { <b,a> }
kill = { <d,b>, <b,d> }
{ }
{ <b,a> }
gen = { }
c = b + 1 kill = { }
{ <b,a> }
d=a
gen = { <d,b> }
kill = { <b,d> }
{ <b,a>, <d,b> }
gen = { }
b = d + c kill = { <b,a> <d,b>, <b,d> }
{ }
b=d
gen = { <b,d> }
kill = { <b,a>, <d,b> }
54
{ <b,d> }
Ejemplo
b=a
gen = { <b,a> }
kill = { <d,b>, <b,d> }
{ }
{ <b,a> }
gen = { }
c = b + 1 kill = { }
{ <b,a> }
d=a
gen = { <d,b> }
kill = { <b,d> }
{ <b,a>, <d,b> }
gen = { }
b = d + c kill = { <b,a> <d,b>, <b,d> }
{ }
b=d
gen = { <b,d> }
kill = { <b,a>, <d,b> }
55
{ <b,d> }
Ejemplo
b=a
gen = { <b,a> }
kill = { <d,b>, <b,d> }
{ }
{ <b,a> }
gen = { }
c = b + 1 kill = { }
{ <b,a> }
d=a
gen = { <d,b> }
kill = { <b,d> }
{ <b,a>, <d,b> }
gen = { }
b = b + c kill = { <b,a> <d,b>, <b,d> }
{ }
b=d
gen = { <b,d> }
kill = { <b,a>, <d,b> }
56
{ <b,d> }
Ejemplo
b=a
gen = { <b,a> }
kill = { <d,b>, <b,d> }
{ }
{ <b,a> }
gen = { }
c = b + 1 kill = { }
{ <b,a> }
d=a
gen = { <d,b> }
kill = { <b,d> }
{ <b,a>, <d,b> }
gen = { }
b = b + c kill = { <b,a> <d,b>, <b,d> }
{ }
b=d
gen = { <b,d> }
kill = { <b,a>, <d,b> }
57
{ <b,d> }
Ejemplo
b=a
c=b+1
d=a
b=b+c
b=d
58
gen = { <v,u> | v = u es el statement }
kill = { <v,u> | LHS var. del stmt. es v ó u }
b=a
c=b+1
d=a
b=b+c
b=d
gen = { <b,a> }
gen = { }
gen = { <d,a> }
gen = { }
gen = { <b,d> }
59
gen = { <v,u> | v = u es el statement }
kill = { <v,u> | LHS var. del stmt. es v ó u }
b=a
gen = { <b,a> }
kill = { <d,a>, <b,d> }
gen = { }
c = b + 1 kill = { }
d=a
gen = { <d,a> }
kill = { <b,d> }
gen = { }
b = b + c kill = { <b,a>, <b,d> }
b=d
gen = { <b,d> }
kill = { <b,a> }
60
OUT = gen  (IN - kill)
b=a
gen = { <b,a> }
kill = { <d,a>, <b,d> }
IN = { }
OUT = { <b,a> }
gen = { }
c = b + 1 kill = { }
d=a
gen = { <d,a> }
kill = { <b,d> }
gen = { }
b = b + c kill = { <b,a>, <b,d> }
b=d
gen = { <b,d> }
kill = { <b,a> }
61
OUT = gen  (IN - kill)
b=a
gen = { <b,a> }
kill = { <d,a>, <b,d> }
IN = { }
IN = { <b,a> }
gen = { }
c = b + 1 kill = { }
OUT = { <b,a> }
d=a
gen = { <d,a> }
kill = { <b,d> }
gen = { }
b = b + c kill = { <b,a>, <b,d> }
b=d
gen = { <b,d> }
kill = { <b,a> }
62
OUT = gen  (IN - kill)
b=a
gen = { <b,a> }
kill = { <d,a>, <b,d> }
IN = { }
IN = { <b,a> }
gen = { }
c = b + 1 kill = { }
IN = { <b,a> }
d=a
gen = { <d,a> }
kill = { <b,d> }
OUT = { <b,a>, <d,a> }
gen = { }
b = b + c kill = { <b,a>, <b,d> }
b=d
gen = { <b,d> }
kill = { <b,a> }
63
OUT = gen  (IN - kill)
b=a
gen = { <b,a> }
kill = { <d,a>, <b,d> }
IN = { }
IN = { <b,a> }
gen = { }
c = b + 1 kill = { }
IN = { <b,a> }
d=a
gen = { <d,a> }
kill = { <b,d> }
IN = { <b,a>, <d,a> }
gen = { }
b = b + c kill = { <b,a>, <b,d> }
OUT = { <d,a> }
b=d
gen = { <b,d> }
kill = { <b,a> }
64
OUT = gen  (IN - kill)
b=a
gen = { <b,a> }
kill = { <d,a>, <b,d> }
IN = { }
IN = { <b,a> }
gen = { }
c = b + 1 kill = { }
IN = { <b,a> }
d=a
gen = { <d,a> }
kill = { <b,d> }
IN = { <b,a>, <d,a> }
gen = { }
b = b + c kill = { <b,a>, <b,d> }
IN = { <d,a> }
b=d
gen = { <b,d> }
kill = { <b,a> }
OUT = {<d,a> ,<b,d> }
65
Ejemplo
b=a
gen = { <b,a> }
kill = { <d,a>, <b,d> }
{ }
{ <b,a> }
gen = { }
c = b + 1 kill = { }
{ <b,a> }
d=a
gen = { <d,a> }
kill = { <b,d> }
{ <b,a>, <d,a> }
gen = { }
b = b + c kill = { <b,a>, <b,d> }
{ <d,a> }
b=d
gen = { <b,d> }
kill = { <b,a> }
{<d,a> ,<b,d> }
66
Ejemplo
b=a
gen = { <b,a> }
kill = { <d,a>, <b,d> }
{ }
{ <b,a> }
gen = { }
c = b + 1 kill = { }
{ <b,a> }
d=a
gen = { <d,a> }
kill = { <b,d> }
{ <b,a>, <d,a> }
gen = { }
b = b + c kill = { <b,a>, <b,d> }
{ <d,a> }
b=d
gen = { <b,d> }
kill = { <b,a> }
{<d,a> ,<b,d> }
67
Ejemplo
b=a
gen = { <b,a> }
kill = { <d,a>, <b,d> }
{ }
{ <b,a> }
gen = { }
c = b + 1 kill = { }
{ <b,a> }
d=a
gen = { <d,a> }
kill = { <b,d> }
{ <b,a>, <d,a> }
gen = { }
b = a + c kill = { <b,a>, <b,d> }
{ <d,a> }
b=d
gen = { <b,d> }
kill = { <b,a> }
{<d,a> ,<b,d> }
68
Ejemplo
b=a
gen = { <b,a> }
kill = { <d,a>, <b,d> }
{ }
{ <b,a> }
gen = { }
c = b + 1 kill = { }
{ <b,a> }
d=a
gen = { <d,a> }
kill = { <b,d> }
{ <b,a>, <d,a> }
gen = { }
b = a + c kill = { <b,a>, <b,d> }
{ <d,a> }
b=d
gen = { <b,d> }
kill = { <b,a> }
{<d,a> ,<b,d> }
69
Ejemplo
b=a
gen = { <b,a> }
kill = { <d,a>, <b,d> }
{ }
{ <b,a> }
gen = { }
c = b + 1 kill = { }
{ <b,a> }
d=a
gen = { <d,a> }
kill = { <b,d> }
{ <b,a>, <d,a> }
gen = { }
b = a + c kill = { <b,a>, <b,d> }
{ <d,a> }
b=a
gen = { <b,d> }
kill = { <b,a> }
{<d,a> ,<b,d> }
70
Ejemplo
b=a
gen = { <b,a> }
kill = { <d,a>, <b,d> }
{ }
{ <b,a> }
gen = { }
c = b + 1 kill = { }
{ <b,a> }
d=a
gen = { <d,a> }
kill = { <b,d> }
{ <b,a>, <d,a> }
gen = { }
b = a + c kill = { <b,a>, <b,d> }
{ <d,a> }
b=a
gen = { <b,d> }
kill = { <b,a> }
{<d,a> ,<b,d> }
71
Ejemplo
b=a
c=b+1
d=a
b=a+c
b=a
72
Otro Ejemplo
a=b+c
p=q+r
d=a
s=p
d=a
a=d+p
73
Otro Ejemplo
gen = { <v,u> | v = u es el statement }
kill = { <v,u> | LHS var. del stmt. es v ó u }
a=b+c
p=q+r
Gen = {<d,a>, <s,p> }
d=a
s=p
Gen = { }
d=a
Gen = {<d,a> }
Gen = { }
a=d+p
74
Otro Ejemplo
gen = { <v,u> | v = u es el statement }
kill = { <v,u> | LHS var. del stmt. es v ó u }
a=b+c
p=q+r
Gen = {<d,a>, <s,p> }
Kill = { }
d=a
s=p
Gen = { }
Kill = {<d,a>, <s,p> }
d=a
Gen = {<d,a> }
Kill = { }
Gen = { }
Kill = {{<d,a> }
a=d+p
75
Otro Ejemplo
IN =  OUT
OUT = gen  (IN - kill)
Gen = {<d,a>, <s,p> }
Kill = { }
a=b+c
p=q+r
d=a
s=p
Gen = { }
Kill = {<d,a>, <s,p> }
d=a
Gen = {<d,a> }
Kill = { }
Gen = { }
Kill = {{<d,a> }
a=d+p
76
Otro Ejemplo
IN =  OUT
IN = { }
OUT = gen  (IN - kill)
a=b+c
p=q+r
Gen = {<d,a>, <s,p> }
Kill = { }
d=a
s=p
Gen = { }
Kill = {<d,a>, <s,p> }
d=a
Gen = {<d,a> }
Kill = { }
Gen = { }
Kill = {{<d,a> }
a=d+p
77
Otro Ejemplo
IN =  OUT
IN = { }
OUT = gen  (IN - kill)
a=b+c
p=q+r
Gen = {<d,a>, <s,p> }
Kill = { }
d=a
s=p
Gen = { }
Kill = {<d,a>, <s,p> }
d=a
Gen = {<d,a> }
Kill = { }
Gen = { }
Kill = {{<d,a> }
a=d+p
78
Otro Ejemplo
IN =  OUT
IN = { }
OUT = gen  (IN - kill)
a=b+c
p=q+r
Gen = { }
Kill = {<d,a>, <s,p> }
OUT = { }
Gen = {<d,a>, <s,p> }
Kill = { }
d=a
s=p
d=a
Gen = {<d,a> }
Kill = { }
Gen = { }
Kill = {{<d,a> }
a=d+p
79
Otro Ejemplo
IN =  OUT
IN = { }
OUT = gen  (IN - kill)
a=b+c
p=q+r
Gen = { }
Kill = {<d,a>, <s,p> }
OUT = { }
IN = { }
Gen = {<d,a>, <s,p> } d = a
Kill = { }
d=a
s=p
Gen = {<d,a> }
Kill = { }
Gen = { }
Kill = {{<d,a> }
a=d+p
80
Otro Ejemplo
IN =  OUT
IN = { }
OUT = gen  (IN - kill)
a=b+c
p=q+r
Gen = { }
Kill = {<d,a>, <s,p> }
OUT = { }
IN = { }
Gen = {<d,a>, <s,p> } d = a
Kill = { }
d=a
s=p
Gen = {<d,a> }
Kill = { }
Gen = { }
Kill = {{<d,a> }
a=d+p
81
Otro Ejemplo
IN =  OUT
IN = { }
OUT = gen  (IN - kill)
a=b+c
p=q+r
Gen = { }
Kill = {<d,a>, <s,p> }
OUT = { }
IN = { }
Gen = {<d,a>, <s,p> } d = a
Kill = { }
d=a
s=p
Gen = {<d,a> }
Kill = { }
OUT = { <d,a>, <s,p> }
Gen = { }
Kill = {{<d,a> }
a=d+p
82
Otro Ejemplo
IN =  OUT
IN = { }
OUT = gen  (IN - kill)
a=b+c
p=q+r
Gen = { }
Kill = {<d,a>, <s,p> }
OUT = { }
IN = { }
Gen = {<d,a>, <s,p> } d = a
Kill = { }
IN = { }
d=a
s=p
Gen = {<d,a> }
Kill = { }
OUT = { <d,a>, <s,p> }
Gen = { }
Kill = {{<d,a> }
a=d+p
83
Otro Ejemplo
IN =  OUT
IN = { }
OUT = gen  (IN - kill)
a=b+c
p=q+r
Gen = { }
Kill = {<d,a>, <s,p> }
OUT = { }
IN = { }
Gen = {<d,a>, <s,p> } d = a
Kill = { }
IN = { }
d=a
s=p
Gen = {<d,a> }
Kill = { }
OUT = { <d,a>, <s,p> }
Gen = { }
Kill = {{<d,a> }
a=d+p
84
Otro Ejemplo
IN =  OUT
IN = { }
OUT = gen  (IN - kill)
a=b+c
p=q+r
Gen = { }
Kill = {<d,a>, <s,p> }
OUT = { }
IN = { }
Gen = {<d,a>, <s,p> } d = a
Kill = { }
IN = { }
Gen = {<d,a> }
Kill = { }
d=a
s=p
OUT = { <d,a>, <s,p> }
OUT = { <d,a> }
Gen = { }
Kill = {{<d,a> }
a=d+p
85
Otro Ejemplo
IN =  OUT
IN = { }
OUT = gen  (IN - kill)
a=b+c
p=q+r
Gen = { }
Kill = {<d,a>, <s,p> }
OUT = { }
IN = { }
Gen = {<d,a>, <s,p> } d = a
Kill = { }
IN = { }
Gen = {<d,a> }
Kill = { }
d=a
s=p
OUT = { <d,a>, <s,p> }
OUT = { <d,a> }
IN = { <d,a> }
Gen = { }
Kill = {{<d,a> }
a=d+p
86
Otro Ejemplo
IN =  OUT
IN = { }
OUT = gen  (IN - kill)
a=b+c
p=q+r
Gen = { }
Kill = {<d,a>, <s,p> }
OUT = { }
IN = { }
Gen = {<d,a>, <s,p> } d = a
Kill = { }
IN = { }
Gen = {<d,a> }
Kill = { }
d=a
s=p
OUT = { <d,a>, <s,p> }
OUT = { <d,a> }
IN = { <d,a> }
Gen = { }
Kill = {{<d,a> }
a=d+p
87
Otro Ejemplo
IN =  OUT
IN = { }
OUT = gen  (IN - kill)
a=b+c
p=q+r
Gen = { }
Kill = {<d,a>, <s,p> }
OUT = { }
IN = { }
Gen = {<d,a>, <s,p> } d = a
Kill = { }
IN = { }
Gen = {<d,a> }
Kill = { }
d=a
s=p
OUT = { <d,a>, <s,p> }
OUT = { <d,a> }
IN = { <d,a> }
Gen = { }
Kill = {{<d,a> }
a=d+p
OUT = { }
88
Otro Ejemplo
IN = { }
a=b+c
p=q+r
OUT = { }
IN = { }
IN = { }
d=a
s=p
d=a
OUT = { <d,a>, <s,p> }
OUT = { <d,a> }
IN = { <d,a> }
a=d+p
OUT = { }
89
Otro Ejemplo
IN = { }
a=b+c
p=q+r
OUT = { }
IN = { }
IN = { }
d=a
s=p
d=a
OUT = { <d,a>, <s,p> }
OUT = { <d,a> }
IN = { <d,a> }
a=d+p
OUT = { }
90
Otro Ejemplo
IN = { }
a=b+c
p=q+r
OUT = { }
IN = { }
IN = { }
d=a
s=p
d=a
OUT = { <d,a>, <s,p> }
OUT = { <d,a> }
IN = { <d,a> }
a=a+p
OUT = { }
91
Otro Ejemplo
IN = { }
a=b+c
p=q+r
OUT = { }
IN = { }
IN = { }
d=a
s=p
d=a
OUT = { <d,a>, <s,p> }
OUT = { <d,a> }
IN = { <d,a> }
a=a+p
OUT = { }
92
Otro Ejemplo
a=b+c
p=q+r
d=a
s=p
d=a
a=a+p
93
40
Resumen
•
•
•
•
Overview de análisis de control de flujo
Simplificación algebraica
Copy Propagation
Constant Propagation
94
Constant Propagation
• Usar valores constantes
– Usar la constante conocida para una variable
95
Constant Propagation
• Usar valores constantes
– Usar la constante conocida para una variable
• Ejemplo
a = 43
b = 4
d = a + 2*b + c
96
Constant Propagation
• Usar valores constantes
– Usar la constante conocida para una variable
• Ejemplo
a = 43
b = 4
d = a + 2*b + c
97
Constant Propagation
• Usar valores constantes
– Usar la constante conocida para una variable
• Ejemplo
a = 43
b = 4
d = 43 + 2*b + c
98
Constant Propagation
• Usar valores constantes
– Usar la constante conocida para una variable
• Ejemplo
a = 43
b = 4
d = a + 2*b + c
99
Constant Propagation
• Usar valores constantes
– Usar la constante conocida para una variable
• Ejemplo
a = 43
b = 4
d = 43 + 2*4 + c
100
Oportunidades para
Constant 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
101
Ventajas de Constant Propagation
• Simplificación del programa
102
Ventajas de Constant Propagation
• Simplificación del programa
• Ejemplo
a = 43
b = 4
d = 43 + 2*4 + c
103
Ventajas de Constant Propagation
• Simplificación del programa
• Ejemplo
a = 43
b = 4
d = 43 + 2*4 + c
104
Ventajas de Constant Propagation
• Simplificación del programa
• Ejemplo
a = 43
b = 4
d = 51 + c
105
Ventajas de Constant Propagation
• Habilita otras optimizaciones
106
Ventajas de Constant Propagation
• Habilita otras optimizaciones
• Ejemplo
a
b
d
e
=
=
=
=
4
8
2*a - b + c
c + d
107
Ventajas de Constant Propagation
• Habilita otras optimizaciones
• Ejemplo
a
b
d
e
=
=
=
=
4
8
2*a - b + c
c + d
108
Ventajas de Constant Propagation
• Habilita otras optimizaciones
• Ejemplo
a
b
d
e
=
=
=
=
4
8
2*4 - b + c
c + d
109
Ventajas de Constant Propagation
• Habilita otras optimizaciones
• Ejemplo
a
b
d
e
=
=
=
=
4
8
2*4 - b + c
c + d
110
Ventajas de Constant Propagation
• Habilita otras optimizaciones
• Ejemplo
a
b
d
e
=
=
=
=
4
8
2*4 - 8 + c
c + d
111
Ventajas de Constant Propagation
• Habilita otras optimizaciones
• Ejemplo
a
b
d
e
=
=
=
=
4
8
2*4 - 8 + c
c + d
112
Ventajas de Constant Propagation
• Habilita otras optimizaciones
• Ejemplo
a
b
d
e
=
=
=
=
4
8
8 - 8 + c
c + d
113
Ventajas de Constant Propagation
• Habilita otras optimizaciones
• Ejemplo
a
b
d
e
=
=
=
=
4
8
8 - 8 + c
c + d
114
Ventajas de Constant Propagation
• Habilita otras optimizaciones
• Ejemplo
a
b
d
e
=
=
=
=
4
8
0 + c
c + d
115
Ventajas de Constant Propagation
• Habilita otras optimizaciones
• Ejemplo
a
b
d
e
=
=
=
=
4
8
0 + c
c + d
116
Ventajas de Constant Propagation
• Habilita otras optimizaciones
• Ejemplo
a
b
d
e
=
=
=
=
4
8
c
c + d
117
Ventajas de Constant Propagation
• Habilita otras optimizaciones
• Ejemplo
a
b
d
e
=
=
=
=
4
8
c
c + d
118
Ventajas de Constant Propagation
• Habilita otras optimizaciones
• Ejemplo
a
b
d
e
=
=
=
=
4
8
c
c + d
119
Ventajas de Constant Propagation
• Habilita otras optimizaciones
• Ejemplo
a
b
d
e
=
=
=
=
4
8
c
c + c
120
Ventajas de Constant Propagation
• Habilita otras optimizaciones
• Ejemplo
a
b
d
e
=
=
=
=
4
8
c
c + c
121
Ventajas de Constant Propagation
• Habilita otras optimizaciones
• Ejemplo
a
b
d
e
=
=
=
=
4
8
c
c + c
122
Ventajas de Constant Propagation
• Habilita otras optimizaciones
• Ejemplo
a
b
d
e
=
=
=
=
4
8
c
2*c
123
Ventajas de Constant Propagation
• Habilita otras optimizaciones
• Ejemplo
a
b
d
e
=
=
=
=
4
8
c
2*c
124
Ventajas de Constant Propagation
• Habilita otras optimizaciones
• Ejemplo
a = 4
b = 8
e = 2*c
125
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
126
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!
127
Valores de dos caminos
a=5
a=5
b = a + 10
128
Valores de dos caminos
a=5
a=k+2
b = a + 10
129
Valores de dos caminos
a=5
a=7
b = a + 10
130
Valores de dos caminos
a=5
a no definida
b = a + 10
131
Valores de dos caminos
a=5
a no definida
b = a + 10
• programa tonto, usa un valor no inicializado
132
Valores de dos caminos
a=5
a no definida
b = a + 10
• programa tonto, usa un valor no inicializado
• semántica de alto nivel que el compilador no entiende
hace que este sea un programa correcto
133
Lattice para Constant Propagation
T = undefined
false true ….
-2
-1
0
1
 = not a constant
134
2
3
4
….
Lattice (repaso)
• Un lattice L consiste de
– un conjunto de valores
– dos operaciones meet(  ) y join (  )
– un valor top (T) y un valor bottom ()
135
Lattice (repaso)
• Ejemplo: el lattice para el problema de reaching
definitions cuándo sólo hay 3 definiciones
T = { d1, d2, d3 }
{ d2, d3 }
{ d1, d2 }
{ d1, d3 }
{ d2 }
{ d1 }
={ }
136
{ d3 }
Operaciones Meet y Join
{ d1, d2 }  { d2, d3 } = ???
T = { d1, d2, d3 }
{ d2, d3 }
{ d1, d2 }
{ d1, d3 }
{ d2 }
{ d1 }
={ }
137
{ d3 }
Operaciones Meet y Join
{ d1, d2 }  { d2, d3 } = ???
T = { d1, d2, d3 }
{ d2, d3 }
{ d1, d2 }
{ d1, d3 }
{ d2 }
{ d1 }
={ }
138
{ d3 }
Operaciones Meet y Join
{ d1, d2 }  { d2, d3 } = ???
T = { d1, d2, d3 }
{ d2, d3 }
{ d1, d2 }
{ d1, d3 }
{ d2 }
{ d1 }
={ }
139
{ d3 }
Operaciones Meet y Join
{ d1, d2 }  { d2, d3 } = { d2 }
T = { d1, d2, d3 }
{ d2, d3 }
{ d1, d2 }
{ d1, d3 }
{ d2 }
{ d1 }
={ }
140
{ d3 }
Operaciones Meet y Join
{ d1, d2 }  { d3 } = ???
T = { d1, d2, d3 }
{ d2, d3 }
{ d1, d2 }
{ d1, d3 }
{ d2 }
{ d1 }
={ }
141
{ d3 }
Operaciones Meet y Join
{ d1, d2 }  { d3 } = ???
T = { d1, d2, d3 }
{ d2, d3 }
{ d1, d2 }
{ d1, d3 }
{ d2 }
{ d1 }
={ }
142
{ d3 }
Operaciones Meet y Join
{ d1, d2 }  { d3 } = ???
T = { d1, d2, d3 }
{ d2, d3 }
{ d1, d2 }
{ d1, d3 }
{ d2 }
{ d1 }
={ }
143
{ d3 }
Operaciones Meet y Join
{ d1, d2 }  { d3 } = ???
T = { d1, d2, d3 }
{ d2, d3 }
{ d1, d2 }
{ d1, d3 }
{ d2 }
{ d1 }
={ }
144
{ d3 }
Operaciones Meet y Join
{ d1, d2 }  { d3 } = { d1, d2, d3 }
T = { d1, d2, d3 }
{ d2, d3 }
{ d1, d2 }
{ d1, d3 }
{ d2 }
{ d1 }
={ }
145
{ d3 }
Lattice para Constant Propagation
T = undefined
false true ….
-2
-1
0
1
 = not a constant
146
2
3
4
….
Operación Meet en el lattice
a=2
a=2
2 2 =
T = undefined
=a
false true ….
-2
-1
0
1
 = not a constant
147
2
3
4
….
Operación Meet en el lattice
a=2
a=2
2 2 =
T = undefined
=a
false true ….
-2
-1
0
1
 = not a constant
148
2
3
4
….
Operación Meet en el lattice
a=2
a=2
2 2 =2
T = undefined
=a
false true ….
-2
-1
0
1
 = not a constant
149
2
3
4
….
Operación Meet en el lattice
a=2
a=0
2 0 =
T = undefined
=a
false true ….
-2
-1
0
1
 = not a constant
150
2
3
4
….
Operación Meet en el lattice
a=2
a=0
2 0 =
T = undefined
=a
false true ….
-2
-1
0
1
 = not a constant
151
2
3
4
….
Operación Meet en el lattice
a=2
a=0
2 0 =
T = undefined
=a
false true ….
-2
-1
0
1
 = not a constant
152
2
3
4
….
Operación Meet en el lattice
a=2
a=0
2  0 = not a constant
T = undefined
=a
false true ….
-2
-1
0
1
 = not a constant
153
2
3
4
….
Operación Meet en el lattice
a=2
undefined
2  undefined =
T = undefined
=a
false true ….
-2
-1
0
1
 = not a constant
154
2
3
4
….
Operación Meet en el lattice
a=2
undefined
2  undefined =
T = undefined
=a
false true ….
-2
-1
0
1
 = not a constant
155
2
3
4
….
Operación Meet en el lattice
a=2
undefined
2  undefined =
T = undefined
=a
false true ….
-2
-1
0
1
 = not a constant
156
2
3
4
….
Operación Meet en el lattice
a=2
undefined
2  undefined = 2
T = undefined
=a
false true ….
-2
-1
0
1
 = not a constant
157
2
3
4
….
Problema de Data-Flow para
Constant Propagation
• Dominio
– Para cada variable un lattice Lv
• Dirección de flujo de datos
• Función de flujo de datos
– OUT = gen  (IN  resv)
158
Hacia adelante
Problema de Data-Flow para
Constant Propagation
• Dominio
– Para cada variable un lattice Lv
• Dirección de flujo de datos
• Función de flujo de datos
Hacia adelante
– OUT = gen  (IN  resv)
T
si v no es LHS
– gen = xv xv = valor si v es LHS & RHS es constante

de otra forma
159
Problema de Data-Flow para
Constant Propagation
• Dominio
– Para cada variable un lattice Lv
• Dirección de flujo de datos
• Función de flujo de datos
Hacia adelante
– OUT = gen  (IN  resv)
T
si v no es LHS
– gen = xv xv = valor si v es LHS & RHS es constante

de otra forma
T
– prsv = xv xv =

si v es el LHS
si v no es el LHS
160
Problema de Data-Flow para
Constant Propagation
• Dominio
– Para cada variable un lattice Lv
• Dirección de flujo de datos
• Función de flujo de datos
Hacia adelante
– OUT = gen  (IN  resv)
T
si v no es LHS
– gen = xv xv = valor si v es LHS & RHS es constante

de otra forma
T
– prsv = xv xv =

• Valores Iniciales
si v es el LHS
si v no es el LHS
T (= undefined)
161
i=1
j=2
k = false
i<n
k
i=3
j=2
print j
j=j+1
exit
162
i=1
j=2
k = false
163
•
T
si v no es LHS
– gen = xv xv = valor si v es LHS & RHS es constante.

de otra forma
T si v es el LHS
– prsv = xv xv =  si v no es el LHS
164
gen ={
•
i:T,
j:T,
T
k:T,
n:T }
si v no es LHS
– gen = xv xv = valor si v es LHS & RHS es constante.

de otra forma
T si v es el LHS
– prsv = xv xv =  si v no es el LHS
165
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
T si v es el LHS
– prsv = xv xv =  si v no es el LHS
166
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
T si v es el LHS
– prsv = xv xv =  si v no es el LHS
167
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
T si v es el LHS
– prsv = xv xv =  si v no es el LHS
168
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
T si v es el LHS
– prsv = xv xv =  si v no es el LHS
169
i=1
j=2
k = false
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: }
i<n
k
i=3
j=2
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 } print j
prsv = { i:, j:, k:, n: }
j=j+1
exit
170
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: }
i=1
j=2
k = false
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: }
i<n
k
i=3
j=2
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 } print j
prsv = { i:, j:, k:, n: }
j=j+1
exit
171
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 }
i=1
gen ={ i:1, j:2, k:false, n:T }
j=2
prsv = { i:T, j:T, k:T, n: }
k = false
gen ={ i:T, j:T, k:T, n:T }
prsv = { i:, j:, k:, n: }
i<n
k
i=3
j=2
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 } print j
prsv = { i:, j:, k:, n: }
j=j+1
exit
172
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: }
i=1
j=2
k = false
gen = { i:1,
j:2,
k:false,
n:T }
prsv = { i:T,
j:T,
k:T,
n: }
IN =
j:T,
k:T,
n:T }
{ i:T,
173
T = undefined
i=1
false
j=2
k = false
true ….
-2
-1
0
1
2
3
4
….
 = not a constant
gen = { i:1,
j:2,
k:false,
n:T }
prsv = { i:T,
j:T,
k:T,
n: }
IN =
j:T,
k:T,
n:T }
{ i:T,
OUT = gen  (IN  resv)
174
T = undefined
i=1
false
j=2
k = false
true ….
-2
-1
0
1
2
3
4
….
 = not a constant
gen = { i:1,
j:2,
k:false,
n:T }
prsv = { i:T,
j:T,
k:T,
n: }
IN =
j:T,
k:T,
n:T }
k:false,
n:T }
{ i:T,
OUT = gen  (IN  resv)
IN =
{ i:1,
j:2,
175
IN ={ i:T, j:T, k:T, n:T }
i=1
gen ={ i:1, j:2, k:false, n:T }
j=2
prsv = { i:T, j:T, k:T, n: }
k = false
OUT ={i:1, j:2, k:false, n:T }
gen ={ i:T, j:T, k:T, n:T }
prsv = { i:, j:, k:, n: }
i<n
k
gen ={ i:T, j:T, k:T, n:T }
prsv = { i:, j:, k:, n: }
i=3
gen ={ i:3, j:2, k:T, n:T }
prsv = { i:T, j:T, k:, n: }
j=2
OUT ={ i:T, j:T, k:T, n:T }
gen ={ i:T, j:T, k:T, n:T } print j
prsv = { i:, j:, k:, n: }
j=j+1
exit
176
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 }
i=1
gen ={ i:1, j:2, k:false, n:T }
j=2
prsv = { i:T, j:T, k:T, n: }
k = false
OUT ={i:1, j:2, k:false, n:T }
gen ={ i:T, j:T, k:T, n:T }
prsv = { i:, j:, k:, n: }
i<n
k
gen ={ i:T, j:T, k:T, n:T }
prsv = { i:, j:, k:, n: }
i=3
gen ={ i:3, j:2, k:T, n:T }
prsv = { i:T, j:T, k:, n: }
j=2
OUT ={ i:T, j:T, k:T, n:T }
gen ={ i:T, j:T, k:T, n:T } print j
prsv = { i:, j:, k:, n: }
j=j+1
exit
177
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: }
T = undefined
false
i<n
out1 = { i:T,
out2 = { i:1,
IN = out1  out2
true ….
-2
-1
0
1
2
3
4
….
 = not a constant
j:T,
j:2,
178
k:T,
k:false,
n:T }
n:T }
T = undefined
false
i<n
out1 = { i:T,
out2 = { i:1,
IN = out1  out2
IN = { i:1,
true ….
-2
-1
0
1
2
3
4
….
 = not a constant
j:T,
j:2,
k:T,
k:false,
n:T }
n:T }
j:2,
k:false,
n:T }
179
IN ={ i:T, j:T, k:T, n:T }
i=1
gen ={ i:1, j:2, k:false, n:T }
j=2
prsv = { i:T, j:T, k:T, n: }
k = false
OUT ={i:1, j:2, k:false, n:T }
IN ={i:1, j:2, k:false, n:T }
gen ={ i:T, j:T, k:T, n:T }
i<n
prsv = { i:, j:, k:, n: }
k
gen ={ i:T, j:T, k:T, n:T }
prsv = { i:, j:, k:, n: }
i=3
gen ={ i:3, j:2, k:T, n:T }
prsv = { i:T, j:T, k:, n: }
j=2
OUT ={ i:T, j:T, k:T, n:T }
gen ={ i:T, j:T, k:T, n:T } print j
prsv = { i:, j:, k:, n: }
j=j+1
exit
180
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 }
i=1
gen ={ i:1, j:2, k:false, n:T }
j=2
prsv = { i:T, j:T, k:T, n: }
k = false
OUT ={i:1, j:2, k:false, n:T }
IN ={i:1, j:2, k:false, n:T }
gen ={ i:T, j:T, k:T, n:T }
i<n
prsv = { i:, j:, k:, n: }
OUT ={i:1, j:2, k:false, n:T }
k
gen ={ i:T, j:T, k:T, n:T }
prsv = { i:, j:, k:, n: }
i=3
gen ={ i:3, j:2, k:T, n:T }
prsv = { i:T, j:T, k:, n: }
j=2
OUT ={ i:T, j:T, k:T, n:T }
gen ={ i:T, j:T, k:T, n:T } print j
prsv = { i:, j:, k:, n: }
j=j+1
exit
181
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 }
i=1
gen ={ i:1, j:2, k:false, n:T }
j=2
prsv = { i:T, j:T, k:T, n: }
k = false
OUT ={i:1, j:2, k:false, n:T }
IN ={i:1, j:2, k:false, n:T }
gen ={ i:T, j:T, k:T, n:T }
i<n
prsv = { i:, j:, k:, n: }
OUT ={i:1, j:2, k:false, n:T }
k
gen ={ i:T, j:T, k:T, n:T }
prsv = { i:, j:, k:, n: }
i=3
gen ={ i:3, j:2, k:T, n:T }
prsv = { i:T, j:T, k:, n: }
j=2
OUT ={ i:T, j:T, k:T, n:T }
gen ={ i:T, j:T, k:T, n:T } print j
prsv = { i:, j:, k:, n: }
j=j+1
exit
182
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 }
i=1
gen ={ i:1, j:2, k:false, n:T }
j=2
prsv = { i:T, j:T, k:T, n: }
k = false
OUT ={i:1, j:2, k:false, n:T }
IN ={i:1, j:2, k:false, n:T }
gen ={ i:T, j:T, k:T, n:T }
i<n
prsv = { i:, j:, k:, n: }
OUT ={i:1, j:2, k:false, n:T }
k
IN ={i:1, j:2, k:false, n:T }
i=3
gen ={ i:3, j:2, k:T, n:T }
prsv = { i:T, j:T, k:, n: }
j=2
OUT ={ i:T, j:T, k:T, n:T }
gen ={ i:T, j:T, k:T, n:T } print j
prsv = { i:, j:, k:, n: }
gen ={ i:T, j:T, k:T, n:T }
prsv = { i:, j:, k:, n: }
j=j+1
exit
183
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: }
T = undefined
i=3
false
j=2
true ….
-2
-1
0
1
2
3
4
….
 = not a constant
gen = { i:3,
j:2,
k:T,
n:T }
prsv = { i:T,
j:T,
k:,
n: }
IN =
j:2,
k:false,
n:T }
{ i:1,
OUT = gen  (IN  resv)
184
T = undefined
i=3
false
j=2
true ….
-2
-1
0
1
2
3
4
….
 = not a constant
gen = { i:3,
j:2,
k:T,
n:T }
prsv = { i:T,
j:T,
k:,
n: }
IN =
j:2,
k:false,
n:T }
k:false,
n:T }
{ i:1,
OUT = gen  (IN  resv)
IN =
{ i:3,
j:2,
185
IN ={ i:T, j:T, k:T, n:T }
i=1
gen ={ i:1, j:2, k:false, n:T }
j=2
prsv = { i:T, j:T, k:T, n: }
k = false
OUT ={i:1, j:2, k:false, n:T }
IN ={i:1, j:2, k:false, n:T }
gen ={ i:T, j:T, k:T, n:T }
i<n
prsv = { i:, j:, k:, n: }
OUT ={i:1, j:2, k:false, n:T }
k
IN ={i:1, j:2, k:false, n:T }
i=3
gen ={ i:3, j:2, k:T, n:T }
prsv = { i:T, j:T, k:, n: }
j=2
OUT ={i:3, j:2, k:false, n:T }
gen ={ i:T, j:T, k:T, n:T } print j
prsv = { i:, j:, k:, n: }
gen ={ i:T, j:T, k:T, n:T }
prsv = { i:, j:, k:, n: }
j=j+1
exit
186
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 }
i=1
gen ={ i:1, j:2, k:false, n:T }
j=2
prsv = { i:T, j:T, k:T, n: }
k = false
OUT ={i:1, j:2, k:false, n:T }
IN ={i:1, j:2, k:false, n:T }
gen ={ i:T, j:T, k:T, n:T }
i<n
prsv = { i:, j:, k:, n: }
OUT ={i:1, j:2, k:false, n:T }
k
IN ={i:1, j:2, k:false, n:T }
i=3
gen ={ i:3, j:2, k:T, n:T }
prsv = { i:T, j:T, k:, n: }
j=2
OUT ={i:3, j:2, k:false, n:T }
gen ={ i:T, j:T, k:T, n:T } print j
prsv = { i:, j:, k:, n: }
gen ={ i:T, j:T, k:T, n:T }
prsv = { i:, j:, k:, n: }
j=j+1
exit
187
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: }
T = undefined
false
i<n
out1 = { i:1,
out2 = { i:3,
IN = out1  out2
true ….
-2
-1
0
1
2
3
4
….
 = not a constant
j:2,
j:2,
188
k:false,
k:false,
n:T }
n:T }
T = undefined
false
i<n
out1 = { i:1,
out2 = { i:3,
IN = out1  out2
IN = { i:,
true ….
-2
-1
0
1
2
3
4
….
 = not a constant
j:2,
j:2,
k:false,
k:false,
n:T }
n:T }
j:2,
k:false,
n:T }
189
IN ={ i:T, j:T, k:T, n:T }
i=1
gen ={ i:1, j:2, k:false, n:T }
j=2
prsv = { i:T, j:T, k:T, n: }
k = false
OUT ={i:1, j:2, k:false, n:T }
IN ={i:, j:2, k:false, n:T }
gen ={ i:T, j:T, k:T, n:T }
i<n
prsv = { i:, j:, k:, n: }
OUT ={i:, j:2, k:false, n:T }
k
IN ={i:1, j:2, k:false, n:T }
i=3
gen ={ i:3, j:2, k:T, n:T }
prsv = { i:T, j:T, k:, n: }
j=2
OUT ={i:3, j:2, k:false, n:T }
gen ={ i:T, j:T, k:T, n:T } print j
prsv = { i:, j:, k:, n: }
gen ={ i:T, j:T, k:T, n:T }
prsv = { i:, j:, k:, n: }
j=j+1
exit
190
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 }
i=1
gen ={ i:1, j:2, k:false, n:T }
j=2
prsv = { i:T, j:T, k:T, n: }
k = false
OUT ={i:1, j:2, k:false, n:T }
IN ={i:, j:2, k:false, n:T }
gen ={ i:T, j:T, k:T, n:T }
i<n
prsv = { i:, j:, k:, n: }
OUT ={i:, j:2, k:false, n:T }
IN ={i:, j:2, k:false, n:T }
k
IN ={i:1, j:2, k:false, n:T }
i=3
gen ={ i:3, j:2, k:T, n:T }
prsv = { i:T, j:T, k:, n: }
j=2
OUT ={i:3, j:2, k:false, n:T }
gen ={ i:T, j:T, k:T, n:T } print j
prsv = { i:, j:, k:, n: }
gen ={ i:T, j:T, k:T, n:T }
prsv = { i:, j:, k:, n: }
j=j+1
exit
191
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 }
i=1
gen ={ i:1, j:2, k:false, n:T }
j=2
prsv = { i:T, j:T, k:T, n: }
k = false
OUT ={i:1, j:2, k:false, n:T }
IN ={i:, j:2, k:false, n:T }
gen ={ i:T, j:T, k:T, n:T }
i<n
prsv = { i:, j:, k:, n: }
OUT ={i:, j:2, k:false, n:T }
IN ={i:, j:2, k:false, n:T }
k
gen ={ i:T, j:T, k:T, n:T }
prsv = { i:, j:, k:, n: }
IN ={i:1, j:2, k:false, n:T }
OUT ={i:, j:2, k:false, n:T }
i=3
gen ={ i:3, j:2, k:T, n:T }
prsv = { i:T, j:T, k:, n: }
j=2
OUT ={i:3, j:2, k:false, n:T }
gen ={ i:T, j:T, k:T, n:T } print j
prsv = { i:, j:, k:, n: }
j=j+1
exit
192
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 }
i=1
gen ={ i:1, j:2, k:false, n:T }
j=2
prsv = { i:T, j:T, k:T, n: }
k = false
OUT ={i:1, j:2, k:false, n:T }
IN ={i:, j:2, k:false, n:T }
gen ={ i:T, j:T, k:T, n:T }
i<n
prsv = { i:, j:, k:, n: }
OUT ={i:, j:2, k:false, n:T }
IN ={i:, j:2, k:false, n:T }
k
gen ={ i:T, j:T, k:T, n:T }
prsv = { i:, j:, k:, n: }
IN ={i:1, j:2, k:false, n:T }
OUT ={i:, j:2, k:false, n:T }
i=3
gen ={ i:3, j:2, k:T, n:T }
prsv = { i:T, j:T, k:, n: }
j=2
OUT ={i:3, j:2, k:false, n:T }
gen ={ i:T, j:T, k:T, n:T } print j
prsv = { i:, j:, k:, n: }
j=j+1
exit
193
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 }
i=1
gen ={ i:1, j:2, k:false, n:T }
j=2
prsv = { i:T, j:T, k:T, n: }
k = false
OUT ={i:1, j:2, k:false, n:T }
IN ={i:, j:2, k:false, n:T }
gen ={ i:T, j:T, k:T, n:T }
i<n
prsv = { i:, j:, k:, n: }
OUT ={i:, j:2, k:false, n:T }
IN ={i:, j:2, k:false, n:T }
k
gen ={ i:T, j:T, k:T, n:T }
prsv = { i:, j:, k:, n: }
IN ={i:1, j:2, k:false, n:T }
OUT ={i:, j:2, k:false, n:T }
i=3
gen ={ i:3, j:2, k:T, n:T }
prsv = { i:T, j:T, k:, n: }
j=2
OUT ={i:3, j:2, k:false, n:T }IN ={i:, j:2, k:false, n:T }
gen ={ i:T, j:T, k:T, n:T } print j
prsv = { i:, j:, k:, n: }
j=j+1
exit
194
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 }
i=1
gen ={ i:1, j:2, k:false, n:T }
j=2
prsv = { i:T, j:T, k:T, n: }
k = false
OUT ={i:1, j:2, k:false, n:T }
IN ={i:, j:2, k:false, n:T }
gen ={ i:T, j:T, k:T, n:T }
i<n
prsv = { i:, j:, k:, n: }
OUT ={i:, j:2, k:false, n:T }
IN ={i:, j:2, k:false, n:T }
k
gen ={ i:T, j:T, k:T, n:T }
prsv = { i:, j:, k:, n: }
IN ={i:1, j:2, k:false, n:T }
OUT ={i:, j:2, k:false, n:T }
i=3
gen ={ i:3, j:2, k:T, n:T }
prsv = { i:T, j:T, k:, n: }
j=2
OUT ={i:3, j:2, k:false, n:T }IN ={i:, j:2, k:false, n:T }
gen ={ i:T, j:T, k:T, n:T } print j
prsv = { i:, j:, k:, n: }
j=j+1
gen ={ i:T, j:, k:T, n:T }
prsv ={ i:, j:T, k:, n:}
OUT ={i:, j:2, k:false, n:T }
exit
195
gen ={ i:T, j:T, k:T, n:T }
prsv = { i:, j:, k:, n: }
IN ={ i:T, j:T, k:T, n:T }
i=1
gen ={ i:1, j:2, k:false, n:T }
j=2
prsv = { i:T, j:T, k:T, n: }
k = false
OUT ={i:1, j:2, k:false, n:T }
IN ={i:, j:2, k:false, n:T }
gen ={ i:T, j:T, k:T, n:T }
i<n
prsv = { i:, j:, k:, n: }
OUT ={i:, j:2, k:false, n:T }
IN ={i:, j:2, k:false, n:T }
k
gen ={ i:T, j:T, k:T, n:T }
prsv = { i:, j:, k:, n: }
IN ={i:1, j:2, k:false, n:T }
OUT ={i:, j:2, k:false, n:T }
i=3
gen ={ i:3, j:2, k:T, n:T }
prsv = { i:T, j:T, k:, n: }
j=2
OUT ={i:3, j:2, k:false, n:T }IN ={i:, j:2, k:false, n:T }
gen ={ i:T, j:T, k:T, n:T } print j
prsv = { i:, j:, k:, n: }
j=j+1
gen ={ i:T, j:, k:T, n:T }
prsv ={ i:, j:T, k:, n:}
OUT ={i:, j:2, k:false, n:T }
exit
196
gen ={ i:T, j:T, k:T, n:T }
prsv = { i:, j:, k:, n: }
IN ={ i:T, j:T, k:T, n:T }
i=1
gen ={ i:1, j:2, k:false, n:T }
j=2
prsv = { i:T, j:T, k:T, n: }
k = false
OUT ={i:1, j:2, k:false, n:T }
IN ={i:, j:2, k:false, n:T }
gen ={ i:T, j:T, k:T, n:T }
i<n
prsv = { i:, j:, k:, n: }
OUT ={i:, j:2, k:false, n:T }
IN ={i:, j:2, k:false, n:T }
k
gen ={ i:T, j:T, k:T, n:T }
prsv = { i:, j:, k:, n: }
IN ={i:1, j:2, k:false, n:T }
OUT ={i:, j:2, k:false, n:T }
i=3
gen ={ i:3, j:2, k:T, n:T }
prsv = { i:T, j:T, k:, n: }
j=2
OUT ={i:3, j:2, k:false, n:T }IN ={i:, j:2, k:false, n:T } IN ={i:, j:2, k:false, n:T }
gen ={ i:T, j:T, k:T, n:T } print j
prsv = { i:, j:, k:, n: }
j=j+1
gen ={ i:T, j:, k:T, n:T }
prsv ={ i:, j:T, k:, n:}
OUT ={i:, j:2, k:false, n:T }
exit
197
gen ={ i:T, j:T, k:T, n:T }
prsv = { i:, j:, k:, n: }
T = undefined
j=j+1
false
true ….
-2
-1
0
1
2
3
4
….
 = not a constant
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)
198
T = undefined
j=j+1
false
true ….
-2
-1
0
1
2
3
4
….
 = not a constant
gen = { i:T,
j:,
k:T,
n:T }
prsv = { i:,
j:T,
k:,
n: }
IN = { i:,
j:2,
k:false,
n:T }
k:false,
n:T }
OUT = gen  (IN  resv)
IN = { i:,
j:,
199
IN ={ i:T, j:T, k:T, n:T }
i=1
gen ={ i:1, j:2, k:false, n:T }
j=2
prsv = { i:T, j:T, k:T, n: }
k = false
OUT ={i:1, j:2, k:false, n:T }
IN ={i:, j:2, k:false, n:T }
gen ={ i:T, j:T, k:T, n:T }
i<n
prsv = { i:, j:, k:, n: }
OUT ={i:, j:2, k:false, n:T }
IN ={i:, j:2, k:false, n:T }
k
gen ={ i:T, j:T, k:T, n:T }
prsv = { i:, j:, k:, n: }
IN ={i:1, j:2, k:false, n:T }
OUT ={i:, j:2, k:false, n:T }
i=3
gen ={ i:3, j:2, k:T, n:T }
prsv = { i:T, j:T, k:, n: }
j=2
OUT ={i:3, j:2, k:false, n:T }IN ={i:, j:2, k:false, n:T } IN ={i:, j:2, k:false, n:T }
gen ={ i:T, j:T, k:T, n:T } print j
prsv = { i:, j:, k:, n: }
j=j+1
OUT ={i:, j:2, k:false, n:T }
exit
200
gen ={ i:T, j:, k:T, n:T }
prsv ={ i:, j:T, k:, n:}
OUT ={i:, j:, k:false, n:T }
gen ={ i:T, j:T, k:T, n:T }
prsv = { i:, j:, k:, n: }
IN ={ i:T, j:T, k:T, n:T }
i=1
gen ={ i:1, j:2, k:false, n:T }
j=2
prsv = { i:T, j:T, k:T, n: }
k = false
OUT ={i:1, j:2, k:false, n:T }
IN ={i:, j:2, k:false, n:T }
gen ={ i:T, j:T, k:T, n:T }
i<n
prsv = { i:, j:, k:, n: }
OUT ={i:, j:2, k:false, n:T }
IN ={i:, j:2, k:false, n:T }
k
gen ={ i:T, j:T, k:T, n:T }
prsv = { i:, j:, k:, n: }
IN ={i:1, j:2, k:false, n:T }
OUT ={i:, j:2, k:false, n:T }
i=3
gen ={ i:3, j:2, k:T, n:T }
prsv = { i:T, j:T, k:, n: }
j=2
OUT ={i:3, j:2, k:false, n:T }IN ={i:, j:2, k:false, n:T } IN ={i:, j:2, k:false, n:T }
gen ={ i:T, j:T, k:T, n:T } print j
prsv = { i:, j:, k:, n: }
j=j+1
OUT ={i:, j:2, k:false, n:T }
exit
201
gen ={ i:T, j:, k:T, n:T }
prsv ={ i:, j:T, k:, n:}
OUT ={i:, j:, k:false, n:T }
gen ={ i:T, j:T, k:T, n:T }
prsv = { i:, j:, k:, n: }
T = undefined
false
exit
out1 = { i:,
out2 = { i:,
IN = out1  out2
IN = { i:,
true ….
-2
-1
0
1
2
3
4
….
 = not a constant
j:2,
j:,
k:false,
k:false,
n:T }
n:T }
j:,
k:false,
n:T }
202
IN ={ i:T, j:T, k:T, n:T }
i=1
gen ={ i:1, j:2, k:false, n:T }
j=2
prsv = { i:T, j:T, k:T, n: }
k = false
OUT ={i:1, j:2, k:false, n:T }
IN ={i:, j:2, k:false, n:T }
gen ={ i:T, j:T, k:T, n:T }
i<n
prsv = { i:, j:, k:, n: }
OUT ={i:, j:2, k:false, n:T }
IN ={i:, j:2, k:false, n:T }
k
gen ={ i:T, j:T, k:T, n:T }
prsv = { i:, j:, k:, n: }
IN ={i:1, j:2, k:false, n:T }
OUT ={i:, j:2, k:false, n:T }
i=3
gen ={ i:3, j:2, k:T, n:T }
prsv = { i:T, j:T, k:, n: }
j=2
OUT ={i:3, j:2, k:false, n:T }IN ={i:, j:2, k:false, n:T } IN ={i:, j:2, k:false, n:T }
gen ={ i:T, j:T, k:T, n:T } print j
prsv = { i:, j:, k:, n: }
j=j+1
OUT ={i:, j:2, k:false, n:T }
gen ={ i:T, j:, k:T, n:T }
prsv ={ i:, j:T, k:, n:}
OUT ={i:, j:, k:false, n:T }
OUT ={i:, j:, k:false, n:T }
gen ={ i:T, j:T, k:T, n:T }
exit
prsv = { i:, j:, k:, n: }
203
IN ={ i:T, j:T, k:T, n:T }
i=1
gen ={ i:1, j:2, k:false, n:T }
j=2
prsv = { i:T, j:T, k:T, n: }
k = false
OUT ={i:1, j:2, k:false, n:T }
IN ={i:, j:2, k:false, n:T }
gen ={ i:T, j:T, k:T, n:T }
i<n
prsv = { i:, j:, k:, n: }
OUT ={i:, j:2, k:false, n:T }
IN ={i:, j:2, k:false, n:T }
k
gen ={ i:T, j:T, k:T, n:T }
prsv = { i:, j:, k:, n: }
IN ={i:1, j:2, k:false, n:T }
OUT ={i:, j:2, k:false, n:T }
i=3
gen ={ i:3, j:2, k:T, n:T }
prsv = { i:T, j:T, k:, n: }
j=2
OUT ={i:3, j:2, k:false, n:T }IN ={i:, j:2, k:false, n:T } IN ={i:, j:2, k:false, n:T }
gen ={ i:T, j:T, k:T, n:T } print j
prsv = { i:, j:, k:, n: }
j=j+1
OUT ={i:, j:2, k:false, n:T }
gen ={ i:T, j:, k:T, n:T }
prsv ={ i:, j:T, k:, n:}
OUT ={i:, j:, k:false, n:T }
OUT ={i:, j:, k:false, n:T }
gen ={ i:T, j:T, k:T, n:T }
exit
prsv = { i:, j:, k:, n: }
204
IN ={ i:T, j:T, k:T, n:T }
i=1
j=2
k = false
IN ={i:, j:2, k:false, n:T }
i<n
IN ={i:, j:2, k:false, n:T }
k
IN ={i:1, j:2, k:false, n:T }
i=3
j=2
IN ={i:, j:2, k:false, n:T }
print j
IN ={i:, j:2, k:false, n:T }
j=j+1
OUT ={i:, j:, k:false, n:T }
exit
205
IN ={ i:T, j:T, k:T, n:T }
i=1
j=2
k = false
IN ={i:1, j:2, k:false, n:T }
i<n
IN ={i:, j:2, k:false, n:T }
k
IN ={i:1, j:2, k:false, n:T }
i=3
j=2
IN ={i:, j:2, k:false, n:T }
print j
IN ={i:, j:2, k:false, n:T }
j=j+1
OUT ={i:, j:, k:false, n:T }
exit
206
IN ={ i:T, j:T, k:T, n:T }
i=1
j=2
k = false
IN ={i:1, j:2, k:false, n:T }
i<n
IN ={i:, j:2, k:false, n:T }
false
IN ={i:1, j:2, k:false, n:T }
i=3
j=2
IN ={i:, j:2, k:false, n:T }
print j
IN ={i:, j:2, k:false, n:T }
j=j+1
OUT ={i:, j:, k:false, n:T }
exit
207
IN ={ i:T, j:T, k:T, n:T }
i=1
j=2
k = false
IN ={i:1, j:2, k:false, n:T }
i<n
IN ={i:, j:2, k:false, n:T }
false
IN ={i:1, j:2, k:false, n:T }
i=3
j=2
IN ={i:, j:2, k:false, n:T }
print j
IN ={i:, j:2, k:false, n:T }
j=j+1
OUT ={i:, j:, k:false, n:T }
exit
208
IN ={ i:T, j:T, k:T, n:T }
i=1
j=2
k = false
IN ={i:1, j:2, k:false, n:T }
i<n
IN ={i:, j:2, k:false, n:T }
false
IN ={i:1, j:2, k:false, n:T }
i=3
j=2
IN ={i:, j:2, k:false, n:T }
print 2
IN ={i:, j:2, k:false, n:T }
j=j+1
OUT ={i:, j:, k:false, n:T }
exit
209
IN ={ i:T, j:T, k:T, n:T }
i=1
j=2
k = false
IN ={i:1, j:2, k:false, n:T }
i<n
IN ={i:, j:2, k:false, n:T }
false
IN ={i:1, j:2, k:false, n:T }
i=3
j=2
IN ={i:, j:2, k:false, n:T }
print 2
IN ={i:, j:2, k:false, n:T }
j=j+1
OUT ={i:, j:, k:false, n:T }
exit
210
IN ={ i:T, j:T, k:T, n:T }
i=1
j=2
k = false
IN ={i:1, j:2, k:false, n:T }
i<n
IN ={i:, j:2, k:false, n:T }
false
IN ={i:1, j:2, k:false, n:T }
i=3
j=2
IN ={i:, j:2, k:false, n:T }
print 2
IN ={i:, j:2, k:false, n:T }
j=j+1
OUT ={i:, j:, k:false, n:T }
exit
211
IN ={ i:T, j:T, k:T, n:T }
i=1
j=2
k = false
IN ={i:1, j:2, k:false, n:T }
i<n
IN ={i:, j:2, k:false, n:T }
false
IN ={i:1, j:2, k:false, n:T }
i=3
j=2
IN ={i:, j:2, k:false, n:T }
print 2
IN ={i:, j:2, k:false, n:T }
j=2+1
OUT ={i:, j:, k:false, n:T }
exit
212
IN ={ i:T, j:T, k:T, n:T }
i=1
j=2
k = false
IN ={i:1, j:2, k:false, n:T }
i<n
IN ={i:, j:2, k:false, n:T }
false
IN ={i:1, j:2, k:false, n:T }
i=3
j=2
IN ={i:, j:2, k:false, n:T }
print 2
IN ={i:, j:2, k:false, n:T }
j=2+1
OUT ={i:, j:, k:false, n:T }
exit
213
IN ={ i:T, j:T, k:T, n:T }
i=1
j=2
k = false
IN ={i:1, j:2, k:false, n:T }
i<n
IN ={i:, j:2, k:false, n:T }
IN ={i:1, j:2, k:false, n:T }
i=3
j=2
IN ={i:, j:2, k:false, n:T }
j=2+1
OUT ={i:, j:, k:false, n:T }
exit
214
Lecturas
• Ballena
– Capítulo 13
215