Figure 1

Procesos básicos de un compilador

Típicamente, el proceso de compilación se divide en un número de pasos identificables, como se muestra en la Figure 1. Aunque no todos los compiladores estén implementados exactamente de esta manera, ayuda a comprender las diferentes funciones que éstos deben realizar:

Conforme los compiladores se vuelven más y más sofisticados para poder dar hasta el último bit de rendimiento del procesador, algunos de estos pasos (especialmente los de optimización y generación de código) se vuelven más y más confusos. En este capítulo nos enfocaremos en el optimizador de código tradicional de un compilador, y en los capítulos subsecuentes revisaremos más de cerca cómo hacen optimizaciones más sofisticadas los compiladores modernos.

Como estamos más interesados en la optimización de nuestro programa, comenzaremos nuestra discusión a partir de la salida de la fase de análisis sintáctico del compilador. Dicha salida está en la forma de un lenguaje intermedio (LI), algo entre un lenguaje de alto nivel y un lenguaje ensamblador. El lenguaje intermedio expresa los mismos cálculos que en el programa original, en una forma que el compilador pueda manipular más fácilmente. Es más, ciertas instrucciones que no están presentes en el fuente, tales como expresiones de direccionamiento para referencias a arreglos, se hacen visibles junto con el resto del programa, haciéndolo también de este modo sujeto de optimización.

¿Cómo luce un lenguaje intermedio? En términos de complejidad, es similar a un código ensamblador, pero no tan simple como para que se pierdan las definiciones1 y usos de las variables. Necesitaremos la información acerca de definición y uso para analizar el flujo de datos a través del programa. Típicamente los cálculos se expresan como u flujo de cuádruplas — sentencias con exactamente un operador, (hasta) dos operandos, y un resultado.2 Presuponiendo que cualquier cosa en el programa fuente original pueda cambiar su representación en términos de cuádruplas, tenemos un lenguaje intermedio utilizable. Para darnos una idea de cómo trabaja, reescribiremos la sentencia siguiente como una serie de cuatro cuádruplas:

A = -B + C * D / E 
    

Tomando todo como una unidad, la sentencia tiene cuatro operadores y cuatro operandos: /, *, + y - (negación), y B, C, D, y E. Claramente es demasiado para que quepa en una cuádrupla. Necesitamos una forma con exactamente un operador y, cuando mucho, dos operandos por sentencia. La versión que sigue lo lleva a cabo, empleando variables temporales para almacenar los resultados intermedios:

      T1 = D / E 
      T2 = C * T1
      T3 = -B
      A  = T3 + T2
    

Por supuesto, un lenguaje intermedio utilizable requiere de algunas otras características, como apuntadores. Estamos por sugerir la creación de nuestro propio lenguaje intermedio para investigar cómo trabajan las optimizaciones. Para comenzar, necesitamos establecer unas pocas reglas:

Si estamos construyendo un compilador, deberemos ser un poco más específicos. Para nuestros propósitos con esto basta. Considere el siguiente fragmento de código en C:

      while (j < n) {
          k = k + j * 2;
          m = j * 2;
          j++;
      }
    

Este ciclo se traduce en la representación en lenguaje intermedio que se muestra a continuación:

      A:: t1  := j 
          t2  := n
          t3  := t1 < t2 
          jmp (B) t3
          jmp (C) TRUE
    
      B:: t4  := k 
          t5  := j
          t6  := t5 * 2 
          t7  := t4 + t6 
          k   := t7
          t8  := j
          t9  := t8 * 2 
          m   := t9
          t10 := j
          t11 := t10 + 1 
          j   := t11
          jmp (A) TRUE
      C::
    

Cada línea de código fuente en C se representa mediante varias sentencias en LI. En muchos procesadores RISC, nuestro código LI es tan parecido al lenguaje máquina que podemos traducirlo directamente a código objeto.3 A menudo el nivel más bajo de optimización consiste en una traducción literal del lenguaje intermedio a código máquina. Cuando esto sucede, el código generalmente es muy largo y su rendimiento es pobre. Al revisarlo, puede usted encontrar lugares donde ahorrar unas pocas instrucciones. Por ejemplo, j se carga en variables temporales en cuatro lugares; seguramente podemos reducirlo. Tenemos que realizar algo de análisis y algunas optimizaciones.

Tras generar nuestro lenguaje intermedio, queremos cortarlo en bloques básicos. Se trata de secuencias de código que comienzan con una instrucción que o bien sigue una bifurcación o es en sí misma el destino de un salto. Dicho de otra forma, cada bloque básico tiene una entrada (en la parte superior) y una salida (en la parte inferior). Figure 2 representa nuestro código LI como un grupo de tres bloques básicos. Estos bloques hacen el código más fácil de analizar. Al restringir el flujo de control al interior de un bloque básico de arriba hacia abajo y eliminar todas las bifurcaciones, podemos asegurarnos que si se ejecuta la primera sentencia, también lo hará la segunda, y así sucesivamente. Por supuesto, las bifurcaciones no han desaparecido, pero las hemos forzado afuera de los bloques en la forma de flechas de conexión - el grafo de flujo.

Figure 2

Lenguaje intermedio dividido en bloques básicos

Ahora somos libres de extraer información de los bloques mismos. Por ejemplo, podemos decir con certeza cuáles variables usa cierto bloque, y cuáles define (les asigna valor), cosa que no hubiéramos podido ser capaces de hacer si el bloque contuviera una bifurcación. También podemos reunir la misma clase de información sobre los cálculos que realizan. Tras haber analizado los bloques, de forma tal que sepamos qué entra y qué sale de ellos, podemos modificarlos para mejorar el rendimiento, sin preocuparnos acerca de la interacción entre bloques.