Tal como la asignación de variables puede depender de otras asignaciones, el valor de una variable puede depender también del flujo de control del programa. Por ejemplo, una asignación adentro de una sentencia condicional sólo puede ocurrir si la condición se evalúa como verdadera. Lo mismo puede decirse de una asignación al interior de un ciclo; si nunca se entra en dicho ciclo, ninguna sentencia en su interior se ejecutará.

Cuando los cálculos ocurren como consecuencia del flujo de control, decimos que se trata de una dependencia de control, tal como en el código que aparece más abajo y que se explica gráficamente en Figure 1. La asignación ubicada dentro del bloque condicional puede o no ejecutarse, dependiendo del resultado de la prueba X .NE. 0. En otras palabras, el valor de Y depende del flujo de control en el código a su alrededor. Nuevamente, esto puede sonarle a usted como un asunto que sólo le importa a los diseñadores de compiladores, y no a los programadores, cosa que es mayormente cierta. Pero hay veces que usted deseará mover tales instrucciones dependientes del control, para así quitar del camino costosos cálculos (suponiendo que su compilador no sea lo suficientemente inteligente para hacerlo por usted). Por ejemplo, digamos que Figure 2 representa una pequeña sección de su programa. El flujo de control inicia en la parte superior y avanza a lo largo de dos decisiones. Por otro lado, digamos que hay una operación de raíz cuadrada en el punto de entrada, y que el flujo de control casi siempre inicia en la parte de arriba y baja por la rama que contiene la sentencia A=0.0. Ello significa que el resultado del cálculo A=SQRT(B) casi siempre se descargará, porque A obtiene un nuevo valor de 0.0 cada vez. Una operación de raíz cuadrada siempre es "cara", porque toma mucho tiempo en ejecutarse. El problema es que usted no puede simplemente quitarla de ahí, puesto que ocasionalmente se requiere. Sin embargo, puede quitarla del camino y continuar observando las dependencias e control, haciendo dos copias de la operación de raíz cuadrada a lo largo de la bifurcación menos recorrida, como se muestra en Figure 3. De esta forma el código SQRT sólo se ejecutará a lo largo de tales rutas cuando realmente se requiera.

Figure 1

Dependencia de control

Figure 2

Una pequeña sección de nuestro programa

Esta clase de planificación de instrucciones irá apareciendo en los compiladores (e incluso en el hardware) más y más conforme pase el tiempo. Una variante de esta técnica es calcular los resultados que se requieran en aquellos momentos donde haya una brecha en el flujo de instrucciones (debido a las dependencias), usando así algunos ciclos sobrantes, que de otro modo se desperdiciarían.

Figure 3

La operación cara se movió, de forma que se ejecute pocas veces

Un cálculo que está ligado en cierta forma con uno previo, se dice que presenta dependencia de los datos con respecto a este último. En el código siguiente, el valor de B es dependiente de los datos con respecto de A. Ello se debe a que no puede usted calcular B hasta que el valor de A esté disponible:

      A = X + Y + COS(Z) 
      B = A * C 
    

Esta dependencia es fácil de reorganizar, pero otras no lo son tanto. En otras ocasiones, deberá usted ser cuidadoso de no reescribir una variable con un nuevo valor antes de que otro cálculo haya terminado de usar el valor previo. Podemos agrupar todas las dependencias de datos en tres categorías: (1) dependencias del flujo, (2) antidependencias, y (3) dependencias de la salida. Figure 4 contiene algunos ejemplos sencillos que demuestran cada tipo de dependencia. En cada ejemplo, usamos una flecha que inicia en el origen de la dependencia, y termina en la sentencia que debe retrasarse por causa de la dependencia. El problema clave en cada una de esas dependencias, es que la segunda sentencia no puede ejecutarse hasta que se haya completado la primera. Obviamente en el ejemplo de dependencia de salida en particular, el primer cálculo es código muerto y puede eliminarse, a menos que intervenga algún código que requiera de esos valores. Hay otras técnicas para eliminar ya sean las dependencias de salida o las antidependencias. El siguiente ejemplo contiene una dependencia de flujo seguida por una dependencia de salida:

Figure 4

Tipos de dependencias de datos

      X = A / B 
      Y = X + 2.0
      X = D - E 
    

Aunque no podamos eliminar la dependencia de flujo, sí podemos lograrlo con la dependencia de salida agregando una variable nueva:

      Xtemp = A/B
      Y = Xtemp + 2.0
      X = D - E 
    

Conforme crece el número de sentencias e interacciones entre ellas, necesitamos una forma mejor de identificar y procesar tales dependencias.Figure 5 muestra cuatro sentencias con cuatro dependencias.

Figure 5

Dependencias múltiples

Ninguna de las instrucciones, de la segunda hasta la cuarta, pueden iniciarse antes de que se complete la primera instrucción.

Un método para analizar una secuencia de instrucciones, es organizarlas en ungrafo acíclico dirigido (GAD).1 Tal como las instrucciones que representa, un GAD describe todos los cálculos y relaciones entre variables. El flujo de datos en el GAD procede en una sola dirección; la mayoría de las ocasiones el GAD se construye de arriba hacia abajo. Los identificadores y las constantes se colocan en los nodos "hoja" -los que están en la parte superior. Las operaciones, posiblemente con los nombres de las variables adjuntos, se encuentran en los nodos internos. Las variables aparecen en sus estados finales en la parte inferior. Las aristas del GAD ordenan las relaciones entre las variables y las operaciones entre ellas. Todo el flujo de datos transcurre de arriba hacia abajo.

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 Figure 6.

Figure 6

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 Figure 7. Este ejemplo en particular tiene muchas dependencias, así que no hay mucha oportunidad para el paralelismo. Figure 8 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.

Figure 7

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.

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 Figure 8, 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.

Figure 8

Extracting parallelism from a DAG

Para ilustrarlo, supongamos que tenemos el grafo de flujo de Figure 9. 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 Figure 9 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.

Figure 9

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.