# ISW II - Práctica 5 - Dataflow Analysis
Hecho por Lorenzo Ruiz Díaz.

Como no había cosas de Dataflow en CubaWiki y quería hacer algún aporte a la comunidad antes de dejar de cursar, hice esta guía con mucho amor para todos ustedes.

***NOTA: No hay pruebas de que estos ejercicios estén bien resueltos. Tomé libertades creativas con algunas notaciones, pero siempre tratando de que queden bien expresadas las ideas.***

Cuando se pide un retículado, si el mismo es finito, mostrarlo mediante un diagrama de Hasse. En caso contrario indicar el dominio, la relación de orden $\sqsubseteq$, el supremo e ínfimo.

## Parte 1 - Reticulados, Punto fijo
### Ejercicio 1
a) $(\mathbb{Z}, \leq)$ es un reticulado, ya que $\leq$ es un orden total (y por ende un orden parcial), con $x \sqcup y := \max\{x,y\}$ y $x \sqcap y := \min\{x,y\}$.

Observamos que no existe $\top_\mathbb{Z}$, ya que para todo $x \in \mathbb{Z}$, vale $x + 1 \nleq x$. Del mismo modo pero hacia abajo, no existe $\bot_\mathbb{Z}$.

b) Sobre el conjunto $\mathbb{Z} \cup \{-\infty, \infty\}$, se puede definir un reticulado completo utilizando la siguiente relación de orden (total) $\sqsubseteq$, valiendo $x \sqsubseteq y$ en los siguientes tres casos:
- $x,y \in \mathbb{Z}$ y $x \leq y$.
- $x = -\infty$.
- $y = \infty$.

Es claro que $\sqsubseteq$ es una relación de orden, pues satisface los axiomas de reflexividad, antisimetría y transitividad. Luego, observamos que para todo $X \subseteq \mathbb{Z} \cup \{-\infty, \infty\}$, podemos definir tanto $\sqcup X$ como $\sqcap X$ de la siguiente forma:
- Si $\infty \in X$, vale $\sqcup X = \infty$, caso contrario $\sqcup = \displaystyle\max_\mathbb{(Z,\leq)}X$ (excepto en el caso borde $X = \{-\infty\}$).
- Si $-\infty \in X$, vale $\sqcap X = -\infty$, caso contrario $\sqcap = \displaystyle\min_\mathbb{(Z,\leq)}X$ (excepto en el caso borde $X = \{\infty\}$).

Es decir, en este contexto, el reticulado es completo para $\top = \infty$ y $\bot = -\infty$.

### Ejercicio 2
El orden parcial $P_1$ no es un reticulado, ya que tomando cualquier par de los tres elementos superiores $x_1, x_2, x_3$ del diagrama de Hasse, no tienen una mínima cota superior (ya que para cada $x_i$, vale $x_i \sqsubseteq x$ sii $x = x_i$). Una forma de reparar $P_1$ es añadir un elemento más $y$ al tope, tal que $x_i \sqsubseteq y$ para cada $i=1,2,3$.

El orden parcial $P_2$ no es un reticulado. Para verlo, consideramos los dos elementos $v_1, v_2$ que están inmediatamente por encima de $\top$. Están también sus superiores directos $w_1, w_2$ y el tope $\top$. Observando la relación de orden, el conjunto de cotas superiores de $v_1,v_2$ es
$$UB(v_1,v_2) = \{w_1,w_2,\top\}$$
Luego, como valen $w_1 \sqsubseteq \top$ y $w_2 \sqsubseteq \top$, la mínima cota superior $v_1 \sqcup v_2$ no puede ser $\top$, y debe pertenecer a $\{w_1, w_2\}$. Sin embargo, estos dos elementos no son comparables en $\sqsubseteq$, es decir que no hay una mínima cota superior.

Una forma de reparar $P_2$ es remover $v_1 \sqsubseteq w_2$ y $v_2 \sqsubseteq w_1$, obteniendo así $v_1 \sqcup v_2 = w_1 \sqcup w_2 = \top$.

### Ejercicio 3
a) $S = \{A, B, C\}$. Para que el ejercicio tenga sentido, el reticulado creado $(P, \sqsubseteq)$ debe ser sobre un conjunto $P \supset S$. En particular consideramos $P = S \cup \{\bot,\top\}$, con $A,B,C$ no comparables por $\sqsubseteq$ pero sí vale $\bot \sqsubseteq p$ y $p \sqsubseteq \top$ para todo $p \in P$.

Observamos que todos los caminos de $\bot$ a $\top$ son de la forma $(\bot, s, \top)$ con $s \in S$, entonces el reticulado tiene altura $2$. En particular, $(P, \sqsubseteq)$ es el **reticulado plano** de $S$.

b) Es el reticulado dado por $(\mathcal{P}(S), \subseteq)$. En este caso, $\top_{\mathcal{P}(S)} = S$ y $\bot_{\mathcal{P}(S)} = \emptyset$. Como todos los caminos de $\bot$ a $\top$ van aumentando en uno el número de sus elementos en cada paso, la altura es $3$ (porque vamos de $|\emptyset| = 0$ a $|S| = 3$).

c) $N = \{1,2\}$ con $1 \sqsubseteq_N 2$. El reticulado de pares $(S \times N, \sqsubseteq)$ está dado por:
$$(s,n) \sqsubseteq (s',n') \iff s \sqsubseteq_S s' \wedge n \sqsubseteq_N n'$$

Observamos que los elementos de $S$ no son comparables, es decir $\forall s,s' \in S$ vale $s \not\sqsubseteq_S s'$, luego siempre vale $(s,n) \not\sqsubseteq (s',n')$.

Si los elementos de $S$ fueran comparables y formaran un orden total (por ejemplo $A \sqsubseteq_S B \sqsubseteq_S C$), el reticulado obtenido sería:


