compiladores análisis de flujo de datos. 2 resumen overview de análisis de control de flujo...
TRANSCRIPT
![Page 1: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/1.jpg)
Compiladores
Análisis de Flujo de Datos
![Page 2: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/2.jpg)
2
Resumen
• Overview de análisis de control de flujo
• Expresiones disponibles
• Algoritmo para calcular expresiones disponibles
• Bit sets
• Formulando un problema de análisis de flujo de datos
• Cadenas DU
• Forma SSA
![Page 3: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/3.jpg)
3
Representando el control de flujo del progama
• Forma un grafo
• Un grafo muy grande
• Crear Bloques Básicos• Un Grafo de Control de Flujo (CFG) conecta
los Bloques Básicos
![Page 4: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/4.jpg)
4
Grafo de Control de Flujo (CFG)
• Control-Flow Graph G = <N, E>
• Nodos(N): Bloques Básicos
• Edges(E): (x,y) E ssi la primera instrucción en el bloque básico y sigue a la última instrucción en el bloque básico x
![Page 5: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/5.jpg)
5
Identificando loops de estructuras recursivas
• Identificar aristas de retorno• Encontrar los nodos y aristas en el
loop dado por la arista de retorno• Aparte de la arista de retorno
– Aristas entrantes sólo al bloque básico con la cabeza de la arista de retorno
– Una arista saliente del bloque básico a la cola de la arista de retorno
• ¿Cómo encontramos las aristas de retorno?
bb1
bb2
bb4bb3
bb5
bb6
![Page 6: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/6.jpg)
6
Computando Dominators
• Algoritmo– Hacer que el conjunto de dominators del nodo de
entrada sólo contenga ese nodo– Hacer que el conjunto de dominators del resto de
los nodos contenga todos los nodos– Visitar los nodos en cualquier orden– Hacer que el conjunto de dominators del nodo
actual sea la intersección del conjunto de dominators del nodo predecesor y el nodo actual
– Repetir hasta que no hayan cambios
![Page 7: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/7.jpg)
7
Computando Dominators
bb2
bb4bb3
bb5
bb6
{bb1} bb1
• Algoritmo– Hacer que el conjunto de
dominators del nodo de entrada sólo contenga ese nodo
– Hacer que el conjunto de dominators del resto de los nodos contenga todos los nodos
– Visitar los nodos en cualquier orden
– Hacer que el conjunto de dominators del nodo actual sea la intersección del conjunto de dominators del nodo predecesor y el nodo actual
– Repetir hasta que no hayan cambios
![Page 8: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/8.jpg)
8
Computando Dominators
bb2
bb4bb3
bb5
bb6
{bb1} bb1
bb1bb2bb3bb4bb5bb6
bb1bb2bb3bb4bb5bb6
bb1bb2bb3bb4bb5bb6
bb1bb2bb3bb4bb5bb6
bb1bb2bb3bb4bb5bb6
• Algoritmo– Hacer que el conjunto de
dominators del nodo de entrada sólo contenga ese nodo
– Hacer que el conjunto de dominators del resto de los nodos contenga todos los nodos
– Visitar los nodos en cualquier orden
– Hacer que el conjunto de dominators del nodo actual sea la intersección del conjunto de dominators del nodo predecesor y el nodo actual
– Repetir hasta que no hayan cambios
![Page 9: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/9.jpg)
9
Computando Dominators
bb2
bb4bb3
bb5
bb6
{bb1} bb1
bb1bb2bb3bb4bb5bb6
bb1bb2bb3bb4bb5bb6
bb1bb2bb3bb4bb5bb6
bb1bb2bb3bb4bb5bb6
bb1bb2bb3bb4bb5bb6
• Algoritmo– Hacer que el conjunto de
dominators del nodo de entrada sólo contenga ese nodo
– Hacer que el conjunto de dominators del resto de los nodos contenga todos los nodos
– Visitar los nodos en cualquier orden
– Hacer que el conjunto de dominators del nodo actual sea la intersección del conjunto de dominators del nodo predecesor y el nodo actual
– Repetir hasta que no hayan cambios
![Page 10: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/10.jpg)
10
Computando Dominators
bb1
bb2
bb4bb3
bb5
bb6
{bb1}
bb1bb2bb3bb4bb5bb6
bb1bb2bb3bb4bb5bb6
bb1bb2bb3bb4bb5bb6
bb1bb2bb3bb4bb5bb6
bb1bb2bb3bb4bb5bb6
• Algoritmo– Hacer que el conjunto de
dominators del nodo de entrada sólo contenga ese nodo
– Hacer que el conjunto de dominators del resto de los nodos contenga todos los nodos
– Visitar los nodos en cualquier orden
– Hacer que el conjunto de dominators del nodo actual sea la intersección del conjunto de dominators del nodo predecesor y el nodo actual
– Repetir hasta que no hayan cambios
![Page 11: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/11.jpg)
11
Computando Dominators
bb1
bb2
bb4bb3
bb5
bb6
{bb1}
bb1bb2bb3bb4bb5bb6
bb1bb2bb3bb4bb5bb6
bb1bb2bb3bb4bb5bb6
bb1bb2bb3bb4bb5bb6
bb1bb2bb3bb4bb5bb6
• Algoritmo– Hacer que el conjunto de
dominators del nodo de entrada sólo contenga ese nodo
– Hacer que el conjunto de dominators del resto de los nodos contenga todos los nodos
– Visitar los nodos en cualquier orden
– Hacer que el conjunto de dominators del nodo actual sea la intersección del conjunto de dominators del nodo predecesor y el nodo actual
– Repetir hasta que no hayan cambios
![Page 12: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/12.jpg)
12
Computando Dominators
bb1
bb2
bb4bb3
bb5
bb6
{bb1}
bb1bb2bb3bb4bb5bb6
bb1bb2bb3bb4bb5bb6
bb1bb2bb3bb4bb5bb6
bb1bb2bb3bb4bb5bb6
bb1bb2
• Algoritmo– Hacer que el conjunto de
dominators del nodo de entrada sólo contenga ese nodo
– Hacer que el conjunto de dominators del resto de los nodos contenga todos los nodos
– Visitar los nodos en cualquier orden
– Hacer que el conjunto de dominators del nodo actual sea la intersección del conjunto de dominators del nodo predecesor y el nodo actual
– Repetir hasta que no hayan cambios
![Page 13: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/13.jpg)
13
Computando Dominators
bb2
bb4bb3
bb5
bb6
{bb1} bb1
bb1bb2bb3bb4bb5bb6
bb1bb2bb3bb4bb5bb6
bb1bb2bb3bb4bb5bb6
bb1bb2
bb1bb2bb3bb4bb5bb6
• Algoritmo– Hacer que el conjunto de
dominators del nodo de entrada sólo contenga ese nodo
– Hacer que el conjunto de dominators del resto de los nodos contenga todos los nodos
– Visitar los nodos en cualquier orden
– Hacer que el conjunto de dominators del nodo actual sea la intersección del conjunto de dominators del nodo predecesor y el nodo actual
– Repetir hasta que no hayan cambios
![Page 14: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/14.jpg)
14
Computando Dominators
bb2
bb4bb3
bb5
bb6
{bb1} bb1
bb1bb2bb3bb4bb5bb6
bb1bb2bb3bb4bb5bb6
bb1bb2bb3
bb1bb2bb3bb4bb5bb6
bb1bb2
• Algoritmo– Hacer que el conjunto de
dominators del nodo de entrada sólo contenga ese nodo
– Hacer que el conjunto de dominators del resto de los nodos contenga todos los nodos
– Visitar los nodos en cualquier orden
– Hacer que el conjunto de dominators del nodo actual sea la intersección del conjunto de dominators del nodo predecesor y el nodo actual
– Repetir hasta que no hayan cambios
![Page 15: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/15.jpg)
15
Computando Dominators
bb2
bb4bb3
bb5
bb6
{bb1} bb1
bb1bb2bb3bb4bb5bb6
bb1bb2bb3bb4bb5bb6
bb1bb2bb3
bb1bb2
bb1bb2bb3bb4bb5bb6
• Algoritmo– Hacer que el conjunto de
dominators del nodo de entrada sólo contenga ese nodo
– Hacer que el conjunto de dominators del resto de los nodos contenga todos los nodos
– Visitar los nodos en cualquier orden
– Hacer que el conjunto de dominators del nodo actual sea la intersección del conjunto de dominators del nodo predecesor y el nodo actual
– Repetir hasta que no hayan cambios
![Page 16: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/16.jpg)
16
Computando Dominators
bb2
bb4bb3
bb5
bb6
{bb1} bb1
bb1bb2bb3bb4bb5bb6
bb1bb2bb3bb4bb5bb6
bb1bb2bb3
bb1bb2
bb1bb2bb3bb5
• Algoritmo– Hacer que el conjunto de
dominators del nodo de entrada sólo contenga ese nodo
– Hacer que el conjunto de dominators del resto de los nodos contenga todos los nodos
– Visitar los nodos en cualquier orden
– Hacer que el conjunto de dominators del nodo actual sea la intersección del conjunto de dominators del nodo predecesor y el nodo actual
– Repetir hasta que no hayan cambios
![Page 17: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/17.jpg)
17
Computando Dominators
bb2
bb4bb3
bb5
bb6
{bb1} bb1
bb1bb2bb3bb4bb5bb6
bb1bb2bb3bb4bb5bb6
bb1bb2bb3
bb1bb2
bb1bb2bb3bb5
• Algoritmo– Hacer que el conjunto de
dominators del nodo de entrada sólo contenga ese nodo
– Hacer que el conjunto de dominators del resto de los nodos contenga todos los nodos
– Visitar los nodos en cualquier orden
– Hacer que el conjunto de dominators del nodo actual sea la intersección del conjunto de dominators del nodo predecesor y el nodo actual
– Repetir hasta que no hayan cambios
![Page 18: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/18.jpg)
18
Computando Dominators
bb2
bb4bb3
bb5
bb6
{bb1} bb1
bb1bb2bb3bb5bb6
bb1bb2bb3bb4bb5bb6
bb1bb2bb3
bb1bb2
bb1bb2bb3bb5
• Algoritmo– Hacer que el conjunto de
dominators del nodo de entrada sólo contenga ese nodo
– Hacer que el conjunto de dominators del resto de los nodos contenga todos los nodos
– Visitar los nodos en cualquier orden
– Hacer que el conjunto de dominators del nodo actual sea la intersección del conjunto de dominators del nodo predecesor y el nodo actual
– Repetir hasta que no hayan cambios
![Page 19: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/19.jpg)
19
Computando Dominators
bb2
bb4bb3
bb5
bb6
{bb1} bb1
bb1bb2bb3bb5bb6
bb1bb2bb3bb4bb5bb6
bb1bb2bb3
bb1bb2
bb1bb2bb3bb5
• Algoritmo– Hacer que el conjunto de
dominators del nodo de entrada sólo contenga ese nodo
– Hacer que el conjunto de dominators del resto de los nodos contenga todos los nodos
– Visitar los nodos en cualquier orden
– Hacer que el conjunto de dominators del nodo actual sea la intersección del conjunto de dominators del nodo predecesor y el nodo actual
– Repetir hasta que no hayan cambios
![Page 20: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/20.jpg)
20
Computando Dominators
bb2
bb4bb3
bb5
bb6
{bb1} bb1
bb1bb2bb4
bb1bb2bb3
bb1bb2
bb1bb2bb3bb5bb6
bb1bb2bb3bb5
• Algoritmo– Hacer que el conjunto de
dominators del nodo de entrada sólo contenga ese nodo
– Hacer que el conjunto de dominators del resto de los nodos contenga todos los nodos
– Visitar los nodos en cualquier orden
– Hacer que el conjunto de dominators del nodo actual sea la intersección del conjunto de dominators del nodo predecesor y el nodo actual
– Repetir hasta que no hayan cambios
![Page 21: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/21.jpg)
21
Computando Dominators
bb2
bb4bb3
bb5
bb6
{bb1} bb1
bb1bb2bb4
bb1bb2bb3
bb1bb2
bb1bb2bb3bb5bb6
bb1bb2bb3bb5
• Algoritmo– Hacer que el conjunto de
dominators del nodo de entrada sólo contenga ese nodo
– Hacer que el conjunto de dominators del resto de los nodos contenga todos los nodos
– Visitar los nodos en cualquier orden
– Hacer que el conjunto de dominators del nodo actual sea la intersección del conjunto de dominators del nodo predecesor y el nodo actual
– Repetir hasta que no hayan cambios
![Page 22: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/22.jpg)
22
Computando Dominators
bb2
bb4bb3
bb5
bb6
{bb1} bb1
bb1bb2bb4
bb1bb2bb3
bb1bb2
bb1bb2bb3bb5bb6
bb1bb2bb3bb5
• Algoritmo– Hacer que el conjunto de
dominators del nodo de entrada sólo contenga ese nodo
– Hacer que el conjunto de dominators del resto de los nodos contenga todos los nodos
– Visitar los nodos en cualquier orden
– Hacer que el conjunto de dominators del nodo actual sea la intersección del conjunto de dominators del nodo predecesor y el nodo actual
– Repetir hasta que no hayan cambios
![Page 23: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/23.jpg)
23
Computando Dominators
bb2
bb4bb3
bb5
bb6
{bb1} bb1
bb1bb2bb4
bb1bb2bb3
bb1bb2
bb1bb2bb3bb5bb6
bb1bb2bb3bb5
• Algoritmo– Hacer que el conjunto de
dominators del nodo de entrada sólo contenga ese nodo
– Hacer que el conjunto de dominators del resto de los nodos contenga todos los nodos
– Visitar los nodos en cualquier orden
– Hacer que el conjunto de dominators del nodo actual sea la intersección del conjunto de dominators del nodo predecesor y el nodo actual
– Repetir hasta que no hayan cambios
![Page 24: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/24.jpg)
24
Computando Dominators
bb2
bb4bb3
bb5
bb6
{bb1} bb1
bb1bb2bb4
bb1bb2bb3
bb1bb2
bb1bb2bb3bb5bb6
bb1bb2bb3bb5
• Algoritmo– Hacer que el conjunto de
dominators del nodo de entrada sólo contenga ese nodo
– Hacer que el conjunto de dominators del resto de los nodos contenga todos los nodos
– Visitar los nodos en cualquier orden
– Hacer que el conjunto de dominators del nodo actual sea la intersección del conjunto de dominators del nodo predecesor y el nodo actual
– Repetir hasta que no hayan cambios
![Page 25: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/25.jpg)
25
Computando Dominators
bb2
bb4bb3
bb5
bb6
{bb1} bb1
bb1bb2bb4
bb1bb2bb3
bb1bb2
bb1bb2bb3bb5bb6
bb1bb2bb3bb5
• Algoritmo– Hacer que el conjunto de
dominators del nodo de entrada sólo contenga ese nodo
– Hacer que el conjunto de dominators del resto de los nodos contenga todos los nodos
– Visitar los nodos en cualquier orden
– Hacer que el conjunto de dominators del nodo actual sea la intersección del conjunto de dominators del nodo predecesor y el nodo actual
– Repetir hasta que no hayan cambios
![Page 26: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/26.jpg)
26
Computando Dominators
bb2
bb4bb3
bb5
bb6
{bb1} bb1
bb1bb2bb4
bb1bb2bb3
bb1bb2
bb1bb2bb3bb5bb6
bb1bb2bb5
• Algoritmo– Hacer que el conjunto de
dominators del nodo de entrada sólo contenga ese nodo
– Hacer que el conjunto de dominators del resto de los nodos contenga todos los nodos
– Visitar los nodos en cualquier orden
– Hacer que el conjunto de dominators del nodo actual sea la intersección del conjunto de dominators del nodo predecesor y el nodo actual
– Repetir hasta que no hayan cambios
![Page 27: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/27.jpg)
27
Computando Dominators
bb2
bb4bb3
bb5
bb6
{bb1} bb1
bb1bb2bb4
bb1bb2bb3
bb1bb2
bb1bb2bb3bb5bb6
bb1bb2bb5
• Algoritmo– Hacer que el conjunto de
dominators del nodo de entrada sólo contenga ese nodo
– Hacer que el conjunto de dominators del resto de los nodos contenga todos los nodos
– Visitar los nodos en cualquier orden
– Hacer que el conjunto de dominators del nodo actual sea la intersección del conjunto de dominators del nodo predecesor y el nodo actual
– Repetir hasta que no hayan cambios
![Page 28: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/28.jpg)
28
Computando Dominators
bb2
bb4bb3
bb5
bb6
{bb1} bb1
bb1bb2bb4
bb1bb2bb3
bb1bb2
bb1bb2bb5bb6
bb1bb2bb5
• Algoritmo– Hacer que el conjunto de
dominators del nodo de entrada sólo contenga ese nodo
– Hacer que el conjunto de dominators del resto de los nodos contenga todos los nodos
– Visitar los nodos en cualquier orden
– Hacer que el conjunto de dominators del nodo actual sea la intersección del conjunto de dominators del nodo predecesor y el nodo actual
– Repetir hasta que no hayan cambios
![Page 29: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/29.jpg)
29
Computando Dominators
bb2
bb4bb3
bb5
bb6
{bb1} bb1
bb1bb2bb4
bb1bb2bb3
bb1bb2
bb1bb2bb5bb6
bb1bb2bb5
• Algoritmo– Hacer que el conjunto de
dominators del nodo de entrada sólo contenga ese nodo
– Hacer que el conjunto de dominators del resto de los nodos contenga todos los nodos
– Visitar los nodos en cualquier orden
– Hacer que el conjunto de dominators del nodo actual sea la intersección del conjunto de dominators del nodo predecesor y el nodo actual
– Repetir hasta que no hayan cambios
![Page 30: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/30.jpg)
30
Computando Dominators
bb2
bb4bb3
bb5
bb6
{bb1} bb1
bb1bb2bb4
bb1bb2bb3
bb1bb2
bb1bb2bb5bb6
bb1bb2bb5
• Algoritmo– Hacer que el conjunto de
dominators del nodo de entrada sólo contenga ese nodo
– Hacer que el conjunto de dominators del resto de los nodos contenga todos los nodos
– Visitar los nodos en cualquier orden
– Hacer que el conjunto de dominators del nodo actual sea la intersección del conjunto de dominators del nodo predecesor y el nodo actual
– Repetir hasta que no hayan cambios
![Page 31: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/31.jpg)
31
Computando Dominators
bb2
bb4bb3
bb5
bb6
{bb1} bb1
bb1bb2bb4
bb1bb2bb3
bb1bb2
bb1bb2bb5bb6
bb1bb2bb5
• Algoritmo– Hacer que el conjunto de
dominators del nodo de entrada sólo contenga ese nodo
– Hacer que el conjunto de dominators del resto de los nodos contenga todos los nodos
– Visitar los nodos en cualquier orden
– Hacer que el conjunto de dominators del nodo actual sea la intersección del conjunto de dominators del nodo predecesor y el nodo actual
– Repetir hasta que no hayan cambios
![Page 32: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/32.jpg)
32
Computando Dominators
bb2
bb4bb3
bb5
bb6
{bb1} bb1
bb1bb2bb4
bb1bb2bb3
bb1bb2
bb1bb2bb5bb6
bb1bb2bb5
• Algoritmo– Hacer que el conjunto de
dominators del nodo de entrada sólo contenga ese nodo
– Hacer que el conjunto de dominators del resto de los nodos contenga todos los nodos
– Visitar los nodos en cualquier orden
– Hacer que el conjunto de dominators del nodo actual sea la intersección del conjunto de dominators del nodo predecesor y el nodo actual
– Repetir hasta que no hayan cambios
![Page 33: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/33.jpg)
33
Computando Dominators
bb2
bb4bb3
bb5
bb6
{bb1} bb1
bb1bb2bb4
bb1bb2bb3
bb1bb2
bb1bb2bb5bb6
bb1bb2bb5
• Algoritmo– Hacer que el conjunto de
dominators del nodo de entrada sólo contenga ese nodo
– Hacer que el conjunto de dominators del resto de los nodos contenga todos los nodos
– Visitar los nodos en cualquier orden
– Hacer que el conjunto de dominators del nodo actual sea la intersección del conjunto de dominators del nodo predecesor y el nodo actual
– Repetir hasta que no hayan cambios
![Page 34: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/34.jpg)
34
Computando Dominators
bb2
bb4bb3
bb5
bb6
{bb1} bb1
bb1bb2bb4
bb1bb2bb3
bb1bb2
bb1bb2bb5bb6
bb1bb2bb5
• Algoritmo– Hacer que el conjunto de
dominators del nodo de entrada sólo contenga ese nodo
– Hacer que el conjunto de dominators del resto de los nodos contenga todos los nodos
– Visitar los nodos en cualquier orden
– Hacer que el conjunto de dominators del nodo actual sea la intersección del conjunto de dominators del nodo predecesor y el nodo actual
– Repetir hasta que no hayan cambios
![Page 35: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/35.jpg)
35
Computando Dominators
bb2
bb4bb3
bb5
bb6
{bb1} bb1
bb1bb2bb4
bb1bb2bb3
bb1bb2
bb1bb2bb5bb6
bb1bb2bb5
• Algoritmo– Hacer que el conjunto de
dominators del nodo de entrada sólo contenga ese nodo
– Hacer que el conjunto de dominators del resto de los nodos contenga todos los nodos
– Visitar los nodos en cualquier orden
– Hacer que el conjunto de dominators del nodo actual sea la intersección del conjunto de dominators del nodo predecesor y el nodo actual
– Repetir hasta que no hayan cambios
![Page 36: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/36.jpg)
36
Computando Dominators
bb2
bb4bb3
bb5
bb6
{bb1} bb1
bb1bb2bb4
bb1bb2bb3
bb1bb2
bb1bb2bb5bb6
bb1bb2bb5
• Algoritmo– Hacer que el conjunto de
dominators del nodo de entrada sólo contenga ese nodo
– Hacer que el conjunto de dominators del resto de los nodos contenga todos los nodos
– Visitar los nodos en cualquier orden
– Hacer que el conjunto de dominators del nodo actual sea la intersección del conjunto de dominators del nodo predecesor y el nodo actual
– Repetir hasta que no hayan cambios
![Page 37: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/37.jpg)
37
Computando Dominators
bb2
bb4bb3
bb5
bb6
{bb1} bb1
bb1bb2bb4
bb1bb2bb3
bb1bb2
bb1bb2bb5bb6
bb1bb2bb5
• Algoritmo– Hacer que el conjunto de
dominators del nodo de entrada sólo contenga ese nodo
– Hacer que el conjunto de dominators del resto de los nodos contenga todos los nodos
– Visitar los nodos en cualquier orden
– Hacer que el conjunto de dominators del nodo actual sea la intersección del conjunto de dominators del nodo predecesor y el nodo actual
– Repetir hasta que no hayan cambios
![Page 38: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/38.jpg)
38
Computando Dominators
• Lo que acabamos de ver fue un algoritmo iterativo de análisis de flujo de datos en acción– Inicializar todos los nodos a un valor dado– Visitar los nodos en algún orden– Calcular el valor del nodo– Repetir hasta que no haya cambios
![Page 39: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/39.jpg)
39
Análisis de Flujo de Datos
• Análisis Local– Analizar el efecto de cada instrucción– Componer efectos de instrucciones para derivar
información desde el principio del bloque básico a cada instrucción
• Análisis de Flujo de Datos– Iterativamente propagar la información del bloque básico
sobre el grafo de control de flujo hasta que no hayan cambios
– Calcular el valor final al principio del bloque básico
• Propagación Local– Propagar la información desde el principio del bloque
básico a cada instrucción
![Page 40: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/40.jpg)
40
Resumen
• Overview de análisis de control de flujo
• Expresiones disponibles
• Algoritmo para calcular expresiones disponibles
• Bit sets
• Formulando un problema de análisis de flujo de datos
• Cadenas DU
• Forma SSA
![Page 41: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/41.jpg)
41
Ejemplo: Expresiones Disponibles
• Una expresión está disponible ssi– Todos los caminos que llegan al punto actual
pasan a través del punto donde se definió la expresión
– Ninguna variable usada en la expresión fue modificada entre el punto en que se definió la expresión y el punto actual
![Page 42: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/42.jpg)
42
Ejemplo: Expresiones Disponibles
a = b + cd = e + ff = a + c
g = a + c
j = a + b + c + d
b = a + dh = c + f
![Page 43: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/43.jpg)
43
¿Está la expresión disponible?
a = b + cd = e + ff = a + c
g = a + c
j = a + b + c + d
b = a + dh = c + f
Sí!
![Page 44: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/44.jpg)
44
¿Está la expresión disponible?
a = b + cd = e + ff = a + c
g = a + c
j = a + b + c + d
b = a + dh = c + f
Sí!
![Page 45: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/45.jpg)
45
¿Está la expresión disponible?
a = b + cd = e + ff = a + c
g = a + c
j = a + b + c + d
b = a + dh = c + f
No!
![Page 46: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/46.jpg)
46
¿Está la expresión disponible?
a = b + cd = e + ff = a + c
g = a + c
j = a + b + c + d
b = a + dh = c + f
No!
![Page 47: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/47.jpg)
47
¿Está la expresión disponible?
a = b + cd = e + ff = a + c
g = a + c
j = a + b + c + d
b = a + dh = c + f
No!
![Page 48: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/48.jpg)
48
¿Está la expresión disponible?
a = b + cd = e + ff = a + c
g = a + c
j = a + b + c + d
b = a + dh = c + f
Sí!
![Page 49: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/49.jpg)
49
¿Está la expresión disponible?
a = b + cd = e + ff = a + c
g = a + c
j = a + b + c + d
b = a + dh = c + f
Sí!
![Page 50: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/50.jpg)
50
Uso de Expresiones Disponibles
a = b + cd = e + ff = a + c
g = a + c
j = a + b + c + d
b = a + dh = c + f
![Page 51: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/51.jpg)
51
Uso de Expresiones Disponibles
a = b + cd = e + ff = a + c
g = a + c
j = a + b + c + d
b = a + dh = c + f
![Page 52: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/52.jpg)
52
Uso de Expresiones Disponibles
a = b + cd = e + ff = a + c
g = a + c
j = a + b + c + d
b = a + dh = c + f
![Page 53: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/53.jpg)
53
Uso de Expresiones Disponibles
a = b + cd = e + ff = a + c
g = f
j = a + b + c + d
b = a + dh = c + f
![Page 54: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/54.jpg)
54
Uso de Expresiones Disponibles
a = b + cd = e + ff = a + c
g = f
j = a + b + c + d
b = a + dh = c + f
![Page 55: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/55.jpg)
55
Uso de Expresiones Disponibles
a = b + cd = e + ff = a + c
g = f
j = a + c + b + d
b = a + dh = c + f
![Page 56: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/56.jpg)
56
Uso de Expresiones Disponibles
a = b + cd = e + ff = a + c
g = f
j = f + b + d
b = a + dh = c + f
![Page 57: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/57.jpg)
57
Uso de Expresiones Disponibles
a = b + cd = e + ff = a + c
g = f
j = f + b + d
b = a + dh = c + f
![Page 58: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/58.jpg)
58
Resumen
• Overview de análisis de control de flujo• Expresiones Disponibles• Algoritmo para calcular expresiones
disponibles• Bit sets• Formulando un problema de análisis de flujo
de datos• Cadenas DU• Forma SSA
5
![Page 59: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/59.jpg)
59
Algoritmo para Expresiones Disponibles
• Asignar un número a cada expresión
![Page 60: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/60.jpg)
60
b = a + d h = c + f
g = a + c
Ejemplo: Expresiones Disponibles
a = b + cd = e + ff = a + c
j = a + b + c + d
![Page 61: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/61.jpg)
61
b = a + d h = c + f
g = a + c
Ejemplo: Expresiones Disponibles
a = b + cd = e + ff = a + c
j = a + b + c + d
123
456
7
![Page 62: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/62.jpg)
62
Conjuntos Gen y Kill
• Conjunto Gen– Si el bloque básico actual (o instrucción) crea la
definición, está en el conjunto gen– El elemento debe estar en la salida del bloque
básico siempre
• Conjunto Kill– Si el bloque básico actual (o instrucción)
redefine una variable en la expresión, está en el conjunto kill
– La expresión no es válida después de esto
![Page 63: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/63.jpg)
63
Algoritmo para Expresiones Disponibles
• Asignar un número a cada expresión
• Calcular conjuntos gen y kill para cada expresión
15
![Page 64: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/64.jpg)
64
Conjuntos Gen y Kill
a = b + c 1d = e + f 2f = a + c 3
g = a + c 4
j = a + b + c + d 7
b = a + d 5h = c + f 6
![Page 65: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/65.jpg)
65
Conjuntos Gen y Kill
a = b + c 1
d = e + f 2
f = a + c 3
a = b + c 1d = e + f 2f = a + c 3
g = a + c 4
j = a + b + c + d 7
b = a + d 5h = c + f 6
![Page 66: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/66.jpg)
66
a = b + c 1
gen = { b + c }
kill = { cualquier expr con a }
d = e + f 2
gen = { e + f }
kill = { cualquier expr con d }
f = a + c 3
gen = { a + c }
kill = {cualquier expr con f }
Conjuntos Gen y Kill
a = b + c 1d = e + f 2f = a + c 3
g = a + c 4
j = a + b + c + d 7
b = a + d 5h = c + f 6
![Page 67: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/67.jpg)
67
a = b + c 1
gen = { 1 }
kill = { 3, 4, 5, 7 }
d = e + f 2
gen = { 2 }
kill = { 5, 7 }
f = a + c 3
gen = { 3 }
kill = { 2, 6 }
Conjuntos Gen y Kill
a = b + c 1d = e + f 2f = a + c 3
g = a + c 4
j = a + b + c + d 7
b = a + d 5h = c + f 6
![Page 68: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/68.jpg)
68
Algoritmo para Expresiones Disponibles
• Asignarle un número a cada expresión
• Calcular conjuntos gen y kill para cada expresión
• Calcular conjuntos gen y kill agregados para cada bloque básico
16
![Page 69: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/69.jpg)
69
Conjuntos Gen y Kill agregados
a = b + c 1
gen = { 1 }
kill = { 3, 4, 5, 7 }
d = e + f 2
gen = { 2 }
kill = { 5, 7 }
f = a + c 3
gen = { 3 }
kill = { 2, 6 }
• Propagar todos los conjuntos gen y kill desde el comienzo del bloque básico hasta el final del bloque básico
![Page 70: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/70.jpg)
70
Conjunto Gen agregado
a = b + c 1
gen = { 1 }
kill = { 3, 4, 5, 7 }
InGEN set
OutGEN set
OutGEN =
![Page 71: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/71.jpg)
71
Conjunto Gen agregado
a = b + c 1
gen = { 1 }
kill = { 3, 4, 5, 7 }
InGEN set
OutGEN set
• El conjunto gen en la expresión actual debe estar en el conjunto OutGEN
OutGEN = gen
![Page 72: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/72.jpg)
72
Conjunto Gen agregado
a = b + c 1
gen = { 1 }
kill = { 3, 4, 5, 7 }
InGEN set
OutGEN set
• El conjunto gen en la expresión actual debe estar en el conjunto OutGEN
• Cualquier expresión en el conjunto InGEN que no está en el conjunto kill debe estar en el conjunto OutGEN
OutGEN = gen (InGEN - kill)
![Page 73: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/73.jpg)
73
Conjunto Gen agregado
a = b + c 1
gen = { 1 }kill = { 3, 4, 5, 7 }
d = e + f 2gen = { 2 }kill = { 5, 7 }
f = a + c 3gen = { 3 }kill = { 2, 6 }
![Page 74: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/74.jpg)
74
Conjunto Gen agregadoInGEN = { }
a = b + c 1gen = { 1 }kill = { 3, 4, 5, 7 }
OutGEN = gen (InGEN - kill)
d = e + f 2gen = { 2 }kill = { 5, 7 }
f = a + c 3gen = { 3 }kill = { 2, 6 }
![Page 75: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/75.jpg)
75
Conjunto Gen agregadoInGEN = { }
a = b + c 1gen = { 1 }kill = { 3, 4, 5, 7 }
OutGEN = { 1 } ({ } - { 3,4,5,7})
d = e + f 2gen = { 2 }kill = { 5, 7 }
f = a + c 3gen = { 3 }kill = { 2, 6 }
![Page 76: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/76.jpg)
76
Conjunto Gen agregadoInGEN = { }
a = b + c 1gen = { 1 }kill = { 3, 4, 5, 7 }
OutGEN = { 1 }
d = e + f 2gen = { 2 }kill = { 5, 7 }
f = a + c 3gen = { 3 }kill = { 2, 6 }
![Page 77: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/77.jpg)
77
Conjunto Gen agregado
a = b + c 1gen = { 1 }kill = { 3, 4, 5, 7 }
InGEN = { 1 }
d = e + f 2gen = { 2 }kill = { 5, 7 }
OutGEN = gen (InGEN - kill)
f = a + c 3gen = { 3 }kill = { 2, 6 }
![Page 78: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/78.jpg)
78
Conjunto Gen agregado
a = b + c 1gen = { 1 }kill = { 3, 4, 5, 7 }
InGEN = { 1 }
d = e + f 2gen = { 2 }kill = { 5, 7 }
OutGEN = { 2 } ({ 1 } - { 5,7 })
f = a + c 3gen = { 3 }kill = { 2, 6 }
![Page 79: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/79.jpg)
79
Conjunto Gen agregado
a = b + c 1gen = { 1 }kill = { 3, 4, 5, 7 }
InGEN = { 1 }
d = e + f 2gen = { 2 }kill = { 5, 7 }
OutGEN = { 1, 2 }
f = a + c 3gen = { 3 }kill = { 2, 6 }
![Page 80: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/80.jpg)
80
Conjunto Gen agregado
a = b + c 1gen = { 1 }kill = { 3, 4, 5, 7 }
d = e + f 2gen = { 2 }kill = { 5, 7 }
InGEN = { 1, 2 }
f = a + c 3gen = { 3 }kill = { 2, 6 }
OutGEN = gen (InGEN - kill)
![Page 81: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/81.jpg)
81
Conjunto Gen agregado
a = b + c 1gen = { 1 }kill = { 3, 4, 5, 7 }
d = e + f 2gen = { 2 }kill = { 5, 7 }
InGEN = { 1, 2 }
f = a + c 3gen = { 3 }kill = { 2, 6 }
OutGEN = { 3 } ({ 1,2 } - { 2,6 })
![Page 82: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/82.jpg)
82
Conjunto Gen agregado
A = b + c 1gen = { 1 }kill = { 3, 4, 5, 7 }
d = e + f 2gen = { 2 }kill = { 5, 7 }
InGEN = { 1, 2 }
f = a + c 3gen = { 3 }kill = { 2, 6 }
OutGEN = { 1, 3 }
![Page 83: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/83.jpg)
83
Conjunto Gen agregado
A = b + c 1gen = { 1 }kill = { 3, 4, 5, 7 }
d = e + f 2gen = { 2 }kill = { 5, 7 }
f = a + c 3gen = { 3 }kill = { 2, 6 }
GE
N =
{ 1
, 3 }
![Page 84: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/84.jpg)
84
Conjunto Kill agregado
a = b + c 1
gen = { 1 }
kill = { 3, 4, 5, 7 }
InKILL set
OutKILL set
OutKILL =
![Page 85: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/85.jpg)
85
Conjunto Kill agregado
a = b + c 1
gen = { 1 }
kill = { 3, 4, 5, 7 }
InKILL set
OutKILL set
• El conjunto kill de la expresión actual debe estar en el conjunto OutKILL
OutKILL = kill
![Page 86: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/86.jpg)
86
Conjunto Kill agregado
a = b + c 1
gen = { 1 }
kill = { 3, 4, 5, 7 }
InKILL set
OutKILL set
• El conjunto kill de la expresión actual debe estar en el conjunto OutKILL
• Cualquier conjunto en el InKILL debe estar en el OutKILL
OutKILL = kill InKILL
![Page 87: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/87.jpg)
87
Conjunto Kill agregado
a = b + c 1gen = { 1 }kill = { 3, 4, 5, 7 }
d = e + f 2gen = { 2 }kill = { 5, 7 }
f = a + c 3gen = { 3 }kill = { 2, 6 }
![Page 88: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/88.jpg)
88
Conjunto Kill agregadoInKILL = { }
a = b + c 1gen = { 1 }kill = { 3, 4, 5, 7 }
OutKILL = kill InKILL
d = e + f 2gen = { 2 }kill = { 5, 7 }
f = a + c 3gen = { 3 }kill = { 2, 6 }
![Page 89: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/89.jpg)
89
Conjunto Kill agregadoInKILL = { }
a = b + c 1gen = { 1 }kill = { 3, 4, 5, 7 }
OutKILL = { 3,4,5,7 } { }
d = e + f 2gen = { 2 }kill = { 5, 7 }
f = a + c 3gen = { 3 }kill = { 2, 6 }
![Page 90: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/90.jpg)
90
Conjunto Kill agregadoInKILL = { }
a = b + c 1gen = { 1 }kill = { 3, 4, 5, 7 }
OutKILL = { 3,4,5,7 }
d = e + f 2gen = { 2 }kill = { 5, 7 }
f = a + c 3gen = { 3 }kill = { 2, 6 }
![Page 91: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/91.jpg)
91
Conjunto Kill agregado
a = b + c 1gen = { 1 }kill = { 3, 4, 5, 7 }
InKILL = { 3,4,5,7 }
d = e + f 2gen = { 2 }kill = { 5, 7 }
OutKILL = kill InKILL
f = a + c 3gen = { 3 }kill = { 2, 6 }
![Page 92: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/92.jpg)
92
Conjunto Kill agregado
a = b + c 1gen = { 1 }kill = { 3, 4, 5, 7 }
InKILL = { 3,4,5,7 }
d = e + f 2gen = { 2 }kill = { 5, 7 }
OutKILL = { 5,7 } { 3,4,5,7 }
f = a + c 3gen = { 3 }kill = { 2, 6 }
![Page 93: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/93.jpg)
93
Conjunto Kill agregado
a = b + c 1gen = { 1 }kill = { 3, 4, 5, 7 }
InKILL = { 3,4,5,7 }
d = e + f 2gen = { 2 }kill = { 5, 7 }
OutKILL = { 3,4,5,7 }
f = a + c 3gen = { 3 }kill = { 2, 6 }
![Page 94: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/94.jpg)
94
Conjunto Kill agregado
a = b + c 1gen = { 1 }kill = { 3, 4, 5, 7 }
d = e + f 2gen = { 2 }kill = { 5, 7 }
InKILL = { 3,4,5,7 }
f = a + c 3gen = { 3 }kill = { 2, 6 }
OutKILL = kill InKILL
![Page 95: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/95.jpg)
95
Conjunto Kill agregado
a = b + c 1gen = { 1 }kill = { 3, 4, 5, 7 }
d = e + f 2gen = { 2 }kill = { 5, 7 }
InKILL = { 3,4,5,7 }
f = a + c 3gen = { 3 }kill = { 2, 6 }
OutKILL = { 3,4,5,7 } { 2,6 }
![Page 96: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/96.jpg)
96
Conjunto Kill agregado
a = b + c 1gen = { 1 }kill = { 3, 4, 5, 7 }
d = e + f 2gen = { 2 }kill = { 5, 7 }
InKILL = { 3,4,5,7 }
f = a + c 3gen = { 3 }kill = { 2, 6 }
OutKILL = { 2,3,4,5,6,7 }
![Page 97: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/97.jpg)
97
Conjunto Kill agregado
a = b + c 1gen = { 1 }kill = { 3, 4, 5, 7 }
d = e + f 2gen = { 2 }kill = { 5, 7 }
f = a + c 3gen = { 3 }kill = { 2, 6 }
KIL
L =
{ 2
, 3, 4
, 5, 6
, 7 }
![Page 98: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/98.jpg)
98
Conjuntos Gen y Kill agregados
a = b + c 1d = e + f 2f = a + c 3
g = a + c 4
j = a + b + c + d 7
b = a + d 5h = c + f 6
Gen = { 1, 3}Kill = { 2,3,4,5,6,7 }
Gen = { 4 }Kill = { }
Gen = { 5, 6 }Kill = { 1, 7 }
Gen = { 7 }Kill = { }
![Page 99: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/99.jpg)
99
Algoritmo para Expresiones Disponibles
• Asignar un número a cada expresión
• Calcular conjuntos gen y kill para cada instrucción
• Calcular conjuntos gen y kill agregados para cada bloque básico
• Inicializar conjunto de disponibles de cada bloque básico con todas las expresiones
20
![Page 100: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/100.jpg)
100
Conjuntos Gen y Kill agregados
a = b + c 1d = e + f 2f = a + c 3
g = a + c 4
j = a + b + c + d 7
b = a + d 5h = c + f 6
Gen = { 1, 3}Kill = { 2,3,4,5,6,7 }
Gen = { 4 }Kill = { }
Gen = { 5, 6 }Kill = { 1, 7 }
Gen = { 7 }Kill = { }
IN = {1,2,3,4,5,6,7}
IN = {1,2,3,4,5,6,7}IN = {1,2,3,4,5,6,7}
IN = {1,2,3,4,5,6,7}
OUT = {1,2,3,4,5,6,7}
OUT = {1,2,3,4,5,6,7} OUT = {1,2,3,4,5,6,7}
OUT = {1,2,3,4,5,6,7}
![Page 101: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/101.jpg)
101
Algoritmo para Expresiones Disponibles
• Asignar un número a cada expresión
• Calcular conjuntos gen y kill para cada instrucción
• Calcular conjuntos gen y kill agregados para cada bloque básico
• Inicializar conjunto de disponibles de cada bloque básico con todas las expresiones
• Iterativamente propagar el conjunto de expresiones disponibles por el CFG
![Page 102: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/102.jpg)
102
Propagar conjunto de disponibles
gen = { … }
kill = { ... }
IN set
OUT set
OUT =
![Page 103: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/103.jpg)
103
Propagar conjunto de disponibles
gen = { … }
kill = { ... }
IN set
OUT set
• Si la expresión es generada (en el conjunto gen) entonces está disponible al final– Debe estar en el conjunto OUT
OUT = gen
![Page 104: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/104.jpg)
104
Propagar conjunto de disponibles
gen = { … }
kill = { ... }
IN set
OUT set
• Si la expresión es generada (en el conjunto gen) entonces está disponible al final– Debe estar en el conjunto OUT
• Cualquier expresión disponible en la entrada (en el conjunto IN) y que no está en el conjunto kill debe estar disponible al final
OUT = gen (IN - kill)
![Page 105: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/105.jpg)
105
Propagar conjunto de disponibles
IN set
OUT = gen (IN - kill)
OUT set OU
T se
t
IN =
![Page 106: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/106.jpg)
106
Propagar conjunto de disponibles
IN set
• La expresión está disponible sólo está disponible en todos los caminos de entrada
OUT = gen (IN - kill)
OUT set OU
T se
t
IN = OUT
![Page 107: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/107.jpg)
107
Conjuntos Gen y Kill agregados
a = b + c 1d = e + f 2f = a + c 3
g = a + c 4
j = a + b + c + d 7
b = a + d 5h = c + f 6
Gen = { 1, 3}Kill = { 2,3,4,5,6,7 }
Gen = { 4 }Kill = { }
Gen = { 5, 6 }Kill = { 1, 7 }
Gen = { 7 }Kill = { }
IN = {1,2,3,4,5,6,7}
IN = {1,2,3,4,5,6,7}IN = {1,2,3,4,5,6,7}
IN = {1,2,3,4,5,6,7}
OUT = {1,2,3,4,5,6,7}
OUT = {1,2,3,4,5,6,7} OUT = {1,2,3,4,5,6,7}
OUT = {1,2,3,4,5,6,7}
OUT = gen (IN - kill)
IN = OUT
![Page 108: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/108.jpg)
108
Conjuntos Gen y Kill agregados
g = a + c 4
j = a + b + c + d 7
b = a + d 5h = c + f 6
Gen = { 1, 3}Kill = { 2,3,4,5,6,7 }
Gen = { 4 }Kill = { }
Gen = { 5, 6 }Kill = { 1, 7 }
Gen = { 7 }Kill = { }
IN = {1,2,3,4,5,6,7}
IN = {1,2,3,4,5,6,7}IN = {1,2,3,4,5,6,7}
IN = {1,2,3,4,5,6,7}
OUT = {1,2,3,4,5,6,7}
OUT = {1,2,3,4,5,6,7} OUT = {1,2,3,4,5,6,7}
OUT = {1,2,3,4,5,6,7}
OUT = gen (IN - kill)
IN = OUTa = b + c 1d = e + f 2f = a + c 3
![Page 109: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/109.jpg)
109
Conjuntos Gen y Kill agregados
g = a + c 4
j = a + b + c + d 7
b = a + d 5h = c + f 6
Gen = { 1, 3}Kill = { 2,3,4,5,6,7 }
Gen = { 4 }Kill = { }
Gen = { 5, 6 }Kill = { 1, 7 }
Gen = { 7 }Kill = { }
IN = {}
IN = {1,2,3,4,5,6,7}IN = {1,2,3,4,5,6,7}
IN = {1,2,3,4,5,6,7}
OUT = {1,2,3,4,5,6,7}
OUT = {1,2,3,4,5,6,7} OUT = {1,2,3,4,5,6,7}
OUT = {1,2,3,4,5,6,7}
OUT = gen (IN - kill)
IN = OUTa = b + c 1d = e + f 2f = a + c 3
![Page 110: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/110.jpg)
110
Conjuntos Gen y Kill agregados
g = a + c 4
j = a + b + c + d 7
b = a + d 5h = c + f 6
Gen = { 1, 3}Kill = { 2,3,4,5,6,7 }
Gen = { 4 }Kill = { }
Gen = { 5, 6 }Kill = { 1, 7 }
Gen = { 7 }Kill = { }
IN = {}
IN = {1,2,3,4,5,6,7}IN = {1,2,3,4,5,6,7}
IN = {1,2,3,4,5,6,7}
OUT = {1,3}
OUT = {1,2,3,4,5,6,7} OUT = {1,2,3,4,5,6,7}
OUT = {1,2,3,4,5,6,7}
OUT = gen (IN - kill)
IN = OUTa = b + c 1d = e + f 2f = a + c 3
![Page 111: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/111.jpg)
111
Conjuntos Gen y Kill agregados
j = a + b + c + d 7
b = a + d 5h = c + f 6
Gen = { 1, 3}Kill = { 2,3,4,5,6,7 }
Gen = { 4 }Kill = { }
Gen = { 5, 6 }Kill = { 1, 7 }
Gen = { 7 }Kill = { }
IN = {}
IN = {1,2,3,4,5,6,7}IN = {1,2,3,4,5,6,7}
IN = {1,2,3,4,5,6,7}
OUT = {1,3}
OUT = {1,2,3,4,5,6,7} OUT = {1,2,3,4,5,6,7}
OUT = {1,2,3,4,5,6,7}
OUT = gen (IN - kill)
IN = OUT
g = a + c 4
a = b + c 1d = e + f 2f = a + c 3
![Page 112: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/112.jpg)
112
Conjuntos Gen y Kill agregados
j = a + b + c + d 7
b = a + d 5h = c + f 6
Gen = { 1, 3}Kill = { 2,3,4,5,6,7 }
Gen = { 4 }Kill = { }
Gen = { 5, 6 }Kill = { 1, 7 }
Gen = { 7 }Kill = { }
IN = {}
IN = {1,3}IN = {1,2,3,4,5,6,7}
IN = {1,2,3,4,5,6,7}
OUT = {1,3}
OUT = {1,2,3,4,5,6,7} OUT = {1,2,3,4,5,6,7}
OUT = {1,2,3,4,5,6,7}
OUT = gen (IN - kill)
IN = OUT
g = a + c 4
a = b + c 1d = e + f 2f = a + c 3
![Page 113: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/113.jpg)
113
Conjuntos Gen y Kill agregados
j = a + b + c + d 7
b = a + d 5h = c + f 6
Gen = { 1, 3}Kill = { 2,3,4,5,6,7 }
Gen = { 4 }Kill = { }
Gen = { 5, 6 }Kill = { 1, 7 }
Gen = { 7 }Kill = { }
IN = {}
IN = {1,3}IN = {1,2,3,4,5,6,7}
IN = {1,2,3,4,5,6,7}
OUT = {1,3}
OUT = {1,3,4} OUT = {1,2,3,4,5,6,7}
OUT = {1,2,3,4,5,6,7}
OUT = gen (IN - kill)
IN = OUT
g = a + c 4
a = b + c 1d = e + f 2f = a + c 3
![Page 114: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/114.jpg)
114
Conjuntos Gen y Kill agregados
b = a + d 5h = c + f 6
Gen = { 1, 3}Kill = { 2,3,4,5,6,7 }
Gen = { 4 }Kill = { }
Gen = { 5, 6 }Kill = { 1, 7 }
Gen = { 7 }Kill = { }
IN = {}
IN = {1,3}IN = {1,2,3,4,5,6,7}
IN = {1,2,3,4,5,6,7}
OUT = {1,3}
OUT = {1,3,4} OUT = {1,2,3,4,5,6,7}
OUT = {1,2,3,4,5,6,7}
OUT = gen (IN - kill)
IN = OUTa = b + c 1d = e + f 2f = a + c 3
g = a + c 4
j = a + b + c + d 7
![Page 115: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/115.jpg)
115
Conjuntos Gen y Kill agregados
b = a + d 5h = c + f 6
Gen = { 1, 3}Kill = { 2,3,4,5,6,7 }
Gen = { 4 }Kill = { }
Gen = { 5, 6 }Kill = { 1, 7 }
Gen = { 7 }Kill = { }
IN = {}
IN = {1,3}IN = {1,2,3,4,5,6,7}
IN = {1,3,4}
OUT = {1,3}
OUT = {1,3,4} OUT = {1,2,3,4,5,6,7}
OUT = {1,2,3,4,5,6,7}
OUT = gen (IN - kill)
IN = OUTa = b + c 1d = e + f 2f = a + c 3
g = a + c 4
j = a + b + c + d 7
![Page 116: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/116.jpg)
116
Conjuntos Gen y Kill agregados
b = a + d 5h = c + f 6
Gen = { 1, 3}Kill = { 2,3,4,5,6,7 }
Gen = { 4 }Kill = { }
Gen = { 5, 6 }Kill = { 1, 7 }
Gen = { 7 }Kill = { }
IN = {}
IN = {1,3}IN = {1,2,3,4,5,6,7}
IN = {1,3,4}
OUT = {1,3}
OUT = {1,3,4} OUT = {1,2,3,4,5,6,7}
OUT = {1,3,4,7}
OUT = gen (IN - kill)
IN = OUTa = b + c 1d = e + f 2f = a + c 3
g = a + c 4
j = a + b + c + d 7
![Page 117: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/117.jpg)
117
Conjuntos Gen y Kill agregados
Gen = { 1, 3}Kill = { 2,3,4,5,6,7 }
Gen = { 4 }Kill = { }
Gen = { 5, 6 }Kill = { 1, 7 }
Gen = { 7 }Kill = { }
IN = {}
IN = {1,3}IN = {1,2,3,4,5,6,7}
IN = {1,3,4}
OUT = {1,3}
OUT = {1,3,4} OUT = {1,2,3,4,5,6,7}
OUT = {1,3,4,7}
OUT = gen (IN - kill)
IN = OUTa = b + c 1d = e + f 2f = a + c 3
g = a + c 4b = a + d 5h = c + f 6
j = a + b + c + d 7
![Page 118: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/118.jpg)
118
Conjuntos Gen y Kill agregados
Gen = { 1, 3}Kill = { 2,3,4,5,6,7 }
Gen = { 4 }Kill = { }
Gen = { 5, 6 }Kill = { 1, 7 }
Gen = { 7 }Kill = { }
IN = {}
IN = {1,3}IN = {1,3}
IN = {1,3,4}
OUT = {1,3}
OUT = {1,3,4} OUT = {1,2,3,4,5,6,7}
OUT = {1,3,4,7}
OUT = gen (IN - kill)
IN = OUTa = b + c 1d = e + f 2f = a + c 3
g = a + c 4b = a + d 5h = c + f 6
j = a + b + c + d 7
![Page 119: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/119.jpg)
119
Conjuntos Gen y Kill agregados
Gen = { 1, 3}Kill = { 2,3,4,5,6,7 }
Gen = { 4 }Kill = { }
Gen = { 5, 6 }Kill = { 1, 7 }
Gen = { 7 }Kill = { }
IN = {}
IN = {1,3}IN = {1,3}
IN = {1,3,4}
OUT = {1,3}
OUT = {1,3,4} OUT = {3,5,6}
OUT = {1,3,4,7}
OUT = gen (IN - kill)
IN = OUTa = b + c 1d = e + f 2f = a + c 3
g = a + c 4b = a + d 5h = c + f 6
j = a + b + c + d 7
![Page 120: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/120.jpg)
120
Conjuntos Gen y Kill agregados
Gen = { 1, 3}Kill = { 2,3,4,5,6,7 }
Gen = { 4 }Kill = { }
Gen = { 5, 6 }Kill = { 1, 7 }
Gen = { 7 }Kill = { }
IN = {}
IN = {1,3}IN = {1,3}
IN = {1,3,4}
OUT = {1,3}
OUT = {1,3,4} OUT = {3,5,6}
OUT = {1,3,4,7}
OUT = gen (IN - kill)
IN = OUTa = b + c 1d = e + f 2f = a + c 3
g = a + c 4
j = a + b + c + d 7
b = a + d 5h = c + f 6
![Page 121: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/121.jpg)
121
Conjuntos Gen y Kill agregados
Gen = { 1, 3}Kill = { 2,3,4,5,6,7 }
Gen = { 4 }Kill = { }
Gen = { 5, 6 }Kill = { 1, 7 }
Gen = { 7 }Kill = { }
IN = {}
IN = {1,3}IN = {1,3}
IN = {1,3,4}
OUT = {1,3}
OUT = {1,3,4} OUT = {3,5,6}
OUT = {1,3,4,7}
OUT = gen (IN - kill)
IN = OUT
g = a + c 4
j = a + b + c + d 7
b = a + d 5h = c + f 6
a = b + c 1d = e + f 2f = a + c 3
![Page 122: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/122.jpg)
122
Conjuntos Gen y Kill agregados
Gen = { 1, 3}Kill = { 2,3,4,5,6,7 }
Gen = { 4 }Kill = { }
Gen = { 5, 6 }Kill = { 1, 7 }
Gen = { 7 }Kill = { }
IN = {}
IN = {1,3}IN = {1,3}
IN = {1,3,4}
OUT = {1,3}
OUT = {1,3,4} OUT = {3,5,6}
OUT = {1,3,4,7}
OUT = gen (IN - kill)
IN = OUT
j = a + b + c + d 7
b = a + d 5h = c + f 6
a = b + c 1d = e + f 2f = a + c 3
g = a + c 4
![Page 123: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/123.jpg)
123
Conjuntos Gen y Kill agregados
Gen = { 1, 3}Kill = { 2,3,4,5,6,7 }
Gen = { 4 }Kill = { }
Gen = { 5, 6 }Kill = { 1, 7 }
Gen = { 7 }Kill = { }
IN = {}
IN = {1,3}IN = {1,3}
IN = {1,3,4}
OUT = {1,3}
OUT = {1,3,4} OUT = {3,5,6}
OUT = {1,3,4,7}
OUT = gen (IN - kill)
IN = OUT
b = a + d 5h = c + f 6
a = b + c 1d = e + f 2f = a + c 3
g = a + c 4
j = a + b + c + d 7
![Page 124: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/124.jpg)
124
Conjuntos Gen y Kill agregados
Gen = { 1, 3}Kill = { 2,3,4,5,6,7 }
Gen = { 4 }Kill = { }
Gen = { 5, 6 }Kill = { 1, 7 }
Gen = { 7 }Kill = { }
IN = {}
IN = {1,3}IN = {1,3}
IN = {3}
OUT = {1,3}
OUT = {1,3,4} OUT = {3,5,6}
OUT = {1,3,4,7}
OUT = gen (IN - kill)
IN = OUT
b = a + d 5h = c + f 6
a = b + c 1d = e + f 2f = a + c 3
g = a + c 4
j = a + b + c + d 7
![Page 125: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/125.jpg)
125
Conjuntos Gen y Kill agregados
Gen = { 1, 3}Kill = { 2,3,4,5,6,7 }
Gen = { 4 }Kill = { }
Gen = { 5, 6 }Kill = { 1, 7 }
Gen = { 7 }Kill = { }
IN = {}
IN = {1,3}IN = {1,3}
IN = {3}
OUT = {1,3}
OUT = {1,3,4} OUT = {3,5,6}
OUT = {3,7}
OUT = gen (IN - kill)
IN = OUT
b = a + d 5h = c + f 6
a = b + c 1d = e + f 2f = a + c 3
g = a + c 4
j = a + b + c + d 7
![Page 126: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/126.jpg)
126
Conjuntos Gen y Kill agregados
Gen = { 1, 3}Kill = { 2,3,4,5,6,7 }
Gen = { 4 }Kill = { }
Gen = { 5, 6 }Kill = { 1, 7 }
Gen = { 7 }Kill = { }
IN = {}
IN = {1,3}IN = {1,3}
IN = {3}
OUT = {1,3}
OUT = {1,3,4} OUT = {3,5,6}
OUT = {3,7}
OUT = gen (IN - kill)
IN = OUTa = b + c 1d = e + f 2f = a + c 3
g = a + c 4b = a + d 5h = c + f 6
j = a + b + c + d 7
![Page 127: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/127.jpg)
127
Conjuntos Gen y Kill agregados
Gen = { 1, 3}Kill = { 2,3,4,5,6,7 }
Gen = { 4 }Kill = { }
Gen = { 5, 6 }Kill = { 1, 7 }
Gen = { 7 }Kill = { }
IN = {}
IN = {1,3}IN = {3}
IN = {3}
OUT = {1,3}
OUT = {1,3,4} OUT = {3,5,6}
OUT = {3,7}
OUT = gen (IN - kill)
IN = OUTa = b + c 1d = e + f 2f = a + c 3
g = a + c 4b = a + d 5h = c + f 6
j = a + b + c + d 7
![Page 128: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/128.jpg)
128
Conjuntos Gen y Kill agregados
Gen = { 1, 3}Kill = { 2,3,4,5,6,7 }
Gen = { 4 }Kill = { }
Gen = { 5, 6 }Kill = { 1, 7 }
Gen = { 7 }Kill = { }
IN = {}
IN = {1,3}IN = {3}
IN = {3}
OUT = {1,3}
OUT = {1,3,4} OUT = {3,5,6}
OUT = {3,7}
OUT = gen (IN - kill)
IN = OUTa = b + c 1d = e + f 2f = a + c 3
g = a + c 4
j = a + b + c + d 7
b = a + d 5h = c + f 6
![Page 129: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/129.jpg)
129
Conjuntos Gen y Kill agregados
Gen = { 1, 3}Kill = { 2,3,4,5,6,7 }
Gen = { 4 }Kill = { }
Gen = { 5, 6 }Kill = { 1, 7 }
Gen = { 7 }Kill = { }
IN = {}
IN = {1,3}IN = {3}
IN = {3}
OUT = {1,3}
OUT = {1,3,4} OUT = {3,5,6}
OUT = {3,7}
OUT = gen (IN - kill)
IN = OUT
g = a + c 4
j = a + b + c + d 7
b = a + d 5h = c + f 6
a = b + c 1d = e + f 2f = a + c 3
![Page 130: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/130.jpg)
130
Conjuntos Gen y Kill agregados
Gen = { 1, 3}Kill = { 2,3,4,5,6,7 }
Gen = { 4 }Kill = { }
Gen = { 5, 6 }Kill = { 1, 7 }
Gen = { 7 }Kill = { }
IN = {}
IN = {1,3}IN = {3}
IN = {3}
OUT = {1,3}
OUT = {1,3,4} OUT = {3,5,6}
OUT = {3,7}
OUT = gen (IN - kill)
IN = OUTa = b + c 1d = e + f 2f = a + c 3
j = a + b + c + d 7
b = a + d 5h = c + f 6g = a + c 4
![Page 131: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/131.jpg)
131
Conjuntos Gen y Kill agregados
Gen = { 1, 3}Kill = { 2,3,4,5,6,7 }
Gen = { 4 }Kill = { }
Gen = { 5, 6 }Kill = { 1, 7 }
Gen = { 7 }Kill = { }
IN = {}
IN = {1,3}IN = {3}
IN = {3}
OUT = {1,3}
OUT = {1,3,4} OUT = {3,5,6}
OUT = {3,7}
OUT = gen (IN - kill)
IN = OUTa = b + c 1d = e + f 2f = a + c 3
g = a + c 4b = a + d 5h = c + f 6
j = a + b + c + d 7
![Page 132: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/132.jpg)
132
Conjuntos Gen y Kill agregados
Gen = { 1, 3}Kill = { 2,3,4,5,6,7 }
Gen = { 4 }Kill = { }
Gen = { 5, 6 }Kill = { 1, 7 }
Gen = { 7 }Kill = { }
IN = {}
IN = {1,3}IN = {3}
IN = {3}
OUT = {1,3}
OUT = {1,3,4} OUT = {3,5,6}
OUT = {3,7}
OUT = gen (IN - kill)
IN = OUTa = b + c 1d = e + f 2f = a + c 3
g = a + c 4
j = a + b + c + d 7
b = a + d 5h = c + f 6
![Page 133: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/133.jpg)
133
Conjuntos Gen y Kill agregados
Gen = { 1, 3}Kill = { 2,3,4,5,6,7 }
Gen = { 4 }Kill = { }
Gen = { 5, 6 }Kill = { 1, 7 }
Gen = { 7 }Kill = { }
IN = {}
IN = {1,3}IN = {3}
IN = {3}
OUT = {1,3}
OUT = {1,3,4} OUT = {3,5,6}
OUT = {3,7}
OUT = gen (IN - kill)
IN = OUTa = b + c 1d = e + f 2f = a + c 3
g = a + c 4
j = a + b + c + d 7
b = a + d 5h = c + f 6
![Page 134: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/134.jpg)
134
Algoritmo para Expresiones Disponibles
• Asignar un número a cada expresión
• Calcular conjuntos gen y kill para cada instrucción
• Calcular conjuntos gen y kill agregados para cada bloque básico
• Inicializar conjunto de disponibles en cada bloque básico con todas las expresiones
• Iterativamente propagar expresiones disponibles sobre el CFG
• Propagar dentro del bloque básico
28
![Page 135: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/135.jpg)
135
Propagar dentro del bloque básico
a = b + c 1
gen = { 1 }
kill = { 3, 4, 5, 7 }
IN set
OUT set
• Comenzar con el conjunto IN de expresiones disponibles
• Linealmente propagar hacia abajo del bloque básico– Igual que el paso de data-flow
– Una sola pasada ya que no hay aristas de retorno
OUT = gen (IN - kill)
![Page 136: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/136.jpg)
136
ae = { 1, 3 }g = a + c 4
ae = { 1, 3, 4 }
Expresiones Disponibles
ae = { }a = b + c 1 ae = { 1 }d = e + f 2 ae = { 1, 2 }f = a + c 3 ae = { 1, 3 }
ae = { 3 }j = a + b + c + d 7
ae = { 3, 7 }
ae = { 3 }b = a + d 5
ae = { 3, 5 }h = c + f 6
ae = { 3, 5, 6 }
![Page 137: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/137.jpg)
137
Resumen
• Overview de análisis de control de flujo• Expresiones Disponibles• Algoritmo para calcular expresiones
disponibles• Bit sets• Formulando un problema de análisis de flujo
de datos• Cadenas DU• Forma SSA
5
![Page 138: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/138.jpg)
138
Bitsets
• Asignar un bit a cada elemento del conjunto– Unión OR– Intersección AND – Subtracción NEGATE y AND
• Implementación rápida– 32 elementos empacados en cada word– AND y OR son ambas una instrucción
![Page 139: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/139.jpg)
139
Conjunto Kill vrs. Conjunto Preserve
• Conjuntos Kill– OUT = gen (IN - kill)– Usando vectores de bits: OUT = gen (IN - kill)– Subtracción NEGATE y AND– OUT = gen (IN kill)
• Conjuntos Preserve– Usados en el libro de la Ballena– PRSV = Entire Set - KILL– OUT = gen (IN prsv)– OUT = gen (IN prsv)
![Page 140: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/140.jpg)
140
Conjuntos Gen y Kill agregados
a = b + c 1d = e + f 2f = a + c 3
g = a + c 4
j = a + b + c + d 7
b = a + d 5h = c + f 6
Gen = { 1,3}Kill = { 2,3,4,5,6,7 }
Gen = { 4 }Kill = { }
Gen = { 5,6 }Kill = { 1,7 }
Gen = { 7 }Kill = { }
![Page 141: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/141.jpg)
141
Conjuntos Gen y Kill agregados
a = b + c 1d = e + f 2f = a + c 3
g = a + c 4
j = a + b + c + d 7
b = a + d 5h = c + f 6
Gen = { 1,3}Kill = { 2,3,4,5,6,7 }
Gen = { 4 }Kill = { }
Gen = { 5,6 }Kill = { 1,7 }
Gen = { 7 }Kill = { }
•Se requieren 7 bits por conjunto
![Page 142: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/142.jpg)
142
Conjuntos Gen y Kill agregados
a = b + c 1d = e + f 2f = a + c 3
g = a + c 4
j = a + b + c + d 7
b = a + d 5h = c + f 6
Gen = 1010000Kill = 0111111
Gen = 0001000Kill = 0000000
Gen = 0000110Kill = 1000001
Gen = 0000001Kill = 0000000
•Se requieren 7 bits por conjunto
![Page 143: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/143.jpg)
143
Resumen
• Overview de análisis de control de flujo• Expresiones Disponibles• Algoritmo para calcular expresiones
disponibles• Bit sets• Formulando un problema de análisis de flujo
de datos• Cadenas DU• Forma SSA
5
![Page 144: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/144.jpg)
144
Formulando un problema de análisis de flujo de datos
• Independiente del problema– Calcular conjuntos gen y kill para bloque básico– Propagación iterativa de información hasta que
converja– Propagación de información dentro del bloque
básico
![Page 145: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/145.jpg)
145
Formulando un problema de análisis de flujo de datos
• Lattice– Estructuras abstractas sobre las que opera el análisis
ejemplo: conjuntos de expresiones disponibles
• Funciones de flujo– Cómo cada control de flujo y construcciones
computacionales afectan las estructuras abstractas• Ejemplo: la ecuación OUT de cada statement
![Page 146: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/146.jpg)
146
Lattice
• Una lattice L consiste de– Un conjunto de valores– Dos operaciones: meet( ) y join ( )– Un valor superior [top] (T) y un valor inferior
[bottom] ()
![Page 147: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/147.jpg)
147
Lattice
• Ejemplo: el lattice para el problema de “reaching definition” cuando sólo hay 3 definiciones
{ d1, d2 }
{ d2, d3 }
{ d1 }
{ d3 }
= { }
T = { d1, d2, d3 }
{ d1, d3 }
{ d2 }
![Page 148: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/148.jpg)
148
Operaciones Meet y Join
• Meet y Join forman una “cerradura”– Para todos a, b L existen c y d L únicos, tal que
a b = c a b = d• Meet y Join con conmutativas
– a b = b a a b = b a• Meet y Join son asociativas
– (a b) c = b (a c) (a b) c = b (a c)
• Existe un único elemento (T) [top] y un único elemento () [bottom] en L tal que– a = a T = T
![Page 149: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/149.jpg)
149
Operaciones Meet y Join
{ d1, d2 }
{ d2, d3 }
{ d1 }
{ d3 }
= { }
T = { d1, d2, d3 }
{ d1, d3 }
{ d2 }
{ d1, d2 } { d2, d3 } = ???
![Page 150: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/150.jpg)
150
Operaciones Meet y Join
{ d1, d2 }
{ d2, d3 }
{ d1 }
{ d3 }
= { }
T = { d1, d2, d3 }
{ d1, d3 }
{ d2 }
{ d1, d2 } { d2, d3 } = ???
![Page 151: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/151.jpg)
151
Operaciones Meet y Join
{ d1, d2 }
{ d2, d3 }
{ d1 }
{ d3 }
= { }
T = { d1, d2, d3 }
{ d1, d3 }
{ d2 }
{ d1, d2 } { d2, d3 } = ???
![Page 152: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/152.jpg)
152
Operaciones Meet y Join
{ d1, d2 }
{ d2, d3 }
{ d1 }
{ d3 }
= { }
T = { d1, d2, d3 }
{ d1, d3 }
{ d2 }
{ d1, d2 } { d2, d3 } = { d2 }
![Page 153: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/153.jpg)
153
Operaciones Meet y Join
{ d1, d2 }
{ d2, d3 }
{ d1 }
{ d3 }
= { }
T = { d1, d2, d3 }
{ d1, d3 }
{ d2 }
{ d1, d2 } { d3 } = ???
![Page 154: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/154.jpg)
154
Operaciones Meet y Join
{ d1, d2 }
{ d2, d3 }
{ d1 }
{ d3 }
= { }
T = { d1, d2, d3 }
{ d1, d3 }
{ d2 }
{ d1, d2 } { d3 } = ???
![Page 155: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/155.jpg)
155
Operaciones Meet y Join
{ d1, d2 }
{ d2, d3 }
{ d1 }
{ d3 }
= { }
T = { d1, d2, d3 }
{ d1, d3 }
{ d2 }
{ d1, d2 } { d3 } = ???
![Page 156: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/156.jpg)
156
Operaciones Meet y Join
{ d1, d2 }
{ d2, d3 }
{ d1 }
{ d3 }
= { }
T = { d1, d2, d3 }
{ d1, d3 }
{ d2 }
{ d1, d2 } { d3 } = ???
![Page 157: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/157.jpg)
157
Operaciones Meet y Join
{ d1, d2 }
{ d2, d3 }
{ d1 }
{ d3 }
= { }
T = { d1, d2, d3 }
{ d1, d3 }
{ d2 }
{ d1, d2 } { d3 } = { d1, d2, d3 }
![Page 158: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/158.jpg)
158
Operaciones Meet y Join
• Operación Meet– Intersección de conjuntos
– Seguir las líneas hacia abajo desde los dos elementos en el lattice hasta que se encuentren en un sólo elemento único
• Operación Join– Unión de conjuntos– Hay un sólo elemento en el lattice desde el que hay
un camino hacia abajo (sin segmentos compartidos) hacia ambos elementos
![Page 159: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/159.jpg)
159
Orden Parcial
• Definimos a b sí y sólo sí a b = b
• Propiedades– Reflexivo: a a– Antisimétrico: a b y b a a = b– Transitivo: a b y b c a c
![Page 160: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/160.jpg)
160
Orden Parcial
• Definimos a b sí y sólo sí a b = b
• Propiedades– a b existe un camino desde b hasta a
{ d1, d2 }
{ d2, d3 }
{ d1 }
{ d3 }
= { }
T = { d1, d2, d3 }
{ d1, d3 }
{ d2 }
![Page 161: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/161.jpg)
161
Alto del Lattice
• El alto del lattice es la cadena ascendiente más larga en el lattice– (T, a, b, c, …, )
![Page 162: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/162.jpg)
162
Alto del Lattice
• El alto del lattice es la cadena ascendiente más larga en el lattice– (T, a, b, c, …, )
– Alto es (T, {d2,d3}, {d3}, ) = 4
{ d1, d2 }
{ d2, d3 }
{ d1 }
{ d3 }
= { }
T = { d1, d2, d3 }
{ d1, d3 }
{ d2 }
![Page 163: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/163.jpg)
163
Funciones de Flujo
• Ejemplo: OUT = f(IN)
• f: L L donde L es un lattice
• Propiedades– Monótona: a,b L a b f(a) f(b)
• Punto Fijo– Un punto fijo es un elemento a L tal que
f(a) = a
![Page 164: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/164.jpg)
164
Intuición acerca de Finalización
• El análisis de flujo de datos comienza asumiendo los valores más optimistas (T)
• Cada etapa aplica funciones de flujo– Vnew Vprev
– Se mueve hacia abajo en el lattice
• Hasta que sea estable (valores no cambian)– Se llega a un punto fijo en cada bloque básico
• Lattice tiene un alto finito debe terminar
![Page 165: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/165.jpg)
165
Resumen
• Overview de análisis de control de flujo• Expresiones Disponibles• Algoritmo para calcular expresiones
disponibles• Bit sets• Formulando un problema de análisis de flujo
de datos• Cadenas DU• Forma SSA
5
![Page 166: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/166.jpg)
166
Cadenas Def-Use y Use-Def
• Cadena Def-Use (DU)– Conecta la definición de cada variable con todos
los posibles usos de esa variable
• Cadena Use-Def (UD)– Conecta el uso de una variable con todas las
posibles definiciones de esa variable
![Page 167: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/167.jpg)
167
Formulación del problema de flujo de datos para cadena DU
• Lattice: El conjunto de definiciones– Bitvector format: un bit para cada definición en el
procedimiento
• Dirección del Flujo: Flujo hacia adelante
• Funciones de Flujo:– gen = { b0…bn | bk = 1 ssi la k-ésima definición}
– kill = { b0…bn | bk = 1 ssi k-ésima variable es redefinida }
– OUT = gen (IN - kill)
– IN = OUT
![Page 168: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/168.jpg)
168
Formulen el problema de flujo de datos para la cadena UD
• Lattice: – Bitvector format:
• Dirección del Flujo: Flujo hacia adelante/atrás
• Funciones de flujo:– gen = { b0…bn | bk = 1 }
– kill = { b0…bn | bk = 1 }
– OUT =
– IN =
![Page 169: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/169.jpg)
169
Ejemplo DUentry
k = false i = 1 j = 2
j = j * 2 k = true i = i + 1
print j i = i + 1
k
exit
i < n
![Page 170: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/170.jpg)
170
Ejemplo DUentry
k = false 1i = 1 2j = 2 3
j = j * 2 4k = true 5i = i + 1 6
print j i = i + 1 7
k
exit
i < n
![Page 171: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/171.jpg)
171
Ejemplo DUentry
k = false 1i = 1 2j = 2 3
j = j * 2 4k = true 5i = i + 1 6
print j i = i + 1 7
k
exit
i < n
gen ={ 1, 2, 3 }kill = { 4,5,6,7 }
gen ={ 4,5,6 }kill = { 1,2,3,7 }
gen ={ }kill = { }
gen ={ }kill = { }
gen ={ }kill = { }
gen ={ 7 }kill = { 2,6 }
![Page 172: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/172.jpg)
172
Ejemplo DUentry
k = false 1i = 1 2j = 2 3
j = j * 2 4k = true 5i = i + 1 6
print j i = i + 1 7
k
exit
i < n
gen ={ 1, 2, 3 }kill = { 4,5,6,7 }
gen ={ 4,5,6 }kill = { 1,2,3,7 }
gen ={ }kill = { }
gen ={ }kill = { }
gen ={ }kill = { }
gen ={ 7 }kill = { 2,6 }
OUT = { }IN = { }
OUT = IN = { }
OUT = IN = { }
OUT = IN = { }
OUT = { } OUT = { } OUT = { }IN = { }
![Page 173: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/173.jpg)
173
Ejemplo DUentry
k = false 1i = 1 2j = 2 3
j = j * 2 4k = true 5i = i + 1 6
print j i = i + 1 7
k
exit
i < n
gen ={ 1, 2, 3 }kill = { 4,5,6,7 }
gen ={ 4,5,6 }kill = { 1,2,3,7 }
gen ={ }kill = { }
gen ={ }kill = { }
gen ={ }kill = { }
gen ={ 7 }kill = { 2,6 }
OUT = { }IN = { }
OUT = IN = { }
OUT = IN = { }
OUT = IN = { }
OUT = { } OUT = { } OUT = { }IN = { }
![Page 174: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/174.jpg)
174
Ejemplo DUentry
k = false 1i = 1 2j = 2 3
j = j * 2 4k = true 5i = i + 1 6
print j i = i + 1 7
k
exit
i < n
gen ={ 1, 2, 3 }kill = { 4,5,6,7 }
gen ={ 4,5,6 }kill = { 1,2,3,7 }
gen ={ }kill = { }
gen ={ }kill = { }
gen ={ }kill = { }
gen ={ 7 }kill = { 2,6 }
OUT = { }IN = { }
OUT = IN = { }
OUT = IN = { }
OUT = IN = { }
OUT = { } OUT = { } OUT = { }IN = { }
![Page 175: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/175.jpg)
175
Ejemplo DUentry
k = false 1i = 1 2j = 2 3
j = j * 2 4k = true 5i = i + 1 6
print j i = i + 1 7
k
exit
i < n
gen ={ 1, 2, 3 }kill = { 4,5,6,7 }
gen ={ 4,5,6 }kill = { 1,2,3,7 }
gen ={ }kill = { }
gen ={ }kill = { }
gen ={ }kill = { }
gen ={ 7 }kill = { 2,6 }
OUT = { 1, 2, 3 }IN = { }
OUT = IN = { }
OUT = IN = { }
OUT = IN = { }
OUT = { } OUT = { } OUT = { }IN = { }
![Page 176: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/176.jpg)
176
Ejemplo DUentry
k = false 1i = 1 2j = 2 3
j = j * 2 4k = true 5i = i + 1 6
print j i = i + 1 7
k
exit
i < n
gen ={ 1, 2, 3 }kill = { 4,5,6,7 }
gen ={ 4,5,6 }kill = { 1,2,3,7 }
gen ={ }kill = { }
gen ={ }kill = { }
gen ={ }kill = { }
gen ={ 7 }kill = { 2,6 }
OUT = { 1, 2, 3 }IN = { 1, 2, 3 }
OUT = IN = { }
OUT = IN = { }
OUT = IN = { }
OUT = { } OUT = { } OUT = { }IN = { }
![Page 177: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/177.jpg)
177
Ejemplo DUentry
k = false 1i = 1 2j = 2 3
j = j * 2 4k = true 5i = i + 1 6
print j i = i + 1 7
k
exit
i < n
gen ={ 1, 2, 3 }kill = { 4,5,6,7 }
gen ={ 4,5,6 }kill = { 1,2,3,7 }
gen ={ }kill = { }
gen ={ }kill = { }
gen ={ }kill = { }
gen ={ 7 }kill = { 2,6 }
OUT = { 1, 2, 3 }IN = { 1, 2, 3 }
OUT = IN = { }
OUT = IN = { }
OUT = IN = { }
OUT = { } OUT = { } OUT = { }IN = { }
![Page 178: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/178.jpg)
178
Ejemplo DUentry
k = false 1i = 1 2j = 2 3
j = j * 2 4k = true 5i = i + 1 6
print j i = i + 1 7
k
exit
i < n
gen ={ 1, 2, 3 }kill = { 4,5,6,7 }
gen ={ 4,5,6 }kill = { 1,2,3,7 }
gen ={ }kill = { }
gen ={ }kill = { }
gen ={ }kill = { }
gen ={ 7 }kill = { 2,6 }
OUT = { 1, 2, 3 }IN = { 1, 2, 3 }
OUT = IN = { }
OUT = IN = { 1, 2, 3 }
OUT = IN = { }
OUT = { } OUT = { } OUT = { }IN = { }
![Page 179: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/179.jpg)
179
Ejemplo DUentry
k = false 1i = 1 2j = 2 3
j = j * 2 4k = true 5i = i + 1 6
print j i = i + 1 7
k
exit
i < n
gen ={ 1, 2, 3 }kill = { 4,5,6,7 }
gen ={ 4,5,6 }kill = { 1,2,3,7 }
gen ={ }kill = { }
gen ={ }kill = { }
gen ={ }kill = { }
gen ={ 7 }kill = { 2,6 }
OUT = { 1, 2, 3 }IN = { 1, 2, 3 }
OUT = IN = { }
OUT = IN = { 1, 2, 3 }
OUT = IN = { }
OUT = { } OUT = { } OUT = { }IN = { }
![Page 180: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/180.jpg)
180
Ejemplo DUentry
k = false 1i = 1 2j = 2 3
j = j * 2 4k = true 5i = i + 1 6
print j i = i + 1 7
k
exit
i < n
gen ={ 1, 2, 3 }kill = { 4,5,6,7 }
gen ={ 4,5,6 }kill = { 1,2,3,7 }
gen ={ }kill = { }
gen ={ }kill = { }
gen ={ }kill = { }
gen ={ 7 }kill = { 2,6 }
OUT = { 1, 2, 3 }IN = { 1, 2, 3 }
OUT = IN = { }
OUT = IN = { 1, 2, 3 }
OUT = IN = { }
OUT = { 4, 5, 6 } OUT = { } OUT = { }IN = { }
![Page 181: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/181.jpg)
181
Ejemplo DUentry
k = false 1i = 1 2j = 2 3
j = j * 2 4k = true 5i = i + 1 6
print j i = i + 1 7
k
exit
i < n
gen ={ 1, 2, 3 }kill = { 4,5,6,7 }
gen ={ 4,5,6 }kill = { 1,2,3,7 }
gen ={ }kill = { }
gen ={ }kill = { }
gen ={ }kill = { }
gen ={ 7 }kill = { 2,6 }
OUT = { 1, 2, 3 }IN = { 1, 2, 3 }
OUT = IN = { }
OUT = IN = { 1, 2, 3 }
OUT = IN = { }
OUT = { 4, 5, 6 } OUT = { } OUT = { }IN = { }
![Page 182: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/182.jpg)
182
Ejemplo DUentry
k = false 1i = 1 2j = 2 3
j = j * 2 4k = true 5i = i + 1 6
print j i = i + 1 7
k
exit
i < n
gen ={ 1, 2, 3 }kill = { 4,5,6,7 }
gen ={ 4,5,6 }kill = { 1,2,3,7 }
gen ={ }kill = { }
gen ={ }kill = { }
gen ={ }kill = { }
gen ={ 7 }kill = { 2,6 }
OUT = { 1, 2, 3 }IN = { 1, 2, 3 }
OUT = IN = { }
OUT = IN = { 1, 2, 3 }
OUT = IN = { 1, 2, 3 }
OUT = { 4, 5, 6 } OUT = { } OUT = { }IN = { }
![Page 183: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/183.jpg)
183
Ejemplo DUentry
k = false 1i = 1 2j = 2 3
j = j * 2 4k = true 5i = i + 1 6
print j i = i + 1 7
k
exit
i < n
gen ={ 1, 2, 3 }kill = { 4,5,6,7 }
gen ={ 4,5,6 }kill = { 1,2,3,7 }
gen ={ }kill = { }
gen ={ }kill = { }
gen ={ }kill = { }
gen ={ 7 }kill = { 2,6 }
OUT = { 1, 2, 3 }IN = { 1, 2, 3 }
OUT = IN = { }
OUT = IN = { 1, 2, 3 }
OUT = IN = { 1, 2, 3 }
OUT = { 4, 5, 6 } OUT = { } OUT = { }IN = { }
![Page 184: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/184.jpg)
184
Ejemplo DUentry
k = false 1i = 1 2j = 2 3
j = j * 2 4k = true 5i = i + 1 6
print j i = i + 1 7
k
exit
i < n
gen ={ 1, 2, 3 }kill = { 4,5,6,7 }
gen ={ 4,5,6 }kill = { 1,2,3,7 }
gen ={ }kill = { }
gen ={ }kill = { }
gen ={ }kill = { }
gen ={ 7 }kill = { 2,6 }
OUT = { 1, 2, 3 }IN = { 1, 2, 3 }
OUT = IN = { }
OUT = IN = { 1, 2, 3 }
OUT = IN = { 1, 2, 3 }
OUT = { 4, 5, 6 } OUT = { 1, 2, 3 } OUT = { }IN = { }
![Page 185: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/185.jpg)
185
Ejemplo DUentry
k = false 1i = 1 2j = 2 3
j = j * 2 4k = true 5i = i + 1 6
print j i = i + 1 7
k
exit
i < n
gen ={ 1, 2, 3 }kill = { 4,5,6,7 }
gen ={ 4,5,6 }kill = { 1,2,3,7 }
gen ={ }kill = { }
gen ={ }kill = { }
gen ={ }kill = { }
gen ={ 7 }kill = { 2,6 }
OUT = { 1, 2, 3 }IN = { 1, 2, 3 }
OUT = IN = { }
OUT = IN = { 1, 2, 3 }
OUT = IN = { 1, 2, 3 }
OUT = { 4, 5, 6 } OUT = { 1, 2, 3 } OUT = { }IN = { }
![Page 186: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/186.jpg)
186
Ejemplo DUentry
k = false 1i = 1 2j = 2 3
j = j * 2 4k = true 5i = i + 1 6
print j i = i + 1 7
k
exit
i < n
gen ={ 1, 2, 3 }kill = { 4,5,6,7 }
gen ={ 4,5,6 }kill = { 1,2,3,7 }
gen ={ }kill = { }
gen ={ }kill = { }
gen ={ }kill = { }
gen ={ 7 }kill = { 2,6 }
OUT = { 1, 2, 3 }IN = { 1, 2, 3 }
OUT = IN = { }
OUT = IN = { 1, 2, 3 }
OUT = IN = { 1, 2, 3 }
OUT = { 4, 5, 6 } OUT = { 1, 2, 3 } OUT = { 1, 3, 7 }IN = { }
![Page 187: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/187.jpg)
187
Ejemplo DUentry
k = false 1i = 1 2j = 2 3
j = j * 2 4k = true 5i = i + 1 6
print j i = i + 1 7
k
exit
i < n
gen ={ 1, 2, 3 }kill = { 4,5,6,7 }
gen ={ 4,5,6 }kill = { 1,2,3,7 }
gen ={ }kill = { }
gen ={ }kill = { }
gen ={ }kill = { }
gen ={ 7 }kill = { 2,6 }
OUT = { 1, 2, 3 }IN = { 1, 2, 3 }
OUT = IN = { }
OUT = IN = { 1, 2, 3 }
OUT = IN = { 1, 2, 3 }
OUT = { 4, 5, 6 } OUT = { 1, 2, 3 } OUT = { 1, 3, 7 }IN = { 1, 2, 3, 7 }
![Page 188: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/188.jpg)
188
Ejemplo DUentry
k = false 1i = 1 2j = 2 3
j = j * 2 4k = true 5i = i + 1 6
print j i = i + 1 7
k
exit
i < n
gen ={ 1, 2, 3 }kill = { 4,5,6,7 }
gen ={ 4,5,6 }kill = { 1,2,3,7 }
gen ={ }kill = { }
gen ={ }kill = { }
gen ={ }kill = { }
gen ={ 7 }kill = { 2,6 }
OUT = { 1, 2, 3 }IN = { 1, 2, 3 }
OUT = IN = { }
OUT = IN = { 1, 2, 3 }
OUT = IN = { 1, 2, 3 }
OUT = { 4, 5, 6 } OUT = { 1, 2, 3 } OUT = { 1, 3, 7 }IN = { 1, 2, 3, 7 }
![Page 189: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/189.jpg)
189
Ejemplo DUentry
k = false 1i = 1 2j = 2 3
j = j * 2 4k = true 5i = i + 1 6
print j i = i + 1 7
k
exit
i < n
gen ={ 1, 2, 3 }kill = { 4,5,6,7 }
gen ={ 4,5,6 }kill = { 1,2,3,7 }
gen ={ }kill = { }
gen ={ }kill = { }
gen ={ }kill = { }
gen ={ 7 }kill = { 2,6 }
OUT = { 1, 2, 3 }IN = { 1, 2, 3 }
OUT = IN = { }
OUT = IN = { 1, 2, 3 }
OUT = IN = { 1, 2, 3 }
OUT = { 4, 5, 6 } OUT = { 1, 2, 3 } OUT = { 1, 3, 7 }IN = { 1, 2, 3, 7 }
![Page 190: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/190.jpg)
190
Ejemplo DUentry
k = false 1i = 1 2j = 2 3
j = j * 2 4k = true 5i = i + 1 6
print j i = i + 1 7
k
exit
i < n
gen ={ 1, 2, 3 }kill = { 4,5,6,7 }
gen ={ 4,5,6 }kill = { 1,2,3,7 }
gen ={ }kill = { }
gen ={ }kill = { }
gen ={ }kill = { }
gen ={ 7 }kill = { 2,6 }
OUT = { 1, 2, 3 }IN = { 1, 2, 3, 4, 5, 6 }
OUT = IN = { }
OUT = IN = { 1, 2, 3 }
OUT = IN = { 1, 2, 3 }
OUT = { 4, 5, 6 } OUT = { 1, 2, 3 } OUT = { 1, 3, 7 }IN = { 1, 2, 3, 7 }
![Page 191: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/191.jpg)
191
Ejemplo DUentry
k = false 1i = 1 2j = 2 3
j = j * 2 4k = true 5i = i + 1 6
print j i = i + 1 7
k
exit
i < n
gen ={ 1, 2, 3 }kill = { 4,5,6,7 }
gen ={ 4,5,6 }kill = { 1,2,3,7 }
gen ={ }kill = { }
gen ={ }kill = { }
gen ={ }kill = { }
gen ={ 7 }kill = { 2,6 }
OUT = { 1, 2, 3 }IN = { 1, 2, 3, 4, 5, 6 }
OUT = IN = { }
OUT = IN = { 1, 2, 3 }
OUT = IN = { 1, 2, 3 }
OUT = { 4, 5, 6 } OUT = { 1, 2, 3 } OUT = { 1, 3, 7 }IN = { 1, 2, 3, 7 }
![Page 192: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/192.jpg)
192
Ejemplo DUentry
k = false 1i = 1 2j = 2 3
j = j * 2 4k = true 5i = i + 1 6
print j i = i + 1 7
k
exit
i < n
gen ={ 1, 2, 3 }kill = { 4,5,6,7 }
gen ={ 4,5,6 }kill = { 1,2,3,7 }
gen ={ }kill = { }
gen ={ }kill = { }
gen ={ }kill = { }
gen ={ 7 }kill = { 2,6 }
OUT = { 1, 2, 3 }IN = { 1, 2, 3, 4, 5, 6 }
OUT = IN = { }
OUT = IN = { 1, 2, 3, 4, 5, 6 }
OUT = IN = { 1, 2, 3 }
OUT = { 4, 5, 6 } OUT = { 1, 2, 3 } OUT = { 1, 3, 7 }IN = { 1, 2, 3, 7 }
![Page 193: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/193.jpg)
193
Ejemplo DUentry
k = false 1i = 1 2j = 2 3
j = j * 2 4k = true 5i = i + 1 6
print j i = i + 1 7
k
exit
i < n
gen ={ 1, 2, 3 }kill = { 4,5,6,7 }
gen ={ 4,5,6 }kill = { 1,2,3,7 }
gen ={ }kill = { }
gen ={ }kill = { }
gen ={ }kill = { }
gen ={ 7 }kill = { 2,6 }
OUT = { 1, 2, 3 }IN = { 1, 2, 3, 4, 5, 6 }
OUT = IN = { }
OUT = IN = { 1, 2, 3, 4, 5, 6 }
OUT = IN = { 1, 2, 3 }
OUT = { 4, 5, 6 } OUT = { 1, 2, 3 } OUT = { 1, 3, 7 }IN = { 1, 2, 3, 7 }
![Page 194: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/194.jpg)
194
Ejemplo DUentry
k = false 1i = 1 2j = 2 3
j = j * 2 4k = true 5i = i + 1 6
print j i = i + 1 7
k
exit
i < n
gen ={ 1, 2, 3 }kill = { 4,5,6,7 }
gen ={ 4,5,6 }kill = { 1,2,3,7 }
gen ={ }kill = { }
gen ={ }kill = { }
gen ={ }kill = { }
gen ={ 7 }kill = { 2,6 }
OUT = { 1, 2, 3 }IN = { 1, 2, 3, 4, 5, 6 }
OUT = IN = { }
OUT = IN = { 1, 2, 3, 4, 5, 6 }
OUT = IN = { 1, 2, 3 }
OUT = { 4, 5, 6 } OUT = { 1, 2, 3 } OUT = { 1, 3, 7 }IN = { 1, 2, 3, 7 }
![Page 195: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/195.jpg)
195
Ejemplo DUentry
k = false 1i = 1 2j = 2 3
j = j * 2 4k = true 5i = i + 1 6
print j i = i + 1 7
k
exit
i < n
gen ={ 1, 2, 3 }kill = { 4,5,6,7 }
gen ={ 4,5,6 }kill = { 1,2,3,7 }
gen ={ }kill = { }
gen ={ }kill = { }
gen ={ }kill = { }
gen ={ 7 }kill = { 2,6 }
OUT = { 1, 2, 3 }IN = { 1, 2, 3, 4, 5, 6 }
OUT = IN = { }
OUT = IN = { 1, 2, 3, 4, 5, 6 }
OUT = IN = { 1, 2, 3, 4, 5, 6 }
OUT = { 4, 5, 6 } OUT = { 1, 2, 3 } OUT = { 1, 3, 7 }IN = { 1, 2, 3, 7 }
![Page 196: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/196.jpg)
196
Ejemplo DUentry
k = false 1i = 1 2j = 2 3
j = j * 2 4k = true 5i = i + 1 6
print j i = i + 1 7
k
exit
i < n
gen ={ 1, 2, 3 }kill = { 4,5,6,7 }
gen ={ 4,5,6 }kill = { 1,2,3,7 }
gen ={ }kill = { }
gen ={ }kill = { }
gen ={ }kill = { }
gen ={ 7 }kill = { 2,6 }
OUT = { 1, 2, 3 }IN = { 1, 2, 3, 4, 5, 6 }
OUT = IN = { }
OUT = IN = { 1, 2, 3, 4, 5, 6 }
OUT = IN = { 1, 2, 3, 4, 5, 6 }
OUT = { 4, 5, 6 } OUT = { 1, 2, 3 } OUT = { 1, 3, 7 }IN = { 1, 2, 3, 7 }
![Page 197: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/197.jpg)
197
Ejemplo DUentry
k = false 1i = 1 2j = 2 3
j = j * 2 4k = true 5i = i + 1 6
print j i = i + 1 7
k
exit
i < n
gen ={ 1, 2, 3 }kill = { 4,5,6,7 }
gen ={ 4,5,6 }kill = { 1,2,3,7 }
gen ={ }kill = { }
gen ={ }kill = { }
gen ={ }kill = { }
gen ={ 7 }kill = { 2,6 }
OUT = { 1, 2, 3 }IN = { 1, 2, 3, 4, 5, 6 }
OUT = IN = { }
OUT = IN = { 1, 2, 3, 4, 5, 6 }
OUT = IN = { 1, 2, 3, 4, 5, 6 }
OUT = { 4, 5, 6 } OUT = { 1, 2, 3, 4, 5, 6 } OUT = { 1, 3, 7 }IN = { 1, 2, 3, 7 }
![Page 198: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/198.jpg)
198
Ejemplo DUentry
k = false 1i = 1 2j = 2 3
j = j * 2 4k = true 5i = i + 1 6
print j i = i + 1 7
k
exit
i < n
gen ={ 1, 2, 3 }kill = { 4,5,6,7 }
gen ={ 4,5,6 }kill = { 1,2,3,7 }
gen ={ }kill = { }
gen ={ }kill = { }
gen ={ }kill = { }
gen ={ 7 }kill = { 2,6 }
OUT = { 1, 2, 3 }IN = { 1, 2, 3, 4, 5, 6 }
OUT = IN = { }
OUT = IN = { 1, 2, 3, 4, 5, 6 }
OUT = IN = { 1, 2, 3, 4, 5, 6 }
OUT = { 4, 5, 6 } OUT = { 1, 2, 3, 4, 5, 6 } OUT = { 1, 3, 7 }IN = { 1, 2, 3, 7 }
![Page 199: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/199.jpg)
199
Ejemplo DUentry
k = false 1i = 1 2j = 2 3
j = j * 2 4k = true 5i = i + 1 6
print j i = i + 1 7
k
exit
i < n
gen ={ 1, 2, 3 }kill = { 4,5,6,7 }
gen ={ 4,5,6 }kill = { 1,2,3,7 }
gen ={ }kill = { }
gen ={ }kill = { }
gen ={ }kill = { }
gen ={ 7 }kill = { 2,6 }
OUT = { 1, 2, 3 }IN = { 1, 2, 3, 4, 5, 6 }
OUT = IN = { }
OUT = IN = { 1, 2, 3, 4, 5, 6 }
OUT = IN = { 1, 2, 3, 4, 5, 6 }
OUT = { 4, 5, 6 } OUT = { 1, 2, 3, 4, 5, 6 } OUT = { 1, 3, 4, 5, 7 }IN = { 1, 2, 3, 7 }
![Page 200: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/200.jpg)
200
Ejemplo DUentry
k = false 1i = 1 2j = 2 3
j = j * 2 4k = true 5i = i + 1 6
print j i = i + 1 7
k
exit
i < n
gen ={ 1, 2, 3 }kill = { 4,5,6,7 }
gen ={ 4,5,6 }kill = { 1,2,3,7 }
gen ={ }kill = { }
gen ={ }kill = { }
gen ={ }kill = { }
gen ={ 7 }kill = { 2,6 }
OUT = { 1, 2, 3 }IN = { 1, 2, 3, 4, 5, 6 }
OUT = IN = { }
OUT = IN = { 1, 2, 3, 4, 5, 6 }
OUT = IN = { 1, 2, 3, 4, 5, 6 }
OUT = { 4, 5, 6 } OUT = { 1, 2, 3, 4, 5, 6 } OUT = { 1, 3, 4, 5, 7 }IN = { 1, 2, 3, 4, 5, 6, 7 }
![Page 201: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/201.jpg)
201
Ejemplo DUentry
k = false 1i = 1 2j = 2 3
j = j * 2 4k = true 5i = i + 1 6
print j i = i + 1 7
k
exit
i < n
gen ={ 1, 2, 3 }kill = { 4,5,6,7 }
gen ={ 4,5,6 }kill = { 1,2,3,7 }
gen ={ }kill = { }
gen ={ }kill = { }
gen ={ }kill = { }
gen ={ 7 }kill = { 2,6 }
OUT = { 1, 2, 3 }IN = { 1, 2, 3, 4, 5, 6 }
OUT = IN = { }
OUT = IN = { 1, 2, 3, 4, 5, 6 }
OUT = IN = { 1, 2, 3, 4, 5, 6 }
OUT = { 4, 5, 6 } OUT = { 1, 2, 3, 4, 5, 6 } OUT = { 1, 3, 4, 5, 7 }IN = { 1, 2, 3, 4, 5, 6, 7 }
![Page 202: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/202.jpg)
202
Ejemplo DUentry
k = false 1i = 1 2j = 2 3
j = j * 2 4k = true 5i = i + 1 6
print j i = i + 1 7
k
exit
i < n
gen ={ 1, 2, 3 }kill = { 4,5,6,7 }
gen ={ 4,5,6 }kill = { 1,2,3,7 }
gen ={ }kill = { }
gen ={ }kill = { }
gen ={ }kill = { }
gen ={ 7 }kill = { 2,6 }
OUT = { 1, 2, 3 }IN = { 1, 2, 3, 4, 5, 6 }
OUT = IN = { }
OUT = IN = { 1, 2, 3, 4, 5, 6 }
OUT = IN = { 1, 2, 3, 4, 5, 6 }
OUT = { 4, 5, 6 } OUT = { 1, 2, 3, 4, 5, 6 } OUT = { 1, 3, 4, 5, 7 }IN = { 1, 2, 3, 4, 5, 6, 7 }
![Page 203: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/203.jpg)
203
Ejemplo DUentry
k = false 1i = 1 2j = 2 3
j = j * 2 4k = true 5i = i + 1 6
print j i = i + 1 7
k
exit
i < n
gen ={ 1, 2, 3 }kill = { 4,5,6,7 }
gen ={ 4,5,6 }kill = { 1,2,3,7 }
gen ={ }kill = { }
gen ={ }kill = { }
gen ={ }kill = { }
gen ={ 7 }kill = { 2,6 }
OUT = { 1, 2, 3 }IN = { 1, 2, 3, 4, 5, 6 }
OUT = IN = { }
OUT = IN = { 1, 2, 3, 4, 5, 6 }
OUT = IN = { 1, 2, 3, 4, 5, 6 }
OUT = { 4, 5, 6 } OUT = { 1, 2, 3, 4, 5, 6 } OUT = { 1, 3, 4, 5, 7 }IN = { 1, 2, 3, 4, 5, 6, 7 }
![Page 204: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/204.jpg)
204
Ejemplo DUentry
k = false 1i = 1 2j = 2 3
j = j * 2 4k = true 5i = i + 1 6
print j i = i + 1 7
k
exit
i < n
gen ={ 1, 2, 3 }kill = { 4,5,6,7 }
gen ={ 4,5,6 }kill = { 1,2,3,7 }
gen ={ }kill = { }
gen ={ }kill = { }
gen ={ }kill = { }
gen ={ 7 }kill = { 2,6 }
OUT = { 1, 2, 3 }IN = { 1, 2, 3, 4, 5, 6 }
OUT = IN = { }
OUT = IN = { 1, 2, 3, 4, 5, 6 }
OUT = IN = { 1, 2, 3, 4, 5, 6 }
OUT = { 4, 5, 6 } OUT = { 1, 2, 3, 4, 5, 6 } OUT = { 1, 3, 4, 5, 7 }IN = { 1, 2, 3, 4, 5, 6, 7 }
![Page 205: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/205.jpg)
205
Ejemplo DUentry
k = false 1i = 1 2j = 2 3
j = j * 2 4k = true 5i = i + 1 6
print j i = i + 1 7
k
exit
i < n
gen ={ 1, 2, 3 }kill = { 4,5,6,7 }
gen ={ 4,5,6 }kill = { 1,2,3,7 }
gen ={ }kill = { }
gen ={ }kill = { }
gen ={ }kill = { }
gen ={ 7 }kill = { 2,6 }
OUT = { 1, 2, 3 }IN = { 1, 2, 3, 4, 5, 6 }
OUT = IN = { }
OUT = IN = { 1, 2, 3, 4, 5, 6 }
OUT = IN = { 1, 2, 3, 4, 5, 6 }
OUT = { 4, 5, 6 } OUT = { 1, 2, 3, 4, 5, 6 } OUT = { 1, 3, 4, 5, 7 }IN = { 1, 2, 3, 4, 5, 6, 7 }
![Page 206: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/206.jpg)
206
Ejemplo DUentry
k = false 1i = 1 2j = 2 3
j = j * 2 4k = true 5i = i + 1 6
print j i = i + 1 7
k
exit
i < n
gen ={ 1, 2, 3 }kill = { 4,5,6,7 }
gen ={ 4,5,6 }kill = { 1,2,3,7 }
gen ={ }kill = { }
gen ={ }kill = { }
gen ={ }kill = { }
gen ={ 7 }kill = { 2,6 }
OUT = { 1, 2, 3 }IN = { 1, 2, 3, 4, 5, 6 }
OUT = IN = { }
OUT = IN = { 1, 2, 3, 4, 5, 6 }
OUT = IN = { 1, 2, 3, 4, 5, 6 }
OUT = { 4, 5, 6 } OUT = { 1, 2, 3, 4, 5, 6 } OUT = { 1, 3, 4, 5, 7 }IN = { 1, 2, 3, 4, 5, 6, 7 }
![Page 207: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/207.jpg)
207
Ejemplo DUentry
k = false 1i = 1 2j = 2 3
j = j * 2 4k = true 5i = i + 1 6
print j i = i + 1 7
k
exit
i < n
gen ={ 1, 2, 3 }kill = { 4,5,6,7 }
gen ={ 4,5,6 }kill = { 1,2,3,7 }
gen ={ }kill = { }
gen ={ }kill = { }
gen ={ }kill = { }
gen ={ 7 }kill = { 2,6 }
OUT = { 1, 2, 3 }IN = { 1, 2, 3, 4, 5, 6 }
OUT = IN = { }
OUT = IN = { 1, 2, 3, 4, 5, 6 }
OUT = IN = { 1, 2, 3, 4, 5, 6 }
OUT = { 4, 5, 6 } OUT = { 1, 2, 3, 4, 5, 6 } OUT = { 1, 3, 4, 5, 7 }IN = { 1, 2, 3, 4, 5, 6, 7 }
![Page 208: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/208.jpg)
208
Ejemplo DUentry
k = false 1i = 1 2j = 2 3
j = j * 2 4k = true 5i = i + 1 6
print j i = i + 1 7
k
exit
i < n
gen ={ 1, 2, 3 }kill = { 4,5,6,7 }
gen ={ 4,5,6 }kill = { 1,2,3,7 }
gen ={ }kill = { }
gen ={ }kill = { }
gen ={ }kill = { }
gen ={ 7 }kill = { 2,6 }
OUT = { 1, 2, 3 }IN = { 1, 2, 3, 4, 5, 6 }
OUT = IN = { }
OUT = IN = { 1, 2, 3, 4, 5, 6 }
OUT = IN = { 1, 2, 3, 4, 5, 6 }
OUT = { 4, 5, 6 } OUT = { 1, 2, 3, 4, 5, 6 } OUT = { 1, 3, 4, 5, 7 }IN = { 1, 2, 3, 4, 5, 6, 7 }
![Page 209: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/209.jpg)
209
Ejemplo DUentry
k = false 1i = 1 2j = 2 3
j = j * 2 4k = true 5i = i + 1 6
print j i = i + 1 7
k
exit
i < n
IN = { 1, 2, 3, 4, 5, 6 }
IN = { }
IN = { 1, 2, 3, 4, 5, 6 }
IN = { 1, 2, 3, 4, 5, 6 }
IN = { 1, 2, 3, 4, 5, 6, 7 }
IN = { 1, 2, 3, 4, 5, 6 }
IN = { 1, 2, 3, 4, 5, 6 }
![Page 210: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/210.jpg)
210
Cadenas DU
• En cada uso de la variable, apunta a todas las posibles definiciones– Información muy útil– Usada en muchas optimizaciones
• Incorporar esta información en la representación– Forma SSA
![Page 211: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/211.jpg)
211
Resumen
• Overview de análisis de control de flujo• Expresiones Disponibles• Algoritmo para calcular expresiones
disponibles• Bit sets• Formulando un problema de análisis de flujo
de datos• Cadenas DU• Forma SSA
5
![Page 212: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/212.jpg)
212
Forma Static Single Assignment (SSA)
• Cada definición tiene un nombre único de variable– Nombre original + número de versión
• Cada uso se refiere a la definición por nombre
• ¿Qué hay acerca de posibles definiciones múltiples?– Agregamos nodos de union especiales (merge) para
que sólo pueda haber una definición (funciones
![Page 213: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/213.jpg)
213
Forma Static Single Assignment (SSA)
a = 1 b = a + 2c = a + ba = a + 1d = a + b
![Page 214: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/214.jpg)
214
Forma Static Single Assignment (SSA)
a = 1 b = a + 2c = a + ba = a + 1d = a + b
a1 = 1 b1 = a1 + 2c1 = a1 + b1
a2 = a1 + 1d1 = a2 + b1
![Page 215: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/215.jpg)
215
Forma Static Single Assignment (SSA)a = 1 c = a + 2
b = 1 c = b + 2
d = a + b + c
![Page 216: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/216.jpg)
216
Forma Static Single Assignment (SSA)a = 1 c = a + 2
b = 1 c = b + 2
d = a + b + c
a1 = 1 c1 = a1 + 2
b1 = 1 c2 = b1 + 2
c3 = (c1, c2)d1 = c3 + 2
![Page 217: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/217.jpg)
217
Ejemplo DUentry
k = false i = 1 j = 2
j = j * 2 k = true i = i + 1
print j i = i + 1
k
exit
i < n
![Page 218: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/218.jpg)
218
Ejemplo DUentry
k1 = false i1 = 1 j1 = 2
j2 = j3 * 2 k2 = true i2 = i3 + 1 print j3 i4 = i3 + 1
k3
i5 = (i3, i4)
exit
i3 = (i1, i2) j3 = (j1, j2) k3 = (k1, k2)
i1 < n
![Page 219: Compiladores Análisis de Flujo de Datos. 2 Resumen Overview de análisis de control de flujo Expresiones disponibles Algoritmo para calcular expresiones](https://reader038.vdocumento.com/reader038/viewer/2022102716/54ead12c4a795936438b50fe/html5/thumbnails/219.jpg)
219
Lecturas
• Ballena– Capítulo 12
• Tigre– 17.1 - 17.4, 19.1, 19.2