Para construir un GAD, el compilador toma cada tupla de lenguaje intermedio y lo mapea sobre uno o más nodos. Por ejemplo, aquellas tuplas que representan operaciones binarias, tales como suma (
X=A+B ), forman una porción del GAD con dos entradas (
A y
B ) enlazadas por una operación (
+ ). El resultado de la operación puede alimentarse a su vez en otras operaciones en el bloque básico (y el GAD), como se muestra en
[link] .
Un grafo de flujo de datos trivial
Si se trata de un bloque de código básico, construimos nuestro GAD en el orden de las instrucciones. El GAD de para las cuatro instrucciones previas se muestra en [link] . Este ejemplo en particular tiene muchas dependencias, así que no hay mucha oportunidad para el paralelismo. [link] muestra un ejemplo más sencillo sobre cómo construir un GAD permite identificar el paralelismo.
A partir de este GAD, podemos determinar que las instrucciones 1 y 2 pueden ejecutarse en paralelo. Dado que vemos los cálculo que se realizan sobre los valores
A y
B durante el procesamiento de la instrucción 4, podemos eliminar una subexpresión común durante la construcción del GAD. Si podemos determinar que
Z es la única variable que se usa afuera de este pequeño bloque de código, podemos asumir que el cálculo de
Y es código muerto.
Un grafo de flujo de datos más complejo
Al construir el GAD, tomamos una secuencia de instrucciones y determinamos cuáles deben ejecutarse en un orden particular, y cuáles pueden ejecutarse en paralelo. Este tipo de análisis de flujo de datos es muy importante en la fase de generación de código en los procesadores superescalares. Hemos introducido el concepto de dependencias y cómo usar el flujo de datos para encontrar oportunidades de paralelismo en secuencias de código adentro de un bloque básico. También podemos usar el análisis de flujo de datos para identificar dependencias, oportunidades para el paralelismo, y código muerto al interior de bloques básicos.
Usos y definiciones
Conforme se construye el GAD, el compilador puede crear listas de usos y
definiciones de variables, así como otra información, y aplicarlas a las optimizaciones globales a través de muchos bloques básicos tomados junto. Al revisar el GAD en
[link] , podemos ver que las variables definidas son
Z ,
Y ,
X ,
C , y
D , y que las variables usadas son
A y
B . Al tomar en cuenta muchos bloques como uno solo, podemos decir cuan lejos alcanza la definición de una variable particular —dónde puede verse su valor. A partir de esto podemos reconocer situaciones en las cuales se descartan cálculos, lugares donde dos usos de una variable dada son completamente independientes, o dónde podemos reescribir valores residentes en registros sin tener que regresarlos a memoria. Llamamos a este tipo de investigación
análisis de flujo de datos .
Extracting parallelism from a dag
Para ilustrarlo, supongamos que tenemos el grafo de flujo de [link] . Junto a cada bloque básico hemos listado las variables que usa y las variables que define. ¿Qué nos puede decir al respecto el análisis del flujo de datos?
Observe que el valor de
A se definió en el bloque
X , pero sólo se usó en el bloque
Y . Ello significa que
A está muerto hasta la salida del bloque
Y o inmediatamente antes de tomar la rama derecha al dejar
X ; ninguno de los otros bloques básicos usan el valor de A. Ello nos dice que cualesquiera recursos asociados, tales como un registro, pueden liberarse para otros usos.
En la
[link] podemos ver que
D está definida en el bloque básico
X , pero jamás utilizada. Ello significa que los cálculos que definen a
D pueden descartarse.
Algo interesante está sucediendo con la variable
G . Tanto el bloque
X como el
W la utilizan, pero si observa detenidamente verá que los dos usos son distintos, significando que pueden tratarse como dos variables independientes.
Un compilador que instrumente técnicas avanzadas para la planificación adelantada de instrucciones, debe notar que
W es el único bloque que usa el valor de
E , y así mover los cálculos que definen
E fuera del bloque
Y y dentro de
W , donde se requieren.
Grafo de flujo para análisis de flujo de datos.
Además de recopilar datos acerca de las variables, el compilador también puede mantener información acerca de subexpresiones. Al examinarlas juntas, puede reconocer casos donde se hacen cálculos redundantes (a lo largo de bloques básicos), y sustituirlos por cálculos previamente realizados. Si, por ejemplo, la expresión
H*I aparece en los bloques
X ,
Y , y
W , puede calcularse sólo una vez en el bloque
X , y propagarse a los otros que la usan.