### Ejercicio 4
a) Tenemos:
- $(S,\sqsubseteq)$ con $S = \{-,0,+\}$ y $- \sqsubseteq 0 \sqsubseteq +$.
- $\varphi: S \to S$ dada por $\varphi(-) = \varphi(0) = 0, \varphi(+) = +$.

Primero, veremos que $S$ es un poset completo (o dominio), es decir que $\sqcup C$ existe para todas las cadenas incrementales $C$ de $S$. Para esto, basta enumerarlas y calcular $\sqcup C$ para cada una, lo que haremos será calcular $\sqcup X$ para todo $X \subseteq S$ (si existe para todos los subconjuntos, existirá para todas las cadenas $C \in \mathcal{C}$).

Al ser un orden total, vale:
- Si $+ \in X$, es $\sqcup X = +$. En este caso, $\varphi(\sqcup X) = +$
- Si $+ \notin X$ pero $0 \in X$, es $\sqcup X = 0$. En este caso, $\varphi(\sqcup X) = 0$
- Si no, $\sqcup X = -$. En este caso, $\varphi(\sqcup X) = 0$.

Las cadenas incrementales de $S$ son las del conjunto $$\mathcal{C} = \{(-), (0), (+), (-,0), (0,+), (-,+), (-,0,+)\}$$

Observamos que $\varphi$ es monótona, analizando todos los pares de elementos $x,y \in S$ con $x \neq y$ y $x \sqsubseteq y$:
- $- \sqsubseteq 0$: Ver que $\varphi(-) = 0 \sqsubseteq 0 = \varphi(0)$.
- $0 \sqsubseteq +$: Ver que $\varphi(0) = 0 \sqsubseteq + = \varphi(+)$.
- $- \sqsubseteq +$: Vale por transitividad de las anteriores, ya que $\varphi(-) \sqsubseteq \varphi(0) \sqsubseteq \varphi(+)$.

Como $S$ es un dominio de altura finita $2$ y $\varphi$ es monótona, por el Teorema del Punto Fijo existe $\text{LFP}(\varphi)$ Para computar iterativamente $\text{LFP}(\varphi)$, notar que tenemos:
$$\varphi^0(-) = -, \quad \varphi(-) = 0, \quad \varphi^2(-) = \varphi(0) = 0$$
y por ende $\text{LFP}(\varphi) = 0$.

b) Tenemos:
- $(S,\sqsubseteq)$ con $S = \{-,0,+\}$ y $- \sqsubseteq 0 \sqsubseteq +$.
- $\varphi: S \to S$ dada por $\varphi(-) = 0, \varphi(0) = -, \varphi(+) = +$.

La diferencia con el ejercicio anterior es que $\varphi$ no es monótona, en tanto $- \sqsubseteq 0$ pero $\varphi(-) = 0 \not\sqsubseteq - = \varphi(0)$. Luego, el Teorema del Punto Fijo no es aplicable a $\varphi$.

c) Tenemos:
- $(S,\sqsubseteq)$ con $S = \{\bot,0,-,+,\top\}$ y $\bot \sqsubseteq 0 \sqsubseteq \{-,+\} \sqsubseteq \top$, donde $-,+$ no son comparables por $\sqsubseteq$.
- $\varphi: S \to S$ dada por $\varphi(\bot) = \varphi(0) = \varphi(-) = 0, \varphi(+) = \varphi(\top) = \top$.

Las cadenas incrementales de $S$ son las del conjunto $\mathcal{C}$ (que no tengo ganas de listar). Observar que $\sqcup X$ existe para todo $X \subseteq S$, y está dado por:
- Si $\top \in X$, $\sqcup X = \top$. En este caso $\varphi(\sqcup X) = \top$.
- Si $\top,+ \notin X$ y $- \in X$, $\sqcup X = -$. En este caso $\varphi(\sqcup X) = 0$.
- Si $\top,- \notin X$ y $+ \in X$, $\sqcup X = +$. En este caso $\varphi(\sqcup X) = \top$.
- Si $\top \notin X$ y $+,- \in X$, $\sqcup X = \top$. En este caso $\varphi(\sqcup X) = \top$.
- Si $\top,+,- \notin X$ y $0 \in X$, $\sqcup X = 0$. En este caso $\varphi(\sqcup X) = 0$.
- Si no, $\sqcup X = \bot$. En este caso $\varphi(\sqcup X) = 0$.

Ahora notamos que $\varphi$ es monótona, en tanto:
- $\bot \sqsubseteq 0$: Vale $\varphi(\bot) = 0 = \varphi(0)$.
- $0 \sqsubseteq +$: Vale $\varphi(0) = 0 \sqsubseteq \top = \varphi(+)$.
- $0 \sqsubseteq -$: Vale $\varphi(0) = 0 = \varphi(-)$.
- $+ \sqsubseteq \top$: Vale $\varphi(+) = \top = \varphi(\top)$.
- $- \sqsubseteq \top$: Vale $\varphi(-) = 0 \sqsubseteq \top = \varphi(\top)$.
- Los demás valen por los axiomas de orden de $\sqsubseteq$.

El Teorema del Punto Fijo es aplicable a $\phi$ en tanto $S$ es un reticulado completo y $\phi$ es monótona. Iterativamente, se obtiene que
$$\varphi^0(\bot) = \bot, \quad \varphi(\bot) = 0, \quad \varphi^2(\bot) = \varphi(0) = 0$$
y por ende $\text{LFP}(\varphi) = 0$.

### Ejercicio 5
Si $X$ no es monótona, el teorema del punto fijo no vale. Como contraejemplo, se puede considerar el poset $(S, \leq)$ con $S = \{1,2\}$ y $\varphi: S \to S$ dada por $\varphi(1) = 2, \varphi(2) = 1$, que no tiene puntos fijos pese a que $(S, \leq)$ es un reticulado completo (ya que es un orden total).

