Selección de Código y Gramáticas Árbol

La generación de código es la fase en la que a partir de la Representación intermedia o IR se genera una secuencia de instrucciones para la máquina objeto. Esta tarea conlleva diversas subtareas, entre ellas destacan tres:

• La selección de instrucciones o selección de código,
• La asignación de registros y
• La planificación de las instrucciones.

El problema de la selección de código surge de que la mayoría de las máquinas suelen tener una gran variedad de instrucciones, habitualmente cientos y muchas instrucciones admiten mas de una decena de modos de direccionamiento. En consecuencia,

There Is More Than One Way To Do It (The Translation)

Es posible asociar una gramática árbol con el juego de instrucciones de una máquina. Las partes derechas de las reglas de producción de esta gramática vienen determinadas por el conjunto de árboles sintácticos de las instrucciones. La gramática tiene dos variables sintácticas que denotan dos tipos de recursos de la máquina: los registros representados por la variable sintáctica $R$ y las direcciones de memoria representadas por $M.$ Una instrucción deja su resultado en cierto lugar, normalmente un registro o memoria. La idea es que las variables sintácticas en los lados izquierdos de las reglas representan los lugares en los cuales las instrucciones dejan sus resultados.

Ademas, a cada instrucción le asociamos un coste:

Gramática Arbol Para un Juego de Instrucciones Simple
Producción	Instrucción	Coste
R $\rightarrow$ NUM	LOADC R, NUM	1
R $\rightarrow$ M	LOADM R, M	3
M $\rightarrow$ R	STOREM M, R	3
R $\rightarrow$ PLUS(R,M)	PLUSM R, M	3
R $\rightarrow$ PLUS(R,R)	PLUSR R, R	1
R $\rightarrow$ TIMES(R,M)	TIMESM R, M	6
R $\rightarrow$ TIMES(R,R)	TIMESR R, R	4
R $\rightarrow$ PLUS(R,TIMES(NUM,R))	PLUSCR R, NUM, R	4
R $\rightarrow$ TIMES(R,TIMES(NUM,R))	TIMESCR R, NUM, R	5

Consideremos la IR consistente en el AST generado por el front-end del compilador para la expresión x+3*(7*y):

                           PLUS(M[x],TIMES(N[3],TIMES(N[7],M[y])

Construyamos una derivación a izquierdas para el árbol anterior:

Una derivación árbol a izquierdas para $P(M,T(N,T(N,M)))$
Derivación	Producción	Instrucción	Coste
$R \Longrightarrow$	R $\rightarrow$ PLUS(R,R)	PLUSR R, R	1
$P(R,R) \Longrightarrow$	R $\rightarrow$ M	LOADM R, M	3
$P(M,R) \Longrightarrow$	R $\rightarrow$ TIMES(R,R)	TIMESR R, R	4
$P(M, T(R, R)) \Longrightarrow$	R $\rightarrow$ NUM	LOADC R, NUM	1
$P(M, T(N, R)) \Longrightarrow$	R $\rightarrow$ TIMES(R,R)	TIMESR R, R	4
$P(M, T(N, T(R, R))) \Longrightarrow$	R $\rightarrow$ NUM	LOADC R, NUM	1
$P(M, T(N, T(N, R))) \Longrightarrow$	R $\rightarrow$ M	LOADM R, M	3
$P(M,T(N,T(N,M)))$			Total: 17

Obsérvese que, si asumimos por ahora que hay suficientes registros, la secuencia de instrucciones resultante en la tercera columna de la tabla si se lee en orden inverso (esto es, si se sigue el orden de instrucciones asociadas a las reglas de producción en orden de anti-derivación) y se hace una asignación correcta de registros nos da una traducción correcta de la expresión x+3*(7*y):

LOADM R, M         # y 
LOADC R, NUM       # 7
TIMESR R, R        # 7*y
LOADC R, NUM       # 3
TIMESR R, R        # 3*(7*y)
LOADM R, M         # x
PLUSR R, R         # x+3*(7*y)

La gramática anterior es ambigua. El árbol de x+3*(7*y) puede ser generado también mediante la siguiente derivación a izquierdas:

Otra derivación árbol a izquierdas para $P(M,T(N,T(N,M)))$
Derivación	Producción	Instrucción	Coste
$R \Longrightarrow$	R $\rightarrow$ PLUS(R,TIMES(NUM,R))	PLUSCR R, NUM, R	4
$P(R,T(N,R)) \Longrightarrow$	R $\rightarrow$ M	LOADM R, M	3
$P(M, T(N, R)) \Longrightarrow$	R $\rightarrow$ TIMES(R,M)	TIMESM R, M	6
$P(M,T(N,T(R,M)))$	R $\rightarrow$ NUM	LOADC R, NUM	1
$P(M,T(N,T(N,M)))$			Total: 14

La nueva secuencia de instrucciones para x+3*(7*y) es:

LOADC R, NUM        # 7
TIMESM R, M         # 7*y
LOADM R, M          # x
PLUSCR R, NUM, R    # x+3*(7*y)

Cada antiderivación a izquierdas produce una secuencia de instrucciones que es una traducción legal del AST de x+3*(7*y).

El problema de la selección de código óptima puede aproximarse resolviendo el problema de encontrar la derivación árbol óptima que produce el árbol de entrada (en representación intermedia IR)

Definición 7.2.1   Un generador de generadores de código es una componente software que toma como entrada una especificación de la plataforma objeto -por ejemplo mediante una gramática árbol- y genera un módulo que es utilizado por el compilador. Este módulo lee la representación intermedia (habitualmente un árbol) y retorna código máquina como resultado.

Un ejemplo de generador de generadores de código es iburg [7].

Véase también el libro Automatic Code Generation Using Dynamic Programming Techniques y la página http://www.bytelabs.org/hburg.html

Ejercicio 7.2.1   Responda a las siguientes preguntas:

• Sea $G_M$ la gramática árbol asociada segun la descripción anterior con el juego de instrucciones de la máquina $M$. Especifique formalmente las cuatro componentes de la gramática $G_M = (\Sigma_M, V_M, P_M, S_M)$
• ¿Cual es el lenguaje árbol generado por $G_M$?
• ¿A que lenguaje debe pertenecer la representación intermedia IR para que se pueda aplicar la aproximación presentada en esta sección?