Selección de instrucciones

En informática , la selección de instrucciones es la etapa del backend de un compilador que transforma su representación intermedia (IR) de nivel medio en una IR de bajo nivel. En un compilador típico, la selección de instrucciones precede tanto a la planificación de instrucciones como a la asignación de registros ; por lo tanto, su IR de salida tiene un conjunto infinito de pseudoregistros (a menudo conocidos como temporales ) y puede estar —y normalmente lo está— sujeto a optimización de peephole . Por lo demás, se asemeja mucho al código máquina , bytecode o lenguaje ensamblador de destino .

Por ejemplo, para la siguiente secuencia de código IR de nivel medio

t1 = a t2 = b t3 = t1 + t2 a = t3 b = t1 

Una buena secuencia de instrucciones para la arquitectura x86 es

MOVER EAX , a CAMBIAR EAX , b AÑADIR a , EAX

Para un análisis exhaustivo sobre la selección de instrucción, consulte ^{[ 1 ] [ 2 ] .}

El enfoque más simple para la selección de instrucciones se conoce como expansión de macros ^{[ 3 ]} o generación de código interpretativo . ^{[ 4 ] [ 5 ] [ 6 ]} Un selector de instrucciones de expansión de macros opera haciendo coincidir plantillas sobre el IR de nivel medio. Al encontrar una coincidencia, se ejecuta la macro correspondiente , utilizando la porción coincidente del IR como entrada, que emite las instrucciones objetivo apropiadas. La expansión de macros puede hacerse directamente sobre la representación textual del IR de nivel medio, ^{[ 7 ] [ 8 ]} o el IR puede transformarse primero en una representación gráfica que luego se recorre en profundidad. ^{[ 9 ]} En este último caso, una plantilla coincide con uno o más nodos adyacentes en el grafo.

A menos que la máquina de destino sea muy simple, la expansión de macros aislada suele generar código ineficiente. Para mitigar esta limitación, los compiladores que aplican este enfoque suelen combinarlo con la optimización de peephole para reemplazar combinaciones de instrucciones simples con equivalentes más complejos que aumentan el rendimiento y reducen el tamaño del código. Esto se conoce como el enfoque de Davidson-Fraser y actualmente se aplica en GCC . ^{[ 10 ]}

Otro enfoque consiste en transformar primero el IR de nivel intermedio en un grafo y luego cubrirlo mediante patrones . Un patrón es una plantilla que coincide con una parte del grafo y puede implementarse con una sola instrucción proporcionada por la máquina de destino. El objetivo es cubrir el grafo de manera que se minimice el coste total de los patrones seleccionados, donde el coste suele representar el número de ciclos necesarios para ejecutar la instrucción. Para grafos con forma de árbol, la cobertura de menor coste puede encontrarse en tiempo lineal mediante programación dinámica ^{[ 11 ]} , pero para DAG y grafos completos el problema se vuelve NP-completo y, por lo tanto, se suele resolver mediante algoritmos voraces o métodos de optimización combinatoria ^{[ 12 ] [ 13 ] [ 14 ] .}

• Formas alternativas de dar soporte a diferentes generaciones de ordenadores