### Ejercicio 6
Tenemos el reticulado $\text{Sign} = \text{Flat}(\{-,0,+\}) = \{\bot, -, 0, +, \top\}$. En particular, en este reticulado los elementos $-,0,+$ no son comparables, en tanto la relación de orden está dada por el conocimiento que tenemos sobre las variables. Queremos extender $\text{Sign}$ para incluir dos símbolos $\tilde{+}, \tilde{-}$ que representen los valores mayores o iguales a $0$ y menores o iguales a $0$ respectivamente.

- Observamos que $\tilde{+}$ es un caso que es más general que $+$ y $0$, pero menos general que $\top$. Entonces, valdrán $+ \sqsubseteq \tilde{+},$ $0 \sqsubseteq \tilde{+}$, $\tilde{+} \sqsubseteq \top$.
- Observamos que $\tilde{-}$ es un caso que es más general que $-$ y $0$, pero menos general que $\top$. Entonces, valdrán $- \sqsubseteq \tilde{-},$ $0 \sqsubseteq \tilde{-}$, $\tilde{-} \sqsubseteq \top$.

Para definir la operación suma en el nuevo reticulado, realizamos una tabla:
| Suma | $\bot$ | $-$ | $0$ | $+$ | $\tilde{-}$ | $\tilde{+}$ | $\top$ |
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|
| $\bot$ | $\bot$ | $\bot$ | $\bot$ | $\bot$ | $\bot$ | $\bot$ | $\bot$ |
| $-$ | $\bot$ | $-$ | $-$ | $\top$ | $-$ | $\top$ | $\top$ |
| $0$ | $\bot$ | $-$ | $0$ | $+$ | $\tilde{-}$ | $\tilde{+}$ | $\top$ |
| $+$ | $\bot$ | $\top$ | $+$ | $+$ | $\top$ | $+$ | $\top$ |
| $\tilde{-}$ | $\bot$ | $-$ | $\tilde{-}$ | $\top$ | $\tilde{-}$ | $\top$ | $\top$ |
| $\tilde{+}$ | $\bot$ | $\top$ | $\tilde{+}$ | $+$ | $\top$ | $\tilde{+}$ | $\top$ |
| $\top$ | $\bot$ | $\top$ | $\top$ | $\top$ | $\top$ | $\top$ | $\top$ |

### Ejercicio 7
Sea $D$ el conjunto que representa funciones de variables a signos, $D = \{d \mid d: \text{Var} \to \text{Sign}\}$. Cada elemento $d \in D$ es una función.

Convertiremos $D$ en un poset con una relación de orden $\sqsubseteq$, de forma que $\forall d_1, d_2 \in D$, valga $d_1 \sqsubseteq d_2$ sii $d_1$ es igual o más precisa que $d_2$. En este contexto, "más precisa" quiere decir que ocurren:
- No puede haber variables indefinidas en $d_1$ y definidas en $d_2$. $$\forall v \in \text{Var}: d_1(v) = \bot \implies d_2(v) = \bot$$
- Para ninguna variable con un valor definido puede haber mayor certeza sobre su valor en $d_2$ que en $d_1$. Más aún, los valores deben ser consistentes. $$\forall v \in \text{Var}: d_2(v) \in \{-,+,0\} \implies d_1(v) = d_2(v)$$

Notar que de las condiciones anteriores, se deduce que si $d_2(v) = \top$ entonces $d_1(v)$ puede ser cualquiera excepto $\bot$. Entonces, la respuesta es:
$$d_1 \sqsubseteq d_2 \iff \forall v \in \text{Var}: (d_1(v) = \bot \implies d_2(v) = \bot) \wedge (d_2(v) \in \{-,+,0\} \implies d_1(v) = d_2(v))$$

Ahora, queremos definir la operación $\sqcup$ que represente el supremo en $D$. Es decir, para cada $X \subseteq D$ dar un $\sqcup X \in D$ tal que sea la mínima cota superior de $X$. En este contexto, a mayor imprecisión que tenga un $d \in D$ sobre el valor de las variables, "más alto" estará en la relación de orden $\sqsubseteq$.

Vamos a analizar la imagen de cada variable por separado, para un $X \subseteq D$ no necesariamente finito. Para simplificar las expresiones asumo que van a tener una variable libre $v \in \text{Var}$.
- Si para alguna de las funciones, la imagen de la variable es $\bot$, entonces en su mínima cota superior también. $$\exists d \in X: d(v) = \bot \implies \sqcup X(v) = \bot$$
- Si hay una variable que está definida en todas las funciones de $X$ con el mismo valor, entonces en su mínima cota superior va a estar con ese valor. $$\exists n \in \text{Sign}: (\forall d \in X: d(v) = n) \implies \sqcup X(v) = n$$
- En el único caso restante (porque son disjuntos), si hay los valores no coinciden pero no hay ningún $\bot$, entonces en su mínima cota superior va a estar con un $\top$.

Luego, vale que $\sqcup X: \text{Var} \to \text{Sign}$ está dada por $$\sqcup X(v) = \begin{cases}
\bot \text{ si } \exists d \in X: d(v) = \bot \\
n \text{ si } \exists n \in \text{Sign}: (\forall d \in X: d(v) = n) \\
\top \text{ si no}
\end{cases}$$

La notación $d[x \to n]$ indica una nueva función $d' \in D$ tal que $d'(x) = n$, y $d'(x') = d(x)$ para todo $x \in \text{Var} \setminus \{x\}$. Además, extendemos el lenguaje con la instrucción $x += E$, que dado $d \in D$ modifica el estado de $x \in \text{Var}$ sumándole el valor del signo de $E$. Es decir (si $\text{sign}(E)$ es el valor de $E$ en el reticulado $\text{Sign}$), la instrucción es una función $\llbracket x+=E \rrbracket: D \to D$:
$$\llbracket x+=E \rrbracket(d) = d[x \to x + \text{sign}(E)]$$

