analisis de diagrama de flujo

Compiladores
Análisis de Flujo de Datos

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

2

Representando el control de flujo
del progama
• Forma un grafo

• Un grafo muy grande
• Crear BloquesBásicos
• Un Grafo de Control de Flujo (CFG) conecta
los Bloques Básicos
3

Grafo de Control de Flujo (CFG)
• Control-Flow Graph G =
• 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

4

Identificando loops de estructuras
recursivas
• Identificar aristas de retorno
• Encontrar losnodos 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?
5

bb1

bb2
bb3

bb4
bb5
bb6

Computando Dominators
• Algoritmo
– Hacer que elconjunto 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

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 hayancambios

7

{bb1} bb1

bb2
bb3

bb4
bb5
bb6

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 conjuntode
dominators del nodo predecesor
y el nodo actual
– Repetir hasta que no hayan
cambios

8

{bb1} bb1

bb1
bb2
bb3
bb4
bb5
bb6

bb1
bb2
bb3
bb4
bb5
bb6

bb2

bb3
bb1
bb2
bb3
bb4
bb5
bb6
bb1
bb2
bb3
bb4
bb5
bb6

bb4
bb5
bb6

bb1
bb2
bb3
bb4
bb5
bb6

Computando Dominators
• Algoritmo
– Hacer que el conjunto de
dominators del nodo de entradasó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

9

{bb1} bb1

bb1
bb2
bb3
bb4
bb5
bb6

bb1
bb2
bb3bb4
bb5
bb6

bb2

bb3
bb1
bb2
bb3
bb4
bb5
bb6
bb1
bb2
bb3
bb4
bb5
bb6

bb4
bb5
bb6

bb1
bb2
bb3
bb4
bb5
bb6

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

10

{bb1} bb1

bb1
bb2
bb3
bb4
bb5
bb6

bb1
bb2
bb3
bb4
bb5
bb6

bb2

bb3
bb1
bb2
bb3
bb4
bb5
bb6
bb1
bb2
bb3
bb4
bb5
bb6

bb4
bb5
bb6

bb1
bb2
bb3
bb4
bb5
bb6

Computando...