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 programación de instrucciones como a la asignación de registros ; por lo tanto, su IR de salida tiene un conjunto infinito de pseudorregistros (a menudo conocidos como temporales ) y aún puede estar (y normalmente lo está) sujeto a optimización de mirilla . De lo contrario, se parece mucho al código de máquina de destino , al código de bytes o al lenguaje ensamblador .

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

t1 = at2 = bt3 = t1 + t2a = t3b = t1

Una buena secuencia de instrucciones para la arquitectura x86 es

MOV EAX , a XCHG EAX , b AGREGAR a , EAX      

Para una encuesta completa 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 macro ^[3] o generación de código interpretativo . ^{[4] [5] [6]} Un selector de instrucciones de expansión de macro funciona haciendo coincidir plantillas sobre el IR de nivel medio. Tras una coincidencia, se ejecuta la macro correspondiente , utilizando la parte coincidente del IR como entrada, que emite las instrucciones de destino adecuadas. La expansión de macro se puede realizar directamente en la representación textual del IR de nivel medio, ^{[7] [8]} o el IR se puede transformar 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 gráfico.

A menos que la máquina de destino sea muy simple, la expansión de macros de forma aislada suele generar código ineficiente. Para mitigar esta limitación, los compiladores que aplican este enfoque suelen combinarlo con la optimización de mirilla 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 Davidson-Fraser y actualmente se aplica en GCC . ^[10]

Otro enfoque es transformar primero el IR de nivel medio en un gráfico y luego cubrir el gráfico utilizando patrones . Un patrón es una plantilla que coincide con una parte del gráfico y se puede implementar con una sola instrucción proporcionada por la máquina de destino. El objetivo es cubrir el gráfico de manera que se minimice el costo total de los patrones seleccionados, donde el costo generalmente representa la cantidad de ciclos que se necesitan para ejecutar la instrucción. Para los gráficos en forma de árbol, la cobertura de menor costo se puede encontrar en tiempo lineal utilizando programación dinámica , ^[11] pero para DAG y gráficos completos el problema se vuelve NP-completo y, por lo tanto, se resuelve con mayor frecuencia utilizando algoritmos voraces o métodos de optimización combinatoria. ^{[12] [13] [14]}

• Formas alternativas de dar soporte a distintas generaciones de ordenadores ^{[ enlace muerto permanente ]}