Para saber si es monótona, hay que justificar que $d_1 \sqsubseteq d_2$ implica $\llbracket x+=E \rrbracket(d_1) \sqsubseteq \llbracket x+=E \rrbracket(d_2)$, o lo que es lo mismo,
$$d_1[x \to x + \text{sign}(E)] \sqsubseteq d_2[x \to x + \text{sign}(E)].$$
- Para $v \in \text{Var} \setminus \{x\}$, observamos que la propiedad se cumple ya que vale en $d_1, d_2$, en tanto $$d_1(v) = [x \to x + \text{sign}(E)](v),\quad d_2(v) = d_2[x \to x + \text{sign}(E)](v).$$
- Para $v = x$, vamos a apelar a la tabla de Suma en el reticulado $\text{Sign}$. Podemos pensar a cada fila como un valor de $\text{sign}(E)$ (esto permite resolver el problema para los $5$ casos) y analizar los valores de $d_i(x)$ según las columnas. Recordar que como $d_1 \sqsubseteq d_2$, vale $d_1(x) \sqsubseteq_\text{Sign} d_2(x)$.
- Caso $\text{sign}(E) = \bot$: Vale $d_1[x \to x + \bot](x) = \bot \sqsubseteq_\text{Sign} \bot = d_2[x \to x + \bot]$.
- Para el resto de los casos:
- Si $d_1(x) = \bot$ o $d_2(x) = \bot$ es trivial al reducirse a $\bot \sqsubseteq_\text{Sign} \bot$.
- Si $d_1(x) = d_2(x)$ también es trivial porque las imágenes de las funciones coincidirán.
- Si $d_1(x) \in \{-,0,+\}$ y $d_2(x) = \top$ también sirve porque queda $d_1[x \to x + \text{sign}(E)] \in \{-,0,+,\top\}$ y $d_2[x \to x + \text{sign}(E)] = \top$.

| Suma | $\bot$ | $-$ | $0$ | $+$ | $\top$ |
|:-:|:-:|:-:|:-:|:-:|:-:|
| $\bot$ | $\bot$ | $\bot$ | $\bot$ | $\bot$ | $\bot$ |
| $-$ | $\bot$ | $-$ | $-$ | $\top$ | $\top$ |
| $0$ | $\bot$ | $-$ | $0$ | $+$ | $\top$ |
| $+$ | $\bot$ | $\top$ | $+$ | $+$ | $\top$ |
| $\top$ | $\bot$ | $\top$ | $\top$ | $\top$ | $\top$ |

Entonces se puede concluir la propiedad que usamos para definir $\sqsubseteq$:
$$\begin{aligned}
\forall v \in \text{Var}: & (d_1[x \to x + \text{sign(E)}](v) = \bot \implies d_2[x \to x + \text{sign(E)}](v) = \bot) \\
& \wedge (d_2[x \to x + \text{sign(E)}](v) \in \{-,+,0\} \implies \\
& \quad \quad d_1[x \to x + \text{sign(E)}](v) = d_2[x \to x + \text{sign(E)}](v))
\end{aligned}$$
y con ello que $\llbracket x+= E \rrbracket$ es monótona.

## Parte 2 - Dataflow Analysis
### Ejercicio 8
Recordamos que el reticulado de _reaching definitions_ nos habla de un recorrido **MAY**. Un análisis MAY es aquel que determina propiedades que alguna traza de ejecución fuerza. Es una sobre-aproximación y generalmente usan $(\sqsubseteq, \cup)$. Además, es un recorrido **FORWARD**, es decir que usa los $\text{IN}[n]$ para calcular los $\text{OUT}[n]$, aplicando la función de transferencia $\text{Transfer}$ al conjunto de predecesores $\text{Pred}[n]$ de un nodo $n$.

En el reticulado de reaching definitions, el reticulado es $\mathcal{P}(S) = 2^S$ donde $S$ es el conjunto de instrucciones del programa. En este contexto, decir que $\text{IN}[n] = \{2\}$ es una forma reducida de decir que la instrucción $\{2: x = y\}$ fluye hasta la entrada de un nodo $n$ (que lo alcanza), así como $\text{OUT}[n] = \{2\}$ quiere decir que fluye hasta la salida de ese nodo.

Es decir que el algoritmo caótico iterativo para este reticulado (un caso MAY/FORWARD) estará dado por:

- Inicialmente los conjuntos serán todos $\text{IN}[n] = \text{OUT}[n] = \emptyset$ para todo $n$.
- Se fijan los conjuntos $\text{Pred}[n], \text{Gen}[n], \text{Kill}[n]$ para todo $n$.
- Mientras haya cambios en $\text{IN}[n]$ o $\text{OUT}[n]$ de algún nodo $n$, vamos a realizar cambios para los nodos en orden creciente usando las siguientes reglas:
- $\text{IN}[n] = \displaystyle\bigcup_{p \in \text{Pred}[n]} \text{OUT}[p]$.
- $\text{Transfer}[n](X) = \text{Gen}[n] \cup (X \setminus \text{Kill}[n])$.
- $\text{OUT}[n] = \text{Transfer}[n](\text{IN}[n])$
- En este caso $\text{Gen}[n]$ es $n$ en caso de que su instrucción sea la definición de alguna variable, y $\text{Kill}[n]$ el conjunto de nodos $n' \neq n$ cuyas instrucciones definen la misma variable que $n$.

| Nodo $n$ | $\text{IN}[n]$ | $\text{OUT}[n]$ |
|:-:|:-:|:-:|
| $1$ | $-$ | $\emptyset$ |
| $2$ | $\emptyset$ | $\{2\}$ |
| $3$ | $\{2\}$ | $\{2,3\}$ |
| $4$ | $\{2,3,5,6\}$ | $\{2,3,5,6\}$ |
| $5$ | $\{2,3,5,6\}$ | $\{2,5,6\}$ |
| $6$ | $\{2,5,6\}$ | $\{5,6\}$ |
| $7$ | $\{2,3,5,6\}$ | $\{2,3,5,6\}$ |

