El Teorema de los 4 Colores Aplicado a los Compiladores

El Teorema de los 4 Colores establece que cualquier plano dividido en regiones contiguas puede ser coloreado usando 4 colores, de forma que dos regiones adyacentes cualesquiera (que tengan un borde en común, no sólo un punto) tienen colores distintos. Por ejemplo, el siguiente plano dividido puede colorearse con sólo 4 colores:

Aunque hay casos en que es posible colorear un plano de forma válida usando menos colores, el teorema se sigue cumpliendo, ya que dice que hacen falta como mucho 4. Una aplicación directa de este teorema se encuentra en la cartografía y el coloreado de mapas políticos. Sin embargo, este teorema es bastante más importante que sólo eso, y es que además se mantuvo sin demostrar desde 1852 hasta que en 1976 se convirtió en el primer gran teorema demostrado por computador, si bien hay quien se mostraba reacio a ello por aquello de suponer la correción del programa, compilador y hardware.

Enunciado Formal en Teoría de Grafos

En teoría de grafos, el problema se puede formular convirtiendo el mapa en un grafo plano tal que cada región es un vértice y las aristas van desde los vértices que se corresponden con regiones adyacentes. La solución sería aquella en la que cada vértice tiene un color, de forma que dos vértices adyacentes no tengan el mismo color.

La demostración, que en 1976 llevaron a cabo Kenneth Appel y Wolfgang Haken se basó en demostrar que no existía ningún vértice adicional para ningún grafo tal que fueran necesarios 5 colores. Por ello, se dice que un grafo plano correspondiente a un mapa es, como mucho, un grafo 4-coloreable.

En general, un grafo es k-coloreable si necesita k colores como mínimo para ser coloreado. A este número se le llama número cromático del grafo, y se representa con la letra χ. El problema de calcular el número cromático de un grafo es NP-duro, aunque existen distintos algoritmos de clase P que se basan en ciertas asunciones para tipos concretos de grafo.

Coloreado de Grafos en Compiladores

La aplicación de la coloración de grafos en compiladores es una de las cosas que me dejó sorprendido cuando lo estudié, por el ingenio del que se hace gala. Cuando un compilador ha calculado ya la serie de instrucciones para máquina abstracta, el siguiente paso es asignar los registros de la CPU a cada variable, teniendo en cuenta cuando se necesita cada una y cuando deja de utilizarse, para optimizar la ejecución al máximo y acceder a memoria el menor número de veces posible, agilizando así la ejecución.

La forma usual de resolver este problema empieza con un análisis de flujo, del que se calcula el llamado grafo de interferencia. Por ejemplo, dado el siguiente código que empieza con las variables k y j, y termina con las variables d, k y j:

1. k, j
2. g = mem[ j + 12 ]
3. h = k -1
4. f = g * h
5. e = mem[ j + 8 ]
6. m = mem[ j + 16 ]
7. b = mem[ f ]
8. c = e + 8
9. d = c
10. k = m * 4
11. j = b
12. d, k, j

la cosa consiste en ir desde el final hasta el principio, marcando por cada variable cuales son las transiciones en las que es necesario guardar su valor. Por ejemplo, d es necesaria en la transición 11→12, ya que su valor debe ser devuelto en el estado 12. Paso a paso hacia atrás, se ve que en el estado 9 se le asigna un valor, por lo que ha de mantenerse hasta el estado 12. Si continuamos hacia atrás, se ve que no es usada anteriormente, por lo que se concluye que d debe mantenerse en las transiciones 9→10→11→12. De forma parecida, j debe mantenerse en 11→12, ya que es en 11 donde se le asigna un valor. Sin embargo, retrocediento puede verse que desde el estado 1 es usada hasta el estado 6, a partir de donde su valor puede desecharse hasta el estado 11. Así pues, j debe mantenerse en las transiciones 1→2→3→4→5→6 y 11→12. Continuando con cada variable, construimos la siguiente matriz de interferencia:

Matriz que, a su vez, se corresponde con el siguiente grafo de interferencia, en donde cada vértice es una variable y las aristas unen las variables que están vivas al mismo tiempo y, por tanto, deben estar en registros distintos de la CPU:

Como se ve, el grafo puede colorearse de forma válida con 4 colores. La idea detrás de este grafo es que dos vértices adyacentes contienen variables que deben guardarse en registros distintos. Así, el color asignado a cada vértice se corresponde con un registro de la CPU, y por ello ambos vértices deben tener colores distintos.

De esta forma, 4 registros son válidos para el anterior programa, asignando cada variable al registro de color correspondiente. En general, si la CPU tiene n registros y el número cromático del grafo de interferencia es m, no será necesario llevar variables a la memoria RAM si m es menor o igual que n. Sin embargo, una parte que nos hemos saltado es la de optimización del código. Dejando de lado aquello de que hay operaciones no necesarias (la verdad es que las instrucciones del ejemplo son bastante enrevesadas), un punto a tener en cuenta es que j actúa como dos variables distintas: j₁ entre 1→2→3→4→5→6 y j₂ entre 10→11→12, ocurriendo lo mismo con k. Tomando ventaja de ello, la matriz de interferencia (y el correspondiente grafo) puede colorearse de la siguiente forma:

Como se ve, ahora son necesarios sólo 3 registros. En particular, el grafo optimizado con j₁, j₂, k₁ y k₂ es 3-coloreable, mientras que el que usa j y k es 4-coloreable. De hecho, puede apreciarse que j usa colores distintos en la matriz de interferencia optimizada, debido a que se consideran 2 variables distintas (ocurriendo lo mismo con k). El problema de calcular el número cromático en estos casos es más sencillo, porque es el mayor número de variables que estén vivas en una misma transición (número de variables vivas en una misma columna de la matriz de interferencia). En el ejemplo podemos ver que cada columna tiene como máximo 3 variables vivas, así que 3 registros son suficientes para el programa.