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]
Expansión macro
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]
Cobertura gráfica
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]
Referencias
- ^ Blindell, Gabriel S. Hjort (2013). Encuesta sobre selección de instrucción: una revisión bibliográfica extensa y moderna (informe). arXiv : 1306.4898 . ISBN 978-91-7501-898-0.
- ^ Blindell, Gabriel S. Hjort (2016). Selección de instrucciones: principios, métodos y aplicaciones. Springer. doi :10.1007/978-3-319-34019-7. ISBN 978-3-319-34017-3. Número de identificación del sujeto 13390131.
- ^ Brown, P. (1969). "Un estudio de los macroprocesadores". Revisión anual de programación automática . 6 (2): 37–88. doi :10.1016/0066-4138(69)90001-9. ISSN 0066-4138.
- ^ Cattell, RGG (1979). "A Survey and Critique of Some Models of Code Generation" (PDF) . Facultad de Ciencias de la Computación, Universidad Carnegie Mellon (informe técnico). Archivado (PDF) del original el 23 de mayo de 2019.
- ^ Ganapathi, M.; Fischer, CN; Hennessy, JL (1982). "Generación de código de compilador reorientable". Computing Surveys . 14 (4): 573–592. doi :10.1145/356893.356897. ISSN 0360-0300. S2CID 2361347.
- ^ Lunell, H. (1983). Sistemas de escritura de generadores de código (tesis doctoral). Linköping, Suecia: Universidad de Linköping.
- ^ Ammann, U.; Nori, KV; Jensen, K.; Nägeli, H. (1974). "Notas de implementación del compilador PASCAL (P)". Instituts für Informatik (Informe técnico).
- ^ Orgass, RJ; Waite, WM (1969). "Una base para un sistema de programación móvil". Comunicaciones de la ACM . 12 (9): 507–510. doi : 10.1145/363219.363226 . S2CID 8164996.
- ^ Wilcox, TR (1971). Generación de código de máquina para lenguajes de programación de alto nivel (tesis doctoral). Ithaca, Nueva York, EE. UU.: Cornell University.
- ^ Davidson, JW; Fraser, CW (1984). "Selección de código mediante optimización de código objeto". ACM Transactions on Programming Languages and Systems . 6 (4): 505–526. CiteSeerX 10.1.1.76.3796 . doi :10.1145/1780.1783. ISSN 0164-0925. S2CID 10315537.
- ^ Aho, AV; Ganapathi, M.; Tjiang, SWK (1989). "Generación de código mediante emparejamiento de árboles y programación dinámica". ACM Transactions on Programming Languages and Systems . 11 (4): 491–516. CiteSeerX 10.1.1.456.9102 . doi :10.1145/69558.75700. S2CID 1165995.
- ^ Wilson, T.; Grewal, G.; Halley, B.; Banerji, D. (1994). "Un enfoque integrado para la generación de código reorientable". Actas del 7º Simposio Internacional sobre Síntesis de Alto Nivel . págs. 70–75. CiteSeerX 10.1.1.521.8288 . doi :10.1109/ISHLS.1994.302339. ISBN . 978-0-8186-5785-6.S2CID14384424 .
- ^ Bashford, Steven; Leupers, Rainer (1999). "Selección de código basada en restricciones para DSPS de punto fijo". Actas de la 36.ª conferencia ACM/IEEE sobre automatización del diseño - DAC '99 . págs. 817–822. CiteSeerX 10.1.1.331.390 . doi :10.1145/309847.310076. ISBN . 978-1581331097. Número de identificación del sujeto 5513238.
- ^ Floch, A.; Wolinski, C.; Kuchcinski, K. (2010). "Programación combinada y selección de instrucciones para procesadores con estructura de celdas reconfigurable". Actas de la 21.ª Conferencia internacional sobre arquitecturas y procesadores específicos de aplicaciones (ASAP'10) : 167–174.
Enlaces externos