- Primera iteración (está explicado muy detalladamente porque es mi primer ejercicio haciendo _reaching definitions_):
- Notar que las iteraciones solamente vale la pena hacerlas a partir de la entrada al primer bucle de una función en adelante, excepto la primera.
- $\text{IN}_1[4] = \{2,3\}$ porque $\text{Pred}[4] = \{3,6\}$ y hasta que no lleguemos al nodo $6$, tenemos $\text{OUT}_0[6] = \emptyset$. Como el nodo $4$ no define ninguna variable, tenemos $\text{Gen}[4] = \text{Kill}[4] = \emptyset$, lo que implica $\text{Transfer}[4](X) = X$ y $\text{OUT}_1[4] = \{2,3\}$.
- $\text{IN}_1[5] = \{2,3\}$ porque $\text{Pred}[5] = 4$. Notar que $\text{Gen}[5] = \{5\}$ y $\text{Kill}[5] = \{3\}$. Por lo tanto $\text{Transfer}[5](X) = X \cup \{5\} \setminus \{3\}$, deduciendo $\text{OUT}_1[5] = \{2,5\}$.
- $\text{IN}_1[6] = \{2,5\}$ porque $\text{Pred}[6] = 5$. Notar que $\text{Gen}[6] = \{6\}$ y $\text{Kill}[6] = \{2\}$. Por lo tanto $\text{Transfer}[6](X) = X \cup \{6\} \setminus \{2\}$, deduciendo $\text{OUT}_1[5] = \{5,6\}$.
- $\text{IN}_1[7] = \{2,3\}$ porque $\text{Pred}[7] = 4$. Como el nodo no define ninguna variable, tendremos $\text{OUT}_1[7] = \{2,3\}$
- Segunda iteración:
- $\text{IN}_2[4] = \{2,3,5,6\} = \text{OUT}_1[3] \cup \text{OUT}_1[6]$, y $\text{OUT}_2[4] = \{2,3,5,6\}$.
- $\text{IN}_2[5] = \{2,3,5,6\}$. Usando $\text{Transfer}[5]$, deducimos $\text{OUT}_2[5] = \{2,5,6\}$.
- $\text{IN}_2[6] = \{2,5,6\}$. Usando $\text{Transfer}[6]$, deducimos $\text{OUT}_2[5] = \{5,6\}$.
- $\text{IN}_2[7] = \{2,3,5,6\}$, ídem para $\text{OUT}_2[7]$.
- Tercera iteración:
- $\text{IN}_3[4] = \{2,3,5,6\} = \text{OUT}_2[3] \cup \text{OUT}_2[6]$, y $\text{OUT}_3[4] = \{2,3,5,6\}$.
- $\text{IN}_3[5] = \{2,3,5,6\}$. Usando $\text{Transfer}[5]$, deducimos $\text{OUT}_3[5] = \{2,5,6\}$.
- $\text{IN}_3[6] = \{2,5,6\}$. Usando $\text{Transfer}[6]$, deducimos $\text{OUT}_3[5] = \{5,6\}$.
- $\text{IN}_3[7] = \{2,3,5,6\}$, ídem para $\text{OUT}_3[7]$.
- No hubo cambios en la tercera iteración, luego obtuvimos los conjuntos $\text{IN}$ y $\text{OUT}$ finales para el ejercicio.

### Ejercicio 9
Fue realizado como explicación del ejercicio anterior.
$$\begin{aligned}
\text{IN}[n](X) &= \displaystyle\bigcup_{p \in \text{Pred}[n]} \text{OUT}[p] \\
\text{OUT}[n](X) &= \text{Transfer}[n](\text{IN}[n]) \\
\text{Transfer}[n](X) &= \text{Gen}[n] \cup (X \setminus \text{Kill}[n])
\end{aligned}$$

### Ejercicio 10
Control-flow graph del programa:

El análisis _live variables_ es **MAY** y **BACKWARD**, es decir que trabaja por sobre-aproximación (usando $\sqsubseteq$ y $\cup$) y usa los $\text{OUT}[n]$ para calcular los $\text{IN}[n]$ (es un recorrido hacia atrás), aplicando la función de transferencia $\text{Transfer}[n]$ al conjunto de sucesores $\text{Succ}[n]$ de un nodo $n$.

En este caso particular, las ecuaciones de flujo de datos son las siguientes:
$$\begin{aligned}
\text{OUT}[n] &= \displaystyle\bigcup_{p \in \text{Succ}[n]} \text{IN}[p] \\
\text{IN}[n] &= \text{Transfer}[n](\text{OUT}[n]) \\
\text{Transfer}[n](X) &= \text{Gen}[n] \cup (X \setminus \text{Kill}[n]),
\end{aligned}$$
donde $\text{Gen}[n]$ es el conjunto de variables leídas en $n$ y $\text{Kill}[n]$ es el conjunto de variables escritas en $n$ (esto parece contra-intuitivo, pero recordar que es un análisis backward). Cuando completamos la siguiente tabla, empezamos por $\text{OUT}[9]$ y vamos hacia arriba.

El conjunto de constantes del programa es $\mathcal{C} = \{MASK, IA, IQ, IR, IM, AM\}$. Luego, la tabla de análisis _live variables_:
| Nodo $n$ | $\text{Succ}[n]$ | $\text{IN}[n]$ | $\text{OUT}[n]$ |
|:-:|:-:|:-:|:-:|
| $1$ | $\{2\}$ | $\{pid\}$ | $\{pid\}$ |
| $2$ | $\{3\}$ | $\{pid\}$ | $\{pid,i\}$ |
| $3$ | $\{4\}$ | $\{pid,i\}$ | $\{pid,k,i\}$ |
| $4$ | $\{5\}$ | $\{pid,k,i\}$ | $\{pid,k,j\}$ |
| $5$ | $\{6\}$ | $\{pid,k,j\}$ | $\{h,pid,k\}$ |
| $6$ | $\{7,8\}$ | $\{h,pid,k\}$ | $\{h,pid,k\}$ |
| $7$ | $\{8\}$ | $\{h,pid,k\}$ | $\{h,pid,k\}$ |
| $8$ | $\{9\}$ | $\{h,pid,k\}$ | $\{answer,pid,k\}$ |
| $9$ | $\emptyset$ | $\{answer,pid,k\}$ | $\emptyset$ |

En caso de que las constantes fueran variables, la tabla de análisis _live variables_ sería:
| Nodo $n$ | $\text{Succ}[n]$ | $\text{IN}[n]$ | $\text{OUT}[n]$ |
|:-:|:-:|:-:|:-:|
| $1$ | $\{2\}$ | $\{AM,IM,pid,MASK,IA,IQ,IR\}$ | $\{AM,IM,pid,MASK,IA,IQ,IR\}$ |
| $2$ | $\{3\}$ | $\{AM,IM,pid,MASK,IA,IQ,IR\}$ | $\{AM,IM,pid,MASK,IA,i,IQ,IR\}$ |
| $3$ | $\{4\}$ | $\{AM,IM,pid,MASK,IA,i,IQ,IR\}$ | $\{AM,IM,pid,k,MASK,IA,i,IQ,IR\}$ |
| $4$ | $\{5\}$ | $\{AM,IM,pid,k,MASK,IA,i,IQ,IR\}$ | $\{AM,IM,pid,k,j,MASK\}$ |
| $5$ | $\{6\}$ | $\{AM,IM,pid,k,j,MASK\}$ | $\{AM,IM,h,pid,k\}$ |
| $6$ | $\{7,8\}$ | $\{AM,IM,h,pid,k\}$ | $\{AM,IM,h,pid,k\}$ |
| $7$ | $\{8\}$ | $\{AM,IM,h,pid,k\}$ | $\{AM,h,pid,k\}$ |
| $8$ | $\{9\}$ | $\{AM,h,pid,k\}$ | $\{answer,pid,k\}$ |
| $9$ | $\emptyset$ | $\{answer,pid,k\}$ | $\emptyset$ |

### Ejercicio 11
El análisis _available expressions_ es **MUST** y **FORWARD**, es decir que trabaja por sub-aproximación (usando $\sqsupseteq$ y $\cap$) y usa los $\text{IN}[n]$ para calcular los $\text{OUT}[n]$ (es un recorrido hacia adelante), aplicando la función de transferencia $\text{Transfer}[n]$ al conjunto de predecesores $\text{Pred}[n]$ de un nodo $n$.

En este caso particular, las ecuaciones de flujo de datos son las siguientes:
$$\begin{aligned}
\text{IN}[n] &= \displaystyle\bigcap_{p \in \text{Pred}[n]} \text{OUT}[p] \\
\text{OUT}[n] &= \text{Transfer}[n](\text{IN}[n]) \\
\text{Transfer}[n](X) &= (X \cup \text{Gen}[n]) \downarrow \text{Kill}[n],
\end{aligned}$$
donde $\text{Gen}[n]$ es la expresión creada en la instrucción del nodo $n$, $\text{Kill}[n]$ son todas las variables escritas en $n$, y $C \downarrow \{x_1, \ldots, x_n\}$ significa eliminar del conjunto $C$ todas las expresiones donde aparece alguno de los $x_i$.

Nota: En el siguiente análisis, se consideran los accesos a arreglos (i.e. $m[i]$) como una expresión. Además, creo que en este caso no vale la pena considerar el nodo salida de la función.

Luego de primera iteración:
| Nodo $n$ | $\text{Pred}[n]$ | $\text{IN}[n]$ | $\text{OUT}[n]$ |
|:-:|:-:|:-:|:-:|
| $1$ | $\emptyset$ | $\emptyset$ | $\{3\}$ |
| $2$ | $\{1\}$ | $\{3\}$ | $\{3,a+2\}$ |
| $3$ | $\{3,8\}$ | $\{3,a+2\}$ | $\{3,a+2\}$ |
| $4$ | $\{4\}$ | $\{3,a+2\}$ | $\{3,a+2,m[i]*a\}$ |
| $5$ | $\{5\}$ | $\{3,a+2,m[i]*a\}$ | $\{3,a+2,t\}$ |
| $6$ | $\{6\}$ | $\{3,a+2,t\}$ | $\{3,a+2,t,i+1\}$ |
| $7$ | $\{7\}$ | $\{3,a+2,t,i+1\}$ | $\{3,a+2,t,j\}$ |
| $8$ | $\{8\}$ | $\{3,a+2,t,j\}$ | $\{3,t,j\}$ |

Luego de segunda iteración:
| Nodo $n$ | $\text{Pred}[n]$ | $\text{IN}[n]$ | $\text{OUT}[n]$ |
|:-:|:-:|:-:|:-:|
| $1$ | $\emptyset$ | $\emptyset$ | $\{3\}$ |
| $2$ | $\{1\}$ | $\{3\}$ | $\{3,a+2\}$ |
| $3$ | $\{3,8\}$ | $\{3,a+2,t,j\}$ | $\{3,a+2,t,j\}$ |
| $4$ | $\{4\}$ | $\{3,a+2,t,j\}$ | $\{3,a+2,m[i]*a,j\}$ |
| $5$ | $\{5\}$ | $\{3,a+2,m[i]*a,j\}$ | $\{3,a+2,j,t\}$ |
| $6$ | $\{6\}$ | $\{3,a+2,j,t\}$ | $\{3,a+2,t,i+1\}$ |
| $7$ | $\{7\}$ | $\{3,a+2,t,i+1\}$ | $\{3,a+2,t,j\}$ |
| $8$ | $\{8\}$ | $\{3,a+2,t,j\}$ | $\{3,t,j\}$ |

Luego de la tercera iteración, la lista se mantendrá igual. Una forma de verlo es que luego de la segunda iteración vale $\text{OUT}_1[3] \cup \text{OUT}_1[8] = \text{OUT}_2[3] \cup \text{OUT}_2[8]$.

### Ejercicio 12
Esta categorización está dada en la clase teórica.


### Ejercicio 13
Control-flow graph del programa:


Recordar que el análisis _live variables_ es MAY y BACKWARD.

| Nodo $n$ | $\text{Succ}[n]$ | $\text{IN}[n]$ | $\text{OUT}[n]$ |
|:-:|:-:|:-:|:-:|
| $1$ | $\{2\}$ | $\emptyset$ | $\{p2,p1\}$ |
| $2$ | $\{3\}$ | $\{p2,p1\}$ | $\{a,p2\}$ |
| $3$ | $\{4\}$ | $\{a,p2\}$ | $\{a,b\}$ |
| $4$ | $\{5\}$ | $\{a,b\}$ | $\{a,b\}$ |
| $5$ | $\{6\}$ | $\{a,b\}$ | $\{y,a,b\}$ |
| $6$ | $\{7,9\}$ | $\{y,a,b\}$ | $\{y,a,b\}$ |
| $7$ | $\{8\}$ | $\{y,a,b\}$ | $\{y,a,b\}$ |
| $8$ | $\{6\}$ | $\{y,a,b\}$ | $\{y,a,b\}$ |
| $9$ | $\emptyset$ | $\emptyset$ | $\emptyset$ |

### Ejercicio 14
Sea $D = \{d: \text{Var} \to \{\bot, S,I\}\}$ donde para todo $x \in \text{Var}$:
- El significado de $d(x) = \bot$ es "no hay información acerca de la sensibilidad de $x$".
- El significado de $d(x) = S$ es "$x$ es sensible".
- El significado de $d(x) = I$ es "$x$ es insensible".

Se puede definir un reticulado $\sqsubseteq$ en $\{\bot,S,I\}$ donde $\bot \sqsubseteq S, \bot \sqsubseteq I$, y donde $S,I$ no son comparables. A su vez, un reticulado $\sqsubseteq_D$ en $D$ de forma que
$$d_1 \sqsubseteq_D d_2 \iff \forall x \in \text{Var}: d_1(x) \sqsubseteq d_2(x),$$
lo que quiere decir "$d_1$ tiene menor o igual sensibilidad en su conjunto de variables que $d_2$". Este reticulado no es completo, ya que ni siquiera $\sqsubseteq$ lo es, pero es un dominio (o poset completo, al igual que $\sqsubseteq$). Esto quiere decir que puede ser utilizado como hipótesis para el Teorema del Punto Fijo.

Bajo el reticulado $(D, \sqsubseteq)$, es razonable que las siguientes funciones se comporten como monótonas (aunque no lo voy a demostrar porque no tengo ganas):
- $\text{sensible}(x): D \to D$.
- $\text{insensible}(x): D \to D$.
- $\text{interaccion}(x,E): D \to D$ para toda expresión $E$ (que incluye algunas variables).

Luego, el Teorema del Punto Fijo nos garantiza que el algoritmo iterativo caótico finalizará (efectivamente, hallando un estado fijo acerca de la sensibilidad de las variables) cuando hagamos un análisis Dataflow sobre programas para calcular sensibilidad de variables.

Al hacer un análisis Dataflow para calcular qué variables pueden ser sensibles, Ahora, observamos que este análisis debe ser:
- Por sobre-aproximación (MAY), ya que basta que exista alguna traza de ejecución donde una variable es sensible en un punto de programa para que la analicemos como potencialmente sensible en ese punto del programa.
- Un recorrido FORWARD, ya que usa qué variables eran sensibles previamente (es decir, _en los predecesores del nodo_) para calcular qué variables son sensibles luego de la instrucción.

Formalmente, el análisis es equivalente al de _reaching definitions_, pero donde $\text{Gen}[n]$ es la nueva variable sensible del nodo (sea $x$ por $\text{sensible}(x)$ o por $\text{interaccion}(x,E)$) y $\text{Kill}[n]$ es la nueva variable insensible del nodo (por $\text{insensible}(X)$):
$$\begin{aligned}
\text{IN}[n](X) &= \displaystyle\bigcup_{p \in \text{Pred}[n]} \text{OUT}[p] \\
\text{OUT}[n](X) &= \text{Transfer}[n](\text{IN}[n]) \\
\text{Transfer}[n](X) &= \text{Gen}[n] \cup (X \setminus \text{Kill}[n])
\end{aligned}$$

| Nodo $n$ | $\text{Pred}[n]$ | $\text{IN}[n]$ | $\text{OUT}[n]$ |
|:-:|:-:|:-:|:-:|
| $1$ | $\emptyset$ | $\emptyset$ | $\emptyset$ |
| $2$ | $\{1\}$ | $\emptyset$ | $\emptyset$ |
| $3$ | $\{2\}$ | $\emptyset$ | $\{x\}$ |
| $4$ | $\{3\}$ | $\{x\}$ | $\{x\}$ |
| $5$ | $\{4\}$ | $\{x\}$ | $\{x,z\}$ |
| $7$ | $\{4\}$ | $\{x\}$ | $\{x\}$ |
| $8$ | $\{5,7\}$ | $\{x,z\} = \{x,z\} \cup \{x\}$ | $\{z\}$ |

### Ejercicio 15
Control-flow graph del programa:


Por lo tanto, en este problema tenemos fijo $\text{Var} = \{x,y,z\}$.

Definiremos un reticulado para trackear igualdad entre variables durante un programa. Siguiendo la hint (aunque creo que lo mejor sería algo que funcione con clases de equivalencia manteniendo una clausura transitiva), usamos $D = \mathcal{P}(\text{Var} \times \text{Var})$ y el reticulado $(D, \subseteq)$. Entonces:
- $\bot_D = \emptyset$ representa el estado donde no se conoce ninguna igualdad.
- $\top_D = \text{Var} \times \text{Var}$ representa el estado donde todas las variables son iguales entre sí.
- Dados $X,Y \in D$, tendremos $X \sqcup Y = X \cap Y$, i.e. será un análisis asociado es de tipo MUST. Esto es porque cuando se combinan dos o más flujos de ejecución, solamente se pueden conservar las igualdades que son válidas en _todos_ esos flujos de ejecución a la vez.

Es claro que será un análisis FORWARD, usando las igualdades de variables que conocemos en los nodos predecesores para calcularlas en los nuevos. Tendremos las siguientes ecuaciones de Dataflow:
- $\text{IN}[n] = \displaystyle\bigcap_{p \in \text{Pred}[n]} \text{OUT}[n]$.
- $\text{OUT}[n] = \text{Transfer}[n](\text{IN}[n]).$
- La función de transferencia es:
- Si $n$ tiene una instrucción de asignación de la forma $x = E$ con $x \in \text{Var}$, es $\text{Transfer}[n](X) = \text{Gen}[n] \cup (X \setminus \text{Kill}[n])$.
- $\text{Kill}[n]$ está compuesto por todos los pares donde alguna de las variables es $x$.
- $\text{Gen}[n]$ está compuesto por los pares $(x,r)$ donde $r = \text{Valor}(E)$.
- En este contexto, la única forma razonable que encontré de hacerlo es tratando a las constantes como variables simbólicas en el programa. Por ejemplo $0$ como $c_0$ y que el problema sea sobre este conjunto extendido de variables.
- Si $n$ tiene otro tipo de instrucción, es $\text{Transfer}[n](d) = d$ (la identidad en $D \to D$, trivialmente monótona).

Al hacer la siguiente tabla, necesitamos un total de $3$ iteraciones del algoritmo iterativo caótico (en la tercera no hay cambios y concluimos que no habrá más cambios).

| Nodo $n$ | $\text{Pred}[n]$ | $\text{IN}[n]$ | $\text{OUT}$[n] |
|:-:|:-:|:-:|:-:|
| $1$ | $\emptyset$ | $\emptyset$ | $\{(y, c_0)\}$ |
| $2$ | $\{1\}$ | $\{(y, c_0)\}$ | $\{(x, c_0), (y, c_0), (x, y)\}$ |
| $3$ | $\{2\}$ | $\{(x, c_0), (y, c_0), (x, y)\}$ | $\{(x, c_0), (y, c_0), (x, y), (z, c_1)\}$ |
| $4$ | $\{3,6,7\}$ | $\{(y, c_0), (z, c_1)\}$ | $\{(y, c_0), (z, c_1)\}$ |
| $5$ | $\{4\}$ | $\{(y, c_0), (z, c_1)\}$ | $\{(y, c_0), (z, c_1), (x, c_1), (x, z)\}$ |
| $6$ | $\{5\}$ | $\{(y, c_0), (z, c_1), (x, c_1), (x, z)\}$ | $\{(y, c_0), (z, c_1), (x, c_1), (x, z)\}$ |
| $7$ | $\{6\}$ | $\{(y, c_0), (z, c_1), (x, c_1), (x, z)\}$ | $\{(y, c_0), (z, c_1), (x, c_0), (x, y)\}$ |

### Ejercicio 16
Es el análisis de signo (igual que en el taller $5$). Luego, es un análisis dataflow MAY y FORWARD.

Vamos a usar el conjunto $\text{Var} = \{x,y,z\}$ y el reticulado $D = \{d: \text{Var} \to \text{Sign}\}$, que tiene:
- Su mínimo total $\bot_D = \{x \to \bot, y \to \bot, z \to \bot\}$.
- Su máximo total $\top_D = \{x \to \top, y \to \top, z \to \top\}$.

Tendremos las siguientes ecuaciones de Dataflow:
- $\text{IN}[n] = \displaystyle\bigsqcup_{p \in \text{Pred}[n]} \text{OUT}[p]$ (es decir la mínima cota superior).
- $\text{OUT}[n] = \text{Transfer[n]}(\text{IN}[n])$.
- La función de transferencia es:
- Si $n$ tiene una instrucción de la forma $v = E$, entonces $\text{Transfer}[n](d)$ reemplaza la función por una exactamente igual $d'$ excepto por la imagen de $v$ que pasa a ser $\text{sign}(E)$. Es claro que esta función es monótona para programas bien definidos.
- El cálculo de las expresiones (por ejemplo $x + 1$ en la instrucción $x = y + 1$) se hace mediante las tablas (por ejemplo la de Suma).
- Si $n$ tiene otro tipo de instrucción, vale $\text{Transfer}[n](d) = d$ (la identidad en $D \to D$, trivialmente monótona).

Al hacer la siguiente tabla, necesitamos un total de $3$ iteraciones del algoritmo iterativo caótico (en la tercera no hay cambios y concluimos que no habrá más cambios).

| Nodo $n$ | $\text{Pred}[n]$ | $\text{IN}[n]$ | $\text{OUT}[n]$ |
|:-:|:-:|:-:|:-:|
| $1$ | $\emptyset$ | $\{x \to \bot, y \to \bot, z \to \bot\}$ | $\{x \to \bot, y \to 0, z \to \bot\}$ |
| $2$ | $\{1\}$ | $\{x \to \bot, y \to 0, z \to \bot\}$ | $\{x \to 0, y \to 0, z \to \bot\}$ |
| $3$ | $\{2\}$ | $\{x \to 0, y \to 0, z \to \bot\}$ | $\{x \to 0, y \to 0, z \to +\}$ |
| $4$ | $\{3,6,7\}$ | $\{x \to \top, y \to 0, z \to +\}$ | $\{x \to \top, y \to 0, z \to +\}$ |
| $5$ | $\{4\}$ | $\{x \to \top, y \to 0, z \to +\}$ | $\{x \to +, y \to 0, z \to +\}$ |
| $6$ | $\{5\}$ | $\{x \to +, y \to 0, z \to +\}$ | $\{x \to +, y \to 0, z \to +\}$ |
| $7$ | $\{6\}$ | $\{x \to +, y \to 0, z \to +\}$ | $\{x \to 0, y \to 0, z \to +\}$ |